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       }
 207
 208       seseStack.push( fsen );
 209     } break;
 210
 211     case FKind.FlatSESEExitNode: {
 212       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 213       assert !seseStack.empty();
 214       FlatSESEEnterNode fsen = seseStack.pop();
 215     } break;
 216
 217     case FKind.FlatReturnNode: {
 218       FlatReturnNode frn = (FlatReturnNode) fn;
 219       if( !seseStack.empty() &&
 220           !seseStack.peek().getIsCallerSESEplaceholder()
 221           ) {
 222         throw new Error( "Error: return statement enclosed within SESE "+
 223                          seseStack.peek().getPrettyIdentifier() );
 224       }
 225     } break;
 226
 227     }
 228   }
 229
 230
 231   protected void computeLeafSESEs() {
 232
 233     Set<FlatSESEEnterNode> all=new HashSet<FlatSESEEnterNode>();
 234     all.addAll(allSESEs);
 235     all.addAll(allBogusSESEs);
 236
 237     for (Iterator<FlatSESEEnterNode> itr = all.iterator(); itr.hasNext();) {
 238       FlatSESEEnterNode fsen = itr.next();
 239
 240       boolean hasNoNestedChildren = fsen.getChildren().isEmpty();
 241       boolean hasNoChildrenByCall = !hasChildrenByCall(fsen);
 242
 243       fsen.setIsLeafSESE(hasNoNestedChildren && hasNoChildrenByCall);
 244     }
 245
 246     // for( Iterator<FlatSESEEnterNode> itr = allSESEs.iterator();
 247     // itr.hasNext();
 248     // ) {
 249     // FlatSESEEnterNode fsen = itr.next();
 250     //
 251     // boolean hasNoNestedChildren = fsen.getChildren().isEmpty();
 252     // boolean hasNoChildrenByCall = !hasChildrenByCall( fsen );
 253     //
 254     // fsen.setIsLeafSESE( hasNoNestedChildren &&
 255     // hasNoChildrenByCall );
 256     // }
 257   }
 258
 259
 260   protected boolean hasChildrenByCall(FlatSESEEnterNode fsen) {
 261
 262     boolean hasChildrenByCall=false;
 263
 264     // visit every flat node in SESE body, find method calls that
 265     // may transitively call methods with SESEs enclosed
 266     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 267     flatNodesToVisit.add(fsen);
 268
 269     Set<FlatNode> visited = new HashSet<FlatNode>();
 270
 271     while (!flatNodesToVisit.isEmpty()) {
 272       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 273       FlatNode fn = fnItr.next();
 274
 275       flatNodesToVisit.remove(fn);
 276       visited.add(fn);
 277
 278       if (fn.kind() == FKind.FlatCall) {
 279         FlatCall fc = (FlatCall) fn;
 280         MethodDescriptor mdCallee = fc.getMethod();
 281         Set reachable = new HashSet();
 282
 283         reachable.add(mdCallee);
 284         reachable.addAll(callGraph.getAllMethods(mdCallee));
 285
 286         reachable.retainAll(methodsContainingSESEs);
 287
 288         if (!reachable.isEmpty()) {
 289           hasChildrenByCall = true;
 290
 291           if (!fsen.getIsCallerSESEplaceholder()) {
 292             // System.out.println("%%%mdCallee="+mdCallee+" from fsen="+fsen);
 293             Set reachableSESEMethodSet =
 294                 callGraph.getFirstReachableMethodContainingSESE(mdCallee, methodsContainingSESEs);
 295
 296             // if (methodsContainingSESEs.contains(mdCallee)) {
 297             reachableSESEMethodSet.add(mdCallee);
 298             // }
 299
 300             // System.out.println("#");
 301             // System.out.println("fsen"+fsen);
 302             // System.out.println("reachableSESEMethodSet="+reachableSESEMethodSet);
 303
 304             for (Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext();) {
 305               MethodDescriptor md = (MethodDescriptor) iterator.next();
 306               // Set<FlatSESEEnterNode> seseSet = md2seseSet.get(md);
 307               FlatMethod fm = state.getMethodFlat(md);
 308               FlatSESEEnterNode fsenBogus = (FlatSESEEnterNode) fm.getNext(0);
 309               fsenBogus.addSESEParent(fsen);
 310               // System.out.println("% "+fm+"->"+fsen);
 311             }
 312
 313             reachableSESEMethodSet.retainAll(methodsContainingSESEs);
 314
 315             for (Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext();) {
 316               MethodDescriptor md = (MethodDescriptor) iterator.next();
 317               Set<FlatSESEEnterNode> seseSet = md2seseSet.get(md);
 318               if (seseSet != null) {
 319                 fsen.addSESEChildren(seseSet);
 320                 for (Iterator iterator2 = seseSet.iterator(); iterator2.hasNext();) {
 321                   FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
 322                   child.addSESEParent(fsen);
 323                 }
 324               }
 325             }
 326
 327           }
 328         }
 329
 330       }
 331
 332       if (fn == fsen.getFlatExit()) {
 333         // don't enqueue any futher nodes
 334         continue;
 335       }
 336
 337       for (int i = 0; i < fn.numNext(); i++) {
 338         FlatNode nn = fn.getNext(i);
 339
 340         if (!visited.contains(nn)) {
 341           flatNodesToVisit.add(nn);
 342         }
 343       }
 344     }
 345
 346     return hasChildrenByCall;
 347   }
 348
 349
 350 }