Robust/src/Analysis/Pointer/Pointer.java

   1 package Analysis.Pointer;
   2 import java.util.*;
   3 import IR.Flat.*;
   4 import IR.*;
   5 import Analysis.Pointer.BasicBlock.BBlock;
   6 import Analysis.Pointer.AllocFactory.AllocNode;
   7
   8 public class Pointer {
   9   HashMap<FlatMethod, BasicBlock> blockMap;
  10   HashMap<BBlock, Graph> bbgraphMap;
  11   HashMap<FlatNode, Graph> graphMap;
  12   HashMap<FlatCall, Set<BBlock>> callMap;
  13   HashMap<BBlock, Set<PPoint>> returnMap;
  14
  15   State state;
  16   TypeUtil typeUtil;
  17   AllocFactory allocFactory;
  18   LinkedList<Delta> toprocess;
  19   TempDescriptor returntmp;
  20
  21   public Pointer(State state, TypeUtil typeUtil) {
  22     this.state=state;
  23     this.blockMap=new HashMap<FlatMethod, BasicBlock>();
  24     this.bbgraphMap=new HashMap<BBlock, Graph>();
  25     this.graphMap=new HashMap<FlatNode, Graph>();
  26     this.callMap=new HashMap<FlatCall, Set<BBlock>>();
  27     this.returnMap=new HashMap<BBlock, Set<PPoint>>();
  28     this.typeUtil=typeUtil;
  29     this.allocFactory=new AllocFactory(state, typeUtil);
  30     this.toprocess=new LinkedList<Delta>();
  31     ClassDescriptor stringcd=typeUtil.getClass(TypeUtil.ObjectClass);
  32     this.returntmp=new TempDescriptor("RETURNVAL", stringcd);
  33   }
  34
  35   public BasicBlock getBBlock(FlatMethod fm) {
  36     if (!blockMap.containsKey(fm))
  37       blockMap.put(fm, BasicBlock.getBBlock(fm));
  38     return blockMap.get(fm);
  39   }
  40
  41   Delta buildInitialContext() {
  42     MethodDescriptor md=typeUtil.getMain();
  43     FlatMethod fm=state.getMethodFlat(md);
  44     BasicBlock bb=getBBlock(fm);
  45     BBlock start=bb.getStart();
  46     Delta delta=new Delta(new PPoint(start), true);
  47     MySet<Edge> arrayset=new MySet<Edge>();
  48     MySet<Edge> varset=new MySet<Edge>();
  49     Edge arrayedge=new Edge(allocFactory.StringArray, null, allocFactory.Strings);
  50     arrayset.add(arrayedge);
  51     Edge stringedge=new Edge(fm.getParameter(0), allocFactory.StringArray);
  52     varset.add(stringedge);
  53     delta.heapedgeadd.put(allocFactory.StringArray, arrayset);
  54     delta.varedgeadd.put(fm.getParameter(0), varset);
  55     return delta;
  56   }
  57
  58   public void doAnalysis() {
  59     toprocess.add(buildInitialContext());
  60
  61     while(!toprocess.isEmpty()) {
  62       Delta delta=toprocess.remove();
  63       PPoint ppoint=delta.getBlock();
  64       BBlock bblock=ppoint.getBBlock();
  65       Vector<FlatNode> nodes=bblock.nodes();
  66
  67       //Build base graph for entrance to this basic block
  68       delta=applyInitDelta(delta, bblock);
  69       Graph graph=bbgraphMap.get(bblock);
  70
  71       Graph nodeGraph=null;
  72       //Compute delta at exit of each node
  73       for(int i=0; i<nodes.size();i++) {
  74         FlatNode currNode=nodes.get(i);
  75         if (!graphMap.containsKey(currNode)) {
  76           graphMap.put(currNode, new Graph(graph));
  77         }
  78         nodeGraph=graphMap.get(currNode);
  79         delta=processNode(bblock, i, currNode, delta, nodeGraph);
  80       }
  81       generateFinalDelta(bblock, delta, nodeGraph);
  82     }
  83   }
  84
  85   void buildInitDelta(Graph graph, Delta newDelta) {
  86     //First compute the set of temps
  87     HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
  88     tmpSet.addAll(graph.varMap.keySet());
  89     tmpSet.addAll(graph.parent.varMap.keySet());
  90
  91     //Next build the temp map part of the delta
  92     for(TempDescriptor tmp:tmpSet) {
  93       MySet<Edge> edgeSet=new MySet<Edge>();
  94       /* Get target set */
  95       if (graph.varMap.containsKey(tmp))
  96         edgeSet.addAll(graph.varMap.get(tmp));
  97       else
  98         edgeSet.addAll(graph.parent.varMap.get(tmp));
  99       newDelta.varedgeadd.put(tmp, edgeSet);
 100     }
 101
 102     //Next compute the set of src allocnodes
 103     HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
 104     nodeSet.addAll(graph.nodeMap.keySet());
 105     nodeSet.addAll(graph.parent.nodeMap.keySet());
 106
 107     for(AllocNode node:nodeSet) {
 108       MySet<Edge> edgeSet=new MySet<Edge>();
 109       /* Get edge set */
 110       if (graph.nodeMap.containsKey(node))
 111         edgeSet.addAll(graph.nodeMap.get(node));
 112       else
 113         edgeSet.addAll(graph.parent.nodeMap.get(node));
 114       newDelta.heapedgeadd.put(node, edgeSet);
 115
 116       /* Compute ages */
 117       if (graph.nodeAges.contains(node))
 118         newDelta.addNodeAges.add(node);
 119       else if (graph.parent.nodeAges.contains(node))
 120         newDelta.addNodeAges.add(node);
 121     }
 122   }
 123
 124   void generateFinalDelta(BBlock bblock, Delta delta, Graph graph) {
 125     Delta newDelta=new Delta(null, false);
 126     if (delta.getInit()) {
 127       buildInitDelta(graph, newDelta);
 128     } else {
 129       /* We can break the old delta...it is done being used */
 130       /* First we will build variable edges */
 131       HashSet<TempDescriptor> tmpSet=new HashSet<TempDescriptor>();
 132       tmpSet.addAll(delta.basevaredge.keySet());
 133       tmpSet.addAll(delta.varedgeadd.keySet());
 134       for(TempDescriptor tmp:tmpSet) {
 135         /* Start with the new incoming edges */
 136         MySet<Edge> newbaseedge=delta.basevaredge.get(tmp);
 137         /* Remove the remove set */
 138         newbaseedge.removeAll(delta.varedgeremove.get(tmp));
 139         /* Add in the new set*/
 140         newbaseedge.addAll(delta.varedgeadd.get(tmp));
 141         /* Store the results */
 142         newDelta.varedgeadd.put(tmp, newbaseedge);
 143       }
 144
 145       /* Next we build heap edges */
 146       HashSet<AllocNode> nodeSet=new HashSet<AllocNode>();
 147       nodeSet.addAll(delta.baseheapedge.keySet());
 148       nodeSet.addAll(delta.heapedgeadd.keySet());
 149       nodeSet.addAll(delta.heapedgeremove.keySet());
 150       for(AllocNode node:nodeSet) {
 151         /* Start with the new incoming edges */
 152         MySet<Edge> newheapedge=(MySet<Edge>) delta.baseheapedge.get(node).clone();
 153         /* Remove the remove set */
 154         newheapedge.removeAll(delta.heapedgeremove.get(node));
 155         /* Add in the add set */
 156         newheapedge.addAll(delta.heapedgeadd.get(node));
 157         newDelta.heapedgeadd.put(node, newheapedge);
 158
 159         /* Also need to subtract off some edges */
 160         MySet<Edge> removeset=delta.heapedgeremove.get(node);
 161
 162         /* Remove the newly created edges..no need to propagate a diff for those */
 163         removeset.removeAll(delta.baseheapedge.get(node));
 164         newDelta.heapedgeremove.put(node, removeset);
 165       }
 166
 167       /* Compute new ages */
 168       newDelta.addNodeAges.addAll(delta.baseNodeAges);
 169       newDelta.addNodeAges.addAll(delta.addNodeAges);
 170     }
 171
 172     /* Now we need to propagate newdelta */
 173     if (!newDelta.heapedgeadd.isEmpty()||!newDelta.heapedgeremove.isEmpty()||!newDelta.varedgeadd.isEmpty()||!newDelta.addNodeAges.isEmpty()) {
 174       /* We have a delta to propagate */
 175       Vector<BBlock> blockvector=bblock.next();
 176       for(int i=0;i<blockvector.size();i++) {
 177         if (i==0) {
 178           newDelta.setBlock(new PPoint(blockvector.get(i)));
 179           toprocess.add(newDelta);
 180         } else {
 181           toprocess.add(newDelta.diffBlock(new PPoint(blockvector.get(i))));
 182         }
 183       }
 184     }
 185   }
 186
 187   Delta processNode(BBlock bblock, int index, FlatNode node, Delta delta, Graph newgraph) {
 188     switch(node.kind()) {
 189     case FKind.FlatNew:
 190       return processNewNode((FlatNew)node, delta, newgraph);
 191     case FKind.FlatFieldNode:
 192     case FKind.FlatElementNode:
 193       return processFieldElementNode(node, delta, newgraph);
 194     case FKind.FlatCastNode:
 195     case FKind.FlatOpNode:
 196     case FKind.FlatReturnNode:
 197       return processCopyNode(node, delta, newgraph);
 198     case FKind.FlatSetFieldNode:
 199     case FKind.FlatSetElementNode:
 200       return processSetFieldElementNode(node, delta, newgraph);
 201     case FKind.FlatMethod:
 202     case FKind.FlatExit:
 203       return processFlatNop(node, delta, newgraph);
 204     case FKind.FlatCall:
 205       return processFlatCall(bblock, index, (FlatCall) node, delta, newgraph);
 206     case FKind.FlatSESEEnterNode:
 207     case FKind.FlatSESEExitNode:
 208       throw new Error("Unimplemented node:"+node);
 209     default:
 210       throw new Error("Unrecognized node:"+node);
 211     }
 212   }
 213
 214
 215   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) {
 216     //Handle the this temp
 217     if (tmpthis!=null) {
 218       MySet<Edge> edges=(oldnodeset!=null)?GraphManip.getDiffEdges(delta, tmpthis):GraphManip.getEdges(graph, delta, tmpthis);
 219       newDelta.varedgeadd.put(tmpthis, (MySet<Edge>) edges.clone());
 220       edgeset.addAll(edges);
 221       for(Edge e:edges) {
 222         AllocNode dstnode=e.dst;
 223         if (!nodeset.contains(dstnode)&&(oldnodeset==null||!oldnodeset.contains(dstnode))) {
 224           TypeDescriptor type=dstnode.getType();
 225           if (!type.isArray()) {
 226             targetSet.add(type.getClassDesc());
 227           } else {
 228             //arrays don't have code
 229             targetSet.add(typeUtil.getClass(TypeUtil.ObjectClass));
 230           }
 231           nodeset.add(dstnode);
 232           tovisit.add(dstnode);
 233         }
 234       }
 235     }
 236   }
 237
 238   void processParams(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, FlatCall fcall, boolean diff) {
 239     //Go through each temp
 240     for(int i=0;i<fcall.numArgs();i++) {
 241       TempDescriptor tmp=fcall.getArg(i);
 242       MySet<Edge> edges=diff?GraphManip.getDiffEdges(delta, tmp):GraphManip.getEdges(graph, delta, tmp);
 243       newDelta.varedgeadd.put(tmp, (MySet<Edge>) edges.clone());
 244       edgeset.addAll(edges);
 245       for(Edge e:edges) {
 246         if (!nodeset.contains(e.dst)) {
 247           nodeset.add(e.dst);
 248           tovisit.add(e.dst);
 249         }
 250       }
 251     }
 252   }
 253
 254   void computeReachableNodes(Graph graph, Delta delta, Delta newDelta, HashSet<AllocNode> nodeset, Stack<AllocNode> tovisit, MySet<Edge> edgeset, HashSet<AllocNode> oldnodeset) {
 255       while(!tovisit.isEmpty()) {
 256         AllocNode node=tovisit.pop();
 257         MySet<Edge> edges=GraphManip.getEdges(graph, delta, node);
 258         newDelta.heapedgeadd.put(node, edges);
 259         edgeset.addAll(edges);
 260         for(Edge e:edges) {
 261           if (!nodeset.contains(e.dst)&&(oldnodeset==null||!oldnodeset.contains(e.dst))) {
 262             nodeset.add(e.dst);
 263             tovisit.add(e.dst);
 264           }
 265         }
 266       }
 267   }
 268
 269   HashSet<MethodDescriptor> computeTargets(FlatCall fcall, Delta newDelta) {
 270     TempDescriptor tmpthis=fcall.getThis();
 271     MethodDescriptor md=fcall.getMethod();
 272     HashSet<MethodDescriptor> targets=new HashSet<MethodDescriptor>();
 273     if (md.isStatic()) {
 274       targets.add(md);
 275     } else {
 276       //Compute Edges
 277       for(Edge e:newDelta.varedgeadd.get(tmpthis)) {
 278         AllocNode node=e.dst;
 279         ClassDescriptor cd=node.getType().getClassDesc();
 280         //Figure out exact method called and add to set
 281         targets.add(cd.getCalledMethod(md));
 282       }
 283     }
 284     return targets;
 285   }
 286
 287   Delta processFlatCall(BBlock callblock, int callindex, FlatCall fcall, Delta delta, Graph graph) {
 288     Delta newDelta=new Delta(null, false);
 289
 290     if (delta.getInit()) {
 291       MySet<Edge> edgeset=new MySet<Edge>();
 292       HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
 293       HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
 294       Stack<AllocNode> tovisit=new Stack<AllocNode>();
 295       TempDescriptor tmpthis=fcall.getThis();
 296
 297       //Handle the this temp
 298       processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, null);
 299
 300       //Go through each temp
 301       processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, false);
 302
 303       //Traverse all reachable nodes
 304       computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, null);
 305
 306       //Compute call targets
 307       HashSet<MethodDescriptor> targets=computeTargets(fcall, newDelta);
 308
 309       //Fix mapping
 310       for(MethodDescriptor calledmd:targets) {
 311         FlatMethod fm=state.getMethodFlat(calledmd);
 312
 313         //Build tmpMap
 314         HashMap<TempDescriptor, TempDescriptor> tmpMap=new HashMap<TempDescriptor, TempDescriptor>();
 315         int offset=0;
 316         if(tmpthis!=null) {
 317           tmpMap.put(tmpthis, fm.getParameter(offset++));
 318         }
 319         for(int i=0;i<fcall.numArgs();i++) {
 320           TempDescriptor tmp=fcall.getArg(i);
 321           tmpMap.put(tmp,fm.getParameter(i+offset));
 322         }
 323
 324         //Get basicblock for the method
 325         BasicBlock block=getBBlock(fm);
 326
 327         //Build and enqueue delta
 328         Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
 329         toprocess.add(d);
 330
 331         //Hook up exits
 332         if (!callMap.containsKey(fcall)) {
 333           callMap.put(fcall, new HashSet<BBlock>());
 334         }
 335         callMap.get(fcall).add(block.getStart());
 336
 337         //If we have an existing exit, build delta
 338         Delta returnDelta=null;
 339
 340         //Hook up return
 341         if (!returnMap.containsKey(block.getExit())) {
 342           returnMap.put(block.getExit(), new HashSet<PPoint>());
 343         }
 344         returnMap.get(block.getExit()).add(new PPoint(callblock, callindex));
 345
 346         if (bbgraphMap.containsKey(block.getExit())) {
 347           //Need to push existing results to current node
 348           if (returnDelta==null) {
 349             returnDelta=new Delta(null, false);
 350             buildInitDelta(bbgraphMap.get(block.getExit()), returnDelta);
 351             if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
 352               returnDelta.setBlock(new PPoint(callblock, callindex));
 353               toprocess.add(returnDelta);
 354             }
 355           } else {
 356             if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
 357               toprocess.add(returnDelta.diffBlock(new PPoint(callblock, callindex)));
 358             }
 359           }
 360         }
 361       }
 362       graph.reachNode=nodeset;
 363       graph.reachEdge=edgeset;
 364
 365       //Apply diffs to graph
 366       applyDiffs(graph, delta);
 367     } else {
 368       MySet<Edge> edgeset=new MySet<Edge>();
 369       HashSet<AllocNode> nodeset=new HashSet<AllocNode>();
 370       MySet<Edge> oldedgeset=graph.reachEdge;
 371       HashSet<AllocNode> oldnodeset=graph.reachNode;
 372
 373       HashSet<ClassDescriptor> targetSet=new HashSet<ClassDescriptor>();
 374       Stack<AllocNode> tovisit=new Stack<AllocNode>();
 375       TempDescriptor tmpthis=fcall.getThis();
 376
 377       //Handle the this temp
 378       processThisTargets(targetSet, graph, delta, newDelta, nodeset, tovisit, edgeset, tmpthis, oldnodeset);
 379
 380       //Go through each temp
 381       processParams(graph, delta, newDelta, nodeset, tovisit, edgeset, fcall, true);
 382
 383       //Go through each new heap edge that starts from old node
 384       MySet<Edge> newedges=GraphManip.getDiffEdges(delta, oldnodeset);
 385       edgeset.addAll(newedges);
 386       for(Edge e:newedges) {
 387         if (!nodeset.contains(e.dst)&&!oldnodeset.contains(e.dst)) {
 388           nodeset.add(e.dst);
 389           tovisit.add(e.dst);
 390         }
 391       }
 392
 393       //Traverse all reachable nodes
 394       computeReachableNodes(graph, delta, newDelta, nodeset, tovisit, edgeset, oldnodeset);
 395
 396       //Compute call targets
 397       HashSet<MethodDescriptor> targets=computeTargets(fcall, newDelta);
 398
 399       //add in new nodeset and edgeset
 400       oldnodeset.addAll(nodeset);
 401       oldedgeset.addAll(edgeset);
 402       Delta basedelta=null;
 403
 404       //Fix mapping
 405       for(MethodDescriptor calledmd:targets) {
 406         FlatMethod fm=state.getMethodFlat(calledmd);
 407         boolean newmethod=false;
 408
 409         //Get basicblock for the method
 410         BasicBlock block=getBBlock(fm);
 411
 412         //Hook up exits
 413         if (!callMap.containsKey(fcall)) {
 414           callMap.put(fcall, new HashSet<BBlock>());
 415         }
 416
 417         Delta returnDelta=null;
 418
 419         if (!callMap.get(fcall).contains(block.getStart())) {
 420           callMap.get(fcall).add(block.getStart());
 421           newmethod=true;
 422
 423           //Hook up exits
 424           if (!returnMap.containsKey(block.getExit())) {
 425             returnMap.put(block.getExit(), new HashSet<PPoint>());
 426           }
 427           returnMap.get(block.getExit()).add(new PPoint(callblock, callindex));
 428
 429           if (bbgraphMap.containsKey(block.getExit())) {
 430             //Need to push existing results to current node
 431             if (returnDelta==null) {
 432               returnDelta=new Delta(null, false);
 433               buildInitDelta(bbgraphMap.get(block.getExit()), returnDelta);
 434               if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
 435                 returnDelta.setBlock(new PPoint(callblock, callindex));
 436                 toprocess.add(returnDelta);
 437               }
 438             } else {
 439               if (!returnDelta.heapedgeadd.isEmpty()||!returnDelta.heapedgeremove.isEmpty()||!returnDelta.varedgeadd.isEmpty()) {
 440                 toprocess.add(returnDelta.diffBlock(new PPoint(callblock, callindex)));
 441               }
 442             }
 443           }
 444         }
 445
 446         //Build tmpMap
 447         HashMap<TempDescriptor, TempDescriptor> tmpMap=new HashMap<TempDescriptor, TempDescriptor>();
 448         int offset=0;
 449         if(tmpthis!=null) {
 450           tmpMap.put(tmpthis, fm.getParameter(offset++));
 451         }
 452         for(int i=0;i<fcall.numArgs();i++) {
 453           TempDescriptor tmp=fcall.getArg(i);
 454           tmpMap.put(tmp,fm.getParameter(i+offset));
 455         }
 456
 457         if (newmethod) {
 458           if (basedelta==null) {
 459             basedelta=newDelta.buildBase(oldedgeset);
 460           }
 461           //Build and enqueue delta
 462           Delta d=basedelta.changeParams(tmpMap, new PPoint(block.getStart()));
 463           toprocess.add(d);
 464         } else  {
 465           //Build and enqueue delta
 466           Delta d=newDelta.changeParams(tmpMap, new PPoint(block.getStart()));
 467           toprocess.add(d);
 468         }
 469       }
 470
 471       //Apply diffs to graph
 472       applyDiffs(graph, delta);
 473     }
 474     return newDelta;
 475   }
 476
 477   void applyDiffs(Graph graph, Delta delta) {
 478     //Add hidden base edges
 479     for(Map.Entry<AllocNode, MySet<Edge>> e: delta.baseheapedge.entrySet()) {
 480       AllocNode node=e.getKey();
 481       MySet<Edge> edges=e.getValue();
 482       if (graph.nodeMap.containsKey(node)) {
 483         MySet<Edge> nodeEdges=graph.nodeMap.get(node);
 484         nodeEdges.addAll(edges);
 485       }
 486     }
 487
 488     //Remove heap edges
 489     for(Map.Entry<AllocNode, MySet<Edge>> e: delta.heapedgeremove.entrySet()) {
 490       AllocNode node=e.getKey();
 491       MySet<Edge> edgestoremove=e.getValue();
 492       if (graph.nodeMap.containsKey(node)) {
 493         //Just apply diff to current map
 494         graph.nodeMap.get(node).removeAll(edgestoremove);
 495       } else {
 496         //Generate diff from parent graph
 497         MySet<Edge> parentedges=graph.parent.nodeMap.get(node);
 498         MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
 499         graph.nodeMap.put(node, newedgeset);
 500       }
 501     }
 502
 503     //Add heap edges
 504     for(Map.Entry<AllocNode, MySet<Edge>> e: delta.heapedgeadd.entrySet()) {
 505       AllocNode node=e.getKey();
 506       MySet<Edge> edgestoadd=e.getValue();
 507       //If we have not done a subtract, then
 508       if (!graph.nodeMap.containsKey(node)) {
 509         //Copy the parent entry
 510         graph.nodeMap.put(node, (MySet<Edge>)graph.parent.nodeMap.get(node).clone());
 511       }
 512       graph.nodeMap.get(node).addAll(edgestoadd);
 513     }
 514
 515     //Remove var edges
 516     for(Map.Entry<TempDescriptor, MySet<Edge>> e: delta.varedgeremove.entrySet()) {
 517       TempDescriptor tmp=e.getKey();
 518       MySet<Edge> edgestoremove=e.getValue();
 519
 520       if (graph.varMap.containsKey(tmp)) {
 521         //Just apply diff to current map
 522         graph.varMap.get(tmp).removeAll(edgestoremove);
 523       } else {
 524         //Generate diff from parent graph
 525         MySet<Edge> parentedges=graph.parent.varMap.get(tmp);
 526         MySet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
 527         graph.varMap.put(tmp, newedgeset);
 528       }
 529     }
 530
 531     //Add var edges
 532     for(Map.Entry<TempDescriptor, MySet<Edge>> e: delta.varedgeadd.entrySet()) {
 533       TempDescriptor tmp=e.getKey();
 534       MySet<Edge> edgestoadd=e.getValue();
 535       graph.varMap.put(tmp, (MySet<Edge>) edgestoadd.clone());
 536     }
 537
 538     //Add node additions
 539     for(AllocNode node:delta.addNodeAges) {
 540       graph.nodeAges.add(node);
 541     }
 542   }
 543
 544   Delta processSetFieldElementNode(FlatNode node, Delta delta, Graph graph) {
 545     TempDescriptor src;
 546     FieldDescriptor fd;
 547     TempDescriptor dst;
 548     if (node.kind()==FKind.FlatSetElementNode) {
 549       FlatSetElementNode fen=(FlatSetElementNode) node;
 550       src=fen.getSrc();
 551       fd=null;
 552       dst=fen.getDst();
 553     } else {
 554       FlatSetFieldNode ffn=(FlatSetFieldNode) node;
 555       src=ffn.getSrc();
 556       fd=ffn.getField();
 557       dst=ffn.getDst();
 558     }
 559     if (delta.getInit()) {
 560       HashSet<AllocNode> srcNodes=GraphManip.getNodes(graph, delta, src);
 561       HashSet<AllocNode> dstNodes=GraphManip.getNodes(graph, delta, dst);
 562       MySet<Edge> edgesToAdd=GraphManip.genEdges(srcNodes, fd, dstNodes);
 563       MySet<Edge> edgesToRemove=null;
 564       if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()) {
 565         /* Can do a strong update */
 566         edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
 567       }
 568       /* Update diff */
 569       updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
 570       applyDiffs(graph, delta);
 571     } else {
 572       /* First look at new sources */
 573       MySet<Edge> edgesToAdd=new MySet<Edge>();
 574       HashSet<AllocNode> newSrcNodes=GraphManip.getDiffNodes(delta, src);
 575       HashSet<AllocNode> dstNodes=GraphManip.getDiffNodes(delta, dst);
 576       edgesToAdd.addAll(GraphManip.genEdges(newSrcNodes, fd, dstNodes));
 577       HashSet<AllocNode> newDstNodes=GraphManip.getDiffNodes(delta, dst);
 578       MySet<Edge> edgesToRemove=null;
 579       if (newDstNodes.size()!=0) {
 580         if (dstNodes.size()==1&&!dstNodes.iterator().next().isSummary()) {
 581           /* Need to undo strong update */
 582           if (graph.strongUpdateSet!=null) {
 583             edgesToAdd.addAll(graph.strongUpdateSet);
 584             graph.strongUpdateSet.clear();
 585           }
 586         } else if (dstNodes.size()==0&&newDstNodes.size()==1&&!newDstNodes.iterator().next().isSummary()&&graph.strongUpdateSet==null) {
 587           edgesToRemove=GraphManip.getEdges(graph, delta, dstNodes, fd);
 588         }
 589         HashSet<AllocNode> srcNodes=GraphManip.getDiffNodes(delta, src);
 590         edgesToAdd.addAll(GraphManip.genEdges(srcNodes, fd, newDstNodes));
 591       }
 592       /* Update diff */
 593       updateHeapDelta(graph, delta, edgesToAdd, edgesToRemove);
 594       applyDiffs(graph, delta);
 595     }
 596     return delta;
 597   }
 598
 599   Delta processCopyNode(FlatNode node, Delta delta, Graph graph) {
 600     TempDescriptor src;
 601     TempDescriptor dst;
 602     if (node.kind()==FKind.FlatOpNode) {
 603       FlatOpNode fon=(FlatOpNode) node;
 604       src=fon.getLeft();
 605       dst=fon.getDest();
 606     } else if (node.kind()==FKind.FlatReturnNode) {
 607       FlatReturnNode frn=(FlatReturnNode)node;
 608       src=frn.getReturnTemp();
 609       dst=returntmp;
 610     } else {
 611       FlatCastNode fcn=(FlatCastNode) node;
 612       src=fcn.getSrc();
 613       dst=fcn.getDst();
 614     }
 615     if (delta.getInit()) {
 616       HashSet<AllocNode> srcnodes=GraphManip.getNodes(graph, delta, src);
 617       MySet<Edge> edgesToAdd=GraphManip.genEdges(src, srcnodes);
 618       MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
 619       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
 620       applyDiffs(graph, delta);
 621     } else {
 622       /* First compute new src nodes */
 623       HashSet<AllocNode> newSrcNodes=GraphManip.getDiffNodes(delta, src);
 624
 625       /* Compute the union, and then the set of edges */
 626       MySet<Edge> edgesToAdd=GraphManip.genEdges(src, newSrcNodes);
 627
 628       /* Compute set of edges to remove */
 629       MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
 630
 631       /* Update diff */
 632       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
 633       applyDiffs(graph, delta);
 634     }
 635     return delta;
 636   }
 637
 638   Delta processFieldElementNode(FlatNode node, Delta delta, Graph graph) {
 639     TempDescriptor src;
 640     FieldDescriptor fd;
 641     TempDescriptor dst;
 642     if (node.kind()==FKind.FlatElementNode) {
 643       FlatElementNode fen=(FlatElementNode) node;
 644       src=fen.getSrc();
 645       fd=null;
 646       dst=fen.getDst();
 647     } else {
 648       FlatFieldNode ffn=(FlatFieldNode) node;
 649       src=ffn.getSrc();
 650       fd=ffn.getField();
 651       dst=ffn.getDst();
 652     }
 653     if (delta.getInit()) {
 654       HashSet<AllocNode> srcnodes=GraphManip.getNodes(graph, delta, src);
 655       HashSet<AllocNode> fdnodes=GraphManip.getNodes(graph, delta, srcnodes, fd);
 656       MySet<Edge> edgesToAdd=GraphManip.genEdges(src, fdnodes);
 657       MySet<Edge> edgesToRemove=GraphManip.getEdges(graph, delta, dst);
 658       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
 659       applyDiffs(graph, delta);
 660     } else {
 661       /* First compute new objects we read fields of */
 662       HashSet<AllocNode> allsrcnodes=GraphManip.getNodes(graph, delta, src);
 663       HashSet<AllocNode> difffdnodes=GraphManip.getDiffNodes(delta, allsrcnodes, fd);
 664       /* Next compute new targets of fields */
 665       HashSet<AllocNode> newsrcnodes=GraphManip.getDiffNodes(delta, src);
 666       HashSet<AllocNode> newfdnodes=GraphManip.getNodes(graph, delta, newsrcnodes, fd);
 667       /* Compute the union, and then the set of edges */
 668       HashSet<AllocNode> newTargets=new HashSet<AllocNode>();
 669       newTargets.addAll(newfdnodes);
 670       newTargets.addAll(difffdnodes);
 671       MySet<Edge> edgesToAdd=GraphManip.genEdges(src, newTargets);
 672
 673       /* Compute set of edges to remove */
 674       MySet<Edge> edgesToRemove=GraphManip.getDiffEdges(delta, dst);
 675
 676       /* Update diff */
 677       updateVarDelta(graph, delta, dst, edgesToAdd, edgesToRemove);
 678       applyDiffs(graph, delta);
 679     }
 680     return delta;
 681   }
 682
 683   static void updateVarDelta(Graph graph, Delta delta, TempDescriptor tmp, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
 684     MySet<Edge> edgeAdd=delta.varedgeadd.get(tmp);
 685     MySet<Edge> edgeRemove=delta.varedgeremove.get(tmp);
 686     MySet<Edge> existingEdges=graph.getEdges(tmp);
 687     for(Edge e: edgestoRemove) {
 688       //remove edge from delta
 689       edgeAdd.remove(e);
 690       //if the edge is already in the graph, add an explicit remove to the delta
 691       if (existingEdges.contains(e))
 692         edgeRemove.add(e);
 693     }
 694     for(Edge e: edgestoAdd) {
 695       //Remove the edge from the remove set
 696       edgeRemove.remove(e);
 697       //Explicitly add it to the add set unless it is already in the graph
 698       if (!existingEdges.contains(e))
 699         edgeAdd.add(e);
 700     }
 701   }
 702
 703   static void updateHeapDelta(Graph graph, Delta delta, MySet<Edge> edgestoAdd, MySet<Edge> edgestoRemove) {
 704     for(Edge e: edgestoRemove) {
 705       AllocNode src=e.src;
 706       MySet<Edge> edgeAdd=delta.heapedgeadd.get(src);
 707       MySet<Edge> existingEdges=graph.getEdges(src);
 708       //remove edge from delta
 709       edgeAdd.remove(e);
 710       //if the edge is already in the graph, add an explicit remove to the delta
 711       if (existingEdges.contains(e)) {
 712         MySet<Edge> edgeRemove=delta.heapedgeremove.get(src);
 713         edgeRemove.add(e);
 714       }
 715     }
 716     for(Edge e: edgestoAdd) {
 717       AllocNode src=e.src;
 718       MySet<Edge> edgeRemove=delta.heapedgeremove.get(src);
 719       MySet<Edge> existingEdges=graph.getEdges(src);
 720       //Remove the edge from the remove set
 721       edgeRemove.remove(e);
 722       //Explicitly add it to the add set unless it is already in the graph
 723       if (!existingEdges.contains(e)) {
 724         MySet<Edge> edgeAdd=delta.heapedgeadd.get(src);
 725         edgeAdd.add(e);
 726       }
 727     }
 728   }
 729
 730   Delta processFlatNop(FlatNode node, Delta delta, Graph graph) {
 731     applyDiffs(graph, delta);
 732     return delta;
 733   }
 734
 735   Delta processNewNode(FlatNew node, Delta delta, Graph graph) {
 736     AllocNode summary=allocFactory.getAllocNode(node, true);
 737     AllocNode single=allocFactory.getAllocNode(node, false);
 738     TempDescriptor tmp=node.getDst();
 739
 740     if (delta.getInit()) {
 741       /* We don't have to deal with summarization here...  The
 742        * intuition is that this is the only place where we generate
 743        * nodes for this allocation site and this is the first time
 744        * we've analyzed this site */
 745
 746       //Build new Edge
 747       Edge e=new Edge(tmp, single);
 748       //Build new Edge set
 749       MySet<Edge> newedges=new MySet<Edge>();
 750       newedges.add(e);
 751       //Add it into the diffs
 752       delta.varedgeadd.put(tmp, newedges);
 753       //Remove the old edges
 754       delta.varedgeremove.put(tmp, graph.getEdges(tmp));
 755       //Apply incoming diffs to graph
 756       applyDiffs(graph, delta);
 757       //Note that we create a single node
 758       delta.addNodeAges.add(single);
 759     } else {
 760       /* 1. Fix up the variable edge additions */
 761
 762       for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.varedgeadd.entrySet().iterator();entryIt.hasNext();) {
 763         Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
 764
 765         if (entry.getKey()==tmp) {
 766           /* Check if this is the tmp we overwrite */
 767           entryIt.remove();
 768         } else {
 769           /* Otherwise, check if the target of the edge is changed... */
 770           summarizeSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary);
 771         }
 772       }
 773
 774       /* 2. Fix up the base variable edges */
 775
 776       for(Iterator<Map.Entry<TempDescriptor, MySet<Edge>>> entryIt=delta.basevaredge.entrySet().iterator();entryIt.hasNext();) {
 777         Map.Entry<TempDescriptor, MySet<Edge>> entry=entryIt.next();
 778         TempDescriptor entrytmp=entry.getKey();
 779         if (entrytmp==tmp) {
 780           /* Check is this is the tmp we overwrite, if so add to remove set */
 781           Util.relationUpdate(delta.varedgeremove, tmp, null, entry.getValue());
 782         } else {
 783           /* Check if the target of the edge is changed */
 784           MySet<Edge> newset=(MySet<Edge>)entry.getValue().clone();
 785           MySet<Edge> removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary);
 786           Util.relationUpdate(delta.varedgeremove, entrytmp, newset, removeset);
 787           Util.relationUpdate(delta.varedgeadd, entrytmp, null, newset);
 788         }
 789       }
 790
 791
 792       /* 3. Fix up heap edge additions */
 793
 794       HashMap<AllocNode, MySet<Edge>> addheapedge=new HashMap<AllocNode, MySet<Edge>>();
 795       for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.heapedgeadd.entrySet().iterator();entryIt.hasNext();) {
 796         Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
 797         MySet<Edge> edgeset=entry.getValue();
 798         AllocNode allocnode=entry.getKey();
 799         if (allocnode==single) {
 800           entryIt.remove();
 801           summarizeSet(edgeset, graph.nodeMap.get(summary), single, summary);
 802           addheapedge.put(summary, edgeset);
 803         } else {
 804           summarizeSet(edgeset, graph.nodeMap.get(allocnode), single, summary);
 805         }
 806       }
 807
 808       /* Merge in diffs */
 809
 810       for(Map.Entry<AllocNode, MySet<Edge>> entry:addheapedge.entrySet()) {
 811         AllocNode allocnode=entry.getKey();
 812         Util.relationUpdate(delta.heapedgeadd, allocnode, null, entry.getValue());
 813       }
 814
 815       /* 4. Fix up the base heap edges */
 816
 817       for(Iterator<Map.Entry<AllocNode, MySet<Edge>>> entryIt=delta.baseheapedge.entrySet().iterator();entryIt.hasNext();) {
 818         Map.Entry<AllocNode, MySet<Edge>> entry=entryIt.next();
 819         MySet<Edge> edgeset=entry.getValue();
 820         AllocNode allocnode=entry.getKey();
 821         if (allocnode==single) {
 822           entryIt.remove();
 823         }
 824         AllocNode addnode=(allocnode==single)?summary:allocnode;
 825
 826         MySet<Edge> newset=(MySet<Edge>) edgeset.clone();
 827         MySet<Edge> removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary);
 828         Util.relationUpdate(delta.heapedgeadd, addnode, null, newset);
 829         Util.relationUpdate(delta.heapedgeremove, allocnode, null, removeset);
 830       }
 831
 832       /* Update Node Ages...If the base or addNodeAges set contains a
 833        * single node, it now should also contain a summary node...  No
 834        * need to generate a single node as that has already been
 835        * done. */
 836       if (delta.baseNodeAges.contains(single)||delta.addNodeAges.contains(single)) {
 837         delta.addNodeAges.add(summary);
 838       }
 839
 840       //Apply incoming diffs to graph
 841       applyDiffs(graph, delta);
 842     }
 843     return delta;
 844   }
 845
 846   /* This function builds a new edge set where oldnode is summarized into new node */
 847
 848   void summarizeSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode sumnode) {
 849     MySet<Edge> newSet=null;
 850     for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
 851       Edge e=edgeit.next();
 852       if (e.dst==oldnode||e.src==oldnode) {
 853         if (newSet==null) {
 854           newSet=new MySet<Edge>();
 855         }
 856         edgeit.remove();
 857         e=e.copy();
 858
 859         if (e.dst==oldnode) {
 860           e.dst=sumnode;
 861         }
 862         if (e.src==oldnode) {
 863           e.src=sumnode;
 864         }
 865         if (oldedgeset==null||!oldedgeset.contains(e))
 866           newSet.add(e);
 867       }
 868     }
 869     if (newSet!=null)
 870       edgeset.addAll(newSet);
 871   }
 872
 873   /* Shrinks the incoming set to just include rewritten values.
 874    * Returns a set of the original rewritten values */
 875
 876   MySet<Edge> shrinkSet(MySet<Edge> edgeset, MySet<Edge> oldedgeset, AllocNode oldnode, AllocNode newnode) {
 877     MySet<Edge> newSet=null;
 878     MySet<Edge> removeSet=null;
 879     for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
 880       Edge e=edgeit.next();
 881       edgeit.remove();
 882       if (e.dst==oldnode||e.src==oldnode) {
 883         if (newSet==null) {
 884           newSet=new MySet<Edge>();
 885           removeSet=new MySet<Edge>();
 886         }
 887
 888         removeSet.add(e.copy());
 889         if (e.dst==oldnode)
 890           e.dst=newnode;
 891         if (e.src==oldnode)
 892           e.src=newnode;
 893         if (oldedgeset==null||!oldedgeset.contains(e))
 894           newSet.add(e);
 895       }
 896     }
 897     if (newSet!=null)
 898       edgeset.addAll(newSet);
 899     return removeSet;
 900   }
 901
 902   /* This function returns a completely new Delta...  It is safe to
 903    * modify this */
 904
 905   Delta applyInitDelta(Delta delta, BBlock block) {
 906     //Apply delta to graph
 907     boolean newGraph=false;
 908     if (!bbgraphMap.containsKey(block)) {
 909       bbgraphMap.put(block, new Graph(null));
 910       newGraph=true;
 911     }
 912     Delta newdelta;
 913     Graph graph=bbgraphMap.get(block);
 914
 915     if (newGraph) {
 916       newdelta=new Delta(null, true);
 917       //Add in heap edges and throw away original diff
 918       graph.nodeMap.putAll(delta.heapedgeadd);
 919       //Add in var edges and throw away original diff
 920       graph.varMap.putAll(delta.varedgeadd);
 921       //Record that this is initial set...
 922       graph.nodeAges.addAll(delta.addNodeAges);
 923     } else {
 924       newdelta=new Delta(null, false);
 925       //merge in heap edges and variables
 926       mergeHeapEdges(graph, delta, newdelta);
 927       mergeVarEdges(graph, delta, newdelta);
 928       mergeAges(graph, delta, newdelta);
 929     }
 930     return newdelta;
 931   }
 932
 933   /* This function merges in the heap edges.  It updates delta to be
 934    * the difference */
 935
 936   void mergeHeapEdges(Graph graph, Delta delta, Delta newdelta) {
 937     //Merge in edges
 938     for(Map.Entry<AllocNode, MySet<Edge>> heapedge:delta.heapedgeadd.entrySet()) {
 939       AllocNode nsrc=heapedge.getKey();
 940       MySet<Edge> edges=heapedge.getValue();
 941       if (!graph.nodeMap.containsKey(nsrc)) {
 942         graph.nodeMap.put(nsrc, new MySet<Edge>());
 943       }
 944       MySet<Edge> dstedges=graph.nodeMap.get(nsrc);
 945       MySet<Edge> diffedges=new MySet<Edge>();
 946       for(Edge e:edges) {
 947         if (!dstedges.contains(e)) {
 948           //We have a new edge
 949           diffedges.add(e);
 950           dstedges.add(e);
 951         }
 952       }
 953       //Done with edge set...
 954       if (diffedges.size()>0) {
 955         //completely new
 956         newdelta.baseheapedge.put(nsrc, diffedges);
 957       }
 958     }
 959   }
 960
 961   /* This function merges in the var edges.  It updates delta to be
 962    * the difference */
 963
 964   void mergeVarEdges(Graph graph, Delta delta, Delta newdelta) {
 965     //Merge in edges
 966     for(Map.Entry<TempDescriptor, MySet<Edge>> varedge:delta.varedgeadd.entrySet()) {
 967       TempDescriptor tmpsrc=varedge.getKey();
 968       MySet<Edge> edges=varedge.getValue();
 969       if (!graph.varMap.containsKey(tmpsrc)) {
 970         graph.varMap.put(tmpsrc, new MySet<Edge>());
 971       }
 972       MySet<Edge> dstedges=graph.varMap.get(tmpsrc);
 973       MySet<Edge> diffedges=new MySet<Edge>();
 974       for(Edge e:edges) {
 975         if (!dstedges.contains(e)) {
 976           //We have a new edge
 977           diffedges.add(e);
 978           dstedges.add(e);
 979         }
 980       }
 981       //Done with edge set...
 982       if (diffedges.size()>=0) {
 983         //completely new
 984         newdelta.basevaredge.put(tmpsrc,diffedges);
 985       }
 986     }
 987   }
 988
 989   void mergeAges(Graph graph, Delta delta, Delta newDelta) {
 990     //Merge in edges
 991     for(AllocNode node:delta.addNodeAges) {
 992       if (!graph.nodeAges.contains(node)) {
 993         graph.nodeAges.add(node);
 994         newDelta.baseNodeAges.add(node);
 995       }
 996     }
 997   }
 998 }