Robust/src/Analysis/OoOJava/RBlockStatusAnalysis.java

   1 package Analysis.OoOJava;
   2
   3 import java.util.HashSet;
   4 import java.util.Hashtable;
   5 import java.util.Iterator;
   6 import java.util.LinkedList;
   7 import java.util.Set;
   8 import java.util.Stack;
   9 import java.util.TreeSet;
  10 import java.util.Map.Entry;
  11
  12 import Analysis.CallGraph.CallGraph;
  13 import Analysis.Disjoint.ReachGraph;
  14 import IR.Descriptor;
  15 import IR.MethodDescriptor;
  16 import IR.State;
  17 import IR.TypeDescriptor;
  18 import IR.TypeUtil;
  19 import IR.Flat.FKind;
  20 import IR.Flat.FlatCall;
  21 import IR.Flat.FlatMethod;
  22 import IR.Flat.FlatNode;
  23 import IR.Flat.FlatSESEEnterNode;
  24 import IR.Flat.FlatSESEExitNode;
  25
  26 public class RBlockStatusAnalysis {
  27
  28   // compiler data
  29   State state;
  30   TypeUtil typeUtil;
  31   CallGraph callGraph;
  32   RBlockRelationAnalysis rra;
  33
  34   // per method-per node-rblock stacks
  35   protected Hashtable<FlatMethod, Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>> fm2statusmap;
  36
  37   public RBlockStatusAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph,
  38       RBlockRelationAnalysis rra) {
  39     this.state = state;
  40     this.typeUtil = typeUtil;
  41     this.callGraph = callGraph;
  42     this.rra = rra;
  43
  44     fm2statusmap =
  45         new Hashtable<FlatMethod, Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>>();
  46
  47     MethodDescriptor mdSourceEntry = typeUtil.getMain();
  48     FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
  49
  50     // add all methods transitively reachable from the
  51     // source's main to set for analysis
  52     Set<MethodDescriptor> descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
  53
  54     descriptorsToAnalyze.add(mdSourceEntry);
  55
  56     analyzeMethods(descriptorsToAnalyze);
  57
  58      //analyzeMethodsDebug(descriptorsToAnalyze);
  59   }
  60
  61   protected void analyzeMethods(Set<MethodDescriptor> descriptorsToAnalyze) {
  62
  63     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
  64     while (mdItr.hasNext()) {
  65       FlatMethod fm = state.getMethodFlat(mdItr.next());
  66
  67       Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> fn2seseStatus =
  68           computeRBlockStatus(fm);
  69
  70       fm2statusmap.put(fm, fn2seseStatus);
  71     }
  72   }
  73
  74   public Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> computeRBlockStatus(
  75       FlatMethod fm) {
  76
  77     Hashtable<FlatNode, Stack<FlatSESEEnterNode>> seseStacks =
  78         new Hashtable<FlatNode, Stack<FlatSESEEnterNode>>();
  79
  80     Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> fn2seseStatus =
  81         new Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>();
  82
  83     LinkedList<FlatNode> flatNodesToVisit = new LinkedList<FlatNode>();
  84     flatNodesToVisit.add(fm);
  85
  86     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
  87     seseStacks.put(fm, seseStackFirst);
  88
  89     while (!flatNodesToVisit.isEmpty()) {
  90       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
  91       FlatNode fn = fnItr.next();
  92
  93       Hashtable<FlatSESEEnterNode, Boolean> prevResult = fn2seseStatus.get(fn);
  94
  95       Hashtable<FlatSESEEnterNode, Boolean> currentResult =
  96           new Hashtable<FlatSESEEnterNode, Boolean>();
  97
  98       for (int i = 0; i < fn.numPrev(); i++) {
  99         FlatNode prevFlatNode = fn.getPrev(i);
 100         Hashtable<FlatSESEEnterNode, Boolean> incoming = fn2seseStatus.get(prevFlatNode);
 101         if (incoming != null) {
 102           merge(currentResult, incoming);
 103         }
 104       }
 105
 106       flatNodesToVisit.remove(fn);
 107
 108       nodeActions(fn, fm, currentResult);
 109
 110       // if we have a new result, schedule forward nodes for
 111       // analysis
 112       if (prevResult == null || !currentResult.equals(prevResult)) {
 113         fn2seseStatus.put(fn, currentResult);
 114         for (int i = 0; i < fn.numNext(); i++) {
 115           FlatNode nn = fn.getNext(i);
 116           flatNodesToVisit.addFirst(nn);
 117         }
 118       }
 119     }
 120
 121     return fn2seseStatus;
 122   }
 123
 124   private void merge(Hashtable<FlatSESEEnterNode, Boolean> current,
 125       Hashtable<FlatSESEEnterNode, Boolean> incoming) {
 126
 127     Iterator inIter = incoming.entrySet().iterator();
 128     while (inIter.hasNext()) {
 129       Entry inEntry = (Entry) inIter.next();
 130       FlatSESEEnterNode seseContaining = (FlatSESEEnterNode) inEntry.getKey();
 131       Boolean isAfter = (Boolean) inEntry.getValue();
 132
 133       Boolean currentIsAfter = current.get(seseContaining);
 134       if (currentIsAfter == null || currentIsAfter == Boolean.FALSE) {
 135         current.put(seseContaining, isAfter);
 136       }
 137     }
 138
 139   }
 140
 141   public boolean isInCriticalRegion(FlatMethod fmContaining, FlatNode fn) {
 142     FlatSESEEnterNode seseContaining = rra.getRBlockStacks(fmContaining, fn).peek();
 143     Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> statusMap =
 144         fm2statusmap.get(fmContaining);
 145     Hashtable<FlatSESEEnterNode, Boolean> status = statusMap.get(fn);
 146
 147     if(status.get(seseContaining).booleanValue()==true){
 148 //      System.out.println(fn+" is in the critical region in according to "+seseContaining);
 149     }
 150
 151     return status.get(seseContaining).booleanValue();
 152   }
 153
 154   protected void nodeActions(FlatNode fn, FlatMethod fm,
 155       Hashtable<FlatSESEEnterNode, Boolean> status) {
 156     switch (fn.kind()) {
 157
 158     case FKind.FlatSESEExitNode: {
 159       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 160       FlatSESEEnterNode fsen = fsexn.getFlatEnter();
 161       if (fsen.getParent() != null) {
 162         status.put(fsen.getParent(), Boolean.TRUE);
 163       }
 164     }
 165       break;
 166
 167     case FKind.FlatCall: {
 168       Descriptor mdCaller = fm.getMethod();
 169
 170       FlatCall         fc       = (FlatCall) fn;
 171       MethodDescriptor mdCallee = fc.getMethod();
 172       FlatMethod       fmCallee = state.getMethodFlat( mdCallee );
 173
 174          Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 175
 176       if (mdCallee.isStatic()) {
 177         setPossibleCallees.add(mdCallee);
 178       } else {
 179         TypeDescriptor typeDesc = fc.getThis().getType();
 180         setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
 181       }
 182
 183       Iterator<MethodDescriptor> mdItr = setPossibleCallees.iterator();
 184       while( mdItr.hasNext() ) {
 185         MethodDescriptor mdPossible = mdItr.next();
 186         FlatMethod       fmPossible = state.getMethodFlat( mdPossible );
 187       }
 188
 189       boolean hasSESECallee=false;
 190       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 191         MethodDescriptor md = (MethodDescriptor) iterator.next();
 192         FlatMethod flatMethod = state.getMethodFlat(md);
 193         FlatNode flatNode = flatMethod.getNext(0);
 194         assert flatNode instanceof FlatSESEEnterNode;
 195         FlatSESEEnterNode flatSESE = (FlatSESEEnterNode) flatNode;
 196         hasSESECallee |= (!flatSESE.getIsLeafSESE());
 197       }
 198
 199       Stack<FlatSESEEnterNode> seseStack = rra.getRBlockStacks(fm, fn);
 200       if (!seseStack.isEmpty()) {
 201         FlatSESEEnterNode currentParent = seseStack.peek();
 202         if(!status.containsKey(currentParent)){
 203 //          System.out.println("currentParent="+currentParent+" fm="+currentParent.getfmEnclosing()+" hasSESECallee="+hasSESECallee);
 204           status.put(currentParent, new Boolean(hasSESECallee));
 205         }else{
 206           boolean currentParentStatus=status.get(currentParent).booleanValue();
 207 //          System.out.println("currentParent="+currentParent+" fm="+currentParent.getfmEnclosing()+" hasSESECallee="+hasSESECallee+" currentParentStatus="+currentParentStatus);
 208           status.put(currentParent, new Boolean(hasSESECallee|currentParentStatus));
 209         }
 210       }
 211
 212     } break;
 213
 214     default: {
 215       if (!(fn instanceof FlatMethod)) {
 216         Stack<FlatSESEEnterNode> seseStack = rra.getRBlockStacks(fm, fn);
 217         if (!seseStack.isEmpty()) {
 218           FlatSESEEnterNode currentParent = seseStack.peek();
 219           if (!status.containsKey(currentParent)) {
 220             status.put(currentParent, Boolean.FALSE);
 221           }
 222         }
 223       }
 224
 225     }
 226       break;
 227     }
 228
 229   }
 230
 231   /*
 232    * DEBUG
 233    */
 234   protected void analyzeMethodsDebug(Set<MethodDescriptor> descriptorsToAnalyze) {
 235
 236     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 237     while (mdItr.hasNext()) {
 238       FlatMethod fm = state.getMethodFlat(mdItr.next());
 239       printStatusMap(fm);
 240
 241     }
 242   }
 243
 244   protected void printStatusMap(FlatMethod fm) {
 245
 246     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 247     flatNodesToVisit.add(fm);
 248
 249     Set<FlatNode> visited = new HashSet<FlatNode>();
 250
 251     while (!flatNodesToVisit.isEmpty()) {
 252       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 253       FlatNode fn = fnItr.next();
 254
 255       flatNodesToVisit.remove(fn);
 256       visited.add(fn);
 257
 258       System.out.println("------------------");
 259       System.out.println("fn=" + fn);
 260       System.out.println(fm2statusmap.get(fm).get(fn));
 261
 262       for (int i = 0; i < fn.numNext(); i++) {
 263         FlatNode nn = fn.getNext(i);
 264
 265         if (!visited.contains(nn)) {
 266           flatNodesToVisit.add(nn);
 267
 268         }
 269       }
 270     }
 271
 272   }
 273
 274 }