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

Class CFGUtil

java.lang.Object

com.pnfsoftware.jeb.core.units.code.CFGUtil

public class CFGUtil
extends Object

Utility code for IControlFlowGraph.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	CFGUtil.BlockGroup	Given a start block A and an end block B, find the group of blocks G flowing from A to B, such that: 1) all blocks in G are reachable from A; 2) no blocks in G are reachable from B.
static class	CFGUtil.DotFileGenerator	GraphViz generator for CFG objects.
static class	CFGUtil.RegionFinder	This class attempts to determine a region in a graph.

Constructor Summary

Constructors

Constructor	Description
CFGUtil()

Method Summary

Modifier and Type	Method	Description
static boolean	canReach(IBasicBlock<? extends IInstruction> from, IBasicBlock<? extends IInstruction> to)	Determine whether a regular path exists between a source block and a destination block.
static boolean	canReach(IBasicBlock<? extends IInstruction> from, IBasicBlock<? extends IInstruction> to, boolean alsoFollowIrregularFlow)	Determine whether a path exists between a source block and a destination block.
static boolean	canReach(IBasicBlock<? extends IInstruction> from, IBasicBlock<? extends IInstruction> to, boolean alsoFollowIrregularFlow, Collection<IBasicBlock<? extends IInstruction>> stopperBlocks)	Determine whether a path exists between a source block and a destination block.
static int	countDeepInputs(IBasicBlock<? extends IInstruction> b, int maxdepth)	Count regular the number of top-level input blocks leading to the provided block.
static void	toDot(IControlFlowGraph<?,?> cfg, File file)	Build the CFG text representation using the dot language.
static void	toDot(IControlFlowGraph<?,?> cfg, File file, String title)	Build the CFG text representation using the dot language.
static void	toDot(IControlFlowGraph<?,?> cfg, File file, String title, Map<Long,String> blockHeaders)	Build the CFG text representation using the dot language.
static void	toDot(IControlFlowGraph<?,?> cfg, File file, String title, Map<Long,String> blockHeaders, int lineLimit)	Build the CFG text representation using the dot language.
static void	toTempDot(IControlFlowGraph<?,?> cfg, String name)
static void	toTempDot(IControlFlowGraph<?,?> cfg, String name, String title, Map<Long,String> blockHeaders, int lineLimit)
static void	verify(IControlFlowGraph<?,?> cfg)	Verification of a CFG.
static void	verify(IControlFlowGraph<?,?> cfg, boolean checkConnected, boolean checkGapless, boolean checkFlowinfo, boolean checkNoDupEdges, boolean checkNoDupIrregularEdges)	Verification of a CFG.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

CFGUtil

public CFGUtil()

Method Details

verify

public static void verify(IControlFlowGraph<?,?> cfg)

Verification of a CFG. Throws RuntimeException (or derived) on error.

Calls verify(IControlFlowGraph, boolean, boolean, boolean, boolean, boolean) with all optional checks enabled.

Parameters:

cfg - the CFG to be verified

Throws:

RuntimeException - if the verification failed

verify

public static void verify(IControlFlowGraph<?,?> cfg,
 boolean checkConnected,
 boolean checkGapless,
 boolean checkFlowinfo,
 boolean checkNoDupEdges,
 boolean checkNoDupIrregularEdges)

Verification of a CFG. Throws RuntimeException (or derived) on error.

This method checks the following:
- the graph is not empty
- no block is empty
- all blocks are reachable, either regularly or irregularly, from the entry node #0

Additional optional checks can be performed, see the parameters.

Parameters:

cfg - the CFG to be verified

checkConnected - if true, the graph is verified to be connected, i.e. all blocks must be reachable from the entry block

checkGapless - if true, the graph cannot have gaps between basic blocks

checkFlowinfo - if true, consistency checks between IInstruction.getBreakingFlow(long) and IBasicBlock.getOutputBlocks() are performed

checkNoDupEdges - if true, verify that CFG input/output regular edges of basic blocks do not contain duplicates

checkNoDupIrregularEdges - if true, verify that CFG input/output irregular edges of basic blocks do not contain duplicates

Throws:

RuntimeException - if the verification failed

toTempDot

public static void toTempDot(IControlFlowGraph<?,?> cfg,
 String name)

Parameters:

cfg -

name -

toTempDot

public static void toTempDot(IControlFlowGraph<?,?> cfg,
 String name,
 String title,
 Map<Long,String> blockHeaders,
 int lineLimit)

Parameters:

cfg -

name -

title -

blockHeaders -

toDot

public static void toDot(IControlFlowGraph<?,?> cfg,
 File file)
                  throws IOException

Build the CFG text representation using the dot language. To generate a PNG: dot out.dot -Tpng -o out.png

Parameters:

cfg -

file - output file

Throws:

IOException

toDot

public static void toDot(IControlFlowGraph<?,?> cfg,
 File file,
 String title)
                  throws IOException

Build the CFG text representation using the dot language. To generate a PNG: dot out.dot -Tpng -o out.png

Parameters:

cfg -

file - output file

title - optional graph title

Throws:

IOException

toDot

public static void toDot(IControlFlowGraph<?,?> cfg,
 File file,
 String title,
 Map<Long,String> blockHeaders)
                  throws IOException

Build the CFG text representation using the dot language. To generate a PNG: dot out.dot -Tpng -o out.png

Parameters:

cfg -

file - output file

title - optional graph title

blockHeaders - optional map of block headers (block_address -> block_description_string); if null, a standard header "(block_index)" is used

Throws:

IOException

toDot

public static void toDot(IControlFlowGraph<?,?> cfg,
 File file,
 String title,
 Map<Long,String> blockHeaders,
 int lineLimit)
                  throws IOException

Build the CFG text representation using the dot language. To generate a PNG: dot out.dot -Tpng -o out.png

Parameters:

cfg -

file -

title -

blockHeaders -

lineLimit -

Throws:

IOException

countDeepInputs

public static int countDeepInputs(IBasicBlock<? extends IInstruction> b,
 int maxdepth)

Count regular the number of top-level input blocks leading to the provided block.

Parameters:

b - the basic block to be examined

maxdepth - if less or equal than 1, this method is equivalent to IBasicBlock.insize()

Returns:

the number of inputs

canReach

public static boolean canReach(IBasicBlock<? extends IInstruction> from,
 IBasicBlock<? extends IInstruction> to)

Determine whether a regular path exists between a source block and a destination block. If both source and destination blocks are the same block B, the method returns true if B is part of a regular loop (i.e., a path exists from B to B). Exceptional flow (irregular edges) are disregarded.

Parameters:

from - source block

to - destination block

Returns:

true if a path exists between the source and the destination

canReach

public static boolean canReach(IBasicBlock<? extends IInstruction> from,
 IBasicBlock<? extends IInstruction> to,
 boolean alsoFollowIrregularFlow)

Determine whether a path exists between a source block and a destination block. If both source and destination blocks are the same block B, the method returns true if B is part of a loop (i.e., a path exists from B to B).

Parameters:

from - source block

to - destination block

alsoFollowIrregularFlow - if true, irregular control flow will also be followed

Returns:

true if a path exists between the source and the destination

canReach

public static boolean canReach(IBasicBlock<? extends IInstruction> from,
 IBasicBlock<? extends IInstruction> to,
 boolean alsoFollowIrregularFlow,
 Collection<IBasicBlock<? extends IInstruction>> stopperBlocks)

Determine whether a path exists between a source block and a destination block. If both source and destination blocks are the same block B, the method returns true if B is part of a loop (i.e., a path exists from B to B).

Parameters:

from - source block

to - destination block

alsoFollowIrregularFlow - if true, irregular control flow will also be followed

stopperBlocks -

Returns:

true if a path exists between the source and the destination