Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java

   1 package Analysis.OoOJava;
   2
   3 import IR.State;
   4 import IR.TypeUtil;
   5 import IR.MethodDescriptor;
   6 import IR.TypeDescriptor;
   7 import IR.Flat.*;
   8 import Util.Pair;
   9 import Analysis.CallGraph.CallGraph;
  10 import java.util.*;
  11
  12
  13 // This analysis finds all reachable rblocks in the
  14 // program and computes parent/child relations
  15 // between those rblocks
  16
  17 // SPECIAL NOTE!
  18 // There is a distict between parent/child and
  19 // local parent/local child!  "Local" means defined
  20 // and nested within a single method context.
  21 // Otherwise, SESE/rblocks/tasks may have many
  22 // parents and many non-method-context-local
  23 // children considering the call graph
  24
  25 // Also this analysis should identify "critical regions"
  26 // in the context of interprocedural sese/rblock/task relations
  27 // where a statement may conflict with some previously executing
  28 // child task, even if it is in another method context.
  29 //
  30 // Ex:
  31 //
  32 // void main() {
  33 //   task a {
  34 //     Foo f = new Foo();
  35 //     task achild1 {
  36 //       f.z = 1;
  37 //     }
  38 //     doSomething( f );
  39 //   }
  40 // }
  41 //
  42 // void doSomething( Foo f ) {
  43 //   f.z++;     <-------- These two statements are in the critical
  44 //   f.z--;     <-------- region of 'a' after 'c1' and before 'c2'
  45 //   task achild2 {
  46 //     f.z--;
  47 //   }
  48 // }
  49
  50
  51 public class RBlockRelationAnalysis {
  52
  53   // compiler data
  54   State state;
  55   TypeUtil typeUtil;
  56   CallGraph callGraph;
  57
  58   // an implicit SESE is automatically spliced into
  59   // the IR graph around the C main before this analysis--it
  60   // is nothing special except that we can make assumptions
  61   // about it, such as the whole program ends when it ends
  62   protected FlatSESEEnterNode mainSESE;
  63
  64   // this is a special task object, it is not in any IR graph
  65   // and it does not appear to have any children or parents.
  66   // It is a stand-in for whichever task is running when a
  67   // method context starts such that intraprocedural task
  68   // analyses have one static name for "the task who invoked
  69   // this method" to attach facts to.  It GREATLY simplifies
  70   // the OoOJava variable analysis, for instance
  71   protected FlatSESEEnterNode callerProxySESE;
  72
  73   // simply the set of every reachable SESE in the program
  74   protected Set<FlatSESEEnterNode> allSESEs;
  75
  76   // to support calculation of leaf SESEs (no children even
  77   // through method calls) for optimization during code gen
  78   protected Set<MethodDescriptor> methodsContainingSESEs;
  79
  80   // maps method descriptor to SESE defined inside of it
  81   // only contains local root SESE definitions in corresponding method
  82   // (has no parent in the local method context)
  83   protected Hashtable< MethodDescriptor, Set<FlatSESEEnterNode> > md2localRootSESEs;
  84
  85   // the set of every local root SESE in the program (SESE that
  86   // has no parent in the local method context)
  87   protected Set<FlatSESEEnterNode> allLocalRootSESEs;
  88
  89   // if you want to know which rblocks might be executing a given flat
  90   // node it will be in this set
  91   protected Hashtable< FlatNode, Set<FlatSESEEnterNode> > fn2currentSESEs;
  92
  93   // if you want to know which rblocks might be TRANSITIVELY executing
  94   // a given flat node it will be in this set
  95   protected Hashtable< FlatNode, Set<FlatSESEEnterNode> > fn2allSESEs;
  96
  97   // if you want to know the method-local, inner-most nested task that
  98   // is executing a flat node, it is either here or null.
  99   //
 100   // ex:
 101   // void foo() {
 102   //   task a {
 103   //     bar();  <-- here 'a' is the localInnerSESE
 104   //   }
 105   // void bar() {
 106   //   baz();  <-- here there is no locally-defined SESE, would be null
 107   // }
 108   protected Hashtable<FlatNode, FlatSESEEnterNode> fn2localInnerSESE;
 109
 110   // indicates whether this statement might occur in a task and
 111   // after some child task definition such that, without looking at
 112   // the flat node itself, the parent might have to stall for child
 113   protected Hashtable<FlatNode, Boolean> fn2isPotentialStallSite;
 114
 115   HashMap<MethodDescriptor, Set<Pair<FlatCall, MethodDescriptor>>> methodmap=
 116     new HashMap<MethodDescriptor, Set<Pair<FlatCall, MethodDescriptor>>>();
 117
 118
 119
 120   ////////////////////////
 121   // public interface
 122   ////////////////////////
 123   public FlatSESEEnterNode getMainSESE() {
 124     return mainSESE;
 125   }
 126
 127   public Set<FlatSESEEnterNode> getAllSESEs() {
 128     return allSESEs;
 129   }
 130
 131   public Set<FlatSESEEnterNode> getLocalRootSESEs() {
 132     return allLocalRootSESEs;
 133   }
 134
 135   public Set<FlatSESEEnterNode> getLocalRootSESEs(FlatMethod fm) {
 136     Set<FlatSESEEnterNode> out = md2localRootSESEs.get(fm);
 137     if( out == null ) {
 138       out = new HashSet<FlatSESEEnterNode>();
 139     }
 140     return out;
 141   }
 142
 143   public Set<MethodDescriptor> getMethodsWithSESEs() {
 144     return methodsContainingSESEs;
 145   }
 146
 147   /* Returns all SESE's that this fn can be a member of
 148    * transitively. */
 149
 150   public Set<FlatSESEEnterNode> getTransitiveExecutingRBlocks(FlatNode fn) {
 151     if (fn2allSESEs.containsKey(fn))
 152       return fn2allSESEs.get(fn);
 153
 154     //Compute and memoize result
 155     HashSet<FlatSESEEnterNode> seseSet=new HashSet<FlatSESEEnterNode>();
 156     fn2allSESEs.put(fn, seseSet);
 157     Stack<FlatNode> toprocess=new Stack<FlatNode>();
 158     toprocess.add(fn);
 159     while(!toprocess.isEmpty()) {
 160       FlatNode curr=toprocess.pop();
 161       Set<FlatSESEEnterNode> callers=fn2currentSESEs.get(curr);
 162       if (callers!=null) {
 163         for(FlatSESEEnterNode sese : callers) {
 164           if (!seseSet.contains(sese)) {
 165             seseSet.add(sese);
 166             toprocess.add(fn);
 167           }
 168         }
 169       }
 170     }
 171     return seseSet;
 172   }
 173
 174   public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks(FlatNode fn) {
 175     Set<FlatSESEEnterNode> out = fn2currentSESEs.get(fn);
 176     if( out == null ) {
 177       out = new HashSet<FlatSESEEnterNode>();
 178     }
 179     return out;
 180   }
 181
 182   public FlatSESEEnterNode getLocalInnerRBlock(FlatNode fn) {
 183     return fn2localInnerSESE.get(fn);
 184   }
 185
 186   // the "caller proxy" is a static name for whichever
 187   // task invoked the current method context.  It is very
 188   // convenient to know this is ALWAYS a different instance
 189   // of any task defined within the current method context,
 190   // and so using its name simplifies many intraprocedural
 191   // analyses
 192   public FlatSESEEnterNode getCallerProxySESE() {
 193     return callerProxySESE;
 194   }
 195
 196   public boolean isPotentialStallSite(FlatNode fn) {
 197     Boolean ipss = fn2isPotentialStallSite.get(fn);
 198     if( ipss == null ) {
 199       return false;
 200     }
 201     return ipss;
 202   }
 203
 204
 205   public RBlockRelationAnalysis(State state,
 206                                 TypeUtil typeUtil,
 207                                 CallGraph callGraph) {
 208     this.state     = state;
 209     this.typeUtil  = typeUtil;
 210     this.callGraph = callGraph;
 211
 212     callerProxySESE = new FlatSESEEnterNode(null);
 213     callerProxySESE.setIsCallerProxySESE();
 214
 215     allSESEs                = new HashSet<FlatSESEEnterNode>();
 216     allLocalRootSESEs       = new HashSet<FlatSESEEnterNode>();
 217     methodsContainingSESEs  = new HashSet<MethodDescriptor>();
 218     md2localRootSESEs       = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
 219     fn2currentSESEs         = new Hashtable<FlatNode, Set<FlatSESEEnterNode>>();
 220     fn2localInnerSESE       = new Hashtable<FlatNode, FlatSESEEnterNode>();
 221     fn2isPotentialStallSite = new Hashtable<FlatNode, Boolean>();
 222     fn2allSESEs             = new Hashtable< FlatNode, Set<FlatSESEEnterNode>>();
 223
 224
 225     MethodDescriptor mdSourceEntry = typeUtil.getMain();
 226     FlatMethod fmMain        = state.getMethodFlat(mdSourceEntry);
 227
 228     mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
 229     mainSESE.setfmEnclosing(fmMain);
 230     mainSESE.setmdEnclosing(fmMain.getMethod() );
 231     mainSESE.setcdEnclosing(fmMain.getMethod().getClassDesc() );
 232
 233
 234     // add all methods transitively reachable from the
 235     // source's main to set to find rblocks
 236     Set<MethodDescriptor> descriptorsToAnalyze =
 237       callGraph.getAllMethods(mdSourceEntry);
 238
 239     descriptorsToAnalyze.add(mdSourceEntry);
 240
 241     findRblocksAndLocalParentChildRelations(descriptorsToAnalyze);
 242
 243     findTransitiveParentChildRelations();
 244
 245     findPossibleExecutingRBlocksAndStallSites();
 246
 247
 248     // Uncomment this phase to debug the marking of potential
 249     // stall sites for parents between/after children tasks.
 250     // After this debug thing runs in calls System.exit()
 251     // debugPrintPotentialStallSites( descriptorsToAnalyze );
 252   }
 253
 254
 255
 256
 257   protected void findRblocksAndLocalParentChildRelations(Set<MethodDescriptor> descriptorsToAnalyze) {
 258
 259     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 260     while( mdItr.hasNext() ) {
 261       FlatMethod fm = state.getMethodFlat(mdItr.next() );
 262
 263       // start from flat method top, visit every node in
 264       // method exactly once, find SESE stack on every
 265       // control path: this will discover every reachable
 266       // SESE in the program, and define the local parent
 267       // and local children relations
 268       Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
 269         new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
 270
 271       Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 272       flatNodesToVisit.add(fm);
 273
 274       Set<FlatNode> visited = new HashSet<FlatNode>();
 275
 276       Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 277       seseStacks.put(fm, seseStackFirst);
 278
 279       while( !flatNodesToVisit.isEmpty() ) {
 280         Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 281         FlatNode fn = fnItr.next();
 282
 283         Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
 284         assert seseStack != null;
 285
 286         flatNodesToVisit.remove(fn);
 287         visited.add(fn);
 288
 289         if( !seseStack.isEmpty() ) {
 290           fn2localInnerSESE.put(fn, seseStack.peek() );
 291         }
 292
 293         nodeActions(fn, seseStack, fm);
 294
 295         for( int i = 0; i < fn.numNext(); i++ ) {
 296           FlatNode nn = fn.getNext(i);
 297
 298           if( !visited.contains(nn) ) {
 299             flatNodesToVisit.add(nn);
 300
 301             // clone stack and send along each control path
 302             seseStacks.put(nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 303           }
 304         }
 305       }
 306     }
 307   }
 308
 309   protected void nodeActions(FlatNode fn,
 310                              Stack<FlatSESEEnterNode> seseStack,
 311                              FlatMethod fm) {
 312     switch( fn.kind() ) {
 313
 314     case FKind.FlatSESEEnterNode: {
 315       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 316
 317       allSESEs.add(fsen);
 318       methodsContainingSESEs.add(fm.getMethod() );
 319
 320       fsen.setfmEnclosing(fm);
 321       fsen.setmdEnclosing(fm.getMethod() );
 322       fsen.setcdEnclosing(fm.getMethod().getClassDesc() );
 323
 324       if( seseStack.empty() ) {
 325         // no local parent
 326         fsen.setLocalParent(null);
 327
 328         allLocalRootSESEs.add(fsen);
 329
 330         Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get(fm.getMethod() );
 331         if( seseSet == null ) {
 332           seseSet = new HashSet<FlatSESEEnterNode>();
 333         }
 334         seseSet.add(fsen);
 335         md2localRootSESEs.put(fm.getMethod(), seseSet);
 336
 337       } else {
 338         // otherwise a local parent/child relation
 339         // which is also the broader parent/child
 340         // relation as well
 341         seseStack.peek().addLocalChild(fsen);
 342         fsen.setLocalParent(seseStack.peek() );
 343
 344         seseStack.peek().addChild(fsen);
 345         fsen.addParent(seseStack.peek() );
 346       }
 347
 348       seseStack.push(fsen);
 349     } break;
 350
 351     case FKind.FlatSESEExitNode: {
 352       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 353       assert !seseStack.empty();
 354       FlatSESEEnterNode fsen = seseStack.pop();
 355     } break;
 356
 357     case FKind.FlatReturnNode: {
 358       FlatReturnNode frn = (FlatReturnNode) fn;
 359       if( !seseStack.empty() ) {
 360         throw new Error("Error: return statement enclosed within SESE "+
 361                         seseStack.peek().getPrettyIdentifier() );
 362       }
 363     } break;
 364
 365     }
 366   }
 367
 368
 369
 370   protected void findTransitiveParentChildRelations() {
 371
 372     for (Iterator<FlatSESEEnterNode> itr = allSESEs.iterator(); itr.hasNext(); ) {
 373       FlatSESEEnterNode fsen = itr.next();
 374
 375       boolean hasNoNestedChildren = fsen.getLocalChildren().isEmpty();
 376       boolean hasNoChildrenByCall = !hasChildrenByCall(fsen);
 377
 378       fsen.setIsLeafSESE(hasNoNestedChildren && hasNoChildrenByCall);
 379     }
 380   }
 381
 382   protected boolean hasChildrenByCall(FlatSESEEnterNode fsen) {
 383
 384     boolean hasChildrenByCall = false;
 385
 386     // visit every flat node in SESE body, find method calls that
 387     // may transitively call methods with SESEs enclosed
 388     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 389     flatNodesToVisit.add(fsen);
 390
 391     Set<FlatNode> visited = new HashSet<FlatNode>();
 392
 393     while( !flatNodesToVisit.isEmpty() ) {
 394       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 395       FlatNode fn = fnItr.next();
 396
 397       flatNodesToVisit.remove(fn);
 398       visited.add(fn);
 399
 400       if( fn.kind() == FKind.FlatCall ) {
 401         FlatCall fc        = (FlatCall) fn;
 402         MethodDescriptor mdCallee  = fc.getMethod();
 403         Set reachable = new HashSet();
 404
 405         reachable.add(mdCallee);
 406         reachable.addAll(callGraph.getAllMethods(mdCallee) );
 407         reachable.retainAll(methodsContainingSESEs);
 408
 409         if( !reachable.isEmpty() ) {
 410           hasChildrenByCall = true;
 411
 412           Set reachableSESEMethodSet =
 413             callGraph.getFirstReachableMethodContainingSESE(mdCallee, methodsContainingSESEs);
 414
 415           reachableSESEMethodSet.add(mdCallee);
 416           reachableSESEMethodSet.retainAll(methodsContainingSESEs);
 417
 418           for( Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext(); ) {
 419             MethodDescriptor md = (MethodDescriptor) iterator.next();
 420             Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get(md);
 421             if( seseSet != null ) {
 422               fsen.addChildren(seseSet);
 423               for( Iterator iterator2 = seseSet.iterator(); iterator2.hasNext(); ) {
 424                 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
 425                 child.addParent(fsen);
 426               }
 427             }
 428           }
 429         }
 430       }
 431
 432       if( fn == fsen.getFlatExit() ) {
 433         // don't enqueue any futher nodes
 434         continue;
 435       }
 436
 437       for( int i = 0; i < fn.numNext(); i++ ) {
 438         FlatNode nn = fn.getNext(i);
 439
 440         if( !visited.contains(nn) ) {
 441           flatNodesToVisit.add(nn);
 442         }
 443       }
 444     }
 445
 446     return hasChildrenByCall;
 447   }
 448
 449   protected void findPossibleExecutingRBlocksAndStallSites() {
 450     for( Iterator<FlatSESEEnterNode> fsenItr = allSESEs.iterator(); fsenItr.hasNext(); ) {
 451       FlatSESEEnterNode fsen = fsenItr.next();
 452
 453       // walk the program points, including across method calls, reachable within
 454       // this sese/rblock/task and mark that this rblock might be executing.
 455       // Important: skip the body of child rblocks, BUT DO mark the child ENTER
 456       // and EXIT flat nodes as the parent being the current executing rblock!
 457       Hashtable<FlatNode, FlatMethod> flatNodesToVisit =
 458         new Hashtable<FlatNode, FlatMethod>();
 459
 460       for( int i = 0; i < fsen.numNext(); i++ ) {
 461         FlatNode nn = fsen.getNext(i);
 462         flatNodesToVisit.put(nn, fsen.getfmEnclosing() );
 463       }
 464
 465       Set<FlatNode> visited = new HashSet<FlatNode>();
 466
 467       while (!flatNodesToVisit.isEmpty()) {
 468         Map.Entry me = (Map.Entry)flatNodesToVisit.entrySet().iterator().next();
 469         FlatNode fn = (FlatNode) me.getKey();
 470         FlatMethod fm = (FlatMethod) me.getValue();
 471
 472         flatNodesToVisit.remove(fn);
 473         visited.add(fn);
 474
 475         // the "is potential stall site" strategy is to propagate
 476         // "false" from the beginning of a task until you hit a
 477         // child, then from the child's exit propagate "true" for
 478         // the parent statements after children. When you pull a node
 479         // out of the bag for traversal and it happens to be an
 480         // enter or an exit node, fix the dumb propagation that
 481         // your IR predecessor pushed on you
 482         Boolean isPotentialStallSite = isPotentialStallSite(fn);
 483
 484         if (fn == fsen.getFlatExit()) {
 485           // don't enqueue any further nodes when you find your exit,
 486           // NOR mark your own flat as a statement you are currently
 487           // executing, your parent(s) will mark it
 488           continue;
 489         }
 490
 491         if (fn instanceof FlatSESEExitNode) {
 492           setIsPotentialStallSite(fn, false);
 493           isPotentialStallSite = true;
 494         }
 495
 496         // the purpose of this traversal is to find program
 497         // points where rblock 'fsen' might be executing
 498         addPossibleExecutingRBlock(fn, fsen);
 499
 500         if (fn instanceof FlatSESEEnterNode) {
 501           // don't visit internal nodes of child,
 502           // just enqueue the exit node
 503           FlatSESEEnterNode child = (FlatSESEEnterNode) fn;
 504           assert fsen.getChildren().contains(child);
 505           assert child.getParents().contains(fsen);
 506           flatNodesToVisit.put(child.getFlatExit(), fm);
 507           setIsPotentialStallSite(fn, false);
 508
 509           // explicitly do this to handle the case that you
 510           // should mark yourself as possibly executing at
 511           // your own exit, because one instance can
 512           // recursively invoke another
 513           addPossibleExecutingRBlock(child.getFlatExit(), fsen);
 514
 515           continue;
 516         }
 517
 518         // if previous flat nodes have any changes,,
 519         // propagate predecessor's status of stall site potential
 520
 521         if (fn instanceof FlatCall) {
 522
 523           // start visiting nodes in other contexts
 524           FlatCall fc = (FlatCall) fn;
 525           MethodDescriptor mdCallee = fc.getMethod();
 526
 527           Set<MethodDescriptor> implementations = new HashSet<MethodDescriptor>();
 528
 529           if (mdCallee.isStatic()) {
 530             implementations.add(mdCallee);
 531           } else {
 532             TypeDescriptor typeDesc = fc.getThis().getType();
 533             implementations.addAll(callGraph.getMethods(mdCallee, typeDesc));
 534           }
 535
 536           for (Iterator imps = implementations.iterator(); imps.hasNext(); ) {
 537             MethodDescriptor mdImp = (MethodDescriptor) imps.next();
 538             FlatMethod fmImp = state.getMethodFlat(mdImp);
 539
 540             // keep mapping from fc's md to <fc,caller's md>
 541             // later, when return node of callee becomes a potential stall site,
 542             // following flat nodes of fc should be re-analyzied
 543             if(!methodmap.containsKey(fmImp)) {
 544               methodmap.put(mdImp, new HashSet<Pair<FlatCall,MethodDescriptor>>());
 545             }
 546             methodmap.get(mdImp).add(new Pair<FlatCall,MethodDescriptor>(fc,fm.getMethod()));
 547
 548             if ((isPotentialStallSite && !isPotentialStallSite(fmImp)) || !visited.contains(fmImp)) {
 549               flatNodesToVisit.put(fmImp, fmImp);
 550
 551               // propagate your IR graph predecessor's stall site potential
 552               mergeIsPotentialStallSite(fmImp, isPotentialStallSite);
 553             }
 554
 555           }
 556           // don't 'continue' out of this loop, also enqueue
 557           // flat nodes that flow in the current method context
 558         }
 559
 560         if (fn instanceof FlatReturnNode) {
 561           // if return node is potential stall site, need to inform its caller
 562           if (isPotentialStallSite) {
 563             Set<Pair<FlatCall, MethodDescriptor>> callset = methodmap.get(fm.getMethod());
 564             if (callset != null) {
 565               for (Pair<FlatCall, MethodDescriptor> fcallpair : callset) {
 566                 FlatCall fcall = fcallpair.getFirst();
 567                 MethodDescriptor mdcaller = fcallpair.getSecond();
 568                 for (int i = 0; i < fcall.numNext(); i++) {
 569                   FlatNode nn = fcall.getNext(i);
 570                   if ( visited.contains(nn) && (!isPotentialStallSite(nn)) ) {
 571                     mergeIsPotentialStallSite(nn, isPotentialStallSite);
 572                     FlatMethod fmcaller = state.getMethodFlat(mdcaller);
 573                     flatNodesToVisit.put(nn, fmcaller);
 574                   }
 575                 }
 576               }
 577             }
 578           }
 579         }
 580
 581         // note: only when current flat node has a change on the status of potential
 582         // stall site, need to visit following flat nodes
 583         for (int i = 0; i < fn.numNext(); i++) {
 584           FlatNode nn = fn.getNext(i);
 585           if ((isPotentialStallSite && !isPotentialStallSite(nn)) || !visited.contains(nn)) {
 586             flatNodesToVisit.put(nn, fm);
 587             mergeIsPotentialStallSite(nn, isPotentialStallSite);
 588           }
 589         }
 590       }
 591     }
 592   }
 593
 594
 595
 596   protected void addPossibleExecutingRBlock(FlatNode fn,
 597                                             FlatSESEEnterNode fsen) {
 598
 599     Set<FlatSESEEnterNode> currentSESEs = fn2currentSESEs.get(fn);
 600     if( currentSESEs == null ) {
 601       currentSESEs = new HashSet<FlatSESEEnterNode>();
 602     }
 603
 604     currentSESEs.add(fsen);
 605     fn2currentSESEs.put(fn, currentSESEs);
 606   }
 607
 608
 609   // definitively set whether a statement is a potential stall site
 610   // such as a task exit is FALSE and the statement following an exit
 611   // is TRUE
 612   protected void setIsPotentialStallSite(FlatNode fn,
 613                                          Boolean ipss) {
 614     fn2isPotentialStallSite.put(fn, ipss);
 615   }
 616
 617
 618   // Use this to OR the previous result with a new result
 619   protected void mergeIsPotentialStallSite(FlatNode fn,
 620                                            Boolean ipss) {
 621     Boolean ipssPrev = isPotentialStallSite(fn);
 622     setIsPotentialStallSite(fn, ipssPrev || ipss);
 623   }
 624
 625
 626
 627
 628
 629   /////////////////////////////////////////////////
 630   // for DEBUG
 631   /////////////////////////////////////////////////
 632   protected void debugPrintPotentialStallSites(Set<MethodDescriptor> descriptorsToAnalyze) {
 633     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 634     while (mdItr.hasNext()) {
 635       FlatMethod fm = state.getMethodFlat(mdItr.next());
 636       printStatusMap(fm);
 637     }
 638     System.exit(0);
 639   }
 640
 641   protected void printStatusMap(FlatMethod fm) {
 642
 643     System.out.println("\n\n=== "+fm+" ===");
 644
 645     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 646     flatNodesToVisit.add(fm);
 647
 648     Set<FlatNode> visited = new HashSet<FlatNode>();
 649
 650     while (!flatNodesToVisit.isEmpty()) {
 651       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 652       FlatNode fn = fnItr.next();
 653
 654       flatNodesToVisit.remove(fn);
 655       visited.add(fn);
 656
 657       System.out.println(fn+"[["+isPotentialStallSite(fn)+"]]");
 658
 659       for (int i = 0; i < fn.numNext(); i++) {
 660         FlatNode nn = fn.getNext(i);
 661
 662         if (!visited.contains(nn)) {
 663           flatNodesToVisit.add(nn);
 664         }
 665       }
 666     }
 667   }
 668
 669 }