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