From 9aac95a08e6a23532a328c88240b1ad8a7dac9d3 Mon Sep 17 00:00:00 2001 From: yeom Date: Mon, 7 Dec 2009 19:46:30 +0000 Subject: [PATCH] annotating conflict edges. --- Robust/src/Analysis/MLP/ConflictGraph.java | 492 +++++++++++++++------ Robust/src/Analysis/MLP/ConflictNode.java | 16 - Robust/src/Analysis/MLP/LiveInNode.java | 13 +- Robust/src/Analysis/MLP/MLPAnalysis.java | 105 ++--- Robust/src/Analysis/MLP/StallSite.java | 1 - Robust/src/Analysis/MLP/StallSiteNode.java | 6 +- 6 files changed, 392 insertions(+), 241 deletions(-) diff --git a/Robust/src/Analysis/MLP/ConflictGraph.java b/Robust/src/Analysis/MLP/ConflictGraph.java index 79a2c383..3898a07b 100644 --- a/Robust/src/Analysis/MLP/ConflictGraph.java +++ b/Robust/src/Analysis/MLP/ConflictGraph.java @@ -9,7 +9,6 @@ import java.util.Set; import java.util.Map.Entry; import Analysis.OwnershipAnalysis.HeapRegionNode; -import Analysis.OwnershipAnalysis.TokenTuple; import IR.Flat.FlatMethod; import IR.Flat.FlatSESEEnterNode; import IR.Flat.TempDescriptor; @@ -23,140 +22,369 @@ public class ConflictGraph { } public void analyzeConflicts() { + Set keySet = id2cn.keySet(); + Set analyzedIDSet = new HashSet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { String nodeID = (String) iterator.next(); ConflictNode node = id2cn.get(nodeID); - analyzePossibleConflicts(node); + analyzePossibleConflicts(analyzedIDSet, node); } } - public void analyzePossibleConflicts(ConflictNode node) { + private boolean isWriteConflicts(StallSiteNode nodeA, LiveInNode nodeB) { - // compare with all nodes + boolean result = false; + StallSite stallSite = nodeA.getStallSite(); - Set nodeReachabilitySet = node.getReachabilitySet(); + Set writeEffectsSet = nodeB.getWriteEffectsSet(); + Set readEffectsSet = nodeB.getReadEffectsSet(); - Set> set = id2cn.entrySet(); - for (Iterator iterator = set.iterator(); iterator.hasNext();) { - Entry entry = (Entry) iterator - .next(); + if (writeEffectsSet != null) { + Iterator writeIter = writeEffectsSet.iterator(); + while (writeIter.hasNext()) { + SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIter + .next(); + String writeHeapRegionID = seseEffectsKey.getHRNUniqueId(); + String writeFieldName = seseEffectsKey.getFieldDescriptor(); + + HashSet stallSiteHRNSet = nodeA.getHRNSet(); + for (Iterator iterator = stallSiteHRNSet.iterator(); iterator + .hasNext();) { + HeapRegionNode stallHRN = (HeapRegionNode) iterator.next(); + if (stallHRN.getGloballyUniqueIdentifier().equals( + writeHeapRegionID)) { + + // check whether there are read or write effects of + // stall sites + + HashSet effectSet = stallSite.getEffectSet(); + for (Iterator iterator2 = effectSet.iterator(); iterator2 + .hasNext();) { + Effect effect = (Effect) iterator2.next(); + String stallEffectfieldName = effect.getField(); + + if (stallEffectfieldName.equals(writeFieldName)) { + result = result | true; + } + } - String currentNodeID = entry.getKey(); - ConflictNode currentNode = entry.getValue(); + } + } - if ((node instanceof StallSiteNode) - && (currentNode instanceof StallSiteNode)) { - continue; } + } - if (currentNodeID.equals(node.getID())) { - continue; - } + if (readEffectsSet != null) { + Iterator readIter = readEffectsSet.iterator(); + while (readIter.hasNext()) { + + SESEEffectsKey seseEffectsKey = (SESEEffectsKey) readIter + .next(); + String readHeapRegionID = seseEffectsKey.getHRNUniqueId(); + String readFieldName = seseEffectsKey.getFieldDescriptor(); + + HashSet stallSiteHRNSet = nodeA.getHRNSet(); + for (Iterator iterator = stallSiteHRNSet.iterator(); iterator + .hasNext();) { + HeapRegionNode stallHRN = (HeapRegionNode) iterator.next(); + if (stallHRN.getGloballyUniqueIdentifier().equals( + readHeapRegionID)) { + + HashSet effectSet = stallSite.getEffectSet(); + for (Iterator iterator2 = effectSet.iterator(); iterator2 + .hasNext();) { + Effect effect = (Effect) iterator2.next(); + String stallEffectfieldName = effect.getField(); + + if (effect.getEffectType().equals( + StallSite.WRITE_EFFECT)) { + if (stallEffectfieldName.equals(readFieldName)) { + result = result | true; + } + } + + } + + } - Set currentNodeReachabilitySet = currentNode - .getReachabilitySet(); - - Set overlapSet = calculateOverlappedReachableRegion( - nodeReachabilitySet, currentNodeReachabilitySet); - if (overlapSet.size() > 0) { - - // System.out.println("OVERLAPPED=" + overlapSet); - - if (node instanceof StallSiteNode - && currentNode instanceof LiveInNode) { - int edgeType = decideConflictEdgeType(overlapSet, - (StallSiteNode) node, (LiveInNode) currentNode); - addConflictEdge(edgeType, node, currentNode); - } else if (node instanceof LiveInNode - && currentNode instanceof LiveInNode) { - int edgeType = decideConflictEdgeType(overlapSet, - (LiveInNode) node, (LiveInNode) currentNode); - addConflictEdge(edgeType, node, currentNode); } - } else { - // System.out.println("DOSE NOT OVERLAPPED " + node + " <-> " - // + currentNode); } } + + return result; } - public boolean containsTokenTuple(Set overlapSet, - String uniqueID) { + private int determineWriteConflictsType(LiveInNode liveInNodeA, + LiveInNode liveInNodeB) { - for (Iterator iterator = overlapSet.iterator(); iterator.hasNext();) { - GloballyUniqueTokenTuple globallyUniqueTokenTuple = (GloballyUniqueTokenTuple) iterator - .next(); - if (globallyUniqueTokenTuple.getID().equals(uniqueID)) { - return true; + Set liveInHrnSetA = liveInNodeA.getHRNSet(); + Set liveInHrnSetB = liveInNodeB.getHRNSet(); + + boolean isPointingToSameRegion = compareHRNSet(liveInHrnSetA, + liveInHrnSetB); + + boolean isSharingReachability = false; + + Set liveInNodeReachabilitySetA = liveInNodeA.getReachabilitySet(); + Set liveInNodeReachabilitySetB = liveInNodeB.getReachabilitySet(); + + Set overlappedReachableRegionSet = calculateOverlappedReachableRegion( + liveInNodeReachabilitySetA, liveInNodeReachabilitySetB); + if (overlappedReachableRegionSet.size() > 0) { + isSharingReachability = true; + } + + if (isPointingToSameRegion && isSharingReachability) { + // two node share same reachability and points to same region, then + // it is fine grain conflicts + return ConflictEdge.FINE_GRAIN_EDGE; + } else if (isSharingReachability) { + // two node share same reachability but points to different region, + // then it is coarse grain conflicts + return ConflictEdge.COARSE_GRAIN_EDGE; + } else { + // otherwise, it is not write conflicts + return ConflictEdge.NON_WRITE_CONFLICT; + } + + } + + private boolean compareHRNSet(Set setA, + Set setB) { + + for (Iterator iterator = setA.iterator(); iterator.hasNext();) { + HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next(); + String gID = heapRegionNode.getGloballyUniqueIdentifier(); + boolean found = false; + for (Iterator iterator2 = setB.iterator(); iterator2.hasNext();) { + HeapRegionNode heapRegionNode2 = (HeapRegionNode) iterator2 + .next(); + if (heapRegionNode2.getGloballyUniqueIdentifier().equals(gID)) { + found = true; + } + } + if (!found) { + return false; } } + return true; + } - return false; + private int determineWriteConflictsType(StallSiteNode stallNode, + LiveInNode liveInNode) { + + System.out.println("determine write ocnflict type between " + stallNode + + "<->" + liveInNode); + + Set stallHrnSet = stallNode.getHRNSet(); + Set liveInHrnSet = liveInNode.getHRNSet(); + + System.out.println("stallHrnSet=" + stallHrnSet); + System.out.println("liveInHrnSet=" + liveInHrnSet); + + boolean isPointingToSameRegion = compareHRNSet(stallHrnSet, + liveInHrnSet); + System.out.println("isporintTosameRegion=" + isPointingToSameRegion); + + boolean isSharingReachability = false; + + Set stallNodeReachabilitySet = stallNode.getReachabilitySet(); + Set liveInNodeReachabilitySet = liveInNode.getReachabilitySet(); + + Set overlappedReachableRegionSet = calculateOverlappedReachableRegion( + stallNodeReachabilitySet, liveInNodeReachabilitySet); + if (overlappedReachableRegionSet.size() > 0) { + isSharingReachability = true; + } + System.out.println("isSharingReachability=" + isSharingReachability); + + if (isPointingToSameRegion && isSharingReachability) { + // two node share same reachability and points to same region, then + // it is fine grain conflicts + return ConflictEdge.FINE_GRAIN_EDGE; + } else if (isSharingReachability) { + // two node share same reachability but points to different region, + // then it is coarse grain conflicts + return ConflictEdge.COARSE_GRAIN_EDGE; + } else { + // otherwise, it is not write conflicts + return ConflictEdge.NON_WRITE_CONFLICT; + } } - private int decideConflictEdgeType( - Set overlapSet, - StallSiteNode stallSiteNode, LiveInNode liveInNode) { + private boolean isWriteConflicts(LiveInNode nodeA, LiveInNode nodeB) { - Set liveInWriteEffectSet = liveInNode - .getWriteEffectsSet(); + Set readEffectsSetA = nodeA.getReadEffectsSet(); + Set writeEffectsSetA = nodeA.getWriteEffectsSet(); + Set readEffectsSetB = nodeB.getReadEffectsSet(); + Set writeEffectsSetB = nodeB.getWriteEffectsSet(); - if (liveInWriteEffectSet != null) { - for (Iterator iterator = liveInWriteEffectSet.iterator(); iterator - .hasNext();) { - SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator + // if node A has write effects on reading/writing regions of node B + if (writeEffectsSetA != null) { + Iterator writeIterA = writeEffectsSetA.iterator(); + while (writeIterA.hasNext()) { + SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIterA .next(); - String hrnUniqueID = seseEffectsKey.getHRNUniqueId(); + String writeHeapRegionID = seseEffectsKey.getHRNUniqueId(); + String writeFieldName = seseEffectsKey.getFieldDescriptor(); + + if (readEffectsSetB != null) { + Iterator readIterB = readEffectsSetB + .iterator(); + while (readIterB.hasNext()) { + SESEEffectsKey readingEffect = (SESEEffectsKey) readIterB + .next(); + + if (readingEffect.getHRNUniqueId().equals( + writeHeapRegionID) + && readingEffect.getFieldDescriptor().equals( + writeFieldName)) { + return true; + } + } + } + + if (writeEffectsSetB != null) { + Iterator writeIterB = writeEffectsSetB + .iterator(); + while (writeIterB.hasNext()) { + SESEEffectsKey writingEffect = (SESEEffectsKey) writeIterB + .next(); - if (containsTokenTuple(overlapSet, hrnUniqueID)) { - return ConflictEdge.COARSE_GRAIN_EDGE; + if (writingEffect.getHRNUniqueId().equals( + writeHeapRegionID) + && writingEffect.getFieldDescriptor().equals( + writeFieldName)) { + return true; + } + } } + } } - return ConflictEdge.FINE_GRAIN_EDGE; + // if node B has write effects on reading regions of node A + if (writeEffectsSetB != null) { + Iterator writeIterB = writeEffectsSetB.iterator(); + while (writeIterB.hasNext()) { + SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIterB + .next(); + String writeHeapRegionID = seseEffectsKey.getHRNUniqueId(); + String writeFieldName = seseEffectsKey.getFieldDescriptor(); + + if (readEffectsSetA != null) { + Iterator readIterA = readEffectsSetA + .iterator(); + while (readIterA.hasNext()) { + SESEEffectsKey readingEffect = (SESEEffectsKey) readIterA + .next(); + if (readingEffect.getHRNUniqueId().equals( + writeHeapRegionID) + && readingEffect.getFieldDescriptor().equals( + writeFieldName)) { + return true; + } + } + } + + if (writeEffectsSetA != null) { + Iterator writeIterA = writeEffectsSetA + .iterator(); + while (writeIterA.hasNext()) { + SESEEffectsKey writingEffect = (SESEEffectsKey) writeIterA + .next(); + if (writingEffect.getHRNUniqueId().equals( + writeHeapRegionID) + && writingEffect.getFieldDescriptor().equals( + writeFieldName)) { + return true; + } + } + } + + } + } + return false; } - private int decideConflictEdgeType( - Set overlapSet, LiveInNode liveInNodeA, - LiveInNode liveInNodeB) { + public void analyzePossibleConflicts(Set analyzedIDSet, + ConflictNode currentNode) { - Set liveInWriteEffectSetA = liveInNodeA - .getWriteEffectsSet(); + // compare with all nodes - if (liveInWriteEffectSetA != null) { - for (Iterator iterator = liveInWriteEffectSetA.iterator(); iterator - .hasNext();) { - SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator - .next(); - String hrnUniqueID = seseEffectsKey.getHRNUniqueId(); + Set> set = id2cn.entrySet(); + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + Entry entry = (Entry) iterator + .next(); + + String entryNodeID = entry.getKey(); + ConflictNode entryNode = entry.getValue(); + + if ((!currentNode.getID().equals(entryNodeID)) + && !(analyzedIDSet.contains(currentNode.getID() + + entryNodeID) || analyzedIDSet + .contains(entryNodeID + currentNode.getID()))) { + + if (currentNode instanceof StallSiteNode + && entryNode instanceof LiveInNode) { + if (isWriteConflicts((StallSiteNode) currentNode, + (LiveInNode) entryNode)) { + int conflictType = determineWriteConflictsType( + (StallSiteNode) currentNode, + (LiveInNode) entryNode); + // System.out.println("WRITE CONFLICT type=" + // + conflictType + " BETWEEN=" + currentNode + // + "<->" + entryNode); + if (conflictType > 0) { + addConflictEdge(conflictType, currentNode, + entryNode); + } + } + analyzedIDSet.add(currentNode.getID() + entryNodeID); + + } else if (currentNode instanceof LiveInNode + && entryNode instanceof LiveInNode) { + if (isWriteConflicts((LiveInNode) currentNode, + (LiveInNode) entryNode)) { + + int conflictType = determineWriteConflictsType( + (LiveInNode) currentNode, + (LiveInNode) entryNode); +// System.out.println("WRITE CONFLICT type=" +// + conflictType + " BETWEEN=" + currentNode +// + "<->" + entryNode); + if (conflictType > 0) { + addConflictEdge(conflictType, currentNode, + entryNode); + } - if (containsTokenTuple(overlapSet, hrnUniqueID)) { - return ConflictEdge.COARSE_GRAIN_EDGE; + } + analyzedIDSet.add(currentNode.getID() + entryNodeID); } + } + } - Set liveInWriteEffectSetB = liveInNodeB - .getWriteEffectsSet(); + } - if (liveInWriteEffectSetB != null) { - for (Iterator iterator = liveInWriteEffectSetB.iterator(); iterator - .hasNext();) { - SESEEffectsKey seseEffectsKey = (SESEEffectsKey) iterator - .next(); - String hrnUniqueID = seseEffectsKey.getHRNUniqueId(); + public boolean containsTokenTuple(Set overlapSet, + String uniqueID) { - if (containsTokenTuple(overlapSet, hrnUniqueID)) { - return ConflictEdge.COARSE_GRAIN_EDGE; - } + for (Iterator iterator = overlapSet.iterator(); iterator.hasNext();) { + GloballyUniqueTokenTuple globallyUniqueTokenTuple = (GloballyUniqueTokenTuple) iterator + .next(); + if (globallyUniqueTokenTuple.getID().equals(uniqueID)) { + return true; } } - return 0; + return false; + } private Set calculateOverlappedReachableRegion( @@ -210,42 +438,24 @@ public class ConflictGraph { } } - public void addLiveInNode(TempDescriptor td, FlatSESEEnterNode fsen, - Set readEffectsSet, + public void addLiveInNode(TempDescriptor td, Set hrnSet, + FlatSESEEnterNode fsen, Set readEffectsSet, Set writeEffectsSet, Set reachabilitySet) { String liveinNodeID = td + "_" + fsen.getIdentifier(); - LiveInNode liveInNode = (LiveInNode) id2cn.get(liveinNodeID); - if (liveInNode != null) { - liveInNode.addReadEffectsSet(readEffectsSet); - liveInNode.addWriteEffectsSet(writeEffectsSet); - liveInNode.addReachabilitySet(reachabilitySet); - id2cn.put(liveinNodeID, liveInNode); - } else { - LiveInNode newNode = new LiveInNode(liveinNodeID, td, - readEffectsSet, writeEffectsSet, reachabilitySet); - id2cn.put(liveinNodeID, newNode); - } + LiveInNode newNode = new LiveInNode(liveinNodeID, td, hrnSet, + readEffectsSet, writeEffectsSet, reachabilitySet); + id2cn.put(liveinNodeID, newNode); } public void addConflictEdge(int type, ConflictNode nodeU, ConflictNode nodeV) { - if (!nodeU.isConflictConnectedTo(nodeV)) { - ConflictEdge newEdge = new ConflictEdge(nodeU, nodeV, type); - nodeU.addEdge(newEdge); - nodeV.addEdge(newEdge); - } - - } + ConflictEdge newEdge = new ConflictEdge(nodeU, nodeV, type); + nodeU.addEdge(newEdge); + nodeV.addEdge(newEdge); - public void addWriteConflictEdge(StallSiteNode stallNode, - LiveInNode liveInNode) { - ConflictEdge newEdge = new ConflictEdge(stallNode, liveInNode, - ConflictEdge.WRITE_CONFLICT); - stallNode.addEdge(newEdge); - liveInNode.addEdge(newEdge); } public HashSet getLiveInNodeSet() { @@ -283,13 +493,13 @@ public class ConflictGraph { Entry entry = i.next(); ConflictNode node = entry.getValue(); - // if (node.getID().startsWith("___dst") - // || node.getID().startsWith("___srctmp") - // || node.getID().startsWith("___neverused") - // || node.getID().startsWith("___temp")) { - // - // continue; - // } + if (node.getID().startsWith("___dst") + || node.getID().startsWith("___srctmp") + || node.getID().startsWith("___neverused") + || node.getID().startsWith("___temp")) { + + continue; + } String attributes = "["; @@ -309,28 +519,26 @@ public class ConflictGraph { ConflictNode u = conflictEdge.getVertexU(); ConflictNode v = conflictEdge.getVertexV(); - // String uID=u.getID(); - // String vID=v.getID(); - // if (uID.startsWith("___dst") - // || uID.startsWith("___srctmp") - // || uID.startsWith("___neverused") - // || uID.startsWith("___temp") - // || vID.startsWith("___dst") - // || vID.startsWith("___srctmp") - // || vID.startsWith("___neverused") - // || vID.startsWith("___temp")) { - // continue; - // } - - if (conflictEdge.getType() == ConflictEdge.WRITE_CONFLICT) { - if (!addedSet.contains(conflictEdge)) { - bw.write(" " + u.getID() + "--" + v.getID() - + "[label=\"" - + conflictEdge.toGraphEdgeString() - + "\",decorate];\n"); - addedSet.add(conflictEdge); - } + String uID=u.getID(); + String vID=v.getID(); + if (uID.startsWith("___dst") + || uID.startsWith("___srctmp") + || uID.startsWith("___neverused") + || uID.startsWith("___temp") + || vID.startsWith("___dst") + || vID.startsWith("___srctmp") + || vID.startsWith("___neverused") + || vID.startsWith("___temp")) { + continue; + } + + if (!addedSet.contains(conflictEdge)) { + bw.write(" " + u.getID() + "--" + v.getID() + "[label=\"" + + conflictEdge.toGraphEdgeString() + + "\",decorate];\n"); + addedSet.add(conflictEdge); } + } } @@ -349,7 +557,7 @@ class ConflictEdge { private ConflictNode v; private int type; - public static final int WRITE_CONFLICT = 0; + public static final int NON_WRITE_CONFLICT = 0; public static final int FINE_GRAIN_EDGE = 1; public static final int COARSE_GRAIN_EDGE = 2; @@ -360,9 +568,7 @@ class ConflictEdge { } public String toGraphEdgeString() { - if (type == WRITE_CONFLICT) { - return "W_CONFLICT"; - } else if (type == FINE_GRAIN_EDGE) { + if (type == FINE_GRAIN_EDGE) { return "F_CONFLICT"; } else { return "C_CONFLICT"; diff --git a/Robust/src/Analysis/MLP/ConflictNode.java b/Robust/src/Analysis/MLP/ConflictNode.java index d2ba07f0..5b2973a1 100644 --- a/Robust/src/Analysis/MLP/ConflictNode.java +++ b/Robust/src/Analysis/MLP/ConflictNode.java @@ -1,10 +1,8 @@ package Analysis.MLP; import java.util.HashSet; -import java.util.Iterator; import java.util.Set; -import Analysis.OwnershipAnalysis.TokenTupleSet; import IR.Flat.TempDescriptor; public abstract class ConflictNode { @@ -26,20 +24,6 @@ public abstract class ConflictNode { return id; } - public boolean isConflictConnectedTo(ConflictNode node) { - - for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { - ConflictEdge edge = (ConflictEdge) iterator.next(); - if (edge.getType() != ConflictEdge.WRITE_CONFLICT) { - if (edge.getVertexU().equals(node) - || edge.getVertexV().equals(node)) { - return true; - } - } - } - return false; - } - public void addEdge(ConflictEdge edge) { edgeSet.add(edge); } diff --git a/Robust/src/Analysis/MLP/LiveInNode.java b/Robust/src/Analysis/MLP/LiveInNode.java index 9d2b7abc..c8584fe1 100644 --- a/Robust/src/Analysis/MLP/LiveInNode.java +++ b/Robust/src/Analysis/MLP/LiveInNode.java @@ -11,10 +11,12 @@ public class LiveInNode extends ConflictNode { Set readEffectsSet; Set writeEffectsSet; + Set hrnSet; - public LiveInNode(String id, TempDescriptor td, + public LiveInNode(String id, TempDescriptor td, Set hrnSet, Set readEffectsSet, Set writeEffectsSet, Set reachabilitySet) { + this.hrnSet = hrnSet; this.id = id; this.td = td; this.readEffectsSet = readEffectsSet; @@ -22,6 +24,10 @@ public class LiveInNode extends ConflictNode { this.reachabilitySet = reachabilitySet; } + public Set getHRNSet() { + return hrnSet; + } + public Set getReadEffectsSet() { return readEffectsSet; } @@ -152,4 +158,9 @@ public class LiveInNode extends ConflictNode { } + public String toString() { + String str = "LiveInNode " + id; + return str; + } + } diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index ed1d7aec..07734064 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -2064,7 +2064,7 @@ public class MLPAnalysis { Set> entrySet = stallMap .entrySet(); - HashSet newStallNodeSet = new HashSet(); +// HashSet newStallNodeSet = new HashSet(); for (Iterator> iterator2 = entrySet .iterator(); iterator2.hasNext();) { @@ -2078,42 +2078,11 @@ public class MLPAnalysis { .getOwnvershipGraphByMethodContext(mc); Set reachabilitySet = calculateReachabilitySet(og, td); - if ((stallNodeID = conflictGraph.addStallNode(td, fm, - stallSite, reachabilitySet)) != null) { - // it added new stall node - newStallNodeSet.add(stallNodeID); - } - } - - // Analyzing write conflicts between stall site and live-in - // variables - for (Iterator iterator = newStallNodeSet.iterator(); iterator - .hasNext();) { - String stallNodeID = (String) iterator.next(); + conflictGraph.addStallNode(td, fm, stallSite, + reachabilitySet); - StallSiteNode stallNode = conflictGraph - .getStallNode(stallNodeID); - - if (stallNode != null) { - // if prior sese blocks have write effects on this stall - // node, it should be connected between them. - HashSet liveInNodeSet = conflictGraph - .getLiveInNodeSet(); - for (Iterator iterator2 = liveInNodeSet.iterator(); iterator2 - .hasNext();) { - LiveInNode liveInNode = (LiveInNode) iterator2 - .next(); - if (liveInNode.isWriteConflictWith(stallNode)) { - // create conflict edge - conflictGraph.addWriteConflictEdge(stallNode, - liveInNode); - } - } - } } - // /////////////////////////////////////////////////////////////////////// - conflictGraph_nodeAction(mc, fm, fn, conflictGraph, currentConflictsMap); @@ -2128,27 +2097,26 @@ public class MLPAnalysis { } // end of while(mcIter) - // decide fine-grain edge or coarse-grain edge among all vertexes + // decide fine-grain edge or coarse-grain edge among all vertexes by pair-wise comparison conflictGraph.analyzeConflicts(); conflictGraphResults.put(fm, conflictGraph); } - private Set calculateReachabilitySet(OwnershipGraph og, TempDescriptor tempDescriptor){ + private Set calculateReachabilitySet(OwnershipGraph og, + TempDescriptor tempDescriptor) { // reachability set Set reachabilitySet = new HashSet(); LabelNode ln = og.td2ln.get(tempDescriptor); - Iterator refEdgeIter = ln - .iteratorToReferencees(); + Iterator refEdgeIter = ln.iteratorToReferencees(); while (refEdgeIter.hasNext()) { - ReferenceEdge referenceEdge = (ReferenceEdge) refEdgeIter - .next(); + ReferenceEdge referenceEdge = (ReferenceEdge) refEdgeIter.next(); + ReachabilitySet set = referenceEdge.getBeta(); Iterator ttsIter = set.iterator(); while (ttsIter.hasNext()) { - TokenTupleSet tokenTupleSet = (TokenTupleSet) ttsIter - .next(); + TokenTupleSet tokenTupleSet = (TokenTupleSet) ttsIter.next(); HashSet newTokenTupleSet = new HashSet(); // reachabilitySet.add(tokenTupleSet); @@ -2157,8 +2125,7 @@ public class MLPAnalysis { while (iter.hasNext()) { TokenTuple tt = (TokenTuple) iter.next(); int token = tt.getToken(); - String uniqueID = og.id2hrn.get( - new Integer(token)) + String uniqueID = og.id2hrn.get(new Integer(token)) .getGloballyUniqueIdentifier(); GloballyUniqueTokenTuple gtt = new GloballyUniqueTokenTuple( uniqueID, tt); @@ -2171,8 +2138,8 @@ public class MLPAnalysis { return reachabilitySet; } - private void conflictGraph_nodeAction(MethodContext mc, FlatMethod fm, FlatNode fn, - ConflictGraph graph, + private void conflictGraph_nodeAction(MethodContext mc, FlatMethod fm, + FlatNode fn, ConflictGraph graph, ParentChildConflictsMap currentConflictsMap) { switch (fn.kind()) { @@ -2198,11 +2165,21 @@ public class MLPAnalysis { Set writeEffectsSet = seseEffectsSet .getWritingSet(tempDescriptor); - Set reachabilitySet=calculateReachabilitySet(og,tempDescriptor); + Set reachabilitySet = calculateReachabilitySet(og, + tempDescriptor); // add new live-in node - graph.addLiveInNode(tempDescriptor, fsen, readEffectsSet, - writeEffectsSet, reachabilitySet); + LabelNode ln = og.td2ln.get(tempDescriptor); + Set hrnSet = new HashSet(); + Iterator refIter = ln + .iteratorToReferencees(); + while (refIter.hasNext()) { + ReferenceEdge referenceEdge = (ReferenceEdge) refIter + .next(); + hrnSet.add(referenceEdge.getDst()); + } + graph.addLiveInNode(tempDescriptor, hrnSet, fsen, + readEffectsSet, writeEffectsSet, reachabilitySet); } @@ -2303,36 +2280,6 @@ public class MLPAnalysis { } - - - - /* - // collects related allocation sites - Iterator referenceeIter = ln - .iteratorToReferencees(); - while (referenceeIter.hasNext()) { - ReferenceEdge referenceEdge = (ReferenceEdge) referenceeIter - .next(); - HeapRegionNode dstHRN = referenceEdge.getDst(); - if (dstHRN.isParameter()) { - - HashSet visitedHRN = new HashSet(); - visitedHRN.add(dstHRN); - setupRelatedAllocSiteAnalysis(og, mc, dstHRN, - visitedHRN); - - } else { - addLiveInAllocationSite(mc, dstHRN - .getAllocationSite()); - } - } - */ - - - // if(currentConflictsMap.isAfterChildSESE()){ - // - // } - } private void conflicts_nodeAction(MethodContext mc, FlatNode fn, diff --git a/Robust/src/Analysis/MLP/StallSite.java b/Robust/src/Analysis/MLP/StallSite.java index f2739050..6d9e544a 100644 --- a/Robust/src/Analysis/MLP/StallSite.java +++ b/Robust/src/Analysis/MLP/StallSite.java @@ -6,7 +6,6 @@ import java.util.Set; import Analysis.OwnershipAnalysis.AllocationSite; import Analysis.OwnershipAnalysis.HeapRegionNode; -import Analysis.OwnershipAnalysis.ReachabilitySet; import Analysis.OwnershipAnalysis.TokenTupleSet; import IR.Flat.FlatNode; diff --git a/Robust/src/Analysis/MLP/StallSiteNode.java b/Robust/src/Analysis/MLP/StallSiteNode.java index 5797028a..8c48ec6f 100644 --- a/Robust/src/Analysis/MLP/StallSiteNode.java +++ b/Robust/src/Analysis/MLP/StallSiteNode.java @@ -4,7 +4,6 @@ import java.util.HashSet; import java.util.Set; import Analysis.OwnershipAnalysis.HeapRegionNode; -import Analysis.OwnershipAnalysis.TokenTupleSet; import IR.Flat.TempDescriptor; public class StallSiteNode extends ConflictNode { @@ -26,5 +25,10 @@ public class StallSiteNode extends ConflictNode { public StallSite getStallSite() { return stallSite; } + + public String toString(){ + String str="StallSiteNode "+id; + return str; + } } -- 2.34.1