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());
146 System.out.println("checkSharedLocationResult=" + result);
148 Set<NTuple<Descriptor>> hpKeySet = result.keySet();
149 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
150 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
151 SharedStatus state = result.get(hpKey);
152 Set<Location> locKeySet = state.getLocationSet();
153 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
154 Location locKey = (Location) iterator2.next();
155 if (!state.getFlag(locKey)) {
157 "Some concrete locations of the shared abstract location are not cleared at the same time.");
164 private void sharedLocationAnalysis() {
165 // verify that all concrete locations of shared location are cleared out at
166 // the same time once per the out-most loop
168 computeReadSharedDescriptorSet();
169 System.out.println("Reading Shared Location=" + mapSharedLocation2DescriptorSet);
171 methodDescriptorsToVisitStack.clear();
173 methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
175 // analyze scheduled methods until there are no more to visit
176 while (!methodDescriptorsToVisitStack.isEmpty()) {
177 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
179 ClearingSummary completeSummary =
180 sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
182 ClearingSummary prevCompleteSummary = mapMethodDescriptorToCompleteClearingSummary.get(md);
184 if (!completeSummary.equals(prevCompleteSummary)) {
186 mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
188 // results for callee changed, so enqueue dependents caller for
190 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
191 while (depsItr.hasNext()) {
192 MethodDescriptor methodNext = depsItr.next();
193 if (!methodDescriptorsToVisitStack.contains(methodNext)) {
194 methodDescriptorsToVisitStack.add(methodNext);
198 // if there is set of callee to be analyzed,
199 // add this set into the top of stack
200 Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
201 while (calleeIter.hasNext()) {
202 MethodDescriptor mdNext = calleeIter.next();
203 if (!methodDescriptorsToVisitStack.contains(mdNext)) {
204 methodDescriptorsToVisitStack.add(mdNext);
207 calleesToEnqueue.clear();
215 private ClearingSummary sharedLocation_analyzeMethod(MethodDescriptor md,
216 boolean onlyVisitSSJavaLoop) {
218 if (state.SSJAVADEBUG) {
219 System.out.println("Definitely written for shared locations Analyzing: " + md + " "
220 + onlyVisitSSJavaLoop);
223 FlatMethod fm = state.getMethodFlat(md);
225 // intraprocedural analysis
226 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
228 // start a new mapping of partial results for each flat node
229 mapFlatNodeToClearingSummary = new Hashtable<FlatNode, ClearingSummary>();
231 if (onlyVisitSSJavaLoop) {
232 flatNodesToVisit.add(ssjavaLoopEntrance);
234 flatNodesToVisit.add(fm);
237 Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
239 while (!flatNodesToVisit.isEmpty()) {
240 FlatNode fn = flatNodesToVisit.iterator().next();
241 flatNodesToVisit.remove(fn);
243 ClearingSummary curr = new ClearingSummary();
245 Set<ClearingSummary> prevSet = new HashSet<ClearingSummary>();
246 for (int i = 0; i < fn.numPrev(); i++) {
247 FlatNode prevFn = fn.getPrev(i);
248 ClearingSummary in = mapFlatNodeToClearingSummary.get(prevFn);
253 mergeSharedLocationAnaylsis(curr, prevSet);
255 sharedLocation_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
256 ClearingSummary clearingPrev = mapFlatNodeToClearingSummary.get(fn);
258 if (!curr.equals(clearingPrev)) {
259 mapFlatNodeToClearingSummary.put(fn, curr);
261 for (int i = 0; i < fn.numNext(); i++) {
262 FlatNode nn = fn.getNext(i);
264 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
265 flatNodesToVisit.add(nn);
273 ClearingSummary completeSummary = new ClearingSummary();
274 Set<ClearingSummary> summarySet = new HashSet<ClearingSummary>();
276 if (onlyVisitSSJavaLoop) {
277 // when analyzing ssjava loop,
278 // complete summary is merging of all previous nodes of ssjava loop
280 for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
281 ClearingSummary frnSummary =
282 mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
283 if (frnSummary != null) {
284 summarySet.add(frnSummary);
288 // merging all exit node summary into the complete summary
289 if (!returnNodeSet.isEmpty()) {
290 for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
291 FlatNode frn = (FlatNode) iterator.next();
292 ClearingSummary frnSummary = mapFlatNodeToClearingSummary.get(frn);
293 summarySet.add(frnSummary);
297 mergeSharedLocationAnaylsis(completeSummary, summarySet);
298 return completeSummary;
301 private void sharedLocation_nodeActions(MethodDescriptor caller, FlatNode fn,
302 ClearingSummary curr, Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
309 case FKind.FlatMethod: {
310 FlatMethod fm = (FlatMethod) fn;
312 ClearingSummary summaryFromCaller =
313 mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
315 Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
316 inSet.add(summaryFromCaller);
317 mergeSharedLocationAnaylsis(curr, inSet);
322 case FKind.FlatOpNode: {
323 FlatOpNode fon = (FlatOpNode) fn;
327 if (fon.getOp().getOp() == Operation.ASSIGN) {
328 if (rhs.getType().isImmutable() && isSSJavaLoop) {
329 // in ssjavaloop, we need to take care about reading local variables!
330 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
331 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
332 rhsHeapPath.add(LOCAL);
333 lhsHeapPath.add(LOCAL);
334 if (!lhs.getSymbol().startsWith("neverused")) {
335 readLocation(curr, rhsHeapPath, rhs);
336 writeLocation(curr, lhsHeapPath, lhs);
344 case FKind.FlatFieldNode:
345 case FKind.FlatElementNode: {
347 FlatFieldNode ffn = (FlatFieldNode) fn;
350 fld = ffn.getField();
353 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
354 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
356 if (fld.getType().isImmutable()) {
357 readLocation(curr, fldHeapPath, fld);
363 case FKind.FlatSetFieldNode:
364 case FKind.FlatSetElementNode: {
366 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
368 fld = fsfn.getField();
371 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
372 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
373 if (fld.getType().isImmutable()) {
374 writeLocation(curr, fldHeapPath, fld);
376 // updates reference field case:
377 // 2. if there exists a tuple t in sharing summary that starts with
378 // hp(x) then, set flag of tuple t to 'true'
379 fldHeapPath.add(fld);
380 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
381 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
382 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
383 if (hpKey.startsWith(fldHeapPath)) {
384 curr.get(hpKey).updateFlag(true);
392 case FKind.FlatCall: {
394 FlatCall fc = (FlatCall) fn;
396 // find out the set of callees
397 MethodDescriptor mdCallee = fc.getMethod();
398 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
399 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
400 TypeDescriptor typeDesc = fc.getThis().getType();
401 setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
403 possibleCalleeCompleteSummarySetToCaller.clear();
405 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
406 MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
407 FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
409 addDependent(mdPossibleCallee, // callee
412 calleesToEnqueue.add(mdPossibleCallee);
414 // updates possible callee's initial summary using caller's current
416 ClearingSummary prevCalleeInitSummary =
417 mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
419 ClearingSummary calleeInitSummary =
420 bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
422 // if changes, update the init summary
423 // and reschedule the callee for analysis
424 if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
426 if (!methodDescriptorsToVisitStack.contains(mdPossibleCallee)) {
427 methodDescriptorsToVisitStack.add(mdPossibleCallee);
429 mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
434 // contribute callee's writing effects to the caller
435 mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
440 case FKind.FlatReturnNode: {
441 returnNodeSet.add(fn);
449 private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc,
450 FlatMethod calleeFlatMethod, ClearingSummary curr) {
452 ClearingSummary boundSet = new ClearingSummary();
454 // create mapping from arg idx to its heap paths
455 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
456 new Hashtable<Integer, NTuple<Descriptor>>();
458 // arg idx is starting from 'this' arg
459 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
460 if (thisHeapPath == null) {
461 // method is called without creating new flat node representing 'this'
462 thisHeapPath = new NTuple<Descriptor>();
463 thisHeapPath.add(fc.getThis());
466 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
468 for (int i = 0; i < fc.numArgs(); i++) {
469 TempDescriptor arg = fc.getArg(i);
470 NTuple<Descriptor> argHeapPath = computePath(arg);
471 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
474 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
475 new Hashtable<Integer, TempDescriptor>();
476 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
477 TempDescriptor param = calleeFlatMethod.getParameter(i);
478 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
481 // binding caller's writing effects to callee's params
482 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
483 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
484 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
486 // iterate over caller's writing effect set
487 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
488 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
489 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
490 // current element is reachable caller's arg
491 // so need to bind it to the caller's side and add it to the callee's
493 if (hpKey.startsWith(argHeapPath)) {
494 NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
495 boundSet.put(boundHeapPath, curr.get(hpKey).clone());
502 // contribute callee's complete summary into the caller's current summary
503 ClearingSummary calleeCompleteSummary =
504 mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
506 if (calleeCompleteSummary != null) {
507 ClearingSummary boundCalleeEfffects = new ClearingSummary();
508 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
509 NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
510 TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
512 // iterate over callee's writing effect set
513 Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
514 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
515 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
516 // current element is reachable caller's arg
517 // so need to bind it to the caller's side and add it to the callee's
519 if (hpKey.startsWith(calleeParamHeapPath)) {
521 NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
523 boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
529 possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
535 private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
537 // replace the head of heap path with caller's arg path
538 // for example, heap path 'param.a.b' in callee's side will be replaced with
539 // (corresponding arg heap path).a.b for caller's side
541 NTuple<Descriptor> bound = new NTuple<Descriptor>();
543 for (int i = 0; i < argHeapPath.size(); i++) {
544 bound.add(argHeapPath.get(i));
547 for (int i = 1; i < hpKey.size(); i++) {
548 bound.add(hpKey.get(i));
554 private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
555 NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
556 // replace the head of caller's heap path with callee's param heap path
558 NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
559 boundHeapPath.add(calleeParamHeapPath);
561 for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
562 boundHeapPath.add(effectHeapPath.get(i));
565 return boundHeapPath;
568 private void computeReadSharedDescriptorSet() {
569 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
570 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
572 for (Iterator iterator = methodDescriptorsToAnalyze.iterator(); iterator.hasNext();) {
573 MethodDescriptor md = (MethodDescriptor) iterator.next();
574 FlatMethod fm = state.getMethodFlat(md);
575 computeReadSharedDescriptorSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
580 private void computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm,
581 boolean onlyVisitSSJavaLoop) {
583 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
584 Set<FlatNode> visited = new HashSet<FlatNode>();
586 if (onlyVisitSSJavaLoop) {
587 flatNodesToVisit.add(ssjavaLoopEntrance);
589 flatNodesToVisit.add(fm);
592 while (!flatNodesToVisit.isEmpty()) {
593 FlatNode fn = flatNodesToVisit.iterator().next();
594 flatNodesToVisit.remove(fn);
597 computeReadSharedDescriptorSet_nodeActions(fn, onlyVisitSSJavaLoop);
599 for (int i = 0; i < fn.numNext(); i++) {
600 FlatNode nn = fn.getNext(i);
601 if (!visited.contains(nn)) {
602 if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
603 flatNodesToVisit.add(nn);
612 private void computeReadSharedDescriptorSet_nodeActions(FlatNode fn, boolean isSSJavaLoop) {
619 case FKind.FlatOpNode: {
620 FlatOpNode fon = (FlatOpNode) fn;
624 if (fon.getOp().getOp() == Operation.ASSIGN) {
625 if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) {
626 // in ssjavaloop, we need to take care about reading local variables!
627 NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
628 NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
629 rhsHeapPath.add(LOCAL);
630 addReadDescriptor(rhsHeapPath, rhs);
637 case FKind.FlatFieldNode:
638 case FKind.FlatElementNode: {
640 FlatFieldNode ffn = (FlatFieldNode) fn;
643 fld = ffn.getField();
646 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
647 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
648 // fldHeapPath.add(fld);
650 if (fld.getType().isImmutable()) {
651 addReadDescriptor(fldHeapPath, fld);
654 // propagate rhs's heap path to the lhs
655 mapHeapPath.put(lhs, fldHeapPath);
660 case FKind.FlatSetFieldNode:
661 case FKind.FlatSetElementNode: {
663 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
665 fld = fsfn.getField();
668 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
669 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
670 // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
678 private boolean hasReadingEffectOnSharedLocation(NTuple<Descriptor> hp, Location loc, Descriptor d) {
679 if (!mapSharedLocation2DescriptorSet.containsKey(loc)) {
682 return mapSharedLocation2DescriptorSet.get(loc).contains(d);
686 private void addReadDescriptor(NTuple<Descriptor> hp, Descriptor d) {
688 Location loc = getLocation(d);
690 if (loc != null && ssjava.isSharedLocation(loc)) {
692 Set<Descriptor> set = mapSharedLocation2DescriptorSet.get(loc);
694 set = new HashSet<Descriptor>();
695 mapSharedLocation2DescriptorSet.put(loc, set);
702 private Location getLocation(Descriptor d) {
704 if (d instanceof FieldDescriptor) {
705 return (Location) ((FieldDescriptor) d).getType().getExtension();
707 assert d instanceof TempDescriptor;
708 CompositeLocation comp = (CompositeLocation) ((TempDescriptor) d).getType().getExtension();
712 return comp.get(comp.getSize() - 1);
718 private void writeLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
719 Location loc = getLocation(d);
720 if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
722 // 1. add field x to the clearing set
723 SharedStatus state = getState(curr, hp);
724 state.addVar(loc, d);
726 // 3. if the set v contains all of variables belonging to the shared
727 // location, set flag to true
728 Set<Descriptor> sharedVarSet = mapSharedLocation2DescriptorSet.get(loc);
729 if (state.getVarSet(loc).containsAll(sharedVarSet)) {
730 state.updateFlag(loc, true);
735 private void readLocation(ClearingSummary curr, 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 SharedStatus state = getState(curr, hp);
740 state.removeVar(loc, d);
744 private SharedStatus getState(ClearingSummary curr, NTuple<Descriptor> hp) {
745 SharedStatus state = curr.get(hp);
747 state = new SharedStatus();
753 private void writtenAnalyis() {
754 // perform second stage analysis: intraprocedural analysis ensure that
756 // variables are definitely written in-between the same read
758 // First, identify ssjava loop entrace
759 FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
760 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
761 flatNodesToVisit.add(fm);
763 LoopFinder loopFinder = new LoopFinder(fm);
765 while (!flatNodesToVisit.isEmpty()) {
766 FlatNode fn = flatNodesToVisit.iterator().next();
767 flatNodesToVisit.remove(fn);
769 String label = (String) state.fn2labelMap.get(fn);
772 if (label.equals(ssjava.SSJAVA)) {
773 ssjavaLoopEntrance = fn;
778 for (int i = 0; i < fn.numNext(); i++) {
779 FlatNode nn = fn.getNext(i);
780 flatNodesToVisit.add(nn);
784 assert ssjavaLoopEntrance != null;
786 System.out.println("ssjavaLoopEntrance=" + ssjavaLoopEntrance);
788 // assume that ssjava loop is top-level loop in method, not nested loop
789 Set nestedLoop = loopFinder.nestedLoops();
790 for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
791 LoopFinder lf = (LoopFinder) loopIter.next();
792 System.out.println("lf=" + lf.loopEntrances());
793 System.out.println("elements=" + lf.loopIncElements());
794 if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
799 assert ssjavaLoop != null;
801 writtenAnalysis_analyzeLoop();
805 private void writtenAnalysis_analyzeLoop() {
807 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
808 flatNodesToVisit.add(ssjavaLoopEntrance);
810 loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
812 while (!flatNodesToVisit.isEmpty()) {
813 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
814 flatNodesToVisit.remove(fn);
816 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
817 definitelyWrittenResults.get(fn);
819 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
820 new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
821 for (int i = 0; i < fn.numPrev(); i++) {
822 FlatNode nn = fn.getPrev(i);
823 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
824 definitelyWrittenResults.get(nn);
830 writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
832 // if a new result, schedule forward nodes for analysis
833 if (!curr.equals(prev)) {
834 definitelyWrittenResults.put(fn, curr);
836 for (int i = 0; i < fn.numNext(); i++) {
837 FlatNode nn = fn.getNext(i);
838 if (loopIncElements.contains(nn)) {
839 flatNodesToVisit.add(nn);
847 private void writtenAnalysis_nodeAction(FlatNode fn,
848 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
850 if (fn.equals(loopEntrance)) {
851 // it reaches loop entrance: changes all flag to true
852 Set<NTuple<Descriptor>> keySet = curr.keySet();
853 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
854 NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
855 Hashtable<FlatNode, Boolean> pair = curr.get(key);
857 Set<FlatNode> pairKeySet = pair.keySet();
858 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
859 FlatNode pairKey = (FlatNode) iterator2.next();
860 pair.put(pairKey, Boolean.TRUE);
870 case FKind.FlatOpNode: {
871 FlatOpNode fon = (FlatOpNode) fn;
875 NTuple<Descriptor> rhsHeapPath = computePath(rhs);
876 if (!rhs.getType().isImmutable()) {
877 mapHeapPath.put(lhs, rhsHeapPath);
879 if (fon.getOp().getOp() == Operation.ASSIGN) {
881 readValue(fn, rhsHeapPath, curr);
884 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
885 removeHeapPath(curr, lhsHeapPath);
890 case FKind.FlatLiteralNode: {
891 FlatLiteralNode fln = (FlatLiteralNode) fn;
895 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
896 removeHeapPath(curr, lhsHeapPath);
901 case FKind.FlatFieldNode:
902 case FKind.FlatElementNode: {
904 if (fn.kind() == FKind.FlatFieldNode) {
905 FlatFieldNode ffn = (FlatFieldNode) fn;
908 fld = ffn.getField();
910 FlatElementNode fen = (FlatElementNode) fn;
913 TypeDescriptor td = rhs.getType().dereference();
914 fld = getArrayField(td);
917 if(fld.isFinal() && fld.isStatic()){
918 // if field is final and static, no need to check
923 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
924 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
925 fldHeapPath.add(fld);
927 if (fld.getType().isImmutable()) {
928 readValue(fn, fldHeapPath, curr);
931 // propagate rhs's heap path to the lhs
932 mapHeapPath.put(lhs, fldHeapPath);
937 case FKind.FlatSetFieldNode:
938 case FKind.FlatSetElementNode: {
940 if (fn.kind() == FKind.FlatSetFieldNode) {
941 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
943 fld = fsfn.getField();
945 FlatSetElementNode fsen = (FlatSetElementNode) fn;
948 TypeDescriptor td = lhs.getType().dereference();
949 fld = getArrayField(td);
953 NTuple<Descriptor> lhsHeapPath = computePath(lhs);
954 NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
955 fldHeapPath.add(fld);
956 removeHeapPath(curr, fldHeapPath);
961 case FKind.FlatCall: {
962 FlatCall fc = (FlatCall) fn;
963 bindHeapPathCallerArgWithCaleeParam(fc);
965 // add <hp,statement,false> in which hp is an element of
967 // of callee: callee has 'read' requirement!
968 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
969 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
971 Hashtable<FlatNode, Boolean> gen = curr.get(read);
973 gen = new Hashtable<FlatNode, Boolean>();
976 Boolean currentStatus = gen.get(fn);
977 if (currentStatus == null) {
978 gen.put(fn, Boolean.FALSE);
980 checkFlag(currentStatus.booleanValue(), fn, read);
984 // removes <hp,statement,flag> if hp is an element of
986 // set of callee. it means that callee will overwrite it
987 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
988 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
989 removeHeapPath(curr, write);
999 private void readValue(FlatNode fn, NTuple<Descriptor> hp,
1000 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
1001 Hashtable<FlatNode, Boolean> gen = curr.get(hp);
1003 gen = new Hashtable<FlatNode, Boolean>();
1006 Boolean currentStatus = gen.get(fn);
1007 if (currentStatus == null) {
1008 gen.put(fn, Boolean.FALSE);
1010 checkFlag(currentStatus.booleanValue(), fn, hp);
1015 private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1016 NTuple<Descriptor> hp) {
1018 // removes all of heap path that starts with prefix 'hp'
1019 // since any reference overwrite along heap path gives overwriting side
1020 // effects on the value
1022 Set<NTuple<Descriptor>> keySet = curr.keySet();
1023 for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
1024 NTuple<Descriptor> key = iter.next();
1025 if (key.startsWith(hp)) {
1026 curr.put(key, new Hashtable<FlatNode, Boolean>());
1032 private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
1033 // compute all possible callee set
1034 // transform all READ/OVERWRITE set from the any possible
1038 calleeUnionBoundReadSet.clear();
1039 calleeIntersectBoundOverWriteSet.clear();
1041 MethodDescriptor mdCallee = fc.getMethod();
1042 FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1043 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1044 TypeDescriptor typeDesc = fc.getThis().getType();
1045 setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
1047 // create mapping from arg idx to its heap paths
1048 Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1049 new Hashtable<Integer, NTuple<Descriptor>>();
1051 // arg idx is starting from 'this' arg
1052 NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1053 if (thisHeapPath == null) {
1054 // method is called without creating new flat node representing 'this'
1055 thisHeapPath = new NTuple<Descriptor>();
1056 thisHeapPath.add(fc.getThis());
1059 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1061 for (int i = 0; i < fc.numArgs(); i++) {
1062 TempDescriptor arg = fc.getArg(i);
1063 NTuple<Descriptor> argHeapPath = computePath(arg);
1064 mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1067 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1068 MethodDescriptor callee = (MethodDescriptor) iterator.next();
1069 FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1071 // binding caller's args and callee's params
1073 Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
1074 if (calleeReadSet == null) {
1075 calleeReadSet = new HashSet<NTuple<Descriptor>>();
1076 mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
1078 Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
1079 if (calleeOverWriteSet == null) {
1080 calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
1081 mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
1084 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1085 new Hashtable<Integer, TempDescriptor>();
1086 for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1087 TempDescriptor param = calleeFlatMethod.getParameter(i);
1088 mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
1091 Set<NTuple<Descriptor>> calleeBoundReadSet =
1092 bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1093 // union of the current read set and the current callee's
1095 calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1096 Set<NTuple<Descriptor>> calleeBoundWriteSet =
1097 bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1098 // intersection of the current overwrite set and the current
1101 merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
1106 private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1109 "There is a variable, which is reachable through references "
1111 + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1112 + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1117 private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1118 Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
1120 Set<NTuple<Descriptor>> inKeySet = in.keySet();
1121 for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1122 NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1123 Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
1125 Set<FlatNode> pairKeySet = inPair.keySet();
1126 for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1127 FlatNode pairKey = (FlatNode) iterator2.next();
1128 Boolean inFlag = inPair.get(pairKey);
1130 Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
1131 if (currPair == null) {
1132 currPair = new Hashtable<FlatNode, Boolean>();
1133 curr.put(inKey, currPair);
1136 Boolean currFlag = currPair.get(pairKey);
1137 // by default, flag is set by false
1138 if (currFlag == null) {
1139 currFlag = Boolean.FALSE;
1141 currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
1142 currPair.put(pairKey, currFlag);
1149 private void methodReadOverWriteAnalysis() {
1150 // perform method READ/OVERWRITE analysis
1151 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1152 methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1154 sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1156 LinkedList<MethodDescriptor> descriptorListToAnalyze =
1157 (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1159 // no need to analyze method having ssjava loop
1160 methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
1162 // current descriptors to visit in fixed-point interprocedural analysis,
1164 // dependency in the call graph
1165 methodDescriptorsToVisitStack.clear();
1167 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1168 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1170 while (!descriptorListToAnalyze.isEmpty()) {
1171 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1172 methodDescriptorsToVisitStack.add(md);
1175 // analyze scheduled methods until there are no more to visit
1176 while (!methodDescriptorsToVisitStack.isEmpty()) {
1177 // start to analyze leaf node
1178 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1179 FlatMethod fm = state.getMethodFlat(md);
1181 Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1182 Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
1184 methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
1186 Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
1187 Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
1189 if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
1190 mapFlatMethodToRead.put(fm, readSet);
1191 mapFlatMethodToOverWrite.put(fm, overWriteSet);
1193 // results for callee changed, so enqueue dependents caller for
1196 Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1197 while (depsItr.hasNext()) {
1198 MethodDescriptor methodNext = depsItr.next();
1199 if (!methodDescriptorsToVisitStack.contains(methodNext)
1200 && methodDescriptorToVistSet.contains(methodNext)) {
1201 methodDescriptorsToVisitStack.add(methodNext);
1212 private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1213 Set<NTuple<Descriptor>> overWriteSet) {
1214 if (state.SSJAVADEBUG) {
1215 System.out.println("Definitely written Analyzing: " + fm);
1218 // intraprocedural analysis
1219 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1220 flatNodesToVisit.add(fm);
1222 while (!flatNodesToVisit.isEmpty()) {
1223 FlatNode fn = flatNodesToVisit.iterator().next();
1224 flatNodesToVisit.remove(fn);
1226 Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
1228 for (int i = 0; i < fn.numPrev(); i++) {
1229 FlatNode prevFn = fn.getPrev(i);
1230 Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
1236 methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
1238 Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
1239 if (!curr.equals(writtenSetPrev)) {
1240 mapFlatNodeToWrittenSet.put(fn, curr);
1241 for (int i = 0; i < fn.numNext(); i++) {
1242 FlatNode nn = fn.getNext(i);
1243 flatNodesToVisit.add(nn);
1251 private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
1252 Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
1255 FieldDescriptor fld;
1257 switch (fn.kind()) {
1258 case FKind.FlatMethod: {
1260 // set up initial heap paths for method parameters
1261 FlatMethod fm = (FlatMethod) fn;
1262 for (int i = 0; i < fm.numParameters(); i++) {
1263 TempDescriptor param = fm.getParameter(i);
1264 NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1265 heapPath.add(param);
1266 mapHeapPath.put(param, heapPath);
1271 case FKind.FlatOpNode: {
1272 FlatOpNode fon = (FlatOpNode) fn;
1273 // for a normal assign node, need to propagate lhs's heap path to
1275 if (fon.getOp().getOp() == Operation.ASSIGN) {
1276 rhs = fon.getLeft();
1277 lhs = fon.getDest();
1279 NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1280 if (rhsHeapPath != null) {
1281 mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1288 case FKind.FlatElementNode:
1289 case FKind.FlatFieldNode: {
1293 if (fn.kind() == FKind.FlatFieldNode) {
1294 FlatFieldNode ffn = (FlatFieldNode) fn;
1297 fld = ffn.getField();
1299 FlatElementNode fen = (FlatElementNode) fn;
1302 TypeDescriptor td = rhs.getType().dereference();
1303 fld = getArrayField(td);
1306 if(fld.isFinal() && fld.isStatic()){
1307 // if field is final and static, no need to check
1312 NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1313 if (srcHeapPath != null) {
1314 // if lhs srcHeapPath is null, it means that it is not reachable from
1315 // callee's parameters. so just ignore it
1317 NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1318 readingHeapPath.add(fld);
1319 mapHeapPath.put(lhs, readingHeapPath);
1322 if (fld.getType().isImmutable()) {
1323 // if WT doesnot have hp(x.f), add hp(x.f) to READ
1324 if (!writtenSet.contains(readingHeapPath)) {
1325 readSet.add(readingHeapPath);
1329 // need to kill hp(x.f) from WT
1330 writtenSet.remove(readingHeapPath);
1336 case FKind.FlatSetFieldNode:
1337 case FKind.FlatSetElementNode: {
1341 if (fn.kind() == FKind.FlatSetFieldNode) {
1342 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1343 lhs = fsfn.getDst();
1344 fld = fsfn.getField();
1345 rhs = fsfn.getSrc();
1347 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1348 lhs = fsen.getDst();
1349 rhs = fsen.getSrc();
1350 TypeDescriptor td = lhs.getType().dereference();
1351 fld = getArrayField(td);
1355 NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1356 if (lhsHeapPath != null) {
1357 // if lhs heap path is null, it means that it is not reachable from
1358 // callee's parameters. so just ignore it
1359 NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1360 newHeapPath.add(fld);
1361 mapHeapPath.put(fld, newHeapPath);
1364 // need to add hp(y) to WT
1365 writtenSet.add(newHeapPath);
1371 case FKind.FlatCall: {
1373 FlatCall fc = (FlatCall) fn;
1375 bindHeapPathCallerArgWithCaleeParam(fc);
1377 // add heap path, which is an element of READ_bound set and is not
1379 // element of WT set, to the caller's READ set
1380 for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1381 NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1382 if (!writtenSet.contains(read)) {
1386 writtenSet.removeAll(calleeUnionBoundReadSet);
1388 // add heap path, which is an element of OVERWRITE_bound set, to the
1390 for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1391 NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1392 writtenSet.add(write);
1398 case FKind.FlatExit: {
1399 // merge the current written set with OVERWRITE set
1400 merge(overWriteSet, writtenSet);
1408 static public FieldDescriptor getArrayField(TypeDescriptor td) {
1409 FieldDescriptor fd = mapTypeToArrayField.get(td);
1412 new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), td, arrayElementFieldName, null,
1414 mapTypeToArrayField.put(td, fd);
1419 private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
1421 if (inSet.size() == 0) {
1425 Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
1426 new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
1428 for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1430 ClearingSummary inTable = (ClearingSummary) inIterator.next();
1432 Set<NTuple<Descriptor>> keySet = inTable.keySet();
1434 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1435 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1436 SharedStatus inState = inTable.get(hpKey);
1438 SharedStatus currState = curr.get(hpKey);
1439 if (currState == null) {
1440 currState = new SharedStatus();
1441 curr.put(hpKey, currState);
1443 currState.merge(inState);
1445 Set<Location> locSet = inState.getMap().keySet();
1446 for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
1447 Location loc = (Location) iterator2.next();
1448 Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
1449 boolean inFlag = pair.getSecond().booleanValue();
1451 Pair<NTuple<Descriptor>, Location> flagKey =
1452 new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
1453 Boolean current = mapHeapPathLoc2Flag.get(flagKey);
1454 if (current == null) {
1455 current = new Boolean(true);
1457 boolean newInFlag = current.booleanValue() & inFlag;
1458 mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
1465 // merge flag status
1466 Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
1467 for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
1468 NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1469 SharedStatus currState = curr.get(hpKey);
1470 Set<Location> locKeySet = currState.getMap().keySet();
1471 for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
1472 Location locKey = (Location) iterator2.next();
1473 Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
1474 boolean currentFlag = pair.getSecond().booleanValue();
1475 Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
1476 if (inFlag != null) {
1477 boolean newFlag = currentFlag | inFlag.booleanValue();
1478 if (currentFlag != newFlag) {
1479 currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
1487 private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
1488 if (curr.isEmpty()) {
1489 // WrittenSet has a special initial value which covers all possible
1491 // For the first time of intersection, we can take all previous set
1494 // otherwise, current set is the intersection of the two sets
1500 // combine two heap path
1501 private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
1502 NTuple<Descriptor> combined = new NTuple<Descriptor>();
1504 for (int i = 0; i < callerIn.size(); i++) {
1505 combined.add(callerIn.get(i));
1508 // the first element of callee's heap path represents parameter
1509 // so we skip the first one since it is already added from caller's heap
1511 for (int i = 1; i < calleeIn.size(); i++) {
1512 combined.add(calleeIn.get(i));
1518 private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
1519 Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
1520 Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
1522 Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
1524 Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
1525 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1526 Integer idx = (Integer) iterator.next();
1528 NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
1529 TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1531 for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
1532 NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
1533 if (element.startsWith(calleeParam)) {
1534 NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
1535 boundedCalleeSet.add(boundElement);
1541 return boundedCalleeSet;
1545 // Borrowed it from disjoint analysis
1546 private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
1548 Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1550 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1552 Iterator<MethodDescriptor> itr = toSort.iterator();
1553 while (itr.hasNext()) {
1554 MethodDescriptor d = itr.next();
1556 if (!discovered.contains(d)) {
1557 dfsVisit(d, toSort, sorted, discovered);
1564 // While we're doing DFS on call graph, remember
1565 // dependencies for efficient queuing of methods
1566 // during interprocedural analysis:
1568 // a dependent of a method decriptor d for this analysis is:
1569 // 1) a method or task that invokes d
1570 // 2) in the descriptorsToAnalyze set
1571 private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
1572 LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
1576 Iterator itr = callGraph.getCallerSet(md).iterator();
1577 while (itr.hasNext()) {
1578 MethodDescriptor dCaller = (MethodDescriptor) itr.next();
1579 // only consider callers in the original set to analyze
1580 if (!toSort.contains(dCaller)) {
1583 if (!discovered.contains(dCaller)) {
1584 addDependent(md, // callee
1588 dfsVisit(dCaller, toSort, sorted, discovered);
1592 // for leaf-nodes last now!
1596 // a dependent of a method decriptor d for this analysis is:
1597 // 1) a method or task that invokes d
1598 // 2) in the descriptorsToAnalyze set
1599 private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1600 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1602 deps = new HashSet<MethodDescriptor>();
1605 mapDescriptorToSetDependents.put(callee, deps);
1608 private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1609 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1611 deps = new HashSet<MethodDescriptor>();
1612 mapDescriptorToSetDependents.put(callee, deps);
1617 private NTuple<Descriptor> computePath(TempDescriptor td) {
1618 // generate proper path fot input td
1619 // if td is local variable, it just generate one element tuple path
1620 if (mapHeapPath.containsKey(td)) {
1621 return mapHeapPath.get(td);
1623 NTuple<Descriptor> path = new NTuple<Descriptor>();