1 package Analysis.Disjoint;
5 import Util.UtilAlgorithms;
9 public class ReachGraph {
11 // use to disable improvements for comparison
12 protected static final boolean DISABLE_STRONG_UPDATES = false;
13 protected static final boolean DISABLE_GLOBAL_SWEEP = true;
15 // a special out-of-scope temp
16 protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
18 // some frequently used reachability constants
19 protected static final ReachState rstateEmpty = ReachState.factory();
20 protected static final ReachSet rsetEmpty = ReachSet.factory();
21 protected static final ReachSet rsetWithEmptyState = ReachSet.factory( rstateEmpty );
23 // predicate constants
24 protected static final ExistPred predTrue = ExistPred.factory(); // if no args, true
25 protected static final ExistPredSet predsEmpty = ExistPredSet.factory();
26 protected static final ExistPredSet predsTrue = ExistPredSet.factory( predTrue );
29 // from DisjointAnalysis for convenience
30 protected static int allocationDepth = -1;
31 protected static TypeUtil typeUtil = null;
34 // variable and heap region nodes indexed by unique ID
35 public Hashtable<Integer, HeapRegionNode> id2hrn;
36 public Hashtable<TempDescriptor, VariableNode > td2vn;
38 // convenient set of alloc sites for all heap regions
39 // present in the graph without having to search
40 public HashSet<AllocSite> allocSites;
43 id2hrn = new Hashtable<Integer, HeapRegionNode>();
44 td2vn = new Hashtable<TempDescriptor, VariableNode >();
45 allocSites = new HashSet<AllocSite>();
49 // temp descriptors are globally unique and map to
50 // exactly one variable node, easy
51 protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
54 if( !td2vn.containsKey( td ) ) {
55 td2vn.put( td, new VariableNode( td ) );
58 return td2vn.get( td );
61 public boolean hasVariable( TempDescriptor td ) {
62 return td2vn.containsKey( td );
66 // the reason for this method is to have the option
67 // of creating new heap regions with specific IDs, or
68 // duplicating heap regions with specific IDs (especially
69 // in the merge() operation) or to create new heap
70 // regions with a new unique ID
71 protected HeapRegionNode
72 createNewHeapRegionNode( Integer id,
73 boolean isSingleObject,
76 boolean isOutOfContext,
85 boolean markForAnalysis = isFlagged;
87 TypeDescriptor typeToUse = null;
88 if( allocSite != null ) {
89 typeToUse = allocSite.getType();
90 allocSites.add( allocSite );
95 if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
96 markForAnalysis = true;
100 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
103 if( inherent == null ) {
104 if( markForAnalysis ) {
108 ReachTuple.factory( id,
115 inherent = rsetWithEmptyState;
119 if( alpha == null ) {
123 if( preds == null ) {
124 // TODO: do this right? For out-of-context nodes?
125 preds = ExistPredSet.factory();
128 HeapRegionNode hrn = new HeapRegionNode( id,
139 id2hrn.put( id, hrn );
145 ////////////////////////////////////////////////
147 // Low-level referencee and referencer methods
149 // These methods provide the lowest level for
150 // creating references between reachability nodes
151 // and handling the details of maintaining both
152 // list of referencers and referencees.
154 ////////////////////////////////////////////////
155 protected void addRefEdge( RefSrcNode referencer,
156 HeapRegionNode referencee,
158 assert referencer != null;
159 assert referencee != null;
161 assert edge.getSrc() == referencer;
162 assert edge.getDst() == referencee;
164 // edges are getting added twice to graphs now, the
165 // kind that should have abstract facts merged--use
166 // this check to prevent that
167 assert referencer.getReferenceTo( referencee,
172 referencer.addReferencee( edge );
173 referencee.addReferencer( edge );
176 protected void removeRefEdge( RefEdge e ) {
177 removeRefEdge( e.getSrc(),
183 protected void removeRefEdge( RefSrcNode referencer,
184 HeapRegionNode referencee,
187 assert referencer != null;
188 assert referencee != null;
190 RefEdge edge = referencer.getReferenceTo( referencee,
194 assert edge == referencee.getReferenceFrom( referencer,
198 referencer.removeReferencee( edge );
199 referencee.removeReferencer( edge );
202 protected void clearRefEdgesFrom( RefSrcNode referencer,
205 boolean removeAll ) {
206 assert referencer != null;
208 // get a copy of the set to iterate over, otherwise
209 // we will be trying to take apart the set as we
210 // are iterating over it, which won't work
211 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
212 while( i.hasNext() ) {
213 RefEdge edge = i.next();
216 (edge.typeEquals( type ) && edge.fieldEquals( field ))
219 HeapRegionNode referencee = edge.getDst();
221 removeRefEdge( referencer,
229 protected void clearRefEdgesTo( HeapRegionNode referencee,
232 boolean removeAll ) {
233 assert referencee != null;
235 // get a copy of the set to iterate over, otherwise
236 // we will be trying to take apart the set as we
237 // are iterating over it, which won't work
238 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
239 while( i.hasNext() ) {
240 RefEdge edge = i.next();
243 (edge.typeEquals( type ) && edge.fieldEquals( field ))
246 RefSrcNode referencer = edge.getSrc();
248 removeRefEdge( referencer,
256 protected void clearNonVarRefEdgesTo( HeapRegionNode referencee ) {
257 assert referencee != null;
259 // get a copy of the set to iterate over, otherwise
260 // we will be trying to take apart the set as we
261 // are iterating over it, which won't work
262 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
263 while( i.hasNext() ) {
264 RefEdge edge = i.next();
265 RefSrcNode referencer = edge.getSrc();
266 if( !(referencer instanceof VariableNode) ) {
267 removeRefEdge( referencer,
276 ////////////////////////////////////////////////////
278 // Assignment Operation Methods
280 // These methods are high-level operations for
281 // modeling program assignment statements using
282 // the low-level reference create/remove methods
285 ////////////////////////////////////////////////////
287 public void assignTempXEqualToTempY( TempDescriptor x,
289 assignTempXEqualToCastedTempY( x, y, null );
292 public void assignTempXEqualToCastedTempY( TempDescriptor x,
294 TypeDescriptor tdCast ) {
296 VariableNode lnX = getVariableNodeFromTemp( x );
297 VariableNode lnY = getVariableNodeFromTemp( y );
299 clearRefEdgesFrom( lnX, null, null, true );
301 // note it is possible that the types of temps in the
302 // flat node to analyze will reveal that some typed
303 // edges in the reachability graph are impossible
304 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
306 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
307 while( itrYhrn.hasNext() ) {
308 RefEdge edgeY = itrYhrn.next();
309 HeapRegionNode referencee = edgeY.getDst();
310 RefEdge edgeNew = edgeY.copy();
312 if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
313 impossibleEdges.add( edgeY );
317 edgeNew.setSrc( lnX );
319 if( tdCast == null ) {
320 edgeNew.setType( mostSpecificType( y.getType(),
326 edgeNew.setType( mostSpecificType( y.getType(),
328 referencee.getType(),
334 edgeNew.setField( null );
336 addRefEdge( lnX, referencee, edgeNew );
339 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
340 while( itrImp.hasNext() ) {
341 RefEdge edgeImp = itrImp.next();
342 removeRefEdge( edgeImp );
347 public void assignTempXEqualToTempYFieldF( TempDescriptor x,
349 FieldDescriptor f ) {
350 VariableNode lnX = getVariableNodeFromTemp( x );
351 VariableNode lnY = getVariableNodeFromTemp( y );
353 clearRefEdgesFrom( lnX, null, null, true );
355 // note it is possible that the types of temps in the
356 // flat node to analyze will reveal that some typed
357 // edges in the reachability graph are impossible
358 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
360 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
361 while( itrYhrn.hasNext() ) {
362 RefEdge edgeY = itrYhrn.next();
363 HeapRegionNode hrnY = edgeY.getDst();
364 ReachSet betaY = edgeY.getBeta();
366 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
367 while( itrHrnFhrn.hasNext() ) {
368 RefEdge edgeHrn = itrHrnFhrn.next();
369 HeapRegionNode hrnHrn = edgeHrn.getDst();
370 ReachSet betaHrn = edgeHrn.getBeta();
372 // prune edges that are not a matching field
373 if( edgeHrn.getType() != null &&
374 !edgeHrn.getField().equals( f.getSymbol() )
379 // check for impossible edges
380 if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
381 impossibleEdges.add( edgeHrn );
385 TypeDescriptor tdNewEdge =
386 mostSpecificType( edgeHrn.getType(),
390 RefEdge edgeNew = new RefEdge( lnX,
394 Canonical.intersection( betaY, betaHrn ),
398 addRefEdge( lnX, hrnHrn, edgeNew );
402 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
403 while( itrImp.hasNext() ) {
404 RefEdge edgeImp = itrImp.next();
405 removeRefEdge( edgeImp );
408 // anytime you might remove edges between heap regions
409 // you must global sweep to clean up broken reachability
410 if( !impossibleEdges.isEmpty() ) {
411 if( !DISABLE_GLOBAL_SWEEP ) {
418 public void assignTempXFieldFEqualToTempY( TempDescriptor x,
422 VariableNode lnX = getVariableNodeFromTemp( x );
423 VariableNode lnY = getVariableNodeFromTemp( y );
425 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
426 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
428 // note it is possible that the types of temps in the
429 // flat node to analyze will reveal that some typed
430 // edges in the reachability graph are impossible
431 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
433 // first look for possible strong updates and remove those edges
434 boolean strongUpdate = false;
436 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
437 while( itrXhrn.hasNext() ) {
438 RefEdge edgeX = itrXhrn.next();
439 HeapRegionNode hrnX = edgeX.getDst();
441 // we can do a strong update here if one of two cases holds
443 f != DisjointAnalysis.getArrayField( f.getType() ) &&
444 ( (hrnX.getNumReferencers() == 1) || // case 1
445 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
448 if( !DISABLE_STRONG_UPDATES ) {
450 clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
455 // then do all token propagation
456 itrXhrn = lnX.iteratorToReferencees();
457 while( itrXhrn.hasNext() ) {
458 RefEdge edgeX = itrXhrn.next();
459 HeapRegionNode hrnX = edgeX.getDst();
460 ReachSet betaX = edgeX.getBeta();
461 ReachSet R = Canonical.intersection( hrnX.getAlpha(),
465 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
466 while( itrYhrn.hasNext() ) {
467 RefEdge edgeY = itrYhrn.next();
468 HeapRegionNode hrnY = edgeY.getDst();
469 ReachSet O = edgeY.getBeta();
471 // check for impossible edges
472 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
473 impossibleEdges.add( edgeY );
477 // propagate tokens over nodes starting from hrnSrc, and it will
478 // take care of propagating back up edges from any touched nodes
479 ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
480 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
482 // then propagate back just up the edges from hrn
483 ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
484 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
486 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
487 new Hashtable<RefEdge, ChangeSet>();
489 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
490 while( referItr.hasNext() ) {
491 RefEdge edgeUpstream = referItr.next();
492 todoEdges.add( edgeUpstream );
493 edgePlannedChanges.put( edgeUpstream, Cx );
496 propagateTokensOverEdges( todoEdges,
503 // apply the updates to reachability
504 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
505 while( nodeItr.hasNext() ) {
506 nodeItr.next().applyAlphaNew();
509 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
510 while( edgeItr.hasNext() ) {
511 edgeItr.next().applyBetaNew();
515 // then go back through and add the new edges
516 itrXhrn = lnX.iteratorToReferencees();
517 while( itrXhrn.hasNext() ) {
518 RefEdge edgeX = itrXhrn.next();
519 HeapRegionNode hrnX = edgeX.getDst();
521 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
522 while( itrYhrn.hasNext() ) {
523 RefEdge edgeY = itrYhrn.next();
524 HeapRegionNode hrnY = edgeY.getDst();
526 // skip impossible edges here, we already marked them
527 // when computing reachability propagations above
528 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
532 // prepare the new reference edge hrnX.f -> hrnY
533 TypeDescriptor tdNewEdge =
534 mostSpecificType( y.getType(),
539 RefEdge edgeNew = new RefEdge( hrnX,
543 Canonical.pruneBy( edgeY.getBeta(),
549 // look to see if an edge with same field exists
550 // and merge with it, otherwise just add the edge
551 RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
555 if( edgeExisting != null ) {
556 edgeExisting.setBeta(
557 Canonical.union( edgeExisting.getBeta(),
561 edgeExisting.setPreds(
562 Canonical.join( edgeExisting.getPreds(),
568 addRefEdge( hrnX, hrnY, edgeNew );
573 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
574 while( itrImp.hasNext() ) {
575 RefEdge edgeImp = itrImp.next();
576 removeRefEdge( edgeImp );
579 // if there was a strong update, make sure to improve
580 // reachability with a global sweep
581 if( strongUpdate || !impossibleEdges.isEmpty() ) {
582 if( !DISABLE_GLOBAL_SWEEP ) {
589 public void assignReturnEqualToTemp( TempDescriptor x ) {
591 VariableNode lnR = getVariableNodeFromTemp( tdReturn );
592 VariableNode lnX = getVariableNodeFromTemp( x );
594 clearRefEdgesFrom( lnR, null, null, true );
596 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
597 while( itrXhrn.hasNext() ) {
598 RefEdge edgeX = itrXhrn.next();
599 HeapRegionNode referencee = edgeX.getDst();
600 RefEdge edgeNew = edgeX.copy();
601 edgeNew.setSrc( lnR );
603 addRefEdge( lnR, referencee, edgeNew );
608 public void assignTempEqualToNewAlloc( TempDescriptor x,
615 // after the age operation the newest (or zero-ith oldest)
616 // node associated with the allocation site should have
617 // no references to it as if it were a newly allocated
619 Integer idNewest = as.getIthOldest( 0 );
620 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
621 assert hrnNewest != null;
623 VariableNode lnX = getVariableNodeFromTemp( x );
624 clearRefEdgesFrom( lnX, null, null, true );
626 // make a new reference to allocated node
627 TypeDescriptor type = as.getType();
630 new RefEdge( lnX, // source
634 hrnNewest.getAlpha(), // beta
635 predsTrue // predicates
638 addRefEdge( lnX, hrnNewest, edgeNew );
642 // use the allocation site (unique to entire analysis) to
643 // locate the heap region nodes in this reachability graph
644 // that should be aged. The process models the allocation
645 // of new objects and collects all the oldest allocations
646 // in a summary node to allow for a finite analysis
648 // There is an additional property of this method. After
649 // running it on a particular reachability graph (many graphs
650 // may have heap regions related to the same allocation site)
651 // the heap region node objects in this reachability graph will be
652 // allocated. Therefore, after aging a graph for an allocation
653 // site, attempts to retrieve the heap region nodes using the
654 // integer id's contained in the allocation site should always
655 // return non-null heap regions.
656 public void age( AllocSite as ) {
658 // keep track of allocation sites that are represented
659 // in this graph for efficiency with other operations
660 allocSites.add( as );
662 // if there is a k-th oldest node, it merges into
664 Integer idK = as.getOldest();
665 if( id2hrn.containsKey( idK ) ) {
666 HeapRegionNode hrnK = id2hrn.get( idK );
668 // retrieve the summary node, or make it
670 HeapRegionNode hrnSummary = getSummaryNode( as, false );
672 mergeIntoSummary( hrnK, hrnSummary );
675 // move down the line of heap region nodes
676 // clobbering the ith and transferring all references
677 // to and from i-1 to node i.
678 for( int i = allocationDepth - 1; i > 0; --i ) {
680 // only do the transfer if the i-1 node exists
681 Integer idImin1th = as.getIthOldest( i - 1 );
682 if( id2hrn.containsKey( idImin1th ) ) {
683 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
684 if( hrnImin1.isWiped() ) {
685 // there is no info on this node, just skip
689 // either retrieve or make target of transfer
690 HeapRegionNode hrnI = getIthNode( as, i, false );
692 transferOnto( hrnImin1, hrnI );
697 // as stated above, the newest node should have had its
698 // references moved over to the second oldest, so we wipe newest
699 // in preparation for being the new object to assign something to
700 HeapRegionNode hrn0 = getIthNode( as, 0, false );
701 wipeOut( hrn0, true );
703 // now tokens in reachability sets need to "age" also
704 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
705 while( itrAllVariableNodes.hasNext() ) {
706 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
707 VariableNode ln = (VariableNode) me.getValue();
709 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
710 while( itrEdges.hasNext() ) {
711 ageTuplesFrom( as, itrEdges.next() );
715 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
716 while( itrAllHRNodes.hasNext() ) {
717 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
718 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
720 ageTuplesFrom( as, hrnToAge );
722 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
723 while( itrEdges.hasNext() ) {
724 ageTuplesFrom( as, itrEdges.next() );
729 // after tokens have been aged, reset newest node's reachability
730 // and a brand new node has a "true" predicate
731 hrn0.setAlpha( hrn0.getInherent() );
732 hrn0.setPreds( predsTrue );
736 // either retrieve or create the needed heap region node
737 protected HeapRegionNode getSummaryNode( AllocSite as,
742 idSummary = as.getSummaryShadow();
744 idSummary = as.getSummary();
747 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
749 if( hrnSummary == null ) {
751 boolean hasFlags = false;
752 if( as.getType().isClass() ) {
753 hasFlags = as.getType().getClassDesc().hasFlags();
757 hasFlags = as.getFlag();
760 String strDesc = as.toStringForDOT()+"\\nsummary";
762 strDesc += " shadow";
766 createNewHeapRegionNode( idSummary, // id or null to generate a new one
767 false, // single object?
769 hasFlags, // flagged?
770 false, // out-of-context?
771 as.getType(), // type
772 as, // allocation site
773 null, // inherent reach
774 null, // current reach
775 predsEmpty, // predicates
776 strDesc // description
783 // either retrieve or create the needed heap region node
784 protected HeapRegionNode getIthNode( AllocSite as,
790 idIth = as.getIthOldestShadow( i );
792 idIth = as.getIthOldest( i );
795 HeapRegionNode hrnIth = id2hrn.get( idIth );
797 if( hrnIth == null ) {
799 boolean hasFlags = false;
800 if( as.getType().isClass() ) {
801 hasFlags = as.getType().getClassDesc().hasFlags();
805 hasFlags = as.getFlag();
808 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
810 strDesc += " shadow";
813 hrnIth = createNewHeapRegionNode( idIth, // id or null to generate a new one
814 true, // single object?
816 hasFlags, // flagged?
817 false, // out-of-context?
818 as.getType(), // type
819 as, // allocation site
820 null, // inherent reach
821 null, // current reach
822 predsEmpty, // predicates
823 strDesc // description
831 // used to assert that the given node object
832 // belongs to THIS graph instance, some gross bugs
833 // have popped up where a node from one graph works
834 // itself into another
835 public boolean belongsToThis( HeapRegionNode hrn ) {
836 return this.id2hrn.get( hrn.getID() ) == hrn;
839 protected void mergeIntoSummary( HeapRegionNode hrn,
840 HeapRegionNode hrnSummary ) {
841 assert hrnSummary.isNewSummary();
843 // assert that these nodes belong to THIS graph
844 assert belongsToThis( hrn );
845 assert belongsToThis( hrnSummary );
847 // transfer references _from_ hrn over to hrnSummary
848 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
849 while( itrReferencee.hasNext() ) {
850 RefEdge edge = itrReferencee.next();
851 RefEdge edgeMerged = edge.copy();
852 edgeMerged.setSrc( hrnSummary );
854 HeapRegionNode hrnReferencee = edge.getDst();
855 RefEdge edgeSummary =
856 hrnSummary.getReferenceTo( hrnReferencee,
861 if( edgeSummary == null ) {
862 // the merge is trivial, nothing to be done
863 addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
866 // otherwise an edge from the referencer to hrnSummary exists already
867 // and the edge referencer->hrn should be merged with it
869 Canonical.union( edgeMerged.getBeta(),
870 edgeSummary.getBeta()
873 edgeSummary.setPreds(
874 Canonical.join( edgeMerged.getPreds(),
875 edgeSummary.getPreds()
881 // next transfer references _to_ hrn over to hrnSummary
882 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
883 while( itrReferencer.hasNext() ) {
884 RefEdge edge = itrReferencer.next();
885 RefEdge edgeMerged = edge.copy();
886 edgeMerged.setDst( hrnSummary );
888 RefSrcNode onReferencer = edge.getSrc();
889 RefEdge edgeSummary =
890 onReferencer.getReferenceTo( hrnSummary,
895 if( edgeSummary == null ) {
896 // the merge is trivial, nothing to be done
897 addRefEdge( onReferencer, hrnSummary, edgeMerged );
900 // otherwise an edge from the referencer to alpha_S exists already
901 // and the edge referencer->alpha_K should be merged with it
903 Canonical.union( edgeMerged.getBeta(),
904 edgeSummary.getBeta()
907 edgeSummary.setPreds(
908 Canonical.join( edgeMerged.getPreds(),
909 edgeSummary.getPreds()
915 // then merge hrn reachability into hrnSummary
917 Canonical.union( hrnSummary.getAlpha(),
923 Canonical.join( hrnSummary.getPreds(),
928 // and afterward, this node is gone
929 wipeOut( hrn, true );
933 protected void transferOnto( HeapRegionNode hrnA,
934 HeapRegionNode hrnB ) {
936 assert belongsToThis( hrnA );
937 assert belongsToThis( hrnB );
939 // clear references in and out of node b
940 assert hrnB.isWiped();
942 // copy each edge in and out of A to B
943 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
944 while( itrReferencee.hasNext() ) {
945 RefEdge edge = itrReferencee.next();
946 HeapRegionNode hrnReferencee = edge.getDst();
947 RefEdge edgeNew = edge.copy();
948 edgeNew.setSrc( hrnB );
949 edgeNew.setDst( hrnReferencee );
951 addRefEdge( hrnB, hrnReferencee, edgeNew );
954 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
955 while( itrReferencer.hasNext() ) {
956 RefEdge edge = itrReferencer.next();
957 RefSrcNode onReferencer = edge.getSrc();
958 RefEdge edgeNew = edge.copy();
959 edgeNew.setDst( hrnB );
960 edgeNew.setDst( hrnB );
962 addRefEdge( onReferencer, hrnB, edgeNew );
965 // replace hrnB reachability and preds with hrnA's
966 hrnB.setAlpha( hrnA.getAlpha() );
967 hrnB.setPreds( hrnA.getPreds() );
969 // after transfer, wipe out source
970 wipeOut( hrnA, true );
974 // the purpose of this method is to conceptually "wipe out"
975 // a heap region from the graph--purposefully not called REMOVE
976 // because the node is still hanging around in the graph, just
977 // not mechanically connected or have any reach or predicate
978 // information on it anymore--lots of ops can use this
979 protected void wipeOut( HeapRegionNode hrn,
980 boolean wipeVariableReferences ) {
982 assert belongsToThis( hrn );
984 clearRefEdgesFrom( hrn, null, null, true );
986 if( wipeVariableReferences ) {
987 clearRefEdgesTo( hrn, null, null, true );
989 clearNonVarRefEdgesTo( hrn );
992 hrn.setAlpha( rsetEmpty );
993 hrn.setPreds( predsEmpty );
997 protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
999 Canonical.ageTuplesFrom( edge.getBeta(),
1005 protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
1007 Canonical.ageTuplesFrom( hrn.getAlpha(),
1015 protected void propagateTokensOverNodes( HeapRegionNode nPrime,
1017 HashSet<HeapRegionNode> nodesWithNewAlpha,
1018 HashSet<RefEdge> edgesWithNewBeta ) {
1020 HashSet<HeapRegionNode> todoNodes
1021 = new HashSet<HeapRegionNode>();
1022 todoNodes.add( nPrime );
1024 HashSet<RefEdge> todoEdges
1025 = new HashSet<RefEdge>();
1027 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1028 = new Hashtable<HeapRegionNode, ChangeSet>();
1029 nodePlannedChanges.put( nPrime, c0 );
1031 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1032 = new Hashtable<RefEdge, ChangeSet>();
1034 // first propagate change sets everywhere they can go
1035 while( !todoNodes.isEmpty() ) {
1036 HeapRegionNode n = todoNodes.iterator().next();
1037 ChangeSet C = nodePlannedChanges.get( n );
1039 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1040 while( referItr.hasNext() ) {
1041 RefEdge edge = referItr.next();
1042 todoEdges.add( edge );
1044 if( !edgePlannedChanges.containsKey( edge ) ) {
1045 edgePlannedChanges.put( edge,
1050 edgePlannedChanges.put( edge,
1051 Canonical.union( edgePlannedChanges.get( edge ),
1057 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1058 while( refeeItr.hasNext() ) {
1059 RefEdge edgeF = refeeItr.next();
1060 HeapRegionNode m = edgeF.getDst();
1062 ChangeSet changesToPass = ChangeSet.factory();
1064 Iterator<ChangeTuple> itrCprime = C.iterator();
1065 while( itrCprime.hasNext() ) {
1066 ChangeTuple c = itrCprime.next();
1067 if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
1068 changesToPass = Canonical.union( changesToPass, c );
1072 if( !changesToPass.isEmpty() ) {
1073 if( !nodePlannedChanges.containsKey( m ) ) {
1074 nodePlannedChanges.put( m, ChangeSet.factory() );
1077 ChangeSet currentChanges = nodePlannedChanges.get( m );
1079 if( !changesToPass.isSubset( currentChanges ) ) {
1081 nodePlannedChanges.put( m,
1082 Canonical.union( currentChanges,
1091 todoNodes.remove( n );
1094 // then apply all of the changes for each node at once
1095 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1096 while( itrMap.hasNext() ) {
1097 Map.Entry me = (Map.Entry) itrMap.next();
1098 HeapRegionNode n = (HeapRegionNode) me.getKey();
1099 ChangeSet C = (ChangeSet) me.getValue();
1101 // this propagation step is with respect to one change,
1102 // so we capture the full change from the old alpha:
1103 ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1107 // but this propagation may be only one of many concurrent
1108 // possible changes, so keep a running union with the node's
1109 // partially updated new alpha set
1110 n.setAlphaNew( Canonical.union( n.getAlphaNew(),
1115 nodesWithNewAlpha.add( n );
1118 propagateTokensOverEdges( todoEdges,
1125 protected void propagateTokensOverEdges( HashSet <RefEdge> todoEdges,
1126 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1127 HashSet <RefEdge> edgesWithNewBeta ) {
1129 // first propagate all change tuples everywhere they can go
1130 while( !todoEdges.isEmpty() ) {
1131 RefEdge edgeE = todoEdges.iterator().next();
1132 todoEdges.remove( edgeE );
1134 if( !edgePlannedChanges.containsKey( edgeE ) ) {
1135 edgePlannedChanges.put( edgeE,
1140 ChangeSet C = edgePlannedChanges.get( edgeE );
1142 ChangeSet changesToPass = ChangeSet.factory();
1144 Iterator<ChangeTuple> itrC = C.iterator();
1145 while( itrC.hasNext() ) {
1146 ChangeTuple c = itrC.next();
1147 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1148 changesToPass = Canonical.union( changesToPass, c );
1152 RefSrcNode rsn = edgeE.getSrc();
1154 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1155 HeapRegionNode n = (HeapRegionNode) rsn;
1157 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1158 while( referItr.hasNext() ) {
1159 RefEdge edgeF = referItr.next();
1161 if( !edgePlannedChanges.containsKey( edgeF ) ) {
1162 edgePlannedChanges.put( edgeF,
1167 ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1169 if( !changesToPass.isSubset( currentChanges ) ) {
1170 todoEdges.add( edgeF );
1171 edgePlannedChanges.put( edgeF,
1172 Canonical.union( currentChanges,
1181 // then apply all of the changes for each edge at once
1182 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1183 while( itrMap.hasNext() ) {
1184 Map.Entry me = (Map.Entry) itrMap.next();
1185 RefEdge e = (RefEdge) me.getKey();
1186 ChangeSet C = (ChangeSet) me.getValue();
1188 // this propagation step is with respect to one change,
1189 // so we capture the full change from the old beta:
1190 ReachSet localDelta =
1191 Canonical.applyChangeSet( e.getBeta(),
1196 // but this propagation may be only one of many concurrent
1197 // possible changes, so keep a running union with the edge's
1198 // partially updated new beta set
1199 e.setBetaNew( Canonical.union( e.getBetaNew(),
1204 edgesWithNewBeta.add( e );
1209 // used in makeCalleeView below to decide if there is
1210 // already an appropriate out-of-context edge in a callee
1211 // view graph for merging, or null if a new one will be added
1213 getOutOfContextReferenceTo( HeapRegionNode hrn,
1214 TypeDescriptor srcType,
1215 TypeDescriptor refType,
1218 HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1219 if( hrnInContext == null ) {
1223 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1224 while( refItr.hasNext() ) {
1225 RefEdge re = refItr.next();
1226 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1230 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1231 if( !hrnSrc.isOutOfContext() ) {
1235 if( srcType == null ) {
1236 if( hrnSrc.getType() != null ) {
1240 if( !srcType.equals( hrnSrc.getType() ) ) {
1245 if( !re.typeEquals( refType ) ) {
1249 if( !re.fieldEquals( refField ) ) {
1253 // tada! We found it!
1261 // use this method to make a new reach graph that is
1262 // what heap the FlatMethod callee from the FlatCall
1263 // would start with reaching from its arguments in
1266 makeCalleeView( FlatCall fc,
1268 Set<Integer> callerNodeIDsCopiedToCallee,
1269 boolean writeDebugDOTs
1272 // the callee view is a new graph: DON'T MODIFY
1274 ReachGraph rg = new ReachGraph();
1276 // track what parts of this graph have already been
1277 // added to callee view, variables not needed.
1278 // Note that we need this because when we traverse
1279 // this caller graph for each parameter we may find
1280 // nodes and edges more than once (which the per-param
1281 // "visit" sets won't show) and we only want to create
1282 // an element in the new callee view one time
1285 // a conservative starting point is to take the
1286 // mechanically-reachable-from-arguments graph
1287 // as opposed to using reachability information
1288 // to prune the graph further
1289 for( int i = 0; i < fm.numParameters(); ++i ) {
1291 // for each parameter index, get the symbol in the
1292 // caller view and callee view
1294 // argument defined here is the symbol in the caller
1295 TempDescriptor tdArg = fc.getArgMatchingParamIndex( fm, i );
1297 // parameter defined here is the symbol in the callee
1298 TempDescriptor tdParam = fm.getParameter( i );
1300 // use these two VariableNode objects to translate
1301 // between caller and callee--its easy to compare
1302 // a HeapRegionNode across callee and caller because
1303 // they will have the same heap region ID
1304 VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
1305 VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
1307 // now traverse the calleR view using the argument to
1308 // build the calleE view which has the parameter symbol
1309 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1310 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1311 toVisitInCaller.add( vnCaller );
1313 while( !toVisitInCaller.isEmpty() ) {
1314 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1315 RefSrcNode rsnCallee;
1317 toVisitInCaller.remove( rsnCaller );
1318 visitedInCaller.add( rsnCaller );
1320 // FIRST - setup the source end of an edge, and
1321 // remember the identifying info of the source
1322 // to build predicates
1323 TempDescriptor tdSrc = null;
1324 Integer hrnSrcID = null;
1326 if( rsnCaller == vnCaller ) {
1327 // if the caller node is the param symbol, we
1328 // have to do this translation for the callee
1329 rsnCallee = vnCallee;
1333 // otherwise the callee-view node is a heap
1334 // region with the same ID, that may or may
1335 // not have been created already
1336 assert rsnCaller instanceof HeapRegionNode;
1338 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1339 hrnSrcID = hrnSrcCaller.getID();
1341 if( !callerNodeIDsCopiedToCallee.contains( hrnSrcID ) ) {
1344 ExistPred.factory( hrnSrcID, null );
1346 ExistPredSet preds =
1347 ExistPredSet.factory( pred );
1350 rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
1351 hrnSrcCaller.isSingleObject(),
1352 hrnSrcCaller.isNewSummary(),
1353 hrnSrcCaller.isFlagged(),
1354 false, // out-of-context?
1355 hrnSrcCaller.getType(),
1356 hrnSrcCaller.getAllocSite(),
1357 /*toShadowTokens( this,*/ hrnSrcCaller.getInherent() /*)*/,
1358 /*toShadowTokens( this,*/ hrnSrcCaller.getAlpha() /*)*/,
1360 hrnSrcCaller.getDescription()
1363 callerNodeIDsCopiedToCallee.add( hrnSrcID );
1366 rsnCallee = rg.id2hrn.get( hrnSrcID );
1370 // SECOND - go over all edges from that source
1372 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1373 while( itrRefEdges.hasNext() ) {
1374 RefEdge reCaller = itrRefEdges.next();
1375 HeapRegionNode hrnCaller = reCaller.getDst();
1376 HeapRegionNode hrnCallee;
1378 // THIRD - setup destination ends of edges
1379 Integer hrnDstID = hrnCaller.getID();
1381 if( !callerNodeIDsCopiedToCallee.contains( hrnDstID ) ) {
1384 ExistPred.factory( hrnDstID, null );
1386 ExistPredSet preds =
1387 ExistPredSet.factory( pred );
1390 rg.createNewHeapRegionNode( hrnDstID,
1391 hrnCaller.isSingleObject(),
1392 hrnCaller.isNewSummary(),
1393 hrnCaller.isFlagged(),
1394 false, // out-of-context?
1395 hrnCaller.getType(),
1396 hrnCaller.getAllocSite(),
1397 /*toShadowTokens( this,*/ hrnCaller.getInherent() /*)*/,
1398 /*toShadowTokens( this,*/ hrnCaller.getAlpha() /*)*/,
1400 hrnCaller.getDescription()
1403 callerNodeIDsCopiedToCallee.add( hrnDstID );
1406 hrnCallee = rg.id2hrn.get( hrnDstID );
1409 // FOURTH - copy edge over if needed
1410 RefEdge reCallee = rsnCallee.getReferenceTo( hrnCallee,
1414 if( reCallee == null ) {
1417 ExistPred.factory( tdSrc,
1421 reCaller.getField(),
1423 rsnCaller instanceof VariableNode ); // out-of-context
1425 ExistPredSet preds =
1426 ExistPredSet.factory( pred );
1428 rg.addRefEdge( rsnCallee,
1430 new RefEdge( rsnCallee,
1433 reCaller.getField(),
1434 /*toShadowTokens( this,*/ reCaller.getBeta() /*)*/,
1440 // keep traversing nodes reachable from param i
1441 // that we haven't visited yet
1442 if( !visitedInCaller.contains( hrnCaller ) ) {
1443 toVisitInCaller.add( hrnCaller );
1446 } // end edge iteration
1447 } // end visiting heap nodes in caller
1448 } // end iterating over parameters as starting points
1451 // find the set of edges in this graph with source
1452 // out-of-context (not in nodes copied) and have a
1453 // destination in context (one of nodes copied) as
1454 // a starting point for building out-of-context nodes
1455 Iterator<Integer> itrInContext =
1456 callerNodeIDsCopiedToCallee.iterator();
1457 while( itrInContext.hasNext() ) {
1458 Integer hrnID = itrInContext.next();
1459 HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1461 Iterator<RefEdge> itrMightCross =
1462 hrnCallerAndInContext.iteratorToReferencers();
1463 while( itrMightCross.hasNext() ) {
1464 RefEdge edgeMightCross = itrMightCross.next();
1466 RefSrcNode rsnCallerAndOutContext =
1467 edgeMightCross.getSrc();
1469 TypeDescriptor oocNodeType;
1472 TempDescriptor oocPredSrcTemp = null;
1473 Integer oocPredSrcID = null;
1475 if( rsnCallerAndOutContext instanceof VariableNode ) {
1476 // variables are always out-of-context
1478 oocReach = rsetEmpty;
1480 ((VariableNode)rsnCallerAndOutContext).getTempDescriptor();
1484 HeapRegionNode hrnCallerAndOutContext =
1485 (HeapRegionNode) rsnCallerAndOutContext;
1487 // is this source node out-of-context?
1488 if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1489 // no, skip this edge
1493 oocNodeType = hrnCallerAndOutContext.getType();
1494 oocReach = hrnCallerAndOutContext.getAlpha();
1495 oocPredSrcID = hrnCallerAndOutContext.getID();
1498 // if we're here we've found an out-of-context edge
1501 ExistPred.factory( oocPredSrcTemp,
1504 edgeMightCross.getType(),
1505 edgeMightCross.getField(),
1507 true ); // out-of-context
1509 ExistPredSet preds =
1510 ExistPredSet.factory( pred );
1513 HeapRegionNode hrnCalleeAndInContext =
1514 rg.id2hrn.get( hrnCallerAndInContext.getID() );
1516 RefEdge oocEdgeExisting =
1517 rg.getOutOfContextReferenceTo( hrnCalleeAndInContext,
1519 edgeMightCross.getType(),
1520 edgeMightCross.getField()
1523 if( oocEdgeExisting == null ) {
1524 // we found a reference that crosses from out-of-context
1525 // to in-context, so build a special out-of-context node
1526 // for the callee IHM and its reference edge
1528 // for consistency, map one out-of-context "identifier"
1529 // to one heap region node id, otherwise no convergence
1530 String oocid = "oocid"+
1531 hrnCalleeAndInContext.getIDString()+
1533 edgeMightCross.getType()+
1534 edgeMightCross.getField();
1536 Integer oocHrnID = oocid2hrnid.get( oocid );
1538 HeapRegionNode hrnCalleeAndOutContext;
1540 if( oocHrnID == null ) {
1542 hrnCalleeAndOutContext =
1543 rg.createNewHeapRegionNode( null, // ID
1544 false, // single object?
1545 false, // new summary?
1547 true, // out-of-context?
1549 null, // alloc site, shouldn't be used
1550 /*toShadowTokens( this,*/ oocReach /*)*/, // inherent
1551 /*toShadowTokens( this,*/ oocReach /*)*/, // alpha
1556 oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1559 hrnCalleeAndOutContext =
1560 rg.createNewHeapRegionNode( oocHrnID, // ID
1561 false, // single object?
1562 false, // new summary?
1564 true, // out-of-context?
1566 null, // alloc site, shouldn't be used
1567 /*toShadowTokens( this,*/ oocReach /*)*/, // inherent
1568 /*toShadowTokens( this,*/ oocReach /*)*/, // alpha
1574 rg.addRefEdge( hrnCalleeAndOutContext,
1575 hrnCalleeAndInContext,
1576 new RefEdge( hrnCalleeAndOutContext,
1577 hrnCalleeAndInContext,
1578 edgeMightCross.getType(),
1579 edgeMightCross.getField(),
1580 /*toShadowTokens( this,*/ edgeMightCross.getBeta() /*)*/,
1586 // the out-of-context edge already exists
1587 oocEdgeExisting.setBeta( Canonical.union( oocEdgeExisting.getBeta(),
1588 edgeMightCross.getBeta()
1595 if( writeDebugDOTs ) {
1597 rg.writeGraph( "calleeview", true, false, false, false, true, true );
1598 } catch( IOException e ) {}
1604 private static Hashtable<String, Integer> oocid2hrnid =
1605 new Hashtable<String, Integer>();
1610 resolveMethodCall( FlatCall fc,
1612 ReachGraph rgCallee,
1613 Set<Integer> callerNodeIDsCopiedToCallee,
1614 boolean writeDebugDOTs
1618 if( writeDebugDOTs ) {
1620 rgCallee.writeGraph( "callee",
1621 true, false, false, false, true, true );
1622 writeGraph( "caller00In",
1623 true, false, false, false, true, true,
1624 callerNodeIDsCopiedToCallee );
1625 } catch( IOException e ) {}
1629 // method call transfer function steps:
1630 // 1. Use current callee-reachable heap (CRH) to test callee
1631 // predicates and mark what will be coming in.
1632 // 2. Wipe CRH out of caller.
1633 // 3. Transplant marked callee parts in:
1634 // a) bring in nodes
1635 // b) bring in callee -> callee edges
1636 // c) resolve out-of-context -> callee edges
1637 // d) assign return value
1638 // 4. Collapse shadow nodes down
1639 // 5. Global sweep it.
1643 // 1. mark what callee elements have satisfied predicates
1644 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1645 new Hashtable<HeapRegionNode, ExistPredSet>();
1647 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1648 new Hashtable<RefEdge, ExistPredSet>();
1650 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1651 while( meItr.hasNext() ) {
1652 Map.Entry me = (Map.Entry) meItr.next();
1653 Integer id = (Integer) me.getKey();
1654 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1656 ExistPredSet predsIfSatis =
1657 hrnCallee.getPreds().isSatisfiedBy( this,
1658 callerNodeIDsCopiedToCallee
1660 if( predsIfSatis != null ) {
1661 calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1663 // otherwise don't bother looking at edges from this node
1667 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencees();
1668 while( reItr.hasNext() ) {
1669 RefEdge reCallee = reItr.next();
1671 ExistPredSet ifDst =
1672 reCallee.getDst().getPreds().isSatisfiedBy( this,
1673 callerNodeIDsCopiedToCallee
1675 if( ifDst == null ) {
1680 reCallee.getPreds().isSatisfiedBy( this,
1681 callerNodeIDsCopiedToCallee
1683 if( predsIfSatis != null ) {
1684 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
1689 // test param -> HRN edges, also
1690 for( int i = 0; i < fm.numParameters(); ++i ) {
1692 // parameter defined here is the symbol in the callee
1693 TempDescriptor tdParam = fm.getParameter( i );
1694 VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
1696 Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
1697 while( reItr.hasNext() ) {
1698 RefEdge reCallee = reItr.next();
1700 ExistPredSet ifDst =
1701 reCallee.getDst().getPreds().isSatisfiedBy( this,
1702 callerNodeIDsCopiedToCallee
1704 if( ifDst == null ) {
1708 ExistPredSet predsIfSatis =
1709 reCallee.getPreds().isSatisfiedBy( this,
1710 callerNodeIDsCopiedToCallee
1712 if( predsIfSatis != null ) {
1713 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
1721 if( writeDebugDOTs ) {
1723 writeGraph( "caller20BeforeWipe",
1724 true, false, false, false, true, true );
1725 } catch( IOException e ) {}
1729 // 2. predicates tested, ok to wipe out caller part
1730 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
1731 while( hrnItr.hasNext() ) {
1732 Integer hrnID = hrnItr.next();
1733 HeapRegionNode hrnCaller = id2hrn.get( hrnID );
1734 assert hrnCaller != null;
1736 // when clearing off nodes, also eliminate variable
1738 wipeOut( hrnCaller, true );
1743 if( writeDebugDOTs ) {
1745 writeGraph( "caller30BeforeAddingNodes",
1746 true, false, false, false, true, true );
1747 } catch( IOException e ) {}
1751 // 3. callee elements with satisfied preds come in, note that
1752 // the mapping of elements satisfied to preds is like this:
1753 // A callee element EE has preds EEp that are satisfied by
1754 // some caller element ER. We bring EE into the caller
1755 // context as ERee with the preds of ER, namely ERp, which
1756 // in the following algorithm is the value in the mapping
1759 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
1760 while( satisItr.hasNext() ) {
1761 Map.Entry me = (Map.Entry) satisItr.next();
1762 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
1763 ExistPredSet preds = (ExistPredSet) me.getValue();
1765 if( hrnCallee.isOutOfContext() ) {
1769 AllocSite as = hrnCallee.getAllocSite();
1770 allocSites.add( as );
1772 Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
1774 HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
1775 if( hrnCaller == null ) {
1777 createNewHeapRegionNode( hrnIDshadow, // id or null to generate a new one
1778 hrnCallee.isSingleObject(), // single object?
1779 hrnCallee.isNewSummary(), // summary?
1780 hrnCallee.isFlagged(), // flagged?
1781 false, // out-of-context?
1782 hrnCallee.getType(), // type
1783 hrnCallee.getAllocSite(), // allocation site
1784 hrnCallee.getInherent(), // inherent reach
1785 null, // current reach
1786 predsEmpty, // predicates
1787 hrnCallee.getDescription() // description
1790 assert hrnCaller.isWiped();
1793 // TODO: alpha should be some rewritten version of callee in caller context
1794 hrnCaller.setAlpha( rsetEmpty );
1796 hrnCaller.setPreds( preds );
1801 if( writeDebugDOTs ) {
1803 writeGraph( "caller31BeforeAddingEdges",
1804 true, false, false, false, true, true );
1805 } catch( IOException e ) {}
1809 // 3.b) callee -> callee edges AND out-of-context -> callee
1810 satisItr = calleeEdgesSatisfied.entrySet().iterator();
1811 while( satisItr.hasNext() ) {
1812 Map.Entry me = (Map.Entry) satisItr.next();
1813 RefEdge reCallee = (RefEdge) me.getKey();
1814 ExistPredSet preds = (ExistPredSet) me.getValue();
1816 RefSrcNode rsnCallee = reCallee.getSrc();
1817 HeapRegionNode hrnDstCallee = reCallee.getDst();
1819 // even though we don't know yet what we're doing with
1820 // this edge, do this translation from callee dst to
1821 // caller dst a little early so we can use the result
1822 // for out-of-context matching below
1824 hrnDstCallee.getAllocSite();
1825 Integer hrnIDDstShadow =
1826 asDst.getShadowIDfromID( hrnDstCallee.getID() );
1827 HeapRegionNode hrnDstCaller =
1828 id2hrn.get( hrnIDDstShadow );
1830 // we'll find the set of sources in the caller that
1831 // this callee source could be (out-of-context node
1832 // can potentially map to multiple caller nodes)
1833 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
1835 if( rsnCallee instanceof VariableNode ) {
1836 // variable -> node in the callee should only
1837 // come into the caller if its from a param var
1838 VariableNode vnCallee = (VariableNode) rsnCallee;
1839 TempDescriptor tdParam = vnCallee.getTempDescriptor();
1840 TempDescriptor tdArg = fc.getArgMatchingParam( fm,
1842 if( tdArg == null ) {
1843 // this means the variable isn't a parameter, its local
1844 // to the callee so we ignore it in call site transfer
1848 rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
1851 HeapRegionNode hrnSrcCallee = (HeapRegionNode) reCallee.getSrc();
1853 if( !hrnSrcCallee.isOutOfContext() ) {
1854 AllocSite asSrc = hrnSrcCallee.getAllocSite();
1855 allocSites.add( asSrc );
1857 Integer hrnIDSrcShadow = asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
1858 rsnCallers.add( id2hrn.get( hrnIDSrcShadow ) );
1861 // for out-of-context sources we have to find all
1862 // caller sources that might match
1863 assert hrnDstCaller != null;
1865 Iterator<RefEdge> reItr = hrnDstCaller.iteratorToReferencers();
1866 while( reItr.hasNext() ) {
1867 // the edge and field (either possibly null) must match
1868 RefEdge reCaller = reItr.next();
1869 if( !reCaller.typeEquals ( reCallee.getType() ) ||
1870 !reCaller.fieldEquals( reCallee.getField() )
1875 RefSrcNode rsnCaller = reCaller.getSrc();
1876 if( rsnCaller instanceof VariableNode ) {
1877 // a variable node matches an OOC region with null type
1878 if( hrnSrcCallee.getType() != null ) {
1883 // otherwise types should match
1884 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
1885 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
1890 // it matches, add to sources of edges to make
1891 rsnCallers.add( rsnCaller );
1896 assert !rsnCallers.isEmpty();
1898 allocSites.add( asDst );
1900 assert hrnDstCaller != null;
1902 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
1903 while( rsnItr.hasNext() ) {
1904 RefSrcNode rsnCaller = rsnItr.next();
1906 // TODO: beta rewrites
1907 RefEdge reCaller = new RefEdge( rsnCaller,
1910 reCallee.getField(),
1915 // look to see if an edge with same field exists
1916 // and merge with it, otherwise just add the edge
1917 RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
1921 if( edgeExisting != null ) {
1922 edgeExisting.setBeta(
1923 Canonical.union( edgeExisting.getBeta(),
1927 edgeExisting.setPreds(
1928 Canonical.join( edgeExisting.getPreds(),
1934 addRefEdge( rsnCaller, hrnDstCaller, reCaller );
1941 if( writeDebugDOTs ) {
1943 writeGraph( "caller33BeforeResolveOutOfContextEdges",
1944 true, false, false, false, true, true );
1945 } catch( IOException e ) {}
1952 if( writeDebugDOTs ) {
1954 writeGraph( "caller35BeforeAssignReturnValue",
1955 true, false, false, false, true, true );
1956 } catch( IOException e ) {}
1960 // 3.d) handle return value assignment if needed
1961 TempDescriptor returnTemp = fc.getReturnTemp();
1962 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
1964 VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
1965 clearRefEdgesFrom( vnLhsCaller, null, null, true );
1967 VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
1968 Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
1969 while( reCalleeItr.hasNext() ) {
1970 RefEdge reCallee = reCalleeItr.next();
1971 HeapRegionNode hrnDstCallee = reCallee.getDst();
1973 // some edge types are not possible return values when we can
1974 // see what type variable we are assigning it to
1975 if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
1976 System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
1977 reCallee+" for return temp "+returnTemp );
1982 AllocSite asDst = hrnDstCallee.getAllocSite();
1983 allocSites.add( asDst );
1985 Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
1987 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
1988 assert hrnDstCaller != null;
1990 TypeDescriptor tdNewEdge =
1991 mostSpecificType( reCallee.getType(),
1992 hrnDstCallee.getType(),
1993 hrnDstCaller.getType()
1996 RefEdge reCaller = new RefEdge( vnLhsCaller,
2004 addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2010 if( writeDebugDOTs ) {
2012 writeGraph( "caller40BeforeShadowMerge",
2013 true, false, false, false, true, true );
2014 } catch( IOException e ) {}
2018 // 4) merge shadow nodes so alloc sites are back to k
2019 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2020 while( asItr.hasNext() ) {
2021 // for each allocation site do the following to merge
2022 // shadow nodes (newest from callee) with any existing
2023 // look for the newest normal and newest shadow "slot"
2024 // not being used, transfer normal to shadow. Keep
2025 // doing this until there are no more normal nodes, or
2026 // no empty shadow slots: then merge all remaining normal
2027 // nodes into the shadow summary. Finally, convert all
2028 // shadow to their normal versions.
2029 AllocSite as = asItr.next();
2032 while( ageNorm < allocationDepth &&
2033 ageShad < allocationDepth ) {
2035 // first, are there any normal nodes left?
2036 Integer idNorm = as.getIthOldest( ageNorm );
2037 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2038 if( hrnNorm == null ) {
2039 // no, this age of normal node not in the caller graph
2044 // yes, a normal node exists, is there an empty shadow
2045 // "slot" to transfer it onto?
2046 HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2047 if( !hrnShad.isWiped() ) {
2048 // no, this age of shadow node is not empty
2053 // yes, this shadow node is empty
2054 transferOnto( hrnNorm, hrnShad );
2059 // now, while there are still normal nodes but no shadow
2060 // slots, merge normal nodes into the shadow summary
2061 while( ageNorm < allocationDepth ) {
2063 // first, are there any normal nodes left?
2064 Integer idNorm = as.getIthOldest( ageNorm );
2065 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2066 if( hrnNorm == null ) {
2067 // no, this age of normal node not in the caller graph
2072 // yes, a normal node exists, so get the shadow summary
2073 HeapRegionNode summShad = getSummaryNode( as, true );
2074 mergeIntoSummary( hrnNorm, summShad );
2078 // if there is a normal summary, merge it into shadow summary
2079 Integer idNorm = as.getSummary();
2080 HeapRegionNode summNorm = id2hrn.get( idNorm );
2081 if( summNorm != null ) {
2082 HeapRegionNode summShad = getSummaryNode( as, true );
2083 mergeIntoSummary( summNorm, summShad );
2086 // finally, flip all existing shadow nodes onto the normal
2087 for( int i = 0; i < allocationDepth; ++i ) {
2088 Integer idShad = as.getIthOldestShadow( i );
2089 HeapRegionNode hrnShad = id2hrn.get( idShad );
2090 if( hrnShad != null ) {
2092 HeapRegionNode hrnNorm = getIthNode( as, i, false );
2093 assert hrnNorm.isWiped();
2094 transferOnto( hrnShad, hrnNorm );
2098 Integer idShad = as.getSummaryShadow();
2099 HeapRegionNode summShad = id2hrn.get( idShad );
2100 if( summShad != null ) {
2101 summNorm = getSummaryNode( as, false );
2102 transferOnto( summShad, summNorm );
2107 if( writeDebugDOTs ) {
2109 writeGraph( "caller50BeforeGlobalSweep",
2110 true, false, false, false, true, true );
2111 } catch( IOException e ) {}
2120 if( writeDebugDOTs ) {
2122 writeGraph( "caller90AfterTransfer",
2123 true, false, false, false, true, true );
2124 } catch( IOException e ) {}
2130 ////////////////////////////////////////////////////
2132 // Abstract garbage collection simply removes
2133 // heap region nodes that are not mechanically
2134 // reachable from a root set. This step is
2135 // essential for testing node and edge existence
2136 // predicates efficiently
2138 ////////////////////////////////////////////////////
2139 public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2141 // calculate a root set, will be different for Java
2142 // version of analysis versus Bamboo version
2143 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2145 // visit every variable in graph while building root
2146 // set, and do iterating on a copy, so we can remove
2147 // dead variables while we're at this
2148 Iterator makeCopyItr = td2vn.entrySet().iterator();
2149 Set entrysCopy = new HashSet();
2150 while( makeCopyItr.hasNext() ) {
2151 entrysCopy.add( makeCopyItr.next() );
2154 Iterator eItr = entrysCopy.iterator();
2155 while( eItr.hasNext() ) {
2156 Map.Entry me = (Map.Entry) eItr.next();
2157 TempDescriptor td = (TempDescriptor) me.getKey();
2158 VariableNode vn = (VariableNode) me.getValue();
2160 if( liveSet.contains( td ) ) {
2164 // dead var, remove completely from graph
2166 clearRefEdgesFrom( vn, null, null, true );
2170 // everything visited in a traversal is
2171 // considered abstractly live
2172 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2174 while( !toVisit.isEmpty() ) {
2175 RefSrcNode rsn = toVisit.iterator().next();
2176 toVisit.remove( rsn );
2179 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2180 while( hrnItr.hasNext() ) {
2181 RefEdge edge = hrnItr.next();
2182 HeapRegionNode hrn = edge.getDst();
2184 if( !visited.contains( hrn ) ) {
2190 // get a copy of the set to iterate over because
2191 // we're going to monkey with the graph when we
2192 // identify a garbage node
2193 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2194 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2195 while( hrnItr.hasNext() ) {
2196 hrnAllPrior.add( hrnItr.next() );
2199 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2200 while( hrnAllItr.hasNext() ) {
2201 HeapRegionNode hrn = hrnAllItr.next();
2203 if( !visited.contains( hrn ) ) {
2205 // heap region nodes are compared across ReachGraph
2206 // objects by their integer ID, so when discarding
2207 // garbage nodes we must also discard entries in
2208 // the ID -> heap region hashtable.
2209 id2hrn.remove( hrn.getID() );
2211 // RefEdge objects are two-way linked between
2212 // nodes, so when a node is identified as garbage,
2213 // actively clear references to and from it so
2214 // live nodes won't have dangling RefEdge's
2215 wipeOut( hrn, true );
2217 // if we just removed the last node from an allocation
2218 // site, it should be taken out of the ReachGraph's list
2219 AllocSite as = hrn.getAllocSite();
2220 if( !hasNodesOf( as ) ) {
2221 allocSites.remove( as );
2227 protected boolean hasNodesOf( AllocSite as ) {
2228 if( id2hrn.containsKey( as.getSummary() ) ) {
2232 for( int i = 0; i < allocationDepth; ++i ) {
2233 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2241 ////////////////////////////////////////////////////
2243 // This global sweep is an optional step to prune
2244 // reachability sets that are not internally
2245 // consistent with the global graph. It should be
2246 // invoked after strong updates or method calls.
2248 ////////////////////////////////////////////////////
2249 public void globalSweep() {
2251 // boldB is part of the phase 1 sweep
2252 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
2253 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2255 // visit every heap region to initialize alphaNew and calculate boldB
2256 Iterator itrHrns = id2hrn.entrySet().iterator();
2257 while( itrHrns.hasNext() ) {
2258 Map.Entry me = (Map.Entry) itrHrns.next();
2259 Integer hrnID = (Integer) me.getKey();
2260 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2262 // assert that this node and incoming edges have clean alphaNew
2263 // and betaNew sets, respectively
2264 assert rsetEmpty.equals( hrn.getAlphaNew() );
2266 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2267 while( itrRers.hasNext() ) {
2268 RefEdge edge = itrRers.next();
2269 assert rsetEmpty.equals( edge.getBetaNew() );
2272 // calculate boldB for this flagged node
2273 if( hrn.isFlagged() ) {
2275 Hashtable<RefEdge, ReachSet> boldB_f =
2276 new Hashtable<RefEdge, ReachSet>();
2278 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2280 // initial boldB_f constraints
2281 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2282 while( itrRees.hasNext() ) {
2283 RefEdge edge = itrRees.next();
2285 assert !boldB.containsKey( edge );
2286 boldB_f.put( edge, edge.getBeta() );
2288 assert !workSetEdges.contains( edge );
2289 workSetEdges.add( edge );
2292 // enforce the boldB_f constraint at edges until we reach a fixed point
2293 while( !workSetEdges.isEmpty() ) {
2294 RefEdge edge = workSetEdges.iterator().next();
2295 workSetEdges.remove( edge );
2297 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2298 while( itrPrime.hasNext() ) {
2299 RefEdge edgePrime = itrPrime.next();
2301 ReachSet prevResult = boldB_f.get( edgePrime );
2302 ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2306 if( prevResult == null ||
2307 Canonical.union( prevResult,
2308 intersection ).size() > prevResult.size() ) {
2310 if( prevResult == null ) {
2311 boldB_f.put( edgePrime,
2312 Canonical.union( edgePrime.getBeta(),
2317 boldB_f.put( edgePrime,
2318 Canonical.union( prevResult,
2323 workSetEdges.add( edgePrime );
2328 boldB.put( hrnID, boldB_f );
2333 // use boldB to prune hrnIDs from alpha states that are impossible
2334 // and propagate the differences backwards across edges
2335 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2337 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2338 new Hashtable<RefEdge, ChangeSet>();
2341 itrHrns = id2hrn.entrySet().iterator();
2342 while( itrHrns.hasNext() ) {
2343 Map.Entry me = (Map.Entry) itrHrns.next();
2344 Integer hrnID = (Integer) me.getKey();
2345 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2347 // create the inherent hrnID from a flagged region
2348 // as an exception to removal below
2349 ReachTuple rtException =
2350 ReachTuple.factory( hrnID,
2351 !hrn.isSingleObject(),
2352 ReachTuple.ARITY_ONE
2355 ChangeSet cts = ChangeSet.factory();
2357 // mark hrnIDs for removal
2358 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2359 while( stateItr.hasNext() ) {
2360 ReachState stateOld = stateItr.next();
2362 ReachState markedHrnIDs = ReachState.factory();
2364 Iterator<ReachTuple> rtItr = stateOld.iterator();
2365 while( rtItr.hasNext() ) {
2366 ReachTuple rtOld = rtItr.next();
2368 // never remove the inherent hrnID from a flagged region
2369 // because it is trivially satisfied
2370 if( hrn.isFlagged() ) {
2371 if( rtOld == rtException ) {
2376 // does boldB_ttOld allow this hrnID?
2377 boolean foundState = false;
2378 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2379 while( incidentEdgeItr.hasNext() ) {
2380 RefEdge incidentEdge = incidentEdgeItr.next();
2382 // if it isn't allowed, mark for removal
2383 Integer idOld = rtOld.getHrnID();
2384 assert id2hrn.containsKey( idOld );
2385 Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
2386 ReachSet boldB_ttOld_incident = B.get( incidentEdge );
2387 if( boldB_ttOld_incident != null &&
2388 boldB_ttOld_incident.contains( stateOld ) ) {
2394 markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
2398 // if there is nothing marked, just move on
2399 if( markedHrnIDs.isEmpty() ) {
2400 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2407 // remove all marked hrnIDs and establish a change set that should
2408 // propagate backwards over edges from this node
2409 ReachState statePruned = ReachState.factory();
2410 rtItr = stateOld.iterator();
2411 while( rtItr.hasNext() ) {
2412 ReachTuple rtOld = rtItr.next();
2414 if( !markedHrnIDs.containsTuple( rtOld ) ) {
2415 statePruned = Canonical.union( statePruned, rtOld );
2418 assert !stateOld.equals( statePruned );
2420 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2424 ChangeTuple ct = ChangeTuple.factory( stateOld,
2427 cts = Canonical.union( cts, ct );
2430 // throw change tuple set on all incident edges
2431 if( !cts.isEmpty() ) {
2432 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2433 while( incidentEdgeItr.hasNext() ) {
2434 RefEdge incidentEdge = incidentEdgeItr.next();
2436 edgesForPropagation.add( incidentEdge );
2438 if( edgePlannedChanges.get( incidentEdge ) == null ) {
2439 edgePlannedChanges.put( incidentEdge, cts );
2441 edgePlannedChanges.put(
2443 Canonical.union( edgePlannedChanges.get( incidentEdge ),
2452 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2454 propagateTokensOverEdges( edgesForPropagation,
2458 // at the end of the 1st phase reference edges have
2459 // beta, betaNew that correspond to beta and betaR
2461 // commit beta<-betaNew, so beta=betaR and betaNew
2462 // will represent the beta' calculation in 2nd phase
2464 // commit alpha<-alphaNew because it won't change
2465 HashSet<RefEdge> res = new HashSet<RefEdge>();
2467 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2468 while( nodeItr.hasNext() ) {
2469 HeapRegionNode hrn = nodeItr.next();
2470 hrn.applyAlphaNew();
2471 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
2472 while( itrRes.hasNext() ) {
2473 res.add( itrRes.next() );
2479 Iterator<RefEdge> edgeItr = res.iterator();
2480 while( edgeItr.hasNext() ) {
2481 RefEdge edge = edgeItr.next();
2482 HeapRegionNode hrn = edge.getDst();
2484 // commit results of last phase
2485 if( edgesUpdated.contains( edge ) ) {
2486 edge.applyBetaNew();
2489 // compute intial condition of 2nd phase
2490 edge.setBetaNew( Canonical.intersection( edge.getBeta(),
2496 // every edge in the graph is the initial workset
2497 Set<RefEdge> edgeWorkSet = (Set) res.clone();
2498 while( !edgeWorkSet.isEmpty() ) {
2499 RefEdge edgePrime = edgeWorkSet.iterator().next();
2500 edgeWorkSet.remove( edgePrime );
2502 RefSrcNode rsn = edgePrime.getSrc();
2503 if( !(rsn instanceof HeapRegionNode) ) {
2506 HeapRegionNode hrn = (HeapRegionNode) rsn;
2508 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
2509 while( itrEdge.hasNext() ) {
2510 RefEdge edge = itrEdge.next();
2512 ReachSet prevResult = edge.getBetaNew();
2513 assert prevResult != null;
2515 ReachSet intersection =
2516 Canonical.intersection( edge.getBeta(),
2517 edgePrime.getBetaNew()
2520 if( Canonical.union( prevResult,
2522 ).size() > prevResult.size() ) {
2524 Canonical.union( prevResult,
2528 edgeWorkSet.add( edge );
2533 // commit beta' (beta<-betaNew)
2534 edgeItr = res.iterator();
2535 while( edgeItr.hasNext() ) {
2536 edgeItr.next().applyBetaNew();
2542 ////////////////////////////////////////////////////
2543 // high-level merge operations
2544 ////////////////////////////////////////////////////
2545 public void merge_sameMethodContext( ReachGraph rg ) {
2546 // when merging two graphs that abstract the heap
2547 // of the same method context, we just call the
2548 // basic merge operation
2552 public void merge_diffMethodContext( ReachGraph rg ) {
2553 // when merging graphs for abstract heaps in
2554 // different method contexts we should:
2555 // 1) age the allocation sites?
2559 ////////////////////////////////////////////////////
2560 // in merge() and equals() methods the suffix A
2561 // represents the passed in graph and the suffix
2562 // B refers to the graph in this object
2563 // Merging means to take the incoming graph A and
2564 // merge it into B, so after the operation graph B
2565 // is the final result.
2566 ////////////////////////////////////////////////////
2567 protected void merge( ReachGraph rg ) {
2574 mergeRefEdges ( rg );
2575 mergeAllocSites( rg );
2578 protected void mergeNodes( ReachGraph rg ) {
2580 // start with heap region nodes
2581 Set sA = rg.id2hrn.entrySet();
2582 Iterator iA = sA.iterator();
2583 while( iA.hasNext() ) {
2584 Map.Entry meA = (Map.Entry) iA.next();
2585 Integer idA = (Integer) meA.getKey();
2586 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2588 // if this graph doesn't have a node the
2589 // incoming graph has, allocate it
2590 if( !id2hrn.containsKey( idA ) ) {
2591 HeapRegionNode hrnB = hrnA.copy();
2592 id2hrn.put( idA, hrnB );
2595 // otherwise this is a node present in both graphs
2596 // so make the new reachability set a union of the
2597 // nodes' reachability sets
2598 HeapRegionNode hrnB = id2hrn.get( idA );
2599 hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
2604 // if hrnB is already dirty or hrnA is dirty,
2605 // the hrnB should end up dirty: TODO
2607 if( !hrnA.isClean() ) {
2608 hrnB.setIsClean( false );
2614 // now add any variable nodes that are in graph B but
2616 sA = rg.td2vn.entrySet();
2618 while( iA.hasNext() ) {
2619 Map.Entry meA = (Map.Entry) iA.next();
2620 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2621 VariableNode lnA = (VariableNode) meA.getValue();
2623 // if the variable doesn't exist in B, allocate and add it
2624 VariableNode lnB = getVariableNodeFromTemp( tdA );
2628 protected void mergeRefEdges( ReachGraph rg ) {
2630 // between heap regions
2631 Set sA = rg.id2hrn.entrySet();
2632 Iterator iA = sA.iterator();
2633 while( iA.hasNext() ) {
2634 Map.Entry meA = (Map.Entry) iA.next();
2635 Integer idA = (Integer) meA.getKey();
2636 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2638 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2639 while( heapRegionsItrA.hasNext() ) {
2640 RefEdge edgeA = heapRegionsItrA.next();
2641 HeapRegionNode hrnChildA = edgeA.getDst();
2642 Integer idChildA = hrnChildA.getID();
2644 // at this point we know an edge in graph A exists
2645 // idA -> idChildA, does this exist in B?
2646 assert id2hrn.containsKey( idA );
2647 HeapRegionNode hrnB = id2hrn.get( idA );
2648 RefEdge edgeToMerge = null;
2650 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2651 while( heapRegionsItrB.hasNext() &&
2652 edgeToMerge == null ) {
2654 RefEdge edgeB = heapRegionsItrB.next();
2655 HeapRegionNode hrnChildB = edgeB.getDst();
2656 Integer idChildB = hrnChildB.getID();
2658 // don't use the RefEdge.equals() here because
2659 // we're talking about existence between graphs,
2660 // not intragraph equal
2661 if( idChildB.equals( idChildA ) &&
2662 edgeB.typeAndFieldEquals( edgeA ) ) {
2664 edgeToMerge = edgeB;
2668 // if the edge from A was not found in B,
2670 if( edgeToMerge == null ) {
2671 assert id2hrn.containsKey( idChildA );
2672 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2673 edgeToMerge = edgeA.copy();
2674 edgeToMerge.setSrc( hrnB );
2675 edgeToMerge.setDst( hrnChildB );
2676 addRefEdge( hrnB, hrnChildB, edgeToMerge );
2678 // otherwise, the edge already existed in both graphs
2679 // so merge their reachability sets
2681 // just replace this beta set with the union
2682 assert edgeToMerge != null;
2683 edgeToMerge.setBeta(
2684 Canonical.union( edgeToMerge.getBeta(),
2690 if( !edgeA.isClean() ) {
2691 edgeToMerge.setIsClean( false );
2698 // and then again from variable nodes
2699 sA = rg.td2vn.entrySet();
2701 while( iA.hasNext() ) {
2702 Map.Entry meA = (Map.Entry) iA.next();
2703 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2704 VariableNode vnA = (VariableNode) meA.getValue();
2706 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
2707 while( heapRegionsItrA.hasNext() ) {
2708 RefEdge edgeA = heapRegionsItrA.next();
2709 HeapRegionNode hrnChildA = edgeA.getDst();
2710 Integer idChildA = hrnChildA.getID();
2712 // at this point we know an edge in graph A exists
2713 // tdA -> idChildA, does this exist in B?
2714 assert td2vn.containsKey( tdA );
2715 VariableNode vnB = td2vn.get( tdA );
2716 RefEdge edgeToMerge = null;
2718 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
2719 while( heapRegionsItrB.hasNext() &&
2720 edgeToMerge == null ) {
2722 RefEdge edgeB = heapRegionsItrB.next();
2723 HeapRegionNode hrnChildB = edgeB.getDst();
2724 Integer idChildB = hrnChildB.getID();
2726 // don't use the RefEdge.equals() here because
2727 // we're talking about existence between graphs
2728 if( idChildB.equals( idChildA ) &&
2729 edgeB.typeAndFieldEquals( edgeA ) ) {
2731 edgeToMerge = edgeB;
2735 // if the edge from A was not found in B,
2737 if( edgeToMerge == null ) {
2738 assert id2hrn.containsKey( idChildA );
2739 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2740 edgeToMerge = edgeA.copy();
2741 edgeToMerge.setSrc( vnB );
2742 edgeToMerge.setDst( hrnChildB );
2743 addRefEdge( vnB, hrnChildB, edgeToMerge );
2745 // otherwise, the edge already existed in both graphs
2746 // so merge their reachability sets
2748 // just replace this beta set with the union
2749 edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
2755 if( !edgeA.isClean() ) {
2756 edgeToMerge.setIsClean( false );
2764 protected void mergeAllocSites( ReachGraph rg ) {
2765 allocSites.addAll( rg.allocSites );
2769 // it is necessary in the equals() member functions
2770 // to "check both ways" when comparing the data
2771 // structures of two graphs. For instance, if all
2772 // edges between heap region nodes in graph A are
2773 // present and equal in graph B it is not sufficient
2774 // to say the graphs are equal. Consider that there
2775 // may be edges in graph B that are not in graph A.
2776 // the only way to know that all edges in both graphs
2777 // are equally present is to iterate over both data
2778 // structures and compare against the other graph.
2779 public boolean equals( ReachGraph rg ) {
2785 if( !areHeapRegionNodesEqual( rg ) ) {
2789 if( !areVariableNodesEqual( rg ) ) {
2793 if( !areRefEdgesEqual( rg ) ) {
2797 // if everything is equal up to this point,
2798 // assert that allocSites is also equal--
2799 // this data is redundant but kept for efficiency
2800 assert allocSites.equals( rg.allocSites );
2806 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
2808 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
2812 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
2819 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
2821 Set sA = rgA.id2hrn.entrySet();
2822 Iterator iA = sA.iterator();
2823 while( iA.hasNext() ) {
2824 Map.Entry meA = (Map.Entry) iA.next();
2825 Integer idA = (Integer) meA.getKey();
2826 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2828 if( !rgB.id2hrn.containsKey( idA ) ) {
2832 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2833 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
2842 protected boolean areVariableNodesEqual( ReachGraph rg ) {
2844 if( !areallVNinAalsoinBandequal( this, rg ) ) {
2848 if( !areallVNinAalsoinBandequal( rg, this ) ) {
2855 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
2857 Set sA = rgA.td2vn.entrySet();
2858 Iterator iA = sA.iterator();
2859 while( iA.hasNext() ) {
2860 Map.Entry meA = (Map.Entry) iA.next();
2861 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2863 if( !rgB.td2vn.containsKey( tdA ) ) {
2872 protected boolean areRefEdgesEqual( ReachGraph rg ) {
2873 if( !areallREinAandBequal( this, rg ) ) {
2880 static protected boolean areallREinAandBequal( ReachGraph rgA,
2883 // check all the heap region->heap region edges
2884 Set sA = rgA.id2hrn.entrySet();
2885 Iterator iA = sA.iterator();
2886 while( iA.hasNext() ) {
2887 Map.Entry meA = (Map.Entry) iA.next();
2888 Integer idA = (Integer) meA.getKey();
2889 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2891 // we should have already checked that the same
2892 // heap regions exist in both graphs
2893 assert rgB.id2hrn.containsKey( idA );
2895 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
2899 // then check every edge in B for presence in A, starting
2900 // from the same parent HeapRegionNode
2901 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2903 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
2908 // then check all the variable->heap region edges
2909 sA = rgA.td2vn.entrySet();
2911 while( iA.hasNext() ) {
2912 Map.Entry meA = (Map.Entry) iA.next();
2913 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2914 VariableNode vnA = (VariableNode) meA.getValue();
2916 // we should have already checked that the same
2917 // label nodes exist in both graphs
2918 assert rgB.td2vn.containsKey( tdA );
2920 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
2924 // then check every edge in B for presence in A, starting
2925 // from the same parent VariableNode
2926 VariableNode vnB = rgB.td2vn.get( tdA );
2928 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
2937 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
2941 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
2942 while( itrA.hasNext() ) {
2943 RefEdge edgeA = itrA.next();
2944 HeapRegionNode hrnChildA = edgeA.getDst();
2945 Integer idChildA = hrnChildA.getID();
2947 assert rgB.id2hrn.containsKey( idChildA );
2949 // at this point we know an edge in graph A exists
2950 // rnA -> idChildA, does this exact edge exist in B?
2951 boolean edgeFound = false;
2953 RefSrcNode rnB = null;
2954 if( rnA instanceof HeapRegionNode ) {
2955 HeapRegionNode hrnA = (HeapRegionNode) rnA;
2956 rnB = rgB.id2hrn.get( hrnA.getID() );
2958 VariableNode vnA = (VariableNode) rnA;
2959 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
2962 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
2963 while( itrB.hasNext() ) {
2964 RefEdge edgeB = itrB.next();
2965 HeapRegionNode hrnChildB = edgeB.getDst();
2966 Integer idChildB = hrnChildB.getID();
2968 if( idChildA.equals( idChildB ) &&
2969 edgeA.typeAndFieldEquals( edgeB ) ) {
2971 // there is an edge in the right place with the right field,
2972 // but do they have the same attributes?
2973 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
2974 edgeA.equalsPreds( edgeB )
2991 // this analysis no longer has the "match anything"
2992 // type which was represented by null
2993 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2994 TypeDescriptor td2 ) {
2998 if( td1.isNull() ) {
3001 if( td2.isNull() ) {
3004 return typeUtil.mostSpecific( td1, td2 );
3007 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3009 TypeDescriptor td3 ) {
3011 return mostSpecificType( td1,
3012 mostSpecificType( td2, td3 )
3016 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3019 TypeDescriptor td4 ) {
3021 return mostSpecificType( mostSpecificType( td1, td2 ),
3022 mostSpecificType( td3, td4 )
3026 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3027 TypeDescriptor possibleChild ) {
3028 assert possibleSuper != null;
3029 assert possibleChild != null;
3031 if( possibleSuper.isNull() ||
3032 possibleChild.isNull() ) {
3036 return typeUtil.isSuperorType( possibleSuper, possibleChild );
3040 protected boolean hasMatchingField( HeapRegionNode src,
3043 TypeDescriptor tdSrc = src.getType();
3044 assert tdSrc != null;
3046 if( tdSrc.isArray() ) {
3047 TypeDescriptor td = edge.getType();
3050 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3051 assert tdSrcDeref != null;
3053 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3057 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3060 // if it's not a class, it doesn't have any fields to match
3061 if( !tdSrc.isClass() ) {
3065 ClassDescriptor cd = tdSrc.getClassDesc();
3066 while( cd != null ) {
3067 Iterator fieldItr = cd.getFields();
3069 while( fieldItr.hasNext() ) {
3070 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3072 if( fd.getType().equals( edge.getType() ) &&
3073 fd.getSymbol().equals( edge.getField() ) ) {
3078 cd = cd.getSuperDesc();
3081 // otherwise it is a class with fields
3082 // but we didn't find a match
3086 protected boolean hasMatchingType( RefEdge edge,
3087 HeapRegionNode dst ) {
3089 // if the region has no type, matches everything
3090 TypeDescriptor tdDst = dst.getType();
3091 assert tdDst != null;
3093 // if the type is not a class or an array, don't
3094 // match because primitives are copied, no aliases
3095 ClassDescriptor cdDst = tdDst.getClassDesc();
3096 if( cdDst == null && !tdDst.isArray() ) {
3100 // if the edge type is null, it matches everything
3101 TypeDescriptor tdEdge = edge.getType();
3102 assert tdEdge != null;
3104 return typeUtil.isSuperorType( tdEdge, tdDst );
3109 public void writeGraph( String graphName,
3110 boolean writeLabels,
3111 boolean labelSelect,
3112 boolean pruneGarbage,
3113 boolean writeReferencers,
3114 boolean hideSubsetReachability,
3115 boolean hideEdgeTaints
3116 ) throws java.io.IOException {
3117 writeGraph( graphName,
3122 hideSubsetReachability,
3127 public void writeGraph( String graphName,
3128 boolean writeLabels,
3129 boolean labelSelect,
3130 boolean pruneGarbage,
3131 boolean writeReferencers,
3132 boolean hideSubsetReachability,
3133 boolean hideEdgeTaints,
3134 Set<Integer> callerNodeIDsCopiedToCallee
3135 ) throws java.io.IOException {
3137 // remove all non-word characters from the graph name so
3138 // the filename and identifier in dot don't cause errors
3139 graphName = graphName.replaceAll( "[\\W]", "" );
3142 new BufferedWriter( new FileWriter( graphName+".dot" ) );
3144 bw.write( "digraph "+graphName+" {\n" );
3147 // this is an optional step to form the callee-reachable
3148 // "cut-out" into a DOT cluster for visualization
3149 if( callerNodeIDsCopiedToCallee != null ) {
3151 bw.write( " subgraph cluster0 {\n" );
3152 bw.write( " color=blue;\n" );
3154 Iterator i = id2hrn.entrySet().iterator();
3155 while( i.hasNext() ) {
3156 Map.Entry me = (Map.Entry) i.next();
3157 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3159 if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3160 bw.write( " "+hrn.toString()+
3161 hrn.toStringDOT( hideSubsetReachability )+
3171 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3173 // then visit every heap region node
3174 Iterator i = id2hrn.entrySet().iterator();
3175 while( i.hasNext() ) {
3176 Map.Entry me = (Map.Entry) i.next();
3177 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3179 // only visit nodes worth writing out--for instance
3180 // not every node at an allocation is referenced
3181 // (think of it as garbage-collected), etc.
3182 if( !pruneGarbage ||
3183 (hrn.isFlagged() && hrn.getID() > 0) ||
3184 hrn.getDescription().startsWith( "param" ) ||
3185 hrn.isOutOfContext()
3188 if( !visited.contains( hrn ) ) {
3189 traverseHeapRegionNodes( hrn,
3194 hideSubsetReachability,
3196 callerNodeIDsCopiedToCallee );
3201 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
3204 // then visit every label node, useful for debugging
3206 i = td2vn.entrySet().iterator();
3207 while( i.hasNext() ) {
3208 Map.Entry me = (Map.Entry) i.next();
3209 VariableNode vn = (VariableNode) me.getValue();
3212 String labelStr = vn.getTempDescriptorString();
3213 if( labelStr.startsWith("___temp") ||
3214 labelStr.startsWith("___dst") ||
3215 labelStr.startsWith("___srctmp") ||
3216 labelStr.startsWith("___neverused")
3222 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3223 while( heapRegionsItr.hasNext() ) {
3224 RefEdge edge = heapRegionsItr.next();
3225 HeapRegionNode hrn = edge.getDst();
3227 if( pruneGarbage && !visited.contains( hrn ) ) {
3228 traverseHeapRegionNodes( hrn,
3233 hideSubsetReachability,
3235 callerNodeIDsCopiedToCallee );
3238 bw.write( " "+vn.toString()+
3239 " -> "+hrn.toString()+
3240 edge.toStringDOT( hideSubsetReachability, "" )+
3250 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
3253 Set<HeapRegionNode> visited,
3254 boolean writeReferencers,
3255 boolean hideSubsetReachability,
3256 boolean hideEdgeTaints,
3257 Set<Integer> callerNodeIDsCopiedToCallee
3258 ) throws java.io.IOException {
3260 if( visited.contains( hrn ) ) {
3265 // if we're drawing the callee-view subgraph, only
3266 // write out the node info if it hasn't already been
3268 if( callerNodeIDsCopiedToCallee == null ||
3269 !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3271 bw.write( " "+hrn.toString()+
3272 hrn.toStringDOT( hideSubsetReachability )+
3276 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3277 while( childRegionsItr.hasNext() ) {
3278 RefEdge edge = childRegionsItr.next();
3279 HeapRegionNode hrnChild = edge.getDst();
3281 if( callerNodeIDsCopiedToCallee != null &&
3282 (edge.getSrc() instanceof HeapRegionNode) ) {
3283 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3284 if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
3285 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3287 bw.write( " "+hrn.toString()+
3288 " -> "+hrnChild.toString()+
3289 edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
3291 } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
3292 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3294 bw.write( " "+hrn.toString()+
3295 " -> "+hrnChild.toString()+
3296 edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
3299 bw.write( " "+hrn.toString()+
3300 " -> "+hrnChild.toString()+
3301 edge.toStringDOT( hideSubsetReachability, "" )+
3305 bw.write( " "+hrn.toString()+
3306 " -> "+hrnChild.toString()+
3307 edge.toStringDOT( hideSubsetReachability, "" )+
3311 traverseHeapRegionNodes( hrnChild,
3316 hideSubsetReachability,
3318 callerNodeIDsCopiedToCallee );