From 54cd5aec9f186f7988020e97effc6bbeb5e3efa2 Mon Sep 17 00:00:00 2001 From: yeom Date: Mon, 26 Oct 2009 18:41:25 +0000 Subject: [PATCH] changes towards method context insensitive analysis. add stall edge mapping. --- Robust/src/Analysis/MLP/MLPAnalysis.java | 232 +++++++++++++----- .../Analysis/MLP/ParentChildConflictsMap.java | 109 ++++++-- Robust/src/Analysis/MLP/StallSite.java | 115 +++++++-- 3 files changed, 357 insertions(+), 99 deletions(-) diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 809482e4..64a12d55 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -54,6 +54,7 @@ public class MLPAnalysis { private Hashtable < FlatNode, ParentChildConflictsMap > conflictsResults; private ParentChildConflictsMap currentConflictsMap; + private Hashtable < ReferenceEdge, StallSite > stallEdgeMapping; public static int maxSESEage = -1; @@ -110,7 +111,7 @@ public class MLPAnalysis { mapMethodContextToLiveInAllocationSiteSet = new Hashtable< MethodContext, HashSet>(); conflictsResults = new Hashtable < FlatNode, ParentChildConflictsMap >(); - + stallEdgeMapping = new Hashtable < ReferenceEdge, StallSite >(); FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() ); @@ -204,13 +205,7 @@ public class MLPAnalysis { } // Parent/child memory conflicts analysis - methItr = ownAnalysis.descriptorsToAnalyze.iterator(); - javaCallGraph = new JavaCallGraph(state,tu); - while( methItr.hasNext() ) { - Descriptor d = methItr.next(); - FlatMethod fm = state.getMethodFlat( d ); - seseConflictsForward(fm,javaCallGraph); - } + seseConflictsForward(javaCallGraph); // disjoint analysis with a set of flagged allocation sites of live-in variable @@ -1053,6 +1048,9 @@ public class MLPAnalysis { if (obj instanceof MethodDescriptor) { MethodDescriptor callerMD = (MethodDescriptor) obj; + if(callerMD.equals(mc.getDescriptor())){ + continue; + } analyzeRelatedAllocationSite(callerMD, mc, paramIndexSet,visitedHRN); } @@ -1700,6 +1698,27 @@ public class MLPAnalysis { } + private HashSet getRefEdgeSetReferenceToSameHRN( + OwnershipGraph og, TempDescriptor td) { + + HashSet returnSet = new HashSet(); + + HashSet heapIDs = getReferenceHeapIDSet(og, td); + for (Iterator iterator = heapIDs.iterator(); iterator + .hasNext();) { + HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next(); + Iterator referenceeIter = heapRegionNode + .iteratorToReferencees(); + while (referenceeIter.hasNext()) { + ReferenceEdge edge = (ReferenceEdge) referenceeIter.next(); + if (edge.getSrc() instanceof HeapRegionNode) { + returnSet.add(edge); + } + } + } + return returnSet; + } + private HashSet getTempDescSetReferenceToSameHRN( OwnershipGraph og, TempDescriptor td) { @@ -1722,65 +1741,102 @@ public class MLPAnalysis { return returnSet; } - private void seseConflictsForward(FlatMethod fm, JavaCallGraph callGraph) { + private void DFSVisit( MethodDescriptor md, + LinkedList sorted, + HashSet discovered, JavaCallGraph javaCallGraph) { - MethodDescriptor md = fm.getMethod(); - HashSet mcSet = ownAnalysis - .getAllMethodContextSetByDescriptor(md); - Iterator mcIter = mcSet.iterator(); + discovered.add(md); - while (mcIter.hasNext()) { - MethodContext mc = mcIter.next(); + Iterator itr = javaCallGraph.getCallerSet(md).iterator(); + while (itr.hasNext()) { + MethodDescriptor mdCaller = (MethodDescriptor) itr.next(); - Set visited = new HashSet(); + if (!discovered.contains(mdCaller)) { + DFSVisit(mdCaller, sorted, discovered, javaCallGraph); + } + } - Set flatNodesToVisit = new HashSet(); - flatNodesToVisit.add(fm); + sorted.addFirst(md); + } + + + private LinkedList topologicalSort(Set set, + JavaCallGraph javaCallGraph) { + HashSet discovered = new HashSet(); + LinkedList sorted = new LinkedList(); - while (!flatNodesToVisit.isEmpty()) { - FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); - flatNodesToVisit.remove(fn); + Iterator itr = set.iterator(); + while (itr.hasNext()) { + MethodDescriptor md = itr.next(); - Stack seseStack = seseStacks.get(fn); - assert seseStack != null; + if (!discovered.contains(md)) { + DFSVisit(md, sorted, discovered, javaCallGraph); + } + } - if (!seseStack.empty()) { - conflicts_nodeAction(mc, fn, seseStack.peek(), callGraph); - } + return sorted; + } + + + private void seseConflictsForward(JavaCallGraph javaCallGraph) { - flatNodesToVisit.remove(fn); - visited.add(fn); + Set methodCallSet = javaCallGraph.getAllMethods(typeUtil.getMain()); - for (int i = 0; i < fn.numNext(); i++) { - FlatNode nn = fn.getNext(i); - if (!visited.contains(nn)) { - flatNodesToVisit.add(nn); + // topologically sort java call chain so that leaf calls are ordered + // first + LinkedList sortedMethodCalls = topologicalSort( + methodCallSet, javaCallGraph); + + for (Iterator iterator = sortedMethodCalls.iterator(); iterator + .hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + + FlatMethod fm = state.getMethodFlat(md); + + HashSet mcSet = ownAnalysis + .getAllMethodContextSetByDescriptor(md); + Iterator mcIter = mcSet.iterator(); + + while (mcIter.hasNext()) { + + MethodContext mc = mcIter.next(); + + Set visited = new HashSet(); + + Set flatNodesToVisit = new HashSet(); + flatNodesToVisit.add(fm); + + while (!flatNodesToVisit.isEmpty()) { + FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); + flatNodesToVisit.remove(fn); + + conflicts_nodeAction(mc, fn, callGraph); + + flatNodesToVisit.remove(fn); + visited.add(fn); + + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + if (!visited.contains(nn)) { + flatNodesToVisit.add(nn); + } } } - } - } } private void conflicts_nodeAction(MethodContext mc, FlatNode fn, - FlatSESEEnterNode currentSESE, CallGraph callGraph) { + CallGraph callGraph) { OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc); switch (fn.kind()) { - case FKind.FlatSESEEnterNode: { - - } - break; - case FKind.FlatSESEExitNode: { - // all object variables are inaccessible currentConflictsMap = new ParentChildConflictsMap(); - } break; @@ -1798,6 +1854,7 @@ public class MLPAnalysis { case FKind.FlatFieldNode: { if (currentConflictsMap != null) { + FlatFieldNode ffn = (FlatFieldNode) fn; TempDescriptor dst = ffn.getDst(); TempDescriptor src = ffn.getSrc(); @@ -1874,46 +1931,95 @@ public class MLPAnalysis { } // TODO need to create edge mapping for newly created edge + HashSet edges = getRefEdgeSetReferenceToSameHRN( + og, dst); + StallSite ss = currentConflictsMap.getStallMap().get(dst); + if (ss != null) { + for (Iterator iterator = edges.iterator(); iterator + .hasNext();) { + ReferenceEdge referenceEdge = (ReferenceEdge) iterator + .next(); + stallEdgeMapping.put(referenceEdge, ss); + // System.out.println("STALL EDGE MAPPING WITH "+referenceEdge+" -> "+ss); + } + } } - } break; case FKind.FlatOpNode: { + if (currentConflictsMap != null) { - // destination variable gets the status of source. - FlatOpNode fon = (FlatOpNode) fn; + // destination variable gets the status of source. + FlatOpNode fon = (FlatOpNode) fn; - if (fon.getOp().getOp() == Operation.ASSIGN - && currentConflictsMap != null) { + if (fon.getOp().getOp() == Operation.ASSIGN + && currentConflictsMap != null) { - TempDescriptor dst = fon.getDest(); - TempDescriptor src = fon.getLeft(); + TempDescriptor dst = fon.getDest(); + TempDescriptor src = fon.getLeft(); - Integer sourceStatus = currentConflictsMap.getAccessibleMap() - .get(src); - if(sourceStatus==null){ - sourceStatus=ParentChildConflictsMap.INACCESSIBLE; - } + Integer sourceStatus = currentConflictsMap + .getAccessibleMap().get(src); + if (sourceStatus == null) { + sourceStatus = ParentChildConflictsMap.INACCESSIBLE; + } - HashSet dstTempSet = getTempDescSetReferenceToSameHRN( - og, dst); + HashSet dstTempSet = getTempDescSetReferenceToSameHRN( + og, dst); - for (Iterator iterator = dstTempSet.iterator(); iterator - .hasNext();) { - TempDescriptor possibleDst = iterator.next(); + for (Iterator iterator = dstTempSet + .iterator(); iterator.hasNext();) { + TempDescriptor possibleDst = iterator.next(); + + if (sourceStatus + .equals(ParentChildConflictsMap.ACCESSIBLE)) { + currentConflictsMap.addAccessibleVar(possibleDst); + } else { + currentConflictsMap.addInaccessibleVar(possibleDst); + } - if (sourceStatus.equals(ParentChildConflictsMap.ACCESSIBLE)) { - currentConflictsMap.addAccessibleVar(possibleDst); - } else { - currentConflictsMap.addInaccessibleVar(possibleDst); } + } + + } + } + break; + case FKind.FlatNop: { + + FlatNop fnop = (FlatNop) fn; + if (fnop.numPrev() > 1) { + // merge point + for (int i = 0; i < fnop.numPrev(); i++) { + FlatNode prev = fnop.getPrev(i); + ParentChildConflictsMap prevConflictsMap = conflictsResults + .get(prev); + if (prevConflictsMap != null) { + if (currentConflictsMap == null) { + currentConflictsMap = new ParentChildConflictsMap(); + } + currentConflictsMap.merge(prevConflictsMap); + } } } + + // TODO: need to merge edge mappings + + } + break; + + case FKind.FlatCall: { + + FlatCall fc = (FlatCall) fn; + + // look at all possible context, and then take all of them into one + // context + } break; + } // for every program point, we keep accessible map and stall map. diff --git a/Robust/src/Analysis/MLP/ParentChildConflictsMap.java b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java index 58d31b1f..0d549a54 100644 --- a/Robust/src/Analysis/MLP/ParentChildConflictsMap.java +++ b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java @@ -1,7 +1,12 @@ package Analysis.MLP; +import java.util.HashSet; import java.util.Hashtable; +import java.util.Iterator; +import java.util.Set; +import Analysis.OwnershipAnalysis.ReachabilitySet; +import Analysis.OwnershipAnalysis.TokenTupleSet; import IR.Flat.TempDescriptor; public class ParentChildConflictsMap { @@ -26,34 +31,106 @@ public class ParentChildConflictsMap { public Hashtable getStallMap() { return stallMap; } - - public void addAccessibleVar(TempDescriptor td){ + + public void addAccessibleVar(TempDescriptor td) { accessibleMap.put(td, ACCESSIBLE); } - - public void addInaccessibleVar(TempDescriptor td){ + + public void addInaccessibleVar(TempDescriptor td) { accessibleMap.put(td, INACCESSIBLE); } - - public void addStallSite(TempDescriptor td){ - StallSite stallSite=new StallSite(); + + public void addStallSite(TempDescriptor td) { + StallSite stallSite = new StallSite(); stallMap.put(td, stallSite); } - public boolean isAccessible(TempDescriptor td){ - if(accessibleMap.contains(td) && accessibleMap.get(td).equals(ACCESSIBLE)){ + public boolean isAccessible(TempDescriptor td) { + if (accessibleMap.contains(td) + && accessibleMap.get(td).equals(ACCESSIBLE)) { return true; } return false; } - - public void contributeEffect(TempDescriptor td, String type, String field, int effect){ - - StallSite stallSite=stallMap.get(td); - if(stallSite!=null){ + + public void contributeEffect(TempDescriptor td, String type, String field, + int effect) { + + StallSite stallSite = stallMap.get(td); + if (stallSite != null) { stallSite.addEffect(type, field, effect); } - + } - + + public void merge(ParentChildConflictsMap newConflictsMap) { + + Hashtable newAccessibleMap = newConflictsMap + .getAccessibleMap(); + Hashtable newStallMap = newConflictsMap + .getStallMap(); + + Set keySet = newAccessibleMap.keySet(); + for (Iterator iterator = keySet.iterator(); iterator + .hasNext();) { + TempDescriptor key = iterator.next(); + + Integer newStatus = newAccessibleMap.get(key); + + // inaccessible is prior to accessible + Integer currentStatus = getAccessibleMap().get(key); + if (currentStatus != null && currentStatus == ACCESSIBLE + && newStatus == INACCESSIBLE) { + getAccessibleMap().put(key, INACCESSIBLE); + } + } + + keySet = newStallMap.keySet(); + for (Iterator iterator = keySet.iterator(); iterator + .hasNext();) { + TempDescriptor key = iterator.next(); + + StallSite newStallSite = newStallMap.get(key); + StallSite currentStallSite = getStallMap().get(key); + + // handle effects + HashSet currentEffectSet = currentStallSite.getEffectSet(); + HashSet newEffectSet = newStallSite.getEffectSet(); + for (Iterator iterator2 = newEffectSet.iterator(); iterator2 + .hasNext();) { + Effect effect = (Effect) iterator2.next(); + if (!currentEffectSet.contains(effect)) { + currentEffectSet.add(effect); + } + } + + // handle heap region + HashSet currentHRNSet = currentStallSite.getHRNIDSet(); + HashSet newHRNSet = newStallSite.getHRNIDSet(); + for (Iterator iterator2 = newHRNSet.iterator(); iterator2.hasNext();) { + Integer hrnID = (Integer) iterator2.next(); + if (!currentHRNSet.contains(hrnID)) { + currentHRNSet.add(hrnID); + } + } + + // handle reachabilitySet + ReachabilitySet currentRSet = currentStallSite.getReachabilitySet(); + ReachabilitySet newRSet = newStallSite.getReachabilitySet(); + Iterator ttsIter = newRSet.iterator(); + while (ttsIter.hasNext()) { + TokenTupleSet tokenTupleSet = (TokenTupleSet) ttsIter.next(); + currentRSet.add(tokenTupleSet); + } + + getStallMap() + .put( + key, + new StallSite(currentEffectSet, currentHRNSet, + currentRSet)); + + } + + } + } diff --git a/Robust/src/Analysis/MLP/StallSite.java b/Robust/src/Analysis/MLP/StallSite.java index 23480a34..edb794d9 100644 --- a/Robust/src/Analysis/MLP/StallSite.java +++ b/Robust/src/Analysis/MLP/StallSite.java @@ -5,35 +5,110 @@ import java.util.HashSet; import Analysis.OwnershipAnalysis.ReachabilitySet; public class StallSite { - - public static final Integer READ_EFFECT=new Integer(1); - public static final Integer WRITE_EFFECT=new Integer(2); - + + public static final Integer READ_EFFECT = new Integer(1); + public static final Integer WRITE_EFFECT = new Integer(2); + private HashSet effectSet; - private int hrnID; + private HashSet hrnIDSet; private ReachabilitySet rechabilitySet; - - public StallSite(){ - effectSet=new HashSet(); + + public StallSite() { + effectSet = new HashSet(); + hrnIDSet = new HashSet(); + rechabilitySet = new ReachabilitySet(); + } + + public StallSite(HashSet effectSet, HashSet hrnIDSet, + ReachabilitySet rechabilitySet) { + this.effectSet = effectSet; + this.hrnIDSet = hrnIDSet; + this.rechabilitySet = rechabilitySet; } - - public void addEffect(String type, String field, Integer effect){ - Effect e=new Effect(type,field,effect); + + public void addEffect(String type, String field, Integer effect) { + Effect e = new Effect(type, field, effect); effectSet.add(e); } - + + public HashSet getEffectSet() { + return effectSet; + } + + public HashSet getHRNIDSet() { + return hrnIDSet; + } + + public ReachabilitySet getReachabilitySet() { + return rechabilitySet; + } + + public boolean equals(Object o) { + + if (o == null) { + return false; + } + + if (!(o instanceof StallSite)) { + return false; + } + + StallSite in = (StallSite) o; + + if (effectSet.equals(in.getEffectSet()) + && hrnIDSet.equals(in.getHRNIDSet()) + && rechabilitySet.equals(in.getReachabilitySet())) { + return true; + } else { + return false; + } + + } } -class Effect{ - +class Effect { + private String field; private String type; private Integer effect; - - public Effect(String type, String field, Integer effect){ - this.type=type; - this.field=field; - this.effect=effect; + + public Effect(String type, String field, Integer effect) { + this.type = type; + this.field = field; + this.effect = effect; + } + + public String getField() { + return field; + } + + public String getType() { + return type; + } + + public Integer getEffect() { + return effect; } - + + public boolean equals(Object o) { + + if (o == null) { + return false; + } + + if (!(o instanceof StallSite)) { + return false; + } + + Effect in = (Effect) o; + + if (type.equals(in.getType()) && field.equals(in.getField()) + && effect.equals(in.getEffect())) { + return true; + } else { + return false; + } + + } + } \ No newline at end of file -- 2.34.1