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.FlatElementNode;
21 import IR.Flat.FlatFieldNode;
22 import IR.Flat.FlatLiteralNode;
23 import IR.Flat.FlatMethod;
24 import IR.Flat.FlatNode;
25 import IR.Flat.FlatOpNode;
26 import IR.Flat.FlatSetElementNode;
27 import IR.Flat.FlatSetFieldNode;
28 import IR.Flat.TempDescriptor;
29 import IR.Tree.Modifiers;
32 public class DefinitelyWrittenCheck {
34 SSJavaAnalysis ssjava;
38 // maps a descriptor to its known dependents: namely
39 // methods or tasks that call the descriptor's method
40 // AND are part of this analysis (reachable from main)
41 private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
43 // maps a flat node to its WrittenSet: this keeps all heap path overwritten
45 private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
47 // maps a temp descriptor to its heap path
48 // each temp descriptor has a unique heap path since we do not allow any
50 private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
52 // maps a flat method to the READ that is the set of heap path that is
53 // expected to be written before method invocation
54 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
56 // maps a flat method to the OVERWRITE that is the set of heap path that is
57 // overwritten on every possible path during method invocation
58 private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
60 // points to method containing SSJAVA Loop
61 private MethodDescriptor methodContainingSSJavaLoop;
63 // maps a flatnode to definitely written analysis mapping M
64 private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
66 // maps a method descriptor to its current summary during the analysis
67 // then analysis reaches fixed-point, this mapping will have the final summary
68 // for each method descriptor
69 private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToCompleteClearingSummary;
71 // maps a method descriptor to the merged incoming caller's current
73 private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToInitialClearingSummary;
75 // maps a flat node to current partial results
76 private Hashtable<FlatNode, ClearingSummary> mapFlatNodeToClearingSummary;
78 // maps shared location to the set of descriptors which belong to the shared
80 private Hashtable<Location, Set<Descriptor>> mapSharedLocation2DescriptorSet;
82 // keep current descriptors to visit in fixed-point interprocedural analysis,
83 private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
85 // when analyzing flatcall, need to re-schedule set of callee
86 private Set<MethodDescriptor> calleesToEnqueue;
88 public static final String arrayElementFieldName = "___element_";
89 static protected Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField;
91 private Set<ClearingSummary> possibleCalleeCompleteSummarySetToCaller;
93 private LinkedList<MethodDescriptor> sortedDescriptors;
95 private FlatNode ssjavaLoopEntrance;
96 private LoopFinder ssjavaLoop;
97 private Set<FlatNode> loopIncElements;
99 private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
100 private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
102 private TempDescriptor LOCAL;
104 public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
106 this.ssjava = ssjava;
107 this.callGraph = ssjava.getCallGraph();
108 this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
109 this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
110 this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
111 this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
112 this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
113 this.definitelyWrittenResults =
114 new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
115 this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
116 this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
118 this.mapMethodDescriptorToCompleteClearingSummary =
119 new Hashtable<MethodDescriptor, ClearingSummary>();
120 this.mapMethodDescriptorToInitialClearingSummary =
121 new Hashtable<MethodDescriptor, ClearingSummary>();
122 this.mapSharedLocation2DescriptorSet = new Hashtable<Location, Set<Descriptor>>();
123 this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
124 this.calleesToEnqueue = new HashSet<MethodDescriptor>();
125 this.possibleCalleeCompleteSummarySetToCaller = new HashSet<ClearingSummary>();
126 this.mapTypeToArrayField = new Hashtable<TypeDescriptor, FieldDescriptor>();
127 this.LOCAL = new TempDescriptor("LOCAL");
130 public void definitelyWrittenCheck() {
131 if (!ssjava.getAnnotationRequireSet().isEmpty()) {
132 methodReadOverWriteAnalysis();
134 sharedLocationAnalysis();
135 checkSharedLocationResult();
139 private void checkSharedLocationResult() {
141 // mapping of method containing ssjava loop has the final result of
142 // shared location analysis
143 ClearingSummary result =
144 mapMethodDescriptorToCompleteClearingSummary.get(sortedDescriptors.peekFirst());
147 Set<NTuple<Descriptor>> hpKeySet = result.keySet();
148 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
149 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
150 SharedStatus state = result.get(hpKey);
151 Set<Location> locKeySet = state.getLocationSet();
152 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
153 Location locKey = (Location) iterator2.next();
154 if (!state.getFlag(locKey)) {
156 "Some concrete locations of the shared abstract location are not cleared at the same time.");
163 private void sharedLocationAnalysis() {
164 // verify that all concrete locations of shared location are cleared out at
165 // the same time once per the out-most loop
167 computeReadSharedDescriptorSet();
169 methodDescriptorsToVisitStack.clear();
171 methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
173 // analyze scheduled methods until there are no more to visit
174 while (!methodDescriptorsToVisitStack.isEmpty()) {
175 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
177 ClearingSummary completeSummary =
178 sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
180 ClearingSummary prevCompleteSummary = mapMethodDescriptorToCompleteClearingSummary.get(md);
182 if (!completeSummary.equals(prevCompleteSummary)) {
184 mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
186 // results for callee changed, so enqueue dependents caller for
188 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
189 while (depsItr.hasNext()) {
190 MethodDescriptor methodNext = depsItr.next();
191 if (!methodDescriptorsToVisitStack.contains(methodNext)) {
192 methodDescriptorsToVisitStack.add(methodNext);
196 // if there is set of callee to be analyzed,
197 // add this set into the top of stack
198 Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
199 while (calleeIter.hasNext()) {
200 MethodDescriptor mdNext = calleeIter.next();
201 if (!methodDescriptorsToVisitStack.contains(mdNext)) {
202 methodDescriptorsToVisitStack.add(mdNext);
205 calleesToEnqueue.clear();
213 private ClearingSummary sharedLocation_analyzeMethod(MethodDescriptor md,
214 boolean onlyVisitSSJavaLoop) {
216 if (state.SSJAVADEBUG) {
217 System.out.println("Definitely written for shared locations Analyzing: " + md + " "
218 + onlyVisitSSJavaLoop);
221 FlatMethod fm = state.getMethodFlat(md);
223 // intraprocedural analysis
224 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
226 // start a new mapping of partial results for each flat node
227 mapFlatNodeToClearingSummary = new Hashtable<FlatNode, ClearingSummary>();
229 if (onlyVisitSSJavaLoop) {
230 flatNodesToVisit.add(ssjavaLoopEntrance);
232 flatNodesToVisit.add(fm);
235 Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
237 while (!flatNodesToVisit.isEmpty()) {
238 FlatNode fn = flatNodesToVisit.iterator().next();
239 flatNodesToVisit.remove(fn);
241 ClearingSummary curr = new ClearingSummary();
243 Set<ClearingSummary> prevSet = new HashSet<ClearingSummary>();
244 for (int i = 0; i < fn.numPrev(); i++) {
245 FlatNode prevFn = fn.getPrev(i);
246 ClearingSummary in = mapFlatNodeToClearingSummary.get(prevFn);
251 mergeSharedLocationAnaylsis(curr, prevSet);
253 sharedLocation_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
254 ClearingSummary clearingPrev = mapFlatNodeToClearingSummary.get(fn);
256 if (!curr.equals(clearingPrev)) {
257 mapFlatNodeToClearingSummary.put(fn, curr);
259 for (int i = 0; i < fn.numNext(); i++) {
260 FlatNode nn = fn.getNext(i);
262 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
263 flatNodesToVisit.add(nn);
271 ClearingSummary completeSummary = new ClearingSummary();
272 Set<ClearingSummary> summarySet = new HashSet<ClearingSummary>();
274 if (onlyVisitSSJavaLoop) {
275 // when analyzing ssjava loop,
276 // complete summary is merging of all previous nodes of ssjava loop
278 for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
279 ClearingSummary frnSummary =
280 mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
281 if (frnSummary != null) {
282 summarySet.add(frnSummary);
286 // merging all exit node summary into the complete summary
287 if (!returnNodeSet.isEmpty()) {
288 for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
289 FlatNode frn = (FlatNode) iterator.next();
290 ClearingSummary frnSummary = mapFlatNodeToClearingSummary.get(frn);
291 summarySet.add(frnSummary);
295 mergeSharedLocationAnaylsis(completeSummary, summarySet);
296 return completeSummary;
299 private void sharedLocation_nodeActions(MethodDescriptor caller, FlatNode fn,
300 ClearingSummary curr, Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
307 case FKind.FlatMethod: {
308 FlatMethod fm = (FlatMethod) fn;
310 ClearingSummary summaryFromCaller =
311 mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
313 Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
314 inSet.add(summaryFromCaller);
315 mergeSharedLocationAnaylsis(curr, inSet);
320 case FKind.FlatOpNode: {
321 FlatOpNode fon = (FlatOpNode) fn;
325 if (fon.getOp().getOp() == Operation.ASSIGN) {
326 if (rhs.getType().isImmutable() && isSSJavaLoop) {
327 // in ssjavaloop, we need to take care about reading local variables!
328 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
329 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
330 rhsHeapPath.add(LOCAL);
331 lhsHeapPath.add(LOCAL);
332 if (!lhs.getSymbol().startsWith("neverused")) {
333 readLocation(curr, rhsHeapPath, rhs);
334 writeLocation(curr, lhsHeapPath, lhs);
342 case FKind.FlatFieldNode:
343 case FKind.FlatElementNode: {
345 FlatFieldNode ffn = (FlatFieldNode) fn;
348 fld = ffn.getField();
351 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
352 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
354 if (fld.getType().isImmutable()) {
355 readLocation(curr, fldHeapPath, fld);
361 case FKind.FlatSetFieldNode:
362 case FKind.FlatSetElementNode: {
364 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
366 fld = fsfn.getField();
369 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
370 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
371 if (fld.getType().isImmutable()) {
372 writeLocation(curr, fldHeapPath, fld);
374 // updates reference field case:
375 // 2. if there exists a tuple t in sharing summary that starts with
376 // hp(x) then, set flag of tuple t to 'true'
377 fldHeapPath.add(fld);
378 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
379 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
380 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
381 if (hpKey.startsWith(fldHeapPath)) {
382 curr.get(hpKey).updateFlag(true);
390 case FKind.FlatCall: {
392 FlatCall fc = (FlatCall) fn;
394 // find out the set of callees
395 MethodDescriptor mdCallee = fc.getMethod();
396 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
397 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
398 TypeDescriptor typeDesc = fc.getThis().getType();
399 setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
401 possibleCalleeCompleteSummarySetToCaller.clear();
403 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
404 MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
405 FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
407 addDependent(mdPossibleCallee, // callee
410 calleesToEnqueue.add(mdPossibleCallee);
412 // updates possible callee's initial summary using caller's current
414 ClearingSummary prevCalleeInitSummary =
415 mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
417 ClearingSummary calleeInitSummary =
418 bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
420 // if changes, update the init summary
421 // and reschedule the callee for analysis
422 if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
424 if (!methodDescriptorsToVisitStack.contains(mdPossibleCallee)) {
425 methodDescriptorsToVisitStack.add(mdPossibleCallee);
427 mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
432 // contribute callee's writing effects to the caller
433 mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
438 case FKind.FlatReturnNode: {
439 returnNodeSet.add(fn);
447 private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc,
448 FlatMethod calleeFlatMethod, ClearingSummary curr) {
450 ClearingSummary boundSet = new ClearingSummary();
452 // create mapping from arg idx to its heap paths
453 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
454 new Hashtable<Integer, NTuple<Descriptor>>();
456 // arg idx is starting from 'this' arg
457 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
458 if (thisHeapPath == null) {
459 // method is called without creating new flat node representing 'this'
460 thisHeapPath = new NTuple<Descriptor>();
461 thisHeapPath.add(fc.getThis());
464 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
466 for (int i = 0; i < fc.numArgs(); i++) {
467 TempDescriptor arg = fc.getArg(i);
468 NTuple<Descriptor> argHeapPath = computePath(arg);
469 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
472 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
473 new Hashtable<Integer, TempDescriptor>();
474 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
475 TempDescriptor param = calleeFlatMethod.getParameter(i);
476 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
479 // binding caller's writing effects to callee's params
480 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
481 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
482 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
484 // iterate over caller's writing effect set
485 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
486 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
487 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
488 // current element is reachable caller's arg
489 // so need to bind it to the caller's side and add it to the callee's
491 if (hpKey.startsWith(argHeapPath)) {
492 NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
493 boundSet.put(boundHeapPath, curr.get(hpKey).clone());
500 // contribute callee's complete summary into the caller's current summary
501 ClearingSummary calleeCompleteSummary =
502 mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
504 if (calleeCompleteSummary != null) {
505 ClearingSummary boundCalleeEfffects = new ClearingSummary();
506 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
507 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
508 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
510 // iterate over callee's writing effect set
511 Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
512 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
513 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
514 // current element is reachable caller's arg
515 // so need to bind it to the caller's side and add it to the callee's
517 if (hpKey.startsWith(calleeParamHeapPath)) {
519 NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
521 boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
527 possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
533 private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
535 // replace the head of heap path with caller's arg path
536 // for example, heap path 'param.a.b' in callee's side will be replaced with
537 // (corresponding arg heap path).a.b for caller's side
539 NTuple<Descriptor> bound = new NTuple<Descriptor>();
541 for (int i = 0; i < argHeapPath.size(); i++) {
542 bound.add(argHeapPath.get(i));
545 for (int i = 1; i < hpKey.size(); i++) {
546 bound.add(hpKey.get(i));
552 private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
553 NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
554 // replace the head of caller's heap path with callee's param heap path
556 NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
557 boundHeapPath.add(calleeParamHeapPath);
559 for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
560 boundHeapPath.add(effectHeapPath.get(i));
563 return boundHeapPath;
566 private void computeReadSharedDescriptorSet() {
567 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
568 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
570 for (Iterator iterator = methodDescriptorsToAnalyze.iterator(); iterator.hasNext();) {
571 MethodDescriptor md = (MethodDescriptor) iterator.next();
572 FlatMethod fm = state.getMethodFlat(md);
573 computeReadSharedDescriptorSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
578 private void computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm,
579 boolean onlyVisitSSJavaLoop) {
581 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
582 Set<FlatNode> visited = new HashSet<FlatNode>();
584 if (onlyVisitSSJavaLoop) {
585 flatNodesToVisit.add(ssjavaLoopEntrance);
587 flatNodesToVisit.add(fm);
590 while (!flatNodesToVisit.isEmpty()) {
591 FlatNode fn = flatNodesToVisit.iterator().next();
592 flatNodesToVisit.remove(fn);
595 computeReadSharedDescriptorSet_nodeActions(fn, onlyVisitSSJavaLoop);
597 for (int i = 0; i < fn.numNext(); i++) {
598 FlatNode nn = fn.getNext(i);
599 if (!visited.contains(nn)) {
600 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
601 flatNodesToVisit.add(nn);
610 private void computeReadSharedDescriptorSet_nodeActions(FlatNode fn, boolean isSSJavaLoop) {
617 case FKind.FlatOpNode: {
618 FlatOpNode fon = (FlatOpNode) fn;
622 if (fon.getOp().getOp() == Operation.ASSIGN) {
623 if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) {
624 // in ssjavaloop, we need to take care about reading local variables!
625 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
626 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
627 rhsHeapPath.add(LOCAL);
628 addReadDescriptor(rhsHeapPath, rhs);
635 case FKind.FlatFieldNode:
636 case FKind.FlatElementNode: {
638 FlatFieldNode ffn = (FlatFieldNode) fn;
641 fld = ffn.getField();
644 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
645 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
646 // fldHeapPath.add(fld);
648 if (fld.getType().isImmutable()) {
649 addReadDescriptor(fldHeapPath, fld);
652 // propagate rhs's heap path to the lhs
653 mapHeapPath.put(lhs, fldHeapPath);
658 case FKind.FlatSetFieldNode:
659 case FKind.FlatSetElementNode: {
661 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
663 fld = fsfn.getField();
666 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
667 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
668 // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
676 private boolean hasReadingEffectOnSharedLocation(NTuple<Descriptor> hp, Location loc, Descriptor d) {
677 if (!mapSharedLocation2DescriptorSet.containsKey(loc)) {
680 return mapSharedLocation2DescriptorSet.get(loc).contains(d);
684 private void addReadDescriptor(NTuple<Descriptor> hp, Descriptor d) {
686 Location loc = getLocation(d);
688 if (loc != null && ssjava.isSharedLocation(loc)) {
690 Set<Descriptor> set = mapSharedLocation2DescriptorSet.get(loc);
692 set = new HashSet<Descriptor>();
693 mapSharedLocation2DescriptorSet.put(loc, set);
700 private Location getLocation(Descriptor d) {
702 if (d instanceof FieldDescriptor) {
703 return (Location) ((FieldDescriptor) d).getType().getExtension();
705 assert d instanceof TempDescriptor;
706 CompositeLocation comp = (CompositeLocation) ((TempDescriptor) d).getType().getExtension();
710 return comp.get(comp.getSize() - 1);
716 private void writeLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
717 Location loc = getLocation(d);
718 if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
720 // 1. add field x to the clearing set
721 SharedStatus state = getState(curr, hp);
722 state.addVar(loc, d);
724 // 3. if the set v contains all of variables belonging to the shared
725 // location, set flag to true
726 Set<Descriptor> sharedVarSet = mapSharedLocation2DescriptorSet.get(loc);
727 if (state.getVarSet(loc).containsAll(sharedVarSet)) {
728 state.updateFlag(loc, true);
733 private void readLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
734 // remove reading var x from written set
735 Location loc = getLocation(d);
736 if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
737 SharedStatus state = getState(curr, hp);
738 state.removeVar(loc, d);
742 private SharedStatus getState(ClearingSummary curr, NTuple<Descriptor> hp) {
743 SharedStatus state = curr.get(hp);
745 state = new SharedStatus();
751 private void writtenAnalyis() {
752 // perform second stage analysis: intraprocedural analysis ensure that
754 // variables are definitely written in-between the same read
756 // First, identify ssjava loop entrace
757 FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
758 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
759 flatNodesToVisit.add(fm);
761 LoopFinder loopFinder = new LoopFinder(fm);
763 while (!flatNodesToVisit.isEmpty()) {
764 FlatNode fn = flatNodesToVisit.iterator().next();
765 flatNodesToVisit.remove(fn);
767 String label = (String) state.fn2labelMap.get(fn);
770 if (label.equals(ssjava.SSJAVA)) {
771 ssjavaLoopEntrance = fn;
776 for (int i = 0; i < fn.numNext(); i++) {
777 FlatNode nn = fn.getNext(i);
778 flatNodesToVisit.add(nn);
782 assert ssjavaLoopEntrance != null;
784 // assume that ssjava loop is top-level loop in method, not nested loop
785 Set nestedLoop = loopFinder.nestedLoops();
786 for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
787 LoopFinder lf = (LoopFinder) loopIter.next();
788 if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
793 assert ssjavaLoop != null;
795 writtenAnalysis_analyzeLoop();
799 private void writtenAnalysis_analyzeLoop() {
801 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
802 flatNodesToVisit.add(ssjavaLoopEntrance);
804 loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
806 while (!flatNodesToVisit.isEmpty()) {
807 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
808 flatNodesToVisit.remove(fn);
810 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
811 definitelyWrittenResults.get(fn);
813 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
814 new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
815 for (int i = 0; i < fn.numPrev(); i++) {
816 FlatNode nn = fn.getPrev(i);
817 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
818 definitelyWrittenResults.get(nn);
824 writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
826 // if a new result, schedule forward nodes for analysis
827 if (!curr.equals(prev)) {
828 definitelyWrittenResults.put(fn, curr);
830 for (int i = 0; i < fn.numNext(); i++) {
831 FlatNode nn = fn.getNext(i);
832 if (loopIncElements.contains(nn)) {
833 flatNodesToVisit.add(nn);
841 private void writtenAnalysis_nodeAction(FlatNode fn,
842 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
844 if (fn.equals(loopEntrance)) {
845 // it reaches loop entrance: changes all flag to true
846 Set<NTuple<Descriptor>> keySet = curr.keySet();
847 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
848 NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
849 Hashtable<FlatNode, Boolean> pair = curr.get(key);
851 Set<FlatNode> pairKeySet = pair.keySet();
852 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
853 FlatNode pairKey = (FlatNode) iterator2.next();
854 pair.put(pairKey, Boolean.TRUE);
864 case FKind.FlatOpNode: {
865 FlatOpNode fon = (FlatOpNode) fn;
869 NTuple<Descriptor> rhsHeapPath = computePath(rhs);
870 if (!rhs.getType().isImmutable()) {
871 mapHeapPath.put(lhs, rhsHeapPath);
873 if (fon.getOp().getOp() == Operation.ASSIGN) {
875 readValue(fn, rhsHeapPath, curr);
878 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
879 removeHeapPath(curr, lhsHeapPath);
884 case FKind.FlatLiteralNode: {
885 FlatLiteralNode fln = (FlatLiteralNode) fn;
889 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
890 removeHeapPath(curr, lhsHeapPath);
895 case FKind.FlatFieldNode:
896 case FKind.FlatElementNode: {
898 if (fn.kind() == FKind.FlatFieldNode) {
899 FlatFieldNode ffn = (FlatFieldNode) fn;
902 fld = ffn.getField();
904 FlatElementNode fen = (FlatElementNode) fn;
907 TypeDescriptor td = rhs.getType().dereference();
908 fld = getArrayField(td);
911 if (fld.isFinal() /* && fld.isStatic() */) {
912 // if field is final and static, no need to check
917 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
918 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
919 fldHeapPath.add(fld);
921 if (fld.getType().isImmutable()) {
922 readValue(fn, fldHeapPath, curr);
925 // propagate rhs's heap path to the lhs
926 mapHeapPath.put(lhs, fldHeapPath);
931 case FKind.FlatSetFieldNode:
932 case FKind.FlatSetElementNode: {
934 if (fn.kind() == FKind.FlatSetFieldNode) {
935 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
937 fld = fsfn.getField();
939 FlatSetElementNode fsen = (FlatSetElementNode) fn;
942 TypeDescriptor td = lhs.getType().dereference();
943 fld = getArrayField(td);
947 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
948 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
949 fldHeapPath.add(fld);
950 removeHeapPath(curr, fldHeapPath);
955 case FKind.FlatCall: {
956 FlatCall fc = (FlatCall) fn;
957 bindHeapPathCallerArgWithCaleeParam(fc);
958 // add <hp,statement,false> in which hp is an element of
960 // of callee: callee has 'read' requirement!
963 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
964 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
965 Hashtable<FlatNode, Boolean> gen = curr.get(read);
967 gen = new Hashtable<FlatNode, Boolean>();
970 Boolean currentStatus = gen.get(fn);
971 if (currentStatus == null) {
972 gen.put(fn, Boolean.FALSE);
974 checkFlag(currentStatus.booleanValue(), fn, read);
978 // removes <hp,statement,flag> if hp is an element of
980 // set of callee. it means that callee will overwrite it
981 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
982 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
983 removeHeapPath(curr, write);
993 private void readValue(FlatNode fn, NTuple<Descriptor> hp,
994 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
995 Hashtable<FlatNode, Boolean> gen = curr.get(hp);
997 gen = new Hashtable<FlatNode, Boolean>();
1000 Boolean currentStatus = gen.get(fn);
1001 if (currentStatus == null) {
1002 gen.put(fn, Boolean.FALSE);
1004 checkFlag(currentStatus.booleanValue(), fn, hp);
1009 private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1010 NTuple<Descriptor> hp) {
1012 // removes all of heap path that starts with prefix 'hp'
1013 // since any reference overwrite along heap path gives overwriting side
1014 // effects on the value
1016 Set<NTuple<Descriptor>> keySet = curr.keySet();
1017 for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
1018 NTuple<Descriptor> key = iter.next();
1019 if (key.startsWith(hp)) {
1020 curr.put(key, new Hashtable<FlatNode, Boolean>());
1026 private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
1027 // compute all possible callee set
1028 // transform all READ/OVERWRITE set from the any possible
1031 calleeUnionBoundReadSet.clear();
1032 calleeIntersectBoundOverWriteSet.clear();
1034 MethodDescriptor mdCallee = fc.getMethod();
1035 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1036 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1037 TypeDescriptor typeDesc = fc.getThis().getType();
1038 setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
1040 // create mapping from arg idx to its heap paths
1041 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1042 new Hashtable<Integer, NTuple<Descriptor>>();
1044 // arg idx is starting from 'this' arg
1045 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1046 if (thisHeapPath == null) {
1047 // method is called without creating new flat node representing 'this'
1048 thisHeapPath = new NTuple<Descriptor>();
1049 thisHeapPath.add(fc.getThis());
1052 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1054 for (int i = 0; i < fc.numArgs(); i++) {
1055 TempDescriptor arg = fc.getArg(i);
1056 NTuple<Descriptor> argHeapPath = computePath(arg);
1057 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1060 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1061 MethodDescriptor callee = (MethodDescriptor) iterator.next();
1062 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1064 // binding caller's args and callee's params
1066 Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
1067 if (calleeReadSet == null) {
1068 calleeReadSet = new HashSet<NTuple<Descriptor>>();
1069 mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
1071 Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
1072 if (calleeOverWriteSet == null) {
1073 calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
1074 mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
1077 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1078 new Hashtable<Integer, TempDescriptor>();
1079 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1080 TempDescriptor param = calleeFlatMethod.getParameter(i);
1081 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
1084 Set<NTuple<Descriptor>> calleeBoundReadSet =
1085 bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1086 // union of the current read set and the current callee's
1088 calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1089 Set<NTuple<Descriptor>> calleeBoundWriteSet =
1090 bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1091 // intersection of the current overwrite set and the current
1094 merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
1099 private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1102 "There is a variable, which is reachable through references "
1104 + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1105 + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1110 private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1111 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
1113 Set<NTuple<Descriptor>> inKeySet = in.keySet();
1114 for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1115 NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1116 Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
1118 Set<FlatNode> pairKeySet = inPair.keySet();
1119 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1120 FlatNode pairKey = (FlatNode) iterator2.next();
1121 Boolean inFlag = inPair.get(pairKey);
1123 Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
1124 if (currPair == null) {
1125 currPair = new Hashtable<FlatNode, Boolean>();
1126 curr.put(inKey, currPair);
1129 Boolean currFlag = currPair.get(pairKey);
1130 // by default, flag is set by false
1131 if (currFlag == null) {
1132 currFlag = Boolean.FALSE;
1134 currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
1135 currPair.put(pairKey, currFlag);
1142 private void methodReadOverWriteAnalysis() {
1143 // perform method READ/OVERWRITE analysis
1144 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1145 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1147 sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1149 LinkedList<MethodDescriptor> descriptorListToAnalyze =
1150 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1152 // no need to analyze method having ssjava loop
1153 // methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
1154 methodContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop();
1156 // current descriptors to visit in fixed-point interprocedural analysis,
1158 // dependency in the call graph
1159 methodDescriptorsToVisitStack.clear();
1161 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1162 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1164 while (!descriptorListToAnalyze.isEmpty()) {
1165 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1166 methodDescriptorsToVisitStack.add(md);
1169 // analyze scheduled methods until there are no more to visit
1170 while (!methodDescriptorsToVisitStack.isEmpty()) {
1171 // start to analyze leaf node
1172 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1173 FlatMethod fm = state.getMethodFlat(md);
1175 Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1176 Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
1178 methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
1180 Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
1181 Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
1183 if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
1184 mapFlatMethodToRead.put(fm, readSet);
1185 mapFlatMethodToOverWrite.put(fm, overWriteSet);
1187 // results for callee changed, so enqueue dependents caller for
1190 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1191 while (depsItr.hasNext()) {
1192 MethodDescriptor methodNext = depsItr.next();
1193 if (!methodDescriptorsToVisitStack.contains(methodNext)
1194 && methodDescriptorToVistSet.contains(methodNext)) {
1195 methodDescriptorsToVisitStack.add(methodNext);
1206 private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1207 Set<NTuple<Descriptor>> overWriteSet) {
1208 if (state.SSJAVADEBUG) {
1209 System.out.println("Definitely written Analyzing: " + fm);
1212 // intraprocedural analysis
1213 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1214 flatNodesToVisit.add(fm);
1216 while (!flatNodesToVisit.isEmpty()) {
1217 FlatNode fn = flatNodesToVisit.iterator().next();
1218 flatNodesToVisit.remove(fn);
1220 Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
1222 for (int i = 0; i < fn.numPrev(); i++) {
1223 FlatNode prevFn = fn.getPrev(i);
1224 Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
1230 methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
1232 Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
1233 if (!curr.equals(writtenSetPrev)) {
1234 mapFlatNodeToWrittenSet.put(fn, curr);
1235 for (int i = 0; i < fn.numNext(); i++) {
1236 FlatNode nn = fn.getNext(i);
1237 flatNodesToVisit.add(nn);
1245 private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
1246 Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
1249 FieldDescriptor fld;
1251 switch (fn.kind()) {
1252 case FKind.FlatMethod: {
1254 // set up initial heap paths for method parameters
1255 FlatMethod fm = (FlatMethod) fn;
1256 for (int i = 0; i < fm.numParameters(); i++) {
1257 TempDescriptor param = fm.getParameter(i);
1258 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1259 heapPath.add(param);
1260 mapHeapPath.put(param, heapPath);
1265 case FKind.FlatOpNode: {
1266 FlatOpNode fon = (FlatOpNode) fn;
1267 // for a normal assign node, need to propagate lhs's heap path to
1269 if (fon.getOp().getOp() == Operation.ASSIGN) {
1270 rhs = fon.getLeft();
1271 lhs = fon.getDest();
1273 NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1274 if (rhsHeapPath != null) {
1275 mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1282 case FKind.FlatElementNode:
1283 case FKind.FlatFieldNode: {
1287 if (fn.kind() == FKind.FlatFieldNode) {
1288 FlatFieldNode ffn = (FlatFieldNode) fn;
1291 fld = ffn.getField();
1293 FlatElementNode fen = (FlatElementNode) fn;
1296 TypeDescriptor td = rhs.getType().dereference();
1297 fld = getArrayField(td);
1300 if (fld.isFinal() /* && fld.isStatic() */) {
1301 // if field is final and static, no need to check
1306 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1307 if (srcHeapPath != null) {
1308 // if lhs srcHeapPath is null, it means that it is not reachable from
1309 // callee's parameters. so just ignore it
1311 NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1312 readingHeapPath.add(fld);
1313 mapHeapPath.put(lhs, readingHeapPath);
1316 if (fld.getType().isImmutable()) {
1317 // if WT doesnot have hp(x.f), add hp(x.f) to READ
1318 if (!writtenSet.contains(readingHeapPath)) {
1319 readSet.add(readingHeapPath);
1323 //no need to kill hp(x.f) from WT
1329 case FKind.FlatSetFieldNode:
1330 case FKind.FlatSetElementNode: {
1334 if (fn.kind() == FKind.FlatSetFieldNode) {
1335 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1336 lhs = fsfn.getDst();
1337 fld = fsfn.getField();
1338 rhs = fsfn.getSrc();
1340 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1341 lhs = fsen.getDst();
1342 rhs = fsen.getSrc();
1343 TypeDescriptor td = lhs.getType().dereference();
1344 fld = getArrayField(td);
1348 NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1349 if (lhsHeapPath != null) {
1350 // if lhs heap path is null, it means that it is not reachable from
1351 // callee's parameters. so just ignore it
1352 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1353 newHeapPath.add(fld);
1354 mapHeapPath.put(fld, newHeapPath);
1357 // need to add hp(y) to WT
1358 writtenSet.add(newHeapPath);
1364 case FKind.FlatCall: {
1366 FlatCall fc = (FlatCall) fn;
1368 if (fc.getThis() != null) {
1369 bindHeapPathCallerArgWithCaleeParam(fc);
1371 // add heap path, which is an element of READ_bound set and is not
1373 // element of WT set, to the caller's READ set
1374 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1375 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1376 if (!writtenSet.contains(read)) {
1381 // add heap path, which is an element of OVERWRITE_bound set, to the
1383 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1384 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1385 writtenSet.add(write);
1392 case FKind.FlatExit: {
1393 // merge the current written set with OVERWRITE set
1394 merge(overWriteSet, writtenSet);
1402 static public FieldDescriptor getArrayField(TypeDescriptor td) {
1403 FieldDescriptor fd = mapTypeToArrayField.get(td);
1406 new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), td, arrayElementFieldName, null,
1408 mapTypeToArrayField.put(td, fd);
1413 private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
1415 if (inSet.size() == 0) {
1419 Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
1420 new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
1422 for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1424 ClearingSummary inTable = (ClearingSummary) inIterator.next();
1426 Set<NTuple<Descriptor>> keySet = inTable.keySet();
1428 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1429 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1430 SharedStatus inState = inTable.get(hpKey);
1432 SharedStatus currState = curr.get(hpKey);
1433 if (currState == null) {
1434 currState = new SharedStatus();
1435 curr.put(hpKey, currState);
1437 currState.merge(inState);
1439 Set<Location> locSet = inState.getMap().keySet();
1440 for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
1441 Location loc = (Location) iterator2.next();
1442 Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
1443 boolean inFlag = pair.getSecond().booleanValue();
1445 Pair<NTuple<Descriptor>, Location> flagKey =
1446 new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
1447 Boolean current = mapHeapPathLoc2Flag.get(flagKey);
1448 if (current == null) {
1449 current = new Boolean(true);
1451 boolean newInFlag = current.booleanValue() & inFlag;
1452 mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
1459 // merge flag status
1460 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
1461 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
1462 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1463 SharedStatus currState = curr.get(hpKey);
1464 Set<Location> locKeySet = currState.getMap().keySet();
1465 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
1466 Location locKey = (Location) iterator2.next();
1467 Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
1468 boolean currentFlag = pair.getSecond().booleanValue();
1469 Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
1470 if (inFlag != null) {
1471 boolean newFlag = currentFlag | inFlag.booleanValue();
1472 if (currentFlag != newFlag) {
1473 currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
1481 private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
1482 if (curr.isEmpty()) {
1483 // WrittenSet has a special initial value which covers all possible
1485 // For the first time of intersection, we can take all previous set
1488 // otherwise, current set is the intersection of the two sets
1494 // combine two heap path
1495 private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
1496 NTuple<Descriptor> combined = new NTuple<Descriptor>();
1498 for (int i = 0; i < callerIn.size(); i++) {
1499 combined.add(callerIn.get(i));
1502 // the first element of callee's heap path represents parameter
1503 // so we skip the first one since it is already added from caller's heap
1505 for (int i = 1; i < calleeIn.size(); i++) {
1506 combined.add(calleeIn.get(i));
1512 private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
1513 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
1514 Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
1516 Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
1518 Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
1519 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1520 Integer idx = (Integer) iterator.next();
1522 NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
1523 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1525 for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
1526 NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
1527 if (element.startsWith(calleeParam)) {
1528 NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
1529 boundedCalleeSet.add(boundElement);
1535 return boundedCalleeSet;
1539 // Borrowed it from disjoint analysis
1540 private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
1542 Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1544 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1546 Iterator<MethodDescriptor> itr = toSort.iterator();
1547 while (itr.hasNext()) {
1548 MethodDescriptor d = itr.next();
1550 if (!discovered.contains(d)) {
1551 dfsVisit(d, toSort, sorted, discovered);
1558 // While we're doing DFS on call graph, remember
1559 // dependencies for efficient queuing of methods
1560 // during interprocedural analysis:
1562 // a dependent of a method decriptor d for this analysis is:
1563 // 1) a method or task that invokes d
1564 // 2) in the descriptorsToAnalyze set
1565 private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
1566 LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
1570 Iterator itr = callGraph.getCallerSet(md).iterator();
1571 while (itr.hasNext()) {
1572 MethodDescriptor dCaller = (MethodDescriptor) itr.next();
1573 // only consider callers in the original set to analyze
1574 if (!toSort.contains(dCaller)) {
1577 if (!discovered.contains(dCaller)) {
1578 addDependent(md, // callee
1582 dfsVisit(dCaller, toSort, sorted, discovered);
1586 // for leaf-nodes last now!
1590 // a dependent of a method decriptor d for this analysis is:
1591 // 1) a method or task that invokes d
1592 // 2) in the descriptorsToAnalyze set
1593 private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1594 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1596 deps = new HashSet<MethodDescriptor>();
1599 mapDescriptorToSetDependents.put(callee, deps);
1602 private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1603 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1605 deps = new HashSet<MethodDescriptor>();
1606 mapDescriptorToSetDependents.put(callee, deps);
1611 private NTuple<Descriptor> computePath(TempDescriptor td) {
1612 // generate proper path fot input td
1613 // if td is local variable, it just generate one element tuple path
1614 if (mapHeapPath.containsKey(td)) {
1615 return mapHeapPath.get(td);
1617 NTuple<Descriptor> path = new NTuple<Descriptor>();