1 package Analysis.Pointer;
5 import Analysis.Pointer.BasicBlock.BBlock;
6 import Analysis.Pointer.AllocFactory.AllocNode;
10 HashMap<FlatMethod, BasicBlock> blockMap;
11 HashMap<BBlock, Graph> bbgraphMap;
12 HashMap<FlatNode, Graph> graphMap;
13 HashMap<FlatCall, Set<BBlock>> callMap;
14 HashMap<BBlock, Set<PPoint>> returnMap;
18 AllocFactory allocFactory;
19 LinkedList<Delta> toprocess;
20 TempDescriptor returntmp;
22 public Pointer(State state, TypeUtil typeUtil) {
24 this.blockMap=new HashMap<FlatMethod, BasicBlock>();
25 this.bbgraphMap=new HashMap<BBlock, Graph>();
26 this.graphMap=new HashMap<FlatNode, Graph>();
27 this.callMap=new HashMap<FlatCall, Set<BBlock>>();
28 this.returnMap=new HashMap<BBlock, Set<PPoint>>();
29 this.typeUtil=typeUtil;
30 this.allocFactory=new AllocFactory(state, typeUtil);
31 this.toprocess=new LinkedList<Delta>();
32 ClassDescriptor stringcd=typeUtil.getClass(TypeUtil.ObjectClass);
33 this.returntmp=new TempDescriptor("RETURNVAL", stringcd);
36 public BasicBlock getBBlock(FlatMethod fm) {
37 if (!blockMap.containsKey(fm))
38 blockMap.put(fm, BasicBlock.getBBlock(fm));
39 return blockMap.get(fm);
42 Delta buildInitialContext() {
43 MethodDescriptor md=typeUtil.getMain();
44 FlatMethod fm=state.getMethodFlat(md);
45 BasicBlock bb=getBBlock(fm);
46 BBlock start=bb.getStart();
47 Delta delta=new Delta(new PPoint(start), true);
48 MySet<Edge> arrayset=new MySet<Edge>();
49 MySet<Edge> varset=new MySet<Edge>();
50 Edge arrayedge=new Edge(allocFactory.StringArray, null, allocFactory.Strings);
51 Edge stringedge=new Edge(fm.getParameter(0), allocFactory.StringArray);
52 delta.addHeapEdge(arrayedge);
53 delta.addVarEdge(stringedge);
58 public void doAnalysis() {
59 toprocess.add(buildInitialContext());
61 while(!toprocess.isEmpty()) {
62 Delta delta=toprocess.remove();
63 PPoint ppoint=delta.getBlock();
64 BBlock bblock=ppoint.getBBlock();
65 Vector<FlatNode> nodes=bblock.nodes();
67 if (ppoint.getIndex()==-1) {
68 //Build base graph for entrance to this basic block
69 delta=applyInitDelta(delta, bblock);
71 startindex=ppoint.getIndex()+1;
72 delta=applyCallDelta(delta, bblock);
74 Graph graph=bbgraphMap.get(bblock);
76 //Compute delta at exit of each node
77 for(int i=startindex; i<nodes.size();i++) {
78 FlatNode currNode=nodes.get(i);
79 if (!graphMap.containsKey(currNode)) {
80 graphMap.put(currNode, new Graph(graph));
82 nodeGraph=graphMap.get(currNode);
83 delta=processNode(bblock, i, currNode, delta, nodeGraph);
85 generateFinalDelta(bblock, delta, nodeGraph);
90 for(Map.Entry<BBlock, Graph> e:bbgraphMap.entrySet()) {
93 PrintWriter pw=new PrintWriter(new FileWriter("BB"+debugindex+".dot"));
94 g.printGraph(pw, "BB");
96 } catch (Exception ex) {
102 for(Map.Entry<FlatNode, Graph> e:graphMap.entrySet()) {
103 FlatNode fn=e.getKey();
104 Graph g=e.getValue();
106 PrintWriter pw=new PrintWriter(new FileWriter("FN"+fn.toString().replace(' ','_')+".dot"));
107 g.printGraph(pw, fn.toString());
109 } catch (Exception ex) {
110 ex.printStackTrace();
114 for(FlatMethod fm:blockMap.keySet()) {
119 /* This function builds the last delta for a basic block. It
120 * handles the case for the first time the basic block is
123 void buildInitDelta(Graph graph, Delta newDelta) {
124 //First compute the set of temps
125 HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
126 tmpSet.addAll(graph.varMap.keySet());
127 tmpSet.addAll(graph.parent.varMap.keySet());
129 //Next build the temp map part of the delta
130 for(TempDescriptor tmp:tmpSet) {
131 MySet<Edge> edgeSet=new MySet<Edge>();
133 if (graph.varMap.containsKey(tmp))
134 edgeSet.addAll(graph.varMap.get(tmp));
136 edgeSet.addAll(graph.parent.varMap.get(tmp));
137 newDelta.varedgeadd.put(tmp, edgeSet);
140 //Next compute the set of src allocnodes
141 HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
142 nodeSet.addAll(graph.nodeMap.keySet());
143 nodeSet.addAll(graph.parent.nodeMap.keySet());
145 for(AllocNode node:nodeSet) {
146 MySet<Edge> edgeSet=new MySet<Edge>();
148 if (graph.nodeMap.containsKey(node))
149 edgeSet.addAll(graph.nodeMap.get(node));
151 edgeSet.addAll(graph.parent.nodeMap.get(node));
152 newDelta.heapedgeadd.put(node, edgeSet);
155 if (graph.nodeAges.contains(node))
156 newDelta.addNodeAges.add(node);
157 else if (graph.parent.nodeAges.contains(node))
158 newDelta.addNodeAges.add(node);
161 if (graph.oldNodes.containsKey(node)) {
162 if (graph.oldNodes.get(node).booleanValue())
163 newDelta.addOldNodes.put(node, Boolean.TRUE);
164 } else if (graph.parent.oldNodes.containsKey(node)) {
165 //parent graphs only contain true...no need to check
166 newDelta.addOldNodes.put(node, Boolean.TRUE);
171 /* This function build the delta for the exit of a basic block. */
173 void generateFinalDelta(BBlock bblock, Delta delta, Graph graph) {
174 Delta newDelta=new Delta(null, false);
175 if (delta.getInit()) {
176 buildInitDelta(graph, newDelta);
178 /* We can break the old delta...it is done being used */
179 /* First we will build variable edges */
180 HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
181 tmpSet.addAll(delta.basevaredge.keySet());
182 tmpSet.addAll(delta.varedgeadd.keySet());
183 for(TempDescriptor tmp:tmpSet) {
184 /* Start with the new incoming edges */
185 MySet<Edge> newbaseedge=delta.basevaredge.get(tmp);
186 /* Remove the remove set */
187 if (newbaseedge==null)
188 newbaseedge=new MySet<Edge>();
189 newbaseedge.removeAll(delta.varedgeremove.get(tmp));
190 /* Add in the new set*/
191 newbaseedge.addAll(delta.varedgeadd.get(tmp));
192 /* Store the results */
193 newDelta.varedgeadd.put(tmp, newbaseedge);
195 delta.basevaredge.clear();
197 /* Next we build heap edges */
198 HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
199 nodeSet.addAll(delta.baseheapedge.keySet());
200 nodeSet.addAll(delta.heapedgeadd.keySet());
201 nodeSet.addAll(delta.heapedgeremove.keySet());
202 for(AllocNode node:nodeSet) {
203 /* Start with the new incoming edges */
204 MySet<Edge> newheapedge=new MySet<Edge>(delta.baseheapedge.get(node));
205 /* Remove the remove set */
206 MySet<Edge> removeset=delta.heapedgeremove.get(node);
209 newheapedge.removeAll(removeset);
211 /* Add in the add set */
212 MySet<Edge> settoadd=delta.heapedgeadd.get(node);
214 newheapedge.addAll(settoadd);
215 newDelta.heapedgeadd.put(node, newheapedge);
217 /* Remove the newly created edges..no need to propagate a diff for those */
218 if (removeset!=null) {
219 removeset.removeAll(delta.baseheapedge.get(node));
220 newDelta.heapedgeremove.put(node, removeset);
224 /* Compute new ages */
225 newDelta.addNodeAges.addAll(delta.baseNodeAges);
226 newDelta.addNodeAges.addAll(delta.addNodeAges);
227 HashSet<AllocNode> oldNodes=new HashSet<AllocNode>();
229 /* Compute whether old nodes survive */
230 oldNodes.addAll(delta.baseOldNodes.keySet());
231 oldNodes.addAll(delta.addOldNodes.keySet());
232 for(AllocNode node:oldNodes) {
233 if (delta.addOldNodes.containsKey(node)) {
234 if (delta.addOldNodes.get(node).booleanValue()) {
235 newDelta.addOldNodes.put(node, Boolean.TRUE);
238 if (delta.baseOldNodes.get(node).booleanValue()) {
239 newDelta.addOldNodes.put(node, Boolean.TRUE);
245 /* Now we need to propagate newdelta */
246 if (!newDelta.heapedgeadd.isEmpty()||!newDelta.heapedgeremove.isEmpty()||!newDelta.varedgeadd.isEmpty()||!newDelta.addNodeAges.isEmpty()||!newDelta.addOldNodes.isEmpty()) {
247 /* We have a delta to propagate */
249 if (returnMap.containsKey(bblock)) {
253 for(PPoint caller:returnMap.get(bblock)) {
255 newDelta.setBlock(caller);
256 toprocess.add(newDelta);
259 Delta d=newDelta.diffBlock(caller);
265 Vector<BBlock> blockvector=bblock.next();
266 for(int i=0;i<blockvector.size();i++) {
268 newDelta.setBlock(new PPoint(blockvector.get(i)));
269 toprocess.add(newDelta);
271 Delta d=newDelta.diffBlock(new PPoint(blockvector.get(i)));
279 Delta processNode(BBlock bblock, int index, FlatNode node, Delta delta, Graph newgraph) {
280 switch(node.kind()) {
282 return processNewNode((FlatNew)node, delta, newgraph);
283 case FKind.FlatFieldNode:
284 case FKind.FlatElementNode:
285 return processFieldElementNode(node, delta, newgraph);
286 case FKind.FlatCastNode:
287 case FKind.FlatOpNode:
288 case FKind.FlatReturnNode:
289 return processCopyNode(node, delta, newgraph);
290 case FKind.FlatSetFieldNode:
291 case FKind.FlatSetElementNode:
292 return processSetFieldElementNode(node, delta, newgraph);
293 case FKind.FlatMethod:
295 case FKind.FlatGenReachNode:
296 return processFlatNop(node, delta, newgraph);
298 return processFlatCall(bblock, index, (FlatCall) node, delta, newgraph);
299 case FKind.FlatSESEEnterNode:
300 case FKind.FlatSESEExitNode:
301 throw new Error("Unimplemented node:"+node);
303 throw new Error("Unrecognized node:"+node);
307 /* This function compute the edges for the this variable for a
308 * callee if it exists. */
310 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) {
311 //Handle the this temp
313 MySet<Edge> edges=(oldnodeset!=null)?GraphManip.getDiffEdges(delta, tmpthis):GraphManip.getEdges(graph, delta, tmpthis);
314 newDelta.varedgeadd.put(tmpthis, (MySet<Edge>) edges.clone());
315 edgeset.addAll(edges);
317 AllocNode dstnode=e.dst;
318 if (!nodeset.contains(dstnode)&&(oldnodeset==null||!oldnodeset.contains(dstnode))) {
319 TypeDescriptor type=dstnode.getType();
320 if (!type.isArray()) {
321 targetSet.add(type.getClassDesc());
323 //arrays don't have code
324 targetSet.add(typeUtil.getClass(TypeUtil.ObjectClass));
326 nodeset.add(dstnode);
327 tovisit.add(dstnode);
333 /* This function compute the edges for a call's parameters. */
335 void processParams(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, FlatCall fcall, boolean diff) {
336 //Go through each temp
337 for(int i=0;i<fcall.numArgs();i++) {
338 TempDescriptor tmp=fcall.getArg(i);
339 MySet<Edge> edges=diff?GraphManip.getDiffEdges(delta, tmp):GraphManip.getEdges(graph, delta, tmp);
340 newDelta.varedgeadd.put(tmp, (MySet<Edge>) edges.clone());
341 edgeset.addAll(edges);
343 if (!nodeset.contains(e.dst)) {
351 /* This function computes the reachable nodes for a callee. */
353 void computeReachableNodes(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, HashSet<AllocNode> oldnodeset) {
354 while(!tovisit.isEmpty()) {
355 AllocNode node=tovisit.pop();
356 MySet<Edge> edges=GraphManip.getEdges(graph, delta, node);
357 newDelta.heapedgeadd.put(node, edges);
358 edgeset.addAll(edges);
360 if (!nodeset.contains(e.dst)&&(oldnodeset==null||!oldnodeset.contains(e.dst))) {
368 HashSet<MethodDescriptor> computeTargets(FlatCall fcall, Delta newDelta) {
369 TempDescriptor tmpthis=fcall.getThis();
370 MethodDescriptor md=fcall.getMethod();
371 HashSet<MethodDescriptor> targets=new HashSet<MethodDescriptor>();
376 for(Edge e:newDelta.varedgeadd.get(tmpthis)) {
377 AllocNode node=e.dst;
378 ClassDescriptor cd=node.getType().getClassDesc();
379 //Figure out exact method called and add to set
380 targets.add(cd.getCalledMethod(md));
386 void fixMapping(FlatCall fcall, HashSet<MethodDescriptor> targets, MySet<Edge> oldedgeset, Delta newDelta, BBlock callblock, int callindex) {
387 Delta basedelta=null;
388 TempDescriptor tmpthis=fcall.getThis();
390 for(MethodDescriptor calledmd:targets) {
391 FlatMethod fm=state.getMethodFlat(calledmd);
392 boolean newmethod=false;
395 HashMap<TempDescriptor, TempDescriptor> tmpMap=new HashMap<TempDescriptor, TempDescriptor>();
398 tmpMap.put(tmpthis, fm.getParameter(offset++));
400 for(int i=0;i<fcall.numArgs();i++) {
401 TempDescriptor tmp=fcall.getArg(i);
402 tmpMap.put(tmp,fm.getParameter(i+offset));
405 //Get basicblock for the method
406 BasicBlock block=getBBlock(fm);
409 if (!callMap.containsKey(fcall)) {
410 callMap.put(fcall, new HashSet<BBlock>());
413 Delta returnDelta=null;
414 if (!callMap.get(fcall).contains(block.getStart())) {
415 callMap.get(fcall).add(block.getStart());
419 if (!returnMap.containsKey(block.getExit())) {
420 returnMap.put(block.getExit(), new HashSet<PPoint>());
422 returnMap.get(block.getExit()).add(new PPoint(callblock, callindex));
424 if (bbgraphMap.containsKey(block.getExit())) {
425 //Need to push existing results to current node
426 if (returnDelta==null) {
427 returnDelta=new Delta(null, false);
428 Vector<FlatNode> exitblocknodes=block.getExit().nodes();
429 FlatExit fexit=(FlatExit)exitblocknodes.get(exitblocknodes.size()-1);
430 buildInitDelta(graphMap.get(fexit), returnDelta);
431 if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
432 returnDelta.setBlock(new PPoint(callblock, callindex));
433 toprocess.add(returnDelta);
436 if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
437 toprocess.add(returnDelta.diffBlock(new PPoint(callblock, callindex)));
443 if (oldedgeset==null) {
444 //First build of this graph
445 //Build and enqueue delta...safe to just use existing delta
446 Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
448 } else if (newmethod) {
449 if (basedelta==null) {
450 basedelta=newDelta.buildBase(oldedgeset);
452 //Build and enqueue delta
453 Delta d=basedelta.changeParams(tmpMap, new PPoint(block.getStart()));
456 //Build and enqueue delta
457 Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
464 /* This function computes all edges that start outside of the callee context and go into the callee context */
466 void computeExternalEdges(Graph graph, Delta delta, HashSet<AllocNode> nodeset, HashSet<AllocNode> deltaset, MySet<Edge> externaledgeset) {
467 //Do heap edges first
468 HashSet<AllocNode> externalnodes=new HashSet<AllocNode>();
469 externalnodes.addAll(delta.baseheapedge.keySet());
470 externalnodes.addAll(delta.heapedgeadd.keySet());
471 externalnodes.addAll(delta.heapedgeremove.keySet());
472 //remove allinternal nodes
473 externalnodes.removeAll(nodeset);
474 for(AllocNode extNode:externalnodes) {
475 //Compute set of edges from given node
476 MySet<Edge> edges=new MySet<Edge>(delta.baseheapedge.get(extNode));
477 edges.removeAll(delta.heapedgeremove.get(extNode));
478 edges.addAll(delta.heapedgeadd.get(extNode));
481 if (nodeset.contains(e.dst))
482 externaledgeset.add(e);
486 //Do heap edges first
487 HashSet<TempDescriptor> temps=new HashSet<TempDescriptor>();
488 temps.addAll(delta.basevaredge.keySet());
489 temps.addAll(delta.varedgeadd.keySet());
490 temps.addAll(delta.varedgeremove.keySet());
491 //remove allinternal nodes
492 temps.removeAll(nodeset);
494 for(TempDescriptor tmp:temps) {
495 //Compute set of edges from given node
496 MySet<Edge> edges=new MySet<Edge>(delta.basevaredge.get(tmp));
498 edges.removeAll(delta.varedgeremove.get(tmp));
499 edges.addAll(delta.varedgeadd.get(tmp));
502 if (nodeset.contains(e.dst))
503 externaledgeset.add(e);
508 /* This function removes the caller reachable edges from the
511 void removeEdges(Delta delta, HashSet<AllocNode> nodeset, MySet<Edge> edgeset, MySet<Edge> externaledgeset) {
512 //Want to remove the set of internal edges
513 for(Edge e:edgeset) {
515 delta.removeHeapEdge(e);
519 //Want to remove the set of external edges
520 for(Edge e:externaledgeset) {
521 //want to remove the set of internal edges
526 Delta processFlatCall(BBlock callblock, int callindex, FlatCall fcall, Delta delta, Graph graph) {
527 Delta newDelta=new Delta(null, false);
529 if (delta.getInit()) {
530 MySet<Edge> edgeset=new MySet<Edge>();
531 MySet<Edge> externaledgeset=new MySet<Edge>();
532 HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
533 HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
534 Stack<AllocNode> tovisit=new Stack<AllocNode>();
535 TempDescriptor tmpthis=fcall.getThis();
537 //Handle the this temp
538 processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, null);
540 //Go through each temp
541 processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, false);
543 //Traverse all reachable nodes
544 computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, null);
546 //Compute call targets
547 HashSet<MethodDescriptor> targets=computeTargets(fcall, newDelta);
550 fixMapping(fcall, targets, null, newDelta, callblock, callindex);
552 //Compute edges into region to splice out
553 computeExternalEdges(graph, delta, nodeset, null, externaledgeset);
555 //Splice out internal edges
556 removeEdges(delta, nodeset, edgeset, externaledgeset);
558 //store data structures
559 graph.externalEdgeSet=externaledgeset;
560 graph.reachNode=nodeset;
561 graph.reachEdge=edgeset;
563 graph.callNodeAges=new HashSet<AllocNode>();
564 graph.callOldNodes=new HashSet<AllocNode>();
566 //Apply diffs to graph
567 applyDiffs(graph, delta, true);
569 MySet<Edge> edgeset=new MySet<Edge>();
570 MySet<Edge> externaledgeset=new MySet<Edge>();
571 HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
572 MySet<Edge> oldedgeset=graph.reachEdge;
573 HashSet<AllocNode> oldnodeset=graph.reachNode;
575 HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
576 Stack<AllocNode> tovisit=new Stack<AllocNode>();
577 TempDescriptor tmpthis=fcall.getThis();
579 //Handle the this temp
580 processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, oldnodeset);
582 //Go through each temp
583 processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, true);
585 //Go through each new heap edge that starts from old node
586 MySet<Edge> newedges=GraphManip.getDiffEdges(delta, oldnodeset);
587 edgeset.addAll(newedges);
588 for(Edge e:newedges) {
589 if (!nodeset.contains(e.dst)&&!oldnodeset.contains(e.dst)) {
595 //Traverse all reachable nodes
596 computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, oldnodeset);
598 //Compute call targets
599 HashSet<MethodDescriptor> targets=computeTargets(fcall, newDelta);
601 //add in new nodeset and edgeset
602 oldnodeset.addAll(nodeset);
603 oldedgeset.addAll(edgeset);
606 fixMapping(fcall, targets, oldedgeset, newDelta, callblock, callindex);
608 //Compute edges into region to splice out
609 computeExternalEdges(graph, delta, oldnodeset, nodeset, externaledgeset);
611 //Splice out internal edges
612 removeEdges(delta, nodeset, edgeset, externaledgeset);
614 //Add in new external edges
615 graph.externalEdgeSet.addAll(externaledgeset);
617 //Apply diffs to graph
618 applyDiffs(graph, delta);
623 /* This function applies callee deltas to the caller heap. */
625 Delta applyCallDelta(Delta delta, BBlock bblock) {
626 Delta newDelta=new Delta(null, false);
627 Vector<FlatNode> nodes=bblock.nodes();
628 PPoint ppoint=delta.getBlock();
629 FlatCall fcall=(FlatCall)nodes.get(ppoint.getIndex());
630 Graph graph=graphMap.get(fcall);
631 Graph oldgraph=(ppoint.getIndex()==0)?
632 bbgraphMap.get(bblock):
633 graphMap.get(nodes.get(ppoint.getIndex()-1));
635 //Age outside nodes if necessary
636 for(Iterator<AllocNode> nodeit=delta.addNodeAges.iterator();nodeit.hasNext();) {
637 AllocNode node=nodeit.next();
638 if (!graph.callNodeAges.contains(node)) {
639 graph.callNodeAges.add(node);
643 if (!graph.reachNode.contains(node)&&!node.isSummary()) {
644 /* Need to age node in existing graph*/
645 summarizeInGraph(graph, newDelta, node);
649 for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.heapedgeadd.entrySet()) {
650 for(Edge e:entry.getValue()) {
651 boolean addedge=false;
653 if (e.statuspredicate==Edge.NEW) {
656 Edge origEdgeKey=e.makeStatus(allocFactory);
657 if (oldgraph.nodeMap.containsKey(origEdgeKey.src)&&
658 oldgraph.nodeMap.get(origEdgeKey.src).contains(origEdgeKey)) {
659 Edge origEdge=oldgraph.nodeMap.get(origEdgeKey.src).get(origEdgeKey);
661 origEdgeKey.statuspredicate=origEdge.statuspredicate;
662 edgetoadd=origEdgeKey;
665 mergeEdge(graph, newDelta, edgetoadd);
668 //Add external edges in
669 for(Edge e:graph.externalEdgeSet) {
670 //First did we age the source
671 Edge newedge=e.copy();
672 if (newedge.src!=null&&!e.src.isSummary()&&graph.callNodeAges.contains(e.src)) {
673 AllocNode summaryNode=allocFactory.getAllocNode(newedge.src, true);
674 newedge.src=summaryNode;
677 if (graph.callNodeAges.contains(e.dst)&&!e.dst.isSummary()) {
678 if (graph.callOldNodes.contains(e.dst)) {
680 Edge copy=newedge.copy();
681 mergeEdge(graph, newDelta, copy);
683 //Now add summarized node
684 newedge.dst=allocFactory.getAllocNode(newedge.dst, true);
685 mergeEdge(graph, newDelta, newedge);
687 //Add edge to single node
688 mergeEdge(graph, newDelta, newedge);
691 //Add edge for return value
692 if (fcall.getReturnTemp()!=null) {
693 MySet<Edge> returnedge=delta.varedgeadd.get(returntmp);
694 if (returnedge!=null)
695 for(Edge e:returnedge) {
696 Edge newedge=e.copy();
697 newedge.srcvar=fcall.getReturnTemp();
698 if (graph.getEdges(fcall.getReturnTemp())==null||!graph.getEdges(fcall.getReturnTemp()).contains(newedge))
699 newDelta.addEdge(newedge);
702 applyDiffs(graph, newDelta);
706 public void mergeEdge(Graph graph, Delta newDelta, Edge edgetoadd) {
707 if (edgetoadd!=null) {
708 Edge match=graph.getMatch(edgetoadd);
710 if (match==null||!match.subsumes(edgetoadd)) {
711 Edge mergededge=edgetoadd.merge(match);
712 newDelta.addEdge(mergededge);
718 /* Summarizes out of context nodes in graph */
719 void summarizeInGraph(Graph graph, Delta newDelta, AllocNode singleNode) {
720 AllocNode summaryNode=allocFactory.getAllocNode(singleNode, true);
722 //Handle outgoing heap edges
723 MySet<Edge> edgeset=graph.getEdges(singleNode);
725 for(Edge e:edgeset) {
726 Edge rewrite=e.rewrite(singleNode, summaryNode);
728 newDelta.removeHeapEdge(e);
729 mergeEdge(graph, newDelta, rewrite);
732 //Handle incoming edges
733 MySet<Edge> backedges=graph.getBackEdges(singleNode);
734 for(Edge e:backedges) {
735 if (e.dst==singleNode) {
736 //Need to get original edge so that predicate will be correct
737 Edge match=graph.getMatch(e);
738 Edge rewrite=match.rewrite(singleNode, summaryNode);
739 newDelta.removeEdge(match);
740 mergeEdge(graph, newDelta, rewrite);
745 void applyDiffs(Graph graph, Delta delta) {
746 applyDiffs(graph, delta, false);
749 void applyDiffs(Graph graph, Delta delta, boolean genbackwards) {
750 //build backwards map if requested
751 if (genbackwards&&graph.backMap==null) {
752 graph.backMap=new HashMap<AllocNode, MySet<Edge>>();
753 if (graph.parent.backMap==null) {
754 graph.parent.backMap=new HashMap<AllocNode, MySet<Edge>>();
755 for(Map.Entry<AllocNode, MySet<Edge>> entry:graph.nodeMap.entrySet()) {
756 for(Edge e:entry.getValue()) {
757 if (!graph.parent.backMap.containsKey(e.dst))
758 graph.parent.backMap.put(e.dst, new MySet<Edge>());
759 graph.parent.backMap.get(e.dst).add(e);
762 for(Map.Entry<TempDescriptor, MySet<Edge>> entry:graph.varMap.entrySet()) {
763 for(Edge e:entry.getValue()) {
764 if (!graph.parent.backMap.containsKey(e.dst))
765 graph.parent.backMap.put(e.dst, new MySet<Edge>());
766 graph.parent.backMap.get(e.dst).add(e);
772 //Add hidden base edges
773 for(Map.Entry<AllocNode, MySet<Edge>> e: delta.baseheapedge.entrySet()) {
774 AllocNode node=e.getKey();
775 MySet<Edge> edges=e.getValue();
776 if (graph.nodeMap.containsKey(node)) {
777 MySet<Edge> nodeEdges=graph.nodeMap.get(node);
778 nodeEdges.addAll(edges);
783 for(Map.Entry<AllocNode, MySet<Edge>> e: delta.heapedgeremove.entrySet()) {
784 AllocNode node=e.getKey();
785 MySet<Edge> edgestoremove=e.getValue();
786 if (graph.nodeMap.containsKey(node)) {
787 //Just apply diff to current map
788 graph.nodeMap.get(node).removeAll(edgestoremove);
790 //Generate diff from parent graph
791 MySet<Edge> parentedges=graph.parent.nodeMap.get(node);
792 MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
793 graph.nodeMap.put(node, newedgeset);
798 for(Map.Entry<AllocNode, MySet<Edge>> e: delta.heapedgeadd.entrySet()) {
799 AllocNode node=e.getKey();
800 MySet<Edge> edgestoadd=e.getValue();
801 //If we have not done a subtract, then
802 if (!graph.nodeMap.containsKey(node)) {
803 //Copy the parent entry
804 if (graph.parent.nodeMap.containsKey(node))
805 graph.nodeMap.put(node, (MySet<Edge>)graph.parent.nodeMap.get(node).clone());
807 graph.nodeMap.put(node, new MySet<Edge>());
809 graph.nodeMap.get(node).addAll(edgestoadd);
811 for(Edge eadd:edgestoadd) {
812 if (!graph.backMap.containsKey(eadd.dst))
813 graph.backMap.put(eadd.dst, new MySet<Edge>());
814 graph.backMap.get(eadd.dst).add(eadd);
820 for(Map.Entry<TempDescriptor, MySet<Edge>> e: delta.varedgeremove.entrySet()) {
821 TempDescriptor tmp=e.getKey();
822 MySet<Edge> edgestoremove=e.getValue();
824 if (graph.varMap.containsKey(tmp)) {
825 //Just apply diff to current map
826 graph.varMap.get(tmp).removeAll(edgestoremove);
827 } else if (graph.parent.varMap.containsKey(tmp)) {
828 //Generate diff from parent graph
829 MySet<Edge> parentedges=graph.parent.varMap.get(tmp);
830 MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
831 graph.varMap.put(tmp, newedgeset);
836 for(Map.Entry<TempDescriptor, MySet<Edge>> e: delta.varedgeadd.entrySet()) {
837 TempDescriptor tmp=e.getKey();
838 MySet<Edge> edgestoadd=e.getValue();
839 graph.varMap.put(tmp, (MySet<Edge>) edgestoadd.clone());
841 for(Edge eadd:edgestoadd) {
842 if (!graph.backMap.containsKey(eadd.dst))
843 graph.backMap.put(eadd.dst, new MySet<Edge>());
844 graph.backMap.get(eadd.dst).add(eadd);
850 for(AllocNode node:delta.addNodeAges) {
851 graph.nodeAges.add(node);
854 for(Map.Entry<AllocNode, Boolean> nodeentry:delta.addOldNodes.entrySet()) {
855 AllocNode node=nodeentry.getKey();
856 Boolean ispresent=nodeentry.getValue();
857 graph.oldNodes.put(node, ispresent);
861 Delta processSetFieldElementNode(FlatNode node, Delta delta, Graph graph) {
865 if (node.kind()==FKind.FlatSetElementNode) {
866 FlatSetElementNode fen=(FlatSetElementNode) node;
871 FlatSetFieldNode ffn=(FlatSetFieldNode) node;
876 if (delta.getInit()) {
877 HashSet<AllocNode> srcNodes=GraphManip.getNodes(graph, delta, src);
878 HashSet<AllocNode> dstNodes=GraphManip.getNodes(graph, delta, dst);
879 MySet<Edge> edgesToAdd=GraphManip.genEdges(dstNodes, fd, srcNodes);
880 MySet<Edge> edgesToRemove=null;
881 if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()) {
882 /* Can do a strong update */
883 edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
884 graph.strongUpdateSet=edgesToRemove;
886 graph.strongUpdateSet=new MySet<Edge>();
888 updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
889 applyDiffs(graph, delta);
891 /* First look at new sources */
892 MySet<Edge> edgesToAdd=new MySet<Edge>();
893 HashSet<AllocNode> newSrcNodes=GraphManip.getDiffNodes(delta, src);
894 HashSet<AllocNode> srcNodes=GraphManip.getNodes(graph, delta, src);
895 HashSet<AllocNode> dstNodes=GraphManip.getNodes(graph, delta, dst);
896 HashSet<AllocNode> newDstNodes=GraphManip.getDiffNodes(delta, dst);
899 MySet<Edge> edgesToRemove=null;
900 if (newDstNodes.size()!=0) {
901 if (dstNodes.size()>1&&!dstNodes.iterator().next().isSummary()) {
902 /* Need to undo strong update */
903 if (graph.strongUpdateSet!=null) {
904 edgesToAdd.addAll(graph.strongUpdateSet);
905 graph.strongUpdateSet=null; //Prevent future strong updates
907 } else if (dstNodes.size()==1&&newDstNodes.size()==1&&!newDstNodes.iterator().next().isSummary()&&graph.strongUpdateSet!=null) {
908 edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
909 graph.strongUpdateSet.addAll(edgesToRemove);
911 edgesToAdd.addAll(GraphManip.genEdges(newDstNodes, fd, srcNodes));
915 if (graph.strongUpdateSet!=null) {
916 MySet<Edge> otherEdgesToRemove=GraphManip.getDiffEdges(delta, dstNodes);
917 if (edgesToRemove!=null)
918 edgesToRemove.addAll(otherEdgesToRemove);
920 edgesToRemove=otherEdgesToRemove;
921 graph.strongUpdateSet.addAll(otherEdgesToRemove);
924 //Next look at new destinations
925 edgesToAdd.addAll(GraphManip.genEdges(dstNodes, fd, newSrcNodes));
928 updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
929 applyDiffs(graph, delta);
934 Delta processCopyNode(FlatNode node, Delta delta, Graph graph) {
937 if (node.kind()==FKind.FlatOpNode) {
938 FlatOpNode fon=(FlatOpNode) node;
941 } else if (node.kind()==FKind.FlatReturnNode) {
942 FlatReturnNode frn=(FlatReturnNode)node;
943 src=frn.getReturnTemp();
945 if (src==null||!src.getType().isPtr()) {
947 applyDiffs(graph, delta);
951 FlatCastNode fcn=(FlatCastNode) node;
955 if (delta.getInit()) {
956 HashSet<AllocNode> srcnodes=GraphManip.getNodes(graph, delta, src);
957 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, srcnodes);
958 MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
959 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
960 applyDiffs(graph, delta);
962 /* First compute new src nodes */
963 HashSet<AllocNode> newSrcNodes=GraphManip.getDiffNodes(delta, src);
965 /* Compute the union, and then the set of edges */
966 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, newSrcNodes);
968 /* Compute set of edges to remove */
969 MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
972 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
973 applyDiffs(graph, delta);
978 Delta processFieldElementNode(FlatNode node, Delta delta, Graph graph) {
982 if (node.kind()==FKind.FlatElementNode) {
983 FlatElementNode fen=(FlatElementNode) node;
988 FlatFieldNode ffn=(FlatFieldNode) node;
993 if (delta.getInit()) {
994 HashSet<AllocNode> srcnodes=GraphManip.getNodes(graph, delta, src);
995 HashSet<AllocNode> fdnodes=GraphManip.getNodes(graph, delta, srcnodes, fd);
996 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, fdnodes);
997 MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
998 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
999 applyDiffs(graph, delta);
1001 /* First compute new objects we read fields of */
1002 HashSet<AllocNode> allsrcnodes=GraphManip.getNodes(graph, delta, src);
1003 HashSet<AllocNode> difffdnodes=GraphManip.getDiffNodes(delta, allsrcnodes, fd);
1004 /* Next compute new targets of fields */
1005 HashSet<AllocNode> newsrcnodes=GraphManip.getDiffNodes(delta, src);
1006 HashSet<AllocNode> newfdnodes=GraphManip.getNodes(graph, delta, newsrcnodes, fd);
1007 /* Compute the union, and then the set of edges */
1008 HashSet<AllocNode> newTargets=new HashSet<AllocNode>();
1009 newTargets.addAll(newfdnodes);
1010 newTargets.addAll(difffdnodes);
1011 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, newTargets);
1013 /* Compute set of edges to remove */
1014 MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
1017 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1018 applyDiffs(graph, delta);
1023 static void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1024 MySet<Edge> edgeAdd=delta.varedgeadd.get(tmp);
1025 MySet<Edge> edgeRemove=delta.varedgeremove.get(tmp);
1026 MySet<Edge> existingEdges=graph.getEdges(tmp);
1027 for(Edge e: edgestoRemove) {
1028 //remove edge from delta
1031 //if the edge is already in the graph, add an explicit remove to the delta
1032 if (existingEdges.contains(e))
1033 delta.removeVarEdge(e);
1035 for(Edge e: edgestoAdd) {
1036 //Remove the edge from the remove set
1037 if (edgeRemove!=null)
1038 edgeRemove.remove(e);
1039 //Explicitly add it to the add set unless it is already in the graph
1040 if (!existingEdges.contains(e))
1041 delta.addVarEdge(e);
1045 static void updateHeapDelta(Graph graph, Delta delta, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1046 if (edgestoRemove!=null)
1047 for(Edge e: edgestoRemove) {
1048 AllocNode src=e.src;
1049 MySet<Edge> edgeAdd=delta.heapedgeadd.get(src);
1050 MySet<Edge> existingEdges=graph.getEdges(src);
1051 //remove edge from delta
1053 //if the edge is already in the graph, add an explicit remove to the delta
1054 if (existingEdges.contains(e)) {
1055 delta.removeHeapEdge(e);
1058 if (edgestoAdd!=null)
1059 for(Edge e: edgestoAdd) {
1060 AllocNode src=e.src;
1061 MySet<Edge> edgeRemove=delta.heapedgeremove.get(src);
1062 MySet<Edge> existingEdges=graph.getEdges(src);
1063 //Remove the edge from the remove set
1064 if (edgeRemove!=null)
1065 edgeRemove.remove(e);
1066 //Explicitly add it to the add set unless it is already in the graph
1067 if (!existingEdges.contains(e)||!existingEdges.get(e).isNew()) {
1068 delta.addHeapEdge(e);
1073 Delta processFlatNop(FlatNode node, Delta delta, Graph graph) {
1074 applyDiffs(graph, delta);
1078 Delta processNewNode(FlatNew node, Delta delta, Graph graph) {
1079 AllocNode summary=allocFactory.getAllocNode(node, true);
1080 AllocNode single=allocFactory.getAllocNode(node, false);
1081 TempDescriptor tmp=node.getDst();
1083 if (delta.getInit()) {
1084 /* We don't have to deal with summarization here... The
1085 * intuition is that this is the only place where we generate
1086 * nodes for this allocation site and this is the first time
1087 * we've analyzed this site */
1090 Edge e=new Edge(tmp, single);
1091 //Build new Edge set
1092 MySet<Edge> newedges=new MySet<Edge>();
1094 //Add it into the diffs
1095 delta.varedgeadd.put(tmp, newedges);
1096 //Remove the old edges
1097 delta.varedgeremove.put(tmp, (MySet<Edge>) graph.getEdges(tmp).clone());
1098 //Apply incoming diffs to graph
1099 applyDiffs(graph, delta);
1100 //Note that we create a single node
1101 delta.addNodeAges.add(single);
1103 if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1104 delta.addOldNodes.put(single, Boolean.FALSE);
1107 /* 1. Fix up the variable edge additions */
1109 for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.varedgeadd.entrySet().iterator();entryIt.hasNext();) {
1110 Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1112 if (entry.getKey()==tmp) {
1113 /* Check if this is the tmp we overwrite */
1116 /* Otherwise, check if the target of the edge is changed... */
1117 summarizeSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary);
1121 /* 2. Fix up the base variable edges */
1123 for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.basevaredge.entrySet().iterator();entryIt.hasNext();) {
1124 Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1125 TempDescriptor entrytmp=entry.getKey();
1126 if (entrytmp==tmp) {
1127 /* Check is this is the tmp we overwrite, if so add to remove set */
1128 Util.relationUpdate(delta.varedgeremove, tmp, null, entry.getValue());
1130 /* Check if the target of the edge is changed */
1131 MySet<Edge> newset=(MySet<Edge>)entry.getValue().clone();
1132 MySet<Edge> removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary);
1133 Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset);
1134 Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset);
1139 /* 3. Fix up heap edge additions */
1141 HashMap<AllocNode, MySet<Edge>> addheapedge=new HashMap<AllocNode, MySet<Edge>>();
1142 for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.heapedgeadd.entrySet().iterator();entryIt.hasNext();) {
1143 Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1144 MySet<Edge> edgeset=entry.getValue();
1145 AllocNode allocnode=entry.getKey();
1146 if (allocnode==single) {
1148 summarizeSet(edgeset, graph.nodeMap.get(summary), single, summary);
1149 addheapedge.put(summary, edgeset);
1151 summarizeSet(edgeset, graph.nodeMap.get(allocnode), single, summary);
1155 /* Merge in diffs */
1157 for(Map.Entry<AllocNode, MySet<Edge>> entry:addheapedge.entrySet()) {
1158 AllocNode allocnode=entry.getKey();
1159 Util.relationUpdate(delta.heapedgeadd, allocnode, null, entry.getValue());
1162 /* 4. Fix up the base heap edges */
1164 for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.baseheapedge.entrySet().iterator();entryIt.hasNext();) {
1165 Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1166 MySet<Edge> edgeset=entry.getValue();
1167 AllocNode allocnode=entry.getKey();
1168 if (allocnode==single) {
1171 AllocNode addnode=(allocnode==single)?summary:allocnode;
1173 MySet<Edge> newset=(MySet<Edge>) edgeset.clone();
1174 MySet<Edge> removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary);
1175 Util.relationUpdate(delta.heapedgeadd, addnode, null, newset);
1176 Util.relationUpdate(delta.heapedgeremove, allocnode, null, removeset);
1179 /* Update Node Ages...If the base or addNodeAges set contains a
1180 * single node, it now should also contain a summary node... No
1181 * need to generate a single node as that has already been
1183 if (delta.baseNodeAges.contains(single)||delta.addNodeAges.contains(single)) {
1184 delta.addNodeAges.add(summary);
1187 //Kill the old node if someone tries to add it
1188 if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1189 delta.addOldNodes.put(single, Boolean.FALSE);
1192 //Apply incoming diffs to graph
1193 applyDiffs(graph, delta);
1198 /* This function builds a new edge set where oldnode is summarized into new node */
1200 void summarizeSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode sumnode) {
1201 MySet<Edge> newSet=null;
1202 for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
1203 Edge e=edgeit.next();
1204 if (e.dst==oldnode||e.src==oldnode) {
1206 newSet=new MySet<Edge>();
1211 if (e.dst==oldnode) {
1214 if (e.src==oldnode) {
1217 if (oldedgeset==null||!oldedgeset.contains(e))
1222 edgeset.addAll(newSet);
1225 /* Shrinks the incoming set to just include rewritten values.
1226 * Returns a set of the original rewritten values */
1228 MySet<Edge> shrinkSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode newnode) {
1229 MySet<Edge> newSet=null;
1230 MySet<Edge> removeSet=null;
1231 for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
1232 Edge e=edgeit.next();
1234 if (e.dst==oldnode||e.src==oldnode) {
1236 newSet=new MySet<Edge>();
1237 removeSet=new MySet<Edge>();
1240 removeSet.add(e.copy());
1245 if (oldedgeset==null||!oldedgeset.contains(e))
1250 edgeset.addAll(newSet);
1254 /* This function returns a completely new Delta... It is safe to
1257 Delta applyInitDelta(Delta delta, BBlock block) {
1258 //Apply delta to graph
1259 boolean newGraph=false;
1260 if (!bbgraphMap.containsKey(block)) {
1261 bbgraphMap.put(block, new Graph(null));
1265 Graph graph=bbgraphMap.get(block);
1268 newdelta=new Delta(null, true);
1269 //Add in heap edges and throw away original diff
1270 graph.nodeMap.putAll(delta.heapedgeadd);
1271 //Add in var edges and throw away original diff
1272 graph.varMap.putAll(delta.varedgeadd);
1273 //Record that this is initial set...
1274 graph.nodeAges.addAll(delta.addNodeAges);
1276 for(Map.Entry<AllocNode, Boolean> oldentry:delta.addOldNodes.entrySet()) {
1277 if (oldentry.getValue().booleanValue()) {
1278 graph.oldNodes.put(oldentry.getKey(), Boolean.TRUE);
1282 newdelta=new Delta(null, false);
1283 //merge in heap edges and variables
1284 mergeHeapEdges(graph, delta, newdelta);
1285 mergeVarEdges(graph, delta, newdelta);
1286 mergeAges(graph, delta, newdelta);
1292 /* This function merges in the heap edges. It updates delta to be
1295 void mergeHeapEdges(Graph graph, Delta delta, Delta newdelta) {
1297 for(Map.Entry<AllocNode, MySet<Edge>> heapedge:delta.heapedgeadd.entrySet()) {
1298 AllocNode nsrc=heapedge.getKey();
1299 MySet<Edge> edges=heapedge.getValue();
1301 if (graph.backMap!=null) {
1303 if (!graph.backMap.containsKey(e.dst))
1304 graph.backMap.put(e.dst, new MySet<Edge>());
1305 graph.backMap.get(e.dst).add(e);
1309 if (!graph.nodeMap.containsKey(nsrc)) {
1310 graph.nodeMap.put(nsrc, new MySet<Edge>());
1312 MySet<Edge> dstedges=graph.nodeMap.get(nsrc);
1313 MySet<Edge> diffedges=new MySet<Edge>();
1315 if (!dstedges.contains(e)) {
1316 //We have a new edge
1320 Edge origedge=dstedges.get(e);
1321 if (!origedge.subsumes(e)) {
1322 Edge mergededge=origedge.merge(e);
1323 diffedges.add(mergededge);
1324 dstedges.add(mergededge);
1328 //Done with edge set...
1329 if (diffedges.size()>0) {
1331 newdelta.baseheapedge.put(nsrc, diffedges);
1336 /* This function merges in the var edges. It updates delta to be
1339 void mergeVarEdges(Graph graph, Delta delta, Delta newdelta) {
1341 for(Map.Entry<TempDescriptor, MySet<Edge>> varedge:delta.varedgeadd.entrySet()) {
1342 TempDescriptor tmpsrc=varedge.getKey();
1343 MySet<Edge> edges=varedge.getValue();
1344 if (graph.backMap!=null) {
1346 if (!graph.backMap.containsKey(e.dst))
1347 graph.backMap.put(e.dst, new MySet<Edge>());
1348 graph.backMap.get(e.dst).add(e);
1352 if (!graph.varMap.containsKey(tmpsrc)) {
1353 graph.varMap.put(tmpsrc, new MySet<Edge>());
1355 MySet<Edge> dstedges=graph.varMap.get(tmpsrc);
1356 MySet<Edge> diffedges=new MySet<Edge>();
1358 if (!dstedges.contains(e)) {
1359 //We have a new edge
1364 //Done with edge set...
1365 if (diffedges.size()>=0) {
1367 newdelta.basevaredge.put(tmpsrc,diffedges);
1372 void mergeAges(Graph graph, Delta delta, Delta newDelta) {
1374 for(AllocNode node:delta.addNodeAges) {
1375 if (!graph.nodeAges.contains(node)) {
1376 graph.nodeAges.add(node);
1377 newDelta.baseNodeAges.add(node);
1380 for(Map.Entry<AllocNode, Boolean> oldentry:delta.addOldNodes.entrySet()) {
1381 AllocNode node=oldentry.getKey();
1382 boolean ispresent=oldentry.getValue().booleanValue();
1383 if (ispresent&&!graph.oldNodes.containsKey(node)) {
1384 graph.oldNodes.put(node, Boolean.TRUE);
1385 newDelta.baseOldNodes.put(node, Boolean.TRUE);