Editing Code generation (compiler) (section)

==Major tasks==
In addition to the basic conversion from an intermediate representation into a linear sequence of machine instructions, a typical code generator tries to optimize the generated code in some way.

Tasks which are typically part of a sophisticated compiler's "code generation" phase include:
* [[Instruction selection]]: which instructions to use.
* [[Instruction scheduling]]: in which order to put those instructions. Scheduling is a speed optimization that can have a critical effect on [[instruction pipeline|pipeline]]d machines.
* [[Register allocation]]: the allocation of [[Variable (programming)|variables]] to [[processor register]]s<ref name=ASU>{{Cite book|title=Compilers: Principles, Techniques, and Tools|last=Aho|first=Alfred V. |author2=Ravi Sethi |author3=Jeffrey D. Ullman|year=1987|publisher=Addison-Wesley|isbn=0-201-10088-6|page=15}}<!--|access-date=June 15, 2012--></ref>
* [[Debugging data format|Debug data]] generation if required so the code can be [[Debugging|debugged]].

Instruction selection is typically carried out by doing a [[recursion|recursive]] [[postorder traversal]] on the abstract syntax tree, matching particular tree configurations against templates; for example, the tree <code>W := ADD(X,MUL(Y,Z))</code> might be transformed into a linear sequence of instructions by recursively generating the sequences for <code>t1 := X</code> and <code>t2 := MUL(Y,Z)</code>, and then emitting the instruction <code>ADD W, t1, t2</code>.

In a compiler that uses an intermediate language, there may be two instruction selection stages&mdash;one to convert the parse tree into intermediate code, and a second phase much later to convert the intermediate code into instructions from the [[instruction set]] of the target machine. This second phase does not require a tree traversal; it can be done linearly, and typically involves a simple replacement of intermediate-language operations with their corresponding [[opcode]]s. However, if the compiler is actually a [[Transcompiler|language translator]] (for example, one that converts [[Java (programming language)|Java]] to [[C++]]), then the second code-generation phase may involve ''building'' a tree from the linear intermediate code.