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