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( ReachSet rs,
1285 TempDescriptor tdSrc,
1288 TypeDescriptor type,
1290 boolean outOfContext
1292 ReachSet out = ReachSet.factory();
1294 Iterator<ReachState> itr = rs.iterator();
1295 while( itr.hasNext() ) {
1296 ReachState stateCaller = itr.next();
1298 ReachState stateCallee = stateCaller;
1300 Iterator<AllocSite> asItr = allocSites.iterator();
1301 while( asItr.hasNext() ) {
1302 AllocSite as = asItr.next();
1304 stateCallee = Canonical.toCalleeContext( stateCallee, as );
1309 if( outOfContext ) {
1313 if( hrnID != null ) {
1314 assert tdSrc == null;
1315 assert hrnSrcID == null;
1316 assert hrnDstID == null;
1317 pred = ExistPred.factory( hrnID,
1320 assert tdSrc != null || hrnSrcID != null;
1321 assert hrnDstID != null;
1322 pred = ExistPred.factory( tdSrc,
1330 preds = ExistPredSet.factory( pred );
1333 stateCallee = Canonical.attach( stateCallee,
1336 out = Canonical.add( out,
1341 assert out.isCanonical();
1345 // used below to convert a ReachSet to its caller-context
1346 // equivalent with respect to allocation sites in this graph
1348 toCallerContext( ReachSet rs,
1349 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1351 ReachSet out = ReachSet.factory();
1353 Iterator<ReachState> itr = rs.iterator();
1354 while( itr.hasNext() ) {
1355 ReachState stateCallee = itr.next();
1357 if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
1359 // starting from one callee state...
1360 ReachSet rsCaller = ReachSet.factory( stateCallee );
1362 // possibly branch it into many states, which any
1363 // allocation site might do, so lots of derived states
1364 Iterator<AllocSite> asItr = allocSites.iterator();
1365 while( asItr.hasNext() ) {
1366 AllocSite as = asItr.next();
1367 rsCaller = Canonical.toCallerContext( rs, as );
1370 // then before adding each derived, now caller-context
1371 // states to the output, attach the appropriate pred
1372 // based on the source callee state
1373 Iterator<ReachState> stateItr = rsCaller.iterator();
1374 while( stateItr.hasNext() ) {
1375 ReachState stateCaller = stateItr.next();
1376 stateCaller = Canonical.attach( stateCaller,
1377 calleeStatesSatisfied.get( stateCallee )
1379 out = Canonical.union( out,
1386 assert out.isCanonical();
1390 // used below to convert a ReachSet to an equivalent
1391 // version with shadow IDs merged into unshadowed IDs
1392 protected ReachSet unshadow( ReachSet rs ) {
1394 Iterator<AllocSite> asItr = allocSites.iterator();
1395 while( asItr.hasNext() ) {
1396 AllocSite as = asItr.next();
1397 out = Canonical.unshadow( out, as );
1399 assert out.isCanonical();
1404 // use this method to make a new reach graph that is
1405 // what heap the FlatMethod callee from the FlatCall
1406 // would start with reaching from its arguments in
1409 makeCalleeView( FlatCall fc,
1410 FlatMethod fmCallee,
1411 Set<Integer> callerNodeIDsCopiedToCallee,
1412 boolean writeDebugDOTs
1415 // the callee view is a new graph: DON'T MODIFY
1417 ReachGraph rg = new ReachGraph();
1419 // track what parts of this graph have already been
1420 // added to callee view, variables not needed.
1421 // Note that we need this because when we traverse
1422 // this caller graph for each parameter we may find
1423 // nodes and edges more than once (which the per-param
1424 // "visit" sets won't show) and we only want to create
1425 // an element in the new callee view one time
1428 // a conservative starting point is to take the
1429 // mechanically-reachable-from-arguments graph
1430 // as opposed to using reachability information
1431 // to prune the graph further
1432 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1434 // for each parameter index, get the symbol in the
1435 // caller view and callee view
1437 // argument defined here is the symbol in the caller
1438 TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1440 // parameter defined here is the symbol in the callee
1441 TempDescriptor tdParam = fmCallee.getParameter( i );
1443 // use these two VariableNode objects to translate
1444 // between caller and callee--its easy to compare
1445 // a HeapRegionNode across callee and caller because
1446 // they will have the same heap region ID
1447 VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
1448 VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
1450 // now traverse the calleR view using the argument to
1451 // build the calleE view which has the parameter symbol
1452 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1453 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1454 toVisitInCaller.add( vnCaller );
1456 while( !toVisitInCaller.isEmpty() ) {
1457 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1458 RefSrcNode rsnCallee;
1460 toVisitInCaller.remove( rsnCaller );
1461 visitedInCaller.add( rsnCaller );
1463 // FIRST - setup the source end of an edge, and
1464 // remember the identifying info of the source
1465 // to build predicates
1466 TempDescriptor tdSrc = null;
1467 Integer hrnSrcID = null;
1469 if( rsnCaller == vnCaller ) {
1470 // if the caller node is the param symbol, we
1471 // have to do this translation for the callee
1472 rsnCallee = vnCallee;
1476 // otherwise the callee-view node is a heap
1477 // region with the same ID, that may or may
1478 // not have been created already
1479 assert rsnCaller instanceof HeapRegionNode;
1481 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1482 hrnSrcID = hrnSrcCaller.getID();
1484 if( !callerNodeIDsCopiedToCallee.contains( hrnSrcID ) ) {
1487 ExistPred.factory( hrnSrcID, null );
1489 ExistPredSet preds =
1490 ExistPredSet.factory( pred );
1493 rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
1494 hrnSrcCaller.isSingleObject(),
1495 hrnSrcCaller.isNewSummary(),
1496 hrnSrcCaller.isFlagged(),
1497 false, // out-of-context?
1498 hrnSrcCaller.getType(),
1499 hrnSrcCaller.getAllocSite(),
1500 toCalleeContext( hrnSrcCaller.getInherent(), // in state
1501 hrnSrcCaller.getID(), // node pred
1502 null, null, null, null, null, // edge pred
1503 false ), // ooc pred
1504 toCalleeContext( hrnSrcCaller.getAlpha(), // in state
1505 hrnSrcCaller.getID(), // node pred
1506 null, null, null, null, null, // edge pred
1507 false ), // ooc pred
1509 hrnSrcCaller.getDescription()
1512 callerNodeIDsCopiedToCallee.add( hrnSrcID );
1515 rsnCallee = rg.id2hrn.get( hrnSrcID );
1519 // SECOND - go over all edges from that source
1521 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1522 while( itrRefEdges.hasNext() ) {
1523 RefEdge reCaller = itrRefEdges.next();
1524 HeapRegionNode hrnCaller = reCaller.getDst();
1525 HeapRegionNode hrnCallee;
1527 // THIRD - setup destination ends of edges
1528 Integer hrnDstID = hrnCaller.getID();
1530 if( !callerNodeIDsCopiedToCallee.contains( hrnDstID ) ) {
1533 ExistPred.factory( hrnDstID, null );
1535 ExistPredSet preds =
1536 ExistPredSet.factory( pred );
1539 rg.createNewHeapRegionNode( hrnDstID,
1540 hrnCaller.isSingleObject(),
1541 hrnCaller.isNewSummary(),
1542 hrnCaller.isFlagged(),
1543 false, // out-of-context?
1544 hrnCaller.getType(),
1545 hrnCaller.getAllocSite(),
1546 toCalleeContext( hrnCaller.getInherent(), // in state
1547 hrnDstID, // node pred
1548 null, null, null, null, null, // edge pred
1549 false ), // ooc pred
1550 toCalleeContext( hrnCaller.getAlpha(), // in state
1551 hrnDstID, // node pred
1552 null, null, null, null, null, // edge pred
1553 false ), // ooc pred
1555 hrnCaller.getDescription()
1558 callerNodeIDsCopiedToCallee.add( hrnDstID );
1561 hrnCallee = rg.id2hrn.get( hrnDstID );
1564 // FOURTH - copy edge over if needed
1565 RefEdge reCallee = rsnCallee.getReferenceTo( hrnCallee,
1569 if( reCallee == null ) {
1572 ExistPred.factory( tdSrc,
1576 reCaller.getField(),
1578 rsnCaller instanceof VariableNode ); // out-of-context
1580 ExistPredSet preds =
1581 ExistPredSet.factory( pred );
1583 rg.addRefEdge( rsnCallee,
1585 new RefEdge( rsnCallee,
1588 reCaller.getField(),
1589 toCalleeContext( reCaller.getBeta(), // in state
1592 hrnSrcID, // edge pred
1593 hrnDstID, // edge pred
1594 reCaller.getType(), // edge pred
1595 reCaller.getField(), // edge pred
1596 false ), // ooc pred
1602 // keep traversing nodes reachable from param i
1603 // that we haven't visited yet
1604 if( !visitedInCaller.contains( hrnCaller ) ) {
1605 toVisitInCaller.add( hrnCaller );
1608 } // end edge iteration
1609 } // end visiting heap nodes in caller
1610 } // end iterating over parameters as starting points
1613 // find the set of edges in this graph with source
1614 // out-of-context (not in nodes copied) and have a
1615 // destination in context (one of nodes copied) as
1616 // a starting point for building out-of-context nodes
1617 Iterator<Integer> itrInContext =
1618 callerNodeIDsCopiedToCallee.iterator();
1619 while( itrInContext.hasNext() ) {
1620 Integer hrnID = itrInContext.next();
1621 HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1623 Iterator<RefEdge> itrMightCross =
1624 hrnCallerAndInContext.iteratorToReferencers();
1625 while( itrMightCross.hasNext() ) {
1626 RefEdge edgeMightCross = itrMightCross.next();
1628 RefSrcNode rsnCallerAndOutContext =
1629 edgeMightCross.getSrc();
1631 TypeDescriptor oocNodeType;
1634 TempDescriptor oocPredSrcTemp = null;
1635 Integer oocPredSrcID = null;
1637 if( rsnCallerAndOutContext instanceof VariableNode ) {
1638 // variables are always out-of-context
1640 oocReach = rsetEmpty;
1642 ((VariableNode)rsnCallerAndOutContext).getTempDescriptor();
1646 HeapRegionNode hrnCallerAndOutContext =
1647 (HeapRegionNode) rsnCallerAndOutContext;
1649 // is this source node out-of-context?
1650 if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1651 // no, skip this edge
1655 oocNodeType = hrnCallerAndOutContext.getType();
1656 oocReach = hrnCallerAndOutContext.getAlpha();
1657 oocPredSrcID = hrnCallerAndOutContext.getID();
1660 // if we're here we've found an out-of-context edge
1663 ExistPred.factory( oocPredSrcTemp,
1666 edgeMightCross.getType(),
1667 edgeMightCross.getField(),
1669 true ); // out-of-context
1671 ExistPredSet preds =
1672 ExistPredSet.factory( pred );
1675 HeapRegionNode hrnCalleeAndInContext =
1676 rg.id2hrn.get( hrnCallerAndInContext.getID() );
1678 RefEdge oocEdgeExisting =
1679 rg.getOutOfContextReferenceTo( hrnCalleeAndInContext,
1681 edgeMightCross.getType(),
1682 edgeMightCross.getField()
1685 if( oocEdgeExisting == null ) {
1686 // we found a reference that crosses from out-of-context
1687 // to in-context, so build a special out-of-context node
1688 // for the callee IHM and its reference edge
1690 // for consistency, map one out-of-context "identifier"
1691 // to one heap region node id, otherwise no convergence
1692 String oocid = "oocid"+
1694 hrnCalleeAndInContext.getIDString()+
1696 edgeMightCross.getType()+
1697 edgeMightCross.getField();
1699 Integer oocHrnID = oocid2hrnid.get( oocid );
1701 HeapRegionNode hrnCalleeAndOutContext;
1703 if( oocHrnID == null ) {
1705 hrnCalleeAndOutContext =
1706 rg.createNewHeapRegionNode( null, // ID
1707 false, // single object?
1708 false, // new summary?
1710 true, // out-of-context?
1712 null, // alloc site, shouldn't be used
1713 toCalleeContext( oocReach, // in state
1715 null, null, null, null, null, // edge pred
1718 toCalleeContext( oocReach, // in state
1720 null, null, null, null, null, // edge pred
1727 oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1731 // the mapping already exists, so see if node is there
1732 hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1734 if( hrnCalleeAndOutContext == null ) {
1736 hrnCalleeAndOutContext =
1737 rg.createNewHeapRegionNode( oocHrnID, // ID
1738 false, // single object?
1739 false, // new summary?
1741 true, // out-of-context?
1743 null, // alloc site, shouldn't be used
1744 toCalleeContext( oocReach, // in state
1746 null, null, null, null, null, // edge pred
1749 toCalleeContext( oocReach, // in state
1751 null, null, null, null, null, // edge pred
1760 rg.addRefEdge( hrnCalleeAndOutContext,
1761 hrnCalleeAndInContext,
1762 new RefEdge( hrnCalleeAndOutContext,
1763 hrnCalleeAndInContext,
1764 edgeMightCross.getType(),
1765 edgeMightCross.getField(),
1766 toCalleeContext( edgeMightCross.getBeta(), // in state
1768 oocPredSrcTemp, // edge pred
1769 oocPredSrcID, // edge pred
1770 hrnCallerAndInContext.getID(), // edge pred
1771 edgeMightCross.getType(), // edge pred
1772 edgeMightCross.getField(), // edge pred
1780 // the out-of-context edge already exists
1781 oocEdgeExisting.setBeta( Canonical.union( oocEdgeExisting.getBeta(),
1782 toCalleeContext( edgeMightCross.getBeta(), // in state
1784 oocPredSrcTemp, // edge pred
1785 oocPredSrcID, // edge pred
1786 hrnCallerAndInContext.getID(), // edge pred
1787 edgeMightCross.getType(), // edge pred
1788 edgeMightCross.getField(), // edge pred
1794 oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1795 edgeMightCross.getPreds()
1803 if( writeDebugDOTs ) {
1805 rg.writeGraph( "calleeview", true, false, false, false, true, true );
1806 } catch( IOException e ) {}
1812 private static Hashtable<String, Integer> oocid2hrnid =
1813 new Hashtable<String, Integer>();
1818 resolveMethodCall( FlatCall fc,
1819 FlatMethod fmCallee,
1820 ReachGraph rgCallee,
1821 Set<Integer> callerNodeIDsCopiedToCallee,
1822 boolean writeDebugDOTs
1826 if( writeDebugDOTs ) {
1828 rgCallee.writeGraph( "callee",
1829 true, false, false, false, true, true );
1830 writeGraph( "caller00In",
1831 true, false, false, false, true, true,
1832 callerNodeIDsCopiedToCallee );
1833 } catch( IOException e ) {}
1837 // method call transfer function steps:
1838 // 1. Use current callee-reachable heap (CRH) to test callee
1839 // predicates and mark what will be coming in.
1840 // 2. Wipe CRH out of caller.
1841 // 3. Transplant marked callee parts in:
1842 // a) bring in nodes
1843 // b) bring in callee -> callee edges
1844 // c) resolve out-of-context -> callee edges
1845 // d) assign return value
1846 // 4. Collapse shadow nodes down
1847 // 5. Global sweep it.
1851 // 1. mark what callee elements have satisfied predicates
1852 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1853 new Hashtable<HeapRegionNode, ExistPredSet>();
1855 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1856 new Hashtable<RefEdge, ExistPredSet>();
1858 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1859 new Hashtable<ReachState, ExistPredSet>();
1861 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1862 new Hashtable< RefEdge, Set<RefSrcNode> >();
1864 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1865 while( meItr.hasNext() ) {
1866 Map.Entry me = (Map.Entry) meItr.next();
1867 Integer id = (Integer) me.getKey();
1868 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1870 // if a callee element's predicates are satisfied then a set
1871 // of CALLER predicates is returned: they are the predicates
1872 // that the callee element moved into the caller context
1873 // should have, and it is inefficient to find this again later
1874 ExistPredSet predsIfSatis =
1875 hrnCallee.getPreds().isSatisfiedBy( this,
1876 callerNodeIDsCopiedToCallee
1878 if( predsIfSatis != null ) {
1879 calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1881 // otherwise don't bother looking at edges to this node
1885 // since the node is coming over, find out which reach
1886 // states on it should come over, too
1887 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
1888 while( stateItr.hasNext() ) {
1889 ReachState stateCallee = stateItr.next();
1892 stateCallee.getPreds().isSatisfiedBy( this,
1893 callerNodeIDsCopiedToCallee
1895 if( predsIfSatis != null ) {
1896 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
1900 // then look at edges to the node
1901 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
1902 while( reItr.hasNext() ) {
1903 RefEdge reCallee = reItr.next();
1904 RefSrcNode rsnCallee = reCallee.getSrc();
1906 // (caller local variables to in-context heap regions)
1907 // have an (out-of-context heap region -> in-context heap region)
1908 // abstraction in the callEE, so its true we never need to
1909 // look at a (var node -> heap region) edge in callee to bring
1910 // those over for the call site transfer. What about (param var->heap region)
1911 // edges in callee? They are dealt with below this loop.
1912 // So, yes, at this point skip (var->region) edges in callee
1913 if( rsnCallee instanceof VariableNode ) {
1917 // first see if the source is out-of-context, and only
1918 // proceed with this edge if we find some caller-context
1920 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
1921 boolean matchedOutOfContext = false;
1923 if( hrnSrcCallee.isOutOfContext() ) {
1925 assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
1926 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
1928 HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
1929 Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
1930 while( reDstItr.hasNext() ) {
1931 // the edge and field (either possibly null) must match
1932 RefEdge reCaller = reDstItr.next();
1934 if( !reCaller.typeEquals ( reCallee.getType() ) ||
1935 !reCaller.fieldEquals( reCallee.getField() )
1940 RefSrcNode rsnCaller = reCaller.getSrc();
1941 if( rsnCaller instanceof VariableNode ) {
1942 // a variable node matches an OOC region with null type
1943 if( hrnSrcCallee.getType() != null ) {
1948 // otherwise types should match
1949 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
1950 if( hrnSrcCallee.getType() == null ) {
1951 if( hrnCallerSrc.getType() != null ) {
1955 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
1961 rsnCallers.add( rsnCaller );
1962 matchedOutOfContext = true;
1965 if( !rsnCallers.isEmpty() ) {
1966 calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
1970 if( hrnSrcCallee.isOutOfContext() &&
1971 !matchedOutOfContext ) {
1976 reCallee.getPreds().isSatisfiedBy( this,
1977 callerNodeIDsCopiedToCallee
1979 if( predsIfSatis != null ) {
1980 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
1982 // since the edge is coming over, find out which reach
1983 // states on it should come over, too
1984 stateItr = reCallee.getBeta().iterator();
1985 while( stateItr.hasNext() ) {
1986 ReachState stateCallee = stateItr.next();
1989 stateCallee.getPreds().isSatisfiedBy( this,
1990 callerNodeIDsCopiedToCallee
1992 if( predsIfSatis != null ) {
1993 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2002 // test param -> HRN edges, also
2003 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
2005 // parameter defined here is the symbol in the callee
2006 TempDescriptor tdParam = fmCallee.getParameter( i );
2007 VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
2009 Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
2010 while( reItr.hasNext() ) {
2011 RefEdge reCallee = reItr.next();
2013 ExistPredSet ifDst =
2014 reCallee.getDst().getPreds().isSatisfiedBy( this,
2015 callerNodeIDsCopiedToCallee
2017 if( ifDst == null ) {
2021 ExistPredSet predsIfSatis =
2022 reCallee.getPreds().isSatisfiedBy( this,
2023 callerNodeIDsCopiedToCallee
2025 if( predsIfSatis != null ) {
2026 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2028 // since the edge is coming over, find out which reach
2029 // states on it should come over, too
2030 Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
2031 while( stateItr.hasNext() ) {
2032 ReachState stateCallee = stateItr.next();
2035 stateCallee.getPreds().isSatisfiedBy( this,
2036 callerNodeIDsCopiedToCallee
2038 if( predsIfSatis != null ) {
2039 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2050 if( writeDebugDOTs ) {
2052 writeGraph( "caller20BeforeWipe",
2053 true, false, false, false, true, true );
2054 } catch( IOException e ) {}
2058 // 2. predicates tested, ok to wipe out caller part
2059 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2060 while( hrnItr.hasNext() ) {
2061 Integer hrnID = hrnItr.next();
2062 HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2063 assert hrnCaller != null;
2065 // when clearing off nodes, also eliminate variable
2067 wipeOut( hrnCaller, true );
2072 if( writeDebugDOTs ) {
2074 writeGraph( "caller30BeforeAddingNodes",
2075 true, false, false, false, true, true );
2076 } catch( IOException e ) {}
2080 // 3. callee elements with satisfied preds come in, note that
2081 // the mapping of elements satisfied to preds is like this:
2082 // A callee element EE has preds EEp that are satisfied by
2083 // some caller element ER. We bring EE into the caller
2084 // context as ERee with the preds of ER, namely ERp, which
2085 // in the following algorithm is the value in the mapping
2088 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2089 while( satisItr.hasNext() ) {
2090 Map.Entry me = (Map.Entry) satisItr.next();
2091 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2092 ExistPredSet preds = (ExistPredSet) me.getValue();
2094 // TODO: I think its true that the current implementation uses
2095 // the type of the OOC region and the predicates OF THE EDGE from
2096 // it to link everything up in caller context, so that's why we're
2097 // skipping this... maybe that's a sillier way to do it?
2098 if( hrnCallee.isOutOfContext() ) {
2102 AllocSite as = hrnCallee.getAllocSite();
2103 allocSites.add( as );
2105 Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2107 HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2108 if( hrnCaller == null ) {
2110 createNewHeapRegionNode( hrnIDshadow, // id or null to generate a new one
2111 hrnCallee.isSingleObject(), // single object?
2112 hrnCallee.isNewSummary(), // summary?
2113 hrnCallee.isFlagged(), // flagged?
2114 false, // out-of-context?
2115 hrnCallee.getType(), // type
2116 hrnCallee.getAllocSite(), // allocation site
2117 toCallerContext( hrnCallee.getInherent(),
2118 calleeStatesSatisfied ), // inherent reach
2119 null, // current reach
2120 predsEmpty, // predicates
2121 hrnCallee.getDescription() // description
2124 assert hrnCaller.isWiped();
2127 hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2128 calleeStatesSatisfied
2132 hrnCaller.setPreds( preds );
2137 if( writeDebugDOTs ) {
2139 writeGraph( "caller31BeforeAddingEdges",
2140 true, false, false, false, true, true );
2141 } catch( IOException e ) {}
2145 // 3.b) callee -> callee edges AND out-of-context -> callee
2146 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2147 while( satisItr.hasNext() ) {
2148 Map.Entry me = (Map.Entry) satisItr.next();
2149 RefEdge reCallee = (RefEdge) me.getKey();
2150 ExistPredSet preds = (ExistPredSet) me.getValue();
2152 HeapRegionNode hrnDstCallee = reCallee.getDst();
2153 AllocSite asDst = hrnDstCallee.getAllocSite();
2154 allocSites.add( asDst );
2156 Integer hrnIDDstShadow =
2157 asDst.getShadowIDfromID( hrnDstCallee.getID() );
2159 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2160 assert hrnDstCaller != null;
2163 RefSrcNode rsnCallee = reCallee.getSrc();
2165 Set<RefSrcNode> rsnCallers =
2166 new HashSet<RefSrcNode>();
2168 Set<RefSrcNode> oocCallers =
2169 calleeEdges2oocCallerSrcMatches.get( reCallee );
2171 if( oocCallers == null ) {
2172 // there are no out-of-context matches, so it's
2173 // either a param/arg var or one in-context heap region
2174 if( rsnCallee instanceof VariableNode ) {
2175 // variable -> node in the callee should only
2176 // come into the caller if its from a param var
2177 VariableNode vnCallee = (VariableNode) rsnCallee;
2178 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2179 TempDescriptor tdArg = fc.getArgMatchingParam( fmCallee,
2181 if( tdArg == null ) {
2182 // this means the variable isn't a parameter, its local
2183 // to the callee so we ignore it in call site transfer
2184 // shouldn't this NEVER HAPPEN?
2188 rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2191 // otherwise source is in context, one region
2192 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2194 // translate an in-context node to shadow
2195 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2196 allocSites.add( asSrc );
2198 Integer hrnIDSrcShadow =
2199 asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2201 HeapRegionNode hrnSrcCallerShadow =
2202 this.id2hrn.get( hrnIDSrcShadow );
2204 if( hrnSrcCallerShadow == null ) {
2205 hrnSrcCallerShadow =
2206 createNewHeapRegionNode( hrnIDSrcShadow, // id or null to generate a new one
2207 hrnSrcCallee.isSingleObject(), // single object?
2208 hrnSrcCallee.isNewSummary(), // summary?
2209 hrnSrcCallee.isFlagged(), // flagged?
2210 false, // out-of-context?
2211 hrnSrcCallee.getType(), // type
2212 hrnSrcCallee.getAllocSite(), // allocation site
2213 toCallerContext( hrnSrcCallee.getInherent(),
2214 calleeStatesSatisfied ), // inherent reach
2215 toCallerContext( hrnSrcCallee.getAlpha(),
2216 calleeStatesSatisfied ), // current reach
2217 predsEmpty, // predicates
2218 hrnSrcCallee.getDescription() // description
2222 rsnCallers.add( hrnSrcCallerShadow );
2226 // otherwise we have a set of out-of-context srcs
2227 // that should NOT be translated to shadow nodes
2228 assert !oocCallers.isEmpty();
2229 rsnCallers.addAll( oocCallers );
2232 // now make all caller edges we've identified from
2233 // this callee edge with a satisfied predicate
2234 assert !rsnCallers.isEmpty();
2235 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2236 while( rsnItr.hasNext() ) {
2237 RefSrcNode rsnCaller = rsnItr.next();
2239 // TODO: beta rewrites
2240 RefEdge reCaller = new RefEdge( rsnCaller,
2243 reCallee.getField(),
2244 toCallerContext( reCallee.getBeta(),
2245 calleeStatesSatisfied ),
2249 // look to see if an edge with same field exists
2250 // and merge with it, otherwise just add the edge
2251 RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2255 if( edgeExisting != null ) {
2256 edgeExisting.setBeta(
2257 Canonical.union( edgeExisting.getBeta(),
2261 edgeExisting.setPreds(
2262 Canonical.join( edgeExisting.getPreds(),
2268 addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2277 if( writeDebugDOTs ) {
2279 writeGraph( "caller35BeforeAssignReturnValue",
2280 true, false, false, false, true, true );
2281 } catch( IOException e ) {}
2286 // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2287 // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2288 // EDGES, JUST BRINGING THEM ALL! It'll work for now, over approximation
2290 // 3.d) handle return value assignment if needed
2291 TempDescriptor returnTemp = fc.getReturnTemp();
2292 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2294 VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2295 clearRefEdgesFrom( vnLhsCaller, null, null, true );
2297 VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2298 Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2299 while( reCalleeItr.hasNext() ) {
2300 RefEdge reCallee = reCalleeItr.next();
2301 HeapRegionNode hrnDstCallee = reCallee.getDst();
2303 // some edge types are not possible return values when we can
2304 // see what type variable we are assigning it to
2305 if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2306 System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2307 reCallee+" for return temp "+returnTemp );
2312 AllocSite asDst = hrnDstCallee.getAllocSite();
2313 allocSites.add( asDst );
2315 Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2317 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2318 if( hrnDstCaller == null ) {
2320 createNewHeapRegionNode( hrnIDDstShadow, // id or null to generate a new one
2321 hrnDstCallee.isSingleObject(), // single object?
2322 hrnDstCallee.isNewSummary(), // summary?
2323 hrnDstCallee.isFlagged(), // flagged?
2324 false, // out-of-context?
2325 hrnDstCallee.getType(), // type
2326 hrnDstCallee.getAllocSite(), // allocation site
2327 toCallerContext( hrnDstCallee.getInherent(),
2328 calleeStatesSatisfied ), // inherent reach
2329 toCallerContext( hrnDstCallee.getAlpha(),
2330 calleeStatesSatisfied ), // current reach
2331 predsTrue, // predicates
2332 hrnDstCallee.getDescription() // description
2335 assert hrnDstCaller.isWiped();
2338 TypeDescriptor tdNewEdge =
2339 mostSpecificType( reCallee.getType(),
2340 hrnDstCallee.getType(),
2341 hrnDstCaller.getType()
2344 RefEdge reCaller = new RefEdge( vnLhsCaller,
2348 toCallerContext( reCallee.getBeta(),
2349 calleeStatesSatisfied ),
2353 addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2359 if( writeDebugDOTs ) {
2361 writeGraph( "caller40BeforeShadowMerge",
2362 true, false, false, false, true, true );
2363 } catch( IOException e ) {}
2367 // 4) merge shadow nodes so alloc sites are back to k
2368 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2369 while( asItr.hasNext() ) {
2370 // for each allocation site do the following to merge
2371 // shadow nodes (newest from callee) with any existing
2372 // look for the newest normal and newest shadow "slot"
2373 // not being used, transfer normal to shadow. Keep
2374 // doing this until there are no more normal nodes, or
2375 // no empty shadow slots: then merge all remaining normal
2376 // nodes into the shadow summary. Finally, convert all
2377 // shadow to their normal versions.
2378 AllocSite as = asItr.next();
2381 while( ageNorm < allocationDepth &&
2382 ageShad < allocationDepth ) {
2384 // first, are there any normal nodes left?
2385 Integer idNorm = as.getIthOldest( ageNorm );
2386 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2387 if( hrnNorm == null ) {
2388 // no, this age of normal node not in the caller graph
2393 // yes, a normal node exists, is there an empty shadow
2394 // "slot" to transfer it onto?
2395 HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2396 if( !hrnShad.isWiped() ) {
2397 // no, this age of shadow node is not empty
2402 // yes, this shadow node is empty
2403 transferOnto( hrnNorm, hrnShad );
2408 // now, while there are still normal nodes but no shadow
2409 // slots, merge normal nodes into the shadow summary
2410 while( ageNorm < allocationDepth ) {
2412 // first, are there any normal nodes left?
2413 Integer idNorm = as.getIthOldest( ageNorm );
2414 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2415 if( hrnNorm == null ) {
2416 // no, this age of normal node not in the caller graph
2421 // yes, a normal node exists, so get the shadow summary
2422 HeapRegionNode summShad = getSummaryNode( as, true );
2423 mergeIntoSummary( hrnNorm, summShad );
2427 // if there is a normal summary, merge it into shadow summary
2428 Integer idNorm = as.getSummary();
2429 HeapRegionNode summNorm = id2hrn.get( idNorm );
2430 if( summNorm != null ) {
2431 HeapRegionNode summShad = getSummaryNode( as, true );
2432 mergeIntoSummary( summNorm, summShad );
2435 // finally, flip all existing shadow nodes onto the normal
2436 for( int i = 0; i < allocationDepth; ++i ) {
2437 Integer idShad = as.getIthOldestShadow( i );
2438 HeapRegionNode hrnShad = id2hrn.get( idShad );
2439 if( hrnShad != null ) {
2441 HeapRegionNode hrnNorm = getIthNode( as, i, false );
2442 assert hrnNorm.isWiped();
2443 transferOnto( hrnShad, hrnNorm );
2447 Integer idShad = as.getSummaryShadow();
2448 HeapRegionNode summShad = id2hrn.get( idShad );
2449 if( summShad != null ) {
2450 summNorm = getSummaryNode( as, false );
2451 transferOnto( summShad, summNorm );
2456 if( writeDebugDOTs ) {
2458 writeGraph( "caller45BeforeUnshadow",
2459 true, false, false, false, true, true );
2460 } catch( IOException e ) {}
2464 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2465 while( itrAllHRNodes.hasNext() ) {
2466 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
2467 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2469 hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2471 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2472 while( itrEdges.hasNext() ) {
2473 RefEdge re = itrEdges.next();
2474 re.setBeta( unshadow( re.getBeta() ) );
2480 if( writeDebugDOTs ) {
2482 writeGraph( "caller50BeforeGlobalSweep",
2483 true, false, false, false, true, true );
2484 } catch( IOException e ) {}
2489 if( !DISABLE_GLOBAL_SWEEP ) {
2495 if( writeDebugDOTs ) {
2497 writeGraph( "caller90AfterTransfer",
2498 true, false, false, false, true, true );
2499 } catch( IOException e ) {}
2505 ////////////////////////////////////////////////////
2507 // Abstract garbage collection simply removes
2508 // heap region nodes that are not mechanically
2509 // reachable from a root set. This step is
2510 // essential for testing node and edge existence
2511 // predicates efficiently
2513 ////////////////////////////////////////////////////
2514 public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2516 // calculate a root set, will be different for Java
2517 // version of analysis versus Bamboo version
2518 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2520 // visit every variable in graph while building root
2521 // set, and do iterating on a copy, so we can remove
2522 // dead variables while we're at this
2523 Iterator makeCopyItr = td2vn.entrySet().iterator();
2524 Set entrysCopy = new HashSet();
2525 while( makeCopyItr.hasNext() ) {
2526 entrysCopy.add( makeCopyItr.next() );
2529 Iterator eItr = entrysCopy.iterator();
2530 while( eItr.hasNext() ) {
2531 Map.Entry me = (Map.Entry) eItr.next();
2532 TempDescriptor td = (TempDescriptor) me.getKey();
2533 VariableNode vn = (VariableNode) me.getValue();
2535 if( liveSet.contains( td ) ) {
2539 // dead var, remove completely from graph
2541 clearRefEdgesFrom( vn, null, null, true );
2545 // everything visited in a traversal is
2546 // considered abstractly live
2547 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2549 while( !toVisit.isEmpty() ) {
2550 RefSrcNode rsn = toVisit.iterator().next();
2551 toVisit.remove( rsn );
2554 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2555 while( hrnItr.hasNext() ) {
2556 RefEdge edge = hrnItr.next();
2557 HeapRegionNode hrn = edge.getDst();
2559 if( !visited.contains( hrn ) ) {
2565 // get a copy of the set to iterate over because
2566 // we're going to monkey with the graph when we
2567 // identify a garbage node
2568 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2569 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2570 while( hrnItr.hasNext() ) {
2571 hrnAllPrior.add( hrnItr.next() );
2574 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2575 while( hrnAllItr.hasNext() ) {
2576 HeapRegionNode hrn = hrnAllItr.next();
2578 if( !visited.contains( hrn ) ) {
2580 // heap region nodes are compared across ReachGraph
2581 // objects by their integer ID, so when discarding
2582 // garbage nodes we must also discard entries in
2583 // the ID -> heap region hashtable.
2584 id2hrn.remove( hrn.getID() );
2586 // RefEdge objects are two-way linked between
2587 // nodes, so when a node is identified as garbage,
2588 // actively clear references to and from it so
2589 // live nodes won't have dangling RefEdge's
2590 wipeOut( hrn, true );
2592 // if we just removed the last node from an allocation
2593 // site, it should be taken out of the ReachGraph's list
2594 AllocSite as = hrn.getAllocSite();
2595 if( !hasNodesOf( as ) ) {
2596 allocSites.remove( as );
2602 protected boolean hasNodesOf( AllocSite as ) {
2603 if( id2hrn.containsKey( as.getSummary() ) ) {
2607 for( int i = 0; i < allocationDepth; ++i ) {
2608 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2616 ////////////////////////////////////////////////////
2618 // This global sweep is an optional step to prune
2619 // reachability sets that are not internally
2620 // consistent with the global graph. It should be
2621 // invoked after strong updates or method calls.
2623 ////////////////////////////////////////////////////
2624 public void globalSweep() {
2626 // boldB is part of the phase 1 sweep
2627 // it has an in-context table and an out-of-context table
2628 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2629 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2631 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2632 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2634 // visit every heap region to initialize alphaNew and betaNew,
2635 // and make a map of every hrnID to the source nodes it should
2636 // propagate forward from. In-context flagged hrnID's propagate
2637 // from only the in-context node they name, but out-of-context
2638 // ID's may propagate from several out-of-context nodes
2639 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2640 new Hashtable< Integer, Set<HeapRegionNode> >();
2642 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2643 new Hashtable< Integer, Set<HeapRegionNode> >();
2646 Iterator itrHrns = id2hrn.entrySet().iterator();
2647 while( itrHrns.hasNext() ) {
2648 Map.Entry me = (Map.Entry) itrHrns.next();
2649 Integer hrnID = (Integer) me.getKey();
2650 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2652 // assert that this node and incoming edges have clean alphaNew
2653 // and betaNew sets, respectively
2654 assert rsetEmpty.equals( hrn.getAlphaNew() );
2656 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2657 while( itrRers.hasNext() ) {
2658 RefEdge edge = itrRers.next();
2659 assert rsetEmpty.equals( edge.getBetaNew() );
2662 // calculate boldB for this flagged node, or out-of-context node
2663 if( hrn.isFlagged() ) {
2664 assert !hrn.isOutOfContext();
2665 assert !icID2srcs.containsKey( hrn.getID() );
2666 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2668 icID2srcs.put( hrn.getID(), srcs );
2671 if( hrn.isOutOfContext() ) {
2672 assert !hrn.isFlagged();
2674 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2675 while( stateItr.hasNext() ) {
2676 ReachState state = stateItr.next();
2678 Iterator<ReachTuple> rtItr = state.iterator();
2679 while( rtItr.hasNext() ) {
2680 ReachTuple rt = rtItr.next();
2681 assert rt.isOutOfContext();
2683 Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2684 if( srcs == null ) {
2685 srcs = new HashSet<HeapRegionNode>();
2688 oocID2srcs.put( rt.getHrnID(), srcs );
2694 // calculate boldB for all hrnIDs identified by the above
2695 // node traversal, propagating from every source
2696 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2699 Set<HeapRegionNode> srcs;
2702 if( !icID2srcs.isEmpty() ) {
2703 Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2704 hrnID = (Integer) me.getKey();
2705 srcs = (Set<HeapRegionNode>) me.getValue();
2707 icID2srcs.remove( hrnID );
2710 assert !oocID2srcs.isEmpty();
2712 Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2713 hrnID = (Integer) me.getKey();
2714 srcs = (Set<HeapRegionNode>) me.getValue();
2716 oocID2srcs.remove( hrnID );
2720 Hashtable<RefEdge, ReachSet> boldB_f =
2721 new Hashtable<RefEdge, ReachSet>();
2723 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2725 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2726 while( hrnItr.hasNext() ) {
2727 HeapRegionNode hrn = hrnItr.next();
2729 assert workSetEdges.isEmpty();
2731 // initial boldB_f constraints
2732 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2733 while( itrRees.hasNext() ) {
2734 RefEdge edge = itrRees.next();
2736 assert !boldB_f.containsKey( edge );
2737 boldB_f.put( edge, edge.getBeta() );
2739 assert !workSetEdges.contains( edge );
2740 workSetEdges.add( edge );
2743 // enforce the boldB_f constraint at edges until we reach a fixed point
2744 while( !workSetEdges.isEmpty() ) {
2745 RefEdge edge = workSetEdges.iterator().next();
2746 workSetEdges.remove( edge );
2748 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2749 while( itrPrime.hasNext() ) {
2750 RefEdge edgePrime = itrPrime.next();
2752 ReachSet prevResult = boldB_f.get( edgePrime );
2753 ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2757 if( prevResult == null ||
2758 Canonical.union( prevResult,
2759 intersection ).size() > prevResult.size() ) {
2761 if( prevResult == null ) {
2762 boldB_f.put( edgePrime,
2763 Canonical.union( edgePrime.getBeta(),
2768 boldB_f.put( edgePrime,
2769 Canonical.union( prevResult,
2774 workSetEdges.add( edgePrime );
2781 boldBic.put( hrnID, boldB_f );
2783 boldBooc.put( hrnID, boldB_f );
2788 // use boldB to prune hrnIDs from alpha states that are impossible
2789 // and propagate the differences backwards across edges
2790 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2792 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2793 new Hashtable<RefEdge, ChangeSet>();
2796 itrHrns = id2hrn.entrySet().iterator();
2797 while( itrHrns.hasNext() ) {
2798 Map.Entry me = (Map.Entry) itrHrns.next();
2799 Integer hrnID = (Integer) me.getKey();
2800 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2802 // out-of-context nodes don't participate in the
2803 // global sweep, they serve as sources for the pass
2805 if( hrn.isOutOfContext() ) {
2809 // the inherent states of a region are the exception
2810 // to removal as the global sweep prunes
2811 ReachTuple rtException = ReachTuple.factory( hrnID,
2812 !hrn.isSingleObject(),
2813 ReachTuple.ARITY_ONE,
2814 false // out-of-context
2817 ChangeSet cts = ChangeSet.factory();
2819 // mark hrnIDs for removal
2820 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2821 while( stateItr.hasNext() ) {
2822 ReachState stateOld = stateItr.next();
2824 ReachState markedHrnIDs = ReachState.factory();
2826 Iterator<ReachTuple> rtItr = stateOld.iterator();
2827 while( rtItr.hasNext() ) {
2828 ReachTuple rtOld = rtItr.next();
2830 // never remove the inherent hrnID from a flagged region
2831 // because it is trivially satisfied
2832 if( hrn.isFlagged() ) {
2833 if( rtOld == rtException ) {
2838 // does boldB allow this hrnID?
2839 boolean foundState = false;
2840 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2841 while( incidentEdgeItr.hasNext() ) {
2842 RefEdge incidentEdge = incidentEdgeItr.next();
2844 Hashtable<RefEdge, ReachSet> B;
2845 if( rtOld.isOutOfContext() ) {
2846 B = boldBooc.get( rtOld.getHrnID() );
2848 assert id2hrn.containsKey( rtOld.getHrnID() );
2849 B = boldBic.get( rtOld.getHrnID() );
2854 writeGraph( "glob", true, false, false, false, true, true );
2855 } catch( IOException e ) {}
2856 System.out.println( " need B for "+rtOld );
2861 ReachSet boldB_rtOld_incident = B.get( incidentEdge );
2862 if( boldB_rtOld_incident != null &&
2863 boldB_rtOld_incident.contains( stateOld ) ) {
2870 markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
2874 // if there is nothing marked, just move on
2875 if( markedHrnIDs.isEmpty() ) {
2876 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2883 // remove all marked hrnIDs and establish a change set that should
2884 // propagate backwards over edges from this node
2885 ReachState statePruned = ReachState.factory();
2886 rtItr = stateOld.iterator();
2887 while( rtItr.hasNext() ) {
2888 ReachTuple rtOld = rtItr.next();
2890 if( !markedHrnIDs.containsTuple( rtOld ) ) {
2891 statePruned = Canonical.union( statePruned, rtOld );
2894 assert !stateOld.equals( statePruned );
2896 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2900 ChangeTuple ct = ChangeTuple.factory( stateOld,
2903 cts = Canonical.union( cts, ct );
2906 // throw change tuple set on all incident edges
2907 if( !cts.isEmpty() ) {
2908 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2909 while( incidentEdgeItr.hasNext() ) {
2910 RefEdge incidentEdge = incidentEdgeItr.next();
2912 edgesForPropagation.add( incidentEdge );
2914 if( edgePlannedChanges.get( incidentEdge ) == null ) {
2915 edgePlannedChanges.put( incidentEdge, cts );
2917 edgePlannedChanges.put(
2919 Canonical.union( edgePlannedChanges.get( incidentEdge ),
2928 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2930 propagateTokensOverEdges( edgesForPropagation,
2934 // at the end of the 1st phase reference edges have
2935 // beta, betaNew that correspond to beta and betaR
2937 // commit beta<-betaNew, so beta=betaR and betaNew
2938 // will represent the beta' calculation in 2nd phase
2940 // commit alpha<-alphaNew because it won't change
2941 HashSet<RefEdge> res = new HashSet<RefEdge>();
2943 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2944 while( nodeItr.hasNext() ) {
2945 HeapRegionNode hrn = nodeItr.next();
2946 hrn.applyAlphaNew();
2947 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
2948 while( itrRes.hasNext() ) {
2949 res.add( itrRes.next() );
2955 Iterator<RefEdge> edgeItr = res.iterator();
2956 while( edgeItr.hasNext() ) {
2957 RefEdge edge = edgeItr.next();
2958 HeapRegionNode hrn = edge.getDst();
2960 // commit results of last phase
2961 if( edgesUpdated.contains( edge ) ) {
2962 edge.applyBetaNew();
2965 // compute intial condition of 2nd phase
2966 edge.setBetaNew( Canonical.intersection( edge.getBeta(),
2972 // every edge in the graph is the initial workset
2973 Set<RefEdge> edgeWorkSet = (Set) res.clone();
2974 while( !edgeWorkSet.isEmpty() ) {
2975 RefEdge edgePrime = edgeWorkSet.iterator().next();
2976 edgeWorkSet.remove( edgePrime );
2978 RefSrcNode rsn = edgePrime.getSrc();
2979 if( !(rsn instanceof HeapRegionNode) ) {
2982 HeapRegionNode hrn = (HeapRegionNode) rsn;
2984 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
2985 while( itrEdge.hasNext() ) {
2986 RefEdge edge = itrEdge.next();
2988 ReachSet prevResult = edge.getBetaNew();
2989 assert prevResult != null;
2991 ReachSet intersection =
2992 Canonical.intersection( edge.getBeta(),
2993 edgePrime.getBetaNew()
2996 if( Canonical.union( prevResult,
2998 ).size() > prevResult.size() ) {
3000 Canonical.union( prevResult,
3004 edgeWorkSet.add( edge );
3009 // commit beta' (beta<-betaNew)
3010 edgeItr = res.iterator();
3011 while( edgeItr.hasNext() ) {
3012 edgeItr.next().applyBetaNew();
3018 ////////////////////////////////////////////////////
3019 // high-level merge operations
3020 ////////////////////////////////////////////////////
3021 public void merge_sameMethodContext( ReachGraph rg ) {
3022 // when merging two graphs that abstract the heap
3023 // of the same method context, we just call the
3024 // basic merge operation
3028 public void merge_diffMethodContext( ReachGraph rg ) {
3029 // when merging graphs for abstract heaps in
3030 // different method contexts we should:
3031 // 1) age the allocation sites?
3035 ////////////////////////////////////////////////////
3036 // in merge() and equals() methods the suffix A
3037 // represents the passed in graph and the suffix
3038 // B refers to the graph in this object
3039 // Merging means to take the incoming graph A and
3040 // merge it into B, so after the operation graph B
3041 // is the final result.
3042 ////////////////////////////////////////////////////
3043 protected void merge( ReachGraph rg ) {
3050 mergeRefEdges ( rg );
3051 mergeAllocSites( rg );
3054 protected void mergeNodes( ReachGraph rg ) {
3056 // start with heap region nodes
3057 Set sA = rg.id2hrn.entrySet();
3058 Iterator iA = sA.iterator();
3059 while( iA.hasNext() ) {
3060 Map.Entry meA = (Map.Entry) iA.next();
3061 Integer idA = (Integer) meA.getKey();
3062 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3064 // if this graph doesn't have a node the
3065 // incoming graph has, allocate it
3066 if( !id2hrn.containsKey( idA ) ) {
3067 HeapRegionNode hrnB = hrnA.copy();
3068 id2hrn.put( idA, hrnB );
3071 // otherwise this is a node present in both graphs
3072 // so make the new reachability set a union of the
3073 // nodes' reachability sets
3074 HeapRegionNode hrnB = id2hrn.get( idA );
3075 hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
3080 // if hrnB is already dirty or hrnA is dirty,
3081 // the hrnB should end up dirty: TODO
3083 if( !hrnA.isClean() ) {
3084 hrnB.setIsClean( false );
3090 // now add any variable nodes that are in graph B but
3092 sA = rg.td2vn.entrySet();
3094 while( iA.hasNext() ) {
3095 Map.Entry meA = (Map.Entry) iA.next();
3096 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3097 VariableNode lnA = (VariableNode) meA.getValue();
3099 // if the variable doesn't exist in B, allocate and add it
3100 VariableNode lnB = getVariableNodeFromTemp( tdA );
3104 protected void mergeRefEdges( ReachGraph rg ) {
3106 // between heap regions
3107 Set sA = rg.id2hrn.entrySet();
3108 Iterator iA = sA.iterator();
3109 while( iA.hasNext() ) {
3110 Map.Entry meA = (Map.Entry) iA.next();
3111 Integer idA = (Integer) meA.getKey();
3112 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3114 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3115 while( heapRegionsItrA.hasNext() ) {
3116 RefEdge edgeA = heapRegionsItrA.next();
3117 HeapRegionNode hrnChildA = edgeA.getDst();
3118 Integer idChildA = hrnChildA.getID();
3120 // at this point we know an edge in graph A exists
3121 // idA -> idChildA, does this exist in B?
3122 assert id2hrn.containsKey( idA );
3123 HeapRegionNode hrnB = id2hrn.get( idA );
3124 RefEdge edgeToMerge = null;
3126 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3127 while( heapRegionsItrB.hasNext() &&
3128 edgeToMerge == null ) {
3130 RefEdge edgeB = heapRegionsItrB.next();
3131 HeapRegionNode hrnChildB = edgeB.getDst();
3132 Integer idChildB = hrnChildB.getID();
3134 // don't use the RefEdge.equals() here because
3135 // we're talking about existence between graphs,
3136 // not intragraph equal
3137 if( idChildB.equals( idChildA ) &&
3138 edgeB.typeAndFieldEquals( edgeA ) ) {
3140 edgeToMerge = edgeB;
3144 // if the edge from A was not found in B,
3146 if( edgeToMerge == null ) {
3147 assert id2hrn.containsKey( idChildA );
3148 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3149 edgeToMerge = edgeA.copy();
3150 edgeToMerge.setSrc( hrnB );
3151 edgeToMerge.setDst( hrnChildB );
3152 addRefEdge( hrnB, hrnChildB, edgeToMerge );
3154 // otherwise, the edge already existed in both graphs
3155 // so merge their reachability sets
3157 // just replace this beta set with the union
3158 assert edgeToMerge != null;
3159 edgeToMerge.setBeta(
3160 Canonical.union( edgeToMerge.getBeta(),
3166 if( !edgeA.isClean() ) {
3167 edgeToMerge.setIsClean( false );
3174 // and then again from variable nodes
3175 sA = rg.td2vn.entrySet();
3177 while( iA.hasNext() ) {
3178 Map.Entry meA = (Map.Entry) iA.next();
3179 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3180 VariableNode vnA = (VariableNode) meA.getValue();
3182 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3183 while( heapRegionsItrA.hasNext() ) {
3184 RefEdge edgeA = heapRegionsItrA.next();
3185 HeapRegionNode hrnChildA = edgeA.getDst();
3186 Integer idChildA = hrnChildA.getID();
3188 // at this point we know an edge in graph A exists
3189 // tdA -> idChildA, does this exist in B?
3190 assert td2vn.containsKey( tdA );
3191 VariableNode vnB = td2vn.get( tdA );
3192 RefEdge edgeToMerge = null;
3194 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3195 while( heapRegionsItrB.hasNext() &&
3196 edgeToMerge == null ) {
3198 RefEdge edgeB = heapRegionsItrB.next();
3199 HeapRegionNode hrnChildB = edgeB.getDst();
3200 Integer idChildB = hrnChildB.getID();
3202 // don't use the RefEdge.equals() here because
3203 // we're talking about existence between graphs
3204 if( idChildB.equals( idChildA ) &&
3205 edgeB.typeAndFieldEquals( edgeA ) ) {
3207 edgeToMerge = edgeB;
3211 // if the edge from A was not found in B,
3213 if( edgeToMerge == null ) {
3214 assert id2hrn.containsKey( idChildA );
3215 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3216 edgeToMerge = edgeA.copy();
3217 edgeToMerge.setSrc( vnB );
3218 edgeToMerge.setDst( hrnChildB );
3219 addRefEdge( vnB, hrnChildB, edgeToMerge );
3221 // otherwise, the edge already existed in both graphs
3222 // so merge their reachability sets
3224 // just replace this beta set with the union
3225 edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
3231 if( !edgeA.isClean() ) {
3232 edgeToMerge.setIsClean( false );
3240 protected void mergeAllocSites( ReachGraph rg ) {
3241 allocSites.addAll( rg.allocSites );
3245 // it is necessary in the equals() member functions
3246 // to "check both ways" when comparing the data
3247 // structures of two graphs. For instance, if all
3248 // edges between heap region nodes in graph A are
3249 // present and equal in graph B it is not sufficient
3250 // to say the graphs are equal. Consider that there
3251 // may be edges in graph B that are not in graph A.
3252 // the only way to know that all edges in both graphs
3253 // are equally present is to iterate over both data
3254 // structures and compare against the other graph.
3255 public boolean equals( ReachGraph rg ) {
3261 if( !areHeapRegionNodesEqual( rg ) ) {
3265 if( !areVariableNodesEqual( rg ) ) {
3269 if( !areRefEdgesEqual( rg ) ) {
3273 // if everything is equal up to this point,
3274 // assert that allocSites is also equal--
3275 // this data is redundant but kept for efficiency
3276 assert allocSites.equals( rg.allocSites );
3282 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3284 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3288 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3295 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3297 Set sA = rgA.id2hrn.entrySet();
3298 Iterator iA = sA.iterator();
3299 while( iA.hasNext() ) {
3300 Map.Entry meA = (Map.Entry) iA.next();
3301 Integer idA = (Integer) meA.getKey();
3302 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3304 if( !rgB.id2hrn.containsKey( idA ) ) {
3308 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3309 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3318 protected boolean areVariableNodesEqual( ReachGraph rg ) {
3320 if( !areallVNinAalsoinBandequal( this, rg ) ) {
3324 if( !areallVNinAalsoinBandequal( rg, this ) ) {
3331 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3333 Set sA = rgA.td2vn.entrySet();
3334 Iterator iA = sA.iterator();
3335 while( iA.hasNext() ) {
3336 Map.Entry meA = (Map.Entry) iA.next();
3337 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3339 if( !rgB.td2vn.containsKey( tdA ) ) {
3348 protected boolean areRefEdgesEqual( ReachGraph rg ) {
3349 if( !areallREinAandBequal( this, rg ) ) {
3356 static protected boolean areallREinAandBequal( ReachGraph rgA,
3359 // check all the heap region->heap region edges
3360 Set sA = rgA.id2hrn.entrySet();
3361 Iterator iA = sA.iterator();
3362 while( iA.hasNext() ) {
3363 Map.Entry meA = (Map.Entry) iA.next();
3364 Integer idA = (Integer) meA.getKey();
3365 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3367 // we should have already checked that the same
3368 // heap regions exist in both graphs
3369 assert rgB.id2hrn.containsKey( idA );
3371 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3375 // then check every edge in B for presence in A, starting
3376 // from the same parent HeapRegionNode
3377 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3379 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3384 // then check all the variable->heap region edges
3385 sA = rgA.td2vn.entrySet();
3387 while( iA.hasNext() ) {
3388 Map.Entry meA = (Map.Entry) iA.next();
3389 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3390 VariableNode vnA = (VariableNode) meA.getValue();
3392 // we should have already checked that the same
3393 // label nodes exist in both graphs
3394 assert rgB.td2vn.containsKey( tdA );
3396 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3400 // then check every edge in B for presence in A, starting
3401 // from the same parent VariableNode
3402 VariableNode vnB = rgB.td2vn.get( tdA );
3404 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3413 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3417 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3418 while( itrA.hasNext() ) {
3419 RefEdge edgeA = itrA.next();
3420 HeapRegionNode hrnChildA = edgeA.getDst();
3421 Integer idChildA = hrnChildA.getID();
3423 assert rgB.id2hrn.containsKey( idChildA );
3425 // at this point we know an edge in graph A exists
3426 // rnA -> idChildA, does this exact edge exist in B?
3427 boolean edgeFound = false;
3429 RefSrcNode rnB = null;
3430 if( rnA instanceof HeapRegionNode ) {
3431 HeapRegionNode hrnA = (HeapRegionNode) rnA;
3432 rnB = rgB.id2hrn.get( hrnA.getID() );
3434 VariableNode vnA = (VariableNode) rnA;
3435 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3438 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3439 while( itrB.hasNext() ) {
3440 RefEdge edgeB = itrB.next();
3441 HeapRegionNode hrnChildB = edgeB.getDst();
3442 Integer idChildB = hrnChildB.getID();
3444 if( idChildA.equals( idChildB ) &&
3445 edgeA.typeAndFieldEquals( edgeB ) ) {
3447 // there is an edge in the right place with the right field,
3448 // but do they have the same attributes?
3449 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3450 edgeA.equalsPreds( edgeB )
3467 // this analysis no longer has the "match anything"
3468 // type which was represented by null
3469 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3470 TypeDescriptor td2 ) {
3474 if( td1.isNull() ) {
3477 if( td2.isNull() ) {
3480 return typeUtil.mostSpecific( td1, td2 );
3483 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3485 TypeDescriptor td3 ) {
3487 return mostSpecificType( td1,
3488 mostSpecificType( td2, td3 )
3492 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3495 TypeDescriptor td4 ) {
3497 return mostSpecificType( mostSpecificType( td1, td2 ),
3498 mostSpecificType( td3, td4 )
3502 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3503 TypeDescriptor possibleChild ) {
3504 assert possibleSuper != null;
3505 assert possibleChild != null;
3507 if( possibleSuper.isNull() ||
3508 possibleChild.isNull() ) {
3512 return typeUtil.isSuperorType( possibleSuper, possibleChild );
3516 protected boolean hasMatchingField( HeapRegionNode src,
3519 TypeDescriptor tdSrc = src.getType();
3520 assert tdSrc != null;
3522 if( tdSrc.isArray() ) {
3523 TypeDescriptor td = edge.getType();
3526 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3527 assert tdSrcDeref != null;
3529 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3533 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3536 // if it's not a class, it doesn't have any fields to match
3537 if( !tdSrc.isClass() ) {
3541 ClassDescriptor cd = tdSrc.getClassDesc();
3542 while( cd != null ) {
3543 Iterator fieldItr = cd.getFields();
3545 while( fieldItr.hasNext() ) {
3546 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3548 if( fd.getType().equals( edge.getType() ) &&
3549 fd.getSymbol().equals( edge.getField() ) ) {
3554 cd = cd.getSuperDesc();
3557 // otherwise it is a class with fields
3558 // but we didn't find a match
3562 protected boolean hasMatchingType( RefEdge edge,
3563 HeapRegionNode dst ) {
3565 // if the region has no type, matches everything
3566 TypeDescriptor tdDst = dst.getType();
3567 assert tdDst != null;
3569 // if the type is not a class or an array, don't
3570 // match because primitives are copied, no aliases
3571 ClassDescriptor cdDst = tdDst.getClassDesc();
3572 if( cdDst == null && !tdDst.isArray() ) {
3576 // if the edge type is null, it matches everything
3577 TypeDescriptor tdEdge = edge.getType();
3578 assert tdEdge != null;
3580 return typeUtil.isSuperorType( tdEdge, tdDst );
3585 public void writeGraph( String graphName,
3586 boolean writeLabels,
3587 boolean labelSelect,
3588 boolean pruneGarbage,
3589 boolean writeReferencers,
3590 boolean hideSubsetReachability,
3591 boolean hideEdgeTaints
3592 ) throws java.io.IOException {
3593 writeGraph( graphName,
3598 hideSubsetReachability,
3603 public void writeGraph( String graphName,
3604 boolean writeLabels,
3605 boolean labelSelect,
3606 boolean pruneGarbage,
3607 boolean writeReferencers,
3608 boolean hideSubsetReachability,
3609 boolean hideEdgeTaints,
3610 Set<Integer> callerNodeIDsCopiedToCallee
3611 ) throws java.io.IOException {
3613 // remove all non-word characters from the graph name so
3614 // the filename and identifier in dot don't cause errors
3615 graphName = graphName.replaceAll( "[\\W]", "" );
3618 new BufferedWriter( new FileWriter( graphName+".dot" ) );
3620 bw.write( "digraph "+graphName+" {\n" );
3623 // this is an optional step to form the callee-reachable
3624 // "cut-out" into a DOT cluster for visualization
3625 if( callerNodeIDsCopiedToCallee != null ) {
3627 bw.write( " subgraph cluster0 {\n" );
3628 bw.write( " color=blue;\n" );
3630 Iterator i = id2hrn.entrySet().iterator();
3631 while( i.hasNext() ) {
3632 Map.Entry me = (Map.Entry) i.next();
3633 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3635 if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3636 bw.write( " "+hrn.toString()+
3637 hrn.toStringDOT( hideSubsetReachability )+
3647 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3649 // then visit every heap region node
3650 Iterator i = id2hrn.entrySet().iterator();
3651 while( i.hasNext() ) {
3652 Map.Entry me = (Map.Entry) i.next();
3653 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3655 // only visit nodes worth writing out--for instance
3656 // not every node at an allocation is referenced
3657 // (think of it as garbage-collected), etc.
3658 if( !pruneGarbage ||
3659 (hrn.isFlagged() && hrn.getID() > 0) ||
3660 hrn.getDescription().startsWith( "param" ) ||
3661 hrn.isOutOfContext()
3664 if( !visited.contains( hrn ) ) {
3665 traverseHeapRegionNodes( hrn,
3670 hideSubsetReachability,
3672 callerNodeIDsCopiedToCallee );
3677 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
3680 // then visit every label node, useful for debugging
3682 i = td2vn.entrySet().iterator();
3683 while( i.hasNext() ) {
3684 Map.Entry me = (Map.Entry) i.next();
3685 VariableNode vn = (VariableNode) me.getValue();
3688 String labelStr = vn.getTempDescriptorString();
3689 if( labelStr.startsWith("___temp") ||
3690 labelStr.startsWith("___dst") ||
3691 labelStr.startsWith("___srctmp") ||
3692 labelStr.startsWith("___neverused")
3698 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3699 while( heapRegionsItr.hasNext() ) {
3700 RefEdge edge = heapRegionsItr.next();
3701 HeapRegionNode hrn = edge.getDst();
3703 if( pruneGarbage && !visited.contains( hrn ) ) {
3704 traverseHeapRegionNodes( hrn,
3709 hideSubsetReachability,
3711 callerNodeIDsCopiedToCallee );
3714 bw.write( " "+vn.toString()+
3715 " -> "+hrn.toString()+
3716 edge.toStringDOT( hideSubsetReachability, "" )+
3726 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
3729 Set<HeapRegionNode> visited,
3730 boolean writeReferencers,
3731 boolean hideSubsetReachability,
3732 boolean hideEdgeTaints,
3733 Set<Integer> callerNodeIDsCopiedToCallee
3734 ) throws java.io.IOException {
3736 if( visited.contains( hrn ) ) {
3741 // if we're drawing the callee-view subgraph, only
3742 // write out the node info if it hasn't already been
3744 if( callerNodeIDsCopiedToCallee == null ||
3745 !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3747 bw.write( " "+hrn.toString()+
3748 hrn.toStringDOT( hideSubsetReachability )+
3752 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3753 while( childRegionsItr.hasNext() ) {
3754 RefEdge edge = childRegionsItr.next();
3755 HeapRegionNode hrnChild = edge.getDst();
3757 if( callerNodeIDsCopiedToCallee != null &&
3758 (edge.getSrc() instanceof HeapRegionNode) ) {
3759 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3760 if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
3761 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3763 bw.write( " "+hrn.toString()+
3764 " -> "+hrnChild.toString()+
3765 edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
3767 } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
3768 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3770 bw.write( " "+hrn.toString()+
3771 " -> "+hrnChild.toString()+
3772 edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
3775 bw.write( " "+hrn.toString()+
3776 " -> "+hrnChild.toString()+
3777 edge.toStringDOT( hideSubsetReachability, "" )+
3781 bw.write( " "+hrn.toString()+
3782 " -> "+hrnChild.toString()+
3783 edge.toStringDOT( hideSubsetReachability, "" )+
3787 traverseHeapRegionNodes( hrnChild,
3792 hideSubsetReachability,
3794 callerNodeIDsCopiedToCallee );