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
   8 public class Pointer {
   9   HashMap<FlatMethod, BasicBlock> blockMap;
  10   HashMap<BBlock, Graph> bbgraphMap;
  11   HashMap<FlatNode, Graph> graphMap;
  12   State state;
  13   TypeUtil typeUtil;
  14   AllocFactory allocFactory;
  15   LinkedList<Delta> toprocess;
  16
  17   public Pointer(State state, TypeUtil typeUtil) {
  18     this.state=state;
  19     this.blockMap=new HashMap<FlatMethod, BasicBlock>();
  20     this.bbgraphMap=new HashMap<BBlock, Graph>();
  21     this.graphMap=new HashMap<FlatNode, Graph>();
  22     this.typeUtil=typeUtil;
  23     this.allocFactory=new AllocFactory(state, typeUtil);
  24     this.toprocess=new LinkedList<Delta>();
  25   }
  26
  27   public BasicBlock getBBlock(FlatMethod fm) {
  28     if (!blockMap.containsKey(fm))
  29       blockMap.put(fm, BasicBlock.getBBlock(fm));
  30     return blockMap.get(fm);
  31   }
  32
  33   Delta buildInitialContext() {
  34     MethodDescriptor md=typeUtil.getMain();
  35     FlatMethod fm=state.getMethodFlat(md);
  36     BasicBlock bb=getBBlock(fm);
  37     BBlock start=bb.getStart();
  38     Delta delta=new Delta(start, true);
  39     HashSet<Edge> arrayset=new HashSet<Edge>();
  40     HashSet<Edge> varset=new HashSet<Edge>();
  41     arrayset.add(new Edge(allocFactory.StringArray, null, allocFactory.Strings));
  42     varset.add(new Edge(fm.getParameter(0), allocFactory.StringArray));
  43     delta.heapedgeadd.put(allocFactory.StringArray, arrayset);
  44     delta.varedgeadd.put(fm.getParameter(0), varset);
  45     return delta;
  46   }
  47
  48   void doAnalysis() {
  49     toprocess.add(buildInitialContext());
  50
  51     while(!toprocess.isEmpty()) {
  52       Delta delta=toprocess.remove();
  53       BBlock bblock=delta.getBlock();
  54       Vector<FlatNode> nodes=bblock.nodes();
  55
  56       //Build base graph for entrance to this basic block
  57       delta=applyInitDelta(delta, bblock);
  58       Graph graph=bbgraphMap.get(bblock);
  59
  60       //Compute delta at exit of each node
  61       for(int i=0; i<nodes.size();i++) {
  62         FlatNode currNode=nodes.get(i);
  63         if (!graphMap.containsKey(currNode)) {
  64           graphMap.put(currNode, new Graph(graph));
  65         }
  66         Graph nodeGraph=graphMap.get(currNode);
  67         delta=processNode(currNode, delta, nodeGraph);
  68       }
  69       generateFinalDelta(nodeGraph, delta)
  70     }
  71   }
  72
  73   void generateFinalDelta(Delta delta, Graph graph) {
  74     Delta newDelta=new Delta(null, false);
  75     if (delta.isInit()) {
  76       //First compute the set of temps
  77       HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
  78       tmpSet.addAll(graph.varMap.keySet());
  79       tmpSet.addAll(graph.parent.varMap.keySet());
  80
  81       //Next build the temp map part of the delta
  82       for(tmp:tmpSet) {
  83         HashSet<Edge> edgeSet=new HashSet<Edge>();
  84         /* Get target set */
  85         if (graph.varMap.containsKey(tmp))
  86           edgeSet.addAll(graph.varMap.get(tmp));
  87         else
  88           edgeSet.addAll(graph.parent.varMap.get(tmp));
  89         newdelta.varedgeadd.put(tmp, edgeset);
  90       }
  91
  92       //Next compute the set of src allocnodes
  93       HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
  94       nodeSet.addAll(graph.nodeMap.keySet());
  95       nodeSet.addAll(graph.parent.nodeMap.keySet());
  96
  97       for(node:nodeSet) {
  98         HashSet<Edge> edgeSet=new HashSet<Edge>();
  99         /* Get edge set */
 100         if (graph.nodeMap.containsKey(node))
 101           edgeSet.addAll(graph.nodeMap.get(node));
 102         else
 103           edgeSet.addAll(graph.parent.nodeMap.get(node));
 104         newdelta.heapedgeadd.put(node, edgeset);
 105       }
 106     } else {
 107
 108
 109     }
 110   }
 111
 112   Delta processNode(FlatNode node, Delta delta, Graph newgraph) {
 113     switch(node.kind()) {
 114     case FKind.FlatNew:
 115       return processNewNode((FlatNew)node, delta, newgraph);
 116     case FKind.FlatFieldNode:
 117     case FKind.FlatElementNode:
 118       return processFieldElementNode(node, delta, newgraph);
 119     case FKind.FlatCastNode:
 120     case FKind.FlatOpNode:
 121       return processCopyNode(node, delta, newgraph);
 122     case FKind.FlatSetFieldNode:
 123     case FKind.FlatSetElementNode:
 124       return processSetFieldElementNode(node, delta, newgraph);
 125     case FKind.FlatMethod:
 126     case FKind.FlatCall:
 127     case FKind.FlatReturnNode:
 128     case FKind.FlatExit:
 129
 130     case FKind.FlatSESEEnterNode:
 131     case FKind.FlatSESEExitNode:
 132       throw new Error("Unimplemented node:"+node);
 133     default:
 134       throw new Error("Unrecognized node:"+node);
 135     }
 136   }
 137
 138   void applyDiffs(Graph graph, Delta delta) {
 139     //Add hidden base edges
 140     for(Map.Entry<AllocNode, HashSet<Edge>> e: delta.baseheapedge.entrySet()) {
 141       AllocNode node=e.getKey();
 142       HashSet<Edge> edges=e.getValue();
 143       if (graph.nodeMap.containsKey(node)) {
 144         HashSet<Edge> nodeEdges=graph.nodeMap.get(node);
 145         nodeEdges.addAll(edges);
 146       }
 147     }
 148
 149     //Remove heap edges
 150     for(Map.Entry<AllocNode, HashSet<Edge>> e: delta.heapedgeremove.entrySet()) {
 151       AllocNode node=e.getKey();
 152       HashSet<Edge> edgestoremove=e.getValue();
 153       if (graph.nodeMap.containsKey(node)) {
 154         //Just apply diff to current map
 155         graph.nodeMap.get(node).removeAll(edgestoremove);
 156       } else {
 157         //Generate diff from parent graph
 158         HashSet<Edge> parentedges=graph.parent.nodeMap.get(node);
 159         HashSet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
 160         graph.nodeMap.put(node, newedgeset);
 161       }
 162     }
 163
 164     //Add heap edges
 165     for(Map.Entry<AllocNode, HashSet<Edge>> e: delta.heapedgeadd.entrySet()) {
 166       AllocNode node=e.getKey();
 167       HashSet<Edge> edgestoadd=e.getValue();
 168       //If we have not done a subtract, then
 169       if (!graph.nodeMap.containsKey(node)) {
 170         //Copy the parent entry
 171         graph.nodeMap.put(node, (HashSet<Edge>)graph.parent.nodeMap.get(node).clone());
 172       }
 173       graph.nodeMap.get(node).addAll(edgestoadd);
 174     }
 175
 176     //Remove var edges
 177     for(Map.Entry<TempDescriptor, HashSet<Edge>> e: delta.varedgeremove.entrySet()) {
 178       TempDescriptor tmp=e.getKey();
 179       HashSet<Edge> edgestoremove=e.getValue();
 180
 181       if (graph.varMap.containsKey(tmp)) {
 182         //Just apply diff to current map
 183         graph.varMap.get(tmp).removeAll(edgestoremove);
 184       } else {
 185         //Generate diff from parent graph
 186         HashSet<Edge> parentedges=graph.parent.varMap.get(tmp);
 187         HashSet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
 188         graph.varMap.put(tmp, newedgeset);
 189       }
 190     }
 191
 192     //Add var edges
 193     for(Map.Entry<TempDescriptor, HashSet<Edge>> e: delta.varedgeadd.entrySet()) {
 194       TempDescriptor tmp=e.getKey();
 195       HashSet<Edge> edgestoadd=e.getValue();
 196       graph.varMap.put(tmp, (HashSet<Edge>) edgestoadd.clone());
 197     }
 198   }
 199
 200   Delta processSetFieldElementNode(FlatNode node, Delta delta, Graph graph) {
 201     TempDescriptor src;
 202     FieldDescriptor fd;
 203     TempDescriptor dst;
 204     if (node.kind()==FKind.FlatSetElementNode) {
 205       FlatSetElementNode fen=(FlatSetElementNode) node;
 206       src=fen.getSrc();
 207       fd=null;
 208       dst=fen.getDst();
 209     } else {
 210       FlatSetFieldNode ffn=(FlatSetFieldNode) node;
 211       src=ffn.getSrc();
 212       fd=ffn.getField();
 213       dst=ffn.getDst();
 214     }
 215     if (delta.getInit()) {
 216       HashSet<AllocNode> srcNodes=GraphManip.getNodes(graph, delta, src);
 217       HashSet<AllocNode> dstNodes=GraphManip.getNodes(graph, delta, dst);
 218       HashSet<Edge> edgesToAdd=GraphManip.genEdges(srcNodes, fd, dstNodes);
 219       HashSet<Edge> edgesToRemove=null;
 220       if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()) {
 221         /* Can do a strong update */
 222         edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
 223       }
 224       /* Update diff */
 225       updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
 226       applyDiffs(graph, delta);
 227     } else {
 228       /* First look at new sources */
 229       HashSet<Edge> edgesToAdd=new HashSet<Edge>();
 230       HashSet<AllocNode> newSrcNodes=GraphManip.getDiffNodes(delta, src);
 231       HashSet<AllocNode> dstNodes=GraphManip.getDiffNodes(delta, dst);
 232       edgesToAdd.addAll(GraphManip.genEdges(newSrcNodes, fd, dstNodes));
 233       HashSet<AllocNode> newDstNodes=GraphManip.getDiffNodes(delta, dst);
 234       HashSet<Edge> edgesToRemove=null;
 235       if (newDstNodes.size()!=0) {
 236         if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()) {
 237           /* Need to undo strong update */
 238           if (graph.strongUpdateSet!=null) {
 239             edgesToAdd.addAll(graph.strongUpdateSet);
 240             graph.strongUpdateSet.clear();
 241           }
 242         } else if (dstNodes.size()==0&&newDstNodes.size()==1&&!newDstNodes.iterator().next().isSummary()&&graph.strongUpdateSet==null) {
 243           edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
 244         }
 245         HashSet<AllocNode> srcNodes=GraphManip.getDiffNodes(delta, src);
 246         edgesToAdd.addAll(GraphManip.genEdges(srcNodes, fd, newDstNodes));
 247       }
 248       /* Update diff */
 249       updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
 250       applyDiffs(graph, delta);
 251     }
 252     return delta;
 253   }
 254
 255   Delta processCopyNode(FlatNode node, Delta delta, Graph graph) {
 256     TempDescriptor src;
 257     TempDescriptor dst;
 258     if (node.kind()==FKind.FlatOpNode) {
 259       FlatOpNode fon=(FlatOpNode) node;
 260       src=fon.getLeft();
 261       dst=fon.getDest();
 262     } else {
 263       FlatCastNode fcn=(FlatCastNode) node;
 264       src=fcn.getSrc();
 265       dst=fcn.getDst();
 266     }
 267     if (delta.getInit()) {
 268       HashSet<AllocNode> srcnodes=GraphManip.getNodes(graph, delta, src);
 269       HashSet<Edge> edgesToAdd=GraphManip.genEdges(src, srcnodes);
 270       HashSet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
 271       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
 272       applyDiffs(graph, delta);
 273     } else {
 274       /* First compute new src nodes */
 275       HashSet<AllocNode> newSrcNodes=GraphManip.getDiffNodes(delta, src);
 276
 277       /* Compute the union, and then the set of edges */
 278       HashSet<Edge> edgesToAdd=GraphManip.genEdges(src, newSrcNodes);
 279
 280       /* Compute set of edges to remove */
 281       HashSet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
 282
 283       /* Update diff */
 284       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
 285       applyDiffs(graph, delta);
 286     }
 287     return delta;
 288   }
 289
 290   Delta processFieldElementNode(FlatNode node, Delta delta, Graph graph) {
 291     TempDescriptor src;
 292     FieldDescriptor fd;
 293     TempDescriptor dst;
 294     if (node.kind()==FKind.FlatElementNode) {
 295       FlatElementNode fen=(FlatElementNode) node;
 296       src=fen.getSrc();
 297       fd=null;
 298       dst=fen.getDst();
 299     } else {
 300       FlatFieldNode ffn=(FlatFieldNode) node;
 301       src=ffn.getSrc();
 302       fd=ffn.getField();
 303       dst=ffn.getDst();
 304     }
 305     if (delta.getInit()) {
 306       HashSet<AllocNode> srcnodes=GraphManip.getNodes(graph, delta, src);
 307       HashSet<AllocNode> fdnodes=GraphManip.getNodes(graph, delta, srcnodes, fd);
 308       HashSet<Edge> edgesToAdd=GraphManip.genEdges(src, fdnodes);
 309       HashSet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
 310       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
 311       applyDiffs(graph, delta);
 312     } else {
 313       /* First compute new objects we read fields of */
 314       HashSet<AllocNode> allsrcnodes=GraphManip.getNodes(graph, delta, src);
 315       HashSet<AllocNode> difffdnodes=GraphManip.getDiffNodes(delta, allsrcnodes, fd);
 316       /* Next compute new targets of fields */
 317       HashSet<AllocNode> newsrcnodes=GraphManip.getDiffNodes(delta, src);
 318       HashSet<AllocNode> newfdnodes=GraphManip.getNodes(graph, delta, newsrcnodes, fd);
 319       /* Compute the union, and then the set of edges */
 320       HashSet<AllocNode> newTargets=new HashSet<AllocNode>();
 321       newTargets.addAll(newfdnodes);
 322       newTargets.addAll(difffdnodes);
 323       HashSet<Edge> edgesToAdd=GraphManip.genEdges(src, newTargets);
 324
 325       /* Compute set of edges to remove */
 326       HashSet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
 327
 328       /* Update diff */
 329       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
 330       applyDiffs(graph, delta);
 331     }
 332     return delta;
 333   }
 334
 335   static void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, HashSet<Edge> edgestoAdd, HashSet<Edge> edgestoRemove) {
 336     HashSet<Edge> edgeAdd=delta.varedgeadd.get(tmp);
 337     HashSet<Edge> edgeRemove=delta.varedgeremove.get(tmp);
 338     HashSet<Edge> existingEdges=graph.getEdges(tmp);
 339     for(Edge e: edgestoRemove) {
 340       //remove edge from delta
 341       edgeAdd.remove(e);
 342       //if the edge is already in the graph, add an explicit remove to the delta
 343       if (existingEdges.contains(e))
 344         edgeRemove.add(e);
 345     }
 346     for(Edge e: edgestoAdd) {
 347       //Remove the edge from the remove set
 348       edgeRemove.remove(e);
 349       //Explicitly add it to the add set unless it is already in the graph
 350       if (!existingEdges.contains(e))
 351         edgeAdd.add(e);
 352     }
 353   }
 354
 355   static void updateHeapDelta(Graph graph, Delta delta, HashSet<Edge> edgestoAdd, HashSet<Edge> edgestoRemove) {
 356     for(Edge e: edgestoRemove) {
 357       AllocNode src=e.src;
 358       HashSet<Edge> edgeAdd=delta.heapedgeadd.get(src);
 359       HashSet<Edge> existingEdges=graph.getEdges(src);
 360       //remove edge from delta
 361       edgeAdd.remove(e);
 362       //if the edge is already in the graph, add an explicit remove to the delta
 363       if (existingEdges.contains(e)) {
 364         HashSet<Edge> edgeRemove=delta.heapedgeremove.get(src);
 365         edgeRemove.add(e);
 366       }
 367     }
 368     for(Edge e: edgestoAdd) {
 369       AllocNode src=e.src;
 370       HashSet<Edge> edgeRemove=delta.heapedgeremove.get(src);
 371       HashSet<Edge> existingEdges=graph.getEdges(src);
 372       //Remove the edge from the remove set
 373       edgeRemove.remove(e);
 374       //Explicitly add it to the add set unless it is already in the graph
 375       if (!existingEdges.contains(e)) {
 376         HashSet<Edge> edgeAdd=delta.heapedgeadd.get(src);
 377         edgeAdd.add(e);
 378       }
 379     }
 380   }
 381
 382   Delta processNewNode(FlatNew node, Delta delta, Graph graph) {
 383     AllocNode summary=allocFactory.getAllocNode(node, true);
 384     AllocNode single=allocFactory.getAllocNode(node, false);
 385     TempDescriptor tmp=node.getDst();
 386
 387     if (delta.getInit()) {
 388       //Build new Edge
 389       Edge e=new Edge(tmp, single);
 390       //Build new Edge set
 391       HashSet<Edge> newedges=new HashSet<Edge>();
 392       newedges.add(e);
 393       //Add it into the diffs
 394       delta.varedgeadd.put(tmp, newedges);
 395       //Remove the old edges
 396       delta.varedgeremove.put(tmp, graph.getEdges(tmp));
 397       //Apply incoming diffs to graph
 398       applyDiffs(graph, delta);
 399     } else {
 400       /* 1. Fix up the variable edge additions */
 401
 402       for(Iterator<Map.Entry<TempDescriptor, HashSet<Edge>>> entryIt=delta.varedgeadd.entrySet().iterator();entryIt.hasNext();) {
 403         Map.Entry<TempDescriptor, HashSet<Edge>> entry=entryIt.next();
 404
 405         if (entry.getKey()==tmp) {
 406           /* Check if this is the tmp we overwrite */
 407           entryIt.remove();
 408         } else {
 409           /* Otherwise, check if the target of the edge is changed... */
 410           rewriteSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary);
 411         }
 412       }
 413
 414       /* 2. Fix up the base variable edges */
 415
 416       for(Iterator<Map.Entry<TempDescriptor, HashSet<Edge>>> entryIt=delta.basevaredge.entrySet().iterator();entryIt.hasNext();) {
 417         Map.Entry<TempDescriptor, HashSet<Edge>> entry=entryIt.next();
 418         TempDescriptor entrytmp=entry.getKey();
 419         if (entrytmp==tmp) {
 420           /* Check is this is the tmp we overwrite, if so add to remove set */
 421           Util.relationUpdate(delta.varedgeremove, tmp, null, entry.getValue());
 422         } else {
 423           /* Check if the target of the edge is changed */
 424           HashSet<Edge> newset=(HashSet<Edge>)entry.getValue().clone();
 425           HashSet<Edge> removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary);
 426           Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset);
 427           Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset);
 428         }
 429       }
 430
 431
 432       /* 3. Fix up heap edge additions */
 433
 434       HashMap<AllocNode, HashSet<Edge>> addheapedge=new HashMap<AllocNode, HashSet<Edge>>();
 435       for(Iterator<Map.Entry<AllocNode, HashSet<Edge>>> entryIt=delta.heapedgeadd.entrySet().iterator();entryIt.hasNext();) {
 436         Map.Entry<AllocNode, HashSet<Edge>> entry=entryIt.next();
 437         HashSet<Edge> edgeset=entry.getValue();
 438         AllocNode allocnode=entry.getKey();
 439         if (allocnode==single) {
 440           entryIt.remove();
 441           rewriteSet(edgeset, graph.nodeMap.get(summary), single, summary);
 442           addheapedge.put(summary, edgeset);
 443         } else {
 444           rewriteSet(edgeset, graph.nodeMap.get(allocnode), single, summary);
 445         }
 446       }
 447
 448       /* Merge in diffs */
 449
 450       for(Map.Entry<AllocNode, HashSet<Edge>> entry:addheapedge.entrySet()) {
 451         AllocNode allocnode=entry.getKey();
 452         Util.relationUpdate(delta.heapedgeadd, allocnode, null, entry.getValue());
 453       }
 454
 455       /* 4. Fix up the base heap edges */
 456
 457       for(Iterator<Map.Entry<AllocNode, HashSet<Edge>>> entryIt=delta.baseheapedge.entrySet().iterator();entryIt.hasNext();) {
 458         Map.Entry<AllocNode, HashSet<Edge>> entry=entryIt.next();
 459         HashSet<Edge> edgeset=entry.getValue();
 460         AllocNode allocnode=entry.getKey();
 461         if (allocnode==single) {
 462           entryIt.remove();
 463         }
 464         AllocNode addnode=(allocnode==single)?summary:allocnode;
 465
 466         HashSet<Edge> newset=(HashSet<Edge>) edgeset.clone();
 467         HashSet<Edge> removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary);
 468         Util.relationUpdate(delta.heapedgeadd, addnode, null, newset);
 469         Util.relationUpdate(delta.heapedgeremove, allocnode, null, removeset);
 470       }
 471
 472       //Apply incoming diffs to graph
 473       applyDiffs(graph, delta);
 474     }
 475     return delta;
 476   }
 477
 478   void rewriteSet(HashSet<Edge> edgeset, HashSet<Edge> oldedgeset, AllocNode oldnode, AllocNode newnode) {
 479     HashSet<Edge> newSet=null;
 480     for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
 481       Edge e=edgeit.next();
 482       if (e.dst==oldnode||e.src==oldnode) {
 483         if (newSet==null) {
 484           newSet=new HashSet<Edge>();
 485         }
 486         edgeit.remove();
 487         if (e.dst==oldnode)
 488           e.dst=newnode;
 489         if (e.src==oldnode)
 490           e.src=newnode;
 491         if (oldedgeset==null||!oldedgeset.contains(e))
 492           newSet.add(e);
 493       }
 494     }
 495     if (newSet!=null)
 496       edgeset.addAll(newSet);
 497   }
 498
 499   /* Shrinks the incoming set to just include rewritten values.
 500    * Returns a set of the original rewritten values */
 501
 502   HashSet<Edge> shrinkSet(HashSet<Edge> edgeset, HashSet<Edge> oldedgeset, AllocNode oldnode, AllocNode newnode) {
 503     HashSet<Edge> newSet=null;
 504     HashSet<Edge> removeSet=null;
 505     for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
 506       Edge e=edgeit.next();
 507       edgeit.remove();
 508       if (e.dst==oldnode||e.src==oldnode) {
 509         if (newSet==null) {
 510           newSet=new HashSet<Edge>();
 511           removeSet=new HashSet<Edge>();
 512         }
 513
 514         removeSet.add(e.copy());
 515         if (e.dst==oldnode)
 516           e.dst=newnode;
 517         if (e.src==oldnode)
 518           e.src=newnode;
 519         if (oldedgeset==null||!oldedgeset.contains(e))
 520           newSet.add(e);
 521       }
 522     }
 523     if (newSet!=null)
 524       edgeset.addAll(newSet);
 525     return removeSet;
 526   }
 527
 528   Delta applyInitDelta(Delta delta, BBlock block) {
 529     //Apply delta to graph
 530     boolean newGraph=false;
 531     if (!bbgraphMap.containsKey(block)) {
 532       bbgraphMap.put(block, new Graph(null));
 533       newGraph=true;
 534     }
 535     Delta newdelta;
 536     Graph graph=bbgraphMap.get(block);
 537
 538     if (newGraph) {
 539       newdelta=new Delta(null, true);
 540       //Add in heap edges and throw away original diff
 541       graph.nodeMap.putAll(delta.heapedgeadd);
 542       //Add in var edges and throw away original diff
 543       graph.varMap.putAll(delta.varedgeadd);
 544       //Record that this is initial set...
 545     } else {
 546       newdelta=new Delta(null, false);
 547       //merge in heap edges and variables
 548       mergeHeapEdges(graph, delta, newdelta);
 549       mergeVarEdges(graph, delta, newdelta);
 550       //Record that this is a diff
 551       newdelta.setInit(false);
 552     }
 553     return newdelta;
 554   }
 555
 556   /* This function merges in the heap edges.  It updates delta to be
 557    * the difference */
 558
 559   void mergeHeapEdges(Graph graph, Delta delta, Delta newdelta) {
 560     //Merge in edges
 561     for(Map.Entry<AllocNode, HashSet<Edge>> heapedge:delta.heapedgeadd.entrySet()) {
 562       AllocNode nsrc=heapedge.getKey();
 563       HashSet<Edge> edges=heapedge.getValue();
 564       if (!graph.nodeMap.containsKey(nsrc)) {
 565         graph.nodeMap.put(nsrc, new HashSet<Edge>());
 566       }
 567       HashSet<Edge> dstedges=graph.nodeMap.get(nsrc);
 568       HashSet<Edge> diffedges=new HashSet<Edge>();
 569       for(Edge e:edges) {
 570         if (!dstedges.contains(e)) {
 571           //We have a new edge
 572           diffedges.add(e);
 573           dstedges.add(e);
 574         }
 575       }
 576       //Done with edge set...
 577       if (diffedges.size()>0) {
 578         //completely new
 579         newdelta.baseheapedge.put(nsrc, diffedges);
 580       }
 581     }
 582   }
 583
 584   /* This function merges in the var edges.  It updates delta to be
 585    * the difference */
 586
 587   void mergeVarEdges(Graph graph, Delta delta, Delta newdelta) {
 588     //Merge in edges
 589     for(Map.Entry<TempDescriptor, HashSet<Edge>> varedge:delta.varedgeadd.entrySet()) {
 590       TempDescriptor tmpsrc=varedge.getKey();
 591       HashSet<Edge> edges=varedge.getValue();
 592       if (!graph.varMap.containsKey(tmpsrc)) {
 593         graph.varMap.put(tmpsrc, new HashSet<Edge>());
 594       }
 595       HashSet<Edge> dstedges=graph.varMap.get(tmpsrc);
 596       HashSet<Edge> diffedges=new HashSet<Edge>();
 597       for(Edge e:edges) {
 598         if (!dstedges.contains(e)) {
 599           //We have a new edge
 600           diffedges.add(e);
 601           dstedges.add(e);
 602         }
 603       }
 604       //Done with edge set...
 605       if (diffedges.size()>=0) {
 606         //completely new
 607         newdelta.basevaredge.put(tmpsrc,diffedges);
 608       }
 609     }
 610   }
 611 }