org.checkerframework.dataflow.analysis

Class BackwardAnalysisImpl<V extends AbstractValue<V>,S extends Store<S>,T extends BackwardTransferFunction<V,S>>

java.lang.Object

org.checkerframework.dataflow.analysis.AbstractAnalysis<V,S,T>

org.checkerframework.dataflow.analysis.BackwardAnalysisImpl<V,S,T>

Type Parameters:

V - the abstract value type to be tracked by the analysis

S - the store type used in the analysis

T - the transfer function type that is used to approximate runtime behavior

All Implemented Interfaces:

Analysis<V,S,T>, BackwardAnalysis<V,S,T>

public class BackwardAnalysisImpl<V extends AbstractValue<V>,S extends Store<S>,T extends BackwardTransferFunction<V,S>>
extends AbstractAnalysis<V,S,T>
implements BackwardAnalysis<V,S,T>

An implementation of a backward analysis to solve a org.checkerframework.dataflow problem given a control flow graph and a backward transfer function.

Nested Class Summary

Nested classes/interfaces inherited from class org.checkerframework.dataflow.analysis.AbstractAnalysis

AbstractAnalysis.Worklist

Nested classes/interfaces inherited from interface org.checkerframework.dataflow.analysis.Analysis

Analysis.Direction

Field Summary

Fields

Modifier and Type	Field and Description
protected IdentityHashMap<ExceptionBlock,S>	exceptionStores Exception store of an exception block, propagated by exceptional successors of its exception block, and merged with the normal TransferResult.
protected IdentityHashMap<Block,S>	outStores Out stores after every basic block (assumed to be 'no information' if not present).
protected S	storeAtEntry The store right before the entry block.

Fields inherited from class org.checkerframework.dataflow.analysis.AbstractAnalysis

cfg, currentInput, currentNode, currentTree, direction, finalLocalValues, inputs, isRunning, nodeValues, transferFunction, worklist

Constructor Summary

Constructors

Constructor and Description
BackwardAnalysisImpl() Construct an object that can perform a org.checkerframework.dataflow backward analysis over a control flow graph.
BackwardAnalysisImpl(T transfer) Construct an object that can perform a org.checkerframework.dataflow backward analysis over a control flow graph given a transfer function.

Method Summary

Modifier and Type	Method and Description
protected void	addStoreAfter(Block pred, @Nullable Node node, S s, boolean addBlockToWorklist) Add a store after the basic block pred by merging with the existing stores for that location.
S	getEntryStore() Get the output store at the entry block of a given control flow graph.
@Nullable TransferInput<V,S>	getInput(Block b) Get the transfer input of a given Block b.
protected S	getStoreAfter(Block b) Returns the store corresponding to the location right after the basic block b.
protected void	initFields(ControlFlowGraph cfg) Initialize class fields based on a given control flow graph.
protected void	initInitialInputs() Initialize the transfer inputs of every basic block before performing the analysis.
void	performAnalysis(ControlFlowGraph cfg) Perform the actual analysis.
void	performAnalysisBlock(Block b) Perform the actual analysis on one block.
protected void	propagateStoresTo(Block pred, @Nullable Node node, TransferInput<V,S> currentInput, Store.FlowRule flowRule, boolean addToWorklistAgain) Propagate the stores in currentInput to the next block in the direction of analysis, according to the flowRule.
S	runAnalysisFor(Node node, boolean before, TransferInput<V,S> transferInput, IdentityHashMap<Node,V> nodeValues, Map<TransferInput<V,S>,IdentityHashMap<Node,TransferResult<V,S>>> analysisCaches) Runs the analysis again within the block of node and returns the store at the location of node.

Methods inherited from class org.checkerframework.dataflow.analysis.AbstractAnalysis

addToWorklist, callTransferFunction, getContainingClass, getContainingMethod, getCurrentTree, getDirection, getExceptionalExitStore, getNodesForTree, getNodeValues, getRegularExitStore, getResult, getTransferFunction, getValue, getValue, init, isRunning, readFromStore, setCurrentNode, setCurrentTree, updateNodeValues

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.checkerframework.dataflow.analysis.Analysis

getDirection, getExceptionalExitStore, getRegularExitStore, getResult, getTransferFunction, getValue, getValue, isRunning

Field Detail

outStores

protected final IdentityHashMap<Block,S extends Store<S>> outStores

Out stores after every basic block (assumed to be 'no information' if not present).

exceptionStores

protected final IdentityHashMap<ExceptionBlock,S extends Store<S>> exceptionStores

Exception store of an exception block, propagated by exceptional successors of its exception block, and merged with the normal TransferResult.

storeAtEntry

protected S extends Store<S> storeAtEntry

The store right before the entry block.

Constructor Detail

BackwardAnalysisImpl

public BackwardAnalysisImpl()

Construct an object that can perform a org.checkerframework.dataflow backward analysis over a control flow graph. The transfer function is set by the subclass, e.g., org.checkerframework.framework.flow.CFAbstractAnalysis, later.

BackwardAnalysisImpl

public BackwardAnalysisImpl(T transfer)

Construct an object that can perform a org.checkerframework.dataflow backward analysis over a control flow graph given a transfer function.

Parameters:

transfer - the transfer function

Method Detail

performAnalysis

public void performAnalysis(ControlFlowGraph cfg)

Description copied from interface: Analysis

Perform the actual analysis.

Specified by:

performAnalysis in interface Analysis<V extends AbstractValue<V>,S extends Store<S>,T extends BackwardTransferFunction<V,S>>

Parameters:

cfg - the control flow graph

performAnalysisBlock

public void performAnalysisBlock(Block b)

Description copied from interface: Analysis

Perform the actual analysis on one block.

Specified by:

performAnalysisBlock in interface Analysis<V extends AbstractValue<V>,S extends Store<S>,T extends BackwardTransferFunction<V,S>>

Parameters:

b - the block to analyze

getInput

public @Nullable TransferInput<V,S> getInput(Block b)

Description copied from interface: Analysis

Get the transfer input of a given Block b.

Specified by:

getInput in interface Analysis<V extends AbstractValue<V>,S extends Store<S>,T extends BackwardTransferFunction<V,S>>

Parameters:

b - a given Block

Returns:

the transfer input of this Block

getEntryStore

public S getEntryStore()

Description copied from interface: BackwardAnalysis

Get the output store at the entry block of a given control flow graph. For a backward analysis, the output store contains the analyzed flow information from the exit block to the entry block.

Specified by:

getEntryStore in interface BackwardAnalysis<V extends AbstractValue<V>,S extends Store<S>,T extends BackwardTransferFunction<V,S>>

Returns:

the output store at the entry block of a given control flow graph

initFields

protected void initFields(ControlFlowGraph cfg)

Description copied from class: AbstractAnalysis

Initialize class fields based on a given control flow graph. Sub-class may override this method to initialize customized fields.

Overrides:

initFields in class AbstractAnalysis<V extends AbstractValue<V>,S extends Store<S>,T extends BackwardTransferFunction<V,S>>

Parameters:

cfg - a given control flow graph

initInitialInputs

@RequiresNonNull(value="cfg")
protected void initInitialInputs()

Description copied from class: AbstractAnalysis

Initialize the transfer inputs of every basic block before performing the analysis.

Specified by:

initInitialInputs in class AbstractAnalysis<V extends AbstractValue<V>,S extends Store<S>,T extends BackwardTransferFunction<V,S>>

propagateStoresTo

protected void propagateStoresTo(Block pred,
                                 @Nullable Node node,
                                 TransferInput<V,S> currentInput,
                                 Store.FlowRule flowRule,
                                 boolean addToWorklistAgain)

Description copied from class: AbstractAnalysis

Propagate the stores in currentInput to the next block in the direction of analysis, according to the flowRule.

Specified by:

propagateStoresTo in class AbstractAnalysis<V extends AbstractValue<V>,S extends Store<S>,T extends BackwardTransferFunction<V,S>>

Parameters:

pred - the target block to propagate the stores to

node - the node of the target block

currentInput - the current transfer input

flowRule - the flow rule being used

addToWorklistAgain - whether the block should be added to AbstractAnalysis.worklist again

addStoreAfter

protected void addStoreAfter(Block pred,
                             @Nullable Node node,
                             S s,
                             boolean addBlockToWorklist)

Add a store after the basic block pred by merging with the existing stores for that location.

Parameters:

pred - the basic block

node - the node of the basic block b

s - the store being added

addBlockToWorklist - whether the basic block b should be added back to Worklist

getStoreAfter

protected S getStoreAfter(Block b)

Returns the store corresponding to the location right after the basic block b.

Parameters:

b - the given block

Returns:

the store right after the given block

runAnalysisFor

public S runAnalysisFor(@FindDistinct
                        Node node,
                        boolean before,
                        TransferInput<V,S> transferInput,
                        IdentityHashMap<Node,V> nodeValues,
                        Map<TransferInput<V,S>,IdentityHashMap<Node,TransferResult<V,S>>> analysisCaches)

Description copied from interface: Analysis

Runs the analysis again within the block of node and returns the store at the location of node. If before is true, then the store immediately before the Node node is returned. Otherwise, the store immediately after node is returned. If analysisCaches is not null, this method uses a cache. analysisCaches is a map of a block of node to the cached analysis result. If the cache for transferInput is not in analysisCaches, this method creates new cache and stores it in analysisCaches. The cache is a map of nodes to the analysis results of the nodes.

Specified by:

runAnalysisFor in interface Analysis<V extends AbstractValue<V>,S extends Store<S>,T extends BackwardTransferFunction<V,S>>

Parameters:

node - the node to analyze

before - the boolean value to indicate which store to return (if it is true, return the store immediately before node; otherwise, the store after node is returned)

transferInput - the transfer input of the block of this node

nodeValues - abstract values of nodes

analysisCaches - caches of analysis results

Returns:

the store before or after node (depends on the value of before) after running the analysis