1 package Analysis.Disjoint;
5 import Util.UtilAlgorithms;
9 public class ReachGraph {
11 // use to disable improvements for comparison
12 protected static final boolean DISABLE_STRONG_UPDATES = false;
13 protected static final boolean DISABLE_GLOBAL_SWEEP = false;
15 // a special out-of-scope temp
16 protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
18 // some frequently used reachability constants
19 protected static final ReachState rstateEmpty = ReachState.factory();
20 protected static final ReachSet rsetEmpty = ReachSet.factory();
21 protected static final ReachSet rsetWithEmptyState = ReachSet.factory( rstateEmpty );
23 // predicate constants
24 protected static final ExistPred predTrue = ExistPred.factory(); // if no args, true
25 protected static final ExistPredSet predsEmpty = ExistPredSet.factory();
26 protected static final ExistPredSet predsTrue = ExistPredSet.factory( predTrue );
29 // from DisjointAnalysis for convenience
30 protected static int allocationDepth = -1;
31 protected static TypeUtil typeUtil = null;
34 // variable and heap region nodes indexed by unique ID
35 public Hashtable<Integer, HeapRegionNode> id2hrn;
36 public Hashtable<TempDescriptor, VariableNode > td2vn;
38 // convenient set of alloc sites for all heap regions
39 // present in the graph without having to search
40 public HashSet<AllocSite> allocSites;
43 id2hrn = new Hashtable<Integer, HeapRegionNode>();
44 td2vn = new Hashtable<TempDescriptor, VariableNode >();
45 allocSites = new HashSet<AllocSite>();
49 // temp descriptors are globally unique and map to
50 // exactly one variable node, easy
51 protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
54 if( !td2vn.containsKey( td ) ) {
55 td2vn.put( td, new VariableNode( td ) );
58 return td2vn.get( td );
61 public boolean hasVariable( TempDescriptor td ) {
62 return td2vn.containsKey( td );
66 // this suite of methods can be used to assert a
67 // very important property of ReachGraph objects:
68 // some element, HeapRegionNode, RefEdge etc.
69 // should be referenced by at most ONE ReachGraph!!
70 // If a heap region or edge or variable should be
71 // in another graph, make a new object with
72 // equivalent properties for a new graph
73 public boolean belongsToThis( RefSrcNode rsn ) {
74 if( rsn instanceof VariableNode ) {
75 VariableNode vn = (VariableNode) rsn;
76 return this.td2vn.get( vn.getTempDescriptor() ) == vn;
78 HeapRegionNode hrn = (HeapRegionNode) rsn;
79 return this.id2hrn.get( hrn.getID() ) == hrn;
84 // the reason for this method is to have the option
85 // of creating new heap regions with specific IDs, or
86 // duplicating heap regions with specific IDs (especially
87 // in the merge() operation) or to create new heap
88 // regions with a new unique ID
89 protected HeapRegionNode
90 createNewHeapRegionNode( Integer id,
91 boolean isSingleObject,
94 boolean isOutOfContext,
103 boolean markForAnalysis = isFlagged;
105 TypeDescriptor typeToUse = null;
106 if( allocSite != null ) {
107 typeToUse = allocSite.getType();
108 allocSites.add( allocSite );
113 if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
114 markForAnalysis = true;
118 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
121 if( inherent == null ) {
122 if( markForAnalysis ) {
126 ReachTuple.factory( id,
128 ReachTuple.ARITY_ONE,
129 false // out-of-context
134 inherent = rsetWithEmptyState;
138 if( alpha == null ) {
142 if( preds == null ) {
143 // TODO: do this right? For out-of-context nodes?
144 preds = ExistPredSet.factory();
147 HeapRegionNode hrn = new HeapRegionNode( id,
158 id2hrn.put( id, hrn );
164 ////////////////////////////////////////////////
166 // Low-level referencee and referencer methods
168 // These methods provide the lowest level for
169 // creating references between reachability nodes
170 // and handling the details of maintaining both
171 // list of referencers and referencees.
173 ////////////////////////////////////////////////
174 protected void addRefEdge( RefSrcNode referencer,
175 HeapRegionNode referencee,
177 assert referencer != null;
178 assert referencee != null;
180 assert edge.getSrc() == referencer;
181 assert edge.getDst() == referencee;
182 assert belongsToThis( referencer );
183 assert belongsToThis( referencee );
185 // edges are getting added twice to graphs now, the
186 // kind that should have abstract facts merged--use
187 // this check to prevent that
188 assert referencer.getReferenceTo( referencee,
193 referencer.addReferencee( edge );
194 referencee.addReferencer( edge );
197 protected void removeRefEdge( RefEdge e ) {
198 removeRefEdge( e.getSrc(),
204 protected void removeRefEdge( RefSrcNode referencer,
205 HeapRegionNode referencee,
208 assert referencer != null;
209 assert referencee != null;
211 RefEdge edge = referencer.getReferenceTo( referencee,
215 assert edge == referencee.getReferenceFrom( referencer,
219 referencer.removeReferencee( edge );
220 referencee.removeReferencer( edge );
223 protected void clearRefEdgesFrom( RefSrcNode referencer,
226 boolean removeAll ) {
227 assert referencer != null;
229 // get a copy of the set to iterate over, otherwise
230 // we will be trying to take apart the set as we
231 // are iterating over it, which won't work
232 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
233 while( i.hasNext() ) {
234 RefEdge edge = i.next();
237 (edge.typeEquals( type ) && edge.fieldEquals( field ))
240 HeapRegionNode referencee = edge.getDst();
242 removeRefEdge( referencer,
250 protected void clearRefEdgesTo( HeapRegionNode referencee,
253 boolean removeAll ) {
254 assert referencee != null;
256 // get a copy of the set to iterate over, otherwise
257 // we will be trying to take apart the set as we
258 // are iterating over it, which won't work
259 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
260 while( i.hasNext() ) {
261 RefEdge edge = i.next();
264 (edge.typeEquals( type ) && edge.fieldEquals( field ))
267 RefSrcNode referencer = edge.getSrc();
269 removeRefEdge( referencer,
277 protected void clearNonVarRefEdgesTo( HeapRegionNode referencee ) {
278 assert referencee != null;
280 // get a copy of the set to iterate over, otherwise
281 // we will be trying to take apart the set as we
282 // are iterating over it, which won't work
283 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
284 while( i.hasNext() ) {
285 RefEdge edge = i.next();
286 RefSrcNode referencer = edge.getSrc();
287 if( !(referencer instanceof VariableNode) ) {
288 removeRefEdge( referencer,
297 ////////////////////////////////////////////////////
299 // Assignment Operation Methods
301 // These methods are high-level operations for
302 // modeling program assignment statements using
303 // the low-level reference create/remove methods
306 ////////////////////////////////////////////////////
308 public void assignTempXEqualToTempY( TempDescriptor x,
310 assignTempXEqualToCastedTempY( x, y, null );
313 public void assignTempXEqualToCastedTempY( TempDescriptor x,
315 TypeDescriptor tdCast ) {
317 VariableNode lnX = getVariableNodeFromTemp( x );
318 VariableNode lnY = getVariableNodeFromTemp( y );
320 clearRefEdgesFrom( lnX, null, null, true );
322 // note it is possible that the types of temps in the
323 // flat node to analyze will reveal that some typed
324 // edges in the reachability graph are impossible
325 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
327 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
328 while( itrYhrn.hasNext() ) {
329 RefEdge edgeY = itrYhrn.next();
330 HeapRegionNode referencee = edgeY.getDst();
331 RefEdge edgeNew = edgeY.copy();
333 if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
334 impossibleEdges.add( edgeY );
338 edgeNew.setSrc( lnX );
340 if( tdCast == null ) {
341 edgeNew.setType( mostSpecificType( y.getType(),
347 edgeNew.setType( mostSpecificType( y.getType(),
349 referencee.getType(),
355 edgeNew.setField( null );
357 addRefEdge( lnX, referencee, edgeNew );
360 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
361 while( itrImp.hasNext() ) {
362 RefEdge edgeImp = itrImp.next();
363 removeRefEdge( edgeImp );
368 public void assignTempXEqualToTempYFieldF( TempDescriptor x,
370 FieldDescriptor f ) {
371 VariableNode lnX = getVariableNodeFromTemp( x );
372 VariableNode lnY = getVariableNodeFromTemp( y );
374 clearRefEdgesFrom( lnX, null, null, true );
376 // note it is possible that the types of temps in the
377 // flat node to analyze will reveal that some typed
378 // edges in the reachability graph are impossible
379 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
381 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
382 while( itrYhrn.hasNext() ) {
383 RefEdge edgeY = itrYhrn.next();
384 HeapRegionNode hrnY = edgeY.getDst();
385 ReachSet betaY = edgeY.getBeta();
387 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
388 while( itrHrnFhrn.hasNext() ) {
389 RefEdge edgeHrn = itrHrnFhrn.next();
390 HeapRegionNode hrnHrn = edgeHrn.getDst();
391 ReachSet betaHrn = edgeHrn.getBeta();
393 // prune edges that are not a matching field
394 if( edgeHrn.getType() != null &&
395 !edgeHrn.getField().equals( f.getSymbol() )
400 // check for impossible edges
401 if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
402 impossibleEdges.add( edgeHrn );
406 TypeDescriptor tdNewEdge =
407 mostSpecificType( edgeHrn.getType(),
411 RefEdge edgeNew = new RefEdge( lnX,
415 Canonical.intersection( betaY, betaHrn ),
419 addRefEdge( lnX, hrnHrn, edgeNew );
423 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
424 while( itrImp.hasNext() ) {
425 RefEdge edgeImp = itrImp.next();
426 removeRefEdge( edgeImp );
429 // anytime you might remove edges between heap regions
430 // you must global sweep to clean up broken reachability
431 if( !impossibleEdges.isEmpty() ) {
432 if( !DISABLE_GLOBAL_SWEEP ) {
439 public void assignTempXFieldFEqualToTempY( TempDescriptor x,
443 VariableNode lnX = getVariableNodeFromTemp( x );
444 VariableNode lnY = getVariableNodeFromTemp( y );
446 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
447 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
449 // note it is possible that the types of temps in the
450 // flat node to analyze will reveal that some typed
451 // edges in the reachability graph are impossible
452 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
454 // first look for possible strong updates and remove those edges
455 boolean strongUpdate = false;
457 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
458 while( itrXhrn.hasNext() ) {
459 RefEdge edgeX = itrXhrn.next();
460 HeapRegionNode hrnX = edgeX.getDst();
462 // we can do a strong update here if one of two cases holds
464 f != DisjointAnalysis.getArrayField( f.getType() ) &&
465 ( (hrnX.getNumReferencers() == 1) || // case 1
466 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
469 if( !DISABLE_STRONG_UPDATES ) {
471 clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
476 // then do all token propagation
477 itrXhrn = lnX.iteratorToReferencees();
478 while( itrXhrn.hasNext() ) {
479 RefEdge edgeX = itrXhrn.next();
480 HeapRegionNode hrnX = edgeX.getDst();
481 ReachSet betaX = edgeX.getBeta();
482 ReachSet R = Canonical.intersection( hrnX.getAlpha(),
486 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
487 while( itrYhrn.hasNext() ) {
488 RefEdge edgeY = itrYhrn.next();
489 HeapRegionNode hrnY = edgeY.getDst();
490 ReachSet O = edgeY.getBeta();
492 // check for impossible edges
493 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
494 impossibleEdges.add( edgeY );
498 // propagate tokens over nodes starting from hrnSrc, and it will
499 // take care of propagating back up edges from any touched nodes
500 ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
501 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
503 // then propagate back just up the edges from hrn
504 ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
505 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
507 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
508 new Hashtable<RefEdge, ChangeSet>();
510 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
511 while( referItr.hasNext() ) {
512 RefEdge edgeUpstream = referItr.next();
513 todoEdges.add( edgeUpstream );
514 edgePlannedChanges.put( edgeUpstream, Cx );
517 propagateTokensOverEdges( todoEdges,
524 // apply the updates to reachability
525 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
526 while( nodeItr.hasNext() ) {
527 nodeItr.next().applyAlphaNew();
530 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
531 while( edgeItr.hasNext() ) {
532 edgeItr.next().applyBetaNew();
536 // then go back through and add the new edges
537 itrXhrn = lnX.iteratorToReferencees();
538 while( itrXhrn.hasNext() ) {
539 RefEdge edgeX = itrXhrn.next();
540 HeapRegionNode hrnX = edgeX.getDst();
542 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
543 while( itrYhrn.hasNext() ) {
544 RefEdge edgeY = itrYhrn.next();
545 HeapRegionNode hrnY = edgeY.getDst();
547 // skip impossible edges here, we already marked them
548 // when computing reachability propagations above
549 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
553 // prepare the new reference edge hrnX.f -> hrnY
554 TypeDescriptor tdNewEdge =
555 mostSpecificType( y.getType(),
560 RefEdge edgeNew = new RefEdge( hrnX,
564 Canonical.pruneBy( edgeY.getBeta(),
570 // look to see if an edge with same field exists
571 // and merge with it, otherwise just add the edge
572 RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
576 if( edgeExisting != null ) {
577 edgeExisting.setBeta(
578 Canonical.union( edgeExisting.getBeta(),
582 edgeExisting.setPreds(
583 Canonical.join( edgeExisting.getPreds(),
589 addRefEdge( hrnX, hrnY, edgeNew );
594 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
595 while( itrImp.hasNext() ) {
596 RefEdge edgeImp = itrImp.next();
597 removeRefEdge( edgeImp );
600 // if there was a strong update, make sure to improve
601 // reachability with a global sweep
602 if( strongUpdate || !impossibleEdges.isEmpty() ) {
603 if( !DISABLE_GLOBAL_SWEEP ) {
610 public void assignReturnEqualToTemp( TempDescriptor x ) {
612 VariableNode lnR = getVariableNodeFromTemp( tdReturn );
613 VariableNode lnX = getVariableNodeFromTemp( x );
615 clearRefEdgesFrom( lnR, null, null, true );
617 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
618 while( itrXhrn.hasNext() ) {
619 RefEdge edgeX = itrXhrn.next();
620 HeapRegionNode referencee = edgeX.getDst();
621 RefEdge edgeNew = edgeX.copy();
622 edgeNew.setSrc( lnR );
624 addRefEdge( lnR, referencee, edgeNew );
629 public void assignTempEqualToNewAlloc( TempDescriptor x,
636 // after the age operation the newest (or zero-ith oldest)
637 // node associated with the allocation site should have
638 // no references to it as if it were a newly allocated
640 Integer idNewest = as.getIthOldest( 0 );
641 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
642 assert hrnNewest != null;
644 VariableNode lnX = getVariableNodeFromTemp( x );
645 clearRefEdgesFrom( lnX, null, null, true );
647 // make a new reference to allocated node
648 TypeDescriptor type = as.getType();
651 new RefEdge( lnX, // source
655 hrnNewest.getAlpha(), // beta
656 predsTrue // predicates
659 addRefEdge( lnX, hrnNewest, edgeNew );
663 // use the allocation site (unique to entire analysis) to
664 // locate the heap region nodes in this reachability graph
665 // that should be aged. The process models the allocation
666 // of new objects and collects all the oldest allocations
667 // in a summary node to allow for a finite analysis
669 // There is an additional property of this method. After
670 // running it on a particular reachability graph (many graphs
671 // may have heap regions related to the same allocation site)
672 // the heap region node objects in this reachability graph will be
673 // allocated. Therefore, after aging a graph for an allocation
674 // site, attempts to retrieve the heap region nodes using the
675 // integer id's contained in the allocation site should always
676 // return non-null heap regions.
677 public void age( AllocSite as ) {
679 // keep track of allocation sites that are represented
680 // in this graph for efficiency with other operations
681 allocSites.add( as );
683 // if there is a k-th oldest node, it merges into
685 Integer idK = as.getOldest();
686 if( id2hrn.containsKey( idK ) ) {
687 HeapRegionNode hrnK = id2hrn.get( idK );
689 // retrieve the summary node, or make it
691 HeapRegionNode hrnSummary = getSummaryNode( as, false );
693 mergeIntoSummary( hrnK, hrnSummary );
696 // move down the line of heap region nodes
697 // clobbering the ith and transferring all references
698 // to and from i-1 to node i.
699 for( int i = allocationDepth - 1; i > 0; --i ) {
701 // only do the transfer if the i-1 node exists
702 Integer idImin1th = as.getIthOldest( i - 1 );
703 if( id2hrn.containsKey( idImin1th ) ) {
704 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
705 if( hrnImin1.isWiped() ) {
706 // there is no info on this node, just skip
710 // either retrieve or make target of transfer
711 HeapRegionNode hrnI = getIthNode( as, i, false );
713 transferOnto( hrnImin1, hrnI );
718 // as stated above, the newest node should have had its
719 // references moved over to the second oldest, so we wipe newest
720 // in preparation for being the new object to assign something to
721 HeapRegionNode hrn0 = getIthNode( as, 0, false );
722 wipeOut( hrn0, true );
724 // now tokens in reachability sets need to "age" also
725 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
726 while( itrAllVariableNodes.hasNext() ) {
727 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
728 VariableNode ln = (VariableNode) me.getValue();
730 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
731 while( itrEdges.hasNext() ) {
732 ageTuplesFrom( as, itrEdges.next() );
736 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
737 while( itrAllHRNodes.hasNext() ) {
738 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
739 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
741 ageTuplesFrom( as, hrnToAge );
743 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
744 while( itrEdges.hasNext() ) {
745 ageTuplesFrom( as, itrEdges.next() );
750 // after tokens have been aged, reset newest node's reachability
751 // and a brand new node has a "true" predicate
752 hrn0.setAlpha( hrn0.getInherent() );
753 hrn0.setPreds( predsTrue );
757 // either retrieve or create the needed heap region node
758 protected HeapRegionNode getSummaryNode( AllocSite as,
763 idSummary = as.getSummaryShadow();
765 idSummary = as.getSummary();
768 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
770 if( hrnSummary == null ) {
772 boolean hasFlags = false;
773 if( as.getType().isClass() ) {
774 hasFlags = as.getType().getClassDesc().hasFlags();
778 hasFlags = as.getFlag();
781 String strDesc = as.toStringForDOT()+"\\nsummary";
783 strDesc += " shadow";
787 createNewHeapRegionNode( idSummary, // id or null to generate a new one
788 false, // single object?
790 hasFlags, // flagged?
791 false, // out-of-context?
792 as.getType(), // type
793 as, // allocation site
794 null, // inherent reach
795 null, // current reach
796 predsEmpty, // predicates
797 strDesc // description
804 // either retrieve or create the needed heap region node
805 protected HeapRegionNode getIthNode( AllocSite as,
811 idIth = as.getIthOldestShadow( i );
813 idIth = as.getIthOldest( i );
816 HeapRegionNode hrnIth = id2hrn.get( idIth );
818 if( hrnIth == null ) {
820 boolean hasFlags = false;
821 if( as.getType().isClass() ) {
822 hasFlags = as.getType().getClassDesc().hasFlags();
826 hasFlags = as.getFlag();
829 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
831 strDesc += " shadow";
834 hrnIth = createNewHeapRegionNode( idIth, // id or null to generate a new one
835 true, // single object?
837 hasFlags, // flagged?
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.union( 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.union( 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.union( 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().contains( c.getSetToMatch() ) ) {
1084 changesToPass = Canonical.union( changesToPass, c );
1088 if( !changesToPass.isEmpty() ) {
1089 if( !nodePlannedChanges.containsKey( m ) ) {
1090 nodePlannedChanges.put( m, ChangeSet.factory() );
1093 ChangeSet currentChanges = nodePlannedChanges.get( m );
1095 if( !changesToPass.isSubset( currentChanges ) ) {
1097 nodePlannedChanges.put( m,
1098 Canonical.union( currentChanges,
1107 todoNodes.remove( n );
1110 // then apply all of the changes for each node at once
1111 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1112 while( itrMap.hasNext() ) {
1113 Map.Entry me = (Map.Entry) itrMap.next();
1114 HeapRegionNode n = (HeapRegionNode) me.getKey();
1115 ChangeSet C = (ChangeSet) me.getValue();
1117 // this propagation step is with respect to one change,
1118 // so we capture the full change from the old alpha:
1119 ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1123 // but this propagation may be only one of many concurrent
1124 // possible changes, so keep a running union with the node's
1125 // partially updated new alpha set
1126 n.setAlphaNew( Canonical.union( n.getAlphaNew(),
1131 nodesWithNewAlpha.add( n );
1134 propagateTokensOverEdges( todoEdges,
1141 protected void propagateTokensOverEdges( HashSet <RefEdge> todoEdges,
1142 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1143 HashSet <RefEdge> edgesWithNewBeta ) {
1145 // first propagate all change tuples everywhere they can go
1146 while( !todoEdges.isEmpty() ) {
1147 RefEdge edgeE = todoEdges.iterator().next();
1148 todoEdges.remove( edgeE );
1150 if( !edgePlannedChanges.containsKey( edgeE ) ) {
1151 edgePlannedChanges.put( edgeE,
1156 ChangeSet C = edgePlannedChanges.get( edgeE );
1158 ChangeSet changesToPass = ChangeSet.factory();
1160 Iterator<ChangeTuple> itrC = C.iterator();
1161 while( itrC.hasNext() ) {
1162 ChangeTuple c = itrC.next();
1163 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1164 changesToPass = Canonical.union( changesToPass, c );
1168 RefSrcNode rsn = edgeE.getSrc();
1170 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1171 HeapRegionNode n = (HeapRegionNode) rsn;
1173 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1174 while( referItr.hasNext() ) {
1175 RefEdge edgeF = referItr.next();
1177 if( !edgePlannedChanges.containsKey( edgeF ) ) {
1178 edgePlannedChanges.put( edgeF,
1183 ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1185 if( !changesToPass.isSubset( currentChanges ) ) {
1186 todoEdges.add( edgeF );
1187 edgePlannedChanges.put( edgeF,
1188 Canonical.union( currentChanges,
1197 // then apply all of the changes for each edge at once
1198 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1199 while( itrMap.hasNext() ) {
1200 Map.Entry me = (Map.Entry) itrMap.next();
1201 RefEdge e = (RefEdge) me.getKey();
1202 ChangeSet C = (ChangeSet) me.getValue();
1204 // this propagation step is with respect to one change,
1205 // so we capture the full change from the old beta:
1206 ReachSet localDelta =
1207 Canonical.applyChangeSet( e.getBeta(),
1212 // but this propagation may be only one of many concurrent
1213 // possible changes, so keep a running union with the edge's
1214 // partially updated new beta set
1215 e.setBetaNew( Canonical.union( e.getBetaNew(),
1220 edgesWithNewBeta.add( e );
1225 // used in makeCalleeView below to decide if there is
1226 // already an appropriate out-of-context edge in a callee
1227 // view graph for merging, or null if a new one will be added
1229 getOutOfContextReferenceTo( HeapRegionNode hrn,
1230 TypeDescriptor srcType,
1231 TypeDescriptor refType,
1233 assert belongsToThis( hrn );
1235 HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1236 if( hrnInContext == null ) {
1240 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1241 while( refItr.hasNext() ) {
1242 RefEdge re = refItr.next();
1244 assert belongsToThis( re.getSrc() );
1245 assert belongsToThis( re.getDst() );
1247 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1251 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1252 if( !hrnSrc.isOutOfContext() ) {
1256 if( srcType == null ) {
1257 if( hrnSrc.getType() != null ) {
1261 if( !srcType.equals( hrnSrc.getType() ) ) {
1266 if( !re.typeEquals( refType ) ) {
1270 if( !re.fieldEquals( refField ) ) {
1274 // tada! We found it!
1281 // used below to convert a ReachSet to its callee-context
1282 // equivalent with respect to allocation sites in this graph
1283 protected ReachSet toCalleeContext( Set<ReachTuple> oocTuples,
1286 TempDescriptor tdSrc,
1289 TypeDescriptor type,
1291 boolean outOfContext
1293 ReachSet out = ReachSet.factory();
1295 Iterator<ReachState> itr = rs.iterator();
1296 while( itr.hasNext() ) {
1297 ReachState stateCaller = itr.next();
1299 ReachState stateCallee = stateCaller;
1301 Iterator<AllocSite> asItr = allocSites.iterator();
1302 while( asItr.hasNext() ) {
1303 AllocSite as = asItr.next();
1305 ReachState stateNew = ReachState.factory();
1306 Iterator<ReachTuple> rtItr = stateCallee.iterator();
1307 while( rtItr.hasNext() ) {
1308 ReachTuple rt = rtItr.next();
1310 // only translate this tuple if it is in the out-context bag
1311 if( !oocTuples.contains( rt ) ) {
1312 stateNew = Canonical.union( stateNew, rt );
1316 int age = as.getAgeCategory( rt.getHrnID() );
1318 // this is the current mapping, where 0, 1, 2S were allocated
1319 // in the current context, 0?, 1? and 2S? were allocated in a
1320 // previous context, and we're translating to a future context
1332 if( age == AllocSite.AGE_notInThisSite ) {
1333 // things not from the site just go back in
1334 stateNew = Canonical.union( stateNew, rt );
1336 } else if( age == AllocSite.AGE_summary ||
1339 // the in-context summary and all existing out-of-context
1341 stateNew = Canonical.union( stateNew,
1342 ReachTuple.factory( as.getSummary(),
1345 true // out-of-context
1349 // otherwise everything else just goes to an out-of-context
1350 // version, everything else the same
1351 Integer I = as.getAge( rt.getHrnID() );
1354 assert !rt.isMultiObject();
1356 stateNew = Canonical.union( stateNew,
1357 ReachTuple.factory( rt.getHrnID(),
1360 true // out-of-context
1366 stateCallee = stateNew;
1372 if( outOfContext ) {
1376 if( hrnID != null ) {
1377 assert tdSrc == null;
1378 assert hrnSrcID == null;
1379 assert hrnDstID == null;
1380 pred = ExistPred.factory( hrnID,
1383 assert tdSrc != null || hrnSrcID != null;
1384 assert hrnDstID != null;
1385 pred = ExistPred.factory( tdSrc,
1393 preds = ExistPredSet.factory( pred );
1396 stateCallee = Canonical.attach( stateCallee,
1399 out = Canonical.add( out,
1404 assert out.isCanonical();
1408 // used below to convert a ReachSet to its caller-context
1409 // equivalent with respect to allocation sites in this graph
1411 toCallerContext( ReachSet rs,
1412 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1414 ReachSet out = ReachSet.factory();
1416 Iterator<ReachState> itr = rs.iterator();
1417 while( itr.hasNext() ) {
1418 ReachState stateCallee = itr.next();
1420 if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
1422 // starting from one callee state...
1423 ReachSet rsCaller = ReachSet.factory( stateCallee );
1425 // possibly branch it into many states, which any
1426 // allocation site might do, so lots of derived states
1427 Iterator<AllocSite> asItr = allocSites.iterator();
1428 while( asItr.hasNext() ) {
1429 AllocSite as = asItr.next();
1430 rsCaller = Canonical.toCallerContext( rs, as );
1433 // then before adding each derived, now caller-context
1434 // states to the output, attach the appropriate pred
1435 // based on the source callee state
1436 Iterator<ReachState> stateItr = rsCaller.iterator();
1437 while( stateItr.hasNext() ) {
1438 ReachState stateCaller = stateItr.next();
1439 stateCaller = Canonical.attach( stateCaller,
1440 calleeStatesSatisfied.get( stateCallee )
1442 out = Canonical.union( out,
1449 assert out.isCanonical();
1453 // used below to convert a ReachSet to an equivalent
1454 // version with shadow IDs merged into unshadowed IDs
1455 protected ReachSet unshadow( ReachSet rs ) {
1457 Iterator<AllocSite> asItr = allocSites.iterator();
1458 while( asItr.hasNext() ) {
1459 AllocSite as = asItr.next();
1460 out = Canonical.unshadow( out, as );
1462 assert out.isCanonical();
1467 // use this method to make a new reach graph that is
1468 // what heap the FlatMethod callee from the FlatCall
1469 // would start with reaching from its arguments in
1472 makeCalleeView( FlatCall fc,
1473 FlatMethod fmCallee,
1474 Set<Integer> callerNodeIDsCopiedToCallee,
1475 boolean writeDebugDOTs
1478 // first traverse this context to find nodes and edges
1479 // that will be callee-reachable
1480 Set<HeapRegionNode> reachableCallerNodes =
1481 new HashSet<HeapRegionNode>();
1483 Set<RefEdge> reachableCallerEdges =
1484 new HashSet<RefEdge>();
1486 Set<RefEdge> oocCallerEdges =
1487 new HashSet<RefEdge>();
1489 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1491 TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1492 VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
1494 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1495 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1497 toVisitInCaller.add( vnCaller );
1499 while( !toVisitInCaller.isEmpty() ) {
1500 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1501 toVisitInCaller.remove( rsnCaller );
1502 visitedInCaller.add( rsnCaller );
1504 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1505 while( itrRefEdges.hasNext() ) {
1506 RefEdge reCaller = itrRefEdges.next();
1507 HeapRegionNode hrnCaller = reCaller.getDst();
1509 callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
1510 reachableCallerNodes.add( hrnCaller );
1512 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1513 reachableCallerEdges.add( reCaller );
1515 oocCallerEdges.add( reCaller );
1518 if( !visitedInCaller.contains( hrnCaller ) ) {
1519 toVisitInCaller.add( hrnCaller );
1522 } // end edge iteration
1523 } // end visiting heap nodes in caller
1524 } // end iterating over parameters as starting points
1527 // now collect out-of-context reach tuples and
1528 // more out-of-context edges
1529 Set<ReachTuple> oocTuples = new HashSet<ReachTuple>();
1531 Iterator<Integer> itrInContext =
1532 callerNodeIDsCopiedToCallee.iterator();
1533 while( itrInContext.hasNext() ) {
1534 Integer hrnID = itrInContext.next();
1535 HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1537 Iterator<RefEdge> itrMightCross =
1538 hrnCallerAndInContext.iteratorToReferencers();
1539 while( itrMightCross.hasNext() ) {
1540 RefEdge edgeMightCross = itrMightCross.next();
1542 RefSrcNode rsnCallerAndOutContext =
1543 edgeMightCross.getSrc();
1545 if( rsnCallerAndOutContext instanceof VariableNode ) {
1546 // variables do not have out-of-context reach states,
1548 oocCallerEdges.add( edgeMightCross );
1552 HeapRegionNode hrnCallerAndOutContext =
1553 (HeapRegionNode) rsnCallerAndOutContext;
1555 // is this source node out-of-context?
1556 if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1557 // no, skip this edge
1562 oocCallerEdges.add( edgeMightCross );
1564 // add all reach tuples on the node to list
1565 // of things that are out-of-context: insight
1566 // if this node is reachable from someting that WAS
1567 // in-context, then this node should already be in-context
1568 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1569 while( stateItr.hasNext() ) {
1570 ReachState state = stateItr.next();
1572 Iterator<ReachTuple> rtItr = state.iterator();
1573 while( rtItr.hasNext() ) {
1574 ReachTuple rt = rtItr.next();
1576 oocTuples.add( rt );
1583 // the callee view is a new graph: DON'T MODIFY *THIS* graph
1584 ReachGraph rg = new ReachGraph();
1586 // add nodes to callee graph
1587 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1588 while( hrnItr.hasNext() ) {
1589 HeapRegionNode hrnCaller = hrnItr.next();
1591 assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
1592 assert !rg.id2hrn.containsKey( hrnCaller.getID() );
1594 ExistPred pred = ExistPred.factory( hrnCaller.getID(), null );
1595 ExistPredSet preds = ExistPredSet.factory( pred );
1597 rg.createNewHeapRegionNode( hrnCaller.getID(),
1598 hrnCaller.isSingleObject(),
1599 hrnCaller.isNewSummary(),
1600 hrnCaller.isFlagged(),
1601 false, // out-of-context?
1602 hrnCaller.getType(),
1603 hrnCaller.getAllocSite(),
1604 toCalleeContext( oocTuples,
1605 hrnCaller.getInherent(), // in state
1606 hrnCaller.getID(), // node pred
1607 null, null, null, null, null, // edge pred
1608 false ), // ooc pred
1609 toCalleeContext( oocTuples,
1610 hrnCaller.getAlpha(), // in state
1611 hrnCaller.getID(), // node pred
1612 null, null, null, null, null, // edge pred
1613 false ), // ooc pred
1615 hrnCaller.getDescription()
1619 // add in-context edges to callee graph
1620 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1621 while( reItr.hasNext() ) {
1622 RefEdge reCaller = reItr.next();
1623 RefSrcNode rsnCaller = reCaller.getSrc();
1624 assert rsnCaller instanceof HeapRegionNode;
1625 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1626 HeapRegionNode hrnDstCaller = reCaller.getDst();
1628 HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
1629 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1630 assert hrnSrcCallee != null;
1631 assert hrnDstCallee != null;
1634 ExistPred.factory( null,
1635 hrnSrcCallee.getID(),
1636 hrnDstCallee.getID(),
1638 reCaller.getField(),
1640 false ); // out-of-context
1642 ExistPredSet preds =
1643 ExistPredSet.factory( pred );
1646 new RefEdge( hrnSrcCallee,
1649 reCaller.getField(),
1650 toCalleeContext( oocTuples,
1651 reCaller.getBeta(), // in state
1654 hrnSrcCallee.getID(), // edge pred
1655 hrnDstCallee.getID(), // edge pred
1656 reCaller.getType(), // edge pred
1657 reCaller.getField(), // edge pred
1658 false ), // ooc pred
1662 rg.addRefEdge( hrnSrcCallee,
1668 // add out-of-context edges to callee graph
1669 reItr = oocCallerEdges.iterator();
1670 while( reItr.hasNext() ) {
1671 RefEdge reCaller = reItr.next();
1672 RefSrcNode rsnCaller = reCaller.getSrc();
1673 HeapRegionNode hrnDstCaller = reCaller.getDst();
1674 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1675 assert hrnDstCallee != null;
1677 TypeDescriptor oocNodeType;
1679 TempDescriptor oocPredSrcTemp = null;
1680 Integer oocPredSrcID = null;
1682 if( rsnCaller instanceof VariableNode ) {
1683 VariableNode vnCaller = (VariableNode) rsnCaller;
1685 oocReach = rsetEmpty;
1686 oocPredSrcTemp = vnCaller.getTempDescriptor();
1689 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1690 assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
1691 oocNodeType = hrnSrcCaller.getType();
1692 oocReach = hrnSrcCaller.getAlpha();
1693 oocPredSrcID = hrnSrcCaller.getID();
1697 ExistPred.factory( oocPredSrcTemp,
1699 hrnDstCallee.getID(),
1701 reCaller.getField(),
1703 true ); // out-of-context
1705 ExistPredSet preds =
1706 ExistPredSet.factory( pred );
1708 RefEdge oocEdgeExisting =
1709 rg.getOutOfContextReferenceTo( hrnDstCallee,
1715 if( oocEdgeExisting == null ) {
1716 // for consistency, map one out-of-context "identifier"
1717 // to one heap region node id, otherwise no convergence
1718 String oocid = "oocid"+
1720 hrnDstCallee.getIDString()+
1723 reCaller.getField();
1725 Integer oocHrnID = oocid2hrnid.get( oocid );
1727 HeapRegionNode hrnCalleeAndOutContext;
1729 if( oocHrnID == null ) {
1731 hrnCalleeAndOutContext =
1732 rg.createNewHeapRegionNode( null, // ID
1733 false, // single object?
1734 false, // new summary?
1736 true, // out-of-context?
1738 null, // alloc site, shouldn't be used
1739 toCalleeContext( oocTuples,
1740 oocReach, // in state
1742 null, null, null, null, null, // edge pred
1745 toCalleeContext( oocTuples,
1746 oocReach, // in state
1748 null, null, null, null, null, // edge pred
1755 oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1759 // the mapping already exists, so see if node is there
1760 hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1762 if( hrnCalleeAndOutContext == null ) {
1764 hrnCalleeAndOutContext =
1765 rg.createNewHeapRegionNode( oocHrnID, // ID
1766 false, // single object?
1767 false, // new summary?
1769 true, // out-of-context?
1771 null, // alloc site, shouldn't be used
1772 toCalleeContext( oocTuples,
1773 oocReach, // in state
1775 null, null, null, null, null, // edge pred
1778 toCalleeContext( oocTuples,
1779 oocReach, // in state
1781 null, null, null, null, null, // edge pred
1790 rg.addRefEdge( hrnCalleeAndOutContext,
1792 new RefEdge( hrnCalleeAndOutContext,
1795 reCaller.getField(),
1796 toCalleeContext( oocTuples,
1797 reCaller.getBeta(), // in state
1799 oocPredSrcTemp, // edge pred
1800 oocPredSrcID, // edge pred
1801 hrnDstCaller.getID(), // edge pred
1802 reCaller.getType(), // edge pred
1803 reCaller.getField(), // edge pred
1811 // the out-of-context edge already exists
1812 oocEdgeExisting.setBeta( Canonical.union( oocEdgeExisting.getBeta(),
1813 toCalleeContext( oocTuples,
1814 reCaller.getBeta(), // in state
1816 oocPredSrcTemp, // edge pred
1817 oocPredSrcID, // edge pred
1818 hrnDstCaller.getID(), // edge pred
1819 reCaller.getType(), // edge pred
1820 reCaller.getField(), // edge pred
1826 oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1835 if( writeDebugDOTs ) {
1837 rg.writeGraph( "calleeview", true, false, false, false, true, true );
1838 } catch( IOException e ) {}
1844 private static Hashtable<String, Integer> oocid2hrnid =
1845 new Hashtable<String, Integer>();
1850 resolveMethodCall( FlatCall fc,
1851 FlatMethod fmCallee,
1852 ReachGraph rgCallee,
1853 Set<Integer> callerNodeIDsCopiedToCallee,
1854 boolean writeDebugDOTs
1858 if( writeDebugDOTs ) {
1860 rgCallee.writeGraph( "callee",
1861 true, false, false, false, true, true );
1862 writeGraph( "caller00In",
1863 true, false, false, false, true, true,
1864 callerNodeIDsCopiedToCallee );
1865 } catch( IOException e ) {}
1869 // method call transfer function steps:
1870 // 1. Use current callee-reachable heap (CRH) to test callee
1871 // predicates and mark what will be coming in.
1872 // 2. Wipe CRH out of caller.
1873 // 3. Transplant marked callee parts in:
1874 // a) bring in nodes
1875 // b) bring in callee -> callee edges
1876 // c) resolve out-of-context -> callee edges
1877 // d) assign return value
1878 // 4. Collapse shadow nodes down
1879 // 5. Global sweep it.
1883 // 1. mark what callee elements have satisfied predicates
1884 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1885 new Hashtable<HeapRegionNode, ExistPredSet>();
1887 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1888 new Hashtable<RefEdge, ExistPredSet>();
1890 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1891 new Hashtable<ReachState, ExistPredSet>();
1893 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1894 new Hashtable< RefEdge, Set<RefSrcNode> >();
1896 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1897 while( meItr.hasNext() ) {
1898 Map.Entry me = (Map.Entry) meItr.next();
1899 Integer id = (Integer) me.getKey();
1900 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1902 // if a callee element's predicates are satisfied then a set
1903 // of CALLER predicates is returned: they are the predicates
1904 // that the callee element moved into the caller context
1905 // should have, and it is inefficient to find this again later
1906 ExistPredSet predsIfSatis =
1907 hrnCallee.getPreds().isSatisfiedBy( this,
1908 callerNodeIDsCopiedToCallee
1910 if( predsIfSatis != null ) {
1911 calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1913 // otherwise don't bother looking at edges to this node
1917 // since the node is coming over, find out which reach
1918 // states on it should come over, too
1919 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
1920 while( stateItr.hasNext() ) {
1921 ReachState stateCallee = stateItr.next();
1924 stateCallee.getPreds().isSatisfiedBy( this,
1925 callerNodeIDsCopiedToCallee
1927 if( predsIfSatis != null ) {
1928 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
1932 // then look at edges to the node
1933 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
1934 while( reItr.hasNext() ) {
1935 RefEdge reCallee = reItr.next();
1936 RefSrcNode rsnCallee = reCallee.getSrc();
1938 // (caller local variables to in-context heap regions)
1939 // have an (out-of-context heap region -> in-context heap region)
1940 // abstraction in the callEE, so its true we never need to
1941 // look at a (var node -> heap region) edge in callee to bring
1942 // those over for the call site transfer. What about (param var->heap region)
1943 // edges in callee? They are dealt with below this loop.
1944 // So, yes, at this point skip (var->region) edges in callee
1945 if( rsnCallee instanceof VariableNode ) {
1949 // first see if the source is out-of-context, and only
1950 // proceed with this edge if we find some caller-context
1952 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
1953 boolean matchedOutOfContext = false;
1955 if( hrnSrcCallee.isOutOfContext() ) {
1957 assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
1958 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
1960 HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
1961 Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
1962 while( reDstItr.hasNext() ) {
1963 // the edge and field (either possibly null) must match
1964 RefEdge reCaller = reDstItr.next();
1966 if( !reCaller.typeEquals ( reCallee.getType() ) ||
1967 !reCaller.fieldEquals( reCallee.getField() )
1972 RefSrcNode rsnCaller = reCaller.getSrc();
1973 if( rsnCaller instanceof VariableNode ) {
1974 // a variable node matches an OOC region with null type
1975 if( hrnSrcCallee.getType() != null ) {
1980 // otherwise types should match
1981 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
1982 if( hrnSrcCallee.getType() == null ) {
1983 if( hrnCallerSrc.getType() != null ) {
1987 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
1993 rsnCallers.add( rsnCaller );
1994 matchedOutOfContext = true;
1997 if( !rsnCallers.isEmpty() ) {
1998 calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2002 if( hrnSrcCallee.isOutOfContext() &&
2003 !matchedOutOfContext ) {
2008 reCallee.getPreds().isSatisfiedBy( this,
2009 callerNodeIDsCopiedToCallee
2011 if( predsIfSatis != null ) {
2012 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2014 // since the edge is coming over, find out which reach
2015 // states on it should come over, too
2016 stateItr = reCallee.getBeta().iterator();
2017 while( stateItr.hasNext() ) {
2018 ReachState stateCallee = stateItr.next();
2021 stateCallee.getPreds().isSatisfiedBy( this,
2022 callerNodeIDsCopiedToCallee
2024 if( predsIfSatis != null ) {
2025 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2034 // test param -> HRN edges, also
2035 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
2037 // parameter defined here is the symbol in the callee
2038 TempDescriptor tdParam = fmCallee.getParameter( i );
2039 VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
2041 Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
2042 while( reItr.hasNext() ) {
2043 RefEdge reCallee = reItr.next();
2045 ExistPredSet ifDst =
2046 reCallee.getDst().getPreds().isSatisfiedBy( this,
2047 callerNodeIDsCopiedToCallee
2049 if( ifDst == null ) {
2053 ExistPredSet predsIfSatis =
2054 reCallee.getPreds().isSatisfiedBy( this,
2055 callerNodeIDsCopiedToCallee
2057 if( predsIfSatis != null ) {
2058 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2060 // since the edge is coming over, find out which reach
2061 // states on it should come over, too
2062 Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
2063 while( stateItr.hasNext() ) {
2064 ReachState stateCallee = stateItr.next();
2067 stateCallee.getPreds().isSatisfiedBy( this,
2068 callerNodeIDsCopiedToCallee
2070 if( predsIfSatis != null ) {
2071 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2082 if( writeDebugDOTs ) {
2084 writeGraph( "caller20BeforeWipe",
2085 true, false, false, false, true, true );
2086 } catch( IOException e ) {}
2090 // 2. predicates tested, ok to wipe out caller part
2091 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2092 while( hrnItr.hasNext() ) {
2093 Integer hrnID = hrnItr.next();
2094 HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2095 assert hrnCaller != null;
2097 // when clearing off nodes, also eliminate variable
2099 wipeOut( hrnCaller, true );
2104 if( writeDebugDOTs ) {
2106 writeGraph( "caller30BeforeAddingNodes",
2107 true, false, false, false, true, true );
2108 } catch( IOException e ) {}
2112 // 3. callee elements with satisfied preds come in, note that
2113 // the mapping of elements satisfied to preds is like this:
2114 // A callee element EE has preds EEp that are satisfied by
2115 // some caller element ER. We bring EE into the caller
2116 // context as ERee with the preds of ER, namely ERp, which
2117 // in the following algorithm is the value in the mapping
2120 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2121 while( satisItr.hasNext() ) {
2122 Map.Entry me = (Map.Entry) satisItr.next();
2123 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2124 ExistPredSet preds = (ExistPredSet) me.getValue();
2126 // TODO: I think its true that the current implementation uses
2127 // the type of the OOC region and the predicates OF THE EDGE from
2128 // it to link everything up in caller context, so that's why we're
2129 // skipping this... maybe that's a sillier way to do it?
2130 if( hrnCallee.isOutOfContext() ) {
2134 AllocSite as = hrnCallee.getAllocSite();
2135 allocSites.add( as );
2137 Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2139 HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2140 if( hrnCaller == null ) {
2142 createNewHeapRegionNode( hrnIDshadow, // id or null to generate a new one
2143 hrnCallee.isSingleObject(), // single object?
2144 hrnCallee.isNewSummary(), // summary?
2145 hrnCallee.isFlagged(), // flagged?
2146 false, // out-of-context?
2147 hrnCallee.getType(), // type
2148 hrnCallee.getAllocSite(), // allocation site
2149 toCallerContext( hrnCallee.getInherent(),
2150 calleeStatesSatisfied ), // inherent reach
2151 null, // current reach
2152 predsEmpty, // predicates
2153 hrnCallee.getDescription() // description
2156 assert hrnCaller.isWiped();
2159 hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2160 calleeStatesSatisfied
2164 hrnCaller.setPreds( preds );
2169 if( writeDebugDOTs ) {
2171 writeGraph( "caller31BeforeAddingEdges",
2172 true, false, false, false, true, true );
2173 } catch( IOException e ) {}
2177 // set these up during the next procedure so after
2178 // the caller has all of its nodes and edges put
2179 // back together we can propagate the callee's
2180 // reach changes backwards into the caller graph
2181 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2183 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2184 new Hashtable<RefEdge, ChangeSet>();
2187 // 3.b) callee -> callee edges AND out-of-context -> callee
2188 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2189 while( satisItr.hasNext() ) {
2190 Map.Entry me = (Map.Entry) satisItr.next();
2191 RefEdge reCallee = (RefEdge) me.getKey();
2192 ExistPredSet preds = (ExistPredSet) me.getValue();
2194 HeapRegionNode hrnDstCallee = reCallee.getDst();
2195 AllocSite asDst = hrnDstCallee.getAllocSite();
2196 allocSites.add( asDst );
2198 Integer hrnIDDstShadow =
2199 asDst.getShadowIDfromID( hrnDstCallee.getID() );
2201 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2202 assert hrnDstCaller != null;
2205 RefSrcNode rsnCallee = reCallee.getSrc();
2207 Set<RefSrcNode> rsnCallers =
2208 new HashSet<RefSrcNode>();
2210 Set<RefSrcNode> oocCallers =
2211 calleeEdges2oocCallerSrcMatches.get( reCallee );
2213 boolean oocEdges = false;
2215 if( oocCallers == null ) {
2216 // there are no out-of-context matches, so it's
2217 // either a param/arg var or one in-context heap region
2218 if( rsnCallee instanceof VariableNode ) {
2219 // variable -> node in the callee should only
2220 // come into the caller if its from a param var
2221 VariableNode vnCallee = (VariableNode) rsnCallee;
2222 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2223 TempDescriptor tdArg = fc.getArgMatchingParam( fmCallee,
2225 if( tdArg == null ) {
2226 // this means the variable isn't a parameter, its local
2227 // to the callee so we ignore it in call site transfer
2228 // shouldn't this NEVER HAPPEN?
2231 rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2235 // otherwise source is in context, one region
2236 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2238 // translate an in-context node to shadow
2239 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2240 allocSites.add( asSrc );
2242 Integer hrnIDSrcShadow =
2243 asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2245 HeapRegionNode hrnSrcCallerShadow =
2246 this.id2hrn.get( hrnIDSrcShadow );
2248 if( hrnSrcCallerShadow == null ) {
2249 hrnSrcCallerShadow =
2250 createNewHeapRegionNode( hrnIDSrcShadow, // id or null to generate a new one
2251 hrnSrcCallee.isSingleObject(), // single object?
2252 hrnSrcCallee.isNewSummary(), // summary?
2253 hrnSrcCallee.isFlagged(), // flagged?
2254 false, // out-of-context?
2255 hrnSrcCallee.getType(), // type
2256 hrnSrcCallee.getAllocSite(), // allocation site
2257 toCallerContext( hrnSrcCallee.getInherent(),
2258 calleeStatesSatisfied ), // inherent reach
2259 toCallerContext( hrnSrcCallee.getAlpha(),
2260 calleeStatesSatisfied ), // current reach
2261 predsEmpty, // predicates
2262 hrnSrcCallee.getDescription() // description
2266 rsnCallers.add( hrnSrcCallerShadow );
2270 // otherwise we have a set of out-of-context srcs
2271 // that should NOT be translated to shadow nodes
2272 assert !oocCallers.isEmpty();
2273 rsnCallers.addAll( oocCallers );
2277 // now make all caller edges we've identified from
2278 // this callee edge with a satisfied predicate
2279 assert !rsnCallers.isEmpty();
2280 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2281 while( rsnItr.hasNext() ) {
2282 RefSrcNode rsnCaller = rsnItr.next();
2284 // TODO: beta rewrites
2285 RefEdge reCaller = new RefEdge( rsnCaller,
2288 reCallee.getField(),
2289 toCallerContext( reCallee.getBeta(),
2290 calleeStatesSatisfied ),
2294 ChangeSet cs = ChangeSet.factory();
2295 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2296 while( rsItr.hasNext() ) {
2297 ReachState state = rsItr.next();
2298 ExistPredSet preds2 = state.getPreds();
2299 assert preds2.preds.size() == 1;
2301 ExistPred pred = preds2.preds.iterator().next();
2302 ReachState old = pred.ne_state;
2305 cs = Canonical.union( cs,
2306 ChangeTuple.factory( old,
2312 // look to see if an edge with same field exists
2313 // and merge with it, otherwise just add the edge
2314 RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2318 if( edgeExisting != null ) {
2319 edgeExisting.setBeta(
2320 Canonical.union( edgeExisting.getBeta(),
2324 edgeExisting.setPreds(
2325 Canonical.join( edgeExisting.getPreds(),
2330 // for reach propagation
2331 edgePlannedChanges.put(
2333 Canonical.union( edgePlannedChanges.get( edgeExisting ),
2339 addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2341 // for reach propagation
2342 edgesForPropagation.add( reCaller );
2343 assert !edgePlannedChanges.containsKey( reCaller );
2344 edgePlannedChanges.put( reCaller, cs );
2353 if( writeDebugDOTs ) {
2355 writeGraph( "caller35BeforeAssignReturnValue",
2356 true, false, false, false, true, true );
2357 } catch( IOException e ) {}
2362 // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2363 // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2364 // EDGES, JUST BRINGING THEM ALL! It'll work for now, over approximation
2366 // 3.d) handle return value assignment if needed
2367 TempDescriptor returnTemp = fc.getReturnTemp();
2368 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2370 VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2371 clearRefEdgesFrom( vnLhsCaller, null, null, true );
2373 VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2374 Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2375 while( reCalleeItr.hasNext() ) {
2376 RefEdge reCallee = reCalleeItr.next();
2377 HeapRegionNode hrnDstCallee = reCallee.getDst();
2379 // some edge types are not possible return values when we can
2380 // see what type variable we are assigning it to
2381 if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2382 System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2383 reCallee+" for return temp "+returnTemp );
2388 AllocSite asDst = hrnDstCallee.getAllocSite();
2389 allocSites.add( asDst );
2391 Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2393 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2394 if( hrnDstCaller == null ) {
2396 createNewHeapRegionNode( hrnIDDstShadow, // id or null to generate a new one
2397 hrnDstCallee.isSingleObject(), // single object?
2398 hrnDstCallee.isNewSummary(), // summary?
2399 hrnDstCallee.isFlagged(), // flagged?
2400 false, // out-of-context?
2401 hrnDstCallee.getType(), // type
2402 hrnDstCallee.getAllocSite(), // allocation site
2403 toCallerContext( hrnDstCallee.getInherent(),
2404 calleeStatesSatisfied ), // inherent reach
2405 toCallerContext( hrnDstCallee.getAlpha(),
2406 calleeStatesSatisfied ), // current reach
2407 predsTrue, // predicates
2408 hrnDstCallee.getDescription() // description
2411 assert hrnDstCaller.isWiped();
2414 TypeDescriptor tdNewEdge =
2415 mostSpecificType( reCallee.getType(),
2416 hrnDstCallee.getType(),
2417 hrnDstCaller.getType()
2420 RefEdge reCaller = new RefEdge( vnLhsCaller,
2424 toCallerContext( reCallee.getBeta(),
2425 calleeStatesSatisfied ),
2429 addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2435 if( writeDebugDOTs ) {
2437 writeGraph( "caller38propagateReach",
2438 true, false, false, false, true, true );
2439 } catch( IOException e ) {}
2442 // propagate callee reachability changes to the rest
2443 // of the caller graph edges
2447 if( !cts.isEmpty() ) {
2448 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2449 while( incidentEdgeItr.hasNext() ) {
2450 RefEdge incidentEdge = incidentEdgeItr.next();
2452 edgesForPropagation.add( incidentEdge );
2454 if( edgePlannedChanges.get( incidentEdge ) == null ) {
2455 edgePlannedChanges.put( incidentEdge, cts );
2457 edgePlannedChanges.put(
2459 Canonical.union( edgePlannedChanges.get( incidentEdge ),
2468 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2470 propagateTokensOverEdges( edgesForPropagation, // source edges
2471 edgePlannedChanges, // map src edge to change set
2472 edgesUpdated ); // list of updated edges
2474 // commit beta' (beta<-betaNew)
2475 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2476 while( edgeItr.hasNext() ) {
2477 edgeItr.next().applyBetaNew();
2485 if( writeDebugDOTs ) {
2487 writeGraph( "caller40BeforeShadowMerge",
2488 true, false, false, false, true, true );
2489 } catch( IOException e ) {}
2493 // 4) merge shadow nodes so alloc sites are back to k
2494 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2495 while( asItr.hasNext() ) {
2496 // for each allocation site do the following to merge
2497 // shadow nodes (newest from callee) with any existing
2498 // look for the newest normal and newest shadow "slot"
2499 // not being used, transfer normal to shadow. Keep
2500 // doing this until there are no more normal nodes, or
2501 // no empty shadow slots: then merge all remaining normal
2502 // nodes into the shadow summary. Finally, convert all
2503 // shadow to their normal versions.
2504 AllocSite as = asItr.next();
2507 while( ageNorm < allocationDepth &&
2508 ageShad < allocationDepth ) {
2510 // first, are there any normal nodes left?
2511 Integer idNorm = as.getIthOldest( ageNorm );
2512 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2513 if( hrnNorm == null ) {
2514 // no, this age of normal node not in the caller graph
2519 // yes, a normal node exists, is there an empty shadow
2520 // "slot" to transfer it onto?
2521 HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2522 if( !hrnShad.isWiped() ) {
2523 // no, this age of shadow node is not empty
2528 // yes, this shadow node is empty
2529 transferOnto( hrnNorm, hrnShad );
2534 // now, while there are still normal nodes but no shadow
2535 // slots, merge normal nodes into the shadow summary
2536 while( ageNorm < allocationDepth ) {
2538 // first, are there any normal nodes left?
2539 Integer idNorm = as.getIthOldest( ageNorm );
2540 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2541 if( hrnNorm == null ) {
2542 // no, this age of normal node not in the caller graph
2547 // yes, a normal node exists, so get the shadow summary
2548 HeapRegionNode summShad = getSummaryNode( as, true );
2549 mergeIntoSummary( hrnNorm, summShad );
2553 // if there is a normal summary, merge it into shadow summary
2554 Integer idNorm = as.getSummary();
2555 HeapRegionNode summNorm = id2hrn.get( idNorm );
2556 if( summNorm != null ) {
2557 HeapRegionNode summShad = getSummaryNode( as, true );
2558 mergeIntoSummary( summNorm, summShad );
2561 // finally, flip all existing shadow nodes onto the normal
2562 for( int i = 0; i < allocationDepth; ++i ) {
2563 Integer idShad = as.getIthOldestShadow( i );
2564 HeapRegionNode hrnShad = id2hrn.get( idShad );
2565 if( hrnShad != null ) {
2567 HeapRegionNode hrnNorm = getIthNode( as, i, false );
2568 assert hrnNorm.isWiped();
2569 transferOnto( hrnShad, hrnNorm );
2573 Integer idShad = as.getSummaryShadow();
2574 HeapRegionNode summShad = id2hrn.get( idShad );
2575 if( summShad != null ) {
2576 summNorm = getSummaryNode( as, false );
2577 transferOnto( summShad, summNorm );
2582 if( writeDebugDOTs ) {
2584 writeGraph( "caller45BeforeUnshadow",
2585 true, false, false, false, true, true );
2586 } catch( IOException e ) {}
2590 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2591 while( itrAllHRNodes.hasNext() ) {
2592 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
2593 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2595 hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2597 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2598 while( itrEdges.hasNext() ) {
2599 RefEdge re = itrEdges.next();
2600 re.setBeta( unshadow( re.getBeta() ) );
2606 if( writeDebugDOTs ) {
2608 writeGraph( "caller50BeforeGlobalSweep",
2609 true, false, false, false, true, true );
2610 } catch( IOException e ) {}
2615 if( !DISABLE_GLOBAL_SWEEP ) {
2621 if( writeDebugDOTs ) {
2623 writeGraph( "caller90AfterTransfer",
2624 true, false, false, false, true, true );
2625 } catch( IOException e ) {}
2631 ////////////////////////////////////////////////////
2633 // Abstract garbage collection simply removes
2634 // heap region nodes that are not mechanically
2635 // reachable from a root set. This step is
2636 // essential for testing node and edge existence
2637 // predicates efficiently
2639 ////////////////////////////////////////////////////
2640 public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2642 // calculate a root set, will be different for Java
2643 // version of analysis versus Bamboo version
2644 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2646 // visit every variable in graph while building root
2647 // set, and do iterating on a copy, so we can remove
2648 // dead variables while we're at this
2649 Iterator makeCopyItr = td2vn.entrySet().iterator();
2650 Set entrysCopy = new HashSet();
2651 while( makeCopyItr.hasNext() ) {
2652 entrysCopy.add( makeCopyItr.next() );
2655 Iterator eItr = entrysCopy.iterator();
2656 while( eItr.hasNext() ) {
2657 Map.Entry me = (Map.Entry) eItr.next();
2658 TempDescriptor td = (TempDescriptor) me.getKey();
2659 VariableNode vn = (VariableNode) me.getValue();
2661 if( liveSet.contains( td ) ) {
2665 // dead var, remove completely from graph
2667 clearRefEdgesFrom( vn, null, null, true );
2671 // everything visited in a traversal is
2672 // considered abstractly live
2673 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2675 while( !toVisit.isEmpty() ) {
2676 RefSrcNode rsn = toVisit.iterator().next();
2677 toVisit.remove( rsn );
2680 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2681 while( hrnItr.hasNext() ) {
2682 RefEdge edge = hrnItr.next();
2683 HeapRegionNode hrn = edge.getDst();
2685 if( !visited.contains( hrn ) ) {
2691 // get a copy of the set to iterate over because
2692 // we're going to monkey with the graph when we
2693 // identify a garbage node
2694 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2695 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2696 while( hrnItr.hasNext() ) {
2697 hrnAllPrior.add( hrnItr.next() );
2700 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2701 while( hrnAllItr.hasNext() ) {
2702 HeapRegionNode hrn = hrnAllItr.next();
2704 if( !visited.contains( hrn ) ) {
2706 // heap region nodes are compared across ReachGraph
2707 // objects by their integer ID, so when discarding
2708 // garbage nodes we must also discard entries in
2709 // the ID -> heap region hashtable.
2710 id2hrn.remove( hrn.getID() );
2712 // RefEdge objects are two-way linked between
2713 // nodes, so when a node is identified as garbage,
2714 // actively clear references to and from it so
2715 // live nodes won't have dangling RefEdge's
2716 wipeOut( hrn, true );
2718 // if we just removed the last node from an allocation
2719 // site, it should be taken out of the ReachGraph's list
2720 AllocSite as = hrn.getAllocSite();
2721 if( !hasNodesOf( as ) ) {
2722 allocSites.remove( as );
2728 protected boolean hasNodesOf( AllocSite as ) {
2729 if( id2hrn.containsKey( as.getSummary() ) ) {
2733 for( int i = 0; i < allocationDepth; ++i ) {
2734 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2742 ////////////////////////////////////////////////////
2744 // This global sweep is an optional step to prune
2745 // reachability sets that are not internally
2746 // consistent with the global graph. It should be
2747 // invoked after strong updates or method calls.
2749 ////////////////////////////////////////////////////
2750 public void globalSweep() {
2752 // boldB is part of the phase 1 sweep
2753 // it has an in-context table and an out-of-context table
2754 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2755 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2757 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2758 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2760 // visit every heap region to initialize alphaNew and betaNew,
2761 // and make a map of every hrnID to the source nodes it should
2762 // propagate forward from. In-context flagged hrnID's propagate
2763 // from only the in-context node they name, but out-of-context
2764 // ID's may propagate from several out-of-context nodes
2765 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2766 new Hashtable< Integer, Set<HeapRegionNode> >();
2768 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2769 new Hashtable< Integer, Set<HeapRegionNode> >();
2772 Iterator itrHrns = id2hrn.entrySet().iterator();
2773 while( itrHrns.hasNext() ) {
2774 Map.Entry me = (Map.Entry) itrHrns.next();
2775 Integer hrnID = (Integer) me.getKey();
2776 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2778 // assert that this node and incoming edges have clean alphaNew
2779 // and betaNew sets, respectively
2780 assert rsetEmpty.equals( hrn.getAlphaNew() );
2782 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2783 while( itrRers.hasNext() ) {
2784 RefEdge edge = itrRers.next();
2785 assert rsetEmpty.equals( edge.getBetaNew() );
2788 // calculate boldB for this flagged node, or out-of-context node
2789 if( hrn.isFlagged() ) {
2790 assert !hrn.isOutOfContext();
2791 assert !icID2srcs.containsKey( hrn.getID() );
2792 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2794 icID2srcs.put( hrn.getID(), srcs );
2797 if( hrn.isOutOfContext() ) {
2798 assert !hrn.isFlagged();
2800 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2801 while( stateItr.hasNext() ) {
2802 ReachState state = stateItr.next();
2804 Iterator<ReachTuple> rtItr = state.iterator();
2805 while( rtItr.hasNext() ) {
2806 ReachTuple rt = rtItr.next();
2807 assert rt.isOutOfContext();
2809 Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2810 if( srcs == null ) {
2811 srcs = new HashSet<HeapRegionNode>();
2814 oocID2srcs.put( rt.getHrnID(), srcs );
2820 // calculate boldB for all hrnIDs identified by the above
2821 // node traversal, propagating from every source
2822 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2825 Set<HeapRegionNode> srcs;
2828 if( !icID2srcs.isEmpty() ) {
2829 Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2830 hrnID = (Integer) me.getKey();
2831 srcs = (Set<HeapRegionNode>) me.getValue();
2833 icID2srcs.remove( hrnID );
2836 assert !oocID2srcs.isEmpty();
2838 Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2839 hrnID = (Integer) me.getKey();
2840 srcs = (Set<HeapRegionNode>) me.getValue();
2842 oocID2srcs.remove( hrnID );
2846 Hashtable<RefEdge, ReachSet> boldB_f =
2847 new Hashtable<RefEdge, ReachSet>();
2849 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2851 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2852 while( hrnItr.hasNext() ) {
2853 HeapRegionNode hrn = hrnItr.next();
2855 assert workSetEdges.isEmpty();
2857 // initial boldB_f constraints
2858 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2859 while( itrRees.hasNext() ) {
2860 RefEdge edge = itrRees.next();
2862 assert !boldB_f.containsKey( edge );
2863 boldB_f.put( edge, edge.getBeta() );
2865 assert !workSetEdges.contains( edge );
2866 workSetEdges.add( edge );
2869 // enforce the boldB_f constraint at edges until we reach a fixed point
2870 while( !workSetEdges.isEmpty() ) {
2871 RefEdge edge = workSetEdges.iterator().next();
2872 workSetEdges.remove( edge );
2874 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2875 while( itrPrime.hasNext() ) {
2876 RefEdge edgePrime = itrPrime.next();
2878 ReachSet prevResult = boldB_f.get( edgePrime );
2879 ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2883 if( prevResult == null ||
2884 Canonical.union( prevResult,
2885 intersection ).size() > prevResult.size() ) {
2887 if( prevResult == null ) {
2888 boldB_f.put( edgePrime,
2889 Canonical.union( edgePrime.getBeta(),
2894 boldB_f.put( edgePrime,
2895 Canonical.union( prevResult,
2900 workSetEdges.add( edgePrime );
2907 boldBic.put( hrnID, boldB_f );
2909 boldBooc.put( hrnID, boldB_f );
2914 // use boldB to prune hrnIDs from alpha states that are impossible
2915 // and propagate the differences backwards across edges
2916 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2918 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2919 new Hashtable<RefEdge, ChangeSet>();
2922 itrHrns = id2hrn.entrySet().iterator();
2923 while( itrHrns.hasNext() ) {
2924 Map.Entry me = (Map.Entry) itrHrns.next();
2925 Integer hrnID = (Integer) me.getKey();
2926 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2928 // out-of-context nodes don't participate in the
2929 // global sweep, they serve as sources for the pass
2931 if( hrn.isOutOfContext() ) {
2935 // the inherent states of a region are the exception
2936 // to removal as the global sweep prunes
2937 ReachTuple rtException = ReachTuple.factory( hrnID,
2938 !hrn.isSingleObject(),
2939 ReachTuple.ARITY_ONE,
2940 false // out-of-context
2943 ChangeSet cts = ChangeSet.factory();
2945 // mark hrnIDs for removal
2946 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2947 while( stateItr.hasNext() ) {
2948 ReachState stateOld = stateItr.next();
2950 ReachState markedHrnIDs = ReachState.factory();
2952 Iterator<ReachTuple> rtItr = stateOld.iterator();
2953 while( rtItr.hasNext() ) {
2954 ReachTuple rtOld = rtItr.next();
2956 // never remove the inherent hrnID from a flagged region
2957 // because it is trivially satisfied
2958 if( hrn.isFlagged() ) {
2959 if( rtOld == rtException ) {
2964 // does boldB allow this hrnID?
2965 boolean foundState = false;
2966 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2967 while( incidentEdgeItr.hasNext() ) {
2968 RefEdge incidentEdge = incidentEdgeItr.next();
2970 Hashtable<RefEdge, ReachSet> B;
2971 if( rtOld.isOutOfContext() ) {
2972 B = boldBooc.get( rtOld.getHrnID() );
2974 assert id2hrn.containsKey( rtOld.getHrnID() );
2975 B = boldBic.get( rtOld.getHrnID() );
2979 ReachSet boldB_rtOld_incident = B.get( incidentEdge );
2980 if( boldB_rtOld_incident != null &&
2981 boldB_rtOld_incident.contains( stateOld ) ) {
2988 markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
2992 // if there is nothing marked, just move on
2993 if( markedHrnIDs.isEmpty() ) {
2994 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
3001 // remove all marked hrnIDs and establish a change set that should
3002 // propagate backwards over edges from this node
3003 ReachState statePruned = ReachState.factory();
3004 rtItr = stateOld.iterator();
3005 while( rtItr.hasNext() ) {
3006 ReachTuple rtOld = rtItr.next();
3008 if( !markedHrnIDs.containsTuple( rtOld ) ) {
3009 statePruned = Canonical.union( statePruned, rtOld );
3012 assert !stateOld.equals( statePruned );
3014 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
3018 ChangeTuple ct = ChangeTuple.factory( stateOld,
3021 cts = Canonical.union( cts, ct );
3024 // throw change tuple set on all incident edges
3025 if( !cts.isEmpty() ) {
3026 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3027 while( incidentEdgeItr.hasNext() ) {
3028 RefEdge incidentEdge = incidentEdgeItr.next();
3030 edgesForPropagation.add( incidentEdge );
3032 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3033 edgePlannedChanges.put( incidentEdge, cts );
3035 edgePlannedChanges.put(
3037 Canonical.union( edgePlannedChanges.get( incidentEdge ),
3046 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3048 propagateTokensOverEdges( edgesForPropagation,
3052 // at the end of the 1st phase reference edges have
3053 // beta, betaNew that correspond to beta and betaR
3055 // commit beta<-betaNew, so beta=betaR and betaNew
3056 // will represent the beta' calculation in 2nd phase
3058 // commit alpha<-alphaNew because it won't change
3059 HashSet<RefEdge> res = new HashSet<RefEdge>();
3061 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3062 while( nodeItr.hasNext() ) {
3063 HeapRegionNode hrn = nodeItr.next();
3064 hrn.applyAlphaNew();
3065 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3066 while( itrRes.hasNext() ) {
3067 res.add( itrRes.next() );
3073 Iterator<RefEdge> edgeItr = res.iterator();
3074 while( edgeItr.hasNext() ) {
3075 RefEdge edge = edgeItr.next();
3076 HeapRegionNode hrn = edge.getDst();
3078 // commit results of last phase
3079 if( edgesUpdated.contains( edge ) ) {
3080 edge.applyBetaNew();
3083 // compute intial condition of 2nd phase
3084 edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3090 // every edge in the graph is the initial workset
3091 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3092 while( !edgeWorkSet.isEmpty() ) {
3093 RefEdge edgePrime = edgeWorkSet.iterator().next();
3094 edgeWorkSet.remove( edgePrime );
3096 RefSrcNode rsn = edgePrime.getSrc();
3097 if( !(rsn instanceof HeapRegionNode) ) {
3100 HeapRegionNode hrn = (HeapRegionNode) rsn;
3102 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3103 while( itrEdge.hasNext() ) {
3104 RefEdge edge = itrEdge.next();
3106 ReachSet prevResult = edge.getBetaNew();
3107 assert prevResult != null;
3109 ReachSet intersection =
3110 Canonical.intersection( edge.getBeta(),
3111 edgePrime.getBetaNew()
3114 if( Canonical.union( prevResult,
3116 ).size() > prevResult.size() ) {
3118 Canonical.union( prevResult,
3122 edgeWorkSet.add( edge );
3127 // commit beta' (beta<-betaNew)
3128 edgeItr = res.iterator();
3129 while( edgeItr.hasNext() ) {
3130 edgeItr.next().applyBetaNew();
3136 ////////////////////////////////////////////////////
3137 // high-level merge operations
3138 ////////////////////////////////////////////////////
3139 public void merge_sameMethodContext( ReachGraph rg ) {
3140 // when merging two graphs that abstract the heap
3141 // of the same method context, we just call the
3142 // basic merge operation
3146 public void merge_diffMethodContext( ReachGraph rg ) {
3147 // when merging graphs for abstract heaps in
3148 // different method contexts we should:
3149 // 1) age the allocation sites?
3153 ////////////////////////////////////////////////////
3154 // in merge() and equals() methods the suffix A
3155 // represents the passed in graph and the suffix
3156 // B refers to the graph in this object
3157 // Merging means to take the incoming graph A and
3158 // merge it into B, so after the operation graph B
3159 // is the final result.
3160 ////////////////////////////////////////////////////
3161 protected void merge( ReachGraph rg ) {
3168 mergeRefEdges ( rg );
3169 mergeAllocSites( rg );
3172 protected void mergeNodes( ReachGraph rg ) {
3174 // start with heap region nodes
3175 Set sA = rg.id2hrn.entrySet();
3176 Iterator iA = sA.iterator();
3177 while( iA.hasNext() ) {
3178 Map.Entry meA = (Map.Entry) iA.next();
3179 Integer idA = (Integer) meA.getKey();
3180 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3182 // if this graph doesn't have a node the
3183 // incoming graph has, allocate it
3184 if( !id2hrn.containsKey( idA ) ) {
3185 HeapRegionNode hrnB = hrnA.copy();
3186 id2hrn.put( idA, hrnB );
3189 // otherwise this is a node present in both graphs
3190 // so make the new reachability set a union of the
3191 // nodes' reachability sets
3192 HeapRegionNode hrnB = id2hrn.get( idA );
3193 hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
3198 // if hrnB is already dirty or hrnA is dirty,
3199 // the hrnB should end up dirty: TODO
3201 if( !hrnA.isClean() ) {
3202 hrnB.setIsClean( false );
3208 // now add any variable nodes that are in graph B but
3210 sA = rg.td2vn.entrySet();
3212 while( iA.hasNext() ) {
3213 Map.Entry meA = (Map.Entry) iA.next();
3214 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3215 VariableNode lnA = (VariableNode) meA.getValue();
3217 // if the variable doesn't exist in B, allocate and add it
3218 VariableNode lnB = getVariableNodeFromTemp( tdA );
3222 protected void mergeRefEdges( ReachGraph rg ) {
3224 // between heap regions
3225 Set sA = rg.id2hrn.entrySet();
3226 Iterator iA = sA.iterator();
3227 while( iA.hasNext() ) {
3228 Map.Entry meA = (Map.Entry) iA.next();
3229 Integer idA = (Integer) meA.getKey();
3230 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3232 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3233 while( heapRegionsItrA.hasNext() ) {
3234 RefEdge edgeA = heapRegionsItrA.next();
3235 HeapRegionNode hrnChildA = edgeA.getDst();
3236 Integer idChildA = hrnChildA.getID();
3238 // at this point we know an edge in graph A exists
3239 // idA -> idChildA, does this exist in B?
3240 assert id2hrn.containsKey( idA );
3241 HeapRegionNode hrnB = id2hrn.get( idA );
3242 RefEdge edgeToMerge = null;
3244 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3245 while( heapRegionsItrB.hasNext() &&
3246 edgeToMerge == null ) {
3248 RefEdge edgeB = heapRegionsItrB.next();
3249 HeapRegionNode hrnChildB = edgeB.getDst();
3250 Integer idChildB = hrnChildB.getID();
3252 // don't use the RefEdge.equals() here because
3253 // we're talking about existence between graphs,
3254 // not intragraph equal
3255 if( idChildB.equals( idChildA ) &&
3256 edgeB.typeAndFieldEquals( edgeA ) ) {
3258 edgeToMerge = edgeB;
3262 // if the edge from A was not found in B,
3264 if( edgeToMerge == null ) {
3265 assert id2hrn.containsKey( idChildA );
3266 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3267 edgeToMerge = edgeA.copy();
3268 edgeToMerge.setSrc( hrnB );
3269 edgeToMerge.setDst( hrnChildB );
3270 addRefEdge( hrnB, hrnChildB, edgeToMerge );
3272 // otherwise, the edge already existed in both graphs
3273 // so merge their reachability sets
3275 // just replace this beta set with the union
3276 assert edgeToMerge != null;
3277 edgeToMerge.setBeta(
3278 Canonical.union( edgeToMerge.getBeta(),
3284 if( !edgeA.isClean() ) {
3285 edgeToMerge.setIsClean( false );
3292 // and then again from variable nodes
3293 sA = rg.td2vn.entrySet();
3295 while( iA.hasNext() ) {
3296 Map.Entry meA = (Map.Entry) iA.next();
3297 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3298 VariableNode vnA = (VariableNode) meA.getValue();
3300 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3301 while( heapRegionsItrA.hasNext() ) {
3302 RefEdge edgeA = heapRegionsItrA.next();
3303 HeapRegionNode hrnChildA = edgeA.getDst();
3304 Integer idChildA = hrnChildA.getID();
3306 // at this point we know an edge in graph A exists
3307 // tdA -> idChildA, does this exist in B?
3308 assert td2vn.containsKey( tdA );
3309 VariableNode vnB = td2vn.get( tdA );
3310 RefEdge edgeToMerge = null;
3312 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3313 while( heapRegionsItrB.hasNext() &&
3314 edgeToMerge == null ) {
3316 RefEdge edgeB = heapRegionsItrB.next();
3317 HeapRegionNode hrnChildB = edgeB.getDst();
3318 Integer idChildB = hrnChildB.getID();
3320 // don't use the RefEdge.equals() here because
3321 // we're talking about existence between graphs
3322 if( idChildB.equals( idChildA ) &&
3323 edgeB.typeAndFieldEquals( edgeA ) ) {
3325 edgeToMerge = edgeB;
3329 // if the edge from A was not found in B,
3331 if( edgeToMerge == null ) {
3332 assert id2hrn.containsKey( idChildA );
3333 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3334 edgeToMerge = edgeA.copy();
3335 edgeToMerge.setSrc( vnB );
3336 edgeToMerge.setDst( hrnChildB );
3337 addRefEdge( vnB, hrnChildB, edgeToMerge );
3339 // otherwise, the edge already existed in both graphs
3340 // so merge their reachability sets
3342 // just replace this beta set with the union
3343 edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
3349 if( !edgeA.isClean() ) {
3350 edgeToMerge.setIsClean( false );
3358 protected void mergeAllocSites( ReachGraph rg ) {
3359 allocSites.addAll( rg.allocSites );
3363 // it is necessary in the equals() member functions
3364 // to "check both ways" when comparing the data
3365 // structures of two graphs. For instance, if all
3366 // edges between heap region nodes in graph A are
3367 // present and equal in graph B it is not sufficient
3368 // to say the graphs are equal. Consider that there
3369 // may be edges in graph B that are not in graph A.
3370 // the only way to know that all edges in both graphs
3371 // are equally present is to iterate over both data
3372 // structures and compare against the other graph.
3373 public boolean equals( ReachGraph rg ) {
3379 if( !areHeapRegionNodesEqual( rg ) ) {
3383 if( !areVariableNodesEqual( rg ) ) {
3387 if( !areRefEdgesEqual( rg ) ) {
3391 // if everything is equal up to this point,
3392 // assert that allocSites is also equal--
3393 // this data is redundant but kept for efficiency
3394 assert allocSites.equals( rg.allocSites );
3400 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3402 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3406 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3413 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3415 Set sA = rgA.id2hrn.entrySet();
3416 Iterator iA = sA.iterator();
3417 while( iA.hasNext() ) {
3418 Map.Entry meA = (Map.Entry) iA.next();
3419 Integer idA = (Integer) meA.getKey();
3420 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3422 if( !rgB.id2hrn.containsKey( idA ) ) {
3426 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3427 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3436 protected boolean areVariableNodesEqual( ReachGraph rg ) {
3438 if( !areallVNinAalsoinBandequal( this, rg ) ) {
3442 if( !areallVNinAalsoinBandequal( rg, this ) ) {
3449 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3451 Set sA = rgA.td2vn.entrySet();
3452 Iterator iA = sA.iterator();
3453 while( iA.hasNext() ) {
3454 Map.Entry meA = (Map.Entry) iA.next();
3455 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3457 if( !rgB.td2vn.containsKey( tdA ) ) {
3466 protected boolean areRefEdgesEqual( ReachGraph rg ) {
3467 if( !areallREinAandBequal( this, rg ) ) {
3474 static protected boolean areallREinAandBequal( ReachGraph rgA,
3477 // check all the heap region->heap region edges
3478 Set sA = rgA.id2hrn.entrySet();
3479 Iterator iA = sA.iterator();
3480 while( iA.hasNext() ) {
3481 Map.Entry meA = (Map.Entry) iA.next();
3482 Integer idA = (Integer) meA.getKey();
3483 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3485 // we should have already checked that the same
3486 // heap regions exist in both graphs
3487 assert rgB.id2hrn.containsKey( idA );
3489 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3493 // then check every edge in B for presence in A, starting
3494 // from the same parent HeapRegionNode
3495 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3497 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3502 // then check all the variable->heap region edges
3503 sA = rgA.td2vn.entrySet();
3505 while( iA.hasNext() ) {
3506 Map.Entry meA = (Map.Entry) iA.next();
3507 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3508 VariableNode vnA = (VariableNode) meA.getValue();
3510 // we should have already checked that the same
3511 // label nodes exist in both graphs
3512 assert rgB.td2vn.containsKey( tdA );
3514 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3518 // then check every edge in B for presence in A, starting
3519 // from the same parent VariableNode
3520 VariableNode vnB = rgB.td2vn.get( tdA );
3522 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3531 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3535 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3536 while( itrA.hasNext() ) {
3537 RefEdge edgeA = itrA.next();
3538 HeapRegionNode hrnChildA = edgeA.getDst();
3539 Integer idChildA = hrnChildA.getID();
3541 assert rgB.id2hrn.containsKey( idChildA );
3543 // at this point we know an edge in graph A exists
3544 // rnA -> idChildA, does this exact edge exist in B?
3545 boolean edgeFound = false;
3547 RefSrcNode rnB = null;
3548 if( rnA instanceof HeapRegionNode ) {
3549 HeapRegionNode hrnA = (HeapRegionNode) rnA;
3550 rnB = rgB.id2hrn.get( hrnA.getID() );
3552 VariableNode vnA = (VariableNode) rnA;
3553 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3556 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3557 while( itrB.hasNext() ) {
3558 RefEdge edgeB = itrB.next();
3559 HeapRegionNode hrnChildB = edgeB.getDst();
3560 Integer idChildB = hrnChildB.getID();
3562 if( idChildA.equals( idChildB ) &&
3563 edgeA.typeAndFieldEquals( edgeB ) ) {
3565 // there is an edge in the right place with the right field,
3566 // but do they have the same attributes?
3567 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3568 edgeA.equalsPreds( edgeB )
3585 // this analysis no longer has the "match anything"
3586 // type which was represented by null
3587 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3588 TypeDescriptor td2 ) {
3592 if( td1.isNull() ) {
3595 if( td2.isNull() ) {
3598 return typeUtil.mostSpecific( td1, td2 );
3601 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3603 TypeDescriptor td3 ) {
3605 return mostSpecificType( td1,
3606 mostSpecificType( td2, td3 )
3610 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3613 TypeDescriptor td4 ) {
3615 return mostSpecificType( mostSpecificType( td1, td2 ),
3616 mostSpecificType( td3, td4 )
3620 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3621 TypeDescriptor possibleChild ) {
3622 assert possibleSuper != null;
3623 assert possibleChild != null;
3625 if( possibleSuper.isNull() ||
3626 possibleChild.isNull() ) {
3630 return typeUtil.isSuperorType( possibleSuper, possibleChild );
3634 protected boolean hasMatchingField( HeapRegionNode src,
3637 TypeDescriptor tdSrc = src.getType();
3638 assert tdSrc != null;
3640 if( tdSrc.isArray() ) {
3641 TypeDescriptor td = edge.getType();
3644 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3645 assert tdSrcDeref != null;
3647 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3651 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3654 // if it's not a class, it doesn't have any fields to match
3655 if( !tdSrc.isClass() ) {
3659 ClassDescriptor cd = tdSrc.getClassDesc();
3660 while( cd != null ) {
3661 Iterator fieldItr = cd.getFields();
3663 while( fieldItr.hasNext() ) {
3664 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3666 if( fd.getType().equals( edge.getType() ) &&
3667 fd.getSymbol().equals( edge.getField() ) ) {
3672 cd = cd.getSuperDesc();
3675 // otherwise it is a class with fields
3676 // but we didn't find a match
3680 protected boolean hasMatchingType( RefEdge edge,
3681 HeapRegionNode dst ) {
3683 // if the region has no type, matches everything
3684 TypeDescriptor tdDst = dst.getType();
3685 assert tdDst != null;
3687 // if the type is not a class or an array, don't
3688 // match because primitives are copied, no aliases
3689 ClassDescriptor cdDst = tdDst.getClassDesc();
3690 if( cdDst == null && !tdDst.isArray() ) {
3694 // if the edge type is null, it matches everything
3695 TypeDescriptor tdEdge = edge.getType();
3696 assert tdEdge != null;
3698 return typeUtil.isSuperorType( tdEdge, tdDst );
3703 public void writeGraph( String graphName,
3704 boolean writeLabels,
3705 boolean labelSelect,
3706 boolean pruneGarbage,
3707 boolean writeReferencers,
3708 boolean hideSubsetReachability,
3709 boolean hideEdgeTaints
3710 ) throws java.io.IOException {
3711 writeGraph( graphName,
3716 hideSubsetReachability,
3721 public void writeGraph( String graphName,
3722 boolean writeLabels,
3723 boolean labelSelect,
3724 boolean pruneGarbage,
3725 boolean writeReferencers,
3726 boolean hideSubsetReachability,
3727 boolean hideEdgeTaints,
3728 Set<Integer> callerNodeIDsCopiedToCallee
3729 ) throws java.io.IOException {
3731 // remove all non-word characters from the graph name so
3732 // the filename and identifier in dot don't cause errors
3733 graphName = graphName.replaceAll( "[\\W]", "" );
3736 new BufferedWriter( new FileWriter( graphName+".dot" ) );
3738 bw.write( "digraph "+graphName+" {\n" );
3741 // this is an optional step to form the callee-reachable
3742 // "cut-out" into a DOT cluster for visualization
3743 if( callerNodeIDsCopiedToCallee != null ) {
3745 bw.write( " subgraph cluster0 {\n" );
3746 bw.write( " color=blue;\n" );
3748 Iterator i = id2hrn.entrySet().iterator();
3749 while( i.hasNext() ) {
3750 Map.Entry me = (Map.Entry) i.next();
3751 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3753 if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3754 bw.write( " "+hrn.toString()+
3755 hrn.toStringDOT( hideSubsetReachability )+
3765 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3767 // then visit every heap region node
3768 Iterator i = id2hrn.entrySet().iterator();
3769 while( i.hasNext() ) {
3770 Map.Entry me = (Map.Entry) i.next();
3771 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3773 // only visit nodes worth writing out--for instance
3774 // not every node at an allocation is referenced
3775 // (think of it as garbage-collected), etc.
3776 if( !pruneGarbage ||
3777 (hrn.isFlagged() && hrn.getID() > 0) ||
3778 hrn.getDescription().startsWith( "param" ) ||
3779 hrn.isOutOfContext()
3782 if( !visited.contains( hrn ) ) {
3783 traverseHeapRegionNodes( hrn,
3788 hideSubsetReachability,
3790 callerNodeIDsCopiedToCallee );
3795 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
3798 // then visit every label node, useful for debugging
3800 i = td2vn.entrySet().iterator();
3801 while( i.hasNext() ) {
3802 Map.Entry me = (Map.Entry) i.next();
3803 VariableNode vn = (VariableNode) me.getValue();
3806 String labelStr = vn.getTempDescriptorString();
3807 if( labelStr.startsWith("___temp") ||
3808 labelStr.startsWith("___dst") ||
3809 labelStr.startsWith("___srctmp") ||
3810 labelStr.startsWith("___neverused")
3816 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3817 while( heapRegionsItr.hasNext() ) {
3818 RefEdge edge = heapRegionsItr.next();
3819 HeapRegionNode hrn = edge.getDst();
3821 if( pruneGarbage && !visited.contains( hrn ) ) {
3822 traverseHeapRegionNodes( hrn,
3827 hideSubsetReachability,
3829 callerNodeIDsCopiedToCallee );
3832 bw.write( " "+vn.toString()+
3833 " -> "+hrn.toString()+
3834 edge.toStringDOT( hideSubsetReachability, "" )+
3844 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
3847 Set<HeapRegionNode> visited,
3848 boolean writeReferencers,
3849 boolean hideSubsetReachability,
3850 boolean hideEdgeTaints,
3851 Set<Integer> callerNodeIDsCopiedToCallee
3852 ) throws java.io.IOException {
3854 if( visited.contains( hrn ) ) {
3859 // if we're drawing the callee-view subgraph, only
3860 // write out the node info if it hasn't already been
3862 if( callerNodeIDsCopiedToCallee == null ||
3863 !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3865 bw.write( " "+hrn.toString()+
3866 hrn.toStringDOT( hideSubsetReachability )+
3870 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3871 while( childRegionsItr.hasNext() ) {
3872 RefEdge edge = childRegionsItr.next();
3873 HeapRegionNode hrnChild = edge.getDst();
3875 if( callerNodeIDsCopiedToCallee != null &&
3876 (edge.getSrc() instanceof HeapRegionNode) ) {
3877 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3878 if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
3879 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3881 bw.write( " "+hrn.toString()+
3882 " -> "+hrnChild.toString()+
3883 edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
3885 } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
3886 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3888 bw.write( " "+hrn.toString()+
3889 " -> "+hrnChild.toString()+
3890 edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
3893 bw.write( " "+hrn.toString()+
3894 " -> "+hrnChild.toString()+
3895 edge.toStringDOT( hideSubsetReachability, "" )+
3899 bw.write( " "+hrn.toString()+
3900 " -> "+hrnChild.toString()+
3901 edge.toStringDOT( hideSubsetReachability, "" )+
3905 traverseHeapRegionNodes( hrnChild,
3910 hideSubsetReachability,
3912 callerNodeIDsCopiedToCallee );