Robust/src/Analysis/Disjoint/DefiniteReachState.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 DefiniteReachState {
  11
  12   // R
  13   //
  14   // Maps two variables to an edge (x, y, e) to an unused value when the
  15   // object of x is already reachable from the object of y, and the
  16   // set of edges conservatively gives the path.
  17   // NOTE: Use EdgeKey instead of edges because this analysis's
  18   // scope is beyond the scope of a single reach graph.
  19   private static MultiViewMapBuilder<Object> RBuilder;
  20   private static BitSet viewR0;
  21   private static BitSet viewR1;
  22   private static BitSet viewR01;
  23   private MultiViewMap<Object> R;
  24
  25   // Rs
  26   //
  27   // Tracks whether the analysis must know the definite reachability
  28   // information of a given variable.
  29   //private enum DefReachKnown {
  30   //  UNKNOWN,
  31   //  KNOWN,
  32   //}
  33   //private Map<TempDescriptor, DefReachKnown> Rs;
  34
  35
  36   // Fu (upstream)
  37   //
  38   // Maps a variable that points to object o0 to the
  39   // set of variables that point to objects o1...oN
  40   // that have a reference to o0.
  41   //private static MultiViewMapBuilder<Object> FuBuilder;
  42   //private static BitSet viewFu0;
  43   //private static BitSet viewFu1;
  44   //private MultiViewMap<Object> Fu;
  45
  46
  47   // Fd (downstream)
  48
  49
  50
  51
  52
  53
  54   // call before instantiating this class
  55   static public void initBuilders() {
  56     RBuilder =
  57       new MultiViewMapBuilder<Object>( new Class[] {
  58                                          TempDescriptor.class,
  59                                          TempDescriptor.class,
  60                                          EdgeKey.class },
  61                                        new JoinOpNop() );
  62     viewR0  = RBuilder.addPartialView( 0 );
  63     viewR1  = RBuilder.addPartialView( 1 );
  64     viewR01 = RBuilder.addPartialView( 0, 1 );
  65     RBuilder.setCheckTypes( true );
  66     RBuilder.setCheckConsistency( true );
  67
  68     //FuBuilder =
  69     //  new MultiViewMapBuilder<Object>( new Class[] {
  70     //                                     TempDescriptor.class,
  71     //                                     DefReachFuVal.class},
  72     //                                   new JoinOpNop() );
  73     //viewFu0 = FuBuilder.addPartialView( 0 );
  74     //viewFu1 = FuBuilder.addPartialView( 1 );
  75     //FuBuilder.setCheckTypes( true );
  76     //FuBuilder.setCheckConsistency( true );
  77   }
  78
  79
  80
  81
  82
  83   public DefiniteReachState() {
  84     R = RBuilder.build();
  85     //Rs = new HashMap<TempDescriptor, DefReachKnown>();
  86     //Fu = FuBuilder.build();
  87   }
  88
  89
  90   public void methodEntry( Set<TempDescriptor> parameters ) {
  91     methodEntryR( parameters );
  92
  93     //Rs.clear();
  94     //for( TempDescriptor p : parameters ) {
  95     //  Rs.put( p, DefReachKnown.UNKNOWN );
  96     //}
  97     //
  98     //Fu = FuBuilder.build();
  99   }
 100
 101   public void copy( TempDescriptor x,
 102                     TempDescriptor y ) {
 103     copyR( x, y );
 104
 105     // Rs' := (Rs - <x,*>) U {<x,v> | <y,v> in Rs}
 106     //DefReachKnown valRs = Rs.get( y );
 107     //assert( valRs != null );
 108     //Rs.put( x, valRs );
 109
 110     // Fu' := (Fu - <x, *> - <*, x>) U
 111     //        {<x,v> | <y,v> in Fu} U
 112     //        {<v,x> | <v,y> in Fu} U
 113     //        {<z, unknown> | <z,<x>> in Fu}
 114     //Fu.remove( viewFu0, MultiKey.factory( x ) );
 115     //Fu.remove( viewFu1, MultiKey.factory( x ) );
 116     //for( MultiKey key : Fu.get( viewFu0, MultiKey.factory( y ) ).keySet() ) {
 117     //  DefReachFuVal val = (DefReachFuVal) key.get( 1 );
 118     //  Fu.put( MultiKey.factory( x, val ), dummy );
 119     //}
 120     //for( MultiKey key : Fu.get( viewFu1, MultiKey.factory( y ) ).keySet() ) {
 121     //  TempDescriptor v = (TempDescriptor) key.get( 0 );
 122     //  Fu.put( MultiKey.factory( v, DefReachFuVal.factory( x ) ), dummy );
 123     //}
 124     //for( MultiKey key :
 125     //       Fu.get( viewFu1,
 126     //               MultiKey.factory( DefReachFuVal.factory( DefReachFuVal.Val.UNKNOWN ) )
 127     //               ).keySet()
 128     //     ) {
 129     //  TempDescriptor z = (TempDescriptor) key.get( 0 );
 130     //  Fu.put( MultiKey.factory( z, DefReachFuVal.factory( x ) ), dummy );
 131     //}
 132   }
 133
 134   public void load( TempDescriptor x,
 135                     TempDescriptor y,
 136                     FieldDescriptor f,
 137                     Set<EdgeKey> edgeKeysForLoad ) {
 138
 139     loadR( x, y, f, edgeKeysForLoad );
 140     // Rs' := (Rs - <x,*>) U {<x, unknown>}
 141     //Rs.put( x, DefReachKnown.UNKNOWN );
 142   }
 143
 144   public void store( TempDescriptor x,
 145                      FieldDescriptor f,
 146                      TempDescriptor y,
 147                      Set<EdgeKey> edgeKeysRemoved,
 148                      Set<EdgeKey> edgeKeysAdded ) {
 149
 150     storeR( x, f, y, edgeKeysRemoved, edgeKeysAdded );
 151     // Rs' := Rs
 152   }
 153
 154   public void newObject( TempDescriptor x ) {
 155     newObjectR( x );
 156
 157     // Rs' := (Rs - <x,*>) U {<x, new>}
 158     //Rs.put( x, DefReachKnown.KNOWN );
 159
 160   }
 161
 162   public void methodCall( TempDescriptor retVal ) {
 163     methodCallR( retVal );
 164
 165     // Rs' := (Rs - <x,*>) U {<x, unknown>}
 166     //Rs.put( x, DefReachKnown.UNKNOWN );
 167   }
 168
 169   public void merge( DefiniteReachState that ) {
 170     mergeR( that );
 171
 172     // Rs' := <x, new> iff in all incoming edges, otherwie <x, unknown>
 173     //mergeRs( that );
 174   }
 175
 176
 177
 178
 179
 180
 181   public void methodEntryR( Set<TempDescriptor> parameters ) {
 182     R.clear();
 183   }
 184
 185   public void copyR( TempDescriptor x,
 186                      TempDescriptor y ) {
 187     // consider that x and y can be the same, so do the
 188     // parts of the update in the right order:
 189
 190     // first get all info for update
 191     MultiKey keyY = MultiKey.factory( y );
 192     Map<MultiKey, Object> mapY0 = R.get( viewR0, keyY );
 193     Map<MultiKey, Object> mapY1 = R.get( viewR1, keyY );
 194
 195     // then remove anything
 196     MultiKey keyX = MultiKey.factory( x );
 197     R.remove( viewR0, keyX );
 198     R.remove( viewR1, keyX );
 199
 200     // then insert new stuff
 201     for( MultiKey fullKeyY : mapY0.keySet() ) {
 202       MultiKey fullKeyX = MultiKey.factory( x,
 203                                             fullKeyY.get( 1 ),
 204                                             fullKeyY.get( 2 ) );
 205       R.put( fullKeyX, MultiViewMap.dummyValue );
 206     }
 207     for( MultiKey fullKeyY : mapY1.keySet() ) {
 208       MultiKey fullKeyX = MultiKey.factory( fullKeyY.get( 0 ),
 209                                             x,
 210                                             fullKeyY.get( 2 ) );
 211       R.put( fullKeyX, MultiViewMap.dummyValue );
 212     }
 213   }
 214
 215   public void loadR( TempDescriptor x,
 216                      TempDescriptor y,
 217                      FieldDescriptor f,
 218                      Set<EdgeKey> edgeKeysForLoad ) {
 219     // consider that x and y can be the same, so do the
 220     // parts of the update in the right order:
 221
 222     // first get all info for update
 223     MultiKey keyY = MultiKey.factory( y );
 224     Map<MultiKey, Object> mapY0 = R.get( viewR0, keyY );
 225
 226     // then remove anything
 227     MultiKey keyX = MultiKey.factory( x );
 228     R.remove( viewR0, keyX );
 229     R.remove( viewR1, keyX );
 230
 231     // then insert new stuff
 232     for( EdgeKey e : edgeKeysForLoad ) {
 233       R.put( MultiKey.factory( x, y, e ), MultiViewMap.dummyValue );
 234
 235       for( MultiKey fullKeyY : mapY0.keySet() ) {
 236         R.put( MultiKey.factory( x,
 237                                  fullKeyY.get( 1 ),
 238                                  e ),
 239                MultiViewMap.dummyValue );
 240
 241         R.put( MultiKey.factory( x,
 242                                  fullKeyY.get( 1 ),
 243                                  fullKeyY.get( 2 ) ),
 244                MultiViewMap.dummyValue );
 245       }
 246     }
 247   }
 248
 249   public void storeR( TempDescriptor x,
 250                       FieldDescriptor f,
 251                       TempDescriptor y,
 252                       Set<EdgeKey> edgeKeysRemoved,
 253                       Set<EdgeKey> edgeKeysAdded ) {
 254     // I think this should be if there is ANY <w,z>->e' IN Eremove, then kill all <w,z>
 255     // R' := (R - {<w,z>->e | <w,z>->e in R, A<w,z>->e' in R, e' notin Eremove}) U
 256     //       {<y,x>->e | e in E(x) x {f} x E(y)}
 257     // R' = new Map(R)
 258     // R'.remove(?); some e's...
 259     // R'.put(<y,x>, E(x) x {f} x E(y));
 260   }
 261
 262   public void newObjectR( TempDescriptor x ) {
 263     // R' := (R - <x,*> - <*,x>)
 264     // R' = new Map(R)
 265     // R'.remove(view0, x);
 266     // R'.remove(view1, x);
 267   }
 268
 269   public void methodCallR( TempDescriptor retVal ) {
 270     // R' := (R - <x,*> - <*,x>)
 271     // R' = new Map(R)
 272     // R'.remove(view0, x);
 273     // R'.remove(view1, x);
 274   }
 275
 276   public void mergeR( DefiniteReachState that ) {
 277     // R' := <x,y>->e iff its in all incoming edges
 278   }
 279
 280
 281
 282
 283   ///////////////////////////////////////////////////////////
 284   //
 285   //  This is WRONG
 286   //
 287   //  It definitely tests the current R as well as Rs
 288   //
 289   //  but also be careful what null means, is it actually
 290   //  equivalent to UNKOWN?  I'd rather put nothing, meaning
 291   //  we have to do an analysis pass over all the incoming edges
 292   //  before there is a sensical answer.  I think...
 293   private void mergeRs( DefiniteReachState that ) {
 294     // merge "that" into "this" and leave "that" unchanged
 295     //Set<TempDescriptor> allVars = new HashSet<TempDescriptor>();
 296     //allVars.addAll( this.Rs.keySet() );
 297     //allVars.addAll( that.Rs.keySet() );
 298     //for( TempDescriptor x : allVars ) {
 299     //  DefReachKnown vThis = this.Rs.get( x );
 300     //  DefReachKnown vThat = that.Rs.get( x );
 301     //  if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) &&
 302     //      vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) {
 303     //    this.Rs.put( x, DefReachKnown.KNOWN );
 304     //  } else {
 305     //    this.Rs.put( x, DefReachKnown.UNKNOWN );
 306     //  }
 307     //}
 308   }
 309
 310
 311
 312   public boolean equals( Object o ) {
 313     if( this == o ) {
 314       return true;
 315     }
 316     if( o == null ) {
 317       return false;
 318     }
 319     if( !(o instanceof DefiniteReachState) ) {
 320       return false;
 321     }
 322     DefiniteReachState that = (DefiniteReachState) o;
 323
 324     assert( false );
 325     return false;
 326   }
 327
 328
 329   public int hashCode() {
 330     assert( false );
 331     return 0;
 332   }
 333
 334
 335
 336   public String toString() {
 337     StringBuilder s = new StringBuilder( "R_s = {" );
 338     //for( TempDescriptor x : Rs.keySet() ) {
 339     //  s.append( "  "+x+"->"+Rs.get( x ) );
 340     //}
 341     //s.append( "}" );
 342     return s.toString();
 343   }
 344 }