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