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