10.6 ELIMINATING GLOBAL COMMON SUBEXPRESSIONS


10.5 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 10.13.

  1. S 1 : = 4 * I

  2. S 2 : addr( A ) ˆ’ 4

  3. S 3 : S 2 [ S 1]

  4. S 4 : 4 * I

  5. S 5 : = addr( B ) ˆ’ 4

  6. S 6 : = S 5 [ S 4]

  7. S 7 : = S 3 * S 6

  8. S 8 : PROD + S 7

  9. PROD : = S 8

  10. S 9 : = I + 1

  11. I = S 9

  12. if I 20 goto (1).

click to expand
Figure 10.13: DAG representation of a basic block.

In Figure 10.13, PROD 0 indicates the initial value of PROD, and I 0 indicates the initial value of I . We see that the same value is assigned to S 8 and PROD. Similarly, the value assigned to S 9 is the same as I . And the value computed for S 1 and S 4 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. S 1 : = 4 * I

  2. S 2 : = addr( A ) ˆ’ 4

  3. S 3 : = S 2 [ S 1]

  4. S 5 : = addr( B ) ˆ’ 4

  5. S 6 : = S 5 [ S 1]

  6. S 7 : = S 3 * S 6

  7. PROD : = PROD + S 7

  8. I : = I + 1

  9. if I 20 goto (1)




Algorithms for Compiler Design
Algorithms for Compiler Design (Electrical and Computer Engineering Series)
ISBN: 1584501006
EAN: 2147483647
Year: 2005
Pages: 108
Authors: O G Kakde

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net