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