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