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 Set<FlatSESEEnterNode> allSESEs;
  25
  26   private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
  27   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessRootView;
  28   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessVirtualReads;
  29   private Hashtable< FlatNode, VarSrcTokTable           > variableResults;
  30   private Hashtable< FlatNode, Set<TempDescriptor>      > notAvailableResults;
  31   private Hashtable< FlatNode, CodePlan                 > codePlans;
  32
  33
  34   // use these methods in BuildCode to have access to analysis results
  35   public Set<FlatSESEEnterNode> getAllSESEs() {
  36     return allSESEs;
  37   }
  38
  39   public CodePlan getCodePlan( FlatNode fn ) {
  40     CodePlan cp = codePlans.get( fn );
  41     assert cp != null;
  42     return cp;
  43   }
  44
  45
  46   public MLPAnalysis( State             state,
  47                       TypeUtil          tu,
  48                       CallGraph         callGraph,
  49                       OwnershipAnalysis ownAnalysis
  50                       ) {
  51
  52     double timeStartAnalysis = (double) System.nanoTime();
  53
  54     this.state       = state;
  55     this.typeUtil    = tu;
  56     this.callGraph   = callGraph;
  57     this.ownAnalysis = ownAnalysis;
  58
  59     // initialize analysis data structures
  60     allSESEs = new HashSet<FlatSESEEnterNode>();
  61
  62     seseStacks           = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
  63     livenessVirtualReads = new Hashtable< FlatNode, Set<TempDescriptor>      >();
  64     variableResults      = new Hashtable< FlatNode, VarSrcTokTable           >();
  65     notAvailableResults  = new Hashtable< FlatNode, Set<TempDescriptor>      >();
  66     codePlans            = new Hashtable< FlatNode, CodePlan                 >();
  67
  68
  69     // build an implicit root SESE to wrap contents of main method
  70     rootTree = new SESENode( "root" );
  71     rootSESE = new FlatSESEEnterNode( rootTree );
  72     rootExit = new FlatSESEExitNode ( rootTree );
  73     rootSESE.setFlatExit ( rootExit );
  74     rootExit.setFlatEnter( rootSESE );
  75
  76     FlatMethod fmMain = state.getMethodFlat( tu.getMain() );
  77
  78
  79     // 1st pass
  80     // run analysis on each method that is actually called
  81     // reachability analysis already computed this so reuse
  82     Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
  83     while( methItr.hasNext() ) {
  84       Descriptor d  = methItr.next();
  85       FlatMethod fm = state.getMethodFlat( d );
  86
  87       // find every SESE from methods that may be called
  88       // and organize them into roots and children
  89       buildForestForward( fm );
  90     }
  91
  92
  93     // 2nd pass, results are saved in FlatSESEEnterNode, so
  94     // intermediate results, for safety, are discarded
  95     livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() );
  96
  97
  98     // 3rd pass
  99     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 100     while( methItr.hasNext() ) {
 101       Descriptor d  = methItr.next();
 102       FlatMethod fm = state.getMethodFlat( d );
 103
 104       // starting from roots do a forward, fixed-point
 105       // variable analysis for refinement and stalls
 106       variableAnalysisForward( fm );
 107     }
 108
 109
 110     // 4th pass, compute liveness contribution from
 111     // virtual reads discovered in variable pass
 112     livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() );
 113
 114
 115     // 5th pass
 116     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 117     while( methItr.hasNext() ) {
 118       Descriptor d  = methItr.next();
 119       FlatMethod fm = state.getMethodFlat( d );
 120
 121       // compute what is not available at every program
 122       // point, in a forward fixed-point pass
 123       notAvailableForward( fm );
 124     }
 125
 126
 127     // 5th pass
 128     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 129     while( methItr.hasNext() ) {
 130       Descriptor d  = methItr.next();
 131       FlatMethod fm = state.getMethodFlat( d );
 132
 133       // compute a plan for code injections
 134       computeStallsForward( fm );
 135     }
 136
 137
 138     double timeEndAnalysis = (double) System.nanoTime();
 139     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 140     String treport = String.format( "The mlp analysis took %.3f sec.", dt );
 141     System.out.println( treport );
 142   }
 143
 144
 145   private void buildForestForward( FlatMethod fm ) {
 146
 147     // start from flat method top, visit every node in
 148     // method exactly once, find SESEs and remember
 149     // roots and child relationships
 150     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 151     flatNodesToVisit.add( fm );
 152
 153     Set<FlatNode> visited = new HashSet<FlatNode>();
 154
 155     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 156     seseStackFirst.push( rootSESE );
 157     seseStacks.put( fm, seseStackFirst );
 158
 159     while( !flatNodesToVisit.isEmpty() ) {
 160       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 161       FlatNode fn = fnItr.next();
 162
 163       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 164       assert seseStack != null;
 165
 166       flatNodesToVisit.remove( fn );
 167       visited.add( fn );
 168
 169       buildForest_nodeActions( fn, seseStack, fm );
 170
 171       for( int i = 0; i < fn.numNext(); i++ ) {
 172         FlatNode nn = fn.getNext( i );
 173
 174         if( !visited.contains( nn ) ) {
 175           flatNodesToVisit.add( nn );
 176
 177           // clone stack and send along each analysis path
 178           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 179         }
 180       }
 181     }
 182
 183     if( state.MLPDEBUG ) {
 184       printSESEForest();
 185     }
 186   }
 187
 188   private void buildForest_nodeActions( FlatNode fn,
 189                                         Stack<FlatSESEEnterNode> seseStack,
 190                                         FlatMethod fm ) {
 191     switch( fn.kind() ) {
 192
 193     case FKind.FlatSESEEnterNode: {
 194       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 195
 196       allSESEs.add( fsen );
 197       fsen.setEnclosingFlatMeth( fm );
 198
 199       assert !seseStack.empty();
 200       seseStack.peek().addChild( fsen );
 201       fsen.setParent( seseStack.peek() );
 202       seseStack.push( fsen );
 203     } break;
 204
 205     case FKind.FlatSESEExitNode: {
 206       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 207       assert !seseStack.empty();
 208       FlatSESEEnterNode fsen = seseStack.pop();
 209     } break;
 210
 211     case FKind.FlatReturnNode: {
 212       FlatReturnNode frn = (FlatReturnNode) fn;
 213       if( !seseStack.empty() &&
 214           !seseStack.peek().equals( rootSESE ) ) {
 215         throw new Error( "Error: return statement enclosed within "+seseStack.peek() );
 216       }
 217     } break;
 218
 219     }
 220   }
 221
 222   private void printSESEForest() {
 223     // our forest is actually a tree now that
 224     // there is an implicit root SESE
 225     printSESETree( rootSESE, 0 );
 226     System.out.println( "" );
 227   }
 228
 229   private void printSESETree( FlatSESEEnterNode fsen, int depth ) {
 230     for( int i = 0; i < depth; ++i ) {
 231       System.out.print( "  " );
 232     }
 233     System.out.println( fsen.getPrettyIdentifier() );
 234
 235     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 236     while( childItr.hasNext() ) {
 237       FlatSESEEnterNode fsenChild = childItr.next();
 238       printSESETree( fsenChild, depth + 1 );
 239     }
 240   }
 241
 242
 243     private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
 244                                            boolean toplevel,
 245                                            Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout,
 246                                            FlatExit fexit ) {
 247
 248     // start from an SESE exit, visit nodes in reverse up to
 249     // SESE enter in a fixed-point scheme, where children SESEs
 250     // should already be analyzed and therefore can be skipped
 251     // because child SESE enter node has all necessary info
 252     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 253
 254     FlatSESEExitNode fsexn = fsen.getFlatExit();
 255     if (toplevel) {
 256         //handle root SESE
 257         flatNodesToVisit.add( fexit );
 258     } else
 259         flatNodesToVisit.add( fsexn );
 260     Hashtable<FlatNode, Set<TempDescriptor>> livenessResults=new Hashtable<FlatNode, Set<TempDescriptor>>();
 261
 262     if (toplevel==true)
 263         liveout=new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
 264
 265     while( !flatNodesToVisit.isEmpty() ) {
 266       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 267       flatNodesToVisit.remove( fn );
 268
 269       Set<TempDescriptor> prev = livenessResults.get( fn );
 270
 271       // merge sets from control flow joins
 272       Set<TempDescriptor> u = new HashSet<TempDescriptor>();
 273       for( int i = 0; i < fn.numNext(); i++ ) {
 274         FlatNode nn = fn.getNext( i );
 275         Set<TempDescriptor> s = livenessResults.get( nn );
 276         if( s != null ) {
 277           u.addAll( s );
 278         }
 279       }
 280
 281       Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
 282
 283       // if a new result, schedule backward nodes for analysis
 284       if(!curr.equals(prev)) {
 285         livenessResults.put( fn, curr );
 286
 287         // don't flow backwards past current SESE enter
 288         if( !fn.equals( fsen ) ) {
 289           for( int i = 0; i < fn.numPrev(); i++ ) {
 290             FlatNode nn = fn.getPrev( i );
 291             flatNodesToVisit.add( nn );
 292           }
 293         }
 294       }
 295     }
 296
 297     Set<TempDescriptor> s = livenessResults.get( fsen );
 298     if( s != null ) {
 299       fsen.addInVarSet( s );
 300     }
 301
 302     if( state.MLPDEBUG ) {
 303       System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
 304       Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
 305       while( tItr.hasNext() ) {
 306         System.out.println( "  "+tItr.next() );
 307       }
 308       System.out.println( "and out-set:" );
 309       tItr = fsen.getOutVarSet().iterator();
 310       while( tItr.hasNext() ) {
 311         System.out.println( "  "+tItr.next() );
 312       }
 313       System.out.println( "" );
 314     }
 315
 316     // remember liveness per node from the root view as the
 317     // global liveness of variables for later passes to use
 318     if( toplevel == true ) {
 319       livenessRootView = livenessResults;
 320     }
 321
 322     // post-order traversal, so do children first
 323     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 324     while( childItr.hasNext() ) {
 325       FlatSESEEnterNode fsenChild = childItr.next();
 326       livenessAnalysisBackward( fsenChild, false, liveout, null);
 327     }
 328   }
 329
 330   private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
 331                                                     Set<TempDescriptor> liveIn,
 332                                                     FlatSESEEnterNode currentSESE,
 333                                                     boolean toplevel,
 334                                                     Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
 335
 336     switch( fn.kind() ) {
 337
 338     case FKind.FlatSESEExitNode:
 339       if (toplevel==true) {
 340           FlatSESEExitNode exitn=(FlatSESEExitNode) fn;
 341         //update liveout set for FlatSESEExitNode
 342           if (!liveout.containsKey(exitn))
 343             liveout.put(exitn, new HashSet<TempDescriptor>());
 344           liveout.get(exitn).addAll(liveIn);
 345       }
 346       // no break, sese exits should also execute default actions
 347
 348     default: {
 349       // handle effects of statement in reverse, writes then reads
 350       TempDescriptor [] writeTemps = fn.writesTemps();
 351       for( int i = 0; i < writeTemps.length; ++i ) {
 352         liveIn.remove( writeTemps[i] );
 353
 354         if (!toplevel) {
 355           FlatSESEExitNode exitnode=currentSESE.getFlatExit();
 356           Set<TempDescriptor> livetemps=liveout.get(exitnode);
 357           if (livetemps.contains(writeTemps[i])) {
 358             //write to a live out temp...
 359             //need to put in SESE liveout set
 360             currentSESE.addOutVar(writeTemps[i]);
 361           }
 362         }
 363       }
 364
 365       TempDescriptor [] readTemps = fn.readsTemps();
 366       for( int i = 0; i < readTemps.length; ++i ) {
 367         liveIn.add( readTemps[i] );
 368       }
 369
 370       Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
 371       if( virtualReadTemps != null ) {
 372         Iterator<TempDescriptor> vrItr = virtualReadTemps.iterator();
 373         while( vrItr.hasNext() ) {
 374           TempDescriptor vrt = vrItr.next();
 375           liveIn.add( vrt );
 376         }
 377       }
 378     } break;
 379
 380     } // end switch
 381
 382     return liveIn;
 383   }
 384
 385
 386   private void variableAnalysisForward( FlatMethod fm ) {
 387
 388     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 389     flatNodesToVisit.add( fm );
 390
 391     while( !flatNodesToVisit.isEmpty() ) {
 392       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 393       flatNodesToVisit.remove( fn );
 394
 395       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 396       assert seseStack != null;
 397
 398       VarSrcTokTable prev = variableResults.get( fn );
 399
 400       // merge sets from control flow joins
 401       VarSrcTokTable inUnion = new VarSrcTokTable();
 402       for( int i = 0; i < fn.numPrev(); i++ ) {
 403         FlatNode nn = fn.getPrev( i );
 404         VarSrcTokTable incoming = variableResults.get( nn );
 405         inUnion.merge( incoming );
 406       }
 407
 408       VarSrcTokTable curr = variable_nodeActions( fn, inUnion, seseStack.peek() );
 409
 410       // if a new result, schedule forward nodes for analysis
 411       if( !curr.equals( prev ) ) {
 412         variableResults.put( fn, curr );
 413
 414         for( int i = 0; i < fn.numNext(); i++ ) {
 415           FlatNode nn = fn.getNext( i );
 416           flatNodesToVisit.add( nn );
 417         }
 418       }
 419     }
 420   }
 421
 422   private VarSrcTokTable variable_nodeActions( FlatNode fn,
 423                                                VarSrcTokTable vstTable,
 424                                                FlatSESEEnterNode currentSESE ) {
 425     switch( fn.kind() ) {
 426
 427     case FKind.FlatSESEEnterNode: {
 428       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 429       assert fsen.equals( currentSESE );
 430       vstTable.age( currentSESE );
 431       vstTable.assertConsistency();
 432     } break;
 433
 434     case FKind.FlatSESEExitNode: {
 435       FlatSESEExitNode  fsexn = (FlatSESEExitNode)  fn;
 436       FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 437       assert currentSESE.getChildren().contains( fsen );
 438       vstTable.remapChildTokens( fsen );
 439
 440       Set<TempDescriptor> liveIn       = currentSESE.getInVarSet();
 441       Set<TempDescriptor> virLiveIn    = vstTable.removeParentAndSiblingTokens( fsen, liveIn );
 442       Set<TempDescriptor> virLiveInOld = livenessVirtualReads.get( fn );
 443       if( virLiveInOld != null ) {
 444         virLiveIn.addAll( virLiveInOld );
 445       }
 446       livenessVirtualReads.put( fn, virLiveIn );
 447       vstTable.assertConsistency();
 448     } break;
 449
 450     case FKind.FlatOpNode: {
 451       FlatOpNode fon = (FlatOpNode) fn;
 452
 453       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 454         TempDescriptor lhs = fon.getDest();
 455         TempDescriptor rhs = fon.getLeft();
 456
 457         vstTable.remove( lhs );
 458
 459         Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
 460
 461         Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
 462         while( itr.hasNext() ) {
 463           VariableSourceToken vst = itr.next();
 464
 465           HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 466           ts.add( lhs );
 467
 468           // if this is from a child, keep the source information
 469           if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
 470             forAddition.add( new VariableSourceToken( ts,
 471                                                       vst.getSESE(),
 472                                                       vst.getAge(),
 473                                                       vst.getAddrVar()
 474                                                       )
 475                              );
 476
 477           // otherwise, it's our or an ancestor's token so we
 478           // can assume we have everything we need
 479           } else {
 480             forAddition.add( new VariableSourceToken( ts,
 481                                                       currentSESE,
 482                                                       new Integer( 0 ),
 483                                                       lhs
 484                                                       )
 485                              );
 486           }
 487         }
 488
 489         vstTable.addAll( forAddition );
 490
 491         // only break if this is an ASSIGN op node,
 492         // otherwise fall through to default case
 493         vstTable.assertConsistency();
 494         break;
 495       }
 496     }
 497
 498     // note that FlatOpNode's that aren't ASSIGN
 499     // fall through to this default case
 500     default: {
 501       TempDescriptor [] writeTemps = fn.writesTemps();
 502       if( writeTemps.length > 0 ) {
 503         assert writeTemps.length == 1;
 504
 505         vstTable.remove( writeTemps[0] );
 506
 507         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 508         ts.add( writeTemps[0] );
 509
 510         vstTable.add( new VariableSourceToken( ts,
 511                                                currentSESE,
 512                                                new Integer( 0 ),
 513                                                writeTemps[0]
 514                                              )
 515                       );
 516       }
 517
 518       vstTable.assertConsistency();
 519     } break;
 520
 521     } // end switch
 522
 523     return vstTable;
 524   }
 525
 526
 527   private void notAvailableForward( FlatMethod fm ) {
 528
 529     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 530     flatNodesToVisit.add( fm );
 531
 532     while( !flatNodesToVisit.isEmpty() ) {
 533       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 534       flatNodesToVisit.remove( fn );
 535
 536       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 537       assert seseStack != null;
 538
 539       Set<TempDescriptor> prev = notAvailableResults.get( fn );
 540
 541       Set<TempDescriptor> inUnion = new HashSet<TempDescriptor>();
 542       for( int i = 0; i < fn.numPrev(); i++ ) {
 543         FlatNode nn = fn.getPrev( i );
 544         Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
 545         if( notAvailIn != null ) {
 546           inUnion.addAll( notAvailIn );
 547         }
 548       }
 549
 550       Set<TempDescriptor> curr = notAvailable_nodeActions( fn, inUnion, seseStack.peek() );
 551
 552       // if a new result, schedule forward nodes for analysis
 553       if( !curr.equals( prev ) ) {
 554         notAvailableResults.put( fn, curr );
 555
 556         for( int i = 0; i < fn.numNext(); i++ ) {
 557           FlatNode nn = fn.getNext( i );
 558           flatNodesToVisit.add( nn );
 559         }
 560       }
 561     }
 562   }
 563
 564   private Set<TempDescriptor> notAvailable_nodeActions( FlatNode fn,
 565                                                         Set<TempDescriptor> notAvailSet,
 566                                                         FlatSESEEnterNode currentSESE ) {
 567
 568     // any temps that are removed from the not available set
 569     // at this node should be marked in this node's code plan
 570     // as temps to be grabbed at runtime!
 571
 572     switch( fn.kind() ) {
 573
 574     case FKind.FlatSESEEnterNode: {
 575       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 576       assert fsen.equals( currentSESE );
 577       notAvailSet.clear();
 578     } break;
 579
 580     case FKind.FlatSESEExitNode: {
 581       FlatSESEExitNode  fsexn = (FlatSESEExitNode)  fn;
 582       FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 583       assert currentSESE.getChildren().contains( fsen );
 584
 585       Set<TempDescriptor> liveTemps = livenessRootView.get( fn );
 586       assert liveTemps != null;
 587
 588       VarSrcTokTable vstTable = variableResults.get( fn );
 589       assert vstTable != null;
 590
 591       Set<TempDescriptor> notAvailAtEnter = notAvailableResults.get( fsen );
 592       assert notAvailAtEnter != null;
 593
 594       Iterator<TempDescriptor> tdItr = liveTemps.iterator();
 595       while( tdItr.hasNext() ) {
 596         TempDescriptor td = tdItr.next();
 597
 598         if( vstTable.get( fsen, td ).size() > 0 ) {
 599           // there is at least one child token for this variable
 600           notAvailSet.add( td );
 601           continue;
 602         }
 603
 604         if( notAvailAtEnter.contains( td ) ) {
 605           // wasn't available at enter, not available now
 606           notAvailSet.add( td );
 607           continue;
 608         }
 609       }
 610     } break;
 611
 612     case FKind.FlatOpNode: {
 613       FlatOpNode fon = (FlatOpNode) fn;
 614
 615       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 616         TempDescriptor lhs = fon.getDest();
 617         TempDescriptor rhs = fon.getLeft();
 618
 619         // copy makes lhs same availability as rhs
 620         if( notAvailSet.contains( rhs ) ) {
 621           notAvailSet.add( lhs );
 622         } else {
 623           notAvailSet.remove( lhs );
 624         }
 625
 626         // only break if this is an ASSIGN op node,
 627         // otherwise fall through to default case
 628         break;
 629       }
 630     }
 631
 632     // note that FlatOpNode's that aren't ASSIGN
 633     // fall through to this default case
 634     default: {
 635       TempDescriptor [] writeTemps = fn.writesTemps();
 636       for( int i = 0; i < writeTemps.length; i++ ) {
 637         TempDescriptor wTemp = writeTemps[i];
 638         notAvailSet.remove( wTemp );
 639       }
 640       TempDescriptor [] readTemps = fn.readsTemps();
 641       for( int i = 0; i < readTemps.length; i++ ) {
 642         TempDescriptor rTemp = readTemps[i];
 643         notAvailSet.remove( rTemp );
 644
 645         // if this variable has exactly one source, mark everything
 646         // else from that source as available as well
 647         VarSrcTokTable table = variableResults.get( fn );
 648         Set<VariableSourceToken> srcs = table.get( rTemp );
 649
 650         if( srcs.size() == 1 ) {
 651           VariableSourceToken vst = srcs.iterator().next();
 652
 653           Iterator<VariableSourceToken> availItr = table.get( vst.getSESE(),
 654                                                               vst.getAge()
 655                                                             ).iterator();
 656           while( availItr.hasNext() ) {
 657             VariableSourceToken vstAlsoAvail = availItr.next();
 658             notAvailSet.removeAll( vstAlsoAvail.getRefVars() );
 659           }
 660         }
 661       }
 662     } break;
 663
 664     } // end switch
 665
 666     return notAvailSet;
 667   }
 668
 669
 670   private void computeStallsForward( FlatMethod fm ) {
 671
 672     // start from flat method top, visit every node in
 673     // method exactly once
 674     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 675     flatNodesToVisit.add( fm );
 676
 677     Set<FlatNode> visited = new HashSet<FlatNode>();
 678
 679     while( !flatNodesToVisit.isEmpty() ) {
 680       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 681       FlatNode fn = fnItr.next();
 682
 683       flatNodesToVisit.remove( fn );
 684       visited.add( fn );
 685
 686       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 687       assert seseStack != null;
 688
 689       // use incoming results as "dot statement" or just
 690       // before the current statement
 691       VarSrcTokTable dotSTtable = new VarSrcTokTable();
 692       for( int i = 0; i < fn.numPrev(); i++ ) {
 693         FlatNode nn = fn.getPrev( i );
 694         dotSTtable.merge( variableResults.get( nn ) );
 695       }
 696
 697       // find dt-st notAvailableSet also
 698       Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
 699       for( int i = 0; i < fn.numPrev(); i++ ) {
 700         FlatNode nn = fn.getPrev( i );
 701         Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
 702         if( notAvailIn != null ) {
 703           dotSTnotAvailSet.addAll( notAvailIn );
 704         }
 705       }
 706
 707       computeStalls_nodeActions( fn, dotSTtable, dotSTnotAvailSet, seseStack.peek() );
 708
 709       for( int i = 0; i < fn.numNext(); i++ ) {
 710         FlatNode nn = fn.getNext( i );
 711
 712         if( !visited.contains( nn ) ) {
 713           flatNodesToVisit.add( nn );
 714         }
 715       }
 716     }
 717
 718     if( state.MLPDEBUG ) {
 719       //System.out.println( fm.printMethod( livenessRootView ) );
 720       //System.out.println( fm.printMethod( variableResults ) );
 721       //System.out.println( fm.printMethod( notAvailableResults ) );
 722       System.out.println( fm.printMethod( codePlans ) );
 723     }
 724   }
 725
 726   private void computeStalls_nodeActions( FlatNode fn,
 727                                           VarSrcTokTable vstTable,
 728                                           Set<TempDescriptor> notAvailSet,
 729                                           FlatSESEEnterNode currentSESE ) {
 730     String before = null;
 731     String after  = null;
 732
 733     switch( fn.kind() ) {
 734
 735     case FKind.FlatSESEEnterNode: {
 736       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 737     } break;
 738
 739     case FKind.FlatSESEExitNode: {
 740       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 741     } break;
 742
 743     case FKind.FlatOpNode: {
 744       FlatOpNode fon = (FlatOpNode) fn;
 745
 746       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 747         // if this is an op node, don't stall, copy
 748         // source and delay until we need to use value
 749
 750         // only break if this is an ASSIGN op node,
 751         // otherwise fall through to default case
 752         break;
 753       }
 754     }
 755
 756     // note that FlatOpNode's that aren't ASSIGN
 757     // fall through to this default case
 758     default: {
 759       // decide if we must stall for variables dereferenced at this node
 760       Set<VariableSourceToken> stallSet = vstTable.getStallSet( currentSESE );
 761
 762       TempDescriptor[] readarray = fn.readsTemps();
 763       for( int i = 0; i < readarray.length; i++ ) {
 764         TempDescriptor readtmp = readarray[i];
 765
 766         // ignore temps that are definitely available
 767         // when considering to stall on it
 768         if( !notAvailSet.contains( readtmp ) ) {
 769           continue;
 770         }
 771
 772         Set<VariableSourceToken> readSet = vstTable.get( readtmp );
 773
 774         //Two cases:
 775
 776         //1) Multiple token/age pairs or unknown age: Stall for
 777         //dynamic name only.
 778
 779
 780
 781         //2) Single token/age pair: Stall for token/age pair, and copy
 782         //all live variables with same token/age pair at the same
 783         //time.  This is the same stuff that the notavaialable analysis
 784         //marks as now available.
 785
 786         //VarSrcTokTable table = variableResults.get( fn );
 787         //Set<VariableSourceToken> srcs = table.get( rTemp );
 788
 789         //XXXXXXXXXX: Note: We have to generate code to do these
 790         //copies in the codeplan.  Note we should only copy the
 791         //variables that are live!
 792
 793         /*
 794         if( srcs.size() == 1 ) {
 795           VariableSourceToken vst = srcs.iterator().next();
 796
 797           Iterator<VariableSourceToken> availItr = table.get( vst.getSESE(),
 798                                                               vst.getAge()
 799                                                             ).iterator();
 800           while( availItr.hasNext() ) {
 801             VariableSourceToken vstAlsoAvail = availItr.next();
 802             notAvailSet.removeAll( vstAlsoAvail.getRefVars() );
 803           }
 804         }
 805         */
 806
 807
 808         // assert notAvailSet.containsAll( writeSet );
 809
 810
 811         for( Iterator<VariableSourceToken> readit = readSet.iterator();
 812              readit.hasNext(); ) {
 813           VariableSourceToken vst = readit.next();
 814           if( stallSet.contains( vst ) ) {
 815             if( before == null ) {
 816               before = "**STALL for:";
 817             }
 818             before += "("+vst+" "+readtmp+")";
 819           }
 820         }
 821       }
 822     } break;
 823
 824     } // end switch
 825
 826
 827     // if any variable at this node has a static source (exactly one sese)
 828     // but goes to a dynamic source at a next node, write its dynamic addr
 829     Set<VariableSourceToken> static2dynamicSet = new HashSet<VariableSourceToken>();
 830     for( int i = 0; i < fn.numNext(); i++ ) {
 831       FlatNode nn = fn.getNext( i );
 832       VarSrcTokTable nextVstTable = variableResults.get( nn );
 833       assert nextVstTable != null;
 834       static2dynamicSet.addAll( vstTable.getStatic2DynamicSet( nextVstTable ) );
 835     }
 836     Iterator<VariableSourceToken> vstItr = static2dynamicSet.iterator();
 837     while( vstItr.hasNext() ) {
 838       VariableSourceToken vst = vstItr.next();
 839       if( after == null ) {
 840         after = "** Write dynamic: ";
 841       }
 842       after += "("+vst+")";
 843     }
 844
 845
 846     if( before == null ) {
 847       before = "";
 848     }
 849
 850     if( after == null ) {
 851       after = "";
 852     }
 853
 854     codePlans.put( fn, new CodePlan( before, after ) );
 855   }
 856 }