Package edu.umd.cs.findbugs.ba

Class AbstractDominatorsAnalysis

java.lang.Object

edu.umd.cs.findbugs.ba.BasicAbstractDataflowAnalysis<java.util.BitSet>

edu.umd.cs.findbugs.ba.AbstractDominatorsAnalysis

All Implemented Interfaces:

DataflowAnalysis<java.util.BitSet>

Direct Known Subclasses:

DominatorsAnalysis, PostDominatorsAnalysis

public abstract class AbstractDominatorsAnalysis
extends BasicAbstractDataflowAnalysis<java.util.BitSet>

A dataflow analysis to compute dominator relationships between basic blocks. Use the BasicAbstractDataflowAnalysis.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.

An EdgeChooser may be specified to select which edges to take into account. For example, exception edges could be ignored.

Author:

David Hovemeyer

See Also:

DataflowAnalysis, CFG, BasicBlock

Constructor Summary

Constructors

Constructor	Description
AbstractDominatorsAnalysis(CFG cfg, boolean ignoreExceptionEdges)	Constructor.
AbstractDominatorsAnalysis(CFG cfg, EdgeChooser edgeChooser)	Constructor.

Method Summary

Modifier and Type	Method	Description
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 a bitset containing the unique IDs of all blocks in CFG dominated (or postdominated, depending on how the analysis was done) by given block.
java.util.BitSet	getAllDominatorsOf(BasicBlock block)	Get a bitset containing the unique IDs of all blocks which dominate (or postdominate) the given block.
void	initEntryFact(java.util.BitSet result)	Initialize the "entry" fact for the graph.
boolean	isTop(java.util.BitSet fact)	Is the given fact the top value.
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 edu.umd.cs.findbugs.ba.BasicAbstractDataflowAnalysis

edgeTransfer, factToString, finishIteration, getFactAfterLocation, getFactAtLocation, getFactOnEdge, getLastUpdateTimestamp, getResultFact, getStartFact, resultFactIterator, setLastUpdateTimestamp, startIteration

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

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

AbstractDominatorsAnalysis

public AbstractDominatorsAnalysis(CFG cfg,
                                  EdgeChooser edgeChooser)

Constructor.

Parameters:

cfg - the CFG to compute dominator relationships for

edgeChooser - EdgeChooser to choose which Edges to consider significant

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.

copy

public void copy(java.util.BitSet source,
                 java.util.BitSet dest)

Description copied from interface: DataflowAnalysis

Copy dataflow facts.

initEntryFact

public void initEntryFact(java.util.BitSet result)

Description copied from interface: DataflowAnalysis

Initialize the "entry" fact for the graph.

isTop

public boolean isTop(java.util.BitSet fact)

Description copied from interface: DataflowAnalysis

Is the given fact the top value.

makeFactTop

public void makeFactTop(java.util.BitSet fact)

Description copied from interface: DataflowAnalysis

Make given fact the top value.

same

public boolean same(java.util.BitSet fact1,
                    java.util.BitSet fact2)

Description copied from interface: DataflowAnalysis

Are given dataflow facts the same?

transfer

public void transfer(BasicBlock basicBlock,
                     @CheckForNull
                     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.

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.

Parameters:

fact - the predecessor fact (incoming edge)

edge - the edge from the predecessor

result - the result fact

Throws:

DataflowAnalysisException

getAllDominatorsOf

public java.util.BitSet getAllDominatorsOf(BasicBlock block)

Get a bitset containing the unique IDs of all blocks which dominate (or postdominate) the given block.

Parameters:

block - a BasicBlock

Returns:

BitSet of the unique IDs of all blocks that dominate (or postdominate) the BasicBlock

getAllDominatedBy

public java.util.BitSet getAllDominatedBy(BasicBlock dominator)

Get a bitset containing the unique IDs of 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