public class

DFA3

extends Object
implements IDFA3<InsnType extends IInstruction, Block extends IBasicBlock<InsnType>>
java.lang.Object
   ↳ com.pnfsoftware.jeb.core.units.code.DFA3<InsnType extends com.pnfsoftware.jeb.core.units.code.IInstruction, Block extends com.pnfsoftware.jeb.core.units.code.IBasicBlock<InsnType>>

Class Overview

Lean Data Flow Analysis (DFA) object implementation.

Summary

Nested Classes
class DFA3.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.IDFA3
Public Constructors
DFA3(IControlFlowGraph<InsnType, Block> cfg)
Create a DFA object with CFG-provided default collection flags and basic caching for instruction-level def-use information.
DFA3(IControlFlowGraph<InsnType, Block> 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(int varid)
boolean checkOutput(Block blk, int varid)
Collection<Long> checkOutputsWithDefs(int varid)
Collection<Long> checkOutputsWithDefs(Block blk, int varid)
Long checkSingleDef(long addr, int varid)
Check whether a used variable has a single definition point.
Long checkSingleDef(long addr, int varid, boolean liveInIsDef)
Check whether a used variable has a single explicit definition point (i.e.
Long checkSingleDefNoInput(long addr, int varid)
Check whether a used variable has a single explicit definition point.
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)
void collectInstructionAllDefs(long addr, Collection<Integer> r)
void collectInstructionAllUses(long addr, Collection<Integer> r)
Collection<Integer> filterInputs(Collection<Integer> varids)
Map<Integer, Collection<Long>> filterInputsWithUses(Collection<Integer> varids)
Collection<Integer> filterOutputs(Block blk, Collection<Integer> varids)
Collection<Integer> filterOutputs(Collection<Integer> varids)
Map<Integer, Collection<Long>> filterOutputsWithDefs(Collection<Integer> varids)
Map<Integer, Collection<Long>> filterOutputsWithDefs(Block blk, Collection<Integer> varids)
String formatDUI(DFA3.DUI o)
Collection<Long> getBlockDefUses(long addr, int varid)
int getCacheConfiguration()
Retrieve the cache configuration.
IControlFlowGraph<InsnType, Block> getCfg()
Retrieve a reference to the CFG object that will be accessed and modified when performing an analysis.
DFA3.DUI getDUI(AddressableInstruction<InsnType> a)
DFA3.DUI getDUI(long addr)
DFA3.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, Block blkForLiveChains, int idxForLiveChains, int maxBlocks, boolean limitToStartBlock)
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(Block b, int idx, Collection<Integer> varids)
Collection<Long> getLiveChains(Block b, int idx, int varid)
Map<Integer, Collection<Long>> getLiveChains(Block b, int idx)
int getMaxBlocks()
Retrieve the maximum block count used for common DFA operations.
Map<Integer, Collection<Long>> getOutputMap()
Collection<Long> getOutputMap(Block blk, int varid)
Map<Integer, Collection<Long>> getOutputMap(Block blk)
Collection<Long> getOutputMap(int varid)
Collection<Integer> getOutputs(Block blk)
Collection<Integer> getOutputs()
Map<Integer, Collection<Long>> getOutputsWithDefs()
Map<Integer, Collection<Long>> getOutputsWithDefs(Block blk)
Map<Integer, Collection<Long>> getReachChains(Block b, int idx, Collection<Integer> varids)
Collection<Long> getReachChains(Block b, int idx, int varid)
Map<Integer, Collection<Long>> getReachChains(Block b, int idx)
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, boolean verifyStartOnUsePoint, boolean recordLiveIn, Block blkForReachChains, int idxForReachChains, boolean[] aDetectedUseDiscrepancy, boolean treatSpoiledAsDefs, int maxBlocks)
Find the list of definition points for a used variable.
Collection<Long> getUseDefs(long addr, int varid, int stopCount)
Collection<Long> getUseDefs(long addr, int varid)
Collection<Integer> getUseDiscrepancies(long addr)
Retrieve the list of use-discrepancies at the provided instruction address.
int getVariableCollectionFlags()
Retrieve the variable collection flags.
ICFGOwnerContext getVariableInformationProvider()
void invalidate()
Invalidate the analysis.
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, Block b0, int i0, Block b1, int i1)
Determine if a variable reaching a start instruction has not been redefined when it reaches a final instruction.
boolean isTerminator(Block 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, long addr0, long addr1)
Determine if a variable used by the start instruction reaches the final instruction with the same value.
Boolean isVarReachingFromTo(int varid, Block b0, int i0, Block b1, int i1)
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 setIntegrateCalculatedInputRegisters(boolean integrateCalculatedInputRegisters)
int setMaxBlocks(int maxBlocks)
Set an exploration threshold for most DFA operations.
void setVariableCollectionFlags(int flags)
Set the variable collection flags.
void setVariableInformationProvider(ICFGOwnerContext varInfoProvider)
String toString()
[Expand]
Inherited Methods
From class java.lang.Object
From interface com.pnfsoftware.jeb.core.units.code.IDFA3

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 DFA3 (IControlFlowGraph<InsnType, Block> 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 DFA3 (IControlFlowGraph<InsnType, Block> 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 (int varid)

public boolean checkOutput (Block blk, int varid)

public Collection<Long> checkOutputsWithDefs (int varid)

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

public Long checkSingleDef (long addr, int varid)

Check whether a used variable has a single definition point. The def point may be explicit (e.g. resulting from an assignment) or implicit (e.g. provided as a parameter to the routine, which is always represented as the address -1).

Parameters
addr initial instruction address
varid used variable at the initial instruction

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 checkSingleDefNoInput (long addr, int varid)

Check whether a used variable has a single explicit definition point. The def point cannot be a routine input (i.e. the definition must be explicit).

Parameters
addr initial instruction address
varid used variable at the initial instruction

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 void collectInstructionAllDefs (long addr, Collection<Integer> r)

public void collectInstructionAllUses (long addr, Collection<Integer> r)

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 (Block 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 (Block blk, Collection<Integer> varids)

public String formatDUI (DFA3.DUI o)

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

public int getCacheConfiguration ()

Retrieve the cache configuration.

Returns
  • value one of CACHE_xxx attribute

public IControlFlowGraph<InsnType, Block> getCfg ()

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

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

public DFA3.DUI getDUI (long addr)

public DFA3.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, Block blkForLiveChains, int idxForLiveChains, int maxBlocks, boolean limitToStartBlock)

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
limitToStartBlock if true, the exploration will stop as soon as a use is detected outside the provide starting block, where the def took place, and -2 will be added to the returned list (if true, blkForLiveChains should be null); note: unlike what maxBlocks intends to do, a -2 in the resulting collection will indicate a definite out-of-block use
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 (Block b, int idx, Collection<Integer> varids)

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

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

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 Collection<Long> getOutputMap (Block blk, int varid)

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

public Collection<Long> getOutputMap (int varid)

public Collection<Integer> getOutputs (Block blk)

public Collection<Integer> getOutputs ()

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

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

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

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

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

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, boolean verifyStartOnUsePoint, boolean recordLiveIn, Block 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<Long> getUseDefs (long addr, int varid, int stopCount)

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

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 if the variable)

public int getVariableCollectionFlags ()

Retrieve the variable collection flags.

Returns

public ICFGOwnerContext 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 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, Block b0, int i0, Block 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 (Block 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, 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 Boolean isVarReachingFromTo (int varid, Block b0, int i0, Block 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 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 setIntegrateCalculatedInputRegisters (boolean integrateCalculatedInputRegisters)

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

public int 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
Returns
  • the previous value for this setting

public void setVariableCollectionFlags (int flags)

Set the variable collection flags.

Parameters
flags flags, see DefUseInfo

public void setVariableInformationProvider (ICFGOwnerContext varInfoProvider)

public String toString ()