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, Hashtable<NTuple<Descriptor>, SharedLocState>> mapMethodDescriptorToCompleteClearingSummary;
68 // maps a method descriptor to the merged incoming caller's current
70 private Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, SharedLocState>> mapMethodDescriptorToInitialClearingSummary;
72 // maps a flat node to current partial results
73 private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, SharedLocState>> 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<Hashtable<NTuple<Descriptor>, SharedLocState>> 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, Hashtable<NTuple<Descriptor>, SharedLocState>>();
114 this.mapMethodDescriptorToInitialClearingSummary =
115 new Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, SharedLocState>>();
116 this.mapSharedLocation2DescriptorSet = new Hashtable<Location, Set<Descriptor>>();
117 this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
118 this.calleesToEnqueue = new HashSet<MethodDescriptor>();
119 this.possibleCalleeCompleteSummarySetToCaller =
120 new HashSet<Hashtable<NTuple<Descriptor>, SharedLocState>>();
121 this.LOCAL = new TempDescriptor("LOCAL");
124 public void definitelyWrittenCheck() {
125 if (!ssjava.getAnnotationRequireSet().isEmpty()) {
126 methodReadOverWriteAnalysis();
128 sharedLocationAnalysis();
129 checkSharedLocationResult();
133 private void checkSharedLocationResult() {
135 // mapping of method containing ssjava loop has the final result of
136 // shared location analysis
137 Hashtable<NTuple<Descriptor>, SharedLocState> result =
138 mapMethodDescriptorToCompleteClearingSummary.get(sortedDescriptors.peekFirst());
140 System.out.println("checkSharedLocationResult=" + result);
142 Set<NTuple<Descriptor>> hpKeySet = result.keySet();
143 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
144 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
145 SharedLocState state = result.get(hpKey);
146 Set<Location> locKeySet = state.getLocationSet();
147 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
148 Location locKey = (Location) iterator2.next();
149 if (!state.getFlag(locKey)) {
151 "Some concrete locations of the shared abstract location are not cleared at the same time.");
158 private void sharedLocationAnalysis() {
159 // verify that all concrete locations of shared location are cleared out at
160 // the same time once per the out-most loop
162 computeReadSharedDescriptorSet();
163 System.out.println("Reading Shared Location=" + mapSharedLocation2DescriptorSet);
165 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
167 methodDescriptorsToVisitStack.clear();
168 methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
169 methodDescriptorToVistSet.add(sortedDescriptors.peekFirst());
171 // analyze scheduled methods until there are no more to visit
172 while (!methodDescriptorsToVisitStack.isEmpty()) {
173 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
174 methodDescriptorToVistSet.remove(md);
176 Hashtable<NTuple<Descriptor>, SharedLocState> completeSummary =
177 sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
179 Hashtable<NTuple<Descriptor>, SharedLocState> prevCompleteSummary =
180 mapMethodDescriptorToCompleteClearingSummary.get(md);
182 if (!completeSummary.equals(prevCompleteSummary)) {
184 mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
186 Set<MethodDescriptor> dependentsSet = getDependents(md);
187 if (dependentsSet.size() == 0) {
188 dependentsSet.add(methodContainingSSJavaLoop);
191 // results for callee changed, so enqueue dependents caller for
193 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
194 while (depsItr.hasNext()) {
195 MethodDescriptor methodNext = depsItr.next();
196 if (!methodDescriptorsToVisitStack.contains(methodNext)
197 && !methodDescriptorToVistSet.contains(methodNext)) {
198 methodDescriptorsToVisitStack.add(methodNext);
202 // if there is set of callee to be analyzed,
203 // add this set into the top of stack
204 Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
205 while (calleeIter.hasNext()) {
206 MethodDescriptor mdNext = calleeIter.next();
207 methodDescriptorsToVisitStack.add(mdNext);
209 calleesToEnqueue.clear();
215 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
216 flatNodesToVisit.add(ssjavaLoopEntrance);
220 private Hashtable<NTuple<Descriptor>, SharedLocState> sharedLocation_analyzeMethod(
221 MethodDescriptor md, boolean onlyVisitSSJavaLoop) {
223 if (state.SSJAVADEBUG) {
224 System.out.println("Definitely written for shared locations Analyzing: " + md + " "
225 + onlyVisitSSJavaLoop);
228 FlatMethod fm = state.getMethodFlat(md);
230 // intraprocedural analysis
231 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
233 // start a new mapping of partial results for each flat node
234 mapFlatNodeToClearingSummary =
235 new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, SharedLocState>>();
237 if (onlyVisitSSJavaLoop) {
238 flatNodesToVisit.add(ssjavaLoopEntrance);
240 flatNodesToVisit.add(fm);
243 Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
245 while (!flatNodesToVisit.isEmpty()) {
246 FlatNode fn = flatNodesToVisit.iterator().next();
247 flatNodesToVisit.remove(fn);
249 Hashtable<NTuple<Descriptor>, SharedLocState> curr =
250 new Hashtable<NTuple<Descriptor>, SharedLocState>();
252 Set<Hashtable<NTuple<Descriptor>, SharedLocState>> prevSet =
253 new HashSet<Hashtable<NTuple<Descriptor>, SharedLocState>>();
254 for (int i = 0; i < fn.numPrev(); i++) {
255 FlatNode prevFn = fn.getPrev(i);
256 Hashtable<NTuple<Descriptor>, SharedLocState> in = mapFlatNodeToClearingSummary.get(prevFn);
261 mergeSharedLocationAnaylsis(curr, prevSet);
263 sharedLocation_nodeActions(fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
264 Hashtable<NTuple<Descriptor>, SharedLocState> clearingPrev =
265 mapFlatNodeToClearingSummary.get(fn);
267 if (!curr.equals(clearingPrev)) {
268 mapFlatNodeToClearingSummary.put(fn, curr);
270 for (int i = 0; i < fn.numNext(); i++) {
271 FlatNode nn = fn.getNext(i);
273 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
274 flatNodesToVisit.add(nn);
282 Hashtable<NTuple<Descriptor>, SharedLocState> completeSummary =
283 new Hashtable<NTuple<Descriptor>, SharedLocState>();
285 Set<Hashtable<NTuple<Descriptor>, SharedLocState>> summarySet =
286 new HashSet<Hashtable<NTuple<Descriptor>, SharedLocState>>();
287 if (onlyVisitSSJavaLoop) {
288 // when analyzing ssjava loop,
289 // complete summary is merging of all previous nodes of ssjava loop
291 for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
292 Hashtable<NTuple<Descriptor>, SharedLocState> frnSummary =
293 mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
294 if (frnSummary != null) {
295 summarySet.add(frnSummary);
299 // merging all exit node summary into the complete summary
300 if (!returnNodeSet.isEmpty()) {
301 for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
302 FlatNode frn = (FlatNode) iterator.next();
303 Hashtable<NTuple<Descriptor>, SharedLocState> frnSummary =
304 mapFlatNodeToClearingSummary.get(frn);
305 summarySet.add(frnSummary);
309 mergeSharedLocationAnaylsis(completeSummary, summarySet);
310 return completeSummary;
313 private void sharedLocation_nodeActions(FlatNode fn,
314 Hashtable<NTuple<Descriptor>, SharedLocState> curr, Set<FlatNode> returnNodeSet,
315 boolean isSSJavaLoop) {
322 case FKind.FlatMethod: {
323 FlatMethod fm = (FlatMethod) fn;
325 Hashtable<NTuple<Descriptor>, SharedLocState> summaryFromCaller =
326 mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
328 Set<Hashtable<NTuple<Descriptor>, SharedLocState>> inSet =
329 new HashSet<Hashtable<NTuple<Descriptor>, SharedLocState>>();
330 inSet.add(summaryFromCaller);
331 mergeSharedLocationAnaylsis(curr, inSet);
336 case FKind.FlatOpNode: {
337 FlatOpNode fon = (FlatOpNode) fn;
341 if (fon.getOp().getOp() == Operation.ASSIGN) {
342 if (rhs.getType().isImmutable() && isSSJavaLoop) {
343 // in ssjavaloop, we need to take care about reading local variables!
344 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
345 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
346 rhsHeapPath.add(LOCAL);
347 lhsHeapPath.add(LOCAL);
348 if (!lhs.getSymbol().startsWith("neverused")) {
349 readLocation(curr, rhsHeapPath, rhs);
350 writeLocation(curr, lhsHeapPath, lhs);
358 case FKind.FlatFieldNode:
359 case FKind.FlatElementNode: {
361 FlatFieldNode ffn = (FlatFieldNode) fn;
364 fld = ffn.getField();
367 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
368 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
370 if (fld.getType().isImmutable()) {
371 readLocation(curr, fldHeapPath, fld);
377 case FKind.FlatSetFieldNode:
378 case FKind.FlatSetElementNode: {
380 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
382 fld = fsfn.getField();
385 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
386 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
387 if (fld.getType().isImmutable()) {
388 writeLocation(curr, fldHeapPath, fld);
394 case FKind.FlatCall: {
396 FlatCall fc = (FlatCall) fn;
398 // find out the set of callees
399 MethodDescriptor mdCallee = fc.getMethod();
400 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
401 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
402 TypeDescriptor typeDesc = fc.getThis().getType();
403 setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
405 possibleCalleeCompleteSummarySetToCaller.clear();
407 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
408 MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
409 FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
411 calleesToEnqueue.add(mdPossibleCallee);
413 // updates possible callee's initial summary using caller's current
415 Hashtable<NTuple<Descriptor>, SharedLocState> prevCalleeInitSummary =
416 mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
418 Hashtable<NTuple<Descriptor>, SharedLocState> calleeInitSummary =
419 bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
421 // if changes, update the init summary
422 // and reschedule the callee for analysis
423 if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
424 methodDescriptorsToVisitStack.add(mdPossibleCallee);
425 mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
430 // contribute callee's writing effects to the caller
431 mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
436 case FKind.FlatReturnNode: {
437 returnNodeSet.add(fn);
445 private Hashtable<NTuple<Descriptor>, SharedLocState> bindHeapPathOfCalleeCallerEffects(
446 FlatCall fc, FlatMethod calleeFlatMethod, Hashtable<NTuple<Descriptor>, SharedLocState> curr) {
448 Hashtable<NTuple<Descriptor>, SharedLocState> boundSet =
449 new Hashtable<NTuple<Descriptor>, SharedLocState>();
451 // create mapping from arg idx to its heap paths
452 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
453 new Hashtable<Integer, NTuple<Descriptor>>();
455 // arg idx is starting from 'this' arg
456 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
457 if (thisHeapPath == null) {
458 // method is called without creating new flat node representing 'this'
459 thisHeapPath = new NTuple<Descriptor>();
460 thisHeapPath.add(fc.getThis());
463 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
465 for (int i = 0; i < fc.numArgs(); i++) {
466 TempDescriptor arg = fc.getArg(i);
467 NTuple<Descriptor> argHeapPath = computePath(arg);
468 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
471 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
472 new Hashtable<Integer, TempDescriptor>();
473 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
474 TempDescriptor param = calleeFlatMethod.getParameter(i);
475 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
478 // binding caller's writing effects to callee's params
479 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
480 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
481 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
483 // iterate over caller's writing effect set
484 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
485 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
486 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
487 // current element is reachable caller's arg
488 // so need to bind it to the caller's side and add it to the callee's
490 if (hpKey.startsWith(argHeapPath)) {
491 NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
492 boundSet.put(boundHeapPath, curr.get(hpKey).clone());
499 // contribute callee's complete summary into the caller's current summary
500 Hashtable<NTuple<Descriptor>, SharedLocState> calleeCompleteSummary =
501 mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
503 if (calleeCompleteSummary != null) {
504 Hashtable<NTuple<Descriptor>, SharedLocState> boundCalleeEfffects =
505 new Hashtable<NTuple<Descriptor>, SharedLocState>();
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(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
717 NTuple<Descriptor> hp, Descriptor d) {
718 Location loc = getLocation(d);
719 if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
720 SharedLocState state = getState(curr, hp);
721 state.addVar(loc, d);
723 // if the set v contains all of variables belonging to the shared
724 // location, set flag to true
726 Set<Descriptor> sharedVarSet = mapSharedLocation2DescriptorSet.get(loc);
728 if (state.getVarSet(loc).containsAll(sharedVarSet)) {
729 state.updateFlag(loc, true);
734 private void readLocation(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
735 NTuple<Descriptor> hp, Descriptor d) {
736 // remove reading var x from written set
737 Location loc = getLocation(d);
738 if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
739 SharedLocState state = getState(curr, hp);
740 state.removeVar(loc, d);
744 private SharedLocState getState(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
745 NTuple<Descriptor> hp) {
746 SharedLocState state = curr.get(hp);
748 state = new SharedLocState();
754 private void writtenAnalyis() {
755 // perform second stage analysis: intraprocedural analysis ensure that
757 // variables are definitely written in-between the same read
759 // First, identify ssjava loop entrace
760 FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
761 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
762 flatNodesToVisit.add(fm);
764 LoopFinder loopFinder = new LoopFinder(fm);
766 while (!flatNodesToVisit.isEmpty()) {
767 FlatNode fn = flatNodesToVisit.iterator().next();
768 flatNodesToVisit.remove(fn);
770 String label = (String) state.fn2labelMap.get(fn);
773 if (label.equals(ssjava.SSJAVA)) {
774 ssjavaLoopEntrance = fn;
779 for (int i = 0; i < fn.numNext(); i++) {
780 FlatNode nn = fn.getNext(i);
781 flatNodesToVisit.add(nn);
785 assert ssjavaLoopEntrance != null;
787 // assume that ssjava loop is top-level loop in method, not nested loop
788 Set nestedLoop = loopFinder.nestedLoops();
789 for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
790 LoopFinder lf = (LoopFinder) loopIter.next();
791 if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
796 assert ssjavaLoop != null;
798 writtenAnalysis_analyzeLoop();
802 private void writtenAnalysis_analyzeLoop() {
804 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
805 flatNodesToVisit.add(ssjavaLoopEntrance);
807 loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
809 while (!flatNodesToVisit.isEmpty()) {
810 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
811 flatNodesToVisit.remove(fn);
813 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
814 definitelyWrittenResults.get(fn);
816 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
817 new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
818 for (int i = 0; i < fn.numPrev(); i++) {
819 FlatNode nn = fn.getPrev(i);
820 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
821 definitelyWrittenResults.get(nn);
827 writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
829 // if a new result, schedule forward nodes for analysis
830 if (!curr.equals(prev)) {
831 definitelyWrittenResults.put(fn, curr);
833 for (int i = 0; i < fn.numNext(); i++) {
834 FlatNode nn = fn.getNext(i);
835 if (loopIncElements.contains(nn)) {
836 flatNodesToVisit.add(nn);
844 private void writtenAnalysis_nodeAction(FlatNode fn,
845 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
847 if (fn.equals(loopEntrance)) {
848 // it reaches loop entrance: changes all flag to true
849 Set<NTuple<Descriptor>> keySet = curr.keySet();
850 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
851 NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
852 Hashtable<FlatNode, Boolean> pair = curr.get(key);
854 Set<FlatNode> pairKeySet = pair.keySet();
855 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
856 FlatNode pairKey = (FlatNode) iterator2.next();
857 pair.put(pairKey, Boolean.TRUE);
867 case FKind.FlatOpNode: {
868 FlatOpNode fon = (FlatOpNode) fn;
872 NTuple<Descriptor> rhsHeapPath = computePath(rhs);
873 if (!rhs.getType().isImmutable()) {
874 mapHeapPath.put(lhs, rhsHeapPath);
876 if (fon.getOp().getOp() == Operation.ASSIGN) {
878 readValue(fn, rhsHeapPath, curr);
881 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
882 removeHeapPath(curr, lhsHeapPath);
887 case FKind.FlatLiteralNode: {
888 FlatLiteralNode fln = (FlatLiteralNode) fn;
892 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
893 removeHeapPath(curr, lhsHeapPath);
898 case FKind.FlatFieldNode:
899 case FKind.FlatElementNode: {
901 FlatFieldNode ffn = (FlatFieldNode) fn;
904 fld = ffn.getField();
907 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
908 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
909 fldHeapPath.add(fld);
911 if (fld.getType().isImmutable()) {
912 readValue(fn, fldHeapPath, curr);
915 // propagate rhs's heap path to the lhs
916 mapHeapPath.put(lhs, fldHeapPath);
921 case FKind.FlatSetFieldNode:
922 case FKind.FlatSetElementNode: {
924 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
926 fld = fsfn.getField();
929 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
930 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
931 fldHeapPath.add(fld);
932 removeHeapPath(curr, fldHeapPath);
937 case FKind.FlatCall: {
938 FlatCall fc = (FlatCall) fn;
939 bindHeapPathCallerArgWithCaleeParam(fc);
941 // add <hp,statement,false> in which hp is an element of
943 // of callee: callee has 'read' requirement!
944 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
945 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
947 Hashtable<FlatNode, Boolean> gen = curr.get(read);
949 gen = new Hashtable<FlatNode, Boolean>();
952 Boolean currentStatus = gen.get(fn);
953 if (currentStatus == null) {
954 gen.put(fn, Boolean.FALSE);
956 checkFlag(currentStatus.booleanValue(), fn, read);
960 // removes <hp,statement,flag> if hp is an element of
962 // set of callee. it means that callee will overwrite it
963 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
964 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
965 removeHeapPath(curr, write);
975 private void readValue(FlatNode fn, NTuple<Descriptor> hp,
976 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
977 Hashtable<FlatNode, Boolean> gen = curr.get(hp);
979 gen = new Hashtable<FlatNode, Boolean>();
982 Boolean currentStatus = gen.get(fn);
983 if (currentStatus == null) {
984 gen.put(fn, Boolean.FALSE);
986 checkFlag(currentStatus.booleanValue(), fn, hp);
991 private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
992 NTuple<Descriptor> hp) {
994 // removes all of heap path that starts with prefix 'hp'
995 // since any reference overwrite along heap path gives overwriting side
996 // effects on the value
998 Set<NTuple<Descriptor>> keySet = curr.keySet();
999 for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
1000 NTuple<Descriptor> key = iter.next();
1001 if (key.startsWith(hp)) {
1002 curr.put(key, new Hashtable<FlatNode, Boolean>());
1008 private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
1009 // compute all possible callee set
1010 // transform all READ/OVERWRITE set from the any possible
1014 calleeUnionBoundReadSet.clear();
1015 calleeIntersectBoundOverWriteSet.clear();
1017 MethodDescriptor mdCallee = fc.getMethod();
1018 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1019 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1020 TypeDescriptor typeDesc = fc.getThis().getType();
1021 setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
1023 // create mapping from arg idx to its heap paths
1024 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1025 new Hashtable<Integer, NTuple<Descriptor>>();
1027 // arg idx is starting from 'this' arg
1028 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1029 if (thisHeapPath == null) {
1030 // method is called without creating new flat node representing 'this'
1031 thisHeapPath = new NTuple<Descriptor>();
1032 thisHeapPath.add(fc.getThis());
1035 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1037 for (int i = 0; i < fc.numArgs(); i++) {
1038 TempDescriptor arg = fc.getArg(i);
1039 NTuple<Descriptor> argHeapPath = computePath(arg);
1040 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1043 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1044 MethodDescriptor callee = (MethodDescriptor) iterator.next();
1045 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1047 // binding caller's args and callee's params
1049 Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
1050 if (calleeReadSet == null) {
1051 calleeReadSet = new HashSet<NTuple<Descriptor>>();
1052 mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
1054 Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
1055 if (calleeOverWriteSet == null) {
1056 calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
1057 mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
1060 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1061 new Hashtable<Integer, TempDescriptor>();
1062 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1063 TempDescriptor param = calleeFlatMethod.getParameter(i);
1064 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
1067 Set<NTuple<Descriptor>> calleeBoundReadSet =
1068 bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1069 // union of the current read set and the current callee's
1071 calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1072 Set<NTuple<Descriptor>> calleeBoundWriteSet =
1073 bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1074 // intersection of the current overwrite set and the current
1077 merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
1082 private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1085 "There is a variable, which is reachable through references "
1087 + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1088 + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1093 private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1094 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
1096 Set<NTuple<Descriptor>> inKeySet = in.keySet();
1097 for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1098 NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1099 Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
1101 Set<FlatNode> pairKeySet = inPair.keySet();
1102 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1103 FlatNode pairKey = (FlatNode) iterator2.next();
1104 Boolean inFlag = inPair.get(pairKey);
1106 Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
1107 if (currPair == null) {
1108 currPair = new Hashtable<FlatNode, Boolean>();
1109 curr.put(inKey, currPair);
1112 Boolean currFlag = currPair.get(pairKey);
1113 // by default, flag is set by false
1114 if (currFlag == null) {
1115 currFlag = Boolean.FALSE;
1117 currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
1118 currPair.put(pairKey, currFlag);
1125 private void methodReadOverWriteAnalysis() {
1126 // perform method READ/OVERWRITE analysis
1127 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1128 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1130 sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1132 LinkedList<MethodDescriptor> descriptorListToAnalyze =
1133 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1135 // no need to analyze method having ssjava loop
1136 methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
1138 // current descriptors to visit in fixed-point interprocedural analysis,
1140 // dependency in the call graph
1141 methodDescriptorsToVisitStack.clear();
1143 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1144 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1146 while (!descriptorListToAnalyze.isEmpty()) {
1147 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1148 methodDescriptorsToVisitStack.add(md);
1151 // analyze scheduled methods until there are no more to visit
1152 while (!methodDescriptorsToVisitStack.isEmpty()) {
1153 // start to analyze leaf node
1154 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1155 FlatMethod fm = state.getMethodFlat(md);
1157 Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1158 Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
1160 methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
1162 Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
1163 Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
1165 if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
1166 mapFlatMethodToRead.put(fm, readSet);
1167 mapFlatMethodToOverWrite.put(fm, overWriteSet);
1169 // results for callee changed, so enqueue dependents caller for
1172 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1173 while (depsItr.hasNext()) {
1174 MethodDescriptor methodNext = depsItr.next();
1175 if (!methodDescriptorsToVisitStack.contains(methodNext)
1176 && methodDescriptorToVistSet.contains(methodNext)) {
1177 methodDescriptorsToVisitStack.add(methodNext);
1188 private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1189 Set<NTuple<Descriptor>> overWriteSet) {
1190 if (state.SSJAVADEBUG) {
1191 System.out.println("Definitely written Analyzing: " + fm);
1194 // intraprocedural analysis
1195 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1196 flatNodesToVisit.add(fm);
1198 while (!flatNodesToVisit.isEmpty()) {
1199 FlatNode fn = flatNodesToVisit.iterator().next();
1200 flatNodesToVisit.remove(fn);
1202 Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
1204 for (int i = 0; i < fn.numPrev(); i++) {
1205 FlatNode prevFn = fn.getPrev(i);
1206 Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
1212 methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
1214 Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
1215 if (!curr.equals(writtenSetPrev)) {
1216 mapFlatNodeToWrittenSet.put(fn, curr);
1217 for (int i = 0; i < fn.numNext(); i++) {
1218 FlatNode nn = fn.getNext(i);
1219 flatNodesToVisit.add(nn);
1227 private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
1228 Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
1231 FieldDescriptor fld;
1233 switch (fn.kind()) {
1234 case FKind.FlatMethod: {
1236 // set up initial heap paths for method parameters
1237 FlatMethod fm = (FlatMethod) fn;
1238 for (int i = 0; i < fm.numParameters(); i++) {
1239 TempDescriptor param = fm.getParameter(i);
1240 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1241 heapPath.add(param);
1242 mapHeapPath.put(param, heapPath);
1247 case FKind.FlatOpNode: {
1248 FlatOpNode fon = (FlatOpNode) fn;
1249 // for a normal assign node, need to propagate lhs's heap path to
1251 if (fon.getOp().getOp() == Operation.ASSIGN) {
1252 rhs = fon.getLeft();
1253 lhs = fon.getDest();
1255 NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1256 if (rhsHeapPath != null) {
1257 mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1264 case FKind.FlatFieldNode:
1265 case FKind.FlatElementNode: {
1269 FlatFieldNode ffn = (FlatFieldNode) fn;
1272 fld = ffn.getField();
1275 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1276 if (srcHeapPath != null) {
1277 // if lhs srcHeapPath is null, it means that it is not reachable from
1278 // callee's parameters. so just ignore it
1280 NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1281 readingHeapPath.add(fld);
1282 mapHeapPath.put(lhs, readingHeapPath);
1285 if (fld.getType().isImmutable()) {
1286 // if WT doesnot have hp(x.f), add hp(x.f) to READ
1287 if (!writtenSet.contains(readingHeapPath)) {
1288 readSet.add(readingHeapPath);
1292 // need to kill hp(x.f) from WT
1293 writtenSet.remove(readingHeapPath);
1299 case FKind.FlatSetFieldNode:
1300 case FKind.FlatSetElementNode: {
1303 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1304 lhs = fsfn.getDst();
1305 fld = fsfn.getField();
1306 rhs = fsfn.getSrc();
1309 NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1310 if (lhsHeapPath != null) {
1311 // if lhs heap path is null, it means that it is not reachable from
1312 // callee's parameters. so just ignore it
1313 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1314 newHeapPath.add(fld);
1315 mapHeapPath.put(fld, newHeapPath);
1318 // need to add hp(y) to WT
1319 writtenSet.add(newHeapPath);
1325 case FKind.FlatCall: {
1327 FlatCall fc = (FlatCall) fn;
1329 bindHeapPathCallerArgWithCaleeParam(fc);
1331 // add heap path, which is an element of READ_bound set and is not
1333 // element of WT set, to the caller's READ set
1334 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1335 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1336 if (!writtenSet.contains(read)) {
1340 writtenSet.removeAll(calleeUnionBoundReadSet);
1342 // add heap path, which is an element of OVERWRITE_bound set, to the
1344 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1345 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1346 writtenSet.add(write);
1352 case FKind.FlatExit: {
1353 // merge the current written set with OVERWRITE set
1354 merge(overWriteSet, writtenSet);
1362 private void mergeSharedLocationAnaylsis(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
1363 Set<Hashtable<NTuple<Descriptor>, SharedLocState>> inSet) {
1365 if (inSet.size() == 0) {
1369 Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
1370 new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
1372 for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1374 Hashtable<NTuple<Descriptor>, SharedLocState> inTable =
1375 (Hashtable<NTuple<Descriptor>, SharedLocState>) inIterator.next();
1377 Set<NTuple<Descriptor>> keySet = inTable.keySet();
1379 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1380 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1381 SharedLocState inState = inTable.get(hpKey);
1383 SharedLocState currState = curr.get(hpKey);
1384 if (currState == null) {
1385 currState = new SharedLocState();
1386 curr.put(hpKey, currState);
1388 currState.merge(inState);
1390 Set<Location> locSet = inState.getMap().keySet();
1391 for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
1392 Location loc = (Location) iterator2.next();
1393 Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
1394 boolean inFlag = pair.getSecond().booleanValue();
1396 Pair<NTuple<Descriptor>, Location> flagKey =
1397 new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
1398 Boolean current = mapHeapPathLoc2Flag.get(flagKey);
1399 if (current == null) {
1400 current = new Boolean(true);
1402 boolean newInFlag = current.booleanValue() & inFlag;
1403 mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
1410 // merge flag status
1411 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
1412 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
1413 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1414 SharedLocState currState = curr.get(hpKey);
1415 Set<Location> locKeySet = currState.getMap().keySet();
1416 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
1417 Location locKey = (Location) iterator2.next();
1418 Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
1419 boolean currentFlag = pair.getSecond().booleanValue();
1420 Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
1421 if (inFlag != null) {
1422 boolean newFlag = currentFlag | inFlag.booleanValue();
1423 if (currentFlag != newFlag) {
1424 currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
1432 private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
1433 if (curr.isEmpty()) {
1434 // WrittenSet has a special initial value which covers all possible
1436 // For the first time of intersection, we can take all previous set
1439 // otherwise, current set is the intersection of the two sets
1445 // combine two heap path
1446 private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
1447 NTuple<Descriptor> combined = new NTuple<Descriptor>();
1449 for (int i = 0; i < callerIn.size(); i++) {
1450 combined.add(callerIn.get(i));
1453 // the first element of callee's heap path represents parameter
1454 // so we skip the first one since it is already added from caller's heap
1456 for (int i = 1; i < calleeIn.size(); i++) {
1457 combined.add(calleeIn.get(i));
1463 private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
1464 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
1465 Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
1467 Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
1469 Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
1470 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1471 Integer idx = (Integer) iterator.next();
1473 NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
1474 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1476 for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
1477 NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
1478 if (element.startsWith(calleeParam)) {
1479 NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
1480 boundedCalleeSet.add(boundElement);
1486 return boundedCalleeSet;
1490 // Borrowed it from disjoint analysis
1491 private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
1493 Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1495 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1497 Iterator<MethodDescriptor> itr = toSort.iterator();
1498 while (itr.hasNext()) {
1499 MethodDescriptor d = itr.next();
1501 if (!discovered.contains(d)) {
1502 dfsVisit(d, toSort, sorted, discovered);
1509 // While we're doing DFS on call graph, remember
1510 // dependencies for efficient queuing of methods
1511 // during interprocedural analysis:
1513 // a dependent of a method decriptor d for this analysis is:
1514 // 1) a method or task that invokes d
1515 // 2) in the descriptorsToAnalyze set
1516 private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
1517 LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
1521 Iterator itr = callGraph.getCallerSet(md).iterator();
1522 while (itr.hasNext()) {
1523 MethodDescriptor dCaller = (MethodDescriptor) itr.next();
1524 // only consider callers in the original set to analyze
1525 if (!toSort.contains(dCaller)) {
1528 if (!discovered.contains(dCaller)) {
1529 addDependent(md, // callee
1533 dfsVisit(dCaller, toSort, sorted, discovered);
1537 // for leaf-nodes last now!
1541 // a dependent of a method decriptor d for this analysis is:
1542 // 1) a method or task that invokes d
1543 // 2) in the descriptorsToAnalyze set
1544 private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1545 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1547 deps = new HashSet<MethodDescriptor>();
1550 mapDescriptorToSetDependents.put(callee, deps);
1553 private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1554 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1556 deps = new HashSet<MethodDescriptor>();
1557 mapDescriptorToSetDependents.put(callee, deps);
1562 private NTuple<Descriptor> computePath(TempDescriptor td) {
1563 // generate proper path fot input td
1564 // if td is local variable, it just generate one element tuple path
1565 if (mapHeapPath.containsKey(td)) {
1566 return mapHeapPath.get(td);
1568 NTuple<Descriptor> path = new NTuple<Descriptor>();