From 4720a1389e07ebc94012b458c93d4e349dff2f74 Mon Sep 17 00:00:00 2001 From: jjenista Date: Tue, 15 Jul 2008 21:42:41 +0000 Subject: [PATCH] More reachability implementation, no token propagation yet. --- .../OwnershipAnalysis/HeapRegionNode.java | 16 ++++++ .../OwnershipAnalysis/OwnershipGraph.java | 52 ++++++++++++++++--- .../ReferenceEdgeProperties.java | 32 ++++++++++-- .../OwnershipAnalysisTest/test01/test01.java | 15 ++++++ 4 files changed, 103 insertions(+), 12 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java index 08502304..6650e669 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java +++ b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java @@ -18,6 +18,7 @@ public class HeapRegionNode extends OwnershipNode { protected AllocationSite allocSite; protected ReachabilitySet alpha; + protected ReachabilitySet alphaNew; protected String description; @@ -36,6 +37,7 @@ public class HeapRegionNode extends OwnershipNode { this.isNewSummary = isNewSummary; this.allocSite = allocSite; this.alpha = alpha; + this.alphaNew = null; this.description = description; referencers = new HashSet(); @@ -126,6 +128,20 @@ public class HeapRegionNode extends OwnershipNode { return alpha; } + public ReachabilitySet getAlphaNew() { + return alphaNew; + } + + public void setAlphaNew( ReachabilitySet alpha ) { + this.alphaNew = alpha; + } + + public void applyAlphaNew() { + assert alphaNew != null; + alpha = alphaNew; + alphaNew = null; + } + public String getIDString() { return id.toString(); diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index afab559d..cee91235 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -156,6 +156,12 @@ public class OwnershipGraph { } + + protected void propagateTokens( HeapRegionNode nPrime, ChangeTupleSet c0 ) { + + } + + //////////////////////////////////////////////////// // // Assignment Operation Methods @@ -215,6 +221,7 @@ public class OwnershipGraph { ReachabilitySet beta2 = rep2.getBeta(); ReferenceEdgeProperties rep = rep2.copy(); + rep.setIsInitialParamReflexive( false ); rep.setBeta( beta1.intersection( beta2 ) ); addReferenceEdge( dstln, hrnOneHop, rep ); @@ -225,25 +232,54 @@ public class OwnershipGraph { public void assignFieldToTemp( TempDescriptor src, TempDescriptor dst, FieldDescriptor fd ) { + + // I think my use of src and dst are actually backwards in this method! + // acccording to the Reachability Notes, think of dst at N and src as N prime + LabelNode srcln = getLabelNodeFromTemp( src ); LabelNode dstln = getLabelNodeFromTemp( dst ); - HeapRegionNode hrn = null; + HashSet nodesWithNewAlpha = new HashSet(); + HashSet edgesWithNewBeta = new HashSet(); + + HeapRegionNode hrn = null; + ReferenceEdgeProperties rep = null; Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions(); while( dstRegionsItr.hasNext() ) { - Map.Entry me = (Map.Entry) dstRegionsItr.next(); - hrn = (HeapRegionNode) me.getKey(); + Map.Entry me = (Map.Entry) dstRegionsItr.next(); + hrn = (HeapRegionNode) me.getKey(); + rep = (ReferenceEdgeProperties) me.getValue(); - HeapRegionNode hrnSrc = null; + ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() ); + + HeapRegionNode hrnSrc = null; + ReferenceEdgeProperties repSrc = null; Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions(); while( srcRegionsItr.hasNext() ) { - Map.Entry meS = (Map.Entry) srcRegionsItr.next(); - hrnSrc = (HeapRegionNode) meS.getKey(); + Map.Entry meS = (Map.Entry) srcRegionsItr.next(); + hrnSrc = (HeapRegionNode) meS.getKey(); + repSrc = (ReferenceEdgeProperties) meS.getValue(); + + ReferenceEdgeProperties repNew + = new ReferenceEdgeProperties( false, false, null ); - ReferenceEdgeProperties rep = new ReferenceEdgeProperties(); - addReferenceEdge( hrn, hrnSrc, rep ); + addReferenceEdge( hrn, hrnSrc, repNew ); + + ReachabilitySet O = srcln.getReferenceTo( hrnSrc ).getBeta(); + ChangeTupleSet C = O.unionUpArity( R ); + propagateTokens( hrnSrc, C ); } } + + Iterator nodeItr = nodesWithNewAlpha.iterator(); + while( nodeItr.hasNext() ) { + ((HeapRegionNode) nodeItr.next()).applyAlphaNew(); + } + + Iterator edgeItr = edgesWithNewBeta.iterator(); + while( edgeItr.hasNext() ) { + ((ReferenceEdgeProperties) edgeItr.next()).applyBetaNew(); + } } public void assignTempToParameterAllocation( boolean isTask, diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java index c0a90736..3226d681 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java @@ -2,16 +2,25 @@ package Analysis.OwnershipAnalysis; public class ReferenceEdgeProperties { + protected boolean isUnique; + protected boolean isInitialParamReflexive; + + protected ReachabilitySet beta; + protected ReachabilitySet betaNew; + + public ReferenceEdgeProperties() { this.isUnique = false; this.isInitialParamReflexive = false; this.beta = new ReachabilitySet(); + this.betaNew = null; } public ReferenceEdgeProperties( boolean isUnique ) { this.isUnique = isUnique; this.isInitialParamReflexive = false; this.beta = new ReachabilitySet(); + this.betaNew = null; } public ReferenceEdgeProperties( boolean isUnique, @@ -19,6 +28,7 @@ public class ReferenceEdgeProperties { this.isUnique = isUnique; this.isInitialParamReflexive = isInitialParamReflexive; this.beta = new ReachabilitySet(); + this.betaNew = null; } public ReferenceEdgeProperties( boolean isUnique, @@ -27,6 +37,7 @@ public class ReferenceEdgeProperties { this.isUnique = isUnique; this.isInitialParamReflexive = isInitialParamReflexive; this.beta = beta; + this.betaNew = null; } @@ -37,7 +48,7 @@ public class ReferenceEdgeProperties { } - protected boolean isUnique; + public boolean isUnique() { return isUnique; } @@ -46,7 +57,7 @@ public class ReferenceEdgeProperties { } - protected boolean isInitialParamReflexive; + public boolean isInitialParamReflexive() { return isInitialParamReflexive; } @@ -55,7 +66,7 @@ public class ReferenceEdgeProperties { } - protected ReachabilitySet beta; + public ReachabilitySet getBeta() { return beta; } @@ -63,6 +74,19 @@ public class ReferenceEdgeProperties { this.beta = beta; } + public ReachabilitySet getBetaNew() { + return betaNew; + } + public void setBetaNew( ReachabilitySet beta ) { + this.betaNew = beta; + } + public void applyBetaNew() { + assert betaNew != null; + beta = betaNew; + betaNew = null; + } + + public boolean equals( ReferenceEdgeProperties rep ) { return isUnique == rep.isUnique() && isInitialParamReflexive == rep.isInitialParamReflexive(); @@ -80,7 +104,7 @@ public class ReferenceEdgeProperties { } */ if( isInitialParamReflexive ) { - edgeLabel += "Rfx\\n"; + edgeLabel += "Rflx\\n"; } edgeLabel += getBetaString(); return edgeLabel; diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index fff7a976..7c3e770f 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -36,6 +36,8 @@ public class Baw { public class Foo { + flag f; + public Foo() {} public Foo x; @@ -62,6 +64,18 @@ task Startup( StartupObject s{ initialstate } ) { } +task NewObject( Foo a{ f }, Foo b{ f } ) { + + Foo c = new Foo(); + + a.x = c; + + taskexit( a{ !f }, b{ !f } ); +} + + + +/* // this task allocates a new object, so there should // be a heap region for the parameter, and several // heap regions for the allocation site, but the label @@ -123,3 +137,4 @@ task ClobberInitParamReflex( Voo v{ f }, Voo w{ f } ) { taskexit( v{ !f }, w{ !f } ); } +*/ \ No newline at end of file -- 2.34.1