Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java

   1 package Analysis.OoOJava;
   2
   3 import IR.State;
   4 import IR.TypeUtil;
   5 import Analysis.CallGraph.CallGraph;
   6 import IR.MethodDescriptor;
   7 import IR.Flat.*;
   8 import java.util.*;
   9
  10 // This analysis computes relations between rblocks
  11 // and identifies important rblocks.
  12
  13 public class RBlockRelationAnalysis {
  14
  15   // compiler data
  16   State     state;
  17   TypeUtil  typeUtil;
  18   CallGraph callGraph;
  19
  20   // an implicit SESE is automatically spliced into
  21   // the IR graph around the C main before this analysis--it
  22   // is nothing special except that we can make assumptions
  23   // about it, such as the whole program ends when it ends
  24   protected FlatSESEEnterNode mainSESE;
  25
  26   // SESEs that are the root of an SESE tree belong to this
  27   // set--the main SESE is always a root, statically SESEs
  28   // inside methods are a root because we don't know how they
  29   // will fit into the runtime tree of SESEs
  30   protected Set<FlatSESEEnterNode> rootSESEs;
  31
  32   // simply a set of every reachable SESE in the program, not
  33   // including caller placeholder SESEs
  34   protected Set<FlatSESEEnterNode> allSESEs;
  35
  36   // a set of every bogus palceholder SESEs
  37   protected Set<FlatSESEEnterNode> allBogusSESEs;
  38
  39   // per method-per node-rblock stacks
  40   protected Hashtable< FlatMethod,
  41                        Hashtable< FlatNode,
  42                                   Stack<FlatSESEEnterNode>
  43                                 >
  44                      > fm2relmap;
  45
  46   // to support calculation of leaf SESEs (no children even
  47   // through method calls) for optimization during code gen
  48   protected Set<MethodDescriptor> methodsContainingSESEs;
  49
  50   // maps method descriptor to SESE defined inside of it
  51   // only contains top-level SESE definition in corresponding method
  52   protected Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>> md2seseSet;
  53
  54   public RBlockRelationAnalysis( State     state,
  55                                  TypeUtil  typeUtil,
  56                                  CallGraph callGraph ) {
  57     this.state     = state;
  58     this.typeUtil  = typeUtil;
  59     this.callGraph = callGraph;
  60
  61     rootSESEs = new HashSet<FlatSESEEnterNode>();
  62     allSESEs  = new HashSet<FlatSESEEnterNode>();
  63     allBogusSESEs  = new HashSet<FlatSESEEnterNode>();
  64
  65     methodsContainingSESEs = new HashSet<MethodDescriptor>();
  66
  67     fm2relmap =
  68       new Hashtable< FlatMethod, Hashtable< FlatNode, Stack<FlatSESEEnterNode> > >();
  69
  70     md2seseSet = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
  71
  72
  73     MethodDescriptor mdSourceEntry = typeUtil.getMain();
  74     FlatMethod       fmMain        = state.getMethodFlat( mdSourceEntry );
  75
  76     mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
  77     mainSESE.setfmEnclosing( fmMain );
  78     mainSESE.setmdEnclosing( fmMain.getMethod() );
  79     mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
  80
  81     // add all methods transitively reachable from the
  82     // source's main to set for analysis
  83     Set<MethodDescriptor> descriptorsToAnalyze =
  84       callGraph.getAllMethods( mdSourceEntry );
  85
  86     descriptorsToAnalyze.add( mdSourceEntry );
  87
  88     analyzeMethods( descriptorsToAnalyze );
  89
  90     computeLeafSESEs();
  91   }
  92
  93
  94   public FlatSESEEnterNode getMainSESE() {
  95     return mainSESE;
  96   }
  97
  98   public Set<FlatSESEEnterNode> getRootSESEs() {
  99     return rootSESEs;
 100   }
 101
 102   public Set<FlatSESEEnterNode> getAllSESEs() {
 103     return allSESEs;
 104   }
 105
 106   public Stack<FlatSESEEnterNode> getRBlockStacks( FlatMethod fm,
 107                                                    FlatNode   fn ) {
 108     if( !fm2relmap.containsKey( fm ) ) {
 109       fm2relmap.put( fm, computeRBlockRelations( fm ) );
 110     }
 111     return fm2relmap.get( fm ).get( fn );
 112   }
 113
 114
 115   protected void analyzeMethods( Set<MethodDescriptor> descriptorsToAnalyze ) {
 116
 117     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 118     while( mdItr.hasNext() ) {
 119       FlatMethod fm = state.getMethodFlat( mdItr.next() );
 120
 121       Hashtable< FlatNode, Stack<FlatSESEEnterNode> > relmap =
 122         computeRBlockRelations( fm );
 123
 124       fm2relmap.put( fm, relmap );
 125     }
 126   }
 127
 128   public Hashtable< FlatNode, Stack<FlatSESEEnterNode> >
 129     computeRBlockRelations( FlatMethod fm ) {
 130
 131     Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
 132       new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
 133
 134     // start from flat method top, visit every node in
 135     // method exactly once, find SESE stack on every
 136     // control path
 137     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 138     flatNodesToVisit.add( fm );
 139
 140     Set<FlatNode> visited = new HashSet<FlatNode>();
 141
 142     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 143     seseStacks.put( fm, seseStackFirst );
 144
 145     while( !flatNodesToVisit.isEmpty() ) {
 146       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 147       FlatNode fn = fnItr.next();
 148
 149       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 150       assert seseStack != null;
 151
 152       flatNodesToVisit.remove( fn );
 153       visited.add( fn );
 154
 155       nodeActions( fn, seseStack, fm );
 156
 157       for( int i = 0; i < fn.numNext(); i++ ) {
 158         FlatNode nn = fn.getNext( i );
 159
 160         if( !visited.contains( nn ) ) {
 161           flatNodesToVisit.add( nn );
 162
 163           // clone stack and send along each control path
 164           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 165         }
 166       }
 167     }
 168
 169     return seseStacks;
 170   }
 171
 172   protected void nodeActions( FlatNode fn,
 173                               Stack<FlatSESEEnterNode> seseStack,
 174                               FlatMethod fm ) {
 175     switch( fn.kind() ) {
 176
 177     case FKind.FlatSESEEnterNode: {
 178       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 179
 180       if( !fsen.getIsCallerSESEplaceholder() ) {
 181         allSESEs.add( fsen );
 182         methodsContainingSESEs.add( fm.getMethod() );
 183       }else{
 184         allBogusSESEs.add(fsen);
 185       }
 186
 187       fsen.setfmEnclosing( fm );
 188       fsen.setmdEnclosing( fm.getMethod() );
 189       fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
 190
 191       if(!fsen.getIsCallerSESEplaceholder() && fsen.getParent()==null ){
 192         Set<FlatSESEEnterNode> seseSet=md2seseSet.get(fm.getMethod());
 193         if(seseSet==null){
 194           seseSet=new HashSet<FlatSESEEnterNode>();
 195         }
 196         seseSet.add(fsen);
 197         md2seseSet.put(fm.getMethod(), seseSet);
 198       }
 199
 200       if( seseStack.empty() ) {
 201         rootSESEs.add( fsen );
 202         fsen.setParent( null );
 203       } else {
 204         seseStack.peek().addChild( fsen );
 205         fsen.setParent( seseStack.peek() );
 206         // if the top of stack is not bogus one, it should be a non-bogus parent to the current sese
 207         if(!seseStack.peek().getIsCallerSESEplaceholder()){
 208           fsen.addSESEParent(seseStack.peek());
 209         }
 210       }
 211
 212       seseStack.push( fsen );
 213     } break;
 214
 215     case FKind.FlatSESEExitNode: {
 216       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 217       assert !seseStack.empty();
 218       FlatSESEEnterNode fsen = seseStack.pop();
 219     } break;
 220
 221     case FKind.FlatReturnNode: {
 222       FlatReturnNode frn = (FlatReturnNode) fn;
 223       if( !seseStack.empty() &&
 224           !seseStack.peek().getIsCallerSESEplaceholder()
 225           ) {
 226         throw new Error( "Error: return statement enclosed within SESE "+
 227                          seseStack.peek().getPrettyIdentifier() );
 228       }
 229     } break;
 230
 231     }
 232   }
 233
 234
 235   protected void computeLeafSESEs() {
 236
 237     Set<FlatSESEEnterNode> all=new HashSet<FlatSESEEnterNode>();
 238     all.addAll(allSESEs);
 239     all.addAll(allBogusSESEs);
 240
 241     for (Iterator<FlatSESEEnterNode> itr = all.iterator(); itr.hasNext();) {
 242       FlatSESEEnterNode fsen = itr.next();
 243
 244       boolean hasNoNestedChildren = fsen.getChildren().isEmpty();
 245       boolean hasNoChildrenByCall = !hasChildrenByCall(fsen);
 246
 247       fsen.setIsLeafSESE(hasNoNestedChildren && hasNoChildrenByCall);
 248     }
 249
 250     // for( Iterator<FlatSESEEnterNode> itr = allSESEs.iterator();
 251     // itr.hasNext();
 252     // ) {
 253     // FlatSESEEnterNode fsen = itr.next();
 254     //
 255     // boolean hasNoNestedChildren = fsen.getChildren().isEmpty();
 256     // boolean hasNoChildrenByCall = !hasChildrenByCall( fsen );
 257     //
 258     // fsen.setIsLeafSESE( hasNoNestedChildren &&
 259     // hasNoChildrenByCall );
 260     // }
 261   }
 262
 263
 264   protected boolean hasChildrenByCall(FlatSESEEnterNode fsen) {
 265     boolean hasChildrenByCall=false;
 266
 267     // visit every flat node in SESE body, find method calls that
 268     // may transitively call methods with SESEs enclosed
 269     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 270     flatNodesToVisit.add(fsen);
 271
 272     Set<FlatNode> visited = new HashSet<FlatNode>();
 273
 274     while (!flatNodesToVisit.isEmpty()) {
 275       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 276       FlatNode fn = fnItr.next();
 277
 278       flatNodesToVisit.remove(fn);
 279       visited.add(fn);
 280
 281       if (fn.kind() == FKind.FlatCall) {
 282         FlatCall fc = (FlatCall) fn;
 283         MethodDescriptor mdCallee = fc.getMethod();
 284         Set reachable = new HashSet();
 285
 286         reachable.add(mdCallee);
 287         reachable.addAll(callGraph.getAllMethods(mdCallee));
 288
 289         reachable.retainAll(methodsContainingSESEs);
 290
 291         if (!reachable.isEmpty()) {
 292           hasChildrenByCall = true;
 293
 294           if (!fsen.getIsCallerSESEplaceholder()) {
 295             Set reachableSESEMethodSet =
 296                 callGraph.getFirstReachableMethodContainingSESE(mdCallee, methodsContainingSESEs);
 297
 298             reachableSESEMethodSet.add(mdCallee);
 299
 300             for (Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext();) {
 301               MethodDescriptor md = (MethodDescriptor) iterator.next();
 302               FlatMethod fm = state.getMethodFlat(md);
 303               FlatSESEEnterNode fsenBogus = (FlatSESEEnterNode) fm.getNext(0);
 304               fsenBogus.addSESEParent(fsen);
 305             }
 306
 307             reachableSESEMethodSet.retainAll(methodsContainingSESEs);
 308
 309             for (Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext();) {
 310               MethodDescriptor md = (MethodDescriptor) iterator.next();
 311               Set<FlatSESEEnterNode> seseSet = md2seseSet.get(md);
 312               if (seseSet != null) {
 313                 fsen.addSESEChildren(seseSet);
 314                 for (Iterator iterator2 = seseSet.iterator(); iterator2.hasNext();) {
 315                   FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
 316                   child.addSESEParent(fsen);
 317                 }
 318               }
 319             }
 320
 321           }
 322         }
 323
 324       }
 325
 326       if (fn == fsen.getFlatExit()) {
 327         // don't enqueue any futher nodes
 328         continue;
 329       }
 330
 331       for (int i = 0; i < fn.numNext(); i++) {
 332         FlatNode nn = fn.getNext(i);
 333
 334         if (!visited.contains(nn)) {
 335           flatNodesToVisit.add(nn);
 336         }
 337       }
 338     }
 339
 340     return hasChildrenByCall;
 341   }
 342
 343
 344 }