1 package Analysis.SSJava;
3 import java.io.BufferedWriter;
4 import java.io.FileWriter;
5 import java.io.IOException;
6 import java.util.ArrayList;
7 import java.util.Collections;
8 import java.util.Comparator;
9 import java.util.HashMap;
10 import java.util.HashSet;
11 import java.util.Hashtable;
12 import java.util.Iterator;
13 import java.util.LinkedList;
14 import java.util.List;
17 import java.util.StringTokenizer;
18 import java.util.Vector;
20 import Analysis.CallGraph.CallGraph;
21 import Analysis.Loops.GlobalFieldType;
22 import Analysis.Loops.LoopOptimize;
23 import Analysis.Loops.LoopTerminate;
24 import IR.AnnotationDescriptor;
25 import IR.ClassDescriptor;
27 import IR.FieldDescriptor;
28 import IR.MethodDescriptor;
29 import IR.NameDescriptor;
31 import IR.SymbolTable;
33 import IR.Flat.BuildFlat;
34 import IR.Flat.FlatMethod;
35 import IR.Flat.FlatNode;
38 public class SSJavaAnalysis {
40 public static final String SSJAVA = "SSJAVA";
41 public static final String LATTICE = "LATTICE";
42 public static final String METHODDEFAULT = "METHODDEFAULT";
43 public static final String THISLOC = "THISLOC";
44 public static final String GLOBALLOC = "GLOBALLOC";
45 public static final String RETURNLOC = "RETURNLOC";
46 public static final String PCLOC = "PCLOC";
47 public static final String LOC = "LOC";
48 public static final String DELTA = "DELTA";
49 public static final String TERMINATE = "TERMINATE";
50 public static final String DELEGATE = "DELEGATE";
51 public static final String DELEGATETHIS = "DELEGATETHIS";
52 public static final String TRUST = "TRUST";
54 public static final String TOP = "_top_";
55 public static final String BOTTOM = "_bottom_";
59 FlowDownCheck flowDownChecker;
60 MethodAnnotationCheck methodAnnotationChecker;
63 // set containing method requires to be annoated
64 Set<MethodDescriptor> annotationRequireSet;
66 // class -> field lattice
67 Hashtable<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
69 // class -> default local variable lattice
70 Hashtable<ClassDescriptor, MethodLattice<String>> cd2methodDefault;
72 // method -> local variable lattice
73 Hashtable<MethodDescriptor, MethodLattice<String>> md2lattice;
75 // method set that does not want to have loop termination analysis
76 Hashtable<MethodDescriptor, Integer> skipLoopTerminate;
78 // map shared location to its descriptors
79 Hashtable<Location, Set<Descriptor>> mapSharedLocation2DescriptorSet;
81 // set containing a class that has at least one annoated method
82 Set<ClassDescriptor> annotationRequireClassSet;
84 // the set of method descriptor required to check the linear type property
85 Set<MethodDescriptor> linearTypeCheckMethodSet;
87 // the set of method descriptors annotated as "TRUST"
88 Set<MethodDescriptor> trustWorthyMDSet;
90 // method -> the initial program counter location
91 Map<MethodDescriptor, CompositeLocation> md2pcLoc;
93 // points to method containing SSJAVA Loop
94 private MethodDescriptor methodContainingSSJavaLoop;
96 private FlatNode ssjavaLoopEntrance;
98 // keep the field ownership from the linear type checking
99 Hashtable<MethodDescriptor, Set<FieldDescriptor>> mapMethodToOwnedFieldSet;
101 Set<FlatNode> sameHeightWriteFlatNodeSet;
105 LinearTypeCheck checker;
107 // maps a descriptor to its known dependents: namely
108 // methods or tasks that call the descriptor's method
109 // AND are part of this analysis (reachable from main)
110 private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
112 private LinkedList<MethodDescriptor> sortedDescriptors;
114 private Map<Location, Set<Descriptor>> mapSharedLocToDescSet;
116 private Map<Descriptor, SSJavaLattice<String>> mapDescToCompleteLattice;
117 public Map<Descriptor, Integer> mapNumLocsMapManual;
118 public Map<Descriptor, Integer> mapNumPathsMapManual;
120 public SSJavaAnalysis(State state, TypeUtil tu, BuildFlat bf, CallGraph callgraph) {
123 this.callgraph = callgraph;
124 this.cd2lattice = new Hashtable<ClassDescriptor, SSJavaLattice<String>>();
125 this.cd2methodDefault = new Hashtable<ClassDescriptor, MethodLattice<String>>();
126 this.md2lattice = new Hashtable<MethodDescriptor, MethodLattice<String>>();
127 this.annotationRequireSet = new HashSet<MethodDescriptor>();
128 this.annotationRequireClassSet = new HashSet<ClassDescriptor>();
129 this.skipLoopTerminate = new Hashtable<MethodDescriptor, Integer>();
130 this.mapSharedLocation2DescriptorSet = new Hashtable<Location, Set<Descriptor>>();
131 this.linearTypeCheckMethodSet = new HashSet<MethodDescriptor>();
133 this.trustWorthyMDSet = new HashSet<MethodDescriptor>();
134 this.mapMethodToOwnedFieldSet = new Hashtable<MethodDescriptor, Set<FieldDescriptor>>();
135 this.sameHeightWriteFlatNodeSet = new HashSet<FlatNode>();
136 this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
137 this.sortedDescriptors = new LinkedList<MethodDescriptor>();
138 this.md2pcLoc = new HashMap<MethodDescriptor, CompositeLocation>();
139 this.mapSharedLocToDescSet = new HashMap<Location, Set<Descriptor>>();
140 this.mapDescToCompleteLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
141 this.mapNumLocsMapManual = new HashMap<Descriptor, Integer>();
142 this.mapNumPathsMapManual = new HashMap<Descriptor, Integer>();
145 public void doCheck() {
146 doMethodAnnotationCheck();
148 if (state.SSJAVA && !state.SSJAVAINFER) {
150 computeLinearTypeCheckMethodSet();
154 if (state.SSJAVADEBUG) {
155 // debug_printAnnotationRequiredSet();
157 if (state.SSJAVAINFER) {
161 parseLocationAnnotation();
162 debug_countNumLocations();
165 doDefinitelyWrittenCheck();
169 for (Iterator iterator = annotationRequireSet.iterator(); iterator.hasNext();) {
170 MethodDescriptor md = (MethodDescriptor) iterator.next();
171 MethodLattice<String> locOrder = getMethodLattice(md);
172 writeLatticeDotFile(md.getClassDesc(), md, getMethodLattice(md));
173 System.out.println("~~~\t" + md.getClassDesc() + "_" + md + "\t"
174 + locOrder.getKeySet().size());
179 private void debug_countNumLocations() {
181 BuildLattice buildLattice = new BuildLattice();
183 for (Iterator iterator = cd2lattice.keySet().iterator(); iterator.hasNext();) {
184 ClassDescriptor cd = (ClassDescriptor) iterator.next();
185 SSJavaLattice<String> lattice = cd2lattice.get(cd).clone();
186 SSJavaLattice<String> completeLattice = debug_buildCompleteLattice(buildLattice, cd, lattice);
187 mapDescToCompleteLattice.put(cd, completeLattice);
188 writeLatticeDotFile(cd, null, completeLattice);
191 for (Iterator iterator = md2lattice.keySet().iterator(); iterator.hasNext();) {
192 MethodDescriptor md = (MethodDescriptor) iterator.next();
193 SSJavaLattice<String> lattice = md2lattice.get(md).clone();
194 SSJavaLattice<String> completeLattice = debug_buildCompleteLattice(buildLattice, md, lattice);
195 mapDescToCompleteLattice.put(md, completeLattice);
196 writeLatticeDotFile(md.getClassDesc(), md, completeLattice);
199 for (Iterator iterator = annotationRequireSet.iterator(); iterator.hasNext();) {
200 MethodDescriptor md = (MethodDescriptor) iterator.next();
201 SSJavaLattice<String> lattice = getMethodLattice(md).clone();
202 if (!mapDescToCompleteLattice.containsKey(md)) {
203 System.out.println("@NOT FOUND!");
204 SSJavaLattice<String> completeLattice =
205 debug_buildCompleteLattice(buildLattice, md, lattice);
206 mapDescToCompleteLattice.put(md, completeLattice);
207 writeLatticeDotFile(md.getClassDesc(), md, completeLattice);
211 writeNumLocsPathsCSVFile();
215 public SSJavaLattice<String> debug_buildCompleteLattice(BuildLattice buildLattice,
216 Descriptor desc, SSJavaLattice<String> lattice) {
218 // First, create a hierarchy graph
219 HierarchyGraph hierarchyGraph = new HierarchyGraph();
220 Set<String> keySet = lattice.getKeySet();
222 Map<String, Descriptor> mapLocNameToDesc = new HashMap<String, Descriptor>();
224 for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
225 String higher = (String) iterator2.next();
226 Set<String> lowerSet = lattice.get(higher);
227 if (!mapLocNameToDesc.containsKey(higher)) {
228 mapLocNameToDesc.put(higher, new NameDescriptor(higher));
231 Descriptor higherDesc = mapLocNameToDesc.get(higher);
233 for (Iterator iterator3 = lowerSet.iterator(); iterator3.hasNext();) {
234 String lower = (String) iterator3.next();
235 if (!mapLocNameToDesc.containsKey(lower)) {
236 mapLocNameToDesc.put(lower, new NameDescriptor(lower));
238 Descriptor lowerDesc = mapLocNameToDesc.get(lower);
239 hierarchyGraph.addEdge(higherDesc, lowerDesc);
243 BasisSet basisSet = hierarchyGraph.computeBasisSet(new HashSet<HNode>());
245 SSJavaLattice<String> completeLattice = buildLattice.buildLattice(hierarchyGraph);
247 int numLocs = completeLattice.getKeySet().size() + 1;
248 LocationInference.numLocationsSInfer += numLocs;
249 mapNumLocsMapManual.put(desc, new Integer(numLocs));
251 System.out.println(desc + "::" + "lattice=" + lattice.getKeySet().size() + " complete="
254 int numPaths = completeLattice.countPaths();
255 LocationInference.numLocationsSInfer += numPaths;
256 mapNumPathsMapManual.put(desc, new Integer(numPaths));
258 return completeLattice;
261 public void writeNumLocsPathsCSVFile() {
264 BufferedWriter bw = new BufferedWriter(new FileWriter("manualnumbers.csv"));
266 Set<Descriptor> keySet = mapNumLocsMapManual.keySet();
267 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
268 Descriptor desc = (Descriptor) iterator.next();
269 int numLocs = mapNumLocsMapManual.get(desc);
270 int numPaths = mapNumPathsMapManual.get(desc);
271 bw.write(desc.getSymbol().replaceAll("[,]", "") + "," + numLocs + "," + numPaths + "\n");
275 } catch (IOException e) {
276 // TODO Auto-generated catch block
283 // perform topological sort over the set of methods accessed by the main
285 Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
286 methodDescriptorsToAnalyze.addAll(getAnnotationRequireSet());
287 sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
290 public LinkedList<MethodDescriptor> getSortedDescriptors() {
291 return (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
294 public void addSharedDesc(Location loc, Descriptor fd) {
295 if (!mapSharedLocToDescSet.containsKey(loc)) {
296 mapSharedLocToDescSet.put(loc, new HashSet<Descriptor>());
298 mapSharedLocToDescSet.get(loc).add(fd);
301 public Set<Descriptor> getSharedDescSet(Location loc) {
302 return mapSharedLocToDescSet.get(loc);
305 private void inference() {
306 LocationInference inferEngine = new LocationInference(this, state, tu);
307 inferEngine.inference();
310 private void doLoopCheck() {
311 GlobalFieldType gft = new GlobalFieldType(callgraph, state, tu.getMain());
312 LoopOptimize lo = new LoopOptimize(gft, tu);
314 SymbolTable classtable = state.getClassSymbolTable();
316 List<ClassDescriptor> toanalyzeList = new ArrayList<ClassDescriptor>();
317 List<MethodDescriptor> toanalyzeMethodList = new ArrayList<MethodDescriptor>();
319 toanalyzeList.addAll(classtable.getValueSet());
320 Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
321 public int compare(ClassDescriptor o1, ClassDescriptor o2) {
322 return o1.getClassName().compareTo(o2.getClassName());
326 for (int i = 0; i < toanalyzeList.size(); i++) {
327 ClassDescriptor cd = toanalyzeList.get(i);
329 SymbolTable methodtable = cd.getMethodTable();
330 toanalyzeMethodList.clear();
331 toanalyzeMethodList.addAll(methodtable.getValueSet());
332 Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
333 public int compare(MethodDescriptor o1, MethodDescriptor o2) {
334 return o1.getSymbol().compareTo(o2.getSymbol());
338 for (int mdIdx = 0; mdIdx < toanalyzeMethodList.size(); mdIdx++) {
339 MethodDescriptor md = toanalyzeMethodList.get(mdIdx);
340 if (needTobeAnnotated(md)) {
341 lo.analyze(state.getMethodFlat(md));
342 doLoopTerminationCheck(lo, state.getMethodFlat(md));
350 public void addTrustMethod(MethodDescriptor md) {
351 trustWorthyMDSet.add(md);
354 public boolean isTrustMethod(MethodDescriptor md) {
355 return trustWorthyMDSet.contains(md);
358 private void computeLinearTypeCheckMethodSet() {
360 Set<MethodDescriptor> allCalledSet = callgraph.getMethodCalls(tu.getMain());
361 linearTypeCheckMethodSet.addAll(allCalledSet);
363 Set<MethodDescriptor> trustedSet = new HashSet<MethodDescriptor>();
365 for (Iterator iterator = trustWorthyMDSet.iterator(); iterator.hasNext();) {
366 MethodDescriptor trustMethod = (MethodDescriptor) iterator.next();
367 Set<MethodDescriptor> calledFromTrustMethodSet = callgraph.getMethodCalls(trustMethod);
368 trustedSet.add(trustMethod);
369 trustedSet.addAll(calledFromTrustMethodSet);
372 linearTypeCheckMethodSet.removeAll(trustedSet);
374 // if a method is called only by trusted method, no need to check linear
375 // type & flow down rule
376 for (Iterator iterator = trustedSet.iterator(); iterator.hasNext();) {
377 MethodDescriptor md = (MethodDescriptor) iterator.next();
378 Set<MethodDescriptor> callerSet = callgraph.getCallerSet(md);
379 if (!trustedSet.containsAll(callerSet) && !trustWorthyMDSet.contains(md)) {
380 linearTypeCheckMethodSet.add(md);
384 linearTypeCheckMethodSet.addAll(sortedDescriptors);
388 private void doLinearTypeCheck() {
389 LinearTypeCheck checker = new LinearTypeCheck(this, state);
390 checker.linearTypeCheck();
393 public void debug_printAnnotationRequiredSet() {
394 System.out.println("SSJAVA: SSJava is checking the following methods:");
395 for (Iterator<MethodDescriptor> iterator = annotationRequireSet.iterator(); iterator.hasNext();) {
396 MethodDescriptor md = iterator.next();
397 System.out.println(md);
399 System.out.println();
402 private void doMethodAnnotationCheck() {
403 methodAnnotationChecker = new MethodAnnotationCheck(this, state, tu);
404 methodAnnotationChecker.methodAnnoatationCheck();
405 methodAnnotationChecker.methodAnnoataionInheritanceCheck();
406 if (state.SSJAVAINFER) {
407 annotationRequireClassSet.add(methodContainingSSJavaLoop.getClassDesc());
408 annotationRequireSet.add(methodContainingSSJavaLoop);
410 state.setAnnotationRequireSet(annotationRequireSet);
413 public void doFlowDownCheck() {
414 flowDownChecker = new FlowDownCheck(this, state);
415 flowDownChecker.flowDownCheck();
418 public void doDefinitelyWrittenCheck() {
419 DefinitelyWrittenCheck checker = new DefinitelyWrittenCheck(this, state);
420 checker.definitelyWrittenCheck();
423 private void parseLocationAnnotation() {
424 Iterator it = state.getClassSymbolTable().getDescriptorsIterator();
425 while (it.hasNext()) {
426 ClassDescriptor cd = (ClassDescriptor) it.next();
427 // parsing location hierarchy declaration for the class
428 Vector<AnnotationDescriptor> classAnnotations = cd.getModifier().getAnnotations();
429 for (int i = 0; i < classAnnotations.size(); i++) {
430 AnnotationDescriptor an = classAnnotations.elementAt(i);
431 String marker = an.getMarker();
432 if (marker.equals(LATTICE)) {
433 SSJavaLattice<String> locOrder =
434 new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
435 cd2lattice.put(cd, locOrder);
436 parseClassLatticeDefinition(cd, an.getValue(), locOrder);
438 if (state.SSJAVADEBUG) {
439 // generate lattice dot file
440 writeLatticeDotFile(cd, null, locOrder);
441 System.out.println("~~~\t" + cd + "\t" + locOrder.getKeySet().size());
444 } else if (marker.equals(METHODDEFAULT)) {
445 MethodLattice<String> locOrder =
446 new MethodLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
447 cd2methodDefault.put(cd, locOrder);
448 parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder);
449 // writeLatticeDotFile(cd, null, locOrder, "METHOD_DEFAULT");
453 for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
454 MethodDescriptor md = (MethodDescriptor) method_it.next();
455 // parsing location hierarchy declaration for the method
457 if (needTobeAnnotated(md)) {
458 Vector<AnnotationDescriptor> methodAnnotations = md.getModifiers().getAnnotations();
459 if (methodAnnotations != null) {
460 for (int i = 0; i < methodAnnotations.size(); i++) {
461 AnnotationDescriptor an = methodAnnotations.elementAt(i);
462 if (an.getMarker().equals(LATTICE)) {
463 // developer explicitly defines method lattice
464 MethodLattice<String> locOrder =
465 new MethodLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
466 md2lattice.put(md, locOrder);
467 System.out.println("parsing method lattice=" + md);
468 parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder);
469 writeLatticeDotFile(cd, md, locOrder, "");
470 } else if (an.getMarker().equals(TERMINATE)) {
471 // developer explicitly wants to skip loop termination analysis
472 String value = an.getValue();
473 int maxIteration = 0;
475 maxIteration = Integer.parseInt(value);
477 skipLoopTerminate.put(md, new Integer(maxIteration));
488 public <T> void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
489 SSJavaLattice<T> locOrder) {
490 writeLatticeDotFile(cd, md, locOrder, "");
494 public <T> void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
495 SSJavaLattice<T> locOrder, String nameSuffix) {
497 String fileName = "lattice_";
500 cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", "");
502 fileName += cd.getSymbol().replaceAll("[\\W_]", "");
505 fileName += nameSuffix;
507 Set<Pair<T, T>> pairSet = locOrder.getOrderingPairSet();
509 if (pairSet.size() > 0) {
511 BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
513 bw.write("digraph " + fileName + " {\n");
515 for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
516 // pair is in the form of <higher, lower>
517 Pair<T, T> pair = (Pair<T, T>) iterator.next();
519 T highLocId = pair.getFirst();
520 String highLocStr, lowLocStr;
521 if (locOrder.isSharedLoc(highLocId)) {
522 highLocStr = "\"" + highLocId + "*\"";
524 highLocStr = highLocId.toString();
526 T lowLocId = pair.getSecond();
527 if (locOrder.isSharedLoc(lowLocId)) {
528 lowLocStr = "\"" + lowLocId + "*\"";
530 lowLocStr = lowLocId.toString();
532 bw.write(highLocStr + " -> " + lowLocStr + ";\n");
537 } catch (IOException e) {
545 private void parseMethodDefaultLatticeDefinition(ClassDescriptor cd, String value,
546 MethodLattice<String> locOrder) {
548 value = value.replaceAll(" ", ""); // remove all blank spaces
550 StringTokenizer tokenizer = new StringTokenizer(value, ",");
552 while (tokenizer.hasMoreTokens()) {
553 String orderElement = tokenizer.nextToken();
554 int idx = orderElement.indexOf("<");
555 if (idx > 0) {// relative order element
556 String lowerLoc = orderElement.substring(0, idx);
557 String higherLoc = orderElement.substring(idx + 1);
558 locOrder.put(higherLoc, lowerLoc);
559 if (locOrder.isIntroducingCycle(higherLoc)) {
560 throw new Error("Error: the order relation " + lowerLoc + " < " + higherLoc
561 + " introduces a cycle.");
563 } else if (orderElement.startsWith(THISLOC + "=")) {
564 String thisLoc = orderElement.substring(8);
565 locOrder.setThisLoc(thisLoc);
566 } else if (orderElement.startsWith(GLOBALLOC + "=")) {
567 String globalLoc = orderElement.substring(10);
568 locOrder.setGlobalLoc(globalLoc);
569 } else if (orderElement.startsWith(RETURNLOC + "=")) {
570 String returnLoc = orderElement.substring(10);
571 locOrder.setReturnLoc(returnLoc);
572 } else if (orderElement.endsWith("*")) {
573 // spin loc definition
574 locOrder.addSharedLoc(orderElement.substring(0, orderElement.length() - 1));
577 locOrder.put(orderElement);
582 if (locOrder.getThisLoc() != null && !locOrder.containsKey(locOrder.getThisLoc())) {
583 throw new Error("Variable 'this' location '" + locOrder.getThisLoc()
584 + "' is not defined in the local variable lattice at " + cd.getSourceFileName());
587 if (locOrder.getGlobalLoc() != null && !locOrder.containsKey(locOrder.getGlobalLoc())) {
588 throw new Error("Variable global location '" + locOrder.getGlobalLoc()
589 + "' is not defined in the local variable lattice at " + cd.getSourceFileName());
593 private void parseClassLatticeDefinition(ClassDescriptor cd, String value,
594 SSJavaLattice<String> locOrder) {
596 value = value.replaceAll(" ", ""); // remove all blank spaces
598 StringTokenizer tokenizer = new StringTokenizer(value, ",");
600 while (tokenizer.hasMoreTokens()) {
601 String orderElement = tokenizer.nextToken();
602 int idx = orderElement.indexOf("<");
604 if (idx > 0) {// relative order element
605 String lowerLoc = orderElement.substring(0, idx);
606 String higherLoc = orderElement.substring(idx + 1);
607 locOrder.put(higherLoc, lowerLoc);
608 if (locOrder.isIntroducingCycle(higherLoc)) {
609 throw new Error("Error: the order relation " + lowerLoc + " < " + higherLoc
610 + " introduces a cycle in the class lattice " + cd);
612 } else if (orderElement.contains("*")) {
613 // spin loc definition
614 locOrder.addSharedLoc(orderElement.substring(0, orderElement.length() - 1));
617 locOrder.put(orderElement);
622 Set<String> spinLocSet = locOrder.getSharedLocSet();
623 for (Iterator iterator = spinLocSet.iterator(); iterator.hasNext();) {
624 String spinLoc = (String) iterator.next();
625 if (!locOrder.containsKey(spinLoc)) {
626 throw new Error("Spin location '" + spinLoc
627 + "' is not defined in the default local variable lattice at " + cd.getSourceFileName());
632 public Hashtable<ClassDescriptor, SSJavaLattice<String>> getCd2lattice() {
636 public Hashtable<ClassDescriptor, MethodLattice<String>> getCd2methodDefault() {
637 return cd2methodDefault;
640 public Hashtable<MethodDescriptor, MethodLattice<String>> getMd2lattice() {
644 public SSJavaLattice<String> getClassLattice(ClassDescriptor cd) {
645 return cd2lattice.get(cd);
648 public MethodLattice<String> getMethodDefaultLattice(ClassDescriptor cd) {
649 return cd2methodDefault.get(cd);
652 public MethodLattice<String> getMethodLattice(MethodDescriptor md) {
653 if (md2lattice.containsKey(md)) {
654 return md2lattice.get(md);
657 if (cd2methodDefault.containsKey(md.getClassDesc())) {
658 return cd2methodDefault.get(md.getClassDesc());
660 throw new Error("Method Lattice of " + md + " is not defined.");
666 public CompositeLocation getPCLocation(MethodDescriptor md) {
667 if (!md2pcLoc.containsKey(md)) {
668 // by default, the initial pc location is TOP
669 CompositeLocation pcLoc = new CompositeLocation(new Location(md, Location.TOP));
670 md2pcLoc.put(md, pcLoc);
672 return md2pcLoc.get(md);
675 public void setPCLocation(MethodDescriptor md, CompositeLocation pcLoc) {
676 md2pcLoc.put(md, pcLoc);
679 public boolean needToCheckLinearType(MethodDescriptor md) {
680 return linearTypeCheckMethodSet.contains(md);
683 public boolean needTobeAnnotated(MethodDescriptor md) {
684 return annotationRequireSet.contains(md);
687 public boolean needToBeAnnoated(ClassDescriptor cd) {
688 return annotationRequireClassSet.contains(cd);
691 public void addAnnotationRequire(ClassDescriptor cd) {
692 annotationRequireClassSet.add(cd);
695 public void addAnnotationRequire(MethodDescriptor md) {
697 ClassDescriptor cd = md.getClassDesc();
698 // if a method requires to be annotated, class containg that method also
699 // requires to be annotated
700 if (!isSSJavaUtil(cd)) {
701 annotationRequireClassSet.add(cd);
702 annotationRequireSet.add(md);
706 public Set<MethodDescriptor> getAnnotationRequireSet() {
707 return annotationRequireSet;
710 public void doLoopTerminationCheck(LoopOptimize lo, FlatMethod fm) {
711 LoopTerminate lt = new LoopTerminate(this, state);
712 if (needTobeAnnotated(fm.getMethod())) {
713 lt.terminateAnalysis(fm, lo.getLoopInvariant(fm));
717 public CallGraph getCallGraph() {
721 public SSJavaLattice<String> getLattice(Descriptor d) {
723 if (d instanceof MethodDescriptor) {
724 return getMethodLattice((MethodDescriptor) d);
726 return getClassLattice((ClassDescriptor) d);
731 public boolean isSharedLocation(Location loc) {
732 SSJavaLattice<String> lattice = getLattice(loc.getDescriptor());
733 return lattice.getSharedLocSet().contains(loc.getLocIdentifier());
736 public void mapSharedLocation2Descriptor(Location loc, Descriptor d) {
737 Set<Descriptor> set = mapSharedLocation2DescriptorSet.get(loc);
739 set = new HashSet<Descriptor>();
740 mapSharedLocation2DescriptorSet.put(loc, set);
745 public BuildFlat getBuildFlat() {
749 public MethodDescriptor getMethodContainingSSJavaLoop() {
750 return methodContainingSSJavaLoop;
753 public void setMethodContainingSSJavaLoop(MethodDescriptor methodContainingSSJavaLoop) {
754 this.methodContainingSSJavaLoop = methodContainingSSJavaLoop;
757 public boolean isSSJavaUtil(ClassDescriptor cd) {
758 if (cd.getSymbol().equals("SSJAVA")) {
764 public void setFieldOnwership(MethodDescriptor md, FieldDescriptor field) {
766 Set<FieldDescriptor> fieldSet = mapMethodToOwnedFieldSet.get(md);
767 if (fieldSet == null) {
768 fieldSet = new HashSet<FieldDescriptor>();
769 mapMethodToOwnedFieldSet.put(md, fieldSet);
774 public boolean isOwnedByMethod(MethodDescriptor md, FieldDescriptor field) {
775 Set<FieldDescriptor> fieldSet = mapMethodToOwnedFieldSet.get(md);
776 if (fieldSet != null) {
777 return fieldSet.contains(field);
782 public FlatNode getSSJavaLoopEntrance() {
783 return ssjavaLoopEntrance;
786 public void setSSJavaLoopEntrance(FlatNode ssjavaLoopEntrance) {
787 this.ssjavaLoopEntrance = ssjavaLoopEntrance;
790 public void addSameHeightWriteFlatNode(FlatNode fn) {
791 this.sameHeightWriteFlatNodeSet.add(fn);
794 public boolean isSameHeightWrite(FlatNode fn) {
795 return this.sameHeightWriteFlatNodeSet.contains(fn);
798 public LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
800 Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
802 LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
804 Iterator<MethodDescriptor> itr = toSort.iterator();
805 while (itr.hasNext()) {
806 MethodDescriptor d = itr.next();
808 if (!discovered.contains(d)) {
809 dfsVisit(d, toSort, sorted, discovered);
816 // While we're doing DFS on call graph, remember
817 // dependencies for efficient queuing of methods
818 // during interprocedural analysis:
820 // a dependent of a method decriptor d for this analysis is:
821 // 1) a method or task that invokes d
822 // 2) in the descriptorsToAnalyze set
823 private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
824 LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
828 Iterator itr2 = callgraph.getCalleeSet(md).iterator();
829 while (itr2.hasNext()) {
830 MethodDescriptor dCallee = (MethodDescriptor) itr2.next();
831 addDependent(dCallee, md);
834 Iterator itr = callgraph.getCallerSet(md).iterator();
835 while (itr.hasNext()) {
836 MethodDescriptor dCaller = (MethodDescriptor) itr.next();
837 // only consider callers in the original set to analyze
838 if (!toSort.contains(dCaller)) {
841 if (!discovered.contains(dCaller)) {
842 addDependent(md, // callee
846 dfsVisit(dCaller, toSort, sorted, discovered);
850 // for leaf-nodes last now!
854 public void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
855 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
857 deps = new HashSet<MethodDescriptor>();
860 mapDescriptorToSetDependents.put(callee, deps);
863 public Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
864 Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
866 deps = new HashSet<MethodDescriptor>();
867 mapDescriptorToSetDependents.put(callee, deps);