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 ) {
1897 rg.writeGraph( "calleeview",
1898 resolveMethodDebugDOTwriteLabels,
1899 resolveMethodDebugDOTselectTemps,
1900 resolveMethodDebugDOTpruneGarbage,
1901 resolveMethodDebugDOThideSubsetReach,
1902 resolveMethodDebugDOThideEdgeTaints );
1903 } catch( IOException e ) {}
1909 private static Hashtable<String, Integer> oocid2hrnid =
1910 new Hashtable<String, Integer>();
1913 // useful since many graphs writes in the method call debug code
1914 private static boolean resolveMethodDebugDOTwriteLabels = true;
1915 private static boolean resolveMethodDebugDOTselectTemps = true;
1916 private static boolean resolveMethodDebugDOTpruneGarbage = true;
1917 private static boolean resolveMethodDebugDOThideSubsetReach = false;
1918 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
1923 resolveMethodCall( FlatCall fc,
1924 FlatMethod fmCallee,
1925 ReachGraph rgCallee,
1926 Set<Integer> callerNodeIDsCopiedToCallee,
1927 boolean writeDebugDOTs
1931 if( writeDebugDOTs ) {
1933 rgCallee.writeGraph( "callee",
1934 resolveMethodDebugDOTwriteLabels,
1935 resolveMethodDebugDOTselectTemps,
1936 resolveMethodDebugDOTpruneGarbage,
1937 resolveMethodDebugDOThideSubsetReach,
1938 resolveMethodDebugDOThideEdgeTaints );
1940 writeGraph( "caller00In",
1941 resolveMethodDebugDOTwriteLabels,
1942 resolveMethodDebugDOTselectTemps,
1943 resolveMethodDebugDOTpruneGarbage,
1944 resolveMethodDebugDOThideSubsetReach,
1945 resolveMethodDebugDOThideEdgeTaints,
1946 callerNodeIDsCopiedToCallee );
1947 } catch( IOException e ) {}
1951 // method call transfer function steps:
1952 // 1. Use current callee-reachable heap (CRH) to test callee
1953 // predicates and mark what will be coming in.
1954 // 2. Wipe CRH out of caller.
1955 // 3. Transplant marked callee parts in:
1956 // a) bring in nodes
1957 // b) bring in callee -> callee edges
1958 // c) resolve out-of-context -> callee edges
1959 // d) assign return value
1960 // 4. Collapse shadow nodes down
1961 // 5. Global sweep it.
1965 // 1. mark what callee elements have satisfied predicates
1966 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1967 new Hashtable<HeapRegionNode, ExistPredSet>();
1969 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1970 new Hashtable<RefEdge, ExistPredSet>();
1972 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1973 new Hashtable<ReachState, ExistPredSet>();
1975 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1976 new Hashtable< RefEdge, Set<RefSrcNode> >();
1978 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1979 while( meItr.hasNext() ) {
1980 Map.Entry me = (Map.Entry) meItr.next();
1981 Integer id = (Integer) me.getKey();
1982 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1984 // if a callee element's predicates are satisfied then a set
1985 // of CALLER predicates is returned: they are the predicates
1986 // that the callee element moved into the caller context
1987 // should have, and it is inefficient to find this again later
1988 ExistPredSet predsIfSatis =
1989 hrnCallee.getPreds().isSatisfiedBy( this,
1990 callerNodeIDsCopiedToCallee
1992 if( predsIfSatis != null ) {
1993 calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1995 // otherwise don't bother looking at edges to this node
1999 // since the node is coming over, find out which reach
2000 // states on it should come over, too
2001 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2002 while( stateItr.hasNext() ) {
2003 ReachState stateCallee = stateItr.next();
2006 stateCallee.getPreds().isSatisfiedBy( this,
2007 callerNodeIDsCopiedToCallee
2009 if( predsIfSatis != null ) {
2010 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2014 // then look at edges to the node
2015 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2016 while( reItr.hasNext() ) {
2017 RefEdge reCallee = reItr.next();
2018 RefSrcNode rsnCallee = reCallee.getSrc();
2020 // (caller local variables to in-context heap regions)
2021 // have an (out-of-context heap region -> in-context heap region)
2022 // abstraction in the callEE, so its true we never need to
2023 // look at a (var node -> heap region) edge in callee to bring
2024 // those over for the call site transfer. What about (param var->heap region)
2025 // edges in callee? They are dealt with below this loop.
2026 // So, yes, at this point skip (var->region) edges in callee
2027 if( rsnCallee instanceof VariableNode ) {
2031 // first see if the source is out-of-context, and only
2032 // proceed with this edge if we find some caller-context
2034 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2035 boolean matchedOutOfContext = false;
2037 if( hrnSrcCallee.isOutOfContext() ) {
2039 assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2041 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2043 // is the target node in the caller?
2044 HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2045 if( hrnDstCaller == null ) {
2049 Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2050 while( reDstItr.hasNext() ) {
2051 // the edge and field (either possibly null) must match
2052 RefEdge reCaller = reDstItr.next();
2054 if( !reCaller.typeEquals ( reCallee.getType() ) ||
2055 !reCaller.fieldEquals( reCallee.getField() )
2060 RefSrcNode rsnCaller = reCaller.getSrc();
2061 if( rsnCaller instanceof VariableNode ) {
2062 // a variable node matches an OOC region with null type
2063 if( hrnSrcCallee.getType() != null ) {
2068 // otherwise types should match
2069 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2070 if( hrnSrcCallee.getType() == null ) {
2071 if( hrnCallerSrc.getType() != null ) {
2075 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2081 rsnCallers.add( rsnCaller );
2082 matchedOutOfContext = true;
2085 if( !rsnCallers.isEmpty() ) {
2086 calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2090 if( hrnSrcCallee.isOutOfContext() &&
2091 !matchedOutOfContext ) {
2096 reCallee.getPreds().isSatisfiedBy( this,
2097 callerNodeIDsCopiedToCallee
2099 if( predsIfSatis != null ) {
2100 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2102 // since the edge is coming over, find out which reach
2103 // states on it should come over, too
2104 stateItr = reCallee.getBeta().iterator();
2105 while( stateItr.hasNext() ) {
2106 ReachState stateCallee = stateItr.next();
2109 stateCallee.getPreds().isSatisfiedBy( this,
2110 callerNodeIDsCopiedToCallee
2112 if( predsIfSatis != null ) {
2113 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2120 // test param -> HRN edges, also
2121 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
2123 // parameter defined here is the symbol in the callee
2124 TempDescriptor tdParam = fmCallee.getParameter( i );
2125 VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
2127 Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
2128 while( reItr.hasNext() ) {
2129 RefEdge reCallee = reItr.next();
2131 ExistPredSet ifDst =
2132 reCallee.getDst().getPreds().isSatisfiedBy( this,
2133 callerNodeIDsCopiedToCallee
2135 if( ifDst == null ) {
2139 ExistPredSet predsIfSatis =
2140 reCallee.getPreds().isSatisfiedBy( this,
2141 callerNodeIDsCopiedToCallee
2143 if( predsIfSatis != null ) {
2144 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2146 // since the edge is coming over, find out which reach
2147 // states on it should come over, too
2148 Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
2149 while( stateItr.hasNext() ) {
2150 ReachState stateCallee = stateItr.next();
2153 stateCallee.getPreds().isSatisfiedBy( this,
2154 callerNodeIDsCopiedToCallee
2156 if( predsIfSatis != null ) {
2157 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2168 if( writeDebugDOTs ) {
2170 writeGraph( "caller20BeforeWipe",
2171 resolveMethodDebugDOTwriteLabels,
2172 resolveMethodDebugDOTselectTemps,
2173 resolveMethodDebugDOTpruneGarbage,
2174 resolveMethodDebugDOThideSubsetReach,
2175 resolveMethodDebugDOThideEdgeTaints );
2176 } catch( IOException e ) {}
2180 // 2. predicates tested, ok to wipe out caller part
2181 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2182 while( hrnItr.hasNext() ) {
2183 Integer hrnID = hrnItr.next();
2184 HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2185 assert hrnCaller != null;
2187 // when clearing off nodes, also eliminate variable
2189 wipeOut( hrnCaller, true );
2194 if( writeDebugDOTs ) {
2196 writeGraph( "caller30BeforeAddingNodes",
2197 resolveMethodDebugDOTwriteLabels,
2198 resolveMethodDebugDOTselectTemps,
2199 resolveMethodDebugDOTpruneGarbage,
2200 resolveMethodDebugDOThideSubsetReach,
2201 resolveMethodDebugDOThideEdgeTaints );
2202 } catch( IOException e ) {}
2206 // 3. callee elements with satisfied preds come in, note that
2207 // the mapping of elements satisfied to preds is like this:
2208 // A callee element EE has preds EEp that are satisfied by
2209 // some caller element ER. We bring EE into the caller
2210 // context as ERee with the preds of ER, namely ERp, which
2211 // in the following algorithm is the value in the mapping
2214 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2215 while( satisItr.hasNext() ) {
2216 Map.Entry me = (Map.Entry) satisItr.next();
2217 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2218 ExistPredSet preds = (ExistPredSet) me.getValue();
2220 // TODO: I think its true that the current implementation uses
2221 // the type of the OOC region and the predicates OF THE EDGE from
2222 // it to link everything up in caller context, so that's why we're
2223 // skipping this... maybe that's a sillier way to do it?
2224 if( hrnCallee.isOutOfContext() ) {
2228 AllocSite as = hrnCallee.getAllocSite();
2229 allocSites.add( as );
2231 Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2233 HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2234 if( hrnCaller == null ) {
2236 createNewHeapRegionNode( hrnIDshadow, // id or null to generate a new one
2237 hrnCallee.isSingleObject(), // single object?
2238 hrnCallee.isNewSummary(), // summary?
2239 hrnCallee.isFlagged(), // flagged?
2240 false, // out-of-context?
2241 hrnCallee.getType(), // type
2242 hrnCallee.getAllocSite(), // allocation site
2243 toCallerContext( hrnCallee.getInherent(),
2244 calleeStatesSatisfied ), // inherent reach
2245 null, // current reach
2246 predsEmpty, // predicates
2247 hrnCallee.getDescription() // description
2250 assert hrnCaller.isWiped();
2253 hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2254 calleeStatesSatisfied
2258 hrnCaller.setPreds( preds );
2263 if( writeDebugDOTs ) {
2265 writeGraph( "caller31BeforeAddingEdges",
2266 resolveMethodDebugDOTwriteLabels,
2267 resolveMethodDebugDOTselectTemps,
2268 resolveMethodDebugDOTpruneGarbage,
2269 resolveMethodDebugDOThideSubsetReach,
2270 resolveMethodDebugDOThideEdgeTaints );
2271 } catch( IOException e ) {}
2275 // set these up during the next procedure so after
2276 // the caller has all of its nodes and edges put
2277 // back together we can propagate the callee's
2278 // reach changes backwards into the caller graph
2279 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2281 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2282 new Hashtable<RefEdge, ChangeSet>();
2285 // 3.b) callee -> callee edges AND out-of-context -> callee
2286 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2287 while( satisItr.hasNext() ) {
2288 Map.Entry me = (Map.Entry) satisItr.next();
2289 RefEdge reCallee = (RefEdge) me.getKey();
2290 ExistPredSet preds = (ExistPredSet) me.getValue();
2292 HeapRegionNode hrnDstCallee = reCallee.getDst();
2293 AllocSite asDst = hrnDstCallee.getAllocSite();
2294 allocSites.add( asDst );
2296 Integer hrnIDDstShadow =
2297 asDst.getShadowIDfromID( hrnDstCallee.getID() );
2299 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2300 assert hrnDstCaller != null;
2303 RefSrcNode rsnCallee = reCallee.getSrc();
2305 Set<RefSrcNode> rsnCallers =
2306 new HashSet<RefSrcNode>();
2308 Set<RefSrcNode> oocCallers =
2309 calleeEdges2oocCallerSrcMatches.get( reCallee );
2311 boolean oocEdges = false;
2313 if( oocCallers == null ) {
2314 // there are no out-of-context matches, so it's
2315 // either a param/arg var or one in-context heap region
2316 if( rsnCallee instanceof VariableNode ) {
2317 // variable -> node in the callee should only
2318 // come into the caller if its from a param var
2319 VariableNode vnCallee = (VariableNode) rsnCallee;
2320 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2321 TempDescriptor tdArg = fc.getArgMatchingParam( fmCallee,
2323 if( tdArg == null ) {
2324 // this means the variable isn't a parameter, its local
2325 // to the callee so we ignore it in call site transfer
2326 // shouldn't this NEVER HAPPEN?
2329 rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2333 // otherwise source is in context, one region
2334 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2336 // translate an in-context node to shadow
2337 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2338 allocSites.add( asSrc );
2340 Integer hrnIDSrcShadow =
2341 asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2343 HeapRegionNode hrnSrcCallerShadow =
2344 this.id2hrn.get( hrnIDSrcShadow );
2346 if( hrnSrcCallerShadow == null ) {
2347 hrnSrcCallerShadow =
2348 createNewHeapRegionNode( hrnIDSrcShadow, // id or null to generate a new one
2349 hrnSrcCallee.isSingleObject(), // single object?
2350 hrnSrcCallee.isNewSummary(), // summary?
2351 hrnSrcCallee.isFlagged(), // flagged?
2352 false, // out-of-context?
2353 hrnSrcCallee.getType(), // type
2354 hrnSrcCallee.getAllocSite(), // allocation site
2355 toCallerContext( hrnSrcCallee.getInherent(),
2356 calleeStatesSatisfied ), // inherent reach
2357 toCallerContext( hrnSrcCallee.getAlpha(),
2358 calleeStatesSatisfied ), // current reach
2359 predsEmpty, // predicates
2360 hrnSrcCallee.getDescription() // description
2364 rsnCallers.add( hrnSrcCallerShadow );
2368 // otherwise we have a set of out-of-context srcs
2369 // that should NOT be translated to shadow nodes
2370 assert !oocCallers.isEmpty();
2371 rsnCallers.addAll( oocCallers );
2375 // now make all caller edges we've identified from
2376 // this callee edge with a satisfied predicate
2377 assert !rsnCallers.isEmpty();
2378 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2379 while( rsnItr.hasNext() ) {
2380 RefSrcNode rsnCaller = rsnItr.next();
2382 RefEdge reCaller = new RefEdge( rsnCaller,
2385 reCallee.getField(),
2386 toCallerContext( reCallee.getBeta(),
2387 calleeStatesSatisfied ),
2391 ChangeSet cs = ChangeSet.factory();
2392 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2393 while( rsItr.hasNext() ) {
2394 ReachState state = rsItr.next();
2395 ExistPredSet predsPreCallee = state.getPreds();
2397 if( state.isEmpty() ) {
2401 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2402 while( predItr.hasNext() ) {
2403 ExistPred pred = predItr.next();
2404 ReachState old = pred.ne_state;
2410 cs = Canonical.add( cs,
2411 ChangeTuple.factory( old,
2419 // look to see if an edge with same field exists
2420 // and merge with it, otherwise just add the edge
2421 RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2425 if( edgeExisting != null ) {
2426 edgeExisting.setBeta(
2427 Canonical.unionORpreds( edgeExisting.getBeta(),
2431 edgeExisting.setPreds(
2432 Canonical.join( edgeExisting.getPreds(),
2437 // for reach propagation
2438 if( !cs.isEmpty() ) {
2439 edgePlannedChanges.put(
2441 Canonical.union( edgePlannedChanges.get( edgeExisting ),
2448 addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2450 // for reach propagation
2451 if( !cs.isEmpty() ) {
2452 edgesForPropagation.add( reCaller );
2453 assert !edgePlannedChanges.containsKey( reCaller );
2454 edgePlannedChanges.put( reCaller, cs );
2464 if( writeDebugDOTs ) {
2466 writeGraph( "caller35BeforeAssignReturnValue",
2467 resolveMethodDebugDOTwriteLabels,
2468 resolveMethodDebugDOTselectTemps,
2469 resolveMethodDebugDOTpruneGarbage,
2470 resolveMethodDebugDOThideSubsetReach,
2471 resolveMethodDebugDOThideEdgeTaints );
2472 } catch( IOException e ) {}
2477 // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2478 // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2479 // EDGES, JUST BRINGING THEM ALL! It'll work for now, over approximation
2481 // 3.d) handle return value assignment if needed
2482 TempDescriptor returnTemp = fc.getReturnTemp();
2483 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2485 VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2486 clearRefEdgesFrom( vnLhsCaller, null, null, true );
2488 VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2489 Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2490 while( reCalleeItr.hasNext() ) {
2491 RefEdge reCallee = reCalleeItr.next();
2492 HeapRegionNode hrnDstCallee = reCallee.getDst();
2494 // some edge types are not possible return values when we can
2495 // see what type variable we are assigning it to
2496 if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2497 System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2498 reCallee+" for return temp "+returnTemp );
2503 AllocSite asDst = hrnDstCallee.getAllocSite();
2504 allocSites.add( asDst );
2506 Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2508 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2509 if( hrnDstCaller == null ) {
2511 createNewHeapRegionNode( hrnIDDstShadow, // id or null to generate a new one
2512 hrnDstCallee.isSingleObject(), // single object?
2513 hrnDstCallee.isNewSummary(), // summary?
2514 hrnDstCallee.isFlagged(), // flagged?
2515 false, // out-of-context?
2516 hrnDstCallee.getType(), // type
2517 hrnDstCallee.getAllocSite(), // allocation site
2518 toCallerContext( hrnDstCallee.getInherent(),
2519 calleeStatesSatisfied ), // inherent reach
2520 toCallerContext( hrnDstCallee.getAlpha(),
2521 calleeStatesSatisfied ), // current reach
2522 predsTrue, // predicates
2523 hrnDstCallee.getDescription() // description
2527 TypeDescriptor tdNewEdge =
2528 mostSpecificType( reCallee.getType(),
2529 hrnDstCallee.getType(),
2530 hrnDstCaller.getType()
2533 RefEdge reCaller = new RefEdge( vnLhsCaller,
2537 toCallerContext( reCallee.getBeta(),
2538 calleeStatesSatisfied ),
2542 addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2548 if( writeDebugDOTs ) {
2550 writeGraph( "caller38propagateReach",
2551 resolveMethodDebugDOTwriteLabels,
2552 resolveMethodDebugDOTselectTemps,
2553 resolveMethodDebugDOTpruneGarbage,
2554 resolveMethodDebugDOThideSubsetReach,
2555 resolveMethodDebugDOThideEdgeTaints );
2556 } catch( IOException e ) {}
2559 // propagate callee reachability changes to the rest
2560 // of the caller graph edges
2561 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2563 propagateTokensOverEdges( edgesForPropagation, // source edges
2564 edgePlannedChanges, // map src edge to change set
2565 edgesUpdated ); // list of updated edges
2567 // commit beta' (beta<-betaNew)
2568 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2569 while( edgeItr.hasNext() ) {
2570 edgeItr.next().applyBetaNew();
2578 if( writeDebugDOTs ) {
2580 writeGraph( "caller40BeforeShadowMerge",
2581 resolveMethodDebugDOTwriteLabels,
2582 resolveMethodDebugDOTselectTemps,
2583 resolveMethodDebugDOTpruneGarbage,
2584 resolveMethodDebugDOThideSubsetReach,
2585 resolveMethodDebugDOThideEdgeTaints );
2586 } catch( IOException e ) {}
2590 // 4) merge shadow nodes so alloc sites are back to k
2591 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2592 while( asItr.hasNext() ) {
2593 // for each allocation site do the following to merge
2594 // shadow nodes (newest from callee) with any existing
2595 // look for the newest normal and newest shadow "slot"
2596 // not being used, transfer normal to shadow. Keep
2597 // doing this until there are no more normal nodes, or
2598 // no empty shadow slots: then merge all remaining normal
2599 // nodes into the shadow summary. Finally, convert all
2600 // shadow to their normal versions.
2601 AllocSite as = asItr.next();
2604 while( ageNorm < allocationDepth &&
2605 ageShad < allocationDepth ) {
2607 // first, are there any normal nodes left?
2608 Integer idNorm = as.getIthOldest( ageNorm );
2609 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2610 if( hrnNorm == null ) {
2611 // no, this age of normal node not in the caller graph
2616 // yes, a normal node exists, is there an empty shadow
2617 // "slot" to transfer it onto?
2618 HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2619 if( !hrnShad.isWiped() ) {
2620 // no, this age of shadow node is not empty
2625 // yes, this shadow node is empty
2626 transferOnto( hrnNorm, hrnShad );
2631 // now, while there are still normal nodes but no shadow
2632 // slots, merge normal nodes into the shadow summary
2633 while( ageNorm < allocationDepth ) {
2635 // first, are there any normal nodes left?
2636 Integer idNorm = as.getIthOldest( ageNorm );
2637 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2638 if( hrnNorm == null ) {
2639 // no, this age of normal node not in the caller graph
2644 // yes, a normal node exists, so get the shadow summary
2645 HeapRegionNode summShad = getSummaryNode( as, true );
2646 mergeIntoSummary( hrnNorm, summShad );
2650 // if there is a normal summary, merge it into shadow summary
2651 Integer idNorm = as.getSummary();
2652 HeapRegionNode summNorm = id2hrn.get( idNorm );
2653 if( summNorm != null ) {
2654 HeapRegionNode summShad = getSummaryNode( as, true );
2655 mergeIntoSummary( summNorm, summShad );
2658 // finally, flip all existing shadow nodes onto the normal
2659 for( int i = 0; i < allocationDepth; ++i ) {
2660 Integer idShad = as.getIthOldestShadow( i );
2661 HeapRegionNode hrnShad = id2hrn.get( idShad );
2662 if( hrnShad != null ) {
2664 HeapRegionNode hrnNorm = getIthNode( as, i, false );
2665 assert hrnNorm.isWiped();
2666 transferOnto( hrnShad, hrnNorm );
2670 Integer idShad = as.getSummaryShadow();
2671 HeapRegionNode summShad = id2hrn.get( idShad );
2672 if( summShad != null ) {
2673 summNorm = getSummaryNode( as, false );
2674 transferOnto( summShad, summNorm );
2679 if( writeDebugDOTs ) {
2681 writeGraph( "caller45BeforeUnshadow",
2682 resolveMethodDebugDOTwriteLabels,
2683 resolveMethodDebugDOTselectTemps,
2684 resolveMethodDebugDOTpruneGarbage,
2685 resolveMethodDebugDOThideSubsetReach,
2686 resolveMethodDebugDOThideEdgeTaints );
2687 } catch( IOException e ) {}
2691 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2692 while( itrAllHRNodes.hasNext() ) {
2693 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
2694 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2696 hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2698 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2699 while( itrEdges.hasNext() ) {
2700 RefEdge re = itrEdges.next();
2701 re.setBeta( unshadow( re.getBeta() ) );
2707 if( writeDebugDOTs ) {
2709 writeGraph( "caller50BeforeGlobalSweep",
2710 resolveMethodDebugDOTwriteLabels,
2711 resolveMethodDebugDOTselectTemps,
2712 resolveMethodDebugDOTpruneGarbage,
2713 resolveMethodDebugDOThideSubsetReach,
2714 resolveMethodDebugDOThideEdgeTaints );
2715 } catch( IOException e ) {}
2720 if( !DISABLE_GLOBAL_SWEEP ) {
2726 if( writeDebugDOTs ) {
2728 writeGraph( "caller90AfterTransfer",
2729 resolveMethodDebugDOTwriteLabels,
2730 resolveMethodDebugDOTselectTemps,
2731 resolveMethodDebugDOTpruneGarbage,
2732 resolveMethodDebugDOThideSubsetReach,
2733 resolveMethodDebugDOThideEdgeTaints );
2734 } catch( IOException e ) {}
2740 ////////////////////////////////////////////////////
2742 // Abstract garbage collection simply removes
2743 // heap region nodes that are not mechanically
2744 // reachable from a root set. This step is
2745 // essential for testing node and edge existence
2746 // predicates efficiently
2748 ////////////////////////////////////////////////////
2749 public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2751 // calculate a root set, will be different for Java
2752 // version of analysis versus Bamboo version
2753 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2755 // visit every variable in graph while building root
2756 // set, and do iterating on a copy, so we can remove
2757 // dead variables while we're at this
2758 Iterator makeCopyItr = td2vn.entrySet().iterator();
2759 Set entrysCopy = new HashSet();
2760 while( makeCopyItr.hasNext() ) {
2761 entrysCopy.add( makeCopyItr.next() );
2764 Iterator eItr = entrysCopy.iterator();
2765 while( eItr.hasNext() ) {
2766 Map.Entry me = (Map.Entry) eItr.next();
2767 TempDescriptor td = (TempDescriptor) me.getKey();
2768 VariableNode vn = (VariableNode) me.getValue();
2770 if( liveSet.contains( td ) ) {
2774 // dead var, remove completely from graph
2776 clearRefEdgesFrom( vn, null, null, true );
2780 // everything visited in a traversal is
2781 // considered abstractly live
2782 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2784 while( !toVisit.isEmpty() ) {
2785 RefSrcNode rsn = toVisit.iterator().next();
2786 toVisit.remove( rsn );
2789 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2790 while( hrnItr.hasNext() ) {
2791 RefEdge edge = hrnItr.next();
2792 HeapRegionNode hrn = edge.getDst();
2794 if( !visited.contains( hrn ) ) {
2800 // get a copy of the set to iterate over because
2801 // we're going to monkey with the graph when we
2802 // identify a garbage node
2803 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2804 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2805 while( hrnItr.hasNext() ) {
2806 hrnAllPrior.add( hrnItr.next() );
2809 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2810 while( hrnAllItr.hasNext() ) {
2811 HeapRegionNode hrn = hrnAllItr.next();
2813 if( !visited.contains( hrn ) ) {
2815 // heap region nodes are compared across ReachGraph
2816 // objects by their integer ID, so when discarding
2817 // garbage nodes we must also discard entries in
2818 // the ID -> heap region hashtable.
2819 id2hrn.remove( hrn.getID() );
2821 // RefEdge objects are two-way linked between
2822 // nodes, so when a node is identified as garbage,
2823 // actively clear references to and from it so
2824 // live nodes won't have dangling RefEdge's
2825 wipeOut( hrn, true );
2827 // if we just removed the last node from an allocation
2828 // site, it should be taken out of the ReachGraph's list
2829 AllocSite as = hrn.getAllocSite();
2830 if( !hasNodesOf( as ) ) {
2831 allocSites.remove( as );
2837 protected boolean hasNodesOf( AllocSite as ) {
2838 if( id2hrn.containsKey( as.getSummary() ) ) {
2842 for( int i = 0; i < allocationDepth; ++i ) {
2843 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2851 ////////////////////////////////////////////////////
2853 // This global sweep is an optional step to prune
2854 // reachability sets that are not internally
2855 // consistent with the global graph. It should be
2856 // invoked after strong updates or method calls.
2858 ////////////////////////////////////////////////////
2859 public void globalSweep() {
2861 // boldB is part of the phase 1 sweep
2862 // it has an in-context table and an out-of-context table
2863 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2864 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2866 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2867 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2869 // visit every heap region to initialize alphaNew and betaNew,
2870 // and make a map of every hrnID to the source nodes it should
2871 // propagate forward from. In-context flagged hrnID's propagate
2872 // from only the in-context node they name, but out-of-context
2873 // ID's may propagate from several out-of-context nodes
2874 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2875 new Hashtable< Integer, Set<HeapRegionNode> >();
2877 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2878 new Hashtable< Integer, Set<HeapRegionNode> >();
2881 Iterator itrHrns = id2hrn.entrySet().iterator();
2882 while( itrHrns.hasNext() ) {
2883 Map.Entry me = (Map.Entry) itrHrns.next();
2884 Integer hrnID = (Integer) me.getKey();
2885 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2887 // assert that this node and incoming edges have clean alphaNew
2888 // and betaNew sets, respectively
2889 assert rsetEmpty.equals( hrn.getAlphaNew() );
2891 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2892 while( itrRers.hasNext() ) {
2893 RefEdge edge = itrRers.next();
2894 assert rsetEmpty.equals( edge.getBetaNew() );
2897 // make a mapping of IDs to heap regions they propagate from
2898 if( hrn.isFlagged() ) {
2899 assert !hrn.isOutOfContext();
2900 assert !icID2srcs.containsKey( hrn.getID() );
2902 // in-context flagged node IDs simply propagate from the
2904 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2906 icID2srcs.put( hrn.getID(), srcs );
2909 if( hrn.isOutOfContext() ) {
2910 assert !hrn.isFlagged();
2912 // the reachability states on an out-of-context
2913 // node are not really important (combinations of
2914 // IDs or arity)--what matters is that the states
2915 // specify which nodes this out-of-context node
2916 // stands in for. For example, if the state [17?, 19*]
2917 // appears on the ooc node, it may serve as a source
2918 // for node 17? and a source for node 19.
2919 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2920 while( stateItr.hasNext() ) {
2921 ReachState state = stateItr.next();
2923 Iterator<ReachTuple> rtItr = state.iterator();
2924 while( rtItr.hasNext() ) {
2925 ReachTuple rt = rtItr.next();
2926 assert rt.isOutOfContext();
2928 Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2929 if( srcs == null ) {
2930 srcs = new HashSet<HeapRegionNode>();
2933 oocID2srcs.put( rt.getHrnID(), srcs );
2939 // calculate boldB for all hrnIDs identified by the above
2940 // node traversal, propagating from every source
2941 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2944 Set<HeapRegionNode> srcs;
2947 if( !icID2srcs.isEmpty() ) {
2948 Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2949 hrnID = (Integer) me.getKey();
2950 srcs = (Set<HeapRegionNode>) me.getValue();
2952 icID2srcs.remove( hrnID );
2955 assert !oocID2srcs.isEmpty();
2957 Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2958 hrnID = (Integer) me.getKey();
2959 srcs = (Set<HeapRegionNode>) me.getValue();
2961 oocID2srcs.remove( hrnID );
2965 Hashtable<RefEdge, ReachSet> boldB_f =
2966 new Hashtable<RefEdge, ReachSet>();
2968 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2970 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2971 while( hrnItr.hasNext() ) {
2972 HeapRegionNode hrn = hrnItr.next();
2974 assert workSetEdges.isEmpty();
2976 // initial boldB_f constraints
2977 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2978 while( itrRees.hasNext() ) {
2979 RefEdge edge = itrRees.next();
2981 assert !boldB_f.containsKey( edge );
2982 boldB_f.put( edge, edge.getBeta() );
2984 assert !workSetEdges.contains( edge );
2985 workSetEdges.add( edge );
2988 // enforce the boldB_f constraint at edges until we reach a fixed point
2989 while( !workSetEdges.isEmpty() ) {
2990 RefEdge edge = workSetEdges.iterator().next();
2991 workSetEdges.remove( edge );
2993 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2994 while( itrPrime.hasNext() ) {
2995 RefEdge edgePrime = itrPrime.next();
2997 ReachSet prevResult = boldB_f.get( edgePrime );
2998 ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
3002 if( prevResult == null ||
3003 Canonical.unionORpreds( prevResult,
3004 intersection ).size()
3008 if( prevResult == null ) {
3009 boldB_f.put( edgePrime,
3010 Canonical.unionORpreds( edgePrime.getBeta(),
3015 boldB_f.put( edgePrime,
3016 Canonical.unionORpreds( prevResult,
3021 workSetEdges.add( edgePrime );
3028 boldBic.put( hrnID, boldB_f );
3030 boldBooc.put( hrnID, boldB_f );
3035 // use boldB to prune hrnIDs from alpha states that are impossible
3036 // and propagate the differences backwards across edges
3037 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3039 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3040 new Hashtable<RefEdge, ChangeSet>();
3043 itrHrns = id2hrn.entrySet().iterator();
3044 while( itrHrns.hasNext() ) {
3045 Map.Entry me = (Map.Entry) itrHrns.next();
3046 Integer hrnID = (Integer) me.getKey();
3047 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3049 // out-of-context nodes don't participate in the
3050 // global sweep, they serve as sources for the pass
3052 if( hrn.isOutOfContext() ) {
3056 // the inherent states of a region are the exception
3057 // to removal as the global sweep prunes
3058 ReachTuple rtException = ReachTuple.factory( hrnID,
3059 !hrn.isSingleObject(),
3060 ReachTuple.ARITY_ONE,
3061 false // out-of-context
3064 ChangeSet cts = ChangeSet.factory();
3066 // mark hrnIDs for removal
3067 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3068 while( stateItr.hasNext() ) {
3069 ReachState stateOld = stateItr.next();
3071 ReachState markedHrnIDs = ReachState.factory();
3073 Iterator<ReachTuple> rtItr = stateOld.iterator();
3074 while( rtItr.hasNext() ) {
3075 ReachTuple rtOld = rtItr.next();
3077 // never remove the inherent hrnID from a flagged region
3078 // because it is trivially satisfied
3079 if( hrn.isFlagged() ) {
3080 if( rtOld == rtException ) {
3085 // does boldB allow this hrnID?
3086 boolean foundState = false;
3087 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3088 while( incidentEdgeItr.hasNext() ) {
3089 RefEdge incidentEdge = incidentEdgeItr.next();
3091 Hashtable<RefEdge, ReachSet> B;
3092 if( rtOld.isOutOfContext() ) {
3093 B = boldBooc.get( rtOld.getHrnID() );
3095 assert id2hrn.containsKey( rtOld.getHrnID() );
3096 B = boldBic.get( rtOld.getHrnID() );
3100 ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3101 if( boldB_rtOld_incident != null &&
3102 boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
3110 markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3114 // if there is nothing marked, just move on
3115 if( markedHrnIDs.isEmpty() ) {
3116 hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3123 // remove all marked hrnIDs and establish a change set that should
3124 // propagate backwards over edges from this node
3125 ReachState statePruned = ReachState.factory();
3126 rtItr = stateOld.iterator();
3127 while( rtItr.hasNext() ) {
3128 ReachTuple rtOld = rtItr.next();
3130 if( !markedHrnIDs.containsTuple( rtOld ) ) {
3131 statePruned = Canonical.add( statePruned, rtOld );
3134 assert !stateOld.equals( statePruned );
3136 hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3140 ChangeTuple ct = ChangeTuple.factory( stateOld,
3143 cts = Canonical.add( cts, ct );
3146 // throw change tuple set on all incident edges
3147 if( !cts.isEmpty() ) {
3148 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3149 while( incidentEdgeItr.hasNext() ) {
3150 RefEdge incidentEdge = incidentEdgeItr.next();
3152 edgesForPropagation.add( incidentEdge );
3154 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3155 edgePlannedChanges.put( incidentEdge, cts );
3157 edgePlannedChanges.put(
3159 Canonical.union( edgePlannedChanges.get( incidentEdge ),
3168 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3170 propagateTokensOverEdges( edgesForPropagation,
3174 // at the end of the 1st phase reference edges have
3175 // beta, betaNew that correspond to beta and betaR
3177 // commit beta<-betaNew, so beta=betaR and betaNew
3178 // will represent the beta' calculation in 2nd phase
3180 // commit alpha<-alphaNew because it won't change
3181 HashSet<RefEdge> res = new HashSet<RefEdge>();
3183 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3184 while( nodeItr.hasNext() ) {
3185 HeapRegionNode hrn = nodeItr.next();
3187 // as mentioned above, out-of-context nodes only serve
3188 // as sources of reach states for the sweep, not part
3190 if( hrn.isOutOfContext() ) {
3191 assert hrn.getAlphaNew().equals( rsetEmpty );
3193 hrn.applyAlphaNew();
3196 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3197 while( itrRes.hasNext() ) {
3198 res.add( itrRes.next() );
3204 Iterator<RefEdge> edgeItr = res.iterator();
3205 while( edgeItr.hasNext() ) {
3206 RefEdge edge = edgeItr.next();
3207 HeapRegionNode hrn = edge.getDst();
3209 // commit results of last phase
3210 if( edgesUpdated.contains( edge ) ) {
3211 edge.applyBetaNew();
3214 // compute intial condition of 2nd phase
3215 edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3221 // every edge in the graph is the initial workset
3222 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3223 while( !edgeWorkSet.isEmpty() ) {
3224 RefEdge edgePrime = edgeWorkSet.iterator().next();
3225 edgeWorkSet.remove( edgePrime );
3227 RefSrcNode rsn = edgePrime.getSrc();
3228 if( !(rsn instanceof HeapRegionNode) ) {
3231 HeapRegionNode hrn = (HeapRegionNode) rsn;
3233 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3234 while( itrEdge.hasNext() ) {
3235 RefEdge edge = itrEdge.next();
3237 ReachSet prevResult = edge.getBetaNew();
3238 assert prevResult != null;
3240 ReachSet intersection =
3241 Canonical.intersection( edge.getBeta(),
3242 edgePrime.getBetaNew()
3245 if( Canonical.unionORpreds( prevResult,
3252 Canonical.unionORpreds( prevResult,
3256 edgeWorkSet.add( edge );
3261 // commit beta' (beta<-betaNew)
3262 edgeItr = res.iterator();
3263 while( edgeItr.hasNext() ) {
3264 edgeItr.next().applyBetaNew();
3270 ////////////////////////////////////////////////////
3271 // high-level merge operations
3272 ////////////////////////////////////////////////////
3273 public void merge_sameMethodContext( ReachGraph rg ) {
3274 // when merging two graphs that abstract the heap
3275 // of the same method context, we just call the
3276 // basic merge operation
3280 public void merge_diffMethodContext( ReachGraph rg ) {
3281 // when merging graphs for abstract heaps in
3282 // different method contexts we should:
3283 // 1) age the allocation sites?
3287 ////////////////////////////////////////////////////
3288 // in merge() and equals() methods the suffix A
3289 // represents the passed in graph and the suffix
3290 // B refers to the graph in this object
3291 // Merging means to take the incoming graph A and
3292 // merge it into B, so after the operation graph B
3293 // is the final result.
3294 ////////////////////////////////////////////////////
3295 protected void merge( ReachGraph rg ) {
3302 mergeRefEdges ( rg );
3303 mergeAllocSites( rg );
3306 protected void mergeNodes( ReachGraph rg ) {
3308 // start with heap region nodes
3309 Set sA = rg.id2hrn.entrySet();
3310 Iterator iA = sA.iterator();
3311 while( iA.hasNext() ) {
3312 Map.Entry meA = (Map.Entry) iA.next();
3313 Integer idA = (Integer) meA.getKey();
3314 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3316 // if this graph doesn't have a node the
3317 // incoming graph has, allocate it
3318 if( !id2hrn.containsKey( idA ) ) {
3319 HeapRegionNode hrnB = hrnA.copy();
3320 id2hrn.put( idA, hrnB );
3323 // otherwise this is a node present in both graphs
3324 // so make the new reachability set a union of the
3325 // nodes' reachability sets
3326 HeapRegionNode hrnB = id2hrn.get( idA );
3327 hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3332 hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3339 // now add any variable nodes that are in graph B but
3341 sA = rg.td2vn.entrySet();
3343 while( iA.hasNext() ) {
3344 Map.Entry meA = (Map.Entry) iA.next();
3345 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3346 VariableNode lnA = (VariableNode) meA.getValue();
3348 // if the variable doesn't exist in B, allocate and add it
3349 VariableNode lnB = getVariableNodeFromTemp( tdA );
3353 protected void mergeRefEdges( ReachGraph rg ) {
3355 // between heap regions
3356 Set sA = rg.id2hrn.entrySet();
3357 Iterator iA = sA.iterator();
3358 while( iA.hasNext() ) {
3359 Map.Entry meA = (Map.Entry) iA.next();
3360 Integer idA = (Integer) meA.getKey();
3361 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3363 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3364 while( heapRegionsItrA.hasNext() ) {
3365 RefEdge edgeA = heapRegionsItrA.next();
3366 HeapRegionNode hrnChildA = edgeA.getDst();
3367 Integer idChildA = hrnChildA.getID();
3369 // at this point we know an edge in graph A exists
3370 // idA -> idChildA, does this exist in B?
3371 assert id2hrn.containsKey( idA );
3372 HeapRegionNode hrnB = id2hrn.get( idA );
3373 RefEdge edgeToMerge = null;
3375 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3376 while( heapRegionsItrB.hasNext() &&
3377 edgeToMerge == null ) {
3379 RefEdge edgeB = heapRegionsItrB.next();
3380 HeapRegionNode hrnChildB = edgeB.getDst();
3381 Integer idChildB = hrnChildB.getID();
3383 // don't use the RefEdge.equals() here because
3384 // we're talking about existence between graphs,
3385 // not intragraph equal
3386 if( idChildB.equals( idChildA ) &&
3387 edgeB.typeAndFieldEquals( edgeA ) ) {
3389 edgeToMerge = edgeB;
3393 // if the edge from A was not found in B,
3395 if( edgeToMerge == null ) {
3396 assert id2hrn.containsKey( idChildA );
3397 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3398 edgeToMerge = edgeA.copy();
3399 edgeToMerge.setSrc( hrnB );
3400 edgeToMerge.setDst( hrnChildB );
3401 addRefEdge( hrnB, hrnChildB, edgeToMerge );
3403 // otherwise, the edge already existed in both graphs
3404 // so merge their reachability sets
3406 // just replace this beta set with the union
3407 assert edgeToMerge != null;
3408 edgeToMerge.setBeta(
3409 Canonical.unionORpreds( edgeToMerge.getBeta(),
3413 edgeToMerge.setPreds(
3414 Canonical.join( edgeToMerge.getPreds(),
3422 // and then again from variable nodes
3423 sA = rg.td2vn.entrySet();
3425 while( iA.hasNext() ) {
3426 Map.Entry meA = (Map.Entry) iA.next();
3427 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3428 VariableNode vnA = (VariableNode) meA.getValue();
3430 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3431 while( heapRegionsItrA.hasNext() ) {
3432 RefEdge edgeA = heapRegionsItrA.next();
3433 HeapRegionNode hrnChildA = edgeA.getDst();
3434 Integer idChildA = hrnChildA.getID();
3436 // at this point we know an edge in graph A exists
3437 // tdA -> idChildA, does this exist in B?
3438 assert td2vn.containsKey( tdA );
3439 VariableNode vnB = td2vn.get( tdA );
3440 RefEdge edgeToMerge = null;
3442 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3443 while( heapRegionsItrB.hasNext() &&
3444 edgeToMerge == null ) {
3446 RefEdge edgeB = heapRegionsItrB.next();
3447 HeapRegionNode hrnChildB = edgeB.getDst();
3448 Integer idChildB = hrnChildB.getID();
3450 // don't use the RefEdge.equals() here because
3451 // we're talking about existence between graphs
3452 if( idChildB.equals( idChildA ) &&
3453 edgeB.typeAndFieldEquals( edgeA ) ) {
3455 edgeToMerge = edgeB;
3459 // if the edge from A was not found in B,
3461 if( edgeToMerge == null ) {
3462 assert id2hrn.containsKey( idChildA );
3463 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3464 edgeToMerge = edgeA.copy();
3465 edgeToMerge.setSrc( vnB );
3466 edgeToMerge.setDst( hrnChildB );
3467 addRefEdge( vnB, hrnChildB, edgeToMerge );
3469 // otherwise, the edge already existed in both graphs
3470 // so merge their reachability sets
3472 // just replace this beta set with the union
3473 edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3477 edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3486 protected void mergeAllocSites( ReachGraph rg ) {
3487 allocSites.addAll( rg.allocSites );
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 ) {
3507 if( !areHeapRegionNodesEqual( rg ) ) {
3511 if( !areVariableNodesEqual( rg ) ) {
3515 if( !areRefEdgesEqual( rg ) ) {
3519 // if everything is equal up to this point,
3520 // assert that allocSites is also equal--
3521 // this data is redundant but kept for efficiency
3522 assert allocSites.equals( rg.allocSites );
3528 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3530 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3534 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3541 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3543 Set sA = rgA.id2hrn.entrySet();
3544 Iterator iA = sA.iterator();
3545 while( iA.hasNext() ) {
3546 Map.Entry meA = (Map.Entry) iA.next();
3547 Integer idA = (Integer) meA.getKey();
3548 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3550 if( !rgB.id2hrn.containsKey( idA ) ) {
3554 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3555 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3563 protected boolean areVariableNodesEqual( ReachGraph rg ) {
3565 if( !areallVNinAalsoinBandequal( this, rg ) ) {
3569 if( !areallVNinAalsoinBandequal( rg, this ) ) {
3576 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3578 Set sA = rgA.td2vn.entrySet();
3579 Iterator iA = sA.iterator();
3580 while( iA.hasNext() ) {
3581 Map.Entry meA = (Map.Entry) iA.next();
3582 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3584 if( !rgB.td2vn.containsKey( tdA ) ) {
3593 protected boolean areRefEdgesEqual( ReachGraph rg ) {
3594 if( !areallREinAandBequal( this, rg ) ) {
3601 static protected boolean areallREinAandBequal( ReachGraph rgA,
3604 // check all the heap region->heap region edges
3605 Set sA = rgA.id2hrn.entrySet();
3606 Iterator iA = sA.iterator();
3607 while( iA.hasNext() ) {
3608 Map.Entry meA = (Map.Entry) iA.next();
3609 Integer idA = (Integer) meA.getKey();
3610 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3612 // we should have already checked that the same
3613 // heap regions exist in both graphs
3614 assert rgB.id2hrn.containsKey( idA );
3616 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3620 // then check every edge in B for presence in A, starting
3621 // from the same parent HeapRegionNode
3622 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3624 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3629 // then check all the variable->heap region edges
3630 sA = rgA.td2vn.entrySet();
3632 while( iA.hasNext() ) {
3633 Map.Entry meA = (Map.Entry) iA.next();
3634 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3635 VariableNode vnA = (VariableNode) meA.getValue();
3637 // we should have already checked that the same
3638 // label nodes exist in both graphs
3639 assert rgB.td2vn.containsKey( tdA );
3641 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3645 // then check every edge in B for presence in A, starting
3646 // from the same parent VariableNode
3647 VariableNode vnB = rgB.td2vn.get( tdA );
3649 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3658 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3662 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3663 while( itrA.hasNext() ) {
3664 RefEdge edgeA = itrA.next();
3665 HeapRegionNode hrnChildA = edgeA.getDst();
3666 Integer idChildA = hrnChildA.getID();
3668 assert rgB.id2hrn.containsKey( idChildA );
3670 // at this point we know an edge in graph A exists
3671 // rnA -> idChildA, does this exact edge exist in B?
3672 boolean edgeFound = false;
3674 RefSrcNode rnB = null;
3675 if( rnA instanceof HeapRegionNode ) {
3676 HeapRegionNode hrnA = (HeapRegionNode) rnA;
3677 rnB = rgB.id2hrn.get( hrnA.getID() );
3679 VariableNode vnA = (VariableNode) rnA;
3680 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3683 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3684 while( itrB.hasNext() ) {
3685 RefEdge edgeB = itrB.next();
3686 HeapRegionNode hrnChildB = edgeB.getDst();
3687 Integer idChildB = hrnChildB.getID();
3689 if( idChildA.equals( idChildB ) &&
3690 edgeA.typeAndFieldEquals( edgeB ) ) {
3692 // there is an edge in the right place with the right field,
3693 // but do they have the same attributes?
3694 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3695 edgeA.equalsPreds( edgeB )
3712 // this analysis no longer has the "match anything"
3713 // type which was represented by null
3714 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3715 TypeDescriptor td2 ) {
3719 if( td1.isNull() ) {
3722 if( td2.isNull() ) {
3725 return typeUtil.mostSpecific( td1, td2 );
3728 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3730 TypeDescriptor td3 ) {
3732 return mostSpecificType( td1,
3733 mostSpecificType( td2, td3 )
3737 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3740 TypeDescriptor td4 ) {
3742 return mostSpecificType( mostSpecificType( td1, td2 ),
3743 mostSpecificType( td3, td4 )
3747 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3748 TypeDescriptor possibleChild ) {
3749 assert possibleSuper != null;
3750 assert possibleChild != null;
3752 if( possibleSuper.isNull() ||
3753 possibleChild.isNull() ) {
3757 return typeUtil.isSuperorType( possibleSuper, possibleChild );
3761 protected boolean hasMatchingField( HeapRegionNode src,
3764 TypeDescriptor tdSrc = src.getType();
3765 assert tdSrc != null;
3767 if( tdSrc.isArray() ) {
3768 TypeDescriptor td = edge.getType();
3771 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3772 assert tdSrcDeref != null;
3774 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3778 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3781 // if it's not a class, it doesn't have any fields to match
3782 if( !tdSrc.isClass() ) {
3786 ClassDescriptor cd = tdSrc.getClassDesc();
3787 while( cd != null ) {
3788 Iterator fieldItr = cd.getFields();
3790 while( fieldItr.hasNext() ) {
3791 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3793 if( fd.getType().equals( edge.getType() ) &&
3794 fd.getSymbol().equals( edge.getField() ) ) {
3799 cd = cd.getSuperDesc();
3802 // otherwise it is a class with fields
3803 // but we didn't find a match
3807 protected boolean hasMatchingType( RefEdge edge,
3808 HeapRegionNode dst ) {
3810 // if the region has no type, matches everything
3811 TypeDescriptor tdDst = dst.getType();
3812 assert tdDst != null;
3814 // if the type is not a class or an array, don't
3815 // match because primitives are copied, no aliases
3816 ClassDescriptor cdDst = tdDst.getClassDesc();
3817 if( cdDst == null && !tdDst.isArray() ) {
3821 // if the edge type is null, it matches everything
3822 TypeDescriptor tdEdge = edge.getType();
3823 assert tdEdge != null;
3825 return typeUtil.isSuperorType( tdEdge, tdDst );
3830 public void writeGraph( String graphName,
3831 boolean writeLabels,
3832 boolean labelSelect,
3833 boolean pruneGarbage,
3834 boolean hideSubsetReachability,
3835 boolean hideEdgeTaints
3836 ) throws java.io.IOException {
3837 writeGraph( graphName,
3841 hideSubsetReachability,
3846 public void writeGraph( String graphName,
3847 boolean writeLabels,
3848 boolean labelSelect,
3849 boolean pruneGarbage,
3850 boolean hideSubsetReachability,
3851 boolean hideEdgeTaints,
3852 Set<Integer> callerNodeIDsCopiedToCallee
3853 ) throws java.io.IOException {
3855 // remove all non-word characters from the graph name so
3856 // the filename and identifier in dot don't cause errors
3857 graphName = graphName.replaceAll( "[\\W]", "" );
3860 new BufferedWriter( new FileWriter( graphName+".dot" ) );
3862 bw.write( "digraph "+graphName+" {\n" );
3865 // this is an optional step to form the callee-reachable
3866 // "cut-out" into a DOT cluster for visualization
3867 if( callerNodeIDsCopiedToCallee != null ) {
3869 bw.write( " subgraph cluster0 {\n" );
3870 bw.write( " color=blue;\n" );
3872 Iterator i = id2hrn.entrySet().iterator();
3873 while( i.hasNext() ) {
3874 Map.Entry me = (Map.Entry) i.next();
3875 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3877 if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3878 bw.write( " "+hrn.toString()+
3879 hrn.toStringDOT( hideSubsetReachability )+
3889 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3891 // then visit every heap region node
3892 Iterator i = id2hrn.entrySet().iterator();
3893 while( i.hasNext() ) {
3894 Map.Entry me = (Map.Entry) i.next();
3895 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3897 // only visit nodes worth writing out--for instance
3898 // not every node at an allocation is referenced
3899 // (think of it as garbage-collected), etc.
3900 if( !pruneGarbage ||
3901 hrn.isOutOfContext()
3904 if( !visited.contains( hrn ) ) {
3905 traverseHeapRegionNodes( hrn,
3909 hideSubsetReachability,
3911 callerNodeIDsCopiedToCallee );
3916 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
3919 // then visit every label node, useful for debugging
3921 i = td2vn.entrySet().iterator();
3922 while( i.hasNext() ) {
3923 Map.Entry me = (Map.Entry) i.next();
3924 VariableNode vn = (VariableNode) me.getValue();
3927 String labelStr = vn.getTempDescriptorString();
3928 if( labelStr.startsWith( "___temp" ) ||
3929 labelStr.startsWith( "___dst" ) ||
3930 labelStr.startsWith( "___srctmp" ) ||
3931 labelStr.startsWith( "___neverused" )
3937 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3938 while( heapRegionsItr.hasNext() ) {
3939 RefEdge edge = heapRegionsItr.next();
3940 HeapRegionNode hrn = edge.getDst();
3942 if( !visited.contains( hrn ) ) {
3943 traverseHeapRegionNodes( hrn,
3947 hideSubsetReachability,
3949 callerNodeIDsCopiedToCallee );
3952 bw.write( " "+vn.toString()+
3953 " -> "+hrn.toString()+
3954 edge.toStringDOT( hideSubsetReachability, "" )+
3964 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
3967 Set<HeapRegionNode> visited,
3968 boolean hideSubsetReachability,
3969 boolean hideEdgeTaints,
3970 Set<Integer> callerNodeIDsCopiedToCallee
3971 ) throws java.io.IOException {
3973 if( visited.contains( hrn ) ) {
3978 // if we're drawing the callee-view subgraph, only
3979 // write out the node info if it hasn't already been
3981 if( callerNodeIDsCopiedToCallee == null ||
3982 !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3984 bw.write( " "+hrn.toString()+
3985 hrn.toStringDOT( hideSubsetReachability )+
3989 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3990 while( childRegionsItr.hasNext() ) {
3991 RefEdge edge = childRegionsItr.next();
3992 HeapRegionNode hrnChild = edge.getDst();
3994 if( callerNodeIDsCopiedToCallee != null &&
3995 (edge.getSrc() instanceof HeapRegionNode) ) {
3996 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3997 if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
3998 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4000 bw.write( " "+hrn.toString()+
4001 " -> "+hrnChild.toString()+
4002 edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
4004 } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
4005 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4007 bw.write( " "+hrn.toString()+
4008 " -> "+hrnChild.toString()+
4009 edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
4012 bw.write( " "+hrn.toString()+
4013 " -> "+hrnChild.toString()+
4014 edge.toStringDOT( hideSubsetReachability, "" )+
4018 bw.write( " "+hrn.toString()+
4019 " -> "+hrnChild.toString()+
4020 edge.toStringDOT( hideSubsetReachability, "" )+
4024 traverseHeapRegionNodes( hrnChild,
4028 hideSubsetReachability,
4030 callerNodeIDsCopiedToCallee );
4034 public Set<HeapRegionNode> findCommonReachableNodes(HeapRegionNode hrn1,
4035 HeapRegionNode hrn2) {
4037 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
4038 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
4040 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
4041 todoNodes1.add(hrn1);
4043 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
4044 todoNodes2.add(hrn2);
4046 // follow links until all reachable nodes have been found
4047 while (!todoNodes1.isEmpty()) {
4048 HeapRegionNode hrn = todoNodes1.iterator().next();
4049 todoNodes1.remove(hrn);
4050 reachableNodes1.add(hrn);
4052 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
4053 while (edgeItr.hasNext()) {
4054 RefEdge edge = edgeItr.next();
4056 if (!reachableNodes1.contains(edge.getDst())) {
4057 todoNodes1.add(edge.getDst());
4062 while (!todoNodes2.isEmpty()) {
4063 HeapRegionNode hrn = todoNodes2.iterator().next();
4064 todoNodes2.remove(hrn);
4065 reachableNodes2.add(hrn);
4067 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
4068 while (edgeItr.hasNext()) {
4069 RefEdge edge = edgeItr.next();
4071 if (!reachableNodes2.contains(edge.getDst())) {
4072 todoNodes2.add(edge.getDst());
4077 Set<HeapRegionNode> intersection =
4078 new HashSet<HeapRegionNode>( reachableNodes1 );
4080 intersection.retainAll( reachableNodes2 );
4082 return intersection;
4085 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4086 HeapRegionNode hrn2) {
4087 assert hrn1 != null;
4088 assert hrn2 != null;
4090 // then get the various tokens for these heap regions
4091 ReachTuple h1 = ReachTuple.factory(hrn1.getID(),
4092 !hrn1.isSingleObject(), ReachTuple.ARITY_ONE, false);
4095 if(hrn1.isSingleObject){
4096 arity=ReachTuple.ARITY_ONE;
4098 arity=ReachTuple.ARITY_ZEROORMORE;
4100 ReachTuple h1star = ReachTuple.factory(hrn1.getID(), !hrn1
4101 .isSingleObject(), arity, false);
4103 ReachTuple h2 = ReachTuple.factory(hrn2.getID(),
4104 !hrn2.isSingleObject(), ReachTuple.ARITY_ONE, false);
4106 if(hrn2.isSingleObject){
4107 arity=ReachTuple.ARITY_ONE;
4109 arity=ReachTuple.ARITY_ZEROORMORE;
4112 ReachTuple h2star = ReachTuple.factory(hrn2.getID(), !hrn2
4113 .isSingleObject(), arity, false);
4115 // then get the merged beta of all out-going edges from these heap
4118 ReachSet beta1 = ReachSet.factory();
4119 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4120 while (itrEdge.hasNext()) {
4121 RefEdge edge = itrEdge.next();
4122 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4125 ReachSet beta2 = ReachSet.factory();
4126 itrEdge = hrn2.iteratorToReferencees();
4127 while (itrEdge.hasNext()) {
4128 RefEdge edge = itrEdge.next();
4129 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4132 boolean aliasDetected = false;
4134 // only do this one if they are different tokens
4135 if (h1 != h2 && beta1.containsStateWithBoth(h1, h2)) {
4136 aliasDetected = true;
4138 // if (beta1.containsStateWithBoth(h1plus, h2)) {
4139 // aliasDetected = true;
4141 if (beta1.containsStateWithBoth(h1star, h2)) {
4142 aliasDetected = true;
4144 // if (beta1.containsStateWithBoth(h1, h2plus)) {
4145 // aliasDetected = true;
4147 // if (beta1.containsStateWithBoth(h1plus, h2plus)) {
4148 // aliasDetected = true;
4150 // if (beta1.containsStateWithBoth(h1star, h2plus)) {
4151 // aliasDetected = true;
4153 if (beta1.containsStateWithBoth(h1, h2star)) {
4154 aliasDetected = true;
4156 // if (beta1.containsStateWithBoth(h1plus, h2star)) {
4157 // aliasDetected = true;
4159 if (beta1.containsStateWithBoth(h1star, h2star)) {
4160 aliasDetected = true;
4163 if (h1 != h2 && beta2.containsStateWithBoth(h1, h2)) {
4164 aliasDetected = true;
4166 // if (beta2.containsStateWithBoth(h1plus, h2)) {
4167 // aliasDetected = true;
4169 if (beta2.containsStateWithBoth(h1star, h2)) {
4170 aliasDetected = true;
4172 // if (beta2.containsStateWithBoth(h1, h2plus)) {
4173 // aliasDetected = true;
4175 // if (beta2.containsStateWithBoth(h1plus, h2plus)) {
4176 // aliasDetected = true;
4178 // if (beta2.containsStateWithBoth(h1star, h2plus)) {
4179 // aliasDetected = true;
4181 if (beta2.containsStateWithBoth(h1, h2star)) {
4182 aliasDetected = true;
4184 // if (beta2.containsStateWithBoth(h1plus, h2star)) {
4185 // aliasDetected = true;
4187 if (beta2.containsStateWithBoth(h1star, h2star)) {
4188 aliasDetected = true;
4191 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4192 if (aliasDetected) {
4193 common = findCommonReachableNodes(hrn1, hrn2);
4194 if (!(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP)) {
4195 assert !common.isEmpty();
4202 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4203 Integer paramIndex1, Integer paramIndex2) {
4205 // get parameter's heap regions
4206 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4207 VariableNode argVar1 = getVariableNodeFromTemp(paramTemp1);
4208 RefEdge argEdge1 = argVar1.iteratorToReferencees().next();
4209 HeapRegionNode hrnParam1 = argEdge1.getDst();
4211 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4212 VariableNode argVar2 = getVariableNodeFromTemp(paramTemp2);
4213 RefEdge argEdge2 = argVar2.iteratorToReferencees().next();
4214 HeapRegionNode hrnParam2 = argEdge2.getDst();
4216 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4217 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4222 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4223 Integer paramIndex, AllocSite as) {
4225 // get parameter's heap regions
4226 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4227 VariableNode argVar = getVariableNodeFromTemp(paramTemp);
4228 RefEdge argEdge = argVar.iteratorToReferencees().next();
4229 HeapRegionNode hrnParam = argEdge.getDst();
4232 HeapRegionNode hrnSummary=null;
4233 if(id2hrn.containsKey(as.getSummary())){
4234 // if summary node doesn't exist, ignore this case
4235 hrnSummary = id2hrn.get(as.getSummary());
4236 assert hrnSummary != null;
4239 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4240 if(hrnSummary!=null){
4241 common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4244 // check for other nodes
4245 for (int i = 0; i < as.getAllocationDepth(); ++i) {
4247 assert id2hrn.containsKey(as.getIthOldest(i));
4248 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4249 assert hrnIthOldest != null;
4251 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4258 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4261 // get summary node 1's alpha
4262 Integer idSum1 = as1.getSummary();
4263 HeapRegionNode hrnSum1=null;
4264 if(id2hrn.containsKey(idSum1)){
4265 hrnSum1 = id2hrn.get(idSum1);
4268 // get summary node 2's alpha
4269 Integer idSum2 = as2.getSummary();
4270 HeapRegionNode hrnSum2=null;
4271 if(id2hrn.containsKey(idSum2)){
4272 hrnSum2 = id2hrn.get(idSum2);
4275 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4276 if(hrnSum1!=null && hrnSum2!=null){
4277 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4280 // check sum2 against alloc1 nodes
4282 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4283 Integer idI1 = as1.getIthOldest(i);
4284 assert id2hrn.containsKey(idI1);
4285 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4286 assert hrnI1 != null;
4287 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4291 // check sum1 against alloc2 nodes
4292 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4293 Integer idI2 = as2.getIthOldest(i);
4294 assert id2hrn.containsKey(idI2);
4295 HeapRegionNode hrnI2 = id2hrn.get(idI2);
4296 assert hrnI2 != null;
4299 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4302 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4303 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4304 Integer idI1 = as1.getIthOldest(j);
4306 // if these are the same site, don't look for the same token, no
4308 // different tokens of the same site could alias together though
4309 if (idI1.equals(idI2)) {
4313 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4315 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));