Module 7: Code Generation

No. of lectures : 10

Topics Covered

1. Simple Code generation for expressions -- operand descriptors and the handling of partial results. Code generation algorithm for a simple machine architecture like Intel 8086.
2. Issues in efficient code generation -- instruction costs, register utilization and evaluation order. The Sethi-Ullman algorithm.
3. Optimal code generation for expression trees -- The machine model, instruction costs. Cover of an expression tree. The Aho-Johnson dynamic programming algorithm for optimal code generation.

Objectives

At the conclusion of the module, the student should be able to :

1. Understand the role of operand descriptors in the process of code generation,

2. Understand the techniques for handling partial results in unoptimized code,

3. Understand the importance of and the issues involved in generating optimal code for expressions.

4. Understand the assumptions behind Sethi-Ullman algorithm - the expressions considered, the machine model and the the cost measure of the code generated.

5. Understand Sethi-Ullman algorithm, especially the influence of register requirements on the optimal evaluation order for an expression.

6. Understand the proof of optimality and complexity of the algorithm.

7. Understand the assumptions behind Aho-Johnson algorithm.

8. Understand Aho-Johnson algorithm along with its optimality proof and complexity.