edu.umd.cs.findbugs.ba
Class ValueNumberAnalysis

java.lang.Object
  extended by edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis<Fact>
      extended by edu.umd.cs.findbugs.ba.ForwardDataflowAnalysis<FrameType>
          extended by edu.umd.cs.findbugs.ba.FrameDataflowAnalysis<ValueNumber,ValueNumberFrame>
              extended by edu.umd.cs.findbugs.ba.ValueNumberAnalysis
All Implemented Interfaces:
DataflowAnalysis<ValueNumberFrame>

public class ValueNumberAnalysis
extends FrameDataflowAnalysis<ValueNumber,ValueNumberFrame>

A dataflow analysis to track the production and flow of values in the Java stack frame. See the ValueNumber class for an explanation of what the value numbers mean, and when they can be compared.

This class is still experimental.

Author:
David Hovemeyer
See Also:
ValueNumber, DominatorsAnalysis

Nested Class Summary
private static class ValueNumberAnalysis.ValueCompacter
           
 
Field Summary
private  ValueNumberCache cache
           
private static boolean DEBUG
           
private  ValueNumber[] entryLocalValueList
           
private  java.util.IdentityHashMap<BasicBlock,ValueNumber> exceptionHandlerValueNumberMap
           
private  java.util.HashMap<Location,ValueNumberFrame> factAfterLocationMap
           
private  java.util.HashMap<Location,ValueNumberFrame> factAtLocationMap
           
private  ValueNumberFactory factory
           
private  org.apache.bcel.generic.MethodGen methodGen
           
private  ValueNumber thisValue
           
private  ValueNumberFrameModelingVisitor visitor
           
 
Constructor Summary
ValueNumberAnalysis(org.apache.bcel.generic.MethodGen methodGen, DepthFirstSearch dfs, LoadedFieldSet loadedFieldSet, RepositoryLookupFailureCallback lookupFailureCallback)
           
 
Method Summary
 void compactValueNumbers(Dataflow<ValueNumberFrame,ValueNumberAnalysis> dataflow)
          Compact the value numbers assigned.
 ValueNumberFrame createFact()
          Create empty (uninitialized) dataflow facts for one program point.
 java.util.Iterator<ValueNumberFrame> factIterator()
          Get an Iterator over all dataflow facts that we've recorded for the Locations in the CFG.
 ValueNumber getEntryValue(int local)
           
private  ValueNumber getExceptionValueNumber(BasicBlock handlerBlock)
           
 ValueNumberFrame getFactAfterLocation(Location location)
          Get the dataflow fact representing the point just after given Location.
 ValueNumberFrame getFactAtLocation(Location location)
          Get the dataflow fact representing the point just before given Location.
 ValueNumberFactory getFactory()
           
 int getNumValuesAllocated()
           
 ValueNumber getThisValue()
           
 void initEntryFact(ValueNumberFrame result)
          Initialize the "entry" fact for the graph.
 boolean isThisValue(ValueNumber value)
           
static void main(java.lang.String[] argv)
          Test driver.
private static void markFrameValues(ValueNumberFrame frame, ValueNumberAnalysis.ValueCompacter compacter)
          Mark value numbers in a value number frame for compaction.
 void meetInto(ValueNumberFrame fact, Edge edge, ValueNumberFrame result)
          Meet a dataflow fact associated with an incoming edge into another fact.
protected  void mergeInto(ValueNumberFrame frame, ValueNumberFrame result)
          Merge one frame into another.
protected  ValueNumber mergeValues(ValueNumberFrame frame, int slot, ValueNumber mine, ValueNumber other)
          Merge two values in a particular slot of a Frame.
 void transferInstruction(org.apache.bcel.generic.InstructionHandle handle, BasicBlock basicBlock, ValueNumberFrame fact)
          Transfer function for a single instruction.
 
Methods inherited from class edu.umd.cs.findbugs.ba.FrameDataflowAnalysis
copy, initResultFact, isFactValid, makeFactTop, modifyFrame, same
 
Methods inherited from class edu.umd.cs.findbugs.ba.ForwardDataflowAnalysis
getBlockOrder, getDepthFirstSearch, isForwards
 
Methods inherited from class edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis
endTransfer, factToString, getResultFact, getStartFact, resultFactIterator, startTransfer, transfer
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEBUG

private static final boolean DEBUG

methodGen

private org.apache.bcel.generic.MethodGen methodGen

factory

private ValueNumberFactory factory

cache

private ValueNumberCache cache

visitor

private ValueNumberFrameModelingVisitor visitor

entryLocalValueList

private ValueNumber[] entryLocalValueList

exceptionHandlerValueNumberMap

private java.util.IdentityHashMap<BasicBlock,ValueNumber> exceptionHandlerValueNumberMap

thisValue

private ValueNumber thisValue

factAtLocationMap

private java.util.HashMap<Location,ValueNumberFrame> factAtLocationMap

factAfterLocationMap

private java.util.HashMap<Location,ValueNumberFrame> factAfterLocationMap
Constructor Detail

ValueNumberAnalysis

public ValueNumberAnalysis(org.apache.bcel.generic.MethodGen methodGen,
                           DepthFirstSearch dfs,
                           LoadedFieldSet loadedFieldSet,
                           RepositoryLookupFailureCallback lookupFailureCallback)
Method Detail

getFactory

public ValueNumberFactory getFactory()

getNumValuesAllocated

public int getNumValuesAllocated()

isThisValue

public boolean isThisValue(ValueNumber value)

getThisValue

public ValueNumber getThisValue()

getEntryValue

public ValueNumber getEntryValue(int local)

createFact

public ValueNumberFrame 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.


initEntryFact

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


transferInstruction

public void transferInstruction(org.apache.bcel.generic.InstructionHandle handle,
                                BasicBlock basicBlock,
                                ValueNumberFrame fact)
                         throws DataflowAnalysisException
Description copied from class: AbstractDataflowAnalysis
Transfer function for a single instruction.

Specified by:
transferInstruction in class AbstractDataflowAnalysis<ValueNumberFrame>
Parameters:
handle - the instruction
basicBlock - the BasicBlock containing the instruction; needed to disambiguate instructions in inlined JSR subroutines
fact - which should be modified based on the instruction
Throws:
DataflowAnalysisException

meetInto

public void meetInto(ValueNumberFrame fact,
                     Edge edge,
                     ValueNumberFrame 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

mergeInto

protected void mergeInto(ValueNumberFrame frame,
                         ValueNumberFrame result)
                  throws DataflowAnalysisException
Description copied from class: FrameDataflowAnalysis
Merge one frame into another.

Overrides:
mergeInto in class FrameDataflowAnalysis<ValueNumber,ValueNumberFrame>
Parameters:
frame - the frame to merge with the result
result - the result frame, which is modified to be the merge of the two frames
Throws:
DataflowAnalysisException

mergeValues

protected ValueNumber mergeValues(ValueNumberFrame frame,
                                  int slot,
                                  ValueNumber mine,
                                  ValueNumber other)
                           throws DataflowAnalysisException
Description copied from class: FrameDataflowAnalysis
Merge two values in a particular slot of a Frame.

Specified by:
mergeValues in class FrameDataflowAnalysis<ValueNumber,ValueNumberFrame>
Parameters:
frame - the Frame
slot - the slot of the Frame
mine - a value
other - another value
Returns:
the merged value
Throws:
DataflowAnalysisException

getFactAtLocation

public ValueNumberFrame getFactAtLocation(Location location)
Description copied from class: AbstractDataflowAnalysis
Get the dataflow fact representing the point just before given Location. Note "before" is meant in the logical sense, so for backward analyses, before means after the location in the control flow sense.

Overrides:
getFactAtLocation in class AbstractDataflowAnalysis<ValueNumberFrame>
Parameters:
location - the location
Returns:
the fact at the point just before the location

getFactAfterLocation

public ValueNumberFrame getFactAfterLocation(Location location)
Description copied from class: AbstractDataflowAnalysis
Get the dataflow fact representing the point just after given Location. Note "after" is meant in the logical sense, so for backward analyses, after means before the location in the control flow sense.

Overrides:
getFactAfterLocation in class AbstractDataflowAnalysis<ValueNumberFrame>

factIterator

public java.util.Iterator<ValueNumberFrame> factIterator()
Get an Iterator over all dataflow facts that we've recorded for the Locations in the CFG. Note that this does not include result facts (since there are no Locations corresponding to the end of basic blocks).


compactValueNumbers

public void compactValueNumbers(Dataflow<ValueNumberFrame,ValueNumberAnalysis> dataflow)
Compact the value numbers assigned. This should be done only after the dataflow algorithm has executed. This works by modifying the actual ValueNumber objects assigned. After this method is called, the getNumValuesAllocated() method of this object will return a value less than or equal to the value it would have returned before the call to this method.

This method should be called at most once.

Parameters:
dataflow - the Dataflow object which executed this analysis (and has all of the block result values)

markFrameValues

private static void markFrameValues(ValueNumberFrame frame,
                                    ValueNumberAnalysis.ValueCompacter compacter)
Mark value numbers in a value number frame for compaction.


main

public static void main(java.lang.String[] argv)
Test driver.


getExceptionValueNumber

private ValueNumber getExceptionValueNumber(BasicBlock handlerBlock)