Algorithms for Compiler Design: ELIMINATING LOCAL COMMON SUBEXPRESSIONS

The first step in eliminating local common subexpressions is to detect the common subexpression in a basic block. The common subexpressions in a basic block can be automatically detected if we construct a directed acyclic graph (DAG).

DAG Construction

For constructing a basic block DAG, we make use of the function node(id), which returns the most recently created node associated with id. For every three-address statement x = y op z, x = op y, or x = y in the block we:

do
 {

1. If node(y) is undefined, create a leaf labeled y, and let node(y) be this node. If node(z) is undefined, create a leaf labeled z, and let that leaf be node(z). If the statement is of the form x = op y or x = y, then if node(y) is undefined, create a leaf labeled y, and let node(y) be this node.

2. If a node exists that is labeled op whose left child is node(y) and whose right child is node(z) (to catch the common subexpressions), then return this node. Otherwise, create such a node, and return it. If the statement is of the form x = op y, then check if a node exists that is labeled op whose only child is node(y). Return this node. Otherwise, create such a node and return. Let the returned node be n.

3. Append x to the list of identifiers for the node n returned in step 2. Delete x from the list of attached identifiers for node(x), and set node(x) to be node n.

    }

Therefore, we first go for a DAG representation of the basic block. And if the interior nodes in the DAG have more than one label, then those nodes of the DAG represent the common subexpressions in the basic block. After detecting these common subexpressions, we eliminate them from the basic block. The following example shows the elimination of local common subexpressions, and the DAG is shown in Figure 1.

1. S1 : = 4 * I

2. S2 : addr(A) − 4

3. S3 : S2 [S1]

4. S4 : 4 * I

5. S5 : = addr(B) − 4

6. S6 : = S5 [S4]

7. S7 : = S3 * S6

8. S8 : PROD + S7

9. PROD : = S8

10. S9 : = I + 1

11. I = S9

12. if I ≤ 20 goto (1).

Figure 1: DAG representation of a basic block.

In Figure 1, PROD 0 indicates the initial value of PROD, and I0 indicates the initial value of I. We see that the same value is assigned to S8 and PROD. Similarly, the value assigned to S9 is the same as I. And the value computed for S1 and S4 are the same; hence, we can eliminate these common subexpressions by selecting one of the attached identifiers (one that is needed outside the block). We assume that none of the temporaries is needed outside the block. The rewritten block will be:

1. S1 : = 4 * I

2. S2 : = addr(A) − 4

3. S3 : = S2 [S1]

4. S5 : = addr(B) − 4

5. S6 : = S5 [S1]

6. S7 : = S3 * S6

7. PROD : = PROD + S7

8. I : = I + 1

9. if I ≤ 20 goto (1)