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, VarSrcTokTable           > 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,          VarSrcTokTable  >();
  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       VarSrcTokTable prev = livenessResults.get( fn );
 243
 244       // merge sets from control flow joins
 245       VarSrcTokTable inUnion = new VarSrcTokTable();
 246       for( int i = 0; i < fn.numNext(); i++ ) {
 247         FlatNode nn = fn.getNext( i );
 248         inUnion.merge( livenessResults.get( nn ) );
 249       }
 250
 251       VarSrcTokTable curr = liveness_nodeActions( fn, inUnion, fsen );
 252
 253       // if a new result, schedule backward nodes for analysis
 254       if( !curr.equals( prev ) ) {
 255
 256         livenessResults.put( fn, curr );
 257
 258         // don't flow backwards past current SESE enter
 259         if( !fn.equals( fsen ) ) {
 260           for( int i = 0; i < fn.numPrev(); i++ ) {
 261             FlatNode nn = fn.getPrev( i );
 262             flatNodesToVisit.add( nn );
 263           }
 264         }
 265       }
 266     }
 267
 268     fsen.addInVarSet( livenessResults.get( fsen ).get() );
 269
 270     if( state.MLPDEBUG ) {
 271       System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
 272       Iterator<VariableSourceToken> tItr = fsen.getInVarSet().iterator();
 273       while( tItr.hasNext() ) {
 274         System.out.println( "  "+tItr.next() );
 275       }
 276       /*
 277       System.out.println( "and out-set:" );
 278       tItr = fsen.getOutVarSet().iterator();
 279       while( tItr.hasNext() ) {
 280         System.out.println( "  "+tItr.next() );
 281       }
 282       */
 283       System.out.println( "" );
 284     }
 285   }
 286
 287   private VarSrcTokTable liveness_nodeActions( FlatNode fn,
 288                                                VarSrcTokTable vstTable,
 289                                                FlatSESEEnterNode currentSESE ) {
 290     switch( fn.kind() ) {
 291
 292     case FKind.FlatSESEEnterNode: {
 293       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 294
 295       // only age if this is a child SESE, not the current
 296       if( !fsen.equals( currentSESE ) ) {
 297         vstTable = vstTable.age( currentSESE );
 298       }
 299     } break;
 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         vstTable.remove( writeTemps[i] );
 306         currentSESE.addOutVar( new VariableSourceToken( currentSESE,
 307                                                         writeTemps[i],
 308                                                         new Integer( 0 ) ) );
 309       }
 310
 311       TempDescriptor [] readTemps = fn.readsTemps();
 312       for( int i = 0; i < readTemps.length; ++i ) {
 313         vstTable.add( new VariableSourceToken( currentSESE,
 314                                                readTemps[i],
 315                                                new Integer( 0 ) ) );
 316       }
 317     } break;
 318
 319     } // end switch
 320
 321     return vstTable;
 322   }
 323
 324
 325   private void variableAnalysisForward( FlatSESEEnterNode fsen ) {
 326
 327     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 328     flatNodesToVisit.add( fsen );
 329
 330     while( !flatNodesToVisit.isEmpty() ) {
 331       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 332       flatNodesToVisit.remove( fn );
 333
 334       VarSrcTokTable prev = variableResults.get( fn );
 335
 336       // merge sets from control flow joins
 337       VarSrcTokTable inUnion = new VarSrcTokTable();
 338       for( int i = 0; i < fn.numPrev(); i++ ) {
 339         FlatNode nn = fn.getPrev( i );
 340         inUnion.merge( variableResults.get( nn ) );
 341       }
 342
 343       VarSrcTokTable curr = variable_nodeActions( fn, inUnion, fsen );
 344
 345       // if a new result, schedule backward nodes for analysis
 346       if( !curr.equals( prev ) ) {
 347
 348         variableResults.put( fn, curr );
 349
 350         // don't flow backwards past SESE enter
 351         if( !fn.equals( fsen ) ) {
 352           for( int i = 0; i < fn.numPrev(); i++ ) {
 353             FlatNode nn = fn.getPrev( i );
 354             flatNodesToVisit.add( nn );
 355           }
 356         }
 357       }
 358     }
 359
 360     fsen.addInVarSet( variableResults.get( fsen ).get() );
 361
 362     if( state.MLPDEBUG ) {
 363       System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
 364       Iterator<VariableSourceToken> tItr = fsen.getInVarSet().iterator();
 365       while( tItr.hasNext() ) {
 366         System.out.println( "  "+tItr.next() );
 367       }
 368       System.out.println( "and out-set:" );
 369       tItr = fsen.getOutVarSet().iterator();
 370       while( tItr.hasNext() ) {
 371         System.out.println( "  "+tItr.next() );
 372       }
 373       System.out.println( "" );
 374     }
 375   }
 376
 377   private VarSrcTokTable variable_nodeActions( FlatNode fn,
 378                                                VarSrcTokTable vstTable,
 379                                                FlatSESEEnterNode currentSESE ) {
 380     switch( fn.kind() ) {
 381
 382
 383     default: {
 384     } break;
 385
 386     } // end switch
 387
 388     return vstTable;
 389   }
 390 }