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