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