public Hashtable<Integer, HeapRegionNode> id2hrn;
public Hashtable<TempDescriptor, LabelNode > td2ln;
public Hashtable<Integer, Integer > id2paramIndex;
+ public Hashtable<Integer, Integer > paramIndex2id;
+
+ public HashSet<AllocationSite> allocationSites;
public OwnershipGraph( int allocationDepth ) {
id2hrn = new Hashtable<Integer, HeapRegionNode>();
td2ln = new Hashtable<TempDescriptor, LabelNode >();
id2paramIndex = new Hashtable<Integer, Integer >();
+ paramIndex2id = new Hashtable<Integer, Integer >();
+
+ allocationSites = new HashSet <AllocationSite>();
}
// 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,
+ boolean isParameter,
+ AllocationSite allocSite,
+ ReachabilitySet alpha,
+ String description ) {
if( id == null ) {
id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
}
+ if( alpha == null ) {
+ if( isFlagged || isParameter ) {
+ alpha = new ReachabilitySet( new TokenTuple( id,
+ isNewSummary,
+ TokenTuple.ARITY_ONE ) );
+ } else {
+ alpha = new ReachabilitySet();
+ }
+ }
+
HeapRegionNode hrn = new HeapRegionNode( id,
isSingleObject,
isFlagged,
isNewSummary,
+ allocSite,
+ alpha,
description );
id2hrn.put( id, hrn );
return hrn;
HeapRegionNode referencee,
ReferenceEdgeProperties rep ) {
assert referencer != null;
- assert referencee != null;
+ assert referencee != null;
+ assert rep != null;
referencer.addReferencedRegion( referencee, rep );
referencee.addReferencer( referencer );
+ rep.setSrc( referencer );
+ rep.setDst( referencee );
}
protected void removeReferenceEdge( OwnershipNode referencer,
}
}
+ protected void propagateTokens( HeapRegionNode nPrime,
+ ChangeTupleSet c0,
+ HashSet<HeapRegionNode> nodesWithNewAlpha,
+ HashSet<ReferenceEdgeProperties> edgesWithNewBeta ) {
+
+ HashSet<HeapRegionNode> todoNodes
+ = new HashSet<HeapRegionNode>();
+ todoNodes.add( nPrime );
+
+ HashSet<ReferenceEdgeProperties> todoEdges
+ = new HashSet<ReferenceEdgeProperties>();
+
+ Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
+ = new Hashtable<HeapRegionNode, ChangeTupleSet>();
+ nodePlannedChanges.put( nPrime, c0 );
+
+ Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges
+ = new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
+
+ Hashtable<HeapRegionNode, ChangeTupleSet> nodeChangesMade
+ = new Hashtable<HeapRegionNode, ChangeTupleSet>();
+
+ while( !todoNodes.isEmpty() ) {
+ HeapRegionNode n = todoNodes.iterator().next();
+ todoNodes.remove( n );
+
+ ChangeTupleSet C = nodePlannedChanges.get( n );
+
+ if( !nodeChangesMade.containsKey( n ) ) {
+ nodeChangesMade.put( n, new ChangeTupleSet().makeCanonical() );
+ }
+
+ Iterator itrC = C.iterator();
+ while( itrC.hasNext() ) {
+ ChangeTuple c = (ChangeTuple) itrC.next();
+
+ if( n.getAlpha().contains( c.getSetToMatch() ) ) {
+ ReachabilitySet withChange = n.getAlpha().union( c.getSetToAdd() );
+ n.setAlphaNew( n.getAlphaNew().union( withChange ) );
+ nodesWithNewAlpha.add( n );
+ 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().makeCanonical();
+
+ 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 ) );
+ }
+ }
+ }
+ }
+
+
+ while( !todoEdges.isEmpty() ) {
+ ReferenceEdgeProperties e = todoEdges.iterator().next();
+ todoEdges.remove( e );
+
+ if( !edgePlannedChanges.containsKey( e ) ) {
+ edgePlannedChanges.put( e, new ChangeTupleSet().makeCanonical() );
+ }
+
+ ChangeTupleSet C = edgePlannedChanges.get( e );
+
+ ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
+
+ Iterator itrC = C.iterator();
+ while( itrC.hasNext() ) {
+ ChangeTuple c = (ChangeTuple) itrC.next();
+ if( e.getBeta().contains( c.getSetToMatch() ) ) {
+ ReachabilitySet withChange = e.getBeta().union( c.getSetToAdd() );
+ e.setBetaNew( e.getBetaNew().union( withChange ) );
+ edgesWithNewBeta.add( e );
+ changesToPass = changesToPass.union( c );
+ }
+ }
+
+ OwnershipNode onSrc = e.getSrc();
+
+ if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
+ HeapRegionNode n = (HeapRegionNode) onSrc;
+ Iterator referItr = n.iteratorToReferencers();
+
+ while( referItr.hasNext() ) {
+ OwnershipNode onRef = (OwnershipNode) referItr.next();
+ ReferenceEdgeProperties f = onRef.getReferenceTo( n );
+
+ if( !edgePlannedChanges.containsKey( f ) ) {
+ edgePlannedChanges.put( f, new ChangeTupleSet().makeCanonical() );
+ }
+
+ ChangeTupleSet currentChanges = edgePlannedChanges.get( f );
+
+ if( !changesToPass.isSubset( currentChanges ) ) {
+ todoEdges.add( f );
+ edgePlannedChanges.put( f, currentChanges.union( changesToPass ) );
+ }
+ }
+ }
+ }
+ }
+
////////////////////////////////////////////////////
//
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();
+ Map.Entry me = (Map.Entry) srcRegionsItr.next();
newReferencee = (HeapRegionNode) me.getKey();
ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
}
}
- 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();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
+ Map.Entry meH = (Map.Entry) hrnRegionsItr.next();
+ hrnOneHop = (HeapRegionNode) meH.getKey();
+ ReferenceEdgeProperties rep2 = (ReferenceEdgeProperties) meH.getValue();
+ ReachabilitySet beta2 = rep2.getBeta();
- addReferenceEdge( dstln, hrnOneHop, rep.copy() );
+ ReferenceEdgeProperties rep = rep2.copy();
+ rep.setIsInitialParamReflexive( false );
+ rep.setBeta( beta1.intersection( beta2 ) );
+
+ addReferenceEdge( dstln, hrnOneHop, rep );
}
}
}
- public void assignFieldToTemp( TempDescriptor src,
- TempDescriptor dst,
+ 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<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
+ HashSet<ReferenceEdgeProperties> edgesWithNewBeta = new HashSet<ReferenceEdgeProperties>();
+
+ 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();
+
+ ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() );
- HeapRegionNode hrnSrc = null;
+ HeapRegionNode hrnSrc = null;
+ ReferenceEdgeProperties repSrc = null;
Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
while( srcRegionsItr.hasNext() ) {
- Map.Entry meS = (Map.Entry) srcRegionsItr.next();
- hrnSrc = (HeapRegionNode) meS.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meS.getValue();
+ Map.Entry meS = (Map.Entry) srcRegionsItr.next();
+ hrnSrc = (HeapRegionNode) meS.getKey();
+ repSrc = (ReferenceEdgeProperties) meS.getValue();
+
+ ReachabilitySet O = srcln.getReferenceTo( hrnSrc ).getBeta();
+
+ ChangeTupleSet Cy = O.unionUpArityToChangeSet( R );
+ ChangeTupleSet Cx = R.unionUpArityToChangeSet( O );
+
+ propagateTokens( hrnSrc, Cy, nodesWithNewAlpha, edgesWithNewBeta );
+ propagateTokens( hrn, Cx, nodesWithNewAlpha, edgesWithNewBeta );
- addReferenceEdge( hrn, hrnSrc, rep.copy() );
+ // note that this picks up the beta after the propogation has
+ // been applied
+ ReferenceEdgeProperties repNew
+ = new ReferenceEdgeProperties( false, false, repSrc.getBetaNew() );
+
+ addReferenceEdge( hrn, hrnSrc, repNew );
}
}
+
+ 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,
false,
isTask,
false,
- "param" );
+ true,
+ null,
+ null,
+ "param" + paramIndex );
// keep track of heap regions that were created for
// parameter labels, the index of the parameter they
assert !id2paramIndex.containsKey ( newID );
assert !id2paramIndex.containsValue( paramIndex );
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,
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 );
-
- addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false ) );
+
+ clearReferenceEdgesFrom( dst );
+
+ addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false, false, hrnNewest.getAlpha() ) );
}
// 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
// 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,
- false,
+ hasFlags,
true,
- as + "\\nsummary" );
+ false,
+ as,
+ null,
+ as + "\\n" + as.getType() + "\\nsummary" );
+
+ for( int i = 0; i < as.getAllocationDepth(); ++i ) {
+ Integer idIth = as.getIthOldest( i );
+ assert !id2hrn.containsKey( idIth );
+ createNewHeapRegionNode( idIth,
+ true,
+ hasFlags,
+ false,
+ false,
+ as,
+ null,
+ as + "\\n" + as.getType() + "\\n" + i + " oldest" );
+ }
}
// 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,
- as + "\\noldest" );
- }
HeapRegionNode hrnReferencee = null;
Iterator itrReferencee = hrnK.setIteratorToReferencedRegions();
onReferencer = (OwnershipNode) itrReferencer.next();
ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnK );
- assert rep != null;
-
- addReferenceEdge( onReferencer, hrnSummary, rep.copy() );
+ assert rep != null;
+ ReferenceEdgeProperties repSummary = onReferencer.getReferenceTo( hrnSummary );
+ ReferenceEdgeProperties repMerged = rep.copy();
+
+ if( repSummary == null ) {
+ // the merge is trivial, nothing to be done
+ } else {
+ // otherwise an edge from the referencer to alpha_S exists already
+ // and the edge referencer->alpha_K should be merged with it
+ repMerged.setBeta( repMerged.getBeta().union( repSummary.getBeta() ) );
+ }
+
+ addReferenceEdge( onReferencer, hrnSummary, repMerged );
}
// alpha_0 to alpha_1 before we finish
for( int i = allocationDepth - 1; i > 0; --i ) {
- // move references from the ith oldest to the i+1 oldest
+ // move references from the i-1 oldest to the ith oldest
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,
- as + "\\n" + Integer.toString( i ) + "th" );
- }
- if( hrnImin1 == null ) {
- hrnImin1 = createNewHeapRegionNode( idImin1th,
- true,
- false,
- false,
- as + "\\n" + Integer.toString( i-1 ) + "th" );
- }
-
// clear references in and out of node i
clearReferenceEdgesFrom( hrnI );
clearReferenceEdgesTo ( hrnI );
// clear all references in and out of newest node
clearReferenceEdgesFrom( hrn0 );
- clearReferenceEdgesTo ( hrn0 );
+ clearReferenceEdgesTo ( hrn0 );
}
-
// some notes:
// the heap regions that are specially allocated as multiple-object
public void resolveMethodCall( FlatCall fc,
boolean isStatic,
FlatMethod fm,
- OwnershipGraph ogCallee,
-
HashSet<AllocationSite> allocSiteSet ) {
+ OwnershipGraph ogCallee ) { //,
+
//HashSet<AllocationSite> 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
// 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<HeapRegionNode> possibleCallerSrcs =
getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
idCallee,
while( dstItr.hasNext() ) {
HeapRegionNode dst = (HeapRegionNode) dstItr.next();
- ReferenceEdgeProperties rep = new ReferenceEdgeProperties();
- addReferenceEdge( src, dst, rep );
+ addReferenceEdge( src, dst, repC.copy() );
}
}
}
} else {
// this heap region is not a parameter, so it should
- // have a matching heap region in the caller graph
-
- /*
- try {
- ogCallee.writeGraph( "TheCallee" );
- writeGraph( "TheCaller" );
- } catch( Exception e ) {}
- */
-
+ // have a matching heap region in the caller graph
assert id2hrn.containsKey( idCallee );
possibleCallerHRNs.add( id2hrn.get( idCallee ) );
}
// in merge() and equals() methods the suffix A
// represents the passed in graph and the suffix
// B refers to the graph in this object
+ // Merging means to take the incoming graph A and
+ // merge it into B, so after the operation graph B
+ // is the final result.
////////////////////////////////////////////////////
-
public void merge( OwnershipGraph og ) {
if( og == null ) {
return;
}
- mergeOwnershipNodes( og );
- mergeReferenceEdges( og );
- mergeId2paramIndex( og );
+ mergeOwnershipNodes ( og );
+ mergeReferenceEdges ( og );
+ mergeId2paramIndex ( og );
+ mergeAllocationSites( og );
}
+
protected void mergeOwnershipNodes( OwnershipGraph og ) {
Set sA = og.id2hrn.entrySet();
Iterator iA = sA.iterator();
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
+ // nodes' reachability sets
+ HeapRegionNode hrnB = id2hrn.get( idA );
+ hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
}
}
// for stroing heap region nodes retrieved by integer
// ids. Because finding edges requires interacting
// with these disparate data structures frequently the
- // process is nearly duplicated, one for each
+ // process is nearly duplicated, one for each structure
+ // that stores edges
// heap regions
Set sA = og.id2hrn.entrySet();
assert id2hrn.containsKey( idA );
HeapRegionNode hrnB = id2hrn.get( idA );
- HeapRegionNode hrnChildB = null;
+ HeapRegionNode hrnChildB = null;
+ ReferenceEdgeProperties repB = null;
Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
while( heapRegionsItrB.hasNext() ) {
- Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) meC.getKey();
+ Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
+ hrnChildB = (HeapRegionNode) meC.getKey();
+ ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
if( hrnChildB.equals( idChildA ) ) {
edgeFound = true;
+ repB = rep;
}
}
if( !edgeFound ) {
assert id2hrn.containsKey( idChildA );
hrnChildB = id2hrn.get( idChildA );
- ReferenceEdgeProperties repB = repA.copy();
+ repB = repA.copy();
addReferenceEdge( hrnB, hrnChildB, repB );
}
- // otherwise, the edge already existed in both graphs.
- // if this is the case, check to see whether the isUnique
- // predicate of the edges might change
- else
- {
-
+ // otherwise, the edge already existed in both graphs
+ // so merge their reachability sets
+ else {
+ // just replace this beta set with the union
+ assert repB != null;
+ repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
}
}
}
assert td2ln.containsKey( tdA );
LabelNode lnB = td2ln.get( tdA );
- HeapRegionNode hrnChildB = null;
+ HeapRegionNode hrnChildB = null;
+ ReferenceEdgeProperties repB = null;
Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
while( heapRegionsItrB.hasNext() ) {
- Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) meC.getKey();
+ Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
+ hrnChildB = (HeapRegionNode) meC.getKey();
+ ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
if( hrnChildB.equals( idChildA ) ) {
edgeFound = true;
+ repB = rep;
}
}
if( !edgeFound ) {
assert id2hrn.containsKey( idChildA );
hrnChildB = id2hrn.get( idChildA );
- ReferenceEdgeProperties repB = repA.copy();
+ repB = repA.copy();
addReferenceEdge( lnB, hrnChildB, repB );
}
- // otherwise, the edge already existed in both graphs.
- // if this is the case, check to see whether the isUnique
- // predicate of the edges might change
- else
- {
-
+ // otherwise, the edge already existed in both graphs
+ // so merge the reachability sets
+ else {
+ // just replace this beta set with the union
+ assert repB != null;
+ repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
}
}
}
protected void mergeId2paramIndex( OwnershipGraph og ) {
if( id2paramIndex.size() == 0 ) {
id2paramIndex = og.id2paramIndex;
+ paramIndex2id = og.paramIndex2id;
return;
}
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
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;
}
return false;
}
- HeapRegionNode hrnB = og.id2hrn.get( idA );
+ //HeapRegionNode hrnB = og.id2hrn.get( idA );
+ HeapRegionNode hrnB = id2hrn.get( idA );
if( !hrnA.equals( hrnB ) ) {
return false;
}
- /*
- // 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 ) {
+ // 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<Integer> getReachableSet( HashSet<Integer> idSetB ) {
+
+ HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
+ HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
+
+ // 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<Integer> idSetReachableFromB = new HashSet<Integer>();
+
+ // 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<Integer> idSet ) {
+
+ assert id2hrn.contains( id );
+ HeapRegionNode hrn = id2hrn.get( id );
+
+ /*
+ HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
+
+ 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<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
+ HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
+ 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;
}
- */
+
// for writing ownership graphs to dot files
public void writeGraph( Descriptor methodDesc,
- FlatNode fn ) throws java.io.IOException {
+ FlatNode fn,
+ boolean writeLabels,
+ boolean writeReferencers
+ ) throws java.io.IOException {
writeGraph(
methodDesc.getSymbol() +
methodDesc.getNum() +
- fn.toString()
+ fn.toString(),
+ writeLabels,
+ writeReferencers
);
}
- public void writeGraph( Descriptor methodDesc ) throws java.io.IOException {
+ public void writeGraph( Descriptor methodDesc,
+ boolean writeLabels,
+ boolean writeReferencers
+ ) throws java.io.IOException {
writeGraph(
methodDesc.getSymbol() +
methodDesc.getNum() +
- "COMPLETE"
+ "COMPLETE",
+ writeLabels,
+ writeReferencers
);
}
- private void writeGraph( String graphName ) 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
graphName = graphName.replaceAll( "[\\W]", "" );
BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
bw.write( "digraph "+graphName+" {\n" );
+ //bw.write( " size=\"7.5,10\";\n" );
+
// then visit every heap region node
HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
Map.Entry me = (Map.Entry) i.next();
HeapRegionNode hrn = (HeapRegionNode) me.getValue();
if( !visited.contains( hrn ) ) {
- traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL, hrn, bw, null, visited );
+ traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
+ hrn,
+ bw,
+ null,
+ visited,
+ writeReferencers );
}
}
- // then visit every label node
- s = td2ln.entrySet();
- i = s.iterator();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry) i.next();
- LabelNode ln = (LabelNode) me.getValue();
-
- HeapRegionNode hrn = null;
- Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
- while( heapRegionsItr.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItr.next();
- hrn = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
-
- String edgeLabel = "";
- if( rep.isUnique() ) {
- edgeLabel = "Unique";
+ bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
+
+
+ // then visit every label node, useful for debugging
+ if( writeLabels ) {
+ s = td2ln.entrySet();
+ i = s.iterator();
+ while( i.hasNext() ) {
+ Map.Entry me = (Map.Entry) i.next();
+ LabelNode ln = (LabelNode) me.getValue();
+
+ HeapRegionNode hrn = null;
+ Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
+ while( heapRegionsItr.hasNext() ) {
+ Map.Entry meH = (Map.Entry) heapRegionsItr.next();
+ hrn = (HeapRegionNode) meH.getKey();
+ ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
+
+ bw.write( " " + ln.toString() +
+ " -> " + hrn.toString() +
+ "[label=\"" + rep.toEdgeLabelString() +
+ "\",decorate];\n" );
}
- bw.write( " " + ln.toString() +
- " -> " + hrn.toString() +
- "[label=\"" + edgeLabel +
- "\"];\n" );
}
}
+
bw.write( "}\n" );
bw.close();
}
HeapRegionNode hrn,
BufferedWriter bw,
TempDescriptor td,
- HashSet<HeapRegionNode> visited
+ HashSet<HeapRegionNode> visited,
+ boolean writeReferencers
) throws java.io.IOException {
if( visited.contains( hrn ) ) {
attributes += ",style=filled,fillcolor=lightgrey";
}
- attributes += ",label=\"" +
- hrn.getDescription() +
+ attributes += ",label=\"ID" +
+ hrn.getID() +
+ "\\n" +
+ hrn.getDescription() +
+ "\\n" +
+ hrn.getAlphaString() +
"\"]";
bw.write( " " + hrn.toString() + attributes + ";\n" );
}
- // go back and let a compile flag control whether the light
- // gray "referencer" edges are written to dot files. It makes
- // the graph cluttered but can be useful for debugging.
- /*
- OwnershipNode onRef = null;
- Iterator refItr = hrn.iteratorToReferencers();
- while( refItr.hasNext() ) {
- onRef = (OwnershipNode) refItr.next();
-
- switch( mode ) {
- case VISIT_HRN_WRITE_FULL:
- bw.write( " " + hrn.toString() +
- " -> " + onRef.toString() +
- "[color=lightgray];\n" );
- break;
+ // useful for debugging
+ if( writeReferencers ) {
+ OwnershipNode onRef = null;
+ Iterator refItr = hrn.iteratorToReferencers();
+ while( refItr.hasNext() ) {
+ onRef = (OwnershipNode) refItr.next();
+
+ switch( mode ) {
+ case VISIT_HRN_WRITE_FULL:
+ bw.write( " " + hrn.toString() +
+ " -> " + onRef.toString() +
+ "[color=lightgray];\n" );
+ break;
+ }
}
}
- */
+
HeapRegionNode hrnChild = null;
Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
switch( mode ) {
case VISIT_HRN_WRITE_FULL:
- String edgeLabel = "";
- if( rep.isUnique() ) {
- edgeLabel = "Unique";
- }
bw.write( " " + hrn.toString() +
" -> " + hrnChild.toString() +
- "[label=\"" + edgeLabel +
- "\"];\n" );
+ "[label=\"" + rep.toEdgeLabelString() +
+ "\",decorate];\n" );
break;
}
- traverseHeapRegionNodes( mode, hrnChild, bw, td, visited );
+ traverseHeapRegionNodes( mode,
+ hrnChild,
+ bw,
+ td,
+ visited,
+ writeReferencers );
}
}
}
projects / IRC.git / blobdiff