1 package Analysis.OwnershipAnalysis;
8 public class OwnershipGraph {
10 private int allocationDepth;
12 // there was already one other very similar reason
13 // for traversing heap nodes that is no longer needed
14 // instead of writing a new heap region visitor, use
15 // the existing method with a new mode to describe what
16 // actions to take during the traversal
17 protected static final int VISIT_HRN_WRITE_FULL = 0;
20 public Hashtable<Integer, HeapRegionNode> id2hrn;
21 public Hashtable<TempDescriptor, LabelNode > td2ln;
22 public Hashtable<Integer, Integer > id2paramIndex;
23 public Hashtable<Integer, Integer > paramIndex2id;
25 public HashSet<AllocationSite> allocationSites;
28 public OwnershipGraph( int allocationDepth ) {
29 this.allocationDepth = allocationDepth;
31 id2hrn = new Hashtable<Integer, HeapRegionNode>();
32 td2ln = new Hashtable<TempDescriptor, LabelNode >();
33 id2paramIndex = new Hashtable<Integer, Integer >();
34 paramIndex2id = new Hashtable<Integer, Integer >();
36 allocationSites = new HashSet <AllocationSite>();
40 // label nodes are much easier to deal with than
41 // heap region nodes. Whenever there is a request
42 // for the label node that is associated with a
43 // temp descriptor we can either find it or make a
44 // new one and return it. This is because temp
45 // descriptors are globally unique and every label
46 // node is mapped to exactly one temp descriptor.
47 protected LabelNode getLabelNodeFromTemp( TempDescriptor td ) {
50 if( !td2ln.containsKey( td ) ) {
51 td2ln.put( td, new LabelNode( td ) );
54 return td2ln.get( td );
58 // the reason for this method is to have the option
59 // creating new heap regions with specific IDs, or
60 // duplicating heap regions with specific IDs (especially
61 // in the merge() operation) or to create new heap
62 // regions with a new unique ID.
63 protected HeapRegionNode
64 createNewHeapRegionNode( Integer id,
65 boolean isSingleObject,
69 AllocationSite allocSite,
70 ReachabilitySet alpha,
71 String description ) {
74 id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
78 if( isFlagged || isParameter ) {
79 alpha = new ReachabilitySet( new TokenTuple( id,
81 TokenTuple.ARITY_ONE ) );
83 alpha = new ReachabilitySet();
87 HeapRegionNode hrn = new HeapRegionNode( id,
94 id2hrn.put( id, hrn );
100 ////////////////////////////////////////////////
102 // Low-level referencee and referencer methods
104 // These methods provide the lowest level for
105 // creating references between ownership nodes
106 // and handling the details of maintaining both
107 // list of referencers and referencees.
109 ////////////////////////////////////////////////
110 protected void addReferenceEdge( OwnershipNode referencer,
111 HeapRegionNode referencee,
112 ReferenceEdgeProperties rep ) {
113 assert referencer != null;
114 assert referencee != null;
116 referencer.addReferencedRegion( referencee, rep );
117 referencee.addReferencer( referencer );
118 rep.setSrc( referencer );
119 rep.setDst( referencee );
122 protected void removeReferenceEdge( OwnershipNode referencer,
123 HeapRegionNode referencee ) {
124 assert referencer != null;
125 assert referencee != null;
126 assert referencer.getReferenceTo( referencee ) != null;
127 assert referencee.isReferencedBy( referencer );
129 referencer.removeReferencedRegion( referencee );
130 referencee.removeReferencer( referencer );
133 protected void clearReferenceEdgesFrom( OwnershipNode referencer ) {
134 assert referencer != null;
136 // get a copy of the table to iterate over, otherwise
137 // we will be trying to take apart the table as we
138 // are iterating over it, which won't work
139 Iterator i = referencer.setIteratorToReferencedRegionsClone();
140 while( i.hasNext() ) {
141 Map.Entry me = (Map.Entry) i.next();
142 HeapRegionNode referencee = (HeapRegionNode) me.getKey();
143 removeReferenceEdge( referencer, referencee );
147 protected void clearReferenceEdgesTo( HeapRegionNode referencee ) {
148 assert referencee != null;
150 // get a copy of the table to iterate over, otherwise
151 // we will be trying to take apart the table as we
152 // are iterating over it, which won't work
153 Iterator i = referencee.iteratorToReferencersClone();
154 while( i.hasNext() ) {
155 OwnershipNode referencer = (OwnershipNode) i.next();
156 removeReferenceEdge( referencer, referencee );
160 protected void propagateTokensOverNodes( HeapRegionNode nPrime,
162 HashSet<HeapRegionNode> nodesWithNewAlpha,
163 HashSet<ReferenceEdgeProperties> edgesWithNewBeta ) {
165 HashSet<HeapRegionNode> todoNodes
166 = new HashSet<HeapRegionNode>();
167 todoNodes.add( nPrime );
169 HashSet<ReferenceEdgeProperties> todoEdges
170 = new HashSet<ReferenceEdgeProperties>();
172 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
173 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
174 nodePlannedChanges.put( nPrime, c0 );
176 Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges
177 = new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
179 Hashtable<HeapRegionNode, ChangeTupleSet> nodeChangesMade
180 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
182 while( !todoNodes.isEmpty() ) {
183 HeapRegionNode n = todoNodes.iterator().next();
184 todoNodes.remove( n );
186 ChangeTupleSet C = nodePlannedChanges.get( n );
188 if( !nodeChangesMade.containsKey( n ) ) {
189 nodeChangesMade.put( n, new ChangeTupleSet().makeCanonical() );
192 Iterator itrC = C.iterator();
193 while( itrC.hasNext() ) {
194 ChangeTuple c = (ChangeTuple) itrC.next();
196 if( n.getAlpha().contains( c.getSetToMatch() ) ) {
197 ReachabilitySet withChange = n.getAlpha().union( c.getSetToAdd() );
198 n.setAlphaNew( n.getAlphaNew().union( withChange ) );
199 nodesWithNewAlpha.add( n );
200 nodeChangesMade.put( n, nodeChangesMade.get( n ).union( c ) );
204 ChangeTupleSet Cprime = nodeChangesMade.get( n );
206 Iterator referItr = n.iteratorToReferencers();
207 while( referItr.hasNext() ) {
208 OwnershipNode on = (OwnershipNode) referItr.next();
209 ReferenceEdgeProperties rep = on.getReferenceTo( n );
210 todoEdges.add( rep );
212 if( !edgePlannedChanges.containsKey( rep ) ) {
213 edgePlannedChanges.put( rep, new ChangeTupleSet().makeCanonical() );
216 edgePlannedChanges.put( rep, edgePlannedChanges.get( rep ).union( Cprime ) );
219 HeapRegionNode m = null;
220 ReferenceEdgeProperties f = null;
221 Iterator refeeItr = n.setIteratorToReferencedRegions();
222 while( refeeItr.hasNext() ) {
223 Map.Entry me = (Map.Entry) refeeItr.next();
224 m = (HeapRegionNode) me.getKey();
225 f = (ReferenceEdgeProperties) me.getValue();
227 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
229 Iterator itrCprime = Cprime.iterator();
230 while( itrCprime.hasNext() ) {
231 ChangeTuple c = (ChangeTuple) itrCprime.next();
232 if( f.getBeta().contains( c.getSetToMatch() ) ) {
233 changesToPass = changesToPass.union( c );
237 if( !changesToPass.isEmpty() ) {
238 if( !nodePlannedChanges.containsKey( m ) ) {
239 nodePlannedChanges.put( m, new ChangeTupleSet().makeCanonical() );
242 ChangeTupleSet currentChanges = nodePlannedChanges.get( m );
244 if( !changesToPass.isSubset( currentChanges ) ) {
246 nodePlannedChanges.put( m, currentChanges.union( changesToPass ) );
252 propagateTokensOverEdges( todoEdges, edgePlannedChanges, nodesWithNewAlpha, edgesWithNewBeta );
256 protected void propagateTokensOverEdges(
257 HashSet<ReferenceEdgeProperties> todoEdges,
258 Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges,
259 HashSet<HeapRegionNode> nodesWithNewAlpha,
260 HashSet<ReferenceEdgeProperties> edgesWithNewBeta ) {
263 while( !todoEdges.isEmpty() ) {
264 ReferenceEdgeProperties e = todoEdges.iterator().next();
265 todoEdges.remove( e );
267 if( !edgePlannedChanges.containsKey( e ) ) {
268 edgePlannedChanges.put( e, new ChangeTupleSet().makeCanonical() );
271 ChangeTupleSet C = edgePlannedChanges.get( e );
273 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
275 Iterator itrC = C.iterator();
276 while( itrC.hasNext() ) {
277 ChangeTuple c = (ChangeTuple) itrC.next();
278 if( e.getBeta().contains( c.getSetToMatch() ) ) {
279 ReachabilitySet withChange = e.getBeta().union( c.getSetToAdd() );
280 e.setBetaNew( e.getBetaNew().union( withChange ) );
281 edgesWithNewBeta.add( e );
282 changesToPass = changesToPass.union( c );
286 OwnershipNode onSrc = e.getSrc();
288 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
289 HeapRegionNode n = (HeapRegionNode) onSrc;
290 Iterator referItr = n.iteratorToReferencers();
292 while( referItr.hasNext() ) {
293 OwnershipNode onRef = (OwnershipNode) referItr.next();
294 ReferenceEdgeProperties f = onRef.getReferenceTo( n );
296 if( !edgePlannedChanges.containsKey( f ) ) {
297 edgePlannedChanges.put( f, new ChangeTupleSet().makeCanonical() );
300 ChangeTupleSet currentChanges = edgePlannedChanges.get( f );
302 if( !changesToPass.isSubset( currentChanges ) ) {
304 edgePlannedChanges.put( f, currentChanges.union( changesToPass ) );
312 ////////////////////////////////////////////////////
314 // Assignment Operation Methods
316 // These methods are high-level operations for
317 // modeling program assignment statements using
318 // the low-level reference create/remove methods
321 // The destination in an assignment statement is
322 // going to have new references. The method of
323 // determining the references depends on the type
324 // of the FlatNode assignment and the predicates
325 // of the nodes and edges involved.
327 ////////////////////////////////////////////////////
328 public void assignTempToTemp( TempDescriptor src,
329 TempDescriptor dst ) {
330 LabelNode srcln = getLabelNodeFromTemp( src );
331 LabelNode dstln = getLabelNodeFromTemp( dst );
333 clearReferenceEdgesFrom( dstln );
335 HeapRegionNode newReferencee = null;
336 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
337 while( srcRegionsItr.hasNext() ) {
338 Map.Entry me = (Map.Entry) srcRegionsItr.next();
339 newReferencee = (HeapRegionNode) me.getKey();
340 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
342 addReferenceEdge( dstln, newReferencee, rep.copy() );
346 public void assignTempToField( TempDescriptor src,
348 FieldDescriptor fd ) {
349 LabelNode srcln = getLabelNodeFromTemp( src );
350 LabelNode dstln = getLabelNodeFromTemp( dst );
352 clearReferenceEdgesFrom( dstln );
354 HeapRegionNode hrn = null;
355 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
356 while( srcRegionsItr.hasNext() ) {
357 Map.Entry me = (Map.Entry) srcRegionsItr.next();
358 hrn = (HeapRegionNode) me.getKey();
359 ReferenceEdgeProperties rep1 = (ReferenceEdgeProperties) me.getValue();
360 ReachabilitySet beta1 = rep1.getBeta();
362 HeapRegionNode hrnOneHop = null;
363 Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions();
364 while( hrnRegionsItr.hasNext() ) {
365 Map.Entry meH = (Map.Entry) hrnRegionsItr.next();
366 hrnOneHop = (HeapRegionNode) meH.getKey();
367 ReferenceEdgeProperties rep2 = (ReferenceEdgeProperties) meH.getValue();
368 ReachabilitySet beta2 = rep2.getBeta();
370 ReferenceEdgeProperties rep =
371 new ReferenceEdgeProperties( false,
373 beta1.intersection( beta2 ) );
375 addReferenceEdge( dstln, hrnOneHop, rep );
380 public void assignFieldToTemp( TempDescriptor src,
382 FieldDescriptor fd ) {
384 // I think my use of src and dst are actually backwards in this method!
385 // acccording to the Reachability Notes, think of dst at N and src as N prime
387 LabelNode srcln = getLabelNodeFromTemp( src );
388 LabelNode dstln = getLabelNodeFromTemp( dst );
390 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
391 HashSet<ReferenceEdgeProperties> edgesWithNewBeta = new HashSet<ReferenceEdgeProperties>();
393 HeapRegionNode hrn = null;
394 ReferenceEdgeProperties rep = null;
395 Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions();
396 while( dstRegionsItr.hasNext() ) {
397 Map.Entry me = (Map.Entry) dstRegionsItr.next();
398 hrn = (HeapRegionNode) me.getKey();
399 rep = (ReferenceEdgeProperties) me.getValue();
401 ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() );
403 HeapRegionNode hrnSrc = null;
404 ReferenceEdgeProperties repSrc = null;
405 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
406 while( srcRegionsItr.hasNext() ) {
407 Map.Entry meS = (Map.Entry) srcRegionsItr.next();
408 hrnSrc = (HeapRegionNode) meS.getKey();
409 repSrc = (ReferenceEdgeProperties) meS.getValue();
411 ReachabilitySet O = srcln.getReferenceTo( hrnSrc ).getBeta();
414 // propagate tokens over nodes starting from hrnSrc, and it will
415 // take care of propagating back up edges from any touched nodes
416 ChangeTupleSet Cy = O.unionUpArityToChangeSet( R );
417 propagateTokensOverNodes( hrnSrc, Cy, nodesWithNewAlpha, edgesWithNewBeta );
420 // then propagate back just up the edges from hrn
421 ChangeTupleSet Cx = R.unionUpArityToChangeSet( O );
423 HashSet<ReferenceEdgeProperties> todoEdges =
424 new HashSet<ReferenceEdgeProperties>();
426 Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges =
427 new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
429 Iterator referItr = hrn.iteratorToReferencers();
430 while( referItr.hasNext() ) {
431 OwnershipNode onRef = (OwnershipNode) referItr.next();
432 ReferenceEdgeProperties repUpstream = onRef.getReferenceTo( hrn );
434 todoEdges.add( repUpstream );
435 edgePlannedChanges.put( repUpstream, Cx );
438 propagateTokensOverEdges( todoEdges,
443 // finally, create the actual reference edge hrn->hrnSrc
444 ReferenceEdgeProperties repNew
445 = new ReferenceEdgeProperties( false,
447 repSrc.getBetaNew().pruneBy( hrn.getAlpha() )
450 addReferenceEdge( hrn, hrnSrc, repNew );
454 Iterator nodeItr = nodesWithNewAlpha.iterator();
455 while( nodeItr.hasNext() ) {
456 ((HeapRegionNode) nodeItr.next()).applyAlphaNew();
459 Iterator edgeItr = edgesWithNewBeta.iterator();
460 while( edgeItr.hasNext() ) {
461 ((ReferenceEdgeProperties) edgeItr.next()).applyBetaNew();
465 public void assignTempToParameterAllocation( boolean isTask,
467 Integer paramIndex ) {
470 LabelNode lnParam = getLabelNodeFromTemp( td );
471 HeapRegionNode hrn = createNewHeapRegionNode( null,
478 "param" + paramIndex );
480 // keep track of heap regions that were created for
481 // parameter labels, the index of the parameter they
482 // are for is important when resolving method calls
483 Integer newID = hrn.getID();
484 assert !id2paramIndex.containsKey ( newID );
485 assert !id2paramIndex.containsValue( paramIndex );
486 id2paramIndex.put( newID, paramIndex );
487 paramIndex2id.put( paramIndex, newID );
489 ReachabilitySet beta = new ReachabilitySet( new TokenTuple( newID,
491 TokenTuple.ARITY_ONE ) );
493 // heap regions for parameters are always multiple object (see above)
494 // and have a reference to themselves, because we can't know the
495 // structure of memory that is passed into the method. We're assuming
497 addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( false, false, beta ) );
498 addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( false, true, beta ) );
501 public void assignTempToNewAllocation( TempDescriptor td,
502 AllocationSite as ) {
509 // after the age operation the newest (or zero-ith oldest)
510 // node associated with the allocation site should have
511 // no references to it as if it were a newly allocated
512 // heap region, so make a reference to it to complete
514 Integer idNewest = as.getIthOldest( 0 );
515 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
516 assert hrnNewest != null;
518 LabelNode dst = getLabelNodeFromTemp( td );
520 clearReferenceEdgesFrom( dst );
522 addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false, false, hrnNewest.getAlpha() ) );
526 // use the allocation site (unique to entire analysis) to
527 // locate the heap region nodes in this ownership graph
528 // that should be aged. The process models the allocation
529 // of new objects and collects all the oldest allocations
530 // in a summary node to allow for a finite analysis
532 // There is an additional property of this method. After
533 // running it on a particular ownership graph (many graphs
534 // may have heap regions related to the same allocation site)
535 // the heap region node objects in this ownership graph will be
536 // allocated. Therefore, after aging a graph for an allocation
537 // site, attempts to retrieve the heap region nodes using the
538 // integer id's contained in the allocation site should always
539 // return non-null heap regions.
540 public void age( AllocationSite as ) {
542 // aging adds this allocation site to the graph's
543 // list of sites that exist in the graph, or does
544 // nothing if the site is already in the list
545 allocationSites.add( as );
548 //////////////////////////////////////////////////////////////////
550 // move existing references down the line toward
551 // the oldest element, starting with the oldest
554 // TempDescriptor = the td passed into this function, left side of new statement
555 // AllocationSite = { alpha0, alpha1, alpha2, alphaSummary }
557 // 1. Specially merge refs in/out at alpha2 into alphaSummary
558 // 2. Move refs in/out at alpha1 over to alpha2 (alpha1 becomes alpha2)
559 // 3. Move refs in/out at alpha0 over to alpha1
560 // 4. Assign reference from td to alpha0, which now represents a freshly allocated object
562 //////////////////////////////////////////////////////////////////
565 // first specially merge the references from the oldest
566 // node into the summary node, keeping track of 1-to-1 edges
567 Integer idSummary = as.getSummary();
568 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
570 // if this is null then we haven't touched this allocation site
571 // in the context of the current ownership graph, so simply
572 // allocate an appropriate heap region node
573 // this should only happen once per ownership per allocation site,
574 // and a particular integer id can be used to locate the heap region
575 // in different ownership graphs that represents the same part of an
577 if( hrnSummary == null ) {
579 boolean hasFlags = false;
580 if( as.getType().isClass() ) {
581 hasFlags = as.getType().getClassDesc().hasFlags();
584 hrnSummary = createNewHeapRegionNode( idSummary,
591 as + "\\n" + as.getType() + "\\nsummary" );
593 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
594 Integer idIth = as.getIthOldest( i );
595 assert !id2hrn.containsKey( idIth );
596 createNewHeapRegionNode( idIth,
603 as + "\\n" + as.getType() + "\\n" + i + " oldest" );
607 // first transfer the references out of alpha_k to alpha_s
608 Integer idK = as.getOldest();
609 HeapRegionNode hrnK = id2hrn.get( idK );
611 HeapRegionNode hrnReferencee = null;
612 Iterator itrReferencee = hrnK.setIteratorToReferencedRegions();
613 while( itrReferencee.hasNext() ) {
614 Map.Entry me = (Map.Entry) itrReferencee.next();
615 hrnReferencee = (HeapRegionNode) me.getKey();
616 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
618 ReferenceEdgeProperties repSummary = hrnSummary.getReferenceTo( hrnReferencee );
619 ReferenceEdgeProperties repMerged = rep.copy();
621 if( repSummary == null ) {
622 // the merge is trivial, nothing to be done
624 // otherwise an edge from the referencer to alpha_S exists already
625 // and the edge referencer->alpha_K should be merged with it
626 repMerged.setBeta( repMerged.getBeta().union( repSummary.getBeta() ) );
629 addReferenceEdge( hrnSummary, hrnReferencee, repMerged );
632 // next transfer references to alpha_k over to alpha_s
633 OwnershipNode onReferencer = null;
634 Iterator itrReferencer = hrnK.iteratorToReferencers();
635 while( itrReferencer.hasNext() ) {
636 onReferencer = (OwnershipNode) itrReferencer.next();
638 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnK );
640 ReferenceEdgeProperties repSummary = onReferencer.getReferenceTo( hrnSummary );
641 ReferenceEdgeProperties repMerged = rep.copy();
643 if( repSummary == null ) {
644 // the merge is trivial, nothing to be done
646 // otherwise an edge from the referencer to alpha_S exists already
647 // and the edge referencer->alpha_K should be merged with it
648 repMerged.setBeta( repMerged.getBeta().union( repSummary.getBeta() ) );
651 addReferenceEdge( onReferencer, hrnSummary, repMerged );
654 // then merge alpha_k reachability into alpha_s
655 hrnSummary.setAlpha( hrnSummary.getAlpha().union( hrnK.getAlpha() ) );
658 // then move down the line of heap region nodes
659 // clobbering the ith and transferring all references
660 // to and from i-1 to node i. Note that this clobbers
661 // the oldest node (alpha_k) that was just merged into
662 // the summary above and should move everything from
663 // alpha_0 to alpha_1 before we finish
664 for( int i = allocationDepth - 1; i > 0; --i ) {
666 // move references from the i-1 oldest to the ith oldest
667 Integer idIth = as.getIthOldest( i );
668 HeapRegionNode hrnI = id2hrn.get( idIth );
669 Integer idImin1th = as.getIthOldest( i - 1 );
670 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
672 // clear references in and out of node i
673 clearReferenceEdgesFrom( hrnI );
674 clearReferenceEdgesTo ( hrnI );
676 // copy each edge in and out of i-1 to i
677 hrnReferencee = null;
678 itrReferencee = hrnImin1.setIteratorToReferencedRegions();
679 while( itrReferencee.hasNext() ) {
680 Map.Entry me = (Map.Entry) itrReferencee.next();
681 hrnReferencee = (HeapRegionNode) me.getKey();
682 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
684 addReferenceEdge( hrnI, hrnReferencee, rep.copy() );
688 itrReferencer = hrnImin1.iteratorToReferencers();
689 while( itrReferencer.hasNext() ) {
690 onReferencer = (OwnershipNode) itrReferencer.next();
692 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnImin1 );
695 addReferenceEdge( onReferencer, hrnI, rep.copy() );
698 // replace hrnI reachability with hrnImin1
699 hrnI.setAlpha( hrnImin1.getAlpha() );
702 // as stated above, the newest node alpha_0 should have had its
703 // references moved over to alpha_1, so we can wipe alpha_0 clean
704 // in preparation for operations that want to reference a freshly
705 // allocated object from this allocation site
706 Integer id0th = as.getIthOldest( 0 );
707 HeapRegionNode hrn0 = id2hrn.get( id0th );
709 // the loop to move references from i-1 to i should
710 // have touched this node, therefore assert it is non-null
714 // clear all references in and out of newest node
715 clearReferenceEdgesFrom( hrn0 );
716 clearReferenceEdgesTo ( hrn0 );
719 // now tokens in reachability sets need to "age" as well
720 ReferenceEdgeProperties repToAge = null;
721 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
722 while( itrAllLabelNodes.hasNext() ) {
723 Map.Entry me = (Map.Entry) itrAllLabelNodes.next();
724 LabelNode ln = (LabelNode) me.getValue();
726 Iterator itrEdges = ln.setIteratorToReferencedRegions();
727 while( itrEdges.hasNext() ) {
728 Map.Entry meE = (Map.Entry) itrEdges.next();
729 repToAge = (ReferenceEdgeProperties) meE.getValue();
731 ageTokens( as, repToAge );
734 HeapRegionNode hrnToAge = null;
735 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
736 while( itrAllHRNodes.hasNext() ) {
737 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
738 hrnToAge = (HeapRegionNode) me.getValue();
740 ageTokens( as, hrnToAge );
742 Iterator itrEdges = hrnToAge.setIteratorToReferencedRegions();
743 while( itrEdges.hasNext() ) {
744 Map.Entry meE = (Map.Entry) itrEdges.next();
745 repToAge = (ReferenceEdgeProperties) meE.getValue();
747 ageTokens( as, repToAge );
752 // after tokens have been aged, reset newest node's reachability
753 hrn0.setAlpha( new ReachabilitySet(
755 new TokenTuple( hrn0 )
761 protected void ageTokens( AllocationSite as, ReferenceEdgeProperties rep ) {
762 rep.setBeta( rep.getBeta().ageTokens( as ) );
765 protected void ageTokens( AllocationSite as, HeapRegionNode hrn ) {
766 hrn.setAlpha( hrn.getAlpha().ageTokens( as ) );
771 // the heap regions that are specially allocated as multiple-object
772 // regions for method parameters need to be remembered in order to
773 // resolve a function call. So actually, we need a mapping from
774 // caller argument descriptors to the callee parameter heap regions
775 // to apply reference edges in the callee to the caller graph.
777 // also, Constructors and virtual dispatch methods have a "this"
778 // argument that make the mapping of arguments to parameters a little
779 // tricky. What happens to that this region?
782 public void resolveMethodCall( FlatCall fc,
785 OwnershipGraph ogCallee ) { //,
786 //HashSet<AllocationSite> allocSiteSet ) {
788 // first age all of the allocation sites from
789 // the callee graph in this graph
790 Iterator i = ogCallee.allocationSites.iterator();
791 while( i.hasNext() ) {
792 AllocationSite allocSite = (AllocationSite) i.next();
793 this.age( allocSite );
796 // in non-static methods there is a "this" pointer
797 // that should be taken into account
799 assert fc.numArgs() == fm.numParameters();
801 assert fc.numArgs() + 1 == fm.numParameters();
804 // the heap regions represented by the arguments (caller graph)
805 // and heap regions for the parameters (callee graph)
806 // don't correspond to each other by heap region ID. In fact,
807 // an argument label node can be referencing several heap regions
808 // so the parameter label always references a multiple-object
809 // heap region in order to handle the range of possible contexts
810 // for a method call. This means we need to make a special mapping
811 // of argument->parameter regions in order to update the caller graph
813 // for every heap region->heap region edge in the
814 // callee graph, create the matching edge or edges
815 // in the caller graph
816 Set sCallee = ogCallee.id2hrn.entrySet();
817 Iterator iCallee = sCallee.iterator();
818 while( iCallee.hasNext() ) {
819 Map.Entry meCallee = (Map.Entry) iCallee.next();
820 Integer idCallee = (Integer) meCallee.getKey();
821 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
823 HeapRegionNode hrnChildCallee = null;
824 Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
825 while( heapRegionsItrCallee.hasNext() ) {
826 Map.Entry me = (Map.Entry) heapRegionsItrCallee.next();
827 hrnChildCallee = (HeapRegionNode) me.getKey();
828 ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
830 Integer idChildCallee = hrnChildCallee.getID();
832 // only address this edge if it is not a special reflexive edge
833 if( !repC.isInitialParamReflexive() ) {
835 // now we know that in the callee method's ownership graph
836 // there is a heap region->heap region reference edge given
837 // by heap region pointers:
838 // hrnCallee -> heapChildCallee
840 // or by the ownership-graph independent ID's:
841 // idCallee -> idChildCallee
843 // So now make a set of possible source heaps in the caller graph
844 // and a set of destination heaps in the caller graph, and make
845 // a reference edge in the caller for every possible (src,dst) pair
846 if( !ogCallee.id2hrn.contains( idChildCallee ) ) {
847 //System.out.println( "Houston, we got a problem." );
848 //System.out.println( "idCallee is "+idCallee );
849 //System.out.println( "idChildCallee is "+idChildCallee );
852 writeGraph( "caller", false, false, false );
853 ogCallee.writeGraph( "callee", false, false, false );
854 } catch( IOException e ) {}
857 HashSet<HeapRegionNode> possibleCallerSrcs =
858 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
863 HashSet<HeapRegionNode> possibleCallerDsts =
864 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
869 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
870 Iterator srcItr = possibleCallerSrcs.iterator();
871 while( srcItr.hasNext() ) {
872 HeapRegionNode src = (HeapRegionNode) srcItr.next();
874 Iterator dstItr = possibleCallerDsts.iterator();
875 while( dstItr.hasNext() ) {
876 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
878 addReferenceEdge( src, dst, repC.copy() );
886 private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
891 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
893 if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
894 // the heap region that is part of this
895 // reference edge won't have a matching ID in the
896 // caller graph because it is specifically allocated
897 // for a particular parameter. Use that information
898 // to find the corresponding argument label in the
899 // caller in order to create the proper reference edge
901 assert !id2hrn.containsKey( idCallee );
903 Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
904 TempDescriptor argTemp;
906 // now depending on whether the callee is static or not
907 // we need to account for a "this" argument in order to
908 // find the matching argument in the caller context
910 argTemp = fc.getArg( paramIndex );
912 if( paramIndex == 0 ) {
913 argTemp = fc.getThis();
915 argTemp = fc.getArg( paramIndex - 1 );
919 LabelNode argLabel = getLabelNodeFromTemp( argTemp );
920 Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
921 while( argHeapRegionsItr.hasNext() ) {
922 Map.Entry meArg = (Map.Entry) argHeapRegionsItr.next();
923 HeapRegionNode argHeapRegion = (HeapRegionNode) meArg.getKey();
924 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
926 possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
930 // this heap region is not a parameter, so it should
931 // have a matching heap region in the caller graph
932 assert id2hrn.containsKey( idCallee );
933 possibleCallerHRNs.add( id2hrn.get( idCallee ) );
936 return possibleCallerHRNs;
941 ////////////////////////////////////////////////////
942 // in merge() and equals() methods the suffix A
943 // represents the passed in graph and the suffix
944 // B refers to the graph in this object
945 // Merging means to take the incoming graph A and
946 // merge it into B, so after the operation graph B
947 // is the final result.
948 ////////////////////////////////////////////////////
949 public void merge( OwnershipGraph og ) {
955 mergeOwnershipNodes ( og );
956 mergeReferenceEdges ( og );
957 mergeId2paramIndex ( og );
958 mergeAllocationSites( og );
962 protected void mergeOwnershipNodes( OwnershipGraph og ) {
963 Set sA = og.id2hrn.entrySet();
964 Iterator iA = sA.iterator();
965 while( iA.hasNext() ) {
966 Map.Entry meA = (Map.Entry) iA.next();
967 Integer idA = (Integer) meA.getKey();
968 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
970 // if this graph doesn't have a node the
971 // incoming graph has, allocate it
972 if( !id2hrn.containsKey( idA ) ) {
973 HeapRegionNode hrnB = hrnA.copy();
974 id2hrn.put( idA, hrnB );
977 // otherwise this is a node present in both graphs
978 // so make the new reachability set a union of the
979 // nodes' reachability sets
980 HeapRegionNode hrnB = id2hrn.get( idA );
981 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
985 // now add any label nodes that are in graph B but
987 sA = og.td2ln.entrySet();
989 while( iA.hasNext() ) {
990 Map.Entry meA = (Map.Entry) iA.next();
991 TempDescriptor tdA = (TempDescriptor) meA.getKey();
992 LabelNode lnA = (LabelNode) meA.getValue();
994 // if the label doesn't exist in B, allocate and add it
995 LabelNode lnB = getLabelNodeFromTemp( tdA );
999 protected void mergeReferenceEdges( OwnershipGraph og ) {
1000 // there is a data structure for storing label nodes
1001 // retireved by temp descriptors, and a data structure
1002 // for stroing heap region nodes retrieved by integer
1003 // ids. Because finding edges requires interacting
1004 // with these disparate data structures frequently the
1005 // process is nearly duplicated, one for each structure
1006 // that stores edges
1009 Set sA = og.id2hrn.entrySet();
1010 Iterator iA = sA.iterator();
1011 while( iA.hasNext() ) {
1012 Map.Entry meA = (Map.Entry) iA.next();
1013 Integer idA = (Integer) meA.getKey();
1014 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1016 HeapRegionNode hrnChildA = null;
1017 Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1018 while( heapRegionsItrA.hasNext() ) {
1019 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
1020 hrnChildA = (HeapRegionNode) me.getKey();
1021 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1023 Integer idChildA = hrnChildA.getID();
1025 // at this point we know an edge in graph A exists
1026 // idA -> idChildA, does this exist in B?
1027 boolean edgeFound = false;
1028 assert id2hrn.containsKey( idA );
1029 HeapRegionNode hrnB = id2hrn.get( idA );
1031 HeapRegionNode hrnChildB = null;
1032 ReferenceEdgeProperties repB = null;
1033 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1034 while( heapRegionsItrB.hasNext() ) {
1035 Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
1036 hrnChildB = (HeapRegionNode) meC.getKey();
1037 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
1039 if( hrnChildB.equals( idChildA ) ) {
1045 // if the edge from A was not found in B,
1048 assert id2hrn.containsKey( idChildA );
1049 hrnChildB = id2hrn.get( idChildA );
1051 addReferenceEdge( hrnB, hrnChildB, repB );
1053 // otherwise, the edge already existed in both graphs
1054 // so merge their reachability sets
1056 // just replace this beta set with the union
1057 assert repB != null;
1058 repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
1063 // and then again with label nodes
1064 sA = og.td2ln.entrySet();
1066 while( iA.hasNext() ) {
1067 Map.Entry meA = (Map.Entry) iA.next();
1068 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1069 LabelNode lnA = (LabelNode) meA.getValue();
1071 HeapRegionNode hrnChildA = null;
1072 Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1073 while( heapRegionsItrA.hasNext() ) {
1074 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
1075 hrnChildA = (HeapRegionNode) meH.getKey();
1076 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1078 Integer idChildA = hrnChildA.getID();
1080 // at this point we know an edge in graph A exists
1081 // tdA -> idChildA, does this exist in B?
1082 boolean edgeFound = false;
1083 assert td2ln.containsKey( tdA );
1084 LabelNode lnB = td2ln.get( tdA );
1086 HeapRegionNode hrnChildB = null;
1087 ReferenceEdgeProperties repB = null;
1088 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1089 while( heapRegionsItrB.hasNext() ) {
1090 Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
1091 hrnChildB = (HeapRegionNode) meC.getKey();
1092 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
1094 if( hrnChildB.equals( idChildA ) ) {
1100 // if the edge from A was not found in B,
1103 assert id2hrn.containsKey( idChildA );
1104 hrnChildB = id2hrn.get( idChildA );
1106 addReferenceEdge( lnB, hrnChildB, repB );
1108 // otherwise, the edge already existed in both graphs
1109 // so merge the reachability sets
1111 // just replace this beta set with the union
1112 assert repB != null;
1113 repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
1119 // you should only merge ownership graphs that have the
1120 // same number of parameters, or if one or both parameter
1121 // index tables are empty
1122 protected void mergeId2paramIndex( OwnershipGraph og ) {
1123 if( id2paramIndex.size() == 0 ) {
1124 id2paramIndex = og.id2paramIndex;
1125 paramIndex2id = og.paramIndex2id;
1129 if( og.id2paramIndex.size() == 0 ) {
1133 assert id2paramIndex.size() == og.id2paramIndex.size();
1136 protected void mergeAllocationSites( OwnershipGraph og ) {
1137 allocationSites.addAll( og.allocationSites );
1142 // it is necessary in the equals() member functions
1143 // to "check both ways" when comparing the data
1144 // structures of two graphs. For instance, if all
1145 // edges between heap region nodes in graph A are
1146 // present and equal in graph B it is not sufficient
1147 // to say the graphs are equal. Consider that there
1148 // may be edges in graph B that are not in graph A.
1149 // the only way to know that all edges in both graphs
1150 // are equally present is to iterate over both data
1151 // structures and compare against the other graph.
1152 public boolean equals( OwnershipGraph og ) {
1158 if( !areHeapRegionNodesEqual( og ) ) {
1162 if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
1166 if( !areLabelNodesEqual( og ) ) {
1170 if( !areLabelToHeapRegionEdgesEqual( og ) ) {
1174 if( !areId2paramIndexEqual( og ) ) {
1178 // if everything is equal up to this point,
1179 // assert that allocationSites is also equal--
1180 // this data is redundant and kept for efficiency
1181 assert allocationSites.equals( og.allocationSites );
1186 protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
1187 // check all nodes in A for presence in graph B
1188 Set sA = og.id2hrn.entrySet();
1189 Iterator iA = sA.iterator();
1190 while( iA.hasNext() ) {
1191 Map.Entry meA = (Map.Entry) iA.next();
1192 Integer idA = (Integer) meA.getKey();
1193 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1195 if( !id2hrn.containsKey( idA ) ) {
1199 //HeapRegionNode hrnB = og.id2hrn.get( idA );
1200 HeapRegionNode hrnB = id2hrn.get( idA );
1201 if( !hrnA.equals( hrnB ) ) {
1206 // then check all nodes in B verses graph A
1207 Set sB = id2hrn.entrySet();
1208 Iterator iB = sB.iterator();
1209 while( iB.hasNext() ) {
1210 Map.Entry meB = (Map.Entry) iB.next();
1211 Integer idB = (Integer) meB.getKey();
1212 HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
1214 if( !og.id2hrn.containsKey( idB ) ) {
1218 // we should have already checked the equality
1219 // of this pairing in the last pass if they both
1220 // exist so assert that they are equal now
1221 HeapRegionNode hrnA = og.id2hrn.get( idB );
1222 assert hrnB.equals( hrnA );
1228 protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
1229 Set sA = og.id2hrn.entrySet();
1230 Iterator iA = sA.iterator();
1231 while( iA.hasNext() ) {
1232 Map.Entry meA = (Map.Entry) iA.next();
1233 Integer idA = (Integer) meA.getKey();
1234 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1236 // we should have already checked that the same
1237 // heap regions exist in both graphs
1238 assert id2hrn.containsKey( idA );
1240 // and are their edges the same? first check every
1241 // edge in A for presence and equality in B
1242 HeapRegionNode hrnChildA = null;
1243 Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1244 while( heapRegionsItrA.hasNext() ) {
1245 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
1246 hrnChildA = (HeapRegionNode) me.getKey();
1247 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1249 Integer idChildA = hrnChildA.getID();
1250 assert id2hrn.containsKey( idChildA );
1252 // at this point we know an edge in graph A exists
1253 // idA -> idChildA, does this edge exist in B?
1254 boolean edgeFound = false;
1255 HeapRegionNode hrnB = id2hrn.get( idA );
1257 HeapRegionNode hrnChildB = null;
1258 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1259 while( heapRegionsItrB.hasNext() ) {
1260 Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
1261 hrnChildB = (HeapRegionNode) meH.getKey();
1262 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1264 if( idChildA.equals( hrnChildB.getID() ) ) {
1265 if( !repA.equals( repB ) ) {
1277 // then check every edge in B for presence in A, starting
1278 // from the same parent HeapRegionNode
1279 HeapRegionNode hrnB = id2hrn.get( idA );
1281 HeapRegionNode hrnChildB = null;
1282 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1283 while( heapRegionsItrB.hasNext() ) {
1284 Map.Entry me = (Map.Entry) heapRegionsItrB.next();
1285 hrnChildB = (HeapRegionNode) me.getKey();
1286 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1288 Integer idChildB = hrnChildB.getID();
1290 // at this point we know an edge in graph B exists
1291 // idB -> idChildB, does this edge exist in A?
1292 boolean edgeFound = false;
1295 heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1296 while( heapRegionsItrA.hasNext() ) {
1297 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
1298 hrnChildA = (HeapRegionNode) meH.getKey();
1299 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1301 if( idChildB.equals( hrnChildA.getID() ) ) {
1302 assert repB.equals( repA );
1316 protected boolean areLabelNodesEqual( OwnershipGraph og ) {
1317 // are all label nodes in A also in graph B?
1318 Set sA = og.td2ln.entrySet();
1319 Iterator iA = sA.iterator();
1320 while( iA.hasNext() ) {
1321 Map.Entry meA = (Map.Entry) iA.next();
1322 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1324 if( !td2ln.containsKey( tdA ) ) {
1329 // are all label nodes in B also in A?
1330 Set sB = td2ln.entrySet();
1331 Iterator iB = sB.iterator();
1332 while( iB.hasNext() ) {
1333 Map.Entry meB = (Map.Entry) iB.next();
1334 TempDescriptor tdB = (TempDescriptor) meB.getKey();
1336 if( !og.td2ln.containsKey( tdB ) ) {
1344 protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
1345 Set sA = og.td2ln.entrySet();
1346 Iterator iA = sA.iterator();
1347 while( iA.hasNext() ) {
1348 Map.Entry meA = (Map.Entry) iA.next();
1349 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1350 LabelNode lnA = (LabelNode) meA.getValue();
1352 // we should have already checked that the same
1353 // label nodes exist in both graphs
1354 assert td2ln.containsKey( tdA );
1356 // and are their edges the same? first check every
1357 // edge in A for presence and equality in B
1358 HeapRegionNode hrnChildA = null;
1359 Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1360 while( heapRegionsItrA.hasNext() ) {
1361 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
1362 hrnChildA = (HeapRegionNode) me.getKey();
1363 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1365 Integer idChildA = hrnChildA.getID();
1366 assert id2hrn.containsKey( idChildA );
1368 // at this point we know an edge in graph A exists
1369 // tdA -> idChildA, does this edge exist in B?
1370 boolean edgeFound = false;
1371 LabelNode lnB = td2ln.get( tdA );
1373 HeapRegionNode hrnChildB = null;
1374 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1375 while( heapRegionsItrB.hasNext() ) {
1376 Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
1377 hrnChildB = (HeapRegionNode) meH.getKey();
1378 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1380 if( idChildA.equals( hrnChildB.getID() ) ) {
1381 if( !repA.equals( repB ) ) {
1393 // then check every edge in B for presence in A, starting
1394 // from the same parent LabelNode
1395 LabelNode lnB = td2ln.get( tdA );
1397 HeapRegionNode hrnChildB = null;
1398 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1399 while( heapRegionsItrB.hasNext() ) {
1400 Map.Entry me = (Map.Entry) heapRegionsItrB.next();
1401 hrnChildB = (HeapRegionNode) me.getKey();
1402 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1404 Integer idChildB = hrnChildB.getID();
1406 // at this point we know an edge in graph B exists
1407 // tdB -> idChildB, does this edge exist in A?
1408 boolean edgeFound = false;
1411 heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1412 while( heapRegionsItrA.hasNext() ) {
1413 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
1414 hrnChildA = (HeapRegionNode) meH.getKey();
1415 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1417 if( idChildB.equals( hrnChildA.getID() ) ) {
1418 assert repB.equals( repA );
1433 protected boolean areId2paramIndexEqual( OwnershipGraph og ) {
1434 return id2paramIndex.size() == og.id2paramIndex.size();
1439 // given a set B of heap region node ID's, return the set of heap
1440 // region node ID's that is reachable from B
1441 public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1443 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1444 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1446 // initial nodes to visit are from set B
1447 Iterator initialItr = idSetB.iterator();
1448 while( initialItr.hasNext() ) {
1449 Integer idInitial = (Integer) initialItr.next();
1450 assert id2hrn.contains( idInitial );
1451 HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1452 toVisit.add( hrnInitial );
1455 HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1457 // do a heap traversal
1458 while( !toVisit.isEmpty() ) {
1459 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1460 toVisit.remove( hrnVisited );
1461 visited.add ( hrnVisited );
1463 // for every node visited, add it to the total
1465 idSetReachableFromB.add( hrnVisited.getID() );
1467 // find other reachable nodes
1468 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1469 while( referenceeItr.hasNext() ) {
1470 Map.Entry me = (Map.Entry) referenceeItr.next();
1471 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1472 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1474 if( !visited.contains( hrnReferencee ) ) {
1475 toVisit.add( hrnReferencee );
1480 return idSetReachableFromB;
1484 // used to find if a heap region can possibly have a reference to
1485 // any of the heap regions in the given set
1486 // if the id supplied is in the set, then a self-referencing edge
1487 // would return true, but that special case is specifically allowed
1488 // meaning that it isn't an external alias
1489 public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1491 assert id2hrn.contains( id );
1492 HeapRegionNode hrn = id2hrn.get( id );
1495 HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1497 Iterator i = idSet.iterator();
1498 while( i.hasNext() ) {
1499 Integer idFromSet = (Integer) i.next();
1500 assert id2hrn.contains( idFromSet );
1501 hrnSet.add( id2hrn.get( idFromSet ) );
1505 // do a traversal from hrn and see if any of the
1506 // heap regions from the set come up during that
1507 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1508 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1511 while( !toVisit.isEmpty() ) {
1512 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1513 toVisit.remove( hrnVisited );
1514 visited.add ( hrnVisited );
1516 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1517 while( referenceeItr.hasNext() ) {
1518 Map.Entry me = (Map.Entry) referenceeItr.next();
1519 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1520 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1522 if( idSet.contains( hrnReferencee.getID() ) ) {
1523 if( !id.equals( hrnReferencee.getID() ) ) {
1528 if( !visited.contains( hrnReferencee ) ) {
1529 toVisit.add( hrnReferencee );
1539 // for writing ownership graphs to dot files
1540 public void writeGraph( Descriptor methodDesc,
1542 boolean writeLabels,
1543 boolean labelSelect,
1544 boolean writeReferencers
1545 ) throws java.io.IOException {
1547 methodDesc.getSymbol() +
1548 methodDesc.getNum() +
1556 public void writeGraph( Descriptor methodDesc,
1558 boolean writeLabels,
1559 boolean writeReferencers
1560 ) throws java.io.IOException {
1562 methodDesc.getSymbol() +
1563 methodDesc.getNum() +
1571 public void writeGraph( Descriptor methodDesc,
1572 boolean writeLabels,
1573 boolean writeReferencers
1574 ) throws java.io.IOException {
1576 methodDesc.getSymbol() +
1577 methodDesc.getNum() +
1585 public void writeGraph( Descriptor methodDesc,
1586 boolean writeLabels,
1587 boolean labelSelect,
1588 boolean writeReferencers
1589 ) throws java.io.IOException {
1591 methodDesc.getSymbol() +
1592 methodDesc.getNum() +
1600 public void writeGraph( String graphName,
1601 boolean writeLabels,
1602 boolean labelSelect,
1603 boolean writeReferencers
1604 ) throws java.io.IOException {
1606 // remove all non-word characters from the graph name so
1607 // the filename and identifier in dot don't cause errors
1608 graphName = graphName.replaceAll( "[\\W]", "" );
1610 BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
1611 bw.write( "digraph "+graphName+" {\n" );
1612 //bw.write( " size=\"7.5,10\";\n" );
1615 // then visit every heap region node
1616 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1618 Set s = id2hrn.entrySet();
1619 Iterator i = s.iterator();
1620 while( i.hasNext() ) {
1621 Map.Entry me = (Map.Entry) i.next();
1622 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1623 if( !visited.contains( hrn ) ) {
1624 traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1633 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
1636 // then visit every label node, useful for debugging
1638 s = td2ln.entrySet();
1640 while( i.hasNext() ) {
1641 Map.Entry me = (Map.Entry) i.next();
1642 LabelNode ln = (LabelNode) me.getValue();
1645 String labelStr = ln.getTempDescriptorString();
1646 if( labelStr.startsWith( "___temp" ) ||
1647 labelStr.startsWith( "___dst" ) ||
1648 labelStr.startsWith( "___srctmp" ) ||
1649 labelStr.startsWith( "___neverused" ) ) {
1654 HeapRegionNode hrn = null;
1655 Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
1656 while( heapRegionsItr.hasNext() ) {
1657 Map.Entry meH = (Map.Entry) heapRegionsItr.next();
1658 hrn = (HeapRegionNode) meH.getKey();
1659 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
1661 bw.write( " " + ln.toString() +
1662 " -> " + hrn.toString() +
1663 "[label=\"" + rep.toEdgeLabelString() +
1664 "\",decorate];\n" );
1674 protected void traverseHeapRegionNodes( int mode,
1678 HashSet<HeapRegionNode> visited,
1679 boolean writeReferencers
1680 ) throws java.io.IOException {
1682 if( visited.contains( hrn ) ) {
1688 case VISIT_HRN_WRITE_FULL:
1690 String attributes = "[";
1692 if( hrn.isSingleObject() ) {
1693 attributes += "shape=box";
1695 attributes += "shape=Msquare";
1698 if( hrn.isFlagged() ) {
1699 attributes += ",style=filled,fillcolor=lightgrey";
1702 attributes += ",label=\"ID" +
1705 hrn.getDescription() +
1707 hrn.getAlphaString() +
1710 bw.write( " " + hrn.toString() + attributes + ";\n" );
1715 // useful for debugging
1716 if( writeReferencers ) {
1717 OwnershipNode onRef = null;
1718 Iterator refItr = hrn.iteratorToReferencers();
1719 while( refItr.hasNext() ) {
1720 onRef = (OwnershipNode) refItr.next();
1723 case VISIT_HRN_WRITE_FULL:
1724 bw.write( " " + hrn.toString() +
1725 " -> " + onRef.toString() +
1726 "[color=lightgray];\n" );
1733 HeapRegionNode hrnChild = null;
1734 Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
1735 while( childRegionsItr.hasNext() ) {
1736 Map.Entry me = (Map.Entry) childRegionsItr.next();
1737 hrnChild = (HeapRegionNode) me.getKey();
1738 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1741 case VISIT_HRN_WRITE_FULL:
1742 bw.write( " " + hrn.toString() +
1743 " -> " + hrnChild.toString() +
1744 "[label=\"" + rep.toEdgeLabelString() +
1745 "\",decorate];\n" );
1749 traverseHeapRegionNodes( mode,