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.Flat.FlatMethod;
  18 import IR.Flat.FlatNode;
  19 import IR.Flat.FlatCall;
  20 import IR.Flat.FKind;
  21 import IR.Descriptor;
  22 import IR.ClassDescriptor;
  23 import IR.MethodDescriptor;
  24 import IR.TaskDescriptor;
  25 import IR.TypeDescriptor;
  26 import Util.UtilAlgorithms;
  27 import java.util.*;
  28 import java.io.*;
  29
  30
  31 public class ArrayReferencees {
  32
  33   ////////////////////////////////
  34   // public interface
  35   ////////////////////////////////
  36   public ArrayReferencees( State state ) {
  37     init( state );
  38   }
  39
  40   public boolean mayCreateNewReachabilityPaths( FlatSetElementNode fsen ) {
  41     return true;
  42   }
  43   ////////////////////////////////
  44   // end public interface
  45   ////////////////////////////////
  46
  47
  48
  49   protected State state;
  50
  51   // maintain the relation at every program point
  52   protected Hashtable<FlatNode, InArrayRelation> fn2rel;
  53
  54
  55   protected ArrayReferencees() {}
  56
  57   protected void init( State state ) {
  58     this.state = state;
  59     fn2rel = new Hashtable<FlatNode, InArrayRelation>();
  60     buildRelation();
  61   }
  62
  63   protected void buildRelation() {
  64     // just analyze every method of every class that the
  65     // compiler has code for, fix if this is too costly
  66     Iterator classItr = state.getClassSymbolTable().getDescriptorsIterator();
  67     while( classItr.hasNext() ) {
  68       ClassDescriptor cd = (ClassDescriptor)classItr.next();
  69
  70       Iterator methodItr = cd.getMethods();
  71       while( methodItr.hasNext() ) {
  72         MethodDescriptor md = (MethodDescriptor)methodItr.next();
  73
  74         FlatMethod fm = state.getMethodFlat( md );
  75         analyzeMethod( fm );
  76       }
  77     }
  78   }
  79
  80   protected void analyzeMethod( FlatMethod fm ) {
  81     Set<FlatNode> toVisit = new HashSet<FlatNode>();
  82     toVisit.add( fm );
  83
  84     while( !toVisit.isEmpty() ) {
  85       FlatNode fn = toVisit.iterator().next();
  86       toVisit.remove( fn );
  87
  88       // find the result flowing into this node
  89       InArrayRelation rel = new InArrayRelation();
  90
  91       // the join operation is intersection, so
  92       // merge with 1st predecessor (if any) and
  93       // then do intersect with all others
  94       if( fn.numPrev() > 0 ) {
  95         rel.merge( fn2rel.get( fn.getPrev( 0 ) ) );
  96
  97         for( int i = 1; i < fn.numPrev(); ++i ) {
  98           rel.intersect( fn2rel.get( fn.getPrev( i ) ) );
  99         }
 100       }
 101
 102       analyzeFlatNode( rel, fn );
 103
 104       // enqueue child nodes if new results were found
 105       InArrayRelation relPrev = fn2rel.get( fn );
 106       if( !rel.equals( relPrev ) ) {
 107         fn2rel.put( fn, rel );
 108         for( int i = 0; i < fn.numNext(); i++ ) {
 109           FlatNode nn = fn.getNext( i );
 110           toVisit.add( nn );
 111         }
 112       }
 113     }
 114   }
 115
 116   protected void analyzeFlatNode( FlatNode fn,
 117                                   InArrayRelation rel ) {
 118
 119     TempDescriptor lhs;
 120     TempDescriptor rhs;
 121
 122     // use node type to transform relation
 123     switch( fn.kind() ) {
 124
 125     case FKind.FlatElementNode:
 126       // lhs = rhs[...]
 127       FlatElementNode fen = (FlatElementNode) fn;
 128       lhs = fen.getDst();
 129       rhs = fen.getSrc();
 130       rel.remove( lhs );
 131       rel.put_array2refee( rhs, lhs );
 132       break;
 133
 134     case FKind.FlatSetElementNode:
 135       // lhs[...] = rhs
 136       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 137       lhs = fsen.getDst();
 138       rhs = fsen.getSrc();
 139       rel.put_array2refee( lhs, rhs );
 140       break;
 141
 142     default:
 143       // the default action is to remove every temp
 144       // written by this node from the relation
 145       TempDescriptor[] writeTemps = fn.writesTemps();
 146       for( int i = 0; i < writeTemps.length; ++i ) {
 147         TempDescriptor td = writeTemps[i];
 148         rel.remove( td );
 149       }
 150       break;
 151
 152     }
 153   }
 154 }
 155
 156
 157
 158 protected class InArrayRelation {
 159
 160   // The relation is possibly dense, in that any variable might
 161   // be referenced by many arrays, and an array may reference
 162   // many variables.  So maintain the relation as two hashtables
 163   // that are redundant but allow efficient operations
 164   protected Hashtable< TempDescriptor, Set<TempDescriptor> > array2refees;
 165   protected Hashtable< TempDescriptor, Set<TempDescriptor> > refee2arrays;
 166
 167   public InArrayRelation() {
 168     array2refees = new Hashtable< TempDescriptor, Set<TempDescriptor> >();
 169     refee2arrays = new Hashtable< TempDescriptor, Set<TempDescriptor> >();
 170   }
 171
 172   public void put_array2refee( TempDescriptor array, TempDescriptor refee ) {
 173     // update one direction
 174     Set<TempDescriptor> refees = array2refees.get( array );
 175     if( refees == null ) {
 176       refees = new HashSet<TempDescriptor>();
 177     }
 178     refees.add( refee );
 179     array2refees.put( array, refees );
 180
 181     // and then the other
 182     Set<TempDescriptor> arrays = refee2arrays.get( refee );
 183     if( arrayss == null ) {
 184       arrays = new HashSet<TempDescriptor>();
 185     }
 186     arrays.add( array );
 187     refee2arrays.put( refee, arrays );
 188
 189     assertConsistent();
 190   }
 191
 192   public void remove( TempDescriptor td ) {
 193
 194
 195     assertConsistent();
 196   }
 197
 198   public void merge( InArrayRelation r ) {
 199     if( r == null ) {
 200       return;
 201     }
 202     UtilAlgorithms.mergeHashtablesWithHashSetValues( array2refees, r.array2refees );
 203     UtilAlgorithms.mergeHashtablesWithHashSetValues( refee2arrays, r.refee2arrays );
 204     assertConsistent();
 205   }
 206
 207   public void intersect( InArrayRelation r ) {
 208     if( r == null ) {
 209       array2refees.clear();
 210       refee2arrays.clear();
 211       return;
 212     }
 213     UtilAlgorithms.intersectHashtablesWithSetValues( array2refees, r.array2refees );
 214     UtilAlgorithms.intersectHashtablesWithSetValues( refee2arrays, r.refee2arrays );
 215     assertConsistent();
 216   }
 217
 218   public void assertConsistent() {
 219     assert allEntriesInAReversedInB( array2refees, refee2arrays );
 220     assert allEntriesInAReversedInB( refee2arrays, array2refees );
 221   }
 222
 223   protected boolean allEntriesInAReversedInB(
 224     Hashtable< TempDescriptor, Set<TempDescriptor> > a,
 225     Hashtable< TempDescriptor, Set<TempDescriptor> > b ) {
 226
 227     Iterator mapItr = a.entrySet().iterator();
 228     while( mapItr.hasNext() ) {
 229       Map.Entry           me    = (Map.Entry)           mapItr.next();
 230       TempDescriptor      keyA  = (TempDescriptor)      me.getKey();
 231       Set<TempDescriptor> valsA = (Set<TempDescriptor>) me.getValue();
 232
 233       Iterator<TempDescriptor> valItr = valsA.iterator();
 234       while( valItr.hasNext() ) {
 235         TempDescriptor valA = valItr.next();
 236
 237         Set<TempDescriptor> valsB = b.get( valA );
 238
 239         if( valsB == null ) {
 240           return false;
 241         }
 242
 243         if( !valsB.contains( keyA ) ) {
 244           return false;
 245         }
 246       }
 247     }
 248
 249     return true;
 250   }
 251
 252   public boolean equals( Object o ) {
 253     if( o == null ) {
 254       return false;
 255     }
 256     if( !(o instanceof InArrayRelation) ) {
 257       return false;
 258     }
 259     InArrayRelation rel = (InArrayRelation) o;
 260     return
 261       array2refees.equals( rel.array2refees ) &&
 262       refee2arrays.equals( rel.refee2arrays );
 263   }
 264
 265   public int hashCode() {
 266     return
 267       array2refees.hashCode() +
 268       refee2arrays.hashCode();
 269   }
 270 }