From aa7889832a56cc990b84908184fd7615f4db4233 Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 8 Oct 2008 18:30:48 +0000 Subject: [PATCH] Committing a stable version of global sweep that works for simple strong updates, does not work correctly after some method calls --- .../OwnershipAnalysis/OwnershipGraph.java | 224 +++++++++++++++++- .../OwnershipAnalysis/ReachabilitySet.java | 37 +++ .../OwnershipAnalysis/TokenTupleSet.java | 31 +++ .../OwnershipAnalysisTest/test01/test01.java | 31 +-- 4 files changed, 298 insertions(+), 25 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index cd46e708..126f2886 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -412,6 +412,8 @@ public class OwnershipGraph { HashSet nodesWithNewAlpha = new HashSet(); HashSet edgesWithNewBeta = new HashSet(); + boolean strongUpdate = false; + Iterator itrXhrn = lnX.iteratorToReferencees(); while( itrXhrn.hasNext() ) { ReferenceEdge edgeX = itrXhrn.next(); @@ -456,29 +458,36 @@ public class OwnershipGraph { // if edgeY's beta was updated, use that to calculate beta for new edge // otherwise the edgeY didn't change and it is the source for the calc ReachabilitySet sourceBetaForNewEdge; - if( edgesWithNewBeta.contains( edgeY ) ) { + //if( edgesWithNewBeta.contains( edgeY ) ) { + if( !edgeY.getBetaNew().equals( new ReachabilitySet().makeCanonical() ) ) { sourceBetaForNewEdge = edgeY.getBetaNew(); } else { sourceBetaForNewEdge = edgeY.getBeta(); } + ReachabilitySet sourceAlphaForPrune; + if( !hrnX.getAlphaNew().equals( new ReachabilitySet().makeCanonical() ) ) { + sourceAlphaForPrune = hrnX.getAlphaNew(); + } else { + sourceAlphaForPrune = hrnX.getAlpha(); + } + // prepare the new reference edge hrnX.f -> hrnY ReferenceEdge edgeNew = new ReferenceEdge(hrnX, hrnY, f, false, - sourceBetaForNewEdge.pruneBy(hrnX.getAlpha() ) + sourceBetaForNewEdge.pruneBy( sourceAlphaForPrune ) ); // we can do a strong update here if one of two cases holds - boolean strongUpdate = false; if( f != null && ( (hrnX.getNumReferencers() == 1) || ( lnX.getNumReferencees() == 1 && hrnX.isSingleObject() ) ) ) { strongUpdate = true; - //clearReferenceEdgesFrom( hrnX, f, false ); + clearReferenceEdgesFrom( hrnX, f, false ); } // look to see if an edge with same field exists @@ -495,12 +504,6 @@ public class OwnershipGraph { } else { addReferenceEdge( hrnX, hrnY, edgeNew ); } - - // if it was a strong update, make sure to improve - // reachability with a global sweep - if( strongUpdate ) { - globalSweep(); - } } } @@ -513,6 +516,16 @@ public class OwnershipGraph { while( edgeItr.hasNext() ) { edgeItr.next().applyBetaNew(); } + + // if it was a strong update, make sure to improve + // reachability with a global sweep + if( strongUpdate ) { + //try { + //writeGraph( "testBefore", true, true, true, false, false ); + globalSweep(); + //writeGraph( "testPost", true, true, true, false, false ); + //} catch( Exception e ) {} + } } @@ -1810,7 +1823,196 @@ public class OwnershipGraph { // //////////////////////////////////////////////////// protected void globalSweep() { - + + // a work set for performing the sweep + Hashtable > workSet = + new Hashtable >(); + + // first initialize every alphaNew for a flagged region to + // a set with just that token + Set hrns = id2hrn.entrySet(); + Iterator itrHrns = hrns.iterator(); + while( itrHrns.hasNext() ) { + Map.Entry me = (Map.Entry)itrHrns.next(); + Integer token = (Integer) me.getKey(); + HeapRegionNode hrn = (HeapRegionNode) me.getValue(); + + // assert that this node and incoming edges have clean alphaNew + // and betaNew sets, respectively + ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical(); + //System.out.println( "hrn="+hrn ); + //System.out.println( "alphaNew="+hrn.getAlphaNew() ); + assert rsEmpty.equals( hrn.getAlphaNew() ); + + Iterator itrRes = hrn.iteratorToReferencers(); + while( itrRes.hasNext() ) { + ReferenceEdge edge = itrRes.next(); + assert rsEmpty.equals( edge.getBetaNew() ); + } + + TokenTuple tt = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONE ).makeCanonical(); + TokenTuple ttPlus = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONEORMORE ).makeCanonical(); + TokenTuple ttStar = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ZEROORMORE ).makeCanonical(); + + TokenTupleSet tts = new TokenTupleSet( tt ).makeCanonical(); + TokenTupleSet ttsPlus = new TokenTupleSet( ttPlus ).makeCanonical(); + TokenTupleSet ttsStar = new TokenTupleSet( ttStar ).makeCanonical(); + TokenTupleSet ttsEmpty = new TokenTupleSet( ).makeCanonical(); + + if( hrn.isFlagged() ) { + HashSet subWorkSet = new HashSet(); + subWorkSet.add( tts ); + subWorkSet.add( ttsPlus ); + subWorkSet.add( ttsStar ); + workSet.put( hrn, subWorkSet ); + + hrn.setAlphaNew( new ReachabilitySet( tts ).makeCanonical() ); + } else { + hrn.setAlphaNew( new ReachabilitySet( ttsEmpty ).makeCanonical() ); + } + } + + // then propagate tokens forward one step at a time + while( !workSet.isEmpty() ) { + HeapRegionNode hrn = workSet.keySet().iterator().next(); + + HashSet subWorkSet = workSet.get( hrn ); + assert subWorkSet != null; + + if( subWorkSet.isEmpty() ) { + // we're currently done with sub work at this heap region, although + // more work may get queued up later, but remove it for now and continue + workSet.remove( hrn ); + continue; + } + + TokenTupleSet tts = subWorkSet.iterator().next(); + subWorkSet.remove( tts ); + + // try to push this TokenTupleSet over all outgoing edges + Iterator itrRes = hrn.iteratorToReferencees(); + while( itrRes.hasNext() ) { + ReferenceEdge edge = itrRes.next(); + if( edge.getBeta().containsSuperSet( tts ) ) { + HeapRegionNode dst = edge.getDst(); + + // make a set of possible contributions this token + // might have on the alpha set here + HashSet ttsNewSet = new HashSet(); + //ttsNewSet.add( tts ); + + Iterator itrDstAlphaNew = dst.getAlphaNew().iterator(); + while( itrDstAlphaNew.hasNext() ) { + TokenTupleSet ttsDstAlphaNew = itrDstAlphaNew.next(); + ttsNewSet.add( tts.unionUpArity( ttsDstAlphaNew ) ); + } + + // only add this to the dst alpha new if it is in the beta of + // the edge we crossed to get here, and then only continue the + // propagation if it isn't already in the dst alpha new + Iterator itrNewSet = ttsNewSet.iterator(); + while( itrNewSet.hasNext() ) { + TokenTupleSet ttsNew = itrNewSet.next(); + + if( edge.getBeta().containsSuperSet( ttsNew ) && + !dst.getAlphaNew().contains( ttsNew ) ) { + + // okay, this is a valid propagation, and add to the + // work set to further propagate it + dst.setAlphaNew( dst.getAlphaNew().union( ttsNew ) ); + + HashSet subWorkSetDst = workSet.get( dst ); + if( subWorkSetDst == null ) { + subWorkSetDst = new HashSet(); + } + + subWorkSetDst.add( ttsNew ); + workSet.put( dst, subWorkSetDst ); + } + } + } + } + } + + // now prepare work sets to propagate token sets backwards + // from heap regions across all edges + assert workSet.isEmpty(); + hrns = id2hrn.entrySet(); + itrHrns = hrns.iterator(); + while( itrHrns.hasNext() ) { + Map.Entry me = (Map.Entry)itrHrns.next(); + HeapRegionNode hrn = (HeapRegionNode) me.getValue(); + + HashSet subWorkSet = new HashSet(); + + Iterator itrAlphaNewSets = hrn.getAlphaNew().iterator(); + while( itrAlphaNewSets.hasNext() ) { + TokenTupleSet tts = itrAlphaNewSets.next(); + subWorkSet.add( tts ); + } + + workSet.put( hrn, subWorkSet ); + } + + // propagate token sets backwards across edges one step at a time + while( !workSet.isEmpty() ) { + HeapRegionNode hrn = workSet.keySet().iterator().next(); + + HashSet subWorkSet = workSet.get( hrn ); + assert subWorkSet != null; + + if( subWorkSet.isEmpty() ) { + // we're currently done with sub work at this heap region, although + // more work may get queued up later, but remove it for now and continue + workSet.remove( hrn ); + continue; + } + + TokenTupleSet tts = subWorkSet.iterator().next(); + subWorkSet.remove( tts ); + + // try to push this TokenTupleSet back up incoming edges + Iterator itrRes = hrn.iteratorToReferencers(); + while( itrRes.hasNext() ) { + ReferenceEdge edge = itrRes.next(); + if( edge.getBeta().containsWithZeroes( tts ) && + !edge.getBetaNew().contains( tts ) ) { + // okay, this is a valid propagation, and add to the + // work set to further propagate it + edge.setBetaNew( edge.getBetaNew().union( tts ) ); + + OwnershipNode src = edge.getSrc(); + if( src instanceof HeapRegionNode ) { + + HashSet subWorkSetSrc = workSet.get( (HeapRegionNode) src ); + if( subWorkSetSrc == null ) { + subWorkSetSrc = new HashSet(); + } + + subWorkSetSrc.add( tts ); + workSet.put( (HeapRegionNode) src, subWorkSetSrc ); + } + } + } + } + + // apply alphaNew and betaNew to all nodes and edges + HashSet res = new HashSet(); + + Iterator nodeItr = id2hrn.values().iterator(); + while( nodeItr.hasNext() ) { + HeapRegionNode hrn = nodeItr.next(); + hrn.applyAlphaNew(); + Iterator itrRes = hrn.iteratorToReferencers(); + while( itrRes.hasNext() ) { + res.add( itrRes.next() ); + } + } + + Iterator edgeItr = res.iterator(); + while( edgeItr.hasNext() ) { + edgeItr.next().applyBetaNew(); + } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java index 391e2758..830c6f87 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -60,6 +60,43 @@ public class ReachabilitySet extends Canonical { return possibleReachabilities.contains(tts); } + public boolean containsWithZeroes(TokenTupleSet tts) { + assert tts != null; + + if( possibleReachabilities.contains(tts) ) { + return true; + } + + Iterator itr = iterator(); + while( itr.hasNext() ) { + TokenTupleSet ttsThis = (TokenTupleSet) itr.next(); + if( ttsThis.containsWithZeroes(tts) ) { + return true; + } + } + + return false; + } + + public boolean containsSuperSet(TokenTupleSet tts) { + assert tts != null; + + if( possibleReachabilities.contains(tts) ) { + return true; + } + + Iterator itr = iterator(); + while( itr.hasNext() ) { + TokenTupleSet ttsThis = (TokenTupleSet) itr.next(); + if( tts.isSubset(ttsThis) ) { + return true; + } + } + + return false; + } + + public boolean containsTuple(TokenTuple tt) { Iterator itr = iterator(); while( itr.hasNext() ) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java index f1ec73cf..e1c603cb 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java @@ -50,6 +50,37 @@ public class TokenTupleSet extends Canonical { return tokenTuples.contains(tt); } + public boolean containsWithZeroes(TokenTupleSet tts) { + assert tts != null; + + // first establish that every token tuple from tts is + // also in this set + Iterator ttItrIn = tts.iterator(); + while( ttItrIn.hasNext() ) { + TokenTuple ttIn = ttItrIn.next(); + TokenTuple ttThis = this.containsToken(ttIn.getToken() ); + + if( ttThis == null ) { + return false; + } + } + + // then establish that anything in this set that is + // not in tts is a zero-arity token tuple, which is okay + Iterator ttItrThis = this.iterator(); + while( ttItrThis.hasNext() ) { + TokenTuple ttThis = ttItrThis.next(); + TokenTuple ttIn = tts.containsToken(ttThis.getToken() ); + + if( ttIn == null && + ttThis.getArity() != TokenTuple.ARITY_ZEROORMORE ) { + return false; + } + } + + // if so this set contains tts with zeroes + return true; + } public TokenTupleSet union(TokenTuple ttIn) { assert ttIn != null; diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index 5b56727f..3787b57f 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -1,12 +1,12 @@ public class Parameter { flag w; - //int a; - //int b; - //Parameter f; - //Parameter g; - //Penguin p; - //Foo h; + int a; + int b; + Parameter f; + Parameter g; + Penguin p; + Foo h; public Parameter() {} @@ -28,7 +28,7 @@ public class Fooz { public Fooz x; } -/* + public class Penguin { int x; int y; @@ -188,7 +188,7 @@ public class Foo { p1.y = g0; } } -*/ + // this empty task should still create a non-empty @@ -327,7 +327,7 @@ task SummaryNodeTokens( Foo p0{ f } ) { taskexit( p0{ !f } ); } - +*/ task strongUpdates( Foo p0{ f } ) { @@ -335,12 +335,13 @@ task strongUpdates( Foo p0{ f } ) { Foo a = new Foo(); if( false ) { - a.x = new Foo(); - a.y = new Foo(); + a.x = new Foo(); + a.y = new Foo(); } else if( false ) { - a.x = new Foo(); - a.y = new Foo(); + a.x = new Foo(); + a.y = new Foo(); } + // this should effect a strong update a.x = b; @@ -357,10 +358,12 @@ task strongUpdates( Foo p0{ f } ) { // p0 points to a multiple-object heap region // so this should not make a strong update p0.x = b; - + + taskexit( p0{ !f } ); } +/* task ObjectChainByMethodCalls( Foo a{ f } ) { -- 2.34.1