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