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