1 package Analysis.Disjoint;
5 import Util.UtilAlgorithms;
9 public class ReachGraph {
11 protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
13 // some frequently used reachability constants
14 protected static final ReachState rstateEmpty = new ReachState().makeCanonical();
15 protected static final ReachSet rsetEmpty = new ReachSet().makeCanonical();
16 protected static final ReachSet rsetWithEmptyState = new ReachSet( rstateEmpty ).makeCanonical();
18 public Hashtable<Integer, HeapRegionNode> id2hrn;
19 public Hashtable<TempDescriptor, VariableNode > td2vn;
21 public HashSet<AllocSite> allocSites;
23 // this is kept to allow edges created from variables (a src and dst)
24 // to know the access paths that allowed it, to prune edges when
25 // mapping them back into the caller--an access path must appear
26 public Hashtable< TempDescriptor, Set<AccessPath> > temp2accessPaths;
29 // use to disable improvements for comparison
30 protected static final boolean DISABLE_STRONG_UPDATES = false;
31 protected static final boolean DISABLE_GLOBAL_SWEEP = true;
33 protected static int allocationDepth = -1;
34 protected static TypeUtil typeUtil = null;
35 protected static boolean debugCallMap = false;
36 protected static int debugCallMapCount = 0;
37 protected static String debugCallee = null;
38 protected static String debugCaller = null;
42 id2hrn = new Hashtable<Integer, HeapRegionNode>();
43 td2vn = new Hashtable<TempDescriptor, VariableNode >();
45 allocSites = new HashSet<AllocSite>();
48 new Hashtable< TempDescriptor, Set<AccessPath> >();
52 // temp descriptors are globally unique and maps to
53 // exactly one variable node, easy
54 protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
57 if( !td2vn.containsKey( td ) ) {
58 td2vn.put( td, new VariableNode( td ) );
61 return td2vn.get( td );
64 public boolean hasVariable( TempDescriptor td ) {
65 return td2vn.containsKey( td );
69 // the reason for this method is to have the option
70 // of creating new heap regions with specific IDs, or
71 // duplicating heap regions with specific IDs (especially
72 // in the merge() operation) or to create new heap
73 // regions with a new unique ID
74 protected HeapRegionNode
75 createNewHeapRegionNode( Integer id,
76 boolean isSingleObject,
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( alpha == null ) {
104 if( markForAnalysis ) {
105 alpha = new ReachSet(
112 alpha = rsetWithEmptyState;
116 HeapRegionNode hrn = new HeapRegionNode( id,
124 id2hrn.put( id, hrn );
130 ////////////////////////////////////////////////
132 // Low-level referencee and referencer methods
134 // These methods provide the lowest level for
135 // creating references between reachability nodes
136 // and handling the details of maintaining both
137 // list of referencers and referencees.
139 ////////////////////////////////////////////////
140 protected void addRefEdge( RefSrcNode referencer,
141 HeapRegionNode referencee,
143 assert referencer != null;
144 assert referencee != null;
146 assert edge.getSrc() == referencer;
147 assert edge.getDst() == referencee;
149 referencer.addReferencee( edge );
150 referencee.addReferencer( edge );
153 protected void removeRefEdge( RefEdge e ) {
154 removeRefEdge( e.getSrc(),
160 protected void removeRefEdge( RefSrcNode referencer,
161 HeapRegionNode referencee,
164 assert referencer != null;
165 assert referencee != null;
167 RefEdge edge = referencer.getReferenceTo( referencee,
171 assert edge == referencee.getReferenceFrom( referencer,
175 referencer.removeReferencee( edge );
176 referencee.removeReferencer( edge );
179 protected void clearRefEdgesFrom( RefSrcNode referencer,
182 boolean removeAll ) {
183 assert referencer != null;
185 // get a copy of the set to iterate over, otherwise
186 // we will be trying to take apart the set as we
187 // are iterating over it, which won't work
188 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
189 while( i.hasNext() ) {
190 RefEdge edge = i.next();
193 (edge.typeEquals( type ) && edge.fieldEquals( field ))
196 HeapRegionNode referencee = edge.getDst();
198 removeRefEdge( referencer,
206 protected void clearRefEdgesTo( HeapRegionNode referencee,
209 boolean removeAll ) {
210 assert referencee != null;
212 // get a copy of the set to iterate over, otherwise
213 // we will be trying to take apart the set as we
214 // are iterating over it, which won't work
215 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
216 while( i.hasNext() ) {
217 RefEdge edge = i.next();
220 (edge.typeEquals( type ) && edge.fieldEquals( field ))
223 RefSrcNode referencer = edge.getSrc();
225 removeRefEdge( referencer,
234 ////////////////////////////////////////////////////
236 // Assignment Operation Methods
238 // These methods are high-level operations for
239 // modeling program assignment statements using
240 // the low-level reference create/remove methods
243 ////////////////////////////////////////////////////
245 public void nullifyDeadVars( Set<TempDescriptor> liveIn ) {
249 // make a set of the temps that are out of scope, don't
250 // consider them when nullifying dead in-scope variables
251 Set<TempDescriptor> outOfScope = new HashSet<TempDescriptor>();
252 outOfScope.add( tdReturn );
253 outOfScope.add( tdAliasBlob );
254 outOfScope.addAll( paramIndex2tdQ.values() );
255 outOfScope.addAll( paramIndex2tdR.values() );
257 Iterator varItr = td2vn.entrySet().iterator();
258 while( varItr.hasNext() ) {
259 Map.Entry me = (Map.Entry) varItr.next();
260 TempDescriptor td = (TempDescriptor) me.getKey();
261 VariableNode ln = (VariableNode) me.getValue();
263 // if this variable is not out-of-scope or live
264 // in graph, nullify its references to anything
265 if( !outOfScope.contains( td ) &&
266 !liveIn.contains( td )
268 clearRefEdgesFrom( ln, null, null, true );
275 public void assignTempXEqualToTempY( TempDescriptor x,
277 assignTempXEqualToCastedTempY( x, y, null );
280 public void assignTempXEqualToCastedTempY( TempDescriptor x,
282 TypeDescriptor tdCast ) {
284 VariableNode lnX = getVariableNodeFromTemp( x );
285 VariableNode lnY = getVariableNodeFromTemp( y );
287 clearRefEdgesFrom( lnX, null, null, true );
289 // note it is possible that the types of temps in the
290 // flat node to analyze will reveal that some typed
291 // edges in the reachability graph are impossible
292 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
294 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
295 while( itrYhrn.hasNext() ) {
296 RefEdge edgeY = itrYhrn.next();
297 HeapRegionNode referencee = edgeY.getDst();
298 RefEdge edgeNew = edgeY.copy();
300 if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
301 impossibleEdges.add( edgeY );
305 edgeNew.setSrc( lnX );
307 edgeNew.setType( mostSpecificType( y.getType(),
314 edgeNew.setField( null );
316 addRefEdge( lnX, referencee, edgeNew );
319 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
320 while( itrImp.hasNext() ) {
321 RefEdge edgeImp = itrImp.next();
322 removeRefEdge( edgeImp );
327 public void assignTempXEqualToTempYFieldF( TempDescriptor x,
329 FieldDescriptor f ) {
330 VariableNode lnX = getVariableNodeFromTemp( x );
331 VariableNode lnY = getVariableNodeFromTemp( y );
333 clearRefEdgesFrom( lnX, null, null, true );
335 // note it is possible that the types of temps in the
336 // flat node to analyze will reveal that some typed
337 // edges in the reachability graph are impossible
338 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
340 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
341 while( itrYhrn.hasNext() ) {
342 RefEdge edgeY = itrYhrn.next();
343 HeapRegionNode hrnY = edgeY.getDst();
344 ReachSet betaY = edgeY.getBeta();
346 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
347 while( itrHrnFhrn.hasNext() ) {
348 RefEdge edgeHrn = itrHrnFhrn.next();
349 HeapRegionNode hrnHrn = edgeHrn.getDst();
350 ReachSet betaHrn = edgeHrn.getBeta();
352 // prune edges that are not a matching field
353 if( edgeHrn.getType() != null &&
354 !edgeHrn.getField().equals( f.getSymbol() )
359 // check for impossible edges
360 if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
361 impossibleEdges.add( edgeHrn );
365 TypeDescriptor tdNewEdge =
366 mostSpecificType( edgeHrn.getType(),
370 RefEdge edgeNew = new RefEdge( lnX,
375 betaY.intersection( betaHrn )
378 addRefEdge( lnX, hrnHrn, edgeNew );
382 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
383 while( itrImp.hasNext() ) {
384 RefEdge edgeImp = itrImp.next();
385 removeRefEdge( edgeImp );
388 // anytime you might remove edges between heap regions
389 // you must global sweep to clean up broken reachability
390 if( !impossibleEdges.isEmpty() ) {
391 if( !DISABLE_GLOBAL_SWEEP ) {
398 public void assignTempXFieldFEqualToTempY( TempDescriptor x,
402 VariableNode lnX = getVariableNodeFromTemp( x );
403 VariableNode lnY = getVariableNodeFromTemp( y );
405 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
406 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
408 // note it is possible that the types of temps in the
409 // flat node to analyze will reveal that some typed
410 // edges in the reachability graph are impossible
411 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
413 // first look for possible strong updates and remove those edges
414 boolean strongUpdate = false;
416 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
417 while( itrXhrn.hasNext() ) {
418 RefEdge edgeX = itrXhrn.next();
419 HeapRegionNode hrnX = edgeX.getDst();
421 // we can do a strong update here if one of two cases holds
423 f != DisjointAnalysis.getArrayField( f.getType() ) &&
424 ( (hrnX.getNumReferencers() == 1) || // case 1
425 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
428 if( !DISABLE_STRONG_UPDATES ) {
430 clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
435 // then do all token propagation
436 itrXhrn = lnX.iteratorToReferencees();
437 while( itrXhrn.hasNext() ) {
438 RefEdge edgeX = itrXhrn.next();
439 HeapRegionNode hrnX = edgeX.getDst();
440 ReachSet betaX = edgeX.getBeta();
441 ReachSet R = hrnX.getAlpha().intersection( edgeX.getBeta() );
443 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
444 while( itrYhrn.hasNext() ) {
445 RefEdge edgeY = itrYhrn.next();
446 HeapRegionNode hrnY = edgeY.getDst();
447 ReachSet O = edgeY.getBeta();
449 // check for impossible edges
450 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
451 impossibleEdges.add( edgeY );
455 // propagate tokens over nodes starting from hrnSrc, and it will
456 // take care of propagating back up edges from any touched nodes
457 ChangeSet Cy = O.unionUpArityToChangeSet( R );
458 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
460 // then propagate back just up the edges from hrn
461 ChangeSet Cx = R.unionUpArityToChangeSet(O);
462 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
464 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
465 new Hashtable<RefEdge, ChangeSet>();
467 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
468 while( referItr.hasNext() ) {
469 RefEdge edgeUpstream = referItr.next();
470 todoEdges.add( edgeUpstream );
471 edgePlannedChanges.put( edgeUpstream, Cx );
474 propagateTokensOverEdges( todoEdges,
481 // apply the updates to reachability
482 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
483 while( nodeItr.hasNext() ) {
484 nodeItr.next().applyAlphaNew();
487 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
488 while( edgeItr.hasNext() ) {
489 edgeItr.next().applyBetaNew();
493 // then go back through and add the new edges
494 itrXhrn = lnX.iteratorToReferencees();
495 while( itrXhrn.hasNext() ) {
496 RefEdge edgeX = itrXhrn.next();
497 HeapRegionNode hrnX = edgeX.getDst();
499 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
500 while( itrYhrn.hasNext() ) {
501 RefEdge edgeY = itrYhrn.next();
502 HeapRegionNode hrnY = edgeY.getDst();
504 // skip impossible edges here, we already marked them
505 // when computing reachability propagations above
506 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
510 // prepare the new reference edge hrnX.f -> hrnY
511 TypeDescriptor tdNewEdge =
512 mostSpecificType( y.getType(),
517 RefEdge edgeNew = new RefEdge( hrnX,
522 edgeY.getBeta().pruneBy( hrnX.getAlpha() )
525 // look to see if an edge with same field exists
526 // and merge with it, otherwise just add the edge
527 RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
531 if( edgeExisting != null ) {
532 edgeExisting.setBeta(
533 edgeExisting.getBeta().union( edgeNew.getBeta() )
535 // a new edge here cannot be reflexive, so existing will
536 // always be also not reflexive anymore
537 edgeExisting.setIsInitialParam( false );
540 addRefEdge( hrnX, hrnY, edgeNew );
545 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
546 while( itrImp.hasNext() ) {
547 RefEdge edgeImp = itrImp.next();
548 removeRefEdge( edgeImp );
551 // if there was a strong update, make sure to improve
552 // reachability with a global sweep
553 if( strongUpdate || !impossibleEdges.isEmpty() ) {
554 if( !DISABLE_GLOBAL_SWEEP ) {
561 public void assignReturnEqualToTemp( TempDescriptor x ) {
563 VariableNode lnR = getVariableNodeFromTemp( tdReturn );
564 VariableNode lnX = getVariableNodeFromTemp( x );
566 clearRefEdgesFrom( lnR, null, null, true );
568 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
569 while( itrXhrn.hasNext() ) {
570 RefEdge edgeX = itrXhrn.next();
571 HeapRegionNode referencee = edgeX.getDst();
572 RefEdge edgeNew = edgeX.copy();
573 edgeNew.setSrc( lnR );
575 addRefEdge( lnR, referencee, edgeNew );
580 public void assignTempEqualToNewAlloc( TempDescriptor x,
587 // after the age operation the newest (or zero-ith oldest)
588 // node associated with the allocation site should have
589 // no references to it as if it were a newly allocated
591 Integer idNewest = as.getIthOldest( 0 );
592 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
593 assert hrnNewest != null;
595 VariableNode lnX = getVariableNodeFromTemp( x );
596 clearRefEdgesFrom( lnX, null, null, true );
598 // make a new reference to allocated node
599 TypeDescriptor type = as.getType();
602 new RefEdge( lnX, // source
606 false, // is initial param
607 hrnNewest.getAlpha() // beta
610 addRefEdge( lnX, hrnNewest, edgeNew );
614 // use the allocation site (unique to entire analysis) to
615 // locate the heap region nodes in this reachability graph
616 // that should be aged. The process models the allocation
617 // of new objects and collects all the oldest allocations
618 // in a summary node to allow for a finite analysis
620 // There is an additional property of this method. After
621 // running it on a particular reachability graph (many graphs
622 // may have heap regions related to the same allocation site)
623 // the heap region node objects in this reachability graph will be
624 // allocated. Therefore, after aging a graph for an allocation
625 // site, attempts to retrieve the heap region nodes using the
626 // integer id's contained in the allocation site should always
627 // return non-null heap regions.
628 public void age( AllocSite as ) {
630 // aging adds this allocation site to the graph's
631 // list of sites that exist in the graph, or does
632 // nothing if the site is already in the list
633 allocSites.add( as );
635 // get the summary node for the allocation site in the context
636 // of this particular reachability graph
637 HeapRegionNode hrnSummary = getSummaryNode( as );
639 // merge oldest node into summary
640 Integer idK = as.getOldest();
641 HeapRegionNode hrnK = id2hrn.get( idK );
642 mergeIntoSummary( hrnK, hrnSummary );
644 // move down the line of heap region nodes
645 // clobbering the ith and transferring all references
646 // to and from i-1 to node i. Note that this clobbers
647 // the oldest node (hrnK) that was just merged into
649 for( int i = allocationDepth - 1; i > 0; --i ) {
651 // move references from the i-1 oldest to the ith oldest
652 Integer idIth = as.getIthOldest( i );
653 HeapRegionNode hrnI = id2hrn.get( idIth );
654 Integer idImin1th = as.getIthOldest( i - 1 );
655 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
657 transferOnto( hrnImin1, hrnI );
660 // as stated above, the newest node should have had its
661 // references moved over to the second oldest, so we wipe newest
662 // in preparation for being the new object to assign something to
663 Integer id0th = as.getIthOldest( 0 );
664 HeapRegionNode hrn0 = id2hrn.get( id0th );
667 // clear all references in and out of newest node
668 clearRefEdgesFrom( hrn0, null, null, true );
669 clearRefEdgesTo ( hrn0, null, null, true );
672 // now tokens in reachability sets need to "age" also
673 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
674 while( itrAllVariableNodes.hasNext() ) {
675 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
676 VariableNode ln = (VariableNode) me.getValue();
678 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
679 while( itrEdges.hasNext() ) {
680 ageTokens(as, itrEdges.next() );
684 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
685 while( itrAllHRNodes.hasNext() ) {
686 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
687 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
689 ageTokens( as, hrnToAge );
691 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
692 while( itrEdges.hasNext() ) {
693 ageTokens( as, itrEdges.next() );
698 // after tokens have been aged, reset newest node's reachability
699 if( hrn0.isFlagged() ) {
700 hrn0.setAlpha( new ReachSet(
702 new ReachTuple( hrn0 ).makeCanonical()
707 hrn0.setAlpha( new ReachSet(
708 new ReachState().makeCanonical()
715 protected HeapRegionNode getSummaryNode( AllocSite as ) {
717 Integer idSummary = as.getSummary();
718 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
720 // If this is null then we haven't touched this allocation site
721 // in the context of the current reachability graph, so allocate
722 // heap region nodes appropriate for the entire allocation site.
723 // This should only happen once per reachability graph per allocation site,
724 // and a particular integer id can be used to locate the heap region
725 // in different reachability graphs that represents the same part of an
727 if( hrnSummary == null ) {
729 boolean hasFlags = false;
730 if( as.getType().isClass() ) {
731 hasFlags = as.getType().getClassDesc().hasFlags();
735 hasFlags = as.getFlag();
738 String strDesc = as.toStringForDOT()+"\\nsummary";
740 createNewHeapRegionNode( idSummary, // id or null to generate a new one
741 false, // single object?
743 hasFlags, // flagged?
744 as.getType(), // type
745 as, // allocation site
746 null, // reachability set
747 strDesc // description
750 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
751 Integer idIth = as.getIthOldest( i );
752 assert !id2hrn.containsKey( idIth );
753 strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
754 createNewHeapRegionNode( idIth, // id or null to generate a new one
755 true, // single object?
757 hasFlags, // flagged?
758 as.getType(), // type
759 as, // allocation site
760 null, // reachability set
761 strDesc // description
770 protected HeapRegionNode getShadowSummaryNode( AllocSite as ) {
772 Integer idShadowSummary = as.getSummaryShadow();
773 HeapRegionNode hrnShadowSummary = id2hrn.get( idShadowSummary );
775 if( hrnShadowSummary == null ) {
777 boolean hasFlags = false;
778 if( as.getType().isClass() ) {
779 hasFlags = as.getType().getClassDesc().hasFlags();
783 hasFlags = as.getFlag();
786 String strDesc = as+"\\n"+as.getType()+"\\nshadowSum";
788 createNewHeapRegionNode( idShadowSummary, // id or null to generate a new one
789 false, // single object?
791 hasFlags, // flagged?
792 as.getType(), // type
793 as, // allocation site
794 null, // reachability set
795 strDesc // description
798 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
799 Integer idShadowIth = as.getIthOldestShadow( i );
800 assert !id2hrn.containsKey( idShadowIth );
801 strDesc = as+"\\n"+as.getType()+"\\n"+i+" shadow";
802 createNewHeapRegionNode( idShadowIth, // id or null to generate a new one
803 true, // single object?
805 hasFlags, // flagged?
806 as.getType(), // type
807 as, // allocation site
808 null, // reachability set
809 strDesc // description
814 return hrnShadowSummary;
818 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
819 assert hrnSummary.isNewSummary();
821 // transfer references _from_ hrn over to hrnSummary
822 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
823 while( itrReferencee.hasNext() ) {
824 RefEdge edge = itrReferencee.next();
825 RefEdge edgeMerged = edge.copy();
826 edgeMerged.setSrc(hrnSummary);
828 HeapRegionNode hrnReferencee = edge.getDst();
829 RefEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee,
833 if( edgeSummary == null ) {
834 // the merge is trivial, nothing to be done
836 // otherwise an edge from the referencer to hrnSummary exists already
837 // and the edge referencer->hrn should be merged with it
838 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
841 addRefEdge(hrnSummary, hrnReferencee, edgeMerged);
844 // next transfer references _to_ hrn over to hrnSummary
845 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
846 while( itrReferencer.hasNext() ) {
847 RefEdge edge = itrReferencer.next();
848 RefEdge edgeMerged = edge.copy();
849 edgeMerged.setDst(hrnSummary);
851 RefSrcNode onReferencer = edge.getSrc();
852 RefEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary,
856 if( edgeSummary == null ) {
857 // the merge is trivial, nothing to be done
859 // otherwise an edge from the referencer to alpha_S exists already
860 // and the edge referencer->alpha_K should be merged with it
861 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
864 addRefEdge(onReferencer, hrnSummary, edgeMerged);
867 // then merge hrn reachability into hrnSummary
868 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
872 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
874 // clear references in and out of node b
875 clearRefEdgesFrom(hrnB, null, null, true);
876 clearRefEdgesTo(hrnB, null, null, true);
878 // copy each edge in and out of A to B
879 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
880 while( itrReferencee.hasNext() ) {
881 RefEdge edge = itrReferencee.next();
882 HeapRegionNode hrnReferencee = edge.getDst();
883 RefEdge edgeNew = edge.copy();
884 edgeNew.setSrc(hrnB);
886 addRefEdge(hrnB, hrnReferencee, edgeNew);
889 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
890 while( itrReferencer.hasNext() ) {
891 RefEdge edge = itrReferencer.next();
892 RefSrcNode onReferencer = edge.getSrc();
893 RefEdge edgeNew = edge.copy();
894 edgeNew.setDst(hrnB);
896 addRefEdge(onReferencer, hrnB, edgeNew);
899 // replace hrnB reachability with hrnA's
900 hrnB.setAlpha(hrnA.getAlpha() );
904 protected void ageTokens(AllocSite as, RefEdge edge) {
905 edge.setBeta(edge.getBeta().ageTokens(as) );
908 protected void ageTokens(AllocSite as, HeapRegionNode hrn) {
909 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
914 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
916 HashSet<HeapRegionNode> nodesWithNewAlpha,
917 HashSet<RefEdge> edgesWithNewBeta) {
919 HashSet<HeapRegionNode> todoNodes
920 = new HashSet<HeapRegionNode>();
921 todoNodes.add(nPrime);
923 HashSet<RefEdge> todoEdges
924 = new HashSet<RefEdge>();
926 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
927 = new Hashtable<HeapRegionNode, ChangeSet>();
928 nodePlannedChanges.put(nPrime, c0);
930 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
931 = new Hashtable<RefEdge, ChangeSet>();
933 // first propagate change sets everywhere they can go
934 while( !todoNodes.isEmpty() ) {
935 HeapRegionNode n = todoNodes.iterator().next();
936 ChangeSet C = nodePlannedChanges.get(n);
938 Iterator<RefEdge> referItr = n.iteratorToReferencers();
939 while( referItr.hasNext() ) {
940 RefEdge edge = referItr.next();
943 if( !edgePlannedChanges.containsKey(edge) ) {
944 edgePlannedChanges.put(edge, new ChangeSet().makeCanonical() );
947 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
950 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
951 while( refeeItr.hasNext() ) {
952 RefEdge edgeF = refeeItr.next();
953 HeapRegionNode m = edgeF.getDst();
955 ChangeSet changesToPass = new ChangeSet().makeCanonical();
957 Iterator<ChangeTuple> itrCprime = C.iterator();
958 while( itrCprime.hasNext() ) {
959 ChangeTuple c = itrCprime.next();
960 if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
961 changesToPass = changesToPass.union(c);
965 if( !changesToPass.isEmpty() ) {
966 if( !nodePlannedChanges.containsKey(m) ) {
967 nodePlannedChanges.put(m, new ChangeSet().makeCanonical() );
970 ChangeSet currentChanges = nodePlannedChanges.get(m);
972 if( !changesToPass.isSubset(currentChanges) ) {
974 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
983 // then apply all of the changes for each node at once
984 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
985 while( itrMap.hasNext() ) {
986 Map.Entry me = (Map.Entry) itrMap.next();
987 HeapRegionNode n = (HeapRegionNode) me.getKey();
988 ChangeSet C = (ChangeSet) me.getValue();
990 // this propagation step is with respect to one change,
991 // so we capture the full change from the old alpha:
992 ReachSet localDelta = n.getAlpha().applyChangeSet( C, true );
994 // but this propagation may be only one of many concurrent
995 // possible changes, so keep a running union with the node's
996 // partially updated new alpha set
997 n.setAlphaNew( n.getAlphaNew().union( localDelta ) );
999 nodesWithNewAlpha.add( n );
1002 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
1006 protected void propagateTokensOverEdges(
1007 HashSet<RefEdge> todoEdges,
1008 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1009 HashSet<RefEdge> edgesWithNewBeta) {
1011 // first propagate all change tuples everywhere they can go
1012 while( !todoEdges.isEmpty() ) {
1013 RefEdge edgeE = todoEdges.iterator().next();
1014 todoEdges.remove(edgeE);
1016 if( !edgePlannedChanges.containsKey(edgeE) ) {
1017 edgePlannedChanges.put(edgeE, new ChangeSet().makeCanonical() );
1020 ChangeSet C = edgePlannedChanges.get(edgeE);
1022 ChangeSet changesToPass = new ChangeSet().makeCanonical();
1024 Iterator<ChangeTuple> itrC = C.iterator();
1025 while( itrC.hasNext() ) {
1026 ChangeTuple c = itrC.next();
1027 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1028 changesToPass = changesToPass.union(c);
1032 RefSrcNode onSrc = edgeE.getSrc();
1034 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
1035 HeapRegionNode n = (HeapRegionNode) onSrc;
1037 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1038 while( referItr.hasNext() ) {
1039 RefEdge edgeF = referItr.next();
1041 if( !edgePlannedChanges.containsKey(edgeF) ) {
1042 edgePlannedChanges.put(edgeF, new ChangeSet().makeCanonical() );
1045 ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
1047 if( !changesToPass.isSubset(currentChanges) ) {
1048 todoEdges.add(edgeF);
1049 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
1055 // then apply all of the changes for each edge at once
1056 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1057 while( itrMap.hasNext() ) {
1058 Map.Entry me = (Map.Entry) itrMap.next();
1059 RefEdge e = (RefEdge) me.getKey();
1060 ChangeSet C = (ChangeSet) me.getValue();
1062 // this propagation step is with respect to one change,
1063 // so we capture the full change from the old beta:
1064 ReachSet localDelta = e.getBeta().applyChangeSet( C, true );
1066 // but this propagation may be only one of many concurrent
1067 // possible changes, so keep a running union with the edge's
1068 // partially updated new beta set
1069 e.setBetaNew( e.getBetaNew().union( localDelta ) );
1071 edgesWithNewBeta.add( e );
1077 // resolveMethodCall() is used to incorporate a callee graph's effects into
1078 // *this* graph, which is the caller. This method can also be used, after
1079 // the entire analysis is complete, to perform parameter decomposition for
1080 // a given call chain.
1081 public void resolveMethodCall(FlatCall fc, // call site in caller method
1082 boolean isStatic, // whether it is a static method
1083 FlatMethod fm, // the callee method (when virtual, can be many)
1084 ReachGraph ogCallee, // the callee's current reachability graph
1085 MethodContext mc, // the aliasing context for this call
1086 ParameterDecomposition pd // if this is not null, we're calling after analysis
1090 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
1091 fm.getMethod().getSymbol().equals( debugCallee )
1095 writeGraph("debug1BeforeCall",
1096 true, // write labels (variables)
1097 true, // selectively hide intermediate temp vars
1098 true, // prune unreachable heap regions
1099 false, // show back edges to confirm graph validity
1100 false, // show parameter indices (unmaintained!)
1101 true, // hide subset reachability states
1102 true); // hide edge taints
1104 ogCallee.writeGraph("debug0Callee",
1105 true, // write labels (variables)
1106 true, // selectively hide intermediate temp vars
1107 true, // prune unreachable heap regions
1108 false, // show back edges to confirm graph validity
1109 false, // show parameter indices (unmaintained!)
1110 true, // hide subset reachability states
1111 true); // hide edge taints
1112 } catch( IOException e ) {}
1114 System.out.println( " "+mc+" is calling "+fm );
1119 // define rewrite rules and other structures to organize data by parameter/argument index
1120 Hashtable<Integer, ReachSet> paramIndex2rewriteH_p = new Hashtable<Integer, ReachSet>();
1121 Hashtable<Integer, ReachSet> paramIndex2rewriteH_s = new Hashtable<Integer, ReachSet>();
1123 Hashtable<String, ReachSet> paramIndex2rewriteJ_p2p = new Hashtable<String, ReachSet>(); // select( i, j, f )
1124 Hashtable<String, ReachSet> paramIndex2rewriteJ_p2s = new Hashtable<String, ReachSet>(); // select( i, f )
1125 Hashtable<Integer, ReachSet> paramIndex2rewriteJ_s2p = new Hashtable<Integer, ReachSet>();
1126 Hashtable<Integer, ReachSet> paramIndex2rewriteJ_s2s = new Hashtable<Integer, ReachSet>();
1128 Hashtable<Integer, ReachSet> paramIndex2rewriteK_p = new Hashtable<Integer, ReachSet>();
1129 Hashtable<Integer, ReachSet> paramIndex2rewriteK_p2 = new Hashtable<Integer, ReachSet>();
1130 Hashtable<Integer, ReachSet> paramIndex2rewriteK_s = new Hashtable<Integer, ReachSet>();
1132 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_p = new Hashtable<Integer, ReachSet>();
1133 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_s = new Hashtable<Integer, ReachSet>();
1135 Hashtable<Integer, ReachSet> paramIndex2rewriteD = new Hashtable<Integer, ReachSet>();
1138 Hashtable<Integer, VariableNode> paramIndex2ln = new Hashtable<Integer, VariableNode>();
1141 paramIndex2rewriteH_p.put( bogusIndex, rsIdentity );
1142 paramIndex2rewriteH_s.put( bogusIndex, rsIdentity );
1144 paramIndex2rewriteJ_p2p.put( bogusIndex.toString(), rsIdentity );
1145 paramIndex2rewriteJ_p2s.put( bogusIndex.toString(), rsIdentity );
1146 paramIndex2rewriteJ_s2p.put( bogusIndex, rsIdentity );
1147 paramIndex2rewriteJ_s2s.put( bogusIndex, rsIdentity );
1150 for( int i = 0; i < fm.numParameters(); ++i ) {
1151 Integer paramIndex = new Integer(i);
1153 if( !ogCallee.paramIndex2idPrimary.containsKey( paramIndex ) ) {
1154 // skip this immutable parameter
1158 // setup H (primary)
1159 Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
1160 assert ogCallee.id2hrn.containsKey( idPrimary );
1161 HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
1162 assert hrnPrimary != null;
1163 paramIndex2rewriteH_p.put( paramIndex, toShadowTokens( ogCallee, hrnPrimary.getAlpha() ) );
1165 // setup J (primary->X)
1166 Iterator<RefEdge> p2xItr = hrnPrimary.iteratorToReferencees();
1167 while( p2xItr.hasNext() ) {
1168 RefEdge p2xEdge = p2xItr.next();
1170 // we only care about initial parameter edges here
1171 if( !p2xEdge.isInitialParam() ) { continue; }
1173 HeapRegionNode hrnDst = p2xEdge.getDst();
1175 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
1176 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
1177 while( jItr.hasNext() ) {
1178 Integer j = jItr.next();
1179 paramIndex2rewriteJ_p2p.put( makeMapKey( i, j, p2xEdge.getField() ),
1180 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
1184 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
1185 paramIndex2rewriteJ_p2s.put( makeMapKey( i, p2xEdge.getField() ),
1186 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
1190 // setup K (primary)
1191 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
1192 assert tdParamQ != null;
1193 VariableNode lnParamQ = ogCallee.td2vn.get( tdParamQ );
1194 assert lnParamQ != null;
1195 RefEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnPrimary, null, null );
1196 assert edgeSpecialQ_i != null;
1197 ReachSet qBeta = toShadowTokens( ogCallee, edgeSpecialQ_i.getBeta() );
1199 ReachTuple p_i = ogCallee.paramIndex2paramTokenPrimary .get( paramIndex );
1200 ReachTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( paramIndex );
1202 ReachSet K_p = new ReachSet().makeCanonical();
1203 ReachSet K_p2 = new ReachSet().makeCanonical();
1207 // sort qBeta into K_p1 and K_p2
1208 Iterator<ReachState> ttsItr = qBeta.iterator();
1209 while( ttsItr.hasNext() ) {
1210 ReachState tts = ttsItr.next();
1211 if( s_i != null && tts.containsBoth( p_i, s_i ) ) {
1212 K_p2 = K_p2.union( tts );
1214 K_p = K_p.union( tts );
1218 paramIndex2rewriteK_p .put( paramIndex, K_p );
1219 paramIndex2rewriteK_p2.put( paramIndex, K_p2 );
1222 // if there is a secondary node, compute the rest of the rewrite rules
1223 if( ogCallee.paramIndex2idSecondary.containsKey( paramIndex ) ) {
1225 // setup H (secondary)
1226 Integer idSecondary = ogCallee.paramIndex2idSecondary.get( paramIndex );
1227 assert ogCallee.id2hrn.containsKey( idSecondary );
1228 HeapRegionNode hrnSecondary = ogCallee.id2hrn.get( idSecondary );
1229 assert hrnSecondary != null;
1230 paramIndex2rewriteH_s.put( paramIndex, toShadowTokens( ogCallee, hrnSecondary.getAlpha() ) );
1232 // setup J (secondary->X)
1233 Iterator<RefEdge> s2xItr = hrnSecondary.iteratorToReferencees();
1234 while( s2xItr.hasNext() ) {
1235 RefEdge s2xEdge = s2xItr.next();
1237 if( !s2xEdge.isInitialParam() ) { continue; }
1239 HeapRegionNode hrnDst = s2xEdge.getDst();
1241 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
1242 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
1243 while( jItr.hasNext() ) {
1244 Integer j = jItr.next();
1245 paramIndex2rewriteJ_s2p.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
1249 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
1250 paramIndex2rewriteJ_s2s.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
1254 // setup K (secondary)
1255 TempDescriptor tdParamR = ogCallee.paramIndex2tdR.get( paramIndex );
1256 assert tdParamR != null;
1257 VariableNode lnParamR = ogCallee.td2vn.get( tdParamR );
1258 assert lnParamR != null;
1259 RefEdge edgeSpecialR_i = lnParamR.getReferenceTo( hrnSecondary, null, null );
1260 assert edgeSpecialR_i != null;
1261 paramIndex2rewriteK_s.put( paramIndex,
1262 toShadowTokens( ogCallee, edgeSpecialR_i.getBeta() ) );
1266 // now depending on whether the callee is static or not
1267 // we need to account for a "this" argument in order to
1268 // find the matching argument in the caller context
1269 TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, paramIndex );
1271 // remember which caller arg label maps to param index
1272 VariableNode argLabel_i = getVariableNodeFromTemp( argTemp_i );
1273 paramIndex2ln.put( paramIndex, argLabel_i );
1275 // do a callee-effect strong update pre-pass here
1276 if( argTemp_i.getType().isClass() ) {
1278 Iterator<RefEdge> edgeItr = argLabel_i.iteratorToReferencees();
1279 while( edgeItr.hasNext() ) {
1280 RefEdge edge = edgeItr.next();
1281 HeapRegionNode hrn = edge.getDst();
1283 if( (hrn.getNumReferencers() == 1) || // case 1
1284 (hrn.isSingleObject() && argLabel_i.getNumReferencees() == 1) // case 2
1286 if( !DISABLE_STRONG_UPDATES ) {
1287 effectCalleeStrongUpdates( paramIndex, ogCallee, hrn );
1293 // then calculate the d and D rewrite rules
1294 ReachSet d_i_p = new ReachSet().makeCanonical();
1295 ReachSet d_i_s = new ReachSet().makeCanonical();
1296 Iterator<RefEdge> edgeItr = argLabel_i.iteratorToReferencees();
1297 while( edgeItr.hasNext() ) {
1298 RefEdge edge = edgeItr.next();
1300 d_i_p = d_i_p.union( edge.getBeta().intersection( edge.getDst().getAlpha() ) );
1301 d_i_s = d_i_s.union( edge.getBeta() );
1303 paramIndex2rewrite_d_p.put( paramIndex, d_i_p );
1304 paramIndex2rewrite_d_s.put( paramIndex, d_i_s );
1306 // TODO: we should only do this when we need it, and then
1307 // memoize it for the rest of the mapping procedure
1308 ReachSet D_i = d_i_s.exhaustiveArityCombinations();
1309 paramIndex2rewriteD.put( paramIndex, D_i );
1313 // with respect to each argument, map parameter effects into caller
1314 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1315 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
1317 Hashtable<Integer, Set<HeapRegionNode> > pi2dr =
1318 new Hashtable<Integer, Set<HeapRegionNode> >();
1320 Hashtable<Integer, Set<HeapRegionNode> > pi2r =
1321 new Hashtable<Integer, Set<HeapRegionNode> >();
1323 Set<HeapRegionNode> defParamObj = new HashSet<HeapRegionNode>();
1325 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1326 while( lnArgItr.hasNext() ) {
1327 Map.Entry me = (Map.Entry) lnArgItr.next();
1328 Integer index = (Integer) me.getKey();
1329 VariableNode lnArg_i = (VariableNode) me.getValue();
1331 Set<HeapRegionNode> dr = new HashSet<HeapRegionNode>();
1332 Set<HeapRegionNode> r = new HashSet<HeapRegionNode>();
1333 Set<HeapRegionNode> todo = new HashSet<HeapRegionNode>();
1335 // find all reachable nodes starting with label referencees
1336 Iterator<RefEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1337 while( edgeArgItr.hasNext() ) {
1338 RefEdge edge = edgeArgItr.next();
1339 HeapRegionNode hrn = edge.getDst();
1343 if( lnArg_i.getNumReferencees() == 1 && hrn.isSingleObject() ) {
1344 defParamObj.add( hrn );
1347 Iterator<RefEdge> edgeHrnItr = hrn.iteratorToReferencees();
1348 while( edgeHrnItr.hasNext() ) {
1349 RefEdge edger = edgeHrnItr.next();
1350 todo.add( edger.getDst() );
1353 // then follow links until all reachable nodes have been found
1354 while( !todo.isEmpty() ) {
1355 HeapRegionNode hrnr = todo.iterator().next();
1356 todo.remove( hrnr );
1360 Iterator<RefEdge> edgeItr = hrnr.iteratorToReferencees();
1361 while( edgeItr.hasNext() ) {
1362 RefEdge edger = edgeItr.next();
1363 if( !r.contains( edger.getDst() ) ) {
1364 todo.add( edger.getDst() );
1369 if( hrn.isSingleObject() ) {
1374 pi2dr.put( index, dr );
1375 pi2r .put( index, r );
1378 assert defParamObj.size() <= fm.numParameters();
1380 // if we're in parameter decomposition mode, report some results here
1384 // report primary parameter object mappings
1385 mapItr = pi2dr.entrySet().iterator();
1386 while( mapItr.hasNext() ) {
1387 Map.Entry me = (Map.Entry) mapItr.next();
1388 Integer paramIndex = (Integer) me.getKey();
1389 Set<HeapRegionNode> hrnAset = (Set<HeapRegionNode>) me.getValue();
1391 Iterator<HeapRegionNode> hrnItr = hrnAset.iterator();
1392 while( hrnItr.hasNext() ) {
1393 HeapRegionNode hrnA = hrnItr.next();
1394 pd.mapRegionToParamObject( hrnA, paramIndex );
1398 // report parameter-reachable mappings
1399 mapItr = pi2r.entrySet().iterator();
1400 while( mapItr.hasNext() ) {
1401 Map.Entry me = (Map.Entry) mapItr.next();
1402 Integer paramIndex = (Integer) me.getKey();
1403 Set<HeapRegionNode> hrnRset = (Set<HeapRegionNode>) me.getValue();
1405 Iterator<HeapRegionNode> hrnItr = hrnRset.iterator();
1406 while( hrnItr.hasNext() ) {
1407 HeapRegionNode hrnR = hrnItr.next();
1408 pd.mapRegionToParamReachable( hrnR, paramIndex );
1412 // and we're done in this method for special param decomp mode
1417 // now iterate over reachable nodes to rewrite their alpha, and
1418 // classify edges found for beta rewrite
1419 Hashtable<ReachTuple, ReachSet> tokens2states = new Hashtable<ReachTuple, ReachSet>();
1421 Hashtable< Integer, Set<Vector> > edges_p2p = new Hashtable< Integer, Set<Vector> >();
1422 Hashtable< Integer, Set<Vector> > edges_p2s = new Hashtable< Integer, Set<Vector> >();
1423 Hashtable< Integer, Set<Vector> > edges_s2p = new Hashtable< Integer, Set<Vector> >();
1424 Hashtable< Integer, Set<Vector> > edges_s2s = new Hashtable< Integer, Set<Vector> >();
1425 Hashtable< Integer, Set<Vector> > edges_up_dr = new Hashtable< Integer, Set<Vector> >();
1426 Hashtable< Integer, Set<Vector> > edges_up_r = new Hashtable< Integer, Set<Vector> >();
1428 // so again, with respect to some arg i...
1429 lnArgItr = paramIndex2ln.entrySet().iterator();
1430 while( lnArgItr.hasNext() ) {
1431 Map.Entry me = (Map.Entry) lnArgItr.next();
1432 Integer index = (Integer) me.getKey();
1433 VariableNode lnArg_i = (VariableNode) me.getValue();
1435 ReachTuple p_i = ogCallee.paramIndex2paramTokenPrimary.get( index );
1436 ReachTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( index );
1439 ensureEmptyEdgeIndexPair( edges_p2p, index );
1440 ensureEmptyEdgeIndexPair( edges_p2s, index );
1441 ensureEmptyEdgeIndexPair( edges_s2p, index );
1442 ensureEmptyEdgeIndexPair( edges_s2s, index );
1443 ensureEmptyEdgeIndexPair( edges_up_dr, index );
1444 ensureEmptyEdgeIndexPair( edges_up_r, index );
1446 Set<HeapRegionNode> dr = pi2dr.get( index );
1447 Iterator<HeapRegionNode> hrnItr = dr.iterator();
1448 while( hrnItr.hasNext() ) {
1449 // this heap region is definitely an "a_i" or primary by virtue of being in dr
1450 HeapRegionNode hrn = hrnItr.next();
1452 tokens2states.clear();
1453 tokens2states.put( p_i, hrn.getAlpha() );
1455 rewriteCallerReachability( index,
1458 paramIndex2rewriteH_p.get( index ),
1460 paramIndex2rewrite_d_p,
1461 paramIndex2rewrite_d_s,
1462 paramIndex2rewriteD,
1467 nodesWithNewAlpha.add( hrn );
1470 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
1471 while( edgeItr.hasNext() ) {
1472 RefEdge edge = edgeItr.next();
1473 RefSrcNode on = edge.getSrc();
1475 boolean edge_classified = false;
1478 if( on instanceof HeapRegionNode ) {
1479 // hrn0 may be "a_j" and/or "r_j" or even neither
1480 HeapRegionNode hrn0 = (HeapRegionNode) on;
1482 Iterator itr = pi2dr.entrySet().iterator();
1483 while( itr.hasNext() ) {
1484 Map.Entry mo = (Map.Entry) itr.next();
1485 Integer pi = (Integer) mo.getKey();
1486 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
1488 if( dr_i.contains( hrn0 ) ) {
1489 addEdgeIndexPair( edges_p2p, pi, edge, index );
1490 edge_classified = true;
1494 itr = pi2r.entrySet().iterator();
1495 while( itr.hasNext() ) {
1496 Map.Entry mo = (Map.Entry) itr.next();
1497 Integer pi = (Integer) mo.getKey();
1498 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
1500 if( r_i.contains( hrn0 ) ) {
1501 addEdgeIndexPair( edges_s2p, pi, edge, index );
1502 edge_classified = true;
1507 // all of these edges are upstream of directly reachable objects
1508 if( !edge_classified ) {
1509 addEdgeIndexPair( edges_up_dr, index, edge, index );
1515 Set<HeapRegionNode> r = pi2r.get( index );
1516 hrnItr = r.iterator();
1517 while( hrnItr.hasNext() ) {
1518 // this heap region is definitely an "r_i" or secondary by virtue of being in r
1519 HeapRegionNode hrn = hrnItr.next();
1521 if( paramIndex2rewriteH_s.containsKey( index ) ) {
1523 tokens2states.clear();
1524 tokens2states.put( p_i, new ReachSet().makeCanonical() );
1525 tokens2states.put( s_i, hrn.getAlpha() );
1527 rewriteCallerReachability( index,
1530 paramIndex2rewriteH_s.get( index ),
1532 paramIndex2rewrite_d_p,
1533 paramIndex2rewrite_d_s,
1534 paramIndex2rewriteD,
1539 nodesWithNewAlpha.add( hrn );
1543 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
1544 while( edgeItr.hasNext() ) {
1545 RefEdge edge = edgeItr.next();
1546 RefSrcNode on = edge.getSrc();
1548 boolean edge_classified = false;
1550 if( on instanceof HeapRegionNode ) {
1551 // hrn0 may be "a_j" and/or "r_j" or even neither
1552 HeapRegionNode hrn0 = (HeapRegionNode) on;
1554 Iterator itr = pi2dr.entrySet().iterator();
1555 while( itr.hasNext() ) {
1556 Map.Entry mo = (Map.Entry) itr.next();
1557 Integer pi = (Integer) mo.getKey();
1558 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
1560 if( dr_i.contains( hrn0 ) ) {
1561 addEdgeIndexPair( edges_p2s, pi, edge, index );
1562 edge_classified = true;
1566 itr = pi2r.entrySet().iterator();
1567 while( itr.hasNext() ) {
1568 Map.Entry mo = (Map.Entry) itr.next();
1569 Integer pi = (Integer) mo.getKey();
1570 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
1572 if( r_i.contains( hrn0 ) ) {
1573 addEdgeIndexPair( edges_s2s, pi, edge, index );
1574 edge_classified = true;
1579 // these edges are all upstream of some reachable node
1580 if( !edge_classified ) {
1581 addEdgeIndexPair( edges_up_r, index, edge, index );
1588 // and again, with respect to some arg i...
1589 lnArgItr = paramIndex2ln.entrySet().iterator();
1590 while( lnArgItr.hasNext() ) {
1591 Map.Entry me = (Map.Entry) lnArgItr.next();
1592 Integer index = (Integer) me.getKey();
1593 VariableNode lnArg_i = (VariableNode) me.getValue();
1596 // update reachable edges
1597 Iterator edgeItr = edges_p2p.get( index ).iterator();
1598 while( edgeItr.hasNext() ) {
1599 Vector mo = (Vector) edgeItr.next();
1600 RefEdge edge = (RefEdge) mo.get( 0 );
1601 Integer indexJ = (Integer) mo.get( 1 );
1603 if( !paramIndex2rewriteJ_p2p.containsKey( makeMapKey( index,
1605 edge.getField() ) ) ) {
1609 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
1612 tokens2states.clear();
1613 tokens2states.put( p_j, edge.getBeta() );
1615 rewriteCallerReachability( index,
1618 paramIndex2rewriteJ_p2p.get( makeMapKey( index,
1620 edge.getField() ) ),
1622 paramIndex2rewrite_d_p,
1623 paramIndex2rewrite_d_s,
1624 paramIndex2rewriteD,
1629 edgesWithNewBeta.add( edge );
1633 edgeItr = edges_p2s.get( index ).iterator();
1634 while( edgeItr.hasNext() ) {
1635 Vector mo = (Vector) edgeItr.next();
1636 RefEdge edge = (RefEdge) mo.get( 0 );
1637 Integer indexJ = (Integer) mo.get( 1 );
1639 if( !paramIndex2rewriteJ_p2s.containsKey( makeMapKey( index,
1640 edge.getField() ) ) ) {
1644 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
1647 tokens2states.clear();
1648 tokens2states.put( s_j, edge.getBeta() );
1650 rewriteCallerReachability( index,
1653 paramIndex2rewriteJ_p2s.get( makeMapKey( index,
1654 edge.getField() ) ),
1656 paramIndex2rewrite_d_p,
1657 paramIndex2rewrite_d_s,
1658 paramIndex2rewriteD,
1663 edgesWithNewBeta.add( edge );
1667 edgeItr = edges_s2p.get( index ).iterator();
1668 while( edgeItr.hasNext() ) {
1669 Vector mo = (Vector) edgeItr.next();
1670 RefEdge edge = (RefEdge) mo.get( 0 );
1671 Integer indexJ = (Integer) mo.get( 1 );
1673 if( !paramIndex2rewriteJ_s2p.containsKey( index ) ) {
1677 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
1680 tokens2states.clear();
1681 tokens2states.put( p_j, edge.getBeta() );
1683 rewriteCallerReachability( index,
1686 paramIndex2rewriteJ_s2p.get( index ),
1688 paramIndex2rewrite_d_p,
1689 paramIndex2rewrite_d_s,
1690 paramIndex2rewriteD,
1695 edgesWithNewBeta.add( edge );
1699 edgeItr = edges_s2s.get( index ).iterator();
1700 while( edgeItr.hasNext() ) {
1701 Vector mo = (Vector) edgeItr.next();
1702 RefEdge edge = (RefEdge) mo.get( 0 );
1703 Integer indexJ = (Integer) mo.get( 1 );
1705 if( !paramIndex2rewriteJ_s2s.containsKey( index ) ) {
1709 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
1712 tokens2states.clear();
1713 tokens2states.put( s_j, edge.getBeta() );
1715 rewriteCallerReachability( index,
1718 paramIndex2rewriteJ_s2s.get( index ),
1720 paramIndex2rewrite_d_p,
1721 paramIndex2rewrite_d_s,
1722 paramIndex2rewriteD,
1727 edgesWithNewBeta.add( edge );
1731 // update directly upstream edges
1732 Hashtable<RefEdge, ChangeSet> edgeUpstreamPlannedChanges =
1733 new Hashtable<RefEdge, ChangeSet>();
1735 HashSet<RefEdge> edgesDirectlyUpstream =
1736 new HashSet<RefEdge>();
1738 edgeItr = edges_up_dr.get( index ).iterator();
1739 while( edgeItr.hasNext() ) {
1740 Vector mo = (Vector) edgeItr.next();
1741 RefEdge edge = (RefEdge) mo.get( 0 );
1742 Integer indexJ = (Integer) mo.get( 1 );
1744 edgesDirectlyUpstream.add( edge );
1746 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
1749 // start with K_p2 and p_j
1750 tokens2states.clear();
1751 tokens2states.put( p_j, edge.getBeta() );
1753 rewriteCallerReachability( index,
1756 paramIndex2rewriteK_p2.get( index ),
1758 paramIndex2rewrite_d_p,
1759 paramIndex2rewrite_d_s,
1760 paramIndex2rewriteD,
1763 edgeUpstreamPlannedChanges );
1765 // and add in s_j, if required, and do K_p
1766 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
1768 tokens2states.put( s_j, edge.getBeta() );
1771 rewriteCallerReachability( index,
1774 paramIndex2rewriteK_p.get( index ),
1776 paramIndex2rewrite_d_p,
1777 paramIndex2rewrite_d_s,
1778 paramIndex2rewriteD,
1781 edgeUpstreamPlannedChanges );
1783 edgesWithNewBeta.add( edge );
1786 propagateTokensOverEdges( edgesDirectlyUpstream,
1787 edgeUpstreamPlannedChanges,
1791 // update upstream edges
1792 edgeUpstreamPlannedChanges =
1793 new Hashtable<RefEdge, ChangeSet>();
1795 HashSet<RefEdge> edgesUpstream =
1796 new HashSet<RefEdge>();
1798 edgeItr = edges_up_r.get( index ).iterator();
1799 while( edgeItr.hasNext() ) {
1800 Vector mo = (Vector) edgeItr.next();
1801 RefEdge edge = (RefEdge) mo.get( 0 );
1802 Integer indexJ = (Integer) mo.get( 1 );
1804 if( !paramIndex2rewriteK_s.containsKey( index ) ) {
1808 edgesUpstream.add( edge );
1810 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
1813 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
1816 tokens2states.clear();
1817 tokens2states.put( p_j, rsWttsEmpty );
1818 tokens2states.put( s_j, edge.getBeta() );
1820 rewriteCallerReachability( index,
1823 paramIndex2rewriteK_s.get( index ),
1825 paramIndex2rewrite_d_p,
1826 paramIndex2rewrite_d_s,
1827 paramIndex2rewriteD,
1830 edgeUpstreamPlannedChanges );
1832 edgesWithNewBeta.add( edge );
1835 propagateTokensOverEdges( edgesUpstream,
1836 edgeUpstreamPlannedChanges,
1839 } // end effects per argument/parameter map
1842 // commit changes to alpha and beta
1843 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1844 while( nodeItr.hasNext() ) {
1845 nodeItr.next().applyAlphaNew();
1848 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
1849 while( edgeItr.hasNext() ) {
1850 edgeItr.next().applyBetaNew();
1854 // verify the existence of allocation sites and their
1855 // shadows from the callee in the context of this caller graph
1856 // then map allocated nodes of callee onto the caller shadows
1858 Hashtable<ReachTuple, ReachSet> tokens2statesEmpty = new Hashtable<ReachTuple, ReachSet>();
1860 Iterator<AllocSite> asItr = ogCallee.allocSites.iterator();
1861 while( asItr.hasNext() ) {
1862 AllocSite allocSite = asItr.next();
1864 // grab the summary in the caller just to make sure
1865 // the allocation site has nodes in the caller
1866 HeapRegionNode hrnSummary = getSummaryNode( allocSite );
1868 // assert that the shadow nodes have no reference edges
1869 // because they're brand new to the graph, or last time
1870 // they were used they should have been cleared of edges
1871 HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
1872 assert hrnShadowSummary.getNumReferencers() == 0;
1873 assert hrnShadowSummary.getNumReferencees() == 0;
1875 // then bring g_ij onto g'_ij and rewrite
1876 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode( allocSite );
1877 hrnShadowSummary.setAlpha( toShadowTokens( ogCallee, hrnSummaryCallee.getAlpha() ) );
1879 // shadow nodes only are touched by a rewrite one time,
1880 // so rewrite and immediately commit--and they don't belong
1881 // to a particular parameter, so use a bogus param index
1882 // that pulls a self-rewrite out of H
1883 rewriteCallerReachability( bogusIndex,
1886 funcScriptR( hrnShadowSummary.getAlpha(), ogCallee, mc ),
1888 paramIndex2rewrite_d_p,
1889 paramIndex2rewrite_d_s,
1890 paramIndex2rewriteD,
1895 hrnShadowSummary.applyAlphaNew();
1898 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1899 Integer idIth = allocSite.getIthOldest(i);
1900 assert id2hrn.containsKey(idIth);
1901 HeapRegionNode hrnIth = id2hrn.get(idIth);
1903 Integer idShadowIth = -(allocSite.getIthOldest(i));
1904 assert id2hrn.containsKey(idShadowIth);
1905 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1906 assert hrnIthShadow.getNumReferencers() == 0;
1907 assert hrnIthShadow.getNumReferencees() == 0;
1909 assert ogCallee.id2hrn.containsKey(idIth);
1910 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1911 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1913 rewriteCallerReachability( bogusIndex,
1916 funcScriptR( hrnIthShadow.getAlpha(), ogCallee, mc ),
1918 paramIndex2rewrite_d_p,
1919 paramIndex2rewrite_d_s,
1920 paramIndex2rewriteD,
1925 hrnIthShadow.applyAlphaNew();
1930 // for every heap region->heap region edge in the
1931 // callee graph, create the matching edge or edges
1932 // in the caller graph
1933 Set sCallee = ogCallee.id2hrn.entrySet();
1934 Iterator iCallee = sCallee.iterator();
1936 while( iCallee.hasNext() ) {
1937 Map.Entry meCallee = (Map.Entry) iCallee.next();
1938 Integer idCallee = (Integer) meCallee.getKey();
1939 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1941 Iterator<RefEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1942 while( heapRegionsItrCallee.hasNext() ) {
1943 RefEdge edgeCallee = heapRegionsItrCallee.next();
1944 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1945 Integer idChildCallee = hrnChildCallee.getID();
1947 // only address this edge if it is not a special initial edge
1948 if( !edgeCallee.isInitialParam() ) {
1950 // now we know that in the callee method's reachability graph
1951 // there is a heap region->heap region reference edge given
1952 // by heap region pointers:
1953 // hrnCallee -> heapChildCallee
1955 // or by the reachability-graph independent ID's:
1956 // idCallee -> idChildCallee
1958 // make the edge with src and dst so beta info is
1959 // calculated once, then copy it for each new edge in caller
1961 RefEdge edgeNewInCallerTemplate = new RefEdge( null,
1963 edgeCallee.getType(),
1964 edgeCallee.getField(),
1966 funcScriptR( toShadowTokens( ogCallee,
1967 edgeCallee.getBeta()
1973 rewriteCallerReachability( bogusIndex,
1975 edgeNewInCallerTemplate,
1976 edgeNewInCallerTemplate.getBeta(),
1978 paramIndex2rewrite_d_p,
1979 paramIndex2rewrite_d_s,
1980 paramIndex2rewriteD,
1985 edgeNewInCallerTemplate.applyBetaNew();
1988 // So now make a set of possible source heaps in the caller graph
1989 // and a set of destination heaps in the caller graph, and make
1990 // a reference edge in the caller for every possible (src,dst) pair
1991 HashSet<HeapRegionNode> possibleCallerSrcs =
1992 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1993 (HeapRegionNode) edgeCallee.getSrc(),
1997 HashSet<HeapRegionNode> possibleCallerDsts =
1998 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1999 edgeCallee.getDst(),
2003 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
2004 Iterator srcItr = possibleCallerSrcs.iterator();
2005 while( srcItr.hasNext() ) {
2006 HeapRegionNode src = (HeapRegionNode) srcItr.next();
2008 if( !hasMatchingField( src, edgeCallee ) ) {
2009 // prune this source node possibility
2013 Iterator dstItr = possibleCallerDsts.iterator();
2014 while( dstItr.hasNext() ) {
2015 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
2017 if( !hasMatchingType( edgeCallee, dst ) ) {
2026 // otherwise the caller src and dst pair can match the edge, so make it
2027 TypeDescriptor tdNewEdge =
2028 mostSpecificType( edgeCallee.getType(),
2029 hrnChildCallee.getType(),
2033 RefEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2034 edgeNewInCaller.setSrc( src );
2035 edgeNewInCaller.setDst( dst );
2036 edgeNewInCaller.setType( tdNewEdge );
2039 // handle taint info if callee created this edge
2041 Set<Integer> pParamSet=idPrimary2paramIndexSet.get(dst.getID());
2042 Set<Integer> sParamSet=idSecondary2paramIndexSet.get(dst.getID());
2043 HashSet<Integer> paramSet=new HashSet<Integer>();
2044 if(pParamSet!=null){
2045 paramSet.addAll(pParamSet);
2047 if(sParamSet!=null){
2048 paramSet.addAll(sParamSet);
2050 Iterator<Integer> paramIter=paramSet.iterator();
2051 int newTaintIdentifier=0;
2052 while(paramIter.hasNext()){
2053 Integer paramIdx=paramIter.next();
2054 edgeNewInCaller.tainedBy(paramIdx);
2057 RefEdge edgeExisting = src.getReferenceTo( dst,
2058 edgeNewInCaller.getType(),
2059 edgeNewInCaller.getField() );
2060 if( edgeExisting == null ) {
2061 // if this edge doesn't exist in the caller, create it
2062 addRefEdge( src, dst, edgeNewInCaller );
2065 // if it already exists, merge with it
2066 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2076 // return value may need to be assigned in caller
2077 TempDescriptor returnTemp = fc.getReturnTemp();
2078 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2080 VariableNode lnLhsCaller = getVariableNodeFromTemp( returnTemp );
2081 clearRefEdgesFrom( lnLhsCaller, null, null, true );
2083 VariableNode lnReturnCallee = ogCallee.getVariableNodeFromTemp( tdReturn );
2084 Iterator<RefEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
2085 while( edgeCalleeItr.hasNext() ) {
2086 RefEdge edgeCallee = edgeCalleeItr.next();
2087 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
2089 // some edge types are not possible return values when we can
2090 // see what type variable we are assigning it to
2091 if( !isSuperiorType( returnTemp.getType(), edgeCallee.getType() ) ) {
2092 System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+edgeCallee+" for return temp "+returnTemp );
2097 RefEdge edgeNewInCallerTemplate = new RefEdge( null,
2099 edgeCallee.getType(),
2100 edgeCallee.getField(),
2102 funcScriptR( toShadowTokens(ogCallee,
2103 edgeCallee.getBeta() ),
2107 rewriteCallerReachability( bogusIndex,
2109 edgeNewInCallerTemplate,
2110 edgeNewInCallerTemplate.getBeta(),
2112 paramIndex2rewrite_d_p,
2113 paramIndex2rewrite_d_s,
2114 paramIndex2rewriteD,
2119 edgeNewInCallerTemplate.applyBetaNew();
2122 HashSet<HeapRegionNode> assignCallerRhs =
2123 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2124 edgeCallee.getDst(),
2128 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
2129 while( itrHrn.hasNext() ) {
2130 HeapRegionNode hrnCaller = itrHrn.next();
2132 // don't make edge in caller if it is disallowed by types
2133 if( !isSuperiorType( returnTemp.getType(), hrnCaller.getType() ) ) {
2138 if( !isSuperiorType( returnTemp.getType(), hrnChildCallee.getType() ) ) {
2143 if( !isSuperiorType( edgeCallee.getType(), hrnCaller.getType() ) ) {
2148 TypeDescriptor tdNewEdge =
2149 mostSpecificType( edgeCallee.getType(),
2150 hrnChildCallee.getType(),
2154 // otherwise caller node can match callee edge, so make it
2155 RefEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2156 edgeNewInCaller.setSrc( lnLhsCaller );
2157 edgeNewInCaller.setDst( hrnCaller );
2158 edgeNewInCaller.setType( tdNewEdge );
2160 RefEdge edgeExisting = lnLhsCaller.getReferenceTo( hrnCaller,
2162 edgeNewInCaller.getField() );
2163 if( edgeExisting == null ) {
2165 // if this edge doesn't exist in the caller, create it
2166 addRefEdge( lnLhsCaller, hrnCaller, edgeNewInCaller );
2168 // if it already exists, merge with it
2169 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2177 // merge the shadow nodes of allocation sites back down to normal capacity
2178 Iterator<AllocSite> allocItr = ogCallee.allocSites.iterator();
2179 while( allocItr.hasNext() ) {
2180 AllocSite as = allocItr.next();
2182 // first age each allocation site enough times to make room for the shadow nodes
2183 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2187 // then merge the shadow summary into the normal summary
2188 HeapRegionNode hrnSummary = getSummaryNode( as );
2189 assert hrnSummary != null;
2191 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as );
2192 assert hrnSummaryShadow != null;
2194 mergeIntoSummary( hrnSummaryShadow, hrnSummary );
2196 // then clear off after merge
2197 clearRefEdgesFrom( hrnSummaryShadow, null, null, true );
2198 clearRefEdgesTo ( hrnSummaryShadow, null, null, true );
2199 hrnSummaryShadow.setAlpha( new ReachSet().makeCanonical() );
2201 // then transplant shadow nodes onto the now clean normal nodes
2202 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2204 Integer idIth = as.getIthOldest( i );
2205 HeapRegionNode hrnIth = id2hrn.get( idIth );
2206 Integer idIthShadow = as.getIthOldestShadow( i );
2207 HeapRegionNode hrnIthShadow = id2hrn.get( idIthShadow );
2209 transferOnto( hrnIthShadow, hrnIth );
2211 // clear off shadow nodes after transfer
2212 clearRefEdgesFrom( hrnIthShadow, null, null, true );
2213 clearRefEdgesTo ( hrnIthShadow, null, null, true );
2214 hrnIthShadow.setAlpha( new ReachSet().makeCanonical() );
2217 // finally, globally change shadow tokens into normal tokens
2218 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
2219 while( itrAllVariableNodes.hasNext() ) {
2220 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
2221 VariableNode ln = (VariableNode) me.getValue();
2223 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
2224 while( itrEdges.hasNext() ) {
2225 unshadowTokens( as, itrEdges.next() );
2229 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2230 while( itrAllHRNodes.hasNext() ) {
2231 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
2232 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
2234 unshadowTokens( as, hrnToAge );
2236 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
2237 while( itrEdges.hasNext() ) {
2238 unshadowTokens( as, itrEdges.next() );
2245 // improve reachability as much as possible
2246 if( !DISABLE_GLOBAL_SWEEP ) {
2252 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
2253 fm.getMethod().getSymbol().equals( debugCallee )
2257 writeGraph( "debug9endResolveCall",
2258 true, // write labels (variables)
2259 true, // selectively hide intermediate temp vars
2260 true, // prune unreachable heap regions
2261 false, // show back edges to confirm graph validity
2262 false, // show parameter indices (unmaintained!)
2263 true, // hide subset reachability states
2264 true); // hide edge taints
2265 } catch( IOException e ) {}
2266 System.out.println( " "+mc+" done calling "+fm );
2268 if( x == debugCallMapCount ) {
2278 protected boolean hasMatchingField(HeapRegionNode src, RefEdge edge) {
2280 // if no type, then it's a match-everything region
2281 TypeDescriptor tdSrc = src.getType();
2282 if( tdSrc == null ) {
2286 if( tdSrc.isArray() ) {
2287 TypeDescriptor td = edge.getType();
2290 TypeDescriptor tdSrcDeref = tdSrc.dereference();
2291 assert tdSrcDeref != null;
2293 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
2297 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
2300 // if it's not a class, it doesn't have any fields to match
2301 if( !tdSrc.isClass() ) {
2305 ClassDescriptor cd = tdSrc.getClassDesc();
2306 while( cd != null ) {
2307 Iterator fieldItr = cd.getFields();
2309 while( fieldItr.hasNext() ) {
2310 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
2312 if( fd.getType().equals( edge.getType() ) &&
2313 fd.getSymbol().equals( edge.getField() ) ) {
2318 cd = cd.getSuperDesc();
2321 // otherwise it is a class with fields
2322 // but we didn't find a match
2327 protected boolean hasMatchingType(RefEdge edge, HeapRegionNode dst) {
2329 // if the region has no type, matches everything
2330 TypeDescriptor tdDst = dst.getType();
2331 if( tdDst == null ) {
2335 // if the type is not a class or an array, don't
2336 // match because primitives are copied, no aliases
2337 ClassDescriptor cdDst = tdDst.getClassDesc();
2338 if( cdDst == null && !tdDst.isArray() ) {
2342 // if the edge type is null, it matches everything
2343 TypeDescriptor tdEdge = edge.getType();
2344 if( tdEdge == null ) {
2348 return typeUtil.isSuperorType(tdEdge, tdDst);
2352 protected void unshadowTokens(AllocSite as, RefEdge edge) {
2353 edge.setBeta(edge.getBeta().unshadowTokens(as) );
2356 protected void unshadowTokens(AllocSite as, HeapRegionNode hrn) {
2357 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
2361 private ReachSet toShadowTokens(ReachGraph ogCallee,
2364 ReachSet rsOut = new ReachSet(rsIn).makeCanonical();
2366 Iterator<AllocSite> allocItr = ogCallee.allocSites.iterator();
2367 while( allocItr.hasNext() ) {
2368 AllocSite as = allocItr.next();
2370 rsOut = rsOut.toShadowTokens(as);
2373 return rsOut.makeCanonical();
2377 private void rewriteCallerReachability(Integer paramIndex,
2381 Hashtable<ReachTuple, ReachSet> tokens2states,
2382 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_p,
2383 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_s,
2384 Hashtable<Integer, ReachSet> paramIndex2rewriteD,
2385 ReachGraph ogCallee,
2386 boolean makeChangeSet,
2387 Hashtable<RefEdge, ChangeSet> edgePlannedChanges) {
2389 assert(hrn == null && edge != null) ||
2390 (hrn != null && edge == null);
2392 assert rules != null;
2393 assert tokens2states != null;
2395 ReachSet callerReachabilityNew = new ReachSet().makeCanonical();
2397 // for initializing structures in this method
2398 ReachState ttsEmpty = new ReachState().makeCanonical();
2400 // use this to construct a change set if required; the idea is to
2401 // map every partially rewritten token tuple set to the set of
2402 // caller-context token tuple sets that were used to generate it
2403 Hashtable<ReachState, HashSet<ReachState> > rewritten2source =
2404 new Hashtable<ReachState, HashSet<ReachState> >();
2405 rewritten2source.put( ttsEmpty, new HashSet<ReachState>() );
2408 Iterator<ReachState> rulesItr = rules.iterator();
2409 while(rulesItr.hasNext()) {
2410 ReachState rule = rulesItr.next();
2412 ReachSet rewrittenRule = new ReachSet(ttsEmpty).makeCanonical();
2414 Iterator<ReachTuple> ruleItr = rule.iterator();
2415 while(ruleItr.hasNext()) {
2416 ReachTuple ttCallee = ruleItr.next();
2418 // compute the possibilities for rewriting this callee token
2419 ReachSet ttCalleeRewrites = null;
2420 boolean callerSourceUsed = false;
2422 if( tokens2states.containsKey( ttCallee ) ) {
2423 callerSourceUsed = true;
2424 ttCalleeRewrites = tokens2states.get( ttCallee );
2425 assert ttCalleeRewrites != null;
2427 } else if( ogCallee.paramTokenPrimary2paramIndex.containsKey( ttCallee ) ) {
2429 Integer paramIndex_j = ogCallee.paramTokenPrimary2paramIndex.get( ttCallee );
2430 assert paramIndex_j != null;
2431 ttCalleeRewrites = paramIndex2rewrite_d_p.get( paramIndex_j );
2432 assert ttCalleeRewrites != null;
2434 } else if( ogCallee.paramTokenSecondary2paramIndex.containsKey( ttCallee ) ) {
2436 Integer paramIndex_j = ogCallee.paramTokenSecondary2paramIndex.get( ttCallee );
2437 assert paramIndex_j != null;
2438 ttCalleeRewrites = paramIndex2rewrite_d_s.get( paramIndex_j );
2439 assert ttCalleeRewrites != null;
2441 } else if( ogCallee.paramTokenSecondaryPlus2paramIndex.containsKey( ttCallee ) ) {
2443 Integer paramIndex_j = ogCallee.paramTokenSecondaryPlus2paramIndex.get( ttCallee );
2444 assert paramIndex_j != null;
2445 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
2446 assert ttCalleeRewrites != null;
2448 } else if( ogCallee.paramTokenSecondaryStar2paramIndex.containsKey( ttCallee ) ) {
2450 Integer paramIndex_j = ogCallee.paramTokenSecondaryStar2paramIndex.get( ttCallee );
2451 assert paramIndex_j != null;
2452 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
2453 assert ttCalleeRewrites != null;
2456 // otherwise there's no need for a rewrite, just pass this one on
2457 ReachState ttsCaller = new ReachState( ttCallee ).makeCanonical();
2458 ttCalleeRewrites = new ReachSet( ttsCaller ).makeCanonical();
2461 // branch every version of the working rewritten rule with
2462 // the possibilities for rewriting the current callee token
2463 ReachSet rewrittenRuleWithTTCallee = new ReachSet().makeCanonical();
2465 Iterator<ReachState> rewrittenRuleItr = rewrittenRule.iterator();
2466 while( rewrittenRuleItr.hasNext() ) {
2467 ReachState ttsRewritten = rewrittenRuleItr.next();
2469 Iterator<ReachState> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
2470 while( ttCalleeRewritesItr.hasNext() ) {
2471 ReachState ttsBranch = ttCalleeRewritesItr.next();
2473 ReachState ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
2475 if( makeChangeSet ) {
2476 // in order to keep the list of source token tuple sets
2477 // start with the sets used to make the partially rewritten
2478 // rule up to this point
2479 HashSet<ReachState> sourceSets = rewritten2source.get( ttsRewritten );
2480 assert sourceSets != null;
2482 // make a shallow copy for possible modification
2483 sourceSets = (HashSet<ReachState>) sourceSets.clone();
2485 // if we used something from the caller to rewrite it, remember
2486 if( callerSourceUsed ) {
2487 sourceSets.add( ttsBranch );
2490 // set mapping for the further rewritten rule
2491 rewritten2source.put( ttsRewrittenNext, sourceSets );
2494 rewrittenRuleWithTTCallee =
2495 rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
2499 // now the rewritten rule's possibilities have been extended by
2500 // rewriting the current callee token, remember result
2501 rewrittenRule = rewrittenRuleWithTTCallee;
2504 // the rule has been entirely rewritten into the caller context
2505 // now, so add it to the new reachability information
2506 callerReachabilityNew =
2507 callerReachabilityNew.union( rewrittenRule );
2510 if( makeChangeSet ) {
2511 ChangeSet callerChangeSet = new ChangeSet().makeCanonical();
2513 // each possibility for the final reachability should have a set of
2514 // caller sources mapped to it, use to create the change set
2515 Iterator<ReachState> callerReachabilityItr = callerReachabilityNew.iterator();
2516 while( callerReachabilityItr.hasNext() ) {
2517 ReachState ttsRewrittenFinal = callerReachabilityItr.next();
2518 HashSet<ReachState> sourceSets = rewritten2source.get( ttsRewrittenFinal );
2519 assert sourceSets != null;
2521 Iterator<ReachState> sourceSetsItr = sourceSets.iterator();
2522 while( sourceSetsItr.hasNext() ) {
2523 ReachState ttsSource = sourceSetsItr.next();
2526 callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
2530 assert edgePlannedChanges != null;
2531 edgePlannedChanges.put( edge, callerChangeSet );
2535 edge.setBetaNew( edge.getBetaNew().union( callerReachabilityNew ) );
2537 hrn.setAlphaNew( hrn.getAlphaNew().union( callerReachabilityNew ) );
2543 private HashSet<HeapRegionNode>
2544 getHRNSetThatPossiblyMapToCalleeHRN( ReachGraph ogCallee,
2545 HeapRegionNode hrnCallee,
2546 Hashtable<Integer, Set<HeapRegionNode> > pi2dr,
2547 Hashtable<Integer, Set<HeapRegionNode> > pi2r
2550 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
2552 Set<Integer> paramIndicesCallee_p = ogCallee.idPrimary2paramIndexSet .get( hrnCallee.getID() );
2553 Set<Integer> paramIndicesCallee_s = ogCallee.idSecondary2paramIndexSet.get( hrnCallee.getID() );
2555 if( paramIndicesCallee_p == null &&
2556 paramIndicesCallee_s == null ) {
2557 // this is a node allocated in the callee and it has
2558 // exactly one shadow node in the caller to map to
2559 AllocSite as = hrnCallee.getAllocSite();
2562 int age = as.getAgeCategory( hrnCallee.getID() );
2563 assert age != AllocSite.AGE_notInThisSite;
2566 if( age == AllocSite.AGE_summary ) {
2567 idCaller = as.getSummaryShadow();
2569 } else if( age == AllocSite.AGE_oldest ) {
2570 idCaller = as.getOldestShadow();
2573 assert age == AllocSite.AGE_in_I;
2575 Integer I = as.getAge( hrnCallee.getID() );
2578 idCaller = as.getIthOldestShadow( I );
2581 assert id2hrn.containsKey( idCaller );
2582 possibleCallerHRNs.add( id2hrn.get( idCaller ) );
2584 return possibleCallerHRNs;
2587 // find out what primary objects this might be
2588 if( paramIndicesCallee_p != null ) {
2589 // this is a node that was created to represent a parameter
2590 // so it maps to some regions directly reachable from the arg labels
2591 Iterator<Integer> itrIndex = paramIndicesCallee_p.iterator();
2592 while( itrIndex.hasNext() ) {
2593 Integer paramIndexCallee = itrIndex.next();
2594 assert pi2dr.containsKey( paramIndexCallee );
2595 possibleCallerHRNs.addAll( pi2dr.get( paramIndexCallee ) );
2599 // find out what secondary objects this might be
2600 if( paramIndicesCallee_s != null ) {
2601 // this is a node that was created to represent objs reachable from
2602 // some parameter, so it maps to regions reachable from the arg labels
2603 Iterator<Integer> itrIndex = paramIndicesCallee_s.iterator();
2604 while( itrIndex.hasNext() ) {
2605 Integer paramIndexCallee = itrIndex.next();
2606 assert pi2r.containsKey( paramIndexCallee );
2607 possibleCallerHRNs.addAll( pi2r.get( paramIndexCallee ) );
2611 // TODO: is this true?
2612 // one of the two cases above should have put something in here
2613 //assert !possibleCallerHRNs.isEmpty();
2615 return possibleCallerHRNs;
2620 ////////////////////////////////////////////////////
2622 // This global sweep is an optional step to prune
2623 // reachability sets that are not internally
2624 // consistent with the global graph. It should be
2625 // invoked after strong updates or method calls.
2627 ////////////////////////////////////////////////////
2628 public void globalSweep() {
2630 // boldB is part of the phase 1 sweep
2631 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
2632 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2634 // visit every heap region to initialize alphaNew and calculate boldB
2635 Set hrns = id2hrn.entrySet();
2636 Iterator itrHrns = hrns.iterator();
2637 while( itrHrns.hasNext() ) {
2638 Map.Entry me = (Map.Entry)itrHrns.next();
2639 Integer token = (Integer) me.getKey();
2640 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2642 // assert that this node and incoming edges have clean alphaNew
2643 // and betaNew sets, respectively
2644 assert rstateEmpty.equals( hrn.getAlphaNew() );
2646 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2647 while( itrRers.hasNext() ) {
2648 RefEdge edge = itrRers.next();
2649 assert rstateEmpty.equals( edge.getBetaNew() );
2652 // calculate boldB for this flagged node
2653 if( hrn.isFlagged() ) {
2655 Hashtable<RefEdge, ReachSet> boldB_f =
2656 new Hashtable<RefEdge, ReachSet>();
2658 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2660 // initial boldB_f constraints
2661 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2662 while( itrRees.hasNext() ) {
2663 RefEdge edge = itrRees.next();
2665 assert !boldB.containsKey( edge );
2666 boldB_f.put( edge, edge.getBeta() );
2668 assert !workSetEdges.contains( edge );
2669 workSetEdges.add( edge );
2672 // enforce the boldB_f constraint at edges until we reach a fixed point
2673 while( !workSetEdges.isEmpty() ) {
2674 RefEdge edge = workSetEdges.iterator().next();
2675 workSetEdges.remove( edge );
2677 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2678 while( itrPrime.hasNext() ) {
2679 RefEdge edgePrime = itrPrime.next();
2681 ReachSet prevResult = boldB_f.get( edgePrime );
2682 ReachSet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
2684 if( prevResult == null ||
2685 prevResult.union( intersection ).size() > prevResult.size() ) {
2687 if( prevResult == null ) {
2688 boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) );
2690 boldB_f.put( edgePrime, prevResult .union( intersection ) );
2692 workSetEdges.add( edgePrime );
2697 boldB.put( token, boldB_f );
2702 // use boldB to prune tokens from alpha states that are impossible
2703 // and propagate the differences backwards across edges
2704 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2706 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2707 new Hashtable<RefEdge, ChangeSet>();
2709 hrns = id2hrn.entrySet();
2710 itrHrns = hrns.iterator();
2711 while( itrHrns.hasNext() ) {
2712 Map.Entry me = (Map.Entry)itrHrns.next();
2713 Integer token = (Integer) me.getKey();
2714 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2716 // never remove the identity token from a flagged region
2717 // because it is trivially satisfied
2718 ReachTuple ttException = new ReachTuple( token,
2719 !hrn.isSingleObject(),
2720 ReachTuple.ARITY_ONE ).makeCanonical();
2722 ChangeSet cts = new ChangeSet().makeCanonical();
2724 // mark tokens for removal
2725 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2726 while( stateItr.hasNext() ) {
2727 ReachState ttsOld = stateItr.next();
2729 ReachState markedTokens = new ReachState().makeCanonical();
2731 Iterator<ReachTuple> ttItr = ttsOld.iterator();
2732 while( ttItr.hasNext() ) {
2733 ReachTuple ttOld = ttItr.next();
2735 // never remove the identity token from a flagged region
2736 // because it is trivially satisfied
2737 if( hrn.isFlagged() ) {
2738 if( ttOld == ttException ) {
2743 // does boldB_ttOld allow this token?
2744 boolean foundState = false;
2745 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2746 while( incidentEdgeItr.hasNext() ) {
2747 RefEdge incidentEdge = incidentEdgeItr.next();
2749 // if it isn't allowed, mark for removal
2750 Integer idOld = ttOld.getToken();
2751 assert id2hrn.containsKey( idOld );
2752 Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
2753 ReachSet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL!
2754 if( boldB_ttOld_incident != null &&
2755 boldB_ttOld_incident.contains( ttsOld ) ) {
2761 markedTokens = markedTokens.add( ttOld );
2765 // if there is nothing marked, just move on
2766 if( markedTokens.isEmpty() ) {
2767 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
2771 // remove all marked tokens and establish a change set that should
2772 // propagate backwards over edges from this node
2773 ReachState ttsPruned = new ReachState().makeCanonical();
2774 ttItr = ttsOld.iterator();
2775 while( ttItr.hasNext() ) {
2776 ReachTuple ttOld = ttItr.next();
2778 if( !markedTokens.containsTuple( ttOld ) ) {
2779 ttsPruned = ttsPruned.union( ttOld );
2782 assert !ttsOld.equals( ttsPruned );
2784 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
2785 ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
2786 cts = cts.union( ct );
2789 // throw change tuple set on all incident edges
2790 if( !cts.isEmpty() ) {
2791 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2792 while( incidentEdgeItr.hasNext() ) {
2793 RefEdge incidentEdge = incidentEdgeItr.next();
2795 edgesForPropagation.add( incidentEdge );
2797 if( edgePlannedChanges.get( incidentEdge ) == null ) {
2798 edgePlannedChanges.put( incidentEdge, cts );
2800 edgePlannedChanges.put(
2802 edgePlannedChanges.get( incidentEdge ).union( cts )
2809 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2811 propagateTokensOverEdges( edgesForPropagation,
2815 // at the end of the 1st phase reference edges have
2816 // beta, betaNew that correspond to beta and betaR
2818 // commit beta<-betaNew, so beta=betaR and betaNew
2819 // will represent the beta' calculation in 2nd phase
2821 // commit alpha<-alphaNew because it won't change
2822 HashSet<RefEdge> res = new HashSet<RefEdge>();
2824 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2825 while( nodeItr.hasNext() ) {
2826 HeapRegionNode hrn = nodeItr.next();
2827 hrn.applyAlphaNew();
2828 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
2829 while( itrRes.hasNext() ) {
2830 res.add( itrRes.next() );
2836 Iterator<RefEdge> edgeItr = res.iterator();
2837 while( edgeItr.hasNext() ) {
2838 RefEdge edge = edgeItr.next();
2839 HeapRegionNode hrn = edge.getDst();
2841 // commit results of last phase
2842 if( edgesUpdated.contains( edge ) ) {
2843 edge.applyBetaNew();
2846 // compute intial condition of 2nd phase
2847 edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
2850 // every edge in the graph is the initial workset
2851 Set<RefEdge> edgeWorkSet = (Set) res.clone();
2852 while( !edgeWorkSet.isEmpty() ) {
2853 RefEdge edgePrime = edgeWorkSet.iterator().next();
2854 edgeWorkSet.remove( edgePrime );
2856 RefSrcNode on = edgePrime.getSrc();
2857 if( !(on instanceof HeapRegionNode) ) {
2860 HeapRegionNode hrn = (HeapRegionNode) on;
2862 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
2863 while( itrEdge.hasNext() ) {
2864 RefEdge edge = itrEdge.next();
2866 ReachSet prevResult = edge.getBetaNew();
2867 assert prevResult != null;
2869 ReachSet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
2871 if( prevResult.union( intersection ).size() > prevResult.size() ) {
2872 edge.setBetaNew( prevResult.union( intersection ) );
2873 edgeWorkSet.add( edge );
2878 // commit beta' (beta<-betaNew)
2879 edgeItr = res.iterator();
2880 while( edgeItr.hasNext() ) {
2881 edgeItr.next().applyBetaNew();
2887 ////////////////////////////////////////////////////
2888 // high-level merge operations
2889 ////////////////////////////////////////////////////
2890 public void merge_sameMethodContext( ReachGraph rg ) {
2891 // when merging two graphs that abstract the heap
2892 // of the same method context, we just call the
2893 // basic merge operation
2897 public void merge_diffMethodContext( ReachGraph rg ) {
2898 // when merging graphs for abstract heaps in
2899 // different method contexts we should:
2900 // 1) age the allocation sites?
2904 ////////////////////////////////////////////////////
2905 // in merge() and equals() methods the suffix A
2906 // represents the passed in graph and the suffix
2907 // B refers to the graph in this object
2908 // Merging means to take the incoming graph A and
2909 // merge it into B, so after the operation graph B
2910 // is the final result.
2911 ////////////////////////////////////////////////////
2912 protected void merge( ReachGraph rg ) {
2919 mergeRefEdges ( rg );
2920 mergeAllocSites ( rg );
2921 mergeAccessPaths( rg );
2924 protected void mergeNodes( ReachGraph rg ) {
2926 // start with heap region nodes
2927 Set sA = rg.id2hrn.entrySet();
2928 Iterator iA = sA.iterator();
2929 while( iA.hasNext() ) {
2930 Map.Entry meA = (Map.Entry) iA.next();
2931 Integer idA = (Integer) meA.getKey();
2932 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2934 // if this graph doesn't have a node the
2935 // incoming graph has, allocate it
2936 if( !id2hrn.containsKey( idA ) ) {
2937 HeapRegionNode hrnB = hrnA.copy();
2938 id2hrn.put( idA, hrnB );
2941 // otherwise this is a node present in both graphs
2942 // so make the new reachability set a union of the
2943 // nodes' reachability sets
2944 HeapRegionNode hrnB = id2hrn.get( idA );
2945 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
2949 // now add any variable nodes that are in graph B but
2951 sA = rg.td2vn.entrySet();
2953 while( iA.hasNext() ) {
2954 Map.Entry meA = (Map.Entry) iA.next();
2955 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2956 VariableNode lnA = (VariableNode) meA.getValue();
2958 // if the variable doesn't exist in B, allocate and add it
2959 VariableNode lnB = getVariableNodeFromTemp( tdA );
2963 protected void mergeRefEdges( ReachGraph rg ) {
2965 // between heap regions
2966 Set sA = rg.id2hrn.entrySet();
2967 Iterator iA = sA.iterator();
2968 while( iA.hasNext() ) {
2969 Map.Entry meA = (Map.Entry) iA.next();
2970 Integer idA = (Integer) meA.getKey();
2971 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2973 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2974 while( heapRegionsItrA.hasNext() ) {
2975 RefEdge edgeA = heapRegionsItrA.next();
2976 HeapRegionNode hrnChildA = edgeA.getDst();
2977 Integer idChildA = hrnChildA.getID();
2979 // at this point we know an edge in graph A exists
2980 // idA -> idChildA, does this exist in B?
2981 assert id2hrn.containsKey( idA );
2982 HeapRegionNode hrnB = id2hrn.get( idA );
2983 RefEdge edgeToMerge = null;
2985 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2986 while( heapRegionsItrB.hasNext() &&
2987 edgeToMerge == null ) {
2989 RefEdge edgeB = heapRegionsItrB.next();
2990 HeapRegionNode hrnChildB = edgeB.getDst();
2991 Integer idChildB = hrnChildB.getID();
2993 // don't use the RefEdge.equals() here because
2994 // we're talking about existence between graphs,
2995 // not intragraph equal
2996 if( idChildB.equals( idChildA ) &&
2997 edgeB.typeAndFieldEquals( edgeA ) ) {
2999 edgeToMerge = edgeB;
3003 // if the edge from A was not found in B,
3005 if( edgeToMerge == null ) {
3006 assert id2hrn.containsKey( idChildA );
3007 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3008 edgeToMerge = edgeA.copy();
3009 edgeToMerge.setSrc( hrnB );
3010 edgeToMerge.setDst( hrnChildB );
3011 addRefEdge( hrnB, hrnChildB, edgeToMerge );
3013 // otherwise, the edge already existed in both graphs
3014 // so merge their reachability sets
3016 // just replace this beta set with the union
3017 assert edgeToMerge != null;
3018 edgeToMerge.setBeta(
3019 edgeToMerge.getBeta().union( edgeA.getBeta() )
3021 if( !edgeA.isInitialParam() ) {
3022 edgeToMerge.setIsInitialParam( false );
3028 // and then again from variable nodes
3029 sA = rg.td2vn.entrySet();
3031 while( iA.hasNext() ) {
3032 Map.Entry meA = (Map.Entry) iA.next();
3033 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3034 VariableNode vnA = (VariableNode) meA.getValue();
3036 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3037 while( heapRegionsItrA.hasNext() ) {
3038 RefEdge edgeA = heapRegionsItrA.next();
3039 HeapRegionNode hrnChildA = edgeA.getDst();
3040 Integer idChildA = hrnChildA.getID();
3042 // at this point we know an edge in graph A exists
3043 // tdA -> idChildA, does this exist in B?
3044 assert td2vn.containsKey( tdA );
3045 VariableNode vnB = td2vn.get( tdA );
3046 RefEdge edgeToMerge = null;
3048 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3049 while( heapRegionsItrB.hasNext() &&
3050 edgeToMerge == null ) {
3052 RefEdge edgeB = heapRegionsItrB.next();
3053 HeapRegionNode hrnChildB = edgeB.getDst();
3054 Integer idChildB = hrnChildB.getID();
3056 // don't use the RefEdge.equals() here because
3057 // we're talking about existence between graphs
3058 if( idChildB.equals( idChildA ) &&
3059 edgeB.typeAndFieldEquals( edgeA ) ) {
3061 edgeToMerge = edgeB;
3065 // if the edge from A was not found in B,
3067 if( edgeToMerge == null ) {
3068 assert id2hrn.containsKey( idChildA );
3069 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3070 edgeToMerge = edgeA.copy();
3071 edgeToMerge.setSrc( vnB );
3072 edgeToMerge.setDst( hrnChildB );
3073 addRefEdge( vnB, hrnChildB, edgeToMerge );
3075 // otherwise, the edge already existed in both graphs
3076 // so merge their reachability sets
3078 // just replace this beta set with the union
3079 edgeToMerge.setBeta(
3080 edgeToMerge.getBeta().union( edgeA.getBeta() )
3082 if( !edgeA.isInitialParam() ) {
3083 edgeToMerge.setIsInitialParam( false );
3090 protected void mergeAllocSites( ReachGraph rg ) {
3091 allocSites.addAll( rg.allocSites );
3094 protected void mergeAccessPaths( ReachGraph rg ) {
3095 UtilAlgorithms.mergeHashtablesWithHashSetValues( temp2accessPaths,
3096 rg.temp2accessPaths );
3100 // it is necessary in the equals() member functions
3101 // to "check both ways" when comparing the data
3102 // structures of two graphs. For instance, if all
3103 // edges between heap region nodes in graph A are
3104 // present and equal in graph B it is not sufficient
3105 // to say the graphs are equal. Consider that there
3106 // may be edges in graph B that are not in graph A.
3107 // the only way to know that all edges in both graphs
3108 // are equally present is to iterate over both data
3109 // structures and compare against the other graph.
3110 public boolean equals( ReachGraph rg ) {
3116 if( !areHeapRegionNodesEqual( rg ) ) {
3120 if( !areVariableNodesEqual( rg ) ) {
3124 if( !areRefEdgesEqual( rg ) ) {
3128 if( !areAccessPathsEqual( rg ) ) {
3132 // if everything is equal up to this point,
3133 // assert that allocSites is also equal--
3134 // this data is redundant but kept for efficiency
3135 assert allocSites.equals( rg.allocSites );
3141 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3143 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3147 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3154 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3156 Set sA = rgA.id2hrn.entrySet();
3157 Iterator iA = sA.iterator();
3158 while( iA.hasNext() ) {
3159 Map.Entry meA = (Map.Entry) iA.next();
3160 Integer idA = (Integer) meA.getKey();
3161 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3163 if( !rgB.id2hrn.containsKey( idA ) ) {
3167 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3168 if( !hrnA.equalsIncludingAlpha( hrnB ) ) {
3177 protected boolean areVariableNodesEqual( ReachGraph rg ) {
3179 if( !areallVNinAalsoinBandequal( this, rg ) ) {
3183 if( !areallVNinAalsoinBandequal( rg, this ) ) {
3190 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3192 Set sA = rgA.td2vn.entrySet();
3193 Iterator iA = sA.iterator();
3194 while( iA.hasNext() ) {
3195 Map.Entry meA = (Map.Entry) iA.next();
3196 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3198 if( !rgB.td2vn.containsKey( tdA ) ) {
3207 protected boolean areRefEdgesEqual( ReachGraph rg ) {
3208 if( !areallREinAandBequal( this, rg ) ) {
3215 static protected boolean areallREinAandBequal( ReachGraph rgA,
3218 // check all the heap region->heap region edges
3219 Set sA = rgA.id2hrn.entrySet();
3220 Iterator iA = sA.iterator();
3221 while( iA.hasNext() ) {
3222 Map.Entry meA = (Map.Entry) iA.next();
3223 Integer idA = (Integer) meA.getKey();
3224 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3226 // we should have already checked that the same
3227 // heap regions exist in both graphs
3228 assert rgB.id2hrn.containsKey( idA );
3230 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3234 // then check every edge in B for presence in A, starting
3235 // from the same parent HeapRegionNode
3236 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3238 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3243 // then check all the variable->heap region edges
3244 sA = rgA.td2vn.entrySet();
3246 while( iA.hasNext() ) {
3247 Map.Entry meA = (Map.Entry) iA.next();
3248 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3249 VariableNode vnA = (VariableNode) meA.getValue();
3251 // we should have already checked that the same
3252 // label nodes exist in both graphs
3253 assert rgB.td2vn.containsKey( tdA );
3255 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3259 // then check every edge in B for presence in A, starting
3260 // from the same parent VariableNode
3261 VariableNode vnB = rgB.td2vn.get( tdA );
3263 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3272 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3276 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3277 while( itrA.hasNext() ) {
3278 RefEdge edgeA = itrA.next();
3279 HeapRegionNode hrnChildA = edgeA.getDst();
3280 Integer idChildA = hrnChildA.getID();
3282 assert rgB.id2hrn.containsKey( idChildA );
3284 // at this point we know an edge in graph A exists
3285 // rnA -> idChildA, does this exact edge exist in B?
3286 boolean edgeFound = false;
3288 RefSrcNode rnB = null;
3289 if( rnA instanceof HeapRegionNode ) {
3290 HeapRegionNode hrnA = (HeapRegionNode) rnA;
3291 rnB = rgB.id2hrn.get( hrnA.getID() );
3293 VariableNode vnA = (VariableNode) rnA;
3294 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3297 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3298 while( itrB.hasNext() ) {
3299 RefEdge edgeB = itrB.next();
3300 HeapRegionNode hrnChildB = edgeB.getDst();
3301 Integer idChildB = hrnChildB.getID();
3303 if( idChildA.equals( idChildB ) &&
3304 edgeA.typeAndFieldEquals( edgeB ) ) {
3306 // there is an edge in the right place with the right field,
3307 // but do they have the same attributes?
3308 if( edgeA.getBeta().equals( edgeB.getBeta() ) ) {
3323 protected boolean areAccessPathsEqual( ReachGraph rg ) {
3324 return temp2accessPaths.equals( rg.temp2accessPaths );
3328 // use this method to make a new reach graph that is
3329 // what heap the FlatMethod callee from the FlatCall
3330 // would start with reaching from its arguments in
3332 public ReachGraph makeCalleeView( FlatCall fc,
3335 // the callee view is a new graph: DON'T MODIFY
3337 ReachGraph rg = new ReachGraph();
3339 // track what parts of this graph have already been
3340 // added to callee view, variables not needed.
3341 // Note that we need this because when we traverse
3342 // this caller graph for each parameter we may find
3343 // nodes and edges more than once (which the per-param
3344 // "visit" sets won't show) and we only want to create
3345 // an element in the new callee view one time
3346 Set callerNodesCopiedToCallee = new HashSet<HeapRegionNode>();
3347 Set callerEdgesCopiedToCallee = new HashSet<RefEdge>();
3349 // a conservative starting point is to take the
3350 // mechanically-reachable-from-arguments graph
3351 // as opposed to using reachability information
3352 // to prune the graph further
3353 for( int i = 0; i < fm.numParameters(); ++i ) {
3355 // for each parameter index, get the symbol in the
3356 // caller view and callee view
3358 // argument defined here is the symbol in the caller
3359 TempDescriptor tdArg = fc.getArgMatchingParamIndex( fm, i );
3361 // parameter defined here is the symbol in the callee
3362 TempDescriptor tdParam = fm.getParameter( i );
3364 // use these two VariableNode objects to translate
3365 // between caller and callee--its easy to compare
3366 // a HeapRegionNode across callee and caller because
3367 // they will have the same heap region ID
3368 VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
3369 VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
3371 // now traverse the caller view using the argument to
3372 // build the callee view which has the parameter symbol
3373 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
3374 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
3375 toVisitInCaller.add( vnCaller );
3377 while( !toVisitInCaller.isEmpty() ) {
3378 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
3379 RefSrcNode rsnCallee;
3381 toVisitInCaller.remove( rsnCaller );
3382 visitedInCaller.add( rsnCaller );
3384 // FIRST - setup the source end of an edge
3386 if( rsnCaller == vnCaller ) {
3387 // if the caller node is the param symbol, we
3388 // have to do this translation for the callee
3389 rsnCallee = vnCallee;
3391 // otherwise the callee-view node is a heap
3392 // region with the same ID, that may or may
3393 // not have been created already
3394 assert rsnCaller instanceof HeapRegionNode;
3396 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
3397 if( !callerNodesCopiedToCallee.contains( rsnCaller ) ) {
3399 rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
3400 hrnSrcCaller.isSingleObject(),
3401 hrnSrcCaller.isNewSummary(),
3402 hrnSrcCaller.isFlagged(),
3403 hrnSrcCaller.getType(),
3404 hrnSrcCaller.getAllocSite(),
3405 hrnSrcCaller.getAlpha(),
3406 hrnSrcCaller.getDescription()
3408 callerNodesCopiedToCallee.add( rsnCaller );
3410 rsnCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
3414 // SECOND - go over all edges from that source
3416 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
3417 while( itrRefEdges.hasNext() ) {
3418 RefEdge reCaller = itrRefEdges.next();
3419 HeapRegionNode hrnCaller = reCaller.getDst();
3420 HeapRegionNode hrnCallee;
3422 // THIRD - setup destination ends of edges
3424 if( !callerNodesCopiedToCallee.contains( hrnCaller ) ) {
3426 rg.createNewHeapRegionNode( hrnCaller.getID(),
3427 hrnCaller.isSingleObject(),
3428 hrnCaller.isNewSummary(),
3429 hrnCaller.isFlagged(),
3430 hrnCaller.getType(),
3431 hrnCaller.getAllocSite(),
3432 hrnCaller.getAlpha(),
3433 hrnCaller.getDescription()
3435 callerNodesCopiedToCallee.add( hrnCaller );
3437 hrnCallee = rg.id2hrn.get( hrnCaller.getID() );
3440 // FOURTH - copy edge over if needed
3441 if( !callerEdgesCopiedToCallee.contains( reCaller ) ) {
3442 rg.addRefEdge( rsnCallee,
3444 new RefEdge( rsnCallee,
3447 reCaller.getField(),
3448 true, // isInitialParam
3452 callerEdgesCopiedToCallee.add( reCaller );
3455 // keep traversing nodes reachable from param i
3456 // that we haven't visited yet
3457 if( !visitedInCaller.contains( hrnCaller ) ) {
3458 toVisitInCaller.add( hrnCaller );
3461 } // end edge iteration
3462 } // end visiting heap nodes in caller
3463 } // end iterating over parameters as starting points
3465 // Now take the callee view graph we've built from the
3466 // caller and look backwards: for every node in the callee
3467 // look back in the caller for "upstream" reference edges.
3468 // We need to add special elements to the callee view that
3469 // capture relevant effects for mapping back
3472 rg.writeGraph( "calleeview", true, true, true, false, true, true );
3473 } catch( IOException e ) {}
3475 if( fc.getMethod().getSymbol().equals( "f1" ) ) {
3484 public Set<HeapRegionNode> findCommonReachableNodes( HeapRegionNode hrn1,
3485 HeapRegionNode hrn2 ) {
3487 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
3488 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
3490 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
3491 todoNodes1.add( hrn1 );
3493 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
3494 todoNodes2.add( hrn2 );
3496 // follow links until all reachable nodes have been found
3497 while( !todoNodes1.isEmpty() ) {
3498 HeapRegionNode hrn = todoNodes1.iterator().next();
3499 todoNodes1.remove( hrn );
3500 reachableNodes1.add(hrn);
3502 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
3503 while( edgeItr.hasNext() ) {
3504 RefEdge edge = edgeItr.next();
3506 if( !reachableNodes1.contains( edge.getDst() ) ) {
3507 todoNodes1.add( edge.getDst() );
3512 while( !todoNodes2.isEmpty() ) {
3513 HeapRegionNode hrn = todoNodes2.iterator().next();
3514 todoNodes2.remove( hrn );
3515 reachableNodes2.add(hrn);
3517 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
3518 while( edgeItr.hasNext() ) {
3519 RefEdge edge = edgeItr.next();
3521 if( !reachableNodes2.contains( edge.getDst() ) ) {
3522 todoNodes2.add( edge.getDst() );
3527 Set<HeapRegionNode> intersection =
3528 new HashSet<HeapRegionNode>( reachableNodes1 );
3530 intersection.retainAll( reachableNodes2 );
3532 return intersection;
3537 public void writeGraph( String graphName,
3538 boolean writeLabels,
3539 boolean labelSelect,
3540 boolean pruneGarbage,
3541 boolean writeReferencers,
3542 boolean hideSubsetReachability,
3543 boolean hideEdgeTaints
3544 ) throws java.io.IOException {
3546 // remove all non-word characters from the graph name so
3547 // the filename and identifier in dot don't cause errors
3548 graphName = graphName.replaceAll( "[\\W]", "" );
3551 new BufferedWriter( new FileWriter( graphName+".dot" ) );
3553 bw.write( "digraph "+graphName+" {\n" );
3555 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3557 // then visit every heap region node
3558 Set s = id2hrn.entrySet();
3559 Iterator i = s.iterator();
3560 while( i.hasNext() ) {
3561 Map.Entry me = (Map.Entry) i.next();
3562 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3564 if( !pruneGarbage ||
3565 (hrn.isFlagged() && hrn.getID() > 0) ||
3566 hrn.getDescription().startsWith( "param" )
3569 if( !visited.contains( hrn ) ) {
3570 traverseHeapRegionNodes( hrn,
3575 hideSubsetReachability,
3581 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
3584 // then visit every label node, useful for debugging
3586 s = td2vn.entrySet();
3588 while( i.hasNext() ) {
3589 Map.Entry me = (Map.Entry) i.next();
3590 VariableNode vn = (VariableNode) me.getValue();
3593 String labelStr = vn.getTempDescriptorString();
3594 if( labelStr.startsWith("___temp") ||
3595 labelStr.startsWith("___dst") ||
3596 labelStr.startsWith("___srctmp") ||
3597 labelStr.startsWith("___neverused")
3603 //bw.write(" "+vn.toString() + ";\n");
3605 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3606 while( heapRegionsItr.hasNext() ) {
3607 RefEdge edge = heapRegionsItr.next();
3608 HeapRegionNode hrn = edge.getDst();
3610 if( pruneGarbage && !visited.contains( hrn ) ) {
3611 traverseHeapRegionNodes( hrn,
3616 hideSubsetReachability,
3620 bw.write( " " + vn.toString() +
3621 " -> " + hrn.toString() +
3622 "[label=\"" + edge.toGraphEdgeString( hideSubsetReachability ) +
3623 "\",decorate];\n" );
3632 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
3635 Set<HeapRegionNode> visited,
3636 boolean writeReferencers,
3637 boolean hideSubsetReachability,
3638 boolean hideEdgeTaints
3639 ) throws java.io.IOException {
3641 if( visited.contains( hrn ) ) {
3646 String attributes = "[";
3648 if( hrn.isSingleObject() ) {
3649 attributes += "shape=box";
3651 attributes += "shape=Msquare";
3654 if( hrn.isFlagged() ) {
3655 attributes += ",style=filled,fillcolor=lightgrey";
3658 attributes += ",label=\"ID" +
3662 if( hrn.getType() != null ) {
3663 attributes += hrn.getType().toPrettyString() + "\\n";
3666 attributes += hrn.getDescription() +
3668 hrn.getAlphaString( hideSubsetReachability ) +
3671 bw.write( " "+hrn.toString()+attributes+";\n" );
3674 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3675 while( childRegionsItr.hasNext() ) {
3676 RefEdge edge = childRegionsItr.next();
3677 HeapRegionNode hrnChild = edge.getDst();
3679 bw.write( " " +hrn.toString()+
3680 " -> " +hrnChild.toString()+
3681 "[label=\""+edge.toGraphEdgeString( hideSubsetReachability )+
3684 traverseHeapRegionNodes( hrnChild,
3689 hideSubsetReachability,
3695 // in this analysis specifically:
3696 // we have a notion that a null type is the "match any" type,
3697 // so wrap calls to the utility methods that deal with null
3698 public TypeDescriptor mostSpecificType( TypeDescriptor td1,
3699 TypeDescriptor td2 ) {
3706 if( td1.isNull() ) {
3709 if( td2.isNull() ) {
3712 return typeUtil.mostSpecific( td1, td2 );
3715 public TypeDescriptor mostSpecificType( TypeDescriptor td1,
3717 TypeDescriptor td3 ) {
3719 return mostSpecificType( td1,
3720 mostSpecificType( td2, td3 )
3724 public TypeDescriptor mostSpecificType( TypeDescriptor td1,
3727 TypeDescriptor td4 ) {
3729 return mostSpecificType( mostSpecificType( td1, td2 ),
3730 mostSpecificType( td3, td4 )
3734 // remember, in this analysis a null type means "any type"
3735 public boolean isSuperiorType( TypeDescriptor possibleSuper,
3736 TypeDescriptor possibleChild ) {
3737 if( possibleSuper == null ||
3738 possibleChild == null ) {
3742 if( possibleSuper.isNull() ||
3743 possibleChild.isNull() ) {
3747 return typeUtil.isSuperorType( possibleSuper, possibleChild );
3751 public String generateUniqueIdentifier(FlatMethod fm, int paramIdx, String type){
3753 //type: A->aliapsed parameter heap region
3754 // P -> primary paramter heap region
3755 // S -> secondary paramter heap region
3758 if(type.equals("A")){
3760 identifier="FM"+fm.hashCode()+".A";
3762 identifier="FM"+fm.hashCode()+"."+paramIdx+"."+type;
3768 public String generateUniqueIdentifier(AllocSite as, int age, boolean isSummary){
3772 FlatNew fn=as.getFlatNew();
3775 identifier="FN"+fn.hashCode()+".S";
3777 identifier="FN"+fn.hashCode()+"."+age;