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.HashSet;
   7 import java.util.Hashtable;
   8 import java.util.Iterator;
   9 import java.util.Set;
  10 import java.util.Map.Entry;
  11
  12 import Analysis.OwnershipAnalysis.HeapRegionNode;
  13 import IR.Flat.FlatMethod;
  14 import IR.Flat.FlatSESEEnterNode;
  15 import IR.Flat.TempDescriptor;
  16
  17 public class ConflictGraph {
  18
  19         static private int uniqueCliqueIDcount = 100;
  20
  21         public Hashtable<String, ConflictNode> id2cn;
  22
  23         public ConflictGraph() {
  24                 id2cn = new Hashtable<String, ConflictNode>();
  25         }
  26
  27         public void addPseudoEdgeBetweenReadOnlyNode() {
  28
  29                 Collection<ConflictNode> conflictNodes = id2cn.values();
  30                 Set<String> analyzedIDSet = new HashSet<String>();
  31
  32                 for (Iterator iterator = conflictNodes.iterator(); iterator.hasNext();) {
  33                         ConflictNode conflictNode = (ConflictNode) iterator.next();
  34                         if (isReadOnly(conflictNode)
  35                                         && conflictNode.getEdgeSet().size() > 0) {
  36
  37                                 for (Iterator<ConflictNode> iter = id2cn.values().iterator(); iter
  38                                                 .hasNext();) {
  39                                         ConflictNode nextNode = iter.next();
  40
  41                                         if (!conflictNode.equals(nextNode)
  42                                                         && nextNode.getEdgeSet().size() > 0
  43                                                         && !analyzedIDSet.contains(conflictNode.getID()
  44                                                                         + nextNode.getID())
  45                                                         && !analyzedIDSet.contains(nextNode.getID()
  46                                                                         + conflictNode.getID())
  47                                                         && isReadOnly(nextNode)) {
  48                                                 if (hasSameReadEffects(conflictNode, nextNode)) {
  49                                                         addConflictEdge(ConflictEdge.PSEUDO_EDGE,
  50                                                                         conflictNode, nextNode);
  51                                                 }
  52                                         }
  53                                         analyzedIDSet.add(conflictNode.getID() + nextNode.getID());
  54                                 }
  55                         }
  56                 }
  57         }
  58
  59         private boolean hasSameReadEffects(ConflictNode nodeA, ConflictNode nodeB) {
  60
  61                 StallSiteNode stallSiteNode = null;
  62                 LiveInNode liveInNode = null;
  63
  64                 if (nodeA instanceof StallSiteNode && nodeB instanceof StallSiteNode) {
  65                         return hasSameReadEffects((StallSiteNode) nodeA,
  66                                         (StallSiteNode) nodeB);
  67                 }
  68
  69                 if (nodeA instanceof StallSiteNode) {
  70                         stallSiteNode = (StallSiteNode) nodeA;
  71                 } else {
  72                         liveInNode = (LiveInNode) nodeA;
  73                 }
  74
  75                 if (nodeB instanceof StallSiteNode) {
  76                         stallSiteNode = (StallSiteNode) nodeB;
  77                 } else {
  78                         liveInNode = (LiveInNode) nodeB;
  79                 }
  80
  81                 if (stallSiteNode != null) {
  82                         return hasSameReadEffects(stallSiteNode, liveInNode);
  83                 } else {
  84                         return hasSameReadEffects((LiveInNode) nodeA, (LiveInNode) nodeB);
  85                 }
  86
  87         }
  88
  89         private boolean hasSameReadEffects(LiveInNode linA, LiveInNode linB) {
  90
  91                 Set<SESEEffectsKey> readSetA = linA.getReadEffectsSet();
  92                 Set<SESEEffectsKey> readSetB = linB.getReadEffectsSet();
  93
  94                 boolean returnValue = true;
  95                 for (Iterator iterator = readSetA.iterator(); iterator.hasNext();) {
  96                         SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator.next();
  97
  98                         for (Iterator iterator2 = readSetB.iterator(); iterator2.hasNext();) {
  99                                 SESEEffectsKey opr = (SESEEffectsKey) iterator2.next();
 100                                 if (!(seseEffectsKey.getHRNUniqueId().equals(
 101                                                 opr.getHRNUniqueId()) && seseEffectsKey
 102                                                 .getFieldDescriptor().equals(opr.getFieldDescriptor()))) {
 103                                         returnValue = false;
 104                                 }
 105                         }
 106                 }
 107                 return returnValue;
 108         }
 109
 110         private boolean hasSameReadEffects(StallSiteNode ssnA, StallSiteNode ssnB) {
 111
 112                 HashSet<Effect> effectSetA = ssnA.getStallSite().getEffectSet();
 113                 HashSet<HeapRegionNode> nodeSetA = ssnA.getStallSite().getHRNSet();
 114                 HashSet<Effect> effectSetB = ssnB.getStallSite().getEffectSet();
 115                 HashSet<HeapRegionNode> nodeSetB = ssnA.getStallSite().getHRNSet();
 116                 boolean returnValue = true;
 117
 118                 for (Iterator iteratorA = effectSetA.iterator(); iteratorA.hasNext();) {
 119                         Effect effectKeyA = (Effect) iteratorA.next();
 120                         for (Iterator iterator2A = nodeSetA.iterator(); iterator2A
 121                                         .hasNext();) {
 122                                 HeapRegionNode hrnA = (HeapRegionNode) iterator2A.next();
 123
 124                                 for (Iterator iteratorB = effectSetB.iterator(); iteratorB
 125                                                 .hasNext();) {
 126                                         Effect effectKeyB = (Effect) iteratorB.next();
 127                                         for (Iterator iterator2B = nodeSetB.iterator(); iterator2B
 128                                                         .hasNext();) {
 129                                                 HeapRegionNode hrnB = (HeapRegionNode) iterator2B
 130                                                                 .next();
 131
 132                                                 if (!(hrnA.getGloballyUniqueIdentifier().equals(
 133                                                                 hrnB.getGloballyUniqueIdentifier()) && effectKeyA
 134                                                                 .getField().equals(effectKeyB.getField()))) {
 135                                                         returnValue = false;
 136                                                 }
 137                                         }
 138                                 }
 139
 140                         }
 141
 142                 }
 143
 144                 return returnValue;
 145         }
 146
 147         private boolean hasSameReadEffects(StallSiteNode ssnA, LiveInNode linB) {
 148
 149                 HashSet<Effect> effectSetA = ssnA.getStallSite().getEffectSet();
 150                 HashSet<HeapRegionNode> nodeSetA = ssnA.getStallSite().getHRNSet();
 151
 152                 Set<SESEEffectsKey> readSetB = linB.getReadEffectsSet();
 153                 if (readSetB == null) {
 154                         return false;
 155                 }
 156
 157                 boolean returnValue = true;
 158
 159                 for (Iterator iterator = effectSetA.iterator(); iterator.hasNext();) {
 160                         Effect effectKey = (Effect) iterator.next();
 161                         for (Iterator iterator2 = nodeSetA.iterator(); iterator2.hasNext();) {
 162                                 HeapRegionNode hrn = (HeapRegionNode) iterator2.next();
 163
 164                                 for (Iterator iterator3 = readSetB.iterator(); iterator3
 165                                                 .hasNext();) {
 166                                         SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator3
 167                                                         .next();
 168
 169                                         if (!(seseEffectsKey.getHRNUniqueId().equals(
 170                                                         hrn.getGloballyUniqueIdentifier()) && seseEffectsKey
 171                                                         .getFieldDescriptor().equals(effectKey.getField()))) {
 172                                                 returnValue = false;
 173                                         }
 174
 175                                 }
 176
 177                         }
 178                 }
 179
 180                 return returnValue;
 181         }
 182
 183         private boolean isReadOnly(ConflictNode node) {
 184
 185                 if (node instanceof StallSiteNode) {
 186                         StallSiteNode stallSiteNode = (StallSiteNode) node;
 187                         HashSet<Effect> effectSet = stallSiteNode.getStallSite()
 188                                         .getEffectSet();
 189                         for (Iterator iterator = effectSet.iterator(); iterator.hasNext();) {
 190                                 Effect effect = (Effect) iterator.next();
 191                                 if (effect.getEffectType().equals(StallSite.WRITE_EFFECT)) {
 192                                         return false;
 193                                 }
 194                         }
 195                 } else {
 196                         LiveInNode liveInNode = (LiveInNode) node;
 197                         Set<SESEEffectsKey> writeEffectSet = liveInNode
 198                                         .getWriteEffectsSet();
 199                         if (writeEffectSet != null && writeEffectSet.size() > 0) {
 200                                 return false;
 201                         }
 202                 }
 203
 204                 return true;
 205         }
 206
 207         public void analyzeConflicts() {
 208
 209                 Set<String> keySet = id2cn.keySet();
 210                 Set<String> analyzedIDSet = new HashSet<String>();
 211
 212                 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 213                         String nodeID = (String) iterator.next();
 214                         ConflictNode node = id2cn.get(nodeID);
 215                         analyzePossibleConflicts(analyzedIDSet, node);
 216                 }
 217         }
 218
 219         private boolean isWriteConflicts(StallSiteNode nodeA, LiveInNode nodeB) {
 220
 221                 boolean result = false;
 222                 StallSite stallSite = nodeA.getStallSite();
 223
 224                 Set<SESEEffectsKey> writeEffectsSet = nodeB.getWriteEffectsSet();
 225                 Set<SESEEffectsKey> readEffectsSet = nodeB.getReadEffectsSet();
 226
 227                 if (writeEffectsSet != null) {
 228                         Iterator<SESEEffectsKey> writeIter = writeEffectsSet.iterator();
 229                         while (writeIter.hasNext()) {
 230                                 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIter
 231                                                 .next();
 232                                 String writeHeapRegionID = seseEffectsKey.getHRNUniqueId();
 233                                 String writeFieldName = seseEffectsKey.getFieldDescriptor();
 234
 235                                 if(writeFieldName.length()>0){
 236                                         HashSet<HeapRegionNode> stallSiteHRNSet = nodeA.getHRNSet();
 237                                         for (Iterator iterator = stallSiteHRNSet.iterator(); iterator
 238                                                         .hasNext();) {
 239                                                 HeapRegionNode stallHRN = (HeapRegionNode) iterator.next();
 240                                                 if (stallHRN.getGloballyUniqueIdentifier().equals(
 241                                                                 writeHeapRegionID)) {
 242
 243                                                         // check whether there are read or write effects of
 244                                                         // stall sites
 245
 246                                                         HashSet<Effect> effectSet = stallSite.getEffectSet();
 247                                                         for (Iterator iterator2 = effectSet.iterator(); iterator2
 248                                                                         .hasNext();) {
 249                                                                 Effect effect = (Effect) iterator2.next();
 250                                                                 String stallEffectfieldName = effect.getField();
 251
 252                                                                 if (stallEffectfieldName.equals(writeFieldName)) {
 253                                                                         result = result | true;
 254                                                                 }
 255                                                         }
 256
 257                                                 }
 258                                         }
 259                                 }else{
 260                                         // no field name
 261
 262                                         HashSet<Effect> effectSet = stallSite.getEffectSet();
 263                                         for (Iterator iterator2 = effectSet.iterator(); iterator2
 264                                                         .hasNext();) {
 265                                                 Effect effect = (Effect) iterator2.next();
 266                                                 String stallEffectfieldName = effect.getField();
 267
 268                                                 if (stallEffectfieldName.length()==0 && nodeB.getTempDescriptor().equals(nodeA.getStallSite().getTdA())) {
 269                                                         result = result | true;
 270                                                 }
 271                                         }
 272
 273                                 }
 274
 275                         }
 276
 277                 }
 278
 279                 if (readEffectsSet != null) {
 280                         Iterator<SESEEffectsKey> readIter = readEffectsSet.iterator();
 281                         while (readIter.hasNext()) {
 282
 283                                 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) readIter
 284                                                 .next();
 285                                 String readHeapRegionID = seseEffectsKey.getHRNUniqueId();
 286                                 String readFieldName = seseEffectsKey.getFieldDescriptor();
 287
 288                                 if(readFieldName.length()>0){
 289                                         HashSet<HeapRegionNode> stallSiteHRNSet = nodeA.getHRNSet();
 290                                         for (Iterator iterator = stallSiteHRNSet.iterator(); iterator
 291                                                         .hasNext();) {
 292                                                 HeapRegionNode stallHRN = (HeapRegionNode) iterator.next();
 293                                                 if (stallHRN.getGloballyUniqueIdentifier().equals(
 294                                                                 readHeapRegionID)) {
 295
 296                                                         HashSet<Effect> effectSet = stallSite.getEffectSet();
 297                                                         for (Iterator iterator2 = effectSet.iterator(); iterator2
 298                                                                         .hasNext();) {
 299                                                                 Effect effect = (Effect) iterator2.next();
 300                                                                 String stallEffectfieldName = effect.getField();
 301
 302                                                                 if (effect.getEffectType().equals(
 303                                                                                 StallSite.WRITE_EFFECT)) {
 304                                                                         if (stallEffectfieldName.equals(readFieldName)) {
 305                                                                                 result = result | true;
 306                                                                         }
 307                                                                 }
 308
 309                                                         }
 310
 311                                                 }
 312
 313                                         }
 314                                 }else{
 315                                         //no field
 316                                         HashSet<Effect> effectSet = stallSite.getEffectSet();
 317                                         for (Iterator iterator2 = effectSet.iterator(); iterator2
 318                                                         .hasNext();) {
 319                                                 Effect effect = (Effect) iterator2.next();
 320                                                 String stallEffectfieldName = effect.getField();
 321
 322                                                 if (effect.getEffectType().equals(
 323                                                                 StallSite.WRITE_EFFECT)) {
 324                                                         if (stallEffectfieldName.length()==0 && nodeB.getTempDescriptor().equals(nodeA.getStallSite().getTdA())) {
 325                                                                 result = result | true;
 326                                                         }
 327                                                 }
 328
 329                                         }
 330                                 }
 331
 332
 333                         }
 334
 335                 }
 336
 337                 return result;
 338         }
 339
 340         private int determineWriteConflictsType(LiveInNode liveInNodeA,
 341                         LiveInNode liveInNodeB) {
 342
 343                 Set<HeapRegionNode> liveInHrnSetA = liveInNodeA.getHRNSet();
 344                 Set<HeapRegionNode> liveInHrnSetB = liveInNodeB.getHRNSet();
 345
 346                 boolean isPointingToSameRegion = compareHRNSet(liveInHrnSetA,
 347                                 liveInHrnSetB);
 348
 349                 boolean isSharingReachability = false;
 350
 351                 Set<Set> liveInNodeReachabilitySetA = liveInNodeA.getReachabilitySet();
 352                 Set<Set> liveInNodeReachabilitySetB = liveInNodeB.getReachabilitySet();
 353
 354                 Set<GloballyUniqueTokenTuple> overlappedReachableRegionSet = calculateOverlappedReachableRegion(
 355                                 liveInNodeReachabilitySetA, liveInNodeReachabilitySetB);
 356                 if (overlappedReachableRegionSet.size() > 0) {
 357                         isSharingReachability = true;
 358                 }
 359
 360                 if (isPointingToSameRegion && isSharingReachability) {
 361                         // two node share same reachability and points to same region, then
 362                         // it is fine grain conflicts
 363                         return ConflictEdge.FINE_GRAIN_EDGE;
 364                 } else if (isSharingReachability) {
 365                         // two node share same reachability but points to different region,
 366                         // then it is coarse grain conflicts
 367                         return ConflictEdge.COARSE_GRAIN_EDGE;
 368                 } else {
 369                         // otherwise, it is not write conflicts
 370                         return ConflictEdge.NON_WRITE_CONFLICT;
 371                 }
 372
 373         }
 374
 375         private boolean compareHRNSet(Set<HeapRegionNode> setA,
 376                         Set<HeapRegionNode> setB) {
 377
 378                 for (Iterator iterator = setA.iterator(); iterator.hasNext();) {
 379                         HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next();
 380                         String gID = heapRegionNode.getGloballyUniqueIdentifier();
 381                         boolean found = false;
 382                         for (Iterator iterator2 = setB.iterator(); iterator2.hasNext();) {
 383                                 HeapRegionNode heapRegionNode2 = (HeapRegionNode) iterator2
 384                                                 .next();
 385                                 if (heapRegionNode2.getGloballyUniqueIdentifier().equals(gID)) {
 386                                         found = true;
 387                                 }
 388                         }
 389                         if (!found) {
 390                                 return false;
 391                         }
 392                 }
 393                 return true;
 394         }
 395
 396         private int determineWriteConflictsType(StallSiteNode stallNode,
 397                         LiveInNode liveInNode) {
 398
 399                 Set<HeapRegionNode> stallHrnSet = stallNode.getHRNSet();
 400                 Set<HeapRegionNode> liveInHrnSet = liveInNode.getHRNSet();
 401
 402                 boolean isPointingToSameRegion = compareHRNSet(stallHrnSet,
 403                                 liveInHrnSet);
 404
 405                 boolean isSharingReachability = false;
 406
 407                 Set<Set> stallNodeReachabilitySet = stallNode.getReachabilitySet();
 408                 Set<Set> liveInNodeReachabilitySet = liveInNode.getReachabilitySet();
 409
 410                 Set<GloballyUniqueTokenTuple> overlappedReachableRegionSet = calculateOverlappedReachableRegion(
 411                                 stallNodeReachabilitySet, liveInNodeReachabilitySet);
 412                 if (overlappedReachableRegionSet.size() > 0) {
 413                         isSharingReachability = true;
 414                 }
 415
 416                 if (isPointingToSameRegion && isSharingReachability) {
 417                         // two node share same reachability and points to same region, then
 418                         // it is fine grain conflicts
 419                         return ConflictEdge.FINE_GRAIN_EDGE;
 420                 } else if (isSharingReachability) {
 421                         // two node share same reachability but points to different region,
 422                         // then it is coarse grain conflicts
 423                         return ConflictEdge.COARSE_GRAIN_EDGE;
 424                 } else {
 425                         // otherwise, it is not write conflicts
 426                         return ConflictEdge.NON_WRITE_CONFLICT;
 427                 }
 428
 429         }
 430
 431         private boolean hasStrongUpdate(SESEEffectsKey writeEffect,
 432                         Set<SESEEffectsKey> strongUpdateSet) {
 433
 434                 if(strongUpdateSet!=null){
 435                         Iterator<SESEEffectsKey> strongUpdateIter = strongUpdateSet.iterator();
 436                         while (strongUpdateIter.hasNext()) {
 437                                 SESEEffectsKey strongEffect = (SESEEffectsKey) strongUpdateIter
 438                                                 .next();
 439
 440                                 if (strongEffect.getHRNUniqueId().equals(
 441                                                 writeEffect.getHRNUniqueId())
 442                                                 && strongEffect.getFieldDescriptor().equals(
 443                                                                 writeEffect.getFieldDescriptor())) {
 444                                         return true;
 445                                 }
 446                         }
 447                 }
 448
 449                 return false;
 450         }
 451
 452         private boolean isWriteConflicts(LiveInNode nodeA, LiveInNode nodeB) {
 453
 454                 Set<SESEEffectsKey> readEffectsSetA = nodeA.getReadEffectsSet();
 455                 Set<SESEEffectsKey> writeEffectsSetA = nodeA.getWriteEffectsSet();
 456                 Set<SESEEffectsKey> strongUpdateSetA = nodeA.getStrongUpdateSet();
 457
 458                 Set<SESEEffectsKey> readEffectsSetB = nodeB.getReadEffectsSet();
 459                 Set<SESEEffectsKey> writeEffectsSetB = nodeB.getWriteEffectsSet();
 460                 Set<SESEEffectsKey> strongUpdateSetB = nodeB.getStrongUpdateSet();
 461                 /*
 462                 System.out.println("nodeA="+nodeA);
 463                 System.out.println("readEffectsSetA="+readEffectsSetA);
 464                 System.out.println("writeEffectsSetA="+writeEffectsSetA);
 465                 System.out.println("strongUpdateSetA="+strongUpdateSetA);
 466                 System.out.println("nodeB="+nodeB);
 467                 System.out.println("readEffectsSetB="+readEffectsSetB);
 468                 System.out.println("writeEffectsSetB="+writeEffectsSetB);
 469                 System.out.println("strongUpdateSetB="+strongUpdateSetB);
 470                 System.out.println("--");
 471                 */
 472
 473                 // if node A has write effects on reading/writing regions of node B
 474                 if (writeEffectsSetA != null) {
 475                         Iterator<SESEEffectsKey> writeIterA = writeEffectsSetA.iterator();
 476                         while (writeIterA.hasNext()) {
 477                                 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIterA
 478                                                 .next();
 479
 480 //                              if (!hasStrongUpdate(seseEffectsKey, strongUpdateSetA)) {
 481
 482                                         String writeHeapRegionID = seseEffectsKey.getHRNUniqueId();
 483                                         String writeFieldName = seseEffectsKey.getFieldDescriptor();
 484
 485                                         if (readEffectsSetB != null) {
 486                                                 Iterator<SESEEffectsKey> readIterB = readEffectsSetB
 487                                                                 .iterator();
 488                                                 while (readIterB.hasNext()) {
 489                                                         SESEEffectsKey readingEffect = (SESEEffectsKey) readIterB
 490                                                                         .next();
 491
 492                                                         if (readingEffect.getHRNUniqueId().equals(
 493                                                                         writeHeapRegionID)
 494                                                                         && readingEffect.getFieldDescriptor()
 495                                                                                         .equals(writeFieldName)) {
 496                                                                 return true;
 497                                                         }
 498                                                 }
 499                                         }
 500
 501                                         if (writeEffectsSetB != null) {
 502                                                 Iterator<SESEEffectsKey> writeIterB = writeEffectsSetB
 503                                                                 .iterator();
 504                                                 while (writeIterB.hasNext()) {
 505                                                         SESEEffectsKey writingEffect = (SESEEffectsKey) writeIterB
 506                                                                         .next();
 507
 508                                                         if (writingEffect.getHRNUniqueId().equals(
 509                                                                         writeHeapRegionID)
 510                                                                         && writingEffect.getFieldDescriptor()
 511                                                                                         .equals(writeFieldName)) {
 512                                                                 return true;
 513                                                         }
 514                                                 }
 515                                         }
 516
 517 //                              } // end of if(hasStrong)
 518
 519                         }
 520                 }
 521
 522                 // if node B has write effects on reading regions of node A
 523                 if (writeEffectsSetB != null) {
 524                         Iterator<SESEEffectsKey> writeIterB = writeEffectsSetB.iterator();
 525                         while (writeIterB.hasNext()) {
 526                                 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIterB
 527                                                 .next();
 528
 529                                 //if (!hasStrongUpdate(seseEffectsKey, strongUpdateSetB)) {
 530
 531                                         String writeHeapRegionID = seseEffectsKey.getHRNUniqueId();
 532                                         String writeFieldName = seseEffectsKey.getFieldDescriptor();
 533
 534                                         if (readEffectsSetA != null) {
 535                                                 Iterator<SESEEffectsKey> readIterA = readEffectsSetA
 536                                                                 .iterator();
 537                                                 while (readIterA.hasNext()) {
 538                                                         SESEEffectsKey readingEffect = (SESEEffectsKey) readIterA
 539                                                                         .next();
 540                                                         if (readingEffect.getHRNUniqueId().equals(
 541                                                                         writeHeapRegionID)
 542                                                                         && readingEffect.getFieldDescriptor()
 543                                                                                         .equals(writeFieldName)) {
 544                                                                 return true;
 545                                                         }
 546                                                 }
 547                                         }
 548
 549                                         if (writeEffectsSetA != null) {
 550                                                 Iterator<SESEEffectsKey> writeIterA = writeEffectsSetA
 551                                                                 .iterator();
 552                                                 while (writeIterA.hasNext()) {
 553                                                         SESEEffectsKey writingEffect = (SESEEffectsKey) writeIterA
 554                                                                         .next();
 555                                                         if (writingEffect.getHRNUniqueId().equals(
 556                                                                         writeHeapRegionID)
 557                                                                         && writingEffect.getFieldDescriptor()
 558                                                                                         .equals(writeFieldName)) {
 559                                                                 return true;
 560                                                         }
 561                                                 }
 562                                         }
 563                                 //} // if(hasStrong)
 564
 565                         }
 566                 }
 567                 return false;
 568         }
 569
 570         private boolean isSelfConflicted(LiveInNode liveInNode) {
 571
 572                 int strongUpdateCount = 0;
 573
 574                 if (liveInNode.getWriteEffectsSet() != null
 575                                 && liveInNode.getWriteEffectsSet().size() > 0) {
 576
 577                         Set<SESEEffectsKey> strongUpdateSet = liveInNode
 578                                         .getStrongUpdateSet();
 579
 580                         Iterator<SESEEffectsKey> writeIter = liveInNode
 581                                         .getWriteEffectsSet().iterator();
 582                         while (writeIter.hasNext()) {
 583                                 SESEEffectsKey writeEffect = (SESEEffectsKey) writeIter.next();
 584                                 if (hasStrongUpdate(writeEffect, strongUpdateSet)) {
 585                                         strongUpdateCount++;
 586                                 }
 587
 588                                 if(writeEffect.isStrong()){
 589                                         return false;
 590                                 }
 591                         }
 592
 593
 594                         if (liveInNode.getWriteEffectsSet().size() == strongUpdateCount) {
 595                                 return false;
 596                         }else{
 597                                 return true;
 598                         }
 599
 600                 }
 601
 602                 return false;
 603         }
 604
 605         public void analyzePossibleConflicts(Set<String> analyzedIDSet,
 606                         ConflictNode currentNode) {
 607
 608                 // compare with all nodes
 609
 610                 // examine the case where self-edge exists
 611                 if (currentNode instanceof LiveInNode) {
 612                         LiveInNode liveInNode = (LiveInNode) currentNode;
 613 //                      if (liveInNode.getWriteEffectsSet() != null
 614 //                                      && liveInNode.getWriteEffectsSet().size() > 0) {
 615 //                              addConflictEdge(ConflictEdge.FINE_GRAIN_EDGE, currentNode,
 616 //                                              currentNode);
 617 //                      }
 618                         if(isSelfConflicted(liveInNode)){
 619                                 addConflictEdge(ConflictEdge.FINE_GRAIN_EDGE, currentNode,
 620                                                 currentNode);
 621                         }
 622
 623                 }
 624
 625                 Set<Entry<String, ConflictNode>> set = id2cn.entrySet();
 626                 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 627                         Entry<String, ConflictNode> entry = (Entry<String, ConflictNode>) iterator
 628                                         .next();
 629
 630                         String entryNodeID = entry.getKey();
 631                         ConflictNode entryNode = entry.getValue();
 632
 633                         if ((!currentNode.getID().equals(entryNodeID))
 634                                         && !(analyzedIDSet.contains(currentNode.getID()
 635                                                         + entryNodeID) || analyzedIDSet
 636                                                         .contains(entryNodeID + currentNode.getID()))) {
 637
 638                                 if (currentNode instanceof StallSiteNode
 639                                                 && entryNode instanceof LiveInNode) {
 640                                         if (isWriteConflicts((StallSiteNode) currentNode,
 641                                                         (LiveInNode) entryNode)) {
 642                                                 int conflictType = determineWriteConflictsType(
 643                                                                 (StallSiteNode) currentNode,
 644                                                                 (LiveInNode) entryNode);
 645                                                 if (conflictType > 0) {
 646                                                         addConflictEdge(conflictType, currentNode,
 647                                                                         entryNode);
 648                                                 }
 649                                         }
 650                                         analyzedIDSet.add(currentNode.getID() + entryNodeID);
 651
 652                                 } else if (currentNode instanceof LiveInNode
 653                                                 && entryNode instanceof LiveInNode) {
 654                                         if (isWriteConflicts((LiveInNode) currentNode,
 655                                                         (LiveInNode) entryNode)) {
 656
 657                                                 int conflictType = determineWriteConflictsType(
 658                                                                 (LiveInNode) currentNode,
 659                                                                 (LiveInNode) entryNode);
 660                                                 if (conflictType > 0) {
 661                                                         addConflictEdge(conflictType, currentNode,
 662                                                                         entryNode);
 663                                                 }
 664
 665                                         }
 666                                         analyzedIDSet.add(currentNode.getID() + entryNodeID);
 667                                 }
 668
 669                         }
 670
 671                 }
 672
 673         }
 674
 675         public boolean containsTokenTuple(Set<GloballyUniqueTokenTuple> overlapSet,
 676                         String uniqueID) {
 677
 678                 for (Iterator iterator = overlapSet.iterator(); iterator.hasNext();) {
 679                         GloballyUniqueTokenTuple globallyUniqueTokenTuple = (GloballyUniqueTokenTuple) iterator
 680                                         .next();
 681                         if (globallyUniqueTokenTuple.getID().equals(uniqueID)) {
 682                                 return true;
 683                         }
 684                 }
 685
 686                 return false;
 687
 688         }
 689
 690         private Set<GloballyUniqueTokenTuple> calculateOverlappedReachableRegion(
 691                         Set<Set> setA, Set<Set> setB) {
 692
 693                 Set<GloballyUniqueTokenTuple> returnSet = new HashSet<GloballyUniqueTokenTuple>();
 694
 695                 for (Iterator iterator2 = setA.iterator(); iterator2.hasNext();) {
 696                         Set tokenTupleSetA = (Set) iterator2.next();
 697
 698                         for (Iterator iterator3 = setB.iterator(); iterator3.hasNext();) {
 699                                 Set tokenTupleSetB = (Set) iterator3.next();
 700
 701                                 if (tokenTupleSetA.equals(tokenTupleSetB)) {
 702                                         // reachability states are overlapped
 703                                         Iterator ttsIter = tokenTupleSetA.iterator();
 704                                         while (ttsIter.hasNext()) {
 705                                                 GloballyUniqueTokenTuple tt = (GloballyUniqueTokenTuple) ttsIter
 706                                                                 .next();
 707                                                 returnSet.add(tt);
 708                                         }
 709                                 }
 710                         }
 711                 }
 712                 return returnSet;
 713         }
 714
 715         public String addStallNode(TempDescriptor td, FlatMethod fm,
 716                         StallSite stallSite, Set<Set> reachabilitySet) {
 717
 718                 String stallNodeID = td + "_" + fm.getMethod().getSymbol();
 719
 720                 if (!id2cn.containsKey(stallNodeID)) {
 721                         StallSiteNode newNode = new StallSiteNode(stallNodeID, td,
 722                                         stallSite, reachabilitySet);
 723                         id2cn.put(stallNodeID, newNode);
 724                         // it add new new stall node to conflict graph
 725                         return stallNodeID;
 726                 }
 727                 // it doesn't add new stall node because stall node has already been
 728                 // added.
 729                 return null;
 730         }
 731
 732         public StallSiteNode getStallNode(String stallNodeID) {
 733                 ConflictNode node = id2cn.get(stallNodeID);
 734                 if (node instanceof StallSiteNode) {
 735                         return (StallSiteNode) node;
 736                 } else {
 737                         return null;
 738                 }
 739         }
 740
 741         public void addLiveInNode(TempDescriptor td, Set<HeapRegionNode> hrnSet,
 742                         FlatSESEEnterNode fsen, Set<SESEEffectsKey> readEffectsSet,
 743                         Set<SESEEffectsKey> writeEffectsSet,
 744                         Set<SESEEffectsKey> strongUpdateSet, Set<Set> reachabilitySet) {
 745
 746                 String liveinNodeID = td + "_" + fsen.getIdentifier();
 747
 748                 LiveInNode newNode = new LiveInNode(liveinNodeID, td, hrnSet,
 749                                 readEffectsSet, writeEffectsSet, strongUpdateSet,
 750                                 reachabilitySet, fsen.getIdentifier());
 751                 id2cn.put(liveinNodeID, newNode);
 752
 753         }
 754
 755         public void addConflictEdge(int type, ConflictNode nodeU, ConflictNode nodeV) {
 756
 757                 ConflictEdge newEdge = new ConflictEdge(nodeU, nodeV, type);
 758                 nodeU.addEdge(newEdge);
 759                 nodeV.addEdge(newEdge);
 760
 761         }
 762
 763         public HashSet<LiveInNode> getLiveInNodeSet() {
 764                 HashSet<LiveInNode> resultSet = new HashSet<LiveInNode>();
 765
 766                 Set<String> keySet = id2cn.keySet();
 767                 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 768                         String key = (String) iterator.next();
 769                         ConflictNode node = id2cn.get(key);
 770
 771                         if (node instanceof LiveInNode) {
 772                                 resultSet.add((LiveInNode) node);
 773                         }
 774                 }
 775
 776                 return resultSet;
 777         }
 778
 779         public Set<WaitingElement> getStallSiteWaitingElementSet(
 780                         ParentChildConflictsMap conflictsMap, HashSet<SESELock> seseLockSet) {
 781
 782                 HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
 783                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
 784                 Collection<StallSite> stallSites = conflictsMap.getStallMap().values();
 785
 786                 for (Iterator iterator = stallSites.iterator(); iterator.hasNext();) {
 787
 788                         StallSite stallSite = (StallSite) iterator.next();
 789                         Iterator<Entry<String, ConflictNode>> i = s.iterator();
 790                         while (i.hasNext()) {
 791                                 Entry<String, ConflictNode> entry = i.next();
 792                                 ConflictNode node = entry.getValue();
 793
 794                                 if (node instanceof StallSiteNode) {
 795                                         StallSiteNode stallSiteNode = (StallSiteNode) node;
 796                                         if (stallSiteNode.getStallSite().equals(stallSite)) {
 797                                                 HashSet<ConflictEdge> edgeSet = stallSiteNode
 798                                                                 .getEdgeSet();
 799                                                 for (Iterator iter2 = edgeSet.iterator(); iter2
 800                                                                 .hasNext();) {
 801                                                         ConflictEdge conflictEdge = (ConflictEdge) iter2
 802                                                                         .next();
 803
 804                                                         int type = -1;
 805                                                         HashSet<Integer> allocSet = new HashSet<Integer>();
 806
 807                                                         if (conflictEdge.getType() == ConflictEdge.COARSE_GRAIN_EDGE) {
 808                                                                 if (isReadOnly(node)) {
 809                                                                         type = 2; // coarse read
 810                                                                 } else {
 811                                                                         type = 3; // coarse write
 812                                                                 }
 813
 814                                                                 allocSet.addAll(getAllocSet(conflictEdge
 815                                                                                 .getVertexU()));
 816                                                                 allocSet.addAll(getAllocSet(conflictEdge
 817                                                                                 .getVertexV()));
 818
 819                                                         } else if (conflictEdge.getType() == ConflictEdge.FINE_GRAIN_EDGE) {// it
 820                                                                                                                                                                                                 // is
 821                                                                                                                                                                                                 // fine-grain
 822                                                                                                                                                                                                 // edge
 823                                                                 allocSet.addAll(getAllocSet(node));
 824                                                                 if (isReadOnly(node)) {
 825                                                                         // fine-grain read
 826                                                                         type = 0;
 827                                                                 } else {
 828                                                                         // fine-grain write
 829                                                                         type = 1;
 830                                                                 }
 831                                                         }
 832
 833                                                         if (type > -1) {
 834                                                                 for (Iterator<SESELock> seseLockIter = seseLockSet
 835                                                                                 .iterator(); seseLockIter.hasNext();) {
 836                                                                         SESELock seseLock = seseLockIter.next();
 837                                                                         if (seseLock
 838                                                                                         .containsConflictNode(stallSiteNode)) {
 839                                                                                 WaitingElement newElement = new WaitingElement();
 840                                                                                 newElement.setAllocList(allocSet);
 841                                                                                 newElement.setWaitingID(seseLock
 842                                                                                                 .getID());
 843                                                                                 newElement.setStatus(type);
 844                                                                                 waitingElementSet.add(newElement);
 845                                                                         }
 846                                                                 }
 847                                                         }
 848
 849                                                 }
 850                                         }
 851                                 }
 852                         }
 853
 854                 }
 855
 856                 return waitingElementSet;
 857         }
 858
 859         public Set<Integer> getConnectedConflictNodeSet(
 860                         ParentChildConflictsMap conflictsMap) {
 861
 862                 HashSet<Integer> nodeIDSet = new HashSet<Integer>();
 863
 864                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
 865
 866                 Collection<StallSite> stallSites = conflictsMap.getStallMap().values();
 867                 for (Iterator iterator = stallSites.iterator(); iterator.hasNext();) {
 868                         StallSite stallSite = (StallSite) iterator.next();
 869                         Iterator<Entry<String, ConflictNode>> i = s.iterator();
 870                         while (i.hasNext()) {
 871                                 Entry<String, ConflictNode> entry = i.next();
 872                                 ConflictNode node = entry.getValue();
 873
 874                                 if (node instanceof StallSiteNode) {
 875                                         StallSiteNode stallSiteNode = (StallSiteNode) node;
 876                                         if (stallSiteNode.getStallSite().equals(stallSite)) {
 877                                                 HashSet<ConflictEdge> edgeSet = stallSiteNode
 878                                                                 .getEdgeSet();
 879                                                 for (Iterator iter2 = edgeSet.iterator(); iter2
 880                                                                 .hasNext();) {
 881                                                         ConflictEdge conflictEdge = (ConflictEdge) iter2
 882                                                                         .next();
 883                                                         nodeIDSet
 884                                                                         .addAll(getConnectedConflictNode(conflictEdge));
 885                                                 }
 886                                         }
 887                                 }
 888                         }
 889                 }
 890
 891                 return nodeIDSet;
 892
 893         }
 894
 895         private Set<Integer> getConnectedConflictNode(ConflictEdge conflictEdge) {
 896
 897                 HashSet<Integer> nodeIDSet = new HashSet<Integer>();
 898
 899                 if (conflictEdge.getVertexU() instanceof LiveInNode) {
 900                         LiveInNode lin = (LiveInNode) conflictEdge.getVertexU();
 901                         nodeIDSet.add(new Integer(lin.getSESEIdentifier()));
 902                 }
 903                 if (conflictEdge.getVertexV() instanceof LiveInNode) {
 904                         LiveInNode lin = (LiveInNode) conflictEdge.getVertexV();
 905                         nodeIDSet.add(new Integer(lin.getSESEIdentifier()));
 906                 }
 907
 908                 return nodeIDSet;
 909         }
 910
 911         private Set<Integer> getConnectedConflictNode(ConflictEdge conflictEdge,
 912                         int seseID) {
 913
 914                 HashSet<Integer> nodeIDSet = new HashSet<Integer>();
 915
 916                 if (conflictEdge.getVertexU() instanceof LiveInNode) {
 917                         LiveInNode lin = (LiveInNode) conflictEdge.getVertexU();
 918                         if (lin.getSESEIdentifier() != seseID) {
 919                                 nodeIDSet.add(new Integer(lin.getSESEIdentifier()));
 920                         }
 921                 } else {
 922                         // it is stall site
 923                         nodeIDSet.add(new Integer(-1));
 924                 }
 925                 if (conflictEdge.getVertexV() instanceof LiveInNode) {
 926                         LiveInNode lin = (LiveInNode) conflictEdge.getVertexV();
 927                         if (lin.getSESEIdentifier() != seseID) {
 928                                 nodeIDSet.add(new Integer(lin.getSESEIdentifier()));
 929                         }
 930                 } else {
 931                         // it is stall site
 932                         nodeIDSet.add(new Integer(-1));
 933                 }
 934
 935                 // self-edge case
 936                 if (conflictEdge.getVertexU() instanceof LiveInNode
 937                                 && conflictEdge.getVertexV() instanceof LiveInNode) {
 938                         if (((LiveInNode) conflictEdge.getVertexU()).getSESEIdentifier() == seseID
 939                                         && ((LiveInNode) conflictEdge.getVertexV())
 940                                                         .getSESEIdentifier() == seseID) {
 941                                 nodeIDSet.add(seseID);
 942                         }
 943                 }
 944
 945                 return nodeIDSet;
 946         }
 947
 948         public Set<Integer> getConnectedConflictNodeSet(int seseID) {
 949
 950                 HashSet<Integer> nodeIDSet = new HashSet<Integer>();
 951
 952                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
 953                 Iterator<Entry<String, ConflictNode>> i = s.iterator();
 954
 955                 while (i.hasNext()) {
 956                         Entry<String, ConflictNode> entry = i.next();
 957                         ConflictNode node = entry.getValue();
 958
 959                         if (node instanceof LiveInNode) {
 960                                 LiveInNode liveInNode = (LiveInNode) node;
 961                                 if (liveInNode.getSESEIdentifier() == seseID) {
 962                                         HashSet<ConflictEdge> edgeSet = liveInNode.getEdgeSet();
 963                                         for (Iterator iterator = edgeSet.iterator(); iterator
 964                                                         .hasNext();) {
 965                                                 ConflictEdge conflictEdge = (ConflictEdge) iterator
 966                                                                 .next();
 967                                                 //
 968                                                 nodeIDSet.addAll(getConnectedConflictNode(conflictEdge,
 969                                                                 seseID));
 970                                                 //
 971                                         }
 972                                 }
 973                         }
 974                 }
 975
 976                 return nodeIDSet;
 977
 978         }
 979
 980         public Set<WaitingElement> getWaitingElementSetBySESEID(int seseID,
 981                         HashSet<SESELock> seseLockSet) {
 982
 983                 HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
 984
 985                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
 986                 Iterator<Entry<String, ConflictNode>> i = s.iterator();
 987
 988                 while (i.hasNext()) {
 989                         Entry<String, ConflictNode> entry = i.next();
 990                         ConflictNode node = entry.getValue();
 991
 992                         if (node instanceof LiveInNode) {
 993                                 LiveInNode liveInNode = (LiveInNode) node;
 994                                 if (liveInNode.getSESEIdentifier() == seseID) {
 995
 996                                         HashSet<ConflictEdge> edgeSet = liveInNode.getEdgeSet();
 997
 998                                         for (Iterator iterator = edgeSet.iterator(); iterator
 999                                                         .hasNext();) {
1000                                                 ConflictEdge conflictEdge = (ConflictEdge) iterator
1001                                                                 .next();
1002                                                 int type = -1;
1003                                                 HashSet<Integer> allocSet = new HashSet<Integer>();
1004
1005                                                 if (conflictEdge.getType() == ConflictEdge.COARSE_GRAIN_EDGE) {
1006                                                         if (isReadOnly(node)) {
1007                                                                 type = 2; // coarse read
1008                                                         } else {
1009                                                                 type = 3; // coarse write
1010                                                         }
1011
1012                                                         allocSet.addAll(getAllocSet(conflictEdge
1013                                                                         .getVertexU()));
1014                                                         allocSet.addAll(getAllocSet(conflictEdge
1015                                                                         .getVertexV()));
1016
1017                                                 } else if (conflictEdge.getType() == ConflictEdge.FINE_GRAIN_EDGE) {// it
1018                                                                                                                                                                                         // is
1019                                                                                                                                                                                         // fine-grain
1020                                                                                                                                                                                         // edge
1021                                                         allocSet.addAll(getAllocSet(node));
1022                                                         if (isReadOnly(node)) {
1023                                                                 // fine-grain read
1024                                                                 type = 0;
1025                                                         } else {
1026                                                                 // fine-grain write
1027                                                                 type = 1;
1028                                                         }
1029                                                 }
1030
1031                                                 if (type > -1) {
1032
1033                                                         for (Iterator<SESELock> seseLockIter = seseLockSet
1034                                                                         .iterator(); seseLockIter.hasNext();) {
1035                                                                 SESELock seseLock = seseLockIter.next();
1036                                                                 if (seseLock.containsConflictNode(liveInNode)) {
1037                                                                         WaitingElement newElement = new WaitingElement();
1038                                                                         newElement.setAllocList(allocSet);
1039                                                                         newElement.setWaitingID(seseLock.getID());
1040                                                                         newElement.setStatus(type);
1041                                                                         if(!waitingElementSet.contains(newElement)){
1042                                                                                 waitingElementSet.add(newElement);
1043                                                                         }else{
1044                                                                         }
1045
1046
1047                                                                 }
1048                                                         }
1049                                                 }
1050                                         }
1051
1052                                 }
1053                         }
1054
1055                 }
1056
1057                 return waitingElementSet;
1058         }
1059
1060         public Set<Long> getAllocationSiteIDSetBySESEID(int seseID) {
1061                 // deprecated
1062                 HashSet<Long> allocSiteIDSet = new HashSet<Long>();
1063
1064                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
1065                 Iterator<Entry<String, ConflictNode>> i = s.iterator();
1066
1067                 while (i.hasNext()) {
1068                         Entry<String, ConflictNode> entry = i.next();
1069                         ConflictNode node = entry.getValue();
1070
1071                         if (node instanceof LiveInNode) {
1072                                 LiveInNode liveInNode = (LiveInNode) node;
1073                                 if (liveInNode.getSESEIdentifier() == seseID) {
1074                                         HashSet<ConflictEdge> edgeSet = liveInNode.getEdgeSet();
1075                                         for (Iterator iterator = edgeSet.iterator(); iterator
1076                                                         .hasNext();) {
1077                                                 ConflictEdge conflictEdge = (ConflictEdge) iterator
1078                                                                 .next();
1079                                                 //
1080                                                 getConnectedConflictNode(conflictEdge, seseID);
1081                                                 //
1082                                                 if (conflictEdge.getType() == ConflictEdge.COARSE_GRAIN_EDGE) {
1083                                                         allocSiteIDSet
1084                                                                         .addAll(getHRNIdentifierSet(conflictEdge
1085                                                                                         .getVertexU()));
1086                                                         allocSiteIDSet
1087                                                                         .addAll(getHRNIdentifierSet(conflictEdge
1088                                                                                         .getVertexV()));
1089                                                 } else {// it is fine-grain edge
1090                                                         allocSiteIDSet.addAll(getHRNIdentifierSet(node));
1091                                                 }
1092                                         }
1093
1094                                 }
1095                         }
1096                 }
1097
1098                 return allocSiteIDSet;
1099
1100         }
1101
1102         public Set<Long> getAllocationSiteIDSetofStallSite() {
1103
1104                 HashSet<Long> allocSiteIDSet = new HashSet<Long>();
1105
1106                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
1107                 Iterator<Entry<String, ConflictNode>> i = s.iterator();
1108
1109                 while (i.hasNext()) {
1110
1111                         Entry<String, ConflictNode> entry = i.next();
1112                         ConflictNode node = entry.getValue();
1113
1114                         if (node instanceof StallSiteNode) {
1115                                 allocSiteIDSet.addAll(getHRNIdentifierSet(node));
1116                         }
1117
1118                 }
1119
1120                 return allocSiteIDSet;
1121
1122         }
1123
1124         public Set<Long> getAllocationSiteIDSet() {
1125
1126                 HashSet<Long> allocSiteIDSet = new HashSet<Long>();
1127
1128                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
1129                 Iterator<Entry<String, ConflictNode>> i = s.iterator();
1130
1131                 while (i.hasNext()) {
1132                         Entry<String, ConflictNode> entry = i.next();
1133                         ConflictNode node = entry.getValue();
1134
1135                         HashSet<ConflictEdge> edgeSet = node.getEdgeSet();
1136                         for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
1137                                 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1138                                 if (conflictEdge.getType() == ConflictEdge.COARSE_GRAIN_EDGE) {
1139                                         allocSiteIDSet.addAll(getHRNIdentifierSet(conflictEdge
1140                                                         .getVertexU()));
1141                                         allocSiteIDSet.addAll(getHRNIdentifierSet(conflictEdge
1142                                                         .getVertexV()));
1143                                 } else {// it is fine-grain edge
1144                                         allocSiteIDSet.addAll(getHRNIdentifierSet(node));
1145                                 }
1146                         }
1147
1148                 }
1149
1150                 return allocSiteIDSet;
1151
1152         }
1153
1154         private HashSet<Integer> getAllocSet(ConflictNode node) {
1155
1156                 HashSet<Integer> returnSet = new HashSet<Integer>();
1157
1158                 if (node instanceof StallSiteNode) {
1159                         StallSiteNode stallSiteNode = (StallSiteNode) node;
1160                         Set<HeapRegionNode> hrnSet = stallSiteNode.getHRNSet();
1161                         for (Iterator iterator = hrnSet.iterator(); iterator.hasNext();) {
1162                                 HeapRegionNode hrn = (HeapRegionNode) iterator.next();
1163                                 // allocSiteIDSet.add(hrn.getGloballyUniqueIdentifier());
1164                                 if (hrn.getAllocationSite() != null) {
1165                                         returnSet.add(new Integer(hrn.getAllocationSite().getID()));
1166                                 }
1167                         }
1168                 } else {
1169                         LiveInNode liveInNode = (LiveInNode) node;
1170                         Set<HeapRegionNode> hrnSet = liveInNode.getHRNSet();
1171                         for (Iterator iterator = hrnSet.iterator(); iterator.hasNext();) {
1172                                 HeapRegionNode hrn = (HeapRegionNode) iterator.next();
1173                                 // allocSiteIDSet.add(hrn.getGloballyUniqueIdentifier());
1174                                 if (hrn.getAllocationSite() != null) {
1175                                         returnSet.add(new Integer(hrn.getAllocationSite().getID()));
1176                                 }else{
1177                                         returnSet.add(new Integer(hrn.getID()));
1178                                 }
1179                         }
1180                 }
1181
1182                 return returnSet;
1183         }
1184
1185         private HashSet<Long> getHRNIdentifierSet(ConflictNode node) {
1186
1187                 HashSet<Long> returnSet = new HashSet<Long>();
1188
1189                 if (node instanceof StallSiteNode) {
1190                         StallSiteNode stallSiteNode = (StallSiteNode) node;
1191                         Set<HeapRegionNode> hrnSet = stallSiteNode.getHRNSet();
1192                         for (Iterator iterator = hrnSet.iterator(); iterator.hasNext();) {
1193                                 HeapRegionNode hrn = (HeapRegionNode) iterator.next();
1194                                 // allocSiteIDSet.add(hrn.getGloballyUniqueIdentifier());
1195                                 returnSet
1196                                                 .add(new Long(hrn.getGloballyUniqueIntegerIdentifier()));
1197                         }
1198                 } else {
1199                         LiveInNode liveInNode = (LiveInNode) node;
1200                         Set<HeapRegionNode> hrnSet = liveInNode.getHRNSet();
1201                         for (Iterator iterator = hrnSet.iterator(); iterator.hasNext();) {
1202                                 HeapRegionNode hrn = (HeapRegionNode) iterator.next();
1203                                 // allocSiteIDSet.add(hrn.getGloballyUniqueIdentifier());
1204                                 returnSet
1205                                                 .add(new Long(hrn.getGloballyUniqueIntegerIdentifier()));
1206                         }
1207                 }
1208
1209                 return returnSet;
1210
1211         }
1212
1213         public HashSet<ConflictEdge> getEdgeSet() {
1214
1215                 HashSet<ConflictEdge> returnSet = new HashSet<ConflictEdge>();
1216
1217                 Collection<ConflictNode> nodes = id2cn.values();
1218                 for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
1219                         ConflictNode conflictNode = (ConflictNode) iterator.next();
1220                         returnSet.addAll(conflictNode.getEdgeSet());
1221                 }
1222
1223                 return returnSet;
1224         }
1225
1226         static public int generateUniqueCliqueID() {
1227                 ++uniqueCliqueIDcount;
1228                 return uniqueCliqueIDcount;
1229         }
1230
1231         public void writeGraph(String graphName, boolean filter)
1232                         throws java.io.IOException {
1233
1234                 graphName = graphName.replaceAll("[\\W]", "");
1235
1236                 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName
1237                                 + ".dot"));
1238                 bw.write("graph " + graphName + " {\n");
1239
1240                 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1241                 // then visit every heap region node
1242                 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
1243                 Iterator<Entry<String, ConflictNode>> i = s.iterator();
1244
1245                 HashSet<ConflictEdge> addedSet = new HashSet<ConflictEdge>();
1246
1247                 while (i.hasNext()) {
1248                         Entry<String, ConflictNode> entry = i.next();
1249                         ConflictNode node = entry.getValue();
1250
1251                         if (filter) {
1252                                 if (node.getID().startsWith("___dst")
1253                                                 || node.getID().startsWith("___srctmp")
1254                                                 || node.getID().startsWith("___neverused")
1255                                                 || node.getID().startsWith("___temp")) {
1256
1257                                         continue;
1258                                 }
1259                         }
1260
1261                         String attributes = "[";
1262
1263                         attributes += "label=\"ID" + node.getID() + "\\n";
1264
1265                         if (node instanceof StallSiteNode) {
1266                                 attributes += "STALL SITE" + "\\n" + "\"]";
1267                         } else {
1268                                 attributes += "LIVE-IN" + "\\n" + "\"]";
1269                         }
1270                         bw.write(entry.getKey() + attributes + ";\n");
1271
1272                         HashSet<ConflictEdge> edgeSet = node.getEdgeSet();
1273                         for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
1274                                 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1275
1276                                 ConflictNode u = conflictEdge.getVertexU();
1277                                 ConflictNode v = conflictEdge.getVertexV();
1278
1279                                 if (filter) {
1280                                         String uID = u.getID();
1281                                         String vID = v.getID();
1282                                         if (uID.startsWith("___dst") || uID.startsWith("___srctmp")
1283                                                         || uID.startsWith("___neverused")
1284                                                         || uID.startsWith("___temp")
1285                                                         || vID.startsWith("___dst")
1286                                                         || vID.startsWith("___srctmp")
1287                                                         || vID.startsWith("___neverused")
1288                                                         || vID.startsWith("___temp")) {
1289                                                 continue;
1290                                         }
1291                                 }
1292
1293                                 if (!addedSet.contains(conflictEdge)) {
1294                                         bw.write(" " + u.getID() + "--" + v.getID() + "[label="
1295                                                         + conflictEdge.toGraphEdgeString()
1296                                                         + ",decorate];\n");
1297                                         addedSet.add(conflictEdge);
1298                                 }
1299
1300                         }
1301                 }
1302
1303                 bw.write("  graphTitle[label=\"" + graphName + "\",shape=box];\n");
1304
1305                 bw.write("}\n");
1306                 bw.close();
1307
1308         }
1309
1310 }
1311
1312 class ConflictEdge {
1313
1314         private ConflictNode u;
1315         private ConflictNode v;
1316         private int type;
1317
1318         public static final int NON_WRITE_CONFLICT = 0;
1319         public static final int FINE_GRAIN_EDGE = 1;
1320         public static final int COARSE_GRAIN_EDGE = 2;
1321         public static final int PSEUDO_EDGE = 3;
1322
1323         public ConflictEdge(ConflictNode u, ConflictNode v, int type) {
1324                 this.u = u;
1325                 this.v = v;
1326                 this.type = type;
1327         }
1328
1329         public String toGraphEdgeString() {
1330                 if (type == FINE_GRAIN_EDGE) {
1331                         return "\"F_CONFLICT\"";
1332                 } else if (type == COARSE_GRAIN_EDGE) {
1333                         return "\"C_CONFLICT\"";
1334                 } else if (type == PSEUDO_EDGE) {
1335                         return "\"P_CONFLICT\", style=dotted";
1336                 } else {
1337                         return "CONFLICT\"";
1338                 }
1339         }
1340
1341         public ConflictNode getVertexU() {
1342                 return u;
1343         }
1344
1345         public ConflictNode getVertexV() {
1346                 return v;
1347         }
1348
1349         public int getType() {
1350                 return type;
1351         }
1352
1353 }