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 (false) {
 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());
 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           //skip the edge if types don't allow it...
1182           if (!typeUtil.isSuperorType(fcall.getReturnTemp().getType(), e.dst.getType()))
1183             continue;
1184           Edge newedge=e.copy();
1185           newedge.srcvar=fcall.getReturnTemp();
1186           if (seseCallers!=null)
1187             newedge.taintModify(seseCallers);
1188           mergeEdge(graph, newDelta, newedge);
1189         }
1190     }
1191     applyDiffs(graph, newDelta);
1192     return newDelta;
1193   }
1194
1195   public void mergeEdge(Graph graph, Delta newDelta, Edge edgetoadd) {
1196     if (edgetoadd!=null) {
1197       Edge match=graph.getMatch(edgetoadd);
1198
1199       if (match==null||!match.subsumes(edgetoadd)) {
1200         Edge mergededge=edgetoadd.merge(match);
1201         newDelta.addEdge(mergededge);
1202       }
1203     }
1204   }
1205
1206   /* This is a call produced edge...need to remember this */
1207
1208   public void mergeCallEdge(Graph graph, Delta newDelta, Edge edgetoadd) {
1209     if (edgetoadd!=null) {
1210       newDelta.addEdgeClear(edgetoadd);
1211
1212       Edge match=graph.getMatch(edgetoadd);
1213
1214       if (match==null||!match.subsumes(edgetoadd)) {
1215         Edge mergededge=edgetoadd.merge(match);
1216         newDelta.addEdge(mergededge);
1217         graph.callerEdges.add(mergededge);
1218       }
1219     }
1220   }
1221
1222
1223   /* Summarizes out of context nodes in graph */
1224   void summarizeInGraph(Graph graph, Delta newDelta, AllocNode singleNode) {
1225     AllocNode summaryNode=allocFactory.getAllocNode(singleNode, true);
1226
1227     //Handle outgoing heap edges
1228     MySet<Edge> edgeset=graph.getEdges(singleNode);
1229
1230     for(Edge e:edgeset) {
1231       Edge rewrite=e.rewrite(singleNode, summaryNode);
1232       //Remove old edge
1233       newDelta.removeHeapEdge(e);
1234       mergeCallEdge(graph, newDelta, rewrite);
1235     }
1236
1237     //Handle incoming edges
1238     MySet<Edge> backedges=graph.getBackEdges(singleNode);
1239     for(Edge e:backedges) {
1240       if (e.dst==singleNode) {
1241         //Need to get original edge so that predicate will be correct
1242         Edge match=graph.getMatch(e);
1243         if (match!=null) {
1244           Edge rewrite=match.rewrite(singleNode, summaryNode);
1245           newDelta.removeEdge(match);
1246           mergeCallEdge(graph, newDelta, rewrite);
1247         }
1248       }
1249     }
1250   }
1251
1252   void applyDiffs(Graph graph, Delta delta) {
1253     applyDiffs(graph, delta, false);
1254   }
1255
1256   void applyDiffs(Graph graph, Delta delta, boolean genbackwards) {
1257     //build backwards map if requested
1258     if (genbackwards&&graph.backMap==null) {
1259       graph.backMap=new HashMap<AllocNode, MySet<Edge>>();
1260       if (graph.parent.backMap==null) {
1261         graph.parent.backMap=new HashMap<AllocNode, MySet<Edge>>();
1262         for(Map.Entry<AllocNode, MySet<Edge>> entry:graph.nodeMap.entrySet()) {
1263           for(Edge e:entry.getValue()) {
1264             if (!graph.parent.backMap.containsKey(e.dst))
1265               graph.parent.backMap.put(e.dst, new MySet<Edge>());
1266             graph.parent.backMap.get(e.dst).add(e);
1267           }
1268         }
1269         for(Map.Entry<TempDescriptor, MySet<Edge>> entry:graph.varMap.entrySet()) {
1270           for(Edge e:entry.getValue()) {
1271             if (!graph.parent.backMap.containsKey(e.dst))
1272               graph.parent.backMap.put(e.dst, new MySet<Edge>());
1273             graph.parent.backMap.get(e.dst).add(e);
1274           }
1275         }
1276       }
1277     }
1278
1279     //Add hidden base edges
1280     for(Map.Entry<AllocNode, MySet<Edge>> e: delta.baseheapedge.entrySet()) {
1281       AllocNode node=e.getKey();
1282       MySet<Edge> edges=e.getValue();
1283       if (graph.nodeMap.containsKey(node)) {
1284         MySet<Edge> nodeEdges=graph.nodeMap.get(node);
1285         nodeEdges.addAll(edges);
1286       }
1287     }
1288
1289     //Remove heap edges
1290     for(Map.Entry<AllocNode, MySet<Edge>> e: delta.heapedgeremove.entrySet()) {
1291       AllocNode node=e.getKey();
1292       MySet<Edge> edgestoremove=e.getValue();
1293       if (graph.nodeMap.containsKey(node)) {
1294         //Just apply diff to current map
1295         graph.nodeMap.get(node).removeAll(edgestoremove);
1296       } else {
1297         //Generate diff from parent graph
1298         MySet<Edge> parentedges=graph.parent.nodeMap.get(node);
1299         if (parentedges!=null) {
1300           MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
1301           graph.nodeMap.put(node, newedgeset);
1302         }
1303       }
1304     }
1305
1306     //Add heap edges
1307     for(Map.Entry<AllocNode, MySet<Edge>> e: delta.heapedgeadd.entrySet()) {
1308       AllocNode node=e.getKey();
1309       MySet<Edge> edgestoadd=e.getValue();
1310       //If we have not done a subtract, then
1311       if (!graph.nodeMap.containsKey(node)) {
1312         //Copy the parent entry
1313         if (graph.parent.nodeMap.containsKey(node))
1314           graph.nodeMap.put(node, (MySet<Edge>)graph.parent.nodeMap.get(node).clone());
1315         else
1316           graph.nodeMap.put(node, new MySet<Edge>());
1317       }
1318       Edge.mergeEdgesInto(graph.nodeMap.get(node),edgestoadd);
1319       if (genbackwards) {
1320         for(Edge eadd:edgestoadd) {
1321           if (!graph.backMap.containsKey(eadd.dst))
1322             graph.backMap.put(eadd.dst, new MySet<Edge>());
1323           graph.backMap.get(eadd.dst).add(eadd);
1324         }
1325       }
1326     }
1327
1328     //Remove var edges
1329     for(Map.Entry<TempDescriptor, MySet<Edge>> e: delta.varedgeremove.entrySet()) {
1330       TempDescriptor tmp=e.getKey();
1331       MySet<Edge> edgestoremove=e.getValue();
1332
1333       if (graph.varMap.containsKey(tmp)) {
1334         //Just apply diff to current map
1335         graph.varMap.get(tmp).removeAll(edgestoremove);
1336       } else if (graph.parent.varMap.containsKey(tmp)) {
1337         //Generate diff from parent graph
1338         MySet<Edge> parentedges=graph.parent.varMap.get(tmp);
1339         MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
1340         graph.varMap.put(tmp, newedgeset);
1341       }
1342     }
1343
1344     //Add var edges
1345     for(Map.Entry<TempDescriptor, MySet<Edge>> e: delta.varedgeadd.entrySet()) {
1346       TempDescriptor tmp=e.getKey();
1347       MySet<Edge> edgestoadd=e.getValue();
1348       if (graph.varMap.containsKey(tmp)) {
1349         Edge.mergeEdgesInto(graph.varMap.get(tmp), edgestoadd);
1350       } else if (graph.parent.varMap.containsKey(tmp)) {
1351         graph.varMap.put(tmp, new MySet<Edge>(graph.parent.varMap.get(tmp)));
1352         Edge.mergeEdgesInto(graph.varMap.get(tmp), edgestoadd);
1353       } else
1354         graph.varMap.put(tmp, (MySet<Edge>) edgestoadd.clone());
1355       if (genbackwards) {
1356         for(Edge eadd:edgestoadd) {
1357           if (!graph.backMap.containsKey(eadd.dst))
1358             graph.backMap.put(eadd.dst, new MySet<Edge>());
1359           graph.backMap.get(eadd.dst).add(eadd);
1360         }
1361       }
1362     }
1363
1364     //Add node additions
1365     for(AllocNode node:delta.addNodeAges) {
1366       graph.nodeAges.add(node);
1367     }
1368
1369     for(Map.Entry<AllocNode, Boolean> nodeentry:delta.addOldNodes.entrySet()) {
1370       AllocNode node=nodeentry.getKey();
1371       Boolean ispresent=nodeentry.getValue();
1372       graph.oldNodes.put(node, ispresent);
1373     }
1374   }
1375
1376   boolean isINACC(FlatNode node) {
1377     if (!OoOJava)
1378       return false;
1379     switch(node.kind()) {
1380     case FKind.FlatSetFieldNode: {
1381       FlatSetFieldNode n=(FlatSetFieldNode)node;
1382       return !accessible.isAccessible(n, n.getDst());
1383     }
1384     case FKind.FlatSetElementNode: {
1385       FlatSetElementNode n=(FlatSetElementNode)node;
1386       return !accessible.isAccessible(n, n.getDst());
1387     }
1388     case FKind.FlatFieldNode: {
1389       FlatFieldNode n=(FlatFieldNode)node;
1390       return !accessible.isAccessible(n, n.getSrc());
1391     }
1392     case FKind.FlatElementNode: {
1393       FlatElementNode n=(FlatElementNode)node;
1394       return !accessible.isAccessible(n, n.getSrc());
1395     }
1396     }
1397     return false;
1398   }
1399
1400   Delta processSetFieldElementNode(FlatNode node, Delta delta, Graph graph) {
1401     TempDescriptor src;
1402     FieldDescriptor fd;
1403     TempDescriptor dst;
1404     if (node.kind()==FKind.FlatSetElementNode) {
1405       FlatSetElementNode fen=(FlatSetElementNode) node;
1406       src=fen.getSrc();
1407       fd=null;
1408       dst=fen.getDst();
1409     } else {
1410       FlatSetFieldNode ffn=(FlatSetFieldNode) node;
1411       src=ffn.getSrc();
1412       fd=ffn.getField();
1413       dst=ffn.getDst();
1414     }
1415
1416     if (delta.getInit()) {
1417       MySet<Edge> dstEdges=GraphManip.getEdges(graph, delta, dst);
1418
1419       if (OoOJava&&!accessible.isAccessible(node, dst)) {
1420         Taint dstStallTaint=Taint.factory(node,  dst, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1421         dstEdges=Edge.taintAll(dstEdges, dstStallTaint);
1422         updateVarDelta(graph, delta, dst, dstEdges, null);
1423       }
1424       if (OoOJava) {
1425         effectsAnalysis.analyzeFlatSetFieldNode(dstEdges, fd, node);
1426       }
1427
1428       //Do nothing for non pointers
1429       if (!src.getType().isPtr()) {
1430         if (mustProcess.contains(node)) {
1431           applyDiffs(graph, delta);
1432         }
1433         return delta;
1434       }
1435
1436       MySet<Edge> srcEdges=GraphManip.getEdges(graph, delta, src);
1437       if (OoOJava&&!accessible.isAccessible(node, src)) {
1438         Taint srcStallTaint=Taint.factory(node,  src, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1439         srcEdges=Edge.taintAll(srcEdges, srcStallTaint);
1440         updateVarDelta(graph, delta, src, srcEdges, null);
1441       }
1442
1443       MySet<Edge> edgesToAdd=GraphManip.genEdges(dstEdges, fd, srcEdges);
1444       MySet<Edge> edgesToRemove=null;
1445       if (dstEdges.size()==1&&!dstEdges.iterator().next().dst.isSummary()&&fd!=null) {
1446         /* Can do a strong update */
1447         edgesToRemove=GraphManip.getEdges(graph, delta, dstEdges, fd);
1448         graph.strongUpdateSet=edgesToRemove;
1449       } else
1450         graph.strongUpdateSet=new MySet<Edge>();
1451
1452       /* Update diff */
1453       updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
1454       applyDiffs(graph, delta);
1455     } else {
1456       MySet<Edge> newDstEdges=GraphManip.getDiffEdges(delta, dst);
1457
1458       if (OoOJava&&!accessible.isAccessible(node, dst)) {
1459         Taint dstStallTaint=Taint.factory(node,  dst, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1460         newDstEdges=Edge.taintAll(newDstEdges, dstStallTaint);
1461         updateVarDelta(graph, delta, dst, newDstEdges, null);
1462       }
1463
1464       if (OoOJava) {
1465         effectsAnalysis.analyzeFlatSetFieldNode(newDstEdges, fd, node);
1466       }
1467
1468       if (!src.getType().isPtr()) {
1469         if (mustProcess.contains(node)) {
1470           applyDiffs(graph, delta);
1471         }
1472         return delta;
1473       }
1474
1475       /* Next look at new sources */
1476
1477       MySet<Edge> edgesToAdd=new MySet<Edge>();
1478       MySet<Edge> newSrcEdges=GraphManip.getDiffEdges(delta, src);
1479       MySet<Edge> srcEdges=GraphManip.getEdges(graph, delta, src);
1480       HashSet<AllocNode> dstNodes=GraphManip.getNodes(graph, delta, dst);
1481
1482       if (OoOJava&&!accessible.isAccessible(node, src)) {
1483         Taint srcStallTaint=Taint.factory(node,  src, AllocFactory.dummySite, null, ReachGraph.predsEmpty);
1484         newSrcEdges=Edge.taintAll(newSrcEdges, srcStallTaint);
1485         updateVarDelta(graph, delta, src, newSrcEdges, null);
1486       }
1487
1488       MySet<Edge> edgesToRemove=null;
1489       if (newDstEdges.size()!=0) {
1490         if (dstNodes.size()>1&&!dstNodes.iterator().next().isSummary()&&fd!=null) {
1491           /* Need to undo strong update */
1492           if (graph.strongUpdateSet!=null) {
1493             edgesToAdd.addAll(graph.strongUpdateSet);
1494             graph.strongUpdateSet=null; //Prevent future strong updates
1495           }
1496         } else if (dstNodes.size()==1&&newDstEdges.size()==1&&!newDstEdges.iterator().next().dst.isSummary()&&graph.strongUpdateSet!=null&&fd!=null) {
1497           edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
1498           graph.strongUpdateSet.addAll(edgesToRemove);
1499         }
1500         Edge.mergeEdgesInto(edgesToAdd, GraphManip.genEdges(newDstEdges, fd, srcEdges));
1501       }
1502
1503       //Kill new edges
1504       if (graph.strongUpdateSet!=null&&fd!=null) {
1505         MySet<Edge> otherEdgesToRemove=GraphManip.getDiffEdges(delta, dstNodes, fd);
1506         if (edgesToRemove!=null)
1507           edgesToRemove.addAll(otherEdgesToRemove);
1508         else
1509           edgesToRemove=otherEdgesToRemove;
1510         graph.strongUpdateSet.addAll(otherEdgesToRemove);
1511       }
1512
1513       //Next look at new destinations
1514       Edge.mergeEdgesInto(edgesToAdd, GraphManip.genEdges(dstNodes, fd, newSrcEdges));
1515
1516       /* Update diff */
1517       updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
1518       applyDiffs(graph, delta);
1519     }
1520     return delta;
1521   }
1522
1523   Delta processCopyNode(FlatNode node, Delta delta, Graph graph) {
1524     TempDescriptor src;
1525     TempDescriptor dst;
1526     if (node.kind()==FKind.FlatOpNode) {
1527       FlatOpNode fon=(FlatOpNode) node;
1528       src=fon.getLeft();
1529       dst=fon.getDest();
1530     } else if (node.kind()==FKind.FlatReturnNode) {
1531       FlatReturnNode frn=(FlatReturnNode)node;
1532       src=frn.getReturnTemp();
1533       dst=returntmp;
1534       if (src==null||!src.getType().isPtr()) {
1535         //This is a NOP
1536         applyDiffs(graph, delta);
1537         return delta;
1538       }
1539     } else {
1540       FlatCastNode fcn=(FlatCastNode) node;
1541       src=fcn.getSrc();
1542       dst=fcn.getDst();
1543     }
1544     if (delta.getInit()) {
1545       MySet<Edge> srcedges=GraphManip.getEdges(graph, delta, src);
1546       MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, srcedges);
1547       MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
1548       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1549       applyDiffs(graph, delta);
1550     } else {
1551       /* First compute new src nodes */
1552       MySet<Edge> newSrcEdges=GraphManip.getDiffEdges(delta, src);
1553
1554       /* Compute the union, and then the set of edges */
1555       MySet<Edge> edgesToAdd=GraphManip.genEdges(dst, newSrcEdges);
1556
1557       /* Compute set of edges to remove */
1558       MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
1559
1560       /* Update diff */
1561       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1562       applyDiffs(graph, delta);
1563     }
1564     return delta;
1565   }
1566
1567   Delta processFieldElementNode(FlatNode node, Delta delta, Graph graph) {
1568     TempDescriptor src;
1569     FieldDescriptor fd;
1570     TempDescriptor dst;
1571     TaintSet taint=null;
1572
1573     if (node.kind()==FKind.FlatElementNode) {
1574       FlatElementNode fen=(FlatElementNode) node;
1575       src=fen.getSrc();
1576       fd=null;
1577       dst=fen.getDst();
1578     } else {
1579       FlatFieldNode ffn=(FlatFieldNode) node;
1580       src=ffn.getSrc();
1581       fd=ffn.getField();
1582       dst=ffn.getDst();
1583     }
1584     if (OoOJava&&!accessible.isAccessible(node, src)) {
1585       taint=TaintSet.factory(Taint.factory(node,  src, AllocFactory.dummySite, null, ReachGraph.predsEmpty));
1586     }
1587
1588     //Do nothing for non pointers
1589     if (delta.getInit()) {
1590       MySet<Edge> srcedges=GraphManip.getEdges(graph, delta, src);
1591       if (OoOJava) {
1592         if (taint!=null) {
1593           srcedges=Edge.taintAll(srcedges, taint);
1594           updateVarDelta(graph, delta, src, srcedges, null);
1595         }
1596         effectsAnalysis.analyzeFlatFieldNode(srcedges, fd, node);
1597       }
1598       if (!dst.getType().isPtr()) {
1599         if (mustProcess.contains(node)) {
1600           applyDiffs(graph, delta);
1601         }
1602         return delta;
1603       }
1604
1605       MySet<Edge> edgesToAdd=GraphManip.dereference(graph, delta, dst, srcedges, fd, node);
1606       MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
1607
1608       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1609       applyDiffs(graph, delta);
1610     } else {
1611       MySet<Edge> newsrcedges=GraphManip.getDiffEdges(delta, src);
1612       if (OoOJava) {
1613         if (taint!=null) {
1614           newsrcedges=Edge.taintAll(newsrcedges, taint);
1615           updateVarDelta(graph, delta, src, newsrcedges, null);
1616         }
1617         effectsAnalysis.analyzeFlatFieldNode(newsrcedges, fd, node);
1618       }
1619       if (!dst.getType().isPtr()) {
1620         if (mustProcess.contains(node)) {
1621           applyDiffs(graph, delta);
1622         }
1623         return delta;
1624       }
1625       /* First compute new objects we read fields of */
1626       MySet<Edge> allsrcedges=GraphManip.getEdges(graph, delta, src);
1627       MySet<Edge> edgesToAdd=GraphManip.diffDereference(delta, dst, allsrcedges, fd, node);
1628       /* Next compute new targets of fields */
1629       MySet<Edge> newfdedges=GraphManip.dereference(graph, delta, dst, newsrcedges, fd, node);
1630
1631       /* Compute the union, and then the set of edges */
1632       Edge.mergeEdgesInto(edgesToAdd, newfdedges);
1633
1634       /* Compute set of edges to remove */
1635       MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
1636
1637
1638       /* Update diff */
1639       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
1640       applyDiffs(graph, delta);
1641     }
1642
1643     return delta;
1644   }
1645
1646   void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1647     MySet<Edge> edgeAdd=delta.varedgeadd.get(tmp);
1648     MySet<Edge> edgeRemove=delta.varedgeremove.get(tmp);
1649     MySet<Edge> existingEdges=graph.getEdges(tmp);
1650     if (edgestoRemove!=null)
1651       for(Edge e: edgestoRemove) {
1652         //remove edge from delta
1653         if (edgeAdd!=null)
1654           edgeAdd.remove(e);
1655         //if the edge is already in the graph, add an explicit remove to the delta
1656         if (existingEdges.contains(e))
1657           delta.removeVarEdge(e);
1658       }
1659     for(Edge e: edgestoAdd) {
1660       //Remove the edge from the remove set
1661       if (edgeRemove!=null)
1662         edgeRemove.remove(e);
1663       //Explicitly add it to the add set unless it is already in the graph
1664       if (typeUtil.isSuperorType(tmp.getType(), e.dst.getType())) {
1665         if (!existingEdges.contains(e)) {
1666           delta.addVarEdge(e);
1667         } else {
1668           //See if the old edge subsumes the new one
1669           Edge olde=existingEdges.get(e);
1670           if (!olde.subsumes(e)) {
1671             delta.addVarEdge(olde.merge(e));
1672           }
1673         }
1674       }
1675     }
1676   }
1677
1678   void updateHeapDelta(Graph graph, Delta delta, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
1679     if (edgestoRemove!=null)
1680       for(Edge e: edgestoRemove) {
1681         AllocNode src=e.src;
1682         MySet<Edge> edgeAdd=delta.heapedgeadd.get(src);
1683         MySet<Edge> existingEdges=graph.getEdges(src);
1684         //remove edge from delta
1685         if (edgeAdd!=null)
1686           edgeAdd.remove(e);
1687         //if the edge is already in the graph, add an explicit remove to the delta
1688         if (existingEdges.contains(e)) {
1689           delta.removeHeapEdge(e);
1690         }
1691       }
1692     if (edgestoAdd!=null)
1693       for(Edge e: edgestoAdd) {
1694         AllocNode src=e.src;
1695         MySet<Edge> edgeRemove=delta.heapedgeremove.get(src);
1696         MySet<Edge> existingEdges=graph.getEdges(src);
1697         //Remove the edge from the remove set
1698         if (edgeRemove!=null)
1699           edgeRemove.remove(e);
1700         //Explicitly add it to the add set unless it is already in the graph
1701         if (!existingEdges.contains(e)) {
1702           delta.addHeapEdge(e);
1703         } else {
1704           //See if the old edge subsumes the new one
1705           Edge olde=existingEdges.get(e);
1706           if (!olde.subsumes(e)) {
1707             delta.addHeapEdge(olde.merge(e));
1708           }
1709         }
1710       }
1711   }
1712
1713   Delta processFlatNop(FlatNode node, Delta delta, Graph graph) {
1714     applyDiffs(graph, delta);
1715     return delta;
1716   }
1717
1718   Delta processNewNode(FlatNew node, Delta delta, Graph graph) {
1719     AllocNode summary=allocFactory.getAllocNode(node, true);
1720     AllocNode single=allocFactory.getAllocNode(node, false);
1721     TempDescriptor tmp=node.getDst();
1722
1723     if (delta.getInit()) {
1724       /* We don't have to deal with summarization here...  The
1725        * intuition is that this is the only place where we generate
1726        * nodes for this allocation site and this is the first time
1727        * we've analyzed this site */
1728
1729       //Build new Edge
1730       Edge e=new Edge(tmp, single);
1731       //Build new Edge set
1732       MySet<Edge> newedges=new MySet<Edge>();
1733       newedges.add(e);
1734       //Add it into the diffs
1735       delta.varedgeadd.put(tmp, newedges);
1736       //Remove the old edges
1737       MySet<Edge> oldedges=graph.getEdges(tmp);
1738       if (!oldedges.isEmpty())
1739         delta.varedgeremove.put(tmp, (MySet<Edge>) oldedges);
1740       //Note that we create a single node
1741       delta.addNodeAges.add(single);
1742       //Kill the old node
1743       if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1744         delta.addOldNodes.put(single, Boolean.FALSE);
1745       }
1746     } else {
1747       /* 1. Fix up the variable edge additions */
1748
1749       for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.varedgeadd.entrySet().iterator();entryIt.hasNext();) {
1750         Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1751
1752         if (entry.getKey()==tmp) {
1753           /* Check if this is the tmp we overwrite */
1754           entryIt.remove();
1755         } else {
1756           /* Otherwise, check if the target of the edge is changed... */
1757           summarizeSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary);
1758         }
1759       }
1760
1761       /* 2. Fix up the base variable edges */
1762
1763       for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.basevaredge.entrySet().iterator();entryIt.hasNext();) {
1764         Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
1765         TempDescriptor entrytmp=entry.getKey();
1766         if (entrytmp==tmp) {
1767           /* Check is this is the tmp we overwrite, if so add to remove set */
1768           Util.relationUpdate(delta.varedgeremove, tmp, null, entry.getValue());
1769         } else if (graph.varMap.containsKey(entrytmp)) {
1770           /* Check if the target of the edge is changed */
1771           MySet<Edge> newset=(MySet<Edge>)entry.getValue().clone();
1772           MySet<Edge> removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary);
1773           Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset);
1774           Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset);
1775         } else {
1776           /* Check if the target of the edge is changed */
1777           MySet<Edge> newset=(MySet<Edge>)entry.getValue().clone();
1778           MySet<Edge> removeset=shrinkSet(newset, graph.parent.varMap.get(entrytmp), single, summary);
1779           Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset);
1780           Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset);
1781         }
1782       }
1783
1784
1785       /* 3. Fix up heap edge additions */
1786
1787       HashMap<AllocNode, MySet<Edge>> addheapedge=new HashMap<AllocNode, MySet<Edge>>();
1788       for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.heapedgeadd.entrySet().iterator();entryIt.hasNext();) {
1789         Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1790         MySet<Edge> edgeset=entry.getValue();
1791         AllocNode allocnode=entry.getKey();
1792         if (allocnode==single) {
1793           entryIt.remove();
1794           summarizeSet(edgeset, graph.nodeMap.get(summary), single, summary);
1795           addheapedge.put(summary, edgeset);
1796         } else {
1797           summarizeSet(edgeset, graph.nodeMap.get(allocnode), single, summary);
1798         }
1799       }
1800
1801       /* Merge in diffs */
1802
1803       for(Map.Entry<AllocNode, MySet<Edge>> entry:addheapedge.entrySet()) {
1804         AllocNode allocnode=entry.getKey();
1805         Util.relationUpdate(delta.heapedgeadd, allocnode, null, entry.getValue());
1806       }
1807
1808       /* 4. Fix up the base heap edges */
1809
1810       for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.baseheapedge.entrySet().iterator();entryIt.hasNext();) {
1811         Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
1812         MySet<Edge> edgeset=entry.getValue();
1813         AllocNode allocnode=entry.getKey();
1814         if (allocnode==single) {
1815           entryIt.remove();
1816         }
1817         AllocNode addnode=(allocnode==single)?summary:allocnode;
1818
1819         MySet<Edge> newset=(MySet<Edge>) edgeset.clone();
1820         MySet<Edge> removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary);
1821         Util.relationUpdate(delta.heapedgeadd, addnode, null, newset);
1822         Util.relationUpdate(delta.heapedgeremove, allocnode, null, removeset);
1823       }
1824
1825       /* Update Node Ages...If the base or addNodeAges set contains a
1826        * single node, it now should also contain a summary node...  No
1827        * need to generate a single node as that has already been
1828        * done. */
1829       if (delta.baseNodeAges.contains(single)||delta.addNodeAges.contains(single)) {
1830         delta.addNodeAges.add(summary);
1831       }
1832
1833       //Kill the old node if someone tries to add it
1834       if (delta.addOldNodes.containsKey(single)||delta.baseOldNodes.containsKey(single)) {
1835         delta.addOldNodes.put(single, Boolean.FALSE);
1836       }
1837
1838     }
1839     //Apply incoming diffs to graph
1840     applyDiffs(graph, delta);
1841
1842     return delta;
1843   }
1844
1845   /* This function builds a new edge set where oldnode is summarized into new node */
1846
1847   void summarizeSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode sumnode) {
1848     MySet<Edge> newSet=null;
1849     for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
1850       Edge e=edgeit.next();
1851       if (e.dst==oldnode||e.src==oldnode) {
1852         if (newSet==null) {
1853           newSet=new MySet<Edge>();
1854         }
1855         edgeit.remove();
1856         e=e.copy();
1857
1858         if (e.dst==oldnode) {
1859           e.dst=sumnode;
1860         }
1861         if (e.src==oldnode) {
1862           e.src=sumnode;
1863         }
1864         if (oldedgeset==null||!oldedgeset.contains(e))
1865           newSet.add(e);
1866       }
1867     }
1868     if (newSet!=null)
1869       edgeset.addAll(newSet);
1870   }
1871
1872   /* Shrinks the incoming set to just include rewritten values.
1873    * Returns a set of the original rewritten values */
1874
1875   MySet<Edge> shrinkSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode newnode) {
1876     MySet<Edge> newSet=null;
1877     MySet<Edge> removeSet=null;
1878     for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
1879       Edge e=edgeit.next();
1880       edgeit.remove();
1881       if (e.dst==oldnode||e.src==oldnode) {
1882         if (newSet==null) {
1883           newSet=new MySet<Edge>();
1884           removeSet=new MySet<Edge>();
1885         }
1886
1887         removeSet.add(e);
1888         e=e.copy();
1889         if (e.dst==oldnode)
1890           e.dst=newnode;
1891         if (e.src==oldnode)
1892           e.src=newnode;
1893         if (oldedgeset==null||!oldedgeset.contains(e))
1894           newSet.add(e);
1895       }
1896     }
1897     if (newSet!=null)
1898       edgeset.addAll(newSet);
1899     return removeSet;
1900   }
1901
1902   /* This function returns a completely new Delta...  It is safe to
1903    * modify this */
1904
1905   Delta applyInitDelta(Delta delta, BBlock block) {
1906     //Apply delta to graph
1907     boolean newGraph=false;
1908     if (!bbgraphMap.containsKey(block)) {
1909       bbgraphMap.put(block, new Graph(null));
1910       newGraph=true;
1911     }
1912     Graph graph=bbgraphMap.get(block);
1913
1914     if (newGraph) {
1915       Delta newdelta=new Delta(null, true);
1916       //Add in heap edges and throw away original diff
1917
1918       for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.heapedgeadd.entrySet()) {
1919         graph.nodeMap.put(entry.getKey(), new MySet<Edge>(entry.getValue()));
1920       }
1921       //Add in var edges and throw away original diff
1922       Set<TempDescriptor> livetemps=bblivetemps.get(block);
1923
1924       for(Map.Entry<TempDescriptor, MySet<Edge>> entry:delta.varedgeadd.entrySet()) {
1925         if (livetemps.contains(entry.getKey()))
1926           graph.varMap.put(entry.getKey(), new MySet<Edge>(entry.getValue()));
1927       }
1928       //Record that this is initial set...
1929       graph.nodeAges.addAll(delta.addNodeAges);
1930       //Add old nodes
1931       for(Map.Entry<AllocNode, Boolean> oldentry:delta.addOldNodes.entrySet()) {
1932         if (oldentry.getValue().booleanValue()) {
1933           graph.oldNodes.put(oldentry.getKey(), Boolean.TRUE);
1934         }
1935       }
1936       return newdelta;
1937     } else {
1938       Delta newdelta=new Delta(null, false);
1939       //merge in heap edges and variables
1940       mergeHeapEdges(graph, delta, newdelta);
1941       mergeVarEdges(graph, delta, newdelta, block);
1942       mergeAges(graph, delta, newdelta);
1943       return newdelta;
1944     }
1945   }
1946
1947   /* This function merges in the heap edges.  It updates delta to be
1948    * the difference */
1949
1950   void mergeHeapEdges(Graph graph, Delta delta, Delta newdelta) {
1951     //Merge in edges
1952     for(Map.Entry<AllocNode, MySet<Edge>> heapedge:delta.heapedgeadd.entrySet()) {
1953       AllocNode nsrc=heapedge.getKey();
1954       MySet<Edge> edges=heapedge.getValue();
1955
1956       if (graph.backMap!=null) {
1957         for(Edge e:edges) {
1958           if (!graph.backMap.containsKey(e.dst))
1959             graph.backMap.put(e.dst, new MySet<Edge>());
1960           graph.backMap.get(e.dst).add(e);
1961         }
1962       }
1963
1964       if (!graph.nodeMap.containsKey(nsrc)) {
1965         graph.nodeMap.put(nsrc, new MySet<Edge>());
1966       }
1967       MySet<Edge> dstedges=graph.nodeMap.get(nsrc);
1968       MySet<Edge> diffedges=new MySet<Edge>();
1969       for(Edge e:edges) {
1970         if (!dstedges.contains(e)) {
1971           //We have a new edge
1972           diffedges.add(e);
1973           dstedges.add(e);
1974         } else {
1975           Edge origedge=dstedges.get(e);
1976           if (!origedge.subsumes(e)) {
1977             Edge mergededge=origedge.merge(e);
1978             diffedges.add(mergededge);
1979             dstedges.add(mergededge);
1980           }
1981         }
1982       }
1983       //Done with edge set...
1984       if (diffedges.size()>0) {
1985         //completely new
1986         newdelta.baseheapedge.put(nsrc, diffedges);
1987       }
1988     }
1989   }
1990
1991   /* This function merges in the var edges.  It updates delta to be
1992    * the difference */
1993
1994   void mergeVarEdges(Graph graph, Delta delta, Delta newdelta, BBlock block) {
1995     //Merge in edges
1996     Set<TempDescriptor> livetemps=bblivetemps.get(block);
1997
1998     for(Map.Entry<TempDescriptor, MySet<Edge>> varedge:delta.varedgeadd.entrySet()) {
1999       TempDescriptor tmpsrc=varedge.getKey();
2000       if (livetemps.contains(tmpsrc)) {
2001         MySet<Edge> edges=varedge.getValue();
2002         if (graph.backMap!=null) {
2003           for(Edge e:edges) {
2004             if (!graph.backMap.containsKey(e.dst))
2005               graph.backMap.put(e.dst, new MySet<Edge>());
2006             graph.backMap.get(e.dst).add(e);
2007           }
2008         }
2009
2010         if (!graph.varMap.containsKey(tmpsrc)) {
2011           graph.varMap.put(tmpsrc, new MySet<Edge>());
2012         }
2013         MySet<Edge> dstedges=graph.varMap.get(tmpsrc);
2014         MySet<Edge> diffedges=new MySet<Edge>();
2015         for(Edge e:edges) {
2016           if (!dstedges.contains(e)) {
2017             //We have a new edge
2018             diffedges.add(e);
2019             dstedges.add(e);
2020           } else {
2021             Edge origedge=dstedges.get(e);
2022             if (!origedge.subsumes(e)) {
2023               Edge mergededge=origedge.merge(e);
2024               diffedges.add(mergededge);
2025               dstedges.add(mergededge);
2026             }
2027           }
2028         }
2029         //Done with edge set...
2030         if (diffedges.size()>0) {
2031           //completely new
2032           newdelta.basevaredge.put(tmpsrc,diffedges);
2033         }
2034       }
2035     }
2036   }
2037
2038   void mergeAges(Graph graph, Delta delta, Delta newDelta) {
2039     //Merge in edges
2040     for(AllocNode node:delta.addNodeAges) {
2041       if (!graph.nodeAges.contains(node)) {
2042         graph.nodeAges.add(node);
2043         newDelta.baseNodeAges.add(node);
2044       }
2045     }
2046     for(Map.Entry<AllocNode, Boolean> oldentry:delta.addOldNodes.entrySet()) {
2047       AllocNode node=oldentry.getKey();
2048       boolean ispresent=oldentry.getValue().booleanValue();
2049       if (ispresent&&!graph.oldNodes.containsKey(node)) {
2050         graph.oldNodes.put(node, Boolean.TRUE);
2051         newDelta.baseOldNodes.put(node, Boolean.TRUE);
2052       }
2053     }
2054   }
2055 }