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   public boolean isAlreadyReachable( TempDescriptor a,
  38                                      TempDescriptor b,
  39                                      FlatNode fn ) {
  40     return makeIn( fn ).isAlreadyReachable( a, b );
  41   }
  42
  43
  44   public Set<DefiniteReachState.FdEntry> edgesToElidePropagation( TempDescriptor x,
  45                                                                   TempDescriptor y,
  46                                                                   FlatNode fn ) {
  47     return makeIn( fn ).edgesToElidePropagation( x, y );
  48   }
  49
  50
  51
  52   private void addPartialResult( FlatNode fn, DefiniteReachState state ) {
  53     fn2state.put( fn, state );
  54     fnHasPartial.add( fn );
  55   }
  56
  57
  58   public void methodEntry( FlatNode fn,
  59                            Set<TempDescriptor> parameters ) {
  60     // this should be called exactly once at the beginning
  61     // of any intraprocedural pass, so clear partial result
  62     // set
  63     fnHasPartial.clear();
  64
  65     DefiniteReachState state = makeIn( fn );
  66     state.methodEntry( parameters );
  67     addPartialResult( fn, state );
  68   }
  69
  70   public void copy( FlatNode fn,
  71                     TempDescriptor x,
  72                     TempDescriptor y ) {
  73     DefiniteReachState state = makeIn( fn );
  74     state.copy( x, y );
  75     addPartialResult( fn, state );
  76   }
  77
  78   public void load( FlatNode fn,
  79                     TempDescriptor  x,
  80                     TempDescriptor  y,
  81                     FieldDescriptor f,
  82                     Set<EdgeKey> edgeKeysForLoad ) {
  83
  84     DefiniteReachState state = makeIn( fn );
  85     state.load( x, y, f, edgeKeysForLoad );
  86     addPartialResult( fn, state );
  87   }
  88
  89   public void store( FlatNode fn,
  90                      TempDescriptor  x,
  91                      FieldDescriptor f,
  92                      TempDescriptor  y,
  93                      Set<EdgeKey> edgeKeysRemoved,
  94                      Set<EdgeKey> edgeKeysAdded ) {
  95
  96     DefiniteReachState state = makeIn( fn );
  97     state.store( x, f, y, edgeKeysRemoved, edgeKeysAdded );
  98     addPartialResult( fn, state );
  99   }
 100
 101   public void newObject( FlatNode fn,
 102                          TempDescriptor x ) {
 103     DefiniteReachState state = makeIn( fn );
 104     state.newObject( x );
 105     addPartialResult( fn, state );
 106   }
 107
 108   public void methodCall( FlatNode fn,
 109                           TempDescriptor retVal ) {
 110     DefiniteReachState state = makeIn( fn );
 111     if( retVal != null ) {
 112       state.methodCall( retVal );
 113     }
 114     addPartialResult( fn, state );
 115   }
 116
 117   public void otherStatement( FlatNode fn ) {
 118     addPartialResult( fn, makeIn( fn ) );
 119   }
 120
 121
 122   public void writeState( FlatNode fn, String outputName ) {
 123     makeIn( fn ).writeState( outputName );
 124   }
 125
 126
 127   // get the current state for just after the given
 128   // program point
 129   public DefiniteReachState get( FlatNode fn ) {
 130     DefiniteReachState state = fn2state.get( fn );
 131     if( state == null ) {
 132       state = new DefiniteReachState();
 133       fn2state.put( fn, state );
 134     }
 135     return state;
 136   }
 137
 138
 139   // get the current state for the program point just
 140   // before the given program point by merging the out
 141   // states of the predecessor statements
 142   public DefiniteReachState makeIn( FlatNode fn ) {
 143
 144     if( pm.numPrev( fn ) == 0 ) {
 145       return new DefiniteReachState();
 146     }
 147
 148     DefiniteReachState stateIn = null;
 149
 150     for( int i = 0; i < pm.numPrev( fn ); ++i ) {
 151       if( fnHasPartial.contains( pm.getPrev( fn, i ) ) ) {
 152         if( stateIn == null ) {
 153           // duplicate the first partial result we find
 154           stateIn = new DefiniteReachState( get( pm.getPrev( fn, i ) ) );
 155         } else {
 156           // merge other partial results into the rest
 157           stateIn.merge( get( pm.getPrev( fn, i ) ) );
 158         }
 159       }
 160     }
 161
 162     // at least one predecessor was analyzed before this
 163     assert( stateIn != null );
 164     return stateIn;
 165   }
 166 }