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