Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java

   1 package Analysis.Disjoint;
   2
   3 import java.util.*;
   4
   5 import IR.*;
   6 import IR.Flat.*;
   7 import Util.*;
   8
   9
  10 public class DefiniteReachAnalysis {
  11
  12   // keep a state of definite reachability analysis for
  13   // every program point
  14   private Map<FlatNode, DefiniteReachState> fn2state;
  15
  16   // even though the above map has a set of nodes that
  17   // have been analyzed, we need a per-intra pass set
  18   // of nodes that have been analyzed, too, to filter
  19   // out nodes that do not have a partial result yet
  20   private Set<FlatNode> fnHasPartial;
  21
  22
  23   private static PointerMethod pm;
  24
  25
  26   public DefiniteReachAnalysis( PointerMethod pm ) {
  27     // a class-wide initialization
  28     DefiniteReachState.initBuilders();
  29
  30     DefiniteReachAnalysis.pm = pm;
  31
  32     fn2state     = new HashMap<FlatNode, DefiniteReachState>();
  33     fnHasPartial = new HashSet<FlatNode>();
  34   }
  35
  36
  37   private void addPartialResult( FlatNode fn, DefiniteReachState state ) {
  38     fn2state.put( fn, state );
  39     fnHasPartial.add( fn );
  40   }
  41
  42
  43   public void methodEntry( FlatNode fn,
  44                            Set<TempDescriptor> parameters ) {
  45     // this should be called exactly once at the beginning
  46     // of any intraprocedural pass, so clear partial result
  47     // set
  48     fnHasPartial.clear();
  49
  50     DefiniteReachState state = makeIn( fn );
  51     state.methodEntry( parameters );
  52     addPartialResult( fn, state );
  53   }
  54
  55   public void copy( FlatNode fn,
  56                     TempDescriptor x,
  57                     TempDescriptor y ) {
  58     DefiniteReachState state = makeIn( fn );
  59     state.copy( x, y );
  60     addPartialResult( fn, state );
  61   }
  62
  63   public void load( FlatNode fn,
  64                     TempDescriptor  x,
  65                     TempDescriptor  y,
  66                     FieldDescriptor f,
  67                     Set<EdgeKey> edgeKeysForLoad ) {
  68
  69     DefiniteReachState state = makeIn( fn );
  70     state.load( x, y, f, edgeKeysForLoad );
  71     addPartialResult( fn, state );
  72   }
  73
  74   public void store( FlatNode fn,
  75                      TempDescriptor  x,
  76                      FieldDescriptor f,
  77                      TempDescriptor  y,
  78                      Set<EdgeKey> edgeKeysRemoved,
  79                      Set<EdgeKey> edgeKeysAdded ) {
  80
  81     DefiniteReachState state = makeIn( fn );
  82     state.store( x, f, y, edgeKeysRemoved, edgeKeysAdded );
  83     addPartialResult( fn, state );
  84   }
  85
  86   public void newObject( FlatNode fn,
  87                          TempDescriptor x ) {
  88     DefiniteReachState state = makeIn( fn );
  89     state.newObject( x );
  90     addPartialResult( fn, state );
  91   }
  92
  93   public void methodCall( FlatNode fn,
  94                           TempDescriptor retVal ) {
  95     DefiniteReachState state = makeIn( fn );
  96     if( retVal != null ) {
  97       state.methodCall( retVal );
  98     }
  99     addPartialResult( fn, state );
 100   }
 101
 102   public void otherStatement( FlatNode fn ) {
 103     addPartialResult( fn, makeIn( fn ) );
 104   }
 105
 106
 107   public void writeState( FlatNode fn, String outputName ) {
 108     makeIn( fn ).writeState( outputName );
 109   }
 110
 111
 112   // get the current state for just after the given
 113   // program point
 114   public DefiniteReachState get( FlatNode fn ) {
 115     DefiniteReachState state = fn2state.get( fn );
 116     if( state == null ) {
 117       state = new DefiniteReachState();
 118       fn2state.put( fn, state );
 119     }
 120     return state;
 121   }
 122
 123
 124   // get the current state for the program point just
 125   // before the given program point by merging the out
 126   // states of the predecessor statements
 127   public DefiniteReachState makeIn( FlatNode fn ) {
 128
 129     if( pm.numPrev( fn ) == 0 ) {
 130       return new DefiniteReachState();
 131     }
 132
 133     DefiniteReachState stateIn = null;
 134
 135     for( int i = 0; i < pm.numPrev( fn ); ++i ) {
 136       if( fnHasPartial.contains( pm.getPrev( fn, i ) ) ) {
 137         if( stateIn == null ) {
 138           // duplicate the first partial result we find
 139           stateIn = new DefiniteReachState( get( pm.getPrev( fn, i ) ) );
 140         } else {
 141           // merge other partial results into the rest
 142           stateIn.merge( get( pm.getPrev( fn, i ) ) );
 143         }
 144       }
 145     }
 146
 147     // at least one predecessor was analyzed before this
 148     assert( stateIn != null );
 149     return stateIn;
 150   }
 151 }