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