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 propagateTokens( 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 Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgeChangesMade
183 = new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
185 System.out.println( "New propagation with changes "+c0 );
187 while( !todoNodes.isEmpty() ) {
188 HeapRegionNode n = todoNodes.iterator().next();
189 todoNodes.remove( n );
191 System.out.println( " Propagating tokens over "+n );
193 if( !nodeChangesMade.containsKey( n ) ) {
194 nodeChangesMade.put( n, new ChangeTupleSet().makeCanonical() );
197 ChangeTupleSet C = nodePlannedChanges.get( n );
199 Iterator itrC = C.iterator();
200 while( itrC.hasNext() ) {
201 ChangeTuple c = (ChangeTuple) itrC.next();
203 System.out.println( " Considering applying "+c );
205 if( n.getAlpha().contains( c.getSetToMatch() ) ) {
206 n.setAlphaNew( n.getAlpha().union( c.getSetToAdd() ) );
207 nodesWithNewAlpha.add( n );
208 nodeChangesMade.put( n, nodeChangesMade.get( n ).union( c ) );
212 ChangeTupleSet Cprime = nodeChangesMade.get( n );
214 Iterator referItr = n.iteratorToReferencers();
215 while( referItr.hasNext() ) {
216 OwnershipNode on = (OwnershipNode) referItr.next();
217 ReferenceEdgeProperties rep = on.getReferenceTo( n );
218 todoEdges.add( rep );
220 if( !edgePlannedChanges.containsKey( rep ) ) {
221 edgePlannedChanges.put( rep, new ChangeTupleSet().makeCanonical() );
224 edgePlannedChanges.put( rep, edgePlannedChanges.get( rep ).union( Cprime ) );
227 HeapRegionNode m = null;
228 ReferenceEdgeProperties f = null;
229 Iterator refeeItr = n.setIteratorToReferencedRegions();
230 while( refeeItr.hasNext() ) {
231 Map.Entry me = (Map.Entry) refeeItr.next();
232 m = (HeapRegionNode) me.getKey();
233 f = (ReferenceEdgeProperties) me.getValue();
235 ChangeTupleSet changesToPass = new ChangeTupleSet();
237 Iterator itrCprime = Cprime.iterator();
238 while( itrCprime.hasNext() ) {
239 ChangeTuple c = (ChangeTuple) itrCprime.next();
240 if( f.getBeta().contains( c.getSetToMatch() ) ) {
241 changesToPass = changesToPass.union( c );
245 if( !changesToPass.isEmpty() ) {
246 if( !nodePlannedChanges.containsKey( m ) ) {
247 nodePlannedChanges.put( m, new ChangeTupleSet().makeCanonical() );
250 ChangeTupleSet currentChanges = nodePlannedChanges.get( m );
252 if( !changesToPass.isSubset( currentChanges ) ) {
254 nodePlannedChanges.put( m, currentChanges.union( changesToPass ) );
263 ////////////////////////////////////////////////////
265 // Assignment Operation Methods
267 // These methods are high-level operations for
268 // modeling program assignment statements using
269 // the low-level reference create/remove methods
272 // The destination in an assignment statement is
273 // going to have new references. The method of
274 // determining the references depends on the type
275 // of the FlatNode assignment and the predicates
276 // of the nodes and edges involved.
278 ////////////////////////////////////////////////////
279 public void assignTempToTemp( TempDescriptor src,
280 TempDescriptor dst ) {
281 LabelNode srcln = getLabelNodeFromTemp( src );
282 LabelNode dstln = getLabelNodeFromTemp( dst );
284 clearReferenceEdgesFrom( dstln );
286 HeapRegionNode newReferencee = null;
287 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
288 while( srcRegionsItr.hasNext() ) {
289 Map.Entry me = (Map.Entry) srcRegionsItr.next();
290 newReferencee = (HeapRegionNode) me.getKey();
291 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
293 addReferenceEdge( dstln, newReferencee, rep.copy() );
297 public void assignTempToField( TempDescriptor src,
299 FieldDescriptor fd ) {
300 LabelNode srcln = getLabelNodeFromTemp( src );
301 LabelNode dstln = getLabelNodeFromTemp( dst );
303 clearReferenceEdgesFrom( dstln );
305 HeapRegionNode hrn = null;
306 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
307 while( srcRegionsItr.hasNext() ) {
308 Map.Entry me = (Map.Entry) srcRegionsItr.next();
309 hrn = (HeapRegionNode) me.getKey();
310 ReferenceEdgeProperties rep1 = (ReferenceEdgeProperties) me.getValue();
311 ReachabilitySet beta1 = rep1.getBeta();
313 HeapRegionNode hrnOneHop = null;
314 Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions();
315 while( hrnRegionsItr.hasNext() ) {
316 Map.Entry meH = (Map.Entry) hrnRegionsItr.next();
317 hrnOneHop = (HeapRegionNode) meH.getKey();
318 ReferenceEdgeProperties rep2 = (ReferenceEdgeProperties) meH.getValue();
319 ReachabilitySet beta2 = rep2.getBeta();
321 ReferenceEdgeProperties rep = rep2.copy();
322 rep.setIsInitialParamReflexive( false );
323 rep.setBeta( beta1.intersection( beta2 ) );
325 addReferenceEdge( dstln, hrnOneHop, rep );
330 public void assignFieldToTemp( TempDescriptor src,
332 FieldDescriptor fd ) {
334 // I think my use of src and dst are actually backwards in this method!
335 // acccording to the Reachability Notes, think of dst at N and src as N prime
337 LabelNode srcln = getLabelNodeFromTemp( src );
338 LabelNode dstln = getLabelNodeFromTemp( dst );
340 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
341 HashSet<ReferenceEdgeProperties> edgesWithNewBeta = new HashSet<ReferenceEdgeProperties>();
343 HeapRegionNode hrn = null;
344 ReferenceEdgeProperties rep = null;
345 Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions();
346 while( dstRegionsItr.hasNext() ) {
347 Map.Entry me = (Map.Entry) dstRegionsItr.next();
348 hrn = (HeapRegionNode) me.getKey();
349 rep = (ReferenceEdgeProperties) me.getValue();
351 ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() );
353 HeapRegionNode hrnSrc = null;
354 ReferenceEdgeProperties repSrc = null;
355 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
356 while( srcRegionsItr.hasNext() ) {
357 Map.Entry meS = (Map.Entry) srcRegionsItr.next();
358 hrnSrc = (HeapRegionNode) meS.getKey();
359 repSrc = (ReferenceEdgeProperties) meS.getValue();
361 ReferenceEdgeProperties repNew
362 = new ReferenceEdgeProperties( false, false, null );
364 addReferenceEdge( hrn, hrnSrc, repNew );
366 ReachabilitySet O = srcln.getReferenceTo( hrnSrc ).getBeta();
367 ChangeTupleSet C = O.unionUpArity( R );
368 propagateTokens( hrnSrc, C, nodesWithNewAlpha, edgesWithNewBeta );
372 Iterator nodeItr = nodesWithNewAlpha.iterator();
373 while( nodeItr.hasNext() ) {
374 ((HeapRegionNode) nodeItr.next()).applyAlphaNew();
377 Iterator edgeItr = edgesWithNewBeta.iterator();
378 while( edgeItr.hasNext() ) {
379 ((ReferenceEdgeProperties) edgeItr.next()).applyBetaNew();
383 public void assignTempToParameterAllocation( boolean isTask,
385 Integer paramIndex ) {
388 LabelNode lnParam = getLabelNodeFromTemp( td );
389 HeapRegionNode hrn = createNewHeapRegionNode( null,
396 "param" + paramIndex );
398 // keep track of heap regions that were created for
399 // parameter labels, the index of the parameter they
400 // are for is important when resolving method calls
401 Integer newID = hrn.getID();
402 assert !id2paramIndex.containsKey ( newID );
403 assert !id2paramIndex.containsValue( paramIndex );
404 id2paramIndex.put( newID, paramIndex );
405 paramIndex2id.put( paramIndex, newID );
407 ReachabilitySet beta = new ReachabilitySet( new TokenTuple( newID,
409 TokenTuple.ARITY_ONE ) );
411 // heap regions for parameters are always multiple object (see above)
412 // and have a reference to themselves, because we can't know the
413 // structure of memory that is passed into the method. We're assuming
415 addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( false, false, beta ) );
416 addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( false, true, beta ) );
419 public void assignTempToNewAllocation( TempDescriptor td,
420 AllocationSite as ) {
427 // after the age operation the newest (or zero-ith oldest)
428 // node associated with the allocation site should have
429 // no references to it as if it were a newly allocated
430 // heap region, so make a reference to it to complete
432 Integer idNewest = as.getIthOldest( 0 );
433 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
434 assert hrnNewest != null;
436 LabelNode dst = getLabelNodeFromTemp( td );
438 clearReferenceEdgesFrom( dst );
440 addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false, false, null ) );
444 // use the allocation site (unique to entire analysis) to
445 // locate the heap region nodes in this ownership graph
446 // that should be aged. The process models the allocation
447 // of new objects and collects all the oldest allocations
448 // in a summary node to allow for a finite analysis
450 // There is an additional property of this method. After
451 // running it on a particular ownership graph (many graphs
452 // may have heap regions related to the same allocation site)
453 // the heap region node objects in this ownership graph will be
454 // allocated. Therefore, after aging a graph for an allocation
455 // site, attempts to retrieve the heap region nodes using the
456 // integer id's contained in the allocation site should always
457 // return non-null heap regions.
458 public void age( AllocationSite as ) {
460 // aging adds this allocation site to the graph's
461 // list of sites that exist in the graph, or does
462 // nothing if the site is already in the list
463 allocationSites.add( as );
466 //////////////////////////////////////////////////////////////////
468 // move existing references down the line toward
469 // the oldest element, starting with the oldest
472 // TempDescriptor = the td passed into this function, left side of new statement
473 // AllocationSite = { alpha0, alpha1, alpha2, alphaSummary }
475 // 1. Specially merge refs in/out at alpha2 into alphaSummary
476 // 2. Move refs in/out at alpha1 over to alpha2 (alpha1 becomes alpha2)
477 // 3. Move refs in/out at alpha0 over to alpha1
478 // 4. Assign reference from td to alpha0, which now represents a freshly allocated object
480 //////////////////////////////////////////////////////////////////
483 // first specially merge the references from the oldest
484 // node into the summary node, keeping track of 1-to-1 edges
485 Integer idSummary = as.getSummary();
486 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
488 // if this is null then we haven't touched this allocation site
489 // in the context of the current ownership graph, so simply
490 // allocate an appropriate heap region node
491 // this should only happen once per ownership per allocation site,
492 // and a particular integer id can be used to locate the heap region
493 // in different ownership graphs that represents the same part of an
495 if( hrnSummary == null ) {
497 boolean hasFlags = false;
498 if( as.getType().isClass() ) {
499 hasFlags = as.getType().getClassDesc().hasFlags();
502 hrnSummary = createNewHeapRegionNode( idSummary,
509 as + "\\n" + as.getType() + "\\nsummary" );
511 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
512 Integer idIth = as.getIthOldest( i );
513 assert !id2hrn.containsKey( idIth );
514 createNewHeapRegionNode( idIth,
521 as + "\\n" + as.getType() + "\\n" + i + " oldest" );
525 // first transfer the references out of alpha_k to alpha_s
526 Integer idK = as.getOldest();
527 HeapRegionNode hrnK = id2hrn.get( idK );
529 HeapRegionNode hrnReferencee = null;
530 Iterator itrReferencee = hrnK.setIteratorToReferencedRegions();
531 while( itrReferencee.hasNext() ) {
532 Map.Entry me = (Map.Entry) itrReferencee.next();
533 hrnReferencee = (HeapRegionNode) me.getKey();
534 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
536 // determine if another summary node is already referencing this referencee
537 boolean hasSummaryReferencer = false;
538 OwnershipNode onReferencer = null;
539 Iterator itrReferencer = hrnReferencee.iteratorToReferencers();
540 while( itrReferencer.hasNext() ) {
541 onReferencer = (OwnershipNode) itrReferencer.next();
542 if( onReferencer instanceof HeapRegionNode ) {
543 HeapRegionNode hrnPossibleSummary = (HeapRegionNode) onReferencer;
544 if( hrnPossibleSummary.isNewSummary() ) {
545 hasSummaryReferencer = true;
550 addReferenceEdge( hrnSummary,
552 new ReferenceEdgeProperties( !hasSummaryReferencer ) );
555 // next transfer references to alpha_k over to alpha_s
556 OwnershipNode onReferencer = null;
557 Iterator itrReferencer = hrnK.iteratorToReferencers();
558 while( itrReferencer.hasNext() ) {
559 onReferencer = (OwnershipNode) itrReferencer.next();
561 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnK );
564 addReferenceEdge( onReferencer, hrnSummary, rep.copy() );
568 // then move down the line of heap region nodes
569 // clobbering the ith and transferring all references
570 // to and from i-1 to node i. Note that this clobbers
571 // the oldest node (alpha_k) that was just merged into
572 // the summary above and should move everything from
573 // alpha_0 to alpha_1 before we finish
574 for( int i = allocationDepth - 1; i > 0; --i ) {
576 // move references from the i-1 oldest to the ith oldest
577 Integer idIth = as.getIthOldest( i );
578 HeapRegionNode hrnI = id2hrn.get( idIth );
579 Integer idImin1th = as.getIthOldest( i - 1 );
580 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
582 // clear references in and out of node i
583 clearReferenceEdgesFrom( hrnI );
584 clearReferenceEdgesTo ( hrnI );
586 // copy each edge in and out of i-1 to i
587 hrnReferencee = null;
588 itrReferencee = hrnImin1.setIteratorToReferencedRegions();
589 while( itrReferencee.hasNext() ) {
590 Map.Entry me = (Map.Entry) itrReferencee.next();
591 hrnReferencee = (HeapRegionNode) me.getKey();
592 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
594 addReferenceEdge( hrnI, hrnReferencee, rep.copy() );
598 itrReferencer = hrnImin1.iteratorToReferencers();
599 while( itrReferencer.hasNext() ) {
600 onReferencer = (OwnershipNode) itrReferencer.next();
602 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnImin1 );
605 addReferenceEdge( onReferencer, hrnI, rep.copy() );
609 // as stated above, the newest node alpha_0 should have had its
610 // references moved over to alpha_1, so we can wipe alpha_0 clean
611 // in preparation for operations that want to reference a freshly
612 // allocated object from this allocation site
613 Integer id0th = as.getIthOldest( 0 );
614 HeapRegionNode hrn0 = id2hrn.get( id0th );
616 // the loop to move references from i-1 to i should
617 // have touched this node, therefore assert it is non-null
620 // clear all references in and out of newest node
621 clearReferenceEdgesFrom( hrn0 );
622 clearReferenceEdgesTo ( hrn0 );
627 // the heap regions that are specially allocated as multiple-object
628 // regions for method parameters need to be remembered in order to
629 // resolve a function call. So actually, we need a mapping from
630 // caller argument descriptors to the callee parameter heap regions
631 // to apply reference edges in the callee to the caller graph.
633 // also, Constructors and virtual dispatch methods have a "this"
634 // argument that make the mapping of arguments to parameters a little
635 // tricky. What happens to that this region?
638 public void resolveMethodCall( FlatCall fc,
641 OwnershipGraph ogCallee ) { //,
642 //HashSet<AllocationSite> allocSiteSet ) {
644 // first age all of the allocation sites from
645 // the callee graph in this graph
646 Iterator i = ogCallee.allocationSites.iterator();
647 while( i.hasNext() ) {
648 AllocationSite allocSite = (AllocationSite) i.next();
649 this.age( allocSite );
652 // in non-static methods there is a "this" pointer
653 // that should be taken into account
655 assert fc.numArgs() == fm.numParameters();
657 assert fc.numArgs() + 1 == fm.numParameters();
660 // the heap regions represented by the arguments (caller graph)
661 // and heap regions for the parameters (callee graph)
662 // don't correspond to each other by heap region ID. In fact,
663 // an argument label node can be referencing several heap regions
664 // so the parameter label always references a multiple-object
665 // heap region in order to handle the range of possible contexts
666 // for a method call. This means we need to make a special mapping
667 // of argument->parameter regions in order to update the caller graph
669 // for every heap region->heap region edge in the
670 // callee graph, create the matching edge or edges
671 // in the caller graph
672 Set sCallee = ogCallee.id2hrn.entrySet();
673 Iterator iCallee = sCallee.iterator();
674 while( iCallee.hasNext() ) {
675 Map.Entry meCallee = (Map.Entry) iCallee.next();
676 Integer idCallee = (Integer) meCallee.getKey();
677 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
679 HeapRegionNode hrnChildCallee = null;
680 Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
681 while( heapRegionsItrCallee.hasNext() ) {
682 Map.Entry me = (Map.Entry) heapRegionsItrCallee.next();
683 hrnChildCallee = (HeapRegionNode) me.getKey();
684 ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
686 Integer idChildCallee = hrnChildCallee.getID();
688 // only address this edge if it is not a special reflexive edge
689 if( !repC.isInitialParamReflexive() ) {
691 // now we know that in the callee method's ownership graph
692 // there is a heap region->heap region reference edge given
693 // by heap region pointers:
694 // hrnCallee -> heapChildCallee
696 // or by the ownership-graph independent ID's:
697 // idCallee -> idChildCallee
699 // So now make a set of possible source heaps in the caller graph
700 // and a set of destination heaps in the caller graph, and make
701 // a reference edge in the caller for every possible (src,dst) pair
702 if( !ogCallee.id2hrn.contains( idChildCallee ) ) {
703 //System.out.println( "Houston, we got a problem." );
704 //System.out.println( "idCallee is "+idCallee );
705 //System.out.println( "idChildCallee is "+idChildCallee );
708 writeGraph( "caller", false, false );
709 ogCallee.writeGraph( "callee", false, false );
710 } catch( IOException e ) {}
713 HashSet<HeapRegionNode> possibleCallerSrcs =
714 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
719 HashSet<HeapRegionNode> possibleCallerDsts =
720 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
725 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
726 Iterator srcItr = possibleCallerSrcs.iterator();
727 while( srcItr.hasNext() ) {
728 HeapRegionNode src = (HeapRegionNode) srcItr.next();
730 Iterator dstItr = possibleCallerDsts.iterator();
731 while( dstItr.hasNext() ) {
732 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
734 addReferenceEdge( src, dst, repC.copy() );
742 private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
747 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
749 if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
750 // the heap region that is part of this
751 // reference edge won't have a matching ID in the
752 // caller graph because it is specifically allocated
753 // for a particular parameter. Use that information
754 // to find the corresponding argument label in the
755 // caller in order to create the proper reference edge
757 assert !id2hrn.containsKey( idCallee );
759 Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
760 TempDescriptor argTemp;
762 // now depending on whether the callee is static or not
763 // we need to account for a "this" argument in order to
764 // find the matching argument in the caller context
766 argTemp = fc.getArg( paramIndex );
768 if( paramIndex == 0 ) {
769 argTemp = fc.getThis();
771 argTemp = fc.getArg( paramIndex - 1 );
775 LabelNode argLabel = getLabelNodeFromTemp( argTemp );
776 Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
777 while( argHeapRegionsItr.hasNext() ) {
778 Map.Entry meArg = (Map.Entry) argHeapRegionsItr.next();
779 HeapRegionNode argHeapRegion = (HeapRegionNode) meArg.getKey();
780 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
782 possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
786 // this heap region is not a parameter, so it should
787 // have a matching heap region in the caller graph
788 assert id2hrn.containsKey( idCallee );
789 possibleCallerHRNs.add( id2hrn.get( idCallee ) );
792 return possibleCallerHRNs;
797 ////////////////////////////////////////////////////
798 // in merge() and equals() methods the suffix A
799 // represents the passed in graph and the suffix
800 // B refers to the graph in this object
801 // Merging means to take the incoming graph A and
802 // merge it into B, so after the operation graph B
803 // is the final result.
804 ////////////////////////////////////////////////////
805 public void merge( OwnershipGraph og ) {
811 mergeOwnershipNodes ( og );
812 mergeReferenceEdges ( og );
813 mergeId2paramIndex ( og );
814 mergeAllocationSites( og );
818 protected void mergeOwnershipNodes( OwnershipGraph og ) {
819 Set sA = og.id2hrn.entrySet();
820 Iterator iA = sA.iterator();
821 while( iA.hasNext() ) {
822 Map.Entry meA = (Map.Entry) iA.next();
823 Integer idA = (Integer) meA.getKey();
824 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
826 // if this graph doesn't have a node the
827 // incoming graph has, allocate it
828 if( !id2hrn.containsKey( idA ) ) {
829 HeapRegionNode hrnB = hrnA.copy();
830 id2hrn.put( idA, hrnB );
833 // otherwise this is a node present in both graphs
834 // so make the new reachability set a union of the
835 // nodes' reachability sets
836 HeapRegionNode hrnB = id2hrn.get( idA );
837 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
841 // now add any label nodes that are in graph B but
843 sA = og.td2ln.entrySet();
845 while( iA.hasNext() ) {
846 Map.Entry meA = (Map.Entry) iA.next();
847 TempDescriptor tdA = (TempDescriptor) meA.getKey();
848 LabelNode lnA = (LabelNode) meA.getValue();
850 // if the label doesn't exist in B, allocate and add it
851 LabelNode lnB = getLabelNodeFromTemp( tdA );
855 protected void mergeReferenceEdges( OwnershipGraph og ) {
856 // there is a data structure for storing label nodes
857 // retireved by temp descriptors, and a data structure
858 // for stroing heap region nodes retrieved by integer
859 // ids. Because finding edges requires interacting
860 // with these disparate data structures frequently the
861 // process is nearly duplicated, one for each structure
865 Set sA = og.id2hrn.entrySet();
866 Iterator iA = sA.iterator();
867 while( iA.hasNext() ) {
868 Map.Entry meA = (Map.Entry) iA.next();
869 Integer idA = (Integer) meA.getKey();
870 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
872 HeapRegionNode hrnChildA = null;
873 Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
874 while( heapRegionsItrA.hasNext() ) {
875 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
876 hrnChildA = (HeapRegionNode) me.getKey();
877 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
879 Integer idChildA = hrnChildA.getID();
881 // at this point we know an edge in graph A exists
882 // idA -> idChildA, does this exist in B?
883 boolean edgeFound = false;
884 assert id2hrn.containsKey( idA );
885 HeapRegionNode hrnB = id2hrn.get( idA );
887 HeapRegionNode hrnChildB = null;
888 ReferenceEdgeProperties repB = null;
889 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
890 while( heapRegionsItrB.hasNext() ) {
891 Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
892 hrnChildB = (HeapRegionNode) meC.getKey();
893 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
895 if( hrnChildB.equals( idChildA ) ) {
901 // if the edge from A was not found in B,
904 assert id2hrn.containsKey( idChildA );
905 hrnChildB = id2hrn.get( idChildA );
907 addReferenceEdge( hrnB, hrnChildB, repB );
909 // otherwise, the edge already existed in both graphs
910 // so merge their reachability sets
912 // just replace this beta set with the union
914 repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
919 // and then again with label nodes
920 sA = og.td2ln.entrySet();
922 while( iA.hasNext() ) {
923 Map.Entry meA = (Map.Entry) iA.next();
924 TempDescriptor tdA = (TempDescriptor) meA.getKey();
925 LabelNode lnA = (LabelNode) meA.getValue();
927 HeapRegionNode hrnChildA = null;
928 Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
929 while( heapRegionsItrA.hasNext() ) {
930 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
931 hrnChildA = (HeapRegionNode) meH.getKey();
932 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
934 Integer idChildA = hrnChildA.getID();
936 // at this point we know an edge in graph A exists
937 // tdA -> idChildA, does this exist in B?
938 boolean edgeFound = false;
939 assert td2ln.containsKey( tdA );
940 LabelNode lnB = td2ln.get( tdA );
942 HeapRegionNode hrnChildB = null;
943 ReferenceEdgeProperties repB = null;
944 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
945 while( heapRegionsItrB.hasNext() ) {
946 Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
947 hrnChildB = (HeapRegionNode) meC.getKey();
948 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
950 if( hrnChildB.equals( idChildA ) ) {
956 // if the edge from A was not found in B,
959 assert id2hrn.containsKey( idChildA );
960 hrnChildB = id2hrn.get( idChildA );
962 addReferenceEdge( lnB, hrnChildB, repB );
964 // otherwise, the edge already existed in both graphs
965 // so merge the reachability sets
967 // just replace this beta set with the union
969 repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
975 // you should only merge ownership graphs that have the
976 // same number of parameters, or if one or both parameter
977 // index tables are empty
978 protected void mergeId2paramIndex( OwnershipGraph og ) {
979 if( id2paramIndex.size() == 0 ) {
980 id2paramIndex = og.id2paramIndex;
981 paramIndex2id = og.paramIndex2id;
985 if( og.id2paramIndex.size() == 0 ) {
989 assert id2paramIndex.size() == og.id2paramIndex.size();
992 protected void mergeAllocationSites( OwnershipGraph og ) {
993 allocationSites.addAll( og.allocationSites );
998 // it is necessary in the equals() member functions
999 // to "check both ways" when comparing the data
1000 // structures of two graphs. For instance, if all
1001 // edges between heap region nodes in graph A are
1002 // present and equal in graph B it is not sufficient
1003 // to say the graphs are equal. Consider that there
1004 // may be edges in graph B that are not in graph A.
1005 // the only way to know that all edges in both graphs
1006 // are equally present is to iterate over both data
1007 // structures and compare against the other graph.
1008 public boolean equals( OwnershipGraph og ) {
1014 if( !areHeapRegionNodesEqual( og ) ) {
1018 if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
1022 if( !areLabelNodesEqual( og ) ) {
1026 if( !areLabelToHeapRegionEdgesEqual( og ) ) {
1030 if( !areId2paramIndexEqual( og ) ) {
1034 // if everything is equal up to this point,
1035 // assert that allocationSites is also equal--
1036 // this data is redundant and kept for efficiency
1037 assert allocationSites.equals( og.allocationSites );
1042 protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
1043 // check all nodes in A for presence in graph B
1044 Set sA = og.id2hrn.entrySet();
1045 Iterator iA = sA.iterator();
1046 while( iA.hasNext() ) {
1047 Map.Entry meA = (Map.Entry) iA.next();
1048 Integer idA = (Integer) meA.getKey();
1049 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1051 if( !id2hrn.containsKey( idA ) ) {
1055 //HeapRegionNode hrnB = og.id2hrn.get( idA );
1056 HeapRegionNode hrnB = id2hrn.get( idA );
1057 if( !hrnA.equals( hrnB ) ) {
1062 // then check all nodes in B verses graph A
1063 Set sB = id2hrn.entrySet();
1064 Iterator iB = sB.iterator();
1065 while( iB.hasNext() ) {
1066 Map.Entry meB = (Map.Entry) iB.next();
1067 Integer idB = (Integer) meB.getKey();
1068 HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
1070 if( !og.id2hrn.containsKey( idB ) ) {
1074 // we should have already checked the equality
1075 // of this pairing in the last pass if they both
1076 // exist so assert that they are equal now
1077 HeapRegionNode hrnA = og.id2hrn.get( idB );
1078 assert hrnB.equals( hrnA );
1084 protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
1085 Set sA = og.id2hrn.entrySet();
1086 Iterator iA = sA.iterator();
1087 while( iA.hasNext() ) {
1088 Map.Entry meA = (Map.Entry) iA.next();
1089 Integer idA = (Integer) meA.getKey();
1090 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1092 // we should have already checked that the same
1093 // heap regions exist in both graphs
1094 assert id2hrn.containsKey( idA );
1096 // and are their edges the same? first check every
1097 // edge in A for presence and equality in B
1098 HeapRegionNode hrnChildA = null;
1099 Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1100 while( heapRegionsItrA.hasNext() ) {
1101 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
1102 hrnChildA = (HeapRegionNode) me.getKey();
1103 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1105 Integer idChildA = hrnChildA.getID();
1106 assert id2hrn.containsKey( idChildA );
1108 // at this point we know an edge in graph A exists
1109 // idA -> idChildA, does this edge exist in B?
1110 boolean edgeFound = false;
1111 HeapRegionNode hrnB = id2hrn.get( idA );
1113 HeapRegionNode hrnChildB = null;
1114 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1115 while( heapRegionsItrB.hasNext() ) {
1116 Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
1117 hrnChildB = (HeapRegionNode) meH.getKey();
1118 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1120 if( idChildA.equals( hrnChildB.getID() ) ) {
1121 if( !repA.equals( repB ) ) {
1133 // then check every edge in B for presence in A, starting
1134 // from the same parent HeapRegionNode
1135 HeapRegionNode hrnB = id2hrn.get( idA );
1137 HeapRegionNode hrnChildB = null;
1138 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1139 while( heapRegionsItrB.hasNext() ) {
1140 Map.Entry me = (Map.Entry) heapRegionsItrB.next();
1141 hrnChildB = (HeapRegionNode) me.getKey();
1142 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1144 Integer idChildB = hrnChildB.getID();
1146 // at this point we know an edge in graph B exists
1147 // idB -> idChildB, does this edge exist in A?
1148 boolean edgeFound = false;
1151 heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1152 while( heapRegionsItrA.hasNext() ) {
1153 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
1154 hrnChildA = (HeapRegionNode) meH.getKey();
1155 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1157 if( idChildB.equals( hrnChildA.getID() ) ) {
1158 assert repB.equals( repA );
1172 protected boolean areLabelNodesEqual( OwnershipGraph og ) {
1173 // are all label nodes in A also in graph B?
1174 Set sA = og.td2ln.entrySet();
1175 Iterator iA = sA.iterator();
1176 while( iA.hasNext() ) {
1177 Map.Entry meA = (Map.Entry) iA.next();
1178 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1180 if( !td2ln.containsKey( tdA ) ) {
1185 // are all label nodes in B also in A?
1186 Set sB = td2ln.entrySet();
1187 Iterator iB = sB.iterator();
1188 while( iB.hasNext() ) {
1189 Map.Entry meB = (Map.Entry) iB.next();
1190 TempDescriptor tdB = (TempDescriptor) meB.getKey();
1192 if( !og.td2ln.containsKey( tdB ) ) {
1200 protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
1201 Set sA = og.td2ln.entrySet();
1202 Iterator iA = sA.iterator();
1203 while( iA.hasNext() ) {
1204 Map.Entry meA = (Map.Entry) iA.next();
1205 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1206 LabelNode lnA = (LabelNode) meA.getValue();
1208 // we should have already checked that the same
1209 // label nodes exist in both graphs
1210 assert td2ln.containsKey( tdA );
1212 // and are their edges the same? first check every
1213 // edge in A for presence and equality in B
1214 HeapRegionNode hrnChildA = null;
1215 Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1216 while( heapRegionsItrA.hasNext() ) {
1217 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
1218 hrnChildA = (HeapRegionNode) me.getKey();
1219 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1221 Integer idChildA = hrnChildA.getID();
1222 assert id2hrn.containsKey( idChildA );
1224 // at this point we know an edge in graph A exists
1225 // tdA -> idChildA, does this edge exist in B?
1226 boolean edgeFound = false;
1227 LabelNode lnB = td2ln.get( tdA );
1229 HeapRegionNode hrnChildB = null;
1230 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1231 while( heapRegionsItrB.hasNext() ) {
1232 Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
1233 hrnChildB = (HeapRegionNode) meH.getKey();
1234 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1236 if( idChildA.equals( hrnChildB.getID() ) ) {
1237 if( !repA.equals( repB ) ) {
1249 // then check every edge in B for presence in A, starting
1250 // from the same parent LabelNode
1251 LabelNode lnB = td2ln.get( tdA );
1253 HeapRegionNode hrnChildB = null;
1254 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1255 while( heapRegionsItrB.hasNext() ) {
1256 Map.Entry me = (Map.Entry) heapRegionsItrB.next();
1257 hrnChildB = (HeapRegionNode) me.getKey();
1258 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1260 Integer idChildB = hrnChildB.getID();
1262 // at this point we know an edge in graph B exists
1263 // tdB -> idChildB, does this edge exist in A?
1264 boolean edgeFound = false;
1267 heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1268 while( heapRegionsItrA.hasNext() ) {
1269 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
1270 hrnChildA = (HeapRegionNode) meH.getKey();
1271 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1273 if( idChildB.equals( hrnChildA.getID() ) ) {
1274 assert repB.equals( repA );
1289 protected boolean areId2paramIndexEqual( OwnershipGraph og ) {
1290 return id2paramIndex.size() == og.id2paramIndex.size();
1295 // given a set B of heap region node ID's, return the set of heap
1296 // region node ID's that is reachable from B
1297 public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1299 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1300 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1302 // initial nodes to visit are from set B
1303 Iterator initialItr = idSetB.iterator();
1304 while( initialItr.hasNext() ) {
1305 Integer idInitial = (Integer) initialItr.next();
1306 assert id2hrn.contains( idInitial );
1307 HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1308 toVisit.add( hrnInitial );
1311 HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1313 // do a heap traversal
1314 while( !toVisit.isEmpty() ) {
1315 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1316 toVisit.remove( hrnVisited );
1317 visited.add ( hrnVisited );
1319 // for every node visited, add it to the total
1321 idSetReachableFromB.add( hrnVisited.getID() );
1323 // find other reachable nodes
1324 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1325 while( referenceeItr.hasNext() ) {
1326 Map.Entry me = (Map.Entry) referenceeItr.next();
1327 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1328 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1330 if( !visited.contains( hrnReferencee ) ) {
1331 toVisit.add( hrnReferencee );
1336 return idSetReachableFromB;
1340 // used to find if a heap region can possibly have a reference to
1341 // any of the heap regions in the given set
1342 // if the id supplied is in the set, then a self-referencing edge
1343 // would return true, but that special case is specifically allowed
1344 // meaning that it isn't an external alias
1345 public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1347 assert id2hrn.contains( id );
1348 HeapRegionNode hrn = id2hrn.get( id );
1351 HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1353 Iterator i = idSet.iterator();
1354 while( i.hasNext() ) {
1355 Integer idFromSet = (Integer) i.next();
1356 assert id2hrn.contains( idFromSet );
1357 hrnSet.add( id2hrn.get( idFromSet ) );
1361 // do a traversal from hrn and see if any of the
1362 // heap regions from the set come up during that
1363 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1364 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1367 while( !toVisit.isEmpty() ) {
1368 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1369 toVisit.remove( hrnVisited );
1370 visited.add ( hrnVisited );
1372 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1373 while( referenceeItr.hasNext() ) {
1374 Map.Entry me = (Map.Entry) referenceeItr.next();
1375 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1376 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1378 if( idSet.contains( hrnReferencee.getID() ) ) {
1379 if( !id.equals( hrnReferencee.getID() ) ) {
1384 if( !visited.contains( hrnReferencee ) ) {
1385 toVisit.add( hrnReferencee );
1395 // for writing ownership graphs to dot files
1396 public void writeGraph( Descriptor methodDesc,
1398 boolean writeLabels,
1399 boolean writeReferencers
1400 ) throws java.io.IOException {
1402 methodDesc.getSymbol() +
1403 methodDesc.getNum() +
1410 public void writeGraph( Descriptor methodDesc,
1411 boolean writeLabels,
1412 boolean writeReferencers
1413 ) throws java.io.IOException {
1415 methodDesc.getSymbol() +
1416 methodDesc.getNum() +
1423 public void writeGraph( String graphName,
1424 boolean writeLabels,
1425 boolean writeReferencers
1426 ) throws java.io.IOException {
1428 // remove all non-word characters from the graph name so
1429 // the filename and identifier in dot don't cause errors
1430 graphName = graphName.replaceAll( "[\\W]", "" );
1432 BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
1433 bw.write( "digraph "+graphName+" {\n" );
1434 //bw.write( " size=\"7.5,10\";\n" );
1437 // then visit every heap region node
1438 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1440 Set s = id2hrn.entrySet();
1441 Iterator i = s.iterator();
1442 while( i.hasNext() ) {
1443 Map.Entry me = (Map.Entry) i.next();
1444 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1445 if( !visited.contains( hrn ) ) {
1446 traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1455 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
1458 // then visit every label node, useful for debugging
1460 s = td2ln.entrySet();
1462 while( i.hasNext() ) {
1463 Map.Entry me = (Map.Entry) i.next();
1464 LabelNode ln = (LabelNode) me.getValue();
1466 HeapRegionNode hrn = null;
1467 Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
1468 while( heapRegionsItr.hasNext() ) {
1469 Map.Entry meH = (Map.Entry) heapRegionsItr.next();
1470 hrn = (HeapRegionNode) meH.getKey();
1471 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
1473 bw.write( " " + ln.toString() +
1474 " -> " + hrn.toString() +
1475 "[label=\"" + rep.toEdgeLabelString() +
1486 protected void traverseHeapRegionNodes( int mode,
1490 HashSet<HeapRegionNode> visited,
1491 boolean writeReferencers
1492 ) throws java.io.IOException {
1494 if( visited.contains( hrn ) ) {
1500 case VISIT_HRN_WRITE_FULL:
1502 String attributes = "[";
1504 if( hrn.isSingleObject() ) {
1505 attributes += "shape=box";
1507 attributes += "shape=Msquare";
1510 if( hrn.isFlagged() ) {
1511 attributes += ",style=filled,fillcolor=lightgrey";
1514 attributes += ",label=\"ID" +
1517 hrn.getDescription() +
1519 hrn.getAlphaString() +
1522 bw.write( " " + hrn.toString() + attributes + ";\n" );
1527 // useful for debugging
1528 if( writeReferencers ) {
1529 OwnershipNode onRef = null;
1530 Iterator refItr = hrn.iteratorToReferencers();
1531 while( refItr.hasNext() ) {
1532 onRef = (OwnershipNode) refItr.next();
1535 case VISIT_HRN_WRITE_FULL:
1536 bw.write( " " + hrn.toString() +
1537 " -> " + onRef.toString() +
1538 "[color=lightgray];\n" );
1545 HeapRegionNode hrnChild = null;
1546 Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
1547 while( childRegionsItr.hasNext() ) {
1548 Map.Entry me = (Map.Entry) childRegionsItr.next();
1549 hrnChild = (HeapRegionNode) me.getKey();
1550 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1553 case VISIT_HRN_WRITE_FULL:
1554 bw.write( " " + hrn.toString() +
1555 " -> " + hrnChild.toString() +
1556 "[label=\"" + rep.toEdgeLabelString() +
1561 traverseHeapRegionNodes( mode,