From c2b1f2910bac539cdf66b6110cf9cb3346fb6bc6 Mon Sep 17 00:00:00 2001 From: yeom Date: Tue, 29 Nov 2011 20:07:16 +0000 Subject: [PATCH] have n-to-1 mapping from location paths to a set of may-written shared descriptors. every call site propagates a set of may-written shared descriptors to the caller's arg location paths. if an argument is bound to the callee's parameter leading to a write effect on shared locations, the corresponding location path that is started with the callee's param location will be bound to the caller's arg location path. For example, suppose that caller has an arg with location path and corresponding callee has param with location . If the param leads to an write effect on shared location "F" through the location path , the caller will have an write effect on F with the location path . --- .../SSJava/DefinitelyWrittenCheck.java | 240 +++++++++++++----- Robust/src/Analysis/SSJava/Location.java | 4 + .../src/Analysis/SSJava/MultiSourceMap.java | 67 +++++ Robust/src/Analysis/SSJava/NTuple.java | 2 +- 4 files changed, 254 insertions(+), 59 deletions(-) create mode 100644 Robust/src/Analysis/SSJava/MultiSourceMap.java diff --git a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java index a5724874..c4524b92 100644 --- a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java +++ b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java @@ -58,7 +58,7 @@ public class DefinitelyWrittenCheck { private Hashtable> mapHeapPath; // maps a temp descriptor to its composite location - private Hashtable> mapDescriptorToComposteLocation; + private Hashtable> mapDescriptorToLocationStrPath; // maps a flat method to the READ that is the set of heap path that is // expected to be written before method invocation @@ -129,12 +129,12 @@ public class DefinitelyWrittenCheck { // it is for setting clearance flag when all read set is overwritten private Hashtable mapMethodDescriptorToReadSummary; + private MultiSourceMap mapLocationPathToMayWrittenSet; + private Hashtable mapFlatNodeToSharedLocMapping; private Hashtable> mapSharedLocationToCoverSet; - private Hashtable, Set> mapSharedLocationTupleToMayWriteSet; - private LinkedList sortedDescriptors; private FlatNode ssjavaLoopEntrance; @@ -160,7 +160,7 @@ public class DefinitelyWrittenCheck { this.mapFlatNodeToMustWriteSet = new Hashtable>>(); this.mapDescriptorToSetDependents = new Hashtable>(); this.mapHeapPath = new Hashtable>(); - this.mapDescriptorToComposteLocation = new Hashtable>(); + this.mapDescriptorToLocationStrPath = new Hashtable>(); this.mapFlatMethodToReadSet = new Hashtable>>(); this.mapFlatMethodToMustWriteSet = new Hashtable>>(); this.mapFlatMethodToMayWriteSet = new Hashtable>>(); @@ -191,7 +191,7 @@ public class DefinitelyWrittenCheck { this.calleeUnionBoundDeleteSet = new HashSet>(); this.calleeIntersectBoundSharedSet = new SharedLocMappingSet(); this.mapFlatMethodToSharedLocMappingSet = new Hashtable(); - this.mapSharedLocationTupleToMayWriteSet = new Hashtable, Set>(); + this.mapLocationPathToMayWrittenSet = new MultiSourceMap(); } public void definitelyWrittenCheck() { @@ -200,7 +200,7 @@ public class DefinitelyWrittenCheck { computeSharedCoverSet(); System.out.println("#"); - System.out.println(mapSharedLocationTupleToMayWriteSet); + System.out.println(mapLocationPathToMayWrittenSet); // methodReadWriteSetAnalysis(); @@ -1100,17 +1100,22 @@ public class DefinitelyWrittenCheck { // analyze scheduled methods until there are no more to visit while (!methodDescriptorsToVisitStack.isEmpty()) { MethodDescriptor md = methodDescriptorsToVisitStack.pop(); - FlatMethod fm = state.getMethodFlat(md); - computeSharedCoverSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop)); - } + computeSharedCoverSetForEventLoop(); + + } + + private void computeSharedCoverSetForEventLoop() { + computeSharedCoverSet_analyzeMethod(state.getMethodFlat(methodContainingSSJavaLoop), true); } private void computeSharedCoverSet_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) { + System.out.println("computeSharedCoverSet_analyzeMethod=" + fm); + MethodDescriptor md = fm.getMethod(); Set flatNodesToVisit = new HashSet(); @@ -1142,6 +1147,10 @@ public class DefinitelyWrittenCheck { } + System.out.println("result=" + mapLocationPathToMayWrittenSet); + System.out.println("###############"); + System.out.println(); + } private void computeSharedCoverSet_nodeActions(MethodDescriptor md, FlatNode fn) { @@ -1180,24 +1189,26 @@ public class DefinitelyWrittenCheck { lhs = fon.getDest(); if (lhs.getType().isPrimitive() && !lhs.getSymbol().startsWith("neverused") - && !lhs.getSymbol().startsWith("srctmp")) { - - System.out.println("FN=" + fn); - NTuple loc = deriveLocationTuple(md, rhs); - System.out.println("LOC TUPLE=" + loc); - - addDescriptorToSharedLocMayWriteSet(loc, lhs); - - // // 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); - // } - // } + && !lhs.getSymbol().startsWith("srctmp") && !lhs.getSymbol().startsWith("leftop") + && !lhs.getSymbol().startsWith("rightop")) { + + NTuple locStrTuple = deriveLocationTuple(md, rhs); + mapLocationPathToMayWrittenSet.put(locStrTuple, null, lhs); + + } + + if (mapDescriptorToLocationStrPath.containsKey(rhs)) { + mapDescriptorToLocationStrPath.put(lhs, mapDescriptorToLocationStrPath.get(rhs)); + } else { + if (rhs.getType().getExtension() instanceof SSJavaType) { + NTuple locStrTuple = new NTuple(); + NTuple locTuple = + ((SSJavaType) rhs.getType().getExtension()).getCompLoc().getTuple(); + for (int i = 0; i < locTuple.size(); i++) { + locStrTuple.add(locTuple.get(i).getSymbol()); + } + mapDescriptorToLocationStrPath.put(lhs, locStrTuple); + } } } @@ -1227,10 +1238,11 @@ public class DefinitelyWrittenCheck { addSharedLocDescriptor(fieldLocation, fld); System.out.println("FIELD WRITE FN=" + fn); - NTuple locTuple = deriveLocationTuple(md, lhs); - locTuple.addAll(deriveLocationTuple(md, fld)); - System.out.println("LOC TUPLE=" + locTuple); - addDescriptorToSharedLocMayWriteSet(locTuple, fld); + NTuple locStrTuple = deriveLocationTuple(md, lhs); + locStrTuple.addAll(deriveLocationTuple(md, fld)); + System.out.println("LOC TUPLE=" + locStrTuple); + + mapLocationPathToMayWrittenSet.put(locStrTuple, null, fld); } @@ -1260,12 +1272,18 @@ public class DefinitelyWrittenCheck { break; } - System.out.println("FN=" + fn); - NTuple locTuple = deriveLocationTuple(md, rhs); - locTuple.addAll(deriveLocationTuple(md, fld)); - System.out.println("LOC TUPLE=" + locTuple); - mapDescriptorToComposteLocation.put(lhs, locTuple); - System.out.println("mapping " + lhs + " to " + locTuple); + NTuple locStrTuple = deriveLocationTuple(md, rhs); + locStrTuple.addAll(deriveLocationTuple(md, fld)); + mapDescriptorToLocationStrPath.put(lhs, locStrTuple); + + } + break; + + case FKind.FlatCall: { + + System.out.println("###FLATCALL=" + fn); + FlatCall fc = (FlatCall) fn; + bindLocationPathCallerArgWithCalleeParam(md, fc); } break; @@ -1273,14 +1291,110 @@ public class DefinitelyWrittenCheck { } } - private void addDescriptorToSharedLocMayWriteSet(NTuple locTuple, Descriptor d) { + private void bindLocationPathCallerArgWithCalleeParam(MethodDescriptor mdCaller, FlatCall fc) { + + if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) { + // ssjava util case! + // have write effects on the first argument + TempDescriptor arg = fc.getArg(0); + NTuple argLocationStrPath = deriveLocationTuple(mdCaller, arg); + NTuple argHeapPath = computePath(arg); + mapLocationPathToMayWrittenSet.put(argLocationStrPath, null, + argHeapPath.get(argHeapPath.size() - 1)); + + } else { + + // if arg is not primitive type, we need to propagate maywritten set to + // the caller's location path + + MethodDescriptor mdCallee = fc.getMethod(); + Set setPossibleCallees = new HashSet(); + setPossibleCallees.addAll(callGraph.getMethods(mdCallee)); + + // create mapping from arg idx to its heap paths + Hashtable> mapArgIdx2CallerAgLocationStrPath = + new Hashtable>(); + + // arg idx is starting from 'this' arg + if (fc.getThis() != null) { + NTuple thisLocationStrPath = deriveLocationTuple(mdCaller, fc.getThis()); + mapArgIdx2CallerAgLocationStrPath.put(Integer.valueOf(0), thisLocationStrPath); + } + + for (int i = 0; i < fc.numArgs(); i++) { + TempDescriptor arg = fc.getArg(i); + NTuple argLocationStrPath = deriveLocationTuple(mdCaller, arg); + mapArgIdx2CallerAgLocationStrPath.put(Integer.valueOf(i + 1), argLocationStrPath); + } + + for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) { + MethodDescriptor callee = (MethodDescriptor) iterator.next(); + FlatMethod calleeFlatMethod = state.getMethodFlat(callee); + + // binding caller's args and callee's params + + 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); + } + + Set keySet = mapArgIdx2CallerAgLocationStrPath.keySet(); + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + Integer idx = (Integer) iterator2.next(); + NTuple callerArgLocationStrPath = mapArgIdx2CallerAgLocationStrPath.get(idx); + + TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx); + NTuple calleeLocationStrPath = deriveLocationTuple(mdCallee, calleeParam); + + createNewMappingOfMayWrittenSet(callerArgLocationStrPath, calleeLocationStrPath); + + } + + } + + } + + } + + private void createNewMappingOfMayWrittenSet(NTuple callerPath, + NTuple calleeParamPath) { + + // propagate may-written-set associated with the key that is started with + // calleepath to the caller + // 1) makes a new key by combining caller path and callee path(except local + // loc element of param) + // 2) create new mapping of may-written-set of callee path to caller path + + // extract all may written effect accessed through callee param path + Hashtable, Set> mapping = + mapLocationPathToMayWrittenSet.getMappingByStartedWith(calleeParamPath); + System.out.println("CALLEE MAPPING=" + mapping); + + Set> calleeKeySet = mapping.keySet(); + for (Iterator iterator = calleeKeySet.iterator(); iterator.hasNext();) { + NTuple calleeKey = (NTuple) iterator.next(); + Set calleeMayWriteSet = mapLocationPathToMayWrittenSet.get(calleeKey); + + NTuple newKey = new NTuple(); + newKey.addAll(callerPath); + // need to replace the local location with the caller's path so skip the + // local location of the parameter + for (int i = 1; i < calleeKey.size(); i++) { + newKey.add(calleeKey.get(i)); + } + + System.out.println("calleeParamPath=" + calleeParamPath + " newKey=" + newKey + + " maywriteSet=" + calleeMayWriteSet); + mapLocationPathToMayWrittenSet.put(newKey, calleeKey, calleeMayWriteSet); - Set mayWriteSet = mapSharedLocationTupleToMayWriteSet.get(locTuple); - if (mayWriteSet == null) { - mayWriteSet = new HashSet(); - mapSharedLocationTupleToMayWriteSet.put(locTuple, mayWriteSet); } - mayWriteSet.add(d); } @@ -1740,7 +1854,7 @@ public class DefinitelyWrittenCheck { } - private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) { + private void bindHeapPathCallerArgWithCalleeParam(FlatCall fc) { // compute all possible callee set // transform all READ/WRITE set from the any possible // callees to the caller @@ -2395,7 +2509,7 @@ public class DefinitelyWrittenCheck { FlatCall fc = (FlatCall) fn; - bindHeapPathCallerArgWithCaleeParam(fc); + bindHeapPathCallerArgWithCalleeParam(fc); mapFlatNodeToBoundReadSet.put(fn, calleeUnionBoundReadSet); mapFlatNodeToBoundMustWriteSet.put(fn, calleeIntersectBoundMustWriteSet); @@ -2734,34 +2848,44 @@ public class DefinitelyWrittenCheck { } } - private NTuple deriveLocationTuple(MethodDescriptor md, TempDescriptor td) { + private NTuple deriveThisLocationTuple(MethodDescriptor md) { + String thisLocIdentifier = ssjava.getMethodLattice(md).getThisLoc(); + Location thisLoc = new Location(md, thisLocIdentifier); + NTuple locStrTuple = new NTuple(); + locStrTuple.add(thisLoc.getSymbol()); + return locStrTuple; + } + + private NTuple deriveLocationTuple(MethodDescriptor md, TempDescriptor td) { assert td.getType() != null; - if (mapDescriptorToComposteLocation.containsKey(td)) { - return mapDescriptorToComposteLocation.get(td); + if (mapDescriptorToLocationStrPath.containsKey(td)) { + return mapDescriptorToLocationStrPath.get(td); } else { if (td.getSymbol().startsWith("this")) { - String thisLocIdentifier = ssjava.getMethodLattice(md).getThisLoc(); - Location thisLoc = new Location(md, thisLocIdentifier); - NTuple locTuple = new NTuple(); - locTuple.add(thisLoc); - return locTuple; + return deriveThisLocationTuple(md); } else { - return ((SSJavaType) td.getType().getExtension()).getCompLoc().getTuple(); + NTuple locTuple = + ((SSJavaType) td.getType().getExtension()).getCompLoc().getTuple(); + NTuple locStrTuple = new NTuple(); + for (int i = 0; i < locTuple.size(); i++) { + locStrTuple.add(locTuple.get(i).getSymbol()); + } + return locStrTuple; } } } - private NTuple deriveLocationTuple(MethodDescriptor md, FieldDescriptor fld) { + private NTuple deriveLocationTuple(MethodDescriptor md, FieldDescriptor fld) { assert fld.getType() != null; Location fieldLoc = (Location) fld.getType().getExtension(); - NTuple locTuple = new NTuple(); - locTuple.add(fieldLoc); - return locTuple; + NTuple locStrTuple = new NTuple(); + locStrTuple.add(fieldLoc.getSymbol()); + return locStrTuple; } } \ No newline at end of file diff --git a/Robust/src/Analysis/SSJava/Location.java b/Robust/src/Analysis/SSJava/Location.java index 06dfdb99..271b447f 100644 --- a/Robust/src/Analysis/SSJava/Location.java +++ b/Robust/src/Analysis/SSJava/Location.java @@ -81,6 +81,10 @@ public class Location implements TypeExtension { return "Loc[" + d.getSymbol() + "." + loc + "]"; } + public String getSymbol() { + return d.getSymbol() + "." + loc; + } + public static Location createTopLocation(Descriptor d) { Location topLoc = new Location(d, TOP); return topLoc; diff --git a/Robust/src/Analysis/SSJava/MultiSourceMap.java b/Robust/src/Analysis/SSJava/MultiSourceMap.java new file mode 100644 index 00000000..68135da2 --- /dev/null +++ b/Robust/src/Analysis/SSJava/MultiSourceMap.java @@ -0,0 +1,67 @@ +package Analysis.SSJava; + +import java.util.HashSet; +import java.util.Hashtable; +import java.util.Iterator; +import java.util.Set; + +public class MultiSourceMap { + + Hashtable, Set> map; + + public MultiSourceMap() { + map = new Hashtable, Set>(); + } + + public void put(NTuple key, NTuple setKey, Set set) { + + if (!map.containsKey(setKey)) { + map.put(setKey, set); + } + map.put(key, set); + } + + public void put(NTuple key, NTuple setKey, V value) { + + if (setKey == null) { + if (map.containsKey(key)) { + Set set = map.get(key); + set.add(value); + } else { + // first insert + Set set = new HashSet(); + set.add(value); + map.put(key, set); + } + } else { + assert map.containsKey(setKey); + Set set = map.get(setKey); + set.add(value); + map.put(key, set); + } + } + + public Set get(NTuple key) { + return map.get(key); + } + + public String toString() { + return map.toString(); + } + + public Hashtable, Set> getMappingByStartedWith(NTuple in) { + + Hashtable, Set> rtrMapping = new Hashtable, Set>(); + + Set> keySet = map.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + NTuple key = (NTuple) iterator.next(); + if (key.startsWith(in)) { + rtrMapping.put(key, map.get(key)); + } + } + + return rtrMapping; + + } +} diff --git a/Robust/src/Analysis/SSJava/NTuple.java b/Robust/src/Analysis/SSJava/NTuple.java index 3190cef0..a968908c 100644 --- a/Robust/src/Analysis/SSJava/NTuple.java +++ b/Robust/src/Analysis/SSJava/NTuple.java @@ -51,7 +51,7 @@ public class NTuple { if (o == null || o.getClass() != this.getClass()) { return false; } - return (((NTuple) o).elements).equals(elements); + return (((NTuple) o).elements).equals(elements); } public int hashCode() { -- 2.34.1