From 8f886168bb9a41655b0d29ef43f4554a0e2f7ab0 Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 10 Mar 2008 21:39:22 +0000 Subject: [PATCH] Most up-to-date allocation site algorithm implemented, but some references are being created incorrectly. Stable but not yet useful capture. --- .../OwnershipAnalysis/AllocationSite.java | 16 +- .../OwnershipAnalysis/OwnershipAnalysis.java | 37 ++- .../OwnershipAnalysis/OwnershipGraph.java | 258 ++++++++++++------ .../OwnershipAnalysisTest/test01/makefile | 3 + .../OwnershipAnalysisTest/test01/test01.java | 17 ++ 5 files changed, 222 insertions(+), 109 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java index 9a8ac2e6..cb2cbc83 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java +++ b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java @@ -21,8 +21,9 @@ import java.util.*; public class AllocationSite { - protected int allocationDepth; + protected int allocationDepth; protected Vector ithOldest; + protected Integer summary; public AllocationSite( int allocationDepth ) { assert allocationDepth >= 3; @@ -45,4 +46,17 @@ public class AllocationSite { return ithOldest.get( i ); } + + public Integer getOldest() { + return ithOldest.get( allocationDepth - 1 ); + } + + public void setSummary( Integer id ) { + assert id != null; + summary = id; + } + + public Integer getSummary() { + return summary; + } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index e045c8ca..39d3c900 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -15,6 +15,11 @@ public class OwnershipAnalysis { private int allocationDepth; + // used to identify HeapRegionNode objects + // A unique ID equates an object in one + // ownership graph with an object in another + // graph that logically represents the same + // heap region static private int uniqueIDcount = 0; @@ -222,13 +227,9 @@ public class OwnershipAnalysis { FlatNode fn, OwnershipGraph og ) throws java.io.IOException { - //System.out.println( "Analyszing a flat node" ); - TempDescriptor src; TempDescriptor dst; FieldDescriptor fld; - //String nodeDescription = "No description"; - //boolean writeGraph = false; // use node type to decide what alterations to make // to the ownership graph @@ -279,23 +280,16 @@ public class OwnershipAnalysis { og.writeGraph( methodDesc, fn ); break; - /* case FKind.FlatNew: FlatNew fnn = (FlatNew) fn; dst = fnn.getDst(); - og.assignTempToNewAllocation( dst, fnn ); + AllocationSite as = getAllocationSiteFromFlatNew( fnn ); + og.assignTempToNewAllocation( dst, as ); // !!!!!!!!!!!!!! // do this if the new object is a flagged type - //og.addAnalysisRegion( tdParam ); - - //nodeDescription = "New"; - //writeGraph = true; - og.writeGraph( fn ); - + //og.addAnalysisRegion( tdParam ); break; - - */ case FKind.FlatCall: //FlatCall fc = (FlatCall) fn; @@ -306,19 +300,18 @@ public class OwnershipAnalysis { break; case FKind.FlatReturnNode: - //nodeDescription = "Return"; - //writeGraph = true; - //og.writeCondensedAnalysis( makeCondensedAnalysisName( methodname, flatnodetolabel.get(fn) ) ); og.writeGraph( methodDesc, fn ); break; } } + static public Integer generateUniqueHeapRegionNodeID() { ++uniqueIDcount; return new Integer( uniqueIDcount ); } + private OwnershipGraph getGraphFromFlatNode( FlatNode fn ) { if( !mapFlatNodeToOwnershipGraph.containsKey( fn ) ) { mapFlatNodeToOwnershipGraph.put( fn, new OwnershipGraph( allocationDepth ) ); @@ -331,21 +324,23 @@ public class OwnershipAnalysis { mapFlatNodeToOwnershipGraph.put( fn, og ); } + private AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) { if( !mapFlatNewToAllocationSite.containsKey( fn ) ) { AllocationSite as = new AllocationSite( allocationDepth ); // the first k-1 nodes are single objects - for( int i = 0; i < allocationDepth - 1; ++i ) { - //HeapRegionNode hrn = createNewHeapRegionNode( null, true, false, false ); + for( int i = 0; i < allocationDepth; ++i ) { Integer id = generateUniqueHeapRegionNodeID(); + //HeapRegionNode hrn = createNewHeapRegionNode( null, true, false, false ); as.setIthOldest( i, id ); } // the kth node is a summary node //HeapRegionNode hrnNewSummary = createNewHeapRegionNode( null, false, false, true ); - Integer id2 = generateUniqueHeapRegionNodeID(); - as.setIthOldest( allocationDepth - 1, id2 ); + Integer idSummary = generateUniqueHeapRegionNodeID(); + //as.setIthOldest( allocationDepth - 1, id2 ); + as.setSummary( idSummary ); mapFlatNewToAllocationSite.put( fn, as ); } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 2b10d553..0b71c573 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -7,26 +7,16 @@ import java.io.*; public class OwnershipGraph { - protected static final int VISIT_HRN_WRITE_FULL = 0; //protected static final int VISIT_HRN_WRITE_CONDENSED = 1; - private int allocationDepth; - //protected static int heapRegionNodeIDs = 0; public Hashtable id2hrn; public Hashtable heapRoots; - //protected static int labelNodeIDs = 0; public Hashtable td2ln; - //public HashSet analysisRegionLabels; - //protected Hashtable linkedRegions; - - - //public Hashtable fn2nc; - public OwnershipGraph( int allocationDepth ) { this.allocationDepth = allocationDepth; @@ -34,12 +24,9 @@ public class OwnershipGraph { id2hrn = new Hashtable(); heapRoots = new Hashtable(); td2ln = new Hashtable(); - - //analysisRegionLabels = new HashSet(); - //linkedRegions = new Hashtable(); - //fn2nc = new Hashtable(); } + protected LabelNode getLabelNodeFromTemp( TempDescriptor td ) { assert td != null; @@ -49,6 +36,7 @@ public class OwnershipGraph { return td2ln.get( td ); } + protected void addReferenceEdge( OwnershipNode referencer, HeapRegionNode referencee, @@ -108,6 +96,10 @@ public class OwnershipGraph { // of the FlatNode assignment and the predicates // of the nodes and edges involved. // + // These procedures are used by several other + // operations defined below (paramter allocation, + // assignment to new allocation) + // //////////////////////////////////////////////////// public void assignTempToTemp( TempDescriptor src, TempDescriptor dst ) { @@ -187,8 +179,6 @@ public class OwnershipGraph { boolean isNewSummary ) { if( id == null ) { - //id = new Integer( heapRegionNodeIDs ); - //++heapRegionNodeIDs; id = OwnershipAnalysis.generateUniqueHeapRegionNodeID(); } @@ -200,6 +190,7 @@ public class OwnershipGraph { return hrn; } + public void parameterAllocation( boolean isTask, TempDescriptor td ) { assert td != null; @@ -211,97 +202,190 @@ public class OwnershipGraph { addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( false ) ); } - /* - public void assignTempToNewAllocation( TempDescriptor td, FlatNew fn ) { + + public void assignTempToNewAllocation( TempDescriptor td, AllocationSite as ) { assert td != null; - assert fn != null; + assert as != null; + + age( as ); + + // after the age operation the newest (or zeroith 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 ); + assert hrnNewest != null; + + LabelNode dst = getLabelNodeFromTemp( td ); + + addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false ) ); + } + + + // use the allocation site (unique to entire analysis) to + // locate the heap region nodes in this ownership graph + // that should be aged. The process models the allocation + // of new objects and collects all the oldest allocations + // in a summary node to allow for a finite analysis + // + // There is an additional property of this method. After + // running it on a particular ownership graph (many graphs + // may have heap regions related to the same allocation site) + // the heap region node objects in this ownership graph will be + // allocated. Therefore, after aging a graph for an allocation + // site, attempts to retrieve the heap region nodes using the + // integer id's contained in the allocation site should always + // return non-null heap regions. + public void age( AllocationSite as ) { + + ////////////////////////////////////////////////////////////////// + // + // move existing references down the line toward + // the oldest element, starting with the oldest + // + // An illustration: + // TempDescriptor = the td passed into this function, left side of new statement + // AllocationSite = { alpha0, alpha1, alpha2, alphaSummary } + // + // 1. Specially merge refs in/out at alpha2 into alphaSummary + // 2. Move refs in/out at alpha1 over to alpha2 (alpha1 becomes alpha2) + // 3. Move refs in/out at alpha0 over to alpha1 + // 4. Assign reference from td to alpha0, which now represents a freshly allocated object + // + ////////////////////////////////////////////////////////////////// + + + // first specially merge the references from the oldest + // node into the summary node, keeping track of 1-to-1 edges + Integer idSummary = as.getSummary(); + HeapRegionNode hrnSummary = id2hrn.get( idSummary ); + + // if this is null then we haven't touched this allocation site + // in the context of the current ownership graph, so simply + // allocate an appropriate heap region node + // this should only happen once per ownership per allocation site, + // and a particular integer id can be used to locate the heap region + // in different ownership graphs that represents the same part of an + // allocation site + if( hrnSummary == null ) { + hrnSummary = createNewHeapRegionNode( idSummary, false, false, true ); + } + + // first transfer the references out of alpha_k to alpha_s + Integer idK = as.getOldest(); + HeapRegionNode hrnK = id2hrn.get( idK ); + + // see comment above about needing to allocate a heap region + // for the context of this ownership graph + if( hrnK == null ) { + hrnK = createNewHeapRegionNode( idK, true, false, false ); + } + + HeapRegionNode hrnReferencee = null; + Iterator itrReferencee = hrnK.setIteratorToReferencedRegions(); + while( itrReferencee.hasNext() ) { + 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 ) ); + } + + // next transfer references to alpha_k over to alpha_s + OwnershipNode onReferencer = null; + Iterator itrReferencer = hrnK.iteratorToReferencers(); + while( itrReferencer.hasNext() ) { + onReferencer = (OwnershipNode) itrReferencer.next(); + + ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnK ); + assert rep != null; + + addReferenceEdge( onReferencer, hrnSummary, rep.copy() ); + } - NewCluster nc = getNewClusterFromFlatNew( fn ); + + // then move down the line of heap region nodes + // clobbering the ith and transferring all references + // to and from i-1 to node i. Note that this clobbers + // the oldest node (alpha_k) that was just merged into + // the summary above and should move everything from + // alpha_0 to alpha_1 before we finish + for( int i = allocationDepth - 1; i > 0; --i ) { - // move existing references down the line toward - // the oldest element - for( int i = newDepthK - 2; i >= 0; --i ) { // move references from the ith oldest to the i+1 oldest - HeapRegionNode hrnIthOld = nc.getIthOldest( i ); - HeapRegionNode hrnIp1Old = nc.getIthOldest( i + 1 ); - - // clear i + 1 references in and out, unless it is the - // oldest node which keeps everything - if( !(i + 1 == newDepthK - 1) ) { - clearReferenceEdgesFrom( hrnIp1Old ); - clearReferenceEdgesTo ( hrnIp1Old ); + Integer idIth = as.getIthOldest( i ); + HeapRegionNode hrnI = id2hrn.get( idIth ); + Integer idImin1th = as.getIthOldest( i - 1 ); + HeapRegionNode hrnImin1 = id2hrn.get( idImin1th ); + + // see comment above about needing to allocate a heap region + // for the context of this ownership graph + if( hrnI == null ) { + hrnI = createNewHeapRegionNode( idIth, true, false, false ); } + if( hrnImin1 == null ) { + hrnImin1 = createNewHeapRegionNode( idImin1th, true, false, false ); + } + + // clear references in and out of node i + clearReferenceEdgesFrom( hrnI ); + clearReferenceEdgesTo ( hrnI ); - // copy each edge in and out of i to i + 1 - HeapRegionNode hrnReferencee = null; - Iterator itrReferencee = hrnIthOld.setIteratorToReferencedRegions(); + // copy each edge in and out of i-1 to i + hrnReferencee = null; + itrReferencee = hrnImin1.setIteratorToReferencedRegions(); while( itrReferencee.hasNext() ) { Map.Entry me = (Map.Entry) itrReferencee.next(); hrnReferencee = (HeapRegionNode) me.getKey(); ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue(); - addReferenceEdge( hrnIp1Old, hrnReferencee, rep.copy() ); + addReferenceEdge( hrnI, hrnReferencee, rep.copy() ); } - OwnershipNode onReferencer = null; - Iterator itrReferencer = hrnIthOld.iteratorToReferencers(); + onReferencer = null; + itrReferencer = hrnImin1.iteratorToReferencers(); while( itrReferencer.hasNext() ) { onReferencer = (OwnershipNode) itrReferencer.next(); - ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnIthOld ); + ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnImin1 ); assert rep != null; - addReferenceEdge( onReferencer, hrnIp1Old, rep.copy() ); + addReferenceEdge( onReferencer, hrnI, rep.copy() ); } } - HeapRegionNode hrnNewest = nc.getIthOldest( 0 ); - ReferenceEdgeProperties rep = new ReferenceEdgeProperties( true ); - LabelNode dst = getLabelNodeFromTemp( td ); - - // clear all references in and out of newest node - clearReferenceEdgesFrom( hrnNewest ); - clearReferenceEdgesTo ( hrnNewest ); - - // finally assign the temp descriptor to the newest - // node in the new cluster - addReferenceEdge( dst, hrnNewest, rep ); - } - + // as stated above, the newest node alpha_0 should have had its + // references moved over to alpha_1, so we can wipe alpha_0 clean + // in preparation for operations that want to reference a freshly + // allocated object from this allocation site + Integer id0th = as.getIthOldest( 0 ); + HeapRegionNode hrn0 = id2hrn.get( id0th ); + // the loop to move references from i-1 to i should + // have touched this node, therefore assert it is non-null + assert hrn0 != null; - - public void addAnalysisRegion( TempDescriptor td ) { - assert td != null; - analysisRegionLabels.add( td ); - } - - // This method gives an existing label node for a temp - // descriptor or creates one if it has not been requested - // yet. The system is simple because temp descriptors and - // label nodes have a one-to-one mapping and no special - // predicates - protected LabelNode getLabelNodeFromTemp( TempDescriptor td ) { - assert td != null; - - if( !td2ln.containsKey( td ) ) { - Integer id = new Integer( labelNodeIDs ); - td2ln.put( td, new LabelNode( td ) ); - ++labelNodeIDs; - } - - return td2ln.get( td ); - } - */ - - - // use the allocation site (unique to entire analysis) to - // locate the heap region nodes in this ownership graph - // that should be aged. The process models the allocation - // of new objects and collects all the oldest allocations - // in a summary node to allow for a finite analysis - public void age( AllocationSite as ) { - + // clear all references in and out of newest node + clearReferenceEdgesFrom( hrn0 ); + clearReferenceEdgesTo ( hrn0 ); } @@ -513,9 +597,9 @@ public class OwnershipGraph { // does not care whether the regions are part of clusters NewCluster ncB = null; if( !fn2nc.containsKey( fnA ) ) { - ncB = new NewCluster( newDepthK ); + ncB = new NewCluster( allocationDepth ); - for( int i = 0; i < newDepthK; ++i ) { + for( int i = 0; i < allocationDepth; ++i ) { HeapRegionNode hrnA = ncA.getIthOldest( i ); // this node shouldn't exist in graph B if the @@ -947,7 +1031,7 @@ public class OwnershipGraph { bw.write( " rankdir=LR;\n" ); bw.write( " label=\"" + fn.toString() + "\";\n" ); - for( int j = 0; j < newDepthK; ++j ) { + for( int j = 0; j < allocationDepth; ++j ) { HeapRegionNode hrn = nc.getIthOldest( j ); bw.write( " " + hrn.toString() + ";\n" ); } diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile b/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile index bf640f77..3250e18e 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile @@ -20,6 +20,9 @@ PNGs: DOTs rm -f *FlatOpNode*.dot rm -f *FlatFieldNode*.dot rm -f *FlatSetFieldNode*.dot + rm -f *FlatCall*.dot + rm -f *Parameter*.dot + rm -f *Penguin*.dot d2p *.dot DOTs: $(PROGRAM).bin diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index fe8258fa..1e03e52c 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -2,6 +2,7 @@ public class Parameter { flag w; int a, b; Parameter f, g; + Penguin penguin; public Parameter() { a = 0; b = 0; f = null; g = null; } @@ -19,11 +20,23 @@ public class Penguin { task Startup( StartupObject s{ initialstate } ) { + /* Parameter p = new Parameter(){!w}; p.foo(); Penguin g = new Penguin(); g.bar(); + */ + + Parameter p; + + for( int i = 0; i < 3; ++i ) { + p = new Parameter(); + p.penguin = new Penguin(); + p.penguin.bar(); + } + + p = null; taskexit( s{ !initialstate } ); } @@ -91,6 +104,8 @@ task possibleAliasConditional taskexit( p1{w}, p2{w} ); } */ + +/* task bunchOfPaths ( Parameter p1{!w}, Parameter p2{!w} ) { @@ -123,6 +138,8 @@ task bunchOfPaths taskexit( p1{w}, p2{w} ); } +*/ + /* task literalTest( Parameter p1{!w} ) { Parameter x = null; -- 2.34.1