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