package jp.sourceforge.stigmata.birthmarks;\r
\r
import java.util.ArrayList;\r
+import java.util.Collections;\r
+import java.util.HashSet;\r
+import java.util.Iterator;\r
import java.util.List;\r
+import java.util.Set;\r
\r
+import org.objectweb.asm.Label;\r
import org.objectweb.asm.tree.AbstractInsnNode;\r
import org.objectweb.asm.tree.InsnNode;\r
\r
public class BasicBlock {\r
- private List<AbstractInsnNode> nodes = new ArrayList<AbstractInsnNode>();\r
+ private Set<BasicBlock> nexts = new HashSet<BasicBlock>();\r
+ private List<Opcode> opcodes = new ArrayList<Opcode>();\r
+ private Set<BasicBlock> prevs = new HashSet<BasicBlock>();\r
\r
BasicBlock(){\r
}\r
\r
public BasicBlock(InsnNode[] nodeArray){\r
for(InsnNode node: nodeArray){\r
- nodes.add(node);\r
+ addNode(node);\r
}\r
}\r
\r
void addNode(AbstractInsnNode node){\r
- nodes.add(node);\r
+ OpcodeManager manager = OpcodeManager.getInstance();\r
+ Opcode opcode = manager.getOpcode(node);\r
+ if(opcode != null){\r
+ addNode(opcode);\r
+ }\r
+ }\r
+\r
+ void addNode(Opcode opcode){\r
+ opcodes.add(opcode);\r
+ }\r
+\r
+ public Opcode getOpcode(int index){\r
+ return opcodes.get(index);\r
+ }\r
+\r
+ public int getSize(){\r
+ return opcodes.size();\r
+ }\r
+\r
+ public Label[] getTargets(){\r
+ Set<Label> targets = new HashSet<Label>();\r
+ for(Opcode opcode: opcodes){\r
+ if(opcode.getCategory() != Opcode.Category.TARGETER){\r
+ Label[] labels = opcode.getLabels();\r
+ for(Label label: labels){\r
+ targets.add(label);\r
+ }\r
+ }\r
+ }\r
+\r
+ return targets.toArray(new Label[targets.size()]);\r
+ }\r
+\r
+ public boolean hasLabel(Label label){\r
+ boolean flag = false;\r
+ for(Opcode opcode: opcodes){\r
+ if(flag || opcode.hasLabel(label)){\r
+ flag = true;\r
+ }\r
+ }\r
+ return flag;\r
+ }\r
+\r
+ public boolean isEmpty(){\r
+ return opcodes.size() == 0;\r
+ }\r
+\r
+ public Iterator<BasicBlock> nextIterator(){\r
+ return Collections.unmodifiableSet(nexts).iterator();\r
+ }\r
+\r
+ public Iterator<BasicBlock> previousIterator(){\r
+ return Collections.unmodifiableSet(prevs).iterator();\r
+ }\r
+\r
+ public void setNext(BasicBlock block){\r
+ block.prevs.add(this);\r
+ nexts.add(block);\r
+ }\r
+\r
+ public void setPrev(BasicBlock block){\r
+ block.nexts.add(this);\r
+ prevs.add(block);\r
+ }\r
+\r
+ /*\r
+ public String toString(){\r
+ StringBuilder sb = new StringBuilder("---- block ----");\r
+ String ln = System.getProperty("line.separator");\r
+ for(Opcode opcode: opcodes){\r
+ sb.append(ln).append(opcode);\r
+ }\r
+ Label[] targets = getTargets();\r
+ sb.append(ln).append("Targeter: ");\r
+ for(Label label: targets){\r
+ sb.append(label).append(", ");\r
+ }\r
+ return new String(sb);\r
}\r
+ */\r
}\r
\r
import java.util.ArrayList;\r
import java.util.HashSet;\r
+import java.util.Iterator;\r
import java.util.List;\r
import java.util.Set;\r
\r
+import org.objectweb.asm.Label;\r
import org.objectweb.asm.tree.AbstractInsnNode;\r
import org.objectweb.asm.tree.JumpInsnNode;\r
import org.objectweb.asm.tree.LabelNode;\r
import org.objectweb.asm.tree.TableSwitchInsnNode;\r
import org.objectweb.asm.tree.TryCatchBlockNode;\r
\r
+import com.sun.xml.internal.ws.org.objectweb.asm.Opcodes;\r
+\r
public class ControlFlowGraph {\r
private String name;\r
private boolean includeException;\r
parse(method);\r
}\r
\r
+ public int[][] getGraphMatrix(){\r
+ int[][] matrix = new int[blocks.length][blocks.length];\r
+\r
+ for(int i = 0; i < blocks.length; i++){\r
+ for(int j = 0; j < blocks.length; j++){\r
+ int nextValue = 0;\r
+ for(Iterator<BasicBlock> iter = blocks[i].nextIterator(); iter.hasNext(); ){\r
+ BasicBlock nextBlock = iter.next();\r
+ if(nextBlock == blocks[j]){\r
+ nextValue = 1;\r
+ break;\r
+ }\r
+ }\r
+ matrix[i][j] = nextValue;\r
+ }\r
+ }\r
+ return matrix;\r
+ }\r
+\r
public String getName(){\r
return name;\r
}\r
}\r
}\r
\r
- private void separateBasicBlock(MethodNode node){\r
+ private Set<LabelNode> collectLabels(MethodNode node){\r
Set<LabelNode> jumpedTarget = new HashSet<LabelNode>();\r
int size = node.instructions.size();\r
-\r
for(int i = 0; i < size; i++){\r
AbstractInsnNode inst = node.instructions.get(i);\r
switch(inst.getType()){\r
case AbstractInsnNode.JUMP_INSN:\r
- jumpedTarget.add(((JumpInsnNode)inst).label);\r
+ {\r
+ JumpInsnNode jump = (JumpInsnNode)inst;\r
+ jumpedTarget.add(jump.label);\r
break;\r
+ }\r
case AbstractInsnNode.LOOKUPSWITCH_INSN:\r
{\r
LookupSwitchInsnNode lookup = (LookupSwitchInsnNode)inst;\r
for(Object label: lookup.labels){\r
jumpedTarget.add((LabelNode)label);\r
}\r
+ break;\r
}\r
case AbstractInsnNode.TABLESWITCH_INSN:\r
{\r
for(Object label: lookup.labels){\r
jumpedTarget.add((LabelNode)label);\r
}\r
+ break;\r
}\r
}\r
}\r
jumpedTarget.add(((TryCatchBlockNode)object).handler);\r
}\r
}\r
+ return jumpedTarget;\r
+ }\r
+\r
+ private BasicBlock[] separateBasicBlock(MethodNode node, Set<LabelNode> jumpedTarget){\r
+ int size = node.instructions.size();\r
\r
List<BasicBlock> blockList = new ArrayList<BasicBlock>();\r
BasicBlock block = new BasicBlock();\r
for(int i = 0; i < size; i++){\r
AbstractInsnNode inst = node.instructions.get(i);\r
+\r
if(jumpedTarget.contains(inst)){\r
- blockList.add(block);\r
- block = new BasicBlock();\r
+ if(!block.isEmpty()){\r
+ blockList.add(block);\r
+ block = new BasicBlock();\r
+ }\r
}\r
-\r
block.addNode(inst);\r
-\r
if(inst.getType() == AbstractInsnNode.JUMP_INSN\r
|| inst.getType() == AbstractInsnNode.TABLESWITCH_INSN\r
|| inst.getType() == AbstractInsnNode.LOOKUPSWITCH_INSN){\r
- blockList.add(block);\r
- block = new BasicBlock();\r
+ if(!block.isEmpty()){\r
+ blockList.add(block);\r
+ BasicBlock block2 = new BasicBlock();\r
+ if(inst.getOpcode() != Opcodes.GOTO && inst.getOpcode() != Opcodes.JSR){\r
+ block2.setPrev(block);\r
+ }\r
+ block = block2;\r
+ }\r
}\r
}\r
- this.blocks = blockList.toArray(new BasicBlock[blockList.size()]);\r
+ blockList.add(block);\r
+ return blockList.toArray(new BasicBlock[blockList.size()]);\r
+ }\r
+\r
+ private BasicBlock[] joinBasicBlocks(BasicBlock[] blocks){\r
+ for(int i = 0; i < blocks.length; i++){\r
+ Label[] labels = blocks[i].getTargets();\r
+ for(int j = 0; j < labels.length; j++){\r
+ for(int k = 0; k < blocks.length; k++){\r
+ if(i != k && blocks[k].hasLabel(labels[j])){\r
+ blocks[i].setNext(blocks[k]);\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ if(labels.length == 0 && (i + 1) < blocks.length){\r
+ blocks[i].setNext(blocks[i + 1]);\r
+ }\r
+ }\r
+\r
+ return blocks;\r
}\r
\r
- /**\r
- * \83R\83\93\83g\83\8d\81[\83\8b\83t\83\8d\81[\83O\83\89\83t\82ð\8dì\90¬\82·\82é\81D\r
- */\r
private void parse(MethodNode node){\r
- separateBasicBlock(node);\r
+ Set<LabelNode> jumpedTarget = collectLabels(node);\r
+ BasicBlock[] blocks = separateBasicBlock(node, jumpedTarget);\r
+ this.blocks = joinBasicBlocks(blocks);\r
}\r
}\r
public class LabelOpcode extends Opcode{
private static final long serialVersionUID = -346783431316464L;
- private Label label;
-
public LabelOpcode(Label label){
super(-1, "targeter", 0, 0, Category.TARGETER);
- this.label = label;
+ super.addLabel(label);
+ }
+
+ @Override
+ public final void addLabel(Label label){
+ throw new NoSuchMethodError("illegal method call");
+ }
+
+ @Override
+ public final void setLabels(Label[] label){
+ throw new NoSuchMethodError("illegal method call");
}
public Label getLabel(){
- return label;
+ return getLabel(0);
}
}
* @author Haruaki Tamada
* @version $Revision$
*/
-public class Opcode implements Serializable{
+public class Opcode implements Serializable, Iterable<Label>{
private static final long serialVersionUID = -2349834745416345564L;
public static enum Category{
this.category = category;
}
- public int getOpcode(){
+ public final int getOpcode(){
return opcode;
}
- public String getName(){
+ public final String getName(){
return name;
}
if(label == null){
throw new NullPointerException();
}
- if(category != Category.BRANCH){
+ if(!(category == Category.TARGETER && labels.size() == 0)
+ && category != Category.BRANCH){
throw new IllegalStateException("this method allows only branch category");
}
labels.add(label);
}
}
+ public boolean hasLabel(Label label){
+ return labels.contains(label);
+ }
+
public Label getLabel(int index){
return labels.get(index);
}
- public Iterator<Label> labels(){
+ public synchronized Label[] getLabels(){
+ return labels.toArray(new Label[labels.size()]);
+ }
+
+ public Iterator<Label> iterator(){
return Collections.unmodifiableList(labels).iterator();
}
}
public String toString(){
- return String.format("%d:%s:%f(%s)", getOpcode(), getName(), getAct(), getCategory());
+ StringBuilder sb = new StringBuilder();
+ sb.append(String.format("%d:%s:%d(%s)", getOpcode(), getName(), getAct(), getCategory()));
+
+ if(getCategory() == Category.BRANCH || getCategory() == Category.TARGETER){
+ sb.append(labels);
+ }
+
+ return new String(sb);
}
}
@Override
public void visitFieldInsn(int opcode, String owner, String name, String desc){
- Opcode field = manager.getOpcode(opcode);
- Opcode o = new Opcode(field);
+ Opcode o = new Opcode(manager.getOpcode(opcode));
int size = Type.getType(desc).getSize();
switch(opcode){
case Opcodes.PUTFIELD:
@Override
public void visitJumpInsn(int opcode, Label label){
- Opcode o = manager.getOpcode(opcode);
+ Opcode o = new Opcode(manager.getOpcode(opcode));
o.addLabel(label);
opcodes.add(o);
super.visitJumpInsn(opcode, label);
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.net.URL;
+import java.util.ArrayList;
import java.util.HashMap;
+import java.util.List;
import java.util.Map;
import jp.sourceforge.talisman.csvio.CsvLine;
import jp.sourceforge.talisman.csvio.CsvParser;
+import org.objectweb.asm.Label;
+import org.objectweb.asm.Opcodes;
+import org.objectweb.asm.Type;
+import org.objectweb.asm.tree.AbstractInsnNode;
+import org.objectweb.asm.tree.FieldInsnNode;
+import org.objectweb.asm.tree.JumpInsnNode;
+import org.objectweb.asm.tree.LabelNode;
+import org.objectweb.asm.tree.LookupSwitchInsnNode;
+import org.objectweb.asm.tree.MethodInsnNode;
+import org.objectweb.asm.tree.TableSwitchInsnNode;
+
/**
*
* @author Haruaki Tamada
public Opcode getOpcode(int opcode){
return opcodeMap.get(opcode);
}
+
+ private Map<LabelNode, LabelOpcode> labelMap = new HashMap<LabelNode, LabelOpcode>();
+
+ public Opcode getOpcode(AbstractInsnNode node){
+ Opcode opcode = getOpcode(node.getOpcode());
+ if(opcode == null && node instanceof LabelNode){
+ opcode = labelMap.get(node);
+ if(opcode == null){
+ opcode = new LabelOpcode(((LabelNode)node).getLabel());
+ labelMap.put((LabelNode)node, (LabelOpcode)opcode);
+ }
+ }
+ if(opcode != null){
+ switch(opcode.getCategory()){
+ case BRANCH:
+ opcode = constructBranchOpcode(opcode, node);
+ break;
+ case INVOKE:
+ opcode = constructMethodOpcode(opcode, node);
+ break;
+ case OBJECT:
+ opcode = constructObjectOpcode(opcode, node);
+ break;
+ case NORMAL: // Not needs conversion.
+ case TARGETER: // Already convert above.
+ default:
+ break;
+ }
+ }
+
+ return opcode;
+ }
+
+ private Opcode constructMethodOpcode(Opcode o, AbstractInsnNode node){
+ Opcode methodOpcode = new Opcode(o);
+ MethodInsnNode methodNode = (MethodInsnNode)node;
+ Type[] types = Type.getArgumentTypes(methodNode.desc);
+ int argumentSize = 0;
+ for(Type type: types) argumentSize = type.getSize();
+ int size = Type.getReturnType(methodNode.desc).getSize();
+ switch(o.getOpcode()){
+ case Opcodes.INVOKESTATIC:
+ size = size - argumentSize;
+ break;
+ case Opcodes.INVOKEINTERFACE:
+ case Opcodes.INVOKESPECIAL:
+ case Opcodes.INVOKEVIRTUAL:
+ size = size - argumentSize - 1;
+ break;
+ }
+ methodOpcode.setAct(size);
+
+ return methodOpcode;
+ }
+
+ private Opcode constructObjectOpcode(Opcode o, AbstractInsnNode node){
+ Opcode opcode = new Opcode(o);
+ FieldInsnNode field = (FieldInsnNode)node;
+
+ int size = Type.getType(field.desc).getSize();
+ switch(opcode.getOpcode()){
+ case Opcodes.PUTFIELD:
+ size = -1 - size;
+ break;
+ case Opcodes.PUTSTATIC:
+ size = 0 - size;
+ break;
+ case Opcodes.GETFIELD:
+ size = -1 + size;
+ break;
+ case Opcodes.GETSTATIC:
+ size = 0 + size;
+ break;
+ }
+ opcode.setAct(size);
+ return opcode;
+ }
+
+ private Opcode constructBranchOpcode(Opcode defaultOpcode, AbstractInsnNode node){
+ Opcode opcode = new Opcode(defaultOpcode);
+ if(node instanceof TableSwitchInsnNode){
+ TableSwitchInsnNode table = (TableSwitchInsnNode)node;
+ List<Label> labels = new ArrayList<Label>();
+ labels.add(table.dflt.getLabel());
+ for(Object o: table.labels){
+ labels.add(((LabelNode)o).getLabel());
+ }
+ }
+ else if(node instanceof LookupSwitchInsnNode){
+ LookupSwitchInsnNode lookup = (LookupSwitchInsnNode)node;
+ List<Label> labels = new ArrayList<Label>();
+ labels.add(lookup.dflt.getLabel());
+ for(Object o: lookup.labels){
+ labels.add(((LabelNode)o).getLabel());
+ }
+ }
+ else{
+ opcode.addLabel(((JumpInsnNode)node).label.getLabel());
+ }
+ return opcode;
+ }
}
\r
Assert.assertEquals(6, graph.getBasicBlockSize());\r
\r
- graph.setIncludingExceptionFlow(true);\r
- Assert.assertEquals(7, graph.getBasicBlockSize());\r
+ // graph.setIncludingExceptionFlow(true);\r
+ // Assert.assertEquals(6, graph.getBasicBlockSize());\r
+ }\r
+\r
+ @Test\r
+ public void testGraph() throws Exception{\r
+ ControlFlowGraph graph = visitor.getGraph("<init>(I)V");\r
+ int[][] graphMatrix = graph.getGraphMatrix();\r
+\r
+ Assert.assertEquals(6, graphMatrix.length);\r
+\r
+ Assert.assertEquals(0, graphMatrix[0][0]);\r
+ Assert.assertEquals(1, graphMatrix[0][1]);\r
+ Assert.assertEquals(1, graphMatrix[0][2]);\r
+ Assert.assertEquals(0, graphMatrix[0][3]);\r
+ Assert.assertEquals(0, graphMatrix[0][4]);\r
+ Assert.assertEquals(0, graphMatrix[0][5]);\r
+\r
+ Assert.assertEquals(0, graphMatrix[1][0]);\r
+ Assert.assertEquals(0, graphMatrix[1][1]);\r
+ Assert.assertEquals(0, graphMatrix[1][2]);\r
+ Assert.assertEquals(1, graphMatrix[1][3]);\r
+ Assert.assertEquals(0, graphMatrix[1][4]);\r
+ Assert.assertEquals(0, graphMatrix[1][5]);\r
+\r
+ Assert.assertEquals(0, graphMatrix[2][0]);\r
+ Assert.assertEquals(0, graphMatrix[2][1]);\r
+ Assert.assertEquals(0, graphMatrix[2][2]);\r
+ Assert.assertEquals(1, graphMatrix[2][3]);\r
+ Assert.assertEquals(0, graphMatrix[2][4]);\r
+ Assert.assertEquals(0, graphMatrix[2][5]);\r
+\r
+ Assert.assertEquals(0, graphMatrix[3][0]);\r
+ Assert.assertEquals(0, graphMatrix[3][1]);\r
+ Assert.assertEquals(0, graphMatrix[3][2]);\r
+ Assert.assertEquals(0, graphMatrix[3][3]);\r
+ Assert.assertEquals(0, graphMatrix[3][4]);\r
+ Assert.assertEquals(1, graphMatrix[3][5]);\r
+\r
+ Assert.assertEquals(0, graphMatrix[4][0]);\r
+ Assert.assertEquals(0, graphMatrix[4][1]);\r
+ Assert.assertEquals(0, graphMatrix[4][2]);\r
+ Assert.assertEquals(0, graphMatrix[4][3]);\r
+ Assert.assertEquals(0, graphMatrix[4][4]);\r
+ Assert.assertEquals(1, graphMatrix[4][5]);\r
+\r
+ Assert.assertEquals(0, graphMatrix[5][0]);\r
+ Assert.assertEquals(0, graphMatrix[5][1]);\r
+ Assert.assertEquals(0, graphMatrix[5][2]);\r
+ Assert.assertEquals(0, graphMatrix[5][3]);\r
+ Assert.assertEquals(0, graphMatrix[5][4]);\r
+ Assert.assertEquals(0, graphMatrix[5][5]);\r
}\r
}\r
Assert.assertEquals(label2, opcode.getLabel(1));
Assert.assertEquals(label3, opcode.getLabel(2));
- Iterator<Label> iterator = opcode.labels();
+ Iterator<Label> iterator = opcode.iterator();
Assert.assertTrue(iterator.hasNext());
Assert.assertEquals(label1, iterator.next());
Assert.assertTrue(iterator.hasNext());
Assert.assertEquals(label2, opcode.getLabel(1));
Assert.assertEquals(label3, opcode.getLabel(2));
- Iterator<Label> iterator = opcode.labels();
+ Iterator<Label> iterator = opcode.iterator();
Assert.assertTrue(iterator.hasNext());
Assert.assertEquals(label1, iterator.next());
Assert.assertTrue(iterator.hasNext());
OSDN Git Service
