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   // for MultiViewMaps that don't need to use the value,
  53   // always map to this dummy
  54   private static Object dummy = new Integer( -12345 );
  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     viewR0  = RBuilder.addPartialView( 0 );
  66     viewR1  = RBuilder.addPartialView( 1 );
  67     viewR01 = RBuilder.addPartialView( 0, 1 );
  68     RBuilder.setCheckTypes( true );
  69     RBuilder.setCheckConsistency( true );
  70
  71     //FuBuilder =
  72     //  new MultiViewMapBuilder<Object>( new Class[] {
  73     //                                     TempDescriptor.class,
  74     //                                     DefReachFuVal.class},
  75     //                                   new JoinOpNop() );
  76     //viewFu0 = FuBuilder.addPartialView( 0 );
  77     //viewFu1 = FuBuilder.addPartialView( 1 );
  78     //FuBuilder.setCheckTypes( true );
  79     //FuBuilder.setCheckConsistency( true );
  80   }
  81
  82
  83
  84
  85
  86   public DefiniteReachState() {
  87     //Rs = new HashMap<TempDescriptor, DefReachKnown>();
  88     //Fu = FuBuilder.build();
  89   }
  90
  91
  92
  93   public void methodEntry(Set<TempDescriptor> parameters) {
  94     // R' := {}
  95     // R.clear();
  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     // R' := (R - <x,*> - <*,x>)        U
 108     //       {<x,z>->e | <y,z>->e in R} U
 109     //       {<z,x>->e | <z,y>->e in R}
 110     // R' = new Map(R)
 111     // R'.remove(view0, x);
 112     // R'.remove(view1, x);
 113     // setYs = R.get(view0, y);
 114     // for each <y,z>->e: R'.put(<x,z>, e);
 115     // setYs = R.get(view1, y);
 116     // for each <z,y>->e: R'.put(<z,x>, e);
 117
 118     // Rs' := (Rs - <x,*>) U {<x,v> | <y,v> in Rs}
 119     //DefReachKnown valRs = Rs.get( y );
 120     //assert( valRs != null );
 121     //Rs.put( x, valRs );
 122
 123     // Fu' := (Fu - <x, *> - <*, x>) U
 124     //        {<x,v> | <y,v> in Fu} U
 125     //        {<v,x> | <v,y> in Fu} U
 126     //        {<z, unknown> | <z,<x>> in Fu}
 127     //Fu.remove( viewFu0, MultiKey.factory( x ) );
 128     //Fu.remove( viewFu1, MultiKey.factory( x ) );
 129     //for( MultiKey key : Fu.get( viewFu0, MultiKey.factory( y ) ).keySet() ) {
 130     //  DefReachFuVal val = (DefReachFuVal) key.get( 1 );
 131     //  Fu.put( MultiKey.factory( x, val ), dummy );
 132     //}
 133     //for( MultiKey key : Fu.get( viewFu1, MultiKey.factory( y ) ).keySet() ) {
 134     //  TempDescriptor v = (TempDescriptor) key.get( 0 );
 135     //  Fu.put( MultiKey.factory( v, DefReachFuVal.factory( x ) ), dummy );
 136     //}
 137     //for( MultiKey key :
 138     //       Fu.get( viewFu1,
 139     //               MultiKey.factory( DefReachFuVal.factory( DefReachFuVal.Val.UNKNOWN ) )
 140     //               ).keySet()
 141     //     ) {
 142     //  TempDescriptor z = (TempDescriptor) key.get( 0 );
 143     //  Fu.put( MultiKey.factory( z, DefReachFuVal.factory( x ) ), dummy );
 144     //}
 145   }
 146
 147   public void load(TempDescriptor x,
 148                    TempDescriptor y,
 149                    FieldDescriptor f) {
 150     // R' := (R - <x,*> - <*,x>) U
 151     //       ({<x,y>} x Eo(y,f)) U
 152     //       U        {<x,z>} x (Eo(y,f)U{e})
 153     //   <y,z>->e in R
 154     // R' = new Map(R)
 155     // R'.remove(view0, x);
 156     // R'.remove(view1, x);
 157     // R'.put(<x,y>, eee!);
 158     // setYs = R.get(view0, y);
 159     // for each <y,z>->e: R'.put(<x,z>, eee!Ue);
 160
 161     // Rs' := (Rs - <x,*>) U {<x, unknown>}
 162     //Rs.put( x, DefReachKnown.UNKNOWN );
 163   }
 164
 165   public void store(TempDescriptor x,
 166                    FieldDescriptor f,
 167                    TempDescriptor y,
 168                    Set<EdgeKey> edgeKeysRemoved) {
 169     // I think this should be if there is ANY <w,z>->e' IN Eremove, then kill all <w,z>
 170     // R' := (R - {<w,z>->e | <w,z>->e in R, A<w,z>->e' in R, e' notin Eremove}) U
 171     //       {<y,x>->e | e in E(x) x {f} x E(y)}
 172     // R' = new Map(R)
 173     // R'.remove(?); some e's...
 174     // R'.put(<y,x>, E(x) x {f} x E(y));
 175
 176     // Rs' := Rs
 177   }
 178
 179   public void newObject(TempDescriptor x) {
 180     // R' := (R - <x,*> - <*,x>)
 181     // R' = new Map(R)
 182     // R'.remove(view0, x);
 183     // R'.remove(view1, x);
 184
 185     // Rs' := (Rs - <x,*>) U {<x, new>}
 186     //Rs.put( x, DefReachKnown.KNOWN );
 187
 188   }
 189
 190   // x is the return value, x = foo(...);
 191   public void methodCall(TempDescriptor x) {
 192     // R' := (R - <x,*> - <*,x>)
 193     // R' = new Map(R)
 194     // R'.remove(view0, x);
 195     // R'.remove(view1, x);
 196
 197     // Rs' := (Rs - <x,*>) U {<x, unknown>}
 198     //Rs.put( x, DefReachKnown.UNKNOWN );
 199   }
 200
 201   public void merge( DefiniteReachState that ) {
 202     // R' := <x,y>->e iff its in all incoming edges
 203
 204     // Rs' := <x, new> iff in all incoming edges, otherwie <x, unknown>
 205     //mergeRs( that );
 206   }
 207
 208
 209   ///////////////////////////////////////////////////////////
 210   //
 211   //  This is WRONG
 212   //
 213   //  It definitely tests the current R as well as Rs
 214   //
 215   //  but also be careful what null means, is it actually
 216   //  equivalent to UNKOWN?  I'd rather put nothing, meaning
 217   //  we have to do an analysis pass over all the incoming edges
 218   //  before there is a sensical answer.  I think...
 219   private void mergeRs( DefiniteReachState that ) {
 220     // merge "that" into "this" and leave "that" unchanged
 221     //Set<TempDescriptor> allVars = new HashSet<TempDescriptor>();
 222     //allVars.addAll( this.Rs.keySet() );
 223     //allVars.addAll( that.Rs.keySet() );
 224     //for( TempDescriptor x : allVars ) {
 225     //  DefReachKnown vThis = this.Rs.get( x );
 226     //  DefReachKnown vThat = that.Rs.get( x );
 227     //  if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) &&
 228     //      vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) {
 229     //    this.Rs.put( x, DefReachKnown.KNOWN );
 230     //  } else {
 231     //    this.Rs.put( x, DefReachKnown.UNKNOWN );
 232     //  }
 233     //}
 234   }
 235
 236
 237
 238   public boolean equals( Object o ) {
 239     if( this == o ) {
 240       return true;
 241     }
 242     if( o == null ) {
 243       return false;
 244     }
 245     if( !(o instanceof DefiniteReachState) ) {
 246       return false;
 247     }
 248     DefiniteReachState that = (DefiniteReachState) o;
 249
 250     assert( false );
 251     return false;
 252   }
 253
 254
 255   public int hashCode() {
 256     assert( false );
 257     return 0;
 258   }
 259
 260
 261
 262   public String toString() {
 263     StringBuilder s = new StringBuilder( "R_s = {" );
 264     //for( TempDescriptor x : Rs.keySet() ) {
 265     //  s.append( "  "+x+"->"+Rs.get( x ) );
 266     //}
 267     //s.append( "}" );
 268     return s.toString();
 269   }
 270 }