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 (field 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 (field downstream)
  51   //
  52   // Entries <x, f, y> mean x.f points directly at what
  53   // y points at.
  54   public class FdEntry {
  55     TempDescriptor  y;
  56     FieldDescriptor f0;
  57     TempDescriptor  z;
  58     public FdEntry( TempDescriptor  y,
  59                     FieldDescriptor f0,
  60                     TempDescriptor  z ) {
  61       this.y  = y;
  62       this.f0 = f0;
  63       this.z  = z;
  64     }
  65   }
  66   private static MultiViewMapBuilder<Object> FdBuilder;
  67   private static BitSet viewFd0;
  68   private static BitSet viewFd2;
  69   private MultiViewMap<Object> Fd;
  70
  71
  72
  73
  74
  75   // call before instantiating this class
  76   static public void initBuilders() {
  77     RBuilder =
  78       new MultiViewMapBuilder<Object>( new Class[] {
  79                                          TempDescriptor.class,
  80                                          TempDescriptor.class,
  81                                          EdgeKey.class },
  82                                        new JoinOpNop() );
  83     viewRfull = RBuilder.getFullView();
  84     viewR0    = RBuilder.addPartialView( 0 );
  85     viewR1    = RBuilder.addPartialView( 1 );
  86     viewR2    = RBuilder.addPartialView( 2 );
  87     viewR01   = RBuilder.addPartialView( 0, 1 );
  88     RBuilder.setCheckTypes( true );
  89     RBuilder.setCheckConsistency( true );
  90
  91     //FuBuilder =
  92     //  new MultiViewMapBuilder<Object>( new Class[] {
  93     //                                     TempDescriptor.class,
  94     //                                     DefReachFuVal.class},
  95     //                                   new JoinOpNop() );
  96     //viewFu0 = FuBuilder.addPartialView( 0 );
  97     //viewFu1 = FuBuilder.addPartialView( 1 );
  98     //FuBuilder.setCheckTypes( true );
  99     //FuBuilder.setCheckConsistency( true );
 100
 101     FdBuilder =
 102       new MultiViewMapBuilder<Object>( new Class[] {
 103                                          TempDescriptor.class,
 104                                          FieldDescriptor.class,
 105                                          TempDescriptor.class},
 106                                        new JoinOpNop() );
 107     viewFd0 = FdBuilder.addPartialView( 0 );
 108     viewFd2 = FdBuilder.addPartialView( 2 );
 109     FdBuilder.setCheckTypes( true );
 110     FdBuilder.setCheckConsistency( true );
 111   }
 112
 113
 114
 115   public DefiniteReachState( DefiniteReachState toCopy ) {
 116     this.R  = toCopy.R.clone( RBuilder );
 117     this.Rs = new HashMap<TempDescriptor, DefReachKnown>( toCopy.Rs );
 118     this.Fd = toCopy.Fd.clone( FdBuilder );
 119   }
 120
 121
 122   public DefiniteReachState() {
 123     R = RBuilder.build();
 124     Rs = new HashMap<TempDescriptor, DefReachKnown>();
 125     //Fu = FuBuilder.build();
 126     Fd = FdBuilder.build();
 127   }
 128
 129
 130
 131   public boolean isAlreadyReachable( TempDescriptor a,
 132                                      TempDescriptor b ) {
 133     return !R.get( viewR01, MultiKey.factory( a, b ) ).isEmpty();
 134   }
 135
 136
 137   public Set<FdEntry> edgesToElidePropagation( TempDescriptor x,
 138                                                TempDescriptor y ) {
 139     // return the set of edges that definite reach analysis tells
 140     // us we can elide propagating reach info across during the
 141     // store: x.f = y
 142
 143     Set<FdEntry> out = new HashSet<FdEntry>();
 144
 145     // we have to know something about y
 146     DefReachKnown known = Rs.get( y );
 147     if( known == null || known == DefReachKnown.UNKNOWN ) {
 148       return out;
 149     }
 150
 151     // find all 'y points at' entries in Fd
 152     MultiKey keyY = MultiKey.factory( y );
 153     Map<MultiKey, Object> mapY0 = Fd.get( viewFd0, keyY );
 154
 155     for( MultiKey fullKeyY : mapY0.keySet() ) {
 156       // if y.f0 points at z, and z is already reachable from x,
 157       // include the edge y.f0->z
 158       FieldDescriptor f0 = (FieldDescriptor) fullKeyY.get( 1 );
 159       TempDescriptor  z  = (TempDescriptor)  fullKeyY.get( 2 );
 160
 161       if( isAlreadyReachable( z, x ) ) {
 162         out.add( new FdEntry( y, f0, z ) );
 163       }
 164     }
 165
 166     return out;
 167   }
 168
 169
 170
 171
 172   public void methodEntry( Set<TempDescriptor> parameters ) {
 173     methodEntryR ( parameters );
 174     methodEntryRs( parameters );
 175     methodEntryFd( parameters );
 176   }
 177
 178   public void copy( TempDescriptor x,
 179                     TempDescriptor y ) {
 180     copyR ( x, y );
 181     copyRs( x, y );
 182     copyFd( x, y );
 183
 184     // Fu' := (Fu - <x, *> - <*, x>) U
 185     //        {<x,v> | <y,v> in Fu} U
 186     //        {<v,x> | <v,y> in Fu} U
 187     //        {<z, unknown> | <z,<x>> in Fu}
 188     //Fu.remove( viewFu0, MultiKey.factory( x ) );
 189     //Fu.remove( viewFu1, MultiKey.factory( x ) );
 190     //for( MultiKey key : Fu.get( viewFu0, MultiKey.factory( y ) ).keySet() ) {
 191     //  DefReachFuVal val = (DefReachFuVal) key.get( 1 );
 192     //  Fu.put( MultiKey.factory( x, val ), dummy );
 193     //}
 194     //for( MultiKey key : Fu.get( viewFu1, MultiKey.factory( y ) ).keySet() ) {
 195     //  TempDescriptor v = (TempDescriptor) key.get( 0 );
 196     //  Fu.put( MultiKey.factory( v, DefReachFuVal.factory( x ) ), dummy );
 197     //}
 198     //for( MultiKey key :
 199     //       Fu.get( viewFu1,
 200     //               MultiKey.factory( DefReachFuVal.factory( DefReachFuVal.Val.UNKNOWN ) )
 201     //               ).keySet()
 202     //     ) {
 203     //  TempDescriptor z = (TempDescriptor) key.get( 0 );
 204     //  Fu.put( MultiKey.factory( z, DefReachFuVal.factory( x ) ), dummy );
 205     //}
 206   }
 207
 208   public void load( TempDescriptor x,
 209                     TempDescriptor y,
 210                     FieldDescriptor f,
 211                     Set<EdgeKey> edgeKeysForLoad ) {
 212
 213     loadR ( x, y, f, edgeKeysForLoad );
 214     loadRs( x, y, f, edgeKeysForLoad );
 215     loadFd( x, y, f, edgeKeysForLoad );
 216   }
 217
 218   public void store( TempDescriptor x,
 219                      FieldDescriptor f,
 220                      TempDescriptor y,
 221                      Set<EdgeKey> edgeKeysRemoved,
 222                      Set<EdgeKey> edgeKeysAdded ) {
 223
 224     storeR ( x, f, y, edgeKeysRemoved, edgeKeysAdded );
 225     storeRs( x, f, y, edgeKeysRemoved, edgeKeysAdded );
 226     storeFd( x, f, y, edgeKeysRemoved, edgeKeysAdded );
 227   }
 228
 229   public void newObject( TempDescriptor x ) {
 230     newObjectR ( x );
 231     newObjectRs( x );
 232     newObjectFd( x );
 233   }
 234
 235   public void methodCall( TempDescriptor retVal ) {
 236     methodCallR ( retVal );
 237     methodCallRs( retVal );
 238     methodCallFd( retVal );
 239   }
 240
 241   public void merge( DefiniteReachState that ) {
 242     mergeR ( that );
 243     mergeRs( that );
 244     mergeFd( that );
 245   }
 246
 247
 248
 249
 250
 251
 252   public void methodEntryR( Set<TempDescriptor> parameters ) {
 253     R.clear();
 254   }
 255
 256   public void copyR( TempDescriptor x,
 257                      TempDescriptor y ) {
 258     // consider that x and y can be the same, so do the
 259     // parts of the update in the right order:
 260
 261     // first get all info for update
 262     MultiKey keyY = MultiKey.factory( y );
 263     Map<MultiKey, Object> mapY0 = R.get( viewR0, keyY );
 264     Map<MultiKey, Object> mapY1 = R.get( viewR1, keyY );
 265
 266     // then remove anything
 267     MultiKey keyX = MultiKey.factory( x );
 268     R.remove( viewR0, keyX );
 269     R.remove( viewR1, keyX );
 270
 271     // then insert new stuff
 272     for( MultiKey fullKeyY : mapY0.keySet() ) {
 273       MultiKey fullKeyX = MultiKey.factory( x,
 274                                             fullKeyY.get( 1 ),
 275                                             fullKeyY.get( 2 ) );
 276       R.put( fullKeyX, MultiViewMap.dummyValue );
 277     }
 278     for( MultiKey fullKeyY : mapY1.keySet() ) {
 279       MultiKey fullKeyX = MultiKey.factory( fullKeyY.get( 0 ),
 280                                             x,
 281                                             fullKeyY.get( 2 ) );
 282       R.put( fullKeyX, MultiViewMap.dummyValue );
 283     }
 284   }
 285
 286   public void loadR( TempDescriptor x,
 287                      TempDescriptor y,
 288                      FieldDescriptor f,
 289                      Set<EdgeKey> edgeKeysForLoad ) {
 290     // consider that x and y can be the same, so do the
 291     // parts of the update in the right order:
 292
 293     // first get all info for update
 294     MultiKey keyY = MultiKey.factory( y );
 295     Map<MultiKey, Object> mapY0 = R.get( viewR0, keyY );
 296
 297     // then remove anything
 298     MultiKey keyX = MultiKey.factory( x );
 299     R.remove( viewR0, keyX );
 300     R.remove( viewR1, keyX );
 301
 302     // then insert new stuff
 303     for( EdgeKey e : edgeKeysForLoad ) {
 304       R.put( MultiKey.factory( x, y, e ), MultiViewMap.dummyValue );
 305
 306       for( MultiKey fullKeyY : mapY0.keySet() ) {
 307         R.put( MultiKey.factory( x,
 308                                  fullKeyY.get( 1 ),
 309                                  e ),
 310                MultiViewMap.dummyValue );
 311
 312         R.put( MultiKey.factory( x,
 313                                  fullKeyY.get( 1 ),
 314                                  fullKeyY.get( 2 ) ),
 315                MultiViewMap.dummyValue );
 316       }
 317     }
 318   }
 319
 320   public void storeR( TempDescriptor x,
 321                       FieldDescriptor f,
 322                       TempDescriptor y,
 323                       Set<EdgeKey> edgeKeysRemoved,
 324                       Set<EdgeKey> edgeKeysAdded ) {
 325
 326     for( EdgeKey edgeKeyWZ : edgeKeysRemoved ) {
 327       R.remove( viewR2, MultiKey.factory( edgeKeyWZ ) );
 328     }
 329
 330     for( EdgeKey edgeKeyXY : edgeKeysAdded ) {
 331       R.put( MultiKey.factory( y, x, edgeKeyXY ), MultiViewMap.dummyValue );
 332     }
 333   }
 334
 335   public void newObjectR( TempDescriptor x ) {
 336     MultiKey keyX = MultiKey.factory( x );
 337     R.remove( viewR0, keyX );
 338     R.remove( viewR1, keyX );
 339   }
 340
 341   public void methodCallR( TempDescriptor retVal ) {
 342     MultiKey keyRetVal = MultiKey.factory( retVal );
 343     R.remove( viewR0, keyRetVal );
 344     R.remove( viewR1, keyRetVal );
 345   }
 346
 347   public void mergeR( DefiniteReachState that ) {
 348     for( MultiKey key : this.R.get().keySet() ) {
 349       if( that.R.get( viewRfull, key ).isEmpty() ) {
 350         this.R.remove( viewRfull, key );
 351       }
 352     }
 353   }
 354
 355
 356
 357
 358
 359
 360
 361
 362   public void methodEntryRs( Set<TempDescriptor> parameters ) {
 363     Rs.clear();
 364     for( TempDescriptor p : parameters ) {
 365       Rs.put( p, DefReachKnown.UNKNOWN );
 366     }
 367   }
 368
 369   public void copyRs( TempDescriptor x,
 370                       TempDescriptor y ) {
 371     DefReachKnown valRs = Rs.get( y );
 372     assert( valRs != null );
 373     Rs.put( x, valRs );
 374   }
 375
 376   public void loadRs( TempDescriptor x,
 377                       TempDescriptor y,
 378                       FieldDescriptor f,
 379                       Set<EdgeKey> edgeKeysForLoad ) {
 380     Rs.put( x, DefReachKnown.UNKNOWN );
 381   }
 382
 383   public void storeRs( TempDescriptor x,
 384                        FieldDescriptor f,
 385                        TempDescriptor y,
 386                        Set<EdgeKey> edgeKeysRemoved,
 387                        Set<EdgeKey> edgeKeysAdded ) {
 388   }
 389
 390   public void newObjectRs( TempDescriptor x ) {
 391     Rs.put( x, DefReachKnown.KNOWN );
 392   }
 393
 394   public void methodCallRs( TempDescriptor retVal ) {
 395     Rs.put( retVal, DefReachKnown.UNKNOWN );
 396   }
 397
 398   ///////////////////////////////////////////////////////////
 399   //
 400   //  This is WRONG
 401   //
 402   //  It definitely tests the current R as well as Rs
 403   //
 404   //  but also be careful what null means, is it actually
 405   //  equivalent to UNKOWN?  I'd rather put nothing, meaning
 406   //  we have to do an analysis pass over all the incoming edges
 407   //  before there is a sensical answer.  I think...
 408   private void mergeRs( DefiniteReachState that ) {
 409     Set<TempDescriptor> allVars = new HashSet<TempDescriptor>();
 410     allVars.addAll( this.Rs.keySet() );
 411     allVars.addAll( that.Rs.keySet() );
 412     for( TempDescriptor x : allVars ) {
 413       DefReachKnown vThis = this.Rs.get( x );
 414       DefReachKnown vThat = that.Rs.get( x );
 415       if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) &&
 416           vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) {
 417         this.Rs.put( x, DefReachKnown.KNOWN );
 418       } else {
 419         this.Rs.put( x, DefReachKnown.UNKNOWN );
 420       }
 421     }
 422   }
 423
 424
 425
 426
 427
 428
 429
 430   public void methodEntryFd( Set<TempDescriptor> parameters ) {
 431     Fd.clear();
 432   }
 433
 434   public void copyFd( TempDescriptor x,
 435                      TempDescriptor y ) {
 436     // consider that x and y can be the same, so do the
 437     // parts of the update in the right order:
 438
 439     // first get all info for update
 440     MultiKey keyY = MultiKey.factory( y );
 441     Map<MultiKey, Object> mapY0 = Fd.get( viewFd0, keyY );
 442     Map<MultiKey, Object> mapY2 = Fd.get( viewFd2, keyY );
 443
 444     // then remove anything
 445     MultiKey keyX = MultiKey.factory( x );
 446     Fd.remove( viewFd0, keyX );
 447     Fd.remove( viewFd2, keyX );
 448
 449     // then insert new stuff
 450     for( MultiKey fullKeyY : mapY0.keySet() ) {
 451       MultiKey fullKeyX = MultiKey.factory( x,
 452                                             fullKeyY.get( 1 ),
 453                                             fullKeyY.get( 2 ) );
 454       Fd.put( fullKeyX, MultiViewMap.dummyValue );
 455     }
 456     for( MultiKey fullKeyY : mapY2.keySet() ) {
 457       MultiKey fullKeyX = MultiKey.factory( fullKeyY.get( 0 ),
 458                                             fullKeyY.get( 1 ),
 459                                             x );
 460       Fd.put( fullKeyX, MultiViewMap.dummyValue );
 461     }
 462   }
 463
 464   public void loadFd( TempDescriptor x,
 465                      TempDescriptor y,
 466                      FieldDescriptor f,
 467                      Set<EdgeKey> edgeKeysForLoad ) {
 468
 469     MultiKey keyX = MultiKey.factory( x );
 470     Fd.remove( viewFd0, keyX );
 471     Fd.remove( viewFd2, keyX );
 472   }
 473
 474   public void storeFd( TempDescriptor x,
 475                       FieldDescriptor f,
 476                       TempDescriptor y,
 477                       Set<EdgeKey> edgeKeysFdemoved,
 478                       Set<EdgeKey> edgeKeysAdded ) {
 479     Fd.put( MultiKey.factory( x, f, y ),
 480             MultiViewMap.dummyValue );
 481   }
 482
 483   public void newObjectFd( TempDescriptor x ) {
 484     MultiKey keyX = MultiKey.factory( x );
 485     Fd.remove( viewFd0, keyX );
 486     Fd.remove( viewFd2, keyX );
 487   }
 488
 489   public void methodCallFd( TempDescriptor retVal ) {
 490     MultiKey keyRetVal = MultiKey.factory( retVal );
 491     Fd.remove( viewFd0, keyRetVal );
 492     Fd.remove( viewFd2, keyRetVal );
 493   }
 494
 495   public void mergeFd( DefiniteReachState that ) {
 496     this.Fd.merge( that.Fd );
 497   }
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510   public boolean equals( Object o ) {
 511     if( this == o ) {
 512       return true;
 513     }
 514     if( o == null ) {
 515       return false;
 516     }
 517     if( !(o instanceof DefiniteReachState) ) {
 518       return false;
 519     }
 520     DefiniteReachState that = (DefiniteReachState) o;
 521
 522     assert( false );
 523     return false;
 524   }
 525
 526
 527   public int hashCode() {
 528     assert( false );
 529     return 0;
 530   }
 531
 532
 533   public void writeState( String outputName ) {
 534     try {
 535       BufferedWriter bw = new BufferedWriter( new FileWriter( "defReach-"+outputName+".txt" ) );
 536       bw.write( this.toString() );
 537       bw.close();
 538     } catch( IOException e ) {
 539       System.out.println( "ERROR writing definite reachability state:\n  "+e );
 540     }
 541   }
 542
 543
 544   public String toString() {
 545     StringBuilder s = new StringBuilder();
 546
 547     s.append( "R = {\n" );
 548     s.append( R.toString( 2 ) );
 549     s.append( "}\n" );
 550
 551     s.append( "Rs = {\n" );
 552     for( TempDescriptor x : Rs.keySet() ) {
 553       s.append( "  "+x+"->"+Rs.get( x )+"\n" );
 554     }
 555     s.append( "}\n" );
 556
 557     s.append( "Fd = {\n" );
 558     s.append( Fd.toString( 2 ) );
 559     s.append( "}\n" );
 560
 561     return s.toString();
 562   }
 563 }