harpoon.Analysis.Tree
Class TreeFolding

java.lang.Object
  harpoon.Analysis.BasicBlockInterfVisitor
      harpoon.Analysis.DataFlow.DataFlowBasicBlockVisitor
          harpoon.Analysis.DataFlow.ForwardDataFlowBasicBlockVisitor
              harpoon.Analysis.Tree.TreeFolding

public class TreeFolding
extends ForwardDataFlowBasicBlockVisitor

The TreeFolding class performs tree folding on a tree code in canonical form. Tree folding is used to remove superfluous temp definitions in the tree form. For example, in the tree expression:

    SEQ(
     MOVE(t1, 5)
     CJUMP(t1, L-true, L-false)
    )
 

the superfluous temp t1 would be removed, and its use would be replaced with the expression to which t1 was assigned:

     CJUMP(5, L-true, L-false)
 

The algorithm for tree folding is as follows:

   foreach TEMP t do
     if ((t has one DEF)             AND 
         (DEF(t) has one USE)        AND
         (RHS(DEF(t)) is available))
       remove DEF(t)
       replace t with RHS(DEF(t))
 

Issues:

At this time, memory writes kill all expressions. However, this is not really necessary. Furthermore, the algorithm is not especially efficient either in time or in space.

Version:

$Id: TreeFolding.java,v 1.7 2004/02/08 03:20:35 cananian Exp $

Author:

Duncan Bryce <duncan@lcs.mit.edu>

Constructor Summary

TreeFolding(Code code)
Constructs a new TreeFolding object for the code.

Method Summary

Code	fold() Performs the tree-folding optimization on this class's tree code.
boolean	merge(BasicBlockInterf from, BasicBlockInterf to) Merges operation on the from and to basic block.
void	visit(BasicBlock bb) Visit (Transfer) function.

Methods inherited from class harpoon.Analysis.DataFlow.ForwardDataFlowBasicBlockVisitor

addSuccessors

Methods inherited from class harpoon.Analysis.DataFlow.DataFlowBasicBlockVisitor

db, visit

Methods inherited from class harpoon.Analysis.BasicBlockInterfVisitor

visit

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TreeFolding

public TreeFolding(Code code)

Constructs a new TreeFolding object for the code.
requires:

1. code is a tree codeview in canonical form (code.isCanonical() should return true).
   modifies: nothing.
   effects: constructs a new BasicBlockVisitor and initializes its internal datasets for analysis of the BasicBlocks in code. However, the visit() and merge() methods should not be called directly. Rather, the folded tree code should be extracted by calling the calling the fold() method.

Method Detail

fold

public Code fold()

Performs the tree-folding optimization on this class's tree code.
Requires:
Modifies: this class's tree code
Effects: Performs the tree-folding optimization on this class's tree code, and returns the resulting tree code. Preserves the CFGraphable interface correctly by calling the code's recomputeEdges() method.

visit

public void visit(BasicBlock bb)

Visit (Transfer) function.

  OUT(bb)     = GEN(bb) union (IN(bb) intersect PRSV(bb))  

  OUT_mem(bb) = IN_mem(bb) union KILL_mem(bb)  

. Note: this method should never be called directly, and will cause an assertion failure if it is called from outside of the TreeFolding class.

Specified by:

visit in class DataFlowBasicBlockVisitor

merge

public boolean merge(BasicBlockInterf from,
                     BasicBlockInterf to)

Merges operation on the from and to basic block. Returns true if the to basic block changes.
NOTE: "changes" above refers to our knowledge about the basic block changing, not the contents of the basic block itself, which shouldn't be modified during Analysis. Thus, an appropriate "change" would be a variable being added to the IN-set of 'to' during Forward Dataflow Analysis

Specified by:

merge in class DataFlowBasicBlockVisitor