Robust/src/Analysis/ArrayReferencees.java

   1 //////////////////////////////////////////////////
   2 //
   3 //  The object of this analysis is to maintain a
   4 //  relation for program points:
   5 //  array variable -> variables referenced by the array's elements
   6 //
   7 //  This analysis is useful in reachability analysis
   8 //  because if a variable is read from an array,
   9 //  then inserted back into the array, we can be
  10 //  sure that no new reachability paths are created.
  11 //
  12 //////////////////////////////////////////////////
  13
  14 package Analysis;
  15
  16 import IR.State;
  17 import IR.Descriptor;
  18 import IR.ClassDescriptor;
  19 import IR.MethodDescriptor;
  20 import IR.TaskDescriptor;
  21 import IR.TypeDescriptor;
  22 import IR.Flat.TempDescriptor;
  23 import IR.Flat.FlatMethod;
  24 import IR.Flat.FlatNode;
  25 import IR.Flat.FlatElementNode;
  26 import IR.Flat.FlatSetElementNode;
  27 import IR.Flat.FKind;
  28 import Util.UtilAlgorithms;
  29 import java.util.*;
  30 import java.io.*;
  31
  32
  33 public class ArrayReferencees {
  34
  35   ////////////////////////////////
  36   // public interface
  37   ////////////////////////////////
  38   public ArrayReferencees( State state ) {
  39     init( state );
  40   }
  41
  42   public boolean doesNotCreateNewReaching( FlatSetElementNode fsen ) {
  43     return noNewReaching.contains( fsen );
  44   }
  45   ////////////////////////////////
  46   // end public interface
  47   ////////////////////////////////
  48
  49
  50
  51   protected State state;
  52
  53   // maintain the relation at every program point
  54   protected Hashtable<FlatNode, InArrayRelation> fn2rel;
  55
  56   // use relation to calculate set of array populate
  57   // nodes that cannot create new reachability paths
  58   protected Set<FlatSetElementNode> noNewReaching;
  59
  60
  61   protected ArrayReferencees() {}
  62
  63   protected void init( State state ) {
  64     this.state = state;
  65     fn2rel = new Hashtable<FlatNode, InArrayRelation>();
  66     noNewReaching = new HashSet<FlatSetElementNode>();
  67     buildRelation();
  68   }
  69
  70   protected void buildRelation() {
  71     // just analyze every method of every class that the
  72     // compiler has code for, fix if this is too costly
  73     Iterator classItr = state.getClassSymbolTable().getDescriptorsIterator();
  74     while( classItr.hasNext() ) {
  75       ClassDescriptor cd = (ClassDescriptor)classItr.next();
  76
  77       Iterator methodItr = cd.getMethods();
  78       while( methodItr.hasNext() ) {
  79         MethodDescriptor md = (MethodDescriptor)methodItr.next();
  80
  81         FlatMethod fm = state.getMethodFlat( md );
  82         analyzeMethod( fm );
  83       }
  84     }
  85   }
  86
  87   protected void analyzeMethod( FlatMethod fm ) {
  88     Set<FlatNode> toVisit = new HashSet<FlatNode>();
  89     toVisit.add( fm );
  90
  91     while( !toVisit.isEmpty() ) {
  92       FlatNode fn = toVisit.iterator().next();
  93       toVisit.remove( fn );
  94
  95       // find the result flowing into this node
  96       InArrayRelation rel = new InArrayRelation();
  97
  98       // the join operation is intersection, so
  99       // merge with 1st predecessor (if any) and
 100       // then do intersect with all others
 101       if( fn.numPrev() > 0 ) {
 102         rel.merge( fn2rel.get( fn.getPrev( 0 ) ) );
 103
 104         for( int i = 1; i < fn.numPrev(); ++i ) {
 105           rel.intersect( fn2rel.get( fn.getPrev( i ) ) );
 106         }
 107       }
 108
 109       analyzeFlatNode( fn, rel );
 110
 111       // enqueue child nodes if new results were found
 112       InArrayRelation relPrev = fn2rel.get( fn );
 113       if( !rel.equals( relPrev ) ) {
 114         fn2rel.put( fn, rel );
 115         for( int i = 0; i < fn.numNext(); i++ ) {
 116           FlatNode nn = fn.getNext( i );
 117           toVisit.add( nn );
 118         }
 119       }
 120     }
 121   }
 122
 123   protected void analyzeFlatNode( FlatNode fn,
 124                                   InArrayRelation rel ) {
 125
 126     TempDescriptor lhs;
 127     TempDescriptor rhs;
 128
 129     // use node type to transform relation
 130     switch( fn.kind() ) {
 131
 132     case FKind.FlatElementNode:
 133       // lhs = rhs[...]
 134       FlatElementNode fen = (FlatElementNode) fn;
 135       lhs = fen.getDst();
 136       rhs = fen.getSrc();
 137       rel.remove( lhs );
 138       rel.put_array2refee( rhs, lhs );
 139       break;
 140
 141     case FKind.FlatSetElementNode:
 142       // lhs[...] = rhs
 143       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 144       lhs = fsen.getDst();
 145       rhs = fsen.getSrc();
 146
 147       // use relation result coming into this program
 148       // point ("rel" before we modify it) to compute
 149       // whether this node affects reachability paths
 150       if( rel.canArrayAlreadyReach( lhs, rhs ) ) {
 151         noNewReaching.add( fsen );
 152
 153       } else {
 154         // otherwise we can't be sure, so remove
 155         noNewReaching.remove( fsen );
 156       }
 157
 158       // then update the relation for the fixed-point
 159       // analysis to continue
 160       rel.put_array2refee( lhs, rhs );
 161       break;
 162
 163     default:
 164       // the default action is to remove every temp
 165       // written by this node from the relation
 166       TempDescriptor[] writeTemps = fn.writesTemps();
 167       for( int i = 0; i < writeTemps.length; ++i ) {
 168         TempDescriptor td = writeTemps[i];
 169         rel.remove( td );
 170       }
 171       break;
 172
 173     }
 174   }
 175
 176
 177
 178
 179   protected class InArrayRelation {
 180
 181     // The relation is possibly dense, in that any variable might
 182     // be referenced by many arrays, and an array may reference
 183     // many variables.  So maintain the relation as two hashtables
 184     // that are redundant but allow efficient operations
 185     protected Hashtable< TempDescriptor, Set<TempDescriptor> > array2refees;
 186     protected Hashtable< TempDescriptor, Set<TempDescriptor> > refee2arrays;
 187
 188     public InArrayRelation() {
 189       array2refees = new Hashtable< TempDescriptor, Set<TempDescriptor> >();
 190       refee2arrays = new Hashtable< TempDescriptor, Set<TempDescriptor> >();
 191     }
 192
 193     public boolean canArrayAlreadyReach( TempDescriptor array,
 194                                          TempDescriptor elem ) {
 195
 196       Set<TempDescriptor> refees = array2refees.get( array );
 197       return refees != null && refees.contains( elem );
 198     }
 199
 200     public void put_array2refee( TempDescriptor array, TempDescriptor refee ) {
 201       // update one direction
 202       Set<TempDescriptor> refees = array2refees.get( array );
 203       if( refees == null ) {
 204         refees = new HashSet<TempDescriptor>();
 205       }
 206       refees.add( refee );
 207       array2refees.put( array, refees );
 208
 209       // and then the other
 210       Set<TempDescriptor> arrays = refee2arrays.get( refee );
 211       if( arrays == null ) {
 212         arrays = new HashSet<TempDescriptor>();
 213       }
 214       arrays.add( array );
 215       refee2arrays.put( refee, arrays );
 216
 217       assertConsistent();
 218     }
 219
 220     public void remove( TempDescriptor td ) {
 221       // removal of one temp from the relation is a bit
 222       // tricky--it can be on either side of the pair or
 223       // both at the same time
 224
 225       // during traversal, mark keys that should be removed
 226       Set<TempDescriptor> a2rKeysToRemove = new HashSet<TempDescriptor>();
 227       Set<TempDescriptor> r2aKeysToRemove = new HashSet<TempDescriptor>();
 228
 229       // also during traversal, mark sets by how they
 230       // should be shortened
 231       Hashtable<Set, Set> set2removals = new Hashtable<Set, Set>();
 232
 233       {
 234         // first consider one side of the relation
 235         Set<TempDescriptor> refees = array2refees.get( td );
 236         if( refees != null ) {
 237           assert !refees.isEmpty();
 238
 239           // definitely remove the key from this mapping
 240           a2rKeysToRemove.add( td );
 241
 242           // and remove it from set values in the other mapping
 243           Iterator<TempDescriptor> refItr = refees.iterator();
 244           while( refItr.hasNext() ) {
 245             TempDescriptor ref = refItr.next();
 246
 247             Set<TempDescriptor> arrays = refee2arrays.get( ref );
 248             assert arrays != null;
 249             assert !arrays.isEmpty();
 250
 251             Set<TempDescriptor> removals = set2removals.get( arrays );
 252             if( removals == null ) {
 253               removals = new HashSet<TempDescriptor>();
 254             }
 255             removals.add( td );
 256             set2removals.put( arrays, removals );
 257
 258             if( removals.size() == arrays.size() ) {
 259               // we've marked everything in this for removal! So
 260               // just remove the key from the mapping
 261               assert arrays.containsAll( removals );
 262               r2aKeysToRemove.add( ref );
 263             }
 264           }
 265         }
 266       }
 267
 268       {
 269         // and then see if it is in the relation's other direction
 270         Set<TempDescriptor> arrays = refee2arrays.get( td );
 271         if( arrays != null ) {
 272           assert !arrays.isEmpty();
 273
 274           // definitely remove the key from this mapping
 275           r2aKeysToRemove.add( td );
 276
 277           // and remove it from set values in the other mapping
 278           Iterator<TempDescriptor> arrItr = arrays.iterator();
 279           while( arrItr.hasNext() ) {
 280             TempDescriptor arr = arrItr.next();
 281
 282             Set<TempDescriptor> refees = array2refees.get( arr );
 283             assert refees != null;
 284             assert !refees.isEmpty();
 285
 286             Set<TempDescriptor> removals = set2removals.get( refees );
 287             if( removals == null ) {
 288               removals = new HashSet<TempDescriptor>();
 289             }
 290             removals.add( td );
 291             set2removals.put( refees, removals );
 292
 293             if( removals.size() == refees.size() ) {
 294               // we've marked everything in this for removal! So
 295               // just remove the key from the mapping
 296               assert refees.containsAll( removals );
 297               a2rKeysToRemove.add( arr );
 298             }
 299           }
 300         }
 301       }
 302
 303       // perform all marked removing now
 304       Iterator<TempDescriptor> keyItr;
 305
 306       keyItr = a2rKeysToRemove.iterator();
 307       while( keyItr.hasNext() ) {
 308         array2refees.remove( keyItr.next() );
 309       }
 310
 311       keyItr = r2aKeysToRemove.iterator();
 312       while( keyItr.hasNext() ) {
 313         refee2arrays.remove( keyItr.next() );
 314       }
 315
 316       Iterator meItr = set2removals.entrySet().iterator();
 317       while( meItr.hasNext() ) {
 318         Map.Entry me       = (Map.Entry) meItr.next();
 319         Set       set      = (Set)       me.getKey();
 320         Set       removals = (Set)       me.getValue();
 321
 322         set.removeAll( removals );
 323       }
 324
 325
 326       assertConsistent();
 327     }
 328
 329     public void merge( InArrayRelation r ) {
 330       if( r == null ) {
 331         return;
 332       }
 333       UtilAlgorithms.mergeHashtablesWithHashSetValues( array2refees, r.array2refees );
 334       UtilAlgorithms.mergeHashtablesWithHashSetValues( refee2arrays, r.refee2arrays );
 335       assertConsistent();
 336     }
 337
 338     public void intersect( InArrayRelation r ) {
 339       if( r == null ) {
 340         array2refees.clear();
 341         refee2arrays.clear();
 342         return;
 343       }
 344       UtilAlgorithms.intersectHashtablesWithSetValues( array2refees, r.array2refees );
 345       UtilAlgorithms.intersectHashtablesWithSetValues( refee2arrays, r.refee2arrays );
 346       assertConsistent();
 347     }
 348
 349     public void assertConsistent() {
 350       assert allEntriesInAReversedInB( array2refees, refee2arrays );
 351       assert allEntriesInAReversedInB( refee2arrays, array2refees );
 352     }
 353
 354     protected boolean allEntriesInAReversedInB(
 355       Hashtable< TempDescriptor, Set<TempDescriptor> > a,
 356       Hashtable< TempDescriptor, Set<TempDescriptor> > b ) {
 357
 358       Iterator mapItr = a.entrySet().iterator();
 359       while( mapItr.hasNext() ) {
 360         Map.Entry           me    = (Map.Entry)           mapItr.next();
 361         TempDescriptor      keyA  = (TempDescriptor)      me.getKey();
 362         Set<TempDescriptor> valsA = (Set<TempDescriptor>) me.getValue();
 363
 364         Iterator<TempDescriptor> valItr = valsA.iterator();
 365         while( valItr.hasNext() ) {
 366           TempDescriptor valA = valItr.next();
 367
 368           Set<TempDescriptor> valsB = b.get( valA );
 369
 370           if( valsB == null ) {
 371             return false;
 372           }
 373
 374           if( !valsB.contains( keyA ) ) {
 375             return false;
 376           }
 377         }
 378       }
 379
 380       return true;
 381     }
 382
 383     public boolean equals( Object o ) {
 384       if( o == null ) {
 385         return false;
 386       }
 387       if( !(o instanceof InArrayRelation) ) {
 388         return false;
 389       }
 390       InArrayRelation rel = (InArrayRelation) o;
 391       return
 392         array2refees.equals( rel.array2refees ) &&
 393         refee2arrays.equals( rel.refee2arrays );
 394     }
 395
 396     public int hashCode() {
 397       return
 398         array2refees.hashCode() +
 399         refee2arrays.hashCode();
 400     }
 401   }
 402 }