Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java

   1 package Analysis.OoOJava;
   2
   3 import java.io.IOException;
   4 import java.util.Enumeration;
   5 import java.util.HashSet;
   6 import java.util.Hashtable;
   7 import java.util.Iterator;
   8 import java.util.Set;
   9 import java.util.Stack;
  10 import java.util.Map.Entry;
  11
  12 import Analysis.ArrayReferencees;
  13 import Analysis.Liveness;
  14 import Analysis.CallGraph.CallGraph;
  15 import Analysis.Disjoint.DisjointAnalysis;
  16 import Analysis.Disjoint.Effect;
  17 import Analysis.Disjoint.EffectsAnalysis;
  18 import Analysis.Disjoint.Taint;
  19 import IR.Descriptor;
  20 import IR.MethodDescriptor;
  21 import IR.Operation;
  22 import IR.State;
  23 import IR.TypeUtil;
  24 import IR.Flat.FKind;
  25 import IR.Flat.FlatEdge;
  26 import IR.Flat.FlatFieldNode;
  27 import IR.Flat.FlatMethod;
  28 import IR.Flat.FlatNode;
  29 import IR.Flat.FlatOpNode;
  30 import IR.Flat.FlatSESEEnterNode;
  31 import IR.Flat.FlatSESEExitNode;
  32 import IR.Flat.FlatSetFieldNode;
  33 import IR.Flat.FlatWriteDynamicVarNode;
  34 import IR.Flat.TempDescriptor;
  35
  36 public class OoOJavaAnalysis {
  37
  38   // data from the compiler
  39   private State state;
  40   private TypeUtil typeUtil;
  41   private CallGraph callGraph;
  42   private RBlockRelationAnalysis rblockRel;
  43   private RBlockStatusAnalysis rblockStatus;
  44   private DisjointAnalysis disjointAnalysisTaints;
  45   private DisjointAnalysis disjointAnalysisReach;
  46
  47   private Hashtable<FlatNode, Set<TempDescriptor>> livenessRootView;
  48   private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
  49   private Hashtable<FlatNode, VarSrcTokTable> variableResults;
  50   private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
  51   private Hashtable<FlatNode, CodePlan> codePlans;
  52
  53   private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
  54
  55   private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
  56
  57   // temporal data structures to track analysis progress.
  58   static private int uniqueLockSetId = 0;
  59   // mapping of a conflict graph to its compiled lock
  60   private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
  61   // mapping of a sese block to its conflict graph
  62   private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
  63
  64
  65
  66
  67   // private Hashtable<FlatNode, ParentChildConflictsMap> conflictsResults;
  68   // private Hashtable<FlatMethod, MethodSummary> methodSummaryResults;
  69   // private OwnershipAnalysis ownAnalysisForSESEConflicts;
  70
  71   // static private int uniqueLockSetId = 0;
  72
  73   public static int maxSESEage = -1;
  74
  75   public int getMaxSESEage() {
  76     return maxSESEage;
  77   }
  78
  79   // may be null
  80   public CodePlan getCodePlan(FlatNode fn) {
  81     CodePlan cp = codePlans.get(fn);
  82     return cp;
  83   }
  84
  85   public OoOJavaAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, Liveness liveness,
  86       ArrayReferencees arrayReferencees) {
  87
  88     double timeStartAnalysis = (double) System.nanoTime();
  89
  90     this.state = state;
  91     this.typeUtil = typeUtil;
  92     this.callGraph = callGraph;
  93     this.maxSESEage = state.MLP_MAXSESEAGE;
  94
  95     livenessRootView = new Hashtable<FlatNode, Set<TempDescriptor>>();
  96     livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
  97     variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
  98     notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
  99     codePlans = new Hashtable<FlatNode, CodePlan>();
 100     wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
 101
 102     notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
 103
 104     sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
 105     conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
 106
 107     // add all methods transitively reachable from the
 108     // source's main to set for analysis
 109     MethodDescriptor mdSourceEntry = typeUtil.getMain();
 110     FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
 111
 112     Set<MethodDescriptor> descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
 113
 114     descriptorsToAnalyze.add(mdSourceEntry);
 115
 116     // conflictsResults = new Hashtable<FlatNode, ParentChildConflictsMap>();
 117     // methodSummaryResults = new Hashtable<FlatMethod, MethodSummary>();
 118     // conflictGraphResults = new Hashtable<FlatNode, ConflictGraph>();
 119
 120     // seseSummaryMap = new Hashtable<FlatNode, SESESummary>();
 121     // isAfterChildSESEIndicatorMap = new Hashtable<FlatNode, Boolean>();
 122     // conflictGraphLockMap = new Hashtable<ConflictGraph, HashSet<SESELock>>();
 123
 124     // 1st pass, find basic rblock relations
 125     rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
 126
 127     rblockStatus = new RBlockStatusAnalysis(state, typeUtil, callGraph, rblockRel);
 128
 129
 130     // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
 131     Iterator<FlatSESEEnterNode> rootItr = rblockRel.getRootSESEs().iterator();
 132     while (rootItr.hasNext()) {
 133       FlatSESEEnterNode root = rootItr.next();
 134       livenessAnalysisBackward(root, true, null);
 135     }
 136
 137     // 3rd pass, variable analysis
 138     Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
 139     while (methItr.hasNext()) {
 140       Descriptor d = methItr.next();
 141       FlatMethod fm = state.getMethodFlat(d);
 142
 143       // starting from roots do a forward, fixed-point
 144       // variable analysis for refinement and stalls
 145       variableAnalysisForward(fm);
 146     }
 147
 148     // 4th pass, compute liveness contribution from
 149     // virtual reads discovered in variable pass
 150     rootItr = rblockRel.getRootSESEs().iterator();
 151     while (rootItr.hasNext()) {
 152       FlatSESEEnterNode root = rootItr.next();
 153       livenessAnalysisBackward(root, true, null);
 154     }
 155
 156     // 5th pass, use disjointness with NO FLAGGED REGIONS
 157     // to compute taints and effects
 158     disjointAnalysisTaints = new DisjointAnalysis(state, typeUtil, callGraph, liveness,
 159         arrayReferencees, rblockRel, rblockStatus);
 160
 161     // 6th pass, not available analysis FOR VARIABLES!
 162     methItr = descriptorsToAnalyze.iterator();
 163     while (methItr.hasNext()) {
 164       Descriptor d = methItr.next();
 165       FlatMethod fm = state.getMethodFlat(d);
 166
 167       // compute what is not available at every program
 168       // point, in a forward fixed-point pass
 169       notAvailableForward(fm);
 170     }
 171
 172     /*
 173     // #th pass,  make conflict graph
 174     // conflict graph is maintained by each parent sese
 175     methItr = descriptorsToAnalyze.iterator();
 176     while (methItr.hasNext()) {
 177       Descriptor d = methItr.next();
 178       FlatMethod fm = state.getMethodFlat(d);
 179       makeConflictGraph(fm);
 180     }
 181
 182     // debug routine
 183     Iterator iter = sese2conflictGraph.entrySet().iterator();
 184     while (iter.hasNext()) {
 185       Entry e = (Entry) iter.next();
 186       FlatNode fn = (FlatNode) e.getKey();
 187       ConflictGraph conflictGraph = (ConflictGraph) e.getValue();
 188       System.out.println("CONFLICT GRAPH for " + fn);
 189       Set<String> keySet = conflictGraph.id2cn.keySet();
 190       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 191         String key = (String) iterator.next();
 192         ConflictNode node = conflictGraph.id2cn.get(key);
 193         System.out.println("key=" + key + " --\n" + node.toString());
 194       }
 195     }
 196
 197     // #th pass, calculate conflicts
 198     calculateConflicts();
 199
 200     // #th pass, compiling locks
 201     synthesizeLocks();
 202
 203     // #th pass, writing conflict graph
 204     writeConflictGraph();
 205     */
 206
 207   }
 208
 209   private void livenessAnalysisBackward(FlatSESEEnterNode fsen, boolean toplevel,
 210       Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
 211
 212     // start from an SESE exit, visit nodes in reverse up to
 213     // SESE enter in a fixed-point scheme, where children SESEs
 214     // should already be analyzed and therefore can be skipped
 215     // because child SESE enter node has all necessary info
 216     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 217
 218     if (toplevel) {
 219       flatNodesToVisit.add(fsen.getfmEnclosing().getFlatExit());
 220     } else {
 221       flatNodesToVisit.add(fsen.getFlatExit());
 222     }
 223
 224     Hashtable<FlatNode, Set<TempDescriptor>> livenessResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
 225
 226     if (toplevel) {
 227       liveout = new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
 228     }
 229
 230     while (!flatNodesToVisit.isEmpty()) {
 231       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 232       flatNodesToVisit.remove(fn);
 233
 234       Set<TempDescriptor> prev = livenessResults.get(fn);
 235
 236       // merge sets from control flow joins
 237       Set<TempDescriptor> u = new HashSet<TempDescriptor>();
 238       for (int i = 0; i < fn.numNext(); i++) {
 239         FlatNode nn = fn.getNext(i);
 240         Set<TempDescriptor> s = livenessResults.get(nn);
 241         if (s != null) {
 242           u.addAll(s);
 243         }
 244       }
 245
 246       Set<TempDescriptor> curr = liveness_nodeActions(fn, u, fsen, toplevel, liveout);
 247
 248       // if a new result, schedule backward nodes for analysis
 249       if (!curr.equals(prev)) {
 250         livenessResults.put(fn, curr);
 251
 252         // don't flow backwards past current SESE enter
 253         if (!fn.equals(fsen)) {
 254           for (int i = 0; i < fn.numPrev(); i++) {
 255             FlatNode nn = fn.getPrev(i);
 256             flatNodesToVisit.add(nn);
 257           }
 258         }
 259       }
 260     }
 261
 262     Set<TempDescriptor> s = livenessResults.get(fsen);
 263     if (s != null) {
 264       fsen.addInVarSet(s);
 265     }
 266
 267     // remember liveness per node from the root view as the
 268     // global liveness of variables for later passes to use
 269     if (toplevel) {
 270       livenessRootView.putAll(livenessResults);
 271     }
 272
 273     // post-order traversal, so do children first
 274     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 275     while (childItr.hasNext()) {
 276       FlatSESEEnterNode fsenChild = childItr.next();
 277       livenessAnalysisBackward(fsenChild, false, liveout);
 278     }
 279   }
 280
 281   private Set<TempDescriptor> liveness_nodeActions(FlatNode fn, Set<TempDescriptor> liveIn,
 282       FlatSESEEnterNode currentSESE, boolean toplevel,
 283       Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
 284     switch (fn.kind()) {
 285
 286     case FKind.FlatSESEExitNode:
 287       if (toplevel) {
 288         FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 289         if (!liveout.containsKey(fsexn)) {
 290           liveout.put(fsexn, new HashSet<TempDescriptor>());
 291         }
 292         liveout.get(fsexn).addAll(liveIn);
 293       }
 294       // no break, sese exits should also execute default actions
 295
 296     default: {
 297       // handle effects of statement in reverse, writes then reads
 298       TempDescriptor[] writeTemps = fn.writesTemps();
 299       for (int i = 0; i < writeTemps.length; ++i) {
 300         liveIn.remove(writeTemps[i]);
 301
 302         if (!toplevel) {
 303           FlatSESEExitNode fsexn = currentSESE.getFlatExit();
 304           Set<TempDescriptor> livetemps = liveout.get(fsexn);
 305           if (livetemps != null && livetemps.contains(writeTemps[i])) {
 306             // write to a live out temp...
 307             // need to put in SESE liveout set
 308             currentSESE.addOutVar(writeTemps[i]);
 309           }
 310         }
 311       }
 312
 313       TempDescriptor[] readTemps = fn.readsTemps();
 314       for (int i = 0; i < readTemps.length; ++i) {
 315         liveIn.add(readTemps[i]);
 316       }
 317
 318       Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get(fn);
 319       if (virtualReadTemps != null) {
 320         liveIn.addAll(virtualReadTemps);
 321       }
 322
 323     }
 324       break;
 325
 326     } // end switch
 327
 328     return liveIn;
 329   }
 330
 331   private void variableAnalysisForward(FlatMethod fm) {
 332
 333     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 334     flatNodesToVisit.add(fm);
 335
 336     while (!flatNodesToVisit.isEmpty()) {
 337       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 338       flatNodesToVisit.remove(fn);
 339
 340       Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
 341       assert seseStack != null;
 342
 343       VarSrcTokTable prev = variableResults.get(fn);
 344
 345       // merge sets from control flow joins
 346       VarSrcTokTable curr = new VarSrcTokTable();
 347       for (int i = 0; i < fn.numPrev(); i++) {
 348         FlatNode nn = fn.getPrev(i);
 349         VarSrcTokTable incoming = variableResults.get(nn);
 350         curr.merge(incoming);
 351       }
 352
 353       if (!seseStack.empty()) {
 354         variable_nodeActions(fn, curr, seseStack.peek());
 355       }
 356
 357       // if a new result, schedule forward nodes for analysis
 358       if (!curr.equals(prev)) {
 359         variableResults.put(fn, curr);
 360
 361         for (int i = 0; i < fn.numNext(); i++) {
 362           FlatNode nn = fn.getNext(i);
 363           flatNodesToVisit.add(nn);
 364         }
 365       }
 366     }
 367   }
 368
 369   private void variable_nodeActions(FlatNode fn, VarSrcTokTable vstTable,
 370       FlatSESEEnterNode currentSESE) {
 371     switch (fn.kind()) {
 372
 373     case FKind.FlatSESEEnterNode: {
 374       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 375       assert fsen.equals(currentSESE);
 376
 377       vstTable.age(currentSESE);
 378       vstTable.assertConsistency();
 379     }
 380       break;
 381
 382     case FKind.FlatSESEExitNode: {
 383       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 384       FlatSESEEnterNode fsen = fsexn.getFlatEnter();
 385       assert currentSESE.getChildren().contains(fsen);
 386
 387       // remap all of this child's children tokens to be
 388       // from this child as the child exits
 389       vstTable.remapChildTokens(fsen);
 390
 391       // liveness virtual reads are things that might be
 392       // written by an SESE and should be added to the in-set
 393       // anything virtually read by this SESE should be pruned
 394       // of parent or sibling sources
 395       Set<TempDescriptor> liveVars = livenessRootView.get(fn);
 396       Set<TempDescriptor> fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(
 397           fsen, liveVars);
 398       Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
 399       if (fsenVirtReadsOld != null) {
 400         fsenVirtReads.addAll(fsenVirtReadsOld);
 401       }
 402       livenessVirtualReads.put(fn, fsenVirtReads);
 403
 404       // then all child out-set tokens are guaranteed
 405       // to be filled in, so clobber those entries with
 406       // the latest, clean sources
 407       Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
 408       while (outVarItr.hasNext()) {
 409         TempDescriptor outVar = outVarItr.next();
 410         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 411         ts.add(outVar);
 412         VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
 413         vstTable.remove(outVar);
 414         vstTable.add(vst);
 415       }
 416       vstTable.assertConsistency();
 417
 418     }
 419       break;
 420
 421     case FKind.FlatOpNode: {
 422       FlatOpNode fon = (FlatOpNode) fn;
 423
 424       if (fon.getOp().getOp() == Operation.ASSIGN) {
 425         TempDescriptor lhs = fon.getDest();
 426         TempDescriptor rhs = fon.getLeft();
 427
 428         vstTable.remove(lhs);
 429
 430         Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
 431
 432         Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
 433         while (itr.hasNext()) {
 434           VariableSourceToken vst = itr.next();
 435
 436           HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 437           ts.add(lhs);
 438
 439           if (currentSESE.getChildren().contains(vst.getSESE())) {
 440             // if the source comes from a child, copy it over
 441             forAddition.add(new VariableSourceToken(ts, vst.getSESE(), vst.getAge(), vst
 442                 .getAddrVar()));
 443           } else {
 444             // otherwise, stamp it as us as the source
 445             forAddition.add(new VariableSourceToken(ts, currentSESE, new Integer(0), lhs));
 446           }
 447         }
 448
 449         vstTable.addAll(forAddition);
 450
 451         // only break if this is an ASSIGN op node,
 452         // otherwise fall through to default case
 453         vstTable.assertConsistency();
 454         break;
 455       }
 456     }
 457
 458       // note that FlatOpNode's that aren't ASSIGN
 459       // fall through to this default case
 460     default: {
 461       TempDescriptor[] writeTemps = fn.writesTemps();
 462       if (writeTemps.length > 0) {
 463
 464         // for now, when writeTemps > 1, make sure
 465         // its a call node, programmer enforce only
 466         // doing stuff like calling a print routine
 467         // assert writeTemps.length == 1;
 468         if (writeTemps.length > 1) {
 469           assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
 470           break;
 471         }
 472
 473         vstTable.remove(writeTemps[0]);
 474
 475         HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
 476         ts.add(writeTemps[0]);
 477
 478         vstTable.add(new VariableSourceToken(ts, currentSESE, new Integer(0), writeTemps[0]));
 479       }
 480
 481       vstTable.assertConsistency();
 482     }
 483       break;
 484
 485     } // end switch
 486   }
 487
 488   private void notAvailableForward(FlatMethod fm) {
 489
 490     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 491     flatNodesToVisit.add(fm);
 492
 493     while (!flatNodesToVisit.isEmpty()) {
 494       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 495       flatNodesToVisit.remove(fn);
 496
 497       Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
 498       assert seseStack != null;
 499
 500       Set<TempDescriptor> prev = notAvailableResults.get(fn);
 501
 502       Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
 503       for (int i = 0; i < fn.numPrev(); i++) {
 504         FlatNode nn = fn.getPrev(i);
 505         Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
 506         if (notAvailIn != null) {
 507           curr.addAll(notAvailIn);
 508         }
 509       }
 510
 511       if (!seseStack.empty()) {
 512         notAvailable_nodeActions(fn, curr, seseStack.peek());
 513       }
 514
 515       // if a new result, schedule forward nodes for analysis
 516       if (!curr.equals(prev)) {
 517         notAvailableResults.put(fn, curr);
 518
 519         for (int i = 0; i < fn.numNext(); i++) {
 520           FlatNode nn = fn.getNext(i);
 521           flatNodesToVisit.add(nn);
 522         }
 523       }
 524     }
 525   }
 526
 527   private void notAvailable_nodeActions(FlatNode fn, Set<TempDescriptor> notAvailSet,
 528       FlatSESEEnterNode currentSESE) {
 529
 530     // any temps that are removed from the not available set
 531     // at this node should be marked in this node's code plan
 532     // as temps to be grabbed at runtime!
 533
 534     switch (fn.kind()) {
 535
 536     case FKind.FlatSESEEnterNode: {
 537       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 538       assert fsen.equals(currentSESE);
 539
 540       // keep a copy of what's not available into the SESE
 541       // and restore it at the matching exit node
 542       Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
 543       Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
 544       while (tdItr.hasNext()) {
 545         notAvailCopy.add(tdItr.next());
 546       }
 547       notAvailableIntoSESE.put(fsen, notAvailCopy);
 548
 549       notAvailSet.clear();
 550     }
 551       break;
 552
 553     case FKind.FlatSESEExitNode: {
 554       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 555       FlatSESEEnterNode fsen = fsexn.getFlatEnter();
 556       assert currentSESE.getChildren().contains(fsen);
 557
 558       notAvailSet.addAll(fsen.getOutVarSet());
 559
 560       Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
 561       assert notAvailIn != null;
 562       notAvailSet.addAll(notAvailIn);
 563
 564     }
 565       break;
 566
 567     case FKind.FlatMethod: {
 568       notAvailSet.clear();
 569     }
 570
 571     case FKind.FlatOpNode: {
 572       FlatOpNode fon = (FlatOpNode) fn;
 573
 574       if (fon.getOp().getOp() == Operation.ASSIGN) {
 575         TempDescriptor lhs = fon.getDest();
 576         TempDescriptor rhs = fon.getLeft();
 577
 578         // copy makes lhs same availability as rhs
 579         if (notAvailSet.contains(rhs)) {
 580           notAvailSet.add(lhs);
 581         } else {
 582           notAvailSet.remove(lhs);
 583         }
 584
 585         // only break if this is an ASSIGN op node,
 586         // otherwise fall through to default case
 587         break;
 588       }
 589     }
 590
 591       // note that FlatOpNode's that aren't ASSIGN
 592       // fall through to this default case
 593     default: {
 594       TempDescriptor[] writeTemps = fn.writesTemps();
 595       for (int i = 0; i < writeTemps.length; i++) {
 596         TempDescriptor wTemp = writeTemps[i];
 597         notAvailSet.remove(wTemp);
 598       }
 599       TempDescriptor[] readTemps = fn.readsTemps();
 600       for (int i = 0; i < readTemps.length; i++) {
 601         TempDescriptor rTemp = readTemps[i];
 602         notAvailSet.remove(rTemp);
 603
 604         // if this variable has exactly one source, potentially
 605         // get other things from this source as well
 606         VarSrcTokTable vstTable = variableResults.get(fn);
 607
 608         VSTWrapper vstIfStatic = new VSTWrapper();
 609         Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
 610
 611         if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
 612
 613           VariableSourceToken vst = vstIfStatic.vst;
 614
 615           Iterator<VariableSourceToken> availItr = vstTable.get(vst.getSESE(), vst.getAge())
 616               .iterator();
 617
 618           // look through things that are also available from same source
 619           while (availItr.hasNext()) {
 620             VariableSourceToken vstAlsoAvail = availItr.next();
 621
 622             Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
 623             while (refVarItr.hasNext()) {
 624               TempDescriptor refVarAlso = refVarItr.next();
 625
 626               // if a variable is available from the same source, AND it ALSO
 627               // only comes from one statically known source, mark it available
 628               VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
 629               Integer srcTypeAlso = vstTable.getRefVarSrcType(refVarAlso, currentSESE,
 630                   vstIfStaticNotUsed);
 631               if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
 632                 notAvailSet.remove(refVarAlso);
 633               }
 634             }
 635           }
 636         }
 637       }
 638     }
 639       break;
 640
 641     } // end switch
 642   }
 643
 644   private void makeConflictGraph(FlatMethod fm) {
 645
 646     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 647     flatNodesToVisit.add(fm);
 648
 649     Set<FlatNode> visited = new HashSet<FlatNode>();
 650
 651     while (!flatNodesToVisit.isEmpty()) {
 652       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 653       flatNodesToVisit.remove(fn);
 654       visited.add(fn);
 655
 656       Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
 657       assert seseStack != null;
 658
 659       if (!seseStack.isEmpty()) {
 660
 661         // Add Stall Node of current program statement
 662         // disjointAnalysisTaints.getEffectsAnalysis().getEffects(t);
 663
 664         ConflictGraph conflictGraph = sese2conflictGraph.get(seseStack.peek());
 665         if (conflictGraph == null) {
 666           conflictGraph = new ConflictGraph();
 667         }
 668
 669         conflictGraph_nodeAction(fn, seseStack.peek());
 670
 671       }
 672
 673       // schedule forward nodes for analysis
 674       for (int i = 0; i < fn.numNext(); i++) {
 675         FlatNode nn = fn.getNext(i);
 676         if (!visited.contains(nn)) {
 677           flatNodesToVisit.add(nn);
 678         }
 679       }
 680
 681     }
 682
 683   }
 684
 685
 686   private void conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE) {
 687
 688     EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
 689     ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE.getParent());
 690     if (conflictGraph == null) {
 691       conflictGraph = new ConflictGraph();
 692     }
 693
 694     switch (fn.kind()) {
 695
 696     case FKind.FlatSESEEnterNode: {
 697
 698       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 699
 700       if (!fsen.getIsCallerSESEplaceholder() && currentSESE.getParent() != null) {
 701         // collects effects set of invar set and generates invar node
 702         Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.getSESEEffects(currentSESE);
 703         conflictGraph.addLiveIn(taint2Effects);
 704       }
 705     }
 706       break;
 707
 708     case FKind.FlatFieldNode:
 709     case FKind.FlatElementNode: {
 710
 711       FlatFieldNode ffn = (FlatFieldNode) fn;
 712       TempDescriptor rhs = ffn.getSrc();
 713
 714       // add stall site
 715       Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.getStallSiteEffects(fn, rhs);
 716       conflictGraph.addStallSite(taint2Effects);
 717
 718     }
 719       break;
 720
 721     case FKind.FlatSetFieldNode:
 722     case FKind.FlatSetElementNode: {
 723
 724       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 725       TempDescriptor lhs = fsfn.getDst();
 726       TempDescriptor rhs = fsfn.getSrc();
 727
 728       // collects effects of stall site and generates stall site node
 729       Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.getStallSiteEffects(fn, rhs);
 730       conflictGraph.addStallSite(taint2Effects);
 731
 732       taint2Effects=effectsAnalysis.getStallSiteEffects(fn, lhs);
 733       conflictGraph.addStallSite(taint2Effects);
 734
 735     }
 736       break;
 737     }
 738
 739     if (conflictGraph.id2cn.size() > 0) {
 740       sese2conflictGraph.put(currentSESE.getParent(), conflictGraph);
 741     }
 742
 743   }
 744
 745   private void calculateConflicts() {
 746     // decide fine-grain edge or coarse-grain edge among all vertexes by
 747     // pair-wise comparison
 748
 749     Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
 750     while (seseIter.hasNext()) {
 751       FlatNode sese = seseIter.next();
 752       ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
 753       conflictGraph.analyzeConflicts();
 754       sese2conflictGraph.put(sese, conflictGraph);
 755     }
 756   }
 757
 758   private void writeConflictGraph() {
 759     Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
 760     while (keyEnum.hasMoreElements()) {
 761       FlatNode key = (FlatNode) keyEnum.nextElement();
 762       ConflictGraph cg = sese2conflictGraph.get(key);
 763       try {
 764         if (cg.hasConflictEdge()) {
 765           cg.writeGraph("ConflictGraphFor" + key, false);
 766         }
 767       } catch (IOException e) {
 768         System.out.println("Error writing");
 769         System.exit(0);
 770       }
 771     }
 772   }
 773
 774   private void synthesizeLocks() {
 775     Set<Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
 776     for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
 777       Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator.next();
 778       FlatNode sese = graphEntry.getKey();
 779       ConflictGraph conflictGraph = graphEntry.getValue();
 780       calculateCovering(conflictGraph);
 781     }
 782   }
 783
 784   private void calculateCovering(ConflictGraph conflictGraph) {
 785     uniqueLockSetId = 0; // reset lock counter for every new conflict graph
 786     HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
 787     HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
 788     HashSet<SESELock> lockSet = new HashSet<SESELock>();
 789
 790     Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
 791     for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
 792       ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
 793       if (conflictEdge.isCoarseEdge()) {
 794         coarseToCover.add(conflictEdge);
 795       } else {
 796         fineToCover.add(conflictEdge);
 797       }
 798     }
 799
 800     HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
 801     toCover.addAll(fineToCover);
 802     toCover.addAll(coarseToCover);
 803
 804     while (!toCover.isEmpty()) {
 805
 806       SESELock seseLock = new SESELock();
 807       seseLock.setID(uniqueLockSetId++);
 808
 809       boolean changed;
 810
 811       do { // fine-grained edge
 812
 813         changed = false;
 814
 815         for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
 816
 817           int type;
 818           ConflictEdge edge = (ConflictEdge) iterator.next();
 819           if (seseLock.getConflictNodeSet().size() == 0) {
 820             // initial setup
 821             if (seseLock.isWriteNode(edge.getVertexU())) {
 822               // mark as fine_write
 823               if (edge.getVertexU().isStallSiteNode()) {
 824                 type = ConflictNode.PARENT_WRITE;
 825               } else {
 826                 type = ConflictNode.FINE_WRITE;
 827               }
 828               seseLock.addConflictNode(edge.getVertexU(), type);
 829             } else {
 830               // mark as fine_read
 831               if (edge.getVertexU().isStallSiteNode()) {
 832                 type = ConflictNode.PARENT_READ;
 833               } else {
 834                 type = ConflictNode.FINE_READ;
 835               }
 836               seseLock.addConflictNode(edge.getVertexU(), type);
 837             }
 838             if (edge.getVertexV() != edge.getVertexU()) {
 839               if (seseLock.isWriteNode(edge.getVertexV())) {
 840                 // mark as fine_write
 841                 if (edge.getVertexV().isStallSiteNode()) {
 842                   type = ConflictNode.PARENT_WRITE;
 843                 } else {
 844                   type = ConflictNode.FINE_WRITE;
 845                 }
 846                 seseLock.addConflictNode(edge.getVertexV(), type);
 847               } else {
 848                 // mark as fine_read
 849                 if (edge.getVertexV().isStallSiteNode()) {
 850                   type = ConflictNode.PARENT_READ;
 851                 } else {
 852                   type = ConflictNode.FINE_READ;
 853                 }
 854                 seseLock.addConflictNode(edge.getVertexV(), type);
 855               }
 856             }
 857             changed = true;
 858             seseLock.addConflictEdge(edge);
 859             fineToCover.remove(edge);
 860             break;// exit iterator loop
 861           }// end of initial setup
 862
 863           ConflictNode newNode;
 864           if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
 865             // new node has a fine-grained edge to all current node
 866             // If there is a coarse grained edge where need a fine edge, it's
 867             // okay to add the node
 868             // but the edge must remain uncovered.
 869
 870             changed = true;
 871
 872             if (seseLock.isWriteNode(newNode)) {
 873               if (newNode.isStallSiteNode()) {
 874                 type = ConflictNode.PARENT_WRITE;
 875               } else {
 876                 type = ConflictNode.FINE_WRITE;
 877               }
 878               seseLock.setNodeType(newNode, type);
 879             } else {
 880               if (newNode.isStallSiteNode()) {
 881                 type = ConflictNode.PARENT_READ;
 882               } else {
 883                 type = ConflictNode.FINE_READ;
 884               }
 885               seseLock.setNodeType(newNode, type);
 886             }
 887
 888             seseLock.addEdge(edge);
 889             Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
 890             for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
 891               ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
 892
 893               // mark all fine edges between new node and nodes in the group as
 894               // covered
 895               if (!conflictEdge.getVertexU().equals(newNode)) {
 896                 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
 897                   changed = true;
 898                   seseLock.addConflictEdge(conflictEdge);
 899                   fineToCover.remove(conflictEdge);
 900                 }
 901               } else if (!conflictEdge.getVertexV().equals(newNode)) {
 902                 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
 903                   changed = true;
 904                   seseLock.addConflictEdge(conflictEdge);
 905                   fineToCover.remove(conflictEdge);
 906                 }
 907               }
 908
 909             }
 910
 911             break;// exit iterator loop
 912           }
 913         }
 914
 915       } while (changed);
 916       do { // coarse
 917         changed = false;
 918         int type;
 919         for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
 920
 921           ConflictEdge edge = (ConflictEdge) iterator.next();
 922
 923           if (seseLock.getConflictNodeSet().size() == 0) {
 924             // initial setup
 925             if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
 926               // node has a coarse-grained edge with itself
 927               if (!(edge.getVertexU().isStallSiteNode())) {
 928                 // and it is not parent
 929                 type = ConflictNode.SCC;
 930               } else {
 931                 type = ConflictNode.PARENT_COARSE;
 932               }
 933               seseLock.addConflictNode(edge.getVertexU(), type);
 934             } else {
 935               if (edge.getVertexU().isStallSiteNode()) {
 936                 type = ConflictNode.PARENT_COARSE;
 937               } else {
 938                 type = ConflictNode.COARSE;
 939               }
 940               seseLock.addConflictNode(edge.getVertexU(), type);
 941             }
 942             if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
 943               // node has a coarse-grained edge with itself
 944               if (!(edge.getVertexV().isStallSiteNode())) {
 945                 // and it is not parent
 946                 type = ConflictNode.SCC;
 947               } else {
 948                 type = ConflictNode.PARENT_COARSE;
 949               }
 950               seseLock.addConflictNode(edge.getVertexV(), type);
 951             } else {
 952               if (edge.getVertexV().isStallSiteNode()) {
 953                 type = ConflictNode.PARENT_COARSE;
 954               } else {
 955                 type = ConflictNode.COARSE;
 956               }
 957               seseLock.addConflictNode(edge.getVertexV(), type);
 958             }
 959             changed = true;
 960             coarseToCover.remove(edge);
 961             seseLock.addConflictEdge(edge);
 962             break;// exit iterator loop
 963           }// end of initial setup
 964
 965           ConflictNode newNode;
 966           if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
 967             // new node has a coarse-grained edge to all fine-read, fine-write,
 968             // parent
 969             changed = true;
 970
 971             if (seseLock.hasSelfCoarseEdge(newNode)) {
 972               // SCC
 973               if (newNode.isStallSiteNode()) {
 974                 type = ConflictNode.PARENT_COARSE;
 975               } else {
 976                 type = ConflictNode.SCC;
 977               }
 978               seseLock.setNodeType(newNode, type);
 979             } else {
 980               if (newNode.isStallSiteNode()) {
 981                 type = ConflictNode.PARENT_COARSE;
 982               } else {
 983                 type = ConflictNode.COARSE;
 984               }
 985               seseLock.setNodeType(newNode, type);
 986             }
 987
 988             seseLock.addEdge(edge);
 989             Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
 990             for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
 991               ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
 992               // mark all coarse edges between new node and nodes in the group
 993               // as covered
 994               if (!conflictEdge.getVertexU().equals(newNode)) {
 995                 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
 996                   changed = true;
 997                   seseLock.addConflictEdge(conflictEdge);
 998                   coarseToCover.remove(conflictEdge);
 999                 }
1000               } else if (!conflictEdge.getVertexV().equals(newNode)) {
1001                 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1002                   changed = true;
1003                   seseLock.addConflictEdge(conflictEdge);
1004                   coarseToCover.remove(conflictEdge);
1005                 }
1006               }
1007
1008             }
1009             break;// exit iterator loop
1010           }
1011
1012         }
1013
1014       } while (changed);
1015       lockSet.add(seseLock);
1016
1017       toCover.clear();
1018       toCover.addAll(fineToCover);
1019       toCover.addAll(coarseToCover);
1020
1021     }
1022
1023     conflictGraph2SESELock.put(conflictGraph, lockSet);
1024   }
1025
1026 }