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 variables and 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
  20
  21   // Rs
  22   // Tracks whether the analysis must know the definite reachability
  23   // information of a given variable.
  24   private enum DefReachKnown {
  25     UNKNOWN,
  26     KNOWN,
  27   }
  28   private Map<TempDescriptor, DefReachKnown> Rs;
  29
  30
  31   // Fu (upstream)
  32   //
  33   // Maps a variable that points to object o0 to the
  34   // set of variables that point to objects o1...oN
  35   // that have a reference to o0.
  36   private static MultiViewMapBuilder<Object> FuBuilder;
  37   private static BitSet viewFu0;
  38   private static BitSet viewFu1;
  39   private MultiViewMap<Object> Fu;
  40
  41
  42   // Fd (downstream)
  43
  44
  45
  46
  47   // for MultiViewMaps that don't need to use the value,
  48   // always map to this dummy
  49   private static Object dummy = new Integer( -1234 );
  50
  51
  52   // call before instantiating this class
  53   static public void initBuilders() {
  54     FuBuilder =
  55       new MultiViewMapBuilder<Object>( new Class[] {
  56                                          TempDescriptor.class,
  57                                          DefReachFuVal.class},
  58                                        new JoinOpNop() );
  59     viewFu0 = FuBuilder.addPartialView( 0 );
  60     viewFu1 = FuBuilder.addPartialView( 1 );
  61     FuBuilder.setCheckTypes( true );
  62     FuBuilder.setCheckConsistency( true );
  63   }
  64
  65
  66
  67
  68
  69   public DefiniteReachState() {
  70     Rs = new HashMap<TempDescriptor, DefReachKnown>();
  71     Fu = FuBuilder.build();
  72   }
  73
  74
  75
  76   public void methodEntry(Set<TempDescriptor> parameters) {
  77     // R' := {}
  78     // R.clear();
  79
  80     Rs.clear();
  81     for( TempDescriptor p : parameters ) {
  82       Rs.put( p, DefReachKnown.UNKNOWN );
  83     }
  84
  85     Fu = FuBuilder.build();
  86   }
  87
  88   public void copy(TempDescriptor x,
  89                    TempDescriptor y) {
  90     // R' := (R - <x,*> - <*,x>)        U
  91     //       {<x,z>->e | <y,z>->e in R} U
  92     //       {<z,x>->e | <z,y>->e in R}
  93     // R' = new Map(R)
  94     // R'.remove(view0, x);
  95     // R'.remove(view1, x);
  96     // setYs = R.get(view0, y);
  97     // for each <y,z>->e: R'.put(<x,z>, e);
  98     // setYs = R.get(view1, y);
  99     // for each <z,y>->e: R'.put(<z,x>, e);
 100
 101     // Rs' := (Rs - <x,*>) U {<x,v> | <y,v> in Rs}
 102     DefReachKnown valRs = Rs.get( y );
 103     assert( valRs != null );
 104     Rs.put( x, valRs );
 105
 106     // Fu' := (Fu - <x, *> - <*, x>) U
 107     //        {<x,v> | <y,v> in Fu} U
 108     //        {<v,x> | <v,y> in Fu} U
 109     //        {<z, unknown> | <z,<x>> in Fu}
 110     Fu.remove( viewFu0, MultiKey.factory( x ) );
 111     Fu.remove( viewFu1, MultiKey.factory( x ) );
 112     for( MultiKey key : Fu.get( viewFu0, MultiKey.factory( y ) ).keySet() ) {
 113       DefReachFuVal val = (DefReachFuVal) key.get( 1 );
 114       Fu.put( MultiKey.factory( x, val ), dummy );
 115     }
 116     for( MultiKey key : Fu.get( viewFu1, MultiKey.factory( y ) ).keySet() ) {
 117       TempDescriptor v = (TempDescriptor) key.get( 0 );
 118       Fu.put( MultiKey.factory( v, DefReachFuVal.factory( x ) ), dummy );
 119     }
 120     for( MultiKey key :
 121            Fu.get( viewFu1,
 122                    MultiKey.factory( DefReachFuVal.factory( DefReachFuVal.Val.UNKNOWN ) )
 123                    ).keySet()
 124          ) {
 125       TempDescriptor z = (TempDescriptor) key.get( 0 );
 126       Fu.put( MultiKey.factory( z, DefReachFuVal.factory( x ) ), dummy );
 127     }
 128   }
 129
 130   public void load(TempDescriptor x,
 131                    TempDescriptor y,
 132                    FieldDescriptor f) {
 133     // R' := (R - <x,*> - <*,x>) U
 134     //       ({<x,y>} x Eo(y,f)) U
 135     //       U        {<x,z>} x (Eo(y,f)U{e})
 136     //   <y,z>->e in R
 137     // R' = new Map(R)
 138     // R'.remove(view0, x);
 139     // R'.remove(view1, x);
 140     // R'.put(<x,y>, eee!);
 141     // setYs = R.get(view0, y);
 142     // for each <y,z>->e: R'.put(<x,z>, eee!Ue);
 143
 144     // Rs' := (Rs - <x,*>) U {<x, unknown>}
 145     Rs.put( x, DefReachKnown.UNKNOWN );
 146   }
 147
 148   public void store(TempDescriptor x,
 149                    FieldDescriptor f,
 150                    TempDescriptor y) {
 151     // I think this should be if there is ANY <w,z>->e' IN Eremove, then kill all <w,z>
 152     // R' := (R - {<w,z>->e | <w,z>->e in R, A<w,z>->e' in R, e' notin Eremove}) U
 153     //       {<y,x>->e | e in E(x) x {f} x E(y)}
 154     // R' = new Map(R)
 155     // R'.remove(?); some e's...
 156     // R'.put(<y,x>, E(x) x {f} x E(y));
 157
 158     // Rs' := Rs
 159   }
 160
 161   public void newObject(TempDescriptor x) {
 162     // R' := (R - <x,*> - <*,x>)
 163     // R' = new Map(R)
 164     // R'.remove(view0, x);
 165     // R'.remove(view1, x);
 166
 167     // Rs' := (Rs - <x,*>) U {<x, new>}
 168     Rs.put( x, DefReachKnown.KNOWN );
 169
 170   }
 171
 172   // x is the return value, x = foo(...);
 173   public void methodCall(TempDescriptor x) {
 174     // R' := (R - <x,*> - <*,x>)
 175     // R' = new Map(R)
 176     // R'.remove(view0, x);
 177     // R'.remove(view1, x);
 178
 179     // Rs' := (Rs - <x,*>) U {<x, unknown>}
 180     Rs.put( x, DefReachKnown.UNKNOWN );
 181   }
 182
 183   public void merge( DefiniteReachState that ) {
 184     // R' := <x,y>->e iff its in all incoming edges
 185
 186     // Rs' := <x, new> iff in all incoming edges, otherwie <x, unknown>
 187     mergeRs( that );
 188   }
 189
 190
 191   ///////////////////////////////////////////////////////////
 192   //
 193   //  This is WRONG
 194   //
 195   //  It definitely tests the current R as well as Rs
 196   //
 197   //  but also be careful what null means, is it actually
 198   //  equivalent to UNKOWN?  I'd rather put nothing, meaning
 199   //  we have to do an analysis pass over all the incoming edges
 200   //  before there is a sensical answer.  I think...
 201   private void mergeRs( DefiniteReachState that ) {
 202     // merge "that" into "this" and leave "that" unchanged
 203     Set<TempDescriptor> allVars = new HashSet<TempDescriptor>();
 204     allVars.addAll( this.Rs.keySet() );
 205     allVars.addAll( that.Rs.keySet() );
 206     for( TempDescriptor x : allVars ) {
 207       DefReachKnown vThis = this.Rs.get( x );
 208       DefReachKnown vThat = that.Rs.get( x );
 209       if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) &&
 210           vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) {
 211         this.Rs.put( x, DefReachKnown.KNOWN );
 212       } else {
 213         this.Rs.put( x, DefReachKnown.UNKNOWN );
 214       }
 215     }
 216   }
 217
 218
 219
 220   public boolean equals( Object o ) {
 221     if( this == o ) {
 222       return true;
 223     }
 224     if( o == null ) {
 225       return false;
 226     }
 227     if( !(o instanceof DefiniteReachState) ) {
 228       return false;
 229     }
 230     DefiniteReachState that = (DefiniteReachState) o;
 231
 232     assert( false );
 233     return false;
 234   }
 235
 236
 237   public int hashCode() {
 238     assert( false );
 239     return 0;
 240   }
 241
 242
 243
 244   public String toString() {
 245     StringBuilder s = new StringBuilder( "R_s = {" );
 246     for( TempDescriptor x : Rs.keySet() ) {
 247       s.append( "  "+x+"->"+Rs.get( x ) );
 248     }
 249     s.append( "}" );
 250     return s.toString();
 251   }
 252 }