From 9a5c940b95f5e994bfedfa590ca0a4d284ad54b9 Mon Sep 17 00:00:00 2001 From: jjenista Date: Fri, 30 Oct 2009 01:11:01 +0000 Subject: [PATCH] an analysis for maintaining a relation at each program point of array temps to temps that are referenced by that array's elements--needs a few more pieces --- Robust/src/Analysis/ArrayReferencees.java | 270 ++++++++++++++++++++++ Robust/src/Util/UtilAlgorithms.java | 42 ++++ 2 files changed, 312 insertions(+) create mode 100644 Robust/src/Analysis/ArrayReferencees.java diff --git a/Robust/src/Analysis/ArrayReferencees.java b/Robust/src/Analysis/ArrayReferencees.java new file mode 100644 index 00000000..5e351538 --- /dev/null +++ b/Robust/src/Analysis/ArrayReferencees.java @@ -0,0 +1,270 @@ +////////////////////////////////////////////////// +// +// 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.State; +import IR.Flat.FlatMethod; +import IR.Flat.FlatNode; +import IR.Flat.FlatCall; +import IR.Flat.FKind; +import IR.Descriptor; +import IR.ClassDescriptor; +import IR.MethodDescriptor; +import IR.TaskDescriptor; +import IR.TypeDescriptor; +import Util.UtilAlgorithms; +import java.util.*; +import java.io.*; + + +public class ArrayReferencees { + + //////////////////////////////// + // public interface + //////////////////////////////// + public ArrayReferencees( State state ) { + init( state ); + } + + public boolean mayCreateNewReachabilityPaths( FlatSetElementNode fsen ) { + return true; + } + //////////////////////////////// + // end public interface + //////////////////////////////// + + + + protected State state; + + // maintain the relation at every program point + protected Hashtable fn2rel; + + + protected ArrayReferencees() {} + + protected void init( State state ) { + this.state = state; + fn2rel = new Hashtable(); + buildRelation(); + } + + protected void buildRelation() { + // just analyze every method of every class that the + // compiler has code for, fix if this is too costly + Iterator classItr = state.getClassSymbolTable().getDescriptorsIterator(); + while( classItr.hasNext() ) { + ClassDescriptor cd = (ClassDescriptor)classItr.next(); + + Iterator methodItr = cd.getMethods(); + while( methodItr.hasNext() ) { + MethodDescriptor md = (MethodDescriptor)methodItr.next(); + + 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( rel, fn ); + + // 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(); + 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 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( arrayss == null ) { + arrays = new HashSet(); + } + arrays.add( array ); + refee2arrays.put( refee, arrays ); + + assertConsistent(); + } + + public void remove( TempDescriptor td ) { + + + 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(); + } +} diff --git a/Robust/src/Util/UtilAlgorithms.java b/Robust/src/Util/UtilAlgorithms.java index fd021d05..e9ca7981 100644 --- a/Robust/src/Util/UtilAlgorithms.java +++ b/Robust/src/Util/UtilAlgorithms.java @@ -31,4 +31,46 @@ public class UtilAlgorithms { } } + + // This method makes hashtable a the intersection of + // itself and hashtable b, where the new key set is the + // intersection. The values are sets, so if a key is + // common its new value should be the intersection of + // the existing values in a and b. If a new value is + // the empty set, then also remove that key. + static public void intersectHashtablesWithSetValues( Hashtable a, + Hashtable b ) { + Set keysToRemove = new HashSet(); + + Iterator mapItr = a.entrySet().iterator(); + while( mapItr.hasNext() ) { + Map.Entry me = (Map.Entry) mapItr.next(); + Object akey = (Object) me.getKey(); + Set avals = (Set) me.getValue(); + Set bvals = (Set) b.get( akey ); + + if( bvals == null ) { + // if b doesn't have the key, mark it for + // safe removal after we traverse the map + keysToRemove.add( akey ); + + } else { + // otherwise we have the key, but pare + // down the value set, if needed, and if + // nothing is left, remove the key, too + avals.retainAll( bvals ); + if( avals.isEmpty() ) { + keysToRemove.add( akey ); + } + } + } + + // then safely remove keys + Iterator keyItr = keysToRemove.iterator(); + while( keyItr.hasNext() ) { + Object key = keyItr.next(); + a.remove( key ); + } + } + } -- 2.34.1