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 = Canonical.makePredsTrue(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;
86 // the reason for this method is to have the option
87 // of creating new heap regions with specific IDs, or
88 // duplicating heap regions with specific IDs (especially
89 // in the merge() operation) or to create new heap
90 // regions with a new unique ID
91 protected HeapRegionNode
92 createNewHeapRegionNode( Integer id,
93 boolean isSingleObject,
95 boolean isOutOfContext,
104 TypeDescriptor typeToUse = null;
105 if( allocSite != null ) {
106 typeToUse = allocSite.getType();
107 allocSites.add( allocSite );
112 boolean markForAnalysis = false;
113 if( allocSite != null && allocSite.isFlagged() ) {
114 markForAnalysis = true;
117 if( allocSite == null ) {
118 assert !markForAnalysis;
120 } else if( markForAnalysis != allocSite.isFlagged() ) {
126 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
129 if( inherent == null ) {
130 if( markForAnalysis ) {
132 Canonical.makePredsTrue(
135 ReachTuple.factory( id,
137 ReachTuple.ARITY_ONE,
138 false // out-of-context
144 inherent = rsetWithEmptyState;
148 if( alpha == null ) {
152 assert preds != null;
154 HeapRegionNode hrn = new HeapRegionNode( id,
165 id2hrn.put( id, hrn );
171 ////////////////////////////////////////////////
173 // Low-level referencee and referencer methods
175 // These methods provide the lowest level for
176 // creating references between reachability nodes
177 // and handling the details of maintaining both
178 // list of referencers and referencees.
180 ////////////////////////////////////////////////
181 protected void addRefEdge( RefSrcNode referencer,
182 HeapRegionNode referencee,
184 assert referencer != null;
185 assert referencee != null;
187 assert edge.getSrc() == referencer;
188 assert edge.getDst() == referencee;
189 assert belongsToThis( referencer );
190 assert belongsToThis( referencee );
192 // edges are getting added twice to graphs now, the
193 // kind that should have abstract facts merged--use
194 // this check to prevent that
195 assert referencer.getReferenceTo( referencee,
200 referencer.addReferencee( edge );
201 referencee.addReferencer( edge );
204 protected void removeRefEdge( RefEdge e ) {
205 removeRefEdge( e.getSrc(),
211 protected void removeRefEdge( RefSrcNode referencer,
212 HeapRegionNode referencee,
215 assert referencer != null;
216 assert referencee != null;
218 RefEdge edge = referencer.getReferenceTo( referencee,
222 assert edge == referencee.getReferenceFrom( referencer,
226 referencer.removeReferencee( edge );
227 referencee.removeReferencer( edge );
230 protected void clearRefEdgesFrom( RefSrcNode referencer,
233 boolean removeAll ) {
234 assert referencer != null;
236 // get a copy of the set to iterate over, otherwise
237 // we will be trying to take apart the set as we
238 // are iterating over it, which won't work
239 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
240 while( i.hasNext() ) {
241 RefEdge edge = i.next();
244 (edge.typeEquals( type ) && edge.fieldEquals( field ))
247 HeapRegionNode referencee = edge.getDst();
249 removeRefEdge( referencer,
257 protected void clearRefEdgesTo( HeapRegionNode referencee,
260 boolean removeAll ) {
261 assert referencee != null;
263 // get a copy of the set to iterate over, otherwise
264 // we will be trying to take apart the set as we
265 // are iterating over it, which won't work
266 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
267 while( i.hasNext() ) {
268 RefEdge edge = i.next();
271 (edge.typeEquals( type ) && edge.fieldEquals( field ))
274 RefSrcNode referencer = edge.getSrc();
276 removeRefEdge( referencer,
284 protected void clearNonVarRefEdgesTo( HeapRegionNode referencee ) {
285 assert referencee != null;
287 // get a copy of the set to iterate over, otherwise
288 // we will be trying to take apart the set as we
289 // are iterating over it, which won't work
290 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
291 while( i.hasNext() ) {
292 RefEdge edge = i.next();
293 RefSrcNode referencer = edge.getSrc();
294 if( !(referencer instanceof VariableNode) ) {
295 removeRefEdge( referencer,
303 // this is a common operation in many transfer functions: we want
304 // to add an edge, but if there is already such an edge we should
305 // merge the properties of the existing and the new edges
306 protected void addEdgeOrMergeWithExisting( RefEdge edgeNew ) {
308 RefSrcNode src = edgeNew.getSrc();
309 assert belongsToThis( src );
311 HeapRegionNode dst = edgeNew.getDst();
312 assert belongsToThis( dst );
314 // look to see if an edge with same field exists
315 // and merge with it, otherwise just add the edge
316 RefEdge edgeExisting = src.getReferenceTo( dst,
321 if( edgeExisting != null ) {
322 edgeExisting.setBeta(
323 Canonical.unionORpreds( edgeExisting.getBeta(),
327 edgeExisting.setPreds(
328 Canonical.join( edgeExisting.getPreds(),
334 addRefEdge( src, dst, edgeNew );
340 ////////////////////////////////////////////////////
342 // Assignment Operation Methods
344 // These methods are high-level operations for
345 // modeling program assignment statements using
346 // the low-level reference create/remove methods
349 ////////////////////////////////////////////////////
351 public void assignTempXEqualToTempY( TempDescriptor x,
353 assignTempXEqualToCastedTempY( x, y, null );
356 public void assignTempXEqualToCastedTempY( TempDescriptor x,
358 TypeDescriptor tdCast ) {
360 VariableNode lnX = getVariableNodeFromTemp( x );
361 VariableNode lnY = getVariableNodeFromTemp( y );
363 clearRefEdgesFrom( lnX, null, null, true );
365 // note it is possible that the types of temps in the
366 // flat node to analyze will reveal that some typed
367 // edges in the reachability graph are impossible
368 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
370 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
371 while( itrYhrn.hasNext() ) {
372 RefEdge edgeY = itrYhrn.next();
373 HeapRegionNode referencee = edgeY.getDst();
374 RefEdge edgeNew = edgeY.copy();
376 if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
377 impossibleEdges.add( edgeY );
381 edgeNew.setSrc( lnX );
383 if( tdCast == null ) {
384 edgeNew.setType( mostSpecificType( y.getType(),
390 edgeNew.setType( mostSpecificType( y.getType(),
392 referencee.getType(),
398 edgeNew.setField( null );
400 addRefEdge( lnX, referencee, edgeNew );
403 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
404 while( itrImp.hasNext() ) {
405 RefEdge edgeImp = itrImp.next();
406 removeRefEdge( edgeImp );
411 public void assignTempXEqualToTempYFieldF( TempDescriptor x,
413 FieldDescriptor f ) {
414 VariableNode lnX = getVariableNodeFromTemp( x );
415 VariableNode lnY = getVariableNodeFromTemp( y );
417 clearRefEdgesFrom( lnX, null, null, true );
419 // note it is possible that the types of temps in the
420 // flat node to analyze will reveal that some typed
421 // edges in the reachability graph are impossible
422 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
424 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
425 while( itrYhrn.hasNext() ) {
426 RefEdge edgeY = itrYhrn.next();
427 HeapRegionNode hrnY = edgeY.getDst();
428 ReachSet betaY = edgeY.getBeta();
430 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
431 while( itrHrnFhrn.hasNext() ) {
432 RefEdge edgeHrn = itrHrnFhrn.next();
433 HeapRegionNode hrnHrn = edgeHrn.getDst();
434 ReachSet betaHrn = edgeHrn.getBeta();
436 // prune edges that are not a matching field
437 if( edgeHrn.getType() != null &&
438 !edgeHrn.getField().equals( f.getSymbol() )
443 // check for impossible edges
444 if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
445 impossibleEdges.add( edgeHrn );
449 TypeDescriptor tdNewEdge =
450 mostSpecificType( edgeHrn.getType(),
454 RefEdge edgeNew = new RefEdge( lnX,
458 Canonical.intersection( betaY, betaHrn ),
462 addEdgeOrMergeWithExisting( edgeNew );
466 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
467 while( itrImp.hasNext() ) {
468 RefEdge edgeImp = itrImp.next();
469 removeRefEdge( edgeImp );
472 // anytime you might remove edges between heap regions
473 // you must global sweep to clean up broken reachability
474 if( !impossibleEdges.isEmpty() ) {
475 if( !DISABLE_GLOBAL_SWEEP ) {
482 public void assignTempXFieldFEqualToTempY( TempDescriptor x,
486 VariableNode lnX = getVariableNodeFromTemp( x );
487 VariableNode lnY = getVariableNodeFromTemp( y );
489 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
490 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
492 // note it is possible that the types of temps in the
493 // flat node to analyze will reveal that some typed
494 // edges in the reachability graph are impossible
495 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
497 // first look for possible strong updates and remove those edges
498 boolean strongUpdate = false;
500 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
501 while( itrXhrn.hasNext() ) {
502 RefEdge edgeX = itrXhrn.next();
503 HeapRegionNode hrnX = edgeX.getDst();
505 // we can do a strong update here if one of two cases holds
507 f != DisjointAnalysis.getArrayField( f.getType() ) &&
508 ( (hrnX.getNumReferencers() == 1) || // case 1
509 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
512 if( !DISABLE_STRONG_UPDATES ) {
514 clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
519 // then do all token propagation
520 itrXhrn = lnX.iteratorToReferencees();
521 while( itrXhrn.hasNext() ) {
522 RefEdge edgeX = itrXhrn.next();
523 HeapRegionNode hrnX = edgeX.getDst();
524 ReachSet betaX = edgeX.getBeta();
525 ReachSet R = Canonical.intersection( hrnX.getAlpha(),
529 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
530 while( itrYhrn.hasNext() ) {
531 RefEdge edgeY = itrYhrn.next();
532 HeapRegionNode hrnY = edgeY.getDst();
533 ReachSet O = edgeY.getBeta();
535 // check for impossible edges
536 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
537 impossibleEdges.add( edgeY );
541 // propagate tokens over nodes starting from hrnSrc, and it will
542 // take care of propagating back up edges from any touched nodes
543 ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
544 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
546 // then propagate back just up the edges from hrn
547 ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
548 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
550 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
551 new Hashtable<RefEdge, ChangeSet>();
553 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
554 while( referItr.hasNext() ) {
555 RefEdge edgeUpstream = referItr.next();
556 todoEdges.add( edgeUpstream );
557 edgePlannedChanges.put( edgeUpstream, Cx );
560 propagateTokensOverEdges( todoEdges,
567 // apply the updates to reachability
568 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
569 while( nodeItr.hasNext() ) {
570 nodeItr.next().applyAlphaNew();
573 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
574 while( edgeItr.hasNext() ) {
575 edgeItr.next().applyBetaNew();
579 // then go back through and add the new edges
580 itrXhrn = lnX.iteratorToReferencees();
581 while( itrXhrn.hasNext() ) {
582 RefEdge edgeX = itrXhrn.next();
583 HeapRegionNode hrnX = edgeX.getDst();
585 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
586 while( itrYhrn.hasNext() ) {
587 RefEdge edgeY = itrYhrn.next();
588 HeapRegionNode hrnY = edgeY.getDst();
590 // skip impossible edges here, we already marked them
591 // when computing reachability propagations above
592 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
596 // prepare the new reference edge hrnX.f -> hrnY
597 TypeDescriptor tdNewEdge =
598 mostSpecificType( y.getType(),
608 Canonical.makePredsTrue(
609 Canonical.pruneBy( edgeY.getBeta(),
616 addEdgeOrMergeWithExisting( edgeNew );
620 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
621 while( itrImp.hasNext() ) {
622 RefEdge edgeImp = itrImp.next();
623 removeRefEdge( edgeImp );
626 // if there was a strong update, make sure to improve
627 // reachability with a global sweep
628 if( strongUpdate || !impossibleEdges.isEmpty() ) {
629 if( !DISABLE_GLOBAL_SWEEP ) {
636 public void assignReturnEqualToTemp( TempDescriptor x ) {
638 VariableNode lnR = getVariableNodeFromTemp( tdReturn );
639 VariableNode lnX = getVariableNodeFromTemp( x );
641 clearRefEdgesFrom( lnR, null, null, true );
643 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
644 while( itrXhrn.hasNext() ) {
645 RefEdge edgeX = itrXhrn.next();
646 HeapRegionNode referencee = edgeX.getDst();
647 RefEdge edgeNew = edgeX.copy();
648 edgeNew.setSrc( lnR );
650 addRefEdge( lnR, referencee, edgeNew );
655 public void assignTempEqualToNewAlloc( TempDescriptor x,
662 // after the age operation the newest (or zero-ith oldest)
663 // node associated with the allocation site should have
664 // no references to it as if it were a newly allocated
666 Integer idNewest = as.getIthOldest( 0 );
667 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
668 assert hrnNewest != null;
670 VariableNode lnX = getVariableNodeFromTemp( x );
671 clearRefEdgesFrom( lnX, null, null, true );
673 // make a new reference to allocated node
674 TypeDescriptor type = as.getType();
677 new RefEdge( lnX, // source
681 hrnNewest.getAlpha(), // beta
682 predsTrue // predicates
685 addRefEdge( lnX, hrnNewest, edgeNew );
689 // use the allocation site (unique to entire analysis) to
690 // locate the heap region nodes in this reachability graph
691 // that should be aged. The process models the allocation
692 // of new objects and collects all the oldest allocations
693 // in a summary node to allow for a finite analysis
695 // There is an additional property of this method. After
696 // running it on a particular reachability graph (many graphs
697 // may have heap regions related to the same allocation site)
698 // the heap region node objects in this reachability graph will be
699 // allocated. Therefore, after aging a graph for an allocation
700 // site, attempts to retrieve the heap region nodes using the
701 // integer id's contained in the allocation site should always
702 // return non-null heap regions.
703 public void age( AllocSite as ) {
705 // keep track of allocation sites that are represented
706 // in this graph for efficiency with other operations
707 allocSites.add( as );
709 // if there is a k-th oldest node, it merges into
711 Integer idK = as.getOldest();
712 if( id2hrn.containsKey( idK ) ) {
713 HeapRegionNode hrnK = id2hrn.get( idK );
715 // retrieve the summary node, or make it
717 HeapRegionNode hrnSummary = getSummaryNode( as, false );
719 mergeIntoSummary( hrnK, hrnSummary );
722 // move down the line of heap region nodes
723 // clobbering the ith and transferring all references
724 // to and from i-1 to node i.
725 for( int i = allocationDepth - 1; i > 0; --i ) {
727 // only do the transfer if the i-1 node exists
728 Integer idImin1th = as.getIthOldest( i - 1 );
729 if( id2hrn.containsKey( idImin1th ) ) {
730 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
731 if( hrnImin1.isWiped() ) {
732 // there is no info on this node, just skip
736 // either retrieve or make target of transfer
737 HeapRegionNode hrnI = getIthNode( as, i, false );
739 transferOnto( hrnImin1, hrnI );
744 // as stated above, the newest node should have had its
745 // references moved over to the second oldest, so we wipe newest
746 // in preparation for being the new object to assign something to
747 HeapRegionNode hrn0 = getIthNode( as, 0, false );
748 wipeOut( hrn0, true );
750 // now tokens in reachability sets need to "age" also
751 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
752 while( itrAllVariableNodes.hasNext() ) {
753 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
754 VariableNode ln = (VariableNode) me.getValue();
756 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
757 while( itrEdges.hasNext() ) {
758 ageTuplesFrom( as, itrEdges.next() );
762 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
763 while( itrAllHRNodes.hasNext() ) {
764 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
765 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
767 ageTuplesFrom( as, hrnToAge );
769 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
770 while( itrEdges.hasNext() ) {
771 ageTuplesFrom( as, itrEdges.next() );
776 // after tokens have been aged, reset newest node's reachability
777 // and a brand new node has a "true" predicate
778 hrn0.setAlpha( hrn0.getInherent() );
779 hrn0.setPreds( predsTrue );
783 // either retrieve or create the needed heap region node
784 protected HeapRegionNode getSummaryNode( AllocSite as,
789 idSummary = as.getSummaryShadow();
791 idSummary = as.getSummary();
794 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
796 if( hrnSummary == null ) {
798 String strDesc = as.toStringForDOT()+"\\nsummary";
801 createNewHeapRegionNode( idSummary, // id or null to generate a new one
802 false, // single object?
804 false, // out-of-context?
805 as.getType(), // type
806 as, // allocation site
807 null, // inherent reach
808 null, // current reach
809 predsEmpty, // predicates
810 strDesc // description
817 // either retrieve or create the needed heap region node
818 protected HeapRegionNode getIthNode( AllocSite as,
824 idIth = as.getIthOldestShadow( i );
826 idIth = as.getIthOldest( i );
829 HeapRegionNode hrnIth = id2hrn.get( idIth );
831 if( hrnIth == null ) {
833 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
835 hrnIth = createNewHeapRegionNode( idIth, // id or null to generate a new one
836 true, // single object?
838 false, // out-of-context?
839 as.getType(), // type
840 as, // allocation site
841 null, // inherent reach
842 null, // current reach
843 predsEmpty, // predicates
844 strDesc // description
852 protected void mergeIntoSummary( HeapRegionNode hrn,
853 HeapRegionNode hrnSummary ) {
854 assert hrnSummary.isNewSummary();
856 // assert that these nodes belong to THIS graph
857 assert belongsToThis( hrn );
858 assert belongsToThis( hrnSummary );
860 assert hrn != hrnSummary;
862 // transfer references _from_ hrn over to hrnSummary
863 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
864 while( itrReferencee.hasNext() ) {
865 RefEdge edge = itrReferencee.next();
866 RefEdge edgeMerged = edge.copy();
867 edgeMerged.setSrc( hrnSummary );
869 HeapRegionNode hrnReferencee = edge.getDst();
870 RefEdge edgeSummary =
871 hrnSummary.getReferenceTo( hrnReferencee,
876 if( edgeSummary == null ) {
877 // the merge is trivial, nothing to be done
878 addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
881 // otherwise an edge from the referencer to hrnSummary exists already
882 // and the edge referencer->hrn should be merged with it
884 Canonical.unionORpreds( edgeMerged.getBeta(),
885 edgeSummary.getBeta()
888 edgeSummary.setPreds(
889 Canonical.join( edgeMerged.getPreds(),
890 edgeSummary.getPreds()
896 // next transfer references _to_ hrn over to hrnSummary
897 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
898 while( itrReferencer.hasNext() ) {
899 RefEdge edge = itrReferencer.next();
900 RefEdge edgeMerged = edge.copy();
901 edgeMerged.setDst( hrnSummary );
903 RefSrcNode onReferencer = edge.getSrc();
904 RefEdge edgeSummary =
905 onReferencer.getReferenceTo( hrnSummary,
910 if( edgeSummary == null ) {
911 // the merge is trivial, nothing to be done
912 addRefEdge( onReferencer, hrnSummary, edgeMerged );
915 // otherwise an edge from the referencer to alpha_S exists already
916 // and the edge referencer->alpha_K should be merged with it
918 Canonical.unionORpreds( edgeMerged.getBeta(),
919 edgeSummary.getBeta()
922 edgeSummary.setPreds(
923 Canonical.join( edgeMerged.getPreds(),
924 edgeSummary.getPreds()
930 // then merge hrn reachability into hrnSummary
932 Canonical.unionORpreds( hrnSummary.getAlpha(),
938 Canonical.join( hrnSummary.getPreds(),
943 // and afterward, this node is gone
944 wipeOut( hrn, true );
948 protected void transferOnto( HeapRegionNode hrnA,
949 HeapRegionNode hrnB ) {
951 assert belongsToThis( hrnA );
952 assert belongsToThis( hrnB );
955 // clear references in and out of node b?
956 assert hrnB.isWiped();
958 // copy each: (edge in and out of A) to B
959 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
960 while( itrReferencee.hasNext() ) {
961 RefEdge edge = itrReferencee.next();
962 HeapRegionNode hrnReferencee = edge.getDst();
963 RefEdge edgeNew = edge.copy();
964 edgeNew.setSrc( hrnB );
965 edgeNew.setDst( hrnReferencee );
967 addRefEdge( hrnB, hrnReferencee, edgeNew );
970 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
971 while( itrReferencer.hasNext() ) {
972 RefEdge edge = itrReferencer.next();
973 RefSrcNode rsnReferencer = edge.getSrc();
974 RefEdge edgeNew = edge.copy();
975 edgeNew.setSrc( rsnReferencer );
976 edgeNew.setDst( hrnB );
978 addRefEdge( rsnReferencer, hrnB, edgeNew );
981 // replace hrnB reachability and preds with hrnA's
982 hrnB.setAlpha( hrnA.getAlpha() );
983 hrnB.setPreds( hrnA.getPreds() );
985 // after transfer, wipe out source
986 wipeOut( hrnA, true );
990 // the purpose of this method is to conceptually "wipe out"
991 // a heap region from the graph--purposefully not called REMOVE
992 // because the node is still hanging around in the graph, just
993 // not mechanically connected or have any reach or predicate
994 // information on it anymore--lots of ops can use this
995 protected void wipeOut( HeapRegionNode hrn,
996 boolean wipeVariableReferences ) {
998 assert belongsToThis( hrn );
1000 clearRefEdgesFrom( hrn, null, null, true );
1002 if( wipeVariableReferences ) {
1003 clearRefEdgesTo( hrn, null, null, true );
1005 clearNonVarRefEdgesTo( hrn );
1008 hrn.setAlpha( rsetEmpty );
1009 hrn.setPreds( predsEmpty );
1013 protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
1015 Canonical.ageTuplesFrom( edge.getBeta(),
1021 protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
1023 Canonical.ageTuplesFrom( hrn.getAlpha(),
1031 protected void propagateTokensOverNodes( HeapRegionNode nPrime,
1033 HashSet<HeapRegionNode> nodesWithNewAlpha,
1034 HashSet<RefEdge> edgesWithNewBeta ) {
1036 HashSet<HeapRegionNode> todoNodes
1037 = new HashSet<HeapRegionNode>();
1038 todoNodes.add( nPrime );
1040 HashSet<RefEdge> todoEdges
1041 = new HashSet<RefEdge>();
1043 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1044 = new Hashtable<HeapRegionNode, ChangeSet>();
1045 nodePlannedChanges.put( nPrime, c0 );
1047 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1048 = new Hashtable<RefEdge, ChangeSet>();
1050 // first propagate change sets everywhere they can go
1051 while( !todoNodes.isEmpty() ) {
1052 HeapRegionNode n = todoNodes.iterator().next();
1053 ChangeSet C = nodePlannedChanges.get( n );
1055 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1056 while( referItr.hasNext() ) {
1057 RefEdge edge = referItr.next();
1058 todoEdges.add( edge );
1060 if( !edgePlannedChanges.containsKey( edge ) ) {
1061 edgePlannedChanges.put( edge,
1066 edgePlannedChanges.put( edge,
1067 Canonical.union( edgePlannedChanges.get( edge ),
1073 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1074 while( refeeItr.hasNext() ) {
1075 RefEdge edgeF = refeeItr.next();
1076 HeapRegionNode m = edgeF.getDst();
1078 ChangeSet changesToPass = ChangeSet.factory();
1080 Iterator<ChangeTuple> itrCprime = C.iterator();
1081 while( itrCprime.hasNext() ) {
1082 ChangeTuple c = itrCprime.next();
1083 if( edgeF.getBeta().containsIgnorePreds( c.getStateToMatch() )
1086 changesToPass = Canonical.add( changesToPass, c );
1090 if( !changesToPass.isEmpty() ) {
1091 if( !nodePlannedChanges.containsKey( m ) ) {
1092 nodePlannedChanges.put( m, ChangeSet.factory() );
1095 ChangeSet currentChanges = nodePlannedChanges.get( m );
1097 if( !changesToPass.isSubset( currentChanges ) ) {
1099 nodePlannedChanges.put( m,
1100 Canonical.union( currentChanges,
1109 todoNodes.remove( n );
1112 // then apply all of the changes for each node at once
1113 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1114 while( itrMap.hasNext() ) {
1115 Map.Entry me = (Map.Entry) itrMap.next();
1116 HeapRegionNode n = (HeapRegionNode) me.getKey();
1117 ChangeSet C = (ChangeSet) me.getValue();
1119 // this propagation step is with respect to one change,
1120 // so we capture the full change from the old alpha:
1121 ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1125 // but this propagation may be only one of many concurrent
1126 // possible changes, so keep a running union with the node's
1127 // partially updated new alpha set
1128 n.setAlphaNew( Canonical.unionORpreds( n.getAlphaNew(),
1133 nodesWithNewAlpha.add( n );
1136 propagateTokensOverEdges( todoEdges,
1143 protected void propagateTokensOverEdges( HashSet <RefEdge> todoEdges,
1144 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1145 HashSet <RefEdge> edgesWithNewBeta ) {
1147 // first propagate all change tuples everywhere they can go
1148 while( !todoEdges.isEmpty() ) {
1149 RefEdge edgeE = todoEdges.iterator().next();
1150 todoEdges.remove( edgeE );
1152 if( !edgePlannedChanges.containsKey( edgeE ) ) {
1153 edgePlannedChanges.put( edgeE,
1158 ChangeSet C = edgePlannedChanges.get( edgeE );
1160 ChangeSet changesToPass = ChangeSet.factory();
1162 Iterator<ChangeTuple> itrC = C.iterator();
1163 while( itrC.hasNext() ) {
1164 ChangeTuple c = itrC.next();
1165 if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
1168 changesToPass = Canonical.add( changesToPass, c );
1172 RefSrcNode rsn = edgeE.getSrc();
1174 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1175 HeapRegionNode n = (HeapRegionNode) rsn;
1177 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1178 while( referItr.hasNext() ) {
1179 RefEdge edgeF = referItr.next();
1181 if( !edgePlannedChanges.containsKey( edgeF ) ) {
1182 edgePlannedChanges.put( edgeF,
1187 ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1189 if( !changesToPass.isSubset( currentChanges ) ) {
1190 todoEdges.add( edgeF );
1191 edgePlannedChanges.put( edgeF,
1192 Canonical.union( currentChanges,
1201 // then apply all of the changes for each edge at once
1202 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1203 while( itrMap.hasNext() ) {
1204 Map.Entry me = (Map.Entry) itrMap.next();
1205 RefEdge e = (RefEdge) me.getKey();
1206 ChangeSet C = (ChangeSet) me.getValue();
1208 // this propagation step is with respect to one change,
1209 // so we capture the full change from the old beta:
1210 ReachSet localDelta =
1211 Canonical.applyChangeSet( e.getBeta(),
1216 // but this propagation may be only one of many concurrent
1217 // possible changes, so keep a running union with the edge's
1218 // partially updated new beta set
1219 e.setBetaNew( Canonical.unionORpreds( e.getBetaNew(),
1224 edgesWithNewBeta.add( e );
1229 // used in makeCalleeView below to decide if there is
1230 // already an appropriate out-of-context edge in a callee
1231 // view graph for merging, or null if a new one will be added
1233 getOutOfContextReferenceTo( HeapRegionNode hrn,
1234 TypeDescriptor srcType,
1235 TypeDescriptor refType,
1237 assert belongsToThis( hrn );
1239 HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1240 if( hrnInContext == null ) {
1244 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1245 while( refItr.hasNext() ) {
1246 RefEdge re = refItr.next();
1248 assert belongsToThis( re.getSrc() );
1249 assert belongsToThis( re.getDst() );
1251 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1255 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1256 if( !hrnSrc.isOutOfContext() ) {
1260 if( srcType == null ) {
1261 if( hrnSrc.getType() != null ) {
1265 if( !srcType.equals( hrnSrc.getType() ) ) {
1270 if( !re.typeEquals( refType ) ) {
1274 if( !re.fieldEquals( refField ) ) {
1278 // tada! We found it!
1285 // used below to convert a ReachSet to its callee-context
1286 // equivalent with respect to allocation sites in this graph
1287 protected ReachSet toCalleeContext( ReachSet rs,
1289 Set<HrnIdOoc> oocHrnIdOoc2callee
1291 ReachSet out = ReachSet.factory();
1293 Iterator<ReachState> itr = rs.iterator();
1294 while( itr.hasNext() ) {
1295 ReachState stateCaller = itr.next();
1297 ReachState stateCallee = stateCaller;
1299 Iterator<AllocSite> asItr = allocSites.iterator();
1300 while( asItr.hasNext() ) {
1301 AllocSite as = asItr.next();
1303 ReachState stateNew = ReachState.factory();
1304 Iterator<ReachTuple> rtItr = stateCallee.iterator();
1305 while( rtItr.hasNext() ) {
1306 ReachTuple rt = rtItr.next();
1308 // only translate this tuple if it is
1309 // in the out-callee-context bag
1310 HrnIdOoc hio = new HrnIdOoc( rt.getHrnID(),
1313 if( !oocHrnIdOoc2callee.contains( hio ) ) {
1314 stateNew = Canonical.add( stateNew, rt );
1318 int age = as.getAgeCategory( rt.getHrnID() );
1320 // this is the current mapping, where 0, 1, 2S were allocated
1321 // in the current context, 0?, 1? and 2S? were allocated in a
1322 // previous context, and we're translating to a future context
1334 if( age == AllocSite.AGE_notInThisSite ) {
1335 // things not from the site just go back in
1336 stateNew = Canonical.add( stateNew, rt );
1338 } else if( age == AllocSite.AGE_summary ||
1341 // the in-context summary and all existing out-of-context
1343 stateNew = Canonical.add( stateNew,
1344 ReachTuple.factory( as.getSummary(),
1347 true // out-of-context
1351 // otherwise everything else just goes to an out-of-context
1352 // version, everything else the same
1353 Integer I = as.getAge( rt.getHrnID() );
1356 assert !rt.isMultiObject();
1358 stateNew = Canonical.add( stateNew,
1359 ReachTuple.factory( rt.getHrnID(),
1362 true // out-of-context
1368 stateCallee = stateNew;
1371 // attach the passed in preds
1372 stateCallee = Canonical.attach( stateCallee,
1375 out = Canonical.add( out,
1380 assert out.isCanonical();
1384 // used below to convert a ReachSet to its caller-context
1385 // equivalent with respect to allocation sites in this graph
1387 toCallerContext( ReachSet rs,
1388 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1390 ReachSet out = ReachSet.factory();
1392 Iterator<ReachState> itr = rs.iterator();
1393 while( itr.hasNext() ) {
1394 ReachState stateCallee = itr.next();
1396 if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
1398 // starting from one callee state...
1399 ReachSet rsCaller = ReachSet.factory( stateCallee );
1401 // possibly branch it into many states, which any
1402 // allocation site might do, so lots of derived states
1403 Iterator<AllocSite> asItr = allocSites.iterator();
1404 while( asItr.hasNext() ) {
1405 AllocSite as = asItr.next();
1406 rsCaller = Canonical.toCallerContext( rsCaller, as );
1409 // then before adding each derived, now caller-context
1410 // states to the output, attach the appropriate pred
1411 // based on the source callee state
1412 Iterator<ReachState> stateItr = rsCaller.iterator();
1413 while( stateItr.hasNext() ) {
1414 ReachState stateCaller = stateItr.next();
1415 stateCaller = Canonical.attach( stateCaller,
1416 calleeStatesSatisfied.get( stateCallee )
1418 out = Canonical.add( out,
1425 assert out.isCanonical();
1429 // used below to convert a ReachSet to an equivalent
1430 // version with shadow IDs merged into unshadowed IDs
1431 protected ReachSet unshadow( ReachSet rs ) {
1433 Iterator<AllocSite> asItr = allocSites.iterator();
1434 while( asItr.hasNext() ) {
1435 AllocSite as = asItr.next();
1436 out = Canonical.unshadow( out, as );
1438 assert out.isCanonical();
1443 // use this method to make a new reach graph that is
1444 // what heap the FlatMethod callee from the FlatCall
1445 // would start with reaching from its arguments in
1448 makeCalleeView( FlatCall fc,
1449 FlatMethod fmCallee,
1450 Set<Integer> callerNodeIDsCopiedToCallee,
1451 boolean writeDebugDOTs
1455 // first traverse this context to find nodes and edges
1456 // that will be callee-reachable
1457 Set<HeapRegionNode> reachableCallerNodes =
1458 new HashSet<HeapRegionNode>();
1460 // caller edges between callee-reachable nodes
1461 Set<RefEdge> reachableCallerEdges =
1462 new HashSet<RefEdge>();
1464 // caller edges from arg vars, and the matching param index
1465 // because these become a special edge in callee
1466 Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1467 new Hashtable<RefEdge, Integer>();
1469 // caller edges from local vars or callee-unreachable nodes
1470 // (out-of-context sources) to callee-reachable nodes
1471 Set<RefEdge> oocCallerEdges =
1472 new HashSet<RefEdge>();
1475 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1477 TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1478 VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
1480 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1481 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1483 toVisitInCaller.add( vnArgCaller );
1485 while( !toVisitInCaller.isEmpty() ) {
1486 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1487 toVisitInCaller.remove( rsnCaller );
1488 visitedInCaller.add( rsnCaller );
1490 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1491 while( itrRefEdges.hasNext() ) {
1492 RefEdge reCaller = itrRefEdges.next();
1493 HeapRegionNode hrnCaller = reCaller.getDst();
1495 callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
1496 reachableCallerNodes.add( hrnCaller );
1498 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1499 reachableCallerEdges.add( reCaller );
1501 if( rsnCaller.equals( vnArgCaller ) ) {
1502 reachableCallerArgEdges2paramIndex.put( reCaller, i );
1504 oocCallerEdges.add( reCaller );
1508 if( !visitedInCaller.contains( hrnCaller ) ) {
1509 toVisitInCaller.add( hrnCaller );
1512 } // end edge iteration
1513 } // end visiting heap nodes in caller
1514 } // end iterating over parameters as starting points
1517 // now collect out-of-callee-context IDs and
1518 // map them to whether the ID is out of the caller
1520 Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1522 Iterator<Integer> itrInContext =
1523 callerNodeIDsCopiedToCallee.iterator();
1524 while( itrInContext.hasNext() ) {
1525 Integer hrnID = itrInContext.next();
1526 HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1528 Iterator<RefEdge> itrMightCross =
1529 hrnCallerAndInContext.iteratorToReferencers();
1530 while( itrMightCross.hasNext() ) {
1531 RefEdge edgeMightCross = itrMightCross.next();
1533 RefSrcNode rsnCallerAndOutContext =
1534 edgeMightCross.getSrc();
1536 if( rsnCallerAndOutContext instanceof VariableNode ) {
1537 // variables do not have out-of-context reach states,
1539 oocCallerEdges.add( edgeMightCross );
1543 HeapRegionNode hrnCallerAndOutContext =
1544 (HeapRegionNode) rsnCallerAndOutContext;
1546 // is this source node out-of-context?
1547 if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1548 // no, skip this edge
1553 oocCallerEdges.add( edgeMightCross );
1555 // add all reach tuples on the node to list
1556 // of things that are out-of-context: insight
1557 // if this node is reachable from someting that WAS
1558 // in-context, then this node should already be in-context
1559 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1560 while( stateItr.hasNext() ) {
1561 ReachState state = stateItr.next();
1563 Iterator<ReachTuple> rtItr = state.iterator();
1564 while( rtItr.hasNext() ) {
1565 ReachTuple rt = rtItr.next();
1567 oocHrnIdOoc2callee.add( new HrnIdOoc( rt.getHrnID(),
1576 // the callee view is a new graph: DON'T MODIFY *THIS* graph
1577 ReachGraph rg = new ReachGraph();
1579 // add nodes to callee graph
1580 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1581 while( hrnItr.hasNext() ) {
1582 HeapRegionNode hrnCaller = hrnItr.next();
1584 assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
1585 assert !rg.id2hrn.containsKey( hrnCaller.getID() );
1587 ExistPred pred = ExistPred.factory( hrnCaller.getID(), null );
1588 ExistPredSet preds = ExistPredSet.factory( pred );
1590 rg.createNewHeapRegionNode( hrnCaller.getID(),
1591 hrnCaller.isSingleObject(),
1592 hrnCaller.isNewSummary(),
1593 false, // out-of-context?
1594 hrnCaller.getType(),
1595 hrnCaller.getAllocSite(),
1596 toCalleeContext( hrnCaller.getInherent(),
1600 toCalleeContext( hrnCaller.getAlpha(),
1605 hrnCaller.getDescription()
1609 // add param edges to callee graph
1611 reachableCallerArgEdges2paramIndex.entrySet().iterator();
1612 while( argEdges.hasNext() ) {
1613 Map.Entry me = (Map.Entry) argEdges.next();
1614 RefEdge reArg = (RefEdge) me.getKey();
1615 Integer index = (Integer) me.getValue();
1617 TempDescriptor arg = fmCallee.getParameter( index );
1619 VariableNode vnCallee =
1620 rg.getVariableNodeFromTemp( arg );
1622 HeapRegionNode hrnDstCaller = reArg.getDst();
1623 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1624 assert hrnDstCallee != null;
1627 ExistPred.factory( arg,
1629 hrnDstCallee.getID(),
1633 true, // out-of-callee-context
1634 false // out-of-caller-context
1637 ExistPredSet preds =
1638 ExistPredSet.factory( pred );
1641 new RefEdge( vnCallee,
1645 toCalleeContext( reArg.getBeta(),
1652 rg.addRefEdge( vnCallee,
1658 // add in-context edges to callee graph
1659 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1660 while( reItr.hasNext() ) {
1661 RefEdge reCaller = reItr.next();
1662 RefSrcNode rsnCaller = reCaller.getSrc();
1663 assert rsnCaller instanceof HeapRegionNode;
1664 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1665 HeapRegionNode hrnDstCaller = reCaller.getDst();
1667 HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
1668 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1669 assert hrnSrcCallee != null;
1670 assert hrnDstCallee != null;
1673 ExistPred.factory( null,
1674 hrnSrcCallee.getID(),
1675 hrnDstCallee.getID(),
1677 reCaller.getField(),
1679 false, // out-of-callee-context
1680 false // out-of-caller-context
1683 ExistPredSet preds =
1684 ExistPredSet.factory( pred );
1687 new RefEdge( hrnSrcCallee,
1690 reCaller.getField(),
1691 toCalleeContext( reCaller.getBeta(),
1698 rg.addRefEdge( hrnSrcCallee,
1704 // add out-of-context edges to callee graph
1705 reItr = oocCallerEdges.iterator();
1706 while( reItr.hasNext() ) {
1707 RefEdge reCaller = reItr.next();
1708 RefSrcNode rsnCaller = reCaller.getSrc();
1709 HeapRegionNode hrnDstCaller = reCaller.getDst();
1710 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1711 assert hrnDstCallee != null;
1713 TypeDescriptor oocNodeType;
1715 TempDescriptor oocPredSrcTemp = null;
1716 Integer oocPredSrcID = null;
1717 boolean outOfCalleeContext;
1718 boolean outOfCallerContext;
1720 if( rsnCaller instanceof VariableNode ) {
1721 VariableNode vnCaller = (VariableNode) rsnCaller;
1723 oocReach = rsetEmpty;
1724 oocPredSrcTemp = vnCaller.getTempDescriptor();
1725 outOfCalleeContext = true;
1726 outOfCallerContext = false;
1729 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1730 assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
1731 oocNodeType = hrnSrcCaller.getType();
1732 oocReach = hrnSrcCaller.getAlpha();
1733 oocPredSrcID = hrnSrcCaller.getID();
1734 if( hrnSrcCaller.isOutOfContext() ) {
1735 outOfCalleeContext = false;
1736 outOfCallerContext = true;
1738 outOfCalleeContext = true;
1739 outOfCallerContext = false;
1744 ExistPred.factory( oocPredSrcTemp,
1746 hrnDstCallee.getID(),
1748 reCaller.getField(),
1754 ExistPredSet preds =
1755 ExistPredSet.factory( pred );
1757 RefEdge oocEdgeExisting =
1758 rg.getOutOfContextReferenceTo( hrnDstCallee,
1764 if( oocEdgeExisting == null ) {
1765 // for consistency, map one out-of-context "identifier"
1766 // to one heap region node id, otherwise no convergence
1767 String oocid = "oocid"+
1769 hrnDstCallee.getIDString()+
1772 reCaller.getField();
1774 Integer oocHrnID = oocid2hrnid.get( oocid );
1776 HeapRegionNode hrnCalleeAndOutContext;
1778 if( oocHrnID == null ) {
1780 hrnCalleeAndOutContext =
1781 rg.createNewHeapRegionNode( null, // ID
1782 false, // single object?
1783 false, // new summary?
1784 true, // out-of-context?
1786 null, // alloc site, shouldn't be used
1787 toCalleeContext( oocReach,
1791 toCalleeContext( oocReach,
1799 oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1803 // the mapping already exists, so see if node is there
1804 hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1806 if( hrnCalleeAndOutContext == null ) {
1808 hrnCalleeAndOutContext =
1809 rg.createNewHeapRegionNode( oocHrnID, // ID
1810 false, // single object?
1811 false, // new summary?
1812 true, // out-of-context?
1814 null, // alloc site, shouldn't be used
1815 toCalleeContext( oocReach,
1819 toCalleeContext( oocReach,
1828 // otherwise it is there, so merge reachability
1829 hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1830 toCalleeContext( oocReach,
1839 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1841 rg.addRefEdge( hrnCalleeAndOutContext,
1843 new RefEdge( hrnCalleeAndOutContext,
1846 reCaller.getField(),
1847 toCalleeContext( reCaller.getBeta(),
1856 // the out-of-context edge already exists
1857 oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
1858 toCalleeContext( reCaller.getBeta(),
1865 oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1870 HeapRegionNode hrnCalleeAndOutContext =
1871 (HeapRegionNode) oocEdgeExisting.getSrc();
1872 hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1873 toCalleeContext( oocReach,
1880 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1885 if( writeDebugDOTs ) {
1886 debugGraphPrefix = String.format( "call%02d", debugCallSiteVisitCounter );
1887 rg.writeGraph( debugGraphPrefix+"calleeview",
1888 resolveMethodDebugDOTwriteLabels,
1889 resolveMethodDebugDOTselectTemps,
1890 resolveMethodDebugDOTpruneGarbage,
1891 resolveMethodDebugDOThideSubsetReach,
1892 resolveMethodDebugDOThideEdgeTaints );
1898 private static Hashtable<String, Integer> oocid2hrnid =
1899 new Hashtable<String, Integer>();
1902 // useful since many graphs writes in the method call debug code
1903 private static boolean resolveMethodDebugDOTwriteLabels = true;
1904 private static boolean resolveMethodDebugDOTselectTemps = true;
1905 private static boolean resolveMethodDebugDOTpruneGarbage = true;
1906 private static boolean resolveMethodDebugDOThideSubsetReach = false;
1907 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
1909 static String debugGraphPrefix;
1910 static int debugCallSiteVisitCounter;
1911 static int debugCallSiteVisitStartCapture;
1912 static int debugCallSiteNumVisitsToCapture;
1913 static boolean debugCallSiteStopAfter;
1917 resolveMethodCall( FlatCall fc,
1918 FlatMethod fmCallee,
1919 ReachGraph rgCallee,
1920 Set<Integer> callerNodeIDsCopiedToCallee,
1921 boolean writeDebugDOTs
1924 if( writeDebugDOTs ) {
1925 System.out.println( " Writing out visit "+
1926 debugCallSiteVisitCounter+
1927 " to debug call site" );
1929 debugGraphPrefix = String.format( "call%02d",
1930 debugCallSiteVisitCounter );
1932 rgCallee.writeGraph( debugGraphPrefix+"callee",
1933 resolveMethodDebugDOTwriteLabels,
1934 resolveMethodDebugDOTselectTemps,
1935 resolveMethodDebugDOTpruneGarbage,
1936 resolveMethodDebugDOThideSubsetReach,
1937 resolveMethodDebugDOThideEdgeTaints );
1939 writeGraph( debugGraphPrefix+"caller00In",
1940 resolveMethodDebugDOTwriteLabels,
1941 resolveMethodDebugDOTselectTemps,
1942 resolveMethodDebugDOTpruneGarbage,
1943 resolveMethodDebugDOThideSubsetReach,
1944 resolveMethodDebugDOThideEdgeTaints,
1945 callerNodeIDsCopiedToCallee );
1950 // method call transfer function steps:
1951 // 1. Use current callee-reachable heap (CRH) to test callee
1952 // predicates and mark what will be coming in.
1953 // 2. Wipe CRH out of caller.
1954 // 3. Transplant marked callee parts in:
1955 // a) bring in nodes
1956 // b) bring in callee -> callee edges
1957 // c) resolve out-of-context -> callee edges
1958 // d) assign return value
1959 // 4. Collapse shadow nodes down
1960 // 5. Global sweep it.
1963 // 1. mark what callee elements have satisfied predicates
1964 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1965 new Hashtable<HeapRegionNode, ExistPredSet>();
1967 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1968 new Hashtable<RefEdge, ExistPredSet>();
1970 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1971 new Hashtable<ReachState, ExistPredSet>();
1973 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1974 new Hashtable< RefEdge, Set<RefSrcNode> >();
1976 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1977 while( meItr.hasNext() ) {
1978 Map.Entry me = (Map.Entry) meItr.next();
1979 Integer id = (Integer) me.getKey();
1980 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1982 // if a callee element's predicates are satisfied then a set
1983 // of CALLER predicates is returned: they are the predicates
1984 // that the callee element moved into the caller context
1985 // should have, and it is inefficient to find this again later
1986 ExistPredSet predsIfSatis =
1987 hrnCallee.getPreds().isSatisfiedBy( this,
1988 callerNodeIDsCopiedToCallee
1991 if( predsIfSatis != null ) {
1992 calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1994 // otherwise don't bother looking at edges to this node
1998 // since the node is coming over, find out which reach
1999 // states on it should come over, too
2000 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2001 while( stateItr.hasNext() ) {
2002 ReachState stateCallee = stateItr.next();
2005 stateCallee.getPreds().isSatisfiedBy( this,
2006 callerNodeIDsCopiedToCallee
2008 if( predsIfSatis != null ) {
2009 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2013 // then look at edges to the node
2014 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2015 while( reItr.hasNext() ) {
2016 RefEdge reCallee = reItr.next();
2017 RefSrcNode rsnCallee = reCallee.getSrc();
2019 // (caller local variables to in-context heap regions)
2020 // have an (out-of-context heap region -> in-context heap region)
2021 // abstraction in the callEE, so its true we never need to
2022 // look at a (var node -> heap region) edge in callee to bring
2023 // those over for the call site transfer. What about (param var->heap region)
2024 // edges in callee? They are dealt with below this loop.
2025 // So, yes, at this point skip (var->region) edges in callee
2026 if( rsnCallee instanceof VariableNode ) {
2030 // first see if the source is out-of-context, and only
2031 // proceed with this edge if we find some caller-context
2033 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2034 boolean matchedOutOfContext = false;
2036 if( !hrnSrcCallee.isOutOfContext() ) {
2039 hrnSrcCallee.getPreds().isSatisfiedBy( this,
2040 callerNodeIDsCopiedToCallee
2042 if( predsIfSatis != null ) {
2043 calleeNodesSatisfied.put( hrnSrcCallee, predsIfSatis );
2045 // otherwise forget this edge
2050 // hrnSrcCallee is out-of-context
2052 assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2054 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2056 // is the target node in the caller?
2057 HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2058 if( hrnDstCaller == null ) {
2062 Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2063 while( reDstItr.hasNext() ) {
2064 // the edge and field (either possibly null) must match
2065 RefEdge reCaller = reDstItr.next();
2067 if( !reCaller.typeEquals ( reCallee.getType() ) ||
2068 !reCaller.fieldEquals( reCallee.getField() )
2073 RefSrcNode rsnCaller = reCaller.getSrc();
2074 if( rsnCaller instanceof VariableNode ) {
2076 // a variable node matches an OOC region with null type
2077 if( hrnSrcCallee.getType() != null ) {
2082 // otherwise types should match
2083 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2084 if( hrnSrcCallee.getType() == null ) {
2085 if( hrnCallerSrc.getType() != null ) {
2089 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2095 rsnCallers.add( rsnCaller );
2096 matchedOutOfContext = true;
2099 if( !rsnCallers.isEmpty() ) {
2100 calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2104 if( hrnSrcCallee.isOutOfContext() &&
2105 !matchedOutOfContext ) {
2110 reCallee.getPreds().isSatisfiedBy( this,
2111 callerNodeIDsCopiedToCallee
2114 if( predsIfSatis != null ) {
2115 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2117 // since the edge is coming over, find out which reach
2118 // states on it should come over, too
2119 stateItr = reCallee.getBeta().iterator();
2120 while( stateItr.hasNext() ) {
2121 ReachState stateCallee = stateItr.next();
2124 stateCallee.getPreds().isSatisfiedBy( this,
2125 callerNodeIDsCopiedToCallee
2127 if( predsIfSatis != null ) {
2128 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2135 if( writeDebugDOTs ) {
2136 writeGraph( debugGraphPrefix+"caller20BeforeWipe",
2137 resolveMethodDebugDOTwriteLabels,
2138 resolveMethodDebugDOTselectTemps,
2139 resolveMethodDebugDOTpruneGarbage,
2140 resolveMethodDebugDOThideSubsetReach,
2141 resolveMethodDebugDOThideEdgeTaints );
2145 // 2. predicates tested, ok to wipe out caller part
2146 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2147 while( hrnItr.hasNext() ) {
2148 Integer hrnID = hrnItr.next();
2149 HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2150 assert hrnCaller != null;
2152 // when clearing off nodes, also eliminate variable
2154 wipeOut( hrnCaller, true );
2159 if( writeDebugDOTs ) {
2160 writeGraph( debugGraphPrefix+"caller30BeforeAddingNodes",
2161 resolveMethodDebugDOTwriteLabels,
2162 resolveMethodDebugDOTselectTemps,
2163 resolveMethodDebugDOTpruneGarbage,
2164 resolveMethodDebugDOThideSubsetReach,
2165 resolveMethodDebugDOThideEdgeTaints );
2171 // 3. callee elements with satisfied preds come in, note that
2172 // the mapping of elements satisfied to preds is like this:
2173 // A callee element EE has preds EEp that are satisfied by
2174 // some caller element ER. We bring EE into the caller
2175 // context as ERee with the preds of ER, namely ERp, which
2176 // in the following algorithm is the value in the mapping
2179 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2180 while( satisItr.hasNext() ) {
2181 Map.Entry me = (Map.Entry) satisItr.next();
2182 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2183 ExistPredSet preds = (ExistPredSet) me.getValue();
2185 // TODO: I think its true that the current implementation uses
2186 // the type of the OOC region and the predicates OF THE EDGE from
2187 // it to link everything up in caller context, so that's why we're
2188 // skipping this... maybe that's a sillier way to do it?
2189 if( hrnCallee.isOutOfContext() ) {
2193 AllocSite as = hrnCallee.getAllocSite();
2194 allocSites.add( as );
2196 Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2198 HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2199 if( hrnCaller == null ) {
2201 createNewHeapRegionNode( hrnIDshadow, // id or null to generate a new one
2202 hrnCallee.isSingleObject(), // single object?
2203 hrnCallee.isNewSummary(), // summary?
2204 false, // out-of-context?
2205 hrnCallee.getType(), // type
2206 hrnCallee.getAllocSite(), // allocation site
2207 toCallerContext( hrnCallee.getInherent(),
2208 calleeStatesSatisfied ), // inherent reach
2209 null, // current reach
2210 predsEmpty, // predicates
2211 hrnCallee.getDescription() // description
2214 assert hrnCaller.isWiped();
2217 hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2218 calleeStatesSatisfied
2222 hrnCaller.setPreds( preds );
2229 if( writeDebugDOTs ) {
2230 writeGraph( debugGraphPrefix+"caller31BeforeAddingEdges",
2231 resolveMethodDebugDOTwriteLabels,
2232 resolveMethodDebugDOTselectTemps,
2233 resolveMethodDebugDOTpruneGarbage,
2234 resolveMethodDebugDOThideSubsetReach,
2235 resolveMethodDebugDOThideEdgeTaints );
2239 // set these up during the next procedure so after
2240 // the caller has all of its nodes and edges put
2241 // back together we can propagate the callee's
2242 // reach changes backwards into the caller graph
2243 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2245 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2246 new Hashtable<RefEdge, ChangeSet>();
2249 // 3.b) callee -> callee edges AND out-of-context -> callee
2250 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2251 while( satisItr.hasNext() ) {
2252 Map.Entry me = (Map.Entry) satisItr.next();
2253 RefEdge reCallee = (RefEdge) me.getKey();
2254 ExistPredSet preds = (ExistPredSet) me.getValue();
2256 HeapRegionNode hrnDstCallee = reCallee.getDst();
2257 AllocSite asDst = hrnDstCallee.getAllocSite();
2258 allocSites.add( asDst );
2260 Integer hrnIDDstShadow =
2261 asDst.getShadowIDfromID( hrnDstCallee.getID() );
2263 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2264 assert hrnDstCaller != null;
2267 RefSrcNode rsnCallee = reCallee.getSrc();
2269 Set<RefSrcNode> rsnCallers =
2270 new HashSet<RefSrcNode>();
2272 Set<RefSrcNode> oocCallers =
2273 calleeEdges2oocCallerSrcMatches.get( reCallee );
2275 if( rsnCallee instanceof HeapRegionNode ) {
2276 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2277 if( hrnCalleeSrc.isOutOfContext() ) {
2278 assert oocCallers != null;
2283 if( oocCallers == null ) {
2284 // there are no out-of-context matches, so it's
2285 // either a param/arg var or one in-context heap region
2286 if( rsnCallee instanceof VariableNode ) {
2287 // variable -> node in the callee should only
2288 // come into the caller if its from a param var
2289 VariableNode vnCallee = (VariableNode) rsnCallee;
2290 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2291 TempDescriptor tdArg = fc.getArgMatchingParam( fmCallee,
2293 if( tdArg == null ) {
2294 // this means the variable isn't a parameter, its local
2295 // to the callee so we ignore it in call site transfer
2296 // shouldn't this NEVER HAPPEN?
2300 rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2303 // otherwise source is in context, one region
2305 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2307 // translate an in-context node to shadow
2308 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2309 allocSites.add( asSrc );
2311 Integer hrnIDSrcShadow =
2312 asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2314 HeapRegionNode hrnSrcCallerShadow =
2315 this.id2hrn.get( hrnIDSrcShadow );
2317 assert hrnSrcCallerShadow != null;
2319 rsnCallers.add( hrnSrcCallerShadow );
2323 // otherwise we have a set of out-of-context srcs
2324 // that should NOT be translated to shadow nodes
2325 assert !oocCallers.isEmpty();
2326 rsnCallers.addAll( oocCallers );
2329 // now make all caller edges we've identified from
2330 // this callee edge with a satisfied predicate
2331 assert !rsnCallers.isEmpty();
2332 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2333 while( rsnItr.hasNext() ) {
2334 RefSrcNode rsnCaller = rsnItr.next();
2336 RefEdge reCaller = new RefEdge( rsnCaller,
2339 reCallee.getField(),
2340 toCallerContext( reCallee.getBeta(),
2341 calleeStatesSatisfied ),
2345 ChangeSet cs = ChangeSet.factory();
2346 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2347 while( rsItr.hasNext() ) {
2348 ReachState state = rsItr.next();
2349 ExistPredSet predsPreCallee = state.getPreds();
2351 if( state.isEmpty() ) {
2355 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2356 while( predItr.hasNext() ) {
2357 ExistPred pred = predItr.next();
2358 ReachState old = pred.ne_state;
2364 cs = Canonical.add( cs,
2365 ChangeTuple.factory( old,
2373 // look to see if an edge with same field exists
2374 // and merge with it, otherwise just add the edge
2375 RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2379 if( edgeExisting != null ) {
2380 edgeExisting.setBeta(
2381 Canonical.unionORpreds( edgeExisting.getBeta(),
2385 edgeExisting.setPreds(
2386 Canonical.join( edgeExisting.getPreds(),
2391 // for reach propagation
2392 if( !cs.isEmpty() ) {
2393 ChangeSet csExisting = edgePlannedChanges.get( edgeExisting );
2394 if( csExisting == null ) {
2395 csExisting = ChangeSet.factory();
2397 edgePlannedChanges.put( edgeExisting,
2398 Canonical.union( csExisting,
2405 addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2407 // for reach propagation
2408 if( !cs.isEmpty() ) {
2409 edgesForPropagation.add( reCaller );
2410 assert !edgePlannedChanges.containsKey( reCaller );
2411 edgePlannedChanges.put( reCaller, cs );
2420 if( writeDebugDOTs ) {
2421 writeGraph( debugGraphPrefix+"caller35BeforeAssignReturnValue",
2422 resolveMethodDebugDOTwriteLabels,
2423 resolveMethodDebugDOTselectTemps,
2424 resolveMethodDebugDOTpruneGarbage,
2425 resolveMethodDebugDOThideSubsetReach,
2426 resolveMethodDebugDOThideEdgeTaints );
2431 // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2432 // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2433 // EDGES, JUST BRINGING THEM ALL! It'll work for now, over approximation
2435 // 3.d) handle return value assignment if needed
2436 TempDescriptor returnTemp = fc.getReturnTemp();
2437 if( returnTemp != null &&
2438 DisjointAnalysis.shouldAnalysisTrack( returnTemp.getType() )
2441 VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2442 clearRefEdgesFrom( vnLhsCaller, null, null, true );
2444 VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2445 Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2446 while( reCalleeItr.hasNext() ) {
2447 RefEdge reCallee = reCalleeItr.next();
2448 HeapRegionNode hrnDstCallee = reCallee.getDst();
2450 // some edge types are not possible return values when we can
2451 // see what type variable we are assigning it to
2452 if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2453 System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2455 " for return temp "+returnTemp+
2456 " of type "+returnTemp.getType()
2462 AllocSite asDst = hrnDstCallee.getAllocSite();
2463 allocSites.add( asDst );
2465 Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2467 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2468 if( hrnDstCaller == null ) {
2470 createNewHeapRegionNode( hrnIDDstShadow, // id or null to generate a new one
2471 hrnDstCallee.isSingleObject(), // single object?
2472 hrnDstCallee.isNewSummary(), // summary?
2473 false, // out-of-context?
2474 hrnDstCallee.getType(), // type
2475 hrnDstCallee.getAllocSite(), // allocation site
2476 toCallerContext( hrnDstCallee.getInherent(),
2477 calleeStatesSatisfied ), // inherent reach
2478 toCallerContext( hrnDstCallee.getAlpha(),
2479 calleeStatesSatisfied ), // current reach
2480 predsTrue, // predicates
2481 hrnDstCallee.getDescription() // description
2485 TypeDescriptor tdNewEdge =
2486 mostSpecificType( reCallee.getType(),
2487 hrnDstCallee.getType(),
2488 hrnDstCaller.getType()
2491 RefEdge reCaller = new RefEdge( vnLhsCaller,
2495 toCallerContext( reCallee.getBeta(),
2496 calleeStatesSatisfied ),
2500 addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2506 if( writeDebugDOTs ) {
2507 writeGraph( debugGraphPrefix+"caller38propagateReach",
2508 resolveMethodDebugDOTwriteLabels,
2509 resolveMethodDebugDOTselectTemps,
2510 resolveMethodDebugDOTpruneGarbage,
2511 resolveMethodDebugDOThideSubsetReach,
2512 resolveMethodDebugDOThideEdgeTaints );
2515 // propagate callee reachability changes to the rest
2516 // of the caller graph edges
2517 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2519 propagateTokensOverEdges( edgesForPropagation, // source edges
2520 edgePlannedChanges, // map src edge to change set
2521 edgesUpdated ); // list of updated edges
2523 // commit beta' (beta<-betaNew)
2524 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2525 while( edgeItr.hasNext() ) {
2526 edgeItr.next().applyBetaNew();
2535 if( writeDebugDOTs ) {
2536 writeGraph( debugGraphPrefix+"caller40BeforeShadowMerge",
2537 resolveMethodDebugDOTwriteLabels,
2538 resolveMethodDebugDOTselectTemps,
2539 resolveMethodDebugDOTpruneGarbage,
2540 resolveMethodDebugDOThideSubsetReach,
2541 resolveMethodDebugDOThideEdgeTaints );
2545 // 4) merge shadow nodes so alloc sites are back to k
2546 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2547 while( asItr.hasNext() ) {
2548 // for each allocation site do the following to merge
2549 // shadow nodes (newest from callee) with any existing
2550 // look for the newest normal and newest shadow "slot"
2551 // not being used, transfer normal to shadow. Keep
2552 // doing this until there are no more normal nodes, or
2553 // no empty shadow slots: then merge all remaining normal
2554 // nodes into the shadow summary. Finally, convert all
2555 // shadow to their normal versions.
2556 AllocSite as = asItr.next();
2559 while( ageNorm < allocationDepth &&
2560 ageShad < allocationDepth ) {
2562 // first, are there any normal nodes left?
2563 Integer idNorm = as.getIthOldest( ageNorm );
2564 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2565 if( hrnNorm == null ) {
2566 // no, this age of normal node not in the caller graph
2571 // yes, a normal node exists, is there an empty shadow
2572 // "slot" to transfer it onto?
2573 HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2574 if( !hrnShad.isWiped() ) {
2575 // no, this age of shadow node is not empty
2580 // yes, this shadow node is empty
2581 transferOnto( hrnNorm, hrnShad );
2586 // now, while there are still normal nodes but no shadow
2587 // slots, merge normal nodes into the shadow summary
2588 while( ageNorm < allocationDepth ) {
2590 // first, are there any normal nodes left?
2591 Integer idNorm = as.getIthOldest( ageNorm );
2592 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2593 if( hrnNorm == null ) {
2594 // no, this age of normal node not in the caller graph
2599 // yes, a normal node exists, so get the shadow summary
2600 HeapRegionNode summShad = getSummaryNode( as, true );
2601 mergeIntoSummary( hrnNorm, summShad );
2605 // if there is a normal summary, merge it into shadow summary
2606 Integer idNorm = as.getSummary();
2607 HeapRegionNode summNorm = id2hrn.get( idNorm );
2608 if( summNorm != null ) {
2609 HeapRegionNode summShad = getSummaryNode( as, true );
2610 mergeIntoSummary( summNorm, summShad );
2613 // finally, flip all existing shadow nodes onto the normal
2614 for( int i = 0; i < allocationDepth; ++i ) {
2615 Integer idShad = as.getIthOldestShadow( i );
2616 HeapRegionNode hrnShad = id2hrn.get( idShad );
2617 if( hrnShad != null ) {
2619 HeapRegionNode hrnNorm = getIthNode( as, i, false );
2620 assert hrnNorm.isWiped();
2621 transferOnto( hrnShad, hrnNorm );
2625 Integer idShad = as.getSummaryShadow();
2626 HeapRegionNode summShad = id2hrn.get( idShad );
2627 if( summShad != null ) {
2628 summNorm = getSummaryNode( as, false );
2629 transferOnto( summShad, summNorm );
2638 if( writeDebugDOTs ) {
2639 writeGraph( debugGraphPrefix+"caller45BeforeUnshadow",
2640 resolveMethodDebugDOTwriteLabels,
2641 resolveMethodDebugDOTselectTemps,
2642 resolveMethodDebugDOTpruneGarbage,
2643 resolveMethodDebugDOThideSubsetReach,
2644 resolveMethodDebugDOThideEdgeTaints );
2648 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2649 while( itrAllHRNodes.hasNext() ) {
2650 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
2651 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2653 hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2655 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2656 while( itrEdges.hasNext() ) {
2657 RefEdge re = itrEdges.next();
2658 re.setBeta( unshadow( re.getBeta() ) );
2665 if( writeDebugDOTs ) {
2666 writeGraph( debugGraphPrefix+"caller50BeforeGlobalSweep",
2667 resolveMethodDebugDOTwriteLabels,
2668 resolveMethodDebugDOTselectTemps,
2669 resolveMethodDebugDOTpruneGarbage,
2670 resolveMethodDebugDOThideSubsetReach,
2671 resolveMethodDebugDOThideEdgeTaints );
2676 if( !DISABLE_GLOBAL_SWEEP ) {
2681 if( writeDebugDOTs ) {
2682 writeGraph( debugGraphPrefix+"caller90AfterTransfer",
2683 resolveMethodDebugDOTwriteLabels,
2684 resolveMethodDebugDOTselectTemps,
2685 resolveMethodDebugDOTpruneGarbage,
2686 resolveMethodDebugDOThideSubsetReach,
2687 resolveMethodDebugDOThideEdgeTaints );
2693 ////////////////////////////////////////////////////
2695 // Abstract garbage collection simply removes
2696 // heap region nodes that are not mechanically
2697 // reachable from a root set. This step is
2698 // essential for testing node and edge existence
2699 // predicates efficiently
2701 ////////////////////////////////////////////////////
2702 public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2704 // calculate a root set, will be different for Java
2705 // version of analysis versus Bamboo version
2706 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2708 // visit every variable in graph while building root
2709 // set, and do iterating on a copy, so we can remove
2710 // dead variables while we're at this
2711 Iterator makeCopyItr = td2vn.entrySet().iterator();
2712 Set entrysCopy = new HashSet();
2713 while( makeCopyItr.hasNext() ) {
2714 entrysCopy.add( makeCopyItr.next() );
2717 Iterator eItr = entrysCopy.iterator();
2718 while( eItr.hasNext() ) {
2719 Map.Entry me = (Map.Entry) eItr.next();
2720 TempDescriptor td = (TempDescriptor) me.getKey();
2721 VariableNode vn = (VariableNode) me.getValue();
2723 if( liveSet.contains( td ) ) {
2727 // dead var, remove completely from graph
2729 clearRefEdgesFrom( vn, null, null, true );
2733 // everything visited in a traversal is
2734 // considered abstractly live
2735 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2737 while( !toVisit.isEmpty() ) {
2738 RefSrcNode rsn = toVisit.iterator().next();
2739 toVisit.remove( rsn );
2742 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2743 while( hrnItr.hasNext() ) {
2744 RefEdge edge = hrnItr.next();
2745 HeapRegionNode hrn = edge.getDst();
2747 if( !visited.contains( hrn ) ) {
2753 // get a copy of the set to iterate over because
2754 // we're going to monkey with the graph when we
2755 // identify a garbage node
2756 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2757 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2758 while( hrnItr.hasNext() ) {
2759 hrnAllPrior.add( hrnItr.next() );
2762 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2763 while( hrnAllItr.hasNext() ) {
2764 HeapRegionNode hrn = hrnAllItr.next();
2766 if( !visited.contains( hrn ) ) {
2768 // heap region nodes are compared across ReachGraph
2769 // objects by their integer ID, so when discarding
2770 // garbage nodes we must also discard entries in
2771 // the ID -> heap region hashtable.
2772 id2hrn.remove( hrn.getID() );
2774 // RefEdge objects are two-way linked between
2775 // nodes, so when a node is identified as garbage,
2776 // actively clear references to and from it so
2777 // live nodes won't have dangling RefEdge's
2778 wipeOut( hrn, true );
2780 // if we just removed the last node from an allocation
2781 // site, it should be taken out of the ReachGraph's list
2782 AllocSite as = hrn.getAllocSite();
2783 if( !hasNodesOf( as ) ) {
2784 allocSites.remove( as );
2790 protected boolean hasNodesOf( AllocSite as ) {
2791 if( id2hrn.containsKey( as.getSummary() ) ) {
2795 for( int i = 0; i < allocationDepth; ++i ) {
2796 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2804 ////////////////////////////////////////////////////
2806 // This global sweep is an optional step to prune
2807 // reachability sets that are not internally
2808 // consistent with the global graph. It should be
2809 // invoked after strong updates or method calls.
2811 ////////////////////////////////////////////////////
2812 public void globalSweep() {
2814 // boldB is part of the phase 1 sweep
2815 // it has an in-context table and an out-of-context table
2816 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2817 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2819 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2820 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2822 // visit every heap region to initialize alphaNew and betaNew,
2823 // and make a map of every hrnID to the source nodes it should
2824 // propagate forward from. In-context flagged hrnID's propagate
2825 // from only the in-context node they name, but out-of-context
2826 // ID's may propagate from several out-of-context nodes
2827 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2828 new Hashtable< Integer, Set<HeapRegionNode> >();
2830 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2831 new Hashtable< Integer, Set<HeapRegionNode> >();
2834 Iterator itrHrns = id2hrn.entrySet().iterator();
2835 while( itrHrns.hasNext() ) {
2836 Map.Entry me = (Map.Entry) itrHrns.next();
2837 Integer hrnID = (Integer) me.getKey();
2838 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2840 // assert that this node and incoming edges have clean alphaNew
2841 // and betaNew sets, respectively
2842 assert rsetEmpty.equals( hrn.getAlphaNew() );
2844 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2845 while( itrRers.hasNext() ) {
2846 RefEdge edge = itrRers.next();
2847 assert rsetEmpty.equals( edge.getBetaNew() );
2850 // make a mapping of IDs to heap regions they propagate from
2851 if( hrn.isFlagged() ) {
2852 assert !hrn.isOutOfContext();
2853 assert !icID2srcs.containsKey( hrn.getID() );
2855 // in-context flagged node IDs simply propagate from the
2857 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2859 icID2srcs.put( hrn.getID(), srcs );
2862 if( hrn.isOutOfContext() ) {
2863 assert !hrn.isFlagged();
2865 // the reachability states on an out-of-context
2866 // node are not really important (combinations of
2867 // IDs or arity)--what matters is that the states
2868 // specify which nodes this out-of-context node
2869 // stands in for. For example, if the state [17?, 19*]
2870 // appears on the ooc node, it may serve as a source
2871 // for node 17? and a source for node 19.
2872 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2873 while( stateItr.hasNext() ) {
2874 ReachState state = stateItr.next();
2876 Iterator<ReachTuple> rtItr = state.iterator();
2877 while( rtItr.hasNext() ) {
2878 ReachTuple rt = rtItr.next();
2879 assert rt.isOutOfContext();
2881 Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2882 if( srcs == null ) {
2883 srcs = new HashSet<HeapRegionNode>();
2886 oocID2srcs.put( rt.getHrnID(), srcs );
2892 // calculate boldB for all hrnIDs identified by the above
2893 // node traversal, propagating from every source
2894 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2897 Set<HeapRegionNode> srcs;
2900 if( !icID2srcs.isEmpty() ) {
2901 Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2902 hrnID = (Integer) me.getKey();
2903 srcs = (Set<HeapRegionNode>) me.getValue();
2905 icID2srcs.remove( hrnID );
2908 assert !oocID2srcs.isEmpty();
2910 Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2911 hrnID = (Integer) me.getKey();
2912 srcs = (Set<HeapRegionNode>) me.getValue();
2914 oocID2srcs.remove( hrnID );
2918 Hashtable<RefEdge, ReachSet> boldB_f =
2919 new Hashtable<RefEdge, ReachSet>();
2921 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2923 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2924 while( hrnItr.hasNext() ) {
2925 HeapRegionNode hrn = hrnItr.next();
2927 assert workSetEdges.isEmpty();
2929 // initial boldB_f constraints
2930 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2931 while( itrRees.hasNext() ) {
2932 RefEdge edge = itrRees.next();
2934 assert !boldB_f.containsKey( edge );
2935 boldB_f.put( edge, edge.getBeta() );
2937 assert !workSetEdges.contains( edge );
2938 workSetEdges.add( edge );
2941 // enforce the boldB_f constraint at edges until we reach a fixed point
2942 while( !workSetEdges.isEmpty() ) {
2943 RefEdge edge = workSetEdges.iterator().next();
2944 workSetEdges.remove( edge );
2946 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2947 while( itrPrime.hasNext() ) {
2948 RefEdge edgePrime = itrPrime.next();
2950 ReachSet prevResult = boldB_f.get( edgePrime );
2951 ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2955 if( prevResult == null ||
2956 Canonical.unionORpreds( prevResult,
2957 intersection ).size()
2961 if( prevResult == null ) {
2962 boldB_f.put( edgePrime,
2963 Canonical.unionORpreds( edgePrime.getBeta(),
2968 boldB_f.put( edgePrime,
2969 Canonical.unionORpreds( prevResult,
2974 workSetEdges.add( edgePrime );
2981 boldBic.put( hrnID, boldB_f );
2983 boldBooc.put( hrnID, boldB_f );
2988 // use boldB to prune hrnIDs from alpha states that are impossible
2989 // and propagate the differences backwards across edges
2990 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2992 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2993 new Hashtable<RefEdge, ChangeSet>();
2996 itrHrns = id2hrn.entrySet().iterator();
2997 while( itrHrns.hasNext() ) {
2998 Map.Entry me = (Map.Entry) itrHrns.next();
2999 Integer hrnID = (Integer) me.getKey();
3000 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3002 // out-of-context nodes don't participate in the
3003 // global sweep, they serve as sources for the pass
3005 if( hrn.isOutOfContext() ) {
3009 // the inherent states of a region are the exception
3010 // to removal as the global sweep prunes
3011 ReachTuple rtException = ReachTuple.factory( hrnID,
3012 !hrn.isSingleObject(),
3013 ReachTuple.ARITY_ONE,
3014 false // out-of-context
3017 ChangeSet cts = ChangeSet.factory();
3019 // mark hrnIDs for removal
3020 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3021 while( stateItr.hasNext() ) {
3022 ReachState stateOld = stateItr.next();
3024 ReachState markedHrnIDs = ReachState.factory();
3026 Iterator<ReachTuple> rtItr = stateOld.iterator();
3027 while( rtItr.hasNext() ) {
3028 ReachTuple rtOld = rtItr.next();
3030 // never remove the inherent hrnID from a flagged region
3031 // because it is trivially satisfied
3032 if( hrn.isFlagged() ) {
3033 if( rtOld == rtException ) {
3038 // does boldB allow this hrnID?
3039 boolean foundState = false;
3040 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3041 while( incidentEdgeItr.hasNext() ) {
3042 RefEdge incidentEdge = incidentEdgeItr.next();
3044 Hashtable<RefEdge, ReachSet> B;
3045 if( rtOld.isOutOfContext() ) {
3046 B = boldBooc.get( rtOld.getHrnID() );
3049 if( !id2hrn.containsKey( rtOld.getHrnID() ) ) {
3050 // let symbols not in the graph get pruned
3054 B = boldBic.get( rtOld.getHrnID() );
3058 ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3059 if( boldB_rtOld_incident != null &&
3060 boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
3068 markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3072 // if there is nothing marked, just move on
3073 if( markedHrnIDs.isEmpty() ) {
3074 hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3081 // remove all marked hrnIDs and establish a change set that should
3082 // propagate backwards over edges from this node
3083 ReachState statePruned = ReachState.factory();
3084 rtItr = stateOld.iterator();
3085 while( rtItr.hasNext() ) {
3086 ReachTuple rtOld = rtItr.next();
3088 if( !markedHrnIDs.containsTuple( rtOld ) ) {
3089 statePruned = Canonical.add( statePruned, rtOld );
3092 assert !stateOld.equals( statePruned );
3094 hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3098 ChangeTuple ct = ChangeTuple.factory( stateOld,
3101 cts = Canonical.add( cts, ct );
3104 // throw change tuple set on all incident edges
3105 if( !cts.isEmpty() ) {
3106 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3107 while( incidentEdgeItr.hasNext() ) {
3108 RefEdge incidentEdge = incidentEdgeItr.next();
3110 edgesForPropagation.add( incidentEdge );
3112 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3113 edgePlannedChanges.put( incidentEdge, cts );
3115 edgePlannedChanges.put(
3117 Canonical.union( edgePlannedChanges.get( incidentEdge ),
3126 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3128 propagateTokensOverEdges( edgesForPropagation,
3132 // at the end of the 1st phase reference edges have
3133 // beta, betaNew that correspond to beta and betaR
3135 // commit beta<-betaNew, so beta=betaR and betaNew
3136 // will represent the beta' calculation in 2nd phase
3138 // commit alpha<-alphaNew because it won't change
3139 HashSet<RefEdge> res = new HashSet<RefEdge>();
3141 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3142 while( nodeItr.hasNext() ) {
3143 HeapRegionNode hrn = nodeItr.next();
3145 // as mentioned above, out-of-context nodes only serve
3146 // as sources of reach states for the sweep, not part
3148 if( hrn.isOutOfContext() ) {
3149 assert hrn.getAlphaNew().equals( rsetEmpty );
3151 hrn.applyAlphaNew();
3154 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3155 while( itrRes.hasNext() ) {
3156 res.add( itrRes.next() );
3162 Iterator<RefEdge> edgeItr = res.iterator();
3163 while( edgeItr.hasNext() ) {
3164 RefEdge edge = edgeItr.next();
3165 HeapRegionNode hrn = edge.getDst();
3167 // commit results of last phase
3168 if( edgesUpdated.contains( edge ) ) {
3169 edge.applyBetaNew();
3172 // compute intial condition of 2nd phase
3173 edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3179 // every edge in the graph is the initial workset
3180 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3181 while( !edgeWorkSet.isEmpty() ) {
3182 RefEdge edgePrime = edgeWorkSet.iterator().next();
3183 edgeWorkSet.remove( edgePrime );
3185 RefSrcNode rsn = edgePrime.getSrc();
3186 if( !(rsn instanceof HeapRegionNode) ) {
3189 HeapRegionNode hrn = (HeapRegionNode) rsn;
3191 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3192 while( itrEdge.hasNext() ) {
3193 RefEdge edge = itrEdge.next();
3195 ReachSet prevResult = edge.getBetaNew();
3196 assert prevResult != null;
3198 ReachSet intersection =
3199 Canonical.intersection( edge.getBeta(),
3200 edgePrime.getBetaNew()
3203 if( Canonical.unionORpreds( prevResult,
3210 Canonical.unionORpreds( prevResult,
3214 edgeWorkSet.add( edge );
3219 // commit beta' (beta<-betaNew)
3220 edgeItr = res.iterator();
3221 while( edgeItr.hasNext() ) {
3222 edgeItr.next().applyBetaNew();
3227 // a useful assertion for debugging:
3228 // every in-context tuple on any edge or
3229 // any node should name a node that is
3230 // part of the graph
3231 public boolean inContextTuplesInGraph() {
3233 Iterator hrnItr = id2hrn.entrySet().iterator();
3234 while( hrnItr.hasNext() ) {
3235 Map.Entry me = (Map.Entry) hrnItr.next();
3236 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3239 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3240 while( stateItr.hasNext() ) {
3241 ReachState state = stateItr.next();
3243 Iterator<ReachTuple> rtItr = state.iterator();
3244 while( rtItr.hasNext() ) {
3245 ReachTuple rt = rtItr.next();
3247 if( !rt.isOutOfContext() ) {
3248 if( !id2hrn.containsKey( rt.getHrnID() ) ) {
3249 System.out.println( rt.getHrnID()+" is missing" );
3257 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3258 while( edgeItr.hasNext() ) {
3259 RefEdge edge = edgeItr.next();
3261 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3262 while( stateItr.hasNext() ) {
3263 ReachState state = stateItr.next();
3265 Iterator<ReachTuple> rtItr = state.iterator();
3266 while( rtItr.hasNext() ) {
3267 ReachTuple rt = rtItr.next();
3269 if( !rt.isOutOfContext() ) {
3270 if( !id2hrn.containsKey( rt.getHrnID() ) ) {
3271 System.out.println( rt.getHrnID()+" is missing" );
3284 // another useful assertion for debugging
3285 public boolean noEmptyReachSetsInGraph() {
3287 Iterator hrnItr = id2hrn.entrySet().iterator();
3288 while( hrnItr.hasNext() ) {
3289 Map.Entry me = (Map.Entry) hrnItr.next();
3290 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3292 if( !hrn.isOutOfContext() &&
3294 hrn.getAlpha().isEmpty()
3296 System.out.println( "!!! "+hrn+" has an empty ReachSet !!!" );
3300 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3301 while( edgeItr.hasNext() ) {
3302 RefEdge edge = edgeItr.next();
3304 if( edge.getBeta().isEmpty() ) {
3305 System.out.println( "!!! "+edge+" has an empty ReachSet !!!" );
3315 public boolean everyReachStateWTrue() {
3317 Iterator hrnItr = id2hrn.entrySet().iterator();
3318 while( hrnItr.hasNext() ) {
3319 Map.Entry me = (Map.Entry) hrnItr.next();
3320 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3323 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3324 while( stateItr.hasNext() ) {
3325 ReachState state = stateItr.next();
3327 if( !state.getPreds().equals( predsTrue ) ) {
3333 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3334 while( edgeItr.hasNext() ) {
3335 RefEdge edge = edgeItr.next();
3337 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3338 while( stateItr.hasNext() ) {
3339 ReachState state = stateItr.next();
3341 if( !state.getPreds().equals( predsTrue ) ) {
3354 ////////////////////////////////////////////////////
3355 // in merge() and equals() methods the suffix A
3356 // represents the passed in graph and the suffix
3357 // B refers to the graph in this object
3358 // Merging means to take the incoming graph A and
3359 // merge it into B, so after the operation graph B
3360 // is the final result.
3361 ////////////////////////////////////////////////////
3362 protected void merge( ReachGraph rg ) {
3369 mergeRefEdges ( rg );
3370 mergeAllocSites( rg );
3373 protected void mergeNodes( ReachGraph rg ) {
3375 // start with heap region nodes
3376 Set sA = rg.id2hrn.entrySet();
3377 Iterator iA = sA.iterator();
3378 while( iA.hasNext() ) {
3379 Map.Entry meA = (Map.Entry) iA.next();
3380 Integer idA = (Integer) meA.getKey();
3381 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3383 // if this graph doesn't have a node the
3384 // incoming graph has, allocate it
3385 if( !id2hrn.containsKey( idA ) ) {
3386 HeapRegionNode hrnB = hrnA.copy();
3387 id2hrn.put( idA, hrnB );
3390 // otherwise this is a node present in both graphs
3391 // so make the new reachability set a union of the
3392 // nodes' reachability sets
3393 HeapRegionNode hrnB = id2hrn.get( idA );
3394 hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3399 hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3406 if( !hrnA.equals( hrnB ) ) {
3407 rg.writeGraph( "graphA" );
3408 this.writeGraph( "graphB" );
3409 throw new Error( "flagged not matching" );
3417 // now add any variable nodes that are in graph B but
3419 sA = rg.td2vn.entrySet();
3421 while( iA.hasNext() ) {
3422 Map.Entry meA = (Map.Entry) iA.next();
3423 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3424 VariableNode lnA = (VariableNode) meA.getValue();
3426 // if the variable doesn't exist in B, allocate and add it
3427 VariableNode lnB = getVariableNodeFromTemp( tdA );
3431 protected void mergeRefEdges( ReachGraph rg ) {
3433 // between heap regions
3434 Set sA = rg.id2hrn.entrySet();
3435 Iterator iA = sA.iterator();
3436 while( iA.hasNext() ) {
3437 Map.Entry meA = (Map.Entry) iA.next();
3438 Integer idA = (Integer) meA.getKey();
3439 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3441 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3442 while( heapRegionsItrA.hasNext() ) {
3443 RefEdge edgeA = heapRegionsItrA.next();
3444 HeapRegionNode hrnChildA = edgeA.getDst();
3445 Integer idChildA = hrnChildA.getID();
3447 // at this point we know an edge in graph A exists
3448 // idA -> idChildA, does this exist in B?
3449 assert id2hrn.containsKey( idA );
3450 HeapRegionNode hrnB = id2hrn.get( idA );
3451 RefEdge edgeToMerge = null;
3453 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3454 while( heapRegionsItrB.hasNext() &&
3455 edgeToMerge == null ) {
3457 RefEdge edgeB = heapRegionsItrB.next();
3458 HeapRegionNode hrnChildB = edgeB.getDst();
3459 Integer idChildB = hrnChildB.getID();
3461 // don't use the RefEdge.equals() here because
3462 // we're talking about existence between graphs,
3463 // not intragraph equal
3464 if( idChildB.equals( idChildA ) &&
3465 edgeB.typeAndFieldEquals( edgeA ) ) {
3467 edgeToMerge = edgeB;
3471 // if the edge from A was not found in B,
3473 if( edgeToMerge == null ) {
3474 assert id2hrn.containsKey( idChildA );
3475 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3476 edgeToMerge = edgeA.copy();
3477 edgeToMerge.setSrc( hrnB );
3478 edgeToMerge.setDst( hrnChildB );
3479 addRefEdge( hrnB, hrnChildB, edgeToMerge );
3481 // otherwise, the edge already existed in both graphs
3482 // so merge their reachability sets
3484 // just replace this beta set with the union
3485 assert edgeToMerge != null;
3486 edgeToMerge.setBeta(
3487 Canonical.unionORpreds( edgeToMerge.getBeta(),
3491 edgeToMerge.setPreds(
3492 Canonical.join( edgeToMerge.getPreds(),
3500 // and then again from variable nodes
3501 sA = rg.td2vn.entrySet();
3503 while( iA.hasNext() ) {
3504 Map.Entry meA = (Map.Entry) iA.next();
3505 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3506 VariableNode vnA = (VariableNode) meA.getValue();
3508 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3509 while( heapRegionsItrA.hasNext() ) {
3510 RefEdge edgeA = heapRegionsItrA.next();
3511 HeapRegionNode hrnChildA = edgeA.getDst();
3512 Integer idChildA = hrnChildA.getID();
3514 // at this point we know an edge in graph A exists
3515 // tdA -> idChildA, does this exist in B?
3516 assert td2vn.containsKey( tdA );
3517 VariableNode vnB = td2vn.get( tdA );
3518 RefEdge edgeToMerge = null;
3520 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3521 while( heapRegionsItrB.hasNext() &&
3522 edgeToMerge == null ) {
3524 RefEdge edgeB = heapRegionsItrB.next();
3525 HeapRegionNode hrnChildB = edgeB.getDst();
3526 Integer idChildB = hrnChildB.getID();
3528 // don't use the RefEdge.equals() here because
3529 // we're talking about existence between graphs
3530 if( idChildB.equals( idChildA ) &&
3531 edgeB.typeAndFieldEquals( edgeA ) ) {
3533 edgeToMerge = edgeB;
3537 // if the edge from A was not found in B,
3539 if( edgeToMerge == null ) {
3540 assert id2hrn.containsKey( idChildA );
3541 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3542 edgeToMerge = edgeA.copy();
3543 edgeToMerge.setSrc( vnB );
3544 edgeToMerge.setDst( hrnChildB );
3545 addRefEdge( vnB, hrnChildB, edgeToMerge );
3547 // otherwise, the edge already existed in both graphs
3548 // so merge their reachability sets
3550 // just replace this beta set with the union
3551 edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3555 edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3564 protected void mergeAllocSites( ReachGraph rg ) {
3565 allocSites.addAll( rg.allocSites );
3570 static boolean dbgEquals = false;
3573 // it is necessary in the equals() member functions
3574 // to "check both ways" when comparing the data
3575 // structures of two graphs. For instance, if all
3576 // edges between heap region nodes in graph A are
3577 // present and equal in graph B it is not sufficient
3578 // to say the graphs are equal. Consider that there
3579 // may be edges in graph B that are not in graph A.
3580 // the only way to know that all edges in both graphs
3581 // are equally present is to iterate over both data
3582 // structures and compare against the other graph.
3583 public boolean equals( ReachGraph rg ) {
3587 System.out.println( "rg is null" );
3592 if( !areHeapRegionNodesEqual( rg ) ) {
3594 System.out.println( "hrn not equal" );
3599 if( !areVariableNodesEqual( rg ) ) {
3601 System.out.println( "vars not equal" );
3606 if( !areRefEdgesEqual( rg ) ) {
3608 System.out.println( "edges not equal" );
3613 // if everything is equal up to this point,
3614 // assert that allocSites is also equal--
3615 // this data is redundant but kept for efficiency
3616 assert allocSites.equals( rg.allocSites );
3622 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3624 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3628 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3635 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3637 Set sA = rgA.id2hrn.entrySet();
3638 Iterator iA = sA.iterator();
3639 while( iA.hasNext() ) {
3640 Map.Entry meA = (Map.Entry) iA.next();
3641 Integer idA = (Integer) meA.getKey();
3642 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3644 if( !rgB.id2hrn.containsKey( idA ) ) {
3648 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3649 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3657 protected boolean areVariableNodesEqual( ReachGraph rg ) {
3659 if( !areallVNinAalsoinBandequal( this, rg ) ) {
3663 if( !areallVNinAalsoinBandequal( rg, this ) ) {
3670 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3672 Set sA = rgA.td2vn.entrySet();
3673 Iterator iA = sA.iterator();
3674 while( iA.hasNext() ) {
3675 Map.Entry meA = (Map.Entry) iA.next();
3676 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3678 if( !rgB.td2vn.containsKey( tdA ) ) {
3687 protected boolean areRefEdgesEqual( ReachGraph rg ) {
3688 if( !areallREinAandBequal( this, rg ) ) {
3692 if( !areallREinAandBequal( rg, this ) ) {
3699 static protected boolean areallREinAandBequal( ReachGraph rgA,
3702 // check all the heap region->heap region edges
3703 Set sA = rgA.id2hrn.entrySet();
3704 Iterator iA = sA.iterator();
3705 while( iA.hasNext() ) {
3706 Map.Entry meA = (Map.Entry) iA.next();
3707 Integer idA = (Integer) meA.getKey();
3708 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3710 // we should have already checked that the same
3711 // heap regions exist in both graphs
3712 assert rgB.id2hrn.containsKey( idA );
3714 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3718 // then check every edge in B for presence in A, starting
3719 // from the same parent HeapRegionNode
3720 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3722 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3727 // then check all the variable->heap region edges
3728 sA = rgA.td2vn.entrySet();
3730 while( iA.hasNext() ) {
3731 Map.Entry meA = (Map.Entry) iA.next();
3732 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3733 VariableNode vnA = (VariableNode) meA.getValue();
3735 // we should have already checked that the same
3736 // label nodes exist in both graphs
3737 assert rgB.td2vn.containsKey( tdA );
3739 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3743 // then check every edge in B for presence in A, starting
3744 // from the same parent VariableNode
3745 VariableNode vnB = rgB.td2vn.get( tdA );
3747 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3756 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3760 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3761 while( itrA.hasNext() ) {
3762 RefEdge edgeA = itrA.next();
3763 HeapRegionNode hrnChildA = edgeA.getDst();
3764 Integer idChildA = hrnChildA.getID();
3766 assert rgB.id2hrn.containsKey( idChildA );
3768 // at this point we know an edge in graph A exists
3769 // rnA -> idChildA, does this exact edge exist in B?
3770 boolean edgeFound = false;
3772 RefSrcNode rnB = null;
3773 if( rnA instanceof HeapRegionNode ) {
3774 HeapRegionNode hrnA = (HeapRegionNode) rnA;
3775 rnB = rgB.id2hrn.get( hrnA.getID() );
3777 VariableNode vnA = (VariableNode) rnA;
3778 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3781 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3782 while( itrB.hasNext() ) {
3783 RefEdge edgeB = itrB.next();
3784 HeapRegionNode hrnChildB = edgeB.getDst();
3785 Integer idChildB = hrnChildB.getID();
3787 if( idChildA.equals( idChildB ) &&
3788 edgeA.typeAndFieldEquals( edgeB ) ) {
3790 // there is an edge in the right place with the right field,
3791 // but do they have the same attributes?
3792 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3793 edgeA.equalsPreds( edgeB )
3809 // can be used to assert monotonicity
3810 static public boolean isNoSmallerThan( ReachGraph rgA,
3813 //System.out.println( "*** Asking if A is no smaller than B ***" );
3816 Iterator iA = rgA.id2hrn.entrySet().iterator();
3817 while( iA.hasNext() ) {
3818 Map.Entry meA = (Map.Entry) iA.next();
3819 Integer idA = (Integer) meA.getKey();
3820 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3822 if( !rgB.id2hrn.containsKey( idA ) ) {
3823 System.out.println( " regions smaller" );
3827 //HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3828 /* NOT EQUALS, NO SMALLER THAN!
3829 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3830 System.out.println( " regions smaller" );
3836 // this works just fine, no smaller than
3837 if( !areallVNinAalsoinBandequal( rgA, rgB ) ) {
3838 System.out.println( " vars smaller:" );
3839 System.out.println( " A:"+rgA.td2vn.keySet() );
3840 System.out.println( " B:"+rgB.td2vn.keySet() );
3845 iA = rgA.id2hrn.entrySet().iterator();
3846 while( iA.hasNext() ) {
3847 Map.Entry meA = (Map.Entry) iA.next();
3848 Integer idA = (Integer) meA.getKey();
3849 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3851 Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
3852 while( reItr.hasNext() ) {
3853 RefEdge edgeA = reItr.next();
3854 RefSrcNode rsnA = edgeA.getSrc();
3856 // we already checked that nodes were present
3857 HeapRegionNode hrnB = rgB.id2hrn.get( hrnA.getID() );
3858 assert hrnB != null;
3861 if( rsnA instanceof VariableNode ) {
3862 VariableNode vnA = (VariableNode) rsnA;
3863 rsnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3866 HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
3867 rsnB = rgB.id2hrn.get( hrnSrcA.getID() );
3869 assert rsnB != null;
3871 RefEdge edgeB = rsnB.getReferenceTo( hrnB,
3875 if( edgeB == null ) {
3876 System.out.println( " edges smaller:" );
3880 // REMEMBER, IS NO SMALLER THAN
3882 System.out.println( " edges smaller" );
3898 // this analysis no longer has the "match anything"
3899 // type which was represented by null
3900 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3901 TypeDescriptor td2 ) {
3905 if( td1.isNull() ) {
3908 if( td2.isNull() ) {
3911 return typeUtil.mostSpecific( td1, td2 );
3914 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3916 TypeDescriptor td3 ) {
3918 return mostSpecificType( td1,
3919 mostSpecificType( td2, td3 )
3923 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3926 TypeDescriptor td4 ) {
3928 return mostSpecificType( mostSpecificType( td1, td2 ),
3929 mostSpecificType( td3, td4 )
3933 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3934 TypeDescriptor possibleChild ) {
3935 assert possibleSuper != null;
3936 assert possibleChild != null;
3938 if( possibleSuper.isNull() ||
3939 possibleChild.isNull() ) {
3943 return typeUtil.isSuperorType( possibleSuper, possibleChild );
3947 protected boolean hasMatchingField( HeapRegionNode src,
3950 TypeDescriptor tdSrc = src.getType();
3951 assert tdSrc != null;
3953 if( tdSrc.isArray() ) {
3954 TypeDescriptor td = edge.getType();
3957 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3958 assert tdSrcDeref != null;
3960 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3964 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3967 // if it's not a class, it doesn't have any fields to match
3968 if( !tdSrc.isClass() ) {
3972 ClassDescriptor cd = tdSrc.getClassDesc();
3973 while( cd != null ) {
3974 Iterator fieldItr = cd.getFields();
3976 while( fieldItr.hasNext() ) {
3977 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3979 if( fd.getType().equals( edge.getType() ) &&
3980 fd.getSymbol().equals( edge.getField() ) ) {
3985 cd = cd.getSuperDesc();
3988 // otherwise it is a class with fields
3989 // but we didn't find a match
3993 protected boolean hasMatchingType( RefEdge edge,
3994 HeapRegionNode dst ) {
3996 // if the region has no type, matches everything
3997 TypeDescriptor tdDst = dst.getType();
3998 assert tdDst != null;
4000 // if the type is not a class or an array, don't
4001 // match because primitives are copied, no aliases
4002 ClassDescriptor cdDst = tdDst.getClassDesc();
4003 if( cdDst == null && !tdDst.isArray() ) {
4007 // if the edge type is null, it matches everything
4008 TypeDescriptor tdEdge = edge.getType();
4009 assert tdEdge != null;
4011 return typeUtil.isSuperorType( tdEdge, tdDst );
4016 // the default signature for quick-and-dirty debugging
4017 public void writeGraph( String graphName ) {
4018 writeGraph( graphName,
4019 true, // write labels
4020 true, // label select
4021 true, // prune garbage
4022 true, // hide subset reachability
4023 true, // hide edge taints
4024 null // in-context boundary
4028 public void writeGraph( String graphName,
4029 boolean writeLabels,
4030 boolean labelSelect,
4031 boolean pruneGarbage,
4032 boolean hideSubsetReachability,
4033 boolean hideEdgeTaints
4035 writeGraph( graphName,
4039 hideSubsetReachability,
4044 public void writeGraph( String graphName,
4045 boolean writeLabels,
4046 boolean labelSelect,
4047 boolean pruneGarbage,
4048 boolean hideSubsetReachability,
4049 boolean hideEdgeTaints,
4050 Set<Integer> callerNodeIDsCopiedToCallee
4054 // remove all non-word characters from the graph name so
4055 // the filename and identifier in dot don't cause errors
4056 graphName = graphName.replaceAll( "[\\W]", "" );
4059 new BufferedWriter( new FileWriter( graphName+".dot" ) );
4061 bw.write( "digraph "+graphName+" {\n" );
4064 // this is an optional step to form the callee-reachable
4065 // "cut-out" into a DOT cluster for visualization
4066 if( callerNodeIDsCopiedToCallee != null ) {
4068 bw.write( " subgraph cluster0 {\n" );
4069 bw.write( " color=blue;\n" );
4071 Iterator i = id2hrn.entrySet().iterator();
4072 while( i.hasNext() ) {
4073 Map.Entry me = (Map.Entry) i.next();
4074 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4076 if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
4077 bw.write( " "+hrn.toString()+
4078 hrn.toStringDOT( hideSubsetReachability )+
4088 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4090 // then visit every heap region node
4091 Iterator i = id2hrn.entrySet().iterator();
4092 while( i.hasNext() ) {
4093 Map.Entry me = (Map.Entry) i.next();
4094 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4096 // only visit nodes worth writing out--for instance
4097 // not every node at an allocation is referenced
4098 // (think of it as garbage-collected), etc.
4099 if( !pruneGarbage ||
4100 hrn.isOutOfContext() ||
4101 (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4104 if( !visited.contains( hrn ) ) {
4105 traverseHeapRegionNodes( hrn,
4109 hideSubsetReachability,
4111 callerNodeIDsCopiedToCallee );
4116 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
4119 // then visit every label node, useful for debugging
4121 i = td2vn.entrySet().iterator();
4122 while( i.hasNext() ) {
4123 Map.Entry me = (Map.Entry) i.next();
4124 VariableNode vn = (VariableNode) me.getValue();
4127 String labelStr = vn.getTempDescriptorString();
4128 if( labelStr.startsWith( "___temp" ) ||
4129 labelStr.startsWith( "___dst" ) ||
4130 labelStr.startsWith( "___srctmp" ) ||
4131 labelStr.startsWith( "___neverused" )
4137 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4138 while( heapRegionsItr.hasNext() ) {
4139 RefEdge edge = heapRegionsItr.next();
4140 HeapRegionNode hrn = edge.getDst();
4142 if( !visited.contains( hrn ) ) {
4143 traverseHeapRegionNodes( hrn,
4147 hideSubsetReachability,
4149 callerNodeIDsCopiedToCallee );
4152 bw.write( " "+vn.toString()+
4153 " -> "+hrn.toString()+
4154 edge.toStringDOT( hideSubsetReachability, "" )+
4163 } catch( IOException e ) {
4164 throw new Error( "Error writing out DOT graph "+graphName );
4168 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
4171 Set<HeapRegionNode> visited,
4172 boolean hideSubsetReachability,
4173 boolean hideEdgeTaints,
4174 Set<Integer> callerNodeIDsCopiedToCallee
4175 ) throws java.io.IOException {
4177 if( visited.contains( hrn ) ) {
4182 // if we're drawing the callee-view subgraph, only
4183 // write out the node info if it hasn't already been
4185 if( callerNodeIDsCopiedToCallee == null ||
4186 !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
4188 bw.write( " "+hrn.toString()+
4189 hrn.toStringDOT( hideSubsetReachability )+
4193 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4194 while( childRegionsItr.hasNext() ) {
4195 RefEdge edge = childRegionsItr.next();
4196 HeapRegionNode hrnChild = edge.getDst();
4198 if( callerNodeIDsCopiedToCallee != null &&
4199 (edge.getSrc() instanceof HeapRegionNode) ) {
4200 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4201 if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
4202 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4204 bw.write( " "+hrn.toString()+
4205 " -> "+hrnChild.toString()+
4206 edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
4208 } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
4209 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4211 bw.write( " "+hrn.toString()+
4212 " -> "+hrnChild.toString()+
4213 edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
4216 bw.write( " "+hrn.toString()+
4217 " -> "+hrnChild.toString()+
4218 edge.toStringDOT( hideSubsetReachability, "" )+
4222 bw.write( " "+hrn.toString()+
4223 " -> "+hrnChild.toString()+
4224 edge.toStringDOT( hideSubsetReachability, "" )+
4228 traverseHeapRegionNodes( hrnChild,
4232 hideSubsetReachability,
4234 callerNodeIDsCopiedToCallee );
4242 public Set<HeapRegionNode> findCommonReachableNodes( ReachSet proofOfSharing ) {
4244 Set<HeapRegionNode> exhibitProofState =
4245 new HashSet<HeapRegionNode>();
4247 Iterator hrnItr = id2hrn.entrySet().iterator();
4248 while( hrnItr.hasNext() ) {
4249 Map.Entry me = (Map.Entry) hrnItr.next();
4250 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4252 ReachSet intersection =
4253 Canonical.intersection( proofOfSharing,
4256 if( !intersection.isEmpty() ) {
4257 assert !hrn.isOutOfContext();
4258 exhibitProofState.add( hrn );
4262 return exhibitProofState;
4266 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4267 HeapRegionNode hrn2) {
4268 assert hrn1 != null;
4269 assert hrn2 != null;
4271 assert !hrn1.isOutOfContext();
4272 assert !hrn2.isOutOfContext();
4274 assert belongsToThis( hrn1 );
4275 assert belongsToThis( hrn2 );
4277 assert !hrn1.getID().equals( hrn2.getID() );
4280 // then get the various tokens for these heap regions
4282 ReachTuple.factory( hrn1.getID(),
4283 !hrn1.isSingleObject(), // multi?
4284 ReachTuple.ARITY_ONE,
4287 ReachTuple h1star = null;
4288 if( !hrn1.isSingleObject() ) {
4290 ReachTuple.factory( hrn1.getID(),
4291 !hrn1.isSingleObject(),
4292 ReachTuple.ARITY_ZEROORMORE,
4297 ReachTuple.factory( hrn2.getID(),
4298 !hrn2.isSingleObject(),
4299 ReachTuple.ARITY_ONE,
4302 ReachTuple h2star = null;
4303 if( !hrn2.isSingleObject() ) {
4305 ReachTuple.factory( hrn2.getID(),
4306 !hrn2.isSingleObject(),
4307 ReachTuple.ARITY_ZEROORMORE,
4311 // then get the merged beta of all out-going edges from these heap
4314 ReachSet beta1 = ReachSet.factory();
4315 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4316 while (itrEdge.hasNext()) {
4317 RefEdge edge = itrEdge.next();
4318 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4321 ReachSet beta2 = ReachSet.factory();
4322 itrEdge = hrn2.iteratorToReferencees();
4323 while (itrEdge.hasNext()) {
4324 RefEdge edge = itrEdge.next();
4325 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4328 ReachSet proofOfSharing = ReachSet.factory();
4331 Canonical.unionORpreds( proofOfSharing,
4332 beta1.getStatesWithBoth( h1, h2 )
4335 Canonical.unionORpreds( proofOfSharing,
4336 beta2.getStatesWithBoth( h1, h2 )
4339 if( !hrn1.isSingleObject() ) {
4341 Canonical.unionORpreds( proofOfSharing,
4342 beta1.getStatesWithBoth( h1star, h2 )
4345 Canonical.unionORpreds( proofOfSharing,
4346 beta2.getStatesWithBoth( h1star, h2 )
4350 if( !hrn2.isSingleObject() ) {
4352 Canonical.unionORpreds( proofOfSharing,
4353 beta1.getStatesWithBoth( h1, h2star )
4356 Canonical.unionORpreds( proofOfSharing,
4357 beta2.getStatesWithBoth( h1, h2star )
4361 if( !hrn1.isSingleObject() &&
4362 !hrn2.isSingleObject()
4365 Canonical.unionORpreds( proofOfSharing,
4366 beta1.getStatesWithBoth( h1star, h2star )
4369 Canonical.unionORpreds( proofOfSharing,
4370 beta2.getStatesWithBoth( h1star, h2star )
4374 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4375 if( !proofOfSharing.isEmpty() ) {
4376 common = findCommonReachableNodes( proofOfSharing );
4377 if( !DISABLE_STRONG_UPDATES &&
4378 !DISABLE_GLOBAL_SWEEP
4380 assert !common.isEmpty();
4387 // this version of the above method checks whether there is sharing
4388 // among the objects in a summary node
4389 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4391 assert hrn.isNewSummary();
4392 assert !hrn.isOutOfContext();
4393 assert belongsToThis( hrn );
4396 ReachTuple.factory( hrn.getID(),
4398 ReachTuple.ARITY_ZEROORMORE,
4401 // then get the merged beta of all out-going edges from
4404 ReachSet beta = ReachSet.factory();
4405 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4406 while (itrEdge.hasNext()) {
4407 RefEdge edge = itrEdge.next();
4408 beta = Canonical.unionORpreds(beta, edge.getBeta());
4411 ReachSet proofOfSharing = ReachSet.factory();
4414 Canonical.unionORpreds( proofOfSharing,
4415 beta.getStatesWithBoth( hstar, hstar )
4418 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4419 if( !proofOfSharing.isEmpty() ) {
4420 common = findCommonReachableNodes( proofOfSharing );
4421 if( !DISABLE_STRONG_UPDATES &&
4422 !DISABLE_GLOBAL_SWEEP
4424 assert !common.isEmpty();
4432 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4433 Integer paramIndex1,
4434 Integer paramIndex2) {
4436 // get parameter's heap regions
4437 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4438 assert this.hasVariable( paramTemp1 );
4439 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
4442 if( !(paramVar1.getNumReferencees() == 1) ) {
4443 System.out.println( "\n fm="+fm+"\n param="+paramTemp1 );
4444 writeGraph( "whatup" );
4448 assert paramVar1.getNumReferencees() == 1;
4449 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
4450 HeapRegionNode hrnParam1 = paramEdge1.getDst();
4452 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4453 assert this.hasVariable( paramTemp2 );
4454 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
4456 if( !(paramVar2.getNumReferencees() == 1) ) {
4457 System.out.println( "\n fm="+fm+"\n param="+paramTemp2 );
4458 writeGraph( "whatup" );
4461 assert paramVar2.getNumReferencees() == 1;
4462 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
4463 HeapRegionNode hrnParam2 = paramEdge2.getDst();
4465 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4466 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4471 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4475 // get parameter's heap regions
4476 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4477 assert this.hasVariable( paramTemp );
4478 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
4479 assert paramVar.getNumReferencees() == 1;
4480 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
4481 HeapRegionNode hrnParam = paramEdge.getDst();
4484 HeapRegionNode hrnSummary=null;
4485 if(id2hrn.containsKey(as.getSummary())){
4486 // if summary node doesn't exist, ignore this case
4487 hrnSummary = id2hrn.get(as.getSummary());
4488 assert hrnSummary != null;
4491 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4492 if(hrnSummary!=null){
4493 common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4496 // check for other nodes
4497 for (int i = 0; i < as.getAllocationDepth(); ++i) {
4499 assert id2hrn.containsKey(as.getIthOldest(i));
4500 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4501 assert hrnIthOldest != null;
4503 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4510 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4513 // get summary node 1's alpha
4514 Integer idSum1 = as1.getSummary();
4515 HeapRegionNode hrnSum1=null;
4516 if(id2hrn.containsKey(idSum1)){
4517 hrnSum1 = id2hrn.get(idSum1);
4520 // get summary node 2's alpha
4521 Integer idSum2 = as2.getSummary();
4522 HeapRegionNode hrnSum2=null;
4523 if(id2hrn.containsKey(idSum2)){
4524 hrnSum2 = id2hrn.get(idSum2);
4527 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4528 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2){
4529 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4533 // ask if objects from this summary share among each other
4534 common.addAll(mayReachSharedObjects(hrnSum1));
4537 // check sum2 against alloc1 nodes
4539 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4540 Integer idI1 = as1.getIthOldest(i);
4541 assert id2hrn.containsKey(idI1);
4542 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4543 assert hrnI1 != null;
4544 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4547 // also ask if objects from this summary share among each other
4548 common.addAll(mayReachSharedObjects(hrnSum2));
4551 // check sum1 against alloc2 nodes
4552 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4553 Integer idI2 = as2.getIthOldest(i);
4554 assert id2hrn.containsKey(idI2);
4555 HeapRegionNode hrnI2 = id2hrn.get(idI2);
4556 assert hrnI2 != null;
4559 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4562 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4563 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4564 Integer idI1 = as1.getIthOldest(j);
4566 // if these are the same site, don't look for the same token, no
4568 // different tokens of the same site could alias together though
4569 if (idI1.equals(idI2)) {
4573 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4575 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));