From 126d6464a100bed2851492f87accf74a24c020dc Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 16 Apr 2008 17:54:30 +0000 Subject: [PATCH] Properly use transitive closure of allocation sites when resolving a FlatCall node, and related extensions to the node classes. Needs some cleanup though! --- .../OwnershipAnalysis/HeapRegionNode.java | 83 ++--- .../OwnershipAnalysis/OwnershipAnalysis.java | 299 +++++++++++++++++- .../OwnershipAnalysis/OwnershipGraph.java | 184 +++++++++-- .../OwnershipAnalysisTest/test01/makefile | 3 +- .../OwnershipAnalysisTest/test01/test01.java | 30 +- 5 files changed, 494 insertions(+), 105 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java index 15b5c442..55774b53 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java +++ b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java @@ -6,15 +6,32 @@ import java.util.*; public class HeapRegionNode extends OwnershipNode { - public HeapRegionNode( Integer id, - boolean isSingleObject, - boolean isFlagged, - boolean isNewSummary, - String description ) { + protected Integer id; + + protected boolean isSingleObject; + protected boolean isFlagged; + protected boolean isNewSummary; + + protected HashSet memberFields; + protected HashSet referencers; + + protected AllocationSite allocSite; + + protected String description; + + + + public HeapRegionNode( Integer id, + boolean isSingleObject, + boolean isFlagged, + boolean isNewSummary, + AllocationSite allocSite, + String description ) { this.id = id; this.isSingleObject = isSingleObject; this.isFlagged = isFlagged; this.isNewSummary = isNewSummary; + this.allocSite = allocSite; this.description = description; referencers = new HashSet(); @@ -26,15 +43,11 @@ public class HeapRegionNode extends OwnershipNode { isSingleObject, isFlagged, isNewSummary, + allocSite, description ); } - ///////////////// - // equality - ///////////////// - protected Integer id; - public Integer getID() { return id; } @@ -48,40 +61,22 @@ public class HeapRegionNode extends OwnershipNode { isNewSummary == hrn.isNewSummary() && description.equals( hrn.getDescription() ); } - ///////////////// - // end equality - ///////////////// - - ///////////////// - // predicates - ///////////////// - boolean isSingleObject; + public boolean isSingleObject() { return isSingleObject; } - boolean isFlagged; public boolean isFlagged() { return isFlagged; } - boolean isNewSummary; public boolean isNewSummary() { return isNewSummary; } - /////////////////// - // end predicates - /////////////////// - - /////////////////////////////////////////// - // interface with larger graph - /////////////////////////////////////////// - protected HashSet memberFields; - protected HashSet referencers; public Iterator iteratorToReferencers() { return referencers.iterator(); @@ -109,37 +104,11 @@ public class HeapRegionNode extends OwnershipNode { assert on != null; return referencers.contains( on ); } - /////////////////////////////////////////////// - // end interface with larger graph - /////////////////////////////////////////////// - - - /////////////////////////////////////////////// - // analysis interface - /////////////////////////////////////////////// - /* - protected HashSet analysisRegionAliases; - - public void addAnalysisRegionAlias( TempDescriptor td ) { - assert td != null; - assert !analysisRegionAliases.contains( td ); - - analysisRegionAliases.add( td ); - } - - public Iterator iteratorToAnalysisRegionAliases() { - return analysisRegionAliases.iterator(); + public AllocationSite getAllocationSite() { + return allocSite; } - */ - /////////////////////////////////////////////// - // end analysis interface - /////////////////////////////////////////////// - - - // for writing out - String description; public String getIDString() { return id.toString(); diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index ec3449c6..991bd02b 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -9,12 +9,155 @@ import java.io.*; public class OwnershipAnalysis { - // from the compiler + /////////////////////////////////////////// + // + // Public interface to discover possible + // aliases in the program under analysis + // + /////////////////////////////////////////// + public HashSet + getFlaggedAllocationSitesReachableFromTask( TaskDescriptor td ) { + + return getFlaggedAllocationSitesReachableFromTaskPRIVATE( td ); + } + + public AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) { + return getAllocationSiteFromFlatNewPRIVATE( fn ); + } + + public boolean createsPotentialAliases( Descriptor taskOrMethod, + int paramIndex1, + int paramIndex2 ) { + + OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); + assert( og != null ); + + return createsPotentialAliases( og, + getHeapRegionIDset( og, paramIndex1 ), + getHeapRegionIDset( og, paramIndex2 ) ); + } + + public boolean createsPotentialAliases( Descriptor taskOrMethod, + int paramIndex, + AllocationSite alloc ) { + + OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); + assert( og != null ); + + return createsPotentialAliases( og, + getHeapRegionIDset( og, paramIndex ), + getHeapRegionIDset( alloc ) ); + } + + public boolean createsPotentialAliases( Descriptor taskOrMethod, + AllocationSite alloc, + int paramIndex ) { + + OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); + assert( og != null ); + + return createsPotentialAliases( og, + getHeapRegionIDset( og, paramIndex ), + getHeapRegionIDset( alloc ) ); + } + + public boolean createsPotentialAliases( Descriptor taskOrMethod, + AllocationSite alloc1, + AllocationSite alloc2 ) { + + OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); + assert( og != null ); + + return createsPotentialAliases( og, + getHeapRegionIDset( alloc1 ), + getHeapRegionIDset( alloc2 ) ); + } + + public boolean createsPotentialAliases( Descriptor taskOrMethod, + AllocationSite alloc, + HashSet allocSet ) { + + OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); + assert( og != null ); + + return createsPotentialAliases( og, + getHeapRegionIDset( alloc ), + getHeapRegionIDset( allocSet ) ); + } + + // use the methods given above to check every possible alias + // between task parameters and flagged allocation sites reachable + // from the task + public void writeAllAliases( String outputFile ) throws java.io.IOException { + + BufferedWriter bw = new BufferedWriter( new FileWriter( outputFile ) ); + + // look through every task for potential aliases + Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); + while( taskItr.hasNext() ) { + TaskDescriptor td = (TaskDescriptor) taskItr.next(); + + HashSet allocSites = getFlaggedAllocationSitesReachableFromTask( td ); + + // for each task parameter, check for aliases with + // other task parameters and every allocation site + // reachable from this task + FlatMethod fm = state.getMethodFlat( td ); + for( int i = 0; i < fm.numParameters(); ++i ) { + + // for the ith parameter check for aliases to all + // higher numbered parameters + for( int j = i + 1; j < fm.numParameters(); ++j ) { + if( createsPotentialAliases( td, i, j ) ) { + bw.write( "Task "+td+" potentially aliases parameters "+i+" and "+j+".\n" ); + } + } + + // for the ith parameter, check for aliases against + // the set of allocation sites reachable from this + // task context + Iterator allocItr = allocSites.iterator(); + while( allocItr.hasNext() ) { + AllocationSite as = (AllocationSite) allocItr.next(); + if( createsPotentialAliases( td, i, as ) ) { + bw.write( "Task "+td+" potentially aliases parameter "+i+" and "+as+".\n" ); + } + } + } + + // for each allocation site check for aliases with + // other allocation sites in the context of execution + // of this task + Iterator allocItr = allocSites.iterator(); + while( allocItr.hasNext() ) { + AllocationSite as = (AllocationSite) allocItr.next(); + if( createsPotentialAliases( td, as, allocSites ) ) { + bw.write( "Task "+td+" potentially aliases "+as+" and the rest of the set.\n" ); + } + } + } + + bw.close(); + } + + /////////////////////////////////////////// + // + // end public interface + // + /////////////////////////////////////////// + + + + + + + + + // data from the compiler private State state; private CallGraph callGraph; private int allocationDepth; - // used to identify HeapRegionNode objects // A unique ID equates an object in one // ownership graph with an object in another @@ -289,7 +432,7 @@ public class OwnershipAnalysis { case FKind.FlatNew: FlatNew fnn = (FlatNew) fn; dst = fnn.getDst(); - AllocationSite as = getAllocationSiteFromFlatNew( fnn ); + AllocationSite as = getAllocationSiteFromFlatNewPRIVATE( fnn ); og.assignTempToNewAllocation( dst, as ); break; @@ -298,7 +441,7 @@ public class OwnershipAnalysis { FlatCall fc = (FlatCall) fn; MethodDescriptor md = fc.getMethod(); FlatMethod flatm = state.getMethodFlat( md ); - HashSet allocSiteSet = getAllocationSiteSet( md ); + //HashSet allocSiteSet = getAllocationSiteSet( md ); OwnershipGraph ogAllPossibleCallees = new OwnershipGraph( allocationDepth ); if( md.isStatic() ) { @@ -306,6 +449,13 @@ public class OwnershipAnalysis { OwnershipGraph onlyPossibleCallee = mapDescriptorToCompleteOwnershipGraph.get( md ); ogAllPossibleCallees.merge( onlyPossibleCallee ); + /* + if( onlyPossibleCallee != null ) { + onlyPossibleCallee.writeGraph( "only", false, false ); + System.out.println( "There was only one possible callee, "+md ); + } + */ + } else { // if the method descriptor is virtual, then there could be a // set of possible methods that will actually be invoked, so @@ -313,15 +463,29 @@ public class OwnershipAnalysis { TypeDescriptor typeDesc = fc.getThis().getType(); Set possibleCallees = callGraph.getMethods( md, typeDesc ); + //int j = 0; + Iterator i = possibleCallees.iterator(); while( i.hasNext() ) { MethodDescriptor possibleMd = (MethodDescriptor) i.next(); - allocSiteSet.addAll( getAllocationSiteSet( possibleMd ) ); + //allocSiteSet.addAll( getAllocationSiteSet( possibleMd ) ); OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get( possibleMd ); + + /* + if( ogPotentialCallee != null ) { + ogPotentialCallee.writeGraph( "potential"+j, false, false ); + ++j; + } + */ + ogAllPossibleCallees.merge( ogPotentialCallee ); } + + //System.out.println( "There were "+j+" potential callees merged together." ); } + //System.out.println( "AllocationSiteSet has "+allocSiteSet.size()+" items." ); + // now we should have the following information to resolve this method call: // // 1. A FlatCall fc to query for the caller's context (argument labels, etc) @@ -339,7 +503,7 @@ public class OwnershipAnalysis { // 5. The Set of AllocationSite objects, allocSiteSet that is the set of allocation sites from // every possible method we might have chosen // - og.resolveMethodCall( fc, md.isStatic(), flatm, ogAllPossibleCallees, allocSiteSet ); + og.resolveMethodCall( fc, md.isStatic(), flatm, ogAllPossibleCallees ); //og.writeGraph( methodDesc, fn ); break; @@ -372,8 +536,12 @@ public class OwnershipAnalysis { } + + + + // return just the allocation site associated with one FlatNew node - private AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) { + private AllocationSite getAllocationSiteFromFlatNewPRIVATE( FlatNew fn ) { if( !mapFlatNewToAllocationSite.containsKey( fn ) ) { AllocationSite as = new AllocationSite( allocationDepth, fn.getType() ); @@ -427,7 +595,7 @@ public class OwnershipAnalysis { FlatNode n = toVisit.iterator().next(); if( n instanceof FlatNew ) { - s.add( getAllocationSiteFromFlatNew( (FlatNew) n ) ); + s.add( getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n ) ); } toVisit.remove( n ); @@ -443,4 +611,119 @@ public class OwnershipAnalysis { mapDescriptorToAllocationSiteSet.put( d, s ); } + + + private HashSet + getFlaggedAllocationSitesReachableFromTaskPRIVATE( TaskDescriptor td ) { + + HashSet asSetTotal = new HashSet(); + HashSet toVisit = new HashSet(); + HashSet visited = new HashSet(); + + toVisit.add( td ); + + // traverse this task and all methods reachable from this task + while( !toVisit.isEmpty() ) { + Descriptor d = toVisit.iterator().next(); + toVisit.remove( d ); + visited.add( d ); + + HashSet asSet = getAllocationSiteSet( d ); + Iterator asItr = asSet.iterator(); + while( asItr.hasNext() ) { + AllocationSite as = (AllocationSite) asItr.next(); + if( as.getType().getClassDesc().hasFlags() ) { + asSetTotal.add( as ); + } + } + + // enqueue callees of this method to be searched for + // allocation sites also + Set callees = callGraph.getCalleeSet( d ); + if( callees != null ) { + Iterator methItr = callees.iterator(); + while( methItr.hasNext() ) { + MethodDescriptor md = (MethodDescriptor) methItr.next(); + + if( !visited.contains( md ) ) { + toVisit.add( md ); + } + } + } + } + + + return asSetTotal; + } + + + + private HashSet getHeapRegionIDset( OwnershipGraph og, + int paramIndex ) { + + assert og.paramIndex2id.containsKey( paramIndex ); + Integer idParam = og.paramIndex2id.get( paramIndex ); + + HashSet idSet = new HashSet(); + idSet.add( idParam ); + + return idSet; + } + + private HashSet getHeapRegionIDset( AllocationSite alloc ) { + + HashSet idSet = new HashSet(); + + for( int i = 0; i < alloc.getAllocationDepth(); ++i ) { + Integer id = alloc.getIthOldest( i ); + idSet.add( id ); + } + + Integer idSummary = alloc.getSummary(); + idSet.add( idSummary ); + + return idSet; + } + + private HashSet getHeapRegionIDset( HashSet allocSet ) { + + HashSet idSet = new HashSet(); + + Iterator allocItr = allocSet.iterator(); + while( allocItr.hasNext() ) { + AllocationSite alloc = (AllocationSite) allocItr.next(); + + for( int i = 0; i < alloc.getAllocationDepth(); ++i ) { + Integer id = alloc.getIthOldest( i ); + idSet.add( id ); + } + + Integer idSummary = alloc.getSummary(); + idSet.add( idSummary ); + } + + return idSet; + } + + private boolean createsPotentialAliases( OwnershipGraph og, + HashSet idSetA, + HashSet idSetB ) { + boolean potentialAlias = false; + + // first expand set B into the set of all heap region node ID's + // reachable from the nodes in set B + HashSet idSetReachableFromB = og.getReachableSet( idSetB ); + + // then see if anything in A can reach a node in the set reachable + // from B. If so, there is a potential alias. + Iterator i = idSetA.iterator(); + while( i.hasNext() ) { + Integer id = (Integer) i.next(); + if( og.canIdReachSet( id, idSetB ) ) { + return true; + } + } + + return false; + } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 3ba6cf07..e5061e12 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -20,6 +20,9 @@ public class OwnershipGraph { public Hashtable id2hrn; public Hashtable td2ln; public Hashtable id2paramIndex; + public Hashtable paramIndex2id; + + public HashSet allocationSites; public OwnershipGraph( int allocationDepth ) { @@ -28,6 +31,9 @@ public class OwnershipGraph { id2hrn = new Hashtable(); td2ln = new Hashtable(); id2paramIndex = new Hashtable(); + paramIndex2id = new Hashtable(); + + allocationSites = new HashSet (); } @@ -55,11 +61,12 @@ public class OwnershipGraph { // in the merge() operation) or to create new heap // regions with a new unique ID. protected HeapRegionNode - createNewHeapRegionNode( Integer id, - boolean isSingleObject, - boolean isFlagged, - boolean isNewSummary, - String description ) { + createNewHeapRegionNode( Integer id, + boolean isSingleObject, + boolean isFlagged, + boolean isNewSummary, + AllocationSite allocSite, + String description ) { if( id == null ) { id = OwnershipAnalysis.generateUniqueHeapRegionNodeID(); @@ -69,6 +76,7 @@ public class OwnershipGraph { isSingleObject, isFlagged, isNewSummary, + allocSite, description ); id2hrn.put( id, hrn ); return hrn; @@ -228,6 +236,7 @@ public class OwnershipGraph { false, isTask, false, + null, "param" + paramIndex ); // keep track of heap regions that were created for @@ -237,6 +246,7 @@ public class OwnershipGraph { assert !id2paramIndex.containsKey ( newID ); assert !id2paramIndex.containsValue( paramIndex ); id2paramIndex.put( newID, paramIndex ); + paramIndex2id.put( paramIndex, newID ); // heap regions for parameters are always multiple object (see above) // and have a reference to themselves, because we can't know the @@ -285,6 +295,12 @@ public class OwnershipGraph { // return non-null heap regions. public void age( AllocationSite as ) { + // aging adds this allocation site to the graph's + // list of sites that exist in the graph, or does + // nothing if the site is already in the list + allocationSites.add( as ); + + ////////////////////////////////////////////////////////////////// // // move existing references down the line toward @@ -315,10 +331,17 @@ public class OwnershipGraph { // in different ownership graphs that represents the same part of an // allocation site if( hrnSummary == null ) { + + boolean hasFlags = false; + if( as.getType().isClass() ) { + hasFlags = as.getType().getClassDesc().hasFlags(); + } + hrnSummary = createNewHeapRegionNode( idSummary, false, - as.getType().getClassDesc().hasFlags(), + hasFlags, true, + as, as + "\\n" + as.getType() + "\\nsummary" ); for( int i = 0; i < as.getAllocationDepth(); ++i ) { @@ -326,8 +349,9 @@ public class OwnershipGraph { assert !id2hrn.containsKey( idIth ); createNewHeapRegionNode( idIth, true, - as.getType().getClassDesc().hasFlags(), + hasFlags, false, + as, as + "\\n" + as.getType() + "\\n" + i + " oldest" ); } } @@ -449,14 +473,15 @@ public class OwnershipGraph { public void resolveMethodCall( FlatCall fc, boolean isStatic, FlatMethod fm, - OwnershipGraph ogCallee, - HashSet allocSiteSet ) { + OwnershipGraph ogCallee ) { //, + //HashSet allocSiteSet ) { // first age all of the allocation sites from // the callee graph in this graph - Iterator i = allocSiteSet.iterator(); + Iterator i = ogCallee.allocationSites.iterator(); while( i.hasNext() ) { - this.age( (AllocationSite) i.next() ); + AllocationSite allocSite = (AllocationSite) i.next(); + this.age( allocSite ); } // in non-static methods there is a "this" pointer @@ -509,6 +534,17 @@ public class OwnershipGraph { // So now make a set of possible source heaps in the caller graph // and a set of destination heaps in the caller graph, and make // a reference edge in the caller for every possible (src,dst) pair + if( !ogCallee.id2hrn.contains( idChildCallee ) ) { + //System.out.println( "Houston, we got a problem." ); + //System.out.println( "idCallee is "+idCallee ); + //System.out.println( "idChildCallee is "+idChildCallee ); + + try { + writeGraph( "caller", false, false ); + ogCallee.writeGraph( "callee", false, false ); + } catch( IOException e ) {} + } + HashSet possibleCallerSrcs = getHRNSetThatPossiblyMapToCalleeHRN( ogCallee, idCallee, @@ -604,9 +640,10 @@ public class OwnershipGraph { return; } - mergeOwnershipNodes( og ); - mergeReferenceEdges( og ); - mergeId2paramIndex( og ); + mergeOwnershipNodes ( og ); + mergeReferenceEdges ( og ); + mergeId2paramIndex ( og ); + mergeAllocationSites( og ); } protected void mergeOwnershipNodes( OwnershipGraph og ) { @@ -758,6 +795,7 @@ public class OwnershipGraph { protected void mergeId2paramIndex( OwnershipGraph og ) { if( id2paramIndex.size() == 0 ) { id2paramIndex = og.id2paramIndex; + paramIndex2id = og.paramIndex2id; return; } @@ -768,6 +806,10 @@ public class OwnershipGraph { assert id2paramIndex.size() == og.id2paramIndex.size(); } + protected void mergeAllocationSites( OwnershipGraph og ) { + allocationSites.addAll( og.allocationSites ); + } + // it is necessary in the equals() member functions // to "check both ways" when comparing the data @@ -805,6 +847,11 @@ public class OwnershipGraph { return false; } + // if everything is equal up to this point, + // assert that allocationSites is also equal-- + // this data is redundant and kept for efficiency + assert allocationSites.equals( og.allocationSites ); + return true; } @@ -1060,15 +1107,100 @@ public class OwnershipGraph { - - // use this method to determine if two temp descriptors can possibly - // access the same heap regions, which means there is a possible alias - public boolean havePossibleAlias( TempDescriptor td1, - TempDescriptor td2 ) { - LabelNode ln1 = getLabelNodeFromTemp( td1 ); - LabelNode ln2 = getLabelNodeFromTemp( td2 ); - + // given a set B of heap region node ID's, return the set of heap + // region node ID's that is reachable from B + public HashSet getReachableSet( HashSet idSetB ) { + + HashSet toVisit = new HashSet(); + HashSet visited = new HashSet(); + + // initial nodes to visit are from set B + Iterator initialItr = idSetB.iterator(); + while( initialItr.hasNext() ) { + Integer idInitial = (Integer) initialItr.next(); + assert id2hrn.contains( idInitial ); + HeapRegionNode hrnInitial = id2hrn.get( idInitial ); + toVisit.add( hrnInitial ); + } + + HashSet idSetReachableFromB = new HashSet(); + + // do a heap traversal + while( !toVisit.isEmpty() ) { + HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next(); + toVisit.remove( hrnVisited ); + visited.add ( hrnVisited ); + + // for every node visited, add it to the total + // reachable set + idSetReachableFromB.add( hrnVisited.getID() ); + + // find other reachable nodes + Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions(); + while( referenceeItr.hasNext() ) { + Map.Entry me = (Map.Entry) referenceeItr.next(); + HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey(); + ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue(); + + if( !visited.contains( hrnReferencee ) ) { + toVisit.add( hrnReferencee ); + } + } + } + + return idSetReachableFromB; + } + + + // used to find if a heap region can possibly have a reference to + // any of the heap regions in the given set + // if the id supplied is in the set, then a self-referencing edge + // would return true, but that special case is specifically allowed + // meaning that it isn't an external alias + public boolean canIdReachSet( Integer id, HashSet idSet ) { + + assert id2hrn.contains( id ); + HeapRegionNode hrn = id2hrn.get( id ); + + /* + HashSet hrnSet = new HashSet(); + + Iterator i = idSet.iterator(); + while( i.hasNext() ) { + Integer idFromSet = (Integer) i.next(); + assert id2hrn.contains( idFromSet ); + hrnSet.add( id2hrn.get( idFromSet ) ); + } + */ + + // do a traversal from hrn and see if any of the + // heap regions from the set come up during that + HashSet toVisit = new HashSet(); + HashSet visited = new HashSet(); + toVisit.add( hrn ); + while( !toVisit.isEmpty() ) { + HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next(); + toVisit.remove( hrnVisited ); + visited.add ( hrnVisited ); + + Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions(); + while( referenceeItr.hasNext() ) { + Map.Entry me = (Map.Entry) referenceeItr.next(); + HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey(); + ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue(); + + if( idSet.contains( hrnReferencee.getID() ) ) { + if( !id.equals( hrnReferencee.getID() ) ) { + return true; + } + } + + if( !visited.contains( hrnReferencee ) ) { + toVisit.add( hrnReferencee ); + } + } + } return false; } @@ -1103,10 +1235,10 @@ public class OwnershipGraph { ); } - private void writeGraph( String graphName, - boolean writeLabels, - boolean writeReferencers - ) throws java.io.IOException { + public void writeGraph( String graphName, + boolean writeLabels, + boolean writeReferencers + ) throws java.io.IOException { // remove all non-word characters from the graph name so // the filename and identifier in dot don't cause errors diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile b/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile index 9168b1cd..650e7e72 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile @@ -3,7 +3,7 @@ PROGRAM=test01 SOURCE_FILES=test01.java BUILDSCRIPT=~/research/Robust/src/buildscript -BSFLAGS= -recover -flatirtasks -ownership #-enable-assertions +BSFLAGS= -recover -flatirtasks -ownership -enable-assertions #BSFLAGS= -recover -ownership -enable-assertions all: $(PROGRAM).bin @@ -54,3 +54,4 @@ clean: rm -f *.png rm -f *.ps rm -f *.eps + rm -f identifiedAliases.txt diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index 161abb19..9349ccca 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -26,7 +26,7 @@ public class Voo { } public class Baw { - flag g; int y; + int y; Foo f; public Baw() {} @@ -50,14 +50,6 @@ public class Foo { // look for the parameter s as a label referencing // a heap region that is multi-object, flagged, not summary task Startup( StartupObject s{ initialstate } ) { - - /* - Foo a = new Foo(); - Foo b = new Foo(); - Foo c = new Foo(); - - c.ruinSomeFoos( a, b ); - */ while( false ) { Foo a = new Foo(); @@ -68,7 +60,7 @@ task Startup( StartupObject s{ initialstate } ) { taskexit( s{ !initialstate } ); } -/* + // this task allocates a new object, so there should // be a heap region for the parameter, and several @@ -99,16 +91,29 @@ task Branch( Voo v{ f } ) { task NoAliasNewInLoop( Voo v{ f } ) { - Voo w = new Voo(); for( int i = 0; i < 10; ++i ) { - w.b = new Baw(); + Voo w = new Voo(); + w.b = new Baw(); w.b.f = new Foo(); } taskexit( v{ !f } ); } +task NoAliasNewInLoopAnotherWay( Voo v{ f } ) { + + for( int i = 0; i < 10; ++i ) { + Voo w = new Voo(); + Baw b = new Baw(); + Foo f = new Foo(); + + w.b = b; + b.f = f; + } + + taskexit( v{ !f } ); +} task ClobberInitParamReflex( Voo v{ f }, Voo w{ f } ) { v.b = v.bb; @@ -116,4 +121,3 @@ task ClobberInitParamReflex( Voo v{ f }, Voo w{ f } ) { taskexit( v{ !f }, w{ !f } ); } -*/ -- 2.34.1