1 package Analysis.Pointer;
5 import Analysis.Liveness;
6 import Analysis.Pointer.BasicBlock.BBlock;
7 import Analysis.Pointer.AllocFactory.AllocNode;
8 import Analysis.Disjoint.Alloc;
9 import Analysis.Disjoint.Taint;
10 import Analysis.Disjoint.TaintSet;
11 import Analysis.Disjoint.Canonical;
12 import Analysis.Disjoint.HeapAnalysis;
13 import Analysis.CallGraph.CallGraph;
14 import Analysis.OoOJava.RBlockRelationAnalysis;
15 import Analysis.OoOJava.Accessible;
16 import Analysis.Disjoint.ExistPred;
17 import Analysis.Disjoint.ReachGraph;
18 import Analysis.Disjoint.EffectsAnalysis;
19 import Analysis.Disjoint.BuildStateMachines;
23 public class Pointer implements HeapAnalysis {
24 HashMap<FlatMethod, BasicBlock> blockMap;
25 HashMap<BBlock, Graph> bbgraphMap;
26 HashMap<FlatNode, Graph> graphMap;
27 HashMap<FlatCall, Set<BBlock>> callMap;
28 HashMap<BBlock, Set<PPoint>> returnMap;
29 HashMap<BBlock, Set<TempDescriptor>> bblivetemps;
30 HashSet<FlatNode> mustProcess;
32 private boolean OoOJava=false;
36 AllocFactory allocFactory;
37 LinkedList<Delta> toprocess;
38 TempDescriptor returntmp;
39 RBlockRelationAnalysis taskAnalysis;
40 EffectsAnalysis effectsAnalysis;
41 Accessible accessible;
43 public Pointer(State state, TypeUtil typeUtil, CallGraph callGraph, RBlockRelationAnalysis taskAnalysis, Liveness liveness, BuildStateMachines bsm) {
44 this(state, typeUtil);
45 this.callGraph=callGraph;
47 this.taskAnalysis=taskAnalysis;
48 this.effectsAnalysis=new EffectsAnalysis();
49 effectsAnalysis.state=state;
50 effectsAnalysis.buildStateMachines=bsm;
51 accessible=new Accessible(state, callGraph, taskAnalysis, liveness);
52 accessible.doAnalysis();
53 State.logEvent("Done Writing Accessible Analysis");
56 public Pointer(State state, TypeUtil typeUtil) {
58 this.blockMap=new HashMap<FlatMethod, BasicBlock>();
59 this.bbgraphMap=new HashMap<BBlock, Graph>();
60 this.bblivetemps=new HashMap<BBlock, Set<TempDescriptor>>();
61 this.graphMap=new HashMap<FlatNode, Graph>();
62 this.callMap=new HashMap<FlatCall, Set<BBlock>>();
63 this.returnMap=new HashMap<BBlock, Set<PPoint>>();
64 this.typeUtil=typeUtil;
65 this.allocFactory=new AllocFactory(state, typeUtil);
66 this.toprocess=new LinkedList<Delta>();
67 ClassDescriptor stringcd=typeUtil.getClass(TypeUtil.ObjectClass);
68 this.returntmp=new TempDescriptor("RETURNVAL", stringcd);
69 this.mustProcess=new HashSet<FlatNode>();
72 public EffectsAnalysis getEffectsAnalysis() {
73 return effectsAnalysis;
76 public BasicBlock getBBlock(FlatMethod fm) {
77 if (!blockMap.containsKey(fm)) {
78 blockMap.put(fm, BasicBlock.getBBlock(fm));
79 Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
80 for(BBlock bblock : blockMap.get(fm).getBlocks()) {
81 FlatNode fn=bblock.nodes.get(0);
83 HashSet<TempDescriptor> fmset=new HashSet<TempDescriptor>();
84 fmset.addAll((List<TempDescriptor>)Arrays.asList(fm.writesTemps()));
85 bblivetemps.put(bblock, fmset);
87 Set<TempDescriptor> livetemps=livemap.get(fn);
88 bblivetemps.put(bblock, livetemps);
89 livetemps.add(returntmp);
93 return blockMap.get(fm);
96 Delta buildInitialContext() {
97 MethodDescriptor md=typeUtil.getMain();
98 FlatMethod fm=state.getMethodFlat(md);
99 BasicBlock bb=getBBlock(fm);
100 BBlock start=bb.getStart();
101 Delta delta=new Delta(new PPoint(start), true);
102 MySet<Edge> arrayset=new MySet<Edge>();
103 MySet<Edge> varset=new MySet<Edge>();
104 Edge arrayedge=new Edge(allocFactory.StringArray, null, allocFactory.Strings);
105 Edge stringedge=new Edge(fm.getParameter(0), allocFactory.StringArray);
106 delta.addHeapEdge(arrayedge);
107 delta.addVarEdge(stringedge);
113 public Graph getGraph(FlatNode fn) {
114 return graphMap.get(fn);
117 public void doAnalysis() {
119 toprocess.add(buildInitialContext());
121 while(!toprocess.isEmpty()) {
122 Delta delta=toprocess.remove();
123 PPoint ppoint=delta.getBlock();
124 BBlock bblock=ppoint.getBBlock();
125 Vector<FlatNode> nodes=bblock.nodes();
128 if (ppoint.getIndex()==-1) {
129 //Build base graph for entrance to this basic block
130 //System.out.println("Processing "+bblock.nodes.get(0).toString().replace(' ','_'));
132 delta=applyInitDelta(delta, bblock);
133 //System.out.println("Generating:");
136 //System.out.println("Processing Call "+bblock.nodes.get(ppoint.getIndex()).toString().replace(' ','_'));
139 startindex=ppoint.getIndex()+1;
140 delta=applyCallDelta(delta, bblock);
141 //System.out.println("Generating:");
144 Graph graph=bbgraphMap.get(bblock);
145 Graph nodeGraph=null;
148 //Compute delta at exit of each node
149 for(int i=startindex; i<nodes.size(); i++) {
150 FlatNode currNode=nodes.get(i);
151 //System.out.println("Start Processing "+currNode);
152 boolean init=delta.getInit();
153 if (!init&&delta.isEmpty())
157 if (!graphMap.containsKey(currNode)) {
158 if (isNEEDED(currNode)) {
159 graphMap.put(currNode, new Graph(graph));
161 boolean fallthru=true;
162 if (isINACC(currNode)&&((lasti==-1)||(lasti==i))) {
164 for(lasti=nodes.size()-1; lasti>=i; lasti--) {
165 FlatNode scurrNode=nodes.get(lasti);
166 if (isNEEDED(scurrNode)||isINACC(scurrNode)) {
172 mustProcess.add(currNode);
173 graphMap.put(currNode, new Graph(graph));
179 //base graph works for us
180 graphMap.put(currNode, new Graph(graph));
182 //just use previous graph
183 graphMap.put(currNode, graphMap.get(nodes.get(i-1)));
189 nodeGraph=graphMap.get(currNode);
190 delta=processNode(bblock, i, currNode, delta, nodeGraph);
191 //System.out.println("Processing "+currNode+" and generating delta:");
194 generateFinalDelta(bblock, delta, nodeGraph);
200 for(Map.Entry<BBlock, Graph> e : bbgraphMap.entrySet()) {
201 Graph g=e.getValue();
202 plotGraph(g,"BB"+e.getKey().nodes.get(0).toString().replace(' ','_'));
206 for(FlatMethod fm : blockMap.keySet()) {
207 System.out.println(fm.printMethod());
209 for(Map.Entry<FlatNode, Graph> e : graphMap.entrySet()) {
210 FlatNode fn=e.getKey();
211 Graph g=e.getValue();
212 plotGraph(g,"FN"+fn.toString()+debugindex);
217 State.logEvent("Done With Pointer Analysis");
221 effectsAnalysis.buildStateMachines.writeStateMachines();
222 State.logEvent("Done Writing State Machines");
226 void plotGraph(Graph g, String name) {
228 PrintWriter pw=new PrintWriter(new FileWriter(name.toString().replace(' ','_')+".dot"));
229 g.printGraph(pw, name);
231 } catch (Exception ex) {
232 ex.printStackTrace();
237 /* This function builds the last delta for a basic block. It
238 * handles the case for the first time the basic block is
241 void buildInitDelta(Graph graph, Delta newDelta) {
242 //First compute the set of temps
243 HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
244 tmpSet.addAll(graph.varMap.keySet());
245 tmpSet.addAll(graph.parent.varMap.keySet());
247 //Next build the temp map part of the delta
248 for(TempDescriptor tmp : tmpSet) {
249 MySet<Edge> edgeSet=new MySet<Edge>();
251 if (graph.varMap.containsKey(tmp))
252 edgeSet.addAll(graph.varMap.get(tmp));
254 edgeSet.addAll(graph.parent.varMap.get(tmp));
255 newDelta.varedgeadd.put(tmp, edgeSet);
258 //Next compute the set of src allocnodes
259 HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
260 nodeSet.addAll(graph.nodeMap.keySet());
261 nodeSet.addAll(graph.parent.nodeMap.keySet());
263 for(AllocNode node : nodeSet) {
264 MySet<Edge> edgeSet=new MySet<Edge>();
266 if (graph.nodeMap.containsKey(node))
267 edgeSet.addAll(graph.nodeMap.get(node));
269 edgeSet.addAll(graph.parent.nodeMap.get(node));
270 newDelta.heapedgeadd.put(node, edgeSet);
273 if (graph.oldNodes.containsKey(node)) {
274 if (graph.oldNodes.get(node).booleanValue())
275 newDelta.addOldNodes.put(node, Boolean.TRUE);
276 } else if (graph.parent.oldNodes.containsKey(node)) {
277 //parent graphs only contain true...no need to check
278 newDelta.addOldNodes.put(node, Boolean.TRUE);
282 newDelta.addNodeAges.addAll(graph.nodeAges);
283 newDelta.addNodeAges.addAll(graph.parent.nodeAges);
286 /* This function build the delta for the exit of a basic block. */
288 void generateFinalDelta(BBlock bblock, Delta delta, Graph graph) {
289 Delta newDelta=new Delta(null, false);
290 if (delta.getInit()) {
291 buildInitDelta(graph, newDelta);
293 /* We can break the old delta...it is done being used */
294 /* First we will build variable edges */
295 HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
296 tmpSet.addAll(delta.basevaredge.keySet());
297 tmpSet.addAll(delta.varedgeadd.keySet());
298 for(TempDescriptor tmp : tmpSet) {
299 /* Start with the new incoming edges */
300 MySet<Edge> newbaseedge=delta.basevaredge.get(tmp);
301 /* Remove the remove set */
302 if (newbaseedge==null)
303 newbaseedge=new MySet<Edge>();
304 newbaseedge.removeAll(delta.varedgeremove.get(tmp));
305 /* Add in the new set*/
306 newbaseedge.addAll(delta.varedgeadd.get(tmp));
307 /* Store the results */
308 newDelta.varedgeadd.put(tmp, newbaseedge);
310 delta.basevaredge.clear();
312 /* Next we build heap edges */
313 HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
314 nodeSet.addAll(delta.baseheapedge.keySet());
315 nodeSet.addAll(delta.heapedgeadd.keySet());
316 nodeSet.addAll(delta.heapedgeremove.keySet());
317 for(AllocNode node : nodeSet) {
318 /* Start with the new incoming edges */
319 MySet<Edge> newheapedge=new MySet<Edge>(delta.baseheapedge.get(node));
320 /* Remove the remove set */
321 MySet<Edge> removeset=delta.heapedgeremove.get(node);
324 newheapedge.removeAll(removeset);
326 /* Add in the add set */
327 MySet<Edge> settoadd=delta.heapedgeadd.get(node);
329 newheapedge.addAll(settoadd);
330 newDelta.heapedgeadd.put(node, newheapedge);
332 /* Remove the newly created edges..no need to propagate a diff for those */
333 if (removeset!=null) {
334 removeset.removeAll(delta.baseheapedge.get(node));
335 newDelta.heapedgeremove.put(node, removeset);
339 /* Compute new ages */
340 newDelta.addNodeAges.addAll(delta.baseNodeAges);
341 newDelta.addNodeAges.addAll(delta.addNodeAges);
342 HashSet<AllocNode> oldNodes=new HashSet<AllocNode>();
344 /* Compute whether old nodes survive */
345 oldNodes.addAll(delta.baseOldNodes.keySet());
346 oldNodes.addAll(delta.addOldNodes.keySet());
347 for(AllocNode node : oldNodes) {
348 if (delta.addOldNodes.containsKey(node)) {
349 if (delta.addOldNodes.get(node).booleanValue()) {
350 newDelta.addOldNodes.put(node, Boolean.TRUE);
353 if (delta.baseOldNodes.get(node).booleanValue()) {
354 newDelta.addOldNodes.put(node, Boolean.TRUE);
360 if (returnMap.containsKey(bblock)) {
361 //clear everything but our return temp!
362 MySet<Edge> edges=newDelta.varedgeadd.get(returntmp);
363 newDelta.varedgeadd.clear();
364 newDelta.varedgeadd.put(returntmp, edges);
367 /* Now we need to propagate newdelta */
368 if (!newDelta.heapedgeadd.isEmpty()||!newDelta.heapedgeremove.isEmpty()||!newDelta.varedgeadd.isEmpty()||!newDelta.addNodeAges.isEmpty()||!newDelta.addOldNodes.isEmpty()) {
369 /* We have a delta to propagate */
370 if (returnMap.containsKey(bblock)) {
374 for(PPoint caller : returnMap.get(bblock)) {
375 //System.out.println("Sending Return BBlock to "+caller.getBBlock().nodes.get(caller.getIndex()).toString().replace(' ','_'));
378 newDelta.setBlock(caller);
379 toprocess.add(newDelta);
382 Delta d=newDelta.diffBlock(caller);
388 Vector<BBlock> blockvector=bblock.next();
389 for(int i=0; i<blockvector.size(); i++) {
390 //System.out.println("Sending BBlock to "+blockvector.get(i).nodes.get(0).toString().replace(' ','_'));
393 newDelta.setBlock(new PPoint(blockvector.get(i)));
394 toprocess.add(newDelta);
396 Delta d=newDelta.diffBlock(new PPoint(blockvector.get(i)));
402 //System.out.println("EMPTY DELTA");
403 //System.out.println("delta");
405 //System.out.println("newDelta");
410 boolean isNEEDED(FlatNode node) {
411 switch(node.kind()) {
412 case FKind.FlatSetFieldNode: {
413 FlatSetFieldNode n=(FlatSetFieldNode)node;
414 return n.getSrc().getType().isPtr();
417 case FKind.FlatSetElementNode: {
418 FlatSetElementNode n=(FlatSetElementNode)node;
419 return n.getSrc().getType().isPtr();
422 case FKind.FlatFieldNode: {
423 FlatFieldNode n=(FlatFieldNode)node;
424 return n.getDst().getType().isPtr();
427 case FKind.FlatElementNode: {
428 FlatElementNode n=(FlatElementNode)node;
429 return n.getDst().getType().isPtr();
435 Delta processNode(BBlock bblock, int index, FlatNode node, Delta delta, Graph newgraph) {
436 switch(node.kind()) {
438 return processNewNode((FlatNew)node, delta, newgraph);
440 case FKind.FlatFieldNode:
441 case FKind.FlatElementNode:
442 return processFieldElementNode(node, delta, newgraph);
444 case FKind.FlatCastNode:
445 case FKind.FlatOpNode:
446 case FKind.FlatReturnNode:
447 return processCopyNode(node, delta, newgraph);
449 case FKind.FlatSetFieldNode:
450 case FKind.FlatSetElementNode:
451 return processSetFieldElementNode(node, delta, newgraph);
453 case FKind.FlatSESEEnterNode:
454 return processSESEEnterNode((FlatSESEEnterNode) node, delta, newgraph);
456 case FKind.FlatSESEExitNode:
457 return processSESEExitNode((FlatSESEExitNode) node, delta, newgraph);
459 case FKind.FlatMethod:
461 case FKind.FlatBackEdge:
462 case FKind.FlatGenReachNode:
463 return processFlatNop(node, delta, newgraph);
466 return processFlatCall(bblock, index, (FlatCall) node, delta, newgraph);
469 throw new Error("Unrecognized node:"+node);
473 Delta processSESEEnterNode(FlatSESEEnterNode sese, Delta delta, Graph graph) {
475 return processFlatNop(sese, delta, graph);
476 if (delta.getInit()) {
477 removeInitTaints(null, delta, graph);
478 for (TempDescriptor tmp : sese.getInVarSet()) {
479 Taint taint=Taint.factory(sese, null, tmp, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
480 MySet<Edge> edges=GraphManip.getEdges(graph, delta, tmp);
481 for(Edge e : edges) {
482 Edge newe=e.addTaint(taint);
483 delta.addVarEdge(newe);
487 removeDiffTaints(null, delta);
488 for (TempDescriptor tmp : sese.getInVarSet()) {
489 Taint taint=Taint.factory(sese, null, tmp, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
490 MySet<Edge> edges=GraphManip.getDiffEdges(delta, tmp);
491 for(Edge e : edges) {
492 Edge newe=e.addTaint(taint);
493 delta.addVarEdge(newe);
499 applyDiffs(graph, delta);
503 private boolean isRecursive(FlatSESEEnterNode sese) {
504 MethodDescriptor md=sese.getmdEnclosing();
505 boolean isrecursive=callGraph.getCalleeSet(md).contains(md);
509 Delta processSESEExitNode(FlatSESEExitNode seseexit, Delta delta, Graph graph) {
511 return processFlatNop(seseexit, delta, graph);
512 FlatSESEEnterNode sese=seseexit.getFlatEnter();
513 //Strip Taints from this SESE
514 if (delta.getInit()) {
515 removeInitTaints(isRecursive(sese)?null:sese, delta, graph);
517 removeDiffTaints(isRecursive(sese)?null:sese, delta);
519 applyDiffs(graph, delta);
523 void removeDiffTaints(FlatSESEEnterNode sese, Delta delta) {
524 //Start with variable edges
526 MySet<Edge> edgestoadd=new MySet<Edge>();
527 MySet<Edge> edgestoremove=new MySet<Edge>();
529 //Process base diff edges
530 processEdgeMap(sese, delta.basevaredge, null, delta.varedgeremove, edgestoremove, edgestoadd);
531 //Process delta edges
532 processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd);
533 for(Edge e : edgestoremove) {
534 delta.removeVarEdge(e);
536 for(Edge e : edgestoadd) {
543 MySet<Edge> edgestoadd=new MySet<Edge>();
544 MySet<Edge> edgestoremove=new MySet<Edge>();
546 //Process base diff edges
547 processEdgeMap(sese, delta.baseheapedge, null, delta.heapedgeremove, edgestoremove, edgestoadd);
548 //Process delta edges
549 processEdgeMap(sese, delta.heapedgeadd, null, null, edgestoremove, edgestoadd);
550 for(Edge e : edgestoremove) {
551 delta.removeHeapEdge(e);
553 for(Edge e : edgestoadd) {
554 delta.addHeapEdge(e);
559 void removeInitTaints(FlatSESEEnterNode sese, Delta delta, Graph graph) {
560 //Start with variable edges
562 MySet<Edge> edgestoadd=new MySet<Edge>();
563 MySet<Edge> edgestoremove=new MySet<Edge>();
565 //Process parent edges
566 processEdgeMap(sese, graph.parent.varMap, graph.varMap, delta.varedgeremove, edgestoremove, edgestoadd);
567 //Process graph edges
568 processEdgeMap(sese, graph.varMap, null, delta.varedgeremove, edgestoremove, edgestoadd);
569 //Process delta edges
570 processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd);
571 for(Edge e : edgestoremove) {
572 delta.removeVarEdge(e);
574 for(Edge e : edgestoadd) {
581 MySet<Edge> edgestoadd=new MySet<Edge>();
582 MySet<Edge> edgestoremove=new MySet<Edge>();
584 //Process parent edges
585 processEdgeMap(sese, graph.parent.nodeMap, graph.nodeMap, delta.heapedgeremove, edgestoremove, edgestoadd);
586 //Process graph edges
587 processEdgeMap(sese, graph.nodeMap, null, delta.heapedgeremove, edgestoremove, edgestoadd);
588 //Process delta edges
589 processEdgeMap(sese, delta.heapedgeadd, null, null, edgestoremove, edgestoadd);
590 for(Edge e : edgestoremove) {
591 delta.removeHeapEdge(e);
593 for(Edge e : edgestoadd) {
594 delta.addHeapEdge(e);
599 void processEdgeMap(FlatSESEEnterNode sese, HashMap<?, MySet<Edge>> edgemap, HashMap<?, MySet<Edge>> childmap, HashMap<?, MySet<Edge>> removemap, MySet<Edge> edgestoremove, MySet<Edge> edgestoadd) {
600 for(Map.Entry<?, MySet<Edge>> entry:edgemap.entrySet()) {
601 //If the parent map exists and overrides this entry, skip it
602 if (childmap!=null&&childmap.containsKey(entry.getKey()))
604 for(Edge e:entry.getValue()) {
605 //check whether this edge has been removed
606 if (removemap!=null&&removemap.containsKey(entry.getKey())&&
607 removemap.get(entry.getKey()).contains(e))
610 TaintSet ts=e.getTaints();
612 //update non-null taint set
614 newts=Canonical.removeInContextTaintsNP(ts, sese);
615 if (newts!=null&&newts!=ts) {
616 edgestoremove.add(e);
617 edgestoadd.add(e.changeTaintSet(newts));
623 /* This function compute the edges for the this variable for a
624 * callee if it exists. */
626 void processThisTargets(HashSet<ClassDescriptor> targetSet, Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, TempDescriptor tmpthis, HashSet<AllocNode> oldnodeset) {
627 //Handle the this temp
629 MySet<Edge> edges=(oldnodeset!=null)?GraphManip.getDiffEdges(delta, tmpthis):GraphManip.getEdges(graph, delta, tmpthis);
630 newDelta.varedgeadd.put(tmpthis, (MySet<Edge>)edges.clone());
631 edgeset.addAll(edges);
633 AllocNode dstnode=e.dst;
634 if (!nodeset.contains(dstnode)&&(oldnodeset==null||!oldnodeset.contains(dstnode))) {
635 TypeDescriptor type=dstnode.getType();
636 if (!type.isArray()) {
637 targetSet.add(type.getClassDesc());
639 //arrays don't have code
640 targetSet.add(typeUtil.getClass(TypeUtil.ObjectClass));
642 nodeset.add(dstnode);
643 tovisit.add(dstnode);
649 /* This function compute the edges for a call's parameters. */
651 void processParams(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, FlatCall fcall, boolean diff) {
652 //Go through each temp
653 for(int i=0; i<fcall.numArgs(); i++) {
654 TempDescriptor tmp=fcall.getArg(i);
655 MySet<Edge> edges=diff?GraphManip.getDiffEdges(delta, tmp):GraphManip.getEdges(graph, delta, tmp);
656 newDelta.varedgeadd.put(tmp, (MySet<Edge>)edges.clone());
657 edgeset.addAll(edges);
659 if (!nodeset.contains(e.dst)) {
667 /* This function computes the reachable nodes for a callee. */
669 void computeReachableNodes(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, HashSet<AllocNode> oldnodeset) {
670 while(!tovisit.isEmpty()) {
671 AllocNode node=tovisit.pop();
672 MySet<Edge> edges=GraphManip.getEdges(graph, delta, node);
673 if (!edges.isEmpty()) {
674 newDelta.heapedgeadd.put(node, Edge.makeOld(edges));
675 edgeset.addAll(edges);
676 for(Edge e : edges) {
677 if (!nodeset.contains(e.dst)&&(oldnodeset==null||!oldnodeset.contains(e.dst))) {
686 HashSet<MethodDescriptor> computeTargets(FlatCall fcall, Delta newDelta) {
687 TempDescriptor tmpthis=fcall.getThis();
688 MethodDescriptor md=fcall.getMethod();
689 HashSet<MethodDescriptor> targets=new HashSet<MethodDescriptor>();
690 if (md.isStatic()||fcall.getSuper()) {
694 for(Edge e : newDelta.varedgeadd.get(tmpthis)) {
695 AllocNode node=e.dst;
696 ClassDescriptor cd=node.getType().getClassDesc();
697 //Figure out exact method called and add to set
698 MethodDescriptor calledmd=cd.getCalledMethod(md);
699 targets.add(calledmd);
705 void fixMapping(FlatCall fcall, HashSet<MethodDescriptor> targets, MySet<Edge> oldedgeset, Delta newDelta, BBlock callblock, int callindex) {
706 Delta basedelta=null;
707 TempDescriptor tmpthis=fcall.getThis();
709 for(MethodDescriptor calledmd : targets) {
710 FlatMethod fm=state.getMethodFlat(calledmd);
711 boolean newmethod=false;
714 HashMap<TempDescriptor, TempDescriptor> tmpMap=new HashMap<TempDescriptor, TempDescriptor>();
717 tmpMap.put(tmpthis, fm.getParameter(offset++));
719 for(int i=0; i<fcall.numArgs(); i++) {
720 TempDescriptor tmp=fcall.getArg(i);
721 tmpMap.put(tmp,fm.getParameter(i+offset));
724 //Get basicblock for the method
725 BasicBlock block=getBBlock(fm);
728 if (!callMap.containsKey(fcall)) {
729 callMap.put(fcall, new HashSet<BBlock>());
732 Delta returnDelta=null;
733 if (!callMap.get(fcall).contains(block.getStart())) {
734 callMap.get(fcall).add(block.getStart());
738 if (!returnMap.containsKey(block.getExit())) {
739 returnMap.put(block.getExit(), new HashSet<PPoint>());
741 returnMap.get(block.getExit()).add(new PPoint(callblock, callindex));
743 if (bbgraphMap.containsKey(block.getExit())) {
744 //Need to push existing results to current node
745 if (returnDelta==null) {
746 returnDelta=new Delta(null, false);
747 Vector<FlatNode> exitblocknodes=block.getExit().nodes();
748 FlatExit fexit=(FlatExit)exitblocknodes.get(exitblocknodes.size()-1);
749 buildInitDelta(graphMap.get(fexit), returnDelta);
750 if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
751 returnDelta.setBlock(new PPoint(callblock, callindex));
752 toprocess.add(returnDelta);
755 if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
756 toprocess.add(returnDelta.diffBlock(new PPoint(callblock, callindex)));
762 if (oldedgeset==null) {
763 //First build of this graph
764 //Build and enqueue delta...safe to just use existing delta
765 Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
766 //System.out.println("AProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_'));
769 } else if (newmethod) {
770 if (basedelta==null) {
771 basedelta=newDelta.buildBase(oldedgeset);
773 //Build and enqueue delta
774 Delta d=basedelta.changeParams(tmpMap, new PPoint(block.getStart()));
775 //System.out.println("BProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_'));
779 //Build and enqueue delta
780 Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
781 //System.out.println("CProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_'));
789 /* This function computes all edges that start outside of the callee
790 * context and go into the callee context */
792 void computeExternalEdges(Graph graph, Delta delta, HashSet<AllocNode> nodeset, HashSet<AllocNode> deltaset, MySet<Edge> externaledgeset) {
793 //Do heap edges first
794 HashSet<AllocNode> externalnodes=new HashSet<AllocNode>();
795 externalnodes.addAll(delta.baseheapedge.keySet());
796 externalnodes.addAll(delta.heapedgeadd.keySet());
797 externalnodes.addAll(delta.heapedgeremove.keySet());
798 //remove allinternal nodes
799 externalnodes.removeAll(nodeset);
800 for(AllocNode extNode : externalnodes) {
801 //Compute set of edges from given node
802 MySet<Edge> edges=new MySet<Edge>(delta.baseheapedge.get(extNode));
803 edges.removeAll(delta.heapedgeremove.get(extNode));
804 edges.addAll(delta.heapedgeadd.get(extNode));
806 for(Edge e : edges) {
807 if (nodeset.contains(e.dst))
808 externaledgeset.add(e);
813 HashSet<TempDescriptor> temps=new HashSet<TempDescriptor>();
814 temps.addAll(delta.basevaredge.keySet());
815 temps.addAll(delta.varedgeadd.keySet());
816 temps.addAll(delta.varedgeremove.keySet());
817 //remove allinternal nodes
818 temps.removeAll(nodeset);
820 for(TempDescriptor tmp : temps) {
821 //Compute set of edges from given node
822 MySet<Edge> edges=new MySet<Edge>(delta.basevaredge.get(tmp));
824 edges.removeAll(delta.varedgeremove.get(tmp));
825 edges.addAll(delta.varedgeadd.get(tmp));
827 for(Edge e : edges) {
828 if (nodeset.contains(e.dst))
829 externaledgeset.add(e);
834 /* This function removes the caller reachable edges from the
837 void removeEdges(Graph graph, Delta delta, HashSet<AllocNode> nodeset, MySet<Edge> edgeset, MySet<Edge> externaledgeset) {
838 //Want to remove the set of internal edges
839 for(Edge e : edgeset) {
840 if (e.src!=null&&!graph.callerEdges.contains(e)) {
841 delta.removeHeapEdge(e);
845 //Want to remove the set of external edges
846 for(Edge e : externaledgeset) {
847 //want to remove the set of internal edges
848 if (!graph.callerEdges.contains(e))
853 Delta processFlatCall(BBlock callblock, int callindex, FlatCall fcall, Delta delta, Graph graph) {
854 Delta newDelta=new Delta(null, false);
856 if (delta.getInit()) {
857 MySet<Edge> edgeset=new MySet<Edge>();
858 MySet<Edge> externaledgeset=new MySet<Edge>();
859 HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
860 HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
861 Stack<AllocNode> tovisit=new Stack<AllocNode>();
862 TempDescriptor tmpthis=fcall.getThis();
863 graph.callerEdges=new MySet<Edge>();
865 //Handle the this temp
866 processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, null);
868 //Go through each temp
869 processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, false);
871 //Traverse all reachable nodes
872 computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, null);
874 //Compute call targets
875 HashSet<MethodDescriptor> newtargets=computeTargets(fcall, newDelta);
878 fixMapping(fcall, newtargets, null, newDelta, callblock, callindex);
880 //Compute edges into region to splice out
881 computeExternalEdges(graph, delta, nodeset, null, externaledgeset);
883 //Splice out internal edges
884 removeEdges(graph, delta, nodeset, edgeset, externaledgeset);
886 //store data structures
887 graph.externalEdgeSet=externaledgeset;
888 graph.reachNode=nodeset;
889 graph.reachEdge=edgeset;
891 graph.callTargets=newtargets;
892 graph.callNodeAges=new HashSet<AllocNode>();
893 graph.callOldNodes=new HashSet<AllocNode>();
894 graph.callNewEdges=new HashMap<AllocNode, MySet<Edge>>();
895 graph.callOldEdges=new HashMap<Edge,MySet<Edge>>();
897 //Apply diffs to graph
898 applyDiffs(graph, delta, true);
900 MySet<Edge> edgeset=new MySet<Edge>();
901 MySet<Edge> externaledgeset=new MySet<Edge>();
902 HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
903 MySet<Edge> oldedgeset=graph.reachEdge;
904 HashSet<AllocNode> oldnodeset=graph.reachNode;
906 HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
907 Stack<AllocNode> tovisit=new Stack<AllocNode>();
908 TempDescriptor tmpthis=fcall.getThis();
909 //Fix up delta to get rid of unnecessary heap edge removals
910 for(Map.Entry<AllocNode, MySet<Edge>> entry : delta.heapedgeremove.entrySet()) {
911 for(Iterator<Edge> eit=entry.getValue().iterator(); eit.hasNext(); ) {
913 if (graph.callerEdges.contains(e))
918 //Fix up delta to get rid of unnecessary var edge removals
919 for(Map.Entry<TempDescriptor, MySet<Edge>> entry : delta.varedgeremove.entrySet()) {
920 for(Iterator<Edge> eit=entry.getValue().iterator(); eit.hasNext(); ) {
922 if (graph.callerEdges.contains(e))
927 //Handle the this temp
928 processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, oldnodeset);
930 //Go through each temp
931 processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, true);
932 //Go through each new heap edge that starts from old node
933 MySet<Edge> newedges=GraphManip.getDiffEdges(delta, oldnodeset);
934 edgeset.addAll(newedges);
935 for(Edge e : newedges) {
936 //Add new edges that start from old node to newDelta
938 if (!newDelta.heapedgeadd.containsKey(src)) {
939 newDelta.heapedgeadd.put(src, new MySet<Edge>());
941 newDelta.heapedgeadd.get(src).add(e.makeOld());
942 if (!nodeset.contains(e.dst)&&!oldnodeset.contains(e.dst)) {
948 //Traverse all reachable nodes
949 computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, oldnodeset);
950 //Compute call targets
951 HashSet<MethodDescriptor> newtargets=computeTargets(fcall, newDelta);
952 graph.callTargets.addAll(newtargets);
954 //add in new nodeset and edgeset
955 oldnodeset.addAll(nodeset);
956 oldedgeset.addAll(edgeset);
958 fixMapping(fcall, graph.callTargets, oldedgeset, newDelta, callblock, callindex);
959 //Compute edges into region to splice out
960 computeExternalEdges(graph, delta, oldnodeset, nodeset, externaledgeset);
962 //Splice out internal edges
963 removeEdges(graph, delta, nodeset, edgeset, externaledgeset);
965 //Add external edges back in
966 processCallExternal(graph, delta, externaledgeset);
968 //Move new edges that should be summarized
969 processSummarization(graph, delta);
971 Set<FlatSESEEnterNode> seseCallers=OoOJava?taskAnalysis.getTransitiveExecutingRBlocks(fcall):null;
972 //Check if the new nodes allow us to insert a new edge
973 for(AllocNode node : nodeset) {
974 if (graph.callNewEdges.containsKey(node)) {
975 for(Iterator<Edge> eit=graph.callNewEdges.get(node).iterator(); eit.hasNext(); ) {
977 if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&&
978 (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) {
979 Edge edgetoadd=e.copy(); //we need our own copy to modify below
981 if (seseCallers!=null)
982 edgetoadd.taintModify(seseCallers);
983 mergeCallEdge(graph, delta, edgetoadd);
989 for(Edge e : edgeset) {
990 //See if these edges would allow an old edge to be added
991 if (graph.callOldEdges.containsKey(e)) {
992 for(Edge adde : graph.callOldEdges.get(e)) {
993 Edge ecopy=adde.copy();
994 ecopy.statuspredicate=e.statuspredicate;
995 mergeCallEdge(graph, delta, ecopy);
1000 //Add in new external edges
1001 graph.externalEdgeSet.addAll(externaledgeset);
1002 //Apply diffs to graph
1003 applyDiffs(graph, delta);
1008 void processSummarization(Graph graph, Delta delta) {
1009 processSumHeapEdgeSet(delta.heapedgeadd, delta, graph);
1010 processSumHeapEdgeSet(delta.baseheapedge, delta, graph);
1011 processSumVarEdgeSet(delta.varedgeadd, delta, graph);
1012 processSumVarEdgeSet(delta.basevaredge, delta, graph);
1015 void processSumVarEdgeSet(HashMap<TempDescriptor, MySet<Edge>> map, Delta delta, Graph graph) {
1016 MySet<Edge> edgestoadd=new MySet<Edge>();
1017 MySet<Edge> edgestoremove=new MySet<Edge>();
1018 for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> eit=map.entrySet().iterator(); eit.hasNext(); ) {
1019 Map.Entry<TempDescriptor, MySet<Edge>> entry=eit.next();
1020 MySet<Edge> edgeset=entry.getValue();
1022 for(Edge e : edgeset) {
1024 boolean rewrite=false;
1025 if (copy.dst!=null&&graph.callNodeAges.contains(copy.dst)) {
1026 copy.dst=allocFactory.getAllocNode(copy.dst, true);
1030 edgestoremove.add(e);
1031 edgestoadd.add(copy);
1035 for(Edge e : edgestoremove) {
1036 if (!graph.callerEdges.contains(e))
1037 delta.removeVarEdge(e);
1039 for(Edge e : edgestoadd) {
1040 delta.addVarEdge(e);
1044 public Alloc getAllocationSiteFromFlatNew(FlatNew node) {
1045 return allocFactory.getAllocNode(node, false).getAllocSite();
1048 void processSumHeapEdgeSet(HashMap<AllocNode, MySet<Edge>> map, Delta delta, Graph graph) {
1049 MySet<Edge> edgestoadd=new MySet<Edge>();
1050 MySet<Edge> edgestoremove=new MySet<Edge>();
1051 for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> eit=map.entrySet().iterator(); eit.hasNext(); ) {
1052 Map.Entry<AllocNode, MySet<Edge>> entry=eit.next();
1053 AllocNode node=entry.getKey();
1054 MySet<Edge> edgeset=entry.getValue();
1056 for(Edge e : edgeset) {
1058 boolean rewrite=false;
1059 if (copy.src!=null&&graph.callNodeAges.contains(copy.src)) {
1060 copy.src=allocFactory.getAllocNode(copy.src, true);
1063 if (copy.dst!=null&&graph.callNodeAges.contains(copy.dst)) {
1064 copy.dst=allocFactory.getAllocNode(copy.dst, true);
1068 edgestoremove.add(e);
1069 edgestoadd.add(copy);
1073 for(Edge e : edgestoremove) {
1074 if (!graph.callerEdges.contains(e))
1075 delta.removeHeapEdge(e);
1077 for(Edge e : edgestoadd) {
1078 delta.addHeapEdge(e);
1082 //Handle external edges
1083 void processCallExternal(Graph graph, Delta newDelta, MySet<Edge> externalEdgeSet) {
1084 //Add external edges in
1085 for(Edge e : externalEdgeSet) {
1086 //First did we age the source
1087 Edge newedge=e.copy();
1088 if (newedge.src!=null&&!e.src.isSummary()&&graph.callNodeAges.contains(e.src)) {
1089 AllocNode summaryNode=allocFactory.getAllocNode(newedge.src, true);
1090 newedge.src=summaryNode;
1093 if (graph.callNodeAges.contains(e.dst)&&!e.dst.isSummary()) {
1094 if (graph.callOldNodes.contains(e.dst)) {
1096 Edge copy=newedge.copy();
1097 mergeEdge(graph, newDelta, copy);
1099 //Now add summarized node
1100 newedge.dst=allocFactory.getAllocNode(newedge.dst, true);
1101 mergeCallEdge(graph, newDelta, newedge);
1103 //Add edge to single node
1104 mergeEdge(graph, newDelta, newedge);
1109 /* This function applies callee deltas to the caller heap. */
1111 Delta applyCallDelta(Delta delta, BBlock bblock) {
1112 Delta newDelta=new Delta(null, false);
1113 Vector<FlatNode> nodes=bblock.nodes();
1114 PPoint ppoint=delta.getBlock();
1115 FlatCall fcall=(FlatCall)nodes.get(ppoint.getIndex());
1116 Graph graph=graphMap.get(fcall);
1117 Graph oldgraph=(ppoint.getIndex()==0)?
1118 bbgraphMap.get(bblock):
1119 graphMap.get(nodes.get(ppoint.getIndex()-1));
1120 Set<FlatSESEEnterNode> seseCallers=OoOJava?taskAnalysis.getTransitiveExecutingRBlocks(fcall):null;
1122 //Age outside nodes if necessary
1123 for(Iterator<AllocNode> nodeit=delta.addNodeAges.iterator(); nodeit.hasNext(); ) {
1124 AllocNode node=nodeit.next();
1125 if (!graph.callNodeAges.contains(node)) {
1126 graph.callNodeAges.add(node);
1127 newDelta.addNodeAges.add(node);
1129 AllocNode summaryAdd=null;
1130 if (!graph.reachNode.contains(node)&&!node.isSummary()) {
1131 /* Need to age node in existing graph*/
1133 AllocNode summaryNode=allocFactory.getAllocNode(node, true);
1135 if (!graph.callNodeAges.contains(summaryNode)) {
1136 graph.callNodeAges.add(summaryNode);
1137 newDelta.addNodeAges.add(summaryNode);
1138 summaryAdd=summaryNode;
1140 summarizeInGraph(graph, newDelta, node);
1143 if (graph.callNewEdges.containsKey(node)) {
1144 for(Iterator<Edge> eit=graph.callNewEdges.get(node).iterator(); eit.hasNext(); ) {
1146 if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&&
1147 (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) {
1148 Edge edgetoadd=e.copy(); //we need our own copy to modify below
1150 if (seseCallers!=null)
1151 edgetoadd.taintModify(seseCallers);
1152 mergeCallEdge(graph, newDelta, edgetoadd);
1156 //do the summary node if we added that also...
1159 } while(node!=null);
1163 for(Map.Entry<AllocNode, MySet<Edge>> entry : delta.heapedgeadd.entrySet()) {
1164 for(Edge e : entry.getValue()) {
1165 boolean addedge=false;
1166 Edge edgetoadd=null;
1167 if (e.statuspredicate==Edge.NEW) {
1168 if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&&
1169 (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) {
1170 edgetoadd=e.copy(); //we need our own copy to modify below
1172 graph.addCallEdge(e);
1175 Edge[] edgeArray=e.makeStatus(allocFactory);
1177 int statuspredicate=0;
1178 for(int i=0; i<edgeArray.length; i++) {
1179 Edge origEdgeKey=edgeArray[i];
1180 if (graph.reachEdge.contains(origEdgeKey)) {
1181 Edge origEdge=graph.reachEdge.get(origEdgeKey);
1182 //copy the predicate
1183 statuspredicate=statuspredicate|origEdge.statuspredicate;
1185 if (!graph.callOldEdges.containsKey(origEdgeKey)) {
1186 graph.callOldEdges.put(origEdgeKey, new MySet<Edge>());
1188 if (graph.callOldEdges.get(origEdgeKey).contains(e)) {
1189 Edge olde=graph.callOldEdges.get(origEdgeKey).get(e);
1190 graph.callOldEdges.get(origEdgeKey).add(olde.merge(e));
1192 graph.callOldEdges.get(origEdgeKey).add(e);
1195 if (statuspredicate!=0) {
1197 newe.statuspredicate=statuspredicate;
1201 if (seseCallers!=null&&edgetoadd!=null)
1202 edgetoadd.taintModify(seseCallers);
1203 mergeCallEdge(graph, newDelta, edgetoadd);
1207 processCallExternal(graph, newDelta, graph.externalEdgeSet);
1209 //Add edge for return value
1210 if (fcall.getReturnTemp()!=null) {
1211 MySet<Edge> returnedge=delta.varedgeadd.get(returntmp);
1212 if (returnedge!=null)
1213 for(Edge e : returnedge) {
1214 //skip the edge if types don't allow it...
1215 if (!typeUtil.isSuperorType(fcall.getReturnTemp().getType(), e.dst.getType()))
1217 Edge newedge=e.copy();
1218 newedge.srcvar=fcall.getReturnTemp();
1219 if (seseCallers!=null)
1220 newedge.taintModify(seseCallers);
1221 mergeEdge(graph, newDelta, newedge);
1224 applyDiffs(graph, newDelta);
1228 public void mergeEdge(Graph graph, Delta newDelta, Edge edgetoadd) {
1229 if (edgetoadd!=null) {
1230 Edge match=graph.getMatch(edgetoadd);
1232 if (match==null||!match.subsumes(edgetoadd)) {
1233 Edge mergededge=edgetoadd.merge(match);
1234 newDelta.addEdge(mergededge);
1239 /* This is a call produced edge...need to remember this */
1241 public void mergeCallEdge(Graph graph, Delta newDelta, Edge edgetoadd) {
1242 if (edgetoadd!=null) {
1243 newDelta.addEdgeClear(edgetoadd);
1245 Edge match=graph.getMatch(edgetoadd);
1247 if (match==null||!match.subsumes(edgetoadd)) {
1248 Edge mergededge=edgetoadd.merge(match);
1249 newDelta.addEdge(mergededge);
1250 graph.callerEdges.add(mergededge);
1256 /* Summarizes out of context nodes in graph */
1257 void summarizeInGraph(Graph graph, Delta newDelta, AllocNode singleNode) {
1258 AllocNode summaryNode=allocFactory.getAllocNode(singleNode, true);
1260 //Handle outgoing heap edges
1261 MySet<Edge> edgeset=graph.getEdges(singleNode);
1263 for(Edge e : edgeset) {
1264 Edge rewrite=e.rewrite(singleNode, summaryNode);
1266 newDelta.removeHeapEdge(e);
1267 mergeCallEdge(graph, newDelta, rewrite);
1270 //Handle incoming edges
1271 MySet<Edge> backedges=graph.getBackEdges(singleNode);
1272 for(Edge e : backedges) {
1273 if (e.dst==singleNode) {
1274 //Need to get original edge so that predicate will be correct
1275 Edge match=graph.getMatch(e);
1277 Edge rewrite=match.rewrite(singleNode, summaryNode);
1278 newDelta.removeEdge(match);
1279 mergeCallEdge(graph, newDelta, rewrite);
1285 void applyDiffs(Graph graph, Delta delta) {
1286 applyDiffs(graph, delta, false);
1289 void applyDiffs(Graph graph, Delta delta, boolean genbackwards) {
1290 //build backwards map if requested
1291 if (genbackwards&&graph.backMap==null) {
1292 graph.backMap=new HashMap<AllocNode, MySet<Edge>>();
1293 if (graph.parent.backMap==null) {
1294 graph.parent.backMap=new HashMap<AllocNode, MySet<Edge>>();
1295 for(Map.Entry<AllocNode, MySet<Edge>> entry : graph.nodeMap.entrySet()) {
1296 for(Edge e : entry.getValue()) {
1297 if (!graph.parent.backMap.containsKey(e.dst))
1298 graph.parent.backMap.put(e.dst, new MySet<Edge>());
1299 graph.parent.backMap.get(e.dst).add(e);
1302 for(Map.Entry<TempDescriptor, MySet<Edge>> entry : graph.varMap.entrySet()) {
1303 for(Edge e : entry.getValue()) {
1304 if (!graph.parent.backMap.containsKey(e.dst))
1305 graph.parent.backMap.put(e.dst, new MySet<Edge>());
1306 graph.parent.backMap.get(e.dst).add(e);
1312 //Add hidden base edges
1313 for(Map.Entry<AllocNode, MySet<Edge>> e : delta.baseheapedge.entrySet()) {
1314 AllocNode node=e.getKey();
1315 MySet<Edge> edges=e.getValue();
1316 if (graph.nodeMap.containsKey(node)) {
1317 MySet<Edge> nodeEdges=graph.nodeMap.get(node);
1318 nodeEdges.addAll(edges);
1323 for(Map.Entry<AllocNode, MySet<Edge>> e : delta.heapedgeremove.entrySet()) {
1324 AllocNode node=e.getKey();
1325 MySet<Edge> edgestoremove=e.getValue();
1326 if (graph.nodeMap.containsKey(node)) {
1327 //Just apply diff to current map
1328 graph.nodeMap.get(node).removeAll(edgestoremove);
1330 //Generate diff from parent graph
1331 MySet<Edge> parentedges=graph.parent.nodeMap.get(node);
1332 if (parentedges!=null) {
1333 MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
1334 graph.nodeMap.put(node, newedgeset);
1340 for(Map.Entry<AllocNode, MySet<Edge>> e : delta.heapedgeadd.entrySet()) {
1341 AllocNode node=e.getKey();
1342 MySet<Edge> edgestoadd=e.getValue();
1343 //If we have not done a subtract, then
1344 if (!graph.nodeMap.containsKey(node)) {
1345 //Copy the parent entry
1346 if (graph.parent.nodeMap.containsKey(node))
1347 graph.nodeMap.put(node, (MySet<Edge>)graph.parent.nodeMap.get(node).clone());
1349 graph.nodeMap.put(node, new MySet<Edge>());
1351 Edge.mergeEdgesInto(graph.nodeMap.get(node),edgestoadd);
1353 for(Edge eadd : edgestoadd) {
1354 if (!graph.backMap.containsKey(eadd.dst))
1355 graph.backMap.put(eadd.dst, new MySet<Edge>());
1356 graph.backMap.get(eadd.dst).add(eadd);
1362 for(Map.Entry<TempDescriptor, MySet<Edge>> e : delta.varedgeremove.entrySet()) {
1363 TempDescriptor tmp=e.getKey();
1364 MySet<Edge> edgestoremove=e.getValue();
1366 if (graph.varMap.containsKey(tmp)) {
1367 //Just apply diff to current map
1368 graph.varMap.get(tmp).removeAll(edgestoremove);
1369 } else if (graph.parent.varMap.containsKey(tmp)) {
1370 //Generate diff from parent graph
1371 MySet<Edge> parentedges=graph.parent.varMap.get(tmp);
1372 MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
1373 graph.varMap.put(tmp, newedgeset);
1378 for(Map.Entry<TempDescriptor, MySet<Edge>> e : delta.varedgeadd.entrySet()) {
1379 TempDescriptor tmp=e.getKey();
1380 MySet<Edge> edgestoadd=e.getValue();
1381 if (graph.varMap.containsKey(tmp)) {
1382 Edge.mergeEdgesInto(graph.varMap.get(tmp), edgestoadd);
1383 } else if (graph.parent.varMap.containsKey(tmp)) {
1384 graph.varMap.put(tmp, new MySet<Edge>(graph.parent.varMap.get(tmp)));
1385 Edge.mergeEdgesInto(graph.varMap.get(tmp), edgestoadd);
1387 graph.varMap.put(tmp, (MySet<Edge>)edgestoadd.clone());
1389 for(Edge eadd : edgestoadd) {
1390 if (!graph.backMap.containsKey(eadd.dst))
1391 graph.backMap.put(eadd.dst, new MySet<Edge>());
1392 graph.backMap.get(eadd.dst).add(eadd);
1397 //Add node additions
1398 for(AllocNode node : delta.addNodeAges) {
1399 graph.nodeAges.add(node);
1402 for(Map.Entry<AllocNode, Boolean> nodeentry : delta.addOldNodes.entrySet()) {
1403 AllocNode node=nodeentry.getKey();
1404 Boolean ispresent=nodeentry.getValue();
1405 graph.oldNodes.put(node, ispresent);
1409 boolean isINACC(FlatNode node) {
1412 switch(node.kind()) {
1413 case FKind.FlatSetFieldNode: {
1414 FlatSetFieldNode n=(FlatSetFieldNode)node;
1415 return !accessible.isAccessible(n, n.getDst());
1418 case FKind.FlatSetElementNode: {
1419 FlatSetElementNode n=(FlatSetElementNode)node;
1420 return !accessible.isAccessible(n, n.getDst());
1423 case FKind.FlatFieldNode: {
1424 FlatFieldNode n=(FlatFieldNode)node;
1425 return !accessible.isAccessible(n, n.getSrc());
1428 case FKind.FlatElementNode: {
1429 FlatElementNode n=(FlatElementNode)node;
1430 return !accessible.isAccessible(n, n.getSrc());
1436 Delta processSetFieldElementNode(FlatNode node, Delta delta, Graph graph) {
1440 if (node.kind()==FKind.FlatSetElementNode) {
1441 FlatSetElementNode fen=(FlatSetElementNode) node;
1446 FlatSetFieldNode ffn=(FlatSetFieldNode) node;
1452 if (delta.getInit()) {
1453 MySet<Edge> dstEdges=GraphManip.getEdges(graph, delta, dst);
1455 if (OoOJava&&!accessible.isAccessible(node, dst)) {
1456 Taint dstStallTaint=Taint.factory(node, dst, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1457 dstEdges=Edge.taintAll(dstEdges, dstStallTaint);
1458 updateVarDelta(graph, delta, dst, dstEdges, null);
1461 effectsAnalysis.analyzeFlatSetFieldNode(dstEdges, fd, node);
1464 //Do nothing for non pointers
1465 if (!src.getType().isPtr()) {
1466 if (mustProcess.contains(node)) {
1467 applyDiffs(graph, delta);
1472 MySet<Edge> srcEdges=GraphManip.getEdges(graph, delta, src);
1473 if (OoOJava&&!accessible.isAccessible(node, src)) {
1474 Taint srcStallTaint=Taint.factory(node, src, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1475 srcEdges=Edge.taintAll(srcEdges, srcStallTaint);
1476 updateVarDelta(graph, delta, src, srcEdges, null);
1479 MySet<Edge> edgesToAdd=GraphManip.genEdges(dstEdges, fd, srcEdges);
1480 MySet<Edge> edgesToRemove=null;
1481 if (dstEdges.size()==1&&!dstEdges.iterator().next().dst.isSummary()&&fd!=null) {
1482 /* Can do a strong update */
1483 edgesToRemove=GraphManip.getEdges(graph, delta, dstEdges, fd);
1484 graph.strongUpdateSet=edgesToRemove;
1486 graph.strongUpdateSet=new MySet<Edge>();
1489 updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
1490 applyDiffs(graph, delta);
1492 MySet<Edge> newDstEdges=GraphManip.getDiffEdges(delta, dst);
1494 if (OoOJava&&!accessible.isAccessible(node, dst)) {
1495 Taint dstStallTaint=Taint.factory(node, dst, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1496 newDstEdges=Edge.taintAll(newDstEdges, dstStallTaint);
1497 updateVarDelta(graph, delta, dst, newDstEdges, null);
1501 effectsAnalysis.analyzeFlatSetFieldNode(newDstEdges, fd, node);
1504 if (!src.getType().isPtr()) {
1505 if (mustProcess.contains(node)) {
1506 applyDiffs(graph, delta);
1511 /* Next look at new sources */
1513 MySet<Edge> edgesToAdd=new MySet<Edge>();
1514 MySet<Edge> newSrcEdges=GraphManip.getDiffEdges(delta, src);
1515 MySet<Edge> srcEdges=GraphManip.getEdges(graph, delta, src);
1516 HashSet<AllocNode> dstNodes=GraphManip.getNodes(graph, delta, dst);
1518 if (OoOJava&&!accessible.isAccessible(node, src)) {
1519 Taint srcStallTaint=Taint.factory(node, src, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1520 newSrcEdges=Edge.taintAll(newSrcEdges, srcStallTaint);
1521 updateVarDelta(graph, delta, src, newSrcEdges, null);
1524 MySet<Edge> edgesToRemove=null;
1525 if (newDstEdges.size()!=0) {
1526 if (dstNodes.size()>1&&!dstNodes.iterator().next().isSummary()&&fd!=null) {
1527 /* Need to undo strong update */
1528 if (graph.strongUpdateSet!=null) {
1529 edgesToAdd.addAll(graph.strongUpdateSet);
1530 graph.strongUpdateSet=null; //Prevent future strong updates
1532 } else if (dstNodes.size()==1&&newDstEdges.size()==1&&!newDstEdges.iterator().next().dst.isSummary()&&graph.strongUpdateSet!=null&&fd!=null) {
1533 edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
1534 graph.strongUpdateSet.addAll(edgesToRemove);
1536 Edge.mergeEdgesInto(edgesToAdd, GraphManip.genEdges(newDstEdges, fd, srcEdges));
1540 if (graph.strongUpdateSet!=null&&fd!=null) {
1541 MySet<Edge> otherEdgesToRemove=GraphManip.getDiffEdges(delta, dstNodes, fd);
1542 if (edgesToRemove!=null)
1543 edgesToRemove.addAll(otherEdgesToRemove);
1545 edgesToRemove=otherEdgesToRemove;
1546 graph.strongUpdateSet.addAll(otherEdgesToRemove);
1549 //Next look at new destinations
1550 Edge.mergeEdgesInto(edgesToAdd, GraphManip.genEdges(dstNodes, fd, newSrcEdges));
1553 updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
1554 applyDiffs(graph, delta);
1559 Delta processCopyNode(FlatNode node, Delta delta, Graph graph) {
1563 if (node.kind()==FKind.FlatOpNode) {
1564 FlatOpNode fon=(FlatOpNode) node;
1567 } else if (node.kind()==FKind.FlatReturnNode) {
1568 FlatReturnNode frn=(FlatReturnNode)node;
1569 src=frn.getReturnTemp();
1571 if (src==null||!src.getType().isPtr()) {
1573 applyDiffs(graph, delta);
1577 FlatCastNode fcn=(FlatCastNode) node;
1581 if (delta.getInit()) {
1582 MySet<Edge> srcedges=GraphManip.getEdges(graph, delta, src);
1583 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, srcedges);
1584 MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
1585 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1586 applyDiffs(graph, delta);
1588 /* First compute new src nodes */
1589 MySet<Edge> newSrcEdges=GraphManip.getDiffEdges(delta, src);
1591 /* Compute the union, and then the set of edges */
1592 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, newSrcEdges);
1594 /* Compute set of edges to remove */
1595 MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
1598 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1599 applyDiffs(graph, delta);
1604 Delta processFieldElementNode(FlatNode node, Delta delta, Graph graph) {
1608 TaintSet taint=null;
1610 if (node.kind()==FKind.FlatElementNode) {
1611 FlatElementNode fen=(FlatElementNode) node;
1616 FlatFieldNode ffn=(FlatFieldNode) node;
1621 if (OoOJava&&!accessible.isAccessible(node, src)) {
1622 taint=TaintSet.factory(Taint.factory(node, src, AllocFactory.dummySite, null, ReachGraph.predsEmpty));
1625 //Do nothing for non pointers
1626 if (delta.getInit()) {
1627 MySet<Edge> srcedges=GraphManip.getEdges(graph, delta, src);
1630 srcedges=Edge.taintAll(srcedges, taint);
1631 updateVarDelta(graph, delta, src, srcedges, null);
1633 effectsAnalysis.analyzeFlatFieldNode(srcedges, fd, node);
1635 if (!dst.getType().isPtr()) {
1636 if (mustProcess.contains(node)) {
1637 applyDiffs(graph, delta);
1642 MySet<Edge> edgesToAdd=GraphManip.dereference(graph, delta, dst, srcedges, fd, node);
1643 MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
1645 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1646 applyDiffs(graph, delta);
1648 MySet<Edge> newsrcedges=GraphManip.getDiffEdges(delta, src);
1651 newsrcedges=Edge.taintAll(newsrcedges, taint);
1652 updateVarDelta(graph, delta, src, newsrcedges, null);
1654 effectsAnalysis.analyzeFlatFieldNode(newsrcedges, fd, node);
1656 if (!dst.getType().isPtr()) {
1657 if (mustProcess.contains(node)) {
1658 applyDiffs(graph, delta);
1662 /* First compute new objects we read fields of */
1663 MySet<Edge> allsrcedges=GraphManip.getEdges(graph, delta, src);
1664 MySet<Edge> edgesToAdd=GraphManip.diffDereference(delta, dst, allsrcedges, fd, node);
1665 /* Next compute new targets of fields */
1666 MySet<Edge> newfdedges=GraphManip.dereference(graph, delta, dst, newsrcedges, fd, node);
1668 /* Compute the union, and then the set of edges */
1669 Edge.mergeEdgesInto(edgesToAdd, newfdedges);
1671 /* Compute set of edges to remove */
1672 MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
1676 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1677 applyDiffs(graph, delta);
1683 void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1684 MySet<Edge> edgeAdd=delta.varedgeadd.get(tmp);
1685 MySet<Edge> edgeRemove=delta.varedgeremove.get(tmp);
1686 MySet<Edge> existingEdges=graph.getEdges(tmp);
1687 if (edgestoRemove!=null)
1688 for(Edge e : edgestoRemove) {
1689 //remove edge from delta
1692 //if the edge is already in the graph, add an explicit remove to the delta
1693 if (existingEdges.contains(e))
1694 delta.removeVarEdge(e);
1696 for(Edge e : edgestoAdd) {
1697 //Remove the edge from the remove set
1698 if (edgeRemove!=null)
1699 edgeRemove.remove(e);
1700 //Explicitly add it to the add set unless it is already in the graph
1701 if (typeUtil.isSuperorType(tmp.getType(), e.dst.getType())) {
1702 if (!existingEdges.contains(e)) {
1703 delta.addVarEdge(e);
1705 //See if the old edge subsumes the new one
1706 Edge olde=existingEdges.get(e);
1707 if (!olde.subsumes(e)) {
1708 delta.addVarEdge(olde.merge(e));
1715 void updateHeapDelta(Graph graph, Delta delta, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1716 if (edgestoRemove!=null)
1717 for(Edge e : edgestoRemove) {
1718 AllocNode src=e.src;
1719 MySet<Edge> edgeAdd=delta.heapedgeadd.get(src);
1720 MySet<Edge> existingEdges=graph.getEdges(src);
1721 //remove edge from delta
1724 //if the edge is already in the graph, add an explicit remove to the delta
1725 if (existingEdges.contains(e)) {
1726 delta.removeHeapEdge(e);
1729 if (edgestoAdd!=null)
1730 for(Edge e : edgestoAdd) {
1731 AllocNode src=e.src;
1732 MySet<Edge> edgeRemove=delta.heapedgeremove.get(src);
1733 MySet<Edge> existingEdges=graph.getEdges(src);
1734 //Remove the edge from the remove set
1735 if (edgeRemove!=null)
1736 edgeRemove.remove(e);
1737 //Explicitly add it to the add set unless it is already in the graph
1738 if (!existingEdges.contains(e)) {
1739 delta.addHeapEdge(e);
1741 //See if the old edge subsumes the new one
1742 Edge olde=existingEdges.get(e);
1743 if (!olde.subsumes(e)) {
1744 delta.addHeapEdge(olde.merge(e));
1750 Delta processFlatNop(FlatNode node, Delta delta, Graph graph) {
1751 applyDiffs(graph, delta);
1755 Delta processNewNode(FlatNew node, Delta delta, Graph graph) {
1756 AllocNode summary=allocFactory.getAllocNode(node, true);
1757 AllocNode single=allocFactory.getAllocNode(node, false);
1758 TempDescriptor tmp=node.getDst();
1760 if (delta.getInit()) {
1761 /* We don't have to deal with summarization here... The
1762 * intuition is that this is the only place where we generate
1763 * nodes for this allocation site and this is the first time
1764 * we've analyzed this site */
1767 Edge e=new Edge(tmp, single);
1768 //Build new Edge set
1769 MySet<Edge> newedges=new MySet<Edge>();
1771 //Add it into the diffs
1772 delta.varedgeadd.put(tmp, newedges);
1773 //Remove the old edges
1774 MySet<Edge> oldedges=graph.getEdges(tmp);
1775 if (!oldedges.isEmpty())
1776 delta.varedgeremove.put(tmp, (MySet<Edge>)oldedges);
1777 //Note that we create a single node
1778 delta.addNodeAges.add(single);
1780 if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1781 delta.addOldNodes.put(single, Boolean.FALSE);
1784 /* 1. Fix up the variable edge additions */
1785 for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.varedgeadd.entrySet().iterator(); entryIt.hasNext(); ) {
1786 Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1788 if (entry.getKey()==tmp) {
1789 /* Check if this is the tmp we overwrite */
1792 /* Otherwise, check if the target of the edge is changed... */
1793 summarizeSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary);
1797 /* 2. Fix up the base variable edges */
1799 for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.basevaredge.entrySet().iterator(); entryIt.hasNext(); ) {
1800 Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1801 TempDescriptor entrytmp=entry.getKey();
1802 if (entrytmp==tmp) {
1803 /* Check is this is the tmp we overwrite, if so add to remove set */
1804 Util.relationUpdate(delta.varedgeremove, tmp, null, entry.getValue());
1805 } else if (graph.varMap.containsKey(entrytmp)) {
1806 /* Check if the target of the edge is changed */
1807 MySet<Edge> newset=(MySet<Edge>)entry.getValue().clone();
1808 MySet<Edge> removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary);
1809 Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset);
1810 Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset);
1812 /* Check if the target of the edge is changed */
1813 MySet<Edge> newset=(MySet<Edge>)entry.getValue().clone();
1814 MySet<Edge> removeset=shrinkSet(newset, graph.parent.varMap.get(entrytmp), single, summary);
1815 Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset);
1816 Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset);
1821 /* 3. Fix up heap edge additions */
1823 HashMap<AllocNode, MySet<Edge>> addheapedge=new HashMap<AllocNode, MySet<Edge>>();
1824 for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.heapedgeadd.entrySet().iterator(); entryIt.hasNext(); ) {
1825 Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1826 MySet<Edge> edgeset=entry.getValue();
1827 AllocNode allocnode=entry.getKey();
1828 if (allocnode==single) {
1830 summarizeSet(edgeset, graph.nodeMap.get(summary), single, summary);
1831 addheapedge.put(summary, edgeset);
1833 summarizeSet(edgeset, graph.nodeMap.get(allocnode), single, summary);
1837 /* Merge in diffs */
1839 for(Map.Entry<AllocNode, MySet<Edge>> entry : addheapedge.entrySet()) {
1840 AllocNode allocnode=entry.getKey();
1841 Util.relationUpdate(delta.heapedgeadd, allocnode, null, entry.getValue());
1844 /* 4. Fix up the base heap edges */
1846 for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.baseheapedge.entrySet().iterator(); entryIt.hasNext(); ) {
1847 Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1848 MySet<Edge> edgeset=entry.getValue();
1849 AllocNode allocnode=entry.getKey();
1850 if (allocnode==single) {
1853 AllocNode addnode=(allocnode==single)?summary:allocnode;
1855 MySet<Edge> newset=(MySet<Edge>)edgeset.clone();
1856 MySet<Edge> removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary);
1857 Util.relationUpdate(delta.heapedgeadd, addnode, null, newset);
1858 Util.relationUpdate(delta.heapedgeremove, allocnode, null, removeset);
1861 /* Update Node Ages...If the base or addNodeAges set contains a
1862 * single node, it now should also contain a summary node... No
1863 * need to generate a single node as that has already been
1865 if (delta.baseNodeAges.contains(single)||delta.addNodeAges.contains(single)) {
1866 delta.addNodeAges.add(summary);
1869 //Kill the old node if someone tries to add it
1870 if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1871 delta.addOldNodes.put(single, Boolean.FALSE);
1875 //Apply incoming diffs to graph
1876 applyDiffs(graph, delta);
1881 /* This function builds a new edge set where oldnode is summarized into new node */
1883 void summarizeSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode sumnode) {
1884 MySet<Edge> newSet=null;
1885 for(Iterator<Edge> edgeit=edgeset.iterator(); edgeit.hasNext(); ) {
1886 Edge e=edgeit.next();
1887 if (e.dst==oldnode||e.src==oldnode) {
1889 newSet=new MySet<Edge>();
1894 if (e.dst==oldnode) {
1897 if (e.src==oldnode) {
1900 if (oldedgeset==null||!oldedgeset.contains(e))
1905 edgeset.addAll(newSet);
1908 /* Shrinks the incoming set to just include rewritten values.
1909 * Returns a set of the original rewritten values */
1911 MySet<Edge> shrinkSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode newnode) {
1912 MySet<Edge> newSet=null;
1913 MySet<Edge> removeSet=null;
1914 for(Iterator<Edge> edgeit=edgeset.iterator(); edgeit.hasNext(); ) {
1915 Edge e=edgeit.next();
1917 if (e.dst==oldnode||e.src==oldnode) {
1919 newSet=new MySet<Edge>();
1920 removeSet=new MySet<Edge>();
1929 if (oldedgeset==null||!oldedgeset.contains(e))
1934 edgeset.addAll(newSet);
1938 /* This function returns a completely new Delta... It is safe to
1941 Delta applyInitDelta(Delta delta, BBlock block) {
1942 //Apply delta to graph
1943 boolean newGraph=false;
1944 if (!bbgraphMap.containsKey(block)) {
1945 bbgraphMap.put(block, new Graph(null));
1948 Graph graph=bbgraphMap.get(block);
1951 Delta newdelta=new Delta(null, true);
1952 //Add in heap edges and throw away original diff
1954 for(Map.Entry<AllocNode, MySet<Edge>> entry : delta.heapedgeadd.entrySet()) {
1955 graph.nodeMap.put(entry.getKey(), new MySet<Edge>(entry.getValue()));
1957 //Add in var edges and throw away original diff
1958 Set<TempDescriptor> livetemps=bblivetemps.get(block);
1960 for(Map.Entry<TempDescriptor, MySet<Edge>> entry : delta.varedgeadd.entrySet()) {
1961 if (livetemps.contains(entry.getKey()))
1962 graph.varMap.put(entry.getKey(), new MySet<Edge>(entry.getValue()));
1964 //Record that this is initial set...
1965 graph.nodeAges.addAll(delta.addNodeAges);
1967 for(Map.Entry<AllocNode, Boolean> oldentry : delta.addOldNodes.entrySet()) {
1968 if (oldentry.getValue().booleanValue()) {
1969 graph.oldNodes.put(oldentry.getKey(), Boolean.TRUE);
1974 Delta newdelta=new Delta(null, false);
1975 //merge in heap edges and variables
1976 mergeHeapEdges(graph, delta, newdelta);
1977 mergeVarEdges(graph, delta, newdelta, block);
1978 mergeAges(graph, delta, newdelta);
1983 /* This function merges in the heap edges. It updates delta to be
1986 void mergeHeapEdges(Graph graph, Delta delta, Delta newdelta) {
1988 for(Map.Entry<AllocNode, MySet<Edge>> heapedge : delta.heapedgeadd.entrySet()) {
1989 AllocNode nsrc=heapedge.getKey();
1990 MySet<Edge> edges=heapedge.getValue();
1992 if (graph.backMap!=null) {
1993 for(Edge e : edges) {
1994 if (!graph.backMap.containsKey(e.dst))
1995 graph.backMap.put(e.dst, new MySet<Edge>());
1996 graph.backMap.get(e.dst).add(e);
2000 if (!graph.nodeMap.containsKey(nsrc)) {
2001 graph.nodeMap.put(nsrc, new MySet<Edge>());
2003 MySet<Edge> dstedges=graph.nodeMap.get(nsrc);
2004 MySet<Edge> diffedges=new MySet<Edge>();
2005 for(Edge e : edges) {
2006 if (!dstedges.contains(e)) {
2007 //We have a new edge
2011 Edge origedge=dstedges.get(e);
2012 if (!origedge.subsumes(e)) {
2013 Edge mergededge=origedge.merge(e);
2014 diffedges.add(mergededge);
2015 dstedges.add(mergededge);
2019 //Done with edge set...
2020 if (diffedges.size()>0) {
2022 newdelta.baseheapedge.put(nsrc, diffedges);
2027 /* This function merges in the var edges. It updates delta to be
2030 void mergeVarEdges(Graph graph, Delta delta, Delta newdelta, BBlock block) {
2032 Set<TempDescriptor> livetemps=bblivetemps.get(block);
2034 for(Map.Entry<TempDescriptor, MySet<Edge>> varedge : delta.varedgeadd.entrySet()) {
2035 TempDescriptor tmpsrc=varedge.getKey();
2036 if (livetemps.contains(tmpsrc)) {
2037 MySet<Edge> edges=varedge.getValue();
2038 if (graph.backMap!=null) {
2039 for(Edge e : edges) {
2040 if (!graph.backMap.containsKey(e.dst))
2041 graph.backMap.put(e.dst, new MySet<Edge>());
2042 graph.backMap.get(e.dst).add(e);
2046 if (!graph.varMap.containsKey(tmpsrc)) {
2047 graph.varMap.put(tmpsrc, new MySet<Edge>());
2049 MySet<Edge> dstedges=graph.varMap.get(tmpsrc);
2050 MySet<Edge> diffedges=new MySet<Edge>();
2051 for(Edge e : edges) {
2052 if (!dstedges.contains(e)) {
2053 //We have a new edge
2057 Edge origedge=dstedges.get(e);
2058 if (!origedge.subsumes(e)) {
2059 Edge mergededge=origedge.merge(e);
2060 diffedges.add(mergededge);
2061 dstedges.add(mergededge);
2065 //Done with edge set...
2066 if (diffedges.size()>0) {
2068 newdelta.basevaredge.put(tmpsrc,diffedges);
2074 void mergeAges(Graph graph, Delta delta, Delta newDelta) {
2076 for(AllocNode node : delta.addNodeAges) {
2077 if (!graph.nodeAges.contains(node)) {
2078 graph.nodeAges.add(node);
2079 newDelta.baseNodeAges.add(node);
2082 for(Map.Entry<AllocNode, Boolean> oldentry : delta.addOldNodes.entrySet()) {
2083 AllocNode node=oldentry.getKey();
2084 boolean ispresent=oldentry.getValue().booleanValue();
2085 if (ispresent&&!graph.oldNodes.containsKey(node)) {
2086 graph.oldNodes.put(node, Boolean.TRUE);
2087 newDelta.baseOldNodes.put(node, Boolean.TRUE);