Programming Languages and Translators
Lecture 21: Code Generation
April 14, 2008
- Issues in code generation
- The target machine
- Basic blocks and flow graphs
- Storage-allocation strategies
- Activation trees and records
- Parameter passing mechanisms
- Calling sequences
2. Issues in Code Generation
- Position of the code generator
- Desired properties of a code generator
- The target program must preserve the semantic meaning of the
- The target program should make efficient use of the target
- The code generator itself should be efficient.
- Challenges in code generation
- The problem of optimal code generation is undecidable.
- Many subproblems in code generation, such as optimal register
allocation, are computationally intractable.
- The design of a good code generator reverts to the problem of
designing good heuristics.
- Primary tasks of a code generator
- Instruction selection
- Register allocation
- Evaluation order
3. The Target Machine
- Reduced instruction set machines (RISC)
- many registers
- three-address instructions
- simple addressing modes
- simple instruction set architecture
- Complex instruction set machines (CISC)
- few registers
- two-address instructions
- variety of addressing modes
- several register classes
- variable-length instructions
- instructions with side effects
- Stack-based machines
- push operands onto stack
- perform operations on operands at top of stack
- stack kept in registers
- model for Java Virtual Machine
4. Basic blocks and Flow Graphs
- A basic block is a maximal sequence of consecutive three-address
instructions such that
A flow graph for the basic blocks of an intermediate program
can be constructed as follows:
- The flow of control can only enter the basic block throught the
first instruction in the block.
- Control will leave the block without halting or branching
except possibly at the last instruction in the block.
A set of nodes L in a flow graph is a loop if
- The basic blocks are the nodes of the flow graph.
- There is an edge from block B to block C iff it is possible
for the first instruction in C to immediately follow the last
instruction in B.
- There is a node in L called the loop entry with the property
that no other node in L has a predecessor outside L.
- Every node in L has a nonempty path completely within L to
the entry of L.