From 98c3bec627cf4b7b64eca5c02575558e262d127b Mon Sep 17 00:00:00 2001 From: jjenista Date: Sun, 27 Jul 2008 23:46:39 +0000 Subject: [PATCH] Reachability bug fixes. Tokens propagate and age in allocation sites, and the example programs produce results that are almost correct. One thing to note is that token propagation through many allocation sites in a loop doesn't work properly, where the same field-by-field construction of a single complex object does propagate the tokens. --- .../OwnershipAnalysis/OwnershipAnalysis.java | 2 +- .../OwnershipAnalysis/OwnershipGraph.java | 104 +++++++++++------- .../OwnershipAnalysis/ReachabilitySet.java | 3 +- .../OwnershipAnalysis/TokenTupleSet.java | 23 ++-- .../OwnershipAnalysisTest/test01/test01.java | 23 ++-- 5 files changed, 92 insertions(+), 63 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index de8be215..a7dfd223 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -280,7 +280,7 @@ public class OwnershipAnalysis { if( !og.equals( ogPrev ) ) { mapDescriptorToCompleteOwnershipGraph.put( d, og ); - og.writeGraph( d, true, false ); + og.writeGraph( d, true, true, false ); // only methods have dependents, tasks cannot // be invoked by any user program calls diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index a7a65cd0..7010de5b 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -405,22 +405,9 @@ public class OwnershipGraph { addReferenceEdge( hrn, hrnSrc, repNew ); - - ChangeTupleSet Cy = O.unionUpArityToChangeSet( R ); - //ChangeTupleSet Cx = R.unionUpArityToChangeSet( O ); propagateTokens( hrnSrc, Cy, nodesWithNewAlpha, edgesWithNewBeta ); - //propagateTokens( hrn, Cx, nodesWithNewAlpha, edgesWithNewBeta ); - - /* - // note that this picks up the beta after the propogation has - // been applied - ReferenceEdgeProperties repNew - = new ReferenceEdgeProperties( false, false, repSrc.getBetaNew() ); - - addReferenceEdge( hrn, hrnSrc, repNew ); - */ } } @@ -587,26 +574,6 @@ public class OwnershipGraph { Map.Entry me = (Map.Entry) itrReferencee.next(); hrnReferencee = (HeapRegionNode) me.getKey(); 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(); - while( itrReferencer.hasNext() ) { - onReferencer = (OwnershipNode) itrReferencer.next(); - if( onReferencer instanceof HeapRegionNode ) { - HeapRegionNode hrnPossibleSummary = (HeapRegionNode) onReferencer; - if( hrnPossibleSummary.isNewSummary() ) { - hasSummaryReferencer = true; - } - } - } - - addReferenceEdge( hrnSummary, - hrnReferencee, - new ReferenceEdgeProperties( !hasSummaryReferencer ) ); - */ ReferenceEdgeProperties repSummary = hrnSummary.getReferenceTo( hrnReferencee ); ReferenceEdgeProperties repMerged = rep.copy(); @@ -644,6 +611,9 @@ public class OwnershipGraph { addReferenceEdge( onReferencer, hrnSummary, repMerged ); } + // then merge alpha_k reachability into alpha_s + hrnSummary.setAlpha( hrnSummary.getAlpha().union( hrnK.getAlpha() ) ); + // then move down the line of heap region nodes // clobbering the ith and transferring all references @@ -684,6 +654,9 @@ public class OwnershipGraph { addReferenceEdge( onReferencer, hrnI, rep.copy() ); } + + // replace hrnI reachability with hrnImin1 + hrnI.setAlpha( hrnImin1.getAlpha() ); } // as stated above, the newest node alpha_0 should have had its @@ -697,11 +670,12 @@ public class OwnershipGraph { // have touched this node, therefore assert it is non-null assert hrn0 != null; + // 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(); @@ -717,7 +691,6 @@ public class OwnershipGraph { ageTokens( as, repToAge ); } } - HeapRegionNode hrnToAge = null; Iterator itrAllHRNodes = id2hrn.entrySet().iterator(); while( itrAllHRNodes.hasNext() ) { @@ -734,8 +707,15 @@ public class OwnershipGraph { ageTokens( as, repToAge ); } } - */ - + + + // after tokens have been aged, reset newest node's reachability + hrn0.setAlpha( new ReachabilitySet( + new TokenTupleSet( + new TokenTuple( hrn0 ) + ) + ).makeCanonical() + ); } protected void ageTokens( AllocationSite as, ReferenceEdgeProperties rep ) { @@ -828,9 +808,9 @@ public class OwnershipGraph { //System.out.println( "idCallee is "+idCallee ); //System.out.println( "idChildCallee is "+idChildCallee ); - try { - writeGraph( "caller", false, false ); - ogCallee.writeGraph( "callee", false, false ); + try { + writeGraph( "caller", false, false, false ); + ogCallee.writeGraph( "callee", false, false, false ); } catch( IOException e ) {} } @@ -1517,6 +1497,22 @@ public class OwnershipGraph { // for writing ownership graphs to dot files + public void writeGraph( Descriptor methodDesc, + FlatNode fn, + boolean writeLabels, + boolean labelSelect, + boolean writeReferencers + ) throws java.io.IOException { + writeGraph( + methodDesc.getSymbol() + + methodDesc.getNum() + + fn.toString(), + writeLabels, + labelSelect, + writeReferencers + ); + } + public void writeGraph( Descriptor methodDesc, FlatNode fn, boolean writeLabels, @@ -1527,6 +1523,7 @@ public class OwnershipGraph { methodDesc.getNum() + fn.toString(), writeLabels, + false, writeReferencers ); } @@ -1540,12 +1537,29 @@ public class OwnershipGraph { methodDesc.getNum() + "COMPLETE", writeLabels, + false, + writeReferencers + ); + } + + public void writeGraph( Descriptor methodDesc, + boolean writeLabels, + boolean labelSelect, + boolean writeReferencers + ) throws java.io.IOException { + writeGraph( + methodDesc.getSymbol() + + methodDesc.getNum() + + "COMPLETE", + writeLabels, + labelSelect, writeReferencers ); } public void writeGraph( String graphName, boolean writeLabels, + boolean labelSelect, boolean writeReferencers ) throws java.io.IOException { @@ -1587,6 +1601,16 @@ public class OwnershipGraph { Map.Entry me = (Map.Entry) i.next(); LabelNode ln = (LabelNode) me.getValue(); + if( labelSelect ) { + String labelStr = ln.getTempDescriptorString(); + if( labelStr.startsWith( "___temp" ) || + labelStr.startsWith( "___dst" ) || + labelStr.startsWith( "___srctmp" ) || + labelStr.startsWith( "___neverused" ) ) { + continue; + } + } + HeapRegionNode hrn = null; Iterator heapRegionsItr = ln.setIteratorToReferencedRegions(); while( heapRegionsItr.hasNext() ) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java index b3a35fcf..d412cffd 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -201,7 +201,8 @@ public class ReachabilitySet extends Canonical { } - public ReachabilitySet ageTokens( AllocationSite as ) { + public ReachabilitySet ageTokens( AllocationSite as ) { + ReachabilitySet rsOut = new ReachabilitySet(); Iterator itrS = this.iterator(); diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java index c9c96abe..edd9edcc 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java @@ -31,10 +31,12 @@ public class TokenTupleSet extends Canonical { return tokenTuples.iterator(); } + /* public TokenTupleSet add( TokenTuple tt ) { TokenTupleSet ttsOut = new TokenTupleSet( tt ); return this.union( ttsOut ); } + */ public TokenTupleSet union( TokenTupleSet ttsIn ) { TokenTupleSet ttsOut = new TokenTupleSet( this ); @@ -144,7 +146,7 @@ public class TokenTupleSet extends Canonical { } public TokenTupleSet ageTokens( AllocationSite as ) { - TokenTupleSet ttsOut = new TokenTupleSet( this ); + TokenTupleSet ttsOut = new TokenTupleSet(); TokenTuple ttSummary = null; boolean foundOldest = false; @@ -158,26 +160,29 @@ public class TokenTupleSet extends Canonical { // summary tokens and tokens not associated with // the site should be left alone - if( age != AllocationSite.AGE_notInThisSite ) { + 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 a token + // 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 ); - tt = tt.changeTokenTo( tokenToChangeTo ); + TokenTuple ttAged = tt.changeTokenTo( tokenToChangeTo ); + ttsOut.tokenTuples.add( ttAged ); } - } - ttsOut.add( tt ); + } } // there are four cases to consider here @@ -189,15 +194,15 @@ public class TokenTupleSet extends Canonical { // Merge them by increasing arity of summary // 4. (not handled) we found neither, do nothing if ( ttSummary != null && !foundOldest ) { - ttsOut.add( ttSummary ); + ttsOut.tokenTuples.add( ttSummary ); } else if( ttSummary == null && foundOldest ) { - ttsOut.add( new TokenTuple( as.getSummary(), + ttsOut.tokenTuples.add( new TokenTuple( as.getSummary(), true, TokenTuple.ARITY_ONE ).makeCanonical() ); } else if( ttSummary != null && foundOldest ) { - ttsOut.add( ttSummary.increaseArity() ); + ttsOut.tokenTuples.add( ttSummary.increaseArity() ); } return ttsOut.makeCanonical(); diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index 8b843453..c616953a 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -53,29 +53,28 @@ public class Foo { // look for the parameter s as a label referencing // a heap region that is multi-object, flagged, not summary task Startup( StartupObject s{ initialstate } ) { - + while( false ) { Foo a = new Foo(); a.x = new Foo(); + a.x.x = new Foo(); } - - /* + + Foo b; while( false ) { Foo c = new Foo(); c.x = b; b = c; } - */ - - /* - Foo a = new Foo(); - Foo b = new Foo(); - Foo c = new Foo(); + + + Foo d = new Foo(); + Foo e = new Foo(); + Foo f = new Foo(); - a.x = b; - b.x = c; - */ + d.x = e; + e.x = f; taskexit( s{ !initialstate } ); } -- 2.34.1