From 00d0dadf59c7541895a95bbea1aacef44a48d6a7 Mon Sep 17 00:00:00 2001 From: jjenista Date: Tue, 15 Jul 2008 19:22:32 +0000 Subject: [PATCH] Added reachability to simple edge cases. --- .../OwnershipAnalysis/OwnershipAnalysis.java | 14 ++-- .../OwnershipAnalysis/OwnershipGraph.java | 69 ++++++++++--------- .../ReferenceEdgeProperties.java | 25 +++++-- .../OwnershipAnalysisTest/test01/test01.java | 9 ++- 4 files changed, 65 insertions(+), 52 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index 23d9af6f..de8be215 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -277,11 +277,10 @@ public class OwnershipAnalysis { OwnershipGraph og = analyzeFlatMethod( d, fm ); OwnershipGraph ogPrev = mapDescriptorToCompleteOwnershipGraph.get( d ); - if( !og.equals( ogPrev ) ) { mapDescriptorToCompleteOwnershipGraph.put( d, og ); - og.writeGraph( d, false, false ); + og.writeGraph( d, true, false ); // only methods have dependents, tasks cannot // be invoked by any user program calls @@ -523,14 +522,11 @@ public class OwnershipAnalysis { // every possible method we might have chosen // og.resolveMethodCall( fc, md.isStatic(), flatm, ogAllPossibleCallees ); - - //og.writeGraph( methodDesc, fn ); break; case FKind.FlatReturnNode: FlatReturnNode frn = (FlatReturnNode) fn; setRetNodes.add( frn ); - //og.writeGraph( methodDesc, fn ); break; } } @@ -561,6 +557,7 @@ public class OwnershipAnalysis { // return just the allocation site associated with one FlatNew node private AllocationSite getAllocationSiteFromFlatNewPRIVATE( FlatNew fn ) { + if( !mapFlatNewToAllocationSite.containsKey( fn ) ) { AllocationSite as = new AllocationSite( allocationDepth, fn.getType() ); @@ -689,12 +686,13 @@ public class OwnershipAnalysis { return idSet; } + private HashSet getHeapRegionIDset( AllocationSite alloc ) { HashSet idSet = new HashSet(); - for( int i = 0; i < alloc.getAllocationDepth(); ++i ) { - Integer id = alloc.getIthOldest( i ); + for( int i = 0; i < alloc.getAllocationDepth(); ++i ) { + Integer id = alloc.getIthOldest( i ); idSet.add( id ); } @@ -707,7 +705,7 @@ public class OwnershipAnalysis { private HashSet getHeapRegionIDset( HashSet allocSet ) { HashSet idSet = new HashSet(); - + Iterator allocItr = allocSet.iterator(); while( allocItr.hasNext() ) { AllocationSite alloc = (AllocationSite) allocItr.next(); diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 0eb63db7..afab559d 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -178,45 +178,52 @@ public class OwnershipGraph { LabelNode dstln = getLabelNodeFromTemp( dst ); clearReferenceEdgesFrom( dstln ); + HeapRegionNode newReferencee = null; - Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions(); + Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions(); while( srcRegionsItr.hasNext() ) { - Map.Entry me = (Map.Entry) srcRegionsItr.next(); - newReferencee = (HeapRegionNode) me.getKey(); + Map.Entry me = (Map.Entry) srcRegionsItr.next(); + newReferencee = (HeapRegionNode) me.getKey(); + ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue(); - ReferenceEdgeProperties rep = new ReferenceEdgeProperties(); - addReferenceEdge( dstln, newReferencee, rep ); + addReferenceEdge( dstln, newReferencee, rep.copy() ); } } - public void assignTempToField( TempDescriptor src, - TempDescriptor dst, + public void assignTempToField( TempDescriptor src, + TempDescriptor dst, FieldDescriptor fd ) { LabelNode srcln = getLabelNodeFromTemp( src ); LabelNode dstln = getLabelNodeFromTemp( dst ); clearReferenceEdgesFrom( dstln ); - HeapRegionNode hrn = null; - Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions(); + HeapRegionNode hrn = null; + Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions(); while( srcRegionsItr.hasNext() ) { - Map.Entry me = (Map.Entry) srcRegionsItr.next(); - hrn = (HeapRegionNode) me.getKey(); + Map.Entry me = (Map.Entry) srcRegionsItr.next(); + hrn = (HeapRegionNode) me.getKey(); + ReferenceEdgeProperties rep1 = (ReferenceEdgeProperties) me.getValue(); + ReachabilitySet beta1 = rep1.getBeta(); HeapRegionNode hrnOneHop = null; Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions(); while( hrnRegionsItr.hasNext() ) { - Map.Entry meH = (Map.Entry) hrnRegionsItr.next(); - hrnOneHop = (HeapRegionNode) meH.getKey(); + Map.Entry meH = (Map.Entry) hrnRegionsItr.next(); + hrnOneHop = (HeapRegionNode) meH.getKey(); + ReferenceEdgeProperties rep2 = (ReferenceEdgeProperties) meH.getValue(); + ReachabilitySet beta2 = rep2.getBeta(); + + ReferenceEdgeProperties rep = rep2.copy(); + rep.setBeta( beta1.intersection( beta2 ) ); - ReferenceEdgeProperties rep = new ReferenceEdgeProperties(); addReferenceEdge( dstln, hrnOneHop, rep ); } } } - public void assignFieldToTemp( TempDescriptor src, - TempDescriptor dst, + public void assignFieldToTemp( TempDescriptor src, + TempDescriptor dst, FieldDescriptor fd ) { LabelNode srcln = getLabelNodeFromTemp( src ); LabelNode dstln = getLabelNodeFromTemp( dst ); @@ -263,12 +270,16 @@ public class OwnershipGraph { id2paramIndex.put( newID, paramIndex ); paramIndex2id.put( paramIndex, newID ); + ReachabilitySet beta = new ReachabilitySet( new TokenTuple( newID, + false, + TokenTuple.ARITY_ONE ) ); + // heap regions for parameters are always multiple object (see above) // and have a reference to themselves, because we can't know the // structure of memory that is passed into the method. We're assuming // the worst here. - addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( false ) ); - addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( false, true ) ); + addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( false, false, beta ) ); + addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( false, true, beta ) ); } public void assignTempToNewAllocation( TempDescriptor td, @@ -278,13 +289,14 @@ public class OwnershipGraph { age( as ); + // after the age operation the newest (or zero-ith oldest) // node associated with the allocation site should have // no references to it as if it were a newly allocated // heap region, so make a reference to it to complete // this operation - Integer id = as.getIthOldest( 0 ); - HeapRegionNode hrnNewest = id2hrn.get( id ); + Integer idNewest = as.getIthOldest( 0 ); + HeapRegionNode hrnNewest = id2hrn.get( idNewest ); assert hrnNewest != null; LabelNode dst = getLabelNodeFromTemp( td ); @@ -475,7 +487,6 @@ public class OwnershipGraph { clearReferenceEdgesTo ( hrn0 ); } - // some notes: // the heap regions that are specially allocated as multiple-object @@ -682,6 +693,7 @@ public class OwnershipGraph { if( !id2hrn.containsKey( idA ) ) { HeapRegionNode hrnB = hrnA.copy(); id2hrn.put( idA, hrnB ); + } else { // otherwise this is a node present in both graphs // so make the new reachability set a union of the @@ -1323,13 +1335,9 @@ public class OwnershipGraph { hrn = (HeapRegionNode) meH.getKey(); ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue(); - String edgeLabel = ""; - if( rep.isUnique() ) { - edgeLabel = "Unique"; - } bw.write( " " + ln.toString() + " -> " + hrn.toString() + - "[label=\"" + edgeLabel + + "[label=\"" + rep.toEdgeLabelString() + "\"];\n" ); } } @@ -1408,16 +1416,9 @@ public class OwnershipGraph { switch( mode ) { case VISIT_HRN_WRITE_FULL: - String edgeLabel = ""; - if( rep.isUnique() ) { - edgeLabel += "Unq"; - } - if( rep.isInitialParamReflexive() ) { - edgeLabel += "Rfx"; - } bw.write( " " + hrn.toString() + " -> " + hrnChild.toString() + - "[label=\"" + edgeLabel + + "[label=\"" + rep.toEdgeLabelString() + "\"];\n" ); break; } diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java index 72b4457b..c0a90736 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java @@ -32,7 +32,8 @@ public class ReferenceEdgeProperties { public ReferenceEdgeProperties copy() { return new ReferenceEdgeProperties( isUnique, - isInitialParamReflexive ); + isInitialParamReflexive, + beta ); } @@ -61,13 +62,27 @@ public class ReferenceEdgeProperties { public void setBeta( ReachabilitySet beta ) { this.beta = beta; } - public String getBetaString() { - return beta.toStringEscapeNewline(); - } - public boolean equals( ReferenceEdgeProperties rep ) { return isUnique == rep.isUnique() && isInitialParamReflexive == rep.isInitialParamReflexive(); } + + public String getBetaString() { + return beta.toStringEscapeNewline(); + } + + public String toEdgeLabelString() { + String edgeLabel = ""; + /* + if( rep.isUnique() ) { + edgeLabel += "Unq"; + } + */ + if( isInitialParamReflexive ) { + edgeLabel += "Rfx\\n"; + } + edgeLabel += getBetaString(); + return edgeLabel; + } } diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index dc458915..fff7a976 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -45,6 +45,7 @@ public class Foo { } } + // this empty task should still create a non-empty // ownership graph showing parameter allocation // look for the parameter s as a label referencing @@ -61,7 +62,6 @@ task Startup( StartupObject s{ initialstate } ) { } -/* // 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 @@ -89,7 +89,7 @@ task Branch( Voo v{ f } ) { taskexit( v{ !f } ); } -*/ + task NoAliasNewInLoop( Voo v{ f } ) { @@ -102,7 +102,7 @@ task NoAliasNewInLoop( Voo v{ f } ) { taskexit( v{ !f } ); } -/* + task NoAliasNewInLoopAnotherWay( Voo v{ f } ) { for( int i = 0; i < 10; ++i ) { @@ -117,10 +117,9 @@ task NoAliasNewInLoopAnotherWay( Voo v{ f } ) { taskexit( v{ !f } ); } + task ClobberInitParamReflex( Voo v{ f }, Voo w{ f } ) { v.b = v.bb; taskexit( v{ !f }, w{ !f } ); } - -*/ \ No newline at end of file -- 2.34.1