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