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;
19 import IR.Flat.FlatCall;
20 import IR.Flat.FlatFieldNode;
21 import IR.Flat.FlatLiteralNode;
22 import IR.Flat.FlatMethod;
23 import IR.Flat.FlatNode;
24 import IR.Flat.FlatOpNode;
25 import IR.Flat.FlatSetFieldNode;
26 import IR.Flat.TempDescriptor;
29 public class DefinitelyWrittenCheck {
31 SSJavaAnalysis ssjava;
35 // maps a descriptor to its known dependents: namely
36 // methods or tasks that call the descriptor's method
37 // AND are part of this analysis (reachable from main)
38 private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
40 // maps a flat node to its WrittenSet: this keeps all heap path overwritten
42 private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
44 // maps a temp descriptor to its heap path
45 // each temp descriptor has a unique heap path since we do not allow any
47 private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
49 // maps a flat method to the READ that is the set of heap path that is
50 // expected to be written before method invocation
51 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
53 // maps a flat method to the OVERWRITE that is the set of heap path that is
54 // overwritten on every possible path during method invocation
55 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
57 // points to method containing SSJAVA Loop
58 private MethodDescriptor methodContainingSSJavaLoop;
60 // maps a flatnode to definitely written analysis mapping M
61 private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
63 // maps a method descriptor to its current summary during the analysis
64 // then analysis reaches fixed-point, this mapping will have the final summary
65 // for each method descriptor
66 private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToCompleteClearingSummary;
68 // maps a method descriptor to the merged incoming caller's current
70 private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToInitialClearingSummary;
72 // maps a flat node to current partial results
73 private Hashtable<FlatNode, ClearingSummary> mapFlatNodeToClearingSummary;
75 // maps shared location to the set of descriptors which belong to the shared
77 private Hashtable<Location, Set<Descriptor>> mapSharedLocation2DescriptorSet;
79 // keep current descriptors to visit in fixed-point interprocedural analysis,
80 private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
82 // when analyzing flatcall, need to re-schedule set of callee
83 private Set<MethodDescriptor> calleesToEnqueue;
85 private Set<ClearingSummary> possibleCalleeCompleteSummarySetToCaller;
87 private LinkedList<MethodDescriptor> sortedDescriptors;
89 private FlatNode ssjavaLoopEntrance;
90 private LoopFinder ssjavaLoop;
91 private Set<FlatNode> loopIncElements;
93 private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
94 private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
96 private TempDescriptor LOCAL;
98 public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
100 this.ssjava = ssjava;
101 this.callGraph = ssjava.getCallGraph();
102 this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
103 this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
104 this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
105 this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
106 this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
107 this.definitelyWrittenResults =
108 new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
109 this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
110 this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
112 this.mapMethodDescriptorToCompleteClearingSummary =
113 new Hashtable<MethodDescriptor, ClearingSummary>();
114 this.mapMethodDescriptorToInitialClearingSummary =
115 new Hashtable<MethodDescriptor, ClearingSummary>();
116 this.mapSharedLocation2DescriptorSet = new Hashtable<Location, Set<Descriptor>>();
117 this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
118 this.calleesToEnqueue = new HashSet<MethodDescriptor>();
119 this.possibleCalleeCompleteSummarySetToCaller = new HashSet<ClearingSummary>();
120 this.LOCAL = new TempDescriptor("LOCAL");
123 public void definitelyWrittenCheck() {
124 if (!ssjava.getAnnotationRequireSet().isEmpty()) {
125 methodReadOverWriteAnalysis();
127 sharedLocationAnalysis();
128 checkSharedLocationResult();
132 private void checkSharedLocationResult() {
134 // mapping of method containing ssjava loop has the final result of
135 // shared location analysis
136 ClearingSummary result =
137 mapMethodDescriptorToCompleteClearingSummary.get(sortedDescriptors.peekFirst());
139 System.out.println("checkSharedLocationResult=" + result);
141 Set<NTuple<Descriptor>> hpKeySet = result.keySet();
142 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
143 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
144 SharedStatus state = result.get(hpKey);
145 Set<Location> locKeySet = state.getLocationSet();
146 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
147 Location locKey = (Location) iterator2.next();
148 if (!state.getFlag(locKey)) {
150 "Some concrete locations of the shared abstract location are not cleared at the same time.");
157 private void sharedLocationAnalysis() {
158 // verify that all concrete locations of shared location are cleared out at
159 // the same time once per the out-most loop
161 computeReadSharedDescriptorSet();
162 System.out.println("Reading Shared Location=" + mapSharedLocation2DescriptorSet);
164 methodDescriptorsToVisitStack.clear();
166 methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
168 // analyze scheduled methods until there are no more to visit
169 while (!methodDescriptorsToVisitStack.isEmpty()) {
170 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
172 ClearingSummary completeSummary =
173 sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
175 ClearingSummary prevCompleteSummary = mapMethodDescriptorToCompleteClearingSummary.get(md);
177 if (!completeSummary.equals(prevCompleteSummary)) {
179 mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
181 // results for callee changed, so enqueue dependents caller for
183 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
184 while (depsItr.hasNext()) {
185 MethodDescriptor methodNext = depsItr.next();
186 if (!methodDescriptorsToVisitStack.contains(methodNext)) {
187 methodDescriptorsToVisitStack.add(methodNext);
191 // if there is set of callee to be analyzed,
192 // add this set into the top of stack
193 Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
194 while (calleeIter.hasNext()) {
195 MethodDescriptor mdNext = calleeIter.next();
196 if (!methodDescriptorsToVisitStack.contains(mdNext)) {
197 methodDescriptorsToVisitStack.add(mdNext);
200 calleesToEnqueue.clear();
208 private ClearingSummary sharedLocation_analyzeMethod(MethodDescriptor md,
209 boolean onlyVisitSSJavaLoop) {
211 if (state.SSJAVADEBUG) {
212 System.out.println("Definitely written for shared locations Analyzing: " + md + " "
213 + onlyVisitSSJavaLoop);
216 FlatMethod fm = state.getMethodFlat(md);
218 // intraprocedural analysis
219 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
221 // start a new mapping of partial results for each flat node
222 mapFlatNodeToClearingSummary = new Hashtable<FlatNode, ClearingSummary>();
224 if (onlyVisitSSJavaLoop) {
225 flatNodesToVisit.add(ssjavaLoopEntrance);
227 flatNodesToVisit.add(fm);
230 Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
232 while (!flatNodesToVisit.isEmpty()) {
233 FlatNode fn = flatNodesToVisit.iterator().next();
234 flatNodesToVisit.remove(fn);
236 ClearingSummary curr = new ClearingSummary();
238 Set<ClearingSummary> prevSet = new HashSet<ClearingSummary>();
239 for (int i = 0; i < fn.numPrev(); i++) {
240 FlatNode prevFn = fn.getPrev(i);
241 ClearingSummary in = mapFlatNodeToClearingSummary.get(prevFn);
246 mergeSharedLocationAnaylsis(curr, prevSet);
248 sharedLocation_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
249 ClearingSummary clearingPrev = mapFlatNodeToClearingSummary.get(fn);
251 if (!curr.equals(clearingPrev)) {
252 mapFlatNodeToClearingSummary.put(fn, curr);
254 for (int i = 0; i < fn.numNext(); i++) {
255 FlatNode nn = fn.getNext(i);
257 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
258 flatNodesToVisit.add(nn);
266 ClearingSummary completeSummary = new ClearingSummary();
267 Set<ClearingSummary> summarySet = new HashSet<ClearingSummary>();
269 if (onlyVisitSSJavaLoop) {
270 // when analyzing ssjava loop,
271 // complete summary is merging of all previous nodes of ssjava loop
273 for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
274 ClearingSummary frnSummary =
275 mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
276 if (frnSummary != null) {
277 summarySet.add(frnSummary);
281 // merging all exit node summary into the complete summary
282 if (!returnNodeSet.isEmpty()) {
283 for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
284 FlatNode frn = (FlatNode) iterator.next();
285 ClearingSummary frnSummary = mapFlatNodeToClearingSummary.get(frn);
286 summarySet.add(frnSummary);
290 mergeSharedLocationAnaylsis(completeSummary, summarySet);
291 return completeSummary;
294 private void sharedLocation_nodeActions(MethodDescriptor caller, FlatNode fn,
295 ClearingSummary curr, Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
302 case FKind.FlatMethod: {
303 FlatMethod fm = (FlatMethod) fn;
305 ClearingSummary summaryFromCaller =
306 mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
308 Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
309 inSet.add(summaryFromCaller);
310 mergeSharedLocationAnaylsis(curr, inSet);
315 case FKind.FlatOpNode: {
316 FlatOpNode fon = (FlatOpNode) fn;
320 if (fon.getOp().getOp() == Operation.ASSIGN) {
321 if (rhs.getType().isImmutable() && isSSJavaLoop) {
322 // in ssjavaloop, we need to take care about reading local variables!
323 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
324 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
325 rhsHeapPath.add(LOCAL);
326 lhsHeapPath.add(LOCAL);
327 if (!lhs.getSymbol().startsWith("neverused")) {
328 readLocation(curr, rhsHeapPath, rhs);
329 writeLocation(curr, lhsHeapPath, lhs);
337 case FKind.FlatFieldNode:
338 case FKind.FlatElementNode: {
340 FlatFieldNode ffn = (FlatFieldNode) fn;
343 fld = ffn.getField();
346 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
347 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
349 if (fld.getType().isImmutable()) {
350 readLocation(curr, fldHeapPath, fld);
356 case FKind.FlatSetFieldNode:
357 case FKind.FlatSetElementNode: {
359 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
361 fld = fsfn.getField();
364 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
365 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
366 if (fld.getType().isImmutable()) {
367 writeLocation(curr, fldHeapPath, fld);
369 // updates reference field case:
370 // 2. if there exists a tuple t in sharing summary that starts with
371 // hp(x) then, set flag of tuple t to 'true'
372 fldHeapPath.add(fld);
373 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
374 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
375 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
376 if (hpKey.startsWith(fldHeapPath)) {
377 curr.get(hpKey).updateFlag(true);
385 case FKind.FlatCall: {
387 FlatCall fc = (FlatCall) fn;
389 // find out the set of callees
390 MethodDescriptor mdCallee = fc.getMethod();
391 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
392 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
393 TypeDescriptor typeDesc = fc.getThis().getType();
394 setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
396 possibleCalleeCompleteSummarySetToCaller.clear();
398 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
399 MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
400 FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
402 addDependent(mdPossibleCallee, // callee
405 calleesToEnqueue.add(mdPossibleCallee);
407 // updates possible callee's initial summary using caller's current
409 ClearingSummary prevCalleeInitSummary =
410 mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
412 ClearingSummary calleeInitSummary =
413 bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
415 // if changes, update the init summary
416 // and reschedule the callee for analysis
417 if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
419 if (!methodDescriptorsToVisitStack.contains(mdPossibleCallee)) {
420 methodDescriptorsToVisitStack.add(mdPossibleCallee);
422 mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
427 // contribute callee's writing effects to the caller
428 mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
433 case FKind.FlatReturnNode: {
434 returnNodeSet.add(fn);
442 private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc,
443 FlatMethod calleeFlatMethod, ClearingSummary curr) {
445 ClearingSummary boundSet = new ClearingSummary();
447 // create mapping from arg idx to its heap paths
448 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
449 new Hashtable<Integer, NTuple<Descriptor>>();
451 // arg idx is starting from 'this' arg
452 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
453 if (thisHeapPath == null) {
454 // method is called without creating new flat node representing 'this'
455 thisHeapPath = new NTuple<Descriptor>();
456 thisHeapPath.add(fc.getThis());
459 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
461 for (int i = 0; i < fc.numArgs(); i++) {
462 TempDescriptor arg = fc.getArg(i);
463 NTuple<Descriptor> argHeapPath = computePath(arg);
464 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
467 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
468 new Hashtable<Integer, TempDescriptor>();
469 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
470 TempDescriptor param = calleeFlatMethod.getParameter(i);
471 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
474 // binding caller's writing effects to callee's params
475 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
476 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
477 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
479 // iterate over caller's writing effect set
480 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
481 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
482 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
483 // current element is reachable caller's arg
484 // so need to bind it to the caller's side and add it to the callee's
486 if (hpKey.startsWith(argHeapPath)) {
487 NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
488 boundSet.put(boundHeapPath, curr.get(hpKey).clone());
495 // contribute callee's complete summary into the caller's current summary
496 ClearingSummary calleeCompleteSummary =
497 mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
499 if (calleeCompleteSummary != null) {
500 ClearingSummary boundCalleeEfffects = new ClearingSummary();
501 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
502 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
503 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
505 // iterate over callee's writing effect set
506 Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
507 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
508 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
509 // current element is reachable caller's arg
510 // so need to bind it to the caller's side and add it to the callee's
512 if (hpKey.startsWith(calleeParamHeapPath)) {
514 NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
516 boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
522 possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
528 private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
530 // replace the head of heap path with caller's arg path
531 // for example, heap path 'param.a.b' in callee's side will be replaced with
532 // (corresponding arg heap path).a.b for caller's side
534 NTuple<Descriptor> bound = new NTuple<Descriptor>();
536 for (int i = 0; i < argHeapPath.size(); i++) {
537 bound.add(argHeapPath.get(i));
540 for (int i = 1; i < hpKey.size(); i++) {
541 bound.add(hpKey.get(i));
547 private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
548 NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
549 // replace the head of caller's heap path with callee's param heap path
551 NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
552 boundHeapPath.add(calleeParamHeapPath);
554 for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
555 boundHeapPath.add(effectHeapPath.get(i));
558 return boundHeapPath;
561 private void computeReadSharedDescriptorSet() {
562 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
563 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
565 for (Iterator iterator = methodDescriptorsToAnalyze.iterator(); iterator.hasNext();) {
566 MethodDescriptor md = (MethodDescriptor) iterator.next();
567 FlatMethod fm = state.getMethodFlat(md);
568 computeReadSharedDescriptorSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
573 private void computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm,
574 boolean onlyVisitSSJavaLoop) {
576 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
577 Set<FlatNode> visited = new HashSet<FlatNode>();
579 if (onlyVisitSSJavaLoop) {
580 flatNodesToVisit.add(ssjavaLoopEntrance);
582 flatNodesToVisit.add(fm);
585 while (!flatNodesToVisit.isEmpty()) {
586 FlatNode fn = flatNodesToVisit.iterator().next();
587 flatNodesToVisit.remove(fn);
590 computeReadSharedDescriptorSet_nodeActions(fn, onlyVisitSSJavaLoop);
592 for (int i = 0; i < fn.numNext(); i++) {
593 FlatNode nn = fn.getNext(i);
594 if (!visited.contains(nn)) {
595 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
596 flatNodesToVisit.add(nn);
605 private void computeReadSharedDescriptorSet_nodeActions(FlatNode fn, boolean isSSJavaLoop) {
612 case FKind.FlatOpNode: {
613 FlatOpNode fon = (FlatOpNode) fn;
617 if (fon.getOp().getOp() == Operation.ASSIGN) {
618 if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) {
619 // in ssjavaloop, we need to take care about reading local variables!
620 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
621 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
622 rhsHeapPath.add(LOCAL);
623 addReadDescriptor(rhsHeapPath, rhs);
630 case FKind.FlatFieldNode:
631 case FKind.FlatElementNode: {
633 FlatFieldNode ffn = (FlatFieldNode) fn;
636 fld = ffn.getField();
639 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
640 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
641 // fldHeapPath.add(fld);
643 if (fld.getType().isImmutable()) {
644 addReadDescriptor(fldHeapPath, fld);
647 // propagate rhs's heap path to the lhs
648 mapHeapPath.put(lhs, fldHeapPath);
653 case FKind.FlatSetFieldNode:
654 case FKind.FlatSetElementNode: {
656 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
658 fld = fsfn.getField();
661 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
662 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
663 // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
671 private boolean hasReadingEffectOnSharedLocation(NTuple<Descriptor> hp, Location loc, Descriptor d) {
672 if (!mapSharedLocation2DescriptorSet.containsKey(loc)) {
675 return mapSharedLocation2DescriptorSet.get(loc).contains(d);
679 private void addReadDescriptor(NTuple<Descriptor> hp, Descriptor d) {
681 Location loc = getLocation(d);
683 if (loc != null && ssjava.isSharedLocation(loc)) {
685 Set<Descriptor> set = mapSharedLocation2DescriptorSet.get(loc);
687 set = new HashSet<Descriptor>();
688 mapSharedLocation2DescriptorSet.put(loc, set);
695 private Location getLocation(Descriptor d) {
697 if (d instanceof FieldDescriptor) {
698 return (Location) ((FieldDescriptor) d).getType().getExtension();
700 assert d instanceof TempDescriptor;
701 CompositeLocation comp = (CompositeLocation) ((TempDescriptor) d).getType().getExtension();
705 return comp.get(comp.getSize() - 1);
711 private void writeLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
712 Location loc = getLocation(d);
713 if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
715 // 1. add field x to the clearing set
716 SharedStatus state = getState(curr, hp);
717 state.addVar(loc, d);
719 // 3. if the set v contains all of variables belonging to the shared
720 // location, set flag to true
721 Set<Descriptor> sharedVarSet = mapSharedLocation2DescriptorSet.get(loc);
722 if (state.getVarSet(loc).containsAll(sharedVarSet)) {
723 state.updateFlag(loc, true);
728 private void readLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
729 // remove reading var x from written set
730 Location loc = getLocation(d);
731 if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
732 SharedStatus state = getState(curr, hp);
733 state.removeVar(loc, d);
737 private SharedStatus getState(ClearingSummary curr, NTuple<Descriptor> hp) {
738 SharedStatus state = curr.get(hp);
740 state = new SharedStatus();
746 private void writtenAnalyis() {
747 // perform second stage analysis: intraprocedural analysis ensure that
749 // variables are definitely written in-between the same read
751 // First, identify ssjava loop entrace
752 FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
753 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
754 flatNodesToVisit.add(fm);
756 LoopFinder loopFinder = new LoopFinder(fm);
758 while (!flatNodesToVisit.isEmpty()) {
759 FlatNode fn = flatNodesToVisit.iterator().next();
760 flatNodesToVisit.remove(fn);
762 String label = (String) state.fn2labelMap.get(fn);
765 if (label.equals(ssjava.SSJAVA)) {
766 ssjavaLoopEntrance = fn;
771 for (int i = 0; i < fn.numNext(); i++) {
772 FlatNode nn = fn.getNext(i);
773 flatNodesToVisit.add(nn);
777 assert ssjavaLoopEntrance != null;
779 // assume that ssjava loop is top-level loop in method, not nested loop
780 Set nestedLoop = loopFinder.nestedLoops();
781 for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
782 LoopFinder lf = (LoopFinder) loopIter.next();
783 if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
788 assert ssjavaLoop != null;
790 writtenAnalysis_analyzeLoop();
794 private void writtenAnalysis_analyzeLoop() {
796 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
797 flatNodesToVisit.add(ssjavaLoopEntrance);
799 loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
801 while (!flatNodesToVisit.isEmpty()) {
802 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
803 flatNodesToVisit.remove(fn);
805 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
806 definitelyWrittenResults.get(fn);
808 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
809 new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
810 for (int i = 0; i < fn.numPrev(); i++) {
811 FlatNode nn = fn.getPrev(i);
812 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
813 definitelyWrittenResults.get(nn);
819 writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
821 // if a new result, schedule forward nodes for analysis
822 if (!curr.equals(prev)) {
823 definitelyWrittenResults.put(fn, curr);
825 for (int i = 0; i < fn.numNext(); i++) {
826 FlatNode nn = fn.getNext(i);
827 if (loopIncElements.contains(nn)) {
828 flatNodesToVisit.add(nn);
836 private void writtenAnalysis_nodeAction(FlatNode fn,
837 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
839 if (fn.equals(loopEntrance)) {
840 // it reaches loop entrance: changes all flag to true
841 Set<NTuple<Descriptor>> keySet = curr.keySet();
842 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
843 NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
844 Hashtable<FlatNode, Boolean> pair = curr.get(key);
846 Set<FlatNode> pairKeySet = pair.keySet();
847 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
848 FlatNode pairKey = (FlatNode) iterator2.next();
849 pair.put(pairKey, Boolean.TRUE);
859 case FKind.FlatOpNode: {
860 FlatOpNode fon = (FlatOpNode) fn;
864 NTuple<Descriptor> rhsHeapPath = computePath(rhs);
865 if (!rhs.getType().isImmutable()) {
866 mapHeapPath.put(lhs, rhsHeapPath);
868 if (fon.getOp().getOp() == Operation.ASSIGN) {
870 readValue(fn, rhsHeapPath, curr);
873 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
874 removeHeapPath(curr, lhsHeapPath);
879 case FKind.FlatLiteralNode: {
880 FlatLiteralNode fln = (FlatLiteralNode) fn;
884 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
885 removeHeapPath(curr, lhsHeapPath);
890 case FKind.FlatFieldNode:
891 case FKind.FlatElementNode: {
893 FlatFieldNode ffn = (FlatFieldNode) fn;
896 fld = ffn.getField();
899 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
900 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
901 fldHeapPath.add(fld);
903 if (fld.getType().isImmutable()) {
904 readValue(fn, fldHeapPath, curr);
907 // propagate rhs's heap path to the lhs
908 mapHeapPath.put(lhs, fldHeapPath);
913 case FKind.FlatSetFieldNode:
914 case FKind.FlatSetElementNode: {
916 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
918 fld = fsfn.getField();
921 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
922 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
923 fldHeapPath.add(fld);
924 removeHeapPath(curr, fldHeapPath);
929 case FKind.FlatCall: {
930 FlatCall fc = (FlatCall) fn;
931 bindHeapPathCallerArgWithCaleeParam(fc);
933 // add <hp,statement,false> in which hp is an element of
935 // of callee: callee has 'read' requirement!
936 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
937 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
939 Hashtable<FlatNode, Boolean> gen = curr.get(read);
941 gen = new Hashtable<FlatNode, Boolean>();
944 Boolean currentStatus = gen.get(fn);
945 if (currentStatus == null) {
946 gen.put(fn, Boolean.FALSE);
948 checkFlag(currentStatus.booleanValue(), fn, read);
952 // removes <hp,statement,flag> if hp is an element of
954 // set of callee. it means that callee will overwrite it
955 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
956 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
957 removeHeapPath(curr, write);
967 private void readValue(FlatNode fn, NTuple<Descriptor> hp,
968 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
969 Hashtable<FlatNode, Boolean> gen = curr.get(hp);
971 gen = new Hashtable<FlatNode, Boolean>();
974 Boolean currentStatus = gen.get(fn);
975 if (currentStatus == null) {
976 gen.put(fn, Boolean.FALSE);
978 checkFlag(currentStatus.booleanValue(), fn, hp);
983 private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
984 NTuple<Descriptor> hp) {
986 // removes all of heap path that starts with prefix 'hp'
987 // since any reference overwrite along heap path gives overwriting side
988 // effects on the value
990 Set<NTuple<Descriptor>> keySet = curr.keySet();
991 for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
992 NTuple<Descriptor> key = iter.next();
993 if (key.startsWith(hp)) {
994 curr.put(key, new Hashtable<FlatNode, Boolean>());
1000 private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
1001 // compute all possible callee set
1002 // transform all READ/OVERWRITE set from the any possible
1006 calleeUnionBoundReadSet.clear();
1007 calleeIntersectBoundOverWriteSet.clear();
1009 MethodDescriptor mdCallee = fc.getMethod();
1010 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1011 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1012 TypeDescriptor typeDesc = fc.getThis().getType();
1013 setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
1015 // create mapping from arg idx to its heap paths
1016 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1017 new Hashtable<Integer, NTuple<Descriptor>>();
1019 // arg idx is starting from 'this' arg
1020 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1021 if (thisHeapPath == null) {
1022 // method is called without creating new flat node representing 'this'
1023 thisHeapPath = new NTuple<Descriptor>();
1024 thisHeapPath.add(fc.getThis());
1027 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1029 for (int i = 0; i < fc.numArgs(); i++) {
1030 TempDescriptor arg = fc.getArg(i);
1031 NTuple<Descriptor> argHeapPath = computePath(arg);
1032 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1035 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1036 MethodDescriptor callee = (MethodDescriptor) iterator.next();
1037 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1039 // binding caller's args and callee's params
1041 Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
1042 if (calleeReadSet == null) {
1043 calleeReadSet = new HashSet<NTuple<Descriptor>>();
1044 mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
1046 Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
1047 if (calleeOverWriteSet == null) {
1048 calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
1049 mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
1052 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1053 new Hashtable<Integer, TempDescriptor>();
1054 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1055 TempDescriptor param = calleeFlatMethod.getParameter(i);
1056 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
1059 Set<NTuple<Descriptor>> calleeBoundReadSet =
1060 bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1061 // union of the current read set and the current callee's
1063 calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1064 Set<NTuple<Descriptor>> calleeBoundWriteSet =
1065 bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1066 // intersection of the current overwrite set and the current
1069 merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
1074 private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1077 "There is a variable, which is reachable through references "
1079 + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1080 + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1085 private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1086 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
1088 Set<NTuple<Descriptor>> inKeySet = in.keySet();
1089 for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1090 NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1091 Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
1093 Set<FlatNode> pairKeySet = inPair.keySet();
1094 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1095 FlatNode pairKey = (FlatNode) iterator2.next();
1096 Boolean inFlag = inPair.get(pairKey);
1098 Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
1099 if (currPair == null) {
1100 currPair = new Hashtable<FlatNode, Boolean>();
1101 curr.put(inKey, currPair);
1104 Boolean currFlag = currPair.get(pairKey);
1105 // by default, flag is set by false
1106 if (currFlag == null) {
1107 currFlag = Boolean.FALSE;
1109 currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
1110 currPair.put(pairKey, currFlag);
1117 private void methodReadOverWriteAnalysis() {
1118 // perform method READ/OVERWRITE analysis
1119 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1120 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1122 sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1124 LinkedList<MethodDescriptor> descriptorListToAnalyze =
1125 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1127 // no need to analyze method having ssjava loop
1128 methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
1130 // current descriptors to visit in fixed-point interprocedural analysis,
1132 // dependency in the call graph
1133 methodDescriptorsToVisitStack.clear();
1135 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1136 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1138 while (!descriptorListToAnalyze.isEmpty()) {
1139 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1140 methodDescriptorsToVisitStack.add(md);
1143 // analyze scheduled methods until there are no more to visit
1144 while (!methodDescriptorsToVisitStack.isEmpty()) {
1145 // start to analyze leaf node
1146 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1147 FlatMethod fm = state.getMethodFlat(md);
1149 Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1150 Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
1152 methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
1154 Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
1155 Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
1157 if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
1158 mapFlatMethodToRead.put(fm, readSet);
1159 mapFlatMethodToOverWrite.put(fm, overWriteSet);
1161 // results for callee changed, so enqueue dependents caller for
1164 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1165 while (depsItr.hasNext()) {
1166 MethodDescriptor methodNext = depsItr.next();
1167 if (!methodDescriptorsToVisitStack.contains(methodNext)
1168 && methodDescriptorToVistSet.contains(methodNext)) {
1169 methodDescriptorsToVisitStack.add(methodNext);
1180 private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1181 Set<NTuple<Descriptor>> overWriteSet) {
1182 if (state.SSJAVADEBUG) {
1183 System.out.println("Definitely written Analyzing: " + fm);
1186 // intraprocedural analysis
1187 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1188 flatNodesToVisit.add(fm);
1190 while (!flatNodesToVisit.isEmpty()) {
1191 FlatNode fn = flatNodesToVisit.iterator().next();
1192 flatNodesToVisit.remove(fn);
1194 Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
1196 for (int i = 0; i < fn.numPrev(); i++) {
1197 FlatNode prevFn = fn.getPrev(i);
1198 Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
1204 methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
1206 Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
1207 if (!curr.equals(writtenSetPrev)) {
1208 mapFlatNodeToWrittenSet.put(fn, curr);
1209 for (int i = 0; i < fn.numNext(); i++) {
1210 FlatNode nn = fn.getNext(i);
1211 flatNodesToVisit.add(nn);
1219 private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
1220 Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
1223 FieldDescriptor fld;
1225 switch (fn.kind()) {
1226 case FKind.FlatMethod: {
1228 // set up initial heap paths for method parameters
1229 FlatMethod fm = (FlatMethod) fn;
1230 for (int i = 0; i < fm.numParameters(); i++) {
1231 TempDescriptor param = fm.getParameter(i);
1232 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1233 heapPath.add(param);
1234 mapHeapPath.put(param, heapPath);
1239 case FKind.FlatOpNode: {
1240 FlatOpNode fon = (FlatOpNode) fn;
1241 // for a normal assign node, need to propagate lhs's heap path to
1243 if (fon.getOp().getOp() == Operation.ASSIGN) {
1244 rhs = fon.getLeft();
1245 lhs = fon.getDest();
1247 NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1248 if (rhsHeapPath != null) {
1249 mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1256 case FKind.FlatFieldNode:
1257 case FKind.FlatElementNode: {
1261 FlatFieldNode ffn = (FlatFieldNode) fn;
1264 fld = ffn.getField();
1267 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1268 if (srcHeapPath != null) {
1269 // if lhs srcHeapPath is null, it means that it is not reachable from
1270 // callee's parameters. so just ignore it
1272 NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1273 readingHeapPath.add(fld);
1274 mapHeapPath.put(lhs, readingHeapPath);
1277 if (fld.getType().isImmutable()) {
1278 // if WT doesnot have hp(x.f), add hp(x.f) to READ
1279 if (!writtenSet.contains(readingHeapPath)) {
1280 readSet.add(readingHeapPath);
1284 // need to kill hp(x.f) from WT
1285 writtenSet.remove(readingHeapPath);
1291 case FKind.FlatSetFieldNode:
1292 case FKind.FlatSetElementNode: {
1295 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1296 lhs = fsfn.getDst();
1297 fld = fsfn.getField();
1298 rhs = fsfn.getSrc();
1301 NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1302 if (lhsHeapPath != null) {
1303 // if lhs heap path is null, it means that it is not reachable from
1304 // callee's parameters. so just ignore it
1305 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1306 newHeapPath.add(fld);
1307 mapHeapPath.put(fld, newHeapPath);
1310 // need to add hp(y) to WT
1311 writtenSet.add(newHeapPath);
1317 case FKind.FlatCall: {
1319 FlatCall fc = (FlatCall) fn;
1321 bindHeapPathCallerArgWithCaleeParam(fc);
1323 // add heap path, which is an element of READ_bound set and is not
1325 // element of WT set, to the caller's READ set
1326 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1327 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1328 if (!writtenSet.contains(read)) {
1332 writtenSet.removeAll(calleeUnionBoundReadSet);
1334 // add heap path, which is an element of OVERWRITE_bound set, to the
1336 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1337 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1338 writtenSet.add(write);
1344 case FKind.FlatExit: {
1345 // merge the current written set with OVERWRITE set
1346 merge(overWriteSet, writtenSet);
1354 private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
1356 if (inSet.size() == 0) {
1360 Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
1361 new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
1363 for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1365 ClearingSummary inTable = (ClearingSummary) inIterator.next();
1367 Set<NTuple<Descriptor>> keySet = inTable.keySet();
1369 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1370 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1371 SharedStatus inState = inTable.get(hpKey);
1373 SharedStatus currState = curr.get(hpKey);
1374 if (currState == null) {
1375 currState = new SharedStatus();
1376 curr.put(hpKey, currState);
1378 currState.merge(inState);
1380 Set<Location> locSet = inState.getMap().keySet();
1381 for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
1382 Location loc = (Location) iterator2.next();
1383 Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
1384 boolean inFlag = pair.getSecond().booleanValue();
1386 Pair<NTuple<Descriptor>, Location> flagKey =
1387 new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
1388 Boolean current = mapHeapPathLoc2Flag.get(flagKey);
1389 if (current == null) {
1390 current = new Boolean(true);
1392 boolean newInFlag = current.booleanValue() & inFlag;
1393 mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
1400 // merge flag status
1401 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
1402 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
1403 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1404 SharedStatus currState = curr.get(hpKey);
1405 Set<Location> locKeySet = currState.getMap().keySet();
1406 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
1407 Location locKey = (Location) iterator2.next();
1408 Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
1409 boolean currentFlag = pair.getSecond().booleanValue();
1410 Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
1411 if (inFlag != null) {
1412 boolean newFlag = currentFlag | inFlag.booleanValue();
1413 if (currentFlag != newFlag) {
1414 currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
1422 private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
1423 if (curr.isEmpty()) {
1424 // WrittenSet has a special initial value which covers all possible
1426 // For the first time of intersection, we can take all previous set
1429 // otherwise, current set is the intersection of the two sets
1435 // combine two heap path
1436 private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
1437 NTuple<Descriptor> combined = new NTuple<Descriptor>();
1439 for (int i = 0; i < callerIn.size(); i++) {
1440 combined.add(callerIn.get(i));
1443 // the first element of callee's heap path represents parameter
1444 // so we skip the first one since it is already added from caller's heap
1446 for (int i = 1; i < calleeIn.size(); i++) {
1447 combined.add(calleeIn.get(i));
1453 private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
1454 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
1455 Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
1457 Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
1459 Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
1460 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1461 Integer idx = (Integer) iterator.next();
1463 NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
1464 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1466 for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
1467 NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
1468 if (element.startsWith(calleeParam)) {
1469 NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
1470 boundedCalleeSet.add(boundElement);
1476 return boundedCalleeSet;
1480 // Borrowed it from disjoint analysis
1481 private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
1483 Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1485 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1487 Iterator<MethodDescriptor> itr = toSort.iterator();
1488 while (itr.hasNext()) {
1489 MethodDescriptor d = itr.next();
1491 if (!discovered.contains(d)) {
1492 dfsVisit(d, toSort, sorted, discovered);
1499 // While we're doing DFS on call graph, remember
1500 // dependencies for efficient queuing of methods
1501 // during interprocedural analysis:
1503 // a dependent of a method decriptor d for this analysis is:
1504 // 1) a method or task that invokes d
1505 // 2) in the descriptorsToAnalyze set
1506 private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
1507 LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
1511 Iterator itr = callGraph.getCallerSet(md).iterator();
1512 while (itr.hasNext()) {
1513 MethodDescriptor dCaller = (MethodDescriptor) itr.next();
1514 // only consider callers in the original set to analyze
1515 if (!toSort.contains(dCaller)) {
1518 if (!discovered.contains(dCaller)) {
1519 addDependent(md, // callee
1523 dfsVisit(dCaller, toSort, sorted, discovered);
1527 // for leaf-nodes last now!
1531 // a dependent of a method decriptor d for this analysis is:
1532 // 1) a method or task that invokes d
1533 // 2) in the descriptorsToAnalyze set
1534 private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1535 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1537 deps = new HashSet<MethodDescriptor>();
1540 mapDescriptorToSetDependents.put(callee, deps);
1543 private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1544 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1546 deps = new HashSet<MethodDescriptor>();
1547 mapDescriptorToSetDependents.put(callee, deps);
1552 private NTuple<Descriptor> computePath(TempDescriptor td) {
1553 // generate proper path fot input td
1554 // if td is local variable, it just generate one element tuple path
1555 if (mapHeapPath.containsKey(td)) {
1556 return mapHeapPath.get(td);
1558 NTuple<Descriptor> path = new NTuple<Descriptor>();