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 );
162 protected void propagateTokens( HeapRegionNode nPrime, ChangeTupleSet c0 ) {
163 HashSet<HeapRegionNode> todoNodes
164 = new HashSet<HeapRegionNode>();
165 todoNodes.add( nPrime );
167 HashSet<ReferenceEdgeProperties> todoEdges
168 = new HashSet<ReferenceEdgeProperties>();
170 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
171 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
172 nodePlannedChanges.put( nPrime, c0 );
174 Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges
175 = new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
177 Hashtable<HeapRegionNode, ChangeTupleSet> nodeChangesMade
178 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
180 Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgeChangesMade
181 = new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
183 while( !todoNodes.isEmpty() ) {
184 HeapRegionNode n = todoNodes.iterator().next();
185 todoNodes.remove( n );
187 if( !nodeChangesMade.containsKey( n ) ) {
188 nodeChangesMade.put( n, new ChangeTupleSet().makeCanonical() );
191 ChangeTupleSet C = nodePlannedChanges.get( n );
193 Iterator itrC = C.iterator();
194 while( itrC.hasNext() ) {
195 ChangeTuple c = (ChangeTuple) itrC.next();
197 if( n.getAlpha().contains( c.getSetToMatch() ) ) {
198 n.setAlphaNew( n.getAlphaNew().union( c.getSetToAdd() ) );
199 nodeChangesMade.put( n, nodeChangesMade.get( n ).union( c ) );
203 ChangeTupleSet Cprime = nodeChangesMade.get( n );
205 Iterator referItr = n.iteratorToReferencers();
206 while( referItr.hasNext() ) {
207 OwnershipNode on = (OwnershipNode) referItr.next();
208 ReferenceEdgeProperties rep = on.getReferenceTo( n );
209 todoEdges.add( rep );
211 if( !edgePlannedChanges.containsKey( rep ) ) {
212 edgePlannedChanges.put( rep, new ChangeTupleSet().makeCanonical() );
215 edgePlannedChanges.put( rep, edgePlannedChanges.get( rep ).union( Cprime ) );
218 HeapRegionNode m = null;
219 ReferenceEdgeProperties f = null;
220 Iterator refeeItr = n.setIteratorToReferencedRegions();
221 while( refeeItr.hasNext() ) {
222 Map.Entry me = (Map.Entry) refeeItr.next();
223 m = (HeapRegionNode) me.getKey();
224 f = (ReferenceEdgeProperties) me.getValue();
226 ChangeTupleSet changesToPass = new ChangeTupleSet();
228 Iterator itrCprime = Cprime.iterator();
229 while( itrCprime.hasNext() ) {
230 ChangeTuple c = (ChangeTuple) itrCprime.next();
231 if( f.getBeta().contains( c.getSetToMatch() ) ) {
232 changesToPass = changesToPass.union( c );
236 if( !changesToPass.isEmpty() ) {
237 if( !nodePlannedChanges.containsKey( m ) ) {
238 nodePlannedChanges.put( m, new ChangeTupleSet().makeCanonical() );
241 ChangeTupleSet currentChanges = nodePlannedChanges.get( m );
243 if( !changesToPass.isSubset( currentChanges ) ) {
245 nodePlannedChanges.put( m, currentChanges.union( changesToPass ) );
254 ////////////////////////////////////////////////////
256 // Assignment Operation Methods
258 // These methods are high-level operations for
259 // modeling program assignment statements using
260 // the low-level reference create/remove methods
263 // The destination in an assignment statement is
264 // going to have new references. The method of
265 // determining the references depends on the type
266 // of the FlatNode assignment and the predicates
267 // of the nodes and edges involved.
269 ////////////////////////////////////////////////////
270 public void assignTempToTemp( TempDescriptor src,
271 TempDescriptor dst ) {
272 LabelNode srcln = getLabelNodeFromTemp( src );
273 LabelNode dstln = getLabelNodeFromTemp( dst );
275 clearReferenceEdgesFrom( dstln );
277 HeapRegionNode newReferencee = null;
278 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
279 while( srcRegionsItr.hasNext() ) {
280 Map.Entry me = (Map.Entry) srcRegionsItr.next();
281 newReferencee = (HeapRegionNode) me.getKey();
282 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
284 addReferenceEdge( dstln, newReferencee, rep.copy() );
288 public void assignTempToField( TempDescriptor src,
290 FieldDescriptor fd ) {
291 LabelNode srcln = getLabelNodeFromTemp( src );
292 LabelNode dstln = getLabelNodeFromTemp( dst );
294 clearReferenceEdgesFrom( dstln );
296 HeapRegionNode hrn = null;
297 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
298 while( srcRegionsItr.hasNext() ) {
299 Map.Entry me = (Map.Entry) srcRegionsItr.next();
300 hrn = (HeapRegionNode) me.getKey();
301 ReferenceEdgeProperties rep1 = (ReferenceEdgeProperties) me.getValue();
302 ReachabilitySet beta1 = rep1.getBeta();
304 HeapRegionNode hrnOneHop = null;
305 Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions();
306 while( hrnRegionsItr.hasNext() ) {
307 Map.Entry meH = (Map.Entry) hrnRegionsItr.next();
308 hrnOneHop = (HeapRegionNode) meH.getKey();
309 ReferenceEdgeProperties rep2 = (ReferenceEdgeProperties) meH.getValue();
310 ReachabilitySet beta2 = rep2.getBeta();
312 ReferenceEdgeProperties rep = rep2.copy();
313 rep.setIsInitialParamReflexive( false );
314 rep.setBeta( beta1.intersection( beta2 ) );
316 addReferenceEdge( dstln, hrnOneHop, rep );
321 public void assignFieldToTemp( TempDescriptor src,
323 FieldDescriptor fd ) {
325 // I think my use of src and dst are actually backwards in this method!
326 // acccording to the Reachability Notes, think of dst at N and src as N prime
328 LabelNode srcln = getLabelNodeFromTemp( src );
329 LabelNode dstln = getLabelNodeFromTemp( dst );
331 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
332 HashSet<ReferenceEdgeProperties> edgesWithNewBeta = new HashSet<ReferenceEdgeProperties>();
334 HeapRegionNode hrn = null;
335 ReferenceEdgeProperties rep = null;
336 Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions();
337 while( dstRegionsItr.hasNext() ) {
338 Map.Entry me = (Map.Entry) dstRegionsItr.next();
339 hrn = (HeapRegionNode) me.getKey();
340 rep = (ReferenceEdgeProperties) me.getValue();
342 ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() );
344 HeapRegionNode hrnSrc = null;
345 ReferenceEdgeProperties repSrc = null;
346 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
347 while( srcRegionsItr.hasNext() ) {
348 Map.Entry meS = (Map.Entry) srcRegionsItr.next();
349 hrnSrc = (HeapRegionNode) meS.getKey();
350 repSrc = (ReferenceEdgeProperties) meS.getValue();
352 ReferenceEdgeProperties repNew
353 = new ReferenceEdgeProperties( false, false, null );
355 addReferenceEdge( hrn, hrnSrc, repNew );
357 ReachabilitySet O = srcln.getReferenceTo( hrnSrc ).getBeta();
358 ChangeTupleSet C = O.unionUpArity( R );
359 propagateTokens( hrnSrc, C );
363 Iterator nodeItr = nodesWithNewAlpha.iterator();
364 while( nodeItr.hasNext() ) {
365 ((HeapRegionNode) nodeItr.next()).applyAlphaNew();
368 Iterator edgeItr = edgesWithNewBeta.iterator();
369 while( edgeItr.hasNext() ) {
370 ((ReferenceEdgeProperties) edgeItr.next()).applyBetaNew();
374 public void assignTempToParameterAllocation( boolean isTask,
376 Integer paramIndex ) {
379 LabelNode lnParam = getLabelNodeFromTemp( td );
380 HeapRegionNode hrn = createNewHeapRegionNode( null,
387 "param" + paramIndex );
389 // keep track of heap regions that were created for
390 // parameter labels, the index of the parameter they
391 // are for is important when resolving method calls
392 Integer newID = hrn.getID();
393 assert !id2paramIndex.containsKey ( newID );
394 assert !id2paramIndex.containsValue( paramIndex );
395 id2paramIndex.put( newID, paramIndex );
396 paramIndex2id.put( paramIndex, newID );
398 ReachabilitySet beta = new ReachabilitySet( new TokenTuple( newID,
400 TokenTuple.ARITY_ONE ) );
402 // heap regions for parameters are always multiple object (see above)
403 // and have a reference to themselves, because we can't know the
404 // structure of memory that is passed into the method. We're assuming
406 addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( false, false, beta ) );
407 addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( false, true, beta ) );
410 public void assignTempToNewAllocation( TempDescriptor td,
411 AllocationSite as ) {
418 // after the age operation the newest (or zero-ith oldest)
419 // node associated with the allocation site should have
420 // no references to it as if it were a newly allocated
421 // heap region, so make a reference to it to complete
423 Integer idNewest = as.getIthOldest( 0 );
424 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
425 assert hrnNewest != null;
427 LabelNode dst = getLabelNodeFromTemp( td );
429 clearReferenceEdgesFrom( dst );
430 addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false ) );
434 // use the allocation site (unique to entire analysis) to
435 // locate the heap region nodes in this ownership graph
436 // that should be aged. The process models the allocation
437 // of new objects and collects all the oldest allocations
438 // in a summary node to allow for a finite analysis
440 // There is an additional property of this method. After
441 // running it on a particular ownership graph (many graphs
442 // may have heap regions related to the same allocation site)
443 // the heap region node objects in this ownership graph will be
444 // allocated. Therefore, after aging a graph for an allocation
445 // site, attempts to retrieve the heap region nodes using the
446 // integer id's contained in the allocation site should always
447 // return non-null heap regions.
448 public void age( AllocationSite as ) {
450 // aging adds this allocation site to the graph's
451 // list of sites that exist in the graph, or does
452 // nothing if the site is already in the list
453 allocationSites.add( as );
456 //////////////////////////////////////////////////////////////////
458 // move existing references down the line toward
459 // the oldest element, starting with the oldest
462 // TempDescriptor = the td passed into this function, left side of new statement
463 // AllocationSite = { alpha0, alpha1, alpha2, alphaSummary }
465 // 1. Specially merge refs in/out at alpha2 into alphaSummary
466 // 2. Move refs in/out at alpha1 over to alpha2 (alpha1 becomes alpha2)
467 // 3. Move refs in/out at alpha0 over to alpha1
468 // 4. Assign reference from td to alpha0, which now represents a freshly allocated object
470 //////////////////////////////////////////////////////////////////
473 // first specially merge the references from the oldest
474 // node into the summary node, keeping track of 1-to-1 edges
475 Integer idSummary = as.getSummary();
476 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
478 // if this is null then we haven't touched this allocation site
479 // in the context of the current ownership graph, so simply
480 // allocate an appropriate heap region node
481 // this should only happen once per ownership per allocation site,
482 // and a particular integer id can be used to locate the heap region
483 // in different ownership graphs that represents the same part of an
485 if( hrnSummary == null ) {
487 boolean hasFlags = false;
488 if( as.getType().isClass() ) {
489 hasFlags = as.getType().getClassDesc().hasFlags();
492 hrnSummary = createNewHeapRegionNode( idSummary,
499 as + "\\n" + as.getType() + "\\nsummary" );
501 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
502 Integer idIth = as.getIthOldest( i );
503 assert !id2hrn.containsKey( idIth );
504 createNewHeapRegionNode( idIth,
511 as + "\\n" + as.getType() + "\\n" + i + " oldest" );
515 // first transfer the references out of alpha_k to alpha_s
516 Integer idK = as.getOldest();
517 HeapRegionNode hrnK = id2hrn.get( idK );
519 HeapRegionNode hrnReferencee = null;
520 Iterator itrReferencee = hrnK.setIteratorToReferencedRegions();
521 while( itrReferencee.hasNext() ) {
522 Map.Entry me = (Map.Entry) itrReferencee.next();
523 hrnReferencee = (HeapRegionNode) me.getKey();
524 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
526 // determine if another summary node is already referencing this referencee
527 boolean hasSummaryReferencer = false;
528 OwnershipNode onReferencer = null;
529 Iterator itrReferencer = hrnReferencee.iteratorToReferencers();
530 while( itrReferencer.hasNext() ) {
531 onReferencer = (OwnershipNode) itrReferencer.next();
532 if( onReferencer instanceof HeapRegionNode ) {
533 HeapRegionNode hrnPossibleSummary = (HeapRegionNode) onReferencer;
534 if( hrnPossibleSummary.isNewSummary() ) {
535 hasSummaryReferencer = true;
540 addReferenceEdge( hrnSummary,
542 new ReferenceEdgeProperties( !hasSummaryReferencer ) );
545 // next transfer references to alpha_k over to alpha_s
546 OwnershipNode onReferencer = null;
547 Iterator itrReferencer = hrnK.iteratorToReferencers();
548 while( itrReferencer.hasNext() ) {
549 onReferencer = (OwnershipNode) itrReferencer.next();
551 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnK );
554 addReferenceEdge( onReferencer, hrnSummary, rep.copy() );
558 // then move down the line of heap region nodes
559 // clobbering the ith and transferring all references
560 // to and from i-1 to node i. Note that this clobbers
561 // the oldest node (alpha_k) that was just merged into
562 // the summary above and should move everything from
563 // alpha_0 to alpha_1 before we finish
564 for( int i = allocationDepth - 1; i > 0; --i ) {
566 // move references from the i-1 oldest to the ith oldest
567 Integer idIth = as.getIthOldest( i );
568 HeapRegionNode hrnI = id2hrn.get( idIth );
569 Integer idImin1th = as.getIthOldest( i - 1 );
570 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
572 // clear references in and out of node i
573 clearReferenceEdgesFrom( hrnI );
574 clearReferenceEdgesTo ( hrnI );
576 // copy each edge in and out of i-1 to i
577 hrnReferencee = null;
578 itrReferencee = hrnImin1.setIteratorToReferencedRegions();
579 while( itrReferencee.hasNext() ) {
580 Map.Entry me = (Map.Entry) itrReferencee.next();
581 hrnReferencee = (HeapRegionNode) me.getKey();
582 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
584 addReferenceEdge( hrnI, hrnReferencee, rep.copy() );
588 itrReferencer = hrnImin1.iteratorToReferencers();
589 while( itrReferencer.hasNext() ) {
590 onReferencer = (OwnershipNode) itrReferencer.next();
592 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnImin1 );
595 addReferenceEdge( onReferencer, hrnI, rep.copy() );
599 // as stated above, the newest node alpha_0 should have had its
600 // references moved over to alpha_1, so we can wipe alpha_0 clean
601 // in preparation for operations that want to reference a freshly
602 // allocated object from this allocation site
603 Integer id0th = as.getIthOldest( 0 );
604 HeapRegionNode hrn0 = id2hrn.get( id0th );
606 // the loop to move references from i-1 to i should
607 // have touched this node, therefore assert it is non-null
610 // clear all references in and out of newest node
611 clearReferenceEdgesFrom( hrn0 );
612 clearReferenceEdgesTo ( hrn0 );
617 // the heap regions that are specially allocated as multiple-object
618 // regions for method parameters need to be remembered in order to
619 // resolve a function call. So actually, we need a mapping from
620 // caller argument descriptors to the callee parameter heap regions
621 // to apply reference edges in the callee to the caller graph.
623 // also, Constructors and virtual dispatch methods have a "this"
624 // argument that make the mapping of arguments to parameters a little
625 // tricky. What happens to that this region?
628 public void resolveMethodCall( FlatCall fc,
631 OwnershipGraph ogCallee ) { //,
632 //HashSet<AllocationSite> allocSiteSet ) {
634 // first age all of the allocation sites from
635 // the callee graph in this graph
636 Iterator i = ogCallee.allocationSites.iterator();
637 while( i.hasNext() ) {
638 AllocationSite allocSite = (AllocationSite) i.next();
639 this.age( allocSite );
642 // in non-static methods there is a "this" pointer
643 // that should be taken into account
645 assert fc.numArgs() == fm.numParameters();
647 assert fc.numArgs() + 1 == fm.numParameters();
650 // the heap regions represented by the arguments (caller graph)
651 // and heap regions for the parameters (callee graph)
652 // don't correspond to each other by heap region ID. In fact,
653 // an argument label node can be referencing several heap regions
654 // so the parameter label always references a multiple-object
655 // heap region in order to handle the range of possible contexts
656 // for a method call. This means we need to make a special mapping
657 // of argument->parameter regions in order to update the caller graph
659 // for every heap region->heap region edge in the
660 // callee graph, create the matching edge or edges
661 // in the caller graph
662 Set sCallee = ogCallee.id2hrn.entrySet();
663 Iterator iCallee = sCallee.iterator();
664 while( iCallee.hasNext() ) {
665 Map.Entry meCallee = (Map.Entry) iCallee.next();
666 Integer idCallee = (Integer) meCallee.getKey();
667 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
669 HeapRegionNode hrnChildCallee = null;
670 Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
671 while( heapRegionsItrCallee.hasNext() ) {
672 Map.Entry me = (Map.Entry) heapRegionsItrCallee.next();
673 hrnChildCallee = (HeapRegionNode) me.getKey();
674 ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
676 Integer idChildCallee = hrnChildCallee.getID();
678 // only address this edge if it is not a special reflexive edge
679 if( !repC.isInitialParamReflexive() ) {
681 // now we know that in the callee method's ownership graph
682 // there is a heap region->heap region reference edge given
683 // by heap region pointers:
684 // hrnCallee -> heapChildCallee
686 // or by the ownership-graph independent ID's:
687 // idCallee -> idChildCallee
689 // So now make a set of possible source heaps in the caller graph
690 // and a set of destination heaps in the caller graph, and make
691 // a reference edge in the caller for every possible (src,dst) pair
692 if( !ogCallee.id2hrn.contains( idChildCallee ) ) {
693 //System.out.println( "Houston, we got a problem." );
694 //System.out.println( "idCallee is "+idCallee );
695 //System.out.println( "idChildCallee is "+idChildCallee );
698 writeGraph( "caller", false, false );
699 ogCallee.writeGraph( "callee", false, false );
700 } catch( IOException e ) {}
703 HashSet<HeapRegionNode> possibleCallerSrcs =
704 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
709 HashSet<HeapRegionNode> possibleCallerDsts =
710 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
715 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
716 Iterator srcItr = possibleCallerSrcs.iterator();
717 while( srcItr.hasNext() ) {
718 HeapRegionNode src = (HeapRegionNode) srcItr.next();
720 Iterator dstItr = possibleCallerDsts.iterator();
721 while( dstItr.hasNext() ) {
722 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
724 addReferenceEdge( src, dst, repC.copy() );
732 private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
737 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
739 if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
740 // the heap region that is part of this
741 // reference edge won't have a matching ID in the
742 // caller graph because it is specifically allocated
743 // for a particular parameter. Use that information
744 // to find the corresponding argument label in the
745 // caller in order to create the proper reference edge
747 assert !id2hrn.containsKey( idCallee );
749 Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
750 TempDescriptor argTemp;
752 // now depending on whether the callee is static or not
753 // we need to account for a "this" argument in order to
754 // find the matching argument in the caller context
756 argTemp = fc.getArg( paramIndex );
758 if( paramIndex == 0 ) {
759 argTemp = fc.getThis();
761 argTemp = fc.getArg( paramIndex - 1 );
765 LabelNode argLabel = getLabelNodeFromTemp( argTemp );
766 Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
767 while( argHeapRegionsItr.hasNext() ) {
768 Map.Entry meArg = (Map.Entry) argHeapRegionsItr.next();
769 HeapRegionNode argHeapRegion = (HeapRegionNode) meArg.getKey();
770 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
772 possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
776 // this heap region is not a parameter, so it should
777 // have a matching heap region in the caller graph
778 assert id2hrn.containsKey( idCallee );
779 possibleCallerHRNs.add( id2hrn.get( idCallee ) );
782 return possibleCallerHRNs;
787 ////////////////////////////////////////////////////
788 // in merge() and equals() methods the suffix A
789 // represents the passed in graph and the suffix
790 // B refers to the graph in this object
791 // Merging means to take the incoming graph A and
792 // merge it into B, so after the operation graph B
793 // is the final result.
794 ////////////////////////////////////////////////////
795 public void merge( OwnershipGraph og ) {
801 mergeOwnershipNodes ( og );
802 mergeReferenceEdges ( og );
803 mergeId2paramIndex ( og );
804 mergeAllocationSites( og );
808 protected void mergeOwnershipNodes( OwnershipGraph og ) {
809 Set sA = og.id2hrn.entrySet();
810 Iterator iA = sA.iterator();
811 while( iA.hasNext() ) {
812 Map.Entry meA = (Map.Entry) iA.next();
813 Integer idA = (Integer) meA.getKey();
814 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
816 // if this graph doesn't have a node the
817 // incoming graph has, allocate it
818 if( !id2hrn.containsKey( idA ) ) {
819 HeapRegionNode hrnB = hrnA.copy();
820 id2hrn.put( idA, hrnB );
823 // otherwise this is a node present in both graphs
824 // so make the new reachability set a union of the
825 // nodes' reachability sets
826 HeapRegionNode hrnB = id2hrn.get( idA );
827 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
831 // now add any label nodes that are in graph B but
833 sA = og.td2ln.entrySet();
835 while( iA.hasNext() ) {
836 Map.Entry meA = (Map.Entry) iA.next();
837 TempDescriptor tdA = (TempDescriptor) meA.getKey();
838 LabelNode lnA = (LabelNode) meA.getValue();
840 // if the label doesn't exist in B, allocate and add it
841 LabelNode lnB = getLabelNodeFromTemp( tdA );
845 protected void mergeReferenceEdges( OwnershipGraph og ) {
846 // there is a data structure for storing label nodes
847 // retireved by temp descriptors, and a data structure
848 // for stroing heap region nodes retrieved by integer
849 // ids. Because finding edges requires interacting
850 // with these disparate data structures frequently the
851 // process is nearly duplicated, one for each structure
855 Set sA = og.id2hrn.entrySet();
856 Iterator iA = sA.iterator();
857 while( iA.hasNext() ) {
858 Map.Entry meA = (Map.Entry) iA.next();
859 Integer idA = (Integer) meA.getKey();
860 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
862 HeapRegionNode hrnChildA = null;
863 Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
864 while( heapRegionsItrA.hasNext() ) {
865 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
866 hrnChildA = (HeapRegionNode) me.getKey();
867 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
869 Integer idChildA = hrnChildA.getID();
871 // at this point we know an edge in graph A exists
872 // idA -> idChildA, does this exist in B?
873 boolean edgeFound = false;
874 assert id2hrn.containsKey( idA );
875 HeapRegionNode hrnB = id2hrn.get( idA );
877 HeapRegionNode hrnChildB = null;
878 ReferenceEdgeProperties repB = null;
879 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
880 while( heapRegionsItrB.hasNext() ) {
881 Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
882 hrnChildB = (HeapRegionNode) meC.getKey();
883 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
885 if( hrnChildB.equals( idChildA ) ) {
891 // if the edge from A was not found in B,
894 assert id2hrn.containsKey( idChildA );
895 hrnChildB = id2hrn.get( idChildA );
897 addReferenceEdge( hrnB, hrnChildB, repB );
899 // otherwise, the edge already existed in both graphs
900 // so merge their reachability sets
902 // just replace this beta set with the union
904 repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
909 // and then again with label nodes
910 sA = og.td2ln.entrySet();
912 while( iA.hasNext() ) {
913 Map.Entry meA = (Map.Entry) iA.next();
914 TempDescriptor tdA = (TempDescriptor) meA.getKey();
915 LabelNode lnA = (LabelNode) meA.getValue();
917 HeapRegionNode hrnChildA = null;
918 Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
919 while( heapRegionsItrA.hasNext() ) {
920 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
921 hrnChildA = (HeapRegionNode) meH.getKey();
922 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
924 Integer idChildA = hrnChildA.getID();
926 // at this point we know an edge in graph A exists
927 // tdA -> idChildA, does this exist in B?
928 boolean edgeFound = false;
929 assert td2ln.containsKey( tdA );
930 LabelNode lnB = td2ln.get( tdA );
932 HeapRegionNode hrnChildB = null;
933 ReferenceEdgeProperties repB = null;
934 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
935 while( heapRegionsItrB.hasNext() ) {
936 Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
937 hrnChildB = (HeapRegionNode) meC.getKey();
938 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
940 if( hrnChildB.equals( idChildA ) ) {
946 // if the edge from A was not found in B,
949 assert id2hrn.containsKey( idChildA );
950 hrnChildB = id2hrn.get( idChildA );
952 addReferenceEdge( lnB, hrnChildB, repB );
954 // otherwise, the edge already existed in both graphs
955 // so merge the reachability sets
957 // just replace this beta set with the union
959 repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
965 // you should only merge ownership graphs that have the
966 // same number of parameters, or if one or both parameter
967 // index tables are empty
968 protected void mergeId2paramIndex( OwnershipGraph og ) {
969 if( id2paramIndex.size() == 0 ) {
970 id2paramIndex = og.id2paramIndex;
971 paramIndex2id = og.paramIndex2id;
975 if( og.id2paramIndex.size() == 0 ) {
979 assert id2paramIndex.size() == og.id2paramIndex.size();
982 protected void mergeAllocationSites( OwnershipGraph og ) {
983 allocationSites.addAll( og.allocationSites );
988 // it is necessary in the equals() member functions
989 // to "check both ways" when comparing the data
990 // structures of two graphs. For instance, if all
991 // edges between heap region nodes in graph A are
992 // present and equal in graph B it is not sufficient
993 // to say the graphs are equal. Consider that there
994 // may be edges in graph B that are not in graph A.
995 // the only way to know that all edges in both graphs
996 // are equally present is to iterate over both data
997 // structures and compare against the other graph.
998 public boolean equals( OwnershipGraph og ) {
1004 if( !areHeapRegionNodesEqual( og ) ) {
1008 if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
1012 if( !areLabelNodesEqual( og ) ) {
1016 if( !areLabelToHeapRegionEdgesEqual( og ) ) {
1020 if( !areId2paramIndexEqual( og ) ) {
1024 // if everything is equal up to this point,
1025 // assert that allocationSites is also equal--
1026 // this data is redundant and kept for efficiency
1027 assert allocationSites.equals( og.allocationSites );
1032 protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
1033 // check all nodes in A for presence in graph B
1034 Set sA = og.id2hrn.entrySet();
1035 Iterator iA = sA.iterator();
1036 while( iA.hasNext() ) {
1037 Map.Entry meA = (Map.Entry) iA.next();
1038 Integer idA = (Integer) meA.getKey();
1039 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1041 if( !id2hrn.containsKey( idA ) ) {
1045 //HeapRegionNode hrnB = og.id2hrn.get( idA );
1046 HeapRegionNode hrnB = id2hrn.get( idA );
1047 if( !hrnA.equals( hrnB ) ) {
1052 // then check all nodes in B verses graph A
1053 Set sB = id2hrn.entrySet();
1054 Iterator iB = sB.iterator();
1055 while( iB.hasNext() ) {
1056 Map.Entry meB = (Map.Entry) iB.next();
1057 Integer idB = (Integer) meB.getKey();
1058 HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
1060 if( !og.id2hrn.containsKey( idB ) ) {
1064 // we should have already checked the equality
1065 // of this pairing in the last pass if they both
1066 // exist so assert that they are equal now
1067 HeapRegionNode hrnA = og.id2hrn.get( idB );
1068 assert hrnB.equals( hrnA );
1074 protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
1075 Set sA = og.id2hrn.entrySet();
1076 Iterator iA = sA.iterator();
1077 while( iA.hasNext() ) {
1078 Map.Entry meA = (Map.Entry) iA.next();
1079 Integer idA = (Integer) meA.getKey();
1080 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1082 // we should have already checked that the same
1083 // heap regions exist in both graphs
1084 assert id2hrn.containsKey( idA );
1086 // and are their edges the same? first check every
1087 // edge in A for presence and equality in B
1088 HeapRegionNode hrnChildA = null;
1089 Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1090 while( heapRegionsItrA.hasNext() ) {
1091 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
1092 hrnChildA = (HeapRegionNode) me.getKey();
1093 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1095 Integer idChildA = hrnChildA.getID();
1096 assert id2hrn.containsKey( idChildA );
1098 // at this point we know an edge in graph A exists
1099 // idA -> idChildA, does this edge exist in B?
1100 boolean edgeFound = false;
1101 HeapRegionNode hrnB = id2hrn.get( idA );
1103 HeapRegionNode hrnChildB = null;
1104 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1105 while( heapRegionsItrB.hasNext() ) {
1106 Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
1107 hrnChildB = (HeapRegionNode) meH.getKey();
1108 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1110 if( idChildA.equals( hrnChildB.getID() ) ) {
1111 if( !repA.equals( repB ) ) {
1123 // then check every edge in B for presence in A, starting
1124 // from the same parent HeapRegionNode
1125 HeapRegionNode hrnB = id2hrn.get( idA );
1127 HeapRegionNode hrnChildB = null;
1128 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1129 while( heapRegionsItrB.hasNext() ) {
1130 Map.Entry me = (Map.Entry) heapRegionsItrB.next();
1131 hrnChildB = (HeapRegionNode) me.getKey();
1132 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1134 Integer idChildB = hrnChildB.getID();
1136 // at this point we know an edge in graph B exists
1137 // idB -> idChildB, does this edge exist in A?
1138 boolean edgeFound = false;
1141 heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1142 while( heapRegionsItrA.hasNext() ) {
1143 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
1144 hrnChildA = (HeapRegionNode) meH.getKey();
1145 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1147 if( idChildB.equals( hrnChildA.getID() ) ) {
1148 assert repB.equals( repA );
1162 protected boolean areLabelNodesEqual( OwnershipGraph og ) {
1163 // are all label nodes in A also in graph B?
1164 Set sA = og.td2ln.entrySet();
1165 Iterator iA = sA.iterator();
1166 while( iA.hasNext() ) {
1167 Map.Entry meA = (Map.Entry) iA.next();
1168 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1170 if( !td2ln.containsKey( tdA ) ) {
1175 // are all label nodes in B also in A?
1176 Set sB = td2ln.entrySet();
1177 Iterator iB = sB.iterator();
1178 while( iB.hasNext() ) {
1179 Map.Entry meB = (Map.Entry) iB.next();
1180 TempDescriptor tdB = (TempDescriptor) meB.getKey();
1182 if( !og.td2ln.containsKey( tdB ) ) {
1190 protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
1191 Set sA = og.td2ln.entrySet();
1192 Iterator iA = sA.iterator();
1193 while( iA.hasNext() ) {
1194 Map.Entry meA = (Map.Entry) iA.next();
1195 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1196 LabelNode lnA = (LabelNode) meA.getValue();
1198 // we should have already checked that the same
1199 // label nodes exist in both graphs
1200 assert td2ln.containsKey( tdA );
1202 // and are their edges the same? first check every
1203 // edge in A for presence and equality in B
1204 HeapRegionNode hrnChildA = null;
1205 Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1206 while( heapRegionsItrA.hasNext() ) {
1207 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
1208 hrnChildA = (HeapRegionNode) me.getKey();
1209 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1211 Integer idChildA = hrnChildA.getID();
1212 assert id2hrn.containsKey( idChildA );
1214 // at this point we know an edge in graph A exists
1215 // tdA -> idChildA, does this edge exist in B?
1216 boolean edgeFound = false;
1217 LabelNode lnB = td2ln.get( tdA );
1219 HeapRegionNode hrnChildB = null;
1220 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1221 while( heapRegionsItrB.hasNext() ) {
1222 Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
1223 hrnChildB = (HeapRegionNode) meH.getKey();
1224 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1226 if( idChildA.equals( hrnChildB.getID() ) ) {
1227 if( !repA.equals( repB ) ) {
1239 // then check every edge in B for presence in A, starting
1240 // from the same parent LabelNode
1241 LabelNode lnB = td2ln.get( tdA );
1243 HeapRegionNode hrnChildB = null;
1244 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1245 while( heapRegionsItrB.hasNext() ) {
1246 Map.Entry me = (Map.Entry) heapRegionsItrB.next();
1247 hrnChildB = (HeapRegionNode) me.getKey();
1248 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1250 Integer idChildB = hrnChildB.getID();
1252 // at this point we know an edge in graph B exists
1253 // tdB -> idChildB, does this edge exist in A?
1254 boolean edgeFound = false;
1257 heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1258 while( heapRegionsItrA.hasNext() ) {
1259 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
1260 hrnChildA = (HeapRegionNode) meH.getKey();
1261 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1263 if( idChildB.equals( hrnChildA.getID() ) ) {
1264 assert repB.equals( repA );
1279 protected boolean areId2paramIndexEqual( OwnershipGraph og ) {
1280 return id2paramIndex.size() == og.id2paramIndex.size();
1285 // given a set B of heap region node ID's, return the set of heap
1286 // region node ID's that is reachable from B
1287 public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1289 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1290 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1292 // initial nodes to visit are from set B
1293 Iterator initialItr = idSetB.iterator();
1294 while( initialItr.hasNext() ) {
1295 Integer idInitial = (Integer) initialItr.next();
1296 assert id2hrn.contains( idInitial );
1297 HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1298 toVisit.add( hrnInitial );
1301 HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1303 // do a heap traversal
1304 while( !toVisit.isEmpty() ) {
1305 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1306 toVisit.remove( hrnVisited );
1307 visited.add ( hrnVisited );
1309 // for every node visited, add it to the total
1311 idSetReachableFromB.add( hrnVisited.getID() );
1313 // find other reachable nodes
1314 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1315 while( referenceeItr.hasNext() ) {
1316 Map.Entry me = (Map.Entry) referenceeItr.next();
1317 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1318 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1320 if( !visited.contains( hrnReferencee ) ) {
1321 toVisit.add( hrnReferencee );
1326 return idSetReachableFromB;
1330 // used to find if a heap region can possibly have a reference to
1331 // any of the heap regions in the given set
1332 // if the id supplied is in the set, then a self-referencing edge
1333 // would return true, but that special case is specifically allowed
1334 // meaning that it isn't an external alias
1335 public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1337 assert id2hrn.contains( id );
1338 HeapRegionNode hrn = id2hrn.get( id );
1341 HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1343 Iterator i = idSet.iterator();
1344 while( i.hasNext() ) {
1345 Integer idFromSet = (Integer) i.next();
1346 assert id2hrn.contains( idFromSet );
1347 hrnSet.add( id2hrn.get( idFromSet ) );
1351 // do a traversal from hrn and see if any of the
1352 // heap regions from the set come up during that
1353 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1354 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1357 while( !toVisit.isEmpty() ) {
1358 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1359 toVisit.remove( hrnVisited );
1360 visited.add ( hrnVisited );
1362 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1363 while( referenceeItr.hasNext() ) {
1364 Map.Entry me = (Map.Entry) referenceeItr.next();
1365 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1366 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1368 if( idSet.contains( hrnReferencee.getID() ) ) {
1369 if( !id.equals( hrnReferencee.getID() ) ) {
1374 if( !visited.contains( hrnReferencee ) ) {
1375 toVisit.add( hrnReferencee );
1385 // for writing ownership graphs to dot files
1386 public void writeGraph( Descriptor methodDesc,
1388 boolean writeLabels,
1389 boolean writeReferencers
1390 ) throws java.io.IOException {
1392 methodDesc.getSymbol() +
1393 methodDesc.getNum() +
1400 public void writeGraph( Descriptor methodDesc,
1401 boolean writeLabels,
1402 boolean writeReferencers
1403 ) throws java.io.IOException {
1405 methodDesc.getSymbol() +
1406 methodDesc.getNum() +
1413 public void writeGraph( String graphName,
1414 boolean writeLabels,
1415 boolean writeReferencers
1416 ) throws java.io.IOException {
1418 // remove all non-word characters from the graph name so
1419 // the filename and identifier in dot don't cause errors
1420 graphName = graphName.replaceAll( "[\\W]", "" );
1422 BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
1423 bw.write( "digraph "+graphName+" {\n" );
1424 //bw.write( " size=\"7.5,10\";\n" );
1427 // then visit every heap region node
1428 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1430 Set s = id2hrn.entrySet();
1431 Iterator i = s.iterator();
1432 while( i.hasNext() ) {
1433 Map.Entry me = (Map.Entry) i.next();
1434 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1435 if( !visited.contains( hrn ) ) {
1436 traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1445 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
1448 // then visit every label node, useful for debugging
1450 s = td2ln.entrySet();
1452 while( i.hasNext() ) {
1453 Map.Entry me = (Map.Entry) i.next();
1454 LabelNode ln = (LabelNode) me.getValue();
1456 HeapRegionNode hrn = null;
1457 Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
1458 while( heapRegionsItr.hasNext() ) {
1459 Map.Entry meH = (Map.Entry) heapRegionsItr.next();
1460 hrn = (HeapRegionNode) meH.getKey();
1461 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
1463 bw.write( " " + ln.toString() +
1464 " -> " + hrn.toString() +
1465 "[label=\"" + rep.toEdgeLabelString() +
1476 protected void traverseHeapRegionNodes( int mode,
1480 HashSet<HeapRegionNode> visited,
1481 boolean writeReferencers
1482 ) throws java.io.IOException {
1484 if( visited.contains( hrn ) ) {
1490 case VISIT_HRN_WRITE_FULL:
1492 String attributes = "[";
1494 if( hrn.isSingleObject() ) {
1495 attributes += "shape=box";
1497 attributes += "shape=Msquare";
1500 if( hrn.isFlagged() ) {
1501 attributes += ",style=filled,fillcolor=lightgrey";
1504 attributes += ",label=\"ID" +
1507 hrn.getDescription() +
1509 hrn.getAlphaString() +
1512 bw.write( " " + hrn.toString() + attributes + ";\n" );
1517 // useful for debugging
1518 if( writeReferencers ) {
1519 OwnershipNode onRef = null;
1520 Iterator refItr = hrn.iteratorToReferencers();
1521 while( refItr.hasNext() ) {
1522 onRef = (OwnershipNode) refItr.next();
1525 case VISIT_HRN_WRITE_FULL:
1526 bw.write( " " + hrn.toString() +
1527 " -> " + onRef.toString() +
1528 "[color=lightgray];\n" );
1535 HeapRegionNode hrnChild = null;
1536 Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
1537 while( childRegionsItr.hasNext() ) {
1538 Map.Entry me = (Map.Entry) childRegionsItr.next();
1539 hrnChild = (HeapRegionNode) me.getKey();
1540 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1543 case VISIT_HRN_WRITE_FULL:
1544 bw.write( " " + hrn.toString() +
1545 " -> " + hrnChild.toString() +
1546 "[label=\"" + rep.toEdgeLabelString() +
1551 traverseHeapRegionNodes( mode,