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 = false;
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 = ReachState.factory();
20 protected static final ReachSet rsetEmpty = ReachSet.factory();
21 protected static final ReachSet rsetWithEmptyState = ReachSet.factory( rstateEmpty );
23 // predicate constants
24 protected static final ExistPred predTrue = ExistPred.factory(); // if no args, true
25 protected static final ExistPredSet predsEmpty = ExistPredSet.factory();
26 protected static final ExistPredSet predsTrue = ExistPredSet.factory( predTrue );
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 // this suite of methods can be used to assert a
67 // very important property of ReachGraph objects:
68 // some element, HeapRegionNode, RefEdge etc.
69 // should be referenced by at most ONE ReachGraph!!
70 // If a heap region or edge or variable should be
71 // in another graph, make a new object with
72 // equivalent properties for a new graph
73 public boolean belongsToThis( RefSrcNode rsn ) {
74 if( rsn instanceof VariableNode ) {
75 VariableNode vn = (VariableNode) rsn;
76 return this.td2vn.get( vn.getTempDescriptor() ) == vn;
78 HeapRegionNode hrn = (HeapRegionNode) rsn;
79 return this.id2hrn.get( hrn.getID() ) == hrn;
84 // the reason for this method is to have the option
85 // of creating new heap regions with specific IDs, or
86 // duplicating heap regions with specific IDs (especially
87 // in the merge() operation) or to create new heap
88 // regions with a new unique ID
89 protected HeapRegionNode
90 createNewHeapRegionNode( Integer id,
91 boolean isSingleObject,
94 boolean isOutOfContext,
103 boolean markForAnalysis = isFlagged;
105 TypeDescriptor typeToUse = null;
106 if( allocSite != null ) {
107 typeToUse = allocSite.getType();
108 allocSites.add( allocSite );
113 if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
114 markForAnalysis = true;
118 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
121 if( inherent == null ) {
122 if( markForAnalysis ) {
126 ReachTuple.factory( id,
128 ReachTuple.ARITY_ONE,
129 false // out-of-context
134 inherent = rsetWithEmptyState;
138 if( alpha == null ) {
142 assert preds != null;
144 HeapRegionNode hrn = new HeapRegionNode( id,
155 id2hrn.put( id, hrn );
161 ////////////////////////////////////////////////
163 // Low-level referencee and referencer methods
165 // These methods provide the lowest level for
166 // creating references between reachability nodes
167 // and handling the details of maintaining both
168 // list of referencers and referencees.
170 ////////////////////////////////////////////////
171 protected void addRefEdge( RefSrcNode referencer,
172 HeapRegionNode referencee,
174 assert referencer != null;
175 assert referencee != null;
177 assert edge.getSrc() == referencer;
178 assert edge.getDst() == referencee;
179 assert belongsToThis( referencer );
180 assert belongsToThis( referencee );
182 // edges are getting added twice to graphs now, the
183 // kind that should have abstract facts merged--use
184 // this check to prevent that
185 assert referencer.getReferenceTo( referencee,
190 referencer.addReferencee( edge );
191 referencee.addReferencer( edge );
194 protected void removeRefEdge( RefEdge e ) {
195 removeRefEdge( e.getSrc(),
201 protected void removeRefEdge( RefSrcNode referencer,
202 HeapRegionNode referencee,
205 assert referencer != null;
206 assert referencee != null;
208 RefEdge edge = referencer.getReferenceTo( referencee,
212 assert edge == referencee.getReferenceFrom( referencer,
216 referencer.removeReferencee( edge );
217 referencee.removeReferencer( edge );
220 protected void clearRefEdgesFrom( RefSrcNode referencer,
223 boolean removeAll ) {
224 assert referencer != null;
226 // get a copy of the set to iterate over, otherwise
227 // we will be trying to take apart the set as we
228 // are iterating over it, which won't work
229 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
230 while( i.hasNext() ) {
231 RefEdge edge = i.next();
234 (edge.typeEquals( type ) && edge.fieldEquals( field ))
237 HeapRegionNode referencee = edge.getDst();
239 removeRefEdge( referencer,
247 protected void clearRefEdgesTo( HeapRegionNode referencee,
250 boolean removeAll ) {
251 assert referencee != null;
253 // get a copy of the set to iterate over, otherwise
254 // we will be trying to take apart the set as we
255 // are iterating over it, which won't work
256 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
257 while( i.hasNext() ) {
258 RefEdge edge = i.next();
261 (edge.typeEquals( type ) && edge.fieldEquals( field ))
264 RefSrcNode referencer = edge.getSrc();
266 removeRefEdge( referencer,
274 protected void clearNonVarRefEdgesTo( HeapRegionNode referencee ) {
275 assert referencee != null;
277 // get a copy of the set to iterate over, otherwise
278 // we will be trying to take apart the set as we
279 // are iterating over it, which won't work
280 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
281 while( i.hasNext() ) {
282 RefEdge edge = i.next();
283 RefSrcNode referencer = edge.getSrc();
284 if( !(referencer instanceof VariableNode) ) {
285 removeRefEdge( referencer,
293 // this is a common operation in many transfer functions: we want
294 // to add an edge, but if there is already such an edge we should
295 // merge the properties of the existing and the new edges
296 protected void addEdgeOrMergeWithExisting( RefEdge edgeNew ) {
298 RefSrcNode src = edgeNew.getSrc();
299 assert belongsToThis( src );
301 HeapRegionNode dst = edgeNew.getDst();
302 assert belongsToThis( dst );
304 // look to see if an edge with same field exists
305 // and merge with it, otherwise just add the edge
306 RefEdge edgeExisting = src.getReferenceTo( dst,
311 if( edgeExisting != null ) {
312 edgeExisting.setBeta(
313 Canonical.unionORpreds( edgeExisting.getBeta(),
317 edgeExisting.setPreds(
318 Canonical.join( edgeExisting.getPreds(),
324 addRefEdge( src, dst, edgeNew );
330 ////////////////////////////////////////////////////
332 // Assignment Operation Methods
334 // These methods are high-level operations for
335 // modeling program assignment statements using
336 // the low-level reference create/remove methods
339 ////////////////////////////////////////////////////
341 public void assignTempXEqualToTempY( TempDescriptor x,
343 assignTempXEqualToCastedTempY( x, y, null );
346 public void assignTempXEqualToCastedTempY( TempDescriptor x,
348 TypeDescriptor tdCast ) {
350 VariableNode lnX = getVariableNodeFromTemp( x );
351 VariableNode lnY = getVariableNodeFromTemp( y );
353 clearRefEdgesFrom( lnX, null, null, true );
355 // note it is possible that the types of temps in the
356 // flat node to analyze will reveal that some typed
357 // edges in the reachability graph are impossible
358 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
360 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
361 while( itrYhrn.hasNext() ) {
362 RefEdge edgeY = itrYhrn.next();
363 HeapRegionNode referencee = edgeY.getDst();
364 RefEdge edgeNew = edgeY.copy();
366 if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
367 impossibleEdges.add( edgeY );
371 edgeNew.setSrc( lnX );
373 if( tdCast == null ) {
374 edgeNew.setType( mostSpecificType( y.getType(),
380 edgeNew.setType( mostSpecificType( y.getType(),
382 referencee.getType(),
388 edgeNew.setField( null );
390 addRefEdge( lnX, referencee, edgeNew );
393 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
394 while( itrImp.hasNext() ) {
395 RefEdge edgeImp = itrImp.next();
396 removeRefEdge( edgeImp );
401 public void assignTempXEqualToTempYFieldF( TempDescriptor x,
403 FieldDescriptor f ) {
404 VariableNode lnX = getVariableNodeFromTemp( x );
405 VariableNode lnY = getVariableNodeFromTemp( y );
407 clearRefEdgesFrom( lnX, null, null, true );
409 // note it is possible that the types of temps in the
410 // flat node to analyze will reveal that some typed
411 // edges in the reachability graph are impossible
412 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
414 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
415 while( itrYhrn.hasNext() ) {
416 RefEdge edgeY = itrYhrn.next();
417 HeapRegionNode hrnY = edgeY.getDst();
418 ReachSet betaY = edgeY.getBeta();
420 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
421 while( itrHrnFhrn.hasNext() ) {
422 RefEdge edgeHrn = itrHrnFhrn.next();
423 HeapRegionNode hrnHrn = edgeHrn.getDst();
424 ReachSet betaHrn = edgeHrn.getBeta();
426 // prune edges that are not a matching field
427 if( edgeHrn.getType() != null &&
428 !edgeHrn.getField().equals( f.getSymbol() )
433 // check for impossible edges
434 if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
435 impossibleEdges.add( edgeHrn );
439 TypeDescriptor tdNewEdge =
440 mostSpecificType( edgeHrn.getType(),
444 RefEdge edgeNew = new RefEdge( lnX,
448 Canonical.intersection( betaY, betaHrn ),
452 addEdgeOrMergeWithExisting( edgeNew );
456 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
457 while( itrImp.hasNext() ) {
458 RefEdge edgeImp = itrImp.next();
459 removeRefEdge( edgeImp );
462 // anytime you might remove edges between heap regions
463 // you must global sweep to clean up broken reachability
464 if( !impossibleEdges.isEmpty() ) {
465 if( !DISABLE_GLOBAL_SWEEP ) {
472 public void assignTempXFieldFEqualToTempY( TempDescriptor x,
476 VariableNode lnX = getVariableNodeFromTemp( x );
477 VariableNode lnY = getVariableNodeFromTemp( y );
479 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
480 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
482 // note it is possible that the types of temps in the
483 // flat node to analyze will reveal that some typed
484 // edges in the reachability graph are impossible
485 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
487 // first look for possible strong updates and remove those edges
488 boolean strongUpdate = false;
490 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
491 while( itrXhrn.hasNext() ) {
492 RefEdge edgeX = itrXhrn.next();
493 HeapRegionNode hrnX = edgeX.getDst();
495 // we can do a strong update here if one of two cases holds
497 f != DisjointAnalysis.getArrayField( f.getType() ) &&
498 ( (hrnX.getNumReferencers() == 1) || // case 1
499 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
502 if( !DISABLE_STRONG_UPDATES ) {
504 clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
509 // then do all token propagation
510 itrXhrn = lnX.iteratorToReferencees();
511 while( itrXhrn.hasNext() ) {
512 RefEdge edgeX = itrXhrn.next();
513 HeapRegionNode hrnX = edgeX.getDst();
514 ReachSet betaX = edgeX.getBeta();
515 ReachSet R = Canonical.intersection( hrnX.getAlpha(),
519 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
520 while( itrYhrn.hasNext() ) {
521 RefEdge edgeY = itrYhrn.next();
522 HeapRegionNode hrnY = edgeY.getDst();
523 ReachSet O = edgeY.getBeta();
525 // check for impossible edges
526 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
527 impossibleEdges.add( edgeY );
531 // propagate tokens over nodes starting from hrnSrc, and it will
532 // take care of propagating back up edges from any touched nodes
533 ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
534 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
536 // then propagate back just up the edges from hrn
537 ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
538 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
540 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
541 new Hashtable<RefEdge, ChangeSet>();
543 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
544 while( referItr.hasNext() ) {
545 RefEdge edgeUpstream = referItr.next();
546 todoEdges.add( edgeUpstream );
547 edgePlannedChanges.put( edgeUpstream, Cx );
550 propagateTokensOverEdges( todoEdges,
557 // apply the updates to reachability
558 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
559 while( nodeItr.hasNext() ) {
560 nodeItr.next().applyAlphaNew();
563 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
564 while( edgeItr.hasNext() ) {
565 edgeItr.next().applyBetaNew();
569 // then go back through and add the new edges
570 itrXhrn = lnX.iteratorToReferencees();
571 while( itrXhrn.hasNext() ) {
572 RefEdge edgeX = itrXhrn.next();
573 HeapRegionNode hrnX = edgeX.getDst();
575 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
576 while( itrYhrn.hasNext() ) {
577 RefEdge edgeY = itrYhrn.next();
578 HeapRegionNode hrnY = edgeY.getDst();
580 // skip impossible edges here, we already marked them
581 // when computing reachability propagations above
582 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
586 // prepare the new reference edge hrnX.f -> hrnY
587 TypeDescriptor tdNewEdge =
588 mostSpecificType( y.getType(),
593 RefEdge edgeNew = new RefEdge( hrnX,
597 Canonical.pruneBy( edgeY.getBeta(),
603 addEdgeOrMergeWithExisting( edgeNew );
607 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
608 while( itrImp.hasNext() ) {
609 RefEdge edgeImp = itrImp.next();
610 removeRefEdge( edgeImp );
613 // if there was a strong update, make sure to improve
614 // reachability with a global sweep
615 if( strongUpdate || !impossibleEdges.isEmpty() ) {
616 if( !DISABLE_GLOBAL_SWEEP ) {
623 public void assignReturnEqualToTemp( TempDescriptor x ) {
625 VariableNode lnR = getVariableNodeFromTemp( tdReturn );
626 VariableNode lnX = getVariableNodeFromTemp( x );
628 clearRefEdgesFrom( lnR, null, null, true );
630 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
631 while( itrXhrn.hasNext() ) {
632 RefEdge edgeX = itrXhrn.next();
633 HeapRegionNode referencee = edgeX.getDst();
634 RefEdge edgeNew = edgeX.copy();
635 edgeNew.setSrc( lnR );
637 addRefEdge( lnR, referencee, edgeNew );
642 public void assignTempEqualToNewAlloc( TempDescriptor x,
649 // after the age operation the newest (or zero-ith oldest)
650 // node associated with the allocation site should have
651 // no references to it as if it were a newly allocated
653 Integer idNewest = as.getIthOldest( 0 );
654 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
655 assert hrnNewest != null;
657 VariableNode lnX = getVariableNodeFromTemp( x );
658 clearRefEdgesFrom( lnX, null, null, true );
660 // make a new reference to allocated node
661 TypeDescriptor type = as.getType();
664 new RefEdge( lnX, // source
668 hrnNewest.getAlpha(), // beta
669 predsTrue // predicates
672 addRefEdge( lnX, hrnNewest, edgeNew );
676 // use the allocation site (unique to entire analysis) to
677 // locate the heap region nodes in this reachability graph
678 // that should be aged. The process models the allocation
679 // of new objects and collects all the oldest allocations
680 // in a summary node to allow for a finite analysis
682 // There is an additional property of this method. After
683 // running it on a particular reachability graph (many graphs
684 // may have heap regions related to the same allocation site)
685 // the heap region node objects in this reachability graph will be
686 // allocated. Therefore, after aging a graph for an allocation
687 // site, attempts to retrieve the heap region nodes using the
688 // integer id's contained in the allocation site should always
689 // return non-null heap regions.
690 public void age( AllocSite as ) {
692 // keep track of allocation sites that are represented
693 // in this graph for efficiency with other operations
694 allocSites.add( as );
696 // if there is a k-th oldest node, it merges into
698 Integer idK = as.getOldest();
699 if( id2hrn.containsKey( idK ) ) {
700 HeapRegionNode hrnK = id2hrn.get( idK );
702 // retrieve the summary node, or make it
704 HeapRegionNode hrnSummary = getSummaryNode( as, false );
706 mergeIntoSummary( hrnK, hrnSummary );
709 // move down the line of heap region nodes
710 // clobbering the ith and transferring all references
711 // to and from i-1 to node i.
712 for( int i = allocationDepth - 1; i > 0; --i ) {
714 // only do the transfer if the i-1 node exists
715 Integer idImin1th = as.getIthOldest( i - 1 );
716 if( id2hrn.containsKey( idImin1th ) ) {
717 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
718 if( hrnImin1.isWiped() ) {
719 // there is no info on this node, just skip
723 // either retrieve or make target of transfer
724 HeapRegionNode hrnI = getIthNode( as, i, false );
726 transferOnto( hrnImin1, hrnI );
731 // as stated above, the newest node should have had its
732 // references moved over to the second oldest, so we wipe newest
733 // in preparation for being the new object to assign something to
734 HeapRegionNode hrn0 = getIthNode( as, 0, false );
735 wipeOut( hrn0, true );
737 // now tokens in reachability sets need to "age" also
738 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
739 while( itrAllVariableNodes.hasNext() ) {
740 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
741 VariableNode ln = (VariableNode) me.getValue();
743 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
744 while( itrEdges.hasNext() ) {
745 ageTuplesFrom( as, itrEdges.next() );
749 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
750 while( itrAllHRNodes.hasNext() ) {
751 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
752 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
754 ageTuplesFrom( as, hrnToAge );
756 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
757 while( itrEdges.hasNext() ) {
758 ageTuplesFrom( as, itrEdges.next() );
763 // after tokens have been aged, reset newest node's reachability
764 // and a brand new node has a "true" predicate
765 hrn0.setAlpha( hrn0.getInherent() );
766 hrn0.setPreds( predsTrue );
770 // either retrieve or create the needed heap region node
771 protected HeapRegionNode getSummaryNode( AllocSite as,
776 idSummary = as.getSummaryShadow();
778 idSummary = as.getSummary();
781 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
783 if( hrnSummary == null ) {
785 boolean hasFlags = false;
786 if( as.getType().isClass() ) {
787 hasFlags = as.getType().getClassDesc().hasFlags();
791 hasFlags = as.getFlag();
794 String strDesc = as.toStringForDOT()+"\\nsummary";
797 createNewHeapRegionNode( idSummary, // id or null to generate a new one
798 false, // single object?
800 hasFlags, // flagged?
801 false, // out-of-context?
802 as.getType(), // type
803 as, // allocation site
804 null, // inherent reach
805 null, // current reach
806 predsEmpty, // predicates
807 strDesc // description
814 // either retrieve or create the needed heap region node
815 protected HeapRegionNode getIthNode( AllocSite as,
821 idIth = as.getIthOldestShadow( i );
823 idIth = as.getIthOldest( i );
826 HeapRegionNode hrnIth = id2hrn.get( idIth );
828 if( hrnIth == null ) {
830 boolean hasFlags = false;
831 if( as.getType().isClass() ) {
832 hasFlags = as.getType().getClassDesc().hasFlags();
836 hasFlags = as.getFlag();
839 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
841 hrnIth = createNewHeapRegionNode( idIth, // id or null to generate a new one
842 true, // single object?
844 hasFlags, // flagged?
845 false, // out-of-context?
846 as.getType(), // type
847 as, // allocation site
848 null, // inherent reach
849 null, // current reach
850 predsEmpty, // predicates
851 strDesc // description
859 protected void mergeIntoSummary( HeapRegionNode hrn,
860 HeapRegionNode hrnSummary ) {
861 assert hrnSummary.isNewSummary();
863 // assert that these nodes belong to THIS graph
864 assert belongsToThis( hrn );
865 assert belongsToThis( hrnSummary );
867 assert hrn != hrnSummary;
869 // transfer references _from_ hrn over to hrnSummary
870 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
871 while( itrReferencee.hasNext() ) {
872 RefEdge edge = itrReferencee.next();
873 RefEdge edgeMerged = edge.copy();
874 edgeMerged.setSrc( hrnSummary );
876 HeapRegionNode hrnReferencee = edge.getDst();
877 RefEdge edgeSummary =
878 hrnSummary.getReferenceTo( hrnReferencee,
883 if( edgeSummary == null ) {
884 // the merge is trivial, nothing to be done
885 addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
888 // otherwise an edge from the referencer to hrnSummary exists already
889 // and the edge referencer->hrn should be merged with it
891 Canonical.unionORpreds( edgeMerged.getBeta(),
892 edgeSummary.getBeta()
895 edgeSummary.setPreds(
896 Canonical.join( edgeMerged.getPreds(),
897 edgeSummary.getPreds()
903 // next transfer references _to_ hrn over to hrnSummary
904 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
905 while( itrReferencer.hasNext() ) {
906 RefEdge edge = itrReferencer.next();
907 RefEdge edgeMerged = edge.copy();
908 edgeMerged.setDst( hrnSummary );
910 RefSrcNode onReferencer = edge.getSrc();
911 RefEdge edgeSummary =
912 onReferencer.getReferenceTo( hrnSummary,
917 if( edgeSummary == null ) {
918 // the merge is trivial, nothing to be done
919 addRefEdge( onReferencer, hrnSummary, edgeMerged );
922 // otherwise an edge from the referencer to alpha_S exists already
923 // and the edge referencer->alpha_K should be merged with it
925 Canonical.unionORpreds( edgeMerged.getBeta(),
926 edgeSummary.getBeta()
929 edgeSummary.setPreds(
930 Canonical.join( edgeMerged.getPreds(),
931 edgeSummary.getPreds()
937 // then merge hrn reachability into hrnSummary
939 Canonical.unionORpreds( hrnSummary.getAlpha(),
945 Canonical.join( hrnSummary.getPreds(),
950 // and afterward, this node is gone
951 wipeOut( hrn, true );
955 protected void transferOnto( HeapRegionNode hrnA,
956 HeapRegionNode hrnB ) {
958 assert belongsToThis( hrnA );
959 assert belongsToThis( hrnB );
962 // clear references in and out of node b?
963 assert hrnB.isWiped();
965 // copy each: (edge in and out of A) to B
966 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
967 while( itrReferencee.hasNext() ) {
968 RefEdge edge = itrReferencee.next();
969 HeapRegionNode hrnReferencee = edge.getDst();
970 RefEdge edgeNew = edge.copy();
971 edgeNew.setSrc( hrnB );
972 edgeNew.setDst( hrnReferencee );
974 addRefEdge( hrnB, hrnReferencee, edgeNew );
977 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
978 while( itrReferencer.hasNext() ) {
979 RefEdge edge = itrReferencer.next();
980 RefSrcNode rsnReferencer = edge.getSrc();
981 RefEdge edgeNew = edge.copy();
982 edgeNew.setSrc( rsnReferencer );
983 edgeNew.setDst( hrnB );
985 addRefEdge( rsnReferencer, hrnB, edgeNew );
988 // replace hrnB reachability and preds with hrnA's
989 hrnB.setAlpha( hrnA.getAlpha() );
990 hrnB.setPreds( hrnA.getPreds() );
992 // after transfer, wipe out source
993 wipeOut( hrnA, true );
997 // the purpose of this method is to conceptually "wipe out"
998 // a heap region from the graph--purposefully not called REMOVE
999 // because the node is still hanging around in the graph, just
1000 // not mechanically connected or have any reach or predicate
1001 // information on it anymore--lots of ops can use this
1002 protected void wipeOut( HeapRegionNode hrn,
1003 boolean wipeVariableReferences ) {
1005 assert belongsToThis( hrn );
1007 clearRefEdgesFrom( hrn, null, null, true );
1009 if( wipeVariableReferences ) {
1010 clearRefEdgesTo( hrn, null, null, true );
1012 clearNonVarRefEdgesTo( hrn );
1015 hrn.setAlpha( rsetEmpty );
1016 hrn.setPreds( predsEmpty );
1020 protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
1022 Canonical.ageTuplesFrom( edge.getBeta(),
1028 protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
1030 Canonical.ageTuplesFrom( hrn.getAlpha(),
1038 protected void propagateTokensOverNodes( HeapRegionNode nPrime,
1040 HashSet<HeapRegionNode> nodesWithNewAlpha,
1041 HashSet<RefEdge> edgesWithNewBeta ) {
1043 HashSet<HeapRegionNode> todoNodes
1044 = new HashSet<HeapRegionNode>();
1045 todoNodes.add( nPrime );
1047 HashSet<RefEdge> todoEdges
1048 = new HashSet<RefEdge>();
1050 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1051 = new Hashtable<HeapRegionNode, ChangeSet>();
1052 nodePlannedChanges.put( nPrime, c0 );
1054 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1055 = new Hashtable<RefEdge, ChangeSet>();
1057 // first propagate change sets everywhere they can go
1058 while( !todoNodes.isEmpty() ) {
1059 HeapRegionNode n = todoNodes.iterator().next();
1060 ChangeSet C = nodePlannedChanges.get( n );
1062 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1063 while( referItr.hasNext() ) {
1064 RefEdge edge = referItr.next();
1065 todoEdges.add( edge );
1067 if( !edgePlannedChanges.containsKey( edge ) ) {
1068 edgePlannedChanges.put( edge,
1073 edgePlannedChanges.put( edge,
1074 Canonical.union( edgePlannedChanges.get( edge ),
1080 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1081 while( refeeItr.hasNext() ) {
1082 RefEdge edgeF = refeeItr.next();
1083 HeapRegionNode m = edgeF.getDst();
1085 ChangeSet changesToPass = ChangeSet.factory();
1087 Iterator<ChangeTuple> itrCprime = C.iterator();
1088 while( itrCprime.hasNext() ) {
1089 ChangeTuple c = itrCprime.next();
1090 if( edgeF.getBeta().containsIgnorePreds( c.getStateToMatch() )
1093 changesToPass = Canonical.add( changesToPass, c );
1097 if( !changesToPass.isEmpty() ) {
1098 if( !nodePlannedChanges.containsKey( m ) ) {
1099 nodePlannedChanges.put( m, ChangeSet.factory() );
1102 ChangeSet currentChanges = nodePlannedChanges.get( m );
1104 if( !changesToPass.isSubset( currentChanges ) ) {
1106 nodePlannedChanges.put( m,
1107 Canonical.union( currentChanges,
1116 todoNodes.remove( n );
1119 // then apply all of the changes for each node at once
1120 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1121 while( itrMap.hasNext() ) {
1122 Map.Entry me = (Map.Entry) itrMap.next();
1123 HeapRegionNode n = (HeapRegionNode) me.getKey();
1124 ChangeSet C = (ChangeSet) me.getValue();
1126 // this propagation step is with respect to one change,
1127 // so we capture the full change from the old alpha:
1128 ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1132 // but this propagation may be only one of many concurrent
1133 // possible changes, so keep a running union with the node's
1134 // partially updated new alpha set
1135 n.setAlphaNew( Canonical.unionORpreds( n.getAlphaNew(),
1140 nodesWithNewAlpha.add( n );
1143 propagateTokensOverEdges( todoEdges,
1150 protected void propagateTokensOverEdges( HashSet <RefEdge> todoEdges,
1151 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1152 HashSet <RefEdge> edgesWithNewBeta ) {
1154 // first propagate all change tuples everywhere they can go
1155 while( !todoEdges.isEmpty() ) {
1156 RefEdge edgeE = todoEdges.iterator().next();
1157 todoEdges.remove( edgeE );
1159 if( !edgePlannedChanges.containsKey( edgeE ) ) {
1160 edgePlannedChanges.put( edgeE,
1165 ChangeSet C = edgePlannedChanges.get( edgeE );
1167 ChangeSet changesToPass = ChangeSet.factory();
1169 Iterator<ChangeTuple> itrC = C.iterator();
1170 while( itrC.hasNext() ) {
1171 ChangeTuple c = itrC.next();
1172 if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
1175 changesToPass = Canonical.add( changesToPass, c );
1179 RefSrcNode rsn = edgeE.getSrc();
1181 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1182 HeapRegionNode n = (HeapRegionNode) rsn;
1184 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1185 while( referItr.hasNext() ) {
1186 RefEdge edgeF = referItr.next();
1188 if( !edgePlannedChanges.containsKey( edgeF ) ) {
1189 edgePlannedChanges.put( edgeF,
1194 ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1196 if( !changesToPass.isSubset( currentChanges ) ) {
1197 todoEdges.add( edgeF );
1198 edgePlannedChanges.put( edgeF,
1199 Canonical.union( currentChanges,
1208 // then apply all of the changes for each edge at once
1209 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1210 while( itrMap.hasNext() ) {
1211 Map.Entry me = (Map.Entry) itrMap.next();
1212 RefEdge e = (RefEdge) me.getKey();
1213 ChangeSet C = (ChangeSet) me.getValue();
1215 // this propagation step is with respect to one change,
1216 // so we capture the full change from the old beta:
1217 ReachSet localDelta =
1218 Canonical.applyChangeSet( e.getBeta(),
1223 // but this propagation may be only one of many concurrent
1224 // possible changes, so keep a running union with the edge's
1225 // partially updated new beta set
1226 e.setBetaNew( Canonical.unionORpreds( e.getBetaNew(),
1231 edgesWithNewBeta.add( e );
1236 // used in makeCalleeView below to decide if there is
1237 // already an appropriate out-of-context edge in a callee
1238 // view graph for merging, or null if a new one will be added
1240 getOutOfContextReferenceTo( HeapRegionNode hrn,
1241 TypeDescriptor srcType,
1242 TypeDescriptor refType,
1244 assert belongsToThis( hrn );
1246 HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1247 if( hrnInContext == null ) {
1251 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1252 while( refItr.hasNext() ) {
1253 RefEdge re = refItr.next();
1255 assert belongsToThis( re.getSrc() );
1256 assert belongsToThis( re.getDst() );
1258 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1262 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1263 if( !hrnSrc.isOutOfContext() ) {
1267 if( srcType == null ) {
1268 if( hrnSrc.getType() != null ) {
1272 if( !srcType.equals( hrnSrc.getType() ) ) {
1277 if( !re.typeEquals( refType ) ) {
1281 if( !re.fieldEquals( refField ) ) {
1285 // tada! We found it!
1292 // used below to convert a ReachSet to its callee-context
1293 // equivalent with respect to allocation sites in this graph
1294 protected ReachSet toCalleeContext( ReachSet rs,
1296 Set<HrnIdOoc> oocHrnIdOoc2callee
1298 ReachSet out = ReachSet.factory();
1300 Iterator<ReachState> itr = rs.iterator();
1301 while( itr.hasNext() ) {
1302 ReachState stateCaller = itr.next();
1304 ReachState stateCallee = stateCaller;
1306 Iterator<AllocSite> asItr = allocSites.iterator();
1307 while( asItr.hasNext() ) {
1308 AllocSite as = asItr.next();
1310 ReachState stateNew = ReachState.factory();
1311 Iterator<ReachTuple> rtItr = stateCallee.iterator();
1312 while( rtItr.hasNext() ) {
1313 ReachTuple rt = rtItr.next();
1315 // only translate this tuple if it is
1316 // in the out-callee-context bag
1317 HrnIdOoc hio = new HrnIdOoc( rt.getHrnID(),
1320 if( !oocHrnIdOoc2callee.contains( hio ) ) {
1321 stateNew = Canonical.add( stateNew, rt );
1325 int age = as.getAgeCategory( rt.getHrnID() );
1327 // this is the current mapping, where 0, 1, 2S were allocated
1328 // in the current context, 0?, 1? and 2S? were allocated in a
1329 // previous context, and we're translating to a future context
1341 if( age == AllocSite.AGE_notInThisSite ) {
1342 // things not from the site just go back in
1343 stateNew = Canonical.add( stateNew, rt );
1345 } else if( age == AllocSite.AGE_summary ||
1348 // the in-context summary and all existing out-of-context
1350 stateNew = Canonical.add( stateNew,
1351 ReachTuple.factory( as.getSummary(),
1354 true // out-of-context
1358 // otherwise everything else just goes to an out-of-context
1359 // version, everything else the same
1360 Integer I = as.getAge( rt.getHrnID() );
1363 assert !rt.isMultiObject();
1365 stateNew = Canonical.add( stateNew,
1366 ReachTuple.factory( rt.getHrnID(),
1369 true // out-of-context
1375 stateCallee = stateNew;
1378 // attach the passed in preds
1379 stateCallee = Canonical.attach( stateCallee,
1382 out = Canonical.add( out,
1387 assert out.isCanonical();
1391 // used below to convert a ReachSet to its caller-context
1392 // equivalent with respect to allocation sites in this graph
1394 toCallerContext( ReachSet rs,
1395 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1397 ReachSet out = ReachSet.factory();
1399 Iterator<ReachState> itr = rs.iterator();
1400 while( itr.hasNext() ) {
1401 ReachState stateCallee = itr.next();
1403 if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
1405 // starting from one callee state...
1406 ReachSet rsCaller = ReachSet.factory( stateCallee );
1408 // possibly branch it into many states, which any
1409 // allocation site might do, so lots of derived states
1410 Iterator<AllocSite> asItr = allocSites.iterator();
1411 while( asItr.hasNext() ) {
1412 AllocSite as = asItr.next();
1413 rsCaller = Canonical.toCallerContext( rsCaller, as );
1416 // then before adding each derived, now caller-context
1417 // states to the output, attach the appropriate pred
1418 // based on the source callee state
1419 Iterator<ReachState> stateItr = rsCaller.iterator();
1420 while( stateItr.hasNext() ) {
1421 ReachState stateCaller = stateItr.next();
1422 stateCaller = Canonical.attach( stateCaller,
1423 calleeStatesSatisfied.get( stateCallee )
1425 out = Canonical.add( out,
1432 assert out.isCanonical();
1436 // used below to convert a ReachSet to an equivalent
1437 // version with shadow IDs merged into unshadowed IDs
1438 protected ReachSet unshadow( ReachSet rs ) {
1440 Iterator<AllocSite> asItr = allocSites.iterator();
1441 while( asItr.hasNext() ) {
1442 AllocSite as = asItr.next();
1443 out = Canonical.unshadow( out, as );
1445 assert out.isCanonical();
1450 // use this method to make a new reach graph that is
1451 // what heap the FlatMethod callee from the FlatCall
1452 // would start with reaching from its arguments in
1455 makeCalleeView( FlatCall fc,
1456 FlatMethod fmCallee,
1457 Set<Integer> callerNodeIDsCopiedToCallee,
1458 boolean writeDebugDOTs
1462 // first traverse this context to find nodes and edges
1463 // that will be callee-reachable
1464 Set<HeapRegionNode> reachableCallerNodes =
1465 new HashSet<HeapRegionNode>();
1467 // caller edges between callee-reachable nodes
1468 Set<RefEdge> reachableCallerEdges =
1469 new HashSet<RefEdge>();
1471 // caller edges from arg vars, and the matching param index
1472 // because these become a special edge in callee
1473 Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1474 new Hashtable<RefEdge, Integer>();
1476 // caller edges from local vars or callee-unreachable nodes
1477 // (out-of-context sources) to callee-reachable nodes
1478 Set<RefEdge> oocCallerEdges =
1479 new HashSet<RefEdge>();
1482 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1484 TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1485 VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
1487 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1488 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1490 toVisitInCaller.add( vnArgCaller );
1492 while( !toVisitInCaller.isEmpty() ) {
1493 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1494 toVisitInCaller.remove( rsnCaller );
1495 visitedInCaller.add( rsnCaller );
1497 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1498 while( itrRefEdges.hasNext() ) {
1499 RefEdge reCaller = itrRefEdges.next();
1500 HeapRegionNode hrnCaller = reCaller.getDst();
1502 callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
1503 reachableCallerNodes.add( hrnCaller );
1505 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1506 reachableCallerEdges.add( reCaller );
1508 if( rsnCaller.equals( vnArgCaller ) ) {
1509 reachableCallerArgEdges2paramIndex.put( reCaller, i );
1511 oocCallerEdges.add( reCaller );
1515 if( !visitedInCaller.contains( hrnCaller ) ) {
1516 toVisitInCaller.add( hrnCaller );
1519 } // end edge iteration
1520 } // end visiting heap nodes in caller
1521 } // end iterating over parameters as starting points
1524 // now collect out-of-callee-context IDs and
1525 // map them to whether the ID is out of the caller
1527 Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1529 Iterator<Integer> itrInContext =
1530 callerNodeIDsCopiedToCallee.iterator();
1531 while( itrInContext.hasNext() ) {
1532 Integer hrnID = itrInContext.next();
1533 HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1535 Iterator<RefEdge> itrMightCross =
1536 hrnCallerAndInContext.iteratorToReferencers();
1537 while( itrMightCross.hasNext() ) {
1538 RefEdge edgeMightCross = itrMightCross.next();
1540 RefSrcNode rsnCallerAndOutContext =
1541 edgeMightCross.getSrc();
1543 if( rsnCallerAndOutContext instanceof VariableNode ) {
1544 // variables do not have out-of-context reach states,
1546 oocCallerEdges.add( edgeMightCross );
1550 HeapRegionNode hrnCallerAndOutContext =
1551 (HeapRegionNode) rsnCallerAndOutContext;
1553 // is this source node out-of-context?
1554 if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1555 // no, skip this edge
1560 oocCallerEdges.add( edgeMightCross );
1562 // add all reach tuples on the node to list
1563 // of things that are out-of-context: insight
1564 // if this node is reachable from someting that WAS
1565 // in-context, then this node should already be in-context
1566 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1567 while( stateItr.hasNext() ) {
1568 ReachState state = stateItr.next();
1570 Iterator<ReachTuple> rtItr = state.iterator();
1571 while( rtItr.hasNext() ) {
1572 ReachTuple rt = rtItr.next();
1574 oocHrnIdOoc2callee.add( new HrnIdOoc( rt.getHrnID(),
1583 // the callee view is a new graph: DON'T MODIFY *THIS* graph
1584 ReachGraph rg = new ReachGraph();
1586 // add nodes to callee graph
1587 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1588 while( hrnItr.hasNext() ) {
1589 HeapRegionNode hrnCaller = hrnItr.next();
1591 assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
1592 assert !rg.id2hrn.containsKey( hrnCaller.getID() );
1594 ExistPred pred = ExistPred.factory( hrnCaller.getID(), null );
1595 ExistPredSet preds = ExistPredSet.factory( pred );
1597 rg.createNewHeapRegionNode( hrnCaller.getID(),
1598 hrnCaller.isSingleObject(),
1599 hrnCaller.isNewSummary(),
1600 hrnCaller.isFlagged(),
1601 false, // out-of-context?
1602 hrnCaller.getType(),
1603 hrnCaller.getAllocSite(),
1604 toCalleeContext( hrnCaller.getInherent(),
1608 toCalleeContext( hrnCaller.getAlpha(),
1613 hrnCaller.getDescription()
1617 // add param edges to callee graph
1619 reachableCallerArgEdges2paramIndex.entrySet().iterator();
1620 while( argEdges.hasNext() ) {
1621 Map.Entry me = (Map.Entry) argEdges.next();
1622 RefEdge reArg = (RefEdge) me.getKey();
1623 Integer index = (Integer) me.getValue();
1625 TempDescriptor arg = fmCallee.getParameter( index );
1627 VariableNode vnCallee =
1628 rg.getVariableNodeFromTemp( arg );
1630 HeapRegionNode hrnDstCaller = reArg.getDst();
1631 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1632 assert hrnDstCallee != null;
1635 ExistPred.factory( arg,
1637 hrnDstCallee.getID(),
1641 true, // out-of-callee-context
1642 false // out-of-caller-context
1645 ExistPredSet preds =
1646 ExistPredSet.factory( pred );
1649 new RefEdge( vnCallee,
1653 toCalleeContext( reArg.getBeta(),
1660 rg.addRefEdge( vnCallee,
1666 // add in-context edges to callee graph
1667 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1668 while( reItr.hasNext() ) {
1669 RefEdge reCaller = reItr.next();
1670 RefSrcNode rsnCaller = reCaller.getSrc();
1671 assert rsnCaller instanceof HeapRegionNode;
1672 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1673 HeapRegionNode hrnDstCaller = reCaller.getDst();
1675 HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
1676 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1677 assert hrnSrcCallee != null;
1678 assert hrnDstCallee != null;
1681 ExistPred.factory( null,
1682 hrnSrcCallee.getID(),
1683 hrnDstCallee.getID(),
1685 reCaller.getField(),
1687 false, // out-of-callee-context
1688 false // out-of-caller-context
1691 ExistPredSet preds =
1692 ExistPredSet.factory( pred );
1695 new RefEdge( hrnSrcCallee,
1698 reCaller.getField(),
1699 toCalleeContext( reCaller.getBeta(),
1706 rg.addRefEdge( hrnSrcCallee,
1712 // add out-of-context edges to callee graph
1713 reItr = oocCallerEdges.iterator();
1714 while( reItr.hasNext() ) {
1715 RefEdge reCaller = reItr.next();
1716 RefSrcNode rsnCaller = reCaller.getSrc();
1717 HeapRegionNode hrnDstCaller = reCaller.getDst();
1718 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1719 assert hrnDstCallee != null;
1721 TypeDescriptor oocNodeType;
1723 TempDescriptor oocPredSrcTemp = null;
1724 Integer oocPredSrcID = null;
1725 boolean outOfCalleeContext;
1726 boolean outOfCallerContext;
1728 if( rsnCaller instanceof VariableNode ) {
1729 VariableNode vnCaller = (VariableNode) rsnCaller;
1731 oocReach = rsetEmpty;
1732 oocPredSrcTemp = vnCaller.getTempDescriptor();
1733 outOfCalleeContext = true;
1734 outOfCallerContext = false;
1737 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1738 assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
1739 oocNodeType = hrnSrcCaller.getType();
1740 oocReach = hrnSrcCaller.getAlpha();
1741 oocPredSrcID = hrnSrcCaller.getID();
1742 if( hrnSrcCaller.isOutOfContext() ) {
1743 outOfCalleeContext = false;
1744 outOfCallerContext = true;
1746 outOfCalleeContext = true;
1747 outOfCallerContext = false;
1752 ExistPred.factory( oocPredSrcTemp,
1754 hrnDstCallee.getID(),
1756 reCaller.getField(),
1762 ExistPredSet preds =
1763 ExistPredSet.factory( pred );
1765 RefEdge oocEdgeExisting =
1766 rg.getOutOfContextReferenceTo( hrnDstCallee,
1772 if( oocEdgeExisting == null ) {
1773 // for consistency, map one out-of-context "identifier"
1774 // to one heap region node id, otherwise no convergence
1775 String oocid = "oocid"+
1777 hrnDstCallee.getIDString()+
1780 reCaller.getField();
1782 Integer oocHrnID = oocid2hrnid.get( oocid );
1784 HeapRegionNode hrnCalleeAndOutContext;
1786 if( oocHrnID == null ) {
1788 hrnCalleeAndOutContext =
1789 rg.createNewHeapRegionNode( null, // ID
1790 false, // single object?
1791 false, // new summary?
1793 true, // out-of-context?
1795 null, // alloc site, shouldn't be used
1796 toCalleeContext( oocReach,
1800 toCalleeContext( oocReach,
1808 oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1812 // the mapping already exists, so see if node is there
1813 hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1815 if( hrnCalleeAndOutContext == null ) {
1817 hrnCalleeAndOutContext =
1818 rg.createNewHeapRegionNode( oocHrnID, // ID
1819 false, // single object?
1820 false, // new summary?
1822 true, // out-of-context?
1824 null, // alloc site, shouldn't be used
1825 toCalleeContext( oocReach,
1829 toCalleeContext( oocReach,
1838 // otherwise it is there, so merge reachability
1839 hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1840 toCalleeContext( oocReach,
1849 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1851 rg.addRefEdge( hrnCalleeAndOutContext,
1853 new RefEdge( hrnCalleeAndOutContext,
1856 reCaller.getField(),
1857 toCalleeContext( reCaller.getBeta(),
1866 // the out-of-context edge already exists
1867 oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
1868 toCalleeContext( reCaller.getBeta(),
1875 oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1880 HeapRegionNode hrnCalleeAndOutContext =
1881 (HeapRegionNode) oocEdgeExisting.getSrc();
1882 hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1883 toCalleeContext( oocReach,
1890 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1895 if( writeDebugDOTs ) {
1896 rg.writeGraph( "calleeview",
1897 resolveMethodDebugDOTwriteLabels,
1898 resolveMethodDebugDOTselectTemps,
1899 resolveMethodDebugDOTpruneGarbage,
1900 resolveMethodDebugDOThideSubsetReach,
1901 resolveMethodDebugDOThideEdgeTaints );
1907 private static Hashtable<String, Integer> oocid2hrnid =
1908 new Hashtable<String, Integer>();
1911 // useful since many graphs writes in the method call debug code
1912 private static boolean resolveMethodDebugDOTwriteLabels = true;
1913 private static boolean resolveMethodDebugDOTselectTemps = true;
1914 private static boolean resolveMethodDebugDOTpruneGarbage = true;
1915 private static boolean resolveMethodDebugDOThideSubsetReach = false;
1916 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
1921 resolveMethodCall( FlatCall fc,
1922 FlatMethod fmCallee,
1923 ReachGraph rgCallee,
1924 Set<Integer> callerNodeIDsCopiedToCallee,
1925 boolean writeDebugDOTs
1928 if( writeDebugDOTs ) {
1929 rgCallee.writeGraph( "callee",
1930 resolveMethodDebugDOTwriteLabels,
1931 resolveMethodDebugDOTselectTemps,
1932 resolveMethodDebugDOTpruneGarbage,
1933 resolveMethodDebugDOThideSubsetReach,
1934 resolveMethodDebugDOThideEdgeTaints );
1936 writeGraph( "caller00In",
1937 resolveMethodDebugDOTwriteLabels,
1938 resolveMethodDebugDOTselectTemps,
1939 resolveMethodDebugDOTpruneGarbage,
1940 resolveMethodDebugDOThideSubsetReach,
1941 resolveMethodDebugDOThideEdgeTaints,
1942 callerNodeIDsCopiedToCallee );
1946 // method call transfer function steps:
1947 // 1. Use current callee-reachable heap (CRH) to test callee
1948 // predicates and mark what will be coming in.
1949 // 2. Wipe CRH out of caller.
1950 // 3. Transplant marked callee parts in:
1951 // a) bring in nodes
1952 // b) bring in callee -> callee edges
1953 // c) resolve out-of-context -> callee edges
1954 // d) assign return value
1955 // 4. Collapse shadow nodes down
1956 // 5. Global sweep it.
1959 // 1. mark what callee elements have satisfied predicates
1960 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1961 new Hashtable<HeapRegionNode, ExistPredSet>();
1963 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1964 new Hashtable<RefEdge, ExistPredSet>();
1966 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1967 new Hashtable<ReachState, ExistPredSet>();
1969 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1970 new Hashtable< RefEdge, Set<RefSrcNode> >();
1972 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1973 while( meItr.hasNext() ) {
1974 Map.Entry me = (Map.Entry) meItr.next();
1975 Integer id = (Integer) me.getKey();
1976 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1978 // if a callee element's predicates are satisfied then a set
1979 // of CALLER predicates is returned: they are the predicates
1980 // that the callee element moved into the caller context
1981 // should have, and it is inefficient to find this again later
1982 ExistPredSet predsIfSatis =
1983 hrnCallee.getPreds().isSatisfiedBy( this,
1984 callerNodeIDsCopiedToCallee
1987 if( predsIfSatis != null ) {
1988 calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1990 // otherwise don't bother looking at edges to this node
1994 // since the node is coming over, find out which reach
1995 // states on it should come over, too
1996 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
1997 while( stateItr.hasNext() ) {
1998 ReachState stateCallee = stateItr.next();
2001 stateCallee.getPreds().isSatisfiedBy( this,
2002 callerNodeIDsCopiedToCallee
2004 if( predsIfSatis != null ) {
2005 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2009 // then look at edges to the node
2010 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2011 while( reItr.hasNext() ) {
2012 RefEdge reCallee = reItr.next();
2013 RefSrcNode rsnCallee = reCallee.getSrc();
2015 // (caller local variables to in-context heap regions)
2016 // have an (out-of-context heap region -> in-context heap region)
2017 // abstraction in the callEE, so its true we never need to
2018 // look at a (var node -> heap region) edge in callee to bring
2019 // those over for the call site transfer. What about (param var->heap region)
2020 // edges in callee? They are dealt with below this loop.
2021 // So, yes, at this point skip (var->region) edges in callee
2022 if( rsnCallee instanceof VariableNode ) {
2026 // first see if the source is out-of-context, and only
2027 // proceed with this edge if we find some caller-context
2029 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2030 boolean matchedOutOfContext = false;
2032 if( hrnSrcCallee.isOutOfContext() ) {
2034 assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2036 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2038 // is the target node in the caller?
2039 HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2040 if( hrnDstCaller == null ) {
2044 Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2045 while( reDstItr.hasNext() ) {
2046 // the edge and field (either possibly null) must match
2047 RefEdge reCaller = reDstItr.next();
2049 if( !reCaller.typeEquals ( reCallee.getType() ) ||
2050 !reCaller.fieldEquals( reCallee.getField() )
2055 RefSrcNode rsnCaller = reCaller.getSrc();
2056 if( rsnCaller instanceof VariableNode ) {
2058 // a variable node matches an OOC region with null type
2059 if( hrnSrcCallee.getType() != null ) {
2064 // otherwise types should match
2065 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2066 if( hrnSrcCallee.getType() == null ) {
2067 if( hrnCallerSrc.getType() != null ) {
2071 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2077 rsnCallers.add( rsnCaller );
2078 matchedOutOfContext = true;
2081 if( !rsnCallers.isEmpty() ) {
2082 calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2086 if( hrnSrcCallee.isOutOfContext() &&
2087 !matchedOutOfContext ) {
2092 reCallee.getPreds().isSatisfiedBy( this,
2093 callerNodeIDsCopiedToCallee
2096 if( predsIfSatis != null ) {
2097 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2099 // since the edge is coming over, find out which reach
2100 // states on it should come over, too
2101 stateItr = reCallee.getBeta().iterator();
2102 while( stateItr.hasNext() ) {
2103 ReachState stateCallee = stateItr.next();
2106 stateCallee.getPreds().isSatisfiedBy( this,
2107 callerNodeIDsCopiedToCallee
2109 if( predsIfSatis != null ) {
2110 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2117 // test param -> HRN edges, also
2118 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
2120 // parameter defined here is the symbol in the callee
2121 TempDescriptor tdParam = fmCallee.getParameter( i );
2123 if( !DisjointAnalysis.shouldAnalysisTrack( tdParam.getType() ) ) {
2124 // skip primitive/immutable parameters
2128 VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
2130 Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
2131 while( reItr.hasNext() ) {
2132 RefEdge reCallee = reItr.next();
2134 ExistPredSet ifDst =
2135 reCallee.getDst().getPreds().isSatisfiedBy( this,
2136 callerNodeIDsCopiedToCallee
2138 if( ifDst == null ) {
2142 ExistPredSet predsIfSatis =
2143 reCallee.getPreds().isSatisfiedBy( this,
2144 callerNodeIDsCopiedToCallee
2146 if( predsIfSatis != null ) {
2147 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2149 // since the edge is coming over, find out which reach
2150 // states on it should come over, too
2151 Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
2152 while( stateItr.hasNext() ) {
2153 ReachState stateCallee = stateItr.next();
2156 stateCallee.getPreds().isSatisfiedBy( this,
2157 callerNodeIDsCopiedToCallee
2159 if( predsIfSatis != null ) {
2160 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2171 if( writeDebugDOTs ) {
2172 writeGraph( "caller20BeforeWipe",
2173 resolveMethodDebugDOTwriteLabels,
2174 resolveMethodDebugDOTselectTemps,
2175 resolveMethodDebugDOTpruneGarbage,
2176 resolveMethodDebugDOThideSubsetReach,
2177 resolveMethodDebugDOThideEdgeTaints );
2181 // 2. predicates tested, ok to wipe out caller part
2182 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2183 while( hrnItr.hasNext() ) {
2184 Integer hrnID = hrnItr.next();
2185 HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2186 assert hrnCaller != null;
2188 // when clearing off nodes, also eliminate variable
2190 wipeOut( hrnCaller, true );
2195 if( writeDebugDOTs ) {
2196 writeGraph( "caller30BeforeAddingNodes",
2197 resolveMethodDebugDOTwriteLabels,
2198 resolveMethodDebugDOTselectTemps,
2199 resolveMethodDebugDOTpruneGarbage,
2200 resolveMethodDebugDOThideSubsetReach,
2201 resolveMethodDebugDOThideEdgeTaints );
2205 // 3. callee elements with satisfied preds come in, note that
2206 // the mapping of elements satisfied to preds is like this:
2207 // A callee element EE has preds EEp that are satisfied by
2208 // some caller element ER. We bring EE into the caller
2209 // context as ERee with the preds of ER, namely ERp, which
2210 // in the following algorithm is the value in the mapping
2213 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2214 while( satisItr.hasNext() ) {
2215 Map.Entry me = (Map.Entry) satisItr.next();
2216 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2217 ExistPredSet preds = (ExistPredSet) me.getValue();
2219 // TODO: I think its true that the current implementation uses
2220 // the type of the OOC region and the predicates OF THE EDGE from
2221 // it to link everything up in caller context, so that's why we're
2222 // skipping this... maybe that's a sillier way to do it?
2223 if( hrnCallee.isOutOfContext() ) {
2227 AllocSite as = hrnCallee.getAllocSite();
2228 allocSites.add( as );
2230 Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2232 HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2233 if( hrnCaller == null ) {
2235 createNewHeapRegionNode( hrnIDshadow, // id or null to generate a new one
2236 hrnCallee.isSingleObject(), // single object?
2237 hrnCallee.isNewSummary(), // summary?
2238 hrnCallee.isFlagged(), // flagged?
2239 false, // out-of-context?
2240 hrnCallee.getType(), // type
2241 hrnCallee.getAllocSite(), // allocation site
2242 toCallerContext( hrnCallee.getInherent(),
2243 calleeStatesSatisfied ), // inherent reach
2244 null, // current reach
2245 predsEmpty, // predicates
2246 hrnCallee.getDescription() // description
2249 assert hrnCaller.isWiped();
2252 hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2253 calleeStatesSatisfied
2257 hrnCaller.setPreds( preds );
2262 if( writeDebugDOTs ) {
2263 writeGraph( "caller31BeforeAddingEdges",
2264 resolveMethodDebugDOTwriteLabels,
2265 resolveMethodDebugDOTselectTemps,
2266 resolveMethodDebugDOTpruneGarbage,
2267 resolveMethodDebugDOThideSubsetReach,
2268 resolveMethodDebugDOThideEdgeTaints );
2272 // set these up during the next procedure so after
2273 // the caller has all of its nodes and edges put
2274 // back together we can propagate the callee's
2275 // reach changes backwards into the caller graph
2276 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2278 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2279 new Hashtable<RefEdge, ChangeSet>();
2282 // 3.b) callee -> callee edges AND out-of-context -> callee
2283 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2284 while( satisItr.hasNext() ) {
2285 Map.Entry me = (Map.Entry) satisItr.next();
2286 RefEdge reCallee = (RefEdge) me.getKey();
2287 ExistPredSet preds = (ExistPredSet) me.getValue();
2289 HeapRegionNode hrnDstCallee = reCallee.getDst();
2290 AllocSite asDst = hrnDstCallee.getAllocSite();
2291 allocSites.add( asDst );
2293 Integer hrnIDDstShadow =
2294 asDst.getShadowIDfromID( hrnDstCallee.getID() );
2296 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2297 assert hrnDstCaller != null;
2300 RefSrcNode rsnCallee = reCallee.getSrc();
2302 Set<RefSrcNode> rsnCallers =
2303 new HashSet<RefSrcNode>();
2305 Set<RefSrcNode> oocCallers =
2306 calleeEdges2oocCallerSrcMatches.get( reCallee );
2309 if( oocCallers == null ) {
2310 // there are no out-of-context matches, so it's
2311 // either a param/arg var or one in-context heap region
2312 if( rsnCallee instanceof VariableNode ) {
2313 // variable -> node in the callee should only
2314 // come into the caller if its from a param var
2315 VariableNode vnCallee = (VariableNode) rsnCallee;
2316 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2317 TempDescriptor tdArg = fc.getArgMatchingParam( fmCallee,
2319 if( tdArg == null ) {
2320 // this means the variable isn't a parameter, its local
2321 // to the callee so we ignore it in call site transfer
2322 // shouldn't this NEVER HAPPEN?
2326 rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2329 // otherwise source is in context, one region
2330 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2332 // translate an in-context node to shadow
2333 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2334 allocSites.add( asSrc );
2336 Integer hrnIDSrcShadow =
2337 asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2339 HeapRegionNode hrnSrcCallerShadow =
2340 this.id2hrn.get( hrnIDSrcShadow );
2342 if( hrnSrcCallerShadow == null ) {
2343 hrnSrcCallerShadow =
2344 createNewHeapRegionNode( hrnIDSrcShadow, // id or null to generate a new one
2345 hrnSrcCallee.isSingleObject(), // single object?
2346 hrnSrcCallee.isNewSummary(), // summary?
2347 hrnSrcCallee.isFlagged(), // flagged?
2348 false, // out-of-context?
2349 hrnSrcCallee.getType(), // type
2350 hrnSrcCallee.getAllocSite(), // allocation site
2351 toCallerContext( hrnSrcCallee.getInherent(),
2352 calleeStatesSatisfied ), // inherent reach
2353 toCallerContext( hrnSrcCallee.getAlpha(),
2354 calleeStatesSatisfied ), // current reach
2355 predsEmpty, // predicates
2356 hrnSrcCallee.getDescription() // description
2360 rsnCallers.add( hrnSrcCallerShadow );
2364 // otherwise we have a set of out-of-context srcs
2365 // that should NOT be translated to shadow nodes
2366 assert !oocCallers.isEmpty();
2367 rsnCallers.addAll( oocCallers );
2370 // now make all caller edges we've identified from
2371 // this callee edge with a satisfied predicate
2372 assert !rsnCallers.isEmpty();
2373 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2374 while( rsnItr.hasNext() ) {
2375 RefSrcNode rsnCaller = rsnItr.next();
2377 RefEdge reCaller = new RefEdge( rsnCaller,
2380 reCallee.getField(),
2381 toCallerContext( reCallee.getBeta(),
2382 calleeStatesSatisfied ),
2386 ChangeSet cs = ChangeSet.factory();
2387 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2388 while( rsItr.hasNext() ) {
2389 ReachState state = rsItr.next();
2390 ExistPredSet predsPreCallee = state.getPreds();
2392 if( state.isEmpty() ) {
2396 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2397 while( predItr.hasNext() ) {
2398 ExistPred pred = predItr.next();
2399 ReachState old = pred.ne_state;
2405 cs = Canonical.add( cs,
2406 ChangeTuple.factory( old,
2414 // look to see if an edge with same field exists
2415 // and merge with it, otherwise just add the edge
2416 RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2420 if( edgeExisting != null ) {
2421 edgeExisting.setBeta(
2422 Canonical.unionORpreds( edgeExisting.getBeta(),
2426 edgeExisting.setPreds(
2427 Canonical.join( edgeExisting.getPreds(),
2432 // for reach propagation
2433 if( !cs.isEmpty() ) {
2434 ChangeSet csExisting = edgePlannedChanges.get( edgeExisting );
2435 if( csExisting == null ) {
2436 csExisting = ChangeSet.factory();
2438 edgePlannedChanges.put( edgeExisting,
2439 Canonical.union( csExisting,
2446 addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2448 // for reach propagation
2449 if( !cs.isEmpty() ) {
2450 edgesForPropagation.add( reCaller );
2451 assert !edgePlannedChanges.containsKey( reCaller );
2452 edgePlannedChanges.put( reCaller, cs );
2462 if( writeDebugDOTs ) {
2463 writeGraph( "caller35BeforeAssignReturnValue",
2464 resolveMethodDebugDOTwriteLabels,
2465 resolveMethodDebugDOTselectTemps,
2466 resolveMethodDebugDOTpruneGarbage,
2467 resolveMethodDebugDOThideSubsetReach,
2468 resolveMethodDebugDOThideEdgeTaints );
2473 // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2474 // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2475 // EDGES, JUST BRINGING THEM ALL! It'll work for now, over approximation
2477 // 3.d) handle return value assignment if needed
2478 TempDescriptor returnTemp = fc.getReturnTemp();
2479 if( returnTemp != null &&
2480 DisjointAnalysis.shouldAnalysisTrack( returnTemp.getType() )
2483 VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2484 clearRefEdgesFrom( vnLhsCaller, null, null, true );
2486 VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2487 Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2488 while( reCalleeItr.hasNext() ) {
2489 RefEdge reCallee = reCalleeItr.next();
2490 HeapRegionNode hrnDstCallee = reCallee.getDst();
2492 // some edge types are not possible return values when we can
2493 // see what type variable we are assigning it to
2494 if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2495 System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2496 reCallee+" for return temp "+returnTemp );
2501 AllocSite asDst = hrnDstCallee.getAllocSite();
2502 allocSites.add( asDst );
2504 Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2506 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2507 if( hrnDstCaller == null ) {
2509 createNewHeapRegionNode( hrnIDDstShadow, // id or null to generate a new one
2510 hrnDstCallee.isSingleObject(), // single object?
2511 hrnDstCallee.isNewSummary(), // summary?
2512 hrnDstCallee.isFlagged(), // flagged?
2513 false, // out-of-context?
2514 hrnDstCallee.getType(), // type
2515 hrnDstCallee.getAllocSite(), // allocation site
2516 toCallerContext( hrnDstCallee.getInherent(),
2517 calleeStatesSatisfied ), // inherent reach
2518 toCallerContext( hrnDstCallee.getAlpha(),
2519 calleeStatesSatisfied ), // current reach
2520 predsTrue, // predicates
2521 hrnDstCallee.getDescription() // description
2525 TypeDescriptor tdNewEdge =
2526 mostSpecificType( reCallee.getType(),
2527 hrnDstCallee.getType(),
2528 hrnDstCaller.getType()
2531 RefEdge reCaller = new RefEdge( vnLhsCaller,
2535 toCallerContext( reCallee.getBeta(),
2536 calleeStatesSatisfied ),
2540 addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2546 if( writeDebugDOTs ) {
2547 writeGraph( "caller38propagateReach",
2548 resolveMethodDebugDOTwriteLabels,
2549 resolveMethodDebugDOTselectTemps,
2550 resolveMethodDebugDOTpruneGarbage,
2551 resolveMethodDebugDOThideSubsetReach,
2552 resolveMethodDebugDOThideEdgeTaints );
2555 // propagate callee reachability changes to the rest
2556 // of the caller graph edges
2557 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2559 propagateTokensOverEdges( edgesForPropagation, // source edges
2560 edgePlannedChanges, // map src edge to change set
2561 edgesUpdated ); // list of updated edges
2563 // commit beta' (beta<-betaNew)
2564 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2565 while( edgeItr.hasNext() ) {
2566 edgeItr.next().applyBetaNew();
2574 if( writeDebugDOTs ) {
2575 writeGraph( "caller40BeforeShadowMerge",
2576 resolveMethodDebugDOTwriteLabels,
2577 resolveMethodDebugDOTselectTemps,
2578 resolveMethodDebugDOTpruneGarbage,
2579 resolveMethodDebugDOThideSubsetReach,
2580 resolveMethodDebugDOThideEdgeTaints );
2584 // 4) merge shadow nodes so alloc sites are back to k
2585 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2586 while( asItr.hasNext() ) {
2587 // for each allocation site do the following to merge
2588 // shadow nodes (newest from callee) with any existing
2589 // look for the newest normal and newest shadow "slot"
2590 // not being used, transfer normal to shadow. Keep
2591 // doing this until there are no more normal nodes, or
2592 // no empty shadow slots: then merge all remaining normal
2593 // nodes into the shadow summary. Finally, convert all
2594 // shadow to their normal versions.
2595 AllocSite as = asItr.next();
2598 while( ageNorm < allocationDepth &&
2599 ageShad < allocationDepth ) {
2601 // first, are there any normal nodes left?
2602 Integer idNorm = as.getIthOldest( ageNorm );
2603 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2604 if( hrnNorm == null ) {
2605 // no, this age of normal node not in the caller graph
2610 // yes, a normal node exists, is there an empty shadow
2611 // "slot" to transfer it onto?
2612 HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2613 if( !hrnShad.isWiped() ) {
2614 // no, this age of shadow node is not empty
2619 // yes, this shadow node is empty
2620 transferOnto( hrnNorm, hrnShad );
2625 // now, while there are still normal nodes but no shadow
2626 // slots, merge normal nodes into the shadow summary
2627 while( ageNorm < allocationDepth ) {
2629 // first, are there any normal nodes left?
2630 Integer idNorm = as.getIthOldest( ageNorm );
2631 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2632 if( hrnNorm == null ) {
2633 // no, this age of normal node not in the caller graph
2638 // yes, a normal node exists, so get the shadow summary
2639 HeapRegionNode summShad = getSummaryNode( as, true );
2640 mergeIntoSummary( hrnNorm, summShad );
2644 // if there is a normal summary, merge it into shadow summary
2645 Integer idNorm = as.getSummary();
2646 HeapRegionNode summNorm = id2hrn.get( idNorm );
2647 if( summNorm != null ) {
2648 HeapRegionNode summShad = getSummaryNode( as, true );
2649 mergeIntoSummary( summNorm, summShad );
2652 // finally, flip all existing shadow nodes onto the normal
2653 for( int i = 0; i < allocationDepth; ++i ) {
2654 Integer idShad = as.getIthOldestShadow( i );
2655 HeapRegionNode hrnShad = id2hrn.get( idShad );
2656 if( hrnShad != null ) {
2658 HeapRegionNode hrnNorm = getIthNode( as, i, false );
2659 assert hrnNorm.isWiped();
2660 transferOnto( hrnShad, hrnNorm );
2664 Integer idShad = as.getSummaryShadow();
2665 HeapRegionNode summShad = id2hrn.get( idShad );
2666 if( summShad != null ) {
2667 summNorm = getSummaryNode( as, false );
2668 transferOnto( summShad, summNorm );
2673 if( writeDebugDOTs ) {
2674 writeGraph( "caller45BeforeUnshadow",
2675 resolveMethodDebugDOTwriteLabels,
2676 resolveMethodDebugDOTselectTemps,
2677 resolveMethodDebugDOTpruneGarbage,
2678 resolveMethodDebugDOThideSubsetReach,
2679 resolveMethodDebugDOThideEdgeTaints );
2683 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2684 while( itrAllHRNodes.hasNext() ) {
2685 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
2686 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2688 hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2690 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2691 while( itrEdges.hasNext() ) {
2692 RefEdge re = itrEdges.next();
2693 re.setBeta( unshadow( re.getBeta() ) );
2699 if( writeDebugDOTs ) {
2700 writeGraph( "caller50BeforeGlobalSweep",
2701 resolveMethodDebugDOTwriteLabels,
2702 resolveMethodDebugDOTselectTemps,
2703 resolveMethodDebugDOTpruneGarbage,
2704 resolveMethodDebugDOThideSubsetReach,
2705 resolveMethodDebugDOThideEdgeTaints );
2710 if( !DISABLE_GLOBAL_SWEEP ) {
2716 if( writeDebugDOTs ) {
2717 writeGraph( "caller90AfterTransfer",
2718 resolveMethodDebugDOTwriteLabels,
2719 resolveMethodDebugDOTselectTemps,
2720 resolveMethodDebugDOTpruneGarbage,
2721 resolveMethodDebugDOThideSubsetReach,
2722 resolveMethodDebugDOThideEdgeTaints );
2728 ////////////////////////////////////////////////////
2730 // Abstract garbage collection simply removes
2731 // heap region nodes that are not mechanically
2732 // reachable from a root set. This step is
2733 // essential for testing node and edge existence
2734 // predicates efficiently
2736 ////////////////////////////////////////////////////
2737 public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2739 // calculate a root set, will be different for Java
2740 // version of analysis versus Bamboo version
2741 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2743 // visit every variable in graph while building root
2744 // set, and do iterating on a copy, so we can remove
2745 // dead variables while we're at this
2746 Iterator makeCopyItr = td2vn.entrySet().iterator();
2747 Set entrysCopy = new HashSet();
2748 while( makeCopyItr.hasNext() ) {
2749 entrysCopy.add( makeCopyItr.next() );
2752 Iterator eItr = entrysCopy.iterator();
2753 while( eItr.hasNext() ) {
2754 Map.Entry me = (Map.Entry) eItr.next();
2755 TempDescriptor td = (TempDescriptor) me.getKey();
2756 VariableNode vn = (VariableNode) me.getValue();
2758 if( liveSet.contains( td ) ) {
2762 // dead var, remove completely from graph
2764 clearRefEdgesFrom( vn, null, null, true );
2768 // everything visited in a traversal is
2769 // considered abstractly live
2770 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2772 while( !toVisit.isEmpty() ) {
2773 RefSrcNode rsn = toVisit.iterator().next();
2774 toVisit.remove( rsn );
2777 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2778 while( hrnItr.hasNext() ) {
2779 RefEdge edge = hrnItr.next();
2780 HeapRegionNode hrn = edge.getDst();
2782 if( !visited.contains( hrn ) ) {
2788 // get a copy of the set to iterate over because
2789 // we're going to monkey with the graph when we
2790 // identify a garbage node
2791 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2792 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2793 while( hrnItr.hasNext() ) {
2794 hrnAllPrior.add( hrnItr.next() );
2797 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2798 while( hrnAllItr.hasNext() ) {
2799 HeapRegionNode hrn = hrnAllItr.next();
2801 if( !visited.contains( hrn ) ) {
2803 // heap region nodes are compared across ReachGraph
2804 // objects by their integer ID, so when discarding
2805 // garbage nodes we must also discard entries in
2806 // the ID -> heap region hashtable.
2807 id2hrn.remove( hrn.getID() );
2809 // RefEdge objects are two-way linked between
2810 // nodes, so when a node is identified as garbage,
2811 // actively clear references to and from it so
2812 // live nodes won't have dangling RefEdge's
2813 wipeOut( hrn, true );
2815 // if we just removed the last node from an allocation
2816 // site, it should be taken out of the ReachGraph's list
2817 AllocSite as = hrn.getAllocSite();
2818 if( !hasNodesOf( as ) ) {
2819 allocSites.remove( as );
2825 protected boolean hasNodesOf( AllocSite as ) {
2826 if( id2hrn.containsKey( as.getSummary() ) ) {
2830 for( int i = 0; i < allocationDepth; ++i ) {
2831 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2839 ////////////////////////////////////////////////////
2841 // This global sweep is an optional step to prune
2842 // reachability sets that are not internally
2843 // consistent with the global graph. It should be
2844 // invoked after strong updates or method calls.
2846 ////////////////////////////////////////////////////
2847 public void globalSweep() {
2849 // boldB is part of the phase 1 sweep
2850 // it has an in-context table and an out-of-context table
2851 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2852 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2854 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2855 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2857 // visit every heap region to initialize alphaNew and betaNew,
2858 // and make a map of every hrnID to the source nodes it should
2859 // propagate forward from. In-context flagged hrnID's propagate
2860 // from only the in-context node they name, but out-of-context
2861 // ID's may propagate from several out-of-context nodes
2862 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2863 new Hashtable< Integer, Set<HeapRegionNode> >();
2865 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2866 new Hashtable< Integer, Set<HeapRegionNode> >();
2869 Iterator itrHrns = id2hrn.entrySet().iterator();
2870 while( itrHrns.hasNext() ) {
2871 Map.Entry me = (Map.Entry) itrHrns.next();
2872 Integer hrnID = (Integer) me.getKey();
2873 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2875 // assert that this node and incoming edges have clean alphaNew
2876 // and betaNew sets, respectively
2877 assert rsetEmpty.equals( hrn.getAlphaNew() );
2879 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2880 while( itrRers.hasNext() ) {
2881 RefEdge edge = itrRers.next();
2882 assert rsetEmpty.equals( edge.getBetaNew() );
2885 // make a mapping of IDs to heap regions they propagate from
2886 if( hrn.isFlagged() ) {
2887 assert !hrn.isOutOfContext();
2888 assert !icID2srcs.containsKey( hrn.getID() );
2890 // in-context flagged node IDs simply propagate from the
2892 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2894 icID2srcs.put( hrn.getID(), srcs );
2897 if( hrn.isOutOfContext() ) {
2898 assert !hrn.isFlagged();
2900 // the reachability states on an out-of-context
2901 // node are not really important (combinations of
2902 // IDs or arity)--what matters is that the states
2903 // specify which nodes this out-of-context node
2904 // stands in for. For example, if the state [17?, 19*]
2905 // appears on the ooc node, it may serve as a source
2906 // for node 17? and a source for node 19.
2907 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2908 while( stateItr.hasNext() ) {
2909 ReachState state = stateItr.next();
2911 Iterator<ReachTuple> rtItr = state.iterator();
2912 while( rtItr.hasNext() ) {
2913 ReachTuple rt = rtItr.next();
2914 assert rt.isOutOfContext();
2916 Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2917 if( srcs == null ) {
2918 srcs = new HashSet<HeapRegionNode>();
2921 oocID2srcs.put( rt.getHrnID(), srcs );
2927 // calculate boldB for all hrnIDs identified by the above
2928 // node traversal, propagating from every source
2929 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2932 Set<HeapRegionNode> srcs;
2935 if( !icID2srcs.isEmpty() ) {
2936 Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2937 hrnID = (Integer) me.getKey();
2938 srcs = (Set<HeapRegionNode>) me.getValue();
2940 icID2srcs.remove( hrnID );
2943 assert !oocID2srcs.isEmpty();
2945 Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2946 hrnID = (Integer) me.getKey();
2947 srcs = (Set<HeapRegionNode>) me.getValue();
2949 oocID2srcs.remove( hrnID );
2953 Hashtable<RefEdge, ReachSet> boldB_f =
2954 new Hashtable<RefEdge, ReachSet>();
2956 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2958 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2959 while( hrnItr.hasNext() ) {
2960 HeapRegionNode hrn = hrnItr.next();
2962 assert workSetEdges.isEmpty();
2964 // initial boldB_f constraints
2965 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2966 while( itrRees.hasNext() ) {
2967 RefEdge edge = itrRees.next();
2969 assert !boldB_f.containsKey( edge );
2970 boldB_f.put( edge, edge.getBeta() );
2972 assert !workSetEdges.contains( edge );
2973 workSetEdges.add( edge );
2976 // enforce the boldB_f constraint at edges until we reach a fixed point
2977 while( !workSetEdges.isEmpty() ) {
2978 RefEdge edge = workSetEdges.iterator().next();
2979 workSetEdges.remove( edge );
2981 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2982 while( itrPrime.hasNext() ) {
2983 RefEdge edgePrime = itrPrime.next();
2985 ReachSet prevResult = boldB_f.get( edgePrime );
2986 ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2990 if( prevResult == null ||
2991 Canonical.unionORpreds( prevResult,
2992 intersection ).size()
2996 if( prevResult == null ) {
2997 boldB_f.put( edgePrime,
2998 Canonical.unionORpreds( edgePrime.getBeta(),
3003 boldB_f.put( edgePrime,
3004 Canonical.unionORpreds( prevResult,
3009 workSetEdges.add( edgePrime );
3016 boldBic.put( hrnID, boldB_f );
3018 boldBooc.put( hrnID, boldB_f );
3023 // use boldB to prune hrnIDs from alpha states that are impossible
3024 // and propagate the differences backwards across edges
3025 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3027 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3028 new Hashtable<RefEdge, ChangeSet>();
3031 itrHrns = id2hrn.entrySet().iterator();
3032 while( itrHrns.hasNext() ) {
3033 Map.Entry me = (Map.Entry) itrHrns.next();
3034 Integer hrnID = (Integer) me.getKey();
3035 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3037 // out-of-context nodes don't participate in the
3038 // global sweep, they serve as sources for the pass
3040 if( hrn.isOutOfContext() ) {
3044 // the inherent states of a region are the exception
3045 // to removal as the global sweep prunes
3046 ReachTuple rtException = ReachTuple.factory( hrnID,
3047 !hrn.isSingleObject(),
3048 ReachTuple.ARITY_ONE,
3049 false // out-of-context
3052 ChangeSet cts = ChangeSet.factory();
3054 // mark hrnIDs for removal
3055 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3056 while( stateItr.hasNext() ) {
3057 ReachState stateOld = stateItr.next();
3059 ReachState markedHrnIDs = ReachState.factory();
3061 Iterator<ReachTuple> rtItr = stateOld.iterator();
3062 while( rtItr.hasNext() ) {
3063 ReachTuple rtOld = rtItr.next();
3065 // never remove the inherent hrnID from a flagged region
3066 // because it is trivially satisfied
3067 if( hrn.isFlagged() ) {
3068 if( rtOld == rtException ) {
3073 // does boldB allow this hrnID?
3074 boolean foundState = false;
3075 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3076 while( incidentEdgeItr.hasNext() ) {
3077 RefEdge incidentEdge = incidentEdgeItr.next();
3079 Hashtable<RefEdge, ReachSet> B;
3080 if( rtOld.isOutOfContext() ) {
3081 B = boldBooc.get( rtOld.getHrnID() );
3085 if( !id2hrn.containsKey( rtOld.getHrnID() ) ) {
3086 System.out.println( "\nLooking for "+rtOld );
3087 writeGraph( "dbgz" );
3091 assert id2hrn.containsKey( rtOld.getHrnID() );
3092 B = boldBic.get( rtOld.getHrnID() );
3096 ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3097 if( boldB_rtOld_incident != null &&
3098 boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
3106 markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3110 // if there is nothing marked, just move on
3111 if( markedHrnIDs.isEmpty() ) {
3112 hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3119 // remove all marked hrnIDs and establish a change set that should
3120 // propagate backwards over edges from this node
3121 ReachState statePruned = ReachState.factory();
3122 rtItr = stateOld.iterator();
3123 while( rtItr.hasNext() ) {
3124 ReachTuple rtOld = rtItr.next();
3126 if( !markedHrnIDs.containsTuple( rtOld ) ) {
3127 statePruned = Canonical.add( statePruned, rtOld );
3130 assert !stateOld.equals( statePruned );
3132 hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3136 ChangeTuple ct = ChangeTuple.factory( stateOld,
3139 cts = Canonical.add( cts, ct );
3142 // throw change tuple set on all incident edges
3143 if( !cts.isEmpty() ) {
3144 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3145 while( incidentEdgeItr.hasNext() ) {
3146 RefEdge incidentEdge = incidentEdgeItr.next();
3148 edgesForPropagation.add( incidentEdge );
3150 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3151 edgePlannedChanges.put( incidentEdge, cts );
3153 edgePlannedChanges.put(
3155 Canonical.union( edgePlannedChanges.get( incidentEdge ),
3164 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3166 propagateTokensOverEdges( edgesForPropagation,
3170 // at the end of the 1st phase reference edges have
3171 // beta, betaNew that correspond to beta and betaR
3173 // commit beta<-betaNew, so beta=betaR and betaNew
3174 // will represent the beta' calculation in 2nd phase
3176 // commit alpha<-alphaNew because it won't change
3177 HashSet<RefEdge> res = new HashSet<RefEdge>();
3179 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3180 while( nodeItr.hasNext() ) {
3181 HeapRegionNode hrn = nodeItr.next();
3183 // as mentioned above, out-of-context nodes only serve
3184 // as sources of reach states for the sweep, not part
3186 if( hrn.isOutOfContext() ) {
3187 assert hrn.getAlphaNew().equals( rsetEmpty );
3189 hrn.applyAlphaNew();
3192 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3193 while( itrRes.hasNext() ) {
3194 res.add( itrRes.next() );
3200 Iterator<RefEdge> edgeItr = res.iterator();
3201 while( edgeItr.hasNext() ) {
3202 RefEdge edge = edgeItr.next();
3203 HeapRegionNode hrn = edge.getDst();
3205 // commit results of last phase
3206 if( edgesUpdated.contains( edge ) ) {
3207 edge.applyBetaNew();
3210 // compute intial condition of 2nd phase
3211 edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3217 // every edge in the graph is the initial workset
3218 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3219 while( !edgeWorkSet.isEmpty() ) {
3220 RefEdge edgePrime = edgeWorkSet.iterator().next();
3221 edgeWorkSet.remove( edgePrime );
3223 RefSrcNode rsn = edgePrime.getSrc();
3224 if( !(rsn instanceof HeapRegionNode) ) {
3227 HeapRegionNode hrn = (HeapRegionNode) rsn;
3229 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3230 while( itrEdge.hasNext() ) {
3231 RefEdge edge = itrEdge.next();
3233 ReachSet prevResult = edge.getBetaNew();
3234 assert prevResult != null;
3236 ReachSet intersection =
3237 Canonical.intersection( edge.getBeta(),
3238 edgePrime.getBetaNew()
3241 if( Canonical.unionORpreds( prevResult,
3248 Canonical.unionORpreds( prevResult,
3252 edgeWorkSet.add( edge );
3257 // commit beta' (beta<-betaNew)
3258 edgeItr = res.iterator();
3259 while( edgeItr.hasNext() ) {
3260 edgeItr.next().applyBetaNew();
3266 ////////////////////////////////////////////////////
3267 // high-level merge operations
3268 ////////////////////////////////////////////////////
3269 public void merge_sameMethodContext( ReachGraph rg ) {
3270 // when merging two graphs that abstract the heap
3271 // of the same method context, we just call the
3272 // basic merge operation
3276 public void merge_diffMethodContext( ReachGraph rg ) {
3277 // when merging graphs for abstract heaps in
3278 // different method contexts we should:
3279 // 1) age the allocation sites?
3283 ////////////////////////////////////////////////////
3284 // in merge() and equals() methods the suffix A
3285 // represents the passed in graph and the suffix
3286 // B refers to the graph in this object
3287 // Merging means to take the incoming graph A and
3288 // merge it into B, so after the operation graph B
3289 // is the final result.
3290 ////////////////////////////////////////////////////
3291 protected void merge( ReachGraph rg ) {
3298 mergeRefEdges ( rg );
3299 mergeAllocSites( rg );
3302 protected void mergeNodes( ReachGraph rg ) {
3304 // start with heap region nodes
3305 Set sA = rg.id2hrn.entrySet();
3306 Iterator iA = sA.iterator();
3307 while( iA.hasNext() ) {
3308 Map.Entry meA = (Map.Entry) iA.next();
3309 Integer idA = (Integer) meA.getKey();
3310 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3312 // if this graph doesn't have a node the
3313 // incoming graph has, allocate it
3314 if( !id2hrn.containsKey( idA ) ) {
3315 HeapRegionNode hrnB = hrnA.copy();
3316 id2hrn.put( idA, hrnB );
3319 // otherwise this is a node present in both graphs
3320 // so make the new reachability set a union of the
3321 // nodes' reachability sets
3322 HeapRegionNode hrnB = id2hrn.get( idA );
3323 hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3328 hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3335 // now add any variable nodes that are in graph B but
3337 sA = rg.td2vn.entrySet();
3339 while( iA.hasNext() ) {
3340 Map.Entry meA = (Map.Entry) iA.next();
3341 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3342 VariableNode lnA = (VariableNode) meA.getValue();
3344 // if the variable doesn't exist in B, allocate and add it
3345 VariableNode lnB = getVariableNodeFromTemp( tdA );
3349 protected void mergeRefEdges( ReachGraph rg ) {
3351 // between heap regions
3352 Set sA = rg.id2hrn.entrySet();
3353 Iterator iA = sA.iterator();
3354 while( iA.hasNext() ) {
3355 Map.Entry meA = (Map.Entry) iA.next();
3356 Integer idA = (Integer) meA.getKey();
3357 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3359 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3360 while( heapRegionsItrA.hasNext() ) {
3361 RefEdge edgeA = heapRegionsItrA.next();
3362 HeapRegionNode hrnChildA = edgeA.getDst();
3363 Integer idChildA = hrnChildA.getID();
3365 // at this point we know an edge in graph A exists
3366 // idA -> idChildA, does this exist in B?
3367 assert id2hrn.containsKey( idA );
3368 HeapRegionNode hrnB = id2hrn.get( idA );
3369 RefEdge edgeToMerge = null;
3371 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3372 while( heapRegionsItrB.hasNext() &&
3373 edgeToMerge == null ) {
3375 RefEdge edgeB = heapRegionsItrB.next();
3376 HeapRegionNode hrnChildB = edgeB.getDst();
3377 Integer idChildB = hrnChildB.getID();
3379 // don't use the RefEdge.equals() here because
3380 // we're talking about existence between graphs,
3381 // not intragraph equal
3382 if( idChildB.equals( idChildA ) &&
3383 edgeB.typeAndFieldEquals( edgeA ) ) {
3385 edgeToMerge = edgeB;
3389 // if the edge from A was not found in B,
3391 if( edgeToMerge == null ) {
3392 assert id2hrn.containsKey( idChildA );
3393 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3394 edgeToMerge = edgeA.copy();
3395 edgeToMerge.setSrc( hrnB );
3396 edgeToMerge.setDst( hrnChildB );
3397 addRefEdge( hrnB, hrnChildB, edgeToMerge );
3399 // otherwise, the edge already existed in both graphs
3400 // so merge their reachability sets
3402 // just replace this beta set with the union
3403 assert edgeToMerge != null;
3404 edgeToMerge.setBeta(
3405 Canonical.unionORpreds( edgeToMerge.getBeta(),
3409 edgeToMerge.setPreds(
3410 Canonical.join( edgeToMerge.getPreds(),
3418 // and then again from variable nodes
3419 sA = rg.td2vn.entrySet();
3421 while( iA.hasNext() ) {
3422 Map.Entry meA = (Map.Entry) iA.next();
3423 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3424 VariableNode vnA = (VariableNode) meA.getValue();
3426 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3427 while( heapRegionsItrA.hasNext() ) {
3428 RefEdge edgeA = heapRegionsItrA.next();
3429 HeapRegionNode hrnChildA = edgeA.getDst();
3430 Integer idChildA = hrnChildA.getID();
3432 // at this point we know an edge in graph A exists
3433 // tdA -> idChildA, does this exist in B?
3434 assert td2vn.containsKey( tdA );
3435 VariableNode vnB = td2vn.get( tdA );
3436 RefEdge edgeToMerge = null;
3438 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3439 while( heapRegionsItrB.hasNext() &&
3440 edgeToMerge == null ) {
3442 RefEdge edgeB = heapRegionsItrB.next();
3443 HeapRegionNode hrnChildB = edgeB.getDst();
3444 Integer idChildB = hrnChildB.getID();
3446 // don't use the RefEdge.equals() here because
3447 // we're talking about existence between graphs
3448 if( idChildB.equals( idChildA ) &&
3449 edgeB.typeAndFieldEquals( edgeA ) ) {
3451 edgeToMerge = edgeB;
3455 // if the edge from A was not found in B,
3457 if( edgeToMerge == null ) {
3458 assert id2hrn.containsKey( idChildA );
3459 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3460 edgeToMerge = edgeA.copy();
3461 edgeToMerge.setSrc( vnB );
3462 edgeToMerge.setDst( hrnChildB );
3463 addRefEdge( vnB, hrnChildB, edgeToMerge );
3465 // otherwise, the edge already existed in both graphs
3466 // so merge their reachability sets
3468 // just replace this beta set with the union
3469 edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3473 edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3482 protected void mergeAllocSites( ReachGraph rg ) {
3483 allocSites.addAll( rg.allocSites );
3488 static boolean dbgEquals = false;
3491 // it is necessary in the equals() member functions
3492 // to "check both ways" when comparing the data
3493 // structures of two graphs. For instance, if all
3494 // edges between heap region nodes in graph A are
3495 // present and equal in graph B it is not sufficient
3496 // to say the graphs are equal. Consider that there
3497 // may be edges in graph B that are not in graph A.
3498 // the only way to know that all edges in both graphs
3499 // are equally present is to iterate over both data
3500 // structures and compare against the other graph.
3501 public boolean equals( ReachGraph rg ) {
3505 System.out.println( "rg is null" );
3510 if( !areHeapRegionNodesEqual( rg ) ) {
3512 System.out.println( "hrn not equal" );
3517 if( !areVariableNodesEqual( rg ) ) {
3519 System.out.println( "vars not equal" );
3524 if( !areRefEdgesEqual( rg ) ) {
3526 System.out.println( "edges not equal" );
3531 // if everything is equal up to this point,
3532 // assert that allocSites is also equal--
3533 // this data is redundant but kept for efficiency
3534 assert allocSites.equals( rg.allocSites );
3540 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3542 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3546 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3553 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3555 Set sA = rgA.id2hrn.entrySet();
3556 Iterator iA = sA.iterator();
3557 while( iA.hasNext() ) {
3558 Map.Entry meA = (Map.Entry) iA.next();
3559 Integer idA = (Integer) meA.getKey();
3560 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3562 if( !rgB.id2hrn.containsKey( idA ) ) {
3566 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3567 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3575 protected boolean areVariableNodesEqual( ReachGraph rg ) {
3577 if( !areallVNinAalsoinBandequal( this, rg ) ) {
3581 if( !areallVNinAalsoinBandequal( rg, this ) ) {
3588 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3590 Set sA = rgA.td2vn.entrySet();
3591 Iterator iA = sA.iterator();
3592 while( iA.hasNext() ) {
3593 Map.Entry meA = (Map.Entry) iA.next();
3594 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3596 if( !rgB.td2vn.containsKey( tdA ) ) {
3605 protected boolean areRefEdgesEqual( ReachGraph rg ) {
3606 if( !areallREinAandBequal( this, rg ) ) {
3613 static protected boolean areallREinAandBequal( ReachGraph rgA,
3616 // check all the heap region->heap region edges
3617 Set sA = rgA.id2hrn.entrySet();
3618 Iterator iA = sA.iterator();
3619 while( iA.hasNext() ) {
3620 Map.Entry meA = (Map.Entry) iA.next();
3621 Integer idA = (Integer) meA.getKey();
3622 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3624 // we should have already checked that the same
3625 // heap regions exist in both graphs
3626 assert rgB.id2hrn.containsKey( idA );
3628 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3632 // then check every edge in B for presence in A, starting
3633 // from the same parent HeapRegionNode
3634 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3636 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3641 // then check all the variable->heap region edges
3642 sA = rgA.td2vn.entrySet();
3644 while( iA.hasNext() ) {
3645 Map.Entry meA = (Map.Entry) iA.next();
3646 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3647 VariableNode vnA = (VariableNode) meA.getValue();
3649 // we should have already checked that the same
3650 // label nodes exist in both graphs
3651 assert rgB.td2vn.containsKey( tdA );
3653 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3657 // then check every edge in B for presence in A, starting
3658 // from the same parent VariableNode
3659 VariableNode vnB = rgB.td2vn.get( tdA );
3661 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3670 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3674 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3675 while( itrA.hasNext() ) {
3676 RefEdge edgeA = itrA.next();
3677 HeapRegionNode hrnChildA = edgeA.getDst();
3678 Integer idChildA = hrnChildA.getID();
3680 assert rgB.id2hrn.containsKey( idChildA );
3682 // at this point we know an edge in graph A exists
3683 // rnA -> idChildA, does this exact edge exist in B?
3684 boolean edgeFound = false;
3686 RefSrcNode rnB = null;
3687 if( rnA instanceof HeapRegionNode ) {
3688 HeapRegionNode hrnA = (HeapRegionNode) rnA;
3689 rnB = rgB.id2hrn.get( hrnA.getID() );
3691 VariableNode vnA = (VariableNode) rnA;
3692 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3695 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3696 while( itrB.hasNext() ) {
3697 RefEdge edgeB = itrB.next();
3698 HeapRegionNode hrnChildB = edgeB.getDst();
3699 Integer idChildB = hrnChildB.getID();
3701 if( idChildA.equals( idChildB ) &&
3702 edgeA.typeAndFieldEquals( edgeB ) ) {
3704 // there is an edge in the right place with the right field,
3705 // but do they have the same attributes?
3706 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3707 edgeA.equalsPreds( edgeB )
3724 // this analysis no longer has the "match anything"
3725 // type which was represented by null
3726 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3727 TypeDescriptor td2 ) {
3731 if( td1.isNull() ) {
3734 if( td2.isNull() ) {
3737 return typeUtil.mostSpecific( td1, td2 );
3740 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3742 TypeDescriptor td3 ) {
3744 return mostSpecificType( td1,
3745 mostSpecificType( td2, td3 )
3749 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3752 TypeDescriptor td4 ) {
3754 return mostSpecificType( mostSpecificType( td1, td2 ),
3755 mostSpecificType( td3, td4 )
3759 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3760 TypeDescriptor possibleChild ) {
3761 assert possibleSuper != null;
3762 assert possibleChild != null;
3764 if( possibleSuper.isNull() ||
3765 possibleChild.isNull() ) {
3769 return typeUtil.isSuperorType( possibleSuper, possibleChild );
3773 protected boolean hasMatchingField( HeapRegionNode src,
3776 TypeDescriptor tdSrc = src.getType();
3777 assert tdSrc != null;
3779 if( tdSrc.isArray() ) {
3780 TypeDescriptor td = edge.getType();
3783 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3784 assert tdSrcDeref != null;
3786 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3790 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3793 // if it's not a class, it doesn't have any fields to match
3794 if( !tdSrc.isClass() ) {
3798 ClassDescriptor cd = tdSrc.getClassDesc();
3799 while( cd != null ) {
3800 Iterator fieldItr = cd.getFields();
3802 while( fieldItr.hasNext() ) {
3803 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3805 if( fd.getType().equals( edge.getType() ) &&
3806 fd.getSymbol().equals( edge.getField() ) ) {
3811 cd = cd.getSuperDesc();
3814 // otherwise it is a class with fields
3815 // but we didn't find a match
3819 protected boolean hasMatchingType( RefEdge edge,
3820 HeapRegionNode dst ) {
3822 // if the region has no type, matches everything
3823 TypeDescriptor tdDst = dst.getType();
3824 assert tdDst != null;
3826 // if the type is not a class or an array, don't
3827 // match because primitives are copied, no aliases
3828 ClassDescriptor cdDst = tdDst.getClassDesc();
3829 if( cdDst == null && !tdDst.isArray() ) {
3833 // if the edge type is null, it matches everything
3834 TypeDescriptor tdEdge = edge.getType();
3835 assert tdEdge != null;
3837 return typeUtil.isSuperorType( tdEdge, tdDst );
3842 // the default signature for quick-and-dirty debugging
3843 public void writeGraph( String graphName ) {
3844 writeGraph( graphName,
3845 true, // write labels
3846 true, // label select
3847 true, // prune garbage
3848 true, // hide subset reachability
3849 true, // hide edge taints
3850 null // in-context boundary
3854 public void writeGraph( String graphName,
3855 boolean writeLabels,
3856 boolean labelSelect,
3857 boolean pruneGarbage,
3858 boolean hideSubsetReachability,
3859 boolean hideEdgeTaints
3861 writeGraph( graphName,
3865 hideSubsetReachability,
3870 public void writeGraph( String graphName,
3871 boolean writeLabels,
3872 boolean labelSelect,
3873 boolean pruneGarbage,
3874 boolean hideSubsetReachability,
3875 boolean hideEdgeTaints,
3876 Set<Integer> callerNodeIDsCopiedToCallee
3880 // remove all non-word characters from the graph name so
3881 // the filename and identifier in dot don't cause errors
3882 graphName = graphName.replaceAll( "[\\W]", "" );
3885 new BufferedWriter( new FileWriter( graphName+".dot" ) );
3887 bw.write( "digraph "+graphName+" {\n" );
3890 // this is an optional step to form the callee-reachable
3891 // "cut-out" into a DOT cluster for visualization
3892 if( callerNodeIDsCopiedToCallee != null ) {
3894 bw.write( " subgraph cluster0 {\n" );
3895 bw.write( " color=blue;\n" );
3897 Iterator i = id2hrn.entrySet().iterator();
3898 while( i.hasNext() ) {
3899 Map.Entry me = (Map.Entry) i.next();
3900 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3902 if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3903 bw.write( " "+hrn.toString()+
3904 hrn.toStringDOT( hideSubsetReachability )+
3914 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3916 // then visit every heap region node
3917 Iterator i = id2hrn.entrySet().iterator();
3918 while( i.hasNext() ) {
3919 Map.Entry me = (Map.Entry) i.next();
3920 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3922 // only visit nodes worth writing out--for instance
3923 // not every node at an allocation is referenced
3924 // (think of it as garbage-collected), etc.
3925 if( !pruneGarbage ||
3926 hrn.isOutOfContext()
3929 if( !visited.contains( hrn ) ) {
3930 traverseHeapRegionNodes( hrn,
3934 hideSubsetReachability,
3936 callerNodeIDsCopiedToCallee );
3941 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
3944 // then visit every label node, useful for debugging
3946 i = td2vn.entrySet().iterator();
3947 while( i.hasNext() ) {
3948 Map.Entry me = (Map.Entry) i.next();
3949 VariableNode vn = (VariableNode) me.getValue();
3952 String labelStr = vn.getTempDescriptorString();
3953 if( labelStr.startsWith( "___temp" ) ||
3954 labelStr.startsWith( "___dst" ) ||
3955 labelStr.startsWith( "___srctmp" ) ||
3956 labelStr.startsWith( "___neverused" )
3962 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3963 while( heapRegionsItr.hasNext() ) {
3964 RefEdge edge = heapRegionsItr.next();
3965 HeapRegionNode hrn = edge.getDst();
3967 if( !visited.contains( hrn ) ) {
3968 traverseHeapRegionNodes( hrn,
3972 hideSubsetReachability,
3974 callerNodeIDsCopiedToCallee );
3977 bw.write( " "+vn.toString()+
3978 " -> "+hrn.toString()+
3979 edge.toStringDOT( hideSubsetReachability, "" )+
3988 } catch( IOException e ) {
3989 throw new Error( "Error writing out DOT graph "+graphName );
3993 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
3996 Set<HeapRegionNode> visited,
3997 boolean hideSubsetReachability,
3998 boolean hideEdgeTaints,
3999 Set<Integer> callerNodeIDsCopiedToCallee
4000 ) throws java.io.IOException {
4002 if( visited.contains( hrn ) ) {
4007 // if we're drawing the callee-view subgraph, only
4008 // write out the node info if it hasn't already been
4010 if( callerNodeIDsCopiedToCallee == null ||
4011 !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
4013 bw.write( " "+hrn.toString()+
4014 hrn.toStringDOT( hideSubsetReachability )+
4018 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4019 while( childRegionsItr.hasNext() ) {
4020 RefEdge edge = childRegionsItr.next();
4021 HeapRegionNode hrnChild = edge.getDst();
4023 if( callerNodeIDsCopiedToCallee != null &&
4024 (edge.getSrc() instanceof HeapRegionNode) ) {
4025 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4026 if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
4027 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4029 bw.write( " "+hrn.toString()+
4030 " -> "+hrnChild.toString()+
4031 edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
4033 } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
4034 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4036 bw.write( " "+hrn.toString()+
4037 " -> "+hrnChild.toString()+
4038 edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
4041 bw.write( " "+hrn.toString()+
4042 " -> "+hrnChild.toString()+
4043 edge.toStringDOT( hideSubsetReachability, "" )+
4047 bw.write( " "+hrn.toString()+
4048 " -> "+hrnChild.toString()+
4049 edge.toStringDOT( hideSubsetReachability, "" )+
4053 traverseHeapRegionNodes( hrnChild,
4057 hideSubsetReachability,
4059 callerNodeIDsCopiedToCallee );
4067 public Set<HeapRegionNode> findCommonReachableNodes( ReachSet proofOfSharing ) {
4069 Set<HeapRegionNode> exhibitProofState =
4070 new HashSet<HeapRegionNode>();
4072 Iterator hrnItr = id2hrn.entrySet().iterator();
4073 while( hrnItr.hasNext() ) {
4074 Map.Entry me = (Map.Entry) hrnItr.next();
4075 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4077 ReachSet intersection =
4078 Canonical.intersection( proofOfSharing,
4081 if( !intersection.isEmpty() ) {
4082 assert !hrn.isOutOfContext();
4083 exhibitProofState.add( hrn );
4087 return exhibitProofState;
4091 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4092 HeapRegionNode hrn2) {
4093 assert hrn1 != null;
4094 assert hrn2 != null;
4096 assert !hrn1.isOutOfContext();
4097 assert !hrn2.isOutOfContext();
4099 assert belongsToThis( hrn1 );
4100 assert belongsToThis( hrn2 );
4102 assert !hrn1.getID().equals( hrn2.getID() );
4105 // then get the various tokens for these heap regions
4107 ReachTuple.factory( hrn1.getID(),
4108 !hrn1.isSingleObject(), // multi?
4109 ReachTuple.ARITY_ONE,
4112 ReachTuple h1star = null;
4113 if( !hrn1.isSingleObject() ) {
4115 ReachTuple.factory( hrn1.getID(),
4116 !hrn1.isSingleObject(),
4117 ReachTuple.ARITY_ZEROORMORE,
4122 ReachTuple.factory( hrn2.getID(),
4123 !hrn2.isSingleObject(),
4124 ReachTuple.ARITY_ONE,
4127 ReachTuple h2star = null;
4128 if( !hrn2.isSingleObject() ) {
4130 ReachTuple.factory( hrn2.getID(),
4131 !hrn2.isSingleObject(),
4132 ReachTuple.ARITY_ZEROORMORE,
4136 // then get the merged beta of all out-going edges from these heap
4139 ReachSet beta1 = ReachSet.factory();
4140 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4141 while (itrEdge.hasNext()) {
4142 RefEdge edge = itrEdge.next();
4143 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4146 ReachSet beta2 = ReachSet.factory();
4147 itrEdge = hrn2.iteratorToReferencees();
4148 while (itrEdge.hasNext()) {
4149 RefEdge edge = itrEdge.next();
4150 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4153 ReachSet proofOfSharing = ReachSet.factory();
4156 Canonical.unionORpreds( proofOfSharing,
4157 beta1.getStatesWithBoth( h1, h2 )
4160 Canonical.unionORpreds( proofOfSharing,
4161 beta2.getStatesWithBoth( h1, h2 )
4164 if( !hrn1.isSingleObject() ) {
4166 Canonical.unionORpreds( proofOfSharing,
4167 beta1.getStatesWithBoth( h1star, h2 )
4170 Canonical.unionORpreds( proofOfSharing,
4171 beta2.getStatesWithBoth( h1star, h2 )
4175 if( !hrn2.isSingleObject() ) {
4177 Canonical.unionORpreds( proofOfSharing,
4178 beta1.getStatesWithBoth( h1, h2star )
4181 Canonical.unionORpreds( proofOfSharing,
4182 beta2.getStatesWithBoth( h1, h2star )
4186 if( !hrn1.isSingleObject() &&
4187 !hrn2.isSingleObject()
4190 Canonical.unionORpreds( proofOfSharing,
4191 beta1.getStatesWithBoth( h1star, h2star )
4194 Canonical.unionORpreds( proofOfSharing,
4195 beta2.getStatesWithBoth( h1star, h2star )
4199 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4200 if( !proofOfSharing.isEmpty() ) {
4201 common = findCommonReachableNodes( proofOfSharing );
4202 if( !DISABLE_STRONG_UPDATES &&
4203 !DISABLE_GLOBAL_SWEEP
4205 assert !common.isEmpty();
4212 // this version of the above method checks whether there is sharing
4213 // among the objects in a summary node
4214 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4216 assert hrn.isNewSummary();
4217 assert !hrn.isOutOfContext();
4218 assert belongsToThis( hrn );
4221 ReachTuple.factory( hrn.getID(),
4223 ReachTuple.ARITY_ZEROORMORE,
4226 // then get the merged beta of all out-going edges from
4229 ReachSet beta = ReachSet.factory();
4230 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4231 while (itrEdge.hasNext()) {
4232 RefEdge edge = itrEdge.next();
4233 beta = Canonical.unionORpreds(beta, edge.getBeta());
4236 ReachSet proofOfSharing = ReachSet.factory();
4239 Canonical.unionORpreds( proofOfSharing,
4240 beta.getStatesWithBoth( hstar, hstar )
4243 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4244 if( !proofOfSharing.isEmpty() ) {
4245 common = findCommonReachableNodes( proofOfSharing );
4246 if( !DISABLE_STRONG_UPDATES &&
4247 !DISABLE_GLOBAL_SWEEP
4249 assert !common.isEmpty();
4257 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4258 Integer paramIndex1,
4259 Integer paramIndex2) {
4261 // get parameter's heap regions
4262 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4263 assert this.hasVariable( paramTemp1 );
4264 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
4267 if( !(paramVar1.getNumReferencees() == 1) ) {
4268 System.out.println( "\n fm="+fm+"\n param="+paramTemp1 );
4269 writeGraph( "whatup" );
4273 assert paramVar1.getNumReferencees() == 1;
4274 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
4275 HeapRegionNode hrnParam1 = paramEdge1.getDst();
4277 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4278 assert this.hasVariable( paramTemp2 );
4279 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
4281 if( !(paramVar2.getNumReferencees() == 1) ) {
4282 System.out.println( "\n fm="+fm+"\n param="+paramTemp2 );
4283 writeGraph( "whatup" );
4286 assert paramVar2.getNumReferencees() == 1;
4287 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
4288 HeapRegionNode hrnParam2 = paramEdge2.getDst();
4290 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4291 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4296 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4300 // get parameter's heap regions
4301 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4302 assert this.hasVariable( paramTemp );
4303 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
4304 assert paramVar.getNumReferencees() == 1;
4305 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
4306 HeapRegionNode hrnParam = paramEdge.getDst();
4309 HeapRegionNode hrnSummary=null;
4310 if(id2hrn.containsKey(as.getSummary())){
4311 // if summary node doesn't exist, ignore this case
4312 hrnSummary = id2hrn.get(as.getSummary());
4313 assert hrnSummary != null;
4316 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4317 if(hrnSummary!=null){
4318 common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4321 // check for other nodes
4322 for (int i = 0; i < as.getAllocationDepth(); ++i) {
4324 assert id2hrn.containsKey(as.getIthOldest(i));
4325 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4326 assert hrnIthOldest != null;
4328 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4335 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4338 // get summary node 1's alpha
4339 Integer idSum1 = as1.getSummary();
4340 HeapRegionNode hrnSum1=null;
4341 if(id2hrn.containsKey(idSum1)){
4342 hrnSum1 = id2hrn.get(idSum1);
4345 // get summary node 2's alpha
4346 Integer idSum2 = as2.getSummary();
4347 HeapRegionNode hrnSum2=null;
4348 if(id2hrn.containsKey(idSum2)){
4349 hrnSum2 = id2hrn.get(idSum2);
4352 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4353 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2){
4354 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4358 // ask if objects from this summary share among each other
4359 common.addAll(mayReachSharedObjects(hrnSum1));
4362 // check sum2 against alloc1 nodes
4364 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4365 Integer idI1 = as1.getIthOldest(i);
4366 assert id2hrn.containsKey(idI1);
4367 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4368 assert hrnI1 != null;
4369 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4372 // also ask if objects from this summary share among each other
4373 common.addAll(mayReachSharedObjects(hrnSum2));
4376 // check sum1 against alloc2 nodes
4377 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4378 Integer idI2 = as2.getIthOldest(i);
4379 assert id2hrn.containsKey(idI2);
4380 HeapRegionNode hrnI2 = id2hrn.get(idI2);
4381 assert hrnI2 != null;
4384 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4387 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4388 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4389 Integer idI1 = as1.getIthOldest(j);
4391 // if these are the same site, don't look for the same token, no
4393 // different tokens of the same site could alias together though
4394 if (idI1.equals(idI2)) {
4398 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4400 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));