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     loadR( x, y, f );
 138     // Rs' := (Rs - <x,*>) U {<x, unknown>}
 139     //Rs.put( x, DefReachKnown.UNKNOWN );
 140   }
 141
 142   public void store( TempDescriptor x,
 143                      FieldDescriptor f,
 144                      TempDescriptor y,
 145                      Set<EdgeKey> edgeKeysRemoved ) {
 146     storeR( x, f, y, edgeKeysRemoved );
 147     // Rs' := Rs
 148   }
 149
 150   public void newObject( TempDescriptor x ) {
 151     newObjectR( x );
 152
 153     // Rs' := (Rs - <x,*>) U {<x, new>}
 154     //Rs.put( x, DefReachKnown.KNOWN );
 155
 156   }
 157
 158   public void methodCall( TempDescriptor retVal ) {
 159     methodCallR( retVal );
 160
 161     // Rs' := (Rs - <x,*>) U {<x, unknown>}
 162     //Rs.put( x, DefReachKnown.UNKNOWN );
 163   }
 164
 165   public void merge( DefiniteReachState that ) {
 166     mergeR( that );
 167
 168     // Rs' := <x, new> iff in all incoming edges, otherwie <x, unknown>
 169     //mergeRs( that );
 170   }
 171
 172
 173
 174
 175
 176
 177   public void methodEntryR( Set<TempDescriptor> parameters ) {
 178     R.clear();
 179   }
 180
 181   public void copyR( TempDescriptor x,
 182                      TempDescriptor y ) {
 183     // R' := (R - <x,*> - <*,x>)        U
 184     //       {<x,z>->e | <y,z>->e in R} U
 185     //       {<z,x>->e | <z,y>->e in R}
 186     // R' = new Map(R)
 187     // R'.remove(view0, x);
 188     // R'.remove(view1, x);
 189     // setYs = R.get(view0, y);
 190     // for each <y,z>->e: R'.put(<x,z>, e);
 191     // setYs = R.get(view1, y);
 192     // for each <z,y>->e: R'.put(<z,x>, e);
 193   }
 194
 195   public void loadR( TempDescriptor x,
 196                      TempDescriptor y,
 197                      FieldDescriptor f ) {
 198     // R' := (R - <x,*> - <*,x>) U
 199     //       ({<x,y>} x Eo(y,f)) U
 200     //       U        {<x,z>} x (Eo(y,f)U{e})
 201     //   <y,z>->e in R
 202     // R' = new Map(R)
 203     // R'.remove(view0, x);
 204     // R'.remove(view1, x);
 205     // R'.put(<x,y>, eee!);
 206     // setYs = R.get(view0, y);
 207     // for each <y,z>->e: R'.put(<x,z>, eee!Ue);
 208   }
 209
 210   public void storeR( TempDescriptor x,
 211                       FieldDescriptor f,
 212                       TempDescriptor y,
 213                       Set<EdgeKey> edgeKeysRemoved ) {
 214     // I think this should be if there is ANY <w,z>->e' IN Eremove, then kill all <w,z>
 215     // R' := (R - {<w,z>->e | <w,z>->e in R, A<w,z>->e' in R, e' notin Eremove}) U
 216     //       {<y,x>->e | e in E(x) x {f} x E(y)}
 217     // R' = new Map(R)
 218     // R'.remove(?); some e's...
 219     // R'.put(<y,x>, E(x) x {f} x E(y));
 220   }
 221
 222   public void newObjectR( TempDescriptor x ) {
 223     // R' := (R - <x,*> - <*,x>)
 224     // R' = new Map(R)
 225     // R'.remove(view0, x);
 226     // R'.remove(view1, x);
 227   }
 228
 229   public void methodCallR( TempDescriptor retVal ) {
 230     // R' := (R - <x,*> - <*,x>)
 231     // R' = new Map(R)
 232     // R'.remove(view0, x);
 233     // R'.remove(view1, x);
 234   }
 235
 236   public void mergeR( DefiniteReachState that ) {
 237     // R' := <x,y>->e iff its in all incoming edges
 238   }
 239
 240
 241
 242
 243   ///////////////////////////////////////////////////////////
 244   //
 245   //  This is WRONG
 246   //
 247   //  It definitely tests the current R as well as Rs
 248   //
 249   //  but also be careful what null means, is it actually
 250   //  equivalent to UNKOWN?  I'd rather put nothing, meaning
 251   //  we have to do an analysis pass over all the incoming edges
 252   //  before there is a sensical answer.  I think...
 253   private void mergeRs( DefiniteReachState that ) {
 254     // merge "that" into "this" and leave "that" unchanged
 255     //Set<TempDescriptor> allVars = new HashSet<TempDescriptor>();
 256     //allVars.addAll( this.Rs.keySet() );
 257     //allVars.addAll( that.Rs.keySet() );
 258     //for( TempDescriptor x : allVars ) {
 259     //  DefReachKnown vThis = this.Rs.get( x );
 260     //  DefReachKnown vThat = that.Rs.get( x );
 261     //  if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) &&
 262     //      vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) {
 263     //    this.Rs.put( x, DefReachKnown.KNOWN );
 264     //  } else {
 265     //    this.Rs.put( x, DefReachKnown.UNKNOWN );
 266     //  }
 267     //}
 268   }
 269
 270
 271
 272   public boolean equals( Object o ) {
 273     if( this == o ) {
 274       return true;
 275     }
 276     if( o == null ) {
 277       return false;
 278     }
 279     if( !(o instanceof DefiniteReachState) ) {
 280       return false;
 281     }
 282     DefiniteReachState that = (DefiniteReachState) o;
 283
 284     assert( false );
 285     return false;
 286   }
 287
 288
 289   public int hashCode() {
 290     assert( false );
 291     return 0;
 292   }
 293
 294
 295
 296   public String toString() {
 297     StringBuilder s = new StringBuilder( "R_s = {" );
 298     //for( TempDescriptor x : Rs.keySet() ) {
 299     //  s.append( "  "+x+"->"+Rs.get( x ) );
 300     //}
 301     //s.append( "}" );
 302     return s.toString();
 303   }
 304 }