From c4e15379352959519956d9b77b723f441aa237b3 Mon Sep 17 00:00:00 2001 From: yeom Date: Sat, 6 Oct 2012 00:24:30 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/SSJava/FlowGraph.java | 2 + .../src/Analysis/SSJava/GlobalFlowGraph.java | 18 +- .../src/Analysis/SSJava/GlobalFlowNode.java | 8 + .../Analysis/SSJava/LocationInference.java | 293 ++++++++++++++++-- 4 files changed, 290 insertions(+), 31 deletions(-) diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index e2783bf6..ded08373 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -711,4 +711,6 @@ public class FlowGraph { bw.write("}\n"); } + + } \ No newline at end of file diff --git a/Robust/src/Analysis/SSJava/GlobalFlowGraph.java b/Robust/src/Analysis/SSJava/GlobalFlowGraph.java index 490ab585..9e8d26d8 100644 --- a/Robust/src/Analysis/SSJava/GlobalFlowGraph.java +++ b/Robust/src/Analysis/SSJava/GlobalFlowGraph.java @@ -11,6 +11,7 @@ import java.util.Set; import IR.Descriptor; import IR.MethodDescriptor; +import IR.Tree.MethodInvokeNode; public class GlobalFlowGraph { @@ -21,15 +22,19 @@ public class GlobalFlowGraph { Map mapLocationToInferCompositeLocation; - Map, NTuple>> mapCalleeToMapCallerArgToCalleeArg; - public GlobalFlowGraph(MethodDescriptor md) { this.md = md; this.mapLocTupleToNode = new HashMap, GlobalFlowNode>(); this.mapFlowNodeToOutNodeSet = new HashMap>(); this.mapLocationToInferCompositeLocation = new HashMap(); - this.mapCalleeToMapCallerArgToCalleeArg = - new HashMap, NTuple>>(); + } + + public MethodDescriptor getMethodDescriptor() { + return md; + } + + public Map getMapLocationToInferCompositeLocation() { + return mapLocationToInferCompositeLocation; } public GlobalFlowNode getFlowNode(NTuple locTuple) { @@ -39,7 +44,7 @@ public class GlobalFlowGraph { } return mapLocTupleToNode.get(locTuple); } - + private GlobalFlowNode createNewGlobalFlowNode(NTuple locTuple) { GlobalFlowNode node = new GlobalFlowNode(locTuple); return node; @@ -53,7 +58,7 @@ public class GlobalFlowGraph { // if both old and new do not share the prefix, throw error CompositeLocation oldCompLoc = mapLocationToInferCompositeLocation.get(loc); - if (newCompLoc.getSize() > oldCompLoc.getSize()) { + if (newCompLoc.getSize() == oldCompLoc.getSize()) { for (int i = 0; i < oldCompLoc.getSize(); i++) { Location oldLocElement = oldCompLoc.get(i); Location newLocElement = newCompLoc.get(i); @@ -62,6 +67,7 @@ public class GlobalFlowGraph { throw new Error("Failed to generate a composite location"); } } + } else if (newCompLoc.getSize() > oldCompLoc.getSize()) { mapLocationToInferCompositeLocation.put(loc, newCompLoc); } diff --git a/Robust/src/Analysis/SSJava/GlobalFlowNode.java b/Robust/src/Analysis/SSJava/GlobalFlowNode.java index a1371d79..03f96b28 100644 --- a/Robust/src/Analysis/SSJava/GlobalFlowNode.java +++ b/Robust/src/Analysis/SSJava/GlobalFlowNode.java @@ -56,6 +56,14 @@ public class GlobalFlowNode { return id; } + public void setInferCompositeLocation(CompositeLocation in) { + this.compLoc = in; + } + + public CompositeLocation getInferCompositeLocation() { + return compLoc; + } + public String getPrettyID() { NTuple descTuple = getDescTuple(); diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 32b3a124..981d942b 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -116,6 +116,8 @@ public class LocationInference { // set of callees reachable from the method private Map mapMethodDescriptorToSubGlobalFlowGraph; + private Map, NTuple>> mapMethodInvokeNodeToMapCallerArgToCalleeArg; + public static final String GLOBALLOC = "GLOBALLOC"; public static final String TOPLOC = "TOPLOC"; @@ -167,7 +169,10 @@ public class LocationInference { this.mapDescToLocationSummary = new HashMap(); - mapMethodDescriptorToSubGlobalFlowGraph = new HashMap(); + this.mapMethodDescriptorToSubGlobalFlowGraph = new HashMap(); + + this.mapMethodInvokeNodeToMapCallerArgToCalleeArg = + new HashMap, NTuple>>(); } @@ -263,13 +268,234 @@ public class LocationInference { } + public Map, NTuple> getMapCallerArgToCalleeParam( + MethodInvokeNode min) { + + if (!mapMethodInvokeNodeToMapCallerArgToCalleeArg.containsKey(min)) { + mapMethodInvokeNodeToMapCallerArgToCalleeArg.put(min, + new HashMap, NTuple>()); + } + + return mapMethodInvokeNodeToMapCallerArgToCalleeArg.get(min); + } + + public void addMapCallerArgToCalleeParam(MethodInvokeNode min, NTuple callerArg, + NTuple calleeParam) { + // System.out.println("min=" + min + " arg=" + callerArg + " param=" + calleeParam); + getMapCallerArgToCalleeParam(min).put(callerArg, calleeParam); + } + private void assignCompositeLocation() { calculateGlobalValueFlowCompositeLocation(); translateCompositeLocationAssignmentToFlowGraph(); + _debug_printGraph(); } private void translateCompositeLocationAssignmentToFlowGraph() { - + + MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); + translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); + + } + + private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) { + + System.out.println("\n#translateCompositeLocationAssignmentToFlowGraph=" + mdCaller); + + // First, assign a composite location to a node in the flow graph + GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller); + + FlowGraph callerFlowGraph = getFlowGraph(mdCaller); + Map callerMapLocToCompLoc = + callerGlobalFlowGraph.getMapLocationToInferCompositeLocation(); + Set methodLocSet = callerMapLocToCompLoc.keySet(); + for (Iterator iterator = methodLocSet.iterator(); iterator.hasNext();) { + Location methodLoc = (Location) iterator.next(); + if (methodLoc.getDescriptor().equals(mdCaller)) { + CompositeLocation inferCompLoc = callerMapLocToCompLoc.get(methodLoc); + assignCompositeLocationToFlowGraph(callerFlowGraph, methodLoc, inferCompLoc); + } + } + + Set minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); + + Set calleeSet = new HashSet(); + for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + // need to translate a composite location that is started with the base tuple of 'min'. + translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min); + calleeSet.add(min.getMethod()); + } + + for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { + MethodDescriptor callee = (MethodDescriptor) iterator.next(); + translateCompositeLocationAssignmentToFlowGraph(callee); + } + + } + + public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc, + CompositeLocation inferCompLoc) { + Descriptor localDesc = loc.getLocDescriptor(); + + Set nodeSet = flowGraph.getNodeSet(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode node = (FlowNode) iterator.next(); + if (node.getDescTuple().startsWith(localDesc)) { + // need to assign the inferred composite location to this node + CompositeLocation newCompLoc = generateCompositeLocation(node.getDescTuple(), inferCompLoc); + node.setCompositeLocation(newCompLoc); + System.out.println("SET Node=" + node + " inferCompLoc=" + newCompLoc); + } + } + } + + private CompositeLocation generateCompositeLocation(NTuple nodeDescTuple, + CompositeLocation inferCompLoc) { + + System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc=" + + inferCompLoc); + + CompositeLocation newCompLoc = new CompositeLocation(); + for (int i = 0; i < inferCompLoc.getSize(); i++) { + newCompLoc.addLocation(inferCompLoc.get(i)); + } + + Descriptor lastDescOfPrefix = nodeDescTuple.get(0); + Descriptor enclosingDescriptor; + if (lastDescOfPrefix instanceof InterDescriptor) { + enclosingDescriptor = null; + } else { + enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); + } + + for (int i = 1; i < nodeDescTuple.size(); i++) { + Descriptor desc = nodeDescTuple.get(i); + Location locElement = new Location(enclosingDescriptor, desc); + newCompLoc.addLocation(locElement); + + enclosingDescriptor = ((FieldDescriptor) desc).getClassDescriptor(); + } + + return newCompLoc; + } + + private void translateMapLocationToInferCompositeLocationToCalleeGraph( + GlobalFlowGraph callerGraph, MethodInvokeNode min) { + + MethodDescriptor mdCallee = min.getMethod(); + MethodDescriptor mdCaller = callerGraph.getMethodDescriptor(); + Map callerMapLocToCompLoc = + callerGraph.getMapLocationToInferCompositeLocation(); + + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + GlobalFlowGraph calleeGlobalGraph = getSubGlobalFlowGraph(mdCallee); + + NTuple baseLocTuple = + translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min)); + + System.out.println("-translate caller infer composite loc to callee=" + mdCallee); + Set keySet = callerMapLocToCompLoc.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Location key = (Location) iterator.next(); + CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(key); + + if (!key.getDescriptor().equals(mdCaller) + && callerCompLoc.getTuple().startsWith(baseLocTuple)) { + // need to translate to the callee side + // System.out.println("need to translate callerCompLoc=" + callerCompLoc + + // " with baseTuple=" + // + baseLocTuple); + // TODO + CompositeLocation newCalleeCompLoc = + translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); + calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); + System.out.println("---callee loc=" + key + " newCalleeCompLoc=" + newCalleeCompLoc); + } + } + + // If the location of an argument has a composite location + // need to assign a proper composite location to the corresponding callee parameter + System.out.println("-translate arg composite location to callee param:"); + Map> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min); + Set idxSet = mapIdxToArgTuple.keySet(); + for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) { + Integer idx = (Integer) iterator.next(); + + if (idx == 0 && !min.getMethod().isStatic()) { + continue; + } + + NTuple argTuple = mapIdxToArgTuple.get(idx); + + // check if an arg tuple has been already assigned to a composite location + NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); + Location argLocalLoc = argLocTuple.get(0); + + // if (!isPrimitiveType(argTuple)) { + if (callerMapLocToCompLoc.containsKey(argLocalLoc)) { + + CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc); + for (int i = 1; i < argLocTuple.size(); i++) { + callerCompLoc.addLocation(argLocTuple.get(i)); + } + + if (callerCompLoc.getTuple().startsWith(baseLocTuple)) { + + FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx); + NTuple calleeParamDescTuple = calleeParamFlowNode.getDescTuple(); + NTuple calleeParamLocTuple = + translateToLocTuple(mdCallee, calleeParamDescTuple); + + CompositeLocation newCalleeCompLoc = + translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); + + calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), + newCalleeCompLoc); + + System.out.println("###need to assign composite location to=" + calleeParamDescTuple + + " with baseTuple=" + baseLocTuple); + System.out.println("---newCalleeCompLoc=" + newCalleeCompLoc); + } + + } + + } + + } + + private boolean isPrimitiveType(NTuple argTuple) { + + Descriptor lastDesc = argTuple.get(argTuple.size() - 1); + + if (lastDesc instanceof FieldDescriptor) { + return ((FieldDescriptor) lastDesc).getType().isPrimitive(); + } else if (lastDesc instanceof VarDescriptor) { + return ((VarDescriptor) lastDesc).getType().isPrimitive(); + } + + return true; + } + + private CompositeLocation translateCompositeLocationToCallee(CompositeLocation callerCompLoc, + NTuple baseLocTuple, MethodDescriptor mdCallee) { + + CompositeLocation newCalleeCompLoc = new CompositeLocation(); + + // replace the last element of the caller compLoc with the 'this' location of the callee + for (int i = 0; i < baseLocTuple.size() - 1; i++) { + newCalleeCompLoc.addLocation(baseLocTuple.get(i)); + } + + Location calleeThisLoc = new Location(mdCallee, mdCallee.getThis()); + newCalleeCompLoc.addLocation(calleeThisLoc); + + for (int i = baseLocTuple.size(); i < callerCompLoc.getSize(); i++) { + newCalleeCompLoc.addLocation(callerCompLoc.get(i)); + } + + return newCalleeCompLoc; + } private void constructGlobalFlowGraph() { @@ -289,7 +515,7 @@ public class LocationInference { FlowGraph flowGraph = getFlowGraph(md); FlowGraph subGlobalFlowGraph = flowGraph.clone(); - + // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); @@ -324,19 +550,17 @@ public class LocationInference { System.out.println("SSJAVA: Calculate composite locations in the global value flow graph"); MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop(); - GlobalFlowGraph graph = getSubGlobalFlowGraph(methodDescEventLoop); + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop); Set> prefixSet = new HashSet>(); - Set nodeSet = graph.getNodeSet(); + Set nodeSet = globalFlowGraph.getNodeSet(); next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { GlobalFlowNode node = (GlobalFlowNode) iterator.next(); - Set incomingNodeSet = graph.getIncomingNodeSet(node); - - List> prefixList = calculatePrefixList(graph, node); - - Set reachNodeSet = graph.getReachableNodeSetFrom(node); + Set incomingNodeSet = globalFlowGraph.getIncomingNodeSet(node); + List> prefixList = calculatePrefixList(globalFlowGraph, node); + Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); // System.out.println("node=" + node + " inNodeSet=" + incomingNodeSet // + " reachableNodeSet=" + reachNodeSet); @@ -356,7 +580,10 @@ public class LocationInference { CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix); System.out.println("- newCompLoc=" + newCompLoc); - // flowNode.setCompositeLocation(newCompLoc); + + Location targetLocalLoc = node.getLocTuple().get(0); + globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); + continue next; } @@ -367,6 +594,15 @@ public class LocationInference { // System.out.println("inNodeSet=" + inNodeSet + " from=" + node); } + private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) { + CompositeLocation newCompLoc = compLocPrefix.clone(); + NTuple locTuple = node.getLocTuple(); + for (int i = 1; i < locTuple.size(); i++) { + newCompLoc.addLocation(locTuple.get(i)); + } + node.setInferCompositeLocation(newCompLoc); + } + private List> calculatePrefixList(GlobalFlowGraph graph, GlobalFlowNode node) { System.out.println("\n##### calculatePrefixList=" + node); @@ -450,6 +686,7 @@ public class LocationInference { NTuple locTuple = new NTuple(); Descriptor enclosingDesc = md; + System.out.println("md=" + md + " descTuple=" + descTuple); for (int i = 0; i < descTuple.size(); i++) { Descriptor desc = descTuple.get(i); @@ -505,15 +742,22 @@ public class LocationInference { private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) { - NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); + Map> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min); - NTuple baseLocTuple = translateToLocTuple(mdCaller, baseTuple); + Set keySet = mapIdxToArg.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Integer idx = (Integer) iterator.next(); + NTuple argDescTuple = mapIdxToArg.get(idx); + NTuple argLocTuple = translateToLocTuple(mdCaller, argDescTuple); - FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); + NTuple paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple(); + NTuple paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple); + addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple); + } - GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee); - Set calleeNodeSet = calleeSubGlobalGraph.getNodeSet(); for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) { GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next(); @@ -2586,11 +2830,6 @@ public class LocationInference { return false; } - public boolean isPrimitiveLocalVariable(FlowNode node) { - VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0); - return varDesc.getType().isPrimitive(); - } - private SSJavaLattice getLattice(Descriptor d) { if (d instanceof MethodDescriptor) { return getMethodLattice((MethodDescriptor) d); @@ -2745,7 +2984,7 @@ public class LocationInference { System.out.println("##constructSubGlobalFlowGraph"); GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg); mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); - + // TODO System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph"); addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); @@ -2756,7 +2995,7 @@ public class LocationInference { } } - _debug_printGraph(); + // _debug_printGraph(); } @@ -3470,11 +3709,15 @@ public class LocationInference { addFlowGraphEdge(md, tuple, interTuple); } argTuple = interTuple; - } else { + } else if (argTupleSet.size() == 1) { argTuple = argTupleSet.iterator().next(); + } else { + argTuple = new NTuple(); } - addArgIdxMap(min, idx, argTuple); + if (argTuple.size() != 0) { + addArgIdxMap(min, idx, argTuple); + } FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) || calleeMethodDesc.getModifiers().isNative()) { -- 2.34.1