1 package Analysis.OoOJava;
3 import java.io.BufferedWriter;
5 import java.io.FileWriter;
6 import java.util.Collection;
7 import java.util.HashMap;
8 import java.util.HashSet;
9 import java.util.Hashtable;
10 import java.util.Iterator;
13 import java.util.Map.Entry;
15 import IR.ClassDescriptor;
19 import Analysis.Disjoint.Alloc;
20 import Analysis.Disjoint.AllocSite;
21 import Analysis.Disjoint.DisjointAnalysis;
22 import Analysis.Disjoint.Effect;
23 import Analysis.Disjoint.Taint;
24 import IR.Flat.FlatMethod;
25 import IR.Flat.FlatNew;
26 import IR.Flat.FlatNode;
27 import IR.Flat.FlatSESEEnterNode;
28 import IR.Flat.TempDescriptor;
29 import IR.FieldDescriptor;
31 public class ConflictGraph {
33 protected Hashtable<String, ConflictNode> id2cn;
34 protected Hashtable<FlatNode, Hashtable<Taint, Set<Effect>>> sese2te;
36 protected DisjointAnalysis da;
37 protected FlatMethod fmEnclosing;
39 public static final int NON_WRITE_CONFLICT = 0;
40 public static final int FINE_GRAIN_EDGE = 1;
41 public static final int COARSE_GRAIN_EDGE = 2;
45 public ConflictGraph(State state) {
47 id2cn = new Hashtable<String, ConflictNode>();
48 sese2te = new Hashtable<FlatNode, Hashtable<Taint, Set<Effect>>>();
51 public void setDisJointAnalysis(DisjointAnalysis da) {
55 public void setFMEnclosing(FlatMethod fmEnclosing) {
56 this.fmEnclosing = fmEnclosing;
59 public void addLiveIn(Hashtable<Taint, Set<Effect>> taint2Effects) {
60 if (taint2Effects == null) {
63 Iterator entryIter = taint2Effects.entrySet().iterator();
64 while (entryIter.hasNext()) {
65 Entry entry = (Entry) entryIter.next();
66 Taint taint = (Taint) entry.getKey();
67 Set<Effect> effectSet = (Set<Effect>)entry.getValue();
68 if (!effectSet.isEmpty()) {
69 Iterator<Effect> effectIter = effectSet.iterator();
70 while (effectIter.hasNext()) {
71 Effect effect = (Effect) effectIter.next();
72 addLiveInNodeEffect(taint, effect);
78 public void addStallSite(Hashtable<Taint, Set<Effect>> taint2Effects, TempDescriptor var,
80 if (taint2Effects == null) {
83 Iterator entryIter = taint2Effects.entrySet().iterator();
84 while (entryIter.hasNext()) {
85 Entry entry = (Entry) entryIter.next();
86 Taint taint = (Taint) entry.getKey();
87 Set<Effect> effectSet = (Set<Effect>)entry.getValue();
88 if (!effectSet.isEmpty()) {
89 Iterator<Effect> effectIter = effectSet.iterator();
90 while (effectIter.hasNext()) {
91 Effect effect = (Effect) effectIter.next();
92 if (taint.getVar().equals(var)) {
93 addStallSiteEffect(taint, effect, cd);
100 public void addStallSiteEffect(Taint t, Effect e, ClassDescriptor cd) {
101 FlatNode fn = t.getStallSite();
102 TempDescriptor var = t.getVar();
103 Alloc as = t.getAllocSite();
105 String id = var + "_fn" + fn.hashCode();
106 ConflictNode node = id2cn.get(id);
108 node = new ConflictNode(id, ConflictNode.STALLSITE, t.getVar(), t.getStallSite(), cd);
110 node.addEffect(as, e);
115 public void addLiveInNodeEffect(Taint t, Effect e) {
117 FlatSESEEnterNode sese = t.getSESE();
118 TempDescriptor invar = t.getVar();
119 Alloc as = t.getAllocSite();
121 String id = invar + "_sese" + sese.getPrettyIdentifier();
122 ConflictNode node = id2cn.get(id);
124 node = new ConflictNode(id, ConflictNode.INVAR, t.getVar(), t.getSESE());
126 node.addEffect(as, e);
133 public void addConflictEdge(int type, ConflictNode nodeU, ConflictNode nodeV) {
135 // if there are two edges between the same node pair, coarse has a
137 Set<ConflictEdge> set = nodeU.getEdgeSet();
138 ConflictEdge toBeRemoved = null;
139 for (Iterator iterator = set.iterator(); iterator.hasNext(); ) {
140 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
142 if ((conflictEdge.getVertexU().equals(nodeU) && conflictEdge.getVertexV().equals(nodeV))
143 || (conflictEdge.getVertexU().equals(nodeV) && conflictEdge.getVertexV().equals(nodeU))) {
144 if (conflictEdge.getType() == ConflictGraph.FINE_GRAIN_EDGE
145 && type == ConflictGraph.COARSE_GRAIN_EDGE) {
146 toBeRemoved = conflictEdge;
148 } else if (conflictEdge.getType() == ConflictGraph.COARSE_GRAIN_EDGE
149 && type == ConflictGraph.FINE_GRAIN_EDGE) {
156 if (toBeRemoved != null) {
157 nodeU.getEdgeSet().remove(toBeRemoved);
158 nodeV.getEdgeSet().remove(toBeRemoved);
161 ConflictEdge newEdge = new ConflictEdge(nodeU, nodeV, type);
162 nodeU.addEdge(newEdge);
163 nodeV.addEdge(newEdge);
167 public void analyzeConflicts(Set<FlatNew> sitesToFlag, boolean useReachInfo) {
169 Set<String> keySet = id2cn.keySet();
170 Set<String> analyzedIDSet = new HashSet<String>();
172 for (Iterator iterator = keySet.iterator(); iterator.hasNext(); ) {
173 String nodeID = (String) iterator.next();
174 ConflictNode node = id2cn.get(nodeID);
175 analyzePossibleConflicts(analyzedIDSet, node, sitesToFlag, useReachInfo);
180 private void analyzePossibleConflicts(Set<String> analyzedIDSet, ConflictNode currentNode,
181 Set<FlatNew> sitesToFlag, boolean useReachInfo) {
182 // compare with all nodes
183 // examine the case where self-edge exists
186 if (currentNode.isInVarNode()) {
187 conflictType = calculateConflictType(currentNode, useReachInfo);
188 if (conflictType > ConflictGraph.NON_WRITE_CONFLICT) {
189 addConflictEdge(conflictType, currentNode, currentNode);
190 if (sitesToFlag != null) {
191 sitesToFlag.addAll(currentNode.getFlatNewSet());
196 Set<Entry<String, ConflictNode>> set = id2cn.entrySet();
197 for (Iterator iterator = set.iterator(); iterator.hasNext(); ) {
198 Entry<String, ConflictNode> entry = (Entry<String, ConflictNode>)iterator.next();
200 String entryNodeID = entry.getKey();
201 ConflictNode entryNode = entry.getValue();
203 if (currentNode.isStallSiteNode() && entryNode.isStallSiteNode()) {
207 if ((currentNode.isInVarNode() && entryNode.isInVarNode())
208 && (currentNode.getSESEIdentifier() == entryNode.getSESEIdentifier())
209 && (currentNode.getVar().equals(entryNode.getVar()))) {
213 if ((!currentNode.getID().equals(entryNodeID))
214 && !(analyzedIDSet.contains(currentNode.getID() + entryNodeID) || analyzedIDSet
215 .contains(entryNodeID + currentNode.getID()))) {
217 conflictType = calculateConflictType(currentNode, entryNode, useReachInfo);
218 if (conflictType > ConflictGraph.NON_WRITE_CONFLICT) {
219 addConflictEdge(conflictType, currentNode, entryNode);
220 if (sitesToFlag != null) {
221 sitesToFlag.addAll(currentNode.getFlatNewSet());
222 sitesToFlag.addAll(entryNode.getFlatNewSet());
225 analyzedIDSet.add(currentNode.getID() + entryNodeID);
232 private int calculateConflictType(ConflictNode node, boolean useReachInfo) {
234 int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
236 Hashtable<Alloc, Set<Effect>> alloc2readEffects = node.getReadEffectSet();
237 Hashtable<Alloc, Set<Effect>> alloc2writeEffects = node.getWriteEffectSet();
238 Hashtable<Alloc, Set<Effect>> alloc2SUEffects = node.getStrongUpdateEffectSet();
241 updateConflictType(conflictType,
242 determineConflictType(node, alloc2writeEffects, node, alloc2writeEffects, useReachInfo));
247 hasStrongUpdateConflicts(node, alloc2SUEffects, node, alloc2readEffects,
248 alloc2writeEffects, useReachInfo));
253 private int calculateConflictType(ConflictNode nodeA, ConflictNode nodeB, boolean useReachInfo) {
255 int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
257 Hashtable<Alloc, Set<Effect>> alloc2readEffectsA = nodeA.getReadEffectSet();
258 Hashtable<Alloc, Set<Effect>> alloc2writeEffectsA = nodeA.getWriteEffectSet();
259 Hashtable<Alloc, Set<Effect>> alloc2SUEffectsA = nodeA.getStrongUpdateEffectSet();
260 Hashtable<Alloc, Set<Effect>> alloc2readEffectsB = nodeB.getReadEffectSet();
261 Hashtable<Alloc, Set<Effect>> alloc2writeEffectsB = nodeB.getWriteEffectSet();
262 Hashtable<Alloc, Set<Effect>> alloc2SUEffectsB = nodeB.getStrongUpdateEffectSet();
264 // if node A has write effects on reading/writing regions of node B
268 determineConflictType(nodeA, alloc2writeEffectsA, nodeB, alloc2readEffectsB,
273 determineConflictType(nodeA, alloc2writeEffectsA, nodeB, alloc2writeEffectsB,
276 // if node B has write effects on reading regions of node A
280 determineConflictType(nodeB, alloc2writeEffectsB, nodeA, alloc2readEffectsA,
283 // strong udpate effects conflict with all effects
284 // on objects that are reachable from the same heap roots
285 // if node A has SU on regions of node B
286 if (!alloc2SUEffectsA.isEmpty()) {
290 hasStrongUpdateConflicts(nodeA, alloc2SUEffectsA, nodeB, alloc2readEffectsB,
291 alloc2writeEffectsB, useReachInfo));
294 // if node B has SU on regions of node A
295 if (!alloc2SUEffectsB.isEmpty()) {
299 hasStrongUpdateConflicts(nodeB, alloc2SUEffectsB, nodeA, alloc2readEffectsA,
300 alloc2writeEffectsA, useReachInfo));
306 private int hasStrongUpdateConflicts(ConflictNode nodeA,
307 Hashtable<Alloc, Set<Effect>> SUEffectsTableA, ConflictNode nodeB,
308 Hashtable<Alloc, Set<Effect>> readTableB, Hashtable<Alloc, Set<Effect>> writeTableB,
309 boolean useReachInfo) {
311 int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
313 Iterator effectItrA = SUEffectsTableA.entrySet().iterator();
314 while (effectItrA.hasNext()) {
315 Map.Entry meA = (Map.Entry)effectItrA.next();
316 Alloc asA = (Alloc) meA.getKey();
317 Set<Effect> strongUpdateSetA = (Set<Effect>)meA.getValue();
319 Iterator effectItrB = readTableB.entrySet().iterator();
320 while (effectItrB.hasNext()) {
321 Map.Entry meB = (Map.Entry)effectItrB.next();
322 Alloc asB = (Alloc) meB.getKey();
323 Set<Effect> esB = (Set<Effect>)meB.getValue();
325 for (Iterator iterator = strongUpdateSetA.iterator(); iterator.hasNext(); ) {
326 Effect strongUpdateA = (Effect) iterator.next();
327 for (Iterator iterator2 = esB.iterator(); iterator2.hasNext(); ) {
328 Effect effectB = (Effect) iterator2.next();
330 if (strongUpdateA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite())
331 && strongUpdateA.getField().equals(effectB.getField())) {
333 FlatNew fnRoot1 = asA.getFlatNew();
334 FlatNew fnRoot2 = asB.getFlatNew();
335 FlatNew fnTarget = strongUpdateA.getAffectedAllocSite().getFlatNew();
336 if (da.mayBothReachTarget(fmEnclosing, fnRoot1, fnRoot2, fnTarget)) {
337 addCoarseEffect(nodeA, asA, strongUpdateA);
338 if (!nodeA.equals(nodeB)) {
339 addCoarseEffect(nodeB, asB, effectB);
341 conflictType = updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
345 // need coarse effects for RCR from just one pass
346 addCoarseEffect(nodeA, asA, strongUpdateA);
347 if (!nodeA.equals(nodeB)) {
348 addCoarseEffect(nodeB, asB, effectB);
350 conflictType = ConflictGraph.COARSE_GRAIN_EDGE;
352 return ConflictGraph.COARSE_GRAIN_EDGE;
362 effectItrB = writeTableB.entrySet().iterator();
363 while (effectItrB.hasNext()) {
364 Map.Entry meB = (Map.Entry)effectItrB.next();
365 Alloc asB = (Alloc) meB.getKey();
366 Set<Effect> esB = (Set<Effect>)meB.getValue();
368 for (Iterator iterator = strongUpdateSetA.iterator(); iterator.hasNext(); ) {
369 Effect strongUpdateA = (Effect) iterator.next();
370 for (Iterator iterator2 = esB.iterator(); iterator2.hasNext(); ) {
371 Effect effectB = (Effect) iterator2.next();
373 if (strongUpdateA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite())
374 && strongUpdateA.getField().equals(effectB.getField())) {
377 FlatNew fnRoot1 = asA.getFlatNew();
378 FlatNew fnRoot2 = asB.getFlatNew();
379 FlatNew fnTarget = strongUpdateA.getAffectedAllocSite().getFlatNew();
380 if (da.mayBothReachTarget(fmEnclosing, fnRoot1, fnRoot2, fnTarget)) {
381 addCoarseEffect(nodeA, asA, strongUpdateA);
382 if (!nodeA.equals(nodeB)) {
383 addCoarseEffect(nodeB, asB, effectB);
385 conflictType = updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
388 return ConflictGraph.COARSE_GRAIN_EDGE;
402 private int determineConflictType(ConflictNode nodeA, Hashtable<Alloc, Set<Effect>> nodeAtable,
403 ConflictNode nodeB, Hashtable<Alloc, Set<Effect>> nodeBtable, boolean useReachInfo) {
405 int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
407 Iterator effectItrA = nodeAtable.entrySet().iterator();
408 while (effectItrA.hasNext()) {
409 Map.Entry meA = (Map.Entry)effectItrA.next();
410 Alloc asA = (Alloc) meA.getKey();
411 Set<Effect> esA = (Set<Effect>)meA.getValue();
413 Iterator effectItrB = nodeBtable.entrySet().iterator();
414 while (effectItrB.hasNext()) {
415 Map.Entry meB = (Map.Entry)effectItrB.next();
416 Alloc asB = (Alloc) meB.getKey();
417 Set<Effect> esB = (Set<Effect>)meB.getValue();
419 for (Iterator iterator = esA.iterator(); iterator.hasNext(); ) {
420 Effect effectA = (Effect) iterator.next();
421 for (Iterator iterator2 = esB.iterator(); iterator2.hasNext(); ) {
422 Effect effectB = (Effect) iterator2.next();
424 if (effectA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite())
425 && ((effectA.getField() != null && effectB.getField() != null && effectA.getField()
426 .equals(effectB.getField())) || (effectA.getField() == null && effectB
427 .getField() == null))) {
430 FlatNew fnRoot1 = asA.getFlatNew();
431 FlatNew fnRoot2 = asB.getFlatNew();
432 FlatNew fnTarget = effectA.getAffectedAllocSite().getFlatNew();
433 if (fnRoot1.equals(fnRoot2)) {
434 if (!da.mayManyReachTarget(fmEnclosing, fnRoot1, fnTarget)) {
435 // fine-grained conflict case
436 conflictType = updateConflictType(conflictType, ConflictGraph.FINE_GRAIN_EDGE);
438 // coarse-grained conflict case
439 addCoarseEffect(nodeA, asA, effectA);
440 if (!nodeA.equals(nodeB)) {
441 addCoarseEffect(nodeB, asB, effectB);
444 updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
447 if (da.mayBothReachTarget(fmEnclosing, fnRoot1, fnRoot2, fnTarget)) {
448 addCoarseEffect(nodeA, asA, effectA);
449 if (!nodeA.equals(nodeB)) {
450 addCoarseEffect(nodeB, asB, effectB);
453 updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
459 // need coarse effects for RCR from just one pass
460 addCoarseEffect(nodeA, asA, effectA);
461 if (!nodeA.equals(nodeB)) {
462 addCoarseEffect(nodeB, asB, effectB);
464 conflictType = ConflictGraph.COARSE_GRAIN_EDGE;
466 return ConflictGraph.COARSE_GRAIN_EDGE;
478 private void addCoarseEffect(ConflictNode node, Alloc as, Effect e) {
479 Taint t = node.getTaint(as);
480 addEffectSetByTaint(t, e);
483 private void addEffectSetByTaint(Taint t, Effect e) {
485 FlatNode node = t.getSESE();
488 node = t.getStallSite();
491 Hashtable<Taint, Set<Effect>> taint2Conflicts = sese2te.get(node);
492 if (taint2Conflicts == null) {
493 taint2Conflicts = new Hashtable<Taint, Set<Effect>>();
496 Set<Effect> effectSet = taint2Conflicts.get(t);
497 if (effectSet == null) {
498 effectSet = new HashSet<Effect>();
501 taint2Conflicts.put(t, effectSet);
503 sese2te.put(node, taint2Conflicts);
507 private int updateConflictType(int current, int newType) {
508 if (newType > current) {
515 public void clearAllConflictEdge() {
516 Collection<ConflictNode> nodes = id2cn.values();
517 for (Iterator iterator = nodes.iterator(); iterator.hasNext(); ) {
518 ConflictNode conflictNode = (ConflictNode) iterator.next();
519 conflictNode.getEdgeSet().clear();
523 public HashSet<ConflictEdge> getEdgeSet() {
525 HashSet<ConflictEdge> returnSet = new HashSet<ConflictEdge>();
527 Collection<ConflictNode> nodes = id2cn.values();
528 for (Iterator iterator = nodes.iterator(); iterator.hasNext(); ) {
529 ConflictNode conflictNode = (ConflictNode) iterator.next();
530 returnSet.addAll(conflictNode.getEdgeSet());
536 public boolean hasConflictEdge() {
538 Set<String> keySet = id2cn.keySet();
539 for (Iterator iterator = keySet.iterator(); iterator.hasNext(); ) {
540 String key = (String) iterator.next();
541 ConflictNode node = id2cn.get(key);
542 if (node.getEdgeSet().size() > 0) {
549 public boolean isFineElement(int type) {
550 if (type == ConflictNode.FINE_READ || type == ConflictNode.FINE_WRITE
551 || type == ConflictNode.PARENT_READ || type == ConflictNode.PARENT_WRITE) {
558 public SESEWaitingQueue getWaitingElementSetBySESEID(int seseID, Set<SESELock> seseLockSet) {
560 HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
562 Iterator iter = id2cn.entrySet().iterator();
563 while (iter.hasNext()) {
564 Entry entry = (Entry) iter.next();
565 String conflictNodeID = (String) entry.getKey();
566 ConflictNode node = (ConflictNode) entry.getValue();
568 if (node.isInVarNode()) {
569 if (node.getSESEIdentifier() == seseID) {
571 Set<ConflictEdge> edgeSet = node.getEdgeSet();
572 for (Iterator iterator = edgeSet.iterator(); iterator.hasNext(); ) {
573 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
575 for (Iterator<SESELock> seseLockIter = seseLockSet.iterator(); seseLockIter.hasNext(); ) {
576 SESELock seseLock = seseLockIter.next();
577 if (seseLock.containsConflictNode(node)
578 && seseLock.containsConflictEdge(conflictEdge)) {
579 WaitingElement newElement = new WaitingElement();
580 newElement.setQueueID(seseLock.getID());
581 newElement.setStatus(seseLock.getNodeType(node));
582 newElement.setTempDesc(node.getVar());
583 if (isFineElement(newElement.getStatus())) {
584 newElement.setDynID(node.getVar().toString());
586 if (!waitingElementSet.contains(newElement)) {
587 waitingElementSet.add(newElement);
599 // handle the case that multiple enqueues by an SESE for different live-in
600 // into the same queue
601 return refineQueue(waitingElementSet);
605 public SESEWaitingQueue refineQueue(Set<WaitingElement> waitingElementSet) {
607 Set<WaitingElement> refinedSet = new HashSet<WaitingElement>();
608 HashMap<Integer, Set<WaitingElement>> map = new HashMap<Integer, Set<WaitingElement>>();
609 SESEWaitingQueue seseDS = new SESEWaitingQueue();
611 for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext(); ) {
612 WaitingElement waitingElement = (WaitingElement) iterator.next();
613 Set<WaitingElement> set = map.get(new Integer(waitingElement.getQueueID()));
615 set = new HashSet<WaitingElement>();
617 set.add(waitingElement);
618 map.put(new Integer(waitingElement.getQueueID()), set);
621 Set<Integer> keySet = map.keySet();
622 for (Iterator iterator = keySet.iterator(); iterator.hasNext(); ) {
623 Integer queueID = (Integer) iterator.next();
624 Set<WaitingElement> queueWEset = map.get(queueID);
625 refineQueue(queueID.intValue(), queueWEset, seseDS);
631 private void refineQueue(int queueID, Set<WaitingElement> waitingElementSet,
632 SESEWaitingQueue seseDS) {
634 if (waitingElementSet.size() > 1) {
635 // only consider there is more than one element submitted by same SESE
636 Set<WaitingElement> refinedSet = new HashSet<WaitingElement>();
641 int total = waitingElementSet.size();
642 WaitingElement SCCelement = null;
643 WaitingElement coarseElement = null;
645 for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext(); ) {
646 WaitingElement waitingElement = (WaitingElement) iterator.next();
647 if (waitingElement.getStatus() == ConflictNode.FINE_READ) {
649 } else if (waitingElement.getStatus() == ConflictNode.FINE_WRITE) {
651 } else if (waitingElement.getStatus() == ConflictNode.COARSE) {
653 coarseElement = waitingElement;
654 } else if (waitingElement.getStatus() == ConflictNode.SCC) {
655 SCCelement = waitingElement;
658 if (SCCelement != null) {
659 // if there is at lease one SCC element, just enqueue SCC and
662 // for rcr, we need to label all of coarse tempdescriptors
663 // here assume that all waiting elements are coarse
664 for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext(); ) {
665 WaitingElement waitingElement = (WaitingElement) iterator.next();
666 SCCelement.addTempDesc(waitingElement.getTempDesc());
667 if (waitingElement != SCCelement) {
668 waitingElement.setBogus(true);
669 refinedSet.add(waitingElement);
673 refinedSet.add(SCCelement);
674 } else if (numCoarse == 1 && (numRead + numWrite == total)) {
675 // if one is a coarse, the othere are reads/write, enqueue SCC.
676 WaitingElement we = new WaitingElement();
677 we.setQueueID(queueID);
678 we.setStatus(ConflictNode.SCC);
680 } else if (numCoarse == total) {
681 // if there are multiple coarses, enqueue just one coarse.
683 // for rcr, we need to label all of coarse tempdescriptors
684 for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext(); ) {
685 WaitingElement waitingElement = (WaitingElement) iterator.next();
686 if (waitingElement != coarseElement) {
687 coarseElement.addTempDesc(waitingElement.getTempDesc());
688 waitingElement.setBogus(true);
689 refinedSet.add(waitingElement);
693 refinedSet.add(coarseElement);
694 } else if (numWrite == total || (numRead + numWrite) == total) {
695 // code generator is going to handle the case for multiple writes &
697 seseDS.setType(queueID, SESEWaitingQueue.EXCEPTION);
698 refinedSet.addAll(waitingElementSet);
700 // otherwise, enqueue everything.
701 refinedSet.addAll(waitingElementSet);
703 seseDS.setWaitingElementSet(queueID, refinedSet);
705 seseDS.setWaitingElementSet(queueID, waitingElementSet);
710 public Set<WaitingElement> getStallSiteWaitingElementSet(FlatNode stallSite,
711 Set<SESELock> seseLockSet) {
713 HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
714 Iterator iter = id2cn.entrySet().iterator();
715 while (iter.hasNext()) {
716 Entry entry = (Entry) iter.next();
717 String conflictNodeID = (String) entry.getKey();
718 ConflictNode node = (ConflictNode) entry.getValue();
720 if (node.isStallSiteNode() && node.getStallSiteFlatNode().equals(stallSite)) {
721 Set<ConflictEdge> edgeSet = node.getEdgeSet();
722 for (Iterator iter2 = edgeSet.iterator(); iter2.hasNext(); ) {
723 ConflictEdge conflictEdge = (ConflictEdge) iter2.next();
725 for (Iterator<SESELock> seseLockIter = seseLockSet.iterator(); seseLockIter.hasNext(); ) {
726 SESELock seseLock = seseLockIter.next();
727 if (seseLock.containsConflictNode(node) && seseLock.containsConflictEdge(conflictEdge)) {
728 WaitingElement newElement = new WaitingElement();
729 newElement.setQueueID(seseLock.getID());
730 newElement.setStatus(seseLock.getNodeType(node));
731 if (isFineElement(newElement.getStatus())) {
732 newElement.setDynID(node.getVar().toString());
734 newElement.setTempDesc(node.getVar());
735 waitingElementSet.add(newElement);
745 return waitingElementSet;
748 public Hashtable<Taint, Set<Effect>> getConflictEffectSet(FlatNode fn) {
749 return sese2te.get(fn);
752 public void writeGraph(String graphName, boolean filter) throws java.io.IOException {
754 graphName = graphName.replaceAll("[\\W]", "");
756 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
757 bw.write("graph " + graphName + " {\n");
759 // then visit every heap region node
760 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
761 Iterator<Entry<String, ConflictNode>> i = s.iterator();
763 HashSet<ConflictEdge> addedSet = new HashSet<ConflictEdge>();
765 while (i.hasNext()) {
766 Entry<String, ConflictNode> entry = i.next();
767 ConflictNode node = entry.getValue();
770 if (node.getID().startsWith("___dst") || node.getID().startsWith("___srctmp")
771 || node.getID().startsWith("___neverused") || node.getID().startsWith("___temp")) {
776 if (node.getEdgeSet().isEmpty()) {
782 String attributes = "[";
784 attributes += "label=\"" + node.getID() + "\\n";
786 if (node.isStallSiteNode()) {
787 String srcFileName = node.getSourceFileName();
788 int separatorIdx = srcFileName.lastIndexOf(File.separator);
789 if (separatorIdx > 0) {
790 srcFileName = srcFileName.substring(separatorIdx + 1);
792 node.stallSite.getNumLine();
794 "STALL SITE" + "\\n" + srcFileName + ":" + node.getStallSiteFlatNode().getNumLine()
797 attributes += "LIVE-IN" + "\\n" + "\"]";
799 bw.write(entry.getKey() + attributes + ";\n");
801 Set<ConflictEdge> edgeSet = node.getEdgeSet();
802 for (Iterator iterator = edgeSet.iterator(); iterator.hasNext(); ) {
803 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
805 ConflictNode u = conflictEdge.getVertexU();
806 ConflictNode v = conflictEdge.getVertexV();
809 String uID = u.getID();
810 String vID = v.getID();
811 if (uID.startsWith("___dst") || uID.startsWith("___srctmp")
812 || uID.startsWith("___neverused") || uID.startsWith("___temp")
813 || vID.startsWith("___dst") || vID.startsWith("___srctmp")
814 || vID.startsWith("___neverused") || vID.startsWith("___temp")) {
819 if (!addedSet.contains(conflictEdge)) {
820 bw.write("" + u.getID() + "--" + v.getID() + "[label=" + conflictEdge.toGraphEdgeString()
822 addedSet.add(conflictEdge);
828 bw.write(" graphTitle[label=\"" + graphName + "\",shape=box];\n");
835 public Hashtable<String, ConflictNode> getId2cn() {