From 0beb24da229f4717a88b56f5d85947431ca5fcc0 Mon Sep 17 00:00:00 2001 From: yeom Date: Fri, 2 Dec 2011 19:56:03 +0000 Subject: [PATCH] get the right cover set wrt shared location path. working on transfuncs for event loop analysis. --- .../SSJava/DefinitelyWrittenCheck.java | 335 ++++++++++++++---- .../src/Analysis/SSJava/MultiSourceMap.java | 36 +- 2 files changed, 275 insertions(+), 96 deletions(-) diff --git a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java index d14c5e2c..95b917d8 100644 --- a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java +++ b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java @@ -128,9 +128,7 @@ public class DefinitelyWrittenCheck { // it is for setting clearance flag when all read set is overwritten private Hashtable mapMethodDescriptorToReadSummary; - private MultiSourceMap mapLocationPathToMayWrittenSet; - - private Hashtable> mapMethodToSharedWriteMapping; + private Hashtable, NTuple>> mapMethodToSharedLocCoverSet; private Hashtable mapFlatNodeToSharedLocMapping; private Hashtable mapFlatNodeToDeleteSet; @@ -193,21 +191,18 @@ public class DefinitelyWrittenCheck { this.calleeUnionBoundDeleteSet = new SharedLocMap(); this.calleeIntersectBoundSharedSet = new SharedLocMap(); this.mapFlatMethodToSharedLocMap = new Hashtable(); - this.mapLocationPathToMayWrittenSet = new MultiSourceMap(); - this.mapMethodToSharedWriteMapping = - new Hashtable>(); + this.mapMethodToSharedLocCoverSet = + new Hashtable, NTuple>>(); this.mapFlatNodeToDeleteSet = new Hashtable(); } public void definitelyWrittenCheck() { if (!ssjava.getAnnotationRequireSet().isEmpty()) { initialize(); - computeSharedCoverSet(); - - // System.out.println("#"); - // System.out.println(mapLocationPathToMayWrittenSet); methodReadWriteSetAnalysis(); + computeSharedCoverSet(); + sharedLocAnalysis(); eventLoopAnalysis(); @@ -282,6 +277,7 @@ public class DefinitelyWrittenCheck { SharedLocMap deleteSet = new SharedLocMap(); sharedLoc_analyzeBody(state.getMethodFlat(methodContainingSSJavaLoop), ssjavaLoopEntrance, sharedLocMap, deleteSet, true); + } private void sharedLoc_analyzeMethod(FlatMethod fm, SharedLocMap sharedLocMap, @@ -1173,6 +1169,8 @@ public class DefinitelyWrittenCheck { private void computeSharedCoverSet_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) { + System.out.println("computeSharedCoverSet_analyzeMethod=" + fm); + MethodDescriptor md = fm.getMethod(); Set flatNodesToVisit = new HashSet(); @@ -1248,8 +1246,11 @@ public class DefinitelyWrittenCheck { NTuple lhsLocTuple = new NTuple(); lhsLocTuple.addAll(deriveLocationTuple(md, rhs)); - mapLocationPathToMayWrittenSet.put(lhsLocTuple, null, lhs); - addMayWrittenSet(md, lhsLocTuple, lhs); + NTuple lhsHeapPath = computePath(lhs); + System.out.println("flatopnode=" + fn); + System.out.println("lhs heap path=" + computePath(lhs)); + System.out.println("rhs heap path=" + computePath(rhs)); + addMayWrittenSet(md, lhsLocTuple, lhsHeapPath); } @@ -1299,8 +1300,12 @@ public class DefinitelyWrittenCheck { locTuple.addAll(deriveLocationTuple(md, lhs)); locTuple.add(fieldLocation); + NTuple fieldHeapPath = new NTuple(); + fieldHeapPath.addAll(computePath(lhs)); + fieldHeapPath.add(fld); + // mapLocationPathToMayWrittenSet.put(locTuple, null, fld); - addMayWrittenSet(md, locTuple, fld); + addMayWrittenSet(md, locTuple, fieldHeapPath); } @@ -1344,28 +1349,32 @@ public class DefinitelyWrittenCheck { FlatCall fc = (FlatCall) fn; bindLocationPathCallerArgWithCalleeParam(md, fc); + System.out.println("###FLATCALL=" + fc); + System.out.println("###CALLER MAPPING=" + mapMethodToSharedLocCoverSet.get(md)); + } break; } } - private void addMayWrittenSet(MethodDescriptor md, NTuple locTuple, Descriptor d) { + private void addMayWrittenSet(MethodDescriptor md, NTuple locTuple, + NTuple heapPath) { - MultiSourceMap map = mapMethodToSharedWriteMapping.get(md); + MultiSourceMap, NTuple> map = mapMethodToSharedLocCoverSet.get(md); if (map == null) { - map = new MultiSourceMap(); - mapMethodToSharedWriteMapping.put(md, map); + map = new MultiSourceMap, NTuple>(); + mapMethodToSharedLocCoverSet.put(md, map); } - Set writeSet = map.get(locTuple); + Set> writeSet = map.get(locTuple); if (writeSet == null) { - writeSet = new HashSet(); + writeSet = new HashSet>(); map.put(locTuple, writeSet); } - writeSet.add(d); + writeSet.add(heapPath); - // System.out.println("ADD WRITE DESC=" + d + " TO locTuple=" + locTuple); + System.out.println("ADD WRITE heapPath=" + heapPath + " TO locTuple=" + locTuple); } private void bindLocationPathCallerArgWithCalleeParam(MethodDescriptor mdCaller, FlatCall fc) { @@ -1376,9 +1385,7 @@ public class DefinitelyWrittenCheck { TempDescriptor arg = fc.getArg(0); NTuple argLocationPath = deriveLocationTuple(mdCaller, arg); NTuple argHeapPath = computePath(arg); - mapLocationPathToMayWrittenSet.put(argLocationPath, null, - argHeapPath.get(argHeapPath.size() - 1)); - + addMayWrittenSet(mdCaller, argLocationPath, argHeapPath); } else { // if arg is not primitive type, we need to propagate maywritten set to @@ -1389,26 +1396,45 @@ public class DefinitelyWrittenCheck { setPossibleCallees.addAll(callGraph.getMethods(mdCallee)); // create mapping from arg idx to its heap paths - Hashtable> mapArgIdx2CallerAgLocationStrPath = + Hashtable> mapArgIdx2CallerArgHeapPath = + new Hashtable>(); + + // create mapping from arg idx to its location paths + Hashtable> mapArgIdx2CallerArgLocationPath = new Hashtable>(); // arg idx is starting from 'this' arg if (fc.getThis() != null) { + // loc path for 'this' NTuple thisLocationPath = deriveLocationTuple(mdCaller, fc.getThis()); - mapArgIdx2CallerAgLocationStrPath.put(Integer.valueOf(0), thisLocationPath); - } - - Hashtable> mapParamIdx2WriteSet = - new Hashtable>(); + mapArgIdx2CallerArgLocationPath.put(Integer.valueOf(0), thisLocationPath); - for (int i = 0; i < fc.numArgs() + 1; i++) { - mapParamIdx2WriteSet.put(Integer.valueOf(i), new HashSet()); + // heap path for 'this' + 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); + // create mapping arg to loc path NTuple argLocationPath = deriveLocationTuple(mdCaller, arg); - mapArgIdx2CallerAgLocationStrPath.put(Integer.valueOf(i + 1), argLocationPath); + mapArgIdx2CallerArgLocationPath.put(Integer.valueOf(i + 1), argLocationPath); + + // create mapping arg to heap path + NTuple argHeapPath = computePath(arg); + mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath); + } + + Hashtable>> mapParamIdx2WriteSet = + new Hashtable>>(); + + for (int i = 0; i < fc.numArgs() + 1; i++) { + mapParamIdx2WriteSet.put(Integer.valueOf(i), new HashSet>()); } for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) { @@ -1429,21 +1455,19 @@ public class DefinitelyWrittenCheck { mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param); } - Set keySet = mapArgIdx2CallerAgLocationStrPath.keySet(); + Set keySet = mapArgIdx2CallerArgLocationPath.keySet(); for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { Integer idx = (Integer) iterator2.next(); - NTuple callerArgLocationStrPath = mapArgIdx2CallerAgLocationStrPath.get(idx); + NTuple callerArgLocationPath = mapArgIdx2CallerArgLocationPath.get(idx); TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx); + + NTuple callerArgHeapPath = mapArgIdx2CallerArgHeapPath.get(idx); NTuple calleeLocationPath = deriveLocationTuple(mdCallee, calleeParam); + NTuple calleeHeapPath = computePath(calleeParam); - // System.out.println("#createNewMappingOfMayWrittenSet callee=" + - // callee - // + " callerArgLocationStrPath=" + callerArgLocationStrPath + - // "calleeLocationPath=" - // + calleeLocationPath + " idx=" + idx + " writeset=" + - // mapParamIdx2WriteSet.get(idx)); - createNewMappingOfMayWrittenSet(callee, callerArgLocationStrPath, calleeLocationPath, + createNewMappingOfMayWrittenSet(mdCaller, callee, callerArgHeapPath, + callerArgLocationPath, calleeHeapPath, calleeLocationPath, mapParamIdx2WriteSet.get(idx)); } @@ -1454,8 +1478,29 @@ public class DefinitelyWrittenCheck { } - private void createNewMappingOfMayWrittenSet(MethodDescriptor callee, - NTuple callerPath, NTuple calleeParamPath, Set writeSet) { + public Hashtable, Set>> getMappingByStartedWith( + MultiSourceMap, NTuple> map, NTuple in) { + + Hashtable, Set>> matchedMapping = + new Hashtable, Set>>(); + + Set> keySet = map.keySet(); + + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + NTuple key = (NTuple) iterator.next(); + if (key.startsWith(in)) { + matchedMapping.put(key, map.get(key)); + } + } + + return matchedMapping; + + } + + private void createNewMappingOfMayWrittenSet(MethodDescriptor caller, MethodDescriptor callee, + NTuple callerArgHeapPath, NTuple callerArgLocPath, + NTuple calleeParamHeapPath, NTuple calleeParamLocPath, + Set> writeSet) { // propagate may-written-set associated with the key that is started with // calleepath to the caller @@ -1464,38 +1509,72 @@ public class DefinitelyWrittenCheck { // 2) create new mapping of may-written-set of callee path to caller path // extract all may written effect accessed through callee param path - MultiSourceMap mapping = mapMethodToSharedWriteMapping.get(callee); + MultiSourceMap, NTuple> calleeMapping = + mapMethodToSharedLocCoverSet.get(callee); - if (mapping == null) { + MultiSourceMap, NTuple> callerMapping = + mapMethodToSharedLocCoverSet.get(caller); + + if (calleeMapping == null) { return; } - Hashtable, Set> paramMapping = - mapping.getMappingByStartedWith(calleeParamPath); + Hashtable, Set>> paramMapping = + getMappingByStartedWith(calleeMapping, calleeParamLocPath); - Set> calleeKeySet = mapping.keySet(); + Set> calleeKeySet = calleeMapping.keySet(); for (Iterator iterator = calleeKeySet.iterator(); iterator.hasNext();) { NTuple calleeKey = (NTuple) iterator.next(); - Set calleeMayWriteSet = paramMapping.get(calleeKey); + Set> calleeMayWriteSet = paramMapping.get(calleeKey); if (calleeMayWriteSet != null) { - writeSet.addAll(calleeMayWriteSet); + + Set> boundWriteSet = + convertCallerMayWriteSet(callerArgHeapPath, calleeParamHeapPath, calleeMayWriteSet); + + writeSet.addAll(boundWriteSet); NTuple newKey = new NTuple(); - newKey.addAll(callerPath); + newKey.addAll(callerArgLocPath); // 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)); } - mapLocationPathToMayWrittenSet.put(calleeKey, newKey, writeSet); + callerMapping.union(newKey, writeSet); + // mapLocationPathToMayWrittenSet.put(calleeKey, newKey, writeSet); } } } + private Set> convertCallerMayWriteSet(NTuple callerArgHeapPath, + NTuple calleeParamHeapPath, Set> calleeMayWriteSet) { + + Set> boundSet = new HashSet>(); + + // replace callee's param path with caller's arg path + for (Iterator iterator = calleeMayWriteSet.iterator(); iterator.hasNext();) { + NTuple calleeWriteHeapPath = (NTuple) iterator.next(); + + NTuple boundHeapPath = new NTuple(); + boundHeapPath.addAll(callerArgHeapPath); + + int startIdx = calleeParamHeapPath.size(); + + for (int i = startIdx; i < calleeWriteHeapPath.size(); i++) { + boundHeapPath.add(calleeWriteHeapPath.get(i)); + } + + boundSet.add(boundHeapPath); + + } + + return boundSet; + } + private void addSharedLocDescriptor(Location sharedLoc, Descriptor desc) { Set descSet = mapSharedLocationToCoverSet.get(sharedLoc); @@ -1707,25 +1786,46 @@ public class DefinitelyWrittenCheck { lhs = fon.getDest(); rhs = fon.getLeft(); - if (!lhs.getSymbol().startsWith("neverused")) { - NTuple rhsHeapPath = computePath(rhs); - if (!rhs.getType().isImmutable()) { - mapHeapPath.put(lhs, rhsHeapPath); - } else { - // write(lhs) - // NTuple lhsHeapPath = computePath(lhs); - NTuple path = new NTuple(); - path.add(lhs); + if (fon.getOp().getOp() == Operation.ASSIGN) { - // System.out.println("WRITE VARIABLE=" + path + " from=" + lhs); + if (!lhs.getSymbol().startsWith("neverused")) { + NTuple rhsHeapPath = computePath(rhs); + if (!rhs.getType().isImmutable()) { + mapHeapPath.put(lhs, rhsHeapPath); + } else { + // write(lhs) + // NTuple lhsHeapPath = computePath(lhs); + NTuple path = new NTuple(); + path.add(lhs); + + System.out.println("#VARIABLE WRITE:" + fn); + + Location lhsLoc = getLocation(lhs); + if (ssjava.isSharedLocation(lhsLoc)) { + + NTuple varHeapPath = computePath(lhs); + NTuple varLocTuple = mapDescriptorToLocationPath.get(lhs); + + Set> writtenSet = + mapFlatNodeToSharedLocMapping.get(fn).get(varLocTuple); + + if (isCovered(varLocTuple, writtenSet)) { + System.out.println("writttenSet is fully covered"); + computeKILLSetForSharedWrite(curr, writtenSet, readWriteKillSet); + computeGENSetForSharedAllCoverWrite(curr, writtenSet, readWriteGenSet); + } else { + computeGENSetForSharedNonCoverWrite(curr, varHeapPath, readWriteGenSet); + } + } else { - computeKILLSetForWrite(curr, path, readWriteKillSet); - computeGENSetForWrite(path, readWriteGenSet); + computeKILLSetForWrite(curr, path, readWriteKillSet); + computeGENSetForWrite(path, readWriteGenSet); + } - // System.out.println("#VARIABLE WRITE:" + fn); - // System.out.println("#KILLSET=" + KILLSet); - // System.out.println("#GENSet=" + GENSet); + System.out.println("#KILLSET=" + readWriteKillSet); + System.out.println("#GENSet=" + readWriteGenSet); + } } } @@ -1781,17 +1881,39 @@ public class DefinitelyWrittenCheck { fld = getArrayField(td); } + System.out.println("FIELD WRITE:" + fn); + // write(field) NTuple lhsHeapPath = computePath(lhs); NTuple fldHeapPath = new NTuple(lhsHeapPath.getList()); fldHeapPath.add(fld); - computeKILLSetForWrite(curr, fldHeapPath, readWriteKillSet); - computeGENSetForWrite(fldHeapPath, readWriteGenSet); + // shared loc extension + Location fieldLoc = (Location) fld.getType().getExtension(); + if (ssjava.isSharedLocation(fieldLoc)) { + + NTuple fieldLocTuple = new NTuple(); + fieldLocTuple.addAll(mapDescriptorToLocationPath.get(lhs)); + fieldLocTuple.add(fieldLoc); - // System.out.println("FIELD WRITE:" + fn); - // System.out.println("KILLSET=" + KILLSet); - // System.out.println("GENSet=" + GENSet); + Set> writtenSet = + mapFlatNodeToSharedLocMapping.get(fn).get(fieldLocTuple); + + if (isCovered(fieldLocTuple, writtenSet)) { + System.out.println("writttenSet is fully covered"); + computeKILLSetForSharedWrite(curr, writtenSet, readWriteKillSet); + computeGENSetForSharedAllCoverWrite(curr, writtenSet, readWriteGenSet); + } else { + computeGENSetForSharedNonCoverWrite(curr, fldHeapPath, readWriteGenSet); + } + + } else { + computeKILLSetForWrite(curr, fldHeapPath, readWriteKillSet); + computeGENSetForWrite(fldHeapPath, readWriteGenSet); + } + + System.out.println("KILLSET=" + readWriteKillSet); + System.out.println("GENSet=" + readWriteGenSet); } break; @@ -1821,6 +1943,64 @@ public class DefinitelyWrittenCheck { } + private void computeGENSetForSharedNonCoverWrite( + Hashtable, Set> curr, NTuple heapPath, + Hashtable, Set> genSet) { + + Set writeAgeSet = genSet.get(heapPath); + if (writeAgeSet == null) { + writeAgeSet = new HashSet(); + genSet.put(heapPath, writeAgeSet); + } + + writeAgeSet.add(new WriteAge(1)); + + } + + private void computeGENSetForSharedAllCoverWrite( + Hashtable, Set> curr, Set> writtenSet, + Hashtable, Set> genSet) { + + for (Iterator iterator = writtenSet.iterator(); iterator.hasNext();) { + NTuple writeHeapPath = (NTuple) iterator.next(); + + Set writeAgeSet = new HashSet(); + writeAgeSet.add(new WriteAge(0)); + + genSet.put(writeHeapPath, writeAgeSet); + } + + } + + private void computeKILLSetForSharedWrite(Hashtable, Set> curr, + Set> writtenSet, Hashtable, Set> killSet) { + + for (Iterator iterator = writtenSet.iterator(); iterator.hasNext();) { + NTuple writeHeapPath = (NTuple) iterator.next(); + Set writeSet = curr.get(writeHeapPath); + if (writeSet != null) { + killSet.put(writeHeapPath, writeSet); + } + } + + } + + private boolean isCovered(NTuple locTuple, Set> inSet) { + + if (inSet == null) { + return false; + } + + Set> coverSet = + mapMethodToSharedLocCoverSet.get(methodContainingSSJavaLoop).get(locTuple); + + System.out.println("# locTuple=" + locTuple); + System.out.print("Current may write Set=" + inSet); + System.out.println("Cover Set=" + coverSet); + + return inSet.containsAll(coverSet); + } + private void checkManyRead(FlatCall fc, Hashtable, Set> curr) { Set> boundReadSet = mapFlatNodeToBoundReadSet.get(fc); @@ -2468,12 +2648,18 @@ public class DefinitelyWrittenCheck { FlatOpNode fon = (FlatOpNode) fn; // for a normal assign node, need to propagate lhs's heap path to // rhs + if (fon.getOp().getOp() == Operation.ASSIGN) { rhs = fon.getLeft(); lhs = fon.getDest(); NTuple rhsHeapPath = mapHeapPath.get(rhs); - if (rhsHeapPath != null) { + + if (lhs.getType().isPrimitive()) { + NTuple lhsHeapPath = new NTuple(); + lhsHeapPath.add(lhs); + mapHeapPath.put(lhs, lhsHeapPath); + } else if (rhsHeapPath != null) { mapHeapPath.put(lhs, mapHeapPath.get(rhs)); } else { NTuple heapPath = new NTuple(); @@ -2507,7 +2693,6 @@ public class DefinitelyWrittenCheck { System.out.println("RHS TYPE EXTENSION=" + rhs.getType().getExtension() + " HEAPPATH=" + rhsHeapPath); - // TODO // computing gen/kill set // computeKILLSetForWrite(currSharedLocMapping, heapPath, dstLoc, // killSetSharedLoc); diff --git a/Robust/src/Analysis/SSJava/MultiSourceMap.java b/Robust/src/Analysis/SSJava/MultiSourceMap.java index 1dc22ec7..b8fd0ef2 100644 --- a/Robust/src/Analysis/SSJava/MultiSourceMap.java +++ b/Robust/src/Analysis/SSJava/MultiSourceMap.java @@ -2,22 +2,21 @@ 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; + Hashtable> map; public MultiSourceMap() { - map = new Hashtable, Set>(); + map = new Hashtable>(); } - public void put(NTuple key, Set set) { + public void put(T key, Set set) { map.put(key, set); } - public void put(NTuple key, NTuple setKey, Set set) { + public void put(T key, T setKey, Set set) { if (!map.containsKey(setKey)) { map.put(setKey, set); @@ -25,7 +24,7 @@ public class MultiSourceMap { map.put(key, set); } - public void put(NTuple key, NTuple setKey, V value) { + public void put(T key, T setKey, V value) { if (setKey == null) { if (map.containsKey(key)) { @@ -45,7 +44,7 @@ public class MultiSourceMap { } } - public Set get(NTuple key) { + public Set get(T key) { return map.get(key); } @@ -53,23 +52,18 @@ public class MultiSourceMap { 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)); - } - } + public Set keySet() { + return map.keySet(); + } - return rtrMapping; + public void union(T newKey, Set writeSet) { - } + if (map.containsKey(newKey)) { + map.get(newKey).addAll(writeSet); + } else { + put(newKey, writeSet); + } - public Set> keySet() { - return map.keySet(); } } -- 2.34.1