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 //////////////////////////////////////////////////
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;
24 import Util.UtilAlgorithms;
29 public class ArrayReferencees {
31 ////////////////////////////////
33 ////////////////////////////////
34 public ArrayReferencees( State state, TypeUtil typeUtil, CallGraph callGraph ) {
35 init( state, typeUtil, callGraph );
38 public boolean doesNotCreateNewReaching( FlatSetElementNode fsen ) {
39 return noNewReaching.contains( fsen );
41 ////////////////////////////////
42 // end public interface
43 ////////////////////////////////
47 protected State state;
48 protected TypeUtil typeUtil;
49 protected CallGraph callGraph;
51 // maintain the relation at every program point
52 protected Hashtable<FlatNode, InArrayRelation> fn2rel;
54 // use relation to calculate set of array populate
55 // nodes that cannot create new reachability paths
56 protected Set<FlatSetElementNode> noNewReaching;
59 protected ArrayReferencees() {}
61 protected void init( State state,
63 CallGraph callGraph ) {
65 this.typeUtil = typeUtil;
66 this.callGraph = callGraph;
67 fn2rel = new Hashtable<FlatNode, InArrayRelation>();
68 noNewReaching = new HashSet<FlatSetElementNode>();
72 protected void buildRelation() {
73 Set<MethodDescriptor> descriptorsToAnalyze = null;
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);
84 descriptorsToAnalyze.addAll(callGraph.getAllMethods(tdSourceEntry));
86 //descriptorsToAnalyze.add( tdSourceEntry );
89 // analyze all methods transitively reachable from main
90 MethodDescriptor mdSourceEntry = typeUtil.getMain();
91 FlatMethod fmMain = state.getMethodFlat( mdSourceEntry );
93 descriptorsToAnalyze = callGraph.getAllMethods( mdSourceEntry );
94 descriptorsToAnalyze.add( mdSourceEntry );
97 for( MethodDescriptor md: descriptorsToAnalyze ) {
98 FlatMethod fm = state.getMethodFlat( md );
103 protected void analyzeMethod( FlatMethod fm ) {
104 Set<FlatNode> toVisit = new HashSet<FlatNode>();
107 while( !toVisit.isEmpty() ) {
108 FlatNode fn = toVisit.iterator().next();
109 toVisit.remove( fn );
111 // find the result flowing into this node
112 InArrayRelation rel = new InArrayRelation();
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 ) ) );
120 for( int i = 1; i < fn.numPrev(); ++i ) {
121 rel.intersect( fn2rel.get( fn.getPrev( i ) ) );
125 analyzeFlatNode( fn, rel );
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 );
139 protected void analyzeFlatNode( FlatNode fn,
140 InArrayRelation rel ) {
145 // use node type to transform relation
146 switch( fn.kind() ) {
148 case FKind.FlatElementNode:
150 FlatElementNode fen = (FlatElementNode) fn;
154 rel.put_array2refee( rhs, lhs );
157 case FKind.FlatSetElementNode:
159 FlatSetElementNode fsen = (FlatSetElementNode) fn;
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 );
170 // otherwise we can't be sure, so remove
171 noNewReaching.remove( fsen );
174 // then update the relation for the fixed-point
175 // analysis to continue
176 rel.put_array2refee( lhs, rhs );
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];
195 protected class InArrayRelation {
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;
204 public InArrayRelation() {
205 array2refees = new Hashtable< TempDescriptor, Set<TempDescriptor> >();
206 refee2arrays = new Hashtable< TempDescriptor, Set<TempDescriptor> >();
209 public boolean canArrayAlreadyReach( TempDescriptor array,
210 TempDescriptor elem ) {
212 Set<TempDescriptor> refees = array2refees.get( array );
213 return refees != null && refees.contains( elem );
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>();
223 array2refees.put( array, refees );
225 // and then the other
226 Set<TempDescriptor> arrays = refee2arrays.get( refee );
227 if( arrays == null ) {
228 arrays = new HashSet<TempDescriptor>();
231 refee2arrays.put( refee, arrays );
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
241 // during traversal, mark keys that should be removed
242 Set<TempDescriptor> a2rKeysToRemove = new HashSet<TempDescriptor>();
243 Set<TempDescriptor> r2aKeysToRemove = new HashSet<TempDescriptor>();
245 // also during traversal, mark sets by how they
246 // should be shortened
247 Hashtable<Set, Set> set2removals = new Hashtable<Set, Set>();
250 // first consider one side of the relation
251 Set<TempDescriptor> refees = array2refees.get( td );
252 if( refees != null ) {
253 assert !refees.isEmpty();
255 // definitely remove the key from this mapping
256 a2rKeysToRemove.add( td );
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();
263 Set<TempDescriptor> arrays = refee2arrays.get( ref );
264 assert arrays != null;
265 assert !arrays.isEmpty();
267 Set<TempDescriptor> removals = set2removals.get( arrays );
268 if( removals == null ) {
269 removals = new HashSet<TempDescriptor>();
272 set2removals.put( arrays, removals );
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 );
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();
290 // definitely remove the key from this mapping
291 r2aKeysToRemove.add( td );
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();
298 Set<TempDescriptor> refees = array2refees.get( arr );
299 assert refees != null;
300 assert !refees.isEmpty();
302 Set<TempDescriptor> removals = set2removals.get( refees );
303 if( removals == null ) {
304 removals = new HashSet<TempDescriptor>();
307 set2removals.put( refees, removals );
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 );
319 // perform all marked removing now
320 Iterator<TempDescriptor> keyItr;
322 keyItr = a2rKeysToRemove.iterator();
323 while( keyItr.hasNext() ) {
324 array2refees.remove( keyItr.next() );
327 keyItr = r2aKeysToRemove.iterator();
328 while( keyItr.hasNext() ) {
329 refee2arrays.remove( keyItr.next() );
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();
338 set.removeAll( removals );
345 public void merge( InArrayRelation r ) {
349 UtilAlgorithms.mergeHashtablesWithHashSetValues( array2refees, r.array2refees );
350 UtilAlgorithms.mergeHashtablesWithHashSetValues( refee2arrays, r.refee2arrays );
354 public void intersect( InArrayRelation r ) {
356 array2refees.clear();
357 refee2arrays.clear();
360 UtilAlgorithms.intersectHashtablesWithSetValues( array2refees, r.array2refees );
361 UtilAlgorithms.intersectHashtablesWithSetValues( refee2arrays, r.refee2arrays );
365 public void assertConsistent() {
366 assert allEntriesInAReversedInB( array2refees, refee2arrays );
367 assert allEntriesInAReversedInB( refee2arrays, array2refees );
370 protected boolean allEntriesInAReversedInB(
371 Hashtable< TempDescriptor, Set<TempDescriptor> > a,
372 Hashtable< TempDescriptor, Set<TempDescriptor> > b ) {
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();
380 Iterator<TempDescriptor> valItr = valsA.iterator();
381 while( valItr.hasNext() ) {
382 TempDescriptor valA = valItr.next();
384 Set<TempDescriptor> valsB = b.get( valA );
386 if( valsB == null ) {
390 if( !valsB.contains( keyA ) ) {
399 public boolean equals( Object o ) {
403 if( !(o instanceof InArrayRelation) ) {
406 InArrayRelation rel = (InArrayRelation) o;
408 array2refees.equals( rel.array2refees ) &&
409 refee2arrays.equals( rel.refee2arrays );
412 public int hashCode() {
414 array2refees.hashCode() +
415 refee2arrays.hashCode();