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