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