Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java

   1 package Analysis.OoOJava;
   2
   3 import java.util.HashSet;
   4 import java.util.Hashtable;
   5 import java.util.Iterator;
   6 import java.util.Set;
   7 import java.util.Stack;
   8
   9 import Analysis.ArrayReferencees;
  10 import Analysis.Liveness;
  11 import Analysis.CallGraph.CallGraph;
  12 import Analysis.Disjoint.DisjointAnalysis;
  13 import Analysis.OwnershipAnalysis.AllocationSite;
  14 import Analysis.OwnershipAnalysis.MethodContext;
  15 import IR.Descriptor;
  16 import IR.Operation;
  17 import IR.State;
  18 import IR.TypeUtil;
  19 import IR.Flat.FKind;
  20 import IR.Flat.FlatEdge;
  21 import IR.Flat.FlatMethod;
  22 import IR.Flat.FlatNode;
  23 import IR.Flat.FlatOpNode;
  24 import IR.Flat.FlatReturnNode;
  25 import IR.Flat.FlatSESEEnterNode;
  26 import IR.Flat.FlatSESEExitNode;
  27 import IR.Flat.FlatWriteDynamicVarNode;
  28 import IR.Flat.TempDescriptor;
  29
  30 public class OoOJavaAnalysis {
  31
  32   // data from the compiler
  33   private State state;
  34   private TypeUtil typeUtil;
  35   private CallGraph callGraph;
  36   private DisjointAnalysis disjointAnalysis;
  37
  38   // an implicit SESE is automatically spliced into
  39   // the IR graph around the C main before this analysis--it
  40   // is nothing special except that we can make assumptions
  41   // about it, such as the whole program ends when it ends
  42   private FlatSESEEnterNode mainSESE;
  43
  44   // SESEs that are the root of an SESE tree belong to this
  45   // set--the main SESE is always a root, statically SESEs
  46   // inside methods are a root because we don't know how they
  47   // will fit into the runtime tree of SESEs
  48   private Set<FlatSESEEnterNode> rootSESEs;
  49
  50   // simply a set of every reachable SESE in the program, not
  51   // including caller placeholder SESEs
  52   private Set<FlatSESEEnterNode> allSESEs;
  53
  54   // A mapping of flat nodes to the stack of SESEs for that node, where
  55   // an SESE is the child of the SESE directly below it on the stack.
  56   // These stacks do not reflect the heirarchy over methods calls--whenever
  57   // there is an empty stack it means all variables are available.
  58   private Hashtable<FlatNode, Stack<FlatSESEEnterNode>> seseStacks;
  59
  60   private Hashtable<FlatNode, Set<TempDescriptor>> livenessRootView;
  61   private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
  62   private Hashtable<FlatNode, VarSrcTokTable> variableResults;
  63   private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
  64   private Hashtable<FlatNode, CodePlan> codePlans;
  65
  66   private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
  67
  68   private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
  69
  70   private Hashtable<MethodContext, HashSet<AllocationSite>> mapMethodContextToLiveInAllocationSiteSet;
  71
  72 //  private Hashtable<FlatNode, ParentChildConflictsMap> conflictsResults;
  73 //  private Hashtable<FlatMethod, MethodSummary> methodSummaryResults;
  74 //  private OwnershipAnalysis ownAnalysisForSESEConflicts;
  75 //  private Hashtable<FlatNode, ConflictGraph> conflictGraphResults;
  76
  77   // temporal data structures to track analysis progress.
  78   static private int uniqueLockSetId = 0;
  79
  80   public static int maxSESEage = -1;
  81
  82   // use these methods in BuildCode to have access to analysis results
  83   public FlatSESEEnterNode getMainSESE() {
  84     return mainSESE;
  85   }
  86
  87   public Set<FlatSESEEnterNode> getRootSESEs() {
  88     return rootSESEs;
  89   }
  90
  91   public Set<FlatSESEEnterNode> getAllSESEs() {
  92     return allSESEs;
  93   }
  94
  95   public int getMaxSESEage() {
  96     return maxSESEage;
  97   }
  98
  99   // may be null
 100   public CodePlan getCodePlan(FlatNode fn) {
 101     CodePlan cp = codePlans.get(fn);
 102     return cp;
 103   }
 104
 105   public OoOJavaAnalysis(State state, TypeUtil tu, CallGraph callGraph,
 106       DisjointAnalysis disjointAnalysis, Liveness liveness, ArrayReferencees arrayReferencees) {
 107
 108     double timeStartAnalysis = (double) System.nanoTime();
 109
 110     this.state = state;
 111     this.typeUtil = tu;
 112     this.callGraph = callGraph;
 113     this.disjointAnalysis = disjointAnalysis;
 114     this.maxSESEage = state.MLP_MAXSESEAGE;
 115
 116     rootSESEs = new HashSet<FlatSESEEnterNode>();
 117     allSESEs = new HashSet<FlatSESEEnterNode>();
 118
 119     seseStacks = new Hashtable<FlatNode, Stack<FlatSESEEnterNode>>();
 120     livenessRootView = new Hashtable<FlatNode, Set<TempDescriptor>>();
 121     livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
 122     variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
 123     notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
 124     codePlans = new Hashtable<FlatNode, CodePlan>();
 125     wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
 126
 127     notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
 128
 129     mapMethodContextToLiveInAllocationSiteSet = new Hashtable<MethodContext, HashSet<AllocationSite>>();
 130
 131 //    conflictsResults = new Hashtable<FlatNode, ParentChildConflictsMap>();
 132 //    methodSummaryResults = new Hashtable<FlatMethod, MethodSummary>();
 133 //    conflictGraphResults = new Hashtable<FlatNode, ConflictGraph>();
 134
 135     // seseSummaryMap = new Hashtable<FlatNode, SESESummary>();
 136     // isAfterChildSESEIndicatorMap = new Hashtable<FlatNode, Boolean>();
 137     // conflictGraphLockMap = new Hashtable<ConflictGraph, HashSet<SESELock>>();
 138
 139     FlatMethod fmMain = state.getMethodFlat(typeUtil.getMain());
 140
 141     mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
 142     mainSESE.setfmEnclosing(fmMain);
 143     mainSESE.setmdEnclosing(fmMain.getMethod());
 144     mainSESE.setcdEnclosing(fmMain.getMethod().getClassDesc());
 145
 146     // 1st pass
 147     // run analysis on each method that is actually called
 148     // reachability analysis already computed this so reuse
 149     Iterator<Descriptor> methItr = disjointAnalysis.getDescriptorsToAnalyze().iterator();
 150     while (methItr.hasNext()) {
 151       Descriptor d = methItr.next();
 152       FlatMethod fm = state.getMethodFlat(d);
 153
 154       // find every SESE from methods that may be called
 155       // and organize them into roots and children
 156       buildForestForward(fm);
 157     }
 158
 159     // 2nd pass, results are saved in FlatSESEEnterNode, so
 160     // intermediate results, for safety, are discarded
 161     Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
 162     while (rootItr.hasNext()) {
 163       FlatSESEEnterNode root = rootItr.next();
 164       livenessAnalysisBackward(root, true, null);
 165     }
 166
 167     // 3rd pass
 168     methItr = disjointAnalysis.getDescriptorsToAnalyze().iterator();
 169     while (methItr.hasNext()) {
 170       Descriptor d = methItr.next();
 171       FlatMethod fm = state.getMethodFlat(d);
 172
 173       // starting from roots do a forward, fixed-point
 174       // variable analysis for refinement and stalls
 175       variableAnalysisForward(fm);
 176     }
 177
 178     // 4th pass, compute liveness contribution from
 179     // virtual reads discovered in variable pass
 180     rootItr = rootSESEs.iterator();
 181     while (rootItr.hasNext()) {
 182       FlatSESEEnterNode root = rootItr.next();
 183       livenessAnalysisBackward(root, true, null);
 184     }
 185
 186     /*
 187      * SOMETHING IS WRONG WITH THIS, DON'T USE IT UNTIL IT CAN BE FIXED
 188      *
 189      * // 5th pass methItr = ownAnalysis.descriptorsToAnalyze.iterator(); while(
 190      * methItr.hasNext() ) { Descriptor d = methItr.next(); FlatMethod fm =
 191      * state.getMethodFlat( d );
 192      *
 193      * // prune variable results in one traversal // by removing reference
 194      * variables that are not live pruneVariableResultsWithLiveness( fm ); }
 195      */
 196
 197     // 6th pass
 198     methItr = disjointAnalysis.getDescriptorsToAnalyze().iterator();
 199     while (methItr.hasNext()) {
 200       Descriptor d = methItr.next();
 201       FlatMethod fm = state.getMethodFlat(d);
 202
 203       // compute what is not available at every program
 204       // point, in a forward fixed-point pass
 205       notAvailableForward(fm);
 206     }
 207
 208   }
 209
 210   private void buildForestForward(FlatMethod fm) {
 211
 212     // start from flat method top, visit every node in
 213     // method exactly once, find SESEs and remember
 214     // roots and child relationships
 215     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 216     flatNodesToVisit.add(fm);
 217
 218     Set<FlatNode> visited = new HashSet<FlatNode>();
 219
 220     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 221     seseStacks.put(fm, seseStackFirst);
 222
 223     while (!flatNodesToVisit.isEmpty()) {
 224       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 225       FlatNode fn = fnItr.next();
 226
 227       Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
 228       assert seseStack != null;
 229
 230       flatNodesToVisit.remove(fn);
 231       visited.add(fn);
 232
 233       buildForest_nodeActions(fn, seseStack, fm);
 234
 235       for (int i = 0; i < fn.numNext(); i++) {
 236         FlatNode nn = fn.getNext(i);
 237
 238         if (!visited.contains(nn)) {
 239           flatNodesToVisit.add(nn);
 240
 241           // clone stack and send along each analysis path
 242           seseStacks.put(nn, (Stack<FlatSESEEnterNode>) seseStack.clone());
 243         }
 244       }
 245     }
 246   }
 247
 248   private void buildForest_nodeActions(FlatNode fn, Stack<FlatSESEEnterNode> seseStack,
 249       FlatMethod fm) {
 250     switch (fn.kind()) {
 251
 252     case FKind.FlatSESEEnterNode: {
 253       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 254
 255       if (!fsen.getIsCallerSESEplaceholder()) {
 256         allSESEs.add(fsen);
 257       }
 258
 259       fsen.setfmEnclosing(fm);
 260       fsen.setmdEnclosing(fm.getMethod());
 261       fsen.setcdEnclosing(fm.getMethod().getClassDesc());
 262
 263       if (seseStack.empty()) {
 264         rootSESEs.add(fsen);
 265         fsen.setParent(null);
 266       } else {
 267         seseStack.peek().addChild(fsen);
 268         fsen.setParent(seseStack.peek());
 269       }
 270
 271       seseStack.push(fsen);
 272     }
 273       break;
 274
 275     case FKind.FlatSESEExitNode: {
 276       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 277       assert !seseStack.empty();
 278       FlatSESEEnterNode fsen = seseStack.pop();
 279     }
 280       break;
 281
 282     case FKind.FlatReturnNode: {
 283       FlatReturnNode frn = (FlatReturnNode) fn;
 284       if (!seseStack.empty() && !seseStack.peek().getIsCallerSESEplaceholder()) {
 285         throw new Error("Error: return statement enclosed within SESE "
 286             + seseStack.peek().getPrettyIdentifier());
 287       }
 288     }
 289       break;
 290
 291     }
 292   }
 293
 294   private void livenessAnalysisBackward(FlatSESEEnterNode fsen, boolean toplevel,
 295       Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
 296
 297     // start from an SESE exit, visit nodes in reverse up to
 298     // SESE enter in a fixed-point scheme, where children SESEs
 299     // should already be analyzed and therefore can be skipped
 300     // because child SESE enter node has all necessary info
 301     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 302
 303     if (toplevel) {
 304       flatNodesToVisit.add(fsen.getfmEnclosing().getFlatExit());
 305     } else {
 306       flatNodesToVisit.add(fsen.getFlatExit());
 307     }
 308
 309     Hashtable<FlatNode, Set<TempDescriptor>> livenessResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
 310
 311     if (toplevel) {
 312       liveout = new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
 313     }
 314
 315     while (!flatNodesToVisit.isEmpty()) {
 316       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 317       flatNodesToVisit.remove(fn);
 318
 319       Set<TempDescriptor> prev = livenessResults.get(fn);
 320
 321       // merge sets from control flow joins
 322       Set<TempDescriptor> u = new HashSet<TempDescriptor>();
 323       for (int i = 0; i < fn.numNext(); i++) {
 324         FlatNode nn = fn.getNext(i);
 325         Set<TempDescriptor> s = livenessResults.get(nn);
 326         if (s != null) {
 327           u.addAll(s);
 328         }
 329       }
 330
 331       Set<TempDescriptor> curr = liveness_nodeActions(fn, u, fsen, toplevel, liveout);
 332
 333       // if a new result, schedule backward nodes for analysis
 334       if (!curr.equals(prev)) {
 335         livenessResults.put(fn, curr);
 336
 337         // don't flow backwards past current SESE enter
 338         if (!fn.equals(fsen)) {
 339           for (int i = 0; i < fn.numPrev(); i++) {
 340             FlatNode nn = fn.getPrev(i);
 341             flatNodesToVisit.add(nn);
 342           }
 343         }
 344       }
 345     }
 346
 347     Set<TempDescriptor> s = livenessResults.get(fsen);
 348     if (s != null) {
 349       fsen.addInVarSet(s);
 350     }
 351
 352     // remember liveness per node from the root view as the
 353     // global liveness of variables for later passes to use
 354     if (toplevel) {
 355       livenessRootView.putAll(livenessResults);
 356     }
 357
 358     // post-order traversal, so do children first
 359     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 360     while (childItr.hasNext()) {
 361       FlatSESEEnterNode fsenChild = childItr.next();
 362       livenessAnalysisBackward(fsenChild, false, liveout);
 363     }
 364   }
 365
 366   private Set<TempDescriptor> liveness_nodeActions(FlatNode fn, Set<TempDescriptor> liveIn,
 367       FlatSESEEnterNode currentSESE, boolean toplevel,
 368       Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
 369     switch (fn.kind()) {
 370
 371     case FKind.FlatSESEExitNode:
 372       if (toplevel) {
 373         FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 374         if (!liveout.containsKey(fsexn)) {
 375           liveout.put(fsexn, new HashSet<TempDescriptor>());
 376         }
 377         liveout.get(fsexn).addAll(liveIn);
 378       }
 379       // no break, sese exits should also execute default actions
 380
 381     default: {
 382       // handle effects of statement in reverse, writes then reads
 383       TempDescriptor[] writeTemps = fn.writesTemps();
 384       for (int i = 0; i < writeTemps.length; ++i) {
 385         liveIn.remove(writeTemps[i]);
 386
 387         if (!toplevel) {
 388           FlatSESEExitNode fsexn = currentSESE.getFlatExit();
 389           Set<TempDescriptor> livetemps = liveout.get(fsexn);
 390           if (livetemps != null && livetemps.contains(writeTemps[i])) {
 391             // write to a live out temp...
 392             // need to put in SESE liveout set
 393             currentSESE.addOutVar(writeTemps[i]);
 394           }
 395         }
 396       }
 397
 398       TempDescriptor[] readTemps = fn.readsTemps();
 399       for (int i = 0; i < readTemps.length; ++i) {
 400         liveIn.add(readTemps[i]);
 401       }
 402
 403       Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get(fn);
 404       if (virtualReadTemps != null) {
 405         liveIn.addAll(virtualReadTemps);
 406       }
 407
 408     }
 409       break;
 410
 411     } // end switch
 412
 413     return liveIn;
 414   }
 415
 416   private void variableAnalysisForward(FlatMethod fm) {
 417
 418     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 419     flatNodesToVisit.add(fm);
 420
 421     while (!flatNodesToVisit.isEmpty()) {
 422       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 423       flatNodesToVisit.remove(fn);
 424
 425       Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
 426       assert seseStack != null;
 427
 428       VarSrcTokTable prev = variableResults.get(fn);
 429
 430       // merge sets from control flow joins
 431       VarSrcTokTable curr = new VarSrcTokTable();
 432       for (int i = 0; i < fn.numPrev(); i++) {
 433         FlatNode nn = fn.getPrev(i);
 434         VarSrcTokTable incoming = variableResults.get(nn);
 435         curr.merge(incoming);
 436       }
 437
 438       if (!seseStack.empty()) {
 439         variable_nodeActions(fn, curr, seseStack.peek());
 440       }
 441
 442       // if a new result, schedule forward nodes for analysis
 443       if (!curr.equals(prev)) {
 444         variableResults.put(fn, curr);
 445
 446         for (int i = 0; i < fn.numNext(); i++) {
 447           FlatNode nn = fn.getNext(i);
 448           flatNodesToVisit.add(nn);
 449         }
 450       }
 451     }
 452   }
 453
 454   private void variable_nodeActions(FlatNode fn, VarSrcTokTable vstTable,
 455       FlatSESEEnterNode currentSESE) {
 456     switch (fn.kind()) {
 457
 458     case FKind.FlatSESEEnterNode: {
 459       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 460       assert fsen.equals(currentSESE);
 461
 462       vstTable.age(currentSESE);
 463       vstTable.assertConsistency();
 464     }
 465       break;
 466
 467     case FKind.FlatSESEExitNode: {
 468       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 469       FlatSESEEnterNode fsen = fsexn.getFlatEnter();
 470       assert currentSESE.getChildren().contains(fsen);
 471
 472       // remap all of this child's children tokens to be
 473       // from this child as the child exits
 474       vstTable.remapChildTokens(fsen);
 475
 476       // liveness virtual reads are things that might be
 477       // written by an SESE and should be added to the in-set
 478       // anything virtually read by this SESE should be pruned
 479       // of parent or sibling sources
 480       Set<TempDescriptor> liveVars = livenessRootView.get(fn);
 481       Set<TempDescriptor> fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(
 482           fsen, liveVars);
 483       Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
 484       if (fsenVirtReadsOld != null) {
 485         fsenVirtReads.addAll(fsenVirtReadsOld);
 486       }
 487       livenessVirtualReads.put(fn, fsenVirtReads);
 488
 489       // then all child out-set tokens are guaranteed
 490       // to be filled in, so clobber those entries with
 491       // the latest, clean sources
 492       Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
 493       while (outVarItr.hasNext()) {
 494         TempDescriptor outVar = outVarItr.next();
 495         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 496         ts.add(outVar);
 497         VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
 498         vstTable.remove(outVar);
 499         vstTable.add(vst);
 500       }
 501       vstTable.assertConsistency();
 502
 503     }
 504       break;
 505
 506     case FKind.FlatOpNode: {
 507       FlatOpNode fon = (FlatOpNode) fn;
 508
 509       if (fon.getOp().getOp() == Operation.ASSIGN) {
 510         TempDescriptor lhs = fon.getDest();
 511         TempDescriptor rhs = fon.getLeft();
 512
 513         vstTable.remove(lhs);
 514
 515         Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
 516
 517         Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
 518         while (itr.hasNext()) {
 519           VariableSourceToken vst = itr.next();
 520
 521           HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 522           ts.add(lhs);
 523
 524           if (currentSESE.getChildren().contains(vst.getSESE())) {
 525             // if the source comes from a child, copy it over
 526             forAddition.add(new VariableSourceToken(ts, vst.getSESE(), vst.getAge(), vst
 527                 .getAddrVar()));
 528           } else {
 529             // otherwise, stamp it as us as the source
 530             forAddition.add(new VariableSourceToken(ts, currentSESE, new Integer(0), lhs));
 531           }
 532         }
 533
 534         vstTable.addAll(forAddition);
 535
 536         // only break if this is an ASSIGN op node,
 537         // otherwise fall through to default case
 538         vstTable.assertConsistency();
 539         break;
 540       }
 541     }
 542
 543       // note that FlatOpNode's that aren't ASSIGN
 544       // fall through to this default case
 545     default: {
 546       TempDescriptor[] writeTemps = fn.writesTemps();
 547       if (writeTemps.length > 0) {
 548
 549         // for now, when writeTemps > 1, make sure
 550         // its a call node, programmer enforce only
 551         // doing stuff like calling a print routine
 552         // assert writeTemps.length == 1;
 553         if (writeTemps.length > 1) {
 554           assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
 555           break;
 556         }
 557
 558         vstTable.remove(writeTemps[0]);
 559
 560         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 561         ts.add(writeTemps[0]);
 562
 563         vstTable.add(new VariableSourceToken(ts, currentSESE, new Integer(0), writeTemps[0]));
 564       }
 565
 566       vstTable.assertConsistency();
 567     }
 568       break;
 569
 570     } // end switch
 571   }
 572
 573   private void notAvailableForward(FlatMethod fm) {
 574
 575     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 576     flatNodesToVisit.add(fm);
 577
 578     while (!flatNodesToVisit.isEmpty()) {
 579       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 580       flatNodesToVisit.remove(fn);
 581
 582       Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
 583       assert seseStack != null;
 584
 585       Set<TempDescriptor> prev = notAvailableResults.get(fn);
 586
 587       Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
 588       for (int i = 0; i < fn.numPrev(); i++) {
 589         FlatNode nn = fn.getPrev(i);
 590         Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
 591         if (notAvailIn != null) {
 592           curr.addAll(notAvailIn);
 593         }
 594       }
 595
 596       if (!seseStack.empty()) {
 597         notAvailable_nodeActions(fn, curr, seseStack.peek());
 598       }
 599
 600       // if a new result, schedule forward nodes for analysis
 601       if (!curr.equals(prev)) {
 602         notAvailableResults.put(fn, curr);
 603
 604         for (int i = 0; i < fn.numNext(); i++) {
 605           FlatNode nn = fn.getNext(i);
 606           flatNodesToVisit.add(nn);
 607         }
 608       }
 609     }
 610   }
 611
 612   private void notAvailable_nodeActions(FlatNode fn, Set<TempDescriptor> notAvailSet,
 613       FlatSESEEnterNode currentSESE) {
 614
 615     // any temps that are removed from the not available set
 616     // at this node should be marked in this node's code plan
 617     // as temps to be grabbed at runtime!
 618
 619     switch (fn.kind()) {
 620
 621     case FKind.FlatSESEEnterNode: {
 622       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 623       assert fsen.equals(currentSESE);
 624
 625       // keep a copy of what's not available into the SESE
 626       // and restore it at the matching exit node
 627       Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
 628       Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
 629       while (tdItr.hasNext()) {
 630         notAvailCopy.add(tdItr.next());
 631       }
 632       notAvailableIntoSESE.put(fsen, notAvailCopy);
 633
 634       notAvailSet.clear();
 635     }
 636       break;
 637
 638     case FKind.FlatSESEExitNode: {
 639       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 640       FlatSESEEnterNode fsen = fsexn.getFlatEnter();
 641       assert currentSESE.getChildren().contains(fsen);
 642
 643       notAvailSet.addAll(fsen.getOutVarSet());
 644
 645       Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
 646       assert notAvailIn != null;
 647       notAvailSet.addAll(notAvailIn);
 648
 649     }
 650       break;
 651
 652     case FKind.FlatMethod: {
 653       notAvailSet.clear();
 654     }
 655
 656     case FKind.FlatOpNode: {
 657       FlatOpNode fon = (FlatOpNode) fn;
 658
 659       if (fon.getOp().getOp() == Operation.ASSIGN) {
 660         TempDescriptor lhs = fon.getDest();
 661         TempDescriptor rhs = fon.getLeft();
 662
 663         // copy makes lhs same availability as rhs
 664         if (notAvailSet.contains(rhs)) {
 665           notAvailSet.add(lhs);
 666         } else {
 667           notAvailSet.remove(lhs);
 668         }
 669
 670         // only break if this is an ASSIGN op node,
 671         // otherwise fall through to default case
 672         break;
 673       }
 674     }
 675
 676       // note that FlatOpNode's that aren't ASSIGN
 677       // fall through to this default case
 678     default: {
 679       TempDescriptor[] writeTemps = fn.writesTemps();
 680       for (int i = 0; i < writeTemps.length; i++) {
 681         TempDescriptor wTemp = writeTemps[i];
 682         notAvailSet.remove(wTemp);
 683       }
 684       TempDescriptor[] readTemps = fn.readsTemps();
 685       for (int i = 0; i < readTemps.length; i++) {
 686         TempDescriptor rTemp = readTemps[i];
 687         notAvailSet.remove(rTemp);
 688
 689         // if this variable has exactly one source, potentially
 690         // get other things from this source as well
 691         VarSrcTokTable vstTable = variableResults.get(fn);
 692
 693         VSTWrapper vstIfStatic = new VSTWrapper();
 694         Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
 695
 696         if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
 697
 698           VariableSourceToken vst = vstIfStatic.vst;
 699
 700           Iterator<VariableSourceToken> availItr = vstTable.get(vst.getSESE(), vst.getAge())
 701               .iterator();
 702
 703           // look through things that are also available from same source
 704           while (availItr.hasNext()) {
 705             VariableSourceToken vstAlsoAvail = availItr.next();
 706
 707             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
 708             while (refVarItr.hasNext()) {
 709               TempDescriptor refVarAlso = refVarItr.next();
 710
 711               // if a variable is available from the same source, AND it ALSO
 712               // only comes from one statically known source, mark it available
 713               VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
 714               Integer srcTypeAlso = vstTable.getRefVarSrcType(refVarAlso, currentSESE,
 715                   vstIfStaticNotUsed);
 716               if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
 717                 notAvailSet.remove(refVarAlso);
 718               }
 719             }
 720           }
 721         }
 722       }
 723     }
 724       break;
 725
 726     } // end switch
 727   }
 728
 729 }