Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 1999 Patrice Pominville, Raja Vallee-Rai
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Lesser General Public
   * License as published by the Free Software Foundation; either
   * version 2.1 of the License, or (at your option) any later version.
   * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * Lesser General Public License for more details.
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  * Boston, MA 02111-1307, USA.
  * Modified by the Sable Research Group and others 1997-2003.  
  * See the 'credits' file distributed with Soot for the complete list of
  * contributors.  (Soot is distributed at
 package soot.toolkits.graph;
 import java.util.*;
 import soot.*;
 import soot.util.Chain;


Represents the control flow graph of a soot.Body at the basic block level. Each node of the graph is a Block while the edges represent the flow of control from one basic block to the next.

This is an abstract base class for different variants of BlockGraph, where the variants differ in how they analyze the control flow between individual units (represented by passing different variants of UnitGraph to the BlockGraph constructor) and in how they identify block leaders (represented by overriding BlockGraph's definition of computeLeaders().

 public abstract class BlockGraph implements DirectedGraph<Block
     protected Body mBody;
     protected Chain<UnitmUnits;
     protected List<BlockmBlocks;
     protected List<BlockmHeads = new ArrayList<Block>();
     protected List<BlockmTails = new ArrayList<Block>();

Create a BlockGraph representing at the basic block level the control flow specified, at the Unit level, by a given UnitGraph.

unitGraph A representation of the control flow at the level of individual soot.Units.
     protected BlockGraph(UnitGraph unitGraph
          = unitGraph.getBody();
          = .getUnits();
 	Set<Unitleaders = computeLeaders(unitGraph);


Utility method for computing the basic block leaders for a soot.Body, given its UnitGraph (i.e., the instructions which begin new basic blocks).

This implementation designates as basic block leaders :

  • Any Unit which has zero predecessors (e.g. the Unit following a return or unconditional branch) or more than one predecessor (e.g. a merge point).
  • Units which are the target of any branch (even if they have no other predecessors and the branch has no other successors, which is possible for the targets of unconditional branches or degenerate conditional branches which both branch and fall through to the same Unit).
  • All successors of any Unit which has more than one successor (this includes the successors of Units which may throw an exception that gets caught within the Body, as well the successors of conditional branches).
  • The first Unit in any Trap handler. (Strictly speaking, if unitGraph were a ExceptionalUnitGraph that included only a single unexceptional predecessor for some handler—because no trapped unit could possibly throw the exception that the handler catches, while the code preceding the handler fell through to the handler's code—then you could merge the handler into the predecessor's basic block; but such situations occur only in carefully contrived bytecode.)

unitGraph is the Unit-level CFG which is to be split into basic blocks.
the java.util.Set of soot.Units in unitGraph which are block leaders.
    protected Set<UnitcomputeLeaders(UnitGraph unitGraph) {
	Body body = unitGraph.getBody();
	if (body != ) {
	    throw new RuntimeException("BlockGraph.computeLeaders() called with a UnitGraph that doesn't match its mBody.");
        Set<Unitleaders = new HashSet<Unit>();
	// Trap handlers start new basic blocks, no matter how many
	// predecessors they have.
	Chain<Traptraps = body.getTraps();
	for (Iterator<TraptrapIt = traps.iterator(); trapIt.hasNext(); ) {
	    Trap trap =;
	for (Iterator<UnitunitIt = body.getUnits().iterator(); unitIt.hasNext(); ) {
	    Unit u =;
	    List<Unitpredecessors = unitGraph.getPredsOf(u);
	    int predCount = predecessors.size();
	    List<Unitsuccessors = unitGraph.getSuccsOf(u);
	    int succCount = successors.size();
	    if (predCount != 1) { // If predCount == 1 but the predecessor
		leaders.add(u);	  // is a branch, u will get added by that
	    }                     // branch's successor test.
	    if ((succCount > 1) || (u.branches())) {
		for (Iterator<Unitit = successors.iterator(); it.hasNext(); ) {
		    leaders.add((; // The cast is an
		}				   // assertion check.
	return leaders;


A utility method that does most of the work of constructing basic blocks, once the set of block leaders has been determined, and which designates the heads and tails of the graph.

BlockGraph provides an implementation of buildBlocks() which splits the soot.Units in unitGraph so that each Unit in the passed set of block leaders is the first unit in a block. It defines as heads the blocks which begin with Units which are heads in unitGraph, and defines as tails the blocks which end with Units which are tails in unitGraph. Subclasses might override this behavior.

leaders Contains Units which are to be block leaders.
unitGraph Provides information about the predecessors and successors of each Unit in the Body, for determining the predecessors and successors of each created Block.
a java.util.Map from soot.Units which begin or end a block to the block which contains them.
    protected Map<UnitBlockbuildBlocks(Set<UnitleadersUnitGraph unitGraph) {
	List<BlockblockList = new ArrayList<Block>(leaders.size());
	Map<UnitBlockunitToBlock = new HashMap<UnitBlock>(); // Maps head and tail units to 
					 // their blocks, for building
					 // predecessor and successor lists.
	Unit blockHead = null;
	int blockLength = 0;
	Iterator<UnitunitIt = .iterator();
	if (unitIt.hasNext()) {
	    blockHead =;
	    if (! leaders.contains(blockHead)) {
		throw new RuntimeException("BlockGraph: first unit not a leader!");
	Unit blockTail = blockHead;
	int indexInMethod = 0;
	while (unitIt.hasNext()) {
	    Unit u =;
	    if (leaders.contains(u)) {
		blockHead = u;
		blockLength = 0;
	    blockTail = u;
	if (blockLength > 0) {
	    // Add final block.
	// The underlying UnitGraph defines heads and tails.
	for (Iterator<Unitit = unitGraph.getHeads().iterator(); it.hasNext(); ) {
	    Unit headUnit = (;
	    Block headBlock = unitToBlock.get(headUnit);
	    if (headBlock.getHead() == headUnit) {
	    } else {
		throw new RuntimeException("BlockGraph(): head Unit is not the first unit in the corresponding Block!");
	for (Iterator<Unitit = unitGraph.getTails().iterator(); it.hasNext(); ) {
	    Unit tailUnit = (;
	    Block tailBlock = unitToBlock.get(tailUnit);
	    if (tailBlock.getTail() == tailUnit) {
	    } else {
		throw new RuntimeException("BlockGraph(): tail Unit is not the last unit in the corresponding Block!");
	for (Iterator<BlockblockIt = blockList.iterator(); blockIt.hasNext(); ) {
	    Block block =;
	    List<UnitpredUnits = unitGraph.getPredsOf(block.getHead());
	    List<BlockpredBlocks = new ArrayList<Block>(predUnits.size());
	    for (Iterator<UnitpredIt = predUnits.iterator(); predIt.hasNext(); ) {
		Unit predUnit =;
		Block predBlock = unitToBlock.get(predUnit);
		if (predBlock == null) {
		    throw new RuntimeException("BlockGraph(): block head mapped to null block!");
	    if (predBlocks.size() == 0) {
		// If the UnreachableCodeEliminator is not eliminating
		// unreachable handlers, then they will have no
		// predecessors, yet not be heads.
		/* if (! mHeads.contains(block)) {
		    throw new RuntimeException("Block with no predecessors is not a head!");
		    // Note that a block can be a head even if it has
		    // predecessors: a handler that might catch an exception
		    // thrown by the first Unit in the method.
	    } else {
		if (block.getHead() == .getFirst()) {
		    .add(block); // Make the first block a head
				       // even if the Body is one huge loop.
	    List<UnitsuccUnits = unitGraph.getSuccsOf(block.getTail());
	    List<BlocksuccBlocks = new ArrayList<Block>(succUnits.size());
	    for (Iterator<UnitsuccIt = succUnits.iterator(); succIt.hasNext(); ) {
		Unit succUnit =;
		Block succBlock = unitToBlock.get(succUnit);
		if (succBlock == null) {
		    throw new RuntimeException("BlockGraph(): block tail mapped to null block!");
	    if (succBlocks.size() == 0) {
		if (! .contains(block)) {
		    throw new RuntimeException("Block with no successors is not a tail!: " + block.toString());
		    // Note that a block can be a tail even if it has
		    // successors: a return that throws a caught exception.
	    } else {
	 = Collections.unmodifiableList(blockList);
	 = Collections.unmodifiableList();
	if (.size() == 0) {
	     = Collections.emptyList();
else {
	     = Collections.unmodifiableList();
	return unitToBlock;

A utility method which creates a new block and adds information about it to data structures used to build the graph.

head The first unit in the block.
tail The last unit in the block.
index The index of this block this soot.Body.
length The number of units in this block.
blockList The list of blocks for this method. addBlock() will add the newly created block to this list.
unitToBlock A map from units to blocks. addBlock() will add mappings from head and tail to the new block
    private void addBlock(Unit headUnit tailint indexint length
			  List<BlockblockListMap<UnitBlockunitToBlock) {
	Block block = new Block(headtailindexlengththis);
Returns the soot.Body this BlockGraph is derived from.

The soot.Body this BlockGraph is derived from.
    public Body getBody()
        return ;

Returns a list of the Blocks composing this graph.

A list of the blocks composing this graph in the same order as they partition underlying Body instance's unit chain.
See also:
    public List<BlockgetBlocks()
        return ;
    public String toString() {
        Iterator<Blockit = .iterator();
        StringBuffer buf = new StringBuffer();
        while(it.hasNext()) {
            Block someBlock =;
            buf.append(someBlock.toString() + '\n');
        return buf.toString();
    /* DirectedGraph implementation   */
    public List<BlockgetHeads()
        return ;
    public List<BlockgetTails()
	return ;
    public List<BlockgetPredsOf(Block b)
        return b.getPreds();
    public List<BlockgetSuccsOf(Block b)
        return b.getSuccs();
    public int size()
        return .size();
    public Iterator<Blockiterator()
        return .iterator();
New to GrepCode? Check out our FAQ X