From 561af6103d5d245d56589c369041dccddf43cf48 Mon Sep 17 00:00:00 2001 From: yeom Date: Tue, 2 Oct 2012 01:15:13 +0000 Subject: [PATCH] changes to get a global flow graph --- Robust/src/Analysis/SSJava/FlowGraph.java | 54 +++-- Robust/src/Analysis/SSJava/FlowNode.java | 25 +- .../Analysis/SSJava/LocationInference.java | 229 ++++++++++-------- 3 files changed, 170 insertions(+), 138 deletions(-) diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index 0655c5fa..c8914f14 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -13,15 +13,12 @@ import IR.ClassDescriptor; import IR.Descriptor; import IR.FieldDescriptor; import IR.MethodDescriptor; -import IR.NameDescriptor; import IR.VarDescriptor; public class FlowGraph { MethodDescriptor md; - Set nodeSet; - Set returnNodeSet; FlowNode thisVarNode; @@ -47,7 +44,6 @@ public class FlowGraph { this.md = md; this.mapFlowNodeToLocTuple = new HashMap>(); this.mapLocTupleToFlowNode = new HashMap, FlowNode>(); - this.nodeSet = new HashSet(); this.mapDescTupleToInferNode = new HashMap, FlowNode>(); this.mapParamDescToIdx = new HashMap(); this.mapParamDescToIdx.putAll(mapParamDescToIdx); @@ -87,10 +83,6 @@ public class FlowGraph { this.mapLocTupleToFlowNode.putAll(in); } - public void setNodeSet(Set in) { - this.nodeSet.addAll(in); - } - public void setReturnNodeSet(Set in) { this.returnNodeSet.addAll(in); } @@ -113,7 +105,7 @@ public class FlowGraph { newNode.setIntermediate(true); mapDescTupleToInferNode.put(tuple, newNode); - nodeSet.add(newNode); + // nodeSet.add(newNode); System.out.println("create new intermediate node= " + newNode); @@ -144,7 +136,9 @@ public class FlowGraph { } public Set getNodeSet() { - return nodeSet; + Set set = new HashSet(); + set.addAll(mapDescTupleToInferNode.values()); + return set; } public MethodDescriptor getMethodDescriptor() { @@ -184,6 +178,26 @@ public class FlowGraph { return false; } + public Set getOutEdgeSetStartingFrom(FlowNode startNode) { + + Descriptor prefixDesc = startNode.getCurrentDescTuple().get(0); + + // returns the set of edges that share the same prefix of startNode + Set edgeSet = new HashSet(); + + for (Iterator> iter = mapFlowNodeToOutEdgeSet.values().iterator(); iter.hasNext();) { + Set nodeEdgeSet = iter.next(); + for (Iterator iter2 = nodeEdgeSet.iterator(); iter2.hasNext();) { + FlowEdge edge = iter2.next(); + if (edge.getInitTuple().get(0).equals(prefixDesc)) { + edgeSet.add(edge); + } + } + } + + return edgeSet; + } + public Set getOutEdgeSet(FlowNode node) { if (!mapFlowNodeToOutEdgeSet.containsKey(node)) { mapFlowNodeToOutEdgeSet.put(node, new HashSet()); @@ -196,7 +210,7 @@ public class FlowGraph { FlowNode fromNode = getFlowNode(fromDescTuple); FlowNode toNode = getFlowNode(toDescTuple); - System.out.println("create an edge from " + fromNode + " to " + toNode); + // System.out.println("create an edge from " + fromNode + " to " + toNode); int fromTupleSize = fromDescTuple.size(); NTuple curFromTuple = new NTuple(); @@ -263,7 +277,7 @@ public class FlowGraph { if (!mapDescTupleToInferNode.containsKey(tuple)) { FlowNode node = new FlowNode(tuple); mapDescTupleToInferNode.put(tuple, node); - nodeSet.add(node); + // nodeSet.add(node); mapLocTupleToFlowNode.put(getLocationTuple(node), node); @@ -442,7 +456,7 @@ public class FlowGraph { public void getIncomingFlowNodeSet(FlowNode node, Set visited) { - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) { FlowNode curNode = (FlowNode) iterator.next(); Set edgeSet = getOutEdgeSet(curNode); @@ -470,7 +484,7 @@ public class FlowGraph { ClassDescriptor cd = null; - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) { FlowNode node = (FlowNode) iterator.next(); Set edgeSet = getOutEdgeSet(node); @@ -504,10 +518,15 @@ public class FlowGraph { return mapParamDescToIdx.containsKey(firstIdxDesc); } + public int getParamIdx(NTuple tuple) { + Descriptor firstIdxDesc = tuple.get(0); + return mapParamDescToIdx.get(firstIdxDesc); + } + public FlowGraph clone() { FlowGraph clone = new FlowGraph(md, mapParamDescToIdx); - clone.setNodeSet(getNodeSet()); + // clone.setNodeSet(getNodeSet()); clone.setMapLocTupleToFlowNode(getMapLocTupleToFlowNode()); clone.setMapFlowNodeToLocTuple(getMapFlowNodeToLocTuple()); clone.setMapDescTupleToInferNode(getMapDescTupleToInferNode()); @@ -595,7 +614,8 @@ public class FlowGraph { // then visit every flow node - Iterator iter = nodeSet.iterator(); + // Iterator iter = nodeSet.iterator(); + Iterator iter = getNodeSet().iterator(); Set addedEdgeSet = new HashSet(); Set addedNodeSet = new HashSet(); @@ -619,7 +639,7 @@ public class FlowGraph { } public boolean constainsNode(FlowNode node) { - return nodeSet.contains(node); + return getNodeSet().contains(node); } private void drawSubgraph(FlowNode node, BufferedWriter bw, Set addedSet) diff --git a/Robust/src/Analysis/SSJava/FlowNode.java b/Robust/src/Analysis/SSJava/FlowNode.java index 51f1b08d..cdd9bd47 100644 --- a/Robust/src/Analysis/SSJava/FlowNode.java +++ b/Robust/src/Analysis/SSJava/FlowNode.java @@ -111,17 +111,6 @@ public class FlowNode { return rtr; } -// 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(); @@ -163,13 +152,13 @@ public class FlowNode { id += " " + compLoc; } - if (isReturn()) { - property += "R"; - } - - if (isSkeleton()) { - property += "S"; - } + // if (isReturn()) { + // property += "R"; + // } + // + // if (isSkeleton()) { + // property += "S"; + // } if (property.length() > 0) { property = " [" + property + "]"; diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 148733af..dfa8e0e7 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -94,7 +94,7 @@ public class LocationInference { // invoked by the method descriptor private Map> mapMethodDescriptorToMethodInvokeNodeSet; - private Map> mapMethodInvokeNodeToArgIdxMap; + private Map>> mapMethodInvokeNodeToArgIdxMap; private Map> mapMethodInvokeNodeToBaseTuple; @@ -146,7 +146,7 @@ public class LocationInference { this.mapMethodDescriptorToMethodInvokeNodeSet = new HashMap>(); this.mapMethodInvokeNodeToArgIdxMap = - new HashMap>(); + new HashMap>>(); this.mapMethodDescToMethodLocationInfo = new HashMap(); this.mapMethodToCalleeSet = new HashMap>(); this.mapClassToLocationInfo = new HashMap(); @@ -290,8 +290,8 @@ public class LocationInference { // FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); // mapMethodDescriptorToFlowGraph.put(md, fg); // analyzeMethodBody(md.getClassDesc(), md); - } + } // _debug_printGraph(); @@ -340,50 +340,61 @@ public class LocationInference { int numParam = calleeSubGlobalGraph.getNumParameters(); for (int idx = 0; idx < numParam; idx++) { FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx); - NodeTupleSet argTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); - System.out.println("argTupleSet=" + argTupleSet + " param=" + paramNode); - for (Iterator> iter = argTupleSet.iterator(); iter.hasNext();) { - NTuple argTuple = iter.next(); - addValueFlowsFromCalleeParam(calleeSubGlobalGraph, paramNode, callerSubGlobalGraph, - argTuple, baseTuple); - } + NTuple argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); + System.out.println("argTupleSet=" + argTuple + " param=" + paramNode); + // here, it adds all value flows reachable from the paramNode in the callee's flow graph + addValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode, callerSubGlobalGraph, + argTuple, baseTuple); } } - private void addValueFlowsFromCalleeParam(FlowGraph calleeSubGlobalGraph, FlowNode paramNode, - FlowGraph callerSubGlobalGraph, NTuple argTuple, NTuple baseTuple) { + private void addValueFlowsFromCalleeParam(MethodInvokeNode min, FlowGraph calleeSubGlobalGraph, + FlowNode paramNode, FlowGraph callerSubGlobalGraph, NTuple argTuple, + NTuple baseTuple) { Set visited = new HashSet(); visited.add(paramNode); - recurAddValueFlowsFromCalleeParam(calleeSubGlobalGraph, paramNode, callerSubGlobalGraph, + recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode, callerSubGlobalGraph, argTuple, visited, baseTuple); } - private void recurAddValueFlowsFromCalleeParam(FlowGraph calleeSubGlobalGraph, - FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph, NTuple callerSrcTuple, - Set visited, NTuple baseTuple) { + private void recurAddValueFlowsFromCalleeParam(MethodInvokeNode min, + FlowGraph calleeSubGlobalGraph, FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph, + NTuple callerSrcTuple, Set visited, NTuple baseTuple) { MethodDescriptor mdCallee = calleeSubGlobalGraph.getMethodDescriptor(); - Set edgeSet = calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode); + // Set edgeSet = calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode); + Set edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { FlowEdge flowEdge = (FlowEdge) iterator.next(); - FlowNode dstNode = flowEdge.getDst(); - NTuple dstDescTuple = dstNode.getCurrentDescTuple(); - if (dstDescTuple.get(0).equals(mdCallee.getThis())) { - // destination node is started with 'this' variable - // need to translate it in terms of the caller's base node - dstDescTuple = translateToCaller(dstDescTuple, baseTuple); + NTuple srcDescTuple = flowEdge.getInitTuple(); + NTuple dstDescTuple = flowEdge.getEndTuple(); + + FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple); + + if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { + // destination node is started with 'parameter' + // need to translate it in terms of the caller's a node + srcDescTuple = + translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple); + } + + if (calleeSubGlobalGraph.isParameter(dstDescTuple)) { + // destination node is started with 'parameter' + // need to translate it in terms of the caller's a node + dstDescTuple = + translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), dstDescTuple); } - callerSubGlobalGraph.addValueFlowEdge(callerSrcTuple, dstDescTuple); + callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple); if (!visited.contains(dstNode)) { visited.add(dstNode); - recurAddValueFlowsFromCalleeParam(calleeSubGlobalGraph, dstNode, callerSubGlobalGraph, + recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph, dstDescTuple, visited, baseTuple); } @@ -391,6 +402,40 @@ public class LocationInference { } + private NTuple translateToCaller(MethodInvokeNode min, int paramIdx, + NTuple srcDescTuple) { + + NTuple callerTuple = new NTuple(); + + NTuple argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); + + for (int i = 0; i < argTuple.size(); i++) { + callerTuple.add(argTuple.get(i)); + } + + for (int i = 1; i < srcDescTuple.size(); i++) { + callerTuple.add(srcDescTuple.get(i)); + } + + return callerTuple; + } + + private NTuple traslateToCalleeParamTupleToCallerArgTuple( + NTuple calleeInitTuple, NTuple callerSrcTuple) { + + NTuple callerInitTuple = new NTuple(); + + for (int i = 0; i < callerSrcTuple.size(); i++) { + callerInitTuple.add(callerSrcTuple.get(i)); + } + + for (int i = 1; i < calleeInitTuple.size(); i++) { + callerInitTuple.add(calleeInitTuple.get(i)); + } + + return callerInitTuple; + } + private NTuple translateToCaller(NTuple dstDescTuple, NTuple baseTuple) { NTuple callerDescTuple = new NTuple(); @@ -2010,39 +2055,28 @@ public class LocationInference { FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i); FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k); - NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i); - NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k); - - for (Iterator> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) { - NTuple arg1Tuple = iter1.next(); - - for (Iterator> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) { - NTuple arg2Tuple = iter2.next(); - - // check if the callee propagates an ordering constraints through - // parameters - - Set localReachSet = - calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); + NTuple arg1Tuple = getNodeTupleByArgIdx(min, i); + NTuple arg2Tuple = getNodeTupleByArgIdx(min, k); - if (localReachSet.contains(paramNode2)) { - // need to propagate an ordering relation s.t. arg1 is higher - // than arg2 + // check if the callee propagates an ordering constraints through + // parameters - System.out - .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); - System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" - + arg2Tuple); + Set localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); - // otherwise, flows between method/field locations... - callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); - System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); + if (localReachSet.contains(paramNode2)) { + // need to propagate an ordering relation s.t. arg1 is higher + // than arg2 - } + System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); + System.out + .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple); - } + // otherwise, flows between method/field locations... + callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); + System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); } + System.out.println(); } } @@ -2082,8 +2116,11 @@ public class LocationInference { System.out.println("param2=" + paramNode2 + " curDescTuple=" + paramNode2.getCurrentDescTuple()); - NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i); - NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k); + // TODO: deprecated method + // NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i); + // NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k); + NodeTupleSet tupleSetArg1 = null; + NodeTupleSet tupleSetArg2 = null; for (Iterator> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) { NTuple arg1Tuple = iter1.next(); @@ -2491,8 +2528,10 @@ public class LocationInference { CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k); if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) { - NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i); - NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k); + // NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i); + // NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k); + NodeTupleSet argDescTupleSet1 = null; + NodeTupleSet argDescTupleSet2 = null; // the callee has the relation in which param1 is higher than param2 // therefore, the caller has to have the relation in which arg1 is @@ -3963,10 +4002,11 @@ public class LocationInference { implicitFlowTupleSet, false); assert (baseNodeSet.size() == 1); - mapMethodInvokeNodeToBaseTuple.put(min, baseNodeSet.iterator().next()); + NTuple baseTuple = baseNodeSet.iterator().next(); + mapMethodInvokeNodeToBaseTuple.put(min, baseTuple); if (!min.getMethod().isStatic()) { - addArgIdxMap(min, 0, baseNodeSet); + addArgIdxMap(min, 0, baseTuple); for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { FlowNode returnNode = (FlowNode) iterator.next(); @@ -3974,14 +4014,11 @@ public class LocationInference { if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) { // the location type of the return value is started with 'this' // reference - for (Iterator> baseIter = baseNodeSet.iterator(); baseIter - .hasNext();) { - NTuple baseTuple = baseIter.next(); - NTuple inFlowTuple = new NTuple(baseTuple.getList()); - inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); - nodeSet.addTuple(inFlowTuple); - } + NTuple inFlowTuple = new NTuple(baseTuple.getList()); + inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); + nodeSet.addTuple(inFlowTuple); } else { + // TODO Set inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode); for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) { FlowNode inFlowNode = (FlowNode) iterator2.next(); @@ -4012,7 +4049,21 @@ public class LocationInference { NodeTupleSet argTupleSet = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false); // if argument is liternal node, argTuple is set to NULL. - addArgIdxMap(min, idx, argTupleSet); + + NTuple argTuple = new NTuple(); + if (argTupleSet.size() > 1) { + NTuple interTuple = + getFlowGraph(md).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + argTuple = interTuple; + } else { + argTuple = argTupleSet.iterator().next(); + } + + addArgIdxMap(min, idx, argTuple); FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) || calleeMethodDesc.getModifiers().isNative()) { @@ -4041,48 +4092,20 @@ public class LocationInference { return false; } - private NodeTupleSet getNodeTupleSetByArgIdx(MethodInvokeNode min, int idx) { + private NTuple getNodeTupleByArgIdx(MethodInvokeNode min, int idx) { return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx)); } - private void addArgIdxMap(MethodInvokeNode min, int idx, NodeTupleSet tupleSet) { - Map mapIdxToTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min); - if (mapIdxToTupleSet == null) { - mapIdxToTupleSet = new HashMap(); - mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTupleSet); + private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple argTuple /* + * NodeTupleSet + * tupleSet + */) { + Map> mapIdxToTuple = mapMethodInvokeNodeToArgIdxMap.get(min); + if (mapIdxToTuple == null) { + mapIdxToTuple = new HashMap>(); + mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTuple); } - mapIdxToTupleSet.put(new Integer(idx), tupleSet); - } - - private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable, - MethodInvokeNode min, NodeTupleSet nodeSet) { - - if (min.numArgs() > 0) { - - int offset; - if (min.getMethod().isStatic()) { - offset = 0; - } else { - offset = 1; - // NTuple thisArgTuple = new NTuple(); - // thisArgTuple.add(callermd.getThis()); - // NodeTupleSet argTupleSet = new NodeTupleSet(); - // argTupleSet.addTuple(thisArgTuple); - // addArgIdxMap(min, 0, argTupleSet); - // nodeSet.addTuple(thisArgTuple); - } - - for (int i = 0; i < min.numArgs(); i++) { - ExpressionNode en = min.getArg(i); - NodeTupleSet argTupleSet = new NodeTupleSet(); - analyzeFlowExpressionNode(callermd, nametable, en, argTupleSet, false); - // if argument is liternal node, argTuple is set to NULL. - addArgIdxMap(min, i + offset, argTupleSet); - nodeSet.addTupleSet(argTupleSet); - } - - } - + mapIdxToTuple.put(new Integer(idx), argTuple); } private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) { -- 2.34.1