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