X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLocationInference.java;h=0967c58b5986b90f2c47dadfa256bb0390bf1989;hp=dfa8e0e72735a6c1364a78a7fe004624d4950773;hb=76263fb08dca40e3c50ec9403ff4ddd02c35bfe1;hpb=561af6103d5d245d56589c369041dccddf43cf48 diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index dfa8e0e7..0967c58b 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -114,7 +114,9 @@ public class LocationInference { // maps a method descriptor to a sub global flow graph that captures all value flows caused by the // set of callees reachable from the method - private Map mapMethodDescriptorToSubGlobalFlowGraph; + private Map mapMethodDescriptorToSubGlobalFlowGraph; + + private Map, NTuple>> mapMethodInvokeNodeToMapCallerArgToCalleeArg; public static final String GLOBALLOC = "GLOBALLOC"; @@ -167,7 +169,10 @@ public class LocationInference { this.mapDescToLocationSummary = new HashMap(); - mapMethodDescriptorToSubGlobalFlowGraph = new HashMap(); + this.mapMethodDescriptorToSubGlobalFlowGraph = new HashMap(); + + this.mapMethodInvokeNodeToMapCallerArgToCalleeArg = + new HashMap, NTuple>>(); } @@ -215,7 +220,9 @@ public class LocationInference { // 1) construct value flow graph constructFlowGraph(); - constructGlobalFlowGraph(); + assignCompositeLocation(); + + // constructGlobalFlowGraph(); System.exit(0); @@ -246,7 +253,7 @@ public class LocationInference { // 2) construct lattices inferLattices(); - simplifyLattices(); + // simplifyLattices(); // 3) check properties checkLattices(); @@ -261,6 +268,241 @@ 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) { + 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'. + if (mapMethodInvokeNodeToBaseTuple.get(min) != null) { + // if mapMethodInvokeNodeToBaseTuple doesn't have a mapping + // it means that the corresponding callee method does not cause any + // flows + 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() { System.out.println(""); @@ -278,27 +520,210 @@ public class LocationInference { FlowGraph flowGraph = getFlowGraph(md); FlowGraph subGlobalFlowGraph = flowGraph.clone(); - mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); - addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); - try { - subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); - } catch (IOException e) { - e.printStackTrace(); - } + // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + + // try { + // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); + // } catch (IOException e) { + // e.printStackTrace(); + // } // FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); // mapMethodDescriptorToFlowGraph.put(md, fg); // analyzeMethodBody(md.getClassDesc(), md); } } + + // DEBUG: write a global flow graph + MethodDescriptor mdContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop(); + // FlowGraph globalFlowGraph = + // getSubGlobalFlowGraph(mdContainingSSJavaLoop); + // System.out.println("GLOBAL NODE SET=" + globalFlowGraph.getNodeSet()); + // assignCompositeLocation(globalFlowGraph); + // try { + // globalFlowGraph.writeGraph("_GLOBAL"); + // } catch (IOException e) { + // e.printStackTrace(); + // } // _debug_printGraph(); } + private void calculateGlobalValueFlowCompositeLocation() { + + System.out.println("SSJAVA: Calculate composite locations in the global value flow graph"); + MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop(); + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop); + + Set> prefixSet = new HashSet>(); + + Set nodeSet = globalFlowGraph.getNodeSet(); + + next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode node = (GlobalFlowNode) iterator.next(); + Set incomingNodeSet = globalFlowGraph.getIncomingNodeSet(node); + List> prefixList = calculatePrefixList(globalFlowGraph, node); + Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); + + // System.out.println("node=" + node + " inNodeSet=" + incomingNodeSet + // + " reachableNodeSet=" + reachNodeSet); + + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachNodeSet.iterator(); iterator2.hasNext();) { + GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next(); + if (reachNode.getLocTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getLocTuple()); + } + } + + if (!reachableCommonPrefixSet.isEmpty()) { + + // TODO + if (!node.getLocTuple().startsWith(curPrefix.get(0))) { + CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); + System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix); + System.out.println("- newCompLoc=" + newCompLoc); + + Location targetLocalLoc = node.getLocTuple().get(0); + globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); + + continue next; + } + + } + + } + + } + // Set inNodeSet = + // graph.getIncomingNodeSetWithPrefix(prefix); + // 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); + + Set incomingNodeSet = graph.getIncomingNodeSet(node); + + List> prefixList = new ArrayList>(); + + for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode inNode = (GlobalFlowNode) iterator.next(); + NTuple inNodeTuple = inNode.getLocTuple(); + + for (int i = 1; i < inNodeTuple.size(); i++) { + NTuple prefix = inNodeTuple.subList(0, i); + if (!prefixList.contains(prefix)) { + prefixList.add(prefix); + } + } + } + + Collections.sort(prefixList, new Comparator>() { + public int compare(NTuple arg0, NTuple arg1) { + int s0 = arg0.size(); + int s1 = arg1.size(); + if (s0 > s1) { + return -1; + } else if (s0 == s1) { + return 0; + } else { + return 1; + } + } + }); + return prefixList; + } + + private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) { + + MethodDescriptor md = flowGraph.getMethodDescriptor(); + + GlobalFlowGraph globalGraph = new GlobalFlowGraph(md); + + // Set nodeSet = flowGraph.getNodeSet(); + Set edgeSet = flowGraph.getEdgeSet(); + + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + + FlowEdge edge = (FlowEdge) iterator.next(); + NTuple srcDescTuple = edge.getInitTuple(); + NTuple dstDescTuple = edge.getEndTuple(); + + // here only keep the first element(method location) of the descriptor + // tuple + NTuple srcLocTuple = translateToLocTuple(md, srcDescTuple); + // Location srcMethodLoc = srcLocTuple.get(0); + // Descriptor srcVarDesc = srcMethodLoc.getLocDescriptor(); + // // if (flowGraph.isParamDesc(srcVarDesc) && + // (!srcVarDesc.equals(md.getThis()))) { + // if (!srcVarDesc.equals(md.getThis())) { + // srcLocTuple = new NTuple(); + // Location loc = new Location(md, srcVarDesc); + // srcLocTuple.add(loc); + // } + // + NTuple dstLocTuple = translateToLocTuple(md, dstDescTuple); + // Location dstMethodLoc = dstLocTuple.get(0); + // Descriptor dstVarDesc = dstMethodLoc.getLocDescriptor(); + // if (!dstVarDesc.equals(md.getThis())) { + // dstLocTuple = new NTuple(); + // Location loc = new Location(md, dstVarDesc); + // dstLocTuple.add(loc); + // } + + globalGraph.addValueFlowEdge(srcLocTuple, dstLocTuple); + + } + + return globalGraph; + } + + private NTuple translateToLocTuple(MethodDescriptor md, NTuple descTuple) { + + 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); + + Location loc = new Location(enclosingDesc, desc); + locTuple.add(loc); + + if (desc instanceof VarDescriptor) { + enclosingDesc = ((VarDescriptor) desc).getType().getClassDesc(); + } else if (desc instanceof FieldDescriptor) { + enclosingDesc = ((FieldDescriptor) desc).getType().getClassDesc(); + } else { + // TODO: inter descriptor case + enclosingDesc = desc; + } + + } + + return locTuple; + + } + private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller, - FlowGraph subGlobalFlowGraph) { + GlobalFlowGraph subGlobalFlowGraph) { // the transformation for a call site propagates flows through parameters // if the method is virtual, it also grab all relations from any possible @@ -322,7 +747,6 @@ public class LocationInference { for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee); - // propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee); } } @@ -332,32 +756,254 @@ public class LocationInference { private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) { + System.out.println("propagateValueFlowsToCallerFromSubGlobalFlowGraph=" + min.printNode(0) + + " by caller=" + mdCaller); + FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); + Map> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min); + + System.out.println("mapMethodInvokeNodeToArgIdxMap.get(min)=" + + mapMethodInvokeNodeToArgIdxMap.get(min)); + Set keySet = mapIdxToArg.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Integer idx = (Integer) iterator.next(); + NTuple argDescTuple = mapIdxToArg.get(idx); + if (argDescTuple.size() > 0) { + NTuple argLocTuple = translateToLocTuple(mdCaller, argDescTuple); + NTuple paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple(); + NTuple paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple); + addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple); + } + + } + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee); + Set calleeNodeSet = calleeSubGlobalGraph.getNodeSet(); + System.out.println("#calleeNodeSet=" + calleeNodeSet); + for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next(); + addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode); + } + + // int numParam = calleeFlowGraph.getNumParameters(); + // for (int idx = 0; idx < numParam; idx++) { + // + // FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + // + // NTuple paramLocTuple = + // translateToLocTuple(possibleMdCallee, paramNode.getCurrentDescTuple()); + // + // GlobalFlowNode globalParamNode = + // calleeSubGlobalGraph.getFlowNode(paramLocTuple); + // + // NTuple argTuple = + // mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); + // + // NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); + // + // System.out.println("argTupleSet=" + argLocTuple + " param=" + + // paramLocTuple); + // // here, it adds all value flows reachable from the paramNode in the + // callee's flow graph + // + // addValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, + // possibleMdCallee, + // globalParamNode); + // } + // + // // TODO + // // FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + // // FlowGraph calleeSubGlobalGraph = + // getSubGlobalFlowGraph(possibleMdCallee); + // // + // // int numParam = calleeSubGlobalGraph.getNumParameters(); + // // for (int idx = 0; idx < numParam; idx++) { + // // FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx); + // // 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 addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor mdCallee, GlobalFlowNode calleeSrcNode) { + + GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); + GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + + NTuple callerSrcNodeLocTuple = + translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple()); + + + if (callerSrcNodeLocTuple != null) { + Set outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeSrcNode); + + for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode outNode = (GlobalFlowNode) iterator.next(); + NTuple callerDstNodeLocTuple = + translateToCallerLocTuple(min, mdCallee, mdCaller, outNode.getLocTuple()); + if (callerDstNodeLocTuple != null) { + callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple); + } + } + } - FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); - FlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee); + } - int numParam = calleeSubGlobalGraph.getNumParameters(); - for (int idx = 0; idx < numParam; idx++) { - FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx); - 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 NTuple translateToCallerLocTuple(MethodInvokeNode min, + MethodDescriptor mdCallee, MethodDescriptor mdCaller, NTuple nodeLocTuple) { + // this method will return NULL if the corresponding argument is literal + // value. + // assumes that we don't need to propagate callee flows to the argument + // which is literal. + + System.out.println("---translateToCallerLocTuple=" + min.printNode(0) + + " callee nodeLocTuple=" + nodeLocTuple); + + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + + NTuple nodeDescTuple = translateToDescTuple(nodeLocTuple); + if (calleeFlowGraph.isParameter(nodeDescTuple)) { + int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple); + NTuple argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); + // System.out.println(" mapMethodInvokeNodeToArgIdxMap.get(min)=" + // + mapMethodInvokeNodeToArgIdxMap.get(min)); + + if (argDescTuple.size() == 0) { + // argument is literal + return null; + } + NTuple argLocTuple = translateToLocTuple(mdCaller, argDescTuple); + + NTuple callerLocTuple = new NTuple(); + + callerLocTuple.addAll(argLocTuple); + for (int i = 1; i < nodeLocTuple.size(); i++) { + callerLocTuple.add(nodeLocTuple.get(i)); + } + return callerLocTuple; + } else { + return nodeLocTuple.clone(); + } + + } + + private NTuple translateToDescTuple(NTuple locTuple) { + + NTuple descTuple = new NTuple(); + for (int i = 0; i < locTuple.size(); i++) { + descTuple.add(locTuple.get(i).getLocDescriptor()); } + return descTuple; + + } + + private void addValueFlowsFromCalleeParam(MethodDescriptor mdCaller, + NTuple argLocTuple, NTuple baseLocTuple, MethodDescriptor mdCallee, + GlobalFlowNode globalParamNode) { + + Set visited = new HashSet(); + visited.add(globalParamNode); + recurAddValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, mdCallee, + globalParamNode); + + } + + private void recurAddValueFlowsFromCalleeParam(MethodDescriptor mdCaller, + NTuple argLocTuple, NTuple baseLocTuple, MethodDescriptor mdCallee, + GlobalFlowNode calleeCurNode) { + + // FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + // GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); + // + // NTuple curNodeLocTuple = calleeCurNode.getLocTuple(); + // NTuple curNodeDescTuple = calleeCurNode.getDescTuple(); + // if (calleeFlowGraph.isParameter(curNodeDescTuple)) { + // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple); + // } + // + // Set outNodeSet = + // calleeSubGlobalGraph.getOutNodeSet(calleeCurNode); + // for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) { + // GlobalFlowNode outNode = (GlobalFlowNode) iterator.next(); + // + // NTuple curNodeLocTuple = calleeCurNode.getLocTuple(); + // NTuple curNodeDescTuple = calleeCurNode.getDescTuple(); + // if (calleeFlowGraph.isParameter(curNodeDescTuple)) { + // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple); + // } + // + // outNode.getDescTuple(); + // + // if (calleeFlowGraph.is) + // + // 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); + // } + // + // } + // + // Set edgeSet = + // calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); + // for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + // FlowEdge flowEdge = (FlowEdge) iterator.next(); + // + // 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(srcDescTuple, dstDescTuple); + // + // if (!visited.contains(dstNode)) { + // visited.add(dstNode); + // recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, + // callerSubGlobalGraph, + // dstDescTuple, visited, baseTuple); + // } + // + // } } - private void addValueFlowsFromCalleeParam(MethodInvokeNode min, FlowGraph calleeSubGlobalGraph, - FlowNode paramNode, FlowGraph callerSubGlobalGraph, NTuple argTuple, - NTuple baseTuple) { + private NTuple translateToCaller(NTuple argLocTuple, + NTuple curNodeLocTuple) { - Set visited = new HashSet(); + NTuple callerLocTuple = new NTuple(); + + callerLocTuple.addAll(argLocTuple); + for (int i = 1; i < curNodeLocTuple.size(); i++) { + callerLocTuple.add(curNodeLocTuple.get(i)); + } - visited.add(paramNode); - recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode, callerSubGlobalGraph, - argTuple, visited, baseTuple); + return callerLocTuple; } private void recurAddValueFlowsFromCalleeParam(MethodInvokeNode min, @@ -366,7 +1012,8 @@ public class LocationInference { 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(); @@ -436,18 +1083,6 @@ public class LocationInference { return callerInitTuple; } - private NTuple translateToCaller(NTuple dstDescTuple, - NTuple baseTuple) { - NTuple callerDescTuple = new NTuple(); - - callerDescTuple.addAll(baseTuple); - for (int i = 1; i < dstDescTuple.size(); i++) { - callerDescTuple.add(dstDescTuple.get(i)); - } - - return callerDescTuple; - } - public LocationSummary getLocationSummary(Descriptor d) { if (!mapDescToLocationSummary.containsKey(d)) { if (d instanceof MethodDescriptor) { @@ -470,7 +1105,8 @@ public class LocationInference { FlowGraph flowGraph = getFlowGraph(md); MethodSummary methodSummary = getMethodSummary(md); - // construct a parameter mapping that maps a parameter descriptor to an inferred composite + // construct a parameter mapping that maps a parameter descriptor to an + // inferred composite // location for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) { @@ -590,14 +1226,16 @@ public class LocationInference { // System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc); // HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc); - // HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone(); + // HierarchyGraph skeletonGraphWithCombinationNode = + // skeletonGraph.clone(); // skeletonGraphWithCombinationNode.setName(desc + "_SC"); // // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); // System.out.println("Identifying Combination Nodes:"); // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph); // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph(); - // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode); + // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, + // skeletonGraphWithCombinationNode); } } @@ -1248,168 +1886,14 @@ public class LocationInference { } - private void simplifyLattices() { + private void checkLattices() { - setupToAnalyze(); + LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); - while (!toAnalyzeIsEmpty()) { - ClassDescriptor cd = toAnalyzeNext(); - setupToAnalazeMethod(cd); - - SSJavaLattice classLattice = cd2lattice.get(cd); - if (classLattice != null) { - System.out.println("@@@check lattice=" + cd); - checkLatticeProperty(cd, classLattice); - } - - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); - SSJavaLattice methodLattice = md2lattice.get(md); - if (methodLattice != null) { - System.out.println("@@@check lattice=" + md); - checkLatticeProperty(md, methodLattice); - } - } - } - - setupToAnalyze(); - - while (!toAnalyzeIsEmpty()) { - ClassDescriptor cd = toAnalyzeNext(); - - setupToAnalazeMethod(cd); - - SSJavaLattice classLattice = cd2lattice.get(cd); - if (classLattice != null) { - classLattice.removeRedundantEdges(); - } - - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); - SSJavaLattice methodLattice = md2lattice.get(md); - if (methodLattice != null) { - methodLattice.removeRedundantEdges(); - } - } - } - - } - - private boolean checkLatticeProperty(Descriptor d, SSJavaLattice lattice) { - // if two elements has the same incoming node set, - // we need to merge two elements ... - - boolean isUpdated; - boolean isModified = false; - do { - isUpdated = removeNodeSharingSameIncomingNodes(d, lattice); - if (!isModified && isUpdated) { - isModified = true; - } - } while (isUpdated); - - return isModified; - } - - private boolean removeNodeSharingSameIncomingNodes(Descriptor d, SSJavaLattice lattice) { - LocationInfo locInfo = getLocationInfo(d); - Map> map = lattice.getIncomingElementMap(); - Set keySet = map.keySet(); - for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { - String key = (String) iterator.next(); - Set incomingSetKey = map.get(key); - - // System.out.println("key=" + key + " incomingSetKey=" + - // incomingSetKey); - if (incomingSetKey.size() > 0) { - for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { - String cur = (String) iterator2.next(); - if (!cur.equals(key)) { - Set incomingSetCur = map.get(cur); - if (incomingSetCur.equals(incomingSetKey)) { - if (!(incomingSetCur.size() == 1 && incomingSetCur.contains(lattice.getTopItem()))) { - // NEED TO MERGE HERE!!!! - System.out.println("@@@Try merge=" + cur + " " + key); - - Set mergeSet = new HashSet(); - mergeSet.add(cur); - mergeSet.add(key); - - String newMergeLoc = "MLoc" + (SSJavaLattice.seed++); - - System.out.println("---ASSIGN NEW MERGE LOC=" + newMergeLoc + " to " + mergeSet); - lattice.mergeIntoNewLocation(mergeSet, newMergeLoc); - - for (Iterator miterator = mergeSet.iterator(); miterator.hasNext();) { - String oldLocSymbol = (String) miterator.next(); - - Set> inferLocSet = - locInfo.getRelatedInferLocSet(oldLocSymbol); - System.out.println("---update related locations=" + inferLocSet - + " oldLocSymbol=" + oldLocSymbol); - - for (Iterator miterator2 = inferLocSet.iterator(); miterator2.hasNext();) { - Pair pair = - (Pair) miterator2.next(); - Descriptor enclosingDesc = pair.getFirst(); - Descriptor desc = pair.getSecond(); - - System.out.println("---inferLoc pair=" + pair); - - CompositeLocation inferLoc = - getLocationInfo(enclosingDesc).getInferLocation(desc); - System.out.println("oldLoc=" + inferLoc); - // if (curMethodInfo.md.equals(enclosingDesc)) { - // inferLoc = curMethodInfo.getInferLocation(desc); - // } else { - // inferLoc = - // getLocationInfo(enclosingDesc).getInferLocation(desc); - // } - - Location locElement = inferLoc.get(inferLoc.getSize() - 1); - - locElement.setLocIdentifier(newMergeLoc); - locInfo.addMapLocSymbolToRelatedInferLoc(newMergeLoc, enclosingDesc, desc); - - // if (curMethodInfo.md.equals(enclosingDesc)) { - // inferLoc = curMethodInfo.getInferLocation(desc); - // } else { - // inferLoc = - // getLocationInfo(enclosingDesc).getInferLocation(desc); - // } - - inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); - System.out.println("---New Infer Loc=" + inferLoc); - - } - - locInfo.removeRelatedInferLocSet(oldLocSymbol, newMergeLoc); - - } - - for (Iterator iterator3 = mergeSet.iterator(); iterator3.hasNext();) { - String oldLoc = (String) iterator3.next(); - lattice.remove(oldLoc); - } - return true; - } - } - } - } - } - - } - return false; - } - - private void checkLattices() { - - LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); - - // current descriptors to visit in fixed-point interprocedural analysis, - // prioritized by - // dependency in the call graph - methodDescriptorsToVisitStack.clear(); + // current descriptors to visit in fixed-point interprocedural analysis, + // prioritized by + // dependency in the call graph + methodDescriptorsToVisitStack.clear(); // descriptorListToAnalyze.removeFirst(); @@ -1463,77 +1947,6 @@ public class LocationInference { } private void inferLattices() { - - // do fixed-point analysis - - ssjava.init(); - LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); - - // Collections.sort(descriptorListToAnalyze, new - // Comparator() { - // public int compare(MethodDescriptor o1, MethodDescriptor o2) { - // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol()); - // } - // }); - - // current descriptors to visit in fixed-point interprocedural analysis, - // prioritized by - // dependency in the call graph - methodDescriptorsToVisitStack.clear(); - - // descriptorListToAnalyze.removeFirst(); - - Set methodDescriptorToVistSet = new HashSet(); - methodDescriptorToVistSet.addAll(descriptorListToAnalyze); - - while (!descriptorListToAnalyze.isEmpty()) { - MethodDescriptor md = descriptorListToAnalyze.removeFirst(); - methodDescriptorsToVisitStack.add(md); - } - - // analyze scheduled methods until there are no more to visit - while (!methodDescriptorsToVisitStack.isEmpty()) { - // start to analyze leaf node - MethodDescriptor md = methodDescriptorsToVisitStack.pop(); - - SSJavaLattice methodLattice = - new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); - - MethodLocationInfo methodInfo = new MethodLocationInfo(md); - curMethodInfo = methodInfo; - - System.out.println(); - System.out.println("SSJAVA: Inferencing the lattice from " + md); - - try { - analyzeMethodLattice(md, methodLattice, methodInfo); - } catch (CyclicFlowException e) { - throw new Error("Fail to generate the method lattice for " + md); - } - - SSJavaLattice prevMethodLattice = getMethodLattice(md); - MethodLocationInfo prevMethodInfo = getMethodLocationInfo(md); - - if ((!methodLattice.equals(prevMethodLattice)) || (!methodInfo.equals(prevMethodInfo))) { - - setMethodLattice(md, methodLattice); - setMethodLocInfo(md, methodInfo); - - // results for callee changed, so enqueue dependents caller for - // further analysis - Iterator depsItr = ssjava.getDependents(md).iterator(); - while (depsItr.hasNext()) { - MethodDescriptor methodNext = depsItr.next(); - if (!methodDescriptorsToVisitStack.contains(methodNext) - && methodDescriptorToVistSet.contains(methodNext)) { - methodDescriptorsToVisitStack.add(methodNext); - } - } - - } - - } - } private void calculateExtraLocations() { @@ -1641,86 +2054,6 @@ public class LocationInference { return desc; } - private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice, - MethodLocationInfo methodInfo) throws CyclicFlowException { - - // first take a look at method invocation nodes to newly added relations - // from the callee - analyzeLatticeMethodInvocationNode(md, methodLattice, methodInfo); - - if (!md.isStatic()) { - // set the this location - String thisLocSymbol = md.getThis().getSymbol(); - methodInfo.setThisLocName(thisLocSymbol); - } - - // set the global location - methodInfo.setGlobalLocName(LocationInference.GLOBALLOC); - methodInfo.mapDescriptorToLocation(GLOBALDESC, new CompositeLocation( - new Location(md, GLOBALLOC))); - - // visit each node of method flow graph - FlowGraph fg = getFlowGraph(md); - Set nodeSet = fg.getNodeSet(); - - // for the method lattice, we need to look at the first element of - // NTuple - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - FlowNode srcNode = (FlowNode) iterator.next(); - - Set outEdgeSet = fg.getOutEdgeSet(srcNode); - for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { - FlowEdge outEdge = (FlowEdge) iterator2.next(); - FlowNode dstNode = outEdge.getDst(); - - NTuple srcNodeTuple = srcNode.getDescTuple(); - NTuple dstNodeTuple = dstNode.getDescTuple(); - - if (outEdge.getInitTuple().equals(srcNodeTuple) - && outEdge.getEndTuple().equals(dstNodeTuple)) { - - if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1) - && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) { - - // value flows between fields - Descriptor desc = srcNodeTuple.get(0); - ClassDescriptor classDesc; - - if (desc.equals(GLOBALDESC)) { - classDesc = md.getClassDesc(); - } else { - VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0); - classDesc = varDesc.getType().getClassDesc(); - } - extractRelationFromFieldFlows(classDesc, srcNode, dstNode, 1); - - } else { - // value flow between local var - local var or local var - field - addRelationToLattice(md, methodLattice, methodInfo, srcNode, dstNode); - } - } - } - } - - // create mapping from param idx to inferred composite location - - int offset; - if (!md.isStatic()) { - // add 'this' reference location - offset = 1; - methodInfo.addMapParamIdxToInferLoc(0, methodInfo.getInferLocation(md.getThis())); - } else { - offset = 0; - } - - for (int idx = 0; idx < md.numParameters(); idx++) { - Descriptor paramDesc = md.getParameter(idx); - CompositeLocation inferParamLoc = methodInfo.getInferLocation(paramDesc); - methodInfo.addMapParamIdxToInferLoc(idx + offset, inferParamLoc); - } - - } - private void calculateExtraLocations(MethodDescriptor md) { // calcualte pcloc, returnloc,... @@ -1744,123 +2077,122 @@ public class LocationInference { Map mapParamToLoc = methodInfo.getMapParamIdxToInferLoc(); Set paramIdxSet = mapParamToLoc.keySet(); - try { - if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { - // calculate the initial program counter location - // PC location is higher than location types of all parameters - String pcLocSymbol = "PCLOC"; - - Set paramInFlowSet = new HashSet(); + if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { + // calculate the initial program counter location + // PC location is higher than location types of all parameters + String pcLocSymbol = "PCLOC"; - for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); + Set paramInFlowSet = new HashSet(); - FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx); + for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { + Integer paramIdx = (Integer) iterator.next(); - if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) { - // parameter has in-value flows - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - paramInFlowSet.add(inferLoc); - } - } + FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx); - if (paramInFlowSet.size() > 0) { - CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet); - assert (lowestLoc != null); - methodInfo.setPCLoc(lowestLoc); + if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) { + // parameter has in-value flows + CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + paramInFlowSet.add(inferLoc); } + } + if (paramInFlowSet.size() > 0) { + CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet); + assert (lowestLoc != null); + methodInfo.setPCLoc(lowestLoc); } - // calculate a return location - // the return location type is lower than all parameters and location - // types - // of return values - if (!md.getReturnType().isVoid()) { - // first, generate the set of return value location types that starts - // with - // 'this' reference - - Set inferFieldReturnLocSet = new HashSet(); - - Set paramFlowNode = getParamNodeFlowingToReturnValue(md); - Set inferParamLocSet = new HashSet(); - if (paramFlowNode != null) { - for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) { - FlowNode fn = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn)); - inferParamLocSet.add(inferLoc); - } - } + } - Set returnNodeSet = fg.getReturnNodeSet(); + // calculate a return location + // the return location type is lower than all parameters and location + // types + // of return values + if (!md.getReturnType().isVoid()) { + // first, generate the set of return value location types that starts + // with + // 'this' reference - skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferReturnLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) { - // if the location type of the return value matches "this" reference - // then, check whether this return value is equal to/lower than all - // of - // parameters that possibly flow into the return values - for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { - CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); - - if ((!paramInferLoc.equals(inferReturnLoc)) - && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { - continue skip; - } - } - inferFieldReturnLocSet.add(inferReturnLoc); + Set inferFieldReturnLocSet = new HashSet(); + Set paramFlowNode = getParamNodeFlowingToReturnValue(md); + Set inferParamLocSet = new HashSet(); + if (paramFlowNode != null) { + for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) { + FlowNode fn = (FlowNode) iterator.next(); + CompositeLocation inferLoc = + generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn)); + inferParamLocSet.add(inferLoc); + } + } + + Set returnNodeSet = fg.getReturnNodeSet(); + + skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode returnNode = (FlowNode) iterator.next(); + CompositeLocation inferReturnLoc = + generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); + if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) { + // if the location type of the return value matches "this" reference + // then, check whether this return value is equal to/lower than all + // of + // parameters that possibly flow into the return values + for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { + CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); + + if ((!paramInferLoc.equals(inferReturnLoc)) + && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { + continue skip; + } } + inferFieldReturnLocSet.add(inferReturnLoc); + } + } - if (inferFieldReturnLocSet.size() > 0) { + if (inferFieldReturnLocSet.size() > 0) { - CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); - if (returnLoc == null) { - // in this case, assign <'this',bottom> to the RETURNLOC - returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); - returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) - .getBottomItem())); - } - methodInfo.setReturnLoc(returnLoc); + CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); + if (returnLoc == null) { + // in this case, assign <'this',bottom> to the RETURNLOC + returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); + returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) + .getBottomItem())); + } + methodInfo.setReturnLoc(returnLoc); - } else { - String returnLocSymbol = "RETURNLOC"; - CompositeLocation returnLocInferLoc = - new CompositeLocation(new Location(md, returnLocSymbol)); - methodInfo.setReturnLoc(returnLocInferLoc); - - for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); - if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { - addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol, - returnLocSymbol); - } - } + } else { + String returnLocSymbol = "RETURNLOC"; + CompositeLocation returnLocInferLoc = + new CompositeLocation(new Location(md, returnLocSymbol)); + methodInfo.setReturnLoc(returnLocInferLoc); - for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { - addRelation(methodLattice, methodInfo, inferLoc, returnLocInferLoc); - } + for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { + Integer paramIdx = (Integer) iterator.next(); + CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); + if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { + // TODO + // addRelationHigherToLower(methodLattice, methodInfo, + // paramLocLocalSymbol, + // returnLocSymbol); } + } + for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode returnNode = (FlowNode) iterator.next(); + CompositeLocation inferLoc = + generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); + if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { + // TODO + // addRelation(methodLattice, methodInfo, inferLoc, + // returnLocInferLoc); + } } } - } catch (CyclicFlowException e) { - e.printStackTrace(); - } + } } private Set getHigherLocSymbolThan(SSJavaLattice lattice, String loc) { @@ -1977,50 +2309,6 @@ public class LocationInference { return false; } - private void recursiveAddRelationToLattice(int idx, MethodDescriptor md, - CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { - - String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); - String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); - - if (srcLocSymbol.equals(dstLocSymbol)) { - recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc); - } else { - - Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); - LocationInfo locInfo = getLocationInfo(parentDesc); - - addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, - dstLocSymbol); - } - - } - - // private void propagateFlowsFromCallee(MethodInvokeNode min, MethodDescriptor mdCaller, - // MethodDescriptor mdCallee) { - // - // // the transformation for a call site propagates all relations between - // // parameters from the callee - // // if the method is virtual, it also grab all relations from any possible - // // callees - // - // Set setPossibleCallees = new HashSet(); - // if (mdCallee.isStatic()) { - // setPossibleCallees.add(mdCallee); - // } else { - // Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); - // // removes method descriptors that are not invoked by the caller - // calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); - // setPossibleCallees.addAll(calleeSet); - // } - // - // for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { - // MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); - // propagateFlowsToCaller(min, mdCaller, possibleMdCallee); - // } - // - // } - private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor mdCallee) { @@ -2030,7 +2318,7 @@ public class LocationInference { } - private FlowGraph getSubGlobalFlowGraph(MethodDescriptor md) { + private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) { return mapMethodDescriptorToSubGlobalFlowGraph.get(md); } @@ -2063,7 +2351,7 @@ public class LocationInference { Set localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); - if (localReachSet.contains(paramNode2)) { + if (arg1Tuple.size() > 0 && arg2Tuple.size() > 2 && localReachSet.contains(paramNode2)) { // need to propagate an ordering relation s.t. arg1 is higher // than arg2 @@ -2095,8 +2383,10 @@ public class LocationInference { // graph // TODO - // also if a parameter is a composite location and is started with "this" reference, - // need to make sure that the corresponding argument is higher than the translated location of + // also if a parameter is a composite location and is started with "this" + // reference, + // need to make sure that the corresponding argument is higher than the + // translated location of // the parameter. FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); @@ -2155,7 +2445,8 @@ public class LocationInference { // calculate the prefix of the argument if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) { - // in this case, the callee flow causes a caller flow to the object whose method + // in this case, the callee flow causes a caller flow to the + // object whose method // is invoked. if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) { @@ -2166,8 +2457,10 @@ public class LocationInference { paramNode1); if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) { - // in this case, we need to create a new edge 'this.FIELD'->'this' - // but we couldn't... instead we assign a new composite location started + // in this case, we need to create a new edge + // 'this.FIELD'->'this' + // but we couldn't... instead we assign a new composite + // location started // with 'this' reference to the corresponding parameter CompositeLocation compLocForParam1 = @@ -2177,8 +2470,10 @@ public class LocationInference { .println("set comp loc=" + compLocForParam1 + " to " + paramNode1); paramNode1.setCompositeLocation(compLocForParam1); - // then, we need to make sure that the corresponding argument in the caller - // is required to be higher than or equal to the translated parameter + // then, we need to make sure that the corresponding + // argument in the caller + // is required to be higher than or equal to the + // translated parameter // location NTuple translatedParamTuple = @@ -2213,7 +2508,8 @@ public class LocationInference { } } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) { - // in this case, the callee flow causes a caller flow originated from the object + // in this case, the callee flow causes a caller flow + // originated from the object // whose // method is invoked. @@ -2227,8 +2523,10 @@ public class LocationInference { if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) { // in this case, we need to create a new edge 'this' -> - // 'this.FIELD' but we couldn't... instead we assign the corresponding - // parameter a new composite location started with 'this' reference + // 'this.FIELD' but we couldn't... instead we assign the + // corresponding + // parameter a new composite location started with + // 'this' reference CompositeLocation compLocForParam2 = generateCompositeLocation(mdCallee, param2Prefix); @@ -2278,6 +2576,38 @@ public class LocationInference { return tuple; } + private CompositeLocation generateCompositeLocation(NTuple prefixLocTuple) { + + System.out.println("generateCompositeLocation=" + prefixLocTuple); + + CompositeLocation newCompLoc = new CompositeLocation(); + for (int i = 0; i < prefixLocTuple.size(); i++) { + newCompLoc.addLocation(prefixLocTuple.get(i)); + } + + Descriptor lastDescOfPrefix = prefixLocTuple.get(prefixLocTuple.size() - 1).getLocDescriptor(); + + ClassDescriptor enclosingDescriptor; + if (lastDescOfPrefix instanceof FieldDescriptor) { + enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc(); + // System.out.println("enclosingDescriptor0=" + enclosingDescriptor); + } else { + // var descriptor case + enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); + } + // System.out.println("enclosingDescriptor=" + enclosingDescriptor); + + LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); + newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor); + + Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol()); + newLoc.setLocDescriptor(newLocDescriptor); + newCompLoc.addLocation(newLoc); + + // System.out.println("--newCompLoc=" + newCompLoc); + return newCompLoc; + } + private CompositeLocation generateCompositeLocation(MethodDescriptor md, NTuple paramPrefix) { @@ -2434,143 +2764,45 @@ public class LocationInference { compLoc.addLocation(locElement); if (curDescriptor instanceof VarDescriptor) { - enclosingDescriptor = md.getClassDesc(); - } else if (curDescriptor instanceof NameDescriptor) { - // it is "GLOBAL LOC" case! - enclosingDescriptor = GLOBALDESC; - } else { - enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor(); - } - - } - - System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc); - - return compLoc; - } - - private LocationDescriptor generateNewLocationDescriptor() { - return new LocationDescriptor("Loc" + (locSeed++)); - } - - private int getPrefixIndex(NTuple tuple1, NTuple tuple2) { - - // return the index where the prefix shared by tuple1 and tuple2 is ended - // if there is no prefix shared by both of them, return -1 - - int minSize = tuple1.size(); - if (minSize > tuple2.size()) { - minSize = tuple2.size(); - } - - int idx = -1; - for (int i = 0; i < minSize; i++) { - if (!tuple1.get(i).equals(tuple2.get(i))) { - break; - } else { - idx++; - } - } - - return idx; - } - - private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller, - SSJavaLattice methodLattice, MethodLocationInfo methodInfo) - throws CyclicFlowException { - - // the transformation for a call site propagates all relations between - // parameters from the callee - // if the method is virtual, it also grab all relations from any possible - // callees - - Set setMethodInvokeNode = - mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); - - if (setMethodInvokeNode != null) { - - for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { - MethodInvokeNode min = (MethodInvokeNode) iterator.next(); - MethodDescriptor mdCallee = min.getMethod(); - Set setPossibleCallees = new HashSet(); - if (mdCallee.isStatic()) { - setPossibleCallees.add(mdCallee); - } else { - Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); - // removes method descriptors that are not invoked by the caller - calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); - setPossibleCallees.addAll(calleeSet); - } - - for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { - MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); - propagateRelationToCaller(min, mdCaller, possibleMdCallee, methodLattice, methodInfo); - } - - } - } - - } - - private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller, - MethodDescriptor possibleMdCallee, SSJavaLattice methodLattice, - MethodLocationInfo methodInfo) throws CyclicFlowException { - - SSJavaLattice calleeLattice = getMethodLattice(possibleMdCallee); - MethodLocationInfo calleeLocInfo = getMethodLocationInfo(possibleMdCallee); - FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); - - int numParam = calleeLocInfo.getNumParam(); - for (int i = 0; i < numParam; i++) { - CompositeLocation param1 = calleeLocInfo.getParamCompositeLocation(i); - for (int k = 0; k < numParam; k++) { - if (i != k) { - CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k); - - if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) { - // 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 - // higher than arg2 - - for (Iterator> iterator = argDescTupleSet1.iterator(); iterator - .hasNext();) { - NTuple argDescTuple1 = iterator.next(); - - for (Iterator> iterator2 = argDescTupleSet2.iterator(); iterator2 - .hasNext();) { - NTuple argDescTuple2 = iterator2.next(); - - // retreive inferred location by the local var descriptor + enclosingDescriptor = md.getClassDesc(); + } else if (curDescriptor instanceof NameDescriptor) { + // it is "GLOBAL LOC" case! + enclosingDescriptor = GLOBALDESC; + } else { + enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor(); + } - NTuple tuple1 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple1); - NTuple tuple2 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple2); + } - // CompositeLocation higherInferLoc = - // methodInfo.getInferLocation(argTuple1.get(0)); - // CompositeLocation lowerInferLoc = - // methodInfo.getInferLocation(argTuple2.get(0)); + System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc); - CompositeLocation inferLoc1 = generateInferredCompositeLocation(methodInfo, tuple1); - CompositeLocation inferLoc2 = generateInferredCompositeLocation(methodInfo, tuple2); + return compLoc; + } - // addRelation(methodLattice, methodInfo, inferLoc1, inferLoc2); + private LocationDescriptor generateNewLocationDescriptor() { + return new LocationDescriptor("Loc" + (locSeed++)); + } - addFlowGraphEdge(mdCaller, argDescTuple1, argDescTuple2); + private int getPrefixIndex(NTuple tuple1, NTuple tuple2) { - } + // return the index where the prefix shared by tuple1 and tuple2 is ended + // if there is no prefix shared by both of them, return -1 - } + int minSize = tuple1.size(); + if (minSize > tuple2.size()) { + minSize = tuple2.size(); + } - } - } + int idx = -1; + for (int i = 0; i < minSize; i++) { + if (!tuple1.get(i).equals(tuple2.get(i))) { + break; + } else { + idx++; } } + return idx; } private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo, @@ -2612,36 +2844,6 @@ public class LocationInference { return inferLoc; } - private void addRelation(SSJavaLattice methodLattice, MethodLocationInfo methodInfo, - CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { - - System.out.println("addRelation --- srcInferLoc=" + srcInferLoc + " dstInferLoc=" - + dstInferLoc); - String srcLocalLocSymbol = srcInferLoc.get(0).getLocIdentifier(); - String dstLocalLocSymbol = dstInferLoc.get(0).getLocIdentifier(); - - if (srcInferLoc.getSize() == 1 && dstInferLoc.getSize() == 1) { - // add a new relation to the local lattice - addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); - } else if (srcInferLoc.getSize() > 1 && dstInferLoc.getSize() > 1) { - // both src and dst have assigned to a composite location - - if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) { - addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); - } else { - recursivelyAddRelation(1, srcInferLoc, dstInferLoc); - } - } else { - // either src or dst has assigned to a composite location - if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) { - addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); - } - } - - System.out.println(); - - } - public LocationInfo getLocationInfo(Descriptor d) { if (d instanceof MethodDescriptor) { return getMethodLocationInfo((MethodDescriptor) d); @@ -2670,101 +2872,6 @@ public class LocationInference { } - private void addRelationToLattice(MethodDescriptor md, SSJavaLattice methodLattice, - MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode) throws CyclicFlowException { - - System.out.println(); - System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode); - - // add a new binary relation of dstNode < srcNode - FlowGraph flowGraph = getFlowGraph(md); - try { - System.out.println("***** src composite case::"); - calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode, null); - - CompositeLocation srcInferLoc = - generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode)); - CompositeLocation dstInferLoc = - generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode)); - addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc); - } catch (CyclicFlowException e) { - // there is a cyclic value flow... try to calculate a composite location - // for the destination node - System.out.println("***** dst composite case::"); - calculateCompositeLocation(flowGraph, methodLattice, methodInfo, dstNode, srcNode); - CompositeLocation srcInferLoc = - generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode)); - CompositeLocation dstInferLoc = - generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode)); - try { - addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc); - } catch (CyclicFlowException e1) { - throw new Error("Failed to merge cyclic value flows into a shared location."); - } - } - - } - - private void recursivelyAddRelation(int idx, CompositeLocation srcInferLoc, - CompositeLocation dstInferLoc) throws CyclicFlowException { - - String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); - String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); - - Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); - - if (srcLocSymbol.equals(dstLocSymbol)) { - // check if it is the case of shared location - if (srcInferLoc.getSize() == (idx + 1) && dstInferLoc.getSize() == (idx + 1)) { - Location inferLocElement = srcInferLoc.get(idx); - System.out.println("SET SHARED LOCATION=" + inferLocElement); - getLattice(inferLocElement.getDescriptor()) - .addSharedLoc(inferLocElement.getLocIdentifier()); - } else if (srcInferLoc.getSize() > (idx + 1) && dstInferLoc.getSize() > (idx + 1)) { - recursivelyAddRelation(idx + 1, srcInferLoc, dstInferLoc); - } - } else { - addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, - dstLocSymbol); - } - } - - private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph, - MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode, Descriptor srcDesc, - Descriptor dstDesc) throws CyclicFlowException { - - CompositeLocation inferSrcLoc; - CompositeLocation inferDstLoc = methodInfo.getInferLocation(dstDesc); - - if (srcNode.getDescTuple().size() > 1) { - // field access - inferSrcLoc = new CompositeLocation(); - - NTuple locTuple = flowGraph.getLocationTuple(srcNode); - for (int i = 0; i < locTuple.size(); i++) { - inferSrcLoc.addLocation(locTuple.get(i)); - } - - } else { - inferSrcLoc = methodInfo.getInferLocation(srcDesc); - } - - if (dstNode.getDescTuple().size() > 1) { - // field access - inferDstLoc = new CompositeLocation(); - - NTuple locTuple = flowGraph.getLocationTuple(dstNode); - for (int i = 0; i < locTuple.size(); i++) { - inferDstLoc.addLocation(locTuple.get(i)); - } - - } else { - inferDstLoc = methodInfo.getInferLocation(dstDesc); - } - - recursiveAddRelationToLattice(1, md, inferSrcLoc, inferDstLoc); - } - private void addPrefixMapping(Map, Set>> map, NTuple prefix, NTuple element) { @@ -2774,254 +2881,6 @@ public class LocationInference { map.get(prefix).add(element); } - private boolean calculateCompositeLocation(FlowGraph flowGraph, - SSJavaLattice methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode, - FlowNode srcNode) throws CyclicFlowException { - - Descriptor localVarDesc = flowNode.getDescTuple().get(0); - NTuple flowNodelocTuple = flowGraph.getLocationTuple(flowNode); - - if (localVarDesc.equals(methodInfo.getMethodDesc())) { - return false; - } - - Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); - Set reachableNodeSet = flowGraph.getReachFlowNodeSetFrom(flowNode); - - Map, Set>> mapPrefixToIncomingLocTupleSet = - new HashMap, Set>>(); - - List> prefixList = new ArrayList>(); - - for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { - FlowNode inNode = (FlowNode) iterator.next(); - NTuple inNodeTuple = flowGraph.getLocationTuple(inNode); - - CompositeLocation inNodeInferredLoc = - generateInferredCompositeLocation(methodInfo, inNodeTuple); - - NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); - - for (int i = 1; i < inNodeInferredLocTuple.size(); i++) { - NTuple prefix = inNodeInferredLocTuple.subList(0, i); - if (!prefixList.contains(prefix)) { - prefixList.add(prefix); - } - addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple); - } - } - - Collections.sort(prefixList, new Comparator>() { - public int compare(NTuple arg0, NTuple arg1) { - int s0 = arg0.size(); - int s1 = arg1.size(); - if (s0 > s1) { - return -1; - } else if (s0 == s1) { - return 0; - } else { - return 1; - } - } - }); - - // System.out.println("prefixList=" + prefixList); - // System.out.println("reachableNodeSet=" + reachableNodeSet); - - // find out reachable nodes that have the longest common prefix - for (int i = 0; i < prefixList.size(); i++) { - NTuple curPrefix = prefixList.get(i); - Set> reachableCommonPrefixSet = new HashSet>(); - - for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { - FlowNode reachableNode = (FlowNode) iterator2.next(); - NTuple reachLocTuple = flowGraph.getLocationTuple(reachableNode); - CompositeLocation reachLocInferLoc = - generateInferredCompositeLocation(methodInfo, reachLocTuple); - if (reachLocInferLoc.getTuple().startsWith(curPrefix)) { - reachableCommonPrefixSet.add(reachLocTuple); - } - } - - if (!reachableCommonPrefixSet.isEmpty()) { - // found reachable nodes that start with the prefix curPrefix - // need to assign a composite location - - // first, check if there are more than one the set of locations that has - // the same length of the longest reachable prefix, no way to assign - // a composite location to the input local var - prefixSanityCheck(prefixList, i, flowGraph, reachableNodeSet); - - Set> incomingCommonPrefixSet = - mapPrefixToIncomingLocTupleSet.get(curPrefix); - - int idx = curPrefix.size(); - NTuple element = incomingCommonPrefixSet.iterator().next(); - Descriptor desc = element.get(idx).getDescriptor(); - - SSJavaLattice lattice = getLattice(desc); - LocationInfo locInfo = getLocationInfo(desc); - - CompositeLocation inferLocation = - generateInferredCompositeLocation(methodInfo, flowNodelocTuple); - - // methodInfo.getInferLocation(localVarDesc); - CompositeLocation newInferLocation = new CompositeLocation(); - - if (inferLocation.getTuple().startsWith(curPrefix)) { - // the same infer location is already existed. no need to do - // anything - System.out.println("NO ATTEMPT TO MAKE A COMPOSITE LOCATION curPrefix=" + curPrefix); - - // TODO: refactoring! - if (srcNode != null) { - CompositeLocation newLoc = new CompositeLocation(); - String newLocSymbol = "Loc" + (SSJavaLattice.seed++); - for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) { - newLoc.addLocation(curPrefix.get(locIdx)); - } - Location newLocationElement = new Location(desc, newLocSymbol); - newLoc.addLocation(newLocationElement); - - Descriptor srcLocalVar = srcNode.getDescTuple().get(0); - methodInfo.mapDescriptorToLocation(srcLocalVar, newLoc.clone()); - addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), srcLocalVar, newLoc); - methodInfo.removeMaplocalVarToLocSet(srcLocalVar); - - // add the field/var descriptor to the set of the location symbol - int lastIdx = srcNode.getDescTuple().size() - 1; - Descriptor lastFlowNodeDesc = srcNode.getDescTuple().get(lastIdx); - NTuple srcNodelocTuple = flowGraph.getLocationTuple(srcNode); - Descriptor enclosinglastLastFlowNodeDesc = srcNodelocTuple.get(lastIdx).getDescriptor(); - - CompositeLocation newlyInferredLocForFlowNode = - generateInferredCompositeLocation(methodInfo, srcNodelocTuple); - Location lastInferLocElement = - newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1); - Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor(); - - // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet( - // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc); - getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc( - lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc, - lastFlowNodeDesc); - - System.out.println("@@@@@@@ ASSIGN " + newLoc + " to SRC=" + srcNode); - } - - return true; - } else { - // assign a new composite location - - // String oldMethodLocationSymbol = - // inferLocation.get(0).getLocIdentifier(); - String newLocSymbol = "Loc" + (SSJavaLattice.seed++); - for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) { - newInferLocation.addLocation(curPrefix.get(locIdx)); - } - Location newLocationElement = new Location(desc, newLocSymbol); - newInferLocation.addLocation(newLocationElement); - - // maps local variable to location types of the common prefix - methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation.clone()); - - // methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation); - addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), localVarDesc, - newInferLocation); - methodInfo.removeMaplocalVarToLocSet(localVarDesc); - - // add the field/var descriptor to the set of the location symbol - int lastIdx = flowNode.getDescTuple().size() - 1; - Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(lastIdx); - Descriptor enclosinglastLastFlowNodeDesc = flowNodelocTuple.get(lastIdx).getDescriptor(); - - CompositeLocation newlyInferredLocForFlowNode = - generateInferredCompositeLocation(methodInfo, flowNodelocTuple); - Location lastInferLocElement = - newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1); - Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor(); - - // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet( - // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc); - getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc( - lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc, - lastFlowNodeDesc); - - // clean up the previous location - // Location prevInferLocElement = - // inferLocation.get(inferLocation.getSize() - 1); - // Descriptor prevEnclosingDesc = prevInferLocElement.getDescriptor(); - // - // SSJavaLattice targetLattice; - // LocationInfo targetInfo; - // if (prevEnclosingDesc.equals(methodInfo.getMethodDesc())) { - // targetLattice = methodLattice; - // targetInfo = methodInfo; - // } else { - // targetLattice = getLattice(prevInferLocElement.getDescriptor()); - // targetInfo = getLocationInfo(prevInferLocElement.getDescriptor()); - // } - // - // Set> associstedDescSet = - // targetInfo.getRelatedInferLocSet(prevInferLocElement.getLocIdentifier()); - // - // if (associstedDescSet.size() == 1) { - // targetLattice.remove(prevInferLocElement.getLocIdentifier()); - // } else { - // associstedDescSet.remove(lastFlowNodeDesc); - // } - - } - - System.out.println("curPrefix=" + curPrefix); - System.out.println("ASSIGN NEW COMPOSITE LOCATION =" + newInferLocation + " to " - + flowNode); - - String newlyInsertedLocName = - newInferLocation.get(newInferLocation.getSize() - 1).getLocIdentifier(); - - System.out.println("-- add in-flow"); - for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) { - NTuple tuple = (NTuple) iterator.next(); - Location loc = tuple.get(idx); - String higher = loc.getLocIdentifier(); - addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName); - } - - System.out.println("-- add out flow"); - for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) { - NTuple tuple = (NTuple) iterator.next(); - if (tuple.size() > idx) { - Location loc = tuple.get(idx); - String lower = loc.getLocIdentifier(); - // String lower = - // locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); - addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower); - } - } - - return true; - } - - } - - return false; - - } - - private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar, - CompositeLocation inferLoc) { - - Location locElement = inferLoc.get((inferLoc.getSize() - 1)); - Descriptor enclosingDesc = locElement.getDescriptor(); - LocationInfo locInfo = getLocationInfo(enclosingDesc); - locInfo.addMapLocSymbolToRelatedInferLoc(locElement.getLocIdentifier(), md, localVar); - } - - private boolean isCompositeLocation(CompositeLocation cl) { - return cl.getSize() > 1; - } - private boolean containsNonPrimitiveElement(Set descSet) { for (Iterator iterator = descSet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); @@ -3042,121 +2901,6 @@ public class LocationInference { return false; } - private void addRelationHigherToLower(SSJavaLattice lattice, LocationInfo locInfo, - String higher, String lower) throws CyclicFlowException { - - System.out.println("---addRelationHigherToLower " + higher + " -> " + lower - + " to the lattice of " + locInfo.getDescIdentifier()); - // if (higher.equals(lower) && lattice.isSharedLoc(higher)) { - // return; - // } - Set cycleElementSet = lattice.getPossibleCycleElements(higher, lower); - - boolean hasNonPrimitiveElement = false; - for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { - String cycleElementLocSymbol = (String) iterator.next(); - - Set descSet = locInfo.getDescSet(cycleElementLocSymbol); - if (containsNonPrimitiveElement(descSet)) { - hasNonPrimitiveElement = true; - break; - } - } - - if (hasNonPrimitiveElement) { - System.out.println("#Check cycle= " + lower + " < " + higher + " cycleElementSet=" - + cycleElementSet); - // if there is non-primitive element in the cycle, no way to merge cyclic - // elements into the shared location - throw new CyclicFlowException(); - } - - if (cycleElementSet.size() > 0) { - - String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++); - - System.out.println("---ASSIGN NEW SHARED LOC=" + newSharedLoc + " to " + cycleElementSet); - lattice.mergeIntoNewLocation(cycleElementSet, newSharedLoc); - lattice.addSharedLoc(newSharedLoc); - - for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { - String oldLocSymbol = (String) iterator.next(); - - Set> inferLocSet = locInfo.getRelatedInferLocSet(oldLocSymbol); - System.out.println("---update related locations=" + inferLocSet); - for (Iterator iterator2 = inferLocSet.iterator(); iterator2.hasNext();) { - Pair pair = (Pair) iterator2.next(); - Descriptor enclosingDesc = pair.getFirst(); - Descriptor desc = pair.getSecond(); - - CompositeLocation inferLoc; - if (curMethodInfo.md.equals(enclosingDesc)) { - inferLoc = curMethodInfo.getInferLocation(desc); - } else { - inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); - } - - Location locElement = inferLoc.get(inferLoc.getSize() - 1); - - locElement.setLocIdentifier(newSharedLoc); - locInfo.addMapLocSymbolToRelatedInferLoc(newSharedLoc, enclosingDesc, desc); - - if (curMethodInfo.md.equals(enclosingDesc)) { - inferLoc = curMethodInfo.getInferLocation(desc); - } else { - inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); - } - System.out.println("---New Infer Loc=" + inferLoc); - - } - locInfo.removeRelatedInferLocSet(oldLocSymbol, newSharedLoc); - - } - - lattice.addSharedLoc(newSharedLoc); - - } else if (!lattice.isGreaterThan(higher, lower)) { - lattice.addRelationHigherToLower(higher, lower); - } - } - - private void replaceOldLocWithNewLoc(SSJavaLattice methodLattice, String oldLocSymbol, - String newLocSymbol) { - - if (methodLattice.containsKey(oldLocSymbol)) { - methodLattice.substituteLocation(oldLocSymbol, newLocSymbol); - } - - } - - private void prefixSanityCheck(List> prefixList, int curIdx, - FlowGraph flowGraph, Set reachableNodeSet) { - - NTuple curPrefix = prefixList.get(curIdx); - - for (int i = curIdx + 1; i < prefixList.size(); i++) { - NTuple prefixTuple = prefixList.get(i); - - if (curPrefix.startsWith(prefixTuple)) { - continue; - } - - for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { - FlowNode reachableNode = (FlowNode) iterator2.next(); - NTuple reachLocTuple = flowGraph.getLocationTuple(reachableNode); - if (reachLocTuple.startsWith(prefixTuple)) { - // TODO - throw new Error("Failed to generate a composite location"); - } - } - } - } - - 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); @@ -3210,43 +2954,6 @@ public class LocationInference { } - private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode, - FlowNode dstNode, int idx) throws CyclicFlowException { - - if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx)) - && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) { - // value flow between fields: we don't need to add a binary relation - // for this case - - Descriptor desc = srcNode.getDescTuple().get(idx); - ClassDescriptor classDesc; - - if (idx == 0) { - classDesc = ((VarDescriptor) desc).getType().getClassDesc(); - } else { - classDesc = ((FieldDescriptor) desc).getType().getClassDesc(); - } - - extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1); - - } else { - - Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx); - Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx); - - // add a new binary relation of dstNode < srcNode - SSJavaLattice fieldLattice = getFieldLattice(cd); - LocationInfo fieldInfo = getFieldLocationInfo(cd); - - String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier(); - String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier(); - - addRelationHigherToLower(fieldLattice, fieldInfo, srcSymbol, dstSymbol); - - } - - } - public SSJavaLattice getFieldLattice(ClassDescriptor cd) { if (!cd2lattice.containsKey(cd)) { cd2lattice.put(cd, new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM)); @@ -3344,12 +3051,43 @@ public class LocationInference { mapMethodDescriptorToFlowGraph.put(md, fg); analyzeMethodBody(md.getClassDesc(), md); + + // System.out.println("##constructSubGlobalFlowGraph"); + // GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg); + // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); + // + // // TODO + // System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph"); + // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); + // + // propagateFlowsFromCalleesWithNoCompositeLocation(md); + + } + } + // _debug_printGraph(); + + methodDescList = (LinkedList) toanalyze_methodDescList.clone(); + + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + if (state.SSJAVADEBUG) { + System.out.println(); + System.out.println("SSJAVA: Constructing a flow graph2: " + md); + + System.out.println("##constructSubGlobalFlowGraph"); + GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(getFlowGraph(md)); + mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); + + // TODO + System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph"); + addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); + propagateFlowsFromCalleesWithNoCompositeLocation(md); - // assignCompositeLocation(md); } } - _debug_printGraph(); } @@ -3581,7 +3319,8 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(condTupleNode); if (newImplicitTupleSet.size() > 1) { - // need to create an intermediate node for the GLB of conditional locations & implicit flows + // need to create an intermediate node for the GLB of conditional + // locations & implicit flows NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { NTuple tuple = idxIter.next(); @@ -3615,16 +3354,21 @@ public class LocationInference { FlowGraph fg = getFlowGraph(md); // if (implicitFlowTupleSet.size() == 1 - // && fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate()) { + // && + // fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate()) + // { // - // // since there is already an intermediate node for the GLB of implicit flows + // // since there is already an intermediate node for the GLB of implicit + // flows // // we don't need to create another intermediate node. // // just re-use the intermediate node for implicit flows. // - // FlowNode meetNode = fg.getFlowNode(implicitFlowTupleSet.iterator().next()); + // FlowNode meetNode = + // fg.getFlowNode(implicitFlowTupleSet.iterator().next()); // // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - // NTuple returnNodeTuple = (NTuple) iterator.next(); + // NTuple returnNodeTuple = (NTuple) + // iterator.next(); // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple()); // } // @@ -3669,7 +3413,8 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(condTupleNode); if (newImplicitTupleSet.size() > 1) { - // need to create an intermediate node for the GLB of conditional locations & implicit flows + // need to create an intermediate node for the GLB of conditional + // locations & implicit flows NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter .hasNext();) { @@ -3683,14 +3428,17 @@ public class LocationInference { // /////////// // System.out.println("condTupleNode="+condTupleNode); - // NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + // NTuple interTuple = + // getFlowGraph(md).createIntermediateNode().getDescTuple(); // - // for (Iterator> idxIter = condTupleNode.iterator(); idxIter.hasNext();) { + // for (Iterator> idxIter = condTupleNode.iterator(); + // idxIter.hasNext();) { // NTuple tuple = idxIter.next(); // addFlowGraphEdge(md, tuple, interTuple); // } - // for (Iterator> idxIter = implicitFlowTupleSet.iterator(); idxIter + // for (Iterator> idxIter = + // implicitFlowTupleSet.iterator(); idxIter // .hasNext();) { // NTuple tuple = idxIter.next(); // addFlowGraphEdge(md, tuple, interTuple); @@ -3973,6 +3721,10 @@ public class LocationInference { private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable, MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0)); + + mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap>()); + if (nodeSet == null) { nodeSet = new NodeTupleSet(); } @@ -3993,8 +3745,6 @@ public class LocationInference { FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc); Set calleeReturnSet = calleeFlowGraph.getReturnNodeSet(); - System.out.println("#calleeReturnSet=" + calleeReturnSet); - if (min.getExpression() != null) { NodeTupleSet baseNodeSet = new NodeTupleSet(); @@ -4020,6 +3770,7 @@ public class LocationInference { } else { // TODO Set inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode); + System.out.println("inFlowSet=" + inFlowSet + " from retrunNode=" + returnNode); for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) { FlowNode inFlowNode = (FlowNode) iterator2.next(); if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) { @@ -4048,9 +3799,10 @@ public class LocationInference { int idx = i + offset; NodeTupleSet argTupleSet = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false); - // if argument is liternal node, argTuple is set to NULL. + // if argument is liternal node, argTuple is set to NULL NTuple argTuple = new NTuple(); + System.out.println("-argTupleSet=" + argTupleSet + " from en=" + en.printNode(0)); if (argTupleSet.size() > 1) { NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); @@ -4059,11 +3811,14 @@ 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); + FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) || calleeMethodDesc.getModifiers().isNative()) { @@ -4076,13 +3831,18 @@ public class LocationInference { // propagateFlowsFromCallee(min, md, min.getMethod()); + System.out.println("min nodeSet=" + nodeSet); } } private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set nodeSet) { // return true if inNode has in-flows to nodeSet - Set reachableSet = fg.getReachFlowNodeSetFrom(inNode); + + // Set reachableSet = fg.getReachFlowNodeSetFrom(inNode); + Set reachableSet = fg.getReachableSetFrom(inNode.getDescTuple()); + System.out.println("inNode=" + inNode + " reachalbeSet=" + reachableSet); + for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) { FlowNode fn = (FlowNode) iterator.next(); if (nodeSet.contains(fn)) {