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 ReferenceEdge edge ) {
113 assert referencer != null;
114 assert referencee != null;
116 assert edge.getSrc() == referencer;
117 assert edge.getDst() == referencee;
119 referencer.addReferencee( edge );
120 referencee.addReferencer( edge );
123 protected void removeReferenceEdge( OwnershipNode referencer,
124 HeapRegionNode referencee,
125 FieldDescriptor fieldDesc ) {
126 assert referencer != null;
127 assert referencee != null;
129 ReferenceEdge edge = referencer.getReferenceTo( referencee,
132 assert edge == referencee.getReferenceFrom( referencer,
135 referencer.removeReferencee( edge );
136 referencee.removeReferencer( edge );
139 protected void clearReferenceEdgesFrom( OwnershipNode referencer,
140 FieldDescriptor fieldDesc,
141 boolean removeAll ) {
142 assert referencer != null;
144 // get a copy of the set to iterate over, otherwise
145 // we will be trying to take apart the set as we
146 // are iterating over it, which won't work
147 Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
148 while( i.hasNext() ) {
149 ReferenceEdge edge = i.next();
151 if( removeAll || edge.getFieldDesc() == fieldDesc ) {
152 HeapRegionNode referencee = edge.getDst();
153 removeReferenceEdge( referencer,
155 edge.getFieldDesc() );
160 protected void clearReferenceEdgesTo( HeapRegionNode referencee,
161 FieldDescriptor fieldDesc,
162 boolean removeAll ) {
163 assert referencee != null;
165 // get a copy of the set to iterate over, otherwise
166 // we will be trying to take apart the set as we
167 // are iterating over it, which won't work
168 Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
169 while( i.hasNext() ) {
170 ReferenceEdge edge = i.next();
172 if( removeAll || edge.getFieldDesc() == fieldDesc ) {
173 OwnershipNode referencer = edge.getSrc();
174 removeReferenceEdge( referencer,
176 edge.getFieldDesc() );
183 protected void propagateTokensOverNodes( HeapRegionNode nPrime,
185 HashSet<HeapRegionNode> nodesWithNewAlpha,
186 HashSet<ReferenceEdgeProperties> edgesWithNewBeta ) {
188 HashSet<HeapRegionNode> todoNodes
189 = new HashSet<HeapRegionNode>();
190 todoNodes.add( nPrime );
192 HashSet<ReferenceEdgeProperties> todoEdges
193 = new HashSet<ReferenceEdgeProperties>();
195 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
196 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
197 nodePlannedChanges.put( nPrime, c0 );
199 Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges
200 = new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
203 while( !todoNodes.isEmpty() ) {
204 HeapRegionNode n = todoNodes.iterator().next();
205 ChangeTupleSet C = nodePlannedChanges.get( n );
207 Iterator itrC = C.iterator();
208 while( itrC.hasNext() ) {
209 ChangeTuple c = (ChangeTuple) itrC.next();
211 if( n.getAlpha().contains( c.getSetToMatch() ) ) {
212 ReachabilitySet withChange = n.getAlpha().union( c.getSetToAdd() );
213 n.setAlphaNew( n.getAlphaNew().union( withChange ) );
214 nodesWithNewAlpha.add( n );
218 Iterator referItr = n.iteratorToReferencers();
219 while( referItr.hasNext() ) {
220 OwnershipNode on = (OwnershipNode) referItr.next();
221 ReferenceEdgeProperties rep = on.getReferenceTo( n );
222 todoEdges.add( rep );
224 if( !edgePlannedChanges.containsKey( rep ) ) {
225 edgePlannedChanges.put( rep, new ChangeTupleSet().makeCanonical() );
228 edgePlannedChanges.put( rep, edgePlannedChanges.get( rep ).union( C ) );
231 HeapRegionNode m = null;
232 ReferenceEdgeProperties f = null;
233 Iterator refeeItr = n.setIteratorToReferencedRegions();
234 while( refeeItr.hasNext() ) {
235 Map.Entry me = (Map.Entry) refeeItr.next();
236 m = (HeapRegionNode) me.getKey();
237 f = (ReferenceEdgeProperties) me.getValue();
239 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
241 Iterator itrCprime = C.iterator();
242 while( itrCprime.hasNext() ) {
243 ChangeTuple c = (ChangeTuple) itrCprime.next();
244 if( f.getBeta().contains( c.getSetToMatch() ) ) {
245 changesToPass = changesToPass.union( c );
249 if( !changesToPass.isEmpty() ) {
250 if( !nodePlannedChanges.containsKey( m ) ) {
251 nodePlannedChanges.put( m, new ChangeTupleSet().makeCanonical() );
254 ChangeTupleSet currentChanges = nodePlannedChanges.get( m );
256 if( !changesToPass.isSubset( currentChanges ) ) {
258 nodePlannedChanges.put( m, currentChanges.union( changesToPass ) );
264 todoNodes.remove( n );
267 propagateTokensOverEdges( todoEdges, edgePlannedChanges, nodesWithNewAlpha, edgesWithNewBeta );
271 protected void propagateTokensOverEdges(
272 HashSet<ReferenceEdgeProperties> todoEdges,
273 Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges,
274 HashSet<HeapRegionNode> nodesWithNewAlpha,
275 HashSet<ReferenceEdgeProperties> edgesWithNewBeta ) {
278 while( !todoEdges.isEmpty() ) {
279 ReferenceEdgeProperties e = todoEdges.iterator().next();
280 todoEdges.remove( e );
282 if( !edgePlannedChanges.containsKey( e ) ) {
283 edgePlannedChanges.put( e, new ChangeTupleSet().makeCanonical() );
286 ChangeTupleSet C = edgePlannedChanges.get( e );
288 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
290 Iterator itrC = C.iterator();
291 while( itrC.hasNext() ) {
292 ChangeTuple c = (ChangeTuple) itrC.next();
293 if( e.getBeta().contains( c.getSetToMatch() ) ) {
294 ReachabilitySet withChange = e.getBeta().union( c.getSetToAdd() );
295 e.setBetaNew( e.getBetaNew().union( withChange ) );
296 edgesWithNewBeta.add( e );
297 changesToPass = changesToPass.union( c );
301 OwnershipNode onSrc = e.getSrc();
303 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
304 HeapRegionNode n = (HeapRegionNode) onSrc;
305 Iterator referItr = n.iteratorToReferencers();
307 while( referItr.hasNext() ) {
308 OwnershipNode onRef = (OwnershipNode) referItr.next();
309 ReferenceEdgeProperties f = onRef.getReferenceTo( n );
311 if( !edgePlannedChanges.containsKey( f ) ) {
312 edgePlannedChanges.put( f, new ChangeTupleSet().makeCanonical() );
315 ChangeTupleSet currentChanges = edgePlannedChanges.get( f );
317 if( !changesToPass.isSubset( currentChanges ) ) {
319 edgePlannedChanges.put( f, currentChanges.union( changesToPass ) );
328 ////////////////////////////////////////////////////
330 // Assignment Operation Methods
332 // These methods are high-level operations for
333 // modeling program assignment statements using
334 // the low-level reference create/remove methods
337 // The destination in an assignment statement is
338 // going to have new references. The method of
339 // determining the references depends on the type
340 // of the FlatNode assignment and the predicates
341 // of the nodes and edges involved.
343 ////////////////////////////////////////////////////
344 public void assignTempXToTempY( TempDescriptor x,
347 LabelNode lnX = getLabelNodeFromTemp( x );
348 LabelNode lnY = getLabelNodeFromTemp( y );
350 clearReferenceEdgesFrom( lnX, null, true );
352 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
353 while( itrYhrn.hasNext() ) {
354 ReferenceEdge edgeY = itrYhrn.next();
355 HeapRegionNode referencee = edgeY.getDst();
356 ReferenceEdge edgeNew = edgeY.copy();
357 edgeNew.setSrc( lnX );
359 addReferenceEdge( lnX, referencee, edgeNew );
364 public void assignTempXToTempYFieldF( TempDescriptor x,
366 FieldDescriptor f ) {
368 LabelNode lnX = getLabelNodeFromTemp( x );
369 LabelNode lnY = getLabelNodeFromTemp( y );
371 clearReferenceEdgesFrom( lnX, null, true );
373 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
374 while( itrYhrn.hasNext() ) {
375 ReferenceEdge edgeY = itrYhrn.next();
376 HeapRegionNode hrnY = edgeY.getDst();
377 ReachabilitySet betaY = edgeY.getBeta();
379 Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
380 while( itrHrnFhrn.hasNext() ) {
381 ReferenceEdge edgeHrn = itrHrnFhrn.next();
382 HeapRegionNode hrnHrn = edgeHrn.getDst();
383 ReachabilitySet betaHrn = edgeHrn.getBeta();
385 if( edgeHrn.getFieldDesc() == null ||
386 edgeHrn.getFieldDesc() == f ) {
388 ReferenceEdge edgeNew = new ReferenceEdge( lnX,
392 betaY.intersection( betaHrn ) );
394 addReferenceEdge( lnX, hrnHrn, edgeNew );
401 public void assignTempXFieldFToTempY( TempDescriptor x,
405 LabelNode lnX = getLabelNodeFromTemp( x );
406 LabelNode lnY = getLabelNodeFromTemp( y );
409 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
410 HashSet<ReferenceEdgeProperties> edgesWithNewBeta = new HashSet<ReferenceEdgeProperties>();
413 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
414 while( itrXhrn.hasNext() ) {
415 ReferenceEdge edgeX = itrXhrn.next();
416 HeapRegionNode hrnX = edgeX.getDst();
417 ReachabilitySet betaX = edgeX.getBeta();
419 //ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() );
421 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
422 while( itrYhrn.hasNext() ) {
423 ReferenceEdge edgeY = itrYhrn.next();
424 HeapRegionNode hrnY = edgeY.getDst();
425 ReachabilitySet betaY = edgeY.getBeta();
427 //ReachabilitySet O = repSrc.getBeta();
430 // propagate tokens over nodes starting from hrnSrc, and it will
431 // take care of propagating back up edges from any touched nodes
432 ChangeTupleSet Cy = O.unionUpArityToChangeSet( R );
433 propagateTokensOverNodes( hrnSrc, Cy, nodesWithNewAlpha, edgesWithNewBeta );
436 // then propagate back just up the edges from hrn
437 ChangeTupleSet Cx = R.unionUpArityToChangeSet( O );
439 HashSet<ReferenceEdgeProperties> todoEdges =
440 new HashSet<ReferenceEdgeProperties>();
442 Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges =
443 new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
445 Iterator referItr = hrn.iteratorToReferencers();
446 while( referItr.hasNext() ) {
447 OwnershipNode onRef = (OwnershipNode) referItr.next();
449 System.out.println( " "+onRef+" is upstream" );
451 ReferenceEdgeProperties repUpstream = onRef.getReferenceTo( hrn );
453 todoEdges.add( repUpstream );
454 edgePlannedChanges.put( repUpstream, Cx );
457 System.out.println( "plans "+edgePlannedChanges );
459 propagateTokensOverEdges( todoEdges,
464 System.out.println( " Onew = "+repSrc.getBetaNew() );
467 // finally, create the actual reference edge hrnX.f -> hrnY
468 ReferenceEdge edgeNew = new ReferenceEdge( hrnX,
475 repSrc.getBetaNew().pruneBy( hrn.getAlpha()
478 addReferenceEdge( hrnX, hrnY, edgeNew );
483 Iterator nodeItr = nodesWithNewAlpha.iterator();
484 while( nodeItr.hasNext() ) {
485 ((HeapRegionNode) nodeItr.next()).applyAlphaNew();
488 Iterator edgeItr = edgesWithNewBeta.iterator();
489 while( edgeItr.hasNext() ) {
490 ((ReferenceEdgeProperties) edgeItr.next()).applyBetaNew();
496 public void assignTempToParameterAllocation( boolean isTask,
498 Integer paramIndex ) {
501 LabelNode lnParam = getLabelNodeFromTemp( td );
502 HeapRegionNode hrn = createNewHeapRegionNode( null,
509 "param" + paramIndex );
511 // keep track of heap regions that were created for
512 // parameter labels, the index of the parameter they
513 // are for is important when resolving method calls
514 Integer newID = hrn.getID();
515 assert !id2paramIndex.containsKey ( newID );
516 assert !id2paramIndex.containsValue( paramIndex );
517 id2paramIndex.put( newID, paramIndex );
518 paramIndex2id.put( paramIndex, newID );
520 ReachabilitySet beta = new ReachabilitySet( new TokenTuple( newID,
522 TokenTuple.ARITY_ONE ) );
524 // heap regions for parameters are always multiple object (see above)
525 // and have a reference to themselves, because we can't know the
526 // structure of memory that is passed into the method. We're assuming
529 ReferenceEdge edgeFromLabel =
530 new ReferenceEdge( lnParam, hrn, null, false, beta );
532 ReferenceEdge edgeReflexive =
533 new ReferenceEdge( hrn, hrn, null, true, beta );
535 addReferenceEdge( lnParam, hrn, edgeFromLabel );
536 addReferenceEdge( hrn, hrn, edgeReflexive );
540 public void assignTempXToNewAllocation( TempDescriptor x,
541 AllocationSite as ) {
547 // after the age operation the newest (or zero-ith oldest)
548 // node associated with the allocation site should have
549 // no references to it as if it were a newly allocated
550 // heap region, so make a reference to it to complete
554 Integer idNewest = as.getIthOldest( 0 );
555 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
556 assert hrnNewest != null;
558 LabelNode lnX = getLabelNodeFromTemp( x );
559 clearReferenceEdgesFrom( lnX, null, true );
561 ReferenceEdge edgeNew =
562 new ReferenceEdge( lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
564 addReferenceEdge( lnX, hrnNewest, edgeNew );
572 // use the allocation site (unique to entire analysis) to
573 // locate the heap region nodes in this ownership graph
574 // that should be aged. The process models the allocation
575 // of new objects and collects all the oldest allocations
576 // in a summary node to allow for a finite analysis
578 // There is an additional property of this method. After
579 // running it on a particular ownership graph (many graphs
580 // may have heap regions related to the same allocation site)
581 // the heap region node objects in this ownership graph will be
582 // allocated. Therefore, after aging a graph for an allocation
583 // site, attempts to retrieve the heap region nodes using the
584 // integer id's contained in the allocation site should always
585 // return non-null heap regions.
586 public void age( AllocationSite as ) {
588 // aging adds this allocation site to the graph's
589 // list of sites that exist in the graph, or does
590 // nothing if the site is already in the list
591 allocationSites.add( as );
593 // get the summary node for the allocation site in the context
594 // of this particular ownership graph
595 HeapRegionNode hrnSummary = getSummaryNode( as );
597 // merge oldest node into summary
598 Integer idK = as.getOldest();
599 HeapRegionNode hrnK = id2hrn.get( idK );
600 mergeIntoSummary( hrnK, hrnSummary );
602 // move down the line of heap region nodes
603 // clobbering the ith and transferring all references
604 // to and from i-1 to node i. Note that this clobbers
605 // the oldest node (hrnK) that was just merged into
607 for( int i = allocationDepth - 1; i > 0; --i ) {
609 // move references from the i-1 oldest to the ith oldest
610 Integer idIth = as.getIthOldest( i );
611 HeapRegionNode hrnI = id2hrn.get( idIth );
612 Integer idImin1th = as.getIthOldest( i - 1 );
613 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
615 transferOnto( hrnImin1, hrnI );
618 // as stated above, the newest node should have had its
619 // references moved over to the second oldest, so we wipe newest
620 // in preparation for being the new object to assign something to
621 Integer id0th = as.getIthOldest( 0 );
622 HeapRegionNode hrn0 = id2hrn.get( id0th );
625 // clear all references in and out of newest node
626 clearReferenceEdgesFrom( hrn0, null, true );
627 clearReferenceEdgesTo ( hrn0, null, true );
630 // now tokens in reachability sets need to "age" also
631 ReferenceEdgeProperties repToAge = null;
632 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
633 while( itrAllLabelNodes.hasNext() ) {
634 Map.Entry me = (Map.Entry) itrAllLabelNodes.next();
635 LabelNode ln = (LabelNode) me.getValue();
637 Iterator itrEdges = ln.setIteratorToReferencedRegions();
638 while( itrEdges.hasNext() ) {
639 Map.Entry meE = (Map.Entry) itrEdges.next();
640 repToAge = (ReferenceEdgeProperties) meE.getValue();
642 ageTokens( as, repToAge );
645 HeapRegionNode hrnToAge = null;
646 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
647 while( itrAllHRNodes.hasNext() ) {
648 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
649 hrnToAge = (HeapRegionNode) me.getValue();
651 ageTokens( as, hrnToAge );
653 Iterator itrEdges = hrnToAge.setIteratorToReferencedRegions();
654 while( itrEdges.hasNext() ) {
655 Map.Entry meE = (Map.Entry) itrEdges.next();
656 repToAge = (ReferenceEdgeProperties) meE.getValue();
658 ageTokens( as, repToAge );
663 // after tokens have been aged, reset newest node's reachability
664 hrn0.setAlpha( new ReachabilitySet(
666 new TokenTuple( hrn0 )
673 protected HeapRegionNode getSummaryNode( AllocationSite as ) {
675 Integer idSummary = as.getSummary();
676 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
678 // If this is null then we haven't touched this allocation site
679 // in the context of the current ownership graph, so allocate
680 // heap region nodes appropriate for the entire allocation site.
681 // This should only happen once per ownership graph per allocation site,
682 // and a particular integer id can be used to locate the heap region
683 // in different ownership graphs that represents the same part of an
685 if( hrnSummary == null ) {
687 boolean hasFlags = false;
688 if( as.getType().isClass() ) {
689 hasFlags = as.getType().getClassDesc().hasFlags();
692 hrnSummary = createNewHeapRegionNode( idSummary,
699 as + "\\n" + as.getType() + "\\nsummary" );
701 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
702 Integer idIth = as.getIthOldest( i );
703 assert !id2hrn.containsKey( idIth );
704 createNewHeapRegionNode( idIth,
711 as + "\\n" + as.getType() + "\\n" + i + " oldest" );
719 protected HeapRegionNode getShadowSummaryNode( AllocationSite as ) {
721 Integer idShadowSummary = -(as.getSummary());
722 HeapRegionNode hrnShadowSummary = id2hrn.get( idShadowSummary );
724 if( hrnShadowSummary == null ) {
726 boolean hasFlags = false;
727 if( as.getType().isClass() ) {
728 hasFlags = as.getType().getClassDesc().hasFlags();
731 hrnShadowSummary = createNewHeapRegionNode( idShadowSummary,
738 as + "\\n" + as.getType() + "\\nshadowSum" );
740 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
741 Integer idShadowIth = -(as.getIthOldest( i ));
742 assert !id2hrn.containsKey( idShadowIth );
743 createNewHeapRegionNode( idShadowIth,
750 as + "\\n" + as.getType() + "\\n" + i + " shadow" );
754 return hrnShadowSummary;
758 protected void mergeIntoSummary( HeapRegionNode hrn, HeapRegionNode hrnSummary ) {
759 assert hrnSummary.isNewSummary();
761 // transfer references _from_ hrn over to hrnSummary
762 HeapRegionNode hrnReferencee = null;
763 Iterator itrReferencee = hrn.setIteratorToReferencedRegions();
764 while( itrReferencee.hasNext() ) {
765 Map.Entry me = (Map.Entry) itrReferencee.next();
766 hrnReferencee = (HeapRegionNode) me.getKey();
767 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
769 ReferenceEdgeProperties repSummary = hrnSummary.getReferenceTo( hrnReferencee );
770 ReferenceEdgeProperties repMerged = rep.copy();
772 if( repSummary == null ) {
773 // the merge is trivial, nothing to be done
775 // otherwise an edge from the referencer to hrnSummary exists already
776 // and the edge referencer->hrn should be merged with it
777 repMerged.setBeta( repMerged.getBeta().union( repSummary.getBeta() ) );
780 addReferenceEdge( hrnSummary, hrnReferencee, repMerged );
783 // next transfer references _to_ hrn over to hrnSummary
784 OwnershipNode onReferencer = null;
785 Iterator itrReferencer = hrn.iteratorToReferencers();
786 while( itrReferencer.hasNext() ) {
787 onReferencer = (OwnershipNode) itrReferencer.next();
789 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrn );
791 ReferenceEdgeProperties repSummary = onReferencer.getReferenceTo( hrnSummary );
792 ReferenceEdgeProperties repMerged = rep.copy();
794 if( repSummary == null ) {
795 // the merge is trivial, nothing to be done
797 // otherwise an edge from the referencer to alpha_S exists already
798 // and the edge referencer->alpha_K should be merged with it
799 repMerged.setBeta( repMerged.getBeta().union( repSummary.getBeta() ) );
802 addReferenceEdge( onReferencer, hrnSummary, repMerged );
805 // then merge hrn reachability into hrnSummary
806 hrnSummary.setAlpha( hrnSummary.getAlpha().union( hrn.getAlpha() ) );
810 protected void transferOnto( HeapRegionNode hrnA, HeapRegionNode hrnB ) {
812 // clear references in and out of node i
813 clearReferenceEdgesFrom( hrnB );
814 clearReferenceEdgesTo ( hrnB );
816 // copy each edge in and out of A to B
817 HeapRegionNode hrnReferencee = null;
818 Iterator itrReferencee = hrnA.setIteratorToReferencedRegions();
819 while( itrReferencee.hasNext() ) {
820 Map.Entry me = (Map.Entry) itrReferencee.next();
821 hrnReferencee = (HeapRegionNode) me.getKey();
822 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
824 addReferenceEdge( hrnB, hrnReferencee, rep.copy() );
827 OwnershipNode onReferencer = null;
828 Iterator itrReferencer = hrnA.iteratorToReferencers();
829 while( itrReferencer.hasNext() ) {
830 onReferencer = (OwnershipNode) itrReferencer.next();
832 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnA );
835 addReferenceEdge( onReferencer, hrnB, rep.copy() );
838 // replace hrnB reachability with hrnA's
839 hrnB.setAlpha( hrnA.getAlpha() );
844 protected void ageTokens( AllocationSite as, ReferenceEdgeProperties rep ) {
845 rep.setBeta( rep.getBeta().ageTokens( as ) );
848 protected void ageTokens( AllocationSite as, HeapRegionNode hrn ) {
849 hrn.setAlpha( hrn.getAlpha().ageTokens( as ) );
852 protected void majorAgeTokens( AllocationSite as, ReferenceEdgeProperties rep ) {
853 //rep.setBeta( rep.getBeta().majorAgeTokens( as ) );
856 protected void majorAgeTokens( AllocationSite as, HeapRegionNode hrn ) {
857 //hrn.setAlpha( hrn.getAlpha().majorAgeTokens( as ) );
862 // the heap regions that are specially allocated as multiple-object
863 // regions for method parameters need to be remembered in order to
864 // resolve a function call. So actually, we need a mapping from
865 // caller argument descriptors to the callee parameter heap regions
866 // to apply reference edges in the callee to the caller graph.
868 // also, Constructors and virtual dispatch methods have a "this"
869 // argument that make the mapping of arguments to parameters a little
870 // tricky. What happens to that this region?
873 public void resolveMethodCall( FlatCall fc,
876 OwnershipGraph ogCallee ) {
879 // verify the existence of allocation sites and their
880 // shadows from the callee in the context of this caller graph
881 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
882 while( asItr.hasNext() ) {
883 AllocationSite allocSite = asItr.next();
884 HeapRegionNode hrnSummary = getSummaryNode ( allocSite );
885 HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
888 // in non-static methods there is a "this" pointer
889 // that should be taken into account
891 assert fc.numArgs() == fm.numParameters();
893 assert fc.numArgs() + 1 == fm.numParameters();
896 // make a change set to translate callee tokens into caller tokens
897 ChangeTupleSet C = new ChangeTupleSet().makeCanonical();
899 for( int i = 0; i < fm.numParameters(); ++i ) {
901 Integer indexParam = new Integer( i );
903 System.out.println( "In method "+fm+ " on param "+indexParam );
905 assert ogCallee.paramIndex2id.containsKey( indexParam );
906 Integer idParam = ogCallee.paramIndex2id.get( indexParam );
908 assert ogCallee.id2hrn.containsKey( idParam );
909 HeapRegionNode hrnParam = ogCallee.id2hrn.get( idParam );
910 assert hrnParam != null;
912 TokenTupleSet calleeTokenToMatch =
913 new TokenTupleSet( new TokenTuple( hrnParam ) ).makeCanonical();
916 // now depending on whether the callee is static or not
917 // we need to account for a "this" argument in order to
918 // find the matching argument in the caller context
919 TempDescriptor argTemp;
921 argTemp = fc.getArg( indexParam );
923 if( indexParam == 0 ) {
924 argTemp = fc.getThis();
926 argTemp = fc.getArg( indexParam - 1 );
930 LabelNode argLabel = getLabelNodeFromTemp( argTemp );
931 Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
932 while( argHeapRegionsItr.hasNext() ) {
933 Map.Entry meArg = (Map.Entry) argHeapRegionsItr.next();
934 HeapRegionNode argHeapRegion = (HeapRegionNode) meArg.getKey();
935 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
937 Iterator<TokenTupleSet> ttsItr = repArg.getBeta().iterator();
938 while( ttsItr.hasNext() ) {
939 TokenTupleSet callerTokensToReplace = ttsItr.next();
941 ChangeTuple ct = new ChangeTuple( calleeTokenToMatch,
942 callerTokensToReplace ).makeCanonical();
949 System.out.println( "Applying method call "+fm );
950 System.out.println( " Change: "+C );
953 // the heap regions represented by the arguments (caller graph)
954 // and heap regions for the parameters (callee graph)
955 // don't correspond to each other by heap region ID. In fact,
956 // an argument label node can be referencing several heap regions
957 // so the parameter label always references a multiple-object
958 // heap region in order to handle the range of possible contexts
959 // for a method call. This means we need to make a special mapping
960 // of argument->parameter regions in order to update the caller graph
962 // for every heap region->heap region edge in the
963 // callee graph, create the matching edge or edges
964 // in the caller graph
965 Set sCallee = ogCallee.id2hrn.entrySet();
966 Iterator iCallee = sCallee.iterator();
967 while( iCallee.hasNext() ) {
968 Map.Entry meCallee = (Map.Entry) iCallee.next();
969 Integer idCallee = (Integer) meCallee.getKey();
970 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
972 HeapRegionNode hrnChildCallee = null;
973 Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
974 while( heapRegionsItrCallee.hasNext() ) {
975 Map.Entry me = (Map.Entry) heapRegionsItrCallee.next();
976 hrnChildCallee = (HeapRegionNode) me.getKey();
977 ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
979 Integer idChildCallee = hrnChildCallee.getID();
981 // only address this edge if it is not a special reflexive edge
982 if( !repC.isInitialParamReflexive() ) {
984 // now we know that in the callee method's ownership graph
985 // there is a heap region->heap region reference edge given
986 // by heap region pointers:
987 // hrnCallee -> heapChildCallee
989 // or by the ownership-graph independent ID's:
990 // idCallee -> idChildCallee
992 // So now make a set of possible source heaps in the caller graph
993 // and a set of destination heaps in the caller graph, and make
994 // a reference edge in the caller for every possible (src,dst) pair
995 HashSet<HeapRegionNode> possibleCallerSrcs =
996 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1001 HashSet<HeapRegionNode> possibleCallerDsts =
1002 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1007 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1008 Iterator srcItr = possibleCallerSrcs.iterator();
1009 while( srcItr.hasNext() ) {
1010 HeapRegionNode src = (HeapRegionNode) srcItr.next();
1012 Iterator dstItr = possibleCallerDsts.iterator();
1013 while( dstItr.hasNext() ) {
1014 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1016 addReferenceEdge( src, dst, repC.copy() );
1026 private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
1029 boolean isStatic ) {
1031 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1033 if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
1034 // the heap region that is part of this
1035 // reference edge won't have a matching ID in the
1036 // caller graph because it is specifically allocated
1037 // for a particular parameter. Use that information
1038 // to find the corresponding argument label in the
1039 // caller in order to create the proper reference edge
1041 assert !id2hrn.containsKey( idCallee );
1043 Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
1044 TempDescriptor argTemp;
1046 // now depending on whether the callee is static or not
1047 // we need to account for a "this" argument in order to
1048 // find the matching argument in the caller context
1050 argTemp = fc.getArg( paramIndex );
1052 if( paramIndex == 0 ) {
1053 argTemp = fc.getThis();
1055 argTemp = fc.getArg( paramIndex - 1 );
1059 LabelNode argLabel = getLabelNodeFromTemp( argTemp );
1060 Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
1061 while( argHeapRegionsItr.hasNext() ) {
1062 Map.Entry meArg = (Map.Entry) argHeapRegionsItr.next();
1063 HeapRegionNode argHeapRegion = (HeapRegionNode) meArg.getKey();
1064 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
1066 possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
1070 // this heap region is not a parameter, so it should
1071 // have a matching heap region in the caller graph
1072 assert id2hrn.containsKey( idCallee );
1073 possibleCallerHRNs.add( id2hrn.get( idCallee ) );
1076 return possibleCallerHRNs;
1081 ////////////////////////////////////////////////////
1082 // in merge() and equals() methods the suffix A
1083 // represents the passed in graph and the suffix
1084 // B refers to the graph in this object
1085 // Merging means to take the incoming graph A and
1086 // merge it into B, so after the operation graph B
1087 // is the final result.
1088 ////////////////////////////////////////////////////
1089 public void merge( OwnershipGraph og ) {
1095 mergeOwnershipNodes ( og );
1096 mergeReferenceEdges ( og );
1097 mergeId2paramIndex ( og );
1098 mergeAllocationSites( og );
1102 protected void mergeOwnershipNodes( OwnershipGraph og ) {
1103 Set sA = og.id2hrn.entrySet();
1104 Iterator iA = sA.iterator();
1105 while( iA.hasNext() ) {
1106 Map.Entry meA = (Map.Entry) iA.next();
1107 Integer idA = (Integer) meA.getKey();
1108 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1110 // if this graph doesn't have a node the
1111 // incoming graph has, allocate it
1112 if( !id2hrn.containsKey( idA ) ) {
1113 HeapRegionNode hrnB = hrnA.copy();
1114 id2hrn.put( idA, hrnB );
1117 // otherwise this is a node present in both graphs
1118 // so make the new reachability set a union of the
1119 // nodes' reachability sets
1120 HeapRegionNode hrnB = id2hrn.get( idA );
1121 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
1125 // now add any label nodes that are in graph B but
1127 sA = og.td2ln.entrySet();
1129 while( iA.hasNext() ) {
1130 Map.Entry meA = (Map.Entry) iA.next();
1131 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1132 LabelNode lnA = (LabelNode) meA.getValue();
1134 // if the label doesn't exist in B, allocate and add it
1135 LabelNode lnB = getLabelNodeFromTemp( tdA );
1139 protected void mergeReferenceEdges( OwnershipGraph og ) {
1142 Set sA = og.id2hrn.entrySet();
1143 Iterator iA = sA.iterator();
1144 while( iA.hasNext() ) {
1145 Map.Entry meA = (Map.Entry) iA.next();
1146 Integer idA = (Integer) meA.getKey();
1147 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1149 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1150 while( heapRegionsItrA.hasNext() ) {
1151 ReferenceEdge edgeA = heapRegionsItrA.next();
1152 HeapRegionNode hrnChildA = edgeA.getDst();
1153 Integer idChildA = hrnChildA.getID();
1155 // at this point we know an edge in graph A exists
1156 // idA -> idChildA, does this exist in B?
1157 assert id2hrn.containsKey( idA );
1158 HeapRegionNode hrnB = id2hrn.get( idA );
1159 ReferenceEdge edgeToMerge = null;
1161 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1162 while( heapRegionsItrB.hasNext() &&
1163 edgeToMerge == null ) {
1165 ReferenceEdge edgeB = heapRegionsItrB.next();
1166 HeapRegionNode hrnChildB = edgeB.getDst();
1168 // don't use the ReferenceEdge.equals() here because
1169 // we're talking about existence between graphs
1170 if( hrnChildB.equals( idChildA ) &&
1171 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1172 edgeToMerge = edgeB;
1176 // if the edge from A was not found in B,
1178 if( edgeToMerge == null ) {
1179 assert id2hrn.containsKey( idChildA );
1180 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
1181 edgeToMerge = edgeA.copy();
1182 edgeToMerge.setSrc( hrnB );
1183 edgeToMerge.setDst( hrnChildB );
1184 addReferenceEdge( hrnB, hrnChildB, edgeToMerge );
1186 // otherwise, the edge already existed in both graphs
1187 // so merge their reachability sets
1189 // just replace this beta set with the union
1190 assert edgeToMerge != null;
1191 edgeToMerge.setBeta(
1192 edgeToMerge.getBeta().union( edgeA.getBeta() )
1194 if( !edgeA.isInitialParamReflexive() ) {
1195 edgeToMerge.setIsInitialParamReflexive( false );
1201 // and then again with label nodes
1202 sA = og.td2ln.entrySet();
1204 while( iA.hasNext() ) {
1205 Map.Entry meA = (Map.Entry) iA.next();
1206 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1207 LabelNode lnA = (LabelNode) meA.getValue();
1209 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1210 while( heapRegionsItrA.hasNext() ) {
1211 ReferenceEdge edgeA = heapRegionsItrA.next();
1212 HeapRegionNode hrnChildA = edgeA.getDst();
1213 Integer idChildA = hrnChildA.getID();
1215 // at this point we know an edge in graph A exists
1216 // tdA -> idChildA, does this exist in B?
1217 assert td2ln.containsKey( tdA );
1218 LabelNode lnB = td2ln.get( tdA );
1219 ReferenceEdge edgeToMerge = null;
1221 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1222 while( heapRegionsItrB.hasNext() &&
1223 edgeToMerge == null ) {
1225 ReferenceEdge edgeB = heapRegionsItrB.next();
1226 HeapRegionNode hrnChildB = edgeB.getDst();
1228 // don't use the ReferenceEdge.equals() here because
1229 // we're talking about existence between graphs
1230 if( hrnChildB.equals( idChildA ) &&
1231 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1232 edgeToMerge = edgeB;
1236 // if the edge from A was not found in B,
1238 if( edgeToMerge == null ) {
1239 assert id2hrn.containsKey( idChildA );
1240 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
1241 edgeToMerge = edgeA.copy();
1242 edgeToMerge.setSrc( lnB );
1243 edgeToMerge.setDst( hrnChildB );
1244 addReferenceEdge( lnB, hrnChildB, edgeToMerge );
1246 // otherwise, the edge already existed in both graphs
1247 // so merge their reachability sets
1249 // just replace this beta set with the union
1250 assert edgeToMerge != null;
1251 edgeToMerge.setBeta(
1252 edgeToMerge.getBeta().union( edgeA.getBeta() )
1254 if( !edgeA.isInitialParamReflexive() ) {
1255 edgeToMerge.setIsInitialParamReflexive( false );
1262 // you should only merge ownership graphs that have the
1263 // same number of parameters, or if one or both parameter
1264 // index tables are empty
1265 protected void mergeId2paramIndex( OwnershipGraph og ) {
1266 if( id2paramIndex.size() == 0 ) {
1267 id2paramIndex = og.id2paramIndex;
1268 paramIndex2id = og.paramIndex2id;
1272 if( og.id2paramIndex.size() == 0 ) {
1276 assert id2paramIndex.size() == og.id2paramIndex.size();
1279 protected void mergeAllocationSites( OwnershipGraph og ) {
1280 allocationSites.addAll( og.allocationSites );
1285 // it is necessary in the equals() member functions
1286 // to "check both ways" when comparing the data
1287 // structures of two graphs. For instance, if all
1288 // edges between heap region nodes in graph A are
1289 // present and equal in graph B it is not sufficient
1290 // to say the graphs are equal. Consider that there
1291 // may be edges in graph B that are not in graph A.
1292 // the only way to know that all edges in both graphs
1293 // are equally present is to iterate over both data
1294 // structures and compare against the other graph.
1295 public boolean equals( OwnershipGraph og ) {
1301 if( !areHeapRegionNodesEqual( og ) ) {
1305 if( !areLabelNodesEqual( og ) ) {
1309 if( !areReferenceEdgesEqual( og ) ) {
1313 if( !areId2paramIndexEqual( og ) ) {
1317 // if everything is equal up to this point,
1318 // assert that allocationSites is also equal--
1319 // this data is redundant and kept for efficiency
1320 assert allocationSites.equals( og.allocationSites );
1325 protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
1327 if( !areallHRNinAalsoinBandequal( this, og ) ) {
1331 if( !areallHRNinAalsoinBandequal( og, this ) ) {
1338 static protected boolean areallHRNinAalsoinBandequal( OwnershipGraph ogA,
1339 OwnershipGraph ogB ) {
1340 Set sA = ogA.id2hrn.entrySet();
1341 Iterator iA = sA.iterator();
1342 while( iA.hasNext() ) {
1343 Map.Entry meA = (Map.Entry) iA.next();
1344 Integer idA = (Integer) meA.getKey();
1345 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1347 if( !ogB.id2hrn.containsKey( idA ) ) {
1351 HeapRegionNode hrnB = ogB.id2hrn.get( idA );
1352 if( !hrnA.equals( hrnB ) ) {
1361 protected boolean areLabelNodesEqual( OwnershipGraph og ) {
1363 if( !areallLNinAalsoinBandequal( this, og ) ) {
1367 if( !areallLNinAalsoinBandequal( og, this ) ) {
1374 static protected boolean areallLNinAalsoinBandequal( OwnershipGraph ogA,
1375 OwnershipGraph ogB ) {
1376 Set sA = ogA.td2ln.entrySet();
1377 Iterator iA = sA.iterator();
1378 while( iA.hasNext() ) {
1379 Map.Entry meA = (Map.Entry) iA.next();
1380 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1382 if( !ogB.td2ln.containsKey( tdA ) ) {
1391 protected boolean areReferenceEdgesEqual( OwnershipGraph og ) {
1392 if( !areallREinAandBequal( this, og ) ) {
1399 static protected boolean areallREinAandBequal( OwnershipGraph ogA,
1400 OwnershipGraph ogB ) {
1402 // check all the heap region->heap region edges
1403 Set sA = ogA.id2hrn.entrySet();
1404 Iterator iA = sA.iterator();
1405 while( iA.hasNext() ) {
1406 Map.Entry meA = (Map.Entry) iA.next();
1407 Integer idA = (Integer) meA.getKey();
1408 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1410 // we should have already checked that the same
1411 // heap regions exist in both graphs
1412 assert ogB.id2hrn.containsKey( idA );
1414 if( !areallREfromAequaltoB( ogA, hrnA, ogB ) ) {
1418 // then check every edge in B for presence in A, starting
1419 // from the same parent HeapRegionNode
1420 HeapRegionNode hrnB = ogB.id2hrn.get( idA );
1422 if( !areallREfromAequaltoB( ogB, hrnB, ogA ) ) {
1427 // then check all the label->heap region edges
1428 sA = ogA.td2ln.entrySet();
1430 while( iA.hasNext() ) {
1431 Map.Entry meA = (Map.Entry) iA.next();
1432 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1433 LabelNode lnA = (LabelNode) meA.getValue();
1435 // we should have already checked that the same
1436 // label nodes exist in both graphs
1437 assert ogB.td2ln.containsKey( tdA );
1439 if( !areallREfromAequaltoB( ogA, lnA, ogB ) ) {
1443 // then check every edge in B for presence in A, starting
1444 // from the same parent LabelNode
1445 LabelNode lnB = ogB.td2ln.get( tdA );
1447 if( !areallREfromAequaltoB( ogB, lnB, ogA ) ) {
1456 static protected boolean areallREfromAequaltoB( OwnershipGraph ogA,
1458 OwnershipGraph ogB ) {
1460 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
1461 while( itrA.hasNext() ) {
1462 ReferenceEdge edgeA = itrA.next();
1463 HeapRegionNode hrnChildA = edgeA.getDst();
1464 Integer idChildA = hrnChildA.getID();
1466 assert ogB.id2hrn.containsKey( idChildA );
1468 // at this point we know an edge in graph A exists
1469 // onA -> idChildA, does this exact edge exist in B?
1470 boolean edgeFound = false;
1472 OwnershipNode onB = null;
1473 if( onA instanceof HeapRegionNode ) {
1474 HeapRegionNode hrnA = (HeapRegionNode) onA;
1475 onB = ogB.id2hrn.get( hrnA.getID() );
1477 LabelNode lnA = (LabelNode) onA;
1478 onB = ogB.td2ln.get( lnA.getTempDescriptor() );
1481 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
1482 while( itrB.hasNext() ) {
1483 ReferenceEdge edgeB = itrB.next();
1484 HeapRegionNode hrnChildB = edgeB.getDst();
1486 if( idChildA.equals( hrnChildB.getID() ) &&
1487 edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
1489 // there is an edge in the right place with the right field,
1490 // but do they have the same attributes?
1491 if( edgeA.isInitialParamReflexive() == edgeB.isInitialParamReflexive() &&
1492 edgeA.getBeta().equals( edgeB.getBeta() ) ) {
1510 protected boolean areId2paramIndexEqual( OwnershipGraph og ) {
1511 return id2paramIndex.size() == og.id2paramIndex.size();
1516 // given a set B of heap region node ID's, return the set of heap
1517 // region node ID's that is reachable from B
1518 public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1520 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1521 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1523 // initial nodes to visit are from set B
1524 Iterator initialItr = idSetB.iterator();
1525 while( initialItr.hasNext() ) {
1526 Integer idInitial = (Integer) initialItr.next();
1527 assert id2hrn.contains( idInitial );
1528 HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1529 toVisit.add( hrnInitial );
1532 HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1534 // do a heap traversal
1535 while( !toVisit.isEmpty() ) {
1536 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1537 toVisit.remove( hrnVisited );
1538 visited.add ( hrnVisited );
1540 // for every node visited, add it to the total
1542 idSetReachableFromB.add( hrnVisited.getID() );
1544 // find other reachable nodes
1545 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1546 while( referenceeItr.hasNext() ) {
1547 Map.Entry me = (Map.Entry) referenceeItr.next();
1548 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1549 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1551 if( !visited.contains( hrnReferencee ) ) {
1552 toVisit.add( hrnReferencee );
1557 return idSetReachableFromB;
1561 // used to find if a heap region can possibly have a reference to
1562 // any of the heap regions in the given set
1563 // if the id supplied is in the set, then a self-referencing edge
1564 // would return true, but that special case is specifically allowed
1565 // meaning that it isn't an external alias
1566 public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1568 assert id2hrn.contains( id );
1569 HeapRegionNode hrn = id2hrn.get( id );
1572 //HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1574 //Iterator i = idSet.iterator();
1575 //while( i.hasNext() ) {
1576 // Integer idFromSet = (Integer) i.next();
1577 // assert id2hrn.contains( idFromSet );
1578 // hrnSet.add( id2hrn.get( idFromSet ) );
1582 // do a traversal from hrn and see if any of the
1583 // heap regions from the set come up during that
1584 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1585 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1588 while( !toVisit.isEmpty() ) {
1589 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1590 toVisit.remove( hrnVisited );
1591 visited.add ( hrnVisited );
1593 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1594 while( referenceeItr.hasNext() ) {
1595 Map.Entry me = (Map.Entry) referenceeItr.next();
1596 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1597 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1599 if( idSet.contains( hrnReferencee.getID() ) ) {
1600 if( !id.equals( hrnReferencee.getID() ) ) {
1605 if( !visited.contains( hrnReferencee ) ) {
1606 toVisit.add( hrnReferencee );
1616 // for writing ownership graphs to dot files
1617 public void writeGraph( Descriptor methodDesc,
1619 boolean writeLabels,
1620 boolean labelSelect,
1621 boolean pruneGarbage,
1622 boolean writeReferencers
1623 ) throws java.io.IOException {
1625 methodDesc.getSymbol() +
1626 methodDesc.getNum() +
1635 public void writeGraph( Descriptor methodDesc,
1637 boolean writeLabels,
1638 boolean writeReferencers
1639 ) throws java.io.IOException {
1641 methodDesc.getSymbol() +
1642 methodDesc.getNum() +
1651 public void writeGraph( Descriptor methodDesc,
1652 boolean writeLabels,
1653 boolean writeReferencers
1654 ) throws java.io.IOException {
1656 methodDesc.getSymbol() +
1657 methodDesc.getNum() +
1666 public void writeGraph( Descriptor methodDesc,
1667 boolean writeLabels,
1668 boolean labelSelect,
1669 boolean pruneGarbage,
1670 boolean writeReferencers
1671 ) throws java.io.IOException {
1673 methodDesc.getSymbol() +
1674 methodDesc.getNum() +
1683 public void writeGraph( String graphName,
1684 boolean writeLabels,
1685 boolean labelSelect,
1686 boolean pruneGarbage,
1687 boolean writeReferencers
1688 ) throws java.io.IOException {
1690 // remove all non-word characters from the graph name so
1691 // the filename and identifier in dot don't cause errors
1692 graphName = graphName.replaceAll( "[\\W]", "" );
1694 BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
1695 bw.write( "digraph "+graphName+" {\n" );
1696 //bw.write( " size=\"7.5,10\";\n" );
1698 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1700 // then visit every heap region node
1701 if( !pruneGarbage ) {
1702 Set s = id2hrn.entrySet();
1703 Iterator i = s.iterator();
1704 while( i.hasNext() ) {
1705 Map.Entry me = (Map.Entry) i.next();
1706 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1707 if( !visited.contains( hrn ) ) {
1708 traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1718 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
1721 // then visit every label node, useful for debugging
1723 Set s = td2ln.entrySet();
1724 Iterator i = s.iterator();
1725 while( i.hasNext() ) {
1726 Map.Entry me = (Map.Entry) i.next();
1727 LabelNode ln = (LabelNode) me.getValue();
1730 String labelStr = ln.getTempDescriptorString();
1731 if( labelStr.startsWith( "___temp" ) ||
1732 labelStr.startsWith( "___dst" ) ||
1733 labelStr.startsWith( "___srctmp" ) ||
1734 labelStr.startsWith( "___neverused" ) ) {
1739 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
1740 while( heapRegionsItr.hasNext() ) {
1741 ReferenceEdge edge = heapRegionsItr.next();
1742 HeapRegionNode hrn = edge.getDst();
1744 if( pruneGarbage && !visited.contains( hrn ) ) {
1745 traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1753 bw.write( " " + ln.toString() +
1754 " -> " + hrn.toString() +
1755 "[label=\"" + edge.toGraphEdgeString() +
1756 "\",decorate];\n" );
1766 protected void traverseHeapRegionNodes( int mode,
1770 HashSet<HeapRegionNode> visited,
1771 boolean writeReferencers
1772 ) throws java.io.IOException {
1774 if( visited.contains( hrn ) ) {
1780 case VISIT_HRN_WRITE_FULL:
1782 String attributes = "[";
1784 if( hrn.isSingleObject() ) {
1785 attributes += "shape=box";
1787 attributes += "shape=Msquare";
1790 if( hrn.isFlagged() ) {
1791 attributes += ",style=filled,fillcolor=lightgrey";
1794 attributes += ",label=\"ID" +
1797 hrn.getDescription() +
1799 hrn.getAlphaString() +
1802 bw.write( " " + hrn.toString() + attributes + ";\n" );
1807 // useful for debugging
1808 if( writeReferencers ) {
1809 OwnershipNode onRef = null;
1810 Iterator refItr = hrn.iteratorToReferencers();
1811 while( refItr.hasNext() ) {
1812 onRef = (OwnershipNode) refItr.next();
1815 case VISIT_HRN_WRITE_FULL:
1816 bw.write( " " + hrn.toString() +
1817 " -> " + onRef.toString() +
1818 "[color=lightgray];\n" );
1824 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
1825 while( childRegionsItr.hasNext() ) {
1826 ReferenceEdge edge = childRegionsItr.next();
1827 HeapRegionNode hrnChild = edge.getDst();
1830 case VISIT_HRN_WRITE_FULL:
1831 bw.write( " " + hrn.toString() +
1832 " -> " + hrnChild.toString() +
1833 "[label=\"" + edge.toGraphEdgeString() +
1834 "\",decorate];\n" );
1838 traverseHeapRegionNodes( mode,