1 package Analysis.SSJava;
3 import java.util.Enumeration;
4 import java.util.HashSet;
5 import java.util.Hashtable;
6 import java.util.Iterator;
7 import java.util.LinkedList;
9 import java.util.Stack;
11 import Analysis.CallGraph.CallGraph;
12 import Analysis.Loops.LoopFinder;
14 import IR.FieldDescriptor;
15 import IR.MethodDescriptor;
18 import IR.TypeDescriptor;
19 import IR.TypeExtension;
21 import IR.Flat.FlatCall;
22 import IR.Flat.FlatElementNode;
23 import IR.Flat.FlatFieldNode;
24 import IR.Flat.FlatLiteralNode;
25 import IR.Flat.FlatMethod;
26 import IR.Flat.FlatNew;
27 import IR.Flat.FlatNode;
28 import IR.Flat.FlatOpNode;
29 import IR.Flat.FlatSetElementNode;
30 import IR.Flat.FlatSetFieldNode;
31 import IR.Flat.TempDescriptor;
32 import IR.Tree.Modifiers;
34 public class DefinitelyWrittenCheck {
36 SSJavaAnalysis ssjava;
42 // maps a descriptor to its known dependents: namely
43 // methods or tasks that call the descriptor's method
44 // AND are part of this analysis (reachable from main)
45 private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
47 // maps a flat node to its WrittenSet: this keeps all heap path overwritten
49 private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToMustWriteSet;
51 // maps a temp descriptor to its heap path
52 // each temp descriptor has a unique heap path since we do not allow any
54 private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
56 // maps a temp descriptor to its composite location
57 private Hashtable<TempDescriptor, NTuple<Location>> mapDescriptorToLocationPath;
59 // maps a flat method to the READ that is the set of heap path that is
60 // expected to be written before method invocation
61 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToReadSet;
63 // maps a flat method to the must-write set that is the set of heap path that
64 // is overwritten on every possible path during method invocation
65 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToMustWriteSet;
67 // maps a flat method to the DELETE SET that is a set of heap path to shared
69 // written to but not overwritten by the higher value
70 private Hashtable<FlatMethod, SharedLocMap> mapFlatMethodToDeleteSet;
72 // maps a flat method to the S SET that is a set of heap path to shared
73 // locations that are overwritten by the higher value
74 private Hashtable<FlatMethod, SharedLocMap> mapFlatMethodToSharedLocMap;
76 // maps a flat method to the may-wirte set that is the set of heap path that
77 // might be written to
78 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToMayWriteSet;
80 // maps a call site to the read set contributed by all callees
81 private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToBoundReadSet;
83 // maps a call site to the must write set contributed by all callees
84 private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToBoundMustWriteSet;
86 // maps a call site to the may read set contributed by all callees
87 private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToBoundMayWriteSet;
89 // points to method containing SSJAVA Loop
90 private MethodDescriptor methodContainingSSJavaLoop;
92 // maps a flatnode to definitely written analysis mapping M
93 private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<WriteAge>>> mapFlatNodetoEventLoopMap;
95 // maps shared location to the set of descriptors which belong to the shared
98 // keep current descriptors to visit in fixed-point interprocedural analysis,
99 private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
101 // when analyzing flatcall, need to re-schedule set of callee
102 private Set<MethodDescriptor> calleesToEnqueue;
104 private Set<ReadSummary> possibleCalleeReadSummarySetToCaller;
106 public static final String arrayElementFieldName = "___element_";
107 static protected Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField;
109 // maps a method descriptor to the merged incoming caller's current
111 // it is for setting clearance flag when all read set is overwritten
112 private Hashtable<MethodDescriptor, ReadSummary> mapMethodDescriptorToReadSummary;
114 private Hashtable<MethodDescriptor, MultiSourceMap<NTuple<Location>, NTuple<Descriptor>>> mapMethodToSharedLocCoverSet;
116 private Hashtable<FlatNode, SharedLocMap> mapFlatNodeToSharedLocMapping;
117 private Hashtable<FlatNode, SharedLocMap> mapFlatNodeToDeleteSet;
119 private Hashtable<Location, Set<Descriptor>> mapSharedLocationToCoverSet;
121 private LinkedList<MethodDescriptor> sortedDescriptors;
123 private LoopFinder ssjavaLoop;
124 private Set<FlatNode> loopIncElements;
126 private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
127 private Set<NTuple<Descriptor>> calleeIntersectBoundMustWriteSet;
128 private Set<NTuple<Descriptor>> calleeUnionBoundMayWriteSet;
129 private SharedLocMap calleeUnionBoundDeleteSet;
130 private SharedLocMap calleeIntersectBoundSharedSet;
132 private Hashtable<Descriptor, Location> mapDescToLocation;
134 private TempDescriptor LOCAL;
136 public static int MAXAGE = 1;
138 public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
140 this.ssjava = ssjava;
141 this.callGraph = ssjava.getCallGraph();
142 this.mapFlatNodeToMustWriteSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
143 this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
144 this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
145 this.mapDescriptorToLocationPath = new Hashtable<TempDescriptor, NTuple<Location>>();
146 this.mapFlatMethodToReadSet = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
147 this.mapFlatMethodToMustWriteSet = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
148 this.mapFlatMethodToMayWriteSet = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
149 this.mapFlatNodetoEventLoopMap =
150 new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<WriteAge>>>();
151 this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
152 this.calleeIntersectBoundMustWriteSet = new HashSet<NTuple<Descriptor>>();
153 this.calleeUnionBoundMayWriteSet = new HashSet<NTuple<Descriptor>>();
155 this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
156 this.calleesToEnqueue = new HashSet<MethodDescriptor>();
157 this.mapTypeToArrayField = new Hashtable<TypeDescriptor, FieldDescriptor>();
158 this.LOCAL = new TempDescriptor("LOCAL");
159 this.mapDescToLocation = new Hashtable<Descriptor, Location>();
160 this.possibleCalleeReadSummarySetToCaller = new HashSet<ReadSummary>();
161 this.mapMethodDescriptorToReadSummary = new Hashtable<MethodDescriptor, ReadSummary>();
162 this.mapFlatNodeToBoundReadSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
163 this.mapFlatNodeToBoundMustWriteSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
164 this.mapFlatNodeToBoundMayWriteSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
165 this.mapSharedLocationToCoverSet = new Hashtable<Location, Set<Descriptor>>();
166 this.mapFlatNodeToSharedLocMapping = new Hashtable<FlatNode, SharedLocMap>();
167 this.mapFlatMethodToDeleteSet = new Hashtable<FlatMethod, SharedLocMap>();
168 this.calleeUnionBoundDeleteSet = new SharedLocMap();
169 this.calleeIntersectBoundSharedSet = new SharedLocMap();
170 this.mapFlatMethodToSharedLocMap = new Hashtable<FlatMethod, SharedLocMap>();
171 this.mapMethodToSharedLocCoverSet =
172 new Hashtable<MethodDescriptor, MultiSourceMap<NTuple<Location>, NTuple<Descriptor>>>();
173 this.mapFlatNodeToDeleteSet = new Hashtable<FlatNode, SharedLocMap>();
176 public void definitelyWrittenCheck() {
177 if (!ssjava.getAnnotationRequireSet().isEmpty()) {
180 methodReadWriteSetAnalysis();
181 computeSharedCoverSet();
190 private void sharedLocAnalysis() {
192 // perform method READ/OVERWRITE analysis
193 LinkedList<MethodDescriptor> descriptorListToAnalyze =
194 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
196 // current descriptors to visit in fixed-point interprocedural analysis,
198 // dependency in the call graph
199 methodDescriptorsToVisitStack.clear();
201 descriptorListToAnalyze.removeFirst();
203 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
204 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
206 while (!descriptorListToAnalyze.isEmpty()) {
207 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
208 methodDescriptorsToVisitStack.add(md);
211 // analyze scheduled methods until there are no more to visit
212 while (!methodDescriptorsToVisitStack.isEmpty()) {
213 // start to analyze leaf node
214 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
215 FlatMethod fm = state.getMethodFlat(md);
217 SharedLocMap sharedLocMap = new SharedLocMap();
218 SharedLocMap deleteSet = new SharedLocMap();
220 sharedLoc_analyzeMethod(fm, sharedLocMap, deleteSet);
221 SharedLocMap prevSharedLocMap = mapFlatMethodToSharedLocMap.get(fm);
222 SharedLocMap prevDeleteSet = mapFlatMethodToDeleteSet.get(fm);
224 if (!(deleteSet.equals(prevDeleteSet) && sharedLocMap.equals(prevSharedLocMap))) {
225 mapFlatMethodToSharedLocMap.put(fm, sharedLocMap);
226 mapFlatMethodToDeleteSet.put(fm, deleteSet);
228 // results for callee changed, so enqueue dependents caller for
231 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
232 while (depsItr.hasNext()) {
233 MethodDescriptor methodNext = depsItr.next();
234 if (!methodDescriptorsToVisitStack.contains(methodNext)
235 && methodDescriptorToVistSet.contains(methodNext)) {
236 methodDescriptorsToVisitStack.add(methodNext);
245 sharedLoc_analyzeEventLoop();
249 private void sharedLoc_analyzeEventLoop() {
250 if (state.SSJAVADEBUG) {
251 System.out.println("SSJAVA: Definite clearance for shared locations Analyzing: eventloop");
253 SharedLocMap sharedLocMap = new SharedLocMap();
254 SharedLocMap deleteSet = new SharedLocMap();
255 sharedLoc_analyzeBody(state.getMethodFlat(methodContainingSSJavaLoop),
256 ssjava.getSSJavaLoopEntrance(), sharedLocMap, deleteSet, true);
260 private void sharedLoc_analyzeMethod(FlatMethod fm, SharedLocMap sharedLocMap,
261 SharedLocMap deleteSet) {
262 if (state.SSJAVADEBUG) {
263 System.out.println("SSJAVA: Definite clearance for shared locations Analyzing: " + fm);
266 sharedLoc_analyzeBody(fm, fm, sharedLocMap, deleteSet, false);
270 private void sharedLoc_analyzeBody(FlatMethod fm, FlatNode startNode, SharedLocMap sharedLocMap,
271 SharedLocMap deleteSet, boolean isEventLoopBody) {
273 // intraprocedural analysis
274 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
275 flatNodesToVisit.add(startNode);
277 while (!flatNodesToVisit.isEmpty()) {
278 FlatNode fn = flatNodesToVisit.iterator().next();
279 flatNodesToVisit.remove(fn);
281 SharedLocMap currSharedSet = new SharedLocMap();
282 SharedLocMap currDeleteSet = new SharedLocMap();
284 for (int i = 0; i < fn.numPrev(); i++) {
285 FlatNode prevFn = fn.getPrev(i);
286 SharedLocMap inSharedLoc = mapFlatNodeToSharedLocMapping.get(prevFn);
287 if (inSharedLoc != null) {
288 mergeSharedLocMap(currSharedSet, inSharedLoc);
291 SharedLocMap inDeleteLoc = mapFlatNodeToDeleteSet.get(prevFn);
292 if (inDeleteLoc != null) {
293 mergeDeleteSet(currDeleteSet, inDeleteLoc);
297 sharedLoc_nodeActions(fm, fn, currSharedSet, currDeleteSet, sharedLocMap, deleteSet,
300 SharedLocMap prevSharedSet = mapFlatNodeToSharedLocMapping.get(fn);
301 SharedLocMap prevDeleteSet = mapFlatNodeToDeleteSet.get(fn);
303 if (!(currSharedSet.equals(prevSharedSet) && currDeleteSet.equals(prevDeleteSet))) {
304 mapFlatNodeToSharedLocMapping.put(fn, currSharedSet);
305 mapFlatNodeToDeleteSet.put(fn, currDeleteSet);
306 for (int i = 0; i < fn.numNext(); i++) {
307 FlatNode nn = fn.getNext(i);
308 if ((!isEventLoopBody) || loopIncElements.contains(nn)) {
309 flatNodesToVisit.add(nn);
319 private void sharedLoc_nodeActions(FlatMethod fm, FlatNode fn, SharedLocMap curr,
320 SharedLocMap currDeleteSet, SharedLocMap sharedLocMap, SharedLocMap deleteSet,
321 boolean isEventLoopBody) {
323 MethodDescriptor md = fm.getMethod();
325 SharedLocMap killSet = new SharedLocMap();
326 SharedLocMap genSet = new SharedLocMap();
334 case FKind.FlatOpNode: {
336 if (isEventLoopBody) {
337 FlatOpNode fon = (FlatOpNode) fn;
339 if (fon.getOp().getOp() == Operation.ASSIGN) {
343 if (!lhs.getSymbol().startsWith("neverused") && !lhs.getSymbol().startsWith("leftop")
344 && !lhs.getSymbol().startsWith("rightop") && rhs.getType().isImmutable()) {
346 Location dstLoc = getLocation(lhs);
347 if (dstLoc != null && ssjava.isSharedLocation(dstLoc)) {
348 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
349 NTuple<Location> lhsLocTuple = mapDescriptorToLocationPath.get(lhs);
351 Location srcLoc = getLocation(lhs);
353 // computing gen/kill set
354 computeKILLSetForWrite(curr, killSet, lhsLocTuple, lhsHeapPath);
355 if (!dstLoc.equals(srcLoc)) {
356 computeGENSetForHigherWrite(curr, killSet, lhsLocTuple, lhsHeapPath);
357 updateDeleteSetForHigherWrite(currDeleteSet, lhsLocTuple, lhsHeapPath);
359 computeGENSetForSameHeightWrite(curr, killSet, lhsLocTuple, lhsHeapPath);
360 updateDeleteSetForSameHeightWrite(currDeleteSet, lhsLocTuple, lhsHeapPath);
363 // System.out.println("VAR WRITE:" + fn);
364 // System.out.println("lhsLocTuple=" + lhsLocTuple +
365 // " lhsHeapPath=" + lhsHeapPath);
366 // System.out.println("dstLoc=" + dstLoc + " srcLoc=" + srcLoc);
367 // System.out.println("KILLSET=" + killSet);
368 // System.out.println("GENSet=" + genSet);
369 // System.out.println("DELETESET=" + currDeleteSet);
382 case FKind.FlatSetFieldNode:
383 case FKind.FlatSetElementNode: {
386 if (fn.kind() == FKind.FlatSetFieldNode) {
387 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
389 fld = fsfn.getField();
391 fieldLoc = (Location) fld.getType().getExtension();
393 FlatSetElementNode fsen = (FlatSetElementNode) fn;
396 TypeDescriptor td = lhs.getType().dereference();
397 fld = getArrayField(td);
399 NTuple<Location> locTuple = deriveLocationTuple(md, lhs);
400 fieldLoc = locTuple.get(locTuple.size() - 1);
403 if (!isEventLoopBody && fieldLoc.getDescriptor().equals(md)) {
404 // if the field belongs to the local lattice, no reason to calculate
409 NTuple<Location> fieldLocTuple = new NTuple<Location>();
410 if (fld.isStatic()) {
412 // in this case, fld has TOP location
413 Location topLocation = Location.createTopLocation(md);
414 fieldLocTuple.add(topLocation);
416 fieldLocTuple.addAll(deriveGlobalLocationTuple(md));
417 if (fn.kind() == FKind.FlatSetFieldNode) {
418 fieldLocTuple.add((Location) fld.getType().getExtension());
423 fieldLocTuple.addAll(deriveLocationTuple(md, lhs));
424 if (fn.kind() == FKind.FlatSetFieldNode) {
425 fieldLocTuple.add((Location) fld.getType().getExtension());
429 // shared loc extension
430 Location srcLoc = getLocation(rhs);
431 if (ssjava.isSharedLocation(fieldLoc)) {
432 // only care the case that loc(f) is shared location
435 // NTuple<Location> fieldLocTuple = new NTuple<Location>();
436 // fieldLocTuple.addAll(mapDescriptorToLocationPath.get(lhs));
437 // fieldLocTuple.add(fieldLoc);
439 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>();
440 fldHeapPath.addAll(computePath(lhs));
441 fldHeapPath.add(fld);
443 // computing gen/kill set
444 computeKILLSetForWrite(curr, killSet, fieldLocTuple, fldHeapPath);
445 if (!fieldLoc.equals(srcLoc)) {
446 computeGENSetForHigherWrite(curr, genSet, fieldLocTuple, fldHeapPath);
447 updateDeleteSetForHigherWrite(currDeleteSet, fieldLocTuple, fldHeapPath);
449 computeGENSetForSameHeightWrite(curr, genSet, fieldLocTuple, fldHeapPath);
450 updateDeleteSetForSameHeightWrite(currDeleteSet, fieldLocTuple, fldHeapPath);
453 // System.out.println("################");
454 // System.out.println("FIELD WRITE:" + fn);
455 // System.out.println("FldHeapPath=" + fldHeapPath);
456 // System.out.println("fieldLocTuple=" + fieldLocTuple + " srcLoc=" +
458 // System.out.println("KILLSET=" + killSet);
459 // System.out.println("GENSet=" + genSet);
460 // System.out.println("DELETESET=" + currDeleteSet);
466 case FKind.FlatCall: {
467 FlatCall fc = (FlatCall) fn;
469 if (ssjava.needTobeAnnotated(fc.getMethod())) {
471 bindHeapPathCallerArgWithCaleeParamForSharedLoc(fm.getMethod(), fc);
473 // computing gen/kill set
474 generateKILLSetForFlatCall(curr, killSet);
475 generateGENSetForFlatCall(curr, genSet);
478 // System.out.println("#FLATCALL=" + fc);
479 // System.out.println("KILLSET=" + killSet);
480 // System.out.println("GENSet=" + genSet);
481 // System.out.println("bound DELETE Set=" + calleeUnionBoundDeleteSet);
486 case FKind.FlatExit: {
487 // merge the current delete/shared loc mapping
488 mergeSharedLocMap(sharedLocMap, curr);
489 mergeDeleteSet(deleteSet, currDeleteSet);
491 // System.out.println("#FLATEXIT sharedLocMap=" + sharedLocMap);
497 computeNewMapping(curr, killSet, genSet);
498 if (!curr.map.isEmpty()) {
499 // System.out.println(fn + "#######" + curr);
504 private void generateGENSetForFlatCall(SharedLocMap curr, SharedLocMap genSet) {
506 Set<NTuple<Location>> locTupleSet = calleeIntersectBoundSharedSet.keySet();
507 for (Iterator iterator = locTupleSet.iterator(); iterator.hasNext();) {
508 NTuple<Location> locTupleKey = (NTuple<Location>) iterator.next();
509 genSet.addWrite(locTupleKey, curr.get(locTupleKey));
510 genSet.addWrite(locTupleKey, calleeIntersectBoundSharedSet.get(locTupleKey));
512 genSet.removeWriteAll(locTupleKey, calleeUnionBoundDeleteSet.get(locTupleKey));
517 private void generateKILLSetForFlatCall(SharedLocMap curr, SharedLocMap killSet) {
519 Set<NTuple<Location>> locTupleSet = calleeIntersectBoundSharedSet.keySet();
520 for (Iterator iterator = locTupleSet.iterator(); iterator.hasNext();) {
521 NTuple<Location> locTupleKey = (NTuple<Location>) iterator.next();
522 killSet.addWrite(locTupleKey, curr.get(locTupleKey));
527 private void mergeDeleteSet(SharedLocMap currDeleteSet, SharedLocMap inDeleteLoc) {
529 Set<NTuple<Location>> locTupleKeySet = inDeleteLoc.keySet();
531 for (Iterator iterator = locTupleKeySet.iterator(); iterator.hasNext();) {
532 NTuple<Location> locTupleKey = (NTuple<Location>) iterator.next();
534 Set<NTuple<Descriptor>> inSet = inDeleteLoc.get(locTupleKey);
535 currDeleteSet.addWrite(locTupleKey, inSet);
540 private void computeNewMapping(SharedLocMap curr, SharedLocMap killSet, SharedLocMap genSet) {
545 private void updateDeleteSetForHigherWrite(SharedLocMap currDeleteSet, NTuple<Location> locTuple,
546 NTuple<Descriptor> hp) {
547 currDeleteSet.removeWrite(locTuple, hp);
550 private void updateDeleteSetForSameHeightWrite(SharedLocMap currDeleteSet,
551 NTuple<Location> locTuple, NTuple<Descriptor> hp) {
552 currDeleteSet.addWrite(locTuple, hp);
555 private void computeGENSetForHigherWrite(SharedLocMap curr, SharedLocMap genSet,
556 NTuple<Location> locTuple, NTuple<Descriptor> hp) {
557 Set<NTuple<Descriptor>> currWriteSet = curr.get(locTuple);
559 if (currWriteSet != null) {
560 genSet.addWrite(locTuple, currWriteSet);
563 genSet.addWrite(locTuple, hp);
566 private void computeGENSetForSameHeightWrite(SharedLocMap curr, SharedLocMap genSet,
567 NTuple<Location> locTuple, NTuple<Descriptor> hp) {
568 Set<NTuple<Descriptor>> currWriteSet = curr.get(locTuple);
570 if (currWriteSet != null) {
571 genSet.addWrite(locTuple, currWriteSet);
573 genSet.removeWrite(locTuple, hp);
576 private void computeKILLSetForWrite(SharedLocMap curr, SharedLocMap killSet,
577 NTuple<Location> locTuple, NTuple<Descriptor> hp) {
579 Set<NTuple<Descriptor>> writeSet = curr.get(locTuple);
580 if (writeSet != null) {
581 killSet.addWrite(locTuple, writeSet);
586 private void mergeSharedLocMap(SharedLocMap currSharedSet, SharedLocMap in) {
588 Set<NTuple<Location>> locTupleKeySet = in.keySet();
589 for (Iterator iterator = locTupleKeySet.iterator(); iterator.hasNext();) {
590 NTuple<Location> locTupleKey = (NTuple<Location>) iterator.next();
592 Set<NTuple<Descriptor>> inSet = in.get(locTupleKey);
593 Set<NTuple<Descriptor>> currSet = currSharedSet.get(locTupleKey);
594 if (currSet == null) {
595 currSet = new HashSet<NTuple<Descriptor>>();
596 currSet.addAll(inSet);
597 currSharedSet.addWrite(locTupleKey, currSet);
599 currSet.retainAll(inSet);
604 private void computeSharedCoverSet() {
605 LinkedList<MethodDescriptor> descriptorListToAnalyze =
606 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
608 // current descriptors to visit in fixed-point interprocedural analysis,
610 // dependency in the call graph
611 methodDescriptorsToVisitStack.clear();
613 descriptorListToAnalyze.removeFirst();
615 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
616 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
618 while (!descriptorListToAnalyze.isEmpty()) {
619 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
620 methodDescriptorsToVisitStack.add(md);
623 // analyze scheduled methods until there are no more to visit
624 while (!methodDescriptorsToVisitStack.isEmpty()) {
625 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
626 FlatMethod fm = state.getMethodFlat(md);
627 computeSharedCoverSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
630 computeSharedCoverSetForEventLoop();
634 private void computeSharedCoverSetForEventLoop() {
635 computeSharedCoverSet_analyzeMethod(state.getMethodFlat(methodContainingSSJavaLoop), true);
638 private void computeSharedCoverSet_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) {
640 System.out.println("computeSharedCoverSet_analyzeMethod=" + fm);
641 MethodDescriptor md = fm.getMethod();
642 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
644 Set<FlatNode> visited = new HashSet<FlatNode>();
646 if (onlyVisitSSJavaLoop) {
647 flatNodesToVisit.add(ssjava.getSSJavaLoopEntrance());
649 flatNodesToVisit.add(fm);
652 while (!flatNodesToVisit.isEmpty()) {
653 FlatNode fn = flatNodesToVisit.iterator().next();
654 flatNodesToVisit.remove(fn);
657 computeSharedCoverSet_nodeActions(md, fn, onlyVisitSSJavaLoop);
659 for (int i = 0; i < fn.numNext(); i++) {
660 FlatNode nn = fn.getNext(i);
662 if (!visited.contains(nn)) {
663 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
664 flatNodesToVisit.add(nn);
674 private void computeSharedCoverSet_nodeActions(MethodDescriptor md, FlatNode fn,
675 boolean isEventLoopBody) {
682 case FKind.FlatLiteralNode: {
683 FlatLiteralNode fln = (FlatLiteralNode) fn;
686 NTuple<Location> lhsLocTuple = new NTuple<Location>();
687 lhsLocTuple.add(Location.createTopLocation(md));
688 mapDescriptorToLocationPath.put(lhs, lhsLocTuple);
690 if (lhs.getType().isPrimitive() && !lhs.getSymbol().startsWith("neverused")
691 && !lhs.getSymbol().startsWith("srctmp")) {
692 // only need to care about composite location case here
693 if (lhs.getType().getExtension() instanceof SSJavaType) {
694 CompositeLocation compLoc = ((SSJavaType) lhs.getType().getExtension()).getCompLoc();
695 Location lastLocElement = compLoc.get(compLoc.getSize() - 1);
696 // check if the last one is shared loc
697 if (ssjava.isSharedLocation(lastLocElement)) {
698 addSharedLocDescriptor(lastLocElement, lhs);
706 case FKind.FlatOpNode: {
707 FlatOpNode fon = (FlatOpNode) fn;
708 // for a normal assign node, need to propagate lhs's location path to
710 if (fon.getOp().getOp() == Operation.ASSIGN) {
714 if (!lhs.getSymbol().startsWith("neverused") && !lhs.getSymbol().startsWith("leftop")
715 && !lhs.getSymbol().startsWith("rightop")) {
717 NTuple<Location> rhsLocTuple = new NTuple<Location>();
718 NTuple<Location> lhsLocTuple = new NTuple<Location>();
719 if (mapDescriptorToLocationPath.containsKey(rhs)) {
720 mapDescriptorToLocationPath.put(lhs, mapDescriptorToLocationPath.get(rhs));
723 if (rhs.getType().getExtension() != null
724 && rhs.getType().getExtension() instanceof SSJavaType) {
726 if (((SSJavaType) rhs.getType().getExtension()).getCompLoc() != null) {
727 rhsLocTuple.addAll(((SSJavaType) rhs.getType().getExtension()).getCompLoc()
732 NTuple<Location> locTuple = deriveLocationTuple(md, rhs);
733 if (locTuple != null) {
734 rhsLocTuple.addAll(locTuple);
737 if (rhsLocTuple.size() > 0) {
738 mapDescriptorToLocationPath.put(rhs, rhsLocTuple);
742 if (lhs.getType().getExtension() != null
743 && lhs.getType().getExtension() instanceof SSJavaType) {
744 lhsLocTuple.addAll(((SSJavaType) lhs.getType().getExtension()).getCompLoc()
746 mapDescriptorToLocationPath.put(lhs, lhsLocTuple);
747 } else if (mapDescriptorToLocationPath.get(rhs) != null) {
748 // propagate rhs's location to lhs
749 lhsLocTuple.addAll(mapDescriptorToLocationPath.get(rhs));
750 mapDescriptorToLocationPath.put(lhs, lhsLocTuple);
755 if (lhs.getType().isPrimitive() && !lhs.getSymbol().startsWith("srctmp")) {
757 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
759 if (lhsLocTuple != null) {
760 addMayWrittenSet(md, lhsLocTuple, lhsHeapPath);
770 case FKind.FlatSetFieldNode:
771 case FKind.FlatSetElementNode: {
775 if (fn.kind() == FKind.FlatSetFieldNode) {
776 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
778 fld = fsfn.getField();
781 FlatSetElementNode fsen = (FlatSetElementNode) fn;
784 TypeDescriptor td = lhs.getType().dereference();
785 fld = getArrayField(td);
788 Location fieldLocation;
789 if (fn.kind() == FKind.FlatSetFieldNode) {
790 fieldLocation = (Location) fld.getType().getExtension();
792 NTuple<Location> locTuple = mapDescriptorToLocationPath.get(lhs);
793 fieldLocation = locTuple.get(locTuple.size() - 1);
796 if (!isEventLoopBody && fieldLocation.getDescriptor().equals(md)) {
797 // if the field belongs to the local lattice, no reason to calculate
802 NTuple<Location> fieldLocTuple = new NTuple<Location>();
803 if (fld.isStatic()) {
805 // in this case, fld has TOP location
806 Location topLocation = Location.createTopLocation(md);
807 fieldLocTuple.add(topLocation);
809 fieldLocTuple.addAll(deriveGlobalLocationTuple(md));
810 if (fn.kind() == FKind.FlatSetFieldNode) {
811 fieldLocTuple.add((Location) fld.getType().getExtension());
816 fieldLocTuple.addAll(deriveLocationTuple(md, lhs));
817 if (fn.kind() == FKind.FlatSetFieldNode) {
818 fieldLocTuple.add((Location) fld.getType().getExtension());
822 NTuple<Location> lTuple = deriveLocationTuple(md, lhs);
823 if (lTuple != null) {
824 NTuple<Location> lhsLocTuple = new NTuple<Location>();
825 lhsLocTuple.addAll(lTuple);
826 mapDescriptorToLocationPath.put(lhs, lhsLocTuple);
829 if (ssjava.isSharedLocation(fieldLocation)) {
830 addSharedLocDescriptor(fieldLocation, fld);
832 NTuple<Descriptor> fieldHeapPath = new NTuple<Descriptor>();
833 fieldHeapPath.addAll(computePath(lhs));
834 fieldHeapPath.add(fld);
836 // mapLocationPathToMayWrittenSet.put(locTuple, null, fld);
837 addMayWrittenSet(md, fieldLocTuple, fieldHeapPath);
844 case FKind.FlatElementNode:
845 case FKind.FlatFieldNode: {
849 if (fn.kind() == FKind.FlatFieldNode) {
850 FlatFieldNode ffn = (FlatFieldNode) fn;
853 fld = ffn.getField();
855 FlatElementNode fen = (FlatElementNode) fn;
858 TypeDescriptor td = rhs.getType().dereference();
859 fld = getArrayField(td);
862 NTuple<Location> locTuple = new NTuple<Location>();
864 if (fld.isStatic()) {
867 // in this case, fld has TOP location
868 Location topLocation = Location.createTopLocation(md);
869 locTuple.add(topLocation);
871 locTuple.addAll(deriveGlobalLocationTuple(md));
872 if (fn.kind() == FKind.FlatFieldNode) {
873 locTuple.add((Location) fld.getType().getExtension());
878 locTuple.addAll(deriveLocationTuple(md, rhs));
879 if (fn.kind() == FKind.FlatFieldNode) {
880 locTuple.add((Location) fld.getType().getExtension());
884 mapDescriptorToLocationPath.put(lhs, locTuple);
889 case FKind.FlatCall: {
891 FlatCall fc = (FlatCall) fn;
893 if (ssjava.needTobeAnnotated(fc.getMethod())) {
894 bindLocationPathCallerArgWithCalleeParam(md, fc);
900 case FKind.FlatNew: {
902 FlatNew fnew = (FlatNew) fn;
903 TempDescriptor dst = fnew.getDst();
904 NTuple<Location> locTuple = deriveLocationTuple(md, dst);
906 if (locTuple != null) {
907 NTuple<Location> dstLocTuple = new NTuple<Location>();
908 dstLocTuple.addAll(locTuple);
909 mapDescriptorToLocationPath.put(dst, dstLocTuple);
917 private void addMayWrittenSet(MethodDescriptor md, NTuple<Location> locTuple,
918 NTuple<Descriptor> heapPath) {
920 MultiSourceMap<NTuple<Location>, NTuple<Descriptor>> map = mapMethodToSharedLocCoverSet.get(md);
922 map = new MultiSourceMap<NTuple<Location>, NTuple<Descriptor>>();
923 mapMethodToSharedLocCoverSet.put(md, map);
926 Set<NTuple<Descriptor>> writeSet = map.get(locTuple);
927 if (writeSet == null) {
928 writeSet = new HashSet<NTuple<Descriptor>>();
929 map.put(locTuple, writeSet);
931 writeSet.add(heapPath);
935 private void bindLocationPathCallerArgWithCalleeParam(MethodDescriptor mdCaller, FlatCall fc) {
937 if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
939 // have write effects on the first argument
940 TempDescriptor arg = fc.getArg(0);
941 NTuple<Location> argLocationPath = deriveLocationTuple(mdCaller, arg);
942 NTuple<Descriptor> argHeapPath = computePath(arg);
943 addMayWrittenSet(mdCaller, argLocationPath, argHeapPath);
946 // if arg is not primitive type, we need to propagate maywritten set to
947 // the caller's location path
949 MethodDescriptor mdCallee = fc.getMethod();
950 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
951 setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
953 // create mapping from arg idx to its heap paths
954 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
955 new Hashtable<Integer, NTuple<Descriptor>>();
957 // create mapping from arg idx to its location paths
958 Hashtable<Integer, NTuple<Location>> mapArgIdx2CallerArgLocationPath =
959 new Hashtable<Integer, NTuple<Location>>();
961 // arg idx is starting from 'this' arg
962 if (fc.getThis() != null) {
963 // loc path for 'this'
964 NTuple<Location> thisLocationPath = deriveLocationTuple(mdCaller, fc.getThis());
965 if (thisLocationPath != null) {
966 mapArgIdx2CallerArgLocationPath.put(Integer.valueOf(0), thisLocationPath);
968 // heap path for 'this'
969 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
970 if (thisHeapPath == null) {
971 // method is called without creating new flat node representing
973 thisHeapPath = new NTuple<Descriptor>();
974 thisHeapPath.add(fc.getThis());
976 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
981 for (int i = 0; i < fc.numArgs(); i++) {
982 TempDescriptor arg = fc.getArg(i);
983 // create mapping arg to loc path
984 NTuple<Location> argLocationPath = deriveLocationTuple(mdCaller, arg);
985 if (argLocationPath != null) {
986 mapArgIdx2CallerArgLocationPath.put(Integer.valueOf(i + 1), argLocationPath);
987 // create mapping arg to heap path
988 NTuple<Descriptor> argHeapPath = computePath(arg);
989 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
994 Hashtable<Integer, Set<NTuple<Descriptor>>> mapParamIdx2WriteSet =
995 new Hashtable<Integer, Set<NTuple<Descriptor>>>();
997 for (int i = 0; i < fc.numArgs() + 1; i++) {
998 mapParamIdx2WriteSet.put(Integer.valueOf(i), new HashSet<NTuple<Descriptor>>());
1001 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1002 MethodDescriptor callee = (MethodDescriptor) iterator.next();
1003 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1005 // binding caller's args and callee's params
1007 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1008 new Hashtable<Integer, TempDescriptor>();
1010 if (calleeFlatMethod.getMethod().isStatic()) {
1011 // static method does not have implicit 'this' arg
1014 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1015 TempDescriptor param = calleeFlatMethod.getParameter(i);
1016 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
1019 Set<Integer> keySet = mapArgIdx2CallerArgLocationPath.keySet();
1020 for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
1021 Integer idx = (Integer) iterator2.next();
1022 NTuple<Location> callerArgLocationPath = mapArgIdx2CallerArgLocationPath.get(idx);
1024 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1026 NTuple<Descriptor> callerArgHeapPath = mapArgIdx2CallerArgHeapPath.get(idx);
1027 NTuple<Location> calleeLocationPath = deriveLocationTuple(mdCallee, calleeParam);
1028 NTuple<Descriptor> calleeHeapPath = computePath(calleeParam);
1030 createNewMappingOfMayWrittenSet(mdCaller, callee, callerArgHeapPath,
1031 callerArgLocationPath, calleeHeapPath, calleeLocationPath,
1032 mapParamIdx2WriteSet.get(idx));
1042 private Hashtable<NTuple<Location>, Set<NTuple<Descriptor>>> getMappingByStartedWith(
1043 MultiSourceMap<NTuple<Location>, NTuple<Descriptor>> map, NTuple<Location> in) {
1045 Hashtable<NTuple<Location>, Set<NTuple<Descriptor>>> matchedMapping =
1046 new Hashtable<NTuple<Location>, Set<NTuple<Descriptor>>>();
1048 Set<NTuple<Location>> keySet = map.keySet();
1050 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1051 NTuple<Location> key = (NTuple<Location>) iterator.next();
1052 if (key.startsWith(in)) {
1053 matchedMapping.put(key, map.get(key));
1057 return matchedMapping;
1061 private void createNewMappingOfMayWrittenSet(MethodDescriptor caller, MethodDescriptor callee,
1062 NTuple<Descriptor> callerArgHeapPath, NTuple<Location> callerArgLocPath,
1063 NTuple<Descriptor> calleeParamHeapPath, NTuple<Location> calleeParamLocPath,
1064 Set<NTuple<Descriptor>> writeSet) {
1066 // propagate may-written-set associated with the key that is started with
1067 // calleepath to the caller
1068 // 1) makes a new key by combining caller path and callee path(except local
1069 // loc element of param)
1070 // 2) create new mapping of may-written-set of callee path to caller path
1072 // extract all may written effect accessed through callee param path
1073 MultiSourceMap<NTuple<Location>, NTuple<Descriptor>> calleeMapping =
1074 mapMethodToSharedLocCoverSet.get(callee);
1076 MultiSourceMap<NTuple<Location>, NTuple<Descriptor>> callerMapping =
1077 mapMethodToSharedLocCoverSet.get(caller);
1079 if (callerMapping == null) {
1080 callerMapping = new MultiSourceMap<NTuple<Location>, NTuple<Descriptor>>();
1081 mapMethodToSharedLocCoverSet.put(caller, callerMapping);
1084 if (calleeMapping == null) {
1088 Hashtable<NTuple<Location>, Set<NTuple<Descriptor>>> paramMapping =
1089 getMappingByStartedWith(calleeMapping, calleeParamLocPath);
1091 Set<NTuple<Location>> calleeKeySet = calleeMapping.keySet();
1092 for (Iterator iterator = calleeKeySet.iterator(); iterator.hasNext();) {
1093 NTuple<Location> calleeKey = (NTuple<Location>) iterator.next();
1094 Set<NTuple<Descriptor>> calleeMayWriteSet = paramMapping.get(calleeKey);
1096 if (calleeMayWriteSet != null) {
1098 Set<NTuple<Descriptor>> boundWriteSet =
1099 convertCallerMayWriteSet(callerArgHeapPath, calleeParamHeapPath, calleeMayWriteSet);
1101 writeSet.addAll(boundWriteSet);
1103 NTuple<Location> newKey = new NTuple<Location>();
1104 newKey.addAll(callerArgLocPath);
1105 // need to replace the local location with the caller's path so skip the
1106 // local location of the parameter
1107 for (int i = 1; i < calleeKey.size(); i++) {
1108 newKey.add(calleeKey.get(i));
1111 callerMapping.union(newKey, writeSet);
1112 // mapLocationPathToMayWrittenSet.put(calleeKey, newKey, writeSet);
1119 private Set<NTuple<Descriptor>> convertCallerMayWriteSet(NTuple<Descriptor> callerArgHeapPath,
1120 NTuple<Descriptor> calleeParamHeapPath, Set<NTuple<Descriptor>> calleeMayWriteSet) {
1122 Set<NTuple<Descriptor>> boundSet = new HashSet<NTuple<Descriptor>>();
1124 // replace callee's param path with caller's arg path
1125 for (Iterator iterator = calleeMayWriteSet.iterator(); iterator.hasNext();) {
1126 NTuple<Descriptor> calleeWriteHeapPath = (NTuple<Descriptor>) iterator.next();
1128 NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
1129 boundHeapPath.addAll(callerArgHeapPath);
1131 int startIdx = calleeParamHeapPath.size();
1133 for (int i = startIdx; i < calleeWriteHeapPath.size(); i++) {
1134 boundHeapPath.add(calleeWriteHeapPath.get(i));
1137 boundSet.add(boundHeapPath);
1144 private void addSharedLocDescriptor(Location sharedLoc, Descriptor desc) {
1146 Set<Descriptor> descSet = mapSharedLocationToCoverSet.get(sharedLoc);
1147 if (descSet == null) {
1148 descSet = new HashSet<Descriptor>();
1149 mapSharedLocationToCoverSet.put(sharedLoc, descSet);
1156 private Location getLocation(Descriptor d) {
1158 if (d instanceof FieldDescriptor) {
1159 TypeExtension te = ((FieldDescriptor) d).getType().getExtension();
1161 return (Location) te;
1164 assert d instanceof TempDescriptor;
1165 TempDescriptor td = (TempDescriptor) d;
1167 TypeExtension te = td.getType().getExtension();
1169 if (te instanceof SSJavaType) {
1170 SSJavaType ssType = (SSJavaType) te;
1171 if (ssType.getCompLoc() != null) {
1172 CompositeLocation comp = ssType.getCompLoc();
1173 return comp.get(comp.getSize() - 1);
1178 return (Location) te;
1183 return mapDescToLocation.get(d);
1186 private void eventLoopAnalysis() {
1187 // perform second stage analysis: intraprocedural analysis ensure that
1189 // variables are definitely written in-between the same read
1191 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1192 flatNodesToVisit.add(ssjava.getSSJavaLoopEntrance());
1194 while (!flatNodesToVisit.isEmpty()) {
1195 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1196 flatNodesToVisit.remove(fn);
1198 Hashtable<NTuple<Descriptor>, Set<WriteAge>> prev = mapFlatNodetoEventLoopMap.get(fn);
1200 Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr =
1201 new Hashtable<NTuple<Descriptor>, Set<WriteAge>>();
1202 for (int i = 0; i < fn.numPrev(); i++) {
1203 FlatNode nn = fn.getPrev(i);
1204 Hashtable<NTuple<Descriptor>, Set<WriteAge>> in = mapFlatNodetoEventLoopMap.get(nn);
1210 eventLoopAnalysis_nodeAction(fn, curr, ssjava.getSSJavaLoopEntrance());
1212 // if a new result, schedule forward nodes for analysis
1213 if (!curr.equals(prev)) {
1214 mapFlatNodetoEventLoopMap.put(fn, curr);
1216 for (int i = 0; i < fn.numNext(); i++) {
1217 FlatNode nn = fn.getNext(i);
1218 if (loopIncElements.contains(nn)) {
1219 flatNodesToVisit.add(nn);
1227 private void union(Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1228 Hashtable<NTuple<Descriptor>, Set<WriteAge>> in) {
1230 Set<NTuple<Descriptor>> inKeySet = in.keySet();
1231 for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1232 NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1233 Set<WriteAge> inSet = in.get(inKey);
1235 Set<WriteAge> currSet = curr.get(inKey);
1237 if (currSet == null) {
1238 currSet = new HashSet<WriteAge>();
1239 curr.put(inKey, currSet);
1241 currSet.addAll(inSet);
1246 private void eventLoopAnalysis_nodeAction(FlatNode fn,
1247 Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr, FlatNode loopEntrance) {
1249 Hashtable<NTuple<Descriptor>, Set<WriteAge>> readWriteKillSet =
1250 new Hashtable<NTuple<Descriptor>, Set<WriteAge>>();
1251 Hashtable<NTuple<Descriptor>, Set<WriteAge>> readWriteGenSet =
1252 new Hashtable<NTuple<Descriptor>, Set<WriteAge>>();
1254 if (fn.equals(loopEntrance)) {
1255 // it reaches loop entrance: changes all flag to true
1256 Set<NTuple<Descriptor>> keySet = curr.keySet();
1257 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1258 NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
1259 Set<WriteAge> writeAgeSet = curr.get(key);
1261 Set<WriteAge> incSet = new HashSet<WriteAge>();
1262 incSet.addAll(writeAgeSet);
1263 writeAgeSet.clear();
1265 for (Iterator iterator2 = incSet.iterator(); iterator2.hasNext();) {
1266 WriteAge writeAge = (WriteAge) iterator2.next();
1267 WriteAge newWriteAge = writeAge.copy();
1269 writeAgeSet.add(newWriteAge);
1277 FieldDescriptor fld;
1279 switch (fn.kind()) {
1281 case FKind.FlatOpNode: {
1282 FlatOpNode fon = (FlatOpNode) fn;
1283 lhs = fon.getDest();
1284 rhs = fon.getLeft();
1286 if (fon.getOp().getOp() == Operation.ASSIGN) {
1288 if (!lhs.getSymbol().startsWith("neverused") && !lhs.getSymbol().startsWith("leftop")
1289 && !lhs.getSymbol().startsWith("rightop")) {
1291 boolean hasWriteEffect = false;
1292 NTuple<Descriptor> rhsHeapPath = computePath(rhs);
1294 if (rhs.getType().getExtension() instanceof SSJavaType
1295 && lhs.getType().getExtension() instanceof SSJavaType) {
1297 CompositeLocation rhsCompLoc =
1298 ((SSJavaType) rhs.getType().getExtension()).getCompLoc();
1300 CompositeLocation lhsCompLoc =
1301 ((SSJavaType) lhs.getType().getExtension()).getCompLoc();
1303 if (lhsCompLoc != rhsCompLoc) {
1304 // have a write effect!
1305 hasWriteEffect = true;
1308 } else if (lhs.getType().isImmutable()) {
1309 hasWriteEffect = true;
1312 if (hasWriteEffect) {
1314 NTuple<Descriptor> lhsPath = new NTuple<Descriptor>();
1316 Location lhsLoc = getLocation(lhs);
1317 if (ssjava.isSharedLocation(lhsLoc)) {
1319 NTuple<Descriptor> varHeapPath = computePath(lhs);
1320 NTuple<Location> varLocTuple = mapDescriptorToLocationPath.get(lhs);
1322 Set<NTuple<Descriptor>> writtenSet =
1323 mapFlatNodeToSharedLocMapping.get(fn).get(varLocTuple);
1325 if (isCovered(varLocTuple, writtenSet)) {
1326 computeKILLSetForSharedWrite(curr, writtenSet, readWriteKillSet);
1327 computeGENSetForSharedAllCoverWrite(curr, writtenSet, readWriteGenSet);
1329 computeGENSetForSharedNonCoverWrite(curr, varHeapPath, readWriteGenSet);
1334 computeKILLSetForWrite(curr, lhsPath, readWriteKillSet);
1335 computeGENSetForWrite(lhsPath, readWriteGenSet);
1338 // System.out.println("#KILLSET=" + readWriteKillSet);
1339 // System.out.println("#GENSet=" + readWriteGenSet + "\n");
1341 Set<WriteAge> writeAgeSet = curr.get(lhsPath);
1342 checkWriteAgeSet(writeAgeSet, lhsPath, fn);
1352 case FKind.FlatFieldNode:
1353 case FKind.FlatElementNode: {
1355 if (fn.kind() == FKind.FlatFieldNode) {
1356 FlatFieldNode ffn = (FlatFieldNode) fn;
1359 fld = ffn.getField();
1361 FlatElementNode fen = (FlatElementNode) fn;
1364 TypeDescriptor td = rhs.getType().dereference();
1365 fld = getArrayField(td);
1369 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1370 NTuple<Descriptor> fldHeapPath;
1371 if (srcHeapPath != null) {
1372 fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1374 // if srcHeapPath is null, it is static reference
1375 fldHeapPath = new NTuple<Descriptor>();
1376 fldHeapPath.add(rhs);
1378 fldHeapPath.add(fld);
1380 Set<WriteAge> writeAgeSet = curr.get(fldHeapPath);
1382 checkWriteAgeSet(writeAgeSet, fldHeapPath, fn);
1387 case FKind.FlatSetFieldNode:
1388 case FKind.FlatSetElementNode: {
1390 if (fn.kind() == FKind.FlatSetFieldNode) {
1391 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1392 lhs = fsfn.getDst();
1393 fld = fsfn.getField();
1395 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1396 lhs = fsen.getDst();
1397 rhs = fsen.getSrc();
1398 TypeDescriptor td = lhs.getType().dereference();
1399 fld = getArrayField(td);
1402 // System.out.println("FIELD WRITE:" + fn);
1405 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1406 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1407 fldHeapPath.add(fld);
1409 // shared loc extension
1410 Location fieldLoc = (Location) fld.getType().getExtension();
1411 if (ssjava.isSharedLocation(fieldLoc)) {
1413 NTuple<Location> fieldLocTuple = new NTuple<Location>();
1414 fieldLocTuple.addAll(mapDescriptorToLocationPath.get(lhs));
1415 fieldLocTuple.add(fieldLoc);
1417 Set<NTuple<Descriptor>> writtenSet =
1418 mapFlatNodeToSharedLocMapping.get(fn).get(fieldLocTuple);
1420 if (isCovered(fieldLocTuple, writtenSet)) {
1421 computeKILLSetForSharedWrite(curr, writtenSet, readWriteKillSet);
1422 computeGENSetForSharedAllCoverWrite(curr, writtenSet, readWriteGenSet);
1424 computeGENSetForSharedNonCoverWrite(curr, fldHeapPath, readWriteGenSet);
1428 computeKILLSetForWrite(curr, fldHeapPath, readWriteKillSet);
1429 computeGENSetForWrite(fldHeapPath, readWriteGenSet);
1432 // System.out.println("KILLSET=" + readWriteKillSet);
1433 // System.out.println("GENSet=" + readWriteGenSet);
1438 case FKind.FlatCall: {
1439 FlatCall fc = (FlatCall) fn;
1441 SharedLocMap sharedLocMap = mapFlatNodeToSharedLocMapping.get(fc);
1442 // System.out.println("FLATCALL:" + fn);
1443 generateKILLSetForFlatCall(fc, curr, sharedLocMap, readWriteKillSet);
1444 generateGENSetForFlatCall(fc, sharedLocMap, readWriteGenSet);
1446 // System.out.println("KILLSET=" + readWriteKillSet);
1447 // System.out.println("GENSet=" + readWriteGenSet);
1449 checkManyRead(fc, curr);
1455 computeNewMapping(curr, readWriteKillSet, readWriteGenSet);
1456 // System.out.println("#######" + curr);
1462 private void computeGENSetForSharedNonCoverWrite(
1463 Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr, NTuple<Descriptor> heapPath,
1464 Hashtable<NTuple<Descriptor>, Set<WriteAge>> genSet) {
1466 Set<WriteAge> writeAgeSet = genSet.get(heapPath);
1467 if (writeAgeSet == null) {
1468 writeAgeSet = new HashSet<WriteAge>();
1469 genSet.put(heapPath, writeAgeSet);
1472 writeAgeSet.add(new WriteAge(1));
1476 private void computeGENSetForSharedAllCoverWrite(
1477 Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr, Set<NTuple<Descriptor>> writtenSet,
1478 Hashtable<NTuple<Descriptor>, Set<WriteAge>> genSet) {
1480 for (Iterator iterator = writtenSet.iterator(); iterator.hasNext();) {
1481 NTuple<Descriptor> writeHeapPath = (NTuple<Descriptor>) iterator.next();
1483 Set<WriteAge> writeAgeSet = new HashSet<WriteAge>();
1484 writeAgeSet.add(new WriteAge(0));
1486 genSet.put(writeHeapPath, writeAgeSet);
1491 private void computeKILLSetForSharedWrite(Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1492 Set<NTuple<Descriptor>> writtenSet, Hashtable<NTuple<Descriptor>, Set<WriteAge>> killSet) {
1494 for (Iterator iterator = writtenSet.iterator(); iterator.hasNext();) {
1495 NTuple<Descriptor> writeHeapPath = (NTuple<Descriptor>) iterator.next();
1496 Set<WriteAge> writeSet = curr.get(writeHeapPath);
1497 if (writeSet != null) {
1498 killSet.put(writeHeapPath, writeSet);
1504 private boolean isCovered(NTuple<Location> locTuple, Set<NTuple<Descriptor>> inSet) {
1506 if (inSet == null) {
1510 Set<NTuple<Descriptor>> coverSet =
1511 mapMethodToSharedLocCoverSet.get(methodContainingSSJavaLoop).get(locTuple);
1513 return inSet.containsAll(coverSet);
1516 private void checkManyRead(FlatCall fc, Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr) {
1518 Set<NTuple<Descriptor>> boundReadSet = mapFlatNodeToBoundReadSet.get(fc);
1520 for (Iterator iterator = boundReadSet.iterator(); iterator.hasNext();) {
1521 NTuple<Descriptor> readHeapPath = (NTuple<Descriptor>) iterator.next();
1522 Set<WriteAge> writeAgeSet = curr.get(readHeapPath);
1523 checkWriteAgeSet(writeAgeSet, readHeapPath, fc);
1528 private void checkWriteAgeSet(Set<WriteAge> writeAgeSet, NTuple<Descriptor> path, FlatNode fn) {
1530 // System.out.println("# CHECK WRITE AGE of " + path + " from set=" +
1533 if (writeAgeSet != null) {
1534 for (Iterator iterator = writeAgeSet.iterator(); iterator.hasNext();) {
1535 WriteAge writeAge = (WriteAge) iterator.next();
1536 if (writeAge.getAge() > MAXAGE) {
1537 generateErrorMessage(path, fn);
1543 private void generateErrorMessage(NTuple<Descriptor> path, FlatNode fn) {
1545 Descriptor lastDesc = path.get(path.size() - 1);
1546 if (ssjava.isSharedLocation(getLocation(lastDesc))) {
1548 NTuple<Location> locPathTuple = getLocationTuple(path);
1549 Set<NTuple<Descriptor>> coverSet =
1550 mapMethodToSharedLocCoverSet.get(methodContainingSSJavaLoop).get(locPathTuple);
1551 throw new Error("Shared memory locations, which is reachable through references " + path
1552 + ", are not completely overwritten by the higher values at "
1553 + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::" + fn.getNumLine()
1554 + ".\nThe following memory locations belong to the same shared locations:" + coverSet);
1558 "Memory location, which is reachable through references "
1560 + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1561 + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1567 private void generateGENSetForFlatCall(FlatCall fc, SharedLocMap sharedLocMap,
1568 Hashtable<NTuple<Descriptor>, Set<WriteAge>> GENSet) {
1570 Set<NTuple<Descriptor>> boundMayWriteSet = mapFlatNodeToBoundMayWriteSet.get(fc);
1571 // System.out.println("boundMayWriteSet=" + boundMayWriteSet);
1573 for (Iterator iterator = boundMayWriteSet.iterator(); iterator.hasNext();) {
1574 NTuple<Descriptor> heapPath = (NTuple<Descriptor>) iterator.next();
1576 if (!isSharedLocation(heapPath)) {
1577 addWriteAgeToSet(heapPath, GENSet, new WriteAge(0));
1579 // if the current heap path is shared location
1581 NTuple<Location> locTuple = getLocationTuple(heapPath);
1583 Set<NTuple<Descriptor>> sharedWriteHeapPathSet = sharedLocMap.get(locTuple);
1585 if (isCovered(locTuple, sharedLocMap.get(locTuple))) {
1586 // if it is covered, add all of heap paths belong to the same shared
1587 // loc with write age 0
1589 for (Iterator iterator2 = sharedWriteHeapPathSet.iterator(); iterator2.hasNext();) {
1590 NTuple<Descriptor> sharedHeapPath = (NTuple<Descriptor>) iterator2.next();
1591 addWriteAgeToSet(sharedHeapPath, GENSet, new WriteAge(0));
1595 // if not covered, add write age 1 to the heap path that is
1596 // may-written but not covered
1597 addWriteAgeToSet(heapPath, GENSet, new WriteAge(1));
1606 private void addWriteAgeToSet(NTuple<Descriptor> heapPath,
1607 Hashtable<NTuple<Descriptor>, Set<WriteAge>> map, WriteAge age) {
1609 Set<WriteAge> currSet = map.get(heapPath);
1610 if (currSet == null) {
1611 currSet = new HashSet<WriteAge>();
1612 map.put(heapPath, currSet);
1618 private void generateKILLSetForFlatCall(FlatCall fc,
1619 Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr, SharedLocMap sharedLocMap,
1620 Hashtable<NTuple<Descriptor>, Set<WriteAge>> KILLSet) {
1622 Set<NTuple<Descriptor>> boundMustWriteSet = mapFlatNodeToBoundMustWriteSet.get(fc);
1623 // System.out.println("boundMustWriteSet=" + boundMustWriteSet);
1625 for (Iterator iterator = boundMustWriteSet.iterator(); iterator.hasNext();) {
1626 NTuple<Descriptor> heapPath = (NTuple<Descriptor>) iterator.next();
1628 if (isSharedLocation(heapPath)) {
1629 NTuple<Location> locTuple = getLocationTuple(heapPath);
1631 if (isCovered(locTuple, sharedLocMap.get(locTuple))) {
1632 // if it is shared loc and corresponding shared loc has been covered
1633 KILLSet.put(heapPath, curr.get(heapPath));
1636 if (curr.get(heapPath) != null) {
1637 KILLSet.put(heapPath, curr.get(heapPath));
1645 private int getArrayBaseDescriptorIdx(NTuple<Descriptor> heapPath) {
1647 for (int i = heapPath.size() - 1; i > 1; i--) {
1648 if (!heapPath.get(i).getSymbol().equals(arrayElementFieldName)) {
1657 private boolean isSharedLocation(NTuple<Descriptor> heapPath) {
1659 Descriptor d = heapPath.get(heapPath.size() - 1);
1661 if (d instanceof FieldDescriptor) {
1664 .isSharedLocation(getLocation(heapPath.get(getArrayBaseDescriptorIdx(heapPath))));
1667 return ssjava.isSharedLocation(getLocation(heapPath.get(heapPath.size() - 1)));
1671 private NTuple<Location> getLocationTuple(NTuple<Descriptor> heapPath) {
1673 NTuple<Location> locTuple = new NTuple<Location>();
1675 locTuple.addAll(mapDescriptorToLocationPath.get(heapPath.get(0)));
1677 for (int i = 1; i <= getArrayBaseDescriptorIdx(heapPath); i++) {
1678 locTuple.add(getLocation(heapPath.get(i)));
1684 private void computeNewMapping(Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1685 Hashtable<NTuple<Descriptor>, Set<WriteAge>> KILLSet,
1686 Hashtable<NTuple<Descriptor>, Set<WriteAge>> GENSet) {
1688 for (Enumeration<NTuple<Descriptor>> e = KILLSet.keys(); e.hasMoreElements();) {
1689 NTuple<Descriptor> key = e.nextElement();
1691 Set<WriteAge> writeAgeSet = curr.get(key);
1692 if (writeAgeSet == null) {
1693 writeAgeSet = new HashSet<WriteAge>();
1694 curr.put(key, writeAgeSet);
1696 writeAgeSet.removeAll(KILLSet.get(key));
1699 for (Enumeration<NTuple<Descriptor>> e = GENSet.keys(); e.hasMoreElements();) {
1700 NTuple<Descriptor> key = e.nextElement();
1702 Set<WriteAge> currWriteAgeSet = curr.get(key);
1703 if (currWriteAgeSet == null) {
1704 currWriteAgeSet = new HashSet<WriteAge>();
1705 curr.put(key, currWriteAgeSet);
1707 currWriteAgeSet.addAll(GENSet.get(key));
1712 private void computeGENSetForWrite(NTuple<Descriptor> fldHeapPath,
1713 Hashtable<NTuple<Descriptor>, Set<WriteAge>> GENSet) {
1715 // generate write age 0 for the field being written to
1716 Set<WriteAge> writeAgeSet = new HashSet<WriteAge>();
1717 writeAgeSet.add(new WriteAge(0));
1718 GENSet.put(fldHeapPath, writeAgeSet);
1722 private void computeKILLSetForWrite(Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1723 NTuple<Descriptor> hp, Hashtable<NTuple<Descriptor>, Set<WriteAge>> KILLSet) {
1725 // removes all of heap path that starts with prefix 'hp'
1726 // since any reference overwrite along heap path gives overwriting side
1727 // effects on the value
1729 Set<NTuple<Descriptor>> keySet = curr.keySet();
1730 for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
1731 NTuple<Descriptor> key = iter.next();
1732 if (key.startsWith(hp)) {
1733 KILLSet.put(key, curr.get(key));
1739 private void bindHeapPathCallerArgWithCalleeParam(FlatCall fc) {
1740 // compute all possible callee set
1741 // transform all READ/WRITE set from the any possible
1742 // callees to the caller
1743 calleeUnionBoundReadSet.clear();
1744 calleeIntersectBoundMustWriteSet.clear();
1745 calleeUnionBoundMayWriteSet.clear();
1747 if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
1748 // ssjava util case!
1749 // have write effects on the first argument
1750 TempDescriptor arg = fc.getArg(0);
1751 NTuple<Descriptor> argHeapPath = computePath(arg);
1752 calleeIntersectBoundMustWriteSet.add(argHeapPath);
1753 calleeUnionBoundMayWriteSet.add(argHeapPath);
1755 MethodDescriptor mdCallee = fc.getMethod();
1756 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1757 setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1759 // create mapping from arg idx to its heap paths
1760 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1761 new Hashtable<Integer, NTuple<Descriptor>>();
1763 // arg idx is starting from 'this' arg
1764 if (fc.getThis() != null) {
1765 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1766 if (thisHeapPath == null) {
1767 // method is called without creating new flat node representing 'this'
1768 thisHeapPath = new NTuple<Descriptor>();
1769 thisHeapPath.add(fc.getThis());
1772 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1775 for (int i = 0; i < fc.numArgs(); i++) {
1776 TempDescriptor arg = fc.getArg(i);
1777 NTuple<Descriptor> argHeapPath = computePath(arg);
1778 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1781 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1782 MethodDescriptor callee = (MethodDescriptor) iterator.next();
1783 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1785 // binding caller's args and callee's params
1787 Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToReadSet.get(calleeFlatMethod);
1788 if (calleeReadSet == null) {
1789 calleeReadSet = new HashSet<NTuple<Descriptor>>();
1790 mapFlatMethodToReadSet.put(calleeFlatMethod, calleeReadSet);
1793 Set<NTuple<Descriptor>> calleeMustWriteSet =
1794 mapFlatMethodToMustWriteSet.get(calleeFlatMethod);
1796 if (calleeMustWriteSet == null) {
1797 calleeMustWriteSet = new HashSet<NTuple<Descriptor>>();
1798 mapFlatMethodToMustWriteSet.put(calleeFlatMethod, calleeMustWriteSet);
1801 Set<NTuple<Descriptor>> calleeMayWriteSet =
1802 mapFlatMethodToMayWriteSet.get(calleeFlatMethod);
1804 if (calleeMayWriteSet == null) {
1805 calleeMayWriteSet = new HashSet<NTuple<Descriptor>>();
1806 mapFlatMethodToMayWriteSet.put(calleeFlatMethod, calleeMayWriteSet);
1809 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1810 new Hashtable<Integer, TempDescriptor>();
1812 if (calleeFlatMethod.getMethod().isStatic()) {
1813 // static method does not have implicit 'this' arg
1816 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1817 TempDescriptor param = calleeFlatMethod.getParameter(i);
1818 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
1821 Set<NTuple<Descriptor>> calleeBoundReadSet =
1822 bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1823 // union of the current read set and the current callee's
1825 calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1827 Set<NTuple<Descriptor>> calleeBoundMustWriteSet =
1828 bindSet(calleeMustWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1829 // intersection of the current overwrite set and the current
1832 merge(calleeIntersectBoundMustWriteSet, calleeBoundMustWriteSet);
1834 Set<NTuple<Descriptor>> boundWriteSetFromCallee =
1835 bindSet(calleeMayWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1836 calleeUnionBoundMayWriteSet.addAll(boundWriteSetFromCallee);
1843 private void bindHeapPathCallerArgWithCaleeParamForSharedLoc(MethodDescriptor mdCaller,
1846 calleeIntersectBoundSharedSet.clear();
1847 calleeUnionBoundDeleteSet.clear();
1849 // if arg is not primitive type, we need to propagate maywritten set to
1850 // the caller's location path
1852 MethodDescriptor mdCallee = fc.getMethod();
1853 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1854 setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1856 // create mapping from arg idx to its heap paths
1857 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1858 new Hashtable<Integer, NTuple<Descriptor>>();
1860 // arg idx is starting from 'this' arg
1861 if (fc.getThis() != null) {
1862 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1863 if (thisHeapPath == null) {
1864 // method is called without creating new flat node representing 'this'
1865 thisHeapPath = new NTuple<Descriptor>();
1866 thisHeapPath.add(fc.getThis());
1869 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1872 for (int i = 0; i < fc.numArgs(); i++) {
1873 TempDescriptor arg = fc.getArg(i);
1874 NTuple<Descriptor> argHeapPath = computePath(arg);
1875 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1878 // create mapping from arg idx to its location paths
1879 Hashtable<Integer, NTuple<Location>> mapArgIdx2CallerAgLocationPath =
1880 new Hashtable<Integer, NTuple<Location>>();
1882 // arg idx is starting from 'this' arg
1883 if (fc.getThis() != null) {
1884 NTuple<Location> thisLocationPath = deriveLocationTuple(mdCaller, fc.getThis());
1885 mapArgIdx2CallerAgLocationPath.put(Integer.valueOf(0), thisLocationPath);
1888 for (int i = 0; i < fc.numArgs(); i++) {
1889 TempDescriptor arg = fc.getArg(i);
1890 NTuple<Location> argLocationPath = deriveLocationTuple(mdCaller, arg);
1891 if (argLocationPath != null) {
1892 mapArgIdx2CallerAgLocationPath.put(Integer.valueOf(i + 1), argLocationPath);
1896 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1897 MethodDescriptor callee = (MethodDescriptor) iterator.next();
1898 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1900 // binding caller's args and callee's params
1902 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1903 new Hashtable<Integer, TempDescriptor>();
1905 if (calleeFlatMethod.getMethod().isStatic()) {
1906 // static method does not have implicit 'this' arg
1909 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1910 TempDescriptor param = calleeFlatMethod.getParameter(i);
1911 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
1914 Set<Integer> keySet = mapArgIdx2CallerAgLocationPath.keySet();
1915 for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
1916 Integer idx = (Integer) iterator2.next();
1917 NTuple<Location> callerArgLocationPath = mapArgIdx2CallerAgLocationPath.get(idx);
1918 NTuple<Descriptor> callerArgHeapPath = mapArgIdx2CallerArgHeapPath.get(idx);
1920 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1921 NTuple<Location> calleeLocationPath = deriveLocationTuple(mdCallee, calleeParam);
1922 SharedLocMap calleeDeleteSet = mapFlatMethodToDeleteSet.get(calleeFlatMethod);
1923 SharedLocMap calleeSharedLocMap = mapFlatMethodToSharedLocMap.get(calleeFlatMethod);
1925 if (calleeDeleteSet != null) {
1926 createNewMappingOfDeleteSet(callerArgLocationPath, callerArgHeapPath, calleeLocationPath,
1930 if (calleeSharedLocMap != null) {
1931 createNewMappingOfSharedSet(callerArgLocationPath, callerArgHeapPath, calleeLocationPath,
1932 calleeSharedLocMap);
1941 private void createNewMappingOfDeleteSet(NTuple<Location> callerArgLocationPath,
1942 NTuple<Descriptor> callerArgHeapPath, NTuple<Location> calleeLocationPath,
1943 SharedLocMap calleeDeleteSet) {
1945 SharedLocMap calleeParamDeleteSet = calleeDeleteSet.getHeapPathStartedWith(calleeLocationPath);
1947 Set<NTuple<Location>> keySet = calleeParamDeleteSet.keySet();
1948 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1949 NTuple<Location> calleeLocTupleKey = (NTuple<Location>) iterator.next();
1950 Set<NTuple<Descriptor>> heapPathSet = calleeParamDeleteSet.get(calleeLocTupleKey);
1951 for (Iterator iterator2 = heapPathSet.iterator(); iterator2.hasNext();) {
1952 NTuple<Descriptor> calleeHeapPath = (NTuple<Descriptor>) iterator2.next();
1953 calleeUnionBoundDeleteSet.addWrite(
1954 bindLocationPath(callerArgLocationPath, calleeLocTupleKey),
1955 bindHeapPath(callerArgHeapPath, calleeHeapPath));
1961 private void createNewMappingOfSharedSet(NTuple<Location> callerArgLocationPath,
1962 NTuple<Descriptor> callerArgHeapPath, NTuple<Location> calleeLocationPath,
1963 SharedLocMap calleeSharedLocMap) {
1965 SharedLocMap calleeParamSharedSet =
1966 calleeSharedLocMap.getHeapPathStartedWith(calleeLocationPath);
1968 Set<NTuple<Location>> keySet = calleeParamSharedSet.keySet();
1969 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1970 NTuple<Location> calleeLocTupleKey = (NTuple<Location>) iterator.next();
1971 Set<NTuple<Descriptor>> heapPathSet = calleeParamSharedSet.get(calleeLocTupleKey);
1972 Set<NTuple<Descriptor>> boundHeapPathSet = new HashSet<NTuple<Descriptor>>();
1973 for (Iterator iterator2 = heapPathSet.iterator(); iterator2.hasNext();) {
1974 NTuple<Descriptor> calleeHeapPath = (NTuple<Descriptor>) iterator2.next();
1975 boundHeapPathSet.add(bindHeapPath(callerArgHeapPath, calleeHeapPath));
1977 calleeIntersectBoundSharedSet.intersect(
1978 bindLocationPath(callerArgLocationPath, calleeLocTupleKey), boundHeapPathSet);
1983 private NTuple<Location> bindLocationPath(NTuple<Location> start, NTuple<Location> end) {
1984 NTuple<Location> locPath = new NTuple<Location>();
1985 locPath.addAll(start);
1986 for (int i = 1; i < end.size(); i++) {
1987 locPath.add(end.get(i));
1992 private NTuple<Descriptor> bindHeapPath(NTuple<Descriptor> start, NTuple<Descriptor> end) {
1993 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1994 heapPath.addAll(start);
1995 for (int i = 1; i < end.size(); i++) {
1996 heapPath.add(end.get(i));
2001 private void initialize() {
2002 // First, identify ssjava loop entrace
2004 // no need to analyze method having ssjava loop
2005 methodContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop();
2007 FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
2008 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
2009 flatNodesToVisit.add(fm);
2011 LoopFinder loopFinder = new LoopFinder(fm);
2013 while (!flatNodesToVisit.isEmpty()) {
2014 FlatNode fn = flatNodesToVisit.iterator().next();
2015 flatNodesToVisit.remove(fn);
2017 String label = (String) state.fn2labelMap.get(fn);
2018 if (label != null) {
2020 if (label.equals(ssjava.SSJAVA)) {
2021 ssjava.setSSJavaLoopEntrance(fn);
2026 for (int i = 0; i < fn.numNext(); i++) {
2027 FlatNode nn = fn.getNext(i);
2028 flatNodesToVisit.add(nn);
2032 assert ssjava.getSSJavaLoopEntrance() != null;
2034 // assume that ssjava loop is top-level loop in method, not nested loop
2035 Set nestedLoop = loopFinder.nestedLoops();
2036 for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
2037 LoopFinder lf = (LoopFinder) loopIter.next();
2038 if (lf.loopEntrances().iterator().next().equals(ssjava.getSSJavaLoopEntrance())) {
2043 assert ssjavaLoop != null;
2045 loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
2047 // perform topological sort over the set of methods accessed by the main
2049 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
2050 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
2051 sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
2054 private void methodReadWriteSetAnalysis() {
2055 // perform method READ/OVERWRITE analysis
2056 LinkedList<MethodDescriptor> descriptorListToAnalyze =
2057 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
2059 // current descriptors to visit in fixed-point interprocedural analysis,
2061 // dependency in the call graph
2062 methodDescriptorsToVisitStack.clear();
2064 descriptorListToAnalyze.removeFirst();
2066 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
2067 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
2069 while (!descriptorListToAnalyze.isEmpty()) {
2070 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
2071 methodDescriptorsToVisitStack.add(md);
2074 // analyze scheduled methods until there are no more to visit
2075 while (!methodDescriptorsToVisitStack.isEmpty()) {
2076 // start to analyze leaf node
2077 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
2078 FlatMethod fm = state.getMethodFlat(md);
2080 Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
2081 Set<NTuple<Descriptor>> mustWriteSet = new HashSet<NTuple<Descriptor>>();
2082 Set<NTuple<Descriptor>> mayWriteSet = new HashSet<NTuple<Descriptor>>();
2084 methodReadWriteSet_analyzeMethod(fm, readSet, mustWriteSet, mayWriteSet);
2086 Set<NTuple<Descriptor>> prevRead = mapFlatMethodToReadSet.get(fm);
2087 Set<NTuple<Descriptor>> prevMustWrite = mapFlatMethodToMustWriteSet.get(fm);
2088 Set<NTuple<Descriptor>> prevMayWrite = mapFlatMethodToMayWriteSet.get(fm);
2090 if (!(readSet.equals(prevRead) && mustWriteSet.equals(prevMustWrite) && mayWriteSet
2091 .equals(prevMayWrite))) {
2092 mapFlatMethodToReadSet.put(fm, readSet);
2093 mapFlatMethodToMustWriteSet.put(fm, mustWriteSet);
2094 mapFlatMethodToMayWriteSet.put(fm, mayWriteSet);
2096 // results for callee changed, so enqueue dependents caller for
2099 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
2100 while (depsItr.hasNext()) {
2101 MethodDescriptor methodNext = depsItr.next();
2102 if (!methodDescriptorsToVisitStack.contains(methodNext)
2103 && methodDescriptorToVistSet.contains(methodNext)) {
2104 methodDescriptorsToVisitStack.add(methodNext);
2113 methodReadWriteSetAnalysisToEventLoopBody();
2117 private void methodReadWriteSet_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
2118 Set<NTuple<Descriptor>> mustWriteSet, Set<NTuple<Descriptor>> mayWriteSet) {
2119 if (state.SSJAVADEBUG) {
2120 System.out.println("SSJAVA: Definitely written Analyzing: " + fm);
2123 methodReadWriteSet_analyzeBody(fm, readSet, mustWriteSet, mayWriteSet, false);
2127 private void methodReadWriteSetAnalysisToEventLoopBody() {
2129 // perform method read/write analysis for Event Loop Body
2131 FlatMethod flatMethodContainingSSJavaLoop = state.getMethodFlat(methodContainingSSJavaLoop);
2133 if (state.SSJAVADEBUG) {
2134 System.out.println("SSJAVA: Definitely written Event Loop Analyzing: "
2135 + flatMethodContainingSSJavaLoop);
2138 Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
2139 Set<NTuple<Descriptor>> mustWriteSet = new HashSet<NTuple<Descriptor>>();
2140 Set<NTuple<Descriptor>> mayWriteSet = new HashSet<NTuple<Descriptor>>();
2142 mapFlatMethodToReadSet.put(flatMethodContainingSSJavaLoop, readSet);
2143 mapFlatMethodToMustWriteSet.put(flatMethodContainingSSJavaLoop, mustWriteSet);
2144 mapFlatMethodToMayWriteSet.put(flatMethodContainingSSJavaLoop, mayWriteSet);
2146 methodReadWriteSet_analyzeBody(ssjava.getSSJavaLoopEntrance(), readSet, mustWriteSet,
2151 private void methodReadWriteSet_analyzeBody(FlatNode startNode, Set<NTuple<Descriptor>> readSet,
2152 Set<NTuple<Descriptor>> mustWriteSet, Set<NTuple<Descriptor>> mayWriteSet,
2153 boolean isEventLoopBody) {
2155 // intraprocedural analysis
2156 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
2157 flatNodesToVisit.add(startNode);
2159 while (!flatNodesToVisit.isEmpty()) {
2160 FlatNode fn = flatNodesToVisit.iterator().next();
2161 flatNodesToVisit.remove(fn);
2163 Set<NTuple<Descriptor>> currMustWriteSet = new HashSet<NTuple<Descriptor>>();
2165 for (int i = 0; i < fn.numPrev(); i++) {
2166 FlatNode prevFn = fn.getPrev(i);
2167 Set<NTuple<Descriptor>> in = mapFlatNodeToMustWriteSet.get(prevFn);
2169 merge(currMustWriteSet, in);
2173 methodReadWriteSet_nodeActions(fn, currMustWriteSet, readSet, mustWriteSet, mayWriteSet,
2176 Set<NTuple<Descriptor>> mustSetPrev = mapFlatNodeToMustWriteSet.get(fn);
2178 if (!currMustWriteSet.equals(mustSetPrev)) {
2179 mapFlatNodeToMustWriteSet.put(fn, currMustWriteSet);
2180 for (int i = 0; i < fn.numNext(); i++) {
2181 FlatNode nn = fn.getNext(i);
2182 if ((!isEventLoopBody) || loopIncElements.contains(nn)) {
2183 flatNodesToVisit.add(nn);
2193 private void methodReadWriteSet_nodeActions(FlatNode fn,
2194 Set<NTuple<Descriptor>> currMustWriteSet, Set<NTuple<Descriptor>> readSet,
2195 Set<NTuple<Descriptor>> mustWriteSet, Set<NTuple<Descriptor>> mayWriteSet,
2196 boolean isEventLoopBody) {
2200 FieldDescriptor fld;
2202 switch (fn.kind()) {
2203 case FKind.FlatMethod: {
2205 // set up initial heap paths for method parameters
2206 FlatMethod fm = (FlatMethod) fn;
2207 for (int i = 0; i < fm.numParameters(); i++) {
2208 TempDescriptor param = fm.getParameter(i);
2209 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
2210 heapPath.add(param);
2211 mapHeapPath.put(param, heapPath);
2216 case FKind.FlatOpNode: {
2217 FlatOpNode fon = (FlatOpNode) fn;
2218 // for a normal assign node, need to propagate lhs's heap path to
2221 if (fon.getOp().getOp() == Operation.ASSIGN) {
2222 rhs = fon.getLeft();
2223 lhs = fon.getDest();
2225 NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
2227 if (lhs.getType().isPrimitive()) {
2228 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
2229 lhsHeapPath.add(lhs);
2230 mapHeapPath.put(lhs, lhsHeapPath);
2231 } else if (rhsHeapPath != null) {
2232 mapHeapPath.put(lhs, mapHeapPath.get(rhs));
2234 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
2236 mapHeapPath.put(lhs, heapPath);
2239 // shared loc extension
2240 if (isEventLoopBody) {
2241 if (!lhs.getSymbol().startsWith("neverused") && rhs.getType().isImmutable()) {
2243 if (rhs.getType().getExtension() instanceof Location
2244 && lhs.getType().getExtension() instanceof CompositeLocation) {
2246 Location rhsLoc = (Location) rhs.getType().getExtension();
2248 CompositeLocation lhsCompLoc = (CompositeLocation) lhs.getType().getExtension();
2249 Location dstLoc = lhsCompLoc.get(lhsCompLoc.getSize() - 1);
2251 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
2252 for (int i = 0; i < rhsHeapPath.size() - 1; i++) {
2253 heapPath.add(rhsHeapPath.get(i));
2256 NTuple<Descriptor> writeHeapPath = new NTuple<Descriptor>();
2257 writeHeapPath.addAll(heapPath);
2258 writeHeapPath.add(lhs);
2268 case FKind.FlatElementNode:
2269 case FKind.FlatFieldNode: {
2273 if (fn.kind() == FKind.FlatFieldNode) {
2274 FlatFieldNode ffn = (FlatFieldNode) fn;
2277 fld = ffn.getField();
2279 FlatElementNode fen = (FlatElementNode) fn;
2282 TypeDescriptor td = rhs.getType().dereference();
2283 fld = getArrayField(td);
2286 if (fld.isFinal()) {
2287 // if field is final no need to check
2292 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
2293 if (srcHeapPath != null) {
2294 // if lhs srcHeapPath is null, it means that it is not reachable from
2295 // callee's parameters. so just ignore it
2297 NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
2298 readingHeapPath.add(fld);
2299 mapHeapPath.put(lhs, readingHeapPath);
2302 if (fld.getType().isImmutable()) {
2303 // if WT doesnot have hp(x.f), add hp(x.f) to READ
2304 if (!currMustWriteSet.contains(readingHeapPath)) {
2305 readSet.add(readingHeapPath);
2309 // no need to kill hp(x.f) from WT
2315 case FKind.FlatSetFieldNode:
2316 case FKind.FlatSetElementNode: {
2320 if (fn.kind() == FKind.FlatSetFieldNode) {
2321 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
2322 lhs = fsfn.getDst();
2323 fld = fsfn.getField();
2324 rhs = fsfn.getSrc();
2326 FlatSetElementNode fsen = (FlatSetElementNode) fn;
2327 lhs = fsen.getDst();
2328 rhs = fsen.getSrc();
2329 TypeDescriptor td = lhs.getType().dereference();
2330 fld = getArrayField(td);
2334 NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
2336 if (lhsHeapPath != null) {
2337 // if lhs heap path is null, it means that it is not reachable from
2338 // callee's parameters. so just ignore it
2339 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
2340 fldHeapPath.add(fld);
2341 mapHeapPath.put(fld, fldHeapPath);
2344 // need to add hp(y) to WT
2345 currMustWriteSet.add(fldHeapPath);
2346 mayWriteSet.add(fldHeapPath);
2353 case FKind.FlatCall: {
2355 FlatCall fc = (FlatCall) fn;
2357 bindHeapPathCallerArgWithCalleeParam(fc);
2359 Set<NTuple<Descriptor>> boundReadSet = new HashSet<NTuple<Descriptor>>();
2360 boundReadSet.addAll(calleeUnionBoundReadSet);
2362 Set<NTuple<Descriptor>> boundMustWriteSet = new HashSet<NTuple<Descriptor>>();
2363 boundMustWriteSet.addAll(calleeIntersectBoundMustWriteSet);
2365 Set<NTuple<Descriptor>> boundMayWriteSet = new HashSet<NTuple<Descriptor>>();
2366 boundMayWriteSet.addAll(calleeUnionBoundMayWriteSet);
2368 mapFlatNodeToBoundReadSet.put(fn, boundReadSet);
2369 mapFlatNodeToBoundMustWriteSet.put(fn, boundMustWriteSet);
2370 mapFlatNodeToBoundMayWriteSet.put(fn, boundMayWriteSet);
2372 // add heap path, which is an element of READ_bound set and is not
2374 // element of WT set, to the caller's READ set
2375 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
2376 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
2377 if (!currMustWriteSet.contains(read)) {
2382 // add heap path, which is an element of OVERWRITE_bound set, to the
2384 for (Iterator iterator = calleeIntersectBoundMustWriteSet.iterator(); iterator.hasNext();) {
2385 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
2386 currMustWriteSet.add(write);
2389 // add heap path, which is an element of WRITE_BOUND set, to the
2390 // caller's writeSet
2391 for (Iterator iterator = calleeUnionBoundMayWriteSet.iterator(); iterator.hasNext();) {
2392 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
2393 mayWriteSet.add(write);
2399 case FKind.FlatExit: {
2400 // merge the current written set with OVERWRITE set
2401 merge(mustWriteSet, currMustWriteSet);
2409 static public FieldDescriptor getArrayField(TypeDescriptor td) {
2410 FieldDescriptor fd = mapTypeToArrayField.get(td);
2413 new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), td, arrayElementFieldName, null,
2415 mapTypeToArrayField.put(td, fd);
2420 private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
2421 if (curr.isEmpty()) {
2422 // set has a special initial value which covers all possible
2424 // For the first time of intersection, we can take all previous set
2427 // otherwise, current set is the intersection of the two sets
2433 // combine two heap path
2434 private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
2435 NTuple<Descriptor> combined = new NTuple<Descriptor>();
2437 for (int i = 0; i < callerIn.size(); i++) {
2438 combined.add(callerIn.get(i));
2441 // the first element of callee's heap path represents parameter
2442 // so we skip the first one since it is already added from caller's heap
2444 for (int i = 1; i < calleeIn.size(); i++) {
2445 combined.add(calleeIn.get(i));
2451 private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
2452 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
2453 Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
2455 Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
2457 Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
2458 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2459 Integer idx = (Integer) iterator.next();
2461 NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
2462 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
2463 for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
2464 NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
2465 if (element.startsWith(calleeParam)) {
2466 NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
2467 boundedCalleeSet.add(boundElement);
2473 return boundedCalleeSet;
2477 // Borrowed it from disjoint analysis
2478 private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
2480 Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
2482 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
2484 Iterator<MethodDescriptor> itr = toSort.iterator();
2485 while (itr.hasNext()) {
2486 MethodDescriptor d = itr.next();
2488 if (!discovered.contains(d)) {
2489 dfsVisit(d, toSort, sorted, discovered);
2496 // While we're doing DFS on call graph, remember
2497 // dependencies for efficient queuing of methods
2498 // during interprocedural analysis:
2500 // a dependent of a method decriptor d for this analysis is:
2501 // 1) a method or task that invokes d
2502 // 2) in the descriptorsToAnalyze set
2503 private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
2504 LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
2508 Iterator itr = callGraph.getCallerSet(md).iterator();
2509 while (itr.hasNext()) {
2510 MethodDescriptor dCaller = (MethodDescriptor) itr.next();
2511 // only consider callers in the original set to analyze
2512 if (!toSort.contains(dCaller)) {
2515 if (!discovered.contains(dCaller)) {
2516 addDependent(md, // callee
2520 dfsVisit(dCaller, toSort, sorted, discovered);
2524 // for leaf-nodes last now!
2528 // a dependent of a method decriptor d for this analysis is:
2529 // 1) a method or task that invokes d
2530 // 2) in the descriptorsToAnalyze set
2531 private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
2532 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2534 deps = new HashSet<MethodDescriptor>();
2537 mapDescriptorToSetDependents.put(callee, deps);
2540 private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
2541 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2543 deps = new HashSet<MethodDescriptor>();
2544 mapDescriptorToSetDependents.put(callee, deps);
2549 private NTuple<Descriptor> computePath(Descriptor td) {
2550 // generate proper path fot input td
2551 // if td is local variable, it just generate one element tuple path
2552 if (mapHeapPath.containsKey(td)) {
2553 NTuple<Descriptor> rtrHeapPath = new NTuple<Descriptor>();
2554 rtrHeapPath.addAll(mapHeapPath.get(td));
2557 NTuple<Descriptor> rtrHeapPath = new NTuple<Descriptor>();
2558 rtrHeapPath.add(td);
2563 private NTuple<Location> deriveThisLocationTuple(MethodDescriptor md) {
2564 String thisLocIdentifier = ssjava.getMethodLattice(md).getThisLoc();
2565 Location thisLoc = new Location(md, thisLocIdentifier);
2566 NTuple<Location> locTuple = new NTuple<Location>();
2567 locTuple.add(thisLoc);
2571 private NTuple<Location> deriveGlobalLocationTuple(MethodDescriptor md) {
2572 String globalLocIdentifier = ssjava.getMethodLattice(md).getGlobalLoc();
2573 Location globalLoc = new Location(md, globalLocIdentifier);
2574 NTuple<Location> locTuple = new NTuple<Location>();
2575 locTuple.add(globalLoc);
2579 private NTuple<Location> deriveLocationTuple(MethodDescriptor md, TempDescriptor td) {
2581 assert td.getType() != null;
2583 if (mapDescriptorToLocationPath.containsKey(td)) {
2584 NTuple<Location> locPath = mapDescriptorToLocationPath.get(td);
2585 NTuple<Location> rtrPath = new NTuple<Location>();
2586 rtrPath.addAll(locPath);
2589 if (td.getSymbol().startsWith("this")) {
2590 NTuple<Location> thisPath = deriveThisLocationTuple(md);
2592 NTuple<Location> rtrPath = new NTuple<Location>();
2593 rtrPath.addAll(thisPath);
2598 if (td.getType().getExtension() != null) {
2599 SSJavaType ssJavaType = (SSJavaType) td.getType().getExtension();
2600 if (ssJavaType.getCompLoc() != null) {
2601 NTuple<Location> rtrPath = new NTuple<Location>();
2602 rtrPath.addAll(ssJavaType.getCompLoc().getTuple());