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
  44   public RBlockRelationAnalysis( State     state,
  45                                  TypeUtil  typeUtil,
  46                                  CallGraph callGraph ) {
  47     this.state     = state;
  48     this.typeUtil  = typeUtil;
  49     this.callGraph = callGraph;
  50
  51     rootSESEs = new HashSet<FlatSESEEnterNode>();
  52     allSESEs  = new HashSet<FlatSESEEnterNode>();
  53
  54     fm2relmap =
  55       new Hashtable< FlatMethod, Hashtable< FlatNode, Stack<FlatSESEEnterNode> > >();
  56
  57
  58     MethodDescriptor mdSourceEntry = typeUtil.getMain();
  59     FlatMethod       fmMain        = state.getMethodFlat( mdSourceEntry );
  60
  61     mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
  62     mainSESE.setfmEnclosing( fmMain );
  63     mainSESE.setmdEnclosing( fmMain.getMethod() );
  64     mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
  65
  66     // add all methods transitively reachable from the
  67     // source's main to set for analysis
  68     Set<MethodDescriptor> descriptorsToAnalyze =
  69       callGraph.getAllMethods( mdSourceEntry );
  70
  71     descriptorsToAnalyze.add( mdSourceEntry );
  72
  73     analyzeMethods( descriptorsToAnalyze );
  74   }
  75
  76
  77   public FlatSESEEnterNode getMainSESE() {
  78     return mainSESE;
  79   }
  80
  81   public Set<FlatSESEEnterNode> getRootSESEs() {
  82     return rootSESEs;
  83   }
  84
  85   public Set<FlatSESEEnterNode> getAllSESEs() {
  86     return allSESEs;
  87   }
  88
  89   public Stack<FlatSESEEnterNode> getRBlockStacks( FlatMethod fm,
  90                                                    FlatNode   fn ) {
  91     if( !fm2relmap.containsKey( fm ) ) {
  92       fm2relmap.put( fm, computeRBlockRelations( fm ) );
  93     }
  94     return fm2relmap.get( fm ).get( fn );
  95   }
  96
  97
  98   protected void analyzeMethods( Set<MethodDescriptor> descriptorsToAnalyze ) {
  99
 100     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 101     while( mdItr.hasNext() ) {
 102       FlatMethod fm = state.getMethodFlat( mdItr.next() );
 103
 104       Hashtable< FlatNode, Stack<FlatSESEEnterNode> > relmap =
 105         computeRBlockRelations( fm );
 106
 107       fm2relmap.put( fm, relmap );
 108     }
 109   }
 110
 111   public Hashtable< FlatNode, Stack<FlatSESEEnterNode> >
 112     computeRBlockRelations( FlatMethod fm ) {
 113
 114     Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
 115       new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
 116
 117     // start from flat method top, visit every node in
 118     // method exactly once, find SESE stack on every
 119     // control path
 120     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 121     flatNodesToVisit.add( fm );
 122
 123     Set<FlatNode> visited = new HashSet<FlatNode>();
 124
 125     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 126     seseStacks.put( fm, seseStackFirst );
 127
 128     while( !flatNodesToVisit.isEmpty() ) {
 129       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 130       FlatNode fn = fnItr.next();
 131
 132       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 133       assert seseStack != null;
 134
 135       flatNodesToVisit.remove( fn );
 136       visited.add( fn );
 137
 138       nodeActions( fn, seseStack, fm );
 139
 140       for( int i = 0; i < fn.numNext(); i++ ) {
 141         FlatNode nn = fn.getNext( i );
 142
 143         if( !visited.contains( nn ) ) {
 144           flatNodesToVisit.add( nn );
 145
 146           // clone stack and send along each control path
 147           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 148         }
 149       }
 150     }
 151
 152     return seseStacks;
 153   }
 154
 155   protected void nodeActions( FlatNode fn,
 156                               Stack<FlatSESEEnterNode> seseStack,
 157                               FlatMethod fm ) {
 158     switch( fn.kind() ) {
 159
 160     case FKind.FlatSESEEnterNode: {
 161       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 162
 163       if( !fsen.getIsCallerSESEplaceholder() ) {
 164         allSESEs.add( fsen );
 165       }
 166
 167       fsen.setfmEnclosing( fm );
 168       fsen.setmdEnclosing( fm.getMethod() );
 169       fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
 170
 171       if( seseStack.empty() ) {
 172         rootSESEs.add( fsen );
 173         fsen.setParent( null );
 174       } else {
 175         seseStack.peek().addChild( fsen );
 176         fsen.setParent( seseStack.peek() );
 177       }
 178
 179       seseStack.push( fsen );
 180     } break;
 181
 182     case FKind.FlatSESEExitNode: {
 183       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 184       assert !seseStack.empty();
 185       FlatSESEEnterNode fsen = seseStack.pop();
 186     } break;
 187
 188     case FKind.FlatReturnNode: {
 189       FlatReturnNode frn = (FlatReturnNode) fn;
 190       if( !seseStack.empty() &&
 191           !seseStack.peek().getIsCallerSESEplaceholder()
 192           ) {
 193         throw new Error( "Error: return statement enclosed within SESE "+
 194                          seseStack.peek().getPrettyIdentifier() );
 195       }
 196     } break;
 197
 198     }
 199   }
 200 }