http://www.javassist.org/: Javassist (JAVA programming ASSISTant) makes Java bytecode manipulation simple. It is a class library for editing bytecodes in Java. (Shigeru Chiba, www.javassist.org) 
/*
 * Javassist, a Java-bytecode translator toolkit.
 * Copyright (C) 1999- Shigeru Chiba. All Rights Reserved.
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License.  Alternatively, the contents of this file may be used under
 * the terms of the GNU Lesser General Public License Version 2.1 or later,
 * or the Apache License Version 2.0.
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 */

package javassist.bytecode.analysis;

import java.util.ArrayList;
import java.util.List;

import javassist.CtClass;
import javassist.CtMethod;
import javassist.bytecode.BadBytecode;
import javassist.bytecode.MethodInfo;
import javassist.bytecode.stackmap.BasicBlock;


Represents the control flow graph of a given method.

To obtain the control flow graph, do the following:


CtMethod m = ...
ControlFlow cf = new ControlFlow(m);
Block[] blocks = cf.basicBlocks();



blocks is an array of basic blocks in
that method body.


Author:Shigeru Chiba
See Also:
Since:3.16
/**
 * Represents the control flow graph of a given method.
 *
 * <p>To obtain the control flow graph, do the following:</p>
 *
 * <pre>CtMethod m = ...
 * ControlFlow cf = new ControlFlow(m);
 * Block[] blocks = cf.basicBlocks();
 * </pre>
 *
 * <p><code>blocks</code> is an array of basic blocks in
 * that method body.</p>
 *
 * @see javassist.CtMethod
 * @see Block
 * @see Frame
 * @see Analyzer
 * @author Shigeru Chiba
 * @since 3.16
 */
public class ControlFlow {
    private CtClass clazz;
    private MethodInfo methodInfo;
    private Block[] basicBlocks;
    private Frame[] frames;

    
Constructs a control-flow analyzer for the given method.

/**
     * Constructs a control-flow analyzer for the given method.
     */
    public ControlFlow(CtMethod method) throws BadBytecode {
        this(method.getDeclaringClass(), method.getMethodInfo2());
    }

    
Constructs a control-flow analyzer.

/**
     * Constructs a control-flow analyzer.
     */
    public ControlFlow(CtClass ctclazz, MethodInfo minfo) throws BadBytecode {
        clazz = ctclazz;
        methodInfo = minfo;
        frames = null;
        basicBlocks = (Block[])new BasicBlock.Maker() {
            @Override
            protected BasicBlock makeBlock(int pos) {
                return new Block(pos, methodInfo);
            }
            @Override
            protected BasicBlock[] makeArray(int size) {
                return new Block[size];
            }
        }.make(minfo);
        if (basicBlocks == null)
            basicBlocks = new Block[0];
        int size = basicBlocks.length;
        int[] counters = new int[size];
        for (int i = 0; i < size; i++) {
            Block b = basicBlocks[i];
            b.index = i;
            b.entrances = new Block[b.incomings()];
            counters[i] = 0;
        }

        for (int i = 0; i < size; i++) {
            Block b = basicBlocks[i];
            for (int k = 0; k < b.exits(); k++) {
                Block e = b.exit(k);
                e.entrances[counters[e.index]++] = b;
            }

            ControlFlow.Catcher[] catchers = b.catchers();
            for (int k = 0; k < catchers.length; k++) {
                Block catchBlock = catchers[k].node;
                catchBlock.entrances[counters[catchBlock.index]++] = b;
            }
        }
    }

    
Returns all the basic blocks in the method body.

Returns:an array of basic blocks, the array has length 0 if
the method doesn't have code.
/**
     * Returns all the basic blocks in the method body.
     *
     * @return an array of basic blocks, the array has length 0 if
     * the method doesn't have code.
     */
    public Block[] basicBlocks() {
        return basicBlocks;
    }

    
Returns the types of the local variables and stack frame entries
available at the given position.  If the byte at the position is
not the first byte of an instruction, then this method returns
null.

Params:
  • pos –       the position.
/**
     * Returns the types of the local variables and stack frame entries
     * available at the given position.  If the byte at the position is
     * not the first byte of an instruction, then this method returns
     * null.
     *
     * @param pos       the position.
     */
    public Frame frameAt(int pos) throws BadBytecode {
        if (frames == null)
            frames = new Analyzer().analyze(clazz, methodInfo);

        return frames[pos];
    }

    
Constructs a dominator tree.  This method returns an array of
the tree nodes.  The first element of the array is the root
of the tree.

 The order of the elements is the same as that
of the elements in the Block array returned
by the basicBlocks
method.  If a Block object is at the i-th position
in the Block array, then  
the Node object referring to that
Block object is at the i-th position in the
array returned by this method.
For every array element node, its index in the
array is equivalent to node.block().index(). 

See Also:
Returns:an array of the tree nodes, or null if the method doesn't have code.
/**
     * Constructs a dominator tree.  This method returns an array of
     * the tree nodes.  The first element of the array is the root
     * of the tree.
     * 
     * <p> The order of the elements is the same as that
     * of the elements in the <code>Block</code> array returned
     * by the <code>basicBlocks</code>
     * method.  If a <code>Block</code> object is at the i-th position
     * in the <code>Block</code> array, then  
     * the <code>Node</code> object referring to that
     * <code>Block</code> object is at the i-th position in the
     * array returned by this method.
     * For every array element <code>node</code>, its index in the
     * array is equivalent to <code>node.block().index()</code>. 
     *
     * @return an array of the tree nodes, or null if the method doesn't have code.
     * @see Node#block()
     * @see Block#index()
     */
    public Node[] dominatorTree() {
        int size = basicBlocks.length;
        if (size == 0)
            return null;

        Node[] nodes = new Node[size];
        boolean[] visited = new boolean[size];
        int[] distance = new int[size];
        for (int i = 0; i < size; i++) {
            nodes[i] = new Node(basicBlocks[i]);
            visited[i] = false;
        }

        Access access = new Access(nodes) {
            @Override
            BasicBlock[] exits(Node n) { return n.block.getExit(); }
            @Override
            BasicBlock[] entrances(Node n) { return n.block.entrances; }
        };
        nodes[0].makeDepth1stTree(null, visited, 0, distance, access);
        do {
            for (int i = 0; i < size; i++)
                visited[i] = false;
        } while (nodes[0].makeDominatorTree(visited, distance, access));
        Node.setChildren(nodes);
        return nodes;
    }

    
Constructs a post dominator tree.  This method returns an array of
the tree nodes.  Note that the tree has multiple roots.
The parent of the root nodes is null.

 The order of the elements is the same as that
of the elements in the Block array returned
by the basicBlocks
method.  If a Block object is at the i-th position
in the Block array, then  
the Node object referring to that
Block object is at the i-th position in the
array returned by this method.
For every array element node, its index in the
array is equivalent to node.block().index().

See Also:
Returns:an array of the tree nodes, or null if the method doesn't have code.
/**
     * Constructs a post dominator tree.  This method returns an array of
     * the tree nodes.  Note that the tree has multiple roots.
     * The parent of the root nodes is null.
     * 
     * <p> The order of the elements is the same as that
     * of the elements in the <code>Block</code> array returned
     * by the <code>basicBlocks</code>
     * method.  If a <code>Block</code> object is at the i-th position
     * in the <code>Block</code> array, then  
     * the <code>Node</code> object referring to that
     * <code>Block</code> object is at the i-th position in the
     * array returned by this method.
     * For every array element <code>node</code>, its index in the
     * array is equivalent to <code>node.block().index()</code>.
     *
     * @return an array of the tree nodes, or null if the method doesn't have code.
     * @see Node#block()
     * @see Block#index()
     */
    public Node[] postDominatorTree() {
        int size = basicBlocks.length;
        if (size == 0)
            return null;

        Node[] nodes = new Node[size];
        boolean[] visited = new boolean[size];
        int[] distance = new int[size];
        for (int i = 0; i < size; i++) {
            nodes[i] = new Node(basicBlocks[i]);
            visited[i] = false;
        }

        Access access = new Access(nodes) {
            @Override
            BasicBlock[] exits(Node n) { return n.block.entrances; }
            @Override
            BasicBlock[] entrances(Node n) { return n.block.getExit(); }
        };

        int counter = 0;
        for (int i = 0; i < size; i++)
            if (nodes[i].block.exits() == 0)
                counter = nodes[i].makeDepth1stTree(null, visited, counter, distance, access);

        boolean changed;
        do {
            for (int i = 0; i < size; i++)
                visited[i] = false;

            changed = false;
            for (int i = 0; i < size; i++)
                if (nodes[i].block.exits() == 0)
                    if (nodes[i].makeDominatorTree(visited, distance, access))
                        changed = true;
        } while (changed);

        Node.setChildren(nodes);
        return nodes;
    }

    
Basic block.
It is a sequence of contiguous instructions that do not contain
jump/branch instructions except the last one.
Since Java6 or later does not allow JSR,
we deal with JSR as a non-branch instruction.

/**
     * Basic block.
     * It is a sequence of contiguous instructions that do not contain
     * jump/branch instructions except the last one.
     * Since Java6 or later does not allow <code>JSR</code>,
     * we deal with <code>JSR</code> as a non-branch instruction.
     */
    public static class Block extends BasicBlock {
        
A field that can be freely used for storing extra data.
A client program of this control-flow analyzer can append
an additional attribute to a Block object.
The Javassist library never accesses this field.

/**
         * A field that can be freely used for storing extra data.
         * A client program of this control-flow analyzer can append
         * an additional attribute to a <code>Block</code> object.
         * The Javassist library never accesses this field.
         */
        public Object clientData = null;

        int index;
        MethodInfo method;
        Block[] entrances;

        Block(int pos, MethodInfo minfo) {
            super(pos);
            method = minfo;
        }

        @Override
        protected void toString2(StringBuffer sbuf) {
            super.toString2(sbuf);
            sbuf.append(", incoming{");
            for (int i = 0; i < entrances.length; i++)
                    sbuf.append(entrances[i].position).append(", ");

            sbuf.append("}");
        }

        BasicBlock[] getExit() { return exit; }

        
Returns the position of this block in the array of
basic blocks that the basicBlocks method
returns.

See Also:
  • basicBlocks()
/**
         * Returns the position of this block in the array of
         * basic blocks that the <code>basicBlocks</code> method
         * returns.
         *
         * @see #basicBlocks()
         */
        public int index() { return index; }

        
Returns the position of the first instruction
in this block.

/**
         * Returns the position of the first instruction
         * in this block.
         */
        public int position() { return position; }

        
Returns the length of this block.

/**
         * Returns the length of this block.
         */
        public int length() { return length; }

        
Returns the number of the control paths entering this block.

/**
         * Returns the number of the control paths entering this block.
         */
        public int incomings() { return incoming; }

        
Returns the block that the control may jump into this block from.

/**
         * Returns the block that the control may jump into this block from.
         */
        public Block incoming(int n) {
            return entrances[n];
        }

        
Return the number of the blocks that may be executed
after this block.

/**
         * Return the number of the blocks that may be executed
         * after this block.
         */
        public int exits() { return exit == null ? 0 : exit.length; }

        
Returns the n-th block that may be executed after this
block.

Params:
  • n –     an index in the array of exit blocks.
/**
         * Returns the n-th block that may be executed after this
         * block.
         *
         * @param n     an index in the array of exit blocks.
         */
        public Block exit(int n) { return (Block)exit[n]; }

        
Returns catch clauses that will catch an exception thrown
in this block. 

/**
         * Returns catch clauses that will catch an exception thrown
         * in this block. 
         */
        public Catcher[] catchers() {
            List<Catcher> catchers = new ArrayList<Catcher>();
            BasicBlock.Catch c = toCatch;
            while (c != null) {
                catchers.add(new Catcher(c));
                c = c.next;
            }

            return catchers.toArray(new Catcher[catchers.size()]);
        }
    }

    static abstract class Access {
        Node[] all;
        Access(Node[] nodes) { all = nodes; }
        Node node(BasicBlock b) { return all[((Block)b).index]; } 
        abstract BasicBlock[] exits(Node n);
        abstract BasicBlock[] entrances(Node n);
    }

    
A node of (post) dominator trees. 

/**
     * A node of (post) dominator trees. 
     */
    public static class Node {
        private Block block;
        private Node parent;
        private Node[] children;

        Node(Block b) {
            block = b;
            parent = null;
        }

        
Returns a String representation.

/**
         * Returns a <code>String</code> representation.
         */
        @Override
        public String toString() {
            StringBuffer sbuf = new StringBuffer();
            sbuf.append("Node[pos=").append(block().position());
            sbuf.append(", parent=");
            sbuf.append(parent == null ? "*" : Integer.toString(parent.block().position()));
            sbuf.append(", children{");
            for (int i = 0; i < children.length; i++)
                sbuf.append(children[i].block().position()).append(", ");

            sbuf.append("}]");
            return sbuf.toString();
        }

        
Returns the basic block indicated by this node.

/**
         * Returns the basic block indicated by this node.
         */
        public Block block() { return block; }

        
Returns the parent of this node.

/**
         * Returns the parent of this node.
         */
        public Node parent() { return parent; }

        
Returns the number of the children of this node.

/**
         * Returns the number of the children of this node.
         */
        public int children() { return children.length; }

        
Returns the n-th child of this node.
 

Params:
  • n –     an index in the array of children.
/**
         * Returns the n-th child of this node.
         *  
         * @param n     an index in the array of children.
         */
        public Node child(int n) { return children[n]; }

        /*
         * After executing this method, distance[] represents the post order of the tree nodes.
         * It also represents distances from the root; a bigger number represents a shorter
         * distance.  parent is set to its parent in the depth first spanning tree.
         */
        int makeDepth1stTree(Node caller, boolean[] visited, int counter, int[] distance, Access access) {
            int index = block.index;
            if (visited[index])
                return counter;

            visited[index] = true;
            parent = caller;
            BasicBlock[] exits = access.exits(this);
            if (exits != null)
                for (int i = 0; i < exits.length; i++) {
                    Node n = access.node(exits[i]);
                    counter = n.makeDepth1stTree(this, visited, counter, distance, access);
                }

            distance[index] = counter++;
            return counter;
        }

        boolean makeDominatorTree(boolean[] visited, int[] distance, Access access) {
            int index = block.index;
            if (visited[index])
                return false;

            visited[index] = true;
            boolean changed = false;
            BasicBlock[] exits = access.exits(this);
            if (exits != null)
                for (int i = 0; i < exits.length; i++) {
                    Node n = access.node(exits[i]);
                    if (n.makeDominatorTree(visited, distance, access))
                        changed = true;
                }

            BasicBlock[] entrances = access.entrances(this);
            if (entrances != null)
                for (int i = 0; i < entrances.length; i++) {
                    if (parent != null) {
                        Node n = getAncestor(parent, access.node(entrances[i]), distance);
                        if (n != parent) {
                            parent = n;
                            changed = true;
                        }
                    }
                }

            return changed;
        }

        private static Node getAncestor(Node n1, Node n2, int[] distance) {
            while (n1 != n2) {
                if (distance[n1.block.index] < distance[n2.block.index])
                    n1 = n1.parent;
                else
                    n2 = n2.parent;

                if (n1 == null || n2 == null)
                    return null;
            }

            return n1;
        }

        private static void setChildren(Node[] all) {
            int size = all.length;
            int[] nchildren = new int[size];
            for (int i = 0; i < size; i++)
                nchildren[i] = 0;

            for (int i = 0; i < size; i++) {
                Node p = all[i].parent;
                if (p != null)
                    nchildren[p.block.index]++;
            }

            for (int i = 0; i < size; i++)
                all[i].children = new Node[nchildren[i]];

            for (int i = 0; i < size; i++)
                nchildren[i] = 0;

            for (int i = 0; i < size; i++) {
                Node n = all[i];
                Node p = n.parent;
                if (p != null)
                    p.children[nchildren[p.block.index]++] = n;
            }
        }
    }

    
Represents a catch clause.

/**
     * Represents a catch clause.
     */
    public static class Catcher {
        private Block node;
        private int typeIndex;

        Catcher(BasicBlock.Catch c) {
            node = (Block)c.body;
            typeIndex = c.typeIndex;
        }

        
Returns the first block of the catch clause. 

/**
         * Returns the first block of the catch clause. 
         */
        public Block block() { return node; }

        
Returns the name of the exception type that
this catch clause catches.

/**
         * Returns the name of the exception type that
         * this catch clause catches.
         */
        public String type() {
            if (typeIndex == 0)
                return "java.lang.Throwable";
            else
                return node.method.getConstPool().getClassInfo(typeIndex);
        }
    }
}