Class CFG<InsnType extends IInstruction>
- Type Parameters:
InsnType
-
- All Implemented Interfaces:
IControlFlowGraph<InsnType,
,BasicBlock<InsnType>> Iterable<BasicBlock<InsnType>>
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:
- Via
CFG(long, List)
and providing a list of pre-parsedbasic blocks
. - Via
CFG(List, List)
and providing a flat list of instructions.
-
Field Summary
FieldsModifier and TypeFieldDescriptionint
long
static final int
This flag is used to indicate that blocks may legally end on instructions that are not terminators.static final int
This flag is used to indicate that the CFG may legally contain blocks not reachable from the entry-point.static final int
This flag is used to specify thatcall-to-subroutine
statements are not basic block terminators. -
Constructor Summary
ConstructorsConstructorDescriptionCFG
(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. -
Method Summary
Modifier and TypeMethodDescriptionvoid
addBlock
(int index, BasicBlock<InsnType> b) Insert a block, does nothing else.void
Add 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.boolean
TODO: Rename to connectIrregular() and SHOULD NOT USE.int
addIrregularEdge
(BasicBlock<InsnType> x, BasicBlock<InsnType> y, int index) Get an instruction-with-address iterator.Create a fresh DFA helper object.void
Remove all block edges.boolean
Delete one duplicate edge X->Y.boolean
deleteEdge
(BasicBlock<InsnType> x, BasicBlock<InsnType> y) Delete an edge x->y.int
deleteEdge
(BasicBlock<InsnType> x, BasicBlock<InsnType> y, int xToYPos) Delete an edge x->y.int
deleteEdges
(BasicBlock<InsnType> x, BasicBlock<InsnType> y) boolean
Delete an irregular edge x->y.int
deleteIrregularEdge
(BasicBlock<InsnType> x, BasicBlock<InsnType> y, int xToYPos) Delete an irregular edge x->y.int
void
Delete all irregular output edges for the provided block.void
Delete all regular output edges for the provided block.Perform data flow analysis on the CFG using standard DFA settings.doDataFlowAnalysis
(boolean redo) Perform data flow analysis on the CFG.doDataFlowAnalysis
(boolean redo, int varCollectionFlags) Perform data flow analysis on the CFG.doDataFlowAnalysis
(boolean redo, int varCollectionFlags, boolean integrateCalculatedInputRegisters) Perform data flow analysis on the CFG.findInstruction
(InsnType insn) Locate an instruction.format()
Format this CFG as an assembly-code listing.Format this CFG as an assembly-code listing.get
(int index) Retrieve a basic block.getAddressableInstruction
(long address) Get a complete map of the basic blocks and their addresses in the CFG.getBlock
(int index) getBlockAt
(long address) Get the basic block that starts at the provided address or offset.getBlockByLastAddress
(long lastAddress) getBlockContaining
(long address) Get the basic block that contains the provided address.getBlockEndingAt
(long address) Get the basic block that ends on the provided address.Get a copy of the block list of the CFG.Get a read-only view of the list of blocks for this CFG.Retrieve a list of all current data flow analyses.Retrieve a valid DFA object done with standard parameters (conservative, with inputs, no copies).getDataFlowAnalysis
(int varCollectionFlags, boolean integrateCalculatedInputRegisters) Retrieve a valid DFA object matching the provided parameters.int
Note that the initial value is set toIDFA.STANDARD_COLLECTION_FLAGS
.int
Calculate the 'effective' size of this CFG, that is, the sum of the size of each basic block.long
Routine highest address (exclusive).long
Routine entry-point address.Get the entry block.Get the ordered list of exit blocks.long
Routine lowest address (inclusive).int
getFlags()
Get the CFG flags.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.getInstruction
(long address) Get the instruction located at the exact address.int
Get the total number of instructions in the CFG.getInstructionLocation
(long address) Locate an instruction.Locate an instruction.Get the instruction list of this CFG by aggregating each instruction of every block.Get the map of addresses to instructions that compose this CFG.long
Routine highest address (inclusive).Retrieve the current variable information provider.boolean
hasExit()
Determine if this CFG has exit blocks, that is, blocks without out-edges.boolean
Determine if this CFG does not have any exit block.Get an indexed-block iterator.int
Get an instruction iterator.void
Invalidate all previously performed data flow analyses.void
invalidateDataFlowAnalysis
(long addressOfInstructionChange) Partially invalidate data flow analyses.boolean
Note that the initial value is set toIDFA.STANDARD_INTEGRATE_INPUTS
.iterator()
Get a block iterator.int
reconnectEdge
(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z) This method reconnects a block x from y to z, i.e.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
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
void
Remove a block, and update the fixtures.int
Remove all blocks not reachable from the entry-point.int
removeUnreachableBlocks
(boolean forced) Remove all blocks not reachable from the entry-point.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.int
setDFADefaultCollectionFlags
(int collectionFlags) Note that the initial value is set toIDFA.STANDARD_COLLECTION_FLAGS
.boolean
setDFADefaultIntegrateInputs
(boolean integrateInputs) Note that the initial value is set toIDFA.STANDARD_INTEGRATE_INPUTS
.void
Set an optional timer verifier that will be checked during long operations, including DFA computations.Set the variable information provider.shallowCopy
(boolean copyBlockReferences) Perform a shallow duplication of a CFG:
- Block references are optionally copied
- DFA data is not copiedint
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.splitBlock
(BasicBlock<InsnType> b, int index) Split a block into two blocks.toString()
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Field Details
-
FLAG_SUBROUTINE_CALL_NOT_BREAKING
public static final int FLAG_SUBROUTINE_CALL_NOT_BREAKINGThis flag is used to specify thatcall-to-subroutine
statements are not basic block terminators.- See Also:
-
FLAG_ALLOW_ARTIFICIAL_BLOCK_END
public static final int FLAG_ALLOW_ARTIFICIAL_BLOCK_ENDThis flag is used to indicate that blocks may legally end on instructions that are not terminators.- See Also:
-
FLAG_ALLOW_UNREACHABLE_BLOCKS
public static final int FLAG_ALLOW_UNREACHABLE_BLOCKSThis flag is used to indicate that the CFG may legally contain blocks not reachable from the entry-point.- See Also:
-
dfaTotalCount
public int dfaTotalCount -
dfaTotalTimeMs
public long dfaTotalTimeMs
-
-
Constructor Details
-
CFG
Create a standard CFG using a pre-constructed list of basic blocks.- Parameters:
entry
-blocks
-
-
CFG
Convenience constructor. Same asCFG(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
-
CFG
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 informationaugmenter
- optional instruction augmenterbase
- routine base addressentry
- routine entry-point addressflags
- parsing flags, seeFLAG_xxx
constants
-
CFG
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-instructionsirrdata
- irregular control flow informationaugmenter
- optional instruction augmenterentry
- routine entry-point addressflags
- parsing flags, seeFLAG_xxx
constants
-
-
Method Details
-
shallowCopy
Perform a shallow duplication of a CFG:
- Block references are optionally copied
- DFA data is not copied- Parameters:
copyBlockReferences
-- Returns:
- a new CFG
-
getFlags
public int getFlags()Get the CFG flags. SeeFLAG_xxx
in this class.- Returns:
- flags
-
get
Description copied from interface:IControlFlowGraph
Retrieve a basic block.- Specified by:
get
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
-
indexOf
- Specified by:
indexOf
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
-
size
public int size()Description copied from interface:IControlFlowGraph
Get the number of blocks.- Specified by:
size
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
-
getEntryAddress
public long getEntryAddress()Description copied from interface:IControlFlowGraph
Routine entry-point address. Note that this address may not be the lowest one in the CFG.- Specified by:
getEntryAddress
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
- the address of the entry block
-
getFirstAddress
public long getFirstAddress()Description copied from interface:IControlFlowGraph
Routine lowest address (inclusive). Note that this address may not be the entry-point address for this routine.- Specified by:
getFirstAddress
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
-
getLastAddress
public long getLastAddress()Description copied from interface:IControlFlowGraph
Routine highest address (inclusive).- Specified by:
getLastAddress
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
-
getEndAddress
public long getEndAddress()Description copied from interface:IControlFlowGraph
Routine highest address (exclusive).- Specified by:
getEndAddress
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
-
getEffectiveSize
public int getEffectiveSize()Description copied from interface:IControlFlowGraph
Calculate the 'effective' size of this CFG, that is, the sum of the size of each basic block.- Specified by:
getEffectiveSize
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
- the CFG size
-
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
-
getBlock
- Specified by:
getBlock
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
-
getBlocks
Description copied from interface:IControlFlowGraph
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.- Specified by:
getBlocks
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
- a copy of the list of blocks
-
getBlocksView
Description copied from interface:IControlFlowGraph
Get a read-only view of the list of blocks for this CFG. The list is ordered by ascending block address.- Specified by:
getBlocksView
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
- the list of blocks
-
getBlockAt
Description copied from interface:IControlFlowGraph
Get the basic block that starts at the provided address or offset.- Specified by:
getBlockAt
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Parameters:
address
- the block address/offset- Returns:
- basic block, or null if none starts at that address
-
getBlockEndingAt
Description copied from interface:IControlFlowGraph
Get the basic block that ends on the provided address.- Specified by:
getBlockEndingAt
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Parameters:
address
- wanted block end address (exclusive)- Returns:
- basic block, or null if none ends at that address
-
getBlockContaining
Description copied from interface:IControlFlowGraph
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
- Specified by:
getBlockContaining
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Parameters:
address
- an address within the block- Returns:
-
getEntryBlock
Description copied from interface:IControlFlowGraph
Get the entry block. The entry block is unique.- Specified by:
getEntryBlock
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
- never null; the method throws on error
-
getExitBlocks
Description copied from interface:IControlFlowGraph
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.- Specified by:
getExitBlocks
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
- a collection of blocks, possibly empty
-
getBlockByLastAddress
- Specified by:
getBlockByLastAddress
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
-
hasExit
public boolean hasExit()Determine if this CFG has exit blocks, that is, blocks without out-edges.- Returns:
-
hasNoExit
public boolean hasNoExit()Determine if this CFG does not have any exit block.- Returns:
-
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 ofgetBlockAt(int)
are to be made.- Returns:
- a map of address to block
-
getInstructions
Description copied from interface:IControlFlowGraph
Get the instruction list of this CFG by aggregating each instruction of every block. The list is ordered by ascending address/offset.- Specified by:
getInstructions
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
-
getInstructionsMap
Get the map of addresses to instructions that compose this CFG.- Returns:
-
getInstructionCount
public int getInstructionCount()Description copied from interface:IControlFlowGraph
Get the total number of instructions in the CFG. This method sums the number of instructions of each block of the CFG.- Specified by:
getInstructionCount
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
-
getInstruction
Description copied from interface:IControlFlowGraph
Get the instruction located at the exact address.- Specified by:
getInstruction
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
- an instruction, null if none
-
getAddressableInstruction
-
findInstruction
Locate an instruction.- Parameters:
insn
-- Returns:
-
getInstructionLocation
Locate an instruction.- Parameters:
insn
-- Returns:
-
getInstructionLocation
Description copied from interface:IControlFlowGraph
Locate an instruction.- Specified by:
getInstructionLocation
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Parameters:
address
- instruction address- Returns:
- a couple (basic block, instruction index within that block); null on error
-
getGraphRepresentation
Description copied from interface:IControlFlowGraph
Get the a graph representation of the CFG. The list of edges use a 1-based node numbering scheme.- Specified by:
getGraphRepresentation
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Parameters:
edges
- (output) array of regular edges, eg: {{1,2},{1,3},{2,3}}irregularEdges
- (output) array of irregular edges
-
simplify
public int simplify()Merge consecutive blocks that can be safely merged.- Returns:
-
simplify
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
IInstruction.getBreakingFlow(long)
andIInstruction.getRoutineCall(long)
to determine block ends.- Parameters:
mergeOnCalls
- if true, this optimization will merge blocks ending by a call to a sub-routinemergeOnJumps
- if true, this optimization will merge blocks ending by a simple branching instructionmergeNonConsecutive
- 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
-
removeBlock
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
-
splitBlock
Split a block into two blocks.- Parameters:
b
- block to splitindex
- 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
-
addBlock
Insert a block, does nothing else. The block is not connected, it is up to client code to connect it.- Parameters:
b
-
-
addBlock
Add a block, does nothing else. The block is not connected, it is up to client code to connect it.- Parameters:
b
-
-
addEdge
TODO: rename to connect() and SHOULD NOT USE. This method does nothing if such an edge already exists.- Parameters:
x
-y
-- Returns:
- true if an edge was added, false if one already existed
-
addEdge
Add a regular edge X->Y.- Parameters:
x
- source blocky
- destination blockindex
-- Returns:
- the updated number of edges x->y
-
addIrregularEdge
TODO: Rename to connectIrregular() and SHOULD NOT USE.- Parameters:
x
-y
-- Returns:
- true if an edge was added, false if one already existed
-
addIrregularEdge
- Parameters:
x
-y
-index
-- Returns:
- the updated number of irregular edges x->y
-
reconnectEdge
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)
. -
reconnectEdge
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 blocky
- original destination blockz
- new destination block; null to indicate that the edge x>y should be deletedxToYPos
- 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); if non-null, this method can introduce duplicate edges- 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
-
reconnectIrregularEdges
public int reconnectIrregularEdges(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z) - Parameters:
x
-y
-z
-- Returns:
-
reconnectIrregularEdge
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)
.- Parameters:
x
-y
-z
-- Returns:
-
reconnectIrregularEdge
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 blocky
- original destination blockz
- new destination block; null to indicate that the irregular edge x>y should be deletedxToYPos
- 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
-
deleteEdges
- Parameters:
x
-y
-- Returns:
- the number of deleted edges
-
deleteEdge
Delete an edge x->y. If duplicates exist, the first one in the list of out-edges deleted.- Parameters:
x
- source blocky
- destination block- Returns:
- true if x->y existed and was deleted
-
deleteEdge
Delete an edge x->y.- Parameters:
x
-y
-xToYPos
-- Returns:
-
deleteIrregularEdges
- Parameters:
x
-y
-- Returns:
-
deleteIrregularEdge
Delete an irregular edge x->y. If duplicates exist, the first one in the list of irrout-edges is deleted.- Parameters:
x
- source blocky
- destination block- Returns:
- true if x->y existed and was deleted
-
deleteIrregularEdge
Delete an irregular edge x->y.- Parameters:
x
-y
-xToYPos
-- Returns:
-
deleteOutEdges
Delete all regular output edges for the provided block.- Parameters:
b
- block
-
deleteIrregularOutEdges
Delete all irregular output edges for the provided block.- Parameters:
b
- block
-
deleteDuplicateEdge
Delete one duplicate edge X->Y.- Parameters:
x
- source blocky
- destination block- Returns:
- true if at least 2 edges x->y existed, and one was deleted
-
deleteAllEdges
public void deleteAllEdges()Remove all block edges. -
removeUnreachableBlocks
public int removeUnreachableBlocks()Remove all blocks not reachable from the entry-point.- Returns:
- count of removed blocks
-
removeUnreachableBlocks
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
-
replaceInstruction
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 addressinsn
- the instruction that will replace the instruction at the provided address- Returns:
- null on error, else the instruction that was replaced
-
replaceInstructionsInBlock
Replace a sequence of instructions contained in a single basic block.- Parameters:
address
- start address for replacementcnt
- number of instructions to be replacedinsns
- new instructions; the total size must be equal to the size of the instructions being replaced- Returns:
- success indicator
-
setVariableInformationProvider
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
-
getVariableInformationProvider
Retrieve the current variable information provider.- Returns:
- the provider, null if none was set
-
setTimedOperationVerifier
Set an optional timer verifier that will be checked during long operations, including DFA computations.- Parameters:
tov
-
-
getTimedOperationVerifier
- Returns:
-
getCurrentDFAs
Retrieve a list of all current data flow analyses.- Returns:
-
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
-
setDFADefaultCollectionFlags
public int setDFADefaultCollectionFlags(int collectionFlags) Note that the initial value is set toIDFA.STANDARD_COLLECTION_FLAGS
.- Returns:
- the previously set value
-
getDFADefaultCollectionFlags
public int getDFADefaultCollectionFlags()Note that the initial value is set toIDFA.STANDARD_COLLECTION_FLAGS
. -
setDFADefaultIntegrateInputs
public boolean setDFADefaultIntegrateInputs(boolean integrateInputs) Note that the initial value is set toIDFA.STANDARD_INTEGRATE_INPUTS
.- Returns:
- the previously set value
-
isDFADefaultIntegrateInputs
public boolean isDFADefaultIntegrateInputs()Note that the initial value is set toIDFA.STANDARD_INTEGRATE_INPUTS
. -
doDataFlowAnalysis
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
-
doDataFlowAnalysis
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 requiredvarCollectionFlags
- variable collection flags- Returns:
- a DFA object
-
doDataFlowAnalysis
public IDFA<InsnType> doDataFlowAnalysis(boolean redo, int varCollectionFlags, boolean integrateCalculatedInputRegisters) Perform data flow analysis on the CFG.- Parameters:
redo
- if true, force a new analysis even if one is not requiredvarCollectionFlags
- variable collection flagsintegrateCalculatedInputRegisters
- if true, the live registers determined after analysis will be integrated in the use-def chains- Returns:
- a DFA object
-
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
-
getDataFlowAnalysis
public IDFA<InsnType> getDataFlowAnalysis(int varCollectionFlags, boolean integrateCalculatedInputRegisters) Retrieve a valid DFA object matching the provided parameters.- Parameters:
varCollectionFlags
- variable collection flagsintegrateCalculatedInputRegisters
- if true, the live registers determined after analysis will be integrated in the use-def chains- Returns:
- a DFA object, null if no valid matching DFA object is retrieved
-
createDataFlowAnalysisHelperObject
Create a fresh DFA helper object. Clients should usedoDataFlowAnalysis()
methods instead of using this object directly.- Returns:
-
invalidateDataFlowAnalysis
public void invalidateDataFlowAnalysis()Invalidate all previously performed data flow analyses. This method can be used after a CFG modification that would render DFA objects obsoletes. -
invalidateDataFlowAnalysis
public void invalidateDataFlowAnalysis(long addressOfInstructionChange) Partially invalidate data flow analyses. This method can be used after modifying an instruction of the CFG.- Parameters:
addressOfInstructionChange
- address
-
formatInstructions
Format this CFG as an assembly-code listing.Consider using a
CFGFormatter
instead of this method.- Returns:
- the formatted CFG
-
format
Format this CFG as an assembly-code listing.Consider using a
CFGFormatter
instead of this method.- Returns:
- the formatted CFG
-
toString
-
iterator
Get a block iterator.- Specified by:
iterator
in interfaceIterable<InsnType extends IInstruction>
- Returns:
- an iterator (not supporting
remove
)
-
instructions
Description copied from interface:IControlFlowGraph
Get an instruction iterator. Also seeIControlFlowGraph.addressableInstructions()
.- Specified by:
instructions
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
- an iterator (not supporting
remove
)
-
addressableInstructions
Description copied from interface:IControlFlowGraph
Get an instruction-with-address iterator. Also seeIControlFlowGraph.instructions()
.- Specified by:
addressableInstructions
in interfaceIControlFlowGraph<InsnType extends IInstruction,
BasicBlock<InsnType extends IInstruction>> - Returns:
- an iterator (not supporting
remove
)
-
indexedBlocks
Get an indexed-block iterator.- Returns:
- an iterator providing basic blocks as well as their indices in the CFG
-