harpoon.Analysis.DataFlow
Class ReachingHCodeElements

java.lang.Object
  harpoon.Analysis.BasicBlockInterfVisitor
      harpoon.Analysis.DataFlow.DataFlowBasicBlockVisitor
          harpoon.Analysis.DataFlow.ForwardDataFlowBasicBlockVisitor
              harpoon.Analysis.DataFlow.ReachingHCodeElements

public class ReachingHCodeElements
extends ForwardDataFlowBasicBlockVisitor

ReachingHCodeElements is an extension of ReachingDefs for performing reaching definitions analysis on HCodeElementss.

Version:

$Id: ReachingHCodeElements.java,v 1.5 2004/02/08 03:19:21 cananian Exp $

Author:

Felix S. Klock II <pnkfelix@mit.edu>, Duncan Bryce <duncan@lcs.mit.edu>

Nested Class Summary

protected static class

ReachingDefs.BBVisitor.ReachingDefInfo

Constructor Summary

ReachingHCodeElements(BasicBlock.Factory bbfactory)
Constructs a new ReachingHCodeElements for the basic blocks in the supplied BasicBlock.Factory.

ReachingHCodeElements(BasicBlock.Factory bbfactory, SetFactory setFact)
Constructs a new ReachingHCodeElements for the basic blocks in the supplied BasicBlock.Factory.

Method Summary

String	dump()
protected Set	findUniverse(Iterator blocks) Constructs a Set of all of the HCodeElements in blocks which have non-empty def sets.
Set	getReachingAfter(HCodeElement hce) Returns the Set of HCodeElementss which represent a definition that reaches the point directly after hce.
Set	getReachingBefore(HCodeElement hce) Returns the Set of HCodeElementss which represent a definition that reaches the point directly before hce.
Set	getReachingOnEntry(BasicBlock b) Returns the Set of definitions that reach the exit of b.
Set	getReachingOnExit(BasicBlock b) Returns the Set of definitions that reach the exit of b.
protected void	initializeBBtoRDI(Iterator blocks, SetFactory setFact) Initializes an internal mapping of BasicBlocks to ReachingDefInfos.
protected void	initializeGenPrsv(Iterator blocks, SetFactory sf) Initializes a mapping of temps to the Set of HCodeElements which do not define them.
protected ReachingDefs.BBVisitor.ReachingDefInfo	makeGenPrsv(BasicBlock bb, SetFactory sf) Initializes the GEN/PRSV information for 'bb' and stores in in the returned ReachingDefInfo.
boolean	merge(BasicBlockInterf from, BasicBlockInterf to) Merge (Confluence) operator.
void	visit(BasicBlock b) 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

ReachingHCodeElements

public ReachingHCodeElements(BasicBlock.Factory bbfactory)

Constructs a new ReachingHCodeElements for the basic blocks in the supplied BasicBlock.Factory.
requires:

1. bbfactory is a valid BasicBlock.Factory.
2. All of the instructions in basicBlocks implement UseDefable,

effects: constructs a new BasicBlockVisitor and initializes internal datasets for analysis of the BasicBlocks in bbfactory.

Parameters:

bbfactory - BasicBlock.Factory of BasicBlocks to be analyzed.

ReachingHCodeElements

public ReachingHCodeElements(BasicBlock.Factory bbfactory,
                             SetFactory setFact)

Constructs a new ReachingHCodeElements for the basic blocks in the supplied BasicBlock.Factory. Allows the user to specify their own SetFactory for constructing sets of HCodeElements in the analysis.
requires:

1. bbfactory is a valid BasicBlock.Factory.
2. All of the instructions in basicBlocks implement UseDefable,
3. All of the HCodeElements in basicBlocks which have non-empty def sets are members of the universe of setFact.

effects: constructs a new BasicBlockVisitor and initializes internal datasets for analysis of the BasicBlocks in bbfactory.

Parameters:

bbfactory - BasicBlock.Factory of BasicBlocks to be analyzed.

setFact - the SetFactory to be used in the construction of sets of HCodeElements.

Method Detail

findUniverse

protected Set findUniverse(Iterator blocks)

Constructs a Set of all of the HCodeElements in blocks which have non-empty def sets.
requires:

1. blocks is an Iterator of BasicBlocks.
2. All of the instructions in each element of blocks implement UseDefable.

modifies: blocks
effects: Iterates through all of the instructions contained in each element of blocks, adding each instruction which has a non-empty def set to a universe of values, returning the universe after all of the instructions have been visited. Internally maintains a reference to this computed dataset.

initializeGenPrsv

protected void initializeGenPrsv(Iterator blocks,
                                 SetFactory sf)

Initializes a mapping of temps to the Set of HCodeElements which do not define them.
Requires:

1. blocks is an Iterator of BasicBlocks.
2. All of the instructions in each element of blocks implement UseDefable.
3. All of the HCodeElements in basicBlocks which have non-empty def sets are members of the universe of setFact.

makeGenPrsv

protected ReachingDefs.BBVisitor.ReachingDefInfo makeGenPrsv(BasicBlock bb,
                                                             SetFactory sf)

Initializes the GEN/PRSV information for 'bb' and stores in in the returned ReachingDefInfo.
Requires: initializeGenPrsv has already been called on this ReachingHCodeElements object, and bb was one of the blocks in the Iterator parameter to the last such invocation.

getReachingBefore

public Set getReachingBefore(HCodeElement hce)

Returns the Set of HCodeElementss which represent a definition that reaches the point directly before hce. If hce represents more than one definition, all definitions which it represents must reach this point. Because of this, the ReachingHCodeElements class is most useful for intermediate representations in which each HCodeElement can represent only 1 definition.
requires: A DataFlow Equation Solver has been run to completion on the graph of BasicBlocks containing some block that contains hce, with this as the DataFlowBasicBlockVisitor.
effects: Returns a Set of Temps that are live on entry to hce.

getReachingAfter

public Set getReachingAfter(HCodeElement hce)

Returns the Set of HCodeElementss which represent a definition that reaches the point directly after hce. If hce represents more than one definition, all definitions which it represents must reach this point. Because of this, the ReachingHCodeElements class is most useful for intermediate representations in which each HCodeElement can represent only 1 definition.
requires: A DataFlow Equation Solver has been run to completion on the graph of BasicBlocks containing some block that contains hce, with this as the DataFlowBasicBlockVisitor.
effects: Returns a Set of Temps that are live on entry to hce.

initializeBBtoRDI

protected void initializeBBtoRDI(Iterator blocks,
                                 SetFactory setFact)

Initializes an internal mapping of BasicBlocks to ReachingDefInfos.

merge

public boolean merge(BasicBlockInterf from,
                     BasicBlockInterf to)

Merge (Confluence) operator.
RDin(bb) = Union over (j elem Pred(bb)) of ( RDout(j) ) from corresponds to a member of Pred('bb'). It is the responsibility of the DataFlow Equation Solver to run merge on all of the Pred('bb')
This method isn't meant to be called by application code; instead, look at one of the DataFlow Equation Solvers in the harpoon.Analysis.DataFlow package.
requires: child and parent are contained in this
effects: Updates the internal information associated with to to include information associated with from.

Specified by:

merge in class DataFlowBasicBlockVisitor

visit

public void visit(BasicBlock b)

Visit (Transfer) function.
RDout(bb) = ( RDin(bb) intersection PRSV(bb) ) union GEN(bb)

Specified by:

visit in class DataFlowBasicBlockVisitor

getReachingOnEntry

public Set getReachingOnEntry(BasicBlock b)

Returns the Set of definitions that reach the exit of b.
requires: A DataFlow Equation Solver has been run to completion on the graph of BasicBlocks containing b with this as the DataFlowBasicBlockVisitor.

getReachingOnExit

public Set getReachingOnExit(BasicBlock b)

Returns the Set of definitions that reach the exit of b.
requires: A DataFlow Equation Solver has been run to completion on the graph of BasicBlocks containing b with this as the DataFlowBasicBlockVisitor.

dump

public String dump()