X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FPointer%2FPointer.java;h=8b0ce00bfac302c3987be65ed739192fd9236ab1;hb=e94f955167b58e9356e2258eac3e66564084129b;hp=cd474145332b792748a9dda51ba2e1fffc1c3b03;hpb=9f6576080dd17f8675251d5047333d3cea411fed;p=IRC.git diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index cd474145..8b0ce00b 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -2,186 +2,1765 @@ 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; + 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>(); this.typeUtil=typeUtil; this.allocFactory=new AllocFactory(state, typeUtil); 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); BasicBlock bb=getBBlock(fm); BBlock start=bb.getStart(); - Delta delta=new Delta(start, true); - HashSet arrayset=new HashSet(); - HashSet varset=new HashSet(); - arrayset.add(new Edge(allocFactory.StringArray, null, allocFactory.Strings)); - varset.add(new Edge(fm.getParameter(0), allocFactory.StringArray)); - delta.heapedgeadd.put(allocFactory.StringArray, arrayset); - delta.varedgeadd.put(fm.getParameter(0), varset); + Delta delta=new Delta(new PPoint(start), true); + MySet arrayset=new MySet(); + MySet varset=new MySet(); + Edge arrayedge=new Edge(allocFactory.StringArray, null, allocFactory.Strings); + Edge stringedge=new Edge(fm.getParameter(0), allocFactory.StringArray); + delta.addHeapEdge(arrayedge); + delta.addVarEdge(stringedge); + return delta; } - void doAnalysis() { - toprocess.add(buildInitialContext()); + public Graph getGraph(FlatNode fn) { + return graphMap.get(fn); + } + + public void doAnalysis() { + + toprocess.add(buildInitialContext()); +nextdelta: while(!toprocess.isEmpty()) { Delta delta=toprocess.remove(); - BBlock bblock=delta.getBlock(); + PPoint ppoint=delta.getBlock(); + BBlock bblock=ppoint.getBBlock(); Vector nodes=bblock.nodes(); + int startindex=0; - //Build base graph for entrance to this basic block - delta=applyInitDelta(delta, bblock); + 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(); + + 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"); } - //XXXX: Need to generate new delta - } + } } - Delta processNode(FlatNode node, Delta delta, Graph newgraph) { + 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) { + MySet edgeSet=new MySet(); + /* Get target set */ + if (graph.varMap.containsKey(tmp)) + edgeSet.addAll(graph.varMap.get(tmp)); + else + 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) { + MySet edgeSet=new MySet(); + /* Get edge set */ + if (graph.nodeMap.containsKey(node)) + edgeSet.addAll(graph.nodeMap.get(node)); + else + edgeSet.addAll(graph.parent.nodeMap.get(node)); + newDelta.heapedgeadd.put(node, edgeSet); + + /* Compute ages */ + if (graph.oldNodes.containsKey(node)) { + if (graph.oldNodes.get(node).booleanValue()) + newDelta.addOldNodes.put(node, Boolean.TRUE); + } 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()) { + buildInitDelta(graph, newDelta); + } else { + /* We can break the old delta...it is done being used */ + /* First we will build variable edges */ + HashSet tmpSet=new HashSet(); + tmpSet.addAll(delta.basevaredge.keySet()); + tmpSet.addAll(delta.varedgeadd.keySet()); + for(TempDescriptor tmp : tmpSet) { + /* Start with the new incoming edges */ + MySet newbaseedge=delta.basevaredge.get(tmp); + /* Remove the remove set */ + if (newbaseedge==null) + newbaseedge=new MySet(); + newbaseedge.removeAll(delta.varedgeremove.get(tmp)); + /* Add in the new set*/ + newbaseedge.addAll(delta.varedgeadd.get(tmp)); + /* Store the results */ + newDelta.varedgeadd.put(tmp, newbaseedge); + } + 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=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()||!newDelta.addOldNodes.isEmpty()) { + /* We have a delta to propagate */ + if (returnMap.containsKey(bblock)) { + //exit of call block + boolean first=true; + + for(PPoint caller : returnMap.get(bblock)) { + //System.out.println("Sending Return BBlock to "+caller.getBBlock().nodes.get(caller.getIndex()).toString().replace(' ','_')); + //newDelta.print(); + if (first) { + newDelta.setBlock(caller); + toprocess.add(newDelta); + first=false; + } else { + Delta d=newDelta.diffBlock(caller); + toprocess.add(d); + } + } + } else { + //normal block + Vector 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()); + 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); + } + } + } + } + + /* 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()); + edgeset.addAll(edges); + for(Edge e:edges) { + 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); + 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()||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 + 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 newtargets=computeTargets(fcall, newDelta); + + //Fix mapping + 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, true); + } else { + MySet edgeset=new MySet(); + MySet externaledgeset=new MySet(); + HashSet nodeset=new HashSet(); + MySet oldedgeset=graph.reachEdge; + HashSet oldnodeset=graph.reachNode; + + 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) { + //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 newtargets=computeTargets(fcall, newDelta); + graph.callTargets.addAll(newtargets); + + //add in new nodeset and edgeset + oldnodeset.addAll(nodeset); + oldedgeset.addAll(edgeset); + //Fix mapping + 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(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) { + 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(); - HashSet edges=e.getValue(); + MySet edges=e.getValue(); if (graph.nodeMap.containsKey(node)) { - HashSet 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(); - HashSet edgestoremove=e.getValue(); + 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 - HashSet parentedges=graph.parent.nodeMap.get(node); - HashSet 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(); - HashSet edgestoadd=e.getValue(); - //If we have not done a subtract, then + MySet edgestoadd=e.getValue(); + //If we have not done a subtract, then if (!graph.nodeMap.containsKey(node)) { - //Copy the parent entry - graph.nodeMap.put(node, (HashSet)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(); - HashSet edgestoremove=e.getValue(); + 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 - HashSet parentedges=graph.parent.varMap.get(tmp); - HashSet 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(); - HashSet edgestoadd=e.getValue(); - graph.varMap.put(tmp, (HashSet) edgestoadd.clone()); + MySet edgestoadd=e.getValue(); + 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) { + graph.nodeAges.add(node); + } + + for(Map.Entry nodeentry : delta.addOldNodes.entrySet()) { + AllocNode node=nodeentry.getKey(); + Boolean ispresent=nodeentry.getValue(); + graph.oldNodes.put(node, ispresent); } } - HashSet getTemps(Graph graph, Delta delta, TempDescriptor tmp) { - HashSet nodes=new HashSet(); - HashSet removeedges=delta.varedgeremove.get(tmp); + 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; + TempDescriptor dst; + if (node.kind()==FKind.FlatSetElementNode) { + FlatSetElementNode fen=(FlatSetElementNode) node; + src=fen.getSrc(); + fd=null; + dst=fen.getDst(); + } else { + FlatSetFieldNode ffn=(FlatSetFieldNode) node; + src=ffn.getSrc(); + fd=ffn.getField(); + dst=ffn.getDst(); + } + + if (delta.getInit()) { + 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 { + 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 */ - for(Edge e:graph.getEdges(tmp)) { - if (removeedges==null||!removeedges.contains(e)) - nodes.add(e.dst); + MySet edgesToAdd=new MySet(); + 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 (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); } - if (delta.varedgeadd.containsKey(tmp)) - for(Edge e:delta.varedgeadd.get(tmp)) { - nodes.add(e.dst); + return delta; + } + + Delta processCopyNode(FlatNode node, Delta delta, Graph graph) { + TempDescriptor src; + TempDescriptor dst; + + if (node.kind()==FKind.FlatOpNode) { + FlatOpNode fon=(FlatOpNode) node; + src=fon.getLeft(); + dst=fon.getDest(); + } else if (node.kind()==FKind.FlatReturnNode) { + FlatReturnNode frn=(FlatReturnNode)node; + src=frn.getReturnTemp(); + dst=returntmp; + if (src==null||!src.getType().isPtr()) { + //This is a NOP + applyDiffs(graph, delta); + return delta; } - return nodes; + } else { + FlatCastNode fcn=(FlatCastNode) node; + src=fcn.getSrc(); + dst=fcn.getDst(); + } + if (delta.getInit()) { + 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 */ + MySet newSrcEdges=GraphManip.getDiffEdges(delta, src); + + /* Compute the union, and then the set of edges */ + MySet edgesToAdd=GraphManip.genEdges(dst, newSrcEdges); + + /* Compute set of edges to remove */ + MySet edgesToRemove=GraphManip.getDiffEdges(delta, dst); + + /* Update diff */ + updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove); + applyDiffs(graph, delta); + } + return delta; } - Delta processFieldNode(FlatFieldNode node, Delta delta, Graph graph) { - TempDescriptor src=node.getSrc(); - FieldDescriptor fd=node.getField(); - TempDescriptor dst=node.getDst(); + Delta processFieldElementNode(FlatNode node, Delta delta, Graph graph) { + TempDescriptor src; + FieldDescriptor fd; + TempDescriptor dst; + TaintSet taint=null; + + if (node.kind()==FKind.FlatElementNode) { + FlatElementNode fen=(FlatElementNode) node; + src=fen.getSrc(); + fd=null; + dst=fen.getDst(); + } else { + FlatFieldNode ffn=(FlatFieldNode) node; + src=ffn.getSrc(); + 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 nodes=getTemps(graph, delta, src); - - + 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 */ + MySet allsrcedges=GraphManip.getEdges(graph, delta, src); + MySet edgesToAdd=GraphManip.diffDereference(delta, dst, allsrcedges, fd, node); + /* Next compute new targets of fields */ + MySet newfdedges=GraphManip.dereference(graph, delta, dst, newsrcedges, fd, node); + + /* Compute the union, and then the set of edges */ + Edge.mergeEdgesInto(edgesToAdd, newfdedges); + + /* Compute set of edges to remove */ + MySet edgesToRemove=GraphManip.getDiffEdges(delta, dst); + + /* Update diff */ + updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove); + applyDiffs(graph, delta); } + + return delta; + } + + 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); + 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); + //Explicitly add it to the add set unless it is already in the graph + if (typeUtil.isSuperorType(tmp.getType(), e.dst.getType())) { + if (!existingEdges.contains(e)) { + delta.addVarEdge(e); + } else { + //See if the old edge subsumes the new one + Edge olde=existingEdges.get(e); + if (!olde.subsumes(e)) { + delta.addVarEdge(olde.merge(e)); + } + } + } + } + } + + 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); + } + } + 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) { + applyDiffs(graph, delta); return delta; } @@ -189,142 +1768,149 @@ public class Pointer { AllocNode summary=allocFactory.getAllocNode(node, true); AllocNode single=allocFactory.getAllocNode(node, false); TempDescriptor tmp=node.getDst(); - + if (delta.getInit()) { + /* We don't have to deal with summarization here... The + * intuition is that this is the only place where we generate + * nodes for this allocation site and this is the first time + * we've analyzed this site */ + //Build new Edge Edge e=new Edge(tmp, single); //Build new Edge set - HashSet newedges=new HashSet(); + MySet newedges=new MySet(); newedges.add(e); //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(); - 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... */ - rewriteSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary); - } + if (entry.getKey()==tmp) { + /* Check if this is the tmp we overwrite */ + entryIt.remove(); + } else { + /* Otherwise, check if the target of the edge is changed... */ + summarizeSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary); + } } - + /* 2. Fix up the base variable edges */ - for(Iterator>> entryIt=delta.basevaredge.entrySet().iterator();entryIt.hasNext();) { - Map.Entry> entry=entryIt.next(); - TempDescriptor entrytmp=entry.getKey(); - if (entrytmp==tmp) { - /* Check is this is the tmp we overwrite, if so add to remove set */ - if (delta.varedgeremove.containsKey(tmp)) - delta.varedgeremove.get(tmp).addAll(entry.getValue()); - else - delta.varedgeremove.put(tmp, entry.getValue()); - } else { - /* Check if the target of the edge is changed */ - HashSet newset=(HashSet)entry.getValue().clone(); - HashSet removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary); - if (delta.varedgeremove.containsKey(entrytmp)) { - /* Make sure we do not remove the newly created edges. */ - delta.varedgeremove.get(entrytmp).removeAll(newset); - /* Remove the old edges to the single node */ - delta.varedgeremove.get(entrytmp).addAll(removeset); - } else { - /* Remove the old edges to the single node */ - delta.varedgeremove.put(entrytmp, removeset); - } - if (delta.varedgeadd.containsKey(entrytmp)) { - /* Create the new edges */ - delta.varedgeadd.get(entrytmp).addAll(newset); - } else { - /* Create the new edges */ - delta.varedgeadd.put(entrytmp, 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(); - HashSet edgeset=entry.getValue(); - AllocNode allocnode=entry.getKey(); - if (allocnode==single) { - entryIt.remove(); - rewriteSet(edgeset, graph.nodeMap.get(summary), single, summary); - addheapedge.put(summary, edgeset); - } else { - rewriteSet(edgeset, graph.nodeMap.get(allocnode), single, summary); - } - } - + 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); + } + } + /* Merge in diffs */ - for(Map.Entry> entry:addheapedge.entrySet()) { - AllocNode allocnode=entry.getKey(); - if (delta.heapedgeadd.containsKey(allocnode)) { - delta.heapedgeadd.get(allocnode).addAll(entry.getValue()); - } else { - delta.heapedgeadd.put(allocnode, 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(); - HashSet edgeset=entry.getValue(); - AllocNode allocnode=entry.getKey(); - if (allocnode==single) { - entryIt.remove(); - } - AllocNode addnode=(allocnode==single)?summary:allocnode; - - HashSet newset=(HashSet) edgeset.clone(); - HashSet removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary); - if (delta.heapedgeadd.containsKey(addnode)) { - delta.heapedgeadd.get(addnode).addAll(newset); - } else { - delta.heapedgeadd.put(addnode, newset); - } - if (delta.heapedgeremove.containsKey(allocnode)) { - delta.heapedgeremove.get(allocnode).addAll(removeset); - } else { - delta.heapedgeremove.put(allocnode, removeset); - } - } - - //Apply incoming diffs to graph - applyDiffs(graph, delta); + 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 + * single node, it now should also contain a summary node... No + * 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); + } + + //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); + return delta; } - void rewriteSet(HashSet edgeset, HashSet oldedgeset, AllocNode oldnode, AllocNode newnode) { - HashSet newSet=null; - for(Iterator edgeit=edgeset.iterator();edgeit.hasNext();) { + /* This function builds a new edge set where oldnode is summarized into new node */ + + void summarizeSet(MySet edgeset, MySet oldedgeset, AllocNode oldnode, AllocNode sumnode) { + MySet newSet=null; + for(Iterator edgeit=edgeset.iterator(); edgeit.hasNext(); ) { Edge e=edgeit.next(); if (e.dst==oldnode||e.src==oldnode) { - if (newSet==null) { - newSet=new HashSet(); - } - edgeit.remove(); - 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(); + } + 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) @@ -334,31 +1920,35 @@ public class Pointer { /* Shrinks the incoming set to just include rewritten values. * Returns a set of the original rewritten values */ - HashSet shrinkSet(HashSet edgeset, HashSet oldedgeset, AllocNode oldnode, AllocNode newnode) { - HashSet newSet=null; - HashSet removeSet=null; - for(Iterator edgeit=edgeset.iterator();edgeit.hasNext();) { + MySet shrinkSet(MySet edgeset, MySet oldedgeset, AllocNode oldnode, AllocNode newnode) { + MySet newSet=null; + MySet removeSet=null; + 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 HashSet(); - removeSet=new HashSet(); - } + 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); + 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 */ Delta applyInitDelta(Delta delta, BBlock block) { //Apply delta to graph @@ -367,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); - //Record that this is a diff - newdelta.setInit(false); + 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 @@ -393,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(); - HashSet edges=heapedge.getValue(); + 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 HashSet()); + graph.nodeMap.put(nsrc, new MySet()); } - HashSet dstedges=graph.nodeMap.get(nsrc); - HashSet diffedges=new HashSet(); - for(Edge e:edges) { - if (!dstedges.contains(e)) { - //We have a new edge - diffedges.add(e); - dstedges.add(e); - } + 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); + } + } } //Done with edge set... if (diffedges.size()>0) { - //completely new - newdelta.baseheapedge.put(nsrc, diffedges); + //completely new + newdelta.baseheapedge.put(nsrc, diffedges); } } } @@ -419,28 +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(); - HashSet edges=varedge.getValue(); - if (!graph.varMap.containsKey(tmpsrc)) { - graph.varMap.put(tmpsrc, new HashSet()); + 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); + } } - HashSet dstedges=graph.varMap.get(tmpsrc); - HashSet diffedges=new HashSet(); - for(Edge e:edges) { - if (!dstedges.contains(e)) { - //We have a new edge - diffedges.add(e); - dstedges.add(e); - } + } + } + + void mergeAges(Graph graph, Delta delta, Delta newDelta) { + //Merge in edges + for(AllocNode node : delta.addNodeAges) { + if (!graph.nodeAges.contains(node)) { + graph.nodeAges.add(node); + newDelta.baseNodeAges.add(node); } - //Done with edge set... - if (diffedges.size()>=0) { - //completely new - newdelta.basevaredge.put(tmpsrc,diffedges); + } + 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; + } +}