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