From dc2cb5f13bf4e45fe4dcf0e0af1d1da8949a7711 Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 17 Jul 2008 18:32:15 +0000 Subject: [PATCH] Fixed propagation, different change sets for the x and y branches before a new edge is added --- .../OwnershipAnalysis/OwnershipGraph.java | 93 ++++++++++++++----- .../OwnershipAnalysis/ReachabilitySet.java | 23 +---- .../OwnershipAnalysisTest/test01/test01.java | 38 +++++++- 3 files changed, 111 insertions(+), 43 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 14bcff27..6f902e53 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -179,31 +179,23 @@ public class OwnershipGraph { Hashtable nodeChangesMade = new Hashtable(); - Hashtable edgeChangesMade - = new Hashtable(); - - System.out.println( "New propagation with changes "+c0 ); - while( !todoNodes.isEmpty() ) { HeapRegionNode n = todoNodes.iterator().next(); todoNodes.remove( n ); - - System.out.println( " Propagating tokens over "+n ); + + ChangeTupleSet C = nodePlannedChanges.get( n ); if( !nodeChangesMade.containsKey( n ) ) { nodeChangesMade.put( n, new ChangeTupleSet().makeCanonical() ); } - - ChangeTupleSet C = nodePlannedChanges.get( n ); Iterator itrC = C.iterator(); while( itrC.hasNext() ) { ChangeTuple c = (ChangeTuple) itrC.next(); - System.out.println( " Considering applying "+c ); - if( n.getAlpha().contains( c.getSetToMatch() ) ) { - n.setAlphaNew( n.getAlpha().union( c.getSetToAdd() ) ); + ReachabilitySet withChange = n.getAlpha().union( c.getSetToAdd() ); + n.setAlphaNew( n.getAlphaNew().union( withChange ) ); nodesWithNewAlpha.add( n ); nodeChangesMade.put( n, nodeChangesMade.get( n ).union( c ) ); } @@ -232,7 +224,7 @@ public class OwnershipGraph { m = (HeapRegionNode) me.getKey(); f = (ReferenceEdgeProperties) me.getValue(); - ChangeTupleSet changesToPass = new ChangeTupleSet(); + ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical(); Iterator itrCprime = Cprime.iterator(); while( itrCprime.hasNext() ) { @@ -256,7 +248,54 @@ public class OwnershipGraph { } } } - + + + while( !todoEdges.isEmpty() ) { + ReferenceEdgeProperties e = todoEdges.iterator().next(); + todoEdges.remove( e ); + + if( !edgePlannedChanges.containsKey( e ) ) { + edgePlannedChanges.put( e, new ChangeTupleSet().makeCanonical() ); + } + + ChangeTupleSet C = edgePlannedChanges.get( e ); + + ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical(); + + Iterator itrC = C.iterator(); + while( itrC.hasNext() ) { + ChangeTuple c = (ChangeTuple) itrC.next(); + if( e.getBeta().contains( c.getSetToMatch() ) ) { + ReachabilitySet withChange = e.getBeta().union( c.getSetToAdd() ); + e.setBetaNew( e.getBetaNew().union( withChange ) ); + edgesWithNewBeta.add( e ); + changesToPass = changesToPass.union( c ); + } + } + + OwnershipNode onSrc = e.getSrc(); + + if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) { + HeapRegionNode n = (HeapRegionNode) onSrc; + Iterator referItr = n.iteratorToReferencers(); + + while( referItr.hasNext() ) { + OwnershipNode onRef = (OwnershipNode) referItr.next(); + ReferenceEdgeProperties f = onRef.getReferenceTo( n ); + + if( !edgePlannedChanges.containsKey( f ) ) { + edgePlannedChanges.put( f, new ChangeTupleSet().makeCanonical() ); + } + + ChangeTupleSet currentChanges = edgePlannedChanges.get( f ); + + if( !changesToPass.isSubset( currentChanges ) ) { + todoEdges.add( f ); + edgePlannedChanges.put( f, currentChanges.union( changesToPass ) ); + } + } + } + } } @@ -357,15 +396,21 @@ public class OwnershipGraph { Map.Entry meS = (Map.Entry) srcRegionsItr.next(); hrnSrc = (HeapRegionNode) meS.getKey(); repSrc = (ReferenceEdgeProperties) meS.getValue(); + + ReachabilitySet O = srcln.getReferenceTo( hrnSrc ).getBeta(); + + ChangeTupleSet Cy = O.unionUpArity( R ); + ChangeTupleSet Cx = R.unionUpArity( 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, null ); + = new ReferenceEdgeProperties( false, false, repSrc.getBetaNew() ); addReferenceEdge( hrn, hrnSrc, repNew ); - - ReachabilitySet O = srcln.getReferenceTo( hrnSrc ).getBeta(); - ChangeTupleSet C = O.unionUpArity( R ); - propagateTokens( hrnSrc, C, nodesWithNewAlpha, edgesWithNewBeta ); } } @@ -436,8 +481,8 @@ public class OwnershipGraph { LabelNode dst = getLabelNodeFromTemp( td ); clearReferenceEdgesFrom( dst ); - - addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false, false, null ) ); + + addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false, false, hrnNewest.getAlpha() ) ); } @@ -496,7 +541,7 @@ public class OwnershipGraph { boolean hasFlags = false; if( as.getType().isClass() ) { - hasFlags = as.getType().getClassDesc().hasFlags(); + hasFlags = as.getType().getClassDesc().hasFlags(); } hrnSummary = createNewHeapRegionNode( idSummary, @@ -1473,7 +1518,7 @@ public class OwnershipGraph { bw.write( " " + ln.toString() + " -> " + hrn.toString() + "[label=\"" + rep.toEdgeLabelString() + - "\"];\n" ); + "\",decorate];\n" ); } } } @@ -1554,7 +1599,7 @@ public class OwnershipGraph { bw.write( " " + hrn.toString() + " -> " + hrnChild.toString() + "[label=\"" + rep.toEdgeLabelString() + - "\"];\n" ); + "\",decorate];\n" ); break; } diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java index 9439f405..918d43c8 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -12,8 +12,8 @@ public class ReachabilitySet extends Canonical { public ReachabilitySet() { possibleReachabilities = new HashSet(); - TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical(); - possibleReachabilities.add( ttsEmpty ); + //TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical(); + //possibleReachabilities.add( ttsEmpty ); } public ReachabilitySet( TokenTupleSet tts ) { @@ -48,14 +48,7 @@ public class ReachabilitySet extends Canonical { assert rsIn != null; ReachabilitySet rsOut = new ReachabilitySet( this ); - - System.out.println( "rsIn = "+rsIn ); - System.out.println( "rsOut = "+rsOut ); - rsOut.possibleReachabilities.addAll( rsIn.possibleReachabilities ); - - System.out.println( "union = "+rsOut ); - return rsOut.makeCanonical(); } @@ -149,18 +142,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; } @@ -180,7 +168,6 @@ public class ReachabilitySet extends Canonical { } s += " ]"; - return s; } } diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index 443375d0..ec5c6426 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -65,7 +65,7 @@ task Startup( StartupObject s{ initialstate } ) { taskexit( s{ !initialstate } ); } - +/* task NewObject( Foo a{ f }, Foo b{ f } ) { Foo c = new Foo(); @@ -74,7 +74,43 @@ task NewObject( Foo a{ f }, Foo b{ f } ) { taskexit( a{ !f }, b{ !f } ); } +*/ + +task NewObjectA( Foo a{ f }, Foo b{ f } ) { + + Foo c = new Foo(); + Foo d = new Foo(); + + c.x = d; + a.x = c; + + taskexit( a{ !f }, b{ !f } ); +} + +task NewObjectB( Foo a{ f }, Foo b{ f } ) { + + Foo c = new Foo(); + Foo d = new Foo(); + + a.x = c; + c.x = d; + + taskexit( a{ !f }, b{ !f } ); +} + +/* +task NewObject2( Foo a{ f }, Foo b{ f } ) { + Foo c; + + while( false ) { + c = new Foo(); + c.x = new Foo(); + } + + taskexit( a{ !f }, b{ !f } ); +} +*/ /* -- 2.34.1