From fdaf311acf73439fef3690b9edfc96722a21154c Mon Sep 17 00:00:00 2001 From: jjenista Date: Fri, 18 Jul 2008 19:29:25 +0000 Subject: [PATCH] Working on allocating with reachability, mostly the "aging" of tokens. Implementation is stable but it is not working correctly. --- .../OwnershipAnalysis/AllocationSite.java | 22 +++++++ .../OwnershipAnalysis/OwnershipGraph.java | 56 +++++++++++++++++ .../OwnershipAnalysis/ReachabilitySet.java | 23 ++++--- .../OwnershipAnalysis/TokenTuple.java | 8 +++ .../OwnershipAnalysis/TokenTupleSet.java | 60 +++++++++++++++++++ 5 files changed, 162 insertions(+), 7 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java index d6ffc614..fb02f461 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java +++ b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java @@ -29,6 +29,10 @@ public class AllocationSite { protected Integer summary; protected TypeDescriptor type; + public static final int AGE_notInThisSite = -1; + public static final int AGE_oldest = -2; + public static final int AGE_summary = -3; + public AllocationSite( int allocationDepth, TypeDescriptor type ) { assert allocationDepth >= 3; @@ -82,6 +86,24 @@ public class AllocationSite { return type; } + public int getAge( Integer id ) { + if( id.equals( summary ) ) { + return AGE_summary; + } + + if( id.equals( getOldest() ) ) { + return AGE_oldest; + } + + for( int i = 0; i < allocationDepth - 1; ++i ) { + if( id.equals( ithOldest.get( i ) ) ) { + return i; + } + } + + return AGE_notInThisSite; + } + public String toString() { return "allocSite" + id; } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index ef55faed..ab25e11a 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -579,6 +579,7 @@ public class OwnershipGraph { ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue(); // determine if another summary node is already referencing this referencee + /* boolean hasSummaryReferencer = false; OwnershipNode onReferencer = null; Iterator itrReferencer = hrnReferencee.iteratorToReferencers(); @@ -595,6 +596,20 @@ public class OwnershipGraph { addReferenceEdge( hrnSummary, hrnReferencee, new ReferenceEdgeProperties( !hasSummaryReferencer ) ); + */ + + ReferenceEdgeProperties repSummary = hrnSummary.getReferenceTo( hrnReferencee ); + ReferenceEdgeProperties repMerged = rep.copy(); + + if( repSummary == null ) { + // the merge is trivial, nothing to be done + } else { + // otherwise an edge from the referencer to alpha_S exists already + // and the edge referencer->alpha_K should be merged with it + repMerged.setBeta( repMerged.getBeta().union( repSummary.getBeta() ) ); + } + + addReferenceEdge( hrnSummary, hrnReferencee, repMerged ); } // next transfer references to alpha_k over to alpha_s @@ -675,6 +690,47 @@ public class OwnershipGraph { // clear all references in and out of newest node clearReferenceEdgesFrom( hrn0 ); clearReferenceEdgesTo ( hrn0 ); + + // now tokens in reachability sets need to "age" as well + ReferenceEdgeProperties repToAge = null; + Iterator itrAllLabelNodes = td2ln.entrySet().iterator(); + while( itrAllLabelNodes.hasNext() ) { + Map.Entry me = (Map.Entry) itrAllLabelNodes.next(); + LabelNode ln = (LabelNode) me.getValue(); + + Iterator itrEdges = ln.setIteratorToReferencedRegions(); + while( itrEdges.hasNext() ) { + Map.Entry meE = (Map.Entry) itrEdges.next(); + repToAge = (ReferenceEdgeProperties) meE.getValue(); + + ageTokens( as, repToAge ); + } + } + + HeapRegionNode hrnToAge = null; + Iterator itrAllHRNodes = id2hrn.entrySet().iterator(); + while( itrAllHRNodes.hasNext() ) { + Map.Entry me = (Map.Entry) itrAllHRNodes.next(); + hrnToAge = (HeapRegionNode) me.getValue(); + + ageTokens( as, hrnToAge ); + + Iterator itrEdges = hrnToAge.setIteratorToReferencedRegions(); + while( itrEdges.hasNext() ) { + Map.Entry meE = (Map.Entry) itrEdges.next(); + repToAge = (ReferenceEdgeProperties) meE.getValue(); + + ageTokens( as, repToAge ); + } + } + } + + protected void ageTokens( AllocationSite as, ReferenceEdgeProperties rep ) { + rep.setBeta( rep.getBeta().ageTokens( as ) ); + } + + protected void ageTokens( AllocationSite as, HeapRegionNode hrn ) { + hrn.setAlpha( hrn.getAlpha().ageTokens( as ) ); } diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java index e7940741..b3a35fcf 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -201,6 +201,19 @@ public class ReachabilitySet extends Canonical { } + public ReachabilitySet ageTokens( AllocationSite as ) { + ReachabilitySet rsOut = new ReachabilitySet(); + + Iterator itrS = this.iterator(); + while( itrS.hasNext() ) { + TokenTupleSet tts = (TokenTupleSet) itrS.next(); + rsOut.possibleReachabilities.add( tts.ageTokens( as ) ); + } + + return rsOut.makeCanonical(); + } + + public boolean equals( Object o ) { if( !(o instanceof ReachabilitySet) ) { return false; @@ -235,17 +248,13 @@ public class ReachabilitySet extends Canonical { Iterator i = this.iterator(); while( i.hasNext() ) { - if( possibleReachabilities.size() > 1 ) { + s += i.next(); + if( i.hasNext() ) { s += "\n"; } - s += " "+i.next(); - } - - if( possibleReachabilities.size() > 1 ) { - s += "\n"; } - s += " ]"; + s += "]"; return s; } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java index cd2f248b..acaf257d 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java @@ -51,6 +51,14 @@ public class TokenTuple extends Canonical return this; } + public TokenTuple changeTokenTo( Integer tokenToChangeTo ) { + assert isNewSummary == false; + + return new TokenTuple( tokenToChangeTo, + isNewSummary, + arity ).makeCanonical(); + } + public boolean equals( Object o ) { if( !(o instanceof TokenTuple) ) { return false; diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java index d08c0073..ecf0633e 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java @@ -143,6 +143,66 @@ public class TokenTupleSet extends Canonical { return false; } + public TokenTupleSet ageTokens( AllocationSite as ) { + TokenTupleSet ttsOut = new TokenTupleSet( this ); + + TokenTuple ttSummary = null; + boolean foundOldest = false; + + Iterator itrT = this.iterator(); + while( itrT.hasNext() ) { + TokenTuple tt = (TokenTuple) itrT.next(); + + Integer token = tt.getToken(); + int age = as.getAge( token ); + + // summary tokens and tokens not associated with + // the site should be left alone + if( age != AllocationSite.AGE_notInThisSite ) { + + if( age == AllocationSite.AGE_summary ) { + // remember the summary tuple, but don't add it + // we may combine it with the oldest tuple + ttSummary = tt; + + } else if( age == AllocationSite.AGE_oldest ) { + // found a token + foundOldest = true; + + } else { + // otherwise, we change this token to the + // next older token + Integer tokenToChangeTo = as.getIthOldest( age + 1 ); + tt = tt.changeTokenTo( tokenToChangeTo ); + } + } + + ttsOut.add( tt ); + } + + // there are four cases to consider here + // 1. we found a summary tuple and no oldest tuple + // Here we just pass the summary unchanged + // 2. we found an oldest tuple, no summary + // Make a new, arity-one summary tuple + // 3. we found both a summary and an oldest + // Merge them by increasing arity of summary + // 4. (not handled) we found neither, do nothing + if ( ttSummary != null && !foundOldest ) { + ttsOut.add( ttSummary ); + + } else if( ttSummary == null && foundOldest ) { + ttsOut.add( new TokenTuple( as.getSummary(), + true, + TokenTuple.ARITY_ONE ).makeCanonical() ); + + } else if( ttSummary != null && foundOldest ) { + ttsOut.add( ttSummary.increaseArity() ); + } + + return ttsOut.makeCanonical(); + } + public String toString() { return tokenTuples.toString(); } -- 2.34.1