From 444c4bac0f0ccf262375e031f717fed9edea8580 Mon Sep 17 00:00:00 2001 From: chiba Date: Fri, 11 Nov 2011 17:00:43 +0000 Subject: [PATCH] added javassist.bytecode.analysis.ControlFlow git-svn-id: http://anonsvn.jboss.org/repos/javassist/trunk@599 30ef5769-5b8d-40dd-aea6-55b5d6557bb3 --- Readme.html | 2 +- src/main/javassist/CtClass.java | 2 +- .../bytecode/analysis/ControlFlow.java | 358 ++++++++++++++++++ .../bytecode/stackmap/BasicBlock.java | 18 +- .../bytecode/analysis/DomTreePrinter.java | 27 ++ 5 files changed, 396 insertions(+), 11 deletions(-) create mode 100644 src/main/javassist/bytecode/analysis/ControlFlow.java create mode 100644 src/test/test/javassist/bytecode/analysis/DomTreePrinter.java diff --git a/Readme.html b/Readme.html index 164a5547..19a65ff3 100644 --- a/Readme.html +++ b/Readme.html @@ -283,7 +283,7 @@ see javassist.Dump.

-version 3.16

-version 3.15 on July 8, 2011 diff --git a/src/main/javassist/CtClass.java b/src/main/javassist/CtClass.java index 166c8653..e168a059 100644 --- a/src/main/javassist/CtClass.java +++ b/src/main/javassist/CtClass.java @@ -53,7 +53,7 @@ public abstract class CtClass { /** * The version number of this release. */ - public static final String version = "3.15.0-GA"; + public static final String version = "3.16.0-GA"; /** * Prints the version number and the copyright notice. diff --git a/src/main/javassist/bytecode/analysis/ControlFlow.java b/src/main/javassist/bytecode/analysis/ControlFlow.java new file mode 100644 index 00000000..424884ba --- /dev/null +++ b/src/main/javassist/bytecode/analysis/ControlFlow.java @@ -0,0 +1,358 @@ +/* + * 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 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. + * + * @author Shigeru Chiba + */ +public class ControlFlow { + private CtClass clazz; + private MethodInfo methodInfo; + private Block[] basicBlocks; + private Frame[] frames; + + /** + * 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. + */ + public ControlFlow(CtClass ctclazz, MethodInfo minfo) throws BadBytecode { + clazz = ctclazz; + methodInfo = minfo; + frames = null; + basicBlocks = (Block[])new BasicBlock.Maker() { + protected BasicBlock makeBlock(int pos) { + return new Block(pos, methodInfo); + } + protected BasicBlock[] makeArray(int size) { + return new Block[size]; + } + }.make(minfo); + 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; + } + } + } + + /** + * Returns all the basic blocks in the method body. + * The first element is the root block of the dominator tree. + */ + public Block[] basicBlocks() { + dominatorTree(); + 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. + * + * @param pos the position. + */ + public Frame frameAt(int pos) throws BadBytecode { + if (frames == null) + frames = new Analyzer().analyze(clazz, methodInfo); + + return frames[pos]; + } + + /** + * Returns a dominator tree. + * + * @return the root node or null if the method is abstract. + */ + public Block dominatorTree() { + int size = basicBlocks.length; + if (size == 0) + return null; + + if (basicBlocks[0].parent == null) { + // a dominator tree has not been constructed. + boolean[] visited = new boolean[size]; + int[] distance = new int[size]; + for (int i = 0; i < size; i++) + visited[i] = false; + + basicBlocks[0].makeDepth1stTree(null, visited, 0, distance); + for (int i = 0; i < size; i++) + visited[i] = false; + + while (basicBlocks[0].makeDominatorTree(visited, distance)) + ; + + setChildren(size); + } + + return basicBlocks[0]; + } + + private void setChildren(int size) { + int[] nchildren = new int[size]; + for (int i = 0; i < size; i++) + nchildren[i] = 0; + + for (int i = 0; i < size; i++) { + Block p = basicBlocks[i].parent; + if (p != null) + nchildren[p.index]++; + } + + for (int i = 0; i < size; i++) + basicBlocks[i].children = new Block[nchildren[i]]; + + for (int i = 0; i < size; i++) + nchildren[i] = 0; + + for (int i = 0; i < size; i++) { + Block b = basicBlocks[i]; + Block p = b.parent; + if (p != null) + p.children[nchildren[p.index]++] = b; + } + } + + /** + * 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. + */ + public static class Block extends BasicBlock { + int index; + MethodInfo method; + Block[] entrances; + Block parent; // for a dominator tree + Block[] children; // for a dominator tree + + Block(int pos, MethodInfo minfo) { + super(pos); + parent = null; + method = minfo; + } + + protected void toString2(StringBuffer sbuf) { + super.toString2(sbuf); + sbuf.append(", incomping{"); + for (int i = 0; i < entrances.length; i++) + sbuf.append(entrances[i].position).append(", "); + + sbuf.append("}, dominator parent{"); + if (parent != null) + sbuf.append(parent.position); + + sbuf.append("}, children{"); + for (int i = 0; i < children.length; i++) + sbuf.append(children[i].position).append(", "); + sbuf.append("}"); + } + + /** + * Returns the position of this block in the array of + * basic blocks that the basicBlocks method + * returns. + * + * @see #basicBlocks() + */ + public int index() { return index; } + + /** + * Returns the position of the first instruction + * in this block. + */ + public int position() { return position; } + + /** + * Returns the length of this block. + * @return + */ + public int length() { return length; } + + /** + * Returns the number of the control paths entering this block. + */ + int incomings() { return incoming; } + + /** + * Returns the blocks 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. + */ + public int exits() { return exit == null ? 0 : exit.length; } + + /** + * 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 the number of the children of this block + * in the dominator tree. + */ + public int children() { return children.length; } + + /** + * Returns the n-th child of this block in the + * dominator tree. + * + * @param n an index in the array of children. + */ + public Block child(int n) { return children[n]; } + + /** + * Returns catch clauses that will catch an exception thrown + * in this block. + */ + public Catcher[] catchers() { + ArrayList catchers = new ArrayList(); + BasicBlock.Catch c = toCatch; + while (c != null) { + catchers.add(new Catcher(c)); + c = c.next; + } + + return (Catcher[])catchers.toArray(new Catcher[catchers.size()]); + } + + /* + * 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(Block caller, boolean[] visited, int counter, int[] distance) { + if (visited[index]) + return counter; + + visited[index] = true; + parent = caller; + if (exit == null) { + distance[index] = counter++; + return counter; + } + else + for (int i = 0; i < exit.length; i++) { + Block b = (Block)exit[i]; + counter = b.makeDepth1stTree(this, visited, counter, distance); + } + + distance[index] = counter++; + return counter; + } + + boolean makeDominatorTree(boolean[] visited, int[] distance) { + if (visited[index]) + return false; + + visited[index] = true; + boolean changed = false; + if (exit != null) + for (int i = 0; i < exit.length; i++) { + Block b = (Block)exit[i]; + if (b.makeDominatorTree(visited, distance)) + changed = true; + } + + for (int i = 0; i < entrances.length; i++) { + if (parent != null) { + Block a = getAncestor(parent, entrances[i], distance); + if (a != parent) { + parent = a; + changed = true; + } + } + } + + return changed; + } + + private Block getAncestor(Block b1, Block b2, int[] distance) { + while (b1 != b2) + if (distance[b1.index] < distance[b2.index]) + b1 = b1.parent; + else + b2 = b2.parent; + + return b1; + } + } + + /** + * 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. + */ + public Block block() { return node; } + + /** + * 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); + } + } +} diff --git a/src/main/javassist/bytecode/stackmap/BasicBlock.java b/src/main/javassist/bytecode/stackmap/BasicBlock.java index 8fe83d46..19a3dc07 100644 --- a/src/main/javassist/bytecode/stackmap/BasicBlock.java +++ b/src/main/javassist/bytecode/stackmap/BasicBlock.java @@ -27,11 +27,11 @@ import java.util.ArrayList; * non-branch instruction. */ public class BasicBlock { - public int position, length; - public int incoming; // the number of incoming branches. - public BasicBlock[] exit; // null if the block is a leaf. - public boolean stop; // true if the block ends with an unconditional jump. - public Catch toCatch; + protected int position, length; + protected int incoming; // the number of incoming branches. + protected BasicBlock[] exit; // null if the block is a leaf. + protected boolean stop; // true if the block ends with an unconditional jump. + protected Catch toCatch; protected BasicBlock(int pos) { position = pos; @@ -52,9 +52,9 @@ public class BasicBlock { } public static class Catch { - Catch next; - BasicBlock body; - int typeIndex; + public Catch next; + public BasicBlock body; + public int typeIndex; Catch(BasicBlock b, int i, Catch c) { body = b; typeIndex = i; @@ -97,7 +97,7 @@ public class BasicBlock { int position; BasicBlock block; BasicBlock[] jump; - boolean alwaysJmp; // true if a unconditional branch. + boolean alwaysJmp; // true if an unconditional branch. int size; // 0 unless the mark indicates RETURN etc. Catch catcher; diff --git a/src/test/test/javassist/bytecode/analysis/DomTreePrinter.java b/src/test/test/javassist/bytecode/analysis/DomTreePrinter.java new file mode 100644 index 00000000..f5418c50 --- /dev/null +++ b/src/test/test/javassist/bytecode/analysis/DomTreePrinter.java @@ -0,0 +1,27 @@ +package test.javassist.bytecode.analysis; + +import javassist.ClassPool; +import javassist.bytecode.analysis.ControlFlow; +import javassist.bytecode.analysis.ControlFlow.Block; + +public class DomTreePrinter { + public static void main(String[] args) throws Exception { + ClassPool pool = ClassPool.getDefault(); + ControlFlow cf = new ControlFlow(pool.get(args[0]).getDeclaredMethod(args[1])); + Block[] blocks = cf.basicBlocks(); + for (int i = 0; i < blocks.length; i++) + System.out.println(i + ": " + blocks[i]); + } + + public int dummy(int n, int[] array) { + for (int i = 0; i < n; i++) { + if (array[i] > 0) + break; + if (array[i] > -1) + continue; + array[0]++; + array[1]++; + } + return array[0]; + } +} -- 2.39.5