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