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<NTuple<Descriptor>, Set<SharedLocState>>> mapMethodDescriptorToCompleteClearingSummary;
68 // maps a method descriptor to the merged incoming caller's current
70 private Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>> mapMethodDescriptorToInitialClearingSummary;
72 // maps a flat node to current partial results
73 private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>> 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 private TempDescriptor LOCAL;
84 public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
87 this.callGraph = ssjava.getCallGraph();
88 this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
89 this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
90 this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
91 this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
92 this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
93 this.definitelyWrittenResults =
94 new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
95 this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
96 this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
98 this.mapMethodDescriptorToCompleteClearingSummary =
99 new Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>>();
100 this.mapMethodDescriptorToInitialClearingSummary =
101 new Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>>();
102 this.mapFlatNodeToClearingSummary =
103 new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>>();
104 this.LOCAL = new TempDescriptor("LOCAL");
107 public void definitelyWrittenCheck() {
108 if (!ssjava.getAnnotationRequireSet().isEmpty()) {
109 methodReadOverWriteAnalysis();
111 sharedLocationAnalysis();
115 private void sharedLocationAnalysis() {
116 // verify that all concrete locations of shared location are cleared out at
117 // the same time once per the out-most loop
119 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
120 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
122 LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
124 Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
125 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
126 methodDescriptorToVistSet.addAll(sortedDescriptors);
128 while (!sortedDescriptors.isEmpty()) {
129 MethodDescriptor md = sortedDescriptors.removeLast();
130 methodDescriptorsToVisitStack.add(md);
133 // analyze scheduled methods until there are no more to visit
134 while (!methodDescriptorsToVisitStack.isEmpty()) {
135 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
136 FlatMethod fm = state.getMethodFlat(md);
138 sharedLocation_analyzeMethod(fm, (md.equals(methodContainingSSJavaLoop)));
142 // results for callee changed, so enqueue dependents caller for
144 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
145 while (depsItr.hasNext()) {
146 MethodDescriptor methodNext = depsItr.next();
147 if (!methodDescriptorsToVisitStack.contains(methodNext)
148 && methodDescriptorToVistSet.contains(methodNext)) {
149 methodDescriptorsToVisitStack.add(methodNext);
158 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
159 flatNodesToVisit.add(ssjavaLoopEntrance);
163 private void sharedLocation_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) {
165 if (state.SSJAVADEBUG) {
166 System.out.println("Definitely written for shared locations Analyzing: " + fm + " "
167 + onlyVisitSSJavaLoop);
170 // intraprocedural analysis
171 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
172 Set<FlatNode> visited = new HashSet<FlatNode>();
174 if (onlyVisitSSJavaLoop) {
175 flatNodesToVisit.add(ssjavaLoopEntrance);
177 flatNodesToVisit.add(fm);
180 while (!flatNodesToVisit.isEmpty()) {
181 FlatNode fn = flatNodesToVisit.iterator().next();
182 flatNodesToVisit.remove(fn);
184 Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr =
185 new Hashtable<NTuple<Descriptor>, Set<SharedLocState>>();
187 for (int i = 0; i < fn.numPrev(); i++) {
188 FlatNode prevFn = fn.getPrev(i);
189 Hashtable<NTuple<Descriptor>, Set<SharedLocState>> in =
190 mapFlatNodeToClearingSummary.get(prevFn);
192 mergeSharedAnaylsis(curr, in);
196 sharedLocation_nodeActions(fn, curr, onlyVisitSSJavaLoop);
198 Hashtable<NTuple<Descriptor>, Set<SharedLocState>> clearingPrev =
199 mapFlatNodeToClearingSummary.get(fn);
201 if (!curr.equals(clearingPrev)) {
202 mapFlatNodeToClearingSummary.put(fn, curr);
204 for (int i = 0; i < fn.numNext(); i++) {
205 FlatNode nn = fn.getNext(i);
207 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
208 flatNodesToVisit.add(nn);
218 private void sharedLocation_nodeActions(FlatNode fn,
219 Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr, boolean isSSJavaLoop) {
226 case FKind.FlatOpNode: {
227 FlatOpNode fon = (FlatOpNode) fn;
231 if (fon.getOp().getOp() == Operation.ASSIGN) {
232 if (rhs.getType().isImmutable() && isSSJavaLoop) {
233 // in ssjavaloop, we need to take care about reading local variables!
234 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
235 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
236 rhsHeapPath.add(LOCAL);
237 lhsHeapPath.add(LOCAL);
238 readLocation(curr, rhsHeapPath, rhs);
239 writeLocation(curr, lhsHeapPath, lhs);
246 case FKind.FlatFieldNode:
247 case FKind.FlatElementNode: {
249 FlatFieldNode ffn = (FlatFieldNode) fn;
252 fld = ffn.getField();
255 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
256 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
257 fldHeapPath.add(fld);
259 if (fld.getType().isImmutable()) {
260 // readLocation(f curr);
263 // propagate rhs's heap path to the lhs
264 mapHeapPath.put(lhs, fldHeapPath);
269 case FKind.FlatSetFieldNode:
270 case FKind.FlatSetElementNode: {
272 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
274 fld = fsfn.getField();
277 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
278 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
279 // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
284 case FKind.FlatCall: {
292 private Location getLocation(Descriptor d) {
294 if (d instanceof FieldDescriptor) {
295 return (Location) ((FieldDescriptor) d).getType().getExtension();
297 assert d instanceof TempDescriptor;
298 CompositeLocation comp = (CompositeLocation) ((TempDescriptor) d).getType().getExtension();
299 return comp.get(comp.getSize() - 1);
304 private SharedLocState getSharedLocState(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
305 NTuple<Descriptor> hp, Location loc) {
307 Set<SharedLocState> set = curr.get(hp);
309 set = new HashSet<SharedLocState>();
313 SharedLocState state = null;
314 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
315 SharedLocState e = (SharedLocState) iterator.next();
316 if (e.getLoc().equals(loc)) {
323 state = new SharedLocState(loc);
330 private void writeLocation(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
331 NTuple<Descriptor> hp, Descriptor d) {
333 Location loc = getLocation(d);
334 if (ssjava.isSharedLocation(loc)) {
335 SharedLocState state = getSharedLocState(curr, hp, loc);
340 private void readLocation(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
341 NTuple<Descriptor> hp, Descriptor d) {
342 // remove reading var x from written set
344 Location loc = getLocation(d);
345 if (ssjava.isSharedLocation(loc)) {
346 SharedLocState state = getSharedLocState(curr, hp, loc);
351 private void writtenAnalyis() {
352 // perform second stage analysis: intraprocedural analysis ensure that
354 // variables are definitely written in-between the same read
356 // First, identify ssjava loop entrace
357 FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
358 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
359 flatNodesToVisit.add(fm);
361 LoopFinder loopFinder = new LoopFinder(fm);
363 while (!flatNodesToVisit.isEmpty()) {
364 FlatNode fn = flatNodesToVisit.iterator().next();
365 flatNodesToVisit.remove(fn);
367 String label = (String) state.fn2labelMap.get(fn);
370 if (label.equals(ssjava.SSJAVA)) {
371 ssjavaLoopEntrance = fn;
376 for (int i = 0; i < fn.numNext(); i++) {
377 FlatNode nn = fn.getNext(i);
378 flatNodesToVisit.add(nn);
382 assert ssjavaLoopEntrance != null;
384 // assume that ssjava loop is top-level loop in method, not nested loop
385 Set nestedLoop = loopFinder.nestedLoops();
386 for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
387 LoopFinder lf = (LoopFinder) loopIter.next();
388 if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
393 assert ssjavaLoop != null;
395 writtenAnalysis_analyzeLoop();
399 private void writtenAnalysis_analyzeLoop() {
401 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
402 flatNodesToVisit.add(ssjavaLoopEntrance);
404 loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
406 while (!flatNodesToVisit.isEmpty()) {
407 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
408 flatNodesToVisit.remove(fn);
410 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
411 definitelyWrittenResults.get(fn);
413 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
414 new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
415 for (int i = 0; i < fn.numPrev(); i++) {
416 FlatNode nn = fn.getPrev(i);
417 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
418 definitelyWrittenResults.get(nn);
424 writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
426 // if a new result, schedule forward nodes for analysis
427 if (!curr.equals(prev)) {
428 definitelyWrittenResults.put(fn, curr);
430 for (int i = 0; i < fn.numNext(); i++) {
431 FlatNode nn = fn.getNext(i);
432 if (loopIncElements.contains(nn)) {
433 flatNodesToVisit.add(nn);
441 private void writtenAnalysis_nodeAction(FlatNode fn,
442 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
444 if (fn.equals(loopEntrance)) {
445 // it reaches loop entrance: changes all flag to true
446 Set<NTuple<Descriptor>> keySet = curr.keySet();
447 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
448 NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
449 Hashtable<FlatNode, Boolean> pair = curr.get(key);
451 Set<FlatNode> pairKeySet = pair.keySet();
452 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
453 FlatNode pairKey = (FlatNode) iterator2.next();
454 pair.put(pairKey, Boolean.TRUE);
464 case FKind.FlatOpNode: {
465 FlatOpNode fon = (FlatOpNode) fn;
469 NTuple<Descriptor> rhsHeapPath = computePath(rhs);
470 if (!rhs.getType().isImmutable()) {
471 mapHeapPath.put(lhs, rhsHeapPath);
473 if (fon.getOp().getOp() == Operation.ASSIGN) {
475 readValue(fn, rhsHeapPath, curr);
478 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
479 removeHeapPath(curr, lhsHeapPath);
484 case FKind.FlatLiteralNode: {
485 FlatLiteralNode fln = (FlatLiteralNode) fn;
489 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
490 removeHeapPath(curr, lhsHeapPath);
495 case FKind.FlatFieldNode:
496 case FKind.FlatElementNode: {
498 FlatFieldNode ffn = (FlatFieldNode) fn;
501 fld = ffn.getField();
504 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
505 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
506 fldHeapPath.add(fld);
508 if (fld.getType().isImmutable()) {
509 readValue(fn, fldHeapPath, curr);
512 // propagate rhs's heap path to the lhs
513 mapHeapPath.put(lhs, fldHeapPath);
518 case FKind.FlatSetFieldNode:
519 case FKind.FlatSetElementNode: {
521 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
523 fld = fsfn.getField();
526 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
527 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
528 fldHeapPath.add(fld);
529 removeHeapPath(curr, fldHeapPath);
534 case FKind.FlatCall: {
535 FlatCall fc = (FlatCall) fn;
536 bindHeapPathCallerArgWithCaleeParam(fc);
538 // add <hp,statement,false> in which hp is an element of
540 // of callee: callee has 'read' requirement!
541 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
542 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
544 Hashtable<FlatNode, Boolean> gen = curr.get(read);
546 gen = new Hashtable<FlatNode, Boolean>();
549 Boolean currentStatus = gen.get(fn);
550 if (currentStatus == null) {
551 gen.put(fn, Boolean.FALSE);
553 checkFlag(currentStatus.booleanValue(), fn, read);
557 // removes <hp,statement,flag> if hp is an element of
559 // set of callee. it means that callee will overwrite it
560 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
561 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
562 removeHeapPath(curr, write);
572 private void readValue(FlatNode fn, NTuple<Descriptor> hp,
573 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
574 Hashtable<FlatNode, Boolean> gen = curr.get(hp);
576 gen = new Hashtable<FlatNode, Boolean>();
579 Boolean currentStatus = gen.get(fn);
580 if (currentStatus == null) {
581 gen.put(fn, Boolean.FALSE);
583 checkFlag(currentStatus.booleanValue(), fn, hp);
588 private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
589 NTuple<Descriptor> hp) {
591 // removes all of heap path that starts with prefix 'hp'
592 // since any reference overwrite along heap path gives overwriting side
593 // effects on the value
595 Set<NTuple<Descriptor>> keySet = curr.keySet();
596 for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
597 NTuple<Descriptor> key = iter.next();
598 if (key.startsWith(hp)) {
599 curr.put(key, new Hashtable<FlatNode, Boolean>());
605 private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
606 // compute all possible callee set
607 // transform all READ/OVERWRITE set from the any possible
611 calleeUnionBoundReadSet.clear();
612 calleeIntersectBoundOverWriteSet.clear();
614 MethodDescriptor mdCallee = fc.getMethod();
615 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
616 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
617 TypeDescriptor typeDesc = fc.getThis().getType();
618 setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
620 // create mapping from arg idx to its heap paths
621 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
622 new Hashtable<Integer, NTuple<Descriptor>>();
624 // arg idx is starting from 'this' arg
625 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
626 if (thisHeapPath == null) {
627 // method is called without creating new flat node representing 'this'
628 thisHeapPath = new NTuple<Descriptor>();
629 thisHeapPath.add(fc.getThis());
632 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
634 for (int i = 0; i < fc.numArgs(); i++) {
635 TempDescriptor arg = fc.getArg(i);
636 NTuple<Descriptor> argHeapPath = computePath(arg);
637 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
640 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
641 MethodDescriptor callee = (MethodDescriptor) iterator.next();
642 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
644 // binding caller's args and callee's params
646 Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
647 if (calleeReadSet == null) {
648 calleeReadSet = new HashSet<NTuple<Descriptor>>();
649 mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
651 Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
652 if (calleeOverWriteSet == null) {
653 calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
654 mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
657 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
658 new Hashtable<Integer, TempDescriptor>();
659 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
660 TempDescriptor param = calleeFlatMethod.getParameter(i);
661 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
664 Set<NTuple<Descriptor>> calleeBoundReadSet =
665 bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
666 // union of the current read set and the current callee's
668 calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
669 Set<NTuple<Descriptor>> calleeBoundWriteSet =
670 bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
671 // intersection of the current overwrite set and the current
674 merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
679 private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
682 "There is a variable, which is reachable through references "
684 + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
685 + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
690 private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
691 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
693 Set<NTuple<Descriptor>> inKeySet = in.keySet();
694 for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
695 NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
696 Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
698 Set<FlatNode> pairKeySet = inPair.keySet();
699 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
700 FlatNode pairKey = (FlatNode) iterator2.next();
701 Boolean inFlag = inPair.get(pairKey);
703 Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
704 if (currPair == null) {
705 currPair = new Hashtable<FlatNode, Boolean>();
706 curr.put(inKey, currPair);
709 Boolean currFlag = currPair.get(pairKey);
710 // by default, flag is set by false
711 if (currFlag == null) {
712 currFlag = Boolean.FALSE;
714 currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
715 currPair.put(pairKey, currFlag);
722 private void methodReadOverWriteAnalysis() {
723 // perform method READ/OVERWRITE analysis
724 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
725 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
727 LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
729 // no need to analyze method having ssjava loop
730 methodContainingSSJavaLoop = sortedDescriptors.removeFirst();
732 // current descriptors to visit in fixed-point interprocedural analysis,
734 // dependency in the call graph
735 Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
737 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
738 methodDescriptorToVistSet.addAll(sortedDescriptors);
740 while (!sortedDescriptors.isEmpty()) {
741 MethodDescriptor md = sortedDescriptors.removeFirst();
742 methodDescriptorsToVisitStack.add(md);
745 // analyze scheduled methods until there are no more to visit
746 while (!methodDescriptorsToVisitStack.isEmpty()) {
747 // start to analyze leaf node
748 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
749 FlatMethod fm = state.getMethodFlat(md);
751 Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
752 Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
754 methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
756 Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
757 Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
759 if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
760 mapFlatMethodToRead.put(fm, readSet);
761 mapFlatMethodToOverWrite.put(fm, overWriteSet);
763 // results for callee changed, so enqueue dependents caller for
766 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
767 while (depsItr.hasNext()) {
768 MethodDescriptor methodNext = depsItr.next();
769 if (!methodDescriptorsToVisitStack.contains(methodNext)
770 && methodDescriptorToVistSet.contains(methodNext)) {
771 methodDescriptorsToVisitStack.add(methodNext);
782 private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
783 Set<NTuple<Descriptor>> overWriteSet) {
784 if (state.SSJAVADEBUG) {
785 System.out.println("Definitely written Analyzing: " + fm);
788 // intraprocedural analysis
789 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
790 flatNodesToVisit.add(fm);
792 while (!flatNodesToVisit.isEmpty()) {
793 FlatNode fn = flatNodesToVisit.iterator().next();
794 flatNodesToVisit.remove(fn);
796 Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
798 for (int i = 0; i < fn.numPrev(); i++) {
799 FlatNode prevFn = fn.getPrev(i);
800 Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
806 methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
808 Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
809 if (!curr.equals(writtenSetPrev)) {
810 mapFlatNodeToWrittenSet.put(fn, curr);
811 for (int i = 0; i < fn.numNext(); i++) {
812 FlatNode nn = fn.getNext(i);
813 flatNodesToVisit.add(nn);
821 private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
822 Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
828 case FKind.FlatMethod: {
830 // set up initial heap paths for method parameters
831 FlatMethod fm = (FlatMethod) fn;
832 for (int i = 0; i < fm.numParameters(); i++) {
833 TempDescriptor param = fm.getParameter(i);
834 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
836 mapHeapPath.put(param, heapPath);
841 case FKind.FlatOpNode: {
842 FlatOpNode fon = (FlatOpNode) fn;
843 // for a normal assign node, need to propagate lhs's heap path to
845 if (fon.getOp().getOp() == Operation.ASSIGN) {
849 NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
850 if (rhsHeapPath != null) {
851 mapHeapPath.put(lhs, mapHeapPath.get(rhs));
858 case FKind.FlatFieldNode:
859 case FKind.FlatElementNode: {
863 FlatFieldNode ffn = (FlatFieldNode) fn;
866 fld = ffn.getField();
869 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
870 if (srcHeapPath != null) {
871 // if lhs srcHeapPath is null, it means that it is not reachable from
872 // callee's parameters. so just ignore it
874 NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
875 readingHeapPath.add(fld);
876 mapHeapPath.put(lhs, readingHeapPath);
879 if (fld.getType().isImmutable()) {
880 // if WT doesnot have hp(x.f), add hp(x.f) to READ
881 if (!writtenSet.contains(readingHeapPath)) {
882 readSet.add(readingHeapPath);
886 // need to kill hp(x.f) from WT
887 writtenSet.remove(readingHeapPath);
893 case FKind.FlatSetFieldNode:
894 case FKind.FlatSetElementNode: {
897 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
899 fld = fsfn.getField();
903 NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
904 if (lhsHeapPath != null) {
905 // if lhs heap path is null, it means that it is not reachable from
906 // callee's parameters. so just ignore it
907 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
908 newHeapPath.add(fld);
909 mapHeapPath.put(fld, newHeapPath);
912 // need to add hp(y) to WT
913 writtenSet.add(newHeapPath);
919 case FKind.FlatCall: {
921 FlatCall fc = (FlatCall) fn;
923 bindHeapPathCallerArgWithCaleeParam(fc);
925 // add heap path, which is an element of READ_bound set and is not
927 // element of WT set, to the caller's READ set
928 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
929 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
930 if (!writtenSet.contains(read)) {
934 writtenSet.removeAll(calleeUnionBoundReadSet);
936 // add heap path, which is an element of OVERWRITE_bound set, to the
938 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
939 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
940 writtenSet.add(write);
946 case FKind.FlatExit: {
947 // merge the current written set with OVERWRITE set
948 merge(overWriteSet, writtenSet);
956 private void mergeSharedAnaylsis(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
957 Hashtable<NTuple<Descriptor>, Set<SharedLocState>> in) {
961 private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
962 if (curr.isEmpty()) {
963 // WrittenSet has a special initial value which covers all possible
965 // For the first time of intersection, we can take all previous set
968 // otherwise, current set is the intersection of the two sets
974 // combine two heap path
975 private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
976 NTuple<Descriptor> combined = new NTuple<Descriptor>();
978 for (int i = 0; i < callerIn.size(); i++) {
979 combined.add(callerIn.get(i));
982 // the first element of callee's heap path represents parameter
983 // so we skip the first one since it is already added from caller's heap
985 for (int i = 1; i < calleeIn.size(); i++) {
986 combined.add(calleeIn.get(i));
992 private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
993 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
994 Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
996 Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
998 Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
999 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1000 Integer idx = (Integer) iterator.next();
1002 NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
1003 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1005 for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
1006 NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
1007 if (element.startsWith(calleeParam)) {
1008 NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
1009 boundedCalleeSet.add(boundElement);
1015 return boundedCalleeSet;
1019 // Borrowed it from disjoint analysis
1020 private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
1022 Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1024 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1026 Iterator<MethodDescriptor> itr = toSort.iterator();
1027 while (itr.hasNext()) {
1028 MethodDescriptor d = itr.next();
1030 if (!discovered.contains(d)) {
1031 dfsVisit(d, toSort, sorted, discovered);
1038 // While we're doing DFS on call graph, remember
1039 // dependencies for efficient queuing of methods
1040 // during interprocedural analysis:
1042 // a dependent of a method decriptor d for this analysis is:
1043 // 1) a method or task that invokes d
1044 // 2) in the descriptorsToAnalyze set
1045 private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
1046 LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
1050 // otherwise call graph guides DFS
1051 Iterator itr = callGraph.getCallerSet(md).iterator();
1052 while (itr.hasNext()) {
1053 MethodDescriptor dCaller = (MethodDescriptor) itr.next();
1055 // only consider callers in the original set to analyze
1056 if (!toSort.contains(dCaller)) {
1060 if (!discovered.contains(dCaller)) {
1061 addDependent(md, // callee
1065 dfsVisit(dCaller, toSort, sorted, discovered);
1069 // for leaf-nodes last now!
1073 // a dependent of a method decriptor d for this analysis is:
1074 // 1) a method or task that invokes d
1075 // 2) in the descriptorsToAnalyze set
1076 private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1077 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1079 deps = new HashSet<MethodDescriptor>();
1082 mapDescriptorToSetDependents.put(callee, deps);
1085 private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1086 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1088 deps = new HashSet<MethodDescriptor>();
1089 mapDescriptorToSetDependents.put(callee, deps);
1094 private NTuple<Descriptor> computePath(TempDescriptor td) {
1095 // generate proper path fot input td
1096 // if td is local variable, it just generate one element tuple path
1097 if (mapHeapPath.containsKey(td)) {
1098 return mapHeapPath.get(td);
1100 NTuple<Descriptor> path = new NTuple<Descriptor>();