public class

DFA2

extends Object
implements IDFA<InsnType extends IInstruction>
java.lang.Object
   ↳ com.pnfsoftware.jeb.core.units.code.asm.cfg.DFA2<InsnType extends com.pnfsoftware.jeb.core.units.code.IInstruction>

Class Overview

Lean Data Flow Analysis (DFA) object for a CFG.

DFA objects can be configured and performed using CFG.doDataFlowAnalysis() methods.

Summary

Nested Classes
class DFA2.DUI  
Constants
int CACHE_DUI Cache basic def/use information at the instruction level
int CACHE_DUI_UDC_DUC CACHE_DUI + cache standard ud-chains and du-chains
int CACHE_NONE Nothing is cached
[Expand]
Inherited Constants
From interface com.pnfsoftware.jeb.core.units.code.IDFA
Public Constructors
DFA2(CFG<InsnType> cfg)
Create a DFA object with CFG-provided default collection flags and basic caching for instruction-level def-use information.
DFA2(CFG<InsnType> cfg, int collectionFlags, int cacheConfig)
Create a DFA object.
Public Methods
boolean checkInput(int varid)
Collection<Long> checkInputWithUses(int varid)
boolean checkNoUse(long addr, int varid)
boolean checkNoUse(long insnAddress, int varId, boolean reachOutIsUse)
Check whether a variable, defined at the provided instruction, is not used.
int checkNoUseEx(long insnAddress, int varId, boolean reachOutIsUse, int maxBlocks)
Check whether a variable, defined at the provided instruction, is not used.
boolean checkOutput(BasicBlock<InsnType> blk, int varid)
boolean checkOutput(int varid)
Collection<Long> checkOutputsWithDefs(int varid)
Collection<Long> checkOutputsWithDefs(BasicBlock<InsnType> blk, int varid)
Long checkSingleDef(long addr, int varid)
Long checkSingleDef(long addr, int varid, boolean liveInIsDef)
Check whether a used variable has a single explicit definition point (i.e.
Long checkSingleSource(long addr, int varid, boolean liveInIsDef)
Long checkSingleSource(long addr, int varid)
Long checkSingleUse(long addr, int varid)
Long checkSingleUse(long addr, int varid, boolean reachOutIsUse)
Collection<Integer> filterInputs(Collection<Integer> varids)
Map<Integer, Collection<Long>> filterInputsWithUses(Collection<Integer> varids)
Collection<Integer> filterOutputs(BasicBlock<InsnType> blk, Collection<Integer> varids)
Collection<Integer> filterOutputs(Collection<Integer> varids)
Map<Integer, Collection<Long>> filterOutputsWithDefs(Collection<Integer> varids)
Map<Integer, Collection<Long>> filterOutputsWithDefs(BasicBlock<InsnType> blk, Collection<Integer> varids)
String formatDUI(DFA2.DUI o)
int getCacheConfiguration()
Retrieve the cache configuration.
CFG<InsnType> getCfg()
Retrieve a reference to the CFG object that will be accessed and modified when performing an analysis.
DFA2.DUI getDUI(AddressableInstruction<InsnType> a)
DFA2.DUI getDUI(long addr)
DFA2.DUI getDUI(long addr, InsnType insn)
Map<Integer, Collection<Long>> getDefUseChains(long addr, boolean recordReachOut)
Map<Integer, Collection<Long>> getDefUseChains(long addr)
Collection<Long> getDefUses(long addr, int varid, int stopCount)
Collection<Long> getDefUses(long addr, int varid)
Collection<Long> getDefUses(long addr, int varid, int stopcount, boolean verifyStartOnDefPoint, boolean recordReachOut, BasicBlock<InsnType> blkForLiveChains, int idxForLiveChains, int maxBlocks)
Find the list of usage points for a defined variable.
Collection<Long> getInputMap(int varid)
Map<Integer, Collection<Long>> getInputMap()
Collection<Integer> getInputs()
Map<Integer, Collection<Long>> getInputsWithUses()
Set<Integer> getInstructionAllDefs(long addr)
Set<Integer> getInstructionAllUses(long addr)
Set<Integer> getInstructionDefs(long addr)
Set<Integer> getInstructionPotentialDefs(long addr)
Set<Integer> getInstructionPotentialUses(long addr)
Set<Integer> getInstructionSpoiledDefs(long addr)
Set<Integer> getInstructionUses(long addr)
Map<Integer, Collection<Long>> getLiveChains(BasicBlock<InsnType> b, int idx)
Map<Integer, Collection<Long>> getLiveChains(BasicBlock<InsnType> b, int idx, Collection<Integer> varids)
Collection<Long> getLiveChains(BasicBlock<InsnType> b, int idx, int varid)
int getMaxBlocks()
Retrieve the maximum block count used for common DFA operations.
Map<Integer, Collection<Long>> getOutputMap()
Map<Integer, Collection<Long>> getOutputMap(BasicBlock<InsnType> blk)
Collection<Long> getOutputMap(BasicBlock<InsnType> blk, int varid)
Collection<Long> getOutputMap(int varid)
Collection<Integer> getOutputs(BasicBlock<InsnType> blk)
Collection<Integer> getOutputs()
Map<Integer, Collection<Long>> getOutputsWithDefs(BasicBlock<InsnType> blk)
Map<Integer, Collection<Long>> getOutputsWithDefs()
Map<Integer, Collection<Long>> getReachChains(BasicBlock<InsnType> b, int idx)
Collection<Long> getReachChains(BasicBlock<InsnType> b, int idx, int varid)
Map<Integer, Collection<Long>> getReachChains(BasicBlock<InsnType> b, int idx, Collection<Integer> varids)
Map<Integer, Collection<Long>> getUseDefChains(long addr)
Map<Integer, Collection<Long>> getUseDefChains(long addr, boolean recordLiveIn)
Collection<Long> getUseDefs(long addr, int varid, int stopCount)
Collection<Long> getUseDefs(long addr, int varid)
Collection<Long> getUseDefs(long addr, int varid, int stopcount, boolean verifyStartOnUsePoint, boolean recordLiveIn, BasicBlock<InsnType> blkForReachChains, int idxForReachChains, boolean[] aDetectedUseDiscrepancy, boolean treatSpoiledAsDefs, int maxBlocks)
Find the list of definition points for a used variable.
Collection<Integer> getUseDiscrepancies(long addr)
Retrieve the list of use-discrepancies at the provided instruction address.
int getVariableCollectionFlags()
Retrieve the variable collection flags.
IVariableInformationProvider getVariableInformationProvider()
void invalidate()
Invalidate the analysis.
boolean isCleanCopies()
boolean isIntegrateCalculatedInputRegisters()
boolean isNotRedefined(int varid, long addr0, long addr1)
Determine if a variable reaching a start instruction has not been redefined when it reaches a final instruction.
boolean isNotRedefined(int varid, BasicBlock<InsnType> b0, int i0, BasicBlock<InsnType> b1, int i1)
Determine if a variable reaching a start instruction has not been redefined when it reaches a final instruction.
boolean isTerminator(BasicBlock<InsnType> blk)
Determine whether the provided block is a terminator.
boolean isUseDiscrepancy(long addr, int varid)
boolean isValid()
Determine whether the current analysis was performed and is valid.
Boolean isVarReachingFromTo(int varid, BasicBlock<InsnType> b0, int i0, BasicBlock<InsnType> b1, int i1)
Determine if a variable used by the start instruction reaches the final instruction with the same value.
Boolean isVarReachingFromTo(int varid, long addr0, long addr1)
Determine if a variable used by the start instruction reaches the final instruction with the same value.
void notifyInstructionUpdate(long addr)
void perform()
Perform data flow analysis on the CFG.
void setCacheConfiguration(int value)
Set or update the cache configuration of this object.
void setCleanCopies(boolean cleanCopies)
void setIntegrateCalculatedInputRegisters(boolean integrateCalculatedInputRegisters)
void setMaxBlocks(int maxBlocks)
Set an exploration threshold for most DFA operations.
void setVariableCollectionFlags(int flags)
Set the variable collection flags.
void setVariableInformationProvider(IVariableInformationProvider varInfoProvider)
String toString()
[Expand]
Inherited Methods
From class java.lang.Object
From interface com.pnfsoftware.jeb.core.units.code.IDFA

Constants

public static final int CACHE_DUI

Cache basic def/use information at the instruction level

Constant Value: 1 (0x00000001)

public static final int CACHE_DUI_UDC_DUC

CACHE_DUI + cache standard ud-chains and du-chains

Constant Value: 2 (0x00000002)

public static final int CACHE_NONE

Nothing is cached

Constant Value: 0 (0x00000000)

Public Constructors

public DFA2 (CFG<InsnType> cfg)

Create a DFA object with CFG-provided default collection flags and basic caching for instruction-level def-use information. This object can be further configured by invoking its various setters.

public DFA2 (CFG<InsnType> cfg, int collectionFlags, int cacheConfig)

Create a DFA object. This object can be further configured by invoking its various setters.

Parameters
collectionFlags collection flags, see constants in DefUseInfo
cacheConfig 0= no cache, 1= cached for instruction-level def-use information; 2= 1 + cache for ud-chains and du-chains

Public Methods

public boolean checkInput (int varid)

public Collection<Long> checkInputWithUses (int varid)

public boolean checkNoUse (long addr, int varid)

public boolean checkNoUse (long insnAddress, int varId, boolean reachOutIsUse)

Check whether a variable, defined at the provided instruction, is not used.

Parameters
insnAddress initial instruction address
varId defined variable at the initial instruction
Returns
  • true if the variable is not used, and optionally (if reachOutIsUse is true), is overwritten before reaching possible end-blocks

public int checkNoUseEx (long insnAddress, int varId, boolean reachOutIsUse, int maxBlocks)

Check whether a variable, defined at the provided instruction, is not used.

Parameters
insnAddress initial instruction address
varId defined variable at the initial instruction
Returns
  • 1: some uses; 0: no use; -1: no use, but may be a meaningful output; -2: unknown (may be returned only if maxBlocks is positive); -3: error

public boolean checkOutput (BasicBlock<InsnType> blk, int varid)

public boolean checkOutput (int varid)

public Collection<Long> checkOutputsWithDefs (int varid)

public Collection<Long> checkOutputsWithDefs (BasicBlock<InsnType> blk, int varid)

public Long checkSingleDef (long addr, int varid)

public Long checkSingleDef (long addr, int varid, boolean liveInIsDef)

Check whether a used variable has a single explicit definition point (i.e. it is a non-input defined at a unique address).

Parameters
addr initial instruction address
varid used variable at the initial instruction
Returns
  • the instruction address, if the variable used at the provided instruction has a single def-point; -1 is returned if the variable has no explicit def-point (as would be the case for method arguments); on error, or if multiple def-points are detected, null is returned

public Long checkSingleSource (long addr, int varid, boolean liveInIsDef)

public Long checkSingleSource (long addr, int varid)

public Long checkSingleUse (long addr, int varid)

public Long checkSingleUse (long addr, int varid, boolean reachOutIsUse)

public Collection<Integer> filterInputs (Collection<Integer> varids)

Parameters
varids optional collection of potential argument variables for which we want to verify uses; leave null to retrieve all potential arguments
Returns
  • a collection of variables that are used in the routine, that look like they have definitions outside the routine

public Map<Integer, Collection<Long>> filterInputsWithUses (Collection<Integer> varids)

public Collection<Integer> filterOutputs (BasicBlock<InsnType> blk, Collection<Integer> varids)

public Collection<Integer> filterOutputs (Collection<Integer> varids)

public Map<Integer, Collection<Long>> filterOutputsWithDefs (Collection<Integer> varids)

public Map<Integer, Collection<Long>> filterOutputsWithDefs (BasicBlock<InsnType> blk, Collection<Integer> varids)

public String formatDUI (DFA2.DUI o)

public int getCacheConfiguration ()

Retrieve the cache configuration.

Returns
  • value one of CACHE_xxx attribute

public CFG<InsnType> getCfg ()

Retrieve a reference to the CFG object that will be accessed and modified when performing an analysis.

public DFA2.DUI getDUI (AddressableInstruction<InsnType> a)

public DFA2.DUI getDUI (long addr)

public DFA2.DUI getDUI (long addr, InsnType insn)

public Map<Integer, Collection<Long>> getDefUseChains (long addr, boolean recordReachOut)

public Map<Integer, Collection<Long>> getDefUseChains (long addr)

public Collection<Long> getDefUses (long addr, int varid, int stopCount)

public Collection<Long> getDefUses (long addr, int varid)

public Collection<Long> getDefUses (long addr, int varid, int stopcount, boolean verifyStartOnDefPoint, boolean recordReachOut, BasicBlock<InsnType> blkForLiveChains, int idxForLiveChains, int maxBlocks)

Find the list of usage points for a defined variable.

Parameters
addr initial instruction address
varid defined variable
stopcount the search will stop if the use-count reaches that threshold; use <= 0 to mean no stopcount
verifyStartOnDefPoint if true, the variable must be defined by the provided initial instruction (else the method will return null)
recordReachOut if true, if the variable reaches the CFG output, a pseudo usage will be recorded as -1
blkForLiveChains optional basic block used to record live variables
idxForLiveChains optional block index used to record live variables
maxBlocks maximum number of basic blocks to be examined; use -1 to mean all; if a positive value is provided, the returned list of addresses may contain -2 to indicate that a usage may be located in an unexplored block
Returns
  • a list of addresses where the variable is used; the list may contain -1 to indicate the the variable reached an output; never returns null unless verifyStartOnDefPoint was true

public Collection<Long> getInputMap (int varid)

public Map<Integer, Collection<Long>> getInputMap ()

public Collection<Integer> getInputs ()

public Map<Integer, Collection<Long>> getInputsWithUses ()

public Set<Integer> getInstructionAllDefs (long addr)

public Set<Integer> getInstructionAllUses (long addr)

public Set<Integer> getInstructionDefs (long addr)

public Set<Integer> getInstructionPotentialDefs (long addr)

public Set<Integer> getInstructionPotentialUses (long addr)

public Set<Integer> getInstructionSpoiledDefs (long addr)

public Set<Integer> getInstructionUses (long addr)

public Map<Integer, Collection<Long>> getLiveChains (BasicBlock<InsnType> b, int idx)

public Map<Integer, Collection<Long>> getLiveChains (BasicBlock<InsnType> b, int idx, Collection<Integer> varids)

public Collection<Long> getLiveChains (BasicBlock<InsnType> b, int idx, int varid)

public int getMaxBlocks ()

Retrieve the maximum block count used for common DFA operations. See setMaxBlocks(int) for details.

public Map<Integer, Collection<Long>> getOutputMap ()

public Map<Integer, Collection<Long>> getOutputMap (BasicBlock<InsnType> blk)

public Collection<Long> getOutputMap (BasicBlock<InsnType> blk, int varid)

public Collection<Long> getOutputMap (int varid)

public Collection<Integer> getOutputs (BasicBlock<InsnType> blk)

public Collection<Integer> getOutputs ()

public Map<Integer, Collection<Long>> getOutputsWithDefs (BasicBlock<InsnType> blk)

public Map<Integer, Collection<Long>> getOutputsWithDefs ()

public Map<Integer, Collection<Long>> getReachChains (BasicBlock<InsnType> b, int idx)

public Collection<Long> getReachChains (BasicBlock<InsnType> b, int idx, int varid)

public Map<Integer, Collection<Long>> getReachChains (BasicBlock<InsnType> b, int idx, Collection<Integer> varids)

public Map<Integer, Collection<Long>> getUseDefChains (long addr)

public Map<Integer, Collection<Long>> getUseDefChains (long addr, boolean recordLiveIn)

public Collection<Long> getUseDefs (long addr, int varid, int stopCount)

public Collection<Long> getUseDefs (long addr, int varid)

public Collection<Long> getUseDefs (long addr, int varid, int stopcount, boolean verifyStartOnUsePoint, boolean recordLiveIn, BasicBlock<InsnType> blkForReachChains, int idxForReachChains, boolean[] aDetectedUseDiscrepancy, boolean treatSpoiledAsDefs, int maxBlocks)

Find the list of definition points for a used variable.

Parameters
addr initial instruction address
varid used variable, for which definitions are to be collected
stopcount the search will stop if the def-count reaches that threshold; use <=0 to mean no stopcount
verifyStartOnUsePoint if true, the variable must be used at the provided instruction (else the method will return null)
recordLiveIn if true, a candidate argument-definition is recorded as -1 in the returned list
blkForReachChains optional basic block used to record reaching variables
idxForReachChains optional block index used to record reaching variables
aDetectedUseDiscrepancy optional one-element array, if provided, any use discrepancy (using a potentially undefined variable) will interrupt the search, and this flag will be set to true
treatSpoiledAsDefs if true, spoiled information for variables will be treated as a regular definition
maxBlocks maximum number of basic blocks to be examined; use -1 to mean all; if a positive value is provided, the returned list of addresses may contain -2 to indicate that a definition may be located in an unexplored block
Returns
  • a list of addresses where the variable was defined; the list may contain -1 to indicate a candidate argument-definition; never return null unless verifyStartOnUsePoint was true

public Collection<Integer> getUseDiscrepancies (long addr)

Retrieve the list of use-discrepancies at the provided instruction address.

Parameters
addr instruction address
Returns
  • a list of variables whose usage at the provided location appears to be incorrect (i.e. not all paths to this usage carry a definition of the variable)

public int getVariableCollectionFlags ()

Retrieve the variable collection flags.

Returns

public IVariableInformationProvider getVariableInformationProvider ()

public void invalidate ()

Invalidate the analysis. Clients have the responsibility to invalidate an analysis if the CFG was modified in such a way that data flow should be recalculated.

public boolean isCleanCopies ()

public boolean isIntegrateCalculatedInputRegisters ()

public boolean isNotRedefined (int varid, long addr0, long addr1)

Determine if a variable reaching a start instruction has not been redefined when it reaches a final instruction. (Note that this method does not verify that varid actually has definitions reaching the start or final instruction; it is up to the caller to verify that.)

Parameters
varid variable id
addr0 start address, exclusive
addr1 final address, also exclusive
Returns
  • true if the variable was not redefined

public boolean isNotRedefined (int varid, BasicBlock<InsnType> b0, int i0, BasicBlock<InsnType> b1, int i1)

Determine if a variable reaching a start instruction has not been redefined when it reaches a final instruction. (Note that this method does not verify that varid actually has definitions reaching the start or final instruction; it is up to the caller to verify that.)

Parameters
varid variable id
b0 start block
i0 final block
b1 index of the start instruction in the start block, exclusive
i1 index of the final instruction in the final block, also exclusive
Returns
  • true if the variable was not redefined

public boolean isTerminator (BasicBlock<InsnType> blk)

Determine whether the provided block is a terminator. A terminator has no output and its final instruction is a clean routine terminator.

Parameters
blk block to test
Returns
  • true if the block is a clean terminator

public boolean isUseDiscrepancy (long addr, int varid)

public boolean isValid ()

Determine whether the current analysis was performed and is valid.

public Boolean isVarReachingFromTo (int varid, BasicBlock<InsnType> b0, int i0, BasicBlock<InsnType> b1, int i1)

Determine if a variable used by the start instruction reaches the final instruction with the same value.

Parameters
varid variable id
b0 start block
i0 final block
b1 index of the start instruction in the start block, exclusive
i1 index of the final instruction in the final block, also exclusive
Returns
  • success indicator; null means unknown

public Boolean isVarReachingFromTo (int varid, long addr0, long addr1)

Determine if a variable used by the start instruction reaches the final instruction with the same value.

Parameters
varid variable id
addr0 start address, exclusive
addr1 final address, also exclusive
Returns
  • success indicator; null means unknown

public void notifyInstructionUpdate (long addr)

public void perform ()

Perform data flow analysis on the CFG. Upon return, basic blocks will have their data chains (ud and du, full and simple) set up and accessible.

public void setCacheConfiguration (int value)

Set or update the cache configuration of this object.

Parameters
value one of CACHE_xxx attribute

public void setCleanCopies (boolean cleanCopies)

public void setIntegrateCalculatedInputRegisters (boolean integrateCalculatedInputRegisters)

Parameters
integrateCalculatedInputRegisters if true, the live registers determined after analysis will be integrated in the use-def chains

public void setMaxBlocks (int maxBlocks)

Set an exploration threshold for most DFA operations. By default, there is no threshold. The threshold is a block count; if a block count is reached, a chain may contain a reference to the invalid address -2 in order to indicate an incomplete result.

Parameters
maxBlocks -1 means no limit

public void setVariableCollectionFlags (int flags)

Set the variable collection flags.

Parameters
flags flags, see DefUseInfo

public void setVariableInformationProvider (IVariableInformationProvider varInfoProvider)

public String toString ()