COMS W4115
Programming Languages and Translators
Lecture 21: Code Generation
April 14, 2008

Homework assignment #2 is due April 21, 2008.

Lecture Outline

1. Review
2. Issues in code generation
3. The target machine
4. Basic blocks and flow graphs

1. Review

• 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 source program.
• The target program should make efficient use of the target machine's resources.
• 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
1. The flow of control can only enter the basic block throught the first instruction in the block.
2. Control will leave the block without halting or branching except possibly at the last instruction in the block.
• A flow graph for the basic blocks of an intermediate program can be constructed as follows:
• 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.
• A set of nodes L in a flow graph is a loop if
1. There is a node in L called the loop entry with the property that no other node in L has a predecessor outside L.
2. Every node in L has a nonempty path completely within L to the entry of L.

5. Reading

• ALSU, Sections 8.1-8.5