X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FPointer%2FPointer.java;h=8b0ce00bfac302c3987be65ed739192fd9236ab1;hp=aae36b2c636489ca0f97c2794c379cccf5f164bc;hb=b124b7bf09a5eed6e272119acba9cfc5a1374b60;hpb=b4dcf05f9bd8d277bcdf3dbe87f7894dcd920bbc diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index aae36b2c..8b0ce00b 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -2,26 +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; - -public class Pointer { +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 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; + 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>(); @@ -30,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); @@ -47,80 +102,193 @@ public class Pointer { MySet arrayset=new MySet(); MySet varset=new MySet(); Edge arrayedge=new Edge(allocFactory.StringArray, null, allocFactory.Strings); - arrayset.add(arrayedge); Edge stringedge=new Edge(fm.getParameter(0), allocFactory.StringArray); - varset.add(stringedge); - delta.heapedgeadd.put(allocFactory.StringArray, arrayset); - delta.varedgeadd.put(fm.getParameter(0), varset); + delta.addHeapEdge(arrayedge); + delta.addVarEdge(stringedge); + return delta; } + + public Graph getGraph(FlatNode fn) { + return graphMap.get(fn); + } + public void doAnalysis() { - toprocess.add(buildInitialContext()); + 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; + + 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(); + } else { + //System.out.println("Processing Call "+bblock.nodes.get(ppoint.getIndex()).toString().replace(' ','_')); + //delta.print(); - //Build base graph for entrance to this basic block - delta=applyInitDelta(delta, bblock); + 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=0; 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 + 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(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++; + } + } + + 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"); + } + } } + void plotGraph(Graph g, String name) { + try { + PrintWriter pw=new PrintWriter(new FileWriter(name.toString().replace(' ','_')+".dot")); + g.printGraph(pw, name); + pw.close(); + } catch (Exception ex) { + ex.printStackTrace(); + } + } + + + /* This function builds the last delta for a basic block. It + * handles the case for the first time the basic block is + * evaluated.*/ + void buildInitDelta(Graph graph, Delta newDelta) { //First compute the set of temps 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); + if (graph.oldNodes.containsKey(node)) { + 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); + } } + + newDelta.addNodeAges.addAll(graph.nodeAges); + newDelta.addNodeAges.addAll(graph.parent.nodeAges); } + /* This function build the delta for the exit of a basic block. */ + void generateFinalDelta(BBlock bblock, Delta delta, Graph graph) { Delta newDelta=new Delta(null, false); if (delta.getInit()) { @@ -131,241 +299,618 @@ public class Pointer { 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 */ - 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(); /* Next we build heap edges */ HashSet nodeSet=new HashSet(); 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=(MySet) delta.baseheapedge.get(node).clone(); - /* Remove the remove set */ - newheapedge.removeAll(delta.heapedgeremove.get(node)); - /* Add in the add set */ - newheapedge.addAll(delta.heapedgeadd.get(node)); - newDelta.heapedgeadd.put(node, newheapedge); - - /* Also need to subtract off some edges */ - MySet removeset=delta.heapedgeremove.get(node); - - /* Remove the newly created edges..no need to propagate a diff for those */ - 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 */ newDelta.addNodeAges.addAll(delta.baseNodeAges); newDelta.addNodeAges.addAll(delta.addNodeAges); + HashSet oldNodes=new HashSet(); + + /* 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); + } + } + } + } + + 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()) { + if (!newDelta.heapedgeadd.isEmpty()||!newDelta.heapedgeremove.isEmpty()||!newDelta.varedgeadd.isEmpty()||!newDelta.addNodeAges.isEmpty()||!newDelta.addOldNodes.isEmpty()) { /* We have a delta to propagate */ - 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)); + } + } + } + } + + /* This function compute the edges for the this variable for a + * callee if it exists. */ void processThisTargets(HashSet targetSet, Graph graph, Delta delta, Delta newDelta, HashSet nodeset, Stack tovisit, MySet edgeset, TempDescriptor tmpthis, HashSet oldnodeset) { //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); + } } } } + /* This function compute the edges for a call's parameters. */ + 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); + } } } } + /* 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; } + void fixMapping(FlatCall fcall, HashSet targets, MySet oldedgeset, Delta newDelta, BBlock callblock, int callindex) { + Delta basedelta=null; + TempDescriptor tmpthis=fcall.getThis(); + + 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++)); + } + for(int i=0; i()); + } + + 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))); + } + } + } + } + + 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); + } 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); + } 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); + } + } + } + + + /* 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 + HashSet externalnodes=new HashSet(); + externalnodes.addAll(delta.baseheapedge.keySet()); + externalnodes.addAll(delta.heapedgeadd.keySet()); + externalnodes.addAll(delta.heapedgeremove.keySet()); + //remove allinternal nodes + externalnodes.removeAll(nodeset); + 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); + } + } + + //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) { + //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); + } + } + } + + /* 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) { + if (e.src!=null&&!graph.callerEdges.contains(e)) { + delta.removeHeapEdge(e); + } + } + + //Want to remove the set of external edges + for(Edge e : externaledgeset) { + //want to remove the set of internal edges + if (!graph.callerEdges.contains(e)) + delta.removeEdge(e); + } + } + Delta processFlatCall(BBlock callblock, int callindex, FlatCall fcall, Delta delta, Graph graph) { Delta newDelta=new Delta(null, false); if (delta.getInit()) { MySet edgeset=new MySet(); + MySet externaledgeset=new MySet(); HashSet nodeset=new HashSet(); 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 - for(MethodDescriptor calledmd:targets) { - FlatMethod fm=state.getMethodFlat(calledmd); - - //Build tmpMap - HashMap tmpMap=new HashMap(); - int offset=0; - if(tmpthis!=null) { - tmpMap.put(tmpthis, fm.getParameter(offset++)); - } - for(int i=0;i()); - } - callMap.get(fcall).add(block.getStart()); - - //If we have an existing exit, build delta - Delta returnDelta=null; - - //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); - buildInitDelta(bbgraphMap.get(block.getExit()), 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))); - } - } - } - } + 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(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); + applyDiffs(graph, delta, true); } else { MySet edgeset=new MySet(); + MySet externaledgeset=new MySet(); HashSet nodeset=new HashSet(); MySet oldedgeset=graph.reachEdge; HashSet oldnodeset=graph.reachNode; @@ -373,172 +918,531 @@ 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); - Delta basedelta=null; - //Fix mapping - for(MethodDescriptor calledmd:targets) { - FlatMethod fm=state.getMethodFlat(calledmd); - boolean newmethod=false; - - //Get basicblock for the method - BasicBlock block=getBBlock(fm); - - //Hook up exits - if (!callMap.containsKey(fcall)) { - 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 exits - 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); - buildInitDelta(bbgraphMap.get(block.getExit()), 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))); - } - } - } - } - - //Build tmpMap - HashMap tmpMap=new HashMap(); - int offset=0; - if(tmpthis!=null) { - tmpMap.put(tmpthis, fm.getParameter(offset++)); - } - for(int i=0;i 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) { + Delta newDelta=new Delta(null, false); + Vector nodes=bblock.nodes(); + PPoint ppoint=delta.getBlock(); + 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)); + Set seseCallers=OoOJava?taskAnalysis.getTransitiveExecutingRBlocks(fcall):null; + + //Age outside nodes if necessary + 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); + } + AllocNode summaryAdd=null; + if (!graph.reachNode.contains(node)&&!node.isSummary()) { + /* 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); + } + } + + 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); + } + } + 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); + } + } + } + + /* 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); + } + } + } + + + /* Summarizes out of context nodes in graph */ + void summarizeInGraph(Graph graph, Delta newDelta, AllocNode singleNode) { + AllocNode summaryNode=allocFactory.getAllocNode(singleNode, true); + + //Handle outgoing heap edges + MySet edgeset=graph.getEdges(singleNode); + + 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) { + 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); + } + } + } + } + void applyDiffs(Graph graph, Delta delta) { + applyDiffs(graph, delta, false); + } + + void applyDiffs(Graph graph, Delta delta, boolean genbackwards) { + //build backwards map if requested + 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); + } + } + } + } + //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); - 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 - graph.nodeMap.put(node, (MySet)graph.parent.nodeMap.get(node).clone()); + //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); + } } - graph.nodeMap.get(node).addAll(edgestoadd); } //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); - } else { - //Generate diff from parent graph - MySet parentedges=graph.parent.varMap.get(tmp); - MySet newedgeset=Util.setSubtract(parentedges, edgestoremove); - graph.varMap.put(tmp, newedgeset); + //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); } } //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); + } + } } //Add node additions - for(AllocNode node:delta.addNodeAges) { + for(AllocNode node : delta.addNodeAges) { graph.nodeAges.add(node); } + + 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) { @@ -556,39 +1460,107 @@ 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(srcNodes, fd, dstNodes); - MySet edgesToRemove=null; - if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()) { - /* Can do a strong update */ - edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd); + 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 (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(); + /* 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 dstNodes=GraphManip.getDiffNodes(delta, dst); - edgesToAdd.addAll(GraphManip.genEdges(newSrcNodes, fd, dstNodes)); - HashSet newDstNodes=GraphManip.getDiffNodes(delta, dst); + MySet newSrcEdges=GraphManip.getDiffEdges(delta, src); + MySet srcEdges=GraphManip.getEdges(graph, delta, src); + 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); + } + MySet edgesToRemove=null; - if (newDstNodes.size()!=0) { - if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()) { - /* Need to undo strong update */ - if (graph.strongUpdateSet!=null) { - edgesToAdd.addAll(graph.strongUpdateSet); - graph.strongUpdateSet.clear(); - } - } else if (dstNodes.size()==0&&newDstNodes.size()==1&&!newDstNodes.iterator().next().isSummary()&&graph.strongUpdateSet==null) { - edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd); - } - HashSet srcNodes=GraphManip.getDiffNodes(delta, src); - edgesToAdd.addAll(GraphManip.genEdges(srcNodes, fd, newDstNodes)); + 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, fd); + if (edgesToRemove!=null) + edgesToRemove.addAll(otherEdgesToRemove); + else + edgesToRemove=otherEdgesToRemove; + graph.strongUpdateSet.addAll(otherEdgesToRemove); + } + + //Next look at new destinations + Edge.mergeEdgesInto(edgesToAdd, GraphManip.genEdges(dstNodes, fd, newSrcEdges)); + /* Update diff */ updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove); applyDiffs(graph, delta); @@ -599,6 +1571,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(); @@ -607,26 +1580,31 @@ public class Pointer { FlatReturnNode frn=(FlatReturnNode)node; src=frn.getReturnTemp(); dst=returntmp; + if (src==null||!src.getType().isPtr()) { + //This is a NOP + applyDiffs(graph, delta); + return delta; + } } else { FlatCastNode fcn=(FlatCastNode) node; src=fcn.getSrc(); dst=fcn.getDst(); } if (delta.getInit()) { - HashSet srcnodes=GraphManip.getNodes(graph, delta, src); - MySet edgesToAdd=GraphManip.genEdges(src, 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(src, 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); @@ -639,6 +1617,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(); @@ -650,81 +1630,133 @@ 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(src, 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(src, 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 - edgeAdd.remove(e); - //if the edge is already in the graph, add an explicit remove to the delta - if (existingEdges.contains(e)) - edgeRemove.add(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 - edgeRemove.remove(e); + if (edgeRemove!=null) + edgeRemove.remove(e); //Explicitly add it to the add set unless it is already in the graph - if (!existingEdges.contains(e)) - edgeAdd.add(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) { - 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)) { - MySet edgeRemove=delta.heapedgeremove.get(src); - edgeRemove.add(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: edgestoAdd) { - AllocNode src=e.src; - MySet edgeRemove=delta.heapedgeremove.get(src); - MySet existingEdges=graph.getEdges(src); - //Remove the edge from the remove set - edgeRemove.remove(e); - //Explicitly add it to the add set unless it is already in the graph - if (!existingEdges.contains(e)) { - MySet edgeAdd=delta.heapedgeadd.get(src); - edgeAdd.add(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)); + } + } } - } } Delta processFlatNop(FlatNode node, Delta delta, Graph graph) { @@ -751,82 +1783,91 @@ public class Pointer { //Add it into the diffs delta.varedgeadd.put(tmp, newedges); //Remove the old edges - delta.varedgeremove.put(tmp, graph.getEdges(tmp)); - //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); + } } 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 @@ -834,12 +1875,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); } - //Apply incoming diffs to graph - applyDiffs(graph, delta); } + //Apply incoming diffs to graph + applyDiffs(graph, delta); + return delta; } @@ -847,23 +1894,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) @@ -876,28 +1923,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 */ @@ -909,25 +1957,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); + } + } + 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 @@ -935,25 +1997,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); + } + } + 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); - } + 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); } } } @@ -961,38 +2039,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()) { + Set livetemps=bblivetemps.get(block); + + for(Map.Entry> varedge : delta.varedgeadd.entrySet()) { TempDescriptor tmpsrc=varedge.getKey(); - MySet edges=varedge.getValue(); - 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); + 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()) { + 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); } } } -} \ 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; + } +}