Algorithms for Compiler Design: USING ALGEBRAIC PROPERTIES TO REDUCE THE REGISTER REQUIREMENT

It is possible to make use of algebraic properties like operator commutativity and associativity to reduce the register requirements of the tree. For example, consider the tree shown in Figure 1.

Figure 1: Tree with a label of two.

The label of the tree in Figure 1 is two, but since + is a commutative operator, we can interchange the left and the right subtrees, as shown in Figure 2. This brings the register requirement of the tree down to one.

Figure 2: The left and right subtrees have been interchanged, reducing the register requirement to one.

Similarly, associativity can be used to reduce the register requirement. Consider the tree shown in Figure 3.

Figure 3: Associativity is used to reduce a tree's register requirement.