Dynamic Programming Algorithm for Register Machines

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 ( R_0, R1, \ldots, R{r-1} ), and instructions of the form ( R_i := E ), where ( E ) is any expression containing operators, registers, and memory locations. If ( E ) involves one or more registers, then ( R_i ) 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 ( E_1 + E_2 ). An optimal program for ( E ) is formed by combining the optimal programs for ( E_1 ) and ( E_2 ), 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 = E_1 \text{ op } E_2 ) “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 ( T_1, T_2 ), and then the root, or in the order ( T_2, T_1 ), 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:

First Phase

Compute an array ( C ) of costs, bottom-up, for each node ( n ) of the expression tree ( T ). The ( i )-th component ( C[i] ) of an 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 ( 1 \leq i \leq r ). The cost includes the following components:

• All loads and stores necessary to evaluate ( S ) in the given number of registers.
• The cost of computing the operator at the root of ( S ).

Second Phase

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

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.