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;
9 import java.util.Vector;
11 import Analysis.CallGraph.CallGraph;
12 import Analysis.Loops.LoopFinder;
14 import IR.FieldDescriptor;
15 import IR.MethodDescriptor;
18 import IR.TypeDescriptor;
20 import IR.Flat.FlatCall;
21 import IR.Flat.FlatFieldNode;
22 import IR.Flat.FlatLiteralNode;
23 import IR.Flat.FlatMethod;
24 import IR.Flat.FlatNode;
25 import IR.Flat.FlatOpNode;
26 import IR.Flat.FlatSetFieldNode;
27 import IR.Flat.TempDescriptor;
29 public class DefinitelyWrittenCheck {
31 SSJavaAnalysis ssjava;
35 // maps a descriptor to its known dependents: namely
36 // methods or tasks that call the descriptor's method
37 // AND are part of this analysis (reachable from main)
38 private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
40 // maps a flat node to its WrittenSet: this keeps all heap path overwritten
42 private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
44 // maps a temp descriptor to its heap path
45 // each temp descriptor has a unique heap path since we do not allow any
47 private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
49 // maps a flat method to the READ that is the set of heap path that is
50 // expected to be written before method invocation
51 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
53 // maps a flat method to the OVERWRITE that is the set of heap path that is
54 // overwritten on every possible path during method invocation
55 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
57 // points to method containing SSJAVA Loop
58 private MethodDescriptor methodContainingSSJavaLoop;
60 // maps a flatnode to definitely written analysis mapping M
61 private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
63 // maps a method descriptor to its current summary during the analysis
64 // then analysis reaches fixed-point, this mapping will have the final summary
65 // for each method descriptor
66 private Hashtable<MethodDescriptor, Hashtable<Location, Vector<Object>>> mapMethodDescriptorToCompleteClearingSummary;
68 // maps a method descriptor to the merged incoming caller's current
70 private Hashtable<MethodDescriptor, Hashtable<Location, Vector<Object>>> mapMethodDescriptorToInitialClearingSummary;
72 // maps a flat node to current partial results
73 private Hashtable<FlatNode, Hashtable<Location, Vector<Object>>> mapFlatNodeToClearingSummary;
75 private FlatNode ssjavaLoopEntrance;
76 private LoopFinder ssjavaLoop;
77 private Set<FlatNode> loopIncElements;
79 private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
80 private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
82 public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
85 this.callGraph = ssjava.getCallGraph();
86 this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
87 this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
88 this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
89 this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
90 this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
91 this.definitelyWrittenResults =
92 new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
93 this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
94 this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
95 this.mapMethodDescriptorToCompleteClearingSummary =
96 new Hashtable<MethodDescriptor, Hashtable<Location, Vector<Object>>>();
97 this.mapMethodDescriptorToInitialClearingSummary =
98 new Hashtable<MethodDescriptor, Hashtable<Location, Vector<Object>>>();
99 this.mapFlatNodeToClearingSummary =
100 new Hashtable<FlatNode, Hashtable<Location, Vector<Object>>>();
103 public void definitelyWrittenCheck() {
104 if (!ssjava.getAnnotationRequireSet().isEmpty()) {
105 methodReadOverWriteAnalysis();
107 // sharedLocationAnalysis();
111 private void sharedLocationAnalysis() {
112 // verify that all concrete locations of shared location are cleared out at
113 // the same time once per the out-most loop
115 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
116 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
118 LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
120 Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
121 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
122 methodDescriptorToVistSet.addAll(sortedDescriptors);
124 while (!sortedDescriptors.isEmpty()) {
125 MethodDescriptor md = sortedDescriptors.removeLast();
126 methodDescriptorsToVisitStack.add(md);
129 // analyze scheduled methods until there are no more to visit
130 while (!methodDescriptorsToVisitStack.isEmpty()) {
131 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
132 FlatMethod fm = state.getMethodFlat(md);
134 sharedLocation_analyzeMethod(fm, (fm.equals(methodContainingSSJavaLoop)));
138 // results for callee changed, so enqueue dependents caller for
140 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
141 while (depsItr.hasNext()) {
142 MethodDescriptor methodNext = depsItr.next();
143 if (!methodDescriptorsToVisitStack.contains(methodNext)
144 && methodDescriptorToVistSet.contains(methodNext)) {
145 methodDescriptorsToVisitStack.add(methodNext);
154 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
155 flatNodesToVisit.add(ssjavaLoopEntrance);
159 private void sharedLocation_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) {
161 if (state.SSJAVADEBUG) {
162 System.out.println("Definitely written for shared locations Analyzing: " + fm);
165 // intraprocedural analysis
166 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
167 Set<FlatNode> visited = new HashSet<FlatNode>();
169 if (onlyVisitSSJavaLoop) {
170 flatNodesToVisit.add(ssjavaLoopEntrance);
172 flatNodesToVisit.add(fm);
175 while (!flatNodesToVisit.isEmpty()) {
176 FlatNode fn = flatNodesToVisit.iterator().next();
177 flatNodesToVisit.remove(fn);
179 Hashtable<Location, Vector<Object>> curr = new Hashtable<Location, Vector<Object>>();
181 for (int i = 0; i < fn.numPrev(); i++) {
182 FlatNode prevFn = fn.getPrev(i);
183 Hashtable<Location, Vector<Object>> in = mapFlatNodeToClearingSummary.get(prevFn);
185 mergeSharedAnaylsis(curr, in);
189 sharedLocation_nodeActions(fn, curr);
191 Hashtable<Location, Vector<Object>> clearingPrev = mapFlatNodeToClearingSummary.get(fn);
193 if (!curr.equals(clearingPrev)) {
194 mapFlatNodeToClearingSummary.put(fn, curr);
196 for (int i = 0; i < fn.numNext(); i++) {
197 FlatNode nn = fn.getNext(i);
199 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
200 flatNodesToVisit.add(nn);
210 private void sharedLocation_nodeActions(FlatNode fn, Hashtable<Location, Vector<Object>> curr) {
216 System.out.println("fn="+fn);
218 case FKind.FlatFieldNode:
219 case FKind.FlatElementNode: {
221 FlatFieldNode ffn = (FlatFieldNode) fn;
224 fld = ffn.getField();
227 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
228 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
229 fldHeapPath.add(fld);
231 if (fld.getType().isImmutable()) {
232 readLocation(fn, fldHeapPath, curr);
235 // propagate rhs's heap path to the lhs
236 mapHeapPath.put(lhs, fldHeapPath);
241 case FKind.FlatSetFieldNode:
242 case FKind.FlatSetElementNode: {
244 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
246 fld = fsfn.getField();
249 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
250 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
251 writeLocation(curr, fldHeapPath, fld);
256 case FKind.FlatCall: {
264 private void writeLocation(Hashtable<Location, Vector<Object>> curr,
265 NTuple<Descriptor> fldHeapPath, FieldDescriptor fld) {
267 Location fieldLoc = (Location) fld.getType().getExtension();
268 if (ssjava.isSharedLocation(fieldLoc)) {
270 Vector<Object> v = curr.get(fieldLoc);
272 v = new Vector<Object>();
273 curr.put(fieldLoc, v);
274 v.add(0, fldHeapPath);
275 v.add(1, new HashSet());
276 v.add(2, new Boolean(false));
278 ((Set) v.get(1)).add(fld);
282 private void readLocation(FlatNode fn, NTuple<Descriptor> fldHeapPath,
283 Hashtable<Location, Vector<Object>> curr) {
284 // TODO Auto-generated method stub
288 private void writtenAnalyis() {
289 // perform second stage analysis: intraprocedural analysis ensure that
291 // variables are definitely written in-between the same read
293 // First, identify ssjava loop entrace
294 FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
295 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
296 flatNodesToVisit.add(fm);
298 LoopFinder loopFinder = new LoopFinder(fm);
300 while (!flatNodesToVisit.isEmpty()) {
301 FlatNode fn = flatNodesToVisit.iterator().next();
302 flatNodesToVisit.remove(fn);
304 String label = (String) state.fn2labelMap.get(fn);
307 if (label.equals(ssjava.SSJAVA)) {
308 ssjavaLoopEntrance = fn;
313 for (int i = 0; i < fn.numNext(); i++) {
314 FlatNode nn = fn.getNext(i);
315 flatNodesToVisit.add(nn);
319 assert ssjavaLoopEntrance != null;
321 // assume that ssjava loop is top-level loop in method, not nested loop
322 Set nestedLoop = loopFinder.nestedLoops();
323 for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
324 LoopFinder lf = (LoopFinder) loopIter.next();
325 if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
330 assert ssjavaLoop != null;
332 writtenAnalysis_analyzeLoop();
336 private void writtenAnalysis_analyzeLoop() {
338 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
339 flatNodesToVisit.add(ssjavaLoopEntrance);
341 loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
343 while (!flatNodesToVisit.isEmpty()) {
344 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
345 flatNodesToVisit.remove(fn);
347 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
348 definitelyWrittenResults.get(fn);
350 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
351 new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
352 for (int i = 0; i < fn.numPrev(); i++) {
353 FlatNode nn = fn.getPrev(i);
354 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
355 definitelyWrittenResults.get(nn);
361 writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
363 // if a new result, schedule forward nodes for analysis
364 if (!curr.equals(prev)) {
365 definitelyWrittenResults.put(fn, curr);
367 for (int i = 0; i < fn.numNext(); i++) {
368 FlatNode nn = fn.getNext(i);
369 if (loopIncElements.contains(nn)) {
370 flatNodesToVisit.add(nn);
378 private void writtenAnalysis_nodeAction(FlatNode fn,
379 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
381 if (fn.equals(loopEntrance)) {
382 // it reaches loop entrance: changes all flag to true
383 Set<NTuple<Descriptor>> keySet = curr.keySet();
384 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
385 NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
386 Hashtable<FlatNode, Boolean> pair = curr.get(key);
388 Set<FlatNode> pairKeySet = pair.keySet();
389 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
390 FlatNode pairKey = (FlatNode) iterator2.next();
391 pair.put(pairKey, Boolean.TRUE);
401 case FKind.FlatOpNode: {
402 FlatOpNode fon = (FlatOpNode) fn;
406 NTuple<Descriptor> rhsHeapPath = computePath(rhs);
407 if (!rhs.getType().isImmutable()) {
408 mapHeapPath.put(lhs, rhsHeapPath);
410 if (fon.getOp().getOp() == Operation.ASSIGN) {
412 readValue(fn, rhsHeapPath, curr);
415 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
416 removeHeapPath(curr, lhsHeapPath);
421 case FKind.FlatLiteralNode: {
422 FlatLiteralNode fln = (FlatLiteralNode) fn;
426 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
427 removeHeapPath(curr, lhsHeapPath);
432 case FKind.FlatFieldNode:
433 case FKind.FlatElementNode: {
435 FlatFieldNode ffn = (FlatFieldNode) fn;
438 fld = ffn.getField();
441 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
442 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
443 fldHeapPath.add(fld);
445 if (fld.getType().isImmutable()) {
446 readValue(fn, fldHeapPath, curr);
449 // propagate rhs's heap path to the lhs
450 mapHeapPath.put(lhs, fldHeapPath);
455 case FKind.FlatSetFieldNode:
456 case FKind.FlatSetElementNode: {
458 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
460 fld = fsfn.getField();
463 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
464 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
465 fldHeapPath.add(fld);
466 removeHeapPath(curr, fldHeapPath);
471 case FKind.FlatCall: {
472 FlatCall fc = (FlatCall) fn;
473 bindHeapPathCallerArgWithCaleeParam(fc);
475 // add <hp,statement,false> in which hp is an element of
477 // of callee: callee has 'read' requirement!
478 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
479 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
481 Hashtable<FlatNode, Boolean> gen = curr.get(read);
483 gen = new Hashtable<FlatNode, Boolean>();
486 Boolean currentStatus = gen.get(fn);
487 if (currentStatus == null) {
488 gen.put(fn, Boolean.FALSE);
490 checkFlag(currentStatus.booleanValue(), fn, read);
494 // removes <hp,statement,flag> if hp is an element of
496 // set of callee. it means that callee will overwrite it
497 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
498 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
499 removeHeapPath(curr, write);
509 private void readValue(FlatNode fn, NTuple<Descriptor> hp,
510 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
511 Hashtable<FlatNode, Boolean> gen = curr.get(hp);
513 gen = new Hashtable<FlatNode, Boolean>();
516 Boolean currentStatus = gen.get(fn);
517 if (currentStatus == null) {
518 gen.put(fn, Boolean.FALSE);
520 checkFlag(currentStatus.booleanValue(), fn, hp);
525 private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
526 NTuple<Descriptor> hp) {
528 // removes all of heap path that starts with prefix 'hp'
529 // since any reference overwrite along heap path gives overwriting side
530 // effects on the value
532 Set<NTuple<Descriptor>> keySet = curr.keySet();
533 for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
534 NTuple<Descriptor> key = iter.next();
535 if (key.startsWith(hp)) {
536 curr.put(key, new Hashtable<FlatNode, Boolean>());
542 private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
543 // compute all possible callee set
544 // transform all READ/OVERWRITE set from the any possible
548 calleeUnionBoundReadSet.clear();
549 calleeIntersectBoundOverWriteSet.clear();
551 MethodDescriptor mdCallee = fc.getMethod();
552 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
553 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
554 TypeDescriptor typeDesc = fc.getThis().getType();
555 setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
557 // create mapping from arg idx to its heap paths
558 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
559 new Hashtable<Integer, NTuple<Descriptor>>();
561 // arg idx is starting from 'this' arg
562 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
563 if (thisHeapPath == null) {
564 // method is called without creating new flat node representing 'this'
565 thisHeapPath = new NTuple<Descriptor>();
566 thisHeapPath.add(fc.getThis());
569 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
571 for (int i = 0; i < fc.numArgs(); i++) {
572 TempDescriptor arg = fc.getArg(i);
573 NTuple<Descriptor> argHeapPath = computePath(arg);
574 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
577 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
578 MethodDescriptor callee = (MethodDescriptor) iterator.next();
579 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
581 // binding caller's args and callee's params
583 Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
584 if (calleeReadSet == null) {
585 calleeReadSet = new HashSet<NTuple<Descriptor>>();
586 mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
588 Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
589 if (calleeOverWriteSet == null) {
590 calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
591 mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
594 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
595 new Hashtable<Integer, TempDescriptor>();
596 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
597 TempDescriptor param = calleeFlatMethod.getParameter(i);
598 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
601 Set<NTuple<Descriptor>> calleeBoundReadSet =
602 bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
603 // union of the current read set and the current callee's
605 calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
606 Set<NTuple<Descriptor>> calleeBoundWriteSet =
607 bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
608 // intersection of the current overwrite set and the current
611 merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
616 private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
619 "There is a variable, which is reachable through references "
621 + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
622 + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
627 private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
628 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
630 Set<NTuple<Descriptor>> inKeySet = in.keySet();
631 for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
632 NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
633 Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
635 Set<FlatNode> pairKeySet = inPair.keySet();
636 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
637 FlatNode pairKey = (FlatNode) iterator2.next();
638 Boolean inFlag = inPair.get(pairKey);
640 Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
641 if (currPair == null) {
642 currPair = new Hashtable<FlatNode, Boolean>();
643 curr.put(inKey, currPair);
646 Boolean currFlag = currPair.get(pairKey);
647 // by default, flag is set by false
648 if (currFlag == null) {
649 currFlag = Boolean.FALSE;
651 currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
652 currPair.put(pairKey, currFlag);
659 private void methodReadOverWriteAnalysis() {
660 // perform method READ/OVERWRITE analysis
661 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
662 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
664 LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
666 // no need to analyze method having ssjava loop
667 methodContainingSSJavaLoop = sortedDescriptors.removeFirst();
669 // current descriptors to visit in fixed-point interprocedural analysis,
671 // dependency in the call graph
672 Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
674 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
675 methodDescriptorToVistSet.addAll(sortedDescriptors);
677 while (!sortedDescriptors.isEmpty()) {
678 MethodDescriptor md = sortedDescriptors.removeFirst();
679 methodDescriptorsToVisitStack.add(md);
682 // analyze scheduled methods until there are no more to visit
683 while (!methodDescriptorsToVisitStack.isEmpty()) {
684 // start to analyze leaf node
685 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
686 FlatMethod fm = state.getMethodFlat(md);
688 Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
689 Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
691 methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
693 Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
694 Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
696 if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
697 mapFlatMethodToRead.put(fm, readSet);
698 mapFlatMethodToOverWrite.put(fm, overWriteSet);
700 // results for callee changed, so enqueue dependents caller for
703 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
704 while (depsItr.hasNext()) {
705 MethodDescriptor methodNext = depsItr.next();
706 if (!methodDescriptorsToVisitStack.contains(methodNext)
707 && methodDescriptorToVistSet.contains(methodNext)) {
708 methodDescriptorsToVisitStack.add(methodNext);
719 private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
720 Set<NTuple<Descriptor>> overWriteSet) {
721 if (state.SSJAVADEBUG) {
722 System.out.println("Definitely written Analyzing: " + fm);
725 // intraprocedural analysis
726 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
727 flatNodesToVisit.add(fm);
729 while (!flatNodesToVisit.isEmpty()) {
730 FlatNode fn = flatNodesToVisit.iterator().next();
731 flatNodesToVisit.remove(fn);
733 Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
735 for (int i = 0; i < fn.numPrev(); i++) {
736 FlatNode prevFn = fn.getPrev(i);
737 Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
743 methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
745 Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
746 if (!curr.equals(writtenSetPrev)) {
747 mapFlatNodeToWrittenSet.put(fn, curr);
748 for (int i = 0; i < fn.numNext(); i++) {
749 FlatNode nn = fn.getNext(i);
750 flatNodesToVisit.add(nn);
758 private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
759 Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
765 case FKind.FlatMethod: {
767 // set up initial heap paths for method parameters
768 FlatMethod fm = (FlatMethod) fn;
769 for (int i = 0; i < fm.numParameters(); i++) {
770 TempDescriptor param = fm.getParameter(i);
771 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
773 mapHeapPath.put(param, heapPath);
778 case FKind.FlatOpNode: {
779 FlatOpNode fon = (FlatOpNode) fn;
780 // for a normal assign node, need to propagate lhs's heap path to
782 if (fon.getOp().getOp() == Operation.ASSIGN) {
786 NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
787 if (rhsHeapPath != null) {
788 mapHeapPath.put(lhs, mapHeapPath.get(rhs));
795 case FKind.FlatFieldNode:
796 case FKind.FlatElementNode: {
800 FlatFieldNode ffn = (FlatFieldNode) fn;
803 fld = ffn.getField();
806 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
807 if (srcHeapPath != null) {
808 // if lhs srcHeapPath is null, it means that it is not reachable from
809 // callee's parameters. so just ignore it
811 NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
812 readingHeapPath.add(fld);
813 mapHeapPath.put(lhs, readingHeapPath);
816 if (fld.getType().isImmutable()) {
817 // if WT doesnot have hp(x.f), add hp(x.f) to READ
818 if (!writtenSet.contains(readingHeapPath)) {
819 readSet.add(readingHeapPath);
823 // need to kill hp(x.f) from WT
824 writtenSet.remove(readingHeapPath);
830 case FKind.FlatSetFieldNode:
831 case FKind.FlatSetElementNode: {
834 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
836 fld = fsfn.getField();
840 NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
841 if (lhsHeapPath != null) {
842 // if lhs heap path is null, it means that it is not reachable from
843 // callee's parameters. so just ignore it
844 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
845 newHeapPath.add(fld);
846 mapHeapPath.put(fld, newHeapPath);
849 // need to add hp(y) to WT
850 writtenSet.add(newHeapPath);
856 case FKind.FlatCall: {
858 FlatCall fc = (FlatCall) fn;
860 bindHeapPathCallerArgWithCaleeParam(fc);
862 // add heap path, which is an element of READ_bound set and is not
864 // element of WT set, to the caller's READ set
865 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
866 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
867 if (!writtenSet.contains(read)) {
871 writtenSet.removeAll(calleeUnionBoundReadSet);
873 // add heap path, which is an element of OVERWRITE_bound set, to the
875 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
876 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
877 writtenSet.add(write);
883 case FKind.FlatExit: {
884 // merge the current written set with OVERWRITE set
885 merge(overWriteSet, writtenSet);
893 private void mergeSharedAnaylsis(Hashtable<Location, Vector<Object>> curr,
894 Hashtable<Location, Vector<Object>> in) {
898 private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
899 if (curr.isEmpty()) {
900 // WrittenSet has a special initial value which covers all possible
902 // For the first time of intersection, we can take all previous set
905 // otherwise, current set is the intersection of the two sets
911 // combine two heap path
912 private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
913 NTuple<Descriptor> combined = new NTuple<Descriptor>();
915 for (int i = 0; i < callerIn.size(); i++) {
916 combined.add(callerIn.get(i));
919 // the first element of callee's heap path represents parameter
920 // so we skip the first one since it is already added from caller's heap
922 for (int i = 1; i < calleeIn.size(); i++) {
923 combined.add(calleeIn.get(i));
929 private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
930 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
931 Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
933 Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
935 Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
936 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
937 Integer idx = (Integer) iterator.next();
939 NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
940 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
942 for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
943 NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
944 if (element.startsWith(calleeParam)) {
945 NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
946 boundedCalleeSet.add(boundElement);
952 return boundedCalleeSet;
956 // Borrowed it from disjoint analysis
957 private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
959 Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
961 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
963 Iterator<MethodDescriptor> itr = toSort.iterator();
964 while (itr.hasNext()) {
965 MethodDescriptor d = itr.next();
967 if (!discovered.contains(d)) {
968 dfsVisit(d, toSort, sorted, discovered);
975 // While we're doing DFS on call graph, remember
976 // dependencies for efficient queuing of methods
977 // during interprocedural analysis:
979 // a dependent of a method decriptor d for this analysis is:
980 // 1) a method or task that invokes d
981 // 2) in the descriptorsToAnalyze set
982 private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
983 LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
987 // otherwise call graph guides DFS
988 Iterator itr = callGraph.getCallerSet(md).iterator();
989 while (itr.hasNext()) {
990 MethodDescriptor dCaller = (MethodDescriptor) itr.next();
992 // only consider callers in the original set to analyze
993 if (!toSort.contains(dCaller)) {
997 if (!discovered.contains(dCaller)) {
998 addDependent(md, // callee
1002 dfsVisit(dCaller, toSort, sorted, discovered);
1006 // for leaf-nodes last now!
1010 // a dependent of a method decriptor d for this analysis is:
1011 // 1) a method or task that invokes d
1012 // 2) in the descriptorsToAnalyze set
1013 private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1014 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1016 deps = new HashSet<MethodDescriptor>();
1019 mapDescriptorToSetDependents.put(callee, deps);
1022 private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1023 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1025 deps = new HashSet<MethodDescriptor>();
1026 mapDescriptorToSetDependents.put(callee, deps);
1031 private NTuple<Descriptor> computePath(TempDescriptor td) {
1032 // generate proper path fot input td
1033 // if td is local variable, it just generate one element tuple path
1034 if (mapHeapPath.containsKey(td)) {
1035 return mapHeapPath.get(td);
1037 NTuple<Descriptor> path = new NTuple<Descriptor>();