Robust/src/Analysis/OoOJava/ConflictGraph.java

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