From dee71d0e4f60998a9eb6f91a77c8b6a5507d68fc Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 25 Aug 2008 22:17:47 +0000 Subject: [PATCH] method call stably implemented as a first pass, results already show some incorrect answers --- .../OwnershipAnalysis/AllocationSite.java | 57 ++++++++- .../OwnershipAnalysis/HeapRegionNode.java | 10 +- .../OwnershipAnalysis/OwnershipAnalysis.java | 2 - .../OwnershipAnalysis/OwnershipGraph.java | 89 ++++++++++++-- .../OwnershipAnalysis/ReachabilitySet.java | 15 +++ .../OwnershipAnalysis/TokenTupleSet.java | 111 ++++++++++++++---- .../OwnershipAnalysisTest/test01/test01.java | 5 +- 7 files changed, 247 insertions(+), 42 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java index c1df19ad..949dd465 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java +++ b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java @@ -29,13 +29,19 @@ 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 static final int AGE_notInThisSite = 100; + public static final int AGE_in_I = 101; + public static final int AGE_oldest = 102; + public static final int AGE_summary = 103; + + public static final int SHADOWAGE_notInThisSite = -100; + public static final int SHADOWAGE_in_I = -101; + public static final int SHADOWAGE_oldest = -102; + public static final int SHADOWAGE_summary = -103; public AllocationSite(int allocationDepth, TypeDescriptor type) { - assert allocationDepth >= 1; + assert allocationDepth >= 2; this.allocationDepth = allocationDepth; this.type = type; @@ -101,7 +107,8 @@ public class AllocationSite { return type; } - public int getAge(Integer id) { + public int getAgeCategory(Integer id) { + if( id.equals(summary) ) { return AGE_summary; } @@ -112,13 +119,51 @@ public class AllocationSite { for( int i = 0; i < allocationDepth - 1; ++i ) { if( id.equals(ithOldest.get(i) ) ) { - return i; + return AGE_in_I; } } return AGE_notInThisSite; } + public Integer getAge(Integer id) { + for( int i = 0; i < allocationDepth - 1; ++i ) { + if( id.equals(ithOldest.get(i) ) ) { + return new Integer( i ); + } + } + + return null; + } + + public int getShadowAgeCategory(Integer id) { + if( id.equals(-summary) ) { + return SHADOWAGE_summary; + } + + if( id.equals(getOldestShadow() ) ) { + return SHADOWAGE_oldest; + } + + for( int i = 0; i < allocationDepth - 1; ++i ) { + if( id.equals( getIthOldestShadow(i) ) ) { + return SHADOWAGE_in_I; + } + } + + return SHADOWAGE_notInThisSite; + } + + public Integer getShadowAge( Integer id ) { + for( int i = 0; i < allocationDepth - 1; ++i ) { + if( id.equals( getIthOldestShadow(i) ) ) { + return new Integer( -i ); + } + } + + return null; + } + public String toString() { return "allocSite" + id; } diff --git a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java index 04778154..f5009b22 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java +++ b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java @@ -181,7 +181,15 @@ public class HeapRegionNode extends OwnershipNode { public String getIDString() { - return id.toString(); + String s; + + if( id < 0 ) { + s = "minus" + new Integer(-id).toString(); + } else { + s = id.toString(); + } + + return s; } public String getAlphaString() { diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index 37457ecb..a67ac4e3 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -196,8 +196,6 @@ public class OwnershipAnalysis { this.callGraph = callGraph; this.allocationDepth = allocationDepth; - // temporary for debugging - this.allocationDepth = 1; descriptorsToVisit = new HashSet(); diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 82fde788..ae12c5fd 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -1292,6 +1292,77 @@ public class OwnershipGraph { } } + + // merge the shadow nodes of allocation sites back down to normal capacity + Iterator allocItr = ogCallee.allocationSites.iterator(); + while( allocItr.hasNext() ) { + AllocationSite as = allocItr.next(); + + // first age each allocation site enough times to make room for the shadow nodes + for( int i = 0; i < as.getAllocationDepth(); ++i ) { + age( as ); + } + + // then merge the shadow summary into the normal summary + HeapRegionNode hrnSummary = getSummaryNode( as ); + assert hrnSummary != null; + + HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as ); + assert hrnSummaryShadow != null; + + mergeIntoSummary( hrnSummaryShadow, hrnSummary ); + + // then transplant shadow nodes onto the now clean normal nodes + for( int i = 0; i < as.getAllocationDepth(); ++i ) { + + Integer idIth = as.getIthOldest(i); + HeapRegionNode hrnIth = id2hrn.get(idIth); + + Integer idIthShadow = as.getIthOldestShadow(i); + HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow); + + transferOnto(hrnIthShadow, hrnIth); + + // clear off shadow nodes after transfer + clearReferenceEdgesFrom(hrnIthShadow, null, true); + clearReferenceEdgesTo(hrnIthShadow, null, true); + hrnIthShadow.setAlpha( new ReachabilitySet().makeCanonical() ); + } + + // finally, globally change shadow tokens into normal tokens + Iterator itrAllLabelNodes = td2ln.entrySet().iterator(); + while( itrAllLabelNodes.hasNext() ) { + Map.Entry me = (Map.Entry)itrAllLabelNodes.next(); + LabelNode ln = (LabelNode) me.getValue(); + + Iterator itrEdges = ln.iteratorToReferencees(); + while( itrEdges.hasNext() ) { + unshadowTokens(as, itrEdges.next() ); + } + } + + Iterator itrAllHRNodes = id2hrn.entrySet().iterator(); + while( itrAllHRNodes.hasNext() ) { + Map.Entry me = (Map.Entry)itrAllHRNodes.next(); + HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue(); + + unshadowTokens(as, hrnToAge); + + Iterator itrEdges = hrnToAge.iteratorToReferencees(); + while( itrEdges.hasNext() ) { + unshadowTokens(as, itrEdges.next() ); + } + } + } + } + + + protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) { + edge.setBeta(edge.getBeta().unshadowTokens(as) ); + } + + protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) { + hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) ); } @@ -1529,7 +1600,7 @@ public class OwnershipGraph { AllocationSite as = hrnCallee.getAllocationSite(); assert as != null; - int age = as.getAge( hrnCallee.getID() ); + int age = as.getAgeCategory( hrnCallee.getID() ); assert age != AllocationSite.AGE_notInThisSite; Integer idCaller; @@ -1538,7 +1609,12 @@ public class OwnershipGraph { } else if( age == AllocationSite.AGE_oldest ) { idCaller = as.getOldestShadow(); } else { - idCaller = as.getIthOldestShadow( age ); + assert age == AllocationSite.AGE_in_I; + + Integer I = as.getAge( hrnCallee.getID() ); + assert I != null; + + idCaller = as.getIthOldestShadow( I ); } assert id2hrn.containsKey( idCaller ); @@ -1558,15 +1634,6 @@ public class OwnershipGraph { } - protected void majorAgeTokens(AllocationSite as, ReferenceEdge edge) { - //edge.setBeta( edge.getBeta().majorAgeTokens( as ) ); - } - - protected void majorAgeTokens(AllocationSite as, HeapRegionNode hrn) { - //hrn.setAlpha( hrn.getAlpha().majorAgeTokens( as ) ); - } - - //////////////////////////////////////////////////// // in merge() and equals() methods the suffix A diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java index 9e4a338e..2fa693b1 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -181,6 +181,21 @@ public class ReachabilitySet extends Canonical { } + public ReachabilitySet unshadowTokens(AllocationSite as) { + assert as != null; + + ReachabilitySet rsOut = new ReachabilitySet(); + + Iterator itrS = this.iterator(); + while( itrS.hasNext() ) { + TokenTupleSet tts = (TokenTupleSet) itrS.next(); + rsOut.possibleReachabilities.add( tts.unshadowTokens(as) ); + } + + return rsOut.makeCanonical(); + } + + public ReachabilitySet toShadowTokens(AllocationSite as) { assert as != null; diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java index b11d90b3..94053a4e 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java @@ -155,32 +155,34 @@ public class TokenTupleSet extends Canonical { TokenTuple tt = (TokenTuple) itrT.next(); Integer token = tt.getToken(); - int age = as.getAge(token); + int age = as.getAgeCategory(token); - // summary tokens and tokens not associated with + // tokens not associated with // the site should be left alone if( age == AllocationSite.AGE_notInThisSite ) { ttsOut.tokenTuples.add(tt); + } else 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 an oldest token, again just remember + // for later + foundOldest = true; + } else { - 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 an oldest token, again just remember - // for later - foundOldest = true; - - } else { - // otherwise, we change this token to the - // next older token - Integer tokenToChangeTo = as.getIthOldest(age + 1); - TokenTuple ttAged = tt.changeTokenTo(tokenToChangeTo); - ttsOut.tokenTuples.add(ttAged); - } + assert age == AllocationSite.AGE_in_I; + + Integer I = as.getAge(token); + assert I != null; + // otherwise, we change this token to the + // next older token + Integer tokenToChangeTo = as.getIthOldest(I + 1); + TokenTuple ttAged = tt.changeTokenTo(tokenToChangeTo); + ttsOut.tokenTuples.add(ttAged); } } @@ -208,6 +210,68 @@ public class TokenTupleSet extends Canonical { } + public TokenTupleSet unshadowTokens(AllocationSite as) { + assert as != null; + + TokenTupleSet ttsOut = new TokenTupleSet(); + + TokenTuple ttSummary = null; + boolean foundShadowSummary = false; + + Iterator itrT = this.iterator(); + while( itrT.hasNext() ) { + TokenTuple tt = (TokenTuple) itrT.next(); + + Integer token = tt.getToken(); + int shadowAge = as.getShadowAgeCategory(token); + + if( shadowAge == AllocationSite.AGE_summary ) { + // remember the summary tuple, but don't add it + // we may combine it with the oldest tuple + ttSummary = tt; + + } else if( shadowAge == AllocationSite.SHADOWAGE_notInThisSite ) { + ttsOut.tokenTuples.add(tt); + + } else if( shadowAge == AllocationSite.SHADOWAGE_summary ) { + // found the shadow summary token, again just remember + // for later + foundShadowSummary = true; + + } else if( shadowAge == AllocationSite.SHADOWAGE_oldest ) { + Integer tokenToChangeTo = as.getOldestShadow(); + TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo); + ttsOut.tokenTuples.add(ttNormal); + + } else { + assert shadowAge == AllocationSite.SHADOWAGE_in_I; + + Integer I = as.getShadowAge(token); + assert I != null; + + Integer tokenToChangeTo = as.getIthOldest(-I); + TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo); + ttsOut.tokenTuples.add(ttNormal); + } + } + + if ( ttSummary != null && !foundShadowSummary ) { + ttsOut.tokenTuples.add(ttSummary); + + } else if( ttSummary == null && foundShadowSummary ) { + ttSummary = new TokenTuple(as.getSummary(), + true, + TokenTuple.ARITY_ONE).makeCanonical(); + ttsOut.tokenTuples.add( ttSummary ); + + } else if( ttSummary != null && foundShadowSummary ) { + ttsOut.tokenTuples.add(ttSummary.increaseArity() ); + } + + return ttsOut.makeCanonical(); + } + + public TokenTupleSet toShadowTokens(AllocationSite as) { assert as != null; @@ -218,7 +282,7 @@ public class TokenTupleSet extends Canonical { TokenTuple tt = (TokenTuple) itrT.next(); Integer token = tt.getToken(); - int age = as.getAge(token); + int age = as.getAgeCategory(token); // summary tokens and tokens not associated with // the site should be left alone @@ -232,7 +296,12 @@ public class TokenTupleSet extends Canonical { ttsOut.tokenTuples.add(tt.changeTokenTo( as.getOldestShadow() )); } else { - ttsOut.tokenTuples.add(tt.changeTokenTo( as.getIthOldestShadow( age ) )); + assert age == AllocationSite.AGE_in_I; + + Integer I = as.getAge(token); + assert I != null; + + ttsOut.tokenTuples.add(tt.changeTokenTo( as.getIthOldestShadow( I ) )); } } diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index 088fd084..ec7e604f 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -71,6 +71,7 @@ public class Foo { p0.x = g1; } + /* static public void m2_( Foo p0 ) { Foo g0 = new Foo(); @@ -141,6 +142,7 @@ public class Foo { p0.y = p1; p1.y = p0; } + */ } @@ -367,7 +369,7 @@ task methodTest01_( Foo p0{ f }, Foo p1{ f } ) { taskexit( p0{ !f }, p1{ !f } ); } - +/* task methodTest02_( Foo p0{ f }, Foo p1{ f } ) { Foo a0before = new Foo(); @@ -569,3 +571,4 @@ task methodTest08_( Foo p0{ f }, Foo p1{ f } ) { taskexit( p0{ !f }, p1{ !f } ); } +*/ \ No newline at end of file -- 2.34.1