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