X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FPointer%2FPointer.java;h=184cf6511cd3c9b93228fd1f51175512e4c70b70;hp=f1fddad9884416a17c175dbae0befdf46445e5e3;hb=2c9fc049afee82726ae47ec7ea2630cfe1623f21;hpb=6c22cffed94206645d16712e7a5b615d8a94f7e9 diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index f1fddad9..184cf651 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -20,7 +20,7 @@ import Analysis.Disjoint.BuildStateMachines; import java.io.*; -public class Pointer implements HeapAnalysis{ +public class Pointer implements HeapAnalysis { HashMap blockMap; HashMap bbgraphMap; HashMap graphMap; @@ -76,23 +76,23 @@ public class Pointer implements HeapAnalysis{ public BasicBlock getBBlock(FlatMethod fm) { if (!blockMap.containsKey(fm)) { blockMap.put(fm, BasicBlock.getBBlock(fm)); - Hashtable> livemap=Liveness.computeLiveTemps(fm); - for(BBlock bblock:blockMap.get(fm).getBlocks()) { - FlatNode fn=bblock.nodes.get(0); - if (fn==fm) { - HashSet fmset=new HashSet(); - fmset.addAll((List)Arrays.asList(fm.writesTemps())); - bblivetemps.put(bblock, fmset); - } else { - Set livetemps=livemap.get(fn); - bblivetemps.put(bblock, livetemps); - livetemps.add(returntmp); - } + Hashtable> livemap=Liveness.computeLiveTemps(fm,-1); + for(BBlock bblock : blockMap.get(fm).getBlocks()) { + FlatNode fn=bblock.nodes.get(0); + if (fn==fm) { + HashSet fmset=new HashSet(); + fmset.addAll((List)Arrays.asList(fm.writesTemps())); + bblivetemps.put(bblock, fmset); + } else { + Set livetemps=livemap.get(fn); + bblivetemps.put(bblock, livetemps); + livetemps.add(returntmp); + } } } return blockMap.get(fm); } - + Delta buildInitialContext() { MethodDescriptor md=typeUtil.getMain(); FlatMethod fm=state.getMethodFlat(md); @@ -117,7 +117,7 @@ public class Pointer implements HeapAnalysis{ public void doAnalysis() { toprocess.add(buildInitialContext()); - nextdelta: +nextdelta: while(!toprocess.isEmpty()) { Delta delta=toprocess.remove(); PPoint ppoint=delta.getBlock(); @@ -126,69 +126,70 @@ public class Pointer implements HeapAnalysis{ int startindex=0; if (ppoint.getIndex()==-1) { - //Build base graph for entrance to this basic block - //System.out.println("Processing "+bblock.nodes.get(0).toString().replace(' ','_')); - //delta.print(); - delta=applyInitDelta(delta, bblock); - //System.out.println("Generating:"); - //delta.print(); + //Build base graph for entrance to this basic block + //System.out.println("Processing "+bblock.nodes.get(0).toString().replace(' ','_')); + //delta.print(); + delta=applyInitDelta(delta, bblock); + //System.out.println("Generating:"); + //delta.print(); } else { - //System.out.println("Processing Call "+bblock.nodes.get(ppoint.getIndex()).toString().replace(' ','_')); - //delta.print(); + //System.out.println("Processing Call "+bblock.nodes.get(ppoint.getIndex()).toString().replace(' ','_')); + //delta.print(); - startindex=ppoint.getIndex()+1; - delta=applyCallDelta(delta, bblock); - //System.out.println("Generating:"); - //delta.print(); + startindex=ppoint.getIndex()+1; + delta=applyCallDelta(delta, bblock); + //System.out.println("Generating:"); + //delta.print(); } Graph graph=bbgraphMap.get(bblock); Graph nodeGraph=null; - boolean init=delta.getInit(); - if (!init&&delta.isEmpty()) - continue nextdelta; - + int lasti=-1; //Compute delta at exit of each node - for(int i=startindex; i=i;lasti--) { - FlatNode scurrNode=nodes.get(lasti); - if (isNEEDED(scurrNode)||isINACC(scurrNode)) { - break; - } - } - } - if (i==lasti) { - mustProcess.add(currNode); - graphMap.put(currNode, new Graph(graph)); - fallthru=false; - } - } - if (fallthru) { - if (i==0) { - //base graph works for us - graphMap.put(currNode, new Graph(graph)); - } else { - //just use previous graph - graphMap.put(currNode, graphMap.get(nodes.get(i-1))); - } - } - } - } - - nodeGraph=graphMap.get(currNode); - delta=processNode(bblock, i, currNode, delta, nodeGraph); - //System.out.println("Processing "+currNode+" and generating delta:"); - //delta.print(); + for(int i=startindex; i=i; lasti--) { + FlatNode scurrNode=nodes.get(lasti); + if (isNEEDED(scurrNode)||isINACC(scurrNode)) { + break; + } + } + } + if (i==lasti) { + mustProcess.add(currNode); + graphMap.put(currNode, new Graph(graph)); + fallthru=false; + } + } + if (fallthru) { + if (i==0) { + //base graph works for us + graphMap.put(currNode, new Graph(graph)); + } else { + //just use previous graph + graphMap.put(currNode, graphMap.get(nodes.get(i-1))); + } + } + } + } + + nodeGraph=graphMap.get(currNode); + delta=processNode(bblock, i, currNode, delta, nodeGraph); + //System.out.println("Processing "+currNode+" and generating delta:"); + //delta.print(); } generateFinalDelta(bblock, delta, nodeGraph); } @@ -196,29 +197,33 @@ public class Pointer implements HeapAnalysis{ //DEBUG if (false) { int debugindex=0; - for(Map.Entry e:bbgraphMap.entrySet()) { - Graph g=e.getValue(); - plotGraph(g,"BB"+e.getKey().nodes.get(0).toString().replace(' ','_')); - debugindex++; + for(Map.Entry e : bbgraphMap.entrySet()) { + Graph g=e.getValue(); + plotGraph(g,"BB"+e.getKey().nodes.get(0).toString().replace(' ','_')); + debugindex++; } - - for(FlatMethod fm:blockMap.keySet()) { - System.out.println(fm.printMethod()); + + for(FlatMethod fm : blockMap.keySet()) { + System.out.println(fm.printMethod()); + } + for(Map.Entry e : graphMap.entrySet()) { + FlatNode fn=e.getKey(); + Graph g=e.getValue(); + plotGraph(g,"FN"+fn.toString()+debugindex); + debugindex++; } - for(Map.Entry e:graphMap.entrySet()) { - FlatNode fn=e.getKey(); - Graph g=e.getValue(); - plotGraph(g,"FN"+fn.toString()+debugindex); - debugindex++; - } } State.logEvent("Done With Pointer Analysis"); - if (OoOJava) { effectsAnalysis.buildStateMachines.writeStateMachines(); State.logEvent("Done Writing State Machines"); + + if( state.OOODEBUG ) { + effectsAnalysis.writeEffects("effects.txt"); + State.logEvent("Done Writing Effects"); + } } } @@ -231,7 +236,7 @@ public class Pointer implements HeapAnalysis{ ex.printStackTrace(); } } - + /* This function builds the last delta for a basic block. It * handles the case for the first time the basic block is @@ -242,42 +247,42 @@ public class Pointer implements HeapAnalysis{ HashSet tmpSet=new HashSet(); tmpSet.addAll(graph.varMap.keySet()); tmpSet.addAll(graph.parent.varMap.keySet()); - + //Next build the temp map part of the delta - for(TempDescriptor tmp:tmpSet) { + for(TempDescriptor tmp : tmpSet) { MySet edgeSet=new MySet(); /* Get target set */ if (graph.varMap.containsKey(tmp)) - edgeSet.addAll(graph.varMap.get(tmp)); + edgeSet.addAll(graph.varMap.get(tmp)); else - edgeSet.addAll(graph.parent.varMap.get(tmp)); + edgeSet.addAll(graph.parent.varMap.get(tmp)); newDelta.varedgeadd.put(tmp, edgeSet); } - + //Next compute the set of src allocnodes HashSet nodeSet=new HashSet(); nodeSet.addAll(graph.nodeMap.keySet()); nodeSet.addAll(graph.parent.nodeMap.keySet()); - - for(AllocNode node:nodeSet) { + + for(AllocNode node : nodeSet) { MySet edgeSet=new MySet(); /* Get edge set */ if (graph.nodeMap.containsKey(node)) - edgeSet.addAll(graph.nodeMap.get(node)); + edgeSet.addAll(graph.nodeMap.get(node)); else - edgeSet.addAll(graph.parent.nodeMap.get(node)); + edgeSet.addAll(graph.parent.nodeMap.get(node)); newDelta.heapedgeadd.put(node, edgeSet); - + /* Compute ages */ if (graph.oldNodes.containsKey(node)) { - if (graph.oldNodes.get(node).booleanValue()) - newDelta.addOldNodes.put(node, Boolean.TRUE); + if (graph.oldNodes.get(node).booleanValue()) + newDelta.addOldNodes.put(node, Boolean.TRUE); } else if (graph.parent.oldNodes.containsKey(node)) { - //parent graphs only contain true...no need to check - newDelta.addOldNodes.put(node, Boolean.TRUE); + //parent graphs only contain true...no need to check + newDelta.addOldNodes.put(node, Boolean.TRUE); } } - + newDelta.addNodeAges.addAll(graph.nodeAges); newDelta.addNodeAges.addAll(graph.parent.nodeAges); } @@ -294,17 +299,17 @@ public class Pointer implements HeapAnalysis{ HashSet tmpSet=new HashSet(); tmpSet.addAll(delta.basevaredge.keySet()); tmpSet.addAll(delta.varedgeadd.keySet()); - for(TempDescriptor tmp:tmpSet) { - /* Start with the new incoming edges */ - MySet newbaseedge=delta.basevaredge.get(tmp); - /* Remove the remove set */ - if (newbaseedge==null) - newbaseedge=new MySet(); - newbaseedge.removeAll(delta.varedgeremove.get(tmp)); - /* Add in the new set*/ - newbaseedge.addAll(delta.varedgeadd.get(tmp)); - /* Store the results */ - newDelta.varedgeadd.put(tmp, newbaseedge); + for(TempDescriptor tmp : tmpSet) { + /* Start with the new incoming edges */ + MySet newbaseedge=delta.basevaredge.get(tmp); + /* Remove the remove set */ + if (newbaseedge==null) + newbaseedge=new MySet(); + newbaseedge.removeAll(delta.varedgeremove.get(tmp)); + /* Add in the new set*/ + newbaseedge.addAll(delta.varedgeadd.get(tmp)); + /* Store the results */ + newDelta.varedgeadd.put(tmp, newbaseedge); } delta.basevaredge.clear(); @@ -313,26 +318,26 @@ public class Pointer implements HeapAnalysis{ nodeSet.addAll(delta.baseheapedge.keySet()); nodeSet.addAll(delta.heapedgeadd.keySet()); nodeSet.addAll(delta.heapedgeremove.keySet()); - for(AllocNode node:nodeSet) { - /* Start with the new incoming edges */ - MySet newheapedge=new MySet(delta.baseheapedge.get(node)); - /* Remove the remove set */ - MySet removeset=delta.heapedgeremove.get(node); + for(AllocNode node : nodeSet) { + /* Start with the new incoming edges */ + MySet newheapedge=new MySet(delta.baseheapedge.get(node)); + /* Remove the remove set */ + MySet removeset=delta.heapedgeremove.get(node); - if (removeset!=null) - newheapedge.removeAll(removeset); + if (removeset!=null) + newheapedge.removeAll(removeset); - /* Add in the add set */ - MySet settoadd=delta.heapedgeadd.get(node); - if (settoadd!=null) - newheapedge.addAll(settoadd); - newDelta.heapedgeadd.put(node, newheapedge); + /* Add in the add set */ + MySet settoadd=delta.heapedgeadd.get(node); + if (settoadd!=null) + newheapedge.addAll(settoadd); + newDelta.heapedgeadd.put(node, newheapedge); - /* Remove the newly created edges..no need to propagate a diff for those */ - if (removeset!=null) { - removeset.removeAll(delta.baseheapedge.get(node)); - newDelta.heapedgeremove.put(node, removeset); - } + /* Remove the newly created edges..no need to propagate a diff for those */ + if (removeset!=null) { + removeset.removeAll(delta.baseheapedge.get(node)); + newDelta.heapedgeremove.put(node, removeset); + } } /* Compute new ages */ @@ -343,52 +348,59 @@ public class Pointer implements HeapAnalysis{ /* Compute whether old nodes survive */ oldNodes.addAll(delta.baseOldNodes.keySet()); oldNodes.addAll(delta.addOldNodes.keySet()); - for(AllocNode node:oldNodes) { - if (delta.addOldNodes.containsKey(node)) { - if (delta.addOldNodes.get(node).booleanValue()) { - newDelta.addOldNodes.put(node, Boolean.TRUE); - } - } else { - if (delta.baseOldNodes.get(node).booleanValue()) { - newDelta.addOldNodes.put(node, Boolean.TRUE); - } - } + for(AllocNode node : oldNodes) { + if (delta.addOldNodes.containsKey(node)) { + if (delta.addOldNodes.get(node).booleanValue()) { + newDelta.addOldNodes.put(node, Boolean.TRUE); + } + } else { + if (delta.baseOldNodes.get(node).booleanValue()) { + newDelta.addOldNodes.put(node, Boolean.TRUE); + } + } } } + if (returnMap.containsKey(bblock)) { + //clear everything but our return temp! + MySet edges=newDelta.varedgeadd.get(returntmp); + newDelta.varedgeadd.clear(); + newDelta.varedgeadd.put(returntmp, edges); + } + /* Now we need to propagate newdelta */ if (!newDelta.heapedgeadd.isEmpty()||!newDelta.heapedgeremove.isEmpty()||!newDelta.varedgeadd.isEmpty()||!newDelta.addNodeAges.isEmpty()||!newDelta.addOldNodes.isEmpty()) { /* We have a delta to propagate */ if (returnMap.containsKey(bblock)) { - //exit of call block - boolean first=true; - - for(PPoint caller:returnMap.get(bblock)) { - //System.out.println("Sending Return BBlock to "+caller.getBBlock().nodes.get(caller.getIndex()).toString().replace(' ','_')); - //newDelta.print(); - if (first) { - newDelta.setBlock(caller); - toprocess.add(newDelta); - first=false; - } else { - Delta d=newDelta.diffBlock(caller); - toprocess.add(d); - } - } + //exit of call block + boolean first=true; + + for(PPoint caller : returnMap.get(bblock)) { + //System.out.println("Sending Return BBlock to "+caller.getBBlock().nodes.get(caller.getIndex()).toString().replace(' ','_')); + //newDelta.print(); + if (first) { + newDelta.setBlock(caller); + toprocess.add(newDelta); + first=false; + } else { + Delta d=newDelta.diffBlock(caller); + toprocess.add(d); + } + } } else { - //normal block - Vector blockvector=bblock.next(); - for(int i=0;i blockvector=bblock.next(); + for(int i=0; i edges=GraphManip.getEdges(graph, delta, tmp); - for(Edge e:edges) { - Edge newe=e.addTaint(taint); - delta.addVarEdge(newe); - } + for (TempDescriptor tmp : sese.getInVarSet()) { + Taint taint=Taint.factory(sese, null, tmp, AllocFactory.dummySite, null, ReachGraph.predsEmpty); + MySet edges=GraphManip.getEdges(graph, delta, tmp); + for(Edge e : edges) { + Edge newe=e.addTaint(taint); + delta.addVarEdge(newe); + } } } else { removeDiffTaints(null, delta); - for (TempDescriptor tmp:sese.getInVarSet()) { - Taint taint=Taint.factory(sese, null, tmp, AllocFactory.dummySite, null, ReachGraph.predsEmpty); - MySet edges=GraphManip.getDiffEdges(delta, tmp); - for(Edge e:edges) { - Edge newe=e.addTaint(taint); - delta.addVarEdge(newe); - } + for (TempDescriptor tmp : sese.getInVarSet()) { + Taint taint=Taint.factory(sese, null, tmp, AllocFactory.dummySite, null, ReachGraph.predsEmpty); + MySet edges=GraphManip.getDiffEdges(delta, tmp); + for(Edge e : edges) { + Edge newe=e.addTaint(taint); + delta.addVarEdge(newe); + } } } @@ -480,7 +516,7 @@ public class Pointer implements HeapAnalysis{ applyDiffs(graph, delta); return delta; } - + private boolean isRecursive(FlatSESEEnterNode sese) { MethodDescriptor md=sese.getmdEnclosing(); boolean isrecursive=callGraph.getCalleeSet(md).contains(md); @@ -500,22 +536,22 @@ public class Pointer implements HeapAnalysis{ applyDiffs(graph, delta); return delta; } - + void removeDiffTaints(FlatSESEEnterNode sese, Delta delta) { //Start with variable edges { MySet edgestoadd=new MySet(); MySet edgestoremove=new MySet(); - + //Process base diff edges - processEdgeMap(sese, delta.basevaredge, null, delta.varedgeremove, edgestoremove, edgestoadd); + processEdgeMap(sese, delta.basevaredge, null, delta.varedgeremove, edgestoremove, edgestoadd); //Process delta edges - processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd); - for(Edge e:edgestoremove) { - delta.removeVarEdge(e); + processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd); + for(Edge e : edgestoremove) { + delta.removeVarEdge(e); } - for(Edge e:edgestoadd) { - delta.addVarEdge(e); + for(Edge e : edgestoadd) { + delta.addVarEdge(e); } } @@ -525,14 +561,14 @@ public class Pointer implements HeapAnalysis{ MySet edgestoremove=new MySet(); //Process base diff edges - processEdgeMap(sese, delta.baseheapedge, null, delta.heapedgeremove, edgestoremove, edgestoadd); + processEdgeMap(sese, delta.baseheapedge, null, delta.heapedgeremove, edgestoremove, edgestoadd); //Process delta edges - processEdgeMap(sese, delta.heapedgeadd, null, null, edgestoremove, edgestoadd); - for(Edge e:edgestoremove) { - delta.removeHeapEdge(e); + processEdgeMap(sese, delta.heapedgeadd, null, null, edgestoremove, edgestoadd); + for(Edge e : edgestoremove) { + delta.removeHeapEdge(e); } - for(Edge e:edgestoadd) { - delta.addHeapEdge(e); + for(Edge e : edgestoadd) { + delta.addHeapEdge(e); } } } @@ -542,18 +578,18 @@ public class Pointer implements HeapAnalysis{ { MySet edgestoadd=new MySet(); MySet edgestoremove=new MySet(); - + //Process parent edges processEdgeMap(sese, graph.parent.varMap, graph.varMap, delta.varedgeremove, edgestoremove, edgestoadd); //Process graph edges - processEdgeMap(sese, graph.varMap, null, delta.varedgeremove, edgestoremove, edgestoadd); + processEdgeMap(sese, graph.varMap, null, delta.varedgeremove, edgestoremove, edgestoadd); //Process delta edges - processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd); - for(Edge e:edgestoremove) { - delta.removeVarEdge(e); + processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd); + for(Edge e : edgestoremove) { + delta.removeVarEdge(e); } - for(Edge e:edgestoadd) { - delta.addVarEdge(e); + for(Edge e : edgestoadd) { + delta.addVarEdge(e); } } @@ -565,14 +601,14 @@ public class Pointer implements HeapAnalysis{ //Process parent edges processEdgeMap(sese, graph.parent.nodeMap, graph.nodeMap, delta.heapedgeremove, edgestoremove, edgestoadd); //Process graph edges - processEdgeMap(sese, graph.nodeMap, null, delta.heapedgeremove, edgestoremove, edgestoadd); + processEdgeMap(sese, graph.nodeMap, null, delta.heapedgeremove, edgestoremove, edgestoadd); //Process delta edges - processEdgeMap(sese, delta.heapedgeadd, null, null, edgestoremove, edgestoadd); - for(Edge e:edgestoremove) { - delta.removeHeapEdge(e); + processEdgeMap(sese, delta.heapedgeadd, null, null, edgestoremove, edgestoadd); + for(Edge e : edgestoremove) { + delta.removeHeapEdge(e); } - for(Edge e:edgestoadd) { - delta.addHeapEdge(e); + for(Edge e : edgestoadd) { + delta.addHeapEdge(e); } } } @@ -581,22 +617,22 @@ public class Pointer implements HeapAnalysis{ for(Map.Entry> entry:edgemap.entrySet()) { //If the parent map exists and overrides this entry, skip it if (childmap!=null&&childmap.containsKey(entry.getKey())) - continue; + continue; for(Edge e:entry.getValue()) { - //check whether this edge has been removed - if (removemap!=null&&removemap.containsKey(entry.getKey())&& - removemap.get(entry.getKey()).contains(e)) - continue; - //have real edge - TaintSet ts=e.getTaints(); - TaintSet newts=null; - //update non-null taint set - if (ts!=null) - newts=Canonical.removeInContextTaintsNP(ts, sese); - if (newts!=null) { - edgestoremove.add(e); - edgestoadd.add(e.changeTaintSet(newts)); - } + //check whether this edge has been removed + if (removemap!=null&&removemap.containsKey(entry.getKey())&& + removemap.get(entry.getKey()).contains(e)) + continue; + //have real edge + TaintSet ts=e.getTaints(); + TaintSet newts=null; + //update non-null taint set + if (ts!=null) + newts=Canonical.removeInContextTaintsNP(ts, sese); + if (newts!=null&&newts!=ts) { + edgestoremove.add(e); + edgestoadd.add(e.changeTaintSet(newts)); + } } } } @@ -608,21 +644,21 @@ public class Pointer implements HeapAnalysis{ //Handle the this temp if (tmpthis!=null) { MySet edges=(oldnodeset!=null)?GraphManip.getDiffEdges(delta, tmpthis):GraphManip.getEdges(graph, delta, tmpthis); - newDelta.varedgeadd.put(tmpthis, (MySet) edges.clone()); + newDelta.varedgeadd.put(tmpthis, (MySet)edges.clone()); edgeset.addAll(edges); for(Edge e:edges) { - AllocNode dstnode=e.dst; - if (!nodeset.contains(dstnode)&&(oldnodeset==null||!oldnodeset.contains(dstnode))) { - TypeDescriptor type=dstnode.getType(); - if (!type.isArray()) { - targetSet.add(type.getClassDesc()); - } else { - //arrays don't have code - targetSet.add(typeUtil.getClass(TypeUtil.ObjectClass)); - } - nodeset.add(dstnode); - tovisit.add(dstnode); - } + AllocNode dstnode=e.dst; + if (!nodeset.contains(dstnode)&&(oldnodeset==null||!oldnodeset.contains(dstnode))) { + TypeDescriptor type=dstnode.getType(); + if (!type.isArray()) { + targetSet.add(type.getClassDesc()); + } else { + //arrays don't have code + targetSet.add(typeUtil.getClass(TypeUtil.ObjectClass)); + } + nodeset.add(dstnode); + tovisit.add(dstnode); + } } } } @@ -631,16 +667,16 @@ public class Pointer implements HeapAnalysis{ void processParams(Graph graph, Delta delta, Delta newDelta, HashSet nodeset, Stack tovisit, MySet edgeset, FlatCall fcall, boolean diff) { //Go through each temp - for(int i=0;i edges=diff?GraphManip.getDiffEdges(delta, tmp):GraphManip.getEdges(graph, delta, tmp); - newDelta.varedgeadd.put(tmp, (MySet) edges.clone()); + newDelta.varedgeadd.put(tmp, (MySet)edges.clone()); edgeset.addAll(edges); for(Edge e:edges) { - if (!nodeset.contains(e.dst)) { - nodeset.add(e.dst); - tovisit.add(e.dst); - } + if (!nodeset.contains(e.dst)) { + nodeset.add(e.dst); + tovisit.add(e.dst); + } } } } @@ -648,20 +684,20 @@ public class Pointer implements HeapAnalysis{ /* This function computes the reachable nodes for a callee. */ void computeReachableNodes(Graph graph, Delta delta, Delta newDelta, HashSet nodeset, Stack tovisit, MySet edgeset, HashSet oldnodeset) { - while(!tovisit.isEmpty()) { - AllocNode node=tovisit.pop(); - MySet edges=GraphManip.getEdges(graph, delta, node); - if (!edges.isEmpty()) { - newDelta.heapedgeadd.put(node, Edge.makeOld(edges)); - edgeset.addAll(edges); - for(Edge e:edges) { - if (!nodeset.contains(e.dst)&&(oldnodeset==null||!oldnodeset.contains(e.dst))) { - nodeset.add(e.dst); - tovisit.add(e.dst); - } - } - } + while(!tovisit.isEmpty()) { + AllocNode node=tovisit.pop(); + MySet edges=GraphManip.getEdges(graph, delta, node); + if (!edges.isEmpty()) { + newDelta.heapedgeadd.put(node, Edge.makeOld(edges)); + edgeset.addAll(edges); + for(Edge e : edges) { + if (!nodeset.contains(e.dst)&&(oldnodeset==null||!oldnodeset.contains(e.dst))) { + nodeset.add(e.dst); + tovisit.add(e.dst); + } + } } + } } HashSet computeTargets(FlatCall fcall, Delta newDelta) { @@ -672,12 +708,12 @@ public class Pointer implements HeapAnalysis{ targets.add(md); } else { //Compute Edges - for(Edge e:newDelta.varedgeadd.get(tmpthis)) { - AllocNode node=e.dst; - ClassDescriptor cd=node.getType().getClassDesc(); - //Figure out exact method called and add to set - MethodDescriptor calledmd=cd.getCalledMethod(md); - targets.add(calledmd); + for(Edge e : newDelta.varedgeadd.get(tmpthis)) { + AllocNode node=e.dst; + ClassDescriptor cd=node.getType().getClassDesc(); + //Figure out exact method called and add to set + MethodDescriptor calledmd=cd.getCalledMethod(md); + targets.add(calledmd); } } return targets; @@ -687,81 +723,81 @@ public class Pointer implements HeapAnalysis{ Delta basedelta=null; TempDescriptor tmpthis=fcall.getThis(); - for(MethodDescriptor calledmd:targets) { + for(MethodDescriptor calledmd : targets) { FlatMethod fm=state.getMethodFlat(calledmd); boolean newmethod=false; - + //Build tmpMap HashMap tmpMap=new HashMap(); int offset=0; if(tmpthis!=null) { - tmpMap.put(tmpthis, fm.getParameter(offset++)); + tmpMap.put(tmpthis, fm.getParameter(offset++)); } - for(int i=0;i()); + callMap.put(fcall, new HashSet()); } - + Delta returnDelta=null; if (!callMap.get(fcall).contains(block.getStart())) { - callMap.get(fcall).add(block.getStart()); - newmethod=true; - - //Hook up return - if (!returnMap.containsKey(block.getExit())) { - returnMap.put(block.getExit(), new HashSet()); - } - returnMap.get(block.getExit()).add(new PPoint(callblock, callindex)); - - if (bbgraphMap.containsKey(block.getExit())) { - //Need to push existing results to current node - if (returnDelta==null) { - returnDelta=new Delta(null, false); - Vector exitblocknodes=block.getExit().nodes(); - FlatExit fexit=(FlatExit)exitblocknodes.get(exitblocknodes.size()-1); - buildInitDelta(graphMap.get(fexit), returnDelta); - if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) { - returnDelta.setBlock(new PPoint(callblock, callindex)); - toprocess.add(returnDelta); - } - } else { - if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) { - toprocess.add(returnDelta.diffBlock(new PPoint(callblock, callindex))); - } - } - } + callMap.get(fcall).add(block.getStart()); + newmethod=true; + + //Hook up return + if (!returnMap.containsKey(block.getExit())) { + returnMap.put(block.getExit(), new HashSet()); + } + returnMap.get(block.getExit()).add(new PPoint(callblock, callindex)); + + if (bbgraphMap.containsKey(block.getExit())) { + //Need to push existing results to current node + if (returnDelta==null) { + returnDelta=new Delta(null, false); + Vector exitblocknodes=block.getExit().nodes(); + FlatExit fexit=(FlatExit)exitblocknodes.get(exitblocknodes.size()-1); + buildInitDelta(graphMap.get(fexit), returnDelta); + if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) { + returnDelta.setBlock(new PPoint(callblock, callindex)); + toprocess.add(returnDelta); + } + } else { + if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) { + toprocess.add(returnDelta.diffBlock(new PPoint(callblock, callindex))); + } + } + } } - + if (oldedgeset==null) { - //First build of this graph - //Build and enqueue delta...safe to just use existing delta - Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart())); - //System.out.println("AProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_')); - //d.print(); - toprocess.add(d); + //First build of this graph + //Build and enqueue delta...safe to just use existing delta + Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart())); + //System.out.println("AProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_')); + //d.print(); + toprocess.add(d); } else if (newmethod) { - if (basedelta==null) { - basedelta=newDelta.buildBase(oldedgeset); - } - //Build and enqueue delta - Delta d=basedelta.changeParams(tmpMap, new PPoint(block.getStart())); - //System.out.println("BProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_')); - //d.print(); - toprocess.add(d); + if (basedelta==null) { + basedelta=newDelta.buildBase(oldedgeset); + } + //Build and enqueue delta + Delta d=basedelta.changeParams(tmpMap, new PPoint(block.getStart())); + //System.out.println("BProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_')); + //d.print(); + toprocess.add(d); } else { - //Build and enqueue delta - Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart())); - //System.out.println("CProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_')); - //d.print(); - toprocess.add(d); + //Build and enqueue delta + Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart())); + //System.out.println("CProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_')); + //d.print(); + toprocess.add(d); } } } @@ -778,15 +814,15 @@ public class Pointer implements HeapAnalysis{ externalnodes.addAll(delta.heapedgeremove.keySet()); //remove allinternal nodes externalnodes.removeAll(nodeset); - for(AllocNode extNode:externalnodes) { + for(AllocNode extNode : externalnodes) { //Compute set of edges from given node MySet edges=new MySet(delta.baseheapedge.get(extNode)); edges.removeAll(delta.heapedgeremove.get(extNode)); edges.addAll(delta.heapedgeadd.get(extNode)); - - for(Edge e:edges) { - if (nodeset.contains(e.dst)) - externaledgeset.add(e); + + for(Edge e : edges) { + if (nodeset.contains(e.dst)) + externaledgeset.add(e); } } @@ -797,37 +833,37 @@ public class Pointer implements HeapAnalysis{ temps.addAll(delta.varedgeremove.keySet()); //remove allinternal nodes temps.removeAll(nodeset); - - for(TempDescriptor tmp:temps) { + + for(TempDescriptor tmp : temps) { //Compute set of edges from given node MySet edges=new MySet(delta.basevaredge.get(tmp)); - + edges.removeAll(delta.varedgeremove.get(tmp)); edges.addAll(delta.varedgeadd.get(tmp)); - - for(Edge e:edges) { - if (nodeset.contains(e.dst)) - externaledgeset.add(e); + + for(Edge e : edges) { + if (nodeset.contains(e.dst)) + externaledgeset.add(e); } } } /* This function removes the caller reachable edges from the * callee's heap. */ - + void removeEdges(Graph graph, Delta delta, HashSet nodeset, MySet edgeset, MySet externaledgeset) { //Want to remove the set of internal edges - for(Edge e:edgeset) { + for(Edge e : edgeset) { if (e.src!=null&&!graph.callerEdges.contains(e)) { - delta.removeHeapEdge(e); + delta.removeHeapEdge(e); } } //Want to remove the set of external edges - for(Edge e:externaledgeset) { + for(Edge e : externaledgeset) { //want to remove the set of internal edges if (!graph.callerEdges.contains(e)) - delta.removeEdge(e); + delta.removeEdge(e); } } @@ -848,7 +884,7 @@ public class Pointer implements HeapAnalysis{ //Go through each temp processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, false); - + //Traverse all reachable nodes computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, null); @@ -868,7 +904,7 @@ public class Pointer implements HeapAnalysis{ graph.externalEdgeSet=externaledgeset; graph.reachNode=nodeset; graph.reachEdge=edgeset; - + graph.callTargets=newtargets; graph.callNodeAges=new HashSet(); graph.callOldNodes=new HashSet(); @@ -888,23 +924,23 @@ public class Pointer implements HeapAnalysis{ Stack tovisit=new Stack(); TempDescriptor tmpthis=fcall.getThis(); //Fix up delta to get rid of unnecessary heap edge removals - for(Map.Entry> entry:delta.heapedgeremove.entrySet()) { - for(Iterator eit=entry.getValue().iterator();eit.hasNext();) { - Edge e=eit.next(); - if (graph.callerEdges.contains(e)) - eit.remove(); - } + for(Map.Entry> entry : delta.heapedgeremove.entrySet()) { + for(Iterator eit=entry.getValue().iterator(); eit.hasNext(); ) { + Edge e=eit.next(); + if (graph.callerEdges.contains(e)) + eit.remove(); + } } //Fix up delta to get rid of unnecessary var edge removals - for(Map.Entry> entry:delta.varedgeremove.entrySet()) { - for(Iterator eit=entry.getValue().iterator();eit.hasNext();) { - Edge e=eit.next(); - if (graph.callerEdges.contains(e)) - eit.remove(); - } + for(Map.Entry> entry : delta.varedgeremove.entrySet()) { + for(Iterator eit=entry.getValue().iterator(); eit.hasNext(); ) { + Edge e=eit.next(); + if (graph.callerEdges.contains(e)) + eit.remove(); + } } - + //Handle the this temp processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, oldnodeset); @@ -913,17 +949,17 @@ public class Pointer implements HeapAnalysis{ //Go through each new heap edge that starts from old node MySet newedges=GraphManip.getDiffEdges(delta, oldnodeset); edgeset.addAll(newedges); - for(Edge e:newedges) { - //Add new edges that start from old node to newDelta - AllocNode src=e.src; - if (!newDelta.heapedgeadd.containsKey(src)) { - newDelta.heapedgeadd.put(src, new MySet()); - } - newDelta.heapedgeadd.get(src).add(e.makeOld()); - if (!nodeset.contains(e.dst)&&!oldnodeset.contains(e.dst)) { - nodeset.add(e.dst); - tovisit.add(e.dst); - } + for(Edge e : newedges) { + //Add new edges that start from old node to newDelta + AllocNode src=e.src; + if (!newDelta.heapedgeadd.containsKey(src)) { + newDelta.heapedgeadd.put(src, new MySet()); + } + newDelta.heapedgeadd.get(src).add(e.makeOld()); + if (!nodeset.contains(e.dst)&&!oldnodeset.contains(e.dst)) { + nodeset.add(e.dst); + tovisit.add(e.dst); + } } //Traverse all reachable nodes @@ -951,31 +987,31 @@ public class Pointer implements HeapAnalysis{ Set seseCallers=OoOJava?taskAnalysis.getTransitiveExecutingRBlocks(fcall):null; //Check if the new nodes allow us to insert a new edge - for(AllocNode node:nodeset) { - if (graph.callNewEdges.containsKey(node)) { - for(Iterator eit=graph.callNewEdges.get(node).iterator();eit.hasNext();) { - Edge e=eit.next(); - if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&& - (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) { - Edge edgetoadd=e.copy();//we need our own copy to modify below - eit.remove(); - if (seseCallers!=null) - edgetoadd.taintModify(seseCallers); - mergeCallEdge(graph, delta, edgetoadd); - } - } - } - } - - for(Edge e:edgeset) { - //See if these edges would allow an old edge to be added - if (graph.callOldEdges.containsKey(e)) { - for(Edge adde:graph.callOldEdges.get(e)) { - Edge ecopy=adde.copy(); - ecopy.statuspredicate=e.statuspredicate; - mergeCallEdge(graph, delta, ecopy); - } - } + for(AllocNode node : nodeset) { + if (graph.callNewEdges.containsKey(node)) { + for(Iterator eit=graph.callNewEdges.get(node).iterator(); eit.hasNext(); ) { + Edge e=eit.next(); + if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&& + (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) { + Edge edgetoadd=e.copy(); //we need our own copy to modify below + eit.remove(); + if (seseCallers!=null) + edgetoadd.taintModify(seseCallers); + mergeCallEdge(graph, delta, edgetoadd); + } + } + } + } + + for(Edge e : edgeset) { + //See if these edges would allow an old edge to be added + if (graph.callOldEdges.containsKey(e)) { + for(Edge adde : graph.callOldEdges.get(e)) { + Edge ecopy=adde.copy(); + ecopy.statuspredicate=e.statuspredicate; + mergeCallEdge(graph, delta, ecopy); + } + } } //Add in new external edges @@ -996,66 +1032,66 @@ public class Pointer implements HeapAnalysis{ void processSumVarEdgeSet(HashMap> map, Delta delta, Graph graph) { MySet edgestoadd=new MySet(); MySet edgestoremove=new MySet(); - for(Iterator>> eit=map.entrySet().iterator();eit.hasNext();) { + for(Iterator>> eit=map.entrySet().iterator(); eit.hasNext(); ) { Map.Entry> entry=eit.next(); MySet edgeset=entry.getValue(); - for(Edge e:edgeset) { - Edge copy=e.copy(); - boolean rewrite=false; - if (copy.dst!=null&&graph.callNodeAges.contains(copy.dst)) { - copy.dst=allocFactory.getAllocNode(copy.dst, true); - rewrite=true; - } - if (rewrite) { - edgestoremove.add(e); - edgestoadd.add(copy); - } + for(Edge e : edgeset) { + Edge copy=e.copy(); + boolean rewrite=false; + if (copy.dst!=null&&graph.callNodeAges.contains(copy.dst)) { + copy.dst=allocFactory.getAllocNode(copy.dst, true); + rewrite=true; + } + if (rewrite) { + edgestoremove.add(e); + edgestoadd.add(copy); + } } } - for(Edge e:edgestoremove) { + for(Edge e : edgestoremove) { if (!graph.callerEdges.contains(e)) - delta.removeVarEdge(e); + delta.removeVarEdge(e); } - for(Edge e:edgestoadd) { + for(Edge e : edgestoadd) { delta.addVarEdge(e); } } - + public Alloc getAllocationSiteFromFlatNew(FlatNew node) { return allocFactory.getAllocNode(node, false).getAllocSite(); } - + void processSumHeapEdgeSet(HashMap> map, Delta delta, Graph graph) { MySet edgestoadd=new MySet(); MySet edgestoremove=new MySet(); - for(Iterator>> eit=map.entrySet().iterator();eit.hasNext();) { + for(Iterator>> eit=map.entrySet().iterator(); eit.hasNext(); ) { Map.Entry> entry=eit.next(); AllocNode node=entry.getKey(); MySet edgeset=entry.getValue(); - for(Edge e:edgeset) { - Edge copy=e.copy(); - boolean rewrite=false; - if (copy.src!=null&&graph.callNodeAges.contains(copy.src)) { - copy.src=allocFactory.getAllocNode(copy.src, true); - rewrite=true; - } - if (copy.dst!=null&&graph.callNodeAges.contains(copy.dst)) { - copy.dst=allocFactory.getAllocNode(copy.dst, true); - rewrite=true; - } - if (rewrite) { - edgestoremove.add(e); - edgestoadd.add(copy); - } - } - } - for(Edge e:edgestoremove) { + for(Edge e : edgeset) { + Edge copy=e.copy(); + boolean rewrite=false; + if (copy.src!=null&&graph.callNodeAges.contains(copy.src)) { + copy.src=allocFactory.getAllocNode(copy.src, true); + rewrite=true; + } + if (copy.dst!=null&&graph.callNodeAges.contains(copy.dst)) { + copy.dst=allocFactory.getAllocNode(copy.dst, true); + rewrite=true; + } + if (rewrite) { + edgestoremove.add(e); + edgestoadd.add(copy); + } + } + } + for(Edge e : edgestoremove) { if (!graph.callerEdges.contains(e)) - delta.removeHeapEdge(e); + delta.removeHeapEdge(e); } - for(Edge e:edgestoadd) { + for(Edge e : edgestoadd) { delta.addHeapEdge(e); } } @@ -1063,26 +1099,26 @@ public class Pointer implements HeapAnalysis{ //Handle external edges void processCallExternal(Graph graph, Delta newDelta, MySet externalEdgeSet) { //Add external edges in - for(Edge e:externalEdgeSet) { + for(Edge e : externalEdgeSet) { //First did we age the source Edge newedge=e.copy(); if (newedge.src!=null&&!e.src.isSummary()&&graph.callNodeAges.contains(e.src)) { - AllocNode summaryNode=allocFactory.getAllocNode(newedge.src, true); - newedge.src=summaryNode; + AllocNode summaryNode=allocFactory.getAllocNode(newedge.src, true); + newedge.src=summaryNode; } //Compute target if (graph.callNodeAges.contains(e.dst)&&!e.dst.isSummary()) { - if (graph.callOldNodes.contains(e.dst)) { - //Need two edges - Edge copy=newedge.copy(); - mergeEdge(graph, newDelta, copy); - } - //Now add summarized node - newedge.dst=allocFactory.getAllocNode(newedge.dst, true); - mergeCallEdge(graph, newDelta, newedge); + if (graph.callOldNodes.contains(e.dst)) { + //Need two edges + Edge copy=newedge.copy(); + mergeEdge(graph, newDelta, copy); + } + //Now add summarized node + newedge.dst=allocFactory.getAllocNode(newedge.dst, true); + mergeCallEdge(graph, newDelta, newedge); } else { - //Add edge to single node - mergeEdge(graph, newDelta, newedge); + //Add edge to single node + mergeEdge(graph, newDelta, newedge); } } } @@ -1096,109 +1132,123 @@ public class Pointer implements HeapAnalysis{ FlatCall fcall=(FlatCall)nodes.get(ppoint.getIndex()); Graph graph=graphMap.get(fcall); Graph oldgraph=(ppoint.getIndex()==0)? - bbgraphMap.get(bblock): - graphMap.get(nodes.get(ppoint.getIndex()-1)); + bbgraphMap.get(bblock): + graphMap.get(nodes.get(ppoint.getIndex()-1)); Set seseCallers=OoOJava?taskAnalysis.getTransitiveExecutingRBlocks(fcall):null; //Age outside nodes if necessary - for(Iterator nodeit=delta.addNodeAges.iterator();nodeit.hasNext();) { + for(Iterator nodeit=delta.addNodeAges.iterator(); nodeit.hasNext(); ) { AllocNode node=nodeit.next(); if (!graph.callNodeAges.contains(node)) { - graph.callNodeAges.add(node); - newDelta.addNodeAges.add(node); + graph.callNodeAges.add(node); + newDelta.addNodeAges.add(node); } + AllocNode summaryAdd=null; if (!graph.reachNode.contains(node)&&!node.isSummary()) { - /* Need to age node in existing graph*/ - summarizeInGraph(graph, newDelta, node); - } - if (graph.callNewEdges.containsKey(node)) { - for(Iterator eit=graph.callNewEdges.get(node).iterator();eit.hasNext();) { - Edge e=eit.next(); - if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&& - (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) { - Edge edgetoadd=e.copy();//we need our own copy to modify below - eit.remove(); - if (seseCallers!=null) - edgetoadd.taintModify(seseCallers); - mergeCallEdge(graph, newDelta, edgetoadd); - } - } - } + /* Need to age node in existing graph*/ + + AllocNode summaryNode=allocFactory.getAllocNode(node, true); + + if (!graph.callNodeAges.contains(summaryNode)) { + graph.callNodeAges.add(summaryNode); + newDelta.addNodeAges.add(summaryNode); + summaryAdd=summaryNode; + } + summarizeInGraph(graph, newDelta, node); + } + do { + if (graph.callNewEdges.containsKey(node)) { + for(Iterator eit=graph.callNewEdges.get(node).iterator(); eit.hasNext(); ) { + Edge e=eit.next(); + if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&& + (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) { + Edge edgetoadd=e.copy(); //we need our own copy to modify below + eit.remove(); + if (seseCallers!=null) + edgetoadd.taintModify(seseCallers); + mergeCallEdge(graph, newDelta, edgetoadd); + } + } + } + //do the summary node if we added that also... + node=summaryAdd; + summaryAdd=null; + } while(node!=null); } //Add heap edges in - for(Map.Entry> entry:delta.heapedgeadd.entrySet()) { - for(Edge e:entry.getValue()) { - boolean addedge=false; - Edge edgetoadd=null; - if (e.statuspredicate==Edge.NEW) { - if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&& - (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) { - edgetoadd=e.copy();//we need our own copy to modify below - } else { - graph.addCallEdge(e); - } - } else { - Edge[] edgeArray=e.makeStatus(allocFactory); - - int statuspredicate=0; - for(int i=0;i()); - } - if (graph.callOldEdges.get(origEdgeKey).contains(e)) { - Edge olde=graph.callOldEdges.get(origEdgeKey).get(e); - graph.callOldEdges.get(origEdgeKey).add(olde.merge(e)); - } else { - graph.callOldEdges.get(origEdgeKey).add(e); - } - } - if (statuspredicate!=0) { - Edge newe=e.copy(); - newe.statuspredicate=statuspredicate; - edgetoadd=newe; - } - } - if (seseCallers!=null&&edgetoadd!=null) - edgetoadd.taintModify(seseCallers); - mergeCallEdge(graph, newDelta, edgetoadd); + for(Map.Entry> entry : delta.heapedgeadd.entrySet()) { + for(Edge e : entry.getValue()) { + boolean addedge=false; + Edge edgetoadd=null; + if (e.statuspredicate==Edge.NEW) { + if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&& + (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) { + edgetoadd=e.copy(); //we need our own copy to modify below + } else { + graph.addCallEdge(e); + } + } else { + Edge[] edgeArray=e.makeStatus(allocFactory); + + int statuspredicate=0; + for(int i=0; i()); + } + if (graph.callOldEdges.get(origEdgeKey).contains(e)) { + Edge olde=graph.callOldEdges.get(origEdgeKey).get(e); + graph.callOldEdges.get(origEdgeKey).add(olde.merge(e)); + } else { + graph.callOldEdges.get(origEdgeKey).add(e); + } + } + if (statuspredicate!=0) { + Edge newe=e.copy(); + newe.statuspredicate=statuspredicate; + edgetoadd=newe; + } + } + if (seseCallers!=null&&edgetoadd!=null) + edgetoadd.taintModify(seseCallers); + mergeCallEdge(graph, newDelta, edgetoadd); } } - + processCallExternal(graph, newDelta, graph.externalEdgeSet); //Add edge for return value if (fcall.getReturnTemp()!=null) { MySet returnedge=delta.varedgeadd.get(returntmp); if (returnedge!=null) - for(Edge e:returnedge) { - //skip the edge if types don't allow it... - if (!typeUtil.isSuperorType(fcall.getReturnTemp().getType(), e.dst.getType())) - continue; - Edge newedge=e.copy(); - newedge.srcvar=fcall.getReturnTemp(); - if (seseCallers!=null) - newedge.taintModify(seseCallers); - mergeEdge(graph, newDelta, newedge); - } + for(Edge e : returnedge) { + //skip the edge if types don't allow it... + if (!typeUtil.isSuperorType(fcall.getReturnTemp().getType(), e.dst.getType())) + continue; + Edge newedge=e.copy(); + newedge.srcvar=fcall.getReturnTemp(); + if (seseCallers!=null) + newedge.taintModify(seseCallers); + mergeEdge(graph, newDelta, newedge); + } } applyDiffs(graph, newDelta); return newDelta; } - + public void mergeEdge(Graph graph, Delta newDelta, Edge edgetoadd) { if (edgetoadd!=null) { Edge match=graph.getMatch(edgetoadd); if (match==null||!match.subsumes(edgetoadd)) { - Edge mergededge=edgetoadd.merge(match); - newDelta.addEdge(mergededge); + Edge mergededge=edgetoadd.merge(match); + newDelta.addEdge(mergededge); } } } @@ -1210,11 +1260,11 @@ public class Pointer implements HeapAnalysis{ newDelta.addEdgeClear(edgetoadd); Edge match=graph.getMatch(edgetoadd); - + if (match==null||!match.subsumes(edgetoadd)) { - Edge mergededge=edgetoadd.merge(match); - newDelta.addEdge(mergededge); - graph.callerEdges.add(mergededge); + Edge mergededge=edgetoadd.merge(match); + newDelta.addEdge(mergededge); + graph.callerEdges.add(mergededge); } } } @@ -1227,24 +1277,24 @@ public class Pointer implements HeapAnalysis{ //Handle outgoing heap edges MySet edgeset=graph.getEdges(singleNode); - for(Edge e:edgeset) { + for(Edge e : edgeset) { Edge rewrite=e.rewrite(singleNode, summaryNode); //Remove old edge newDelta.removeHeapEdge(e); mergeCallEdge(graph, newDelta, rewrite); } - + //Handle incoming edges MySet backedges=graph.getBackEdges(singleNode); - for(Edge e:backedges) { + for(Edge e : backedges) { if (e.dst==singleNode) { - //Need to get original edge so that predicate will be correct - Edge match=graph.getMatch(e); - if (match!=null) { - Edge rewrite=match.rewrite(singleNode, summaryNode); - newDelta.removeEdge(match); - mergeCallEdge(graph, newDelta, rewrite); - } + //Need to get original edge so that predicate will be correct + Edge match=graph.getMatch(e); + if (match!=null) { + Edge rewrite=match.rewrite(singleNode, summaryNode); + newDelta.removeEdge(match); + mergeCallEdge(graph, newDelta, rewrite); + } } } } @@ -1258,115 +1308,115 @@ public class Pointer implements HeapAnalysis{ if (genbackwards&&graph.backMap==null) { graph.backMap=new HashMap>(); if (graph.parent.backMap==null) { - graph.parent.backMap=new HashMap>(); - for(Map.Entry> entry:graph.nodeMap.entrySet()) { - for(Edge e:entry.getValue()) { - if (!graph.parent.backMap.containsKey(e.dst)) - graph.parent.backMap.put(e.dst, new MySet()); - graph.parent.backMap.get(e.dst).add(e); - } - } - for(Map.Entry> entry:graph.varMap.entrySet()) { - for(Edge e:entry.getValue()) { - if (!graph.parent.backMap.containsKey(e.dst)) - graph.parent.backMap.put(e.dst, new MySet()); - graph.parent.backMap.get(e.dst).add(e); - } - } + graph.parent.backMap=new HashMap>(); + for(Map.Entry> entry : graph.nodeMap.entrySet()) { + for(Edge e : entry.getValue()) { + if (!graph.parent.backMap.containsKey(e.dst)) + graph.parent.backMap.put(e.dst, new MySet()); + graph.parent.backMap.get(e.dst).add(e); + } + } + for(Map.Entry> entry : graph.varMap.entrySet()) { + for(Edge e : entry.getValue()) { + if (!graph.parent.backMap.containsKey(e.dst)) + graph.parent.backMap.put(e.dst, new MySet()); + graph.parent.backMap.get(e.dst).add(e); + } + } } } //Add hidden base edges - for(Map.Entry> e: delta.baseheapedge.entrySet()) { + for(Map.Entry> e : delta.baseheapedge.entrySet()) { AllocNode node=e.getKey(); MySet edges=e.getValue(); if (graph.nodeMap.containsKey(node)) { - MySet nodeEdges=graph.nodeMap.get(node); - nodeEdges.addAll(edges); + MySet nodeEdges=graph.nodeMap.get(node); + nodeEdges.addAll(edges); } } //Remove heap edges - for(Map.Entry> e: delta.heapedgeremove.entrySet()) { + for(Map.Entry> e : delta.heapedgeremove.entrySet()) { AllocNode node=e.getKey(); MySet edgestoremove=e.getValue(); if (graph.nodeMap.containsKey(node)) { - //Just apply diff to current map - graph.nodeMap.get(node).removeAll(edgestoremove); + //Just apply diff to current map + graph.nodeMap.get(node).removeAll(edgestoremove); } else { - //Generate diff from parent graph - MySet parentedges=graph.parent.nodeMap.get(node); - if (parentedges!=null) { - MySet newedgeset=Util.setSubtract(parentedges, edgestoremove); - graph.nodeMap.put(node, newedgeset); - } + //Generate diff from parent graph + MySet parentedges=graph.parent.nodeMap.get(node); + if (parentedges!=null) { + MySet newedgeset=Util.setSubtract(parentedges, edgestoremove); + graph.nodeMap.put(node, newedgeset); + } } } //Add heap edges - for(Map.Entry> e: delta.heapedgeadd.entrySet()) { + for(Map.Entry> e : delta.heapedgeadd.entrySet()) { AllocNode node=e.getKey(); MySet edgestoadd=e.getValue(); - //If we have not done a subtract, then + //If we have not done a subtract, then if (!graph.nodeMap.containsKey(node)) { - //Copy the parent entry - if (graph.parent.nodeMap.containsKey(node)) - graph.nodeMap.put(node, (MySet)graph.parent.nodeMap.get(node).clone()); - else - graph.nodeMap.put(node, new MySet()); + //Copy the parent entry + if (graph.parent.nodeMap.containsKey(node)) + graph.nodeMap.put(node, (MySet)graph.parent.nodeMap.get(node).clone()); + else + graph.nodeMap.put(node, new MySet()); } Edge.mergeEdgesInto(graph.nodeMap.get(node),edgestoadd); if (genbackwards) { - for(Edge eadd:edgestoadd) { - if (!graph.backMap.containsKey(eadd.dst)) - graph.backMap.put(eadd.dst, new MySet()); - graph.backMap.get(eadd.dst).add(eadd); - } + for(Edge eadd : edgestoadd) { + if (!graph.backMap.containsKey(eadd.dst)) + graph.backMap.put(eadd.dst, new MySet()); + graph.backMap.get(eadd.dst).add(eadd); + } } } //Remove var edges - for(Map.Entry> e: delta.varedgeremove.entrySet()) { + for(Map.Entry> e : delta.varedgeremove.entrySet()) { TempDescriptor tmp=e.getKey(); MySet edgestoremove=e.getValue(); if (graph.varMap.containsKey(tmp)) { - //Just apply diff to current map - graph.varMap.get(tmp).removeAll(edgestoremove); + //Just apply diff to current map + graph.varMap.get(tmp).removeAll(edgestoremove); } else if (graph.parent.varMap.containsKey(tmp)) { - //Generate diff from parent graph - MySet parentedges=graph.parent.varMap.get(tmp); - MySet newedgeset=Util.setSubtract(parentedges, edgestoremove); - graph.varMap.put(tmp, newedgeset); + //Generate diff from parent graph + MySet parentedges=graph.parent.varMap.get(tmp); + MySet newedgeset=Util.setSubtract(parentedges, edgestoremove); + graph.varMap.put(tmp, newedgeset); } } //Add var edges - for(Map.Entry> e: delta.varedgeadd.entrySet()) { + for(Map.Entry> e : delta.varedgeadd.entrySet()) { TempDescriptor tmp=e.getKey(); MySet edgestoadd=e.getValue(); if (graph.varMap.containsKey(tmp)) { - Edge.mergeEdgesInto(graph.varMap.get(tmp), edgestoadd); + Edge.mergeEdgesInto(graph.varMap.get(tmp), edgestoadd); } else if (graph.parent.varMap.containsKey(tmp)) { - graph.varMap.put(tmp, new MySet(graph.parent.varMap.get(tmp))); - Edge.mergeEdgesInto(graph.varMap.get(tmp), edgestoadd); + graph.varMap.put(tmp, new MySet(graph.parent.varMap.get(tmp))); + Edge.mergeEdgesInto(graph.varMap.get(tmp), edgestoadd); } else - graph.varMap.put(tmp, (MySet) edgestoadd.clone()); + graph.varMap.put(tmp, (MySet)edgestoadd.clone()); if (genbackwards) { - for(Edge eadd:edgestoadd) { - if (!graph.backMap.containsKey(eadd.dst)) - graph.backMap.put(eadd.dst, new MySet()); - graph.backMap.get(eadd.dst).add(eadd); - } + for(Edge eadd : edgestoadd) { + if (!graph.backMap.containsKey(eadd.dst)) + graph.backMap.put(eadd.dst, new MySet()); + graph.backMap.get(eadd.dst).add(eadd); + } } } //Add node additions - for(AllocNode node:delta.addNodeAges) { + for(AllocNode node : delta.addNodeAges) { graph.nodeAges.add(node); } - - for(Map.Entry nodeentry:delta.addOldNodes.entrySet()) { + + for(Map.Entry nodeentry : delta.addOldNodes.entrySet()) { AllocNode node=nodeentry.getKey(); Boolean ispresent=nodeentry.getValue(); graph.oldNodes.put(node, ispresent); @@ -1381,14 +1431,17 @@ public class Pointer implements HeapAnalysis{ FlatSetFieldNode n=(FlatSetFieldNode)node; return !accessible.isAccessible(n, n.getDst()); } + case FKind.FlatSetElementNode: { FlatSetElementNode n=(FlatSetElementNode)node; return !accessible.isAccessible(n, n.getDst()); } + case FKind.FlatFieldNode: { FlatFieldNode n=(FlatFieldNode)node; return !accessible.isAccessible(n, n.getSrc()); } + case FKind.FlatElementNode: { FlatElementNode n=(FlatElementNode)node; return !accessible.isAccessible(n, n.getSrc()); @@ -1417,37 +1470,37 @@ public class Pointer implements HeapAnalysis{ MySet dstEdges=GraphManip.getEdges(graph, delta, dst); if (OoOJava&&!accessible.isAccessible(node, dst)) { - Taint dstStallTaint=Taint.factory(node, dst, AllocFactory.dummySite, null, ReachGraph.predsEmpty); - dstEdges=Edge.taintAll(dstEdges, dstStallTaint); - updateVarDelta(graph, delta, dst, dstEdges, null); + Taint dstStallTaint=Taint.factory(node, dst, AllocFactory.dummySite, null, ReachGraph.predsEmpty); + dstEdges=Edge.taintAll(dstEdges, dstStallTaint); + updateVarDelta(graph, delta, dst, dstEdges, null); } if (OoOJava) { - effectsAnalysis.analyzeFlatSetFieldNode(dstEdges, fd, node); + effectsAnalysis.analyzeFlatSetFieldNode(dstEdges, fd, node); } //Do nothing for non pointers if (!src.getType().isPtr()) { - if (mustProcess.contains(node)) { - applyDiffs(graph, delta); - } - return delta; + if (mustProcess.contains(node)) { + applyDiffs(graph, delta); + } + return delta; } MySet srcEdges=GraphManip.getEdges(graph, delta, src); if (OoOJava&&!accessible.isAccessible(node, src)) { - Taint srcStallTaint=Taint.factory(node, src, AllocFactory.dummySite, null, ReachGraph.predsEmpty); - srcEdges=Edge.taintAll(srcEdges, srcStallTaint); - updateVarDelta(graph, delta, src, srcEdges, null); + Taint srcStallTaint=Taint.factory(node, src, AllocFactory.dummySite, null, ReachGraph.predsEmpty); + srcEdges=Edge.taintAll(srcEdges, srcStallTaint); + updateVarDelta(graph, delta, src, srcEdges, null); } MySet edgesToAdd=GraphManip.genEdges(dstEdges, fd, srcEdges); MySet edgesToRemove=null; if (dstEdges.size()==1&&!dstEdges.iterator().next().dst.isSummary()&&fd!=null) { - /* Can do a strong update */ - edgesToRemove=GraphManip.getEdges(graph, delta, dstEdges, fd); - graph.strongUpdateSet=edgesToRemove; + /* Can do a strong update */ + edgesToRemove=GraphManip.getEdges(graph, delta, dstEdges, fd); + graph.strongUpdateSet=edgesToRemove; } else - graph.strongUpdateSet=new MySet(); + graph.strongUpdateSet=new MySet(); /* Update diff */ updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove); @@ -1456,20 +1509,20 @@ public class Pointer implements HeapAnalysis{ MySet newDstEdges=GraphManip.getDiffEdges(delta, dst); if (OoOJava&&!accessible.isAccessible(node, dst)) { - Taint dstStallTaint=Taint.factory(node, dst, AllocFactory.dummySite, null, ReachGraph.predsEmpty); - newDstEdges=Edge.taintAll(newDstEdges, dstStallTaint); - updateVarDelta(graph, delta, dst, newDstEdges, null); + Taint dstStallTaint=Taint.factory(node, dst, AllocFactory.dummySite, null, ReachGraph.predsEmpty); + newDstEdges=Edge.taintAll(newDstEdges, dstStallTaint); + updateVarDelta(graph, delta, dst, newDstEdges, null); } if (OoOJava) { - effectsAnalysis.analyzeFlatSetFieldNode(newDstEdges, fd, node); + effectsAnalysis.analyzeFlatSetFieldNode(newDstEdges, fd, node); } if (!src.getType().isPtr()) { - if (mustProcess.contains(node)) { - applyDiffs(graph, delta); - } - return delta; + if (mustProcess.contains(node)) { + applyDiffs(graph, delta); + } + return delta; } /* Next look at new sources */ @@ -1480,34 +1533,34 @@ public class Pointer implements HeapAnalysis{ HashSet dstNodes=GraphManip.getNodes(graph, delta, dst); if (OoOJava&&!accessible.isAccessible(node, src)) { - Taint srcStallTaint=Taint.factory(node, src, AllocFactory.dummySite, null, ReachGraph.predsEmpty); - newSrcEdges=Edge.taintAll(newSrcEdges, srcStallTaint); - updateVarDelta(graph, delta, src, newSrcEdges, null); + Taint srcStallTaint=Taint.factory(node, src, AllocFactory.dummySite, null, ReachGraph.predsEmpty); + newSrcEdges=Edge.taintAll(newSrcEdges, srcStallTaint); + updateVarDelta(graph, delta, src, newSrcEdges, null); } MySet edgesToRemove=null; if (newDstEdges.size()!=0) { - if (dstNodes.size()>1&&!dstNodes.iterator().next().isSummary()&&fd!=null) { - /* Need to undo strong update */ - if (graph.strongUpdateSet!=null) { - edgesToAdd.addAll(graph.strongUpdateSet); - graph.strongUpdateSet=null; //Prevent future strong updates - } - } else if (dstNodes.size()==1&&newDstEdges.size()==1&&!newDstEdges.iterator().next().dst.isSummary()&&graph.strongUpdateSet!=null&&fd!=null) { - edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd); - graph.strongUpdateSet.addAll(edgesToRemove); - } - Edge.mergeEdgesInto(edgesToAdd, GraphManip.genEdges(newDstEdges, fd, srcEdges)); + if (dstNodes.size()>1&&!dstNodes.iterator().next().isSummary()&&fd!=null) { + /* Need to undo strong update */ + if (graph.strongUpdateSet!=null) { + edgesToAdd.addAll(graph.strongUpdateSet); + graph.strongUpdateSet=null; //Prevent future strong updates + } + } else if (dstNodes.size()==1&&newDstEdges.size()==1&&!newDstEdges.iterator().next().dst.isSummary()&&graph.strongUpdateSet!=null&&fd!=null) { + edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd); + graph.strongUpdateSet.addAll(edgesToRemove); + } + Edge.mergeEdgesInto(edgesToAdd, GraphManip.genEdges(newDstEdges, fd, srcEdges)); } //Kill new edges if (graph.strongUpdateSet!=null&&fd!=null) { - MySet otherEdgesToRemove=GraphManip.getDiffEdges(delta, dstNodes, fd); - if (edgesToRemove!=null) - edgesToRemove.addAll(otherEdgesToRemove); - else - edgesToRemove=otherEdgesToRemove; - graph.strongUpdateSet.addAll(otherEdgesToRemove); + MySet otherEdgesToRemove=GraphManip.getDiffEdges(delta, dstNodes, fd); + if (edgesToRemove!=null) + edgesToRemove.addAll(otherEdgesToRemove); + else + edgesToRemove=otherEdgesToRemove; + graph.strongUpdateSet.addAll(otherEdgesToRemove); } //Next look at new destinations @@ -1523,6 +1576,7 @@ public class Pointer implements HeapAnalysis{ Delta processCopyNode(FlatNode node, Delta delta, Graph graph) { TempDescriptor src; TempDescriptor dst; + if (node.kind()==FKind.FlatOpNode) { FlatOpNode fon=(FlatOpNode) node; src=fon.getLeft(); @@ -1532,9 +1586,9 @@ public class Pointer implements HeapAnalysis{ src=frn.getReturnTemp(); dst=returntmp; if (src==null||!src.getType().isPtr()) { - //This is a NOP - applyDiffs(graph, delta); - return delta; + //This is a NOP + applyDiffs(graph, delta); + return delta; } } else { FlatCastNode fcn=(FlatCastNode) node; @@ -1553,9 +1607,9 @@ public class Pointer implements HeapAnalysis{ /* Compute the union, and then the set of edges */ MySet edgesToAdd=GraphManip.genEdges(dst, newSrcEdges); - + /* Compute set of edges to remove */ - MySet edgesToRemove=GraphManip.getDiffEdges(delta, dst); + MySet edgesToRemove=GraphManip.getDiffEdges(delta, dst); /* Update diff */ updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove); @@ -1589,17 +1643,17 @@ public class Pointer implements HeapAnalysis{ if (delta.getInit()) { MySet srcedges=GraphManip.getEdges(graph, delta, src); if (OoOJava) { - if (taint!=null) { - srcedges=Edge.taintAll(srcedges, taint); - updateVarDelta(graph, delta, src, srcedges, null); - } - effectsAnalysis.analyzeFlatFieldNode(srcedges, fd, node); + if (taint!=null) { + srcedges=Edge.taintAll(srcedges, taint); + updateVarDelta(graph, delta, src, srcedges, null); + } + effectsAnalysis.analyzeFlatFieldNode(srcedges, fd, node); } if (!dst.getType().isPtr()) { - if (mustProcess.contains(node)) { - applyDiffs(graph, delta); - } - return delta; + if (mustProcess.contains(node)) { + applyDiffs(graph, delta); + } + return delta; } MySet edgesToAdd=GraphManip.dereference(graph, delta, dst, srcedges, fd, node); @@ -1610,17 +1664,17 @@ public class Pointer implements HeapAnalysis{ } else { MySet newsrcedges=GraphManip.getDiffEdges(delta, src); if (OoOJava) { - if (taint!=null) { - newsrcedges=Edge.taintAll(newsrcedges, taint); - updateVarDelta(graph, delta, src, newsrcedges, null); - } - effectsAnalysis.analyzeFlatFieldNode(newsrcedges, fd, node); + if (taint!=null) { + newsrcedges=Edge.taintAll(newsrcedges, taint); + updateVarDelta(graph, delta, src, newsrcedges, null); + } + effectsAnalysis.analyzeFlatFieldNode(newsrcedges, fd, node); } if (!dst.getType().isPtr()) { - if (mustProcess.contains(node)) { - applyDiffs(graph, delta); - } - return delta; + if (mustProcess.contains(node)) { + applyDiffs(graph, delta); + } + return delta; } /* First compute new objects we read fields of */ MySet allsrcedges=GraphManip.getEdges(graph, delta, src); @@ -1630,11 +1684,11 @@ public class Pointer implements HeapAnalysis{ /* Compute the union, and then the set of edges */ Edge.mergeEdgesInto(edgesToAdd, newfdedges); - + /* Compute set of edges to remove */ - MySet edgesToRemove=GraphManip.getDiffEdges(delta, dst); + MySet edgesToRemove=GraphManip.getDiffEdges(delta, dst); + - /* Update diff */ updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove); applyDiffs(graph, delta); @@ -1648,65 +1702,65 @@ public class Pointer implements HeapAnalysis{ MySet edgeRemove=delta.varedgeremove.get(tmp); MySet existingEdges=graph.getEdges(tmp); if (edgestoRemove!=null) - for(Edge e: edgestoRemove) { - //remove edge from delta - if (edgeAdd!=null) - edgeAdd.remove(e); - //if the edge is already in the graph, add an explicit remove to the delta - if (existingEdges.contains(e)) - delta.removeVarEdge(e); - } - for(Edge e: edgestoAdd) { + for(Edge e : edgestoRemove) { + //remove edge from delta + if (edgeAdd!=null) + edgeAdd.remove(e); + //if the edge is already in the graph, add an explicit remove to the delta + if (existingEdges.contains(e)) + delta.removeVarEdge(e); + } + for(Edge e : edgestoAdd) { //Remove the edge from the remove set if (edgeRemove!=null) - edgeRemove.remove(e); + edgeRemove.remove(e); //Explicitly add it to the add set unless it is already in the graph if (typeUtil.isSuperorType(tmp.getType(), e.dst.getType())) { - if (!existingEdges.contains(e)) { - delta.addVarEdge(e); - } else { - //See if the old edge subsumes the new one - Edge olde=existingEdges.get(e); - if (!olde.subsumes(e)) { - delta.addVarEdge(olde.merge(e)); - } - } + if (!existingEdges.contains(e)) { + delta.addVarEdge(e); + } else { + //See if the old edge subsumes the new one + Edge olde=existingEdges.get(e); + if (!olde.subsumes(e)) { + delta.addVarEdge(olde.merge(e)); + } + } } } } void updateHeapDelta(Graph graph, Delta delta, MySet edgestoAdd, MySet edgestoRemove) { if (edgestoRemove!=null) - for(Edge e: edgestoRemove) { - AllocNode src=e.src; - MySet edgeAdd=delta.heapedgeadd.get(src); - MySet existingEdges=graph.getEdges(src); - //remove edge from delta - if (edgeAdd!=null) - edgeAdd.remove(e); - //if the edge is already in the graph, add an explicit remove to the delta - if (existingEdges.contains(e)) { - delta.removeHeapEdge(e); - } + for(Edge e : edgestoRemove) { + AllocNode src=e.src; + MySet edgeAdd=delta.heapedgeadd.get(src); + MySet existingEdges=graph.getEdges(src); + //remove edge from delta + if (edgeAdd!=null) + edgeAdd.remove(e); + //if the edge is already in the graph, add an explicit remove to the delta + if (existingEdges.contains(e)) { + delta.removeHeapEdge(e); + } } if (edgestoAdd!=null) - for(Edge e: edgestoAdd) { - AllocNode src=e.src; - MySet edgeRemove=delta.heapedgeremove.get(src); - MySet existingEdges=graph.getEdges(src); - //Remove the edge from the remove set - if (edgeRemove!=null) - edgeRemove.remove(e); - //Explicitly add it to the add set unless it is already in the graph - if (!existingEdges.contains(e)) { - delta.addHeapEdge(e); - } else { - //See if the old edge subsumes the new one - Edge olde=existingEdges.get(e); - if (!olde.subsumes(e)) { - delta.addHeapEdge(olde.merge(e)); - } - } + for(Edge e : edgestoAdd) { + AllocNode src=e.src; + MySet edgeRemove=delta.heapedgeremove.get(src); + MySet existingEdges=graph.getEdges(src); + //Remove the edge from the remove set + if (edgeRemove!=null) + edgeRemove.remove(e); + //Explicitly add it to the add set unless it is already in the graph + if (!existingEdges.contains(e)) { + delta.addHeapEdge(e); + } else { + //See if the old edge subsumes the new one + Edge olde=existingEdges.get(e); + if (!olde.subsumes(e)) { + delta.addHeapEdge(olde.merge(e)); + } + } } } @@ -1714,7 +1768,7 @@ public class Pointer implements HeapAnalysis{ applyDiffs(graph, delta); return delta; } - + Delta processNewNode(FlatNew node, Delta delta, Graph graph) { AllocNode summary=allocFactory.getAllocNode(node, true); AllocNode single=allocFactory.getAllocNode(node, false); @@ -1736,90 +1790,89 @@ public class Pointer implements HeapAnalysis{ //Remove the old edges MySet oldedges=graph.getEdges(tmp); if (!oldedges.isEmpty()) - delta.varedgeremove.put(tmp, (MySet) oldedges); + delta.varedgeremove.put(tmp, (MySet)oldedges); //Note that we create a single node delta.addNodeAges.add(single); //Kill the old node if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) { - delta.addOldNodes.put(single, Boolean.FALSE); + delta.addOldNodes.put(single, Boolean.FALSE); } } else { /* 1. Fix up the variable edge additions */ + for(Iterator>> entryIt=delta.varedgeadd.entrySet().iterator(); entryIt.hasNext(); ) { + Map.Entry> entry=entryIt.next(); - for(Iterator>> entryIt=delta.varedgeadd.entrySet().iterator();entryIt.hasNext();) { - Map.Entry> entry=entryIt.next(); - - if (entry.getKey()==tmp) { - /* Check if this is the tmp we overwrite */ - entryIt.remove(); - } else { - /* Otherwise, check if the target of the edge is changed... */ - summarizeSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary); - } + if (entry.getKey()==tmp) { + /* Check if this is the tmp we overwrite */ + entryIt.remove(); + } else { + /* Otherwise, check if the target of the edge is changed... */ + summarizeSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary); + } } - + /* 2. Fix up the base variable edges */ - for(Iterator>> entryIt=delta.basevaredge.entrySet().iterator();entryIt.hasNext();) { - Map.Entry> entry=entryIt.next(); - TempDescriptor entrytmp=entry.getKey(); - if (entrytmp==tmp) { - /* Check is this is the tmp we overwrite, if so add to remove set */ - Util.relationUpdate(delta.varedgeremove, tmp, null, entry.getValue()); - } else if (graph.varMap.containsKey(entrytmp)) { - /* Check if the target of the edge is changed */ - MySet newset=(MySet)entry.getValue().clone(); - MySet removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary); - Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset); - Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset); - } else { - /* Check if the target of the edge is changed */ - MySet newset=(MySet)entry.getValue().clone(); - MySet removeset=shrinkSet(newset, graph.parent.varMap.get(entrytmp), single, summary); - Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset); - Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset); - } + for(Iterator>> entryIt=delta.basevaredge.entrySet().iterator(); entryIt.hasNext(); ) { + Map.Entry> entry=entryIt.next(); + TempDescriptor entrytmp=entry.getKey(); + if (entrytmp==tmp) { + /* Check is this is the tmp we overwrite, if so add to remove set */ + Util.relationUpdate(delta.varedgeremove, tmp, null, entry.getValue()); + } else if (graph.varMap.containsKey(entrytmp)) { + /* Check if the target of the edge is changed */ + MySet newset=(MySet)entry.getValue().clone(); + MySet removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary); + Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset); + Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset); + } else { + /* Check if the target of the edge is changed */ + MySet newset=(MySet)entry.getValue().clone(); + MySet removeset=shrinkSet(newset, graph.parent.varMap.get(entrytmp), single, summary); + Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset); + Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset); + } } /* 3. Fix up heap edge additions */ HashMap> addheapedge=new HashMap>(); - for(Iterator>> entryIt=delta.heapedgeadd.entrySet().iterator();entryIt.hasNext();) { - Map.Entry> entry=entryIt.next(); - MySet edgeset=entry.getValue(); - AllocNode allocnode=entry.getKey(); - if (allocnode==single) { - entryIt.remove(); - summarizeSet(edgeset, graph.nodeMap.get(summary), single, summary); - addheapedge.put(summary, edgeset); - } else { - summarizeSet(edgeset, graph.nodeMap.get(allocnode), single, summary); - } + for(Iterator>> entryIt=delta.heapedgeadd.entrySet().iterator(); entryIt.hasNext(); ) { + Map.Entry> entry=entryIt.next(); + MySet edgeset=entry.getValue(); + AllocNode allocnode=entry.getKey(); + if (allocnode==single) { + entryIt.remove(); + summarizeSet(edgeset, graph.nodeMap.get(summary), single, summary); + addheapedge.put(summary, edgeset); + } else { + summarizeSet(edgeset, graph.nodeMap.get(allocnode), single, summary); + } } - + /* Merge in diffs */ - for(Map.Entry> entry:addheapedge.entrySet()) { - AllocNode allocnode=entry.getKey(); - Util.relationUpdate(delta.heapedgeadd, allocnode, null, entry.getValue()); + for(Map.Entry> entry : addheapedge.entrySet()) { + AllocNode allocnode=entry.getKey(); + Util.relationUpdate(delta.heapedgeadd, allocnode, null, entry.getValue()); } /* 4. Fix up the base heap edges */ - for(Iterator>> entryIt=delta.baseheapedge.entrySet().iterator();entryIt.hasNext();) { - Map.Entry> entry=entryIt.next(); - MySet edgeset=entry.getValue(); - AllocNode allocnode=entry.getKey(); - if (allocnode==single) { - entryIt.remove(); - } - AllocNode addnode=(allocnode==single)?summary:allocnode; + for(Iterator>> entryIt=delta.baseheapedge.entrySet().iterator(); entryIt.hasNext(); ) { + Map.Entry> entry=entryIt.next(); + MySet edgeset=entry.getValue(); + AllocNode allocnode=entry.getKey(); + if (allocnode==single) { + entryIt.remove(); + } + AllocNode addnode=(allocnode==single)?summary:allocnode; - MySet newset=(MySet) edgeset.clone(); - MySet removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary); - Util.relationUpdate(delta.heapedgeadd, addnode, null, newset); - Util.relationUpdate(delta.heapedgeremove, allocnode, null, removeset); + MySet newset=(MySet)edgeset.clone(); + MySet removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary); + Util.relationUpdate(delta.heapedgeadd, addnode, null, newset); + Util.relationUpdate(delta.heapedgeremove, allocnode, null, removeset); } /* Update Node Ages...If the base or addNodeAges set contains a @@ -1827,17 +1880,17 @@ public class Pointer implements HeapAnalysis{ * need to generate a single node as that has already been * done. */ if (delta.baseNodeAges.contains(single)||delta.addNodeAges.contains(single)) { - delta.addNodeAges.add(summary); + delta.addNodeAges.add(summary); } //Kill the old node if someone tries to add it if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) { - delta.addOldNodes.put(single, Boolean.FALSE); + delta.addOldNodes.put(single, Boolean.FALSE); } - + } //Apply incoming diffs to graph - applyDiffs(graph, delta); + applyDiffs(graph, delta); return delta; } @@ -1846,23 +1899,23 @@ public class Pointer implements HeapAnalysis{ void summarizeSet(MySet edgeset, MySet oldedgeset, AllocNode oldnode, AllocNode sumnode) { MySet newSet=null; - for(Iterator edgeit=edgeset.iterator();edgeit.hasNext();) { + for(Iterator edgeit=edgeset.iterator(); edgeit.hasNext(); ) { Edge e=edgeit.next(); if (e.dst==oldnode||e.src==oldnode) { - if (newSet==null) { - newSet=new MySet(); - } - edgeit.remove(); - e=e.copy(); - - if (e.dst==oldnode) { - e.dst=sumnode; - } - if (e.src==oldnode) { - e.src=sumnode; - } - if (oldedgeset==null||!oldedgeset.contains(e)) - newSet.add(e); + if (newSet==null) { + newSet=new MySet(); + } + edgeit.remove(); + e=e.copy(); + + if (e.dst==oldnode) { + e.dst=sumnode; + } + if (e.src==oldnode) { + e.src=sumnode; + } + if (oldedgeset==null||!oldedgeset.contains(e)) + newSet.add(e); } } if (newSet!=null) @@ -1875,29 +1928,29 @@ public class Pointer implements HeapAnalysis{ MySet shrinkSet(MySet edgeset, MySet oldedgeset, AllocNode oldnode, AllocNode newnode) { MySet newSet=null; MySet removeSet=null; - for(Iterator edgeit=edgeset.iterator();edgeit.hasNext();) { + for(Iterator edgeit=edgeset.iterator(); edgeit.hasNext(); ) { Edge e=edgeit.next(); edgeit.remove(); if (e.dst==oldnode||e.src==oldnode) { - if (newSet==null) { - newSet=new MySet(); - removeSet=new MySet(); - } + if (newSet==null) { + newSet=new MySet(); + removeSet=new MySet(); + } - removeSet.add(e); - e=e.copy(); - if (e.dst==oldnode) - e.dst=newnode; - if (e.src==oldnode) - e.src=newnode; - if (oldedgeset==null||!oldedgeset.contains(e)) - newSet.add(e); + removeSet.add(e); + e=e.copy(); + if (e.dst==oldnode) + e.dst=newnode; + if (e.src==oldnode) + e.src=newnode; + if (oldedgeset==null||!oldedgeset.contains(e)) + newSet.add(e); } } if (newSet!=null) edgeset.addAll(newSet); return removeSet; - } + } /* This function returns a completely new Delta... It is safe to * modify this */ @@ -1915,23 +1968,23 @@ public class Pointer implements HeapAnalysis{ Delta newdelta=new Delta(null, true); //Add in heap edges and throw away original diff - for(Map.Entry> entry:delta.heapedgeadd.entrySet()) { - graph.nodeMap.put(entry.getKey(), new MySet(entry.getValue())); + for(Map.Entry> entry : delta.heapedgeadd.entrySet()) { + graph.nodeMap.put(entry.getKey(), new MySet(entry.getValue())); } //Add in var edges and throw away original diff Set livetemps=bblivetemps.get(block); - for(Map.Entry> entry:delta.varedgeadd.entrySet()) { - if (livetemps.contains(entry.getKey())) - graph.varMap.put(entry.getKey(), new MySet(entry.getValue())); + for(Map.Entry> entry : delta.varedgeadd.entrySet()) { + if (livetemps.contains(entry.getKey())) + graph.varMap.put(entry.getKey(), new MySet(entry.getValue())); } //Record that this is initial set... graph.nodeAges.addAll(delta.addNodeAges); //Add old nodes - for(Map.Entry oldentry:delta.addOldNodes.entrySet()) { - if (oldentry.getValue().booleanValue()) { - graph.oldNodes.put(oldentry.getKey(), Boolean.TRUE); - } + for(Map.Entry oldentry : delta.addOldNodes.entrySet()) { + if (oldentry.getValue().booleanValue()) { + graph.oldNodes.put(oldentry.getKey(), Boolean.TRUE); + } } return newdelta; } else { @@ -1949,41 +2002,41 @@ public class Pointer implements HeapAnalysis{ void mergeHeapEdges(Graph graph, Delta delta, Delta newdelta) { //Merge in edges - for(Map.Entry> heapedge:delta.heapedgeadd.entrySet()) { + for(Map.Entry> heapedge : delta.heapedgeadd.entrySet()) { AllocNode nsrc=heapedge.getKey(); MySet edges=heapedge.getValue(); if (graph.backMap!=null) { - for(Edge e:edges) { - if (!graph.backMap.containsKey(e.dst)) - graph.backMap.put(e.dst, new MySet()); - graph.backMap.get(e.dst).add(e); - } + for(Edge e : edges) { + if (!graph.backMap.containsKey(e.dst)) + graph.backMap.put(e.dst, new MySet()); + graph.backMap.get(e.dst).add(e); + } } if (!graph.nodeMap.containsKey(nsrc)) { - graph.nodeMap.put(nsrc, new MySet()); + graph.nodeMap.put(nsrc, new MySet()); } MySet dstedges=graph.nodeMap.get(nsrc); MySet diffedges=new MySet(); - for(Edge e:edges) { - if (!dstedges.contains(e)) { - //We have a new edge - diffedges.add(e); - dstedges.add(e); - } else { - Edge origedge=dstedges.get(e); - if (!origedge.subsumes(e)) { - Edge mergededge=origedge.merge(e); - diffedges.add(mergededge); - dstedges.add(mergededge); - } - } + for(Edge e : edges) { + if (!dstedges.contains(e)) { + //We have a new edge + diffedges.add(e); + dstedges.add(e); + } else { + Edge origedge=dstedges.get(e); + if (!origedge.subsumes(e)) { + Edge mergededge=origedge.merge(e); + diffedges.add(mergededge); + dstedges.add(mergededge); + } + } } //Done with edge set... if (diffedges.size()>0) { - //completely new - newdelta.baseheapedge.put(nsrc, diffedges); + //completely new + newdelta.baseheapedge.put(nsrc, diffedges); } } } @@ -1994,62 +2047,113 @@ public class Pointer implements HeapAnalysis{ void mergeVarEdges(Graph graph, Delta delta, Delta newdelta, BBlock block) { //Merge in edges Set livetemps=bblivetemps.get(block); - - for(Map.Entry> varedge:delta.varedgeadd.entrySet()) { + + for(Map.Entry> varedge : delta.varedgeadd.entrySet()) { TempDescriptor tmpsrc=varedge.getKey(); if (livetemps.contains(tmpsrc)) { - MySet edges=varedge.getValue(); - if (graph.backMap!=null) { - for(Edge e:edges) { - if (!graph.backMap.containsKey(e.dst)) - graph.backMap.put(e.dst, new MySet()); - graph.backMap.get(e.dst).add(e); - } - } - - if (!graph.varMap.containsKey(tmpsrc)) { - graph.varMap.put(tmpsrc, new MySet()); - } - MySet dstedges=graph.varMap.get(tmpsrc); - MySet diffedges=new MySet(); - for(Edge e:edges) { - if (!dstedges.contains(e)) { - //We have a new edge - diffedges.add(e); - dstedges.add(e); - } else { - Edge origedge=dstedges.get(e); - if (!origedge.subsumes(e)) { - Edge mergededge=origedge.merge(e); - diffedges.add(mergededge); - dstedges.add(mergededge); - } - } - } - //Done with edge set... - if (diffedges.size()>0) { - //completely new - newdelta.basevaredge.put(tmpsrc,diffedges); - } + MySet edges=varedge.getValue(); + if (graph.backMap!=null) { + for(Edge e : edges) { + if (!graph.backMap.containsKey(e.dst)) + graph.backMap.put(e.dst, new MySet()); + graph.backMap.get(e.dst).add(e); + } + } + + if (!graph.varMap.containsKey(tmpsrc)) { + graph.varMap.put(tmpsrc, new MySet()); + } + MySet dstedges=graph.varMap.get(tmpsrc); + MySet diffedges=new MySet(); + for(Edge e : edges) { + if (!dstedges.contains(e)) { + //We have a new edge + diffedges.add(e); + dstedges.add(e); + } else { + Edge origedge=dstedges.get(e); + if (!origedge.subsumes(e)) { + Edge mergededge=origedge.merge(e); + diffedges.add(mergededge); + dstedges.add(mergededge); + } + } + } + //Done with edge set... + if (diffedges.size()>0) { + //completely new + newdelta.basevaredge.put(tmpsrc,diffedges); + } } } } void mergeAges(Graph graph, Delta delta, Delta newDelta) { //Merge in edges - for(AllocNode node:delta.addNodeAges) { + for(AllocNode node : delta.addNodeAges) { if (!graph.nodeAges.contains(node)) { - graph.nodeAges.add(node); - newDelta.baseNodeAges.add(node); + graph.nodeAges.add(node); + newDelta.baseNodeAges.add(node); } } - for(Map.Entry oldentry:delta.addOldNodes.entrySet()) { + for(Map.Entry oldentry : delta.addOldNodes.entrySet()) { AllocNode node=oldentry.getKey(); boolean ispresent=oldentry.getValue().booleanValue(); if (ispresent&&!graph.oldNodes.containsKey(node)) { - graph.oldNodes.put(node, Boolean.TRUE); - newDelta.baseOldNodes.put(node, Boolean.TRUE); + graph.oldNodes.put(node, Boolean.TRUE); + newDelta.baseOldNodes.put(node, Boolean.TRUE); } } } -} \ No newline at end of file + + + + + public Alloc getCmdLineArgsAlloc() { + return null; + } + public Alloc getCmdLineArgAlloc() { + return null; + } + public Alloc getCmdLineArgBytesAlloc() { + return null; + } + public Alloc getNewStringLiteralAlloc() { + return null; + } + public Alloc getNewStringLiteralBytesAlloc() { + return null; + } + + public Set canPointToAt( TempDescriptor x, + FlatNode programPoint ) { + return null; + } + + public Hashtable< Alloc, Set > canPointToAt( TempDescriptor x, + FieldDescriptor f, + FlatNode programPoint ) { + return null; + } + + public Hashtable< Alloc, Set > canPointToAtElement( TempDescriptor x, + FlatNode programPoint ) { + return null; + } + + public Set canPointToAfter( TempDescriptor x, + FlatNode programPoint ) { + return null; + } + + public Hashtable< Alloc, Set > canPointToAfter( TempDescriptor x, + FieldDescriptor f, + FlatNode programPoint ) { + return null; + } + + public Hashtable< Alloc, Set > canPointToAfterElement( TempDescriptor x, // x[i] + FlatNode programPoint ) { + return null; + } +}