From 28fe541626b181952817669e93139a9e8a3e9008 Mon Sep 17 00:00:00 2001 From: yeom Date: Fri, 30 Oct 2009 18:59:23 +0000 Subject: [PATCH] fixes and associate each effect with unique stall tag identifier. --- Robust/src/Analysis/MLP/MLPAnalysis.java | 124 ++++++++++++--- Robust/src/Analysis/MLP/MethodSummary.java | 34 ++-- .../Analysis/MLP/ParentChildConflictsMap.java | 69 ++++++-- Robust/src/Analysis/MLP/StallSite.java | 148 +++++++++++++++--- 4 files changed, 304 insertions(+), 71 deletions(-) diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 88738003..64cea770 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -1836,7 +1836,6 @@ public class MLPAnalysis { // if we have a new result, schedule forward nodes for // analysis - if(!currentConflictsMap.isAfterChildSESE()){ conflictsResults.put(fn, currentConflictsMap); for (int i = 0; i < fn.numNext(); i++) { @@ -1922,9 +1921,9 @@ public class MLPAnalysis { TempDescriptor dst = ffn.getDst(); TempDescriptor src = ffn.getSrc(); FieldDescriptor field = ffn.getField(); - + if (currentConflictsMap.isAfterChildSESE()) { - + HashSet srcTempSet = getTempDescSetReferenceToSameHRN( og, src); for (Iterator iterator = srcTempSet.iterator(); iterator @@ -1933,18 +1932,18 @@ public class MLPAnalysis { .next(); if (!currentConflictsMap.isAccessible(possibleSrc)) { HashSet refHRN=getReferenceHeapIDSet(og, possibleSrc); - currentConflictsMap.addStallSite(possibleSrc,refHRN); + currentConflictsMap.addStallSite(possibleSrc,refHRN,new StallTag(fn)); } currentConflictsMap.addAccessibleVar(possibleSrc); // contribute read effect on source's stall site - currentConflictsMap.contributeEffect(src, field.getType() + currentConflictsMap.contributeEffect(possibleSrc, field.getType() .getSafeSymbol(), field.toString(), StallSite.READ_EFFECT); } - HashSet dstTempSet = getTempDescSetReferenceToSameHRN( + HashSet dstTempSet = getTempDescSetReferenceToSameHRN( og, dst); for (Iterator iterator = dstTempSet.iterator(); iterator .hasNext();) { @@ -1979,7 +1978,7 @@ public class MLPAnalysis { .next(); if (!currentConflictsMap.isAccessible(possibleSrc)) { HashSet refHRN=getReferenceHeapIDSet(og, possibleSrc); - currentConflictsMap.addStallSite(possibleSrc,refHRN); + currentConflictsMap.addStallSite(possibleSrc,refHRN,new StallTag(fn)); } currentConflictsMap.addAccessibleVar(possibleSrc); } @@ -1993,7 +1992,7 @@ public class MLPAnalysis { if (!currentConflictsMap.isAccessible(possibleDst)) { HashSet refHRN=getReferenceHeapIDSet(og, possibleDst); - currentConflictsMap.addStallSite(possibleDst,refHRN); + currentConflictsMap.addStallSite(possibleDst,refHRN,new StallTag(fn)); } currentConflictsMap.addAccessibleVar(possibleDst); // contribute write effect on destination's stall site @@ -2013,7 +2012,7 @@ public class MLPAnalysis { ReferenceEdge referenceEdge = (ReferenceEdge) iterator .next(); if(!(referenceEdge.getSrc() instanceof LabelNode)){ - currentConflictsMap.addStallEdge(referenceEdge, ss); + currentConflictsMap.addStallEdge(referenceEdge,new StallTag(fn)); } } } @@ -2069,6 +2068,11 @@ public class MLPAnalysis { case FKind.FlatCall: { FlatCall fc = (FlatCall) fn; + + int base=0; + if(!fc.getMethod().isStatic()){ + base=1; + } FlatMethod calleeFM = state.getMethodFlat(fc.getMethod()); @@ -2118,7 +2122,9 @@ public class MLPAnalysis { // If callee has at least one child sese, all parent object // is going to be inaccessible. - currentConflictsMap = new ParentChildConflictsMap(); +// currentConflictsMap = new ParentChildConflictsMap(); + currentConflictsMap.makeAllInaccessible(); + currentConflictsMap.setAfterChildSESE(true); TempDescriptor returnTemp = fc.getReturnTemp(); @@ -2127,20 +2133,44 @@ public class MLPAnalysis { // when return value is accessible, associate with its // stall site currentConflictsMap.addAccessibleVar(returnTemp); + + StallSite returnStallSite=calleeMethodSummary.getReturnStallSite().copy(); + // handling parameter regions + HashSet stallParamIdx=returnStallSite.getCallerParamIdxSet(); + for (Iterator iterator = stallParamIdx.iterator(); iterator + .hasNext();) { + Integer idx = (Integer) iterator.next(); + + int paramIdx=idx.intValue()-base; + TempDescriptor paramTD=fc.getArg(paramIdx); + + //TODO: resolve callee's parameter heap regions by following call chain + + } + currentConflictsMap.addStallSite(returnTemp, - calleeMethodSummary.getReturnStallSite()); + returnStallSite); + } else if (calleeMethodSummary.getReturnValueAccessibility() .equals(MethodSummary.INACCESSIBLE)) { // when return value is inaccessible currentConflictsMap.addInaccessibleVar(returnTemp); } + // TODO: need to handle edge mappings from callee + - // TODO: need to handle edge mappings from callee - HashSet stallParamIdx=calleeMethodSummary.getStallParamIdxSet(); + Set stallParamIdx=calleeMethodSummary.getStallParamIdxSet(); for (Iterator iterator = stallParamIdx.iterator(); iterator .hasNext();) { - Integer paramIdx = (Integer) iterator.next(); + Integer paramIdx = (Integer) iterator.next(); + HashSet stallTagSet=calleeMethodSummary.getStallTagByParamIdx(paramIdx); + + int argIdx=paramIdx.intValue()-base; + TempDescriptor argTD=fc.getArg(argIdx); + + putStallTagOnReferenceEdges(og, argTD,stallTagSet,currentConflictsMap); + } } @@ -2158,12 +2188,28 @@ public class MLPAnalysis { // child SESEs. } else { if (currentConflictsMap.isAccessible(returnTD)) { + currentMethodSummary .setReturnValueAccessibility(MethodSummary.ACCESSIBLE); StallSite returnStallSite = currentConflictsMap .getStallMap().get(returnTD); + + HashSet stallSiteHRNSet=returnStallSite.getHRNSet(); + for (Iterator iterator = stallSiteHRNSet.iterator(); iterator + .hasNext();) { + HeapRegionNode stallSiteHRN = (HeapRegionNode) iterator + .next(); + Set paramSet=og.idPrimary2paramIndexSet + .get(stallSiteHRN.getID()); + returnStallSite.addCallerParamIdxSet(paramSet); + paramSet=og.idSecondary2paramIndexSet + .get(stallSiteHRN.getID()); + returnStallSite.addCallerParamIdxSet(paramSet); + } + currentMethodSummary .setReturnStallSite(returnStallSite); + } else { currentMethodSummary .setReturnValueAccessibility(MethodSummary.INACCESSIBLE); @@ -2183,22 +2229,27 @@ public class MLPAnalysis { for (Iterator iterator = stallTempSet.iterator(); iterator .hasNext();) { TempDescriptor stallTD = (TempDescriptor) iterator.next(); - StallSite ss = currentConflictsMap.getStallMap().get( - stallTD); + StallSite stallSite = currentConflictsMap.getStallMap() + .get(stallTD); - HashSet stallSiteHRNSet = ss.getHRNSet(); + HashSet stallSiteHRNSet = stallSite + .getHRNSet(); for (Iterator iterator2 = stallSiteHRNSet.iterator(); iterator2 .hasNext();) { HeapRegionNode stallSiteHRN = (HeapRegionNode) iterator2 .next(); if (stallSiteHRN.isParameter()) { - currentMethodSummary - .addStallParamIdxSet(og.idPrimary2paramIndexSet - .get(stallSiteHRN.getID())); - currentMethodSummary - .addStallParamIdxSet(og.idSecondary2paramIndexSet - .get(stallSiteHRN.getID())); + + Set paramSet = og.idPrimary2paramIndexSet + .get(stallSiteHRN.getID()); + currentMethodSummary.addStallParamIdxSet(paramSet, + stallSite.getStallTagSet()); + + paramSet = og.idSecondary2paramIndexSet + .get(stallSiteHRN.getID()); + currentMethodSummary.addStallParamIdxSet(paramSet, + stallSite.getStallTagSet()); } } @@ -2214,6 +2265,33 @@ public class MLPAnalysis { } + + private void putStallTagOnReferenceEdges(OwnershipGraph og, + TempDescriptor argTD, HashSet stallTagSet, + ParentChildConflictsMap currentConflictsMap) { + + LabelNode ln=og.td2ln.get(argTD); + if(ln!=null){ + + Iterator refrenceeIter=ln.iteratorToReferencees(); + while (refrenceeIter.hasNext()) { + ReferenceEdge refEdge = (ReferenceEdge) refrenceeIter.next(); + HeapRegionNode stallHRN=refEdge.getDst(); + + Iterator referencerIter=stallHRN.iteratorToReferencers(); + while (referencerIter.hasNext()) { + ReferenceEdge referencer = (ReferenceEdge) referencerIter + .next(); + for (Iterator iterator = stallTagSet.iterator(); iterator + .hasNext();) { + StallTag stallTag = (StallTag) iterator.next(); + currentConflictsMap.addStallEdge(referencer, stallTag); + } + } + } + } + } + private void preEffectAnalysis(OwnershipGraph og, TempDescriptor td, FieldDescriptor field, Integer effectType) { diff --git a/Robust/src/Analysis/MLP/MethodSummary.java b/Robust/src/Analysis/MLP/MethodSummary.java index b86081fc..0a743b1e 100644 --- a/Robust/src/Analysis/MLP/MethodSummary.java +++ b/Robust/src/Analysis/MLP/MethodSummary.java @@ -1,6 +1,7 @@ package Analysis.MLP; import java.util.HashSet; +import java.util.Hashtable; import java.util.Iterator; import java.util.Set; @@ -14,24 +15,34 @@ public class MethodSummary { private HashSet effectsSet; private Integer accessibility; private StallSite returnStallSite; - private HashSet stallParamIdxSet; - + + private Hashtable> mapParamIndexToRelatedStallTag; + public MethodSummary() { effectsSet = new HashSet(); accessibility = MethodSummary.VOID; childSESECount = 0; returnStallSite=null; - stallParamIdxSet=new HashSet(); + mapParamIndexToRelatedStallTag=new Hashtable>(); } - public HashSet getStallParamIdxSet(){ - return stallParamIdxSet; + public void addStallParamIdxSet(Set paramIdxSet, HashSet stallTagSet){ + + if(paramIdxSet!=null){ + for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { + Integer paramIdx = (Integer) iterator.next(); + mapParamIndexToRelatedStallTag.put(paramIdx, stallTagSet); + } + } } - public void addStallParamIdxSet(Set newSet){ - if(newSet!=null){ - stallParamIdxSet.addAll(newSet); - } + public HashSet getStallTagByParamIdx(Integer paramIdx){ + return mapParamIndexToRelatedStallTag.get(paramIdx); + } + + + public Set getStallParamIdxSet(){ + return mapParamIndexToRelatedStallTag.keySet(); } public void setReturnStallSite(StallSite ss){ @@ -136,11 +147,6 @@ class PreEffectsKey { PreEffectsKey in = (PreEffectsKey) o; - this.paramIndex = paramIndex; - this.field = field; - this.type = type; - this.effectType = effectType; - if (paramIndex.equals(in.getParamIndex()) && field.equals(in.getField()) && type.equals(in.getType()) && effectType.equals(in.getEffectType())) { diff --git a/Robust/src/Analysis/MLP/ParentChildConflictsMap.java b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java index 2a44dce1..0aa832a0 100644 --- a/Robust/src/Analysis/MLP/ParentChildConflictsMap.java +++ b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java @@ -5,10 +5,12 @@ import java.util.Hashtable; import java.util.Iterator; import java.util.Set; +import Analysis.OwnershipAnalysis.AllocationSite; import Analysis.OwnershipAnalysis.HeapRegionNode; import Analysis.OwnershipAnalysis.ReachabilitySet; import Analysis.OwnershipAnalysis.ReferenceEdge; import Analysis.OwnershipAnalysis.TokenTupleSet; +import IR.Flat.FlatNode; import IR.Flat.TempDescriptor; public class ParentChildConflictsMap { @@ -18,7 +20,7 @@ public class ParentChildConflictsMap { private Hashtable accessibleMap; private Hashtable stallMap; - private Hashtable < ReferenceEdge, StallSite > stallEdgeMap; + private Hashtable < ReferenceEdge, HashSet > stallEdgeMap; private boolean afterChildSESE; @@ -26,20 +28,36 @@ public class ParentChildConflictsMap { accessibleMap = new Hashtable(); stallMap = new Hashtable(); - stallEdgeMap= new Hashtable < ReferenceEdge, StallSite >(); + stallEdgeMap= new Hashtable < ReferenceEdge, HashSet >(); afterChildSESE=false; } - public Hashtable < ReferenceEdge, StallSite > getStallEdgeMap(){ + public void makeAllInaccessible(){ + + Set keySet=accessibleMap.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + TempDescriptor key = (TempDescriptor) iterator.next(); + accessibleMap.put(key, INACCESSIBLE); + } + + } + + public Hashtable < ReferenceEdge, HashSet > getStallEdgeMap(){ return stallEdgeMap; } - public void addStallEdge(ReferenceEdge edge, StallSite site){ - stallEdgeMap.put(edge, site); + public void addStallEdge(ReferenceEdge edge, StallTag sTag){ + + HashSet tagSet=stallEdgeMap.get(edge); + if(tagSet==null){ + tagSet=new HashSet(); + } + tagSet.add(sTag); + stallEdgeMap.put(edge, tagSet); } - public StallSite getStallSiteByEdge(ReferenceEdge edge){ + public HashSet getStallTagByEdge(ReferenceEdge edge){ return stallEdgeMap.get(edge); } @@ -67,8 +85,8 @@ public class ParentChildConflictsMap { accessibleMap.put(td, INACCESSIBLE); } - public void addStallSite(TempDescriptor td, HashSet heapSet) { - StallSite stallSite=new StallSite(heapSet); + public void addStallSite(TempDescriptor td, HashSet heapSet, StallTag sTag) { + StallSite stallSite=new StallSite(heapSet,sTag); stallMap.put(td, stallSite); } @@ -121,7 +139,9 @@ public class ParentChildConflictsMap { if (currentStatus != null && currentStatus == ACCESSIBLE && newStatus == INACCESSIBLE) { getAccessibleMap().put(key, INACCESSIBLE); - } + }else if(currentStatus == null && newStatus == ACCESSIBLE){ + getAccessibleMap().put(key, ACCESSIBLE); + } } keySet = newStallMap.keySet(); @@ -166,8 +186,24 @@ public class ParentChildConflictsMap { currentRSet.add(tokenTupleSet); } + //handle allocationsite + HashSet currentAloc=currentStallSite.getAllocationSiteSet(); + HashSet newAloc=newStallSite.getAllocationSiteSet(); + currentAloc.addAll(newAloc); + + // handle related stall tags + HashSet currentStallTagSet=currentStallSite.getStallTagSet(); + HashSet newStallTagSet=newStallSite.getStallTagSet(); + currentStallTagSet.addAll(newStallTagSet); + + // reaching param idxs + HashSet currentParamIdx=currentStallSite.getCallerParamIdxSet(); + HashSet newParamIdx=newStallSite.getCallerParamIdxSet(); + currentParamIdx.addAll(newParamIdx); + StallSite merged=new StallSite(currentEffectSet, currentHRNSet, - currentRSet); + currentRSet, currentAloc, currentStallTagSet,currentParamIdx); + getStallMap() .put( @@ -178,12 +214,19 @@ public class ParentChildConflictsMap { // merge edge mapping - Hashtable newStallEdgeMapping=newConflictsMap.getStallEdgeMap(); + Hashtable> newStallEdgeMapping=newConflictsMap.getStallEdgeMap(); Set edgeSet=newStallEdgeMapping.keySet(); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { ReferenceEdge stallEdge = (ReferenceEdge) iterator.next(); - StallSite newStallSite=newStallEdgeMapping.get(stallEdge); - getStallEdgeMap().put(stallEdge, newStallSite); + HashSet newStallTagSet=newStallEdgeMapping.get(stallEdge); + HashSetcurrentStallTagSet=getStallEdgeMap().get(stallEdge); + + if(currentStallTagSet==null){ + currentStallTagSet=new HashSet(); + } + currentStallTagSet.addAll(newStallTagSet); + getStallEdgeMap().put(stallEdge,currentStallTagSet); } } diff --git a/Robust/src/Analysis/MLP/StallSite.java b/Robust/src/Analysis/MLP/StallSite.java index beb1b65e..a067a2f1 100644 --- a/Robust/src/Analysis/MLP/StallSite.java +++ b/Robust/src/Analysis/MLP/StallSite.java @@ -2,10 +2,12 @@ package Analysis.MLP; import java.util.HashSet; import java.util.Iterator; +import java.util.Set; import Analysis.OwnershipAnalysis.AllocationSite; import Analysis.OwnershipAnalysis.HeapRegionNode; import Analysis.OwnershipAnalysis.ReachabilitySet; +import IR.Flat.FlatNode; public class StallSite { @@ -16,17 +18,28 @@ public class StallSite { private HashSet hrnSet; private HashSet allocationSiteSet; private ReachabilitySet rechabilitySet; + private HashSet stallTagSet; + + // if stall site is caller's parameter heap regtion, store its parameter idx + // for further analysis + private HashSet callerParamIdxSet; public StallSite() { effectSet = new HashSet(); hrnSet = new HashSet(); rechabilitySet = new ReachabilitySet(); - allocationSiteSet=new HashSet(); + allocationSiteSet = new HashSet(); + stallTagSet = new HashSet(); + callerParamIdxSet = new HashSet(); } - - public StallSite(HashSet hrnSet){ + + public StallSite(HashSet hrnSet, StallTag tag) { + this(); + setHeapRegionNodeSet(hrnSet); + stallTagSet.add(tag); + for (Iterator iterator = hrnSet.iterator(); iterator.hasNext();) { HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next(); setAllocationSite(heapRegionNode.getAllocationSite()); @@ -34,28 +47,52 @@ public class StallSite { } public StallSite(HashSet effectSet, HashSet hrnSet, - ReachabilitySet rechabilitySet) { - this.effectSet = effectSet; - this.hrnSet = hrnSet; + ReachabilitySet rechabilitySet, HashSet alocSet, + HashSet tagSet, HashSet paramIdx) { + this(); + this.effectSet.addAll(effectSet); + this.hrnSet.addAll(hrnSet); this.rechabilitySet = rechabilitySet; + this.allocationSiteSet.addAll(alocSet); + this.stallTagSet.addAll(tagSet); + this.callerParamIdxSet.addAll(paramIdx); + } + + public HashSet getCallerParamIdxSet() { + return callerParamIdxSet; + } + + public void addCallerParamIdxSet(Set newParamSet) { + if (newParamSet != null) { + callerParamIdxSet.addAll(newParamSet); + } + } + + public void setStallTagSet(HashSet tags) { + stallTagSet = tags; + } + + public void addRelatedStallTag(StallTag stallTag) { + stallTagSet.add(stallTag); } - - public void setAllocationSite(AllocationSite allocationSite){ - if(allocationSite!=null){ + + public void setAllocationSite(AllocationSite allocationSite) { + if (allocationSite != null) { allocationSiteSet.add(allocationSite); } } - - public void setHeapRegionNodeSet(HashSet newSet){ + + public void setHeapRegionNodeSet(HashSet newSet) { hrnSet.addAll(newSet); } - - public HashSet getAllocationSiteSet(){ + + public HashSet getAllocationSiteSet() { return allocationSiteSet; } public void addEffect(String type, String field, Integer effect) { - Effect e = new Effect(type, field, effect); + + Effect e = new Effect(type, field, effect, stallTagSet); effectSet.add(e); } @@ -71,6 +108,18 @@ public class StallSite { return rechabilitySet; } + public HashSet getStallTagSet() { + return stallTagSet; + } + + public StallSite copy() { + + StallSite copy = new StallSite(effectSet, hrnSet, rechabilitySet, + allocationSiteSet, stallTagSet, callerParamIdxSet); + return copy; + + } + public boolean equals(Object o) { if (o == null) { @@ -83,7 +132,9 @@ public class StallSite { StallSite in = (StallSite) o; - if (effectSet.equals(in.getEffectSet()) + if (allocationSiteSet.equals(in.getAllocationSiteSet()) + && stallTagSet.equals(in.getStallTagSet()) + && effectSet.equals(in.getEffectSet()) && hrnSet.equals(in.getHRNSet()) && rechabilitySet.equals(in.getReachabilitySet())) { return true; @@ -93,11 +144,48 @@ public class StallSite { } + @Override public String toString() { - return "StallSite [effectSet=" + effectSet + ", hrnIDSet=" + hrnSet - + ", rechabilitySet=" + rechabilitySet + "]"; + return "StallSite [allocationSiteSet=" + allocationSiteSet + + ", callerParamIdxSet=" + callerParamIdxSet + ", effectSet=" + + effectSet + ", hrnSet=" + hrnSet + ", rechabilitySet=" + + rechabilitySet + ", stallTagSet=" + stallTagSet + "]"; } - + +} + +class StallTag { + + private FlatNode fn; + + public StallTag(FlatNode fn) { + this.fn = fn; + } + + public FlatNode getKey() { + return fn; + } + + public boolean equals(Object o) { + + if (o == null) { + return false; + } + + if (!(o instanceof StallTag)) { + return false; + } + + StallTag in = (StallTag) o; + + if (getKey().equals(in.getKey())) { + return true; + } else { + return false; + } + + } + } class Effect { @@ -105,11 +193,19 @@ class Effect { private String field; private String type; private Integer effect; + private HashSet stallTagSet; + + public Effect() { + stallTagSet = new HashSet(); + } - public Effect(String type, String field, Integer effect) { + public Effect(String type, String field, Integer effect, + HashSet tagSet) { + this(); this.type = type; this.field = field; this.effect = effect; + stallTagSet.addAll(tagSet); } public String getField() { @@ -124,19 +220,24 @@ class Effect { return effect; } + public HashSet getStallTagSet() { + return stallTagSet; + } + public boolean equals(Object o) { if (o == null) { return false; } - if (!(o instanceof StallSite)) { + if (!(o instanceof Effect)) { return false; } Effect in = (Effect) o; - if (type.equals(in.getType()) && field.equals(in.getField()) + if (stallTagSet.equals(in.getStallTagSet()) + && type.equals(in.getType()) && field.equals(in.getField()) && effect.equals(in.getEffect())) { return true; } else { @@ -145,4 +246,9 @@ class Effect { } + public String toString() { + return "Effect [effect=" + effect + ", field=" + field + + ", stallTagSet=" + stallTagSet + ", type=" + type + "]"; + } + } \ No newline at end of file -- 2.34.1