edu.umd.cs.findbugs.ba
Class AbstractDominatorsAnalysis

java.lang.Object
  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