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