From 95b4c278fa55588afb6c2dc84901ee1557910dcd Mon Sep 17 00:00:00 2001 From: yeom Date: Mon, 14 Nov 2011 22:27:01 +0000 Subject: [PATCH] working on shared loc extension --- .../SSJava/DefinitelyWrittenCheck.java | 395 ++++-------------- 1 file changed, 85 insertions(+), 310 deletions(-) diff --git a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java index f9e4bb00..e9a2f42f 100644 --- a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java +++ b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java @@ -96,8 +96,6 @@ public class DefinitelyWrittenCheck { // maps a flat node to current partial results private Hashtable mapFlatNodeToClearingSummary; - private Hashtable mapFlatNodeToReadSummary; - // maps shared location to the set of descriptors which belong to the shared // location @@ -119,6 +117,8 @@ public class DefinitelyWrittenCheck { // it is for setting clearance flag when all read set is overwritten private Hashtable mapMethodDescriptorToReadSummary; + private Hashtable> mapSharedLocationToCoverSet; + private LinkedList sortedDescriptors; private FlatNode ssjavaLoopEntrance; @@ -163,19 +163,27 @@ public class DefinitelyWrittenCheck { this.mapDescToLocation = new Hashtable(); this.possibleCalleeReadSummarySetToCaller = new HashSet(); this.mapMethodDescriptorToReadSummary = new Hashtable(); - this.mapFlatNodeToReadSummary = new Hashtable(); this.mapFlatNodeToBoundReadSet = new Hashtable>>(); this.mapFlatNodeToBoundMustWriteSet = new Hashtable>>(); this.mapFlatNodeToBoundMayWriteSet = new Hashtable>>(); + this.mapSharedLocationToCoverSet = new Hashtable>(); } public void definitelyWrittenCheck() { if (!ssjava.getAnnotationRequireSet().isEmpty()) { - identifyMainEventLoop(); + initialize(); methodReadWriteSetAnalysis(); methodReadWriteSetAnalysisToEventLoopBody(); eventLoopAnalysis(); computeSharedCoverSet(); + + System.out.println("#"); + System.out.println(mapSharedLocationToCoverSet); + // XXXXXXX + // methodReadWriteSetAnalysis(); + // methodReadWriteSetAnalysisToEventLoopBody(); + // eventLoopAnalysis(); + // XXXXXXX // sharedLocationAnalysis(); // checkSharedLocationResult(); } @@ -650,112 +658,6 @@ public class DefinitelyWrittenCheck { } - private void bindHeapPathReadSummary(FlatCall fc, FlatMethod calleeFlatMethod, ReadSummary curr) { - - ReadSummary boundSet = new ReadSummary(); - - // create mapping from arg idx to its heap paths - Hashtable> mapArgIdx2CallerArgHeapPath = - new Hashtable>(); - - if (fc.getThis() != null) { - // arg idx is starting from 'this' arg - NTuple thisHeapPath = mapHeapPath.get(fc.getThis()); - if (thisHeapPath == null) { - // method is called without creating new flat node representing 'this' - thisHeapPath = new NTuple(); - thisHeapPath.add(fc.getThis()); - } - - mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath); - } - - for (int i = 0; i < fc.numArgs(); i++) { - TempDescriptor arg = fc.getArg(i); - NTuple argHeapPath = computePath(arg); - mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath); - } - - Hashtable mapParamIdx2ParamTempDesc = - new Hashtable(); - int offset = 0; - if (calleeFlatMethod.getMethod().isStatic()) { - // static method does not have implicit 'this' arg - offset = 1; - } - for (int i = 0; i < calleeFlatMethod.numParameters(); i++) { - TempDescriptor param = calleeFlatMethod.getParameter(i); - mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param); - } - - // binding caller's read effects to callee's params - for (int i = 0; i < calleeFlatMethod.numParameters(); i++) { - NTuple argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i)); - - if (argHeapPath != null) { - // if method is static, the first argument is nulll because static - // method does not have implicit "THIS" arg - TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i)); - - // iterate over caller's writing effect set - Set> hpKeySet = curr.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 summary - if (hpKey.startsWith(argHeapPath)) { - NTuple boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath); - boundSet.put(boundHeapPath, curr.get(hpKey)); - } - } - } - } - - // merge into callee's previous read set - ReadSummary calleeSummary = mapMethodDescriptorToReadSummary.get(calleeFlatMethod.getMethod()); - if (calleeSummary == null) { - calleeSummary = new ReadSummary(); - mapMethodDescriptorToReadSummary.put(calleeFlatMethod.getMethod(), calleeSummary); - } - Set inSet = new HashSet(); - inSet.add(boundSet); - mergeReadLocationAnaylsis(calleeSummary, inSet); - - // contribute callee's read summary into the caller's current summary - ReadSummary boundCalleeEfffects = new ReadSummary(); - for (int i = 0; i < calleeFlatMethod.numParameters(); i++) { - NTuple argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i)); - - if (argHeapPath != null) { - // if method is static, the first argument is nulll because static - // method does not have implicit "THIS" arg - TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i)); - - // iterate over callee's writing effect set - Set> hpKeySet = calleeSummary.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, calleeSummary.get(hpKey)); - - } - } - - } - - } - possibleCalleeReadSummarySetToCaller.add(boundCalleeEfffects); - - } - private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc, FlatMethod calleeFlatMethod, ClearingSummary curr) { @@ -919,132 +821,70 @@ public class DefinitelyWrittenCheck { MethodDescriptor md = methodDescriptorsToVisitStack.pop(); FlatMethod fm = state.getMethodFlat(md); - ReadSummary completeSummary = - computeReadSharedDescriptorSet_analyzeMethod(fm, (md.equals(methodContainingSSJavaLoop))); - ReadSummary prevCompleteSummary = mapMethodDescriptorToReadSummary.get(md); - - if (!completeSummary.equals(prevCompleteSummary)) { - mapMethodDescriptorToReadSummary.put(md, completeSummary); - - // results for callee changed, so enqueue dependents caller for - // further analysis - Iterator depsItr = getDependents(md).iterator(); - while (depsItr.hasNext()) { - MethodDescriptor methodNext = depsItr.next(); - if (!methodDescriptorsToVisitStack.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(); - if (!methodDescriptorsToVisitStack.contains(mdNext)) { - methodDescriptorsToVisitStack.add(mdNext); - } - } - calleesToEnqueue.clear(); - - } + computeSharedCoverSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop)); } } - private ReadSummary computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm, - boolean onlyVisitSSJavaLoop) { + private void computeSharedCoverSet_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) { MethodDescriptor md = fm.getMethod(); Set flatNodesToVisit = new HashSet(); + Set visited = new HashSet(); + if (onlyVisitSSJavaLoop) { flatNodesToVisit.add(ssjavaLoopEntrance); } else { flatNodesToVisit.add(fm); } - Set returnNodeSet = new HashSet(); - while (!flatNodesToVisit.isEmpty()) { FlatNode fn = flatNodesToVisit.iterator().next(); flatNodesToVisit.remove(fn); + visited.add(fn); - ReadSummary curr = new ReadSummary(); + computeSharedCoverSet_nodeActions(md, fn); - Set prevSet = new HashSet(); - for (int i = 0; i < fn.numPrev(); i++) { - FlatNode prevFn = fn.getPrev(i); - ReadSummary in = mapFlatNodeToReadSummary.get(prevFn); - if (in != null) { - prevSet.add(in); - } - } - - mergeReadLocationAnaylsis(curr, prevSet); - - computeReadSharedDescriptorSet_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop); - - ReadSummary readPrev = mapFlatNodeToReadSummary.get(fn); - - if (!curr.equals(readPrev)) { - mapFlatNodeToReadSummary.put(fn, curr); - - for (int i = 0; i < fn.numNext(); i++) { - FlatNode nn = fn.getNext(i); + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + if (!visited.contains(nn)) { if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) { flatNodesToVisit.add(nn); } - } - } - } - - ReadSummary completeSummary = new ReadSummary(); - Set summarySet = new HashSet(); - - 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++) { - ReadSummary frnSummary = mapFlatNodeToReadSummary.get(ssjavaLoopEntrance.getPrev(i)); - if (frnSummary != null) { - summarySet.add(frnSummary); - } } - } else { - // merging exit node summary into the complete summary - summarySet.add(mapFlatNodeToReadSummary.get(fm.getFlatExit())); - } - mergeReadLocationAnaylsis(completeSummary, summarySet); - return completeSummary; + } } - private void computeReadSharedDescriptorSet_nodeActions(MethodDescriptor caller, FlatNode fn, - ReadSummary curr, Set returnNodeSet, boolean isSSJavaLoop) { - + private void computeSharedCoverSet_nodeActions(MethodDescriptor md, FlatNode fn) { TempDescriptor lhs; TempDescriptor rhs; FieldDescriptor fld; switch (fn.kind()) { - case FKind.FlatMethod: { - FlatMethod fm = (FlatMethod) fn; - - ReadSummary summary = mapMethodDescriptorToReadSummary.get(fm.getMethod()); - - Set inSet = new HashSet(); - if (summary != null) { - inSet.add(summary); - mergeReadLocationAnaylsis(curr, inSet); + case FKind.FlatLiteralNode: { + FlatLiteralNode fln = (FlatLiteralNode) fn; + lhs = fln.getDst(); + + if (lhs.getType().isPrimitive() && !lhs.getSymbol().startsWith("neverused") + && !lhs.getSymbol().startsWith("srctmp")) { + // only need to care about composite location case here + if (lhs.getType().getExtension() instanceof SSJavaType) { + CompositeLocation compLoc = ((SSJavaType) lhs.getType().getExtension()).getCompLoc(); + Location lastLocElement = compLoc.get(compLoc.getSize() - 1); + // check if the last one is shared loc + if (ssjava.isSharedLocation(lastLocElement)) { + addSharedLocDescriptor(lastLocElement, lhs); + } + } } } @@ -1052,132 +892,69 @@ public class DefinitelyWrittenCheck { case FKind.FlatOpNode: { FlatOpNode fon = (FlatOpNode) fn; - lhs = fon.getDest(); - rhs = fon.getLeft(); - + // for a normal assign node, need to propagate lhs's heap path to + // rhs if (fon.getOp().getOp() == Operation.ASSIGN) { - if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) { - // in ssjavaloop, we need to take care about reading local variables! - NTuple rhsHeapPath = new NTuple(); - NTuple lhsHeapPath = new NTuple(); - rhsHeapPath.add(LOCAL); - Location loc = getLocation(rhs); - if (loc != null && ssjava.isSharedLocation(loc)) { - curr.addRead(rhsHeapPath, loc, rhs); + rhs = fon.getLeft(); + lhs = fon.getDest(); + + if (lhs.getType().isPrimitive() && !lhs.getSymbol().startsWith("neverused") + && !lhs.getSymbol().startsWith("srctmp")) { + // only need to care about composite location case here + if (lhs.getType().getExtension() instanceof SSJavaType) { + CompositeLocation compLoc = ((SSJavaType) lhs.getType().getExtension()).getCompLoc(); + Location lastLocElement = compLoc.get(compLoc.getSize() - 1); + // check if the last one is shared loc + if (ssjava.isSharedLocation(lastLocElement)) { + addSharedLocDescriptor(lastLocElement, lhs); + } } } - } + } } break; - case FKind.FlatFieldNode: - case FKind.FlatElementNode: { + case FKind.FlatSetFieldNode: + case FKind.FlatSetElementNode: { - if (fn.kind() == FKind.FlatFieldNode) { - FlatFieldNode ffn = (FlatFieldNode) fn; - lhs = ffn.getDst(); - rhs = ffn.getSrc(); - fld = ffn.getField(); + // x.f=y; + + if (fn.kind() == FKind.FlatSetFieldNode) { + FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; + lhs = fsfn.getDst(); + fld = fsfn.getField(); + rhs = fsfn.getSrc(); } else { - FlatElementNode fen = (FlatElementNode) fn; - lhs = fen.getDst(); - rhs = fen.getSrc(); - TypeDescriptor td = rhs.getType().dereference(); + FlatSetElementNode fsen = (FlatSetElementNode) fn; + lhs = fsen.getDst(); + rhs = fsen.getSrc(); + TypeDescriptor td = lhs.getType().dereference(); fld = getArrayField(td); } - if (fld.isStatic() && fld.isFinal()) { - break; - } - - // read field - NTuple srcHeapPath = mapHeapPath.get(rhs); - if (srcHeapPath != null) { - // if srcHeapPath is null, it means that it is not reachable from - // callee's parameters. so just ignore it - - NTuple fldHeapPath = new NTuple(srcHeapPath.getList()); - - if (!fld.getType().isArray() && fld.getType().isImmutable()) { - - Location loc; - if (fn.kind() == FKind.FlatElementNode) { - // array element read case - NTuple newHeapPath = new NTuple(); - for (int i = 0; i < fldHeapPath.size() - 1; i++) { - newHeapPath.add(fldHeapPath.get(i)); - } - - Descriptor desc = fldHeapPath.get(fldHeapPath.size() - 1); - if (desc instanceof FieldDescriptor) { - fld = (FieldDescriptor) desc; - loc = getLocation(fld); - fldHeapPath = newHeapPath; - if (loc != null && ssjava.isSharedLocation(loc)) { - curr.addRead(fldHeapPath, loc, fld); - } - } - } else { - loc = getLocation(fld); - if (loc != null && ssjava.isSharedLocation(loc)) { - curr.addRead(fldHeapPath, loc, fld); - } - } - } else { - // propagate rhs's heap path to the lhs - - if (fn.kind() == FKind.FlatElementNode) { - mapDescToLocation.put(lhs, getLocation(rhs)); - } else { - fldHeapPath.add(fld); - } - mapHeapPath.put(lhs, fldHeapPath); - } - + Location fieldLocation = (Location) fld.getType().getExtension(); + if (ssjava.isSharedLocation(fieldLocation)) { + addSharedLocDescriptor(fieldLocation, fld); } } break; - case FKind.FlatCall: { - - FlatCall fc = (FlatCall) fn; - - // find out the set of callees - MethodDescriptor mdCallee = fc.getMethod(); - FlatMethod fmCallee = state.getMethodFlat(mdCallee); - Set setPossibleCallees = new HashSet(); - setPossibleCallees.addAll(callGraph.getMethods(mdCallee)); - - possibleCalleeReadSummarySetToCaller.clear(); - - for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) { - MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next(); - FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee); - - addDependent(mdPossibleCallee, // callee - caller); // caller - - calleesToEnqueue.add(mdPossibleCallee); - - // updates possible callee's initial summary using caller's read status - bindHeapPathReadSummary(fc, calleeFlatMethod, curr); - - } + } + } - // contribute callee's writing effects to the caller - mergeReadLocationAnaylsis(curr, possibleCalleeReadSummarySetToCaller); + private void addSharedLocDescriptor(Location sharedLoc, Descriptor desc) { + Set descSet = mapSharedLocationToCoverSet.get(sharedLoc); + if (descSet == null) { + descSet = new HashSet(); + mapSharedLocationToCoverSet.put(sharedLoc, descSet); } - break; - case FKind.FlatReturnNode: { - returnNodeSet.add(fn); - } - break; + System.out.println("add " + desc + " to shared loc" + sharedLoc); + descSet.add(desc); - } } private void mergeReadLocationAnaylsis(ReadSummary curr, Set inSet) { @@ -1741,7 +1518,7 @@ public class DefinitelyWrittenCheck { } } - private void identifyMainEventLoop() { + private void initialize() { // First, identify ssjava loop entrace // no need to analyze method having ssjava loop @@ -1787,15 +1564,15 @@ public class DefinitelyWrittenCheck { loopIncElements = (Set) ssjavaLoop.loopIncElements(); - } - - private void methodReadWriteSetAnalysis() { - // perform method READ/OVERWRITE analysis + // perform topological sort over the set of methods accessed by the main + // event loop Set methodDescriptorsToAnalyze = new HashSet(); methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet()); - sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze); + } + private void methodReadWriteSetAnalysis() { + // perform method READ/OVERWRITE analysis LinkedList descriptorListToAnalyze = (LinkedList) sortedDescriptors.clone(); @@ -1884,8 +1661,6 @@ public class DefinitelyWrittenCheck { mapFlatMethodToMustWriteSet.put(flatMethodContainingSSJavaLoop, mustWriteSet); mapFlatMethodToMayWriteSet.put(flatMethodContainingSSJavaLoop, mayWriteSet); - loopIncElements = (Set) ssjavaLoop.loopIncElements(); - methodReadWriteSet_analyzeBody(ssjavaLoopEntrance, readSet, mustWriteSet, mayWriteSet, loopIncElements); -- 2.34.1