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 );
120 protected void removeReferenceEdge( OwnershipNode referencer,
121 HeapRegionNode referencee ) {
122 assert referencer != null;
123 assert referencee != null;
124 assert referencer.getReferenceTo( referencee ) != null;
125 assert referencee.isReferencedBy( referencer );
127 referencer.removeReferencedRegion( referencee );
128 referencee.removeReferencer( referencer );
131 protected void clearReferenceEdgesFrom( OwnershipNode referencer ) {
132 assert referencer != null;
134 // get a copy of the table to iterate over, otherwise
135 // we will be trying to take apart the table as we
136 // are iterating over it, which won't work
137 Iterator i = referencer.setIteratorToReferencedRegionsClone();
138 while( i.hasNext() ) {
139 Map.Entry me = (Map.Entry) i.next();
140 HeapRegionNode referencee = (HeapRegionNode) me.getKey();
141 removeReferenceEdge( referencer, referencee );
145 protected void clearReferenceEdgesTo( HeapRegionNode referencee ) {
146 assert referencee != null;
148 // get a copy of the table to iterate over, otherwise
149 // we will be trying to take apart the table as we
150 // are iterating over it, which won't work
151 Iterator i = referencee.iteratorToReferencersClone();
152 while( i.hasNext() ) {
153 OwnershipNode referencer = (OwnershipNode) i.next();
154 removeReferenceEdge( referencer, referencee );
159 ////////////////////////////////////////////////////
161 // Assignment Operation Methods
163 // These methods are high-level operations for
164 // modeling program assignment statements using
165 // the low-level reference create/remove methods
168 // The destination in an assignment statement is
169 // going to have new references. The method of
170 // determining the references depends on the type
171 // of the FlatNode assignment and the predicates
172 // of the nodes and edges involved.
174 ////////////////////////////////////////////////////
175 public void assignTempToTemp( TempDescriptor src,
176 TempDescriptor dst ) {
177 LabelNode srcln = getLabelNodeFromTemp( src );
178 LabelNode dstln = getLabelNodeFromTemp( dst );
180 clearReferenceEdgesFrom( dstln );
182 HeapRegionNode newReferencee = null;
183 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
184 while( srcRegionsItr.hasNext() ) {
185 Map.Entry me = (Map.Entry) srcRegionsItr.next();
186 newReferencee = (HeapRegionNode) me.getKey();
187 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
189 addReferenceEdge( dstln, newReferencee, rep.copy() );
193 public void assignTempToField( TempDescriptor src,
195 FieldDescriptor fd ) {
196 LabelNode srcln = getLabelNodeFromTemp( src );
197 LabelNode dstln = getLabelNodeFromTemp( dst );
199 clearReferenceEdgesFrom( dstln );
201 HeapRegionNode hrn = null;
202 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
203 while( srcRegionsItr.hasNext() ) {
204 Map.Entry me = (Map.Entry) srcRegionsItr.next();
205 hrn = (HeapRegionNode) me.getKey();
206 ReferenceEdgeProperties rep1 = (ReferenceEdgeProperties) me.getValue();
207 ReachabilitySet beta1 = rep1.getBeta();
209 HeapRegionNode hrnOneHop = null;
210 Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions();
211 while( hrnRegionsItr.hasNext() ) {
212 Map.Entry meH = (Map.Entry) hrnRegionsItr.next();
213 hrnOneHop = (HeapRegionNode) meH.getKey();
214 ReferenceEdgeProperties rep2 = (ReferenceEdgeProperties) meH.getValue();
215 ReachabilitySet beta2 = rep2.getBeta();
217 ReferenceEdgeProperties rep = rep2.copy();
218 rep.setBeta( beta1.intersection( beta2 ) );
220 addReferenceEdge( dstln, hrnOneHop, rep );
225 public void assignFieldToTemp( TempDescriptor src,
227 FieldDescriptor fd ) {
228 LabelNode srcln = getLabelNodeFromTemp( src );
229 LabelNode dstln = getLabelNodeFromTemp( dst );
231 HeapRegionNode hrn = null;
232 Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions();
233 while( dstRegionsItr.hasNext() ) {
234 Map.Entry me = (Map.Entry) dstRegionsItr.next();
235 hrn = (HeapRegionNode) me.getKey();
237 HeapRegionNode hrnSrc = null;
238 Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
239 while( srcRegionsItr.hasNext() ) {
240 Map.Entry meS = (Map.Entry) srcRegionsItr.next();
241 hrnSrc = (HeapRegionNode) meS.getKey();
243 ReferenceEdgeProperties rep = new ReferenceEdgeProperties();
244 addReferenceEdge( hrn, hrnSrc, rep );
249 public void assignTempToParameterAllocation( boolean isTask,
251 Integer paramIndex ) {
254 LabelNode lnParam = getLabelNodeFromTemp( td );
255 HeapRegionNode hrn = createNewHeapRegionNode( null,
262 "param" + paramIndex );
264 // keep track of heap regions that were created for
265 // parameter labels, the index of the parameter they
266 // are for is important when resolving method calls
267 Integer newID = hrn.getID();
268 assert !id2paramIndex.containsKey ( newID );
269 assert !id2paramIndex.containsValue( paramIndex );
270 id2paramIndex.put( newID, paramIndex );
271 paramIndex2id.put( paramIndex, newID );
273 ReachabilitySet beta = new ReachabilitySet( new TokenTuple( newID,
275 TokenTuple.ARITY_ONE ) );
277 // heap regions for parameters are always multiple object (see above)
278 // and have a reference to themselves, because we can't know the
279 // structure of memory that is passed into the method. We're assuming
281 addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( false, false, beta ) );
282 addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( false, true, beta ) );
285 public void assignTempToNewAllocation( TempDescriptor td,
286 AllocationSite as ) {
293 // after the age operation the newest (or zero-ith oldest)
294 // node associated with the allocation site should have
295 // no references to it as if it were a newly allocated
296 // heap region, so make a reference to it to complete
298 Integer idNewest = as.getIthOldest( 0 );
299 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
300 assert hrnNewest != null;
302 LabelNode dst = getLabelNodeFromTemp( td );
304 clearReferenceEdgesFrom( dst );
305 addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false ) );
309 // use the allocation site (unique to entire analysis) to
310 // locate the heap region nodes in this ownership graph
311 // that should be aged. The process models the allocation
312 // of new objects and collects all the oldest allocations
313 // in a summary node to allow for a finite analysis
315 // There is an additional property of this method. After
316 // running it on a particular ownership graph (many graphs
317 // may have heap regions related to the same allocation site)
318 // the heap region node objects in this ownership graph will be
319 // allocated. Therefore, after aging a graph for an allocation
320 // site, attempts to retrieve the heap region nodes using the
321 // integer id's contained in the allocation site should always
322 // return non-null heap regions.
323 public void age( AllocationSite as ) {
325 // aging adds this allocation site to the graph's
326 // list of sites that exist in the graph, or does
327 // nothing if the site is already in the list
328 allocationSites.add( as );
331 //////////////////////////////////////////////////////////////////
333 // move existing references down the line toward
334 // the oldest element, starting with the oldest
337 // TempDescriptor = the td passed into this function, left side of new statement
338 // AllocationSite = { alpha0, alpha1, alpha2, alphaSummary }
340 // 1. Specially merge refs in/out at alpha2 into alphaSummary
341 // 2. Move refs in/out at alpha1 over to alpha2 (alpha1 becomes alpha2)
342 // 3. Move refs in/out at alpha0 over to alpha1
343 // 4. Assign reference from td to alpha0, which now represents a freshly allocated object
345 //////////////////////////////////////////////////////////////////
348 // first specially merge the references from the oldest
349 // node into the summary node, keeping track of 1-to-1 edges
350 Integer idSummary = as.getSummary();
351 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
353 // if this is null then we haven't touched this allocation site
354 // in the context of the current ownership graph, so simply
355 // allocate an appropriate heap region node
356 // this should only happen once per ownership per allocation site,
357 // and a particular integer id can be used to locate the heap region
358 // in different ownership graphs that represents the same part of an
360 if( hrnSummary == null ) {
362 boolean hasFlags = false;
363 if( as.getType().isClass() ) {
364 hasFlags = as.getType().getClassDesc().hasFlags();
367 hrnSummary = createNewHeapRegionNode( idSummary,
374 as + "\\n" + as.getType() + "\\nsummary" );
376 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
377 Integer idIth = as.getIthOldest( i );
378 assert !id2hrn.containsKey( idIth );
379 createNewHeapRegionNode( idIth,
386 as + "\\n" + as.getType() + "\\n" + i + " oldest" );
390 // first transfer the references out of alpha_k to alpha_s
391 Integer idK = as.getOldest();
392 HeapRegionNode hrnK = id2hrn.get( idK );
394 HeapRegionNode hrnReferencee = null;
395 Iterator itrReferencee = hrnK.setIteratorToReferencedRegions();
396 while( itrReferencee.hasNext() ) {
397 Map.Entry me = (Map.Entry) itrReferencee.next();
398 hrnReferencee = (HeapRegionNode) me.getKey();
399 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
401 // determine if another summary node is already referencing this referencee
402 boolean hasSummaryReferencer = false;
403 OwnershipNode onReferencer = null;
404 Iterator itrReferencer = hrnReferencee.iteratorToReferencers();
405 while( itrReferencer.hasNext() ) {
406 onReferencer = (OwnershipNode) itrReferencer.next();
407 if( onReferencer instanceof HeapRegionNode ) {
408 HeapRegionNode hrnPossibleSummary = (HeapRegionNode) onReferencer;
409 if( hrnPossibleSummary.isNewSummary() ) {
410 hasSummaryReferencer = true;
415 addReferenceEdge( hrnSummary,
417 new ReferenceEdgeProperties( !hasSummaryReferencer ) );
420 // next transfer references to alpha_k over to alpha_s
421 OwnershipNode onReferencer = null;
422 Iterator itrReferencer = hrnK.iteratorToReferencers();
423 while( itrReferencer.hasNext() ) {
424 onReferencer = (OwnershipNode) itrReferencer.next();
426 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnK );
429 addReferenceEdge( onReferencer, hrnSummary, rep.copy() );
433 // then move down the line of heap region nodes
434 // clobbering the ith and transferring all references
435 // to and from i-1 to node i. Note that this clobbers
436 // the oldest node (alpha_k) that was just merged into
437 // the summary above and should move everything from
438 // alpha_0 to alpha_1 before we finish
439 for( int i = allocationDepth - 1; i > 0; --i ) {
441 // move references from the i-1 oldest to the ith oldest
442 Integer idIth = as.getIthOldest( i );
443 HeapRegionNode hrnI = id2hrn.get( idIth );
444 Integer idImin1th = as.getIthOldest( i - 1 );
445 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
447 // clear references in and out of node i
448 clearReferenceEdgesFrom( hrnI );
449 clearReferenceEdgesTo ( hrnI );
451 // copy each edge in and out of i-1 to i
452 hrnReferencee = null;
453 itrReferencee = hrnImin1.setIteratorToReferencedRegions();
454 while( itrReferencee.hasNext() ) {
455 Map.Entry me = (Map.Entry) itrReferencee.next();
456 hrnReferencee = (HeapRegionNode) me.getKey();
457 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
459 addReferenceEdge( hrnI, hrnReferencee, rep.copy() );
463 itrReferencer = hrnImin1.iteratorToReferencers();
464 while( itrReferencer.hasNext() ) {
465 onReferencer = (OwnershipNode) itrReferencer.next();
467 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnImin1 );
470 addReferenceEdge( onReferencer, hrnI, rep.copy() );
474 // as stated above, the newest node alpha_0 should have had its
475 // references moved over to alpha_1, so we can wipe alpha_0 clean
476 // in preparation for operations that want to reference a freshly
477 // allocated object from this allocation site
478 Integer id0th = as.getIthOldest( 0 );
479 HeapRegionNode hrn0 = id2hrn.get( id0th );
481 // the loop to move references from i-1 to i should
482 // have touched this node, therefore assert it is non-null
485 // clear all references in and out of newest node
486 clearReferenceEdgesFrom( hrn0 );
487 clearReferenceEdgesTo ( hrn0 );
492 // the heap regions that are specially allocated as multiple-object
493 // regions for method parameters need to be remembered in order to
494 // resolve a function call. So actually, we need a mapping from
495 // caller argument descriptors to the callee parameter heap regions
496 // to apply reference edges in the callee to the caller graph.
498 // also, Constructors and virtual dispatch methods have a "this"
499 // argument that make the mapping of arguments to parameters a little
500 // tricky. What happens to that this region?
503 public void resolveMethodCall( FlatCall fc,
506 OwnershipGraph ogCallee ) { //,
507 //HashSet<AllocationSite> allocSiteSet ) {
509 // first age all of the allocation sites from
510 // the callee graph in this graph
511 Iterator i = ogCallee.allocationSites.iterator();
512 while( i.hasNext() ) {
513 AllocationSite allocSite = (AllocationSite) i.next();
514 this.age( allocSite );
517 // in non-static methods there is a "this" pointer
518 // that should be taken into account
520 assert fc.numArgs() == fm.numParameters();
522 assert fc.numArgs() + 1 == fm.numParameters();
525 // the heap regions represented by the arguments (caller graph)
526 // and heap regions for the parameters (callee graph)
527 // don't correspond to each other by heap region ID. In fact,
528 // an argument label node can be referencing several heap regions
529 // so the parameter label always references a multiple-object
530 // heap region in order to handle the range of possible contexts
531 // for a method call. This means we need to make a special mapping
532 // of argument->parameter regions in order to update the caller graph
534 // for every heap region->heap region edge in the
535 // callee graph, create the matching edge or edges
536 // in the caller graph
537 Set sCallee = ogCallee.id2hrn.entrySet();
538 Iterator iCallee = sCallee.iterator();
539 while( iCallee.hasNext() ) {
540 Map.Entry meCallee = (Map.Entry) iCallee.next();
541 Integer idCallee = (Integer) meCallee.getKey();
542 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
544 HeapRegionNode hrnChildCallee = null;
545 Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
546 while( heapRegionsItrCallee.hasNext() ) {
547 Map.Entry me = (Map.Entry) heapRegionsItrCallee.next();
548 hrnChildCallee = (HeapRegionNode) me.getKey();
549 ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
551 Integer idChildCallee = hrnChildCallee.getID();
553 // only address this edge if it is not a special reflexive edge
554 if( !repC.isInitialParamReflexive() ) {
556 // now we know that in the callee method's ownership graph
557 // there is a heap region->heap region reference edge given
558 // by heap region pointers:
559 // hrnCallee -> heapChildCallee
561 // or by the ownership-graph independent ID's:
562 // idCallee -> idChildCallee
564 // So now make a set of possible source heaps in the caller graph
565 // and a set of destination heaps in the caller graph, and make
566 // a reference edge in the caller for every possible (src,dst) pair
567 if( !ogCallee.id2hrn.contains( idChildCallee ) ) {
568 //System.out.println( "Houston, we got a problem." );
569 //System.out.println( "idCallee is "+idCallee );
570 //System.out.println( "idChildCallee is "+idChildCallee );
573 writeGraph( "caller", false, false );
574 ogCallee.writeGraph( "callee", false, false );
575 } catch( IOException e ) {}
578 HashSet<HeapRegionNode> possibleCallerSrcs =
579 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
584 HashSet<HeapRegionNode> possibleCallerDsts =
585 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
590 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
591 Iterator srcItr = possibleCallerSrcs.iterator();
592 while( srcItr.hasNext() ) {
593 HeapRegionNode src = (HeapRegionNode) srcItr.next();
595 Iterator dstItr = possibleCallerDsts.iterator();
596 while( dstItr.hasNext() ) {
597 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
599 addReferenceEdge( src, dst, repC.copy() );
607 private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
612 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
614 if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
615 // the heap region that is part of this
616 // reference edge won't have a matching ID in the
617 // caller graph because it is specifically allocated
618 // for a particular parameter. Use that information
619 // to find the corresponding argument label in the
620 // caller in order to create the proper reference edge
622 assert !id2hrn.containsKey( idCallee );
624 Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
625 TempDescriptor argTemp;
627 // now depending on whether the callee is static or not
628 // we need to account for a "this" argument in order to
629 // find the matching argument in the caller context
631 argTemp = fc.getArg( paramIndex );
633 if( paramIndex == 0 ) {
634 argTemp = fc.getThis();
636 argTemp = fc.getArg( paramIndex - 1 );
640 LabelNode argLabel = getLabelNodeFromTemp( argTemp );
641 Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
642 while( argHeapRegionsItr.hasNext() ) {
643 Map.Entry meArg = (Map.Entry) argHeapRegionsItr.next();
644 HeapRegionNode argHeapRegion = (HeapRegionNode) meArg.getKey();
645 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
647 possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
651 // this heap region is not a parameter, so it should
652 // have a matching heap region in the caller graph
653 assert id2hrn.containsKey( idCallee );
654 possibleCallerHRNs.add( id2hrn.get( idCallee ) );
657 return possibleCallerHRNs;
662 ////////////////////////////////////////////////////
663 // in merge() and equals() methods the suffix A
664 // represents the passed in graph and the suffix
665 // B refers to the graph in this object
666 // Merging means to take the incoming graph A and
667 // merge it into B, so after the operation graph B
668 // is the final result.
669 ////////////////////////////////////////////////////
670 public void merge( OwnershipGraph og ) {
676 mergeOwnershipNodes ( og );
677 mergeReferenceEdges ( og );
678 mergeId2paramIndex ( og );
679 mergeAllocationSites( og );
683 protected void mergeOwnershipNodes( OwnershipGraph og ) {
684 Set sA = og.id2hrn.entrySet();
685 Iterator iA = sA.iterator();
686 while( iA.hasNext() ) {
687 Map.Entry meA = (Map.Entry) iA.next();
688 Integer idA = (Integer) meA.getKey();
689 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
691 // if this graph doesn't have a node the
692 // incoming graph has, allocate it
693 if( !id2hrn.containsKey( idA ) ) {
694 HeapRegionNode hrnB = hrnA.copy();
695 id2hrn.put( idA, hrnB );
698 // otherwise this is a node present in both graphs
699 // so make the new reachability set a union of the
700 // nodes' reachability sets
701 HeapRegionNode hrnB = id2hrn.get( idA );
702 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
706 // now add any label nodes that are in graph B but
708 sA = og.td2ln.entrySet();
710 while( iA.hasNext() ) {
711 Map.Entry meA = (Map.Entry) iA.next();
712 TempDescriptor tdA = (TempDescriptor) meA.getKey();
713 LabelNode lnA = (LabelNode) meA.getValue();
715 // if the label doesn't exist in B, allocate and add it
716 LabelNode lnB = getLabelNodeFromTemp( tdA );
720 protected void mergeReferenceEdges( OwnershipGraph og ) {
721 // there is a data structure for storing label nodes
722 // retireved by temp descriptors, and a data structure
723 // for stroing heap region nodes retrieved by integer
724 // ids. Because finding edges requires interacting
725 // with these disparate data structures frequently the
726 // process is nearly duplicated, one for each structure
730 Set sA = og.id2hrn.entrySet();
731 Iterator iA = sA.iterator();
732 while( iA.hasNext() ) {
733 Map.Entry meA = (Map.Entry) iA.next();
734 Integer idA = (Integer) meA.getKey();
735 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
737 HeapRegionNode hrnChildA = null;
738 Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
739 while( heapRegionsItrA.hasNext() ) {
740 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
741 hrnChildA = (HeapRegionNode) me.getKey();
742 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
744 Integer idChildA = hrnChildA.getID();
746 // at this point we know an edge in graph A exists
747 // idA -> idChildA, does this exist in B?
748 boolean edgeFound = false;
749 assert id2hrn.containsKey( idA );
750 HeapRegionNode hrnB = id2hrn.get( idA );
752 HeapRegionNode hrnChildB = null;
753 ReferenceEdgeProperties repB = null;
754 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
755 while( heapRegionsItrB.hasNext() ) {
756 Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
757 hrnChildB = (HeapRegionNode) meC.getKey();
758 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
760 if( hrnChildB.equals( idChildA ) ) {
766 // if the edge from A was not found in B,
769 assert id2hrn.containsKey( idChildA );
770 hrnChildB = id2hrn.get( idChildA );
772 addReferenceEdge( hrnB, hrnChildB, repB );
774 // otherwise, the edge already existed in both graphs
775 // so merge their reachability sets
777 // just replace this beta set with the union
779 repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
784 // and then again with label nodes
785 sA = og.td2ln.entrySet();
787 while( iA.hasNext() ) {
788 Map.Entry meA = (Map.Entry) iA.next();
789 TempDescriptor tdA = (TempDescriptor) meA.getKey();
790 LabelNode lnA = (LabelNode) meA.getValue();
792 HeapRegionNode hrnChildA = null;
793 Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
794 while( heapRegionsItrA.hasNext() ) {
795 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
796 hrnChildA = (HeapRegionNode) meH.getKey();
797 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
799 Integer idChildA = hrnChildA.getID();
801 // at this point we know an edge in graph A exists
802 // tdA -> idChildA, does this exist in B?
803 boolean edgeFound = false;
804 assert td2ln.containsKey( tdA );
805 LabelNode lnB = td2ln.get( tdA );
807 HeapRegionNode hrnChildB = null;
808 ReferenceEdgeProperties repB = null;
809 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
810 while( heapRegionsItrB.hasNext() ) {
811 Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
812 hrnChildB = (HeapRegionNode) meC.getKey();
813 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
815 if( hrnChildB.equals( idChildA ) ) {
821 // if the edge from A was not found in B,
824 assert id2hrn.containsKey( idChildA );
825 hrnChildB = id2hrn.get( idChildA );
827 addReferenceEdge( lnB, hrnChildB, repB );
829 // otherwise, the edge already existed in both graphs
830 // so merge the reachability sets
832 // just replace this beta set with the union
834 repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
840 // you should only merge ownership graphs that have the
841 // same number of parameters, or if one or both parameter
842 // index tables are empty
843 protected void mergeId2paramIndex( OwnershipGraph og ) {
844 if( id2paramIndex.size() == 0 ) {
845 id2paramIndex = og.id2paramIndex;
846 paramIndex2id = og.paramIndex2id;
850 if( og.id2paramIndex.size() == 0 ) {
854 assert id2paramIndex.size() == og.id2paramIndex.size();
857 protected void mergeAllocationSites( OwnershipGraph og ) {
858 allocationSites.addAll( og.allocationSites );
863 // it is necessary in the equals() member functions
864 // to "check both ways" when comparing the data
865 // structures of two graphs. For instance, if all
866 // edges between heap region nodes in graph A are
867 // present and equal in graph B it is not sufficient
868 // to say the graphs are equal. Consider that there
869 // may be edges in graph B that are not in graph A.
870 // the only way to know that all edges in both graphs
871 // are equally present is to iterate over both data
872 // structures and compare against the other graph.
873 public boolean equals( OwnershipGraph og ) {
879 if( !areHeapRegionNodesEqual( og ) ) {
883 if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
887 if( !areLabelNodesEqual( og ) ) {
891 if( !areLabelToHeapRegionEdgesEqual( og ) ) {
895 if( !areId2paramIndexEqual( og ) ) {
899 // if everything is equal up to this point,
900 // assert that allocationSites is also equal--
901 // this data is redundant and kept for efficiency
902 assert allocationSites.equals( og.allocationSites );
907 protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
908 // check all nodes in A for presence in graph B
909 Set sA = og.id2hrn.entrySet();
910 Iterator iA = sA.iterator();
911 while( iA.hasNext() ) {
912 Map.Entry meA = (Map.Entry) iA.next();
913 Integer idA = (Integer) meA.getKey();
914 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
916 if( !id2hrn.containsKey( idA ) ) {
920 //HeapRegionNode hrnB = og.id2hrn.get( idA );
921 HeapRegionNode hrnB = id2hrn.get( idA );
922 if( !hrnA.equals( hrnB ) ) {
927 // then check all nodes in B verses graph A
928 Set sB = id2hrn.entrySet();
929 Iterator iB = sB.iterator();
930 while( iB.hasNext() ) {
931 Map.Entry meB = (Map.Entry) iB.next();
932 Integer idB = (Integer) meB.getKey();
933 HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
935 if( !og.id2hrn.containsKey( idB ) ) {
939 // we should have already checked the equality
940 // of this pairing in the last pass if they both
941 // exist so assert that they are equal now
942 HeapRegionNode hrnA = og.id2hrn.get( idB );
943 assert hrnB.equals( hrnA );
949 protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
950 Set sA = og.id2hrn.entrySet();
951 Iterator iA = sA.iterator();
952 while( iA.hasNext() ) {
953 Map.Entry meA = (Map.Entry) iA.next();
954 Integer idA = (Integer) meA.getKey();
955 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
957 // we should have already checked that the same
958 // heap regions exist in both graphs
959 assert id2hrn.containsKey( idA );
961 // and are their edges the same? first check every
962 // edge in A for presence and equality in B
963 HeapRegionNode hrnChildA = null;
964 Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
965 while( heapRegionsItrA.hasNext() ) {
966 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
967 hrnChildA = (HeapRegionNode) me.getKey();
968 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
970 Integer idChildA = hrnChildA.getID();
971 assert id2hrn.containsKey( idChildA );
973 // at this point we know an edge in graph A exists
974 // idA -> idChildA, does this edge exist in B?
975 boolean edgeFound = false;
976 HeapRegionNode hrnB = id2hrn.get( idA );
978 HeapRegionNode hrnChildB = null;
979 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
980 while( heapRegionsItrB.hasNext() ) {
981 Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
982 hrnChildB = (HeapRegionNode) meH.getKey();
983 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
985 if( idChildA.equals( hrnChildB.getID() ) ) {
986 if( !repA.equals( repB ) ) {
998 // then check every edge in B for presence in A, starting
999 // from the same parent HeapRegionNode
1000 HeapRegionNode hrnB = id2hrn.get( idA );
1002 HeapRegionNode hrnChildB = null;
1003 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1004 while( heapRegionsItrB.hasNext() ) {
1005 Map.Entry me = (Map.Entry) heapRegionsItrB.next();
1006 hrnChildB = (HeapRegionNode) me.getKey();
1007 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1009 Integer idChildB = hrnChildB.getID();
1011 // at this point we know an edge in graph B exists
1012 // idB -> idChildB, does this edge exist in A?
1013 boolean edgeFound = false;
1016 heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1017 while( heapRegionsItrA.hasNext() ) {
1018 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
1019 hrnChildA = (HeapRegionNode) meH.getKey();
1020 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1022 if( idChildB.equals( hrnChildA.getID() ) ) {
1023 assert repB.equals( repA );
1037 protected boolean areLabelNodesEqual( OwnershipGraph og ) {
1038 // are all label nodes in A also in graph B?
1039 Set sA = og.td2ln.entrySet();
1040 Iterator iA = sA.iterator();
1041 while( iA.hasNext() ) {
1042 Map.Entry meA = (Map.Entry) iA.next();
1043 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1045 if( !td2ln.containsKey( tdA ) ) {
1050 // are all label nodes in B also in A?
1051 Set sB = td2ln.entrySet();
1052 Iterator iB = sB.iterator();
1053 while( iB.hasNext() ) {
1054 Map.Entry meB = (Map.Entry) iB.next();
1055 TempDescriptor tdB = (TempDescriptor) meB.getKey();
1057 if( !og.td2ln.containsKey( tdB ) ) {
1065 protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
1066 Set sA = og.td2ln.entrySet();
1067 Iterator iA = sA.iterator();
1068 while( iA.hasNext() ) {
1069 Map.Entry meA = (Map.Entry) iA.next();
1070 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1071 LabelNode lnA = (LabelNode) meA.getValue();
1073 // we should have already checked that the same
1074 // label nodes exist in both graphs
1075 assert td2ln.containsKey( tdA );
1077 // and are their edges the same? first check every
1078 // edge in A for presence and equality in B
1079 HeapRegionNode hrnChildA = null;
1080 Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1081 while( heapRegionsItrA.hasNext() ) {
1082 Map.Entry me = (Map.Entry) heapRegionsItrA.next();
1083 hrnChildA = (HeapRegionNode) me.getKey();
1084 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1086 Integer idChildA = hrnChildA.getID();
1087 assert id2hrn.containsKey( idChildA );
1089 // at this point we know an edge in graph A exists
1090 // tdA -> idChildA, does this edge exist in B?
1091 boolean edgeFound = false;
1092 LabelNode lnB = td2ln.get( tdA );
1094 HeapRegionNode hrnChildB = null;
1095 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1096 while( heapRegionsItrB.hasNext() ) {
1097 Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
1098 hrnChildB = (HeapRegionNode) meH.getKey();
1099 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1101 if( idChildA.equals( hrnChildB.getID() ) ) {
1102 if( !repA.equals( repB ) ) {
1114 // then check every edge in B for presence in A, starting
1115 // from the same parent LabelNode
1116 LabelNode lnB = td2ln.get( tdA );
1118 HeapRegionNode hrnChildB = null;
1119 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1120 while( heapRegionsItrB.hasNext() ) {
1121 Map.Entry me = (Map.Entry) heapRegionsItrB.next();
1122 hrnChildB = (HeapRegionNode) me.getKey();
1123 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1125 Integer idChildB = hrnChildB.getID();
1127 // at this point we know an edge in graph B exists
1128 // tdB -> idChildB, does this edge exist in A?
1129 boolean edgeFound = false;
1132 heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1133 while( heapRegionsItrA.hasNext() ) {
1134 Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
1135 hrnChildA = (HeapRegionNode) meH.getKey();
1136 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1138 if( idChildB.equals( hrnChildA.getID() ) ) {
1139 assert repB.equals( repA );
1154 protected boolean areId2paramIndexEqual( OwnershipGraph og ) {
1155 return id2paramIndex.size() == og.id2paramIndex.size();
1160 // given a set B of heap region node ID's, return the set of heap
1161 // region node ID's that is reachable from B
1162 public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1164 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1165 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1167 // initial nodes to visit are from set B
1168 Iterator initialItr = idSetB.iterator();
1169 while( initialItr.hasNext() ) {
1170 Integer idInitial = (Integer) initialItr.next();
1171 assert id2hrn.contains( idInitial );
1172 HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1173 toVisit.add( hrnInitial );
1176 HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1178 // do a heap traversal
1179 while( !toVisit.isEmpty() ) {
1180 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1181 toVisit.remove( hrnVisited );
1182 visited.add ( hrnVisited );
1184 // for every node visited, add it to the total
1186 idSetReachableFromB.add( hrnVisited.getID() );
1188 // find other reachable nodes
1189 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1190 while( referenceeItr.hasNext() ) {
1191 Map.Entry me = (Map.Entry) referenceeItr.next();
1192 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1193 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1195 if( !visited.contains( hrnReferencee ) ) {
1196 toVisit.add( hrnReferencee );
1201 return idSetReachableFromB;
1205 // used to find if a heap region can possibly have a reference to
1206 // any of the heap regions in the given set
1207 // if the id supplied is in the set, then a self-referencing edge
1208 // would return true, but that special case is specifically allowed
1209 // meaning that it isn't an external alias
1210 public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1212 assert id2hrn.contains( id );
1213 HeapRegionNode hrn = id2hrn.get( id );
1216 HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1218 Iterator i = idSet.iterator();
1219 while( i.hasNext() ) {
1220 Integer idFromSet = (Integer) i.next();
1221 assert id2hrn.contains( idFromSet );
1222 hrnSet.add( id2hrn.get( idFromSet ) );
1226 // do a traversal from hrn and see if any of the
1227 // heap regions from the set come up during that
1228 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1229 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1232 while( !toVisit.isEmpty() ) {
1233 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1234 toVisit.remove( hrnVisited );
1235 visited.add ( hrnVisited );
1237 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1238 while( referenceeItr.hasNext() ) {
1239 Map.Entry me = (Map.Entry) referenceeItr.next();
1240 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1241 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1243 if( idSet.contains( hrnReferencee.getID() ) ) {
1244 if( !id.equals( hrnReferencee.getID() ) ) {
1249 if( !visited.contains( hrnReferencee ) ) {
1250 toVisit.add( hrnReferencee );
1260 // for writing ownership graphs to dot files
1261 public void writeGraph( Descriptor methodDesc,
1263 boolean writeLabels,
1264 boolean writeReferencers
1265 ) throws java.io.IOException {
1267 methodDesc.getSymbol() +
1268 methodDesc.getNum() +
1275 public void writeGraph( Descriptor methodDesc,
1276 boolean writeLabels,
1277 boolean writeReferencers
1278 ) throws java.io.IOException {
1280 methodDesc.getSymbol() +
1281 methodDesc.getNum() +
1288 public void writeGraph( String graphName,
1289 boolean writeLabels,
1290 boolean writeReferencers
1291 ) throws java.io.IOException {
1293 // remove all non-word characters from the graph name so
1294 // the filename and identifier in dot don't cause errors
1295 graphName = graphName.replaceAll( "[\\W]", "" );
1297 BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
1298 bw.write( "digraph "+graphName+" {\n" );
1299 //bw.write( " size=\"7.5,10\";\n" );
1302 // then visit every heap region node
1303 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1305 Set s = id2hrn.entrySet();
1306 Iterator i = s.iterator();
1307 while( i.hasNext() ) {
1308 Map.Entry me = (Map.Entry) i.next();
1309 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1310 if( !visited.contains( hrn ) ) {
1311 traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1320 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
1323 // then visit every label node, useful for debugging
1325 s = td2ln.entrySet();
1327 while( i.hasNext() ) {
1328 Map.Entry me = (Map.Entry) i.next();
1329 LabelNode ln = (LabelNode) me.getValue();
1331 HeapRegionNode hrn = null;
1332 Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
1333 while( heapRegionsItr.hasNext() ) {
1334 Map.Entry meH = (Map.Entry) heapRegionsItr.next();
1335 hrn = (HeapRegionNode) meH.getKey();
1336 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
1338 bw.write( " " + ln.toString() +
1339 " -> " + hrn.toString() +
1340 "[label=\"" + rep.toEdgeLabelString() +
1351 protected void traverseHeapRegionNodes( int mode,
1355 HashSet<HeapRegionNode> visited,
1356 boolean writeReferencers
1357 ) throws java.io.IOException {
1359 if( visited.contains( hrn ) ) {
1365 case VISIT_HRN_WRITE_FULL:
1367 String attributes = "[";
1369 if( hrn.isSingleObject() ) {
1370 attributes += "shape=box";
1372 attributes += "shape=Msquare";
1375 if( hrn.isFlagged() ) {
1376 attributes += ",style=filled,fillcolor=lightgrey";
1379 attributes += ",label=\"ID" +
1382 hrn.getDescription() +
1384 hrn.getAlphaString() +
1387 bw.write( " " + hrn.toString() + attributes + ";\n" );
1392 // useful for debugging
1393 if( writeReferencers ) {
1394 OwnershipNode onRef = null;
1395 Iterator refItr = hrn.iteratorToReferencers();
1396 while( refItr.hasNext() ) {
1397 onRef = (OwnershipNode) refItr.next();
1400 case VISIT_HRN_WRITE_FULL:
1401 bw.write( " " + hrn.toString() +
1402 " -> " + onRef.toString() +
1403 "[color=lightgray];\n" );
1410 HeapRegionNode hrnChild = null;
1411 Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
1412 while( childRegionsItr.hasNext() ) {
1413 Map.Entry me = (Map.Entry) childRegionsItr.next();
1414 hrnChild = (HeapRegionNode) me.getKey();
1415 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1418 case VISIT_HRN_WRITE_FULL:
1419 bw.write( " " + hrn.toString() +
1420 " -> " + hrnChild.toString() +
1421 "[label=\"" + rep.toEdgeLabelString() +
1426 traverseHeapRegionNodes( mode,