Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java

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