Robust/src/Analysis/Pointer/Pointer.java

   1 package Analysis.Pointer;
   2 import java.util.*;
   3 import IR.Flat.*;
   4 import IR.*;
   5 import Analysis.Pointer.BasicBlock.BBlock;
   6 import Analysis.Pointer.AllocFactory.AllocNode;
   7 import java.io.*;
   8
   9 public class Pointer {
  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;
  15
  16   State state;
  17   TypeUtil typeUtil;
  18   AllocFactory allocFactory;
  19   LinkedList<Delta> toprocess;
  20   TempDescriptor returntmp;
  21
  22   public Pointer(State state, TypeUtil typeUtil) {
  23     this.state=state;
  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);
  34   }
  35
  36   public BasicBlock getBBlock(FlatMethod fm) {
  37     if (!blockMap.containsKey(fm))
  38       blockMap.put(fm, BasicBlock.getBBlock(fm));
  39     return blockMap.get(fm);
  40   }
  41
  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);
  54
  55     return delta;
  56   }
  57
  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();
  65       int startindex=0;
  66       System.out.println("BB BEGIN");
  67       delta.print();
  68
  69       if (ppoint.getIndex()==-1) {
  70         //Build base graph for entrance to this basic block
  71         System.out.println("INIT");
  72         delta=applyInitDelta(delta, bblock);
  73       } else {
  74         System.out.println("CALL");
  75         startindex=ppoint.getIndex()+1;
  76         delta=applyCallDelta(delta, bblock);
  77       }
  78       Graph graph=bbgraphMap.get(bblock);
  79       Graph nodeGraph=null;
  80       //Compute delta at exit of each node
  81       for(int i=startindex; i<nodes.size();i++) {
  82         FlatNode currNode=nodes.get(i);
  83         System.out.println(currNode);
  84         delta.print();
  85
  86         if (!graphMap.containsKey(currNode)) {
  87           graphMap.put(currNode, new Graph(graph));
  88         }
  89         nodeGraph=graphMap.get(currNode);
  90         delta=processNode(bblock, i, currNode, delta, nodeGraph);
  91       }
  92       System.out.println("LOOPEXIT");
  93       delta.print();
  94       generateFinalDelta(bblock, delta, nodeGraph);
  95     }
  96
  97     //DEBUG
  98     int debugindex=0;
  99     for(Map.Entry<BBlock, Graph> e:bbgraphMap.entrySet()) {
 100       Graph g=e.getValue();
 101       plotGraph(g,"BB"+debugindex);
 102       debugindex++;
 103     }
 104
 105     for(Map.Entry<FlatNode, Graph> e:graphMap.entrySet()) {
 106       FlatNode fn=e.getKey();
 107       Graph g=e.getValue();
 108       plotGraph(g,"FN"+fn.toString()+debugindex);
 109       debugindex++;
 110     }
 111     for(FlatMethod fm:blockMap.keySet()) {
 112       fm.printMethod();
 113     }
 114   }
 115
 116   void plotGraph(Graph g, String name) {
 117     try {
 118       PrintWriter pw=new PrintWriter(new FileWriter(name.toString().replace(' ','_')+".dot"));
 119       g.printGraph(pw, name);
 120       pw.close();
 121     } catch (Exception ex) {
 122       ex.printStackTrace();
 123     }
 124   }
 125
 126
 127   /* This function builds the last delta for a basic block.  It
 128    * handles the case for the first time the basic block is
 129    * evaluated.*/
 130
 131   void buildInitDelta(Graph graph, Delta newDelta) {
 132     //First compute the set of temps
 133     HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
 134     tmpSet.addAll(graph.varMap.keySet());
 135     tmpSet.addAll(graph.parent.varMap.keySet());
 136
 137     //Next build the temp map part of the delta
 138     for(TempDescriptor tmp:tmpSet) {
 139       MySet<Edge> edgeSet=new MySet<Edge>();
 140       /* Get target set */
 141       if (graph.varMap.containsKey(tmp))
 142         edgeSet.addAll(graph.varMap.get(tmp));
 143       else
 144         edgeSet.addAll(graph.parent.varMap.get(tmp));
 145       newDelta.varedgeadd.put(tmp, edgeSet);
 146     }
 147
 148     //Next compute the set of src allocnodes
 149     HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
 150     nodeSet.addAll(graph.nodeMap.keySet());
 151     nodeSet.addAll(graph.parent.nodeMap.keySet());
 152
 153     for(AllocNode node:nodeSet) {
 154       MySet<Edge> edgeSet=new MySet<Edge>();
 155       /* Get edge set */
 156       if (graph.nodeMap.containsKey(node))
 157         edgeSet.addAll(graph.nodeMap.get(node));
 158       else
 159         edgeSet.addAll(graph.parent.nodeMap.get(node));
 160       newDelta.heapedgeadd.put(node, edgeSet);
 161
 162       /* Compute ages */
 163       if (graph.nodeAges.contains(node))
 164         newDelta.addNodeAges.add(node);
 165       else if (graph.parent.nodeAges.contains(node))
 166         newDelta.addNodeAges.add(node);
 167
 168       /* Compute ages */
 169       if (graph.oldNodes.containsKey(node)) {
 170         if (graph.oldNodes.get(node).booleanValue())
 171           newDelta.addOldNodes.put(node, Boolean.TRUE);
 172       } else if (graph.parent.oldNodes.containsKey(node)) {
 173         //parent graphs only contain true...no need to check
 174         newDelta.addOldNodes.put(node, Boolean.TRUE);
 175       }
 176     }
 177   }
 178
 179   /* This function build the delta for the exit of a basic block. */
 180
 181   void generateFinalDelta(BBlock bblock, Delta delta, Graph graph) {
 182     Delta newDelta=new Delta(null, false);
 183     if (delta.getInit()) {
 184       buildInitDelta(graph, newDelta);
 185     } else {
 186       /* We can break the old delta...it is done being used */
 187       /* First we will build variable edges */
 188       HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
 189       tmpSet.addAll(delta.basevaredge.keySet());
 190       tmpSet.addAll(delta.varedgeadd.keySet());
 191       System.out.println(tmpSet);
 192       for(TempDescriptor tmp:tmpSet) {
 193         /* Start with the new incoming edges */
 194         MySet<Edge> newbaseedge=delta.basevaredge.get(tmp);
 195         /* Remove the remove set */
 196         if (newbaseedge==null)
 197           newbaseedge=new MySet<Edge>();
 198         newbaseedge.removeAll(delta.varedgeremove.get(tmp));
 199         /* Add in the new set*/
 200         newbaseedge.addAll(delta.varedgeadd.get(tmp));
 201         /* Store the results */
 202         newDelta.varedgeadd.put(tmp, newbaseedge);
 203       }
 204       delta.basevaredge.clear();
 205
 206       /* Next we build heap edges */
 207       HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
 208       nodeSet.addAll(delta.baseheapedge.keySet());
 209       nodeSet.addAll(delta.heapedgeadd.keySet());
 210       nodeSet.addAll(delta.heapedgeremove.keySet());
 211       for(AllocNode node:nodeSet) {
 212         /* Start with the new incoming edges */
 213         MySet<Edge> newheapedge=new MySet<Edge>(delta.baseheapedge.get(node));
 214         /* Remove the remove set */
 215         MySet<Edge> removeset=delta.heapedgeremove.get(node);
 216
 217         if (removeset!=null)
 218           newheapedge.removeAll(removeset);
 219
 220         /* Add in the add set */
 221         MySet<Edge> settoadd=delta.heapedgeadd.get(node);
 222         if (settoadd!=null)
 223           newheapedge.addAll(settoadd);
 224         newDelta.heapedgeadd.put(node, newheapedge);
 225
 226         /* Remove the newly created edges..no need to propagate a diff for those */
 227         if (removeset!=null) {
 228           removeset.removeAll(delta.baseheapedge.get(node));
 229           newDelta.heapedgeremove.put(node, removeset);
 230         }
 231       }
 232
 233       /* Compute new ages */
 234       newDelta.addNodeAges.addAll(delta.baseNodeAges);
 235       newDelta.addNodeAges.addAll(delta.addNodeAges);
 236       HashSet<AllocNode> oldNodes=new HashSet<AllocNode>();
 237
 238       /* Compute whether old nodes survive */
 239       oldNodes.addAll(delta.baseOldNodes.keySet());
 240       oldNodes.addAll(delta.addOldNodes.keySet());
 241       for(AllocNode node:oldNodes) {
 242         if (delta.addOldNodes.containsKey(node)) {
 243           if (delta.addOldNodes.get(node).booleanValue()) {
 244             newDelta.addOldNodes.put(node, Boolean.TRUE);
 245           }
 246         } else {
 247           if (delta.baseOldNodes.get(node).booleanValue()) {
 248             newDelta.addOldNodes.put(node, Boolean.TRUE);
 249           }
 250         }
 251       }
 252     }
 253     System.out.println("FINAL");
 254     newDelta.print();
 255
 256     /* Now we need to propagate newdelta */
 257     if (!newDelta.heapedgeadd.isEmpty()||!newDelta.heapedgeremove.isEmpty()||!newDelta.varedgeadd.isEmpty()||!newDelta.addNodeAges.isEmpty()||!newDelta.addOldNodes.isEmpty()) {
 258       /* We have a delta to propagate */
 259       if (returnMap.containsKey(bblock)) {
 260         //exit of call block
 261         boolean first=true;
 262
 263         for(PPoint caller:returnMap.get(bblock)) {
 264           if (first) {
 265             newDelta.setBlock(caller);
 266             toprocess.add(newDelta);
 267             first=false;
 268           } else {
 269             Delta d=newDelta.diffBlock(caller);
 270             toprocess.add(d);
 271           }
 272         }
 273       } else {
 274         //normal block
 275         Vector<BBlock> blockvector=bblock.next();
 276         for(int i=0;i<blockvector.size();i++) {
 277           if (i==0) {
 278             newDelta.setBlock(new PPoint(blockvector.get(i)));
 279             toprocess.add(newDelta);
 280           } else {
 281             Delta d=newDelta.diffBlock(new PPoint(blockvector.get(i)));
 282             toprocess.add(d);
 283           }
 284         }
 285       }
 286     }
 287   }
 288
 289   Delta processNode(BBlock bblock, int index, FlatNode node, Delta delta, Graph newgraph) {
 290     switch(node.kind()) {
 291     case FKind.FlatNew:
 292       return processNewNode((FlatNew)node, delta, newgraph);
 293     case FKind.FlatFieldNode:
 294     case FKind.FlatElementNode:
 295       return processFieldElementNode(node, delta, newgraph);
 296     case FKind.FlatCastNode:
 297     case FKind.FlatOpNode:
 298     case FKind.FlatReturnNode:
 299       return processCopyNode(node, delta, newgraph);
 300     case FKind.FlatSetFieldNode:
 301     case FKind.FlatSetElementNode:
 302       return processSetFieldElementNode(node, delta, newgraph);
 303     case FKind.FlatMethod:
 304     case FKind.FlatExit:
 305     case FKind.FlatBackEdge:
 306     case FKind.FlatGenReachNode:
 307       return processFlatNop(node, delta, newgraph);
 308     case FKind.FlatCall:
 309       return processFlatCall(bblock, index, (FlatCall) node, delta, newgraph);
 310     case FKind.FlatSESEEnterNode:
 311     case FKind.FlatSESEExitNode:
 312       throw new Error("Unimplemented node:"+node);
 313     default:
 314       throw new Error("Unrecognized node:"+node);
 315     }
 316   }
 317
 318   /* This function compute the edges for the this variable for a
 319    * callee if it exists. */
 320
 321   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) {
 322     //Handle the this temp
 323     if (tmpthis!=null) {
 324       MySet<Edge> edges=(oldnodeset!=null)?GraphManip.getDiffEdges(delta, tmpthis):GraphManip.getEdges(graph, delta, tmpthis);
 325       newDelta.varedgeadd.put(tmpthis, (MySet<Edge>) edges.clone());
 326       edgeset.addAll(edges);
 327       for(Edge e:edges) {
 328         AllocNode dstnode=e.dst;
 329         if (!nodeset.contains(dstnode)&&(oldnodeset==null||!oldnodeset.contains(dstnode))) {
 330           TypeDescriptor type=dstnode.getType();
 331           if (!type.isArray()) {
 332             targetSet.add(type.getClassDesc());
 333           } else {
 334             //arrays don't have code
 335             targetSet.add(typeUtil.getClass(TypeUtil.ObjectClass));
 336           }
 337           nodeset.add(dstnode);
 338           tovisit.add(dstnode);
 339         }
 340       }
 341     }
 342   }
 343
 344   /* This function compute the edges for a call's parameters. */
 345
 346   void processParams(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, FlatCall fcall, boolean diff) {
 347     //Go through each temp
 348     for(int i=0;i<fcall.numArgs();i++) {
 349       TempDescriptor tmp=fcall.getArg(i);
 350       MySet<Edge> edges=diff?GraphManip.getDiffEdges(delta, tmp):GraphManip.getEdges(graph, delta, tmp);
 351       newDelta.varedgeadd.put(tmp, (MySet<Edge>) edges.clone());
 352       edgeset.addAll(edges);
 353       for(Edge e:edges) {
 354         if (!nodeset.contains(e.dst)) {
 355           nodeset.add(e.dst);
 356           tovisit.add(e.dst);
 357         }
 358       }
 359     }
 360   }
 361
 362   /* This function computes the reachable nodes for a callee. */
 363
 364   void computeReachableNodes(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, HashSet<AllocNode> oldnodeset) {
 365       while(!tovisit.isEmpty()) {
 366         AllocNode node=tovisit.pop();
 367         MySet<Edge> edges=GraphManip.getEdges(graph, delta, node);
 368         newDelta.heapedgeadd.put(node, edges);
 369         edgeset.addAll(edges);
 370         for(Edge e:edges) {
 371           if (!nodeset.contains(e.dst)&&(oldnodeset==null||!oldnodeset.contains(e.dst))) {
 372             nodeset.add(e.dst);
 373             tovisit.add(e.dst);
 374           }
 375         }
 376       }
 377   }
 378
 379   HashSet<MethodDescriptor> computeTargets(FlatCall fcall, Delta newDelta) {
 380     TempDescriptor tmpthis=fcall.getThis();
 381     MethodDescriptor md=fcall.getMethod();
 382     HashSet<MethodDescriptor> targets=new HashSet<MethodDescriptor>();
 383     if (md.isStatic()) {
 384       targets.add(md);
 385     } else {
 386       //Compute Edges
 387       for(Edge e:newDelta.varedgeadd.get(tmpthis)) {
 388         AllocNode node=e.dst;
 389         ClassDescriptor cd=node.getType().getClassDesc();
 390         //Figure out exact method called and add to set
 391         targets.add(cd.getCalledMethod(md));
 392       }
 393     }
 394     return targets;
 395   }
 396
 397   void fixMapping(FlatCall fcall, HashSet<MethodDescriptor> targets, MySet<Edge> oldedgeset, Delta newDelta, BBlock callblock, int callindex) {
 398     Delta basedelta=null;
 399     TempDescriptor tmpthis=fcall.getThis();
 400
 401     for(MethodDescriptor calledmd:targets) {
 402       FlatMethod fm=state.getMethodFlat(calledmd);
 403       boolean newmethod=false;
 404
 405       //Build tmpMap
 406       HashMap<TempDescriptor, TempDescriptor> tmpMap=new HashMap<TempDescriptor, TempDescriptor>();
 407       int offset=0;
 408       if(tmpthis!=null) {
 409         tmpMap.put(tmpthis, fm.getParameter(offset++));
 410       }
 411       for(int i=0;i<fcall.numArgs();i++) {
 412         TempDescriptor tmp=fcall.getArg(i);
 413         tmpMap.put(tmp,fm.getParameter(i+offset));
 414       }
 415
 416       //Get basicblock for the method
 417       BasicBlock block=getBBlock(fm);
 418
 419       //Hook up exits
 420       if (!callMap.containsKey(fcall)) {
 421         callMap.put(fcall, new HashSet<BBlock>());
 422       }
 423
 424       Delta returnDelta=null;
 425       if (!callMap.get(fcall).contains(block.getStart())) {
 426         callMap.get(fcall).add(block.getStart());
 427         newmethod=true;
 428
 429         //Hook up return
 430         if (!returnMap.containsKey(block.getExit())) {
 431           returnMap.put(block.getExit(), new HashSet<PPoint>());
 432         }
 433         returnMap.get(block.getExit()).add(new PPoint(callblock, callindex));
 434
 435         if (bbgraphMap.containsKey(block.getExit())) {
 436           //Need to push existing results to current node
 437           if (returnDelta==null) {
 438             returnDelta=new Delta(null, false);
 439             Vector<FlatNode> exitblocknodes=block.getExit().nodes();
 440             FlatExit fexit=(FlatExit)exitblocknodes.get(exitblocknodes.size()-1);
 441             buildInitDelta(graphMap.get(fexit), returnDelta);
 442             if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
 443               returnDelta.setBlock(new PPoint(callblock, callindex));
 444               toprocess.add(returnDelta);
 445             }
 446           } else {
 447             if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
 448               toprocess.add(returnDelta.diffBlock(new PPoint(callblock, callindex)));
 449             }
 450           }
 451         }
 452       }
 453
 454       if (oldedgeset==null) {
 455         //First build of this graph
 456         //Build and enqueue delta...safe to just use existing delta
 457         Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
 458         toprocess.add(d);
 459       } else if (newmethod) {
 460         if (basedelta==null) {
 461           basedelta=newDelta.buildBase(oldedgeset);
 462         }
 463         //Build and enqueue delta
 464         Delta d=basedelta.changeParams(tmpMap, new PPoint(block.getStart()));
 465         toprocess.add(d);
 466       } else  {
 467         //Build and enqueue delta
 468         Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
 469         toprocess.add(d);
 470       }
 471     }
 472   }
 473
 474
 475   /* This function computes all edges that start outside of the callee context and go into the callee context */
 476
 477   void computeExternalEdges(Graph graph, Delta delta, HashSet<AllocNode> nodeset, HashSet<AllocNode> deltaset, MySet<Edge> externaledgeset) {
 478     //Do heap edges first
 479     HashSet<AllocNode> externalnodes=new HashSet<AllocNode>();
 480     externalnodes.addAll(delta.baseheapedge.keySet());
 481     externalnodes.addAll(delta.heapedgeadd.keySet());
 482     externalnodes.addAll(delta.heapedgeremove.keySet());
 483     //remove allinternal nodes
 484     externalnodes.removeAll(nodeset);
 485     for(AllocNode extNode:externalnodes) {
 486       //Compute set of edges from given node
 487       MySet<Edge> edges=new MySet<Edge>(delta.baseheapedge.get(extNode));
 488       edges.removeAll(delta.heapedgeremove.get(extNode));
 489       edges.addAll(delta.heapedgeadd.get(extNode));
 490
 491       for(Edge e:edges) {
 492         if (nodeset.contains(e.dst))
 493           externaledgeset.add(e);
 494       }
 495     }
 496
 497     //Do heap edges first
 498     HashSet<TempDescriptor> temps=new HashSet<TempDescriptor>();
 499     temps.addAll(delta.basevaredge.keySet());
 500     temps.addAll(delta.varedgeadd.keySet());
 501     temps.addAll(delta.varedgeremove.keySet());
 502     //remove allinternal nodes
 503     temps.removeAll(nodeset);
 504
 505     for(TempDescriptor tmp:temps) {
 506       //Compute set of edges from given node
 507       MySet<Edge> edges=new MySet<Edge>(delta.basevaredge.get(tmp));
 508
 509       edges.removeAll(delta.varedgeremove.get(tmp));
 510       edges.addAll(delta.varedgeadd.get(tmp));
 511
 512       for(Edge e:edges) {
 513         if (nodeset.contains(e.dst))
 514           externaledgeset.add(e);
 515       }
 516     }
 517   }
 518
 519   /* This function removes the caller reachable edges from the
 520    * callee's heap. */
 521
 522   void removeEdges(Delta delta, HashSet<AllocNode> nodeset, MySet<Edge> edgeset, MySet<Edge> externaledgeset) {
 523     //Want to remove the set of internal edges
 524     for(Edge e:edgeset) {
 525       if (e.src!=null) {
 526         delta.removeHeapEdge(e);
 527       }
 528     }
 529
 530     //Want to remove the set of external edges
 531     for(Edge e:externaledgeset) {
 532       //want to remove the set of internal edges
 533       delta.removeEdge(e);
 534     }
 535   }
 536
 537   Delta processFlatCall(BBlock callblock, int callindex, FlatCall fcall, Delta delta, Graph graph) {
 538     Delta newDelta=new Delta(null, false);
 539
 540     if (delta.getInit()) {
 541       MySet<Edge> edgeset=new MySet<Edge>();
 542       MySet<Edge> externaledgeset=new MySet<Edge>();
 543       HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
 544       HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
 545       Stack<AllocNode> tovisit=new Stack<AllocNode>();
 546       TempDescriptor tmpthis=fcall.getThis();
 547
 548       //Handle the this temp
 549       processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, null);
 550
 551       //Go through each temp
 552       processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, false);
 553
 554       //Traverse all reachable nodes
 555       computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, null);
 556
 557       //Compute call targets
 558       HashSet<MethodDescriptor> targets=computeTargets(fcall, newDelta);
 559
 560       //Fix mapping
 561       fixMapping(fcall, targets, null, newDelta, callblock, callindex);
 562
 563       //Compute edges into region to splice out
 564       computeExternalEdges(graph, delta, nodeset, null, externaledgeset);
 565
 566       //Splice out internal edges
 567       removeEdges(delta, nodeset, edgeset, externaledgeset);
 568
 569       //store data structures
 570       graph.externalEdgeSet=externaledgeset;
 571       graph.reachNode=nodeset;
 572       graph.reachEdge=edgeset;
 573
 574       graph.callNodeAges=new HashSet<AllocNode>();
 575       graph.callOldNodes=new HashSet<AllocNode>();
 576
 577       //Apply diffs to graph
 578       applyDiffs(graph, delta, true);
 579     } else {
 580       MySet<Edge> edgeset=new MySet<Edge>();
 581       MySet<Edge> externaledgeset=new MySet<Edge>();
 582       HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
 583       MySet<Edge> oldedgeset=graph.reachEdge;
 584       HashSet<AllocNode> oldnodeset=graph.reachNode;
 585
 586       HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
 587       Stack<AllocNode> tovisit=new Stack<AllocNode>();
 588       TempDescriptor tmpthis=fcall.getThis();
 589
 590       //Handle the this temp
 591       processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, oldnodeset);
 592
 593       //Go through each temp
 594       processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, true);
 595
 596       //Go through each new heap edge that starts from old node
 597       MySet<Edge> newedges=GraphManip.getDiffEdges(delta, oldnodeset);
 598       edgeset.addAll(newedges);
 599       for(Edge e:newedges) {
 600         if (!nodeset.contains(e.dst)&&!oldnodeset.contains(e.dst)) {
 601           nodeset.add(e.dst);
 602           tovisit.add(e.dst);
 603         }
 604       }
 605
 606       //Traverse all reachable nodes
 607       computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, oldnodeset);
 608
 609       //Compute call targets
 610       HashSet<MethodDescriptor> targets=computeTargets(fcall, newDelta);
 611
 612       //add in new nodeset and edgeset
 613       oldnodeset.addAll(nodeset);
 614       oldedgeset.addAll(edgeset);
 615
 616       //Fix mapping
 617       fixMapping(fcall, targets, oldedgeset, newDelta, callblock, callindex);
 618
 619       //Compute edges into region to splice out
 620       computeExternalEdges(graph, delta, oldnodeset, nodeset, externaledgeset);
 621
 622       //Splice out internal edges
 623       removeEdges(delta, nodeset, edgeset, externaledgeset);
 624
 625       //Add in new external edges
 626       graph.externalEdgeSet.addAll(externaledgeset);
 627
 628       //Apply diffs to graph
 629       applyDiffs(graph, delta);
 630     }
 631     return delta;
 632   }
 633
 634   /* This function applies callee deltas to the caller heap. */
 635
 636   Delta applyCallDelta(Delta delta, BBlock bblock) {
 637     Delta newDelta=new Delta(null, false);
 638     Vector<FlatNode> nodes=bblock.nodes();
 639     PPoint ppoint=delta.getBlock();
 640     FlatCall fcall=(FlatCall)nodes.get(ppoint.getIndex());
 641     Graph graph=graphMap.get(fcall);
 642     Graph oldgraph=(ppoint.getIndex()==0)?
 643       bbgraphMap.get(bblock):
 644       graphMap.get(nodes.get(ppoint.getIndex()-1));
 645
 646     //Age outside nodes if necessary
 647     for(Iterator<AllocNode> nodeit=delta.addNodeAges.iterator();nodeit.hasNext();) {
 648       AllocNode node=nodeit.next();
 649       if (!graph.callNodeAges.contains(node)) {
 650         graph.callNodeAges.add(node);
 651       } else {
 652         nodeit.remove();
 653       }
 654       if (!graph.reachNode.contains(node)&&!node.isSummary()) {
 655         /* Need to age node in existing graph*/
 656         summarizeInGraph(graph, newDelta, node);
 657       }
 658     }
 659     //Add heap edges in
 660     for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.heapedgeadd.entrySet()) {
 661       for(Edge e:entry.getValue()) {
 662         boolean addedge=false;
 663         Edge edgetoadd=null;
 664         if (e.statuspredicate==Edge.NEW) {
 665           edgetoadd=e;
 666         } else {
 667           Edge origEdgeKey=e.makeStatus(allocFactory);
 668           if (oldgraph.nodeMap.containsKey(origEdgeKey.src)&&
 669               oldgraph.nodeMap.get(origEdgeKey.src).contains(origEdgeKey)) {
 670             Edge origEdge=oldgraph.nodeMap.get(origEdgeKey.src).get(origEdgeKey);
 671             //copy the predicate
 672             origEdgeKey.statuspredicate=origEdge.statuspredicate;
 673             edgetoadd=origEdgeKey;
 674           }
 675         }
 676         mergeEdge(graph, newDelta, edgetoadd);
 677       }
 678     }
 679     //Add external edges in
 680     for(Edge e:graph.externalEdgeSet) {
 681       //First did we age the source
 682       Edge newedge=e.copy();
 683       if (newedge.src!=null&&!e.src.isSummary()&&graph.callNodeAges.contains(e.src)) {
 684         AllocNode summaryNode=allocFactory.getAllocNode(newedge.src, true);
 685         newedge.src=summaryNode;
 686       }
 687       //Compute target
 688       if (graph.callNodeAges.contains(e.dst)&&!e.dst.isSummary()) {
 689         if (graph.callOldNodes.contains(e.dst)) {
 690           //Need two edges
 691           Edge copy=newedge.copy();
 692           mergeEdge(graph, newDelta, copy);
 693         }
 694         //Now add summarized node
 695         newedge.dst=allocFactory.getAllocNode(newedge.dst, true);
 696         mergeEdge(graph, newDelta, newedge);
 697       } else {
 698         //Add edge to single node
 699         mergeEdge(graph, newDelta, newedge);
 700       }
 701     }
 702     //Add edge for return value
 703     if (fcall.getReturnTemp()!=null) {
 704       MySet<Edge> returnedge=delta.varedgeadd.get(returntmp);
 705       if (returnedge!=null)
 706         for(Edge e:returnedge) {
 707           Edge newedge=e.copy();
 708           newedge.srcvar=fcall.getReturnTemp();
 709           if (graph.getEdges(fcall.getReturnTemp())==null||!graph.getEdges(fcall.getReturnTemp()).contains(newedge))
 710             newDelta.addEdge(newedge);
 711         }
 712     }
 713     applyDiffs(graph, newDelta);
 714     return newDelta;
 715   }
 716
 717   public void mergeEdge(Graph graph, Delta newDelta, Edge edgetoadd) {
 718     if (edgetoadd!=null) {
 719       Edge match=graph.getMatch(edgetoadd);
 720
 721       if (match==null||!match.subsumes(edgetoadd)) {
 722         Edge mergededge=edgetoadd.merge(match);
 723         newDelta.addEdge(mergededge);
 724       }
 725     }
 726   }
 727
 728
 729   /* Summarizes out of context nodes in graph */
 730   void summarizeInGraph(Graph graph, Delta newDelta, AllocNode singleNode) {
 731     AllocNode summaryNode=allocFactory.getAllocNode(singleNode, true);
 732
 733     //Handle outgoing heap edges
 734     MySet<Edge> edgeset=graph.getEdges(singleNode);
 735
 736     for(Edge e:edgeset) {
 737       Edge rewrite=e.rewrite(singleNode, summaryNode);
 738       //Remove old edge
 739       newDelta.removeHeapEdge(e);
 740       mergeEdge(graph, newDelta, rewrite);
 741     }
 742
 743     //Handle incoming edges
 744     MySet<Edge> backedges=graph.getBackEdges(singleNode);
 745     for(Edge e:backedges) {
 746       if (e.dst==singleNode) {
 747         //Need to get original edge so that predicate will be correct
 748         Edge match=graph.getMatch(e);
 749         Edge rewrite=match.rewrite(singleNode, summaryNode);
 750         newDelta.removeEdge(match);
 751         mergeEdge(graph, newDelta, rewrite);
 752       }
 753     }
 754   }
 755
 756   void applyDiffs(Graph graph, Delta delta) {
 757     applyDiffs(graph, delta, false);
 758   }
 759
 760   void applyDiffs(Graph graph, Delta delta, boolean genbackwards) {
 761     //build backwards map if requested
 762     if (genbackwards&&graph.backMap==null) {
 763       graph.backMap=new HashMap<AllocNode, MySet<Edge>>();
 764       if (graph.parent.backMap==null) {
 765         graph.parent.backMap=new HashMap<AllocNode, MySet<Edge>>();
 766         for(Map.Entry<AllocNode, MySet<Edge>> entry:graph.nodeMap.entrySet()) {
 767           for(Edge e:entry.getValue()) {
 768             if (!graph.parent.backMap.containsKey(e.dst))
 769               graph.parent.backMap.put(e.dst, new MySet<Edge>());
 770             graph.parent.backMap.get(e.dst).add(e);
 771           }
 772         }
 773         for(Map.Entry<TempDescriptor, MySet<Edge>> entry:graph.varMap.entrySet()) {
 774           for(Edge e:entry.getValue()) {
 775             if (!graph.parent.backMap.containsKey(e.dst))
 776               graph.parent.backMap.put(e.dst, new MySet<Edge>());
 777             graph.parent.backMap.get(e.dst).add(e);
 778           }
 779         }
 780       }
 781     }
 782
 783     //Add hidden base edges
 784     for(Map.Entry<AllocNode, MySet<Edge>> e: delta.baseheapedge.entrySet()) {
 785       AllocNode node=e.getKey();
 786       MySet<Edge> edges=e.getValue();
 787       if (graph.nodeMap.containsKey(node)) {
 788         MySet<Edge> nodeEdges=graph.nodeMap.get(node);
 789         nodeEdges.addAll(edges);
 790       }
 791     }
 792
 793     //Remove heap edges
 794     for(Map.Entry<AllocNode, MySet<Edge>> e: delta.heapedgeremove.entrySet()) {
 795       AllocNode node=e.getKey();
 796       MySet<Edge> edgestoremove=e.getValue();
 797       if (graph.nodeMap.containsKey(node)) {
 798         //Just apply diff to current map
 799         graph.nodeMap.get(node).removeAll(edgestoremove);
 800       } else {
 801         //Generate diff from parent graph
 802         MySet<Edge> parentedges=graph.parent.nodeMap.get(node);
 803         if (parentedges!=null) {
 804           MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
 805           graph.nodeMap.put(node, newedgeset);
 806         }
 807       }
 808     }
 809
 810     //Add heap edges
 811     for(Map.Entry<AllocNode, MySet<Edge>> e: delta.heapedgeadd.entrySet()) {
 812       AllocNode node=e.getKey();
 813       MySet<Edge> edgestoadd=e.getValue();
 814       //If we have not done a subtract, then
 815       if (!graph.nodeMap.containsKey(node)) {
 816         //Copy the parent entry
 817         if (graph.parent.nodeMap.containsKey(node))
 818           graph.nodeMap.put(node, (MySet<Edge>)graph.parent.nodeMap.get(node).clone());
 819         else
 820           graph.nodeMap.put(node, new MySet<Edge>());
 821       }
 822       graph.nodeMap.get(node).addAll(edgestoadd);
 823       if (genbackwards) {
 824         for(Edge eadd:edgestoadd) {
 825           if (!graph.backMap.containsKey(eadd.dst))
 826             graph.backMap.put(eadd.dst, new MySet<Edge>());
 827           graph.backMap.get(eadd.dst).add(eadd);
 828         }
 829       }
 830     }
 831
 832     //Remove var edges
 833     for(Map.Entry<TempDescriptor, MySet<Edge>> e: delta.varedgeremove.entrySet()) {
 834       TempDescriptor tmp=e.getKey();
 835       MySet<Edge> edgestoremove=e.getValue();
 836
 837       if (graph.varMap.containsKey(tmp)) {
 838         //Just apply diff to current map
 839         graph.varMap.get(tmp).removeAll(edgestoremove);
 840       } else if (graph.parent.varMap.containsKey(tmp)) {
 841         //Generate diff from parent graph
 842         MySet<Edge> parentedges=graph.parent.varMap.get(tmp);
 843         MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
 844         graph.varMap.put(tmp, newedgeset);
 845       }
 846     }
 847
 848     //Add var edges
 849     for(Map.Entry<TempDescriptor, MySet<Edge>> e: delta.varedgeadd.entrySet()) {
 850       TempDescriptor tmp=e.getKey();
 851       MySet<Edge> edgestoadd=e.getValue();
 852       graph.varMap.put(tmp, (MySet<Edge>) edgestoadd.clone());
 853       if (genbackwards) {
 854         for(Edge eadd:edgestoadd) {
 855           if (!graph.backMap.containsKey(eadd.dst))
 856             graph.backMap.put(eadd.dst, new MySet<Edge>());
 857           graph.backMap.get(eadd.dst).add(eadd);
 858         }
 859       }
 860     }
 861
 862     //Add node additions
 863     for(AllocNode node:delta.addNodeAges) {
 864       graph.nodeAges.add(node);
 865     }
 866
 867     for(Map.Entry<AllocNode, Boolean> nodeentry:delta.addOldNodes.entrySet()) {
 868       AllocNode node=nodeentry.getKey();
 869       Boolean ispresent=nodeentry.getValue();
 870       graph.oldNodes.put(node, ispresent);
 871     }
 872   }
 873
 874   Delta processSetFieldElementNode(FlatNode node, Delta delta, Graph graph) {
 875     TempDescriptor src;
 876     FieldDescriptor fd;
 877     TempDescriptor dst;
 878     if (node.kind()==FKind.FlatSetElementNode) {
 879       FlatSetElementNode fen=(FlatSetElementNode) node;
 880       src=fen.getSrc();
 881       fd=null;
 882       dst=fen.getDst();
 883     } else {
 884       FlatSetFieldNode ffn=(FlatSetFieldNode) node;
 885       src=ffn.getSrc();
 886       fd=ffn.getField();
 887       dst=ffn.getDst();
 888     }
 889     if (delta.getInit()) {
 890       HashSet<AllocNode> srcNodes=GraphManip.getNodes(graph, delta, src);
 891       HashSet<AllocNode> dstNodes=GraphManip.getNodes(graph, delta, dst);
 892       MySet<Edge> edgesToAdd=GraphManip.genEdges(dstNodes, fd, srcNodes);
 893       MySet<Edge> edgesToRemove=null;
 894       if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()&&fd!=null) {
 895         /* Can do a strong update */
 896         edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
 897         graph.strongUpdateSet=edgesToRemove;
 898       } else
 899         graph.strongUpdateSet=new MySet<Edge>();
 900       /* Update diff */
 901       updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
 902       applyDiffs(graph, delta);
 903     } else {
 904       /* First look at new sources */
 905       MySet<Edge> edgesToAdd=new MySet<Edge>();
 906       HashSet<AllocNode> newSrcNodes=GraphManip.getDiffNodes(delta, src);
 907       HashSet<AllocNode> srcNodes=GraphManip.getNodes(graph, delta, src);
 908       HashSet<AllocNode> dstNodes=GraphManip.getNodes(graph, delta, dst);
 909       HashSet<AllocNode> newDstNodes=GraphManip.getDiffNodes(delta, dst);
 910
 911
 912       MySet<Edge> edgesToRemove=null;
 913       if (newDstNodes.size()!=0) {
 914         if (dstNodes.size()>1&&!dstNodes.iterator().next().isSummary()&&fd!=null) {
 915           /* Need to undo strong update */
 916           if (graph.strongUpdateSet!=null) {
 917             edgesToAdd.addAll(graph.strongUpdateSet);
 918             graph.strongUpdateSet=null; //Prevent future strong updates
 919           }
 920         } else if (dstNodes.size()==1&&newDstNodes.size()==1&&!newDstNodes.iterator().next().isSummary()&&graph.strongUpdateSet!=null&&fd!=null) {
 921           edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
 922           graph.strongUpdateSet.addAll(edgesToRemove);
 923         }
 924         edgesToAdd.addAll(GraphManip.genEdges(newDstNodes, fd, srcNodes));
 925       }
 926
 927       //Kill new edges
 928       if (graph.strongUpdateSet!=null&&fd!=null) {
 929         MySet<Edge> otherEdgesToRemove=GraphManip.getDiffEdges(delta, dstNodes);
 930         if (edgesToRemove!=null)
 931           edgesToRemove.addAll(otherEdgesToRemove);
 932         else
 933           edgesToRemove=otherEdgesToRemove;
 934         graph.strongUpdateSet.addAll(otherEdgesToRemove);
 935       }
 936
 937       //Next look at new destinations
 938       edgesToAdd.addAll(GraphManip.genEdges(dstNodes, fd, newSrcNodes));
 939
 940       /* Update diff */
 941       updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
 942       applyDiffs(graph, delta);
 943     }
 944     return delta;
 945   }
 946
 947   Delta processCopyNode(FlatNode node, Delta delta, Graph graph) {
 948     TempDescriptor src;
 949     TempDescriptor dst;
 950     if (node.kind()==FKind.FlatOpNode) {
 951       FlatOpNode fon=(FlatOpNode) node;
 952       src=fon.getLeft();
 953       dst=fon.getDest();
 954     } else if (node.kind()==FKind.FlatReturnNode) {
 955       FlatReturnNode frn=(FlatReturnNode)node;
 956       src=frn.getReturnTemp();
 957       dst=returntmp;
 958       if (src==null||!src.getType().isPtr()) {
 959         //This is a NOP
 960         applyDiffs(graph, delta);
 961         return delta;
 962       }
 963     } else {
 964       FlatCastNode fcn=(FlatCastNode) node;
 965       src=fcn.getSrc();
 966       dst=fcn.getDst();
 967     }
 968     if (delta.getInit()) {
 969       HashSet<AllocNode> srcnodes=GraphManip.getNodes(graph, delta, src);
 970       MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, srcnodes);
 971       MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
 972       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
 973       applyDiffs(graph, delta);
 974     } else {
 975       /* First compute new src nodes */
 976       HashSet<AllocNode> newSrcNodes=GraphManip.getDiffNodes(delta, src);
 977
 978       /* Compute the union, and then the set of edges */
 979       MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, newSrcNodes);
 980
 981       /* Compute set of edges to remove */
 982       MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
 983
 984       /* Update diff */
 985       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
 986       applyDiffs(graph, delta);
 987     }
 988     return delta;
 989   }
 990
 991   Delta processFieldElementNode(FlatNode node, Delta delta, Graph graph) {
 992     TempDescriptor src;
 993     FieldDescriptor fd;
 994     TempDescriptor dst;
 995     if (node.kind()==FKind.FlatElementNode) {
 996       FlatElementNode fen=(FlatElementNode) node;
 997       src=fen.getSrc();
 998       fd=null;
 999       dst=fen.getDst();
1000     } else {
1001       FlatFieldNode ffn=(FlatFieldNode) node;
1002       src=ffn.getSrc();
1003       fd=ffn.getField();
1004       dst=ffn.getDst();
1005     }
1006     if (delta.getInit()) {
1007       HashSet<AllocNode> srcnodes=GraphManip.getNodes(graph, delta, src);
1008       HashSet<AllocNode> fdnodes=GraphManip.getNodes(graph, delta, srcnodes, fd);
1009       MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, fdnodes);
1010       MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
1011       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1012       applyDiffs(graph, delta);
1013     } else {
1014       /* First compute new objects we read fields of */
1015       HashSet<AllocNode> allsrcnodes=GraphManip.getNodes(graph, delta, src);
1016       HashSet<AllocNode> difffdnodes=GraphManip.getDiffNodes(delta, allsrcnodes, fd);
1017       /* Next compute new targets of fields */
1018       HashSet<AllocNode> newsrcnodes=GraphManip.getDiffNodes(delta, src);
1019       HashSet<AllocNode> newfdnodes=GraphManip.getNodes(graph, delta, newsrcnodes, fd);
1020       /* Compute the union, and then the set of edges */
1021       HashSet<AllocNode> newTargets=new HashSet<AllocNode>();
1022       newTargets.addAll(newfdnodes);
1023       newTargets.addAll(difffdnodes);
1024       MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, newTargets);
1025
1026       /* Compute set of edges to remove */
1027       MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
1028
1029       /* Update diff */
1030       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1031       applyDiffs(graph, delta);
1032     }
1033     return delta;
1034   }
1035
1036   static void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1037     MySet<Edge> edgeAdd=delta.varedgeadd.get(tmp);
1038     MySet<Edge> edgeRemove=delta.varedgeremove.get(tmp);
1039     MySet<Edge> existingEdges=graph.getEdges(tmp);
1040     for(Edge e: edgestoRemove) {
1041       //remove edge from delta
1042       if (edgeAdd!=null)
1043         edgeAdd.remove(e);
1044       //if the edge is already in the graph, add an explicit remove to the delta
1045       if (existingEdges.contains(e))
1046         delta.removeVarEdge(e);
1047     }
1048     for(Edge e: edgestoAdd) {
1049       //Remove the edge from the remove set
1050       if (edgeRemove!=null)
1051         edgeRemove.remove(e);
1052       //Explicitly add it to the add set unless it is already in the graph
1053       if (!existingEdges.contains(e))
1054         delta.addVarEdge(e);
1055     }
1056   }
1057
1058   static void updateHeapDelta(Graph graph, Delta delta, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1059     if (edgestoRemove!=null)
1060       for(Edge e: edgestoRemove) {
1061         AllocNode src=e.src;
1062         MySet<Edge> edgeAdd=delta.heapedgeadd.get(src);
1063         MySet<Edge> existingEdges=graph.getEdges(src);
1064         //remove edge from delta
1065         edgeAdd.remove(e);
1066         //if the edge is already in the graph, add an explicit remove to the delta
1067         if (existingEdges.contains(e)) {
1068           delta.removeHeapEdge(e);
1069         }
1070       }
1071     if (edgestoAdd!=null)
1072       for(Edge e: edgestoAdd) {
1073         AllocNode src=e.src;
1074         MySet<Edge> edgeRemove=delta.heapedgeremove.get(src);
1075         MySet<Edge> existingEdges=graph.getEdges(src);
1076         //Remove the edge from the remove set
1077         if (edgeRemove!=null)
1078           edgeRemove.remove(e);
1079         //Explicitly add it to the add set unless it is already in the graph
1080         if (!existingEdges.contains(e)||!existingEdges.get(e).isNew()) {
1081           delta.addHeapEdge(e);
1082         }
1083       }
1084   }
1085
1086   Delta processFlatNop(FlatNode node, Delta delta, Graph graph) {
1087     applyDiffs(graph, delta);
1088     return delta;
1089   }
1090
1091   Delta processNewNode(FlatNew node, Delta delta, Graph graph) {
1092     AllocNode summary=allocFactory.getAllocNode(node, true);
1093     AllocNode single=allocFactory.getAllocNode(node, false);
1094     TempDescriptor tmp=node.getDst();
1095
1096     if (delta.getInit()) {
1097       /* We don't have to deal with summarization here...  The
1098        * intuition is that this is the only place where we generate
1099        * nodes for this allocation site and this is the first time
1100        * we've analyzed this site */
1101
1102       //Build new Edge
1103       Edge e=new Edge(tmp, single);
1104       //Build new Edge set
1105       MySet<Edge> newedges=new MySet<Edge>();
1106       newedges.add(e);
1107       //Add it into the diffs
1108       delta.varedgeadd.put(tmp, newedges);
1109       //Remove the old edges
1110       delta.varedgeremove.put(tmp, (MySet<Edge>) graph.getEdges(tmp).clone());
1111       //Apply incoming diffs to graph
1112       applyDiffs(graph, delta);
1113       //Note that we create a single node
1114       delta.addNodeAges.add(single);
1115       //Kill the old node
1116       if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1117         delta.addOldNodes.put(single, Boolean.FALSE);
1118       }
1119     } else {
1120       /* 1. Fix up the variable edge additions */
1121
1122       for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.varedgeadd.entrySet().iterator();entryIt.hasNext();) {
1123         Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1124
1125         if (entry.getKey()==tmp) {
1126           /* Check if this is the tmp we overwrite */
1127           entryIt.remove();
1128         } else {
1129           /* Otherwise, check if the target of the edge is changed... */
1130           summarizeSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary);
1131         }
1132       }
1133
1134       /* 2. Fix up the base variable edges */
1135
1136       for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.basevaredge.entrySet().iterator();entryIt.hasNext();) {
1137         Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1138         TempDescriptor entrytmp=entry.getKey();
1139         if (entrytmp==tmp) {
1140           /* Check is this is the tmp we overwrite, if so add to remove set */
1141           Util.relationUpdate(delta.varedgeremove, tmp, null, entry.getValue());
1142         } else {
1143           /* Check if the target of the edge is changed */
1144           MySet<Edge> newset=(MySet<Edge>)entry.getValue().clone();
1145           MySet<Edge> removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary);
1146           Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset);
1147           Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset);
1148         }
1149       }
1150
1151
1152       /* 3. Fix up heap edge additions */
1153
1154       HashMap<AllocNode, MySet<Edge>> addheapedge=new HashMap<AllocNode, MySet<Edge>>();
1155       for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.heapedgeadd.entrySet().iterator();entryIt.hasNext();) {
1156         Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1157         MySet<Edge> edgeset=entry.getValue();
1158         AllocNode allocnode=entry.getKey();
1159         if (allocnode==single) {
1160           entryIt.remove();
1161           summarizeSet(edgeset, graph.nodeMap.get(summary), single, summary);
1162           addheapedge.put(summary, edgeset);
1163         } else {
1164           summarizeSet(edgeset, graph.nodeMap.get(allocnode), single, summary);
1165         }
1166       }
1167
1168       /* Merge in diffs */
1169
1170       for(Map.Entry<AllocNode, MySet<Edge>> entry:addheapedge.entrySet()) {
1171         AllocNode allocnode=entry.getKey();
1172         Util.relationUpdate(delta.heapedgeadd, allocnode, null, entry.getValue());
1173       }
1174
1175       /* 4. Fix up the base heap edges */
1176
1177       for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.baseheapedge.entrySet().iterator();entryIt.hasNext();) {
1178         Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1179         MySet<Edge> edgeset=entry.getValue();
1180         AllocNode allocnode=entry.getKey();
1181         if (allocnode==single) {
1182           entryIt.remove();
1183         }
1184         AllocNode addnode=(allocnode==single)?summary:allocnode;
1185
1186         MySet<Edge> newset=(MySet<Edge>) edgeset.clone();
1187         MySet<Edge> removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary);
1188         Util.relationUpdate(delta.heapedgeadd, addnode, null, newset);
1189         Util.relationUpdate(delta.heapedgeremove, allocnode, null, removeset);
1190       }
1191
1192       /* Update Node Ages...If the base or addNodeAges set contains a
1193        * single node, it now should also contain a summary node...  No
1194        * need to generate a single node as that has already been
1195        * done. */
1196       if (delta.baseNodeAges.contains(single)||delta.addNodeAges.contains(single)) {
1197         delta.addNodeAges.add(summary);
1198       }
1199
1200       //Kill the old node if someone tries to add it
1201       if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1202         delta.addOldNodes.put(single, Boolean.FALSE);
1203       }
1204
1205       //Apply incoming diffs to graph
1206       applyDiffs(graph, delta);
1207     }
1208     return delta;
1209   }
1210
1211   /* This function builds a new edge set where oldnode is summarized into new node */
1212
1213   void summarizeSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode sumnode) {
1214     MySet<Edge> newSet=null;
1215     for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
1216       Edge e=edgeit.next();
1217       if (e.dst==oldnode||e.src==oldnode) {
1218         if (newSet==null) {
1219           newSet=new MySet<Edge>();
1220         }
1221         edgeit.remove();
1222         e=e.copy();
1223
1224         if (e.dst==oldnode) {
1225           e.dst=sumnode;
1226         }
1227         if (e.src==oldnode) {
1228           e.src=sumnode;
1229         }
1230         if (oldedgeset==null||!oldedgeset.contains(e))
1231           newSet.add(e);
1232       }
1233     }
1234     if (newSet!=null)
1235       edgeset.addAll(newSet);
1236   }
1237
1238   /* Shrinks the incoming set to just include rewritten values.
1239    * Returns a set of the original rewritten values */
1240
1241   MySet<Edge> shrinkSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode newnode) {
1242     MySet<Edge> newSet=null;
1243     MySet<Edge> removeSet=null;
1244     for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
1245       Edge e=edgeit.next();
1246       edgeit.remove();
1247       if (e.dst==oldnode||e.src==oldnode) {
1248         if (newSet==null) {
1249           newSet=new MySet<Edge>();
1250           removeSet=new MySet<Edge>();
1251         }
1252
1253         removeSet.add(e);
1254         e=e.copy();
1255         if (e.dst==oldnode)
1256           e.dst=newnode;
1257         if (e.src==oldnode)
1258           e.src=newnode;
1259         if (oldedgeset==null||!oldedgeset.contains(e))
1260           newSet.add(e);
1261       }
1262     }
1263     if (newSet!=null)
1264       edgeset.addAll(newSet);
1265     return removeSet;
1266   }
1267
1268   /* This function returns a completely new Delta...  It is safe to
1269    * modify this */
1270
1271   Delta applyInitDelta(Delta delta, BBlock block) {
1272     //Apply delta to graph
1273     boolean newGraph=false;
1274     if (!bbgraphMap.containsKey(block)) {
1275       bbgraphMap.put(block, new Graph(null));
1276       newGraph=true;
1277     }
1278     Delta newdelta;
1279     Graph graph=bbgraphMap.get(block);
1280
1281     if (newGraph) {
1282       newdelta=new Delta(null, true);
1283       //Add in heap edges and throw away original diff
1284       graph.nodeMap.putAll(delta.heapedgeadd);
1285       //Add in var edges and throw away original diff
1286       graph.varMap.putAll(delta.varedgeadd);
1287       //Record that this is initial set...
1288       graph.nodeAges.addAll(delta.addNodeAges);
1289       //Add old nodes
1290       for(Map.Entry<AllocNode, Boolean> oldentry:delta.addOldNodes.entrySet()) {
1291         if (oldentry.getValue().booleanValue()) {
1292           graph.oldNodes.put(oldentry.getKey(), Boolean.TRUE);
1293         }
1294       }
1295     } else {
1296       newdelta=new Delta(null, false);
1297       //merge in heap edges and variables
1298       mergeHeapEdges(graph, delta, newdelta);
1299       mergeVarEdges(graph, delta, newdelta);
1300       mergeAges(graph, delta, newdelta);
1301     }
1302
1303     return newdelta;
1304   }
1305
1306   /* This function merges in the heap edges.  It updates delta to be
1307    * the difference */
1308
1309   void mergeHeapEdges(Graph graph, Delta delta, Delta newdelta) {
1310     //Merge in edges
1311     for(Map.Entry<AllocNode, MySet<Edge>> heapedge:delta.heapedgeadd.entrySet()) {
1312       AllocNode nsrc=heapedge.getKey();
1313       MySet<Edge> edges=heapedge.getValue();
1314
1315       if (graph.backMap!=null) {
1316         for(Edge e:edges) {
1317           if (!graph.backMap.containsKey(e.dst))
1318             graph.backMap.put(e.dst, new MySet<Edge>());
1319           graph.backMap.get(e.dst).add(e);
1320         }
1321       }
1322
1323       if (!graph.nodeMap.containsKey(nsrc)) {
1324         graph.nodeMap.put(nsrc, new MySet<Edge>());
1325       }
1326       MySet<Edge> dstedges=graph.nodeMap.get(nsrc);
1327       MySet<Edge> diffedges=new MySet<Edge>();
1328       for(Edge e:edges) {
1329         if (!dstedges.contains(e)) {
1330           //We have a new edge
1331           diffedges.add(e);
1332           dstedges.add(e);
1333         } else {
1334           Edge origedge=dstedges.get(e);
1335           if (!origedge.subsumes(e)) {
1336             Edge mergededge=origedge.merge(e);
1337             diffedges.add(mergededge);
1338             dstedges.add(mergededge);
1339           }
1340         }
1341       }
1342       //Done with edge set...
1343       if (diffedges.size()>0) {
1344         //completely new
1345         newdelta.baseheapedge.put(nsrc, diffedges);
1346       }
1347     }
1348   }
1349
1350   /* This function merges in the var edges.  It updates delta to be
1351    * the difference */
1352
1353   void mergeVarEdges(Graph graph, Delta delta, Delta newdelta) {
1354     //Merge in edges
1355     for(Map.Entry<TempDescriptor, MySet<Edge>> varedge:delta.varedgeadd.entrySet()) {
1356       TempDescriptor tmpsrc=varedge.getKey();
1357       MySet<Edge> edges=varedge.getValue();
1358       if (graph.backMap!=null) {
1359         for(Edge e:edges) {
1360           if (!graph.backMap.containsKey(e.dst))
1361             graph.backMap.put(e.dst, new MySet<Edge>());
1362           graph.backMap.get(e.dst).add(e);
1363         }
1364       }
1365
1366       if (!graph.varMap.containsKey(tmpsrc)) {
1367         graph.varMap.put(tmpsrc, new MySet<Edge>());
1368       }
1369       MySet<Edge> dstedges=graph.varMap.get(tmpsrc);
1370       MySet<Edge> diffedges=new MySet<Edge>();
1371       for(Edge e:edges) {
1372         if (!dstedges.contains(e)) {
1373           //We have a new edge
1374           diffedges.add(e);
1375           dstedges.add(e);
1376         }
1377       }
1378       //Done with edge set...
1379       if (diffedges.size()>0) {
1380         //completely new
1381         newdelta.basevaredge.put(tmpsrc,diffedges);
1382       }
1383     }
1384   }
1385
1386   void mergeAges(Graph graph, Delta delta, Delta newDelta) {
1387     //Merge in edges
1388     for(AllocNode node:delta.addNodeAges) {
1389       if (!graph.nodeAges.contains(node)) {
1390         graph.nodeAges.add(node);
1391         newDelta.baseNodeAges.add(node);
1392       }
1393     }
1394     for(Map.Entry<AllocNode, Boolean> oldentry:delta.addOldNodes.entrySet()) {
1395       AllocNode node=oldentry.getKey();
1396       boolean ispresent=oldentry.getValue().booleanValue();
1397       if (ispresent&&!graph.oldNodes.containsKey(node)) {
1398         graph.oldNodes.put(node, Boolean.TRUE);
1399         newDelta.baseOldNodes.put(node, Boolean.TRUE);
1400       }
1401     }
1402   }
1403 }