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