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