From: yeom Date: Thu, 19 Apr 2012 00:48:21 +0000 (+0000) Subject: changes. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=69b35ab159b9e63de0674dfa5ca4ab78f9e11221 changes. --- diff --git a/Robust/src/Analysis/SSJava/FlowEdge.java b/Robust/src/Analysis/SSJava/FlowEdge.java new file mode 100644 index 00000000..5309bac3 --- /dev/null +++ b/Robust/src/Analysis/SSJava/FlowEdge.java @@ -0,0 +1,73 @@ +package Analysis.SSJava; + +import IR.Descriptor; + +public class FlowEdge { + + private FlowNode src; + private FlowNode dst; + + // indicates that which tuple in the graph initiates this edge + private NTuple initTuple; + + // indicates that which tuple in the graph is the end of this edge + private NTuple endTuple; + + public FlowEdge(FlowNode src, FlowNode dst, NTuple initTuple, + NTuple endTuple) { + this.src = src; + this.dst = dst; + this.initTuple = initTuple; + this.endTuple = endTuple; + } + + public String toString() { + return "Edge(" + initTuple + "/" + endTuple + "):: " + src + " to " + dst; + } + + public FlowNode getSrc() { + return src; + } + + public void setSrc(FlowNode src) { + this.src = src; + } + + public FlowNode getDst() { + return dst; + } + + public void setDst(FlowNode dst) { + this.dst = dst; + } + + public NTuple getInitTuple() { + return initTuple; + } + + public void setInitTuple(NTuple initTuple) { + this.initTuple = initTuple; + } + + public int hashCode() { + return src.hashCode() + dst.hashCode() + initTuple.hashCode() + endTuple.hashCode(); + } + + public NTuple getEndTuple() { + return endTuple; + } + + public boolean equals(Object obj) { + + if (obj instanceof FlowEdge) { + FlowEdge in = (FlowEdge) obj; + if (src.equals(in.getSrc()) && dst.equals(in.getDst()) && initTuple.equals(in.getInitTuple()) + && endTuple.equals(in.getEndTuple())) { + return true; + } + } + + return false; + } + +} diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index a35a93cb..32af6ccf 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -1,10 +1,18 @@ package Analysis.SSJava; +import java.io.BufferedWriter; +import java.io.File; +import java.io.FileWriter; +import java.io.IOException; import java.util.HashMap; import java.util.HashSet; +import java.util.Iterator; import java.util.Map; import java.util.Set; +import java.util.Map.Entry; +import Analysis.OoOJava.ConflictEdge; +import Analysis.OoOJava.ConflictNode; import IR.Descriptor; import IR.MethodDescriptor; @@ -30,7 +38,9 @@ public class FlowGraph { mapNodeToNeighborSet = new HashMap, Set>(); // create a node for 'this' varialbe - FlowNode thisNode = new FlowNode(null, md.getThis()); + NTuple thisDescTuple = new NTuple(); + thisDescTuple.add(md.getThis()); + FlowNode thisNode = new FlowNode(thisDescTuple); NTuple thisVarTuple = new NTuple(); thisVarTuple.add(md.getThis()); mapDescTupleToInferNode.put(thisVarTuple, thisNode); @@ -60,7 +70,7 @@ public class FlowGraph { for (int i = 0; i < fromTupleSize; i++) { Descriptor desc = fromDescTuple.get(i); curTuple.add(desc); - addNeighbor(getInferNode(curTuple), toNode); + addFlowEdge(getFlowNode(curTuple), toNode, fromDescTuple, toDescTuple); } int toTupleSize = toDescTuple.size(); @@ -68,30 +78,117 @@ public class FlowGraph { for (int i = 0; i < toTupleSize; i++) { Descriptor desc = toDescTuple.get(i); curTuple.add(desc); - addNeighbor(fromNode, getInferNode(curTuple)); + addFlowEdge(fromNode, getFlowNode(curTuple), fromDescTuple, toDescTuple); } } - public FlowNode getInferNode(NTuple descTuple) { + private void addFlowEdge(FlowNode fromNode, FlowNode toNode, NTuple initTuple, + NTuple endTuple) { + + FlowEdge edge = new FlowEdge(fromNode, toNode, initTuple, endTuple); + + fromNode.addOutEdge(edge); + + System.out.println("add a new edge=" + edge); + + } + + public FlowNode getFlowNode(NTuple descTuple) { if (mapDescTupleToInferNode.containsKey(descTuple)) { return mapDescTupleToInferNode.get(descTuple); + } else { + FlowNode node = new FlowNode(descTuple); + mapDescTupleToInferNode.put(descTuple, node); + return node; } - return null; } public FlowNode getThisVarNode() { return thisVarNode; } - public void createNewFlowNode(NTuple base) { + public void createNewFlowNode(NTuple tuple) { + + if (!mapDescTupleToInferNode.containsKey(tuple)) { + FlowNode node = new FlowNode(tuple); + mapDescTupleToInferNode.put(tuple, node); + nodeSet.add(node); + + if (tuple.size() > 1) { + NTuple baseTuple = tuple.subList(0, tuple.size() - 1); + getFlowNode(baseTuple).addFieldNode(node); + } + + System.out.println("Creating new node=" + node); + } + + } + + public void writeGraph() throws java.io.IOException { + + String graphName = md.toString(); + graphName = graphName.replaceAll("[\\W]", ""); + + BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot")); + bw.write("digraph " + graphName + " {\n"); + bw.write("compound=true;\n"); + + // then visit every flow node + + Iterator iter = nodeSet.iterator(); - FlowNode node = new FlowNode(base); - mapDescTupleToInferNode.put(base, node); + Set addedSet = new HashSet(); - System.out.println("Creating new node=" + node); + while (iter.hasNext()) { + FlowNode node = iter.next(); + + if (node.getFieldNodeSet().size() > 0) { + drawSubgraph(node, bw); + } + + String attributes = " ["; + + attributes += "label=\"" + node.getID() + "\"]"; + + bw.write(node.getID() + attributes + ";\n"); + + Set edgeSet = node.getOutEdgeSet(); + + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + FlowEdge flowEdge = iterator.next(); + + FlowNode u = flowEdge.getSrc(); + FlowNode v = flowEdge.getDst(); + + if (!addedSet.contains(flowEdge)) { + bw.write("" + u.getID() + " -> " + v.getID() + ";\n"); + addedSet.add(flowEdge); + } + + } + } + + bw.write("graphTitle[label=\"" + graphName + "\",shape=box];\n"); + + bw.write("}\n"); + bw.close(); } - + private void drawSubgraph(FlowNode node, BufferedWriter bw) throws IOException { + + bw.write(" subgraph sg" + node.getID() + "{\n"); + // bw.write(" color=gray;\n"); + bw.write(" label=\"" + node.getID() + "\";\n"); + + Set fieldNodeSet = node.getFieldNodeSet(); + for (Iterator iterator = fieldNodeSet.iterator(); iterator.hasNext();) { + FlowNode fieldNode = (FlowNode) iterator.next(); + String attribute = fieldNode.getID() + ";\n"; + bw.write(" " + attribute); + } + + bw.write(" }\n"); + } } \ No newline at end of file diff --git a/Robust/src/Analysis/SSJava/FlowNode.java b/Robust/src/Analysis/SSJava/FlowNode.java index cc7d4ee1..ee97a2c7 100644 --- a/Robust/src/Analysis/SSJava/FlowNode.java +++ b/Robust/src/Analysis/SSJava/FlowNode.java @@ -1,5 +1,7 @@ package Analysis.SSJava; +import java.util.HashSet; +import java.util.Iterator; import java.util.Set; import IR.Descriptor; @@ -13,15 +15,23 @@ public class FlowNode { // this set contains fields of the base type private Set fieldNodeSet; - public FlowNode(Descriptor desc) { - this(null, desc); + public Set getFieldNodeSet() { + return fieldNodeSet; } - public FlowNode(NTuple base) { - this(base, null); - } + private Set outEdgeSet; + + public FlowNode(NTuple tuple) { - public FlowNode(NTuple base, Descriptor desc) { + NTuple base = null; + Descriptor desc = null; + if (tuple.size() > 1) { + base = tuple.subList(0, tuple.size() - 1); + desc = tuple.get(tuple.size() - 1); + } else { + base = tuple; + } + fieldNodeSet = new HashSet(); descTuple = new NTuple(); if (base != null) { descTuple.addAll(base); @@ -29,6 +39,11 @@ public class FlowNode { if (desc != null) { descTuple.add(desc); } + outEdgeSet = new HashSet(); + } + + public void addFieldNode(FlowNode node) { + fieldNodeSet.add(node); } public NTuple getDescTuple() { @@ -43,4 +58,41 @@ public class FlowNode { return "[FlowNode]::" + descTuple; } + public Iterator iteratorOfOutEdges() { + return outEdgeSet.iterator(); + } + + public void addOutEdge(FlowEdge out) { + outEdgeSet.add(out); + } + + public Set getOutEdgeSet() { + return outEdgeSet; + } + + public int hashCode() { + return 7 + descTuple.hashCode(); + } + + public boolean equals(Object obj) { + + if (obj instanceof FlowNode) { + FlowNode in = (FlowNode) obj; + if (descTuple.equals(in.getDescTuple())) { + return true; + } + } + + return false; + + } + + public String getID() { + String id = ""; + for (int i = 0; i < descTuple.size(); i++) { + id += descTuple.get(i).getSymbol(); + } + return id; + } + } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index c99c6bb7..fe0900c9 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -1,5 +1,6 @@ package Analysis.SSJava; +import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; @@ -123,6 +124,8 @@ public class LocationInference { } } + _debug_printGraph(); + } private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) { @@ -217,8 +220,7 @@ public class LocationInference { if (dn.getExpression() != null) { NodeTupleSet tupleSetRHS = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, - new NTuple()); + analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null); // add a new flow edge from rhs to lhs for (Iterator> iter = tupleSetRHS.iterator(); iter.hasNext();) { @@ -240,6 +242,7 @@ public class LocationInference { // note that expression node can create more than one flow node // nodeSet contains of flow nodes + // base is always assigned to null except name node case! NTuple flowTuple; @@ -261,8 +264,7 @@ public class LocationInference { return flowTuple; case Kind.OpNode: - // return analyzeOpNode(md, nametable, (OpNode) en, new - // HashSet()); + analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet); break; case Kind.CreateObjectNode: @@ -343,21 +345,22 @@ public class LocationInference { } - private Set analyzeOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on, - Set nodeSet) { + private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on, + NodeTupleSet nodeSet) { - ClassDescriptor cd = md.getClassDesc(); + System.out.println("### OPNode=" + on.printNode(0)); + + NodeTupleSet leftOpSet = new NodeTupleSet(); + NodeTupleSet rightOpSet = new NodeTupleSet(); // left operand - // NTuple leftOpTuple = - // analyzeFlowExpressionNode(md, nametable, on.getLeft(), new - // NTuple()); + analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null); + System.out.println("leftOpSet=" + leftOpSet); if (on.getRight() != null) { // right operand - // NTuple rightOpTuple = - // analyzeFlowExpressionNode(md, nametable, on.getRight(), new - // NTuple()); + analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null); + System.out.println("rightOpSet=" + rightOpSet); } Operation op = on.getOp(); @@ -368,7 +371,8 @@ public class LocationInference { case Operation.UNARYMINUS: case Operation.LOGIC_NOT: // single operand - // return leftLoc; + nodeSet.addTupleSet(leftOpSet); + break; case Operation.LOGIC_OR: case Operation.LOGIC_AND: @@ -392,12 +396,10 @@ public class LocationInference { case Operation.RIGHTSHIFT: case Operation.URIGHTSHIFT: - Set inputSet = new HashSet(); - // inputSet.add(leftLoc); - // inputSet.add(rightLoc); - // CompositeLocation glbCompLoc = - // CompositeLattice.calculateGLB(inputSet, generateErrorMessage(cd, on)); - // return glbCompLoc; + // there are two operands + nodeSet.addTupleSet(leftOpSet); + nodeSet.addTupleSet(rightOpSet); + break; default: throw new Error(op.toString()); @@ -550,7 +552,7 @@ public class LocationInference { // if LHS is array access node, need to capture value flows between an array // and its index value - analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, base); + analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null); System.out.println("ASSIGNMENT NODE nodeSetLHS=" + nodeSetLHS); // NTuple lhsDescTuple = analyzeFlowExpressionNode(md, // nametable, an.getDest(), base); @@ -560,20 +562,22 @@ public class LocationInference { analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null); System.out.println("ASSIGNMENT NODE nodeSetRHS=" + nodeSetRHS); - } else { + // creates edges from RHS to LHS + for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { + NTuple fromTuple = iter.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple toTuple = iter2.next(); + addFlowGraphEdge(md, fromTuple, toTuple); + } + } + } else { // postinc case - // src & dest are same - - } - - // creates edges from RHS to LHS - for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { - NTuple fromTuple = iter.next(); for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { - NTuple toTuple = iter2.next(); - addFlowGraphEdge(md, fromTuple, toTuple); + NTuple tuple = iter2.next(); + addFlowGraphEdge(md, tuple, tuple); } + } } @@ -587,4 +591,19 @@ public class LocationInference { graph.addValueFlowEdge(from, to); } + public void _debug_printGraph() { + Set keySet = mapMethodDescriptorToFlowGraph.keySet(); + + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md); + try { + fg.writeGraph(); + } catch (IOException e) { + e.printStackTrace(); + } + } + + } + } diff --git a/Robust/src/Analysis/SSJava/NodeTupleSet.java b/Robust/src/Analysis/SSJava/NodeTupleSet.java index d793424c..30fb1fb8 100644 --- a/Robust/src/Analysis/SSJava/NodeTupleSet.java +++ b/Robust/src/Analysis/SSJava/NodeTupleSet.java @@ -8,7 +8,7 @@ import IR.Descriptor; public class NodeTupleSet { - Set> set; + private Set> set; public NodeTupleSet() { set = new HashSet>(); @@ -21,12 +21,12 @@ public class NodeTupleSet { // for example, if we have input , we need to add additional element // and to the set - NTuple cur = new NTuple(); - for (int i = 0; i < tuple.size(); i++) { - Descriptor d = tuple.get(i); - cur.add(d); - set.add(new NTuple(cur)); - } + // NTuple cur = new NTuple(); + // for (int i = 0; i < tuple.size(); i++) { + // Descriptor d = tuple.get(i); + // cur.add(d); + // set.add(new NTuple(cur)); + // } set.add(tuple); } @@ -39,4 +39,11 @@ public class NodeTupleSet { return set.toString(); } + public Set> getSet() { + return set; + } + + public void addTupleSet(NodeTupleSet in) { + set.addAll(in.getSet()); + } }