1 package Analysis.Disjoint;
5 import Util.UtilAlgorithms;
9 public class ReachGraph {
11 // use to disable improvements for comparison
12 protected static final boolean DISABLE_STRONG_UPDATES = false;
13 protected static final boolean DISABLE_GLOBAL_SWEEP = true;
15 // a special out-of-scope temp
16 protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
18 // some frequently used reachability constants
19 protected static final ReachState rstateEmpty = new ReachState().makeCanonical();
20 protected static final ReachSet rsetEmpty = new ReachSet().makeCanonical();
21 protected static final ReachSet rsetWithEmptyState = new ReachSet( rstateEmpty ).makeCanonical();
23 // predicate constants
24 protected static final ExistPredTrue predTrue = new ExistPredTrue();
25 protected static final ExistPredSet predsEmpty = new ExistPredSet().makeCanonical();
26 protected static final ExistPredSet predsTrue = new ExistPredSet( predTrue ).makeCanonical();
29 // from DisjointAnalysis for convenience
30 protected static int allocationDepth = -1;
31 protected static TypeUtil typeUtil = null;
34 // variable and heap region nodes indexed by unique ID
35 public Hashtable<Integer, HeapRegionNode> id2hrn;
36 public Hashtable<TempDescriptor, VariableNode > td2vn;
38 // convenient set of alloc sites for all heap regions
39 // present in the graph without having to search
40 public HashSet<AllocSite> allocSites;
43 id2hrn = new Hashtable<Integer, HeapRegionNode>();
44 td2vn = new Hashtable<TempDescriptor, VariableNode >();
45 allocSites = new HashSet<AllocSite>();
49 // temp descriptors are globally unique and map to
50 // exactly one variable node, easy
51 protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
54 if( !td2vn.containsKey( td ) ) {
55 td2vn.put( td, new VariableNode( td ) );
58 return td2vn.get( td );
61 public boolean hasVariable( TempDescriptor td ) {
62 return td2vn.containsKey( td );
66 // the reason for this method is to have the option
67 // of creating new heap regions with specific IDs, or
68 // duplicating heap regions with specific IDs (especially
69 // in the merge() operation) or to create new heap
70 // regions with a new unique ID
71 protected HeapRegionNode
72 createNewHeapRegionNode( Integer id,
73 boolean isSingleObject,
76 boolean isOutOfContext,
85 boolean markForAnalysis = isFlagged;
87 TypeDescriptor typeToUse = null;
88 if( allocSite != null ) {
89 typeToUse = allocSite.getType();
90 allocSites.add( allocSite );
95 if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
96 markForAnalysis = true;
100 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
103 if( inherent == null ) {
104 if( markForAnalysis ) {
105 inherent = new ReachSet(
112 inherent = rsetWithEmptyState;
116 if( alpha == null ) {
120 if( preds == null ) {
121 // TODO: do this right? For out-of-context nodes?
122 preds = new ExistPredSet().makeCanonical();
125 HeapRegionNode hrn = new HeapRegionNode( id,
136 id2hrn.put( id, hrn );
142 ////////////////////////////////////////////////
144 // Low-level referencee and referencer methods
146 // These methods provide the lowest level for
147 // creating references between reachability nodes
148 // and handling the details of maintaining both
149 // list of referencers and referencees.
151 ////////////////////////////////////////////////
152 protected void addRefEdge( RefSrcNode referencer,
153 HeapRegionNode referencee,
155 assert referencer != null;
156 assert referencee != null;
158 assert edge.getSrc() == referencer;
159 assert edge.getDst() == referencee;
161 referencer.addReferencee( edge );
162 referencee.addReferencer( edge );
165 protected void removeRefEdge( RefEdge e ) {
166 removeRefEdge( e.getSrc(),
172 protected void removeRefEdge( RefSrcNode referencer,
173 HeapRegionNode referencee,
176 assert referencer != null;
177 assert referencee != null;
179 RefEdge edge = referencer.getReferenceTo( referencee,
183 assert edge == referencee.getReferenceFrom( referencer,
187 referencer.removeReferencee( edge );
188 referencee.removeReferencer( edge );
191 protected void clearRefEdgesFrom( RefSrcNode referencer,
194 boolean removeAll ) {
195 assert referencer != null;
197 // get a copy of the set to iterate over, otherwise
198 // we will be trying to take apart the set as we
199 // are iterating over it, which won't work
200 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
201 while( i.hasNext() ) {
202 RefEdge edge = i.next();
205 (edge.typeEquals( type ) && edge.fieldEquals( field ))
208 HeapRegionNode referencee = edge.getDst();
210 removeRefEdge( referencer,
218 protected void clearRefEdgesTo( HeapRegionNode referencee,
221 boolean removeAll ) {
222 assert referencee != null;
224 // get a copy of the set to iterate over, otherwise
225 // we will be trying to take apart the set as we
226 // are iterating over it, which won't work
227 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
228 while( i.hasNext() ) {
229 RefEdge edge = i.next();
232 (edge.typeEquals( type ) && edge.fieldEquals( field ))
235 RefSrcNode referencer = edge.getSrc();
237 removeRefEdge( referencer,
246 ////////////////////////////////////////////////////
248 // Assignment Operation Methods
250 // These methods are high-level operations for
251 // modeling program assignment statements using
252 // the low-level reference create/remove methods
255 ////////////////////////////////////////////////////
257 public void assignTempXEqualToTempY( TempDescriptor x,
259 assignTempXEqualToCastedTempY( x, y, null );
262 public void assignTempXEqualToCastedTempY( TempDescriptor x,
264 TypeDescriptor tdCast ) {
266 VariableNode lnX = getVariableNodeFromTemp( x );
267 VariableNode lnY = getVariableNodeFromTemp( y );
269 clearRefEdgesFrom( lnX, null, null, true );
271 // note it is possible that the types of temps in the
272 // flat node to analyze will reveal that some typed
273 // edges in the reachability graph are impossible
274 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
276 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
277 while( itrYhrn.hasNext() ) {
278 RefEdge edgeY = itrYhrn.next();
279 HeapRegionNode referencee = edgeY.getDst();
280 RefEdge edgeNew = edgeY.copy();
282 if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
283 impossibleEdges.add( edgeY );
287 edgeNew.setSrc( lnX );
289 if( tdCast == null ) {
290 edgeNew.setType( mostSpecificType( y.getType(),
296 edgeNew.setType( mostSpecificType( y.getType(),
298 referencee.getType(),
304 edgeNew.setField( null );
306 addRefEdge( lnX, referencee, edgeNew );
309 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
310 while( itrImp.hasNext() ) {
311 RefEdge edgeImp = itrImp.next();
312 removeRefEdge( edgeImp );
317 public void assignTempXEqualToTempYFieldF( TempDescriptor x,
319 FieldDescriptor f ) {
320 VariableNode lnX = getVariableNodeFromTemp( x );
321 VariableNode lnY = getVariableNodeFromTemp( y );
323 clearRefEdgesFrom( lnX, null, null, true );
325 // note it is possible that the types of temps in the
326 // flat node to analyze will reveal that some typed
327 // edges in the reachability graph are impossible
328 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
330 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
331 while( itrYhrn.hasNext() ) {
332 RefEdge edgeY = itrYhrn.next();
333 HeapRegionNode hrnY = edgeY.getDst();
334 ReachSet betaY = edgeY.getBeta();
336 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
337 while( itrHrnFhrn.hasNext() ) {
338 RefEdge edgeHrn = itrHrnFhrn.next();
339 HeapRegionNode hrnHrn = edgeHrn.getDst();
340 ReachSet betaHrn = edgeHrn.getBeta();
342 // prune edges that are not a matching field
343 if( edgeHrn.getType() != null &&
344 !edgeHrn.getField().equals( f.getSymbol() )
349 // check for impossible edges
350 if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
351 impossibleEdges.add( edgeHrn );
355 TypeDescriptor tdNewEdge =
356 mostSpecificType( edgeHrn.getType(),
360 RefEdge edgeNew = new RefEdge( lnX,
364 betaY.intersection( betaHrn ),
368 addRefEdge( lnX, hrnHrn, edgeNew );
372 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
373 while( itrImp.hasNext() ) {
374 RefEdge edgeImp = itrImp.next();
375 removeRefEdge( edgeImp );
378 // anytime you might remove edges between heap regions
379 // you must global sweep to clean up broken reachability
380 if( !impossibleEdges.isEmpty() ) {
381 if( !DISABLE_GLOBAL_SWEEP ) {
382 abstractGarbageCollect();
389 public void assignTempXFieldFEqualToTempY( TempDescriptor x,
393 VariableNode lnX = getVariableNodeFromTemp( x );
394 VariableNode lnY = getVariableNodeFromTemp( y );
396 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
397 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
399 // note it is possible that the types of temps in the
400 // flat node to analyze will reveal that some typed
401 // edges in the reachability graph are impossible
402 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
404 // first look for possible strong updates and remove those edges
405 boolean strongUpdate = false;
407 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
408 while( itrXhrn.hasNext() ) {
409 RefEdge edgeX = itrXhrn.next();
410 HeapRegionNode hrnX = edgeX.getDst();
412 // we can do a strong update here if one of two cases holds
414 f != DisjointAnalysis.getArrayField( f.getType() ) &&
415 ( (hrnX.getNumReferencers() == 1) || // case 1
416 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
419 if( !DISABLE_STRONG_UPDATES ) {
421 clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
426 // then do all token propagation
427 itrXhrn = lnX.iteratorToReferencees();
428 while( itrXhrn.hasNext() ) {
429 RefEdge edgeX = itrXhrn.next();
430 HeapRegionNode hrnX = edgeX.getDst();
431 ReachSet betaX = edgeX.getBeta();
432 ReachSet R = hrnX.getAlpha().intersection( edgeX.getBeta() );
434 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
435 while( itrYhrn.hasNext() ) {
436 RefEdge edgeY = itrYhrn.next();
437 HeapRegionNode hrnY = edgeY.getDst();
438 ReachSet O = edgeY.getBeta();
440 // check for impossible edges
441 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
442 impossibleEdges.add( edgeY );
446 // propagate tokens over nodes starting from hrnSrc, and it will
447 // take care of propagating back up edges from any touched nodes
448 ChangeSet Cy = O.unionUpArityToChangeSet( R );
449 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
451 // then propagate back just up the edges from hrn
452 ChangeSet Cx = R.unionUpArityToChangeSet(O);
453 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
455 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
456 new Hashtable<RefEdge, ChangeSet>();
458 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
459 while( referItr.hasNext() ) {
460 RefEdge edgeUpstream = referItr.next();
461 todoEdges.add( edgeUpstream );
462 edgePlannedChanges.put( edgeUpstream, Cx );
465 propagateTokensOverEdges( todoEdges,
472 // apply the updates to reachability
473 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
474 while( nodeItr.hasNext() ) {
475 nodeItr.next().applyAlphaNew();
478 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
479 while( edgeItr.hasNext() ) {
480 edgeItr.next().applyBetaNew();
484 // then go back through and add the new edges
485 itrXhrn = lnX.iteratorToReferencees();
486 while( itrXhrn.hasNext() ) {
487 RefEdge edgeX = itrXhrn.next();
488 HeapRegionNode hrnX = edgeX.getDst();
490 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
491 while( itrYhrn.hasNext() ) {
492 RefEdge edgeY = itrYhrn.next();
493 HeapRegionNode hrnY = edgeY.getDst();
495 // skip impossible edges here, we already marked them
496 // when computing reachability propagations above
497 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
501 // prepare the new reference edge hrnX.f -> hrnY
502 TypeDescriptor tdNewEdge =
503 mostSpecificType( y.getType(),
508 RefEdge edgeNew = new RefEdge( hrnX,
512 edgeY.getBeta().pruneBy( hrnX.getAlpha() ),
516 // look to see if an edge with same field exists
517 // and merge with it, otherwise just add the edge
518 RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
522 if( edgeExisting != null ) {
523 edgeExisting.setBeta(
524 edgeExisting.getBeta().union( edgeNew.getBeta() )
526 edgeExisting.setPreds(
527 edgeExisting.getPreds().join( edgeNew.getPreds() )
531 addRefEdge( hrnX, hrnY, edgeNew );
536 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
537 while( itrImp.hasNext() ) {
538 RefEdge edgeImp = itrImp.next();
539 removeRefEdge( edgeImp );
542 // if there was a strong update, make sure to improve
543 // reachability with a global sweep
544 if( strongUpdate || !impossibleEdges.isEmpty() ) {
545 if( !DISABLE_GLOBAL_SWEEP ) {
546 abstractGarbageCollect();
553 public void assignReturnEqualToTemp( TempDescriptor x ) {
555 VariableNode lnR = getVariableNodeFromTemp( tdReturn );
556 VariableNode lnX = getVariableNodeFromTemp( x );
558 clearRefEdgesFrom( lnR, null, null, true );
560 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
561 while( itrXhrn.hasNext() ) {
562 RefEdge edgeX = itrXhrn.next();
563 HeapRegionNode referencee = edgeX.getDst();
564 RefEdge edgeNew = edgeX.copy();
565 edgeNew.setSrc( lnR );
567 addRefEdge( lnR, referencee, edgeNew );
572 public void assignTempEqualToNewAlloc( TempDescriptor x,
579 // after the age operation the newest (or zero-ith oldest)
580 // node associated with the allocation site should have
581 // no references to it as if it were a newly allocated
583 Integer idNewest = as.getIthOldest( 0 );
584 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
585 assert hrnNewest != null;
587 VariableNode lnX = getVariableNodeFromTemp( x );
588 clearRefEdgesFrom( lnX, null, null, true );
590 // make a new reference to allocated node
591 TypeDescriptor type = as.getType();
594 new RefEdge( lnX, // source
598 hrnNewest.getAlpha(), // beta
599 predsTrue // predicates
602 addRefEdge( lnX, hrnNewest, edgeNew );
604 abstractGarbageCollect();
609 // use the allocation site (unique to entire analysis) to
610 // locate the heap region nodes in this reachability graph
611 // that should be aged. The process models the allocation
612 // of new objects and collects all the oldest allocations
613 // in a summary node to allow for a finite analysis
615 // There is an additional property of this method. After
616 // running it on a particular reachability graph (many graphs
617 // may have heap regions related to the same allocation site)
618 // the heap region node objects in this reachability graph will be
619 // allocated. Therefore, after aging a graph for an allocation
620 // site, attempts to retrieve the heap region nodes using the
621 // integer id's contained in the allocation site should always
622 // return non-null heap regions.
623 public void age( AllocSite as ) {
625 // keep track of allocation sites that are represented
626 // in this graph for efficiency with other operations
627 allocSites.add( as );
630 // if there is a k-th oldest node, it merges into
632 Integer idK = as.getOldest();
633 if( id2hrn.containsKey( idK ) ) {
634 HeapRegionNode hrnK = id2hrn.get( idK );
636 // retrieve the summary node, or make it
638 HeapRegionNode hrnSummary = getSummaryNode( as );
640 mergeIntoSummary( hrnK, hrnSummary );
643 // move down the line of heap region nodes
644 // clobbering the ith and transferring all references
645 // to and from i-1 to node i.
646 for( int i = allocationDepth - 1; i > 0; --i ) {
648 // if the target (ith) node exists, clobber it
649 // whether the i-1 node exists or not
650 Integer idIth = as.getIthOldest( i );
651 if( id2hrn.containsKey( idIth ) ) {
652 HeapRegionNode hrnI = id2hrn.get( idIth );
654 // clear all references in and out
655 clearRefEdgesFrom( hrnI, null, null, true );
656 clearRefEdgesTo ( hrnI, null, null, true );
659 // only do the transfer if the i-1 node exists
660 Integer idImin1th = as.getIthOldest( i - 1 );
661 if( id2hrn.containsKey( idImin1th ) ) {
662 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
664 // either retrieve or make target of transfer
665 HeapRegionNode hrnI = getIthNode( as, i );
667 transferOnto( hrnImin1, hrnI );
672 // as stated above, the newest node should have had its
673 // references moved over to the second oldest, so we wipe newest
674 // in preparation for being the new object to assign something to
675 HeapRegionNode hrn0 = getIthNode( as, 0 );
676 clearRefEdgesFrom( hrn0, null, null, true );
677 clearRefEdgesTo ( hrn0, null, null, true );
679 // now tokens in reachability sets need to "age" also
680 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
681 while( itrAllVariableNodes.hasNext() ) {
682 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
683 VariableNode ln = (VariableNode) me.getValue();
685 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
686 while( itrEdges.hasNext() ) {
687 ageTokens(as, itrEdges.next() );
691 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
692 while( itrAllHRNodes.hasNext() ) {
693 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
694 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
696 ageTokens( as, hrnToAge );
698 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
699 while( itrEdges.hasNext() ) {
700 ageTokens( as, itrEdges.next() );
705 // after tokens have been aged, reset newest node's reachability
706 // and a brand new node has a "true" predicate
707 hrn0.setAlpha( hrn0.getInherent() );
708 hrn0.setPreds( predsTrue );
712 // either retrieve or create the needed heap region node
713 protected HeapRegionNode getSummaryNode( AllocSite as ) {
715 Integer idSummary = as.getSummary();
716 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
718 if( hrnSummary == null ) {
720 boolean hasFlags = false;
721 if( as.getType().isClass() ) {
722 hasFlags = as.getType().getClassDesc().hasFlags();
726 hasFlags = as.getFlag();
729 String strDesc = as.toStringForDOT()+"\\nsummary";
731 createNewHeapRegionNode( idSummary, // id or null to generate a new one
732 false, // single object?
734 hasFlags, // flagged?
735 false, // out-of-context?
736 as.getType(), // type
737 as, // allocation site
738 null, // inherent reach
739 null, // current reach
740 predsEmpty, // predicates
741 strDesc // description
748 // either retrieve or create the needed heap region node
749 protected HeapRegionNode getIthNode( AllocSite as, Integer i ) {
751 Integer idIth = as.getIthOldest( i );
752 HeapRegionNode hrnIth = id2hrn.get( idIth );
754 if( hrnIth == null ) {
756 boolean hasFlags = false;
757 if( as.getType().isClass() ) {
758 hasFlags = as.getType().getClassDesc().hasFlags();
762 hasFlags = as.getFlag();
765 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
766 hrnIth = createNewHeapRegionNode( idIth, // id or null to generate a new one
767 true, // single object?
769 hasFlags, // flagged?
770 false, // out-of-context?
771 as.getType(), // type
772 as, // allocation site
773 null, // inherent reach
774 null, // current reach
775 predsEmpty, // predicates
776 strDesc // description
784 protected HeapRegionNode getShadowSummaryNode( AllocSite as ) {
786 Integer idShadowSummary = as.getSummaryShadow();
787 HeapRegionNode hrnShadowSummary = id2hrn.get( idShadowSummary );
789 if( hrnShadowSummary == null ) {
791 boolean hasFlags = false;
792 if( as.getType().isClass() ) {
793 hasFlags = as.getType().getClassDesc().hasFlags();
797 hasFlags = as.getFlag();
800 String strDesc = as+"\\n"+as.getType()+"\\nshadowSum";
802 createNewHeapRegionNode( idShadowSummary, // id or null to generate a new one
803 false, // single object?
805 hasFlags, // flagged?
806 false, // out-of-context?
807 as.getType(), // type
808 as, // allocation site
809 null, // inherent reach
810 null, // current reach
811 predsEmpty, // predicates
812 strDesc // description
815 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
816 Integer idShadowIth = as.getIthOldestShadow( i );
817 assert !id2hrn.containsKey( idShadowIth );
818 strDesc = as+"\\n"+as.getType()+"\\n"+i+" shadow";
819 createNewHeapRegionNode( idShadowIth, // id or null to generate a new one
820 true, // single object?
822 hasFlags, // flagged?
823 false, // out-of-context?
824 as.getType(), // type
825 as, // allocation site
826 null, // inherent reach
827 null, // current reach
828 predsEmpty, // predicates
829 strDesc // description
834 return hrnShadowSummary;
838 protected void mergeIntoSummary( HeapRegionNode hrn,
839 HeapRegionNode hrnSummary ) {
840 assert hrnSummary.isNewSummary();
842 // transfer references _from_ hrn over to hrnSummary
843 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
844 while( itrReferencee.hasNext() ) {
845 RefEdge edge = itrReferencee.next();
846 RefEdge edgeMerged = edge.copy();
847 edgeMerged.setSrc( hrnSummary );
849 HeapRegionNode hrnReferencee = edge.getDst();
850 RefEdge edgeSummary =
851 hrnSummary.getReferenceTo( hrnReferencee,
856 if( edgeSummary == null ) {
857 // the merge is trivial, nothing to be done
859 // otherwise an edge from the referencer to hrnSummary exists already
860 // and the edge referencer->hrn should be merged with it
861 edgeMerged.setBeta( edgeMerged.getBeta().union( edgeSummary.getBeta() ) );
862 edgeMerged.setPreds( edgeMerged.getPreds().join( edgeSummary.getPreds() ) );
865 addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
868 // next transfer references _to_ hrn over to hrnSummary
869 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
870 while( itrReferencer.hasNext() ) {
871 RefEdge edge = itrReferencer.next();
872 RefEdge edgeMerged = edge.copy();
873 edgeMerged.setDst( hrnSummary );
875 RefSrcNode onReferencer = edge.getSrc();
876 RefEdge edgeSummary =
877 onReferencer.getReferenceTo( hrnSummary,
882 if( edgeSummary == null ) {
883 // the merge is trivial, nothing to be done
885 // otherwise an edge from the referencer to alpha_S exists already
886 // and the edge referencer->alpha_K should be merged with it
887 edgeMerged.setBeta( edgeMerged.getBeta().union( edgeSummary.getBeta() ) );
888 edgeMerged.setPreds( edgeMerged.getPreds().join( edgeSummary.getPreds() ) );
891 addRefEdge( onReferencer, hrnSummary, edgeMerged );
894 // then merge hrn reachability into hrnSummary
895 hrnSummary.setAlpha( hrnSummary.getAlpha().union( hrn.getAlpha() ) );
899 protected void transferOnto( HeapRegionNode hrnA,
900 HeapRegionNode hrnB ) {
902 // clear references in and out of node b
903 clearRefEdgesFrom( hrnB, null, null, true );
904 clearRefEdgesTo ( hrnB, null, null, true );
906 // copy each edge in and out of A to B
907 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
908 while( itrReferencee.hasNext() ) {
909 RefEdge edge = itrReferencee.next();
910 HeapRegionNode hrnReferencee = edge.getDst();
911 RefEdge edgeNew = edge.copy();
912 edgeNew.setSrc( hrnB );
914 addRefEdge( hrnB, hrnReferencee, edgeNew );
917 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
918 while( itrReferencer.hasNext() ) {
919 RefEdge edge = itrReferencer.next();
920 RefSrcNode onReferencer = edge.getSrc();
921 RefEdge edgeNew = edge.copy();
922 edgeNew.setDst( hrnB );
924 addRefEdge( onReferencer, hrnB, edgeNew );
927 // replace hrnB reachability and preds with hrnA's
928 hrnB.setAlpha( hrnA.getAlpha() );
929 hrnB.setPreds( hrnA.getPreds() );
933 protected void ageTokens( AllocSite as, RefEdge edge ) {
934 edge.setBeta( edge.getBeta().ageTokens( as ) );
937 protected void ageTokens( AllocSite as, HeapRegionNode hrn ) {
938 hrn.setAlpha( hrn.getAlpha().ageTokens( as ) );
943 protected void propagateTokensOverNodes(
944 HeapRegionNode nPrime,
946 HashSet<HeapRegionNode> nodesWithNewAlpha,
947 HashSet<RefEdge> edgesWithNewBeta ) {
949 HashSet<HeapRegionNode> todoNodes
950 = new HashSet<HeapRegionNode>();
951 todoNodes.add(nPrime);
953 HashSet<RefEdge> todoEdges
954 = new HashSet<RefEdge>();
956 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
957 = new Hashtable<HeapRegionNode, ChangeSet>();
958 nodePlannedChanges.put(nPrime, c0);
960 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
961 = new Hashtable<RefEdge, ChangeSet>();
963 // first propagate change sets everywhere they can go
964 while( !todoNodes.isEmpty() ) {
965 HeapRegionNode n = todoNodes.iterator().next();
966 ChangeSet C = nodePlannedChanges.get(n);
968 Iterator<RefEdge> referItr = n.iteratorToReferencers();
969 while( referItr.hasNext() ) {
970 RefEdge edge = referItr.next();
973 if( !edgePlannedChanges.containsKey(edge) ) {
974 edgePlannedChanges.put(edge, new ChangeSet().makeCanonical() );
977 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
980 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
981 while( refeeItr.hasNext() ) {
982 RefEdge edgeF = refeeItr.next();
983 HeapRegionNode m = edgeF.getDst();
985 ChangeSet changesToPass = new ChangeSet().makeCanonical();
987 Iterator<ChangeTuple> itrCprime = C.iterator();
988 while( itrCprime.hasNext() ) {
989 ChangeTuple c = itrCprime.next();
990 if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
991 changesToPass = changesToPass.union(c);
995 if( !changesToPass.isEmpty() ) {
996 if( !nodePlannedChanges.containsKey(m) ) {
997 nodePlannedChanges.put(m, new ChangeSet().makeCanonical() );
1000 ChangeSet currentChanges = nodePlannedChanges.get(m);
1002 if( !changesToPass.isSubset(currentChanges) ) {
1004 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
1010 todoNodes.remove(n);
1013 // then apply all of the changes for each node at once
1014 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1015 while( itrMap.hasNext() ) {
1016 Map.Entry me = (Map.Entry) itrMap.next();
1017 HeapRegionNode n = (HeapRegionNode) me.getKey();
1018 ChangeSet C = (ChangeSet) me.getValue();
1020 // this propagation step is with respect to one change,
1021 // so we capture the full change from the old alpha:
1022 ReachSet localDelta = n.getAlpha().applyChangeSet( C, true );
1024 // but this propagation may be only one of many concurrent
1025 // possible changes, so keep a running union with the node's
1026 // partially updated new alpha set
1027 n.setAlphaNew( n.getAlphaNew().union( localDelta ) );
1029 nodesWithNewAlpha.add( n );
1032 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
1036 protected void propagateTokensOverEdges(
1037 HashSet <RefEdge> todoEdges,
1038 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1039 HashSet <RefEdge> edgesWithNewBeta ) {
1041 // first propagate all change tuples everywhere they can go
1042 while( !todoEdges.isEmpty() ) {
1043 RefEdge edgeE = todoEdges.iterator().next();
1044 todoEdges.remove(edgeE);
1046 if( !edgePlannedChanges.containsKey(edgeE) ) {
1047 edgePlannedChanges.put(edgeE, new ChangeSet().makeCanonical() );
1050 ChangeSet C = edgePlannedChanges.get(edgeE);
1052 ChangeSet changesToPass = new ChangeSet().makeCanonical();
1054 Iterator<ChangeTuple> itrC = C.iterator();
1055 while( itrC.hasNext() ) {
1056 ChangeTuple c = itrC.next();
1057 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1058 changesToPass = changesToPass.union(c);
1062 RefSrcNode onSrc = edgeE.getSrc();
1064 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
1065 HeapRegionNode n = (HeapRegionNode) onSrc;
1067 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1068 while( referItr.hasNext() ) {
1069 RefEdge edgeF = referItr.next();
1071 if( !edgePlannedChanges.containsKey(edgeF) ) {
1072 edgePlannedChanges.put(edgeF, new ChangeSet().makeCanonical() );
1075 ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
1077 if( !changesToPass.isSubset(currentChanges) ) {
1078 todoEdges.add(edgeF);
1079 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
1085 // then apply all of the changes for each edge at once
1086 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1087 while( itrMap.hasNext() ) {
1088 Map.Entry me = (Map.Entry) itrMap.next();
1089 RefEdge e = (RefEdge) me.getKey();
1090 ChangeSet C = (ChangeSet) me.getValue();
1092 // this propagation step is with respect to one change,
1093 // so we capture the full change from the old beta:
1094 ReachSet localDelta = e.getBeta().applyChangeSet( C, true );
1096 // but this propagation may be only one of many concurrent
1097 // possible changes, so keep a running union with the edge's
1098 // partially updated new beta set
1099 e.setBetaNew( e.getBetaNew().union( localDelta ) );
1101 edgesWithNewBeta.add( e );
1107 // use this method to make a new reach graph that is
1108 // what heap the FlatMethod callee from the FlatCall
1109 // would start with reaching from its arguments in
1111 public ReachGraph makeCalleeView( FlatCall fc,
1114 // the callee view is a new graph: DON'T MODIFY
1116 ReachGraph rg = new ReachGraph();
1118 // track what parts of this graph have already been
1119 // added to callee view, variables not needed.
1120 // Note that we need this because when we traverse
1121 // this caller graph for each parameter we may find
1122 // nodes and edges more than once (which the per-param
1123 // "visit" sets won't show) and we only want to create
1124 // an element in the new callee view one time
1125 Set callerNodesCopiedToCallee = new HashSet<HeapRegionNode>();
1126 Set callerEdgesCopiedToCallee = new HashSet<RefEdge>();
1129 // a conservative starting point is to take the
1130 // mechanically-reachable-from-arguments graph
1131 // as opposed to using reachability information
1132 // to prune the graph further
1133 for( int i = 0; i < fm.numParameters(); ++i ) {
1135 // for each parameter index, get the symbol in the
1136 // caller view and callee view
1138 // argument defined here is the symbol in the caller
1139 TempDescriptor tdArg = fc.getArgMatchingParamIndex( fm, i );
1141 // parameter defined here is the symbol in the callee
1142 TempDescriptor tdParam = fm.getParameter( i );
1144 // use these two VariableNode objects to translate
1145 // between caller and callee--its easy to compare
1146 // a HeapRegionNode across callee and caller because
1147 // they will have the same heap region ID
1148 VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
1149 VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
1151 // now traverse the calleR view using the argument to
1152 // build the calleE view which has the parameter symbol
1153 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1154 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1155 toVisitInCaller.add( vnCaller );
1157 while( !toVisitInCaller.isEmpty() ) {
1158 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1159 RefSrcNode rsnCallee;
1161 toVisitInCaller.remove( rsnCaller );
1162 visitedInCaller.add( rsnCaller );
1164 // FIRST - setup the source end of an edge, and
1165 // remember the identifying info of the source
1166 // to build predicates
1167 TempDescriptor tdSrc = null;
1168 Integer hrnSrcID = null;
1170 if( rsnCaller == vnCaller ) {
1171 // if the caller node is the param symbol, we
1172 // have to do this translation for the callee
1173 rsnCallee = vnCallee;
1177 // otherwise the callee-view node is a heap
1178 // region with the same ID, that may or may
1179 // not have been created already
1180 assert rsnCaller instanceof HeapRegionNode;
1182 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller; hrnSrcID = hrnSrcCaller.getID();
1184 if( !callerNodesCopiedToCallee.contains( rsnCaller ) ) {
1186 ExistPredNode pred =
1187 new ExistPredNode( hrnSrcID, null );
1189 ExistPredSet preds = new ExistPredSet();
1193 rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
1194 hrnSrcCaller.isSingleObject(),
1195 hrnSrcCaller.isNewSummary(),
1196 hrnSrcCaller.isFlagged(),
1197 false, // out-of-context?
1198 hrnSrcCaller.getType(),
1199 hrnSrcCaller.getAllocSite(),
1200 toShadowTokens( this, hrnSrcCaller.getInherent() ),
1201 toShadowTokens( this, hrnSrcCaller.getAlpha() ),
1203 hrnSrcCaller.getDescription()
1205 callerNodesCopiedToCallee.add( rsnCaller );
1208 rsnCallee = rg.id2hrn.get( hrnSrcID );
1212 // SECOND - go over all edges from that source
1214 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1215 while( itrRefEdges.hasNext() ) {
1216 RefEdge reCaller = itrRefEdges.next();
1217 HeapRegionNode hrnCaller = reCaller.getDst();
1218 HeapRegionNode hrnCallee;
1220 // THIRD - setup destination ends of edges
1221 Integer hrnDstID = hrnCaller.getID();
1223 if( !callerNodesCopiedToCallee.contains( hrnCaller ) ) {
1225 ExistPredNode pred =
1226 new ExistPredNode( hrnDstID, null );
1228 ExistPredSet preds = new ExistPredSet();
1232 rg.createNewHeapRegionNode( hrnCaller.getID(),
1233 hrnCaller.isSingleObject(),
1234 hrnCaller.isNewSummary(),
1235 hrnCaller.isFlagged(),
1236 false, // out-of-context?
1237 hrnCaller.getType(),
1238 hrnCaller.getAllocSite(),
1239 toShadowTokens( this, hrnCaller.getInherent() ),
1240 toShadowTokens( this, hrnCaller.getAlpha() ),
1242 hrnCaller.getDescription()
1244 callerNodesCopiedToCallee.add( hrnCaller );
1246 hrnCallee = rg.id2hrn.get( hrnDstID );
1249 // FOURTH - copy edge over if needed
1250 if( !callerEdgesCopiedToCallee.contains( reCaller ) ) {
1252 ExistPredEdge pred =
1253 new ExistPredEdge( tdSrc,
1257 reCaller.getField(),
1260 ExistPredSet preds = new ExistPredSet();
1263 rg.addRefEdge( rsnCallee,
1265 new RefEdge( rsnCallee,
1268 reCaller.getField(),
1269 toShadowTokens( this, reCaller.getBeta() ),
1273 callerEdgesCopiedToCallee.add( reCaller );
1276 // keep traversing nodes reachable from param i
1277 // that we haven't visited yet
1278 if( !visitedInCaller.contains( hrnCaller ) ) {
1279 toVisitInCaller.add( hrnCaller );
1282 } // end edge iteration
1283 } // end visiting heap nodes in caller
1284 } // end iterating over parameters as starting points
1287 // find the set of edges in this graph with source
1288 // out-of-context (not in nodes copied) and have a
1289 // destination in context (one of nodes copied) as
1290 // a starting point for building out-of-context nodes
1291 Iterator<HeapRegionNode> itrInContext =
1292 callerNodesCopiedToCallee.iterator();
1293 while( itrInContext.hasNext() ) {
1294 HeapRegionNode hrnCallerAndInContext = itrInContext.next();
1296 Iterator<RefEdge> itrMightCross =
1297 hrnCallerAndInContext.iteratorToReferencers();
1298 while( itrMightCross.hasNext() ) {
1299 RefEdge edgeMightCross = itrMightCross.next();
1301 // we're only interested in edges with a source
1302 // 1) out-of-context and 2) is a heap region
1303 if( callerNodesCopiedToCallee.contains( edgeMightCross.getSrc() ) ||
1304 !(edgeMightCross.getSrc() instanceof HeapRegionNode)
1310 HeapRegionNode hrnCallerAndOutContext =
1311 (HeapRegionNode)edgeMightCross.getSrc();
1313 // we found a reference that crosses from out-of-context
1314 // to in-context, so build a special out-of-context node
1315 // for the callee IHM and its reference edge
1316 HeapRegionNode hrnCalleeAndOutContext =
1317 rg.createNewHeapRegionNode( null, // ID
1318 false, // single object?
1319 false, // new summary?
1321 true, // out-of-context?
1322 hrnCallerAndOutContext.getType(),
1323 null, // alloc site, shouldn't be used
1324 toShadowTokens( this, hrnCallerAndOutContext.getAlpha() ), // inherent
1325 toShadowTokens( this, hrnCallerAndOutContext.getAlpha() ), // alpha
1330 HeapRegionNode hrnCalleeAndInContext =
1331 rg.id2hrn.get( hrnCallerAndInContext.getID() );
1333 rg.addRefEdge( hrnCalleeAndOutContext,
1334 hrnCalleeAndInContext,
1335 new RefEdge( hrnCalleeAndOutContext,
1336 hrnCalleeAndInContext,
1337 edgeMightCross.getType(),
1338 edgeMightCross.getField(),
1339 toShadowTokens( this, edgeMightCross.getBeta() ),
1349 rg.writeGraph( "calleeview", true, true, true, false, true, true );
1350 } catch( IOException e ) {}
1353 if( fc.getMethod().getSymbol().equals( "addSomething" ) ) {
1361 public void resolveMethodCall( FlatCall fc,
1366 // to map the callee effects into the caller graph,
1367 // traverse the callee and categorize each element as,
1369 // 1) new node (not in caller)
1370 // 2) old node, clean (not modified in callee)
1371 // 3) old node, dirty
1373 // 5) old edge, clean
1374 // 6) old edge, dirty
1375 // 7) out-of-context nodes
1376 // 8) edge that crosses out-of-context to in-
1378 Iterator hrnItr = rgCallee.id2hrn.entrySet().iterator();
1379 while( hrnItr.hasNext() ) {
1380 Map.Entry me = (Map.Entry) hrnItr.next();
1381 Integer id = (Integer) me.getKey();
1382 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1384 if( hrnCallee.isOutOfContext() ) {
1385 // 7) out-of-context nodes aren't altered by callee
1386 // analysis, they just help calculate changes to other
1387 // elements, so do nothing for this node
1390 // node is in the callee context...
1392 if( !this.id2hrn.containsKey( id ) ) {
1393 // 1) this is a new node in the callee
1394 assert !hrnCallee.isClean();
1396 // bring this node into caller as-is, and do the
1397 // unshadow of tokens in-place
1398 this.createNewHeapRegionNode( id,
1399 hrnCallee.isSingleObject(),
1400 hrnCallee.isNewSummary(),
1401 hrnCallee.isFlagged(),
1403 false, // out-of-context?
1404 hrnCallee.getType(),
1405 hrnCallee.getAllocSite(),
1406 unShadowTokens( rgCallee, hrnCallee.getInherent() ),
1407 unShadowTokens( rgCallee, hrnCallee.getAlpha() ),
1409 hrnCallee.getDescription()
1413 // otherwise, both graphs have this node, so...
1415 if( hrnCallee.isClean() ) {
1416 // 2) this node was not modified by callee,
1417 // just leave it alone in caller
1420 // 3) this node is already in caller, was modified
1421 // by the callee, so update caller node in-place
1422 hrnCaller = this.id2hrn.get( id );
1424 assert hrnCaller.getInherent().equals(
1425 unShadowTokens( rgCallee, hrnCallee.getInherent() )
1428 unShadowTokens( rgCallee, hrnCallee.getAlpha() )
1431 hrnCaller.setClean( false );
1435 } // end visiting callee nodes
1442 protected void unshadowTokens( AllocSite as,
1445 edge.setBeta( edge.getBeta().unshadowTokens( as ) );
1448 protected void unshadowTokens( AllocSite as,
1451 hrn.setAlpha( hrn.getAlpha().unshadowTokens( as ) );
1455 private ReachSet toShadowTokens( ReachGraph rg,
1458 ReachSet rsOut = new ReachSet( rsIn ).makeCanonical();
1460 Iterator<AllocSite> allocItr = rg.allocSites.iterator();
1461 while( allocItr.hasNext() ) {
1462 AllocSite as = allocItr.next();
1463 rsOut = rsOut.toShadowTokens( as );
1466 return rsOut.makeCanonical();
1470 ////////////////////////////////////////////////////
1472 // Abstract garbage collection simply removes
1473 // heap region nodes that are not mechanically
1474 // reachable from a root set. This step is
1475 // essential for testing node and edge existence
1476 // predicates efficiently
1478 ////////////////////////////////////////////////////
1479 public void abstractGarbageCollect() {
1481 // calculate a root set, will be different for Java
1482 // version of analysis versus Bamboo version
1483 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
1484 Iterator<VariableNode> vnItr = td2vn.values().iterator();
1485 while( vnItr.hasNext() ) {
1486 toVisit.add( vnItr.next() );
1489 // everything visited in a traversal is
1490 // considered abstractly live
1491 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
1493 while( !toVisit.isEmpty() ) {
1494 RefSrcNode rsn = toVisit.iterator().next();
1495 toVisit.remove( rsn );
1498 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
1499 while( hrnItr.hasNext() ) {
1500 RefEdge edge = hrnItr.next();
1501 HeapRegionNode hrn = edge.getDst();
1503 if( !visited.contains( hrn ) ) {
1509 // get a copy of the set to iterate over because
1510 // we're going to monkey with the graph when we
1511 // identify a garbage node
1512 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
1513 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
1514 while( hrnItr.hasNext() ) {
1515 hrnAllPrior.add( hrnItr.next() );
1518 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
1519 while( hrnAllItr.hasNext() ) {
1520 HeapRegionNode hrn = hrnAllItr.next();
1522 if( !visited.contains( hrn ) ) {
1523 // heap region nodes are compared across ReachGraph
1524 // objects by their integer ID, so when discarding
1525 // garbage nodes we must also discard entries in
1526 // the ID -> heap region hashtable.
1527 id2hrn.remove( hrn.getID() );
1529 // RefEdge objects are two-way linked between
1530 // nodes, so when a node is identified as garbage,
1531 // actively clear references to and from it so
1532 // live nodes won't have dangling RefEdge's
1533 clearRefEdgesFrom( hrn, null, null, true );
1534 clearRefEdgesTo ( hrn, null, null, true );
1536 // if we just removed the last node from an allocation
1537 // site, it should be taken out of the ReachGraph's list
1538 AllocSite as = hrn.getAllocSite();
1539 if( !hasNodesOf( as ) ) {
1540 allocSites.remove( as );
1546 protected boolean hasNodesOf( AllocSite as ) {
1547 if( id2hrn.containsKey( as.getSummary() ) ) {
1551 for( int i = 0; i < allocationDepth; ++i ) {
1552 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
1560 ////////////////////////////////////////////////////
1562 // This global sweep is an optional step to prune
1563 // reachability sets that are not internally
1564 // consistent with the global graph. It should be
1565 // invoked after strong updates or method calls.
1567 ////////////////////////////////////////////////////
1568 public void globalSweep() {
1570 // boldB is part of the phase 1 sweep
1571 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
1572 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
1574 // visit every heap region to initialize alphaNew and calculate boldB
1575 Set hrns = id2hrn.entrySet();
1576 Iterator itrHrns = hrns.iterator();
1577 while( itrHrns.hasNext() ) {
1578 Map.Entry me = (Map.Entry)itrHrns.next();
1579 Integer token = (Integer) me.getKey();
1580 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1582 // assert that this node and incoming edges have clean alphaNew
1583 // and betaNew sets, respectively
1584 assert rsetEmpty.equals( hrn.getAlphaNew() );
1586 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
1587 while( itrRers.hasNext() ) {
1588 RefEdge edge = itrRers.next();
1589 assert rsetEmpty.equals( edge.getBetaNew() );
1592 // calculate boldB for this flagged node
1593 if( hrn.isFlagged() ) {
1595 Hashtable<RefEdge, ReachSet> boldB_f =
1596 new Hashtable<RefEdge, ReachSet>();
1598 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
1600 // initial boldB_f constraints
1601 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
1602 while( itrRees.hasNext() ) {
1603 RefEdge edge = itrRees.next();
1605 assert !boldB.containsKey( edge );
1606 boldB_f.put( edge, edge.getBeta() );
1608 assert !workSetEdges.contains( edge );
1609 workSetEdges.add( edge );
1612 // enforce the boldB_f constraint at edges until we reach a fixed point
1613 while( !workSetEdges.isEmpty() ) {
1614 RefEdge edge = workSetEdges.iterator().next();
1615 workSetEdges.remove( edge );
1617 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
1618 while( itrPrime.hasNext() ) {
1619 RefEdge edgePrime = itrPrime.next();
1621 ReachSet prevResult = boldB_f.get( edgePrime );
1622 ReachSet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
1624 if( prevResult == null ||
1625 prevResult.union( intersection ).size() > prevResult.size() ) {
1627 if( prevResult == null ) {
1628 boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) );
1630 boldB_f.put( edgePrime, prevResult .union( intersection ) );
1632 workSetEdges.add( edgePrime );
1637 boldB.put( token, boldB_f );
1642 // use boldB to prune tokens from alpha states that are impossible
1643 // and propagate the differences backwards across edges
1644 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
1646 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
1647 new Hashtable<RefEdge, ChangeSet>();
1649 hrns = id2hrn.entrySet();
1650 itrHrns = hrns.iterator();
1651 while( itrHrns.hasNext() ) {
1652 Map.Entry me = (Map.Entry)itrHrns.next();
1653 Integer token = (Integer) me.getKey();
1654 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1656 // never remove the identity token from a flagged region
1657 // because it is trivially satisfied
1658 ReachTuple ttException = new ReachTuple( token,
1659 !hrn.isSingleObject(),
1660 ReachTuple.ARITY_ONE ).makeCanonical();
1662 ChangeSet cts = new ChangeSet().makeCanonical();
1664 // mark tokens for removal
1665 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
1666 while( stateItr.hasNext() ) {
1667 ReachState ttsOld = stateItr.next();
1669 ReachState markedTokens = new ReachState().makeCanonical();
1671 Iterator<ReachTuple> ttItr = ttsOld.iterator();
1672 while( ttItr.hasNext() ) {
1673 ReachTuple ttOld = ttItr.next();
1675 // never remove the identity token from a flagged region
1676 // because it is trivially satisfied
1677 if( hrn.isFlagged() ) {
1678 if( ttOld == ttException ) {
1683 // does boldB_ttOld allow this token?
1684 boolean foundState = false;
1685 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
1686 while( incidentEdgeItr.hasNext() ) {
1687 RefEdge incidentEdge = incidentEdgeItr.next();
1689 // if it isn't allowed, mark for removal
1690 Integer idOld = ttOld.getToken();
1691 assert id2hrn.containsKey( idOld );
1692 Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
1693 ReachSet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL!
1694 if( boldB_ttOld_incident != null &&
1695 boldB_ttOld_incident.contains( ttsOld ) ) {
1701 markedTokens = markedTokens.add( ttOld );
1705 // if there is nothing marked, just move on
1706 if( markedTokens.isEmpty() ) {
1707 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
1711 // remove all marked tokens and establish a change set that should
1712 // propagate backwards over edges from this node
1713 ReachState ttsPruned = new ReachState().makeCanonical();
1714 ttItr = ttsOld.iterator();
1715 while( ttItr.hasNext() ) {
1716 ReachTuple ttOld = ttItr.next();
1718 if( !markedTokens.containsTuple( ttOld ) ) {
1719 ttsPruned = ttsPruned.union( ttOld );
1722 assert !ttsOld.equals( ttsPruned );
1724 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
1725 ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
1726 cts = cts.union( ct );
1729 // throw change tuple set on all incident edges
1730 if( !cts.isEmpty() ) {
1731 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
1732 while( incidentEdgeItr.hasNext() ) {
1733 RefEdge incidentEdge = incidentEdgeItr.next();
1735 edgesForPropagation.add( incidentEdge );
1737 if( edgePlannedChanges.get( incidentEdge ) == null ) {
1738 edgePlannedChanges.put( incidentEdge, cts );
1740 edgePlannedChanges.put(
1742 edgePlannedChanges.get( incidentEdge ).union( cts )
1749 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
1751 propagateTokensOverEdges( edgesForPropagation,
1755 // at the end of the 1st phase reference edges have
1756 // beta, betaNew that correspond to beta and betaR
1758 // commit beta<-betaNew, so beta=betaR and betaNew
1759 // will represent the beta' calculation in 2nd phase
1761 // commit alpha<-alphaNew because it won't change
1762 HashSet<RefEdge> res = new HashSet<RefEdge>();
1764 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
1765 while( nodeItr.hasNext() ) {
1766 HeapRegionNode hrn = nodeItr.next();
1767 hrn.applyAlphaNew();
1768 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
1769 while( itrRes.hasNext() ) {
1770 res.add( itrRes.next() );
1776 Iterator<RefEdge> edgeItr = res.iterator();
1777 while( edgeItr.hasNext() ) {
1778 RefEdge edge = edgeItr.next();
1779 HeapRegionNode hrn = edge.getDst();
1781 // commit results of last phase
1782 if( edgesUpdated.contains( edge ) ) {
1783 edge.applyBetaNew();
1786 // compute intial condition of 2nd phase
1787 edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
1790 // every edge in the graph is the initial workset
1791 Set<RefEdge> edgeWorkSet = (Set) res.clone();
1792 while( !edgeWorkSet.isEmpty() ) {
1793 RefEdge edgePrime = edgeWorkSet.iterator().next();
1794 edgeWorkSet.remove( edgePrime );
1796 RefSrcNode on = edgePrime.getSrc();
1797 if( !(on instanceof HeapRegionNode) ) {
1800 HeapRegionNode hrn = (HeapRegionNode) on;
1802 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
1803 while( itrEdge.hasNext() ) {
1804 RefEdge edge = itrEdge.next();
1806 ReachSet prevResult = edge.getBetaNew();
1807 assert prevResult != null;
1809 ReachSet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
1811 if( prevResult.union( intersection ).size() > prevResult.size() ) {
1812 edge.setBetaNew( prevResult.union( intersection ) );
1813 edgeWorkSet.add( edge );
1818 // commit beta' (beta<-betaNew)
1819 edgeItr = res.iterator();
1820 while( edgeItr.hasNext() ) {
1821 edgeItr.next().applyBetaNew();
1827 ////////////////////////////////////////////////////
1828 // high-level merge operations
1829 ////////////////////////////////////////////////////
1830 public void merge_sameMethodContext( ReachGraph rg ) {
1831 // when merging two graphs that abstract the heap
1832 // of the same method context, we just call the
1833 // basic merge operation
1837 public void merge_diffMethodContext( ReachGraph rg ) {
1838 // when merging graphs for abstract heaps in
1839 // different method contexts we should:
1840 // 1) age the allocation sites?
1844 ////////////////////////////////////////////////////
1845 // in merge() and equals() methods the suffix A
1846 // represents the passed in graph and the suffix
1847 // B refers to the graph in this object
1848 // Merging means to take the incoming graph A and
1849 // merge it into B, so after the operation graph B
1850 // is the final result.
1851 ////////////////////////////////////////////////////
1852 protected void merge( ReachGraph rg ) {
1859 mergeRefEdges ( rg );
1860 mergeAllocSites( rg );
1863 protected void mergeNodes( ReachGraph rg ) {
1865 // start with heap region nodes
1866 Set sA = rg.id2hrn.entrySet();
1867 Iterator iA = sA.iterator();
1868 while( iA.hasNext() ) {
1869 Map.Entry meA = (Map.Entry) iA.next();
1870 Integer idA = (Integer) meA.getKey();
1871 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1873 // if this graph doesn't have a node the
1874 // incoming graph has, allocate it
1875 if( !id2hrn.containsKey( idA ) ) {
1876 HeapRegionNode hrnB = hrnA.copy();
1877 id2hrn.put( idA, hrnB );
1880 // otherwise this is a node present in both graphs
1881 // so make the new reachability set a union of the
1882 // nodes' reachability sets
1883 HeapRegionNode hrnB = id2hrn.get( idA );
1884 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
1886 // if hrnB is already dirty or hrnA is dirty,
1887 // the hrnB should end up dirty: TODO
1889 if( !hrnA.isClean() ) {
1890 hrnB.setIsClean( false );
1896 // now add any variable nodes that are in graph B but
1898 sA = rg.td2vn.entrySet();
1900 while( iA.hasNext() ) {
1901 Map.Entry meA = (Map.Entry) iA.next();
1902 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1903 VariableNode lnA = (VariableNode) meA.getValue();
1905 // if the variable doesn't exist in B, allocate and add it
1906 VariableNode lnB = getVariableNodeFromTemp( tdA );
1910 protected void mergeRefEdges( ReachGraph rg ) {
1912 // between heap regions
1913 Set sA = rg.id2hrn.entrySet();
1914 Iterator iA = sA.iterator();
1915 while( iA.hasNext() ) {
1916 Map.Entry meA = (Map.Entry) iA.next();
1917 Integer idA = (Integer) meA.getKey();
1918 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1920 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1921 while( heapRegionsItrA.hasNext() ) {
1922 RefEdge edgeA = heapRegionsItrA.next();
1923 HeapRegionNode hrnChildA = edgeA.getDst();
1924 Integer idChildA = hrnChildA.getID();
1926 // at this point we know an edge in graph A exists
1927 // idA -> idChildA, does this exist in B?
1928 assert id2hrn.containsKey( idA );
1929 HeapRegionNode hrnB = id2hrn.get( idA );
1930 RefEdge edgeToMerge = null;
1932 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1933 while( heapRegionsItrB.hasNext() &&
1934 edgeToMerge == null ) {
1936 RefEdge edgeB = heapRegionsItrB.next();
1937 HeapRegionNode hrnChildB = edgeB.getDst();
1938 Integer idChildB = hrnChildB.getID();
1940 // don't use the RefEdge.equals() here because
1941 // we're talking about existence between graphs,
1942 // not intragraph equal
1943 if( idChildB.equals( idChildA ) &&
1944 edgeB.typeAndFieldEquals( edgeA ) ) {
1946 edgeToMerge = edgeB;
1950 // if the edge from A was not found in B,
1952 if( edgeToMerge == null ) {
1953 assert id2hrn.containsKey( idChildA );
1954 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
1955 edgeToMerge = edgeA.copy();
1956 edgeToMerge.setSrc( hrnB );
1957 edgeToMerge.setDst( hrnChildB );
1958 addRefEdge( hrnB, hrnChildB, edgeToMerge );
1960 // otherwise, the edge already existed in both graphs
1961 // so merge their reachability sets
1963 // just replace this beta set with the union
1964 assert edgeToMerge != null;
1965 edgeToMerge.setBeta(
1966 edgeToMerge.getBeta().union( edgeA.getBeta() )
1970 if( !edgeA.isClean() ) {
1971 edgeToMerge.setIsClean( false );
1978 // and then again from variable nodes
1979 sA = rg.td2vn.entrySet();
1981 while( iA.hasNext() ) {
1982 Map.Entry meA = (Map.Entry) iA.next();
1983 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1984 VariableNode vnA = (VariableNode) meA.getValue();
1986 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
1987 while( heapRegionsItrA.hasNext() ) {
1988 RefEdge edgeA = heapRegionsItrA.next();
1989 HeapRegionNode hrnChildA = edgeA.getDst();
1990 Integer idChildA = hrnChildA.getID();
1992 // at this point we know an edge in graph A exists
1993 // tdA -> idChildA, does this exist in B?
1994 assert td2vn.containsKey( tdA );
1995 VariableNode vnB = td2vn.get( tdA );
1996 RefEdge edgeToMerge = null;
1998 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
1999 while( heapRegionsItrB.hasNext() &&
2000 edgeToMerge == null ) {
2002 RefEdge edgeB = heapRegionsItrB.next();
2003 HeapRegionNode hrnChildB = edgeB.getDst();
2004 Integer idChildB = hrnChildB.getID();
2006 // don't use the RefEdge.equals() here because
2007 // we're talking about existence between graphs
2008 if( idChildB.equals( idChildA ) &&
2009 edgeB.typeAndFieldEquals( edgeA ) ) {
2011 edgeToMerge = edgeB;
2015 // if the edge from A was not found in B,
2017 if( edgeToMerge == null ) {
2018 assert id2hrn.containsKey( idChildA );
2019 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2020 edgeToMerge = edgeA.copy();
2021 edgeToMerge.setSrc( vnB );
2022 edgeToMerge.setDst( hrnChildB );
2023 addRefEdge( vnB, hrnChildB, edgeToMerge );
2025 // otherwise, the edge already existed in both graphs
2026 // so merge their reachability sets
2028 // just replace this beta set with the union
2029 edgeToMerge.setBeta(
2030 edgeToMerge.getBeta().union( edgeA.getBeta() )
2034 if( !edgeA.isClean() ) {
2035 edgeToMerge.setIsClean( false );
2043 protected void mergeAllocSites( ReachGraph rg ) {
2044 allocSites.addAll( rg.allocSites );
2048 // it is necessary in the equals() member functions
2049 // to "check both ways" when comparing the data
2050 // structures of two graphs. For instance, if all
2051 // edges between heap region nodes in graph A are
2052 // present and equal in graph B it is not sufficient
2053 // to say the graphs are equal. Consider that there
2054 // may be edges in graph B that are not in graph A.
2055 // the only way to know that all edges in both graphs
2056 // are equally present is to iterate over both data
2057 // structures and compare against the other graph.
2058 public boolean equals( ReachGraph rg ) {
2064 if( !areHeapRegionNodesEqual( rg ) ) {
2068 if( !areVariableNodesEqual( rg ) ) {
2072 if( !areRefEdgesEqual( rg ) ) {
2076 // if everything is equal up to this point,
2077 // assert that allocSites is also equal--
2078 // this data is redundant but kept for efficiency
2079 assert allocSites.equals( rg.allocSites );
2085 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
2087 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
2091 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
2098 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
2100 Set sA = rgA.id2hrn.entrySet();
2101 Iterator iA = sA.iterator();
2102 while( iA.hasNext() ) {
2103 Map.Entry meA = (Map.Entry) iA.next();
2104 Integer idA = (Integer) meA.getKey();
2105 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2107 if( !rgB.id2hrn.containsKey( idA ) ) {
2111 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2112 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
2121 protected boolean areVariableNodesEqual( ReachGraph rg ) {
2123 if( !areallVNinAalsoinBandequal( this, rg ) ) {
2127 if( !areallVNinAalsoinBandequal( rg, this ) ) {
2134 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
2136 Set sA = rgA.td2vn.entrySet();
2137 Iterator iA = sA.iterator();
2138 while( iA.hasNext() ) {
2139 Map.Entry meA = (Map.Entry) iA.next();
2140 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2142 if( !rgB.td2vn.containsKey( tdA ) ) {
2151 protected boolean areRefEdgesEqual( ReachGraph rg ) {
2152 if( !areallREinAandBequal( this, rg ) ) {
2159 static protected boolean areallREinAandBequal( ReachGraph rgA,
2162 // check all the heap region->heap region edges
2163 Set sA = rgA.id2hrn.entrySet();
2164 Iterator iA = sA.iterator();
2165 while( iA.hasNext() ) {
2166 Map.Entry meA = (Map.Entry) iA.next();
2167 Integer idA = (Integer) meA.getKey();
2168 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2170 // we should have already checked that the same
2171 // heap regions exist in both graphs
2172 assert rgB.id2hrn.containsKey( idA );
2174 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
2178 // then check every edge in B for presence in A, starting
2179 // from the same parent HeapRegionNode
2180 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2182 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
2187 // then check all the variable->heap region edges
2188 sA = rgA.td2vn.entrySet();
2190 while( iA.hasNext() ) {
2191 Map.Entry meA = (Map.Entry) iA.next();
2192 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2193 VariableNode vnA = (VariableNode) meA.getValue();
2195 // we should have already checked that the same
2196 // label nodes exist in both graphs
2197 assert rgB.td2vn.containsKey( tdA );
2199 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
2203 // then check every edge in B for presence in A, starting
2204 // from the same parent VariableNode
2205 VariableNode vnB = rgB.td2vn.get( tdA );
2207 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
2216 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
2220 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
2221 while( itrA.hasNext() ) {
2222 RefEdge edgeA = itrA.next();
2223 HeapRegionNode hrnChildA = edgeA.getDst();
2224 Integer idChildA = hrnChildA.getID();
2226 assert rgB.id2hrn.containsKey( idChildA );
2228 // at this point we know an edge in graph A exists
2229 // rnA -> idChildA, does this exact edge exist in B?
2230 boolean edgeFound = false;
2232 RefSrcNode rnB = null;
2233 if( rnA instanceof HeapRegionNode ) {
2234 HeapRegionNode hrnA = (HeapRegionNode) rnA;
2235 rnB = rgB.id2hrn.get( hrnA.getID() );
2237 VariableNode vnA = (VariableNode) rnA;
2238 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
2241 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
2242 while( itrB.hasNext() ) {
2243 RefEdge edgeB = itrB.next();
2244 HeapRegionNode hrnChildB = edgeB.getDst();
2245 Integer idChildB = hrnChildB.getID();
2247 if( idChildA.equals( idChildB ) &&
2248 edgeA.typeAndFieldEquals( edgeB ) ) {
2250 // there is an edge in the right place with the right field,
2251 // but do they have the same attributes?
2252 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
2253 edgeA.equalsPreds( edgeB )
2270 // this analysis no longer has the "match anything"
2271 // type which was represented by null
2272 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2273 TypeDescriptor td2 ) {
2277 if( td1.isNull() ) {
2280 if( td2.isNull() ) {
2283 return typeUtil.mostSpecific( td1, td2 );
2286 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2288 TypeDescriptor td3 ) {
2290 return mostSpecificType( td1,
2291 mostSpecificType( td2, td3 )
2295 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2298 TypeDescriptor td4 ) {
2300 return mostSpecificType( mostSpecificType( td1, td2 ),
2301 mostSpecificType( td3, td4 )
2305 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
2306 TypeDescriptor possibleChild ) {
2307 assert possibleSuper != null;
2308 assert possibleChild != null;
2310 if( possibleSuper.isNull() ||
2311 possibleChild.isNull() ) {
2315 return typeUtil.isSuperorType( possibleSuper, possibleChild );
2319 protected boolean hasMatchingField( HeapRegionNode src,
2322 TypeDescriptor tdSrc = src.getType();
2323 assert tdSrc != null;
2325 if( tdSrc.isArray() ) {
2326 TypeDescriptor td = edge.getType();
2329 TypeDescriptor tdSrcDeref = tdSrc.dereference();
2330 assert tdSrcDeref != null;
2332 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
2336 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
2339 // if it's not a class, it doesn't have any fields to match
2340 if( !tdSrc.isClass() ) {
2344 ClassDescriptor cd = tdSrc.getClassDesc();
2345 while( cd != null ) {
2346 Iterator fieldItr = cd.getFields();
2348 while( fieldItr.hasNext() ) {
2349 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
2351 if( fd.getType().equals( edge.getType() ) &&
2352 fd.getSymbol().equals( edge.getField() ) ) {
2357 cd = cd.getSuperDesc();
2360 // otherwise it is a class with fields
2361 // but we didn't find a match
2365 protected boolean hasMatchingType( RefEdge edge,
2366 HeapRegionNode dst ) {
2368 // if the region has no type, matches everything
2369 TypeDescriptor tdDst = dst.getType();
2370 assert tdDst != null;
2372 // if the type is not a class or an array, don't
2373 // match because primitives are copied, no aliases
2374 ClassDescriptor cdDst = tdDst.getClassDesc();
2375 if( cdDst == null && !tdDst.isArray() ) {
2379 // if the edge type is null, it matches everything
2380 TypeDescriptor tdEdge = edge.getType();
2381 assert tdEdge != null;
2383 return typeUtil.isSuperorType( tdEdge, tdDst );
2387 public void writeGraph( String graphName,
2388 boolean writeLabels,
2389 boolean labelSelect,
2390 boolean pruneGarbage,
2391 boolean writeReferencers,
2392 boolean hideSubsetReachability,
2393 boolean hideEdgeTaints
2394 ) throws java.io.IOException {
2396 // remove all non-word characters from the graph name so
2397 // the filename and identifier in dot don't cause errors
2398 graphName = graphName.replaceAll( "[\\W]", "" );
2401 new BufferedWriter( new FileWriter( graphName+".dot" ) );
2403 bw.write( "digraph "+graphName+" {\n" );
2405 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2407 // then visit every heap region node
2408 Set s = id2hrn.entrySet();
2409 Iterator i = s.iterator();
2410 while( i.hasNext() ) {
2411 Map.Entry me = (Map.Entry) i.next();
2412 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2414 // only visit nodes worth writing out--for instance
2415 // not every node at an allocation is referenced
2416 // (think of it as garbage-collected), etc.
2417 if( !pruneGarbage ||
2418 (hrn.isFlagged() && hrn.getID() > 0) ||
2419 hrn.getDescription().startsWith( "param" ) ||
2420 hrn.isOutOfContext()
2423 if( !visited.contains( hrn ) ) {
2424 traverseHeapRegionNodes( hrn,
2429 hideSubsetReachability,
2435 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
2438 // then visit every label node, useful for debugging
2440 s = td2vn.entrySet();
2442 while( i.hasNext() ) {
2443 Map.Entry me = (Map.Entry) i.next();
2444 VariableNode vn = (VariableNode) me.getValue();
2447 String labelStr = vn.getTempDescriptorString();
2448 if( labelStr.startsWith("___temp") ||
2449 labelStr.startsWith("___dst") ||
2450 labelStr.startsWith("___srctmp") ||
2451 labelStr.startsWith("___neverused")
2457 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
2458 while( heapRegionsItr.hasNext() ) {
2459 RefEdge edge = heapRegionsItr.next();
2460 HeapRegionNode hrn = edge.getDst();
2462 if( pruneGarbage && !visited.contains( hrn ) ) {
2463 traverseHeapRegionNodes( hrn,
2468 hideSubsetReachability,
2472 bw.write( " "+vn.toString()+
2473 " -> "+hrn.toString()+
2474 edge.toStringDOT( hideSubsetReachability )+
2484 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
2487 Set<HeapRegionNode> visited,
2488 boolean writeReferencers,
2489 boolean hideSubsetReachability,
2490 boolean hideEdgeTaints
2491 ) throws java.io.IOException {
2493 if( visited.contains( hrn ) ) {
2498 bw.write( " "+hrn.toString()+
2499 hrn.toStringDOT( hideSubsetReachability )+
2502 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
2503 while( childRegionsItr.hasNext() ) {
2504 RefEdge edge = childRegionsItr.next();
2505 HeapRegionNode hrnChild = edge.getDst();
2507 bw.write( " "+hrn.toString()+
2508 " -> "+hrnChild.toString()+
2509 edge.toStringDOT( hideSubsetReachability )+
2512 traverseHeapRegionNodes( hrnChild,
2517 hideSubsetReachability,