From: yeom Date: Thu, 29 Oct 2009 01:23:46 +0000 (+0000) Subject: changes to handle fixed point analysis properly + bug fix. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=49fa81cd8913dc419ed94afc24981ed8ee4b8cf2 changes to handle fixed point analysis properly + bug fix. --- diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index f00c0195..88738003 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -53,8 +53,6 @@ public class MLPAnalysis { private Hashtable< MethodContext, HashSet> mapMethodContextToLiveInAllocationSiteSet; 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. @@ -116,7 +114,6 @@ public class MLPAnalysis { mapMethodContextToLiveInAllocationSiteSet = new Hashtable< MethodContext, HashSet>(); conflictsResults = new Hashtable < FlatNode, ParentChildConflictsMap >(); - stallEdgeMapping = new Hashtable < ReferenceEdge, StallSite >(); methodSummaryResults=new Hashtable(); FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() ); @@ -963,7 +960,8 @@ public class MLPAnalysis { FlatCall fc = (FlatCall) fn; - if(fc.numArgs()>0){ + + if(fc.numArgs()>0 && fc.getMethod().equals(calleeMC.getDescriptor())){ MethodContext calleeMCfromOG = ownAnalysis.getCalleeMethodContext( callerMC, fc); @@ -1802,12 +1800,11 @@ public class MLPAnalysis { HashSet mcSet = ownAnalysis .getAllMethodContextSetByDescriptor(md); Iterator mcIter = mcSet.iterator(); - - currentMethodSummary=new MethodSummary(); - preeffectsSet=new HashSet(); - - while (mcIter.hasNext()) { + currentMethodSummary = new MethodSummary(); + preeffectsSet = new HashSet(); + + while (mcIter.hasNext()) { MethodContext mc = mcIter.next(); Set visited = new HashSet(); @@ -1815,22 +1812,49 @@ 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, preeffectsSet); - 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); + ParentChildConflictsMap prevResult = conflictsResults + .get(fn); + + // merge sets from control flow + ParentChildConflictsMap currentConflictsMap = new ParentChildConflictsMap(); + for (int i = 0; i < fn.numPrev(); i++) { + FlatNode prevFlatNode = fn.getPrev(i); + ParentChildConflictsMap incoming = conflictsResults + .get(prevFlatNode); + if (incoming != null) { + currentConflictsMap.merge(incoming); + } + } + + conflicts_nodeAction(mc, fn, callGraph, preeffectsSet, + currentConflictsMap); + + // 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++) { + FlatNode nn = fn.getNext(i); + if (!visited.contains(nn)) { + flatNodesToVisit.add(nn); + } + } + }else{ + if (!currentConflictsMap.equals(prevResult)) { + conflictsResults.put(fn, currentConflictsMap); + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + flatNodesToVisit.add(nn); + } } } + } } methodSummaryResults.put(fm, currentMethodSummary); @@ -1839,14 +1863,14 @@ public class MLPAnalysis { } private void conflicts_nodeAction(MethodContext mc, FlatNode fn, - CallGraph callGraph, HashSet preeffectsSet) { + CallGraph callGraph, HashSet preeffectsSet,ParentChildConflictsMap currentConflictsMap) { OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc); switch (fn.kind()) { case FKind.FlatSESEEnterNode: { - + FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; if (!fsen.getIsCallerSESEplaceholder()) { currentMethodSummary.increaseChildSESECount(); @@ -1869,14 +1893,21 @@ public class MLPAnalysis { break; case FKind.FlatSESEExitNode: { - // all object variables are inaccessible. - currentConflictsMap = new ParentChildConflictsMap(); + + FlatSESEExitNode fsen = (FlatSESEExitNode) fn; + + if (!fsen.getFlatEnter().getIsCallerSESEplaceholder()) { + // all object variables are inaccessible. + currentConflictsMap.setAfterChildSESE(true); + currentConflictsMap = new ParentChildConflictsMap(); + } + } break; case FKind.FlatNew: { - if (currentConflictsMap != null) { + if (currentConflictsMap.isAfterChildSESE()) { FlatNew fnew = (FlatNew) fn; TempDescriptor dst = fnew.getDst(); currentConflictsMap.addAccessibleVar(dst); @@ -1892,7 +1923,7 @@ public class MLPAnalysis { TempDescriptor src = ffn.getSrc(); FieldDescriptor field = ffn.getField(); - if (currentConflictsMap != null) { + if (currentConflictsMap.isAfterChildSESE()) { HashSet srcTempSet = getTempDescSetReferenceToSameHRN( og, src); @@ -1901,7 +1932,8 @@ public class MLPAnalysis { TempDescriptor possibleSrc = (TempDescriptor) iterator .next(); if (!currentConflictsMap.isAccessible(possibleSrc)) { - currentConflictsMap.addStallSite(possibleSrc); + HashSet refHRN=getReferenceHeapIDSet(og, possibleSrc); + currentConflictsMap.addStallSite(possibleSrc,refHRN); } currentConflictsMap.addAccessibleVar(possibleSrc); @@ -1936,8 +1968,8 @@ public class MLPAnalysis { TempDescriptor dst = fsen.getDst(); FieldDescriptor field = fsen.getField(); TempDescriptor src = fsen.getSrc(); - - if (currentConflictsMap != null) { + + if (currentConflictsMap.isAfterChildSESE()) { HashSet srcTempSet = getTempDescSetReferenceToSameHRN( og, src); @@ -1946,7 +1978,8 @@ public class MLPAnalysis { TempDescriptor possibleSrc = (TempDescriptor) iterator .next(); if (!currentConflictsMap.isAccessible(possibleSrc)) { - currentConflictsMap.addStallSite(possibleSrc); + HashSet refHRN=getReferenceHeapIDSet(og, possibleSrc); + currentConflictsMap.addStallSite(possibleSrc,refHRN); } currentConflictsMap.addAccessibleVar(possibleSrc); } @@ -1959,7 +1992,8 @@ public class MLPAnalysis { .next(); if (!currentConflictsMap.isAccessible(possibleDst)) { - currentConflictsMap.addStallSite(possibleDst); + HashSet refHRN=getReferenceHeapIDSet(og, possibleDst); + currentConflictsMap.addStallSite(possibleDst,refHRN); } currentConflictsMap.addAccessibleVar(possibleDst); // contribute write effect on destination's stall site @@ -1978,8 +2012,9 @@ public class MLPAnalysis { .hasNext();) { ReferenceEdge referenceEdge = (ReferenceEdge) iterator .next(); - stallEdgeMapping.put(referenceEdge, ss); - // System.out.println("STALL EDGE MAPPING WITH "+referenceEdge+" -> "+ss); + if(!(referenceEdge.getSrc() instanceof LabelNode)){ + currentConflictsMap.addStallEdge(referenceEdge, ss); + } } } } @@ -1993,13 +2028,12 @@ public class MLPAnalysis { break; case FKind.FlatOpNode: { - if (currentConflictsMap != null) { + if (currentConflictsMap.isAfterChildSESE()) { // 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) { TempDescriptor dst = fon.getDest(); TempDescriptor src = fon.getLeft(); @@ -2032,29 +2066,6 @@ public class MLPAnalysis { } 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; @@ -2075,7 +2086,7 @@ public class MLPAnalysis { for (int i = 0; i < fc.numArgs(); i++) { TempDescriptor paramTemp = fc.getArg(i); - if (currentConflictsMap != null) { + if (currentConflictsMap.isAfterChildSESE()) { if (currentConflictsMap.isAccessible(paramTemp) && currentConflictsMap.hasStallSite(paramTemp)) { // preeffect contribute its effect to caller's stall @@ -2123,10 +2134,16 @@ public class MLPAnalysis { // when return value is inaccessible currentConflictsMap.addInaccessibleVar(returnTemp); } + + + // TODO: need to handle edge mappings from callee + HashSet stallParamIdx=calleeMethodSummary.getStallParamIdxSet(); + for (Iterator iterator = stallParamIdx.iterator(); iterator + .hasNext();) { + Integer paramIdx = (Integer) iterator.next(); + } } - // TODO: need to handle edge mappings from callee - } break; @@ -2136,8 +2153,8 @@ public class MLPAnalysis { TempDescriptor returnTD = frn.getReturnTemp(); if (returnTD != null) { - if (currentConflictsMap == null) { - // in this case, all variables is accessible. There are no + if (!currentConflictsMap.isAfterChildSESE()) { + // in this case, all variables are accessible. There are no // child SESEs. } else { if (currentConflictsMap.isAccessible(returnTD)) { @@ -2160,9 +2177,33 @@ public class MLPAnalysis { // store method summary when it has at least one child SESE if (currentMethodSummary.getChildSESECount() > 0) { - FlatMethod fm = state.getMethodFlat(mc.getDescriptor()); // current - // flat - // method + // current flat method + FlatMethod fm = state.getMethodFlat(mc.getDescriptor()); + Set stallTempSet=currentConflictsMap.getStallMap().keySet(); + for (Iterator iterator = stallTempSet.iterator(); iterator + .hasNext();) { + TempDescriptor stallTD = (TempDescriptor) iterator.next(); + StallSite ss = currentConflictsMap.getStallMap().get( + stallTD); + + HashSet stallSiteHRNSet = ss.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())); + } + + } + + } methodSummaryResults.put(fm, currentMethodSummary); } @@ -2171,11 +2212,6 @@ public class MLPAnalysis { } - // for every program point, we keep accessible map and stall map. - if (currentConflictsMap != null) { - conflictsResults.put(fn, currentConflictsMap); - } - } private void preEffectAnalysis(OwnershipGraph og, TempDescriptor td, @@ -2222,39 +2258,6 @@ public class MLPAnalysis { } } - 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 ) { // start from flat method top, visit every node in diff --git a/Robust/src/Analysis/MLP/MethodSummary.java b/Robust/src/Analysis/MLP/MethodSummary.java index 303eb97d..b86081fc 100644 --- a/Robust/src/Analysis/MLP/MethodSummary.java +++ b/Robust/src/Analysis/MLP/MethodSummary.java @@ -2,8 +2,7 @@ package Analysis.MLP; import java.util.HashSet; import java.util.Iterator; - -import IR.TypeDescriptor; +import java.util.Set; public class MethodSummary { @@ -15,12 +14,24 @@ public class MethodSummary { private HashSet effectsSet; private Integer accessibility; private StallSite returnStallSite; + private HashSet stallParamIdxSet; public MethodSummary() { effectsSet = new HashSet(); accessibility = MethodSummary.VOID; childSESECount = 0; returnStallSite=null; + stallParamIdxSet=new HashSet(); + } + + public HashSet getStallParamIdxSet(){ + return stallParamIdxSet; + } + + public void addStallParamIdxSet(Set newSet){ + if(newSet!=null){ + stallParamIdxSet.addAll(newSet); + } } public void setReturnStallSite(StallSite ss){ diff --git a/Robust/src/Analysis/MLP/ParentChildConflictsMap.java b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java index 705a829b..2a44dce1 100644 --- a/Robust/src/Analysis/MLP/ParentChildConflictsMap.java +++ b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java @@ -5,7 +5,9 @@ import java.util.Hashtable; import java.util.Iterator; import java.util.Set; +import Analysis.OwnershipAnalysis.HeapRegionNode; import Analysis.OwnershipAnalysis.ReachabilitySet; +import Analysis.OwnershipAnalysis.ReferenceEdge; import Analysis.OwnershipAnalysis.TokenTupleSet; import IR.Flat.TempDescriptor; @@ -16,13 +18,38 @@ public class ParentChildConflictsMap { private Hashtable accessibleMap; private Hashtable stallMap; + private Hashtable < ReferenceEdge, StallSite > stallEdgeMap; + + private boolean afterChildSESE; public ParentChildConflictsMap() { accessibleMap = new Hashtable(); stallMap = new Hashtable(); + stallEdgeMap= new Hashtable < ReferenceEdge, StallSite >(); + afterChildSESE=false; } + + public Hashtable < ReferenceEdge, StallSite > getStallEdgeMap(){ + return stallEdgeMap; + } + + public void addStallEdge(ReferenceEdge edge, StallSite site){ + stallEdgeMap.put(edge, site); + } + + public StallSite getStallSiteByEdge(ReferenceEdge edge){ + return stallEdgeMap.get(edge); + } + + public void setAfterChildSESE(boolean b){ + this.afterChildSESE=b; + } + + public boolean isAfterChildSESE(){ + return afterChildSESE; + } public Hashtable getAccessibleMap() { return accessibleMap; @@ -40,8 +67,8 @@ public class ParentChildConflictsMap { accessibleMap.put(td, INACCESSIBLE); } - public void addStallSite(TempDescriptor td) { - StallSite stallSite = new StallSite(); + public void addStallSite(TempDescriptor td, HashSet heapSet) { + StallSite stallSite=new StallSite(heapSet); stallMap.put(td, stallSite); } @@ -72,6 +99,10 @@ public class ParentChildConflictsMap { } public void merge(ParentChildConflictsMap newConflictsMap) { + + if(afterChildSESE==false && newConflictsMap.isAfterChildSESE()){ + this.afterChildSESE=true; + } Hashtable newAccessibleMap = newConflictsMap .getAccessibleMap(); @@ -100,6 +131,10 @@ public class ParentChildConflictsMap { StallSite newStallSite = newStallMap.get(key); StallSite currentStallSite = getStallMap().get(key); + + if(currentStallSite==null){ + currentStallSite=new StallSite(); + } // handle effects HashSet currentEffectSet = currentStallSite.getEffectSet(); @@ -113,10 +148,10 @@ public class ParentChildConflictsMap { } // handle heap region - HashSet currentHRNSet = currentStallSite.getHRNIDSet(); - HashSet newHRNSet = newStallSite.getHRNIDSet(); + HashSet currentHRNSet = currentStallSite.getHRNSet(); + HashSet newHRNSet = newStallSite.getHRNSet(); for (Iterator iterator2 = newHRNSet.iterator(); iterator2.hasNext();) { - Integer hrnID = (Integer) iterator2.next(); + HeapRegionNode hrnID = (HeapRegionNode) iterator2.next(); if (!currentHRNSet.contains(hrnID)) { currentHRNSet.add(hrnID); } @@ -130,15 +165,54 @@ public class ParentChildConflictsMap { TokenTupleSet tokenTupleSet = (TokenTupleSet) ttsIter.next(); currentRSet.add(tokenTupleSet); } + + StallSite merged=new StallSite(currentEffectSet, currentHRNSet, + currentRSet); getStallMap() .put( key, - new StallSite(currentEffectSet, currentHRNSet, - currentRSet)); + merged); } + + // merge edge mapping + + 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); + } + + } + + public boolean equals(Object o) { + + if (o == null) { + return false; + } + + if (!(o instanceof ParentChildConflictsMap)) { + return false; + } + + ParentChildConflictsMap in = (ParentChildConflictsMap) o; + + if (afterChildSESE==in.isAfterChildSESE() && accessibleMap.equals(in.getAccessibleMap()) + && stallMap.equals(in.getStallMap())) { + return true; + } else { + return false; + } + + } + public String toString() { + return "ParentChildConflictsMap [accessibleMap=" + accessibleMap + + ", afterChildSESE=" + afterChildSESE + ", stallMap=" + + stallMap + "]"; } }