1 package Analysis.SSJava;
3 import java.io.BufferedWriter;
4 import java.io.FileWriter;
5 import java.io.IOException;
6 import java.util.HashSet;
7 import java.util.Hashtable;
8 import java.util.Iterator;
9 import java.util.LinkedList;
11 import java.util.Stack;
13 import Analysis.CallGraph.CallGraph;
14 import Analysis.Loops.LoopFinder;
15 import IR.ClassDescriptor;
17 import IR.FieldDescriptor;
18 import IR.MethodDescriptor;
21 import IR.TypeDescriptor;
22 import IR.TypeExtension;
24 import IR.Flat.FlatCall;
25 import IR.Flat.FlatElementNode;
26 import IR.Flat.FlatFieldNode;
27 import IR.Flat.FlatLiteralNode;
28 import IR.Flat.FlatMethod;
29 import IR.Flat.FlatNode;
30 import IR.Flat.FlatOpNode;
31 import IR.Flat.FlatSetElementNode;
32 import IR.Flat.FlatSetFieldNode;
33 import IR.Flat.TempDescriptor;
34 import IR.Tree.Modifiers;
37 public class DefinitelyWrittenCheck {
39 SSJavaAnalysis ssjava;
45 // maps a descriptor to its known dependents: namely
46 // methods or tasks that call the descriptor's method
47 // AND are part of this analysis (reachable from main)
48 private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
50 // maps a flat node to its WrittenSet: this keeps all heap path overwritten
52 private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
54 // maps a temp descriptor to its heap path
55 // each temp descriptor has a unique heap path since we do not allow any
57 private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
59 // maps a flat method to the READ that is the set of heap path that is
60 // expected to be written before method invocation
61 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
63 // maps a flat method to the OVERWRITE that is the set of heap path that is
64 // overwritten on every possible path during method invocation
65 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
67 // maps a flat method to the WRITE that is the set of heap path that is
69 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToWrite;
71 // points to method containing SSJAVA Loop
72 private MethodDescriptor methodContainingSSJavaLoop;
74 // maps a flatnode to definitely written analysis mapping M
75 private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
77 // maps a method descriptor to its current summary during the analysis
78 // then analysis reaches fixed-point, this mapping will have the final summary
79 // for each method descriptor
80 private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToCompleteClearingSummary;
82 // maps a method descriptor to the merged incoming caller's current
84 private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToInitialClearingSummary;
86 // maps a flat node to current partial results
87 private Hashtable<FlatNode, ClearingSummary> mapFlatNodeToClearingSummary;
89 private Hashtable<FlatNode, ReadSummary> mapFlatNodeToReadSummary;
91 // maps shared location to the set of descriptors which belong to the shared
94 // keep current descriptors to visit in fixed-point interprocedural analysis,
95 private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
97 // when analyzing flatcall, need to re-schedule set of callee
98 private Set<MethodDescriptor> calleesToEnqueue;
100 private Set<ReadSummary> possibleCalleeReadSummarySetToCaller;
102 public static final String arrayElementFieldName = "___element_";
103 static protected Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField;
105 private Set<ClearingSummary> possibleCalleeCompleteSummarySetToCaller;
107 // maps a method descriptor to the merged incoming caller's current
109 // it is for setting clearance flag when all read set is overwritten
110 private Hashtable<MethodDescriptor, ReadSummary> mapMethodDescriptorToReadSummary;
112 private LinkedList<MethodDescriptor> sortedDescriptors;
114 private FlatNode ssjavaLoopEntrance;
115 private LoopFinder ssjavaLoop;
116 private Set<FlatNode> loopIncElements;
118 private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
119 private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
120 private Set<NTuple<Descriptor>> calleeBoundWriteSet;
122 private Hashtable<Descriptor, Location> mapDescToLocation;
124 private TempDescriptor LOCAL;
126 public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
128 this.ssjava = ssjava;
129 this.callGraph = ssjava.getCallGraph();
130 this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
131 this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
132 this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
133 this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
134 this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
135 this.mapFlatMethodToWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
136 this.definitelyWrittenResults =
137 new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
138 this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
139 this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
140 this.calleeBoundWriteSet = new HashSet<NTuple<Descriptor>>();
142 this.mapMethodDescriptorToCompleteClearingSummary =
143 new Hashtable<MethodDescriptor, ClearingSummary>();
144 this.mapMethodDescriptorToInitialClearingSummary =
145 new Hashtable<MethodDescriptor, ClearingSummary>();
146 this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
147 this.calleesToEnqueue = new HashSet<MethodDescriptor>();
148 this.possibleCalleeCompleteSummarySetToCaller = new HashSet<ClearingSummary>();
149 this.mapTypeToArrayField = new Hashtable<TypeDescriptor, FieldDescriptor>();
150 this.LOCAL = new TempDescriptor("LOCAL");
151 this.mapDescToLocation = new Hashtable<Descriptor, Location>();
152 this.possibleCalleeReadSummarySetToCaller = new HashSet<ReadSummary>();
153 this.mapMethodDescriptorToReadSummary = new Hashtable<MethodDescriptor, ReadSummary>();
154 this.mapFlatNodeToReadSummary = new Hashtable<FlatNode, ReadSummary>();
157 public void definitelyWrittenCheck() {
158 if (!ssjava.getAnnotationRequireSet().isEmpty()) {
159 methodReadOverWriteAnalysis();
161 sharedLocationAnalysis();
162 checkSharedLocationResult();
166 private void checkSharedLocationResult() {
168 // mapping of method containing ssjava loop has the final result of
169 // shared location analysis
171 ClearingSummary result =
172 mapMethodDescriptorToCompleteClearingSummary.get(methodContainingSSJavaLoop);
174 String str = generateNotClearedResult(result);
175 if (str.length() > 0) {
177 "Following concrete locations of the shared abstract location are not cleared at the same time:\n"
183 private String generateNotClearedResult(ClearingSummary result) {
184 Set<NTuple<Descriptor>> keySet = result.keySet();
186 StringBuffer str = new StringBuffer();
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 if (status.haveWriteEffect(locKey)) {
195 Pair<Set<Descriptor>, Boolean> pair = map.get(locKey);
196 if (!pair.getSecond().booleanValue()) {
198 str.append("- Concrete locations of the shared location '" + locKey
199 + "' are not cleared out, which are reachable through the heap path '" + hpKey
206 return str.toString();
210 private void writeReadMapFile() {
212 String fileName = "SharedLocationReadMap";
215 BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".txt"));
217 Set<MethodDescriptor> keySet = mapMethodDescriptorToReadSummary.keySet();
218 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
219 MethodDescriptor mdKey = (MethodDescriptor) iterator.next();
220 ReadSummary summary = mapMethodDescriptorToReadSummary.get(mdKey);
221 bw.write("Method " + mdKey + "::\n");
222 bw.write(summary + "\n\n");
225 } catch (IOException e) {
231 private void sharedLocationAnalysis() {
232 // verify that all concrete locations of shared location are cleared out at
233 // the same time once per the out-most loop
235 computeReadSharedDescriptorSet();
237 if (state.SSJAVADEBUG) {
241 // methodDescriptorsToVisitStack.clear();
242 // methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
244 LinkedList<MethodDescriptor> descriptorListToAnalyze =
245 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
247 // current descriptors to visit in fixed-point interprocedural analysis,
249 // dependency in the call graph
250 methodDescriptorsToVisitStack.clear();
252 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
253 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
255 while (!descriptorListToAnalyze.isEmpty()) {
256 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
257 methodDescriptorsToVisitStack.add(md);
260 // analyze scheduled methods until there are no more to visit
261 while (!methodDescriptorsToVisitStack.isEmpty()) {
262 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
264 ClearingSummary completeSummary =
265 sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
267 ClearingSummary prevCompleteSummary = mapMethodDescriptorToCompleteClearingSummary.get(md);
269 if (!completeSummary.equals(prevCompleteSummary)) {
271 mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
273 // results for callee changed, so enqueue dependents caller for
275 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
276 while (depsItr.hasNext()) {
277 MethodDescriptor methodNext = depsItr.next();
278 if (!methodDescriptorsToVisitStack.contains(methodNext)) {
279 methodDescriptorsToVisitStack.add(methodNext);
283 // if there is set of callee to be analyzed,
284 // add this set into the top of stack
285 Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
286 while (calleeIter.hasNext()) {
287 MethodDescriptor mdNext = calleeIter.next();
288 if (!methodDescriptorsToVisitStack.contains(mdNext)) {
289 methodDescriptorsToVisitStack.add(mdNext);
292 calleesToEnqueue.clear();
300 private ClearingSummary sharedLocation_analyzeMethod(MethodDescriptor md,
301 boolean onlyVisitSSJavaLoop) {
303 if (state.SSJAVADEBUG) {
304 System.out.println("SSJAVA: Definite clearance for shared locations Analyzing: " + md);
307 FlatMethod fm = state.getMethodFlat(md);
309 // intraprocedural analysis
310 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
312 // start a new mapping of partial results for each flat node
313 mapFlatNodeToClearingSummary = new Hashtable<FlatNode, ClearingSummary>();
315 if (onlyVisitSSJavaLoop) {
316 flatNodesToVisit.add(ssjavaLoopEntrance);
318 flatNodesToVisit.add(fm);
321 Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
323 while (!flatNodesToVisit.isEmpty()) {
324 FlatNode fn = flatNodesToVisit.iterator().next();
325 flatNodesToVisit.remove(fn);
327 ClearingSummary curr = new ClearingSummary();
329 Set<ClearingSummary> prevSet = new HashSet<ClearingSummary>();
330 for (int i = 0; i < fn.numPrev(); i++) {
331 FlatNode prevFn = fn.getPrev(i);
332 ClearingSummary in = mapFlatNodeToClearingSummary.get(prevFn);
337 mergeSharedLocationAnaylsis(curr, prevSet);
339 sharedLocation_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
340 ClearingSummary clearingPrev = mapFlatNodeToClearingSummary.get(fn);
342 if (!curr.equals(clearingPrev)) {
343 mapFlatNodeToClearingSummary.put(fn, curr);
345 for (int i = 0; i < fn.numNext(); i++) {
346 FlatNode nn = fn.getNext(i);
348 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
349 flatNodesToVisit.add(nn);
357 ClearingSummary completeSummary = new ClearingSummary();
358 Set<ClearingSummary> summarySet = new HashSet<ClearingSummary>();
360 if (onlyVisitSSJavaLoop) {
361 // when analyzing ssjava loop,
362 // complete summary is merging of all previous nodes of ssjava loop
364 for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
365 ClearingSummary frnSummary =
366 mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
367 if (frnSummary != null) {
368 summarySet.add(frnSummary);
372 // merging all exit node summary into the complete summary
373 if (!returnNodeSet.isEmpty()) {
374 for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
375 FlatNode frn = (FlatNode) iterator.next();
376 ClearingSummary frnSummary = mapFlatNodeToClearingSummary.get(frn);
377 summarySet.add(frnSummary);
381 mergeSharedLocationAnaylsis(completeSummary, summarySet);
383 return completeSummary;
386 private void sharedLocation_nodeActions(MethodDescriptor md, FlatNode fn, ClearingSummary curr,
387 Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
394 case FKind.FlatMethod: {
395 FlatMethod fm = (FlatMethod) fn;
397 ClearingSummary summaryFromCaller =
398 mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
400 Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
401 if (summaryFromCaller != null) {
402 inSet.add(summaryFromCaller);
403 mergeSharedLocationAnaylsis(curr, inSet);
409 case FKind.FlatOpNode: {
410 FlatOpNode fon = (FlatOpNode) fn;
414 if (fon.getOp().getOp() == Operation.ASSIGN) {
415 if (rhs.getType().isImmutable() && isSSJavaLoop) {
416 // in ssjavaloop, we need to take care about reading local variables!
417 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
418 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
419 rhsHeapPath.add(LOCAL);
420 lhsHeapPath.add(LOCAL);
421 if (!lhs.getSymbol().startsWith("neverused")) {
422 readLocation(md, curr, rhsHeapPath, getLocation(rhs), rhs);
423 writeLocation(md, curr, lhsHeapPath, getLocation(lhs), lhs);
431 case FKind.FlatFieldNode:
432 case FKind.FlatElementNode: {
434 if (fn.kind() == FKind.FlatFieldNode) {
435 FlatFieldNode ffn = (FlatFieldNode) fn;
438 fld = ffn.getField();
440 FlatElementNode fen = (FlatElementNode) fn;
443 TypeDescriptor td = rhs.getType().dereference();
444 fld = getArrayField(td);
448 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
450 if (srcHeapPath != null) {
451 // if lhs srcHeapPath is null, it means that it is not reachable from
452 // callee's parameters. so just ignore it
453 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
455 if (!fld.getType().isArray() && fld.getType().isImmutable()) {
457 if (fn.kind() == FKind.FlatElementNode) {
458 // array element read case
459 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>();
460 for (int i = 0; i < fldHeapPath.size() - 1; i++) {
461 newHeapPath.add(fldHeapPath.get(i));
464 Descriptor desc = fldHeapPath.get(fldHeapPath.size() - 1);
465 if (desc instanceof FieldDescriptor) {
466 fld = (FieldDescriptor) desc;
467 fldHeapPath = newHeapPath;
468 loc = getLocation(fld);
469 readLocation(md, curr, fldHeapPath, loc, fld);
472 loc = getLocation(fld);
473 readLocation(md, curr, fldHeapPath, loc, fld);
477 if (fn.kind() != FKind.FlatElementNode) {
478 // if it is multi dimensional array, do not need to add heap path
479 // because all accesses from the same array is represented by
481 fldHeapPath.add(fld);
483 mapHeapPath.put(lhs, fldHeapPath);
493 case FKind.FlatSetFieldNode:
494 case FKind.FlatSetElementNode: {
496 if (fn.kind() == FKind.FlatSetFieldNode) {
497 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
499 fld = fsfn.getField();
502 FlatSetElementNode fsen = (FlatSetElementNode) fn;
505 TypeDescriptor td = lhs.getType().dereference();
506 fld = getArrayField(td);
510 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
511 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
512 if (fld.getType().isImmutable()) {
513 writeLocation(md, curr, fldHeapPath, getLocation(fld), fld);
515 Descriptor desc = fldHeapPath.get(fldHeapPath.size() - 1);
516 if (desc instanceof FieldDescriptor) {
517 NTuple<Descriptor> arrayPath = new NTuple<Descriptor>();
518 for (int i = 0; i < fldHeapPath.size() - 1; i++) {
519 arrayPath.add(fldHeapPath.get(i));
521 SharedStatus state = getState(curr, arrayPath);
522 state.setWriteEffect(getLocation(desc));
526 // updates reference field case:
527 fldHeapPath.add(fld);
528 updateWriteEffectOnReferenceField(curr, fldHeapPath);
534 case FKind.FlatCall: {
536 FlatCall fc = (FlatCall) fn;
538 if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
540 // have write effects on the first argument
542 if (fc.getArg(0).getType().isArray()) {
543 // updates reference field case:
544 // 2. if there exists a tuple t in sharing summary that starts with
545 // hp(x) then, set flag of tuple t to 'true'
546 NTuple<Descriptor> argHeapPath = computePath(fc.getArg(0));
548 Location loc = getLocation(fc.getArg(0));
549 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>();
550 for (int i = 0; i < argHeapPath.size() - 1; i++) {
551 newHeapPath.add(argHeapPath.get(i));
553 fld = (FieldDescriptor) argHeapPath.get(argHeapPath.size() - 1);
554 argHeapPath = newHeapPath;
556 writeLocation(md, curr, argHeapPath, loc, fld);
560 // find out the set of callees
561 MethodDescriptor mdCallee = fc.getMethod();
562 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
563 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
564 setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
566 possibleCalleeCompleteSummarySetToCaller.clear();
568 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
569 MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
570 FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
572 addDependent(mdPossibleCallee, // callee
575 calleesToEnqueue.add(mdPossibleCallee);
577 // updates possible callee's initial summary using caller's current
579 ClearingSummary prevCalleeInitSummary =
580 mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
582 ClearingSummary calleeInitSummary =
583 bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
585 Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
586 if (prevCalleeInitSummary != null) {
587 inSet.add(prevCalleeInitSummary);
588 mergeSharedLocationAnaylsis(calleeInitSummary, inSet);
591 // if changes, update the init summary
592 // and reschedule the callee for analysis
593 if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
595 if (!methodDescriptorsToVisitStack.contains(mdPossibleCallee)) {
596 methodDescriptorsToVisitStack.add(mdPossibleCallee);
599 mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
604 // contribute callee's writing effects to the caller
605 mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
612 case FKind.FlatReturnNode: {
613 returnNodeSet.add(fn);
621 private void updateWriteEffectOnReferenceField(ClearingSummary curr, NTuple<Descriptor> heapPath) {
623 // 2. if there exists a tuple t in sharing summary that starts with
624 // hp(x) then, set flag of tuple t to 'true'
625 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
626 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
627 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
628 if (hpKey.startsWith(heapPath)) {
629 curr.get(hpKey).updateFlag(true);
635 private void bindHeapPathReadSummary(FlatCall fc, FlatMethod calleeFlatMethod, ReadSummary curr) {
637 ReadSummary boundSet = new ReadSummary();
639 // create mapping from arg idx to its heap paths
640 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
641 new Hashtable<Integer, NTuple<Descriptor>>();
643 if (fc.getThis() != null) {
644 // arg idx is starting from 'this' arg
645 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
646 if (thisHeapPath == null) {
647 // method is called without creating new flat node representing 'this'
648 thisHeapPath = new NTuple<Descriptor>();
649 thisHeapPath.add(fc.getThis());
652 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
655 for (int i = 0; i < fc.numArgs(); i++) {
656 TempDescriptor arg = fc.getArg(i);
657 NTuple<Descriptor> argHeapPath = computePath(arg);
658 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
661 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
662 new Hashtable<Integer, TempDescriptor>();
664 if (calleeFlatMethod.getMethod().isStatic()) {
665 // static method does not have implicit 'this' arg
668 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
669 TempDescriptor param = calleeFlatMethod.getParameter(i);
670 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
673 // binding caller's read effects to callee's params
674 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
675 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
677 if (argHeapPath != null) {
678 // if method is static, the first argument is nulll because static
679 // method does not have implicit "THIS" arg
680 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
682 // iterate over caller's writing effect set
683 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
684 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
685 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
686 // current element is reachable caller's arg
687 // so need to bind it to the caller's side and add it to the
689 if (hpKey.startsWith(argHeapPath)) {
690 NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
691 boundSet.put(boundHeapPath, curr.get(hpKey));
697 // merge into callee's previous read set
698 ReadSummary calleeSummary = mapMethodDescriptorToReadSummary.get(calleeFlatMethod.getMethod());
699 if (calleeSummary == null) {
700 calleeSummary = new ReadSummary();
701 mapMethodDescriptorToReadSummary.put(calleeFlatMethod.getMethod(), calleeSummary);
703 Set<ReadSummary> inSet = new HashSet<ReadSummary>();
705 mergeReadLocationAnaylsis(calleeSummary, inSet);
707 // contribute callee's read summary into the caller's current summary
708 ReadSummary boundCalleeEfffects = new ReadSummary();
709 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
710 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
712 if (argHeapPath != null) {
713 // if method is static, the first argument is nulll because static
714 // method does not have implicit "THIS" arg
715 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
717 // iterate over callee's writing effect set
718 Set<NTuple<Descriptor>> hpKeySet = calleeSummary.keySet();
719 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
720 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
721 // current element is reachable caller's arg
722 // so need to bind it to the caller's side and add it to the
725 if (hpKey.startsWith(calleeParamHeapPath)) {
727 NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
729 boundCalleeEfffects.put(boundHeapPathForCaller, calleeSummary.get(hpKey));
737 possibleCalleeReadSummarySetToCaller.add(boundCalleeEfffects);
741 private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc,
742 FlatMethod calleeFlatMethod, ClearingSummary curr) {
744 ClearingSummary boundSet = new ClearingSummary();
746 // create mapping from arg idx to its heap paths
747 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
748 new Hashtable<Integer, NTuple<Descriptor>>();
750 if (fc.getThis() != null) {
751 // arg idx is starting from 'this' arg
752 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
753 if (thisHeapPath == null) {
754 // method is called without creating new flat node representing 'this'
755 thisHeapPath = new NTuple<Descriptor>();
756 thisHeapPath.add(fc.getThis());
759 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
762 for (int i = 0; i < fc.numArgs(); i++) {
763 TempDescriptor arg = fc.getArg(i);
764 NTuple<Descriptor> argHeapPath = computePath(arg);
765 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
768 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
769 new Hashtable<Integer, TempDescriptor>();
771 if (calleeFlatMethod.getMethod().isStatic()) {
772 // static method does not have implicit 'this' arg
775 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
776 TempDescriptor param = calleeFlatMethod.getParameter(i);
777 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
780 // binding caller's writing effects to callee's params
781 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
782 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
784 if (argHeapPath != null) {
785 // if method is static, the first argument is nulll because static
786 // method does not have implicit "THIS" arg
787 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
789 // iterate over caller's writing effect set
790 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
791 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
792 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
793 // current element is reachable caller's arg
794 // so need to bind it to the caller's side and add it to the
797 if (hpKey.startsWith(argHeapPath)) {
798 NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
799 boundSet.put(boundHeapPath, curr.get(hpKey).clone());
807 // contribute callee's complete summary into the caller's current summary
808 ClearingSummary calleeCompleteSummary =
809 mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
810 if (calleeCompleteSummary != null) {
811 ClearingSummary boundCalleeEfffects = new ClearingSummary();
812 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
813 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
815 if (argHeapPath != null) {
816 // if method is static, the first argument is nulll because static
817 // method does not have implicit "THIS" arg
818 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
820 // iterate over callee's writing effect set
821 Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
822 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
823 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
824 // current element is reachable caller's arg
825 // so need to bind it to the caller's side and add it to the
828 if (hpKey.startsWith(calleeParamHeapPath)) {
830 NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
832 boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
841 possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
847 private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
849 // replace the head of heap path with caller's arg path
850 // for example, heap path 'param.a.b' in callee's side will be replaced with
851 // (corresponding arg heap path).a.b for caller's side
853 NTuple<Descriptor> bound = new NTuple<Descriptor>();
855 for (int i = 0; i < argHeapPath.size(); i++) {
856 bound.add(argHeapPath.get(i));
859 for (int i = 1; i < hpKey.size(); i++) {
860 bound.add(hpKey.get(i));
866 private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
867 NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
868 // replace the head of caller's heap path with callee's param heap path
870 NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
871 boundHeapPath.add(calleeParamHeapPath);
873 for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
874 boundHeapPath.add(effectHeapPath.get(i));
877 return boundHeapPath;
880 private void computeReadSharedDescriptorSet() {
881 LinkedList<MethodDescriptor> descriptorListToAnalyze =
882 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
884 // current descriptors to visit in fixed-point interprocedural analysis,
886 // dependency in the call graph
887 methodDescriptorsToVisitStack.clear();
889 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
890 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
892 while (!descriptorListToAnalyze.isEmpty()) {
893 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
894 methodDescriptorsToVisitStack.add(md);
897 // analyze scheduled methods until there are no more to visit
898 while (!methodDescriptorsToVisitStack.isEmpty()) {
899 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
901 FlatMethod fm = state.getMethodFlat(md);
902 ReadSummary completeSummary =
903 computeReadSharedDescriptorSet_analyzeMethod(fm, (md.equals(methodContainingSSJavaLoop)));
905 ReadSummary prevCompleteSummary = mapMethodDescriptorToReadSummary.get(md);
907 if (!completeSummary.equals(prevCompleteSummary)) {
908 mapMethodDescriptorToReadSummary.put(md, completeSummary);
910 // results for callee changed, so enqueue dependents caller for
912 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
913 while (depsItr.hasNext()) {
914 MethodDescriptor methodNext = depsItr.next();
915 if (!methodDescriptorsToVisitStack.contains(methodNext)) {
916 methodDescriptorsToVisitStack.add(methodNext);
920 // if there is set of callee to be analyzed,
921 // add this set into the top of stack
922 Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
923 while (calleeIter.hasNext()) {
924 MethodDescriptor mdNext = calleeIter.next();
925 if (!methodDescriptorsToVisitStack.contains(mdNext)) {
926 methodDescriptorsToVisitStack.add(mdNext);
929 calleesToEnqueue.clear();
937 private ReadSummary computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm,
938 boolean onlyVisitSSJavaLoop) {
940 MethodDescriptor md = fm.getMethod();
941 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
943 if (onlyVisitSSJavaLoop) {
944 flatNodesToVisit.add(ssjavaLoopEntrance);
946 flatNodesToVisit.add(fm);
949 Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
951 while (!flatNodesToVisit.isEmpty()) {
952 FlatNode fn = flatNodesToVisit.iterator().next();
953 flatNodesToVisit.remove(fn);
955 ReadSummary curr = new ReadSummary();
957 Set<ReadSummary> prevSet = new HashSet<ReadSummary>();
958 for (int i = 0; i < fn.numPrev(); i++) {
959 FlatNode prevFn = fn.getPrev(i);
960 ReadSummary in = mapFlatNodeToReadSummary.get(prevFn);
966 mergeReadLocationAnaylsis(curr, prevSet);
968 computeReadSharedDescriptorSet_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
970 ReadSummary readPrev = mapFlatNodeToReadSummary.get(fn);
972 if (!curr.equals(readPrev)) {
973 mapFlatNodeToReadSummary.put(fn, curr);
975 for (int i = 0; i < fn.numNext(); i++) {
976 FlatNode nn = fn.getNext(i);
978 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
979 flatNodesToVisit.add(nn);
987 ReadSummary completeSummary = new ReadSummary();
988 Set<ReadSummary> summarySet = new HashSet<ReadSummary>();
990 if (onlyVisitSSJavaLoop) {
991 // when analyzing ssjava loop,
992 // complete summary is merging of all previous nodes of ssjava loop
994 for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
995 ReadSummary frnSummary = mapFlatNodeToReadSummary.get(ssjavaLoopEntrance.getPrev(i));
996 if (frnSummary != null) {
997 summarySet.add(frnSummary);
1001 // merging exit node summary into the complete summary
1002 summarySet.add(mapFlatNodeToReadSummary.get(fm.getFlatExit()));
1004 mergeReadLocationAnaylsis(completeSummary, summarySet);
1006 return completeSummary;
1010 private void computeReadSharedDescriptorSet_nodeActions(MethodDescriptor caller, FlatNode fn,
1011 ReadSummary curr, Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
1015 FieldDescriptor fld;
1017 switch (fn.kind()) {
1019 case FKind.FlatMethod: {
1020 FlatMethod fm = (FlatMethod) fn;
1022 ReadSummary summary = mapMethodDescriptorToReadSummary.get(fm.getMethod());
1024 Set<ReadSummary> inSet = new HashSet<ReadSummary>();
1025 if (summary != null) {
1027 mergeReadLocationAnaylsis(curr, inSet);
1033 case FKind.FlatOpNode: {
1034 FlatOpNode fon = (FlatOpNode) fn;
1035 lhs = fon.getDest();
1036 rhs = fon.getLeft();
1038 if (fon.getOp().getOp() == Operation.ASSIGN) {
1039 if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) {
1040 // in ssjavaloop, we need to take care about reading local variables!
1041 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
1042 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
1043 rhsHeapPath.add(LOCAL);
1044 Location loc = getLocation(rhs);
1045 if (loc != null && ssjava.isSharedLocation(loc)) {
1046 curr.addRead(rhsHeapPath, loc, rhs);
1054 case FKind.FlatFieldNode:
1055 case FKind.FlatElementNode: {
1057 if (fn.kind() == FKind.FlatFieldNode) {
1058 FlatFieldNode ffn = (FlatFieldNode) fn;
1061 fld = ffn.getField();
1063 FlatElementNode fen = (FlatElementNode) fn;
1066 TypeDescriptor td = rhs.getType().dereference();
1067 fld = getArrayField(td);
1070 if (fld.isStatic() && fld.isFinal()) {
1075 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1076 if (srcHeapPath != null) {
1077 // if srcHeapPath is null, it means that it is not reachable from
1078 // callee's parameters. so just ignore it
1080 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1082 if (!fld.getType().isArray() && fld.getType().isImmutable()) {
1085 if (fn.kind() == FKind.FlatElementNode) {
1086 // array element read case
1087 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>();
1088 for (int i = 0; i < fldHeapPath.size() - 1; i++) {
1089 newHeapPath.add(fldHeapPath.get(i));
1092 Descriptor desc = fldHeapPath.get(fldHeapPath.size() - 1);
1093 if (desc instanceof FieldDescriptor) {
1094 fld = (FieldDescriptor) desc;
1095 loc = getLocation(fld);
1096 fldHeapPath = newHeapPath;
1097 if (loc != null && ssjava.isSharedLocation(loc)) {
1098 curr.addRead(fldHeapPath, loc, fld);
1102 loc = getLocation(fld);
1103 if (loc != null && ssjava.isSharedLocation(loc)) {
1104 curr.addRead(fldHeapPath, loc, fld);
1108 // propagate rhs's heap path to the lhs
1110 if (fn.kind() == FKind.FlatElementNode) {
1111 mapDescToLocation.put(lhs, getLocation(rhs));
1113 fldHeapPath.add(fld);
1115 mapHeapPath.put(lhs, fldHeapPath);
1123 case FKind.FlatCall: {
1125 FlatCall fc = (FlatCall) fn;
1127 // find out the set of callees
1128 MethodDescriptor mdCallee = fc.getMethod();
1129 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1130 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1131 setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1133 possibleCalleeReadSummarySetToCaller.clear();
1135 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1136 MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
1137 FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
1139 addDependent(mdPossibleCallee, // callee
1142 calleesToEnqueue.add(mdPossibleCallee);
1144 // updates possible callee's initial summary using caller's read status
1145 bindHeapPathReadSummary(fc, calleeFlatMethod, curr);
1149 // contribute callee's writing effects to the caller
1150 mergeReadLocationAnaylsis(curr, possibleCalleeReadSummarySetToCaller);
1155 case FKind.FlatReturnNode: {
1156 returnNodeSet.add(fn);
1163 private void mergeReadLocationAnaylsis(ReadSummary curr, Set<ReadSummary> inSet) {
1165 if (inSet.size() == 0) {
1169 for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1170 ReadSummary inSummary = (ReadSummary) inIterator.next();
1171 curr.merge(inSummary);
1176 private boolean hasReadingEffectOnSharedLocation(MethodDescriptor md, NTuple<Descriptor> hp,
1177 Location loc, Descriptor d) {
1179 ReadSummary summary = mapMethodDescriptorToReadSummary.get(md);
1181 if (summary != null) {
1182 Hashtable<Location, Set<Descriptor>> map = summary.get(hp);
1184 Set<Descriptor> descSec = map.get(loc);
1185 if (descSec != null) {
1186 return descSec.contains(d);
1194 private Location getLocation(Descriptor d) {
1196 if (d instanceof FieldDescriptor) {
1197 TypeExtension te = ((FieldDescriptor) d).getType().getExtension();
1199 return (Location) te;
1202 assert d instanceof TempDescriptor;
1203 TempDescriptor td = (TempDescriptor) d;
1205 TypeExtension te = td.getType().getExtension();
1207 if (te instanceof SSJavaType) {
1208 SSJavaType ssType = (SSJavaType) te;
1209 CompositeLocation comp = ssType.getCompLoc();
1210 return comp.get(comp.getSize() - 1);
1212 return (Location) te;
1217 return mapDescToLocation.get(d);
1220 private void writeLocation(MethodDescriptor md, ClearingSummary curr, NTuple<Descriptor> hp,
1221 Location loc, Descriptor d) {
1223 SharedStatus state = getState(curr, hp);
1224 if (loc != null && hasReadingEffectOnSharedLocation(md, hp, loc, d)) {
1225 // 1. add field x to the clearing set
1227 state.addVar(loc, d);
1229 // 3. if the set v contains all of variables belonging to the shared
1230 // location, set flag to true
1231 if (isOverWrittenAllDescsOfSharedLoc(md, hp, loc, state.getVarSet(loc))) {
1232 state.updateFlag(loc, true);
1235 state.setWriteEffect(loc);
1239 private boolean isOverWrittenAllDescsOfSharedLoc(MethodDescriptor md, NTuple<Descriptor> hp,
1240 Location loc, Set<Descriptor> writtenSet) {
1242 ReadSummary summary = mapMethodDescriptorToReadSummary.get(md);
1244 if (summary != null) {
1245 Hashtable<Location, Set<Descriptor>> map = summary.get(hp);
1247 Set<Descriptor> descSet = map.get(loc);
1248 if (descSet != null) {
1249 return writtenSet.containsAll(descSet);
1256 private void readLocation(MethodDescriptor md, ClearingSummary curr, NTuple<Descriptor> hp,
1257 Location loc, Descriptor d) {
1258 // remove reading var x from written set
1259 if (loc != null && hasReadingEffectOnSharedLocation(md, hp, loc, d)) {
1260 SharedStatus state = getState(curr, hp);
1261 state.removeVar(loc, d);
1265 private SharedStatus getState(ClearingSummary curr, NTuple<Descriptor> hp) {
1266 SharedStatus state = curr.get(hp);
1267 if (state == null) {
1268 state = new SharedStatus();
1269 curr.put(hp, state);
1274 private void writtenAnalyis() {
1275 // perform second stage analysis: intraprocedural analysis ensure that
1277 // variables are definitely written in-between the same read
1279 // First, identify ssjava loop entrace
1280 FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
1281 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1282 flatNodesToVisit.add(fm);
1284 LoopFinder loopFinder = new LoopFinder(fm);
1286 while (!flatNodesToVisit.isEmpty()) {
1287 FlatNode fn = flatNodesToVisit.iterator().next();
1288 flatNodesToVisit.remove(fn);
1290 String label = (String) state.fn2labelMap.get(fn);
1291 if (label != null) {
1293 if (label.equals(ssjava.SSJAVA)) {
1294 ssjavaLoopEntrance = fn;
1299 for (int i = 0; i < fn.numNext(); i++) {
1300 FlatNode nn = fn.getNext(i);
1301 flatNodesToVisit.add(nn);
1305 assert ssjavaLoopEntrance != null;
1307 // assume that ssjava loop is top-level loop in method, not nested loop
1308 Set nestedLoop = loopFinder.nestedLoops();
1309 for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
1310 LoopFinder lf = (LoopFinder) loopIter.next();
1311 if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
1316 assert ssjavaLoop != null;
1318 writtenAnalysis_analyzeLoop();
1320 if (debugcount > 0) {
1326 private void writtenAnalysis_analyzeLoop() {
1328 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1329 flatNodesToVisit.add(ssjavaLoopEntrance);
1331 loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
1333 while (!flatNodesToVisit.isEmpty()) {
1334 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1335 flatNodesToVisit.remove(fn);
1337 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
1338 definitelyWrittenResults.get(fn);
1340 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
1341 new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
1342 for (int i = 0; i < fn.numPrev(); i++) {
1343 FlatNode nn = fn.getPrev(i);
1344 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
1345 definitelyWrittenResults.get(nn);
1351 writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
1353 // if a new result, schedule forward nodes for analysis
1354 if (!curr.equals(prev)) {
1355 definitelyWrittenResults.put(fn, curr);
1357 for (int i = 0; i < fn.numNext(); i++) {
1358 FlatNode nn = fn.getNext(i);
1359 if (loopIncElements.contains(nn)) {
1360 flatNodesToVisit.add(nn);
1368 private void writtenAnalysis_nodeAction(FlatNode fn,
1369 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
1371 if (fn.equals(loopEntrance)) {
1372 // it reaches loop entrance: changes all flag to true
1373 Set<NTuple<Descriptor>> keySet = curr.keySet();
1374 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1375 NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
1376 Hashtable<FlatNode, Boolean> pair = curr.get(key);
1378 Set<FlatNode> pairKeySet = pair.keySet();
1379 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1380 FlatNode pairKey = (FlatNode) iterator2.next();
1381 pair.put(pairKey, Boolean.TRUE);
1388 FieldDescriptor fld;
1390 switch (fn.kind()) {
1391 case FKind.FlatOpNode: {
1392 FlatOpNode fon = (FlatOpNode) fn;
1393 lhs = fon.getDest();
1394 rhs = fon.getLeft();
1396 NTuple<Descriptor> rhsHeapPath = computePath(rhs);
1397 if (!rhs.getType().isImmutable()) {
1398 mapHeapPath.put(lhs, rhsHeapPath);
1400 if (fon.getOp().getOp() == Operation.ASSIGN) {
1402 readValue(fn, rhsHeapPath, curr);
1405 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1406 removeHeapPath(curr, lhsHeapPath);
1411 case FKind.FlatLiteralNode: {
1412 FlatLiteralNode fln = (FlatLiteralNode) fn;
1416 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1417 removeHeapPath(curr, lhsHeapPath);
1422 case FKind.FlatFieldNode:
1423 case FKind.FlatElementNode: {
1425 if (fn.kind() == FKind.FlatFieldNode) {
1426 FlatFieldNode ffn = (FlatFieldNode) fn;
1429 fld = ffn.getField();
1431 FlatElementNode fen = (FlatElementNode) fn;
1434 TypeDescriptor td = rhs.getType().dereference();
1435 fld = getArrayField(td);
1438 if (fld.isFinal() /* && fld.isStatic() */) {
1439 // if field is final and static, no need to check
1444 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1445 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1446 fldHeapPath.add(fld);
1448 if (fld.getType().isImmutable()) {
1449 readValue(fn, fldHeapPath, curr);
1452 // propagate rhs's heap path to the lhs
1453 mapHeapPath.put(lhs, fldHeapPath);
1458 case FKind.FlatSetFieldNode:
1459 case FKind.FlatSetElementNode: {
1461 if (fn.kind() == FKind.FlatSetFieldNode) {
1462 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1463 lhs = fsfn.getDst();
1464 fld = fsfn.getField();
1466 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1467 lhs = fsen.getDst();
1468 rhs = fsen.getSrc();
1469 TypeDescriptor td = lhs.getType().dereference();
1470 fld = getArrayField(td);
1474 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1475 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1476 fldHeapPath.add(fld);
1477 removeHeapPath(curr, fldHeapPath);
1482 case FKind.FlatCall: {
1483 FlatCall fc = (FlatCall) fn;
1485 bindHeapPathCallerArgWithCaleeParam(fc);
1486 // add <hp,statement,false> in which hp is an element of
1488 // of callee: callee has 'read' requirement!
1490 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1491 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1492 Hashtable<FlatNode, Boolean> gen = curr.get(read);
1494 gen = new Hashtable<FlatNode, Boolean>();
1495 curr.put(read, gen);
1497 Boolean currentStatus = gen.get(fn);
1498 if (currentStatus == null) {
1499 gen.put(fn, Boolean.FALSE);
1501 checkFlag(currentStatus.booleanValue(), fn, read);
1505 // removes <hp,statement,flag> if hp is an element of
1507 // set of callee. it means that callee will overwrite it
1508 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1509 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1510 removeHeapPath(curr, write);
1520 private void readValue(FlatNode fn, NTuple<Descriptor> hp,
1521 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
1522 Hashtable<FlatNode, Boolean> gen = curr.get(hp);
1524 gen = new Hashtable<FlatNode, Boolean>();
1527 Boolean currentStatus = gen.get(fn);
1528 if (currentStatus == null) {
1529 gen.put(fn, Boolean.FALSE);
1531 checkFlag(currentStatus.booleanValue(), fn, hp);
1536 private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1537 NTuple<Descriptor> hp) {
1539 // removes all of heap path that starts with prefix 'hp'
1540 // since any reference overwrite along heap path gives overwriting side
1541 // effects on the value
1543 Set<NTuple<Descriptor>> keySet = curr.keySet();
1544 for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
1545 NTuple<Descriptor> key = iter.next();
1546 if (key.startsWith(hp)) {
1547 curr.put(key, new Hashtable<FlatNode, Boolean>());
1553 private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
1554 // compute all possible callee set
1555 // transform all READ/OVERWRITE set from the any possible
1558 calleeUnionBoundReadSet.clear();
1559 calleeIntersectBoundOverWriteSet.clear();
1560 calleeBoundWriteSet.clear();
1562 if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
1563 // ssjava util case!
1564 // have write effects on the first argument
1565 TempDescriptor arg = fc.getArg(0);
1566 NTuple<Descriptor> argHeapPath = computePath(arg);
1567 calleeIntersectBoundOverWriteSet.add(argHeapPath);
1569 MethodDescriptor mdCallee = fc.getMethod();
1570 // FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1571 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1572 // setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
1573 setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1575 // create mapping from arg idx to its heap paths
1576 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1577 new Hashtable<Integer, NTuple<Descriptor>>();
1579 // arg idx is starting from 'this' arg
1580 if (fc.getThis() != null) {
1581 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1582 if (thisHeapPath == null) {
1583 // method is called without creating new flat node representing 'this'
1584 thisHeapPath = new NTuple<Descriptor>();
1585 thisHeapPath.add(fc.getThis());
1588 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1591 for (int i = 0; i < fc.numArgs(); i++) {
1592 TempDescriptor arg = fc.getArg(i);
1593 NTuple<Descriptor> argHeapPath = computePath(arg);
1594 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1597 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1598 MethodDescriptor callee = (MethodDescriptor) iterator.next();
1599 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1601 // binding caller's args and callee's params
1603 Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
1604 if (calleeReadSet == null) {
1605 calleeReadSet = new HashSet<NTuple<Descriptor>>();
1606 mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
1609 Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
1611 if (calleeOverWriteSet == null) {
1612 calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
1613 mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
1616 Set<NTuple<Descriptor>> calleeWriteSet = mapFlatMethodToWrite.get(calleeFlatMethod);
1618 if (calleeWriteSet == null) {
1619 calleeWriteSet = new HashSet<NTuple<Descriptor>>();
1620 mapFlatMethodToWrite.put(calleeFlatMethod, calleeWriteSet);
1623 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1624 new Hashtable<Integer, TempDescriptor>();
1626 if (calleeFlatMethod.getMethod().isStatic()) {
1627 // static method does not have implicit 'this' arg
1630 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1631 TempDescriptor param = calleeFlatMethod.getParameter(i);
1632 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
1635 Set<NTuple<Descriptor>> calleeBoundReadSet =
1636 bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1637 // union of the current read set and the current callee's
1639 calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1640 Set<NTuple<Descriptor>> calleeBoundOverWriteSet =
1641 bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1642 // intersection of the current overwrite set and the current
1645 merge(calleeIntersectBoundOverWriteSet, calleeBoundOverWriteSet);
1647 Set<NTuple<Descriptor>> boundWriteSetFromCallee =
1648 bindSet(calleeWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1649 calleeBoundWriteSet.addAll(boundWriteSetFromCallee);
1656 private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1658 // the definitely written analysis only takes care about locations that
1659 // are written to inside of the SSJava loop
1660 for (Iterator iterator = calleeBoundWriteSet.iterator(); iterator.hasNext();) {
1661 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1662 if (hp.startsWith(write)) {
1663 // it has write effect!
1667 + "There is a variable, which is reachable through references "
1669 + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1670 + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1678 private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1679 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
1681 Set<NTuple<Descriptor>> inKeySet = in.keySet();
1682 for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1683 NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1684 Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
1686 Set<FlatNode> pairKeySet = inPair.keySet();
1687 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1688 FlatNode pairKey = (FlatNode) iterator2.next();
1689 Boolean inFlag = inPair.get(pairKey);
1691 Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
1692 if (currPair == null) {
1693 currPair = new Hashtable<FlatNode, Boolean>();
1694 curr.put(inKey, currPair);
1697 Boolean currFlag = currPair.get(pairKey);
1698 // by default, flag is set by false
1699 if (currFlag == null) {
1700 currFlag = Boolean.FALSE;
1702 currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
1703 currPair.put(pairKey, currFlag);
1710 private void methodReadOverWriteAnalysis() {
1711 // perform method READ/OVERWRITE analysis
1712 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1713 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1715 sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1717 LinkedList<MethodDescriptor> descriptorListToAnalyze =
1718 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1720 // no need to analyze method having ssjava loop
1721 // methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
1722 methodContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop();
1724 // current descriptors to visit in fixed-point interprocedural analysis,
1726 // dependency in the call graph
1727 methodDescriptorsToVisitStack.clear();
1729 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1730 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1732 while (!descriptorListToAnalyze.isEmpty()) {
1733 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1734 methodDescriptorsToVisitStack.add(md);
1737 // analyze scheduled methods until there are no more to visit
1738 while (!methodDescriptorsToVisitStack.isEmpty()) {
1739 // start to analyze leaf node
1740 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1741 FlatMethod fm = state.getMethodFlat(md);
1743 Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1744 Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
1745 Set<NTuple<Descriptor>> writeSet = new HashSet<NTuple<Descriptor>>();
1747 methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet, writeSet);
1749 Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
1750 Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
1751 Set<NTuple<Descriptor>> prevWrite = mapFlatMethodToWrite.get(fm);
1753 if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite) && writeSet
1754 .equals(prevWrite))) {
1755 mapFlatMethodToRead.put(fm, readSet);
1756 mapFlatMethodToOverWrite.put(fm, overWriteSet);
1757 mapFlatMethodToWrite.put(fm, writeSet);
1759 // results for callee changed, so enqueue dependents caller for
1762 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1763 while (depsItr.hasNext()) {
1764 MethodDescriptor methodNext = depsItr.next();
1765 if (!methodDescriptorsToVisitStack.contains(methodNext)
1766 && methodDescriptorToVistSet.contains(methodNext)) {
1767 methodDescriptorsToVisitStack.add(methodNext);
1778 private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1779 Set<NTuple<Descriptor>> overWriteSet, Set<NTuple<Descriptor>> writeSet) {
1780 if (state.SSJAVADEBUG) {
1781 System.out.println("SSJAVA: Definitely written Analyzing: " + fm);
1784 // intraprocedural analysis
1785 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1786 flatNodesToVisit.add(fm);
1788 while (!flatNodesToVisit.isEmpty()) {
1789 FlatNode fn = flatNodesToVisit.iterator().next();
1790 flatNodesToVisit.remove(fn);
1792 Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
1794 for (int i = 0; i < fn.numPrev(); i++) {
1795 FlatNode prevFn = fn.getPrev(i);
1796 Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
1802 methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet, writeSet);
1804 Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
1805 if (!curr.equals(writtenSetPrev)) {
1806 mapFlatNodeToWrittenSet.put(fn, curr);
1807 for (int i = 0; i < fn.numNext(); i++) {
1808 FlatNode nn = fn.getNext(i);
1809 flatNodesToVisit.add(nn);
1817 private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
1818 Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet,
1819 Set<NTuple<Descriptor>> writeSet) {
1822 FieldDescriptor fld;
1824 switch (fn.kind()) {
1825 case FKind.FlatMethod: {
1827 // set up initial heap paths for method parameters
1828 FlatMethod fm = (FlatMethod) fn;
1829 for (int i = 0; i < fm.numParameters(); i++) {
1830 TempDescriptor param = fm.getParameter(i);
1831 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1832 heapPath.add(param);
1833 mapHeapPath.put(param, heapPath);
1838 case FKind.FlatOpNode: {
1839 FlatOpNode fon = (FlatOpNode) fn;
1840 // for a normal assign node, need to propagate lhs's heap path to
1842 if (fon.getOp().getOp() == Operation.ASSIGN) {
1843 rhs = fon.getLeft();
1844 lhs = fon.getDest();
1846 NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1847 if (rhsHeapPath != null) {
1848 mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1855 case FKind.FlatElementNode:
1856 case FKind.FlatFieldNode: {
1860 if (fn.kind() == FKind.FlatFieldNode) {
1861 FlatFieldNode ffn = (FlatFieldNode) fn;
1864 fld = ffn.getField();
1866 FlatElementNode fen = (FlatElementNode) fn;
1869 TypeDescriptor td = rhs.getType().dereference();
1870 fld = getArrayField(td);
1873 if (fld.isFinal() /* && fld.isStatic() */) {
1874 // if field is final and static, no need to check
1879 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1880 if (srcHeapPath != null) {
1881 // if lhs srcHeapPath is null, it means that it is not reachable from
1882 // callee's parameters. so just ignore it
1884 NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1885 readingHeapPath.add(fld);
1886 mapHeapPath.put(lhs, readingHeapPath);
1889 if (fld.getType().isImmutable()) {
1890 // if WT doesnot have hp(x.f), add hp(x.f) to READ
1891 if (!writtenSet.contains(readingHeapPath)) {
1892 readSet.add(readingHeapPath);
1896 // no need to kill hp(x.f) from WT
1902 case FKind.FlatSetFieldNode:
1903 case FKind.FlatSetElementNode: {
1907 if (fn.kind() == FKind.FlatSetFieldNode) {
1908 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1909 lhs = fsfn.getDst();
1910 fld = fsfn.getField();
1911 rhs = fsfn.getSrc();
1913 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1914 lhs = fsen.getDst();
1915 rhs = fsen.getSrc();
1916 TypeDescriptor td = lhs.getType().dereference();
1917 fld = getArrayField(td);
1921 NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1922 if (lhsHeapPath != null) {
1923 // if lhs heap path is null, it means that it is not reachable from
1924 // callee's parameters. so just ignore it
1925 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1926 newHeapPath.add(fld);
1927 mapHeapPath.put(fld, newHeapPath);
1930 // need to add hp(y) to WT
1931 writtenSet.add(newHeapPath);
1933 writeSet.add(newHeapPath);
1939 case FKind.FlatCall: {
1941 FlatCall fc = (FlatCall) fn;
1943 bindHeapPathCallerArgWithCaleeParam(fc);
1945 // add heap path, which is an element of READ_bound set and is not
1947 // element of WT set, to the caller's READ set
1948 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1949 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1950 if (!writtenSet.contains(read)) {
1955 // add heap path, which is an element of OVERWRITE_bound set, to the
1957 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1958 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1959 writtenSet.add(write);
1962 // add heap path, which is an element of WRITE_BOUND set, to the
1963 // caller's writeSet
1964 for (Iterator iterator = calleeBoundWriteSet.iterator(); iterator.hasNext();) {
1965 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1966 writeSet.add(write);
1972 case FKind.FlatExit: {
1973 // merge the current written set with OVERWRITE set
1974 merge(overWriteSet, writtenSet);
1982 static public FieldDescriptor getArrayField(TypeDescriptor td) {
1983 FieldDescriptor fd = mapTypeToArrayField.get(td);
1986 new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), td, arrayElementFieldName, null,
1988 mapTypeToArrayField.put(td, fd);
1993 private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
1994 if (inSet.size() == 0) {
1997 Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
1998 new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
2000 for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
2002 ClearingSummary inTable = (ClearingSummary) inIterator.next();
2004 Set<NTuple<Descriptor>> keySet = inTable.keySet();
2006 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2007 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
2008 SharedStatus inState = inTable.get(hpKey);
2009 SharedStatus currState = curr.get(hpKey);
2010 if (currState == null) {
2011 currState = new SharedStatus();
2012 curr.put(hpKey, currState);
2015 currState.merge(inState);
2017 Set<Location> locSet = inState.getMap().keySet();
2018 for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
2019 Location loc = (Location) iterator2.next();
2020 Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
2021 boolean inFlag = pair.getSecond().booleanValue();
2023 Pair<NTuple<Descriptor>, Location> flagKey =
2024 new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
2025 Boolean current = mapHeapPathLoc2Flag.get(flagKey);
2026 if (current == null) {
2027 current = new Boolean(true);
2029 boolean newInFlag = current.booleanValue() & inFlag;
2030 mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
2037 // merge flag status
2038 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
2039 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
2040 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
2041 SharedStatus currState = curr.get(hpKey);
2042 Set<Location> locKeySet = currState.getMap().keySet();
2043 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
2044 Location locKey = (Location) iterator2.next();
2045 Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
2046 boolean currentFlag = pair.getSecond().booleanValue();
2047 Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
2048 if (inFlag != null) {
2049 boolean newFlag = currentFlag | inFlag.booleanValue();
2050 if (currentFlag != newFlag) {
2051 currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
2059 private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
2060 if (curr.isEmpty()) {
2061 // WrittenSet has a special initial value which covers all possible
2063 // For the first time of intersection, we can take all previous set
2066 // otherwise, current set is the intersection of the two sets
2072 // combine two heap path
2073 private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
2074 NTuple<Descriptor> combined = new NTuple<Descriptor>();
2076 for (int i = 0; i < callerIn.size(); i++) {
2077 combined.add(callerIn.get(i));
2080 // the first element of callee's heap path represents parameter
2081 // so we skip the first one since it is already added from caller's heap
2083 for (int i = 1; i < calleeIn.size(); i++) {
2084 combined.add(calleeIn.get(i));
2090 private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
2091 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
2092 Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
2094 Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
2096 Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
2097 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2098 Integer idx = (Integer) iterator.next();
2100 NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
2101 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
2102 for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
2103 NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
2104 if (element.startsWith(calleeParam)) {
2105 NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
2106 boundedCalleeSet.add(boundElement);
2112 return boundedCalleeSet;
2116 // Borrowed it from disjoint analysis
2117 private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
2119 Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
2121 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
2123 Iterator<MethodDescriptor> itr = toSort.iterator();
2124 while (itr.hasNext()) {
2125 MethodDescriptor d = itr.next();
2127 if (!discovered.contains(d)) {
2128 dfsVisit(d, toSort, sorted, discovered);
2135 // While we're doing DFS on call graph, remember
2136 // dependencies for efficient queuing of methods
2137 // during interprocedural analysis:
2139 // a dependent of a method decriptor d for this analysis is:
2140 // 1) a method or task that invokes d
2141 // 2) in the descriptorsToAnalyze set
2142 private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
2143 LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
2147 Iterator itr = callGraph.getCallerSet(md).iterator();
2148 while (itr.hasNext()) {
2149 MethodDescriptor dCaller = (MethodDescriptor) itr.next();
2150 // only consider callers in the original set to analyze
2151 if (!toSort.contains(dCaller)) {
2154 if (!discovered.contains(dCaller)) {
2155 addDependent(md, // callee
2159 dfsVisit(dCaller, toSort, sorted, discovered);
2163 // for leaf-nodes last now!
2167 // a dependent of a method decriptor d for this analysis is:
2168 // 1) a method or task that invokes d
2169 // 2) in the descriptorsToAnalyze set
2170 private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
2171 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2173 deps = new HashSet<MethodDescriptor>();
2176 mapDescriptorToSetDependents.put(callee, deps);
2179 private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
2180 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2182 deps = new HashSet<MethodDescriptor>();
2183 mapDescriptorToSetDependents.put(callee, deps);
2188 private NTuple<Descriptor> computePath(TempDescriptor td) {
2189 // generate proper path fot input td
2190 // if td is local variable, it just generate one element tuple path
2191 if (mapHeapPath.containsKey(td)) {
2192 return mapHeapPath.get(td);
2194 NTuple<Descriptor> path = new NTuple<Descriptor>();