X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLocationInference.java;h=6575d4bad7708eca4a0669d04875f7e06c32dd4e;hb=52bd77482e98618483034a513931c50a870b9a47;hp=103faa85977101ae28962300a1a7cea4acf48c37;hpb=2dcc891b7dfc2a791c10b820da51755813adefd7;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 103faa85..6575d4ba 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -114,12 +114,16 @@ public class LocationInference { private Map mapDescToLocationSummary; + private Map> mapMethodDescToMethodInvokeNodeSet; + // 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, NTuple>> mapMethodInvokeNodeToMapCallerArgToCalleeArg; + private Map mapMethodDescriptorToCompositeReturnCase; + public static final String GLOBALLOC = "GLOBALLOC"; public static final String INTERLOC = "INTERLOC"; @@ -152,6 +156,8 @@ public class LocationInference { public static int locSeed = 0; + private Stack arrayAccessNodeStack; + public LocationInference(SSJavaAnalysis ssjava, State state) { this.ssjava = ssjava; this.state = state; @@ -193,6 +199,13 @@ public class LocationInference { this.mapMethodInvokeNodeToPCLocTupleSet = new HashMap>>(); + this.arrayAccessNodeStack = new Stack(); + + this.mapMethodDescToMethodInvokeNodeSet = + new HashMap>(); + + this.mapMethodDescriptorToCompositeReturnCase = new HashMap(); + } public void setupToAnalyze() { @@ -243,14 +256,12 @@ public class LocationInference { constructGlobalFlowGraph(); - do { - assignCompositeLocation(); - updateFlowGraph(); - calculateExtraLocations(); - hasChanges = false; - addAdditionalOrderingConstraints(); - System.out.println("&&&&&&&&&&&&&&&&&&&&&&has changes=" + hasChanges); - } while (hasChanges); + checkReturnNodes(); + + assignCompositeLocation(); + updateFlowGraph(); + calculateExtraLocations(); + addAdditionalOrderingConstraints(); _debug_writeFlowGraph(); @@ -260,6 +271,8 @@ public class LocationInference { debug_writeHierarchyDotFiles(); + // System.exit(0); + simplifyHierarchyGraph(); debug_writeSimpleHierarchyDotFiles(); @@ -286,6 +299,25 @@ public class LocationInference { } + private void checkReturnNodes() { + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + + if (md.getReturnType() != null && !md.getReturnType().isVoid()) { + checkFlowNodeReturnThisField(md); + } + // // in this case, this method will return the composite location that starts with 'this' + // FlowGraph flowGraph = getFlowGraph(md); + // Set returnNodeSet = flowGraph.getReturnNodeSet(); + // } + + } + + } + private void updateFlowGraph() { LinkedList methodDescList = @@ -328,6 +360,12 @@ public class LocationInference { translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); } + private void translateCompositeLocationAssignmentToFlowGraph2() { + System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:"); + MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); + translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); + } + private void addAdditionalOrderingConstraints() { System.out.println("\nSSJAVA: Add addtional ordering constriants:"); MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); @@ -414,12 +452,16 @@ public class LocationInference { private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) { + System.out.println("\n\n###translateCompositeLocationAssignmentToFlowGraph mdCaller=" + + 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(); @@ -437,7 +479,9 @@ public class LocationInference { // need to translate a composite location that is started with the base // tuple of 'min'. translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min); - calleeSet.add(min.getMethod()); + MethodDescriptor mdCallee = min.getMethod(); + calleeSet.add(mdCallee); + } for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { @@ -445,16 +489,46 @@ public class LocationInference { translateCompositeLocationAssignmentToFlowGraph(callee); } - for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { - MethodInvokeNode min = (MethodInvokeNode) iterator.next(); - // add an additional ordering constraint - // if the first element of a parameter composite location matches 'this' reference, - // the corresponding argument in the caller is required to be higher than the translated - // parameter location in the caller lattice - // TODO - // addOrderingConstraintFromCompLocParamToArg(mdCaller, min); - } + } + + private CompositeLocation translateArgCompLocToParamCompLoc(MethodInvokeNode min, + CompositeLocation argCompLoc) { + + System.out.println("--------translateArgCompLocToParamCompLoc argCompLoc=" + argCompLoc); + MethodDescriptor mdCallee = min.getMethod(); + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + + NTuple argLocTuple = argCompLoc.getTuple(); + Location argLocalLoc = argLocTuple.get(0); + Map> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min); + Set idxSet = mapIdxToArgTuple.keySet(); + for (Iterator iterator2 = idxSet.iterator(); iterator2.hasNext();) { + Integer idx = (Integer) iterator2.next(); + + if (idx == 0 && !min.getMethod().isStatic()) { + continue; + } + + NTuple argTuple = mapIdxToArgTuple.get(idx); + if (argTuple.size() > 0 && argTuple.get(0).equals(argLocalLoc.getLocDescriptor())) { + // it matches with the current argument composite location + // so what is the corresponding parameter local descriptor? + FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + System.out.println("----------found paramNode=" + paramNode); + NTuple paramDescTuple = paramNode.getCurrentDescTuple(); + + NTuple newParamTupleFromArgTuple = translateToLocTuple(mdCallee, paramDescTuple); + for (int i = 1; i < argLocTuple.size(); i++) { + newParamTupleFromArgTuple.add(argLocTuple.get(i)); + } + + System.out.println("-----------newParamTuple=" + newParamTupleFromArgTuple); + return new CompositeLocation(newParamTupleFromArgTuple); + + } + } + return null; } private void addAddtionalOrderingConstraints(MethodDescriptor mdCaller) { @@ -481,12 +555,11 @@ public class LocationInference { // the corresponding argument in the caller is required to be higher than the translated // parameter location in the caller lattice // TODO - addOrderingConstraintFromCompLocParamToArg(mdCaller, min); + // addOrderingConstraintFromCompLocParamToArg(mdCaller, min); // // update return flow nodes in the caller CompositeLocation returnLoc = getMethodSummary(mdCallee).getRETURNLoc(); - System.out.println("### min=" + min.printNode(0) + " returnLoc=" + returnLoc); if (returnLoc != null && returnLoc.get(0).getLocDescriptor().equals(mdCallee.getThis()) && returnLoc.getSize() > 1) { @@ -499,6 +572,20 @@ public class LocationInference { } System.out.println("###NEW RETURN TUPLE FOR CALLER=" + newReturnTuple); callerFlowGraph.getFlowReturnNode(min).setNewTuple(newReturnTuple); + } else { + // if the return loc set was empty and later pcloc was connected to the return loc + // need to make sure that return loc reflects to this changes. + FlowReturnNode flowReturnNode = callerFlowGraph.getFlowReturnNode(min); + if (flowReturnNode != null && flowReturnNode.getReturnTupleSet().isEmpty()) { + + if (needToUpdateReturnLocHolder(min.getMethod(), flowReturnNode)) { + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + NTuple newReturnTuple = baseTuple.clone(); + flowReturnNode.addTuple(newReturnTuple); + } + + } + } } @@ -510,6 +597,38 @@ public class LocationInference { } + private boolean needToUpdateReturnLocHolder(MethodDescriptor mdCallee, + FlowReturnNode flowReturnNode) { + FlowGraph fg = getFlowGraph(mdCallee); + MethodSummary summary = getMethodSummary(mdCallee); + CompositeLocation returnCompLoc = summary.getRETURNLoc(); + NTuple returnDescTuple = translateToDescTuple(returnCompLoc.getTuple()); + Set incomingNodeToReturnNode = + fg.getIncomingFlowNodeSet(fg.getFlowNode(returnDescTuple)); + for (Iterator iterator = incomingNodeToReturnNode.iterator(); iterator.hasNext();) { + FlowNode inNode = (FlowNode) iterator.next(); + if (inNode.getDescTuple().get(0).equals(mdCallee.getThis())) { + return true; + } + } + return false; + } + + private void addMapMethodDescToMethodInvokeNodeSet(MethodInvokeNode min) { + MethodDescriptor md = min.getMethod(); + if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet()); + } + mapMethodDescToMethodInvokeNodeSet.get(md).add(min); + } + + private Set getMethodInvokeNodeSetByMethodDesc(MethodDescriptor md) { + if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet()); + } + return mapMethodDescToMethodInvokeNodeSet.get(md); + } + private void addOrderingConstraintFromCompLocParamToArg(MethodDescriptor mdCaller, MethodInvokeNode min) { System.out.println("-addOrderingConstraintFromCompLocParamToArg=" + min.printNode(0)); @@ -631,8 +750,8 @@ public class LocationInference { baseLocTuple = translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min)); } - // System.out.println("\n-#translate caller=" + mdCaller + " infer composite loc to callee=" - // + mdCallee + " baseLocTuple=" + baseLocTuple); + System.out.println("\n-#translate caller=" + mdCaller + " infer composite loc to callee=" + + mdCallee + " baseLocTuple=" + baseLocTuple); // System.out.println("-mapIdxToArgTuple=" + mapIdxToArgTuple); // System.out.println("-callerMapLocToCompLoc=" + callerMapLocToCompLoc); @@ -651,10 +770,14 @@ public class LocationInference { translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); - // System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc - // + " newCalleeCompLoc=" + newCalleeCompLoc); + System.out.println("1---key=" + key + " callerCompLoc=" + callerCompLoc + + " newCalleeCompLoc=" + newCalleeCompLoc); + System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + if (!newCalleeCompLoc.get(0).getDescriptor().equals(mdCallee)) { + System.exit(0); + } + // System.out.println("-----baseLoctuple=" + baseLocTuple); - // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); } else { // check if it is the global access Location compLocFirstElement = callerCompLoc.getTuple().get(0); @@ -669,19 +792,41 @@ public class LocationInference { newCalleeCompLoc.addLocation(callerCompLoc.get(i)); } calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); - // System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc - // + " newCalleeCompLoc=" + newCalleeCompLoc); - // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + System.out.println("2---key=" + key + " callerCompLoc=" + callerCompLoc + + " newCalleeCompLoc=" + newCalleeCompLoc); + System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); } else { int paramIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple); if (paramIdx == -1) { + // here, the first element of the current composite location comes from the current + // callee + // so transfer the same composite location to the callee + if (!calleeGlobalGraph.contrainsInferCompositeLocationMapKey(key)) { + if (callerCompLoc.get(0).getDescriptor().equals(mdCallee)) { + System.out.println("3---key=" + key + " callerCompLoc=" + callerCompLoc + + " newCalleeCompLoc=" + callerCompLoc); + System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, callerCompLoc); + } else { + System.out.println("3---SKIP key=" + key + " callerCompLoc=" + callerCompLoc); + } + } continue; } + + // It is the case where two parameters have relative orderings between them by having + // composite locations + // if we found the param idx, it means that the first part of the caller composite + // location corresponds to the one of arguments. + // for example, if the caller argument is <,> + // and the current caller composite location mapping + // <,,> + // and the parameter which matches with the caller argument is 'Br brParam' + // then, the translated callee composite location will be <,> NTuple argTuple = mapIdxToArgTuple.get(paramIdx); FlowNode paramFlowNode = calleeFlowGraph.getParamFlowNode(paramIdx); - // System.out.println("-----paramIdx=" + paramIdx + " paramFlowNode=" + paramFlowNode); NTuple paramLocTuple = translateToLocTuple(mdCallee, paramFlowNode.getDescTuple()); newCalleeCompLoc = new CompositeLocation(); @@ -692,10 +837,14 @@ public class LocationInference { newCalleeCompLoc.addLocation(callerCompLoc.get(i)); } calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); - // System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc - // + " newCalleeCompLoc=" + newCalleeCompLoc); - // System.out.println("------argTuple=" + argTuple); - // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + System.out.println("4---key=" + key + " callerCompLoc=" + callerCompLoc + + " newCalleeCompLoc=" + newCalleeCompLoc); + System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + + // System.out.println("-----argTuple=" + argTuple + " caller=" + mdCaller + + // " callee=" + // + mdCallee); + // System.out.println("-----paramIdx=" + paramIdx + " paramFlowNode=" + paramFlowNode); } @@ -707,6 +856,8 @@ public class LocationInference { // System.out.println("-----*AFTER TRANSLATING COMP LOC MAPPING, CALLEE MAPPING=" // + calleeGlobalGraph.getMapLocationToInferCompositeLocation()); + System.out.println("#ASSIGN COMP LOC TO CALLEE PARAMS: callee=" + mdCallee + " caller=" + + mdCaller); // If the location of an argument has a composite location // need to assign a proper composite location to the corresponding callee parameter Set idxSet = mapIdxToArgTuple.keySet(); @@ -718,6 +869,7 @@ public class LocationInference { } NTuple argTuple = mapIdxToArgTuple.get(idx); + System.out.println("-argTuple=" + argTuple + " idx=" + idx); if (argTuple.size() > 0) { // check if an arg tuple has been already assigned to a composite location NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); @@ -731,16 +883,23 @@ public class LocationInference { callerCompLoc.addLocation(argLocTuple.get(i)); } - if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) { + System.out.println("---callerCompLoc=" + callerCompLoc); - FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx); - NTuple calleeParamDescTuple = calleeParamFlowNode.getDescTuple(); - NTuple calleeParamLocTuple = - translateToLocTuple(mdCallee, calleeParamDescTuple); + // if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) { - // System.out.println("---need to translate callerCompLoc=" + callerCompLoc - // + " with baseTuple=" + baseLocTuple + " calleeParamLocTuple=" - // + calleeParamLocTuple); + FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx); + + NTuple calleeParamDescTuple = calleeParamFlowNode.getDescTuple(); + NTuple calleeParamLocTuple = + translateToLocTuple(mdCallee, calleeParamDescTuple); + + int refParamIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple); + System.out.println("-----paramIdx=" + refParamIdx); + if (refParamIdx == 0 && !mdCallee.isStatic()) { + + System.out.println("-------need to translate callerCompLoc=" + callerCompLoc + + " with baseTuple=" + baseLocTuple + " calleeParamLocTuple=" + + calleeParamLocTuple); CompositeLocation newCalleeCompLoc = translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); @@ -748,11 +907,53 @@ public class LocationInference { calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), newCalleeCompLoc); - // System.out.println("---callee loc=" + calleeParamLocTuple.get(0) - // + " newCalleeCompLoc=" + newCalleeCompLoc); + System.out.println("---------key=" + calleeParamLocTuple.get(0) + " callerCompLoc=" + + callerCompLoc + " newCalleeCompLoc=" + newCalleeCompLoc); + + } else if (refParamIdx != -1) { + // the first element of an argument composite location matches with one of paramtere + // composite locations + System.out.println("-------param match case="); + + NTuple argTupleRef = mapIdxToArgTuple.get(refParamIdx); + FlowNode refParamFlowNode = calleeFlowGraph.getParamFlowNode(refParamIdx); + NTuple refParamLocTuple = + translateToLocTuple(mdCallee, refParamFlowNode.getDescTuple()); + + System.out.println("---------refParamLocTuple=" + refParamLocTuple + + " from argTupleRef=" + argTupleRef); + + CompositeLocation newCalleeCompLoc = new CompositeLocation(); + for (int i = 0; i < refParamLocTuple.size(); i++) { + newCalleeCompLoc.addLocation(refParamLocTuple.get(i)); + } + for (int i = argTupleRef.size(); i < callerCompLoc.getSize(); i++) { + newCalleeCompLoc.addLocation(callerCompLoc.get(i)); + } + + calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), + newCalleeCompLoc); + + calleeParamFlowNode.setCompositeLocation(newCalleeCompLoc); + System.out.println("-----------key=" + calleeParamLocTuple.get(0) + " callerCompLoc=" + + callerCompLoc + " newCalleeCompLoc=" + newCalleeCompLoc); + + } else { + CompositeLocation newCalleeCompLoc = + calculateCompositeLocationFromSubGlobalGraph(mdCallee, calleeParamFlowNode); + if (newCalleeCompLoc != null) { + calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), + newCalleeCompLoc); + calleeParamFlowNode.setCompositeLocation(newCalleeCompLoc); + } } + System.out.println("-----------------calleeParamFlowNode=" + + calleeParamFlowNode.getCompositeLocation()); + + // } + } } @@ -760,6 +961,101 @@ public class LocationInference { } + private CompositeLocation calculateCompositeLocationFromSubGlobalGraph(MethodDescriptor md, + FlowNode paramNode) { + + System.out.println("#############################################################"); + System.out.println("calculateCompositeLocationFromSubGlobalGraph=" + paramNode); + + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); + NTuple paramLocTuple = translateToLocTuple(md, paramNode.getDescTuple()); + GlobalFlowNode paramGlobalNode = subGlobalFlowGraph.getFlowNode(paramLocTuple); + + List> prefixList = calculatePrefixList(subGlobalFlowGraph, paramGlobalNode); + + Location prefixLoc = paramLocTuple.get(0); + + Set reachableNodeSet = + subGlobalFlowGraph.getReachableNodeSetByPrefix(paramGlobalNode.getLocTuple().get(0)); + // Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); + + // System.out.println("node=" + node + " prefixList=" + prefixList); + + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next(); + if (reachNode.getLocTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getLocTuple()); + } + } + // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet); + + if (!reachableCommonPrefixSet.isEmpty()) { + + MethodDescriptor curPrefixFirstElementMethodDesc = + (MethodDescriptor) curPrefix.get(0).getDescriptor(); + + MethodDescriptor nodePrefixLocFirstElementMethodDesc = + (MethodDescriptor) prefixLoc.getDescriptor(); + + // System.out.println("curPrefixFirstElementMethodDesc=" + + // curPrefixFirstElementMethodDesc); + // System.out.println("nodePrefixLocFirstElementMethodDesc=" + // + nodePrefixLocFirstElementMethodDesc); + + if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc) + || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc, + curPrefixFirstElementMethodDesc)) { + + // TODO + // if (!node.getLocTuple().startsWith(curPrefix.get(0))) { + + Location curPrefixLocalLoc = curPrefix.get(0); + if (subGlobalFlowGraph.mapLocationToInferCompositeLocation.containsKey(curPrefixLocalLoc)) { + // in this case, the local variable of the current prefix has already got a composite + // location + // so we just ignore the current composite location. + + // System.out.println("HERE WE DO NOT ASSIGN A COMPOSITE LOCATION TO =" + node + // + " DUE TO " + curPrefix); + return null; + } + + if (!needToGenerateCompositeLocation(paramGlobalNode, curPrefix)) { + System.out.println("NO NEED TO GENERATE COMP LOC to " + paramGlobalNode + + " with prefix=" + curPrefix); + // System.out.println("prefixList=" + prefixList); + // System.out.println("reachableNodeSet=" + reachableNodeSet); + return null; + } + + Location targetLocalLoc = paramGlobalNode.getLocTuple().get(0); + CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); + System.out.println("NEED TO ASSIGN COMP LOC TO " + paramGlobalNode + " with prefix=" + + curPrefix); + System.out.println("-targetLocalLoc=" + targetLocalLoc + " - newCompLoc=" + newCompLoc); + + // makes sure that a newly generated location appears in the hierarchy graph + for (int compIdx = 0; compIdx < newCompLoc.getSize(); compIdx++) { + Location curLoc = newCompLoc.get(compIdx); + getHierarchyGraph(curLoc.getDescriptor()).getHNode(curLoc.getLocDescriptor()); + } + + subGlobalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); + + return newCompLoc; + + } + + } + + } + return null; + } + private int getParamIdx(CompositeLocation compLoc, Map> mapIdxToArgTuple) { @@ -770,7 +1066,8 @@ public class LocationInference { for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Integer key = (Integer) iterator.next(); NTuple argTuple = mapIdxToArgTuple.get(key); - if (translateToDescTuple(compLoc.getTuple()).startsWith(argTuple)) { + if (argTuple.size() > 0 && translateToDescTuple(compLoc.getTuple()).startsWith(argTuple)) { + System.out.println("compLoc.getTuple=" + compLoc + " is started with " + argTuple); return key.intValue(); } } @@ -842,9 +1139,11 @@ public class LocationInference { // Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); // System.out.println("node=" + node + " prefixList=" + prefixList); + System.out.println("---prefixList=" + prefixList); - for (int i = 0; i < prefixList.size(); i++) { + nextprefix: for (int i = 0; i < prefixList.size(); i++) { NTuple curPrefix = prefixList.get(i); + System.out.println("---curPrefix=" + curPrefix); Set> reachableCommonPrefixSet = new HashSet>(); for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { @@ -887,13 +1186,19 @@ public class LocationInference { continue next; } - Location targetLocalLoc = node.getLocTuple().get(0); - // CompositeLocation curCompLoc = globalFlowGraph.getCompositeLocation(targetLocalLoc); - // if ((curPrefix.size() + 1) > curCompLoc.getSize()) { + if (!needToGenerateCompositeLocation(node, curPrefix)) { + System.out.println("NO NEED TO GENERATE COMP LOC to " + node + " with prefix=" + + curPrefix); + // System.out.println("prefixList=" + prefixList); + // System.out.println("reachableNodeSet=" + reachableNodeSet); + continue nextprefix; + } + Location targetLocalLoc = node.getLocTuple().get(0); CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix); - System.out.println("- newCompLoc=" + newCompLoc); + System.out.println("-targetLocalLoc=" + targetLocalLoc + " - newCompLoc=" + + newCompLoc); globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); // } @@ -907,9 +1212,250 @@ public class LocationInference { } } - // Set inNodeSet = - // graph.getIncomingNodeSetWithPrefix(prefix); - // System.out.println("inNodeSet=" + inNodeSet + " from=" + node); + } + + private boolean checkFlowNodeReturnThisField(MethodDescriptor md) { + + MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop(); + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop); + + FlowGraph flowGraph = getFlowGraph(md); + + ClassDescriptor enclosingDesc = getClassTypeDescriptor(md.getThis()); + if (enclosingDesc == null) { + return false; + } + + int count = 0; + Set returnNodeSet = flowGraph.getReturnNodeSet(); + Set globalReturnNodeSet = new HashSet(); + for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + NTuple locTuple = translateToLocTuple(md, flowNode.getDescTuple()); + GlobalFlowNode globalReturnNode = globalFlowGraph.getFlowNode(locTuple); + globalReturnNodeSet.add(globalReturnNode); + + List> prefixList = calculatePrefixList(globalFlowGraph, globalReturnNode); + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + ClassDescriptor cd = + getClassTypeDescriptor(curPrefix.get(curPrefix.size() - 1).getLocDescriptor()); + if (cd != null && cd.equals(enclosingDesc)) { + count++; + break; + } + } + + } + + if (count == returnNodeSet.size()) { + // in this case, all return nodes in the method returns values coming from a location that + // starts with "this" + + System.out.println("$$$SET RETURN LOC TRUE=" + md); + mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.TRUE); + + // NameDescriptor returnLocDesc = new NameDescriptor("RLOC" + (locSeed++)); + // NTuple rDescTuple = new NTuple(); + // rDescTuple.add(md.getThis()); + // rDescTuple.add(returnLocDesc); + // + // for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + // FlowNode rnode = (FlowNode) iterator.next(); + // flowGraph.addValueFlowEdge(rnode.getDescTuple(), rDescTuple); + // } + // + // getMethodSummary(md).setRETURNLoc(new CompositeLocation(translateToLocTuple(md, + // rDescTuple))); + + } else { + mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.FALSE); + } + + return mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue(); + + } + + private boolean needToGenerateCompositeLocation(GlobalFlowNode node, NTuple curPrefix) { + // return true if there is a path between a node to which we want to give a composite location + // and nodes which start with curPrefix + + System.out.println("---needToGenerateCompositeLocation curPrefix=" + curPrefix); + + Location targetLocalLoc = node.getLocTuple().get(0); + + MethodDescriptor md = (MethodDescriptor) targetLocalLoc.getDescriptor(); + FlowGraph flowGraph = getFlowGraph(md); + FlowNode flowNode = flowGraph.getFlowNode(node.getDescTuple()); + Set reachableSet = flowGraph.getReachFlowNodeSetFrom(flowNode); + + Set paramNodeSet = flowGraph.getParamFlowNodeSet(); + for (Iterator iterator = paramNodeSet.iterator(); iterator.hasNext();) { + FlowNode paramFlowNode = (FlowNode) iterator.next(); + if (curPrefix.startsWith(translateToLocTuple(md, paramFlowNode.getDescTuple()))) { + System.out.println("here1?!"); + return true; + } + } + + if (targetLocalLoc.getLocDescriptor() instanceof InterDescriptor) { + Pair pair = + ((InterDescriptor) targetLocalLoc.getLocDescriptor()).getMethodArgIdxPair(); + + if (pair != null) { + System.out.println("$$$TARGETLOCALLOC HOLDER=" + targetLocalLoc); + + MethodInvokeNode min = pair.getFirst(); + Integer paramIdx = pair.getSecond(); + MethodDescriptor mdCallee = min.getMethod(); + + FlowNode paramNode = getFlowGraph(mdCallee).getParamFlowNode(paramIdx); + if (checkNodeReachToReturnNode(mdCallee, paramNode)) { + System.out.println("here2?!"); + return true; + } + + } + + } + + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); + Set subGlobalReachableSet = subGlobalFlowGraph.getReachableNodeSetFrom(node); + + if (!md.isStatic()) { + ClassDescriptor currentMethodThisType = getClassTypeDescriptor(md.getThis()); + for (int i = 0; i < curPrefix.size(); i++) { + ClassDescriptor prefixType = getClassTypeDescriptor(curPrefix.get(i).getLocDescriptor()); + if (prefixType != null && prefixType.equals(currentMethodThisType)) { + System.out.println("PREFIX TYPE MATCHES WITH=" + currentMethodThisType); + + if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) { + boolean hasCompReturnLocWithThis = + mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue(); + if (hasCompReturnLocWithThis) { + if (checkNodeReachToReturnNode(md, flowNode)) { + System.out.println("here3?!"); + return true; + } + } + } + + for (Iterator iterator3 = subGlobalReachableSet.iterator(); iterator3.hasNext();) { + GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator3.next(); + if (subGlobalReachalbeNode.getLocTuple().get(0).getLocDescriptor().equals(md.getThis())) { + System.out.println("PREFIX FOUND=" + subGlobalReachalbeNode); + System.out.println("here4?!"); + return true; + } + } + } + } + } + + // System.out.println("flowGraph.getReturnNodeSet()=" + flowGraph.getReturnNodeSet()); + // System.out.println("flowGraph.contains(node.getDescTuple())=" + // + flowGraph.contains(node.getDescTuple()) + " flowGraph.getFlowNode(node.getDescTuple())=" + // + flowGraph.getFlowNode(node.getDescTuple()));reachableSet + + // if (flowGraph.contains(node.getDescTuple()) + // && flowGraph.getReturnNodeSet().contains(flowGraph.getFlowNode(node.getDescTuple()))) { + // // return checkFlowNodeReturnThisField(flowGraph); + // } + + Location lastLocationOfPrefix = curPrefix.get(curPrefix.size() - 1); + // check whether prefix appears in the list of parameters + Set minSet = mapMethodDescToMethodInvokeNodeSet.get(md); + found: for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + Map> map = mapMethodInvokeNodeToArgIdxMap.get(min); + Set keySet = map.keySet(); + // System.out.println("min=" + min.printNode(0)); + + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + Integer argIdx = (Integer) iterator2.next(); + NTuple argTuple = map.get(argIdx); + + if (!(!md.isStatic() && argIdx == 0)) { + // if the argTuple is empty, we don't need to do with anything(LITERAL CASE). + if (argTuple.size() > 0 + && argTuple.get(argTuple.size() - 1).equals(lastLocationOfPrefix.getLocDescriptor())) { + NTuple locTuple = + translateToLocTuple(md, flowGraph.getParamFlowNode(argIdx).getDescTuple()); + lastLocationOfPrefix = locTuple.get(0); + System.out.println("ARG CASE=" + locTuple); + for (Iterator iterator3 = subGlobalReachableSet.iterator(); iterator3.hasNext();) { + GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator3.next(); + // NTuple locTuple = translateToLocTuple(md, reachalbeNode.getDescTuple()); + NTuple globalReachlocTuple = subGlobalReachalbeNode.getLocTuple(); + for (int i = 0; i < globalReachlocTuple.size(); i++) { + if (globalReachlocTuple.get(i).equals(lastLocationOfPrefix)) { + System.out.println("ARG " + argTuple + " IS MATCHED WITH=" + + lastLocationOfPrefix); + System.out.println("here5?!"); + + return true; + } + } + } + } + } + } + } + + // ClassDescriptor cd; + // if (lastLocationOfPrefix.getLocDescriptor() instanceof VarDescriptor) { + // cd = ((VarDescriptor) lastLocationOfPrefix.getLocDescriptor()).getType().getClassDesc(); + // } else { + // // it is a field descriptor + // cd = ((FieldDescriptor) lastLocationOfPrefix.getLocDescriptor()).getType().getClassDesc(); + // } + // + // GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); + // Set subGlobalReachableSet = subGlobalFlowGraph.getReachableNodeSetFrom(node); + // + // System.out.println("TRY TO FIND lastLocationOfPrefix=" + lastLocationOfPrefix); + // for (Iterator iterator2 = subGlobalReachableSet.iterator(); iterator2.hasNext();) { + // GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator2.next(); + // // NTuple locTuple = translateToLocTuple(md, reachalbeNode.getDescTuple()); + // NTuple locTuple = subGlobalReachalbeNode.getLocTuple(); + // + // for (int i = 0; i < locTuple.size(); i++) { + // if (locTuple.get(i).equals(lastLocationOfPrefix)) { + // return true; + // } + // } + // + // Location lastLoc = locTuple.get(locTuple.size() - 1); + // Descriptor enclosingDescriptor = lastLoc.getDescriptor(); + // + // if (enclosingDescriptor != null && enclosingDescriptor.equals(cd)) { + // System.out.println("# WHY HERE?"); + // System.out.println("subGlobalReachalbeNode=" + subGlobalReachalbeNode); + // return true; + // } + // } + + return false; + } + + private boolean checkNodeReachToReturnNode(MethodDescriptor md, FlowNode node) { + + FlowGraph flowGraph = getFlowGraph(md); + Set reachableSet = flowGraph.getReachFlowNodeSetFrom(node); + if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) { + boolean hasCompReturnLocWithThis = + mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue(); + + if (hasCompReturnLocWithThis) { + for (Iterator iterator = flowGraph.getReturnNodeSet().iterator(); iterator.hasNext();) { + FlowNode returnFlowNode = (FlowNode) iterator.next(); + if (reachableSet.contains(returnFlowNode)) { + return true; + } + } + } + } + return false; } private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) { @@ -927,17 +1473,23 @@ public class LocationInference { Set incomingNodeSetPrefix = graph.getIncomingNodeSetByPrefix(node.getLocTuple().get(0)); - System.out.println("incomingNodeSetPrefix=" + incomingNodeSetPrefix); + // System.out.println("---incomingNodeSetPrefix=" + incomingNodeSetPrefix); Set reachableNodeSetPrefix = graph.getReachableNodeSetByPrefix(node.getLocTuple().get(0)); - System.out.println("reachableNodeSetPrefix=" + reachableNodeSetPrefix); + // System.out.println("---reachableNodeSetPrefix=" + reachableNodeSetPrefix); List> prefixList = new ArrayList>(); for (Iterator iterator = incomingNodeSetPrefix.iterator(); iterator.hasNext();) { GlobalFlowNode inNode = (GlobalFlowNode) iterator.next(); NTuple inNodeTuple = inNode.getLocTuple(); + + if (inNodeTuple.get(0).getLocDescriptor() instanceof InterDescriptor + || inNodeTuple.get(0).getLocDescriptor().equals(GLOBALDESC)) { + continue; + } + for (int i = 1; i < inNodeTuple.size(); i++) { NTuple prefix = inNodeTuple.subList(0, i); if (!prefixList.contains(prefix)) { @@ -980,34 +1532,6 @@ public class LocationInference { return prefixList; - // 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 boolean containsClassDesc(ClassDescriptor cd, NTuple prefixLocTuple) { @@ -1039,6 +1563,11 @@ public class LocationInference { NTuple srcDescTuple = edge.getInitTuple(); NTuple dstDescTuple = edge.getEndTuple(); + if (flowGraph.getFlowNode(srcDescTuple) instanceof FlowReturnNode + || flowGraph.getFlowNode(dstDescTuple) instanceof FlowReturnNode) { + continue; + } + // here only keep the first element(method location) of the descriptor // tuple NTuple srcLocTuple = translateToLocTuple(md, srcDescTuple); @@ -1095,8 +1624,7 @@ public class LocationInference { } - private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller, - GlobalFlowGraph subGlobalFlowGraph) { + private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller) { // the transformation for a call site propagates flows through parameters // if the method is virtual, it also grab all relations from any possible @@ -1129,12 +1657,13 @@ public class LocationInference { private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) { - // System.out.println("---propagate from " + min.printNode(0) + " to caller=" + mdCaller); + System.out.println("---propagate from " + min.printNode(0) + " to caller=" + mdCaller); FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); Map> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min); - // System.out.println("-----mapMethodInvokeNodeToArgIdxMap.get(min)=" - // + 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(); @@ -1143,10 +1672,14 @@ public class LocationInference { NTuple argLocTuple = translateToLocTuple(mdCaller, argDescTuple); NTuple paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple(); NTuple paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple); + System.out.println("-------paramDescTuple=" + paramDescTuple + "->argDescTuple=" + + argDescTuple); addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple); } } + // addValueFlowBetweenParametersToCaller(min, mdCaller, possibleMdCallee); + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee); Set calleeNodeSet = calleeSubGlobalGraph.getNodeSet(); @@ -1155,6 +1688,27 @@ public class LocationInference { addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode); } + System.out.println("$$$GLOBAL PC LOC ADD=" + mdCaller); + Set> pcLocTupleSet = mapMethodInvokeNodeToPCLocTupleSet.get(min); + System.out.println("---pcLocTupleSet=" + pcLocTupleSet); + GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next(); + if (calleeNode.isParamNodeWithIncomingFlows()) { + System.out.println("calleeNode.getLocTuple()" + calleeNode.getLocTuple()); + NTuple callerSrcNodeLocTuple = + translateToCallerLocTuple(min, possibleMdCallee, mdCaller, calleeNode.getLocTuple()); + System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple); + if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) { + for (Iterator iterator2 = pcLocTupleSet.iterator(); iterator2.hasNext();) { + NTuple pcLocTuple = (NTuple) iterator2.next(); + callerSubGlobalGraph.addValueFlowEdge(pcLocTuple, callerSrcNodeLocTuple); + } + } + } + + } + } private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller, @@ -1163,16 +1717,22 @@ public class LocationInference { GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + // System.out.println("$addValueFlowFromCalleeNode calleeSrcNode=" + calleeSrcNode); + NTuple callerSrcNodeLocTuple = translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple()); + // System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple); + + if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) { - 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()); + // System.out.println("outNode=" + outNode + " callerDstNodeLocTuple=" + // + callerDstNodeLocTuple); if (callerDstNodeLocTuple != null) { callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple); } @@ -1193,10 +1753,11 @@ public class LocationInference { int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple); NTuple argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); - if (isPrimitive(nodeLocTuple.get(0).getLocDescriptor())) { - // the type of argument is primitive. - return nodeLocTuple.clone(); - } + // if (isPrimitive(nodeLocTuple.get(0).getLocDescriptor())) { + // // the type of argument is primitive. + // return nodeLocTuple.clone(); + // } + // System.out.println("paramIdx=" + paramIdx + " argDescTuple=" + argDescTuple); NTuple argLocTuple = translateToLocTuple(mdCaller, argDescTuple); NTuple callerLocTuple = new NTuple(); @@ -1225,6 +1786,29 @@ public class LocationInference { return false; } + public static boolean isReference(Descriptor desc) { + + if (desc instanceof FieldDescriptor) { + + TypeDescriptor type = ((FieldDescriptor) desc).getType(); + if (type.isArray()) { + return false; + } else { + return type.isPtr(); + } + + } else if (desc instanceof VarDescriptor) { + TypeDescriptor type = ((VarDescriptor) desc).getType(); + if (type.isArray()) { + return false; + } else { + return type.isPtr(); + } + } + + return false; + } + private NTuple translateToDescTuple(NTuple locTuple) { NTuple descTuple = new NTuple(); @@ -1503,7 +2087,7 @@ public class LocationInference { Set keySet = mapDescriptorToHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); - System.out.println("SSJAVA: remove redundant edges: " + desc); + // System.out.println("SSJAVA: remove redundant edges: " + desc); HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone(); simpleHierarchyGraph.setName(desc + "_SIMPLE"); simpleHierarchyGraph.removeRedundantEdges(); @@ -1715,7 +2299,9 @@ public class LocationInference { // visit each node of method flow graph FlowGraph fg = getFlowGraph(md); - Set nodeSet = fg.getNodeSet(); + // Set nodeSet = fg.getNodeSet(); + + Set edgeSet = fg.getEdgeSet(); Set paramDescSet = fg.getMapParamDescToIdx().keySet(); for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) { @@ -1726,13 +2312,17 @@ public class LocationInference { // for the method lattice, we need to look at the first element of // NTuple boolean hasGlobalAccess = false; - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - FlowNode originalSrcNode = (FlowNode) iterator.next(); + // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + // FlowNode originalSrcNode = (FlowNode) iterator.next(); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + FlowEdge edge = (FlowEdge) iterator.next(); + FlowNode originalSrcNode = fg.getFlowNode(edge.getInitTuple()); Set sourceNodeSet = new HashSet(); if (originalSrcNode instanceof FlowReturnNode) { FlowReturnNode rnode = (FlowReturnNode) originalSrcNode; - Set> tupleSet = rnode.getTupleSet(); + System.out.println("rnode=" + rnode); + Set> tupleSet = rnode.getReturnTupleSet(); for (Iterator iterator2 = tupleSet.iterator(); iterator2.hasNext();) { NTuple nTuple = (NTuple) iterator2.next(); sourceNodeSet.add(fg.getFlowNode(nTuple)); @@ -1742,82 +2332,111 @@ public class LocationInference { sourceNodeSet.add(originalSrcNode); } - System.out.println("---sourceNodeSet=" + sourceNodeSet); + // System.out.println("---sourceNodeSet=" + sourceNodeSet + " from originalSrcNode=" + // + originalSrcNode); + for (Iterator iterator3 = sourceNodeSet.iterator(); iterator3.hasNext();) { FlowNode srcNode = (FlowNode) iterator3.next(); + NTuple srcNodeTuple = srcNode.getDescTuple(); + Descriptor srcLocalDesc = srcNodeTuple.get(0); + + if (srcLocalDesc instanceof InterDescriptor + && ((InterDescriptor) srcLocalDesc).getMethodArgIdxPair() != null) { + + if (srcNode.getCompositeLocation() == null) { + continue; + } + } + // if the srcNode is started with the global descriptor // need to set as a skeleton node if (!hasGlobalAccess && srcNode.getDescTuple().startsWith(GLOBALDESC)) { hasGlobalAccess = true; } - Set outEdgeSet = fg.getOutEdgeSet(originalSrcNode); - for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { - FlowEdge outEdge = (FlowEdge) iterator2.next(); - FlowNode originalDstNode = outEdge.getDst(); - - Set dstNodeSet = new HashSet(); - if (originalDstNode instanceof FlowReturnNode) { - FlowReturnNode rnode = (FlowReturnNode) originalDstNode; - Set> tupleSet = rnode.getTupleSet(); - for (Iterator iterator4 = tupleSet.iterator(); iterator4.hasNext();) { - NTuple nTuple = (NTuple) iterator4.next(); - dstNodeSet.add(fg.getFlowNode(nTuple)); - } - } else { - dstNodeSet.add(originalDstNode); + // Set outEdgeSet = fg.getOutEdgeSet(originalSrcNode); + // for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { + // FlowEdge outEdge = (FlowEdge) iterator2.next(); + // FlowNode originalDstNode = outEdge.getDst(); + FlowNode originalDstNode = fg.getFlowNode(edge.getEndTuple()); + + Set dstNodeSet = new HashSet(); + if (originalDstNode instanceof FlowReturnNode) { + FlowReturnNode rnode = (FlowReturnNode) originalDstNode; + // System.out.println("\n-returnNode=" + rnode); + Set> tupleSet = rnode.getReturnTupleSet(); + for (Iterator iterator4 = tupleSet.iterator(); iterator4.hasNext();) { + NTuple nTuple = (NTuple) iterator4.next(); + dstNodeSet.add(fg.getFlowNode(nTuple)); + System.out.println("&&&DST fg.getFlowNode(nTuple)=" + fg.getFlowNode(nTuple)); } - System.out.println("---dstNodeSet=" + dstNodeSet); - for (Iterator iterator4 = dstNodeSet.iterator(); iterator4.hasNext();) { - FlowNode dstNode = (FlowNode) iterator4.next(); + } else { + dstNodeSet.add(originalDstNode); + } + // System.out.println("---dstNodeSet=" + dstNodeSet); + for (Iterator iterator4 = dstNodeSet.iterator(); iterator4.hasNext();) { + FlowNode dstNode = (FlowNode) iterator4.next(); - NTuple srcNodeTuple = srcNode.getDescTuple(); - NTuple dstNodeTuple = dstNode.getDescTuple(); + NTuple dstNodeTuple = dstNode.getDescTuple(); + Descriptor dstLocalDesc = dstNodeTuple.get(0); + + if (dstLocalDesc instanceof InterDescriptor + && ((InterDescriptor) dstLocalDesc).getMethodArgIdxPair() != null) { + if (dstNode.getCompositeLocation() == null) { + System.out.println("%%%%%%%%%%%%%SKIP=" + dstNode); + continue; + } + } - // if (outEdge.getInitTuple().equals(srcNodeTuple) - // && outEdge.getEndTuple().equals(dstNodeTuple)) { + // if (outEdge.getInitTuple().equals(srcNodeTuple) + // && outEdge.getEndTuple().equals(dstNodeTuple)) { - NTuple srcCurTuple = srcNode.getCurrentDescTuple(); - NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + NTuple srcCurTuple = srcNode.getCurrentDescTuple(); + NTuple dstCurTuple = dstNode.getCurrentDescTuple(); - // System.out.println("-srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple); + System.out.println("-srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple + + " srcNode=" + srcNode + " dstNode=" + dstNode); - if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) - && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { + if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) + && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { - // value flows between fields - Descriptor desc = srcCurTuple.get(0); - ClassDescriptor classDesc; + // value flows between fields + Descriptor desc = srcCurTuple.get(0); + ClassDescriptor classDesc; - if (desc.equals(GLOBALDESC)) { - classDesc = md.getClassDesc(); - } else { - VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0); - classDesc = varDesc.getType().getClassDesc(); - } - extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1); + if (desc.equals(GLOBALDESC)) { + classDesc = md.getClassDesc(); + } else { + VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0); + classDesc = varDesc.getType().getClassDesc(); + } + extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1); - } else if (!srcCurTuple.get(0).equals(dstCurTuple.get(0))) { - // value flow between local var - local var or local var - field + } else if ((srcCurTuple.size() == 1 && dstCurTuple.size() == 1) + || ((srcCurTuple.size() > 1 || dstCurTuple.size() > 1) && !srcCurTuple.get(0).equals( + dstCurTuple.get(0)))) { - Descriptor srcDesc = srcCurTuple.get(0); - Descriptor dstDesc = dstCurTuple.get(0); + // value flow between a primitive local var - a primitive local var or local var - + // field - methodGraph.addEdge(srcDesc, dstDesc); + Descriptor srcDesc = srcCurTuple.get(0); + Descriptor dstDesc = dstCurTuple.get(0); - if (fg.isParamDesc(srcDesc)) { - methodGraph.setParamHNode(srcDesc); - } - if (fg.isParamDesc(dstDesc)) { - methodGraph.setParamHNode(dstDesc); - } + methodGraph.addEdge(srcDesc, dstDesc); + if (fg.isParamDesc(srcDesc)) { + methodGraph.setParamHNode(srcDesc); + } + if (fg.isParamDesc(dstDesc)) { + methodGraph.setParamHNode(dstDesc); } - // } } + // } + // } + } } @@ -2097,6 +2716,9 @@ public class LocationInference { String orgSourceLine = sourceVec.get(varLineNum); int idx = orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc)); + System.out.println("idx=" + idx + + " generateVarDeclaration((VarDescriptor) localVarDesc)=" + + generateVarDeclaration((VarDescriptor) localVarDesc)); assert (idx != -1); String annoatedStr = orgSourceLine.substring(0, idx) + locAnnotationStr + " " @@ -2448,10 +3070,10 @@ public class LocationInference { } } - // System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet); + System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet); if (paramLocTupleHavingInFlowSet.size() > 0 - /* && !coversAllParamters(md, fg, paramLocTupleHavingInFlowSet) */) { + && !coversAllParamters(md, fg, paramLocTupleHavingInFlowSet)) { // Here, generates a location in the method lattice that is higher than the // paramLocTupleHavingInFlowSet @@ -2466,16 +3088,47 @@ public class LocationInference { if (curPCLoc.get(0).isTop() || pcLocTuple.size() > curPCLoc.getSize()) { methodSummary.setPCLoc(new CompositeLocation(pcLocTuple)); + Set flowNodeLowerthanPCLocSet = new HashSet(); + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); // add ordering relations s.t. PCLOC is higher than all flow nodes except the set of // parameters that do not have incoming flows for (Iterator iterator = fg.getNodeSet().iterator(); iterator.hasNext();) { FlowNode node = (FlowNode) iterator.next(); - if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) { - fg.addValueFlowEdge(pcDescTuple, node.getDescTuple()); + if (!(node instanceof FlowReturnNode)) { + if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) { + flowNodeLowerthanPCLocSet.add(node); + fg.addValueFlowEdge(pcDescTuple, node.getDescTuple()); + subGlobalFlowGraph.addValueFlowEdge(pcLocTuple, + translateToLocTuple(md, node.getDescTuple())); + } + } else { + System.out.println("***SKIP PCLOC -> RETURNLOC=" + node); } + } fg.getFlowNode(translateToDescTuple(pcLocTuple)).setSkeleton(true); + + if (pcLocTuple.get(0).getLocDescriptor().equals(md.getThis())) { + System.out.println("#########################################"); + for (Iterator iterator = flowNodeLowerthanPCLocSet.iterator(); iterator.hasNext();) { + FlowNode lowerNode = (FlowNode) iterator.next(); + if (lowerNode.getCompositeLocation() == null) { + NTuple lowerLocTuple = translateToLocTuple(md, lowerNode.getDescTuple()); + CompositeLocation newComp = + calculateCompositeLocationFromSubGlobalGraph(md, lowerNode); + if (newComp != null) { + subGlobalFlowGraph.addMapLocationToInferCompositeLocation(lowerLocTuple.get(0), + newComp); + lowerNode.setCompositeLocation(newComp); + System.out.println("NEW COMP LOC=" + newComp + " to lowerNode=" + lowerNode); + } + + } + + } + } + } } @@ -2522,14 +3175,20 @@ public class LocationInference { private void calculateRETURNLOC(MethodDescriptor md) { System.out.println("#calculateRETURNLOC= " + md); + // calculate a return location: // the return location type is lower than all parameters and the location of return values MethodSummary methodSummary = getMethodSummary(md); + // if (methodSummary.getRETURNLoc() != null) { + // System.out.println("$HERE?"); + // return; + // } + FlowGraph fg = getFlowGraph(md); Map mapParamToLoc = methodSummary.getMapParamIdxToInferLoc(); Set paramIdxSet = mapParamToLoc.keySet(); - if (!md.getReturnType().isVoid()) { + if (md.getReturnType() != null && !md.getReturnType().isVoid()) { // first, generate the set of return value location types that starts // with 'this' reference @@ -2550,8 +3209,8 @@ public class LocationInference { NTuple returnDescTuple = returnNode.getCurrentDescTuple(); tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, returnDescTuple)); } - // System.out.println("-flow graph's returnNodeSet=" + returnNodeSet); - // System.out.println("tupleSetToBeHigherThanReturnLoc=" + tupleToBeHigherThanReturnLocSet); + System.out.println("-flow graph's returnNodeSet=" + returnNodeSet); + System.out.println("tupleSetToBeHigherThanReturnLoc=" + tupleToBeHigherThanReturnLocSet); // Here, generates a return location in the method lattice that is lower than the // locFlowingToReturnValueSet @@ -2572,6 +3231,13 @@ public class LocationInference { } + // makes sure that PCLOC is higher than RETURNLOC + CompositeLocation pcLoc = methodSummary.getPCLoc(); + if (!pcLoc.get(0).isTop()) { + NTuple pcLocDescTuple = translateToDescTuple(pcLoc.getTuple()); + fg.addValueFlowEdge(pcLocDescTuple, returnDescTuple); + } + } } @@ -2631,7 +3297,8 @@ public class LocationInference { } else { // all parameter is started with 'this', so PCLOC will be set relative to the composite // location started with 'this'. - for (int idx = 0; idx < minSize - 1; idx++) { + // for (int idx = 0; idx < minSize - 1; idx++) { + for (int idx = 0; idx < 1; idx++) { Set locDescSet = new HashSet(); Location curLoc = null; NTuple paramLocTuple = null; @@ -2647,17 +3314,17 @@ public class LocationInference { break; } Location newLocElement = new Location(curLoc.getDescriptor(), curLoc.getLocDescriptor()); + System.out.println("newLocElement" + newLocElement); higherLocTuple.add(newLocElement); enclosingDesc = getClassTypeDescriptor(curLoc.getLocDescriptor()); } } - String pcLocIdentifier = locNamePrefix + (locSeed++); - NameDescriptor pcLocDesc = new NameDescriptor(pcLocIdentifier); - Location newLoc = new Location(enclosingDesc, pcLocDesc); + String locIdentifier = locNamePrefix + (locSeed++); + NameDescriptor locDesc = new NameDescriptor(locIdentifier); + Location newLoc = new Location(enclosingDesc, locDesc); higherLocTuple.add(newLoc); - System.out.println("---new loc tuple=" + higherLocTuple); return higherLocTuple; @@ -2845,6 +3512,7 @@ public class LocationInference { private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor mdCallee) { + System.out.println("-propagateFlowsToCallerWithNoCompositeLocation=" + min.printNode(0)); // if the parameter A reaches to the parameter B // then, add an edge the argument A -> the argument B to the caller's flow // graph @@ -2867,15 +3535,17 @@ public class LocationInference { // check if the callee propagates an ordering constraints through // parameters - Set localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); - System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); - // System.out.println("-- localReachSet from param1=" + localReachSet); + // Set localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); + Set localReachSet = + calleeFlowGraph.getReachableSetFrom(paramNode1.getDescTuple()); NTuple paramDescTuple1 = paramNode1.getCurrentDescTuple(); NTuple paramDescTuple2 = paramNode2.getCurrentDescTuple(); - System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple=" - + paramDescTuple2); + // System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple=" + // + paramDescTuple2); + // System.out.println("-- localReachSet from param1=" + localReachSet); + if (paramDescTuple1.get(0).equals(paramDescTuple2.get(0))) { // if two parameters share the same prefix // it already has been assigned to a composite location @@ -2884,20 +3554,22 @@ public class LocationInference { continue; } - if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0 && localReachSet.contains(paramNode2)) { + if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0 + && containsPrefix(paramNode2.getDescTuple().get(0), localReachSet)) { // need to propagate an ordering relation s.t. arg1 is higher // than arg2 + // System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); // add a new flow between the corresponding arguments. callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); - System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); + // System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); // System.out // .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple); } - System.out.println(); + // System.out.println(); } } } @@ -2910,9 +3582,14 @@ public class LocationInference { for (int idx = 0; idx < numParam; idx++) { FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); CompositeLocation compLoc = paramNode.getCompositeLocation(); + System.out.println("paramNode=" + paramNode + " compLoc=" + compLoc); if (compLoc != null && compLoc.get(0).getLocDescriptor().equals(min.getMethod().getThis())) { - System.out.println("$$$COMPLOC CASE=" + compLoc); + System.out.println("$$$COMPLOC CASE=" + compLoc + " idx=" + idx); + NTuple argTuple = getNodeTupleByArgIdx(min, idx); + System.out.println("--- argTuple=" + argTuple + " current compLoc=" + + callerFlowGraph.getFlowNode(argTuple).getCompositeLocation()); + NTuple translatedParamTuple = translateCompositeLocationToCaller(idx, min, compLoc); System.out.println("add a flow edge= " + argTuple + "->" + translatedParamTuple); @@ -2929,6 +3606,18 @@ public class LocationInference { } + private boolean containsPrefix(Descriptor prefixDesc, Set set) { + + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + if (flowNode.getDescTuple().startsWith(prefixDesc)) { + System.out.println("FOUND=" + flowNode); + return true; + } + } + return false; + } + private NTuple translateCompositeLocationToCaller(int idx, MethodInvokeNode min, CompositeLocation compLocForParam1) { @@ -2939,7 +3628,7 @@ public class LocationInference { tuple.add(baseTuple.get(i)); } - for (int i = baseTuple.size(); i < compLocForParam1.getSize(); i++) { + for (int i = 1; i < compLocForParam1.getSize(); i++) { Location loc = compLocForParam1.get(i); tuple.add(loc.getLocDescriptor()); } @@ -3034,52 +3723,6 @@ public class LocationInference { } - private List> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) { - - System.out.println("\n##### calculatePrefixList=" + flowNode); - - Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); - inNodeSet.add(flowNode); - - System.out.println("inNodeSet=" + inNodeSet); - - List> prefixList = new ArrayList>(); - - for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { - FlowNode inNode = (FlowNode) iterator.next(); - - NTuple inNodeTuple = inNode.getCurrentDescTuple(); - - // CompositeLocation inNodeInferredLoc = - // generateInferredCompositeLocation(methodInfo, inNodeTuple); - // NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); - - 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; - - } - public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple tuple) { CompositeLocation compLoc = new CompositeLocation(); @@ -3283,8 +3926,16 @@ public class LocationInference { Descriptor srcFieldDesc = srcCurTuple.get(idx); Descriptor dstFieldDesc = dstCurTuple.get(idx); - // add a new edge - getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); + System.out.println("srcFieldDesc=" + srcFieldDesc + " dstFieldDesc=" + dstFieldDesc + + " idx=" + idx); + if (!srcFieldDesc.equals(dstFieldDesc)) { + // add a new edge + System.out.println("-ADD EDGE"); + getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); + } else if (!isReference(srcFieldDesc) && !isReference(dstFieldDesc)) { + System.out.println("-ADD EDGE"); + getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); + } } @@ -3331,7 +3982,8 @@ public class LocationInference { for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { MethodDescriptor calleemd = (MethodDescriptor) iterator.next(); if ((!ssjava.isTrustMethod(calleemd)) - && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) { + && (!ssjava.isSSJavaUtil(calleemd.getClassDesc())) + && (!calleemd.getModifiers().isNative())) { if (!visited.contains(calleemd)) { temp_toanalyzeMethodList.add(calleemd); } @@ -3413,7 +4065,6 @@ public class LocationInference { // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); // // propagateFlowsFromCalleesWithNoCompositeLocation(md); - } } // _debug_printGraph(); @@ -3430,17 +4081,42 @@ public class LocationInference { System.out.println(); System.out.println("SSJAVA: Constructing a sub global flow graph: " + md); - GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(getFlowGraph(md)); + constructSubGlobalFlowGraph(getFlowGraph(md)); // TODO System.out.println("-add Value Flows From CalleeSubGlobalFlowGraph"); - addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + addValueFlowsFromCalleeSubGlobalFlowGraph(md); // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); // System.out.println("-propagate Flows From Callees With No CompositeLocation"); // propagateFlowsFromCalleesWithNoCompositeLocation(md); + // mark if a parameter has incoming flows + checkParamNodesInSubGlobalFlowGraph(md); + + } + } + } + + private void checkParamNodesInSubGlobalFlowGraph(MethodDescriptor md) { + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + FlowGraph flowGraph = getFlowGraph(md); + + Set paramFlowNodeSet = flowGraph.getParamFlowNodeSet(); + for (Iterator iterator = paramFlowNodeSet.iterator(); iterator.hasNext();) { + FlowNode paramFlowNode = (FlowNode) iterator.next(); + System.out.println("paramFlowNode=" + paramFlowNode); + NTuple paramDescTuple = paramFlowNode.getDescTuple(); + NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); + GlobalFlowNode paramGlobalNode = globalFlowGraph.getFlowNode(paramLocTuple); + + Set incomingNodeSet = + globalFlowGraph.getIncomingNodeSetByPrefix(paramLocTuple.get(0)); + + if (incomingNodeSet.size() > 0) { + paramGlobalNode.setParamNodeWithIncomingFlows(true); } + } } @@ -3563,6 +4239,7 @@ public class LocationInference { if (needToGenerateInterLoc(newImplicitTupleSet)) { // need to create an intermediate node for the GLB of conditional // locations & implicit flows + System.out.println("10"); NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { @@ -3629,6 +4306,8 @@ public class LocationInference { // System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet); if (needToGenerateInterLoc(currentFlowTupleSet)) { + System.out.println("9"); + FlowNode meetNode = fg.createIntermediateNode(); for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) { NTuple currentFlowTuple = (NTuple) iterator.next(); @@ -3667,6 +4346,7 @@ public class LocationInference { } } if (size > 1) { + System.out.println("needToGenerateInterLoc=" + tupleSet + " size=" + size); return true; } else { return false; @@ -3687,9 +4367,13 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); newImplicitTupleSet.addTupleSet(condTupleNode); + newImplicitTupleSet.addGlobalFlowTupleSet(implicitFlowTupleSet.getGlobalLocTupleSet()); + newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet()); + if (needToGenerateInterLoc(newImplicitTupleSet)) { // need to create an intermediate node for the GLB of conditional // locations & implicit flows + System.out.println("6"); NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter @@ -3750,6 +4434,7 @@ public class LocationInference { if (needToGenerateInterLoc(newImplicitTupleSet)) { // need to create an intermediate node for the GLB of conditional // locations & implicit flows + System.out.println("7"); NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter @@ -3807,12 +4492,14 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); newImplicitTupleSet.addTupleSet(condTupleNode); + // System.out.println("$$$GGGcondTupleNode=" + condTupleNode.getGlobalLocTupleSet()); // System.out.println("-condTupleNode=" + condTupleNode); // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet); if (needToGenerateInterLoc(newImplicitTupleSet)) { - System.out.println("2"); + System.out.println("5"); + // 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();) { @@ -3823,6 +4510,18 @@ public class LocationInference { newImplicitTupleSet.addTuple(interTuple); } + // GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + // for (Iterator> iterator = condTupleNode.globalIterator(); + // iterator.hasNext();) { + // NTuple calleeReturnLocTuple = iterator.next(); + // for (Iterator> iter2 = newImplicitTupleSet.iterator(); iter2.hasNext();) { + // NTuple callerImplicitTuple = iter2.next(); + // globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + // translateToLocTuple(md, callerImplicitTuple)); + // } + // } + newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet()); + analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet); if (isn.getFalseBlock() != null) { @@ -3850,12 +4549,14 @@ public class LocationInference { // creates edges from RHS to LHS NTuple interTuple = null; if (needToGenerateInterLoc(nodeSetRHS)) { - + System.out.println("3"); interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); } for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { NTuple fromTuple = iter.next(); + System.out.println("fromTuple=" + fromTuple + " interTuple=" + interTuple + " tupleLSH=" + + tupleLHS); addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS); } @@ -3865,6 +4566,12 @@ public class LocationInference { addFlowGraphEdge(md, implicitTuple, tupleLHS); } + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, tupleLHS)); + } + } } @@ -3887,9 +4594,7 @@ public class LocationInference { // note that expression node can create more than one flow node // nodeSet contains of flow nodes // base is always assigned to null except the case of a name node! - NTuple flowTuple; - switch (en.kind()) { case Kind.AssignmentNode: @@ -3961,6 +4666,7 @@ public class LocationInference { // return null; } + return null; } @@ -3976,20 +4682,48 @@ public class LocationInference { private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + System.out.println("analyzeFlowTertiaryNode=" + tn.printNode(0)); + NodeTupleSet tertiaryTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null, implicitFlowTupleSet, false); + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(tertiaryTupleNode); + + // System.out.println("$$$GGGcondTupleNode=" + tertiaryTupleNode.getGlobalLocTupleSet()); + // System.out.println("-tertiaryTupleNode=" + tertiaryTupleNode); + // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet); + + if (needToGenerateInterLoc(newImplicitTupleSet)) { + System.out.println("15"); + // 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(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); + } + + newImplicitTupleSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet()); + + System.out.println("---------newImplicitTupleSet=" + newImplicitTupleSet); // add edges from tertiaryTupleNode to all nodes of conditional nodes - tertiaryTupleNode.addTupleSet(implicitFlowTupleSet); + // tertiaryTupleNode.addTupleSet(implicitFlowTupleSet); analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null, - implicitFlowTupleSet, false); + newImplicitTupleSet, false); analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null, - implicitFlowTupleSet, false); + newImplicitTupleSet, false); + nodeSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet()); nodeSet.addTupleSet(tertiaryTupleNode); + System.out.println("#tertiary node set=" + nodeSet); } private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller, @@ -4029,12 +4763,21 @@ public class LocationInference { private void analyzeFlowMethodInvokeNode(MethodDescriptor mdCaller, SymbolTable nametable, MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { - // System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0)); + System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0)); + + if (!toanalyze_methodDescList.contains(min.getMethod())) { + return; + } + + addMapMethodDescToMethodInvokeNodeSet(min); Set> pcLocTupleSet = getPCLocTupleSet(min); for (Iterator iterator = implicitFlowTupleSet.iterator(); iterator.hasNext();) { NTuple pcDescTuple = (NTuple) iterator.next(); - pcLocTupleSet.add(translateToLocTuple(mdCaller, pcDescTuple)); + if (!pcDescTuple.get(0).equals(LITERALDESC)) { + // here we don't need to add the literal value as a PC location + pcLocTupleSet.add(translateToLocTuple(mdCaller, pcDescTuple)); + } } mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap>()); @@ -4057,22 +4800,12 @@ public class LocationInference { addMapCallerMethodDescToMethodInvokeNodeSet(mdCaller, min); FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); - + System.out.println("mdCallee=" + mdCallee); Set calleeReturnSet = calleeFlowGraph.getReturnNodeSet(); System.out.println("---calleeReturnSet=" + calleeReturnSet); - // when generating the global flow graph, - // we need to add ordering relations from the set of callee return loc tuple to LHS of the - // caller assignment - for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { - FlowNode calleeReturnNode = (FlowNode) iterator.next(); - NTuple calleeReturnLocTuple = - translateToLocTuple(mdCallee, calleeReturnNode.getDescTuple()); - nodeSet.addGlobalFlowTuple(calleeReturnLocTuple); - } - - FlowReturnNode setNode = getFlowGraph(mdCaller).createReturnNode(min); + NodeTupleSet tupleSet = new NodeTupleSet(); if (min.getExpression() != null) { @@ -4096,7 +4829,7 @@ public class LocationInference { NTuple inFlowTuple = new NTuple(baseTuple.getList()); inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); // nodeSet.addTuple(inFlowTuple); - setNode.addTuple(inFlowTuple); + tupleSet.addTuple(inFlowTuple); } else { // TODO Set inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode); @@ -4105,7 +4838,7 @@ public class LocationInference { FlowNode inFlowNode = (FlowNode) iterator2.next(); if (inFlowNode.getDescTuple().startsWith(mdCallee.getThis())) { // nodeSet.addTupleSet(baseNodeSet); - setNode.addTupleSet(baseNodeSet); + tupleSet.addTupleSet(baseNodeSet); } } @@ -4131,19 +4864,23 @@ public class LocationInference { NodeTupleSet argTupleSet = new NodeTupleSet(); analyzeFlowExpressionNode(mdCaller, nametable, en, argTupleSet, false); // if argument is liternal node, argTuple is set to NULL - - NTuple argTuple = new NTuple(); - if (needToGenerateInterLoc(argTupleSet)) { - NTuple interTuple = - getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); - for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { - NTuple tuple = idxIter.next(); - addFlowGraphEdge(mdCaller, tuple, interTuple); - } - argTuple = interTuple; - } else if (argTupleSet.size() == 1) { - argTuple = argTupleSet.iterator().next(); - } else { + System.out.println("argTupleSet=" + argTupleSet); + NTuple argTuple = generateArgTuple(mdCaller, argTupleSet); + + // if an argument is literal value, + // we need to create an itermediate node so that we could assign a composite location to + // that node if needed + if (argTuple.size() > 0 + && (argTuple.get(0).equals(GLOBALDESC) || argTuple.get(0).equals(LITERALDESC))) { + /* + * System.out.println("***GLOBAL ARG TUPLE CASE=" + argTuple); System.out.println("8"); + * + * NTuple interTuple = + * getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); ((InterDescriptor) + * interTuple.get(0)).setMethodArgIdxPair(min, idx); addFlowGraphEdge(mdCaller, + * argTuple, interTuple); argTuple = interTuple; addArgIdxMap(min, idx, argTuple); + * System.out.println("new min mapping i=" + idx + " ->" + argTuple); + */ argTuple = new NTuple(); } @@ -4163,20 +4900,78 @@ public class LocationInference { // } // } + System.out.println("paramNode=" + paramNode + " calleeReturnSet=" + calleeReturnSet); if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) || mdCallee.getModifiers().isNative()) { addParamNodeFlowingToReturnValue(mdCallee, paramNode); // nodeSet.addTupleSet(argTupleSet); - setNode.addTupleSet(argTupleSet); + tupleSet.addTupleSet(argTupleSet); } } } - nodeSet.addTuple(setNode.getDescTuple()); + if (mdCallee.getReturnType() != null && !mdCallee.getReturnType().isVoid()) { + FlowReturnNode setNode = getFlowGraph(mdCaller).createReturnNode(min); + System.out.println("ADD TUPLESET=" + tupleSet + " to returnnode=" + setNode); + setNode.addTupleSet(tupleSet); + nodeSet.addTuple(setNode.getDescTuple()); + } + // propagateFlowsFromCallee(min, md, min.getMethod()); + // when generating the global flow graph, + // we need to add ordering relations from the set of callee return loc tuple to LHS of the + // caller assignment + for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { + FlowNode calleeReturnNode = (FlowNode) iterator.next(); + NTuple calleeReturnLocTuple = + translateToLocTuple(mdCallee, calleeReturnNode.getDescTuple()); + System.out.println("calleeReturnLocTuple=" + calleeReturnLocTuple); + nodeSet.addGlobalFlowTuple(translateToCallerLocTuple(min, mdCallee, mdCaller, + calleeReturnLocTuple)); + } + System.out.println("min nodeSet=" + nodeSet); + + } + + } + + private NTuple generateArgTuple(MethodDescriptor mdCaller, NodeTupleSet argTupleSet) { + + int size = 0; + + // if argTupleSet is empty, it comes from the top location + if (argTupleSet.size() == 0) { + NTuple descTuple = new NTuple(); + descTuple.add(LITERALDESC); + return descTuple; + } + + Set> argTupleSetNonLiteral = new HashSet>(); + + for (Iterator> iter = argTupleSet.iterator(); iter.hasNext();) { + NTuple descTuple = iter.next(); + if (!descTuple.get(0).equals(LITERALDESC)) { + argTupleSetNonLiteral.add(descTuple); + } + } + + if (argTupleSetNonLiteral.size() > 1) { + System.out.println("11"); + + NTuple interTuple = + getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(mdCaller, tuple, interTuple); + } + return interTuple; + } else if (argTupleSetNonLiteral.size() == 1) { + return argTupleSetNonLiteral.iterator().next(); + } else { + return argTupleSet.iterator().next(); } } @@ -4184,9 +4979,13 @@ public class LocationInference { private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set nodeSet) { // return true if inNode has in-flows to nodeSet + if (nodeSet.contains(inNode)) { + // in this case, the method directly returns a parameter variable. + return true; + } // Set reachableSet = fg.getReachFlowNodeSetFrom(inNode); Set reachableSet = fg.getReachableSetFrom(inNode.getDescTuple()); - // System.out.println("inNode=" + inNode + " reachalbeSet=" + reachableSet); + System.out.println("inNode=" + inNode + " reachalbeSet=" + reachableSet); for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) { FlowNode fn = (FlowNode) iterator.next(); @@ -4223,6 +5022,10 @@ public class LocationInference { private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) { + // System.out.println("analyzeFlowArrayAccessNode aan=" + aan.printNode(0)); + String currentArrayAccessNodeExpStr = aan.printNode(0); + arrayAccessNodeStack.push(aan.printNode(0)); + NodeTupleSet expNodeTupleSet = new NodeTupleSet(); NTuple base = analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS); @@ -4230,6 +5033,8 @@ public class LocationInference { NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS); + arrayAccessNodeStack.pop(); + if (isLHS) { // need to create an edge from idx to array for (Iterator> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) { @@ -4240,6 +5045,16 @@ public class LocationInference { } } + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = idxNodeTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) { + NTuple arrTuple = arrIter.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, arrTuple)); + } + } + nodeSet.addTupleSet(expNodeTupleSet); } else { @@ -4248,19 +5063,27 @@ public class LocationInference { nodeSetArrayAccessExp.addTupleSet(expNodeTupleSet); nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet); - if (needToGenerateInterLoc(nodeSetArrayAccessExp)) { - NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + if (arrayAccessNodeStack.isEmpty() + || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) { + + if (needToGenerateInterLoc(nodeSetArrayAccessExp)) { + System.out.println("1"); + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); - for (Iterator> iter = nodeSetArrayAccessExp.iterator(); iter.hasNext();) { - NTuple higherTuple = iter.next(); - addFlowGraphEdge(md, higherTuple, interTuple); + for (Iterator> iter = nodeSetArrayAccessExp.iterator(); iter.hasNext();) { + NTuple higherTuple = iter.next(); + addFlowGraphEdge(md, higherTuple, interTuple); + } + nodeSetArrayAccessExp.clear(); + nodeSetArrayAccessExp.addTuple(interTuple); } - nodeSetArrayAccessExp.clear(); - nodeSetArrayAccessExp.addTuple(interTuple); } + nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet()); nodeSet.addTupleSet(nodeSetArrayAccessExp); + } + } private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable, @@ -4321,6 +5144,10 @@ public class LocationInference { // there are two operands nodeSet.addTupleSet(leftOpSet); nodeSet.addTupleSet(rightOpSet); + + nodeSet.addGlobalFlowTupleSet(leftOpSet.getGlobalLocTupleSet()); + nodeSet.addGlobalFlowTupleSet(rightOpSet.getGlobalLocTupleSet()); + break; default: @@ -4412,10 +5239,13 @@ public class LocationInference { private NTuple analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan, NodeTupleSet nodeSet, NTuple base, NodeTupleSet implicitFlowTupleSet, boolean isLHS) { + // System.out.println("analyzeFlowFieldAccessNode=" + fan.printNode(0)); + String currentArrayAccessNodeExpStr = null; ExpressionNode left = fan.getExpression(); TypeDescriptor ltd = left.getType(); FieldDescriptor fd = fan.getField(); + ArrayAccessNode aan = null; String varName = null; if (left.kind() == Kind.NameNode) { @@ -4432,14 +5262,19 @@ public class LocationInference { NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); + boolean isArrayCase = false; if (left instanceof ArrayAccessNode) { - ArrayAccessNode aan = (ArrayAccessNode) left; + isArrayCase = true; + aan = (ArrayAccessNode) left; + + currentArrayAccessNodeExpStr = aan.printNode(0); + arrayAccessNodeStack.push(currentArrayAccessNodeExpStr); + left = aan.getExpression(); analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base, implicitFlowTupleSet, isLHS); - nodeSet.addTupleSet(idxNodeTupleSet); } base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS); @@ -4452,13 +5287,11 @@ public class LocationInference { NTuple flowFieldTuple = new NTuple(base.toList()); if (!left.getType().isPrimitive()) { - if (!fd.getSymbol().equals("length")) { // array.length access, just have the location of the array flowFieldTuple.add(fd); nodeSet.removeTuple(base); } - } getFlowGraph(md).createNewFlowNode(flowFieldTuple); @@ -4467,9 +5300,55 @@ public class LocationInference { NTuple idxTuple = idxIter.next(); getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple); } + + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = idxNodeTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, flowFieldTuple)); + } + + } else { + nodeSet.addTupleSet(idxNodeTupleSet); + + // if it is the array case and not the LHS case + if (isArrayCase) { + arrayAccessNodeStack.pop(); + + if (arrayAccessNodeStack.isEmpty() + || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) { + NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet(); + + nodeSetArrayAccessExp.addTuple(flowFieldTuple); + nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet); + nodeSetArrayAccessExp.addTupleSet(nodeSet); + + if (needToGenerateInterLoc(nodeSetArrayAccessExp)) { + System.out.println("4"); + System.out.println("nodeSetArrayAccessExp=" + nodeSetArrayAccessExp); + // System.out.println("idxNodeTupleSet.getGlobalLocTupleSet()=" + // + idxNodeTupleSet.getGlobalLocTupleSet()); + + NTuple interTuple = + getFlowGraph(md).createIntermediateNode().getDescTuple(); + + for (Iterator> iter = nodeSetArrayAccessExp.iterator(); iter + .hasNext();) { + NTuple higherTuple = iter.next(); + addFlowGraphEdge(md, higherTuple, interTuple); + } + nodeSet.clear(); + flowFieldTuple = interTuple; + } + + nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet()); + } + + } + } return flowFieldTuple; - } } @@ -4503,10 +5382,10 @@ public class LocationInference { analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet, false); - // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0)); - // System.out.println("-nodeSetLHS=" + nodeSetLHS); - // System.out.println("-nodeSetRHS=" + nodeSetRHS); - // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0)); + System.out.println("-nodeSetLHS=" + nodeSetLHS); + System.out.println("-nodeSetRHS=" + nodeSetRHS); + System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); // System.out.println("-"); if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) { @@ -4524,6 +5403,7 @@ public class LocationInference { // creates edges from RHS to LHS NTuple interTuple = null; if (needToGenerateInterLoc(nodeSetRHS)) { + System.out.println("2"); interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); } @@ -4545,17 +5425,27 @@ public class LocationInference { } // create global flow edges if the callee gives return value flows to the caller - if (nodeSetRHS.globalLocTupleSize() > 0) { - GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); - for (Iterator> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) { - NTuple calleeReturnLocTuple = iterator.next(); - for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { - NTuple callerLHSTuple = iter2.next(); - globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, - translateToLocTuple(md, callerLHSTuple)); - // System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> " - // + translateToLocTuple(md, callerLHSTuple)); - } + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple callerLHSTuple = iter2.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, callerLHSTuple)); + System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> " + + translateToLocTuple(md, callerLHSTuple)); + } + } + + for (Iterator> iterator = implicitFlowTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple callerLHSTuple = iter2.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, callerLHSTuple)); + System.out.println("$$$ GLOBAL FLOW PCLOC ADD=" + calleeReturnLocTuple + " -> " + + translateToLocTuple(md, callerLHSTuple)); } } @@ -4576,10 +5466,24 @@ public class LocationInference { } } + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = implicitFlowTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple callerLHSTuple = iter2.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, callerLHSTuple)); + System.out.println("$$$ GLOBAL FLOW PC ADD=" + calleeReturnLocTuple + " -> " + + translateToLocTuple(md, callerLHSTuple)); + } + } + } if (nodeSet != null) { nodeSet.addTupleSet(nodeSetLHS); + nodeSet.addGlobalFlowTupleSet(nodeSetLHS.getGlobalLocTupleSet()); } } @@ -4610,6 +5514,8 @@ public class LocationInference { public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph, SSJavaLattice locOrder, String nameSuffix) { + System.out.println("@cd=" + cd); + System.out.println("@sharedLoc=" + locOrder.getSharedLocSet()); writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix); } @@ -4642,7 +5548,6 @@ public class LocationInference { String highLocId = pair.getFirst(); String lowLocId = pair.getSecond(); - if (!addedLocSet.contains(highLocId)) { addedLocSet.add(highLocId); drawNode(bw, locOrder, simpleHierarchyGraph, highLocId); @@ -4682,23 +5587,17 @@ public class LocationInference { private void drawNode(BufferedWriter bw, SSJavaLattice lattice, HierarchyGraph graph, String locName) throws IOException { - HNode node = graph.getHNode(locName); - - if (node == null) { - return; - } - String prettyStr; if (lattice.isSharedLoc(locName)) { prettyStr = locName + "*"; } else { prettyStr = locName; } - - if (node.isMergeNode()) { - Set mergeSet = graph.getMapHNodetoMergeSet().get(node); - prettyStr += ":" + convertMergeSetToString(graph, mergeSet); - } + // HNode node = graph.getHNode(locName); + // if (node != null && node.isMergeNode()) { + // Set mergeSet = graph.getMapHNodetoMergeSet().get(node); + // prettyStr += ":" + convertMergeSetToString(graph, mergeSet); + // } bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n"); } @@ -4727,8 +5626,18 @@ class CyclicFlowException extends Exception { class InterDescriptor extends Descriptor { + Pair minArgIdxPair; + public InterDescriptor(String name) { super(name); } + public void setMethodArgIdxPair(MethodInvokeNode min, int idx) { + minArgIdxPair = new Pair(min, new Integer(idx)); + } + + public Pair getMethodArgIdxPair() { + return minArgIdxPair; + } + }