Instruction selection explained

In computer science, instruction selection is the stage of a compiler backend that transforms its middle-level intermediate representation (IR) into a low-level IR. In a typical compiler, instruction selection precedes both instruction scheduling and register allocation; hence its output IR has an infinite set of pseudo-registers (often known as temporaries) and may still be – and typically is – subject to peephole optimization. Otherwise, it closely resembles the target machine code, bytecode, or assembly language.

For example, for the following sequence of middle-level IR code

t1 = a
t2 = b
t3 = t1 + t2
a = t3
b = t1

a good instruction sequence for the x86 architecture is

MOV EAX, aXCHG EAX, bADD a, EAX

For a comprehensive survey on instruction selection, see.[1] [2]

Macro expansion

The simplest approach to instruction selection is known as macro expansion[3] or interpretative code generation.[4] [5] [6] A macro-expanding instruction selector operates by matching templates over the middle-level IR. Upon a match the corresponding macro is executed, using the matched portion of the IR as input, which emits the appropriate target instructions. Macro expansion can be done either directly on the textual representation of the middle-level IR,[7] [8] or the IR can first be transformed into a graphical representation which is then traversed depth-first.[9] In the latter, a template matches one or more adjacent nodes in the graph.

Unless the target machine is very simple, macro expansion in isolation typically generates inefficient code. To mitigate this limitation, compilers that apply this approach typically combine it with peephole optimization to replace combinations of simple instructions with more complex equivalents that increase performance and reduce code size. This is known as the Davidson-Fraser approach and is currently applied in GCC.[10]

Graph covering

Another approach is to first transform the middle-level IR into a graph and then cover the graph using patterns. A pattern is a template that matches a portion of the graph and can be implemented with a single instruction provided by the target machine. The goal is to cover the graph such that the total cost of the selected patterns is minimized, where the cost typically represents the number of cycles it takes to execute the instruction. For tree-shaped graphs, the least-cost cover can be found in linear time using dynamic programming,[11] but for DAGs and full-fledged graphs the problem becomes NP-complete and thus is most often solved using either greedy algorithms or methods from combinatorial optimization.[12] [13] [14]

External links

Notes and References

  1. Blindell . Gabriel S. Hjort . Survey on Instruction Selection: An Extensive and Modern Literature Review . 2013 . 1306.4898 . 978-91-7501-898-0.
  2. Book: Blindell , Gabriel S. Hjort . Instruction Selection: Principles, Methods, & Applications . Springer . 10.1007/978-3-319-34019-7 . 2016 . 978-3-319-34017-3 . 13390131.
  3. Brown. P.. 1969. A Survey of Macro Processors. Annual Review in Automatic Programming. 6. 2. 37–88. 0066-4138. 10.1016/0066-4138(69)90001-9.
  4. Cattell. R. G. G.. 1979. A Survey and Critique of Some Models of Code Generation. https://web.archive.org/web/20190523223442/https://apps.dtic.mil/dtic/tr/fulltext/u2/a056027.pdf. live. May 23, 2019. School of Computer Science, Carnegie Mellon University. Technical report.
  5. Ganapathi. M.. Fischer. C. N.. Hennessy. J. L.. 1982. Retargetable Compiler Code Generation. Computing Surveys. 14. 4. 573–592. 0360-0300. 10.1145/356893.356897. 2361347.
  6. Book: Lunell, H.. Code Generator Writing Systems. Linköping University. 1983. Linköping, Sweden. Doctoral thesis.
  7. Ammann. U.. Nori. K. V.. Jensen. K.. Nägeli. H.. 1974. The PASCAL (P) Compiler Implementation Notes. Instituts für Informatik. Technical report.
  8. Orgass. R. J.. Waite. W. M.. 1969. A Base for a Mobile Programming System. Communications of the ACM. 12. 9. 507–510. 10.1145/363219.363226. 8164996. free.
  9. Book: Wilcox, T. R.. Generating Machine Code for High-Level Programming Languages. Cornell University. 1971. Ithaca, New York, USA. Doctoral thesis.
  10. Davidson. J. W.. Fraser. C. W.. 1984. Code Selection Through Object Code Optimization. ACM Transactions on Programming Languages and Systems. 6. 4. 505–526. 0164-0925. 10.1145/1780.1783. 10.1.1.76.3796. 10315537.
  11. Aho. A. V.. Ganapathi. M.. Tjiang. S. W. K.. 1989. Code Generation Using Tree Matching and Dynamic Programming. ACM Transactions on Programming Languages and Systems. 11. 4. 491–516. 10.1145/69558.75700. 10.1.1.456.9102. 1165995.
  12. Book: Wilson. T.. Grewal. G.. Halley. B.. Banerji. D.. Proceedings of 7th International Symposium on High-Level Synthesis . An integrated approach to retargetable code generation . 1994. 70–75. 10.1109/ISHLS.1994.302339. 10.1.1.521.8288. 978-0-8186-5785-6. 14384424.
  13. Book: 10.1145/309847.310076. 10.1.1.331.390. 978-1581331097. Constraint driven code selection for fixed-point DSPS. Proceedings of the 36th ACM/IEEE conference on Design automation conference - DAC '99. 817–822. 1999. Bashford. Steven. Leupers. Rainer. 5513238.
  14. Floch. A.. Wolinski. C.. Kuchcinski. K.. 2010. Combined Scheduling and Instruction Selection for Processors with Reconfigurable Cell Fabric. Proceedings of the 21st International Conference on Application-Specific Architectures and Processors (ASAP'10). 167–174.

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Instruction selection".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.