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,
 208                                            boolean toplevel,
 209                                            Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout,
 210                                            FlatExit fexit ) {
 211
 212     // start from an SESE exit, visit nodes in reverse up to
 213     // SESE enter in a fixed-point scheme, where children SESEs
 214     // should already be analyzed and therefore can be skipped
 215     // because child SESE enter node has all necessary info
 216     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 217
 218     FlatSESEExitNode fsexn = fsen.getFlatExit();
 219     if (toplevel) {
 220         //handle root SESE
 221         flatNodesToVisit.add( fexit );
 222     } else
 223         flatNodesToVisit.add( fsexn );
 224     Hashtable<FlatNode, Set<TempDescriptor>> livenessResults=new Hashtable<FlatNode, Set<TempDescriptor>>();
 225
 226     if (toplevel==true)
 227         liveout=new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
 228
 229     while( !flatNodesToVisit.isEmpty() ) {
 230       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 231       flatNodesToVisit.remove( fn );
 232
 233       Set<TempDescriptor> prev = livenessResults.get( fn );
 234
 235       // merge sets from control flow joins
 236       Set<TempDescriptor> u = new HashSet<TempDescriptor>();
 237       for( int i = 0; i < fn.numNext(); i++ ) {
 238         FlatNode nn = fn.getNext( i );
 239         Set<TempDescriptor> s = livenessResults.get( nn );
 240         if( s != null ) {
 241           u.addAll( s );
 242         }
 243       }
 244
 245       Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
 246
 247       // if a new result, schedule backward nodes for analysis
 248       if(!curr.equals(prev)) {
 249         livenessResults.put( fn, curr );
 250
 251         // don't flow backwards past current SESE enter
 252         if( !fn.equals( fsen ) ) {
 253           for( int i = 0; i < fn.numPrev(); i++ ) {
 254             FlatNode nn = fn.getPrev( i );
 255             flatNodesToVisit.add( nn );
 256           }
 257         }
 258       }
 259     }
 260
 261     Set<TempDescriptor> s = livenessResults.get( fsen );
 262     if( s != null ) {
 263       fsen.addInVarSet( s );
 264     }
 265
 266     if( state.MLPDEBUG ) {
 267       System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
 268       Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
 269       while( tItr.hasNext() ) {
 270         System.out.println( "  "+tItr.next() );
 271       }
 272       System.out.println( "and out-set:" );
 273       tItr = fsen.getOutVarSet().iterator();
 274       while( tItr.hasNext() ) {
 275         System.out.println( "  "+tItr.next() );
 276       }
 277       System.out.println( "" );
 278     }
 279     // post-order traversal, so do children first
 280     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 281     while( childItr.hasNext() ) {
 282       FlatSESEEnterNode fsenChild = childItr.next();
 283       livenessAnalysisBackward( fsenChild, false, liveout, null);
 284     }
 285   }
 286
 287   private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
 288                                                     Set<TempDescriptor> liveIn,
 289                                                     FlatSESEEnterNode currentSESE,
 290                                                     boolean toplevel,
 291                                                     Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
 292
 293     switch( fn.kind() ) {
 294
 295     case FKind.FlatSESEExitNode:
 296       if (toplevel==true) {
 297           FlatSESEExitNode exitn=(FlatSESEExitNode) fn;
 298         //update liveout set for FlatSESEExitNode
 299           if (!liveout.containsKey(exitn))
 300             liveout.put(exitn, new HashSet<TempDescriptor>());
 301           liveout.get(exitn).addAll(liveIn);
 302       }
 303       // no break, sese exits should also execute default actions
 304
 305     default: {
 306       // handle effects of statement in reverse, writes then reads
 307       TempDescriptor [] writeTemps = fn.writesTemps();
 308       for( int i = 0; i < writeTemps.length; ++i ) {
 309         liveIn.remove( writeTemps[i] );
 310
 311         if (!toplevel) {
 312           FlatSESEExitNode exitnode=currentSESE.getFlatExit();
 313           Set<TempDescriptor> livetemps=liveout.get(exitnode);
 314           if (livetemps.contains(writeTemps[i])) {
 315             //write to a live out temp...
 316             //need to put in SESE liveout set
 317             currentSESE.addOutVar(writeTemps[i]);
 318           }
 319         }
 320       }
 321
 322       TempDescriptor [] readTemps = fn.readsTemps();
 323       for( int i = 0; i < readTemps.length; ++i ) {
 324         liveIn.add( readTemps[i] );
 325       }
 326
 327       Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
 328       if( virtualReadTemps != null ) {
 329         Iterator<TempDescriptor> vrItr = virtualReadTemps.iterator();
 330         while( vrItr.hasNext() ) {
 331           liveIn.add( vrItr.next() );
 332         }
 333       }
 334     } break;
 335
 336     } // end switch
 337
 338     return liveIn;
 339   }
 340
 341
 342   private void variableAnalysisForward( FlatMethod fm ) {
 343
 344     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 345     flatNodesToVisit.add( fm );
 346
 347     while( !flatNodesToVisit.isEmpty() ) {
 348       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 349       flatNodesToVisit.remove( fn );
 350
 351       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 352       assert seseStack != null;
 353
 354       VarSrcTokTable prev = variableResults.get( fn );
 355
 356       // merge sets from control flow joins
 357       VarSrcTokTable inUnion = new VarSrcTokTable();
 358       for( int i = 0; i < fn.numPrev(); i++ ) {
 359         FlatNode nn = fn.getPrev( i );
 360
 361         VarSrcTokTable incoming = variableResults.get( nn );
 362         if( incoming != null ) {
 363           incoming.assertConsistency();
 364         }
 365
 366         inUnion.merge( incoming );
 367       }
 368
 369       VarSrcTokTable curr = variable_nodeActions( fn, inUnion, seseStack.peek() );
 370
 371       // if a new result, schedule forward nodes for analysis
 372       if( !curr.equals( prev ) ) {
 373
 374
 375         curr.assertConsistency();
 376
 377         variableResults.put( fn, curr );
 378
 379         for( int i = 0; i < fn.numNext(); i++ ) {
 380           FlatNode nn = fn.getNext( i );
 381           flatNodesToVisit.add( nn );
 382         }
 383       }
 384     }
 385   }
 386
 387   private VarSrcTokTable variable_nodeActions( FlatNode fn,
 388                                                VarSrcTokTable vstTable,
 389                                                FlatSESEEnterNode currentSESE ) {
 390     switch( fn.kind() ) {
 391
 392     case FKind.FlatSESEEnterNode: {
 393       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 394       assert fsen.equals( currentSESE );
 395       vstTable.age( currentSESE );
 396
 397       vstTable.assertConsistency();
 398
 399     } break;
 400
 401     case FKind.FlatSESEExitNode: {
 402       FlatSESEExitNode  fsexn = (FlatSESEExitNode)  fn;
 403       FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 404       assert currentSESE.getChildren().contains( fsen );
 405       vstTable.remapChildTokens( fsen );
 406
 407       Set<TempDescriptor> liveIn       = currentSESE.getInVarSet();
 408       Set<TempDescriptor> virLiveIn    = vstTable.removeParentAndSiblingTokens( fsen, liveIn );
 409       Set<TempDescriptor> virLiveInOld = livenessVirtualReads.get( fn );
 410       if( virLiveInOld != null ) {
 411         virLiveIn.addAll( virLiveInOld );
 412       }
 413       livenessVirtualReads.put( fn, virLiveIn );
 414
 415       vstTable.assertConsistency();
 416
 417     } break;
 418
 419     case FKind.FlatOpNode: {
 420       FlatOpNode fon = (FlatOpNode) fn;
 421
 422       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 423         TempDescriptor lhs = fon.getDest();
 424         TempDescriptor rhs = fon.getLeft();
 425
 426         vstTable.remove( lhs );
 427
 428         Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
 429         while( itr.hasNext() ) {
 430           VariableSourceToken vst = itr.next();
 431
 432           HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 433           ts.add( lhs );
 434
 435           // if this is from a child, keep the source information
 436           if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
 437             vstTable.add( new VariableSourceToken( ts,
 438                                                    vst.getSESE(),
 439                                                    vst.getAge(),
 440                                                    vst.getAddrVar()
 441                                                    )
 442                           );
 443
 444           // otherwise, it's our or an ancestor's token so we
 445           // can assume we have everything we need
 446           } else {
 447             vstTable.add( new VariableSourceToken( ts,
 448                                                    currentSESE,
 449                                                    new Integer( 0 ),
 450                                                    lhs
 451                                                    )
 452                           );
 453           }
 454         }
 455
 456         // only break if this is an ASSIGN op node,
 457         // otherwise fall through to default case
 458
 459         vstTable.assertConsistency();
 460
 461         break;
 462       }
 463     }
 464
 465     // note that FlatOpNode's that aren't ASSIGN
 466     // fall through to this default case
 467     default: {
 468       TempDescriptor [] writeTemps = fn.writesTemps();
 469       if( writeTemps.length > 0 ) {
 470         assert writeTemps.length == 1;
 471
 472         vstTable.remove( writeTemps[0] );
 473
 474         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 475         ts.add( writeTemps[0] );
 476
 477         vstTable.add( new VariableSourceToken( ts,
 478                                                currentSESE,
 479                                                new Integer( 0 ),
 480                                                writeTemps[0]
 481                                              )
 482                       );
 483       }
 484
 485       vstTable.assertConsistency();
 486
 487     } break;
 488
 489     } // end switch
 490
 491     return vstTable;
 492   }
 493
 494
 495   private void computeStallsForward( FlatMethod fm ) {
 496
 497     // start from flat method top, visit every node in
 498     // method exactly once
 499     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 500     flatNodesToVisit.add( fm );
 501
 502     Set<FlatNode> visited = new HashSet<FlatNode>();
 503
 504     while( !flatNodesToVisit.isEmpty() ) {
 505       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 506       FlatNode fn = fnItr.next();
 507
 508       flatNodesToVisit.remove( fn );
 509       visited.add( fn );
 510
 511       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 512       assert seseStack != null;
 513
 514       // use incoming results as "dot statement" or just
 515       // before the current statement
 516       VarSrcTokTable dotST = new VarSrcTokTable();
 517       for( int i = 0; i < fn.numPrev(); i++ ) {
 518         FlatNode nn = fn.getPrev( i );
 519         dotST.merge( variableResults.get( nn ) );
 520       }
 521
 522       computeStalls_nodeActions( fn, dotST, seseStack.peek() );
 523
 524       for( int i = 0; i < fn.numNext(); i++ ) {
 525         FlatNode nn = fn.getNext( i );
 526
 527         if( !visited.contains( nn ) ) {
 528           flatNodesToVisit.add( nn );
 529         }
 530       }
 531     }
 532
 533     if( state.MLPDEBUG ) {
 534       System.out.println( fm.printMethod( codePlan ) );
 535     }
 536   }
 537
 538   private void computeStalls_nodeActions( FlatNode fn,
 539                                           VarSrcTokTable vstTable,
 540                                           FlatSESEEnterNode currentSESE ) {
 541     String s = null;
 542
 543     switch( fn.kind() ) {
 544
 545     case FKind.FlatSESEEnterNode: {
 546       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 547     } break;
 548
 549     case FKind.FlatSESEExitNode: {
 550       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 551     } break;
 552
 553     default: {
 554       Set<VariableSourceToken> stallSet = vstTable.getStallSet( currentSESE );
 555       TempDescriptor[] readarray=fn.readsTemps();
 556       for(int i=0;i<readarray.length;i++) {
 557           TempDescriptor readtmp=readarray[i];
 558           Set<VariableSourceToken> readSet = vstTable.get(readtmp);
 559           //containsAny
 560           for(Iterator<VariableSourceToken> readit=readSet.iterator();readit.hasNext();) {
 561               VariableSourceToken vst=readit.next();
 562               if (stallSet.contains(vst)) {
 563                   if (s==null)
 564                       s="STALL for:";
 565                   s+="("+vst+" "+readtmp+")";
 566               }
 567           }
 568
 569       }
 570     } break;
 571
 572     } // end switch
 573     if (s==null)
 574         s="no op";
 575
 576     codePlan.put( fn, s );
 577   }
 578 }