Robust/src/Analysis/OoOJava/ConflictGraph.java

   1 package Analysis.OoOJava;
   2
   3 import java.io.BufferedWriter;
   4 import java.io.FileWriter;
   5 import java.util.Collection;
   6 import java.util.HashMap;
   7 import java.util.HashSet;
   8 import java.util.Hashtable;
   9 import java.util.Iterator;
  10 import java.util.Map;
  11 import java.util.Set;
  12 import java.util.Map.Entry;
  13 import IR.State;
  14
  15 import Analysis.Disjoint.AllocSite;
  16 import Analysis.Disjoint.DisjointAnalysis;
  17 import Analysis.Disjoint.Effect;
  18 import Analysis.Disjoint.Taint;
  19 import IR.Flat.FlatMethod;
  20 import IR.Flat.FlatNew;
  21 import IR.Flat.FlatNode;
  22 import IR.Flat.FlatSESEEnterNode;
  23 import IR.Flat.TempDescriptor;
  24
  25 public class ConflictGraph {
  26
  27   protected Hashtable<String, ConflictNode> id2cn;
  28   protected Hashtable<FlatNode, Hashtable<Taint, Set<Effect>>> sese2te;
  29
  30   protected DisjointAnalysis da;
  31   protected FlatMethod fmEnclosing;
  32
  33   public static final int NON_WRITE_CONFLICT = 0;
  34   public static final int FINE_GRAIN_EDGE = 1;
  35   public static final int COARSE_GRAIN_EDGE = 2;
  36
  37   State state;
  38
  39   public ConflictGraph(State state) {
  40     this.state=state;
  41     id2cn = new Hashtable<String, ConflictNode>();
  42     sese2te = new Hashtable<FlatNode, Hashtable<Taint, Set<Effect>>>();
  43   }
  44
  45   public void setDisJointAnalysis(DisjointAnalysis da) {
  46     this.da = da;
  47   }
  48
  49   public void setFMEnclosing(FlatMethod fmEnclosing) {
  50     this.fmEnclosing = fmEnclosing;
  51   }
  52
  53   public void addLiveIn(Hashtable<Taint, Set<Effect>> taint2Effects) {
  54     if (taint2Effects == null) {
  55       return;
  56     }
  57     Iterator entryIter = taint2Effects.entrySet().iterator();
  58     while (entryIter.hasNext()) {
  59       Entry entry = (Entry) entryIter.next();
  60       Taint taint = (Taint) entry.getKey();
  61       Set<Effect> effectSet = (Set<Effect>) entry.getValue();
  62       if (!effectSet.isEmpty()) {
  63         Iterator<Effect> effectIter = effectSet.iterator();
  64         while (effectIter.hasNext()) {
  65           Effect effect = (Effect) effectIter.next();
  66           addLiveInNodeEffect(taint, effect);
  67         }
  68       }
  69     }
  70   }
  71
  72   public void addStallSite(Hashtable<Taint, Set<Effect>> taint2Effects, TempDescriptor var) {
  73     if (taint2Effects == null) {
  74       return;
  75     }
  76     Iterator entryIter = taint2Effects.entrySet().iterator();
  77     while (entryIter.hasNext()) {
  78       Entry entry = (Entry) entryIter.next();
  79       Taint taint = (Taint) entry.getKey();
  80       Set<Effect> effectSet = (Set<Effect>) entry.getValue();
  81       if (!effectSet.isEmpty()) {
  82         Iterator<Effect> effectIter = effectSet.iterator();
  83         while (effectIter.hasNext()) {
  84           Effect effect = (Effect) effectIter.next();
  85           if (taint.getVar().equals(var)) {
  86             addStallSiteEffect(taint, effect);
  87           }
  88         }
  89       }
  90     }
  91   }
  92
  93   public void addStallSiteEffect(Taint t, Effect e) {
  94     FlatNode fn = t.getStallSite();
  95     TempDescriptor var = t.getVar();
  96     AllocSite as = t.getAllocSite();
  97
  98     String id = var + "_fn" + fn.hashCode();
  99     ConflictNode node = id2cn.get(id);
 100     if (node == null) {
 101       node = new ConflictNode(id, ConflictNode.STALLSITE, t.getVar(), t.getStallSite());
 102     }
 103     node.addEffect(as, e);
 104     node.addTaint(t);
 105
 106     id2cn.put(id, node);
 107   }
 108
 109   public void addLiveInNodeEffect(Taint t, Effect e) {
 110
 111     FlatSESEEnterNode sese = t.getSESE();
 112     TempDescriptor invar = t.getVar();
 113     AllocSite as = t.getAllocSite();
 114
 115     String id = invar + "_sese" + sese.getPrettyIdentifier();
 116     ConflictNode node = id2cn.get(id);
 117     if (node == null) {
 118       node = new ConflictNode(id, ConflictNode.INVAR, t.getVar(), t.getSESE());
 119     }
 120     node.addEffect(as, e);
 121     node.addTaint(t);
 122
 123     id2cn.put(id, node);
 124   }
 125
 126   public void addConflictEdge(int type, ConflictNode nodeU, ConflictNode nodeV) {
 127
 128     // if there are two edges between the same node pair, coarse has a
 129     // priority
 130     Set<ConflictEdge> set = nodeU.getEdgeSet();
 131     ConflictEdge toBeRemoved = null;
 132     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 133       ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
 134
 135       if ((conflictEdge.getVertexU().equals(nodeU) && conflictEdge.getVertexV().equals(nodeV))
 136           || (conflictEdge.getVertexU().equals(nodeV) && conflictEdge.getVertexV().equals(nodeU))) {
 137         if (conflictEdge.getType() == ConflictGraph.FINE_GRAIN_EDGE
 138             && type == ConflictGraph.COARSE_GRAIN_EDGE) {
 139           toBeRemoved = conflictEdge;
 140           break;
 141         } else if (conflictEdge.getType() == ConflictGraph.COARSE_GRAIN_EDGE
 142             && type == ConflictGraph.FINE_GRAIN_EDGE) {
 143           // ignore
 144           return;
 145         }
 146       }
 147     }
 148
 149     if (toBeRemoved != null) {
 150       nodeU.getEdgeSet().remove(toBeRemoved);
 151       nodeV.getEdgeSet().remove(toBeRemoved);
 152     }
 153
 154     ConflictEdge newEdge = new ConflictEdge(nodeU, nodeV, type);
 155     nodeU.addEdge(newEdge);
 156     nodeV.addEdge(newEdge);
 157
 158   }
 159
 160   public void analyzeConflicts(Set<FlatNew> sitesToFlag, boolean useReachInfo) {
 161
 162     Set<String> keySet = id2cn.keySet();
 163     Set<String> analyzedIDSet = new HashSet<String>();
 164
 165     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 166       String nodeID = (String) iterator.next();
 167       ConflictNode node = id2cn.get(nodeID);
 168       analyzePossibleConflicts(analyzedIDSet, node, sitesToFlag, useReachInfo);
 169     }
 170
 171   }
 172
 173   private void analyzePossibleConflicts(Set<String> analyzedIDSet, ConflictNode currentNode,
 174       Set<FlatNew> sitesToFlag, boolean useReachInfo) {
 175     // compare with all nodes
 176     // examine the case where self-edge exists
 177
 178     int conflictType;
 179     if (currentNode.isInVarNode()) {
 180       conflictType = calculateConflictType(currentNode, useReachInfo);
 181       if (conflictType > ConflictGraph.NON_WRITE_CONFLICT) {
 182         addConflictEdge(conflictType, currentNode, currentNode);
 183         if (sitesToFlag != null) {
 184           sitesToFlag.addAll(currentNode.getFlatNewSet());
 185         }
 186       }
 187     }
 188
 189     Set<Entry<String, ConflictNode>> set = id2cn.entrySet();
 190     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 191       Entry<String, ConflictNode> entry = (Entry<String, ConflictNode>) iterator.next();
 192
 193       String entryNodeID = entry.getKey();
 194       ConflictNode entryNode = entry.getValue();
 195
 196       if (currentNode.isStallSiteNode() && entryNode.isStallSiteNode()) {
 197         continue;
 198       }
 199
 200       if ((currentNode.isInVarNode() && entryNode.isInVarNode())
 201           && (currentNode.getSESEIdentifier() == entryNode.getSESEIdentifier())
 202           && (currentNode.getVar().equals(entryNode.getVar()))) {
 203         continue;
 204       }
 205
 206       if ((!currentNode.getID().equals(entryNodeID))
 207           && !(analyzedIDSet.contains(currentNode.getID() + entryNodeID) || analyzedIDSet
 208               .contains(entryNodeID + currentNode.getID()))) {
 209
 210         conflictType = calculateConflictType(currentNode, entryNode, useReachInfo);
 211         if (conflictType > ConflictGraph.NON_WRITE_CONFLICT) {
 212           addConflictEdge(conflictType, currentNode, entryNode);
 213           if (sitesToFlag != null) {
 214             sitesToFlag.addAll(currentNode.getFlatNewSet());
 215             sitesToFlag.addAll(entryNode.getFlatNewSet());
 216           }
 217         }
 218         analyzedIDSet.add(currentNode.getID() + entryNodeID);
 219
 220       }
 221     }
 222
 223   }
 224
 225   private int calculateConflictType(ConflictNode node, boolean useReachInfo) {
 226
 227     int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
 228     Hashtable<AllocSite, Set<Effect>> alloc2readEffects = node.getReadEffectSet();
 229     Hashtable<AllocSite, Set<Effect>> alloc2writeEffects = node.getWriteEffectSet();
 230     Hashtable<AllocSite, Set<Effect>> alloc2SUEffects = node.getStrongUpdateEffectSet();
 231
 232     conflictType =
 233         updateConflictType(conflictType, determineConflictType(node, alloc2writeEffects, node,
 234             alloc2writeEffects, useReachInfo));
 235
 236     conflictType =
 237         updateConflictType(conflictType, hasStrongUpdateConflicts(node, alloc2SUEffects, node,
 238             alloc2readEffects, alloc2writeEffects, useReachInfo));
 239
 240     return conflictType;
 241   }
 242
 243   private int calculateConflictType(ConflictNode nodeA, ConflictNode nodeB, boolean useReachInfo) {
 244
 245     int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
 246
 247     Hashtable<AllocSite, Set<Effect>> alloc2readEffectsA = nodeA.getReadEffectSet();
 248     Hashtable<AllocSite, Set<Effect>> alloc2writeEffectsA = nodeA.getWriteEffectSet();
 249     Hashtable<AllocSite, Set<Effect>> alloc2SUEffectsA = nodeA.getStrongUpdateEffectSet();
 250     Hashtable<AllocSite, Set<Effect>> alloc2readEffectsB = nodeB.getReadEffectSet();
 251     Hashtable<AllocSite, Set<Effect>> alloc2writeEffectsB = nodeB.getWriteEffectSet();
 252     Hashtable<AllocSite, Set<Effect>> alloc2SUEffectsB = nodeB.getStrongUpdateEffectSet();
 253
 254     // if node A has write effects on reading/writing regions of node B
 255     conflictType =
 256         updateConflictType(conflictType, determineConflictType(nodeA, alloc2writeEffectsA, nodeB,
 257             alloc2readEffectsB, useReachInfo));
 258     conflictType =
 259         updateConflictType(conflictType, determineConflictType(nodeA, alloc2writeEffectsA, nodeB,
 260             alloc2writeEffectsB, useReachInfo));
 261
 262     // if node B has write effects on reading regions of node A
 263     conflictType =
 264         updateConflictType(conflictType, determineConflictType(nodeB, alloc2writeEffectsB, nodeA,
 265             alloc2readEffectsA, useReachInfo));
 266
 267     // strong udpate effects conflict with all effects
 268     // on objects that are reachable from the same heap roots
 269     // if node A has SU on regions of node B
 270     if (!alloc2SUEffectsA.isEmpty()) {
 271       conflictType =
 272           updateConflictType(conflictType, hasStrongUpdateConflicts(nodeA, alloc2SUEffectsA, nodeB,
 273               alloc2readEffectsB, alloc2writeEffectsB, useReachInfo));
 274     }
 275
 276     // if node B has SU on regions of node A
 277     if (!alloc2SUEffectsB.isEmpty()) {
 278       conflictType =
 279           updateConflictType(conflictType, hasStrongUpdateConflicts(nodeB, alloc2SUEffectsB, nodeA,
 280               alloc2readEffectsA, alloc2writeEffectsA, useReachInfo));
 281     }
 282
 283     return conflictType;
 284   }
 285
 286   private int hasStrongUpdateConflicts(ConflictNode nodeA,
 287       Hashtable<AllocSite, Set<Effect>> SUEffectsTableA, ConflictNode nodeB,
 288       Hashtable<AllocSite, Set<Effect>> readTableB, Hashtable<AllocSite, Set<Effect>> writeTableB,
 289       boolean useReachInfo) {
 290
 291     int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
 292
 293     Iterator effectItrA = SUEffectsTableA.entrySet().iterator();
 294     while (effectItrA.hasNext()) {
 295       Map.Entry meA = (Map.Entry) effectItrA.next();
 296       AllocSite asA = (AllocSite) meA.getKey();
 297       Set<Effect> strongUpdateSetA = (Set<Effect>) meA.getValue();
 298
 299       Iterator effectItrB = readTableB.entrySet().iterator();
 300       while (effectItrB.hasNext()) {
 301         Map.Entry meB = (Map.Entry) effectItrB.next();
 302         AllocSite asB = (AllocSite) meB.getKey();
 303         Set<Effect> esB = (Set<Effect>) meB.getValue();
 304
 305         for (Iterator iterator = strongUpdateSetA.iterator(); iterator.hasNext();) {
 306           Effect strongUpdateA = (Effect) iterator.next();
 307           for (Iterator iterator2 = esB.iterator(); iterator2.hasNext();) {
 308             Effect effectB = (Effect) iterator2.next();
 309
 310             if (strongUpdateA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite())
 311                 && strongUpdateA.getField().equals(effectB.getField())) {
 312               if (useReachInfo) {
 313                 FlatNew fnRoot1 = asA.getFlatNew();
 314                 FlatNew fnRoot2 = asB.getFlatNew();
 315                 FlatNew fnTarget = strongUpdateA.getAffectedAllocSite().getFlatNew();
 316                 if (da.mayBothReachTarget(fmEnclosing, fnRoot1, fnRoot2, fnTarget)) {
 317                   addCoarseEffect(nodeA, asA, strongUpdateA);
 318                   if (!nodeA.equals(nodeB)) {
 319                     addCoarseEffect(nodeB, asB, effectB);
 320                   }
 321                   conflictType = updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
 322                 }
 323               } else {
 324                 if (state.RCR) {
 325                   // need coarse effects for RCR from just one pass
 326                   addCoarseEffect(nodeA, asA, strongUpdateA);
 327                   if (!nodeA.equals(nodeB)) {
 328                     addCoarseEffect(nodeB, asB, effectB);
 329                   }
 330                   conflictType=ConflictGraph.COARSE_GRAIN_EDGE;
 331                 } else {
 332                   return ConflictGraph.COARSE_GRAIN_EDGE;
 333                 }
 334               }
 335
 336             }
 337
 338           }
 339         }
 340       }
 341
 342       effectItrB = writeTableB.entrySet().iterator();
 343       while (effectItrB.hasNext()) {
 344         Map.Entry meB = (Map.Entry) effectItrB.next();
 345         AllocSite asB = (AllocSite) meB.getKey();
 346         Set<Effect> esB = (Set<Effect>) meB.getValue();
 347
 348         for (Iterator iterator = strongUpdateSetA.iterator(); iterator.hasNext();) {
 349           Effect strongUpdateA = (Effect) iterator.next();
 350           for (Iterator iterator2 = esB.iterator(); iterator2.hasNext();) {
 351             Effect effectB = (Effect) iterator2.next();
 352
 353             if (strongUpdateA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite())
 354                 && strongUpdateA.getField().equals(effectB.getField())) {
 355
 356               if (useReachInfo) {
 357                 FlatNew fnRoot1 = asA.getFlatNew();
 358                 FlatNew fnRoot2 = asB.getFlatNew();
 359                 FlatNew fnTarget = strongUpdateA.getAffectedAllocSite().getFlatNew();
 360                 if (da.mayBothReachTarget(fmEnclosing, fnRoot1, fnRoot2, fnTarget)) {
 361                   addCoarseEffect(nodeA, asA, strongUpdateA);
 362                   if (!nodeA.equals(nodeB)) {
 363                     addCoarseEffect(nodeB, asB, effectB);
 364                   }
 365                   conflictType = updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
 366                 }
 367               } else {
 368                 return ConflictGraph.COARSE_GRAIN_EDGE;
 369               }
 370             }
 371
 372           }
 373         }
 374       }
 375
 376     }
 377
 378     return conflictType;
 379
 380   }
 381
 382   private int determineConflictType(ConflictNode nodeA,
 383       Hashtable<AllocSite, Set<Effect>> nodeAtable, ConflictNode nodeB,
 384       Hashtable<AllocSite, Set<Effect>> nodeBtable, boolean useReachInfo) {
 385
 386     int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
 387
 388     Iterator effectItrA = nodeAtable.entrySet().iterator();
 389     while (effectItrA.hasNext()) {
 390       Map.Entry meA = (Map.Entry) effectItrA.next();
 391       AllocSite asA = (AllocSite) meA.getKey();
 392       Set<Effect> esA = (Set<Effect>) meA.getValue();
 393
 394       Iterator effectItrB = nodeBtable.entrySet().iterator();
 395       while (effectItrB.hasNext()) {
 396         Map.Entry meB = (Map.Entry) effectItrB.next();
 397         AllocSite asB = (AllocSite) meB.getKey();
 398         Set<Effect> esB = (Set<Effect>) meB.getValue();
 399
 400         for (Iterator iterator = esA.iterator(); iterator.hasNext();) {
 401           Effect effectA = (Effect) iterator.next();
 402           for (Iterator iterator2 = esB.iterator(); iterator2.hasNext();) {
 403             Effect effectB = (Effect) iterator2.next();
 404
 405             if (effectA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite())
 406                 && effectA.getField().equals(effectB.getField())) {
 407
 408               if (useReachInfo) {
 409                 FlatNew fnRoot1 = asA.getFlatNew();
 410                 FlatNew fnRoot2 = asB.getFlatNew();
 411                 FlatNew fnTarget = effectA.getAffectedAllocSite().getFlatNew();
 412                 if (fnRoot1.equals(fnRoot2)) {
 413                   if (!da.mayManyReachTarget(fmEnclosing, fnRoot1, fnTarget)) {
 414                     // fine-grained conflict case
 415                     conflictType = updateConflictType(conflictType, ConflictGraph.FINE_GRAIN_EDGE);
 416                   } else {
 417                     // coarse-grained conflict case
 418                     addCoarseEffect(nodeA, asA, effectA);
 419                     if (!nodeA.equals(nodeB)) {
 420                       addCoarseEffect(nodeB, asB, effectB);
 421                     }
 422                     conflictType =
 423                         updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
 424                   }
 425                 } else {
 426                   if (da.mayBothReachTarget(fmEnclosing, fnRoot1, fnRoot2, fnTarget)) {
 427                     addCoarseEffect(nodeA, asA, effectA);
 428                     if (!nodeA.equals(nodeB)) {
 429                       addCoarseEffect(nodeB, asB, effectB);
 430                     }
 431                     conflictType =
 432                         updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
 433                   } else {
 434                   }
 435                 }
 436               } else {
 437                 if (state.RCR) {
 438                   // need coarse effects for RCR from just one pass
 439                   addCoarseEffect(nodeA, asA, effectA);
 440                   if (!nodeA.equals(nodeB)) {
 441                     addCoarseEffect(nodeB, asB, effectB);
 442                   }
 443                   conflictType=ConflictGraph.COARSE_GRAIN_EDGE;
 444                 } else {
 445                   return ConflictGraph.COARSE_GRAIN_EDGE;
 446                 }
 447               }
 448             }
 449           }
 450         }
 451       }
 452     }
 453
 454     return conflictType;
 455   }
 456
 457   private void addCoarseEffect(ConflictNode node, AllocSite as, Effect e) {
 458     Taint t = node.getTaint(as);
 459     addEffectSetByTaint(t, e);
 460   }
 461
 462   private void addEffectSetByTaint(Taint t, Effect e) {
 463
 464     FlatNode node=t.getSESE();
 465     if(node==null){
 466       // stall site case
 467       node=t.getStallSite();
 468     }
 469
 470     Hashtable<Taint, Set<Effect>> taint2Conflicts = sese2te.get(node);
 471     if (taint2Conflicts == null) {
 472       taint2Conflicts = new Hashtable<Taint, Set<Effect>>();
 473     }
 474
 475     Set<Effect> effectSet = taint2Conflicts.get(t);
 476     if (effectSet == null) {
 477       effectSet = new HashSet<Effect>();
 478     }
 479     effectSet.add(e);
 480     taint2Conflicts.put(t, effectSet);
 481
 482     sese2te.put(node, taint2Conflicts);
 483
 484   }
 485
 486   private int updateConflictType(int current, int newType) {
 487     if (newType > current) {
 488       return newType;
 489     } else {
 490       return current;
 491     }
 492   }
 493
 494   public void clearAllConflictEdge() {
 495     Collection<ConflictNode> nodes = id2cn.values();
 496     for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
 497       ConflictNode conflictNode = (ConflictNode) iterator.next();
 498       conflictNode.getEdgeSet().clear();
 499     }
 500   }
 501
 502   public HashSet<ConflictEdge> getEdgeSet() {
 503
 504     HashSet<ConflictEdge> returnSet = new HashSet<ConflictEdge>();
 505
 506     Collection<ConflictNode> nodes = id2cn.values();
 507     for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
 508       ConflictNode conflictNode = (ConflictNode) iterator.next();
 509       returnSet.addAll(conflictNode.getEdgeSet());
 510     }
 511
 512     return returnSet;
 513   }
 514
 515   public boolean hasConflictEdge() {
 516
 517     Set<String> keySet = id2cn.keySet();
 518     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 519       String key = (String) iterator.next();
 520       ConflictNode node = id2cn.get(key);
 521       if (node.getEdgeSet().size() > 0) {
 522         return true;
 523       }
 524     }
 525     return false;
 526   }
 527
 528   public boolean isFineElement(int type) {
 529     if (type == ConflictNode.FINE_READ || type == ConflictNode.FINE_WRITE
 530         || type == ConflictNode.PARENT_READ || type == ConflictNode.PARENT_WRITE) {
 531       return true;
 532     } else {
 533       return false;
 534     }
 535   }
 536
 537   public SESEWaitingQueue getWaitingElementSetBySESEID(int seseID, Set<SESELock> seseLockSet) {
 538
 539     HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
 540
 541     Iterator iter = id2cn.entrySet().iterator();
 542     while (iter.hasNext()) {
 543       Entry entry = (Entry) iter.next();
 544       String conflictNodeID = (String) entry.getKey();
 545       ConflictNode node = (ConflictNode) entry.getValue();
 546
 547       if (node.isInVarNode()) {
 548         if (node.getSESEIdentifier() == seseID) {
 549
 550           Set<ConflictEdge> edgeSet = node.getEdgeSet();
 551           for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
 552             ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
 553
 554             for (Iterator<SESELock> seseLockIter = seseLockSet.iterator(); seseLockIter.hasNext();) {
 555               SESELock seseLock = seseLockIter.next();
 556               if (seseLock.containsConflictNode(node)
 557                   && seseLock.containsConflictEdge(conflictEdge)) {
 558                 WaitingElement newElement = new WaitingElement();
 559                 newElement.setQueueID(seseLock.getID());
 560                 newElement.setStatus(seseLock.getNodeType(node));
 561                 newElement.setTempDesc(node.getVar());
 562                 if (isFineElement(newElement.getStatus())) {
 563                   newElement.setDynID(node.getVar().toString());
 564                 }
 565                 if (!waitingElementSet.contains(newElement)) {
 566                   waitingElementSet.add(newElement);
 567                 }
 568
 569               }
 570             }
 571           }
 572
 573         }
 574       }
 575
 576     }
 577
 578     // handle the case that multiple enqueues by an SESE for different live-in
 579     // into the same queue
 580      return refineQueue(waitingElementSet);
 581
 582   }
 583
 584   public SESEWaitingQueue refineQueue(Set<WaitingElement> waitingElementSet) {
 585
 586     Set<WaitingElement> refinedSet = new HashSet<WaitingElement>();
 587     HashMap<Integer, Set<WaitingElement>> map = new HashMap<Integer, Set<WaitingElement>>();
 588     SESEWaitingQueue seseDS = new SESEWaitingQueue();
 589
 590     for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) {
 591       WaitingElement waitingElement = (WaitingElement) iterator.next();
 592       Set<WaitingElement> set = map.get(new Integer(waitingElement.getQueueID()));
 593       if (set == null) {
 594         set = new HashSet<WaitingElement>();
 595       }
 596       set.add(waitingElement);
 597       map.put(new Integer(waitingElement.getQueueID()), set);
 598     }
 599
 600     Set<Integer> keySet = map.keySet();
 601     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 602       Integer queueID = (Integer) iterator.next();
 603       Set<WaitingElement> queueWEset = map.get(queueID);
 604       refineQueue(queueID.intValue(), queueWEset, seseDS);
 605     }
 606
 607     return seseDS;
 608   }
 609
 610   private void refineQueue(int queueID, Set<WaitingElement> waitingElementSet,
 611       SESEWaitingQueue seseDS) {
 612
 613     if (waitingElementSet.size() > 1) {
 614       // only consider there is more than one element submitted by same SESE
 615       Set<WaitingElement> refinedSet = new HashSet<WaitingElement>();
 616
 617       int numCoarse = 0;
 618       int numRead = 0;
 619       int numWrite = 0;
 620       int total = waitingElementSet.size();
 621       WaitingElement SCCelement = null;
 622       WaitingElement coarseElement = null;
 623
 624       for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) {
 625         WaitingElement waitingElement = (WaitingElement) iterator.next();
 626         if (waitingElement.getStatus() == ConflictNode.FINE_READ) {
 627           numRead++;
 628         } else if (waitingElement.getStatus() == ConflictNode.FINE_WRITE) {
 629           numWrite++;
 630         } else if (waitingElement.getStatus() == ConflictNode.COARSE) {
 631           numCoarse++;
 632           coarseElement = waitingElement;
 633         } else if (waitingElement.getStatus() == ConflictNode.SCC) {
 634           SCCelement = waitingElement;
 635         }
 636       }
 637       if (SCCelement != null) {
 638         // if there is at lease one SCC element, just enqueue SCC and
 639         // ignore others.
 640         if(state.RCR){
 641           // for rcr, we need to label all of coarse tempdescriptors
 642           // here assume that all waiting elements are coarse
 643           for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) {
 644             WaitingElement waitingElement = (WaitingElement) iterator.next();
 645             SCCelement.addTempDesc(waitingElement.getTempDesc());
 646             if(waitingElement!=SCCelement){
 647               waitingElement.setBogus(true);
 648               refinedSet.add(waitingElement);
 649             }
 650           }
 651         }
 652         refinedSet.add(SCCelement);
 653       } else if (numCoarse == 1 && (numRead + numWrite  == total)) {
 654         // if one is a coarse, the othere are reads/write, enqueue SCC.
 655         WaitingElement we = new WaitingElement();
 656         we.setQueueID(queueID);
 657         we.setStatus(ConflictNode.SCC);
 658         refinedSet.add(we);
 659       } else if (numCoarse == total) {
 660         // if there are multiple coarses, enqueue just one coarse.
 661         if(state.RCR){
 662           // for rcr, we need to label all of coarse tempdescriptors
 663           for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) {
 664             WaitingElement waitingElement = (WaitingElement) iterator.next();
 665             if(waitingElement!=coarseElement){
 666               coarseElement.addTempDesc(waitingElement.getTempDesc());
 667               waitingElement.setBogus(true);
 668               refinedSet.add(waitingElement);
 669             }
 670           }
 671         }
 672         refinedSet.add(coarseElement);
 673       } else if (numWrite == total || (numRead + numWrite) == total) {
 674         // code generator is going to handle the case for multiple writes &
 675         // read/writes.
 676         seseDS.setType(queueID, SESEWaitingQueue.EXCEPTION);
 677         refinedSet.addAll(waitingElementSet);
 678       } else {
 679         // otherwise, enqueue everything.
 680         refinedSet.addAll(waitingElementSet);
 681       }
 682       seseDS.setWaitingElementSet(queueID, refinedSet);
 683     } else {
 684       seseDS.setWaitingElementSet(queueID, waitingElementSet);
 685     }
 686
 687   }
 688
 689   public Set<WaitingElement> getStallSiteWaitingElementSet(FlatNode stallSite,
 690       Set<SESELock> seseLockSet) {
 691
 692     HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
 693     Iterator iter = id2cn.entrySet().iterator();
 694     while (iter.hasNext()) {
 695       Entry entry = (Entry) iter.next();
 696       String conflictNodeID = (String) entry.getKey();
 697       ConflictNode node = (ConflictNode) entry.getValue();
 698
 699       if (node.isStallSiteNode() && node.getStallSiteFlatNode().equals(stallSite)) {
 700         Set<ConflictEdge> edgeSet = node.getEdgeSet();
 701         for (Iterator iter2 = edgeSet.iterator(); iter2.hasNext();) {
 702           ConflictEdge conflictEdge = (ConflictEdge) iter2.next();
 703
 704           for (Iterator<SESELock> seseLockIter = seseLockSet.iterator(); seseLockIter.hasNext();) {
 705             SESELock seseLock = seseLockIter.next();
 706             if (seseLock.containsConflictNode(node) && seseLock.containsConflictEdge(conflictEdge)) {
 707               WaitingElement newElement = new WaitingElement();
 708               newElement.setQueueID(seseLock.getID());
 709               newElement.setStatus(seseLock.getNodeType(node));
 710               if (isFineElement(newElement.getStatus())) {
 711                 newElement.setDynID(node.getVar().toString());
 712               }
 713               newElement.setTempDesc(node.getVar());
 714               waitingElementSet.add(newElement);
 715             }
 716           }
 717
 718         }
 719
 720       }
 721
 722     }
 723
 724     return waitingElementSet;
 725   }
 726
 727   public Hashtable<Taint, Set<Effect>> getConflictEffectSet(FlatNode fn) {
 728     return sese2te.get(fn);
 729   }
 730
 731   public void writeGraph(String graphName, boolean filter) throws java.io.IOException {
 732
 733     graphName = graphName.replaceAll("[\\W]", "");
 734
 735     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 736     bw.write("graph " + graphName + " {\n");
 737
 738     // then visit every heap region node
 739     Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
 740     Iterator<Entry<String, ConflictNode>> i = s.iterator();
 741
 742     HashSet<ConflictEdge> addedSet = new HashSet<ConflictEdge>();
 743
 744     while (i.hasNext()) {
 745       Entry<String, ConflictNode> entry = i.next();
 746       ConflictNode node = entry.getValue();
 747
 748       if (filter) {
 749         if (node.getID().startsWith("___dst") || node.getID().startsWith("___srctmp")
 750             || node.getID().startsWith("___neverused") || node.getID().startsWith("___temp")) {
 751
 752           continue;
 753         }
 754
 755         if (node.getEdgeSet().isEmpty()) {
 756           continue;
 757         }
 758
 759       }
 760
 761       String attributes = "[";
 762
 763       attributes += "label=\"" + node.getID() + "\\n";
 764
 765       if (node.isStallSiteNode()) {
 766         attributes += "STALL SITE" + "\\n" + "\"]";
 767       } else {
 768         attributes += "LIVE-IN" + "\\n" + "\"]";
 769       }
 770       bw.write(entry.getKey() + attributes + ";\n");
 771
 772       Set<ConflictEdge> edgeSet = node.getEdgeSet();
 773       for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
 774         ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
 775
 776         ConflictNode u = conflictEdge.getVertexU();
 777         ConflictNode v = conflictEdge.getVertexV();
 778
 779         if (filter) {
 780           String uID = u.getID();
 781           String vID = v.getID();
 782           if (uID.startsWith("___dst") || uID.startsWith("___srctmp")
 783               || uID.startsWith("___neverused") || uID.startsWith("___temp")
 784               || vID.startsWith("___dst") || vID.startsWith("___srctmp")
 785               || vID.startsWith("___neverused") || vID.startsWith("___temp")) {
 786             continue;
 787           }
 788         }
 789
 790         if (!addedSet.contains(conflictEdge)) {
 791           bw.write("" + u.getID() + "--" + v.getID() + "[label=" + conflictEdge.toGraphEdgeString()
 792               + ",decorate];\n");
 793           addedSet.add(conflictEdge);
 794         }
 795
 796       }
 797     }
 798
 799     bw.write("  graphTitle[label=\"" + graphName + "\",shape=box];\n");
 800
 801     bw.write("}\n");
 802     bw.close();
 803
 804   }
 805
 806 }