From c36650a2762616cd083646163efe8d552c0655b6 Mon Sep 17 00:00:00 2001 From: jjenista Date: Tue, 15 Jul 2008 23:24:06 +0000 Subject: [PATCH] Token propagation implemented, stable but incorrect. This is just a capture. --- .../OwnershipAnalysis/ChangeTupleSet.java | 15 ++++ .../OwnershipAnalysis/HeapRegionNode.java | 11 ++- .../OwnershipAnalysis/OwnershipGraph.java | 89 +++++++++++++++++++ .../OwnershipAnalysis/ReachabilitySet.java | 21 +++++ .../ReferenceEdgeProperties.java | 69 ++++++++++---- 5 files changed, 186 insertions(+), 19 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java index afbd0405..498cda9b 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java @@ -32,12 +32,27 @@ public class ChangeTupleSet extends Canonical { } public ChangeTupleSet union( ChangeTupleSet ctsIn ) { + assert ctsIn != null; + ChangeTupleSet ctsOut = new ChangeTupleSet( this ); ctsOut.changeTuples.addAll( ctsIn.changeTuples ); return ctsOut.makeCanonical(); } + public ChangeTupleSet union( ChangeTuple ctIn ) { + assert ctIn != null; + + ChangeTupleSet ctsOut = new ChangeTupleSet( this ); + ctsOut.changeTuples.add( ctIn ); + return ctsOut.makeCanonical(); + } + + public boolean isEmpty() { + return changeTuples.isEmpty(); + } + public boolean isSubset( ChangeTupleSet ctsIn ) { + assert ctsIn != null; return ctsIn.changeTuples.containsAll( this.changeTuples ); } diff --git a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java index 6650e669..237f2a51 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java +++ b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java @@ -37,9 +37,11 @@ public class HeapRegionNode extends OwnershipNode { this.isNewSummary = isNewSummary; this.allocSite = allocSite; this.alpha = alpha; - this.alphaNew = null; this.description = description; + alphaNew = new ReachabilitySet(); + alphaNew = alphaNew.makeCanonical(); + referencers = new HashSet(); memberFields = new HashSet(); } @@ -138,8 +140,11 @@ public class HeapRegionNode extends OwnershipNode { public void applyAlphaNew() { assert alphaNew != null; - alpha = alphaNew; - alphaNew = null; + + alpha = alphaNew; + + alphaNew = new ReachabilitySet(); + alphaNew = alphaNew.makeCanonical(); } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index cee91235..6fb336a0 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -115,6 +115,8 @@ public class OwnershipGraph { assert rep != null; referencer.addReferencedRegion( referencee, rep ); referencee.addReferencer( referencer ); + rep.setSrc( referencer ); + rep.setDst( referencee ); } protected void removeReferenceEdge( OwnershipNode referencer, @@ -158,7 +160,94 @@ public class OwnershipGraph { protected void propagateTokens( HeapRegionNode nPrime, ChangeTupleSet c0 ) { + HashSet todoNodes + = new HashSet(); + todoNodes.add( nPrime ); + HashSet todoEdges + = new HashSet(); + + Hashtable nodePlannedChanges + = new Hashtable(); + nodePlannedChanges.put( nPrime, c0 ); + + Hashtable edgePlannedChanges + = new Hashtable(); + + Hashtable nodeChangesMade + = new Hashtable(); + + Hashtable edgeChangesMade + = new Hashtable(); + + while( !todoNodes.isEmpty() ) { + HeapRegionNode n = todoNodes.iterator().next(); + todoNodes.remove( 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(); + + if( n.getAlpha().contains( c.getSetToMatch() ) ) { + n.setAlphaNew( n.getAlphaNew().union( c.getSetToAdd() ) ); + nodeChangesMade.put( n, nodeChangesMade.get( n ).union( c ) ); + } + } + + ChangeTupleSet Cprime = nodeChangesMade.get( n ); + + Iterator referItr = n.iteratorToReferencers(); + while( referItr.hasNext() ) { + OwnershipNode on = (OwnershipNode) referItr.next(); + ReferenceEdgeProperties rep = on.getReferenceTo( n ); + todoEdges.add( rep ); + + if( !edgePlannedChanges.containsKey( rep ) ) { + edgePlannedChanges.put( rep, new ChangeTupleSet().makeCanonical() ); + } + + edgePlannedChanges.put( rep, edgePlannedChanges.get( rep ).union( Cprime ) ); + } + + HeapRegionNode m = null; + ReferenceEdgeProperties f = null; + Iterator refeeItr = n.setIteratorToReferencedRegions(); + while( refeeItr.hasNext() ) { + Map.Entry me = (Map.Entry) refeeItr.next(); + m = (HeapRegionNode) me.getKey(); + f = (ReferenceEdgeProperties) me.getValue(); + + ChangeTupleSet changesToPass = new ChangeTupleSet(); + + Iterator itrCprime = Cprime.iterator(); + while( itrCprime.hasNext() ) { + ChangeTuple c = (ChangeTuple) itrCprime.next(); + if( f.getBeta().contains( c.getSetToMatch() ) ) { + changesToPass = changesToPass.union( c ); + } + } + + if( !changesToPass.isEmpty() ) { + if( !nodePlannedChanges.containsKey( m ) ) { + nodePlannedChanges.put( m, new ChangeTupleSet().makeCanonical() ); + } + + ChangeTupleSet currentChanges = nodePlannedChanges.get( m ); + + if( !changesToPass.isSubset( currentChanges ) ) { + todoNodes.add( m ); + nodePlannedChanges.put( m, currentChanges.union( changesToPass ) ); + } + } + } + } + } diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java index d333f2c8..842098d1 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -15,6 +15,7 @@ public class ReachabilitySet extends Canonical { } public ReachabilitySet( TokenTupleSet tts ) { + assert tts != null; possibleReachabilities = new HashSet(); possibleReachabilities.add( tts ); } @@ -24,6 +25,7 @@ public class ReachabilitySet extends Canonical { } public ReachabilitySet( ReachabilitySet rs ) { + assert rs != null; possibleReachabilities = (HashSet) rs.possibleReachabilities.clone(); // again, DEEP COPY?! } @@ -31,17 +33,34 @@ public class ReachabilitySet extends Canonical { return (ReachabilitySet) Canonical.makeCanonical( this ); } + public boolean contains( TokenTupleSet tts ) { + assert tts != null; + return possibleReachabilities.contains( tts ); + } + public Iterator iterator() { return possibleReachabilities.iterator(); } public ReachabilitySet union( ReachabilitySet rsIn ) { + assert rsIn != null; + ReachabilitySet rsOut = new ReachabilitySet( this ); rsOut.possibleReachabilities.addAll( rsIn.possibleReachabilities ); return rsOut.makeCanonical(); } + public ReachabilitySet union( TokenTupleSet ttsIn ) { + assert ttsIn != null; + + ReachabilitySet rsOut = new ReachabilitySet( this ); + rsOut.possibleReachabilities.add( ttsIn ); + return rsOut.makeCanonical(); + } + public ReachabilitySet intersection( ReachabilitySet rsIn ) { + assert rsIn != null; + ReachabilitySet rsOut = new ReachabilitySet(); Iterator i = this.iterator(); @@ -56,6 +75,8 @@ public class ReachabilitySet extends Canonical { } public ChangeTupleSet unionUpArity( ReachabilitySet rsIn ) { + assert rsIn != null; + ChangeTupleSet ctsOut = new ChangeTupleSet(); Iterator itrO = this.iterator(); diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java index 3226d681..4b85b2af 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java @@ -8,27 +8,20 @@ public class ReferenceEdgeProperties { protected ReachabilitySet beta; protected ReachabilitySet betaNew; + protected OwnershipNode src; + protected HeapRegionNode dst; public ReferenceEdgeProperties() { - this.isUnique = false; - this.isInitialParamReflexive = false; - this.beta = new ReachabilitySet(); - this.betaNew = null; + this( false, false, null ); } public ReferenceEdgeProperties( boolean isUnique ) { - this.isUnique = isUnique; - this.isInitialParamReflexive = false; - this.beta = new ReachabilitySet(); - this.betaNew = null; + this( isUnique, false, null ); } public ReferenceEdgeProperties( boolean isUnique, boolean isInitialParamReflexive ) { - this.isUnique = isUnique; - this.isInitialParamReflexive = isInitialParamReflexive; - this.beta = new ReachabilitySet(); - this.betaNew = null; + this( isUnique, isInitialParamReflexive, null ); } public ReferenceEdgeProperties( boolean isUnique, @@ -36,11 +29,45 @@ public class ReferenceEdgeProperties { ReachabilitySet beta) { this.isUnique = isUnique; this.isInitialParamReflexive = isInitialParamReflexive; - this.beta = beta; - this.betaNew = null; + + // these members are set by higher-level code + // when this ReferenceEdgeProperties object is + // applied to an edge + this.src = null; + this.dst = null; + + if( beta != null ) { + this.beta = beta; + } else { + this.beta = new ReachabilitySet(); + this.beta = this.beta.makeCanonical(); + } + + betaNew = new ReachabilitySet(); + betaNew = betaNew.makeCanonical(); + } + + + public OwnershipNode getSrc() { + return src; + } + + public void setSrc( OwnershipNode on ) { + assert on != null; + src = on; + } + + public HeapRegionNode getDst() { + return dst; + } + + public void setDst( HeapRegionNode hrn ) { + assert hrn != null; + dst = hrn; } + // copying does not copy source and destination members! public ReferenceEdgeProperties copy() { return new ReferenceEdgeProperties( isUnique, isInitialParamReflexive, @@ -70,24 +97,34 @@ public class ReferenceEdgeProperties { public ReachabilitySet getBeta() { return beta; } + public void setBeta( ReachabilitySet beta ) { + assert beta != null; this.beta = beta; } public ReachabilitySet getBetaNew() { return betaNew; } + public void setBetaNew( ReachabilitySet beta ) { + assert beta != null; this.betaNew = beta; } + public void applyBetaNew() { assert betaNew != null; - beta = betaNew; - betaNew = null; + + beta = betaNew; + + betaNew = new ReachabilitySet(); + betaNew = betaNew.makeCanonical(); } public boolean equals( ReferenceEdgeProperties rep ) { + assert rep != null; + return isUnique == rep.isUnique() && isInitialParamReflexive == rep.isInitialParamReflexive(); } -- 2.34.1