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