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