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