1 package Analysis.OoOJava;
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;
12 import java.util.Map.Entry;
15 import Analysis.Disjoint.AllocSite;
16 import Analysis.Disjoint.DisjointAnalysis;
17 import Analysis.Disjoint.Effect;
18 import Analysis.Disjoint.Taint;
19 import IR.Flat.FlatMethod;
20 import IR.Flat.FlatNew;
21 import IR.Flat.FlatNode;
22 import IR.Flat.FlatSESEEnterNode;
23 import IR.Flat.TempDescriptor;
25 public class ConflictGraph {
27 protected Hashtable<String, ConflictNode> id2cn;
28 protected Hashtable<FlatNode, Hashtable<Taint, Set<Effect>>> sese2te;
30 protected DisjointAnalysis da;
31 protected FlatMethod fmEnclosing;
33 public static final int NON_WRITE_CONFLICT = 0;
34 public static final int FINE_GRAIN_EDGE = 1;
35 public static final int COARSE_GRAIN_EDGE = 2;
39 public ConflictGraph(State state) {
41 id2cn = new Hashtable<String, ConflictNode>();
42 sese2te = new Hashtable<FlatNode, Hashtable<Taint, Set<Effect>>>();
45 public void setDisJointAnalysis(DisjointAnalysis da) {
49 public void setFMEnclosing(FlatMethod fmEnclosing) {
50 this.fmEnclosing = fmEnclosing;
53 public void addLiveIn(Hashtable<Taint, Set<Effect>> taint2Effects) {
54 if (taint2Effects == null) {
57 Iterator entryIter = taint2Effects.entrySet().iterator();
58 while (entryIter.hasNext()) {
59 Entry entry = (Entry) entryIter.next();
60 Taint taint = (Taint) entry.getKey();
61 Set<Effect> effectSet = (Set<Effect>) entry.getValue();
62 if (!effectSet.isEmpty()) {
63 Iterator<Effect> effectIter = effectSet.iterator();
64 while (effectIter.hasNext()) {
65 Effect effect = (Effect) effectIter.next();
66 addLiveInNodeEffect(taint, effect);
72 public void addStallSite(Hashtable<Taint, Set<Effect>> taint2Effects, TempDescriptor var) {
73 if (taint2Effects == null) {
76 Iterator entryIter = taint2Effects.entrySet().iterator();
77 while (entryIter.hasNext()) {
78 Entry entry = (Entry) entryIter.next();
79 Taint taint = (Taint) entry.getKey();
80 Set<Effect> effectSet = (Set<Effect>) entry.getValue();
81 if (!effectSet.isEmpty()) {
82 Iterator<Effect> effectIter = effectSet.iterator();
83 while (effectIter.hasNext()) {
84 Effect effect = (Effect) effectIter.next();
85 if (taint.getVar().equals(var)) {
86 addStallSiteEffect(taint, effect);
93 public void addStallSiteEffect(Taint t, Effect e) {
94 FlatNode fn = t.getStallSite();
95 TempDescriptor var = t.getVar();
96 AllocSite as = t.getAllocSite();
98 String id = var + "_fn" + fn.hashCode();
99 ConflictNode node = id2cn.get(id);
101 node = new ConflictNode(id, ConflictNode.STALLSITE, t.getVar(), t.getStallSite());
103 node.addEffect(as, e);
109 public void addLiveInNodeEffect(Taint t, Effect e) {
111 FlatSESEEnterNode sese = t.getSESE();
112 TempDescriptor invar = t.getVar();
113 AllocSite as = t.getAllocSite();
115 String id = invar + "_sese" + sese.getPrettyIdentifier();
116 ConflictNode node = id2cn.get(id);
118 node = new ConflictNode(id, ConflictNode.INVAR, t.getVar(), t.getSESE());
120 node.addEffect(as, e);
126 public void addConflictEdge(int type, ConflictNode nodeU, ConflictNode nodeV) {
128 // if there are two edges between the same node pair, coarse has a
130 Set<ConflictEdge> set = nodeU.getEdgeSet();
131 ConflictEdge toBeRemoved = null;
132 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
133 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
135 if ((conflictEdge.getVertexU().equals(nodeU) && conflictEdge.getVertexV().equals(nodeV))
136 || (conflictEdge.getVertexU().equals(nodeV) && conflictEdge.getVertexV().equals(nodeU))) {
137 if (conflictEdge.getType() == ConflictGraph.FINE_GRAIN_EDGE
138 && type == ConflictGraph.COARSE_GRAIN_EDGE) {
139 toBeRemoved = conflictEdge;
141 } else if (conflictEdge.getType() == ConflictGraph.COARSE_GRAIN_EDGE
142 && type == ConflictGraph.FINE_GRAIN_EDGE) {
149 if (toBeRemoved != null) {
150 nodeU.getEdgeSet().remove(toBeRemoved);
151 nodeV.getEdgeSet().remove(toBeRemoved);
154 ConflictEdge newEdge = new ConflictEdge(nodeU, nodeV, type);
155 nodeU.addEdge(newEdge);
156 nodeV.addEdge(newEdge);
160 public void analyzeConflicts(Set<FlatNew> sitesToFlag, boolean useReachInfo) {
162 Set<String> keySet = id2cn.keySet();
163 Set<String> analyzedIDSet = new HashSet<String>();
165 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
166 String nodeID = (String) iterator.next();
167 ConflictNode node = id2cn.get(nodeID);
168 analyzePossibleConflicts(analyzedIDSet, node, sitesToFlag, useReachInfo);
173 private void analyzePossibleConflicts(Set<String> analyzedIDSet, ConflictNode currentNode,
174 Set<FlatNew> sitesToFlag, boolean useReachInfo) {
175 // compare with all nodes
176 // examine the case where self-edge exists
179 if (currentNode.isInVarNode()) {
180 conflictType = calculateConflictType(currentNode, useReachInfo);
181 if (conflictType > ConflictGraph.NON_WRITE_CONFLICT) {
182 addConflictEdge(conflictType, currentNode, currentNode);
183 if (sitesToFlag != null) {
184 sitesToFlag.addAll(currentNode.getFlatNewSet());
189 Set<Entry<String, ConflictNode>> set = id2cn.entrySet();
190 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
191 Entry<String, ConflictNode> entry = (Entry<String, ConflictNode>) iterator.next();
193 String entryNodeID = entry.getKey();
194 ConflictNode entryNode = entry.getValue();
196 if (currentNode.isStallSiteNode() && entryNode.isStallSiteNode()) {
200 if ((currentNode.isInVarNode() && entryNode.isInVarNode())
201 && (currentNode.getSESEIdentifier() == entryNode.getSESEIdentifier())
202 && (currentNode.getVar().equals(entryNode.getVar()))) {
206 if ((!currentNode.getID().equals(entryNodeID))
207 && !(analyzedIDSet.contains(currentNode.getID() + entryNodeID) || analyzedIDSet
208 .contains(entryNodeID + currentNode.getID()))) {
210 conflictType = calculateConflictType(currentNode, entryNode, useReachInfo);
211 if (conflictType > ConflictGraph.NON_WRITE_CONFLICT) {
212 addConflictEdge(conflictType, currentNode, entryNode);
213 if (sitesToFlag != null) {
214 sitesToFlag.addAll(currentNode.getFlatNewSet());
215 sitesToFlag.addAll(entryNode.getFlatNewSet());
218 analyzedIDSet.add(currentNode.getID() + entryNodeID);
225 private int calculateConflictType(ConflictNode node, boolean useReachInfo) {
227 int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
228 Hashtable<AllocSite, Set<Effect>> alloc2readEffects = node.getReadEffectSet();
229 Hashtable<AllocSite, Set<Effect>> alloc2writeEffects = node.getWriteEffectSet();
230 Hashtable<AllocSite, Set<Effect>> alloc2SUEffects = node.getStrongUpdateEffectSet();
233 updateConflictType(conflictType, determineConflictType(node, alloc2writeEffects, node,
234 alloc2writeEffects, useReachInfo));
237 updateConflictType(conflictType, hasStrongUpdateConflicts(node, alloc2SUEffects, node,
238 alloc2readEffects, alloc2writeEffects, useReachInfo));
243 private int calculateConflictType(ConflictNode nodeA, ConflictNode nodeB, boolean useReachInfo) {
245 int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
247 Hashtable<AllocSite, Set<Effect>> alloc2readEffectsA = nodeA.getReadEffectSet();
248 Hashtable<AllocSite, Set<Effect>> alloc2writeEffectsA = nodeA.getWriteEffectSet();
249 Hashtable<AllocSite, Set<Effect>> alloc2SUEffectsA = nodeA.getStrongUpdateEffectSet();
250 Hashtable<AllocSite, Set<Effect>> alloc2readEffectsB = nodeB.getReadEffectSet();
251 Hashtable<AllocSite, Set<Effect>> alloc2writeEffectsB = nodeB.getWriteEffectSet();
252 Hashtable<AllocSite, Set<Effect>> alloc2SUEffectsB = nodeB.getStrongUpdateEffectSet();
254 // if node A has write effects on reading/writing regions of node B
256 updateConflictType(conflictType, determineConflictType(nodeA, alloc2writeEffectsA, nodeB,
257 alloc2readEffectsB, useReachInfo));
259 updateConflictType(conflictType, determineConflictType(nodeA, alloc2writeEffectsA, nodeB,
260 alloc2writeEffectsB, useReachInfo));
262 // if node B has write effects on reading regions of node A
264 updateConflictType(conflictType, determineConflictType(nodeB, alloc2writeEffectsB, nodeA,
265 alloc2readEffectsA, useReachInfo));
267 // strong udpate effects conflict with all effects
268 // on objects that are reachable from the same heap roots
269 // if node A has SU on regions of node B
270 if (!alloc2SUEffectsA.isEmpty()) {
272 updateConflictType(conflictType, hasStrongUpdateConflicts(nodeA, alloc2SUEffectsA, nodeB,
273 alloc2readEffectsB, alloc2writeEffectsB, useReachInfo));
276 // if node B has SU on regions of node A
277 if (!alloc2SUEffectsB.isEmpty()) {
279 updateConflictType(conflictType, hasStrongUpdateConflicts(nodeB, alloc2SUEffectsB, nodeA,
280 alloc2readEffectsA, alloc2writeEffectsA, useReachInfo));
286 private int hasStrongUpdateConflicts(ConflictNode nodeA,
287 Hashtable<AllocSite, Set<Effect>> SUEffectsTableA, ConflictNode nodeB,
288 Hashtable<AllocSite, Set<Effect>> readTableB, Hashtable<AllocSite, Set<Effect>> writeTableB,
289 boolean useReachInfo) {
291 int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
293 Iterator effectItrA = SUEffectsTableA.entrySet().iterator();
294 while (effectItrA.hasNext()) {
295 Map.Entry meA = (Map.Entry) effectItrA.next();
296 AllocSite asA = (AllocSite) meA.getKey();
297 Set<Effect> strongUpdateSetA = (Set<Effect>) meA.getValue();
299 Iterator effectItrB = readTableB.entrySet().iterator();
300 while (effectItrB.hasNext()) {
301 Map.Entry meB = (Map.Entry) effectItrB.next();
302 AllocSite asB = (AllocSite) meB.getKey();
303 Set<Effect> esB = (Set<Effect>) meB.getValue();
305 for (Iterator iterator = strongUpdateSetA.iterator(); iterator.hasNext();) {
306 Effect strongUpdateA = (Effect) iterator.next();
307 for (Iterator iterator2 = esB.iterator(); iterator2.hasNext();) {
308 Effect effectB = (Effect) iterator2.next();
310 if (strongUpdateA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite())
311 && strongUpdateA.getField().equals(effectB.getField())) {
313 FlatNew fnRoot1 = asA.getFlatNew();
314 FlatNew fnRoot2 = asB.getFlatNew();
315 FlatNew fnTarget = strongUpdateA.getAffectedAllocSite().getFlatNew();
316 if (da.mayBothReachTarget(fmEnclosing, fnRoot1, fnRoot2, fnTarget)) {
317 addCoarseEffect(nodeA, asA, strongUpdateA);
318 if (!nodeA.equals(nodeB)) {
319 addCoarseEffect(nodeB, asB, effectB);
321 conflictType = updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
325 // need coarse effects for RCR from just one pass
326 addCoarseEffect(nodeA, asA, strongUpdateA);
327 if (!nodeA.equals(nodeB)) {
328 addCoarseEffect(nodeB, asB, effectB);
330 conflictType=ConflictGraph.COARSE_GRAIN_EDGE;
332 return ConflictGraph.COARSE_GRAIN_EDGE;
342 effectItrB = writeTableB.entrySet().iterator();
343 while (effectItrB.hasNext()) {
344 Map.Entry meB = (Map.Entry) effectItrB.next();
345 AllocSite asB = (AllocSite) meB.getKey();
346 Set<Effect> esB = (Set<Effect>) meB.getValue();
348 for (Iterator iterator = strongUpdateSetA.iterator(); iterator.hasNext();) {
349 Effect strongUpdateA = (Effect) iterator.next();
350 for (Iterator iterator2 = esB.iterator(); iterator2.hasNext();) {
351 Effect effectB = (Effect) iterator2.next();
353 if (strongUpdateA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite())
354 && strongUpdateA.getField().equals(effectB.getField())) {
357 FlatNew fnRoot1 = asA.getFlatNew();
358 FlatNew fnRoot2 = asB.getFlatNew();
359 FlatNew fnTarget = strongUpdateA.getAffectedAllocSite().getFlatNew();
360 if (da.mayBothReachTarget(fmEnclosing, fnRoot1, fnRoot2, fnTarget)) {
361 addCoarseEffect(nodeA, asA, strongUpdateA);
362 if (!nodeA.equals(nodeB)) {
363 addCoarseEffect(nodeB, asB, effectB);
365 conflictType = updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
368 return ConflictGraph.COARSE_GRAIN_EDGE;
382 private int determineConflictType(ConflictNode nodeA,
383 Hashtable<AllocSite, Set<Effect>> nodeAtable, ConflictNode nodeB,
384 Hashtable<AllocSite, Set<Effect>> nodeBtable, boolean useReachInfo) {
386 int conflictType = ConflictGraph.NON_WRITE_CONFLICT;
388 Iterator effectItrA = nodeAtable.entrySet().iterator();
389 while (effectItrA.hasNext()) {
390 Map.Entry meA = (Map.Entry) effectItrA.next();
391 AllocSite asA = (AllocSite) meA.getKey();
392 Set<Effect> esA = (Set<Effect>) meA.getValue();
394 Iterator effectItrB = nodeBtable.entrySet().iterator();
395 while (effectItrB.hasNext()) {
396 Map.Entry meB = (Map.Entry) effectItrB.next();
397 AllocSite asB = (AllocSite) meB.getKey();
398 Set<Effect> esB = (Set<Effect>) meB.getValue();
400 for (Iterator iterator = esA.iterator(); iterator.hasNext();) {
401 Effect effectA = (Effect) iterator.next();
402 for (Iterator iterator2 = esB.iterator(); iterator2.hasNext();) {
403 Effect effectB = (Effect) iterator2.next();
405 if (effectA.getAffectedAllocSite().equals(effectB.getAffectedAllocSite())
406 && effectA.getField().equals(effectB.getField())) {
409 FlatNew fnRoot1 = asA.getFlatNew();
410 FlatNew fnRoot2 = asB.getFlatNew();
411 FlatNew fnTarget = effectA.getAffectedAllocSite().getFlatNew();
412 if (fnRoot1.equals(fnRoot2)) {
413 if (!da.mayManyReachTarget(fmEnclosing, fnRoot1, fnTarget)) {
414 // fine-grained conflict case
415 conflictType = updateConflictType(conflictType, ConflictGraph.FINE_GRAIN_EDGE);
417 // coarse-grained conflict case
418 addCoarseEffect(nodeA, asA, effectA);
419 if (!nodeA.equals(nodeB)) {
420 addCoarseEffect(nodeB, asB, effectB);
423 updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
426 if (da.mayBothReachTarget(fmEnclosing, fnRoot1, fnRoot2, fnTarget)) {
427 addCoarseEffect(nodeA, asA, effectA);
428 if (!nodeA.equals(nodeB)) {
429 addCoarseEffect(nodeB, asB, effectB);
432 updateConflictType(conflictType, ConflictGraph.COARSE_GRAIN_EDGE);
438 // need coarse effects for RCR from just one pass
439 addCoarseEffect(nodeA, asA, effectA);
440 if (!nodeA.equals(nodeB)) {
441 addCoarseEffect(nodeB, asB, effectB);
443 conflictType=ConflictGraph.COARSE_GRAIN_EDGE;
445 return ConflictGraph.COARSE_GRAIN_EDGE;
457 private void addCoarseEffect(ConflictNode node, AllocSite as, Effect e) {
458 Taint t = node.getTaint(as);
459 addEffectSetByTaint(t, e);
462 private void addEffectSetByTaint(Taint t, Effect e) {
464 FlatNode node=t.getSESE();
467 node=t.getStallSite();
470 Hashtable<Taint, Set<Effect>> taint2Conflicts = sese2te.get(node);
471 if (taint2Conflicts == null) {
472 taint2Conflicts = new Hashtable<Taint, Set<Effect>>();
475 Set<Effect> effectSet = taint2Conflicts.get(t);
476 if (effectSet == null) {
477 effectSet = new HashSet<Effect>();
480 taint2Conflicts.put(t, effectSet);
482 sese2te.put(node, taint2Conflicts);
486 private int updateConflictType(int current, int newType) {
487 if (newType > current) {
494 public void clearAllConflictEdge() {
495 Collection<ConflictNode> nodes = id2cn.values();
496 for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
497 ConflictNode conflictNode = (ConflictNode) iterator.next();
498 conflictNode.getEdgeSet().clear();
502 public HashSet<ConflictEdge> getEdgeSet() {
504 HashSet<ConflictEdge> returnSet = new HashSet<ConflictEdge>();
506 Collection<ConflictNode> nodes = id2cn.values();
507 for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
508 ConflictNode conflictNode = (ConflictNode) iterator.next();
509 returnSet.addAll(conflictNode.getEdgeSet());
515 public boolean hasConflictEdge() {
517 Set<String> keySet = id2cn.keySet();
518 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
519 String key = (String) iterator.next();
520 ConflictNode node = id2cn.get(key);
521 if (node.getEdgeSet().size() > 0) {
528 public boolean isFineElement(int type) {
529 if (type == ConflictNode.FINE_READ || type == ConflictNode.FINE_WRITE
530 || type == ConflictNode.PARENT_READ || type == ConflictNode.PARENT_WRITE) {
537 public SESEWaitingQueue getWaitingElementSetBySESEID(int seseID, Set<SESELock> seseLockSet) {
539 HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
541 Iterator iter = id2cn.entrySet().iterator();
542 while (iter.hasNext()) {
543 Entry entry = (Entry) iter.next();
544 String conflictNodeID = (String) entry.getKey();
545 ConflictNode node = (ConflictNode) entry.getValue();
547 if (node.isInVarNode()) {
548 if (node.getSESEIdentifier() == seseID) {
550 Set<ConflictEdge> edgeSet = node.getEdgeSet();
551 for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
552 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
554 for (Iterator<SESELock> seseLockIter = seseLockSet.iterator(); seseLockIter.hasNext();) {
555 SESELock seseLock = seseLockIter.next();
556 if (seseLock.containsConflictNode(node)
557 && seseLock.containsConflictEdge(conflictEdge)) {
558 WaitingElement newElement = new WaitingElement();
559 newElement.setQueueID(seseLock.getID());
560 newElement.setStatus(seseLock.getNodeType(node));
561 newElement.setTempDesc(node.getVar());
562 if (isFineElement(newElement.getStatus())) {
563 newElement.setDynID(node.getVar().toString());
565 if (!waitingElementSet.contains(newElement)) {
566 waitingElementSet.add(newElement);
578 // handle the case that multiple enqueues by an SESE for different live-in
579 // into the same queue
580 return refineQueue(waitingElementSet);
584 public SESEWaitingQueue refineQueue(Set<WaitingElement> waitingElementSet) {
586 Set<WaitingElement> refinedSet = new HashSet<WaitingElement>();
587 HashMap<Integer, Set<WaitingElement>> map = new HashMap<Integer, Set<WaitingElement>>();
588 SESEWaitingQueue seseDS = new SESEWaitingQueue();
590 for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) {
591 WaitingElement waitingElement = (WaitingElement) iterator.next();
592 Set<WaitingElement> set = map.get(new Integer(waitingElement.getQueueID()));
594 set = new HashSet<WaitingElement>();
596 set.add(waitingElement);
597 map.put(new Integer(waitingElement.getQueueID()), set);
600 Set<Integer> keySet = map.keySet();
601 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
602 Integer queueID = (Integer) iterator.next();
603 Set<WaitingElement> queueWEset = map.get(queueID);
604 refineQueue(queueID.intValue(), queueWEset, seseDS);
610 private void refineQueue(int queueID, Set<WaitingElement> waitingElementSet,
611 SESEWaitingQueue seseDS) {
613 if (waitingElementSet.size() > 1) {
614 // only consider there is more than one element submitted by same SESE
615 Set<WaitingElement> refinedSet = new HashSet<WaitingElement>();
620 int total = waitingElementSet.size();
621 WaitingElement SCCelement = null;
622 WaitingElement coarseElement = null;
624 for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) {
625 WaitingElement waitingElement = (WaitingElement) iterator.next();
626 if (waitingElement.getStatus() == ConflictNode.FINE_READ) {
628 } else if (waitingElement.getStatus() == ConflictNode.FINE_WRITE) {
630 } else if (waitingElement.getStatus() == ConflictNode.COARSE) {
632 coarseElement = waitingElement;
633 } else if (waitingElement.getStatus() == ConflictNode.SCC) {
634 SCCelement = waitingElement;
638 if (SCCelement != null) {
639 // if there is at lease one SCC element, just enqueue SCC and
642 // for rcr, we need to label all of coarse tempdescriptors
643 // here assume that all waiting elements are coarse
644 for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) {
645 WaitingElement waitingElement = (WaitingElement) iterator.next();
646 SCCelement.addTempDesc(waitingElement.getTempDesc());
649 refinedSet.add(SCCelement);
650 } else if (numCoarse == 1 && (numRead + numWrite + numCoarse == total)) {
651 // if one is a coarse, the othere are reads/write, enqueue SCC.
652 WaitingElement we = new WaitingElement();
653 we.setQueueID(queueID);
654 we.setStatus(ConflictNode.SCC);
656 } else if (numCoarse == total) {
657 // if there are multiple coarses, enqueue just one coarse.
659 // for rcr, we need to label all of coarse tempdescriptors
660 for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) {
661 WaitingElement waitingElement = (WaitingElement) iterator.next();
662 coarseElement.addTempDesc(waitingElement.getTempDesc());
665 refinedSet.add(coarseElement);
666 } else if (numWrite == total || (numRead + numWrite) == total) {
667 // code generator is going to handle the case for multiple writes &
669 seseDS.setType(queueID, SESEWaitingQueue.EXCEPTION);
670 refinedSet.addAll(waitingElementSet);
672 // otherwise, enqueue everything.
673 refinedSet.addAll(waitingElementSet);
675 seseDS.setWaitingElementSet(queueID, refinedSet);
677 seseDS.setWaitingElementSet(queueID, waitingElementSet);
682 public Set<WaitingElement> getStallSiteWaitingElementSet(FlatNode stallSite,
683 Set<SESELock> seseLockSet) {
685 HashSet<WaitingElement> waitingElementSet = new HashSet<WaitingElement>();
686 Iterator iter = id2cn.entrySet().iterator();
687 while (iter.hasNext()) {
688 Entry entry = (Entry) iter.next();
689 String conflictNodeID = (String) entry.getKey();
690 ConflictNode node = (ConflictNode) entry.getValue();
692 if (node.isStallSiteNode() && node.getStallSiteFlatNode().equals(stallSite)) {
693 Set<ConflictEdge> edgeSet = node.getEdgeSet();
694 for (Iterator iter2 = edgeSet.iterator(); iter2.hasNext();) {
695 ConflictEdge conflictEdge = (ConflictEdge) iter2.next();
697 for (Iterator<SESELock> seseLockIter = seseLockSet.iterator(); seseLockIter.hasNext();) {
698 SESELock seseLock = seseLockIter.next();
699 if (seseLock.containsConflictNode(node) && seseLock.containsConflictEdge(conflictEdge)) {
700 WaitingElement newElement = new WaitingElement();
701 newElement.setQueueID(seseLock.getID());
702 newElement.setStatus(seseLock.getNodeType(node));
703 if (isFineElement(newElement.getStatus())) {
704 newElement.setDynID(node.getVar().toString());
706 newElement.setTempDesc(node.getVar());
707 waitingElementSet.add(newElement);
717 return waitingElementSet;
720 public Hashtable<Taint, Set<Effect>> getConflictEffectSet(FlatNode fn) {
721 return sese2te.get(fn);
724 public void writeGraph(String graphName, boolean filter) throws java.io.IOException {
726 graphName = graphName.replaceAll("[\\W]", "");
728 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
729 bw.write("graph " + graphName + " {\n");
731 // then visit every heap region node
732 Set<Entry<String, ConflictNode>> s = id2cn.entrySet();
733 Iterator<Entry<String, ConflictNode>> i = s.iterator();
735 HashSet<ConflictEdge> addedSet = new HashSet<ConflictEdge>();
737 while (i.hasNext()) {
738 Entry<String, ConflictNode> entry = i.next();
739 ConflictNode node = entry.getValue();
742 if (node.getID().startsWith("___dst") || node.getID().startsWith("___srctmp")
743 || node.getID().startsWith("___neverused") || node.getID().startsWith("___temp")) {
748 if (node.getEdgeSet().isEmpty()) {
754 String attributes = "[";
756 attributes += "label=\"" + node.getID() + "\\n";
758 if (node.isStallSiteNode()) {
759 attributes += "STALL SITE" + "\\n" + "\"]";
761 attributes += "LIVE-IN" + "\\n" + "\"]";
763 bw.write(entry.getKey() + attributes + ";\n");
765 Set<ConflictEdge> edgeSet = node.getEdgeSet();
766 for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
767 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
769 ConflictNode u = conflictEdge.getVertexU();
770 ConflictNode v = conflictEdge.getVertexV();
773 String uID = u.getID();
774 String vID = v.getID();
775 if (uID.startsWith("___dst") || uID.startsWith("___srctmp")
776 || uID.startsWith("___neverused") || uID.startsWith("___temp")
777 || vID.startsWith("___dst") || vID.startsWith("___srctmp")
778 || vID.startsWith("___neverused") || vID.startsWith("___temp")) {
783 if (!addedSet.contains(conflictEdge)) {
784 bw.write("" + u.getID() + "--" + v.getID() + "[label=" + conflictEdge.toGraphEdgeString()
786 addedSet.add(conflictEdge);
792 bw.write(" graphTitle[label=\"" + graphName + "\",shape=box];\n");