Robust/src/Analysis/SSJava/SSJavaAnalysis.java

   1 package Analysis.SSJava;
   2
   3 import java.util.Hashtable;
   4 import java.util.Iterator;
   5 import java.util.Set;
   6 import java.util.StringTokenizer;
   7 import java.util.Vector;
   8
   9 import Analysis.Loops.LoopOptimize;
  10 import Analysis.Loops.LoopTerminate;
  11 import IR.AnnotationDescriptor;
  12 import IR.ClassDescriptor;
  13 import IR.MethodDescriptor;
  14 import IR.State;
  15 import IR.TypeUtil;
  16 import IR.Flat.FlatMethod;
  17
  18 public class SSJavaAnalysis {
  19
  20   public static final String SSJAVA = "SSJAVA";
  21   public static final String LATTICE = "LATTICE";
  22   public static final String METHODDEFAULT = "METHODDEFAULT";
  23   public static final String THISLOC = "THISLOC";
  24   public static final String GLOBALLOC = "GLOBALLOC";
  25   public static final String RETURNLOC = "RETURNLOC";
  26   public static final String LOC = "LOC";
  27   public static final String DELTA = "DELTA";
  28   public static final String TERMINATE = "TERMINATE";
  29
  30   State state;
  31   TypeUtil tu;
  32   FlowDownCheck flowDownChecker;
  33   MethodAnnotationCheck methodAnnotationChecker;
  34
  35   // if a method has annotations, the mapping has true
  36   Hashtable<MethodDescriptor, Boolean> md2needAnnotation;
  37
  38   // class -> field lattice
  39   Hashtable<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
  40
  41   // class -> default local variable lattice
  42   Hashtable<ClassDescriptor, MethodLattice<String>> cd2methodDefault;
  43
  44   // method -> local variable lattice
  45   Hashtable<MethodDescriptor, MethodLattice<String>> md2lattice;
  46
  47   // method set that does not have loop termination analysis
  48   Hashtable<MethodDescriptor, Integer> skipLoopTerminate;
  49
  50   public SSJavaAnalysis(State state, TypeUtil tu) {
  51     this.state = state;
  52     this.tu = tu;
  53     this.cd2lattice = new Hashtable<ClassDescriptor, SSJavaLattice<String>>();
  54     this.cd2methodDefault = new Hashtable<ClassDescriptor, MethodLattice<String>>();
  55     this.md2lattice = new Hashtable<MethodDescriptor, MethodLattice<String>>();
  56     this.md2needAnnotation = new Hashtable<MethodDescriptor, Boolean>();
  57     this.skipLoopTerminate = new Hashtable<MethodDescriptor, Integer>();
  58   }
  59
  60   public void doCheck() {
  61     doMethodAnnotationCheck();
  62     parseLocationAnnotation();
  63     doFlowDownCheck();
  64     doDefinitelyWrittenCheck();
  65     doSingleReferenceCheck();
  66   }
  67
  68   private void doMethodAnnotationCheck() {
  69     methodAnnotationChecker = new MethodAnnotationCheck(this, state, tu);
  70     methodAnnotationChecker.methodAnnoatationCheck();
  71     methodAnnotationChecker.methodAnnoataionInheritanceCheck();
  72   }
  73
  74   public void doFlowDownCheck() {
  75     flowDownChecker = new FlowDownCheck(this, state);
  76     flowDownChecker.flowDownCheck();
  77   }
  78
  79   public void doDefinitelyWrittenCheck() {
  80     DefinitelyWrittenCheck checker = new DefinitelyWrittenCheck(state);
  81     checker.definitelyWrittenCheck();
  82   }
  83
  84   public void doSingleReferenceCheck() {
  85     SingleReferenceCheck checker = new SingleReferenceCheck(this, state);
  86     checker.singleReferenceCheck();
  87   }
  88
  89   private void parseLocationAnnotation() {
  90     Iterator it = state.getClassSymbolTable().getDescriptorsIterator();
  91     while (it.hasNext()) {
  92       ClassDescriptor cd = (ClassDescriptor) it.next();
  93       // parsing location hierarchy declaration for the class
  94       Vector<AnnotationDescriptor> classAnnotations = cd.getModifier().getAnnotations();
  95       for (int i = 0; i < classAnnotations.size(); i++) {
  96         AnnotationDescriptor an = classAnnotations.elementAt(i);
  97         String marker = an.getMarker();
  98         if (marker.equals(LATTICE)) {
  99           SSJavaLattice<String> locOrder =
 100               new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
 101           cd2lattice.put(cd, locOrder);
 102           parseClassLatticeDefinition(cd, an.getValue(), locOrder);
 103         } else if (marker.equals(METHODDEFAULT)) {
 104           MethodLattice<String> locOrder =
 105               new MethodLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
 106           cd2methodDefault.put(cd, locOrder);
 107           parseMethodLatticeDefinition(cd, an.getValue(), locOrder);
 108         }
 109       }
 110
 111       for (Iterator method_it = cd.getMethods(); method_it.hasNext();) {
 112         MethodDescriptor md = (MethodDescriptor) method_it.next();
 113         // parsing location hierarchy declaration for the method
 114
 115         if (needAnnotation(md)) {
 116           Vector<AnnotationDescriptor> methodAnnotations = md.getModifiers().getAnnotations();
 117           if (methodAnnotations != null) {
 118             for (int i = 0; i < methodAnnotations.size(); i++) {
 119               AnnotationDescriptor an = methodAnnotations.elementAt(i);
 120               if (an.getMarker().equals(LATTICE)) {
 121                 // developer explicitly defines method lattice
 122                 MethodLattice<String> locOrder =
 123                     new MethodLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
 124                 md2lattice.put(md, locOrder);
 125                 parseMethodLatticeDefinition(cd, an.getValue(), locOrder);
 126               } else if (an.getMarker().equals(TERMINATE)) {
 127                 // developer explicitly wants to skip loop termination analysis
 128                 String value = an.getValue();
 129                 int maxIteration = 0;
 130                 if (value != null) {
 131                   maxIteration = Integer.parseInt(value);
 132                 }
 133                 skipLoopTerminate.put(md, new Integer(maxIteration));
 134               }
 135             }
 136           }
 137         }
 138
 139       }
 140
 141     }
 142   }
 143
 144   private void parseMethodLatticeDefinition(ClassDescriptor cd, String value,
 145       MethodLattice<String> locOrder) {
 146
 147     value = value.replaceAll(" ", ""); // remove all blank spaces
 148
 149     StringTokenizer tokenizer = new StringTokenizer(value, ",");
 150
 151     while (tokenizer.hasMoreTokens()) {
 152       String orderElement = tokenizer.nextToken();
 153       int idx = orderElement.indexOf("<");
 154       if (idx > 0) {// relative order element
 155         String lowerLoc = orderElement.substring(0, idx);
 156         String higherLoc = orderElement.substring(idx + 1);
 157         locOrder.put(higherLoc, lowerLoc);
 158         if (locOrder.isIntroducingCycle(higherLoc)) {
 159           throw new Error("Error: the order relation " + lowerLoc + " < " + higherLoc
 160               + " introduces a cycle.");
 161         }
 162       } else if (orderElement.startsWith(THISLOC + "=")) {
 163         String thisLoc = orderElement.substring(8);
 164         locOrder.setThisLoc(thisLoc);
 165       } else if (orderElement.startsWith(GLOBALLOC + "=")) {
 166         String globalLoc = orderElement.substring(10);
 167         locOrder.setGlobalLoc(globalLoc);
 168       } else if (orderElement.contains("*")) {
 169         // spin loc definition
 170         locOrder.addSpinLoc(orderElement.substring(0, orderElement.length() - 1));
 171       } else {
 172         // single element
 173         locOrder.put(orderElement);
 174       }
 175     }
 176
 177     // sanity checks
 178     if (locOrder.getThisLoc() != null && !locOrder.containsKey(locOrder.getThisLoc())) {
 179       throw new Error("Variable 'this' location '" + locOrder.getThisLoc()
 180           + "' is not defined in the default local variable lattice at " + cd.getSourceFileName());
 181     }
 182
 183     if (locOrder.getGlobalLoc() != null && !locOrder.containsKey(locOrder.getGlobalLoc())) {
 184       throw new Error("Variable global location '" + locOrder.getGlobalLoc()
 185           + "' is not defined in the default local variable lattice at " + cd.getSourceFileName());
 186     }
 187   }
 188
 189   private void parseClassLatticeDefinition(ClassDescriptor cd, String value,
 190       SSJavaLattice<String> locOrder) {
 191
 192     value = value.replaceAll(" ", ""); // remove all blank spaces
 193
 194     StringTokenizer tokenizer = new StringTokenizer(value, ",");
 195
 196     while (tokenizer.hasMoreTokens()) {
 197       String orderElement = tokenizer.nextToken();
 198       int idx = orderElement.indexOf("<");
 199
 200       if (idx > 0) {// relative order element
 201         String lowerLoc = orderElement.substring(0, idx);
 202         String higherLoc = orderElement.substring(idx + 1);
 203         locOrder.put(higherLoc, lowerLoc);
 204         if (locOrder.isIntroducingCycle(higherLoc)) {
 205           throw new Error("Error: the order relation " + lowerLoc + " < " + higherLoc
 206               + " introduces a cycle.");
 207         }
 208       } else if (orderElement.contains("*")) {
 209         // spin loc definition
 210         locOrder.addSpinLoc(orderElement.substring(0, orderElement.length() - 1));
 211       } else {
 212         // single element
 213         locOrder.put(orderElement);
 214       }
 215     }
 216
 217     // sanity check
 218     Set<String> spinLocSet = locOrder.getSpinLocSet();
 219     for (Iterator iterator = spinLocSet.iterator(); iterator.hasNext();) {
 220       String spinLoc = (String) iterator.next();
 221       if (!locOrder.containsKey(spinLoc)) {
 222         throw new Error("Spin location '" + spinLoc
 223             + "' is not defined in the default local variable lattice at " + cd.getSourceFileName());
 224       }
 225     }
 226   }
 227
 228   public Hashtable<ClassDescriptor, SSJavaLattice<String>> getCd2lattice() {
 229     return cd2lattice;
 230   }
 231
 232   public Hashtable<ClassDescriptor, MethodLattice<String>> getCd2methodDefault() {
 233     return cd2methodDefault;
 234   }
 235
 236   public Hashtable<MethodDescriptor, MethodLattice<String>> getMd2lattice() {
 237     return md2lattice;
 238   }
 239
 240   public SSJavaLattice<String> getClassLattice(ClassDescriptor cd) {
 241     return cd2lattice.get(cd);
 242   }
 243
 244   public MethodLattice<String> getMethodLattice(MethodDescriptor md) {
 245     if (md2lattice.containsKey(md)) {
 246       return md2lattice.get(md);
 247     } else {
 248       return cd2methodDefault.get(md.getClassDesc());
 249     }
 250   }
 251
 252   public boolean needAnnotation(MethodDescriptor md) {
 253     return md2needAnnotation.containsKey(md);
 254   }
 255
 256   public void putNeedAnnotation(MethodDescriptor md) {
 257     md2needAnnotation.put(md, new Boolean(true));
 258   }
 259
 260   public Hashtable<MethodDescriptor, Boolean> getMd2hasAnnotation() {
 261     return md2needAnnotation;
 262   }
 263
 264   public void doLoopTerminationCheck(LoopOptimize lo) {
 265     LoopTerminate lt = new LoopTerminate();
 266     Set<MethodDescriptor> mdSet = md2needAnnotation.keySet();
 267     for (Iterator iterator = mdSet.iterator(); iterator.hasNext();) {
 268       MethodDescriptor md = (MethodDescriptor) iterator.next();
 269       if (!skipLoopTerminate.containsKey(md)) {
 270         FlatMethod fm = state.getMethodFlat(md);
 271         lt.terminateAnalysis(fm, lo.getLoopInvariant(fm));
 272       }
 273     }
 274
 275   }
 276
 277 }