From: yeom Date: Fri, 20 Apr 2012 00:21:04 +0000 (+0000) Subject: more changes. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=1bf00baead0bc7e05945fe5649f9d92afadae081 more changes. --- diff --git a/Robust/src/Analysis/SSJava/FlowDownCheck.java b/Robust/src/Analysis/SSJava/FlowDownCheck.java index 01d60c2c..45ceee75 100644 --- a/Robust/src/Analysis/SSJava/FlowDownCheck.java +++ b/Robust/src/Analysis/SSJava/FlowDownCheck.java @@ -606,6 +606,8 @@ public class FlowDownCheck { } else { // check 'for loop' case BlockNode bn = ln.getInitializer(); + // need to check initialization node + checkLocationFromBlockNode(md, nametable, bn, constraint); bn.getVarTable().setParent(nametable); // calculate glb location of condition and update statements diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index 32af6ccf..049317d8 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -14,7 +14,9 @@ import java.util.Map.Entry; import Analysis.OoOJava.ConflictEdge; import Analysis.OoOJava.ConflictNode; import IR.Descriptor; +import IR.FieldDescriptor; import IR.MethodDescriptor; +import IR.VarDescriptor; public class FlowGraph { @@ -87,7 +89,6 @@ public class FlowGraph { NTuple endTuple) { FlowEdge edge = new FlowEdge(fromNode, toNode, initTuple, endTuple); - fromNode.addOutEdge(edge); System.out.println("add a new edge=" + edge); @@ -98,8 +99,7 @@ public class FlowGraph { if (mapDescTupleToInferNode.containsKey(descTuple)) { return mapDescTupleToInferNode.get(descTuple); } else { - FlowNode node = new FlowNode(descTuple); - mapDescTupleToInferNode.put(descTuple, node); + FlowNode node = createNewFlowNode(descTuple); return node; } } @@ -108,7 +108,7 @@ public class FlowGraph { return thisVarNode; } - public void createNewFlowNode(NTuple tuple) { + public FlowNode createNewFlowNode(NTuple tuple) { if (!mapDescTupleToInferNode.containsKey(tuple)) { FlowNode node = new FlowNode(tuple); @@ -121,10 +121,52 @@ public class FlowGraph { } System.out.println("Creating new node=" + node); + return node; + } else { + return mapDescTupleToInferNode.get(tuple); } } + private void drawEdges(FlowNode node, BufferedWriter bw, Set addedNodeSet, + Set addedEdgeSet) throws IOException { + + Set edgeSet = node.getOutEdgeSet(); + + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + FlowEdge flowEdge = iterator.next(); + + FlowNode u = flowEdge.getSrc(); + FlowNode v = flowEdge.getDst(); + + if (u.getDescTuple().equals(flowEdge.getInitTuple()) + && v.getDescTuple().equals(flowEdge.getEndTuple())) { + // only draw an edge of the actual value flow + + if (!addedEdgeSet.contains(flowEdge)) { + + if (!addedNodeSet.contains(u)) { + drawNode(u, bw); + addedNodeSet.add(u); + } + if (!addedNodeSet.contains(v)) { + drawNode(v, bw); + addedNodeSet.add(v); + } + + bw.write("" + u.getID() + " -> " + v.getID() + ";\n"); + addedEdgeSet.add(flowEdge); + } + } + + } + + } + + private void drawNode(FlowNode node, BufferedWriter bw) throws IOException { + bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n"); + } + public void writeGraph() throws java.io.IOException { String graphName = md.toString(); @@ -138,57 +180,58 @@ public class FlowGraph { Iterator iter = nodeSet.iterator(); - Set addedSet = new HashSet(); + Set addedEdgeSet = new HashSet(); + Set addedNodeSet = new HashSet(); 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); + if (node.getDescTuple().size() == 1) { + // here, we just care about the local variable + if (node.getFieldNodeSet().size() > 0) { + drawSubgraph(node, bw, addedEdgeSet); } - } - } + drawEdges(node, bw, addedNodeSet, addedEdgeSet); - bw.write("graphTitle[label=\"" + graphName + "\",shape=box];\n"); + } bw.write("}\n"); bw.close(); } - private void drawSubgraph(FlowNode node, BufferedWriter bw) throws IOException { + public boolean constainsNode(FlowNode node) { + return nodeSet.contains(node); + } - bw.write(" subgraph sg" + node.getID() + "{\n"); - // bw.write(" color=gray;\n"); - bw.write(" label=\"" + node.getID() + "\";\n"); + private void drawSubgraph(FlowNode node, BufferedWriter bw, Set addedSet) + throws IOException { + + bw.write("subgraph cluster_" + node.getID() + "{\n"); + bw.write("label=\"" + node.getPrettyID() + "\";\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); + if (fieldNode.getFieldNodeSet().size() > 0) { + drawSubgraph(fieldNode, bw, addedSet); + } else { + Descriptor desc = fieldNode.getDescTuple().getLastElement(); + if (desc instanceof VarDescriptor) { + VarDescriptor varDesc = (VarDescriptor) desc; + if (varDesc.getType().isPrimitive()) { + bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n"); + } + } else if (desc instanceof FieldDescriptor) { + FieldDescriptor fieldDesc = (FieldDescriptor) desc; + if (fieldDesc.getType().isPrimitive()) { + bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n"); + } + } + } } - bw.write(" }\n"); + 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 ee97a2c7..86edb08d 100644 --- a/Robust/src/Analysis/SSJava/FlowNode.java +++ b/Robust/src/Analysis/SSJava/FlowNode.java @@ -95,4 +95,15 @@ public class FlowNode { return id; } + public String getPrettyID() { + String id = "<"; + for (int i = 0; i < descTuple.size(); i++) { + if (i != 0) { + id += ","; + } + id += descTuple.get(i).getSymbol(); + } + id += ">"; + return id; + } } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index fe0900c9..cb2bb28b 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -130,37 +130,38 @@ public class LocationInference { private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) { BlockNode bn = state.getMethodBody(md); - analyzeBlockNode(md, md.getParameterTable(), bn); + analyzeFlowBlockNode(md, md.getParameterTable(), bn, null); } - private void analyzeBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) { + private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn, + NodeTupleSet implicitFlowTupleSet) { bn.getVarTable().setParent(nametable); for (int i = 0; i < bn.size(); i++) { BlockStatementNode bsn = bn.get(i); - analyzeBlockStatementNode(md, bn.getVarTable(), bsn); + analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet); } } private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable, - BlockStatementNode bsn) { + BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) { switch (bsn.kind()) { case Kind.BlockExpressionNode: - analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn); + analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet); break; case Kind.DeclarationNode: - analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn); + analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet); break; case Kind.IfStatementNode: - analyzeIfStatementNode(md, nametable, (IfStatementNode) bsn); + analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet); break; case Kind.LoopNode: - analyzeLoopNode(md, nametable, (LoopNode) bsn); + analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet); break; case Kind.ReturnNode: @@ -168,7 +169,7 @@ public class LocationInference { break; case Kind.SubBlockNode: - analyzeSubBlockNode(md, nametable, (SubBlockNode) bsn); + analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet); break; case Kind.ContinueBreakNode: @@ -188,9 +189,9 @@ public class LocationInference { } - private void analyzeSubBlockNode(MethodDescriptor md, SymbolTable nametable, SubBlockNode bsn) { - // TODO Auto-generated method stub - + private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable, + SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) { + analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet); } private void analyzeReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode bsn) { @@ -198,19 +199,58 @@ public class LocationInference { } - private void analyzeLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode bsn) { - // TODO Auto-generated method stub + private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln, + NodeTupleSet implicitFlowTupleSet) { + + if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) { + + NodeTupleSet condTupleNode = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null, + implicitFlowTupleSet); + condTupleNode.addTupleSet(implicitFlowTupleSet); + System.out.println("condTupleNode=" + condTupleNode); + + // add edges from condNodeTupleSet to all nodes of conditional nodes + analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode); + + } else { + // check 'for loop' case + BlockNode bn = ln.getInitializer(); + analyzeFlowBlockNode(md, nametable, bn, implicitFlowTupleSet); + bn.getVarTable().setParent(nametable); + + NodeTupleSet condTupleNode = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null, + implicitFlowTupleSet); + condTupleNode.addTupleSet(implicitFlowTupleSet); + System.out.println("condTupleNode=" + condTupleNode); + + analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode); + analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode); + + } } - private void analyzeIfStatementNode(MethodDescriptor md, SymbolTable nametable, - IfStatementNode bsn) { - // TODO Auto-generated method stub + private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable, + IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) { + + NodeTupleSet condTupleNode = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null, + implicitFlowTupleSet); + + // add edges from condNodeTupleSet to all nodes of conditional nodes + condTupleNode.addTupleSet(implicitFlowTupleSet); + analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode); + + if (isn.getFalseBlock() != null) { + analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode); + } } private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable, - DeclarationNode dn) { + DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) { VarDescriptor vd = dn.getVarDescriptor(); NTuple tupleLHS = new NTuple(); @@ -220,7 +260,8 @@ public class LocationInference { if (dn.getExpression() != null) { NodeTupleSet tupleSetRHS = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null); + analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null, + implicitFlowTupleSet); // add a new flow edge from rhs to lhs for (Iterator> iter = tupleSetRHS.iterator(); iter.hasNext();) { @@ -233,12 +274,13 @@ public class LocationInference { } private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable, - BlockExpressionNode ben) { - analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null); + BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) { + analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet); } private NTuple analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable, - ExpressionNode en, NodeTupleSet nodeSet, NTuple base) { + ExpressionNode en, NodeTupleSet nodeSet, NTuple base, + NodeTupleSet implicitFlowTupleSet) { // note that expression node can create more than one flow node // nodeSet contains of flow nodes @@ -249,22 +291,25 @@ public class LocationInference { switch (en.kind()) { case Kind.AssignmentNode: - analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base); + analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base, implicitFlowTupleSet); break; case Kind.FieldAccessNode: - flowTuple = analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base); + flowTuple = + analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base, + implicitFlowTupleSet); nodeSet.addTuple(flowTuple); return flowTuple; case Kind.NameNode: NodeTupleSet nameNodeSet = new NodeTupleSet(); - flowTuple = analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base); + flowTuple = + analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet); nodeSet.addTuple(flowTuple); return flowTuple; case Kind.OpNode: - analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet); + analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet); break; case Kind.CreateObjectNode: @@ -346,20 +391,19 @@ public class LocationInference { } private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on, - NodeTupleSet nodeSet) { - - System.out.println("### OPNode=" + on.printNode(0)); + NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { NodeTupleSet leftOpSet = new NodeTupleSet(); NodeTupleSet rightOpSet = new NodeTupleSet(); // left operand - analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null); + analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet); System.out.println("leftOpSet=" + leftOpSet); if (on.getRight() != null) { // right operand - analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null); + analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null, + implicitFlowTupleSet); System.out.println("rightOpSet=" + rightOpSet); } @@ -407,7 +451,7 @@ public class LocationInference { } private NTuple analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable, - NameNode nn, NodeTupleSet nodeSet, NTuple base) { + NameNode nn, NodeTupleSet nodeSet, NTuple base, NodeTupleSet implicitFlowTupleSet) { if (base == null) { base = new NTuple(); @@ -415,7 +459,8 @@ public class LocationInference { NameDescriptor nd = nn.getName(); if (nd.getBase() != null) { - analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base); + analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base, + implicitFlowTupleSet); } else { String varname = nd.toString(); if (varname.equals("this")) { @@ -491,7 +536,8 @@ public class LocationInference { } private NTuple analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable, - FieldAccessNode fan, NodeTupleSet nodeSet, NTuple base) { + FieldAccessNode fan, NodeTupleSet nodeSet, NTuple base, + NodeTupleSet implicitFlowTupleSet) { ExpressionNode left = fan.getExpression(); TypeDescriptor ltd = left.getType(); @@ -516,7 +562,7 @@ public class LocationInference { // left = aan.getExpression(); // } // fanNodeSet - base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base); + base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet); if (!left.getType().isPrimitive()) { @@ -534,12 +580,10 @@ public class LocationInference { } private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable, - AssignmentNode an, NTuple base) { + AssignmentNode an, NTuple base, NodeTupleSet implicitFlowTupleSet) { System.out.println("analyzeFlowAssignmentNode=" + an); - ClassDescriptor cd = md.getClassDesc(); - NodeTupleSet nodeSetRHS = new NodeTupleSet(); NodeTupleSet nodeSetLHS = new NodeTupleSet(); @@ -552,14 +596,14 @@ 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, null); + analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet); System.out.println("ASSIGNMENT NODE nodeSetLHS=" + nodeSetLHS); // NTuple lhsDescTuple = analyzeFlowExpressionNode(md, // nametable, an.getDest(), base); if (!postinc) { // analyze value flows of rhs expression - analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null); + analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet); System.out.println("ASSIGNMENT NODE nodeSetRHS=" + nodeSetRHS); // creates edges from RHS to LHS @@ -571,6 +615,15 @@ public class LocationInference { } } + // creates edges from implicitFlowTupleSet to LHS + for (Iterator> iter = implicitFlowTupleSet.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 for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { diff --git a/Robust/src/Analysis/SSJava/NTuple.java b/Robust/src/Analysis/SSJava/NTuple.java index 289b46b9..513d7a50 100644 --- a/Robust/src/Analysis/SSJava/NTuple.java +++ b/Robust/src/Analysis/SSJava/NTuple.java @@ -105,4 +105,8 @@ public class NTuple { } + public T getLastElement() { + return elements.get(elements.size() - 1); + } + } diff --git a/Robust/src/Analysis/SSJava/NodeTupleSet.java b/Robust/src/Analysis/SSJava/NodeTupleSet.java index 30fb1fb8..68509604 100644 --- a/Robust/src/Analysis/SSJava/NodeTupleSet.java +++ b/Robust/src/Analysis/SSJava/NodeTupleSet.java @@ -44,6 +44,8 @@ public class NodeTupleSet { } public void addTupleSet(NodeTupleSet in) { - set.addAll(in.getSet()); + if (in != null) { + set.addAll(in.getSet()); + } } }