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;
11 import Analysis.Loops.LoopFinder;
13 import IR.FieldDescriptor;
14 import IR.MethodDescriptor;
17 import IR.TypeDescriptor;
18 import IR.TypeExtension;
20 import IR.Flat.FlatCall;
21 import IR.Flat.FlatElementNode;
22 import IR.Flat.FlatFieldNode;
23 import IR.Flat.FlatLiteralNode;
24 import IR.Flat.FlatMethod;
25 import IR.Flat.FlatNode;
26 import IR.Flat.FlatOpNode;
27 import IR.Flat.FlatSetElementNode;
28 import IR.Flat.FlatSetFieldNode;
29 import IR.Flat.TempDescriptor;
30 import IR.Tree.Modifiers;
33 public class DefinitelyWrittenCheck {
35 SSJavaAnalysis ssjava;
41 // maps a descriptor to its known dependents: namely
42 // methods or tasks that call the descriptor's method
43 // AND are part of this analysis (reachable from main)
44 private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
46 // maps a flat node to its WrittenSet: this keeps all heap path overwritten
48 private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
50 // maps a temp descriptor to its heap path
51 // each temp descriptor has a unique heap path since we do not allow any
53 private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
55 // maps a flat method to the READ that is the set of heap path that is
56 // expected to be written before method invocation
57 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
59 // maps a flat method to the OVERWRITE that is the set of heap path that is
60 // overwritten on every possible path during method invocation
61 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
63 // maps a flat method to the WRITE that is the set of heap path that is
65 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToWrite;
67 // points to method containing SSJAVA Loop
68 private MethodDescriptor methodContainingSSJavaLoop;
70 // maps a flatnode to definitely written analysis mapping M
71 private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
73 // maps a method descriptor to its current summary during the analysis
74 // then analysis reaches fixed-point, this mapping will have the final summary
75 // for each method descriptor
76 private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToCompleteClearingSummary;
78 // maps a method descriptor to the merged incoming caller's current
80 private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToInitialClearingSummary;
82 // maps a flat node to current partial results
83 private Hashtable<FlatNode, ClearingSummary> mapFlatNodeToClearingSummary;
85 // maps shared location to the set of descriptors which belong to the shared
88 // keep current descriptors to visit in fixed-point interprocedural analysis,
89 private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
91 // when analyzing flatcall, need to re-schedule set of callee
92 private Set<MethodDescriptor> calleesToEnqueue;
94 // maps heap path to the mapping of a shared location and the set of reading
96 // it is for setting clearance flag when all read set is overwritten
97 private Hashtable<NTuple<Descriptor>, Hashtable<Location, Set<Descriptor>>> mapHeapPathToLocSharedDescReadSet;
99 public static final String arrayElementFieldName = "___element_";
100 static protected Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField;
102 private Set<ClearingSummary> possibleCalleeCompleteSummarySetToCaller;
104 private LinkedList<MethodDescriptor> sortedDescriptors;
106 private FlatNode ssjavaLoopEntrance;
107 private LoopFinder ssjavaLoop;
108 private Set<FlatNode> loopIncElements;
110 private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
111 private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
112 private Set<NTuple<Descriptor>> calleeBoundWriteSet;
114 private Hashtable<Descriptor, Location> mapDescToLocation;
116 private TempDescriptor LOCAL;
118 public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
120 this.ssjava = ssjava;
121 this.callGraph = ssjava.getCallGraph();
122 this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
123 this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
124 this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
125 this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
126 this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
127 this.mapFlatMethodToWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
128 this.definitelyWrittenResults =
129 new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
130 this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
131 this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
132 this.calleeBoundWriteSet = new HashSet<NTuple<Descriptor>>();
134 this.mapMethodDescriptorToCompleteClearingSummary =
135 new Hashtable<MethodDescriptor, ClearingSummary>();
136 this.mapMethodDescriptorToInitialClearingSummary =
137 new Hashtable<MethodDescriptor, ClearingSummary>();
138 this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
139 this.calleesToEnqueue = new HashSet<MethodDescriptor>();
140 this.possibleCalleeCompleteSummarySetToCaller = new HashSet<ClearingSummary>();
141 this.mapTypeToArrayField = new Hashtable<TypeDescriptor, FieldDescriptor>();
142 this.LOCAL = new TempDescriptor("LOCAL");
143 this.mapDescToLocation = new Hashtable<Descriptor, Location>();
144 this.mapHeapPathToLocSharedDescReadSet =
145 new Hashtable<NTuple<Descriptor>, Hashtable<Location, Set<Descriptor>>>();
148 public void definitelyWrittenCheck() {
149 if (!ssjava.getAnnotationRequireSet().isEmpty()) {
150 methodReadOverWriteAnalysis();
152 sharedLocationAnalysis();
153 checkSharedLocationResult();
157 private void checkSharedLocationResult() {
159 // mapping of method containing ssjava loop has the final result of
160 // shared location analysis
162 ClearingSummary result =
163 mapMethodDescriptorToCompleteClearingSummary.get(methodContainingSSJavaLoop);
165 System.out.println("\n\n#RESULT=" + result);
167 Set<NTuple<Descriptor>> hpKeySet = result.keySet();
168 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
169 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
170 SharedStatus state = result.get(hpKey);
171 Set<Location> locKeySet = state.getLocationSet();
172 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
173 Location locKey = (Location) iterator2.next();
174 if (!state.getFlag(locKey)) {
175 printNotClearedResult(result);
177 "Some concrete locations of the shared abstract location are not cleared at the same time:");
184 private void printNotClearedResult(ClearingSummary result) {
185 Set<NTuple<Descriptor>> keySet = result.keySet();
187 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
188 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
189 SharedStatus status = result.get(hpKey);
190 Hashtable<Location, Pair<Set<Descriptor>, Boolean>> map = status.getMap();
191 Set<Location> locKeySet = map.keySet();
192 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
193 Location locKey = (Location) iterator2.next();
194 Pair<Set<Descriptor>, Boolean> pair = map.get(locKey);
195 if (!pair.getSecond().booleanValue()) {
197 System.out.println("Concrete locations of the shared location '" + locKey
198 + "' are not cleared out, which are reachable through the heap path '" + hpKey + "'");
205 private void sharedLocationAnalysis() {
206 // verify that all concrete locations of shared location are cleared out at
207 // the same time once per the out-most loop
209 computeReadSharedDescriptorSet();
211 System.out.println("###");
212 System.out.println("READ SHARED=" + mapHeapPathToLocSharedDescReadSet);
214 // methodDescriptorsToVisitStack.clear();
215 // methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
217 LinkedList<MethodDescriptor> descriptorListToAnalyze =
218 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
220 // current descriptors to visit in fixed-point interprocedural analysis,
222 // dependency in the call graph
223 methodDescriptorsToVisitStack.clear();
225 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
226 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
228 while (!descriptorListToAnalyze.isEmpty()) {
229 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
230 methodDescriptorsToVisitStack.add(md);
233 // analyze scheduled methods until there are no more to visit
234 while (!methodDescriptorsToVisitStack.isEmpty()) {
235 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
237 ClearingSummary completeSummary =
238 sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
240 ClearingSummary prevCompleteSummary = mapMethodDescriptorToCompleteClearingSummary.get(md);
242 if (!completeSummary.equals(prevCompleteSummary)) {
244 ClearingSummary summaryFromCaller = mapMethodDescriptorToInitialClearingSummary.get(md);
245 // System.out.println("# summaryFromCaller=" + summaryFromCaller);
246 // System.out.println("# completeSummary=" + completeSummary);
247 // System.out.println("# prev=" + prevCompleteSummary);
248 // System.out.println("# changed!\n");
250 mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
252 // results for callee changed, so enqueue dependents caller for
254 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
255 while (depsItr.hasNext()) {
256 MethodDescriptor methodNext = depsItr.next();
257 if (!methodDescriptorsToVisitStack.contains(methodNext)) {
258 methodDescriptorsToVisitStack.add(methodNext);
262 // if there is set of callee to be analyzed,
263 // add this set into the top of stack
264 Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
265 while (calleeIter.hasNext()) {
266 MethodDescriptor mdNext = calleeIter.next();
267 if (!methodDescriptorsToVisitStack.contains(mdNext)) {
268 methodDescriptorsToVisitStack.add(mdNext);
271 calleesToEnqueue.clear();
279 private ClearingSummary sharedLocation_analyzeMethod(MethodDescriptor md,
280 boolean onlyVisitSSJavaLoop) {
282 if (state.SSJAVADEBUG) {
283 System.out.println("Definite clearance for shared locations Analyzing: " + md + " "
284 + onlyVisitSSJavaLoop);
287 FlatMethod fm = state.getMethodFlat(md);
289 // intraprocedural analysis
290 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
292 // start a new mapping of partial results for each flat node
293 mapFlatNodeToClearingSummary = new Hashtable<FlatNode, ClearingSummary>();
295 if (onlyVisitSSJavaLoop) {
296 flatNodesToVisit.add(ssjavaLoopEntrance);
298 flatNodesToVisit.add(fm);
301 Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
303 while (!flatNodesToVisit.isEmpty()) {
304 FlatNode fn = flatNodesToVisit.iterator().next();
305 flatNodesToVisit.remove(fn);
307 ClearingSummary curr = new ClearingSummary();
309 Set<ClearingSummary> prevSet = new HashSet<ClearingSummary>();
310 for (int i = 0; i < fn.numPrev(); i++) {
311 FlatNode prevFn = fn.getPrev(i);
312 ClearingSummary in = mapFlatNodeToClearingSummary.get(prevFn);
317 mergeSharedLocationAnaylsis(curr, prevSet);
319 sharedLocation_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
320 ClearingSummary clearingPrev = mapFlatNodeToClearingSummary.get(fn);
322 if (!curr.equals(clearingPrev)) {
323 mapFlatNodeToClearingSummary.put(fn, curr);
325 for (int i = 0; i < fn.numNext(); i++) {
326 FlatNode nn = fn.getNext(i);
328 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
329 flatNodesToVisit.add(nn);
337 ClearingSummary completeSummary = new ClearingSummary();
338 Set<ClearingSummary> summarySet = new HashSet<ClearingSummary>();
340 if (onlyVisitSSJavaLoop) {
341 // when analyzing ssjava loop,
342 // complete summary is merging of all previous nodes of ssjava loop
344 for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
345 ClearingSummary frnSummary =
346 mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
347 if (frnSummary != null) {
348 summarySet.add(frnSummary);
352 // merging all exit node summary into the complete summary
353 if (!returnNodeSet.isEmpty()) {
354 for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
355 FlatNode frn = (FlatNode) iterator.next();
356 ClearingSummary frnSummary = mapFlatNodeToClearingSummary.get(frn);
357 summarySet.add(frnSummary);
361 mergeSharedLocationAnaylsis(completeSummary, summarySet);
362 return completeSummary;
365 private void sharedLocation_nodeActions(MethodDescriptor caller, FlatNode fn,
366 ClearingSummary curr, Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
373 case FKind.FlatMethod: {
374 FlatMethod fm = (FlatMethod) fn;
376 ClearingSummary summaryFromCaller =
377 mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
379 Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
380 if (summaryFromCaller != null) {
381 inSet.add(summaryFromCaller);
382 mergeSharedLocationAnaylsis(curr, inSet);
388 case FKind.FlatOpNode: {
389 FlatOpNode fon = (FlatOpNode) fn;
393 if (fon.getOp().getOp() == Operation.ASSIGN) {
394 if (rhs.getType().isImmutable() && isSSJavaLoop) {
395 // in ssjavaloop, we need to take care about reading local variables!
396 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
397 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
398 rhsHeapPath.add(LOCAL);
399 lhsHeapPath.add(LOCAL);
400 if (!lhs.getSymbol().startsWith("neverused")) {
401 readLocation(curr, rhsHeapPath, rhs);
402 writeLocation(curr, lhsHeapPath, lhs);
410 case FKind.FlatFieldNode:
411 case FKind.FlatElementNode: {
413 if (fn.kind() == FKind.FlatFieldNode) {
414 FlatFieldNode ffn = (FlatFieldNode) fn;
417 fld = ffn.getField();
419 FlatElementNode fen = (FlatElementNode) fn;
422 TypeDescriptor td = rhs.getType().dereference();
423 fld = getArrayField(td);
427 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
429 if (srcHeapPath != null) {
430 // if lhs srcHeapPath is null, it means that it is not reachable from
431 // callee's parameters. so just ignore it
432 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
434 if (!fld.getType().isArray() && fld.getType().isImmutable()) {
435 readLocation(curr, fldHeapPath, fld);
437 fldHeapPath.add(fld);
438 mapHeapPath.put(lhs, fldHeapPath);
448 case FKind.FlatSetFieldNode:
449 case FKind.FlatSetElementNode: {
451 if (fn.kind() == FKind.FlatSetFieldNode) {
452 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
454 fld = fsfn.getField();
457 FlatSetElementNode fsen = (FlatSetElementNode) fn;
460 TypeDescriptor td = lhs.getType().dereference();
461 fld = getArrayField(td);
465 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
466 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
467 if (fld.getType().isImmutable()) {
468 writeLocation(curr, fldHeapPath, fld);
470 // updates reference field case:
471 // 2. if there exists a tuple t in sharing summary that starts with
472 // hp(x) then, set flag of tuple t to 'true'
473 fldHeapPath.add(fld);
474 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
475 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
476 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
477 if (hpKey.startsWith(fldHeapPath)) {
478 curr.get(hpKey).updateFlag(true);
486 case FKind.FlatCall: {
488 FlatCall fc = (FlatCall) fn;
490 if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
492 // have write effects on the first argument
493 NTuple<Descriptor> argHeapPath = computePath(fc.getArg(0));
494 writeLocation(curr, argHeapPath, fc.getArg(0));
496 // find out the set of callees
497 MethodDescriptor mdCallee = fc.getMethod();
498 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
499 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
500 // TypeDescriptor typeDesc = fc.getThis().getType();
501 setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
503 possibleCalleeCompleteSummarySetToCaller.clear();
505 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
506 MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
507 FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
509 addDependent(mdPossibleCallee, // callee
512 calleesToEnqueue.add(mdPossibleCallee);
514 // updates possible callee's initial summary using caller's current
516 ClearingSummary prevCalleeInitSummary =
517 mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
519 ClearingSummary calleeInitSummary =
520 bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
522 Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
523 if (prevCalleeInitSummary != null) {
524 inSet.add(prevCalleeInitSummary);
525 mergeSharedLocationAnaylsis(calleeInitSummary, inSet);
528 // if changes, update the init summary
529 // and reschedule the callee for analysis
530 if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
531 // System.out.println("#CALLEE INIT CHANGED=" + mdPossibleCallee);
532 // System.out.println("# prev=" + prevCalleeInitSummary);
533 // System.out.println("# current=" + calleeInitSummary);
534 // System.out.println("#");
536 if (!methodDescriptorsToVisitStack.contains(mdPossibleCallee)) {
537 methodDescriptorsToVisitStack.add(mdPossibleCallee);
540 mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
544 // System.out.println("callee " + fc + " summary=" +
545 // possibleCalleeCompleteSummarySetToCaller);
546 // contribute callee's writing effects to the caller
547 mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
553 case FKind.FlatReturnNode: {
554 returnNodeSet.add(fn);
562 private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc,
563 FlatMethod calleeFlatMethod, ClearingSummary curr) {
565 ClearingSummary boundSet = new ClearingSummary();
567 // create mapping from arg idx to its heap paths
568 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
569 new Hashtable<Integer, NTuple<Descriptor>>();
571 if (fc.getThis() != null) {
572 // arg idx is starting from 'this' arg
573 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
574 if (thisHeapPath == null) {
575 // method is called without creating new flat node representing 'this'
576 thisHeapPath = new NTuple<Descriptor>();
577 thisHeapPath.add(fc.getThis());
580 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
583 for (int i = 0; i < fc.numArgs(); i++) {
584 TempDescriptor arg = fc.getArg(i);
585 NTuple<Descriptor> argHeapPath = computePath(arg);
586 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
589 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
590 new Hashtable<Integer, TempDescriptor>();
592 if (calleeFlatMethod.getMethod().isStatic()) {
593 // static method does not have implicit 'this' arg
596 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
597 TempDescriptor param = calleeFlatMethod.getParameter(i);
598 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
601 // binding caller's writing effects to callee's params
602 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
603 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
605 if (argHeapPath != null) {
606 // if method is static, the first argument is nulll because static
607 // method does not have implicit "THIS" arg
608 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
610 // iterate over caller's writing effect set
611 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
612 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
613 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
614 // current element is reachable caller's arg
615 // so need to bind it to the caller's side and add it to the
618 if (hpKey.startsWith(argHeapPath)) {
619 NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
620 boundSet.put(boundHeapPath, curr.get(hpKey).clone());
628 // contribute callee's complete summary into the caller's current summary
629 ClearingSummary calleeCompleteSummary =
630 mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
631 if (calleeCompleteSummary != null) {
632 ClearingSummary boundCalleeEfffects = new ClearingSummary();
633 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
634 // for (int i = 0; i < fc.numArgs(); i++) {
635 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
637 if (argHeapPath != null) {
638 // if method is static, the first argument is nulll because static
639 // method does not have implicit "THIS" arg
640 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
642 // iterate over callee's writing effect set
643 Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
644 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
645 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
646 // current element is reachable caller's arg
647 // so need to bind it to the caller's side and add it to the
650 if (hpKey.startsWith(calleeParamHeapPath)) {
652 NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
654 boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
663 possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
669 private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
671 // replace the head of heap path with caller's arg path
672 // for example, heap path 'param.a.b' in callee's side will be replaced with
673 // (corresponding arg heap path).a.b for caller's side
675 NTuple<Descriptor> bound = new NTuple<Descriptor>();
677 for (int i = 0; i < argHeapPath.size(); i++) {
678 bound.add(argHeapPath.get(i));
681 for (int i = 1; i < hpKey.size(); i++) {
682 bound.add(hpKey.get(i));
688 private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
689 NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
690 // replace the head of caller's heap path with callee's param heap path
692 NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
693 boundHeapPath.add(calleeParamHeapPath);
695 for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
696 boundHeapPath.add(effectHeapPath.get(i));
699 return boundHeapPath;
702 private void computeReadSharedDescriptorSet() {
703 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
704 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
706 for (Iterator iterator = methodDescriptorsToAnalyze.iterator(); iterator.hasNext();) {
707 MethodDescriptor md = (MethodDescriptor) iterator.next();
708 FlatMethod fm = state.getMethodFlat(md);
709 computeReadSharedDescriptorSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
714 private void computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm,
715 boolean onlyVisitSSJavaLoop) {
717 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
718 Set<FlatNode> visited = new HashSet<FlatNode>();
720 if (onlyVisitSSJavaLoop) {
721 flatNodesToVisit.add(ssjavaLoopEntrance);
723 flatNodesToVisit.add(fm);
726 while (!flatNodesToVisit.isEmpty()) {
727 FlatNode fn = flatNodesToVisit.iterator().next();
728 flatNodesToVisit.remove(fn);
731 computeReadSharedDescriptorSet_nodeActions(fn, onlyVisitSSJavaLoop);
733 for (int i = 0; i < fn.numNext(); i++) {
734 FlatNode nn = fn.getNext(i);
735 if (!visited.contains(nn)) {
736 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
737 flatNodesToVisit.add(nn);
746 private void computeReadSharedDescriptorSet_nodeActions(FlatNode fn, boolean isSSJavaLoop) {
753 case FKind.FlatOpNode: {
754 FlatOpNode fon = (FlatOpNode) fn;
758 if (fon.getOp().getOp() == Operation.ASSIGN) {
759 if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) {
760 // in ssjavaloop, we need to take care about reading local variables!
761 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
762 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
763 rhsHeapPath.add(LOCAL);
764 Location loc = getLocation(rhs);
765 addReadDescriptor(rhsHeapPath, loc, rhs);
772 case FKind.FlatFieldNode:
773 case FKind.FlatElementNode: {
775 if (fn.kind() == FKind.FlatFieldNode) {
776 FlatFieldNode ffn = (FlatFieldNode) fn;
779 fld = ffn.getField();
781 FlatElementNode fen = (FlatElementNode) fn;
784 TypeDescriptor td = rhs.getType().dereference();
785 fld = getArrayField(td);
788 if (fld.isStatic() && fld.isFinal()) {
793 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
794 if (srcHeapPath != null) {
795 // if srcHeapPath is null, it means that it is not reachable from
796 // callee's parameters. so just ignore it
798 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
800 if (!fld.getType().isArray() && fld.getType().isImmutable()) {
803 if (fn.kind() == FKind.FlatElementNode) {
804 loc = mapDescToLocation.get(rhs);
806 loc = getLocation(fld);
809 addReadDescriptor(fldHeapPath, loc, fld);
811 // propagate rhs's heap path to the lhs
813 if (fn.kind() == FKind.FlatElementNode) {
814 mapDescToLocation.put(lhs, getLocation(rhs));
817 fldHeapPath.add(fld);
818 mapHeapPath.put(lhs, fldHeapPath);
826 case FKind.FlatSetFieldNode:
827 case FKind.FlatSetElementNode: {
829 if (fn.kind() == FKind.FlatSetFieldNode) {
830 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
832 fld = fsfn.getField();
834 FlatSetElementNode fsen = (FlatSetElementNode) fn;
837 TypeDescriptor td = lhs.getType().dereference();
838 fld = getArrayField(td);
842 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
843 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
844 // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
849 case FKind.FlatCall: {
851 FlatCall fc = (FlatCall) fn;
853 if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
855 // have write effects on the first argument
856 NTuple<Descriptor> argHeapPath = computePath(fc.getArg(0));
857 Location loc = getLocation(fc.getArg(0));
858 addReadDescriptor(argHeapPath, loc, fc.getArg(0));
866 private boolean hasReadingEffectOnSharedLocation(NTuple<Descriptor> hp, Location loc, Descriptor d) {
868 Hashtable<Location, Set<Descriptor>> mapLocToDescSet =
869 mapHeapPathToLocSharedDescReadSet.get(hp);
870 if (mapLocToDescSet == null) {
873 Set<Descriptor> setDesc = mapLocToDescSet.get(loc);
874 if (setDesc == null) {
877 return setDesc.contains(d);
883 private void addReadDescriptor(NTuple<Descriptor> hp, Location loc, Descriptor d) {
885 if (loc != null && ssjava.isSharedLocation(loc)) {
886 Hashtable<Location, Set<Descriptor>> mapLocToDescSet =
887 mapHeapPathToLocSharedDescReadSet.get(hp);
888 if (mapLocToDescSet == null) {
889 mapLocToDescSet = new Hashtable<Location, Set<Descriptor>>();
890 mapHeapPathToLocSharedDescReadSet.put(hp, mapLocToDescSet);
892 Set<Descriptor> descSet = mapLocToDescSet.get(loc);
893 if (descSet == null) {
894 descSet = new HashSet<Descriptor>();
895 mapLocToDescSet.put(loc, descSet);
902 private Location getLocation(Descriptor d) {
904 if (d instanceof FieldDescriptor) {
905 TypeExtension te = ((FieldDescriptor) d).getType().getExtension();
907 return (Location) te;
910 assert d instanceof TempDescriptor;
911 TempDescriptor td = (TempDescriptor) d;
913 TypeExtension te = td.getType().getExtension();
915 if (te instanceof CompositeLocation) {
916 CompositeLocation comp = (CompositeLocation) te;
918 return comp.get(comp.getSize() - 1);
920 return (Location) te;
925 return mapDescToLocation.get(d);
928 private void writeLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
930 Location loc = getLocation(d);
931 // System.out.println("# WRITE LOC hp=" + hp + " d=" + d);
933 if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
934 // 1. add field x to the clearing set
935 SharedStatus state = getState(curr, hp);
936 state.addVar(loc, d);
938 // 3. if the set v contains all of variables belonging to the shared
939 // location, set flag to true
940 if (overwrittenAllSharedConcreteLocation(hp, loc, state.getVarSet(loc))) {
941 state.updateFlag(loc, true);
944 // System.out.println("# WRITE CURR=" + curr);
948 private boolean overwrittenAllSharedConcreteLocation(NTuple<Descriptor> hp, Location loc,
949 Set<Descriptor> writtenSet) {
951 Hashtable<Location, Set<Descriptor>> mapLocToDescSet =
952 mapHeapPathToLocSharedDescReadSet.get(hp);
954 if (mapLocToDescSet != null) {
955 Set<Descriptor> descSet = mapLocToDescSet.get(loc);
956 if (writtenSet.containsAll(descSet)) {
966 private void readLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
967 // remove reading var x from written set
968 Location loc = getLocation(d);
969 // System.out.println("# READ LOC hp="+hp+" d="+d);
970 if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
971 SharedStatus state = getState(curr, hp);
972 state.removeVar(loc, d);
974 // System.out.println("# READ CURR="+curr);
977 private SharedStatus getState(ClearingSummary curr, NTuple<Descriptor> hp) {
978 SharedStatus state = curr.get(hp);
980 state = new SharedStatus();
986 private void writtenAnalyis() {
987 // perform second stage analysis: intraprocedural analysis ensure that
989 // variables are definitely written in-between the same read
991 // First, identify ssjava loop entrace
992 FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
993 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
994 flatNodesToVisit.add(fm);
996 LoopFinder loopFinder = new LoopFinder(fm);
998 while (!flatNodesToVisit.isEmpty()) {
999 FlatNode fn = flatNodesToVisit.iterator().next();
1000 flatNodesToVisit.remove(fn);
1002 String label = (String) state.fn2labelMap.get(fn);
1003 if (label != null) {
1005 if (label.equals(ssjava.SSJAVA)) {
1006 ssjavaLoopEntrance = fn;
1011 for (int i = 0; i < fn.numNext(); i++) {
1012 FlatNode nn = fn.getNext(i);
1013 flatNodesToVisit.add(nn);
1017 assert ssjavaLoopEntrance != null;
1019 // assume that ssjava loop is top-level loop in method, not nested loop
1020 Set nestedLoop = loopFinder.nestedLoops();
1021 for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
1022 LoopFinder lf = (LoopFinder) loopIter.next();
1023 if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
1028 assert ssjavaLoop != null;
1030 writtenAnalysis_analyzeLoop();
1032 if (debugcount > 0) {
1038 private void writtenAnalysis_analyzeLoop() {
1040 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1041 flatNodesToVisit.add(ssjavaLoopEntrance);
1043 loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
1045 while (!flatNodesToVisit.isEmpty()) {
1046 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1047 flatNodesToVisit.remove(fn);
1049 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
1050 definitelyWrittenResults.get(fn);
1052 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
1053 new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
1054 for (int i = 0; i < fn.numPrev(); i++) {
1055 FlatNode nn = fn.getPrev(i);
1056 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
1057 definitelyWrittenResults.get(nn);
1063 writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
1065 // if a new result, schedule forward nodes for analysis
1066 if (!curr.equals(prev)) {
1067 definitelyWrittenResults.put(fn, curr);
1069 for (int i = 0; i < fn.numNext(); i++) {
1070 FlatNode nn = fn.getNext(i);
1071 if (loopIncElements.contains(nn)) {
1072 flatNodesToVisit.add(nn);
1080 private void writtenAnalysis_nodeAction(FlatNode fn,
1081 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
1083 if (fn.equals(loopEntrance)) {
1084 // it reaches loop entrance: changes all flag to true
1085 Set<NTuple<Descriptor>> keySet = curr.keySet();
1086 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1087 NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
1088 Hashtable<FlatNode, Boolean> pair = curr.get(key);
1090 Set<FlatNode> pairKeySet = pair.keySet();
1091 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1092 FlatNode pairKey = (FlatNode) iterator2.next();
1093 pair.put(pairKey, Boolean.TRUE);
1100 FieldDescriptor fld;
1102 switch (fn.kind()) {
1103 case FKind.FlatOpNode: {
1104 FlatOpNode fon = (FlatOpNode) fn;
1105 lhs = fon.getDest();
1106 rhs = fon.getLeft();
1108 NTuple<Descriptor> rhsHeapPath = computePath(rhs);
1109 if (!rhs.getType().isImmutable()) {
1110 mapHeapPath.put(lhs, rhsHeapPath);
1112 if (fon.getOp().getOp() == Operation.ASSIGN) {
1114 readValue(fn, rhsHeapPath, curr);
1117 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1118 removeHeapPath(curr, lhsHeapPath);
1123 case FKind.FlatLiteralNode: {
1124 FlatLiteralNode fln = (FlatLiteralNode) fn;
1128 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1129 removeHeapPath(curr, lhsHeapPath);
1134 case FKind.FlatFieldNode:
1135 case FKind.FlatElementNode: {
1137 if (fn.kind() == FKind.FlatFieldNode) {
1138 FlatFieldNode ffn = (FlatFieldNode) fn;
1141 fld = ffn.getField();
1143 FlatElementNode fen = (FlatElementNode) fn;
1146 TypeDescriptor td = rhs.getType().dereference();
1147 fld = getArrayField(td);
1150 if (fld.isFinal() /* && fld.isStatic() */) {
1151 // if field is final and static, no need to check
1156 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1157 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1158 fldHeapPath.add(fld);
1160 if (fld.getType().isImmutable()) {
1161 readValue(fn, fldHeapPath, curr);
1164 // propagate rhs's heap path to the lhs
1165 mapHeapPath.put(lhs, fldHeapPath);
1170 case FKind.FlatSetFieldNode:
1171 case FKind.FlatSetElementNode: {
1173 if (fn.kind() == FKind.FlatSetFieldNode) {
1174 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1175 lhs = fsfn.getDst();
1176 fld = fsfn.getField();
1178 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1179 lhs = fsen.getDst();
1180 rhs = fsen.getSrc();
1181 TypeDescriptor td = lhs.getType().dereference();
1182 fld = getArrayField(td);
1186 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1187 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1188 fldHeapPath.add(fld);
1189 removeHeapPath(curr, fldHeapPath);
1194 case FKind.FlatCall: {
1195 FlatCall fc = (FlatCall) fn;
1197 bindHeapPathCallerArgWithCaleeParam(fc);
1198 // add <hp,statement,false> in which hp is an element of
1200 // of callee: callee has 'read' requirement!
1202 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1203 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1204 Hashtable<FlatNode, Boolean> gen = curr.get(read);
1206 gen = new Hashtable<FlatNode, Boolean>();
1207 curr.put(read, gen);
1209 Boolean currentStatus = gen.get(fn);
1210 if (currentStatus == null) {
1211 gen.put(fn, Boolean.FALSE);
1213 checkFlag(currentStatus.booleanValue(), fn, read);
1217 // removes <hp,statement,flag> if hp is an element of
1219 // set of callee. it means that callee will overwrite it
1220 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1221 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1222 removeHeapPath(curr, write);
1232 private void readValue(FlatNode fn, NTuple<Descriptor> hp,
1233 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
1234 Hashtable<FlatNode, Boolean> gen = curr.get(hp);
1236 gen = new Hashtable<FlatNode, Boolean>();
1239 Boolean currentStatus = gen.get(fn);
1240 if (currentStatus == null) {
1241 gen.put(fn, Boolean.FALSE);
1243 checkFlag(currentStatus.booleanValue(), fn, hp);
1248 private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1249 NTuple<Descriptor> hp) {
1251 // removes all of heap path that starts with prefix 'hp'
1252 // since any reference overwrite along heap path gives overwriting side
1253 // effects on the value
1255 Set<NTuple<Descriptor>> keySet = curr.keySet();
1256 for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
1257 NTuple<Descriptor> key = iter.next();
1258 if (key.startsWith(hp)) {
1259 curr.put(key, new Hashtable<FlatNode, Boolean>());
1265 private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
1266 // compute all possible callee set
1267 // transform all READ/OVERWRITE set from the any possible
1270 calleeUnionBoundReadSet.clear();
1271 calleeIntersectBoundOverWriteSet.clear();
1272 calleeBoundWriteSet.clear();
1274 if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
1275 // ssjava util case!
1276 // have write effects on the first argument
1277 TempDescriptor arg = fc.getArg(0);
1278 NTuple<Descriptor> argHeapPath = computePath(arg);
1279 calleeIntersectBoundOverWriteSet.add(argHeapPath);
1281 MethodDescriptor mdCallee = fc.getMethod();
1282 // FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1283 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1284 // setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
1285 setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1287 // create mapping from arg idx to its heap paths
1288 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1289 new Hashtable<Integer, NTuple<Descriptor>>();
1291 // arg idx is starting from 'this' arg
1292 if (fc.getThis() != null) {
1293 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1294 if (thisHeapPath == null) {
1295 // method is called without creating new flat node representing 'this'
1296 thisHeapPath = new NTuple<Descriptor>();
1297 thisHeapPath.add(fc.getThis());
1300 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1303 for (int i = 0; i < fc.numArgs(); i++) {
1304 TempDescriptor arg = fc.getArg(i);
1305 NTuple<Descriptor> argHeapPath = computePath(arg);
1306 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1309 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1310 MethodDescriptor callee = (MethodDescriptor) iterator.next();
1311 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1313 // binding caller's args and callee's params
1315 Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
1316 if (calleeReadSet == null) {
1317 calleeReadSet = new HashSet<NTuple<Descriptor>>();
1318 mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
1321 Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
1323 if (calleeOverWriteSet == null) {
1324 calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
1325 mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
1328 Set<NTuple<Descriptor>> calleeWriteSet = mapFlatMethodToWrite.get(calleeFlatMethod);
1330 if (calleeWriteSet == null) {
1331 calleeWriteSet = new HashSet<NTuple<Descriptor>>();
1332 mapFlatMethodToWrite.put(calleeFlatMethod, calleeWriteSet);
1335 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1336 new Hashtable<Integer, TempDescriptor>();
1338 if (calleeFlatMethod.getMethod().isStatic()) {
1339 // static method does not have implicit 'this' arg
1342 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1343 TempDescriptor param = calleeFlatMethod.getParameter(i);
1344 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
1347 Set<NTuple<Descriptor>> calleeBoundReadSet =
1348 bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1349 // union of the current read set and the current callee's
1351 calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1352 Set<NTuple<Descriptor>> calleeBoundOverWriteSet =
1353 bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1354 // intersection of the current overwrite set and the current
1357 merge(calleeIntersectBoundOverWriteSet, calleeBoundOverWriteSet);
1359 Set<NTuple<Descriptor>> boundWriteSetFromCallee =
1360 bindSet(calleeWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1361 calleeBoundWriteSet.addAll(boundWriteSetFromCallee);
1368 private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1370 // the definitely written analysis only takes care about locations that
1371 // are written to inside of the SSJava loop
1372 for (Iterator iterator = calleeBoundWriteSet.iterator(); iterator.hasNext();) {
1373 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1374 if (hp.startsWith(write)) {
1375 // it has write effect!
1379 + "There is a variable, which is reachable through references "
1381 + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1382 + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1390 private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1391 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
1393 Set<NTuple<Descriptor>> inKeySet = in.keySet();
1394 for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1395 NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1396 Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
1398 Set<FlatNode> pairKeySet = inPair.keySet();
1399 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1400 FlatNode pairKey = (FlatNode) iterator2.next();
1401 Boolean inFlag = inPair.get(pairKey);
1403 Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
1404 if (currPair == null) {
1405 currPair = new Hashtable<FlatNode, Boolean>();
1406 curr.put(inKey, currPair);
1409 Boolean currFlag = currPair.get(pairKey);
1410 // by default, flag is set by false
1411 if (currFlag == null) {
1412 currFlag = Boolean.FALSE;
1414 currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
1415 currPair.put(pairKey, currFlag);
1422 private void methodReadOverWriteAnalysis() {
1423 // perform method READ/OVERWRITE analysis
1424 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1425 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1427 sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1429 LinkedList<MethodDescriptor> descriptorListToAnalyze =
1430 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1432 // no need to analyze method having ssjava loop
1433 // methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
1434 methodContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop();
1436 // current descriptors to visit in fixed-point interprocedural analysis,
1438 // dependency in the call graph
1439 methodDescriptorsToVisitStack.clear();
1441 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1442 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1444 while (!descriptorListToAnalyze.isEmpty()) {
1445 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1446 methodDescriptorsToVisitStack.add(md);
1449 // analyze scheduled methods until there are no more to visit
1450 while (!methodDescriptorsToVisitStack.isEmpty()) {
1451 // start to analyze leaf node
1452 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1453 FlatMethod fm = state.getMethodFlat(md);
1455 Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1456 Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
1457 Set<NTuple<Descriptor>> writeSet = new HashSet<NTuple<Descriptor>>();
1459 methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet, writeSet);
1461 Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
1462 Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
1463 Set<NTuple<Descriptor>> prevWrite = mapFlatMethodToWrite.get(fm);
1465 if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite) && writeSet
1466 .equals(prevWrite))) {
1467 mapFlatMethodToRead.put(fm, readSet);
1468 mapFlatMethodToOverWrite.put(fm, overWriteSet);
1469 mapFlatMethodToWrite.put(fm, writeSet);
1471 // results for callee changed, so enqueue dependents caller for
1474 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1475 while (depsItr.hasNext()) {
1476 MethodDescriptor methodNext = depsItr.next();
1477 if (!methodDescriptorsToVisitStack.contains(methodNext)
1478 && methodDescriptorToVistSet.contains(methodNext)) {
1479 methodDescriptorsToVisitStack.add(methodNext);
1490 private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1491 Set<NTuple<Descriptor>> overWriteSet, Set<NTuple<Descriptor>> writeSet) {
1492 if (state.SSJAVADEBUG) {
1493 System.out.println("Definitely written Analyzing: " + fm);
1496 // intraprocedural analysis
1497 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1498 flatNodesToVisit.add(fm);
1500 while (!flatNodesToVisit.isEmpty()) {
1501 FlatNode fn = flatNodesToVisit.iterator().next();
1502 flatNodesToVisit.remove(fn);
1504 Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
1506 for (int i = 0; i < fn.numPrev(); i++) {
1507 FlatNode prevFn = fn.getPrev(i);
1508 Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
1514 methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet, writeSet);
1516 Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
1517 if (!curr.equals(writtenSetPrev)) {
1518 mapFlatNodeToWrittenSet.put(fn, curr);
1519 for (int i = 0; i < fn.numNext(); i++) {
1520 FlatNode nn = fn.getNext(i);
1521 flatNodesToVisit.add(nn);
1529 private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
1530 Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet,
1531 Set<NTuple<Descriptor>> writeSet) {
1534 FieldDescriptor fld;
1536 switch (fn.kind()) {
1537 case FKind.FlatMethod: {
1539 // set up initial heap paths for method parameters
1540 FlatMethod fm = (FlatMethod) fn;
1541 for (int i = 0; i < fm.numParameters(); i++) {
1542 TempDescriptor param = fm.getParameter(i);
1543 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1544 heapPath.add(param);
1545 mapHeapPath.put(param, heapPath);
1550 case FKind.FlatOpNode: {
1551 FlatOpNode fon = (FlatOpNode) fn;
1552 // for a normal assign node, need to propagate lhs's heap path to
1554 if (fon.getOp().getOp() == Operation.ASSIGN) {
1555 rhs = fon.getLeft();
1556 lhs = fon.getDest();
1558 NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1559 if (rhsHeapPath != null) {
1560 mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1567 case FKind.FlatElementNode:
1568 case FKind.FlatFieldNode: {
1572 if (fn.kind() == FKind.FlatFieldNode) {
1573 FlatFieldNode ffn = (FlatFieldNode) fn;
1576 fld = ffn.getField();
1578 FlatElementNode fen = (FlatElementNode) fn;
1581 TypeDescriptor td = rhs.getType().dereference();
1582 fld = getArrayField(td);
1585 if (fld.isFinal() /* && fld.isStatic() */) {
1586 // if field is final and static, no need to check
1591 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1592 if (srcHeapPath != null) {
1593 // if lhs srcHeapPath is null, it means that it is not reachable from
1594 // callee's parameters. so just ignore it
1596 NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1597 readingHeapPath.add(fld);
1598 mapHeapPath.put(lhs, readingHeapPath);
1601 if (fld.getType().isImmutable()) {
1602 // if WT doesnot have hp(x.f), add hp(x.f) to READ
1603 if (!writtenSet.contains(readingHeapPath)) {
1604 readSet.add(readingHeapPath);
1608 // no need to kill hp(x.f) from WT
1614 case FKind.FlatSetFieldNode:
1615 case FKind.FlatSetElementNode: {
1619 if (fn.kind() == FKind.FlatSetFieldNode) {
1620 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1621 lhs = fsfn.getDst();
1622 fld = fsfn.getField();
1623 rhs = fsfn.getSrc();
1625 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1626 lhs = fsen.getDst();
1627 rhs = fsen.getSrc();
1628 TypeDescriptor td = lhs.getType().dereference();
1629 fld = getArrayField(td);
1633 NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1634 if (lhsHeapPath != null) {
1635 // if lhs heap path is null, it means that it is not reachable from
1636 // callee's parameters. so just ignore it
1637 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1638 newHeapPath.add(fld);
1639 mapHeapPath.put(fld, newHeapPath);
1642 // need to add hp(y) to WT
1643 writtenSet.add(newHeapPath);
1645 writeSet.add(newHeapPath);
1651 case FKind.FlatCall: {
1653 FlatCall fc = (FlatCall) fn;
1655 bindHeapPathCallerArgWithCaleeParam(fc);
1657 // add heap path, which is an element of READ_bound set and is not
1659 // element of WT set, to the caller's READ set
1660 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1661 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1662 if (!writtenSet.contains(read)) {
1667 // add heap path, which is an element of OVERWRITE_bound set, to the
1669 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1670 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1671 writtenSet.add(write);
1674 // add heap path, which is an element of WRITE_BOUND set, to the
1675 // caller's writeSet
1676 for (Iterator iterator = calleeBoundWriteSet.iterator(); iterator.hasNext();) {
1677 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1678 writeSet.add(write);
1684 case FKind.FlatExit: {
1685 // merge the current written set with OVERWRITE set
1686 merge(overWriteSet, writtenSet);
1694 static public FieldDescriptor getArrayField(TypeDescriptor td) {
1695 FieldDescriptor fd = mapTypeToArrayField.get(td);
1698 new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), td, arrayElementFieldName, null,
1700 mapTypeToArrayField.put(td, fd);
1705 private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
1706 if (inSet.size() == 0) {
1709 Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
1710 new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
1712 for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1714 ClearingSummary inTable = (ClearingSummary) inIterator.next();
1716 Set<NTuple<Descriptor>> keySet = inTable.keySet();
1718 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1719 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1720 SharedStatus inState = inTable.get(hpKey);
1721 SharedStatus currState = curr.get(hpKey);
1722 if (currState == null) {
1723 currState = new SharedStatus();
1724 curr.put(hpKey, currState);
1727 currState.merge(inState);
1729 Set<Location> locSet = inState.getMap().keySet();
1730 for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
1731 Location loc = (Location) iterator2.next();
1732 Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
1733 boolean inFlag = pair.getSecond().booleanValue();
1735 Pair<NTuple<Descriptor>, Location> flagKey =
1736 new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
1737 Boolean current = mapHeapPathLoc2Flag.get(flagKey);
1738 if (current == null) {
1739 current = new Boolean(true);
1741 boolean newInFlag = current.booleanValue() & inFlag;
1742 mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
1749 // merge flag status
1750 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
1751 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
1752 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1753 SharedStatus currState = curr.get(hpKey);
1754 Set<Location> locKeySet = currState.getMap().keySet();
1755 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
1756 Location locKey = (Location) iterator2.next();
1757 Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
1758 boolean currentFlag = pair.getSecond().booleanValue();
1759 Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
1760 if (inFlag != null) {
1761 boolean newFlag = currentFlag | inFlag.booleanValue();
1762 if (currentFlag != newFlag) {
1763 currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
1771 private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
1772 if (curr.isEmpty()) {
1773 // WrittenSet has a special initial value which covers all possible
1775 // For the first time of intersection, we can take all previous set
1778 // otherwise, current set is the intersection of the two sets
1784 // combine two heap path
1785 private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
1786 NTuple<Descriptor> combined = new NTuple<Descriptor>();
1788 for (int i = 0; i < callerIn.size(); i++) {
1789 combined.add(callerIn.get(i));
1792 // the first element of callee's heap path represents parameter
1793 // so we skip the first one since it is already added from caller's heap
1795 for (int i = 1; i < calleeIn.size(); i++) {
1796 combined.add(calleeIn.get(i));
1802 private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
1803 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
1804 Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
1806 Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
1808 Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
1809 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1810 Integer idx = (Integer) iterator.next();
1812 NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
1813 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1814 for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
1815 NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
1816 if (element.startsWith(calleeParam)) {
1817 NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
1818 boundedCalleeSet.add(boundElement);
1824 return boundedCalleeSet;
1828 // Borrowed it from disjoint analysis
1829 private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
1831 Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1833 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1835 Iterator<MethodDescriptor> itr = toSort.iterator();
1836 while (itr.hasNext()) {
1837 MethodDescriptor d = itr.next();
1839 if (!discovered.contains(d)) {
1840 dfsVisit(d, toSort, sorted, discovered);
1847 // While we're doing DFS on call graph, remember
1848 // dependencies for efficient queuing of methods
1849 // during interprocedural analysis:
1851 // a dependent of a method decriptor d for this analysis is:
1852 // 1) a method or task that invokes d
1853 // 2) in the descriptorsToAnalyze set
1854 private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
1855 LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
1859 Iterator itr = callGraph.getCallerSet(md).iterator();
1860 while (itr.hasNext()) {
1861 MethodDescriptor dCaller = (MethodDescriptor) itr.next();
1862 // only consider callers in the original set to analyze
1863 if (!toSort.contains(dCaller)) {
1866 if (!discovered.contains(dCaller)) {
1867 addDependent(md, // callee
1871 dfsVisit(dCaller, toSort, sorted, discovered);
1875 // for leaf-nodes last now!
1879 // a dependent of a method decriptor d for this analysis is:
1880 // 1) a method or task that invokes d
1881 // 2) in the descriptorsToAnalyze set
1882 private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1883 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1885 deps = new HashSet<MethodDescriptor>();
1888 mapDescriptorToSetDependents.put(callee, deps);
1891 private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1892 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1894 deps = new HashSet<MethodDescriptor>();
1895 mapDescriptorToSetDependents.put(callee, deps);
1900 private NTuple<Descriptor> computePath(TempDescriptor td) {
1901 // generate proper path fot input td
1902 // if td is local variable, it just generate one element tuple path
1903 if (mapHeapPath.containsKey(td)) {
1904 return mapHeapPath.get(td);
1906 NTuple<Descriptor> path = new NTuple<Descriptor>();