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
  21   // an implicit SESE is automatically spliced into
  22   // the IR graph around the C main before this analysis--it
  23   // is nothing special except that we can make assumptions
  24   // about it, such as the whole program ends when it ends
  25   private FlatSESEEnterNode mainSESE;
  26
  27   // SESEs that are the root of an SESE tree belong to this
  28   // set--the main SESE is always a root, statically SESEs
  29   // inside methods are a root because we don't know how they
  30   // will fit into the runtime tree of SESEs
  31   private Set<FlatSESEEnterNode> rootSESEs;
  32
  33   // simply a set of every reachable SESE in the program, not
  34   // including caller placeholder SESEs
  35   private Set<FlatSESEEnterNode> allSESEs;
  36
  37
  38   // A mapping of flat nodes to the stack of SESEs for that node, where
  39   // an SESE is the child of the SESE directly below it on the stack.
  40   // These stacks do not reflect the heirarchy over methods calls--whenever
  41   // there is an empty stack it means all variables are available.
  42   private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
  43
  44   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessRootView;
  45   private Hashtable< FlatNode, Set<TempDescriptor>      > livenessVirtualReads;
  46   private Hashtable< FlatNode, VarSrcTokTable           > variableResults;
  47   private Hashtable< FlatNode, Set<TempDescriptor>      > notAvailableResults;
  48   private Hashtable< FlatNode, CodePlan                 > codePlans;
  49
  50   private Hashtable<FlatNode, AccSet> effectsResults;
  51
  52   private Hashtable< FlatEdge, FlatWriteDynamicVarNode  > wdvNodesToSpliceIn;
  53
  54   public static int maxSESEage = -1;
  55
  56
  57   // use these methods in BuildCode to have access to analysis results
  58   public FlatSESEEnterNode getMainSESE() {
  59     return mainSESE;
  60   }
  61
  62   public Set<FlatSESEEnterNode> getRootSESEs() {
  63     return rootSESEs;
  64   }
  65
  66   public Set<FlatSESEEnterNode> getAllSESEs() {
  67     return allSESEs;
  68   }
  69
  70   public int getMaxSESEage() {
  71     return maxSESEage;
  72   }
  73
  74   // may be null
  75   public CodePlan getCodePlan( FlatNode fn ) {
  76     CodePlan cp = codePlans.get( fn );
  77     return cp;
  78   }
  79
  80
  81   public MLPAnalysis( State             state,
  82                       TypeUtil          tu,
  83                       CallGraph         callGraph,
  84                       OwnershipAnalysis ownAnalysis
  85                       ) {
  86
  87     double timeStartAnalysis = (double) System.nanoTime();
  88
  89     this.state       = state;
  90     this.typeUtil    = tu;
  91     this.callGraph   = callGraph;
  92     this.ownAnalysis = ownAnalysis;
  93     this.maxSESEage  = state.MLP_MAXSESEAGE;
  94
  95     rootSESEs = new HashSet<FlatSESEEnterNode>();
  96     allSESEs  = new HashSet<FlatSESEEnterNode>();
  97
  98     seseStacks           = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
  99     livenessRootView     = new Hashtable< FlatNode, Set<TempDescriptor>      >();
 100     livenessVirtualReads = new Hashtable< FlatNode, Set<TempDescriptor>      >();
 101     variableResults      = new Hashtable< FlatNode, VarSrcTokTable           >();
 102     notAvailableResults  = new Hashtable< FlatNode, Set<TempDescriptor>      >();
 103     codePlans            = new Hashtable< FlatNode, CodePlan                 >();
 104     wdvNodesToSpliceIn   = new Hashtable< FlatEdge, FlatWriteDynamicVarNode  >();
 105
 106     effectsResults = new Hashtable<FlatNode, AccSet>();
 107
 108
 109     FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() );
 110
 111     mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
 112     mainSESE.setfmEnclosing( fmMain );
 113     mainSESE.setmdEnclosing( fmMain.getMethod() );
 114     mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
 115
 116
 117     // 1st pass
 118     // run analysis on each method that is actually called
 119     // reachability analysis already computed this so reuse
 120     Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 121     while( methItr.hasNext() ) {
 122       Descriptor d  = methItr.next();
 123       FlatMethod fm = state.getMethodFlat( d );
 124
 125       // find every SESE from methods that may be called
 126       // and organize them into roots and children
 127       buildForestForward( fm );
 128     }
 129
 130
 131     // 2nd pass, results are saved in FlatSESEEnterNode, so
 132     // intermediate results, for safety, are discarded
 133     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
 134     while( rootItr.hasNext() ) {
 135       FlatSESEEnterNode root = rootItr.next();
 136       livenessAnalysisBackward( root,
 137                                 true,
 138                                 null );
 139     }
 140
 141
 142     // 3rd pass
 143     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 144     while( methItr.hasNext() ) {
 145       Descriptor d  = methItr.next();
 146       FlatMethod fm = state.getMethodFlat( d );
 147
 148       // starting from roots do a forward, fixed-point
 149       // variable analysis for refinement and stalls
 150       variableAnalysisForward( fm );
 151     }
 152
 153     // 4th pass, compute liveness contribution from
 154     // virtual reads discovered in variable pass
 155     rootItr = rootSESEs.iterator();
 156     while( rootItr.hasNext() ) {
 157       FlatSESEEnterNode root = rootItr.next();
 158       livenessAnalysisBackward( root,
 159                                 true,
 160                                 null );
 161     }
 162
 163
 164     /*
 165       SOMETHING IS WRONG WITH THIS, DON'T USE IT UNTIL IT CAN BE FIXED
 166
 167     // 5th pass
 168     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 169     while( methItr.hasNext() ) {
 170       Descriptor d  = methItr.next();
 171       FlatMethod fm = state.getMethodFlat( d );
 172
 173       // prune variable results in one traversal
 174       // by removing reference variables that are not live
 175       pruneVariableResultsWithLiveness( fm );
 176     }
 177     */
 178
 179
 180     // 6th pass
 181     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 182     while( methItr.hasNext() ) {
 183       Descriptor d  = methItr.next();
 184       FlatMethod fm = state.getMethodFlat( d );
 185
 186       // compute what is not available at every program
 187       // point, in a forward fixed-point pass
 188       notAvailableForward( fm );
 189     }
 190
 191         // new pass for method effects analysis
 192         methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 193         while (methItr.hasNext()) {
 194                 Descriptor d = methItr.next();
 195                 FlatMethod fm = state.getMethodFlat(d);
 196                 effectsForward(fm);
 197         }
 198
 199     // 7th pass
 200     methItr = ownAnalysis.descriptorsToAnalyze.iterator();
 201     while( methItr.hasNext() ) {
 202       Descriptor d  = methItr.next();
 203       FlatMethod fm = state.getMethodFlat( d );
 204
 205       // compute a plan for code injections
 206       codePlansForward( fm );
 207     }
 208
 209
 210     // splice new IR nodes into graph after all
 211     // analysis passes are complete
 212     Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
 213     while( spliceItr.hasNext() ) {
 214       Map.Entry               me    = (Map.Entry)               spliceItr.next();
 215       FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
 216       fwdvn.spliceIntoIR();
 217     }
 218
 219
 220     double timeEndAnalysis = (double) System.nanoTime();
 221     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 222     String treport = String.format( "The mlp analysis took %.3f sec.", dt );
 223     System.out.println( treport );
 224
 225     if( state.MLPDEBUG ) {
 226       try {
 227         writeReports( treport );
 228       } catch( IOException e ) {}
 229     }
 230   }
 231
 232
 233   private void buildForestForward( FlatMethod fm ) {
 234
 235     // start from flat method top, visit every node in
 236     // method exactly once, find SESEs and remember
 237     // roots and child relationships
 238     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 239     flatNodesToVisit.add( fm );
 240
 241     Set<FlatNode> visited = new HashSet<FlatNode>();
 242
 243     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 244     seseStacks.put( fm, seseStackFirst );
 245
 246     while( !flatNodesToVisit.isEmpty() ) {
 247       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 248       FlatNode fn = fnItr.next();
 249
 250       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 251       assert seseStack != null;
 252
 253       flatNodesToVisit.remove( fn );
 254       visited.add( fn );
 255
 256       buildForest_nodeActions( fn, seseStack, fm );
 257
 258       for( int i = 0; i < fn.numNext(); i++ ) {
 259         FlatNode nn = fn.getNext( i );
 260
 261         if( !visited.contains( nn ) ) {
 262           flatNodesToVisit.add( nn );
 263
 264           // clone stack and send along each analysis path
 265           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 266         }
 267       }
 268     }
 269   }
 270
 271   private void buildForest_nodeActions( FlatNode fn,
 272                                         Stack<FlatSESEEnterNode> seseStack,
 273                                         FlatMethod fm ) {
 274     switch( fn.kind() ) {
 275
 276     case FKind.FlatSESEEnterNode: {
 277       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 278
 279       if( !fsen.getIsCallerSESEplaceholder() ) {
 280         allSESEs.add( fsen );
 281       }
 282
 283       fsen.setfmEnclosing( fm );
 284       fsen.setmdEnclosing( fm.getMethod() );
 285       fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
 286
 287       if( seseStack.empty() ) {
 288         rootSESEs.add( fsen );
 289         fsen.setParent( null );
 290       } else {
 291         seseStack.peek().addChild( fsen );
 292         fsen.setParent( seseStack.peek() );
 293       }
 294
 295       seseStack.push( fsen );
 296     } break;
 297
 298     case FKind.FlatSESEExitNode: {
 299       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 300       assert !seseStack.empty();
 301       FlatSESEEnterNode fsen = seseStack.pop();
 302     } break;
 303
 304     case FKind.FlatReturnNode: {
 305       FlatReturnNode frn = (FlatReturnNode) fn;
 306       if( !seseStack.empty() &&
 307           !seseStack.peek().getIsCallerSESEplaceholder()
 308         ) {
 309         throw new Error( "Error: return statement enclosed within SESE "+
 310                          seseStack.peek().getPrettyIdentifier() );
 311       }
 312     } break;
 313
 314     }
 315   }
 316
 317
 318   private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
 319                                          boolean toplevel,
 320                                          Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
 321
 322     // start from an SESE exit, visit nodes in reverse up to
 323     // SESE enter in a fixed-point scheme, where children SESEs
 324     // should already be analyzed and therefore can be skipped
 325     // because child SESE enter node has all necessary info
 326     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 327
 328     if( toplevel ) {
 329       flatNodesToVisit.add( fsen.getfmEnclosing().getFlatExit() );
 330     } else {
 331       flatNodesToVisit.add( fsen.getFlatExit() );
 332     }
 333
 334     Hashtable<FlatNode, Set<TempDescriptor>> livenessResults =
 335       new Hashtable< FlatNode, Set<TempDescriptor> >();
 336
 337     if( toplevel ) {
 338       liveout = new Hashtable< FlatSESEExitNode, Set<TempDescriptor> >();
 339     }
 340
 341     while( !flatNodesToVisit.isEmpty() ) {
 342       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 343       flatNodesToVisit.remove( fn );
 344
 345       Set<TempDescriptor> prev = livenessResults.get( fn );
 346
 347       // merge sets from control flow joins
 348       Set<TempDescriptor> u = new HashSet<TempDescriptor>();
 349       for( int i = 0; i < fn.numNext(); i++ ) {
 350         FlatNode nn = fn.getNext( i );
 351         Set<TempDescriptor> s = livenessResults.get( nn );
 352         if( s != null ) {
 353           u.addAll( s );
 354         }
 355       }
 356
 357       Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
 358
 359       // if a new result, schedule backward nodes for analysis
 360       if( !curr.equals( prev ) ) {
 361         livenessResults.put( fn, curr );
 362
 363         // don't flow backwards past current SESE enter
 364         if( !fn.equals( fsen ) ) {
 365           for( int i = 0; i < fn.numPrev(); i++ ) {
 366             FlatNode nn = fn.getPrev( i );
 367             flatNodesToVisit.add( nn );
 368           }
 369         }
 370       }
 371     }
 372
 373     Set<TempDescriptor> s = livenessResults.get( fsen );
 374     if( s != null ) {
 375       fsen.addInVarSet( s );
 376     }
 377
 378     // remember liveness per node from the root view as the
 379     // global liveness of variables for later passes to use
 380     if( toplevel ) {
 381       livenessRootView.putAll( livenessResults );
 382     }
 383
 384     // post-order traversal, so do children first
 385     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 386     while( childItr.hasNext() ) {
 387       FlatSESEEnterNode fsenChild = childItr.next();
 388       livenessAnalysisBackward( fsenChild, false, liveout );
 389     }
 390   }
 391
 392   private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
 393                                                     Set<TempDescriptor> liveIn,
 394                                                     FlatSESEEnterNode currentSESE,
 395                                                     boolean toplevel,
 396                                                     Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout
 397                                                   ) {
 398     switch( fn.kind() ) {
 399
 400     case FKind.FlatSESEExitNode:
 401       if( toplevel ) {
 402         FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 403         if( !liveout.containsKey( fsexn ) ) {
 404           liveout.put( fsexn, new HashSet<TempDescriptor>() );
 405         }
 406         liveout.get( fsexn ).addAll( liveIn );
 407       }
 408       // no break, sese exits should also execute default actions
 409
 410     default: {
 411       // handle effects of statement in reverse, writes then reads
 412       TempDescriptor [] writeTemps = fn.writesTemps();
 413       for( int i = 0; i < writeTemps.length; ++i ) {
 414         liveIn.remove( writeTemps[i] );
 415
 416         if( !toplevel ) {
 417           FlatSESEExitNode fsexn = currentSESE.getFlatExit();
 418           Set<TempDescriptor> livetemps = liveout.get( fsexn );
 419           if( livetemps != null &&
 420               livetemps.contains( writeTemps[i] ) ) {
 421             // write to a live out temp...
 422             // need to put in SESE liveout set
 423             currentSESE.addOutVar( writeTemps[i] );
 424           }
 425         }
 426       }
 427
 428       TempDescriptor [] readTemps = fn.readsTemps();
 429       for( int i = 0; i < readTemps.length; ++i ) {
 430         liveIn.add( readTemps[i] );
 431       }
 432
 433       Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
 434       if( virtualReadTemps != null ) {
 435         liveIn.addAll( virtualReadTemps );
 436       }
 437
 438     } break;
 439
 440     } // end switch
 441
 442     return liveIn;
 443   }
 444
 445
 446   private void variableAnalysisForward( FlatMethod fm ) {
 447
 448     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 449     flatNodesToVisit.add( fm );
 450
 451     while( !flatNodesToVisit.isEmpty() ) {
 452       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 453       flatNodesToVisit.remove( fn );
 454
 455       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 456       assert seseStack != null;
 457
 458       VarSrcTokTable prev = variableResults.get( fn );
 459
 460       // merge sets from control flow joins
 461       VarSrcTokTable curr = new VarSrcTokTable();
 462       for( int i = 0; i < fn.numPrev(); i++ ) {
 463         FlatNode nn = fn.getPrev( i );
 464         VarSrcTokTable incoming = variableResults.get( nn );
 465         curr.merge( incoming );
 466       }
 467
 468       if( !seseStack.empty() ) {
 469         variable_nodeActions( fn, curr, seseStack.peek() );
 470       }
 471
 472       // if a new result, schedule forward nodes for analysis
 473       if( !curr.equals( prev ) ) {
 474         variableResults.put( fn, curr );
 475
 476         for( int i = 0; i < fn.numNext(); i++ ) {
 477           FlatNode nn = fn.getNext( i );
 478           flatNodesToVisit.add( nn );
 479         }
 480       }
 481     }
 482   }
 483
 484   private void variable_nodeActions( FlatNode fn,
 485                                      VarSrcTokTable vstTable,
 486                                      FlatSESEEnterNode currentSESE ) {
 487     switch( fn.kind() ) {
 488
 489     case FKind.FlatSESEEnterNode: {
 490       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 491       assert fsen.equals( currentSESE );
 492
 493       vstTable.age( currentSESE );
 494       vstTable.assertConsistency();
 495     } break;
 496
 497     case FKind.FlatSESEExitNode: {
 498       FlatSESEExitNode  fsexn = (FlatSESEExitNode)  fn;
 499       FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 500       assert currentSESE.getChildren().contains( fsen );
 501
 502       vstTable.remapChildTokens( fsen );
 503
 504       // liveness virtual reads are things that might be
 505       // written by an SESE and should be added to the in-set
 506       // anything virtually read by this SESE should be pruned
 507       // of parent or sibling sources
 508       Set<TempDescriptor> liveVars         = livenessRootView.get( fn );
 509       Set<TempDescriptor> fsenVirtReads    = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens( fsen, liveVars );
 510       Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get( fn );
 511       if( fsenVirtReadsOld != null ) {
 512         fsenVirtReads.addAll( fsenVirtReadsOld );
 513       }
 514       livenessVirtualReads.put( fn, fsenVirtReads );
 515
 516
 517       // then all child out-set tokens are guaranteed
 518       // to be filled in, so clobber those entries with
 519       // the latest, clean sources
 520       Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
 521       while( outVarItr.hasNext() ) {
 522         TempDescriptor outVar = outVarItr.next();
 523         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 524         ts.add( outVar );
 525         VariableSourceToken vst =
 526           new VariableSourceToken( ts,
 527                                    fsen,
 528                                    new Integer( 0 ),
 529                                    outVar
 530                                    );
 531         vstTable.remove( outVar );
 532         vstTable.add( vst );
 533       }
 534       vstTable.assertConsistency();
 535
 536     } break;
 537
 538     case FKind.FlatOpNode: {
 539       FlatOpNode fon = (FlatOpNode) fn;
 540
 541       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 542         TempDescriptor lhs = fon.getDest();
 543         TempDescriptor rhs = fon.getLeft();
 544
 545         vstTable.remove( lhs );
 546
 547         Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
 548
 549         Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
 550         while( itr.hasNext() ) {
 551           VariableSourceToken vst = itr.next();
 552
 553           HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 554           ts.add( lhs );
 555
 556           if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
 557             // if the source comes from a child, copy it over
 558             forAddition.add( new VariableSourceToken( ts,
 559                                                       vst.getSESE(),
 560                                                       vst.getAge(),
 561                                                       vst.getAddrVar()
 562                                                       )
 563                              );
 564           } else {
 565             // otherwise, stamp it as us as the source
 566             forAddition.add( new VariableSourceToken( ts,
 567                                                       currentSESE,
 568                                                       new Integer( 0 ),
 569                                                       lhs
 570                                                       )
 571                              );
 572           }
 573         }
 574
 575         vstTable.addAll( forAddition );
 576
 577         // only break if this is an ASSIGN op node,
 578         // otherwise fall through to default case
 579         vstTable.assertConsistency();
 580         break;
 581       }
 582     }
 583
 584     // note that FlatOpNode's that aren't ASSIGN
 585     // fall through to this default case
 586     default: {
 587       TempDescriptor [] writeTemps = fn.writesTemps();
 588       if( writeTemps.length > 0 ) {
 589
 590
 591         // for now, when writeTemps > 1, make sure
 592         // its a call node, programmer enforce only
 593         // doing stuff like calling a print routine
 594         //assert writeTemps.length == 1;
 595         if( writeTemps.length > 1 ) {
 596           assert fn.kind() == FKind.FlatCall ||
 597                  fn.kind() == FKind.FlatMethod;
 598           break;
 599         }
 600
 601         vstTable.remove( writeTemps[0] );
 602
 603         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 604         ts.add( writeTemps[0] );
 605
 606         vstTable.add( new VariableSourceToken( ts,
 607                                                currentSESE,
 608                                                new Integer( 0 ),
 609                                                writeTemps[0]
 610                                              )
 611                       );
 612       }
 613
 614       vstTable.assertConsistency();
 615     } break;
 616
 617     } // end switch
 618   }
 619
 620
 621   private void pruneVariableResultsWithLiveness( FlatMethod fm ) {
 622
 623     // start from flat method top, visit every node in
 624     // method exactly once
 625     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 626     flatNodesToVisit.add( fm );
 627
 628     Set<FlatNode> visited = new HashSet<FlatNode>();
 629
 630     while( !flatNodesToVisit.isEmpty() ) {
 631       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 632       FlatNode fn = fnItr.next();
 633
 634       flatNodesToVisit.remove( fn );
 635       visited.add( fn );
 636
 637       Set<TempDescriptor> rootLiveSet = livenessRootView.get( fn );
 638       VarSrcTokTable      vstTable    = variableResults.get( fn );
 639
 640       vstTable.pruneByLiveness( rootLiveSet );
 641
 642       for( int i = 0; i < fn.numNext(); i++ ) {
 643         FlatNode nn = fn.getNext( i );
 644
 645         if( !visited.contains( nn ) ) {
 646           flatNodesToVisit.add( nn );
 647         }
 648       }
 649     }
 650   }
 651
 652   private void effectsForward(FlatMethod fm) {
 653                 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 654                 flatNodesToVisit.add(fm);
 655
 656                 while (!flatNodesToVisit.isEmpty()) {
 657                         FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 658                         flatNodesToVisit.remove(fn);
 659
 660                         AccSet prev = effectsResults.get(fn);
 661                         AccSet curr = new AccSet();
 662
 663                         // merge phase
 664                         for (int i = 0; i < fn.numPrev(); i++) {
 665                                 FlatNode nn = fn.getPrev(i);
 666                                 AccSet accSet = effectsResults.get(nn);
 667                                 if (accSet != null) {
 668                                         curr.addAll(accSet);
 669                                 }
 670                         }
 671
 672                         effects_nodeActions(fn, curr);
 673
 674                         // if a new result, schedule forward nodes for analysis
 675                         if (!curr.equals(prev)) {
 676                                 effectsResults.put(fn, curr);
 677                                 for (int i = 0; i < fn.numNext(); i++) {
 678                                         FlatNode nn = fn.getNext(i);
 679                                         flatNodesToVisit.add(nn);
 680                                 }
 681                         }
 682                 }
 683
 684         }
 685
 686
 687
 688
 689         private void effects_nodeActions(FlatNode fn, AccSet curr) {
 690
 691                 OwnershipGraph fnOG = ownAnalysis
 692                                 .getMappingFlatNodeToOwnershipGraph(fn);
 693
 694                 switch (fn.kind()) {
 695
 696                 case FKind.FlatMethod: {
 697
 698                         FlatMethod fm = (FlatMethod) fn;
 699                         int numParam = fm.numParameters();
 700
 701                         for (int i = 0; i < numParam; i++) {
 702                                 TempDescriptor paramTD = fm.getParameter(i);
 703
 704                                 curr.addParam(paramTD);
 705                         }
 706
 707                         // for debug
 708                         // OwnershipGraph fnOG =
 709                         // ownAnalysis.getMappingFlatNodeToOwnershipGraph(fn);
 710                         // try {
 711                         // fnOG.writeGraph(fn + "FOOGRAPH", true, true, true, true, false);
 712                         // } catch (IOException e) {
 713                         // System.out.println("Error writing debug capture.");
 714                         // System.exit(0);
 715                         // }
 716
 717                 }
 718                         break;
 719
 720                 case FKind.FlatSetFieldNode: {
 721
 722                         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 723
 724                         TempDescriptor dstDesc = fsfn.getDst();
 725                         FieldDescriptor fieldDesc = fsfn.getField();
 726                         TempDescriptor srcDesc = fsfn.getSrc();
 727
 728                         LabelNode ln = fnOG.td2ln.get(dstDesc);
 729                         if (ln != null) {
 730                                 Iterator<ReferenceEdge> heapRegionsItr = ln
 731                                                 .iteratorToReferencees();
 732
 733                                 String tempStr = "";
 734                                 while (heapRegionsItr.hasNext()) {
 735                                         HeapRegionNode hrn2 = heapRegionsItr.next().getDst();
 736
 737                                         Set<Integer> paramSet = fnOG.idSecondary2paramIndexSet
 738                                                         .get(hrn2.getID());
 739
 740                                         String param = null;
 741                                         if (paramSet != null) {
 742                                                 Iterator<Integer> paramIter = paramSet.iterator();
 743                                                 param = "";
 744                                                 while (paramIter.hasNext()) {
 745                                                         param += paramIter.next() + " ";
 746                                                 }
 747                                         }
 748                                         tempStr += " " + hrn2 + "(" + param + ")";
 749                                 }
 750
 751                                 heapRegionsItr = ln.iteratorToReferencees();
 752                                 while (heapRegionsItr.hasNext()) {
 753                                         ReferenceEdge edge = heapRegionsItr.next();
 754                                         HeapRegionNode hrn = edge.getDst();
 755
 756                                         if (hrn.isParameter()) {
 757                                                 // currently, handle this case. otherwise, ignore it.
 758                                                 Iterator<ReferenceEdge> iter = hrn
 759                                                                 .iteratorToReferencers();
 760                                                 while (iter.hasNext()) {
 761                                                         ReferenceEdge re = iter.next();
 762                                                         if (re.getSrc() instanceof LabelNode) {
 763                                                                 LabelNode labelNode = (LabelNode) re.getSrc();
 764
 765                                                                 if (curr.containsParam(labelNode
 766                                                                                 .getTempDescriptor())) {
 767
 768                                                                         curr.addWritingVar(labelNode
 769                                                                                         .getTempDescriptor(), new AccKey(
 770                                                                                         fieldDesc.getSymbol(), dstDesc
 771                                                                                                         .getType()));
 772
 773                                                                 }
 774
 775                                                         }
 776                                                 }
 777
 778                                                 // check weather this heap region is parameter
 779                                                 // reachable...
 780
 781                                                 Set<Integer> paramSet = fnOG.idSecondary2paramIndexSet
 782                                                                 .get(hrn.getID());
 783                                                 if (paramSet != null) {
 784                                                         Iterator<Integer> paramIter = paramSet.iterator();
 785
 786                                                         while (paramIter.hasNext()) {
 787                                                                 Integer paramID = paramIter.next();
 788
 789                                                                 Integer primaryID = fnOG.paramIndex2idPrimary
 790                                                                                 .get(paramID);
 791                                                                 HeapRegionNode paramHRN = fnOG.id2hrn
 792                                                                                 .get(primaryID);
 793
 794                                                                 HashSet<LabelNode> LNSet = getParameterLabelNodeSet(
 795                                                                                 fnOG, curr, paramHRN);
 796
 797                                                                 Iterator<LabelNode> LNSetIter = LNSet
 798                                                                                 .iterator();
 799                                                                 while (LNSetIter.hasNext()) {
 800                                                                         LabelNode labelNode = LNSetIter.next();
 801
 802                                                                         curr.addWritingVar(labelNode
 803                                                                                         .getTempDescriptor(), new AccKey(
 804                                                                                         fieldDesc.getSymbol(), dstDesc
 805                                                                                                         .getType()));
 806                                                                 }
 807
 808                                                         }
 809                                                 }
 810
 811                                         }
 812
 813                                 }
 814                         }
 815
 816                 }
 817                         break;
 818
 819                 case FKind.FlatFieldNode: {
 820
 821                         FlatFieldNode ffn = (FlatFieldNode) fn;
 822
 823                         TempDescriptor srcDesc = ffn.getSrc();
 824                         FieldDescriptor fieldDesc = ffn.getField();
 825
 826                         LabelNode ln = fnOG.td2ln.get(srcDesc);
 827                         if (ln != null) {
 828
 829                                 Iterator<ReferenceEdge> heapRegionsItr = ln
 830                                                 .iteratorToReferencees();
 831                                 String tempStr = "";
 832                                 while (heapRegionsItr.hasNext()) {
 833
 834                                         HeapRegionNode hrn = heapRegionsItr.next().getDst();
 835
 836                                         Set<Integer> paramSet = fnOG.idSecondary2paramIndexSet
 837                                                         .get(hrn.getID());
 838
 839                                         String param = null;
 840                                         if (paramSet != null) {
 841                                                 Iterator<Integer> paramIter = paramSet.iterator();
 842                                                 param = "";
 843                                                 while (paramIter.hasNext()) {
 844                                                         param += paramIter.next() + " ";
 845                                                 }
 846                                         }
 847                                         tempStr += " " + hrn + "(" + param + ")";
 848                                 }
 849
 850                                 heapRegionsItr = ln.iteratorToReferencees();
 851                                 while (heapRegionsItr.hasNext()) {
 852                                         ReferenceEdge edge = heapRegionsItr.next();
 853                                         HeapRegionNode hrn = edge.getDst();
 854
 855                                         if (hrn.isParameter()) {
 856                                                 Iterator<ReferenceEdge> iter = hrn
 857                                                                 .iteratorToReferencers();
 858
 859                                                 while (iter.hasNext()) {
 860                                                         ReferenceEdge re = iter.next();
 861                                                         if (re.getSrc() instanceof LabelNode) {
 862
 863                                                                 LabelNode labelNode = (LabelNode) re.getSrc();
 864
 865                                                                 if (curr.containsParam(labelNode
 866                                                                                 .getTempDescriptor())) {
 867                                                                         curr.addReadingVar(labelNode
 868                                                                                         .getTempDescriptor(), new AccKey(
 869                                                                                         fieldDesc.getSymbol(), srcDesc
 870                                                                                                         .getType()));
 871                                                                 }
 872                                                         }
 873                                                 }
 874
 875                                                 //
 876                                                 // check weather this heap region is parameter
 877                                                 // reachable...
 878                                                 //
 879
 880                                                 Set<Integer> paramSet = fnOG.idSecondary2paramIndexSet
 881                                                                 .get(hrn.getID());
 882                                                 if (paramSet != null) {
 883                                                         Iterator<Integer> paramIter = paramSet.iterator();
 884
 885                                                         while (paramIter.hasNext()) {
 886                                                                 Integer paramID = paramIter.next();
 887
 888                                                                 Integer primaryID = fnOG.paramIndex2idPrimary
 889                                                                                 .get(paramID);
 890                                                                 HeapRegionNode paramHRN = fnOG.id2hrn
 891                                                                                 .get(primaryID);
 892
 893                                                                 HashSet<LabelNode> LNSet = getParameterLabelNodeSet(
 894                                                                                 fnOG, curr, paramHRN);
 895
 896                                                                 Iterator<LabelNode> LNSetIter = LNSet
 897                                                                                 .iterator();
 898                                                                 while (LNSetIter.hasNext()) {
 899                                                                         LabelNode labelNode = LNSetIter.next();
 900
 901                                                                         curr.addReadingVar(labelNode
 902                                                                                         .getTempDescriptor(), new AccKey(
 903                                                                                         fieldDesc.getSymbol(), srcDesc
 904                                                                                                         .getType()));
 905                                                                 }
 906                                                         }
 907                                                 }
 908                                         }
 909                                 }
 910
 911                         }
 912
 913                 }
 914                         break;
 915
 916                 }
 917
 918         }
 919
 920         // returns the set of parameter label node which are associated with the
 921         // specific heap region node.
 922         private HashSet<LabelNode> getParameterLabelNodeSet(OwnershipGraph og,
 923                         AccSet curr, HeapRegionNode hrn) {
 924
 925                 HashSet<LabelNode> set = new HashSet<LabelNode>();
 926                 Iterator<ReferenceEdge> iter = hrn.iteratorToReferencers();
 927                 while (iter.hasNext()) {
 928                         ReferenceEdge re = iter.next();
 929                         if (re.getSrc() instanceof LabelNode) {
 930                                 LabelNode labelNode = (LabelNode) re.getSrc();
 931                                 if (curr.containsParam(labelNode.getTempDescriptor())) {
 932                                         set.add(labelNode);
 933                                 }
 934                         }
 935                 }
 936                 return set;
 937         }
 938
 939   private void notAvailableForward( FlatMethod fm ) {
 940
 941     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 942     flatNodesToVisit.add( fm );
 943
 944     while( !flatNodesToVisit.isEmpty() ) {
 945       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 946       flatNodesToVisit.remove( fn );
 947
 948       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 949       assert seseStack != null;
 950
 951       Set<TempDescriptor> prev = notAvailableResults.get( fn );
 952
 953       Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
 954       for( int i = 0; i < fn.numPrev(); i++ ) {
 955         FlatNode nn = fn.getPrev( i );
 956         Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
 957         if( notAvailIn != null ) {
 958           curr.addAll( notAvailIn );
 959         }
 960       }
 961
 962       if( !seseStack.empty() ) {
 963         notAvailable_nodeActions( fn, curr, seseStack.peek() );
 964       }
 965
 966       // if a new result, schedule forward nodes for analysis
 967       if( !curr.equals( prev ) ) {
 968         notAvailableResults.put( fn, curr );
 969
 970         for( int i = 0; i < fn.numNext(); i++ ) {
 971           FlatNode nn = fn.getNext( i );
 972           flatNodesToVisit.add( nn );
 973         }
 974       }
 975     }
 976   }
 977
 978   private void notAvailable_nodeActions( FlatNode fn,
 979                                          Set<TempDescriptor> notAvailSet,
 980                                          FlatSESEEnterNode currentSESE ) {
 981
 982     // any temps that are removed from the not available set
 983     // at this node should be marked in this node's code plan
 984     // as temps to be grabbed at runtime!
 985
 986     switch( fn.kind() ) {
 987
 988     case FKind.FlatSESEEnterNode: {
 989       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 990       assert fsen.equals( currentSESE );
 991       notAvailSet.clear();
 992     } break;
 993
 994     case FKind.FlatSESEExitNode: {
 995       FlatSESEExitNode  fsexn = (FlatSESEExitNode)  fn;
 996       FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 997       assert currentSESE.getChildren().contains( fsen );
 998       notAvailSet.addAll( fsen.getOutVarSet() );
 999     } break;
1000
1001     case FKind.FlatMethod: {
1002       notAvailSet.clear();
1003     }
1004
1005     case FKind.FlatOpNode: {
1006       FlatOpNode fon = (FlatOpNode) fn;
1007
1008       if( fon.getOp().getOp() == Operation.ASSIGN ) {
1009         TempDescriptor lhs = fon.getDest();
1010         TempDescriptor rhs = fon.getLeft();
1011
1012         // copy makes lhs same availability as rhs
1013         if( notAvailSet.contains( rhs ) ) {
1014           notAvailSet.add( lhs );
1015         } else {
1016           notAvailSet.remove( lhs );
1017         }
1018
1019         // only break if this is an ASSIGN op node,
1020         // otherwise fall through to default case
1021         break;
1022       }
1023     }
1024
1025     // note that FlatOpNode's that aren't ASSIGN
1026     // fall through to this default case
1027     default: {
1028       TempDescriptor [] writeTemps = fn.writesTemps();
1029       for( int i = 0; i < writeTemps.length; i++ ) {
1030         TempDescriptor wTemp = writeTemps[i];
1031         notAvailSet.remove( wTemp );
1032       }
1033       TempDescriptor [] readTemps = fn.readsTemps();
1034       for( int i = 0; i < readTemps.length; i++ ) {
1035         TempDescriptor rTemp = readTemps[i];
1036         notAvailSet.remove( rTemp );
1037
1038         // if this variable has exactly one source, potentially
1039         // get other things from this source as well
1040         VarSrcTokTable vstTable = variableResults.get( fn );
1041
1042         Integer srcType =
1043           vstTable.getRefVarSrcType( rTemp,
1044                                      currentSESE,
1045                                      currentSESE.getParent() );
1046
1047         if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
1048
1049           VariableSourceToken vst = vstTable.get( rTemp ).iterator().next();
1050
1051           Iterator<VariableSourceToken> availItr = vstTable.get( vst.getSESE(),
1052                                                                  vst.getAge()
1053                                                                  ).iterator();
1054
1055           // look through things that are also available from same source
1056           while( availItr.hasNext() ) {
1057             VariableSourceToken vstAlsoAvail = availItr.next();
1058
1059             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
1060             while( refVarItr.hasNext() ) {
1061               TempDescriptor refVarAlso = refVarItr.next();
1062
1063               // if a variable is available from the same source, AND it ALSO
1064               // only comes from one statically known source, mark it available
1065               Integer srcTypeAlso =
1066                 vstTable.getRefVarSrcType( refVarAlso,
1067                                            currentSESE,
1068                                            currentSESE.getParent() );
1069               if( srcTypeAlso.equals( VarSrcTokTable.SrcType_STATIC ) ) {
1070                 notAvailSet.remove( refVarAlso );
1071               }
1072             }
1073           }
1074         }
1075       }
1076     } break;
1077
1078     } // end switch
1079   }
1080
1081
1082   private void codePlansForward( FlatMethod fm ) {
1083
1084     // start from flat method top, visit every node in
1085     // method exactly once
1086     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1087     flatNodesToVisit.add( fm );
1088
1089     Set<FlatNode> visited = new HashSet<FlatNode>();
1090
1091     while( !flatNodesToVisit.isEmpty() ) {
1092       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
1093       FlatNode fn = fnItr.next();
1094
1095       flatNodesToVisit.remove( fn );
1096       visited.add( fn );
1097
1098       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
1099       assert seseStack != null;
1100
1101       // use incoming results as "dot statement" or just
1102       // before the current statement
1103       VarSrcTokTable dotSTtable = new VarSrcTokTable();
1104       for( int i = 0; i < fn.numPrev(); i++ ) {
1105         FlatNode nn = fn.getPrev( i );
1106         dotSTtable.merge( variableResults.get( nn ) );
1107       }
1108
1109       // find dt-st notAvailableSet also
1110       Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
1111       for( int i = 0; i < fn.numPrev(); i++ ) {
1112         FlatNode nn = fn.getPrev( i );
1113         Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
1114         if( notAvailIn != null ) {
1115           dotSTnotAvailSet.addAll( notAvailIn );
1116         }
1117       }
1118
1119       Set<TempDescriptor> dotSTlive = livenessRootView.get( fn );
1120
1121       if( !seseStack.empty() ) {
1122         codePlans_nodeActions( fn,
1123                                dotSTlive,
1124                                dotSTtable,
1125                                dotSTnotAvailSet,
1126                                seseStack.peek()
1127                                );
1128       }
1129
1130       for( int i = 0; i < fn.numNext(); i++ ) {
1131         FlatNode nn = fn.getNext( i );
1132
1133         if( !visited.contains( nn ) ) {
1134           flatNodesToVisit.add( nn );
1135         }
1136       }
1137     }
1138   }
1139
1140   private void codePlans_nodeActions( FlatNode fn,
1141                                       Set<TempDescriptor> liveSetIn,
1142                                       VarSrcTokTable vstTableIn,
1143                                       Set<TempDescriptor> notAvailSetIn,
1144                                       FlatSESEEnterNode currentSESE ) {
1145
1146     CodePlan plan = new CodePlan( currentSESE);
1147
1148     switch( fn.kind() ) {
1149
1150     case FKind.FlatSESEEnterNode: {
1151       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
1152
1153       // track the source types of the in-var set so generated
1154       // code at this SESE issue can compute the number of
1155       // dependencies properly
1156       Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
1157       while( inVarItr.hasNext() ) {
1158         TempDescriptor inVar = inVarItr.next();
1159         Integer srcType =
1160           vstTableIn.getRefVarSrcType( inVar,
1161                                        fsen,
1162                                        fsen.getParent() );
1163
1164         // the current SESE needs a local space to track the dynamic
1165         // variable and the child needs space in its SESE record
1166         if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1167           fsen.addDynamicInVar( inVar );
1168           fsen.getParent().addDynamicVar( inVar );
1169
1170         } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
1171           fsen.addStaticInVar( inVar );
1172           VariableSourceToken vst = vstTableIn.get( inVar ).iterator().next();
1173           fsen.putStaticInVar2src( inVar, vst );
1174           fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(),
1175                                                       vst.getAge()
1176                                                     )
1177                                 );
1178
1179         } else {
1180           assert srcType.equals( VarSrcTokTable.SrcType_READY );
1181           fsen.addReadyInVar( inVar );
1182         }
1183       }
1184
1185     } break;
1186
1187     case FKind.FlatSESEExitNode: {
1188       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
1189     } break;
1190
1191     case FKind.FlatOpNode: {
1192       FlatOpNode fon = (FlatOpNode) fn;
1193
1194       if( fon.getOp().getOp() == Operation.ASSIGN ) {
1195         TempDescriptor lhs = fon.getDest();
1196         TempDescriptor rhs = fon.getLeft();
1197
1198         // if this is an op node, don't stall, copy
1199         // source and delay until we need to use value
1200
1201         // ask whether lhs and rhs sources are dynamic, static, etc.
1202         Integer lhsSrcType
1203           = vstTableIn.getRefVarSrcType( lhs,
1204                                          currentSESE,
1205                                          currentSESE.getParent() );
1206
1207         Integer rhsSrcType
1208           = vstTableIn.getRefVarSrcType( rhs,
1209                                          currentSESE,
1210                                          currentSESE.getParent() );
1211
1212         if( rhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1213           // if rhs is dynamic going in, lhs will definitely be dynamic
1214           // going out of this node, so track that here
1215           plan.addDynAssign( lhs, rhs );
1216           currentSESE.addDynamicVar( lhs );
1217           currentSESE.addDynamicVar( rhs );
1218
1219         } else if( lhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1220           // otherwise, if the lhs is dynamic, but the rhs is not, we
1221           // need to update the variable's dynamic source as "current SESE"
1222           plan.addDynAssign( lhs );
1223         }
1224
1225         // only break if this is an ASSIGN op node,
1226         // otherwise fall through to default case
1227         break;
1228       }
1229     }
1230
1231     // note that FlatOpNode's that aren't ASSIGN
1232     // fall through to this default case
1233     default: {
1234
1235       // a node with no live set has nothing to stall for
1236       if( liveSetIn == null ) {
1237         break;
1238       }
1239
1240       TempDescriptor[] readarray = fn.readsTemps();
1241       for( int i = 0; i < readarray.length; i++ ) {
1242         TempDescriptor readtmp = readarray[i];
1243
1244         // ignore temps that are definitely available
1245         // when considering to stall on it
1246         if( !notAvailSetIn.contains( readtmp ) ) {
1247           continue;
1248         }
1249
1250         // check the source type of this variable
1251         Integer srcType
1252           = vstTableIn.getRefVarSrcType( readtmp,
1253                                          currentSESE,
1254                                          currentSESE.getParent() );
1255
1256         if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
1257           // 1) It is not clear statically where this variable will
1258           // come from statically, so dynamically we must keep track
1259           // along various control paths, and therefore when we stall,
1260           // just stall for the exact thing we need and move on
1261           plan.addDynamicStall( readtmp );
1262           currentSESE.addDynamicVar( readtmp );
1263
1264         } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
1265           // 2) Single token/age pair: Stall for token/age pair, and copy
1266           // all live variables with same token/age pair at the same
1267           // time.  This is the same stuff that the notavaialable analysis
1268           // marks as now available.
1269
1270           VariableSourceToken vst = vstTableIn.get( readtmp ).iterator().next();
1271
1272           Iterator<VariableSourceToken> availItr =
1273             vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator();
1274
1275           while( availItr.hasNext() ) {
1276             VariableSourceToken vstAlsoAvail = availItr.next();
1277
1278             // only grab additional stuff that is live
1279             Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
1280
1281             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
1282             while( refVarItr.hasNext() ) {
1283               TempDescriptor refVar = refVarItr.next();
1284               if( liveSetIn.contains( refVar ) ) {
1285                 copySet.add( refVar );
1286               }
1287             }
1288
1289             if( !copySet.isEmpty() ) {
1290               plan.addStall2CopySet( vstAlsoAvail, copySet );
1291             }
1292           }
1293
1294         } else {
1295           // the other case for srcs is READY, so do nothing
1296         }
1297
1298         // assert that everything being stalled for is in the
1299         // "not available" set coming into this flat node and
1300         // that every VST identified is in the possible "stall set"
1301         // that represents VST's from children SESE's
1302
1303       }
1304     } break;
1305
1306     } // end switch
1307
1308
1309     // identify sese-age pairs that are statically useful
1310     // and should have an associated SESE variable in code
1311     // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
1312     // AND ALWAYS GIVE NAMES TO PARENTS
1313     Set<VariableSourceToken> staticSet = vstTableIn.get();
1314     Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1315     while( vstItr.hasNext() ) {
1316       VariableSourceToken vst = vstItr.next();
1317
1318       // placeholder source tokens are useful results, but
1319       // the placeholder static name is never needed
1320       if( vst.getSESE().getIsCallerSESEplaceholder() ) {
1321         continue;
1322       }
1323
1324       FlatSESEEnterNode sese = currentSESE;
1325       while( sese != null ) {
1326         sese.addNeededStaticName(
1327                                  new SESEandAgePair( vst.getSESE(), vst.getAge() )
1328                                   );
1329         sese.mustTrackAtLeastAge( vst.getAge() );
1330
1331         sese = sese.getParent();
1332       }
1333     }
1334
1335
1336     codePlans.put( fn, plan );
1337
1338
1339     // if any variables at this-node-*dot* have a static source (exactly one vst)
1340     // but go to a dynamic source at next-node-*dot*, create a new IR graph
1341     // node on that edge to track the sources dynamically
1342     VarSrcTokTable thisVstTable = variableResults.get( fn );
1343     for( int i = 0; i < fn.numNext(); i++ ) {
1344       FlatNode            nn           = fn.getNext( i );
1345       VarSrcTokTable      nextVstTable = variableResults.get( nn );
1346       Set<TempDescriptor> nextLiveIn   = livenessRootView.get( nn );
1347
1348       // the table can be null if it is one of the few IR nodes
1349       // completely outside of the root SESE scope
1350       if( nextVstTable != null && nextLiveIn != null ) {
1351
1352         Hashtable<TempDescriptor, VariableSourceToken> static2dynamicSet =
1353           thisVstTable.getStatic2DynamicSet( nextVstTable,
1354                                              nextLiveIn,
1355                                              currentSESE,
1356                                              currentSESE.getParent()
1357                                            );
1358
1359         if( !static2dynamicSet.isEmpty() ) {
1360
1361           // either add these results to partial fixed-point result
1362           // or make a new one if we haven't made any here yet
1363           FlatEdge fe = new FlatEdge( fn, nn );
1364           FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe );
1365
1366           if( fwdvn == null ) {
1367             fwdvn = new FlatWriteDynamicVarNode( fn,
1368                                                  nn,
1369                                                  static2dynamicSet,
1370                                                  currentSESE
1371                                                  );
1372             wdvNodesToSpliceIn.put( fe, fwdvn );
1373           } else {
1374             fwdvn.addMoreVar2Src( static2dynamicSet );
1375           }
1376         }
1377       }
1378     }
1379   }
1380
1381
1382   public void writeReports( String timeReport ) throws java.io.IOException {
1383
1384     BufferedWriter bw = new BufferedWriter( new FileWriter( "mlpReport_summary.txt" ) );
1385     bw.write( "MLP Analysis Results\n\n" );
1386     bw.write( timeReport+"\n\n" );
1387     printSESEHierarchy( bw );
1388     bw.write( "\n" );
1389     printSESEInfo( bw );
1390     bw.close();
1391
1392     Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
1393     while( methItr.hasNext() ) {
1394       MethodDescriptor md = (MethodDescriptor) methItr.next();
1395       FlatMethod       fm = state.getMethodFlat( md );
1396       bw = new BufferedWriter( new FileWriter( "mlpReport_"+
1397                                                md.getClassMethodName()+
1398                                                md.getSafeMethodDescriptor()+
1399                                                ".txt" ) );
1400       bw.write( "MLP Results for "+md+"\n-------------------\n");
1401       bw.write( "\n\nLive-In, Root View\n------------------\n"          +fm.printMethod( livenessRootView ) );
1402       bw.write( "\n\nVariable Results-Out\n----------------\n"          +fm.printMethod( variableResults ) );
1403       bw.write( "\n\nNot Available Results-Out\n---------------------\n"+fm.printMethod( notAvailableResults ) );
1404       bw.write( "\n\nCode Plans\n----------\n"                          +fm.printMethod( codePlans ) );
1405       bw.close();
1406     }
1407   }
1408
1409   private void printSESEHierarchy( BufferedWriter bw ) throws java.io.IOException {
1410     bw.write( "SESE Hierarchy\n--------------\n" );
1411     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
1412     while( rootItr.hasNext() ) {
1413       FlatSESEEnterNode root = rootItr.next();
1414       if( root.getIsCallerSESEplaceholder() ) {
1415         if( !root.getChildren().isEmpty() ) {
1416           printSESEHierarchyTree( bw, root, 0 );
1417         }
1418       } else {
1419         printSESEHierarchyTree( bw, root, 0 );
1420       }
1421     }
1422   }
1423
1424   private void printSESEHierarchyTree( BufferedWriter bw,
1425                                        FlatSESEEnterNode fsen,
1426                                        int depth
1427                                      ) throws java.io.IOException {
1428     for( int i = 0; i < depth; ++i ) {
1429       bw.write( "  " );
1430     }
1431     bw.write( "- "+fsen.getPrettyIdentifier()+"\n" );
1432
1433     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1434     while( childItr.hasNext() ) {
1435       FlatSESEEnterNode fsenChild = childItr.next();
1436       printSESEHierarchyTree( bw, fsenChild, depth + 1 );
1437     }
1438   }
1439
1440
1441   private void printSESEInfo( BufferedWriter bw ) throws java.io.IOException {
1442     bw.write("\nSESE info\n-------------\n" );
1443     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
1444     while( rootItr.hasNext() ) {
1445       FlatSESEEnterNode root = rootItr.next();
1446       if( root.getIsCallerSESEplaceholder() ) {
1447         if( !root.getChildren().isEmpty() ) {
1448           printSESEInfoTree( bw, root );
1449         }
1450       } else {
1451         printSESEInfoTree( bw, root );
1452       }
1453     }
1454   }
1455
1456   private void printSESEInfoTree( BufferedWriter bw,
1457                                   FlatSESEEnterNode fsen
1458                                 ) throws java.io.IOException {
1459
1460     if( !fsen.getIsCallerSESEplaceholder() ) {
1461       bw.write( "SESE "+fsen.getPrettyIdentifier()+" {\n" );
1462
1463       bw.write( "  in-set: "+fsen.getInVarSet()+"\n" );
1464       Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1465       while( tItr.hasNext() ) {
1466         TempDescriptor inVar = tItr.next();
1467         if( fsen.getReadyInVarSet().contains( inVar ) ) {
1468           bw.write( "    (ready)  "+inVar+"\n" );
1469         }
1470         if( fsen.getStaticInVarSet().contains( inVar ) ) {
1471           bw.write( "    (static) "+inVar+"\n" );
1472         }
1473         if( fsen.getDynamicInVarSet().contains( inVar ) ) {
1474           bw.write( "    (dynamic)"+inVar+"\n" );
1475         }
1476       }
1477
1478       bw.write( "  out-set: "+fsen.getOutVarSet()+"\n" );
1479       bw.write( "}\n" );
1480     }
1481
1482     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1483     while( childItr.hasNext() ) {
1484       FlatSESEEnterNode fsenChild = childItr.next();
1485       printSESEInfoTree( bw, fsenChild );
1486     }
1487   }
1488 }