Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java

   1 package Analysis.OoOJava;
   2
   3 import java.io.BufferedWriter;
   4 import java.io.FileWriter;
   5 import java.io.IOException;
   6 import java.util.Enumeration;
   7 import java.util.HashSet;
   8 import java.util.Hashtable;
   9 import java.util.Iterator;
  10 import java.util.Map;
  11 import java.util.Set;
  12 import java.util.Stack;
  13 import java.util.Map.Entry;
  14
  15 import Analysis.ArrayReferencees;
  16 import Analysis.Liveness;
  17 import Analysis.CallGraph.CallGraph;
  18 import Analysis.Disjoint.DisjointAnalysis;
  19 import Analysis.Disjoint.Effect;
  20 import Analysis.Disjoint.EffectsAnalysis;
  21 import Analysis.Disjoint.Taint;
  22 import IR.Descriptor;
  23 import IR.MethodDescriptor;
  24 import IR.Operation;
  25 import IR.State;
  26 import IR.TypeUtil;
  27 import IR.Flat.FKind;
  28 import IR.Flat.FlatCall;
  29 import IR.Flat.FlatEdge;
  30 import IR.Flat.FlatElementNode;
  31 import IR.Flat.FlatFieldNode;
  32 import IR.Flat.FlatMethod;
  33 import IR.Flat.FlatNew;
  34 import IR.Flat.FlatNode;
  35 import IR.Flat.FlatOpNode;
  36 import IR.Flat.FlatSESEEnterNode;
  37 import IR.Flat.FlatSESEExitNode;
  38 import IR.Flat.FlatSetElementNode;
  39 import IR.Flat.FlatSetFieldNode;
  40 import IR.Flat.FlatWriteDynamicVarNode;
  41 import IR.Flat.TempDescriptor;
  42
  43 public class OoOJavaAnalysis {
  44
  45   // data from the compiler
  46   private State state;
  47   private TypeUtil typeUtil;
  48   private CallGraph callGraph;
  49   private RBlockRelationAnalysis rblockRel;
  50   private DisjointAnalysis disjointAnalysisTaints;
  51   private DisjointAnalysis disjointAnalysisReach;
  52
  53   private Set<MethodDescriptor> descriptorsToAnalyze;
  54
  55   private Hashtable<FlatNode, Set<TempDescriptor>> livenessGlobalView;
  56   private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
  57   private Hashtable<FlatNode, VarSrcTokTable> variableResults;
  58   private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
  59   private Hashtable<FlatNode, CodePlan> codePlans;
  60
  61   private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
  62
  63   private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
  64
  65   private Hashtable<FlatNode, ContextTaskNames> fn2contextTaskNames;
  66
  67
  68   // temporal data structures to track analysis progress.
  69   static private int uniqueLockSetId = 0;
  70   // mapping of a conflict graph to its compiled lock
  71   private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
  72   // mapping of a sese block to its conflict graph
  73   private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
  74
  75   public static int maxSESEage = -1;
  76
  77   public int getMaxSESEage() {
  78     return maxSESEage;
  79   }
  80
  81   // may be null
  82   public CodePlan getCodePlan(FlatNode fn) {
  83     CodePlan cp = codePlans.get(fn);
  84     return cp;
  85   }
  86
  87   public Set<FlatNode> getNodesWithPlans() {
  88     return codePlans.keySet();
  89   }
  90
  91   public ContextTaskNames getContextTaskNames( FlatMethod fm ) {
  92     ContextTaskNames out = fn2contextTaskNames.get( fm );
  93     if( out == null ) {
  94       out = new ContextTaskNames();
  95     }
  96     return out;
  97   }
  98
  99   public ContextTaskNames getContextTaskNames( FlatSESEEnterNode fsen ) {
 100     ContextTaskNames out = fn2contextTaskNames.get( fsen );
 101     if( out == null ) {
 102       out = new ContextTaskNames();
 103     }
 104     return out;
 105   }
 106
 107   public DisjointAnalysis getDisjointAnalysis() {
 108     return disjointAnalysisTaints;
 109   }
 110
 111
 112   public OoOJavaAnalysis(State state,
 113                          TypeUtil typeUtil,
 114                          CallGraph callGraph,
 115                          Liveness liveness,
 116                          ArrayReferencees arrayReferencees) {
 117
 118     double timeStartAnalysis = (double) System.nanoTime();
 119
 120     this.state = state;
 121     this.typeUtil = typeUtil;
 122     this.callGraph = callGraph;
 123     this.maxSESEage = state.OOO_MAXSESEAGE;
 124
 125     livenessGlobalView     = new Hashtable<FlatNode, Set<TempDescriptor>>();
 126     livenessVirtualReads   = new Hashtable<FlatNode, Set<TempDescriptor>>();
 127     variableResults        = new Hashtable<FlatNode, VarSrcTokTable>();
 128     notAvailableResults    = new Hashtable<FlatNode, Set<TempDescriptor>>();
 129     codePlans              = new Hashtable<FlatNode, CodePlan>();
 130     wdvNodesToSpliceIn     = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
 131     notAvailableIntoSESE   = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
 132     sese2conflictGraph     = new Hashtable<FlatNode, ConflictGraph>();
 133     conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
 134     fn2contextTaskNames    = new Hashtable<FlatNode, ContextTaskNames>();
 135
 136     // add all methods transitively reachable from the
 137     // source's main to set for analysis
 138     MethodDescriptor mdSourceEntry = typeUtil.getMain();
 139     FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
 140
 141     descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
 142
 143     descriptorsToAnalyze.add(mdSourceEntry);
 144
 145     // 1st pass, find basic rblock relations & potential stall sites
 146     rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
 147     VarSrcTokTable.rblockRel = rblockRel;
 148
 149     // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
 150     Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
 151     while (methItr.hasNext()) {
 152       Descriptor d = methItr.next();
 153       FlatMethod fm = state.getMethodFlat(d);
 154
 155       // note we can't use the general liveness analysis already in
 156       // the compiler because this analysis is task-aware
 157       livenessAnalysisBackward(fm);
 158     }
 159
 160     // 3rd pass, variable analysis
 161     methItr = descriptorsToAnalyze.iterator();
 162     while (methItr.hasNext()) {
 163       Descriptor d = methItr.next();
 164       FlatMethod fm = state.getMethodFlat(d);
 165
 166       // starting from roots do a forward, fixed-point
 167       // variable analysis for refinement and stalls
 168       variableAnalysisForward(fm);
 169     }
 170
 171     // 4th pass, compute liveness contribution from
 172     // virtual reads discovered in variable pass
 173     methItr = descriptorsToAnalyze.iterator();
 174     while (methItr.hasNext()) {
 175       Descriptor d = methItr.next();
 176       FlatMethod fm = state.getMethodFlat(d);
 177       livenessAnalysisBackward(fm);
 178     }
 179
 180     // 5th pass, use disjointness with NO FLAGGED REGIONS
 181     // to compute taints and effects
 182     disjointAnalysisTaints =
 183         new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
 184                              rblockRel,
 185                              true ); // suppress output--this is an intermediate pass
 186
 187     // 6th pass, not available analysis FOR VARIABLES!
 188     methItr = descriptorsToAnalyze.iterator();
 189     while (methItr.hasNext()) {
 190       Descriptor d = methItr.next();
 191       FlatMethod fm = state.getMethodFlat(d);
 192
 193       // compute what is not available at every program
 194       // point, in a forward fixed-point pass
 195       notAvailableForward(fm);
 196     }
 197
 198     // 7th pass, make conflict graph
 199     // conflict graph is maintained by each parent sese,
 200     // where its' own stall sites and children may appear
 201     Set<FlatSESEEnterNode> allSESEs=rblockRel.getAllSESEs();
 202     for (Iterator iterator = allSESEs.iterator(); iterator.hasNext();) {
 203
 204       FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
 205       if (!parent.getIsLeafSESE()) {
 206
 207         EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
 208         ConflictGraph conflictGraph = sese2conflictGraph.get(parent);
 209         if (conflictGraph == null) {
 210           conflictGraph = new ConflictGraph(state);
 211         }
 212
 213         Set<FlatSESEEnterNode> children = parent.getChildren();
 214         for (Iterator iterator2 = children.iterator(); iterator2.hasNext();) {
 215           FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
 216           Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(child);
 217           conflictGraph.addLiveIn(taint2Effects);
 218           sese2conflictGraph.put(parent, conflictGraph);
 219         }
 220       }
 221     }
 222
 223     Iterator descItr = descriptorsToAnalyze.iterator();
 224     while (descItr.hasNext()) {
 225       Descriptor d = (Descriptor) descItr.next();
 226       FlatMethod fm = state.getMethodFlat(d);
 227       if (fm != null) {
 228         makeConflictGraph(fm);
 229       }
 230     }
 231
 232
 233     // 8th pass, calculate all possible conflicts without using
 234     // reachability info and identify set of FlatNew that next
 235     // disjoint reach. analysis should flag
 236     Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
 237     calculateConflicts(sitesToFlag, false);
 238
 239
 240     if (!state.RCR) {
 241       // 9th pass, ask disjoint analysis to compute reachability
 242       // for objects that may cause heap conflicts so the most
 243       // efficient method to deal with conflict can be computed
 244       // later
 245       disjointAnalysisReach =
 246         new DisjointAnalysis(state, typeUtil, callGraph, liveness,
 247                              arrayReferencees, sitesToFlag,
 248                              null // don't do effects analysis again!
 249                              );
 250
 251       // 10th pass, calculate conflicts with reachability info
 252       calculateConflicts(null, true);
 253     }
 254
 255     // 11th pass, compiling locks
 256     synthesizeLocks();
 257
 258     // 12th pass, compute a plan for code injections
 259     methItr = descriptorsToAnalyze.iterator();
 260     while (methItr.hasNext()) {
 261       Descriptor d = methItr.next();
 262       FlatMethod fm = state.getMethodFlat(d);
 263       codePlansForward(fm);
 264     }
 265
 266     // 13th pass,
 267     // splice new IR nodes into graph after all
 268     // analysis passes are complete
 269     Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
 270     while (spliceItr.hasNext()) {
 271       Map.Entry me = (Map.Entry) spliceItr.next();
 272       FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
 273       fwdvn.spliceIntoIR();
 274     }
 275
 276
 277     if (state.OOODEBUG) {
 278       try {
 279         writeReports("");
 280         disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
 281         writeConflictGraph();
 282       } catch (IOException e) {}
 283     }
 284
 285
 286     System.out.println("\n\n\n##########################################################\n"+
 287                        "Warning, lots of code changes going on, OoOJava and RCR/DFJ\n"+
 288                        "systems are being cleaned up.  Until the analyses and code gen\n"+
 289                        "are fully altered and coordinated, these systems will not run\n"+
 290                        "to completion.  Partial stable check-ins are necessary to manage\n"+
 291                        "the number of files getting touched.\n"+
 292                        "##########################################################" );
 293     System.exit( 0 );
 294   }
 295
 296
 297
 298     // debug routine
 299     /*
 300      * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
 301      * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn =
 302      * (FlatNode) e.getKey(); ConflictGraph conflictGraph = (ConflictGraph)
 303      * e.getValue();
 304      * System.out.println("---------------------------------------");
 305      * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
 306      * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
 307      * iterator.hasNext();) { String key = (String) iterator.next();
 308      * ConflictNode node = conflictGraph.id2cn.get(key);
 309      * System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } }
 310      */
 311
 312
 313
 314
 315   private void writeFile(Set<FlatNew> sitesToFlag) {
 316
 317     try {
 318       BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
 319
 320       for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
 321         FlatNew fn = (FlatNew) iterator.next();
 322         bw.write(fn + "\n");
 323       }
 324       bw.close();
 325     } catch (IOException e) {
 326
 327     }
 328
 329   }
 330
 331
 332   private void livenessAnalysisBackward(FlatMethod fm) {
 333
 334     // flow backward across nodes to compute liveness, and
 335     // take special care with sese enter/exit nodes that
 336     // alter this from normal liveness analysis
 337     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 338     flatNodesToVisit.add( fm.getFlatExit() );
 339
 340     while( !flatNodesToVisit.isEmpty() ) {
 341       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 342       flatNodesToVisit.remove( fn );
 343
 344       Set<TempDescriptor> prev = livenessGlobalView.get( fn );
 345
 346       // merge sets from control flow joins
 347       Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
 348       for (int i = 0; i < fn.numNext(); i++) {
 349         FlatNode nn = fn.getNext( i );
 350         Set<TempDescriptor> s = livenessGlobalView.get( nn );
 351         if( s != null ) {
 352           livein.addAll( s );
 353         }
 354       }
 355
 356       Set<TempDescriptor> curr = liveness_nodeActions( fn, livein );
 357
 358       // if a new result, schedule backward nodes for analysis
 359       if( !curr.equals( prev ) ) {
 360         livenessGlobalView.put( fn, curr );
 361
 362         for( int i = 0; i < fn.numPrev(); i++ ) {
 363           FlatNode nn = fn.getPrev( i );
 364           flatNodesToVisit.add( nn );
 365         }
 366       }
 367     }
 368   }
 369
 370   private Set<TempDescriptor> liveness_nodeActions( FlatNode            fn,
 371                                                     Set<TempDescriptor> liveIn
 372                                                     ) {
 373     switch( fn.kind() ) {
 374
 375     case FKind.FlatSESEEnterNode: {
 376       // add whatever is live-in at a task enter to that
 377       // task's in-var set
 378       FlatSESEEnterNode fsen = (FlatSESEEnterNode)fn;
 379       if( liveIn != null ) {
 380         fsen.addInVarSet( liveIn );
 381       }
 382       // no break, should also execute default actions
 383     }
 384
 385     default: {
 386       // handle effects of statement in reverse, writes then reads
 387       TempDescriptor[] writeTemps = fn.writesTemps();
 388       for( int i = 0; i < writeTemps.length; ++i ) {
 389         liveIn.remove( writeTemps[i] );
 390
 391         // if we are analyzing code declared directly in a task,
 392         FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock( fn );
 393         if( fsen != null ) {
 394           // check to see if we are writing to variables that will
 395           // be live-out at the task's exit (and therefore should
 396           // go in the task's out-var set)
 397           FlatSESEExitNode fsexn = fsen.getFlatExit();
 398           Set<TempDescriptor> livetemps = livenessGlobalView.get( fsexn );
 399           if( livetemps != null && livetemps.contains( writeTemps[i] ) ) {
 400             fsen.addOutVar( writeTemps[i] );
 401           }
 402         }
 403       }
 404
 405       TempDescriptor[] readTemps = fn.readsTemps();
 406       for( int i = 0; i < readTemps.length; ++i ) {
 407         liveIn.add( readTemps[i] );
 408       }
 409
 410       Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
 411       if( virtualReadTemps != null ) {
 412         liveIn.addAll( virtualReadTemps );
 413       }
 414     } break;
 415
 416     } // end switch
 417
 418     return liveIn;
 419   }
 420
 421
 422   private void variableAnalysisForward(FlatMethod fm) {
 423
 424     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 425     flatNodesToVisit.add(fm);
 426
 427     while (!flatNodesToVisit.isEmpty()) {
 428       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 429       flatNodesToVisit.remove(fn);
 430
 431       VarSrcTokTable prev = variableResults.get(fn);
 432
 433       // merge sets from control flow joins
 434       VarSrcTokTable curr = new VarSrcTokTable();
 435       for (int i = 0; i < fn.numPrev(); i++) {
 436         FlatNode nn = fn.getPrev(i);
 437         VarSrcTokTable incoming = variableResults.get(nn);
 438         curr.merge(incoming);
 439       }
 440
 441       FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
 442       if( currentSESE == null ) {
 443         currentSESE = rblockRel.getCallerProxySESE();
 444       }
 445
 446       variable_nodeActions(fn, curr, currentSESE);
 447
 448       // if a new result, schedule forward nodes for analysis
 449       if (!curr.equals(prev)) {
 450         variableResults.put(fn, curr);
 451
 452         for (int i = 0; i < fn.numNext(); i++) {
 453           FlatNode nn = fn.getNext(i);
 454           flatNodesToVisit.add(nn);
 455         }
 456       }
 457     }
 458   }
 459
 460   private void variable_nodeActions(FlatNode          fn,
 461                                     VarSrcTokTable    vstTable,
 462                                     FlatSESEEnterNode currentSESE) {
 463     switch (fn.kind()) {
 464
 465
 466     case FKind.FlatSESEEnterNode: {
 467       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 468       // ignore currently executing SESE, at this point
 469       // the analysis considers a new instance is becoming
 470       // the current SESE
 471       vstTable.age(fsen);
 472       vstTable.assertConsistency();
 473     } break;
 474
 475
 476     case FKind.FlatSESEExitNode: {
 477       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 478
 479       // fsen is the child of currently executing tasks
 480       FlatSESEEnterNode fsen = fsexn.getFlatEnter();
 481
 482       // remap all of this child's children tokens to be
 483       // from this child as the child exits
 484       vstTable.remapChildTokens(fsen);
 485
 486       // liveness virtual reads are things that might be
 487       // written by an SESE and should be added to the in-set
 488       // anything virtually read by this SESE should be pruned
 489       // of parent or sibling sources
 490       Set<TempDescriptor> liveVars = livenessGlobalView.get(fn);
 491       Set<TempDescriptor> fsenVirtReads =
 492         vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen,
 493                                                              liveVars);
 494
 495       Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
 496       if (fsenVirtReadsOld != null) {
 497         fsenVirtReads.addAll(fsenVirtReadsOld);
 498       }
 499       livenessVirtualReads.put(fn, fsenVirtReads);
 500
 501       // then all child out-set tokens are guaranteed
 502       // to be filled in, so clobber those entries with
 503       // the latest, clean sources
 504       Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
 505       while (outVarItr.hasNext()) {
 506         TempDescriptor outVar = outVarItr.next();
 507         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 508         ts.add(outVar);
 509         VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
 510         vstTable.remove(outVar);
 511         vstTable.add(vst);
 512       }
 513       vstTable.assertConsistency();
 514     } break;
 515
 516
 517     case FKind.FlatOpNode: {
 518       FlatOpNode fon = (FlatOpNode) fn;
 519
 520       if (fon.getOp().getOp() == Operation.ASSIGN) {
 521         TempDescriptor lhs = fon.getDest();
 522         TempDescriptor rhs = fon.getLeft();
 523
 524         vstTable.remove(lhs);
 525
 526         Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
 527
 528         Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
 529         while (itr.hasNext()) {
 530           VariableSourceToken vst = itr.next();
 531
 532           HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 533           ts.add(lhs);
 534
 535           // when we do x = y for variables, just copy over from a child,
 536           // there are two cases:
 537           //  1. if the current task is the caller proxy, any local root is a child
 538           boolean case1 =
 539             currentSESE.getIsCallerProxySESE() &&
 540             rblockRel.getLocalRootSESEs().contains( vst.getSESE() );
 541
 542           //  2. if the child task is a locally-defined child of the current task
 543           boolean case2 = currentSESE.getLocalChildren().contains( vst.getSESE() );
 544
 545           if( case1 || case2 ) {
 546             // if the source comes from a child, copy it over
 547             forAddition.add( new VariableSourceToken( ts,
 548                                                       vst.getSESE(),
 549                                                       vst.getAge(),
 550                                                       vst.getAddrVar()
 551                                                       )
 552                              );
 553           } else {
 554             // otherwise, stamp it as us as the source
 555             forAddition.add( new VariableSourceToken( ts,
 556                                                       currentSESE,
 557                                                       new Integer( 0 ),
 558                                                       lhs
 559                                                       )
 560                              );
 561           }
 562         }
 563
 564         vstTable.addAll( forAddition );
 565
 566         // only break if this is an ASSIGN op node,
 567         // otherwise fall through to default case
 568         vstTable.assertConsistency();
 569         break;
 570       }
 571     }
 572
 573       // note that FlatOpNode's that aren't ASSIGN
 574       // fall through to this default case
 575     default: {
 576       TempDescriptor[] writeTemps = fn.writesTemps();
 577       if( writeTemps.length > 0 ) {
 578
 579         // for now, when writeTemps > 1, make sure
 580         // its a call node, programmer enforce only
 581         // doing stuff like calling a print routine
 582         if( writeTemps.length > 1 ) {
 583           assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
 584           break;
 585         }
 586
 587         vstTable.remove( writeTemps[0] );
 588
 589         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 590         ts.add( writeTemps[0] );
 591
 592         vstTable.add( new VariableSourceToken( ts,
 593                                                currentSESE,
 594                                                new Integer( 0 ),
 595                                                writeTemps[0]
 596                                                )
 597                       );
 598       }
 599
 600       vstTable.assertConsistency();
 601     } break;
 602
 603     } // end switch
 604   }
 605
 606
 607   private void notAvailableForward(FlatMethod fm) {
 608
 609     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 610     flatNodesToVisit.add(fm);
 611
 612     while (!flatNodesToVisit.isEmpty()) {
 613       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 614       flatNodesToVisit.remove(fn);
 615
 616       Set<TempDescriptor> prev = notAvailableResults.get(fn);
 617
 618       Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
 619       for (int i = 0; i < fn.numPrev(); i++) {
 620         FlatNode nn = fn.getPrev(i);
 621         Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
 622         if (notAvailIn != null) {
 623           curr.addAll(notAvailIn);
 624         }
 625       }
 626
 627       FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
 628       if( currentSESE == null ) {
 629         currentSESE = rblockRel.getCallerProxySESE();
 630       }
 631
 632       notAvailable_nodeActions(fn, curr, currentSESE);
 633
 634       // if a new result, schedule forward nodes for analysis
 635       if (!curr.equals(prev)) {
 636         notAvailableResults.put(fn, curr);
 637
 638         for (int i = 0; i < fn.numNext(); i++) {
 639           FlatNode nn = fn.getNext(i);
 640           flatNodesToVisit.add(nn);
 641         }
 642       }
 643     }
 644   }
 645
 646   private void notAvailable_nodeActions(FlatNode            fn,
 647                                         Set<TempDescriptor> notAvailSet,
 648                                         FlatSESEEnterNode   currentSESE
 649                                         ) {
 650
 651     // any temps that are removed from the not available set
 652     // at this node should be marked in this node's code plan
 653     // as temps to be grabbed at runtime!
 654
 655     switch (fn.kind()) {
 656
 657     case FKind.FlatSESEEnterNode: {
 658       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 659
 660       // keep a copy of what's not available into the SESE
 661       // and restore it at the matching exit node
 662       Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
 663       Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
 664       while (tdItr.hasNext()) {
 665         notAvailCopy.add(tdItr.next());
 666       }
 667       notAvailableIntoSESE.put(fsen, notAvailCopy);
 668
 669       notAvailSet.clear();
 670     } break;
 671
 672     case FKind.FlatSESEExitNode: {
 673       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 674       FlatSESEEnterNode fsen = fsexn.getFlatEnter();
 675
 676       notAvailSet.addAll(fsen.getOutVarSet());
 677
 678       Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
 679       assert notAvailIn != null;
 680       notAvailSet.addAll(notAvailIn);
 681     } break;
 682
 683     case FKind.FlatMethod: {
 684       notAvailSet.clear();
 685     } break;
 686
 687     case FKind.FlatOpNode: {
 688       FlatOpNode fon = (FlatOpNode) fn;
 689
 690       if (fon.getOp().getOp() == Operation.ASSIGN) {
 691         TempDescriptor lhs = fon.getDest();
 692         TempDescriptor rhs = fon.getLeft();
 693
 694         // copy makes lhs same availability as rhs
 695         if (notAvailSet.contains(rhs)) {
 696           notAvailSet.add(lhs);
 697         } else {
 698           notAvailSet.remove(lhs);
 699         }
 700
 701         // only break if this is an ASSIGN op node,
 702         // otherwise fall through to default case
 703         break;
 704       }
 705     }
 706
 707       // note that FlatOpNode's that aren't ASSIGN
 708       // fall through to this default case
 709     default: {
 710       TempDescriptor[] writeTemps = fn.writesTemps();
 711       for (int i = 0; i < writeTemps.length; i++) {
 712         TempDescriptor wTemp = writeTemps[i];
 713         notAvailSet.remove(wTemp);
 714       }
 715       TempDescriptor[] readTemps = fn.readsTemps();
 716       for (int i = 0; i < readTemps.length; i++) {
 717         TempDescriptor rTemp = readTemps[i];
 718         notAvailSet.remove(rTemp);
 719
 720         // if this variable has exactly one source, potentially
 721         // get other things from this source as well
 722         VarSrcTokTable vstTable = variableResults.get(fn);
 723
 724         VSTWrapper vstIfStatic = new VSTWrapper();
 725         Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
 726
 727         if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
 728
 729           VariableSourceToken vst = vstIfStatic.vst;
 730
 731           Iterator<VariableSourceToken> availItr =
 732               vstTable.get(vst.getSESE(), vst.getAge()).iterator();
 733
 734           // look through things that are also available from same source
 735           while (availItr.hasNext()) {
 736             VariableSourceToken vstAlsoAvail = availItr.next();
 737
 738             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
 739             while (refVarItr.hasNext()) {
 740               TempDescriptor refVarAlso = refVarItr.next();
 741
 742               // if a variable is available from the same source, AND it ALSO
 743               // only comes from one statically known source, mark it available
 744               VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
 745               Integer srcTypeAlso =
 746                   vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
 747               if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
 748                 notAvailSet.remove(refVarAlso);
 749               }
 750             }
 751           }
 752         }
 753       }
 754     } break;
 755
 756     } // end switch
 757   }
 758
 759
 760   private void codePlansForward(FlatMethod fm) {
 761
 762     // start from flat method top, visit every node in
 763     // method exactly once
 764     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 765     flatNodesToVisit.add(fm);
 766
 767     Set<FlatNode> visited = new HashSet<FlatNode>();
 768
 769     while (!flatNodesToVisit.isEmpty()) {
 770       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 771       FlatNode fn = fnItr.next();
 772
 773       flatNodesToVisit.remove(fn);
 774       visited.add(fn);
 775
 776       // use incoming results as "dot statement" or just
 777       // before the current statement
 778       VarSrcTokTable dotSTtable = new VarSrcTokTable();
 779       for (int i = 0; i < fn.numPrev(); i++) {
 780         FlatNode nn = fn.getPrev(i);
 781         dotSTtable.merge(variableResults.get(nn));
 782       }
 783
 784       // find dt-st notAvailableSet also
 785       Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
 786       for (int i = 0; i < fn.numPrev(); i++) {
 787         FlatNode nn = fn.getPrev(i);
 788         Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
 789         if (notAvailIn != null) {
 790           dotSTnotAvailSet.addAll(notAvailIn);
 791         }
 792       }
 793
 794       Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
 795
 796       FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
 797       if( currentSESE == null ) {
 798         currentSESE = rblockRel.getCallerProxySESE();
 799       }
 800
 801       codePlans_nodeActions(fm, fn,
 802                             dotSTlive, dotSTtable, dotSTnotAvailSet,
 803                             currentSESE);
 804
 805       for (int i = 0; i < fn.numNext(); i++) {
 806         FlatNode nn = fn.getNext(i);
 807
 808         if (!visited.contains(nn)) {
 809           flatNodesToVisit.add(nn);
 810         }
 811       }
 812     }
 813   }
 814
 815   private void codePlans_nodeActions(FlatMethod fm,
 816                                      FlatNode fn,
 817                                      Set<TempDescriptor> liveSetIn,
 818                                      VarSrcTokTable vstTableIn,
 819                                      Set<TempDescriptor> notAvailSetIn,
 820                                      FlatSESEEnterNode currentSESE) {
 821
 822     CodePlan plan = new CodePlan(currentSESE);
 823
 824     switch (fn.kind()) {
 825
 826     case FKind.FlatSESEEnterNode: {
 827       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 828
 829       // track the source types of the in-var set so generated
 830       // code at this SESE issue can compute the number of
 831       // dependencies properly
 832       Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
 833       while (inVarItr.hasNext()) {
 834         TempDescriptor inVar = inVarItr.next();
 835
 836         // when we get to an SESE enter node we change the
 837         // currentSESE variable of this analysis to the
 838         // child that is declared by the enter node, so
 839         // in order to classify in-vars correctly, pass
 840         // the parent SESE in--at other FlatNode types just
 841         // use the currentSESE
 842         FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock( fn );
 843         if( parent == null ) {
 844           parent = rblockRel.getCallerProxySESE();
 845         }
 846
 847         VSTWrapper vstIfStatic = new VSTWrapper();
 848         Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic);
 849
 850         // the current SESE needs a local space to track the dynamic
 851         // variable and the child needs space in its SESE record
 852         if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
 853           fsen.addDynamicInVar(inVar);
 854           addDynamicVar( fsen, fm, inVar );
 855
 856         } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
 857           fsen.addStaticInVar(inVar);
 858           VariableSourceToken vst = vstIfStatic.vst;
 859           fsen.putStaticInVar2src(inVar, vst);
 860           fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
 861         } else {
 862           assert srcType.equals(VarSrcTokTable.SrcType_READY);
 863           fsen.addReadyInVar(inVar);
 864         }
 865       }
 866     } break;
 867
 868     case FKind.FlatSESEExitNode: {
 869       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 870       //TODO! Shouldn't there be a code plan for task exit
 871       // where the exiting task calculates whether its own
 872       // siblings need variables from its children, so the
 873       // exiter should copy those variables into its own out-set
 874       // and make the available?
 875     } break;
 876
 877     case FKind.FlatOpNode: {
 878       FlatOpNode fon = (FlatOpNode) fn;
 879
 880       if (fon.getOp().getOp() == Operation.ASSIGN) {
 881         TempDescriptor lhs = fon.getDest();
 882         TempDescriptor rhs = fon.getLeft();
 883
 884         // if this is an op node, don't stall, copy
 885         // source and delay until we need to use value
 886
 887         // ask whether lhs and rhs sources are dynamic, static, etc.
 888         VSTWrapper vstIfStatic = new VSTWrapper();
 889         Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
 890         Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
 891
 892         if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
 893           // if rhs is dynamic going in, lhs will definitely be dynamic
 894           // going out of this node, so track that here
 895           plan.addDynAssign( lhs, rhs );
 896           addDynamicVar( currentSESE, fm, lhs );
 897           addDynamicVar( currentSESE, fm, rhs );
 898
 899         } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
 900           // otherwise, if the lhs is dynamic, but the rhs is not, we
 901           // need to update the variable's dynamic source as "current SESE"
 902           plan.addDynAssign(lhs);
 903         }
 904
 905         // only break if this is an ASSIGN op node,
 906         // otherwise fall through to default case
 907         break;
 908       }
 909     }
 910
 911       // note that FlatOpNode's that aren't ASSIGN
 912       // fall through to this default case
 913     default: {
 914
 915       // a node with no live set has nothing to stall for
 916       if (liveSetIn == null) {
 917         break;
 918       }
 919
 920       TempDescriptor[] readarray = fn.readsTemps();
 921       for (int i = 0; i < readarray.length; i++) {
 922         TempDescriptor readtmp = readarray[i];
 923
 924         // ignore temps that are definitely available
 925         // when considering to stall on it
 926         if (!notAvailSetIn.contains(readtmp)) {
 927           continue;
 928         }
 929
 930         // check the source type of this variable
 931         VSTWrapper vstIfStatic = new VSTWrapper();
 932         Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
 933
 934         if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
 935           // 1) It is not clear statically where this variable will
 936           // come from, so dynamically we must keep track
 937           // along various control paths, and therefore when we stall,
 938           // just stall for the exact thing we need and move on
 939           plan.addDynamicStall( readtmp );
 940           addDynamicVar( currentSESE, fm, readtmp );
 941
 942         } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
 943           // 2) Single token/age pair: Stall for token/age pair, and copy
 944           // all live variables with same token/age pair at the same
 945           // time. This is the same stuff that the notavaialable analysis
 946           // marks as now available.
 947           VariableSourceToken vst = vstIfStatic.vst;
 948
 949           Iterator<VariableSourceToken> availItr =
 950               vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
 951
 952           while (availItr.hasNext()) {
 953             VariableSourceToken vstAlsoAvail = availItr.next();
 954
 955             // only grab additional stuff that is live
 956             Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
 957
 958             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
 959             while (refVarItr.hasNext()) {
 960               TempDescriptor refVar = refVarItr.next();
 961               if (liveSetIn.contains(refVar)) {
 962                 copySet.add(refVar);
 963               }
 964             }
 965
 966             if (!copySet.isEmpty()) {
 967               plan.addStall2CopySet(vstAlsoAvail, copySet);
 968             }
 969           }
 970
 971         } else {
 972           // the other case for srcs is READY, so do nothing
 973         }
 974
 975         // assert that everything being stalled for is in the
 976         // "not available" set coming into this flat node and
 977         // that every VST identified is in the possible "stall set"
 978         // that represents VST's from children SESE's
 979
 980       }
 981     }
 982       break;
 983
 984     } // end switch
 985
 986     // identify sese-age pairs that are statically useful
 987     // and should have an associated SESE variable in code
 988     // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
 989     // AND ALWAYS GIVE NAMES TO LOCAL PARENTS
 990     Set<VariableSourceToken> staticSet = vstTableIn.get();
 991     Iterator<VariableSourceToken> vstItr = staticSet.iterator();
 992     while (vstItr.hasNext()) {
 993       VariableSourceToken vst = vstItr.next();
 994
 995       // the caller proxy generates useful analysis facts, but we
 996       // never need to generate another name for it in code (it is
 997       // ALWAYS the task executing the local method context)
 998       if( vst.getSESE().getIsCallerProxySESE() ) {
 999         continue;
1000       }
1001
1002       SESEandAgePair sap = new SESEandAgePair( vst.getSESE(), vst.getAge() );
1003       sap.getSESE().mustTrackAtLeastAge( sap.getAge() );
1004
1005       FlatSESEEnterNode sese = currentSESE;
1006       while( sese != null ) {
1007         addNeededStaticName( sese, fm, sap );
1008         sese = sese.getLocalParent();
1009       }
1010     }
1011
1012     codePlans.put(fn, plan);
1013
1014     // if any variables at this-node-*dot* have a static source (exactly one
1015     // vst)
1016     // but go to a dynamic source at next-node-*dot*, create a new IR graph
1017     // node on that edge to track the sources dynamically
1018     VarSrcTokTable thisVstTable = variableResults.get(fn);
1019     for (int i = 0; i < fn.numNext(); i++) {
1020       FlatNode nn = fn.getNext(i);
1021       VarSrcTokTable nextVstTable = variableResults.get(nn);
1022       Set<TempDescriptor> nextLiveIn = livenessGlobalView.get(nn);
1023
1024       // the table can be null if it is one of the few IR nodes
1025       // completely outside of the root SESE scope
1026       if (nextVstTable != null && nextLiveIn != null) {
1027
1028         Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1029             thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE);
1030
1031         if (!readyOrStatic2dynamicSet.isEmpty()) {
1032
1033           // either add these results to partial fixed-point result
1034           // or make a new one if we haven't made any here yet
1035           FlatEdge fe = new FlatEdge(fn, nn);
1036           FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1037
1038           if (fwdvn == null) {
1039             fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE);
1040             wdvNodesToSpliceIn.put(fe, fwdvn);
1041           } else {
1042             fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1043           }
1044         }
1045       }
1046     }
1047   }
1048
1049   private void addDynamicVar( FlatSESEEnterNode fsen,
1050                               FlatMethod        fm,
1051                               TempDescriptor    var ) {
1052     FlatNode fnContext;
1053
1054     if( fsen.getIsCallerProxySESE() ) {
1055       // attach the dynamic variable to track to
1056       // the flat method, so it can be declared at entry
1057       fnContext = fm;
1058     } else {
1059       // otherwise the code context is a task body
1060       fnContext = fsen;
1061     }
1062
1063     ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1064     if( ctn == null ) {
1065       ctn = new ContextTaskNames();
1066     }
1067
1068     ctn.addDynamicVar( var );
1069     fn2contextTaskNames.put( fnContext, ctn );
1070   }
1071
1072   private void addNeededStaticName( FlatSESEEnterNode fsen,
1073                                     FlatMethod        fm,
1074                                     SESEandAgePair    sap ) {
1075     FlatNode fnContext;
1076
1077     if( fsen.getIsCallerProxySESE() ) {
1078       // attach the dynamic variable to track to
1079       // the flat method, so it can be declared at entry
1080       fnContext = fm;
1081     } else {
1082       // otherwise the code context is a task body
1083       fnContext = fsen;
1084     }
1085
1086     ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1087     if( ctn == null ) {
1088       ctn = new ContextTaskNames();
1089     }
1090
1091     ctn.addNeededStaticName( sap );
1092
1093     fn2contextTaskNames.put( fnContext, ctn );
1094   }
1095
1096
1097   private void makeConflictGraph(FlatMethod fm) {
1098
1099     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1100     flatNodesToVisit.add(fm);
1101
1102     Set<FlatNode> visited = new HashSet<FlatNode>();
1103
1104     while (!flatNodesToVisit.isEmpty()) {
1105       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1106       flatNodesToVisit.remove(fn);
1107       visited.add(fn);
1108
1109       Set<FlatSESEEnterNode> currentSESEs =
1110         rblockRel.getPossibleExecutingRBlocks( fn );
1111
1112       conflictGraph_nodeAction(fn, currentSESEs);
1113
1114       // schedule forward nodes for analysis
1115       for (int i = 0; i < fn.numNext(); i++) {
1116         FlatNode nn = fn.getNext(i);
1117         if (!visited.contains(nn)) {
1118           flatNodesToVisit.add(nn);
1119         }
1120       }
1121
1122     }
1123
1124   }
1125
1126   private void conflictGraph_nodeAction(FlatNode fn,
1127                                         Set<FlatSESEEnterNode> currentSESEs
1128                                         ) {
1129     ConflictGraph conflictGraph;
1130     TempDescriptor lhs;
1131     TempDescriptor rhs;
1132
1133     EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1134
1135
1136     switch (fn.kind()) {
1137
1138
1139     case FKind.FlatFieldNode:
1140     case FKind.FlatElementNode: {
1141
1142       if (fn instanceof FlatFieldNode) {
1143         FlatFieldNode ffn = (FlatFieldNode) fn;
1144         rhs = ffn.getSrc();
1145       } else {
1146         FlatElementNode fen = (FlatElementNode) fn;
1147         rhs = fen.getSrc();
1148       }
1149
1150       for( Iterator<FlatSESEEnterNode> itr = currentSESEs.iterator();
1151            itr.hasNext();
1152            ) {
1153         FlatSESEEnterNode currentSESE = itr.next();
1154
1155         conflictGraph = sese2conflictGraph.get(currentSESE);
1156         if (conflictGraph == null) {
1157           conflictGraph = new ConflictGraph(state);
1158         }
1159
1160         // add stall site
1161         Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1162         conflictGraph.addStallSite(taint2Effects, rhs);
1163
1164         if (conflictGraph.id2cn.size() > 0) {
1165           sese2conflictGraph.put(currentSESE, conflictGraph);
1166         }
1167       }
1168     } break;
1169
1170
1171     case FKind.FlatSetFieldNode:
1172     case FKind.FlatSetElementNode: {
1173
1174       if (fn instanceof FlatSetFieldNode) {
1175         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1176         lhs = fsfn.getDst();
1177         rhs = fsfn.getSrc();
1178       } else {
1179         FlatSetElementNode fsen = (FlatSetElementNode) fn;
1180         lhs = fsen.getDst();
1181         rhs = fsen.getSrc();
1182       }
1183
1184       for( Iterator<FlatSESEEnterNode> itr = currentSESEs.iterator();
1185            itr.hasNext();
1186            ) {
1187         FlatSESEEnterNode currentSESE = itr.next();
1188
1189         conflictGraph = sese2conflictGraph.get(currentSESE);
1190         if (conflictGraph == null) {
1191           conflictGraph = new ConflictGraph(state);
1192         }
1193
1194         Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1195         conflictGraph.addStallSite(taint2Effects, rhs);
1196         conflictGraph.addStallSite(taint2Effects, lhs);
1197
1198         if (conflictGraph.id2cn.size() > 0) {
1199           sese2conflictGraph.put(currentSESE, conflictGraph);
1200         }
1201       }
1202     } break;
1203
1204
1205     case FKind.FlatCall: {
1206       FlatCall fc = (FlatCall) fn;
1207       lhs = fc.getThis();
1208
1209       for( Iterator<FlatSESEEnterNode> itr = currentSESEs.iterator();
1210            itr.hasNext();
1211            ) {
1212         FlatSESEEnterNode currentSESE = itr.next();
1213
1214         conflictGraph = sese2conflictGraph.get(currentSESE);
1215         if (conflictGraph == null) {
1216           conflictGraph = new ConflictGraph(state);
1217         }
1218
1219         // collects effects of stall site and generates stall site node
1220         Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1221
1222         conflictGraph.addStallSite(taint2Effects, lhs);
1223         if (conflictGraph.id2cn.size() > 0) {
1224           sese2conflictGraph.put(currentSESE, conflictGraph);
1225         }
1226       }
1227     } break;
1228
1229     }
1230   }
1231
1232
1233   private void calculateConflicts( Set<FlatNew> sitesToFlag,
1234                                    boolean      useReachInfo ) {
1235
1236     // decide fine-grain edge or coarse-grain edge among all vertexes by
1237     // pair-wise comparison
1238     Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1239     while (seseIter.hasNext()) {
1240       FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1241       ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1242
1243       if (useReachInfo) {
1244         // clear current conflict before recalculating with reachability info
1245         conflictGraph.clearAllConflictEdge();
1246         conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1247         conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1248       }
1249       conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1250       sese2conflictGraph.put(sese, conflictGraph);
1251     }
1252   }
1253
1254
1255   private void writeConflictGraph() {
1256     Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1257     while (keyEnum.hasMoreElements()) {
1258       FlatNode key = (FlatNode) keyEnum.nextElement();
1259       ConflictGraph cg = sese2conflictGraph.get(key);
1260       try {
1261         if (cg.hasConflictEdge()) {
1262           cg.writeGraph("ConflictGraphFor" + key, false);
1263         }
1264       } catch (IOException e) {
1265         System.out.println("Error writing");
1266         System.exit(0);
1267       }
1268     }
1269   }
1270
1271   private void synthesizeLocks() {
1272     Set<Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1273     for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
1274       Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator.next();
1275       FlatNode sese = graphEntry.getKey();
1276       ConflictGraph conflictGraph = graphEntry.getValue();
1277       calculateCovering(conflictGraph);
1278     }
1279   }
1280
1281   private void calculateCovering(ConflictGraph conflictGraph) {
1282     uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1283     HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1284     HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1285     HashSet<SESELock> lockSet = new HashSet<SESELock>();
1286
1287     Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1288     for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1289       ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1290       if (conflictEdge.isCoarseEdge()) {
1291         coarseToCover.add(conflictEdge);
1292       } else {
1293         fineToCover.add(conflictEdge);
1294       }
1295     }
1296
1297     HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1298     toCover.addAll(fineToCover);
1299     toCover.addAll(coarseToCover);
1300
1301     while (!toCover.isEmpty()) {
1302
1303       SESELock seseLock = new SESELock();
1304       seseLock.setID(uniqueLockSetId++);
1305
1306       boolean changed;
1307
1308       do { // fine-grained edge
1309
1310         changed = false;
1311
1312         for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
1313
1314           int type;
1315           ConflictEdge edge = (ConflictEdge) iterator.next();
1316           if (seseLock.getConflictNodeSet().size() == 0) {
1317             // initial setup
1318             if (seseLock.isWriteNode(edge.getVertexU())) {
1319               // mark as fine_write
1320               if (edge.getVertexU().isStallSiteNode()) {
1321                 type = ConflictNode.PARENT_WRITE;
1322               } else {
1323                 type = ConflictNode.FINE_WRITE;
1324               }
1325               seseLock.addConflictNode(edge.getVertexU(), type);
1326             } else {
1327               // mark as fine_read
1328               if (edge.getVertexU().isStallSiteNode()) {
1329                 type = ConflictNode.PARENT_READ;
1330               } else {
1331                 type = ConflictNode.FINE_READ;
1332               }
1333               seseLock.addConflictNode(edge.getVertexU(), type);
1334             }
1335             if (edge.getVertexV() != edge.getVertexU()) {
1336               if (seseLock.isWriteNode(edge.getVertexV())) {
1337                 // mark as fine_write
1338                 if (edge.getVertexV().isStallSiteNode()) {
1339                   type = ConflictNode.PARENT_WRITE;
1340                 } else {
1341                   type = ConflictNode.FINE_WRITE;
1342                 }
1343                 seseLock.addConflictNode(edge.getVertexV(), type);
1344               } else {
1345                 // mark as fine_read
1346                 if (edge.getVertexV().isStallSiteNode()) {
1347                   type = ConflictNode.PARENT_READ;
1348                 } else {
1349                   type = ConflictNode.FINE_READ;
1350                 }
1351                 seseLock.addConflictNode(edge.getVertexV(), type);
1352               }
1353             }
1354             changed = true;
1355             seseLock.addConflictEdge(edge);
1356             fineToCover.remove(edge);
1357             break;// exit iterator loop
1358           }// end of initial setup
1359
1360           ConflictNode newNode;
1361           if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1362             // new node has a fine-grained edge to all current node
1363             // If there is a coarse grained edge where need a fine edge, it's
1364             // okay to add the node
1365             // but the edge must remain uncovered.
1366
1367             changed = true;
1368
1369             if (seseLock.containsConflictNode(newNode)) {
1370               seseLock.addEdge(edge);
1371               fineToCover.remove(edge);
1372               break;
1373             }
1374
1375             if (seseLock.isWriteNode(newNode)) {
1376               if (newNode.isStallSiteNode()) {
1377                 type = ConflictNode.PARENT_WRITE;
1378               } else {
1379                 type = ConflictNode.FINE_WRITE;
1380               }
1381               seseLock.setNodeType(newNode, type);
1382             } else {
1383               if (newNode.isStallSiteNode()) {
1384                 type = ConflictNode.PARENT_READ;
1385               } else {
1386                 type = ConflictNode.FINE_READ;
1387               }
1388               seseLock.setNodeType(newNode, type);
1389             }
1390
1391             seseLock.addEdge(edge);
1392             Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1393             for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1394               ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1395
1396               // mark all fine edges between new node and nodes in the group as
1397               // covered
1398               if (!conflictEdge.getVertexU().equals(newNode)) {
1399                 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1400                   changed = true;
1401                   seseLock.addConflictEdge(conflictEdge);
1402                   fineToCover.remove(conflictEdge);
1403                 }
1404               } else if (!conflictEdge.getVertexV().equals(newNode)) {
1405                 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1406                   changed = true;
1407                   seseLock.addConflictEdge(conflictEdge);
1408                   fineToCover.remove(conflictEdge);
1409                 }
1410               }
1411
1412             }
1413
1414             break;// exit iterator loop
1415           }
1416         }
1417
1418       } while (changed);
1419       HashSet<ConflictEdge> notCovered=new HashSet<ConflictEdge>();
1420       do { // coarse
1421         changed = false;
1422         int type;
1423         for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
1424
1425           ConflictEdge edge = (ConflictEdge) iterator.next();
1426           if (seseLock.getConflictNodeSet().size() == 0) {
1427             // initial setup
1428             if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1429               // node has a coarse-grained edge with itself
1430               if (!(edge.getVertexU().isStallSiteNode())) {
1431                 // and it is not parent
1432                 type = ConflictNode.SCC;
1433               } else {
1434                 if(state.RCR){
1435                   type = ConflictNode.PARENT_COARSE;
1436                 }else{
1437                   type = ConflictNode.PARENT_WRITE;
1438                 }
1439               }
1440               seseLock.addConflictNode(edge.getVertexU(), type);
1441             } else {
1442               if (edge.getVertexU().isStallSiteNode()) {
1443                 if(state.RCR){
1444                   type = ConflictNode.PARENT_COARSE;
1445                 }else{
1446                   if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1447                     type = ConflictNode.PARENT_READ;
1448                   } else {
1449                     type = ConflictNode.PARENT_WRITE;
1450                   }
1451                 }
1452               } else {
1453                 type = ConflictNode.COARSE;
1454               }
1455               seseLock.addConflictNode(edge.getVertexU(), type);
1456             }
1457             if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1458               // node has a coarse-grained edge with itself
1459               if (!(edge.getVertexV().isStallSiteNode())) {
1460                 // and it is not parent
1461                 type = ConflictNode.SCC;
1462               } else {
1463                 if(state.RCR){
1464                   type = ConflictNode.PARENT_COARSE;
1465                 }else{
1466                   type = ConflictNode.PARENT_WRITE;
1467                 }
1468               }
1469               seseLock.addConflictNode(edge.getVertexV(), type);
1470             } else {
1471               if (edge.getVertexV().isStallSiteNode()) {
1472                 if(state.RCR){
1473                   type = ConflictNode.PARENT_COARSE;
1474                 }else{
1475                   if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1476                     type = ConflictNode.PARENT_READ;
1477                   } else {
1478                     type = ConflictNode.PARENT_WRITE;
1479                   }
1480                 }
1481               } else {
1482                 type = ConflictNode.COARSE;
1483               }
1484               seseLock.addConflictNode(edge.getVertexV(), type);
1485             }
1486             changed = true;
1487             coarseToCover.remove(edge);
1488             seseLock.addConflictEdge(edge);
1489             break;// exit iterator loop
1490           }// end of initial setup
1491
1492           ConflictNode newNode;
1493           if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1494             // new node has a coarse-grained edge to all fine-read, fine-write,
1495             // parent
1496             changed = true;
1497
1498             if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1499                 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1500               // this case can't be covered by this queue
1501               coarseToCover.remove(edge);
1502               notCovered.add(edge);
1503               break;
1504             }
1505
1506             if (seseLock.containsConflictNode(newNode)) {
1507               seseLock.addEdge(edge);
1508               coarseToCover.remove(edge);
1509               break;
1510             }
1511
1512             if (seseLock.hasSelfCoarseEdge(newNode)) {
1513               // SCC
1514               if (newNode.isStallSiteNode()) {
1515                 type = ConflictNode.PARENT_COARSE;
1516               } else {
1517                 type = ConflictNode.SCC;
1518               }
1519               seseLock.setNodeType(newNode, type);
1520             } else {
1521               if (newNode.isStallSiteNode()) {
1522                 type = ConflictNode.PARENT_COARSE;
1523               } else {
1524                 type = ConflictNode.COARSE;
1525               }
1526               seseLock.setNodeType(newNode, type);
1527             }
1528
1529             seseLock.addEdge(edge);
1530             Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1531             for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1532               ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1533               // mark all coarse edges between new node and nodes in the group
1534               // as covered
1535               if (!conflictEdge.getVertexU().equals(newNode)) {
1536                 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1537                   changed = true;
1538                   seseLock.addConflictEdge(conflictEdge);
1539                   coarseToCover.remove(conflictEdge);
1540                 }
1541               } else if (!conflictEdge.getVertexV().equals(newNode)) {
1542                 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1543                   changed = true;
1544                   seseLock.addConflictEdge(conflictEdge);
1545                   coarseToCover.remove(conflictEdge);
1546                 }
1547               }
1548
1549             }
1550             break;// exit iterator loop
1551           }
1552
1553         }
1554
1555       } while (changed);
1556       lockSet.add(seseLock);
1557
1558       toCover.clear();
1559       coarseToCover.addAll(notCovered);
1560       toCover.addAll(fineToCover);
1561       toCover.addAll(coarseToCover);
1562
1563     }
1564
1565     conflictGraph2SESELock.put(conflictGraph, lockSet);
1566   }
1567
1568   public ConflictGraph getConflictGraph(FlatNode sese) {
1569     return sese2conflictGraph.get(sese);
1570   }
1571
1572   public Set<SESELock> getLockMappings(ConflictGraph graph) {
1573     return conflictGraph2SESELock.get(graph);
1574   }
1575
1576   public Set<FlatSESEEnterNode> getAllSESEs() {
1577     return rblockRel.getAllSESEs();
1578   }
1579
1580   public FlatSESEEnterNode getMainSESE() {
1581     return rblockRel.getMainSESE();
1582   }
1583
1584   public FlatSESEEnterNode getCallerProxySESE() {
1585     return rblockRel.getCallerProxySESE();
1586   }
1587
1588
1589   public void writeReports(String timeReport) throws java.io.IOException {
1590
1591     BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1592     bw.write("OoOJava Analysis Results\n\n");
1593     bw.write(timeReport + "\n\n");
1594     printSESEHierarchy(bw);
1595     bw.write("\n");
1596     printSESEInfo(bw);
1597     bw.close();
1598
1599     Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1600     while (methItr.hasNext()) {
1601       MethodDescriptor md = methItr.next();
1602       FlatMethod fm = state.getMethodFlat(md);
1603       if (fm != null) {
1604         bw = new BufferedWriter(new FileWriter("ooojReport_" +
1605                                                md.getClassMethodName() +
1606                                                md.getSafeMethodDescriptor() +
1607                                                ".txt"));
1608         bw.write("OoOJava Results for " + md + "\n-------------------\n");
1609
1610         bw.write("Dynamic vars to manage:\n  " + getContextTaskNames( fm ).getDynamicVarSet() );
1611
1612         bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessGlobalView));
1613         bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1614         bw.write("\n\nNot Available Results-Out\n---------------------\n" + fm.printMethod(notAvailableResults));
1615         bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1616         bw.close();
1617       }
1618     }
1619   }
1620
1621   private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1622     bw.write("SESE Local Hierarchy\n--------------\n");
1623     Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1624     while (rootItr.hasNext()) {
1625       FlatSESEEnterNode root = rootItr.next();
1626       printSESEHierarchyTree(bw, root, 0);
1627     }
1628   }
1629
1630   private void printSESEHierarchyTree(BufferedWriter    bw,
1631                                       FlatSESEEnterNode fsen,
1632                                       int               depth
1633                                       ) throws java.io.IOException {
1634     for (int i = 0; i < depth; ++i) {
1635       bw.write("  ");
1636     }
1637     bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1638
1639     Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
1640     while (childItr.hasNext()) {
1641       FlatSESEEnterNode fsenChild = childItr.next();
1642       printSESEHierarchyTree(bw, fsenChild, depth + 1);
1643     }
1644   }
1645
1646   private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1647     bw.write("\nSESE info\n-------------\n");
1648     Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
1649     while( fsenItr.hasNext() ) {
1650       FlatSESEEnterNode fsen = fsenItr.next();
1651
1652       bw.write("SESE " + fsen.getPrettyIdentifier());
1653       if( fsen.getIsLeafSESE() ) {
1654         bw.write(" (leaf)");
1655       }
1656       bw.write(" {\n");
1657
1658       bw.write("  in-set: " + fsen.getInVarSet() + "\n");
1659       Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1660       while (tItr.hasNext()) {
1661         TempDescriptor inVar = tItr.next();
1662         if (fsen.getReadyInVarSet().contains(inVar)) {
1663           bw.write("    (ready)  " + inVar + "\n");
1664         }
1665         if (fsen.getStaticInVarSet().contains(inVar)) {
1666           bw.write("    (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1667         }
1668         if (fsen.getDynamicInVarSet().contains(inVar)) {
1669           bw.write("    (dynamic)" + inVar + "\n");
1670         }
1671       }
1672
1673       bw.write("   Dynamic vars to manage: " + getContextTaskNames( fsen ).getDynamicVarSet() + "\n");
1674
1675       bw.write("  out-set: " + fsen.getOutVarSet() + "\n");
1676
1677       bw.write("  local parent:   " + fsen.getLocalParent() + "\n");
1678       bw.write("  local children: " + fsen.getLocalChildren() + "\n");
1679
1680       bw.write("  possible parents:  " + fsen.getParents() + "\n");
1681       bw.write("  possible children: " + fsen.getChildren() + "\n");
1682
1683       bw.write("}\n");
1684     }
1685   }
1686 }