Robust/src/Analysis/Pointer/Pointer.java

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