Dynamic Programming Code-Generation
Introduction: This procedure works for machines in which all computation is done in registers and in which instructions consist of an operator applied to two registers or to a register and a memory location.
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 dynamic programming algorithm applies to a broad class of register machines with complex instruction sets. The dynamic programming algorithm can be used to generate code for any machine with r interchangeable registers R0,R1,... , Rr—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.
Contiguous Evaluation: The dynamic programming algorithm partitions the problem of generating optimalcode for an expression into the sub problems of generating optimal codefor the subexpressions of the given expression. As a simple example, consideran expression E of the form E\ E2. An optimal program for E is formed bycombining optimal programs for E\ and E2, in one or the other order, followedby code to evaluate the operator . The sub problems of generating optimalcode for E\ and E2 are solved similarly.
An optimal program produced by the dynamic programming algorithm has an important property. It evaluates an expression E = E\ op E2 "contiguously." We can appreciate what this means by looking at the syntax tree T for E.
Here Ti and T2 are trees for E\ and E2, respectively.
We say a 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 Ti, T2, and then the root, or in the order T2, Ti, and then the root, in either case using the previously computed values from memory whenever necessary. As an example of noncontiguous evaluation, P might first evaluate part of Ti leaving the value in a register (instead of memory), next evaluate T2, and then return to evaluate the rest of Ti.
For the register machine in this section, we can prove 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 of no higher cost than P,
2. P' uses no more registers than P, and
3. P' evaluates the tree contiguously.
This result implies that every expression tree can be evaluated optimally by a contiguous program.
By way of contrast, machines with even-odd register pairs do not always have optimal contiguous evaluations; the x86 architecture uses register pairs for multiplication and division. For such machines, we can give examples of expression trees in which an optimal machine language program must first evaluate into a register a portion of the left subtree of the root, then a portion of the right subtree, then another part of the left subtree, then another part of the right, and so on. This type of oscillation is unnecessary for an optimal evaluation of any expression tree using the machine in this section.
The contiguous evaluation property defined above ensures that for any expression tree T there always exists an optimal program that consists of optimal programs for subtrees of the root, followed by an instruction to evaluate the root. This property allows us to use a dynamic programming algorithm to generate an optimal program for T.