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
1479 // first traverse this context to find nodes and edges
1480 // that will be callee-reachable
1481 Set<HeapRegionNode> reachableCallerNodes =
1482 new HashSet<HeapRegionNode>();
1484 // caller edges between callee-reachable nodes
1485 Set<RefEdge> reachableCallerEdges =
1486 new HashSet<RefEdge>();
1488 // caller edges from arg vars, and the matching param index
1489 // because these become a special edge in callee
1490 Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1491 new Hashtable<RefEdge, Integer>();
1493 // caller edges from local vars or callee-unreachable nodes
1494 // (out-of-context sources) to callee-reachable nodes
1495 Set<RefEdge> oocCallerEdges =
1496 new HashSet<RefEdge>();
1499 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1501 TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1502 VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
1504 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1505 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1507 toVisitInCaller.add( vnArgCaller );
1509 while( !toVisitInCaller.isEmpty() ) {
1510 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1511 toVisitInCaller.remove( rsnCaller );
1512 visitedInCaller.add( rsnCaller );
1514 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1515 while( itrRefEdges.hasNext() ) {
1516 RefEdge reCaller = itrRefEdges.next();
1517 HeapRegionNode hrnCaller = reCaller.getDst();
1519 callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
1520 reachableCallerNodes.add( hrnCaller );
1522 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1523 reachableCallerEdges.add( reCaller );
1525 if( rsnCaller.equals( vnArgCaller ) ) {
1526 reachableCallerArgEdges2paramIndex.put( reCaller, i );
1528 oocCallerEdges.add( reCaller );
1532 if( !visitedInCaller.contains( hrnCaller ) ) {
1533 toVisitInCaller.add( hrnCaller );
1536 } // end edge iteration
1537 } // end visiting heap nodes in caller
1538 } // end iterating over parameters as starting points
1541 // now collect out-of-context reach tuples and
1542 // more out-of-context edges
1543 Set<ReachTuple> oocTuples = new HashSet<ReachTuple>();
1545 Iterator<Integer> itrInContext =
1546 callerNodeIDsCopiedToCallee.iterator();
1547 while( itrInContext.hasNext() ) {
1548 Integer hrnID = itrInContext.next();
1549 HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1551 Iterator<RefEdge> itrMightCross =
1552 hrnCallerAndInContext.iteratorToReferencers();
1553 while( itrMightCross.hasNext() ) {
1554 RefEdge edgeMightCross = itrMightCross.next();
1556 RefSrcNode rsnCallerAndOutContext =
1557 edgeMightCross.getSrc();
1559 if( rsnCallerAndOutContext instanceof VariableNode ) {
1560 // variables do not have out-of-context reach states,
1562 oocCallerEdges.add( edgeMightCross );
1566 HeapRegionNode hrnCallerAndOutContext =
1567 (HeapRegionNode) rsnCallerAndOutContext;
1569 // is this source node out-of-context?
1570 if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1571 // no, skip this edge
1576 oocCallerEdges.add( edgeMightCross );
1578 // add all reach tuples on the node to list
1579 // of things that are out-of-context: insight
1580 // if this node is reachable from someting that WAS
1581 // in-context, then this node should already be in-context
1582 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1583 while( stateItr.hasNext() ) {
1584 ReachState state = stateItr.next();
1586 Iterator<ReachTuple> rtItr = state.iterator();
1587 while( rtItr.hasNext() ) {
1588 ReachTuple rt = rtItr.next();
1590 oocTuples.add( rt );
1597 // the callee view is a new graph: DON'T MODIFY *THIS* graph
1598 ReachGraph rg = new ReachGraph();
1600 // add nodes to callee graph
1601 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1602 while( hrnItr.hasNext() ) {
1603 HeapRegionNode hrnCaller = hrnItr.next();
1605 assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
1606 assert !rg.id2hrn.containsKey( hrnCaller.getID() );
1608 ExistPred pred = ExistPred.factory( hrnCaller.getID(), null );
1609 ExistPredSet preds = ExistPredSet.factory( pred );
1611 rg.createNewHeapRegionNode( hrnCaller.getID(),
1612 hrnCaller.isSingleObject(),
1613 hrnCaller.isNewSummary(),
1614 hrnCaller.isFlagged(),
1615 false, // out-of-context?
1616 hrnCaller.getType(),
1617 hrnCaller.getAllocSite(),
1618 toCalleeContext( oocTuples,
1619 hrnCaller.getInherent(), // in state
1620 hrnCaller.getID(), // node pred
1621 null, null, null, null, null, // edge pred
1622 false ), // ooc pred
1623 toCalleeContext( oocTuples,
1624 hrnCaller.getAlpha(), // in state
1625 hrnCaller.getID(), // node pred
1626 null, null, null, null, null, // edge pred
1627 false ), // ooc pred
1629 hrnCaller.getDescription()
1633 // add param edges to callee graph
1635 reachableCallerArgEdges2paramIndex.entrySet().iterator();
1636 while( argEdges.hasNext() ) {
1637 Map.Entry me = (Map.Entry) argEdges.next();
1638 RefEdge reArg = (RefEdge) me.getKey();
1639 Integer index = (Integer) me.getValue();
1641 TempDescriptor arg = fmCallee.getParameter( index );
1643 VariableNode vnCallee =
1644 rg.getVariableNodeFromTemp( arg );
1646 HeapRegionNode hrnDstCaller = reArg.getDst();
1647 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1648 assert hrnDstCallee != null;
1651 ExistPred.factory( arg,
1653 hrnDstCallee.getID(),
1657 false ); // out-of-context
1659 ExistPredSet preds =
1660 ExistPredSet.factory( pred );
1663 new RefEdge( vnCallee,
1667 toCalleeContext( oocTuples,
1668 reArg.getBeta(), // in state
1672 hrnDstCallee.getID(), // edge pred
1673 reArg.getType(), // edge pred
1674 reArg.getField(), // edge pred
1675 false ), // ooc pred
1679 rg.addRefEdge( vnCallee,
1685 // add in-context edges to callee graph
1686 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1687 while( reItr.hasNext() ) {
1688 RefEdge reCaller = reItr.next();
1689 RefSrcNode rsnCaller = reCaller.getSrc();
1690 assert rsnCaller instanceof HeapRegionNode;
1691 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1692 HeapRegionNode hrnDstCaller = reCaller.getDst();
1694 HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
1695 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1696 assert hrnSrcCallee != null;
1697 assert hrnDstCallee != null;
1700 ExistPred.factory( null,
1701 hrnSrcCallee.getID(),
1702 hrnDstCallee.getID(),
1704 reCaller.getField(),
1706 false ); // out-of-context
1708 ExistPredSet preds =
1709 ExistPredSet.factory( pred );
1712 new RefEdge( hrnSrcCallee,
1715 reCaller.getField(),
1716 toCalleeContext( oocTuples,
1717 reCaller.getBeta(), // in state
1720 hrnSrcCallee.getID(), // edge pred
1721 hrnDstCallee.getID(), // edge pred
1722 reCaller.getType(), // edge pred
1723 reCaller.getField(), // edge pred
1724 false ), // ooc pred
1728 rg.addRefEdge( hrnSrcCallee,
1734 // add out-of-context edges to callee graph
1735 reItr = oocCallerEdges.iterator();
1736 while( reItr.hasNext() ) {
1737 RefEdge reCaller = reItr.next();
1738 RefSrcNode rsnCaller = reCaller.getSrc();
1739 HeapRegionNode hrnDstCaller = reCaller.getDst();
1740 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1741 assert hrnDstCallee != null;
1743 TypeDescriptor oocNodeType;
1745 TempDescriptor oocPredSrcTemp = null;
1746 Integer oocPredSrcID = null;
1748 if( rsnCaller instanceof VariableNode ) {
1749 VariableNode vnCaller = (VariableNode) rsnCaller;
1751 oocReach = rsetEmpty;
1752 oocPredSrcTemp = vnCaller.getTempDescriptor();
1755 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1756 assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
1757 oocNodeType = hrnSrcCaller.getType();
1758 oocReach = hrnSrcCaller.getAlpha();
1759 oocPredSrcID = hrnSrcCaller.getID();
1763 ExistPred.factory( oocPredSrcTemp,
1765 hrnDstCallee.getID(),
1767 reCaller.getField(),
1769 true ); // out-of-context
1771 ExistPredSet preds =
1772 ExistPredSet.factory( pred );
1774 RefEdge oocEdgeExisting =
1775 rg.getOutOfContextReferenceTo( hrnDstCallee,
1781 if( oocEdgeExisting == null ) {
1782 // for consistency, map one out-of-context "identifier"
1783 // to one heap region node id, otherwise no convergence
1784 String oocid = "oocid"+
1786 hrnDstCallee.getIDString()+
1789 reCaller.getField();
1791 Integer oocHrnID = oocid2hrnid.get( oocid );
1793 HeapRegionNode hrnCalleeAndOutContext;
1795 if( oocHrnID == null ) {
1797 hrnCalleeAndOutContext =
1798 rg.createNewHeapRegionNode( null, // ID
1799 false, // single object?
1800 false, // new summary?
1802 true, // out-of-context?
1804 null, // alloc site, shouldn't be used
1805 toCalleeContext( oocTuples,
1806 oocReach, // in state
1808 null, null, null, null, null, // edge pred
1811 toCalleeContext( oocTuples,
1812 oocReach, // in state
1814 null, null, null, null, null, // edge pred
1821 oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1825 // the mapping already exists, so see if node is there
1826 hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1828 if( hrnCalleeAndOutContext == null ) {
1830 hrnCalleeAndOutContext =
1831 rg.createNewHeapRegionNode( oocHrnID, // ID
1832 false, // single object?
1833 false, // new summary?
1835 true, // out-of-context?
1837 null, // alloc site, shouldn't be used
1838 toCalleeContext( oocTuples,
1839 oocReach, // in state
1841 null, null, null, null, null, // edge pred
1844 toCalleeContext( oocTuples,
1845 oocReach, // in state
1847 null, null, null, null, null, // edge pred
1856 rg.addRefEdge( hrnCalleeAndOutContext,
1858 new RefEdge( hrnCalleeAndOutContext,
1861 reCaller.getField(),
1862 toCalleeContext( oocTuples,
1863 reCaller.getBeta(), // in state
1865 oocPredSrcTemp, // edge pred
1866 oocPredSrcID, // edge pred
1867 hrnDstCaller.getID(), // edge pred
1868 reCaller.getType(), // edge pred
1869 reCaller.getField(), // edge pred
1877 // the out-of-context edge already exists
1878 oocEdgeExisting.setBeta( Canonical.union( oocEdgeExisting.getBeta(),
1879 toCalleeContext( oocTuples,
1880 reCaller.getBeta(), // in state
1882 oocPredSrcTemp, // edge pred
1883 oocPredSrcID, // edge pred
1884 hrnDstCaller.getID(), // edge pred
1885 reCaller.getType(), // edge pred
1886 reCaller.getField(), // edge pred
1892 oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1901 if( writeDebugDOTs ) {
1903 rg.writeGraph( "calleeview", true, false, false, false, true, true );
1904 } catch( IOException e ) {}
1910 private static Hashtable<String, Integer> oocid2hrnid =
1911 new Hashtable<String, Integer>();
1916 resolveMethodCall( FlatCall fc,
1917 FlatMethod fmCallee,
1918 ReachGraph rgCallee,
1919 Set<Integer> callerNodeIDsCopiedToCallee,
1920 boolean writeDebugDOTs
1924 if( writeDebugDOTs ) {
1926 rgCallee.writeGraph( "callee",
1927 true, false, false, false, true, true );
1928 writeGraph( "caller00In",
1929 true, false, false, false, true, true,
1930 callerNodeIDsCopiedToCallee );
1931 } catch( IOException e ) {}
1935 // method call transfer function steps:
1936 // 1. Use current callee-reachable heap (CRH) to test callee
1937 // predicates and mark what will be coming in.
1938 // 2. Wipe CRH out of caller.
1939 // 3. Transplant marked callee parts in:
1940 // a) bring in nodes
1941 // b) bring in callee -> callee edges
1942 // c) resolve out-of-context -> callee edges
1943 // d) assign return value
1944 // 4. Collapse shadow nodes down
1945 // 5. Global sweep it.
1949 // 1. mark what callee elements have satisfied predicates
1950 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1951 new Hashtable<HeapRegionNode, ExistPredSet>();
1953 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1954 new Hashtable<RefEdge, ExistPredSet>();
1956 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1957 new Hashtable<ReachState, ExistPredSet>();
1959 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1960 new Hashtable< RefEdge, Set<RefSrcNode> >();
1962 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1963 while( meItr.hasNext() ) {
1964 Map.Entry me = (Map.Entry) meItr.next();
1965 Integer id = (Integer) me.getKey();
1966 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1968 // if a callee element's predicates are satisfied then a set
1969 // of CALLER predicates is returned: they are the predicates
1970 // that the callee element moved into the caller context
1971 // should have, and it is inefficient to find this again later
1972 ExistPredSet predsIfSatis =
1973 hrnCallee.getPreds().isSatisfiedBy( this,
1974 callerNodeIDsCopiedToCallee
1976 if( predsIfSatis != null ) {
1977 calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1979 // otherwise don't bother looking at edges to this node
1983 // since the node is coming over, find out which reach
1984 // states on it should come over, too
1985 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
1986 while( stateItr.hasNext() ) {
1987 ReachState stateCallee = stateItr.next();
1990 stateCallee.getPreds().isSatisfiedBy( this,
1991 callerNodeIDsCopiedToCallee
1993 if( predsIfSatis != null ) {
1994 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
1998 // then look at edges to the node
1999 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2000 while( reItr.hasNext() ) {
2001 RefEdge reCallee = reItr.next();
2002 RefSrcNode rsnCallee = reCallee.getSrc();
2004 // (caller local variables to in-context heap regions)
2005 // have an (out-of-context heap region -> in-context heap region)
2006 // abstraction in the callEE, so its true we never need to
2007 // look at a (var node -> heap region) edge in callee to bring
2008 // those over for the call site transfer. What about (param var->heap region)
2009 // edges in callee? They are dealt with below this loop.
2010 // So, yes, at this point skip (var->region) edges in callee
2011 if( rsnCallee instanceof VariableNode ) {
2015 // first see if the source is out-of-context, and only
2016 // proceed with this edge if we find some caller-context
2018 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2019 boolean matchedOutOfContext = false;
2021 if( hrnSrcCallee.isOutOfContext() ) {
2023 assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2024 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2026 HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2027 Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2028 while( reDstItr.hasNext() ) {
2029 // the edge and field (either possibly null) must match
2030 RefEdge reCaller = reDstItr.next();
2032 if( !reCaller.typeEquals ( reCallee.getType() ) ||
2033 !reCaller.fieldEquals( reCallee.getField() )
2038 RefSrcNode rsnCaller = reCaller.getSrc();
2039 if( rsnCaller instanceof VariableNode ) {
2040 // a variable node matches an OOC region with null type
2041 if( hrnSrcCallee.getType() != null ) {
2046 // otherwise types should match
2047 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2048 if( hrnSrcCallee.getType() == null ) {
2049 if( hrnCallerSrc.getType() != null ) {
2053 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2059 rsnCallers.add( rsnCaller );
2060 matchedOutOfContext = true;
2063 if( !rsnCallers.isEmpty() ) {
2064 calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2068 if( hrnSrcCallee.isOutOfContext() &&
2069 !matchedOutOfContext ) {
2074 reCallee.getPreds().isSatisfiedBy( this,
2075 callerNodeIDsCopiedToCallee
2077 if( predsIfSatis != null ) {
2078 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2080 // since the edge is coming over, find out which reach
2081 // states on it should come over, too
2082 stateItr = reCallee.getBeta().iterator();
2083 while( stateItr.hasNext() ) {
2084 ReachState stateCallee = stateItr.next();
2087 stateCallee.getPreds().isSatisfiedBy( this,
2088 callerNodeIDsCopiedToCallee
2090 if( predsIfSatis != null ) {
2091 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2100 // test param -> HRN edges, also
2101 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
2103 // parameter defined here is the symbol in the callee
2104 TempDescriptor tdParam = fmCallee.getParameter( i );
2105 VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
2107 Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
2108 while( reItr.hasNext() ) {
2109 RefEdge reCallee = reItr.next();
2111 ExistPredSet ifDst =
2112 reCallee.getDst().getPreds().isSatisfiedBy( this,
2113 callerNodeIDsCopiedToCallee
2115 if( ifDst == null ) {
2119 ExistPredSet predsIfSatis =
2120 reCallee.getPreds().isSatisfiedBy( this,
2121 callerNodeIDsCopiedToCallee
2123 if( predsIfSatis != null ) {
2124 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2126 // since the edge is coming over, find out which reach
2127 // states on it should come over, too
2128 Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
2129 while( stateItr.hasNext() ) {
2130 ReachState stateCallee = stateItr.next();
2133 stateCallee.getPreds().isSatisfiedBy( this,
2134 callerNodeIDsCopiedToCallee
2136 if( predsIfSatis != null ) {
2137 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2148 if( writeDebugDOTs ) {
2150 writeGraph( "caller20BeforeWipe",
2151 true, false, false, false, true, true );
2152 } catch( IOException e ) {}
2156 // 2. predicates tested, ok to wipe out caller part
2157 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2158 while( hrnItr.hasNext() ) {
2159 Integer hrnID = hrnItr.next();
2160 HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2161 assert hrnCaller != null;
2163 // when clearing off nodes, also eliminate variable
2165 wipeOut( hrnCaller, true );
2170 if( writeDebugDOTs ) {
2172 writeGraph( "caller30BeforeAddingNodes",
2173 true, false, false, false, true, true );
2174 } catch( IOException e ) {}
2178 // 3. callee elements with satisfied preds come in, note that
2179 // the mapping of elements satisfied to preds is like this:
2180 // A callee element EE has preds EEp that are satisfied by
2181 // some caller element ER. We bring EE into the caller
2182 // context as ERee with the preds of ER, namely ERp, which
2183 // in the following algorithm is the value in the mapping
2186 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2187 while( satisItr.hasNext() ) {
2188 Map.Entry me = (Map.Entry) satisItr.next();
2189 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2190 ExistPredSet preds = (ExistPredSet) me.getValue();
2192 // TODO: I think its true that the current implementation uses
2193 // the type of the OOC region and the predicates OF THE EDGE from
2194 // it to link everything up in caller context, so that's why we're
2195 // skipping this... maybe that's a sillier way to do it?
2196 if( hrnCallee.isOutOfContext() ) {
2200 AllocSite as = hrnCallee.getAllocSite();
2201 allocSites.add( as );
2203 Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2205 HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2206 if( hrnCaller == null ) {
2208 createNewHeapRegionNode( hrnIDshadow, // id or null to generate a new one
2209 hrnCallee.isSingleObject(), // single object?
2210 hrnCallee.isNewSummary(), // summary?
2211 hrnCallee.isFlagged(), // flagged?
2212 false, // out-of-context?
2213 hrnCallee.getType(), // type
2214 hrnCallee.getAllocSite(), // allocation site
2215 toCallerContext( hrnCallee.getInherent(),
2216 calleeStatesSatisfied ), // inherent reach
2217 null, // current reach
2218 predsEmpty, // predicates
2219 hrnCallee.getDescription() // description
2222 assert hrnCaller.isWiped();
2225 hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2226 calleeStatesSatisfied
2230 hrnCaller.setPreds( preds );
2235 if( writeDebugDOTs ) {
2237 writeGraph( "caller31BeforeAddingEdges",
2238 true, false, false, false, true, true );
2239 } catch( IOException e ) {}
2243 // set these up during the next procedure so after
2244 // the caller has all of its nodes and edges put
2245 // back together we can propagate the callee's
2246 // reach changes backwards into the caller graph
2247 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2249 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2250 new Hashtable<RefEdge, ChangeSet>();
2253 // 3.b) callee -> callee edges AND out-of-context -> callee
2254 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2255 while( satisItr.hasNext() ) {
2256 Map.Entry me = (Map.Entry) satisItr.next();
2257 RefEdge reCallee = (RefEdge) me.getKey();
2258 ExistPredSet preds = (ExistPredSet) me.getValue();
2260 HeapRegionNode hrnDstCallee = reCallee.getDst();
2261 AllocSite asDst = hrnDstCallee.getAllocSite();
2262 allocSites.add( asDst );
2264 Integer hrnIDDstShadow =
2265 asDst.getShadowIDfromID( hrnDstCallee.getID() );
2267 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2268 assert hrnDstCaller != null;
2271 RefSrcNode rsnCallee = reCallee.getSrc();
2273 Set<RefSrcNode> rsnCallers =
2274 new HashSet<RefSrcNode>();
2276 Set<RefSrcNode> oocCallers =
2277 calleeEdges2oocCallerSrcMatches.get( reCallee );
2279 boolean oocEdges = false;
2281 if( oocCallers == null ) {
2282 // there are no out-of-context matches, so it's
2283 // either a param/arg var or one in-context heap region
2284 if( rsnCallee instanceof VariableNode ) {
2285 // variable -> node in the callee should only
2286 // come into the caller if its from a param var
2287 VariableNode vnCallee = (VariableNode) rsnCallee;
2288 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2289 TempDescriptor tdArg = fc.getArgMatchingParam( fmCallee,
2291 if( tdArg == null ) {
2292 // this means the variable isn't a parameter, its local
2293 // to the callee so we ignore it in call site transfer
2294 // shouldn't this NEVER HAPPEN?
2297 rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2301 // otherwise source is in context, one region
2302 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2304 // translate an in-context node to shadow
2305 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2306 allocSites.add( asSrc );
2308 Integer hrnIDSrcShadow =
2309 asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2311 HeapRegionNode hrnSrcCallerShadow =
2312 this.id2hrn.get( hrnIDSrcShadow );
2314 if( hrnSrcCallerShadow == null ) {
2315 hrnSrcCallerShadow =
2316 createNewHeapRegionNode( hrnIDSrcShadow, // id or null to generate a new one
2317 hrnSrcCallee.isSingleObject(), // single object?
2318 hrnSrcCallee.isNewSummary(), // summary?
2319 hrnSrcCallee.isFlagged(), // flagged?
2320 false, // out-of-context?
2321 hrnSrcCallee.getType(), // type
2322 hrnSrcCallee.getAllocSite(), // allocation site
2323 toCallerContext( hrnSrcCallee.getInherent(),
2324 calleeStatesSatisfied ), // inherent reach
2325 toCallerContext( hrnSrcCallee.getAlpha(),
2326 calleeStatesSatisfied ), // current reach
2327 predsEmpty, // predicates
2328 hrnSrcCallee.getDescription() // description
2332 rsnCallers.add( hrnSrcCallerShadow );
2336 // otherwise we have a set of out-of-context srcs
2337 // that should NOT be translated to shadow nodes
2338 assert !oocCallers.isEmpty();
2339 rsnCallers.addAll( oocCallers );
2343 // now make all caller edges we've identified from
2344 // this callee edge with a satisfied predicate
2345 assert !rsnCallers.isEmpty();
2346 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2347 while( rsnItr.hasNext() ) {
2348 RefSrcNode rsnCaller = rsnItr.next();
2350 RefEdge reCaller = new RefEdge( rsnCaller,
2353 reCallee.getField(),
2354 toCallerContext( reCallee.getBeta(),
2355 calleeStatesSatisfied ),
2359 ChangeSet cs = ChangeSet.factory();
2360 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2361 while( rsItr.hasNext() ) {
2362 ReachState state = rsItr.next();
2363 ExistPredSet preds2 = state.getPreds();
2364 assert preds2.preds.size() == 1;
2366 if( state.isEmpty() ) {
2370 ExistPred pred = preds2.preds.iterator().next();
2371 ReachState old = pred.ne_state;
2379 cs = Canonical.union( cs,
2380 ChangeTuple.factory( old,
2386 // look to see if an edge with same field exists
2387 // and merge with it, otherwise just add the edge
2388 RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2392 if( edgeExisting != null ) {
2393 edgeExisting.setBeta(
2394 Canonical.union( edgeExisting.getBeta(),
2398 edgeExisting.setPreds(
2399 Canonical.join( edgeExisting.getPreds(),
2404 // for reach propagation
2405 if( !cs.isEmpty() ) {
2406 edgePlannedChanges.put(
2408 Canonical.union( edgePlannedChanges.get( edgeExisting ),
2415 addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2417 // for reach propagation
2418 if( !cs.isEmpty() ) {
2419 edgesForPropagation.add( reCaller );
2420 assert !edgePlannedChanges.containsKey( reCaller );
2421 edgePlannedChanges.put( reCaller, cs );
2431 if( writeDebugDOTs ) {
2433 writeGraph( "caller35BeforeAssignReturnValue",
2434 true, false, false, false, true, true );
2435 } catch( IOException e ) {}
2440 // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2441 // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2442 // EDGES, JUST BRINGING THEM ALL! It'll work for now, over approximation
2444 // 3.d) handle return value assignment if needed
2445 TempDescriptor returnTemp = fc.getReturnTemp();
2446 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2448 VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2449 clearRefEdgesFrom( vnLhsCaller, null, null, true );
2451 VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2452 Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2453 while( reCalleeItr.hasNext() ) {
2454 RefEdge reCallee = reCalleeItr.next();
2455 HeapRegionNode hrnDstCallee = reCallee.getDst();
2457 // some edge types are not possible return values when we can
2458 // see what type variable we are assigning it to
2459 if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2460 System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2461 reCallee+" for return temp "+returnTemp );
2466 AllocSite asDst = hrnDstCallee.getAllocSite();
2467 allocSites.add( asDst );
2469 Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2471 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2472 if( hrnDstCaller == null ) {
2474 createNewHeapRegionNode( hrnIDDstShadow, // id or null to generate a new one
2475 hrnDstCallee.isSingleObject(), // single object?
2476 hrnDstCallee.isNewSummary(), // summary?
2477 hrnDstCallee.isFlagged(), // flagged?
2478 false, // out-of-context?
2479 hrnDstCallee.getType(), // type
2480 hrnDstCallee.getAllocSite(), // allocation site
2481 toCallerContext( hrnDstCallee.getInherent(),
2482 calleeStatesSatisfied ), // inherent reach
2483 toCallerContext( hrnDstCallee.getAlpha(),
2484 calleeStatesSatisfied ), // current reach
2485 predsTrue, // predicates
2486 hrnDstCallee.getDescription() // description
2489 assert hrnDstCaller.isWiped();
2492 TypeDescriptor tdNewEdge =
2493 mostSpecificType( reCallee.getType(),
2494 hrnDstCallee.getType(),
2495 hrnDstCaller.getType()
2498 RefEdge reCaller = new RefEdge( vnLhsCaller,
2502 toCallerContext( reCallee.getBeta(),
2503 calleeStatesSatisfied ),
2507 addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2513 if( writeDebugDOTs ) {
2515 writeGraph( "caller38propagateReach",
2516 true, false, false, false, true, true );
2517 } catch( IOException e ) {}
2520 // propagate callee reachability changes to the rest
2521 // of the caller graph edges
2522 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2524 propagateTokensOverEdges( edgesForPropagation, // source edges
2525 edgePlannedChanges, // map src edge to change set
2526 edgesUpdated ); // list of updated edges
2528 // commit beta' (beta<-betaNew)
2529 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2530 while( edgeItr.hasNext() ) {
2531 edgeItr.next().applyBetaNew();
2539 if( writeDebugDOTs ) {
2541 writeGraph( "caller40BeforeShadowMerge",
2542 true, false, false, false, true, true );
2543 } catch( IOException e ) {}
2547 // 4) merge shadow nodes so alloc sites are back to k
2548 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2549 while( asItr.hasNext() ) {
2550 // for each allocation site do the following to merge
2551 // shadow nodes (newest from callee) with any existing
2552 // look for the newest normal and newest shadow "slot"
2553 // not being used, transfer normal to shadow. Keep
2554 // doing this until there are no more normal nodes, or
2555 // no empty shadow slots: then merge all remaining normal
2556 // nodes into the shadow summary. Finally, convert all
2557 // shadow to their normal versions.
2558 AllocSite as = asItr.next();
2561 while( ageNorm < allocationDepth &&
2562 ageShad < allocationDepth ) {
2564 // first, are there any normal nodes left?
2565 Integer idNorm = as.getIthOldest( ageNorm );
2566 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2567 if( hrnNorm == null ) {
2568 // no, this age of normal node not in the caller graph
2573 // yes, a normal node exists, is there an empty shadow
2574 // "slot" to transfer it onto?
2575 HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2576 if( !hrnShad.isWiped() ) {
2577 // no, this age of shadow node is not empty
2582 // yes, this shadow node is empty
2583 transferOnto( hrnNorm, hrnShad );
2588 // now, while there are still normal nodes but no shadow
2589 // slots, merge normal nodes into the shadow summary
2590 while( ageNorm < allocationDepth ) {
2592 // first, are there any normal nodes left?
2593 Integer idNorm = as.getIthOldest( ageNorm );
2594 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2595 if( hrnNorm == null ) {
2596 // no, this age of normal node not in the caller graph
2601 // yes, a normal node exists, so get the shadow summary
2602 HeapRegionNode summShad = getSummaryNode( as, true );
2603 mergeIntoSummary( hrnNorm, summShad );
2607 // if there is a normal summary, merge it into shadow summary
2608 Integer idNorm = as.getSummary();
2609 HeapRegionNode summNorm = id2hrn.get( idNorm );
2610 if( summNorm != null ) {
2611 HeapRegionNode summShad = getSummaryNode( as, true );
2612 mergeIntoSummary( summNorm, summShad );
2615 // finally, flip all existing shadow nodes onto the normal
2616 for( int i = 0; i < allocationDepth; ++i ) {
2617 Integer idShad = as.getIthOldestShadow( i );
2618 HeapRegionNode hrnShad = id2hrn.get( idShad );
2619 if( hrnShad != null ) {
2621 HeapRegionNode hrnNorm = getIthNode( as, i, false );
2622 assert hrnNorm.isWiped();
2623 transferOnto( hrnShad, hrnNorm );
2627 Integer idShad = as.getSummaryShadow();
2628 HeapRegionNode summShad = id2hrn.get( idShad );
2629 if( summShad != null ) {
2630 summNorm = getSummaryNode( as, false );
2631 transferOnto( summShad, summNorm );
2636 if( writeDebugDOTs ) {
2638 writeGraph( "caller45BeforeUnshadow",
2639 true, false, false, false, true, true );
2640 } catch( IOException e ) {}
2644 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2645 while( itrAllHRNodes.hasNext() ) {
2646 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
2647 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2649 hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2651 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2652 while( itrEdges.hasNext() ) {
2653 RefEdge re = itrEdges.next();
2654 re.setBeta( unshadow( re.getBeta() ) );
2660 if( writeDebugDOTs ) {
2662 writeGraph( "caller50BeforeGlobalSweep",
2663 true, false, false, false, true, true );
2664 } catch( IOException e ) {}
2669 if( !DISABLE_GLOBAL_SWEEP ) {
2675 if( writeDebugDOTs ) {
2677 writeGraph( "caller90AfterTransfer",
2678 true, false, false, false, true, true );
2679 } catch( IOException e ) {}
2685 ////////////////////////////////////////////////////
2687 // Abstract garbage collection simply removes
2688 // heap region nodes that are not mechanically
2689 // reachable from a root set. This step is
2690 // essential for testing node and edge existence
2691 // predicates efficiently
2693 ////////////////////////////////////////////////////
2694 public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2696 // calculate a root set, will be different for Java
2697 // version of analysis versus Bamboo version
2698 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2700 // visit every variable in graph while building root
2701 // set, and do iterating on a copy, so we can remove
2702 // dead variables while we're at this
2703 Iterator makeCopyItr = td2vn.entrySet().iterator();
2704 Set entrysCopy = new HashSet();
2705 while( makeCopyItr.hasNext() ) {
2706 entrysCopy.add( makeCopyItr.next() );
2709 Iterator eItr = entrysCopy.iterator();
2710 while( eItr.hasNext() ) {
2711 Map.Entry me = (Map.Entry) eItr.next();
2712 TempDescriptor td = (TempDescriptor) me.getKey();
2713 VariableNode vn = (VariableNode) me.getValue();
2715 if( liveSet.contains( td ) ) {
2719 // dead var, remove completely from graph
2721 clearRefEdgesFrom( vn, null, null, true );
2725 // everything visited in a traversal is
2726 // considered abstractly live
2727 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2729 while( !toVisit.isEmpty() ) {
2730 RefSrcNode rsn = toVisit.iterator().next();
2731 toVisit.remove( rsn );
2734 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2735 while( hrnItr.hasNext() ) {
2736 RefEdge edge = hrnItr.next();
2737 HeapRegionNode hrn = edge.getDst();
2739 if( !visited.contains( hrn ) ) {
2745 // get a copy of the set to iterate over because
2746 // we're going to monkey with the graph when we
2747 // identify a garbage node
2748 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2749 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2750 while( hrnItr.hasNext() ) {
2751 hrnAllPrior.add( hrnItr.next() );
2754 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2755 while( hrnAllItr.hasNext() ) {
2756 HeapRegionNode hrn = hrnAllItr.next();
2758 if( !visited.contains( hrn ) ) {
2760 // heap region nodes are compared across ReachGraph
2761 // objects by their integer ID, so when discarding
2762 // garbage nodes we must also discard entries in
2763 // the ID -> heap region hashtable.
2764 id2hrn.remove( hrn.getID() );
2766 // RefEdge objects are two-way linked between
2767 // nodes, so when a node is identified as garbage,
2768 // actively clear references to and from it so
2769 // live nodes won't have dangling RefEdge's
2770 wipeOut( hrn, true );
2772 // if we just removed the last node from an allocation
2773 // site, it should be taken out of the ReachGraph's list
2774 AllocSite as = hrn.getAllocSite();
2775 if( !hasNodesOf( as ) ) {
2776 allocSites.remove( as );
2782 protected boolean hasNodesOf( AllocSite as ) {
2783 if( id2hrn.containsKey( as.getSummary() ) ) {
2787 for( int i = 0; i < allocationDepth; ++i ) {
2788 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2796 ////////////////////////////////////////////////////
2798 // This global sweep is an optional step to prune
2799 // reachability sets that are not internally
2800 // consistent with the global graph. It should be
2801 // invoked after strong updates or method calls.
2803 ////////////////////////////////////////////////////
2804 public void globalSweep() {
2806 // boldB is part of the phase 1 sweep
2807 // it has an in-context table and an out-of-context table
2808 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2809 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2811 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2812 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2814 // visit every heap region to initialize alphaNew and betaNew,
2815 // and make a map of every hrnID to the source nodes it should
2816 // propagate forward from. In-context flagged hrnID's propagate
2817 // from only the in-context node they name, but out-of-context
2818 // ID's may propagate from several out-of-context nodes
2819 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2820 new Hashtable< Integer, Set<HeapRegionNode> >();
2822 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2823 new Hashtable< Integer, Set<HeapRegionNode> >();
2826 Iterator itrHrns = id2hrn.entrySet().iterator();
2827 while( itrHrns.hasNext() ) {
2828 Map.Entry me = (Map.Entry) itrHrns.next();
2829 Integer hrnID = (Integer) me.getKey();
2830 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2832 // assert that this node and incoming edges have clean alphaNew
2833 // and betaNew sets, respectively
2834 assert rsetEmpty.equals( hrn.getAlphaNew() );
2836 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2837 while( itrRers.hasNext() ) {
2838 RefEdge edge = itrRers.next();
2839 assert rsetEmpty.equals( edge.getBetaNew() );
2842 // calculate boldB for this flagged node, or out-of-context node
2843 if( hrn.isFlagged() ) {
2844 assert !hrn.isOutOfContext();
2845 assert !icID2srcs.containsKey( hrn.getID() );
2846 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2848 icID2srcs.put( hrn.getID(), srcs );
2851 if( hrn.isOutOfContext() ) {
2852 assert !hrn.isFlagged();
2854 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2855 while( stateItr.hasNext() ) {
2856 ReachState state = stateItr.next();
2858 Iterator<ReachTuple> rtItr = state.iterator();
2859 while( rtItr.hasNext() ) {
2860 ReachTuple rt = rtItr.next();
2861 assert rt.isOutOfContext();
2863 Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2864 if( srcs == null ) {
2865 srcs = new HashSet<HeapRegionNode>();
2868 oocID2srcs.put( rt.getHrnID(), srcs );
2874 // calculate boldB for all hrnIDs identified by the above
2875 // node traversal, propagating from every source
2876 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2879 Set<HeapRegionNode> srcs;
2882 if( !icID2srcs.isEmpty() ) {
2883 Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2884 hrnID = (Integer) me.getKey();
2885 srcs = (Set<HeapRegionNode>) me.getValue();
2887 icID2srcs.remove( hrnID );
2890 assert !oocID2srcs.isEmpty();
2892 Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2893 hrnID = (Integer) me.getKey();
2894 srcs = (Set<HeapRegionNode>) me.getValue();
2896 oocID2srcs.remove( hrnID );
2900 Hashtable<RefEdge, ReachSet> boldB_f =
2901 new Hashtable<RefEdge, ReachSet>();
2903 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2905 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2906 while( hrnItr.hasNext() ) {
2907 HeapRegionNode hrn = hrnItr.next();
2909 assert workSetEdges.isEmpty();
2911 // initial boldB_f constraints
2912 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2913 while( itrRees.hasNext() ) {
2914 RefEdge edge = itrRees.next();
2916 assert !boldB_f.containsKey( edge );
2917 boldB_f.put( edge, edge.getBeta() );
2919 assert !workSetEdges.contains( edge );
2920 workSetEdges.add( edge );
2923 // enforce the boldB_f constraint at edges until we reach a fixed point
2924 while( !workSetEdges.isEmpty() ) {
2925 RefEdge edge = workSetEdges.iterator().next();
2926 workSetEdges.remove( edge );
2928 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2929 while( itrPrime.hasNext() ) {
2930 RefEdge edgePrime = itrPrime.next();
2932 ReachSet prevResult = boldB_f.get( edgePrime );
2933 ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2937 if( prevResult == null ||
2938 Canonical.union( prevResult,
2939 intersection ).size() > prevResult.size() ) {
2941 if( prevResult == null ) {
2942 boldB_f.put( edgePrime,
2943 Canonical.union( edgePrime.getBeta(),
2948 boldB_f.put( edgePrime,
2949 Canonical.union( prevResult,
2954 workSetEdges.add( edgePrime );
2961 boldBic.put( hrnID, boldB_f );
2963 boldBooc.put( hrnID, boldB_f );
2968 // use boldB to prune hrnIDs from alpha states that are impossible
2969 // and propagate the differences backwards across edges
2970 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2972 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2973 new Hashtable<RefEdge, ChangeSet>();
2976 itrHrns = id2hrn.entrySet().iterator();
2977 while( itrHrns.hasNext() ) {
2978 Map.Entry me = (Map.Entry) itrHrns.next();
2979 Integer hrnID = (Integer) me.getKey();
2980 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2982 // out-of-context nodes don't participate in the
2983 // global sweep, they serve as sources for the pass
2985 if( hrn.isOutOfContext() ) {
2989 // the inherent states of a region are the exception
2990 // to removal as the global sweep prunes
2991 ReachTuple rtException = ReachTuple.factory( hrnID,
2992 !hrn.isSingleObject(),
2993 ReachTuple.ARITY_ONE,
2994 false // out-of-context
2997 ChangeSet cts = ChangeSet.factory();
2999 // mark hrnIDs for removal
3000 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3001 while( stateItr.hasNext() ) {
3002 ReachState stateOld = stateItr.next();
3004 ReachState markedHrnIDs = ReachState.factory();
3006 Iterator<ReachTuple> rtItr = stateOld.iterator();
3007 while( rtItr.hasNext() ) {
3008 ReachTuple rtOld = rtItr.next();
3010 // never remove the inherent hrnID from a flagged region
3011 // because it is trivially satisfied
3012 if( hrn.isFlagged() ) {
3013 if( rtOld == rtException ) {
3018 // does boldB allow this hrnID?
3019 boolean foundState = false;
3020 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3021 while( incidentEdgeItr.hasNext() ) {
3022 RefEdge incidentEdge = incidentEdgeItr.next();
3024 Hashtable<RefEdge, ReachSet> B;
3025 if( rtOld.isOutOfContext() ) {
3026 B = boldBooc.get( rtOld.getHrnID() );
3028 assert id2hrn.containsKey( rtOld.getHrnID() );
3029 B = boldBic.get( rtOld.getHrnID() );
3033 ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3034 if( boldB_rtOld_incident != null &&
3035 boldB_rtOld_incident.contains( stateOld ) ) {
3042 markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3046 // if there is nothing marked, just move on
3047 if( markedHrnIDs.isEmpty() ) {
3048 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
3055 // remove all marked hrnIDs and establish a change set that should
3056 // propagate backwards over edges from this node
3057 ReachState statePruned = ReachState.factory();
3058 rtItr = stateOld.iterator();
3059 while( rtItr.hasNext() ) {
3060 ReachTuple rtOld = rtItr.next();
3062 if( !markedHrnIDs.containsTuple( rtOld ) ) {
3063 statePruned = Canonical.union( statePruned, rtOld );
3066 assert !stateOld.equals( statePruned );
3068 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
3072 ChangeTuple ct = ChangeTuple.factory( stateOld,
3075 cts = Canonical.union( cts, ct );
3078 // throw change tuple set on all incident edges
3079 if( !cts.isEmpty() ) {
3080 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3081 while( incidentEdgeItr.hasNext() ) {
3082 RefEdge incidentEdge = incidentEdgeItr.next();
3084 edgesForPropagation.add( incidentEdge );
3086 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3087 edgePlannedChanges.put( incidentEdge, cts );
3089 edgePlannedChanges.put(
3091 Canonical.union( edgePlannedChanges.get( incidentEdge ),
3100 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3102 propagateTokensOverEdges( edgesForPropagation,
3106 // at the end of the 1st phase reference edges have
3107 // beta, betaNew that correspond to beta and betaR
3109 // commit beta<-betaNew, so beta=betaR and betaNew
3110 // will represent the beta' calculation in 2nd phase
3112 // commit alpha<-alphaNew because it won't change
3113 HashSet<RefEdge> res = new HashSet<RefEdge>();
3115 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3116 while( nodeItr.hasNext() ) {
3117 HeapRegionNode hrn = nodeItr.next();
3118 hrn.applyAlphaNew();
3119 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3120 while( itrRes.hasNext() ) {
3121 res.add( itrRes.next() );
3127 Iterator<RefEdge> edgeItr = res.iterator();
3128 while( edgeItr.hasNext() ) {
3129 RefEdge edge = edgeItr.next();
3130 HeapRegionNode hrn = edge.getDst();
3132 // commit results of last phase
3133 if( edgesUpdated.contains( edge ) ) {
3134 edge.applyBetaNew();
3137 // compute intial condition of 2nd phase
3138 edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3144 // every edge in the graph is the initial workset
3145 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3146 while( !edgeWorkSet.isEmpty() ) {
3147 RefEdge edgePrime = edgeWorkSet.iterator().next();
3148 edgeWorkSet.remove( edgePrime );
3150 RefSrcNode rsn = edgePrime.getSrc();
3151 if( !(rsn instanceof HeapRegionNode) ) {
3154 HeapRegionNode hrn = (HeapRegionNode) rsn;
3156 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3157 while( itrEdge.hasNext() ) {
3158 RefEdge edge = itrEdge.next();
3160 ReachSet prevResult = edge.getBetaNew();
3161 assert prevResult != null;
3163 ReachSet intersection =
3164 Canonical.intersection( edge.getBeta(),
3165 edgePrime.getBetaNew()
3168 if( Canonical.union( prevResult,
3170 ).size() > prevResult.size() ) {
3172 Canonical.union( prevResult,
3176 edgeWorkSet.add( edge );
3181 // commit beta' (beta<-betaNew)
3182 edgeItr = res.iterator();
3183 while( edgeItr.hasNext() ) {
3184 edgeItr.next().applyBetaNew();
3190 ////////////////////////////////////////////////////
3191 // high-level merge operations
3192 ////////////////////////////////////////////////////
3193 public void merge_sameMethodContext( ReachGraph rg ) {
3194 // when merging two graphs that abstract the heap
3195 // of the same method context, we just call the
3196 // basic merge operation
3200 public void merge_diffMethodContext( ReachGraph rg ) {
3201 // when merging graphs for abstract heaps in
3202 // different method contexts we should:
3203 // 1) age the allocation sites?
3207 ////////////////////////////////////////////////////
3208 // in merge() and equals() methods the suffix A
3209 // represents the passed in graph and the suffix
3210 // B refers to the graph in this object
3211 // Merging means to take the incoming graph A and
3212 // merge it into B, so after the operation graph B
3213 // is the final result.
3214 ////////////////////////////////////////////////////
3215 protected void merge( ReachGraph rg ) {
3222 mergeRefEdges ( rg );
3223 mergeAllocSites( rg );
3226 protected void mergeNodes( ReachGraph rg ) {
3228 // start with heap region nodes
3229 Set sA = rg.id2hrn.entrySet();
3230 Iterator iA = sA.iterator();
3231 while( iA.hasNext() ) {
3232 Map.Entry meA = (Map.Entry) iA.next();
3233 Integer idA = (Integer) meA.getKey();
3234 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3236 // if this graph doesn't have a node the
3237 // incoming graph has, allocate it
3238 if( !id2hrn.containsKey( idA ) ) {
3239 HeapRegionNode hrnB = hrnA.copy();
3240 id2hrn.put( idA, hrnB );
3243 // otherwise this is a node present in both graphs
3244 // so make the new reachability set a union of the
3245 // nodes' reachability sets
3246 HeapRegionNode hrnB = id2hrn.get( idA );
3247 hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
3252 hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3259 // now add any variable nodes that are in graph B but
3261 sA = rg.td2vn.entrySet();
3263 while( iA.hasNext() ) {
3264 Map.Entry meA = (Map.Entry) iA.next();
3265 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3266 VariableNode lnA = (VariableNode) meA.getValue();
3268 // if the variable doesn't exist in B, allocate and add it
3269 VariableNode lnB = getVariableNodeFromTemp( tdA );
3273 protected void mergeRefEdges( ReachGraph rg ) {
3275 // between heap regions
3276 Set sA = rg.id2hrn.entrySet();
3277 Iterator iA = sA.iterator();
3278 while( iA.hasNext() ) {
3279 Map.Entry meA = (Map.Entry) iA.next();
3280 Integer idA = (Integer) meA.getKey();
3281 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3283 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3284 while( heapRegionsItrA.hasNext() ) {
3285 RefEdge edgeA = heapRegionsItrA.next();
3286 HeapRegionNode hrnChildA = edgeA.getDst();
3287 Integer idChildA = hrnChildA.getID();
3289 // at this point we know an edge in graph A exists
3290 // idA -> idChildA, does this exist in B?
3291 assert id2hrn.containsKey( idA );
3292 HeapRegionNode hrnB = id2hrn.get( idA );
3293 RefEdge edgeToMerge = null;
3295 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3296 while( heapRegionsItrB.hasNext() &&
3297 edgeToMerge == null ) {
3299 RefEdge edgeB = heapRegionsItrB.next();
3300 HeapRegionNode hrnChildB = edgeB.getDst();
3301 Integer idChildB = hrnChildB.getID();
3303 // don't use the RefEdge.equals() here because
3304 // we're talking about existence between graphs,
3305 // not intragraph equal
3306 if( idChildB.equals( idChildA ) &&
3307 edgeB.typeAndFieldEquals( edgeA ) ) {
3309 edgeToMerge = edgeB;
3313 // if the edge from A was not found in B,
3315 if( edgeToMerge == null ) {
3316 assert id2hrn.containsKey( idChildA );
3317 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3318 edgeToMerge = edgeA.copy();
3319 edgeToMerge.setSrc( hrnB );
3320 edgeToMerge.setDst( hrnChildB );
3321 addRefEdge( hrnB, hrnChildB, edgeToMerge );
3323 // otherwise, the edge already existed in both graphs
3324 // so merge their reachability sets
3326 // just replace this beta set with the union
3327 assert edgeToMerge != null;
3328 edgeToMerge.setBeta(
3329 Canonical.union( edgeToMerge.getBeta(),
3333 edgeToMerge.setPreds(
3334 Canonical.join( edgeToMerge.getPreds(),
3342 // and then again from variable nodes
3343 sA = rg.td2vn.entrySet();
3345 while( iA.hasNext() ) {
3346 Map.Entry meA = (Map.Entry) iA.next();
3347 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3348 VariableNode vnA = (VariableNode) meA.getValue();
3350 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3351 while( heapRegionsItrA.hasNext() ) {
3352 RefEdge edgeA = heapRegionsItrA.next();
3353 HeapRegionNode hrnChildA = edgeA.getDst();
3354 Integer idChildA = hrnChildA.getID();
3356 // at this point we know an edge in graph A exists
3357 // tdA -> idChildA, does this exist in B?
3358 assert td2vn.containsKey( tdA );
3359 VariableNode vnB = td2vn.get( tdA );
3360 RefEdge edgeToMerge = null;
3362 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3363 while( heapRegionsItrB.hasNext() &&
3364 edgeToMerge == null ) {
3366 RefEdge edgeB = heapRegionsItrB.next();
3367 HeapRegionNode hrnChildB = edgeB.getDst();
3368 Integer idChildB = hrnChildB.getID();
3370 // don't use the RefEdge.equals() here because
3371 // we're talking about existence between graphs
3372 if( idChildB.equals( idChildA ) &&
3373 edgeB.typeAndFieldEquals( edgeA ) ) {
3375 edgeToMerge = edgeB;
3379 // if the edge from A was not found in B,
3381 if( edgeToMerge == null ) {
3382 assert id2hrn.containsKey( idChildA );
3383 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3384 edgeToMerge = edgeA.copy();
3385 edgeToMerge.setSrc( vnB );
3386 edgeToMerge.setDst( hrnChildB );
3387 addRefEdge( vnB, hrnChildB, edgeToMerge );
3389 // otherwise, the edge already existed in both graphs
3390 // so merge their reachability sets
3392 // just replace this beta set with the union
3393 edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
3397 edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3406 protected void mergeAllocSites( ReachGraph rg ) {
3407 allocSites.addAll( rg.allocSites );
3411 // it is necessary in the equals() member functions
3412 // to "check both ways" when comparing the data
3413 // structures of two graphs. For instance, if all
3414 // edges between heap region nodes in graph A are
3415 // present and equal in graph B it is not sufficient
3416 // to say the graphs are equal. Consider that there
3417 // may be edges in graph B that are not in graph A.
3418 // the only way to know that all edges in both graphs
3419 // are equally present is to iterate over both data
3420 // structures and compare against the other graph.
3421 public boolean equals( ReachGraph rg ) {
3427 if( !areHeapRegionNodesEqual( rg ) ) {
3431 if( !areVariableNodesEqual( rg ) ) {
3435 if( !areRefEdgesEqual( rg ) ) {
3439 // if everything is equal up to this point,
3440 // assert that allocSites is also equal--
3441 // this data is redundant but kept for efficiency
3442 assert allocSites.equals( rg.allocSites );
3448 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3450 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3454 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3461 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3463 Set sA = rgA.id2hrn.entrySet();
3464 Iterator iA = sA.iterator();
3465 while( iA.hasNext() ) {
3466 Map.Entry meA = (Map.Entry) iA.next();
3467 Integer idA = (Integer) meA.getKey();
3468 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3470 if( !rgB.id2hrn.containsKey( idA ) ) {
3474 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3475 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3484 protected boolean areVariableNodesEqual( ReachGraph rg ) {
3486 if( !areallVNinAalsoinBandequal( this, rg ) ) {
3490 if( !areallVNinAalsoinBandequal( rg, this ) ) {
3497 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3499 Set sA = rgA.td2vn.entrySet();
3500 Iterator iA = sA.iterator();
3501 while( iA.hasNext() ) {
3502 Map.Entry meA = (Map.Entry) iA.next();
3503 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3505 if( !rgB.td2vn.containsKey( tdA ) ) {
3514 protected boolean areRefEdgesEqual( ReachGraph rg ) {
3515 if( !areallREinAandBequal( this, rg ) ) {
3522 static protected boolean areallREinAandBequal( ReachGraph rgA,
3525 // check all the heap region->heap region edges
3526 Set sA = rgA.id2hrn.entrySet();
3527 Iterator iA = sA.iterator();
3528 while( iA.hasNext() ) {
3529 Map.Entry meA = (Map.Entry) iA.next();
3530 Integer idA = (Integer) meA.getKey();
3531 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3533 // we should have already checked that the same
3534 // heap regions exist in both graphs
3535 assert rgB.id2hrn.containsKey( idA );
3537 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3541 // then check every edge in B for presence in A, starting
3542 // from the same parent HeapRegionNode
3543 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3545 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3550 // then check all the variable->heap region edges
3551 sA = rgA.td2vn.entrySet();
3553 while( iA.hasNext() ) {
3554 Map.Entry meA = (Map.Entry) iA.next();
3555 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3556 VariableNode vnA = (VariableNode) meA.getValue();
3558 // we should have already checked that the same
3559 // label nodes exist in both graphs
3560 assert rgB.td2vn.containsKey( tdA );
3562 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3566 // then check every edge in B for presence in A, starting
3567 // from the same parent VariableNode
3568 VariableNode vnB = rgB.td2vn.get( tdA );
3570 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3579 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3583 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3584 while( itrA.hasNext() ) {
3585 RefEdge edgeA = itrA.next();
3586 HeapRegionNode hrnChildA = edgeA.getDst();
3587 Integer idChildA = hrnChildA.getID();
3589 assert rgB.id2hrn.containsKey( idChildA );
3591 // at this point we know an edge in graph A exists
3592 // rnA -> idChildA, does this exact edge exist in B?
3593 boolean edgeFound = false;
3595 RefSrcNode rnB = null;
3596 if( rnA instanceof HeapRegionNode ) {
3597 HeapRegionNode hrnA = (HeapRegionNode) rnA;
3598 rnB = rgB.id2hrn.get( hrnA.getID() );
3600 VariableNode vnA = (VariableNode) rnA;
3601 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3604 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3605 while( itrB.hasNext() ) {
3606 RefEdge edgeB = itrB.next();
3607 HeapRegionNode hrnChildB = edgeB.getDst();
3608 Integer idChildB = hrnChildB.getID();
3610 if( idChildA.equals( idChildB ) &&
3611 edgeA.typeAndFieldEquals( edgeB ) ) {
3613 // there is an edge in the right place with the right field,
3614 // but do they have the same attributes?
3615 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3616 edgeA.equalsPreds( edgeB )
3633 // this analysis no longer has the "match anything"
3634 // type which was represented by null
3635 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3636 TypeDescriptor td2 ) {
3640 if( td1.isNull() ) {
3643 if( td2.isNull() ) {
3646 return typeUtil.mostSpecific( td1, td2 );
3649 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3651 TypeDescriptor td3 ) {
3653 return mostSpecificType( td1,
3654 mostSpecificType( td2, td3 )
3658 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3661 TypeDescriptor td4 ) {
3663 return mostSpecificType( mostSpecificType( td1, td2 ),
3664 mostSpecificType( td3, td4 )
3668 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3669 TypeDescriptor possibleChild ) {
3670 assert possibleSuper != null;
3671 assert possibleChild != null;
3673 if( possibleSuper.isNull() ||
3674 possibleChild.isNull() ) {
3678 return typeUtil.isSuperorType( possibleSuper, possibleChild );
3682 protected boolean hasMatchingField( HeapRegionNode src,
3685 TypeDescriptor tdSrc = src.getType();
3686 assert tdSrc != null;
3688 if( tdSrc.isArray() ) {
3689 TypeDescriptor td = edge.getType();
3692 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3693 assert tdSrcDeref != null;
3695 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3699 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3702 // if it's not a class, it doesn't have any fields to match
3703 if( !tdSrc.isClass() ) {
3707 ClassDescriptor cd = tdSrc.getClassDesc();
3708 while( cd != null ) {
3709 Iterator fieldItr = cd.getFields();
3711 while( fieldItr.hasNext() ) {
3712 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3714 if( fd.getType().equals( edge.getType() ) &&
3715 fd.getSymbol().equals( edge.getField() ) ) {
3720 cd = cd.getSuperDesc();
3723 // otherwise it is a class with fields
3724 // but we didn't find a match
3728 protected boolean hasMatchingType( RefEdge edge,
3729 HeapRegionNode dst ) {
3731 // if the region has no type, matches everything
3732 TypeDescriptor tdDst = dst.getType();
3733 assert tdDst != null;
3735 // if the type is not a class or an array, don't
3736 // match because primitives are copied, no aliases
3737 ClassDescriptor cdDst = tdDst.getClassDesc();
3738 if( cdDst == null && !tdDst.isArray() ) {
3742 // if the edge type is null, it matches everything
3743 TypeDescriptor tdEdge = edge.getType();
3744 assert tdEdge != null;
3746 return typeUtil.isSuperorType( tdEdge, tdDst );
3751 public void writeGraph( String graphName,
3752 boolean writeLabels,
3753 boolean labelSelect,
3754 boolean pruneGarbage,
3755 boolean writeReferencers,
3756 boolean hideSubsetReachability,
3757 boolean hideEdgeTaints
3758 ) throws java.io.IOException {
3759 writeGraph( graphName,
3764 hideSubsetReachability,
3769 public void writeGraph( String graphName,
3770 boolean writeLabels,
3771 boolean labelSelect,
3772 boolean pruneGarbage,
3773 boolean writeReferencers,
3774 boolean hideSubsetReachability,
3775 boolean hideEdgeTaints,
3776 Set<Integer> callerNodeIDsCopiedToCallee
3777 ) throws java.io.IOException {
3779 // remove all non-word characters from the graph name so
3780 // the filename and identifier in dot don't cause errors
3781 graphName = graphName.replaceAll( "[\\W]", "" );
3784 new BufferedWriter( new FileWriter( graphName+".dot" ) );
3786 bw.write( "digraph "+graphName+" {\n" );
3789 // this is an optional step to form the callee-reachable
3790 // "cut-out" into a DOT cluster for visualization
3791 if( callerNodeIDsCopiedToCallee != null ) {
3793 bw.write( " subgraph cluster0 {\n" );
3794 bw.write( " color=blue;\n" );
3796 Iterator i = id2hrn.entrySet().iterator();
3797 while( i.hasNext() ) {
3798 Map.Entry me = (Map.Entry) i.next();
3799 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3801 if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3802 bw.write( " "+hrn.toString()+
3803 hrn.toStringDOT( hideSubsetReachability )+
3813 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3815 // then visit every heap region node
3816 Iterator i = id2hrn.entrySet().iterator();
3817 while( i.hasNext() ) {
3818 Map.Entry me = (Map.Entry) i.next();
3819 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3821 // only visit nodes worth writing out--for instance
3822 // not every node at an allocation is referenced
3823 // (think of it as garbage-collected), etc.
3824 if( !pruneGarbage ||
3825 (hrn.isFlagged() && hrn.getID() > 0) ||
3826 hrn.getDescription().startsWith( "param" ) ||
3827 hrn.isOutOfContext()
3830 if( !visited.contains( hrn ) ) {
3831 traverseHeapRegionNodes( hrn,
3836 hideSubsetReachability,
3838 callerNodeIDsCopiedToCallee );
3843 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
3846 // then visit every label node, useful for debugging
3848 i = td2vn.entrySet().iterator();
3849 while( i.hasNext() ) {
3850 Map.Entry me = (Map.Entry) i.next();
3851 VariableNode vn = (VariableNode) me.getValue();
3854 String labelStr = vn.getTempDescriptorString();
3855 if( labelStr.startsWith("___temp") ||
3856 labelStr.startsWith("___dst") ||
3857 labelStr.startsWith("___srctmp") ||
3858 labelStr.startsWith("___neverused")
3864 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3865 while( heapRegionsItr.hasNext() ) {
3866 RefEdge edge = heapRegionsItr.next();
3867 HeapRegionNode hrn = edge.getDst();
3869 if( pruneGarbage && !visited.contains( hrn ) ) {
3870 traverseHeapRegionNodes( hrn,
3875 hideSubsetReachability,
3877 callerNodeIDsCopiedToCallee );
3880 bw.write( " "+vn.toString()+
3881 " -> "+hrn.toString()+
3882 edge.toStringDOT( hideSubsetReachability, "" )+
3892 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
3895 Set<HeapRegionNode> visited,
3896 boolean writeReferencers,
3897 boolean hideSubsetReachability,
3898 boolean hideEdgeTaints,
3899 Set<Integer> callerNodeIDsCopiedToCallee
3900 ) throws java.io.IOException {
3902 if( visited.contains( hrn ) ) {
3907 // if we're drawing the callee-view subgraph, only
3908 // write out the node info if it hasn't already been
3910 if( callerNodeIDsCopiedToCallee == null ||
3911 !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3913 bw.write( " "+hrn.toString()+
3914 hrn.toStringDOT( hideSubsetReachability )+
3918 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3919 while( childRegionsItr.hasNext() ) {
3920 RefEdge edge = childRegionsItr.next();
3921 HeapRegionNode hrnChild = edge.getDst();
3923 if( callerNodeIDsCopiedToCallee != null &&
3924 (edge.getSrc() instanceof HeapRegionNode) ) {
3925 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3926 if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
3927 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3929 bw.write( " "+hrn.toString()+
3930 " -> "+hrnChild.toString()+
3931 edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
3933 } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
3934 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3936 bw.write( " "+hrn.toString()+
3937 " -> "+hrnChild.toString()+
3938 edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
3941 bw.write( " "+hrn.toString()+
3942 " -> "+hrnChild.toString()+
3943 edge.toStringDOT( hideSubsetReachability, "" )+
3947 bw.write( " "+hrn.toString()+
3948 " -> "+hrnChild.toString()+
3949 edge.toStringDOT( hideSubsetReachability, "" )+
3953 traverseHeapRegionNodes( hrnChild,
3958 hideSubsetReachability,
3960 callerNodeIDsCopiedToCallee );