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   State state;
  13   TypeUtil typeUtil;
  14   AllocFactory allocFactory;
  15   LinkedList<Delta> toprocess;
  16
  17   public Pointer(State state, TypeUtil typeUtil) {
  18     this.state=state;
  19     this.blockMap=new HashMap<FlatMethod, BasicBlock>();
  20     this.bbgraphMap=new HashMap<BBlock, Graph>();
  21     this.graphMap=new HashMap<FlatNode, Graph>();
  22     this.typeUtil=typeUtil;
  23     this.allocFactory=new AllocFactory(state, typeUtil);
  24     this.toprocess=new LinkedList<Delta>();
  25   }
  26
  27   public BasicBlock getBBlock(FlatMethod fm) {
  28     if (!blockMap.containsKey(fm))
  29       blockMap.put(fm, BasicBlock.getBBlock(fm));
  30     return blockMap.get(fm);
  31   }
  32
  33   Delta buildInitialContext() {
  34     MethodDescriptor md=typeUtil.getMain();
  35     FlatMethod fm=state.getMethodFlat(md);
  36     BasicBlock bb=getBBlock(fm);
  37     BBlock start=bb.getStart();
  38     Delta delta=new Delta(start, true);
  39     HashSet<Edge> arrayset=new HashSet<Edge>();
  40     HashSet<Edge> varset=new HashSet<Edge>();
  41     arrayset.add(new Edge(allocFactory.StringArray, null, allocFactory.Strings));
  42     varset.add(new Edge(fm.getParameter(0), allocFactory.StringArray));
  43     delta.heapedgeadd.put(allocFactory.StringArray, arrayset);
  44     delta.varedgeadd.put(fm.getParameter(0), varset);
  45     return delta;
  46   }
  47
  48   void doAnalysis() {
  49     toprocess.add(buildInitialContext());
  50
  51     while(!toprocess.isEmpty()) {
  52       Delta delta=toprocess.remove();
  53       BBlock bblock=delta.getBlock();
  54       Vector<FlatNode> nodes=bblock.nodes();
  55
  56       //Build base graph for entrance to this basic block
  57       delta=applyInitDelta(delta, bblock);
  58       Graph graph=bbgraphMap.get(bblock);
  59
  60       //Compute delta at exit of each node
  61       for(int i=0; i<nodes.size();i++) {
  62         FlatNode currNode=nodes.get(i);
  63         if (!graphMap.containsKey(currNode)) {
  64           graphMap.put(currNode, new Graph(graph));
  65         }
  66         Graph nodeGraph=graphMap.get(currNode);
  67         delta=processNode(currNode, delta, nodeGraph);
  68       }
  69       //XXXX: Need to generate new delta
  70     }
  71   }
  72
  73   Delta processNode(FlatNode node, Delta delta, Graph newgraph) {
  74     switch(node.kind()) {
  75     case FKind.FlatNew:
  76       return processNewNode((FlatNew)node, delta, newgraph);
  77     case FKind.FlatFieldNode:
  78       return processFieldNode((FlatFieldNode)node, delta, newgraph);
  79     case FKind.FlatCall:
  80     case FKind.FlatSetFieldNode:
  81     case FKind.FlatReturnNode:
  82     case FKind.FlatElementNode:
  83     case FKind.FlatSetElementNode:
  84     case FKind.FlatMethod:
  85     case FKind.FlatExit:
  86     case FKind.FlatSESEEnterNode:
  87     case FKind.FlatSESEExitNode:
  88     case FKind.FlatCastNode:
  89     case FKind.FlatOpNode:
  90       throw new Error("Unimplemented node:"+node);
  91     default:
  92       throw new Error("Unrecognized node:"+node);
  93     }
  94   }
  95
  96   void applyDiffs(Graph graph, Delta delta) {
  97     //Add hidden base edges
  98     for(Map.Entry<AllocNode, HashSet<Edge>> e: delta.baseheapedge.entrySet()) {
  99       AllocNode node=e.getKey();
 100       HashSet<Edge> edges=e.getValue();
 101       if (graph.nodeMap.containsKey(node)) {
 102         HashSet<Edge> nodeEdges=graph.nodeMap.get(node);
 103         nodeEdges.addAll(edges);
 104       }
 105     }
 106
 107     //Remove heap edges
 108     for(Map.Entry<AllocNode, HashSet<Edge>> e: delta.heapedgeremove.entrySet()) {
 109       AllocNode node=e.getKey();
 110       HashSet<Edge> edgestoremove=e.getValue();
 111       if (graph.nodeMap.containsKey(node)) {
 112         //Just apply diff to current map
 113         graph.nodeMap.get(node).removeAll(edgestoremove);
 114       } else {
 115         //Generate diff from parent graph
 116         HashSet<Edge> parentedges=graph.parent.nodeMap.get(node);
 117         HashSet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
 118         graph.nodeMap.put(node, newedgeset);
 119       }
 120     }
 121
 122     //Add heap edges
 123     for(Map.Entry<AllocNode, HashSet<Edge>> e: delta.heapedgeadd.entrySet()) {
 124       AllocNode node=e.getKey();
 125       HashSet<Edge> edgestoadd=e.getValue();
 126       //If we have not done a subtract, then
 127       if (!graph.nodeMap.containsKey(node)) {
 128         //Copy the parent entry
 129         graph.nodeMap.put(node, (HashSet<Edge>)graph.parent.nodeMap.get(node).clone());
 130       }
 131       graph.nodeMap.get(node).addAll(edgestoadd);
 132     }
 133
 134     //Remove var edges
 135     for(Map.Entry<TempDescriptor, HashSet<Edge>> e: delta.varedgeremove.entrySet()) {
 136       TempDescriptor tmp=e.getKey();
 137       HashSet<Edge> edgestoremove=e.getValue();
 138
 139       if (graph.varMap.containsKey(tmp)) {
 140         //Just apply diff to current map
 141         graph.varMap.get(tmp).removeAll(edgestoremove);
 142       } else {
 143         //Generate diff from parent graph
 144         HashSet<Edge> parentedges=graph.parent.varMap.get(tmp);
 145         HashSet<Edge> newedgeset=Util.setSubtract(parentedges, edgestoremove);
 146         graph.varMap.put(tmp, newedgeset);
 147       }
 148     }
 149
 150     //Add var edges
 151     for(Map.Entry<TempDescriptor, HashSet<Edge>> e: delta.varedgeadd.entrySet()) {
 152       TempDescriptor tmp=e.getKey();
 153       HashSet<Edge> edgestoadd=e.getValue();
 154       graph.varMap.put(tmp, (HashSet<Edge>) edgestoadd.clone());
 155     }
 156   }
 157
 158   HashSet<AllocNode> getTemps(Graph graph, Delta delta, TempDescriptor tmp) {
 159     HashSet<AllocNode> nodes=new HashSet<AllocNode>();
 160     HashSet<Edge> removeedges=delta.varedgeremove.get(tmp);
 161
 162     for(Edge e:graph.getEdges(tmp)) {
 163       if (removeedges==null||!removeedges.contains(e))
 164         nodes.add(e.dst);
 165     }
 166     if (delta.varedgeadd.containsKey(tmp))
 167       for(Edge e:delta.varedgeadd.get(tmp)) {
 168         nodes.add(e.dst);
 169       }
 170     return nodes;
 171   }
 172
 173   Delta processFieldNode(FlatFieldNode node, Delta delta, Graph graph) {
 174     TempDescriptor src=node.getSrc();
 175     FieldDescriptor fd=node.getField();
 176     TempDescriptor dst=node.getDst();
 177     if (delta.getInit()) {
 178       HashSet<AllocNode> nodes=getTemps(graph, delta, src);
 179
 180
 181       applyDiffs(graph, delta);
 182     } else {
 183
 184     }
 185     return delta;
 186   }
 187
 188   Delta processNewNode(FlatNew node, Delta delta, Graph graph) {
 189     AllocNode summary=allocFactory.getAllocNode(node, true);
 190     AllocNode single=allocFactory.getAllocNode(node, false);
 191     TempDescriptor tmp=node.getDst();
 192
 193     if (delta.getInit()) {
 194       //Build new Edge
 195       Edge e=new Edge(tmp, single);
 196       //Build new Edge set
 197       HashSet<Edge> newedges=new HashSet<Edge>();
 198       newedges.add(e);
 199       //Add it into the diffs
 200       delta.varedgeadd.put(tmp, newedges);
 201       //Remove the old edges
 202       delta.varedgeremove.put(tmp, graph.getEdges(tmp));
 203       //Apply incoming diffs to graph
 204       applyDiffs(graph, delta);
 205     } else {
 206       /* 1. Fix up the variable edge additions */
 207
 208       for(Iterator<Map.Entry<TempDescriptor, HashSet<Edge>>> entryIt=delta.varedgeadd.entrySet().iterator();entryIt.hasNext();) {
 209         Map.Entry<TempDescriptor, HashSet<Edge>> entry=entryIt.next();
 210
 211         if (entry.getKey()==tmp) {
 212           /* Check if this is the tmp we overwrite */
 213           entryIt.remove();
 214         } else {
 215           /* Otherwise, check if the target of the edge is changed... */
 216           rewriteSet(entry.getValue(), graph.varMap.get(entry.getKey()), single, summary);
 217         }
 218       }
 219
 220       /* 2. Fix up the base variable edges */
 221
 222       for(Iterator<Map.Entry<TempDescriptor, HashSet<Edge>>> entryIt=delta.basevaredge.entrySet().iterator();entryIt.hasNext();) {
 223         Map.Entry<TempDescriptor, HashSet<Edge>> entry=entryIt.next();
 224         TempDescriptor entrytmp=entry.getKey();
 225         if (entrytmp==tmp) {
 226           /* Check is this is the tmp we overwrite, if so add to remove set */
 227           if (delta.varedgeremove.containsKey(tmp))
 228             delta.varedgeremove.get(tmp).addAll(entry.getValue());
 229           else
 230             delta.varedgeremove.put(tmp, entry.getValue());
 231         } else {
 232           /* Check if the target of the edge is changed */
 233           HashSet<Edge> newset=(HashSet<Edge>)entry.getValue().clone();
 234           HashSet<Edge> removeset=shrinkSet(newset, graph.varMap.get(entrytmp), single, summary);
 235           if (delta.varedgeremove.containsKey(entrytmp)) {
 236             /* Make sure we do not remove the newly created edges. */
 237             delta.varedgeremove.get(entrytmp).removeAll(newset);
 238             /* Remove the old edges to the single node */
 239             delta.varedgeremove.get(entrytmp).addAll(removeset);
 240           } else {
 241             /* Remove the old edges to the single node */
 242             delta.varedgeremove.put(entrytmp, removeset);
 243           }
 244           if (delta.varedgeadd.containsKey(entrytmp)) {
 245             /* Create the new edges */
 246             delta.varedgeadd.get(entrytmp).addAll(newset);
 247           } else {
 248             /* Create the new edges */
 249             delta.varedgeadd.put(entrytmp, newset);
 250           }
 251         }
 252       }
 253
 254
 255       /* 3. Fix up heap edge additions */
 256
 257       HashMap<AllocNode, HashSet<Edge>> addheapedge=new HashMap<AllocNode, HashSet<Edge>>();
 258       for(Iterator<Map.Entry<AllocNode, HashSet<Edge>>> entryIt=delta.heapedgeadd.entrySet().iterator();entryIt.hasNext();) {
 259         Map.Entry<AllocNode, HashSet<Edge>> entry=entryIt.next();
 260         HashSet<Edge> edgeset=entry.getValue();
 261         AllocNode allocnode=entry.getKey();
 262         if (allocnode==single) {
 263           entryIt.remove();
 264           rewriteSet(edgeset, graph.nodeMap.get(summary), single, summary);
 265           addheapedge.put(summary, edgeset);
 266         } else {
 267           rewriteSet(edgeset, graph.nodeMap.get(allocnode), single, summary);
 268         }
 269       }
 270
 271       /* Merge in diffs */
 272
 273       for(Map.Entry<AllocNode, HashSet<Edge>> entry:addheapedge.entrySet()) {
 274         AllocNode allocnode=entry.getKey();
 275         if (delta.heapedgeadd.containsKey(allocnode)) {
 276           delta.heapedgeadd.get(allocnode).addAll(entry.getValue());
 277         } else {
 278           delta.heapedgeadd.put(allocnode, entry.getValue());
 279         }
 280       }
 281
 282       /* 4. Fix up the base heap edges */
 283
 284       for(Iterator<Map.Entry<AllocNode, HashSet<Edge>>> entryIt=delta.baseheapedge.entrySet().iterator();entryIt.hasNext();) {
 285         Map.Entry<AllocNode, HashSet<Edge>> entry=entryIt.next();
 286         HashSet<Edge> edgeset=entry.getValue();
 287         AllocNode allocnode=entry.getKey();
 288         if (allocnode==single) {
 289           entryIt.remove();
 290         }
 291         AllocNode addnode=(allocnode==single)?summary:allocnode;
 292
 293         HashSet<Edge> newset=(HashSet<Edge>) edgeset.clone();
 294         HashSet<Edge> removeset=shrinkSet(newset, graph.nodeMap.get(addnode), single, summary);
 295         if (delta.heapedgeadd.containsKey(addnode)) {
 296           delta.heapedgeadd.get(addnode).addAll(newset);
 297         } else {
 298           delta.heapedgeadd.put(addnode, newset);
 299         }
 300         if (delta.heapedgeremove.containsKey(allocnode)) {
 301           delta.heapedgeremove.get(allocnode).addAll(removeset);
 302         } else {
 303           delta.heapedgeremove.put(allocnode, removeset);
 304         }
 305       }
 306
 307       //Apply incoming diffs to graph
 308       applyDiffs(graph, delta);
 309     }
 310     return delta;
 311   }
 312
 313   void rewriteSet(HashSet<Edge> edgeset, HashSet<Edge> oldedgeset, AllocNode oldnode, AllocNode newnode) {
 314     HashSet<Edge> newSet=null;
 315     for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
 316       Edge e=edgeit.next();
 317       if (e.dst==oldnode||e.src==oldnode) {
 318         if (newSet==null) {
 319           newSet=new HashSet<Edge>();
 320         }
 321         edgeit.remove();
 322         if (e.dst==oldnode)
 323           e.dst=newnode;
 324         if (e.src==oldnode)
 325           e.src=newnode;
 326         if (oldedgeset==null||!oldedgeset.contains(e))
 327           newSet.add(e);
 328       }
 329     }
 330     if (newSet!=null)
 331       edgeset.addAll(newSet);
 332   }
 333
 334   /* Shrinks the incoming set to just include rewritten values.
 335    * Returns a set of the original rewritten values */
 336
 337   HashSet<Edge> shrinkSet(HashSet<Edge> edgeset, HashSet<Edge> oldedgeset, AllocNode oldnode, AllocNode newnode) {
 338     HashSet<Edge> newSet=null;
 339     HashSet<Edge> removeSet=null;
 340     for(Iterator<Edge> edgeit=edgeset.iterator();edgeit.hasNext();) {
 341       Edge e=edgeit.next();
 342       edgeit.remove();
 343       if (e.dst==oldnode||e.src==oldnode) {
 344         if (newSet==null) {
 345           newSet=new HashSet<Edge>();
 346           removeSet=new HashSet<Edge>();
 347         }
 348
 349         removeSet.add(e.copy());
 350         if (e.dst==oldnode)
 351           e.dst=newnode;
 352         if (e.src==oldnode)
 353           e.src=newnode;
 354         if (oldedgeset==null||!oldedgeset.contains(e))
 355           newSet.add(e);
 356       }
 357     }
 358     if (newSet!=null)
 359       edgeset.addAll(newSet);
 360     return removeSet;
 361   }
 362
 363   Delta applyInitDelta(Delta delta, BBlock block) {
 364     //Apply delta to graph
 365     boolean newGraph=false;
 366     if (!bbgraphMap.containsKey(block)) {
 367       bbgraphMap.put(block, new Graph(null));
 368       newGraph=true;
 369     }
 370     Delta newdelta;
 371     Graph graph=bbgraphMap.get(block);
 372
 373     if (newGraph) {
 374       newdelta=new Delta(null, true);
 375       //Add in heap edges and throw away original diff
 376       graph.nodeMap.putAll(delta.heapedgeadd);
 377       //Add in var edges and throw away original diff
 378       graph.varMap.putAll(delta.varedgeadd);
 379       //Record that this is initial set...
 380     } else {
 381       newdelta=new Delta(null, false);
 382       //merge in heap edges and variables
 383       mergeHeapEdges(graph, delta, newdelta);
 384       mergeVarEdges(graph, delta, newdelta);
 385       //Record that this is a diff
 386       newdelta.setInit(false);
 387     }
 388     return newdelta;
 389   }
 390
 391   /* This function merges in the heap edges.  It updates delta to be
 392    * the difference */
 393
 394   void mergeHeapEdges(Graph graph, Delta delta, Delta newdelta) {
 395     //Merge in edges
 396     for(Map.Entry<AllocNode, HashSet<Edge>> heapedge:delta.heapedgeadd.entrySet()) {
 397       AllocNode nsrc=heapedge.getKey();
 398       HashSet<Edge> edges=heapedge.getValue();
 399       if (!graph.nodeMap.containsKey(nsrc)) {
 400         graph.nodeMap.put(nsrc, new HashSet<Edge>());
 401       }
 402       HashSet<Edge> dstedges=graph.nodeMap.get(nsrc);
 403       HashSet<Edge> diffedges=new HashSet<Edge>();
 404       for(Edge e:edges) {
 405         if (!dstedges.contains(e)) {
 406           //We have a new edge
 407           diffedges.add(e);
 408           dstedges.add(e);
 409         }
 410       }
 411       //Done with edge set...
 412       if (diffedges.size()>0) {
 413         //completely new
 414         newdelta.baseheapedge.put(nsrc, diffedges);
 415       }
 416     }
 417   }
 418
 419   /* This function merges in the var edges.  It updates delta to be
 420    * the difference */
 421
 422   void mergeVarEdges(Graph graph, Delta delta, Delta newdelta) {
 423     //Merge in edges
 424     for(Map.Entry<TempDescriptor, HashSet<Edge>> varedge:delta.varedgeadd.entrySet()) {
 425       TempDescriptor tmpsrc=varedge.getKey();
 426       HashSet<Edge> edges=varedge.getValue();
 427       if (!graph.varMap.containsKey(tmpsrc)) {
 428         graph.varMap.put(tmpsrc, new HashSet<Edge>());
 429       }
 430       HashSet<Edge> dstedges=graph.varMap.get(tmpsrc);
 431       HashSet<Edge> diffedges=new HashSet<Edge>();
 432       for(Edge e:edges) {
 433         if (!dstedges.contains(e)) {
 434           //We have a new edge
 435           diffedges.add(e);
 436           dstedges.add(e);
 437         }
 438       }
 439       //Done with edge set...
 440       if (diffedges.size()>=0) {
 441         //completely new
 442         newdelta.basevaredge.put(tmpsrc,diffedges);
 443       }
 444     }
 445   }
 446 }