1 package Analysis.SSJava;
3 import java.util.HashSet;
4 import java.util.Hashtable;
5 import java.util.Iterator;
6 import java.util.LinkedList;
8 import java.util.Stack;
10 import Analysis.CallGraph.CallGraph;
12 import IR.FieldDescriptor;
13 import IR.MethodDescriptor;
16 import IR.TypeDescriptor;
18 import IR.Flat.FlatCall;
19 import IR.Flat.FlatFieldNode;
20 import IR.Flat.FlatLiteralNode;
21 import IR.Flat.FlatMethod;
22 import IR.Flat.FlatNode;
23 import IR.Flat.FlatOpNode;
24 import IR.Flat.FlatSetFieldNode;
25 import IR.Flat.TempDescriptor;
27 public class DefinitelyWrittenCheck {
29 SSJavaAnalysis ssjava;
33 // maps a descriptor to its known dependents: namely
34 // methods or tasks that call the descriptor's method
35 // AND are part of this analysis (reachable from main)
36 private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
38 // maps a flat node to its WrittenSet: this keeps all heap path overwritten
40 private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
42 // maps a temp descriptor to its heap path
43 // each temp descriptor has a unique heap path since we do not allow any
45 private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
47 // maps a flat method to the READ that is the set of heap path that is
48 // expected to be written before method invocation
49 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
51 // maps a flat method to the OVERWRITE that is the set of heap path that is
52 // overwritten on every possible path during method invocation
53 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
55 // points to method containing SSJAVA Loop
56 private MethodDescriptor methodContainingSSJavaLoop;
58 // maps a flatnode to definitely written analysis mapping M
59 private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
61 private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
62 private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
64 public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
67 this.callGraph = ssjava.getCallGraph();
68 this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
69 this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
70 this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
71 this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
72 this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
73 this.definitelyWrittenResults =
74 new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
75 this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
76 this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
79 public void definitelyWrittenCheck() {
80 if (!ssjava.getAnnotationRequireSet().isEmpty()) {
81 methodReadOverWriteAnalysis();
86 private void writtenAnalyis() {
87 // perform second stage analysis: intraprocedural analysis ensure that
89 // variables are definitely written in-between the same read
91 // First, identify ssjava loop entrace
92 FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
93 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
94 flatNodesToVisit.add(fm);
96 FlatNode entrance = null;
98 while (!flatNodesToVisit.isEmpty()) {
99 FlatNode fn = flatNodesToVisit.iterator().next();
100 flatNodesToVisit.remove(fn);
102 String label = (String) state.fn2labelMap.get(fn);
105 if (label.equals(ssjava.SSJAVA)) {
111 for (int i = 0; i < fn.numNext(); i++) {
112 FlatNode nn = fn.getNext(i);
113 flatNodesToVisit.add(nn);
117 assert entrance != null;
119 writtenAnalysis_analyzeLoop(entrance);
123 private void writtenAnalysis_analyzeLoop(FlatNode entrance) {
125 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
126 flatNodesToVisit.add(entrance);
128 while (!flatNodesToVisit.isEmpty()) {
129 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
130 flatNodesToVisit.remove(fn);
132 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
133 definitelyWrittenResults.get(fn);
135 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
136 new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
137 for (int i = 0; i < fn.numPrev(); i++) {
138 FlatNode nn = fn.getPrev(i);
139 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
140 definitelyWrittenResults.get(nn);
146 writtenAnalysis_nodeAction(fn, curr, entrance);
148 // if a new result, schedule forward nodes for analysis
149 if (!curr.equals(prev)) {
150 definitelyWrittenResults.put(fn, curr);
152 for (int i = 0; i < fn.numNext(); i++) {
153 FlatNode nn = fn.getNext(i);
154 flatNodesToVisit.add(nn);
160 private void writtenAnalysis_nodeAction(FlatNode fn,
161 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
163 if (fn.equals(loopEntrance)) {
164 // it reaches loop entrance: changes all flag to true
165 Set<NTuple<Descriptor>> keySet = curr.keySet();
166 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
167 NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
168 Hashtable<FlatNode, Boolean> pair = curr.get(key);
170 Set<FlatNode> pairKeySet = pair.keySet();
171 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
172 FlatNode pairKey = (FlatNode) iterator2.next();
173 pair.put(pairKey, Boolean.TRUE);
183 case FKind.FlatOpNode: {
184 FlatOpNode fon = (FlatOpNode) fn;
188 NTuple<Descriptor> rhsHeapPath = computePath(rhs);
189 if (!rhs.getType().isImmutable()) {
190 mapHeapPath.put(lhs, rhsHeapPath);
192 if (fon.getOp().getOp() == Operation.ASSIGN) {
194 readValue(fn, rhsHeapPath, curr);
197 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
198 removeHeapPath(curr, lhsHeapPath);
203 case FKind.FlatLiteralNode: {
204 FlatLiteralNode fln = (FlatLiteralNode) fn;
208 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
209 removeHeapPath(curr, lhsHeapPath);
214 case FKind.FlatFieldNode:
215 case FKind.FlatElementNode: {
217 FlatFieldNode ffn = (FlatFieldNode) fn;
220 fld = ffn.getField();
223 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
224 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
225 fldHeapPath.add(fld);
227 if (fld.getType().isImmutable()) {
228 readValue(fn, fldHeapPath, curr);
231 // propagate rhs's heap path to the lhs
232 mapHeapPath.put(lhs, fldHeapPath);
237 case FKind.FlatSetFieldNode:
238 case FKind.FlatSetElementNode: {
240 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
242 fld = fsfn.getField();
245 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
246 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
247 fldHeapPath.add(fld);
248 removeHeapPath(curr, fldHeapPath);
253 case FKind.FlatCall: {
254 FlatCall fc = (FlatCall) fn;
255 bindHeapPathCallerArgWithCaleeParam(fc);
257 // add <hp,statement,false> in which hp is an element of
259 // of callee: callee has 'read' requirement!
260 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
261 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
263 Hashtable<FlatNode, Boolean> gen = curr.get(read);
265 gen = new Hashtable<FlatNode, Boolean>();
268 Boolean currentStatus = gen.get(fn);
269 if (currentStatus == null) {
270 gen.put(fn, Boolean.FALSE);
272 checkFlag(currentStatus.booleanValue(), fn, read);
276 // removes <hp,statement,flag> if hp is an element of
278 // set of callee. it means that callee will overwrite it
279 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
280 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
281 removeHeapPath(curr, write);
291 private void readValue(FlatNode fn, NTuple<Descriptor> hp,
292 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
293 Hashtable<FlatNode, Boolean> gen = curr.get(hp);
295 gen = new Hashtable<FlatNode, Boolean>();
298 Boolean currentStatus = gen.get(fn);
299 if (currentStatus == null) {
300 gen.put(fn, Boolean.FALSE);
302 checkFlag(currentStatus.booleanValue(), fn, hp);
307 private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
308 NTuple<Descriptor> hp) {
310 // removes all of heap path that starts with prefix 'hp'
311 // since any reference overwrite along heap path gives overwriting side
312 // effects on the value
314 Set<NTuple<Descriptor>> keySet = curr.keySet();
315 for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
316 NTuple<Descriptor> key = iter.next();
317 if (key.startsWith(hp)) {
318 curr.put(key, new Hashtable<FlatNode, Boolean>());
324 private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
325 // compute all possible callee set
326 // transform all READ/OVERWRITE set from the any possible
330 calleeUnionBoundReadSet.clear();
331 calleeIntersectBoundOverWriteSet.clear();
333 MethodDescriptor mdCallee = fc.getMethod();
334 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
335 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
336 TypeDescriptor typeDesc = fc.getThis().getType();
337 setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
339 // create mapping from arg idx to its heap paths
340 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
341 new Hashtable<Integer, NTuple<Descriptor>>();
343 // arg idx is starting from 'this' arg
344 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
345 if (thisHeapPath == null) {
346 // method is called without creating new flat node representing 'this'
347 thisHeapPath = new NTuple<Descriptor>();
348 thisHeapPath.add(fc.getThis());
351 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
353 for (int i = 0; i < fc.numArgs(); i++) {
354 TempDescriptor arg = fc.getArg(i);
355 NTuple<Descriptor> argHeapPath = computePath(arg);
356 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
359 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
360 MethodDescriptor callee = (MethodDescriptor) iterator.next();
361 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
363 // binding caller's args and callee's params
365 Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
366 if (calleeReadSet == null) {
367 calleeReadSet = new HashSet<NTuple<Descriptor>>();
368 mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
370 Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
371 if (calleeOverWriteSet == null) {
372 calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
373 mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
376 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
377 new Hashtable<Integer, TempDescriptor>();
378 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
379 TempDescriptor param = calleeFlatMethod.getParameter(i);
380 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
383 Set<NTuple<Descriptor>> calleeBoundReadSet =
384 bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
385 // union of the current read set and the current callee's
387 calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
388 Set<NTuple<Descriptor>> calleeBoundWriteSet =
389 bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
390 // intersection of the current overwrite set and the current
393 merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
398 private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
401 "There is a variable, which is reachable through references "
403 + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
404 + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
409 private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
410 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
412 Set<NTuple<Descriptor>> inKeySet = in.keySet();
413 for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
414 NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
415 Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
417 Set<FlatNode> pairKeySet = inPair.keySet();
418 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
419 FlatNode pairKey = (FlatNode) iterator2.next();
420 Boolean inFlag = inPair.get(pairKey);
422 Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
423 if (currPair == null) {
424 currPair = new Hashtable<FlatNode, Boolean>();
425 curr.put(inKey, currPair);
428 Boolean currFlag = currPair.get(pairKey);
429 // by default, flag is set by false
430 if (currFlag == null) {
431 currFlag = Boolean.FALSE;
433 currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
434 currPair.put(pairKey, currFlag);
441 private void methodReadOverWriteAnalysis() {
442 // perform method READ/OVERWRITE analysis
443 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
444 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
446 LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
448 // no need to analyze method having ssjava loop
449 methodContainingSSJavaLoop = sortedDescriptors.removeFirst();
451 // current descriptors to visit in fixed-point interprocedural analysis,
453 // dependency in the call graph
454 Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
456 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
457 methodDescriptorToVistSet.addAll(sortedDescriptors);
459 while (!sortedDescriptors.isEmpty()) {
460 MethodDescriptor md = sortedDescriptors.removeFirst();
461 methodDescriptorsToVisitStack.add(md);
464 // analyze scheduled methods until there are no more to visit
465 while (!methodDescriptorsToVisitStack.isEmpty()) {
466 // start to analyze leaf node
467 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
468 FlatMethod fm = state.getMethodFlat(md);
470 Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
471 Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
473 methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
475 Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
476 Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
478 if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
479 mapFlatMethodToRead.put(fm, readSet);
480 mapFlatMethodToOverWrite.put(fm, overWriteSet);
482 // results for callee changed, so enqueue dependents caller for
485 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
486 while (depsItr.hasNext()) {
487 MethodDescriptor methodNext = depsItr.next();
488 if (!methodDescriptorsToVisitStack.contains(methodNext)
489 && methodDescriptorToVistSet.contains(methodNext)) {
490 methodDescriptorsToVisitStack.add(methodNext);
501 private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
502 Set<NTuple<Descriptor>> overWriteSet) {
503 if (state.SSJAVADEBUG) {
504 System.out.println("Definitely written Analyzing: " + fm);
507 // intraprocedural analysis
508 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
509 Set<FlatNode> visited = new HashSet<FlatNode>();
510 flatNodesToVisit.add(fm);
512 while (!flatNodesToVisit.isEmpty()) {
513 FlatNode fn = flatNodesToVisit.iterator().next();
514 flatNodesToVisit.remove(fn);
517 Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
519 for (int i = 0; i < fn.numPrev(); i++) {
520 FlatNode prevFn = fn.getPrev(i);
521 Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
527 methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
529 mapFlatNodeToWrittenSet.put(fn, curr);
531 for (int i = 0; i < fn.numNext(); i++) {
532 FlatNode nn = fn.getNext(i);
533 if (!visited.contains(nn)) {
534 flatNodesToVisit.add(nn);
542 private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
543 Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
549 case FKind.FlatMethod: {
551 // set up initial heap paths for method parameters
552 FlatMethod fm = (FlatMethod) fn;
553 for (int i = 0; i < fm.numParameters(); i++) {
554 TempDescriptor param = fm.getParameter(i);
555 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
557 mapHeapPath.put(param, heapPath);
562 case FKind.FlatOpNode: {
563 FlatOpNode fon = (FlatOpNode) fn;
564 // for a normal assign node, need to propagate lhs's heap path to
566 if (fon.getOp().getOp() == Operation.ASSIGN) {
570 NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
571 if (rhsHeapPath != null) {
572 mapHeapPath.put(lhs, mapHeapPath.get(rhs));
579 case FKind.FlatFieldNode:
580 case FKind.FlatElementNode: {
584 FlatFieldNode ffn = (FlatFieldNode) fn;
587 fld = ffn.getField();
590 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
591 if (srcHeapPath != null) {
592 // if lhs srcHeapPath is null, it means that it is not reachable from
593 // callee's parameters. so just ignore it
595 NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
596 readingHeapPath.add(fld);
597 mapHeapPath.put(lhs, readingHeapPath);
600 if (fld.getType().isImmutable()) {
601 // if WT doesnot have hp(x.f), add hp(x.f) to READ
602 if (!writtenSet.contains(readingHeapPath)) {
603 readSet.add(readingHeapPath);
607 // need to kill hp(x.f) from WT
608 writtenSet.remove(readingHeapPath);
614 case FKind.FlatSetFieldNode:
615 case FKind.FlatSetElementNode: {
618 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
620 fld = fsfn.getField();
624 NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
625 if (lhsHeapPath != null) {
626 // if lhs heap path is null, it means that it is not reachable from
627 // callee's parameters. so just ignore it
628 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
629 newHeapPath.add(fld);
630 mapHeapPath.put(fld, newHeapPath);
633 // need to add hp(y) to WT
634 writtenSet.add(newHeapPath);
640 case FKind.FlatCall: {
642 FlatCall fc = (FlatCall) fn;
644 bindHeapPathCallerArgWithCaleeParam(fc);
646 // add heap path, which is an element of READ_bound set and is not
648 // element of WT set, to the caller's READ set
649 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
650 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
651 if (!writtenSet.contains(read)) {
655 writtenSet.removeAll(calleeUnionBoundReadSet);
657 // add heap path, which is an element of OVERWRITE_bound set, to the
659 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
660 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
661 writtenSet.add(write);
667 case FKind.FlatExit: {
668 // merge the current written set with OVERWRITE set
669 merge(overWriteSet, writtenSet);
677 private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
678 if (curr.isEmpty()) {
679 // WrittenSet has a special initial value which covers all possible
681 // For the first time of intersection, we can take all previous set
684 // otherwise, current set is the intersection of the two sets
690 // combine two heap path
691 private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
692 NTuple<Descriptor> combined = new NTuple<Descriptor>();
694 for (int i = 0; i < callerIn.size(); i++) {
695 combined.add(callerIn.get(i));
698 // the first element of callee's heap path represents parameter
699 // so we skip the first one since it is already added from caller's heap
701 for (int i = 1; i < calleeIn.size(); i++) {
702 combined.add(calleeIn.get(i));
708 private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
709 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
710 Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
712 Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
714 Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
715 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
716 Integer idx = (Integer) iterator.next();
718 NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
719 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
721 for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
722 NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
723 if (element.startsWith(calleeParam)) {
724 NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
725 boundedCalleeSet.add(boundElement);
731 return boundedCalleeSet;
735 // Borrowed it from disjoint analysis
736 private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
738 Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
740 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
742 Iterator<MethodDescriptor> itr = toSort.iterator();
743 while (itr.hasNext()) {
744 MethodDescriptor d = itr.next();
746 if (!discovered.contains(d)) {
747 dfsVisit(d, toSort, sorted, discovered);
754 // While we're doing DFS on call graph, remember
755 // dependencies for efficient queuing of methods
756 // during interprocedural analysis:
758 // a dependent of a method decriptor d for this analysis is:
759 // 1) a method or task that invokes d
760 // 2) in the descriptorsToAnalyze set
761 private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
762 LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
766 // otherwise call graph guides DFS
767 Iterator itr = callGraph.getCallerSet(md).iterator();
768 while (itr.hasNext()) {
769 MethodDescriptor dCaller = (MethodDescriptor) itr.next();
771 // only consider callers in the original set to analyze
772 if (!toSort.contains(dCaller)) {
776 if (!discovered.contains(dCaller)) {
777 addDependent(md, // callee
781 dfsVisit(dCaller, toSort, sorted, discovered);
785 // for leaf-nodes last now!
789 // a dependent of a method decriptor d for this analysis is:
790 // 1) a method or task that invokes d
791 // 2) in the descriptorsToAnalyze set
792 private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
793 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
795 deps = new HashSet<MethodDescriptor>();
798 mapDescriptorToSetDependents.put(callee, deps);
801 private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
802 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
804 deps = new HashSet<MethodDescriptor>();
805 mapDescriptorToSetDependents.put(callee, deps);
810 private NTuple<Descriptor> computePath(TempDescriptor td) {
811 // generate proper path fot input td
812 // if td is local variable, it just generate one element tuple path
813 if (mapHeapPath.containsKey(td)) {
814 return mapHeapPath.get(td);
816 NTuple<Descriptor> path = new NTuple<Descriptor>();