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