X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FDefinitelyWrittenCheck.java;h=fabdf9dbbdbe09f2fb0f0f7c7c9b9618d53be0de;hp=480957ad642b7e07503b9dda92b3545d67b25aa1;hb=d45bb251bdc1196d7848094fa2ccd566b39e021c;hpb=bdc086e2ec7fcc674a604906627b52e16fba7eb3 diff --git a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java index 480957ad..fabdf9db 100644 --- a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java +++ b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java @@ -1,404 +1,2653 @@ package Analysis.SSJava; +import java.util.Enumeration; import java.util.HashSet; import java.util.Hashtable; import java.util.Iterator; +import java.util.LinkedList; import java.util.Set; +import java.util.Stack; +import Analysis.Liveness; +import Analysis.CallGraph.CallGraph; import Analysis.Loops.LoopFinder; -import Analysis.Loops.Loops; -import IR.ClassDescriptor; import IR.Descriptor; import IR.FieldDescriptor; import IR.MethodDescriptor; import IR.Operation; import IR.State; -import IR.SymbolTable; -import IR.VarDescriptor; +import IR.TypeDescriptor; +import IR.TypeExtension; import IR.Flat.FKind; +import IR.Flat.FlatCall; +import IR.Flat.FlatElementNode; import IR.Flat.FlatFieldNode; import IR.Flat.FlatLiteralNode; import IR.Flat.FlatMethod; +import IR.Flat.FlatNew; import IR.Flat.FlatNode; import IR.Flat.FlatOpNode; +import IR.Flat.FlatSetElementNode; import IR.Flat.FlatSetFieldNode; import IR.Flat.TempDescriptor; +import IR.Tree.Modifiers; public class DefinitelyWrittenCheck { - static State state; - HashSet toanalyze; + SSJavaAnalysis ssjava; + State state; + CallGraph callGraph; - private Hashtable>> definitelyWrittenResults; + Liveness liveness; - public DefinitelyWrittenCheck(State state) { + int debugcount = 0; + + // maps a flat node to its WrittenSet: this keeps all heap path overwritten + // previously. + private Hashtable>> mapFlatNodeToMustWriteSet; + + // maps a temp descriptor to its heap path + // each temp descriptor has a unique heap path since we do not allow any + // alias. + private Hashtable> mapHeapPath; + + // maps a temp descriptor to its composite location + private Hashtable> mapDescriptorToLocationPath; + + // maps a flat method to the READ that is the set of heap path that is + // expected to be written before method invocation + private Hashtable>> mapFlatMethodToReadSet; + + // maps a flat method to the must-write set that is the set of heap path that + // is overwritten on every possible path during method invocation + private Hashtable>> mapFlatMethodToMustWriteSet; + + // maps a flat method to the DELETE SET that is a set of heap path to shared + // locations that are + // written to but not overwritten by the higher value + private Hashtable mapFlatMethodToDeleteSet; + + private Hashtable mapFlatMethodToMustClearMap; + + // maps a flat method to the S SET that is a set of heap path to shared + // locations that are overwritten by the higher value + private Hashtable mapFlatMethodToSharedLocMap; + + // maps a flat method to the may-wirte set that is the set of heap path that + // might be written to + private Hashtable>> mapFlatMethodToMayWriteSet; + + // maps a call site to the read set contributed by all callees + private Hashtable>> mapFlatNodeToBoundReadSet; + + // maps a call site to the must write set contributed by all callees + private Hashtable>> mapFlatNodeToBoundMustWriteSet; + + // maps a call site to the may read set contributed by all callees + private Hashtable>> mapFlatNodeToBoundMayWriteSet; + + // points to method containing SSJAVA Loop + private MethodDescriptor methodContainingSSJavaLoop; + + // maps a flatnode to definitely written analysis mapping M + private Hashtable, Set>> mapFlatNodetoEventLoopMap; + + // maps shared location to the set of descriptors which belong to the shared + // location + + // 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 possibleCalleeReadSummarySetToCaller; + + public static final String arrayElementFieldName = "___element_"; + static protected Hashtable mapTypeToArrayField; + + // maps a method descriptor to the merged incoming caller's current + // reading status + // it is for setting clearance flag when all read set is overwritten + private Hashtable mapMethodDescriptorToReadSummary; + + private Hashtable, NTuple>> mapMethodToSharedLocCoverSet; + + private Hashtable mapFlatNodeToSharedLocMapping; + private Hashtable mapFlatNodeToDeleteSet; + private Hashtable mapFlatNodeToMustClearMap; + + private LoopFinder ssjavaLoop; + private Set loopIncElements; + + private Set> calleeUnionBoundReadSet; + private Set> calleeIntersectBoundMustWriteSet; + private Set> calleeUnionBoundMayWriteSet; + private SharedLocMap calleeUnionBoundDeleteSet; + private SharedLocMap calleeIntersectBoundSharedSet; + private SharedLocMap calleeIntersectBoundMustClearSet; + + Set liveInTempSetToEventLoop; + + private Hashtable mapDescToLocation; + + private TempDescriptor LOCAL; + + public static int MAXAGE = 1; + + public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) { this.state = state; - this.toanalyze = new HashSet(); - this.definitelyWrittenResults = - new Hashtable>>(); + this.ssjava = ssjava; + this.callGraph = ssjava.getCallGraph(); + this.mapFlatNodeToMustWriteSet = new Hashtable>>(); + this.mapHeapPath = new Hashtable>(); + this.mapDescriptorToLocationPath = new Hashtable>(); + this.mapFlatMethodToReadSet = new Hashtable>>(); + this.mapFlatMethodToMustWriteSet = new Hashtable>>(); + this.mapFlatMethodToMayWriteSet = new Hashtable>>(); + this.mapFlatNodetoEventLoopMap = + new Hashtable, Set>>(); + this.calleeUnionBoundReadSet = new HashSet>(); + this.calleeIntersectBoundMustWriteSet = new HashSet>(); + this.calleeUnionBoundMayWriteSet = new HashSet>(); + + this.methodDescriptorsToVisitStack = new Stack(); + this.calleesToEnqueue = new HashSet(); + this.mapTypeToArrayField = new Hashtable(); + this.LOCAL = new TempDescriptor("LOCAL"); + this.mapDescToLocation = new Hashtable(); + this.possibleCalleeReadSummarySetToCaller = new HashSet(); + this.mapMethodDescriptorToReadSummary = new Hashtable(); + this.mapFlatNodeToBoundReadSet = new Hashtable>>(); + this.mapFlatNodeToBoundMustWriteSet = new Hashtable>>(); + this.mapFlatNodeToBoundMayWriteSet = new Hashtable>>(); + this.mapFlatNodeToSharedLocMapping = new Hashtable(); + this.mapFlatMethodToDeleteSet = new Hashtable(); + this.calleeUnionBoundDeleteSet = new SharedLocMap(); + this.calleeIntersectBoundSharedSet = new SharedLocMap(); + this.mapFlatMethodToSharedLocMap = new Hashtable(); + this.mapMethodToSharedLocCoverSet = + new Hashtable, NTuple>>(); + this.mapFlatNodeToDeleteSet = new Hashtable(); + this.liveness = new Liveness(); + this.liveInTempSetToEventLoop = new HashSet(); + this.mapFlatNodeToMustClearMap = new Hashtable(); + this.calleeIntersectBoundMustClearSet = new SharedLocMap(); + this.mapFlatMethodToMustClearMap = new Hashtable(); + } + + public void definitelyWrittenCheck() { + if (!ssjava.getAnnotationRequireSet().isEmpty()) { + initialize(); + + methodReadWriteSetAnalysis(); + computeSharedCoverSet(); + + sharedLocAnalysis(); + + eventLoopAnalysis(); + + } + } + + private void sharedLocAnalysis() { + + // perform method READ/OVERWRITE analysis + LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + + // current descriptors to visit in fixed-point interprocedural analysis, + // prioritized by + // dependency in the call graph + methodDescriptorsToVisitStack.clear(); + + descriptorListToAnalyze.removeFirst(); + + Set methodDescriptorToVistSet = new HashSet(); + methodDescriptorToVistSet.addAll(descriptorListToAnalyze); + + while (!descriptorListToAnalyze.isEmpty()) { + MethodDescriptor md = descriptorListToAnalyze.removeFirst(); + methodDescriptorsToVisitStack.add(md); + } + + // analyze scheduled methods until there are no more to visit + while (!methodDescriptorsToVisitStack.isEmpty()) { + // start to analyze leaf node + MethodDescriptor md = methodDescriptorsToVisitStack.pop(); + FlatMethod fm = state.getMethodFlat(md); + + SharedLocMap sharedLocMap = new SharedLocMap(); + SharedLocMap deleteSet = new SharedLocMap(); + SharedLocMap mustClearMap = new SharedLocMap(); + + sharedLoc_analyzeMethod(fm, sharedLocMap, deleteSet, mustClearMap); + SharedLocMap prevSharedLocMap = mapFlatMethodToSharedLocMap.get(fm); + SharedLocMap prevDeleteSet = mapFlatMethodToDeleteSet.get(fm); + SharedLocMap prevMustClearMap = mapFlatMethodToMustClearMap.get(fm); + + if (!(deleteSet.equals(prevDeleteSet) && sharedLocMap.equals(prevSharedLocMap) && mustClearMap + .equals(prevMustClearMap))) { + mapFlatMethodToSharedLocMap.put(fm, sharedLocMap); + mapFlatMethodToDeleteSet.put(fm, deleteSet); + mapFlatMethodToMustClearMap.put(fm, mustClearMap); + + // results for callee changed, so enqueue dependents caller for + // further + // analysis + Iterator depsItr = ssjava.getDependents(md).iterator(); + while (depsItr.hasNext()) { + MethodDescriptor methodNext = depsItr.next(); + if (!methodDescriptorsToVisitStack.contains(methodNext) + && methodDescriptorToVistSet.contains(methodNext)) { + methodDescriptorsToVisitStack.add(methodNext); + } + + } + + } + + } + + sharedLoc_analyzeEventLoop(); + + } + + private void sharedLoc_analyzeEventLoop() { + if (state.SSJAVADEBUG) { + System.out.println("SSJAVA: Definite clearance for shared locations Analyzing: eventloop"); + } + SharedLocMap sharedLocMap = new SharedLocMap(); + SharedLocMap deleteSet = new SharedLocMap(); + SharedLocMap mustClearMap = new SharedLocMap(); + sharedLoc_analyzeBody(state.getMethodFlat(methodContainingSSJavaLoop), + ssjava.getSSJavaLoopEntrance(), sharedLocMap, deleteSet, mustClearMap, true); + + } + + private void sharedLoc_analyzeMethod(FlatMethod fm, SharedLocMap sharedLocMap, + SharedLocMap deleteSet, SharedLocMap mustClearMap) { + if (state.SSJAVADEBUG) { + System.out.println("SSJAVA: Definite clearance for shared locations Analyzing: " + fm); + } + + sharedLoc_analyzeBody(fm, fm, sharedLocMap, deleteSet, mustClearMap, false); + + } + + private void sharedLoc_analyzeBody(FlatMethod fm, FlatNode startNode, SharedLocMap sharedLocMap, + SharedLocMap deleteSet, SharedLocMap mustClearMap, boolean isEventLoopBody) { + + // intraprocedural analysis + Set flatNodesToVisit = new HashSet(); + flatNodesToVisit.add(startNode); + + while (!flatNodesToVisit.isEmpty()) { + FlatNode fn = flatNodesToVisit.iterator().next(); + flatNodesToVisit.remove(fn); + + SharedLocMap currSharedSet = new SharedLocMap(); + SharedLocMap currDeleteSet = new SharedLocMap(); + SharedLocMap currMustClearMap = new SharedLocMap(); + + for (int i = 0; i < fn.numPrev(); i++) { + FlatNode prevFn = fn.getPrev(i); + SharedLocMap inSharedLoc = mapFlatNodeToSharedLocMapping.get(prevFn); + if (inSharedLoc != null) { + mergeSharedLocMap(currSharedSet, inSharedLoc); + } + + SharedLocMap inDeleteLoc = mapFlatNodeToDeleteSet.get(prevFn); + if (inDeleteLoc != null) { + mergeDeleteSet(currDeleteSet, inDeleteLoc); + } + + SharedLocMap inMustClearMap = mapFlatNodeToMustClearMap.get(prevFn); + if (inMustClearMap != null) { + mergeSharedLocMap(currMustClearMap, inMustClearMap); + } + + } + + sharedLoc_nodeActions(fm, fn, currSharedSet, currDeleteSet, currMustClearMap, sharedLocMap, + deleteSet, mustClearMap, isEventLoopBody); + + SharedLocMap prevSharedSet = mapFlatNodeToSharedLocMapping.get(fn); + SharedLocMap prevDeleteSet = mapFlatNodeToDeleteSet.get(fn); + SharedLocMap prevMustClearMap = mapFlatNodeToMustClearMap.get(fn); + + if (!(currSharedSet.equals(prevSharedSet) && currDeleteSet.equals(prevDeleteSet) && currMustClearMap + .equals(prevMustClearMap))) { + mapFlatNodeToSharedLocMapping.put(fn, currSharedSet); + mapFlatNodeToDeleteSet.put(fn, currDeleteSet); + mapFlatNodeToMustClearMap.put(fn, currMustClearMap); + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + if ((!isEventLoopBody) || loopIncElements.contains(nn)) { + flatNodesToVisit.add(nn); + } + + } + } + + } + + } + + private void sharedLoc_nodeActions(FlatMethod fm, FlatNode fn, SharedLocMap curr, + SharedLocMap currDeleteSet, SharedLocMap currMustClearMap, SharedLocMap sharedLocMap, + SharedLocMap deleteSet, SharedLocMap mustClearMap, boolean isEventLoopBody) { + + MethodDescriptor md = fm.getMethod(); + + SharedLocMap killSet = new SharedLocMap(); + SharedLocMap genSet = new SharedLocMap(); + + TempDescriptor lhs; + TempDescriptor rhs; + FieldDescriptor fld; + + NTuple fieldLocTuple = null; + Location fieldLoc = null; + boolean isHigherWriteCase = false; + + switch (fn.kind()) { + + case FKind.FlatOpNode: { + + if (isEventLoopBody) { + FlatOpNode fon = (FlatOpNode) fn; + + if (fon.getOp().getOp() == Operation.ASSIGN) { + lhs = fon.getDest(); + rhs = fon.getLeft(); + + if (!lhs.getSymbol().startsWith("neverused") && !lhs.getSymbol().startsWith("leftop") + && !lhs.getSymbol().startsWith("rightop") && rhs.getType().isImmutable()) { + + if (mapHeapPath.containsKey(rhs)) { + Location dstLoc = getLocation(lhs); + if (dstLoc != null && ssjava.isSharedLocation(dstLoc)) { + NTuple lhsHeapPath = computePath(lhs); + NTuple lhsLocTuple = mapDescriptorToLocationPath.get(lhs); + + Location srcLoc = getLocation(lhs); + + // computing gen/kill set + computeKILLSetForWrite(curr, killSet, lhsLocTuple, lhsHeapPath); + + if (!ssjava.isSameHeightWrite(fn)) { + computeGENSetForHigherWrite(curr, killSet, lhsLocTuple, lhsHeapPath); + updateDeleteSetForHigherWrite(currDeleteSet, lhsLocTuple, lhsHeapPath); + } else { + computeGENSetForSameHeightWrite(curr, killSet, lhsLocTuple, lhsHeapPath); + updateDeleteSetForSameHeightWrite(currDeleteSet, lhsLocTuple, lhsHeapPath); + } + + } + } else { + break; + } + + } + + } + + } + + } + break; + + case FKind.FlatSetFieldNode: + case FKind.FlatSetElementNode: { + + if (fn.kind() == FKind.FlatSetFieldNode) { + FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; + lhs = fsfn.getDst(); + fld = fsfn.getField(); + rhs = fsfn.getSrc(); + fieldLoc = (Location) fld.getType().getExtension(); + } else { + break; + } + + if (!isEventLoopBody && fieldLoc.getDescriptor().equals(md)) { + // if the field belongs to the local lattice, no reason to calculate + // shared location + break; + } + + fieldLocTuple = new NTuple(); + if (fld.isStatic()) { + if (fld.isFinal()) { + // in this case, fld has TOP location + Location topLocation = Location.createTopLocation(md); + fieldLocTuple.add(topLocation); + } else { + fieldLocTuple.addAll(deriveGlobalLocationTuple(md)); + if (fn.kind() == FKind.FlatSetFieldNode) { + fieldLocTuple.add((Location) fld.getType().getExtension()); + } + } + + } else { + fieldLocTuple.addAll(deriveLocationTuple(md, lhs)); + if (fn.kind() == FKind.FlatSetFieldNode) { + fieldLocTuple.add((Location) fld.getType().getExtension()); + } + } + + // shared loc extension + Location srcLoc = getLocation(rhs); + if (ssjava.isSharedLocation(fieldLoc)) { + // only care the case that loc(f) is shared location + // write(field) + + // NTuple fieldLocTuple = new NTuple(); + // fieldLocTuple.addAll(mapDescriptorToLocationPath.get(lhs)); + // fieldLocTuple.add(fieldLoc); + + NTuple fldHeapPath = new NTuple(); + fldHeapPath.addAll(computePath(lhs)); + if (fn.kind() == FKind.FlatSetFieldNode) { + fldHeapPath.add(fld); + } + + // computing gen/kill set + computeKILLSetForWrite(curr, killSet, fieldLocTuple, fldHeapPath); + + if (!ssjava.isSameHeightWrite(fn)) { + computeGENSetForHigherWrite(curr, genSet, fieldLocTuple, fldHeapPath); + updateDeleteSetForHigherWrite(currDeleteSet, fieldLocTuple, fldHeapPath); + + isHigherWriteCase = true; + + } else { + computeGENSetForSameHeightWrite(curr, genSet, fieldLocTuple, fldHeapPath); + updateDeleteSetForSameHeightWrite(currDeleteSet, fieldLocTuple, fldHeapPath); + } + + } + + } + break; + + case FKind.FlatCall: { + FlatCall fc = (FlatCall) fn; + + bindHeapPathCallerArgWithCaleeParamForSharedLoc(fm.getMethod(), fc); + + // computing gen/kill set + generateKILLSetForFlatCall(curr, killSet); + generateGENSetForFlatCall(curr, genSet); + + Set> locTupleSet = calleeIntersectBoundMustClearSet.keySet(); + for (Iterator iterator = locTupleSet.iterator(); iterator.hasNext();) { + NTuple locTupleKey = (NTuple) iterator.next(); + currMustClearMap.addWrite(locTupleKey, calleeIntersectBoundMustClearSet.get(locTupleKey)); + } + + } + break; + + case FKind.FlatExit: { + // merge the current delete/shared loc mapping + mergeSharedLocMap(sharedLocMap, curr); + mergeDeleteSet(deleteSet, currDeleteSet); + mergeSharedLocMap(mustClearMap, currMustClearMap); + } + break; + + } + + computeNewMapping(curr, killSet, genSet); + if (isHigherWriteCase) { + // check all locations with the same shared location are cleared out at this point + Set> writtenSet = curr.get(fieldLocTuple); + Set requirementSet = ssjava.getSharedDescSet(fieldLoc); + + if (checkAllSharedLocationsAreOverwritten(requirementSet, writtenSet)) { + currMustClearMap.addWrite(fieldLocTuple, writtenSet); + } + } + } + + private boolean checkAllSharedLocationsAreOverwritten(Set sharedDescSet, + Set> writtenSet) { + + if (sharedDescSet == null || writtenSet == null) { + return false; + } + Set writtenDescSet = new HashSet(); + for (Iterator iterator = writtenSet.iterator(); iterator.hasNext();) { + NTuple tuple = (NTuple) iterator.next(); + writtenDescSet.add(tuple.get(tuple.size() - 1)); + } + + return writtenDescSet.containsAll(sharedDescSet); + // return sharedDescSet.containsAll(writtenDescSet); + + } + + private void generateGENSetForFlatCall(SharedLocMap curr, SharedLocMap genSet) { + + Set> locTupleSet = calleeIntersectBoundSharedSet.keySet(); + for (Iterator iterator = locTupleSet.iterator(); iterator.hasNext();) { + NTuple locTupleKey = (NTuple) iterator.next(); + genSet.addWrite(locTupleKey, curr.get(locTupleKey)); + genSet.addWrite(locTupleKey, calleeIntersectBoundSharedSet.get(locTupleKey)); + + genSet.removeWriteAll(locTupleKey, calleeUnionBoundDeleteSet.get(locTupleKey)); + } + + } + + private void generateKILLSetForFlatCall(SharedLocMap curr, SharedLocMap killSet) { + + Set> locTupleSet = calleeIntersectBoundSharedSet.keySet(); + for (Iterator iterator = locTupleSet.iterator(); iterator.hasNext();) { + NTuple locTupleKey = (NTuple) iterator.next(); + killSet.addWrite(locTupleKey, curr.get(locTupleKey)); + } + + } + + private void mergeDeleteSet(SharedLocMap currDeleteSet, SharedLocMap inDeleteLoc) { + + Set> locTupleKeySet = inDeleteLoc.keySet(); + + for (Iterator iterator = locTupleKeySet.iterator(); iterator.hasNext();) { + NTuple locTupleKey = (NTuple) iterator.next(); + + Set> inSet = inDeleteLoc.get(locTupleKey); + currDeleteSet.addWrite(locTupleKey, inSet); + + } + } + + private void computeNewMapping(SharedLocMap curr, SharedLocMap killSet, SharedLocMap genSet) { + curr.kill(killSet); + curr.gen(genSet); + } + + private void updateDeleteSetForHigherWrite(SharedLocMap currDeleteSet, NTuple locTuple, + NTuple hp) { + currDeleteSet.removeWrite(locTuple, hp); + } + + private void updateDeleteSetForSameHeightWrite(SharedLocMap currDeleteSet, + NTuple locTuple, NTuple hp) { + currDeleteSet.addWrite(locTuple, hp); + } + + private void computeGENSetForHigherWrite(SharedLocMap curr, SharedLocMap genSet, + NTuple locTuple, NTuple hp) { + Set> currWriteSet = curr.get(locTuple); + + if (currWriteSet != null) { + genSet.addWrite(locTuple, currWriteSet); + } + genSet.addWrite(locTuple, hp); + } + + private void computeGENSetForSameHeightWrite(SharedLocMap curr, SharedLocMap genSet, + NTuple locTuple, NTuple hp) { + Set> currWriteSet = curr.get(locTuple); + + if (currWriteSet != null) { + genSet.addWrite(locTuple, currWriteSet); + } + genSet.removeWrite(locTuple, hp); + } + + private void computeKILLSetForWrite(SharedLocMap curr, SharedLocMap killSet, + NTuple locTuple, NTuple hp) { + + Set> writeSet = curr.get(locTuple); + if (writeSet != null) { + killSet.addWrite(locTuple, writeSet); + } + + } + + private void mergeSharedLocMap(SharedLocMap currSharedSet, SharedLocMap in) { + + Set> locTupleKeySet = in.keySet(); + for (Iterator iterator = locTupleKeySet.iterator(); iterator.hasNext();) { + NTuple locTupleKey = (NTuple) iterator.next(); + + Set> inSet = in.get(locTupleKey); + Set> currSet = currSharedSet.get(locTupleKey); + if (currSet == null) { + currSet = new HashSet>(); + currSet.addAll(inSet); + currSharedSet.addWrite(locTupleKey, currSet); + } + currSet.retainAll(inSet); + } + + } + + private void computeSharedCoverSet() { + LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + + // current descriptors to visit in fixed-point interprocedural analysis, + // prioritized by + // dependency in the call graph + methodDescriptorsToVisitStack.clear(); + + descriptorListToAnalyze.removeFirst(); + + Set methodDescriptorToVistSet = new HashSet(); + methodDescriptorToVistSet.addAll(descriptorListToAnalyze); + + while (!descriptorListToAnalyze.isEmpty()) { + MethodDescriptor md = descriptorListToAnalyze.removeFirst(); + methodDescriptorsToVisitStack.add(md); + } + + // 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) { + + MethodDescriptor md = fm.getMethod(); + + Set flatNodesToVisit = new HashSet(); + + Set visited = new HashSet(); + + if (onlyVisitSSJavaLoop) { + flatNodesToVisit.add(ssjava.getSSJavaLoopEntrance()); + } else { + flatNodesToVisit.add(fm); + } + + while (!flatNodesToVisit.isEmpty()) { + FlatNode fn = flatNodesToVisit.iterator().next(); + flatNodesToVisit.remove(fn); + visited.add(fn); + + computeSharedCoverSet_nodeActions(md, fn, onlyVisitSSJavaLoop); + + 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); + } + } + + } + + } + + } + + private void computeSharedCoverSet_nodeActions(MethodDescriptor md, FlatNode fn, + boolean isEventLoopBody) { + TempDescriptor lhs; + TempDescriptor rhs; + FieldDescriptor fld; + + switch (fn.kind()) { + + case FKind.FlatLiteralNode: { + FlatLiteralNode fln = (FlatLiteralNode) fn; + lhs = fln.getDst(); + + NTuple lhsLocTuple = new NTuple(); + lhsLocTuple.add(Location.createTopLocation(md)); + mapDescriptorToLocationPath.put(lhs, lhsLocTuple); + + 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); + } + } + + } + break; + + case FKind.FlatOpNode: { + FlatOpNode fon = (FlatOpNode) fn; + // for a normal assign node, need to propagate lhs's location path to + // rhs + if (fon.getOp().getOp() == Operation.ASSIGN) { + rhs = fon.getLeft(); + lhs = fon.getDest(); + + if (!lhs.getSymbol().startsWith("neverused") && !lhs.getSymbol().startsWith("leftop") + && !lhs.getSymbol().startsWith("rightop")) { + + if (mapHeapPath.containsKey(rhs)) { + NTuple rhsLocTuple = new NTuple(); + NTuple lhsLocTuple = new NTuple(); + if (mapDescriptorToLocationPath.containsKey(rhs)) { + mapDescriptorToLocationPath.put(lhs, deriveLocationTuple(md, rhs)); + lhsLocTuple = mapDescriptorToLocationPath.get(lhs); + } else { + // rhs side + if (rhs.getType().getExtension() != null + && rhs.getType().getExtension() instanceof SSJavaType) { + + if (((SSJavaType) rhs.getType().getExtension()).getCompLoc() != null) { + rhsLocTuple.addAll(((SSJavaType) rhs.getType().getExtension()).getCompLoc() + .getTuple()); + } + + } else { + NTuple locTuple = deriveLocationTuple(md, rhs); + if (locTuple != null) { + rhsLocTuple.addAll(locTuple); + } + } + if (rhsLocTuple.size() > 0) { + mapDescriptorToLocationPath.put(rhs, rhsLocTuple); + } + + // lhs side + if (lhs.getType().getExtension() != null + && lhs.getType().getExtension() instanceof SSJavaType) { + lhsLocTuple.addAll(((SSJavaType) lhs.getType().getExtension()).getCompLoc() + .getTuple()); + mapDescriptorToLocationPath.put(lhs, lhsLocTuple); + } else if (mapDescriptorToLocationPath.get(rhs) != null) { + // propagate rhs's location to lhs + lhsLocTuple.addAll(mapDescriptorToLocationPath.get(rhs)); + mapDescriptorToLocationPath.put(lhs, lhsLocTuple); + } + } + + if (isEventLoopBody && lhs.getType().isPrimitive() + && !lhs.getSymbol().startsWith("srctmp")) { + + NTuple lhsHeapPath = computePath(lhs); + + if (lhsLocTuple != null) { + addMayWrittenSet(md, lhsLocTuple, lhsHeapPath); + } + + } + } else { + break; + } + + } + + } + } + break; + + case FKind.FlatSetFieldNode: + case FKind.FlatSetElementNode: { + + // x.f=y; + + if (fn.kind() == FKind.FlatSetFieldNode) { + FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; + lhs = fsfn.getDst(); + fld = fsfn.getField(); + rhs = fsfn.getSrc(); + } else { + FlatSetElementNode fsen = (FlatSetElementNode) fn; + lhs = fsen.getDst(); + rhs = fsen.getSrc(); + TypeDescriptor td = lhs.getType().dereference(); + fld = getArrayField(td); + } + + NTuple lhsLocTuple = new NTuple(); + if (fld.isStatic()) { + if (fld.isFinal()) { + // in this case, fld has TOP location + Location topLocation = Location.createTopLocation(md); + lhsLocTuple.add(topLocation); + } else { + lhsLocTuple.addAll(deriveGlobalLocationTuple(md)); + } + } else { + lhsLocTuple.addAll(deriveLocationTuple(md, lhs)); + } + + mapDescriptorToLocationPath.put(lhs, lhsLocTuple); + + NTuple fieldLocTuple = new NTuple(); + fieldLocTuple.addAll(lhsLocTuple); + + if (fn.kind() == FKind.FlatSetFieldNode) { + fieldLocTuple.add((Location) fld.getType().getExtension()); + } + + if (mapHeapPath.containsKey(lhs)) { + // fields reachable from the param can have heap path entry. + NTuple lhsHeapPath = new NTuple(); + lhsHeapPath.addAll(mapHeapPath.get(lhs)); + + Location fieldLocation; + if (fn.kind() == FKind.FlatSetFieldNode) { + fieldLocation = getLocation(fld); + } else { + fieldLocation = getLocation(lhsHeapPath.get(getArrayBaseDescriptorIdx(lhsHeapPath))); + } + + // Location fieldLocation = getLocation(lhs); + if (!isEventLoopBody && fieldLocation.getDescriptor().equals(md)) { + // if the field belongs to the local lattice, no reason to calculate + // shared location + break; + } + + if (ssjava.isSharedLocation(fieldLocation)) { + + NTuple fieldHeapPath = new NTuple(); + fieldHeapPath.addAll(computePath(lhs)); + if (fn.kind() == FKind.FlatSetFieldNode) { + fieldHeapPath.add(fld); + } + + addMayWrittenSet(md, fieldLocTuple, fieldHeapPath); + + } + } + + } + break; + + case FKind.FlatElementNode: + case FKind.FlatFieldNode: { + + // x=y.f; + + if (fn.kind() == FKind.FlatFieldNode) { + FlatFieldNode ffn = (FlatFieldNode) fn; + lhs = ffn.getDst(); + rhs = ffn.getSrc(); + fld = ffn.getField(); + } else { + FlatElementNode fen = (FlatElementNode) fn; + lhs = fen.getDst(); + rhs = fen.getSrc(); + TypeDescriptor td = rhs.getType().dereference(); + fld = getArrayField(td); + } + + NTuple locTuple = new NTuple(); + + if (fld.isStatic()) { + + if (fld.isFinal()) { + // in this case, fld has TOP location + Location topLocation = Location.createTopLocation(md); + locTuple.add(topLocation); + } else { + locTuple.addAll(deriveGlobalLocationTuple(md)); + if (fn.kind() == FKind.FlatFieldNode) { + locTuple.add((Location) fld.getType().getExtension()); + } + } + + } else { + locTuple.addAll(deriveLocationTuple(md, rhs)); + if (fn.kind() == FKind.FlatFieldNode) { + locTuple.add((Location) fld.getType().getExtension()); + } + } + + mapDescriptorToLocationPath.put(lhs, locTuple); + + } + break; + + case FKind.FlatCall: { + + FlatCall fc = (FlatCall) fn; + + bindLocationPathCallerArgWithCalleeParam(md, fc); + + } + break; + + case FKind.FlatNew: { + + FlatNew fnew = (FlatNew) fn; + TempDescriptor dst = fnew.getDst(); + NTuple locTuple = deriveLocationTuple(md, dst); + + if (locTuple != null) { + NTuple dstLocTuple = new NTuple(); + dstLocTuple.addAll(locTuple); + mapDescriptorToLocationPath.put(dst, dstLocTuple); + } + + } + break; + } + } + + private void addMayWrittenSet(MethodDescriptor md, NTuple locTuple, + NTuple heapPath) { + + MultiSourceMap, NTuple> map = mapMethodToSharedLocCoverSet.get(md); + if (map == null) { + map = new MultiSourceMap, NTuple>(); + mapMethodToSharedLocCoverSet.put(md, map); + } + + Set> writeSet = map.get(locTuple); + if (writeSet == null) { + writeSet = new HashSet>(); + map.put(locTuple, writeSet); + } + writeSet.add(heapPath); + + } + + 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 argLocationPath = deriveLocationTuple(mdCaller, arg); + NTuple argHeapPath = computePath(arg); + addMayWrittenSet(mdCaller, argLocationPath, argHeapPath); + } else if (ssjava.needTobeAnnotated(fc.getMethod())) { + + // 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> mapArgIdx2CallerArgHeapPath = + new Hashtable>(); + + // create mapping from arg idx to its location paths + Hashtable> mapArgIdx2CallerArgLocationPath = + new Hashtable>(); + + if (fc.getThis() != null) { + + if (mapHeapPath.containsKey(fc.getThis())) { + + // setup heap path for 'this' + NTuple thisHeapPath = new NTuple(); + thisHeapPath.addAll(mapHeapPath.get(fc.getThis())); + mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath); + + // setup location path for 'this' + NTuple thisLocationPath = deriveLocationTuple(mdCaller, fc.getThis()); + mapArgIdx2CallerArgLocationPath.put(Integer.valueOf(0), thisLocationPath); + + } + } + + for (int i = 0; i < fc.numArgs(); i++) { + TempDescriptor arg = fc.getArg(i); + // create mapping arg to loc path + + if (mapHeapPath.containsKey(arg)) { + // setup heap path + NTuple argHeapPath = mapHeapPath.get(arg); + mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath); + // setup loc path + NTuple argLocationPath = deriveLocationTuple(mdCaller, arg); + mapArgIdx2CallerArgLocationPath.put(Integer.valueOf(i + 1), argLocationPath); + } + + } + + 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, NTuple> mapParamHeapPathToCallerArgHeapPath = + new Hashtable, NTuple>(); + + 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); + + NTuple calleeHeapPath = computePath(param); + + NTuple argHeapPath = + mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i + offset)); + + if (argHeapPath != null) { + mapParamHeapPathToCallerArgHeapPath.put(calleeHeapPath, argHeapPath); + + } + + } + + Set keySet = mapArgIdx2CallerArgLocationPath.keySet(); + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + Integer idx = (Integer) iterator2.next(); + + NTuple callerArgLocationPath = mapArgIdx2CallerArgLocationPath.get(idx); + + TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx); + NTuple calleeLocationPath = deriveLocationTuple(mdCallee, calleeParam); + + NTuple callerArgHeapPath = mapArgIdx2CallerArgHeapPath.get(idx); + NTuple calleeHeapPath = computePath(calleeParam); + + if (!calleeParam.getType().isPrimitive()) { + createNewMappingOfMayWrittenSet(mdCaller, callee, callerArgHeapPath, + callerArgLocationPath, calleeHeapPath, calleeLocationPath, + mapParamHeapPathToCallerArgHeapPath); + } + } + + } + + } + + } + + private 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, + Hashtable, NTuple> mapParamHeapPathToCallerArgHeapPath) { + + // 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 + MultiSourceMap, NTuple> calleeMapping = + mapMethodToSharedLocCoverSet.get(callee); + + if (calleeMapping == null) { + return; + } + + MultiSourceMap, NTuple> callerMapping = + mapMethodToSharedLocCoverSet.get(caller); + + if (callerMapping == null) { + callerMapping = new MultiSourceMap, NTuple>(); + mapMethodToSharedLocCoverSet.put(caller, callerMapping); + } + + Hashtable, Set>> paramMapping = + getMappingByStartedWith(calleeMapping, calleeParamLocPath); + + Set> calleeKeySet = paramMapping.keySet(); + + for (Iterator iterator = calleeKeySet.iterator(); iterator.hasNext();) { + NTuple calleeKey = (NTuple) iterator.next(); + + Set> calleeMayWriteSet = paramMapping.get(calleeKey); + + if (calleeMayWriteSet != null) { + + Set> boundMayWriteSet = new HashSet>(); + + Set> boundSet = + convertToCallerMayWriteSet(calleeParamHeapPath, calleeMayWriteSet, callerMapping, + mapParamHeapPathToCallerArgHeapPath); + + boundMayWriteSet.addAll(boundSet); + + NTuple newKey = new NTuple(); + 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)); + } + + callerMapping.union(newKey, boundMayWriteSet); + } + + } + + } + + private Set> convertToCallerMayWriteSet( + NTuple calleeParamHeapPath, Set> calleeMayWriteSet, + MultiSourceMap, NTuple> callerMapping, + Hashtable, NTuple> mapParamHeapPathToCallerArgHeapPath) { + + 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 writeHeapPathParamHeapPath = calleeWriteHeapPath.subList(0, 1); + + NTuple callerArgHeapPath = + mapParamHeapPathToCallerArgHeapPath.get(writeHeapPathParamHeapPath); + + NTuple boundHeapPath = new NTuple(); + boundHeapPath.addAll(callerArgHeapPath); + + for (int i = 1; i < calleeWriteHeapPath.size(); i++) { + boundHeapPath.add(calleeWriteHeapPath.get(i)); + } + + boundSet.add(boundHeapPath); + + } + + return boundSet; + } + + private Location getLocation(Descriptor d) { + + if (d instanceof FieldDescriptor) { + TypeExtension te = ((FieldDescriptor) d).getType().getExtension(); + if (te != null) { + return (Location) te; + } + } else { + assert d instanceof TempDescriptor; + TempDescriptor td = (TempDescriptor) d; + + TypeExtension te = td.getType().getExtension(); + if (te != null) { + if (te instanceof SSJavaType) { + SSJavaType ssType = (SSJavaType) te; + if (ssType.getCompLoc() != null) { + CompositeLocation comp = ssType.getCompLoc(); + return comp.get(comp.getSize() - 1); + } else { + return null; + } + } else { + return (Location) te; + } + } + } + + return mapDescToLocation.get(d); + } + + private void eventLoopAnalysis() { + // perform second stage analysis: intraprocedural analysis ensure that + // all + // variables are definitely written in-between the same read + + Set flatNodesToVisit = new HashSet(); + flatNodesToVisit.add(ssjava.getSSJavaLoopEntrance()); + + while (!flatNodesToVisit.isEmpty()) { + FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); + flatNodesToVisit.remove(fn); + + Hashtable, Set> prev = mapFlatNodetoEventLoopMap.get(fn); + + Hashtable, Set> curr = + new Hashtable, Set>(); + for (int i = 0; i < fn.numPrev(); i++) { + FlatNode nn = fn.getPrev(i); + Hashtable, Set> in = mapFlatNodetoEventLoopMap.get(nn); + if (in != null) { + union(curr, in); + } + } + + eventLoopAnalysis_nodeAction(fn, curr, ssjava.getSSJavaLoopEntrance()); + + // if a new result, schedule forward nodes for analysis + if (!curr.equals(prev)) { + mapFlatNodetoEventLoopMap.put(fn, curr); + + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + if (loopIncElements.contains(nn)) { + flatNodesToVisit.add(nn); + } + + } + } + } + } + + private void union(Hashtable, Set> curr, + Hashtable, Set> in) { + + Set> inKeySet = in.keySet(); + for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) { + NTuple inKey = (NTuple) iterator.next(); + Set inSet = in.get(inKey); + + Set currSet = curr.get(inKey); + + if (currSet == null) { + currSet = new HashSet(); + curr.put(inKey, currSet); + } + currSet.addAll(inSet); + } + + } + + private void eventLoopAnalysis_nodeAction(FlatNode fn, + Hashtable, Set> curr, FlatNode loopEntrance) { + + Hashtable, Set> readWriteKillSet = + new Hashtable, Set>(); + Hashtable, Set> readWriteGenSet = + new Hashtable, Set>(); + + if (fn.equals(loopEntrance)) { + // it reaches loop entrance: changes all flag to true + Set> keySet = curr.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + NTuple key = (NTuple) iterator.next(); + Set writeAgeSet = curr.get(key); + + Set incSet = new HashSet(); + incSet.addAll(writeAgeSet); + writeAgeSet.clear(); + + for (Iterator iterator2 = incSet.iterator(); iterator2.hasNext();) { + WriteAge writeAge = (WriteAge) iterator2.next(); + WriteAge newWriteAge = writeAge.copy(); + newWriteAge.inc(); + writeAgeSet.add(newWriteAge); + } + + } + + } else { + TempDescriptor lhs; + TempDescriptor rhs; + FieldDescriptor fld; + + switch (fn.kind()) { + + case FKind.FlatOpNode: { + FlatOpNode fon = (FlatOpNode) fn; + lhs = fon.getDest(); + rhs = fon.getLeft(); + + if (fon.getOp().getOp() == Operation.ASSIGN) { + + if (!lhs.getSymbol().startsWith("neverused") && !lhs.getSymbol().startsWith("leftop") + && !lhs.getSymbol().startsWith("rightop")) { + + boolean hasWriteEffect = false; + + if (rhs.getType().getExtension() instanceof SSJavaType + && lhs.getType().getExtension() instanceof SSJavaType) { + + CompositeLocation rhsCompLoc = + ((SSJavaType) rhs.getType().getExtension()).getCompLoc(); + + CompositeLocation lhsCompLoc = + ((SSJavaType) lhs.getType().getExtension()).getCompLoc(); + + if (lhsCompLoc != rhsCompLoc) { + // have a write effect! + hasWriteEffect = true; + } + + } else if (lhs.getType().isImmutable()) { + hasWriteEffect = true; + } + + if (hasWriteEffect && mapHeapPath.containsKey(lhs)) { + // write(lhs) + NTuple lhsHeapPath = new NTuple(); + lhsHeapPath.addAll(mapHeapPath.get(lhs)); + + Location lhsLoc = getLocation(lhs); + if (ssjava.isSharedLocation(lhsLoc)) { + + NTuple varHeapPath = computePath(lhs); + NTuple varLocTuple = mapDescriptorToLocationPath.get(lhs); + + Set> writtenSet = + mapFlatNodeToSharedLocMapping.get(fn).get(varLocTuple); + + Set> mustClearSet = + mapFlatNodeToMustClearMap.get(fn).get(varLocTuple); + + if (isCovered(varLocTuple, writtenSet, mustClearSet)) { + computeKILLSetForSharedWrite(curr, writtenSet, readWriteKillSet); + computeGENSetForSharedAllCoverWrite(curr, writtenSet, readWriteGenSet); + } else { + computeGENSetForSharedNonCoverWrite(curr, varHeapPath, readWriteGenSet); + } + + } else { + + computeKILLSetForWrite(curr, lhsHeapPath, readWriteKillSet); + computeGENSetForWrite(lhsHeapPath, readWriteGenSet); + } + + Set writeAgeSet = curr.get(lhsHeapPath); + checkWriteAgeSet(writeAgeSet, lhsHeapPath, fn); + } + + } + + } + + } + break; + + case FKind.FlatFieldNode: + case FKind.FlatElementNode: { + + if (fn.kind() == FKind.FlatFieldNode) { + FlatFieldNode ffn = (FlatFieldNode) fn; + lhs = ffn.getDst(); + rhs = ffn.getSrc(); + fld = ffn.getField(); + } else { + FlatElementNode fen = (FlatElementNode) fn; + lhs = fen.getDst(); + rhs = fen.getSrc(); + TypeDescriptor td = rhs.getType().dereference(); + fld = getArrayField(td); + } + + // read field + NTuple srcHeapPath = mapHeapPath.get(rhs); + NTuple fldHeapPath; + if (srcHeapPath != null) { + fldHeapPath = new NTuple(srcHeapPath.getList()); + } else { + // if srcHeapPath is null, it is static reference + fldHeapPath = new NTuple(); + fldHeapPath.add(rhs); + } + fldHeapPath.add(fld); + + Set writeAgeSet = curr.get(fldHeapPath); + + checkWriteAgeSet(writeAgeSet, fldHeapPath, fn); + + } + break; + + case FKind.FlatSetFieldNode: + case FKind.FlatSetElementNode: { + + if (fn.kind() == FKind.FlatSetFieldNode) { + FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; + lhs = fsfn.getDst(); + fld = fsfn.getField(); + } else { + FlatSetElementNode fsen = (FlatSetElementNode) fn; + lhs = fsen.getDst(); + rhs = fsen.getSrc(); + TypeDescriptor td = lhs.getType().dereference(); + fld = getArrayField(td); + } + + // set up heap path + NTuple lhsHeapPath = mapHeapPath.get(lhs); + if (lhsHeapPath != null) { + // write(field) + NTuple fldHeapPath = new NTuple(lhsHeapPath.getList()); + if (fn.kind() == FKind.FlatSetFieldNode) { + fldHeapPath.add(fld); + } + + // shared loc extension + Location fieldLoc; + if (fn.kind() == FKind.FlatSetFieldNode) { + fieldLoc = (Location) fld.getType().getExtension(); + } else { + NTuple locTuple = mapDescriptorToLocationPath.get(lhs); + fieldLoc = locTuple.get(locTuple.size() - 1); + } + + if (ssjava.isSharedLocation(fieldLoc)) { + + NTuple fieldLocTuple = new NTuple(); + fieldLocTuple.addAll(mapDescriptorToLocationPath.get(lhs)); + if (fn.kind() == FKind.FlatSetFieldNode) { + fieldLocTuple.add(fieldLoc); + } + + Set> writtenSet = + mapFlatNodeToSharedLocMapping.get(fn).get(fieldLocTuple); + if (isCovered(fieldLocTuple, writtenSet)) { + computeKILLSetForSharedWrite(curr, writtenSet, readWriteKillSet); + computeGENSetForSharedAllCoverWrite(curr, writtenSet, readWriteGenSet); + } else { + computeGENSetForSharedNonCoverWrite(curr, fldHeapPath, readWriteGenSet); + } + + } else { + computeKILLSetForWrite(curr, fldHeapPath, readWriteKillSet); + computeGENSetForWrite(fldHeapPath, readWriteGenSet); + } + + } + + } + break; + + case FKind.FlatCall: { + FlatCall fc = (FlatCall) fn; + SharedLocMap sharedLocMap = mapFlatNodeToSharedLocMapping.get(fc); + SharedLocMap mustClearMap = mapFlatNodeToMustClearMap.get(fc); + generateKILLSetForFlatCall(fc, curr, sharedLocMap, mustClearMap, readWriteKillSet); + generateGENSetForFlatCall(fc, sharedLocMap, mustClearMap, readWriteGenSet); + + } + break; + + } + + computeNewMapping(curr, readWriteKillSet, readWriteGenSet); + if (fn instanceof FlatCall) { + checkManyRead((FlatCall) fn, curr); + } + + } + + } + + 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> curWrittenSet) { + + Set> coverSet = + mapMethodToSharedLocCoverSet.get(methodContainingSSJavaLoop).get(locTuple); + + if (curWrittenSet == null) { + return false; + } + + return curWrittenSet.containsAll(coverSet); + } + + private boolean isCovered(NTuple locTuple, Set> curWrittenSet, + Set> mustClearSet) { + + Set> coverSet = + mapMethodToSharedLocCoverSet.get(methodContainingSSJavaLoop).get(locTuple); + + if (mustClearSet != null && mustClearSet.containsAll(coverSet)) { + return true; + } + + if (curWrittenSet == null) { + return false; + } + + return curWrittenSet.containsAll(coverSet); + } + + private void checkManyRead(FlatCall fc, Hashtable, Set> curr) { + Set> boundReadSet = mapFlatNodeToBoundReadSet.get(fc); + for (Iterator iterator = boundReadSet.iterator(); iterator.hasNext();) { + NTuple readHeapPath = (NTuple) iterator.next(); + Set writeAgeSet = curr.get(readHeapPath); + checkWriteAgeSet(writeAgeSet, readHeapPath, fc); + } + + } + + private void checkWriteAgeSet(Set writeAgeSet, NTuple path, FlatNode fn) { + + if (writeAgeSet != null) { + for (Iterator iterator = writeAgeSet.iterator(); iterator.hasNext();) { + WriteAge writeAge = (WriteAge) iterator.next(); + if (writeAge.getAge() > MAXAGE) { + generateErrorMessage(path, fn); + } + } + } + } + + private void generateErrorMessage(NTuple path, FlatNode fn) { + + Descriptor lastDesc = path.get(getArrayBaseDescriptorIdx(path)); + if (ssjava.isSharedLocation(getLocation(lastDesc))) { + + NTuple locPathTuple = getLocationTuple(path); + Set> coverSet = + mapMethodToSharedLocCoverSet.get(methodContainingSSJavaLoop).get(locPathTuple); + throw new Error("Shared memory locations, which is reachable through references " + path + + ", are not completely overwritten by the higher values at " + + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::" + fn.getNumLine() + + ".\nThe following memory locations belong to the same shared locations:" + coverSet); + + } else { + throw new Error( + "Memory location, which is reachable through references " + + path + + ", who comes back to the same read statement without being overwritten at the out-most iteration at " + + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::" + + fn.getNumLine()); + } + + } + + private void generateGENSetForFlatCall(FlatCall fc, SharedLocMap sharedLocMap, + SharedLocMap mustClearMap, Hashtable, Set> GENSet) { + + Set> boundMayWriteSet = mapFlatNodeToBoundMayWriteSet.get(fc); + + for (Iterator iterator = boundMayWriteSet.iterator(); iterator.hasNext();) { + NTuple heapPath = (NTuple) iterator.next(); + + if (!isSharedLocation(heapPath)) { + addWriteAgeToSet(heapPath, GENSet, new WriteAge(0)); + } else { + // if the current heap path is shared location + + NTuple locTuple = getLocationTuple(heapPath); + + Set> sharedWriteHeapPathSet = sharedLocMap.get(locTuple); + + if (isCovered(locTuple, sharedLocMap.get(locTuple), mustClearMap.get(locTuple))) { + // if it is covered, add all of heap paths belong to the same shared + // loc with write age 0 + for (Iterator iterator2 = sharedWriteHeapPathSet.iterator(); iterator2.hasNext();) { + NTuple sharedHeapPath = (NTuple) iterator2.next(); + addWriteAgeToSet(sharedHeapPath, GENSet, new WriteAge(0)); + } + + } else { + // if not covered, add write age 1 to the heap path that is + // may-written but not covered + addWriteAgeToSet(heapPath, GENSet, new WriteAge(1)); + } + + } + + } + + } + + private void addWriteAgeToSet(NTuple heapPath, + Hashtable, Set> map, WriteAge age) { + + Set currSet = map.get(heapPath); + if (currSet == null) { + currSet = new HashSet(); + map.put(heapPath, currSet); + } + + currSet.add(age); + } + + private void generateKILLSetForFlatCall(FlatCall fc, + Hashtable, Set> curr, SharedLocMap sharedLocMap, + SharedLocMap mustClearMap, Hashtable, Set> KILLSet) { + + Set> boundMustWriteSet = mapFlatNodeToBoundMustWriteSet.get(fc); + + for (Iterator iterator = boundMustWriteSet.iterator(); iterator.hasNext();) { + NTuple heapPath = (NTuple) iterator.next(); + + if (isSharedLocation(heapPath)) { + NTuple locTuple = getLocationTuple(heapPath); + + if (isCovered(locTuple, sharedLocMap.get(locTuple), mustClearMap.get(locTuple)) + && curr.containsKey(heapPath)) { + // if it is shared loc and corresponding shared loc has been covered + KILLSet.put(heapPath, curr.get(heapPath)); + } + } else { + + for (Enumeration> e = curr.keys(); e.hasMoreElements();) { + NTuple key = e.nextElement(); + if (key.startsWith(heapPath)) { + KILLSet.put(key, curr.get(key)); + } + } + + } + + } + + } + + private int getArrayBaseDescriptorIdx(NTuple heapPath) { + + for (int i = heapPath.size() - 1; i >= 0; i--) { + if (!heapPath.get(i).getSymbol().equals(arrayElementFieldName)) { + return i; + } + } + + return -1; + + } + + private boolean isSharedLocation(NTuple heapPath) { + + Descriptor d = heapPath.get(getArrayBaseDescriptorIdx(heapPath)); + + return ssjava.isSharedLocation(getLocation(heapPath.get(getArrayBaseDescriptorIdx(heapPath)))); + + } + + private NTuple getLocationTuple(NTuple heapPath) { + + NTuple locTuple = new NTuple(); + + locTuple.addAll(mapDescriptorToLocationPath.get(heapPath.get(0))); + + for (int i = 1; i <= getArrayBaseDescriptorIdx(heapPath); i++) { + locTuple.add(getLocation(heapPath.get(i))); + } + + return locTuple; + } + + private void computeNewMapping(Hashtable, Set> curr, + Hashtable, Set> KILLSet, + Hashtable, Set> GENSet) { + + for (Enumeration> e = KILLSet.keys(); e.hasMoreElements();) { + NTuple key = e.nextElement(); + + Set writeAgeSet = curr.get(key); + if (writeAgeSet == null) { + writeAgeSet = new HashSet(); + curr.put(key, writeAgeSet); + } + writeAgeSet.removeAll(KILLSet.get(key)); + } + + for (Enumeration> e = GENSet.keys(); e.hasMoreElements();) { + NTuple key = e.nextElement(); + + Set currWriteAgeSet = curr.get(key); + if (currWriteAgeSet == null) { + currWriteAgeSet = new HashSet(); + curr.put(key, currWriteAgeSet); + } + currWriteAgeSet.addAll(GENSet.get(key)); + } + + } + + private void computeGENSetForWrite(NTuple fldHeapPath, + Hashtable, Set> GENSet) { + + // generate write age 0 for the field being written to + Set writeAgeSet = new HashSet(); + writeAgeSet.add(new WriteAge(0)); + GENSet.put(fldHeapPath, writeAgeSet); + } - public void definitelyWrittenCheck() { + private void computeKILLSetForWrite(Hashtable, Set> curr, + NTuple hp, Hashtable, Set> KILLSet) { - SymbolTable classtable = state.getClassSymbolTable(); - toanalyze.addAll(classtable.getValueSet()); - toanalyze.addAll(state.getTaskSymbolTable().getValueSet()); - while (!toanalyze.isEmpty()) { - Object obj = toanalyze.iterator().next(); - ClassDescriptor cd = (ClassDescriptor) obj; - toanalyze.remove(cd); - -// if (cd.isClassLibrary()) { - // doesn't care about class libraries now -// continue; -// } - for (Iterator method_it = cd.getMethods(); method_it.hasNext(); ) { - MethodDescriptor md = (MethodDescriptor) method_it.next(); - FlatMethod fm = state.getMethodFlat(md); - if (fm != null) { - - } - - } - } - - - - /* - // creating map - SymbolTable classtable = state.getClassSymbolTable(); - toanalyze.addAll(classtable.getValueSet()); - toanalyze.addAll(state.getTaskSymbolTable().getValueSet()); - while (!toanalyze.isEmpty()) { - Object obj = toanalyze.iterator().next(); - ClassDescriptor cd = (ClassDescriptor) obj; - toanalyze.remove(cd); - - if (cd.isClassLibrary()) { - // doesn't care about class libraries now - continue; - } - for (Iterator method_it = cd.getMethods(); method_it.hasNext();) { - MethodDescriptor md = (MethodDescriptor) method_it.next(); - FlatMethod fm = state.getMethodFlat(md); - if (fm != null) { - LoopFinder loopFinder = new LoopFinder(fm); - Loops loops = loopFinder.getRootloop(fm); - Set loopSet = loops.nestedLoops(); - - for (Iterator iterator = loopSet.iterator(); iterator.hasNext();) { - Loops rootLoops = (Loops) iterator.next(); - Set loopEntranceSet = rootLoops.loopEntrances(); - for (Iterator iterator2 = loopEntranceSet.iterator(); iterator2.hasNext();) { - FlatNode loopEnter = (FlatNode) iterator2.next(); - String flatNodeLabel = (String) state.fn2labelMap.get(loopEnter); - if (flatNodeLabel != null && flatNodeLabel.equals("ssjava")) { - System.out.println("encounting ss loop:" + loopEnter); - definitelyWrittenForward(loopEnter); - } - } - } + // removes all of heap path that starts with prefix 'hp' + // since any reference overwrite along heap path gives overwriting side + // effects on the value + + Set> keySet = curr.keySet(); + for (Iterator> iter = keySet.iterator(); iter.hasNext();) { + NTuple key = iter.next(); + if (key.startsWith(hp)) { + KILLSet.put(key, curr.get(key)); + } + } + + } + + private void bindHeapPathCallerArgWithCalleeParam(FlatCall fc) { + // compute all possible callee set + // transform all READ/WRITE set from the any possible + // callees to the caller + calleeUnionBoundReadSet.clear(); + calleeIntersectBoundMustWriteSet.clear(); + calleeUnionBoundMayWriteSet.clear(); + + if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) { + // ssjava util case! + // have write effects on the first argument + TempDescriptor arg = fc.getArg(0); + NTuple argHeapPath = computePath(arg); + calleeIntersectBoundMustWriteSet.add(argHeapPath); + calleeUnionBoundMayWriteSet.add(argHeapPath); + } else { + MethodDescriptor mdCallee = fc.getMethod(); + Set setPossibleCallees = new HashSet(); + setPossibleCallees.addAll(callGraph.getMethods(mdCallee)); + + // create mapping from arg idx to its heap paths + Hashtable> mapArgIdx2CallerArgHeapPath = + new Hashtable>(); + + // arg idx is starting from 'this' arg + if (fc.getThis() != null) { + NTuple thisHeapPath = mapHeapPath.get(fc.getThis()); + if (thisHeapPath != null) { + // if 'this' does not have heap path, it is local reference + 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); + } + + 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 + + Set> calleeReadSet = mapFlatMethodToReadSet.get(calleeFlatMethod); + if (calleeReadSet == null) { + calleeReadSet = new HashSet>(); + mapFlatMethodToReadSet.put(calleeFlatMethod, calleeReadSet); + } + + Set> calleeMustWriteSet = + mapFlatMethodToMustWriteSet.get(calleeFlatMethod); + + if (calleeMustWriteSet == null) { + calleeMustWriteSet = new HashSet>(); + mapFlatMethodToMustWriteSet.put(calleeFlatMethod, calleeMustWriteSet); + } + + Set> calleeMayWriteSet = + mapFlatMethodToMayWriteSet.get(calleeFlatMethod); + + if (calleeMayWriteSet == null) { + calleeMayWriteSet = new HashSet>(); + mapFlatMethodToMayWriteSet.put(calleeFlatMethod, calleeMayWriteSet); + } + + 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> calleeBoundReadSet = + bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath); + // union of the current read set and the current callee's + // read set + calleeUnionBoundReadSet.addAll(calleeBoundReadSet); + + Set> calleeBoundMustWriteSet = + bindSet(calleeMustWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath); + // intersection of the current overwrite set and the current + // callee's + // overwrite set + merge(calleeIntersectBoundMustWriteSet, calleeBoundMustWriteSet); + + Set> boundWriteSetFromCallee = + bindSet(calleeMayWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath); + calleeUnionBoundMayWriteSet.addAll(boundWriteSetFromCallee); + } + + } + + } + + private void bindHeapPathCallerArgWithCaleeParamForSharedLoc(MethodDescriptor mdCaller, + FlatCall fc) { + + calleeIntersectBoundSharedSet.clear(); + calleeUnionBoundDeleteSet.clear(); + + if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) { + // ssjava util case! + // have write effects on the first argument + TempDescriptor arg = fc.getArg(0); + NTuple argHeapPath = computePath(arg); + + // convert heap path to location path + NTuple argLocTuple = new NTuple(); + argLocTuple.addAll(deriveLocationTuple(mdCaller, (TempDescriptor) argHeapPath.get(0))); + for (int i = 1; i < argHeapPath.size(); i++) { + argLocTuple.add(getLocation(argHeapPath.get(i))); + } + + calleeIntersectBoundSharedSet.addWrite(argLocTuple, argHeapPath); + + } else if (ssjava.needTobeAnnotated(fc.getMethod())) { + + // 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> mapArgIdx2CallerArgHeapPath = + new Hashtable>(); + + // arg idx is starting from 'this' arg + if (fc.getThis() != null) { + 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); + } + + // create mapping from arg idx to its location paths + Hashtable> mapArgIdx2CallerAgLocationPath = + new Hashtable>(); + + // arg idx is starting from 'this' arg + if (fc.getThis() != null) { + NTuple thisLocationPath = deriveLocationTuple(fc.getMethod(), fc.getThis()); + if (thisLocationPath != null) { + mapArgIdx2CallerAgLocationPath.put(Integer.valueOf(0), thisLocationPath); + } + } + + for (int i = 0; i < fc.numArgs(); i++) { + TempDescriptor arg = fc.getArg(i); + NTuple argLocationPath = deriveLocationTuple(mdCaller, arg); + if (argLocationPath != null) { + mapArgIdx2CallerAgLocationPath.put(Integer.valueOf(i + 1), argLocationPath); + } + } + + 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 = mapArgIdx2CallerAgLocationPath.keySet(); + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + Integer idx = (Integer) iterator2.next(); + NTuple callerArgLocationPath = mapArgIdx2CallerAgLocationPath.get(idx); + NTuple callerArgHeapPath = mapArgIdx2CallerArgHeapPath.get(idx); + + TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx); + NTuple calleeLocationPath = deriveLocationTuple(mdCallee, calleeParam); + SharedLocMap calleeDeleteSet = mapFlatMethodToDeleteSet.get(calleeFlatMethod); + SharedLocMap calleeSharedLocMap = mapFlatMethodToSharedLocMap.get(calleeFlatMethod); + SharedLocMap calleeMustClearMap = mapFlatMethodToMustClearMap.get(calleeFlatMethod); + + if (calleeDeleteSet != null) { + createNewMappingOfDeleteSet(callerArgLocationPath, callerArgHeapPath, + calleeLocationPath, calleeDeleteSet); + } + + if (calleeSharedLocMap != null) { + createNewMappingOfSharedSet(callerArgLocationPath, callerArgHeapPath, + calleeLocationPath, calleeSharedLocMap); + } + + if (calleeMustClearMap != null) { + createNewMappingOfMustClearMap(callerArgLocationPath, callerArgHeapPath, + calleeLocationPath, calleeMustClearMap); + } - // check if there is a read statement with flag=TRUE - toanalyze.addAll(classtable.getValueSet()); - toanalyze.addAll(state.getTaskSymbolTable().getValueSet()); - while (!toanalyze.isEmpty()) { - Object obj = toanalyze.iterator().next(); - ClassDescriptor cd = (ClassDescriptor) obj; - toanalyze.remove(cd); - if (cd.isClassLibrary()) { - // doesn't care about class libraries now - continue; - } - for (Iterator method_it = cd.getMethods(); method_it.hasNext();) { - MethodDescriptor md = (MethodDescriptor) method_it.next(); - FlatMethod fm = state.getMethodFlat(md); - try { - checkMethodBody(fm); - } catch (Error e) { - System.out.println("Error in " + md); - throw e; } - } - } - */ + + } + } + + } + + private void createNewMappingOfMustClearMap(NTuple callerArgLocationPath, + NTuple callerArgHeapPath, NTuple calleeLocationPath, + SharedLocMap calleeMustClearMap) { + + SharedLocMap calleeParamSharedSet = + calleeMustClearMap.getHeapPathStartedWith(calleeLocationPath); + + Set> keySet = calleeParamSharedSet.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + NTuple calleeLocTupleKey = (NTuple) iterator.next(); + Set> heapPathSet = calleeParamSharedSet.get(calleeLocTupleKey); + Set> boundHeapPathSet = new HashSet>(); + for (Iterator iterator2 = heapPathSet.iterator(); iterator2.hasNext();) { + NTuple calleeHeapPath = (NTuple) iterator2.next(); + boundHeapPathSet.add(bindHeapPath(callerArgHeapPath, calleeHeapPath)); + } + calleeIntersectBoundMustClearSet.intersect( + bindLocationPath(callerArgLocationPath, calleeLocTupleKey), boundHeapPathSet); + } + + } + + private void createNewMappingOfDeleteSet(NTuple callerArgLocationPath, + NTuple callerArgHeapPath, NTuple calleeLocationPath, + SharedLocMap calleeDeleteSet) { + + SharedLocMap calleeParamDeleteSet = calleeDeleteSet.getHeapPathStartedWith(calleeLocationPath); + + Set> keySet = calleeParamDeleteSet.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + NTuple calleeLocTupleKey = (NTuple) iterator.next(); + Set> heapPathSet = calleeParamDeleteSet.get(calleeLocTupleKey); + for (Iterator iterator2 = heapPathSet.iterator(); iterator2.hasNext();) { + NTuple calleeHeapPath = (NTuple) iterator2.next(); + calleeUnionBoundDeleteSet.addWrite( + bindLocationPath(callerArgLocationPath, calleeLocTupleKey), + bindHeapPath(callerArgHeapPath, calleeHeapPath)); + } + } + + } + + private void createNewMappingOfSharedSet(NTuple callerArgLocationPath, + NTuple callerArgHeapPath, NTuple calleeLocationPath, + SharedLocMap calleeSharedLocMap) { + + SharedLocMap calleeParamSharedSet = + calleeSharedLocMap.getHeapPathStartedWith(calleeLocationPath); + + Set> keySet = calleeParamSharedSet.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + NTuple calleeLocTupleKey = (NTuple) iterator.next(); + Set> heapPathSet = calleeParamSharedSet.get(calleeLocTupleKey); + Set> boundHeapPathSet = new HashSet>(); + for (Iterator iterator2 = heapPathSet.iterator(); iterator2.hasNext();) { + NTuple calleeHeapPath = (NTuple) iterator2.next(); + boundHeapPathSet.add(bindHeapPath(callerArgHeapPath, calleeHeapPath)); + } + calleeIntersectBoundSharedSet.intersect( + bindLocationPath(callerArgLocationPath, calleeLocTupleKey), boundHeapPathSet); + } } + private NTuple bindLocationPath(NTuple start, NTuple end) { + NTuple locPath = new NTuple(); + locPath.addAll(start); + for (int i = 1; i < end.size(); i++) { + locPath.add(end.get(i)); + } + return locPath; + } + private NTuple bindHeapPath(NTuple start, NTuple end) { + NTuple heapPath = new NTuple(); + heapPath.addAll(start); + for (int i = 1; i < end.size(); i++) { + heapPath.add(end.get(i)); + } + return heapPath; + } + private void initialize() { + // First, identify ssjava loop entrace - private void checkMethodBody(FlatMethod fm) { + // no need to analyze method having ssjava loop + methodContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop(); + FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop); Set flatNodesToVisit = new HashSet(); - Set visited = new HashSet(); flatNodesToVisit.add(fm); + LoopFinder loopFinder = new LoopFinder(fm); + while (!flatNodesToVisit.isEmpty()) { - FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); - visited.add(fn); + FlatNode fn = flatNodesToVisit.iterator().next(); flatNodesToVisit.remove(fn); - checkMethodBody_nodeAction(fn); + String label = (String) state.fn2labelMap.get(fn); + if (label != null) { + + if (label.equals(ssjava.SSJAVA)) { + ssjava.setSSJavaLoopEntrance(fn); + break; + } + } - // if a new result, schedule forward nodes for analysis for (int i = 0; i < fn.numNext(); i++) { FlatNode nn = fn.getNext(i); - if (!visited.contains(nn)) { - flatNodesToVisit.add(nn); - } + flatNodesToVisit.add(nn); + } + } + + assert ssjava.getSSJavaLoopEntrance() != null; + + // assume that ssjava loop is top-level loop in method, not nested loop + Set nestedLoop = loopFinder.nestedLoops(); + for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) { + LoopFinder lf = (LoopFinder) loopIter.next(); + if (lf.loopEntrances().iterator().next().equals(ssjava.getSSJavaLoopEntrance())) { + ssjavaLoop = lf; } } + assert ssjavaLoop != null; + + loopIncElements = (Set) ssjavaLoop.loopIncElements(); + + // 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); + + liveInTempSetToEventLoop = + liveness.getLiveInTemps(state.getMethodFlat(methodContainingSSJavaLoop), + ssjava.getSSJavaLoopEntrance()); } - private void checkMethodBody_nodeAction(FlatNode fn) { + private void methodReadWriteSetAnalysis() { + // perform method READ/OVERWRITE analysis + LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); - TempDescriptor lhs; - TempDescriptor rhs; - FieldDescriptor fld; + // current descriptors to visit in fixed-point interprocedural analysis, + // prioritized by + // dependency in the call graph + methodDescriptorsToVisitStack.clear(); - switch (fn.kind()) { + descriptorListToAnalyze.removeFirst(); - case FKind.FlatOpNode: { + Set methodDescriptorToVistSet = new HashSet(); + methodDescriptorToVistSet.addAll(descriptorListToAnalyze); - FlatOpNode fon = (FlatOpNode) fn; - if (fon.getOp().getOp() == Operation.ASSIGN) { - lhs = fon.getDest(); - rhs = fon.getLeft(); - // read(rhs) - Hashtable> map = definitelyWrittenResults.get(fn); - if (map != null) { - if (map.get(rhs).get(fn).booleanValue()) { - // throw new Error("variable " + rhs - // + - // " was not overwritten in-between the same read statement by the out-most loop."); + while (!descriptorListToAnalyze.isEmpty()) { + MethodDescriptor md = descriptorListToAnalyze.removeFirst(); + methodDescriptorsToVisitStack.add(md); + } + + // analyze scheduled methods until there are no more to visit + while (!methodDescriptorsToVisitStack.isEmpty()) { + // start to analyze leaf node + MethodDescriptor md = methodDescriptorsToVisitStack.pop(); + FlatMethod fm = state.getMethodFlat(md); + + Set> readSet = new HashSet>(); + Set> mustWriteSet = new HashSet>(); + Set> mayWriteSet = new HashSet>(); + + methodReadWriteSet_analyzeMethod(fm, readSet, mustWriteSet, mayWriteSet); + + Set> prevRead = mapFlatMethodToReadSet.get(fm); + Set> prevMustWrite = mapFlatMethodToMustWriteSet.get(fm); + Set> prevMayWrite = mapFlatMethodToMayWriteSet.get(fm); + + if (!(readSet.equals(prevRead) && mustWriteSet.equals(prevMustWrite) && mayWriteSet + .equals(prevMayWrite))) { + mapFlatMethodToReadSet.put(fm, readSet); + mapFlatMethodToMustWriteSet.put(fm, mustWriteSet); + mapFlatMethodToMayWriteSet.put(fm, mayWriteSet); + + // results for callee changed, so enqueue dependents caller for + // further + // analysis + Iterator depsItr = ssjava.getDependents(md).iterator(); + while (depsItr.hasNext()) { + MethodDescriptor methodNext = depsItr.next(); + if (!methodDescriptorsToVisitStack.contains(methodNext) + && methodDescriptorToVistSet.contains(methodNext)) { + methodDescriptorsToVisitStack.add(methodNext); } + } } } - break; - case FKind.FlatFieldNode: { + methodReadWriteSetAnalysisToEventLoopBody(); - FlatFieldNode ffn = (FlatFieldNode) fn; - lhs = ffn.getDst(); - rhs = ffn.getSrc(); - fld = ffn.getField(); + } + private void methodReadWriteSet_analyzeMethod(FlatMethod fm, Set> readSet, + Set> mustWriteSet, Set> mayWriteSet) { + if (state.SSJAVADEBUG) { + System.out.println("SSJAVA: Definitely written Analyzing: " + fm); } - break; - case FKind.FlatElementNode: { + methodReadWriteSet_analyzeBody(fm, readSet, mustWriteSet, mayWriteSet, false); - } - break; + } - case FKind.FlatSetFieldNode: { - } - break; + private void methodReadWriteSetAnalysisToEventLoopBody() { - case FKind.FlatSetElementNode: { + // perform method read/write analysis for Event Loop Body + FlatMethod flatMethodContainingSSJavaLoop = state.getMethodFlat(methodContainingSSJavaLoop); + + if (state.SSJAVADEBUG) { + System.out.println("SSJAVA: Definitely written Event Loop Analyzing: " + + flatMethodContainingSSJavaLoop); } - break; - case FKind.FlatCall: { + Set> readSet = new HashSet>(); + Set> mustWriteSet = new HashSet>(); + Set> mayWriteSet = new HashSet>(); - } - break; + mapFlatMethodToReadSet.put(flatMethodContainingSSJavaLoop, readSet); + mapFlatMethodToMustWriteSet.put(flatMethodContainingSSJavaLoop, mustWriteSet); + mapFlatMethodToMayWriteSet.put(flatMethodContainingSSJavaLoop, mayWriteSet); + for (Iterator iterator = liveInTempSetToEventLoop.iterator(); iterator.hasNext();) { + TempDescriptor liveIn = (TempDescriptor) iterator.next(); + NTuple heapPath = new NTuple(); + heapPath.add(liveIn); + mapHeapPath.put(liveIn, heapPath); } + methodReadWriteSet_analyzeBody(ssjava.getSSJavaLoopEntrance(), readSet, mustWriteSet, + mayWriteSet, true); + } - private void definitelyWrittenForward(FlatNode entrance) { + private void methodReadWriteSet_analyzeBody(FlatNode startNode, Set> readSet, + Set> mustWriteSet, Set> mayWriteSet, + boolean isEventLoopBody) { + // intraprocedural analysis Set flatNodesToVisit = new HashSet(); - flatNodesToVisit.add(entrance); + flatNodesToVisit.add(startNode); while (!flatNodesToVisit.isEmpty()) { - FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); + FlatNode fn = flatNodesToVisit.iterator().next(); flatNodesToVisit.remove(fn); - Hashtable> prev = definitelyWrittenResults.get(fn); + Set> currMustWriteSet = new HashSet>(); - Hashtable> curr = - new Hashtable>(); for (int i = 0; i < fn.numPrev(); i++) { - FlatNode nn = fn.getPrev(i); - Hashtable> dwIn = definitelyWrittenResults.get(nn); - if (dwIn != null) { - mergeResults(curr, dwIn); + FlatNode prevFn = fn.getPrev(i); + Set> in = mapFlatNodeToMustWriteSet.get(prevFn); + if (in != null) { + merge(currMustWriteSet, in); } } - definitelyWritten_nodeActions(fn, curr, entrance); + methodReadWriteSet_nodeActions(fn, currMustWriteSet, readSet, mustWriteSet, mayWriteSet, + isEventLoopBody); - // if a new result, schedule forward nodes for analysis - if (!curr.equals(prev)) { - definitelyWrittenResults.put(fn, curr); + Set> mustSetPrev = mapFlatNodeToMustWriteSet.get(fn); + if (!currMustWriteSet.equals(mustSetPrev)) { + mapFlatNodeToMustWriteSet.put(fn, currMustWriteSet); for (int i = 0; i < fn.numNext(); i++) { FlatNode nn = fn.getNext(i); - flatNodesToVisit.add(nn); + if ((!isEventLoopBody) || loopIncElements.contains(nn)) { + flatNodesToVisit.add(nn); + } + } } + } + } - private void mergeResults(Hashtable> curr, - Hashtable> in) { + private void methodReadWriteSet_nodeActions(FlatNode fn, + Set> currMustWriteSet, Set> readSet, + Set> mustWriteSet, Set> mayWriteSet, + boolean isEventLoopBody) { + + TempDescriptor lhs; + TempDescriptor rhs; + FieldDescriptor fld; + + switch (fn.kind()) { + case FKind.FlatMethod: { + + // set up initial heap paths for method parameters + FlatMethod fm = (FlatMethod) fn; + for (int i = 0; i < fm.numParameters(); i++) { + TempDescriptor param = fm.getParameter(i); + NTuple heapPath = new NTuple(); + heapPath.add(param); + mapHeapPath.put(param, heapPath); + } + } + break; - Set inKeySet = in.keySet(); - for (Iterator iterator = inKeySet.iterator(); iterator.hasNext(); ) { - Descriptor inKey = (Descriptor) iterator.next(); - Hashtable inPair = in.get(inKey); + case FKind.FlatOpNode: { + FlatOpNode fon = (FlatOpNode) fn; + // for a normal assign node, need to propagate lhs's heap path to + // rhs - Set pairKeySet = inPair.keySet(); - for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext(); ) { - FlatNode pairKey = (FlatNode) iterator2.next(); - Boolean inFlag = inPair.get(pairKey); + if (fon.getOp().getOp() == Operation.ASSIGN) { + rhs = fon.getLeft(); + lhs = fon.getDest(); - Hashtable currPair = curr.get(inKey); - if (currPair == null) { - currPair = new Hashtable(); - curr.put(inKey, currPair); + NTuple rhsHeapPath = mapHeapPath.get(rhs); + + // if (lhs.getType().isPrimitive()) { + // NTuple lhsHeapPath = new NTuple(); + // lhsHeapPath.add(lhs); + // mapHeapPath.put(lhs, lhsHeapPath); + // } else + + if (rhsHeapPath != null && (!lhs.getType().isPrimitive())) { + mapHeapPath.put(lhs, mapHeapPath.get(rhs)); + } else { + break; + // if (isEventLoopBody) { + // NTuple lhsHeapPath = new NTuple(); + // lhsHeapPath.add(rhs); + // mapHeapPath.put(lhs, lhsHeapPath); + // } else { + // break; + // } } - Boolean currFlag = currPair.get(pairKey); - // by default, flag is set by false - if (currFlag == null) { - currFlag = Boolean.FALSE; - } - currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue()); - currPair.put(pairKey, currFlag); - } + // shared loc extension + if (isEventLoopBody) { + if (!lhs.getSymbol().startsWith("neverused") && rhs.getType().isImmutable()) { - } + if (rhs.getType().getExtension() instanceof Location + && lhs.getType().getExtension() instanceof CompositeLocation) { + // rhs is field! + Location rhsLoc = (Location) rhs.getType().getExtension(); - } + CompositeLocation lhsCompLoc = (CompositeLocation) lhs.getType().getExtension(); + Location dstLoc = lhsCompLoc.get(lhsCompLoc.getSize() - 1); - private void definitelyWritten_nodeActions(FlatNode fn, - Hashtable> curr, FlatNode entrance) { + NTuple heapPath = new NTuple(); + for (int i = 0; i < rhsHeapPath.size() - 1; i++) { + heapPath.add(rhsHeapPath.get(i)); + } - if (fn == entrance) { + NTuple writeHeapPath = new NTuple(); + writeHeapPath.addAll(heapPath); + writeHeapPath.add(lhs); - Set keySet = curr.keySet(); - for (Iterator iterator = keySet.iterator(); iterator.hasNext(); ) { - Descriptor key = (Descriptor) iterator.next(); - Hashtable pair = curr.get(key); - if (pair != null) { - Set pairKeySet = pair.keySet(); - for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext(); ) { - FlatNode pairKey = (FlatNode) iterator2.next(); - pair.put(pairKey, Boolean.TRUE); + } } } + } + } + break; - } else { - TempDescriptor lhs; - TempDescriptor rhs; - FieldDescriptor fld; + case FKind.FlatElementNode: + case FKind.FlatFieldNode: { - switch (fn.kind()) { + // x=y.f; - case FKind.FlatOpNode: { + if (fn.kind() == FKind.FlatFieldNode) { + FlatFieldNode ffn = (FlatFieldNode) fn; + lhs = ffn.getDst(); + rhs = ffn.getSrc(); + fld = ffn.getField(); + } else { + FlatElementNode fen = (FlatElementNode) fn; + lhs = fen.getDst(); + rhs = fen.getSrc(); + TypeDescriptor td = rhs.getType().dereference(); + fld = getArrayField(td); + } - FlatOpNode fon = (FlatOpNode) fn; - lhs = fon.getDest(); - rhs = fon.getLeft(); - System.out.println("\nfon=" + fon); + if (fld.isFinal()) { + // if field is final no need to check + break; + } - if (fon.getOp().getOp() == Operation.ASSIGN) { + // set up heap path + NTuple srcHeapPath = mapHeapPath.get(rhs); + if (srcHeapPath != null) { + // if lhs srcHeapPath is null, it means that it is not reachable from + // callee's parameters. so just ignore it - // read(rhs) - Hashtable gen = curr.get(rhs); - if (gen == null) { - gen = new Hashtable(); - curr.put(rhs, gen); - } - System.out.println("READ LOC=" + rhs.getType().getExtension()); + NTuple readingHeapPath = new NTuple(srcHeapPath.getList()); + if (fn.kind() == FKind.FlatFieldNode) { + readingHeapPath.add(fld); + } - Boolean currentStatus = gen.get(fn); - if (currentStatus == null) { - gen.put(fn, Boolean.FALSE); + mapHeapPath.put(lhs, readingHeapPath); + + // read (x.f) + if (fld.getType().isImmutable()) { + // if WT doesnot have hp(x.f), add hp(x.f) to READ + if (!currMustWriteSet.contains(readingHeapPath)) { + readSet.add(readingHeapPath); } } - // write(lhs) - curr.put(lhs, new Hashtable()); - System.out.println("WRITING LOC=" + lhs.getType().getExtension()); + // no need to kill hp(x.f) from WT } - break; - case FKind.FlatLiteralNode: { - FlatLiteralNode fln = (FlatLiteralNode) fn; - lhs = fln.getDst(); + } + break; - // write(lhs) - curr.put(lhs, new Hashtable()); + case FKind.FlatSetFieldNode: + case FKind.FlatSetElementNode: { - System.out.println("WRITING LOC=" + lhs.getType().getExtension()); + // x.f=y; + if (fn.kind() == FKind.FlatSetFieldNode) { + FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; + lhs = fsfn.getDst(); + fld = fsfn.getField(); + rhs = fsfn.getSrc(); + } else { + FlatSetElementNode fsen = (FlatSetElementNode) fn; + lhs = fsen.getDst(); + rhs = fsen.getSrc(); + TypeDescriptor td = lhs.getType().dereference(); + fld = getArrayField(td); } - break; - - case FKind.FlatFieldNode: - case FKind.FlatElementNode: { - FlatFieldNode ffn = (FlatFieldNode) fn; - lhs = ffn.getSrc(); - fld = ffn.getField(); + // set up heap path + NTuple lhsHeapPath = mapHeapPath.get(lhs); - // read field - Hashtable gen = curr.get(fld); - if (gen == null) { - gen = new Hashtable(); - curr.put(fld, gen); - } - Boolean currentStatus = gen.get(fn); - if (currentStatus == null) { - gen.put(fn, Boolean.FALSE); + if (lhsHeapPath != null) { + // if lhs heap path is null, it means that it is not reachable from + // callee's parameters. so just ignore it + NTuple fldHeapPath = new NTuple(lhsHeapPath.getList()); + if (fn.kind() != FKind.FlatSetElementNode) { + fldHeapPath.add(fld); } + // mapHeapPath.put(fld, fldHeapPath); - System.out.println("\nffn=" + ffn); - System.out.println("READ LOCfld=" + fld.getType().getExtension()); - System.out.println("READ LOClhs=" + lhs.getType().getExtension()); + // write(x.f) + // need to add hp(y) to WT + if (fn.kind() != FKind.FlatSetElementNode) { + currMustWriteSet.add(fldHeapPath); + } + mayWriteSet.add(fldHeapPath); } + + } break; - case FKind.FlatSetFieldNode: - case FKind.FlatSetElementNode: { + case FKind.FlatCall: { - FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; - fld = fsfn.getField(); + FlatCall fc = (FlatCall) fn; - // write(field) - curr.put(fld, new Hashtable()); + bindHeapPathCallerArgWithCalleeParam(fc); + + Set> boundReadSet = new HashSet>(); + boundReadSet.addAll(calleeUnionBoundReadSet); + + Set> boundMustWriteSet = new HashSet>(); + boundMustWriteSet.addAll(calleeIntersectBoundMustWriteSet); - System.out.println("\nfsfn=" + fsfn); - System.out.println("WRITELOC LOC=" + fld.getType().getExtension()); + Set> boundMayWriteSet = new HashSet>(); + boundMayWriteSet.addAll(calleeUnionBoundMayWriteSet); + mapFlatNodeToBoundReadSet.put(fn, boundReadSet); + mapFlatNodeToBoundMustWriteSet.put(fn, boundMustWriteSet); + mapFlatNodeToBoundMayWriteSet.put(fn, boundMayWriteSet); + + // add heap path, which is an element of READ_bound set and is not + // an + // element of WT set, to the caller's READ set + for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) { + NTuple read = (NTuple) iterator.next(); + if (!currMustWriteSet.contains(read)) { + readSet.add(read); + } } - break; - case FKind.FlatCall: { + // add heap path, which is an element of OVERWRITE_bound set, to the + // caller's WT set + for (Iterator iterator = calleeIntersectBoundMustWriteSet.iterator(); iterator.hasNext();) { + NTuple write = (NTuple) iterator.next(); + currMustWriteSet.add(write); + } + // add heap path, which is an element of WRITE_BOUND set, to the + // caller's writeSet + for (Iterator iterator = calleeUnionBoundMayWriteSet.iterator(); iterator.hasNext();) { + NTuple write = (NTuple) iterator.next(); + mayWriteSet.add(write); } + + } + break; + + case FKind.FlatExit: { + // merge the current written set with OVERWRITE set + merge(mustWriteSet, currMustWriteSet); + } break; + } + + } + + static public FieldDescriptor getArrayField(TypeDescriptor td) { + FieldDescriptor fd = mapTypeToArrayField.get(td); + if (fd == null) { + fd = + new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), td, arrayElementFieldName, null, + false); + mapTypeToArrayField.put(td, fd); + } + return fd; + } + + private void merge(Set> curr, Set> in) { + if (curr.isEmpty()) { + // set has a special initial value which covers all possible + // elements + // For the first time of intersection, we can take all previous set + curr.addAll(in); + } else { + // otherwise, current set is the intersection of the two sets + curr.retainAll(in); + } + + } + + // combine two heap path + private NTuple combine(NTuple callerIn, NTuple calleeIn) { + NTuple combined = new NTuple(); + + for (int i = 0; i < callerIn.size(); i++) { + combined.add(callerIn.get(i)); + } + + // the first element of callee's heap path represents parameter + // so we skip the first one since it is already added from caller's heap + // path + for (int i = 1; i < calleeIn.size(); i++) { + combined.add(calleeIn.get(i)); + } + + return combined; + } + + private Set> bindSet(Set> calleeSet, + Hashtable mapParamIdx2ParamTempDesc, + Hashtable> mapCallerArgIdx2HeapPath) { + + Set> boundedCalleeSet = new HashSet>(); + + Set keySet = mapCallerArgIdx2HeapPath.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Integer idx = (Integer) iterator.next(); + + NTuple callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx); + TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx); + for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) { + NTuple element = (NTuple) iterator2.next(); + if (element.startsWith(calleeParam)) { + NTuple boundElement = combine(callerArgHeapPath, element); + boundedCalleeSet.add(boundElement); + } + } + + } + return boundedCalleeSet; + + } + + private NTuple computePath(Descriptor td) { + // generate proper path fot input td + // if td is local variable, it just generate one element tuple path + if (mapHeapPath.containsKey(td)) { + NTuple rtrHeapPath = new NTuple(); + rtrHeapPath.addAll(mapHeapPath.get(td)); + return rtrHeapPath; + } else { + NTuple rtrHeapPath = new NTuple(); + rtrHeapPath.add(td); + return rtrHeapPath; } + } + + private NTuple deriveThisLocationTuple(MethodDescriptor md) { + String thisLocIdentifier = ssjava.getMethodLattice(md).getThisLoc(); + Location thisLoc = new Location(md, thisLocIdentifier); + NTuple locTuple = new NTuple(); + locTuple.add(thisLoc); + return locTuple; + } + private NTuple deriveGlobalLocationTuple(MethodDescriptor md) { + String globalLocIdentifier = ssjava.getMethodLattice(md).getGlobalLoc(); + Location globalLoc = new Location(md, globalLocIdentifier); + NTuple locTuple = new NTuple(); + locTuple.add(globalLoc); + return locTuple; } -} + private NTuple deriveLocationTuple(MethodDescriptor md, TempDescriptor td) { + assert td.getType() != null; + + if (mapDescriptorToLocationPath.containsKey(td)) { + NTuple locPath = mapDescriptorToLocationPath.get(td); + NTuple rtrPath = new NTuple(); + rtrPath.addAll(locPath); + return rtrPath; + } else { + if (td.getSymbol().startsWith("this")) { + NTuple thisPath = deriveThisLocationTuple(md); + NTuple rtrPath = new NTuple(); + rtrPath.addAll(thisPath); + return rtrPath; + } else { + + if (td.getType().getExtension() != null) { + SSJavaType ssJavaType = (SSJavaType) td.getType().getExtension(); + if (ssJavaType.getCompLoc() != null) { + NTuple rtrPath = new NTuple(); + rtrPath.addAll(ssJavaType.getCompLoc().getTuple()); + return rtrPath; + } + } + + return null; + + } + } + } +} \ No newline at end of file