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;
24 public OwnershipGraph( int allocationDepth ) {
25 this.allocationDepth = allocationDepth;
27 id2hrn = new Hashtable<Integer, HeapRegionNode>();
28 td2ln = new Hashtable<TempDescriptor, LabelNode >();
32 // label nodes are much easier to deal with than
33 // heap region nodes. Whenever there is a request
34 // for the label node that is associated with a
35 // temp descriptor we can either find it or make a
36 // new one and return it. This is because temp
37 // descriptors are globally unique and every label
38 // node is mapped to exactly one temp descriptor.
39 protected LabelNode getLabelNodeFromTemp( TempDescriptor td ) {
42 if( !td2ln.containsKey( td ) ) {
43 td2ln.put( td, new LabelNode( td ) );
46 return td2ln.get( td );
50 // the reason for this method is to have the option
51 // creating new heap regions with specific IDs, or
52 // duplicating heap regions with specific IDs (especially
53 // in the merge() operation) or to create new heap
54 // regions with a new unique ID.
55 protected HeapRegionNode
56 createNewHeapRegionNode( Integer id,
57 boolean isSingleObject,
60 String description ) {
63 id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
66 HeapRegionNode hrn = new HeapRegionNode( id,
71 id2hrn.put( id, hrn );
77 ////////////////////////////////////////////////
79 // Low-level referencee and referencer methods
81 // These methods provide the lowest level for
82 // creating references between ownership nodes
83 // and handling the details of maintaining both
84 // list of referencers and referencees.
86 ////////////////////////////////////////////////
87 protected void addReferenceEdge( OwnershipNode referencer,
88 HeapRegionNode referencee,
89 ReferenceEdgeProperties rep ) {
90 assert referencer != null;
91 assert referencee != null;
92 referencer.addReferencedRegion( referencee, rep );
93 referencee.addReferencer( referencer );
96 protected void removeReferenceEdge( OwnershipNode referencer,
97 HeapRegionNode referencee ) {
98 assert referencer != null;
99 assert referencee != null;
100 assert referencer.getReferenceTo( referencee ) != null;
101 assert referencee.isReferencedBy( referencer );
103 referencer.removeReferencedRegion( referencee );
104 referencee.removeReferencer( referencer );
107 protected void clearReferenceEdgesFrom( OwnershipNode referencer ) {
108 assert referencer != null;
110 // get a copy of the table to iterate over, otherwise
111 // we will be trying to take apart the table as we
112 // are iterating over it, which won't work
113 Iterator i = referencer.setIteratorToReferencedRegionsClone();
114 while( i.hasNext() ) {
115 Map.Entry me = (Map.Entry) i.next();
116 HeapRegionNode referencee = (HeapRegionNode) me.getKey();
117 removeReferenceEdge( referencer, referencee );
121 protected void clearReferenceEdgesTo( HeapRegionNode referencee ) {
122 assert referencee != null;
124 // get a copy of the table to iterate over, otherwise
125 // we will be trying to take apart the table as we
126 // are iterating over it, which won't work
127 Iterator i = referencee.iteratorToReferencersClone();
128 while( i.hasNext() ) {
129 OwnershipNode referencer = (OwnershipNode) i.next();
130 removeReferenceEdge( referencer, referencee );
135 ////////////////////////////////////////////////////
137 // Assignment Operation Methods
139 // These methods are high-level operations for
140 // modeling program assignment statements using
141 // the low-level reference create/remove methods
144 // The destination in an assignment statement is
145 // going to have new references. The method of
146 // determining the references depends on the type
147 // of the FlatNode assignment and the predicates
148 // of the nodes and edges involved.
150 ////////////////////////////////////////////////////
151 public void assignTempToTemp( TempDescriptor src,
152 TempDescriptor dst ) {
153 LabelNode srcln = getLabelNodeFromTemp( src );
154 LabelNode dstln = getLabelNodeFromTemp( dst );
156 clearReferenceEdgesFrom( dstln );
157 HeapRegionNode newReferencee = null;
158 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
159 while( srcRegionsItr.hasNext() ) {
160 Map.Entry me = (Map.Entry) srcRegionsItr.next();
161 newReferencee = (HeapRegionNode) me.getKey();
162 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
164 addReferenceEdge( dstln, newReferencee, rep.copy() );
168 public void assignTempToField( TempDescriptor src,
170 FieldDescriptor fd ) {
171 LabelNode srcln = getLabelNodeFromTemp( src );
172 LabelNode dstln = getLabelNodeFromTemp( dst );
174 clearReferenceEdgesFrom( dstln );
176 HeapRegionNode hrn = null;
177 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
178 while( srcRegionsItr.hasNext() ) {
179 Map.Entry me = (Map.Entry) srcRegionsItr.next();
180 hrn = (HeapRegionNode) me.getKey();
182 HeapRegionNode hrnOneHop = null;
183 Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions();
184 while( hrnRegionsItr.hasNext() ) {
185 Map.Entry meH = (Map.Entry) hrnRegionsItr.next();
186 hrnOneHop = (HeapRegionNode) meH.getKey();
187 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
189 addReferenceEdge( dstln, hrnOneHop, rep.copy() );
194 public void assignFieldToTemp( TempDescriptor src,
196 FieldDescriptor fd ) {
197 LabelNode srcln = getLabelNodeFromTemp( src );
198 LabelNode dstln = getLabelNodeFromTemp( dst );
200 HeapRegionNode hrn = null;
201 Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions();
202 while( dstRegionsItr.hasNext() ) {
203 Map.Entry me = (Map.Entry) dstRegionsItr.next();
204 hrn = (HeapRegionNode) me.getKey();
206 HeapRegionNode hrnSrc = null;
207 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
208 while( srcRegionsItr.hasNext() ) {
209 Map.Entry meS = (Map.Entry) srcRegionsItr.next();
210 hrnSrc = (HeapRegionNode) meS.getKey();
211 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meS.getValue();
213 addReferenceEdge( hrn, hrnSrc, rep.copy() );
218 public void assignTempToParameterAllocation( boolean isTask,
219 TempDescriptor td ) {
222 LabelNode lnParam = getLabelNodeFromTemp( td );
223 HeapRegionNode hrn = createNewHeapRegionNode( null,
229 addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( false ) );
230 addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( false ) );
233 public void assignTempToNewAllocation( TempDescriptor td,
234 AllocationSite as ) {
240 // after the age operation the newest (or zero-ith oldest)
241 // node associated with the allocation site should have
242 // no references to it as if it were a newly allocated
243 // heap region, so make a reference to it to complete
245 Integer id = as.getIthOldest( 0 );
246 HeapRegionNode hrnNewest = id2hrn.get( id );
247 assert hrnNewest != null;
249 LabelNode dst = getLabelNodeFromTemp( td );
251 addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false ) );
255 // use the allocation site (unique to entire analysis) to
256 // locate the heap region nodes in this ownership graph
257 // that should be aged. The process models the allocation
258 // of new objects and collects all the oldest allocations
259 // in a summary node to allow for a finite analysis
261 // There is an additional property of this method. After
262 // running it on a particular ownership graph (many graphs
263 // may have heap regions related to the same allocation site)
264 // the heap region node objects in this ownership graph will be
265 // allocated. Therefore, after aging a graph for an allocation
266 // site, attempts to retrieve the heap region nodes using the
267 // integer id's contained in the allocation site should always
268 // return non-null heap regions.
269 public void age( AllocationSite as ) {
271 //////////////////////////////////////////////////////////////////
273 // move existing references down the line toward
274 // the oldest element, starting with the oldest
277 // TempDescriptor = the td passed into this function, left side of new statement
278 // AllocationSite = { alpha0, alpha1, alpha2, alphaSummary }
280 // 1. Specially merge refs in/out at alpha2 into alphaSummary
281 // 2. Move refs in/out at alpha1 over to alpha2 (alpha1 becomes alpha2)
282 // 3. Move refs in/out at alpha0 over to alpha1
283 // 4. Assign reference from td to alpha0, which now represents a freshly allocated object
285 //////////////////////////////////////////////////////////////////
288 // first specially merge the references from the oldest
289 // node into the summary node, keeping track of 1-to-1 edges
290 Integer idSummary = as.getSummary();
291 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
293 // if this is null then we haven't touched this allocation site
294 // in the context of the current ownership graph, so simply
295 // allocate an appropriate heap region node
296 // this should only happen once per ownership per allocation site,
297 // and a particular integer id can be used to locate the heap region
298 // in different ownership graphs that represents the same part of an
300 if( hrnSummary == null ) {
301 hrnSummary = createNewHeapRegionNode( idSummary,
308 // first transfer the references out of alpha_k to alpha_s
309 Integer idK = as.getOldest();
310 HeapRegionNode hrnK = id2hrn.get( idK );
312 // see comment above about needing to allocate a heap region
313 // for the context of this ownership graph
315 hrnK = createNewHeapRegionNode( idK,
322 HeapRegionNode hrnReferencee = null;
323 Iterator itrReferencee = hrnK.setIteratorToReferencedRegions();
324 while( itrReferencee.hasNext() ) {
325 Map.Entry me = (Map.Entry) itrReferencee.next();
326 hrnReferencee = (HeapRegionNode) me.getKey();
327 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
329 // determine if another summary node is already referencing this referencee
330 boolean hasSummaryReferencer = false;
331 OwnershipNode onReferencer = null;
332 Iterator itrReferencer = hrnReferencee.iteratorToReferencers();
333 while( itrReferencer.hasNext() ) {
334 onReferencer = (OwnershipNode) itrReferencer.next();
335 if( onReferencer instanceof HeapRegionNode ) {
336 HeapRegionNode hrnPossibleSummary = (HeapRegionNode) onReferencer;
337 if( hrnPossibleSummary.isNewSummary() ) {
338 hasSummaryReferencer = true;
343 addReferenceEdge( hrnSummary,
345 new ReferenceEdgeProperties( !hasSummaryReferencer ) );
348 // next transfer references to alpha_k over to alpha_s
349 OwnershipNode onReferencer = null;
350 Iterator itrReferencer = hrnK.iteratorToReferencers();
351 while( itrReferencer.hasNext() ) {
352 onReferencer = (OwnershipNode) itrReferencer.next();
354 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnK );
357 addReferenceEdge( onReferencer, hrnSummary, rep.copy() );
361 // then move down the line of heap region nodes
362 // clobbering the ith and transferring all references
363 // to and from i-1 to node i. Note that this clobbers
364 // the oldest node (alpha_k) that was just merged into
365 // the summary above and should move everything from
366 // alpha_0 to alpha_1 before we finish
367 for( int i = allocationDepth - 1; i > 0; --i ) {
369 // move references from the ith oldest to the i+1 oldest
370 Integer idIth = as.getIthOldest( i );
371 HeapRegionNode hrnI = id2hrn.get( idIth );
372 Integer idImin1th = as.getIthOldest( i - 1 );
373 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
375 // see comment above about needing to allocate a heap region
376 // for the context of this ownership graph
378 hrnI = createNewHeapRegionNode( idIth,
382 as + "\\n" + Integer.toString( i ) + "th" );
384 if( hrnImin1 == null ) {
385 hrnImin1 = createNewHeapRegionNode( idImin1th,
389 as + "\\n" + Integer.toString( i-1 ) + "th" );
392 // clear references in and out of node i
393 clearReferenceEdgesFrom( hrnI );
394 clearReferenceEdgesTo ( hrnI );
396 // copy each edge in and out of i-1 to i
397 hrnReferencee = null;
398 itrReferencee = hrnImin1.setIteratorToReferencedRegions();
399 while( itrReferencee.hasNext() ) {
400 Map.Entry me = (Map.Entry) itrReferencee.next();
401 hrnReferencee = (HeapRegionNode) me.getKey();
402 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
404 addReferenceEdge( hrnI, hrnReferencee, rep.copy() );
408 itrReferencer = hrnImin1.iteratorToReferencers();
409 while( itrReferencer.hasNext() ) {
410 onReferencer = (OwnershipNode) itrReferencer.next();
412 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnImin1 );
415 addReferenceEdge( onReferencer, hrnI, rep.copy() );
419 // as stated above, the newest node alpha_0 should have had its
420 // references moved over to alpha_1, so we can wipe alpha_0 clean
421 // in preparation for operations that want to reference a freshly
422 // allocated object from this allocation site
423 Integer id0th = as.getIthOldest( 0 );
424 HeapRegionNode hrn0 = id2hrn.get( id0th );
426 // the loop to move references from i-1 to i should
427 // have touched this node, therefore assert it is non-null
430 // clear all references in and out of newest node
431 clearReferenceEdgesFrom( hrn0 );
432 clearReferenceEdgesTo ( hrn0 );
437 ////////////////////////////////////////////////////
438 // in merge() and equals() methods the suffix A
439 // represents the passed in graph and the suffix
440 // B refers to the graph in this object
441 ////////////////////////////////////////////////////
443 public void merge( OwnershipGraph og ) {
449 mergeOwnershipNodes ( og );
450 mergeReferenceEdges ( og );
453 protected void mergeOwnershipNodes( OwnershipGraph og ) {
454 Set sA = og.id2hrn.entrySet();
455 Iterator iA = sA.iterator();
456 while( iA.hasNext() ) {
457 Map.Entry meA = (Map.Entry) iA.next();
458 Integer idA = (Integer) meA.getKey();
459 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
461 // if this graph doesn't have a node the
462 // incoming graph has, allocate it
463 if( !id2hrn.containsKey( idA ) ) {
464 HeapRegionNode hrnB = hrnA.copy();
465 id2hrn.put( idA, hrnB );
469 // now add any label nodes that are in graph B but
471 sA = og.td2ln.entrySet();
473 while( iA.hasNext() ) {
474 Map.Entry meA = (Map.Entry) iA.next();
475 TempDescriptor tdA = (TempDescriptor) meA.getKey();
476 LabelNode lnA = (LabelNode) meA.getValue();
478 // if the label doesn't exist in B, allocate and add it
479 LabelNode lnB = getLabelNodeFromTemp( tdA );
483 protected void mergeReferenceEdges( OwnershipGraph og ) {
484 // there is a data structure for storing label nodes
485 // retireved by temp descriptors, and a data structure
486 // for stroing heap region nodes retrieved by integer
487 // ids. Because finding edges requires interacting
488 // with these disparate data structures frequently the
489 // process is nearly duplicated, one for each
492 Set sA = og.id2hrn.entrySet();
493 Iterator iA = sA.iterator();
494 while( iA.hasNext() ) {
495 Map.Entry meA = (Map.Entry) iA.next();
496 Integer idA = (Integer) meA.getKey();
497 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
499 HeapRegionNode hrnChildA = null;
500 Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
501 while( heapRegionsItrA.hasNext() ) {
502 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
503 hrnChildA = (HeapRegionNode) me.getKey();
504 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
506 Integer idChildA = hrnChildA.getID();
508 // at this point we know an edge in graph A exists
509 // idA -> idChildA, does this exist in B?
510 boolean edgeFound = false;
511 assert id2hrn.containsKey( idA );
512 HeapRegionNode hrnB = id2hrn.get( idA );
514 HeapRegionNode hrnChildB = null;
515 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
516 while( heapRegionsItrB.hasNext() ) {
517 Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
518 hrnChildB = (HeapRegionNode) meC.getKey();
520 if( hrnChildB.equals( idChildA ) ) {
525 // if the edge from A was not found in B,
528 assert id2hrn.containsKey( idChildA );
529 hrnChildB = id2hrn.get( idChildA );
530 ReferenceEdgeProperties repB = repA.copy();
531 addReferenceEdge( hrnB, hrnChildB, repB );
533 // otherwise, the edge already existed in both graphs.
534 // if this is the case, check to see whether the isUnique
535 // predicate of the edges might change
543 // and then again with label nodes
544 sA = og.td2ln.entrySet();
546 while( iA.hasNext() ) {
547 Map.Entry meA = (Map.Entry) iA.next();
548 TempDescriptor tdA = (TempDescriptor) meA.getKey();
549 LabelNode lnA = (LabelNode) meA.getValue();
551 HeapRegionNode hrnChildA = null;
552 Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
553 while( heapRegionsItrA.hasNext() ) {
554 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
555 hrnChildA = (HeapRegionNode) meH.getKey();
556 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
558 Integer idChildA = hrnChildA.getID();
560 // at this point we know an edge in graph A exists
561 // tdA -> idChildA, does this exist in B?
562 boolean edgeFound = false;
563 assert td2ln.containsKey( tdA );
564 LabelNode lnB = td2ln.get( tdA );
566 HeapRegionNode hrnChildB = null;
567 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
568 while( heapRegionsItrB.hasNext() ) {
569 Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
570 hrnChildB = (HeapRegionNode) meC.getKey();
572 if( hrnChildB.equals( idChildA ) ) {
577 // if the edge from A was not found in B,
580 assert id2hrn.containsKey( idChildA );
581 hrnChildB = id2hrn.get( idChildA );
582 ReferenceEdgeProperties repB = repA.copy();
583 addReferenceEdge( lnB, hrnChildB, repB );
585 // otherwise, the edge already existed in both graphs.
586 // if this is the case, check to see whether the isUnique
587 // predicate of the edges might change
597 // it is necessary in the equals() member functions
598 // to "check both ways" when comparing the data
599 // structures of two graphs. For instance, if all
600 // edges between heap region nodes in graph A are
601 // present and equal in graph B it is not sufficient
602 // to say the graphs are equal. Consider that there
603 // may be edges in graph B that are not in graph A.
604 // the only way to know that all edges in both graphs
605 // are equally present is to iterate over both data
606 // structures and compare against the other graph.
607 public boolean equals( OwnershipGraph og ) {
613 if( !areHeapRegionNodesEqual( og ) ) {
617 if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
621 if( !areLabelNodesEqual( og ) ) {
625 if( !areLabelToHeapRegionEdgesEqual( og ) ) {
632 protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
633 // check all nodes in A for presence in graph B
634 Set sA = og.id2hrn.entrySet();
635 Iterator iA = sA.iterator();
636 while( iA.hasNext() ) {
637 Map.Entry meA = (Map.Entry) iA.next();
638 Integer idA = (Integer) meA.getKey();
639 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
641 if( !id2hrn.containsKey( idA ) ) {
645 HeapRegionNode hrnB = og.id2hrn.get( idA );
646 if( !hrnA.equals( hrnB ) ) {
651 // then check all nodes in B verses graph A
652 Set sB = id2hrn.entrySet();
653 Iterator iB = sB.iterator();
654 while( iB.hasNext() ) {
655 Map.Entry meB = (Map.Entry) iB.next();
656 Integer idB = (Integer) meB.getKey();
657 HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
659 if( !og.id2hrn.containsKey( idB ) ) {
663 // we should have already checked the equality
664 // of this pairing in the last pass if they both
665 // exist so assert that they are equal now
666 HeapRegionNode hrnA = og.id2hrn.get( idB );
667 assert hrnB.equals( hrnA );
673 protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
674 Set sA = og.id2hrn.entrySet();
675 Iterator iA = sA.iterator();
676 while( iA.hasNext() ) {
677 Map.Entry meA = (Map.Entry) iA.next();
678 Integer idA = (Integer) meA.getKey();
679 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
681 // we should have already checked that the same
682 // heap regions exist in both graphs
683 assert id2hrn.containsKey( idA );
685 // and are their edges the same? first check every
686 // edge in A for presence and equality in B
687 HeapRegionNode hrnChildA = null;
688 Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
689 while( heapRegionsItrA.hasNext() ) {
690 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
691 hrnChildA = (HeapRegionNode) me.getKey();
692 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
694 Integer idChildA = hrnChildA.getID();
695 assert id2hrn.containsKey( idChildA );
697 // at this point we know an edge in graph A exists
698 // idA -> idChildA, does this edge exist in B?
699 boolean edgeFound = false;
700 HeapRegionNode hrnB = id2hrn.get( idA );
702 HeapRegionNode hrnChildB = null;
703 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
704 while( heapRegionsItrB.hasNext() ) {
705 Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
706 hrnChildB = (HeapRegionNode) meH.getKey();
707 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
709 if( idChildA.equals( hrnChildB.getID() ) ) {
710 if( !repA.equals( repB ) ) {
722 // then check every edge in B for presence in A, starting
723 // from the same parent HeapRegionNode
724 HeapRegionNode hrnB = id2hrn.get( idA );
726 HeapRegionNode hrnChildB = null;
727 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
728 while( heapRegionsItrB.hasNext() ) {
729 Map.Entry me = (Map.Entry) heapRegionsItrB.next();
730 hrnChildB = (HeapRegionNode) me.getKey();
731 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
733 Integer idChildB = hrnChildB.getID();
735 // at this point we know an edge in graph B exists
736 // idB -> idChildB, does this edge exist in A?
737 boolean edgeFound = false;
740 heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
741 while( heapRegionsItrA.hasNext() ) {
742 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
743 hrnChildA = (HeapRegionNode) meH.getKey();
744 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
746 if( idChildB.equals( hrnChildA.getID() ) ) {
747 assert repB.equals( repA );
761 protected boolean areLabelNodesEqual( OwnershipGraph og ) {
762 // are all label nodes in A also in graph B?
763 Set sA = og.td2ln.entrySet();
764 Iterator iA = sA.iterator();
765 while( iA.hasNext() ) {
766 Map.Entry meA = (Map.Entry) iA.next();
767 TempDescriptor tdA = (TempDescriptor) meA.getKey();
769 if( !td2ln.containsKey( tdA ) ) {
774 // are all label nodes in B also in A?
775 Set sB = td2ln.entrySet();
776 Iterator iB = sB.iterator();
777 while( iB.hasNext() ) {
778 Map.Entry meB = (Map.Entry) iB.next();
779 TempDescriptor tdB = (TempDescriptor) meB.getKey();
781 if( !og.td2ln.containsKey( tdB ) ) {
789 protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
790 Set sA = og.td2ln.entrySet();
791 Iterator iA = sA.iterator();
792 while( iA.hasNext() ) {
793 Map.Entry meA = (Map.Entry) iA.next();
794 TempDescriptor tdA = (TempDescriptor) meA.getKey();
795 LabelNode lnA = (LabelNode) meA.getValue();
797 // we should have already checked that the same
798 // label nodes exist in both graphs
799 assert td2ln.containsKey( tdA );
801 // and are their edges the same? first check every
802 // edge in A for presence and equality in B
803 HeapRegionNode hrnChildA = null;
804 Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
805 while( heapRegionsItrA.hasNext() ) {
806 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
807 hrnChildA = (HeapRegionNode) me.getKey();
808 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
810 Integer idChildA = hrnChildA.getID();
811 assert id2hrn.containsKey( idChildA );
813 // at this point we know an edge in graph A exists
814 // tdA -> idChildA, does this edge exist in B?
815 boolean edgeFound = false;
816 LabelNode lnB = td2ln.get( tdA );
818 HeapRegionNode hrnChildB = null;
819 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
820 while( heapRegionsItrB.hasNext() ) {
821 Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
822 hrnChildB = (HeapRegionNode) meH.getKey();
823 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
825 if( idChildA.equals( hrnChildB.getID() ) ) {
826 if( !repA.equals( repB ) ) {
838 // then check every edge in B for presence in A, starting
839 // from the same parent LabelNode
840 LabelNode lnB = td2ln.get( tdA );
842 HeapRegionNode hrnChildB = null;
843 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
844 while( heapRegionsItrB.hasNext() ) {
845 Map.Entry me = (Map.Entry) heapRegionsItrB.next();
846 hrnChildB = (HeapRegionNode) me.getKey();
847 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
849 Integer idChildB = hrnChildB.getID();
851 // at this point we know an edge in graph B exists
852 // tdB -> idChildB, does this edge exist in A?
853 boolean edgeFound = false;
856 heapRegionsItrA = lnA.setIteratorToReferencedRegions();
857 while( heapRegionsItrA.hasNext() ) {
858 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
859 hrnChildA = (HeapRegionNode) meH.getKey();
860 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
862 if( idChildB.equals( hrnChildA.getID() ) ) {
863 assert repB.equals( repA );
879 // use this method to determine if two temp descriptors can possibly
880 // access the same heap regions, which means there is a possible alias
881 public boolean havePossibleAlias( TempDescriptor td1,
882 TempDescriptor td2 ) {
890 // for writing ownership graphs to dot files
891 public void writeGraph( Descriptor methodDesc,
892 FlatNode fn ) throws java.io.IOException {
894 methodDesc.getSymbol() +
895 methodDesc.getNum() +
900 public void writeGraph( Descriptor methodDesc ) throws java.io.IOException {
902 methodDesc.getSymbol() +
903 methodDesc.getNum() +
908 private void writeGraph( String graphName ) throws java.io.IOException {
909 // remove all non-word characters from the graph name so
910 // the filename and identifier in dot don't cause errors
911 graphName = graphName.replaceAll( "[\\W]", "" );
913 BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
914 bw.write( "digraph "+graphName+" {\n" );
916 // then visit every heap region node
917 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
919 Set s = id2hrn.entrySet();
920 Iterator i = s.iterator();
921 while( i.hasNext() ) {
922 Map.Entry me = (Map.Entry) i.next();
923 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
924 if( !visited.contains( hrn ) ) {
925 traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL, hrn, bw, null, visited );
929 // then visit every label node
930 s = td2ln.entrySet();
932 while( i.hasNext() ) {
933 Map.Entry me = (Map.Entry) i.next();
934 LabelNode ln = (LabelNode) me.getValue();
936 HeapRegionNode hrn = null;
937 Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
938 while( heapRegionsItr.hasNext() ) {
939 Map.Entry meH = (Map.Entry) heapRegionsItr.next();
940 hrn = (HeapRegionNode) meH.getKey();
941 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
943 String edgeLabel = "";
944 if( rep.isUnique() ) {
945 edgeLabel = "Unique";
947 bw.write( " " + ln.toString() +
948 " -> " + hrn.toString() +
949 "[label=\"" + edgeLabel +
958 protected void traverseHeapRegionNodes( int mode,
962 HashSet<HeapRegionNode> visited
963 ) throws java.io.IOException {
965 if( visited.contains( hrn ) ) {
971 case VISIT_HRN_WRITE_FULL:
973 String attributes = "[";
975 if( hrn.isSingleObject() ) {
976 attributes += "shape=box";
978 attributes += "shape=Msquare";
981 if( hrn.isFlagged() ) {
982 attributes += ",style=filled,fillcolor=lightgrey";
985 attributes += ",label=\"" +
986 hrn.getDescription() +
989 bw.write( " " + hrn.toString() + attributes + ";\n" );
994 // go back and let a compile flag control whether the light
995 // gray "referencer" edges are written to dot files. It makes
996 // the graph cluttered but can be useful for debugging.
998 OwnershipNode onRef = null;
999 Iterator refItr = hrn.iteratorToReferencers();
1000 while( refItr.hasNext() ) {
1001 onRef = (OwnershipNode) refItr.next();
1004 case VISIT_HRN_WRITE_FULL:
1005 bw.write( " " + hrn.toString() +
1006 " -> " + onRef.toString() +
1007 "[color=lightgray];\n" );
1013 HeapRegionNode hrnChild = null;
1014 Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
1015 while( childRegionsItr.hasNext() ) {
1016 Map.Entry me = (Map.Entry) childRegionsItr.next();
1017 hrnChild = (HeapRegionNode) me.getKey();
1018 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1021 case VISIT_HRN_WRITE_FULL:
1022 String edgeLabel = "";
1023 if( rep.isUnique() ) {
1024 edgeLabel = "Unique";
1026 bw.write( " " + hrn.toString() +
1027 " -> " + hrnChild.toString() +
1028 "[label=\"" + edgeLabel +
1033 traverseHeapRegionNodes( mode, hrnChild, bw, td, visited );