Robust/src/Analysis/MLP/MLPAnalysis.java

   1 package Analysis.MLP;
   2
   3 import Analysis.CallGraph.*;
   4 import Analysis.OwnershipAnalysis.*;
   5 import IR.*;
   6 import IR.Flat.*;
   7 import IR.Tree.*;
   8 import java.util.*;
   9 import java.io.*;
  10
  11
  12 public class MLPAnalysis {
  13
  14   // data from the compiler
  15   private State state;
  16   private TypeUtil typeUtil;
  17   private CallGraph callGraph;
  18   private OwnershipAnalysis ownAnalysis;
  19
  20   private SESENode          rootTree;
  21   private FlatSESEEnterNode rootSESE;
  22   private FlatSESEExitNode  rootExit;
  23
  24   private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
  25   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessResults;
  26   private Hashtable< FlatNode, VarSrcTokTable           > variableResults;
  27
  28
  29   public MLPAnalysis( State             state,
  30                       TypeUtil          tu,
  31                       CallGraph         callGraph,
  32                       OwnershipAnalysis ownAnalysis
  33                       ) {
  34
  35     double timeStartAnalysis = (double) System.nanoTime();
  36
  37     this.state       = state;
  38     this.typeUtil    = tu;
  39     this.callGraph   = callGraph;
  40     this.ownAnalysis = ownAnalysis;
  41
  42     // initialize analysis data structures
  43     seseStacks      = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
  44     livenessResults = new Hashtable< FlatNode, Set<TempDescriptor>      >();
  45     variableResults = new Hashtable< FlatNode, VarSrcTokTable           >();
  46
  47     // build an implicit root SESE to wrap contents of main method
  48     rootTree = new SESENode( "root" );
  49     rootSESE = new FlatSESEEnterNode( rootTree );
  50     rootExit = new FlatSESEExitNode ( rootTree );
  51     rootSESE.setFlatExit ( rootExit );
  52     rootExit.setFlatEnter( rootSESE );
  53
  54
  55     // 1st pass
  56     // run analysis on each method that is actually called
  57     // reachability analysis already computed this so reuse
  58     Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
  59     while( methItr.hasNext() ) {
  60       Descriptor d = methItr.next();
  61
  62       FlatMethod fm;
  63       if( d instanceof MethodDescriptor ) {
  64         fm = state.getMethodFlat( (MethodDescriptor) d);
  65       } else {
  66         assert d instanceof TaskDescriptor;
  67         fm = state.getMethodFlat( (TaskDescriptor) d);
  68       }
  69
  70       // find every SESE from methods that may be called
  71       // and organize them into roots and children
  72       buildForestForward( fm );
  73
  74       if( state.MLPDEBUG ) {
  75         printSESEForest();
  76       }
  77     }
  78
  79
  80     // 2nd pass
  81     livenessAnalysisBackward( rootSESE );
  82
  83
  84     // 3rd pass
  85     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
  86     while( methItr.hasNext() ) {
  87       Descriptor d = methItr.next();
  88
  89       FlatMethod fm;
  90       if( d instanceof MethodDescriptor ) {
  91         fm = state.getMethodFlat( (MethodDescriptor) d);
  92       } else {
  93         assert d instanceof TaskDescriptor;
  94         fm = state.getMethodFlat( (TaskDescriptor) d);
  95       }
  96
  97       // starting from roots do a forward, fixed-point
  98       // variable analysis for refinement and stalls
  99       variableAnalysisForward( fm );
 100     }
 101
 102
 103     // 4th pass
 104     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 105     while( methItr.hasNext() ) {
 106       Descriptor d = methItr.next();
 107
 108       FlatMethod fm = state.getMethodFlat( d );
 109
 110       computeStallsForward( fm );
 111     }
 112
 113
 114     double timeEndAnalysis = (double) System.nanoTime();
 115     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 116     String treport = String.format( "The mlp analysis took %.3f sec.", dt );
 117     System.out.println( treport );
 118   }
 119
 120   private void buildForestForward( FlatMethod fm ) {
 121
 122     // start from flat method top, visit every node in
 123     // method exactly once, find SESEs and remember
 124     // roots and child relationships
 125     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 126     flatNodesToVisit.add( fm );
 127
 128     Set<FlatNode> visited = new HashSet<FlatNode>();
 129
 130     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 131     seseStackFirst.push( rootSESE );
 132     seseStacks.put( fm, seseStackFirst );
 133
 134     while( !flatNodesToVisit.isEmpty() ) {
 135       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 136       FlatNode fn = fnItr.next();
 137
 138       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 139       assert seseStack != null;
 140
 141       flatNodesToVisit.remove( fn );
 142       visited.add( fn );
 143
 144       buildForest_nodeActions( fn, seseStack );
 145
 146       for( int i = 0; i < fn.numNext(); i++ ) {
 147         FlatNode nn = fn.getNext( i );
 148
 149         if( !visited.contains( nn ) ) {
 150           flatNodesToVisit.add( nn );
 151
 152           // clone stack and send along each analysis path
 153           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 154         }
 155       }
 156     }
 157   }
 158
 159   private void buildForest_nodeActions( FlatNode fn,
 160                                         Stack<FlatSESEEnterNode> seseStack ) {
 161     switch( fn.kind() ) {
 162
 163     case FKind.FlatSESEEnterNode: {
 164       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 165       assert !seseStack.empty();
 166       seseStack.peek().addChild( fsen );
 167       seseStack.push( fsen );
 168     } break;
 169
 170     case FKind.FlatSESEExitNode: {
 171       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 172       assert !seseStack.empty();
 173       FlatSESEEnterNode fsen = seseStack.pop();
 174     } break;
 175
 176     case FKind.FlatReturnNode: {
 177       FlatReturnNode frn = (FlatReturnNode) fn;
 178       if( !seseStack.empty() &&
 179           !seseStack.peek().equals( rootSESE ) ) {
 180         throw new Error( "Error: return statement enclosed within "+seseStack.peek() );
 181       }
 182     } break;
 183
 184     }
 185   }
 186
 187   private void printSESEForest() {
 188     // our forest is actually a tree now that
 189     // there is an implicit root SESE
 190     printSESETree( rootSESE, 0 );
 191     System.out.println( "" );
 192   }
 193
 194   private void printSESETree( FlatSESEEnterNode fsen, int depth ) {
 195     for( int i = 0; i < depth; ++i ) {
 196       System.out.print( "  " );
 197     }
 198     System.out.println( fsen.getPrettyIdentifier() );
 199
 200     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 201     while( childItr.hasNext() ) {
 202       FlatSESEEnterNode fsenChild = childItr.next();
 203       printSESETree( fsenChild, depth + 1 );
 204     }
 205   }
 206
 207
 208   private void livenessAnalysisBackward( FlatSESEEnterNode fsen ) {
 209
 210     // post-order traversal, so do children first
 211     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 212     while( childItr.hasNext() ) {
 213       FlatSESEEnterNode fsenChild = childItr.next();
 214       livenessAnalysisBackward( fsenChild );
 215     }
 216
 217     // start from an SESE exit, visit nodes in reverse up to
 218     // SESE enter in a fixed-point scheme, where children SESEs
 219     // should already be analyzed and therefore can be skipped
 220     // because child SESE enter node has all necessary info
 221     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 222     FlatSESEExitNode fsexn = fsen.getFlatExit();
 223     flatNodesToVisit.add( fsexn );
 224
 225     while( !flatNodesToVisit.isEmpty() ) {
 226       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 227       flatNodesToVisit.remove( fn );
 228
 229       Set<TempDescriptor> prev = livenessResults.get( fn );
 230
 231       // merge sets from control flow joins
 232       Set<TempDescriptor> u = new HashSet<TempDescriptor>();
 233       for( int i = 0; i < fn.numNext(); i++ ) {
 234         FlatNode nn = fn.getNext( i );
 235         Set<TempDescriptor> s = livenessResults.get( nn );
 236         if( s != null ) {
 237           u.addAll( s );
 238         }
 239       }
 240
 241       Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen );
 242
 243       // if a new result, schedule backward nodes for analysis
 244       if( !curr.equals( prev ) ) {
 245
 246         livenessResults.put( fn, curr );
 247
 248         // don't flow backwards past current SESE enter
 249         if( !fn.equals( fsen ) ) {
 250           for( int i = 0; i < fn.numPrev(); i++ ) {
 251             FlatNode nn = fn.getPrev( i );
 252             flatNodesToVisit.add( nn );
 253           }
 254         }
 255       }
 256     }
 257
 258     Set<TempDescriptor> s = livenessResults.get( fsen );
 259     if( s != null ) {
 260       fsen.addInVarSet( s );
 261     }
 262
 263     if( state.MLPDEBUG ) {
 264       System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
 265       Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
 266       while( tItr.hasNext() ) {
 267         System.out.println( "  "+tItr.next() );
 268       }
 269       System.out.println( "" );
 270     }
 271   }
 272
 273   private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
 274                                                     Set<TempDescriptor> liveIn,
 275                                                     FlatSESEEnterNode currentSESE ) {
 276     switch( fn.kind() ) {
 277
 278     default: {
 279       // handle effects of statement in reverse, writes then reads
 280       TempDescriptor [] writeTemps = fn.writesTemps();
 281       for( int i = 0; i < writeTemps.length; ++i ) {
 282         liveIn.remove( writeTemps[i] );
 283       }
 284
 285       TempDescriptor [] readTemps = fn.readsTemps();
 286       for( int i = 0; i < readTemps.length; ++i ) {
 287         liveIn.add( readTemps[i] );
 288       }
 289     } break;
 290
 291     } // end switch
 292
 293     return liveIn;
 294   }
 295
 296
 297   private void variableAnalysisForward( FlatMethod fm ) {
 298
 299     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 300     flatNodesToVisit.add( fm );
 301
 302     while( !flatNodesToVisit.isEmpty() ) {
 303       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 304       flatNodesToVisit.remove( fn );
 305
 306       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 307       assert seseStack != null;
 308
 309       VarSrcTokTable prev = variableResults.get( fn );
 310
 311       // merge sets from control flow joins
 312       VarSrcTokTable inUnion = new VarSrcTokTable();
 313       for( int i = 0; i < fn.numPrev(); i++ ) {
 314         FlatNode nn = fn.getPrev( i );
 315         inUnion.merge( variableResults.get( nn ) );
 316       }
 317
 318       VarSrcTokTable curr = variable_nodeActions( fn, inUnion, seseStack.peek() );
 319
 320       // if a new result, schedule forward nodes for analysis
 321       if( !curr.equals( prev ) ) {
 322
 323         variableResults.put( fn, curr );
 324
 325         for( int i = 0; i < fn.numNext(); i++ ) {
 326           FlatNode nn = fn.getNext( i );
 327           flatNodesToVisit.add( nn );
 328         }
 329       }
 330     }
 331
 332     if( state.MLPDEBUG ) {
 333     }
 334   }
 335
 336   private VarSrcTokTable variable_nodeActions( FlatNode fn,
 337                                                VarSrcTokTable vstTable,
 338                                                FlatSESEEnterNode currentSESE ) {
 339     switch( fn.kind() ) {
 340
 341     case FKind.FlatSESEEnterNode: {
 342       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 343
 344       if( fsen.equals( currentSESE ) ) {
 345         vstTable.age( currentSESE );
 346       }
 347     } break;
 348
 349     case FKind.FlatSESEExitNode: {
 350       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 351
 352       vstTable.removeChildToks( currentSESE );
 353     } break;
 354
 355     case FKind.FlatOpNode: {
 356       FlatOpNode fon = (FlatOpNode) fn;
 357
 358       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 359         TempDescriptor lhs = fon.getDest();
 360         TempDescriptor rhs = fon.getLeft();
 361
 362         vstTable.remove( lhs );
 363
 364         Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
 365         while( itr.hasNext() ) {
 366           VariableSourceToken vst = itr.next();
 367
 368           vstTable.add( new VariableSourceToken( lhs,
 369                                                  vst.getSESE(),
 370                                                  vst.getAge(),
 371                                                  vst.getVarSrc()
 372                                                )
 373                         );
 374         }
 375
 376         // only break if this is an ASSIGN op node,
 377         // otherwise fall through to default case
 378         break;
 379       }
 380     }
 381
 382     // note that FlatOpNode's that aren't ASSIGN
 383     // fall through to this default case
 384     default: {
 385       TempDescriptor [] writeTemps = fn.writesTemps();
 386       if( writeTemps.length > 0 ) {
 387         assert writeTemps.length == 1;
 388
 389         vstTable.remove( writeTemps[0] );
 390
 391         vstTable.add( new VariableSourceToken( writeTemps[0],
 392                                                currentSESE,
 393                                                new Integer( 0 ),
 394                                                writeTemps[0]
 395                                              )
 396                       );
 397       }
 398     } break;
 399
 400     } // end switch
 401
 402     return vstTable;
 403   }
 404
 405
 406   private void computeStallsForward( FlatMethod fm ) {
 407
 408     // start from flat method top, visit every node in
 409     // method exactly once
 410     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 411     flatNodesToVisit.add( fm );
 412
 413     Set<FlatNode> visited = new HashSet<FlatNode>();
 414
 415     while( !flatNodesToVisit.isEmpty() ) {
 416       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 417       FlatNode fn = fnItr.next();
 418
 419       flatNodesToVisit.remove( fn );
 420       visited.add( fn );
 421
 422       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 423       assert seseStack != null;
 424
 425       VarSrcTokTable vstTable = variableResults.get( fn );
 426
 427       computeStalls_nodeActions( fn, vstTable, seseStack.peek() );
 428
 429       for( int i = 0; i < fn.numNext(); i++ ) {
 430         FlatNode nn = fn.getNext( i );
 431
 432         if( !visited.contains( nn ) ) {
 433           flatNodesToVisit.add( nn );
 434         }
 435       }
 436     }
 437   }
 438
 439   private void computeStalls_nodeActions( FlatNode fn,
 440                                           VarSrcTokTable vstTable,
 441                                           FlatSESEEnterNode currentSESE ) {
 442     switch( fn.kind() ) {
 443
 444     case FKind.FlatSESEEnterNode: {
 445       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 446     } break;
 447
 448     case FKind.FlatSESEExitNode: {
 449       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 450     } break;
 451
 452     default: {
 453       Set<VariableSourceToken> stallSet =
 454         vstTable.getStallSet( currentSESE );
 455
 456       System.out.println( fn+" should stall on\n  "+stallSet+"\n" );
 457     } break;
 458
 459     } // end switch
 460   }
 461 }