Summary of Chapter 8


Code generation is the final phase of a compiler. The code generator maps the intermediate representation produced by the front end, or if there is a code optimization phase by the code  optimizer, into the target program.

Instruction selection is the process of choosing target-language instructions for each IR statement.

Register allocation is the process of deciding which IR values to keep in registers. Graph coloring is an effective technique for doing register allocation in compilers.

Register assignment is the process of deciding which register should hold a given IR value.

retargetable compiler is one that can generate code for multiple instruction set.

virtual machine is an interpreter for bytecode intermediate language produced by languages such as Java and C#.

CISC machine is typically a two-address machine with relatively few registers, several register classes, and variable-length instructions with complex addressing modes.

RISC machine is typically a three-address machine with many registers in which operations are done in registers.

basic block is a maximal sequence of consecutive three-address statements in which flow of control can only enter at the first statement of the block and leave at the last statement without halting or branching except possibly at the last statement in the basic block.

flow graph is a graphical representation of a program in which the nodes of the graph are basic blocks and the edges of the graph show how control can flow among the blocks.

loop in a flow graph is strongly connected region with a single entry point called the loop header.

DAG representation of a basic block is directed acyclic graph in which the node of the DAG represent the statements within the block and each child of a node corresponds to the statement that is the last definition of an operand used in the statement.

Peephole optimizations are local code-improving transformations that can be applied to a program, usually through a sliding window.

Instruction selection can be done by a tree-rewriting process in which tree patterns corresponding to machine instructions are used to tile a syntax tree. We can associate costs with the tree-rewriting rules and apply dynamic programming to obtain an optimal tiling for useful classes of machines and expressions.

An Ershov number tells how many registers are needed to evaluate an expression without storing any temporaries

Spill code is an instruction sequence that stores a value in a register into memory in order to make room to hold another value in that register.