Robust/src/Analysis/MLP/MLPAnalysis.java

   1 package Analysis.MLP;
   2
   3 import Analysis.CallGraph.*;
   4 import Analysis.OwnershipAnalysis.*;
   5 import IR.*;
   6 import IR.Flat.*;
   7 import java.util.*;
   8 import java.io.*;
   9
  10
  11 public class MLPAnalysis {
  12
  13   // data from the compiler
  14   private State state;
  15   private TypeUtil typeUtil;
  16   private CallGraph callGraph;
  17   private OwnershipAnalysis ownAnalysis;
  18
  19   private Set<FlatSESEEnterNode>   seseRoots;
  20
  21   private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
  22   private Hashtable< FlatNode, VarSrcTokTable           > pointResults;
  23
  24
  25   public MLPAnalysis( State state,
  26                       TypeUtil tu,
  27                       CallGraph callGraph,
  28                       OwnershipAnalysis ownAnalysis
  29                       ) {
  30
  31     double timeStartAnalysis = (double) System.nanoTime();
  32
  33     this.state       = state;
  34     this.typeUtil    = tu;
  35     this.callGraph   = callGraph;
  36     this.ownAnalysis = ownAnalysis;
  37
  38     // initialize analysis data structures
  39     seseRoots    = new HashSet<FlatSESEEnterNode>();
  40     seseStacks   = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
  41     pointResults = new Hashtable< FlatNode, VarSrcTokTable           >();
  42
  43
  44     // run analysis on each method that is actually called
  45     // reachability analysis already computed this so reuse
  46     Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
  47     while( methItr.hasNext() ) {
  48       Descriptor d = methItr.next();
  49
  50       FlatMethod fm;
  51       if( d instanceof MethodDescriptor ) {
  52         fm = state.getMethodFlat( (MethodDescriptor) d);
  53       } else {
  54         assert d instanceof TaskDescriptor;
  55         fm = state.getMethodFlat( (TaskDescriptor) d);
  56       }
  57
  58       // find every SESE from methods that may be called
  59       // and organize them into roots and children
  60       buildForestForward( fm );
  61     }
  62
  63     Iterator<FlatSESEEnterNode> seseItr = seseRoots.iterator();
  64     while( seseItr.hasNext() ) {
  65       FlatSESEEnterNode fsen = seseItr.next();
  66
  67       // do a post-order traversal of the forest so that
  68       // a child is analyzed before a parent.  Start from
  69       // SESE's exit and do a backward data-flow analysis
  70       // for the source of variables
  71       computeReadAndWriteSetBackward( fsen );
  72     }
  73
  74     double timeEndAnalysis = (double) System.nanoTime();
  75     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
  76     String treport = String.format( "The mlp analysis took %.3f sec.", dt );
  77     System.out.println( treport );
  78   }
  79
  80
  81   private void buildForestForward( FlatMethod fm ) {
  82
  83     // start from flat method top, visit every node in
  84     // method exactly once, find SESEs and remember
  85     // roots and child relationships
  86     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
  87     flatNodesToVisit.add( fm );
  88
  89     Set<FlatNode> visited = new HashSet<FlatNode>();
  90
  91     Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
  92     seseStacks.put( fm, seseStackFirst );
  93
  94     while( !flatNodesToVisit.isEmpty() ) {
  95       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
  96       FlatNode fn = fnItr.next();
  97
  98       Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
  99       assert seseStack != null;
 100
 101       //System.out.println( "  considering "+fn );
 102
 103       /*
 104       // only analyze sese exit nodes when all the nodes between
 105       // it and its matching enter have been analyzed
 106       if( !seseStack.empty() &&
 107           fn.equals( seseStack.peek().getFlatExit() ) &&
 108           flatNodesToVisit.size() != 1 ) {
 109         // not ready for this exit node yet, just grab another
 110         fn = fnItr.next();
 111       }
 112       */
 113
 114       flatNodesToVisit.remove( fn );
 115       visited.add( fn );
 116
 117       //System.out.println( "    visiting "+fn );
 118
 119       analyzeFlatNodeForward( fn, seseStack );
 120
 121       // initialize for backward computation in next step
 122       pointResults.put( fn, new VarSrcTokTable() );
 123
 124       for( int i = 0; i < fn.numNext(); i++ ) {
 125         FlatNode nn = fn.getNext( i );
 126
 127         if( !visited.contains( nn ) ) {
 128           flatNodesToVisit.add( nn );
 129
 130           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 131         }
 132       }
 133     }
 134   }
 135
 136
 137   private void computeReadAndWriteSetBackward( FlatSESEEnterNode fsen ) {
 138
 139     // start from an SESE exit, visit nodes in reverse up to
 140     // SESE enter in a fixed-point scheme, where children SESEs
 141     // should already be analyzed and therefore can be skipped
 142     // because child SESE enter node has all necessary info
 143     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 144     flatNodesToVisit.add( fsen.getFlatExit() );
 145
 146     while( !flatNodesToVisit.isEmpty() ) {
 147       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 148       flatNodesToVisit.remove( fn );
 149
 150       VarSrcTokTable prev = pointResults.get( fn );
 151
 152       // merge sets from control flow joins
 153       VarSrcTokTable inUnion = new VarSrcTokTable();
 154       for( int i = 0; i < fn.numNext(); i++ ) {
 155         FlatNode nn = fn.getNext( i );
 156         inUnion.merge( pointResults.get( nn ) );
 157       }
 158
 159       VarSrcTokTable curr = analyzeFlatNodeBackward( fn, inUnion, fsen );
 160
 161       // if a new result, schedule backward nodes for analysis
 162       if( !prev.equals( curr ) ) {
 163
 164         //System.out.println( "  "+fn+":" );
 165         //System.out.println( "    prev ="+prev  );
 166         //System.out.println( "    merge="+merge );
 167         //System.out.println( "    curr ="+curr  );
 168         //System.out.println( "" );
 169
 170         pointResults.put( fn, curr );
 171
 172         // don't flow backwards past SESE enter
 173         if( !fn.equals( fsen ) ) {
 174           for( int i = 0; i < fn.numPrev(); i++ ) {
 175             FlatNode nn = fn.getPrev( i );
 176             flatNodesToVisit.add( nn );
 177           }
 178         }
 179       }
 180     }
 181
 182     if( state.MLPDEBUG ) {
 183       System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
 184       Iterator<VariableSourceToken> tItr = pointResults.get( fsen ).iterator();
 185       while( tItr.hasNext() ) {
 186         System.out.println( "  "+tItr.next() );
 187       }
 188     }
 189   }
 190
 191
 192   private void analyzeFlatNodeForward( FlatNode fn,
 193                                        Stack<FlatSESEEnterNode> seseStack ) {
 194     switch( fn.kind() ) {
 195
 196     case FKind.FlatSESEEnterNode: {
 197       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 198
 199       if( seseStack.empty() ) {
 200         seseRoots.add( fsen );
 201       } else {
 202         seseStack.peek().addChild( fsen );
 203       }
 204       seseStack.push( fsen );
 205       //System.out.println( "  pushed "+fsen );
 206     } break;
 207
 208     case FKind.FlatSESEExitNode: {
 209       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 210
 211       assert !seseStack.empty();
 212       FlatSESEEnterNode fsen = seseStack.pop();
 213       //System.out.println( "  popped "+fsen );
 214     } break;
 215
 216     case FKind.FlatReturnNode: {
 217       FlatReturnNode frn = (FlatReturnNode) fn;
 218       if( !seseStack.empty() ) {
 219         throw new Error( "Error: return statement enclosed within "+seseStack.peek() );
 220       }
 221     } break;
 222
 223     }
 224   }
 225
 226
 227   private VarSrcTokTable analyzeFlatNodeBackward( FlatNode fn,
 228                                                   VarSrcTokTable vstTable,
 229                                                   FlatSESEEnterNode currentSESE ) {
 230     switch( fn.kind() ) {
 231
 232     case FKind.FlatSESEEnterNode: {
 233       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 234     } break;
 235
 236     case FKind.FlatSESEExitNode: {
 237       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 238
 239       //FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 240       //assert fsen == seseStack.pop();
 241       //seseStack.peek().addInVarSet ( fsen.getInVarSet()  );
 242       //seseStack.peek().addOutVarSet( fsen.getOutVarSet() );
 243     } break;
 244
 245     /*
 246     case FKind.FlatMethod: {
 247       FlatMethod fm = (FlatMethod) fn;
 248     } break;
 249     */
 250
 251     case FKind.FlatOpNode:
 252     case FKind.FlatCastNode:
 253     case FKind.FlatFieldNode:
 254     case FKind.FlatSetFieldNode:
 255     case FKind.FlatElementNode:
 256     case FKind.FlatSetElementNode: {
 257
 258       // handle effects of statement in reverse, writes then reads
 259       TempDescriptor [] writeTemps = fn.writesTemps();
 260       for( int i = 0; i < writeTemps.length; ++i ) {
 261         vstTable.remove( writeTemps[i] );
 262       }
 263
 264       TempDescriptor [] readTemps = fn.readsTemps();
 265       for( int i = 0; i < readTemps.length; ++i ) {
 266         vstTable.add( new VariableSourceToken( currentSESE,
 267                                                readTemps[i],
 268                                                new Integer( 0 ) ) );
 269       }
 270     } break;
 271
 272     /*
 273     case FKind.FlatNew: {
 274       FlatNew fnn = (FlatNew) fn;
 275       lhs = fnn.getDst();
 276       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 277         //AllocationSite as = getAllocationSiteFromFlatNewPRIVATE( fnn );
 278       }
 279     } break;
 280     */
 281
 282     /*
 283     case FKind.FlatCall: {
 284       FlatCall fc = (FlatCall) fn;
 285       MethodDescriptor md = fc.getMethod();
 286       FlatMethod flatm = state.getMethodFlat( md );
 287
 288
 289       if( md.isStatic() ) {
 290
 291       } else {
 292         // if the method descriptor is virtual, then there could be a
 293         // set of possible methods that will actually be invoked, so
 294         // find all of them and merge all of their results together
 295         TypeDescriptor typeDesc = fc.getThis().getType();
 296         Set possibleCallees = callGraph.getMethods( md, typeDesc );
 297
 298         Iterator i = possibleCallees.iterator();
 299         while( i.hasNext() ) {
 300           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
 301           FlatMethod pflatm = state.getMethodFlat( possibleMd );
 302
 303         }
 304       }
 305
 306     } break;
 307     */
 308
 309     } // end switch
 310
 311
 312     return vstTable;
 313   }
 314 }