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