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   // per method-per node-rblock stacks
  37   protected Hashtable< FlatMethod,
  38                        Hashtable< FlatNode,
  39                                   Stack<FlatSESEEnterNode>
  40                                 >
  41                      > fm2relmap;
  42
  43   // to support calculation of leaf SESEs (no children even
  44   // through method calls) for optimization during code gen
  45   protected Set<MethodDescriptor> methodsContainingSESEs;
  46
  47   // maps method descriptor to SESE defined inside of it
  48   // only contains top-level SESE definition in corresponding method
  49   protected Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>> md2seseSet;
  50
  51   public RBlockRelationAnalysis( State     state,
  52                                  TypeUtil  typeUtil,
  53                                  CallGraph callGraph ) {
  54     this.state     = state;
  55     this.typeUtil  = typeUtil;
  56     this.callGraph = callGraph;
  57
  58     rootSESEs = new HashSet<FlatSESEEnterNode>();
  59     allSESEs  = new HashSet<FlatSESEEnterNode>();
  60
  61     methodsContainingSESEs = new HashSet<MethodDescriptor>();
  62
  63     fm2relmap =
  64       new Hashtable< FlatMethod, Hashtable< FlatNode, Stack<FlatSESEEnterNode> > >();
  65
  66     md2seseSet = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
  67
  68
  69     MethodDescriptor mdSourceEntry = typeUtil.getMain();
  70     FlatMethod       fmMain        = state.getMethodFlat( mdSourceEntry );
  71
  72     mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
  73     mainSESE.setfmEnclosing( fmMain );
  74     mainSESE.setmdEnclosing( fmMain.getMethod() );
  75     mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
  76
  77     // add all methods transitively reachable from the
  78     // source's main to set for analysis
  79     Set<MethodDescriptor> descriptorsToAnalyze =
  80       callGraph.getAllMethods( mdSourceEntry );
  81
  82     descriptorsToAnalyze.add( mdSourceEntry );
  83
  84     analyzeMethods( descriptorsToAnalyze );
  85
  86     computeLeafSESEs();
  87   }
  88
  89
  90   public FlatSESEEnterNode getMainSESE() {
  91     return mainSESE;
  92   }
  93
  94   public Set<FlatSESEEnterNode> getRootSESEs() {
  95     return rootSESEs;
  96   }
  97
  98   public Set<FlatSESEEnterNode> getAllSESEs() {
  99     return allSESEs;
 100   }
 101
 102   public Stack<FlatSESEEnterNode> getRBlockStacks( FlatMethod fm,
 103                                                    FlatNode   fn ) {
 104     if( !fm2relmap.containsKey( fm ) ) {
 105       fm2relmap.put( fm, computeRBlockRelations( fm ) );
 106     }
 107     return fm2relmap.get( fm ).get( fn );
 108   }
 109
 110
 111   protected void analyzeMethods( Set<MethodDescriptor> descriptorsToAnalyze ) {
 112
 113     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 114     while( mdItr.hasNext() ) {
 115       FlatMethod fm = state.getMethodFlat( mdItr.next() );
 116
 117       Hashtable< FlatNode, Stack<FlatSESEEnterNode> > relmap =
 118         computeRBlockRelations( fm );
 119
 120       fm2relmap.put( fm, relmap );
 121     }
 122   }
 123
 124   public Hashtable< FlatNode, Stack<FlatSESEEnterNode> >
 125     computeRBlockRelations( FlatMethod fm ) {
 126
 127     Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
 128       new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
 129
 130     // start from flat method top, visit every node in
 131     // method exactly once, find SESE stack on every
 132     // control path
 133     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 134     flatNodesToVisit.add( fm );
 135
 136     Set<FlatNode> visited = new HashSet<FlatNode>();
 137
 138     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 139     seseStacks.put( fm, seseStackFirst );
 140
 141     while( !flatNodesToVisit.isEmpty() ) {
 142       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 143       FlatNode fn = fnItr.next();
 144
 145       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 146       assert seseStack != null;
 147
 148       flatNodesToVisit.remove( fn );
 149       visited.add( fn );
 150
 151       nodeActions( fn, seseStack, fm );
 152
 153       for( int i = 0; i < fn.numNext(); i++ ) {
 154         FlatNode nn = fn.getNext( i );
 155
 156         if( !visited.contains( nn ) ) {
 157           flatNodesToVisit.add( nn );
 158
 159           // clone stack and send along each control path
 160           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 161         }
 162       }
 163     }
 164
 165     return seseStacks;
 166   }
 167
 168   protected void nodeActions( FlatNode fn,
 169                               Stack<FlatSESEEnterNode> seseStack,
 170                               FlatMethod fm ) {
 171     switch( fn.kind() ) {
 172
 173     case FKind.FlatSESEEnterNode: {
 174       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 175
 176       if( !fsen.getIsCallerSESEplaceholder() ) {
 177         allSESEs.add( fsen );
 178         methodsContainingSESEs.add( fm.getMethod() );
 179       }
 180
 181       fsen.setfmEnclosing( fm );
 182       fsen.setmdEnclosing( fm.getMethod() );
 183       fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
 184
 185       if(!fsen.getIsCallerSESEplaceholder() && fsen.getParent()==null ){
 186         Set<FlatSESEEnterNode> seseSet=md2seseSet.get(fm.getMethod());
 187         if(seseSet==null){
 188           seseSet=new HashSet<FlatSESEEnterNode>();
 189         }
 190         seseSet.add(fsen);
 191         md2seseSet.put(fm.getMethod(), seseSet);
 192       }
 193
 194       if( seseStack.empty() ) {
 195         rootSESEs.add( fsen );
 196         fsen.setParent( null );
 197       } else {
 198         seseStack.peek().addChild( fsen );
 199         fsen.setParent( seseStack.peek() );
 200       }
 201
 202       seseStack.push( fsen );
 203     } break;
 204
 205     case FKind.FlatSESEExitNode: {
 206       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 207       assert !seseStack.empty();
 208       FlatSESEEnterNode fsen = seseStack.pop();
 209     } break;
 210
 211     case FKind.FlatReturnNode: {
 212       FlatReturnNode frn = (FlatReturnNode) fn;
 213       if( !seseStack.empty() &&
 214           !seseStack.peek().getIsCallerSESEplaceholder()
 215           ) {
 216         throw new Error( "Error: return statement enclosed within SESE "+
 217                          seseStack.peek().getPrettyIdentifier() );
 218       }
 219     } break;
 220
 221     }
 222   }
 223
 224
 225   protected void computeLeafSESEs() {
 226     for( Iterator<FlatSESEEnterNode> itr = allSESEs.iterator();
 227          itr.hasNext();
 228          ) {
 229       FlatSESEEnterNode fsen = itr.next();
 230
 231       boolean hasNoNestedChildren = fsen.getChildren().isEmpty();
 232       boolean hasNoChildrenByCall = !hasChildrenByCall( fsen );
 233
 234       fsen.setIsLeafSESE( hasNoNestedChildren &&
 235                           hasNoChildrenByCall );
 236     }
 237   }
 238
 239
 240   protected boolean hasChildrenByCall(FlatSESEEnterNode fsen) {
 241
 242     boolean hasChildrenByCall=false;
 243
 244     // visit every flat node in SESE body, find method calls that
 245     // may transitively call methods with SESEs enclosed
 246     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 247     flatNodesToVisit.add(fsen);
 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       if (fn.kind() == FKind.FlatCall) {
 259         FlatCall fc = (FlatCall) fn;
 260         MethodDescriptor mdCallee = fc.getMethod();
 261         Set reachable = new HashSet();
 262
 263         reachable.add(mdCallee);
 264         reachable.addAll(callGraph.getAllMethods(mdCallee));
 265
 266         reachable.retainAll(methodsContainingSESEs);
 267
 268         if (!reachable.isEmpty()) {
 269           hasChildrenByCall = true;
 270
 271           Set reachableSESEMethodSet =
 272               callGraph.getFirstReachableMethodContainingSESE(mdCallee, methodsContainingSESEs);
 273
 274           if (methodsContainingSESEs.contains(mdCallee)) {
 275             reachableSESEMethodSet.add(mdCallee);
 276           }
 277
 278           for (Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext();) {
 279             MethodDescriptor md = (MethodDescriptor) iterator.next();
 280             Set<FlatSESEEnterNode> seseSet = md2seseSet.get(md);
 281             if (seseSet != null) {
 282               fsen.addSESEChildren(seseSet);
 283             }
 284           }
 285
 286         }
 287       }
 288
 289       if (fn == fsen.getFlatExit()) {
 290         // don't enqueue any futher nodes
 291         continue;
 292       }
 293
 294       for (int i = 0; i < fn.numNext(); i++) {
 295         FlatNode nn = fn.getNext(i);
 296
 297         if (!visited.contains(nn)) {
 298           flatNodesToVisit.add(nn);
 299         }
 300       }
 301     }
 302
 303     return hasChildrenByCall;
 304   }
 305
 306
 307 }