From b28eb53cc507ab65a6cc1a7d97e0bb7249e1f226 Mon Sep 17 00:00:00 2001 From: jjenista Date: Fri, 30 Oct 2009 20:30:18 +0000 Subject: [PATCH] new analysis for array references that create no new reachability is in, and correctly finds the set of FlatSetElementNode objects that we are expecting to be able to skip. Disjointness results still the same, more checking to do --- Robust/src/Analysis/ArrayReferencees.java | 328 ++++++++++++------ Robust/src/Analysis/MLP/MLPAnalysis.java | 14 +- .../OwnershipAnalysis/OwnershipAnalysis.java | 42 ++- .../mlp-small-for-testing/FlightList.java | 12 +- .../mlp-small-for-testing/MessageList.java | 14 +- .../directto/mlp-small-for-testing/makefile | 15 +- Robust/src/Main/Main.java | 7 + 7 files changed, 307 insertions(+), 125 deletions(-) diff --git a/Robust/src/Analysis/ArrayReferencees.java b/Robust/src/Analysis/ArrayReferencees.java index 5e351538..0aa28df6 100644 --- a/Robust/src/Analysis/ArrayReferencees.java +++ b/Robust/src/Analysis/ArrayReferencees.java @@ -14,15 +14,17 @@ 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 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.*; @@ -37,8 +39,8 @@ public class ArrayReferencees { init( state ); } - public boolean mayCreateNewReachabilityPaths( FlatSetElementNode fsen ) { - return true; + public boolean doesNotCreateNewReaching( FlatSetElementNode fsen ) { + return noNewReaching.contains( fsen ); } //////////////////////////////// // end public interface @@ -51,12 +53,17 @@ public class ArrayReferencees { // 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 ) { this.state = state; fn2rel = new Hashtable(); + noNewReaching = new HashSet(); buildRelation(); } @@ -99,7 +106,7 @@ public class ArrayReferencees { } } - analyzeFlatNode( rel, fn ); + analyzeFlatNode( fn, rel ); // enqueue child nodes if new results were found InArrayRelation relPrev = fn2rel.get( fn ); @@ -136,6 +143,20 @@ public class ArrayReferencees { 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; @@ -151,120 +172,231 @@ public class ArrayReferencees { } } -} -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 >(); - } + protected class InArrayRelation { - public void put_array2refee( TempDescriptor array, TempDescriptor refee ) { - // update one direction - Set refees = array2refees.get( array ); - if( refees == null ) { - refees = new HashSet(); + // 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 >(); } - refees.add( refee ); - array2refees.put( array, refees ); - // and then the other - Set arrays = refee2arrays.get( refee ); - if( arrayss == null ) { - arrays = new HashSet(); + public boolean canArrayAlreadyReach( TempDescriptor array, + TempDescriptor elem ) { + + Set refees = array2refees.get( array ); + return refees != null && refees.contains( elem ); } - arrays.add( array ); - refee2arrays.put( refee, arrays ); + + 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(); - } + 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(); - public void remove( TempDescriptor td ) { + { + // 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; + assertConsistent(); } - 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 ) { + 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 ); + } - 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(); + protected boolean allEntriesInAReversedInB( + Hashtable< TempDescriptor, Set > a, + Hashtable< TempDescriptor, Set > b ) { - Iterator valItr = valsA.iterator(); - while( valItr.hasNext() ) { - TempDescriptor valA = valItr.next(); + 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(); - Set valsB = b.get( valA ); + Iterator valItr = valsA.iterator(); + while( valItr.hasNext() ) { + TempDescriptor valA = valItr.next(); - if( valsB == null ) { - return false; - } - - if( !valsB.contains( keyA ) ) { - return false; + 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; + return true; } - if( !(o instanceof InArrayRelation) ) { - return false; + + 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 ); } - InArrayRelation rel = (InArrayRelation) o; - return - array2refees.equals( rel.array2refees ) && - refee2arrays.equals( rel.refee2arrays ); - } - public int hashCode() { - return - array2refees.hashCode() + - refee2arrays.hashCode(); - } + public int hashCode() { + return + array2refees.hashCode() + + refee2arrays.hashCode(); + } + } } diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 64cea770..c031a12a 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -213,11 +213,15 @@ public class MLPAnalysis { // disjoint analysis with a set of flagged allocation sites of live-in variable try { - OwnershipAnalysis oa2 = new OwnershipAnalysis(state, tu, callGraph, new Liveness(), - state.OWNERSHIPALLOCDEPTH, false, - false, state.OWNERSHIPALIASFILE, - state.METHODEFFECTS, - mapMethodContextToLiveInAllocationSiteSet); + OwnershipAnalysis oa2 = new OwnershipAnalysis(state, + tu, + callGraph, + ownAnalysis.liveness, + ownAnalysis.arrayReferencees, + state.OWNERSHIPALLOCDEPTH, false, + false, state.OWNERSHIPALIASFILE, + state.METHODEFFECTS, + mapMethodContextToLiveInAllocationSiteSet); // debug methItr = oa2.descriptorsToAnalyze.iterator(); while (methItr.hasNext()) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index 19862e12..17f9c02d 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -2,6 +2,7 @@ package Analysis.OwnershipAnalysis; import Analysis.CallGraph.*; import Analysis.Liveness; +import Analysis.ArrayReferencees; import IR.*; import IR.Flat.*; import IR.Tree.Modifiers; @@ -314,11 +315,12 @@ public class OwnershipAnalysis { // data from the compiler - public State state; - public CallGraph callGraph; - public Liveness liveness; - public TypeUtil typeUtil; - public int allocationDepth; + public State state; + public CallGraph callGraph; + public Liveness liveness; + public ArrayReferencees arrayReferencees; + public TypeUtil typeUtil; + public int allocationDepth; // for public interface methods to warn that they // are grabbing results during analysis @@ -396,13 +398,14 @@ public class OwnershipAnalysis { TypeUtil tu, CallGraph callGraph, Liveness liveness, + ArrayReferencees ar, int allocationDepth, boolean writeDOTs, boolean writeAllDOTs, String aliasFile) throws java.io.IOException { this.methodEffects = false; - init(state,tu,callGraph,liveness,allocationDepth,writeDOTs,writeAllDOTs,aliasFile); + init(state,tu,callGraph,liveness,ar,allocationDepth,writeDOTs,writeAllDOTs,aliasFile); } @@ -410,6 +413,7 @@ public class OwnershipAnalysis { TypeUtil tu, CallGraph callGraph, Liveness liveness, + ArrayReferencees ar, int allocationDepth, boolean writeDOTs, boolean writeAllDOTs, @@ -417,7 +421,7 @@ public class OwnershipAnalysis { boolean methodEffects) throws java.io.IOException { this.methodEffects = methodEffects; - init(state,tu,callGraph,liveness,allocationDepth,writeDOTs,writeAllDOTs,aliasFile); + init(state,tu,callGraph,liveness,ar,allocationDepth,writeDOTs,writeAllDOTs,aliasFile); } @@ -427,6 +431,7 @@ public class OwnershipAnalysis { TypeUtil tu, CallGraph callGraph, Liveness liveness, + ArrayReferencees ar, int allocationDepth, boolean writeDOTs, boolean writeAllDOTs, @@ -437,7 +442,7 @@ public class OwnershipAnalysis { this.methodEffects = methodEffects; this.mapMethodContextToLiveInAllocationSiteSet=mapMethodContextToLiveInAllocationSiteSet; - init(state, tu, callGraph, liveness, allocationDepth, writeDOTs, writeAllDOTs, + init(state, tu, callGraph, liveness, ar, allocationDepth, writeDOTs, writeAllDOTs, aliasFile); } @@ -446,6 +451,7 @@ public class OwnershipAnalysis { TypeUtil tu, CallGraph callGraph, Liveness liveness, + ArrayReferencees ar, int allocationDepth, boolean writeDOTs, boolean writeAllDOTs, @@ -453,13 +459,14 @@ public class OwnershipAnalysis { analysisComplete = false; - this.state = state; - this.typeUtil = tu; - this.callGraph = callGraph; - this.liveness = liveness; - this.allocationDepth = allocationDepth; - this.writeDOTs = writeDOTs; - this.writeAllDOTs = writeAllDOTs; + this.state = state; + this.typeUtil = tu; + this.callGraph = callGraph; + this.liveness = liveness; + this.arrayReferencees = ar; + this.allocationDepth = allocationDepth; + this.writeDOTs = writeDOTs; + this.writeAllDOTs = writeAllDOTs; // set some static configuration for OwnershipGraphs OwnershipGraph.allocationDepth = allocationDepth; @@ -946,6 +953,11 @@ public class OwnershipAnalysis { case FKind.FlatSetElementNode: FlatSetElementNode fsen = (FlatSetElementNode) fn; + + if( arrayReferencees.doesNotCreateNewReaching( fsen ) ) { + System.out.println( "Skipping no-heap-effect: "+fsen ); + } + lhs = fsen.getDst(); rhs = fsen.getSrc(); if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) { diff --git a/Robust/src/Benchmarks/mlp/directto/mlp-small-for-testing/FlightList.java b/Robust/src/Benchmarks/mlp/directto/mlp-small-for-testing/FlightList.java index 1d9a500a..746516ec 100644 --- a/Robust/src/Benchmarks/mlp/directto/mlp-small-for-testing/FlightList.java +++ b/Robust/src/Benchmarks/mlp/directto/mlp-small-for-testing/FlightList.java @@ -37,8 +37,16 @@ public class FlightList { public void amendFlightPlan(D2 d2, int time, StringTokenizer st) { Flight fAux=getFlight(st.nextToken()); Route rAux=new Route(Integer.parseInt(st.nextToken())); - for (int i=0;i