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.HashSet;
   7 import java.util.Hashtable;
   8 import java.util.Iterator;
   9 import java.util.Set;
  10 import java.util.StringTokenizer;
  11 import java.util.Vector;
  12
  13 import Analysis.CallGraph.CallGraph;
  14 import Analysis.Loops.LoopOptimize;
  15 import Analysis.Loops.LoopTerminate;
  16 import IR.AnnotationDescriptor;
  17 import IR.ClassDescriptor;
  18 import IR.Descriptor;
  19 import IR.MethodDescriptor;
  20 import IR.State;
  21 import IR.TypeUtil;
  22 import IR.Flat.BuildFlat;
  23 import IR.Flat.FlatMethod;
  24 import IR.Flat.TempDescriptor;
  25 import Util.Pair;
  26
  27 public class SSJavaAnalysis {
  28
  29   public static final String SSJAVA = "SSJAVA";
  30   public static final String LATTICE = "LATTICE";
  31   public static final String METHODDEFAULT = "METHODDEFAULT";
  32   public static final String THISLOC = "THISLOC";
  33   public static final String GLOBALLOC = "GLOBALLOC";
  34   public static final String RETURNLOC = "RETURNLOC";
  35   public static final String LOC = "LOC";
  36   public static final String DELTA = "DELTA";
  37   public static final String TERMINATE = "TERMINATE";
  38
  39   State state;
  40   TypeUtil tu;
  41   FlowDownCheck flowDownChecker;
  42   MethodAnnotationCheck methodAnnotationChecker;
  43
  44   // set containing method requires to be annoated
  45   Set<MethodDescriptor> annotationRequireSet;
  46
  47   // class -> field lattice
  48   Hashtable<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
  49
  50   // class -> default local variable lattice
  51   Hashtable<ClassDescriptor, MethodLattice<String>> cd2methodDefault;
  52
  53   // method -> local variable lattice
  54   Hashtable<MethodDescriptor, MethodLattice<String>> md2lattice;
  55
  56   // method set that does not want to have loop termination analysis
  57   Hashtable<MethodDescriptor, Integer> skipLoopTerminate;
  58
  59   // map shared location to its descriptors
  60   Hashtable<Location, Set<Descriptor>> mapSharedLocation2DescriptorSet;
  61
  62   // set containing a class that has at least one annoated method
  63   Set<ClassDescriptor> annotationRequireClassSet;
  64
  65   CallGraph callgraph;
  66
  67   public SSJavaAnalysis(State state, TypeUtil tu, CallGraph callgraph) {
  68     this.state = state;
  69     this.tu = tu;
  70     this.callgraph = callgraph;
  71     this.cd2lattice = new Hashtable<ClassDescriptor, SSJavaLattice<String>>();
  72     this.cd2methodDefault = new Hashtable<ClassDescriptor, MethodLattice<String>>();
  73     this.md2lattice = new Hashtable<MethodDescriptor, MethodLattice<String>>();
  74     this.annotationRequireSet = new HashSet<MethodDescriptor>();
  75     this.annotationRequireClassSet = new HashSet<ClassDescriptor>();
  76     this.skipLoopTerminate = new Hashtable<MethodDescriptor, Integer>();
  77     this.mapSharedLocation2DescriptorSet = new Hashtable<Location, Set<Descriptor>>();
  78   }
  79
  80   public void doCheck() {
  81     doMethodAnnotationCheck();
  82     if (state.SSJAVADEBUG) {
  83       debugPrint();
  84     }
  85     parseLocationAnnotation();
  86     doFlowDownCheck();
  87     doDefinitelyWrittenCheck();
  88     doSingleReferenceCheck();
  89   }
  90
  91   public void debugPrint() {
  92     System.out.println("SSJAVA: SSJava is checking the following methods:");
  93     for (Iterator<MethodDescriptor> iterator = annotationRequireSet.iterator(); iterator.hasNext();) {
  94       MethodDescriptor md = iterator.next();
  95       System.out.print(" " + md);
  96     }
  97     System.out.println();
  98   }
  99
 100   private void doMethodAnnotationCheck() {
 101     methodAnnotationChecker = new MethodAnnotationCheck(this, state, tu);
 102     methodAnnotationChecker.methodAnnoatationCheck();
 103     methodAnnotationChecker.methodAnnoataionInheritanceCheck();
 104   }
 105
 106   public void doFlowDownCheck() {
 107     flowDownChecker = new FlowDownCheck(this, state);
 108     flowDownChecker.flowDownCheck();
 109   }
 110
 111   public void doDefinitelyWrittenCheck() {
 112     DefinitelyWrittenCheck checker = new DefinitelyWrittenCheck(this, state);
 113     checker.definitelyWrittenCheck();
 114   }
 115
 116   public void doSingleReferenceCheck() {
 117     SingleReferenceCheck checker = new SingleReferenceCheck(this, state);
 118     checker.singleReferenceCheck();
 119   }
 120
 121   private void parseLocationAnnotation() {
 122     Iterator it = state.getClassSymbolTable().getDescriptorsIterator();
 123     while (it.hasNext()) {
 124       ClassDescriptor cd = (ClassDescriptor) it.next();
 125       // parsing location hierarchy declaration for the class
 126       Vector<AnnotationDescriptor> classAnnotations = cd.getModifier().getAnnotations();
 127       for (int i = 0; i < classAnnotations.size(); i++) {
 128         AnnotationDescriptor an = classAnnotations.elementAt(i);
 129         String marker = an.getMarker();
 130         if (marker.equals(LATTICE)) {
 131           SSJavaLattice<String> locOrder =
 132               new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
 133           cd2lattice.put(cd, locOrder);
 134           parseClassLatticeDefinition(cd, an.getValue(), locOrder);
 135
 136           if (state.SSJAVADEBUG) {
 137             // generate lattice dot file
 138             writeLatticeDotFile(cd, locOrder);
 139           }
 140
 141         } else if (marker.equals(METHODDEFAULT)) {
 142           MethodLattice<String> locOrder =
 143               new MethodLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
 144           cd2methodDefault.put(cd, locOrder);
 145           parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder);
 146         }
 147       }
 148
 149       for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
 150         MethodDescriptor md = (MethodDescriptor) method_it.next();
 151         // parsing location hierarchy declaration for the method
 152
 153         if (needTobeAnnotated(md)) {
 154           Vector<AnnotationDescriptor> methodAnnotations = md.getModifiers().getAnnotations();
 155           if (methodAnnotations != null) {
 156             for (int i = 0; i < methodAnnotations.size(); i++) {
 157               AnnotationDescriptor an = methodAnnotations.elementAt(i);
 158               if (an.getMarker().equals(LATTICE)) {
 159                 // developer explicitly defines method lattice
 160                 MethodLattice<String> locOrder =
 161                     new MethodLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
 162                 md2lattice.put(md, locOrder);
 163                 parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder);
 164               } else if (an.getMarker().equals(TERMINATE)) {
 165                 // developer explicitly wants to skip loop termination analysis
 166                 String value = an.getValue();
 167                 int maxIteration = 0;
 168                 if (value != null) {
 169                   maxIteration = Integer.parseInt(value);
 170                 }
 171                 System.out.println("###md=" + md);
 172                 skipLoopTerminate.put(md, new Integer(maxIteration));
 173               }
 174             }
 175           }
 176         }
 177
 178       }
 179
 180     }
 181   }
 182
 183   private void writeLatticeDotFile(ClassDescriptor cd, SSJavaLattice<String> locOrder) {
 184
 185     String className = cd.getSymbol().replaceAll("[\\W_]", "");
 186
 187     Set<Pair<String, String>> pairSet = locOrder.getOrderingPairSet();
 188
 189     try {
 190       BufferedWriter bw = new BufferedWriter(new FileWriter(className + ".dot"));
 191
 192       bw.write("digraph " + className + " {\n");
 193
 194       for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
 195         // pair is in the form of <higher, lower>
 196         Pair<String, String> pair = (Pair<String, String>) iterator.next();
 197
 198         String highLocId = pair.getFirst();
 199         if (locOrder.isSharedLoc(highLocId)) {
 200           highLocId = "\"" + highLocId + "*\"";
 201         }
 202         String lowLocId = pair.getSecond();
 203         if (locOrder.isSharedLoc(lowLocId)) {
 204           lowLocId = "\"" + lowLocId + "*\"";
 205         }
 206         bw.write(highLocId + " -> " + lowLocId + ";\n");
 207       }
 208       bw.write("}\n");
 209       bw.close();
 210
 211     } catch (IOException e) {
 212       e.printStackTrace();
 213     }
 214
 215   }
 216
 217   private void parseMethodDefaultLatticeDefinition(ClassDescriptor cd, String value,
 218       MethodLattice<String> locOrder) {
 219
 220     value = value.replaceAll(" ", ""); // remove all blank spaces
 221
 222     StringTokenizer tokenizer = new StringTokenizer(value, ",");
 223
 224     while (tokenizer.hasMoreTokens()) {
 225       String orderElement = tokenizer.nextToken();
 226       int idx = orderElement.indexOf("<");
 227       if (idx > 0) {// relative order element
 228         String lowerLoc = orderElement.substring(0, idx);
 229         String higherLoc = orderElement.substring(idx + 1);
 230         locOrder.put(higherLoc, lowerLoc);
 231         if (locOrder.isIntroducingCycle(higherLoc)) {
 232           throw new Error("Error: the order relation " + lowerLoc + " < " + higherLoc
 233               + " introduces a cycle.");
 234         }
 235       } else if (orderElement.startsWith(THISLOC + "=")) {
 236         String thisLoc = orderElement.substring(8);
 237         locOrder.setThisLoc(thisLoc);
 238       } else if (orderElement.startsWith(GLOBALLOC + "=")) {
 239         String globalLoc = orderElement.substring(10);
 240         locOrder.setGlobalLoc(globalLoc);
 241       } else if (orderElement.startsWith(RETURNLOC + "=")) {
 242         String returnLoc = orderElement.substring(10);
 243         locOrder.setReturnLoc(returnLoc);
 244       } else if (orderElement.contains("*")) {
 245         // spin loc definition
 246         locOrder.addSharedLoc(orderElement.substring(0, orderElement.length() - 1));
 247       } else {
 248         // single element
 249         locOrder.put(orderElement);
 250       }
 251     }
 252
 253     // sanity checks
 254     if (locOrder.getThisLoc() != null && !locOrder.containsKey(locOrder.getThisLoc())) {
 255       throw new Error("Variable 'this' location '" + locOrder.getThisLoc()
 256           + "' is not defined in the default local variable lattice at " + cd.getSourceFileName());
 257     }
 258
 259     if (locOrder.getGlobalLoc() != null && !locOrder.containsKey(locOrder.getGlobalLoc())) {
 260       throw new Error("Variable global location '" + locOrder.getGlobalLoc()
 261           + "' is not defined in the default local variable lattice at " + cd.getSourceFileName());
 262     }
 263   }
 264
 265   private void parseClassLatticeDefinition(ClassDescriptor cd, String value,
 266       SSJavaLattice<String> locOrder) {
 267
 268     value = value.replaceAll(" ", ""); // remove all blank spaces
 269
 270     StringTokenizer tokenizer = new StringTokenizer(value, ",");
 271
 272     while (tokenizer.hasMoreTokens()) {
 273       String orderElement = tokenizer.nextToken();
 274       int idx = orderElement.indexOf("<");
 275
 276       if (idx > 0) {// relative order element
 277         String lowerLoc = orderElement.substring(0, idx);
 278         String higherLoc = orderElement.substring(idx + 1);
 279         locOrder.put(higherLoc, lowerLoc);
 280         if (locOrder.isIntroducingCycle(higherLoc)) {
 281           throw new Error("Error: the order relation " + lowerLoc + " < " + higherLoc
 282               + " introduces a cycle.");
 283         }
 284       } else if (orderElement.contains("*")) {
 285         // spin loc definition
 286         locOrder.addSharedLoc(orderElement.substring(0, orderElement.length() - 1));
 287       } else {
 288         // single element
 289         locOrder.put(orderElement);
 290       }
 291     }
 292
 293     // sanity check
 294     Set<String> spinLocSet = locOrder.getSharedLocSet();
 295     for (Iterator iterator = spinLocSet.iterator(); iterator.hasNext();) {
 296       String spinLoc = (String) iterator.next();
 297       if (!locOrder.containsKey(spinLoc)) {
 298         throw new Error("Spin location '" + spinLoc
 299             + "' is not defined in the default local variable lattice at " + cd.getSourceFileName());
 300       }
 301     }
 302   }
 303
 304   public Hashtable<ClassDescriptor, SSJavaLattice<String>> getCd2lattice() {
 305     return cd2lattice;
 306   }
 307
 308   public Hashtable<ClassDescriptor, MethodLattice<String>> getCd2methodDefault() {
 309     return cd2methodDefault;
 310   }
 311
 312   public Hashtable<MethodDescriptor, MethodLattice<String>> getMd2lattice() {
 313     return md2lattice;
 314   }
 315
 316   public SSJavaLattice<String> getClassLattice(ClassDescriptor cd) {
 317     return cd2lattice.get(cd);
 318   }
 319
 320   public MethodLattice<String> getMethodDefaultLattice(ClassDescriptor cd) {
 321     return cd2methodDefault.get(cd);
 322   }
 323
 324   public MethodLattice<String> getMethodLattice(MethodDescriptor md) {
 325     if (md2lattice.containsKey(md)) {
 326       return md2lattice.get(md);
 327     } else {
 328       return cd2methodDefault.get(md.getClassDesc());
 329     }
 330   }
 331
 332   public boolean needTobeAnnotated(MethodDescriptor md) {
 333     return annotationRequireSet.contains(md);
 334   }
 335
 336   public boolean needToBeAnnoated(ClassDescriptor cd) {
 337     return annotationRequireClassSet.contains(cd);
 338   }
 339
 340   public void addAnnotationRequire(ClassDescriptor cd) {
 341     annotationRequireClassSet.add(cd);
 342   }
 343
 344   public void addAnnotationRequire(MethodDescriptor md) {
 345
 346     ClassDescriptor cd = md.getClassDesc();
 347     // if a method requires to be annotated, class containg that method also
 348     // requires to be annotated
 349     annotationRequireClassSet.add(cd);
 350     annotationRequireSet.add(md);
 351   }
 352
 353   public Set<MethodDescriptor> getAnnotationRequireSet() {
 354     return annotationRequireSet;
 355   }
 356
 357   public void doLoopTerminationCheck(LoopOptimize lo, FlatMethod fm) {
 358     LoopTerminate lt = new LoopTerminate();
 359     if (needTobeAnnotated(fm.getMethod())) {
 360       lt.terminateAnalysis(fm, lo.getLoopInvariant(fm));
 361     }
 362   }
 363
 364   public void doLoopTerminationCheck(LoopOptimize lo) {
 365     LoopTerminate lt = new LoopTerminate();
 366     for (Iterator iterator = annotationRequireSet.iterator(); iterator.hasNext();) {
 367       MethodDescriptor md = (MethodDescriptor) iterator.next();
 368       if (!skipLoopTerminate.containsKey(md)) {
 369         FlatMethod fm = state.getMethodFlat(md);
 370         lt.terminateAnalysis(fm, lo.getLoopInvariant(fm));
 371       }
 372     }
 373
 374   }
 375
 376   public CallGraph getCallGraph() {
 377     return callgraph;
 378   }
 379
 380   public SSJavaLattice<String> getLattice(Descriptor d) {
 381
 382     if (d instanceof MethodDescriptor) {
 383       return getMethodLattice((MethodDescriptor) d);
 384     } else {
 385       return getClassLattice((ClassDescriptor) d);
 386     }
 387
 388   }
 389
 390   public boolean isSharedLocation(Location loc) {
 391     SSJavaLattice<String> lattice = getLattice(loc.getDescriptor());
 392     return lattice.getSharedLocSet().contains(loc.getLocIdentifier());
 393   }
 394
 395   public void mapSharedLocation2Descriptor(Location loc, Descriptor d) {
 396     Set<Descriptor> set = mapSharedLocation2DescriptorSet.get(loc);
 397     if (set == null) {
 398       set = new HashSet<Descriptor>();
 399       mapSharedLocation2DescriptorSet.put(loc, set);
 400     }
 401     set.add(d);
 402   }
 403
 404 }