Interface IDFA<InsnType extends IInstruction>

All Known Implementing Classes:
DFA4

public interface IDFA<InsnType extends IInstruction>
Specification of a data flow analysis objects for control flow graphs.
  • Field Details

    • STANDARD_COLLECTION_FLAGS

      static final int STANDARD_COLLECTION_FLAGS
      Standard setting for variable collection flags: conservative.
      See Also:
    • STANDARD_INTEGRATE_INPUTS

      static final boolean STANDARD_INTEGRATE_INPUTS
      Standard setting for routine inputs integration into output maps and reaching-register chains: enabled.
      See Also:
  • Method Details

    • getCfg

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

      void setVariableCollectionFlags(int varCollectionFlags)
      Set the variable collection flags.
      Parameters:
      varCollectionFlags - flags, see DefUseInfo
    • getVariableCollectionFlags

      int getVariableCollectionFlags()
      Retrieve the variable collection flags.
      Returns:
      flags, see DefUseInfo
    • setConservative

      default void setConservative()
      Convenience method used to set or remove DefUseInfo.CONSERVATIVE variable collection flags.
    • isConservative

      default boolean isConservative()
      Convenience method used to determine whether the variable collection flags are DefUseInfo.CONSERVATIVE.
      Returns:
    • setIntegrateCalculatedInputRegisters

      boolean setIntegrateCalculatedInputRegisters(boolean enabled)
      Parameters:
      enabled -
      Returns:
      the previous value for this setting
    • isIntegrateCalculatedInputRegisters

      boolean isIntegrateCalculatedInputRegisters()
    • setAlwaysExamineIrregularFlows

      boolean setAlwaysExamineIrregularFlows(boolean enabled)
      Parameters:
      enabled -
      Returns:
      the previous value for this setting
    • isAlwaysExamineIrregularFlows

      boolean isAlwaysExamineIrregularFlows()
    • setVariableInformationProvider

      ICFGOwnerContext setVariableInformationProvider(ICFGOwnerContext provider)
      Parameters:
      provider -
      Returns:
      the previously set provider
    • getVariableInformationProvider

      ICFGOwnerContext getVariableInformationProvider()
    • setMaxBlocks

      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
    • getMaxBlocks

      int getMaxBlocks()
      Retrieve the maximum block count used for common DFA operations. See setMaxBlocks(int) for details.
      Returns:
    • perform

      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.
    • isValid

      boolean isValid()
      Determine whether the current analysis was performed and is valid.
      Returns:
    • invalidate

      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.
    • notifyInstructionUpdate

      void notifyInstructionUpdate(long addr)
    • invalidateForRemoval

      void invalidateForRemoval(long addr0)
      Selectively invalidate the cache in preparation for an instruction pseudo-removal (neutering). This method should be called before neutering takes place.
      Parameters:
      addr0 - address of the start instruction; it is assumed that this instruction is no-throw
    • invalidateForSubstitution

      void invalidateForSubstitution(long addr0, Collection<Long> addr1coll, Collection<Long> srccoll)
      Selectively invalidate the cache in preparation for an expression-substitution. This method should be called before the substitution by an immediate took place.
      Parameters:
      addr0 - address of the start instruction, which defines the variable being substituted; it is assumed that this instruction is no-throw
      addr1coll - mandatory collection of addresses where the substitutions will take place place
      srccoll - optional collection of source instructions; if not provided, all instructions defining some of the substituted variables will be invalidated from the cache
    • invalidatePostSimpleSubstitutionWithMultiDefs

      void invalidatePostSimpleSubstitutionWithMultiDefs(Collection<Long> addr0coll, long addr1, int varid)
      Selectively invalidate DFA cache after the substitution of a variable X by an immediate. This method should be called after the substitution by an immediate took place.
      Parameters:
      addr0coll - collection of equivalent source instructions defining a target var X (e.g. X=3); these instructions must be left as-is when calling this method; it is assumed that these instructions are no-throw
      addr1 - destination instruction, whose target variable X was replaced by a constant
      varid - the variable that was propagated (X)
    • collectInstructionAllDefs

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

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

      Collection<Integer> getInstructionAllDefs(long addr)
    • getInstructionAllUses

      Collection<Integer> getInstructionAllUses(long addr)
    • getInstructionDefs

      Collection<Integer> getInstructionDefs(long addr)
      Returns:
      a list of variables defined by the instruction at index in the block
    • getInstructionUses

      Collection<Integer> getInstructionUses(long addr)
      Returns:
      a list of variables used by the instruction at index in the block
    • getInstructionPotentialDefs

      Collection<Integer> getInstructionPotentialDefs(long addr)
      Returns:
      a list of variables potentially defined by the instruction at index in the block; note that this data may not be present (empty lists) depending on DFA settings
    • getInstructionPotentialUses

      Collection<Integer> getInstructionPotentialUses(long addr)
      Returns:
      a list of variables potentially used by the instruction at index in the block; note that this data may not be present (empty lists) depending on DFA settings
    • getInstructionSpoiledDefs

      Collection<Integer> getInstructionSpoiledDefs(long addr)
      Returns:
      a list of variables potentially spoiled by the instruction at index in the block; note that this data may not be present (empty lists) depending on DFA settings
    • getDUI

      DUI getDUI(long addr)
      Parameters:
      addr -
      Returns:
    • getDUI

      Parameters:
      a -
      Returns:
    • getDUI

      DUI getDUI(long addr, InsnType insn)
      Parameters:
      addr -
      insn -
      Returns:
    • isTerminator

      boolean isTerminator(IBasicBlock<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
    • getInputs

      Collection<Integer> getInputs()
    • getInputMap

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

      Collection<Long> getInputMap(int varid)
    • getOutputs

    • getOutputMap

    • getOutputMap

      Collection<Long> getOutputMap(IBasicBlock<InsnType> blk, int varid)
    • getOutputs

      Collection<Integer> getOutputs()
    • getOutputMap

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

      Collection<Long> getOutputMap(int varid)
    • getUseDefChains

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

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

      Collection<Long> getUseDefs(long addr, int varid)
      Parameters:
      addr - instruction address
      varid - a variable, which must be used by the provided instruction
      Returns:
      a collection (possibly empty) or null if the variable is not used by the instruction
    • getUseDefs

      Collection<Long> getUseDefs(long addr, int varid, int stopCount)
      Parameters:
      addr - instruction address
      varid - a variable, which must be used by the provided instruction
      stopCount -
      Returns:
      a collection (possibly empty) or null if the variable is not used by the instruction
    • getBlockUseDefs

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

      Collection<Long> getDefUses(long addr, int varid)
      Parameters:
      addr - instruction address
      varid - a variable, which must be defined by the provided instruction
      Returns:
      a collection (possibly empty) or null if the variable is not defined by the instruction
    • getDefUses

      Collection<Long> getDefUses(long addr, int varid, int stopCount)
      Parameters:
      addr - instruction address
      varid - a variable, which must be defined by the provided instruction
      stopCount - optional stop count (-1 to collect as many uses as possible)
      Returns:
      a collection (possibly empty) or null if the variable is not defined by the instruction
    • getDefUses

      Collection<Long> getDefUses(long addr, int varid, int stopCount, boolean recordReachOut)
      Parameters:
      addr - instruction address
      varid - a variable, which must be defined by the provided instruction
      stopCount - optional stop count (-1 to collect as many uses as possible)
      recordReachOut - if true, a variable reaching is considered used (if so, the output list will contain -1)
      Returns:
      a collection (possibly empty) or null if the variable is not defined by the instruction
    • getBlockDefUses

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

      Collection<Long> getLiveChains(IBasicBlock<InsnType> b, int idx, int varid)
    • getLiveChains

      Collection<Long> getLiveChains(IBasicBlock<InsnType> b, int idx, int varid, int stopcount)
    • getLiveChains

      Map<Integer,Collection<Long>> getLiveChains(IBasicBlock<InsnType> b, int idx)
    • isAlive

      boolean isAlive(IBasicBlock<InsnType> b, int idx, int varid)
    • getReachChains

      Collection<Long> getReachChains(IBasicBlock<InsnType> b, int idx, int varid)
    • getReachChains

      Collection<Long> getReachChains(IBasicBlock<InsnType> b, int idx, int varid, int stopcount)
    • getReachChains

      Map<Integer,Collection<Long>> getReachChains(IBasicBlock<InsnType> b, int idx)
    • isReaching

      boolean isReaching(IBasicBlock<InsnType> b, int idx, int varid)
    • getUseDiscrepancies

      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)
    • isUseDiscrepancy

      boolean isUseDiscrepancy(long addr, int varid)
      Parameters:
      addr -
      varid -
      Returns:
    • checkNoUse

      int checkNoUse(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
      reachOutIsUse -
      maxBlocks -
      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
    • checkNoUse

      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
      reachOutIsUse -
      Returns:
      true if the variable is not used, and optionally (if reachOutIsUse is true), is overwritten before reaching possible end-blocks
    • checkNoUse

      boolean checkNoUse(long insnAddress, int varId)
      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; reaching-out is not considered a use
    • checkSingleUse

      Long checkSingleUse(long addr, int varid)
      Parameters:
      addr -
      varid -
      Returns:
    • checkSingleUse

      default boolean checkSingleUse(long addr, int varid, long expectedUseAddress)
    • checkSingleDefNoInput

      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
      Returns:
    • checkSingleDef

      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 (it must be used at the provided address; else, refer to checkSingleSource)
      Returns:
    • checkSingleDef

      default boolean checkSingleDef(long addr, int varid, long expectedDefAddress)
    • checkSingleSource

      Long checkSingleSource(long addr, int varid, boolean liveInIsDef)
      Parameters:
      addr -
      varid -
      liveInIsDef -
      Returns:
    • checkSingleSource

      Long checkSingleSource(long addr, int varid)
      Parameters:
      addr -
      varid -
      Returns:
    • checkSingleSource

      default boolean checkSingleSource(long addr, int varid, long expectedSourceAddress)
    • isVarReachingFromTo

      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.

      Important notes:
      - This method provides a must-reach result: if a multiple paths exist from source to sink, where the variable reaches the sink via some paths, but not on others (it is overwritten), the method returns false.
      - This method works from the source to the sink, and provides the guarantee that the variable was not overwritten when it reached the sink. There is no guarantee provided at the sink itself regarding other paths that may exist from different sources to the same sink.
      - This method also checks that the paths from the sink back that may connect back to the sink do not overwrite the variable defined at the source.

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

      Boolean isVarReachingFromTo(int varid, IBasicBlock<InsnType> b0, int i0, IBasicBlock<InsnType> b1, int i1)
      Determine if a variable used by the start instruction reaches the final instruction with the same value.

      Important notes:
      - This method provides a must-reach result: if a multiple paths exist from source to sink, where the variable reaches the sink via some paths, but not on others (it is overwritten), the method returns false.
      - This method works from the source to the sink, and provides the guarantee that the variable was not overwritten when it reached the sink. There is no guarantee provided at the sink itself regarding other paths that may exist from different sources to the same sink.
      - This method also checks that the paths from the sink back that may connect back to the sink do not overwrite the variable defined at the source.

      Parameters:
      varid - variable id
      b0 - start block (source)
      i0 - final block (sink)
      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
    • isVarReachingFromTo

      Boolean isVarReachingFromTo(int varid, IBasicBlock<InsnType> b0, int i0, IBasicBlock<InsnType> b1, int i1, boolean performExtendedChecks, int maxBlocks)
      Determine if a variable used by the start instruction reaches the final instruction with the same value.

      Important notes:
      - This method provides a must-reach result: if a multiple paths exist from source to sink, where the variable reaches the sink via some paths, but not on others (it is overwritten), the method returns false.
      - This method works from the source to the sink, and provides the guarantee that the variable was not overwritten when it reached the sink. There is no guarantee provided at the sink itself regarding other paths that may exist from different sources to the same sink.
      - if `performExtendedChecks` is true, this method also checks that the paths from the sink back that may connect back to the sink do not overwrite the variable defined at the source.

      Parameters:
      varid - variable id
      b0 - start block (source)
      i0 - final block (sink)
      b1 - index of the start instruction in the start block, exclusive
      i1 - index of the final instruction in the final block, also exclusive
      performExtendedChecks -
      maxBlocks - optional maximum count of blocks to be explored before failing
      Returns:
      success indicator; null means unknown