Robust/src/Analysis/MLP/ConflictGraph.java

   1 package Analysis.MLP;
   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.Set;
  11 import java.util.Map.Entry;
  12
  13 import Analysis.OwnershipAnalysis.HeapRegionNode;
  14 import Analysis.OwnershipAnalysis.OwnershipGraph;
  15 import Analysis.OwnershipAnalysis.ReachabilitySet;
  16 import Analysis.OwnershipAnalysis.TokenTuple;
  17 import IR.Flat.FlatMethod;
  18 import IR.Flat.FlatSESEEnterNode;
  19 import IR.Flat.TempDescriptor;
  20
  21 public class ConflictGraph {
  22
  23         static private int uniqueCliqueIDcount = 100;
  24
  25         public Hashtable<String, ConflictNode> id2cn;
  26         private OwnershipGraph og;
  27
  28         public ConflictGraph(OwnershipGraph og) {
  29                 id2cn = new Hashtable<String, ConflictNode>();
  30                 this.og = og;
  31         }
  32
  33         public boolean hasConflictEdge() {
  34
  35                 Set<String> keySet = id2cn.keySet();
  36                 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
  37                         String key = (String) iterator.next();
  38                         ConflictNode node = id2cn.get(key);
  39                         if (node.getEdgeSet().size() > 0) {
  40                                 return true;
  41                         }
  42                 }
  43                 return false;
  44         }
  45
  46         public void analyzeConflicts() {
  47
  48                 Set<String> keySet = id2cn.keySet();
  49                 Set<String> analyzedIDSet = new HashSet<String>();
  50
  51                 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
  52                         String nodeID = (String) iterator.next();
  53                         ConflictNode node = id2cn.get(nodeID);
  54                         analyzePossibleConflicts(analyzedIDSet, node);
  55                 }
  56         }
  57
  58         private boolean compareHRNSet(Set<HeapRegionNode> setA,
  59                         Set<HeapRegionNode> setB) {
  60                 boolean found = false;
  61                 for (Iterator iterator = setA.iterator(); iterator.hasNext();) {
  62                         HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next();
  63                         String gID = heapRegionNode.getGloballyUniqueIdentifier();
  64                         for (Iterator iterator2 = setB.iterator(); iterator2.hasNext();) {
  65                                 HeapRegionNode heapRegionNode2 = (HeapRegionNode) iterator2
  66                                                 .next();
  67                                 if (heapRegionNode2.getGloballyUniqueIdentifier().equals(gID)) {
  68                                         found = true;
  69                                 }
  70                         }
  71                 }
  72                 if (!found) {
  73                         return false;
  74                 }
  75                 return true;
  76         }
  77
  78         public String addStallNode(TempDescriptor td, FlatMethod fm,
  79                         StallSite stallSite, Set<Set> reachabilitySet) {
  80
  81                 String stallNodeID = td + "_" + fm.getMethod().getSymbol();
  82
  83                 if (!id2cn.containsKey(stallNodeID)) {
  84                         StallSiteNode newNode = new StallSiteNode(stallNodeID, td,
  85                                         stallSite, reachabilitySet);
  86                         id2cn.put(stallNodeID, newNode);
  87                         // it add new new stall node to conflict graph
  88                         return stallNodeID;
  89                 }
  90                 // it doesn't add new stall node because stall node has already been
  91                 // added.
  92                 return null;
  93         }
  94
  95         public StallSiteNode getStallNode(String stallNodeID) {
  96                 ConflictNode node = id2cn.get(stallNodeID);
  97                 if (node instanceof StallSiteNode) {
  98                         return (StallSiteNode) node;
  99                 } else {
 100                         return null;
 101                 }
 102         }
 103
 104         public void addLiveInNode(TempDescriptor td, Set<HeapRegionNode> hrnSet,
 105                         FlatSESEEnterNode fsen, Set<SESEEffectsKey> readEffectsSet,
 106                         Set<SESEEffectsKey> writeEffectsSet,
 107                         Set<SESEEffectsKey> strongUpdateSet, Set<Set> reachabilitySet) {
 108
 109                 String liveinNodeID = td + "_" + fsen.getIdentifier();
 110
 111                 LiveInNode newNode = new LiveInNode(liveinNodeID, td, hrnSet,
 112                                 readEffectsSet, writeEffectsSet, strongUpdateSet,
 113                                 reachabilitySet, fsen.getIdentifier());
 114                 id2cn.put(liveinNodeID, newNode);
 115
 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                 HashSet<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
 128                                         .getVertexV().equals(nodeV))
 129                                         || (conflictEdge.getVertexU().equals(nodeV) && conflictEdge
 130                                                         .getVertexV().equals(nodeU))) {
 131                                 if (conflictEdge.getType() == ConflictEdge.FINE_GRAIN_EDGE
 132                                                 && type == ConflictEdge.COARSE_GRAIN_EDGE) {
 133                                         toBeRemoved = conflictEdge;
 134                                         break;
 135                                 } else if (conflictEdge.getType() == ConflictEdge.COARSE_GRAIN_EDGE
 136                                                 && type == ConflictEdge.FINE_GRAIN_EDGE) {
 137                                         // ignore
 138                                         return;
 139                                 }
 140                         }
 141                 }
 142
 143                 if (toBeRemoved != null) {
 144                         nodeU.getEdgeSet().remove(toBeRemoved);
 145                         nodeV.getEdgeSet().remove(toBeRemoved);
 146                 }
 147
 148                 ConflictEdge newEdge = new ConflictEdge(nodeU, nodeV, type);
 149                 nodeU.addEdge(newEdge);
 150                 nodeV.addEdge(newEdge);
 151
 152         }
 153
 154         public Set<WaitingElement> getStallSiteWaitingElementSet(
 155                         ParentChildConflictsMap conflictsMap, HashSet<SESELock> seseLockSet) {
 156
 157                 HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
 158                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
 159                 Collection<StallSite> stallSites = conflictsMap.getStallMap().values();
 160
 161                 for (Iterator iterator = stallSites.iterator(); iterator.hasNext();) {
 162
 163                         StallSite stallSite = (StallSite) iterator.next();
 164                         Iterator<Entry<String, ConflictNode>> i = s.iterator();
 165                         while (i.hasNext()) {
 166                                 Entry<String, ConflictNode> entry = i.next();
 167                                 ConflictNode node = entry.getValue();
 168
 169                                 if (node instanceof StallSiteNode) {
 170                                         StallSiteNode stallSiteNode = (StallSiteNode) node;
 171                                         if (stallSiteNode.getStallSite().equals(stallSite)) {
 172                                                 HashSet<ConflictEdge> edgeSet = stallSiteNode
 173                                                                 .getEdgeSet();
 174                                                 for (Iterator iter2 = edgeSet.iterator(); iter2
 175                                                                 .hasNext();) {
 176                                                         ConflictEdge conflictEdge = (ConflictEdge) iter2
 177                                                                         .next();
 178
 179                                                         for (Iterator<SESELock> seseLockIter = seseLockSet
 180                                                                         .iterator(); seseLockIter.hasNext();) {
 181                                                                 SESELock seseLock = seseLockIter.next();
 182                                                                 if (seseLock
 183                                                                                 .containsConflictNode(stallSiteNode)
 184                                                                                 && seseLock
 185                                                                                                 .containsConflictEdge(conflictEdge)) {
 186                                                                         WaitingElement newElement = new WaitingElement();
 187                                                                         newElement.setQueueID(seseLock.getID());
 188                                                                         if (isFineElement(newElement.getStatus())) {
 189                                                                                 newElement
 190                                                                                                 .setDynID(node
 191                                                                                                                 .getTempDescriptor()
 192                                                                                                                 .toString());
 193                                                                         }
 194                                                                         newElement.setStatus(seseLock
 195                                                                                         .getNodeType(stallSiteNode));
 196                                                                         waitingElementSet.add(newElement);
 197                                                                 }
 198                                                         }
 199                                                 }
 200                                         }
 201                                 }
 202                         }
 203
 204                 }
 205
 206                 return waitingElementSet;
 207         }
 208
 209         private Set<Integer> getConnectedConflictNode(ConflictEdge conflictEdge,
 210                         int seseID) {
 211
 212                 HashSet<Integer> nodeIDSet = new HashSet<Integer>();
 213
 214                 if (conflictEdge.getVertexU() instanceof LiveInNode) {
 215                         LiveInNode lin = (LiveInNode) conflictEdge.getVertexU();
 216                         if (lin.getSESEIdentifier() != seseID) {
 217                                 nodeIDSet.add(new Integer(lin.getSESEIdentifier()));
 218                         }
 219                 } else {
 220                         // it is stall site
 221                         nodeIDSet.add(new Integer(-1));
 222                 }
 223                 if (conflictEdge.getVertexV() instanceof LiveInNode) {
 224                         LiveInNode lin = (LiveInNode) conflictEdge.getVertexV();
 225                         if (lin.getSESEIdentifier() != seseID) {
 226                                 nodeIDSet.add(new Integer(lin.getSESEIdentifier()));
 227                         }
 228                 } else {
 229                         // it is stall site
 230                         nodeIDSet.add(new Integer(-1));
 231                 }
 232
 233                 // self-edge case
 234                 if (conflictEdge.getVertexU() instanceof LiveInNode
 235                                 && conflictEdge.getVertexV() instanceof LiveInNode) {
 236                         if (((LiveInNode) conflictEdge.getVertexU()).getSESEIdentifier() == seseID
 237                                         && ((LiveInNode) conflictEdge.getVertexV())
 238                                                         .getSESEIdentifier() == seseID) {
 239                                 nodeIDSet.add(seseID);
 240                         }
 241                 }
 242
 243                 return nodeIDSet;
 244         }
 245
 246         public Set<Integer> getConnectedConflictNodeSet(int seseID) {
 247
 248                 HashSet<Integer> nodeIDSet = new HashSet<Integer>();
 249
 250                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
 251                 Iterator<Entry<String, ConflictNode>> i = s.iterator();
 252
 253                 while (i.hasNext()) {
 254                         Entry<String, ConflictNode> entry = i.next();
 255                         ConflictNode node = entry.getValue();
 256
 257                         if (node instanceof LiveInNode) {
 258                                 LiveInNode liveInNode = (LiveInNode) node;
 259                                 if (liveInNode.getSESEIdentifier() == seseID) {
 260                                         HashSet<ConflictEdge> edgeSet = liveInNode.getEdgeSet();
 261                                         for (Iterator iterator = edgeSet.iterator(); iterator
 262                                                         .hasNext();) {
 263                                                 ConflictEdge conflictEdge = (ConflictEdge) iterator
 264                                                                 .next();
 265                                                 //
 266                                                 nodeIDSet.addAll(getConnectedConflictNode(conflictEdge,
 267                                                                 seseID));
 268                                                 //
 269                                         }
 270                                 }
 271                         }
 272                 }
 273
 274                 return nodeIDSet;
 275
 276         }
 277
 278         public SESEWaitingQueue getWaitingElementSetBySESEID(int seseID,
 279                         HashSet<SESELock> seseLockSet) {
 280                 HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
 281
 282                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
 283                 Iterator<Entry<String, ConflictNode>> i = s.iterator();
 284
 285                 while (i.hasNext()) {
 286                         Entry<String, ConflictNode> entry = i.next();
 287                         ConflictNode node = entry.getValue();
 288
 289                         if (node instanceof LiveInNode) {
 290                                 LiveInNode liveInNode = (LiveInNode) node;
 291                                 if (liveInNode.getSESEIdentifier() == seseID) {
 292
 293                                         HashSet<ConflictEdge> edgeSet = liveInNode.getEdgeSet();
 294
 295                                         for (Iterator iterator = edgeSet.iterator(); iterator
 296                                                         .hasNext();) {
 297                                                 ConflictEdge conflictEdge = (ConflictEdge) iterator
 298                                                                 .next();
 299
 300                                                 for (Iterator<SESELock> seseLockIter = seseLockSet
 301                                                                 .iterator(); seseLockIter.hasNext();) {
 302                                                         SESELock seseLock = seseLockIter.next();
 303                                                         if (seseLock.containsConflictNode(liveInNode)
 304                                                                         && seseLock
 305                                                                                         .containsConflictEdge(conflictEdge)) {
 306                                                                 WaitingElement newElement = new WaitingElement();
 307                                                                 newElement.setQueueID(seseLock.getID());
 308                                                                 newElement.setStatus(seseLock
 309                                                                                 .getNodeType(liveInNode));
 310                                                                 if (isFineElement(newElement.getStatus())) {
 311                                                                         newElement.setDynID(node
 312                                                                                         .getTempDescriptor().toString());
 313                                                                         newElement.setTempDesc(node.getTempDescriptor());
 314                                                                 }
 315                                                                 if (!waitingElementSet.contains(newElement)) {
 316                                                                         waitingElementSet.add(newElement);
 317                                                                 }
 318
 319                                                         }
 320                                                 }
 321                                         }
 322
 323                                 }
 324                         }
 325
 326                 }
 327
 328                 //handle the case that multiple enqueues by an SESE for different live-in into the same queue
 329                 return refineQueue(waitingElementSet);
 330 //              return waitingElementSet;
 331
 332         }
 333
 334         public SESEWaitingQueue refineQueue(Set<WaitingElement> waitingElementSet) {
 335
 336                 Set<WaitingElement> refinedSet=new HashSet<WaitingElement>();
 337                 HashMap<Integer, Set<WaitingElement>> map = new HashMap<Integer, Set<WaitingElement>>();
 338                 SESEWaitingQueue seseDS=new SESEWaitingQueue();
 339
 340                 for (Iterator iterator = waitingElementSet.iterator(); iterator
 341                                 .hasNext();) {
 342                         WaitingElement waitingElement = (WaitingElement) iterator.next();
 343                         Set<WaitingElement> set=map.get(new Integer(waitingElement.getQueueID()));
 344                         if(set==null){
 345                                 set=new HashSet<WaitingElement>();
 346                         }
 347                         set.add(waitingElement);
 348                         map.put(new Integer(waitingElement.getQueueID()), set);
 349                 }
 350
 351                 Set<Integer> keySet=map.keySet();
 352                 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 353                         Integer queueID = (Integer) iterator.next();
 354                         Set<WaitingElement> queueWEset=map.get(queueID);
 355                         refineQueue(queueID.intValue(),queueWEset,seseDS);
 356                 }
 357
 358                 return seseDS;
 359         }
 360
 361         private void refineQueue(int queueID,
 362                         Set<WaitingElement> waitingElementSet, SESEWaitingQueue seseDS) {
 363
 364                 if (waitingElementSet.size() > 1) {
 365                         //only consider there is more than one element submitted by same SESE
 366                         Set<WaitingElement> refinedSet = new HashSet<WaitingElement>();
 367
 368                         int numCoarse = 0;
 369                         int numRead = 0;
 370                         int numWrite = 0;
 371                         int total=waitingElementSet.size();
 372                         WaitingElement SCCelement = null;
 373                         WaitingElement coarseElement = null;
 374
 375                         for (Iterator iterator = waitingElementSet.iterator(); iterator
 376                                         .hasNext();) {
 377                                 WaitingElement waitingElement = (WaitingElement) iterator
 378                                                 .next();
 379                                 if (waitingElement.getStatus() == ConflictNode.FINE_READ) {
 380                                         numRead++;
 381                                 } else if (waitingElement.getStatus() == ConflictNode.FINE_WRITE) {
 382                                         numWrite++;
 383                                 } else if (waitingElement.getStatus() == ConflictNode.COARSE) {
 384                                         numCoarse++;
 385                                         coarseElement = waitingElement;
 386                                 } else if (waitingElement.getStatus() == ConflictNode.SCC) {
 387                                         SCCelement = waitingElement;
 388                                 }
 389                         }
 390
 391                         if (SCCelement != null) {
 392                                 // if there is at lease one SCC element, just enqueue SCC and
 393                                 // ignore others.
 394                                 refinedSet.add(SCCelement);
 395                         } else if (numCoarse == 1 && (numRead + numWrite == total)) {
 396                                 // if one is a coarse, the othere are reads/write, enqueue SCC.
 397                                 WaitingElement we = new WaitingElement();
 398                                 we.setQueueID(queueID);
 399                                 we.setStatus(ConflictNode.SCC);
 400                                 refinedSet.add(we);
 401                         } else if (numCoarse == total) {
 402                                 // if there are multiple coarses, enqueue just one coarse.
 403                                 refinedSet.add(coarseElement);
 404                         } else if(numWrite==total || (numRead+numWrite)==total){
 405                                 // code generator is going to handle the case for multiple writes & read/writes.
 406                                 seseDS.setType(queueID, SESEWaitingQueue.EXCEPTION);
 407                                 refinedSet.addAll(waitingElementSet);
 408                         } else{
 409                                 // otherwise, enqueue everything.
 410                                 refinedSet.addAll(waitingElementSet);
 411                         }
 412                         seseDS.setWaitingElementSet(queueID, refinedSet);
 413                 } else {
 414                         seseDS.setWaitingElementSet(queueID, waitingElementSet);
 415                 }
 416
 417         }
 418
 419         public boolean isFineElement(int type) {
 420                 if (type == ConflictNode.FINE_READ || type == ConflictNode.FINE_WRITE
 421                                 || type == ConflictNode.PARENT_READ
 422                                 || type == ConflictNode.PARENT_WRITE) {
 423                         return true;
 424                 } else {
 425                         return false;
 426                 }
 427         }
 428
 429         public HashSet<ConflictEdge> getEdgeSet() {
 430
 431                 HashSet<ConflictEdge> returnSet = new HashSet<ConflictEdge>();
 432
 433                 Collection<ConflictNode> nodes = id2cn.values();
 434                 for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
 435                         ConflictNode conflictNode = (ConflictNode) iterator.next();
 436                         returnSet.addAll(conflictNode.getEdgeSet());
 437                 }
 438
 439                 return returnSet;
 440         }
 441
 442         public void writeGraph(String graphName, boolean filter)
 443                         throws java.io.IOException {
 444
 445                 graphName = graphName.replaceAll("[\\W]", "");
 446
 447                 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName
 448                                 + ".dot"));
 449                 bw.write("graph " + graphName + " {\n");
 450
 451                 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
 452                 // then visit every heap region node
 453                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
 454                 Iterator<Entry<String, ConflictNode>> i = s.iterator();
 455
 456                 HashSet<ConflictEdge> addedSet = new HashSet<ConflictEdge>();
 457
 458                 while (i.hasNext()) {
 459                         Entry<String, ConflictNode> entry = i.next();
 460                         ConflictNode node = entry.getValue();
 461
 462                         if (filter) {
 463                                 if (node.getID().startsWith("___dst")
 464                                                 || node.getID().startsWith("___srctmp")
 465                                                 || node.getID().startsWith("___neverused")
 466                                                 || node.getID().startsWith("___temp")) {
 467
 468                                         continue;
 469                                 }
 470                         }
 471
 472                         String attributes = "[";
 473
 474                         attributes += "label=\"ID" + node.getID() + "\\n";
 475
 476                         if (node instanceof StallSiteNode) {
 477                                 attributes += "STALL SITE" + "\\n" + "\"]";
 478                         } else {
 479                                 attributes += "LIVE-IN" + "\\n" + "\"]";
 480                         }
 481                         bw.write(entry.getKey() + attributes + ";\n");
 482
 483                         HashSet<ConflictEdge> edgeSet = node.getEdgeSet();
 484                         for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
 485                                 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
 486
 487                                 ConflictNode u = conflictEdge.getVertexU();
 488                                 ConflictNode v = conflictEdge.getVertexV();
 489
 490                                 if (filter) {
 491                                         String uID = u.getID();
 492                                         String vID = v.getID();
 493                                         if (uID.startsWith("___dst") || uID.startsWith("___srctmp")
 494                                                         || uID.startsWith("___neverused")
 495                                                         || uID.startsWith("___temp")
 496                                                         || vID.startsWith("___dst")
 497                                                         || vID.startsWith("___srctmp")
 498                                                         || vID.startsWith("___neverused")
 499                                                         || vID.startsWith("___temp")) {
 500                                                 continue;
 501                                         }
 502                                 }
 503
 504                                 if (!addedSet.contains(conflictEdge)) {
 505                                         bw.write(" " + u.getID() + "--" + v.getID() + "[label="
 506                                                         + conflictEdge.toGraphEdgeString()
 507                                                         + ",decorate];\n");
 508                                         addedSet.add(conflictEdge);
 509                                 }
 510
 511                         }
 512                 }
 513
 514                 bw.write("  graphTitle[label=\"" + graphName + "\",shape=box];\n");
 515
 516                 bw.write("}\n");
 517                 bw.close();
 518
 519         }
 520
 521         private int calculateConflictType(StallSiteNode nodeA, LiveInNode nodeB) {
 522
 523                 StallSite stallSite = nodeA.getStallSite();
 524                 Set<SESEEffectsKey> writeEffectsSet = nodeB.getWriteEffectsSet();
 525                 Set<SESEEffectsKey> readEffectsSet = nodeB.getReadEffectsSet();
 526
 527                 int conflictType = 0;
 528
 529                 if (writeEffectsSet != null) {
 530                         Iterator<SESEEffectsKey> writeIter = writeEffectsSet.iterator();
 531                         while (writeIter.hasNext()) {
 532                                 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIter
 533                                                 .next();
 534                                 String writeHeapRegionID = seseEffectsKey.getHRNUniqueId();
 535                                 String writeFieldName = seseEffectsKey.getFieldDescriptor();
 536
 537                                 HashSet<HeapRegionNode> stallSiteHRNSet = nodeA.getHRNSet();
 538                                 for (Iterator iterator = stallSiteHRNSet.iterator(); iterator
 539                                                 .hasNext();) {
 540                                         HeapRegionNode stallHRN = (HeapRegionNode) iterator.next();
 541                                         if (stallHRN.getGloballyUniqueIdentifier().equals(
 542                                                         writeHeapRegionID)) {
 543                                                 // check whether there are read or write effects of
 544                                                 // stall sites
 545                                                 HashSet<Effect> effectSet = stallSite.getEffectSet();
 546                                                 for (Iterator iterator2 = effectSet.iterator(); iterator2
 547                                                                 .hasNext();) {
 548                                                         Effect effect = (Effect) iterator2.next();
 549                                                         String stallEffectfieldName = effect.getField();
 550
 551                                                         if (stallEffectfieldName.equals(writeFieldName)) {
 552                                                                 int newType = determineConflictType(nodeA,
 553                                                                                 effect, nodeB, seseEffectsKey);
 554                                                                 if (newType > conflictType) {
 555                                                                         // coarse-grain conflict overrides
 556                                                                         // fine-grain conflict
 557                                                                         conflictType = newType;
 558                                                                 }
 559                                                         }
 560                                                 }
 561                                         }
 562                                 }
 563
 564                         }
 565                 }
 566
 567                 if (readEffectsSet != null) {
 568                         Iterator<SESEEffectsKey> readIter = readEffectsSet.iterator();
 569                         while (readIter.hasNext()) {
 570                                 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) readIter
 571                                                 .next();
 572                                 String readHeapRegionID = seseEffectsKey.getHRNUniqueId();
 573                                 String readFieldName = seseEffectsKey.getFieldDescriptor();
 574
 575                                 HashSet<HeapRegionNode> stallSiteHRNSet = nodeA.getHRNSet();
 576                                 for (Iterator iterator = stallSiteHRNSet.iterator(); iterator
 577                                                 .hasNext();) {
 578                                         HeapRegionNode stallHRN = (HeapRegionNode) iterator.next();
 579                                         if (stallHRN.getGloballyUniqueIdentifier().equals(
 580                                                         readHeapRegionID)) {
 581
 582                                                 HashSet<Effect> effectSet = stallSite.getEffectSet();
 583                                                 for (Iterator iterator2 = effectSet.iterator(); iterator2
 584                                                                 .hasNext();) {
 585                                                         Effect effect = (Effect) iterator2.next();
 586                                                         String stallEffectfieldName = effect.getField();
 587
 588                                                         if (effect.getEffectType().equals(
 589                                                                         StallSite.WRITE_EFFECT)) {
 590                                                                 if (stallEffectfieldName.equals(readFieldName)) {
 591                                                                         int newType = determineConflictType(nodeA,
 592                                                                                         effect, nodeB, seseEffectsKey);
 593                                                                         if (newType > conflictType) {
 594                                                                                 // coarse-grain conflict overrides
 595                                                                                 // fine-grain conflict
 596                                                                                 conflictType = newType;
 597                                                                         }
 598                                                                 }
 599                                                         }
 600                                                 }
 601                                         }
 602                                 }
 603                         }
 604                 }
 605 //System.out.println("%%%%%%%%%%%%%% RETURN conflictType="+conflictType);
 606                 return conflictType;
 607         }
 608
 609         private int calculateConflictType(LiveInNode nodeA, LiveInNode nodeB) {
 610
 611                 Set<SESEEffectsKey> readEffectsSetA = nodeA.getReadEffectsSet();
 612                 Set<SESEEffectsKey> writeEffectsSetA = nodeA.getWriteEffectsSet();
 613                 Set<SESEEffectsKey> strongUpdateSetA = nodeA.getStrongUpdateSet();
 614
 615                 Set<SESEEffectsKey> readEffectsSetB = nodeB.getReadEffectsSet();
 616                 Set<SESEEffectsKey> writeEffectsSetB = nodeB.getWriteEffectsSet();
 617                 Set<SESEEffectsKey> strongUpdateSetB = nodeB.getStrongUpdateSet();
 618
 619                 int conflictType = 0;
 620
 621                 // if node A has write effects on reading/writing regions of node B
 622                 if (writeEffectsSetA != null) {
 623                         Iterator<SESEEffectsKey> writeIterA = writeEffectsSetA.iterator();
 624                         while (writeIterA.hasNext()) {
 625                                 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIterA
 626                                                 .next();
 627                                 String writeHeapRegionID = seseEffectsKey.getHRNUniqueId();
 628                                 String writeFieldName = seseEffectsKey.getFieldDescriptor();
 629
 630                                 if (readEffectsSetB != null) {
 631
 632                                         Iterator<SESEEffectsKey> readIterB = readEffectsSetB
 633                                                         .iterator();
 634                                         while (readIterB.hasNext()) {
 635                                                 SESEEffectsKey readingEffect = (SESEEffectsKey) readIterB
 636                                                                 .next();
 637
 638                                                 if (readingEffect.getHRNUniqueId().equals(
 639                                                                 writeHeapRegionID)
 640                                                                 && readingEffect.getFieldDescriptor().equals(
 641                                                                                 writeFieldName)) {
 642                                                         int newType = determineConflictType(nodeA,
 643                                                                         seseEffectsKey, nodeB, readingEffect);
 644                                                         if (newType > conflictType) {
 645                                                                 // coarse-grain conflict overrides fine-grain
 646                                                                 // conflict
 647                                                                 conflictType = newType;
 648                                                         }
 649                                                 }
 650                                         }
 651
 652                                 }
 653
 654                                 if (writeEffectsSetB != null) {
 655                                         Iterator<SESEEffectsKey> writeIterB = writeEffectsSetB
 656                                                         .iterator();
 657                                         while (writeIterB.hasNext()) {
 658                                                 SESEEffectsKey writingEffect = (SESEEffectsKey) writeIterB
 659                                                                 .next();
 660
 661                                                 if (writingEffect.getHRNUniqueId().equals(
 662                                                                 writeHeapRegionID)
 663                                                                 && writingEffect.getFieldDescriptor().equals(
 664                                                                                 writeFieldName)) {
 665                                                         int newType = determineConflictType(nodeA,
 666                                                                         seseEffectsKey, nodeB, writingEffect);
 667                                                         if (newType > conflictType) {
 668                                                                 // coarse-grain conflict overrides fine-grain
 669                                                                 // conflict
 670                                                                 conflictType = newType;
 671                                                         }
 672                                                 }
 673
 674                                         }
 675                                 }
 676
 677                         }
 678                 }
 679
 680                 // if node B has write effects on reading regions of node A
 681                 if (writeEffectsSetB != null) {
 682                         Iterator<SESEEffectsKey> writeIterB = writeEffectsSetB.iterator();
 683                         while (writeIterB.hasNext()) {
 684                                 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIterB
 685                                                 .next();
 686
 687                                 // if (!hasStrongUpdate(seseEffectsKey, strongUpdateSetB)) {
 688
 689                                 String writeHeapRegionID = seseEffectsKey.getHRNUniqueId();
 690                                 String writeFieldName = seseEffectsKey.getFieldDescriptor();
 691
 692                                 if (readEffectsSetA != null) {
 693                                         Iterator<SESEEffectsKey> readIterA = readEffectsSetA
 694                                                         .iterator();
 695                                         while (readIterA.hasNext()) {
 696                                                 SESEEffectsKey readingEffect = (SESEEffectsKey) readIterA
 697                                                                 .next();
 698
 699                                                 if (readingEffect.getHRNUniqueId().equals(
 700                                                                 writeHeapRegionID)
 701                                                                 && readingEffect.getFieldDescriptor().equals(
 702                                                                                 writeFieldName)) {
 703                                                         int newType = determineConflictType(nodeA,
 704                                                                         readingEffect, nodeB, seseEffectsKey);
 705                                                         if (newType > conflictType) {
 706                                                                 // coarse-grain conflict overrides fine-grain
 707                                                                 // conflict
 708                                                                 conflictType = newType;
 709                                                         }
 710                                                 }
 711
 712                                         }
 713                                 }
 714
 715                                 if (writeEffectsSetA != null) {
 716                                         Iterator<SESEEffectsKey> writeIterA = writeEffectsSetA
 717                                                         .iterator();
 718                                         while (writeIterA.hasNext()) {
 719                                                 SESEEffectsKey writingEffect = (SESEEffectsKey) writeIterA
 720                                                                 .next();
 721
 722                                                 if (writingEffect.getHRNUniqueId().equals(
 723                                                                 writeHeapRegionID)
 724                                                                 && writingEffect.getFieldDescriptor().equals(
 725                                                                                 writeFieldName)) {
 726                                                         int newType = determineConflictType(nodeA,
 727                                                                         writingEffect, nodeB, seseEffectsKey);
 728                                                         if (newType > conflictType) {
 729                                                                 // coarse-grain conflict overrides fine-grain
 730                                                                 // conflict
 731                                                                 conflictType = newType;
 732                                                         }
 733                                                 }
 734
 735                                         }
 736                                 }
 737
 738                         }
 739                 }
 740                 return conflictType;
 741         }
 742
 743         private Set<HeapRegionNode> getSameHeapRoot(Set<HeapRegionNode> setA,
 744                         Set<HeapRegionNode> setB) {
 745
 746                 Set<HeapRegionNode> retSet = new HashSet<HeapRegionNode>();
 747
 748                 if (compareHRNSet(setA, setB)) {
 749                         for (Iterator iterator = setA.iterator(); iterator.hasNext();) {
 750                                 HeapRegionNode heapRegionNode = (HeapRegionNode) iterator
 751                                                 .next();
 752                                 String gID = heapRegionNode.getGloballyUniqueIdentifier();
 753                                 for (Iterator iterator2 = setB.iterator(); iterator2.hasNext();) {
 754                                         HeapRegionNode heapRegionNode2 = (HeapRegionNode) iterator2
 755                                                         .next();
 756                                         if (heapRegionNode2.getGloballyUniqueIdentifier().equals(
 757                                                         gID)) {
 758                                                 retSet.add(heapRegionNode2);
 759                                         }
 760                                 }
 761                         }
 762                 }
 763
 764                 return retSet;
 765
 766         }
 767
 768         private boolean isReachableFrom(HeapRegionNode root1, HeapRegionNode root2,
 769                         ReachabilitySet rset) {
 770
 771                 boolean reachable=false;
 772
 773                 TokenTuple h1 = new TokenTuple(root1.getID(), !root1.isSingleObject(),
 774                                 TokenTuple.ARITY_ONE).makeCanonical();
 775
 776                 TokenTuple h1plus = new TokenTuple(root1.getID(), !root1
 777                                 .isSingleObject(), TokenTuple.ARITY_ONEORMORE).makeCanonical();
 778
 779                 TokenTuple h1star = new TokenTuple(root1.getID(), !root1
 780                                 .isSingleObject(), TokenTuple.ARITY_ZEROORMORE).makeCanonical();
 781
 782                 TokenTuple h2 = new TokenTuple(root2.getID(), !root2.isSingleObject(),
 783                                 TokenTuple.ARITY_ONE).makeCanonical();
 784
 785                 TokenTuple h2plus = new TokenTuple(root2.getID(), !root2
 786                                 .isSingleObject(), TokenTuple.ARITY_ONEORMORE).makeCanonical();
 787
 788                 TokenTuple h2star = new TokenTuple(root2.getID(), !root2
 789                                 .isSingleObject(), TokenTuple.ARITY_ZEROORMORE).makeCanonical();
 790
 791                  // only do this one if they are different tokens
 792             if( h1 != h2 &&
 793                         rset.containsTupleSetWithBoth(h1,     h2) ) {
 794                 reachable = true;
 795             }
 796             if( rset.containsTupleSetWithBoth(h1plus, h2) ) {
 797                 reachable = true;
 798             }
 799             if( rset.containsTupleSetWithBoth(h1star, h2) ) {
 800                 reachable = true;
 801             }
 802             if( rset.containsTupleSetWithBoth(h1,     h2plus) ) {
 803                 reachable = true;
 804             }
 805             if( rset.containsTupleSetWithBoth(h1plus, h2plus) ) {
 806                 reachable = true;
 807             }
 808             if( rset.containsTupleSetWithBoth(h1star, h2plus) ) {
 809                 reachable = true;
 810             }
 811             if( rset.containsTupleSetWithBoth(h1,     h2star) ) {
 812                 reachable = true;
 813             }
 814             if( rset.containsTupleSetWithBoth(h1plus, h2star) ) {
 815                 reachable = true;
 816             }
 817             if( rset.containsTupleSetWithBoth(h1star, h2star) ) {
 818                 reachable = true;
 819             }
 820
 821                 return reachable;
 822
 823         }
 824
 825         private int determineConflictType(StallSiteNode stallSiteNodeA,
 826                         Effect effect, LiveInNode liveInNodeB,
 827                         SESEEffectsKey effectB) {
 828
 829                 Set<HeapRegionNode> liveInHrnSetA = stallSiteNodeA.getStallSite().getHRNSet();
 830                 Set<HeapRegionNode> liveInHrnSetB = liveInNodeB.getHRNSet();
 831
 832                 // check whether alloc site is reached from both  heap roots
 833                 boolean isDisjoint=true;
 834                 HeapRegionNode effectHrn=og.gid2hrn.get(effectB.getHRNUniqueId());
 835                 if(effectHrn.isSingleObject()){
 836                         for (Iterator iterator = liveInHrnSetA.iterator(); iterator.hasNext();) {
 837                                 HeapRegionNode r1 = (HeapRegionNode) iterator.next();
 838                                 for (Iterator iterator2 = liveInHrnSetB.iterator(); iterator2.hasNext();) {
 839                                         HeapRegionNode r2 = (HeapRegionNode) iterator2.next();
 840                                         r1=og.gid2hrn.get(r1.getGloballyUniqueIdentifier());
 841                                         r2=og.gid2hrn.get(r2.getGloballyUniqueIdentifier());
 842                                         if(isReachableFrom(r1,r2,effectB.getRSet())){
 843                                                 isDisjoint=false;
 844                                         }
 845                                 }
 846                         }
 847                         if(isDisjoint){
 848                                 return ConflictEdge.NON_WRITE_CONFLICT;
 849                         }
 850                 }
 851
 852                 /*
 853                 HeapRegionNode r1=liveInHrnSetA.iterator().next();
 854                 HeapRegionNode r2=liveInHrnSetB.iterator().next();
 855
 856                 r1=og.gid2hrn.get(r1.getGloballyUniqueIdentifier());
 857                 r2=og.gid2hrn.get(r2.getGloballyUniqueIdentifier());
 858
 859                 System.out.println("r1="+r1);
 860                 System.out.println("r2="+r2);
 861                 System.out.println("effectB="+effectB.getRSet());
 862                 System.out.println("###STALL calculateConflictType2");
 863                 if(!isReachableFrom(r1,r2,effectB.getRSet())){
 864                         System.out.println("###STALL calculateConflictType3");
 865                         return ConflictEdge.NON_WRITE_CONFLICT;
 866                 }
 867                 */
 868                 Set<HeapRegionNode> entryHRNSet = getSameHeapRoot(liveInHrnSetA,
 869                                 liveInHrnSetB);
 870                 if (entryHRNSet.size() == 0) {
 871                         return ConflictEdge.COARSE_GRAIN_EDGE;
 872                 }
 873
 874                 for (Iterator iterator = entryHRNSet.iterator(); iterator.hasNext();) {
 875                         HeapRegionNode hrn = (HeapRegionNode) iterator.next();
 876
 877                         String entryIdentifier = hrn.getGloballyUniqueIdentifier();
 878                         HeapRegionNode entryHRN = og.gid2hrn.get(entryIdentifier);
 879
 880                         TokenTuple h1 = new TokenTuple(entryHRN.getID(), !entryHRN
 881                                         .isSingleObject(), TokenTuple.ARITY_ONE).makeCanonical();
 882
 883                         TokenTuple h1star = new TokenTuple(entryHRN.getID(), true,
 884                                         TokenTuple.ARITY_ONEORMORE).makeCanonical();
 885
 886                         if (effectB.getRSet().containsTuple(h1star)) {
 887                                 return ConflictEdge.COARSE_GRAIN_EDGE;
 888                         }else if (effectB.getRSet().containsTuple(h1)) {
 889                                 // rechability states contain heap root with arity 1
 890                                 return ConflictEdge.FINE_GRAIN_EDGE;
 891                         }
 892                 }
 893                 return ConflictEdge.NON_WRITE_CONFLICT;
 894         }
 895
 896         private int determineConflictType(LiveInNode liveInNodeA,
 897                         SESEEffectsKey effectA, LiveInNode liveInNodeB,
 898                         SESEEffectsKey effectB) {
 899
 900                 if (liveInNodeA.getSESEIdentifier() == liveInNodeB.getSESEIdentifier()) {
 901                         return ConflictEdge.NON_WRITE_CONFLICT;
 902                 }
 903
 904                 Set<HeapRegionNode> liveInHrnSetA = liveInNodeA.getHRNSet();
 905                 Set<HeapRegionNode> liveInHrnSetB = liveInNodeB.getHRNSet();
 906
 907                 // check whether alloc site is reached from both  heap roots
 908                 boolean isDisjoint=true;
 909                 HeapRegionNode effectHrn=og.gid2hrn.get(effectB.getHRNUniqueId());
 910                 if(effectHrn.isSingleObject()){
 911                         for (Iterator iterator = liveInHrnSetA.iterator(); iterator.hasNext();) {
 912                                 HeapRegionNode r1 = (HeapRegionNode) iterator.next();
 913                                 for (Iterator iterator2 = liveInHrnSetB.iterator(); iterator2.hasNext();) {
 914                                         HeapRegionNode r2 = (HeapRegionNode) iterator2.next();
 915                                         r1=og.gid2hrn.get(r1.getGloballyUniqueIdentifier());
 916                                         r2=og.gid2hrn.get(r2.getGloballyUniqueIdentifier());
 917
 918                                         if(isReachableFrom(r1,r2,effectB.getRSet())){
 919                                                 isDisjoint=false;
 920                                         }else{
 921                                         }
 922                                 }
 923                         }
 924                         if(isDisjoint){
 925                                 return ConflictEdge.NON_WRITE_CONFLICT;
 926                         }
 927                 }
 928
 929                 /*
 930                 HeapRegionNode r1=liveInHrnSetA.iterator().next();
 931                 HeapRegionNode r2=liveInHrnSetB.iterator().next();
 932
 933 //              r1=og.gid2hrn.get(r1.getGloballyUniqueIdentifier());
 934 //              r2=og.gid2hrn.get(r2.getGloballyUniqueIdentifier());
 935                 System.out.println("@@r1="+r1);
 936                 System.out.println("@@r2="+r2);
 937                 System.out.println("@@effectB="+effectA.getRSet());
 938
 939                 if(!isReachableFrom(r1,r2,effectA.getRSet())){
 940                         // two heap root are disjoint
 941                         return ConflictEdge.NON_WRITE_CONFLICT;
 942                 }
 943                 */
 944
 945                 Set<HeapRegionNode> entryHRNSet = getSameHeapRoot(liveInHrnSetA,
 946                                 liveInHrnSetB);
 947                 if (entryHRNSet.size() == 0 ) {
 948                         return ConflictEdge.COARSE_GRAIN_EDGE;
 949                 }
 950                 if(entryHRNSet.size()!=liveInHrnSetA.size() || entryHRNSet.size()!=liveInHrnSetB.size()){
 951                         return ConflictEdge.COARSE_GRAIN_EDGE;
 952                 }
 953
 954                 int count=0;
 955                 for (Iterator iterator = entryHRNSet.iterator(); iterator.hasNext();) {
 956                         HeapRegionNode hrn = (HeapRegionNode) iterator.next();
 957                         if(hrn.getType()!=null && hrn.getType().isImmutable()){
 958                                 count++;
 959                         }
 960                 }
 961                 if(count==entryHRNSet.size()){
 962                         return ConflictEdge.FINE_GRAIN_EDGE;
 963                 }
 964
 965                 for (Iterator iterator = entryHRNSet.iterator(); iterator.hasNext();) {
 966                         HeapRegionNode hrn = (HeapRegionNode) iterator.next();
 967
 968                         String entryIdentifier = hrn.getGloballyUniqueIdentifier();
 969                         HeapRegionNode entryHRN = og.gid2hrn.get(entryIdentifier);
 970
 971                         TokenTuple h1 = new TokenTuple(entryHRN.getID(), !entryHRN
 972                                         .isSingleObject(), TokenTuple.ARITY_ONE).makeCanonical();
 973
 974                         TokenTuple h1star = new TokenTuple(entryHRN.getID(), true,
 975                                         TokenTuple.ARITY_ONEORMORE).makeCanonical();
 976
 977                         if (effectA.getRSet().containsTuple(h1star)) {
 978                                 return ConflictEdge.COARSE_GRAIN_EDGE;
 979                         } else if (effectA.getRSet().containsTuple(h1)) {
 980                                 // rechability states contain heap root with arity 1
 981                                 return ConflictEdge.FINE_GRAIN_EDGE;
 982                         }
 983
 984                 }
 985
 986                 return ConflictEdge.NON_WRITE_CONFLICT;
 987
 988         }
 989
 990         private int calculateSelfConflictType(LiveInNode liveInNode) {
 991
 992                 // if strong update effect exists, it conflicts every effects of objects that are reachable from same heap root
 993                 Set<SESEEffectsKey> strongUpdateSet = liveInNode.getStrongUpdateSet();
 994                 if(strongUpdateSet!=null && strongUpdateSet.size()>0){
 995                         return ConflictEdge.FINE_GRAIN_EDGE;
 996                 }
 997
 998                 if (liveInNode.getWriteEffectsSet() != null
 999                                 && liveInNode.getWriteEffectsSet().size() > 0) {
1000
1001                         Set<SESEEffectsKey> writeEffectsSet=liveInNode.getWriteEffectsSet();
1002
1003                         int immuntableCount = 0;
1004                         for (Iterator<HeapRegionNode> iterator = liveInNode.getHRNSet()
1005                                         .iterator(); iterator.hasNext();) {
1006                                 HeapRegionNode root = iterator.next();
1007                                 if(root.getType()!=null && root.getType().isImmutable()){
1008                                         immuntableCount++;
1009                                 }
1010                         }
1011                         if (immuntableCount == liveInNode.getHRNSet().size()) {
1012                                 // in this case, heap root is a parameter heap region
1013                                 return ConflictEdge.FINE_GRAIN_EDGE;
1014                         }
1015
1016
1017                         int paramCount = 0;
1018                         for (Iterator<HeapRegionNode> iterator = liveInNode.getHRNSet()
1019                                         .iterator(); iterator.hasNext();) {
1020                                 HeapRegionNode root = iterator.next();
1021                                 if (root.isParameter()) {
1022                                         paramCount++;
1023                                 }
1024                         }
1025
1026                         if (paramCount == liveInNode.getHRNSet().size()) {
1027                                 // in this case, heap root is a parameter heap region
1028                                 return ConflictEdge.FINE_GRAIN_EDGE;
1029                         }
1030
1031                         if (liveInNode.getHRNSet().size()==1) {
1032                                 HeapRegionNode hrn = liveInNode.getHRNSet().iterator().next();
1033                                         String entryIdentifier = hrn.getGloballyUniqueIdentifier();
1034                                         HeapRegionNode entryHRN = og.gid2hrn.get(entryIdentifier);
1035
1036                                         boolean containsStar=false;
1037                                         for (Iterator iterator = writeEffectsSet.iterator(); iterator
1038                                                         .hasNext();) {
1039                                                 SESEEffectsKey effect = (SESEEffectsKey) iterator.next();
1040                                                 TokenTuple h1 = new TokenTuple(entryHRN.getID(), !entryHRN
1041                                                                 .isSingleObject(), TokenTuple.ARITY_ONE).makeCanonical();
1042                                                 TokenTuple h1star = new TokenTuple(entryHRN.getID(), true, TokenTuple.ARITY_ZEROORMORE).makeCanonical();
1043                                                 if (effect.getRSet().containsTuple(h1star)) {
1044                                                         // rechability states contain heap root with arity star
1045                                                         containsStar=true;
1046                                                 }
1047                                         }
1048                                         if(containsStar){
1049                                                 return ConflictEdge.COARSE_GRAIN_EDGE;
1050                                         }else{
1051                                                 return ConflictEdge.FINE_GRAIN_EDGE;
1052                                         }
1053                         }else{
1054                                 return ConflictEdge.COARSE_GRAIN_EDGE;
1055                         }
1056
1057
1058                         /*
1059                         boolean containsAllTuple=true;
1060                         for (Iterator iterator2 = writeEffectsSet.iterator(); iterator2
1061                                         .hasNext();) {
1062                                 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator2
1063                                                 .next();
1064                                 ReachabilitySet rset = seseEffectsKey.getRSet();
1065                                 Iterator<TokenTupleSet> tsetIter=rset.iterator();
1066                                 int countNotContained=0;
1067                                 while (tsetIter.hasNext()) {
1068                                         TokenTupleSet tokenTupleSet = (TokenTupleSet) tsetIter
1069                                                         .next();
1070                                         boolean found=true;
1071                                         for (Iterator iterator = rootIDSet.iterator(); iterator
1072                                                         .hasNext();) {
1073                                                 Integer rootID = (Integer) iterator.next();
1074                                                 if(tokenTupleSet.containsToken(rootID)==null){
1075                                                         found=false;
1076                                                 }
1077                                         }
1078                                         if(!found){
1079                                                 countNotContained++;
1080                                         }
1081                                 }
1082                                 if(countNotContained==rset.size()){
1083                                         containsAllTuple=false;
1084                                 }
1085                         }
1086
1087                         if (containsAllTuple && liveInNode.getHRNSet().size() > 1) {
1088                                 return ConflictEdge.COARSE_GRAIN_EDGE;
1089                         } else {
1090                                 return ConflictEdge.FINE_GRAIN_EDGE;
1091                         }
1092                         */
1093
1094
1095
1096                 }
1097
1098                 return ConflictEdge.NON_WRITE_CONFLICT;
1099
1100         }
1101
1102         public void analyzePossibleConflicts(Set<String> analyzedIDSet,
1103                         ConflictNode currentNode) {
1104
1105                 // compare with all nodes
1106                 // examine the case where self-edge exists
1107                 if (currentNode instanceof LiveInNode) {
1108                         LiveInNode liveInNode = (LiveInNode) currentNode;
1109                         int conflictType=calculateSelfConflictType(liveInNode);
1110                         if(conflictType>0){
1111                                 addConflictEdge(conflictType, currentNode,
1112                                                 currentNode);
1113                         }
1114                 }
1115
1116                 Set<Entry<String, ConflictNode>> set = id2cn.entrySet();
1117                 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1118                         Entry<String, ConflictNode> entry = (Entry<String, ConflictNode>) iterator
1119                                         .next();
1120
1121                         String entryNodeID = entry.getKey();
1122                         ConflictNode entryNode = entry.getValue();
1123
1124                         if ((!currentNode.getID().equals(entryNodeID))
1125                                         && !(analyzedIDSet.contains(currentNode.getID()
1126                                                         + entryNodeID) || analyzedIDSet
1127                                                         .contains(entryNodeID + currentNode.getID()))) {
1128
1129                                 if (currentNode instanceof StallSiteNode
1130                                                 && entryNode instanceof LiveInNode) {
1131
1132                                         int conflictType = calculateConflictType((StallSiteNode) currentNode,   (LiveInNode) entryNode);
1133                                         if (conflictType > 0) {
1134                                                 addConflictEdge(conflictType, currentNode, entryNode);
1135                                         }
1136
1137                                         analyzedIDSet.add(currentNode.getID() + entryNodeID);
1138
1139                                 } else if (currentNode instanceof LiveInNode
1140                                                 && entryNode instanceof LiveInNode) {
1141
1142                                         int conflictType = calculateConflictType(
1143                                                         (LiveInNode) currentNode, (LiveInNode) entryNode);
1144                                         if (conflictType > 0) {
1145                                                 addConflictEdge(conflictType, currentNode, entryNode);
1146                                         }
1147                                         analyzedIDSet.add(currentNode.getID() + entryNodeID);
1148                                 }
1149
1150                         }
1151
1152                 }
1153
1154         }
1155
1156 }
1157
1158 class ConflictEdge {
1159
1160         private ConflictNode u;
1161         private ConflictNode v;
1162         private int type;
1163
1164         public static final int NON_WRITE_CONFLICT = 0;
1165         public static final int FINE_GRAIN_EDGE = 1;
1166         public static final int COARSE_GRAIN_EDGE = 2;
1167
1168         public ConflictEdge(ConflictNode u, ConflictNode v, int type) {
1169                 this.u = u;
1170                 this.v = v;
1171                 this.type = type;
1172         }
1173
1174         public String toGraphEdgeString() {
1175                 if (type == FINE_GRAIN_EDGE) {
1176                         return "\"F_CONFLICT\"";
1177                 } else if (type == COARSE_GRAIN_EDGE) {
1178                         return "\"C_CONFLICT\"";
1179                 } else {
1180                         return "CONFLICT\"";
1181                 }
1182         }
1183
1184         public ConflictNode getVertexU() {
1185                 return u;
1186         }
1187
1188         public ConflictNode getVertexV() {
1189                 return v;
1190         }
1191
1192         public int getType() {
1193                 return type;
1194         }
1195
1196         public String toString() {
1197                 return getVertexU() + "-" + getVertexV();
1198         }
1199
1200 }