From 4f0ae65ae50c85ad88d00bf7e14c31a458ea7c56 Mon Sep 17 00:00:00 2001 From: yeom Date: Mon, 11 Jul 2011 19:19:31 +0000 Subject: [PATCH] more changes on shared location analysis. now it works fine with interprocedural analysis --- .../SSJava/DefinitelyWrittenCheck.java | 191 ++++++++++++------ 1 file changed, 133 insertions(+), 58 deletions(-) diff --git a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java index aab4777b..0689d6bc 100644 --- a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java +++ b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java @@ -17,13 +17,11 @@ import IR.State; import IR.TypeDescriptor; import IR.Flat.FKind; import IR.Flat.FlatCall; -import IR.Flat.FlatExit; import IR.Flat.FlatFieldNode; import IR.Flat.FlatLiteralNode; import IR.Flat.FlatMethod; import IR.Flat.FlatNode; import IR.Flat.FlatOpNode; -import IR.Flat.FlatReturnNode; import IR.Flat.FlatSetFieldNode; import IR.Flat.TempDescriptor; import Util.Pair; @@ -81,6 +79,11 @@ public class DefinitelyWrittenCheck { // keep current descriptors to visit in fixed-point interprocedural analysis, private Stack methodDescriptorsToVisitStack; + // when analyzing flatcall, need to re-schedule set of callee + private Set calleesToEnqueue; + + private Set, SharedLocState>> possibleCalleeCompleteSummarySetToCaller; + private LinkedList sortedDescriptors; private FlatNode ssjavaLoopEntrance; @@ -110,10 +113,11 @@ public class DefinitelyWrittenCheck { new Hashtable, SharedLocState>>(); this.mapMethodDescriptorToInitialClearingSummary = new Hashtable, SharedLocState>>(); - this.mapFlatNodeToClearingSummary = - new Hashtable, SharedLocState>>(); this.mapSharedLocation2DescriptorSet = new Hashtable>(); this.methodDescriptorsToVisitStack = new Stack(); + this.calleesToEnqueue = new HashSet(); + this.possibleCalleeCompleteSummarySetToCaller = + new HashSet, SharedLocState>>(); this.LOCAL = new TempDescriptor("LOCAL"); } @@ -128,8 +132,13 @@ public class DefinitelyWrittenCheck { private void checkSharedLocationResult() { + // mapping of method containing ssjava loop has the final result of + // shared location analysis Hashtable, SharedLocState> result = - mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance); + mapMethodDescriptorToCompleteClearingSummary.get(sortedDescriptors.peekFirst()); + + System.out.println("checkSharedLocationResult=" + result); + Set> hpKeySet = result.keySet(); for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) { NTuple hpKey = (NTuple) iterator.next(); @@ -153,21 +162,11 @@ public class DefinitelyWrittenCheck { computeReadSharedDescriptorSet(); System.out.println("Reading Shared Location=" + mapSharedLocation2DescriptorSet); - Set methodDescriptorsToAnalyze = new HashSet(); - methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet()); - - LinkedList descriptorListToAnalyze = - (LinkedList) sortedDescriptors.clone(); - - - methodDescriptorsToVisitStack.clear(); Set methodDescriptorToVistSet = new HashSet(); - methodDescriptorToVistSet.addAll(descriptorListToAnalyze); - while (!descriptorListToAnalyze.isEmpty()) { - MethodDescriptor md = descriptorListToAnalyze.removeFirst(); - methodDescriptorsToVisitStack.add(md); - } + methodDescriptorsToVisitStack.clear(); + methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst()); + methodDescriptorToVistSet.add(sortedDescriptors.peekFirst()); // analyze scheduled methods until there are no more to visit while (!methodDescriptorsToVisitStack.isEmpty()) { @@ -180,13 +179,12 @@ public class DefinitelyWrittenCheck { Hashtable, SharedLocState> prevCompleteSummary = mapMethodDescriptorToCompleteClearingSummary.get(md); - if (!completeSummary.equals(prevCompleteSummary)) { mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary); - - Set dependentsSet=getDependents(md); - if(dependentsSet.size()==0){ + + Set dependentsSet = getDependents(md); + if (dependentsSet.size() == 0) { dependentsSet.add(methodContainingSSJavaLoop); } @@ -199,8 +197,16 @@ public class DefinitelyWrittenCheck { && !methodDescriptorToVistSet.contains(methodNext)) { methodDescriptorsToVisitStack.add(methodNext); } + } + // if there is set of callee to be analyzed, + // add this set into the top of stack + Iterator calleeIter = calleesToEnqueue.iterator(); + while (calleeIter.hasNext()) { + MethodDescriptor mdNext = calleeIter.next(); + methodDescriptorsToVisitStack.add(mdNext); } + calleesToEnqueue.clear(); } @@ -215,7 +221,7 @@ public class DefinitelyWrittenCheck { MethodDescriptor md, boolean onlyVisitSSJavaLoop) { if (state.SSJAVADEBUG) { - System.out.println("\nDefinitely written for shared locations Analyzing: " + md + " " + System.out.println("Definitely written for shared locations Analyzing: " + md + " " + onlyVisitSSJavaLoop); } @@ -224,6 +230,10 @@ public class DefinitelyWrittenCheck { // intraprocedural analysis Set flatNodesToVisit = new HashSet(); + // start a new mapping of partial results for each flat node + mapFlatNodeToClearingSummary = + new Hashtable, SharedLocState>>(); + if (onlyVisitSSJavaLoop) { flatNodesToVisit.add(ssjavaLoopEntrance); } else { @@ -241,21 +251,19 @@ public class DefinitelyWrittenCheck { Set, SharedLocState>> prevSet = new HashSet, SharedLocState>>(); - for (int i = 0; i < fn.numPrev(); i++) { - FlatNode prevFn = fn.getPrev(i); - Hashtable, SharedLocState> in = mapFlatNodeToClearingSummary.get(prevFn); - if (in != null) { - prevSet.add(in); - } + for (int i = 0; i < fn.numPrev(); i++) { + FlatNode prevFn = fn.getPrev(i); + Hashtable, SharedLocState> in = mapFlatNodeToClearingSummary.get(prevFn); + if (in != null) { + prevSet.add(in); } - mergeSharedLocationAnaylsis(curr, prevSet); + } + mergeSharedLocationAnaylsis(curr, prevSet); sharedLocation_nodeActions(fn, curr, returnNodeSet, onlyVisitSSJavaLoop); - Hashtable, SharedLocState> clearingPrev = mapFlatNodeToClearingSummary.get(fn); - if (!curr.equals(clearingPrev)) { mapFlatNodeToClearingSummary.put(fn, curr); @@ -271,23 +279,34 @@ public class DefinitelyWrittenCheck { } - // merging all exit node summary into the complete summary Hashtable, SharedLocState> completeSummary = new Hashtable, SharedLocState>(); - if ((!returnNodeSet.isEmpty()) && (!onlyVisitSSJavaLoop)) { - - Set, SharedLocState>> summarySet = - new HashSet, SharedLocState>>(); - for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlatNode frn = (FlatNode) iterator.next(); + Set, SharedLocState>> summarySet = + new HashSet, SharedLocState>>(); + if (onlyVisitSSJavaLoop) { + // when analyzing ssjava loop, + // complete summary is merging of all previous nodes of ssjava loop + // entrance + for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) { Hashtable, SharedLocState> frnSummary = - mapFlatNodeToClearingSummary.get(frn); - summarySet.add(frnSummary); + mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i)); + if (frnSummary != null) { + summarySet.add(frnSummary); + } + } + } else { + // merging all exit node summary into the complete summary + if (!returnNodeSet.isEmpty()) { + for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlatNode frn = (FlatNode) iterator.next(); + Hashtable, SharedLocState> frnSummary = + mapFlatNodeToClearingSummary.get(frn); + summarySet.add(frnSummary); + } } - - mergeSharedLocationAnaylsis(completeSummary, summarySet); } + mergeSharedLocationAnaylsis(completeSummary, summarySet); return completeSummary; } @@ -300,6 +319,20 @@ public class DefinitelyWrittenCheck { FieldDescriptor fld; switch (fn.kind()) { + case FKind.FlatMethod: { + FlatMethod fm = (FlatMethod) fn; + + Hashtable, SharedLocState> summaryFromCaller = + mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod()); + + Set, SharedLocState>> inSet = + new HashSet, SharedLocState>>(); + inSet.add(summaryFromCaller); + mergeSharedLocationAnaylsis(curr, inSet); + + } + break; + case FKind.FlatOpNode: { FlatOpNode fon = (FlatOpNode) fn; lhs = fon.getDest(); @@ -369,21 +402,21 @@ public class DefinitelyWrittenCheck { TypeDescriptor typeDesc = fc.getThis().getType(); setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc)); - Set, SharedLocState>> calleeCompleteSummarySet = - new HashSet, SharedLocState>>(); + possibleCalleeCompleteSummarySetToCaller.clear(); for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) { MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next(); FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee); + calleesToEnqueue.add(mdPossibleCallee); + // updates possible callee's initial summary using caller's current // writing status Hashtable, SharedLocState> prevCalleeInitSummary = mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee); Hashtable, SharedLocState> calleeInitSummary = - contributeCallerEffectsToCalleeInitSummary(fc, calleeFlatMethod, curr); - + bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr); // if changes, update the init summary // and reschedule the callee for analysis @@ -392,18 +425,10 @@ public class DefinitelyWrittenCheck { mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary); } - Hashtable, SharedLocState> calleeCompleteSummary = - mapMethodDescriptorToCompleteClearingSummary.get(mdPossibleCallee); - - if (calleeCompleteSummary != null) { - calleeCompleteSummarySet.add(mapMethodDescriptorToCompleteClearingSummary - .get(mdPossibleCallee)); - } - } // contribute callee's writing effects to the caller - mergeSharedLocationAnaylsis(curr, calleeCompleteSummarySet); + mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller); } break; @@ -417,7 +442,7 @@ public class DefinitelyWrittenCheck { } - private Hashtable, SharedLocState> contributeCallerEffectsToCalleeInitSummary( + private Hashtable, SharedLocState> bindHeapPathOfCalleeCallerEffects( FlatCall fc, FlatMethod calleeFlatMethod, Hashtable, SharedLocState> curr) { Hashtable, SharedLocState> boundSet = @@ -471,9 +496,59 @@ public class DefinitelyWrittenCheck { } + // contribute callee's complete summary into the caller's current summary + Hashtable, SharedLocState> calleeCompleteSummary = + mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod()); + + if (calleeCompleteSummary != null) { + Hashtable, SharedLocState> boundCalleeEfffects = + new Hashtable, SharedLocState>(); + for (int i = 0; i < calleeFlatMethod.numParameters(); i++) { + NTuple argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i)); + TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i)); + + // iterate over callee's writing effect set + Set> hpKeySet = calleeCompleteSummary.keySet(); + for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) { + NTuple hpKey = (NTuple) iterator.next(); + // current element is reachable caller's arg + // so need to bind it to the caller's side and add it to the callee's + // init summary + if (hpKey.startsWith(calleeParamHeapPath)) { + + NTuple boundHeapPathForCaller = replace(hpKey, argHeapPath); + + boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey) + .clone()); + + } + } + } + possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects); + } + return boundSet; } + private NTuple replace(NTuple hpKey, NTuple argHeapPath) { + + // replace the head of heap path with caller's arg path + // for example, heap path 'param.a.b' in callee's side will be replaced with + // (corresponding arg heap path).a.b for caller's side + + NTuple bound = new NTuple(); + + for (int i = 0; i < argHeapPath.size(); i++) { + bound.add(argHeapPath.get(i)); + } + + for (int i = 1; i < hpKey.size(); i++) { + bound.add(hpKey.get(i)); + } + + return bound; + } + private NTuple replace(NTuple effectHeapPath, NTuple argHeapPath, TempDescriptor calleeParamHeapPath) { // replace the head of caller's heap path with callee's param heap path @@ -1343,7 +1418,7 @@ public class DefinitelyWrittenCheck { Pair, Boolean> pair = currState.getMap().get(locKey); boolean currentFlag = pair.getSecond().booleanValue(); Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey)); - if(inFlag!=null){ + if (inFlag != null) { boolean newFlag = currentFlag | inFlag.booleanValue(); if (currentFlag != newFlag) { currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag))); -- 2.34.1