1 //////////////////////////////////////////////////
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
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.
12 //////////////////////////////////////////////////
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;
28 import Util.UtilAlgorithms;
33 public class ArrayReferencees {
35 ////////////////////////////////
37 ////////////////////////////////
38 public ArrayReferencees( State state ) {
42 public boolean doesNotCreateNewReaching( FlatSetElementNode fsen ) {
43 return noNewReaching.contains( fsen );
45 ////////////////////////////////
46 // end public interface
47 ////////////////////////////////
51 protected State state;
53 // maintain the relation at every program point
54 protected Hashtable<FlatNode, InArrayRelation> fn2rel;
56 // use relation to calculate set of array populate
57 // nodes that cannot create new reachability paths
58 protected Set<FlatSetElementNode> noNewReaching;
61 protected ArrayReferencees() {}
63 protected void init( State state ) {
65 fn2rel = new Hashtable<FlatNode, InArrayRelation>();
66 noNewReaching = new HashSet<FlatSetElementNode>();
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();
77 Iterator methodItr = cd.getMethods();
78 while( methodItr.hasNext() ) {
79 MethodDescriptor md = (MethodDescriptor)methodItr.next();
81 FlatMethod fm = state.getMethodFlat( md );
87 protected void analyzeMethod( FlatMethod fm ) {
88 Set<FlatNode> toVisit = new HashSet<FlatNode>();
91 while( !toVisit.isEmpty() ) {
92 FlatNode fn = toVisit.iterator().next();
95 // find the result flowing into this node
96 InArrayRelation rel = new InArrayRelation();
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 ) ) );
104 for( int i = 1; i < fn.numPrev(); ++i ) {
105 rel.intersect( fn2rel.get( fn.getPrev( i ) ) );
109 analyzeFlatNode( fn, rel );
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 );
123 protected void analyzeFlatNode( FlatNode fn,
124 InArrayRelation rel ) {
129 // use node type to transform relation
130 switch( fn.kind() ) {
132 case FKind.FlatElementNode:
134 FlatElementNode fen = (FlatElementNode) fn;
138 rel.put_array2refee( rhs, lhs );
141 case FKind.FlatSetElementNode:
143 FlatSetElementNode fsen = (FlatSetElementNode) fn;
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 );
154 // otherwise we can't be sure, so remove
155 noNewReaching.remove( fsen );
158 // then update the relation for the fixed-point
159 // analysis to continue
160 rel.put_array2refee( lhs, rhs );
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];
179 protected class InArrayRelation {
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;
188 public InArrayRelation() {
189 array2refees = new Hashtable< TempDescriptor, Set<TempDescriptor> >();
190 refee2arrays = new Hashtable< TempDescriptor, Set<TempDescriptor> >();
193 public boolean canArrayAlreadyReach( TempDescriptor array,
194 TempDescriptor elem ) {
196 Set<TempDescriptor> refees = array2refees.get( array );
197 return refees != null && refees.contains( elem );
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>();
207 array2refees.put( array, refees );
209 // and then the other
210 Set<TempDescriptor> arrays = refee2arrays.get( refee );
211 if( arrays == null ) {
212 arrays = new HashSet<TempDescriptor>();
215 refee2arrays.put( refee, arrays );
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
225 // during traversal, mark keys that should be removed
226 Set<TempDescriptor> a2rKeysToRemove = new HashSet<TempDescriptor>();
227 Set<TempDescriptor> r2aKeysToRemove = new HashSet<TempDescriptor>();
229 // also during traversal, mark sets by how they
230 // should be shortened
231 Hashtable<Set, Set> set2removals = new Hashtable<Set, Set>();
234 // first consider one side of the relation
235 Set<TempDescriptor> refees = array2refees.get( td );
236 if( refees != null ) {
237 assert !refees.isEmpty();
239 // definitely remove the key from this mapping
240 a2rKeysToRemove.add( td );
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();
247 Set<TempDescriptor> arrays = refee2arrays.get( ref );
248 assert arrays != null;
249 assert !arrays.isEmpty();
251 Set<TempDescriptor> removals = set2removals.get( arrays );
252 if( removals == null ) {
253 removals = new HashSet<TempDescriptor>();
256 set2removals.put( arrays, removals );
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 );
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();
274 // definitely remove the key from this mapping
275 r2aKeysToRemove.add( td );
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();
282 Set<TempDescriptor> refees = array2refees.get( arr );
283 assert refees != null;
284 assert !refees.isEmpty();
286 Set<TempDescriptor> removals = set2removals.get( refees );
287 if( removals == null ) {
288 removals = new HashSet<TempDescriptor>();
291 set2removals.put( refees, removals );
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 );
303 // perform all marked removing now
304 Iterator<TempDescriptor> keyItr;
306 keyItr = a2rKeysToRemove.iterator();
307 while( keyItr.hasNext() ) {
308 array2refees.remove( keyItr.next() );
311 keyItr = r2aKeysToRemove.iterator();
312 while( keyItr.hasNext() ) {
313 refee2arrays.remove( keyItr.next() );
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();
322 set.removeAll( removals );
329 public void merge( InArrayRelation r ) {
333 UtilAlgorithms.mergeHashtablesWithHashSetValues( array2refees, r.array2refees );
334 UtilAlgorithms.mergeHashtablesWithHashSetValues( refee2arrays, r.refee2arrays );
338 public void intersect( InArrayRelation r ) {
340 array2refees.clear();
341 refee2arrays.clear();
344 UtilAlgorithms.intersectHashtablesWithSetValues( array2refees, r.array2refees );
345 UtilAlgorithms.intersectHashtablesWithSetValues( refee2arrays, r.refee2arrays );
349 public void assertConsistent() {
350 assert allEntriesInAReversedInB( array2refees, refee2arrays );
351 assert allEntriesInAReversedInB( refee2arrays, array2refees );
354 protected boolean allEntriesInAReversedInB(
355 Hashtable< TempDescriptor, Set<TempDescriptor> > a,
356 Hashtable< TempDescriptor, Set<TempDescriptor> > b ) {
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();
364 Iterator<TempDescriptor> valItr = valsA.iterator();
365 while( valItr.hasNext() ) {
366 TempDescriptor valA = valItr.next();
368 Set<TempDescriptor> valsB = b.get( valA );
370 if( valsB == null ) {
374 if( !valsB.contains( keyA ) ) {
383 public boolean equals( Object o ) {
387 if( !(o instanceof InArrayRelation) ) {
390 InArrayRelation rel = (InArrayRelation) o;
392 array2refees.equals( rel.array2refees ) &&
393 refee2arrays.equals( rel.refee2arrays );
396 public int hashCode() {
398 array2refees.hashCode() +
399 refee2arrays.hashCode();