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