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,-1);
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");
220 effectsAnalysis.buildStateMachines.writeStateMachines();
221 State.logEvent("Done Writing State Machines");
223 if( state.OOODEBUG ) {
224 effectsAnalysis.writeEffects("effects.txt");
225 State.logEvent("Done Writing Effects");
230 void plotGraph(Graph g, String name) {
232 PrintWriter pw=new PrintWriter(new FileWriter(name.toString().replace(' ','_')+".dot"));
233 g.printGraph(pw, name);
235 } catch (Exception ex) {
236 ex.printStackTrace();
241 /* This function builds the last delta for a basic block. It
242 * handles the case for the first time the basic block is
245 void buildInitDelta(Graph graph, Delta newDelta) {
246 //First compute the set of temps
247 HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
248 tmpSet.addAll(graph.varMap.keySet());
249 tmpSet.addAll(graph.parent.varMap.keySet());
251 //Next build the temp map part of the delta
252 for(TempDescriptor tmp : tmpSet) {
253 MySet<Edge> edgeSet=new MySet<Edge>();
255 if (graph.varMap.containsKey(tmp))
256 edgeSet.addAll(graph.varMap.get(tmp));
258 edgeSet.addAll(graph.parent.varMap.get(tmp));
259 newDelta.varedgeadd.put(tmp, edgeSet);
262 //Next compute the set of src allocnodes
263 HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
264 nodeSet.addAll(graph.nodeMap.keySet());
265 nodeSet.addAll(graph.parent.nodeMap.keySet());
267 for(AllocNode node : nodeSet) {
268 MySet<Edge> edgeSet=new MySet<Edge>();
270 if (graph.nodeMap.containsKey(node))
271 edgeSet.addAll(graph.nodeMap.get(node));
273 edgeSet.addAll(graph.parent.nodeMap.get(node));
274 newDelta.heapedgeadd.put(node, edgeSet);
277 if (graph.oldNodes.containsKey(node)) {
278 if (graph.oldNodes.get(node).booleanValue())
279 newDelta.addOldNodes.put(node, Boolean.TRUE);
280 } else if (graph.parent.oldNodes.containsKey(node)) {
281 //parent graphs only contain true...no need to check
282 newDelta.addOldNodes.put(node, Boolean.TRUE);
286 newDelta.addNodeAges.addAll(graph.nodeAges);
287 newDelta.addNodeAges.addAll(graph.parent.nodeAges);
290 /* This function build the delta for the exit of a basic block. */
292 void generateFinalDelta(BBlock bblock, Delta delta, Graph graph) {
293 Delta newDelta=new Delta(null, false);
294 if (delta.getInit()) {
295 buildInitDelta(graph, newDelta);
297 /* We can break the old delta...it is done being used */
298 /* First we will build variable edges */
299 HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
300 tmpSet.addAll(delta.basevaredge.keySet());
301 tmpSet.addAll(delta.varedgeadd.keySet());
302 for(TempDescriptor tmp : tmpSet) {
303 /* Start with the new incoming edges */
304 MySet<Edge> newbaseedge=delta.basevaredge.get(tmp);
305 /* Remove the remove set */
306 if (newbaseedge==null)
307 newbaseedge=new MySet<Edge>();
308 newbaseedge.removeAll(delta.varedgeremove.get(tmp));
309 /* Add in the new set*/
310 newbaseedge.addAll(delta.varedgeadd.get(tmp));
311 /* Store the results */
312 newDelta.varedgeadd.put(tmp, newbaseedge);
314 delta.basevaredge.clear();
316 /* Next we build heap edges */
317 HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
318 nodeSet.addAll(delta.baseheapedge.keySet());
319 nodeSet.addAll(delta.heapedgeadd.keySet());
320 nodeSet.addAll(delta.heapedgeremove.keySet());
321 for(AllocNode node : nodeSet) {
322 /* Start with the new incoming edges */
323 MySet<Edge> newheapedge=new MySet<Edge>(delta.baseheapedge.get(node));
324 /* Remove the remove set */
325 MySet<Edge> removeset=delta.heapedgeremove.get(node);
328 newheapedge.removeAll(removeset);
330 /* Add in the add set */
331 MySet<Edge> settoadd=delta.heapedgeadd.get(node);
333 newheapedge.addAll(settoadd);
334 newDelta.heapedgeadd.put(node, newheapedge);
336 /* Remove the newly created edges..no need to propagate a diff for those */
337 if (removeset!=null) {
338 removeset.removeAll(delta.baseheapedge.get(node));
339 newDelta.heapedgeremove.put(node, removeset);
343 /* Compute new ages */
344 newDelta.addNodeAges.addAll(delta.baseNodeAges);
345 newDelta.addNodeAges.addAll(delta.addNodeAges);
346 HashSet<AllocNode> oldNodes=new HashSet<AllocNode>();
348 /* Compute whether old nodes survive */
349 oldNodes.addAll(delta.baseOldNodes.keySet());
350 oldNodes.addAll(delta.addOldNodes.keySet());
351 for(AllocNode node : oldNodes) {
352 if (delta.addOldNodes.containsKey(node)) {
353 if (delta.addOldNodes.get(node).booleanValue()) {
354 newDelta.addOldNodes.put(node, Boolean.TRUE);
357 if (delta.baseOldNodes.get(node).booleanValue()) {
358 newDelta.addOldNodes.put(node, Boolean.TRUE);
364 if (returnMap.containsKey(bblock)) {
365 //clear everything but our return temp!
366 MySet<Edge> edges=newDelta.varedgeadd.get(returntmp);
367 newDelta.varedgeadd.clear();
368 newDelta.varedgeadd.put(returntmp, edges);
371 /* Now we need to propagate newdelta */
372 if (!newDelta.heapedgeadd.isEmpty()||!newDelta.heapedgeremove.isEmpty()||!newDelta.varedgeadd.isEmpty()||!newDelta.addNodeAges.isEmpty()||!newDelta.addOldNodes.isEmpty()) {
373 /* We have a delta to propagate */
374 if (returnMap.containsKey(bblock)) {
378 for(PPoint caller : returnMap.get(bblock)) {
379 //System.out.println("Sending Return BBlock to "+caller.getBBlock().nodes.get(caller.getIndex()).toString().replace(' ','_'));
382 newDelta.setBlock(caller);
383 toprocess.add(newDelta);
386 Delta d=newDelta.diffBlock(caller);
392 Vector<BBlock> blockvector=bblock.next();
393 for(int i=0; i<blockvector.size(); i++) {
394 //System.out.println("Sending BBlock to "+blockvector.get(i).nodes.get(0).toString().replace(' ','_'));
397 newDelta.setBlock(new PPoint(blockvector.get(i)));
398 toprocess.add(newDelta);
400 Delta d=newDelta.diffBlock(new PPoint(blockvector.get(i)));
406 //System.out.println("EMPTY DELTA");
407 //System.out.println("delta");
409 //System.out.println("newDelta");
414 boolean isNEEDED(FlatNode node) {
415 switch(node.kind()) {
416 case FKind.FlatSetFieldNode: {
417 FlatSetFieldNode n=(FlatSetFieldNode)node;
418 return n.getSrc().getType().isPtr();
421 case FKind.FlatSetElementNode: {
422 FlatSetElementNode n=(FlatSetElementNode)node;
423 return n.getSrc().getType().isPtr();
426 case FKind.FlatFieldNode: {
427 FlatFieldNode n=(FlatFieldNode)node;
428 return n.getDst().getType().isPtr();
431 case FKind.FlatElementNode: {
432 FlatElementNode n=(FlatElementNode)node;
433 return n.getDst().getType().isPtr();
439 Delta processNode(BBlock bblock, int index, FlatNode node, Delta delta, Graph newgraph) {
440 switch(node.kind()) {
442 return processNewNode((FlatNew)node, delta, newgraph);
444 case FKind.FlatFieldNode:
445 case FKind.FlatElementNode:
446 return processFieldElementNode(node, delta, newgraph);
448 case FKind.FlatCastNode:
449 case FKind.FlatOpNode:
450 case FKind.FlatReturnNode:
451 return processCopyNode(node, delta, newgraph);
453 case FKind.FlatSetFieldNode:
454 case FKind.FlatSetElementNode:
455 return processSetFieldElementNode(node, delta, newgraph);
457 case FKind.FlatSESEEnterNode:
458 return processSESEEnterNode((FlatSESEEnterNode) node, delta, newgraph);
460 case FKind.FlatSESEExitNode:
461 return processSESEExitNode((FlatSESEExitNode) node, delta, newgraph);
463 case FKind.FlatMethod:
465 case FKind.FlatBackEdge:
466 case FKind.FlatGenReachNode:
467 return processFlatNop(node, delta, newgraph);
470 return processFlatCall(bblock, index, (FlatCall) node, delta, newgraph);
473 * Pointer Analysis does not care about a flat literal node, just ignores it.
474 * Right now(2011/05/01) we do not attempt to model a flat literal node
475 * for checking runtime pointers.
476 case FKind.FlatLiteralNode:
477 // jjenista - the heap analysis abstraction---when used to verify points-to
478 // analysis results against runtime pointers---will eventually need this to
479 // model that a flat literal node can result in a pointer to an implicitly
480 // allocated string. For now it will pass through like Pointer used to, but
481 // the checks versus runtime pointers will fail for string literals.
486 throw new Error("Unrecognized node:"+node + " of kind " + node.kind());
490 Delta processSESEEnterNode(FlatSESEEnterNode sese, Delta delta, Graph graph) {
492 return processFlatNop(sese, delta, graph);
493 if (delta.getInit()) {
494 removeInitTaints(null, delta, graph);
495 for (TempDescriptor tmp : sese.getInVarSet()) {
496 Taint taint=Taint.factory(sese, null, tmp, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
497 MySet<Edge> edges=GraphManip.getEdges(graph, delta, tmp);
498 for(Edge e : edges) {
499 Edge newe=e.addTaint(taint);
500 delta.addVarEdge(newe);
504 removeDiffTaints(null, delta);
505 for (TempDescriptor tmp : sese.getInVarSet()) {
506 Taint taint=Taint.factory(sese, null, tmp, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
507 MySet<Edge> edges=GraphManip.getDiffEdges(delta, tmp);
508 for(Edge e : edges) {
509 Edge newe=e.addTaint(taint);
510 delta.addVarEdge(newe);
516 applyDiffs(graph, delta);
520 private boolean isRecursive(FlatSESEEnterNode sese) {
521 MethodDescriptor md=sese.getmdEnclosing();
522 boolean isrecursive=callGraph.getCalleeSet(md).contains(md);
526 Delta processSESEExitNode(FlatSESEExitNode seseexit, Delta delta, Graph graph) {
528 return processFlatNop(seseexit, delta, graph);
529 FlatSESEEnterNode sese=seseexit.getFlatEnter();
530 //Strip Taints from this SESE
531 if (delta.getInit()) {
532 removeInitTaints(isRecursive(sese)?null:sese, delta, graph);
534 removeDiffTaints(isRecursive(sese)?null:sese, delta);
536 applyDiffs(graph, delta);
540 void removeDiffTaints(FlatSESEEnterNode sese, Delta delta) {
541 //Start with variable edges
543 MySet<Edge> edgestoadd=new MySet<Edge>();
544 MySet<Edge> edgestoremove=new MySet<Edge>();
546 //Process base diff edges
547 processEdgeMap(sese, delta.basevaredge, null, delta.varedgeremove, edgestoremove, edgestoadd);
548 //Process delta edges
549 processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd);
550 for(Edge e : edgestoremove) {
551 delta.removeVarEdge(e);
553 for(Edge e : edgestoadd) {
560 MySet<Edge> edgestoadd=new MySet<Edge>();
561 MySet<Edge> edgestoremove=new MySet<Edge>();
563 //Process base diff edges
564 processEdgeMap(sese, delta.baseheapedge, null, delta.heapedgeremove, edgestoremove, edgestoadd);
565 //Process delta edges
566 processEdgeMap(sese, delta.heapedgeadd, null, null, edgestoremove, edgestoadd);
567 for(Edge e : edgestoremove) {
568 delta.removeHeapEdge(e);
570 for(Edge e : edgestoadd) {
571 delta.addHeapEdge(e);
576 void removeInitTaints(FlatSESEEnterNode sese, Delta delta, Graph graph) {
577 //Start with variable edges
579 MySet<Edge> edgestoadd=new MySet<Edge>();
580 MySet<Edge> edgestoremove=new MySet<Edge>();
582 //Process parent edges
583 processEdgeMap(sese, graph.parent.varMap, graph.varMap, delta.varedgeremove, edgestoremove, edgestoadd);
584 //Process graph edges
585 processEdgeMap(sese, graph.varMap, null, delta.varedgeremove, edgestoremove, edgestoadd);
586 //Process delta edges
587 processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd);
588 for(Edge e : edgestoremove) {
589 delta.removeVarEdge(e);
591 for(Edge e : edgestoadd) {
598 MySet<Edge> edgestoadd=new MySet<Edge>();
599 MySet<Edge> edgestoremove=new MySet<Edge>();
601 //Process parent edges
602 processEdgeMap(sese, graph.parent.nodeMap, graph.nodeMap, delta.heapedgeremove, edgestoremove, edgestoadd);
603 //Process graph edges
604 processEdgeMap(sese, graph.nodeMap, null, delta.heapedgeremove, edgestoremove, edgestoadd);
605 //Process delta edges
606 processEdgeMap(sese, delta.heapedgeadd, null, null, edgestoremove, edgestoadd);
607 for(Edge e : edgestoremove) {
608 delta.removeHeapEdge(e);
610 for(Edge e : edgestoadd) {
611 delta.addHeapEdge(e);
616 void processEdgeMap(FlatSESEEnterNode sese, HashMap<?, MySet<Edge>> edgemap, HashMap<?, MySet<Edge>> childmap, HashMap<?, MySet<Edge>> removemap, MySet<Edge> edgestoremove, MySet<Edge> edgestoadd) {
617 for(Map.Entry<?, MySet<Edge>> entry:edgemap.entrySet()) {
618 //If the parent map exists and overrides this entry, skip it
619 if (childmap!=null&&childmap.containsKey(entry.getKey()))
621 for(Edge e:entry.getValue()) {
622 //check whether this edge has been removed
623 if (removemap!=null&&removemap.containsKey(entry.getKey())&&
624 removemap.get(entry.getKey()).contains(e))
627 TaintSet ts=e.getTaints();
629 //update non-null taint set
631 newts=Canonical.removeInContextTaintsNP(ts, sese);
632 if (newts!=null&&newts!=ts) {
633 edgestoremove.add(e);
634 edgestoadd.add(e.changeTaintSet(newts));
640 /* This function compute the edges for the this variable for a
641 * callee if it exists. */
643 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) {
644 //Handle the this temp
646 MySet<Edge> edges=(oldnodeset!=null)?GraphManip.getDiffEdges(delta, tmpthis):GraphManip.getEdges(graph, delta, tmpthis);
647 newDelta.varedgeadd.put(tmpthis, (MySet<Edge>)edges.clone());
648 edgeset.addAll(edges);
650 AllocNode dstnode=e.dst;
651 if (!nodeset.contains(dstnode)&&(oldnodeset==null||!oldnodeset.contains(dstnode))) {
652 TypeDescriptor type=dstnode.getType();
653 if (!type.isArray()) {
654 targetSet.add(type.getClassDesc());
656 //arrays don't have code
657 targetSet.add(typeUtil.getClass(TypeUtil.ObjectClass));
659 nodeset.add(dstnode);
660 tovisit.add(dstnode);
666 /* This function compute the edges for a call's parameters. */
668 void processParams(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, FlatCall fcall, boolean diff) {
669 //Go through each temp
670 for(int i=0; i<fcall.numArgs(); i++) {
671 TempDescriptor tmp=fcall.getArg(i);
672 MySet<Edge> edges=diff?GraphManip.getDiffEdges(delta, tmp):GraphManip.getEdges(graph, delta, tmp);
673 newDelta.varedgeadd.put(tmp, (MySet<Edge>)edges.clone());
674 edgeset.addAll(edges);
676 if (!nodeset.contains(e.dst)) {
684 /* This function computes the reachable nodes for a callee. */
686 void computeReachableNodes(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, HashSet<AllocNode> oldnodeset) {
687 while(!tovisit.isEmpty()) {
688 AllocNode node=tovisit.pop();
689 MySet<Edge> edges=GraphManip.getEdges(graph, delta, node);
690 if (!edges.isEmpty()) {
691 newDelta.heapedgeadd.put(node, Edge.makeOld(edges));
692 edgeset.addAll(edges);
693 for(Edge e : edges) {
694 if (!nodeset.contains(e.dst)&&(oldnodeset==null||!oldnodeset.contains(e.dst))) {
703 HashSet<MethodDescriptor> computeTargets(FlatCall fcall, Delta newDelta) {
704 TempDescriptor tmpthis=fcall.getThis();
705 MethodDescriptor md=fcall.getMethod();
706 HashSet<MethodDescriptor> targets=new HashSet<MethodDescriptor>();
707 if (md.isStatic()||fcall.getSuper()) {
711 for(Edge e : newDelta.varedgeadd.get(tmpthis)) {
712 AllocNode node=e.dst;
713 ClassDescriptor cd=node.getType().getClassDesc();
714 //Figure out exact method called and add to set
715 MethodDescriptor calledmd=cd.getCalledMethod(md);
716 targets.add(calledmd);
722 void fixMapping(FlatCall fcall, HashSet<MethodDescriptor> targets, MySet<Edge> oldedgeset, Delta newDelta, BBlock callblock, int callindex) {
723 Delta basedelta=null;
724 TempDescriptor tmpthis=fcall.getThis();
726 for(MethodDescriptor calledmd : targets) {
727 FlatMethod fm=state.getMethodFlat(calledmd);
728 boolean newmethod=false;
731 HashMap<TempDescriptor, TempDescriptor> tmpMap=new HashMap<TempDescriptor, TempDescriptor>();
734 tmpMap.put(tmpthis, fm.getParameter(offset++));
736 for(int i=0; i<fcall.numArgs(); i++) {
737 TempDescriptor tmp=fcall.getArg(i);
738 tmpMap.put(tmp,fm.getParameter(i+offset));
741 //Get basicblock for the method
742 BasicBlock block=getBBlock(fm);
745 if (!callMap.containsKey(fcall)) {
746 callMap.put(fcall, new HashSet<BBlock>());
749 Delta returnDelta=null;
750 if (!callMap.get(fcall).contains(block.getStart())) {
751 callMap.get(fcall).add(block.getStart());
755 if (!returnMap.containsKey(block.getExit())) {
756 returnMap.put(block.getExit(), new HashSet<PPoint>());
758 returnMap.get(block.getExit()).add(new PPoint(callblock, callindex));
760 if (bbgraphMap.containsKey(block.getExit())) {
761 //Need to push existing results to current node
762 if (returnDelta==null) {
763 returnDelta=new Delta(null, false);
764 Vector<FlatNode> exitblocknodes=block.getExit().nodes();
765 FlatExit fexit=(FlatExit)exitblocknodes.get(exitblocknodes.size()-1);
766 buildInitDelta(graphMap.get(fexit), returnDelta);
767 if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
768 returnDelta.setBlock(new PPoint(callblock, callindex));
769 toprocess.add(returnDelta);
772 if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
773 toprocess.add(returnDelta.diffBlock(new PPoint(callblock, callindex)));
779 if (oldedgeset==null) {
780 //First build of this graph
781 //Build and enqueue delta...safe to just use existing delta
782 Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
783 //System.out.println("AProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_'));
786 } else if (newmethod) {
787 if (basedelta==null) {
788 basedelta=newDelta.buildBase(oldedgeset);
790 //Build and enqueue delta
791 Delta d=basedelta.changeParams(tmpMap, new PPoint(block.getStart()));
792 //System.out.println("BProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_'));
796 //Build and enqueue delta
797 Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
798 //System.out.println("CProcessing "+block.getStart().nodes.get(0).toString().replace(' ','_'));
806 /* This function computes all edges that start outside of the callee
807 * context and go into the callee context */
809 void computeExternalEdges(Graph graph, Delta delta, HashSet<AllocNode> nodeset, HashSet<AllocNode> deltaset, MySet<Edge> externaledgeset) {
810 //Do heap edges first
811 HashSet<AllocNode> externalnodes=new HashSet<AllocNode>();
812 externalnodes.addAll(delta.baseheapedge.keySet());
813 externalnodes.addAll(delta.heapedgeadd.keySet());
814 externalnodes.addAll(delta.heapedgeremove.keySet());
815 //remove allinternal nodes
816 externalnodes.removeAll(nodeset);
817 for(AllocNode extNode : externalnodes) {
818 //Compute set of edges from given node
819 MySet<Edge> edges=new MySet<Edge>(delta.baseheapedge.get(extNode));
820 edges.removeAll(delta.heapedgeremove.get(extNode));
821 edges.addAll(delta.heapedgeadd.get(extNode));
823 for(Edge e : edges) {
824 if (nodeset.contains(e.dst))
825 externaledgeset.add(e);
830 HashSet<TempDescriptor> temps=new HashSet<TempDescriptor>();
831 temps.addAll(delta.basevaredge.keySet());
832 temps.addAll(delta.varedgeadd.keySet());
833 temps.addAll(delta.varedgeremove.keySet());
834 //remove allinternal nodes
835 temps.removeAll(nodeset);
837 for(TempDescriptor tmp : temps) {
838 //Compute set of edges from given node
839 MySet<Edge> edges=new MySet<Edge>(delta.basevaredge.get(tmp));
841 edges.removeAll(delta.varedgeremove.get(tmp));
842 edges.addAll(delta.varedgeadd.get(tmp));
844 for(Edge e : edges) {
845 if (nodeset.contains(e.dst))
846 externaledgeset.add(e);
851 /* This function removes the caller reachable edges from the
854 void removeEdges(Graph graph, Delta delta, HashSet<AllocNode> nodeset, MySet<Edge> edgeset, MySet<Edge> externaledgeset) {
855 //Want to remove the set of internal edges
856 for(Edge e : edgeset) {
857 if (e.src!=null&&!graph.callerEdges.contains(e)) {
858 delta.removeHeapEdge(e);
862 //Want to remove the set of external edges
863 for(Edge e : externaledgeset) {
864 //want to remove the set of internal edges
865 if (!graph.callerEdges.contains(e))
870 Delta processFlatCall(BBlock callblock, int callindex, FlatCall fcall, Delta delta, Graph graph) {
871 Delta newDelta=new Delta(null, false);
873 if (delta.getInit()) {
874 MySet<Edge> edgeset=new MySet<Edge>();
875 MySet<Edge> externaledgeset=new MySet<Edge>();
876 HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
877 HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
878 Stack<AllocNode> tovisit=new Stack<AllocNode>();
879 TempDescriptor tmpthis=fcall.getThis();
880 graph.callerEdges=new MySet<Edge>();
882 //Handle the this temp
883 processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, null);
885 //Go through each temp
886 processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, false);
888 //Traverse all reachable nodes
889 computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, null);
891 //Compute call targets
892 HashSet<MethodDescriptor> newtargets=computeTargets(fcall, newDelta);
895 fixMapping(fcall, newtargets, null, newDelta, callblock, callindex);
897 //Compute edges into region to splice out
898 computeExternalEdges(graph, delta, nodeset, null, externaledgeset);
900 //Splice out internal edges
901 removeEdges(graph, delta, nodeset, edgeset, externaledgeset);
903 //store data structures
904 graph.externalEdgeSet=externaledgeset;
905 graph.reachNode=nodeset;
906 graph.reachEdge=edgeset;
908 graph.callTargets=newtargets;
909 graph.callNodeAges=new HashSet<AllocNode>();
910 graph.callOldNodes=new HashSet<AllocNode>();
911 graph.callNewEdges=new HashMap<AllocNode, MySet<Edge>>();
912 graph.callOldEdges=new HashMap<Edge,MySet<Edge>>();
914 //Apply diffs to graph
915 applyDiffs(graph, delta, true);
917 MySet<Edge> edgeset=new MySet<Edge>();
918 MySet<Edge> externaledgeset=new MySet<Edge>();
919 HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
920 MySet<Edge> oldedgeset=graph.reachEdge;
921 HashSet<AllocNode> oldnodeset=graph.reachNode;
923 HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
924 Stack<AllocNode> tovisit=new Stack<AllocNode>();
925 TempDescriptor tmpthis=fcall.getThis();
926 //Fix up delta to get rid of unnecessary heap edge removals
927 for(Map.Entry<AllocNode, MySet<Edge>> entry : delta.heapedgeremove.entrySet()) {
928 for(Iterator<Edge> eit=entry.getValue().iterator(); eit.hasNext(); ) {
930 if (graph.callerEdges.contains(e))
935 //Fix up delta to get rid of unnecessary var edge removals
936 for(Map.Entry<TempDescriptor, MySet<Edge>> entry : delta.varedgeremove.entrySet()) {
937 for(Iterator<Edge> eit=entry.getValue().iterator(); eit.hasNext(); ) {
939 if (graph.callerEdges.contains(e))
944 //Handle the this temp
945 processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, oldnodeset);
947 //Go through each temp
948 processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, true);
949 //Go through each new heap edge that starts from old node
950 MySet<Edge> newedges=GraphManip.getDiffEdges(delta, oldnodeset);
951 edgeset.addAll(newedges);
952 for(Edge e : newedges) {
953 //Add new edges that start from old node to newDelta
955 if (!newDelta.heapedgeadd.containsKey(src)) {
956 newDelta.heapedgeadd.put(src, new MySet<Edge>());
958 newDelta.heapedgeadd.get(src).add(e.makeOld());
959 if (!nodeset.contains(e.dst)&&!oldnodeset.contains(e.dst)) {
965 //Traverse all reachable nodes
966 computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, oldnodeset);
967 //Compute call targets
968 HashSet<MethodDescriptor> newtargets=computeTargets(fcall, newDelta);
969 graph.callTargets.addAll(newtargets);
971 //add in new nodeset and edgeset
972 oldnodeset.addAll(nodeset);
973 oldedgeset.addAll(edgeset);
975 fixMapping(fcall, graph.callTargets, oldedgeset, newDelta, callblock, callindex);
976 //Compute edges into region to splice out
977 computeExternalEdges(graph, delta, oldnodeset, nodeset, externaledgeset);
979 //Splice out internal edges
980 removeEdges(graph, delta, nodeset, edgeset, externaledgeset);
982 //Add external edges back in
983 processCallExternal(graph, delta, externaledgeset);
985 //Move new edges that should be summarized
986 processSummarization(graph, delta);
988 Set<FlatSESEEnterNode> seseCallers=OoOJava?taskAnalysis.getTransitiveExecutingRBlocks(fcall):null;
989 //Check if the new nodes allow us to insert a new edge
990 for(AllocNode node : nodeset) {
991 if (graph.callNewEdges.containsKey(node)) {
992 for(Iterator<Edge> eit=graph.callNewEdges.get(node).iterator(); eit.hasNext(); ) {
994 if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&&
995 (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) {
996 Edge edgetoadd=e.copy(); //we need our own copy to modify below
998 if (seseCallers!=null)
999 edgetoadd.taintModify(seseCallers);
1000 mergeCallEdge(graph, delta, edgetoadd);
1006 for(Edge e : edgeset) {
1007 //See if these edges would allow an old edge to be added
1008 if (graph.callOldEdges.containsKey(e)) {
1009 for(Edge adde : graph.callOldEdges.get(e)) {
1010 Edge ecopy=adde.copy();
1011 ecopy.statuspredicate=e.statuspredicate;
1012 mergeCallEdge(graph, delta, ecopy);
1017 //Add in new external edges
1018 graph.externalEdgeSet.addAll(externaledgeset);
1019 //Apply diffs to graph
1020 applyDiffs(graph, delta);
1025 void processSummarization(Graph graph, Delta delta) {
1026 processSumHeapEdgeSet(delta.heapedgeadd, delta, graph);
1027 processSumHeapEdgeSet(delta.baseheapedge, delta, graph);
1028 processSumVarEdgeSet(delta.varedgeadd, delta, graph);
1029 processSumVarEdgeSet(delta.basevaredge, delta, graph);
1032 void processSumVarEdgeSet(HashMap<TempDescriptor, MySet<Edge>> map, Delta delta, Graph graph) {
1033 MySet<Edge> edgestoadd=new MySet<Edge>();
1034 MySet<Edge> edgestoremove=new MySet<Edge>();
1035 for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> eit=map.entrySet().iterator(); eit.hasNext(); ) {
1036 Map.Entry<TempDescriptor, MySet<Edge>> entry=eit.next();
1037 MySet<Edge> edgeset=entry.getValue();
1039 for(Edge e : edgeset) {
1041 boolean rewrite=false;
1042 if (copy.dst!=null&&graph.callNodeAges.contains(copy.dst)) {
1043 copy.dst=allocFactory.getAllocNode(copy.dst, true);
1047 edgestoremove.add(e);
1048 edgestoadd.add(copy);
1052 for(Edge e : edgestoremove) {
1053 if (!graph.callerEdges.contains(e))
1054 delta.removeVarEdge(e);
1056 for(Edge e : edgestoadd) {
1057 delta.addVarEdge(e);
1061 public Alloc getAllocationSiteFromFlatNew(FlatNew node) {
1062 return allocFactory.getAllocNode(node, false).getAllocSite();
1065 void processSumHeapEdgeSet(HashMap<AllocNode, MySet<Edge>> map, Delta delta, Graph graph) {
1066 MySet<Edge> edgestoadd=new MySet<Edge>();
1067 MySet<Edge> edgestoremove=new MySet<Edge>();
1068 for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> eit=map.entrySet().iterator(); eit.hasNext(); ) {
1069 Map.Entry<AllocNode, MySet<Edge>> entry=eit.next();
1070 AllocNode node=entry.getKey();
1071 MySet<Edge> edgeset=entry.getValue();
1073 for(Edge e : edgeset) {
1075 boolean rewrite=false;
1076 if (copy.src!=null&&graph.callNodeAges.contains(copy.src)) {
1077 copy.src=allocFactory.getAllocNode(copy.src, true);
1080 if (copy.dst!=null&&graph.callNodeAges.contains(copy.dst)) {
1081 copy.dst=allocFactory.getAllocNode(copy.dst, true);
1085 edgestoremove.add(e);
1086 edgestoadd.add(copy);
1090 for(Edge e : edgestoremove) {
1091 if (!graph.callerEdges.contains(e))
1092 delta.removeHeapEdge(e);
1094 for(Edge e : edgestoadd) {
1095 delta.addHeapEdge(e);
1099 //Handle external edges
1100 void processCallExternal(Graph graph, Delta newDelta, MySet<Edge> externalEdgeSet) {
1101 //Add external edges in
1102 for(Edge e : externalEdgeSet) {
1103 //First did we age the source
1104 Edge newedge=e.copy();
1105 if (newedge.src!=null&&!e.src.isSummary()&&graph.callNodeAges.contains(e.src)) {
1106 AllocNode summaryNode=allocFactory.getAllocNode(newedge.src, true);
1107 newedge.src=summaryNode;
1110 if (graph.callNodeAges.contains(e.dst)&&!e.dst.isSummary()) {
1111 if (graph.callOldNodes.contains(e.dst)) {
1113 Edge copy=newedge.copy();
1114 mergeEdge(graph, newDelta, copy);
1116 //Now add summarized node
1117 newedge.dst=allocFactory.getAllocNode(newedge.dst, true);
1118 mergeCallEdge(graph, newDelta, newedge);
1120 //Add edge to single node
1121 mergeEdge(graph, newDelta, newedge);
1126 /* This function applies callee deltas to the caller heap. */
1128 Delta applyCallDelta(Delta delta, BBlock bblock) {
1129 Delta newDelta=new Delta(null, false);
1130 Vector<FlatNode> nodes=bblock.nodes();
1131 PPoint ppoint=delta.getBlock();
1132 FlatCall fcall=(FlatCall)nodes.get(ppoint.getIndex());
1133 Graph graph=graphMap.get(fcall);
1134 Graph oldgraph=(ppoint.getIndex()==0)?
1135 bbgraphMap.get(bblock):
1136 graphMap.get(nodes.get(ppoint.getIndex()-1));
1137 Set<FlatSESEEnterNode> seseCallers=OoOJava?taskAnalysis.getTransitiveExecutingRBlocks(fcall):null;
1139 //Age outside nodes if necessary
1140 for(Iterator<AllocNode> nodeit=delta.addNodeAges.iterator(); nodeit.hasNext(); ) {
1141 AllocNode node=nodeit.next();
1142 if (!graph.callNodeAges.contains(node)) {
1143 graph.callNodeAges.add(node);
1144 newDelta.addNodeAges.add(node);
1146 AllocNode summaryAdd=null;
1147 if (!graph.reachNode.contains(node)&&!node.isSummary()) {
1148 /* Need to age node in existing graph*/
1150 AllocNode summaryNode=allocFactory.getAllocNode(node, true);
1152 if (!graph.callNodeAges.contains(summaryNode)) {
1153 graph.callNodeAges.add(summaryNode);
1154 newDelta.addNodeAges.add(summaryNode);
1155 summaryAdd=summaryNode;
1157 summarizeInGraph(graph, newDelta, node);
1160 if (graph.callNewEdges.containsKey(node)) {
1161 for(Iterator<Edge> eit=graph.callNewEdges.get(node).iterator(); eit.hasNext(); ) {
1163 if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&&
1164 (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) {
1165 Edge edgetoadd=e.copy(); //we need our own copy to modify below
1167 if (seseCallers!=null)
1168 edgetoadd.taintModify(seseCallers);
1169 mergeCallEdge(graph, newDelta, edgetoadd);
1173 //do the summary node if we added that also...
1176 } while(node!=null);
1180 for(Map.Entry<AllocNode, MySet<Edge>> entry : delta.heapedgeadd.entrySet()) {
1181 for(Edge e : entry.getValue()) {
1182 boolean addedge=false;
1183 Edge edgetoadd=null;
1184 if (e.statuspredicate==Edge.NEW) {
1185 if ((graph.callNodeAges.contains(e.src)||graph.reachNode.contains(e.src))&&
1186 (graph.callNodeAges.contains(e.dst)||graph.reachNode.contains(e.dst))) {
1187 edgetoadd=e.copy(); //we need our own copy to modify below
1189 graph.addCallEdge(e);
1192 Edge[] edgeArray=e.makeStatus(allocFactory);
1194 int statuspredicate=0;
1195 for(int i=0; i<edgeArray.length; i++) {
1196 Edge origEdgeKey=edgeArray[i];
1197 if (graph.reachEdge.contains(origEdgeKey)) {
1198 Edge origEdge=graph.reachEdge.get(origEdgeKey);
1199 //copy the predicate
1200 statuspredicate=statuspredicate|origEdge.statuspredicate;
1202 if (!graph.callOldEdges.containsKey(origEdgeKey)) {
1203 graph.callOldEdges.put(origEdgeKey, new MySet<Edge>());
1205 if (graph.callOldEdges.get(origEdgeKey).contains(e)) {
1206 Edge olde=graph.callOldEdges.get(origEdgeKey).get(e);
1207 graph.callOldEdges.get(origEdgeKey).add(olde.merge(e));
1209 graph.callOldEdges.get(origEdgeKey).add(e);
1212 if (statuspredicate!=0) {
1214 newe.statuspredicate=statuspredicate;
1218 if (seseCallers!=null&&edgetoadd!=null)
1219 edgetoadd.taintModify(seseCallers);
1220 mergeCallEdge(graph, newDelta, edgetoadd);
1224 processCallExternal(graph, newDelta, graph.externalEdgeSet);
1226 //Add edge for return value
1227 if (fcall.getReturnTemp()!=null) {
1228 MySet<Edge> returnedge=delta.varedgeadd.get(returntmp);
1229 if (returnedge!=null)
1230 for(Edge e : returnedge) {
1231 //skip the edge if types don't allow it...
1232 if (!typeUtil.isSuperorType(fcall.getReturnTemp().getType(), e.dst.getType()))
1234 Edge newedge=e.copy();
1235 newedge.srcvar=fcall.getReturnTemp();
1236 if (seseCallers!=null)
1237 newedge.taintModify(seseCallers);
1238 mergeEdge(graph, newDelta, newedge);
1241 applyDiffs(graph, newDelta);
1245 public void mergeEdge(Graph graph, Delta newDelta, Edge edgetoadd) {
1246 if (edgetoadd!=null) {
1247 Edge match=graph.getMatch(edgetoadd);
1249 if (match==null||!match.subsumes(edgetoadd)) {
1250 Edge mergededge=edgetoadd.merge(match);
1251 newDelta.addEdge(mergededge);
1256 /* This is a call produced edge...need to remember this */
1258 public void mergeCallEdge(Graph graph, Delta newDelta, Edge edgetoadd) {
1259 if (edgetoadd!=null) {
1260 newDelta.addEdgeClear(edgetoadd);
1262 Edge match=graph.getMatch(edgetoadd);
1264 if (match==null||!match.subsumes(edgetoadd)) {
1265 Edge mergededge=edgetoadd.merge(match);
1266 newDelta.addEdge(mergededge);
1267 graph.callerEdges.add(mergededge);
1273 /* Summarizes out of context nodes in graph */
1274 void summarizeInGraph(Graph graph, Delta newDelta, AllocNode singleNode) {
1275 AllocNode summaryNode=allocFactory.getAllocNode(singleNode, true);
1277 //Handle outgoing heap edges
1278 MySet<Edge> edgeset=graph.getEdges(singleNode);
1280 for(Edge e : edgeset) {
1281 Edge rewrite=e.rewrite(singleNode, summaryNode);
1283 newDelta.removeHeapEdge(e);
1284 mergeCallEdge(graph, newDelta, rewrite);
1287 //Handle incoming edges
1288 MySet<Edge> backedges=graph.getBackEdges(singleNode);
1289 for(Edge e : backedges) {
1290 if (e.dst==singleNode) {
1291 //Need to get original edge so that predicate will be correct
1292 Edge match=graph.getMatch(e);
1294 Edge rewrite=match.rewrite(singleNode, summaryNode);
1295 newDelta.removeEdge(match);
1296 mergeCallEdge(graph, newDelta, rewrite);
1302 void applyDiffs(Graph graph, Delta delta) {
1303 applyDiffs(graph, delta, false);
1306 void applyDiffs(Graph graph, Delta delta, boolean genbackwards) {
1307 //build backwards map if requested
1308 if (genbackwards&&graph.backMap==null) {
1309 graph.backMap=new HashMap<AllocNode, MySet<Edge>>();
1310 if (graph.parent.backMap==null) {
1311 graph.parent.backMap=new HashMap<AllocNode, MySet<Edge>>();
1312 for(Map.Entry<AllocNode, MySet<Edge>> entry : graph.nodeMap.entrySet()) {
1313 for(Edge e : entry.getValue()) {
1314 if (!graph.parent.backMap.containsKey(e.dst))
1315 graph.parent.backMap.put(e.dst, new MySet<Edge>());
1316 graph.parent.backMap.get(e.dst).add(e);
1319 for(Map.Entry<TempDescriptor, MySet<Edge>> entry : graph.varMap.entrySet()) {
1320 for(Edge e : entry.getValue()) {
1321 if (!graph.parent.backMap.containsKey(e.dst))
1322 graph.parent.backMap.put(e.dst, new MySet<Edge>());
1323 graph.parent.backMap.get(e.dst).add(e);
1329 //Add hidden base edges
1330 for(Map.Entry<AllocNode, MySet<Edge>> e : delta.baseheapedge.entrySet()) {
1331 AllocNode node=e.getKey();
1332 MySet<Edge> edges=e.getValue();
1333 if (graph.nodeMap.containsKey(node)) {
1334 MySet<Edge> nodeEdges=graph.nodeMap.get(node);
1335 nodeEdges.addAll(edges);
1340 for(Map.Entry<AllocNode, MySet<Edge>> e : delta.heapedgeremove.entrySet()) {
1341 AllocNode node=e.getKey();
1342 MySet<Edge> edgestoremove=e.getValue();
1343 if (graph.nodeMap.containsKey(node)) {
1344 //Just apply diff to current map
1345 graph.nodeMap.get(node).removeAll(edgestoremove);
1347 //Generate diff from parent graph
1348 MySet<Edge> parentedges=graph.parent.nodeMap.get(node);
1349 if (parentedges!=null) {
1350 MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
1351 graph.nodeMap.put(node, newedgeset);
1357 for(Map.Entry<AllocNode, MySet<Edge>> e : delta.heapedgeadd.entrySet()) {
1358 AllocNode node=e.getKey();
1359 MySet<Edge> edgestoadd=e.getValue();
1360 //If we have not done a subtract, then
1361 if (!graph.nodeMap.containsKey(node)) {
1362 //Copy the parent entry
1363 if (graph.parent.nodeMap.containsKey(node))
1364 graph.nodeMap.put(node, (MySet<Edge>)graph.parent.nodeMap.get(node).clone());
1366 graph.nodeMap.put(node, new MySet<Edge>());
1368 Edge.mergeEdgesInto(graph.nodeMap.get(node),edgestoadd);
1370 for(Edge eadd : edgestoadd) {
1371 if (!graph.backMap.containsKey(eadd.dst))
1372 graph.backMap.put(eadd.dst, new MySet<Edge>());
1373 graph.backMap.get(eadd.dst).add(eadd);
1379 for(Map.Entry<TempDescriptor, MySet<Edge>> e : delta.varedgeremove.entrySet()) {
1380 TempDescriptor tmp=e.getKey();
1381 MySet<Edge> edgestoremove=e.getValue();
1383 if (graph.varMap.containsKey(tmp)) {
1384 //Just apply diff to current map
1385 graph.varMap.get(tmp).removeAll(edgestoremove);
1386 } else if (graph.parent.varMap.containsKey(tmp)) {
1387 //Generate diff from parent graph
1388 MySet<Edge> parentedges=graph.parent.varMap.get(tmp);
1389 MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
1390 graph.varMap.put(tmp, newedgeset);
1395 for(Map.Entry<TempDescriptor, MySet<Edge>> e : delta.varedgeadd.entrySet()) {
1396 TempDescriptor tmp=e.getKey();
1397 MySet<Edge> edgestoadd=e.getValue();
1398 if (graph.varMap.containsKey(tmp)) {
1399 Edge.mergeEdgesInto(graph.varMap.get(tmp), edgestoadd);
1400 } else if (graph.parent.varMap.containsKey(tmp)) {
1401 graph.varMap.put(tmp, new MySet<Edge>(graph.parent.varMap.get(tmp)));
1402 Edge.mergeEdgesInto(graph.varMap.get(tmp), edgestoadd);
1404 graph.varMap.put(tmp, (MySet<Edge>)edgestoadd.clone());
1406 for(Edge eadd : edgestoadd) {
1407 if (!graph.backMap.containsKey(eadd.dst))
1408 graph.backMap.put(eadd.dst, new MySet<Edge>());
1409 graph.backMap.get(eadd.dst).add(eadd);
1414 //Add node additions
1415 for(AllocNode node : delta.addNodeAges) {
1416 graph.nodeAges.add(node);
1419 for(Map.Entry<AllocNode, Boolean> nodeentry : delta.addOldNodes.entrySet()) {
1420 AllocNode node=nodeentry.getKey();
1421 Boolean ispresent=nodeentry.getValue();
1422 graph.oldNodes.put(node, ispresent);
1426 boolean isINACC(FlatNode node) {
1429 switch(node.kind()) {
1430 case FKind.FlatSetFieldNode: {
1431 FlatSetFieldNode n=(FlatSetFieldNode)node;
1432 return !accessible.isAccessible(n, n.getDst());
1435 case FKind.FlatSetElementNode: {
1436 FlatSetElementNode n=(FlatSetElementNode)node;
1437 return !accessible.isAccessible(n, n.getDst());
1440 case FKind.FlatFieldNode: {
1441 FlatFieldNode n=(FlatFieldNode)node;
1442 return !accessible.isAccessible(n, n.getSrc());
1445 case FKind.FlatElementNode: {
1446 FlatElementNode n=(FlatElementNode)node;
1447 return !accessible.isAccessible(n, n.getSrc());
1453 Delta processSetFieldElementNode(FlatNode node, Delta delta, Graph graph) {
1457 if (node.kind()==FKind.FlatSetElementNode) {
1458 FlatSetElementNode fen=(FlatSetElementNode) node;
1463 FlatSetFieldNode ffn=(FlatSetFieldNode) node;
1469 if (delta.getInit()) {
1470 MySet<Edge> dstEdges=GraphManip.getEdges(graph, delta, dst);
1472 if (OoOJava&&!accessible.isAccessible(node, dst)) {
1473 Taint dstStallTaint=Taint.factory(node, dst, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1474 dstEdges=Edge.taintAll(dstEdges, dstStallTaint);
1475 updateVarDelta(graph, delta, dst, dstEdges, null);
1478 effectsAnalysis.analyzeFlatSetFieldNode(dstEdges, fd, node);
1481 //Do nothing for non pointers
1482 if (!src.getType().isPtr()) {
1483 if (mustProcess.contains(node)) {
1484 applyDiffs(graph, delta);
1489 MySet<Edge> srcEdges=GraphManip.getEdges(graph, delta, src);
1490 if (OoOJava&&!accessible.isAccessible(node, src)) {
1491 Taint srcStallTaint=Taint.factory(node, src, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1492 srcEdges=Edge.taintAll(srcEdges, srcStallTaint);
1493 updateVarDelta(graph, delta, src, srcEdges, null);
1496 MySet<Edge> edgesToAdd=GraphManip.genEdges(dstEdges, fd, srcEdges);
1497 MySet<Edge> edgesToRemove=null;
1498 if (dstEdges.size()==1&&!dstEdges.iterator().next().dst.isSummary()&&fd!=null) {
1499 /* Can do a strong update */
1500 edgesToRemove=GraphManip.getEdges(graph, delta, dstEdges, fd);
1501 graph.strongUpdateSet=edgesToRemove;
1503 graph.strongUpdateSet=new MySet<Edge>();
1506 updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
1507 applyDiffs(graph, delta);
1509 MySet<Edge> newDstEdges=GraphManip.getDiffEdges(delta, dst);
1511 if (OoOJava&&!accessible.isAccessible(node, dst)) {
1512 Taint dstStallTaint=Taint.factory(node, dst, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1513 newDstEdges=Edge.taintAll(newDstEdges, dstStallTaint);
1514 updateVarDelta(graph, delta, dst, newDstEdges, null);
1518 effectsAnalysis.analyzeFlatSetFieldNode(newDstEdges, fd, node);
1521 if (!src.getType().isPtr()) {
1522 if (mustProcess.contains(node)) {
1523 applyDiffs(graph, delta);
1528 /* Next look at new sources */
1530 MySet<Edge> edgesToAdd=new MySet<Edge>();
1531 MySet<Edge> newSrcEdges=GraphManip.getDiffEdges(delta, src);
1532 MySet<Edge> srcEdges=GraphManip.getEdges(graph, delta, src);
1533 HashSet<AllocNode> dstNodes=GraphManip.getNodes(graph, delta, dst);
1535 if (OoOJava&&!accessible.isAccessible(node, src)) {
1536 Taint srcStallTaint=Taint.factory(node, src, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1537 newSrcEdges=Edge.taintAll(newSrcEdges, srcStallTaint);
1538 updateVarDelta(graph, delta, src, newSrcEdges, null);
1541 MySet<Edge> edgesToRemove=null;
1542 if (newDstEdges.size()!=0) {
1543 if (dstNodes.size()>1&&!dstNodes.iterator().next().isSummary()&&fd!=null) {
1544 /* Need to undo strong update */
1545 if (graph.strongUpdateSet!=null) {
1546 edgesToAdd.addAll(graph.strongUpdateSet);
1547 graph.strongUpdateSet=null; //Prevent future strong updates
1549 } else if (dstNodes.size()==1&&newDstEdges.size()==1&&!newDstEdges.iterator().next().dst.isSummary()&&graph.strongUpdateSet!=null&&fd!=null) {
1550 edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
1551 graph.strongUpdateSet.addAll(edgesToRemove);
1553 Edge.mergeEdgesInto(edgesToAdd, GraphManip.genEdges(newDstEdges, fd, srcEdges));
1557 if (graph.strongUpdateSet!=null&&fd!=null) {
1558 MySet<Edge> otherEdgesToRemove=GraphManip.getDiffEdges(delta, dstNodes, fd);
1559 if (edgesToRemove!=null)
1560 edgesToRemove.addAll(otherEdgesToRemove);
1562 edgesToRemove=otherEdgesToRemove;
1563 graph.strongUpdateSet.addAll(otherEdgesToRemove);
1566 //Next look at new destinations
1567 Edge.mergeEdgesInto(edgesToAdd, GraphManip.genEdges(dstNodes, fd, newSrcEdges));
1570 updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
1571 applyDiffs(graph, delta);
1576 Delta processCopyNode(FlatNode node, Delta delta, Graph graph) {
1580 if (node.kind()==FKind.FlatOpNode) {
1581 FlatOpNode fon=(FlatOpNode) node;
1584 } else if (node.kind()==FKind.FlatReturnNode) {
1585 FlatReturnNode frn=(FlatReturnNode)node;
1586 src=frn.getReturnTemp();
1588 if (src==null||!src.getType().isPtr()) {
1590 applyDiffs(graph, delta);
1594 FlatCastNode fcn=(FlatCastNode) node;
1598 if (delta.getInit()) {
1599 MySet<Edge> srcedges=GraphManip.getEdges(graph, delta, src);
1600 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, srcedges);
1601 MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
1602 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1603 applyDiffs(graph, delta);
1605 /* First compute new src nodes */
1606 MySet<Edge> newSrcEdges=GraphManip.getDiffEdges(delta, src);
1608 /* Compute the union, and then the set of edges */
1609 MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, newSrcEdges);
1611 /* Compute set of edges to remove */
1612 MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
1615 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1616 applyDiffs(graph, delta);
1621 Delta processFieldElementNode(FlatNode node, Delta delta, Graph graph) {
1625 TaintSet taint=null;
1627 if (node.kind()==FKind.FlatElementNode) {
1628 FlatElementNode fen=(FlatElementNode) node;
1633 FlatFieldNode ffn=(FlatFieldNode) node;
1638 if (OoOJava&&!accessible.isAccessible(node, src)) {
1639 taint=TaintSet.factory(Taint.factory(node, src, AllocFactory.dummySite, null, ReachGraph.predsEmpty));
1642 //Do nothing for non pointers
1643 if (delta.getInit()) {
1644 MySet<Edge> srcedges=GraphManip.getEdges(graph, delta, src);
1647 srcedges=Edge.taintAll(srcedges, taint);
1648 updateVarDelta(graph, delta, src, srcedges, null);
1650 effectsAnalysis.analyzeFlatFieldNode(srcedges, fd, node);
1652 if (!dst.getType().isPtr()) {
1653 if (mustProcess.contains(node)) {
1654 applyDiffs(graph, delta);
1659 MySet<Edge> edgesToAdd=GraphManip.dereference(graph, delta, dst, srcedges, fd, node);
1660 MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
1662 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1663 applyDiffs(graph, delta);
1665 MySet<Edge> newsrcedges=GraphManip.getDiffEdges(delta, src);
1668 newsrcedges=Edge.taintAll(newsrcedges, taint);
1669 updateVarDelta(graph, delta, src, newsrcedges, null);
1671 effectsAnalysis.analyzeFlatFieldNode(newsrcedges, fd, node);
1673 if (!dst.getType().isPtr()) {
1674 if (mustProcess.contains(node)) {
1675 applyDiffs(graph, delta);
1679 /* First compute new objects we read fields of */
1680 MySet<Edge> allsrcedges=GraphManip.getEdges(graph, delta, src);
1681 MySet<Edge> edgesToAdd=GraphManip.diffDereference(delta, dst, allsrcedges, fd, node);
1682 /* Next compute new targets of fields */
1683 MySet<Edge> newfdedges=GraphManip.dereference(graph, delta, dst, newsrcedges, fd, node);
1685 /* Compute the union, and then the set of edges */
1686 Edge.mergeEdgesInto(edgesToAdd, newfdedges);
1688 /* Compute set of edges to remove */
1689 MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
1693 updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1694 applyDiffs(graph, delta);
1700 void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1701 MySet<Edge> edgeAdd=delta.varedgeadd.get(tmp);
1702 MySet<Edge> edgeRemove=delta.varedgeremove.get(tmp);
1703 MySet<Edge> existingEdges=graph.getEdges(tmp);
1704 if (edgestoRemove!=null)
1705 for(Edge e : edgestoRemove) {
1706 //remove edge from delta
1709 //if the edge is already in the graph, add an explicit remove to the delta
1710 if (existingEdges.contains(e))
1711 delta.removeVarEdge(e);
1713 for(Edge e : edgestoAdd) {
1714 //Remove the edge from the remove set
1715 if (edgeRemove!=null)
1716 edgeRemove.remove(e);
1717 //Explicitly add it to the add set unless it is already in the graph
1718 if (typeUtil.isSuperorType(tmp.getType(), e.dst.getType())) {
1719 if (!existingEdges.contains(e)) {
1720 delta.addVarEdge(e);
1722 //See if the old edge subsumes the new one
1723 Edge olde=existingEdges.get(e);
1724 if (!olde.subsumes(e)) {
1725 delta.addVarEdge(olde.merge(e));
1732 void updateHeapDelta(Graph graph, Delta delta, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1733 if (edgestoRemove!=null)
1734 for(Edge e : edgestoRemove) {
1735 AllocNode src=e.src;
1736 MySet<Edge> edgeAdd=delta.heapedgeadd.get(src);
1737 MySet<Edge> existingEdges=graph.getEdges(src);
1738 //remove edge from delta
1741 //if the edge is already in the graph, add an explicit remove to the delta
1742 if (existingEdges.contains(e)) {
1743 delta.removeHeapEdge(e);
1746 if (edgestoAdd!=null)
1747 for(Edge e : edgestoAdd) {
1748 AllocNode src=e.src;
1749 MySet<Edge> edgeRemove=delta.heapedgeremove.get(src);
1750 MySet<Edge> existingEdges=graph.getEdges(src);
1751 //Remove the edge from the remove set
1752 if (edgeRemove!=null)
1753 edgeRemove.remove(e);
1754 //Explicitly add it to the add set unless it is already in the graph
1755 if (!existingEdges.contains(e)) {
1756 delta.addHeapEdge(e);
1758 //See if the old edge subsumes the new one
1759 Edge olde=existingEdges.get(e);
1760 if (!olde.subsumes(e)) {
1761 delta.addHeapEdge(olde.merge(e));
1767 Delta processFlatNop(FlatNode node, Delta delta, Graph graph) {
1768 applyDiffs(graph, delta);
1772 Delta processNewNode(FlatNew node, Delta delta, Graph graph) {
1773 AllocNode summary=allocFactory.getAllocNode(node, true);
1774 AllocNode single=allocFactory.getAllocNode(node, false);
1775 TempDescriptor tmp=node.getDst();
1777 if (delta.getInit()) {
1778 /* We don't have to deal with summarization here... The
1779 * intuition is that this is the only place where we generate
1780 * nodes for this allocation site and this is the first time
1781 * we've analyzed this site */
1784 Edge e=new Edge(tmp, single);
1785 //Build new Edge set
1786 MySet<Edge> newedges=new MySet<Edge>();
1788 //Add it into the diffs
1789 delta.varedgeadd.put(tmp, newedges);
1790 //Remove the old edges
1791 MySet<Edge> oldedges=graph.getEdges(tmp);
1792 if (!oldedges.isEmpty())
1793 delta.varedgeremove.put(tmp, (MySet<Edge>)oldedges);
1794 //Note that we create a single node
1795 delta.addNodeAges.add(single);
1797 if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1798 delta.addOldNodes.put(single, Boolean.FALSE);
1801 /* 1. Fix up the variable edge additions */
1802 for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.varedgeadd.entrySet().iterator(); entryIt.hasNext(); ) {
1803 Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1805 if (entry.getKey()==tmp) {
1806 /* Check if this is the tmp we overwrite */
1809 /* Otherwise, check if the target of the edge is changed... */
1810 summarizeSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary);
1814 /* 2. Fix up the base variable edges */
1816 for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.basevaredge.entrySet().iterator(); entryIt.hasNext(); ) {
1817 Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1818 TempDescriptor entrytmp=entry.getKey();
1819 if (entrytmp==tmp) {
1820 /* Check is this is the tmp we overwrite, if so add to remove set */
1821 Util.relationUpdate(delta.varedgeremove, tmp, null, entry.getValue());
1822 } else if (graph.varMap.containsKey(entrytmp)) {
1823 /* Check if the target of the edge is changed */
1824 MySet<Edge> newset=(MySet<Edge>)entry.getValue().clone();
1825 MySet<Edge> removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary);
1826 Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset);
1827 Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset);
1829 /* Check if the target of the edge is changed */
1830 MySet<Edge> newset=(MySet<Edge>)entry.getValue().clone();
1831 MySet<Edge> removeset=shrinkSet(newset, graph.parent.varMap.get(entrytmp), single, summary);
1832 Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset);
1833 Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset);
1838 /* 3. Fix up heap edge additions */
1840 HashMap<AllocNode, MySet<Edge>> addheapedge=new HashMap<AllocNode, MySet<Edge>>();
1841 for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.heapedgeadd.entrySet().iterator(); entryIt.hasNext(); ) {
1842 Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1843 MySet<Edge> edgeset=entry.getValue();
1844 AllocNode allocnode=entry.getKey();
1845 if (allocnode==single) {
1847 summarizeSet(edgeset, graph.nodeMap.get(summary), single, summary);
1848 addheapedge.put(summary, edgeset);
1850 summarizeSet(edgeset, graph.nodeMap.get(allocnode), single, summary);
1854 /* Merge in diffs */
1856 for(Map.Entry<AllocNode, MySet<Edge>> entry : addheapedge.entrySet()) {
1857 AllocNode allocnode=entry.getKey();
1858 Util.relationUpdate(delta.heapedgeadd, allocnode, null, entry.getValue());
1861 /* 4. Fix up the base heap edges */
1863 for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.baseheapedge.entrySet().iterator(); entryIt.hasNext(); ) {
1864 Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1865 MySet<Edge> edgeset=entry.getValue();
1866 AllocNode allocnode=entry.getKey();
1867 if (allocnode==single) {
1870 AllocNode addnode=(allocnode==single)?summary:allocnode;
1872 MySet<Edge> newset=(MySet<Edge>)edgeset.clone();
1873 MySet<Edge> removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary);
1874 Util.relationUpdate(delta.heapedgeadd, addnode, null, newset);
1875 Util.relationUpdate(delta.heapedgeremove, allocnode, null, removeset);
1878 /* Update Node Ages...If the base or addNodeAges set contains a
1879 * single node, it now should also contain a summary node... No
1880 * need to generate a single node as that has already been
1882 if (delta.baseNodeAges.contains(single)||delta.addNodeAges.contains(single)) {
1883 delta.addNodeAges.add(summary);
1886 //Kill the old node if someone tries to add it
1887 if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1888 delta.addOldNodes.put(single, Boolean.FALSE);
1892 //Apply incoming diffs to graph
1893 applyDiffs(graph, delta);
1898 /* This function builds a new edge set where oldnode is summarized into new node */
1900 void summarizeSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode sumnode) {
1901 MySet<Edge> newSet=null;
1902 for(Iterator<Edge> edgeit=edgeset.iterator(); edgeit.hasNext(); ) {
1903 Edge e=edgeit.next();
1904 if (e.dst==oldnode||e.src==oldnode) {
1906 newSet=new MySet<Edge>();
1911 if (e.dst==oldnode) {
1914 if (e.src==oldnode) {
1917 if (oldedgeset==null||!oldedgeset.contains(e))
1922 edgeset.addAll(newSet);
1925 /* Shrinks the incoming set to just include rewritten values.
1926 * Returns a set of the original rewritten values */
1928 MySet<Edge> shrinkSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode newnode) {
1929 MySet<Edge> newSet=null;
1930 MySet<Edge> removeSet=null;
1931 for(Iterator<Edge> edgeit=edgeset.iterator(); edgeit.hasNext(); ) {
1932 Edge e=edgeit.next();
1934 if (e.dst==oldnode||e.src==oldnode) {
1936 newSet=new MySet<Edge>();
1937 removeSet=new MySet<Edge>();
1946 if (oldedgeset==null||!oldedgeset.contains(e))
1951 edgeset.addAll(newSet);
1955 /* This function returns a completely new Delta... It is safe to
1958 Delta applyInitDelta(Delta delta, BBlock block) {
1959 //Apply delta to graph
1960 boolean newGraph=false;
1961 if (!bbgraphMap.containsKey(block)) {
1962 bbgraphMap.put(block, new Graph(null));
1965 Graph graph=bbgraphMap.get(block);
1968 Delta newdelta=new Delta(null, true);
1969 //Add in heap edges and throw away original diff
1971 for(Map.Entry<AllocNode, MySet<Edge>> entry : delta.heapedgeadd.entrySet()) {
1972 graph.nodeMap.put(entry.getKey(), new MySet<Edge>(entry.getValue()));
1974 //Add in var edges and throw away original diff
1975 Set<TempDescriptor> livetemps=bblivetemps.get(block);
1977 for(Map.Entry<TempDescriptor, MySet<Edge>> entry : delta.varedgeadd.entrySet()) {
1978 if (livetemps.contains(entry.getKey()))
1979 graph.varMap.put(entry.getKey(), new MySet<Edge>(entry.getValue()));
1981 //Record that this is initial set...
1982 graph.nodeAges.addAll(delta.addNodeAges);
1984 for(Map.Entry<AllocNode, Boolean> oldentry : delta.addOldNodes.entrySet()) {
1985 if (oldentry.getValue().booleanValue()) {
1986 graph.oldNodes.put(oldentry.getKey(), Boolean.TRUE);
1991 Delta newdelta=new Delta(null, false);
1992 //merge in heap edges and variables
1993 mergeHeapEdges(graph, delta, newdelta);
1994 mergeVarEdges(graph, delta, newdelta, block);
1995 mergeAges(graph, delta, newdelta);
2000 /* This function merges in the heap edges. It updates delta to be
2003 void mergeHeapEdges(Graph graph, Delta delta, Delta newdelta) {
2005 for(Map.Entry<AllocNode, MySet<Edge>> heapedge : delta.heapedgeadd.entrySet()) {
2006 AllocNode nsrc=heapedge.getKey();
2007 MySet<Edge> edges=heapedge.getValue();
2009 if (graph.backMap!=null) {
2010 for(Edge e : edges) {
2011 if (!graph.backMap.containsKey(e.dst))
2012 graph.backMap.put(e.dst, new MySet<Edge>());
2013 graph.backMap.get(e.dst).add(e);
2017 if (!graph.nodeMap.containsKey(nsrc)) {
2018 graph.nodeMap.put(nsrc, new MySet<Edge>());
2020 MySet<Edge> dstedges=graph.nodeMap.get(nsrc);
2021 MySet<Edge> diffedges=new MySet<Edge>();
2022 for(Edge e : edges) {
2023 if (!dstedges.contains(e)) {
2024 //We have a new edge
2028 Edge origedge=dstedges.get(e);
2029 if (!origedge.subsumes(e)) {
2030 Edge mergededge=origedge.merge(e);
2031 diffedges.add(mergededge);
2032 dstedges.add(mergededge);
2036 //Done with edge set...
2037 if (diffedges.size()>0) {
2039 newdelta.baseheapedge.put(nsrc, diffedges);
2044 /* This function merges in the var edges. It updates delta to be
2047 void mergeVarEdges(Graph graph, Delta delta, Delta newdelta, BBlock block) {
2049 Set<TempDescriptor> livetemps=bblivetemps.get(block);
2051 for(Map.Entry<TempDescriptor, MySet<Edge>> varedge : delta.varedgeadd.entrySet()) {
2052 TempDescriptor tmpsrc=varedge.getKey();
2053 if (livetemps.contains(tmpsrc)) {
2054 MySet<Edge> edges=varedge.getValue();
2055 if (graph.backMap!=null) {
2056 for(Edge e : edges) {
2057 if (!graph.backMap.containsKey(e.dst))
2058 graph.backMap.put(e.dst, new MySet<Edge>());
2059 graph.backMap.get(e.dst).add(e);
2063 if (!graph.varMap.containsKey(tmpsrc)) {
2064 graph.varMap.put(tmpsrc, new MySet<Edge>());
2066 MySet<Edge> dstedges=graph.varMap.get(tmpsrc);
2067 MySet<Edge> diffedges=new MySet<Edge>();
2068 for(Edge e : edges) {
2069 if (!dstedges.contains(e)) {
2070 //We have a new edge
2074 Edge origedge=dstedges.get(e);
2075 if (!origedge.subsumes(e)) {
2076 Edge mergededge=origedge.merge(e);
2077 diffedges.add(mergededge);
2078 dstedges.add(mergededge);
2082 //Done with edge set...
2083 if (diffedges.size()>0) {
2085 newdelta.basevaredge.put(tmpsrc,diffedges);
2091 void mergeAges(Graph graph, Delta delta, Delta newDelta) {
2093 for(AllocNode node : delta.addNodeAges) {
2094 if (!graph.nodeAges.contains(node)) {
2095 graph.nodeAges.add(node);
2096 newDelta.baseNodeAges.add(node);
2099 for(Map.Entry<AllocNode, Boolean> oldentry : delta.addOldNodes.entrySet()) {
2100 AllocNode node=oldentry.getKey();
2101 boolean ispresent=oldentry.getValue().booleanValue();
2102 if (ispresent&&!graph.oldNodes.containsKey(node)) {
2103 graph.oldNodes.put(node, Boolean.TRUE);
2104 newDelta.baseOldNodes.put(node, Boolean.TRUE);
2112 public Alloc getCmdLineArgsAlloc() {
2115 public Alloc getCmdLineArgAlloc() {
2118 public Alloc getCmdLineArgBytesAlloc() {
2121 public Alloc getNewStringLiteralAlloc() {
2124 public Alloc getNewStringLiteralBytesAlloc() {
2128 public Set<Alloc> canPointToAt( TempDescriptor x,
2129 FlatNode programPoint ) {
2133 public Hashtable< Alloc, Set<Alloc> > canPointToAt( TempDescriptor x,
2135 FlatNode programPoint ) {
2139 public Hashtable< Alloc, Set<Alloc> > canPointToAtElement( TempDescriptor x,
2140 FlatNode programPoint ) {
2144 public Set<Alloc> canPointToAfter( TempDescriptor x,
2145 FlatNode programPoint ) {
2149 public Hashtable< Alloc, Set<Alloc> > canPointToAfter( TempDescriptor x,
2151 FlatNode programPoint ) {
2155 public Hashtable< Alloc, Set<Alloc> > canPointToAfterElement( TempDescriptor x, // x[i]
2156 FlatNode programPoint ) {