Compiler Design and Construction - Old Questions

5.  Explain the dynamic programming code generation algorithm with example.

The dynamic programming algorithm can be used to generate code for any machine with r interchangeable registers R₀,R₁, .. . , R_r-1 and load, store, and add instructions. For simplicity, we assume every instruction costs one unit, although the dynamic programming algorithm can easily be modified to work even if each instruction has its own cost.

The dynamic programming algorithm partitions the problem of generating optimal code for an expression into the subproblems of generating optimal code for the subexpressions of the given expression.

• Contiguous evaluation: Complete the evaluation of T1, T2, then evaluate root.
• Non-contiguous evaluation: First evaluate part of T1 leaving the value in a register, next evaluate T2, then return to evaluate the rest of T1.

Dynamic programming algorithm uses contiguous evaluation.

The dynamic programming algorithm proceeds in three phases (suppose the target machine has r registers):

1. Compute bottom-up for each node n of the expression tree T an array C of costs, in which the i^th component C[i] is the optimal cost of computing the subtree S rooted at n into a register, assuming i registers are available for the computation, for 1 <= i <= r.

2. Traverse T, using the cost vectors to determine which subtrees of T must be computed into memory.

3. Traverse each tree using the cost vectors and associated instructions to generate the final target code. The code for the subtrees computed into memory locations is generated first.

Example: 

Consider a machine having two registers R₀ and R_l, and the following instructions, each of unit cost:

In these instructions, R_i is either R_O or R_l, and M_i is a memory location. The operator op corresponds to an arithmetic operators.

Now, Computing cost vector at each node:

Final Output: