Dynamic Programming Code Generation Algorithm

An algorithm based on the principle of dynamic programming can be used to extend the class of machines, for which optimal code can be generated from expression trees in linear time. The algorithm applies to a broad class of register machines with complex instruction sets.

Class of Register Machines:

The dynamic programming algorithm can be applied to generate code for any machine with r interchangeable registers Ro, R1 ……….. Rr-1, and instructions of the form Ri:= E, where E is any expression containing operators, registers, and memory locations. If E involves one or more registers, then Ri must be one of those registers.

Principle of Dynamic Programming:

• The dynamic programming algorithm partitions the problem of generating optimal code for an expression into sub-problems of generating optimal code for the sub-expressions of the given expression.

• For example, consider that the expression E is of the form E1 + E2. An optimal program for E is formed by combining the optimal programs for E1, and E2 followed by the code to evaluate the operator +.

• An optimal program produced by the dynamic programming algorithm has the property that it evaluates an expression E = E1 op E2 “contiguously”.

Contiguous Evaluation:

• We say that program P evaluates a tree T contiguously if it first evaluates those subtrees of T that need to be computed into memory. Then it evaluates the remainder of T either in the order T1, T2, and then the root, or in the order T2, T1, and then the root. In either case, it uses the previously computed values from the memory, whenever necessary.

For the register machine class, it can be proved that given any machine language program P to evaluate an expression tree T, we can find an equivalent program P’ such that:

1. P’ is no higher cost than P

2. P’ uses no more registers than P, and

3. P’ evaluates the tree in a contiguous fashion.

This result implies that every expression tree can be evaluated optimally by a contiguous program.

Dynamic Programming Algorithm: The algorithm proceeds in three phases.

1. First Phase:

Compute an array C of costs, bottom-up, for each node n of the expression tree T. The in component C[i] of array C is the optimal cost of computing the subtree S, which is rooted at n into a register. Here it is assumed that I registers are available for computation for 1si Sr. The cost includes the following components.

(i) All loads and stores necessary to evaluate S in the given number of registers.

(ii) The cost of computing the operator at the root of S.

2. Second Phase:

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

3. Third Phase:

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