public class

CFG

extends Object
java.lang.Object
   ↳ com.pnfsoftware.jeb.core.units.code.controlflow.CFG<InsnType extends com.pnfsoftware.jeb.core.units.code.ILocatedInstruction>

Class Overview

This class represents a Control Flow Graph for a 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. Full chains contain more precise cross-block information.

There are two ways to build a CFG:

Summary

Public Constructors
CFG(List<BasicBlockBuilder<InsnType>> foetuses)
Create a CFG using a pre-computed list of partial basic block.
CFG(List<InsnType> insns, List<IrregularFlowData> irrdata)
Create a CFG by recursively parsing a list of instructions.
Protected Constructors
CFG()
Public Methods
boolean deleteEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
Delete a regular edge X->Y
Warning! The method throws if duplicate edges x->y are found.
void doDataFlowAnalysis()

Perform data flow analysis on the CFG.

void doDataFlowAnalysis(boolean redo)

Perform data flow analysis on the CFG.

String format(boolean format_addresses, int format_chains, Object context)
Format the CFG into a printable string.
String formatBlockInstruction(InsnType insn)
String formatBlockInstructions(BasicBlock<InsnType> bb)
String formatChains(InsnType insn, ChainType type)
String formatFullChains(InsnType insn, ChainType type)
String formatInstruction(InsnType insn)
String formatInstructions()
Format all the instructions (and their full chains) of a CFG into a printable string.
String formatInstructions(Collection<InsnType> insns)
Format a list of instructions and their associated full chains.
String formatInstructions2()
static <InsnType extends ILocatedInstruction> String formatRegisterToInsnCollection(Map<Integer, Set<InsnType>> m)
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.
BasicBlock<InsnType> getBlockAt(int address)
Get the basic block that starts at the provided address/offset.
BasicBlock<InsnType> getBlockFor(InsnType insn)
List<BasicBlock<InsnType>> getBlocks()
Get a copy of the block list of the CFG.
Map<InsnType, Map<Integer, List<Integer>>> getDefUseChains()
Retrieve the simple def-use chains.
Map<InsnType, Map<Integer, List<InsnType>>> getFullDefUseChains()
Retrieve the full def-use chains.
Map<InsnType, Map<Integer, List<InsnType>>> getFullUseDefChains()
Retrieve the full use-def chains.
void getGraphRepresentation(List<int[]> edges, List<int[]> irregular_edges)
Get the edges of the CFG.
InsnType getInstructionAt(int offset)
List<InsnType> getInstructions()
Get the instruction list by aggregating each instruction of every block.
Map<Integer, Set<InsnType>> getReachMap(InsnType insn)
Map<InsnType, Map<Integer, List<Integer>>> getUseDefChains()
Retrieve the simple use-def chains.
int reconnectEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z)
This method regularly reconnects a block X from Y to Z.
void removeBlock(BasicBlock<InsnType> b)

Remove a block, and update the fixtures.

void resetDFA()
int simplify()
Merge the blocks that can be merged, without changing the flow of the graph.
int simplifyIrregularFlows()
Merge blocks that can be merged, taking into accounts irregular flows.
int size()
Get the number of blocks.
String toString()
[Expand]
Inherited Methods
From class java.lang.Object

Public Constructors

public CFG (List<BasicBlockBuilder<InsnType>> foetuses)

Create a CFG using a pre-computed list of partial basic block.

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

Create a CFG by recursively parsing a list of instructions.

Parameters
insns list of instructions to be processed
irrdata (optional) irregular flow information, used for exception support

Protected Constructors

protected CFG ()

Public Methods

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

Delete a regular edge X->Y
Warning! The method throws if duplicate edges x->y are found.

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

public void doDataFlowAnalysis ()

Perform data flow analysis on the CFG.

Do NOT force a new analysis: Same as doDataFlowAnalysis(false).

public void doDataFlowAnalysis (boolean redo)

Perform data flow analysis on the CFG.

Parameters
redo force a new analysis

public String format (boolean format_addresses, int format_chains, Object context)

Format the CFG into a printable string.

Parameters
format_chains 0=no, 1=simple chains, 2=full chains

public String formatBlockInstruction (InsnType insn)

public String formatBlockInstructions (BasicBlock<InsnType> bb)

public String formatChains (InsnType insn, ChainType type)

public String formatFullChains (InsnType insn, ChainType type)

public String formatInstruction (InsnType insn)

public String formatInstructions ()

Format all the instructions (and their full chains) of a CFG into a printable string.

public String formatInstructions (Collection<InsnType> insns)

Format a list of instructions and their associated full chains.

public String formatInstructions2 ()

public static String formatRegisterToInsnCollection (Map<Integer, Set<InsnType>> m)

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->block

public BasicBlock<InsnType> getBlockAt (int address)

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

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

public BasicBlock<InsnType> getBlockFor (InsnType insn)

public List<BasicBlock<InsnType>> getBlocks ()

Get a copy of the block list of the CFG. The list is ordered by ascending offset.

public Map<InsnType, Map<Integer, List<Integer>>> getDefUseChains ()

Retrieve the simple def-use chains.

public Map<InsnType, Map<Integer, List<InsnType>>> getFullDefUseChains ()

Retrieve the full def-use chains.
This chain is the only one to have an extra key, set to null, which lists the registers defined 'outside' the routine and used throughout the routine, ie those which should be passed as parameters to the routine.
It is the caller's responsibility to check that these registers are indeed provided as parameters.

public Map<InsnType, Map<Integer, List<InsnType>>> getFullUseDefChains ()

Retrieve the full use-def chains.

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

Get the edges of the CFG. The nodes are numbered from 1 to n.

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

public InsnType getInstructionAt (int offset)

public List<InsnType> getInstructions ()

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

public Map<Integer, Set<InsnType>> getReachMap (InsnType insn)

public Map<InsnType, Map<Integer, List<Integer>>> getUseDefChains ()

Retrieve the simple use-def chains.

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

This method regularly reconnects a block X from Y to Z. (x->y becomes x->z)
Warning! The method throws if duplicate edges x->y are found.

Parameters
x the original source block
y the original destination block
z the new destination block
Returns
  • +1: success
    0: failure, x->y does not exist
    -1: failure, a edge x->z already exists, and duplicate edges are never allowed

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. However, when the CFG is optimized, instructions are removed, and some nodes might end up empty. This transient, stale state is fine AS LONG AS the client knows what it is doing and removes the empty block as soon as they're done, before passing it down the processing chain. This method removes empty blocks and updates the edges of connected and connecting blocks.

1st caveat: the empty block's out-degree or in-degree MUST be one. (Otherwise, stiching 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 an empty 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 void resetDFA ()

public int simplify ()

Merge the blocks that can be merged, without changing the flow of the graph.
Necessary conditions include: adjacent blocks, first block falls thru the second one, no block shall have irregular outputs, and only the first block may have irregular inputs. or contents of the nodes.

Returns
  • number of mergers

public int simplifyIrregularFlows ()

Merge blocks that can be merged, taking into accounts irregular flows.
A follow through may be merged with a block inside a try (with irregular outedges) if no instruction within the block can raise.

Returns
  • the number of simplifications performed

public int size ()

Get the number of blocks.

public String toString ()