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 Set<FlatSESEEnterNode> seseRoots;
  21   private SESENode          rootTree;
  22   private FlatSESEEnterNode rootSESE;
  23   private FlatSESEExitNode  rootExit;
  24
  25   private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
  26   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessResults;
  27   private Hashtable< FlatNode, VarSrcTokTable           > variableResults;
  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     seseRoots       = new HashSet<FlatSESEEnterNode>();
  45     seseStacks      = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
  46     livenessResults = new Hashtable< FlatNode, Set<TempDescriptor>      >();
  47     variableResults = new Hashtable< FlatNode, VarSrcTokTable           >();
  48
  49     // build an implicit root SESE to wrap contents of main method
  50     /*
  51     rootTree = new SESENode( "root" );
  52     rootSESE = new FlatSESEEnterNode( rootTree );
  53     rootExit = new FlatSESEExitNode ( rootTree );
  54     rootSESE.setFlatExit ( rootExit );
  55     rootExit.setFlatEnter( rootSESE );
  56     seseRoots.add( rootSESE );
  57     */
  58
  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
  65       FlatMethod fm;
  66       if( d instanceof MethodDescriptor ) {
  67         fm = state.getMethodFlat( (MethodDescriptor) d);
  68       } else {
  69         assert d instanceof TaskDescriptor;
  70         fm = state.getMethodFlat( (TaskDescriptor) d);
  71       }
  72
  73       // find every SESE from methods that may be called
  74       // and organize them into roots and children
  75       buildForestForward( fm );
  76
  77       if( state.MLPDEBUG ) {
  78         printSESEForest();
  79       }
  80     }
  81
  82     Iterator<FlatSESEEnterNode> seseItr = seseRoots.iterator();
  83     while( seseItr.hasNext() ) {
  84       FlatSESEEnterNode fsen = seseItr.next();
  85
  86       // do a post-order traversal of the forest so that
  87       // a child is analyzed before a parent.  Start from
  88       // SESE's exit and do a backward data-flow analysis
  89       // for the source of variables
  90       livenessAnalysisBackward( fsen );
  91     }
  92
  93     /*
  94     seseItr = seseRoots.iterator();
  95     while( seseItr.hasNext() ) {
  96       FlatSESEEnterNode fsen = seseItr.next();
  97
  98       // starting from roots do a forward, fixed-point
  99       // variable analysis for refinement and stalls
 100       variableAnalysisForward( fsen );
 101     }
 102     */
 103
 104     double timeEndAnalysis = (double) System.nanoTime();
 105     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 106     String treport = String.format( "The mlp analysis took %.3f sec.", dt );
 107     System.out.println( treport );
 108   }
 109
 110   private void buildForestForward( FlatMethod fm ) {
 111
 112     // start from flat method top, visit every node in
 113     // method exactly once, find SESEs and remember
 114     // roots and child relationships
 115     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 116     flatNodesToVisit.add( fm );
 117
 118     Set<FlatNode> visited = new HashSet<FlatNode>();
 119
 120     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 121     //seseStackFirst.push( rootSESE );
 122     seseStacks.put( fm, seseStackFirst );
 123
 124     while( !flatNodesToVisit.isEmpty() ) {
 125       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 126       FlatNode fn = fnItr.next();
 127
 128       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 129       assert seseStack != null;
 130
 131       flatNodesToVisit.remove( fn );
 132       visited.add( fn );
 133
 134       buildForest_nodeActions( fn, seseStack );
 135
 136       for( int i = 0; i < fn.numNext(); i++ ) {
 137         FlatNode nn = fn.getNext( i );
 138
 139         if( !visited.contains( nn ) ) {
 140           flatNodesToVisit.add( nn );
 141
 142           // clone stack and send along each analysis path
 143           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 144         }
 145       }
 146     }
 147   }
 148
 149   private void buildForest_nodeActions( FlatNode fn,
 150                                         Stack<FlatSESEEnterNode> seseStack ) {
 151     switch( fn.kind() ) {
 152
 153     case FKind.FlatSESEEnterNode: {
 154       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 155
 156       if( seseStack.empty() ) {
 157         seseRoots.add( fsen );
 158       } else {
 159         seseStack.peek().addChild( fsen );
 160       }
 161       seseStack.push( fsen );
 162     } break;
 163
 164     case FKind.FlatSESEExitNode: {
 165       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 166
 167       assert !seseStack.empty();
 168       FlatSESEEnterNode fsen = seseStack.pop();
 169     } break;
 170
 171     case FKind.FlatReturnNode: {
 172       FlatReturnNode frn = (FlatReturnNode) fn;
 173       if( !seseStack.empty() ) {
 174         throw new Error( "Error: return statement enclosed within "+seseStack.peek() );
 175       }
 176     } break;
 177
 178     }
 179   }
 180
 181   private void printSESEForest() {
 182     // we are assuming an implicit root SESE in the main method
 183     // so assert that our forest is actually a tree
 184     assert seseRoots.size() == 1;
 185
 186     System.out.println( "SESE Forest:" );
 187     Iterator<FlatSESEEnterNode> seseItr = seseRoots.iterator();
 188     while( seseItr.hasNext() ) {
 189       FlatSESEEnterNode fsen = seseItr.next();
 190       printSESETree( fsen, 0 );
 191       System.out.println( "" );
 192     }
 193   }
 194
 195   private void printSESETree( FlatSESEEnterNode fsen, int depth ) {
 196     for( int i = 0; i < depth; ++i ) {
 197       System.out.print( "  " );
 198     }
 199     System.out.println( fsen.getPrettyIdentifier() );
 200
 201     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 202     while( childItr.hasNext() ) {
 203       FlatSESEEnterNode fsenChild = childItr.next();
 204       printSESETree( fsenChild, depth + 1 );
 205     }
 206   }
 207
 208
 209   private void livenessAnalysisBackward( FlatSESEEnterNode fsen ) {
 210
 211     // post-order traversal, so do children first
 212     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 213     while( childItr.hasNext() ) {
 214       FlatSESEEnterNode fsenChild = childItr.next();
 215       livenessAnalysisBackward( fsenChild );
 216     }
 217
 218     // start from an SESE exit, visit nodes in reverse up to
 219     // SESE enter in a fixed-point scheme, where children SESEs
 220     // should already be analyzed and therefore can be skipped
 221     // because child SESE enter node has all necessary info
 222     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 223     FlatSESEExitNode fsexn = fsen.getFlatExit();
 224     flatNodesToVisit.add( fsexn );
 225     /*
 226     for( int i = 0; i < fsexn.numPrev(); i++ ) {
 227       FlatNode nn = fsexn.getPrev( i );
 228       flatNodesToVisit.add( nn );
 229     }
 230     */
 231
 232     while( !flatNodesToVisit.isEmpty() ) {
 233       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 234       flatNodesToVisit.remove( fn );
 235
 236       /*
 237       if( fn.kind() == FKind.FlatSESEExitNode ) {
 238         fn = ((FlatSESEExitNode)fn).getFlatEnter();
 239       }
 240       */
 241
 242       Set<TempDescriptor> prev = livenessResults.get( fn );
 243
 244       // merge sets from control flow joins
 245       Set<TempDescriptor> u = new HashSet<TempDescriptor>();
 246       for( int i = 0; i < fn.numNext(); i++ ) {
 247         FlatNode nn = fn.getNext( i );
 248         Set<TempDescriptor> s = livenessResults.get( nn );
 249         if( s != null ) {
 250           u.addAll( s );
 251         }
 252       }
 253
 254       Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen );
 255
 256       // if a new result, schedule backward nodes for analysis
 257       if( !curr.equals( prev ) ) {
 258
 259         livenessResults.put( fn, curr );
 260
 261         // don't flow backwards past current SESE enter
 262         if( !fn.equals( fsen ) ) {
 263           for( int i = 0; i < fn.numPrev(); i++ ) {
 264             FlatNode nn = fn.getPrev( i );
 265             flatNodesToVisit.add( nn );
 266           }
 267         }
 268       }
 269     }
 270
 271     Set<TempDescriptor> s = livenessResults.get( fsen );
 272     if( s != null ) {
 273       fsen.addInVarSet( s );
 274     }
 275
 276     if( state.MLPDEBUG ) {
 277       System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
 278       Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
 279       while( tItr.hasNext() ) {
 280         System.out.println( "  "+tItr.next() );
 281       }
 282       /*
 283       System.out.println( "and out-set:" );
 284       tItr = fsen.getOutVarSet().iterator();
 285       while( tItr.hasNext() ) {
 286         System.out.println( "  "+tItr.next() );
 287       }
 288       */
 289       System.out.println( "" );
 290     }
 291   }
 292
 293   private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
 294                                                     Set<TempDescriptor> liveIn,
 295                                                     FlatSESEEnterNode currentSESE ) {
 296     switch( fn.kind() ) {
 297
 298     default: {
 299       // handle effects of statement in reverse, writes then reads
 300       TempDescriptor [] writeTemps = fn.writesTemps();
 301       for( int i = 0; i < writeTemps.length; ++i ) {
 302         liveIn.remove( writeTemps[i] );
 303       }
 304
 305       TempDescriptor [] readTemps = fn.readsTemps();
 306       for( int i = 0; i < readTemps.length; ++i ) {
 307         liveIn.add( readTemps[i] );
 308       }
 309     } break;
 310
 311     } // end switch
 312
 313     return liveIn;
 314   }
 315
 316
 317   private void variableAnalysisForward( FlatSESEEnterNode fsen ) {
 318     /*
 319     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 320     flatNodesToVisit.add( fsen );
 321
 322     while( !flatNodesToVisit.isEmpty() ) {
 323       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 324       flatNodesToVisit.remove( fn );
 325
 326       VarSrcTokTable prev = variableResults.get( fn );
 327
 328       // merge sets from control flow joins
 329       VarSrcTokTable inUnion = new VarSrcTokTable();
 330       for( int i = 0; i < fn.numPrev(); i++ ) {
 331         FlatNode nn = fn.getPrev( i );
 332         inUnion.merge( variableResults.get( nn ) );
 333       }
 334
 335       VarSrcTokTable curr = variable_nodeActions( fn, inUnion, fsen );
 336
 337       // if a new result, schedule backward nodes for analysis
 338       if( !curr.equals( prev ) ) {
 339
 340         variableResults.put( fn, curr );
 341
 342         // don't flow backwards past SESE enter
 343         if( !fn.equals( fsen ) ) {
 344           for( int i = 0; i < fn.numPrev(); i++ ) {
 345             FlatNode nn = fn.getPrev( i );
 346             flatNodesToVisit.add( nn );
 347           }
 348         }
 349       }
 350     }
 351
 352     fsen.addInVarSet( variableResults.get( fsen ).get() );
 353
 354     if( state.MLPDEBUG ) {
 355       System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
 356       Iterator<VariableSourceToken> tItr = fsen.getInVarSet().iterator();
 357       while( tItr.hasNext() ) {
 358         System.out.println( "  "+tItr.next() );
 359       }
 360       System.out.println( "and out-set:" );
 361       tItr = fsen.getOutVarSet().iterator();
 362       while( tItr.hasNext() ) {
 363         System.out.println( "  "+tItr.next() );
 364       }
 365       System.out.println( "" );
 366     }
 367     */
 368   }
 369
 370   private VarSrcTokTable variable_nodeActions( FlatNode fn,
 371                                                VarSrcTokTable vstTable,
 372                                                FlatSESEEnterNode currentSESE ) {
 373     switch( fn.kind() ) {
 374
 375
 376     default: {
 377     } break;
 378
 379     } // end switch
 380
 381     return vstTable;
 382   }
 383 }