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       flatNodesToVisit.remove( fn );
 102       visited.add( fn );
 103
 104       analyzeFlatNodeForward( fn, seseStack );
 105
 106       // initialize for backward computation in next step
 107       //pointResults.put( fn, new VarSrcTokTable() );
 108
 109       for( int i = 0; i < fn.numNext(); i++ ) {
 110         FlatNode nn = fn.getNext( i );
 111
 112         if( !visited.contains( nn ) ) {
 113           flatNodesToVisit.add( nn );
 114
 115           // clone stack and send along each analysis path
 116           seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 117         }
 118       }
 119     }
 120   }
 121
 122
 123   private void computeReadAndWriteSetBackward( FlatSESEEnterNode fsen ) {
 124
 125     // post-order traversal, so do children first
 126     Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
 127     while( childItr.hasNext() ) {
 128       FlatSESEEnterNode fsenChild = childItr.next();
 129       computeReadAndWriteSetBackward( fsenChild );
 130     }
 131
 132
 133     // start from an SESE exit, visit nodes in reverse up to
 134     // SESE enter in a fixed-point scheme, where children SESEs
 135     // should already be analyzed and therefore can be skipped
 136     // because child SESE enter node has all necessary info
 137     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 138     flatNodesToVisit.add( fsen.getFlatExit() );
 139
 140     while( !flatNodesToVisit.isEmpty() ) {
 141       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 142       flatNodesToVisit.remove( fn );
 143
 144       VarSrcTokTable prev = pointResults.get( fn );
 145
 146       // merge sets from control flow joins
 147       VarSrcTokTable inUnion = new VarSrcTokTable();
 148       for( int i = 0; i < fn.numNext(); i++ ) {
 149         FlatNode nn = fn.getNext( i );
 150         inUnion.merge( pointResults.get( nn ) );
 151       }
 152
 153       VarSrcTokTable curr = analyzeFlatNodeBackward( fn, inUnion, fsen );
 154
 155       // if a new result, schedule backward nodes for analysis
 156       if( !curr.equals( prev ) ) {
 157
 158         pointResults.put( fn, curr );
 159
 160         // don't flow backwards past SESE enter
 161         if( !fn.equals( fsen ) ) {
 162           for( int i = 0; i < fn.numPrev(); i++ ) {
 163             FlatNode nn = fn.getPrev( i );
 164             flatNodesToVisit.add( nn );
 165           }
 166         }
 167       }
 168     }
 169
 170     fsen.addInVarSet( pointResults.get( fsen ).get() );
 171
 172     if( state.MLPDEBUG ) {
 173       System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
 174       Iterator<VariableSourceToken> tItr = fsen.getInVarSet().iterator();
 175       while( tItr.hasNext() ) {
 176         System.out.println( "  "+tItr.next() );
 177       }
 178       System.out.println( "and out-set:" );
 179       tItr = fsen.getOutVarSet().iterator();
 180       while( tItr.hasNext() ) {
 181         System.out.println( "  "+tItr.next() );
 182       }
 183       System.out.println( "" );
 184     }
 185   }
 186
 187
 188   private void analyzeFlatNodeForward( FlatNode fn,
 189                                        Stack<FlatSESEEnterNode> seseStack ) {
 190     switch( fn.kind() ) {
 191
 192     case FKind.FlatSESEEnterNode: {
 193       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 194
 195       if( seseStack.empty() ) {
 196         seseRoots.add( fsen );
 197       } else {
 198         seseStack.peek().addChild( fsen );
 199       }
 200       seseStack.push( fsen );
 201     } break;
 202
 203     case FKind.FlatSESEExitNode: {
 204       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 205
 206       assert !seseStack.empty();
 207       FlatSESEEnterNode fsen = seseStack.pop();
 208     } break;
 209
 210     case FKind.FlatReturnNode: {
 211       FlatReturnNode frn = (FlatReturnNode) fn;
 212       if( !seseStack.empty() ) {
 213         throw new Error( "Error: return statement enclosed within "+seseStack.peek() );
 214       }
 215     } break;
 216
 217     }
 218   }
 219
 220
 221   private VarSrcTokTable analyzeFlatNodeBackward( FlatNode fn,
 222                                                   VarSrcTokTable vstTable,
 223                                                   FlatSESEEnterNode currentSESE ) {
 224     switch( fn.kind() ) {
 225
 226     case FKind.FlatSESEEnterNode: {
 227       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 228     } break;
 229
 230     case FKind.FlatSESEExitNode: {
 231       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 232
 233       //FlatSESEEnterNode fsen  = fsexn.getFlatEnter();
 234       //assert fsen == seseStack.pop();
 235       //seseStack.peek().addInVarSet ( fsen.getInVarSet()  );
 236       //seseStack.peek().addOutVarSet( fsen.getOutVarSet() );
 237     } break;
 238
 239     /*
 240     case FKind.FlatMethod: {
 241       FlatMethod fm = (FlatMethod) fn;
 242     } break;
 243     */
 244
 245       /*
 246     case FKind.FlatOpNode:
 247     case FKind.FlatCastNode:
 248     case FKind.FlatFieldNode:
 249     case FKind.FlatSetFieldNode:
 250     case FKind.FlatElementNode:
 251     case FKind.FlatSetElementNode:
 252       */
 253
 254     default: {
 255
 256       // handle effects of statement in reverse, writes then reads
 257       TempDescriptor [] writeTemps = fn.writesTemps();
 258       for( int i = 0; i < writeTemps.length; ++i ) {
 259         vstTable.remove( writeTemps[i] );
 260         currentSESE.addOutVar( new VariableSourceToken( currentSESE,
 261                                                         writeTemps[i],
 262                                                         new Integer( 0 ) ) );
 263       }
 264
 265       TempDescriptor [] readTemps = fn.readsTemps();
 266       for( int i = 0; i < readTemps.length; ++i ) {
 267         vstTable.add( new VariableSourceToken( currentSESE,
 268                                                readTemps[i],
 269                                                new Integer( 0 ) ) );
 270       }
 271     } break;
 272
 273     /*
 274     case FKind.FlatNew: {
 275       FlatNew fnn = (FlatNew) fn;
 276       lhs = fnn.getDst();
 277       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 278         //AllocationSite as = getAllocationSiteFromFlatNewPRIVATE( fnn );
 279       }
 280     } break;
 281     */
 282
 283     /*
 284     case FKind.FlatCall: {
 285       FlatCall fc = (FlatCall) fn;
 286       MethodDescriptor md = fc.getMethod();
 287       FlatMethod flatm = state.getMethodFlat( md );
 288
 289
 290       if( md.isStatic() ) {
 291
 292       } else {
 293         // if the method descriptor is virtual, then there could be a
 294         // set of possible methods that will actually be invoked, so
 295         // find all of them and merge all of their results together
 296         TypeDescriptor typeDesc = fc.getThis().getType();
 297         Set possibleCallees = callGraph.getMethods( md, typeDesc );
 298
 299         Iterator i = possibleCallees.iterator();
 300         while( i.hasNext() ) {
 301           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
 302           FlatMethod pflatm = state.getMethodFlat( possibleMd );
 303
 304         }
 305       }
 306
 307     } break;
 308     */
 309
 310     } // end switch
 311
 312
 313     return vstTable;
 314   }
 315 }