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;
11 import java.util.Map.Entry;
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;
21 public class ConflictGraph {
23 static private int uniqueCliqueIDcount = 100;
25 public Hashtable<String, ConflictNode> id2cn;
26 private OwnershipGraph og;
28 public ConflictGraph(OwnershipGraph og) {
29 id2cn = new Hashtable<String, ConflictNode>();
33 public boolean hasConflictEdge() {
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) {
46 public void analyzeConflicts() {
48 Set<String> keySet = id2cn.keySet();
49 Set<String> analyzedIDSet = new HashSet<String>();
51 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
52 String nodeID = (String) iterator.next();
53 ConflictNode node = id2cn.get(nodeID);
54 analyzePossibleConflicts(analyzedIDSet, node);
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
67 if (heapRegionNode2.getGloballyUniqueIdentifier().equals(gID)) {
78 public String addStallNode(TempDescriptor td, FlatMethod fm,
79 StallSite stallSite, Set<Set> reachabilitySet) {
81 String stallNodeID = td + "_" + fm.getMethod().getSymbol();
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
90 // it doesn't add new stall node because stall node has already been
95 public StallSiteNode getStallNode(String stallNodeID) {
96 ConflictNode node = id2cn.get(stallNodeID);
97 if (node instanceof StallSiteNode) {
98 return (StallSiteNode) node;
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) {
109 String liveinNodeID = td + "_" + fsen.getIdentifier();
111 LiveInNode newNode = new LiveInNode(liveinNodeID, td, hrnSet,
112 readEffectsSet, writeEffectsSet, strongUpdateSet,
113 reachabilitySet, fsen.getIdentifier());
114 id2cn.put(liveinNodeID, newNode);
118 public void addConflictEdge(int type, ConflictNode nodeU, ConflictNode nodeV) {
120 // if there are two edges between the same node pair, coarse has a
122 HashSet<ConflictEdge> set = nodeU.getEdgeSet();
123 ConflictEdge toBeRemoved = null;
124 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
125 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
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;
135 } else if (conflictEdge.getType() == ConflictEdge.COARSE_GRAIN_EDGE
136 && type == ConflictEdge.FINE_GRAIN_EDGE) {
143 if (toBeRemoved != null) {
144 nodeU.getEdgeSet().remove(toBeRemoved);
145 nodeV.getEdgeSet().remove(toBeRemoved);
148 ConflictEdge newEdge = new ConflictEdge(nodeU, nodeV, type);
149 nodeU.addEdge(newEdge);
150 nodeV.addEdge(newEdge);
154 public Set<WaitingElement> getStallSiteWaitingElementSet(
155 ParentChildConflictsMap conflictsMap, HashSet<SESELock> seseLockSet) {
157 HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
158 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
159 Collection<StallSite> stallSites = conflictsMap.getStallMap().values();
161 for (Iterator iterator = stallSites.iterator(); iterator.hasNext();) {
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();
169 if (node instanceof StallSiteNode) {
170 StallSiteNode stallSiteNode = (StallSiteNode) node;
171 if (stallSiteNode.getStallSite().equals(stallSite)) {
172 HashSet<ConflictEdge> edgeSet = stallSiteNode
174 for (Iterator iter2 = edgeSet.iterator(); iter2
176 ConflictEdge conflictEdge = (ConflictEdge) iter2
179 for (Iterator<SESELock> seseLockIter = seseLockSet
180 .iterator(); seseLockIter.hasNext();) {
181 SESELock seseLock = seseLockIter.next();
183 .containsConflictNode(stallSiteNode)
185 .containsConflictEdge(conflictEdge)) {
186 WaitingElement newElement = new WaitingElement();
187 newElement.setQueueID(seseLock.getID());
188 if (isFineElement(newElement.getStatus())) {
194 newElement.setStatus(seseLock
195 .getNodeType(stallSiteNode));
196 waitingElementSet.add(newElement);
206 return waitingElementSet;
209 private Set<Integer> getConnectedConflictNode(ConflictEdge conflictEdge,
212 HashSet<Integer> nodeIDSet = new HashSet<Integer>();
214 if (conflictEdge.getVertexU() instanceof LiveInNode) {
215 LiveInNode lin = (LiveInNode) conflictEdge.getVertexU();
216 if (lin.getSESEIdentifier() != seseID) {
217 nodeIDSet.add(new Integer(lin.getSESEIdentifier()));
221 nodeIDSet.add(new Integer(-1));
223 if (conflictEdge.getVertexV() instanceof LiveInNode) {
224 LiveInNode lin = (LiveInNode) conflictEdge.getVertexV();
225 if (lin.getSESEIdentifier() != seseID) {
226 nodeIDSet.add(new Integer(lin.getSESEIdentifier()));
230 nodeIDSet.add(new Integer(-1));
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);
246 public Set<Integer> getConnectedConflictNodeSet(int seseID) {
248 HashSet<Integer> nodeIDSet = new HashSet<Integer>();
250 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
251 Iterator<Entry<String, ConflictNode>> i = s.iterator();
253 while (i.hasNext()) {
254 Entry<String, ConflictNode> entry = i.next();
255 ConflictNode node = entry.getValue();
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
263 ConflictEdge conflictEdge = (ConflictEdge) iterator
266 nodeIDSet.addAll(getConnectedConflictNode(conflictEdge,
278 public SESEWaitingQueue getWaitingElementSetBySESEID(int seseID,
279 HashSet<SESELock> seseLockSet) {
280 HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
282 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
283 Iterator<Entry<String, ConflictNode>> i = s.iterator();
285 while (i.hasNext()) {
286 Entry<String, ConflictNode> entry = i.next();
287 ConflictNode node = entry.getValue();
289 if (node instanceof LiveInNode) {
290 LiveInNode liveInNode = (LiveInNode) node;
291 if (liveInNode.getSESEIdentifier() == seseID) {
293 HashSet<ConflictEdge> edgeSet = liveInNode.getEdgeSet();
295 for (Iterator iterator = edgeSet.iterator(); iterator
297 ConflictEdge conflictEdge = (ConflictEdge) iterator
300 for (Iterator<SESELock> seseLockIter = seseLockSet
301 .iterator(); seseLockIter.hasNext();) {
302 SESELock seseLock = seseLockIter.next();
303 if (seseLock.containsConflictNode(liveInNode)
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());
315 if (!waitingElementSet.contains(newElement)) {
316 waitingElementSet.add(newElement);
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;
334 public SESEWaitingQueue refineQueue(Set<WaitingElement> waitingElementSet) {
336 Set<WaitingElement> refinedSet=new HashSet<WaitingElement>();
337 HashMap<Integer, Set<WaitingElement>> map = new HashMap<Integer, Set<WaitingElement>>();
338 SESEWaitingQueue seseDS=new SESEWaitingQueue();
340 for (Iterator iterator = waitingElementSet.iterator(); iterator
342 WaitingElement waitingElement = (WaitingElement) iterator.next();
343 Set<WaitingElement> set=map.get(new Integer(waitingElement.getQueueID()));
345 set=new HashSet<WaitingElement>();
347 set.add(waitingElement);
348 map.put(new Integer(waitingElement.getQueueID()), set);
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);
361 private void refineQueue(int queueID,
362 Set<WaitingElement> waitingElementSet, SESEWaitingQueue seseDS) {
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>();
371 int total=waitingElementSet.size();
372 WaitingElement SCCelement = null;
373 WaitingElement coarseElement = null;
375 for (Iterator iterator = waitingElementSet.iterator(); iterator
377 WaitingElement waitingElement = (WaitingElement) iterator
379 if (waitingElement.getStatus() == ConflictNode.FINE_READ) {
381 } else if (waitingElement.getStatus() == ConflictNode.FINE_WRITE) {
383 } else if (waitingElement.getStatus() == ConflictNode.COARSE) {
385 coarseElement = waitingElement;
386 } else if (waitingElement.getStatus() == ConflictNode.SCC) {
387 SCCelement = waitingElement;
391 if (SCCelement != null) {
392 // if there is at lease one SCC element, just enqueue SCC and
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);
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);
409 // otherwise, enqueue everything.
410 refinedSet.addAll(waitingElementSet);
412 seseDS.setWaitingElementSet(queueID, refinedSet);
414 seseDS.setWaitingElementSet(queueID, waitingElementSet);
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) {
429 public HashSet<ConflictEdge> getEdgeSet() {
431 HashSet<ConflictEdge> returnSet = new HashSet<ConflictEdge>();
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());
442 public void writeGraph(String graphName, boolean filter)
443 throws java.io.IOException {
445 graphName = graphName.replaceAll("[\\W]", "");
447 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName
449 bw.write("graph " + graphName + " {\n");
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();
456 HashSet<ConflictEdge> addedSet = new HashSet<ConflictEdge>();
458 while (i.hasNext()) {
459 Entry<String, ConflictNode> entry = i.next();
460 ConflictNode node = entry.getValue();
463 if (node.getID().startsWith("___dst")
464 || node.getID().startsWith("___srctmp")
465 || node.getID().startsWith("___neverused")
466 || node.getID().startsWith("___temp")) {
472 String attributes = "[";
474 attributes += "label=\"ID" + node.getID() + "\\n";
476 if (node instanceof StallSiteNode) {
477 attributes += "STALL SITE" + "\\n" + "\"]";
479 attributes += "LIVE-IN" + "\\n" + "\"]";
481 bw.write(entry.getKey() + attributes + ";\n");
483 HashSet<ConflictEdge> edgeSet = node.getEdgeSet();
484 for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
485 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
487 ConflictNode u = conflictEdge.getVertexU();
488 ConflictNode v = conflictEdge.getVertexV();
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")) {
504 if (!addedSet.contains(conflictEdge)) {
505 bw.write(" " + u.getID() + "--" + v.getID() + "[label="
506 + conflictEdge.toGraphEdgeString()
508 addedSet.add(conflictEdge);
514 bw.write(" graphTitle[label=\"" + graphName + "\",shape=box];\n");
521 private int calculateConflictType(StallSiteNode nodeA, LiveInNode nodeB) {
523 StallSite stallSite = nodeA.getStallSite();
524 Set<SESEEffectsKey> writeEffectsSet = nodeB.getWriteEffectsSet();
525 Set<SESEEffectsKey> readEffectsSet = nodeB.getReadEffectsSet();
527 int conflictType = 0;
529 if (writeEffectsSet != null) {
530 Iterator<SESEEffectsKey> writeIter = writeEffectsSet.iterator();
531 while (writeIter.hasNext()) {
532 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIter
534 String writeHeapRegionID = seseEffectsKey.getHRNUniqueId();
535 String writeFieldName = seseEffectsKey.getFieldDescriptor();
537 HashSet<HeapRegionNode> stallSiteHRNSet = nodeA.getHRNSet();
538 for (Iterator iterator = stallSiteHRNSet.iterator(); iterator
540 HeapRegionNode stallHRN = (HeapRegionNode) iterator.next();
541 if (stallHRN.getGloballyUniqueIdentifier().equals(
542 writeHeapRegionID)) {
543 // check whether there are read or write effects of
545 HashSet<Effect> effectSet = stallSite.getEffectSet();
546 for (Iterator iterator2 = effectSet.iterator(); iterator2
548 Effect effect = (Effect) iterator2.next();
549 String stallEffectfieldName = effect.getField();
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;
567 if (readEffectsSet != null) {
568 Iterator<SESEEffectsKey> readIter = readEffectsSet.iterator();
569 while (readIter.hasNext()) {
570 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) readIter
572 String readHeapRegionID = seseEffectsKey.getHRNUniqueId();
573 String readFieldName = seseEffectsKey.getFieldDescriptor();
575 HashSet<HeapRegionNode> stallSiteHRNSet = nodeA.getHRNSet();
576 for (Iterator iterator = stallSiteHRNSet.iterator(); iterator
578 HeapRegionNode stallHRN = (HeapRegionNode) iterator.next();
579 if (stallHRN.getGloballyUniqueIdentifier().equals(
582 HashSet<Effect> effectSet = stallSite.getEffectSet();
583 for (Iterator iterator2 = effectSet.iterator(); iterator2
585 Effect effect = (Effect) iterator2.next();
586 String stallEffectfieldName = effect.getField();
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;
605 //System.out.println("%%%%%%%%%%%%%% RETURN conflictType="+conflictType);
609 private int calculateConflictType(LiveInNode nodeA, LiveInNode nodeB) {
611 Set<SESEEffectsKey> readEffectsSetA = nodeA.getReadEffectsSet();
612 Set<SESEEffectsKey> writeEffectsSetA = nodeA.getWriteEffectsSet();
613 Set<SESEEffectsKey> strongUpdateSetA = nodeA.getStrongUpdateSet();
615 Set<SESEEffectsKey> readEffectsSetB = nodeB.getReadEffectsSet();
616 Set<SESEEffectsKey> writeEffectsSetB = nodeB.getWriteEffectsSet();
617 Set<SESEEffectsKey> strongUpdateSetB = nodeB.getStrongUpdateSet();
619 int conflictType = 0;
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
627 String writeHeapRegionID = seseEffectsKey.getHRNUniqueId();
628 String writeFieldName = seseEffectsKey.getFieldDescriptor();
630 if (readEffectsSetB != null) {
632 Iterator<SESEEffectsKey> readIterB = readEffectsSetB
634 while (readIterB.hasNext()) {
635 SESEEffectsKey readingEffect = (SESEEffectsKey) readIterB
638 if (readingEffect.getHRNUniqueId().equals(
640 && readingEffect.getFieldDescriptor().equals(
642 int newType = determineConflictType(nodeA,
643 seseEffectsKey, nodeB, readingEffect);
644 if (newType > conflictType) {
645 // coarse-grain conflict overrides fine-grain
647 conflictType = newType;
654 if (writeEffectsSetB != null) {
655 Iterator<SESEEffectsKey> writeIterB = writeEffectsSetB
657 while (writeIterB.hasNext()) {
658 SESEEffectsKey writingEffect = (SESEEffectsKey) writeIterB
661 if (writingEffect.getHRNUniqueId().equals(
663 && writingEffect.getFieldDescriptor().equals(
665 int newType = determineConflictType(nodeA,
666 seseEffectsKey, nodeB, writingEffect);
667 if (newType > conflictType) {
668 // coarse-grain conflict overrides fine-grain
670 conflictType = newType;
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
687 // if (!hasStrongUpdate(seseEffectsKey, strongUpdateSetB)) {
689 String writeHeapRegionID = seseEffectsKey.getHRNUniqueId();
690 String writeFieldName = seseEffectsKey.getFieldDescriptor();
692 if (readEffectsSetA != null) {
693 Iterator<SESEEffectsKey> readIterA = readEffectsSetA
695 while (readIterA.hasNext()) {
696 SESEEffectsKey readingEffect = (SESEEffectsKey) readIterA
699 if (readingEffect.getHRNUniqueId().equals(
701 && readingEffect.getFieldDescriptor().equals(
703 int newType = determineConflictType(nodeA,
704 readingEffect, nodeB, seseEffectsKey);
705 if (newType > conflictType) {
706 // coarse-grain conflict overrides fine-grain
708 conflictType = newType;
715 if (writeEffectsSetA != null) {
716 Iterator<SESEEffectsKey> writeIterA = writeEffectsSetA
718 while (writeIterA.hasNext()) {
719 SESEEffectsKey writingEffect = (SESEEffectsKey) writeIterA
722 if (writingEffect.getHRNUniqueId().equals(
724 && writingEffect.getFieldDescriptor().equals(
726 int newType = determineConflictType(nodeA,
727 writingEffect, nodeB, seseEffectsKey);
728 if (newType > conflictType) {
729 // coarse-grain conflict overrides fine-grain
731 conflictType = newType;
743 private Set<HeapRegionNode> getSameHeapRoot(Set<HeapRegionNode> setA,
744 Set<HeapRegionNode> setB) {
746 Set<HeapRegionNode> retSet = new HashSet<HeapRegionNode>();
748 if (compareHRNSet(setA, setB)) {
749 for (Iterator iterator = setA.iterator(); iterator.hasNext();) {
750 HeapRegionNode heapRegionNode = (HeapRegionNode) iterator
752 String gID = heapRegionNode.getGloballyUniqueIdentifier();
753 for (Iterator iterator2 = setB.iterator(); iterator2.hasNext();) {
754 HeapRegionNode heapRegionNode2 = (HeapRegionNode) iterator2
756 if (heapRegionNode2.getGloballyUniqueIdentifier().equals(
758 retSet.add(heapRegionNode2);
768 private boolean isReachableFrom(HeapRegionNode root1, HeapRegionNode root2,
769 ReachabilitySet rset) {
771 boolean reachable=false;
773 TokenTuple h1 = new TokenTuple(root1.getID(), !root1.isSingleObject(),
774 TokenTuple.ARITY_ONE).makeCanonical();
776 TokenTuple h1plus = new TokenTuple(root1.getID(), !root1
777 .isSingleObject(), TokenTuple.ARITY_ONEORMORE).makeCanonical();
779 TokenTuple h1star = new TokenTuple(root1.getID(), !root1
780 .isSingleObject(), TokenTuple.ARITY_ZEROORMORE).makeCanonical();
782 TokenTuple h2 = new TokenTuple(root2.getID(), !root2.isSingleObject(),
783 TokenTuple.ARITY_ONE).makeCanonical();
785 TokenTuple h2plus = new TokenTuple(root2.getID(), !root2
786 .isSingleObject(), TokenTuple.ARITY_ONEORMORE).makeCanonical();
788 TokenTuple h2star = new TokenTuple(root2.getID(), !root2
789 .isSingleObject(), TokenTuple.ARITY_ZEROORMORE).makeCanonical();
791 // only do this one if they are different tokens
793 rset.containsTupleSetWithBoth(h1, h2) ) {
796 if( rset.containsTupleSetWithBoth(h1plus, h2) ) {
799 if( rset.containsTupleSetWithBoth(h1star, h2) ) {
802 if( rset.containsTupleSetWithBoth(h1, h2plus) ) {
805 if( rset.containsTupleSetWithBoth(h1plus, h2plus) ) {
808 if( rset.containsTupleSetWithBoth(h1star, h2plus) ) {
811 if( rset.containsTupleSetWithBoth(h1, h2star) ) {
814 if( rset.containsTupleSetWithBoth(h1plus, h2star) ) {
817 if( rset.containsTupleSetWithBoth(h1star, h2star) ) {
825 private int determineConflictType(StallSiteNode stallSiteNodeA,
826 Effect effect, LiveInNode liveInNodeB,
827 SESEEffectsKey effectB) {
829 Set<HeapRegionNode> liveInHrnSetA = stallSiteNodeA.getStallSite().getHRNSet();
830 Set<HeapRegionNode> liveInHrnSetB = liveInNodeB.getHRNSet();
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())){
848 return ConflictEdge.NON_WRITE_CONFLICT;
853 HeapRegionNode r1=liveInHrnSetA.iterator().next();
854 HeapRegionNode r2=liveInHrnSetB.iterator().next();
856 r1=og.gid2hrn.get(r1.getGloballyUniqueIdentifier());
857 r2=og.gid2hrn.get(r2.getGloballyUniqueIdentifier());
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;
868 Set<HeapRegionNode> entryHRNSet = getSameHeapRoot(liveInHrnSetA,
870 if (entryHRNSet.size() == 0) {
871 return ConflictEdge.COARSE_GRAIN_EDGE;
874 for (Iterator iterator = entryHRNSet.iterator(); iterator.hasNext();) {
875 HeapRegionNode hrn = (HeapRegionNode) iterator.next();
877 String entryIdentifier = hrn.getGloballyUniqueIdentifier();
878 HeapRegionNode entryHRN = og.gid2hrn.get(entryIdentifier);
880 TokenTuple h1 = new TokenTuple(entryHRN.getID(), !entryHRN
881 .isSingleObject(), TokenTuple.ARITY_ONE).makeCanonical();
883 TokenTuple h1star = new TokenTuple(entryHRN.getID(), true,
884 TokenTuple.ARITY_ONEORMORE).makeCanonical();
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;
893 return ConflictEdge.NON_WRITE_CONFLICT;
896 private int determineConflictType(LiveInNode liveInNodeA,
897 SESEEffectsKey effectA, LiveInNode liveInNodeB,
898 SESEEffectsKey effectB) {
900 if (liveInNodeA.getSESEIdentifier() == liveInNodeB.getSESEIdentifier()) {
901 return ConflictEdge.NON_WRITE_CONFLICT;
904 Set<HeapRegionNode> liveInHrnSetA = liveInNodeA.getHRNSet();
905 Set<HeapRegionNode> liveInHrnSetB = liveInNodeB.getHRNSet();
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());
918 if(isReachableFrom(r1,r2,effectB.getRSet())){
925 return ConflictEdge.NON_WRITE_CONFLICT;
930 HeapRegionNode r1=liveInHrnSetA.iterator().next();
931 HeapRegionNode r2=liveInHrnSetB.iterator().next();
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());
939 if(!isReachableFrom(r1,r2,effectA.getRSet())){
940 // two heap root are disjoint
941 return ConflictEdge.NON_WRITE_CONFLICT;
945 Set<HeapRegionNode> entryHRNSet = getSameHeapRoot(liveInHrnSetA,
947 if (entryHRNSet.size() == 0 ) {
948 return ConflictEdge.COARSE_GRAIN_EDGE;
950 if(entryHRNSet.size()!=liveInHrnSetA.size() || entryHRNSet.size()!=liveInHrnSetB.size()){
951 return ConflictEdge.COARSE_GRAIN_EDGE;
955 for (Iterator iterator = entryHRNSet.iterator(); iterator.hasNext();) {
956 HeapRegionNode hrn = (HeapRegionNode) iterator.next();
957 if(hrn.getType()!=null && hrn.getType().isImmutable()){
961 if(count==entryHRNSet.size()){
962 return ConflictEdge.FINE_GRAIN_EDGE;
965 for (Iterator iterator = entryHRNSet.iterator(); iterator.hasNext();) {
966 HeapRegionNode hrn = (HeapRegionNode) iterator.next();
968 String entryIdentifier = hrn.getGloballyUniqueIdentifier();
969 HeapRegionNode entryHRN = og.gid2hrn.get(entryIdentifier);
971 TokenTuple h1 = new TokenTuple(entryHRN.getID(), !entryHRN
972 .isSingleObject(), TokenTuple.ARITY_ONE).makeCanonical();
974 TokenTuple h1star = new TokenTuple(entryHRN.getID(), true,
975 TokenTuple.ARITY_ONEORMORE).makeCanonical();
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;
986 return ConflictEdge.NON_WRITE_CONFLICT;
990 private int calculateSelfConflictType(LiveInNode liveInNode) {
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;
998 if (liveInNode.getWriteEffectsSet() != null
999 && liveInNode.getWriteEffectsSet().size() > 0) {
1001 Set<SESEEffectsKey> writeEffectsSet=liveInNode.getWriteEffectsSet();
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()){
1011 if (immuntableCount == liveInNode.getHRNSet().size()) {
1012 // in this case, heap root is a parameter heap region
1013 return ConflictEdge.FINE_GRAIN_EDGE;
1018 for (Iterator<HeapRegionNode> iterator = liveInNode.getHRNSet()
1019 .iterator(); iterator.hasNext();) {
1020 HeapRegionNode root = iterator.next();
1021 if (root.isParameter()) {
1026 if (paramCount == liveInNode.getHRNSet().size()) {
1027 // in this case, heap root is a parameter heap region
1028 return ConflictEdge.FINE_GRAIN_EDGE;
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);
1036 boolean containsStar=false;
1037 for (Iterator iterator = writeEffectsSet.iterator(); iterator
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
1049 return ConflictEdge.COARSE_GRAIN_EDGE;
1051 return ConflictEdge.FINE_GRAIN_EDGE;
1054 return ConflictEdge.COARSE_GRAIN_EDGE;
1059 boolean containsAllTuple=true;
1060 for (Iterator iterator2 = writeEffectsSet.iterator(); iterator2
1062 SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator2
1064 ReachabilitySet rset = seseEffectsKey.getRSet();
1065 Iterator<TokenTupleSet> tsetIter=rset.iterator();
1066 int countNotContained=0;
1067 while (tsetIter.hasNext()) {
1068 TokenTupleSet tokenTupleSet = (TokenTupleSet) tsetIter
1071 for (Iterator iterator = rootIDSet.iterator(); iterator
1073 Integer rootID = (Integer) iterator.next();
1074 if(tokenTupleSet.containsToken(rootID)==null){
1079 countNotContained++;
1082 if(countNotContained==rset.size()){
1083 containsAllTuple=false;
1087 if (containsAllTuple && liveInNode.getHRNSet().size() > 1) {
1088 return ConflictEdge.COARSE_GRAIN_EDGE;
1090 return ConflictEdge.FINE_GRAIN_EDGE;
1098 return ConflictEdge.NON_WRITE_CONFLICT;
1102 public void analyzePossibleConflicts(Set<String> analyzedIDSet,
1103 ConflictNode currentNode) {
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);
1111 addConflictEdge(conflictType, currentNode,
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
1121 String entryNodeID = entry.getKey();
1122 ConflictNode entryNode = entry.getValue();
1124 if ((!currentNode.getID().equals(entryNodeID))
1125 && !(analyzedIDSet.contains(currentNode.getID()
1126 + entryNodeID) || analyzedIDSet
1127 .contains(entryNodeID + currentNode.getID()))) {
1129 if (currentNode instanceof StallSiteNode
1130 && entryNode instanceof LiveInNode) {
1132 int conflictType = calculateConflictType((StallSiteNode) currentNode, (LiveInNode) entryNode);
1133 if (conflictType > 0) {
1134 addConflictEdge(conflictType, currentNode, entryNode);
1137 analyzedIDSet.add(currentNode.getID() + entryNodeID);
1139 } else if (currentNode instanceof LiveInNode
1140 && entryNode instanceof LiveInNode) {
1142 int conflictType = calculateConflictType(
1143 (LiveInNode) currentNode, (LiveInNode) entryNode);
1144 if (conflictType > 0) {
1145 addConflictEdge(conflictType, currentNode, entryNode);
1147 analyzedIDSet.add(currentNode.getID() + entryNodeID);
1158 class ConflictEdge {
1160 private ConflictNode u;
1161 private ConflictNode v;
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;
1168 public ConflictEdge(ConflictNode u, ConflictNode v, int type) {
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\"";
1180 return "CONFLICT\"";
1184 public ConflictNode getVertexU() {
1188 public ConflictNode getVertexV() {
1192 public int getType() {
1196 public String toString() {
1197 return getVertexU() + "-" + getVertexV();