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 = true;
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 ) {}
2493 if( writeDebugDOTs ) {
2495 writeGraph( "caller90AfterTransfer",
2496 true, false, false, false, true, true );
2497 } catch( IOException e ) {}
2503 ////////////////////////////////////////////////////
2505 // Abstract garbage collection simply removes
2506 // heap region nodes that are not mechanically
2507 // reachable from a root set. This step is
2508 // essential for testing node and edge existence
2509 // predicates efficiently
2511 ////////////////////////////////////////////////////
2512 public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2514 // calculate a root set, will be different for Java
2515 // version of analysis versus Bamboo version
2516 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2518 // visit every variable in graph while building root
2519 // set, and do iterating on a copy, so we can remove
2520 // dead variables while we're at this
2521 Iterator makeCopyItr = td2vn.entrySet().iterator();
2522 Set entrysCopy = new HashSet();
2523 while( makeCopyItr.hasNext() ) {
2524 entrysCopy.add( makeCopyItr.next() );
2527 Iterator eItr = entrysCopy.iterator();
2528 while( eItr.hasNext() ) {
2529 Map.Entry me = (Map.Entry) eItr.next();
2530 TempDescriptor td = (TempDescriptor) me.getKey();
2531 VariableNode vn = (VariableNode) me.getValue();
2533 if( liveSet.contains( td ) ) {
2537 // dead var, remove completely from graph
2539 clearRefEdgesFrom( vn, null, null, true );
2543 // everything visited in a traversal is
2544 // considered abstractly live
2545 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2547 while( !toVisit.isEmpty() ) {
2548 RefSrcNode rsn = toVisit.iterator().next();
2549 toVisit.remove( rsn );
2552 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2553 while( hrnItr.hasNext() ) {
2554 RefEdge edge = hrnItr.next();
2555 HeapRegionNode hrn = edge.getDst();
2557 if( !visited.contains( hrn ) ) {
2563 // get a copy of the set to iterate over because
2564 // we're going to monkey with the graph when we
2565 // identify a garbage node
2566 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2567 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2568 while( hrnItr.hasNext() ) {
2569 hrnAllPrior.add( hrnItr.next() );
2572 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2573 while( hrnAllItr.hasNext() ) {
2574 HeapRegionNode hrn = hrnAllItr.next();
2576 if( !visited.contains( hrn ) ) {
2578 // heap region nodes are compared across ReachGraph
2579 // objects by their integer ID, so when discarding
2580 // garbage nodes we must also discard entries in
2581 // the ID -> heap region hashtable.
2582 id2hrn.remove( hrn.getID() );
2584 // RefEdge objects are two-way linked between
2585 // nodes, so when a node is identified as garbage,
2586 // actively clear references to and from it so
2587 // live nodes won't have dangling RefEdge's
2588 wipeOut( hrn, true );
2590 // if we just removed the last node from an allocation
2591 // site, it should be taken out of the ReachGraph's list
2592 AllocSite as = hrn.getAllocSite();
2593 if( !hasNodesOf( as ) ) {
2594 allocSites.remove( as );
2600 protected boolean hasNodesOf( AllocSite as ) {
2601 if( id2hrn.containsKey( as.getSummary() ) ) {
2605 for( int i = 0; i < allocationDepth; ++i ) {
2606 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2614 ////////////////////////////////////////////////////
2616 // This global sweep is an optional step to prune
2617 // reachability sets that are not internally
2618 // consistent with the global graph. It should be
2619 // invoked after strong updates or method calls.
2621 ////////////////////////////////////////////////////
2622 public void globalSweep() {
2624 // boldB is part of the phase 1 sweep
2625 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
2626 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2628 // visit every heap region to initialize alphaNew and calculate boldB
2629 Iterator itrHrns = id2hrn.entrySet().iterator();
2630 while( itrHrns.hasNext() ) {
2631 Map.Entry me = (Map.Entry) itrHrns.next();
2632 Integer hrnID = (Integer) me.getKey();
2633 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2635 // assert that this node and incoming edges have clean alphaNew
2636 // and betaNew sets, respectively
2637 assert rsetEmpty.equals( hrn.getAlphaNew() );
2639 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2640 while( itrRers.hasNext() ) {
2641 RefEdge edge = itrRers.next();
2642 assert rsetEmpty.equals( edge.getBetaNew() );
2645 // calculate boldB for this flagged node
2646 if( hrn.isFlagged() ) {
2648 Hashtable<RefEdge, ReachSet> boldB_f =
2649 new Hashtable<RefEdge, ReachSet>();
2651 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2653 // initial boldB_f constraints
2654 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2655 while( itrRees.hasNext() ) {
2656 RefEdge edge = itrRees.next();
2658 assert !boldB.containsKey( edge );
2659 boldB_f.put( edge, edge.getBeta() );
2661 assert !workSetEdges.contains( edge );
2662 workSetEdges.add( edge );
2665 // enforce the boldB_f constraint at edges until we reach a fixed point
2666 while( !workSetEdges.isEmpty() ) {
2667 RefEdge edge = workSetEdges.iterator().next();
2668 workSetEdges.remove( edge );
2670 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2671 while( itrPrime.hasNext() ) {
2672 RefEdge edgePrime = itrPrime.next();
2674 ReachSet prevResult = boldB_f.get( edgePrime );
2675 ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2679 if( prevResult == null ||
2680 Canonical.union( prevResult,
2681 intersection ).size() > prevResult.size() ) {
2683 if( prevResult == null ) {
2684 boldB_f.put( edgePrime,
2685 Canonical.union( edgePrime.getBeta(),
2690 boldB_f.put( edgePrime,
2691 Canonical.union( prevResult,
2696 workSetEdges.add( edgePrime );
2701 boldB.put( hrnID, boldB_f );
2706 // use boldB to prune hrnIDs from alpha states that are impossible
2707 // and propagate the differences backwards across edges
2708 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2710 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2711 new Hashtable<RefEdge, ChangeSet>();
2714 itrHrns = id2hrn.entrySet().iterator();
2715 while( itrHrns.hasNext() ) {
2716 Map.Entry me = (Map.Entry) itrHrns.next();
2717 Integer hrnID = (Integer) me.getKey();
2718 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2720 // create the inherent hrnID from a flagged region
2721 // as an exception to removal below
2722 ReachTuple rtException =
2723 ReachTuple.factory( hrnID,
2724 !hrn.isSingleObject(),
2725 ReachTuple.ARITY_ONE,
2726 false // out-of-context
2729 ChangeSet cts = ChangeSet.factory();
2731 // mark hrnIDs for removal
2732 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2733 while( stateItr.hasNext() ) {
2734 ReachState stateOld = stateItr.next();
2736 ReachState markedHrnIDs = ReachState.factory();
2738 Iterator<ReachTuple> rtItr = stateOld.iterator();
2739 while( rtItr.hasNext() ) {
2740 ReachTuple rtOld = rtItr.next();
2742 // never remove the inherent hrnID from a flagged region
2743 // because it is trivially satisfied
2744 if( hrn.isFlagged() ) {
2745 if( rtOld == rtException ) {
2750 // does boldB_ttOld allow this hrnID?
2751 boolean foundState = false;
2752 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2753 while( incidentEdgeItr.hasNext() ) {
2754 RefEdge incidentEdge = incidentEdgeItr.next();
2756 // if it isn't allowed, mark for removal
2757 Integer idOld = rtOld.getHrnID();
2758 assert id2hrn.containsKey( idOld );
2759 Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
2760 ReachSet boldB_ttOld_incident = B.get( incidentEdge );
2761 if( boldB_ttOld_incident != null &&
2762 boldB_ttOld_incident.contains( stateOld ) ) {
2768 markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
2772 // if there is nothing marked, just move on
2773 if( markedHrnIDs.isEmpty() ) {
2774 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2781 // remove all marked hrnIDs and establish a change set that should
2782 // propagate backwards over edges from this node
2783 ReachState statePruned = ReachState.factory();
2784 rtItr = stateOld.iterator();
2785 while( rtItr.hasNext() ) {
2786 ReachTuple rtOld = rtItr.next();
2788 if( !markedHrnIDs.containsTuple( rtOld ) ) {
2789 statePruned = Canonical.union( statePruned, rtOld );
2792 assert !stateOld.equals( statePruned );
2794 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2798 ChangeTuple ct = ChangeTuple.factory( stateOld,
2801 cts = Canonical.union( cts, ct );
2804 // throw change tuple set on all incident edges
2805 if( !cts.isEmpty() ) {
2806 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2807 while( incidentEdgeItr.hasNext() ) {
2808 RefEdge incidentEdge = incidentEdgeItr.next();
2810 edgesForPropagation.add( incidentEdge );
2812 if( edgePlannedChanges.get( incidentEdge ) == null ) {
2813 edgePlannedChanges.put( incidentEdge, cts );
2815 edgePlannedChanges.put(
2817 Canonical.union( edgePlannedChanges.get( incidentEdge ),
2826 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2828 propagateTokensOverEdges( edgesForPropagation,
2832 // at the end of the 1st phase reference edges have
2833 // beta, betaNew that correspond to beta and betaR
2835 // commit beta<-betaNew, so beta=betaR and betaNew
2836 // will represent the beta' calculation in 2nd phase
2838 // commit alpha<-alphaNew because it won't change
2839 HashSet<RefEdge> res = new HashSet<RefEdge>();
2841 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2842 while( nodeItr.hasNext() ) {
2843 HeapRegionNode hrn = nodeItr.next();
2844 hrn.applyAlphaNew();
2845 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
2846 while( itrRes.hasNext() ) {
2847 res.add( itrRes.next() );
2853 Iterator<RefEdge> edgeItr = res.iterator();
2854 while( edgeItr.hasNext() ) {
2855 RefEdge edge = edgeItr.next();
2856 HeapRegionNode hrn = edge.getDst();
2858 // commit results of last phase
2859 if( edgesUpdated.contains( edge ) ) {
2860 edge.applyBetaNew();
2863 // compute intial condition of 2nd phase
2864 edge.setBetaNew( Canonical.intersection( edge.getBeta(),
2870 // every edge in the graph is the initial workset
2871 Set<RefEdge> edgeWorkSet = (Set) res.clone();
2872 while( !edgeWorkSet.isEmpty() ) {
2873 RefEdge edgePrime = edgeWorkSet.iterator().next();
2874 edgeWorkSet.remove( edgePrime );
2876 RefSrcNode rsn = edgePrime.getSrc();
2877 if( !(rsn instanceof HeapRegionNode) ) {
2880 HeapRegionNode hrn = (HeapRegionNode) rsn;
2882 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
2883 while( itrEdge.hasNext() ) {
2884 RefEdge edge = itrEdge.next();
2886 ReachSet prevResult = edge.getBetaNew();
2887 assert prevResult != null;
2889 ReachSet intersection =
2890 Canonical.intersection( edge.getBeta(),
2891 edgePrime.getBetaNew()
2894 if( Canonical.union( prevResult,
2896 ).size() > prevResult.size() ) {
2898 Canonical.union( prevResult,
2902 edgeWorkSet.add( edge );
2907 // commit beta' (beta<-betaNew)
2908 edgeItr = res.iterator();
2909 while( edgeItr.hasNext() ) {
2910 edgeItr.next().applyBetaNew();
2916 ////////////////////////////////////////////////////
2917 // high-level merge operations
2918 ////////////////////////////////////////////////////
2919 public void merge_sameMethodContext( ReachGraph rg ) {
2920 // when merging two graphs that abstract the heap
2921 // of the same method context, we just call the
2922 // basic merge operation
2926 public void merge_diffMethodContext( ReachGraph rg ) {
2927 // when merging graphs for abstract heaps in
2928 // different method contexts we should:
2929 // 1) age the allocation sites?
2933 ////////////////////////////////////////////////////
2934 // in merge() and equals() methods the suffix A
2935 // represents the passed in graph and the suffix
2936 // B refers to the graph in this object
2937 // Merging means to take the incoming graph A and
2938 // merge it into B, so after the operation graph B
2939 // is the final result.
2940 ////////////////////////////////////////////////////
2941 protected void merge( ReachGraph rg ) {
2948 mergeRefEdges ( rg );
2949 mergeAllocSites( rg );
2952 protected void mergeNodes( ReachGraph rg ) {
2954 // start with heap region nodes
2955 Set sA = rg.id2hrn.entrySet();
2956 Iterator iA = sA.iterator();
2957 while( iA.hasNext() ) {
2958 Map.Entry meA = (Map.Entry) iA.next();
2959 Integer idA = (Integer) meA.getKey();
2960 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2962 // if this graph doesn't have a node the
2963 // incoming graph has, allocate it
2964 if( !id2hrn.containsKey( idA ) ) {
2965 HeapRegionNode hrnB = hrnA.copy();
2966 id2hrn.put( idA, hrnB );
2969 // otherwise this is a node present in both graphs
2970 // so make the new reachability set a union of the
2971 // nodes' reachability sets
2972 HeapRegionNode hrnB = id2hrn.get( idA );
2973 hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
2978 // if hrnB is already dirty or hrnA is dirty,
2979 // the hrnB should end up dirty: TODO
2981 if( !hrnA.isClean() ) {
2982 hrnB.setIsClean( false );
2988 // now add any variable nodes that are in graph B but
2990 sA = rg.td2vn.entrySet();
2992 while( iA.hasNext() ) {
2993 Map.Entry meA = (Map.Entry) iA.next();
2994 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2995 VariableNode lnA = (VariableNode) meA.getValue();
2997 // if the variable doesn't exist in B, allocate and add it
2998 VariableNode lnB = getVariableNodeFromTemp( tdA );
3002 protected void mergeRefEdges( ReachGraph rg ) {
3004 // between heap regions
3005 Set sA = rg.id2hrn.entrySet();
3006 Iterator iA = sA.iterator();
3007 while( iA.hasNext() ) {
3008 Map.Entry meA = (Map.Entry) iA.next();
3009 Integer idA = (Integer) meA.getKey();
3010 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3012 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3013 while( heapRegionsItrA.hasNext() ) {
3014 RefEdge edgeA = heapRegionsItrA.next();
3015 HeapRegionNode hrnChildA = edgeA.getDst();
3016 Integer idChildA = hrnChildA.getID();
3018 // at this point we know an edge in graph A exists
3019 // idA -> idChildA, does this exist in B?
3020 assert id2hrn.containsKey( idA );
3021 HeapRegionNode hrnB = id2hrn.get( idA );
3022 RefEdge edgeToMerge = null;
3024 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3025 while( heapRegionsItrB.hasNext() &&
3026 edgeToMerge == null ) {
3028 RefEdge edgeB = heapRegionsItrB.next();
3029 HeapRegionNode hrnChildB = edgeB.getDst();
3030 Integer idChildB = hrnChildB.getID();
3032 // don't use the RefEdge.equals() here because
3033 // we're talking about existence between graphs,
3034 // not intragraph equal
3035 if( idChildB.equals( idChildA ) &&
3036 edgeB.typeAndFieldEquals( edgeA ) ) {
3038 edgeToMerge = edgeB;
3042 // if the edge from A was not found in B,
3044 if( edgeToMerge == null ) {
3045 assert id2hrn.containsKey( idChildA );
3046 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3047 edgeToMerge = edgeA.copy();
3048 edgeToMerge.setSrc( hrnB );
3049 edgeToMerge.setDst( hrnChildB );
3050 addRefEdge( hrnB, hrnChildB, edgeToMerge );
3052 // otherwise, the edge already existed in both graphs
3053 // so merge their reachability sets
3055 // just replace this beta set with the union
3056 assert edgeToMerge != null;
3057 edgeToMerge.setBeta(
3058 Canonical.union( edgeToMerge.getBeta(),
3064 if( !edgeA.isClean() ) {
3065 edgeToMerge.setIsClean( false );
3072 // and then again from variable nodes
3073 sA = rg.td2vn.entrySet();
3075 while( iA.hasNext() ) {
3076 Map.Entry meA = (Map.Entry) iA.next();
3077 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3078 VariableNode vnA = (VariableNode) meA.getValue();
3080 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3081 while( heapRegionsItrA.hasNext() ) {
3082 RefEdge edgeA = heapRegionsItrA.next();
3083 HeapRegionNode hrnChildA = edgeA.getDst();
3084 Integer idChildA = hrnChildA.getID();
3086 // at this point we know an edge in graph A exists
3087 // tdA -> idChildA, does this exist in B?
3088 assert td2vn.containsKey( tdA );
3089 VariableNode vnB = td2vn.get( tdA );
3090 RefEdge edgeToMerge = null;
3092 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3093 while( heapRegionsItrB.hasNext() &&
3094 edgeToMerge == null ) {
3096 RefEdge edgeB = heapRegionsItrB.next();
3097 HeapRegionNode hrnChildB = edgeB.getDst();
3098 Integer idChildB = hrnChildB.getID();
3100 // don't use the RefEdge.equals() here because
3101 // we're talking about existence between graphs
3102 if( idChildB.equals( idChildA ) &&
3103 edgeB.typeAndFieldEquals( edgeA ) ) {
3105 edgeToMerge = edgeB;
3109 // if the edge from A was not found in B,
3111 if( edgeToMerge == null ) {
3112 assert id2hrn.containsKey( idChildA );
3113 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3114 edgeToMerge = edgeA.copy();
3115 edgeToMerge.setSrc( vnB );
3116 edgeToMerge.setDst( hrnChildB );
3117 addRefEdge( vnB, hrnChildB, edgeToMerge );
3119 // otherwise, the edge already existed in both graphs
3120 // so merge their reachability sets
3122 // just replace this beta set with the union
3123 edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
3129 if( !edgeA.isClean() ) {
3130 edgeToMerge.setIsClean( false );
3138 protected void mergeAllocSites( ReachGraph rg ) {
3139 allocSites.addAll( rg.allocSites );
3143 // it is necessary in the equals() member functions
3144 // to "check both ways" when comparing the data
3145 // structures of two graphs. For instance, if all
3146 // edges between heap region nodes in graph A are
3147 // present and equal in graph B it is not sufficient
3148 // to say the graphs are equal. Consider that there
3149 // may be edges in graph B that are not in graph A.
3150 // the only way to know that all edges in both graphs
3151 // are equally present is to iterate over both data
3152 // structures and compare against the other graph.
3153 public boolean equals( ReachGraph rg ) {
3159 if( !areHeapRegionNodesEqual( rg ) ) {
3163 if( !areVariableNodesEqual( rg ) ) {
3167 if( !areRefEdgesEqual( rg ) ) {
3171 // if everything is equal up to this point,
3172 // assert that allocSites is also equal--
3173 // this data is redundant but kept for efficiency
3174 assert allocSites.equals( rg.allocSites );
3180 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3182 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3186 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3193 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3195 Set sA = rgA.id2hrn.entrySet();
3196 Iterator iA = sA.iterator();
3197 while( iA.hasNext() ) {
3198 Map.Entry meA = (Map.Entry) iA.next();
3199 Integer idA = (Integer) meA.getKey();
3200 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3202 if( !rgB.id2hrn.containsKey( idA ) ) {
3206 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3207 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3216 protected boolean areVariableNodesEqual( ReachGraph rg ) {
3218 if( !areallVNinAalsoinBandequal( this, rg ) ) {
3222 if( !areallVNinAalsoinBandequal( rg, this ) ) {
3229 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3231 Set sA = rgA.td2vn.entrySet();
3232 Iterator iA = sA.iterator();
3233 while( iA.hasNext() ) {
3234 Map.Entry meA = (Map.Entry) iA.next();
3235 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3237 if( !rgB.td2vn.containsKey( tdA ) ) {
3246 protected boolean areRefEdgesEqual( ReachGraph rg ) {
3247 if( !areallREinAandBequal( this, rg ) ) {
3254 static protected boolean areallREinAandBequal( ReachGraph rgA,
3257 // check all the heap region->heap region edges
3258 Set sA = rgA.id2hrn.entrySet();
3259 Iterator iA = sA.iterator();
3260 while( iA.hasNext() ) {
3261 Map.Entry meA = (Map.Entry) iA.next();
3262 Integer idA = (Integer) meA.getKey();
3263 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3265 // we should have already checked that the same
3266 // heap regions exist in both graphs
3267 assert rgB.id2hrn.containsKey( idA );
3269 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3273 // then check every edge in B for presence in A, starting
3274 // from the same parent HeapRegionNode
3275 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3277 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3282 // then check all the variable->heap region edges
3283 sA = rgA.td2vn.entrySet();
3285 while( iA.hasNext() ) {
3286 Map.Entry meA = (Map.Entry) iA.next();
3287 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3288 VariableNode vnA = (VariableNode) meA.getValue();
3290 // we should have already checked that the same
3291 // label nodes exist in both graphs
3292 assert rgB.td2vn.containsKey( tdA );
3294 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3298 // then check every edge in B for presence in A, starting
3299 // from the same parent VariableNode
3300 VariableNode vnB = rgB.td2vn.get( tdA );
3302 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3311 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3315 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3316 while( itrA.hasNext() ) {
3317 RefEdge edgeA = itrA.next();
3318 HeapRegionNode hrnChildA = edgeA.getDst();
3319 Integer idChildA = hrnChildA.getID();
3321 assert rgB.id2hrn.containsKey( idChildA );
3323 // at this point we know an edge in graph A exists
3324 // rnA -> idChildA, does this exact edge exist in B?
3325 boolean edgeFound = false;
3327 RefSrcNode rnB = null;
3328 if( rnA instanceof HeapRegionNode ) {
3329 HeapRegionNode hrnA = (HeapRegionNode) rnA;
3330 rnB = rgB.id2hrn.get( hrnA.getID() );
3332 VariableNode vnA = (VariableNode) rnA;
3333 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3336 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3337 while( itrB.hasNext() ) {
3338 RefEdge edgeB = itrB.next();
3339 HeapRegionNode hrnChildB = edgeB.getDst();
3340 Integer idChildB = hrnChildB.getID();
3342 if( idChildA.equals( idChildB ) &&
3343 edgeA.typeAndFieldEquals( edgeB ) ) {
3345 // there is an edge in the right place with the right field,
3346 // but do they have the same attributes?
3347 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3348 edgeA.equalsPreds( edgeB )
3365 // this analysis no longer has the "match anything"
3366 // type which was represented by null
3367 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3368 TypeDescriptor td2 ) {
3372 if( td1.isNull() ) {
3375 if( td2.isNull() ) {
3378 return typeUtil.mostSpecific( td1, td2 );
3381 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3383 TypeDescriptor td3 ) {
3385 return mostSpecificType( td1,
3386 mostSpecificType( td2, td3 )
3390 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3393 TypeDescriptor td4 ) {
3395 return mostSpecificType( mostSpecificType( td1, td2 ),
3396 mostSpecificType( td3, td4 )
3400 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3401 TypeDescriptor possibleChild ) {
3402 assert possibleSuper != null;
3403 assert possibleChild != null;
3405 if( possibleSuper.isNull() ||
3406 possibleChild.isNull() ) {
3410 return typeUtil.isSuperorType( possibleSuper, possibleChild );
3414 protected boolean hasMatchingField( HeapRegionNode src,
3417 TypeDescriptor tdSrc = src.getType();
3418 assert tdSrc != null;
3420 if( tdSrc.isArray() ) {
3421 TypeDescriptor td = edge.getType();
3424 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3425 assert tdSrcDeref != null;
3427 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3431 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3434 // if it's not a class, it doesn't have any fields to match
3435 if( !tdSrc.isClass() ) {
3439 ClassDescriptor cd = tdSrc.getClassDesc();
3440 while( cd != null ) {
3441 Iterator fieldItr = cd.getFields();
3443 while( fieldItr.hasNext() ) {
3444 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3446 if( fd.getType().equals( edge.getType() ) &&
3447 fd.getSymbol().equals( edge.getField() ) ) {
3452 cd = cd.getSuperDesc();
3455 // otherwise it is a class with fields
3456 // but we didn't find a match
3460 protected boolean hasMatchingType( RefEdge edge,
3461 HeapRegionNode dst ) {
3463 // if the region has no type, matches everything
3464 TypeDescriptor tdDst = dst.getType();
3465 assert tdDst != null;
3467 // if the type is not a class or an array, don't
3468 // match because primitives are copied, no aliases
3469 ClassDescriptor cdDst = tdDst.getClassDesc();
3470 if( cdDst == null && !tdDst.isArray() ) {
3474 // if the edge type is null, it matches everything
3475 TypeDescriptor tdEdge = edge.getType();
3476 assert tdEdge != null;
3478 return typeUtil.isSuperorType( tdEdge, tdDst );
3483 public void writeGraph( String graphName,
3484 boolean writeLabels,
3485 boolean labelSelect,
3486 boolean pruneGarbage,
3487 boolean writeReferencers,
3488 boolean hideSubsetReachability,
3489 boolean hideEdgeTaints
3490 ) throws java.io.IOException {
3491 writeGraph( graphName,
3496 hideSubsetReachability,
3501 public void writeGraph( String graphName,
3502 boolean writeLabels,
3503 boolean labelSelect,
3504 boolean pruneGarbage,
3505 boolean writeReferencers,
3506 boolean hideSubsetReachability,
3507 boolean hideEdgeTaints,
3508 Set<Integer> callerNodeIDsCopiedToCallee
3509 ) throws java.io.IOException {
3511 // remove all non-word characters from the graph name so
3512 // the filename and identifier in dot don't cause errors
3513 graphName = graphName.replaceAll( "[\\W]", "" );
3516 new BufferedWriter( new FileWriter( graphName+".dot" ) );
3518 bw.write( "digraph "+graphName+" {\n" );
3521 // this is an optional step to form the callee-reachable
3522 // "cut-out" into a DOT cluster for visualization
3523 if( callerNodeIDsCopiedToCallee != null ) {
3525 bw.write( " subgraph cluster0 {\n" );
3526 bw.write( " color=blue;\n" );
3528 Iterator i = id2hrn.entrySet().iterator();
3529 while( i.hasNext() ) {
3530 Map.Entry me = (Map.Entry) i.next();
3531 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3533 if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3534 bw.write( " "+hrn.toString()+
3535 hrn.toStringDOT( hideSubsetReachability )+
3545 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3547 // then visit every heap region node
3548 Iterator i = id2hrn.entrySet().iterator();
3549 while( i.hasNext() ) {
3550 Map.Entry me = (Map.Entry) i.next();
3551 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3553 // only visit nodes worth writing out--for instance
3554 // not every node at an allocation is referenced
3555 // (think of it as garbage-collected), etc.
3556 if( !pruneGarbage ||
3557 (hrn.isFlagged() && hrn.getID() > 0) ||
3558 hrn.getDescription().startsWith( "param" ) ||
3559 hrn.isOutOfContext()
3562 if( !visited.contains( hrn ) ) {
3563 traverseHeapRegionNodes( hrn,
3568 hideSubsetReachability,
3570 callerNodeIDsCopiedToCallee );
3575 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
3578 // then visit every label node, useful for debugging
3580 i = td2vn.entrySet().iterator();
3581 while( i.hasNext() ) {
3582 Map.Entry me = (Map.Entry) i.next();
3583 VariableNode vn = (VariableNode) me.getValue();
3586 String labelStr = vn.getTempDescriptorString();
3587 if( labelStr.startsWith("___temp") ||
3588 labelStr.startsWith("___dst") ||
3589 labelStr.startsWith("___srctmp") ||
3590 labelStr.startsWith("___neverused")
3596 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3597 while( heapRegionsItr.hasNext() ) {
3598 RefEdge edge = heapRegionsItr.next();
3599 HeapRegionNode hrn = edge.getDst();
3601 if( pruneGarbage && !visited.contains( hrn ) ) {
3602 traverseHeapRegionNodes( hrn,
3607 hideSubsetReachability,
3609 callerNodeIDsCopiedToCallee );
3612 bw.write( " "+vn.toString()+
3613 " -> "+hrn.toString()+
3614 edge.toStringDOT( hideSubsetReachability, "" )+
3624 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
3627 Set<HeapRegionNode> visited,
3628 boolean writeReferencers,
3629 boolean hideSubsetReachability,
3630 boolean hideEdgeTaints,
3631 Set<Integer> callerNodeIDsCopiedToCallee
3632 ) throws java.io.IOException {
3634 if( visited.contains( hrn ) ) {
3639 // if we're drawing the callee-view subgraph, only
3640 // write out the node info if it hasn't already been
3642 if( callerNodeIDsCopiedToCallee == null ||
3643 !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3645 bw.write( " "+hrn.toString()+
3646 hrn.toStringDOT( hideSubsetReachability )+
3650 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3651 while( childRegionsItr.hasNext() ) {
3652 RefEdge edge = childRegionsItr.next();
3653 HeapRegionNode hrnChild = edge.getDst();
3655 if( callerNodeIDsCopiedToCallee != null &&
3656 (edge.getSrc() instanceof HeapRegionNode) ) {
3657 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3658 if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
3659 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3661 bw.write( " "+hrn.toString()+
3662 " -> "+hrnChild.toString()+
3663 edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
3665 } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
3666 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3668 bw.write( " "+hrn.toString()+
3669 " -> "+hrnChild.toString()+
3670 edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
3673 bw.write( " "+hrn.toString()+
3674 " -> "+hrnChild.toString()+
3675 edge.toStringDOT( hideSubsetReachability, "" )+
3679 bw.write( " "+hrn.toString()+
3680 " -> "+hrnChild.toString()+
3681 edge.toStringDOT( hideSubsetReachability, "" )+
3685 traverseHeapRegionNodes( hrnChild,
3690 hideSubsetReachability,
3692 callerNodeIDsCopiedToCallee );