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=af03fdf74ddff960d677beac76491170dc914544;hb=2c9fc049afee82726ae47ec7ea2630cfe1623f21;hpb=1b4be9f805f681f73e5d1b6446e8048004bd9c32 diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index af03fdf7..184cf651 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -2,28 +2,62 @@ package Analysis.Pointer; import java.util.*; import IR.Flat.*; import IR.*; +import Analysis.Liveness; import Analysis.Pointer.BasicBlock.BBlock; import Analysis.Pointer.AllocFactory.AllocNode; +import Analysis.Disjoint.Alloc; +import Analysis.Disjoint.Taint; +import Analysis.Disjoint.TaintSet; +import Analysis.Disjoint.Canonical; +import Analysis.Disjoint.HeapAnalysis; +import Analysis.CallGraph.CallGraph; +import Analysis.OoOJava.RBlockRelationAnalysis; +import Analysis.OoOJava.Accessible; +import Analysis.Disjoint.ExistPred; +import Analysis.Disjoint.ReachGraph; +import Analysis.Disjoint.EffectsAnalysis; +import Analysis.Disjoint.BuildStateMachines; import java.io.*; -public class Pointer { + +public class Pointer implements HeapAnalysis { HashMap blockMap; HashMap bbgraphMap; HashMap graphMap; HashMap> callMap; HashMap> returnMap; + HashMap> bblivetemps; + HashSet mustProcess; + private boolean OoOJava=false; + CallGraph callGraph; State state; TypeUtil typeUtil; AllocFactory allocFactory; LinkedList toprocess; TempDescriptor returntmp; - int plotcount=0; + RBlockRelationAnalysis taskAnalysis; + EffectsAnalysis effectsAnalysis; + Accessible accessible; + + public Pointer(State state, TypeUtil typeUtil, CallGraph callGraph, RBlockRelationAnalysis taskAnalysis, Liveness liveness, BuildStateMachines bsm) { + this(state, typeUtil); + this.callGraph=callGraph; + this.OoOJava=true; + this.taskAnalysis=taskAnalysis; + this.effectsAnalysis=new EffectsAnalysis(); + effectsAnalysis.state=state; + effectsAnalysis.buildStateMachines=bsm; + accessible=new Accessible(state, callGraph, taskAnalysis, liveness); + accessible.doAnalysis(); + State.logEvent("Done Writing Accessible Analysis"); + } public Pointer(State state, TypeUtil typeUtil) { this.state=state; this.blockMap=new HashMap(); this.bbgraphMap=new HashMap(); + this.bblivetemps=new HashMap>(); this.graphMap=new HashMap(); this.callMap=new HashMap>(); this.returnMap=new HashMap>(); @@ -32,14 +66,33 @@ public class Pointer { this.toprocess=new LinkedList(); ClassDescriptor stringcd=typeUtil.getClass(TypeUtil.ObjectClass); this.returntmp=new TempDescriptor("RETURNVAL", stringcd); + this.mustProcess=new HashSet(); + } + + public EffectsAnalysis getEffectsAnalysis() { + return effectsAnalysis; } public BasicBlock getBBlock(FlatMethod fm) { - if (!blockMap.containsKey(fm)) + if (!blockMap.containsKey(fm)) { blockMap.put(fm, BasicBlock.getBBlock(fm)); + 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); @@ -56,65 +109,121 @@ public class Pointer { return delta; } + + public Graph getGraph(FlatNode fn) { + return graphMap.get(fn); + } + public void doAnalysis() { + toprocess.add(buildInitialContext()); +nextdelta: while(!toprocess.isEmpty()) { Delta delta=toprocess.remove(); PPoint ppoint=delta.getBlock(); BBlock bblock=ppoint.getBBlock(); Vector nodes=bblock.nodes(); int startindex=0; - System.out.println("BB BEGIN"); - delta.print(); if (ppoint.getIndex()==-1) { - //Build base graph for entrance to this basic block - System.out.println("INIT"); - delta=applyInitDelta(delta, bblock); + //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("CALL"); - startindex=ppoint.getIndex()+1; - delta=applyCallDelta(delta, bblock); + //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(); } Graph graph=bbgraphMap.get(bblock); Graph nodeGraph=null; + + 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(); + } generateFinalDelta(bblock, delta, nodeGraph); } //DEBUG - int debugindex=0; - for(Map.Entry e:bbgraphMap.entrySet()) { - Graph g=e.getValue(); - plotGraph(g,"BB"+debugindex); - debugindex++; - } + 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:graphMap.entrySet()) { - FlatNode fn=e.getKey(); - Graph g=e.getValue(); - plotGraph(g,"FN"+fn.toString()+debugindex); - debugindex++; + 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(FlatMethod fm:blockMap.keySet()) { - fm.printMethod(); + + 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"); + } } } @@ -127,7 +236,7 @@ public class Pointer { ex.printStackTrace(); } } - + /* This function builds the last delta for a basic block. It * handles the case for the first time the basic block is @@ -138,47 +247,44 @@ public class Pointer { 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.nodeAges.contains(node)) - newDelta.addNodeAges.add(node); - else if (graph.parent.nodeAges.contains(node)) - newDelta.addNodeAges.add(node); /* 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); } /* This function build the delta for the exit of a basic block. */ @@ -193,18 +299,17 @@ public class Pointer { HashSet tmpSet=new HashSet(); tmpSet.addAll(delta.basevaredge.keySet()); tmpSet.addAll(delta.varedgeadd.keySet()); - System.out.println(tmpSet); - 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(); @@ -213,26 +318,26 @@ public class Pointer { 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); - - 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); - - /* 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); - } + 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); + + /* 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); + } } /* Compute new ages */ @@ -243,80 +348,292 @@ public class Pointer { /* 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); + } + } } } - System.out.println("FINAL"); - newDelta.print(); + + 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)) { - 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); + } + } + } 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); + } + } + } + + + applyDiffs(graph, delta); + return delta; + } + + private boolean isRecursive(FlatSESEEnterNode sese) { + MethodDescriptor md=sese.getmdEnclosing(); + boolean isrecursive=callGraph.getCalleeSet(md).contains(md); + return isrecursive; + } + + Delta processSESEExitNode(FlatSESEExitNode seseexit, Delta delta, Graph graph) { + if (!OoOJava) + return processFlatNop(seseexit, delta, graph); + FlatSESEEnterNode sese=seseexit.getFlatEnter(); + //Strip Taints from this SESE + if (delta.getInit()) { + removeInitTaints(isRecursive(sese)?null:sese, delta, graph); + } else { + removeDiffTaints(isRecursive(sese)?null:sese, delta); + } + 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); + //Process delta edges + processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd); + for(Edge e : edgestoremove) { + delta.removeVarEdge(e); + } + for(Edge e : edgestoadd) { + delta.addVarEdge(e); + } + } + + //Now do heap edges + { + MySet edgestoadd=new MySet(); + MySet edgestoremove=new MySet(); + + //Process base diff edges + 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); + } + for(Edge e : edgestoadd) { + delta.addHeapEdge(e); + } + } + } + + void removeInitTaints(FlatSESEEnterNode sese, Delta delta, Graph graph) { + //Start with variable edges + { + 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); + //Process delta edges + processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd); + for(Edge e : edgestoremove) { + delta.removeVarEdge(e); + } + for(Edge e : edgestoadd) { + delta.addVarEdge(e); + } + } + + //Now do heap edges + { + MySet edgestoadd=new MySet(); + MySet edgestoremove=new MySet(); + + //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); + //Process delta edges + processEdgeMap(sese, delta.heapedgeadd, null, null, edgestoremove, edgestoadd); + for(Edge e : edgestoremove) { + delta.removeHeapEdge(e); + } + for(Edge e : edgestoadd) { + delta.addHeapEdge(e); + } + } + } + + void processEdgeMap(FlatSESEEnterNode sese, HashMap> edgemap, HashMap> childmap, HashMap> removemap, MySet edgestoremove, MySet edgestoadd) { + 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; + 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&&newts!=ts) { + edgestoremove.add(e); + edgestoadd.add(e.changeTaintSet(newts)); + } + } } } @@ -327,21 +644,21 @@ public class Pointer { //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); + } } } } @@ -350,16 +667,16 @@ public class Pointer { 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); + } } } } @@ -367,33 +684,36 @@ public class Pointer { /* 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); - newDelta.heapedgeadd.put(node, 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) { TempDescriptor tmpthis=fcall.getThis(); MethodDescriptor md=fcall.getMethod(); HashSet targets=new HashSet(); - if (md.isStatic()) { + if (md.isStatic()||fcall.getSuper()) { 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 - targets.add(cd.getCalledMethod(md)); + 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; @@ -403,81 +723,88 @@ public class Pointer { 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())); - 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())); - 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())); - 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); } } } - /* This function computes all edges that start outside of the callee context and go into the callee context */ + /* This function computes all edges that start outside of the callee + * context and go into the callee context */ void computeExternalEdges(Graph graph, Delta delta, HashSet nodeset, HashSet deltaset, MySet externaledgeset) { //Do heap edges first @@ -487,55 +814,56 @@ public class Pointer { 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); } } - //Do heap edges first + //Do var edges now HashSet temps=new HashSet(); temps.addAll(delta.basevaredge.keySet()); temps.addAll(delta.varedgeadd.keySet()); 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(Delta delta, HashSet nodeset, MySet edgeset, MySet externaledgeset) { + + void removeEdges(Graph graph, Delta delta, HashSet nodeset, MySet edgeset, MySet externaledgeset) { //Want to remove the set of internal edges - for(Edge e:edgeset) { - if (e.src!=null) { - delta.removeHeapEdge(e); + for(Edge e : edgeset) { + if (e.src!=null&&!graph.callerEdges.contains(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 - delta.removeEdge(e); + if (!graph.callerEdges.contains(e)) + delta.removeEdge(e); } } @@ -549,35 +877,39 @@ public class Pointer { HashSet targetSet=new HashSet(); Stack tovisit=new Stack(); TempDescriptor tmpthis=fcall.getThis(); + graph.callerEdges=new MySet(); //Handle the this temp processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, null); //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); //Compute call targets - HashSet targets=computeTargets(fcall, newDelta); + HashSet newtargets=computeTargets(fcall, newDelta); //Fix mapping - fixMapping(fcall, targets, null, newDelta, callblock, callindex); + fixMapping(fcall, newtargets, null, newDelta, callblock, callindex); //Compute edges into region to splice out computeExternalEdges(graph, delta, nodeset, null, externaledgeset); //Splice out internal edges - removeEdges(delta, nodeset, edgeset, externaledgeset); + removeEdges(graph, delta, nodeset, edgeset, externaledgeset); //store data structures graph.externalEdgeSet=externaledgeset; graph.reachNode=nodeset; graph.reachEdge=edgeset; - + + graph.callTargets=newtargets; graph.callNodeAges=new HashSet(); graph.callOldNodes=new HashSet(); + graph.callNewEdges=new HashMap>(); + graph.callOldEdges=new HashMap>(); //Apply diffs to graph applyDiffs(graph, delta, true); @@ -591,51 +923,206 @@ public class Pointer { HashSet targetSet=new HashSet(); 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(); + } + } + + //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(); + } + } //Handle the this temp processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, oldnodeset); //Go through each temp processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, true); - //Go through each new heap edge that starts from old node MySet newedges=GraphManip.getDiffEdges(delta, oldnodeset); edgeset.addAll(newedges); - for(Edge e:newedges) { - 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 computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, oldnodeset); - //Compute call targets - HashSet targets=computeTargets(fcall, newDelta); + HashSet newtargets=computeTargets(fcall, newDelta); + graph.callTargets.addAll(newtargets); //add in new nodeset and edgeset oldnodeset.addAll(nodeset); oldedgeset.addAll(edgeset); - //Fix mapping - fixMapping(fcall, targets, oldedgeset, newDelta, callblock, callindex); - + fixMapping(fcall, graph.callTargets, oldedgeset, newDelta, callblock, callindex); //Compute edges into region to splice out computeExternalEdges(graph, delta, oldnodeset, nodeset, externaledgeset); //Splice out internal edges - removeEdges(delta, nodeset, edgeset, externaledgeset); + removeEdges(graph, delta, nodeset, edgeset, externaledgeset); + + //Add external edges back in + processCallExternal(graph, delta, externaledgeset); + + //Move new edges that should be summarized + processSummarization(graph, delta); + + 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); + } + } + } //Add in new external edges graph.externalEdgeSet.addAll(externaledgeset); - //Apply diffs to graph applyDiffs(graph, delta); } return delta; } + void processSummarization(Graph graph, Delta delta) { + processSumHeapEdgeSet(delta.heapedgeadd, delta, graph); + processSumHeapEdgeSet(delta.baseheapedge, delta, graph); + processSumVarEdgeSet(delta.varedgeadd, delta, graph); + processSumVarEdgeSet(delta.basevaredge, delta, graph); + } + + void processSumVarEdgeSet(HashMap> map, Delta delta, Graph graph) { + MySet edgestoadd=new MySet(); + MySet edgestoremove=new MySet(); + 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 : edgestoremove) { + if (!graph.callerEdges.contains(e)) + delta.removeVarEdge(e); + } + 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(); ) { + 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) { + if (!graph.callerEdges.contains(e)) + delta.removeHeapEdge(e); + } + for(Edge e : edgestoadd) { + delta.addHeapEdge(e); + } + } + + //Handle external edges + void processCallExternal(Graph graph, Delta newDelta, MySet externalEdgeSet) { + //Add external edges in + 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; + } + //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); + } else { + //Add edge to single node + mergeEdge(graph, newDelta, newedge); + } + } + } + /* This function applies callee deltas to the caller heap. */ Delta applyCallDelta(Delta delta, BBlock bblock) { @@ -645,87 +1132,139 @@ public class Pointer { 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); - } else { - nodeit.remove(); + 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); + /* 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) { - edgetoadd=e; - } else { - Edge origEdgeKey=e.makeStatus(allocFactory); - if (oldgraph.nodeMap.containsKey(origEdgeKey.src)&& - oldgraph.nodeMap.get(origEdgeKey.src).contains(origEdgeKey)) { - Edge origEdge=oldgraph.nodeMap.get(origEdgeKey.src).get(origEdgeKey); - //copy the predicate - origEdgeKey.statuspredicate=origEdge.statuspredicate; - edgetoadd=origEdgeKey; - } - } - mergeEdge(graph, newDelta, edgetoadd); - } - } - //Add external edges in - for(Edge e:graph.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; - } - //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); - mergeEdge(graph, newDelta, newedge); - } else { - //Add edge to single node - mergeEdge(graph, newDelta, newedge); + 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) { - Edge newedge=e.copy(); - newedge.srcvar=fcall.getReturnTemp(); - if (graph.getEdges(fcall.getReturnTemp())==null||!graph.getEdges(fcall.getReturnTemp()).contains(newedge)) - newDelta.addEdge(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); + } + } + } + + /* This is a call produced edge...need to remember this */ + + public void mergeCallEdge(Graph graph, Delta newDelta, Edge edgetoadd) { + if (edgetoadd!=null) { + 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); } } } @@ -738,22 +1277,24 @@ public class Pointer { //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); - mergeEdge(graph, newDelta, rewrite); + 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); - Edge rewrite=match.rewrite(singleNode, summaryNode); - newDelta.removeEdge(match); - mergeEdge(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); + } } } } @@ -767,115 +1308,148 @@ public class Pointer { 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()); } - graph.nodeMap.get(node).addAll(edgestoadd); + 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(); - graph.varMap.put(tmp, (MySet) edgestoadd.clone()); + if (graph.varMap.containsKey(tmp)) { + 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); + } else + 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); } } + boolean isINACC(FlatNode node) { + if (!OoOJava) + return false; + switch(node.kind()) { + case FKind.FlatSetFieldNode: { + 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()); + } + } + return false; + } + Delta processSetFieldElementNode(FlatNode node, Delta delta, Graph graph) { TempDescriptor src; FieldDescriptor fd; @@ -891,56 +1465,106 @@ public class Pointer { fd=ffn.getField(); dst=ffn.getDst(); } + if (delta.getInit()) { - HashSet srcNodes=GraphManip.getNodes(graph, delta, src); - HashSet dstNodes=GraphManip.getNodes(graph, delta, dst); - MySet edgesToAdd=GraphManip.genEdges(dstNodes, fd, srcNodes); + 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); + } + if (OoOJava) { + effectsAnalysis.analyzeFlatSetFieldNode(dstEdges, fd, node); + } + + //Do nothing for non pointers + if (!src.getType().isPtr()) { + 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); + } + + MySet edgesToAdd=GraphManip.genEdges(dstEdges, fd, srcEdges); MySet edgesToRemove=null; - if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()&&fd!=null) { - /* Can do a strong update */ - edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd); - graph.strongUpdateSet=edgesToRemove; + 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; } else - graph.strongUpdateSet=new MySet(); + graph.strongUpdateSet=new MySet(); + /* Update diff */ updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove); applyDiffs(graph, delta); } else { - /* First look at new sources */ + 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); + } + + if (OoOJava) { + effectsAnalysis.analyzeFlatSetFieldNode(newDstEdges, fd, node); + } + + if (!src.getType().isPtr()) { + if (mustProcess.contains(node)) { + applyDiffs(graph, delta); + } + return delta; + } + + /* Next look at new sources */ + MySet edgesToAdd=new MySet(); - HashSet newSrcNodes=GraphManip.getDiffNodes(delta, src); - HashSet srcNodes=GraphManip.getNodes(graph, delta, src); + MySet newSrcEdges=GraphManip.getDiffEdges(delta, src); + MySet srcEdges=GraphManip.getEdges(graph, delta, src); HashSet dstNodes=GraphManip.getNodes(graph, delta, dst); - HashSet newDstNodes=GraphManip.getDiffNodes(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); + } MySet edgesToRemove=null; - if (newDstNodes.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&&newDstNodes.size()==1&&!newDstNodes.iterator().next().isSummary()&&graph.strongUpdateSet!=null&&fd!=null) { - edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd); - graph.strongUpdateSet.addAll(edgesToRemove); - } - edgesToAdd.addAll(GraphManip.genEdges(newDstNodes, fd, srcNodes)); + 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)); } //Kill new edges if (graph.strongUpdateSet!=null&&fd!=null) { - MySet otherEdgesToRemove=GraphManip.getDiffEdges(delta, dstNodes); - 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 - edgesToAdd.addAll(GraphManip.genEdges(dstNodes, fd, newSrcNodes)); + Edge.mergeEdgesInto(edgesToAdd, GraphManip.genEdges(dstNodes, fd, newSrcEdges)); /* Update diff */ updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove); @@ -952,6 +1576,7 @@ public class Pointer { Delta processCopyNode(FlatNode node, Delta delta, Graph graph) { TempDescriptor src; TempDescriptor dst; + if (node.kind()==FKind.FlatOpNode) { FlatOpNode fon=(FlatOpNode) node; src=fon.getLeft(); @@ -961,9 +1586,9 @@ public class Pointer { 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; @@ -971,20 +1596,20 @@ public class Pointer { dst=fcn.getDst(); } if (delta.getInit()) { - HashSet srcnodes=GraphManip.getNodes(graph, delta, src); - MySet edgesToAdd=GraphManip.genEdges(dst, srcnodes); + MySet srcedges=GraphManip.getEdges(graph, delta, src); + MySet edgesToAdd=GraphManip.genEdges(dst, srcedges); MySet edgesToRemove=GraphManip.getEdges(graph, delta, dst); updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove); applyDiffs(graph, delta); } else { /* First compute new src nodes */ - HashSet newSrcNodes=GraphManip.getDiffNodes(delta, src); + MySet newSrcEdges=GraphManip.getDiffEdges(delta, src); /* Compute the union, and then the set of edges */ - MySet edgesToAdd=GraphManip.genEdges(dst, newSrcNodes); - + 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); @@ -997,6 +1622,8 @@ public class Pointer { TempDescriptor src; FieldDescriptor fd; TempDescriptor dst; + TaintSet taint=null; + if (node.kind()==FKind.FlatElementNode) { FlatElementNode fen=(FlatElementNode) node; src=fen.getSrc(); @@ -1008,83 +1635,132 @@ public class Pointer { fd=ffn.getField(); dst=ffn.getDst(); } + if (OoOJava&&!accessible.isAccessible(node, src)) { + taint=TaintSet.factory(Taint.factory(node, src, AllocFactory.dummySite, null, ReachGraph.predsEmpty)); + } + + //Do nothing for non pointers if (delta.getInit()) { - HashSet srcnodes=GraphManip.getNodes(graph, delta, src); - HashSet fdnodes=GraphManip.getNodes(graph, delta, srcnodes, fd); - MySet edgesToAdd=GraphManip.genEdges(dst, fdnodes); + 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 (!dst.getType().isPtr()) { + if (mustProcess.contains(node)) { + applyDiffs(graph, delta); + } + return delta; + } + + MySet edgesToAdd=GraphManip.dereference(graph, delta, dst, srcedges, fd, node); MySet edgesToRemove=GraphManip.getEdges(graph, delta, dst); + updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove); applyDiffs(graph, delta); } 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 (!dst.getType().isPtr()) { + if (mustProcess.contains(node)) { + applyDiffs(graph, delta); + } + return delta; + } /* First compute new objects we read fields of */ - HashSet allsrcnodes=GraphManip.getNodes(graph, delta, src); - HashSet difffdnodes=GraphManip.getDiffNodes(delta, allsrcnodes, fd); + MySet allsrcedges=GraphManip.getEdges(graph, delta, src); + MySet edgesToAdd=GraphManip.diffDereference(delta, dst, allsrcedges, fd, node); /* Next compute new targets of fields */ - HashSet newsrcnodes=GraphManip.getDiffNodes(delta, src); - HashSet newfdnodes=GraphManip.getNodes(graph, delta, newsrcnodes, fd); + MySet newfdedges=GraphManip.dereference(graph, delta, dst, newsrcedges, fd, node); + /* Compute the union, and then the set of edges */ - HashSet newTargets=new HashSet(); - newTargets.addAll(newfdnodes); - newTargets.addAll(difffdnodes); - MySet edgesToAdd=GraphManip.genEdges(dst, newTargets); - + 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); } + return delta; } - static void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, MySet edgestoAdd, MySet edgestoRemove) { + void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, MySet edgestoAdd, MySet edgestoRemove) { MySet edgeAdd=delta.varedgeadd.get(tmp); MySet edgeRemove=delta.varedgeremove.get(tmp); MySet existingEdges=graph.getEdges(tmp); - 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) { + 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) { //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 (!existingEdges.contains(e)) - delta.addVarEdge(e); + 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)); + } + } + } } } - static void updateHeapDelta(Graph graph, Delta delta, MySet edgestoAdd, MySet edgestoRemove) { + 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 - 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)||!existingEdges.get(e).isNew()) { - delta.addHeapEdge(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)); + } + } } } @@ -1092,7 +1768,7 @@ public class Pointer { 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); @@ -1112,86 +1788,91 @@ public class Pointer { //Add it into the diffs delta.varedgeadd.put(tmp, newedges); //Remove the old edges - delta.varedgeremove.put(tmp, (MySet) graph.getEdges(tmp).clone()); - //Apply incoming diffs to graph - applyDiffs(graph, delta); + MySet oldedges=graph.getEdges(tmp); + if (!oldedges.isEmpty()) + 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(); - - 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); - } + 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); + } } - + /* 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 { - /* 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); - } + 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; - - 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); + 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); } /* Update Node Ages...If the base or addNodeAges set contains a @@ -1199,17 +1880,18 @@ public class Pointer { * 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); + } + //Apply incoming diffs to graph + applyDiffs(graph, delta); + return delta; } @@ -1217,23 +1899,23 @@ public class Pointer { 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) @@ -1246,28 +1928,29 @@ public class Pointer { 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(); - } - - removeSet.add(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) { + 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); } } if (newSet!=null) edgeset.addAll(newSet); return removeSet; - } + } /* This function returns a completely new Delta... It is safe to * modify this */ @@ -1279,32 +1962,39 @@ public class Pointer { bbgraphMap.put(block, new Graph(null)); newGraph=true; } - Delta newdelta; Graph graph=bbgraphMap.get(block); if (newGraph) { - newdelta=new Delta(null, true); + Delta newdelta=new Delta(null, true); //Add in heap edges and throw away original diff - graph.nodeMap.putAll(delta.heapedgeadd); + + 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 - graph.varMap.putAll(delta.varedgeadd); + 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())); + } //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 { - newdelta=new Delta(null, false); + Delta newdelta=new Delta(null, false); //merge in heap edges and variables mergeHeapEdges(graph, delta, newdelta); - mergeVarEdges(graph, delta, newdelta); + mergeVarEdges(graph, delta, newdelta, block); mergeAges(graph, delta, newdelta); + return newdelta; } - - return newdelta; } /* This function merges in the heap edges. It updates delta to be @@ -1312,41 +2002,41 @@ public class Pointer { 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); } } } @@ -1354,54 +2044,116 @@ public class Pointer { /* This function merges in the var edges. It updates delta to be * the difference */ - void mergeVarEdges(Graph graph, Delta delta, Delta newdelta) { + void mergeVarEdges(Graph graph, Delta delta, Delta newdelta, BBlock block) { //Merge in edges - for(Map.Entry> varedge:delta.varedgeadd.entrySet()) { - TempDescriptor tmpsrc=varedge.getKey(); - 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); - } - } + Set livetemps=bblivetemps.get(block); - 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); - } - } - //Done with edge set... - if (diffedges.size()>0) { - //completely new - newdelta.basevaredge.put(tmpsrc,diffedges); + 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); + } } } } 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; + } +}