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();
154 removeReferenceEdge( referencer,
156 edge.getFieldDesc() );
161 protected void clearReferenceEdgesTo( HeapRegionNode referencee,
162 FieldDescriptor fieldDesc,
163 boolean removeAll ) {
164 assert referencee != null;
166 // get a copy of the set to iterate over, otherwise
167 // we will be trying to take apart the set as we
168 // are iterating over it, which won't work
169 Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
170 while( i.hasNext() ) {
171 ReferenceEdge edge = i.next();
173 if( removeAll || edge.getFieldDesc() == fieldDesc ) {
174 OwnershipNode referencer = edge.getSrc();
175 removeReferenceEdge( referencer,
177 edge.getFieldDesc() );
183 protected void propagateTokensOverNodes( HeapRegionNode nPrime,
185 HashSet<HeapRegionNode> nodesWithNewAlpha,
186 HashSet<ReferenceEdge> edgesWithNewBeta ) {
188 HashSet<HeapRegionNode> todoNodes
189 = new HashSet<HeapRegionNode>();
190 todoNodes.add( nPrime );
192 HashSet<ReferenceEdge> todoEdges
193 = new HashSet<ReferenceEdge>();
195 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
196 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
197 nodePlannedChanges.put( nPrime, c0 );
199 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
200 = new Hashtable<ReferenceEdge, 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<ReferenceEdge> referItr = n.iteratorToReferencers();
219 while( referItr.hasNext() ) {
220 ReferenceEdge edge = referItr.next();
221 todoEdges.add( edge );
223 if( !edgePlannedChanges.containsKey( edge ) ) {
224 edgePlannedChanges.put( edge, new ChangeTupleSet().makeCanonical() );
227 edgePlannedChanges.put( edge, edgePlannedChanges.get( edge ).union( C ) );
230 Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
231 while( refeeItr.hasNext() ) {
232 ReferenceEdge edgeF = refeeItr.next();
233 HeapRegionNode m = edgeF.getDst();
235 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
237 Iterator<ChangeTuple> itrCprime = C.iterator();
238 while( itrCprime.hasNext() ) {
239 ChangeTuple c = itrCprime.next();
240 if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
241 changesToPass = changesToPass.union( c );
245 if( !changesToPass.isEmpty() ) {
246 if( !nodePlannedChanges.containsKey( m ) ) {
247 nodePlannedChanges.put( m, new ChangeTupleSet().makeCanonical() );
250 ChangeTupleSet currentChanges = nodePlannedChanges.get( m );
252 if( !changesToPass.isSubset( currentChanges ) ) {
254 nodePlannedChanges.put( m, currentChanges.union( changesToPass ) );
260 todoNodes.remove( n );
263 propagateTokensOverEdges( todoEdges, edgePlannedChanges, nodesWithNewAlpha, edgesWithNewBeta );
267 protected void propagateTokensOverEdges(
268 HashSet<ReferenceEdge> todoEdges,
269 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
270 HashSet<HeapRegionNode> nodesWithNewAlpha,
271 HashSet<ReferenceEdge> edgesWithNewBeta ) {
274 while( !todoEdges.isEmpty() ) {
275 ReferenceEdge edgeE = todoEdges.iterator().next();
276 todoEdges.remove( edgeE );
278 if( !edgePlannedChanges.containsKey( edgeE ) ) {
279 edgePlannedChanges.put( edgeE, new ChangeTupleSet().makeCanonical() );
282 ChangeTupleSet C = edgePlannedChanges.get( edgeE );
284 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
286 Iterator<ChangeTuple> itrC = C.iterator();
287 while( itrC.hasNext() ) {
288 ChangeTuple c = itrC.next();
289 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
290 ReachabilitySet withChange = edgeE.getBeta().union( c.getSetToAdd() );
291 edgeE.setBetaNew( edgeE.getBetaNew().union( withChange ) );
292 edgesWithNewBeta.add( edgeE );
293 changesToPass = changesToPass.union( c );
297 OwnershipNode onSrc = edgeE.getSrc();
299 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
300 HeapRegionNode n = (HeapRegionNode) onSrc;
302 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
303 while( referItr.hasNext() ) {
304 ReferenceEdge edgeF = referItr.next();
306 if( !edgePlannedChanges.containsKey( edgeF ) ) {
307 edgePlannedChanges.put( edgeF, new ChangeTupleSet().makeCanonical() );
310 ChangeTupleSet currentChanges = edgePlannedChanges.get( edgeF );
312 if( !changesToPass.isSubset( currentChanges ) ) {
313 todoEdges.add( edgeF );
314 edgePlannedChanges.put( edgeF, currentChanges.union( changesToPass ) );
322 ////////////////////////////////////////////////////
324 // Assignment Operation Methods
326 // These methods are high-level operations for
327 // modeling program assignment statements using
328 // the low-level reference create/remove methods
331 // The destination in an assignment statement is
332 // going to have new references. The method of
333 // determining the references depends on the type
334 // of the FlatNode assignment and the predicates
335 // of the nodes and edges involved.
337 ////////////////////////////////////////////////////
338 public void assignTempYToTempX( TempDescriptor y,
341 LabelNode lnX = getLabelNodeFromTemp( x );
342 LabelNode lnY = getLabelNodeFromTemp( y );
344 clearReferenceEdgesFrom( lnX, null, true );
346 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
347 while( itrYhrn.hasNext() ) {
348 ReferenceEdge edgeY = itrYhrn.next();
349 HeapRegionNode referencee = edgeY.getDst();
350 ReferenceEdge edgeNew = edgeY.copy();
351 edgeNew.setSrc( lnX );
353 addReferenceEdge( lnX, referencee, edgeNew );
358 public void assignTempYFieldFToTempX( TempDescriptor y,
362 LabelNode lnX = getLabelNodeFromTemp( x );
363 LabelNode lnY = getLabelNodeFromTemp( y );
365 clearReferenceEdgesFrom( lnX, null, true );
367 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
368 while( itrYhrn.hasNext() ) {
369 ReferenceEdge edgeY = itrYhrn.next();
370 HeapRegionNode hrnY = edgeY.getDst();
371 ReachabilitySet betaY = edgeY.getBeta();
373 Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
374 while( itrHrnFhrn.hasNext() ) {
375 ReferenceEdge edgeHrn = itrHrnFhrn.next();
376 HeapRegionNode hrnHrn = edgeHrn.getDst();
377 ReachabilitySet betaHrn = edgeHrn.getBeta();
379 if( edgeHrn.getFieldDesc() == null ||
380 edgeHrn.getFieldDesc() == f ) {
382 ReferenceEdge edgeNew = new ReferenceEdge( lnX,
386 betaY.intersection( betaHrn ) );
388 addReferenceEdge( lnX, hrnHrn, edgeNew );
395 public void assignTempYToTempXFieldF( TempDescriptor y,
397 FieldDescriptor f ) {
399 LabelNode lnX = getLabelNodeFromTemp( x );
400 LabelNode lnY = getLabelNodeFromTemp( y );
402 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
403 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
405 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
406 while( itrXhrn.hasNext() ) {
407 ReferenceEdge edgeX = itrXhrn.next();
408 HeapRegionNode hrnX = edgeX.getDst();
409 ReachabilitySet betaX = edgeX.getBeta();
411 ReachabilitySet R = hrnX.getAlpha().intersection( edgeX.getBeta() );
413 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
414 while( itrYhrn.hasNext() ) {
415 ReferenceEdge edgeY = itrYhrn.next();
416 HeapRegionNode hrnY = edgeY.getDst();
417 ReachabilitySet O = edgeY.getBeta();
419 // propagate tokens over nodes starting from hrnSrc, and it will
420 // take care of propagating back up edges from any touched nodes
421 ChangeTupleSet Cy = O.unionUpArityToChangeSet( R );
422 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
425 // then propagate back just up the edges from hrn
426 ChangeTupleSet Cx = R.unionUpArityToChangeSet( O );
428 HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
430 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
431 new Hashtable<ReferenceEdge, ChangeTupleSet>();
433 Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
434 while( referItr.hasNext() ) {
435 ReferenceEdge edgeUpstream = referItr.next();
436 todoEdges.add( edgeUpstream );
437 edgePlannedChanges.put( edgeUpstream, Cx );
440 propagateTokensOverEdges( todoEdges,
445 // finally, create the actual reference edge hrnX.f -> hrnY
446 ReferenceEdge edgeNew = new ReferenceEdge( hrnX,
450 edgeY.getBetaNew().pruneBy( hrnX.getAlpha() )
453 addReferenceEdge( hrnX, hrnY, edgeNew );
457 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
458 while( nodeItr.hasNext() ) {
459 nodeItr.next().applyAlphaNew();
462 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
463 while( edgeItr.hasNext() ) {
464 edgeItr.next().applyBetaNew();
469 public void assignParameterAllocationToTemp( boolean isTask,
471 Integer paramIndex ) {
474 LabelNode lnParam = getLabelNodeFromTemp( td );
475 HeapRegionNode hrn = createNewHeapRegionNode( null,
482 "param" + paramIndex );
484 // keep track of heap regions that were created for
485 // parameter labels, the index of the parameter they
486 // are for is important when resolving method calls
487 Integer newID = hrn.getID();
488 assert !id2paramIndex.containsKey ( newID );
489 assert !id2paramIndex.containsValue( paramIndex );
490 id2paramIndex.put( newID, paramIndex );
491 paramIndex2id.put( paramIndex, newID );
493 ReachabilitySet beta = new ReachabilitySet( new TokenTuple( newID,
495 TokenTuple.ARITY_ONE ) );
497 // heap regions for parameters are always multiple object (see above)
498 // and have a reference to themselves, because we can't know the
499 // structure of memory that is passed into the method. We're assuming
502 ReferenceEdge edgeFromLabel =
503 new ReferenceEdge( lnParam, hrn, null, false, beta );
505 ReferenceEdge edgeReflexive =
506 new ReferenceEdge( hrn, hrn, null, true, beta );
508 addReferenceEdge( lnParam, hrn, edgeFromLabel );
509 addReferenceEdge( hrn, hrn, edgeReflexive );
513 public void assignNewAllocationToTempX( TempDescriptor x,
514 AllocationSite as ) {
520 // after the age operation the newest (or zero-ith oldest)
521 // node associated with the allocation site should have
522 // no references to it as if it were a newly allocated
523 // heap region, so make a reference to it to complete
526 Integer idNewest = as.getIthOldest( 0 );
527 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
528 assert hrnNewest != null;
530 LabelNode lnX = getLabelNodeFromTemp( x );
531 clearReferenceEdgesFrom( lnX, null, true );
533 ReferenceEdge edgeNew =
534 new ReferenceEdge( lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
536 addReferenceEdge( lnX, hrnNewest, edgeNew );
540 // use the allocation site (unique to entire analysis) to
541 // locate the heap region nodes in this ownership graph
542 // that should be aged. The process models the allocation
543 // of new objects and collects all the oldest allocations
544 // in a summary node to allow for a finite analysis
546 // There is an additional property of this method. After
547 // running it on a particular ownership graph (many graphs
548 // may have heap regions related to the same allocation site)
549 // the heap region node objects in this ownership graph will be
550 // allocated. Therefore, after aging a graph for an allocation
551 // site, attempts to retrieve the heap region nodes using the
552 // integer id's contained in the allocation site should always
553 // return non-null heap regions.
554 public void age( AllocationSite as ) {
556 // aging adds this allocation site to the graph's
557 // list of sites that exist in the graph, or does
558 // nothing if the site is already in the list
559 allocationSites.add( as );
561 // get the summary node for the allocation site in the context
562 // of this particular ownership graph
563 HeapRegionNode hrnSummary = getSummaryNode( as );
565 // merge oldest node into summary
566 Integer idK = as.getOldest();
567 HeapRegionNode hrnK = id2hrn.get( idK );
568 mergeIntoSummary( hrnK, hrnSummary );
570 // move down the line of heap region nodes
571 // clobbering the ith and transferring all references
572 // to and from i-1 to node i. Note that this clobbers
573 // the oldest node (hrnK) that was just merged into
575 for( int i = allocationDepth - 1; i > 0; --i ) {
577 // move references from the i-1 oldest to the ith oldest
578 Integer idIth = as.getIthOldest( i );
579 HeapRegionNode hrnI = id2hrn.get( idIth );
580 Integer idImin1th = as.getIthOldest( i - 1 );
581 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
583 transferOnto( hrnImin1, hrnI );
586 // as stated above, the newest node should have had its
587 // references moved over to the second oldest, so we wipe newest
588 // in preparation for being the new object to assign something to
589 Integer id0th = as.getIthOldest( 0 );
590 HeapRegionNode hrn0 = id2hrn.get( id0th );
593 // clear all references in and out of newest node
594 clearReferenceEdgesFrom( hrn0, null, true );
595 clearReferenceEdgesTo ( hrn0, null, true );
598 // now tokens in reachability sets need to "age" also
599 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
600 while( itrAllLabelNodes.hasNext() ) {
601 Map.Entry me = (Map.Entry) itrAllLabelNodes.next();
602 LabelNode ln = (LabelNode) me.getValue();
604 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
605 while( itrEdges.hasNext() ) {
606 ageTokens( as, itrEdges.next() );
610 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
611 while( itrAllHRNodes.hasNext() ) {
612 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
613 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
615 ageTokens( as, hrnToAge );
617 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
618 while( itrEdges.hasNext() ) {
619 ageTokens( as, itrEdges.next() );
624 // after tokens have been aged, reset newest node's reachability
625 hrn0.setAlpha( new ReachabilitySet(
627 new TokenTuple( hrn0 )
634 protected HeapRegionNode getSummaryNode( AllocationSite as ) {
636 Integer idSummary = as.getSummary();
637 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
639 // If this is null then we haven't touched this allocation site
640 // in the context of the current ownership graph, so allocate
641 // heap region nodes appropriate for the entire allocation site.
642 // This should only happen once per ownership graph per allocation site,
643 // and a particular integer id can be used to locate the heap region
644 // in different ownership graphs that represents the same part of an
646 if( hrnSummary == null ) {
648 boolean hasFlags = false;
649 if( as.getType().isClass() ) {
650 hasFlags = as.getType().getClassDesc().hasFlags();
653 hrnSummary = createNewHeapRegionNode( idSummary,
660 as + "\\n" + as.getType() + "\\nsummary" );
662 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
663 Integer idIth = as.getIthOldest( i );
664 assert !id2hrn.containsKey( idIth );
665 createNewHeapRegionNode( idIth,
672 as + "\\n" + as.getType() + "\\n" + i + " oldest" );
680 protected HeapRegionNode getShadowSummaryNode( AllocationSite as ) {
682 Integer idShadowSummary = -(as.getSummary());
683 HeapRegionNode hrnShadowSummary = id2hrn.get( idShadowSummary );
685 if( hrnShadowSummary == null ) {
687 boolean hasFlags = false;
688 if( as.getType().isClass() ) {
689 hasFlags = as.getType().getClassDesc().hasFlags();
692 hrnShadowSummary = createNewHeapRegionNode( idShadowSummary,
699 as + "\\n" + as.getType() + "\\nshadowSum" );
701 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
702 Integer idShadowIth = -(as.getIthOldest( i ));
703 assert !id2hrn.containsKey( idShadowIth );
704 createNewHeapRegionNode( idShadowIth,
711 as + "\\n" + as.getType() + "\\n" + i + " shadow" );
715 return hrnShadowSummary;
719 protected void mergeIntoSummary( HeapRegionNode hrn, HeapRegionNode hrnSummary ) {
720 assert hrnSummary.isNewSummary();
722 // transfer references _from_ hrn over to hrnSummary
723 Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
724 while( itrReferencee.hasNext() ) {
725 ReferenceEdge edge = itrReferencee.next();
726 ReferenceEdge edgeMerged = edge.copy();
727 edgeMerged.setSrc( hrnSummary );
729 HeapRegionNode hrnReferencee = edge.getDst();
730 ReferenceEdge edgeSummary = hrnSummary.getReferenceTo( hrnReferencee, edge.getFieldDesc() );
732 if( edgeSummary == null ) {
733 // the merge is trivial, nothing to be done
735 // otherwise an edge from the referencer to hrnSummary exists already
736 // and the edge referencer->hrn should be merged with it
737 edgeMerged.setBeta( edgeMerged.getBeta().union( edgeSummary.getBeta() ) );
740 addReferenceEdge( hrnSummary, hrnReferencee, edgeMerged );
743 // next transfer references _to_ hrn over to hrnSummary
744 Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
745 while( itrReferencer.hasNext() ) {
746 ReferenceEdge edge = itrReferencer.next();
747 ReferenceEdge edgeMerged = edge.copy();
748 edgeMerged.setDst( hrnSummary );
750 OwnershipNode onReferencer = edge.getSrc();
751 ReferenceEdge edgeSummary = onReferencer.getReferenceTo( hrnSummary, edge.getFieldDesc() );
753 if( edgeSummary == null ) {
754 // the merge is trivial, nothing to be done
756 // otherwise an edge from the referencer to alpha_S exists already
757 // and the edge referencer->alpha_K should be merged with it
758 edgeMerged.setBeta( edgeMerged.getBeta().union( edgeSummary.getBeta() ) );
761 addReferenceEdge( onReferencer, hrnSummary, edgeMerged );
764 // then merge hrn reachability into hrnSummary
765 hrnSummary.setAlpha( hrnSummary.getAlpha().union( hrn.getAlpha() ) );
769 protected void transferOnto( HeapRegionNode hrnA, HeapRegionNode hrnB ) {
771 // clear references in and out of node i
772 clearReferenceEdgesFrom( hrnB, null, true );
773 clearReferenceEdgesTo ( hrnB, null, true );
775 // copy each edge in and out of A to B
776 Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
777 while( itrReferencee.hasNext() ) {
778 ReferenceEdge edge = itrReferencee.next();
779 HeapRegionNode hrnReferencee = edge.getDst();
780 ReferenceEdge edgeNew = edge.copy();
781 edgeNew.setSrc( hrnB );
783 addReferenceEdge( hrnB, hrnReferencee, edgeNew );
786 Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
787 while( itrReferencer.hasNext() ) {
788 ReferenceEdge edge = itrReferencer.next();
789 OwnershipNode onReferencer = edge.getSrc();
790 ReferenceEdge edgeNew = edge.copy();
791 edgeNew.setDst( hrnB );
793 addReferenceEdge( onReferencer, hrnB, edgeNew );
796 // replace hrnB reachability with hrnA's
797 hrnB.setAlpha( hrnA.getAlpha() );
801 protected void ageTokens( AllocationSite as, ReferenceEdge edge ) {
802 edge.setBeta( edge.getBeta().ageTokens( as ) );
805 protected void ageTokens( AllocationSite as, HeapRegionNode hrn ) {
806 hrn.setAlpha( hrn.getAlpha().ageTokens( as ) );
809 protected void majorAgeTokens( AllocationSite as, ReferenceEdge edge ) {
810 //edge.setBeta( edge.getBeta().majorAgeTokens( as ) );
813 protected void majorAgeTokens( AllocationSite as, HeapRegionNode hrn ) {
814 //hrn.setAlpha( hrn.getAlpha().majorAgeTokens( as ) );
819 // the heap regions that are specially allocated as multiple-object
820 // regions for method parameters need to be remembered in order to
821 // resolve a function call. So actually, we need a mapping from
822 // caller argument descriptors to the callee parameter heap regions
823 // to apply reference edges in the callee to the caller graph.
825 // also, Constructors and virtual dispatch methods have a "this"
826 // argument that make the mapping of arguments to parameters a little
827 // tricky. What happens to that this region?
830 public void resolveMethodCall( FlatCall fc,
833 OwnershipGraph ogCallee ) {
836 // verify the existence of allocation sites and their
837 // shadows from the callee in the context of this caller graph
838 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
839 while( asItr.hasNext() ) {
840 AllocationSite allocSite = asItr.next();
841 HeapRegionNode hrnSummary = getSummaryNode ( allocSite );
842 HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
845 // in non-static methods there is a "this" pointer
846 // that should be taken into account
848 assert fc.numArgs() == fm.numParameters();
850 assert fc.numArgs() + 1 == fm.numParameters();
853 // make a change set to translate callee tokens into caller tokens
854 ChangeTupleSet C = new ChangeTupleSet().makeCanonical();
856 for( int i = 0; i < fm.numParameters(); ++i ) {
858 Integer indexParam = new Integer( i );
860 System.out.println( "In method "+fm+ " on param "+indexParam );
862 assert ogCallee.paramIndex2id.containsKey( indexParam );
863 Integer idParam = ogCallee.paramIndex2id.get( indexParam );
865 assert ogCallee.id2hrn.containsKey( idParam );
866 HeapRegionNode hrnParam = ogCallee.id2hrn.get( idParam );
867 assert hrnParam != null;
869 TokenTupleSet calleeTokenToMatch =
870 new TokenTupleSet( new TokenTuple( hrnParam ) ).makeCanonical();
873 // now depending on whether the callee is static or not
874 // we need to account for a "this" argument in order to
875 // find the matching argument in the caller context
876 TempDescriptor argTemp;
878 argTemp = fc.getArg( indexParam );
880 if( indexParam == 0 ) {
881 argTemp = fc.getThis();
883 argTemp = fc.getArg( indexParam - 1 );
887 LabelNode argLabel = getLabelNodeFromTemp( argTemp );
888 Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
889 while( argHeapRegionsItr.hasNext() ) {
890 Map.Entry meArg = (Map.Entry) argHeapRegionsItr.next();
891 HeapRegionNode argHeapRegion = (HeapRegionNode) meArg.getKey();
892 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
894 Iterator<TokenTupleSet> ttsItr = repArg.getBeta().iterator();
895 while( ttsItr.hasNext() ) {
896 TokenTupleSet callerTokensToReplace = ttsItr.next();
898 ChangeTuple ct = new ChangeTuple( calleeTokenToMatch,
899 callerTokensToReplace ).makeCanonical();
906 System.out.println( "Applying method call "+fm );
907 System.out.println( " Change: "+C );
910 // the heap regions represented by the arguments (caller graph)
911 // and heap regions for the parameters (callee graph)
912 // don't correspond to each other by heap region ID. In fact,
913 // an argument label node can be referencing several heap regions
914 // so the parameter label always references a multiple-object
915 // heap region in order to handle the range of possible contexts
916 // for a method call. This means we need to make a special mapping
917 // of argument->parameter regions in order to update the caller graph
919 // for every heap region->heap region edge in the
920 // callee graph, create the matching edge or edges
921 // in the caller graph
922 Set sCallee = ogCallee.id2hrn.entrySet();
923 Iterator iCallee = sCallee.iterator();
924 while( iCallee.hasNext() ) {
925 Map.Entry meCallee = (Map.Entry) iCallee.next();
926 Integer idCallee = (Integer) meCallee.getKey();
927 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
929 HeapRegionNode hrnChildCallee = null;
930 Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
931 while( heapRegionsItrCallee.hasNext() ) {
932 Map.Entry me = (Map.Entry) heapRegionsItrCallee.next();
933 hrnChildCallee = (HeapRegionNode) me.getKey();
934 ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
936 Integer idChildCallee = hrnChildCallee.getID();
938 // only address this edge if it is not a special reflexive edge
939 if( !repC.isInitialParamReflexive() ) {
941 // now we know that in the callee method's ownership graph
942 // there is a heap region->heap region reference edge given
943 // by heap region pointers:
944 // hrnCallee -> heapChildCallee
946 // or by the ownership-graph independent ID's:
947 // idCallee -> idChildCallee
949 // So now make a set of possible source heaps in the caller graph
950 // and a set of destination heaps in the caller graph, and make
951 // a reference edge in the caller for every possible (src,dst) pair
952 HashSet<HeapRegionNode> possibleCallerSrcs =
953 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
958 HashSet<HeapRegionNode> possibleCallerDsts =
959 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
964 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
965 Iterator srcItr = possibleCallerSrcs.iterator();
966 while( srcItr.hasNext() ) {
967 HeapRegionNode src = (HeapRegionNode) srcItr.next();
969 Iterator dstItr = possibleCallerDsts.iterator();
970 while( dstItr.hasNext() ) {
971 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
973 addReferenceEdge( src, dst, repC.copy() );
983 private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
988 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
990 if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
991 // the heap region that is part of this
992 // reference edge won't have a matching ID in the
993 // caller graph because it is specifically allocated
994 // for a particular parameter. Use that information
995 // to find the corresponding argument label in the
996 // caller in order to create the proper reference edge
998 assert !id2hrn.containsKey( idCallee );
1000 Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
1001 TempDescriptor argTemp;
1003 // now depending on whether the callee is static or not
1004 // we need to account for a "this" argument in order to
1005 // find the matching argument in the caller context
1007 argTemp = fc.getArg( paramIndex );
1009 if( paramIndex == 0 ) {
1010 argTemp = fc.getThis();
1012 argTemp = fc.getArg( paramIndex - 1 );
1016 LabelNode argLabel = getLabelNodeFromTemp( argTemp );
1017 Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
1018 while( argHeapRegionsItr.hasNext() ) {
1019 Map.Entry meArg = (Map.Entry) argHeapRegionsItr.next();
1020 HeapRegionNode argHeapRegion = (HeapRegionNode) meArg.getKey();
1021 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
1023 possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
1027 // this heap region is not a parameter, so it should
1028 // have a matching heap region in the caller graph
1029 assert id2hrn.containsKey( idCallee );
1030 possibleCallerHRNs.add( id2hrn.get( idCallee ) );
1033 return possibleCallerHRNs;
1038 ////////////////////////////////////////////////////
1039 // in merge() and equals() methods the suffix A
1040 // represents the passed in graph and the suffix
1041 // B refers to the graph in this object
1042 // Merging means to take the incoming graph A and
1043 // merge it into B, so after the operation graph B
1044 // is the final result.
1045 ////////////////////////////////////////////////////
1046 public void merge( OwnershipGraph og ) {
1052 mergeOwnershipNodes ( og );
1053 mergeReferenceEdges ( og );
1054 mergeId2paramIndex ( og );
1055 mergeAllocationSites( og );
1059 protected void mergeOwnershipNodes( OwnershipGraph og ) {
1060 Set sA = og.id2hrn.entrySet();
1061 Iterator iA = sA.iterator();
1062 while( iA.hasNext() ) {
1063 Map.Entry meA = (Map.Entry) iA.next();
1064 Integer idA = (Integer) meA.getKey();
1065 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1067 // if this graph doesn't have a node the
1068 // incoming graph has, allocate it
1069 if( !id2hrn.containsKey( idA ) ) {
1070 HeapRegionNode hrnB = hrnA.copy();
1071 id2hrn.put( idA, hrnB );
1074 // otherwise this is a node present in both graphs
1075 // so make the new reachability set a union of the
1076 // nodes' reachability sets
1077 HeapRegionNode hrnB = id2hrn.get( idA );
1078 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
1082 // now add any label nodes that are in graph B but
1084 sA = og.td2ln.entrySet();
1086 while( iA.hasNext() ) {
1087 Map.Entry meA = (Map.Entry) iA.next();
1088 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1089 LabelNode lnA = (LabelNode) meA.getValue();
1091 // if the label doesn't exist in B, allocate and add it
1092 LabelNode lnB = getLabelNodeFromTemp( tdA );
1096 protected void mergeReferenceEdges( OwnershipGraph og ) {
1099 Set sA = og.id2hrn.entrySet();
1100 Iterator iA = sA.iterator();
1101 while( iA.hasNext() ) {
1102 Map.Entry meA = (Map.Entry) iA.next();
1103 Integer idA = (Integer) meA.getKey();
1104 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1106 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1107 while( heapRegionsItrA.hasNext() ) {
1108 ReferenceEdge edgeA = heapRegionsItrA.next();
1109 HeapRegionNode hrnChildA = edgeA.getDst();
1110 Integer idChildA = hrnChildA.getID();
1112 // at this point we know an edge in graph A exists
1113 // idA -> idChildA, does this exist in B?
1114 assert id2hrn.containsKey( idA );
1115 HeapRegionNode hrnB = id2hrn.get( idA );
1116 ReferenceEdge edgeToMerge = null;
1118 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1119 while( heapRegionsItrB.hasNext() &&
1120 edgeToMerge == null ) {
1122 ReferenceEdge edgeB = heapRegionsItrB.next();
1123 HeapRegionNode hrnChildB = edgeB.getDst();
1124 Integer idChildB = hrnChildB.getID();
1126 // don't use the ReferenceEdge.equals() here because
1127 // we're talking about existence between graphs
1128 if( idChildB.equals( idChildA ) &&
1129 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1130 edgeToMerge = edgeB;
1134 // if the edge from A was not found in B,
1136 if( edgeToMerge == null ) {
1137 assert id2hrn.containsKey( idChildA );
1138 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
1139 edgeToMerge = edgeA.copy();
1140 edgeToMerge.setSrc( hrnB );
1141 edgeToMerge.setDst( hrnChildB );
1142 addReferenceEdge( hrnB, hrnChildB, edgeToMerge );
1144 // otherwise, the edge already existed in both graphs
1145 // so merge their reachability sets
1147 // just replace this beta set with the union
1148 assert edgeToMerge != null;
1149 edgeToMerge.setBeta(
1150 edgeToMerge.getBeta().union( edgeA.getBeta() )
1152 if( !edgeA.isInitialParamReflexive() ) {
1153 edgeToMerge.setIsInitialParamReflexive( false );
1159 // and then again with label nodes
1160 sA = og.td2ln.entrySet();
1162 while( iA.hasNext() ) {
1163 Map.Entry meA = (Map.Entry) iA.next();
1164 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1165 LabelNode lnA = (LabelNode) meA.getValue();
1167 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1168 while( heapRegionsItrA.hasNext() ) {
1169 ReferenceEdge edgeA = heapRegionsItrA.next();
1170 HeapRegionNode hrnChildA = edgeA.getDst();
1171 Integer idChildA = hrnChildA.getID();
1173 // at this point we know an edge in graph A exists
1174 // tdA -> idChildA, does this exist in B?
1175 assert td2ln.containsKey( tdA );
1176 LabelNode lnB = td2ln.get( tdA );
1177 ReferenceEdge edgeToMerge = null;
1179 // labels never have edges with a field
1180 //assert edgeA.getFieldDesc() == null;
1182 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1183 while( heapRegionsItrB.hasNext() &&
1184 edgeToMerge == null ) {
1186 ReferenceEdge edgeB = heapRegionsItrB.next();
1187 HeapRegionNode hrnChildB = edgeB.getDst();
1188 Integer idChildB = hrnChildB.getID();
1190 // labels never have edges with a field
1191 //assert edgeB.getFieldDesc() == null;
1193 // don't use the ReferenceEdge.equals() here because
1194 // we're talking about existence between graphs
1195 if( idChildB.equals( idChildA ) &&
1196 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1197 edgeToMerge = edgeB;
1201 // if the edge from A was not found in B,
1203 if( edgeToMerge == null ) {
1204 assert id2hrn.containsKey( idChildA );
1205 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
1206 edgeToMerge = edgeA.copy();
1207 edgeToMerge.setSrc( lnB );
1208 edgeToMerge.setDst( hrnChildB );
1209 addReferenceEdge( lnB, hrnChildB, edgeToMerge );
1211 // otherwise, the edge already existed in both graphs
1212 // so merge their reachability sets
1214 // just replace this beta set with the union
1215 edgeToMerge.setBeta(
1216 edgeToMerge.getBeta().union( edgeA.getBeta() )
1218 if( !edgeA.isInitialParamReflexive() ) {
1219 edgeToMerge.setIsInitialParamReflexive( false );
1226 // you should only merge ownership graphs that have the
1227 // same number of parameters, or if one or both parameter
1228 // index tables are empty
1229 protected void mergeId2paramIndex( OwnershipGraph og ) {
1230 if( id2paramIndex.size() == 0 ) {
1231 id2paramIndex = og.id2paramIndex;
1232 paramIndex2id = og.paramIndex2id;
1236 if( og.id2paramIndex.size() == 0 ) {
1240 assert id2paramIndex.size() == og.id2paramIndex.size();
1243 protected void mergeAllocationSites( OwnershipGraph og ) {
1244 allocationSites.addAll( og.allocationSites );
1249 // it is necessary in the equals() member functions
1250 // to "check both ways" when comparing the data
1251 // structures of two graphs. For instance, if all
1252 // edges between heap region nodes in graph A are
1253 // present and equal in graph B it is not sufficient
1254 // to say the graphs are equal. Consider that there
1255 // may be edges in graph B that are not in graph A.
1256 // the only way to know that all edges in both graphs
1257 // are equally present is to iterate over both data
1258 // structures and compare against the other graph.
1259 public boolean equals( OwnershipGraph og ) {
1265 if( !areHeapRegionNodesEqual( og ) ) {
1269 if( !areLabelNodesEqual( og ) ) {
1273 if( !areReferenceEdgesEqual( og ) ) {
1277 if( !areId2paramIndexEqual( og ) ) {
1281 // if everything is equal up to this point,
1282 // assert that allocationSites is also equal--
1283 // this data is redundant and kept for efficiency
1284 assert allocationSites.equals( og.allocationSites );
1289 protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
1291 if( !areallHRNinAalsoinBandequal( this, og ) ) {
1295 if( !areallHRNinAalsoinBandequal( og, this ) ) {
1302 static protected boolean areallHRNinAalsoinBandequal( OwnershipGraph ogA,
1303 OwnershipGraph ogB ) {
1304 Set sA = ogA.id2hrn.entrySet();
1305 Iterator iA = sA.iterator();
1306 while( iA.hasNext() ) {
1307 Map.Entry meA = (Map.Entry) iA.next();
1308 Integer idA = (Integer) meA.getKey();
1309 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1311 if( !ogB.id2hrn.containsKey( idA ) ) {
1315 HeapRegionNode hrnB = ogB.id2hrn.get( idA );
1316 if( !hrnA.equalsIncludingAlpha( hrnB ) ) {
1325 protected boolean areLabelNodesEqual( OwnershipGraph og ) {
1327 if( !areallLNinAalsoinBandequal( this, og ) ) {
1331 if( !areallLNinAalsoinBandequal( og, this ) ) {
1338 static protected boolean areallLNinAalsoinBandequal( OwnershipGraph ogA,
1339 OwnershipGraph ogB ) {
1340 Set sA = ogA.td2ln.entrySet();
1341 Iterator iA = sA.iterator();
1342 while( iA.hasNext() ) {
1343 Map.Entry meA = (Map.Entry) iA.next();
1344 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1346 if( !ogB.td2ln.containsKey( tdA ) ) {
1355 protected boolean areReferenceEdgesEqual( OwnershipGraph og ) {
1356 if( !areallREinAandBequal( this, og ) ) {
1363 static protected boolean areallREinAandBequal( OwnershipGraph ogA,
1364 OwnershipGraph ogB ) {
1366 // check all the heap region->heap region edges
1367 Set sA = ogA.id2hrn.entrySet();
1368 Iterator iA = sA.iterator();
1369 while( iA.hasNext() ) {
1370 Map.Entry meA = (Map.Entry) iA.next();
1371 Integer idA = (Integer) meA.getKey();
1372 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1374 // we should have already checked that the same
1375 // heap regions exist in both graphs
1376 assert ogB.id2hrn.containsKey( idA );
1378 if( !areallREfromAequaltoB( ogA, hrnA, ogB ) ) {
1382 // then check every edge in B for presence in A, starting
1383 // from the same parent HeapRegionNode
1384 HeapRegionNode hrnB = ogB.id2hrn.get( idA );
1386 if( !areallREfromAequaltoB( ogB, hrnB, ogA ) ) {
1391 // then check all the label->heap region edges
1392 sA = ogA.td2ln.entrySet();
1394 while( iA.hasNext() ) {
1395 Map.Entry meA = (Map.Entry) iA.next();
1396 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1397 LabelNode lnA = (LabelNode) meA.getValue();
1399 // we should have already checked that the same
1400 // label nodes exist in both graphs
1401 assert ogB.td2ln.containsKey( tdA );
1403 if( !areallREfromAequaltoB( ogA, lnA, ogB ) ) {
1407 // then check every edge in B for presence in A, starting
1408 // from the same parent LabelNode
1409 LabelNode lnB = ogB.td2ln.get( tdA );
1411 if( !areallREfromAequaltoB( ogB, lnB, ogA ) ) {
1420 static protected boolean areallREfromAequaltoB( OwnershipGraph ogA,
1422 OwnershipGraph ogB ) {
1424 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
1425 while( itrA.hasNext() ) {
1426 ReferenceEdge edgeA = itrA.next();
1427 HeapRegionNode hrnChildA = edgeA.getDst();
1428 Integer idChildA = hrnChildA.getID();
1430 assert ogB.id2hrn.containsKey( idChildA );
1432 // at this point we know an edge in graph A exists
1433 // onA -> idChildA, does this exact edge exist in B?
1434 boolean edgeFound = false;
1436 OwnershipNode onB = null;
1437 if( onA instanceof HeapRegionNode ) {
1438 HeapRegionNode hrnA = (HeapRegionNode) onA;
1439 onB = ogB.id2hrn.get( hrnA.getID() );
1441 LabelNode lnA = (LabelNode) onA;
1442 onB = ogB.td2ln.get( lnA.getTempDescriptor() );
1445 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
1446 while( itrB.hasNext() ) {
1447 ReferenceEdge edgeB = itrB.next();
1448 HeapRegionNode hrnChildB = edgeB.getDst();
1449 Integer idChildB = hrnChildB.getID();
1451 if( idChildA.equals( idChildB ) &&
1452 edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
1454 // there is an edge in the right place with the right field,
1455 // but do they have the same attributes?
1456 if( edgeA.isInitialParamReflexive() == edgeB.isInitialParamReflexive() &&
1457 edgeA.getBeta().equals( edgeB.getBeta() ) ) {
1475 protected boolean areId2paramIndexEqual( OwnershipGraph og ) {
1476 return id2paramIndex.size() == og.id2paramIndex.size();
1481 // given a set B of heap region node ID's, return the set of heap
1482 // region node ID's that is reachable from B
1483 public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1485 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1486 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1488 // initial nodes to visit are from set B
1489 Iterator initialItr = idSetB.iterator();
1490 while( initialItr.hasNext() ) {
1491 Integer idInitial = (Integer) initialItr.next();
1492 assert id2hrn.contains( idInitial );
1493 HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1494 toVisit.add( hrnInitial );
1497 HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1499 // do a heap traversal
1500 while( !toVisit.isEmpty() ) {
1501 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1502 toVisit.remove( hrnVisited );
1503 visited.add ( hrnVisited );
1505 // for every node visited, add it to the total
1507 idSetReachableFromB.add( hrnVisited.getID() );
1509 // find other reachable nodes
1510 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1511 while( referenceeItr.hasNext() ) {
1512 Map.Entry me = (Map.Entry) referenceeItr.next();
1513 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1514 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1516 if( !visited.contains( hrnReferencee ) ) {
1517 toVisit.add( hrnReferencee );
1522 return idSetReachableFromB;
1526 // used to find if a heap region can possibly have a reference to
1527 // any of the heap regions in the given set
1528 // if the id supplied is in the set, then a self-referencing edge
1529 // would return true, but that special case is specifically allowed
1530 // meaning that it isn't an external alias
1531 public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1533 assert id2hrn.contains( id );
1534 HeapRegionNode hrn = id2hrn.get( id );
1537 //HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1539 //Iterator i = idSet.iterator();
1540 //while( i.hasNext() ) {
1541 // Integer idFromSet = (Integer) i.next();
1542 // assert id2hrn.contains( idFromSet );
1543 // hrnSet.add( id2hrn.get( idFromSet ) );
1547 // do a traversal from hrn and see if any of the
1548 // heap regions from the set come up during that
1549 HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1550 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1553 while( !toVisit.isEmpty() ) {
1554 HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1555 toVisit.remove( hrnVisited );
1556 visited.add ( hrnVisited );
1558 Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1559 while( referenceeItr.hasNext() ) {
1560 Map.Entry me = (Map.Entry) referenceeItr.next();
1561 HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
1562 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1564 if( idSet.contains( hrnReferencee.getID() ) ) {
1565 if( !id.equals( hrnReferencee.getID() ) ) {
1570 if( !visited.contains( hrnReferencee ) ) {
1571 toVisit.add( hrnReferencee );
1581 // for writing ownership graphs to dot files
1582 public void writeGraph( Descriptor methodDesc,
1584 boolean writeLabels,
1585 boolean labelSelect,
1586 boolean pruneGarbage,
1587 boolean writeReferencers
1588 ) throws java.io.IOException {
1590 methodDesc.getSymbol() +
1591 methodDesc.getNum() +
1600 public void writeGraph( Descriptor methodDesc,
1602 boolean writeLabels,
1603 boolean writeReferencers
1604 ) throws java.io.IOException {
1606 methodDesc.getSymbol() +
1607 methodDesc.getNum() +
1616 public void writeGraph( Descriptor methodDesc,
1617 boolean writeLabels,
1618 boolean writeReferencers
1619 ) throws java.io.IOException {
1621 methodDesc.getSymbol() +
1622 methodDesc.getNum() +
1631 public void writeGraph( Descriptor methodDesc,
1632 boolean writeLabels,
1633 boolean labelSelect,
1634 boolean pruneGarbage,
1635 boolean writeReferencers
1636 ) throws java.io.IOException {
1638 methodDesc.getSymbol() +
1639 methodDesc.getNum() +
1648 public void writeGraph( String graphName,
1649 boolean writeLabels,
1650 boolean labelSelect,
1651 boolean pruneGarbage,
1652 boolean writeReferencers
1653 ) throws java.io.IOException {
1655 // remove all non-word characters from the graph name so
1656 // the filename and identifier in dot don't cause errors
1657 graphName = graphName.replaceAll( "[\\W]", "" );
1659 BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
1660 bw.write( "digraph "+graphName+" {\n" );
1661 //bw.write( " size=\"7.5,10\";\n" );
1663 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1665 // then visit every heap region node
1666 if( !pruneGarbage ) {
1667 Set s = id2hrn.entrySet();
1668 Iterator i = s.iterator();
1669 while( i.hasNext() ) {
1670 Map.Entry me = (Map.Entry) i.next();
1671 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1672 if( !visited.contains( hrn ) ) {
1673 traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1683 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
1686 // then visit every label node, useful for debugging
1688 Set s = td2ln.entrySet();
1689 Iterator i = s.iterator();
1690 while( i.hasNext() ) {
1691 Map.Entry me = (Map.Entry) i.next();
1692 LabelNode ln = (LabelNode) me.getValue();
1695 String labelStr = ln.getTempDescriptorString();
1696 if( labelStr.startsWith( "___temp" ) ||
1697 labelStr.startsWith( "___dst" ) ||
1698 labelStr.startsWith( "___srctmp" ) ||
1699 labelStr.startsWith( "___neverused" ) ) {
1704 bw.write( ln.toString() + ";\n" );
1706 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
1707 while( heapRegionsItr.hasNext() ) {
1708 ReferenceEdge edge = heapRegionsItr.next();
1709 HeapRegionNode hrn = edge.getDst();
1711 if( pruneGarbage && !visited.contains( hrn ) ) {
1712 traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1720 bw.write( " " + ln.toString() +
1721 " -> " + hrn.toString() +
1722 "[label=\"" + edge.toGraphEdgeString() +
1723 "\",decorate];\n" );
1733 protected void traverseHeapRegionNodes( int mode,
1737 HashSet<HeapRegionNode> visited,
1738 boolean writeReferencers
1739 ) throws java.io.IOException {
1741 if( visited.contains( hrn ) ) {
1747 case VISIT_HRN_WRITE_FULL:
1749 String attributes = "[";
1751 if( hrn.isSingleObject() ) {
1752 attributes += "shape=box";
1754 attributes += "shape=Msquare";
1757 if( hrn.isFlagged() ) {
1758 attributes += ",style=filled,fillcolor=lightgrey";
1761 attributes += ",label=\"ID" +
1764 hrn.getDescription() +
1766 hrn.getAlphaString() +
1769 bw.write( " " + hrn.toString() + attributes + ";\n" );
1774 // useful for debugging
1775 if( writeReferencers ) {
1776 OwnershipNode onRef = null;
1777 Iterator refItr = hrn.iteratorToReferencers();
1778 while( refItr.hasNext() ) {
1779 onRef = (OwnershipNode) refItr.next();
1782 case VISIT_HRN_WRITE_FULL:
1783 bw.write( " " + hrn.toString() +
1784 " -> " + onRef.toString() +
1785 "[color=lightgray];\n" );
1791 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
1792 while( childRegionsItr.hasNext() ) {
1793 ReferenceEdge edge = childRegionsItr.next();
1794 HeapRegionNode hrnChild = edge.getDst();
1797 case VISIT_HRN_WRITE_FULL:
1798 bw.write( " " + hrn.toString() +
1799 " -> " + hrnChild.toString() +
1800 "[label=\"" + edge.toGraphEdgeString() +
1801 "\",decorate];\n" );
1805 traverseHeapRegionNodes( mode,