edu.umd.cs.findbugs.ba
Class AbstractDominatorsAnalysis

java.lang.Object
  extended by edu.umd.cs.findbugs.ba.AbstractDominatorsAnalysis
All Implemented Interfaces:
DataflowAnalysis<java.util.BitSet>
Direct Known Subclasses:
DominatorsAnalysis, PostDominatorsAnalysis

public abstract class AbstractDominatorsAnalysis
extends java.lang.Object
implements DataflowAnalysis<java.util.BitSet>

A dataflow analysis to compute dominator relationships between basic blocks. Use the getResultFact(edu.umd.cs.findbugs.ba.BasicBlock) method to get the dominator set for a given basic block. The dominator sets are represented using the BitSet class, with the individual bits corresponding to the IDs of basic blocks.

Subclasses extend this class to compute either dominators or postdominators.

Exception edges may be ignored, in which case the domination results only take non-exception control flow into account.

Author:
David Hovemeyer
See Also:
DataflowAnalysis, CFG, BasicBlock

Field Summary
private  CFG cfg
           
private  boolean ignoreExceptionEdges
           
private  java.util.IdentityHashMap<BasicBlock,java.util.BitSet> resultFactMap
           
private  java.util.IdentityHashMap<BasicBlock,java.util.BitSet> startFactMap
           
 
Constructor Summary
AbstractDominatorsAnalysis(CFG cfg, boolean ignoreExceptionEdges)
          Constructor.
 
Method Summary
 void copy(java.util.BitSet source, java.util.BitSet dest)
          Copy dataflow facts.
 java.util.BitSet createFact()
          Create empty (uninitialized) dataflow facts for one program point.
 java.util.BitSet getAllDominatedBy(BasicBlock dominator)
          Get all blocks in CFG dominated (or postdominated, depending on how the analysis was done) by given block.
 java.util.BitSet getResultFact(BasicBlock block)
          Get the result fact for given basic block.
 java.util.BitSet getStartFact(BasicBlock block)
          Get the start fact for given basic block.
 void initEntryFact(java.util.BitSet result)
          Initialize the "entry" fact for the graph.
 void initResultFact(java.util.BitSet result)
          Initialize result fact for block.
 boolean isTop(java.util.BitSet fact)
           
private  java.util.BitSet lookupOrCreateFact(java.util.Map<BasicBlock,java.util.BitSet> map, BasicBlock block)
           
 void makeFactTop(java.util.BitSet fact)
          Make given fact the top value.
 void meetInto(java.util.BitSet fact, Edge edge, java.util.BitSet result)
          Meet a dataflow fact associated with an incoming edge into another fact.
 boolean same(java.util.BitSet fact1, java.util.BitSet fact2)
          Are given dataflow facts the same?
 void transfer(BasicBlock basicBlock, org.apache.bcel.generic.InstructionHandle end, java.util.BitSet start, java.util.BitSet result)
          Transfer function for the analysis.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface edu.umd.cs.findbugs.ba.DataflowAnalysis
getBlockOrder, isForwards
 

Field Detail

cfg

private final CFG cfg

ignoreExceptionEdges

private final boolean ignoreExceptionEdges

startFactMap

private final java.util.IdentityHashMap<BasicBlock,java.util.BitSet> startFactMap

resultFactMap

private final java.util.IdentityHashMap<BasicBlock,java.util.BitSet> resultFactMap
Constructor Detail

AbstractDominatorsAnalysis

public AbstractDominatorsAnalysis(CFG cfg,
                                  boolean ignoreExceptionEdges)
Constructor.

Parameters:
cfg - the CFG to compute dominator relationships for
ignoreExceptionEdges - true if exception edges should be ignored
Method Detail

createFact

public java.util.BitSet createFact()
Description copied from interface: DataflowAnalysis
Create empty (uninitialized) dataflow facts for one program point. A valid value will be copied into it before it is used.

Specified by:
createFact in interface DataflowAnalysis<java.util.BitSet>

getStartFact

public java.util.BitSet getStartFact(BasicBlock block)
Description copied from interface: DataflowAnalysis
Get the start fact for given basic block.

Specified by:
getStartFact in interface DataflowAnalysis<java.util.BitSet>
Parameters:
block - the basic block

getResultFact

public java.util.BitSet getResultFact(BasicBlock block)
Description copied from interface: DataflowAnalysis
Get the result fact for given basic block.

Specified by:
getResultFact in interface DataflowAnalysis<java.util.BitSet>
Parameters:
block - the basic block

lookupOrCreateFact

private java.util.BitSet lookupOrCreateFact(java.util.Map<BasicBlock,java.util.BitSet> map,
                                            BasicBlock block)

copy

public void copy(java.util.BitSet source,
                 java.util.BitSet dest)
Description copied from interface: DataflowAnalysis
Copy dataflow facts.

Specified by:
copy in interface DataflowAnalysis<java.util.BitSet>

initEntryFact

public void initEntryFact(java.util.BitSet result)
Description copied from interface: DataflowAnalysis
Initialize the "entry" fact for the graph.

Specified by:
initEntryFact in interface DataflowAnalysis<java.util.BitSet>

initResultFact

public void initResultFact(java.util.BitSet result)
Description copied from interface: DataflowAnalysis
Initialize result fact for block. The start facts for a block are initialized as the meet of the "logical" predecessor's result facts. Note that a "logical predecessor" is actually a CFG successor if the analysis is backwards.

Specified by:
initResultFact in interface DataflowAnalysis<java.util.BitSet>

isTop

public boolean isTop(java.util.BitSet fact)

makeFactTop

public void makeFactTop(java.util.BitSet fact)
Description copied from interface: DataflowAnalysis
Make given fact the top value.

Specified by:
makeFactTop in interface DataflowAnalysis<java.util.BitSet>

same

public boolean same(java.util.BitSet fact1,
                    java.util.BitSet fact2)
Description copied from interface: DataflowAnalysis
Are given dataflow facts the same?

Specified by:
same in interface DataflowAnalysis<java.util.BitSet>

transfer

public void transfer(BasicBlock basicBlock,
                     org.apache.bcel.generic.InstructionHandle end,
                     java.util.BitSet start,
                     java.util.BitSet result)
              throws DataflowAnalysisException
Description copied from interface: DataflowAnalysis
Transfer function for the analysis. Taking dataflow facts at start (which might be either the entry or exit of the block, depending on whether the analysis is forwards or backwards), modify result to be the facts at the other end of the block.

Specified by:
transfer in interface DataflowAnalysis<java.util.BitSet>
Parameters:
basicBlock - the basic block
end - if nonnull, stop before considering this instruction; otherwise, consider all of the instructions in the basic block
start - dataflow facts at beginning of block (if forward analysis) or end of block (if backwards analysis)
result - resulting dataflow facts at other end of block
Throws:
DataflowAnalysisException

meetInto

public void meetInto(java.util.BitSet fact,
                     Edge edge,
                     java.util.BitSet result)
              throws DataflowAnalysisException
Description copied from interface: DataflowAnalysis
Meet a dataflow fact associated with an incoming edge into another fact. This is used to determine the start fact for a basic block.

Specified by:
meetInto in interface DataflowAnalysis<java.util.BitSet>
Parameters:
fact - the predecessor fact (incoming edge)
edge - the edge from the predecessor
result - the result fact
Throws:
DataflowAnalysisException

getAllDominatedBy

public java.util.BitSet getAllDominatedBy(BasicBlock dominator)
Get all blocks in CFG dominated (or postdominated, depending on how the analysis was done) by given block.

Parameters:
dominator - we want to get all blocks dominated (or postdominated) by this block
Returns:
BitSet of the ids of all blocks dominated by the given block