From 5b4d50ee3ad588d3c4a1406c26c1e602d04e5581 Mon Sep 17 00:00:00 2001 From: yeom Date: Mon, 30 Jul 2012 17:42:23 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/SSJava/FlowGraph.java | 63 +- Robust/src/Analysis/SSJava/Location.java | 9 + .../Analysis/SSJava/LocationInference.java | 580 ++++++++++++------ Robust/src/Analysis/SSJava/LocationInfo.java | 112 +++- .../Analysis/SSJava/MethodLocationInfo.java | 26 +- Robust/src/Analysis/SSJava/SSJavaLattice.java | 79 +++ Robust/src/Util/Lattice.java | 14 +- 7 files changed, 628 insertions(+), 255 deletions(-) diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index 6382ed00..a2d1791b 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -23,6 +23,9 @@ public class FlowGraph { Set returnNodeSet; FlowNode thisVarNode; + Map, FlowNode> mapLocTupleToFlowNode; + Map> mapFlowNodeToLocTuple; + // maps the composite representation of field/var descriptors to infer nodes Map, FlowNode> mapDescTupleToInferNode; @@ -35,6 +38,8 @@ public class FlowGraph { public FlowGraph(MethodDescriptor md, Map mapParamDescToIdx) { this.md = md; + this.mapFlowNodeToLocTuple = new HashMap>(); + this.mapLocTupleToFlowNode = new HashMap, FlowNode>(); this.nodeSet = new HashSet(); this.mapDescTupleToInferNode = new HashMap, FlowNode>(); this.mapNodeToNeighborSet = new HashMap, Set>(); @@ -42,14 +47,16 @@ public class FlowGraph { this.mapParamDescToIdx.putAll(mapParamDescToIdx); this.returnNodeSet = new HashSet(); - // create a node for 'this' varialbe - NTuple thisDescTuple = new NTuple(); - thisDescTuple.add(md.getThis()); - FlowNode thisNode = new FlowNode(thisDescTuple, true); - NTuple thisVarTuple = new NTuple(); - thisVarTuple.add(md.getThis()); - createNewFlowNode(thisVarTuple); - thisVarNode = thisNode; + if (!md.isStatic()) { + // create a node for 'this' varialbe + NTuple thisDescTuple = new NTuple(); + thisDescTuple.add(md.getThis()); + FlowNode thisNode = new FlowNode(thisDescTuple, true); + NTuple thisVarTuple = new NTuple(); + thisVarTuple.add(md.getThis()); + createNewFlowNode(thisVarTuple); + thisVarNode = thisNode; + } } @@ -158,6 +165,8 @@ public class FlowGraph { mapDescTupleToInferNode.put(tuple, node); nodeSet.add(node); + mapLocTupleToFlowNode.put(getLocationTuple(node), node); + if (tuple.size() > 1) { NTuple baseTuple = tuple.subList(0, tuple.size() - 1); getFlowNode(baseTuple).addFieldNode(node); @@ -231,26 +240,28 @@ public class FlowGraph { public NTuple getLocationTuple(FlowNode fn) { - NTuple descTuple = fn.getDescTuple(); - - NTuple locTuple = new NTuple(); - - ClassDescriptor cd = null; - - for (int i = 0; i < descTuple.size(); i++) { - Descriptor d = descTuple.get(i); - Location loc; - if (i == 0) { - loc = new Location(md, d.getSymbol()); - cd = ((VarDescriptor) d).getType().getClassDesc(); - } else { - loc = new Location(cd, d.getSymbol()); - cd = ((FieldDescriptor) d).getType().getClassDesc(); + if (!mapFlowNodeToLocTuple.containsKey(fn)) { + NTuple descTuple = fn.getDescTuple(); + NTuple locTuple = new NTuple(); + ClassDescriptor cd = null; + + for (int i = 0; i < descTuple.size(); i++) { + Descriptor curDesc = descTuple.get(i); + Location loc; + if (i == 0) { + loc = new Location(md, curDesc.getSymbol()); + loc.setLocDescriptor(md); + cd = ((VarDescriptor) curDesc).getType().getClassDesc(); + } else { + loc = new Location(cd, curDesc.getSymbol()); + loc.setLocDescriptor(curDesc); + cd = ((FieldDescriptor) curDesc).getType().getClassDesc(); + } + locTuple.add(loc); } - locTuple.add(loc); + mapFlowNodeToLocTuple.put(fn, locTuple); } - - return locTuple; + return mapFlowNodeToLocTuple.get(fn); } public Set getIncomingFlowNodeSet(FlowNode node) { diff --git a/Robust/src/Analysis/SSJava/Location.java b/Robust/src/Analysis/SSJava/Location.java index fbab568e..7fe9331a 100644 --- a/Robust/src/Analysis/SSJava/Location.java +++ b/Robust/src/Analysis/SSJava/Location.java @@ -12,6 +12,7 @@ public class Location implements TypeExtension { int type; Descriptor d; String loc; + Descriptor locDesc; public Location(Descriptor d, String loc) { this.d = d; @@ -29,6 +30,14 @@ public class Location implements TypeExtension { } } + public void setLocDescriptor(Descriptor d) { + locDesc = d; + } + + public Descriptor getLocDescriptor() { + return locDesc; + } + public void setType(int type) { this.type = type; } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 60b56686..89c206d6 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -146,6 +146,8 @@ public class LocationInference { // 2) construct lattices inferLattices(); + simplifyLattices(); + debug_writeLatticeDotFile(); // 3) check properties @@ -153,6 +155,34 @@ public class LocationInference { } + private void simplifyLattices() { + + // generate lattice dot file + setupToAnalyze(); + + while (!toAnalyzeIsEmpty()) { + ClassDescriptor cd = toAnalyzeNext(); + + setupToAnalazeMethod(cd); + + SSJavaLattice classLattice = cd2lattice.get(cd); + if (classLattice != null) { + classLattice.removeRedundantEdges(); + } + + while (!toAnalyzeMethodIsEmpty()) { + MethodDescriptor md = toAnalyzeMethodNext(); + if (ssjava.needTobeAnnotated(md)) { + SSJavaLattice methodLattice = md2lattice.get(md); + if (methodLattice != null) { + methodLattice.removeRedundantEdges(); + } + } + } + } + + } + private void checkLattices() { LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); @@ -187,6 +217,7 @@ public class LocationInference { SSJavaLattice classLattice = cd2lattice.get(cd); if (classLattice != null) { ssjava.writeLatticeDotFile(cd, null, classLattice); + debug_printDescriptorToLocNameMapping(cd); } while (!toAnalyzeMethodIsEmpty()) { @@ -195,6 +226,7 @@ public class LocationInference { SSJavaLattice methodLattice = md2lattice.get(md); if (methodLattice != null) { ssjava.writeLatticeDotFile(cd, md, methodLattice); + debug_printDescriptorToLocNameMapping(md); } } } @@ -202,6 +234,17 @@ public class LocationInference { } + private void debug_printDescriptorToLocNameMapping(Descriptor desc) { + + LocationInfo info = getLocationInfo(desc); + System.out.println("## " + desc + " ##"); + System.out.println(info.getMapDescToInferLocation()); + LocationInfo locInfo = getLocationInfo(desc); + System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet()); + System.out.println("###################"); + + } + private void inferLattices() { // do fixed-point analysis @@ -231,16 +274,20 @@ public class LocationInference { SSJavaLattice methodLattice = new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); + MethodLocationInfo methodInfo = new MethodLocationInfo(md); + System.out.println(); System.out.println("SSJAVA: Inferencing the lattice from " + md); - analyzeMethodLattice(md, methodLattice); + analyzeMethodLattice(md, methodLattice, methodInfo); SSJavaLattice prevMethodLattice = getMethodLattice(md); + MethodLocationInfo prevMethodInfo = getMethodLocationInfo(md); - if (!methodLattice.equals(prevMethodLattice)) { + if ((!methodLattice.equals(prevMethodLattice)) || (!methodInfo.equals(prevMethodInfo))) { setMethodLattice(md, methodLattice); + setMethodLocInfo(md, methodInfo); // results for callee changed, so enqueue dependents caller for // further analysis @@ -259,6 +306,10 @@ public class LocationInference { } + private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) { + mapMethodDescToMethodLocationInfo.put(md, methodInfo); + } + private void checkLatticesOfVirtualMethods(MethodDescriptor md) { if (!md.isStatic()) { @@ -293,9 +344,6 @@ public class LocationInference { for (Iterator iterator2 = paramLocNameSet1.iterator(); iterator2.hasNext();) { String locName2 = (String) iterator2.next(); - // System.out.println("COMPARE " + locName1 + " - " + locName2 + " " - // + lattice1.isGreaterThan(locName1, locName2) + "-" - // + lattice2.isGreaterThan(locName1, locName2)); if (!locName1.equals(locName2)) { @@ -324,14 +372,19 @@ public class LocationInference { return desc; } - private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice) { - - MethodLocationInfo methodInfo = getMethodLocationInfo(md); + private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice, + MethodLocationInfo methodInfo) { // first take a look at method invocation nodes to newly added relations // from the callee analyzeLatticeMethodInvocationNode(md); + // grab the this location if the method use the 'this' reference + String thisLocSymbol = md.getThis().getSymbol(); + // if (methodLattice.getKeySet().contains(thisLocSymbol)) { + methodInfo.setThisLocName(thisLocSymbol); + // } + // visit each node of method flow graph FlowGraph fg = getFlowGraph(md); Set nodeSet = fg.getNodeSet(); @@ -360,12 +413,22 @@ public class LocationInference { ClassDescriptor varClassDesc = varDesc.getType().getClassDesc(); extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1); - } else { + } else if (srcNodeTuple.size() == 1 || dstNodeTuple.size() == 1) { // for the method lattice, we need to look at the first element of // NTuple - if (srcNodeTuple.size() == 1 || dstNodeTuple.size() == 1) { + // in this case, take a look at connected nodes at the local level + addRelationToLattice(md, methodLattice, methodInfo, srcNode, dstNode); + } else { + + if (!srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0))) { // in this case, take a look at connected nodes at the local level - addRelationToLattice(md, methodLattice, srcNode, dstNode); + addRelationToLattice(md, methodLattice, methodInfo, srcNode, dstNode); + } else { + Descriptor srcDesc = srcNode.getDescTuple().get(0); + Descriptor dstDesc = dstNode.getDescTuple().get(0); + recursivelyAddCompositeRelation(md, fg, methodInfo, srcNode, dstNode, srcDesc, + dstDesc); + // recursiveAddRelationToLattice(1, md, srcNode, dstNode); } } @@ -373,12 +436,6 @@ public class LocationInference { } } - // grab the this location if the method use the 'this' reference - String thisLocSymbol = md.getThis().getSymbol(); - if (methodLattice.getKeySet().contains(thisLocSymbol)) { - methodInfo.setThisLocName(thisLocSymbol); - } - // calculate a return location if (!md.getReturnType().isVoid()) { Set returnNodeSet = fg.getReturnNodeSet(); @@ -404,6 +461,25 @@ public class LocationInference { } + private void recursiveAddRelationToLattice(int idx, MethodDescriptor md, + CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) { + + 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 analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller) { // the transformation for a call site propagates all relations between @@ -509,142 +585,121 @@ public class LocationInference { } private void addRelationToLattice(MethodDescriptor md, SSJavaLattice methodLattice, - FlowNode srcNode, FlowNode dstNode) { + MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode) { + System.out.println(); System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode); // add a new binary relation of dstNode < srcNode FlowGraph flowGraph = getFlowGraph(md); - MethodLocationInfo methodInfo = getMethodLocationInfo(md); + // MethodLocationInfo methodInfo = getMethodLocationInfo(md); - String srcOriginSymbol = getSymbol(0, srcNode); - String dstOriginSymbol = getSymbol(0, dstNode); + // String srcOriginSymbol = getSymbol(0, srcNode); + // String dstOriginSymbol = getSymbol(0, dstNode); Descriptor srcDesc = getDescriptor(0, srcNode); Descriptor dstDesc = getDescriptor(0, dstNode); - String srcSymbol = methodInfo.getLocName(srcOriginSymbol); - String dstSymbol = methodInfo.getLocName(dstOriginSymbol); + // consider a composite location case + boolean isSrcLocalVar = false; + boolean isDstLocalVar = false; + if (srcNode.getDescTuple().size() == 1) { + isSrcLocalVar = true; + } + + if (dstNode.getDescTuple().size() == 1) { + isDstLocalVar = true; + } + + boolean isAssignedCompositeLocation = false; + if (!methodInfo.getInferLocation(srcDesc).get(0).getLocIdentifier() + .equals(methodInfo.getThisLocName())) { + isAssignedCompositeLocation = + calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode); + } + + String srcSymbol = methodInfo.getInferLocation(srcDesc).get(0).getLocIdentifier(); + String dstSymbol = methodInfo.getInferLocation(dstDesc).get(0).getLocIdentifier(); + if (srcNode.isParameter()) { int paramIdx = flowGraph.getParamIdx(srcNode.getDescTuple()); methodInfo.addParameter(srcSymbol, srcDesc, paramIdx); } else { - methodInfo.addMappingOfLocNameToDescriptor(srcSymbol, srcDesc); + // methodInfo.addMappingOfLocNameToDescriptor(srcSymbol, srcDesc); } if (dstNode.isParameter()) { int paramIdx = flowGraph.getParamIdx(dstNode.getDescTuple()); methodInfo.addParameter(dstSymbol, dstDesc, paramIdx); } else { - methodInfo.addMappingOfLocNameToDescriptor(dstSymbol, dstDesc); + // methodInfo.addMappingOfLocNameToDescriptor(dstSymbol, dstDesc); } - // consider a composite location case + if (!isAssignedCompositeLocation) { + // source does not have a composite location + if (!srcSymbol.equals(dstSymbol)) { + // add a local relation + if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) { + // if the lattice does not have this relation, add it + addRelationHigherToLower(methodLattice, methodInfo, srcSymbol, dstSymbol); + // methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); + } + } else { + // if src and dst have the same local location... - boolean isSrcLocalVar = false; - boolean isDstLocalVar = false; - if (srcNode.getDescTuple().size() == 1) { - isSrcLocalVar = true; - } + recursivelyAddCompositeRelation(md, flowGraph, methodInfo, srcNode, dstNode, srcDesc, + dstDesc); + + } + + } else { + // source variable has a composite location + if (methodInfo.getInferLocation(dstDesc).getSize() == 1) { + if (!srcSymbol.equals(dstSymbol)) { + addRelationHigherToLower(methodLattice, methodInfo, srcSymbol, dstSymbol); + } + } - if (dstNode.getDescTuple().size() == 1) { - isDstLocalVar = true; } - boolean isAssignedCompositeLocation = false; - if (isSrcLocalVar && isDstLocalVar) { - // both src and dst are local var - - // CompositeLocation inferSrc=methodInfo.getInferLocation(srcNode); - // CompositeLocation inferDst=methodInfo.getInferLocation(dstNode); - // if( (inferSrc!=null && inferSrc.getSize()>1) || (inferDst!=null && - // inferDst.getSize()>1)){ - // isAssignedCompositeLocation = true; - // } - // TODO: need to fix - isAssignedCompositeLocation = - calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, srcNode); - calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, dstNode); + } - } else if (isSrcLocalVar) { - // src is local var - isAssignedCompositeLocation = - calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, srcNode); - } else if (isDstLocalVar) { - // dst is local var - isAssignedCompositeLocation = - calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, dstNode); - } + private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph, + MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode, Descriptor srcDesc, + Descriptor dstDesc) { - if (!isAssignedCompositeLocation) { - if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) { - // if the lattice does not have this relation, add it - methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); + 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); } - // Set cycleElementSet = - // methodLattice.getPossibleCycleElements(srcSymbol, dstSymbol); - // - // System.out.println("### POSSIBLE CYCLE ELEMENT SET=" + cycleElementSet); - // boolean hasNonPrimitiveElement = false; - // for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) - // { - // String cycleElementSymbol = (String) iterator.next(); - // Set flowNodeSet = - // methodInfo.getFlowNodeSet(cycleElementSymbol); - // for (Iterator iterator2 = flowNodeSet.iterator(); iterator2.hasNext();) { - // Descriptor desc = (Descriptor) iterator2.next(); - // if (!isPrimitiveTypeDescriptor(desc)) { - // hasNonPrimitiveElement = true; - // } - // System.out - // .println("flowNode=" + desc + " is primitive?=" + - // isPrimitiveTypeDescriptor(desc)); - // } - // } - // - // if (hasNonPrimitiveElement) { - // // if there is non-primitive element in the cycle, no way to merge cyclic - // // elements into the shared location - // System.out.println("Failed to merge cyclic value flows into a shared location."); - // - // // try to assign more fine-grind composite location to the source or the - // // destination - // System.out.println("SRC=" + srcSymbol + " DST=" + dstSymbol); - // System.out.println("### SRCNODE=" + srcNode + " DSTNODE=" + dstNode); - // - // FlowNode targetNode; - // if (isPrimitiveLocalVariable(srcNode)) { - // targetNode = srcNode; - // } else { - // targetNode = dstNode; - // } - // - // calculateMoreFineGrainedLocation(md, methodLattice, targetNode); - // - // return; - // } - // - // if (cycleElementSet.size() > 0) { - // String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++); - // methodLattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc); - // - // for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) - // { - // String locName = (String) iterator.next(); - // methodInfo.mapDescSymbolToLocName(locName, newSharedLoc); - // } - // - // } else if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) { - // // if the lattice does not have this relation, add it - // methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); - // } - // - // System.out.println("methodLattice=" + methodLattice.getKeySet()); + 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, @@ -654,42 +709,27 @@ public class LocationInference { map.put(prefix, new HashSet>()); } map.get(prefix).add(element); - - } - - private NTuple getLocationTuple(MethodLocationInfo methodInfo, FlowGraph flowGraph, - FlowNode flowNode) { - - NTuple locTuple; - CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode); - if (inferLoc != null) { - // the flow node has already been assigned to the location - locTuple = new NTuple(); - NTuple inferLocTuple = inferLoc.getTuple(); - for (int i = 0; i < inferLocTuple.size(); i++) { - locTuple.add(inferLocTuple.get(i)); - } - } else { - locTuple = flowGraph.getLocationTuple(flowNode); - } - - return locTuple; } - private boolean calculateCompositeLocationForLocalVar(FlowGraph flowGraph, + private boolean calculateCompositeLocation(FlowGraph flowGraph, SSJavaLattice methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode) { + Descriptor localVarDesc = flowNode.getDescTuple().get(0); + Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); Set reachableNodeSet = flowGraph.getReachableFlowNodeSet(flowNode); Map, Set>> mapPrefixToIncomingLocTupleSet = new HashMap, Set>>(); + Set localInNodeSet = new HashSet(); + Set localOutNodeSet = new HashSet(); + List> prefixList = new ArrayList>(); for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { FlowNode inNode = (FlowNode) iterator.next(); - NTuple inTuple = getLocationTuple(methodInfo, flowGraph, inNode); + NTuple inTuple = flowGraph.getLocationTuple(inNode); if (inTuple.size() > 1) { for (int i = 1; i < inTuple.size(); i++) { @@ -699,6 +739,8 @@ public class LocationInference { } addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inTuple); } + } else { + localInNodeSet.add(inNode); } } @@ -716,6 +758,14 @@ public class LocationInference { } }); + + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + FlowNode reachableNode = (FlowNode) iterator2.next(); + if (reachableNode.getDescTuple().size() == 1) { + localOutNodeSet.add(reachableNode); + } + } + // find out reachable nodes that have the longest common prefix for (int i = 0; i < prefixList.size(); i++) { NTuple curPrefix = prefixList.get(i); @@ -727,9 +777,19 @@ public class LocationInference { if (reachLocTuple.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); @@ -740,39 +800,112 @@ public class LocationInference { SSJavaLattice lattice = getLattice(desc); LocationInfo locInfo = getLocationInfo(desc); - CompositeLocation inferNode = methodInfo.getInferLocation(flowNode); - String nodeSymbol; - if (inferNode != null) { + // CompositeLocation inferLocation = + // methodInfo.getInferLocation(flowNode); + CompositeLocation inferLocation = methodInfo.getInferLocation(localVarDesc); + + String newlyInsertedLocName; + if (inferLocation.getSize() == 1) { + // need to replace the old local location with a new composite + // location + + String oldMethodLocationSymbol = inferLocation.get(0).getLocIdentifier(); - } else { String newLocSymbol = "Loc" + (SSJavaLattice.seed++); - inferNode = new CompositeLocation(); + inferLocation = new CompositeLocation(); for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) { - inferNode.addLocation(curPrefix.get(locIdx)); - } - inferNode.addLocation(new Location(desc, newLocSymbol)); - methodInfo.mapFlowNodeToInferLocation(flowNode, inferNode); - if (flowNode.getDescTuple().size() == 1) { - // local variable case - modifyLocalLatticeAccrodingToNewlyAddedCompositeLocation(methodLattice, methodInfo, - inferNode, flowNode); + inferLocation.addLocation(curPrefix.get(locIdx)); } + Location fieldLoc = new Location(desc, newLocSymbol); + inferLocation.addLocation(fieldLoc); + + + methodInfo.mapDescriptorToLocation(localVarDesc, inferLocation); + methodInfo.removeMaplocalVarToLocSet(localVarDesc); + + String newMethodLocationSymbol = curPrefix.get(0).getLocIdentifier(); + + replaceOldLocWithNewLoc(methodLattice, oldMethodLocationSymbol, newMethodLocationSymbol); + + } else { + + String localLocName = methodInfo.getInferLocation(localVarDesc).get(0).getLocIdentifier(); + return true; + + } - nodeSymbol = inferNode.get(inferNode.getSize() - 1).getLocIdentifier(); + newlyInsertedLocName = inferLocation.get(inferLocation.getSize() - 1).getLocIdentifier(); for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) { NTuple tuple = (NTuple) iterator.next(); + Location loc = tuple.get(idx); - String higher = locInfo.getLocName(loc.getLocIdentifier()); - lattice.addRelationHigherToLower(higher, nodeSymbol); + String higher = locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); + System.out.println("here3"); + + addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName); + } + + + for (Iterator iterator = localInNodeSet.iterator(); iterator.hasNext();) { + FlowNode localNode = (FlowNode) iterator.next(); + Descriptor localInVarDesc = localNode.getDescTuple().get(0); + CompositeLocation inNodeInferLoc = methodInfo.getInferLocation(localInVarDesc); + + if (isCompositeLocation(inNodeInferLoc)) { + // need to make sure that newLocSymbol is lower than the infernode + // location in the field lattice + + if (inNodeInferLoc.getTuple().startsWith(curPrefix) + && inNodeInferLoc.getSize() == (curPrefix.size() + 1)) { + String higher = inNodeInferLoc.get(inNodeInferLoc.getSize() - 1).getLocIdentifier(); + if (!higher.equals(newlyInsertedLocName)) { + + addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName); + } + } else { + throw new Error("Failed to generate a composite location."); + } + + } } for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) { NTuple tuple = (NTuple) iterator.next(); Location loc = tuple.get(idx); - String lower = locInfo.getLocName(loc.getLocIdentifier()); - lattice.addRelationHigherToLower(nodeSymbol, lower); + String lower = locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); + // lattice.addRelationHigherToLower(newlyInsertedLocName, lower); + + addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower); + } + + for (Iterator iterator = localOutNodeSet.iterator(); iterator.hasNext();) { + FlowNode localOutNode = (FlowNode) iterator.next(); + + Descriptor localOutDesc = localOutNode.getDescTuple().get(0); + // String localOutNodeSymbol = + // localOutNode.getDescTuple().get(0).getSymbol(); + CompositeLocation outNodeInferLoc = methodInfo.getInferLocation(localOutDesc); + + // System.out + // .println("localOutNode=" + localOutNode + " outNodeInferLoc=" + + // outNodeInferLoc); + if (isCompositeLocation(outNodeInferLoc)) { + // need to make sure that newLocSymbol is higher than the infernode + // location + + if (outNodeInferLoc.getTuple().startsWith(curPrefix) + && outNodeInferLoc.getSize() == (curPrefix.size() + 1)) { + + String lower = outNodeInferLoc.get(outNodeInferLoc.getSize() - 1).getLocIdentifier(); + + addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower); + + } else { + throw new Error("Failed to generate a composite location."); + } + } } return true; @@ -784,17 +917,97 @@ public class LocationInference { } - private void modifyLocalLatticeAccrodingToNewlyAddedCompositeLocation( - SSJavaLattice methodLattice, MethodLocationInfo methodInfo, - CompositeLocation inferNode, FlowNode flowNode) { + 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(); + + if (desc instanceof VarDescriptor) { + if (!((VarDescriptor) desc).getType().isPrimitive()) { + return true; + } + } else if (desc instanceof FieldDescriptor) { + if (!((FieldDescriptor) desc).getType().isPrimitive()) { + return true; + } + } + + } + return false; + } + + private void addRelationHigherToLower(SSJavaLattice lattice, LocationInfo locInfo, + String higher, String lower) { + + 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) { + // if there is non-primitive element in the cycle, no way to merge cyclic + // elements into the shared location + throw new Error("Failed to merge cyclic value flows into a shared location."); + } + + if (cycleElementSet.size() > 0) { + String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++); + + lattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc); + + for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { + String oldLocSymbol = (String) iterator.next(); + locInfo.mergeMapping(oldLocSymbol, 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) { - Location localLocation = inferNode.get(0); - String newLocName = methodInfo.getLocName(localLocation.getLocIdentifier()); - String oldLocName = methodInfo.getLocName(flowNode.getDescTuple().get(0).getSymbol()); - methodInfo.mapDescSymbolToLocName(oldLocName, newLocName); - methodLattice.substituteLocation(oldLocName, newLocName); + 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) { @@ -824,6 +1037,7 @@ public class LocationInference { private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode, int idx) { + 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 @@ -847,30 +1061,13 @@ public class LocationInference { // add a new binary relation of dstNode < srcNode SSJavaLattice fieldLattice = getFieldLattice(cd); - - String srcOriginalSymbol = srcFieldDesc.getSymbol(); - String dstOriginalSymbol = dstFieldDesc.getSymbol(); - LocationInfo fieldInfo = getFieldLocationInfo(cd); - String srcSymbol = fieldInfo.getLocName(srcOriginalSymbol); - String dstSymbol = fieldInfo.getLocName(dstOriginalSymbol); - Set cycleElementSet = fieldLattice.getPossibleCycleElements(srcSymbol, dstSymbol); + String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier(); + String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier(); - if (cycleElementSet.size() > 0) { - String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++); - fieldLattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc); - - for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { - String locName = (String) iterator.next(); - fieldInfo.mapDescSymbolToLocName(locName, newSharedLoc); - } - - } else if (!fieldLattice.isGreaterThan(srcSymbol, dstSymbol)) { - // if the lattice does not have this relation, add it - fieldLattice.addRelationHigherToLower(srcSymbol, dstSymbol); - } + addRelationHigherToLower(fieldLattice, fieldInfo, srcSymbol, dstSymbol); } @@ -1031,8 +1228,11 @@ public class LocationInference { } else { // check 'for loop' case BlockNode bn = ln.getInitializer(); - analyzeFlowBlockNode(md, bn.getVarTable(), bn, implicitFlowTupleSet); bn.getVarTable().setParent(nametable); + for (int i = 0; i < bn.size(); i++) { + BlockStatementNode bsn = bn.get(i); + analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet); + } NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null, @@ -1553,6 +1753,9 @@ public class LocationInference { private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an, NTuple base, NodeTupleSet implicitFlowTupleSet) { + // System.out.println("#an=" + an.printNode(0) + " an src=" + + // an.getSrc().printNode(0) + " dst=" + // + an.getDest().printNode(0)); NodeTupleSet nodeSetRHS = new NodeTupleSet(); NodeTupleSet nodeSetLHS = new NodeTupleSet(); @@ -1562,7 +1765,6 @@ public class LocationInference { .getBaseOp().getOp() != Operation.POSTDEC)) { postinc = false; } - // if LHS is array access node, need to capture value flows between an array // and its index value analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet, diff --git a/Robust/src/Analysis/SSJava/LocationInfo.java b/Robust/src/Analysis/SSJava/LocationInfo.java index 8709ad30..0ec82526 100644 --- a/Robust/src/Analysis/SSJava/LocationInfo.java +++ b/Robust/src/Analysis/SSJava/LocationInfo.java @@ -2,6 +2,7 @@ package Analysis.SSJava; import java.util.HashMap; import java.util.HashSet; +import java.util.Iterator; import java.util.Map; import java.util.Set; @@ -11,57 +12,118 @@ import IR.MethodDescriptor; public class LocationInfo { - Map> mapLocNameToDescSet; - Map mapDescSymbolToLocName; + // Map mapDescToLocSymbol; + Map> mapLocSymbolToDescSet; + Map mapDescToInferCompositeLocation; MethodDescriptor md; ClassDescriptor cd; public LocationInfo() { - mapDescSymbolToLocName = new HashMap(); - mapLocNameToDescSet = new HashMap>(); mapDescToInferCompositeLocation = new HashMap(); + mapLocSymbolToDescSet = new HashMap>(); } public LocationInfo(ClassDescriptor cd) { + this(); this.cd = cd; - this.mapDescSymbolToLocName = new HashMap(); } - public void mapDescriptorToCompositeLocation(Descriptor desc, CompositeLocation inferLoc) { - mapDescToInferCompositeLocation.put(desc, inferLoc); + public Map> getMapLocSymbolToDescSet() { + return mapLocSymbolToDescSet; } - public void mapDescSymbolToLocName(String descSymbol, String locName) { - mapDescSymbolToLocName.put(descSymbol, locName); + public Map getMapDescToInferLocation() { + return mapDescToInferCompositeLocation; } - public String getLocName(String descSymbol) { - if (!mapDescSymbolToLocName.containsKey(descSymbol)) { - mapDescSymbolToLocName.put(descSymbol, descSymbol); - } - return mapDescSymbolToLocName.get(descSymbol); + public void mapDescriptorToLocation(Descriptor desc, CompositeLocation inferLoc) { + mapDescToInferCompositeLocation.put(desc, inferLoc); } - public void addMappingOfLocNameToDescriptor(String locName, Descriptor desc) { - - // System.out.println("### MAP LocName=" + locName + " to " + desc); + // public void mapDescSymbolToLocName(String descSymbol, String locName) { + // mapDescSymbolToLocName.put(descSymbol, locName); + // } + + public CompositeLocation getInferLocation(Descriptor desc) { + if (!mapDescToInferCompositeLocation.containsKey(desc)) { + CompositeLocation newInferLoc = new CompositeLocation(); + Location loc; + if (md != null) { + // method lattice + loc = new Location(md, desc.getSymbol()); + } else { + loc = new Location(cd, desc.getSymbol()); + } + newInferLoc.addLocation(loc); + mapDescToInferCompositeLocation.put(desc, newInferLoc); + addMapLocSymbolToDescSet(desc.getSymbol(), desc); + } + return mapDescToInferCompositeLocation.get(desc); + } - if (!mapLocNameToDescSet.containsKey(locName)) { - mapLocNameToDescSet.put(locName, new HashSet()); + public void addMapLocSymbolToDescSet(String locSymbol, Descriptor desc) { + System.out.println("mapLocSymbolToDescSet=" + mapLocSymbolToDescSet); + if (!mapLocSymbolToDescSet.containsKey(locSymbol)) { + mapLocSymbolToDescSet.put(locSymbol, new HashSet()); } + mapLocSymbolToDescSet.get(locSymbol).add(desc); + } - mapLocNameToDescSet.get(locName).add(desc); + public Location getFieldInferLocation(Descriptor desc) { + return getInferLocation(desc).get(0); + } + public Set getDescSet(String locSymbol) { + if (!mapLocSymbolToDescSet.containsKey(locSymbol)) { + mapLocSymbolToDescSet.put(locSymbol, new HashSet()); + } + return mapLocSymbolToDescSet.get(locSymbol); } - public Set getFlowNodeSet(String locName) { + public void mergeMapping(String oldLocSymbol, String newSharedLoc) { + Set descSet = getDescSet(oldLocSymbol); + getDescSet(newSharedLoc).addAll(descSet); + mapLocSymbolToDescSet.remove(oldLocSymbol); + + Set keySet = mapDescToInferCompositeLocation.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor key = (Descriptor) iterator.next(); + CompositeLocation inferLoc = getInferLocation(key); + + CompositeLocation newInferLoc = new CompositeLocation(); + if (inferLoc.getSize() > 1) { + // local variable has a composite location [refLoc.inferedLoc] + + Location oldLoc = inferLoc.get(inferLoc.getSize() - 1); + // oldLoc corresponds to infered loc. + + if (oldLoc.getLocIdentifier().equals(oldLocSymbol)) { + for (int i = 0; i < inferLoc.getSize() - 1; i++) { + Location loc = inferLoc.get(i); + newInferLoc.addLocation(loc); + } + Location newLoc = new Location(oldLoc.getDescriptor(), newSharedLoc); + newInferLoc.addLocation(newLoc); + mapDescriptorToLocation(key, newInferLoc); + } + // else { + // return; + // } + } else { + // local var has a local location + Location oldLoc = inferLoc.get(0); + if (oldLoc.getLocIdentifier().equals(oldLocSymbol)) { + Location newLoc = new Location(oldLoc.getDescriptor(), newSharedLoc); + newInferLoc.addLocation(newLoc); + mapDescriptorToLocation(key, newInferLoc); + } + // else { + // return; + // } + } - if (!mapLocNameToDescSet.containsKey(locName)) { - mapLocNameToDescSet.put(locName, new HashSet()); } - - return mapLocNameToDescSet.get(locName); } } diff --git a/Robust/src/Analysis/SSJava/MethodLocationInfo.java b/Robust/src/Analysis/SSJava/MethodLocationInfo.java index 5a150aff..986d4550 100644 --- a/Robust/src/Analysis/SSJava/MethodLocationInfo.java +++ b/Robust/src/Analysis/SSJava/MethodLocationInfo.java @@ -10,32 +10,27 @@ import IR.MethodDescriptor; public class MethodLocationInfo extends LocationInfo { - MethodDescriptor md; - String returnLocName; String thisLocName; String PCLocName; Map mapParamIdxToLocName; Set paramLocNameSet; - Map mapFlowNodeToLocation; public MethodLocationInfo(MethodDescriptor md) { this.md = md; this.mapParamIdxToLocName = new HashMap(); this.paramLocNameSet = new HashSet(); this.PCLocName = SSJavaAnalysis.TOP; - this.mapFlowNodeToLocation = new HashMap(); - } - - public void mapFlowNodeToInferLocation(FlowNode node, CompositeLocation location) { - mapFlowNodeToLocation.put(node, location); - } - - public CompositeLocation getInferLocation(FlowNode node) { - return mapFlowNodeToLocation.get(node); } + /* + * public void mapFlowNodeToInferLocation(FlowNode node, CompositeLocation + * location) { mapFlowNodeToLocation.put(node, location); } + * + * public CompositeLocation getInferLocation(FlowNode node) { return + * mapFlowNodeToLocation.get(node); } + */ public String getReturnLocName() { return returnLocName; } @@ -62,7 +57,7 @@ public class MethodLocationInfo extends LocationInfo { public void addParameter(String name, Descriptor desc, int idx) { mapParamIdxToLocName.put(new Integer(idx), name); - addMappingOfLocNameToDescriptor(name, desc); + // addMappingOfLocNameToDescriptor(name, desc); } public Set getParameterLocNameSet() { @@ -83,4 +78,9 @@ public class MethodLocationInfo extends LocationInfo { return paramSet; } + public void removeMaplocalVarToLocSet(Descriptor localVarDesc) { + String localVarLocSymbol = localVarDesc.getSymbol(); + getDescSet(localVarLocSymbol).remove(localVarDesc); + } + } diff --git a/Robust/src/Analysis/SSJava/SSJavaLattice.java b/Robust/src/Analysis/SSJava/SSJavaLattice.java index d30aa399..9fd25957 100644 --- a/Robust/src/Analysis/SSJava/SSJavaLattice.java +++ b/Robust/src/Analysis/SSJava/SSJavaLattice.java @@ -135,10 +135,24 @@ public class SSJavaLattice extends Lattice { Set set = getTable().get(newLoc); set.addAll(newConnectedSet); + // clean up lattice + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + T keyElement = (T) iterator.next(); + get(keyElement).removeAll(cycleSet); + } + + for (Iterator iterator = cycleSet.iterator(); iterator.hasNext();) { + T cycleElement = (T) iterator.next(); + getTable().remove(cycleElement); + } + } public void substituteLocation(T oldLoc, T newLoc) { // the new location is going to take all relations of the old location + if (!getKeySet().contains(newLoc)) { + put(newLoc); + } // consider the set of location s.t. LOC is greater than oldLoc Set keySet = getKeySet(); @@ -172,6 +186,71 @@ public class SSJavaLattice extends Lattice { } } + getTable().remove(oldLoc); + + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + T key = (T) iterator.next(); + getTable().get(key).remove(oldLoc); + } + } + public void removeRedundantEdges() { + boolean isUpdated; + do { + isUpdated = recurRemoveRedundant(); + } while (isUpdated); + } + + public boolean recurRemoveRedundant() { + + Set keySet = getKeySet(); + Set visited = new HashSet(); + + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + T key = (T) iterator.next(); + Set connectedSet = getTable().get(key); + if (connectedSet != null) { + Set toberemovedSet = new HashSet(); + for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) { + T dst = (T) iterator2.next(); + Set otherNeighborSet = new HashSet(); + otherNeighborSet.addAll(connectedSet); + otherNeighborSet.remove(dst); + for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) { + T neighbor = (T) iterator3.next(); + if (isReachable(neighbor, visited, dst)) { + toberemovedSet.add(dst); + } + } + } + if (toberemovedSet.size() > 0) { + connectedSet.removeAll(toberemovedSet); + return true; + } + } + } + + return false; + + } + + private boolean isReachable(T neighbor, Set visited, T dst) { + Set connectedSet = getTable().get(neighbor); + if (connectedSet != null) { + for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) { + T n = iterator.next(); + if (n.equals(dst)) { + return true; + } + if (!visited.contains(n)) { + visited.add(n); + if (isReachable(n, visited, dst)) { + return true; + } + } + } + } + return false; + } } diff --git a/Robust/src/Util/Lattice.java b/Robust/src/Util/Lattice.java index 76aa706c..7c744f62 100644 --- a/Robust/src/Util/Lattice.java +++ b/Robust/src/Util/Lattice.java @@ -71,7 +71,7 @@ public class Lattice { size++; s.add(value); - if (!table.containsKey(value)) { + if ((!table.containsKey(value)) && (!value.equals(bottom))) { Set lowerNeighbor = new HashSet(); lowerNeighbor.add(bottom); table.put(value, lowerNeighbor); @@ -155,6 +155,13 @@ public class Lattice { public boolean isGreaterThan(T a, T b) { + Set visited = new HashSet(); + return isGreaterThan(a, b, visited); + + } + + public boolean isGreaterThan(T a, T b, Set visited) { + if (a.equals(b)) { return false; } @@ -185,7 +192,10 @@ public class Lattice { boolean reachable = false; for (Iterator iterator = neighborSet.iterator(); iterator.hasNext();) { T neighbor = iterator.next(); - reachable = reachable || isGreaterThan(neighbor, b); + if (!visited.contains(neighbor)) { + visited.add(neighbor); + reachable = reachable || isGreaterThan(neighbor, b, visited); + } } return reachable; } -- 2.34.1