Robust/src/Analysis/Disjoint/DefiniteReachState.java

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