Package com.pnfsoftware.jeb.core.units.code

Interface IDFA<InsnType extends IInstruction>

Type Parameters:
InsnType - instruction type
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

      IControlFlowGraph<InsnType,IBasicBlock<InsnType>> getCfg()
      Retrieve a reference to the CFG object that will be accessed and modified when performing an analysis.
      Returns:
      control flow graph

    • 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:
      true if conservative collection is enabled

    • setIntegrateCalculatedInputRegisters

      boolean setIntegrateCalculatedInputRegisters(boolean enabled)
      Set whether calculated input registers should be integrated.
      Parameters:
      enabled - true to integrate calculated input registers
      Returns:
      the previous value for this setting

    • isIntegrateCalculatedInputRegisters

      boolean isIntegrateCalculatedInputRegisters()
      Determine whether calculated input registers are integrated.
      Returns:
      true if calculated input registers are integrated

    • setAlwaysExamineIrregularFlows

      boolean setAlwaysExamineIrregularFlows(boolean enabled)
      Set whether irregular flows should always be examined.
      Parameters:
      enabled - true to always examine irregular flows
      Returns:
      the previous value for this setting

    • isAlwaysExamineIrregularFlows

      boolean isAlwaysExamineIrregularFlows()
      Determine whether irregular flows are always examined.
      Returns:
      true if irregular flows are always examined

    • setVariableInformationProvider

      ICFGOwnerContext setVariableInformationProvider(ICFGOwnerContext provider)
      Set the variable information provider.
      Parameters:
      provider - variable information provider
      Returns:
      the previously set provider

    • getVariableInformationProvider

      ICFGOwnerContext getVariableInformationProvider()
      Get the variable information provider.
      Returns:
      variable information provider

    • 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:
      maximum block count

    • 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:
      true if the analysis is valid

    • 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)
      Notify the DFA that an instruction was updated.
      Parameters:
      addr - instruction address

    • 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)
      Collect all variables defined by an instruction.
      Parameters:
      addr - instruction address
      r - output collection

    • collectInstructionAllUses

      void collectInstructionAllUses(long addr, Collection<Integer> r)
      Collect all variables used by an instruction.
      Parameters:
      addr - instruction address
      r - output collection

    • getInstructionAllDefs

      Collection<Integer> getInstructionAllDefs(long addr)
      Get all variables defined by an instruction.
      Parameters:
      addr - instruction address
      Returns:
      defined variables

    • getInstructionAllUses

      Collection<Integer> getInstructionAllUses(long addr)
      Get all variables used by an instruction.
      Parameters:
      addr - instruction address
      Returns:
      used variables

    • getInstructionDefs

      Collection<Integer> getInstructionDefs(long addr)
      Get the variables defined by an instruction.
      Parameters:
      addr - instruction address
      Returns:
      a list of variables defined by the instruction at index in the block

    • getInstructionUses

      Collection<Integer> getInstructionUses(long addr)
      Get the variables used by an instruction.
      Parameters:
      addr - instruction address
      Returns:
      a list of variables used by the instruction at index in the block

    • getInstructionPotentialDefs

      Collection<Integer> getInstructionPotentialDefs(long addr)
      Get variables potentially defined by an instruction.
      Parameters:
      addr - instruction address
      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)
      Get variables potentially used by an instruction.
      Parameters:
      addr - instruction address
      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)
      Get variables potentially spoiled by an instruction.
      Parameters:
      addr - instruction address
      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)
      Get def-use information for an instruction.
      Parameters:
      addr - instruction address
      Returns:
      def-use information

    • getDUI

      DUI getDUI(AddressableInstruction<InsnType> a)
      Get def-use information for an addressable instruction.
      Parameters:
      a - addressable instruction
      Returns:
      def-use information

    • getDUI

      DUI getDUI(long addr, InsnType insn)
      Get def-use information for an instruction.
      Parameters:
      addr - instruction address
      insn - instruction
      Returns:
      def-use information

    • 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()
      Get input variables.
      Returns:
      input variables

    • getInputMap

      Map<Integer,Collection<Long>> getInputMap()
      Get the input map.
      Returns:
      input map

    • getInputMap

      Collection<Long> getInputMap(int varid)
      Get input locations for a variable.
      Parameters:
      varid - variable id
      Returns:
      input locations

    • getOutputs

      Collection<Integer> getOutputs(IBasicBlock<InsnType> blk)
      Get output variables for a block.
      Parameters:
      blk - basic block
      Returns:
      output variables

    • getOutputMap

      Map<Integer,Collection<Long>> getOutputMap(IBasicBlock<InsnType> blk)
      Get the output map for a block.
      Parameters:
      blk - basic block
      Returns:
      output map

    • getOutputMap

      Collection<Long> getOutputMap(IBasicBlock<InsnType> blk, int varid)
      Get output locations for a block and variable.
      Parameters:
      blk - basic block
      varid - variable id
      Returns:
      output locations

    • getOutputs

      Collection<Integer> getOutputs()
      Get output variables.
      Returns:
      output variables

    • getOutputMap

      Map<Integer,Collection<Long>> getOutputMap()
      Get the output map.
      Returns:
      output map

    • getOutputMap

      Collection<Long> getOutputMap(int varid)
      Get output locations for a variable.
      Parameters:
      varid - variable id
      Returns:
      output locations

    • getUseDefChains

      Map<Integer,Collection<Long>> getUseDefChains(long addr)
      Get use-def chains at an instruction.
      Parameters:
      addr - instruction address
      Returns:
      use-def chains

    • getDefUseChains

      Map<Integer,Collection<Long>> getDefUseChains(long addr)
      Get def-use chains at an instruction.
      Parameters:
      addr - instruction address
      Returns:
      def-use chains

    • getUseDefs

      Collection<Long> getUseDefs(long addr, int varid)
      Get definition locations for a variable use.
      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)
      Get definition locations for a variable use.
      Parameters:
      addr - instruction address
      varid - a variable, which must be used by the provided instruction
      stopCount - optional stop count
      Returns:
      a collection (possibly empty) or null if the variable is not used by the instruction

    • getBlockUseDefs

      Collection<Long> getBlockUseDefs(long addr, int varid)
      Get block-local definition locations for a variable use.
      Parameters:
      addr - instruction address
      varid - variable id
      Returns:
      definition locations

    • getDefUses

      Collection<Long> getDefUses(long addr, int varid)
      Get use locations for a variable definition.
      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)
      Get use locations for a variable definition.
      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)
      Get use locations for a variable definition.
      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)
      Get block-local use locations for a variable definition.
      Parameters:
      addr - instruction address
      varid - variable id
      Returns:
      use locations

    • getBlockDefUses

      Collection<Long> getBlockDefUses(long addr, int varid, int stopCount)
      Get block-local use locations for a variable definition.
      Parameters:
      addr - instruction address
      varid - variable id
      stopCount - optional stop count
      Returns:
      use locations

    • getLiveChains

      Collection<Long> getLiveChains(IBasicBlock<InsnType> b, int idx, int varid)
      Get live chains for a variable at a block location.
      Parameters:
      b - basic block
      idx - instruction index
      varid - variable id
      Returns:
      live chains

    • getLiveChains

      Collection<Long> getLiveChains(IBasicBlock<InsnType> b, int idx, int varid, int stopcount)
      Get live chains for a variable at a block location.
      Parameters:
      b - basic block
      idx - instruction index
      varid - variable id
      stopcount - optional stop count
      Returns:
      live chains

    • getLiveChains

      Map<Integer,Collection<Long>> getLiveChains(IBasicBlock<InsnType> b, int idx)
      Get live chains at a block location.
      Parameters:
      b - basic block
      idx - instruction index
      Returns:
      live chains

    • isAlive

      boolean isAlive(IBasicBlock<InsnType> b, int idx, int varid)
      Determine whether a variable is alive at a block location.
      Parameters:
      b - basic block
      idx - instruction index
      varid - variable id
      Returns:
      true if the variable is alive

    • getReachChains

      Collection<Long> getReachChains(IBasicBlock<InsnType> b, int idx, int varid)
      Get reach chains for a variable at a block location.
      Parameters:
      b - basic block
      idx - instruction index
      varid - variable id
      Returns:
      reach chains

    • getReachChains

      Collection<Long> getReachChains(IBasicBlock<InsnType> b, int idx, int varid, int stopcount)
      Get reach chains for a variable at a block location.
      Parameters:
      b - basic block
      idx - instruction index
      varid - variable id
      stopcount - optional stop count
      Returns:
      reach chains

    • getReachChains

      Map<Integer,Collection<Long>> getReachChains(IBasicBlock<InsnType> b, int idx)
      Get reach chains at a block location.
      Parameters:
      b - basic block
      idx - instruction index
      Returns:
      reach chains

    • isReaching

      boolean isReaching(IBasicBlock<InsnType> b, int idx, int varid)
      Determine whether a variable reaches a block location.
      Parameters:
      b - basic block
      idx - instruction index
      varid - variable id
      Returns:
      true if the variable is reaching

    • 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)
      Determine whether a use discrepancy exists for a variable.
      Parameters:
      addr - instruction address
      varid - variable id
      Returns:
      true if a use discrepancy exists

    • 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 - true if reaching out is considered a use
      maxBlocks - optional maximum block count
      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 - true if reaching out is considered a use
      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)
      Check whether a defined variable has a single use.
      Parameters:
      addr - instruction address
      varid - variable id
      Returns:
      single use address, or null

    • checkSingleUse

      default boolean checkSingleUse(long addr, int varid, long expectedUseAddress)
      Check whether a defined variable has a specific single use.
      Parameters:
      addr - instruction address
      varid - variable id
      expectedUseAddress - expected use address
      Returns:
      true if the single use is the expected address

    • 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:
      single definition address, or null

    • 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:
      single definition address, or null

    • checkSingleDef

      default boolean checkSingleDef(long addr, int varid, long expectedDefAddress)
      Check whether a used variable has a specific single definition point.
      Parameters:
      addr - instruction address
      varid - variable id
      expectedDefAddress - expected definition address
      Returns:
      true if the single definition is the expected address

    • checkSingleSource

      Long checkSingleSource(long addr, int varid, boolean liveInIsDef)
      Check whether a variable has a single source.
      Parameters:
      addr - instruction address
      varid - variable id
      liveInIsDef - true if live-in variables are treated as definitions
      Returns:
      single source address, or null

    • checkSingleSource

      Long checkSingleSource(long addr, int varid)
      Check whether a variable has a single source.
      Parameters:
      addr - instruction address
      varid - variable id
      Returns:
      single source address, or null

    • checkSingleSource

      default boolean checkSingleSource(long addr, int varid, long expectedSourceAddress)
      Check whether a variable has a specific single source.
      Parameters:
      addr - instruction address
      varid - variable id
      expectedSourceAddress - expected source address
      Returns:
      true if the single source is the expected address

    • 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 - true to perform extended reachability checks
      maxBlocks - optional maximum count of blocks to be explored before failing
      Returns:
      success indicator; null means unknown