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