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.Map.Entry;
  10
  11 import Analysis.CallGraph.CallGraph;
  12 import IR.MethodDescriptor;
  13 import IR.State;
  14 import IR.TypeUtil;
  15 import IR.Flat.FKind;
  16 import IR.Flat.FlatMethod;
  17 import IR.Flat.FlatNode;
  18 import IR.Flat.FlatSESEEnterNode;
  19 import IR.Flat.FlatSESEExitNode;
  20
  21 public class RBlockStatusAnalysis {
  22
  23   // compiler data
  24   State state;
  25   TypeUtil typeUtil;
  26   CallGraph callGraph;
  27   RBlockRelationAnalysis rra;
  28
  29   // per method-per node-rblock stacks
  30   protected Hashtable<FlatMethod, Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>> fm2statusmap;
  31
  32   public RBlockStatusAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph,
  33       RBlockRelationAnalysis rra) {
  34     this.state = state;
  35     this.typeUtil = typeUtil;
  36     this.callGraph = callGraph;
  37     this.rra = rra;
  38
  39     fm2statusmap =
  40         new Hashtable<FlatMethod, Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>>();
  41
  42     MethodDescriptor mdSourceEntry = typeUtil.getMain();
  43     FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
  44
  45     // add all methods transitively reachable from the
  46     // source's main to set for analysis
  47     Set<MethodDescriptor> descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
  48
  49     descriptorsToAnalyze.add(mdSourceEntry);
  50
  51     analyzeMethods(descriptorsToAnalyze);
  52
  53     // analyzeMethodsDebug(descriptorsToAnalyze);
  54   }
  55
  56   protected void analyzeMethods(Set<MethodDescriptor> descriptorsToAnalyze) {
  57
  58     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
  59     while (mdItr.hasNext()) {
  60       FlatMethod fm = state.getMethodFlat(mdItr.next());
  61
  62       Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> fn2seseStatus =
  63           computeRBlockStatus(fm);
  64
  65       fm2statusmap.put(fm, fn2seseStatus);
  66     }
  67   }
  68
  69   public Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> computeRBlockStatus(
  70       FlatMethod fm) {
  71
  72     Hashtable<FlatNode, Stack<FlatSESEEnterNode>> seseStacks =
  73         new Hashtable<FlatNode, Stack<FlatSESEEnterNode>>();
  74
  75     Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> fn2seseStatus =
  76         new Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>();
  77
  78     LinkedList<FlatNode> flatNodesToVisit = new LinkedList<FlatNode>();
  79     flatNodesToVisit.add(fm);
  80
  81     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
  82     seseStacks.put(fm, seseStackFirst);
  83
  84     while (!flatNodesToVisit.isEmpty()) {
  85       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
  86       FlatNode fn = fnItr.next();
  87
  88       Hashtable<FlatSESEEnterNode, Boolean> prevResult = fn2seseStatus.get(fn);
  89
  90       Hashtable<FlatSESEEnterNode, Boolean> currentResult =
  91           new Hashtable<FlatSESEEnterNode, Boolean>();
  92
  93       for (int i = 0; i < fn.numPrev(); i++) {
  94         FlatNode prevFlatNode = fn.getPrev(i);
  95         Hashtable<FlatSESEEnterNode, Boolean> incoming = fn2seseStatus.get(prevFlatNode);
  96         if (incoming != null) {
  97           merge(currentResult, incoming);
  98         }
  99       }
 100
 101       flatNodesToVisit.remove(fn);
 102
 103       nodeActions(fn, fm, currentResult);
 104
 105       // if we have a new result, schedule forward nodes for
 106       // analysis
 107       if (prevResult == null || !currentResult.equals(prevResult)) {
 108         fn2seseStatus.put(fn, currentResult);
 109         for (int i = 0; i < fn.numNext(); i++) {
 110           FlatNode nn = fn.getNext(i);
 111           flatNodesToVisit.addFirst(nn);
 112         }
 113       }
 114     }
 115
 116     return fn2seseStatus;
 117   }
 118
 119   private void merge(Hashtable<FlatSESEEnterNode, Boolean> current,
 120       Hashtable<FlatSESEEnterNode, Boolean> incoming) {
 121
 122     Iterator inIter = incoming.entrySet().iterator();
 123     while (inIter.hasNext()) {
 124       Entry inEntry = (Entry) inIter.next();
 125       FlatSESEEnterNode seseContaining = (FlatSESEEnterNode) inEntry.getKey();
 126       Boolean isAfter = (Boolean) inEntry.getValue();
 127
 128       Boolean currentIsAfter = current.get(seseContaining);
 129       if (currentIsAfter == null || currentIsAfter == Boolean.FALSE) {
 130         current.put(seseContaining, isAfter);
 131       }
 132     }
 133
 134   }
 135
 136   public boolean isInCriticalRegion(FlatMethod fmContaining, FlatNode fn) {
 137     FlatSESEEnterNode seseContaining = rra.getRBlockStacks(fmContaining, fn).peek();
 138     Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> statusMap =
 139         fm2statusmap.get(fmContaining);
 140     Hashtable<FlatSESEEnterNode, Boolean> status = statusMap.get(fn);
 141
 142     if(status.get(seseContaining).booleanValue()==true){
 143       //System.out.println(fn+" is in the critical region in according to "+seseContaining);
 144     }
 145
 146     return status.get(seseContaining).booleanValue();
 147   }
 148
 149   protected void nodeActions(FlatNode fn, FlatMethod fm,
 150       Hashtable<FlatSESEEnterNode, Boolean> status) {
 151     switch (fn.kind()) {
 152
 153     case FKind.FlatSESEExitNode: {
 154       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 155       FlatSESEEnterNode fsen = fsexn.getFlatEnter();
 156       if (fsen.getParent() != null) {
 157         status.put(fsen.getParent(), Boolean.TRUE);
 158       }
 159     }
 160       break;
 161
 162     default: {
 163       if (!(fn instanceof FlatMethod)) {
 164         Stack<FlatSESEEnterNode> seseStack = rra.getRBlockStacks(fm, fn);
 165         if (!seseStack.isEmpty()) {
 166           FlatSESEEnterNode currentParent = seseStack.peek();
 167           if (!status.containsKey(currentParent)) {
 168             status.put(currentParent, Boolean.FALSE);
 169           }
 170         }
 171       }
 172
 173     }
 174       break;
 175     }
 176
 177   }
 178
 179   /*
 180    * DEBUG
 181    */
 182   protected void analyzeMethodsDebug(Set<MethodDescriptor> descriptorsToAnalyze) {
 183
 184     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 185     while (mdItr.hasNext()) {
 186       FlatMethod fm = state.getMethodFlat(mdItr.next());
 187       printStatusMap(fm);
 188
 189     }
 190   }
 191
 192   protected void printStatusMap(FlatMethod fm) {
 193
 194     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 195     flatNodesToVisit.add(fm);
 196
 197     Set<FlatNode> visited = new HashSet<FlatNode>();
 198
 199     while (!flatNodesToVisit.isEmpty()) {
 200       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 201       FlatNode fn = fnItr.next();
 202
 203       flatNodesToVisit.remove(fn);
 204       visited.add(fn);
 205
 206       System.out.println("------------------");
 207       System.out.println("fn=" + fn);
 208       System.out.println(fm2statusmap.get(fm).get(fn));
 209
 210       for (int i = 0; i < fn.numNext(); i++) {
 211         FlatNode nn = fn.getNext(i);
 212
 213         if (!visited.contains(nn)) {
 214           flatNodesToVisit.add(nn);
 215
 216         }
 217       }
 218     }
 219
 220   }
 221
 222 }