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());
60 while(!toprocess.isEmpty()) {
61 Delta delta=toprocess.remove();
62 PPoint ppoint=delta.getBlock();
63 BBlock bblock=ppoint.getBBlock();
64 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);
80 if (!graphMap.containsKey(currNode)) {
81 graphMap.put(currNode, new Graph(graph));
83 nodeGraph=graphMap.get(currNode);
84 delta=processNode(bblock, i, currNode, delta, nodeGraph);
86 generateFinalDelta(bblock, delta, nodeGraph);
92 for(Map.Entry<BBlock, Graph> e:bbgraphMap.entrySet()) {
94 plotGraph(g,"BB"+debugindex);
98 for(Map.Entry<FlatNode, Graph> e:graphMap.entrySet()) {
99 FlatNode fn=e.getKey();
100 Graph g=e.getValue();
101 plotGraph(g,"FN"+fn.toString()+debugindex);
104 for(FlatMethod fm:blockMap.keySet()) {
110 void plotGraph(Graph g, String name) {
112 PrintWriter pw=new PrintWriter(new FileWriter(name.toString().replace(' ','_')+".dot"));
113 g.printGraph(pw, name);
115 } catch (Exception ex) {
116 ex.printStackTrace();
121 /* This function builds the last delta for a basic block. It
122 * handles the case for the first time the basic block is
125 void buildInitDelta(Graph graph, Delta newDelta) {
126 //First compute the set of temps
127 HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
128 tmpSet.addAll(graph.varMap.keySet());
129 tmpSet.addAll(graph.parent.varMap.keySet());
131 //Next build the temp map part of the delta
132 for(TempDescriptor tmp:tmpSet) {
133 MySet<Edge> edgeSet=new MySet<Edge>();
135 if (graph.varMap.containsKey(tmp))
136 edgeSet.addAll(graph.varMap.get(tmp));
138 edgeSet.addAll(graph.parent.varMap.get(tmp));
139 newDelta.varedgeadd.put(tmp, edgeSet);
142 //Next compute the set of src allocnodes
143 HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
144 nodeSet.addAll(graph.nodeMap.keySet());
145 nodeSet.addAll(graph.parent.nodeMap.keySet());
147 for(AllocNode node:nodeSet) {
148 MySet<Edge> edgeSet=new MySet<Edge>();
150 if (graph.nodeMap.containsKey(node))
151 edgeSet.addAll(graph.nodeMap.get(node));
153 edgeSet.addAll(graph.parent.nodeMap.get(node));
154 newDelta.heapedgeadd.put(node, edgeSet);
157 if (graph.nodeAges.contains(node))
158 newDelta.addNodeAges.add(node);
159 else if (graph.parent.nodeAges.contains(node))
160 newDelta.addNodeAges.add(node);
163 if (graph.oldNodes.containsKey(node)) {
164 if (graph.oldNodes.get(node).booleanValue())
165 newDelta.addOldNodes.put(node, Boolean.TRUE);
166 } else if (graph.parent.oldNodes.containsKey(node)) {
167 //parent graphs only contain true...no need to check
168 newDelta.addOldNodes.put(node, Boolean.TRUE);
173 /* This function build the delta for the exit of a basic block. */
175 void generateFinalDelta(BBlock bblock, Delta delta, Graph graph) {
176 Delta newDelta=new Delta(null, false);
177 if (delta.getInit()) {
178 buildInitDelta(graph, newDelta);
180 /* We can break the old delta...it is done being used */
181 /* First we will build variable edges */
182 HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
183 tmpSet.addAll(delta.basevaredge.keySet());
184 tmpSet.addAll(delta.varedgeadd.keySet());
185 for(TempDescriptor tmp:tmpSet) {
186 /* Start with the new incoming edges */
187 MySet<Edge> newbaseedge=delta.basevaredge.get(tmp);
188 /* Remove the remove set */
189 if (newbaseedge==null)
190 newbaseedge=new MySet<Edge>();
191 newbaseedge.removeAll(delta.varedgeremove.get(tmp));
192 /* Add in the new set*/
193 newbaseedge.addAll(delta.varedgeadd.get(tmp));
194 /* Store the results */
195 newDelta.varedgeadd.put(tmp, newbaseedge);
197 delta.basevaredge.clear();
199 /* Next we build heap edges */
200 HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
201 nodeSet.addAll(delta.baseheapedge.keySet());
202 nodeSet.addAll(delta.heapedgeadd.keySet());
203 nodeSet.addAll(delta.heapedgeremove.keySet());
204 for(AllocNode node:nodeSet) {
205 /* Start with the new incoming edges */
206 MySet<Edge> newheapedge=new MySet<Edge>(delta.baseheapedge.get(node));
207 /* Remove the remove set */
208 MySet<Edge> removeset=delta.heapedgeremove.get(node);
211 newheapedge.removeAll(removeset);
213 /* Add in the add set */
214 MySet<Edge> settoadd=delta.heapedgeadd.get(node);
216 newheapedge.addAll(settoadd);
217 newDelta.heapedgeadd.put(node, newheapedge);
219 /* Remove the newly created edges..no need to propagate a diff for those */
220 if (removeset!=null) {
221 removeset.removeAll(delta.baseheapedge.get(node));
222 newDelta.heapedgeremove.put(node, removeset);
226 /* Compute new ages */
227 newDelta.addNodeAges.addAll(delta.baseNodeAges);
228 newDelta.addNodeAges.addAll(delta.addNodeAges);
229 HashSet<AllocNode> oldNodes=new HashSet<AllocNode>();
231 /* Compute whether old nodes survive */
232 oldNodes.addAll(delta.baseOldNodes.keySet());
233 oldNodes.addAll(delta.addOldNodes.keySet());
234 for(AllocNode node:oldNodes) {
235 if (delta.addOldNodes.containsKey(node)) {
236 if (delta.addOldNodes.get(node).booleanValue()) {
237 newDelta.addOldNodes.put(node, Boolean.TRUE);
240 if (delta.baseOldNodes.get(node).booleanValue()) {
241 newDelta.addOldNodes.put(node, Boolean.TRUE);
247 /* Now we need to propagate newdelta */
248 if (!newDelta.heapedgeadd.isEmpty()||!newDelta.heapedgeremove.isEmpty()||!newDelta.varedgeadd.isEmpty()||!newDelta.addNodeAges.isEmpty()||!newDelta.addOldNodes.isEmpty()) {
249 /* We have a delta to propagate */
250 if (returnMap.containsKey(bblock)) {
254 for(PPoint caller:returnMap.get(bblock)) {
256 newDelta.setBlock(caller);
257 toprocess.add(newDelta);
260 Delta d=newDelta.diffBlock(caller);
266 Vector<BBlock> blockvector=bblock.next();
267 for(int i=0;i<blockvector.size();i++) {
269 newDelta.setBlock(new PPoint(blockvector.get(i)));
270 toprocess.add(newDelta);
272 Delta d=newDelta.diffBlock(new PPoint(blockvector.get(i)));
280 Delta processNode(BBlock bblock, int index, FlatNode node, Delta delta, Graph newgraph) {
281 switch(node.kind()) {
283 return processNewNode((FlatNew)node, delta, newgraph);
284 case FKind.FlatFieldNode:
285 case FKind.FlatElementNode:
286 return processFieldElementNode(node, delta, newgraph);
287 case FKind.FlatCastNode:
288 case FKind.FlatOpNode:
289 case FKind.FlatReturnNode:
290 return processCopyNode(node, delta, newgraph);
291 case FKind.FlatSetFieldNode:
292 case FKind.FlatSetElementNode:
293 return processSetFieldElementNode(node, delta, newgraph);
294 case FKind.FlatMethod:
296 case FKind.FlatBackEdge:
297 case FKind.FlatGenReachNode:
298 case FKind.FlatSESEEnterNode:
299 case FKind.FlatSESEExitNode:
300 return processFlatNop(node, delta, newgraph);
302 return processFlatCall(bblock, index, (FlatCall) node, delta, newgraph);
304 throw new Error("Unrecognized node:"+node);
308 /* This function compute the edges for the this variable for a
309 * callee if it exists. */
311 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) {
312 //Handle the this temp
314 MySet<Edge> edges=(oldnodeset!=null)?GraphManip.getDiffEdges(delta, tmpthis):GraphManip.getEdges(graph, delta, tmpthis);
315 newDelta.varedgeadd.put(tmpthis, (MySet<Edge>) edges.clone());
316 edgeset.addAll(edges);
318 AllocNode dstnode=e.dst;
319 if (!nodeset.contains(dstnode)&&(oldnodeset==null||!oldnodeset.contains(dstnode))) {
320 TypeDescriptor type=dstnode.getType();
321 if (!type.isArray()) {
322 targetSet.add(type.getClassDesc());
324 //arrays don't have code
325 targetSet.add(typeUtil.getClass(TypeUtil.ObjectClass));
327 nodeset.add(dstnode);
328 tovisit.add(dstnode);
334 /* This function compute the edges for a call's parameters. */
336 void processParams(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, FlatCall fcall, boolean diff) {
337 //Go through each temp
338 for(int i=0;i<fcall.numArgs();i++) {
339 TempDescriptor tmp=fcall.getArg(i);
340 MySet<Edge> edges=diff?GraphManip.getDiffEdges(delta, tmp):GraphManip.getEdges(graph, delta, tmp);
341 newDelta.varedgeadd.put(tmp, (MySet<Edge>) edges.clone());
342 edgeset.addAll(edges);
344 if (!nodeset.contains(e.dst)) {
352 /* This function computes the reachable nodes for a callee. */
354 void computeReachableNodes(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, HashSet<AllocNode> oldnodeset) {
355 while(!tovisit.isEmpty()) {
356 AllocNode node=tovisit.pop();
357 MySet<Edge> edges=GraphManip.getEdges(graph, delta, node);
358 newDelta.heapedgeadd.put(node, edges);
359 edgeset.addAll(edges);
361 if (!nodeset.contains(e.dst)&&(oldnodeset==null||!oldnodeset.contains(e.dst))) {
369 HashSet<MethodDescriptor> computeTargets(FlatCall fcall, Delta newDelta) {
370 TempDescriptor tmpthis=fcall.getThis();
371 MethodDescriptor md=fcall.getMethod();
372 HashSet<MethodDescriptor> targets=new HashSet<MethodDescriptor>();
377 for(Edge e:newDelta.varedgeadd.get(tmpthis)) {
378 AllocNode node=e.dst;
379 ClassDescriptor cd=node.getType().getClassDesc();
380 //Figure out exact method called and add to set
381 targets.add(cd.getCalledMethod(md));
387 void fixMapping(FlatCall fcall, HashSet<MethodDescriptor> targets, MySet<Edge> oldedgeset, Delta newDelta, BBlock callblock, int callindex) {
388 Delta basedelta=null;
389 TempDescriptor tmpthis=fcall.getThis();
391 for(MethodDescriptor calledmd:targets) {
392 FlatMethod fm=state.getMethodFlat(calledmd);
393 boolean newmethod=false;
396 HashMap<TempDescriptor, TempDescriptor> tmpMap=new HashMap<TempDescriptor, TempDescriptor>();
399 tmpMap.put(tmpthis, fm.getParameter(offset++));
401 for(int i=0;i<fcall.numArgs();i++) {
402 TempDescriptor tmp=fcall.getArg(i);
403 tmpMap.put(tmp,fm.getParameter(i+offset));
406 //Get basicblock for the method
407 BasicBlock block=getBBlock(fm);
410 if (!callMap.containsKey(fcall)) {
411 callMap.put(fcall, new HashSet<BBlock>());
414 Delta returnDelta=null;
415 if (!callMap.get(fcall).contains(block.getStart())) {
416 callMap.get(fcall).add(block.getStart());
420 if (!returnMap.containsKey(block.getExit())) {
421 returnMap.put(block.getExit(), new HashSet<PPoint>());
423 returnMap.get(block.getExit()).add(new PPoint(callblock, callindex));
425 if (bbgraphMap.containsKey(block.getExit())) {
426 //Need to push existing results to current node
427 if (returnDelta==null) {
428 returnDelta=new Delta(null, false);
429 Vector<FlatNode> exitblocknodes=block.getExit().nodes();
430 FlatExit fexit=(FlatExit)exitblocknodes.get(exitblocknodes.size()-1);
431 buildInitDelta(graphMap.get(fexit), returnDelta);
432 if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
433 returnDelta.setBlock(new PPoint(callblock, callindex));
434 toprocess.add(returnDelta);
437 if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
438 toprocess.add(returnDelta.diffBlock(new PPoint(callblock, callindex)));
444 if (oldedgeset==null) {
445 //First build of this graph
446 //Build and enqueue delta...safe to just use existing delta
447 Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
449 } else if (newmethod) {
450 if (basedelta==null) {
451 basedelta=newDelta.buildBase(oldedgeset);
453 //Build and enqueue delta
454 Delta d=basedelta.changeParams(tmpMap, new PPoint(block.getStart()));
457 //Build and enqueue delta
458 Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
465 /* This function computes all edges that start outside of the callee context and go into the callee context */
467 void computeExternalEdges(Graph graph, Delta delta, HashSet<AllocNode> nodeset, HashSet<AllocNode> deltaset, MySet<Edge> externaledgeset) {
468 //Do heap edges first
469 HashSet<AllocNode> externalnodes=new HashSet<AllocNode>();
470 externalnodes.addAll(delta.baseheapedge.keySet());
471 externalnodes.addAll(delta.heapedgeadd.keySet());
472 externalnodes.addAll(delta.heapedgeremove.keySet());
473 //remove allinternal nodes
474 externalnodes.removeAll(nodeset);
475 for(AllocNode extNode:externalnodes) {
476 //Compute set of edges from given node
477 MySet<Edge> edges=new MySet<Edge>(delta.baseheapedge.get(extNode));
478 edges.removeAll(delta.heapedgeremove.get(extNode));
479 edges.addAll(delta.heapedgeadd.get(extNode));
482 if (nodeset.contains(e.dst))
483 externaledgeset.add(e);
487 //Do heap edges first
488 HashSet<TempDescriptor> temps=new HashSet<TempDescriptor>();
489 temps.addAll(delta.basevaredge.keySet());
490 temps.addAll(delta.varedgeadd.keySet());
491 temps.addAll(delta.varedgeremove.keySet());
492 //remove allinternal nodes
493 temps.removeAll(nodeset);
495 for(TempDescriptor tmp:temps) {
496 //Compute set of edges from given node
497 MySet<Edge> edges=new MySet<Edge>(delta.basevaredge.get(tmp));
499 edges.removeAll(delta.varedgeremove.get(tmp));
500 edges.addAll(delta.varedgeadd.get(tmp));
503 if (nodeset.contains(e.dst))
504 externaledgeset.add(e);
509 /* This function removes the caller reachable edges from the
512 void removeEdges(Delta delta, HashSet<AllocNode> nodeset, MySet<Edge> edgeset, MySet<Edge> externaledgeset) {
513 //Want to remove the set of internal edges
514 for(Edge e:edgeset) {
516 delta.removeHeapEdge(e);
520 //Want to remove the set of external edges
521 for(Edge e:externaledgeset) {
522 //want to remove the set of internal edges
527 Delta processFlatCall(BBlock callblock, int callindex, FlatCall fcall, Delta delta, Graph graph) {
528 Delta newDelta=new Delta(null, false);
530 if (delta.getInit()) {
531 MySet<Edge> edgeset=new MySet<Edge>();
532 MySet<Edge> externaledgeset=new MySet<Edge>();
533 HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
534 HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
535 Stack<AllocNode> tovisit=new Stack<AllocNode>();
536 TempDescriptor tmpthis=fcall.getThis();
538 //Handle the this temp
539 processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, null);
541 //Go through each temp
542 processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, false);
544 //Traverse all reachable nodes
545 computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, null);
547 //Compute call targets
548 HashSet<MethodDescriptor> targets=computeTargets(fcall, newDelta);
551 fixMapping(fcall, targets, null, newDelta, callblock, callindex);
553 //Compute edges into region to splice out
554 computeExternalEdges(graph, delta, nodeset, null, externaledgeset);
556 //Splice out internal edges
557 removeEdges(delta, nodeset, edgeset, externaledgeset);
559 //store data structures
560 graph.externalEdgeSet=externaledgeset;
561 graph.reachNode=nodeset;
562 graph.reachEdge=edgeset;
564 graph.callNodeAges=new HashSet<AllocNode>();
565 graph.callOldNodes=new HashSet<AllocNode>();
567 //Apply diffs to graph
568 applyDiffs(graph, delta, true);
570 MySet<Edge> edgeset=new MySet<Edge>();
571 MySet<Edge> externaledgeset=new MySet<Edge>();
572 HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
573 MySet<Edge> oldedgeset=graph.reachEdge;
574 HashSet<AllocNode> oldnodeset=graph.reachNode;
576 HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
577 Stack<AllocNode> tovisit=new Stack<AllocNode>();
578 TempDescriptor tmpthis=fcall.getThis();
580 //Handle the this temp
581 processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, oldnodeset);
583 //Go through each temp
584 processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, true);
586 //Go through each new heap edge that starts from old node
587 MySet<Edge> newedges=GraphManip.getDiffEdges(delta, oldnodeset);
588 edgeset.addAll(newedges);
589 for(Edge e:newedges) {
590 if (!nodeset.contains(e.dst)&&!oldnodeset.contains(e.dst)) {
596 //Traverse all reachable nodes
597 computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, oldnodeset);
599 //Compute call targets
600 HashSet<MethodDescriptor> targets=computeTargets(fcall, newDelta);
602 //add in new nodeset and edgeset
603 oldnodeset.addAll(nodeset);
604 oldedgeset.addAll(edgeset);
607 fixMapping(fcall, targets, oldedgeset, newDelta, callblock, callindex);
609 //Compute edges into region to splice out
610 computeExternalEdges(graph, delta, oldnodeset, nodeset, externaledgeset);
612 //Splice out internal edges
613 removeEdges(delta, nodeset, edgeset, externaledgeset);
615 //Add in new external edges
616 graph.externalEdgeSet.addAll(externaledgeset);
618 //Apply diffs to graph
619 applyDiffs(graph, delta);
624 /* This function applies callee deltas to the caller heap. */
626 Delta applyCallDelta(Delta delta, BBlock bblock) {
627 Delta newDelta=new Delta(null, false);
628 Vector<FlatNode> nodes=bblock.nodes();
629 PPoint ppoint=delta.getBlock();
630 FlatCall fcall=(FlatCall)nodes.get(ppoint.getIndex());
631 Graph graph=graphMap.get(fcall);
632 Graph oldgraph=(ppoint.getIndex()==0)?
633 bbgraphMap.get(bblock):
634 graphMap.get(nodes.get(ppoint.getIndex()-1));
636 //Age outside nodes if necessary
637 for(Iterator<AllocNode> nodeit=delta.addNodeAges.iterator();nodeit.hasNext();) {
638 AllocNode node=nodeit.next();
639 if (!graph.callNodeAges.contains(node)) {
640 graph.callNodeAges.add(node);
644 if (!graph.reachNode.contains(node)&&!node.isSummary()) {
645 /* Need to age node in existing graph*/
646 summarizeInGraph(graph, newDelta, node);
650 for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.heapedgeadd.entrySet()) {
651 for(Edge e:entry.getValue()) {
652 boolean addedge=false;
654 if (e.statuspredicate==Edge.NEW) {
657 Edge origEdgeKey=e.makeStatus(allocFactory);
658 if (oldgraph.nodeMap.containsKey(origEdgeKey.src)&&
659 oldgraph.nodeMap.get(origEdgeKey.src).contains(origEdgeKey)) {
660 Edge origEdge=oldgraph.nodeMap.get(origEdgeKey.src).get(origEdgeKey);
662 origEdgeKey.statuspredicate=origEdge.statuspredicate;
663 edgetoadd=origEdgeKey;
666 mergeEdge(graph, newDelta, edgetoadd);
669 //Add external edges in
670 for(Edge e:graph.externalEdgeSet) {
671 //First did we age the source
672 Edge newedge=e.copy();
673 if (newedge.src!=null&&!e.src.isSummary()&&graph.callNodeAges.contains(e.src)) {
674 AllocNode summaryNode=allocFactory.getAllocNode(newedge.src, true);
675 newedge.src=summaryNode;
678 if (graph.callNodeAges.contains(e.dst)&&!e.dst.isSummary()) {
679 if (graph.callOldNodes.contains(e.dst)) {
681 Edge copy=newedge.copy();
682 mergeEdge(graph, newDelta, copy);
684 //Now add summarized node
685 newedge.dst=allocFactory.getAllocNode(newedge.dst, true);
686 mergeEdge(graph, newDelta, newedge);
688 //Add edge to single node
689 mergeEdge(graph, newDelta, newedge);
692 //Add edge for return value
693 if (fcall.getReturnTemp()!=null) {
694 MySet<Edge> returnedge=delta.varedgeadd.get(returntmp);
695 if (returnedge!=null)
696 for(Edge e:returnedge) {
697 Edge newedge=e.copy();
698 newedge.srcvar=fcall.getReturnTemp();
699 if (graph.getEdges(fcall.getReturnTemp())==null||!graph.getEdges(fcall.getReturnTemp()).contains(newedge))
700 newDelta.addEdge(newedge);
703 applyDiffs(graph, newDelta);
707 public void mergeEdge(Graph graph, Delta newDelta, Edge edgetoadd) {
708 if (edgetoadd!=null) {
709 Edge match=graph.getMatch(edgetoadd);
711 if (match==null||!match.subsumes(edgetoadd)) {
712 Edge mergededge=edgetoadd.merge(match);
713 newDelta.addEdge(mergededge);
719 /* Summarizes out of context nodes in graph */
720 void summarizeInGraph(Graph graph, Delta newDelta, AllocNode singleNode) {
721 AllocNode summaryNode=allocFactory.getAllocNode(singleNode, true);
723 //Handle outgoing heap edges
724 MySet<Edge> edgeset=graph.getEdges(singleNode);
726 for(Edge e:edgeset) {
727 Edge rewrite=e.rewrite(singleNode, summaryNode);
729 newDelta.removeHeapEdge(e);
730 mergeEdge(graph, newDelta, rewrite);
733 //Handle incoming edges
734 MySet<Edge> backedges=graph.getBackEdges(singleNode);
735 for(Edge e:backedges) {
736 if (e.dst==singleNode) {
737 //Need to get original edge so that predicate will be correct
738 Edge match=graph.getMatch(e);
739 Edge rewrite=match.rewrite(singleNode, summaryNode);
740 newDelta.removeEdge(match);
741 mergeEdge(graph, newDelta, rewrite);
746 void applyDiffs(Graph graph, Delta delta) {
747 applyDiffs(graph, delta, false);
750 void applyDiffs(Graph graph, Delta delta, boolean genbackwards) {
751 //build backwards map if requested
752 if (genbackwards&&graph.backMap==null) {
753 graph.backMap=new HashMap<AllocNode, MySet<Edge>>();
754 if (graph.parent.backMap==null) {
755 graph.parent.backMap=new HashMap<AllocNode, MySet<Edge>>();
756 for(Map.Entry<AllocNode, MySet<Edge>> entry:graph.nodeMap.entrySet()) {
757 for(Edge e:entry.getValue()) {
758 if (!graph.parent.backMap.containsKey(e.dst))
759 graph.parent.backMap.put(e.dst, new MySet<Edge>());
760 graph.parent.backMap.get(e.dst).add(e);
763 for(Map.Entry<TempDescriptor, MySet<Edge>> entry:graph.varMap.entrySet()) {
764 for(Edge e:entry.getValue()) {
765 if (!graph.parent.backMap.containsKey(e.dst))
766 graph.parent.backMap.put(e.dst, new MySet<Edge>());
767 graph.parent.backMap.get(e.dst).add(e);
773 //Add hidden base edges
774 for(Map.Entry<AllocNode, MySet<Edge>> e: delta.baseheapedge.entrySet()) {
775 AllocNode node=e.getKey();
776 MySet<Edge> edges=e.getValue();
777 if (graph.nodeMap.containsKey(node)) {
778 MySet<Edge> nodeEdges=graph.nodeMap.get(node);
779 nodeEdges.addAll(edges);
784 for(Map.Entry<AllocNode, MySet<Edge>> e: delta.heapedgeremove.entrySet()) {
785 AllocNode node=e.getKey();
786 MySet<Edge> edgestoremove=e.getValue();
787 if (graph.nodeMap.containsKey(node)) {
788 //Just apply diff to current map
789 graph.nodeMap.get(node).removeAll(edgestoremove);
791 //Generate diff from parent graph
792 MySet<Edge> parentedges=graph.parent.nodeMap.get(node);
793 if (parentedges!=null) {
794 MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
795 graph.nodeMap.put(node, newedgeset);
801 for(Map.Entry<AllocNode, MySet<Edge>> e: delta.heapedgeadd.entrySet()) {
802 AllocNode node=e.getKey();
803 MySet<Edge> edgestoadd=e.getValue();
804 //If we have not done a subtract, then
805 if (!graph.nodeMap.containsKey(node)) {
806 //Copy the parent entry
807 if (graph.parent.nodeMap.containsKey(node))
808 graph.nodeMap.put(node, (MySet<Edge>)graph.parent.nodeMap.get(node).clone());
810 graph.nodeMap.put(node, new MySet<Edge>());
812 graph.nodeMap.get(node).addAll(edgestoadd);
814 for(Edge eadd:edgestoadd) {
815 if (!graph.backMap.containsKey(eadd.dst))
816 graph.backMap.put(eadd.dst, new MySet<Edge>());
817 graph.backMap.get(eadd.dst).add(eadd);
823 for(Map.Entry<TempDescriptor, MySet<Edge>> e: delta.varedgeremove.entrySet()) {
824 TempDescriptor tmp=e.getKey();
825 MySet<Edge> edgestoremove=e.getValue();
827 if (graph.varMap.containsKey(tmp)) {
828 //Just apply diff to current map
829 graph.varMap.get(tmp).removeAll(edgestoremove);
830 } else if (graph.parent.varMap.containsKey(tmp)) {
831 //Generate diff from parent graph
832 MySet<Edge> parentedges=graph.parent.varMap.get(tmp);
833 MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
834 graph.varMap.put(tmp, newedgeset);
839 for(Map.Entry<TempDescriptor, MySet<Edge>> e: delta.varedgeadd.entrySet()) {
840 TempDescriptor tmp=e.getKey();
841 MySet<Edge> edgestoadd=e.getValue();
842 graph.varMap.put(tmp, (MySet<Edge>) edgestoadd.clone());
844 for(Edge eadd:edgestoadd) {
845 if (!graph.backMap.containsKey(eadd.dst))
846 graph.backMap.put(eadd.dst, new MySet<Edge>());
847 graph.backMap.get(eadd.dst).add(eadd);
853 for(AllocNode node:delta.addNodeAges) {
854 graph.nodeAges.add(node);
857 for(Map.Entry<AllocNode, Boolean> nodeentry:delta.addOldNodes.entrySet()) {
858 AllocNode node=nodeentry.getKey();
859 Boolean ispresent=nodeentry.getValue();
860 graph.oldNodes.put(node, ispresent);
864 Delta processSetFieldElementNode(FlatNode node, Delta delta, Graph graph) {
868 if (node.kind()==FKind.FlatSetElementNode) {
869 FlatSetElementNode fen=(FlatSetElementNode) node;
874 FlatSetFieldNode ffn=(FlatSetFieldNode) node;
879 if (delta.getInit()) {
880 HashSet<AllocNode> srcNodes=GraphManip.getNodes(graph, delta, src);
881 HashSet<AllocNode> dstNodes=GraphManip.getNodes(graph, delta, dst);
882 MySet<Edge> edgesToAdd=GraphManip.genEdges(dstNodes, fd, srcNodes);
883 MySet<Edge> edgesToRemove=null;
884 if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()&&fd!=null) {
885 /* Can do a strong update */
886 edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
887 graph.strongUpdateSet=edgesToRemove;
889 graph.strongUpdateSet=new MySet<Edge>();
891 updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
892 applyDiffs(graph, delta);
894 /* First look at new sources */
895 MySet<Edge> edgesToAdd=new MySet<Edge>();
896 HashSet<AllocNode> newSrcNodes=GraphManip.getDiffNodes(delta, src);
897 HashSet<AllocNode> srcNodes=GraphManip.getNodes(graph, delta, src);
898 HashSet<AllocNode> dstNodes=GraphManip.getNodes(graph, delta, dst);
899 HashSet<AllocNode> newDstNodes=GraphManip.getDiffNodes(delta, dst);
902 MySet<Edge> edgesToRemove=null;
903 if (newDstNodes.size()!=0) {
904 if (dstNodes.size()>1&&!dstNodes.iterator().next().isSummary()&&fd!=null) {
905 /* Need to undo strong update */
906 if (graph.strongUpdateSet!=null) {
907 edgesToAdd.addAll(graph.strongUpdateSet);
908 graph.strongUpdateSet=null; //Prevent future strong updates
910 } else if (dstNodes.size()==1&&newDstNodes.size()==1&&!newDstNodes.iterator().next().isSummary()&&graph.strongUpdateSet!=null&&fd!=null) {
911 edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
912 graph.strongUpdateSet.addAll(edgesToRemove);
914 edgesToAdd.addAll(GraphManip.genEdges(newDstNodes, fd, srcNodes));
918 if (graph.strongUpdateSet!=null&&fd!=null) {
919 MySet<Edge> otherEdgesToRemove=GraphManip.getDiffEdges(delta, dstNodes);
920 if (edgesToRemove!=null)
921 edgesToRemove.addAll(otherEdgesToRemove);
923 edgesToRemove=otherEdgesToRemove;
924 graph.strongUpdateSet.addAll(otherEdgesToRemove);
927 //Next look at new destinations
928 edgesToAdd.addAll(GraphManip.genEdges(dstNodes, fd, newSrcNodes));
931 updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
932 applyDiffs(graph, delta);
937 Delta processCopyNode(FlatNode node, Delta delta, Graph graph) {
940 if (node.kind()==FKind.FlatOpNode) {
941 FlatOpNode fon=(FlatOpNode) node;
944 } else if (node.kind()==FKind.FlatReturnNode) {
945 FlatReturnNode frn=(FlatReturnNode)node;
946 src=frn.getReturnTemp();
948 if (src==null||!src.getType().isPtr()) {
950 applyDiffs(graph, delta);
954 FlatCastNode fcn=(FlatCastNode) node;
958 if (delta.getInit()) {
959 HashSet<AllocNode> srcnodes=GraphManip.getNodes(graph, delta, src);
960 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, srcnodes);
961 MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
962 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
963 applyDiffs(graph, delta);
965 /* First compute new src nodes */
966 HashSet<AllocNode> newSrcNodes=GraphManip.getDiffNodes(delta, src);
968 /* Compute the union, and then the set of edges */
969 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, newSrcNodes);
971 /* Compute set of edges to remove */
972 MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
975 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
976 applyDiffs(graph, delta);
981 Delta processFieldElementNode(FlatNode node, Delta delta, Graph graph) {
985 if (node.kind()==FKind.FlatElementNode) {
986 FlatElementNode fen=(FlatElementNode) node;
991 FlatFieldNode ffn=(FlatFieldNode) node;
996 if (delta.getInit()) {
997 HashSet<AllocNode> srcnodes=GraphManip.getNodes(graph, delta, src);
998 HashSet<AllocNode> fdnodes=GraphManip.getNodes(graph, delta, srcnodes, fd);
999 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, fdnodes);
1000 MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
1001 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1002 applyDiffs(graph, delta);
1004 /* First compute new objects we read fields of */
1005 HashSet<AllocNode> allsrcnodes=GraphManip.getNodes(graph, delta, src);
1006 HashSet<AllocNode> difffdnodes=GraphManip.getDiffNodes(delta, allsrcnodes, fd);
1007 /* Next compute new targets of fields */
1008 HashSet<AllocNode> newsrcnodes=GraphManip.getDiffNodes(delta, src);
1009 HashSet<AllocNode> newfdnodes=GraphManip.getNodes(graph, delta, newsrcnodes, fd);
1010 /* Compute the union, and then the set of edges */
1011 HashSet<AllocNode> newTargets=new HashSet<AllocNode>();
1012 newTargets.addAll(newfdnodes);
1013 newTargets.addAll(difffdnodes);
1014 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, newTargets);
1016 /* Compute set of edges to remove */
1017 MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
1020 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1021 applyDiffs(graph, delta);
1026 static void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1027 MySet<Edge> edgeAdd=delta.varedgeadd.get(tmp);
1028 MySet<Edge> edgeRemove=delta.varedgeremove.get(tmp);
1029 MySet<Edge> existingEdges=graph.getEdges(tmp);
1030 for(Edge e: edgestoRemove) {
1031 //remove edge from delta
1034 //if the edge is already in the graph, add an explicit remove to the delta
1035 if (existingEdges.contains(e))
1036 delta.removeVarEdge(e);
1038 for(Edge e: edgestoAdd) {
1039 //Remove the edge from the remove set
1040 if (edgeRemove!=null)
1041 edgeRemove.remove(e);
1042 //Explicitly add it to the add set unless it is already in the graph
1043 if (!existingEdges.contains(e))
1044 delta.addVarEdge(e);
1048 static void updateHeapDelta(Graph graph, Delta delta, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1049 if (edgestoRemove!=null)
1050 for(Edge e: edgestoRemove) {
1051 AllocNode src=e.src;
1052 MySet<Edge> edgeAdd=delta.heapedgeadd.get(src);
1053 MySet<Edge> existingEdges=graph.getEdges(src);
1054 //remove edge from delta
1057 //if the edge is already in the graph, add an explicit remove to the delta
1058 if (existingEdges.contains(e)) {
1059 delta.removeHeapEdge(e);
1062 if (edgestoAdd!=null)
1063 for(Edge e: edgestoAdd) {
1064 AllocNode src=e.src;
1065 MySet<Edge> edgeRemove=delta.heapedgeremove.get(src);
1066 MySet<Edge> existingEdges=graph.getEdges(src);
1067 //Remove the edge from the remove set
1068 if (edgeRemove!=null)
1069 edgeRemove.remove(e);
1070 //Explicitly add it to the add set unless it is already in the graph
1071 if (!existingEdges.contains(e)||!existingEdges.get(e).isNew()) {
1072 delta.addHeapEdge(e);
1077 Delta processFlatNop(FlatNode node, Delta delta, Graph graph) {
1078 applyDiffs(graph, delta);
1082 Delta processNewNode(FlatNew node, Delta delta, Graph graph) {
1083 AllocNode summary=allocFactory.getAllocNode(node, true);
1084 AllocNode single=allocFactory.getAllocNode(node, false);
1085 TempDescriptor tmp=node.getDst();
1087 if (delta.getInit()) {
1088 /* We don't have to deal with summarization here... The
1089 * intuition is that this is the only place where we generate
1090 * nodes for this allocation site and this is the first time
1091 * we've analyzed this site */
1094 Edge e=new Edge(tmp, single);
1095 //Build new Edge set
1096 MySet<Edge> newedges=new MySet<Edge>();
1098 //Add it into the diffs
1099 delta.varedgeadd.put(tmp, newedges);
1100 //Remove the old edges
1101 delta.varedgeremove.put(tmp, (MySet<Edge>) graph.getEdges(tmp).clone());
1102 //Apply incoming diffs to graph
1103 applyDiffs(graph, delta);
1104 //Note that we create a single node
1105 delta.addNodeAges.add(single);
1107 if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1108 delta.addOldNodes.put(single, Boolean.FALSE);
1111 /* 1. Fix up the variable edge additions */
1113 for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.varedgeadd.entrySet().iterator();entryIt.hasNext();) {
1114 Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1116 if (entry.getKey()==tmp) {
1117 /* Check if this is the tmp we overwrite */
1120 /* Otherwise, check if the target of the edge is changed... */
1121 summarizeSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary);
1125 /* 2. Fix up the base variable edges */
1127 for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.basevaredge.entrySet().iterator();entryIt.hasNext();) {
1128 Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1129 TempDescriptor entrytmp=entry.getKey();
1130 if (entrytmp==tmp) {
1131 /* Check is this is the tmp we overwrite, if so add to remove set */
1132 Util.relationUpdate(delta.varedgeremove, tmp, null, entry.getValue());
1134 /* Check if the target of the edge is changed */
1135 MySet<Edge> newset=(MySet<Edge>)entry.getValue().clone();
1136 MySet<Edge> removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary);
1137 Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset);
1138 Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset);
1143 /* 3. Fix up heap edge additions */
1145 HashMap<AllocNode, MySet<Edge>> addheapedge=new HashMap<AllocNode, MySet<Edge>>();
1146 for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.heapedgeadd.entrySet().iterator();entryIt.hasNext();) {
1147 Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1148 MySet<Edge> edgeset=entry.getValue();
1149 AllocNode allocnode=entry.getKey();
1150 if (allocnode==single) {
1152 summarizeSet(edgeset, graph.nodeMap.get(summary), single, summary);
1153 addheapedge.put(summary, edgeset);
1155 summarizeSet(edgeset, graph.nodeMap.get(allocnode), single, summary);
1159 /* Merge in diffs */
1161 for(Map.Entry<AllocNode, MySet<Edge>> entry:addheapedge.entrySet()) {
1162 AllocNode allocnode=entry.getKey();
1163 Util.relationUpdate(delta.heapedgeadd, allocnode, null, entry.getValue());
1166 /* 4. Fix up the base heap edges */
1168 for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.baseheapedge.entrySet().iterator();entryIt.hasNext();) {
1169 Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1170 MySet<Edge> edgeset=entry.getValue();
1171 AllocNode allocnode=entry.getKey();
1172 if (allocnode==single) {
1175 AllocNode addnode=(allocnode==single)?summary:allocnode;
1177 MySet<Edge> newset=(MySet<Edge>) edgeset.clone();
1178 MySet<Edge> removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary);
1179 Util.relationUpdate(delta.heapedgeadd, addnode, null, newset);
1180 Util.relationUpdate(delta.heapedgeremove, allocnode, null, removeset);
1183 /* Update Node Ages...If the base or addNodeAges set contains a
1184 * single node, it now should also contain a summary node... No
1185 * need to generate a single node as that has already been
1187 if (delta.baseNodeAges.contains(single)||delta.addNodeAges.contains(single)) {
1188 delta.addNodeAges.add(summary);
1191 //Kill the old node if someone tries to add it
1192 if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1193 delta.addOldNodes.put(single, Boolean.FALSE);
1196 //Apply incoming diffs to graph
1197 applyDiffs(graph, delta);
1202 /* This function builds a new edge set where oldnode is summarized into new node */
1204 void summarizeSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode sumnode) {
1205 MySet<Edge> newSet=null;
1206 for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
1207 Edge e=edgeit.next();
1208 if (e.dst==oldnode||e.src==oldnode) {
1210 newSet=new MySet<Edge>();
1215 if (e.dst==oldnode) {
1218 if (e.src==oldnode) {
1221 if (oldedgeset==null||!oldedgeset.contains(e))
1226 edgeset.addAll(newSet);
1229 /* Shrinks the incoming set to just include rewritten values.
1230 * Returns a set of the original rewritten values */
1232 MySet<Edge> shrinkSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode newnode) {
1233 MySet<Edge> newSet=null;
1234 MySet<Edge> removeSet=null;
1235 for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
1236 Edge e=edgeit.next();
1238 if (e.dst==oldnode||e.src==oldnode) {
1240 newSet=new MySet<Edge>();
1241 removeSet=new MySet<Edge>();
1250 if (oldedgeset==null||!oldedgeset.contains(e))
1255 edgeset.addAll(newSet);
1259 /* This function returns a completely new Delta... It is safe to
1262 Delta applyInitDelta(Delta delta, BBlock block) {
1263 //Apply delta to graph
1264 boolean newGraph=false;
1265 if (!bbgraphMap.containsKey(block)) {
1266 bbgraphMap.put(block, new Graph(null));
1270 Graph graph=bbgraphMap.get(block);
1273 newdelta=new Delta(null, true);
1274 //Add in heap edges and throw away original diff
1275 graph.nodeMap.putAll(delta.heapedgeadd);
1276 //Add in var edges and throw away original diff
1277 graph.varMap.putAll(delta.varedgeadd);
1278 //Record that this is initial set...
1279 graph.nodeAges.addAll(delta.addNodeAges);
1281 for(Map.Entry<AllocNode, Boolean> oldentry:delta.addOldNodes.entrySet()) {
1282 if (oldentry.getValue().booleanValue()) {
1283 graph.oldNodes.put(oldentry.getKey(), Boolean.TRUE);
1287 newdelta=new Delta(null, false);
1288 //merge in heap edges and variables
1289 mergeHeapEdges(graph, delta, newdelta);
1290 mergeVarEdges(graph, delta, newdelta);
1291 mergeAges(graph, delta, newdelta);
1297 /* This function merges in the heap edges. It updates delta to be
1300 void mergeHeapEdges(Graph graph, Delta delta, Delta newdelta) {
1302 for(Map.Entry<AllocNode, MySet<Edge>> heapedge:delta.heapedgeadd.entrySet()) {
1303 AllocNode nsrc=heapedge.getKey();
1304 MySet<Edge> edges=heapedge.getValue();
1306 if (graph.backMap!=null) {
1308 if (!graph.backMap.containsKey(e.dst))
1309 graph.backMap.put(e.dst, new MySet<Edge>());
1310 graph.backMap.get(e.dst).add(e);
1314 if (!graph.nodeMap.containsKey(nsrc)) {
1315 graph.nodeMap.put(nsrc, new MySet<Edge>());
1317 MySet<Edge> dstedges=graph.nodeMap.get(nsrc);
1318 MySet<Edge> diffedges=new MySet<Edge>();
1320 if (!dstedges.contains(e)) {
1321 //We have a new edge
1325 Edge origedge=dstedges.get(e);
1326 if (!origedge.subsumes(e)) {
1327 Edge mergededge=origedge.merge(e);
1328 diffedges.add(mergededge);
1329 dstedges.add(mergededge);
1333 //Done with edge set...
1334 if (diffedges.size()>0) {
1336 newdelta.baseheapedge.put(nsrc, diffedges);
1341 /* This function merges in the var edges. It updates delta to be
1344 void mergeVarEdges(Graph graph, Delta delta, Delta newdelta) {
1346 for(Map.Entry<TempDescriptor, MySet<Edge>> varedge:delta.varedgeadd.entrySet()) {
1347 TempDescriptor tmpsrc=varedge.getKey();
1348 MySet<Edge> edges=varedge.getValue();
1349 if (graph.backMap!=null) {
1351 if (!graph.backMap.containsKey(e.dst))
1352 graph.backMap.put(e.dst, new MySet<Edge>());
1353 graph.backMap.get(e.dst).add(e);
1357 if (!graph.varMap.containsKey(tmpsrc)) {
1358 graph.varMap.put(tmpsrc, new MySet<Edge>());
1360 MySet<Edge> dstedges=graph.varMap.get(tmpsrc);
1361 MySet<Edge> diffedges=new MySet<Edge>();
1363 if (!dstedges.contains(e)) {
1364 //We have a new edge
1369 //Done with edge set...
1370 if (diffedges.size()>0) {
1372 newdelta.basevaredge.put(tmpsrc,diffedges);
1377 void mergeAges(Graph graph, Delta delta, Delta newDelta) {
1379 for(AllocNode node:delta.addNodeAges) {
1380 if (!graph.nodeAges.contains(node)) {
1381 graph.nodeAges.add(node);
1382 newDelta.baseNodeAges.add(node);
1385 for(Map.Entry<AllocNode, Boolean> oldentry:delta.addOldNodes.entrySet()) {
1386 AllocNode node=oldentry.getKey();
1387 boolean ispresent=oldentry.getValue().booleanValue();
1388 if (ispresent&&!graph.oldNodes.containsKey(node)) {
1389 graph.oldNodes.put(node, Boolean.TRUE);
1390 newDelta.baseOldNodes.put(node, Boolean.TRUE);