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;
165 if( referencer.getReferenceTo( referencee,
170 System.out.println( " edge being added again: "+edge );
173 // edges are getting added twice to graphs now, the
174 // kind that should have abstract facts merged--use
175 // this check to prevent that
176 assert referencer.getReferenceTo( referencee,
181 referencer.addReferencee( edge );
182 referencee.addReferencer( edge );
185 protected void removeRefEdge( RefEdge e ) {
186 removeRefEdge( e.getSrc(),
192 protected void removeRefEdge( RefSrcNode referencer,
193 HeapRegionNode referencee,
196 assert referencer != null;
197 assert referencee != null;
199 RefEdge edge = referencer.getReferenceTo( referencee,
203 assert edge == referencee.getReferenceFrom( referencer,
207 referencer.removeReferencee( edge );
208 referencee.removeReferencer( edge );
211 protected void clearRefEdgesFrom( RefSrcNode referencer,
214 boolean removeAll ) {
215 assert referencer != null;
217 // get a copy of the set to iterate over, otherwise
218 // we will be trying to take apart the set as we
219 // are iterating over it, which won't work
220 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
221 while( i.hasNext() ) {
222 RefEdge edge = i.next();
225 (edge.typeEquals( type ) && edge.fieldEquals( field ))
228 HeapRegionNode referencee = edge.getDst();
230 removeRefEdge( referencer,
238 protected void clearRefEdgesTo( HeapRegionNode referencee,
241 boolean removeAll ) {
242 assert referencee != null;
244 // get a copy of the set to iterate over, otherwise
245 // we will be trying to take apart the set as we
246 // are iterating over it, which won't work
247 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
248 while( i.hasNext() ) {
249 RefEdge edge = i.next();
252 (edge.typeEquals( type ) && edge.fieldEquals( field ))
255 RefSrcNode referencer = edge.getSrc();
257 removeRefEdge( referencer,
266 ////////////////////////////////////////////////////
268 // Assignment Operation Methods
270 // These methods are high-level operations for
271 // modeling program assignment statements using
272 // the low-level reference create/remove methods
275 ////////////////////////////////////////////////////
277 public void assignTempXEqualToTempY( TempDescriptor x,
279 assignTempXEqualToCastedTempY( x, y, null );
282 public void assignTempXEqualToCastedTempY( TempDescriptor x,
284 TypeDescriptor tdCast ) {
286 VariableNode lnX = getVariableNodeFromTemp( x );
287 VariableNode lnY = getVariableNodeFromTemp( y );
289 clearRefEdgesFrom( lnX, null, null, true );
291 // note it is possible that the types of temps in the
292 // flat node to analyze will reveal that some typed
293 // edges in the reachability graph are impossible
294 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
296 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
297 while( itrYhrn.hasNext() ) {
298 RefEdge edgeY = itrYhrn.next();
299 HeapRegionNode referencee = edgeY.getDst();
300 RefEdge edgeNew = edgeY.copy();
302 if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
303 impossibleEdges.add( edgeY );
307 edgeNew.setSrc( lnX );
309 if( tdCast == null ) {
310 edgeNew.setType( mostSpecificType( y.getType(),
316 edgeNew.setType( mostSpecificType( y.getType(),
318 referencee.getType(),
324 edgeNew.setField( null );
326 addRefEdge( lnX, referencee, edgeNew );
329 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
330 while( itrImp.hasNext() ) {
331 RefEdge edgeImp = itrImp.next();
332 removeRefEdge( edgeImp );
337 public void assignTempXEqualToTempYFieldF( TempDescriptor x,
339 FieldDescriptor f ) {
340 VariableNode lnX = getVariableNodeFromTemp( x );
341 VariableNode lnY = getVariableNodeFromTemp( y );
343 clearRefEdgesFrom( lnX, null, null, true );
345 // note it is possible that the types of temps in the
346 // flat node to analyze will reveal that some typed
347 // edges in the reachability graph are impossible
348 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
350 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
351 while( itrYhrn.hasNext() ) {
352 RefEdge edgeY = itrYhrn.next();
353 HeapRegionNode hrnY = edgeY.getDst();
354 ReachSet betaY = edgeY.getBeta();
356 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
357 while( itrHrnFhrn.hasNext() ) {
358 RefEdge edgeHrn = itrHrnFhrn.next();
359 HeapRegionNode hrnHrn = edgeHrn.getDst();
360 ReachSet betaHrn = edgeHrn.getBeta();
362 // prune edges that are not a matching field
363 if( edgeHrn.getType() != null &&
364 !edgeHrn.getField().equals( f.getSymbol() )
369 // check for impossible edges
370 if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
371 impossibleEdges.add( edgeHrn );
375 TypeDescriptor tdNewEdge =
376 mostSpecificType( edgeHrn.getType(),
380 RefEdge edgeNew = new RefEdge( lnX,
384 Canonical.intersection( betaY, betaHrn ),
388 addRefEdge( lnX, hrnHrn, edgeNew );
392 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
393 while( itrImp.hasNext() ) {
394 RefEdge edgeImp = itrImp.next();
395 removeRefEdge( edgeImp );
398 // anytime you might remove edges between heap regions
399 // you must global sweep to clean up broken reachability
400 if( !impossibleEdges.isEmpty() ) {
401 if( !DISABLE_GLOBAL_SWEEP ) {
408 public void assignTempXFieldFEqualToTempY( TempDescriptor x,
412 VariableNode lnX = getVariableNodeFromTemp( x );
413 VariableNode lnY = getVariableNodeFromTemp( y );
415 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
416 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
418 // note it is possible that the types of temps in the
419 // flat node to analyze will reveal that some typed
420 // edges in the reachability graph are impossible
421 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
423 // first look for possible strong updates and remove those edges
424 boolean strongUpdate = false;
426 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
427 while( itrXhrn.hasNext() ) {
428 RefEdge edgeX = itrXhrn.next();
429 HeapRegionNode hrnX = edgeX.getDst();
431 // we can do a strong update here if one of two cases holds
433 f != DisjointAnalysis.getArrayField( f.getType() ) &&
434 ( (hrnX.getNumReferencers() == 1) || // case 1
435 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
438 if( !DISABLE_STRONG_UPDATES ) {
440 clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
445 // then do all token propagation
446 itrXhrn = lnX.iteratorToReferencees();
447 while( itrXhrn.hasNext() ) {
448 RefEdge edgeX = itrXhrn.next();
449 HeapRegionNode hrnX = edgeX.getDst();
450 ReachSet betaX = edgeX.getBeta();
451 ReachSet R = Canonical.intersection( hrnX.getAlpha(),
455 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
456 while( itrYhrn.hasNext() ) {
457 RefEdge edgeY = itrYhrn.next();
458 HeapRegionNode hrnY = edgeY.getDst();
459 ReachSet O = edgeY.getBeta();
461 // check for impossible edges
462 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
463 impossibleEdges.add( edgeY );
467 // propagate tokens over nodes starting from hrnSrc, and it will
468 // take care of propagating back up edges from any touched nodes
469 ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
470 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
472 // then propagate back just up the edges from hrn
473 ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
474 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
476 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
477 new Hashtable<RefEdge, ChangeSet>();
479 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
480 while( referItr.hasNext() ) {
481 RefEdge edgeUpstream = referItr.next();
482 todoEdges.add( edgeUpstream );
483 edgePlannedChanges.put( edgeUpstream, Cx );
486 propagateTokensOverEdges( todoEdges,
493 // apply the updates to reachability
494 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
495 while( nodeItr.hasNext() ) {
496 nodeItr.next().applyAlphaNew();
499 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
500 while( edgeItr.hasNext() ) {
501 edgeItr.next().applyBetaNew();
505 // then go back through and add the new edges
506 itrXhrn = lnX.iteratorToReferencees();
507 while( itrXhrn.hasNext() ) {
508 RefEdge edgeX = itrXhrn.next();
509 HeapRegionNode hrnX = edgeX.getDst();
511 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
512 while( itrYhrn.hasNext() ) {
513 RefEdge edgeY = itrYhrn.next();
514 HeapRegionNode hrnY = edgeY.getDst();
516 // skip impossible edges here, we already marked them
517 // when computing reachability propagations above
518 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
522 // prepare the new reference edge hrnX.f -> hrnY
523 TypeDescriptor tdNewEdge =
524 mostSpecificType( y.getType(),
529 RefEdge edgeNew = new RefEdge( hrnX,
533 Canonical.pruneBy( edgeY.getBeta(),
539 // look to see if an edge with same field exists
540 // and merge with it, otherwise just add the edge
541 RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
545 if( edgeExisting != null ) {
546 edgeExisting.setBeta(
547 Canonical.union( edgeExisting.getBeta(),
551 edgeExisting.setPreds(
552 Canonical.join( edgeExisting.getPreds(),
558 addRefEdge( hrnX, hrnY, edgeNew );
563 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
564 while( itrImp.hasNext() ) {
565 RefEdge edgeImp = itrImp.next();
566 removeRefEdge( edgeImp );
569 // if there was a strong update, make sure to improve
570 // reachability with a global sweep
571 if( strongUpdate || !impossibleEdges.isEmpty() ) {
572 if( !DISABLE_GLOBAL_SWEEP ) {
579 public void assignReturnEqualToTemp( TempDescriptor x ) {
581 VariableNode lnR = getVariableNodeFromTemp( tdReturn );
582 VariableNode lnX = getVariableNodeFromTemp( x );
584 clearRefEdgesFrom( lnR, null, null, true );
586 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
587 while( itrXhrn.hasNext() ) {
588 RefEdge edgeX = itrXhrn.next();
589 HeapRegionNode referencee = edgeX.getDst();
590 RefEdge edgeNew = edgeX.copy();
591 edgeNew.setSrc( lnR );
593 addRefEdge( lnR, referencee, edgeNew );
598 public void assignTempEqualToNewAlloc( TempDescriptor x,
605 // after the age operation the newest (or zero-ith oldest)
606 // node associated with the allocation site should have
607 // no references to it as if it were a newly allocated
609 Integer idNewest = as.getIthOldest( 0 );
610 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
611 assert hrnNewest != null;
613 VariableNode lnX = getVariableNodeFromTemp( x );
614 clearRefEdgesFrom( lnX, null, null, true );
616 // make a new reference to allocated node
617 TypeDescriptor type = as.getType();
620 new RefEdge( lnX, // source
624 hrnNewest.getAlpha(), // beta
625 predsTrue // predicates
628 addRefEdge( lnX, hrnNewest, edgeNew );
632 // use the allocation site (unique to entire analysis) to
633 // locate the heap region nodes in this reachability graph
634 // that should be aged. The process models the allocation
635 // of new objects and collects all the oldest allocations
636 // in a summary node to allow for a finite analysis
638 // There is an additional property of this method. After
639 // running it on a particular reachability graph (many graphs
640 // may have heap regions related to the same allocation site)
641 // the heap region node objects in this reachability graph will be
642 // allocated. Therefore, after aging a graph for an allocation
643 // site, attempts to retrieve the heap region nodes using the
644 // integer id's contained in the allocation site should always
645 // return non-null heap regions.
646 public void age( AllocSite as ) {
648 // keep track of allocation sites that are represented
649 // in this graph for efficiency with other operations
650 allocSites.add( as );
652 // if there is a k-th oldest node, it merges into
654 Integer idK = as.getOldest();
655 if( id2hrn.containsKey( idK ) ) {
656 HeapRegionNode hrnK = id2hrn.get( idK );
658 // retrieve the summary node, or make it
660 HeapRegionNode hrnSummary = getSummaryNode( as, false );
662 mergeIntoSummary( hrnK, hrnSummary );
665 // move down the line of heap region nodes
666 // clobbering the ith and transferring all references
667 // to and from i-1 to node i.
668 for( int i = allocationDepth - 1; i > 0; --i ) {
671 // if the target (ith) node exists, clobber it
672 // whether the i-1 node exists or not
673 Integer idIth = as.getIthOldest( i );
674 if( id2hrn.containsKey( idIth ) ) {
675 HeapRegionNode hrnI = id2hrn.get( idIth );
677 // clear all references in and out
682 // only do the transfer if the i-1 node exists
683 Integer idImin1th = as.getIthOldest( i - 1 );
684 if( id2hrn.containsKey( idImin1th ) ) {
685 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
686 if( hrnImin1.isWiped() ) {
687 // there is no info on this node, just skip
691 // either retrieve or make target of transfer
692 HeapRegionNode hrnI = getIthNode( as, i, false );
694 transferOnto( hrnImin1, hrnI );
699 // as stated above, the newest node should have had its
700 // references moved over to the second oldest, so we wipe newest
701 // in preparation for being the new object to assign something to
702 HeapRegionNode hrn0 = getIthNode( as, 0, false );
705 // now tokens in reachability sets need to "age" also
706 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
707 while( itrAllVariableNodes.hasNext() ) {
708 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
709 VariableNode ln = (VariableNode) me.getValue();
711 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
712 while( itrEdges.hasNext() ) {
713 ageTuplesFrom( as, itrEdges.next() );
717 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
718 while( itrAllHRNodes.hasNext() ) {
719 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
720 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
722 ageTuplesFrom( as, hrnToAge );
724 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
725 while( itrEdges.hasNext() ) {
726 ageTuplesFrom( as, itrEdges.next() );
731 // after tokens have been aged, reset newest node's reachability
732 // and a brand new node has a "true" predicate
733 hrn0.setAlpha( hrn0.getInherent() );
734 hrn0.setPreds( predsTrue );
738 // either retrieve or create the needed heap region node
739 protected HeapRegionNode getSummaryNode( AllocSite as,
744 idSummary = as.getSummaryShadow();
746 idSummary = as.getSummary();
749 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
751 if( hrnSummary == null ) {
753 boolean hasFlags = false;
754 if( as.getType().isClass() ) {
755 hasFlags = as.getType().getClassDesc().hasFlags();
759 hasFlags = as.getFlag();
762 String strDesc = as.toStringForDOT()+"\\nsummary";
764 strDesc += " shadow";
768 createNewHeapRegionNode( idSummary, // id or null to generate a new one
769 false, // single object?
771 hasFlags, // flagged?
772 false, // out-of-context?
773 as.getType(), // type
774 as, // allocation site
775 null, // inherent reach
776 null, // current reach
777 predsEmpty, // predicates
778 strDesc // description
785 // either retrieve or create the needed heap region node
786 protected HeapRegionNode getIthNode( AllocSite as,
792 idIth = as.getIthOldestShadow( i );
794 idIth = as.getIthOldest( i );
797 HeapRegionNode hrnIth = id2hrn.get( idIth );
799 if( hrnIth == null ) {
801 boolean hasFlags = false;
802 if( as.getType().isClass() ) {
803 hasFlags = as.getType().getClassDesc().hasFlags();
807 hasFlags = as.getFlag();
810 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
812 strDesc += " shadow";
815 hrnIth = createNewHeapRegionNode( idIth, // id or null to generate a new one
816 true, // single object?
818 hasFlags, // flagged?
819 false, // out-of-context?
820 as.getType(), // type
821 as, // allocation site
822 null, // inherent reach
823 null, // current reach
824 predsEmpty, // predicates
825 strDesc // description
833 // used to assert that the given node object
834 // belongs to THIS graph instance, some gross bugs
835 // have popped up where a node from one graph works
836 // itself into another
837 public boolean belongsToThis( HeapRegionNode hrn ) {
838 return this.id2hrn.get( hrn.getID() ) == hrn;
841 protected void mergeIntoSummary( HeapRegionNode hrn,
842 HeapRegionNode hrnSummary ) {
843 assert hrnSummary.isNewSummary();
845 // assert that these nodes belong to THIS graph
846 assert belongsToThis( hrn );
847 assert belongsToThis( hrnSummary );
849 // transfer references _from_ hrn over to hrnSummary
850 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
851 while( itrReferencee.hasNext() ) {
852 RefEdge edge = itrReferencee.next();
853 RefEdge edgeMerged = edge.copy();
854 edgeMerged.setSrc( hrnSummary );
856 HeapRegionNode hrnReferencee = edge.getDst();
857 RefEdge edgeSummary =
858 hrnSummary.getReferenceTo( hrnReferencee,
863 if( edgeSummary == null ) {
864 // the merge is trivial, nothing to be done
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()
874 Canonical.join( edgeMerged.getPreds(),
875 edgeSummary.getPreds()
880 addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
883 // next transfer references _to_ hrn over to hrnSummary
884 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
885 while( itrReferencer.hasNext() ) {
886 RefEdge edge = itrReferencer.next();
887 RefEdge edgeMerged = edge.copy();
888 edgeMerged.setDst( hrnSummary );
890 RefSrcNode onReferencer = edge.getSrc();
891 RefEdge edgeSummary =
892 onReferencer.getReferenceTo( hrnSummary,
897 if( edgeSummary == null ) {
898 // the merge is trivial, nothing to be done
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()
908 Canonical.join( edgeMerged.getPreds(),
909 edgeSummary.getPreds()
914 addRefEdge( onReferencer, hrnSummary, edgeMerged );
917 // then merge hrn reachability into hrnSummary
919 Canonical.union( hrnSummary.getAlpha(),
924 // and afterward, this node is gone
929 protected void transferOnto( HeapRegionNode hrnA,
930 HeapRegionNode hrnB ) {
932 assert belongsToThis( hrnA );
933 assert belongsToThis( hrnB );
935 // clear references in and out of node b
936 assert hrnB.isWiped();
938 // copy each edge in and out of A to B
939 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
940 while( itrReferencee.hasNext() ) {
941 RefEdge edge = itrReferencee.next();
942 HeapRegionNode hrnReferencee = edge.getDst();
943 RefEdge edgeNew = edge.copy();
944 edgeNew.setSrc( hrnB );
945 edgeNew.setDst( hrnReferencee );
947 addRefEdge( hrnB, hrnReferencee, edgeNew );
950 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
951 while( itrReferencer.hasNext() ) {
952 RefEdge edge = itrReferencer.next();
953 RefSrcNode onReferencer = edge.getSrc();
954 RefEdge edgeNew = edge.copy();
955 edgeNew.setDst( hrnB );
956 edgeNew.setDst( hrnB );
958 addRefEdge( onReferencer, hrnB, edgeNew );
961 // replace hrnB reachability and preds with hrnA's
962 hrnB.setAlpha( hrnA.getAlpha() );
963 hrnB.setPreds( hrnA.getPreds() );
965 // after transfer, wipe out source
970 // the purpose of this method is to conceptually "wipe out"
971 // a heap region from the graph--purposefully not called REMOVE
972 // because the node is still hanging around in the graph, just
973 // not mechanically connected or have any reach or predicate
974 // information on it anymore--lots of ops can use this
975 protected void wipeOut( HeapRegionNode hrn ) {
977 assert belongsToThis( hrn );
979 clearRefEdgesFrom( hrn, null, null, true );
980 clearRefEdgesTo ( hrn, null, null, true );
981 hrn.setAlpha( rsetEmpty );
982 hrn.setPreds( predsEmpty );
986 protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
988 Canonical.ageTuplesFrom( edge.getBeta(),
994 protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
996 Canonical.ageTuplesFrom( hrn.getAlpha(),
1004 protected void propagateTokensOverNodes( HeapRegionNode nPrime,
1006 HashSet<HeapRegionNode> nodesWithNewAlpha,
1007 HashSet<RefEdge> edgesWithNewBeta ) {
1009 HashSet<HeapRegionNode> todoNodes
1010 = new HashSet<HeapRegionNode>();
1011 todoNodes.add( nPrime );
1013 HashSet<RefEdge> todoEdges
1014 = new HashSet<RefEdge>();
1016 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1017 = new Hashtable<HeapRegionNode, ChangeSet>();
1018 nodePlannedChanges.put( nPrime, c0 );
1020 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1021 = new Hashtable<RefEdge, ChangeSet>();
1023 // first propagate change sets everywhere they can go
1024 while( !todoNodes.isEmpty() ) {
1025 HeapRegionNode n = todoNodes.iterator().next();
1026 ChangeSet C = nodePlannedChanges.get( n );
1028 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1029 while( referItr.hasNext() ) {
1030 RefEdge edge = referItr.next();
1031 todoEdges.add( edge );
1033 if( !edgePlannedChanges.containsKey( edge ) ) {
1034 edgePlannedChanges.put( edge,
1039 edgePlannedChanges.put( edge,
1040 Canonical.union( edgePlannedChanges.get( edge ),
1046 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1047 while( refeeItr.hasNext() ) {
1048 RefEdge edgeF = refeeItr.next();
1049 HeapRegionNode m = edgeF.getDst();
1051 ChangeSet changesToPass = ChangeSet.factory();
1053 Iterator<ChangeTuple> itrCprime = C.iterator();
1054 while( itrCprime.hasNext() ) {
1055 ChangeTuple c = itrCprime.next();
1056 if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
1057 changesToPass = Canonical.union( changesToPass, c );
1061 if( !changesToPass.isEmpty() ) {
1062 if( !nodePlannedChanges.containsKey( m ) ) {
1063 nodePlannedChanges.put( m, ChangeSet.factory() );
1066 ChangeSet currentChanges = nodePlannedChanges.get( m );
1068 if( !changesToPass.isSubset( currentChanges ) ) {
1070 nodePlannedChanges.put( m,
1071 Canonical.union( currentChanges,
1080 todoNodes.remove( n );
1083 // then apply all of the changes for each node at once
1084 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1085 while( itrMap.hasNext() ) {
1086 Map.Entry me = (Map.Entry) itrMap.next();
1087 HeapRegionNode n = (HeapRegionNode) me.getKey();
1088 ChangeSet C = (ChangeSet) me.getValue();
1090 // this propagation step is with respect to one change,
1091 // so we capture the full change from the old alpha:
1092 ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1096 // but this propagation may be only one of many concurrent
1097 // possible changes, so keep a running union with the node's
1098 // partially updated new alpha set
1099 n.setAlphaNew( Canonical.union( n.getAlphaNew(),
1104 nodesWithNewAlpha.add( n );
1107 propagateTokensOverEdges( todoEdges,
1114 protected void propagateTokensOverEdges( HashSet <RefEdge> todoEdges,
1115 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1116 HashSet <RefEdge> edgesWithNewBeta ) {
1118 // first propagate all change tuples everywhere they can go
1119 while( !todoEdges.isEmpty() ) {
1120 RefEdge edgeE = todoEdges.iterator().next();
1121 todoEdges.remove( edgeE );
1123 if( !edgePlannedChanges.containsKey( edgeE ) ) {
1124 edgePlannedChanges.put( edgeE,
1129 ChangeSet C = edgePlannedChanges.get( edgeE );
1131 ChangeSet changesToPass = ChangeSet.factory();
1133 Iterator<ChangeTuple> itrC = C.iterator();
1134 while( itrC.hasNext() ) {
1135 ChangeTuple c = itrC.next();
1136 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1137 changesToPass = Canonical.union( changesToPass, c );
1141 RefSrcNode rsn = edgeE.getSrc();
1143 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1144 HeapRegionNode n = (HeapRegionNode) rsn;
1146 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1147 while( referItr.hasNext() ) {
1148 RefEdge edgeF = referItr.next();
1150 if( !edgePlannedChanges.containsKey( edgeF ) ) {
1151 edgePlannedChanges.put( edgeF,
1156 ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1158 if( !changesToPass.isSubset( currentChanges ) ) {
1159 todoEdges.add( edgeF );
1160 edgePlannedChanges.put( edgeF,
1161 Canonical.union( currentChanges,
1170 // then apply all of the changes for each edge at once
1171 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1172 while( itrMap.hasNext() ) {
1173 Map.Entry me = (Map.Entry) itrMap.next();
1174 RefEdge e = (RefEdge) me.getKey();
1175 ChangeSet C = (ChangeSet) me.getValue();
1177 // this propagation step is with respect to one change,
1178 // so we capture the full change from the old beta:
1179 ReachSet localDelta =
1180 Canonical.applyChangeSet( e.getBeta(),
1185 // but this propagation may be only one of many concurrent
1186 // possible changes, so keep a running union with the edge's
1187 // partially updated new beta set
1188 e.setBetaNew( Canonical.union( e.getBetaNew(),
1193 edgesWithNewBeta.add( e );
1199 // use this method to make a new reach graph that is
1200 // what heap the FlatMethod callee from the FlatCall
1201 // would start with reaching from its arguments in
1204 makeCalleeView( FlatCall fc,
1206 Set<Integer> callerNodeIDsCopiedToCallee,
1207 boolean writeDebugDOTs
1210 // the callee view is a new graph: DON'T MODIFY
1212 ReachGraph rg = new ReachGraph();
1214 // track what parts of this graph have already been
1215 // added to callee view, variables not needed.
1216 // Note that we need this because when we traverse
1217 // this caller graph for each parameter we may find
1218 // nodes and edges more than once (which the per-param
1219 // "visit" sets won't show) and we only want to create
1220 // an element in the new callee view one time
1223 // a conservative starting point is to take the
1224 // mechanically-reachable-from-arguments graph
1225 // as opposed to using reachability information
1226 // to prune the graph further
1227 for( int i = 0; i < fm.numParameters(); ++i ) {
1229 // for each parameter index, get the symbol in the
1230 // caller view and callee view
1232 // argument defined here is the symbol in the caller
1233 TempDescriptor tdArg = fc.getArgMatchingParamIndex( fm, i );
1235 // parameter defined here is the symbol in the callee
1236 TempDescriptor tdParam = fm.getParameter( i );
1238 // use these two VariableNode objects to translate
1239 // between caller and callee--its easy to compare
1240 // a HeapRegionNode across callee and caller because
1241 // they will have the same heap region ID
1242 VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
1243 VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
1245 // now traverse the calleR view using the argument to
1246 // build the calleE view which has the parameter symbol
1247 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1248 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1249 toVisitInCaller.add( vnCaller );
1251 while( !toVisitInCaller.isEmpty() ) {
1252 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1253 RefSrcNode rsnCallee;
1255 toVisitInCaller.remove( rsnCaller );
1256 visitedInCaller.add( rsnCaller );
1258 // FIRST - setup the source end of an edge, and
1259 // remember the identifying info of the source
1260 // to build predicates
1261 TempDescriptor tdSrc = null;
1262 Integer hrnSrcID = null;
1264 if( rsnCaller == vnCaller ) {
1265 // if the caller node is the param symbol, we
1266 // have to do this translation for the callee
1267 rsnCallee = vnCallee;
1271 // otherwise the callee-view node is a heap
1272 // region with the same ID, that may or may
1273 // not have been created already
1274 assert rsnCaller instanceof HeapRegionNode;
1276 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1277 hrnSrcID = hrnSrcCaller.getID();
1279 if( !callerNodeIDsCopiedToCallee.contains( hrnSrcID ) ) {
1282 ExistPred.factory( hrnSrcID, null );
1284 ExistPredSet preds =
1285 ExistPredSet.factory( pred );
1288 rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
1289 hrnSrcCaller.isSingleObject(),
1290 hrnSrcCaller.isNewSummary(),
1291 hrnSrcCaller.isFlagged(),
1292 false, // out-of-context?
1293 hrnSrcCaller.getType(),
1294 hrnSrcCaller.getAllocSite(),
1295 /*toShadowTokens( this,*/ hrnSrcCaller.getInherent() /*)*/,
1296 /*toShadowTokens( this,*/ hrnSrcCaller.getAlpha() /*)*/,
1298 hrnSrcCaller.getDescription()
1301 callerNodeIDsCopiedToCallee.add( hrnSrcID );
1304 rsnCallee = rg.id2hrn.get( hrnSrcID );
1308 // SECOND - go over all edges from that source
1310 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1311 while( itrRefEdges.hasNext() ) {
1312 RefEdge reCaller = itrRefEdges.next();
1313 HeapRegionNode hrnCaller = reCaller.getDst();
1314 HeapRegionNode hrnCallee;
1316 // THIRD - setup destination ends of edges
1317 Integer hrnDstID = hrnCaller.getID();
1319 if( !callerNodeIDsCopiedToCallee.contains( hrnDstID ) ) {
1322 ExistPred.factory( hrnDstID, null );
1324 ExistPredSet preds =
1325 ExistPredSet.factory( pred );
1328 rg.createNewHeapRegionNode( hrnDstID,
1329 hrnCaller.isSingleObject(),
1330 hrnCaller.isNewSummary(),
1331 hrnCaller.isFlagged(),
1332 false, // out-of-context?
1333 hrnCaller.getType(),
1334 hrnCaller.getAllocSite(),
1335 /*toShadowTokens( this,*/ hrnCaller.getInherent() /*)*/,
1336 /*toShadowTokens( this,*/ hrnCaller.getAlpha() /*)*/,
1338 hrnCaller.getDescription()
1341 callerNodeIDsCopiedToCallee.add( hrnDstID );
1344 hrnCallee = rg.id2hrn.get( hrnDstID );
1347 // FOURTH - copy edge over if needed
1348 RefEdge reCallee = rsnCallee.getReferenceTo( hrnCallee,
1352 if( reCallee == null ) {
1355 ExistPred.factory( tdSrc,
1359 reCaller.getField(),
1362 ExistPredSet preds =
1363 ExistPredSet.factory( pred );
1365 rg.addRefEdge( rsnCallee,
1367 new RefEdge( rsnCallee,
1370 reCaller.getField(),
1371 /*toShadowTokens( this,*/ reCaller.getBeta() /*)*/,
1377 // keep traversing nodes reachable from param i
1378 // that we haven't visited yet
1379 if( !visitedInCaller.contains( hrnCaller ) ) {
1380 toVisitInCaller.add( hrnCaller );
1383 } // end edge iteration
1384 } // end visiting heap nodes in caller
1385 } // end iterating over parameters as starting points
1388 // find the set of edges in this graph with source
1389 // out-of-context (not in nodes copied) and have a
1390 // destination in context (one of nodes copied) as
1391 // a starting point for building out-of-context nodes
1392 Iterator<Integer> itrInContext =
1393 callerNodeIDsCopiedToCallee.iterator();
1394 while( itrInContext.hasNext() ) {
1395 Integer hrnID = itrInContext.next();
1396 HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1398 Iterator<RefEdge> itrMightCross =
1399 hrnCallerAndInContext.iteratorToReferencers();
1400 while( itrMightCross.hasNext() ) {
1401 RefEdge edgeMightCross = itrMightCross.next();
1403 // we're only interested in edges with a source
1404 // 1) is a heap region and...
1405 if( !(edgeMightCross.getSrc() instanceof HeapRegionNode) ) {
1410 HeapRegionNode hrnCallerAndOutContext =
1411 (HeapRegionNode) edgeMightCross.getSrc();
1413 // ... 2) is out of context
1414 if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() )
1420 // we found a reference that crosses from out-of-context
1421 // to in-context, so build a special out-of-context node
1422 // for the callee IHM and its reference edge
1423 HeapRegionNode hrnCalleeAndOutContext =
1424 rg.createNewHeapRegionNode( null, // ID
1425 false, // single object?
1426 false, // new summary?
1428 true, // out-of-context?
1429 hrnCallerAndOutContext.getType(),
1430 null, // alloc site, shouldn't be used
1431 /*toShadowTokens( this,*/ hrnCallerAndOutContext.getAlpha() /*)*/, // inherent
1432 /*toShadowTokens( this,*/ hrnCallerAndOutContext.getAlpha() /*)*/, // alpha
1437 HeapRegionNode hrnCalleeAndInContext =
1438 rg.id2hrn.get( hrnCallerAndInContext.getID() );
1440 rg.addRefEdge( hrnCalleeAndOutContext,
1441 hrnCalleeAndInContext,
1442 new RefEdge( hrnCalleeAndOutContext,
1443 hrnCalleeAndInContext,
1444 edgeMightCross.getType(),
1445 edgeMightCross.getField(),
1446 /*toShadowTokens( this,*/ edgeMightCross.getBeta() /*)*/,
1453 if( writeDebugDOTs ) {
1455 rg.writeGraph( "calleeview", true, false, false, false, true, true );
1456 } catch( IOException e ) {}
1465 resolveMethodCall( FlatCall fc,
1467 ReachGraph rgCallee,
1468 Set<Integer> callerNodeIDsCopiedToCallee,
1469 boolean writeDebugDOTs
1473 if( writeDebugDOTs ) {
1475 this.writeGraph( "caller",
1476 true, false, false, false, true, true,
1477 callerNodeIDsCopiedToCallee );
1478 rgCallee.writeGraph( "callee",
1479 true, false, false, false, true, true );
1480 } catch( IOException e ) {}
1484 // method call transfer function steps:
1485 // 1. Use current callee-reachable heap (CRH) to test callee
1486 // predicates and mark what will be coming in.
1487 // 2. Wipe CRH out of caller.
1488 // 3. Transplant marked callee parts in:
1489 // a) bring in nodes
1490 // b) bring in callee -> callee edges
1491 // c) resolve out-of-context -> callee edges
1492 // 4. Global sweep it.
1496 // 1. mark what callee elements have satisfied predicates
1497 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1498 new Hashtable<HeapRegionNode, ExistPredSet>();
1500 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1501 new Hashtable<RefEdge, ExistPredSet>();
1503 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1504 while( meItr.hasNext() ) {
1505 Map.Entry me = (Map.Entry) meItr.next();
1506 Integer id = (Integer) me.getKey();
1507 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1509 ExistPredSet predsIfSatis =
1510 hrnCallee.getPreds().isSatisfiedBy( this,
1511 callerNodeIDsCopiedToCallee
1513 if( predsIfSatis != null ) {
1514 calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1516 // otherwise don't bother looking at edges from this node
1520 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencees();
1521 while( reItr.hasNext() ) {
1522 RefEdge reCallee = reItr.next();
1524 ExistPredSet ifDst =
1525 reCallee.getDst().getPreds().isSatisfiedBy( this,
1526 callerNodeIDsCopiedToCallee
1528 if( ifDst == null ) {
1533 reCallee.getPreds().isSatisfiedBy( this,
1534 callerNodeIDsCopiedToCallee
1536 if( predsIfSatis != null ) {
1537 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
1542 // test param -> HRN edges, also
1543 for( int i = 0; i < fm.numParameters(); ++i ) {
1545 // parameter defined here is the symbol in the callee
1546 TempDescriptor tdParam = fm.getParameter( i );
1547 VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
1549 Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
1550 while( reItr.hasNext() ) {
1551 RefEdge reCallee = reItr.next();
1553 ExistPredSet ifDst =
1554 reCallee.getDst().getPreds().isSatisfiedBy( this,
1555 callerNodeIDsCopiedToCallee
1557 if( ifDst == null ) {
1561 ExistPredSet predsIfSatis =
1562 reCallee.getPreds().isSatisfiedBy( this,
1563 callerNodeIDsCopiedToCallee
1565 if( predsIfSatis != null ) {
1566 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
1573 // 2. predicates tested, ok to wipe out caller part
1574 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
1575 while( hrnItr.hasNext() ) {
1576 Integer hrnID = hrnItr.next();
1577 HeapRegionNode hrnCaller = id2hrn.get( hrnID );
1578 assert hrnCaller != null;
1579 wipeOut( hrnCaller );
1583 if( writeDebugDOTs ) {
1585 writeGraph( "callerWiped",
1586 true, false, false, false, true, true );
1587 } catch( IOException e ) {}
1592 // 3. callee elements with satisfied preds come in, note that
1593 // the mapping of elements satisfied to preds is like this:
1594 // A callee element EE has preds EEp that are satisfied by
1595 // some caller element ER. We bring EE into the caller
1596 // context as ERee with the preds of ER, namely ERp, which
1597 // in the following algorithm is the value in the mapping
1600 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
1601 while( satisItr.hasNext() ) {
1602 Map.Entry me = (Map.Entry) satisItr.next();
1603 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
1604 ExistPredSet preds = (ExistPredSet) me.getValue();
1606 if( hrnCallee.isOutOfContext() ) {
1610 AllocSite as = hrnCallee.getAllocSite();
1611 allocSites.add( as );
1613 Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
1615 HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
1616 if( hrnCaller == null ) {
1618 createNewHeapRegionNode( hrnIDshadow, // id or null to generate a new one
1619 hrnCallee.isSingleObject(), // single object?
1620 hrnCallee.isNewSummary(), // summary?
1621 hrnCallee.isFlagged(), // flagged?
1622 false, // out-of-context?
1623 hrnCallee.getType(), // type
1624 hrnCallee.getAllocSite(), // allocation site
1625 hrnCallee.getInherent(), // inherent reach
1626 null, // current reach
1627 predsEmpty, // predicates
1628 hrnCallee.getDescription() // description
1631 assert hrnCaller.isWiped();
1634 // TODO: alpha should be some rewritten version of callee in caller context
1635 hrnCaller.setAlpha( rsetEmpty );
1637 hrnCaller.setPreds( preds );
1641 // 3.b) callee -> callee edges
1642 satisItr = calleeEdgesSatisfied.entrySet().iterator();
1643 while( satisItr.hasNext() ) {
1644 Map.Entry me = (Map.Entry) satisItr.next();
1645 RefEdge reCallee = (RefEdge) me.getKey();
1646 ExistPredSet preds = (ExistPredSet) me.getValue();
1648 RefSrcNode rsnCallee = reCallee.getSrc();
1649 RefSrcNode rsnCaller;
1651 if( rsnCallee instanceof VariableNode ) {
1652 VariableNode vnCallee = (VariableNode) rsnCallee;
1653 TempDescriptor tdParam = vnCallee.getTempDescriptor();
1654 TempDescriptor tdArg = fc.getArgMatchingParam( fm,
1656 if( tdArg == null ) {
1657 // this means the variable isn't a parameter, its local
1658 // to the callee so we ignore it in call site transfer
1662 rsnCaller = this.getVariableNodeFromTemp( tdArg );
1665 HeapRegionNode hrnSrcCallee = (HeapRegionNode) reCallee.getSrc();
1667 AllocSite asSrc = hrnSrcCallee.getAllocSite();
1668 allocSites.add( asSrc );
1670 Integer hrnIDSrcShadow = asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
1671 rsnCaller = id2hrn.get( hrnIDSrcShadow );
1674 assert rsnCaller != null;
1676 HeapRegionNode hrnDstCallee = reCallee.getDst();
1678 AllocSite asDst = hrnDstCallee.getAllocSite();
1679 allocSites.add( asDst );
1681 Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
1683 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
1684 assert hrnDstCaller != null;
1686 // TODO: beta rewrites
1687 RefEdge reCaller = new RefEdge( rsnCaller,
1690 reCallee.getField(),
1695 // look to see if an edge with same field exists
1696 // and merge with it, otherwise just add the edge
1697 RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
1701 if( edgeExisting != null ) {
1702 edgeExisting.setBeta(
1703 Canonical.union( edgeExisting.getBeta(),
1707 edgeExisting.setPreds(
1708 Canonical.join( edgeExisting.getPreds(),
1714 addRefEdge( rsnCaller, hrnDstCaller, reCaller );
1719 // 3.c) resolve out-of-context -> callee edges
1722 if( writeDebugDOTs ) {
1724 writeGraph( "callerBeforeCollapseShadow",
1725 true, false, false, false, true, true );
1726 } catch( IOException e ) {}
1731 // 3.d) merge shadow nodes so alloc sites are back to k
1732 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
1733 while( asItr.hasNext() ) {
1734 // for each allocation site do the following to merge
1735 // shadow nodes (newest from callee) with any existing
1736 // look for the newest normal and newest shadow "slot"
1737 // not being used, transfer normal to shadow. Keep
1738 // doing this until there are no more normal nodes, or
1739 // no empty shadow slots: then merge all remaining normal
1740 // nodes into the shadow summary. Finally, convert all
1741 // shadow to their normal versions.
1742 AllocSite as = asItr.next();
1745 while( ageNorm < allocationDepth &&
1746 ageShad < allocationDepth ) {
1748 // first, are there any normal nodes left?
1749 Integer idNorm = as.getIthOldest( ageNorm );
1750 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
1751 if( hrnNorm == null ) {
1752 // no, this age of normal node not in the caller graph
1757 // yes, a normal node exists, is there an empty shadow
1758 // "slot" to transfer it onto?
1759 HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
1760 if( !hrnShad.isWiped() ) {
1761 // no, this age of shadow node is not empty
1766 // yes, this shadow node is empty
1767 transferOnto( hrnNorm, hrnShad );
1772 // now, while there are still normal nodes but no shadow
1773 // slots, merge normal nodes into the shadow summary
1774 while( ageNorm < allocationDepth ) {
1776 // first, are there any normal nodes left?
1777 Integer idNorm = as.getIthOldest( ageNorm );
1778 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
1779 if( hrnNorm == null ) {
1780 // no, this age of normal node not in the caller graph
1785 // yes, a normal node exists, so get the shadow summary
1786 HeapRegionNode summShad = getSummaryNode( as, true );
1787 mergeIntoSummary( hrnNorm, summShad );
1791 // if there is a normal summary, merge it into shadow summary
1792 Integer idNorm = as.getSummary();
1793 HeapRegionNode summNorm = id2hrn.get( idNorm );
1794 if( summNorm != null ) {
1795 HeapRegionNode summShad = getSummaryNode( as, true );
1796 mergeIntoSummary( summNorm, summShad );
1799 // finally, flip all existing shadow nodes onto the normal
1800 for( int i = 0; i < allocationDepth; ++i ) {
1801 Integer idShad = as.getIthOldestShadow( i );
1802 HeapRegionNode hrnShad = id2hrn.get( idShad );
1803 if( hrnShad != null ) {
1805 HeapRegionNode hrnNorm = getIthNode( as, i, false );
1806 assert hrnNorm.isWiped();
1807 transferOnto( hrnShad, hrnNorm );
1811 Integer idShad = as.getSummaryShadow();
1812 HeapRegionNode summShad = id2hrn.get( idShad );
1813 if( summShad != null ) {
1814 summNorm = getSummaryNode( as, false );
1815 transferOnto( summNorm, summShad );
1825 if( writeDebugDOTs ) {
1827 writeGraph( "callerAfterTransfer",
1828 true, false, false, false, true, true );
1829 } catch( IOException e ) {}
1835 ////////////////////////////////////////////////////
1837 // Abstract garbage collection simply removes
1838 // heap region nodes that are not mechanically
1839 // reachable from a root set. This step is
1840 // essential for testing node and edge existence
1841 // predicates efficiently
1843 ////////////////////////////////////////////////////
1844 public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
1846 // calculate a root set, will be different for Java
1847 // version of analysis versus Bamboo version
1848 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
1850 // visit every variable in graph while building root
1851 // set, and do iterating on a copy, so we can remove
1852 // dead variables while we're at this
1853 Iterator makeCopyItr = td2vn.entrySet().iterator();
1854 Set entrysCopy = new HashSet();
1855 while( makeCopyItr.hasNext() ) {
1856 entrysCopy.add( makeCopyItr.next() );
1859 Iterator eItr = entrysCopy.iterator();
1860 while( eItr.hasNext() ) {
1861 Map.Entry me = (Map.Entry) eItr.next();
1862 TempDescriptor td = (TempDescriptor) me.getKey();
1863 VariableNode vn = (VariableNode) me.getValue();
1865 if( liveSet.contains( td ) ) {
1869 // dead var, remove completely from graph
1871 clearRefEdgesFrom( vn, null, null, true );
1875 // everything visited in a traversal is
1876 // considered abstractly live
1877 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
1879 while( !toVisit.isEmpty() ) {
1880 RefSrcNode rsn = toVisit.iterator().next();
1881 toVisit.remove( rsn );
1884 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
1885 while( hrnItr.hasNext() ) {
1886 RefEdge edge = hrnItr.next();
1887 HeapRegionNode hrn = edge.getDst();
1889 if( !visited.contains( hrn ) ) {
1895 // get a copy of the set to iterate over because
1896 // we're going to monkey with the graph when we
1897 // identify a garbage node
1898 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
1899 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
1900 while( hrnItr.hasNext() ) {
1901 hrnAllPrior.add( hrnItr.next() );
1904 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
1905 while( hrnAllItr.hasNext() ) {
1906 HeapRegionNode hrn = hrnAllItr.next();
1908 if( !visited.contains( hrn ) ) {
1910 // heap region nodes are compared across ReachGraph
1911 // objects by their integer ID, so when discarding
1912 // garbage nodes we must also discard entries in
1913 // the ID -> heap region hashtable.
1914 id2hrn.remove( hrn.getID() );
1916 // RefEdge objects are two-way linked between
1917 // nodes, so when a node is identified as garbage,
1918 // actively clear references to and from it so
1919 // live nodes won't have dangling RefEdge's
1922 // if we just removed the last node from an allocation
1923 // site, it should be taken out of the ReachGraph's list
1924 AllocSite as = hrn.getAllocSite();
1925 if( !hasNodesOf( as ) ) {
1926 allocSites.remove( as );
1932 protected boolean hasNodesOf( AllocSite as ) {
1933 if( id2hrn.containsKey( as.getSummary() ) ) {
1937 for( int i = 0; i < allocationDepth; ++i ) {
1938 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
1946 ////////////////////////////////////////////////////
1948 // This global sweep is an optional step to prune
1949 // reachability sets that are not internally
1950 // consistent with the global graph. It should be
1951 // invoked after strong updates or method calls.
1953 ////////////////////////////////////////////////////
1954 public void globalSweep() {
1956 // boldB is part of the phase 1 sweep
1957 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
1958 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
1960 // visit every heap region to initialize alphaNew and calculate boldB
1961 Iterator itrHrns = id2hrn.entrySet().iterator();
1962 while( itrHrns.hasNext() ) {
1963 Map.Entry me = (Map.Entry) itrHrns.next();
1964 Integer hrnID = (Integer) me.getKey();
1965 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1967 // assert that this node and incoming edges have clean alphaNew
1968 // and betaNew sets, respectively
1969 assert rsetEmpty.equals( hrn.getAlphaNew() );
1971 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
1972 while( itrRers.hasNext() ) {
1973 RefEdge edge = itrRers.next();
1974 assert rsetEmpty.equals( edge.getBetaNew() );
1977 // calculate boldB for this flagged node
1978 if( hrn.isFlagged() ) {
1980 Hashtable<RefEdge, ReachSet> boldB_f =
1981 new Hashtable<RefEdge, ReachSet>();
1983 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
1985 // initial boldB_f constraints
1986 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
1987 while( itrRees.hasNext() ) {
1988 RefEdge edge = itrRees.next();
1990 assert !boldB.containsKey( edge );
1991 boldB_f.put( edge, edge.getBeta() );
1993 assert !workSetEdges.contains( edge );
1994 workSetEdges.add( edge );
1997 // enforce the boldB_f constraint at edges until we reach a fixed point
1998 while( !workSetEdges.isEmpty() ) {
1999 RefEdge edge = workSetEdges.iterator().next();
2000 workSetEdges.remove( edge );
2002 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2003 while( itrPrime.hasNext() ) {
2004 RefEdge edgePrime = itrPrime.next();
2006 ReachSet prevResult = boldB_f.get( edgePrime );
2007 ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2011 if( prevResult == null ||
2012 Canonical.union( prevResult,
2013 intersection ).size() > prevResult.size() ) {
2015 if( prevResult == null ) {
2016 boldB_f.put( edgePrime,
2017 Canonical.union( edgePrime.getBeta(),
2022 boldB_f.put( edgePrime,
2023 Canonical.union( prevResult,
2028 workSetEdges.add( edgePrime );
2033 boldB.put( hrnID, boldB_f );
2038 // use boldB to prune hrnIDs from alpha states that are impossible
2039 // and propagate the differences backwards across edges
2040 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2042 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2043 new Hashtable<RefEdge, ChangeSet>();
2046 itrHrns = id2hrn.entrySet().iterator();
2047 while( itrHrns.hasNext() ) {
2048 Map.Entry me = (Map.Entry) itrHrns.next();
2049 Integer hrnID = (Integer) me.getKey();
2050 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2052 // create the inherent hrnID from a flagged region
2053 // as an exception to removal below
2054 ReachTuple rtException =
2055 ReachTuple.factory( hrnID,
2056 !hrn.isSingleObject(),
2057 ReachTuple.ARITY_ONE
2060 ChangeSet cts = ChangeSet.factory();
2062 // mark hrnIDs for removal
2063 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2064 while( stateItr.hasNext() ) {
2065 ReachState stateOld = stateItr.next();
2067 ReachState markedHrnIDs = ReachState.factory();
2069 Iterator<ReachTuple> rtItr = stateOld.iterator();
2070 while( rtItr.hasNext() ) {
2071 ReachTuple rtOld = rtItr.next();
2073 // never remove the inherent hrnID from a flagged region
2074 // because it is trivially satisfied
2075 if( hrn.isFlagged() ) {
2076 if( rtOld == rtException ) {
2081 // does boldB_ttOld allow this hrnID?
2082 boolean foundState = false;
2083 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2084 while( incidentEdgeItr.hasNext() ) {
2085 RefEdge incidentEdge = incidentEdgeItr.next();
2087 // if it isn't allowed, mark for removal
2088 Integer idOld = rtOld.getHrnID();
2089 assert id2hrn.containsKey( idOld );
2090 Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
2091 ReachSet boldB_ttOld_incident = B.get( incidentEdge );
2092 if( boldB_ttOld_incident != null &&
2093 boldB_ttOld_incident.contains( stateOld ) ) {
2099 markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
2103 // if there is nothing marked, just move on
2104 if( markedHrnIDs.isEmpty() ) {
2105 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2112 // remove all marked hrnIDs and establish a change set that should
2113 // propagate backwards over edges from this node
2114 ReachState statePruned = ReachState.factory();
2115 rtItr = stateOld.iterator();
2116 while( rtItr.hasNext() ) {
2117 ReachTuple rtOld = rtItr.next();
2119 if( !markedHrnIDs.containsTuple( rtOld ) ) {
2120 statePruned = Canonical.union( statePruned, rtOld );
2123 assert !stateOld.equals( statePruned );
2125 hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2129 ChangeTuple ct = ChangeTuple.factory( stateOld,
2132 cts = Canonical.union( cts, ct );
2135 // throw change tuple set on all incident edges
2136 if( !cts.isEmpty() ) {
2137 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2138 while( incidentEdgeItr.hasNext() ) {
2139 RefEdge incidentEdge = incidentEdgeItr.next();
2141 edgesForPropagation.add( incidentEdge );
2143 if( edgePlannedChanges.get( incidentEdge ) == null ) {
2144 edgePlannedChanges.put( incidentEdge, cts );
2146 edgePlannedChanges.put(
2148 Canonical.union( edgePlannedChanges.get( incidentEdge ),
2157 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2159 propagateTokensOverEdges( edgesForPropagation,
2163 // at the end of the 1st phase reference edges have
2164 // beta, betaNew that correspond to beta and betaR
2166 // commit beta<-betaNew, so beta=betaR and betaNew
2167 // will represent the beta' calculation in 2nd phase
2169 // commit alpha<-alphaNew because it won't change
2170 HashSet<RefEdge> res = new HashSet<RefEdge>();
2172 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2173 while( nodeItr.hasNext() ) {
2174 HeapRegionNode hrn = nodeItr.next();
2175 hrn.applyAlphaNew();
2176 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
2177 while( itrRes.hasNext() ) {
2178 res.add( itrRes.next() );
2184 Iterator<RefEdge> edgeItr = res.iterator();
2185 while( edgeItr.hasNext() ) {
2186 RefEdge edge = edgeItr.next();
2187 HeapRegionNode hrn = edge.getDst();
2189 // commit results of last phase
2190 if( edgesUpdated.contains( edge ) ) {
2191 edge.applyBetaNew();
2194 // compute intial condition of 2nd phase
2195 edge.setBetaNew( Canonical.intersection( edge.getBeta(),
2201 // every edge in the graph is the initial workset
2202 Set<RefEdge> edgeWorkSet = (Set) res.clone();
2203 while( !edgeWorkSet.isEmpty() ) {
2204 RefEdge edgePrime = edgeWorkSet.iterator().next();
2205 edgeWorkSet.remove( edgePrime );
2207 RefSrcNode rsn = edgePrime.getSrc();
2208 if( !(rsn instanceof HeapRegionNode) ) {
2211 HeapRegionNode hrn = (HeapRegionNode) rsn;
2213 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
2214 while( itrEdge.hasNext() ) {
2215 RefEdge edge = itrEdge.next();
2217 ReachSet prevResult = edge.getBetaNew();
2218 assert prevResult != null;
2220 ReachSet intersection =
2221 Canonical.intersection( edge.getBeta(),
2222 edgePrime.getBetaNew()
2225 if( Canonical.union( prevResult,
2227 ).size() > prevResult.size() ) {
2229 Canonical.union( prevResult,
2233 edgeWorkSet.add( edge );
2238 // commit beta' (beta<-betaNew)
2239 edgeItr = res.iterator();
2240 while( edgeItr.hasNext() ) {
2241 edgeItr.next().applyBetaNew();
2247 ////////////////////////////////////////////////////
2248 // high-level merge operations
2249 ////////////////////////////////////////////////////
2250 public void merge_sameMethodContext( ReachGraph rg ) {
2251 // when merging two graphs that abstract the heap
2252 // of the same method context, we just call the
2253 // basic merge operation
2257 public void merge_diffMethodContext( ReachGraph rg ) {
2258 // when merging graphs for abstract heaps in
2259 // different method contexts we should:
2260 // 1) age the allocation sites?
2264 ////////////////////////////////////////////////////
2265 // in merge() and equals() methods the suffix A
2266 // represents the passed in graph and the suffix
2267 // B refers to the graph in this object
2268 // Merging means to take the incoming graph A and
2269 // merge it into B, so after the operation graph B
2270 // is the final result.
2271 ////////////////////////////////////////////////////
2272 protected void merge( ReachGraph rg ) {
2279 mergeRefEdges ( rg );
2280 mergeAllocSites( rg );
2283 protected void mergeNodes( ReachGraph rg ) {
2285 // start with heap region nodes
2286 Set sA = rg.id2hrn.entrySet();
2287 Iterator iA = sA.iterator();
2288 while( iA.hasNext() ) {
2289 Map.Entry meA = (Map.Entry) iA.next();
2290 Integer idA = (Integer) meA.getKey();
2291 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2293 // if this graph doesn't have a node the
2294 // incoming graph has, allocate it
2295 if( !id2hrn.containsKey( idA ) ) {
2296 HeapRegionNode hrnB = hrnA.copy();
2297 id2hrn.put( idA, hrnB );
2300 // otherwise this is a node present in both graphs
2301 // so make the new reachability set a union of the
2302 // nodes' reachability sets
2303 HeapRegionNode hrnB = id2hrn.get( idA );
2304 hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
2309 // if hrnB is already dirty or hrnA is dirty,
2310 // the hrnB should end up dirty: TODO
2312 if( !hrnA.isClean() ) {
2313 hrnB.setIsClean( false );
2319 // now add any variable nodes that are in graph B but
2321 sA = rg.td2vn.entrySet();
2323 while( iA.hasNext() ) {
2324 Map.Entry meA = (Map.Entry) iA.next();
2325 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2326 VariableNode lnA = (VariableNode) meA.getValue();
2328 // if the variable doesn't exist in B, allocate and add it
2329 VariableNode lnB = getVariableNodeFromTemp( tdA );
2333 protected void mergeRefEdges( ReachGraph rg ) {
2335 // between heap regions
2336 Set sA = rg.id2hrn.entrySet();
2337 Iterator iA = sA.iterator();
2338 while( iA.hasNext() ) {
2339 Map.Entry meA = (Map.Entry) iA.next();
2340 Integer idA = (Integer) meA.getKey();
2341 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2343 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2344 while( heapRegionsItrA.hasNext() ) {
2345 RefEdge edgeA = heapRegionsItrA.next();
2346 HeapRegionNode hrnChildA = edgeA.getDst();
2347 Integer idChildA = hrnChildA.getID();
2349 // at this point we know an edge in graph A exists
2350 // idA -> idChildA, does this exist in B?
2351 assert id2hrn.containsKey( idA );
2352 HeapRegionNode hrnB = id2hrn.get( idA );
2353 RefEdge edgeToMerge = null;
2355 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2356 while( heapRegionsItrB.hasNext() &&
2357 edgeToMerge == null ) {
2359 RefEdge edgeB = heapRegionsItrB.next();
2360 HeapRegionNode hrnChildB = edgeB.getDst();
2361 Integer idChildB = hrnChildB.getID();
2363 // don't use the RefEdge.equals() here because
2364 // we're talking about existence between graphs,
2365 // not intragraph equal
2366 if( idChildB.equals( idChildA ) &&
2367 edgeB.typeAndFieldEquals( edgeA ) ) {
2369 edgeToMerge = edgeB;
2373 // if the edge from A was not found in B,
2375 if( edgeToMerge == null ) {
2376 assert id2hrn.containsKey( idChildA );
2377 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2378 edgeToMerge = edgeA.copy();
2379 edgeToMerge.setSrc( hrnB );
2380 edgeToMerge.setDst( hrnChildB );
2381 addRefEdge( hrnB, hrnChildB, edgeToMerge );
2383 // otherwise, the edge already existed in both graphs
2384 // so merge their reachability sets
2386 // just replace this beta set with the union
2387 assert edgeToMerge != null;
2388 edgeToMerge.setBeta(
2389 Canonical.union( edgeToMerge.getBeta(),
2395 if( !edgeA.isClean() ) {
2396 edgeToMerge.setIsClean( false );
2403 // and then again from variable nodes
2404 sA = rg.td2vn.entrySet();
2406 while( iA.hasNext() ) {
2407 Map.Entry meA = (Map.Entry) iA.next();
2408 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2409 VariableNode vnA = (VariableNode) meA.getValue();
2411 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
2412 while( heapRegionsItrA.hasNext() ) {
2413 RefEdge edgeA = heapRegionsItrA.next();
2414 HeapRegionNode hrnChildA = edgeA.getDst();
2415 Integer idChildA = hrnChildA.getID();
2417 // at this point we know an edge in graph A exists
2418 // tdA -> idChildA, does this exist in B?
2419 assert td2vn.containsKey( tdA );
2420 VariableNode vnB = td2vn.get( tdA );
2421 RefEdge edgeToMerge = null;
2423 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
2424 while( heapRegionsItrB.hasNext() &&
2425 edgeToMerge == null ) {
2427 RefEdge edgeB = heapRegionsItrB.next();
2428 HeapRegionNode hrnChildB = edgeB.getDst();
2429 Integer idChildB = hrnChildB.getID();
2431 // don't use the RefEdge.equals() here because
2432 // we're talking about existence between graphs
2433 if( idChildB.equals( idChildA ) &&
2434 edgeB.typeAndFieldEquals( edgeA ) ) {
2436 edgeToMerge = edgeB;
2440 // if the edge from A was not found in B,
2442 if( edgeToMerge == null ) {
2443 assert id2hrn.containsKey( idChildA );
2444 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2445 edgeToMerge = edgeA.copy();
2446 edgeToMerge.setSrc( vnB );
2447 edgeToMerge.setDst( hrnChildB );
2448 addRefEdge( vnB, hrnChildB, edgeToMerge );
2450 // otherwise, the edge already existed in both graphs
2451 // so merge their reachability sets
2453 // just replace this beta set with the union
2454 edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
2460 if( !edgeA.isClean() ) {
2461 edgeToMerge.setIsClean( false );
2469 protected void mergeAllocSites( ReachGraph rg ) {
2470 allocSites.addAll( rg.allocSites );
2474 // it is necessary in the equals() member functions
2475 // to "check both ways" when comparing the data
2476 // structures of two graphs. For instance, if all
2477 // edges between heap region nodes in graph A are
2478 // present and equal in graph B it is not sufficient
2479 // to say the graphs are equal. Consider that there
2480 // may be edges in graph B that are not in graph A.
2481 // the only way to know that all edges in both graphs
2482 // are equally present is to iterate over both data
2483 // structures and compare against the other graph.
2484 public boolean equals( ReachGraph rg ) {
2490 if( !areHeapRegionNodesEqual( rg ) ) {
2494 if( !areVariableNodesEqual( rg ) ) {
2498 if( !areRefEdgesEqual( rg ) ) {
2502 // if everything is equal up to this point,
2503 // assert that allocSites is also equal--
2504 // this data is redundant but kept for efficiency
2505 assert allocSites.equals( rg.allocSites );
2511 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
2513 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
2517 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
2524 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
2526 Set sA = rgA.id2hrn.entrySet();
2527 Iterator iA = sA.iterator();
2528 while( iA.hasNext() ) {
2529 Map.Entry meA = (Map.Entry) iA.next();
2530 Integer idA = (Integer) meA.getKey();
2531 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2533 if( !rgB.id2hrn.containsKey( idA ) ) {
2537 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2538 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
2547 protected boolean areVariableNodesEqual( ReachGraph rg ) {
2549 if( !areallVNinAalsoinBandequal( this, rg ) ) {
2553 if( !areallVNinAalsoinBandequal( rg, this ) ) {
2560 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
2562 Set sA = rgA.td2vn.entrySet();
2563 Iterator iA = sA.iterator();
2564 while( iA.hasNext() ) {
2565 Map.Entry meA = (Map.Entry) iA.next();
2566 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2568 if( !rgB.td2vn.containsKey( tdA ) ) {
2577 protected boolean areRefEdgesEqual( ReachGraph rg ) {
2578 if( !areallREinAandBequal( this, rg ) ) {
2585 static protected boolean areallREinAandBequal( ReachGraph rgA,
2588 // check all the heap region->heap region edges
2589 Set sA = rgA.id2hrn.entrySet();
2590 Iterator iA = sA.iterator();
2591 while( iA.hasNext() ) {
2592 Map.Entry meA = (Map.Entry) iA.next();
2593 Integer idA = (Integer) meA.getKey();
2594 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2596 // we should have already checked that the same
2597 // heap regions exist in both graphs
2598 assert rgB.id2hrn.containsKey( idA );
2600 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
2604 // then check every edge in B for presence in A, starting
2605 // from the same parent HeapRegionNode
2606 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2608 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
2613 // then check all the variable->heap region edges
2614 sA = rgA.td2vn.entrySet();
2616 while( iA.hasNext() ) {
2617 Map.Entry meA = (Map.Entry) iA.next();
2618 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2619 VariableNode vnA = (VariableNode) meA.getValue();
2621 // we should have already checked that the same
2622 // label nodes exist in both graphs
2623 assert rgB.td2vn.containsKey( tdA );
2625 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
2629 // then check every edge in B for presence in A, starting
2630 // from the same parent VariableNode
2631 VariableNode vnB = rgB.td2vn.get( tdA );
2633 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
2642 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
2646 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
2647 while( itrA.hasNext() ) {
2648 RefEdge edgeA = itrA.next();
2649 HeapRegionNode hrnChildA = edgeA.getDst();
2650 Integer idChildA = hrnChildA.getID();
2652 assert rgB.id2hrn.containsKey( idChildA );
2654 // at this point we know an edge in graph A exists
2655 // rnA -> idChildA, does this exact edge exist in B?
2656 boolean edgeFound = false;
2658 RefSrcNode rnB = null;
2659 if( rnA instanceof HeapRegionNode ) {
2660 HeapRegionNode hrnA = (HeapRegionNode) rnA;
2661 rnB = rgB.id2hrn.get( hrnA.getID() );
2663 VariableNode vnA = (VariableNode) rnA;
2664 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
2667 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
2668 while( itrB.hasNext() ) {
2669 RefEdge edgeB = itrB.next();
2670 HeapRegionNode hrnChildB = edgeB.getDst();
2671 Integer idChildB = hrnChildB.getID();
2673 if( idChildA.equals( idChildB ) &&
2674 edgeA.typeAndFieldEquals( edgeB ) ) {
2676 // there is an edge in the right place with the right field,
2677 // but do they have the same attributes?
2678 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
2679 edgeA.equalsPreds( edgeB )
2696 // this analysis no longer has the "match anything"
2697 // type which was represented by null
2698 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2699 TypeDescriptor td2 ) {
2703 if( td1.isNull() ) {
2706 if( td2.isNull() ) {
2709 return typeUtil.mostSpecific( td1, td2 );
2712 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2714 TypeDescriptor td3 ) {
2716 return mostSpecificType( td1,
2717 mostSpecificType( td2, td3 )
2721 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2724 TypeDescriptor td4 ) {
2726 return mostSpecificType( mostSpecificType( td1, td2 ),
2727 mostSpecificType( td3, td4 )
2731 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
2732 TypeDescriptor possibleChild ) {
2733 assert possibleSuper != null;
2734 assert possibleChild != null;
2736 if( possibleSuper.isNull() ||
2737 possibleChild.isNull() ) {
2741 return typeUtil.isSuperorType( possibleSuper, possibleChild );
2745 protected boolean hasMatchingField( HeapRegionNode src,
2748 TypeDescriptor tdSrc = src.getType();
2749 assert tdSrc != null;
2751 if( tdSrc.isArray() ) {
2752 TypeDescriptor td = edge.getType();
2755 TypeDescriptor tdSrcDeref = tdSrc.dereference();
2756 assert tdSrcDeref != null;
2758 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
2762 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
2765 // if it's not a class, it doesn't have any fields to match
2766 if( !tdSrc.isClass() ) {
2770 ClassDescriptor cd = tdSrc.getClassDesc();
2771 while( cd != null ) {
2772 Iterator fieldItr = cd.getFields();
2774 while( fieldItr.hasNext() ) {
2775 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
2777 if( fd.getType().equals( edge.getType() ) &&
2778 fd.getSymbol().equals( edge.getField() ) ) {
2783 cd = cd.getSuperDesc();
2786 // otherwise it is a class with fields
2787 // but we didn't find a match
2791 protected boolean hasMatchingType( RefEdge edge,
2792 HeapRegionNode dst ) {
2794 // if the region has no type, matches everything
2795 TypeDescriptor tdDst = dst.getType();
2796 assert tdDst != null;
2798 // if the type is not a class or an array, don't
2799 // match because primitives are copied, no aliases
2800 ClassDescriptor cdDst = tdDst.getClassDesc();
2801 if( cdDst == null && !tdDst.isArray() ) {
2805 // if the edge type is null, it matches everything
2806 TypeDescriptor tdEdge = edge.getType();
2807 assert tdEdge != null;
2809 return typeUtil.isSuperorType( tdEdge, tdDst );
2814 public void writeGraph( String graphName,
2815 boolean writeLabels,
2816 boolean labelSelect,
2817 boolean pruneGarbage,
2818 boolean writeReferencers,
2819 boolean hideSubsetReachability,
2820 boolean hideEdgeTaints
2821 ) throws java.io.IOException {
2822 writeGraph( graphName,
2827 hideSubsetReachability,
2832 public void writeGraph( String graphName,
2833 boolean writeLabels,
2834 boolean labelSelect,
2835 boolean pruneGarbage,
2836 boolean writeReferencers,
2837 boolean hideSubsetReachability,
2838 boolean hideEdgeTaints,
2839 Set<Integer> callerNodeIDsCopiedToCallee
2840 ) throws java.io.IOException {
2842 // remove all non-word characters from the graph name so
2843 // the filename and identifier in dot don't cause errors
2844 graphName = graphName.replaceAll( "[\\W]", "" );
2847 new BufferedWriter( new FileWriter( graphName+".dot" ) );
2849 bw.write( "digraph "+graphName+" {\n" );
2852 // this is an optional step to form the callee-reachable
2853 // "cut-out" into a DOT cluster for visualization
2854 if( callerNodeIDsCopiedToCallee != null ) {
2856 bw.write( " subgraph cluster0 {\n" );
2857 bw.write( " color=blue;\n" );
2859 Iterator i = id2hrn.entrySet().iterator();
2860 while( i.hasNext() ) {
2861 Map.Entry me = (Map.Entry) i.next();
2862 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2864 if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
2865 bw.write( " "+hrn.toString()+
2866 hrn.toStringDOT( hideSubsetReachability )+
2876 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2878 // then visit every heap region node
2879 Iterator i = id2hrn.entrySet().iterator();
2880 while( i.hasNext() ) {
2881 Map.Entry me = (Map.Entry) i.next();
2882 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2884 // only visit nodes worth writing out--for instance
2885 // not every node at an allocation is referenced
2886 // (think of it as garbage-collected), etc.
2887 if( !pruneGarbage ||
2888 (hrn.isFlagged() && hrn.getID() > 0) ||
2889 hrn.getDescription().startsWith( "param" ) ||
2890 hrn.isOutOfContext()
2893 if( !visited.contains( hrn ) ) {
2894 traverseHeapRegionNodes( hrn,
2899 hideSubsetReachability,
2901 callerNodeIDsCopiedToCallee );
2906 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
2909 // then visit every label node, useful for debugging
2911 i = td2vn.entrySet().iterator();
2912 while( i.hasNext() ) {
2913 Map.Entry me = (Map.Entry) i.next();
2914 VariableNode vn = (VariableNode) me.getValue();
2917 String labelStr = vn.getTempDescriptorString();
2918 if( labelStr.startsWith("___temp") ||
2919 labelStr.startsWith("___dst") ||
2920 labelStr.startsWith("___srctmp") ||
2921 labelStr.startsWith("___neverused")
2927 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
2928 while( heapRegionsItr.hasNext() ) {
2929 RefEdge edge = heapRegionsItr.next();
2930 HeapRegionNode hrn = edge.getDst();
2932 if( pruneGarbage && !visited.contains( hrn ) ) {
2933 traverseHeapRegionNodes( hrn,
2938 hideSubsetReachability,
2940 callerNodeIDsCopiedToCallee );
2943 bw.write( " "+vn.toString()+
2944 " -> "+hrn.toString()+
2945 edge.toStringDOT( hideSubsetReachability, "" )+
2955 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
2958 Set<HeapRegionNode> visited,
2959 boolean writeReferencers,
2960 boolean hideSubsetReachability,
2961 boolean hideEdgeTaints,
2962 Set<Integer> callerNodeIDsCopiedToCallee
2963 ) throws java.io.IOException {
2965 if( visited.contains( hrn ) ) {
2970 // if we're drawing the callee-view subgraph, only
2971 // write out the node info if it hasn't already been
2973 if( callerNodeIDsCopiedToCallee == null ||
2974 !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
2976 bw.write( " "+hrn.toString()+
2977 hrn.toStringDOT( hideSubsetReachability )+
2981 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
2982 while( childRegionsItr.hasNext() ) {
2983 RefEdge edge = childRegionsItr.next();
2984 HeapRegionNode hrnChild = edge.getDst();
2986 if( callerNodeIDsCopiedToCallee != null &&
2987 (edge.getSrc() instanceof HeapRegionNode) ) {
2988 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
2989 if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
2990 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
2992 bw.write( " "+hrn.toString()+
2993 " -> "+hrnChild.toString()+
2994 edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
2996 } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
2997 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
2999 bw.write( " "+hrn.toString()+
3000 " -> "+hrnChild.toString()+
3001 edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
3004 bw.write( " "+hrn.toString()+
3005 " -> "+hrnChild.toString()+
3006 edge.toStringDOT( hideSubsetReachability, "" )+
3010 bw.write( " "+hrn.toString()+
3011 " -> "+hrnChild.toString()+
3012 edge.toStringDOT( hideSubsetReachability, "" )+
3016 traverseHeapRegionNodes( hrnChild,
3021 hideSubsetReachability,
3023 callerNodeIDsCopiedToCallee );