1 package Analysis.Disjoint;
5 import Util.UtilAlgorithms;
9 public class ReachGraph {
11 // use to disable improvements for comparison
12 protected static final boolean DISABLE_STRONG_UPDATES = false;
13 protected static final boolean DISABLE_GLOBAL_SWEEP = false;
15 // a special out-of-scope temp
16 protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
18 // some frequently used reachability constants
19 protected static final ReachState rstateEmpty = ReachState.factory();
20 protected static final ReachSet rsetEmpty = ReachSet.factory();
21 protected static final ReachSet rsetWithEmptyState = ReachSet.factory( rstateEmpty );
23 // predicate constants
24 protected static final ExistPred predTrue = ExistPred.factory(); // if no args, true
25 protected static final ExistPredSet predsEmpty = ExistPredSet.factory();
26 protected static final ExistPredSet predsTrue = ExistPredSet.factory( predTrue );
29 // from DisjointAnalysis for convenience
30 protected static int allocationDepth = -1;
31 protected static TypeUtil typeUtil = null;
34 // variable and heap region nodes indexed by unique ID
35 public Hashtable<Integer, HeapRegionNode> id2hrn;
36 public Hashtable<TempDescriptor, VariableNode > td2vn;
38 // convenient set of alloc sites for all heap regions
39 // present in the graph without having to search
40 public HashSet<AllocSite> allocSites;
43 id2hrn = new Hashtable<Integer, HeapRegionNode>();
44 td2vn = new Hashtable<TempDescriptor, VariableNode >();
45 allocSites = new HashSet<AllocSite>();
49 // temp descriptors are globally unique and map to
50 // exactly one variable node, easy
51 protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
54 if( !td2vn.containsKey( td ) ) {
55 td2vn.put( td, new VariableNode( td ) );
58 return td2vn.get( td );
61 public boolean hasVariable( TempDescriptor td ) {
62 return td2vn.containsKey( td );
66 // this suite of methods can be used to assert a
67 // very important property of ReachGraph objects:
68 // some element, HeapRegionNode, RefEdge etc.
69 // should be referenced by at most ONE ReachGraph!!
70 // If a heap region or edge or variable should be
71 // in another graph, make a new object with
72 // equivalent properties for a new graph
73 public boolean belongsToThis( RefSrcNode rsn ) {
74 if( rsn instanceof VariableNode ) {
75 VariableNode vn = (VariableNode) rsn;
76 return this.td2vn.get( vn.getTempDescriptor() ) == vn;
78 HeapRegionNode hrn = (HeapRegionNode) rsn;
79 return this.id2hrn.get( hrn.getID() ) == hrn;
86 // the reason for this method is to have the option
87 // of creating new heap regions with specific IDs, or
88 // duplicating heap regions with specific IDs (especially
89 // in the merge() operation) or to create new heap
90 // regions with a new unique ID
91 protected HeapRegionNode
92 createNewHeapRegionNode( Integer id,
93 boolean isSingleObject,
96 boolean isOutOfContext,
105 boolean markForAnalysis = isFlagged;
107 TypeDescriptor typeToUse = null;
108 if( allocSite != null ) {
109 typeToUse = allocSite.getType();
110 allocSites.add( allocSite );
115 if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
116 markForAnalysis = true;
120 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
123 if( inherent == null ) {
124 if( markForAnalysis ) {
126 Canonical.makePredsTrue(
129 ReachTuple.factory( id,
131 ReachTuple.ARITY_ONE,
132 false // out-of-context
138 inherent = rsetWithEmptyState;
142 if( alpha == null ) {
146 assert preds != null;
148 HeapRegionNode hrn = new HeapRegionNode( id,
159 id2hrn.put( id, hrn );
165 ////////////////////////////////////////////////
167 // Low-level referencee and referencer methods
169 // These methods provide the lowest level for
170 // creating references between reachability nodes
171 // and handling the details of maintaining both
172 // list of referencers and referencees.
174 ////////////////////////////////////////////////
175 protected void addRefEdge( RefSrcNode referencer,
176 HeapRegionNode referencee,
178 assert referencer != null;
179 assert referencee != null;
181 assert edge.getSrc() == referencer;
182 assert edge.getDst() == referencee;
183 assert belongsToThis( referencer );
184 assert belongsToThis( referencee );
186 // edges are getting added twice to graphs now, the
187 // kind that should have abstract facts merged--use
188 // this check to prevent that
189 assert referencer.getReferenceTo( referencee,
194 referencer.addReferencee( edge );
195 referencee.addReferencer( edge );
198 protected void removeRefEdge( RefEdge e ) {
199 removeRefEdge( e.getSrc(),
205 protected void removeRefEdge( RefSrcNode referencer,
206 HeapRegionNode referencee,
209 assert referencer != null;
210 assert referencee != null;
212 RefEdge edge = referencer.getReferenceTo( referencee,
216 assert edge == referencee.getReferenceFrom( referencer,
220 referencer.removeReferencee( edge );
221 referencee.removeReferencer( edge );
224 protected void clearRefEdgesFrom( RefSrcNode referencer,
227 boolean removeAll ) {
228 assert referencer != null;
230 // get a copy of the set to iterate over, otherwise
231 // we will be trying to take apart the set as we
232 // are iterating over it, which won't work
233 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
234 while( i.hasNext() ) {
235 RefEdge edge = i.next();
238 (edge.typeEquals( type ) && edge.fieldEquals( field ))
241 HeapRegionNode referencee = edge.getDst();
243 removeRefEdge( referencer,
251 protected void clearRefEdgesTo( HeapRegionNode referencee,
254 boolean removeAll ) {
255 assert referencee != null;
257 // get a copy of the set to iterate over, otherwise
258 // we will be trying to take apart the set as we
259 // are iterating over it, which won't work
260 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
261 while( i.hasNext() ) {
262 RefEdge edge = i.next();
265 (edge.typeEquals( type ) && edge.fieldEquals( field ))
268 RefSrcNode referencer = edge.getSrc();
270 removeRefEdge( referencer,
278 protected void clearNonVarRefEdgesTo( HeapRegionNode referencee ) {
279 assert referencee != null;
281 // get a copy of the set to iterate over, otherwise
282 // we will be trying to take apart the set as we
283 // are iterating over it, which won't work
284 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
285 while( i.hasNext() ) {
286 RefEdge edge = i.next();
287 RefSrcNode referencer = edge.getSrc();
288 if( !(referencer instanceof VariableNode) ) {
289 removeRefEdge( referencer,
297 // this is a common operation in many transfer functions: we want
298 // to add an edge, but if there is already such an edge we should
299 // merge the properties of the existing and the new edges
300 protected void addEdgeOrMergeWithExisting( RefEdge edgeNew ) {
302 RefSrcNode src = edgeNew.getSrc();
303 assert belongsToThis( src );
305 HeapRegionNode dst = edgeNew.getDst();
306 assert belongsToThis( dst );
308 // look to see if an edge with same field exists
309 // and merge with it, otherwise just add the edge
310 RefEdge edgeExisting = src.getReferenceTo( dst,
315 if( edgeExisting != null ) {
316 edgeExisting.setBeta(
317 Canonical.unionORpreds( edgeExisting.getBeta(),
321 edgeExisting.setPreds(
322 Canonical.join( edgeExisting.getPreds(),
328 addRefEdge( src, dst, edgeNew );
334 ////////////////////////////////////////////////////
336 // Assignment Operation Methods
338 // These methods are high-level operations for
339 // modeling program assignment statements using
340 // the low-level reference create/remove methods
343 ////////////////////////////////////////////////////
345 public void assignTempXEqualToTempY( TempDescriptor x,
347 assignTempXEqualToCastedTempY( x, y, null );
350 public void assignTempXEqualToCastedTempY( TempDescriptor x,
352 TypeDescriptor tdCast ) {
354 VariableNode lnX = getVariableNodeFromTemp( x );
355 VariableNode lnY = getVariableNodeFromTemp( y );
357 clearRefEdgesFrom( lnX, null, null, true );
359 // note it is possible that the types of temps in the
360 // flat node to analyze will reveal that some typed
361 // edges in the reachability graph are impossible
362 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
364 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
365 while( itrYhrn.hasNext() ) {
366 RefEdge edgeY = itrYhrn.next();
367 HeapRegionNode referencee = edgeY.getDst();
368 RefEdge edgeNew = edgeY.copy();
370 if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
371 impossibleEdges.add( edgeY );
375 edgeNew.setSrc( lnX );
377 if( tdCast == null ) {
378 edgeNew.setType( mostSpecificType( y.getType(),
384 edgeNew.setType( mostSpecificType( y.getType(),
386 referencee.getType(),
392 edgeNew.setField( null );
394 addRefEdge( lnX, referencee, edgeNew );
397 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
398 while( itrImp.hasNext() ) {
399 RefEdge edgeImp = itrImp.next();
400 removeRefEdge( edgeImp );
405 public void assignTempXEqualToTempYFieldF( TempDescriptor x,
407 FieldDescriptor f ) {
408 VariableNode lnX = getVariableNodeFromTemp( x );
409 VariableNode lnY = getVariableNodeFromTemp( y );
411 clearRefEdgesFrom( lnX, null, null, true );
413 // note it is possible that the types of temps in the
414 // flat node to analyze will reveal that some typed
415 // edges in the reachability graph are impossible
416 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
418 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
419 while( itrYhrn.hasNext() ) {
420 RefEdge edgeY = itrYhrn.next();
421 HeapRegionNode hrnY = edgeY.getDst();
422 ReachSet betaY = edgeY.getBeta();
424 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
425 while( itrHrnFhrn.hasNext() ) {
426 RefEdge edgeHrn = itrHrnFhrn.next();
427 HeapRegionNode hrnHrn = edgeHrn.getDst();
428 ReachSet betaHrn = edgeHrn.getBeta();
430 // prune edges that are not a matching field
431 if( edgeHrn.getType() != null &&
432 !edgeHrn.getField().equals( f.getSymbol() )
437 // check for impossible edges
438 if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
439 impossibleEdges.add( edgeHrn );
443 TypeDescriptor tdNewEdge =
444 mostSpecificType( edgeHrn.getType(),
448 RefEdge edgeNew = new RefEdge( lnX,
452 Canonical.intersection( betaY, betaHrn ),
456 addEdgeOrMergeWithExisting( edgeNew );
460 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
461 while( itrImp.hasNext() ) {
462 RefEdge edgeImp = itrImp.next();
463 removeRefEdge( edgeImp );
466 // anytime you might remove edges between heap regions
467 // you must global sweep to clean up broken reachability
468 if( !impossibleEdges.isEmpty() ) {
469 if( !DISABLE_GLOBAL_SWEEP ) {
476 public void assignTempXFieldFEqualToTempY( TempDescriptor x,
480 VariableNode lnX = getVariableNodeFromTemp( x );
481 VariableNode lnY = getVariableNodeFromTemp( y );
483 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
484 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
486 // note it is possible that the types of temps in the
487 // flat node to analyze will reveal that some typed
488 // edges in the reachability graph are impossible
489 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
491 // first look for possible strong updates and remove those edges
492 boolean strongUpdate = false;
494 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
495 while( itrXhrn.hasNext() ) {
496 RefEdge edgeX = itrXhrn.next();
497 HeapRegionNode hrnX = edgeX.getDst();
499 // we can do a strong update here if one of two cases holds
501 f != DisjointAnalysis.getArrayField( f.getType() ) &&
502 ( (hrnX.getNumReferencers() == 1) || // case 1
503 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
506 if( !DISABLE_STRONG_UPDATES ) {
508 clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
513 // then do all token propagation
514 itrXhrn = lnX.iteratorToReferencees();
515 while( itrXhrn.hasNext() ) {
516 RefEdge edgeX = itrXhrn.next();
517 HeapRegionNode hrnX = edgeX.getDst();
518 ReachSet betaX = edgeX.getBeta();
519 ReachSet R = Canonical.intersection( hrnX.getAlpha(),
523 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
524 while( itrYhrn.hasNext() ) {
525 RefEdge edgeY = itrYhrn.next();
526 HeapRegionNode hrnY = edgeY.getDst();
527 ReachSet O = edgeY.getBeta();
529 // check for impossible edges
530 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
531 impossibleEdges.add( edgeY );
535 // propagate tokens over nodes starting from hrnSrc, and it will
536 // take care of propagating back up edges from any touched nodes
537 ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
538 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
540 // then propagate back just up the edges from hrn
541 ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
542 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
544 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
545 new Hashtable<RefEdge, ChangeSet>();
547 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
548 while( referItr.hasNext() ) {
549 RefEdge edgeUpstream = referItr.next();
550 todoEdges.add( edgeUpstream );
551 edgePlannedChanges.put( edgeUpstream, Cx );
554 propagateTokensOverEdges( todoEdges,
561 // apply the updates to reachability
562 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
563 while( nodeItr.hasNext() ) {
564 nodeItr.next().applyAlphaNew();
567 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
568 while( edgeItr.hasNext() ) {
569 edgeItr.next().applyBetaNew();
573 // then go back through and add the new edges
574 itrXhrn = lnX.iteratorToReferencees();
575 while( itrXhrn.hasNext() ) {
576 RefEdge edgeX = itrXhrn.next();
577 HeapRegionNode hrnX = edgeX.getDst();
579 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
580 while( itrYhrn.hasNext() ) {
581 RefEdge edgeY = itrYhrn.next();
582 HeapRegionNode hrnY = edgeY.getDst();
584 // skip impossible edges here, we already marked them
585 // when computing reachability propagations above
586 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
590 // prepare the new reference edge hrnX.f -> hrnY
591 TypeDescriptor tdNewEdge =
592 mostSpecificType( y.getType(),
602 Canonical.makePredsTrue(
603 Canonical.pruneBy( edgeY.getBeta(),
610 addEdgeOrMergeWithExisting( edgeNew );
614 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
615 while( itrImp.hasNext() ) {
616 RefEdge edgeImp = itrImp.next();
617 removeRefEdge( edgeImp );
620 // if there was a strong update, make sure to improve
621 // reachability with a global sweep
622 if( strongUpdate || !impossibleEdges.isEmpty() ) {
623 if( !DISABLE_GLOBAL_SWEEP ) {
630 public void assignReturnEqualToTemp( TempDescriptor x ) {
632 VariableNode lnR = getVariableNodeFromTemp( tdReturn );
633 VariableNode lnX = getVariableNodeFromTemp( x );
635 clearRefEdgesFrom( lnR, null, null, true );
637 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
638 while( itrXhrn.hasNext() ) {
639 RefEdge edgeX = itrXhrn.next();
640 HeapRegionNode referencee = edgeX.getDst();
641 RefEdge edgeNew = edgeX.copy();
642 edgeNew.setSrc( lnR );
644 addRefEdge( lnR, referencee, edgeNew );
649 public void assignTempEqualToNewAlloc( TempDescriptor x,
656 // after the age operation the newest (or zero-ith oldest)
657 // node associated with the allocation site should have
658 // no references to it as if it were a newly allocated
660 Integer idNewest = as.getIthOldest( 0 );
661 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
662 assert hrnNewest != null;
664 VariableNode lnX = getVariableNodeFromTemp( x );
665 clearRefEdgesFrom( lnX, null, null, true );
667 // make a new reference to allocated node
668 TypeDescriptor type = as.getType();
671 new RefEdge( lnX, // source
675 hrnNewest.getAlpha(), // beta
676 predsTrue // predicates
679 addRefEdge( lnX, hrnNewest, edgeNew );
683 // use the allocation site (unique to entire analysis) to
684 // locate the heap region nodes in this reachability graph
685 // that should be aged. The process models the allocation
686 // of new objects and collects all the oldest allocations
687 // in a summary node to allow for a finite analysis
689 // There is an additional property of this method. After
690 // running it on a particular reachability graph (many graphs
691 // may have heap regions related to the same allocation site)
692 // the heap region node objects in this reachability graph will be
693 // allocated. Therefore, after aging a graph for an allocation
694 // site, attempts to retrieve the heap region nodes using the
695 // integer id's contained in the allocation site should always
696 // return non-null heap regions.
697 public void age( AllocSite as ) {
699 // keep track of allocation sites that are represented
700 // in this graph for efficiency with other operations
701 allocSites.add( as );
703 // if there is a k-th oldest node, it merges into
705 Integer idK = as.getOldest();
706 if( id2hrn.containsKey( idK ) ) {
707 HeapRegionNode hrnK = id2hrn.get( idK );
709 // retrieve the summary node, or make it
711 HeapRegionNode hrnSummary = getSummaryNode( as, false );
713 mergeIntoSummary( hrnK, hrnSummary );
716 // move down the line of heap region nodes
717 // clobbering the ith and transferring all references
718 // to and from i-1 to node i.
719 for( int i = allocationDepth - 1; i > 0; --i ) {
721 // only do the transfer if the i-1 node exists
722 Integer idImin1th = as.getIthOldest( i - 1 );
723 if( id2hrn.containsKey( idImin1th ) ) {
724 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
725 if( hrnImin1.isWiped() ) {
726 // there is no info on this node, just skip
730 // either retrieve or make target of transfer
731 HeapRegionNode hrnI = getIthNode( as, i, false );
733 transferOnto( hrnImin1, hrnI );
738 // as stated above, the newest node should have had its
739 // references moved over to the second oldest, so we wipe newest
740 // in preparation for being the new object to assign something to
741 HeapRegionNode hrn0 = getIthNode( as, 0, false );
742 wipeOut( hrn0, true );
744 // now tokens in reachability sets need to "age" also
745 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
746 while( itrAllVariableNodes.hasNext() ) {
747 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
748 VariableNode ln = (VariableNode) me.getValue();
750 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
751 while( itrEdges.hasNext() ) {
752 ageTuplesFrom( as, itrEdges.next() );
756 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
757 while( itrAllHRNodes.hasNext() ) {
758 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
759 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
761 ageTuplesFrom( as, hrnToAge );
763 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
764 while( itrEdges.hasNext() ) {
765 ageTuplesFrom( as, itrEdges.next() );
770 // after tokens have been aged, reset newest node's reachability
771 // and a brand new node has a "true" predicate
772 hrn0.setAlpha( hrn0.getInherent() );
773 hrn0.setPreds( predsTrue );
777 // either retrieve or create the needed heap region node
778 protected HeapRegionNode getSummaryNode( AllocSite as,
783 idSummary = as.getSummaryShadow();
785 idSummary = as.getSummary();
788 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
790 if( hrnSummary == null ) {
792 boolean hasFlags = false;
793 if( as.getType().isClass() ) {
794 hasFlags = as.getType().getClassDesc().hasFlags();
798 hasFlags = as.getFlag();
801 String strDesc = as.toStringForDOT()+"\\nsummary";
804 createNewHeapRegionNode( idSummary, // id or null to generate a new one
805 false, // single object?
807 hasFlags, // flagged?
808 false, // out-of-context?
809 as.getType(), // type
810 as, // allocation site
811 null, // inherent reach
812 null, // current reach
813 predsEmpty, // predicates
814 strDesc // description
821 // either retrieve or create the needed heap region node
822 protected HeapRegionNode getIthNode( AllocSite as,
828 idIth = as.getIthOldestShadow( i );
830 idIth = as.getIthOldest( i );
833 HeapRegionNode hrnIth = id2hrn.get( idIth );
835 if( hrnIth == null ) {
837 boolean hasFlags = false;
838 if( as.getType().isClass() ) {
839 hasFlags = as.getType().getClassDesc().hasFlags();
843 hasFlags = as.getFlag();
846 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
848 hrnIth = createNewHeapRegionNode( idIth, // id or null to generate a new one
849 true, // single object?
851 hasFlags, // flagged?
852 false, // out-of-context?
853 as.getType(), // type
854 as, // allocation site
855 null, // inherent reach
856 null, // current reach
857 predsEmpty, // predicates
858 strDesc // description
866 protected void mergeIntoSummary( HeapRegionNode hrn,
867 HeapRegionNode hrnSummary ) {
868 assert hrnSummary.isNewSummary();
870 // assert that these nodes belong to THIS graph
871 assert belongsToThis( hrn );
872 assert belongsToThis( hrnSummary );
874 assert hrn != hrnSummary;
876 // transfer references _from_ hrn over to hrnSummary
877 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
878 while( itrReferencee.hasNext() ) {
879 RefEdge edge = itrReferencee.next();
880 RefEdge edgeMerged = edge.copy();
881 edgeMerged.setSrc( hrnSummary );
883 HeapRegionNode hrnReferencee = edge.getDst();
884 RefEdge edgeSummary =
885 hrnSummary.getReferenceTo( hrnReferencee,
890 if( edgeSummary == null ) {
891 // the merge is trivial, nothing to be done
892 addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
895 // otherwise an edge from the referencer to hrnSummary exists already
896 // and the edge referencer->hrn should be merged with it
898 Canonical.unionORpreds( edgeMerged.getBeta(),
899 edgeSummary.getBeta()
902 edgeSummary.setPreds(
903 Canonical.join( edgeMerged.getPreds(),
904 edgeSummary.getPreds()
910 // next transfer references _to_ hrn over to hrnSummary
911 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
912 while( itrReferencer.hasNext() ) {
913 RefEdge edge = itrReferencer.next();
914 RefEdge edgeMerged = edge.copy();
915 edgeMerged.setDst( hrnSummary );
917 RefSrcNode onReferencer = edge.getSrc();
918 RefEdge edgeSummary =
919 onReferencer.getReferenceTo( hrnSummary,
924 if( edgeSummary == null ) {
925 // the merge is trivial, nothing to be done
926 addRefEdge( onReferencer, hrnSummary, edgeMerged );
929 // otherwise an edge from the referencer to alpha_S exists already
930 // and the edge referencer->alpha_K should be merged with it
932 Canonical.unionORpreds( edgeMerged.getBeta(),
933 edgeSummary.getBeta()
936 edgeSummary.setPreds(
937 Canonical.join( edgeMerged.getPreds(),
938 edgeSummary.getPreds()
944 // then merge hrn reachability into hrnSummary
946 Canonical.unionORpreds( hrnSummary.getAlpha(),
952 Canonical.join( hrnSummary.getPreds(),
957 // and afterward, this node is gone
958 wipeOut( hrn, true );
962 protected void transferOnto( HeapRegionNode hrnA,
963 HeapRegionNode hrnB ) {
965 assert belongsToThis( hrnA );
966 assert belongsToThis( hrnB );
969 // clear references in and out of node b?
970 assert hrnB.isWiped();
972 // copy each: (edge in and out of A) to B
973 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
974 while( itrReferencee.hasNext() ) {
975 RefEdge edge = itrReferencee.next();
976 HeapRegionNode hrnReferencee = edge.getDst();
977 RefEdge edgeNew = edge.copy();
978 edgeNew.setSrc( hrnB );
979 edgeNew.setDst( hrnReferencee );
981 addRefEdge( hrnB, hrnReferencee, edgeNew );
984 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
985 while( itrReferencer.hasNext() ) {
986 RefEdge edge = itrReferencer.next();
987 RefSrcNode rsnReferencer = edge.getSrc();
988 RefEdge edgeNew = edge.copy();
989 edgeNew.setSrc( rsnReferencer );
990 edgeNew.setDst( hrnB );
992 addRefEdge( rsnReferencer, hrnB, edgeNew );
995 // replace hrnB reachability and preds with hrnA's
996 hrnB.setAlpha( hrnA.getAlpha() );
997 hrnB.setPreds( hrnA.getPreds() );
999 // after transfer, wipe out source
1000 wipeOut( hrnA, true );
1004 // the purpose of this method is to conceptually "wipe out"
1005 // a heap region from the graph--purposefully not called REMOVE
1006 // because the node is still hanging around in the graph, just
1007 // not mechanically connected or have any reach or predicate
1008 // information on it anymore--lots of ops can use this
1009 protected void wipeOut( HeapRegionNode hrn,
1010 boolean wipeVariableReferences ) {
1012 assert belongsToThis( hrn );
1014 clearRefEdgesFrom( hrn, null, null, true );
1016 if( wipeVariableReferences ) {
1017 clearRefEdgesTo( hrn, null, null, true );
1019 clearNonVarRefEdgesTo( hrn );
1022 hrn.setAlpha( rsetEmpty );
1023 hrn.setPreds( predsEmpty );
1027 protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
1029 Canonical.ageTuplesFrom( edge.getBeta(),
1035 protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
1037 Canonical.ageTuplesFrom( hrn.getAlpha(),
1045 protected void propagateTokensOverNodes( HeapRegionNode nPrime,
1047 HashSet<HeapRegionNode> nodesWithNewAlpha,
1048 HashSet<RefEdge> edgesWithNewBeta ) {
1050 HashSet<HeapRegionNode> todoNodes
1051 = new HashSet<HeapRegionNode>();
1052 todoNodes.add( nPrime );
1054 HashSet<RefEdge> todoEdges
1055 = new HashSet<RefEdge>();
1057 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1058 = new Hashtable<HeapRegionNode, ChangeSet>();
1059 nodePlannedChanges.put( nPrime, c0 );
1061 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1062 = new Hashtable<RefEdge, ChangeSet>();
1064 // first propagate change sets everywhere they can go
1065 while( !todoNodes.isEmpty() ) {
1066 HeapRegionNode n = todoNodes.iterator().next();
1067 ChangeSet C = nodePlannedChanges.get( n );
1069 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1070 while( referItr.hasNext() ) {
1071 RefEdge edge = referItr.next();
1072 todoEdges.add( edge );
1074 if( !edgePlannedChanges.containsKey( edge ) ) {
1075 edgePlannedChanges.put( edge,
1080 edgePlannedChanges.put( edge,
1081 Canonical.union( edgePlannedChanges.get( edge ),
1087 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1088 while( refeeItr.hasNext() ) {
1089 RefEdge edgeF = refeeItr.next();
1090 HeapRegionNode m = edgeF.getDst();
1092 ChangeSet changesToPass = ChangeSet.factory();
1094 Iterator<ChangeTuple> itrCprime = C.iterator();
1095 while( itrCprime.hasNext() ) {
1096 ChangeTuple c = itrCprime.next();
1097 if( edgeF.getBeta().containsIgnorePreds( c.getStateToMatch() )
1100 changesToPass = Canonical.add( changesToPass, c );
1104 if( !changesToPass.isEmpty() ) {
1105 if( !nodePlannedChanges.containsKey( m ) ) {
1106 nodePlannedChanges.put( m, ChangeSet.factory() );
1109 ChangeSet currentChanges = nodePlannedChanges.get( m );
1111 if( !changesToPass.isSubset( currentChanges ) ) {
1113 nodePlannedChanges.put( m,
1114 Canonical.union( currentChanges,
1123 todoNodes.remove( n );
1126 // then apply all of the changes for each node at once
1127 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1128 while( itrMap.hasNext() ) {
1129 Map.Entry me = (Map.Entry) itrMap.next();
1130 HeapRegionNode n = (HeapRegionNode) me.getKey();
1131 ChangeSet C = (ChangeSet) me.getValue();
1133 // this propagation step is with respect to one change,
1134 // so we capture the full change from the old alpha:
1135 ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1139 // but this propagation may be only one of many concurrent
1140 // possible changes, so keep a running union with the node's
1141 // partially updated new alpha set
1142 n.setAlphaNew( Canonical.unionORpreds( n.getAlphaNew(),
1147 nodesWithNewAlpha.add( n );
1150 propagateTokensOverEdges( todoEdges,
1157 protected void propagateTokensOverEdges( HashSet <RefEdge> todoEdges,
1158 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1159 HashSet <RefEdge> edgesWithNewBeta ) {
1161 // first propagate all change tuples everywhere they can go
1162 while( !todoEdges.isEmpty() ) {
1163 RefEdge edgeE = todoEdges.iterator().next();
1164 todoEdges.remove( edgeE );
1166 if( !edgePlannedChanges.containsKey( edgeE ) ) {
1167 edgePlannedChanges.put( edgeE,
1172 ChangeSet C = edgePlannedChanges.get( edgeE );
1174 ChangeSet changesToPass = ChangeSet.factory();
1176 Iterator<ChangeTuple> itrC = C.iterator();
1177 while( itrC.hasNext() ) {
1178 ChangeTuple c = itrC.next();
1179 if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
1182 changesToPass = Canonical.add( changesToPass, c );
1186 RefSrcNode rsn = edgeE.getSrc();
1188 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1189 HeapRegionNode n = (HeapRegionNode) rsn;
1191 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1192 while( referItr.hasNext() ) {
1193 RefEdge edgeF = referItr.next();
1195 if( !edgePlannedChanges.containsKey( edgeF ) ) {
1196 edgePlannedChanges.put( edgeF,
1201 ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1203 if( !changesToPass.isSubset( currentChanges ) ) {
1204 todoEdges.add( edgeF );
1205 edgePlannedChanges.put( edgeF,
1206 Canonical.union( currentChanges,
1215 // then apply all of the changes for each edge at once
1216 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1217 while( itrMap.hasNext() ) {
1218 Map.Entry me = (Map.Entry) itrMap.next();
1219 RefEdge e = (RefEdge) me.getKey();
1220 ChangeSet C = (ChangeSet) me.getValue();
1222 // this propagation step is with respect to one change,
1223 // so we capture the full change from the old beta:
1224 ReachSet localDelta =
1225 Canonical.applyChangeSet( e.getBeta(),
1230 // but this propagation may be only one of many concurrent
1231 // possible changes, so keep a running union with the edge's
1232 // partially updated new beta set
1233 e.setBetaNew( Canonical.unionORpreds( e.getBetaNew(),
1238 edgesWithNewBeta.add( e );
1243 // used in makeCalleeView below to decide if there is
1244 // already an appropriate out-of-context edge in a callee
1245 // view graph for merging, or null if a new one will be added
1247 getOutOfContextReferenceTo( HeapRegionNode hrn,
1248 TypeDescriptor srcType,
1249 TypeDescriptor refType,
1251 assert belongsToThis( hrn );
1253 HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1254 if( hrnInContext == null ) {
1258 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1259 while( refItr.hasNext() ) {
1260 RefEdge re = refItr.next();
1262 assert belongsToThis( re.getSrc() );
1263 assert belongsToThis( re.getDst() );
1265 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1269 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1270 if( !hrnSrc.isOutOfContext() ) {
1274 if( srcType == null ) {
1275 if( hrnSrc.getType() != null ) {
1279 if( !srcType.equals( hrnSrc.getType() ) ) {
1284 if( !re.typeEquals( refType ) ) {
1288 if( !re.fieldEquals( refField ) ) {
1292 // tada! We found it!
1299 // used below to convert a ReachSet to its callee-context
1300 // equivalent with respect to allocation sites in this graph
1301 protected ReachSet toCalleeContext( ReachSet rs,
1303 Set<HrnIdOoc> oocHrnIdOoc2callee
1305 ReachSet out = ReachSet.factory();
1307 Iterator<ReachState> itr = rs.iterator();
1308 while( itr.hasNext() ) {
1309 ReachState stateCaller = itr.next();
1311 ReachState stateCallee = stateCaller;
1313 Iterator<AllocSite> asItr = allocSites.iterator();
1314 while( asItr.hasNext() ) {
1315 AllocSite as = asItr.next();
1317 ReachState stateNew = ReachState.factory();
1318 Iterator<ReachTuple> rtItr = stateCallee.iterator();
1319 while( rtItr.hasNext() ) {
1320 ReachTuple rt = rtItr.next();
1322 // only translate this tuple if it is
1323 // in the out-callee-context bag
1324 HrnIdOoc hio = new HrnIdOoc( rt.getHrnID(),
1327 if( !oocHrnIdOoc2callee.contains( hio ) ) {
1328 stateNew = Canonical.add( stateNew, rt );
1332 int age = as.getAgeCategory( rt.getHrnID() );
1334 // this is the current mapping, where 0, 1, 2S were allocated
1335 // in the current context, 0?, 1? and 2S? were allocated in a
1336 // previous context, and we're translating to a future context
1348 if( age == AllocSite.AGE_notInThisSite ) {
1349 // things not from the site just go back in
1350 stateNew = Canonical.add( stateNew, rt );
1352 } else if( age == AllocSite.AGE_summary ||
1355 // the in-context summary and all existing out-of-context
1357 stateNew = Canonical.add( stateNew,
1358 ReachTuple.factory( as.getSummary(),
1361 true // out-of-context
1365 // otherwise everything else just goes to an out-of-context
1366 // version, everything else the same
1367 Integer I = as.getAge( rt.getHrnID() );
1370 assert !rt.isMultiObject();
1372 stateNew = Canonical.add( stateNew,
1373 ReachTuple.factory( rt.getHrnID(),
1376 true // out-of-context
1382 stateCallee = stateNew;
1385 // attach the passed in preds
1386 stateCallee = Canonical.attach( stateCallee,
1389 out = Canonical.add( out,
1394 assert out.isCanonical();
1398 // used below to convert a ReachSet to its caller-context
1399 // equivalent with respect to allocation sites in this graph
1401 toCallerContext( ReachSet rs,
1402 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1404 ReachSet out = ReachSet.factory();
1406 Iterator<ReachState> itr = rs.iterator();
1407 while( itr.hasNext() ) {
1408 ReachState stateCallee = itr.next();
1410 if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
1412 // starting from one callee state...
1413 ReachSet rsCaller = ReachSet.factory( stateCallee );
1415 // possibly branch it into many states, which any
1416 // allocation site might do, so lots of derived states
1417 Iterator<AllocSite> asItr = allocSites.iterator();
1418 while( asItr.hasNext() ) {
1419 AllocSite as = asItr.next();
1420 rsCaller = Canonical.toCallerContext( rsCaller, as );
1423 // then before adding each derived, now caller-context
1424 // states to the output, attach the appropriate pred
1425 // based on the source callee state
1426 Iterator<ReachState> stateItr = rsCaller.iterator();
1427 while( stateItr.hasNext() ) {
1428 ReachState stateCaller = stateItr.next();
1429 stateCaller = Canonical.attach( stateCaller,
1430 calleeStatesSatisfied.get( stateCallee )
1432 out = Canonical.add( out,
1439 assert out.isCanonical();
1443 // used below to convert a ReachSet to an equivalent
1444 // version with shadow IDs merged into unshadowed IDs
1445 protected ReachSet unshadow( ReachSet rs ) {
1447 Iterator<AllocSite> asItr = allocSites.iterator();
1448 while( asItr.hasNext() ) {
1449 AllocSite as = asItr.next();
1450 out = Canonical.unshadow( out, as );
1452 assert out.isCanonical();
1457 // use this method to make a new reach graph that is
1458 // what heap the FlatMethod callee from the FlatCall
1459 // would start with reaching from its arguments in
1462 makeCalleeView( FlatCall fc,
1463 FlatMethod fmCallee,
1464 Set<Integer> callerNodeIDsCopiedToCallee,
1465 boolean writeDebugDOTs
1469 // first traverse this context to find nodes and edges
1470 // that will be callee-reachable
1471 Set<HeapRegionNode> reachableCallerNodes =
1472 new HashSet<HeapRegionNode>();
1474 // caller edges between callee-reachable nodes
1475 Set<RefEdge> reachableCallerEdges =
1476 new HashSet<RefEdge>();
1478 // caller edges from arg vars, and the matching param index
1479 // because these become a special edge in callee
1480 Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1481 new Hashtable<RefEdge, Integer>();
1483 // caller edges from local vars or callee-unreachable nodes
1484 // (out-of-context sources) to callee-reachable nodes
1485 Set<RefEdge> oocCallerEdges =
1486 new HashSet<RefEdge>();
1489 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1491 TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1492 VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
1494 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1495 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1497 toVisitInCaller.add( vnArgCaller );
1499 while( !toVisitInCaller.isEmpty() ) {
1500 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1501 toVisitInCaller.remove( rsnCaller );
1502 visitedInCaller.add( rsnCaller );
1504 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1505 while( itrRefEdges.hasNext() ) {
1506 RefEdge reCaller = itrRefEdges.next();
1507 HeapRegionNode hrnCaller = reCaller.getDst();
1509 callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
1510 reachableCallerNodes.add( hrnCaller );
1512 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1513 reachableCallerEdges.add( reCaller );
1515 if( rsnCaller.equals( vnArgCaller ) ) {
1516 reachableCallerArgEdges2paramIndex.put( reCaller, i );
1518 oocCallerEdges.add( reCaller );
1522 if( !visitedInCaller.contains( hrnCaller ) ) {
1523 toVisitInCaller.add( hrnCaller );
1526 } // end edge iteration
1527 } // end visiting heap nodes in caller
1528 } // end iterating over parameters as starting points
1531 // now collect out-of-callee-context IDs and
1532 // map them to whether the ID is out of the caller
1534 Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1536 Iterator<Integer> itrInContext =
1537 callerNodeIDsCopiedToCallee.iterator();
1538 while( itrInContext.hasNext() ) {
1539 Integer hrnID = itrInContext.next();
1540 HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1542 Iterator<RefEdge> itrMightCross =
1543 hrnCallerAndInContext.iteratorToReferencers();
1544 while( itrMightCross.hasNext() ) {
1545 RefEdge edgeMightCross = itrMightCross.next();
1547 RefSrcNode rsnCallerAndOutContext =
1548 edgeMightCross.getSrc();
1550 if( rsnCallerAndOutContext instanceof VariableNode ) {
1551 // variables do not have out-of-context reach states,
1553 oocCallerEdges.add( edgeMightCross );
1557 HeapRegionNode hrnCallerAndOutContext =
1558 (HeapRegionNode) rsnCallerAndOutContext;
1560 // is this source node out-of-context?
1561 if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1562 // no, skip this edge
1567 oocCallerEdges.add( edgeMightCross );
1569 // add all reach tuples on the node to list
1570 // of things that are out-of-context: insight
1571 // if this node is reachable from someting that WAS
1572 // in-context, then this node should already be in-context
1573 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1574 while( stateItr.hasNext() ) {
1575 ReachState state = stateItr.next();
1577 Iterator<ReachTuple> rtItr = state.iterator();
1578 while( rtItr.hasNext() ) {
1579 ReachTuple rt = rtItr.next();
1581 oocHrnIdOoc2callee.add( new HrnIdOoc( rt.getHrnID(),
1590 // the callee view is a new graph: DON'T MODIFY *THIS* graph
1591 ReachGraph rg = new ReachGraph();
1593 // add nodes to callee graph
1594 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1595 while( hrnItr.hasNext() ) {
1596 HeapRegionNode hrnCaller = hrnItr.next();
1598 assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
1599 assert !rg.id2hrn.containsKey( hrnCaller.getID() );
1601 ExistPred pred = ExistPred.factory( hrnCaller.getID(), null );
1602 ExistPredSet preds = ExistPredSet.factory( pred );
1604 rg.createNewHeapRegionNode( hrnCaller.getID(),
1605 hrnCaller.isSingleObject(),
1606 hrnCaller.isNewSummary(),
1607 hrnCaller.isFlagged(),
1608 false, // out-of-context?
1609 hrnCaller.getType(),
1610 hrnCaller.getAllocSite(),
1611 toCalleeContext( hrnCaller.getInherent(),
1615 toCalleeContext( hrnCaller.getAlpha(),
1620 hrnCaller.getDescription()
1624 // add param edges to callee graph
1626 reachableCallerArgEdges2paramIndex.entrySet().iterator();
1627 while( argEdges.hasNext() ) {
1628 Map.Entry me = (Map.Entry) argEdges.next();
1629 RefEdge reArg = (RefEdge) me.getKey();
1630 Integer index = (Integer) me.getValue();
1632 TempDescriptor arg = fmCallee.getParameter( index );
1634 VariableNode vnCallee =
1635 rg.getVariableNodeFromTemp( arg );
1637 HeapRegionNode hrnDstCaller = reArg.getDst();
1638 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1639 assert hrnDstCallee != null;
1642 ExistPred.factory( arg,
1644 hrnDstCallee.getID(),
1648 true, // out-of-callee-context
1649 false // out-of-caller-context
1652 ExistPredSet preds =
1653 ExistPredSet.factory( pred );
1656 new RefEdge( vnCallee,
1660 toCalleeContext( reArg.getBeta(),
1667 rg.addRefEdge( vnCallee,
1673 // add in-context edges to callee graph
1674 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1675 while( reItr.hasNext() ) {
1676 RefEdge reCaller = reItr.next();
1677 RefSrcNode rsnCaller = reCaller.getSrc();
1678 assert rsnCaller instanceof HeapRegionNode;
1679 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1680 HeapRegionNode hrnDstCaller = reCaller.getDst();
1682 HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
1683 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1684 assert hrnSrcCallee != null;
1685 assert hrnDstCallee != null;
1688 ExistPred.factory( null,
1689 hrnSrcCallee.getID(),
1690 hrnDstCallee.getID(),
1692 reCaller.getField(),
1694 false, // out-of-callee-context
1695 false // out-of-caller-context
1698 ExistPredSet preds =
1699 ExistPredSet.factory( pred );
1702 new RefEdge( hrnSrcCallee,
1705 reCaller.getField(),
1706 toCalleeContext( reCaller.getBeta(),
1713 rg.addRefEdge( hrnSrcCallee,
1719 // add out-of-context edges to callee graph
1720 reItr = oocCallerEdges.iterator();
1721 while( reItr.hasNext() ) {
1722 RefEdge reCaller = reItr.next();
1723 RefSrcNode rsnCaller = reCaller.getSrc();
1724 HeapRegionNode hrnDstCaller = reCaller.getDst();
1725 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1726 assert hrnDstCallee != null;
1728 TypeDescriptor oocNodeType;
1730 TempDescriptor oocPredSrcTemp = null;
1731 Integer oocPredSrcID = null;
1732 boolean outOfCalleeContext;
1733 boolean outOfCallerContext;
1735 if( rsnCaller instanceof VariableNode ) {
1736 VariableNode vnCaller = (VariableNode) rsnCaller;
1738 oocReach = rsetEmpty;
1739 oocPredSrcTemp = vnCaller.getTempDescriptor();
1740 outOfCalleeContext = true;
1741 outOfCallerContext = false;
1744 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1745 assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
1746 oocNodeType = hrnSrcCaller.getType();
1747 oocReach = hrnSrcCaller.getAlpha();
1748 oocPredSrcID = hrnSrcCaller.getID();
1749 if( hrnSrcCaller.isOutOfContext() ) {
1750 outOfCalleeContext = false;
1751 outOfCallerContext = true;
1753 outOfCalleeContext = true;
1754 outOfCallerContext = false;
1759 ExistPred.factory( oocPredSrcTemp,
1761 hrnDstCallee.getID(),
1763 reCaller.getField(),
1769 ExistPredSet preds =
1770 ExistPredSet.factory( pred );
1772 RefEdge oocEdgeExisting =
1773 rg.getOutOfContextReferenceTo( hrnDstCallee,
1779 if( oocEdgeExisting == null ) {
1780 // for consistency, map one out-of-context "identifier"
1781 // to one heap region node id, otherwise no convergence
1782 String oocid = "oocid"+
1784 hrnDstCallee.getIDString()+
1787 reCaller.getField();
1789 Integer oocHrnID = oocid2hrnid.get( oocid );
1791 HeapRegionNode hrnCalleeAndOutContext;
1793 if( oocHrnID == null ) {
1795 hrnCalleeAndOutContext =
1796 rg.createNewHeapRegionNode( null, // ID
1797 false, // single object?
1798 false, // new summary?
1800 true, // out-of-context?
1802 null, // alloc site, shouldn't be used
1803 toCalleeContext( oocReach,
1807 toCalleeContext( oocReach,
1815 oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1819 // the mapping already exists, so see if node is there
1820 hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1822 if( hrnCalleeAndOutContext == null ) {
1824 hrnCalleeAndOutContext =
1825 rg.createNewHeapRegionNode( oocHrnID, // ID
1826 false, // single object?
1827 false, // new summary?
1829 true, // out-of-context?
1831 null, // alloc site, shouldn't be used
1832 toCalleeContext( oocReach,
1836 toCalleeContext( oocReach,
1845 // otherwise it is there, so merge reachability
1846 hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1847 toCalleeContext( oocReach,
1856 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1858 rg.addRefEdge( hrnCalleeAndOutContext,
1860 new RefEdge( hrnCalleeAndOutContext,
1863 reCaller.getField(),
1864 toCalleeContext( reCaller.getBeta(),
1873 // the out-of-context edge already exists
1874 oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
1875 toCalleeContext( reCaller.getBeta(),
1882 oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1887 HeapRegionNode hrnCalleeAndOutContext =
1888 (HeapRegionNode) oocEdgeExisting.getSrc();
1889 hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1890 toCalleeContext( oocReach,
1897 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1902 if( writeDebugDOTs ) {
1903 debugGraphPrefix = String.format( "call%02d", debugCallSiteVisits );
1904 rg.writeGraph( debugGraphPrefix+"calleeview",
1905 resolveMethodDebugDOTwriteLabels,
1906 resolveMethodDebugDOTselectTemps,
1907 resolveMethodDebugDOTpruneGarbage,
1908 resolveMethodDebugDOThideSubsetReach,
1909 resolveMethodDebugDOThideEdgeTaints );
1915 private static Hashtable<String, Integer> oocid2hrnid =
1916 new Hashtable<String, Integer>();
1919 // useful since many graphs writes in the method call debug code
1920 private static boolean resolveMethodDebugDOTwriteLabels = true;
1921 private static boolean resolveMethodDebugDOTselectTemps = true;
1922 private static boolean resolveMethodDebugDOTpruneGarbage = true;
1923 private static boolean resolveMethodDebugDOThideSubsetReach = false;
1924 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
1926 static String debugGraphPrefix;
1927 static int debugCallSiteVisits = 0;
1928 static int debugCallSiteVisitsUntilExit = 0;
1932 resolveMethodCall( FlatCall fc,
1933 FlatMethod fmCallee,
1934 ReachGraph rgCallee,
1935 Set<Integer> callerNodeIDsCopiedToCallee,
1936 boolean writeDebugDOTs
1939 if( writeDebugDOTs ) {
1940 debugGraphPrefix = String.format( "call%02d", debugCallSiteVisits );
1942 rgCallee.writeGraph( debugGraphPrefix+"callee",
1943 resolveMethodDebugDOTwriteLabels,
1944 resolveMethodDebugDOTselectTemps,
1945 resolveMethodDebugDOTpruneGarbage,
1946 resolveMethodDebugDOThideSubsetReach,
1947 resolveMethodDebugDOThideEdgeTaints );
1949 writeGraph( debugGraphPrefix+"caller00In",
1950 resolveMethodDebugDOTwriteLabels,
1951 resolveMethodDebugDOTselectTemps,
1952 resolveMethodDebugDOTpruneGarbage,
1953 resolveMethodDebugDOThideSubsetReach,
1954 resolveMethodDebugDOThideEdgeTaints,
1955 callerNodeIDsCopiedToCallee );
1960 // method call transfer function steps:
1961 // 1. Use current callee-reachable heap (CRH) to test callee
1962 // predicates and mark what will be coming in.
1963 // 2. Wipe CRH out of caller.
1964 // 3. Transplant marked callee parts in:
1965 // a) bring in nodes
1966 // b) bring in callee -> callee edges
1967 // c) resolve out-of-context -> callee edges
1968 // d) assign return value
1969 // 4. Collapse shadow nodes down
1970 // 5. Global sweep it.
1973 // 1. mark what callee elements have satisfied predicates
1974 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1975 new Hashtable<HeapRegionNode, ExistPredSet>();
1977 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1978 new Hashtable<RefEdge, ExistPredSet>();
1980 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1981 new Hashtable<ReachState, ExistPredSet>();
1983 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1984 new Hashtable< RefEdge, Set<RefSrcNode> >();
1986 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1987 while( meItr.hasNext() ) {
1988 Map.Entry me = (Map.Entry) meItr.next();
1989 Integer id = (Integer) me.getKey();
1990 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1992 // if a callee element's predicates are satisfied then a set
1993 // of CALLER predicates is returned: they are the predicates
1994 // that the callee element moved into the caller context
1995 // should have, and it is inefficient to find this again later
1996 ExistPredSet predsIfSatis =
1997 hrnCallee.getPreds().isSatisfiedBy( this,
1998 callerNodeIDsCopiedToCallee
2001 if( predsIfSatis != null ) {
2002 calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
2004 // otherwise don't bother looking at edges to this node
2008 // since the node is coming over, find out which reach
2009 // states on it should come over, too
2010 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2011 while( stateItr.hasNext() ) {
2012 ReachState stateCallee = stateItr.next();
2015 stateCallee.getPreds().isSatisfiedBy( this,
2016 callerNodeIDsCopiedToCallee
2018 if( predsIfSatis != null ) {
2019 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2023 // then look at edges to the node
2024 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2025 while( reItr.hasNext() ) {
2026 RefEdge reCallee = reItr.next();
2027 RefSrcNode rsnCallee = reCallee.getSrc();
2029 // (caller local variables to in-context heap regions)
2030 // have an (out-of-context heap region -> in-context heap region)
2031 // abstraction in the callEE, so its true we never need to
2032 // look at a (var node -> heap region) edge in callee to bring
2033 // those over for the call site transfer. What about (param var->heap region)
2034 // edges in callee? They are dealt with below this loop.
2035 // So, yes, at this point skip (var->region) edges in callee
2036 if( rsnCallee instanceof VariableNode ) {
2040 // first see if the source is out-of-context, and only
2041 // proceed with this edge if we find some caller-context
2043 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2044 boolean matchedOutOfContext = false;
2046 if( !hrnSrcCallee.isOutOfContext() ) {
2049 hrnSrcCallee.getPreds().isSatisfiedBy( this,
2050 callerNodeIDsCopiedToCallee
2052 if( predsIfSatis != null ) {
2053 calleeNodesSatisfied.put( hrnSrcCallee, predsIfSatis );
2055 // otherwise forget this edge
2060 // hrnSrcCallee is out-of-context
2062 assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2064 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2066 // is the target node in the caller?
2067 HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2068 if( hrnDstCaller == null ) {
2072 Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2073 while( reDstItr.hasNext() ) {
2074 // the edge and field (either possibly null) must match
2075 RefEdge reCaller = reDstItr.next();
2077 if( !reCaller.typeEquals ( reCallee.getType() ) ||
2078 !reCaller.fieldEquals( reCallee.getField() )
2083 RefSrcNode rsnCaller = reCaller.getSrc();
2084 if( rsnCaller instanceof VariableNode ) {
2086 // a variable node matches an OOC region with null type
2087 if( hrnSrcCallee.getType() != null ) {
2092 // otherwise types should match
2093 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2094 if( hrnSrcCallee.getType() == null ) {
2095 if( hrnCallerSrc.getType() != null ) {
2099 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2105 rsnCallers.add( rsnCaller );
2106 matchedOutOfContext = true;
2109 if( !rsnCallers.isEmpty() ) {
2110 calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2114 if( hrnSrcCallee.isOutOfContext() &&
2115 !matchedOutOfContext ) {
2120 reCallee.getPreds().isSatisfiedBy( this,
2121 callerNodeIDsCopiedToCallee
2124 if( predsIfSatis != null ) {
2125 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2127 // since the edge is coming over, find out which reach
2128 // states on it should come over, too
2129 stateItr = reCallee.getBeta().iterator();
2130 while( stateItr.hasNext() ) {
2131 ReachState stateCallee = stateItr.next();
2134 stateCallee.getPreds().isSatisfiedBy( this,
2135 callerNodeIDsCopiedToCallee
2137 if( predsIfSatis != null ) {
2138 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2145 // test param -> HRN edges, also
2146 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
2148 // parameter defined here is the symbol in the callee
2149 TempDescriptor tdParam = fmCallee.getParameter( i );
2151 if( !DisjointAnalysis.shouldAnalysisTrack( tdParam.getType() ) ) {
2152 // skip primitive/immutable parameters
2156 VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
2158 Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
2159 while( reItr.hasNext() ) {
2160 RefEdge reCallee = reItr.next();
2162 ExistPredSet ifDst =
2163 reCallee.getDst().getPreds().isSatisfiedBy( this,
2164 callerNodeIDsCopiedToCallee
2166 if( ifDst == null ) {
2170 ExistPredSet predsIfSatis =
2171 reCallee.getPreds().isSatisfiedBy( this,
2172 callerNodeIDsCopiedToCallee
2174 if( predsIfSatis != null ) {
2175 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2177 // since the edge is coming over, find out which reach
2178 // states on it should come over, too
2179 Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
2180 while( stateItr.hasNext() ) {
2181 ReachState stateCallee = stateItr.next();
2184 stateCallee.getPreds().isSatisfiedBy( this,
2185 callerNodeIDsCopiedToCallee
2187 if( predsIfSatis != null ) {
2188 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2199 if( writeDebugDOTs ) {
2200 writeGraph( debugGraphPrefix+"caller20BeforeWipe",
2201 resolveMethodDebugDOTwriteLabels,
2202 resolveMethodDebugDOTselectTemps,
2203 resolveMethodDebugDOTpruneGarbage,
2204 resolveMethodDebugDOThideSubsetReach,
2205 resolveMethodDebugDOThideEdgeTaints );
2209 // 2. predicates tested, ok to wipe out caller part
2210 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2211 while( hrnItr.hasNext() ) {
2212 Integer hrnID = hrnItr.next();
2213 HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2214 assert hrnCaller != null;
2216 // when clearing off nodes, also eliminate variable
2218 wipeOut( hrnCaller, true );
2223 if( writeDebugDOTs ) {
2224 writeGraph( debugGraphPrefix+"caller30BeforeAddingNodes",
2225 resolveMethodDebugDOTwriteLabels,
2226 resolveMethodDebugDOTselectTemps,
2227 resolveMethodDebugDOTpruneGarbage,
2228 resolveMethodDebugDOThideSubsetReach,
2229 resolveMethodDebugDOThideEdgeTaints );
2233 // 3. callee elements with satisfied preds come in, note that
2234 // the mapping of elements satisfied to preds is like this:
2235 // A callee element EE has preds EEp that are satisfied by
2236 // some caller element ER. We bring EE into the caller
2237 // context as ERee with the preds of ER, namely ERp, which
2238 // in the following algorithm is the value in the mapping
2241 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2242 while( satisItr.hasNext() ) {
2243 Map.Entry me = (Map.Entry) satisItr.next();
2244 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2245 ExistPredSet preds = (ExistPredSet) me.getValue();
2247 // TODO: I think its true that the current implementation uses
2248 // the type of the OOC region and the predicates OF THE EDGE from
2249 // it to link everything up in caller context, so that's why we're
2250 // skipping this... maybe that's a sillier way to do it?
2251 if( hrnCallee.isOutOfContext() ) {
2255 AllocSite as = hrnCallee.getAllocSite();
2256 allocSites.add( as );
2258 Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2260 HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2261 if( hrnCaller == null ) {
2263 createNewHeapRegionNode( hrnIDshadow, // id or null to generate a new one
2264 hrnCallee.isSingleObject(), // single object?
2265 hrnCallee.isNewSummary(), // summary?
2266 hrnCallee.isFlagged(), // flagged?
2267 false, // out-of-context?
2268 hrnCallee.getType(), // type
2269 hrnCallee.getAllocSite(), // allocation site
2270 toCallerContext( hrnCallee.getInherent(),
2271 calleeStatesSatisfied ), // inherent reach
2272 null, // current reach
2273 predsEmpty, // predicates
2274 hrnCallee.getDescription() // description
2277 assert hrnCaller.isWiped();
2280 hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2281 calleeStatesSatisfied
2285 hrnCaller.setPreds( preds );
2290 if( writeDebugDOTs ) {
2291 writeGraph( debugGraphPrefix+"caller31BeforeAddingEdges",
2292 resolveMethodDebugDOTwriteLabels,
2293 resolveMethodDebugDOTselectTemps,
2294 resolveMethodDebugDOTpruneGarbage,
2295 resolveMethodDebugDOThideSubsetReach,
2296 resolveMethodDebugDOThideEdgeTaints );
2300 // set these up during the next procedure so after
2301 // the caller has all of its nodes and edges put
2302 // back together we can propagate the callee's
2303 // reach changes backwards into the caller graph
2304 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2306 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2307 new Hashtable<RefEdge, ChangeSet>();
2310 // 3.b) callee -> callee edges AND out-of-context -> callee
2311 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2312 while( satisItr.hasNext() ) {
2313 Map.Entry me = (Map.Entry) satisItr.next();
2314 RefEdge reCallee = (RefEdge) me.getKey();
2315 ExistPredSet preds = (ExistPredSet) me.getValue();
2317 HeapRegionNode hrnDstCallee = reCallee.getDst();
2318 AllocSite asDst = hrnDstCallee.getAllocSite();
2319 allocSites.add( asDst );
2321 Integer hrnIDDstShadow =
2322 asDst.getShadowIDfromID( hrnDstCallee.getID() );
2324 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2325 assert hrnDstCaller != null;
2328 RefSrcNode rsnCallee = reCallee.getSrc();
2330 Set<RefSrcNode> rsnCallers =
2331 new HashSet<RefSrcNode>();
2333 Set<RefSrcNode> oocCallers =
2334 calleeEdges2oocCallerSrcMatches.get( reCallee );
2336 if( rsnCallee instanceof HeapRegionNode ) {
2337 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2338 if( hrnCalleeSrc.isOutOfContext() ) {
2339 assert oocCallers != null;
2344 if( oocCallers == null ) {
2345 // there are no out-of-context matches, so it's
2346 // either a param/arg var or one in-context heap region
2347 if( rsnCallee instanceof VariableNode ) {
2348 // variable -> node in the callee should only
2349 // come into the caller if its from a param var
2350 VariableNode vnCallee = (VariableNode) rsnCallee;
2351 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2352 TempDescriptor tdArg = fc.getArgMatchingParam( fmCallee,
2354 if( tdArg == null ) {
2355 // this means the variable isn't a parameter, its local
2356 // to the callee so we ignore it in call site transfer
2357 // shouldn't this NEVER HAPPEN?
2361 rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2364 // otherwise source is in context, one region
2366 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2368 // translate an in-context node to shadow
2369 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2370 allocSites.add( asSrc );
2372 Integer hrnIDSrcShadow =
2373 asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2375 HeapRegionNode hrnSrcCallerShadow =
2376 this.id2hrn.get( hrnIDSrcShadow );
2378 assert hrnSrcCallerShadow != null;
2380 rsnCallers.add( hrnSrcCallerShadow );
2384 // otherwise we have a set of out-of-context srcs
2385 // that should NOT be translated to shadow nodes
2386 assert !oocCallers.isEmpty();
2387 rsnCallers.addAll( oocCallers );
2390 // now make all caller edges we've identified from
2391 // this callee edge with a satisfied predicate
2392 assert !rsnCallers.isEmpty();
2393 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2394 while( rsnItr.hasNext() ) {
2395 RefSrcNode rsnCaller = rsnItr.next();
2397 RefEdge reCaller = new RefEdge( rsnCaller,
2400 reCallee.getField(),
2401 toCallerContext( reCallee.getBeta(),
2402 calleeStatesSatisfied ),
2406 ChangeSet cs = ChangeSet.factory();
2407 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2408 while( rsItr.hasNext() ) {
2409 ReachState state = rsItr.next();
2410 ExistPredSet predsPreCallee = state.getPreds();
2412 if( state.isEmpty() ) {
2416 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2417 while( predItr.hasNext() ) {
2418 ExistPred pred = predItr.next();
2419 ReachState old = pred.ne_state;
2425 cs = Canonical.add( cs,
2426 ChangeTuple.factory( old,
2434 // look to see if an edge with same field exists
2435 // and merge with it, otherwise just add the edge
2436 RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2440 if( edgeExisting != null ) {
2441 edgeExisting.setBeta(
2442 Canonical.unionORpreds( edgeExisting.getBeta(),
2446 edgeExisting.setPreds(
2447 Canonical.join( edgeExisting.getPreds(),
2452 // for reach propagation
2453 if( !cs.isEmpty() ) {
2454 ChangeSet csExisting = edgePlannedChanges.get( edgeExisting );
2455 if( csExisting == null ) {
2456 csExisting = ChangeSet.factory();
2458 edgePlannedChanges.put( edgeExisting,
2459 Canonical.union( csExisting,
2466 addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2468 // for reach propagation
2469 if( !cs.isEmpty() ) {
2470 edgesForPropagation.add( reCaller );
2471 assert !edgePlannedChanges.containsKey( reCaller );
2472 edgePlannedChanges.put( reCaller, cs );
2482 if( writeDebugDOTs ) {
2483 writeGraph( debugGraphPrefix+"caller35BeforeAssignReturnValue",
2484 resolveMethodDebugDOTwriteLabels,
2485 resolveMethodDebugDOTselectTemps,
2486 resolveMethodDebugDOTpruneGarbage,
2487 resolveMethodDebugDOThideSubsetReach,
2488 resolveMethodDebugDOThideEdgeTaints );
2493 // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2494 // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2495 // EDGES, JUST BRINGING THEM ALL! It'll work for now, over approximation
2497 // 3.d) handle return value assignment if needed
2498 TempDescriptor returnTemp = fc.getReturnTemp();
2499 if( returnTemp != null &&
2500 DisjointAnalysis.shouldAnalysisTrack( returnTemp.getType() )
2503 VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2504 clearRefEdgesFrom( vnLhsCaller, null, null, true );
2506 VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2507 Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2508 while( reCalleeItr.hasNext() ) {
2509 RefEdge reCallee = reCalleeItr.next();
2510 HeapRegionNode hrnDstCallee = reCallee.getDst();
2512 // some edge types are not possible return values when we can
2513 // see what type variable we are assigning it to
2514 if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2515 System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2516 reCallee+" for return temp "+returnTemp );
2521 AllocSite asDst = hrnDstCallee.getAllocSite();
2522 allocSites.add( asDst );
2524 Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2526 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2527 if( hrnDstCaller == null ) {
2529 createNewHeapRegionNode( hrnIDDstShadow, // id or null to generate a new one
2530 hrnDstCallee.isSingleObject(), // single object?
2531 hrnDstCallee.isNewSummary(), // summary?
2532 hrnDstCallee.isFlagged(), // flagged?
2533 false, // out-of-context?
2534 hrnDstCallee.getType(), // type
2535 hrnDstCallee.getAllocSite(), // allocation site
2536 toCallerContext( hrnDstCallee.getInherent(),
2537 calleeStatesSatisfied ), // inherent reach
2538 toCallerContext( hrnDstCallee.getAlpha(),
2539 calleeStatesSatisfied ), // current reach
2540 predsTrue, // predicates
2541 hrnDstCallee.getDescription() // description
2545 TypeDescriptor tdNewEdge =
2546 mostSpecificType( reCallee.getType(),
2547 hrnDstCallee.getType(),
2548 hrnDstCaller.getType()
2551 RefEdge reCaller = new RefEdge( vnLhsCaller,
2555 toCallerContext( reCallee.getBeta(),
2556 calleeStatesSatisfied ),
2560 addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2566 if( writeDebugDOTs ) {
2567 writeGraph( debugGraphPrefix+"caller38propagateReach",
2568 resolveMethodDebugDOTwriteLabels,
2569 resolveMethodDebugDOTselectTemps,
2570 resolveMethodDebugDOTpruneGarbage,
2571 resolveMethodDebugDOThideSubsetReach,
2572 resolveMethodDebugDOThideEdgeTaints );
2575 // propagate callee reachability changes to the rest
2576 // of the caller graph edges
2577 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2579 propagateTokensOverEdges( edgesForPropagation, // source edges
2580 edgePlannedChanges, // map src edge to change set
2581 edgesUpdated ); // list of updated edges
2583 // commit beta' (beta<-betaNew)
2584 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2585 while( edgeItr.hasNext() ) {
2586 edgeItr.next().applyBetaNew();
2594 if( writeDebugDOTs ) {
2595 writeGraph( debugGraphPrefix+"caller40BeforeShadowMerge",
2596 resolveMethodDebugDOTwriteLabels,
2597 resolveMethodDebugDOTselectTemps,
2598 resolveMethodDebugDOTpruneGarbage,
2599 resolveMethodDebugDOThideSubsetReach,
2600 resolveMethodDebugDOThideEdgeTaints );
2604 // 4) merge shadow nodes so alloc sites are back to k
2605 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2606 while( asItr.hasNext() ) {
2607 // for each allocation site do the following to merge
2608 // shadow nodes (newest from callee) with any existing
2609 // look for the newest normal and newest shadow "slot"
2610 // not being used, transfer normal to shadow. Keep
2611 // doing this until there are no more normal nodes, or
2612 // no empty shadow slots: then merge all remaining normal
2613 // nodes into the shadow summary. Finally, convert all
2614 // shadow to their normal versions.
2615 AllocSite as = asItr.next();
2618 while( ageNorm < allocationDepth &&
2619 ageShad < allocationDepth ) {
2621 // first, are there any normal nodes left?
2622 Integer idNorm = as.getIthOldest( ageNorm );
2623 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2624 if( hrnNorm == null ) {
2625 // no, this age of normal node not in the caller graph
2630 // yes, a normal node exists, is there an empty shadow
2631 // "slot" to transfer it onto?
2632 HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2633 if( !hrnShad.isWiped() ) {
2634 // no, this age of shadow node is not empty
2639 // yes, this shadow node is empty
2640 transferOnto( hrnNorm, hrnShad );
2645 // now, while there are still normal nodes but no shadow
2646 // slots, merge normal nodes into the shadow summary
2647 while( ageNorm < allocationDepth ) {
2649 // first, are there any normal nodes left?
2650 Integer idNorm = as.getIthOldest( ageNorm );
2651 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2652 if( hrnNorm == null ) {
2653 // no, this age of normal node not in the caller graph
2658 // yes, a normal node exists, so get the shadow summary
2659 HeapRegionNode summShad = getSummaryNode( as, true );
2660 mergeIntoSummary( hrnNorm, summShad );
2664 // if there is a normal summary, merge it into shadow summary
2665 Integer idNorm = as.getSummary();
2666 HeapRegionNode summNorm = id2hrn.get( idNorm );
2667 if( summNorm != null ) {
2668 HeapRegionNode summShad = getSummaryNode( as, true );
2669 mergeIntoSummary( summNorm, summShad );
2672 // finally, flip all existing shadow nodes onto the normal
2673 for( int i = 0; i < allocationDepth; ++i ) {
2674 Integer idShad = as.getIthOldestShadow( i );
2675 HeapRegionNode hrnShad = id2hrn.get( idShad );
2676 if( hrnShad != null ) {
2678 HeapRegionNode hrnNorm = getIthNode( as, i, false );
2679 assert hrnNorm.isWiped();
2680 transferOnto( hrnShad, hrnNorm );
2684 Integer idShad = as.getSummaryShadow();
2685 HeapRegionNode summShad = id2hrn.get( idShad );
2686 if( summShad != null ) {
2687 summNorm = getSummaryNode( as, false );
2688 transferOnto( summShad, summNorm );
2693 if( writeDebugDOTs ) {
2694 writeGraph( debugGraphPrefix+"caller45BeforeUnshadow",
2695 resolveMethodDebugDOTwriteLabels,
2696 resolveMethodDebugDOTselectTemps,
2697 resolveMethodDebugDOTpruneGarbage,
2698 resolveMethodDebugDOThideSubsetReach,
2699 resolveMethodDebugDOThideEdgeTaints );
2703 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2704 while( itrAllHRNodes.hasNext() ) {
2705 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
2706 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2708 hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2710 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2711 while( itrEdges.hasNext() ) {
2712 RefEdge re = itrEdges.next();
2713 re.setBeta( unshadow( re.getBeta() ) );
2719 if( writeDebugDOTs ) {
2720 writeGraph( debugGraphPrefix+"caller50BeforeGlobalSweep",
2721 resolveMethodDebugDOTwriteLabels,
2722 resolveMethodDebugDOTselectTemps,
2723 resolveMethodDebugDOTpruneGarbage,
2724 resolveMethodDebugDOThideSubsetReach,
2725 resolveMethodDebugDOThideEdgeTaints );
2730 if( !DISABLE_GLOBAL_SWEEP ) {
2736 if( writeDebugDOTs ) {
2737 writeGraph( debugGraphPrefix+"caller90AfterTransfer",
2738 resolveMethodDebugDOTwriteLabels,
2739 resolveMethodDebugDOTselectTemps,
2740 resolveMethodDebugDOTpruneGarbage,
2741 resolveMethodDebugDOThideSubsetReach,
2742 resolveMethodDebugDOThideEdgeTaints );
2744 ++debugCallSiteVisits;
2745 if( debugCallSiteVisits >= debugCallSiteVisitsUntilExit ) {
2746 System.out.println( "!!! Exiting after requested visits to call site. !!!" );
2754 ////////////////////////////////////////////////////
2756 // Abstract garbage collection simply removes
2757 // heap region nodes that are not mechanically
2758 // reachable from a root set. This step is
2759 // essential for testing node and edge existence
2760 // predicates efficiently
2762 ////////////////////////////////////////////////////
2763 public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2765 // calculate a root set, will be different for Java
2766 // version of analysis versus Bamboo version
2767 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2769 // visit every variable in graph while building root
2770 // set, and do iterating on a copy, so we can remove
2771 // dead variables while we're at this
2772 Iterator makeCopyItr = td2vn.entrySet().iterator();
2773 Set entrysCopy = new HashSet();
2774 while( makeCopyItr.hasNext() ) {
2775 entrysCopy.add( makeCopyItr.next() );
2778 Iterator eItr = entrysCopy.iterator();
2779 while( eItr.hasNext() ) {
2780 Map.Entry me = (Map.Entry) eItr.next();
2781 TempDescriptor td = (TempDescriptor) me.getKey();
2782 VariableNode vn = (VariableNode) me.getValue();
2784 if( liveSet.contains( td ) ) {
2788 // dead var, remove completely from graph
2790 clearRefEdgesFrom( vn, null, null, true );
2794 // everything visited in a traversal is
2795 // considered abstractly live
2796 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2798 while( !toVisit.isEmpty() ) {
2799 RefSrcNode rsn = toVisit.iterator().next();
2800 toVisit.remove( rsn );
2803 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2804 while( hrnItr.hasNext() ) {
2805 RefEdge edge = hrnItr.next();
2806 HeapRegionNode hrn = edge.getDst();
2808 if( !visited.contains( hrn ) ) {
2814 // get a copy of the set to iterate over because
2815 // we're going to monkey with the graph when we
2816 // identify a garbage node
2817 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2818 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2819 while( hrnItr.hasNext() ) {
2820 hrnAllPrior.add( hrnItr.next() );
2823 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2824 while( hrnAllItr.hasNext() ) {
2825 HeapRegionNode hrn = hrnAllItr.next();
2827 if( !visited.contains( hrn ) ) {
2829 // heap region nodes are compared across ReachGraph
2830 // objects by their integer ID, so when discarding
2831 // garbage nodes we must also discard entries in
2832 // the ID -> heap region hashtable.
2833 id2hrn.remove( hrn.getID() );
2835 // RefEdge objects are two-way linked between
2836 // nodes, so when a node is identified as garbage,
2837 // actively clear references to and from it so
2838 // live nodes won't have dangling RefEdge's
2839 wipeOut( hrn, true );
2841 // if we just removed the last node from an allocation
2842 // site, it should be taken out of the ReachGraph's list
2843 AllocSite as = hrn.getAllocSite();
2844 if( !hasNodesOf( as ) ) {
2845 allocSites.remove( as );
2851 protected boolean hasNodesOf( AllocSite as ) {
2852 if( id2hrn.containsKey( as.getSummary() ) ) {
2856 for( int i = 0; i < allocationDepth; ++i ) {
2857 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2865 ////////////////////////////////////////////////////
2867 // This global sweep is an optional step to prune
2868 // reachability sets that are not internally
2869 // consistent with the global graph. It should be
2870 // invoked after strong updates or method calls.
2872 ////////////////////////////////////////////////////
2873 public void globalSweep() {
2875 // boldB is part of the phase 1 sweep
2876 // it has an in-context table and an out-of-context table
2877 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2878 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2880 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2881 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2883 // visit every heap region to initialize alphaNew and betaNew,
2884 // and make a map of every hrnID to the source nodes it should
2885 // propagate forward from. In-context flagged hrnID's propagate
2886 // from only the in-context node they name, but out-of-context
2887 // ID's may propagate from several out-of-context nodes
2888 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2889 new Hashtable< Integer, Set<HeapRegionNode> >();
2891 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2892 new Hashtable< Integer, Set<HeapRegionNode> >();
2895 Iterator itrHrns = id2hrn.entrySet().iterator();
2896 while( itrHrns.hasNext() ) {
2897 Map.Entry me = (Map.Entry) itrHrns.next();
2898 Integer hrnID = (Integer) me.getKey();
2899 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2901 // assert that this node and incoming edges have clean alphaNew
2902 // and betaNew sets, respectively
2903 assert rsetEmpty.equals( hrn.getAlphaNew() );
2905 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2906 while( itrRers.hasNext() ) {
2907 RefEdge edge = itrRers.next();
2908 assert rsetEmpty.equals( edge.getBetaNew() );
2911 // make a mapping of IDs to heap regions they propagate from
2912 if( hrn.isFlagged() ) {
2913 assert !hrn.isOutOfContext();
2914 assert !icID2srcs.containsKey( hrn.getID() );
2916 // in-context flagged node IDs simply propagate from the
2918 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2920 icID2srcs.put( hrn.getID(), srcs );
2923 if( hrn.isOutOfContext() ) {
2924 assert !hrn.isFlagged();
2926 // the reachability states on an out-of-context
2927 // node are not really important (combinations of
2928 // IDs or arity)--what matters is that the states
2929 // specify which nodes this out-of-context node
2930 // stands in for. For example, if the state [17?, 19*]
2931 // appears on the ooc node, it may serve as a source
2932 // for node 17? and a source for node 19.
2933 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2934 while( stateItr.hasNext() ) {
2935 ReachState state = stateItr.next();
2937 Iterator<ReachTuple> rtItr = state.iterator();
2938 while( rtItr.hasNext() ) {
2939 ReachTuple rt = rtItr.next();
2940 assert rt.isOutOfContext();
2942 Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2943 if( srcs == null ) {
2944 srcs = new HashSet<HeapRegionNode>();
2947 oocID2srcs.put( rt.getHrnID(), srcs );
2953 // calculate boldB for all hrnIDs identified by the above
2954 // node traversal, propagating from every source
2955 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2958 Set<HeapRegionNode> srcs;
2961 if( !icID2srcs.isEmpty() ) {
2962 Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2963 hrnID = (Integer) me.getKey();
2964 srcs = (Set<HeapRegionNode>) me.getValue();
2966 icID2srcs.remove( hrnID );
2969 assert !oocID2srcs.isEmpty();
2971 Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2972 hrnID = (Integer) me.getKey();
2973 srcs = (Set<HeapRegionNode>) me.getValue();
2975 oocID2srcs.remove( hrnID );
2979 Hashtable<RefEdge, ReachSet> boldB_f =
2980 new Hashtable<RefEdge, ReachSet>();
2982 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2984 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2985 while( hrnItr.hasNext() ) {
2986 HeapRegionNode hrn = hrnItr.next();
2988 assert workSetEdges.isEmpty();
2990 // initial boldB_f constraints
2991 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2992 while( itrRees.hasNext() ) {
2993 RefEdge edge = itrRees.next();
2995 assert !boldB_f.containsKey( edge );
2996 boldB_f.put( edge, edge.getBeta() );
2998 assert !workSetEdges.contains( edge );
2999 workSetEdges.add( edge );
3002 // enforce the boldB_f constraint at edges until we reach a fixed point
3003 while( !workSetEdges.isEmpty() ) {
3004 RefEdge edge = workSetEdges.iterator().next();
3005 workSetEdges.remove( edge );
3007 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3008 while( itrPrime.hasNext() ) {
3009 RefEdge edgePrime = itrPrime.next();
3011 ReachSet prevResult = boldB_f.get( edgePrime );
3012 ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
3016 if( prevResult == null ||
3017 Canonical.unionORpreds( prevResult,
3018 intersection ).size()
3022 if( prevResult == null ) {
3023 boldB_f.put( edgePrime,
3024 Canonical.unionORpreds( edgePrime.getBeta(),
3029 boldB_f.put( edgePrime,
3030 Canonical.unionORpreds( prevResult,
3035 workSetEdges.add( edgePrime );
3042 boldBic.put( hrnID, boldB_f );
3044 boldBooc.put( hrnID, boldB_f );
3049 // use boldB to prune hrnIDs from alpha states that are impossible
3050 // and propagate the differences backwards across edges
3051 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3053 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3054 new Hashtable<RefEdge, ChangeSet>();
3057 itrHrns = id2hrn.entrySet().iterator();
3058 while( itrHrns.hasNext() ) {
3059 Map.Entry me = (Map.Entry) itrHrns.next();
3060 Integer hrnID = (Integer) me.getKey();
3061 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3063 // out-of-context nodes don't participate in the
3064 // global sweep, they serve as sources for the pass
3066 if( hrn.isOutOfContext() ) {
3070 // the inherent states of a region are the exception
3071 // to removal as the global sweep prunes
3072 ReachTuple rtException = ReachTuple.factory( hrnID,
3073 !hrn.isSingleObject(),
3074 ReachTuple.ARITY_ONE,
3075 false // out-of-context
3078 ChangeSet cts = ChangeSet.factory();
3080 // mark hrnIDs for removal
3081 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3082 while( stateItr.hasNext() ) {
3083 ReachState stateOld = stateItr.next();
3085 ReachState markedHrnIDs = ReachState.factory();
3087 Iterator<ReachTuple> rtItr = stateOld.iterator();
3088 while( rtItr.hasNext() ) {
3089 ReachTuple rtOld = rtItr.next();
3091 // never remove the inherent hrnID from a flagged region
3092 // because it is trivially satisfied
3093 if( hrn.isFlagged() ) {
3094 if( rtOld == rtException ) {
3099 // does boldB allow this hrnID?
3100 boolean foundState = false;
3101 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3102 while( incidentEdgeItr.hasNext() ) {
3103 RefEdge incidentEdge = incidentEdgeItr.next();
3105 Hashtable<RefEdge, ReachSet> B;
3106 if( rtOld.isOutOfContext() ) {
3107 B = boldBooc.get( rtOld.getHrnID() );
3110 if( !id2hrn.containsKey( rtOld.getHrnID() ) ) {
3111 // let symbols not in the graph get pruned
3115 B = boldBic.get( rtOld.getHrnID() );
3119 ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3120 if( boldB_rtOld_incident != null &&
3121 boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
3129 markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3133 // if there is nothing marked, just move on
3134 if( markedHrnIDs.isEmpty() ) {
3135 hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3142 // remove all marked hrnIDs and establish a change set that should
3143 // propagate backwards over edges from this node
3144 ReachState statePruned = ReachState.factory();
3145 rtItr = stateOld.iterator();
3146 while( rtItr.hasNext() ) {
3147 ReachTuple rtOld = rtItr.next();
3149 if( !markedHrnIDs.containsTuple( rtOld ) ) {
3150 statePruned = Canonical.add( statePruned, rtOld );
3153 assert !stateOld.equals( statePruned );
3155 hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3159 ChangeTuple ct = ChangeTuple.factory( stateOld,
3162 cts = Canonical.add( cts, ct );
3165 // throw change tuple set on all incident edges
3166 if( !cts.isEmpty() ) {
3167 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3168 while( incidentEdgeItr.hasNext() ) {
3169 RefEdge incidentEdge = incidentEdgeItr.next();
3171 edgesForPropagation.add( incidentEdge );
3173 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3174 edgePlannedChanges.put( incidentEdge, cts );
3176 edgePlannedChanges.put(
3178 Canonical.union( edgePlannedChanges.get( incidentEdge ),
3187 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3189 propagateTokensOverEdges( edgesForPropagation,
3193 // at the end of the 1st phase reference edges have
3194 // beta, betaNew that correspond to beta and betaR
3196 // commit beta<-betaNew, so beta=betaR and betaNew
3197 // will represent the beta' calculation in 2nd phase
3199 // commit alpha<-alphaNew because it won't change
3200 HashSet<RefEdge> res = new HashSet<RefEdge>();
3202 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3203 while( nodeItr.hasNext() ) {
3204 HeapRegionNode hrn = nodeItr.next();
3206 // as mentioned above, out-of-context nodes only serve
3207 // as sources of reach states for the sweep, not part
3209 if( hrn.isOutOfContext() ) {
3210 assert hrn.getAlphaNew().equals( rsetEmpty );
3212 hrn.applyAlphaNew();
3215 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3216 while( itrRes.hasNext() ) {
3217 res.add( itrRes.next() );
3223 Iterator<RefEdge> edgeItr = res.iterator();
3224 while( edgeItr.hasNext() ) {
3225 RefEdge edge = edgeItr.next();
3226 HeapRegionNode hrn = edge.getDst();
3228 // commit results of last phase
3229 if( edgesUpdated.contains( edge ) ) {
3230 edge.applyBetaNew();
3233 // compute intial condition of 2nd phase
3234 edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3240 // every edge in the graph is the initial workset
3241 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3242 while( !edgeWorkSet.isEmpty() ) {
3243 RefEdge edgePrime = edgeWorkSet.iterator().next();
3244 edgeWorkSet.remove( edgePrime );
3246 RefSrcNode rsn = edgePrime.getSrc();
3247 if( !(rsn instanceof HeapRegionNode) ) {
3250 HeapRegionNode hrn = (HeapRegionNode) rsn;
3252 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3253 while( itrEdge.hasNext() ) {
3254 RefEdge edge = itrEdge.next();
3256 ReachSet prevResult = edge.getBetaNew();
3257 assert prevResult != null;
3259 ReachSet intersection =
3260 Canonical.intersection( edge.getBeta(),
3261 edgePrime.getBetaNew()
3264 if( Canonical.unionORpreds( prevResult,
3271 Canonical.unionORpreds( prevResult,
3275 edgeWorkSet.add( edge );
3280 // commit beta' (beta<-betaNew)
3281 edgeItr = res.iterator();
3282 while( edgeItr.hasNext() ) {
3283 edgeItr.next().applyBetaNew();
3288 // a useful assertion for debugging:
3289 // every in-context tuple on any edge or
3290 // any node should name a node that is
3291 // part of the graph
3292 public boolean inContextTuplesInGraph() {
3293 Iterator hrnItr = id2hrn.entrySet().iterator();
3294 while( hrnItr.hasNext() ) {
3295 Map.Entry me = (Map.Entry) hrnItr.next();
3296 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3299 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3300 while( stateItr.hasNext() ) {
3301 ReachState state = stateItr.next();
3303 Iterator<ReachTuple> rtItr = state.iterator();
3304 while( rtItr.hasNext() ) {
3305 ReachTuple rt = rtItr.next();
3307 if( !rt.isOutOfContext() ) {
3308 if( !id2hrn.containsKey( rt.getHrnID() ) ) {
3309 System.out.println( rt.getHrnID()+" is missing" );
3317 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3318 while( edgeItr.hasNext() ) {
3319 RefEdge edge = edgeItr.next();
3321 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3322 while( stateItr.hasNext() ) {
3323 ReachState state = stateItr.next();
3325 Iterator<ReachTuple> rtItr = state.iterator();
3326 while( rtItr.hasNext() ) {
3327 ReachTuple rt = rtItr.next();
3329 if( !rt.isOutOfContext() ) {
3330 if( !id2hrn.containsKey( rt.getHrnID() ) ) {
3331 System.out.println( rt.getHrnID()+" is missing" );
3346 ////////////////////////////////////////////////////
3347 // high-level merge operations
3348 ////////////////////////////////////////////////////
3349 public void merge_sameMethodContext( ReachGraph rg ) {
3350 // when merging two graphs that abstract the heap
3351 // of the same method context, we just call the
3352 // basic merge operation
3356 public void merge_diffMethodContext( ReachGraph rg ) {
3357 // when merging graphs for abstract heaps in
3358 // different method contexts we should:
3359 // 1) age the allocation sites?
3363 ////////////////////////////////////////////////////
3364 // in merge() and equals() methods the suffix A
3365 // represents the passed in graph and the suffix
3366 // B refers to the graph in this object
3367 // Merging means to take the incoming graph A and
3368 // merge it into B, so after the operation graph B
3369 // is the final result.
3370 ////////////////////////////////////////////////////
3371 protected void merge( ReachGraph rg ) {
3378 mergeRefEdges ( rg );
3379 mergeAllocSites( rg );
3382 protected void mergeNodes( ReachGraph rg ) {
3384 // start with heap region nodes
3385 Set sA = rg.id2hrn.entrySet();
3386 Iterator iA = sA.iterator();
3387 while( iA.hasNext() ) {
3388 Map.Entry meA = (Map.Entry) iA.next();
3389 Integer idA = (Integer) meA.getKey();
3390 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3392 // if this graph doesn't have a node the
3393 // incoming graph has, allocate it
3394 if( !id2hrn.containsKey( idA ) ) {
3395 HeapRegionNode hrnB = hrnA.copy();
3396 id2hrn.put( idA, hrnB );
3399 // otherwise this is a node present in both graphs
3400 // so make the new reachability set a union of the
3401 // nodes' reachability sets
3402 HeapRegionNode hrnB = id2hrn.get( idA );
3403 hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3408 hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3415 // now add any variable nodes that are in graph B but
3417 sA = rg.td2vn.entrySet();
3419 while( iA.hasNext() ) {
3420 Map.Entry meA = (Map.Entry) iA.next();
3421 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3422 VariableNode lnA = (VariableNode) meA.getValue();
3424 // if the variable doesn't exist in B, allocate and add it
3425 VariableNode lnB = getVariableNodeFromTemp( tdA );
3429 protected void mergeRefEdges( ReachGraph rg ) {
3431 // between heap regions
3432 Set sA = rg.id2hrn.entrySet();
3433 Iterator iA = sA.iterator();
3434 while( iA.hasNext() ) {
3435 Map.Entry meA = (Map.Entry) iA.next();
3436 Integer idA = (Integer) meA.getKey();
3437 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3439 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3440 while( heapRegionsItrA.hasNext() ) {
3441 RefEdge edgeA = heapRegionsItrA.next();
3442 HeapRegionNode hrnChildA = edgeA.getDst();
3443 Integer idChildA = hrnChildA.getID();
3445 // at this point we know an edge in graph A exists
3446 // idA -> idChildA, does this exist in B?
3447 assert id2hrn.containsKey( idA );
3448 HeapRegionNode hrnB = id2hrn.get( idA );
3449 RefEdge edgeToMerge = null;
3451 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3452 while( heapRegionsItrB.hasNext() &&
3453 edgeToMerge == null ) {
3455 RefEdge edgeB = heapRegionsItrB.next();
3456 HeapRegionNode hrnChildB = edgeB.getDst();
3457 Integer idChildB = hrnChildB.getID();
3459 // don't use the RefEdge.equals() here because
3460 // we're talking about existence between graphs,
3461 // not intragraph equal
3462 if( idChildB.equals( idChildA ) &&
3463 edgeB.typeAndFieldEquals( edgeA ) ) {
3465 edgeToMerge = edgeB;
3469 // if the edge from A was not found in B,
3471 if( edgeToMerge == null ) {
3472 assert id2hrn.containsKey( idChildA );
3473 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3474 edgeToMerge = edgeA.copy();
3475 edgeToMerge.setSrc( hrnB );
3476 edgeToMerge.setDst( hrnChildB );
3477 addRefEdge( hrnB, hrnChildB, edgeToMerge );
3479 // otherwise, the edge already existed in both graphs
3480 // so merge their reachability sets
3482 // just replace this beta set with the union
3483 assert edgeToMerge != null;
3484 edgeToMerge.setBeta(
3485 Canonical.unionORpreds( edgeToMerge.getBeta(),
3489 edgeToMerge.setPreds(
3490 Canonical.join( edgeToMerge.getPreds(),
3498 // and then again from variable nodes
3499 sA = rg.td2vn.entrySet();
3501 while( iA.hasNext() ) {
3502 Map.Entry meA = (Map.Entry) iA.next();
3503 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3504 VariableNode vnA = (VariableNode) meA.getValue();
3506 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3507 while( heapRegionsItrA.hasNext() ) {
3508 RefEdge edgeA = heapRegionsItrA.next();
3509 HeapRegionNode hrnChildA = edgeA.getDst();
3510 Integer idChildA = hrnChildA.getID();
3512 // at this point we know an edge in graph A exists
3513 // tdA -> idChildA, does this exist in B?
3514 assert td2vn.containsKey( tdA );
3515 VariableNode vnB = td2vn.get( tdA );
3516 RefEdge edgeToMerge = null;
3518 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3519 while( heapRegionsItrB.hasNext() &&
3520 edgeToMerge == null ) {
3522 RefEdge edgeB = heapRegionsItrB.next();
3523 HeapRegionNode hrnChildB = edgeB.getDst();
3524 Integer idChildB = hrnChildB.getID();
3526 // don't use the RefEdge.equals() here because
3527 // we're talking about existence between graphs
3528 if( idChildB.equals( idChildA ) &&
3529 edgeB.typeAndFieldEquals( edgeA ) ) {
3531 edgeToMerge = edgeB;
3535 // if the edge from A was not found in B,
3537 if( edgeToMerge == null ) {
3538 assert id2hrn.containsKey( idChildA );
3539 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3540 edgeToMerge = edgeA.copy();
3541 edgeToMerge.setSrc( vnB );
3542 edgeToMerge.setDst( hrnChildB );
3543 addRefEdge( vnB, hrnChildB, edgeToMerge );
3545 // otherwise, the edge already existed in both graphs
3546 // so merge their reachability sets
3548 // just replace this beta set with the union
3549 edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3553 edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3562 protected void mergeAllocSites( ReachGraph rg ) {
3563 allocSites.addAll( rg.allocSites );
3568 static boolean dbgEquals = false;
3571 // it is necessary in the equals() member functions
3572 // to "check both ways" when comparing the data
3573 // structures of two graphs. For instance, if all
3574 // edges between heap region nodes in graph A are
3575 // present and equal in graph B it is not sufficient
3576 // to say the graphs are equal. Consider that there
3577 // may be edges in graph B that are not in graph A.
3578 // the only way to know that all edges in both graphs
3579 // are equally present is to iterate over both data
3580 // structures and compare against the other graph.
3581 public boolean equals( ReachGraph rg ) {
3585 System.out.println( "rg is null" );
3590 if( !areHeapRegionNodesEqual( rg ) ) {
3592 System.out.println( "hrn not equal" );
3597 if( !areVariableNodesEqual( rg ) ) {
3599 System.out.println( "vars not equal" );
3604 if( !areRefEdgesEqual( rg ) ) {
3606 System.out.println( "edges not equal" );
3611 // if everything is equal up to this point,
3612 // assert that allocSites is also equal--
3613 // this data is redundant but kept for efficiency
3614 assert allocSites.equals( rg.allocSites );
3620 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3622 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3626 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3633 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3635 Set sA = rgA.id2hrn.entrySet();
3636 Iterator iA = sA.iterator();
3637 while( iA.hasNext() ) {
3638 Map.Entry meA = (Map.Entry) iA.next();
3639 Integer idA = (Integer) meA.getKey();
3640 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3642 if( !rgB.id2hrn.containsKey( idA ) ) {
3646 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3647 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3655 protected boolean areVariableNodesEqual( ReachGraph rg ) {
3657 if( !areallVNinAalsoinBandequal( this, rg ) ) {
3661 if( !areallVNinAalsoinBandequal( rg, this ) ) {
3668 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3670 Set sA = rgA.td2vn.entrySet();
3671 Iterator iA = sA.iterator();
3672 while( iA.hasNext() ) {
3673 Map.Entry meA = (Map.Entry) iA.next();
3674 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3676 if( !rgB.td2vn.containsKey( tdA ) ) {
3685 protected boolean areRefEdgesEqual( ReachGraph rg ) {
3686 if( !areallREinAandBequal( this, rg ) ) {
3693 static protected boolean areallREinAandBequal( ReachGraph rgA,
3696 // check all the heap region->heap region edges
3697 Set sA = rgA.id2hrn.entrySet();
3698 Iterator iA = sA.iterator();
3699 while( iA.hasNext() ) {
3700 Map.Entry meA = (Map.Entry) iA.next();
3701 Integer idA = (Integer) meA.getKey();
3702 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3704 // we should have already checked that the same
3705 // heap regions exist in both graphs
3706 assert rgB.id2hrn.containsKey( idA );
3708 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3712 // then check every edge in B for presence in A, starting
3713 // from the same parent HeapRegionNode
3714 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3716 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3721 // then check all the variable->heap region edges
3722 sA = rgA.td2vn.entrySet();
3724 while( iA.hasNext() ) {
3725 Map.Entry meA = (Map.Entry) iA.next();
3726 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3727 VariableNode vnA = (VariableNode) meA.getValue();
3729 // we should have already checked that the same
3730 // label nodes exist in both graphs
3731 assert rgB.td2vn.containsKey( tdA );
3733 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3737 // then check every edge in B for presence in A, starting
3738 // from the same parent VariableNode
3739 VariableNode vnB = rgB.td2vn.get( tdA );
3741 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3750 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3754 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3755 while( itrA.hasNext() ) {
3756 RefEdge edgeA = itrA.next();
3757 HeapRegionNode hrnChildA = edgeA.getDst();
3758 Integer idChildA = hrnChildA.getID();
3760 assert rgB.id2hrn.containsKey( idChildA );
3762 // at this point we know an edge in graph A exists
3763 // rnA -> idChildA, does this exact edge exist in B?
3764 boolean edgeFound = false;
3766 RefSrcNode rnB = null;
3767 if( rnA instanceof HeapRegionNode ) {
3768 HeapRegionNode hrnA = (HeapRegionNode) rnA;
3769 rnB = rgB.id2hrn.get( hrnA.getID() );
3771 VariableNode vnA = (VariableNode) rnA;
3772 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3775 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3776 while( itrB.hasNext() ) {
3777 RefEdge edgeB = itrB.next();
3778 HeapRegionNode hrnChildB = edgeB.getDst();
3779 Integer idChildB = hrnChildB.getID();
3781 if( idChildA.equals( idChildB ) &&
3782 edgeA.typeAndFieldEquals( edgeB ) ) {
3784 // there is an edge in the right place with the right field,
3785 // but do they have the same attributes?
3786 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3787 edgeA.equalsPreds( edgeB )
3804 // this analysis no longer has the "match anything"
3805 // type which was represented by null
3806 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3807 TypeDescriptor td2 ) {
3811 if( td1.isNull() ) {
3814 if( td2.isNull() ) {
3817 return typeUtil.mostSpecific( td1, td2 );
3820 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3822 TypeDescriptor td3 ) {
3824 return mostSpecificType( td1,
3825 mostSpecificType( td2, td3 )
3829 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3832 TypeDescriptor td4 ) {
3834 return mostSpecificType( mostSpecificType( td1, td2 ),
3835 mostSpecificType( td3, td4 )
3839 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3840 TypeDescriptor possibleChild ) {
3841 assert possibleSuper != null;
3842 assert possibleChild != null;
3844 if( possibleSuper.isNull() ||
3845 possibleChild.isNull() ) {
3849 return typeUtil.isSuperorType( possibleSuper, possibleChild );
3853 protected boolean hasMatchingField( HeapRegionNode src,
3856 TypeDescriptor tdSrc = src.getType();
3857 assert tdSrc != null;
3859 if( tdSrc.isArray() ) {
3860 TypeDescriptor td = edge.getType();
3863 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3864 assert tdSrcDeref != null;
3866 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3870 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3873 // if it's not a class, it doesn't have any fields to match
3874 if( !tdSrc.isClass() ) {
3878 ClassDescriptor cd = tdSrc.getClassDesc();
3879 while( cd != null ) {
3880 Iterator fieldItr = cd.getFields();
3882 while( fieldItr.hasNext() ) {
3883 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3885 if( fd.getType().equals( edge.getType() ) &&
3886 fd.getSymbol().equals( edge.getField() ) ) {
3891 cd = cd.getSuperDesc();
3894 // otherwise it is a class with fields
3895 // but we didn't find a match
3899 protected boolean hasMatchingType( RefEdge edge,
3900 HeapRegionNode dst ) {
3902 // if the region has no type, matches everything
3903 TypeDescriptor tdDst = dst.getType();
3904 assert tdDst != null;
3906 // if the type is not a class or an array, don't
3907 // match because primitives are copied, no aliases
3908 ClassDescriptor cdDst = tdDst.getClassDesc();
3909 if( cdDst == null && !tdDst.isArray() ) {
3913 // if the edge type is null, it matches everything
3914 TypeDescriptor tdEdge = edge.getType();
3915 assert tdEdge != null;
3917 return typeUtil.isSuperorType( tdEdge, tdDst );
3922 // the default signature for quick-and-dirty debugging
3923 public void writeGraph( String graphName ) {
3924 writeGraph( graphName,
3925 true, // write labels
3926 true, // label select
3927 true, // prune garbage
3928 true, // hide subset reachability
3929 true, // hide edge taints
3930 null // in-context boundary
3934 public void writeGraph( String graphName,
3935 boolean writeLabels,
3936 boolean labelSelect,
3937 boolean pruneGarbage,
3938 boolean hideSubsetReachability,
3939 boolean hideEdgeTaints
3941 writeGraph( graphName,
3945 hideSubsetReachability,
3950 public void writeGraph( String graphName,
3951 boolean writeLabels,
3952 boolean labelSelect,
3953 boolean pruneGarbage,
3954 boolean hideSubsetReachability,
3955 boolean hideEdgeTaints,
3956 Set<Integer> callerNodeIDsCopiedToCallee
3960 // remove all non-word characters from the graph name so
3961 // the filename and identifier in dot don't cause errors
3962 graphName = graphName.replaceAll( "[\\W]", "" );
3965 new BufferedWriter( new FileWriter( graphName+".dot" ) );
3967 bw.write( "digraph "+graphName+" {\n" );
3970 // this is an optional step to form the callee-reachable
3971 // "cut-out" into a DOT cluster for visualization
3972 if( callerNodeIDsCopiedToCallee != null ) {
3974 bw.write( " subgraph cluster0 {\n" );
3975 bw.write( " color=blue;\n" );
3977 Iterator i = id2hrn.entrySet().iterator();
3978 while( i.hasNext() ) {
3979 Map.Entry me = (Map.Entry) i.next();
3980 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3982 if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3983 bw.write( " "+hrn.toString()+
3984 hrn.toStringDOT( hideSubsetReachability )+
3994 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3996 // then visit every heap region node
3997 Iterator i = id2hrn.entrySet().iterator();
3998 while( i.hasNext() ) {
3999 Map.Entry me = (Map.Entry) i.next();
4000 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4002 // only visit nodes worth writing out--for instance
4003 // not every node at an allocation is referenced
4004 // (think of it as garbage-collected), etc.
4005 if( !pruneGarbage ||
4006 hrn.isOutOfContext()
4009 if( !visited.contains( hrn ) ) {
4010 traverseHeapRegionNodes( hrn,
4014 hideSubsetReachability,
4016 callerNodeIDsCopiedToCallee );
4021 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
4024 // then visit every label node, useful for debugging
4026 i = td2vn.entrySet().iterator();
4027 while( i.hasNext() ) {
4028 Map.Entry me = (Map.Entry) i.next();
4029 VariableNode vn = (VariableNode) me.getValue();
4032 String labelStr = vn.getTempDescriptorString();
4033 if( labelStr.startsWith( "___temp" ) ||
4034 labelStr.startsWith( "___dst" ) ||
4035 labelStr.startsWith( "___srctmp" ) ||
4036 labelStr.startsWith( "___neverused" )
4042 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4043 while( heapRegionsItr.hasNext() ) {
4044 RefEdge edge = heapRegionsItr.next();
4045 HeapRegionNode hrn = edge.getDst();
4047 if( !visited.contains( hrn ) ) {
4048 traverseHeapRegionNodes( hrn,
4052 hideSubsetReachability,
4054 callerNodeIDsCopiedToCallee );
4057 bw.write( " "+vn.toString()+
4058 " -> "+hrn.toString()+
4059 edge.toStringDOT( hideSubsetReachability, "" )+
4068 } catch( IOException e ) {
4069 throw new Error( "Error writing out DOT graph "+graphName );
4073 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
4076 Set<HeapRegionNode> visited,
4077 boolean hideSubsetReachability,
4078 boolean hideEdgeTaints,
4079 Set<Integer> callerNodeIDsCopiedToCallee
4080 ) throws java.io.IOException {
4082 if( visited.contains( hrn ) ) {
4087 // if we're drawing the callee-view subgraph, only
4088 // write out the node info if it hasn't already been
4090 if( callerNodeIDsCopiedToCallee == null ||
4091 !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
4093 bw.write( " "+hrn.toString()+
4094 hrn.toStringDOT( hideSubsetReachability )+
4098 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4099 while( childRegionsItr.hasNext() ) {
4100 RefEdge edge = childRegionsItr.next();
4101 HeapRegionNode hrnChild = edge.getDst();
4103 if( callerNodeIDsCopiedToCallee != null &&
4104 (edge.getSrc() instanceof HeapRegionNode) ) {
4105 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4106 if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
4107 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4109 bw.write( " "+hrn.toString()+
4110 " -> "+hrnChild.toString()+
4111 edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
4113 } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
4114 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4116 bw.write( " "+hrn.toString()+
4117 " -> "+hrnChild.toString()+
4118 edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
4121 bw.write( " "+hrn.toString()+
4122 " -> "+hrnChild.toString()+
4123 edge.toStringDOT( hideSubsetReachability, "" )+
4127 bw.write( " "+hrn.toString()+
4128 " -> "+hrnChild.toString()+
4129 edge.toStringDOT( hideSubsetReachability, "" )+
4133 traverseHeapRegionNodes( hrnChild,
4137 hideSubsetReachability,
4139 callerNodeIDsCopiedToCallee );
4147 public Set<HeapRegionNode> findCommonReachableNodes( ReachSet proofOfSharing ) {
4149 Set<HeapRegionNode> exhibitProofState =
4150 new HashSet<HeapRegionNode>();
4152 Iterator hrnItr = id2hrn.entrySet().iterator();
4153 while( hrnItr.hasNext() ) {
4154 Map.Entry me = (Map.Entry) hrnItr.next();
4155 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4157 ReachSet intersection =
4158 Canonical.intersection( proofOfSharing,
4161 if( !intersection.isEmpty() ) {
4162 assert !hrn.isOutOfContext();
4163 exhibitProofState.add( hrn );
4167 return exhibitProofState;
4171 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4172 HeapRegionNode hrn2) {
4173 assert hrn1 != null;
4174 assert hrn2 != null;
4176 assert !hrn1.isOutOfContext();
4177 assert !hrn2.isOutOfContext();
4179 assert belongsToThis( hrn1 );
4180 assert belongsToThis( hrn2 );
4182 assert !hrn1.getID().equals( hrn2.getID() );
4185 // then get the various tokens for these heap regions
4187 ReachTuple.factory( hrn1.getID(),
4188 !hrn1.isSingleObject(), // multi?
4189 ReachTuple.ARITY_ONE,
4192 ReachTuple h1star = null;
4193 if( !hrn1.isSingleObject() ) {
4195 ReachTuple.factory( hrn1.getID(),
4196 !hrn1.isSingleObject(),
4197 ReachTuple.ARITY_ZEROORMORE,
4202 ReachTuple.factory( hrn2.getID(),
4203 !hrn2.isSingleObject(),
4204 ReachTuple.ARITY_ONE,
4207 ReachTuple h2star = null;
4208 if( !hrn2.isSingleObject() ) {
4210 ReachTuple.factory( hrn2.getID(),
4211 !hrn2.isSingleObject(),
4212 ReachTuple.ARITY_ZEROORMORE,
4216 // then get the merged beta of all out-going edges from these heap
4219 ReachSet beta1 = ReachSet.factory();
4220 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4221 while (itrEdge.hasNext()) {
4222 RefEdge edge = itrEdge.next();
4223 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4226 ReachSet beta2 = ReachSet.factory();
4227 itrEdge = hrn2.iteratorToReferencees();
4228 while (itrEdge.hasNext()) {
4229 RefEdge edge = itrEdge.next();
4230 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4233 ReachSet proofOfSharing = ReachSet.factory();
4236 Canonical.unionORpreds( proofOfSharing,
4237 beta1.getStatesWithBoth( h1, h2 )
4240 Canonical.unionORpreds( proofOfSharing,
4241 beta2.getStatesWithBoth( h1, h2 )
4244 if( !hrn1.isSingleObject() ) {
4246 Canonical.unionORpreds( proofOfSharing,
4247 beta1.getStatesWithBoth( h1star, h2 )
4250 Canonical.unionORpreds( proofOfSharing,
4251 beta2.getStatesWithBoth( h1star, h2 )
4255 if( !hrn2.isSingleObject() ) {
4257 Canonical.unionORpreds( proofOfSharing,
4258 beta1.getStatesWithBoth( h1, h2star )
4261 Canonical.unionORpreds( proofOfSharing,
4262 beta2.getStatesWithBoth( h1, h2star )
4266 if( !hrn1.isSingleObject() &&
4267 !hrn2.isSingleObject()
4270 Canonical.unionORpreds( proofOfSharing,
4271 beta1.getStatesWithBoth( h1star, h2star )
4274 Canonical.unionORpreds( proofOfSharing,
4275 beta2.getStatesWithBoth( h1star, h2star )
4279 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4280 if( !proofOfSharing.isEmpty() ) {
4281 common = findCommonReachableNodes( proofOfSharing );
4282 if( !DISABLE_STRONG_UPDATES &&
4283 !DISABLE_GLOBAL_SWEEP
4285 assert !common.isEmpty();
4292 // this version of the above method checks whether there is sharing
4293 // among the objects in a summary node
4294 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4296 assert hrn.isNewSummary();
4297 assert !hrn.isOutOfContext();
4298 assert belongsToThis( hrn );
4301 ReachTuple.factory( hrn.getID(),
4303 ReachTuple.ARITY_ZEROORMORE,
4306 // then get the merged beta of all out-going edges from
4309 ReachSet beta = ReachSet.factory();
4310 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4311 while (itrEdge.hasNext()) {
4312 RefEdge edge = itrEdge.next();
4313 beta = Canonical.unionORpreds(beta, edge.getBeta());
4316 ReachSet proofOfSharing = ReachSet.factory();
4319 Canonical.unionORpreds( proofOfSharing,
4320 beta.getStatesWithBoth( hstar, hstar )
4323 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4324 if( !proofOfSharing.isEmpty() ) {
4325 common = findCommonReachableNodes( proofOfSharing );
4326 if( !DISABLE_STRONG_UPDATES &&
4327 !DISABLE_GLOBAL_SWEEP
4329 assert !common.isEmpty();
4337 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4338 Integer paramIndex1,
4339 Integer paramIndex2) {
4341 // get parameter's heap regions
4342 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4343 assert this.hasVariable( paramTemp1 );
4344 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
4347 if( !(paramVar1.getNumReferencees() == 1) ) {
4348 System.out.println( "\n fm="+fm+"\n param="+paramTemp1 );
4349 writeGraph( "whatup" );
4353 assert paramVar1.getNumReferencees() == 1;
4354 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
4355 HeapRegionNode hrnParam1 = paramEdge1.getDst();
4357 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4358 assert this.hasVariable( paramTemp2 );
4359 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
4361 if( !(paramVar2.getNumReferencees() == 1) ) {
4362 System.out.println( "\n fm="+fm+"\n param="+paramTemp2 );
4363 writeGraph( "whatup" );
4366 assert paramVar2.getNumReferencees() == 1;
4367 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
4368 HeapRegionNode hrnParam2 = paramEdge2.getDst();
4370 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4371 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4376 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4380 // get parameter's heap regions
4381 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4382 assert this.hasVariable( paramTemp );
4383 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
4384 assert paramVar.getNumReferencees() == 1;
4385 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
4386 HeapRegionNode hrnParam = paramEdge.getDst();
4389 HeapRegionNode hrnSummary=null;
4390 if(id2hrn.containsKey(as.getSummary())){
4391 // if summary node doesn't exist, ignore this case
4392 hrnSummary = id2hrn.get(as.getSummary());
4393 assert hrnSummary != null;
4396 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4397 if(hrnSummary!=null){
4398 common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4401 // check for other nodes
4402 for (int i = 0; i < as.getAllocationDepth(); ++i) {
4404 assert id2hrn.containsKey(as.getIthOldest(i));
4405 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4406 assert hrnIthOldest != null;
4408 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4415 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4418 // get summary node 1's alpha
4419 Integer idSum1 = as1.getSummary();
4420 HeapRegionNode hrnSum1=null;
4421 if(id2hrn.containsKey(idSum1)){
4422 hrnSum1 = id2hrn.get(idSum1);
4425 // get summary node 2's alpha
4426 Integer idSum2 = as2.getSummary();
4427 HeapRegionNode hrnSum2=null;
4428 if(id2hrn.containsKey(idSum2)){
4429 hrnSum2 = id2hrn.get(idSum2);
4432 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4433 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2){
4434 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4438 // ask if objects from this summary share among each other
4439 common.addAll(mayReachSharedObjects(hrnSum1));
4442 // check sum2 against alloc1 nodes
4444 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4445 Integer idI1 = as1.getIthOldest(i);
4446 assert id2hrn.containsKey(idI1);
4447 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4448 assert hrnI1 != null;
4449 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4452 // also ask if objects from this summary share among each other
4453 common.addAll(mayReachSharedObjects(hrnSum2));
4456 // check sum1 against alloc2 nodes
4457 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4458 Integer idI2 = as2.getIthOldest(i);
4459 assert id2hrn.containsKey(idI2);
4460 HeapRegionNode hrnI2 = id2hrn.get(idI2);
4461 assert hrnI2 != null;
4464 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4467 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4468 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4469 Integer idI1 = as1.getIthOldest(j);
4471 // if these are the same site, don't look for the same token, no
4473 // different tokens of the same site could alias together though
4474 if (idI1.equals(idI2)) {
4478 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4480 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));