////////////////////////////////////////////////// // // The object of this analysis is to maintain a // relation for program points: // array variable -> variables referenced by the array's elements // // This analysis is useful in reachability analysis // because if a variable is read from an array, // then inserted back into the array, we can be // sure that no new reachability paths are created. // ////////////////////////////////////////////////// package Analysis; import IR.*; import Analysis.CallGraph.*; import IR.Flat.TempDescriptor; import IR.Flat.FlatMethod; import IR.Flat.FlatNode; import IR.Flat.FlatElementNode; import IR.Flat.FlatSetElementNode; import IR.Flat.FKind; import Util.UtilAlgorithms; import java.util.*; import java.io.*; public class ArrayReferencees { //////////////////////////////// // public interface //////////////////////////////// public ArrayReferencees( State state, TypeUtil typeUtil, CallGraph callGraph ) { init( state, typeUtil, callGraph ); } public boolean doesNotCreateNewReaching( FlatSetElementNode fsen ) { return noNewReaching.contains( fsen ); } //////////////////////////////// // end public interface //////////////////////////////// protected State state; protected TypeUtil typeUtil; protected CallGraph callGraph; // maintain the relation at every program point protected Hashtable fn2rel; // use relation to calculate set of array populate // nodes that cannot create new reachability paths protected Set noNewReaching; protected ArrayReferencees() {} protected void init( State state, TypeUtil typeUtil, CallGraph callGraph ) { this.state = state; this.typeUtil = typeUtil; this.callGraph = callGraph; fn2rel = new Hashtable(); noNewReaching = new HashSet(); buildRelation(); } protected void buildRelation() { Set descriptorsToAnalyze = null; if(state.TASK) { // for Bristlecone and Bamboo, there are no main method, // analyze all methods transitively reachable from tasks instead Iterator it_sourceEntries = state.getTaskSymbolTable().getDescriptorsIterator(); while(it_sourceEntries.hasNext()) { TaskDescriptor tdSourceEntry = (TaskDescriptor)it_sourceEntries.next(); if(descriptorsToAnalyze == null) { descriptorsToAnalyze = callGraph.getAllMethods(tdSourceEntry); } else { descriptorsToAnalyze.addAll(callGraph.getAllMethods(tdSourceEntry)); } //descriptorsToAnalyze.add( tdSourceEntry ); } } else { // analyze all methods transitively reachable from main MethodDescriptor mdSourceEntry = typeUtil.getMain(); FlatMethod fmMain = state.getMethodFlat( mdSourceEntry ); descriptorsToAnalyze = callGraph.getAllMethods( mdSourceEntry ); descriptorsToAnalyze.add( mdSourceEntry ); } for( MethodDescriptor md: descriptorsToAnalyze ) { FlatMethod fm = state.getMethodFlat( md ); analyzeMethod( fm ); } } protected void analyzeMethod( FlatMethod fm ) { Set toVisit = new HashSet(); toVisit.add( fm ); while( !toVisit.isEmpty() ) { FlatNode fn = toVisit.iterator().next(); toVisit.remove( fn ); // find the result flowing into this node InArrayRelation rel = new InArrayRelation(); // the join operation is intersection, so // merge with 1st predecessor (if any) and // then do intersect with all others if( fn.numPrev() > 0 ) { rel.merge( fn2rel.get( fn.getPrev( 0 ) ) ); for( int i = 1; i < fn.numPrev(); ++i ) { rel.intersect( fn2rel.get( fn.getPrev( i ) ) ); } } analyzeFlatNode( fn, rel ); // enqueue child nodes if new results were found InArrayRelation relPrev = fn2rel.get( fn ); if( !rel.equals( relPrev ) ) { fn2rel.put( fn, rel ); for( int i = 0; i < fn.numNext(); i++ ) { FlatNode nn = fn.getNext( i ); toVisit.add( nn ); } } } } protected void analyzeFlatNode( FlatNode fn, InArrayRelation rel ) { TempDescriptor lhs; TempDescriptor rhs; // use node type to transform relation switch( fn.kind() ) { case FKind.FlatElementNode: // lhs = rhs[...] FlatElementNode fen = (FlatElementNode) fn; lhs = fen.getDst(); rhs = fen.getSrc(); rel.remove( lhs ); rel.put_array2refee( rhs, lhs ); break; case FKind.FlatSetElementNode: // lhs[...] = rhs FlatSetElementNode fsen = (FlatSetElementNode) fn; lhs = fsen.getDst(); rhs = fsen.getSrc(); // use relation result coming into this program // point ("rel" before we modify it) to compute // whether this node affects reachability paths if( rel.canArrayAlreadyReach( lhs, rhs ) ) { noNewReaching.add( fsen ); } else { // otherwise we can't be sure, so remove noNewReaching.remove( fsen ); } // then update the relation for the fixed-point // analysis to continue rel.put_array2refee( lhs, rhs ); break; default: // the default action is to remove every temp // written by this node from the relation TempDescriptor[] writeTemps = fn.writesTemps(); for( int i = 0; i < writeTemps.length; ++i ) { TempDescriptor td = writeTemps[i]; rel.remove( td ); } break; } } protected class InArrayRelation { // The relation is possibly dense, in that any variable might // be referenced by many arrays, and an array may reference // many variables. So maintain the relation as two hashtables // that are redundant but allow efficient operations protected Hashtable< TempDescriptor, Set > array2refees; protected Hashtable< TempDescriptor, Set > refee2arrays; public InArrayRelation() { array2refees = new Hashtable< TempDescriptor, Set >(); refee2arrays = new Hashtable< TempDescriptor, Set >(); } public boolean canArrayAlreadyReach( TempDescriptor array, TempDescriptor elem ) { Set refees = array2refees.get( array ); return refees != null && refees.contains( elem ); } public void put_array2refee( TempDescriptor array, TempDescriptor refee ) { // update one direction Set refees = array2refees.get( array ); if( refees == null ) { refees = new HashSet(); } refees.add( refee ); array2refees.put( array, refees ); // and then the other Set arrays = refee2arrays.get( refee ); if( arrays == null ) { arrays = new HashSet(); } arrays.add( array ); refee2arrays.put( refee, arrays ); assertConsistent(); } public void remove( TempDescriptor td ) { // removal of one temp from the relation is a bit // tricky--it can be on either side of the pair or // both at the same time // during traversal, mark keys that should be removed Set a2rKeysToRemove = new HashSet(); Set r2aKeysToRemove = new HashSet(); // also during traversal, mark sets by how they // should be shortened Hashtable set2removals = new Hashtable(); { // first consider one side of the relation Set refees = array2refees.get( td ); if( refees != null ) { assert !refees.isEmpty(); // definitely remove the key from this mapping a2rKeysToRemove.add( td ); // and remove it from set values in the other mapping Iterator refItr = refees.iterator(); while( refItr.hasNext() ) { TempDescriptor ref = refItr.next(); Set arrays = refee2arrays.get( ref ); assert arrays != null; assert !arrays.isEmpty(); Set removals = set2removals.get( arrays ); if( removals == null ) { removals = new HashSet(); } removals.add( td ); set2removals.put( arrays, removals ); if( removals.size() == arrays.size() ) { // we've marked everything in this for removal! So // just remove the key from the mapping assert arrays.containsAll( removals ); r2aKeysToRemove.add( ref ); } } } } { // and then see if it is in the relation's other direction Set arrays = refee2arrays.get( td ); if( arrays != null ) { assert !arrays.isEmpty(); // definitely remove the key from this mapping r2aKeysToRemove.add( td ); // and remove it from set values in the other mapping Iterator arrItr = arrays.iterator(); while( arrItr.hasNext() ) { TempDescriptor arr = arrItr.next(); Set refees = array2refees.get( arr ); assert refees != null; assert !refees.isEmpty(); Set removals = set2removals.get( refees ); if( removals == null ) { removals = new HashSet(); } removals.add( td ); set2removals.put( refees, removals ); if( removals.size() == refees.size() ) { // we've marked everything in this for removal! So // just remove the key from the mapping assert refees.containsAll( removals ); a2rKeysToRemove.add( arr ); } } } } // perform all marked removing now Iterator keyItr; keyItr = a2rKeysToRemove.iterator(); while( keyItr.hasNext() ) { array2refees.remove( keyItr.next() ); } keyItr = r2aKeysToRemove.iterator(); while( keyItr.hasNext() ) { refee2arrays.remove( keyItr.next() ); } Iterator meItr = set2removals.entrySet().iterator(); while( meItr.hasNext() ) { Map.Entry me = (Map.Entry) meItr.next(); Set set = (Set) me.getKey(); Set removals = (Set) me.getValue(); set.removeAll( removals ); } assertConsistent(); } public void merge( InArrayRelation r ) { if( r == null ) { return; } UtilAlgorithms.mergeHashtablesWithHashSetValues( array2refees, r.array2refees ); UtilAlgorithms.mergeHashtablesWithHashSetValues( refee2arrays, r.refee2arrays ); assertConsistent(); } public void intersect( InArrayRelation r ) { if( r == null ) { array2refees.clear(); refee2arrays.clear(); return; } UtilAlgorithms.intersectHashtablesWithSetValues( array2refees, r.array2refees ); UtilAlgorithms.intersectHashtablesWithSetValues( refee2arrays, r.refee2arrays ); assertConsistent(); } public void assertConsistent() { assert allEntriesInAReversedInB( array2refees, refee2arrays ); assert allEntriesInAReversedInB( refee2arrays, array2refees ); } protected boolean allEntriesInAReversedInB( Hashtable< TempDescriptor, Set > a, Hashtable< TempDescriptor, Set > b ) { Iterator mapItr = a.entrySet().iterator(); while( mapItr.hasNext() ) { Map.Entry me = (Map.Entry) mapItr.next(); TempDescriptor keyA = (TempDescriptor) me.getKey(); Set valsA = (Set) me.getValue(); Iterator valItr = valsA.iterator(); while( valItr.hasNext() ) { TempDescriptor valA = valItr.next(); Set valsB = b.get( valA ); if( valsB == null ) { return false; } if( !valsB.contains( keyA ) ) { return false; } } } return true; } public boolean equals( Object o ) { if( o == null ) { return false; } if( !(o instanceof InArrayRelation) ) { return false; } InArrayRelation rel = (InArrayRelation) o; return array2refees.equals( rel.array2refees ) && refee2arrays.equals( rel.refee2arrays ); } public int hashCode() { return array2refees.hashCode() + refee2arrays.hashCode(); } } }