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