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