From dc480919319111a7ed5b67bff3881a04b7bd4058 Mon Sep 17 00:00:00 2001 From: yeom Date: Tue, 27 Oct 2009 17:47:57 +0000 Subject: [PATCH] added for handling method with child SESE. It collects pre-effects of callee in the first phase, and then it converts pre-effects into caller's. --- Robust/src/Analysis/MLP/MLPAnalysis.java | 256 ++++++++++++++++-- Robust/src/Analysis/MLP/MethodSummary.java | 143 ++++++++++ .../Analysis/MLP/ParentChildConflictsMap.java | 10 +- 3 files changed, 392 insertions(+), 17 deletions(-) create mode 100644 Robust/src/Analysis/MLP/MethodSummary.java diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 64a12d55..f00c0195 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -55,6 +55,11 @@ public class MLPAnalysis { private Hashtable < FlatNode, ParentChildConflictsMap > conflictsResults; private ParentChildConflictsMap currentConflictsMap; private Hashtable < ReferenceEdge, StallSite > stallEdgeMapping; + private Hashtable< FlatMethod, MethodSummary > methodSummaryResults; + + // temporal data structures to track analysis progress. + private MethodSummary currentMethodSummary; + private HashSet preeffectsSet; public static int maxSESEage = -1; @@ -112,6 +117,7 @@ public class MLPAnalysis { conflictsResults = new Hashtable < FlatNode, ParentChildConflictsMap >(); stallEdgeMapping = new Hashtable < ReferenceEdge, StallSite >(); + methodSummaryResults=new Hashtable(); FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() ); @@ -1796,7 +1802,10 @@ public class MLPAnalysis { HashSet mcSet = ownAnalysis .getAllMethodContextSetByDescriptor(md); Iterator mcIter = mcSet.iterator(); - + + currentMethodSummary=new MethodSummary(); + preeffectsSet=new HashSet(); + while (mcIter.hasNext()) { MethodContext mc = mcIter.next(); @@ -1806,11 +1815,12 @@ public class MLPAnalysis { Set flatNodesToVisit = new HashSet(); flatNodesToVisit.add(fm); + currentConflictsMap=null; while (!flatNodesToVisit.isEmpty()) { FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); flatNodesToVisit.remove(fn); - conflicts_nodeAction(mc, fn, callGraph); + conflicts_nodeAction(mc, fn, callGraph, preeffectsSet); flatNodesToVisit.remove(fn); visited.add(fn); @@ -1823,19 +1833,43 @@ public class MLPAnalysis { } } } + methodSummaryResults.put(fm, currentMethodSummary); } } private void conflicts_nodeAction(MethodContext mc, FlatNode fn, - CallGraph callGraph) { + CallGraph callGraph, HashSet preeffectsSet) { OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc); switch (fn.kind()) { + case FKind.FlatSESEEnterNode: { + + FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; + if (!fsen.getIsCallerSESEplaceholder()) { + currentMethodSummary.increaseChildSESECount(); + } + + if (currentMethodSummary.getChildSESECount() == 1) { + // need to store pre-effects + currentMethodSummary.getEffectsSet().addAll(preeffectsSet); + + for (Iterator iterator = currentMethodSummary.getEffectsSet() + .iterator(); iterator.hasNext();) { + PreEffectsKey preEffectsKey = (PreEffectsKey) iterator + .next(); + } + + preeffectsSet.clear(); + } + + } + break; + case FKind.FlatSESEExitNode: { - // all object variables are inaccessible + // all object variables are inaccessible. currentConflictsMap = new ParentChildConflictsMap(); } break; @@ -1853,12 +1887,12 @@ public class MLPAnalysis { case FKind.FlatFieldNode: { - if (currentConflictsMap != null) { + FlatFieldNode ffn = (FlatFieldNode) fn; + TempDescriptor dst = ffn.getDst(); + TempDescriptor src = ffn.getSrc(); + FieldDescriptor field = ffn.getField(); - FlatFieldNode ffn = (FlatFieldNode) fn; - TempDescriptor dst = ffn.getDst(); - TempDescriptor src = ffn.getSrc(); - FieldDescriptor field = ffn.getField(); + if (currentConflictsMap != null) { HashSet srcTempSet = getTempDescSetReferenceToSameHRN( og, src); @@ -1886,7 +1920,11 @@ public class MLPAnalysis { .next(); currentConflictsMap.addAccessibleVar(possibleDst); } + } + if (currentMethodSummary.getChildSESECount() == 0) { + // analyze preeffects + preEffectAnalysis(og, src, field, PreEffectsKey.READ_EFFECT); } } @@ -1894,12 +1932,12 @@ public class MLPAnalysis { case FKind.FlatSetFieldNode: { - if (currentConflictsMap != null) { + FlatSetFieldNode fsen = (FlatSetFieldNode) fn; + TempDescriptor dst = fsen.getDst(); + FieldDescriptor field = fsen.getField(); + TempDescriptor src = fsen.getSrc(); - FlatSetFieldNode fsen = (FlatSetFieldNode) fn; - TempDescriptor dst = fsen.getDst(); - FieldDescriptor field = fsen.getField(); - TempDescriptor src = fsen.getSrc(); + if (currentConflictsMap != null) { HashSet srcTempSet = getTempDescSetReferenceToSameHRN( og, src); @@ -1945,6 +1983,12 @@ public class MLPAnalysis { } } } + + if (currentMethodSummary.getChildSESECount() == 0) { + // analyze preeffects + preEffectAnalysis(og, dst, field, PreEffectsKey.WRITE_EFFECT); + } + } break; @@ -1978,6 +2022,7 @@ public class MLPAnalysis { currentConflictsMap.addAccessibleVar(possibleDst); } else { currentConflictsMap.addInaccessibleVar(possibleDst); + } } @@ -2014,8 +2059,112 @@ public class MLPAnalysis { FlatCall fc = (FlatCall) fn; - // look at all possible context, and then take all of them into one - // context + FlatMethod calleeFM = state.getMethodFlat(fc.getMethod()); + + // retrieve callee's method summary + MethodSummary calleeMethodSummary = methodSummaryResults + .get(calleeFM); + + if (calleeMethodSummary != null + && calleeMethodSummary.getChildSESECount() > 0) { + + // when parameter variable is accessible, + // use callee's preeffects to figure out about how it affects + // caller's stall site + + for (int i = 0; i < fc.numArgs(); i++) { + TempDescriptor paramTemp = fc.getArg(i); + + if (currentConflictsMap != null) { + if (currentConflictsMap.isAccessible(paramTemp) + && currentConflictsMap.hasStallSite(paramTemp)) { + // preeffect contribute its effect to caller's stall + // site + + int offset = 0; + if (!fc.getMethod().isStatic()) { + offset = 1; + } + + HashSet preeffectSet = calleeMethodSummary + .getEffectsSetByParamIdx(i + offset); + + for (Iterator iterator = preeffectSet.iterator(); iterator + .hasNext();) { + PreEffectsKey preEffectsKey = (PreEffectsKey) iterator + .next(); + currentConflictsMap.contributeEffect(paramTemp, + preEffectsKey.getType(), preEffectsKey + .getField(), preEffectsKey + .getEffectType()); + } + } + } + // in other cases, child SESE has not been discovered, + // assumes that all variables are accessible + + } + + // If callee has at least one child sese, all parent object + // is going to be inaccessible. + currentConflictsMap = new ParentChildConflictsMap(); + + TempDescriptor returnTemp = fc.getReturnTemp(); + + if (calleeMethodSummary.getReturnValueAccessibility().equals( + MethodSummary.ACCESSIBLE)) { + // when return value is accessible, associate with its + // stall site + currentConflictsMap.addAccessibleVar(returnTemp); + currentConflictsMap.addStallSite(returnTemp, + calleeMethodSummary.getReturnStallSite()); + } else if (calleeMethodSummary.getReturnValueAccessibility() + .equals(MethodSummary.INACCESSIBLE)) { + // when return value is inaccessible + currentConflictsMap.addInaccessibleVar(returnTemp); + } + } + + // TODO: need to handle edge mappings from callee + + } + break; + + case FKind.FlatReturnNode: { + + FlatReturnNode frn = (FlatReturnNode) fn; + TempDescriptor returnTD = frn.getReturnTemp(); + + if (returnTD != null) { + if (currentConflictsMap == null) { + // in this case, all variables is accessible. There are no + // child SESEs. + } else { + if (currentConflictsMap.isAccessible(returnTD)) { + currentMethodSummary + .setReturnValueAccessibility(MethodSummary.ACCESSIBLE); + StallSite returnStallSite = currentConflictsMap + .getStallMap().get(returnTD); + currentMethodSummary + .setReturnStallSite(returnStallSite); + } else { + currentMethodSummary + .setReturnValueAccessibility(MethodSummary.INACCESSIBLE); + } + } + } + } + break; + + case FKind.FlatExit: { + + // store method summary when it has at least one child SESE + if (currentMethodSummary.getChildSESECount() > 0) { + FlatMethod fm = state.getMethodFlat(mc.getDescriptor()); // current + // flat + // method + methodSummaryResults.put(fm, currentMethodSummary); + } } break; @@ -2029,6 +2178,81 @@ public class MLPAnalysis { } + private void preEffectAnalysis(OwnershipGraph og, TempDescriptor td, + FieldDescriptor field, Integer effectType) { + + // analyze preeffects + HashSet hrnSet = getReferenceHeapIDSet(og, td); + for (Iterator iterator = hrnSet.iterator(); iterator.hasNext();) { + HeapRegionNode hrn = (HeapRegionNode) iterator.next(); + if (hrn.isParameter()) { + // effects on param heap region + + Set paramSet = og.idPrimary2paramIndexSet.get(hrn + .getID()); + + if (paramSet != null) { + Iterator paramIter = paramSet.iterator(); + while (paramIter.hasNext()) { + Integer paramID = paramIter.next(); + PreEffectsKey effectKey = new PreEffectsKey(paramID, + field.toString(), field.getType() + .getSafeSymbol(), effectType); + preeffectsSet.add(effectKey); + } + } + + // check weather this heap region is parameter + // reachable... + + paramSet = og.idSecondary2paramIndexSet.get(hrn.getID()); + if (paramSet != null) { + Iterator paramIter = paramSet.iterator(); + + while (paramIter.hasNext()) { + Integer paramID = paramIter.next(); + PreEffectsKey effectKey = new PreEffectsKey(paramID, + field.toString(), field.getType() + .getSafeSymbol(), effectType); + preeffectsSet.add(effectKey); + } + } + + } + } + } + + private MethodSummary analysisMethodCall(FlatMethod fm, OwnershipGraph calleeOG){ + + MethodSummary methodSummary=new MethodSummary(); + + 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); + } + } + } + + + + return methodSummary; + + } + private void codePlansForward( FlatMethod fm ) { diff --git a/Robust/src/Analysis/MLP/MethodSummary.java b/Robust/src/Analysis/MLP/MethodSummary.java new file mode 100644 index 00000000..303eb97d --- /dev/null +++ b/Robust/src/Analysis/MLP/MethodSummary.java @@ -0,0 +1,143 @@ +package Analysis.MLP; + +import java.util.HashSet; +import java.util.Iterator; + +import IR.TypeDescriptor; + +public class MethodSummary { + + public static final Integer VOID=new Integer(0); + public static final Integer ACCESSIBLE = new Integer(1); + public static final Integer INACCESSIBLE=new Integer(2); + + private int childSESECount; + private HashSet effectsSet; + private Integer accessibility; + private StallSite returnStallSite; + + public MethodSummary() { + effectsSet = new HashSet(); + accessibility = MethodSummary.VOID; + childSESECount = 0; + returnStallSite=null; + } + + public void setReturnStallSite(StallSite ss){ + returnStallSite=ss; + } + + public StallSite getReturnStallSite(){ + return returnStallSite; + } + + public void increaseChildSESECount() { + childSESECount++; + } + + public int getChildSESECount() { + return childSESECount; + } + + public Integer getReturnValueAccessibility() { + return accessibility; + } + + public void setReturnValueAccessibility(Integer accessibility) { + this.accessibility = accessibility; + } + + public HashSet getEffectsSet() { + return effectsSet; + } + + @Override + public String toString() { + return "MethodSummary [accessibility=" + accessibility + + ", childSESECount=" + childSESECount + ", effectsSet=" + + effectsSet + "]"; + } + + public HashSet getEffectsSetByParamIdx(int paramIdx){ + + HashSet returnSet=new HashSet(); + + for (Iterator iterator = effectsSet.iterator(); iterator.hasNext();) { + PreEffectsKey preEffectsKey = (PreEffectsKey) iterator.next(); + if(preEffectsKey.getParamIndex().equals(new Integer(paramIdx))){ + returnSet.add(preEffectsKey); + } + } + + return returnSet; + } + +} + +class PreEffectsKey { + + public static final Integer READ_EFFECT = new Integer(1); + public static final Integer WRITE_EFFECT = new Integer(2); + + private String type; + private String field; + private Integer effectType; + private Integer paramIndex; + + public PreEffectsKey(Integer paramIndex, String field, String type, + Integer effectType) { + this.paramIndex = paramIndex; + this.field = field; + this.type = type; + this.effectType = effectType; + } + + public String getType() { + return type; + } + + public String getField() { + return field; + } + + public Integer getEffectType() { + return effectType; + } + + public Integer getParamIndex() { + return paramIndex; + } + + public String toString() { + return "PreEffectsKey [effectType=" + effectType + ", field=" + field + + ", paramIndex=" + paramIndex + ", type=" + type + "]"; + } + + public boolean equals(Object o) { + + if (o == null) { + return false; + } + + if (!(o instanceof PreEffectsKey)) { + return false; + } + + 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())) { + return true; + } else { + return false; + } + + } + +} diff --git a/Robust/src/Analysis/MLP/ParentChildConflictsMap.java b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java index 0d549a54..705a829b 100644 --- a/Robust/src/Analysis/MLP/ParentChildConflictsMap.java +++ b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java @@ -44,9 +44,17 @@ public class ParentChildConflictsMap { StallSite stallSite = new StallSite(); stallMap.put(td, stallSite); } + + public void addStallSite(TempDescriptor td, StallSite stallSite) { + stallMap.put(td, stallSite); + } + + public boolean hasStallSite(TempDescriptor td){ + return stallMap.containsKey(td); + } public boolean isAccessible(TempDescriptor td) { - if (accessibleMap.contains(td) + if (accessibleMap.containsKey(td) && accessibleMap.get(td).equals(ACCESSIBLE)) { return true; } -- 2.34.1