Robust/src/Analysis/SSJava/SSJavaAnalysis.java

   1 package Analysis.SSJava;
   2
   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;
  15 import java.util.Map;
  16 import java.util.Set;
  17 import java.util.StringTokenizer;
  18 import java.util.Vector;
  19
  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;
  26 import IR.Descriptor;
  27 import IR.FieldDescriptor;
  28 import IR.MethodDescriptor;
  29 import IR.State;
  30 import IR.SymbolTable;
  31 import IR.TypeUtil;
  32 import IR.Flat.BuildFlat;
  33 import IR.Flat.FlatMethod;
  34 import IR.Flat.FlatNode;
  35 import Util.Pair;
  36
  37 public class SSJavaAnalysis {
  38
  39   public static final String SSJAVA = "SSJAVA";
  40   public static final String LATTICE = "LATTICE";
  41   public static final String METHODDEFAULT = "METHODDEFAULT";
  42   public static final String THISLOC = "THISLOC";
  43   public static final String GLOBALLOC = "GLOBALLOC";
  44   public static final String RETURNLOC = "RETURNLOC";
  45   public static final String PCLOC = "PCLOC";
  46   public static final String LOC = "LOC";
  47   public static final String DELTA = "DELTA";
  48   public static final String TERMINATE = "TERMINATE";
  49   public static final String DELEGATE = "DELEGATE";
  50   public static final String DELEGATETHIS = "DELEGATETHIS";
  51   public static final String TRUST = "TRUST";
  52
  53   public static final String TOP = "_top_";
  54   public static final String BOTTOM = "_bottom_";
  55
  56   State state;
  57   TypeUtil tu;
  58   FlowDownCheck flowDownChecker;
  59   MethodAnnotationCheck methodAnnotationChecker;
  60   BuildFlat bf;
  61
  62   // set containing method requires to be annoated
  63   Set<MethodDescriptor> annotationRequireSet;
  64
  65   // class -> field lattice
  66   Hashtable<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
  67
  68   // class -> default local variable lattice
  69   Hashtable<ClassDescriptor, MethodLattice<String>> cd2methodDefault;
  70
  71   // method -> local variable lattice
  72   Hashtable<MethodDescriptor, MethodLattice<String>> md2lattice;
  73
  74   // method set that does not want to have loop termination analysis
  75   Hashtable<MethodDescriptor, Integer> skipLoopTerminate;
  76
  77   // map shared location to its descriptors
  78   Hashtable<Location, Set<Descriptor>> mapSharedLocation2DescriptorSet;
  79
  80   // set containing a class that has at least one annoated method
  81   Set<ClassDescriptor> annotationRequireClassSet;
  82
  83   // the set of method descriptor required to check the linear type property
  84   Set<MethodDescriptor> linearTypeCheckMethodSet;
  85
  86   // the set of method descriptors annotated as "TRUST"
  87   Set<MethodDescriptor> trustWorthyMDSet;
  88
  89   // method -> the initial program counter location
  90   Map<MethodDescriptor, CompositeLocation> md2pcLoc;
  91
  92   // points to method containing SSJAVA Loop
  93   private MethodDescriptor methodContainingSSJavaLoop;
  94
  95   private FlatNode ssjavaLoopEntrance;
  96
  97   // keep the field ownership from the linear type checking
  98   Hashtable<MethodDescriptor, Set<FieldDescriptor>> mapMethodToOwnedFieldSet;
  99
 100   Set<FlatNode> sameHeightWriteFlatNodeSet;
 101
 102   CallGraph callgraph;
 103
 104   LinearTypeCheck checker;
 105
 106   // maps a descriptor to its known dependents: namely
 107   // methods or tasks that call the descriptor's method
 108   // AND are part of this analysis (reachable from main)
 109   private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
 110
 111   private LinkedList<MethodDescriptor> sortedDescriptors;
 112
 113   private Map<Location, Set<Descriptor>> mapSharedLocToDescSet;
 114
 115   public SSJavaAnalysis(State state, TypeUtil tu, BuildFlat bf, CallGraph callgraph) {
 116     this.state = state;
 117     this.tu = tu;
 118     this.callgraph = callgraph;
 119     this.cd2lattice = new Hashtable<ClassDescriptor, SSJavaLattice<String>>();
 120     this.cd2methodDefault = new Hashtable<ClassDescriptor, MethodLattice<String>>();
 121     this.md2lattice = new Hashtable<MethodDescriptor, MethodLattice<String>>();
 122     this.annotationRequireSet = new HashSet<MethodDescriptor>();
 123     this.annotationRequireClassSet = new HashSet<ClassDescriptor>();
 124     this.skipLoopTerminate = new Hashtable<MethodDescriptor, Integer>();
 125     this.mapSharedLocation2DescriptorSet = new Hashtable<Location, Set<Descriptor>>();
 126     this.linearTypeCheckMethodSet = new HashSet<MethodDescriptor>();
 127     this.bf = bf;
 128     this.trustWorthyMDSet = new HashSet<MethodDescriptor>();
 129     this.mapMethodToOwnedFieldSet = new Hashtable<MethodDescriptor, Set<FieldDescriptor>>();
 130     this.sameHeightWriteFlatNodeSet = new HashSet<FlatNode>();
 131     this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
 132     this.sortedDescriptors = new LinkedList<MethodDescriptor>();
 133     this.md2pcLoc = new HashMap<MethodDescriptor, CompositeLocation>();
 134     this.mapSharedLocToDescSet = new HashMap<Location, Set<Descriptor>>();
 135   }
 136
 137   public void doCheck() {
 138     doMethodAnnotationCheck();
 139
 140     if (state.SSJAVA && !state.SSJAVAINFER) {
 141       computeLinearTypeCheckMethodSet();
 142       doLinearTypeCheck();
 143       init();
 144     }
 145
 146     if (state.SSJAVADEBUG) {
 147       // debug_printAnnotationRequiredSet();
 148     }
 149     if (state.SSJAVAINFER) {
 150       inference();
 151       System.exit(0);
 152     } else {
 153       parseLocationAnnotation();
 154       doFlowDownCheck();
 155       doDefinitelyWrittenCheck();
 156       doLoopCheck();
 157     }
 158   }
 159
 160   public void init() {
 161     // perform topological sort over the set of methods accessed by the main
 162     // event loop
 163     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 164     methodDescriptorsToAnalyze.addAll(getAnnotationRequireSet());
 165     sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
 166   }
 167
 168   public LinkedList<MethodDescriptor> getSortedDescriptors() {
 169     return (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
 170   }
 171
 172   public void addSharedDesc(Location loc, Descriptor fd) {
 173     if (!mapSharedLocToDescSet.containsKey(loc)) {
 174       mapSharedLocToDescSet.put(loc, new HashSet<Descriptor>());
 175     }
 176     mapSharedLocToDescSet.get(loc).add(fd);
 177   }
 178
 179   public Set<Descriptor> getSharedDescSet(Location loc) {
 180     return mapSharedLocToDescSet.get(loc);
 181   }
 182
 183   private void inference() {
 184     LocationInference inferEngine = new LocationInference(this, state);
 185     inferEngine.inference();
 186   }
 187
 188   private void doLoopCheck() {
 189     GlobalFieldType gft = new GlobalFieldType(callgraph, state, tu.getMain());
 190     LoopOptimize lo = new LoopOptimize(gft, tu);
 191
 192     SymbolTable classtable = state.getClassSymbolTable();
 193
 194     List<ClassDescriptor> toanalyzeList = new ArrayList<ClassDescriptor>();
 195     List<MethodDescriptor> toanalyzeMethodList = new ArrayList<MethodDescriptor>();
 196
 197     toanalyzeList.addAll(classtable.getValueSet());
 198     Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
 199       public int compare(ClassDescriptor o1, ClassDescriptor o2) {
 200         return o1.getClassName().compareTo(o2.getClassName());
 201       }
 202     });
 203
 204     for (int i = 0; i < toanalyzeList.size(); i++) {
 205       ClassDescriptor cd = toanalyzeList.get(i);
 206
 207       SymbolTable methodtable = cd.getMethodTable();
 208       toanalyzeMethodList.clear();
 209       toanalyzeMethodList.addAll(methodtable.getValueSet());
 210       Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
 211         public int compare(MethodDescriptor o1, MethodDescriptor o2) {
 212           return o1.getSymbol().compareTo(o2.getSymbol());
 213         }
 214       });
 215
 216       for (int mdIdx = 0; mdIdx < toanalyzeMethodList.size(); mdIdx++) {
 217         MethodDescriptor md = toanalyzeMethodList.get(mdIdx);
 218         if (needTobeAnnotated(md)) {
 219           lo.analyze(state.getMethodFlat(md));
 220           doLoopTerminationCheck(lo, state.getMethodFlat(md));
 221         }
 222       }
 223
 224     }
 225
 226   }
 227
 228   public void addTrustMethod(MethodDescriptor md) {
 229     trustWorthyMDSet.add(md);
 230   }
 231
 232   public boolean isTrustMethod(MethodDescriptor md) {
 233     return trustWorthyMDSet.contains(md);
 234   }
 235
 236   private void computeLinearTypeCheckMethodSet() {
 237
 238     Set<MethodDescriptor> allCalledSet = callgraph.getMethodCalls(tu.getMain());
 239     linearTypeCheckMethodSet.addAll(allCalledSet);
 240
 241     Set<MethodDescriptor> trustedSet = new HashSet<MethodDescriptor>();
 242
 243     for (Iterator iterator = trustWorthyMDSet.iterator(); iterator.hasNext();) {
 244       MethodDescriptor trustMethod = (MethodDescriptor) iterator.next();
 245       Set<MethodDescriptor> calledFromTrustMethodSet = callgraph.getMethodCalls(trustMethod);
 246       trustedSet.add(trustMethod);
 247       trustedSet.addAll(calledFromTrustMethodSet);
 248     }
 249
 250     linearTypeCheckMethodSet.removeAll(trustedSet);
 251
 252     // if a method is called only by trusted method, no need to check linear
 253     // type & flow down rule
 254     for (Iterator iterator = trustedSet.iterator(); iterator.hasNext();) {
 255       MethodDescriptor md = (MethodDescriptor) iterator.next();
 256       Set<MethodDescriptor> callerSet = callgraph.getCallerSet(md);
 257       if (!trustedSet.containsAll(callerSet) && !trustWorthyMDSet.contains(md)) {
 258         linearTypeCheckMethodSet.add(md);
 259       }
 260     }
 261
 262   }
 263
 264   private void doLinearTypeCheck() {
 265     LinearTypeCheck checker = new LinearTypeCheck(this, state);
 266     checker.linearTypeCheck();
 267   }
 268
 269   public void debug_printAnnotationRequiredSet() {
 270     System.out.println("SSJAVA: SSJava is checking the following methods:");
 271     for (Iterator<MethodDescriptor> iterator = annotationRequireSet.iterator(); iterator.hasNext();) {
 272       MethodDescriptor md = iterator.next();
 273       System.out.println(md);
 274     }
 275     System.out.println();
 276   }
 277
 278   private void doMethodAnnotationCheck() {
 279     methodAnnotationChecker = new MethodAnnotationCheck(this, state, tu);
 280     methodAnnotationChecker.methodAnnoatationCheck();
 281     methodAnnotationChecker.methodAnnoataionInheritanceCheck();
 282     if (state.SSJAVAINFER) {
 283       annotationRequireClassSet.add(methodContainingSSJavaLoop.getClassDesc());
 284       annotationRequireSet.add(methodContainingSSJavaLoop);
 285     }
 286     state.setAnnotationRequireSet(annotationRequireSet);
 287   }
 288
 289   public void doFlowDownCheck() {
 290     flowDownChecker = new FlowDownCheck(this, state);
 291     flowDownChecker.flowDownCheck();
 292   }
 293
 294   public void doDefinitelyWrittenCheck() {
 295     DefinitelyWrittenCheck checker = new DefinitelyWrittenCheck(this, state);
 296     checker.definitelyWrittenCheck();
 297   }
 298
 299   private void parseLocationAnnotation() {
 300     Iterator it = state.getClassSymbolTable().getDescriptorsIterator();
 301     while (it.hasNext()) {
 302       ClassDescriptor cd = (ClassDescriptor) it.next();
 303       // parsing location hierarchy declaration for the class
 304       Vector<AnnotationDescriptor> classAnnotations = cd.getModifier().getAnnotations();
 305       for (int i = 0; i < classAnnotations.size(); i++) {
 306         AnnotationDescriptor an = classAnnotations.elementAt(i);
 307         String marker = an.getMarker();
 308         if (marker.equals(LATTICE)) {
 309           SSJavaLattice<String> locOrder =
 310               new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
 311           cd2lattice.put(cd, locOrder);
 312           parseClassLatticeDefinition(cd, an.getValue(), locOrder);
 313
 314           if (state.SSJAVADEBUG) {
 315             // generate lattice dot file
 316             writeLatticeDotFile(cd, null, locOrder);
 317           }
 318
 319         } else if (marker.equals(METHODDEFAULT)) {
 320           MethodLattice<String> locOrder =
 321               new MethodLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
 322           cd2methodDefault.put(cd, locOrder);
 323           parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder);
 324         }
 325       }
 326
 327       for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
 328         MethodDescriptor md = (MethodDescriptor) method_it.next();
 329         // parsing location hierarchy declaration for the method
 330
 331         if (needTobeAnnotated(md)) {
 332           Vector<AnnotationDescriptor> methodAnnotations = md.getModifiers().getAnnotations();
 333           if (methodAnnotations != null) {
 334             for (int i = 0; i < methodAnnotations.size(); i++) {
 335               AnnotationDescriptor an = methodAnnotations.elementAt(i);
 336               if (an.getMarker().equals(LATTICE)) {
 337                 // developer explicitly defines method lattice
 338                 MethodLattice<String> locOrder =
 339                     new MethodLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
 340                 md2lattice.put(md, locOrder);
 341                 parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder);
 342               } else if (an.getMarker().equals(TERMINATE)) {
 343                 // developer explicitly wants to skip loop termination analysis
 344                 String value = an.getValue();
 345                 int maxIteration = 0;
 346                 if (value != null) {
 347                   maxIteration = Integer.parseInt(value);
 348                 }
 349                 skipLoopTerminate.put(md, new Integer(maxIteration));
 350               }
 351             }
 352           }
 353         }
 354
 355       }
 356
 357     }
 358   }
 359
 360   public <T> void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
 361       SSJavaLattice<T> locOrder) {
 362     writeLatticeDotFile(cd, md, locOrder, "");
 363
 364   }
 365
 366   public <T> void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
 367       SSJavaLattice<T> locOrder, String nameSuffix) {
 368
 369     String fileName = "lattice_";
 370     if (md != null) {
 371       fileName +=
 372           cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", "");
 373     } else {
 374       fileName += cd.getSymbol().replaceAll("[\\W_]", "");
 375     }
 376
 377     fileName += nameSuffix;
 378
 379     Set<Pair<T, T>> pairSet = locOrder.getOrderingPairSet();
 380
 381     if (pairSet.size() > 0) {
 382       try {
 383         BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
 384
 385         bw.write("digraph " + fileName + " {\n");
 386
 387         for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
 388           // pair is in the form of <higher, lower>
 389           Pair<T, T> pair = (Pair<T, T>) iterator.next();
 390
 391           T highLocId = pair.getFirst();
 392           String highLocStr, lowLocStr;
 393           if (locOrder.isSharedLoc(highLocId)) {
 394             highLocStr = "\"" + highLocId + "*\"";
 395           } else {
 396             highLocStr = highLocId.toString();
 397           }
 398           T lowLocId = pair.getSecond();
 399           if (locOrder.isSharedLoc(lowLocId)) {
 400             lowLocStr = "\"" + lowLocId + "*\"";
 401           } else {
 402             lowLocStr = lowLocId.toString();
 403           }
 404           bw.write(highLocStr + " -> " + lowLocStr + ";\n");
 405         }
 406         bw.write("}\n");
 407         bw.close();
 408
 409       } catch (IOException e) {
 410         e.printStackTrace();
 411       }
 412
 413     }
 414
 415   }
 416
 417   private void parseMethodDefaultLatticeDefinition(ClassDescriptor cd, String value,
 418       MethodLattice<String> locOrder) {
 419
 420     value = value.replaceAll(" ", ""); // remove all blank spaces
 421
 422     StringTokenizer tokenizer = new StringTokenizer(value, ",");
 423
 424     while (tokenizer.hasMoreTokens()) {
 425       String orderElement = tokenizer.nextToken();
 426       int idx = orderElement.indexOf("<");
 427       if (idx > 0) {// relative order element
 428         String lowerLoc = orderElement.substring(0, idx);
 429         String higherLoc = orderElement.substring(idx + 1);
 430         locOrder.put(higherLoc, lowerLoc);
 431         if (locOrder.isIntroducingCycle(higherLoc)) {
 432           throw new Error("Error: the order relation " + lowerLoc + " < " + higherLoc
 433               + " introduces a cycle.");
 434         }
 435       } else if (orderElement.startsWith(THISLOC + "=")) {
 436         String thisLoc = orderElement.substring(8);
 437         locOrder.setThisLoc(thisLoc);
 438       } else if (orderElement.startsWith(GLOBALLOC + "=")) {
 439         String globalLoc = orderElement.substring(10);
 440         locOrder.setGlobalLoc(globalLoc);
 441       } else if (orderElement.startsWith(RETURNLOC + "=")) {
 442         String returnLoc = orderElement.substring(10);
 443         locOrder.setReturnLoc(returnLoc);
 444       } else if (orderElement.endsWith("*")) {
 445         // spin loc definition
 446         locOrder.addSharedLoc(orderElement.substring(0, orderElement.length() - 1));
 447       } else {
 448         // single element
 449         locOrder.put(orderElement);
 450       }
 451     }
 452
 453     // sanity checks
 454     if (locOrder.getThisLoc() != null && !locOrder.containsKey(locOrder.getThisLoc())) {
 455       throw new Error("Variable 'this' location '" + locOrder.getThisLoc()
 456           + "' is not defined in the local variable lattice at " + cd.getSourceFileName());
 457     }
 458
 459     if (locOrder.getGlobalLoc() != null && !locOrder.containsKey(locOrder.getGlobalLoc())) {
 460       throw new Error("Variable global location '" + locOrder.getGlobalLoc()
 461           + "' is not defined in the local variable lattice at " + cd.getSourceFileName());
 462     }
 463   }
 464
 465   private void parseClassLatticeDefinition(ClassDescriptor cd, String value,
 466       SSJavaLattice<String> locOrder) {
 467
 468     value = value.replaceAll(" ", ""); // remove all blank spaces
 469
 470     StringTokenizer tokenizer = new StringTokenizer(value, ",");
 471
 472     while (tokenizer.hasMoreTokens()) {
 473       String orderElement = tokenizer.nextToken();
 474       int idx = orderElement.indexOf("<");
 475
 476       if (idx > 0) {// relative order element
 477         String lowerLoc = orderElement.substring(0, idx);
 478         String higherLoc = orderElement.substring(idx + 1);
 479         locOrder.put(higherLoc, lowerLoc);
 480         if (locOrder.isIntroducingCycle(higherLoc)) {
 481           throw new Error("Error: the order relation " + lowerLoc + " < " + higherLoc
 482               + " introduces a cycle in the class lattice " + cd);
 483         }
 484       } else if (orderElement.contains("*")) {
 485         // spin loc definition
 486         locOrder.addSharedLoc(orderElement.substring(0, orderElement.length() - 1));
 487       } else {
 488         // single element
 489         locOrder.put(orderElement);
 490       }
 491     }
 492
 493     // sanity check
 494     Set<String> spinLocSet = locOrder.getSharedLocSet();
 495     for (Iterator iterator = spinLocSet.iterator(); iterator.hasNext();) {
 496       String spinLoc = (String) iterator.next();
 497       if (!locOrder.containsKey(spinLoc)) {
 498         throw new Error("Spin location '" + spinLoc
 499             + "' is not defined in the default local variable lattice at " + cd.getSourceFileName());
 500       }
 501     }
 502   }
 503
 504   public Hashtable<ClassDescriptor, SSJavaLattice<String>> getCd2lattice() {
 505     return cd2lattice;
 506   }
 507
 508   public Hashtable<ClassDescriptor, MethodLattice<String>> getCd2methodDefault() {
 509     return cd2methodDefault;
 510   }
 511
 512   public Hashtable<MethodDescriptor, MethodLattice<String>> getMd2lattice() {
 513     return md2lattice;
 514   }
 515
 516   public SSJavaLattice<String> getClassLattice(ClassDescriptor cd) {
 517     return cd2lattice.get(cd);
 518   }
 519
 520   public MethodLattice<String> getMethodDefaultLattice(ClassDescriptor cd) {
 521     return cd2methodDefault.get(cd);
 522   }
 523
 524   public MethodLattice<String> getMethodLattice(MethodDescriptor md) {
 525     if (md2lattice.containsKey(md)) {
 526       return md2lattice.get(md);
 527     } else {
 528
 529       if (cd2methodDefault.containsKey(md.getClassDesc())) {
 530         return cd2methodDefault.get(md.getClassDesc());
 531       } else {
 532         throw new Error("Method Lattice of " + md + " is not defined.");
 533       }
 534
 535     }
 536   }
 537
 538   public CompositeLocation getPCLocation(MethodDescriptor md) {
 539     if (!md2pcLoc.containsKey(md)) {
 540       // by default, the initial pc location is TOP
 541       CompositeLocation pcLoc = new CompositeLocation(new Location(md, Location.TOP));
 542       md2pcLoc.put(md, pcLoc);
 543     }
 544     return md2pcLoc.get(md);
 545   }
 546
 547   public void setPCLocation(MethodDescriptor md, CompositeLocation pcLoc) {
 548     md2pcLoc.put(md, pcLoc);
 549   }
 550
 551   public boolean needToCheckLinearType(MethodDescriptor md) {
 552     return linearTypeCheckMethodSet.contains(md);
 553   }
 554
 555   public boolean needTobeAnnotated(MethodDescriptor md) {
 556     return annotationRequireSet.contains(md);
 557   }
 558
 559   public boolean needToBeAnnoated(ClassDescriptor cd) {
 560     return annotationRequireClassSet.contains(cd);
 561   }
 562
 563   public void addAnnotationRequire(ClassDescriptor cd) {
 564     annotationRequireClassSet.add(cd);
 565   }
 566
 567   public void addAnnotationRequire(MethodDescriptor md) {
 568
 569     ClassDescriptor cd = md.getClassDesc();
 570     // if a method requires to be annotated, class containg that method also
 571     // requires to be annotated
 572     if (!isSSJavaUtil(cd)) {
 573       annotationRequireClassSet.add(cd);
 574       annotationRequireSet.add(md);
 575     }
 576   }
 577
 578   public Set<MethodDescriptor> getAnnotationRequireSet() {
 579     return annotationRequireSet;
 580   }
 581
 582   public void doLoopTerminationCheck(LoopOptimize lo, FlatMethod fm) {
 583     LoopTerminate lt = new LoopTerminate(this, state);
 584     if (needTobeAnnotated(fm.getMethod())) {
 585       lt.terminateAnalysis(fm, lo.getLoopInvariant(fm));
 586     }
 587   }
 588
 589   public CallGraph getCallGraph() {
 590     return callgraph;
 591   }
 592
 593   public SSJavaLattice<String> getLattice(Descriptor d) {
 594
 595     if (d instanceof MethodDescriptor) {
 596       return getMethodLattice((MethodDescriptor) d);
 597     } else {
 598       return getClassLattice((ClassDescriptor) d);
 599     }
 600
 601   }
 602
 603   public boolean isSharedLocation(Location loc) {
 604     SSJavaLattice<String> lattice = getLattice(loc.getDescriptor());
 605     return lattice.getSharedLocSet().contains(loc.getLocIdentifier());
 606   }
 607
 608   public void mapSharedLocation2Descriptor(Location loc, Descriptor d) {
 609     Set<Descriptor> set = mapSharedLocation2DescriptorSet.get(loc);
 610     if (set == null) {
 611       set = new HashSet<Descriptor>();
 612       mapSharedLocation2DescriptorSet.put(loc, set);
 613     }
 614     set.add(d);
 615   }
 616
 617   public BuildFlat getBuildFlat() {
 618     return bf;
 619   }
 620
 621   public MethodDescriptor getMethodContainingSSJavaLoop() {
 622     return methodContainingSSJavaLoop;
 623   }
 624
 625   public void setMethodContainingSSJavaLoop(MethodDescriptor methodContainingSSJavaLoop) {
 626     this.methodContainingSSJavaLoop = methodContainingSSJavaLoop;
 627   }
 628
 629   public boolean isSSJavaUtil(ClassDescriptor cd) {
 630     if (cd.getSymbol().equals("SSJAVA")) {
 631       return true;
 632     }
 633     return false;
 634   }
 635
 636   public void setFieldOnwership(MethodDescriptor md, FieldDescriptor field) {
 637
 638     Set<FieldDescriptor> fieldSet = mapMethodToOwnedFieldSet.get(md);
 639     if (fieldSet == null) {
 640       fieldSet = new HashSet<FieldDescriptor>();
 641       mapMethodToOwnedFieldSet.put(md, fieldSet);
 642     }
 643     fieldSet.add(field);
 644   }
 645
 646   public boolean isOwnedByMethod(MethodDescriptor md, FieldDescriptor field) {
 647     Set<FieldDescriptor> fieldSet = mapMethodToOwnedFieldSet.get(md);
 648     if (fieldSet != null) {
 649       return fieldSet.contains(field);
 650     }
 651     return false;
 652   }
 653
 654   public FlatNode getSSJavaLoopEntrance() {
 655     return ssjavaLoopEntrance;
 656   }
 657
 658   public void setSSJavaLoopEntrance(FlatNode ssjavaLoopEntrance) {
 659     this.ssjavaLoopEntrance = ssjavaLoopEntrance;
 660   }
 661
 662   public void addSameHeightWriteFlatNode(FlatNode fn) {
 663     this.sameHeightWriteFlatNodeSet.add(fn);
 664   }
 665
 666   public boolean isSameHeightWrite(FlatNode fn) {
 667     return this.sameHeightWriteFlatNodeSet.contains(fn);
 668   }
 669
 670   public LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
 671
 672     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
 673
 674     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
 675
 676     Iterator<MethodDescriptor> itr = toSort.iterator();
 677     while (itr.hasNext()) {
 678       MethodDescriptor d = itr.next();
 679
 680       if (!discovered.contains(d)) {
 681         dfsVisit(d, toSort, sorted, discovered);
 682       }
 683     }
 684
 685     return sorted;
 686   }
 687
 688   // While we're doing DFS on call graph, remember
 689   // dependencies for efficient queuing of methods
 690   // during interprocedural analysis:
 691   //
 692   // a dependent of a method decriptor d for this analysis is:
 693   // 1) a method or task that invokes d
 694   // 2) in the descriptorsToAnalyze set
 695   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
 696       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
 697
 698     discovered.add(md);
 699
 700     Iterator itr2 = callgraph.getCalleeSet(md).iterator();
 701     while (itr2.hasNext()) {
 702       MethodDescriptor dCallee = (MethodDescriptor) itr2.next();
 703       addDependent(dCallee, md);
 704     }
 705
 706     Iterator itr = callgraph.getCallerSet(md).iterator();
 707     while (itr.hasNext()) {
 708       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
 709       // only consider callers in the original set to analyze
 710       if (!toSort.contains(dCaller)) {
 711         continue;
 712       }
 713       if (!discovered.contains(dCaller)) {
 714         addDependent(md, // callee
 715             dCaller // caller
 716         );
 717
 718         dfsVisit(dCaller, toSort, sorted, discovered);
 719       }
 720     }
 721
 722     // for leaf-nodes last now!
 723     sorted.addLast(md);
 724   }
 725
 726   public void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
 727     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
 728     if (deps == null) {
 729       deps = new HashSet<MethodDescriptor>();
 730     }
 731     deps.add(caller);
 732     mapDescriptorToSetDependents.put(callee, deps);
 733   }
 734
 735   public Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
 736     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
 737     if (deps == null) {
 738       deps = new HashSet<MethodDescriptor>();
 739       mapDescriptorToSetDependents.put(callee, deps);
 740     }
 741     return deps;
 742   }
 743
 744 }