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