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