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 FlatSESEEnterNode getCallerProxySESE() {
 119     return callerProxySESE;
 120   }
 121
 122   public Set<FlatSESEEnterNode> getAllSESEs() {
 123     return allSESEs;
 124   }
 125
 126   public Set<FlatSESEEnterNode> getLocalRootSESEs() {
 127     return allLocalRootSESEs;
 128   }
 129
 130   public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks( FlatNode fn ) {
 131     return fn2currentSESEs.get( fn );
 132   }
 133
 134   public FlatSESEEnterNode getLocalInnerRBlock( FlatNode fn ) {
 135     return fn2localInnerSESE.get( fn );
 136   }
 137
 138   public boolean isPotentialStallSite( FlatNode fn ) {
 139     Boolean ipss = fn2isPotentialStallSite.get( fn );
 140     if( ipss == null ) {
 141       return false;
 142     }
 143     return ipss;
 144   }
 145
 146
 147   public RBlockRelationAnalysis( State     state,
 148                                  TypeUtil  typeUtil,
 149                                  CallGraph callGraph ) {
 150     this.state     = state;
 151     this.typeUtil  = typeUtil;
 152     this.callGraph = callGraph;
 153
 154     callerProxySESE = new FlatSESEEnterNode( null );
 155
 156     allSESEs                = new HashSet<FlatSESEEnterNode>();
 157     allLocalRootSESEs       = new HashSet<FlatSESEEnterNode>();
 158     methodsContainingSESEs  = new HashSet<MethodDescriptor>();
 159     md2localRootSESEs       = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
 160     fn2currentSESEs         = new Hashtable<FlatNode, Set<FlatSESEEnterNode>>();
 161     fn2localInnerSESE       = new Hashtable<FlatNode, FlatSESEEnterNode>();
 162     fn2isPotentialStallSite = new Hashtable<FlatNode, Boolean>();
 163
 164
 165     MethodDescriptor mdSourceEntry = typeUtil.getMain();
 166     FlatMethod       fmMain        = state.getMethodFlat( mdSourceEntry );
 167
 168     mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
 169     mainSESE.setfmEnclosing( fmMain );
 170     mainSESE.setmdEnclosing( fmMain.getMethod() );
 171     mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
 172
 173
 174     // add all methods transitively reachable from the
 175     // source's main to set to find rblocks
 176     Set<MethodDescriptor> descriptorsToAnalyze =
 177       callGraph.getAllMethods( mdSourceEntry );
 178
 179     descriptorsToAnalyze.add( mdSourceEntry );
 180
 181     findRblocksAndLocalParentChildRelations( descriptorsToAnalyze );
 182
 183     findTransitiveParentChildRelations();
 184
 185     findPossibleExecutingRBlocksAndStallSites();
 186
 187
 188     // Uncomment this phase to debug the marking of potential
 189     // stall sites for parents between/after children tasks.
 190     // After this debug thing runs in calls System.exit()
 191     //debugPrintPotentialStallSites( descriptorsToAnalyze );
 192   }
 193
 194
 195
 196
 197   protected void findRblocksAndLocalParentChildRelations( Set<MethodDescriptor> descriptorsToAnalyze ) {
 198
 199     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 200     while( mdItr.hasNext() ) {
 201       FlatMethod fm = state.getMethodFlat( mdItr.next() );
 202
 203       // start from flat method top, visit every node in
 204       // method exactly once, find SESE stack on every
 205       // control path: this will discover every reachable
 206       // SESE in the program, and define the local parent
 207       // and local children relations
 208       Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
 209         new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
 210
 211       Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 212       flatNodesToVisit.add( fm );
 213
 214       Set<FlatNode> visited = new HashSet<FlatNode>();
 215
 216       Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 217       seseStacks.put( fm, seseStackFirst );
 218
 219       while( !flatNodesToVisit.isEmpty() ) {
 220         Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 221         FlatNode fn = fnItr.next();
 222
 223         Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 224         assert seseStack != null;
 225
 226         flatNodesToVisit.remove( fn );
 227         visited.add( fn );
 228
 229         if( !seseStack.isEmpty() ) {
 230           fn2localInnerSESE.put( fn, seseStack.peek() );
 231         }
 232
 233         nodeActions( fn, seseStack, fm );
 234
 235         for( int i = 0; i < fn.numNext(); i++ ) {
 236           FlatNode nn = fn.getNext( i );
 237
 238           if( !visited.contains( nn ) ) {
 239             flatNodesToVisit.add( nn );
 240
 241             // clone stack and send along each control path
 242             seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 243           }
 244         }
 245       }
 246     }
 247   }
 248
 249   protected void nodeActions( FlatNode fn,
 250                               Stack<FlatSESEEnterNode> seseStack,
 251                               FlatMethod fm ) {
 252     switch( fn.kind() ) {
 253
 254     case FKind.FlatSESEEnterNode: {
 255       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 256
 257       allSESEs.add( fsen );
 258       methodsContainingSESEs.add( fm.getMethod() );
 259
 260       fsen.setfmEnclosing( fm );
 261       fsen.setmdEnclosing( fm.getMethod() );
 262       fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
 263
 264       if( seseStack.empty() ) {
 265         // no local parent
 266         fsen.setLocalParent( null );
 267
 268         allLocalRootSESEs.add( fsen );
 269
 270         Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get( fm.getMethod() );
 271         if( seseSet == null ) {
 272           seseSet = new HashSet<FlatSESEEnterNode>();
 273         }
 274         seseSet.add( fsen );
 275         md2localRootSESEs.put( fm.getMethod(), seseSet );
 276
 277       } else {
 278         // otherwise a local parent/child relation
 279         // which is also the broader parent/child
 280         // relation as well
 281         seseStack.peek().addLocalChild( fsen );
 282         fsen.setLocalParent( seseStack.peek() );
 283
 284         seseStack.peek().addChild( fsen );
 285         fsen.addParent( seseStack.peek() );
 286       }
 287
 288       seseStack.push( fsen );
 289     } break;
 290
 291     case FKind.FlatSESEExitNode: {
 292       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 293       assert !seseStack.empty();
 294       FlatSESEEnterNode fsen = seseStack.pop();
 295     } break;
 296
 297     case FKind.FlatReturnNode: {
 298       FlatReturnNode frn = (FlatReturnNode) fn;
 299       if( !seseStack.empty() ) {
 300         throw new Error( "Error: return statement enclosed within SESE "+
 301                          seseStack.peek().getPrettyIdentifier() );
 302       }
 303     } break;
 304
 305     }
 306   }
 307
 308
 309
 310   protected void findTransitiveParentChildRelations() {
 311
 312     for (Iterator<FlatSESEEnterNode> itr = allSESEs.iterator(); itr.hasNext();) {
 313       FlatSESEEnterNode fsen = itr.next();
 314
 315       boolean hasNoNestedChildren = fsen.getLocalChildren().isEmpty();
 316       boolean hasNoChildrenByCall = !hasChildrenByCall( fsen );
 317
 318       fsen.setIsLeafSESE( hasNoNestedChildren && hasNoChildrenByCall );
 319     }
 320   }
 321
 322   protected boolean hasChildrenByCall( FlatSESEEnterNode fsen ) {
 323
 324     boolean hasChildrenByCall = false;
 325
 326     // visit every flat node in SESE body, find method calls that
 327     // may transitively call methods with SESEs enclosed
 328     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 329     flatNodesToVisit.add( fsen );
 330
 331     Set<FlatNode> visited = new HashSet<FlatNode>();
 332
 333     while( !flatNodesToVisit.isEmpty() ) {
 334       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 335       FlatNode fn = fnItr.next();
 336
 337       flatNodesToVisit.remove( fn );
 338       visited.add( fn );
 339
 340       if( fn.kind() == FKind.FlatCall ) {
 341         FlatCall         fc        = (FlatCall) fn;
 342         MethodDescriptor mdCallee  = fc.getMethod();
 343         Set              reachable = new HashSet();
 344
 345         reachable.add( mdCallee );
 346         reachable.addAll( callGraph.getAllMethods( mdCallee ) );
 347         reachable.retainAll( methodsContainingSESEs );
 348
 349         if( !reachable.isEmpty() ) {
 350           hasChildrenByCall = true;
 351
 352           Set reachableSESEMethodSet =
 353             callGraph.getFirstReachableMethodContainingSESE( mdCallee, methodsContainingSESEs );
 354
 355           reachableSESEMethodSet.add( mdCallee );
 356           reachableSESEMethodSet.retainAll( methodsContainingSESEs );
 357
 358           for( Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext(); ) {
 359             MethodDescriptor md = (MethodDescriptor) iterator.next();
 360             Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get( md );
 361             if( seseSet != null ) {
 362               fsen.addChildren( seseSet );
 363               for( Iterator iterator2 = seseSet.iterator(); iterator2.hasNext(); ) {
 364                 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
 365                 child.addParent( fsen );
 366               }
 367             }
 368           }
 369         }
 370       }
 371
 372       if( fn == fsen.getFlatExit() ) {
 373         // don't enqueue any futher nodes
 374         continue;
 375       }
 376
 377       for( int i = 0; i < fn.numNext(); i++ ) {
 378         FlatNode nn = fn.getNext( i );
 379
 380         if( !visited.contains( nn ) ) {
 381           flatNodesToVisit.add( nn );
 382         }
 383       }
 384     }
 385
 386     return hasChildrenByCall;
 387   }
 388
 389
 390
 391   protected void findPossibleExecutingRBlocksAndStallSites() {
 392     for( Iterator<FlatSESEEnterNode> fsenItr = allSESEs.iterator(); fsenItr.hasNext(); ) {
 393       FlatSESEEnterNode fsen = fsenItr.next();
 394
 395       // walk the program points, including across method calls, reachable within
 396       // this sese/rblock/task and mark that this rblock might be executing.
 397       // Important: skip the body of child rblocks, BUT DO mark the child ENTER
 398       // and EXIT flat nodes as the parent being the current executing rblock!
 399       Hashtable<FlatNode, FlatMethod> flatNodesToVisit =
 400         new Hashtable<FlatNode, FlatMethod>();
 401
 402       for( int i = 0; i < fsen.numNext(); i++ ) {
 403         FlatNode nn = fsen.getNext( i );
 404         flatNodesToVisit.put( nn, fsen.getfmEnclosing() );
 405         mergeIsPotentialStallSite( nn, false );
 406       }
 407
 408       Set<FlatNode> visited = new HashSet<FlatNode>();
 409
 410       while( !flatNodesToVisit.isEmpty() ) {
 411         Map.Entry  me = (Map.Entry)  flatNodesToVisit.entrySet().iterator().next();
 412         FlatNode   fn = (FlatNode)   me.getKey();
 413         FlatMethod fm = (FlatMethod) me.getValue();
 414
 415         flatNodesToVisit.remove( fn );
 416         visited.add( fn );
 417
 418
 419         // the "is potential stall site" strategy is to propagate
 420         // "false" from the beginning of a task until you hit a
 421         // child, then from the child's exit propagate "true" for
 422         // the parent statements after children.  When you pull a node
 423         // out of the bag for traversal and it happens to be an
 424         // enter or an exit node, fix the dumb propagation that
 425         // your IR predecessor pushed on you
 426         Boolean isPotentialStallSite = isPotentialStallSite( fn );
 427
 428         if( fn instanceof FlatSESEEnterNode ||
 429             fn instanceof FlatSESEExitNode ) {
 430           // fix it so this is never a potential stall site, but from
 431           // a child definition onward propagate 'true'
 432           setIsPotentialStallSite( fn, false );
 433           isPotentialStallSite = true;
 434         }
 435
 436
 437         if( fn == fsen.getFlatExit() ) {
 438           // don't enqueue any futher nodes when you find your exit,
 439           // NOR mark your own flat as a statement you are currently
 440           // executing, your parent(s) will mark it
 441           continue;
 442         }
 443
 444
 445         // the purpose of this traversal is to find program
 446         // points where rblock 'fsen' might be executing
 447         addPossibleExecutingRBlock( fn, fsen );
 448
 449
 450         if( fn instanceof FlatSESEEnterNode ) {
 451           // don't visit internal nodes of child,
 452           // just enqueue the exit node
 453           FlatSESEEnterNode child = (FlatSESEEnterNode) fn;
 454           assert fsen.getChildren().contains( child );
 455           assert child.getParents().contains( fsen );
 456           flatNodesToVisit.put( child.getFlatExit(), fm );
 457
 458           // explicitly do this to handle the case that you
 459           // should mark yourself as possibly executing at
 460           // your own exit, because one instance can
 461           // recursively invoke another
 462           addPossibleExecutingRBlock( child.getFlatExit(), fsen );
 463
 464           continue;
 465         }
 466
 467         if( fn instanceof FlatCall ) {
 468           // start visiting nodes in other contexts
 469           FlatCall         fc       = (FlatCall) fn;
 470           MethodDescriptor mdCallee = fc.getMethod();
 471
 472           Set<MethodDescriptor> implementations = new HashSet<MethodDescriptor>();
 473
 474           if( mdCallee.isStatic() ) {
 475             implementations.add( mdCallee );
 476           } else {
 477             TypeDescriptor typeDesc = fc.getThis().getType();
 478             implementations.addAll( callGraph.getMethods( mdCallee, typeDesc ) );
 479           }
 480
 481           for( Iterator imps = implementations.iterator(); imps.hasNext(); ) {
 482             MethodDescriptor mdImp = (MethodDescriptor) imps.next();
 483             FlatMethod       fmImp = state.getMethodFlat( mdImp );
 484             flatNodesToVisit.put( fmImp, fmImp );
 485
 486             // propagate your IR graph predecessor's stall site potential
 487             mergeIsPotentialStallSite( fmImp, isPotentialStallSite );
 488           }
 489           // don't 'continue' out of this loop, also enqueue
 490           // flat nodes that flow in the current method context
 491         }
 492
 493         // otherwise keep visiting nodes in same context
 494         for( int i = 0; i < fn.numNext(); i++ ) {
 495           FlatNode nn = fn.getNext( i );
 496
 497           if( !visited.contains( nn ) ) {
 498             flatNodesToVisit.put( nn, fm );
 499
 500             // propagate your IR graph predecessor's stall site potential
 501             mergeIsPotentialStallSite( nn, isPotentialStallSite );
 502           }
 503         }
 504       }
 505     }
 506   }
 507
 508
 509
 510   protected void addPossibleExecutingRBlock( FlatNode          fn,
 511                                              FlatSESEEnterNode fsen ) {
 512
 513     Set<FlatSESEEnterNode> currentSESEs = fn2currentSESEs.get( fn );
 514     if( currentSESEs == null ) {
 515       currentSESEs = new HashSet<FlatSESEEnterNode>();
 516     }
 517
 518     currentSESEs.add( fsen );
 519     fn2currentSESEs.put( fn, currentSESEs );
 520   }
 521
 522
 523   // definitively set whether a statement is a potential stall site
 524   // such as a task exit is FALSE and the statement following an exit
 525   // is TRUE
 526   protected void setIsPotentialStallSite( FlatNode   fn,
 527                                           Boolean    ipss ) {
 528     fn2isPotentialStallSite.put( fn, ipss );
 529   }
 530
 531
 532   // Use this to OR the previous result with a new result
 533   protected void mergeIsPotentialStallSite( FlatNode   fn,
 534                                             Boolean    ipss ) {
 535     Boolean ipssPrev = isPotentialStallSite( fn );
 536     setIsPotentialStallSite( fn, ipssPrev || ipss );
 537   }
 538
 539
 540
 541
 542
 543   /////////////////////////////////////////////////
 544   // for DEBUG
 545   /////////////////////////////////////////////////
 546   protected void debugPrintPotentialStallSites(Set<MethodDescriptor> descriptorsToAnalyze) {
 547     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 548     while (mdItr.hasNext()) {
 549       FlatMethod fm = state.getMethodFlat(mdItr.next());
 550       printStatusMap(fm);
 551     }
 552     System.exit( 0 );
 553   }
 554
 555   protected void printStatusMap(FlatMethod fm) {
 556
 557     System.out.println("\n\n=== "+fm+" ===");
 558
 559     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 560     flatNodesToVisit.add(fm);
 561
 562     Set<FlatNode> visited = new HashSet<FlatNode>();
 563
 564     while (!flatNodesToVisit.isEmpty()) {
 565       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 566       FlatNode fn = fnItr.next();
 567
 568       flatNodesToVisit.remove(fn);
 569       visited.add(fn);
 570
 571       System.out.println(fn+"[["+isPotentialStallSite(fn)+"]]");
 572
 573       for (int i = 0; i < fn.numNext(); i++) {
 574         FlatNode nn = fn.getNext(i);
 575
 576         if (!visited.contains(nn)) {
 577           flatNodesToVisit.add(nn);
 578         }
 579       }
 580     }
 581   }
 582
 583 }