SandMark version 2.0


sandmark.obfuscate.boolsplitter.dcfg
Class FlowGraph

java.lang.Object
  |
  +--EDU.purdue.cs.bloat.util.Graph
        |
        +--sandmark.obfuscate.boolsplitter.dcfg.FlowGraph

public class FlowGraph
extends EDU.purdue.cs.bloat.util.Graph

FlowGraph constructs and represents a Control Flow Graph (CFG) used for analyzing a method. It consists of the basic blocks of a method.

See Also:
MethodEditor, Block

Nested Class Summary
(package private)  class FlowGraph.LoopNode
          A LoopNode is a node in the loop tree.
 
Nested classes inherited from class EDU.purdue.cs.bloat.util.Graph
 
Field Summary
 java.lang.String[] bool_types
           
(package private)  java.util.List catchBlocks
           
static boolean DB_GRAPHS
           
static boolean DEBUG
           
(package private)  int domEdgeModCount
           
(package private)  int file
           
(package private)  java.util.Map handlers
           
(package private)  Block iniBlock
           
(package private)  int loopEdgeModCount
           
(package private)  EDU.purdue.cs.bloat.util.Graph loopTree
           
(package private)  int maxLoopDepth
           
(package private)  EDU.purdue.cs.bloat.editor.MethodEditor method
           
(package private)  int next
           
static int PEEL_ALL_LOOPS
           
static int PEEL_LOOPS_LEVEL
           
static int PEEL_NO_LOOPS
           
static boolean PRINT_GRAPH
           
(package private)  Block snkBlock
           
(package private)  Block srcBlock
           
(package private)  java.util.Map subroutines
           
(package private)  java.util.Vector topo_order
           
(package private)  java.util.List trace
           
 
Fields inherited from class EDU.purdue.cs.bloat.util.Graph
edgeModCount, nodeModCount, removingEdge, removingNode, revRootEdgeModCount, rootEdgeModCount
 
Constructor Summary
FlowGraph(EDU.purdue.cs.bloat.editor.MethodEditor method)
          Constructor.
 
Method Summary
 void addEdge(EDU.purdue.cs.bloat.util.GraphNode src, EDU.purdue.cs.bloat.util.GraphNode dst)
          Adds an edge between two nodes in this graph.
 int blockType(Block block)
          Returns the type of a given block.
 java.util.List catchBlocks()
          Returns theBlocks in this CFG that begin exception handlers.
 java.util.Collection domChildren(Block block)
          Returns the blocks that a given block dominates.
 java.util.Collection domFrontier(Block block)
          Returns the dominance frontier of a given block.
 Block domParent(Block block)
          Returns the Block that dominates a given block.
 void genTopoOrder(Block block)
           
 java.util.Vector getTopoOrder()
           
 java.util.Collection handlers()
          Returns all of the Handler objects in this CFG.
 java.util.Map handlersMap()
          Returns A Map mapping the first block in an exception handler to its Handler object.
 Block init()
          Returns the initialization block.
 void initialize()
          Sets up the control flow graph.
 java.util.Collection iteratedDomFrontier(java.util.Collection blocks)
          Returns the iterated dominance frontiers for several basic blocks.
 java.util.Collection iteratedPdomFrontier(java.util.Collection blocks)
          Returns the iterated postdominance frontier for several basic blocks.
 Subroutine labelSub(EDU.purdue.cs.bloat.editor.Label label)
          Returns the Subroutine whose entry block is labeled by a given Label.
 int loopDepth(Block block)
          Returns the depth of the loop in which a block is contained.
 Block loopHeader(Block block)
          Returns the loop header of the loop containing a given block.
 int loopLevel(Block block)
          Returns the level of the loop containing a given block.
 EDU.purdue.cs.bloat.util.Graph loopTree()
          Returns the loop tree for the method modeled by this flow graph.
 int maxLoopDepth()
          Returns the maximum loop depth (also the maximum loop height) in the control flow graph.
 EDU.purdue.cs.bloat.editor.MethodEditor method()
          Returns the method editor for the method modeled by this graph.
 Block newBlock()
          Returns a new Block with the next available Label.
(package private)  Block newBlock(EDU.purdue.cs.bloat.editor.Label label)
          Creates a new Block starting with the specified Label.
 java.util.Collection pdomChildren(Block block)
          Returns the postdominator children of a given block.
 java.util.Collection pdomFrontier(Block block)
          Returns the postdominance frontier of a given block.
 Block pdomParent(Block block)
          Returns the postdominator parent of a given block.
 java.util.List postOrder()
          Returns the blocks in the flow graph sorted in post-order.
 java.util.List preOrder()
          Returns the blocks in the flow graph sorted in pre-order.
 void print()
           
 void print(java.io.PrintStream out)
           
 void print(java.io.PrintWriter out)
          Prints the graph.
 void printGraph()
           
 void printGraph(java.io.PrintStream out)
          Creates a graphical description of the CFG in the dot language.
 void printGraph(java.io.PrintWriter out)
           
 void printGraph(java.io.PrintWriter out, java.lang.String name)
           
 void removeEdge(EDU.purdue.cs.bloat.util.GraphNode v, EDU.purdue.cs.bloat.util.GraphNode w)
          Removes an edge from the graph and performs the necessary cleanup.
 void removeNode(java.lang.Object key)
          Removes a node (a Block) from the graph.
 void removeSub(Subroutine sub)
          Removes a subroutine from this method.
 java.util.Collection reverseRoots()
           
 java.util.Collection roots()
           
(package private)  void setSubEntry(Subroutine sub, Block entry)
          Set the entry in the mapping between subroutine entry Blocks and the Subroutines that they begin.
 Block sink()
          Returns the sink block.
 Block source()
          Returns the "Enter" block of this CFG.
 java.util.Collection subroutines()
          Returns all of the Subroutines in the method modeled by this FlowGraph.
 java.lang.String toString()
          Returns a brief textual description of this FlowGraph, namely the name of the method it represents.
 java.util.List trace()
          Returns the basic blocks contained in this CFG in trace order.
 void visit(TreeVisitor visitor)
           
 void visitChildren(TreeVisitor visitor)
          Visit each node (block) in this CFG in pre-order.
 
Methods inherited from class EDU.purdue.cs.bloat.util.Graph
addNode, getNode, hasEdge, hasNode, isAncestorToDescendent, keySet, nodes, postOrderIndex, preds, preOrderIndex, removeUnreachable, size, succs
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

PEEL_NO_LOOPS

public static final int PEEL_NO_LOOPS
See Also:
Constant Field Values

PEEL_ALL_LOOPS

public static final int PEEL_ALL_LOOPS
See Also:
Constant Field Values

PEEL_LOOPS_LEVEL

public static int PEEL_LOOPS_LEVEL

DEBUG

public static boolean DEBUG

DB_GRAPHS

public static boolean DB_GRAPHS

PRINT_GRAPH

public static boolean PRINT_GRAPH

method

EDU.purdue.cs.bloat.editor.MethodEditor method

subroutines

java.util.Map subroutines

catchBlocks

java.util.List catchBlocks

handlers

java.util.Map handlers

srcBlock

Block srcBlock

snkBlock

Block snkBlock

iniBlock

Block iniBlock

trace

java.util.List trace

loopTree

EDU.purdue.cs.bloat.util.Graph loopTree

domEdgeModCount

int domEdgeModCount

loopEdgeModCount

int loopEdgeModCount

maxLoopDepth

int maxLoopDepth

topo_order

java.util.Vector topo_order

bool_types

public java.lang.String[] bool_types

file

int file

next

int next
Constructor Detail

FlowGraph

public FlowGraph(EDU.purdue.cs.bloat.editor.MethodEditor method)
Constructor.

Parameters:
method - The method to create the CFG for.
Method Detail

maxLoopDepth

public int maxLoopDepth()
Returns the maximum loop depth (also the maximum loop height) in the control flow graph.


initialize

public void initialize()
Sets up the control flow graph. Computes the dominators and the dominance frontier, cleans up the tree, works with the loops, inserts stores to aid copy and constant propagation as well as code generation.


loopTree

public EDU.purdue.cs.bloat.util.Graph loopTree()
Returns the loop tree for the method modeled by this flow graph. The loop tree represents the nesting of the loops in a method. The procedure is at the root of the loop tree. Nested loops are represented by a parent and child relationship.


removeSub

public void removeSub(Subroutine sub)
Removes a subroutine from this method.

Parameters:
sub - The subroutine to remove.

addEdge

public void addEdge(EDU.purdue.cs.bloat.util.GraphNode src,
                    EDU.purdue.cs.bloat.util.GraphNode dst)
Adds an edge between two nodes in this graph.

Overrides:
addEdge in class EDU.purdue.cs.bloat.util.Graph
Parameters:
src - Node at which the edge originates.
dst - Node at which the edge terminates.

removeEdge

public void removeEdge(EDU.purdue.cs.bloat.util.GraphNode v,
                       EDU.purdue.cs.bloat.util.GraphNode w)
Removes an edge from the graph and performs the necessary cleanup.

Overrides:
removeEdge in class EDU.purdue.cs.bloat.util.Graph
Parameters:
v - Node at which edge to be removed originates.
w - Node at which edge to be removed terminates.

newBlock

public Block newBlock()
Returns a new Block with the next available Label.


newBlock

Block newBlock(EDU.purdue.cs.bloat.editor.Label label)
Creates a new Block starting with the specified Label. The Block is added to this FlowGraph using its label as its key.

Parameters:
label - The new Block's Label

labelSub

public Subroutine labelSub(EDU.purdue.cs.bloat.editor.Label label)
Returns the Subroutine whose entry block is labeled by a given Label.


setSubEntry

void setSubEntry(Subroutine sub,
                 Block entry)
Set the entry in the mapping between subroutine entry Blocks and the Subroutines that they begin. It also sets the Subroutine's entry block.

Parameters:
sub - The subroutine whose entry block is being set.
entry - The subroutine's entry Block.
See Also:
Subroutine.setEntry(sandmark.obfuscate.boolsplitter.dcfg.Block)

subroutines

public java.util.Collection subroutines()
Returns all of the Subroutines in the method modeled by this FlowGraph.


print

public void print(java.io.PrintStream out)

print

public void print(java.io.PrintWriter out)
Prints the graph.

Parameters:
out - The writer to which to print.

printGraph

public void printGraph()

print

public void print()

printGraph

public void printGraph(java.io.PrintStream out)
Creates a graphical description of the CFG in the dot language. The name of the generated file is the name of the method modeled by this CFG followed by a number and the ".dot" postfix. For more information about dot and tools that use it see:

http://www.research.att.com/sw/tools/graphviz/


printGraph

public void printGraph(java.io.PrintWriter out)

printGraph

public void printGraph(java.io.PrintWriter out,
                       java.lang.String name)

visitChildren

public void visitChildren(TreeVisitor visitor)
Visit each node (block) in this CFG in pre-order.


visit

public void visit(TreeVisitor visitor)

method

public EDU.purdue.cs.bloat.editor.MethodEditor method()
Returns the method editor for the method modeled by this graph.


genTopoOrder

public void genTopoOrder(Block block)

getTopoOrder

public java.util.Vector getTopoOrder()

trace

public java.util.List trace()
Returns the basic blocks contained in this CFG in trace order. Trace order implies that basic blocks that end with a conditional jump are followed by their false branch and, where possible, that blocks that end in an unconditional jump are followed by the block that is the target of the unconditional branch.

The trace does not contain the source and the sink blocks.

Returns:
The basic Blocks in this CFG.

source

public Block source()
Returns the "Enter" block of this CFG. That is, the block through which all paths enter.


init

public Block init()
Returns the initialization block.


sink

public Block sink()
Returns the sink block. That is, the block through which all paths exit.


iteratedDomFrontier

public java.util.Collection iteratedDomFrontier(java.util.Collection blocks)
Returns the iterated dominance frontiers for several basic blocks.

See Also:
Block.domFrontier

iteratedPdomFrontier

public java.util.Collection iteratedPdomFrontier(java.util.Collection blocks)
Returns the iterated postdominance frontier for several basic blocks.

See Also:
Block.pdomFrontier

roots

public java.util.Collection roots()
Overrides:
roots in class EDU.purdue.cs.bloat.util.Graph
Returns:
A Collection containing the root(s) of this FlowGraph. In this case there is only one root, so the Collection only contains the source block.

reverseRoots

public java.util.Collection reverseRoots()
Overrides:
reverseRoots in class EDU.purdue.cs.bloat.util.Graph
Returns:
A Collection containing only the sink block.
See Also:
roots()

removeNode

public void removeNode(java.lang.Object key)
Removes a node (a Block) from the graph.

Overrides:
removeNode in class EDU.purdue.cs.bloat.util.Graph
Parameters:
key - Block to remove

handlersMap

public java.util.Map handlersMap()
Returns A Map mapping the first block in an exception handler to its Handler object.

See Also:
Handler

handlers

public java.util.Collection handlers()
Returns all of the Handler objects in this CFG.


catchBlocks

public java.util.List catchBlocks()
Returns theBlocks in this CFG that begin exception handlers.


domChildren

public java.util.Collection domChildren(Block block)
Returns the blocks that a given block dominates.


domParent

public Block domParent(Block block)
Returns the Block that dominates a given block.


blockType

public int blockType(Block block)
Returns the type of a given block. A block's type is one of Block.NON_HEADER, Block.IRREDUCIBLE, or Block.REDUCIBLE.


loopDepth

public int loopDepth(Block block)
Returns the depth of the loop in which a block is contained. The block must be contained in a loop. The procedure has depth 0. A loop (while, for, etc.) at the procedure level has depth 1. Depth increases as loops are nested.

Parameters:
block - A block whose depth we are interested in.
See Also:
loopLevel(sandmark.obfuscate.boolsplitter.dcfg.Block)

loopLevel

public int loopLevel(Block block)
Returns the level of the loop containing a given block. The innermost loops have level 0. The level increases as you go outward to higher loop nestings. For any given loop, the level is the maximum possible.

 procedure()
 {
   // Depth 0, Level 2 (max possible)
   while()
   {
     // Depth 1, Level 1
     while()
     {
       // Depth 2, Level 0
     }
   }
   while()
   {
     // Depth 1, Level 0
   }
 }
 

Parameters:
block - A block whose loop level we want to know. This block must be contained in a loop.

loopHeader

public Block loopHeader(Block block)
Returns the loop header of the loop containing a given block. The loop header is the block that dominates all of the blocks in the loop.


preOrder

public java.util.List preOrder()
Returns the blocks in the flow graph sorted in pre-order.

Overrides:
preOrder in class EDU.purdue.cs.bloat.util.Graph

postOrder

public java.util.List postOrder()
Returns the blocks in the flow graph sorted in post-order.

Overrides:
postOrder in class EDU.purdue.cs.bloat.util.Graph

pdomChildren

public java.util.Collection pdomChildren(Block block)
Returns the postdominator children of a given block.

See Also:
Block.pdomChildren

pdomParent

public Block pdomParent(Block block)
Returns the postdominator parent of a given block.

See Also:
Block.pdomParent

domFrontier

public java.util.Collection domFrontier(Block block)
Returns the dominance frontier of a given block.

See Also:
Block.domFrontier

pdomFrontier

public java.util.Collection pdomFrontier(Block block)
Returns the postdominance frontier of a given block.

See Also:
Block.pdomFrontier

toString

public java.lang.String toString()
Returns a brief textual description of this FlowGraph, namely the name of the method it represents.

Overrides:
toString in class EDU.purdue.cs.bloat.util.Graph

SandMark version 2.0

Mon Jun 17 12:30:47 MST 2002