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