public class

CFG

extends Object
implements IControlFlowGraph<InsnType extends IInstruction> Iterable<T>
java.lang.Object
   ↳ com.pnfsoftware.jeb.core.units.code.asm.cfg.CFG<InsnType extends com.pnfsoftware.jeb.core.units.code.IInstruction>

Class Overview

This class represents a Control Flow Graph for a routine/method, or more generally, any body of code. The CFG can be typed to handle specific instructions.

This class provides basic Data Flow Analysis support. A client can request simple and full du- and ud-chains. Simple chains are for intra-block use and reference instructions by index; Full chains contain precise cross-block information and reference instructions by address.

There are two ways to build a CFG:

Summary

Constants
int FLAG_ALLOW_ARTIFICIAL_BLOCK_END This flag is used to indicate that blocks may legally end on instructions that are not terminators.
int FLAG_ALLOW_UNREACHABLE_BLOCKS This flag is used to indicate that the CFG may legally contain blocks not reachable from the entry-point.
int FLAG_SUBROUTINE_CALL_NOT_BREAKING This flag is used to specify that call-to-subroutine statements are not basic block terminators.
Public Constructors
CFG(long entry, List<BasicBlock<InsnType>> blocks)
Create a standard CFG using a pre-constructed list of basic blocks.
CFG(List<? extends InsnType> insns, List<IrregularFlowData> irrdata)
Convenience constructor.
CFG(List<? extends InsnType> insns, List<IrregularFlowData> irrdata, IInstructionAugmenter augmenter, long base, long entry, int flags)
Create a CFG by recursively processing a list of sequential instructions.
CFG(Map<Long, InsnType> offsetToInsn, List<IrregularFlowData> irrdata, IInstructionAugmenter augmenter, long entry, int flags)
Create a CFG by recursively processing a collection of instructions.
Public Methods
void addBlock(BasicBlock<InsnType> b)
Add a block, does nothing else.
void addBlock(int index, BasicBlock<InsnType> b)
Insert a block, does nothing else.
boolean addEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
TODO: rename to connect() and SHOULD NOT USE.
int addEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, int index)
Add a regular edge X->Y.
int addIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, int index)
boolean addIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
TODO: Rename to connectIrregular() and SHOULD NOT USE.
Iterable<AddressableInstruction<InsnType>> addressableInstructions()
Get an instruction-with-address iterator.
DFA<InsnType> createDataFlowAnalysisHelperObject()
Create a fresh DFA helper object.
void deleteAllEdges()
Remove all block edges.
boolean deleteDuplicateEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
Delete one duplicate edge X->Y.
int deleteEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, int xToYPos)
Delete an edge x->y.
boolean deleteEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
Delete an edge x->y.
int deleteEdges(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
int deleteIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, int xToYPos)
Delete an irregular edge x->y.
boolean deleteIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
Delete an irregular edge x->y.
int deleteIrregularEdges(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
void deleteIrregularOutEdges(BasicBlock<InsnType> b)
Delete all irregular output edges for the provided block.
void deleteOutEdges(BasicBlock<InsnType> b)
Delete all regular output edges for the provided block.
DFA<InsnType> doDataFlowAnalysis(boolean redo, int varCollectionFlags, boolean integrateCalculatedInputRegisters, boolean cleanCopies)
Perform data flow analysis on the CFG.
DFA<InsnType> doDataFlowAnalysis(boolean redo, int varCollectionFlags)
Perform data flow analysis on the CFG.
DFA<InsnType> doDataFlowAnalysis()
Perform data flow analysis on the CFG using standard DFA settings.
DFA<InsnType> doDataFlowAnalysis(boolean redo)
Perform data flow analysis on the CFG.
DFA<InsnType> doDataFlowAnalysis(boolean redo, int varCollectionFlags, boolean integrateCalculatedInputRegisters)
Perform data flow analysis on the CFG.
AddressableInstruction<InsnType> findInstruction(InsnType insn)
Locate an instruction.
String format()
Format this CFG as an assembly-code listing.
String formatInstructions()
Format this CFG as an assembly-code listing.
BasicBlock<InsnType> get(int index)
Retrieve a basic block.
Map<Long, BasicBlock<InsnType>> getAddressBlockMap()
Get a complete map of the basic blocks and their addresses in the CFG.
IBasicBlock<InsnType> getBlock(int index)
BasicBlock<InsnType> getBlockAt(long base)
Get the basic block that starts at the provided address or offset.
BasicBlock<InsnType> getBlockByLastAddress(long lastAddress)
BasicBlock<InsnType> getBlockContaining(long address)
Get the basic block that contains the provided address.
BasicBlock<InsnType> getBlockEndingAt(long end)
List<BasicBlock<InsnType>> getBlocks()
Get a copy of the block list of the CFG.
List<BasicBlock<InsnType>> getBlocksView()
Get a read-only view of the list of blocks for this CFG.
List<DFA<InsnType>> getCurrentDFAs()
Retrieve a list of all current data flow analyses.
int getDFADefaultCollectionFlags()
Note that the initial value is set to #STANDARD_COLLECTION_FLAGS.
DFA<InsnType> getDataFlowAnalysis(int varCollectionFlags, boolean integrateCalculatedInputRegisters, boolean cleanCopies)
Retrieve a valid DFA object matching the provided parameters.
DFA<InsnType> getDataFlowAnalysis()
Retrieve a valid DFA object done with standard parameters (conservative, with inputs, no copies).
int getEffectiveSize()
Calculate the 'effective' size of this CFG, that is, the sum of the size of each basic block.
long getEndAddress()
Routine highest address (exclusive).
long getEntryAddress()
Routine entry-point address.
BasicBlock<InsnType> getEntryBlock()
Get the entry block.
List<BasicBlock<InsnType>> getExitBlocks()
Get the ordered list of exit blocks.
long getFirstAddress()
Routine lowest address (inclusive).
int getFlags()
Get the CFG flags.
List<Couple<Long, Long>> getGaps()
Get a list of gaps found in the routine CFG.
void getGraphRepresentation(List<int[]> edges, List<int[]> irregularEdges)
Get the a graph representation of the CFG.
InsnType getInstruction(long address)
Get the instruction located at the exact address.
int getInstructionCount()
Get the total number of instructions in the CFG.
Couple<BasicBlock<InsnType>, Integer> getInstructionLocation(long address)
Locate an instruction.
Couple<BasicBlock<InsnType>, Integer> getInstructionLocation(InsnType insn)
Locate an instruction.
List<InsnType> getInstructions()
Get the instruction list of this CFG by aggregating each instruction of every block.
Map<Long, InsnType> getInstructionsMap()
Get the map of addresses to instructions that compose this CFG.
long getLastAddress()
Routine highest address (inclusive).
TimedOperationVerifier getTimedOperationVerifier()
IVariableInformationProvider getVariableInformationProvider()
Retrieve the current variable information provider.
boolean hasExit()
Determine if this CFG has exit blocks, that is, blocks without out-edges.
boolean hasNoExit()
Determine if this CFG does not have any exit block.
int indexOf(IBasicBlock<InsnType> b)
Iterable<InsnType> instructions()
Get an instruction iterator.
void invalidateDataFlowAnalysis()
Invalidate all previously performed data flow analyses.
boolean isDFADefaultCleanCopies()
Note that the initial value is set to {@link #STANDARD_CLEAN_COPIES
boolean isDFADefaultIntegrateInputs()
Note that the initial value is set to #STANDARD_INTEGRATE_INPUTS.
Iterator<BasicBlock<InsnType>> iterator()
Get a block iterator.
int reconnectEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z, Integer xToYPos)
This method reconnects a block x from y to z, i.e.
int reconnectEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z)
This method reconnects a block x from y to z, i.e.
int reconnectEdges(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z)
int reconnectIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z)
This method irregularly reconnects a block x from y to z, i.e.
int reconnectIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z, Integer xToYPos)
This method irregularly reconnects a block x from y to z, i.e.
int reconnectIrregularEdges(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z)
void removeBlock(BasicBlock<InsnType> b)
Remove a block, and update the fixtures.
int removeUnreachableBlocks(boolean forced)
Remove all blocks not reachable from the entry-point.
int removeUnreachableBlocks()
Remove all blocks not reachable from the entry-point.
InsnType replaceInstruction(long address, InsnType insn)
Replace an instruction.
boolean replaceInstructionsInBlock(long address, int cnt, Collection<InsnType> insns)
Replace a sequence of instructions contained in a single basic block.
boolean setDFADefaultCleanCopies(boolean cleanCopies)
Note that the initial value is set to #STANDARD_CLEAN_COPIES.
int setDFADefaultCollectionFlags(int collectionFlags)
Note that the initial value is set to #STANDARD_COLLECTION_FLAGS.
boolean setDFADefaultIntegrateInputs(boolean integrateInputs)
Note that the initial value is set to #STANDARD_INTEGRATE_INPUTS.
void setTimedOperationVerifier(TimedOperationVerifier tov)
Set an optional timer verifier that will be checked during long operations, including DFA computations.
IVariableInformationProvider setVariableInformationProvider(IVariableInformationProvider prv)
Set the variable information provider.
CFG<InsnType> shallowCopy(boolean copyBlockReferences)
Perform a shallow duplication of a CFG:
- Block references are optionally copied
- DFA data is not copied
int simplify()
Merge consecutive blocks that can be safely merged.
int simplify(boolean mergeOnCalls, boolean mergeOnJumps, boolean mergeNonConsecutive)
Usage of this function is not recommended.
int size()
Get the number of blocks.
BasicBlock<InsnType> splitBlock(BasicBlock<InsnType> b, int index)
Split a block into two blocks.
String toString()
[Expand]
Inherited Methods
From class java.lang.Object
From interface com.pnfsoftware.jeb.core.units.code.IControlFlowGraph
From interface java.lang.Iterable

Constants

public static final int FLAG_ALLOW_ARTIFICIAL_BLOCK_END

This flag is used to indicate that blocks may legally end on instructions that are not terminators.

Constant Value: 2 (0x00000002)

public static final int FLAG_ALLOW_UNREACHABLE_BLOCKS

This flag is used to indicate that the CFG may legally contain blocks not reachable from the entry-point.

Constant Value: 4 (0x00000004)

public static final int FLAG_SUBROUTINE_CALL_NOT_BREAKING

This flag is used to specify that call-to-subroutine statements are not basic block terminators.

Constant Value: 1 (0x00000001)

Public Constructors

public CFG (long entry, List<BasicBlock<InsnType>> blocks)

Create a standard CFG using a pre-constructed list of basic blocks.

public CFG (List<? extends InsnType> insns, List<IrregularFlowData> irrdata)

Convenience constructor. Same as CFG(insns, irrdata, null, 0, 0, 0).

Parameters
insns list of sequential instructions; they must be contiguous (no gap), which means that the first instruction is at address `base`, the second at `base`+sizeofFirstInstruction, etc.
irrdata irregular control flow information

public CFG (List<? extends InsnType> insns, List<IrregularFlowData> irrdata, IInstructionAugmenter augmenter, long base, long entry, int flags)

Create a CFG by recursively processing a list of sequential instructions.

Delay-slot instruction sets are not supported by this constructor.

Parameters
insns list of sequential instructions; they must be contiguous (no gap), which means that the first instruction is at address `base`, the second at `base`+sizeofFirstInstruction, etc.
irrdata irregular control flow information
augmenter optional instruction augmenter
base routine base address
entry routine entry-point address
flags parsing flags, see FLAG_xxx constants

public CFG (Map<Long, InsnType> offsetToInsn, List<IrregularFlowData> irrdata, IInstructionAugmenter augmenter, long entry, int flags)

Create a CFG by recursively processing a collection of instructions.

Delay-slot instruction sets are not supported by this constructor.

Parameters
offsetToInsn map of address-to-instructions
irrdata irregular control flow information
augmenter optional instruction augmenter
entry routine entry-point address
flags parsing flags, see FLAG_xxx constants

Public Methods

public void addBlock (BasicBlock<InsnType> b)

Add a block, does nothing else. The block is not connected, it is up to client code to connect it.

public void addBlock (int index, BasicBlock<InsnType> b)

Insert a block, does nothing else. The block is not connected, it is up to client code to connect it.

public boolean addEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y)

TODO: rename to connect() and SHOULD NOT USE. This method does nothing if such an edge already exists.

Returns
  • true if an edge was added, false if one already existed

public int addEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y, int index)

Add a regular edge X->Y.

Parameters
x source block
y destination block
Returns
  • the updated number of edges x->y

public int addIrregularEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y, int index)

Returns
  • the updated number of irregular edges x->y

public boolean addIrregularEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y)

TODO: Rename to connectIrregular() and SHOULD NOT USE.

Returns
  • true if an edge was added, false if one already existed

public Iterable<AddressableInstruction<InsnType>> addressableInstructions ()

Get an instruction-with-address iterator. Also see instructions().

Returns
  • an iterator (not supporting remove)

public DFA<InsnType> createDataFlowAnalysisHelperObject ()

Create a fresh DFA helper object. Clients should use doDataFlowAnalysis() methods instead of using this object directly.

public void deleteAllEdges ()

Remove all block edges.

public boolean deleteDuplicateEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y)

Delete one duplicate edge X->Y.

Parameters
x source block
y destination block
Returns
  • true if at least 2 edges x->y existed, and one was deleted

public int deleteEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y, int xToYPos)

Delete an edge x->y.

public boolean deleteEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y)

Delete an edge x->y. If duplicates exist, the first one in the list of out-edges deleted.

Parameters
x source block
y destination block
Returns
  • true if x->y existed and was deleted

public int deleteEdges (BasicBlock<InsnType> x, BasicBlock<InsnType> y)

Returns
  • the number of deleted edges

public int deleteIrregularEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y, int xToYPos)

Delete an irregular edge x->y.

public boolean deleteIrregularEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y)

Delete an irregular edge x->y. If duplicates exist, the first one in the list of irrout-edges is deleted.

Parameters
x source block
y destination block
Returns
  • true if x->y existed and was deleted

public int deleteIrregularEdges (BasicBlock<InsnType> x, BasicBlock<InsnType> y)

public void deleteIrregularOutEdges (BasicBlock<InsnType> b)

Delete all irregular output edges for the provided block.

Parameters
b block

public void deleteOutEdges (BasicBlock<InsnType> b)

Delete all regular output edges for the provided block.

Parameters
b block

public DFA<InsnType> doDataFlowAnalysis (boolean redo, int varCollectionFlags, boolean integrateCalculatedInputRegisters, boolean cleanCopies)

Perform data flow analysis on the CFG.

Parameters
redo if true, force a new analysis even if one is not required
varCollectionFlags variable collection flags
integrateCalculatedInputRegisters if true, the live registers determined after analysis will be integrated in the use-def chains
Returns
  • a DFA object

public DFA<InsnType> doDataFlowAnalysis (boolean redo, int varCollectionFlags)

Perform data flow analysis on the CFG. Default settings are used if not specified.

Parameters
redo if true, force a new analysis even if one is not required
varCollectionFlags variable collection flags
Returns
  • a DFA object

public DFA<InsnType> doDataFlowAnalysis ()

Perform data flow analysis on the CFG using standard DFA settings. Input registers are integrated into the ud-chains. If possible, the analysis is conservative. Variable-copies are cleaned.

This method does not force a new analysis unless the settings of the last valid analysis do not match the required settings: it is the same as invoking doDataFlowAnalysis(false).

Returns
  • a DFA object

public DFA<InsnType> doDataFlowAnalysis (boolean redo)

Perform data flow analysis on the CFG. Default settings are used if not specified.

Parameters
redo if true, force a new analysis even if one is not required
Returns
  • a DFA object

public DFA<InsnType> doDataFlowAnalysis (boolean redo, int varCollectionFlags, boolean integrateCalculatedInputRegisters)

Perform data flow analysis on the CFG. Default settings are used if not specified.

Parameters
redo if true, force a new analysis even if one is not required
varCollectionFlags variable collection flags
integrateCalculatedInputRegisters if true, the live registers determined after analysis will be integrated in the use-def chains
Returns
  • a DFA object

public AddressableInstruction<InsnType> findInstruction (InsnType insn)

Locate an instruction.

public String format ()

Format this CFG as an assembly-code listing.

Consider using a CFGFormatter instead of this method.

Returns
  • the formatted CFG

public String formatInstructions ()

Format this CFG as an assembly-code listing.

Consider using a CFGFormatter instead of this method.

Returns
  • the formatted CFG

public BasicBlock<InsnType> get (int index)

Retrieve a basic block.

public Map<Long, BasicBlock<InsnType>> getAddressBlockMap ()

Get a complete map of the basic blocks and their addresses in the CFG. This method is recommended for use when multiple, repeated invocations of #getBlockAt(int) are to be made.

Returns
  • a map of address to block

public IBasicBlock<InsnType> getBlock (int index)

public BasicBlock<InsnType> getBlockAt (long base)

Get the basic block that starts at the provided address or offset.

Parameters
base the block address/offset
Returns
  • basic block, or null if none starts at that address

public BasicBlock<InsnType> getBlockByLastAddress (long lastAddress)

public BasicBlock<InsnType> getBlockContaining (long address)

Get the basic block that contains the provided address.

Note that the address just needs to be in the block address range; it does not need to point to the beginning of an instruction within the block

Parameters
address an address within the block

public BasicBlock<InsnType> getBlockEndingAt (long end)

public List<BasicBlock<InsnType>> getBlocks ()

Get a copy of the block list of the CFG. The list is ordered by ascending block address. Modifying the list does not impact the CFG.

Returns
  • a copy of the list of blocks

public List<BasicBlock<InsnType>> getBlocksView ()

Get a read-only view of the list of blocks for this CFG. The list is ordered by ascending block address.

Returns
  • the list of blocks

public List<DFA<InsnType>> getCurrentDFAs ()

Retrieve a list of all current data flow analyses.

public int getDFADefaultCollectionFlags ()

Note that the initial value is set to #STANDARD_COLLECTION_FLAGS.

public DFA<InsnType> getDataFlowAnalysis (int varCollectionFlags, boolean integrateCalculatedInputRegisters, boolean cleanCopies)

Retrieve a valid DFA object matching the provided parameters.

Parameters
varCollectionFlags variable collection flags
integrateCalculatedInputRegisters if true, the live registers determined after analysis will be integrated in the use-def chains
cleanCopies attempt to clean copy-variables (a var-info provider must have been provided)
Returns
  • a DFA object, null if no valid matching DFA object is retrieved

public DFA<InsnType> getDataFlowAnalysis ()

Retrieve a valid DFA object done with standard parameters (conservative, with inputs, no copies).

Returns
  • a DFA object, null if no valid matching DFA object is retrieved

public int getEffectiveSize ()

Calculate the 'effective' size of this CFG, that is, the sum of the size of each basic block.

Returns
  • the CFG size

public long getEndAddress ()

Routine highest address (exclusive).

public long getEntryAddress ()

Routine entry-point address. Note that this address may not be the lowest one in the CFG.

Returns
  • the address of the entry block

public BasicBlock<InsnType> getEntryBlock ()

Get the entry block. The entry block is unique.

Returns
  • never null; the method throws on error

public List<BasicBlock<InsnType>> getExitBlocks ()

Get the ordered list of exit blocks. A CFG may have zero or more exit blocks; CFG representing standard routines will have at least one (generally one) exit block.

Returns
  • a collection of blocks, possibly empty

public long getFirstAddress ()

Routine lowest address (inclusive). Note that this address may not be the entry-point address for this routine.

public int getFlags ()

Get the CFG flags. See FLAG_xxx in this class.

Returns
  • flags

public List<Couple<Long, Long>> getGaps ()

Get a list of gaps found in the routine CFG. Gaps are memory spaces between blocks that do not belong to the CFG itself.

Optimizing compilers and obfuscators can produce routines with gaps.

Returns
  • a list of address ranges [begin, end) of gaps

public void getGraphRepresentation (List<int[]> edges, List<int[]> irregularEdges)

Get the a graph representation of the CFG. The list of edges return use a 1-based node numbering scheme.

Parameters
edges (output) array of regular edges, eg: {{1,2},{1,3},{2,3}}
irregularEdges (output) array of irregular edges

public InsnType getInstruction (long address)

Get the instruction located at the exact address.

Returns
  • an instruction, null if none

public int getInstructionCount ()

Get the total number of instructions in the CFG. This method sums the number of instructions of each block of the CFG.

public Couple<BasicBlock<InsnType>, Integer> getInstructionLocation (long address)

Locate an instruction.

Parameters
address instruction address
Returns
  • a couple (basic block, instruction index within that block); null on error

public Couple<BasicBlock<InsnType>, Integer> getInstructionLocation (InsnType insn)

Locate an instruction.

public List<InsnType> getInstructions ()

Get the instruction list of this CFG by aggregating each instruction of every block. The list is ordered by ascending address/offset.

public Map<Long, InsnType> getInstructionsMap ()

Get the map of addresses to instructions that compose this CFG.

public long getLastAddress ()

Routine highest address (inclusive).

public TimedOperationVerifier getTimedOperationVerifier ()

public IVariableInformationProvider getVariableInformationProvider ()

Retrieve the current variable information provider.

Returns
  • the provider, null if none was set

public boolean hasExit ()

Determine if this CFG has exit blocks, that is, blocks without out-edges.

public boolean hasNoExit ()

Determine if this CFG does not have any exit block.

public int indexOf (IBasicBlock<InsnType> b)

public Iterable<InsnType> instructions ()

Get an instruction iterator. Also see addressableInstructions().

Returns
  • an iterator (not supporting remove)

public void invalidateDataFlowAnalysis ()

Invalidate all previously performed data flow analyses. This method can be used after a CFG modification that would have rendered chain data obsolete.

public boolean isDFADefaultCleanCopies ()

Note that the initial value is set to {@link #STANDARD_CLEAN_COPIES

public boolean isDFADefaultIntegrateInputs ()

Note that the initial value is set to #STANDARD_INTEGRATE_INPUTS.

public Iterator<BasicBlock<InsnType>> iterator ()

Get a block iterator.

Returns
  • an iterator (not supporting remove)

public int reconnectEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z, Integer xToYPos)

This method reconnects a block x from y to z, i.e. x->y becomes x->z. If z is null, this method deletes the edge x>y.

Parameters
x source block
y original destination block
z new destination block; null to indicate that the edge x>y should be deleted
xToYPos optional index specifying which x>y edge (if there are more than one) should be picked (this index is not an index into the full out-list of x); if null, this method will fail on duplicate edges (see return codes)
Returns
  • +1: success
    0: failure, x->y does not exist
    -1: failure, a edge x->z already exists, and duplicate edges are never allowed
    -2: failure, multiple edges x->y were found

public int reconnectEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z)

This method reconnects a block x from y to z, i.e. x->y becomes x->z. Duplicates edges are forbidden.

See reconnectEdge(BasicBlock, BasicBlock, BasicBlock, Integer).

public int reconnectEdges (BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z)

Returns
  • the number of reconnected edges

public int reconnectIrregularEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z)

This method irregularly reconnects a block x from y to z, i.e. x->y becomes x->z. Duplicates edges are forbidden.

See reconnectIrregularEdge(BasicBlock, BasicBlock, BasicBlock, Integer).

public int reconnectIrregularEdge (BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z, Integer xToYPos)

This method irregularly reconnects a block x from y to z, i.e. x->y becomes x->z. If z is null, this method deletes the irregular edge x>y.

Parameters
x source block
y original destination block
z new destination block; null to indicate that the irregular edge x>y should be deleted
xToYPos optional index specifying which x>y irregular edge (if there are more than one) should be picked (this index is not an index into the full irrout-list of x); if null, this method will fail on duplicate irregular edges (see return codes)
Returns
  • +1: success
    0: failure, x->y does not exist
    -1: failure, a edge x->z already exists, and duplicate irregular edges are never allowed
    -2: failure, multiple irregular edges x->y were found

public int reconnectIrregularEdges (BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z)

public void removeBlock (BasicBlock<InsnType> b)

Remove a block, and update the fixtures. This method is content-agnostic.

A CFG should never contain empty blocks or orphan blocks (no parents). However, when the CFG is optimized, instructions and edges are removed, and some nodes might end up empty or orphans. This transient, stale state is fine AS LONG AS the client knows what it is doing and removes the blocks as soon as they're done, before passing it down the processing chain. This method removes such blocks and updates the edges of connected and connecting blocks.

Caveats:

  • 1st caveat: the block's out-degree is one, OR the block's in-degree is one or zero. (Otherwise, stitching up the edges would not be possible.)
  • 2nd caveat: duplicate edges can be introduced. The client should remove them if it doesn't like that.
  • 3rd caveat: the fixtures update is instruction-agnostic. This means that the client is solely responsible regarding the decision to remove a block. For instance, the last instruction of the predecessor block should be checked and the client should make sure that removing the block and updating the fixtures is an operation compatible with the semantics of that last instruction.

Parameters
b block to be removed

public int removeUnreachableBlocks (boolean forced)

Remove all blocks not reachable from the entry-point.

If the CFG is composed of IResizableInstruction, instruction sizes may be adjusted to avoid the introduction of gaps between blocks.

Parameters
forced if true, unreachable blocks will be removed even if the CFG's flags specify that unreachable blocks are allowed
Returns
  • count of removed blocks

public int removeUnreachableBlocks ()

Remove all blocks not reachable from the entry-point.

Returns
  • count of removed blocks

public InsnType replaceInstruction (long address, InsnType insn)

Replace an instruction. An existing instruction must exist at the provided address. No adjustment is done (eg, the replaced instruction size is not modified). It is up to the caller to adjust the instruction in order to keep a valid CFG object.

Parameters
address the target address
insn the instruction that will replace the instruction at the provided address
Returns
  • null on error, else the instruction that was replaced

public boolean replaceInstructionsInBlock (long address, int cnt, Collection<InsnType> insns)

Replace a sequence of instructions contained in a single basic block.

Parameters
address start address for replacement
cnt number of instructions to be replaced
insns new instructions; the total size must be equal to the size of the instructions being replaced
Returns
  • success indicator

public boolean setDFADefaultCleanCopies (boolean cleanCopies)

Note that the initial value is set to #STANDARD_CLEAN_COPIES.

Returns
  • the previously set value

public int setDFADefaultCollectionFlags (int collectionFlags)

Note that the initial value is set to #STANDARD_COLLECTION_FLAGS.

Returns
  • the previously set value

public boolean setDFADefaultIntegrateInputs (boolean integrateInputs)

Note that the initial value is set to #STANDARD_INTEGRATE_INPUTS.

Returns
  • the previously set value

public void setTimedOperationVerifier (TimedOperationVerifier tov)

Set an optional timer verifier that will be checked during long operations, including DFA computations.

public IVariableInformationProvider setVariableInformationProvider (IVariableInformationProvider prv)

Set the variable information provider.

The provider is used by two components:
- The data flow analysis components: the provider is used to determine which variables are 'copies' of other variables, and can selectively block their propagation to avoid cluttering live-var data and reaching-var data (especially imporntant to have clean reaching -output information)
- The CFG formatter: when rendering a CFG with data chains: variables are rendered using their names instead of their ids

Parameters
prv Optional provider
Returns
  • the previous provider

public CFG<InsnType> shallowCopy (boolean copyBlockReferences)

Perform a shallow duplication of a CFG:
- Block references are optionally copied
- DFA data is not copied

Returns
  • a new CFG

public int simplify ()

Merge consecutive blocks that can be safely merged.

public int simplify (boolean mergeOnCalls, boolean mergeOnJumps, boolean mergeNonConsecutive)

Usage of this function is not recommended.

Merge the blocks that can be merged, without changing the flow of the graph. WATCH OUT! When merging with mergeOnCalls or mergeOnJumps set to true, the branching instructions are not removed from the merged blocks. It is the responsibility of the client to remove unnecessary branching instructions in those cases.

Necessary conditions include: adjacent blocks, first block falls thru the second one (possibly through two duplicate edges), no block shall have irregular outputs, and only the first block may have irregular inputs.

Data flow analysis: not used; invalidated (if simplifications were performed).

This method uses getBreakingFlow(long) and getRoutineCall(long) to determine block ends.

Parameters
mergeOnCalls if true, this optimization will merge blocks ending by a call to a sub-routine
mergeOnJumps if true, this optimization will merge blocks ending by a simple branching instruction
mergeNonConsecutive allow to merge non strictly consecutive blocks. There are some conditions to respect: the order must be correct, there must NOT exist a block between two consecutive blocks AND the second block must have no outblock. Be careful that there may remain a non-sense jump instruction and it must be necessary to add a jump to previously fallthrough address (caller has to manage it).
Returns
  • number of mergers performed

public int size ()

Get the number of blocks.

public BasicBlock<InsnType> splitBlock (BasicBlock<InsnType> b, int index)

Split a block into two blocks.

Parameters
b block to split
index index of the "split instruction" in the block; that instruction will be the first instruction of the newly-created block
Returns
  • the newly-created block

public String toString ()