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   public void loadR( TempDescriptor x,
 225                      TempDescriptor y,
 226                      FieldDescriptor f,
 227                      Set<EdgeKey> edgeKeysForLoad ) {
 228     // consider that x and y can be the same, so do the
 229     // parts of the update in the right order:
 230
 231     // first get all info for update
 232     MultiKey keyY = MultiKey.factory( y );
 233     Map<MultiKey, Object> mapY0 = R.get( viewR0, keyY );
 234
 235     // then remove anything
 236     MultiKey keyX = MultiKey.factory( x );
 237     R.remove( viewR0, keyX );
 238     R.remove( viewR1, keyX );
 239
 240     // then insert new stuff
 241     for( EdgeKey e : edgeKeysForLoad ) {
 242       R.put( MultiKey.factory( x, y, e ), MultiViewMap.dummyValue );
 243
 244       for( MultiKey fullKeyY : mapY0.keySet() ) {
 245         R.put( MultiKey.factory( x,
 246                                  fullKeyY.get( 1 ),
 247                                  e ),
 248                MultiViewMap.dummyValue );
 249
 250         R.put( MultiKey.factory( x,
 251                                  fullKeyY.get( 1 ),
 252                                  fullKeyY.get( 2 ) ),
 253                MultiViewMap.dummyValue );
 254       }
 255     }
 256   }
 257
 258   public void storeR( TempDescriptor x,
 259                       FieldDescriptor f,
 260                       TempDescriptor y,
 261                       Set<EdgeKey> edgeKeysRemoved,
 262                       Set<EdgeKey> edgeKeysAdded ) {
 263
 264     for( EdgeKey edgeKeyWZ : edgeKeysRemoved ) {
 265       R.remove( viewR2, MultiKey.factory( edgeKeyWZ ) );
 266     }
 267
 268     for( EdgeKey edgeKeyXY : edgeKeysAdded ) {
 269       R.put( MultiKey.factory( y, x, edgeKeyXY ), MultiViewMap.dummyValue );
 270     }
 271   }
 272
 273   public void newObjectR( TempDescriptor x ) {
 274     MultiKey keyX = MultiKey.factory( x );
 275     R.remove( viewR0, keyX );
 276     R.remove( viewR1, keyX );
 277   }
 278
 279   public void methodCallR( TempDescriptor retVal ) {
 280     MultiKey keyRetVal = MultiKey.factory( retVal );
 281     R.remove( viewR0, keyRetVal );
 282     R.remove( viewR1, keyRetVal );
 283   }
 284
 285   public void mergeR( DefiniteReachState that ) {
 286     for( MultiKey key : this.R.get().keySet() ) {
 287       if( that.R.get( viewRfull, key ).isEmpty() ) {
 288         this.R.remove( viewRfull, key );
 289       }
 290     }
 291   }
 292
 293
 294
 295
 296   ///////////////////////////////////////////////////////////
 297   //
 298   //  This is WRONG
 299   //
 300   //  It definitely tests the current R as well as Rs
 301   //
 302   //  but also be careful what null means, is it actually
 303   //  equivalent to UNKOWN?  I'd rather put nothing, meaning
 304   //  we have to do an analysis pass over all the incoming edges
 305   //  before there is a sensical answer.  I think...
 306   private void mergeRs( DefiniteReachState that ) {
 307     // merge "that" into "this" and leave "that" unchanged
 308     //Set<TempDescriptor> allVars = new HashSet<TempDescriptor>();
 309     //allVars.addAll( this.Rs.keySet() );
 310     //allVars.addAll( that.Rs.keySet() );
 311     //for( TempDescriptor x : allVars ) {
 312     //  DefReachKnown vThis = this.Rs.get( x );
 313     //  DefReachKnown vThat = that.Rs.get( x );
 314     //  if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) &&
 315     //      vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) {
 316     //    this.Rs.put( x, DefReachKnown.KNOWN );
 317     //  } else {
 318     //    this.Rs.put( x, DefReachKnown.UNKNOWN );
 319     //  }
 320     //}
 321   }
 322
 323
 324
 325   public boolean equals( Object o ) {
 326     if( this == o ) {
 327       return true;
 328     }
 329     if( o == null ) {
 330       return false;
 331     }
 332     if( !(o instanceof DefiniteReachState) ) {
 333       return false;
 334     }
 335     DefiniteReachState that = (DefiniteReachState) o;
 336
 337     assert( false );
 338     return false;
 339   }
 340
 341
 342   public int hashCode() {
 343     assert( false );
 344     return 0;
 345   }
 346
 347
 348   public void writeState( String outputName ) {
 349     try {
 350       BufferedWriter bw = new BufferedWriter( new FileWriter( "defReach-"+outputName+".txt" ) );
 351       bw.write( this.toString() );
 352       bw.close();
 353     } catch( IOException e ) {
 354       System.out.println( "ERROR writing definite reachability state:\n  "+e );
 355     }
 356   }
 357
 358
 359   public String toString() {
 360     StringBuilder s = new StringBuilder();
 361
 362     s.append( "R = {\n" );
 363     s.append( R.toString( 2 ) );
 364     s.append( "}\n" );
 365
 366     //s.append( "R_s = {" );
 367     //for( TempDescriptor x : Rs.keySet() ) {
 368     //  s.append( "  "+x+"->"+Rs.get( x ) );
 369     //}
 370     //s.append( "}" );
 371     return s.toString();
 372   }
 373 }