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 = false;
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 );
65 // the reason for this method is to have the option
66 // of creating new heap regions with specific IDs, or
67 // duplicating heap regions with specific IDs (especially
68 // in the merge() operation) or to create new heap
69 // regions with a new unique ID
70 protected HeapRegionNode
71 createNewHeapRegionNode( Integer id,
72 boolean isSingleObject,
81 boolean markForAnalysis = isFlagged;
83 TypeDescriptor typeToUse = null;
84 if( allocSite != null ) {
85 typeToUse = allocSite.getType();
90 if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
91 markForAnalysis = true;
95 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
99 if( markForAnalysis ) {
100 alpha = new ReachSet(
107 alpha = rsetWithEmptyState;
111 HeapRegionNode hrn = new HeapRegionNode( id,
119 id2hrn.put( id, hrn );
125 ////////////////////////////////////////////////
127 // Low-level referencee and referencer methods
129 // These methods provide the lowest level for
130 // creating references between reachability nodes
131 // and handling the details of maintaining both
132 // list of referencers and referencees.
134 ////////////////////////////////////////////////
135 protected void addRefEdge( RefSrcNode referencer,
136 HeapRegionNode referencee,
138 assert referencer != null;
139 assert referencee != null;
141 assert edge.getSrc() == referencer;
142 assert edge.getDst() == referencee;
144 referencer.addReferencee( edge );
145 referencee.addReferencer( edge );
148 protected void removeRefEdge( RefEdge e ) {
149 removeRefEdge( e.getSrc(),
155 protected void removeRefEdge( RefSrcNode referencer,
156 HeapRegionNode referencee,
159 assert referencer != null;
160 assert referencee != null;
162 RefEdge edge = referencer.getReferenceTo( referencee,
166 assert edge == referencee.getReferenceFrom( referencer,
170 referencer.removeReferencee( edge );
171 referencee.removeReferencer( edge );
174 protected void clearRefEdgesFrom( RefSrcNode referencer,
177 boolean removeAll ) {
178 assert referencer != null;
180 // get a copy of the set to iterate over, otherwise
181 // we will be trying to take apart the set as we
182 // are iterating over it, which won't work
183 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
184 while( i.hasNext() ) {
185 RefEdge edge = i.next();
188 (edge.typeEquals( type ) && edge.fieldEquals( field ))
191 HeapRegionNode referencee = edge.getDst();
193 removeRefEdge( referencer,
201 protected void clearRefEdgesTo( HeapRegionNode referencee,
204 boolean removeAll ) {
205 assert referencee != null;
207 // get a copy of the set to iterate over, otherwise
208 // we will be trying to take apart the set as we
209 // are iterating over it, which won't work
210 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
211 while( i.hasNext() ) {
212 RefEdge edge = i.next();
215 (edge.typeEquals( type ) && edge.fieldEquals( field ))
218 RefSrcNode referencer = edge.getSrc();
220 removeRefEdge( referencer,
229 ////////////////////////////////////////////////////
231 // Assignment Operation Methods
233 // These methods are high-level operations for
234 // modeling program assignment statements using
235 // the low-level reference create/remove methods
238 ////////////////////////////////////////////////////
240 public void nullifyDeadVars( Set<TempDescriptor> liveIn ) {
244 // make a set of the temps that are out of scope, don't
245 // consider them when nullifying dead in-scope variables
246 Set<TempDescriptor> outOfScope = new HashSet<TempDescriptor>();
247 outOfScope.add( tdReturn );
248 outOfScope.add( tdAliasBlob );
249 outOfScope.addAll( paramIndex2tdQ.values() );
250 outOfScope.addAll( paramIndex2tdR.values() );
252 Iterator varItr = td2vn.entrySet().iterator();
253 while( varItr.hasNext() ) {
254 Map.Entry me = (Map.Entry) varItr.next();
255 TempDescriptor td = (TempDescriptor) me.getKey();
256 VariableNode ln = (VariableNode) me.getValue();
258 // if this variable is not out-of-scope or live
259 // in graph, nullify its references to anything
260 if( !outOfScope.contains( td ) &&
261 !liveIn.contains( td )
263 clearRefEdgesFrom( ln, null, null, true );
270 public void assignTempXEqualToTempY( TempDescriptor x,
272 assignTempXEqualToCastedTempY( x, y, null );
275 public void assignTempXEqualToCastedTempY( TempDescriptor x,
277 TypeDescriptor tdCast ) {
279 VariableNode lnX = getVariableNodeFromTemp( x );
280 VariableNode lnY = getVariableNodeFromTemp( y );
282 clearRefEdgesFrom( lnX, null, null, true );
284 // note it is possible that the types of temps in the
285 // flat node to analyze will reveal that some typed
286 // edges in the reachability graph are impossible
287 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
289 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
290 while( itrYhrn.hasNext() ) {
291 RefEdge edgeY = itrYhrn.next();
292 HeapRegionNode referencee = edgeY.getDst();
293 RefEdge edgeNew = edgeY.copy();
295 if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
296 impossibleEdges.add( edgeY );
300 edgeNew.setSrc( lnX );
302 edgeNew.setType( mostSpecificType( y.getType(),
309 edgeNew.setField( null );
311 addRefEdge( lnX, referencee, edgeNew );
314 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
315 while( itrImp.hasNext() ) {
316 RefEdge edgeImp = itrImp.next();
317 removeRefEdge( edgeImp );
322 public void assignTempXEqualToTempYFieldF( TempDescriptor x,
324 FieldDescriptor f ) {
325 VariableNode lnX = getVariableNodeFromTemp( x );
326 VariableNode lnY = getVariableNodeFromTemp( y );
328 clearRefEdgesFrom( lnX, null, null, true );
330 // note it is possible that the types of temps in the
331 // flat node to analyze will reveal that some typed
332 // edges in the reachability graph are impossible
333 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
335 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
336 while( itrYhrn.hasNext() ) {
337 RefEdge edgeY = itrYhrn.next();
338 HeapRegionNode hrnY = edgeY.getDst();
339 ReachSet betaY = edgeY.getBeta();
341 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
342 while( itrHrnFhrn.hasNext() ) {
343 RefEdge edgeHrn = itrHrnFhrn.next();
344 HeapRegionNode hrnHrn = edgeHrn.getDst();
345 ReachSet betaHrn = edgeHrn.getBeta();
347 // prune edges that are not a matching field
348 if( edgeHrn.getType() != null &&
349 !edgeHrn.getField().equals( f.getSymbol() )
354 // check for impossible edges
355 if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
356 impossibleEdges.add( edgeHrn );
360 TypeDescriptor tdNewEdge =
361 mostSpecificType( edgeHrn.getType(),
365 RefEdge edgeNew = new RefEdge( lnX,
370 betaY.intersection( betaHrn )
373 addRefEdge( lnX, hrnHrn, edgeNew );
377 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
378 while( itrImp.hasNext() ) {
379 RefEdge edgeImp = itrImp.next();
380 removeRefEdge( edgeImp );
383 // anytime you might remove edges between heap regions
384 // you must global sweep to clean up broken reachability
385 if( !impossibleEdges.isEmpty() ) {
386 if( !DISABLE_GLOBAL_SWEEP ) {
393 public void assignTempXFieldFEqualToTempY( TempDescriptor x,
397 VariableNode lnX = getVariableNodeFromTemp( x );
398 VariableNode lnY = getVariableNodeFromTemp( y );
400 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
401 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
403 // note it is possible that the types of temps in the
404 // flat node to analyze will reveal that some typed
405 // edges in the reachability graph are impossible
406 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
408 // first look for possible strong updates and remove those edges
409 boolean strongUpdate = false;
411 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
412 while( itrXhrn.hasNext() ) {
413 RefEdge edgeX = itrXhrn.next();
414 HeapRegionNode hrnX = edgeX.getDst();
416 // we can do a strong update here if one of two cases holds
418 f != DisjointAnalysis.getArrayField( f.getType() ) &&
419 ( (hrnX.getNumReferencers() == 1) || // case 1
420 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
423 if( !DISABLE_STRONG_UPDATES ) {
425 clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
430 // then do all token propagation
431 itrXhrn = lnX.iteratorToReferencees();
432 while( itrXhrn.hasNext() ) {
433 RefEdge edgeX = itrXhrn.next();
434 HeapRegionNode hrnX = edgeX.getDst();
435 ReachSet betaX = edgeX.getBeta();
436 ReachSet R = hrnX.getAlpha().intersection( edgeX.getBeta() );
438 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
439 while( itrYhrn.hasNext() ) {
440 RefEdge edgeY = itrYhrn.next();
441 HeapRegionNode hrnY = edgeY.getDst();
442 ReachSet O = edgeY.getBeta();
444 // check for impossible edges
445 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
446 impossibleEdges.add( edgeY );
450 // propagate tokens over nodes starting from hrnSrc, and it will
451 // take care of propagating back up edges from any touched nodes
452 ChangeSet Cy = O.unionUpArityToChangeSet( R );
453 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
455 // then propagate back just up the edges from hrn
456 ChangeSet Cx = R.unionUpArityToChangeSet(O);
457 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
459 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
460 new Hashtable<RefEdge, ChangeSet>();
462 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
463 while( referItr.hasNext() ) {
464 RefEdge edgeUpstream = referItr.next();
465 todoEdges.add( edgeUpstream );
466 edgePlannedChanges.put( edgeUpstream, Cx );
469 propagateTokensOverEdges( todoEdges,
476 // apply the updates to reachability
477 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
478 while( nodeItr.hasNext() ) {
479 nodeItr.next().applyAlphaNew();
482 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
483 while( edgeItr.hasNext() ) {
484 edgeItr.next().applyBetaNew();
488 // then go back through and add the new edges
489 itrXhrn = lnX.iteratorToReferencees();
490 while( itrXhrn.hasNext() ) {
491 RefEdge edgeX = itrXhrn.next();
492 HeapRegionNode hrnX = edgeX.getDst();
494 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
495 while( itrYhrn.hasNext() ) {
496 RefEdge edgeY = itrYhrn.next();
497 HeapRegionNode hrnY = edgeY.getDst();
499 // skip impossible edges here, we already marked them
500 // when computing reachability propagations above
501 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
505 // prepare the new reference edge hrnX.f -> hrnY
506 TypeDescriptor tdNewEdge =
507 mostSpecificType( y.getType(),
512 RefEdge edgeNew = new RefEdge( hrnX,
517 edgeY.getBeta().pruneBy( hrnX.getAlpha() )
520 // look to see if an edge with same field exists
521 // and merge with it, otherwise just add the edge
522 RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
526 if( edgeExisting != null ) {
527 edgeExisting.setBeta(
528 edgeExisting.getBeta().union( edgeNew.getBeta() )
530 // a new edge here cannot be reflexive, so existing will
531 // always be also not reflexive anymore
532 edgeExisting.setIsInitialParam( false );
535 addRefEdge( hrnX, hrnY, edgeNew );
540 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
541 while( itrImp.hasNext() ) {
542 RefEdge edgeImp = itrImp.next();
543 removeRefEdge( edgeImp );
546 // if there was a strong update, make sure to improve
547 // reachability with a global sweep
548 if( strongUpdate || !impossibleEdges.isEmpty() ) {
549 if( !DISABLE_GLOBAL_SWEEP ) {
556 public void assignReturnEqualToTemp( TempDescriptor x ) {
558 VariableNode lnR = getVariableNodeFromTemp( tdReturn );
559 VariableNode lnX = getVariableNodeFromTemp( x );
561 clearRefEdgesFrom( lnR, null, null, true );
563 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
564 while( itrXhrn.hasNext() ) {
565 RefEdge edgeX = itrXhrn.next();
566 HeapRegionNode referencee = edgeX.getDst();
567 RefEdge edgeNew = edgeX.copy();
568 edgeNew.setSrc( lnR );
570 addRefEdge( lnR, referencee, edgeNew );
575 public void assignTempEqualToNewAlloc( TempDescriptor x,
582 // after the age operation the newest (or zero-ith oldest)
583 // node associated with the allocation site should have
584 // no references to it as if it were a newly allocated
586 Integer idNewest = as.getIthOldest( 0 );
587 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
588 assert hrnNewest != null;
590 VariableNode lnX = getVariableNodeFromTemp( x );
591 clearRefEdgesFrom( lnX, null, null, true );
593 // make a new reference to allocated node
594 TypeDescriptor type = as.getType();
597 new RefEdge( lnX, // source
601 false, // is initial param
602 hrnNewest.getAlpha() // beta
605 addRefEdge( lnX, hrnNewest, edgeNew );
609 // use the allocation site (unique to entire analysis) to
610 // locate the heap region nodes in this reachability graph
611 // that should be aged. The process models the allocation
612 // of new objects and collects all the oldest allocations
613 // in a summary node to allow for a finite analysis
615 // There is an additional property of this method. After
616 // running it on a particular reachability graph (many graphs
617 // may have heap regions related to the same allocation site)
618 // the heap region node objects in this reachability graph will be
619 // allocated. Therefore, after aging a graph for an allocation
620 // site, attempts to retrieve the heap region nodes using the
621 // integer id's contained in the allocation site should always
622 // return non-null heap regions.
623 public void age( AllocSite as ) {
625 // aging adds this allocation site to the graph's
626 // list of sites that exist in the graph, or does
627 // nothing if the site is already in the list
628 allocSites.add( as );
630 // get the summary node for the allocation site in the context
631 // of this particular reachability graph
632 HeapRegionNode hrnSummary = getSummaryNode( as );
634 // merge oldest node into summary
635 Integer idK = as.getOldest();
636 HeapRegionNode hrnK = id2hrn.get( idK );
637 mergeIntoSummary( hrnK, hrnSummary );
639 // move down the line of heap region nodes
640 // clobbering the ith and transferring all references
641 // to and from i-1 to node i. Note that this clobbers
642 // the oldest node (hrnK) that was just merged into
644 for( int i = allocationDepth - 1; i > 0; --i ) {
646 // move references from the i-1 oldest to the ith oldest
647 Integer idIth = as.getIthOldest( i );
648 HeapRegionNode hrnI = id2hrn.get( idIth );
649 Integer idImin1th = as.getIthOldest( i - 1 );
650 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
652 transferOnto( hrnImin1, hrnI );
655 // as stated above, the newest node should have had its
656 // references moved over to the second oldest, so we wipe newest
657 // in preparation for being the new object to assign something to
658 Integer id0th = as.getIthOldest( 0 );
659 HeapRegionNode hrn0 = id2hrn.get( id0th );
662 // clear all references in and out of newest node
663 clearRefEdgesFrom( hrn0, null, null, true );
664 clearRefEdgesTo ( hrn0, null, null, true );
667 // now tokens in reachability sets need to "age" also
668 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
669 while( itrAllVariableNodes.hasNext() ) {
670 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
671 VariableNode ln = (VariableNode) me.getValue();
673 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
674 while( itrEdges.hasNext() ) {
675 ageTokens(as, itrEdges.next() );
679 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
680 while( itrAllHRNodes.hasNext() ) {
681 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
682 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
684 ageTokens( as, hrnToAge );
686 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
687 while( itrEdges.hasNext() ) {
688 ageTokens( as, itrEdges.next() );
693 // after tokens have been aged, reset newest node's reachability
694 if( hrn0.isFlagged() ) {
695 hrn0.setAlpha( new ReachSet(
697 new ReachTuple( hrn0 ).makeCanonical()
702 hrn0.setAlpha( new ReachSet(
703 new ReachState().makeCanonical()
710 protected HeapRegionNode getSummaryNode( AllocSite as ) {
712 Integer idSummary = as.getSummary();
713 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
715 // If this is null then we haven't touched this allocation site
716 // in the context of the current reachability graph, so allocate
717 // heap region nodes appropriate for the entire allocation site.
718 // This should only happen once per reachability graph per allocation site,
719 // and a particular integer id can be used to locate the heap region
720 // in different reachability graphs that represents the same part of an
722 if( hrnSummary == null ) {
724 boolean hasFlags = false;
725 if( as.getType().isClass() ) {
726 hasFlags = as.getType().getClassDesc().hasFlags();
730 hasFlags = as.getFlag();
733 String strDesc = as.toStringForDOT()+"\\nsummary";
735 createNewHeapRegionNode( idSummary, // id or null to generate a new one
736 false, // single object?
738 hasFlags, // flagged?
739 as.getType(), // type
740 as, // allocation site
741 null, // reachability set
742 strDesc // description
745 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
746 Integer idIth = as.getIthOldest( i );
747 assert !id2hrn.containsKey( idIth );
748 strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
749 createNewHeapRegionNode( idIth, // id or null to generate a new one
750 true, // single object?
752 hasFlags, // flagged?
753 as.getType(), // type
754 as, // allocation site
755 null, // reachability set
756 strDesc // description
765 protected HeapRegionNode getShadowSummaryNode( AllocSite as ) {
767 Integer idShadowSummary = as.getSummaryShadow();
768 HeapRegionNode hrnShadowSummary = id2hrn.get( idShadowSummary );
770 if( hrnShadowSummary == null ) {
772 boolean hasFlags = false;
773 if( as.getType().isClass() ) {
774 hasFlags = as.getType().getClassDesc().hasFlags();
778 hasFlags = as.getFlag();
781 String strDesc = as+"\\n"+as.getType()+"\\nshadowSum";
783 createNewHeapRegionNode( idShadowSummary, // id or null to generate a new one
784 false, // single object?
786 hasFlags, // flagged?
787 as.getType(), // type
788 as, // allocation site
789 null, // reachability set
790 strDesc // description
793 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
794 Integer idShadowIth = as.getIthOldestShadow( i );
795 assert !id2hrn.containsKey( idShadowIth );
796 strDesc = as+"\\n"+as.getType()+"\\n"+i+" shadow";
797 createNewHeapRegionNode( idShadowIth, // id or null to generate a new one
798 true, // single object?
800 hasFlags, // flagged?
801 as.getType(), // type
802 as, // allocation site
803 null, // reachability set
804 strDesc // description
809 return hrnShadowSummary;
813 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
814 assert hrnSummary.isNewSummary();
816 // transfer references _from_ hrn over to hrnSummary
817 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
818 while( itrReferencee.hasNext() ) {
819 RefEdge edge = itrReferencee.next();
820 RefEdge edgeMerged = edge.copy();
821 edgeMerged.setSrc(hrnSummary);
823 HeapRegionNode hrnReferencee = edge.getDst();
824 RefEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee,
828 if( edgeSummary == null ) {
829 // the merge is trivial, nothing to be done
831 // otherwise an edge from the referencer to hrnSummary exists already
832 // and the edge referencer->hrn should be merged with it
833 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
836 addRefEdge(hrnSummary, hrnReferencee, edgeMerged);
839 // next transfer references _to_ hrn over to hrnSummary
840 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
841 while( itrReferencer.hasNext() ) {
842 RefEdge edge = itrReferencer.next();
843 RefEdge edgeMerged = edge.copy();
844 edgeMerged.setDst(hrnSummary);
846 RefSrcNode onReferencer = edge.getSrc();
847 RefEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary,
851 if( edgeSummary == null ) {
852 // the merge is trivial, nothing to be done
854 // otherwise an edge from the referencer to alpha_S exists already
855 // and the edge referencer->alpha_K should be merged with it
856 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
859 addRefEdge(onReferencer, hrnSummary, edgeMerged);
862 // then merge hrn reachability into hrnSummary
863 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
867 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
869 // clear references in and out of node b
870 clearRefEdgesFrom(hrnB, null, null, true);
871 clearRefEdgesTo(hrnB, null, null, true);
873 // copy each edge in and out of A to B
874 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
875 while( itrReferencee.hasNext() ) {
876 RefEdge edge = itrReferencee.next();
877 HeapRegionNode hrnReferencee = edge.getDst();
878 RefEdge edgeNew = edge.copy();
879 edgeNew.setSrc(hrnB);
881 addRefEdge(hrnB, hrnReferencee, edgeNew);
884 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
885 while( itrReferencer.hasNext() ) {
886 RefEdge edge = itrReferencer.next();
887 RefSrcNode onReferencer = edge.getSrc();
888 RefEdge edgeNew = edge.copy();
889 edgeNew.setDst(hrnB);
891 addRefEdge(onReferencer, hrnB, edgeNew);
894 // replace hrnB reachability with hrnA's
895 hrnB.setAlpha(hrnA.getAlpha() );
899 protected void ageTokens(AllocSite as, RefEdge edge) {
900 edge.setBeta(edge.getBeta().ageTokens(as) );
903 protected void ageTokens(AllocSite as, HeapRegionNode hrn) {
904 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
909 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
911 HashSet<HeapRegionNode> nodesWithNewAlpha,
912 HashSet<RefEdge> edgesWithNewBeta) {
914 HashSet<HeapRegionNode> todoNodes
915 = new HashSet<HeapRegionNode>();
916 todoNodes.add(nPrime);
918 HashSet<RefEdge> todoEdges
919 = new HashSet<RefEdge>();
921 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
922 = new Hashtable<HeapRegionNode, ChangeSet>();
923 nodePlannedChanges.put(nPrime, c0);
925 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
926 = new Hashtable<RefEdge, ChangeSet>();
928 // first propagate change sets everywhere they can go
929 while( !todoNodes.isEmpty() ) {
930 HeapRegionNode n = todoNodes.iterator().next();
931 ChangeSet C = nodePlannedChanges.get(n);
933 Iterator<RefEdge> referItr = n.iteratorToReferencers();
934 while( referItr.hasNext() ) {
935 RefEdge edge = referItr.next();
938 if( !edgePlannedChanges.containsKey(edge) ) {
939 edgePlannedChanges.put(edge, new ChangeSet().makeCanonical() );
942 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
945 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
946 while( refeeItr.hasNext() ) {
947 RefEdge edgeF = refeeItr.next();
948 HeapRegionNode m = edgeF.getDst();
950 ChangeSet changesToPass = new ChangeSet().makeCanonical();
952 Iterator<ChangeTuple> itrCprime = C.iterator();
953 while( itrCprime.hasNext() ) {
954 ChangeTuple c = itrCprime.next();
955 if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
956 changesToPass = changesToPass.union(c);
960 if( !changesToPass.isEmpty() ) {
961 if( !nodePlannedChanges.containsKey(m) ) {
962 nodePlannedChanges.put(m, new ChangeSet().makeCanonical() );
965 ChangeSet currentChanges = nodePlannedChanges.get(m);
967 if( !changesToPass.isSubset(currentChanges) ) {
969 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
978 // then apply all of the changes for each node at once
979 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
980 while( itrMap.hasNext() ) {
981 Map.Entry me = (Map.Entry) itrMap.next();
982 HeapRegionNode n = (HeapRegionNode) me.getKey();
983 ChangeSet C = (ChangeSet) me.getValue();
985 // this propagation step is with respect to one change,
986 // so we capture the full change from the old alpha:
987 ReachSet localDelta = n.getAlpha().applyChangeSet( C, true );
989 // but this propagation may be only one of many concurrent
990 // possible changes, so keep a running union with the node's
991 // partially updated new alpha set
992 n.setAlphaNew( n.getAlphaNew().union( localDelta ) );
994 nodesWithNewAlpha.add( n );
997 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
1001 protected void propagateTokensOverEdges(
1002 HashSet<RefEdge> todoEdges,
1003 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1004 HashSet<RefEdge> edgesWithNewBeta) {
1006 // first propagate all change tuples everywhere they can go
1007 while( !todoEdges.isEmpty() ) {
1008 RefEdge edgeE = todoEdges.iterator().next();
1009 todoEdges.remove(edgeE);
1011 if( !edgePlannedChanges.containsKey(edgeE) ) {
1012 edgePlannedChanges.put(edgeE, new ChangeSet().makeCanonical() );
1015 ChangeSet C = edgePlannedChanges.get(edgeE);
1017 ChangeSet changesToPass = new ChangeSet().makeCanonical();
1019 Iterator<ChangeTuple> itrC = C.iterator();
1020 while( itrC.hasNext() ) {
1021 ChangeTuple c = itrC.next();
1022 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1023 changesToPass = changesToPass.union(c);
1027 RefSrcNode onSrc = edgeE.getSrc();
1029 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
1030 HeapRegionNode n = (HeapRegionNode) onSrc;
1032 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1033 while( referItr.hasNext() ) {
1034 RefEdge edgeF = referItr.next();
1036 if( !edgePlannedChanges.containsKey(edgeF) ) {
1037 edgePlannedChanges.put(edgeF, new ChangeSet().makeCanonical() );
1040 ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
1042 if( !changesToPass.isSubset(currentChanges) ) {
1043 todoEdges.add(edgeF);
1044 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
1050 // then apply all of the changes for each edge at once
1051 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1052 while( itrMap.hasNext() ) {
1053 Map.Entry me = (Map.Entry) itrMap.next();
1054 RefEdge e = (RefEdge) me.getKey();
1055 ChangeSet C = (ChangeSet) me.getValue();
1057 // this propagation step is with respect to one change,
1058 // so we capture the full change from the old beta:
1059 ReachSet localDelta = e.getBeta().applyChangeSet( C, true );
1061 // but this propagation may be only one of many concurrent
1062 // possible changes, so keep a running union with the edge's
1063 // partially updated new beta set
1064 e.setBetaNew( e.getBetaNew().union( localDelta ) );
1066 edgesWithNewBeta.add( e );
1072 // resolveMethodCall() is used to incorporate a callee graph's effects into
1073 // *this* graph, which is the caller. This method can also be used, after
1074 // the entire analysis is complete, to perform parameter decomposition for
1075 // a given call chain.
1076 public void resolveMethodCall(FlatCall fc, // call site in caller method
1077 boolean isStatic, // whether it is a static method
1078 FlatMethod fm, // the callee method (when virtual, can be many)
1079 ReachGraph ogCallee, // the callee's current reachability graph
1080 MethodContext mc, // the aliasing context for this call
1081 ParameterDecomposition pd // if this is not null, we're calling after analysis
1085 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
1086 fm.getMethod().getSymbol().equals( debugCallee )
1090 writeGraph("debug1BeforeCall",
1091 true, // write labels (variables)
1092 true, // selectively hide intermediate temp vars
1093 true, // prune unreachable heap regions
1094 false, // show back edges to confirm graph validity
1095 false, // show parameter indices (unmaintained!)
1096 true, // hide subset reachability states
1097 true); // hide edge taints
1099 ogCallee.writeGraph("debug0Callee",
1100 true, // write labels (variables)
1101 true, // selectively hide intermediate temp vars
1102 true, // prune unreachable heap regions
1103 false, // show back edges to confirm graph validity
1104 false, // show parameter indices (unmaintained!)
1105 true, // hide subset reachability states
1106 true); // hide edge taints
1107 } catch( IOException e ) {}
1109 System.out.println( " "+mc+" is calling "+fm );
1114 // define rewrite rules and other structures to organize data by parameter/argument index
1115 Hashtable<Integer, ReachSet> paramIndex2rewriteH_p = new Hashtable<Integer, ReachSet>();
1116 Hashtable<Integer, ReachSet> paramIndex2rewriteH_s = new Hashtable<Integer, ReachSet>();
1118 Hashtable<String, ReachSet> paramIndex2rewriteJ_p2p = new Hashtable<String, ReachSet>(); // select( i, j, f )
1119 Hashtable<String, ReachSet> paramIndex2rewriteJ_p2s = new Hashtable<String, ReachSet>(); // select( i, f )
1120 Hashtable<Integer, ReachSet> paramIndex2rewriteJ_s2p = new Hashtable<Integer, ReachSet>();
1121 Hashtable<Integer, ReachSet> paramIndex2rewriteJ_s2s = new Hashtable<Integer, ReachSet>();
1123 Hashtable<Integer, ReachSet> paramIndex2rewriteK_p = new Hashtable<Integer, ReachSet>();
1124 Hashtable<Integer, ReachSet> paramIndex2rewriteK_p2 = new Hashtable<Integer, ReachSet>();
1125 Hashtable<Integer, ReachSet> paramIndex2rewriteK_s = new Hashtable<Integer, ReachSet>();
1127 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_p = new Hashtable<Integer, ReachSet>();
1128 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_s = new Hashtable<Integer, ReachSet>();
1130 Hashtable<Integer, ReachSet> paramIndex2rewriteD = new Hashtable<Integer, ReachSet>();
1133 Hashtable<Integer, VariableNode> paramIndex2ln = new Hashtable<Integer, VariableNode>();
1136 paramIndex2rewriteH_p.put( bogusIndex, rsIdentity );
1137 paramIndex2rewriteH_s.put( bogusIndex, rsIdentity );
1139 paramIndex2rewriteJ_p2p.put( bogusIndex.toString(), rsIdentity );
1140 paramIndex2rewriteJ_p2s.put( bogusIndex.toString(), rsIdentity );
1141 paramIndex2rewriteJ_s2p.put( bogusIndex, rsIdentity );
1142 paramIndex2rewriteJ_s2s.put( bogusIndex, rsIdentity );
1145 for( int i = 0; i < fm.numParameters(); ++i ) {
1146 Integer paramIndex = new Integer(i);
1148 if( !ogCallee.paramIndex2idPrimary.containsKey( paramIndex ) ) {
1149 // skip this immutable parameter
1153 // setup H (primary)
1154 Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
1155 assert ogCallee.id2hrn.containsKey( idPrimary );
1156 HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
1157 assert hrnPrimary != null;
1158 paramIndex2rewriteH_p.put( paramIndex, toShadowTokens( ogCallee, hrnPrimary.getAlpha() ) );
1160 // setup J (primary->X)
1161 Iterator<RefEdge> p2xItr = hrnPrimary.iteratorToReferencees();
1162 while( p2xItr.hasNext() ) {
1163 RefEdge p2xEdge = p2xItr.next();
1165 // we only care about initial parameter edges here
1166 if( !p2xEdge.isInitialParam() ) { continue; }
1168 HeapRegionNode hrnDst = p2xEdge.getDst();
1170 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
1171 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
1172 while( jItr.hasNext() ) {
1173 Integer j = jItr.next();
1174 paramIndex2rewriteJ_p2p.put( makeMapKey( i, j, p2xEdge.getField() ),
1175 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
1179 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
1180 paramIndex2rewriteJ_p2s.put( makeMapKey( i, p2xEdge.getField() ),
1181 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
1185 // setup K (primary)
1186 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
1187 assert tdParamQ != null;
1188 VariableNode lnParamQ = ogCallee.td2vn.get( tdParamQ );
1189 assert lnParamQ != null;
1190 RefEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnPrimary, null, null );
1191 assert edgeSpecialQ_i != null;
1192 ReachSet qBeta = toShadowTokens( ogCallee, edgeSpecialQ_i.getBeta() );
1194 ReachTuple p_i = ogCallee.paramIndex2paramTokenPrimary .get( paramIndex );
1195 ReachTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( paramIndex );
1197 ReachSet K_p = new ReachSet().makeCanonical();
1198 ReachSet K_p2 = new ReachSet().makeCanonical();
1202 // sort qBeta into K_p1 and K_p2
1203 Iterator<ReachState> ttsItr = qBeta.iterator();
1204 while( ttsItr.hasNext() ) {
1205 ReachState tts = ttsItr.next();
1206 if( s_i != null && tts.containsBoth( p_i, s_i ) ) {
1207 K_p2 = K_p2.union( tts );
1209 K_p = K_p.union( tts );
1213 paramIndex2rewriteK_p .put( paramIndex, K_p );
1214 paramIndex2rewriteK_p2.put( paramIndex, K_p2 );
1217 // if there is a secondary node, compute the rest of the rewrite rules
1218 if( ogCallee.paramIndex2idSecondary.containsKey( paramIndex ) ) {
1220 // setup H (secondary)
1221 Integer idSecondary = ogCallee.paramIndex2idSecondary.get( paramIndex );
1222 assert ogCallee.id2hrn.containsKey( idSecondary );
1223 HeapRegionNode hrnSecondary = ogCallee.id2hrn.get( idSecondary );
1224 assert hrnSecondary != null;
1225 paramIndex2rewriteH_s.put( paramIndex, toShadowTokens( ogCallee, hrnSecondary.getAlpha() ) );
1227 // setup J (secondary->X)
1228 Iterator<RefEdge> s2xItr = hrnSecondary.iteratorToReferencees();
1229 while( s2xItr.hasNext() ) {
1230 RefEdge s2xEdge = s2xItr.next();
1232 if( !s2xEdge.isInitialParam() ) { continue; }
1234 HeapRegionNode hrnDst = s2xEdge.getDst();
1236 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
1237 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
1238 while( jItr.hasNext() ) {
1239 Integer j = jItr.next();
1240 paramIndex2rewriteJ_s2p.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
1244 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
1245 paramIndex2rewriteJ_s2s.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
1249 // setup K (secondary)
1250 TempDescriptor tdParamR = ogCallee.paramIndex2tdR.get( paramIndex );
1251 assert tdParamR != null;
1252 VariableNode lnParamR = ogCallee.td2vn.get( tdParamR );
1253 assert lnParamR != null;
1254 RefEdge edgeSpecialR_i = lnParamR.getReferenceTo( hrnSecondary, null, null );
1255 assert edgeSpecialR_i != null;
1256 paramIndex2rewriteK_s.put( paramIndex,
1257 toShadowTokens( ogCallee, edgeSpecialR_i.getBeta() ) );
1261 // now depending on whether the callee is static or not
1262 // we need to account for a "this" argument in order to
1263 // find the matching argument in the caller context
1264 TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, paramIndex );
1266 // remember which caller arg label maps to param index
1267 VariableNode argLabel_i = getVariableNodeFromTemp( argTemp_i );
1268 paramIndex2ln.put( paramIndex, argLabel_i );
1270 // do a callee-effect strong update pre-pass here
1271 if( argTemp_i.getType().isClass() ) {
1273 Iterator<RefEdge> edgeItr = argLabel_i.iteratorToReferencees();
1274 while( edgeItr.hasNext() ) {
1275 RefEdge edge = edgeItr.next();
1276 HeapRegionNode hrn = edge.getDst();
1278 if( (hrn.getNumReferencers() == 1) || // case 1
1279 (hrn.isSingleObject() && argLabel_i.getNumReferencees() == 1) // case 2
1281 if( !DISABLE_STRONG_UPDATES ) {
1282 effectCalleeStrongUpdates( paramIndex, ogCallee, hrn );
1288 // then calculate the d and D rewrite rules
1289 ReachSet d_i_p = new ReachSet().makeCanonical();
1290 ReachSet d_i_s = new ReachSet().makeCanonical();
1291 Iterator<RefEdge> edgeItr = argLabel_i.iteratorToReferencees();
1292 while( edgeItr.hasNext() ) {
1293 RefEdge edge = edgeItr.next();
1295 d_i_p = d_i_p.union( edge.getBeta().intersection( edge.getDst().getAlpha() ) );
1296 d_i_s = d_i_s.union( edge.getBeta() );
1298 paramIndex2rewrite_d_p.put( paramIndex, d_i_p );
1299 paramIndex2rewrite_d_s.put( paramIndex, d_i_s );
1301 // TODO: we should only do this when we need it, and then
1302 // memoize it for the rest of the mapping procedure
1303 ReachSet D_i = d_i_s.exhaustiveArityCombinations();
1304 paramIndex2rewriteD.put( paramIndex, D_i );
1308 // with respect to each argument, map parameter effects into caller
1309 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1310 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
1312 Hashtable<Integer, Set<HeapRegionNode> > pi2dr =
1313 new Hashtable<Integer, Set<HeapRegionNode> >();
1315 Hashtable<Integer, Set<HeapRegionNode> > pi2r =
1316 new Hashtable<Integer, Set<HeapRegionNode> >();
1318 Set<HeapRegionNode> defParamObj = new HashSet<HeapRegionNode>();
1320 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1321 while( lnArgItr.hasNext() ) {
1322 Map.Entry me = (Map.Entry) lnArgItr.next();
1323 Integer index = (Integer) me.getKey();
1324 VariableNode lnArg_i = (VariableNode) me.getValue();
1326 Set<HeapRegionNode> dr = new HashSet<HeapRegionNode>();
1327 Set<HeapRegionNode> r = new HashSet<HeapRegionNode>();
1328 Set<HeapRegionNode> todo = new HashSet<HeapRegionNode>();
1330 // find all reachable nodes starting with label referencees
1331 Iterator<RefEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1332 while( edgeArgItr.hasNext() ) {
1333 RefEdge edge = edgeArgItr.next();
1334 HeapRegionNode hrn = edge.getDst();
1338 if( lnArg_i.getNumReferencees() == 1 && hrn.isSingleObject() ) {
1339 defParamObj.add( hrn );
1342 Iterator<RefEdge> edgeHrnItr = hrn.iteratorToReferencees();
1343 while( edgeHrnItr.hasNext() ) {
1344 RefEdge edger = edgeHrnItr.next();
1345 todo.add( edger.getDst() );
1348 // then follow links until all reachable nodes have been found
1349 while( !todo.isEmpty() ) {
1350 HeapRegionNode hrnr = todo.iterator().next();
1351 todo.remove( hrnr );
1355 Iterator<RefEdge> edgeItr = hrnr.iteratorToReferencees();
1356 while( edgeItr.hasNext() ) {
1357 RefEdge edger = edgeItr.next();
1358 if( !r.contains( edger.getDst() ) ) {
1359 todo.add( edger.getDst() );
1364 if( hrn.isSingleObject() ) {
1369 pi2dr.put( index, dr );
1370 pi2r .put( index, r );
1373 assert defParamObj.size() <= fm.numParameters();
1375 // if we're in parameter decomposition mode, report some results here
1379 // report primary parameter object mappings
1380 mapItr = pi2dr.entrySet().iterator();
1381 while( mapItr.hasNext() ) {
1382 Map.Entry me = (Map.Entry) mapItr.next();
1383 Integer paramIndex = (Integer) me.getKey();
1384 Set<HeapRegionNode> hrnAset = (Set<HeapRegionNode>) me.getValue();
1386 Iterator<HeapRegionNode> hrnItr = hrnAset.iterator();
1387 while( hrnItr.hasNext() ) {
1388 HeapRegionNode hrnA = hrnItr.next();
1389 pd.mapRegionToParamObject( hrnA, paramIndex );
1393 // report parameter-reachable mappings
1394 mapItr = pi2r.entrySet().iterator();
1395 while( mapItr.hasNext() ) {
1396 Map.Entry me = (Map.Entry) mapItr.next();
1397 Integer paramIndex = (Integer) me.getKey();
1398 Set<HeapRegionNode> hrnRset = (Set<HeapRegionNode>) me.getValue();
1400 Iterator<HeapRegionNode> hrnItr = hrnRset.iterator();
1401 while( hrnItr.hasNext() ) {
1402 HeapRegionNode hrnR = hrnItr.next();
1403 pd.mapRegionToParamReachable( hrnR, paramIndex );
1407 // and we're done in this method for special param decomp mode
1412 // now iterate over reachable nodes to rewrite their alpha, and
1413 // classify edges found for beta rewrite
1414 Hashtable<ReachTuple, ReachSet> tokens2states = new Hashtable<ReachTuple, ReachSet>();
1416 Hashtable< Integer, Set<Vector> > edges_p2p = new Hashtable< Integer, Set<Vector> >();
1417 Hashtable< Integer, Set<Vector> > edges_p2s = new Hashtable< Integer, Set<Vector> >();
1418 Hashtable< Integer, Set<Vector> > edges_s2p = new Hashtable< Integer, Set<Vector> >();
1419 Hashtable< Integer, Set<Vector> > edges_s2s = new Hashtable< Integer, Set<Vector> >();
1420 Hashtable< Integer, Set<Vector> > edges_up_dr = new Hashtable< Integer, Set<Vector> >();
1421 Hashtable< Integer, Set<Vector> > edges_up_r = new Hashtable< Integer, Set<Vector> >();
1423 // so again, with respect to some arg i...
1424 lnArgItr = paramIndex2ln.entrySet().iterator();
1425 while( lnArgItr.hasNext() ) {
1426 Map.Entry me = (Map.Entry) lnArgItr.next();
1427 Integer index = (Integer) me.getKey();
1428 VariableNode lnArg_i = (VariableNode) me.getValue();
1430 ReachTuple p_i = ogCallee.paramIndex2paramTokenPrimary.get( index );
1431 ReachTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( index );
1434 ensureEmptyEdgeIndexPair( edges_p2p, index );
1435 ensureEmptyEdgeIndexPair( edges_p2s, index );
1436 ensureEmptyEdgeIndexPair( edges_s2p, index );
1437 ensureEmptyEdgeIndexPair( edges_s2s, index );
1438 ensureEmptyEdgeIndexPair( edges_up_dr, index );
1439 ensureEmptyEdgeIndexPair( edges_up_r, index );
1441 Set<HeapRegionNode> dr = pi2dr.get( index );
1442 Iterator<HeapRegionNode> hrnItr = dr.iterator();
1443 while( hrnItr.hasNext() ) {
1444 // this heap region is definitely an "a_i" or primary by virtue of being in dr
1445 HeapRegionNode hrn = hrnItr.next();
1447 tokens2states.clear();
1448 tokens2states.put( p_i, hrn.getAlpha() );
1450 rewriteCallerReachability( index,
1453 paramIndex2rewriteH_p.get( index ),
1455 paramIndex2rewrite_d_p,
1456 paramIndex2rewrite_d_s,
1457 paramIndex2rewriteD,
1462 nodesWithNewAlpha.add( hrn );
1465 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
1466 while( edgeItr.hasNext() ) {
1467 RefEdge edge = edgeItr.next();
1468 RefSrcNode on = edge.getSrc();
1470 boolean edge_classified = false;
1473 if( on instanceof HeapRegionNode ) {
1474 // hrn0 may be "a_j" and/or "r_j" or even neither
1475 HeapRegionNode hrn0 = (HeapRegionNode) on;
1477 Iterator itr = pi2dr.entrySet().iterator();
1478 while( itr.hasNext() ) {
1479 Map.Entry mo = (Map.Entry) itr.next();
1480 Integer pi = (Integer) mo.getKey();
1481 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
1483 if( dr_i.contains( hrn0 ) ) {
1484 addEdgeIndexPair( edges_p2p, pi, edge, index );
1485 edge_classified = true;
1489 itr = pi2r.entrySet().iterator();
1490 while( itr.hasNext() ) {
1491 Map.Entry mo = (Map.Entry) itr.next();
1492 Integer pi = (Integer) mo.getKey();
1493 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
1495 if( r_i.contains( hrn0 ) ) {
1496 addEdgeIndexPair( edges_s2p, pi, edge, index );
1497 edge_classified = true;
1502 // all of these edges are upstream of directly reachable objects
1503 if( !edge_classified ) {
1504 addEdgeIndexPair( edges_up_dr, index, edge, index );
1510 Set<HeapRegionNode> r = pi2r.get( index );
1511 hrnItr = r.iterator();
1512 while( hrnItr.hasNext() ) {
1513 // this heap region is definitely an "r_i" or secondary by virtue of being in r
1514 HeapRegionNode hrn = hrnItr.next();
1516 if( paramIndex2rewriteH_s.containsKey( index ) ) {
1518 tokens2states.clear();
1519 tokens2states.put( p_i, new ReachSet().makeCanonical() );
1520 tokens2states.put( s_i, hrn.getAlpha() );
1522 rewriteCallerReachability( index,
1525 paramIndex2rewriteH_s.get( index ),
1527 paramIndex2rewrite_d_p,
1528 paramIndex2rewrite_d_s,
1529 paramIndex2rewriteD,
1534 nodesWithNewAlpha.add( hrn );
1538 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
1539 while( edgeItr.hasNext() ) {
1540 RefEdge edge = edgeItr.next();
1541 RefSrcNode on = edge.getSrc();
1543 boolean edge_classified = false;
1545 if( on instanceof HeapRegionNode ) {
1546 // hrn0 may be "a_j" and/or "r_j" or even neither
1547 HeapRegionNode hrn0 = (HeapRegionNode) on;
1549 Iterator itr = pi2dr.entrySet().iterator();
1550 while( itr.hasNext() ) {
1551 Map.Entry mo = (Map.Entry) itr.next();
1552 Integer pi = (Integer) mo.getKey();
1553 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
1555 if( dr_i.contains( hrn0 ) ) {
1556 addEdgeIndexPair( edges_p2s, pi, edge, index );
1557 edge_classified = true;
1561 itr = pi2r.entrySet().iterator();
1562 while( itr.hasNext() ) {
1563 Map.Entry mo = (Map.Entry) itr.next();
1564 Integer pi = (Integer) mo.getKey();
1565 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
1567 if( r_i.contains( hrn0 ) ) {
1568 addEdgeIndexPair( edges_s2s, pi, edge, index );
1569 edge_classified = true;
1574 // these edges are all upstream of some reachable node
1575 if( !edge_classified ) {
1576 addEdgeIndexPair( edges_up_r, index, edge, index );
1583 // and again, with respect to some arg i...
1584 lnArgItr = paramIndex2ln.entrySet().iterator();
1585 while( lnArgItr.hasNext() ) {
1586 Map.Entry me = (Map.Entry) lnArgItr.next();
1587 Integer index = (Integer) me.getKey();
1588 VariableNode lnArg_i = (VariableNode) me.getValue();
1591 // update reachable edges
1592 Iterator edgeItr = edges_p2p.get( index ).iterator();
1593 while( edgeItr.hasNext() ) {
1594 Vector mo = (Vector) edgeItr.next();
1595 RefEdge edge = (RefEdge) mo.get( 0 );
1596 Integer indexJ = (Integer) mo.get( 1 );
1598 if( !paramIndex2rewriteJ_p2p.containsKey( makeMapKey( index,
1600 edge.getField() ) ) ) {
1604 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
1607 tokens2states.clear();
1608 tokens2states.put( p_j, edge.getBeta() );
1610 rewriteCallerReachability( index,
1613 paramIndex2rewriteJ_p2p.get( makeMapKey( index,
1615 edge.getField() ) ),
1617 paramIndex2rewrite_d_p,
1618 paramIndex2rewrite_d_s,
1619 paramIndex2rewriteD,
1624 edgesWithNewBeta.add( edge );
1628 edgeItr = edges_p2s.get( index ).iterator();
1629 while( edgeItr.hasNext() ) {
1630 Vector mo = (Vector) edgeItr.next();
1631 RefEdge edge = (RefEdge) mo.get( 0 );
1632 Integer indexJ = (Integer) mo.get( 1 );
1634 if( !paramIndex2rewriteJ_p2s.containsKey( makeMapKey( index,
1635 edge.getField() ) ) ) {
1639 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
1642 tokens2states.clear();
1643 tokens2states.put( s_j, edge.getBeta() );
1645 rewriteCallerReachability( index,
1648 paramIndex2rewriteJ_p2s.get( makeMapKey( index,
1649 edge.getField() ) ),
1651 paramIndex2rewrite_d_p,
1652 paramIndex2rewrite_d_s,
1653 paramIndex2rewriteD,
1658 edgesWithNewBeta.add( edge );
1662 edgeItr = edges_s2p.get( index ).iterator();
1663 while( edgeItr.hasNext() ) {
1664 Vector mo = (Vector) edgeItr.next();
1665 RefEdge edge = (RefEdge) mo.get( 0 );
1666 Integer indexJ = (Integer) mo.get( 1 );
1668 if( !paramIndex2rewriteJ_s2p.containsKey( index ) ) {
1672 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
1675 tokens2states.clear();
1676 tokens2states.put( p_j, edge.getBeta() );
1678 rewriteCallerReachability( index,
1681 paramIndex2rewriteJ_s2p.get( index ),
1683 paramIndex2rewrite_d_p,
1684 paramIndex2rewrite_d_s,
1685 paramIndex2rewriteD,
1690 edgesWithNewBeta.add( edge );
1694 edgeItr = edges_s2s.get( index ).iterator();
1695 while( edgeItr.hasNext() ) {
1696 Vector mo = (Vector) edgeItr.next();
1697 RefEdge edge = (RefEdge) mo.get( 0 );
1698 Integer indexJ = (Integer) mo.get( 1 );
1700 if( !paramIndex2rewriteJ_s2s.containsKey( index ) ) {
1704 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
1707 tokens2states.clear();
1708 tokens2states.put( s_j, edge.getBeta() );
1710 rewriteCallerReachability( index,
1713 paramIndex2rewriteJ_s2s.get( index ),
1715 paramIndex2rewrite_d_p,
1716 paramIndex2rewrite_d_s,
1717 paramIndex2rewriteD,
1722 edgesWithNewBeta.add( edge );
1726 // update directly upstream edges
1727 Hashtable<RefEdge, ChangeSet> edgeUpstreamPlannedChanges =
1728 new Hashtable<RefEdge, ChangeSet>();
1730 HashSet<RefEdge> edgesDirectlyUpstream =
1731 new HashSet<RefEdge>();
1733 edgeItr = edges_up_dr.get( index ).iterator();
1734 while( edgeItr.hasNext() ) {
1735 Vector mo = (Vector) edgeItr.next();
1736 RefEdge edge = (RefEdge) mo.get( 0 );
1737 Integer indexJ = (Integer) mo.get( 1 );
1739 edgesDirectlyUpstream.add( edge );
1741 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
1744 // start with K_p2 and p_j
1745 tokens2states.clear();
1746 tokens2states.put( p_j, edge.getBeta() );
1748 rewriteCallerReachability( index,
1751 paramIndex2rewriteK_p2.get( index ),
1753 paramIndex2rewrite_d_p,
1754 paramIndex2rewrite_d_s,
1755 paramIndex2rewriteD,
1758 edgeUpstreamPlannedChanges );
1760 // and add in s_j, if required, and do K_p
1761 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
1763 tokens2states.put( s_j, edge.getBeta() );
1766 rewriteCallerReachability( index,
1769 paramIndex2rewriteK_p.get( index ),
1771 paramIndex2rewrite_d_p,
1772 paramIndex2rewrite_d_s,
1773 paramIndex2rewriteD,
1776 edgeUpstreamPlannedChanges );
1778 edgesWithNewBeta.add( edge );
1781 propagateTokensOverEdges( edgesDirectlyUpstream,
1782 edgeUpstreamPlannedChanges,
1786 // update upstream edges
1787 edgeUpstreamPlannedChanges =
1788 new Hashtable<RefEdge, ChangeSet>();
1790 HashSet<RefEdge> edgesUpstream =
1791 new HashSet<RefEdge>();
1793 edgeItr = edges_up_r.get( index ).iterator();
1794 while( edgeItr.hasNext() ) {
1795 Vector mo = (Vector) edgeItr.next();
1796 RefEdge edge = (RefEdge) mo.get( 0 );
1797 Integer indexJ = (Integer) mo.get( 1 );
1799 if( !paramIndex2rewriteK_s.containsKey( index ) ) {
1803 edgesUpstream.add( edge );
1805 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
1808 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
1811 tokens2states.clear();
1812 tokens2states.put( p_j, rsWttsEmpty );
1813 tokens2states.put( s_j, edge.getBeta() );
1815 rewriteCallerReachability( index,
1818 paramIndex2rewriteK_s.get( index ),
1820 paramIndex2rewrite_d_p,
1821 paramIndex2rewrite_d_s,
1822 paramIndex2rewriteD,
1825 edgeUpstreamPlannedChanges );
1827 edgesWithNewBeta.add( edge );
1830 propagateTokensOverEdges( edgesUpstream,
1831 edgeUpstreamPlannedChanges,
1834 } // end effects per argument/parameter map
1837 // commit changes to alpha and beta
1838 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1839 while( nodeItr.hasNext() ) {
1840 nodeItr.next().applyAlphaNew();
1843 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
1844 while( edgeItr.hasNext() ) {
1845 edgeItr.next().applyBetaNew();
1849 // verify the existence of allocation sites and their
1850 // shadows from the callee in the context of this caller graph
1851 // then map allocated nodes of callee onto the caller shadows
1853 Hashtable<ReachTuple, ReachSet> tokens2statesEmpty = new Hashtable<ReachTuple, ReachSet>();
1855 Iterator<AllocSite> asItr = ogCallee.allocSites.iterator();
1856 while( asItr.hasNext() ) {
1857 AllocSite allocSite = asItr.next();
1859 // grab the summary in the caller just to make sure
1860 // the allocation site has nodes in the caller
1861 HeapRegionNode hrnSummary = getSummaryNode( allocSite );
1863 // assert that the shadow nodes have no reference edges
1864 // because they're brand new to the graph, or last time
1865 // they were used they should have been cleared of edges
1866 HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
1867 assert hrnShadowSummary.getNumReferencers() == 0;
1868 assert hrnShadowSummary.getNumReferencees() == 0;
1870 // then bring g_ij onto g'_ij and rewrite
1871 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode( allocSite );
1872 hrnShadowSummary.setAlpha( toShadowTokens( ogCallee, hrnSummaryCallee.getAlpha() ) );
1874 // shadow nodes only are touched by a rewrite one time,
1875 // so rewrite and immediately commit--and they don't belong
1876 // to a particular parameter, so use a bogus param index
1877 // that pulls a self-rewrite out of H
1878 rewriteCallerReachability( bogusIndex,
1881 funcScriptR( hrnShadowSummary.getAlpha(), ogCallee, mc ),
1883 paramIndex2rewrite_d_p,
1884 paramIndex2rewrite_d_s,
1885 paramIndex2rewriteD,
1890 hrnShadowSummary.applyAlphaNew();
1893 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1894 Integer idIth = allocSite.getIthOldest(i);
1895 assert id2hrn.containsKey(idIth);
1896 HeapRegionNode hrnIth = id2hrn.get(idIth);
1898 Integer idShadowIth = -(allocSite.getIthOldest(i));
1899 assert id2hrn.containsKey(idShadowIth);
1900 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1901 assert hrnIthShadow.getNumReferencers() == 0;
1902 assert hrnIthShadow.getNumReferencees() == 0;
1904 assert ogCallee.id2hrn.containsKey(idIth);
1905 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1906 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1908 rewriteCallerReachability( bogusIndex,
1911 funcScriptR( hrnIthShadow.getAlpha(), ogCallee, mc ),
1913 paramIndex2rewrite_d_p,
1914 paramIndex2rewrite_d_s,
1915 paramIndex2rewriteD,
1920 hrnIthShadow.applyAlphaNew();
1925 // for every heap region->heap region edge in the
1926 // callee graph, create the matching edge or edges
1927 // in the caller graph
1928 Set sCallee = ogCallee.id2hrn.entrySet();
1929 Iterator iCallee = sCallee.iterator();
1931 while( iCallee.hasNext() ) {
1932 Map.Entry meCallee = (Map.Entry) iCallee.next();
1933 Integer idCallee = (Integer) meCallee.getKey();
1934 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1936 Iterator<RefEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1937 while( heapRegionsItrCallee.hasNext() ) {
1938 RefEdge edgeCallee = heapRegionsItrCallee.next();
1939 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1940 Integer idChildCallee = hrnChildCallee.getID();
1942 // only address this edge if it is not a special initial edge
1943 if( !edgeCallee.isInitialParam() ) {
1945 // now we know that in the callee method's reachability graph
1946 // there is a heap region->heap region reference edge given
1947 // by heap region pointers:
1948 // hrnCallee -> heapChildCallee
1950 // or by the reachability-graph independent ID's:
1951 // idCallee -> idChildCallee
1953 // make the edge with src and dst so beta info is
1954 // calculated once, then copy it for each new edge in caller
1956 RefEdge edgeNewInCallerTemplate = new RefEdge( null,
1958 edgeCallee.getType(),
1959 edgeCallee.getField(),
1961 funcScriptR( toShadowTokens( ogCallee,
1962 edgeCallee.getBeta()
1968 rewriteCallerReachability( bogusIndex,
1970 edgeNewInCallerTemplate,
1971 edgeNewInCallerTemplate.getBeta(),
1973 paramIndex2rewrite_d_p,
1974 paramIndex2rewrite_d_s,
1975 paramIndex2rewriteD,
1980 edgeNewInCallerTemplate.applyBetaNew();
1983 // So now make a set of possible source heaps in the caller graph
1984 // and a set of destination heaps in the caller graph, and make
1985 // a reference edge in the caller for every possible (src,dst) pair
1986 HashSet<HeapRegionNode> possibleCallerSrcs =
1987 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1988 (HeapRegionNode) edgeCallee.getSrc(),
1992 HashSet<HeapRegionNode> possibleCallerDsts =
1993 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1994 edgeCallee.getDst(),
1998 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1999 Iterator srcItr = possibleCallerSrcs.iterator();
2000 while( srcItr.hasNext() ) {
2001 HeapRegionNode src = (HeapRegionNode) srcItr.next();
2003 if( !hasMatchingField( src, edgeCallee ) ) {
2004 // prune this source node possibility
2008 Iterator dstItr = possibleCallerDsts.iterator();
2009 while( dstItr.hasNext() ) {
2010 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
2012 if( !hasMatchingType( edgeCallee, dst ) ) {
2021 // otherwise the caller src and dst pair can match the edge, so make it
2022 TypeDescriptor tdNewEdge =
2023 mostSpecificType( edgeCallee.getType(),
2024 hrnChildCallee.getType(),
2028 RefEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2029 edgeNewInCaller.setSrc( src );
2030 edgeNewInCaller.setDst( dst );
2031 edgeNewInCaller.setType( tdNewEdge );
2034 // handle taint info if callee created this edge
2036 Set<Integer> pParamSet=idPrimary2paramIndexSet.get(dst.getID());
2037 Set<Integer> sParamSet=idSecondary2paramIndexSet.get(dst.getID());
2038 HashSet<Integer> paramSet=new HashSet<Integer>();
2039 if(pParamSet!=null){
2040 paramSet.addAll(pParamSet);
2042 if(sParamSet!=null){
2043 paramSet.addAll(sParamSet);
2045 Iterator<Integer> paramIter=paramSet.iterator();
2046 int newTaintIdentifier=0;
2047 while(paramIter.hasNext()){
2048 Integer paramIdx=paramIter.next();
2049 edgeNewInCaller.tainedBy(paramIdx);
2052 RefEdge edgeExisting = src.getReferenceTo( dst,
2053 edgeNewInCaller.getType(),
2054 edgeNewInCaller.getField() );
2055 if( edgeExisting == null ) {
2056 // if this edge doesn't exist in the caller, create it
2057 addRefEdge( src, dst, edgeNewInCaller );
2060 // if it already exists, merge with it
2061 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2071 // return value may need to be assigned in caller
2072 TempDescriptor returnTemp = fc.getReturnTemp();
2073 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2075 VariableNode lnLhsCaller = getVariableNodeFromTemp( returnTemp );
2076 clearRefEdgesFrom( lnLhsCaller, null, null, true );
2078 VariableNode lnReturnCallee = ogCallee.getVariableNodeFromTemp( tdReturn );
2079 Iterator<RefEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
2080 while( edgeCalleeItr.hasNext() ) {
2081 RefEdge edgeCallee = edgeCalleeItr.next();
2082 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
2084 // some edge types are not possible return values when we can
2085 // see what type variable we are assigning it to
2086 if( !isSuperiorType( returnTemp.getType(), edgeCallee.getType() ) ) {
2087 System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+edgeCallee+" for return temp "+returnTemp );
2092 RefEdge edgeNewInCallerTemplate = new RefEdge( null,
2094 edgeCallee.getType(),
2095 edgeCallee.getField(),
2097 funcScriptR( toShadowTokens(ogCallee,
2098 edgeCallee.getBeta() ),
2102 rewriteCallerReachability( bogusIndex,
2104 edgeNewInCallerTemplate,
2105 edgeNewInCallerTemplate.getBeta(),
2107 paramIndex2rewrite_d_p,
2108 paramIndex2rewrite_d_s,
2109 paramIndex2rewriteD,
2114 edgeNewInCallerTemplate.applyBetaNew();
2117 HashSet<HeapRegionNode> assignCallerRhs =
2118 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2119 edgeCallee.getDst(),
2123 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
2124 while( itrHrn.hasNext() ) {
2125 HeapRegionNode hrnCaller = itrHrn.next();
2127 // don't make edge in caller if it is disallowed by types
2128 if( !isSuperiorType( returnTemp.getType(), hrnCaller.getType() ) ) {
2133 if( !isSuperiorType( returnTemp.getType(), hrnChildCallee.getType() ) ) {
2138 if( !isSuperiorType( edgeCallee.getType(), hrnCaller.getType() ) ) {
2143 TypeDescriptor tdNewEdge =
2144 mostSpecificType( edgeCallee.getType(),
2145 hrnChildCallee.getType(),
2149 // otherwise caller node can match callee edge, so make it
2150 RefEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2151 edgeNewInCaller.setSrc( lnLhsCaller );
2152 edgeNewInCaller.setDst( hrnCaller );
2153 edgeNewInCaller.setType( tdNewEdge );
2155 RefEdge edgeExisting = lnLhsCaller.getReferenceTo( hrnCaller,
2157 edgeNewInCaller.getField() );
2158 if( edgeExisting == null ) {
2160 // if this edge doesn't exist in the caller, create it
2161 addRefEdge( lnLhsCaller, hrnCaller, edgeNewInCaller );
2163 // if it already exists, merge with it
2164 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2172 // merge the shadow nodes of allocation sites back down to normal capacity
2173 Iterator<AllocSite> allocItr = ogCallee.allocSites.iterator();
2174 while( allocItr.hasNext() ) {
2175 AllocSite as = allocItr.next();
2177 // first age each allocation site enough times to make room for the shadow nodes
2178 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2182 // then merge the shadow summary into the normal summary
2183 HeapRegionNode hrnSummary = getSummaryNode( as );
2184 assert hrnSummary != null;
2186 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as );
2187 assert hrnSummaryShadow != null;
2189 mergeIntoSummary( hrnSummaryShadow, hrnSummary );
2191 // then clear off after merge
2192 clearRefEdgesFrom( hrnSummaryShadow, null, null, true );
2193 clearRefEdgesTo ( hrnSummaryShadow, null, null, true );
2194 hrnSummaryShadow.setAlpha( new ReachSet().makeCanonical() );
2196 // then transplant shadow nodes onto the now clean normal nodes
2197 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2199 Integer idIth = as.getIthOldest( i );
2200 HeapRegionNode hrnIth = id2hrn.get( idIth );
2201 Integer idIthShadow = as.getIthOldestShadow( i );
2202 HeapRegionNode hrnIthShadow = id2hrn.get( idIthShadow );
2204 transferOnto( hrnIthShadow, hrnIth );
2206 // clear off shadow nodes after transfer
2207 clearRefEdgesFrom( hrnIthShadow, null, null, true );
2208 clearRefEdgesTo ( hrnIthShadow, null, null, true );
2209 hrnIthShadow.setAlpha( new ReachSet().makeCanonical() );
2212 // finally, globally change shadow tokens into normal tokens
2213 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
2214 while( itrAllVariableNodes.hasNext() ) {
2215 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
2216 VariableNode ln = (VariableNode) me.getValue();
2218 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
2219 while( itrEdges.hasNext() ) {
2220 unshadowTokens( as, itrEdges.next() );
2224 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2225 while( itrAllHRNodes.hasNext() ) {
2226 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
2227 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
2229 unshadowTokens( as, hrnToAge );
2231 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
2232 while( itrEdges.hasNext() ) {
2233 unshadowTokens( as, itrEdges.next() );
2240 // improve reachability as much as possible
2241 if( !DISABLE_GLOBAL_SWEEP ) {
2247 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
2248 fm.getMethod().getSymbol().equals( debugCallee )
2252 writeGraph( "debug9endResolveCall",
2253 true, // write labels (variables)
2254 true, // selectively hide intermediate temp vars
2255 true, // prune unreachable heap regions
2256 false, // show back edges to confirm graph validity
2257 false, // show parameter indices (unmaintained!)
2258 true, // hide subset reachability states
2259 true); // hide edge taints
2260 } catch( IOException e ) {}
2261 System.out.println( " "+mc+" done calling "+fm );
2263 if( x == debugCallMapCount ) {
2273 protected boolean hasMatchingField(HeapRegionNode src, RefEdge edge) {
2275 // if no type, then it's a match-everything region
2276 TypeDescriptor tdSrc = src.getType();
2277 if( tdSrc == null ) {
2281 if( tdSrc.isArray() ) {
2282 TypeDescriptor td = edge.getType();
2285 TypeDescriptor tdSrcDeref = tdSrc.dereference();
2286 assert tdSrcDeref != null;
2288 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
2292 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
2295 // if it's not a class, it doesn't have any fields to match
2296 if( !tdSrc.isClass() ) {
2300 ClassDescriptor cd = tdSrc.getClassDesc();
2301 while( cd != null ) {
2302 Iterator fieldItr = cd.getFields();
2304 while( fieldItr.hasNext() ) {
2305 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
2307 if( fd.getType().equals( edge.getType() ) &&
2308 fd.getSymbol().equals( edge.getField() ) ) {
2313 cd = cd.getSuperDesc();
2316 // otherwise it is a class with fields
2317 // but we didn't find a match
2322 protected boolean hasMatchingType(RefEdge edge, HeapRegionNode dst) {
2324 // if the region has no type, matches everything
2325 TypeDescriptor tdDst = dst.getType();
2326 if( tdDst == null ) {
2330 // if the type is not a class or an array, don't
2331 // match because primitives are copied, no aliases
2332 ClassDescriptor cdDst = tdDst.getClassDesc();
2333 if( cdDst == null && !tdDst.isArray() ) {
2337 // if the edge type is null, it matches everything
2338 TypeDescriptor tdEdge = edge.getType();
2339 if( tdEdge == null ) {
2343 return typeUtil.isSuperorType(tdEdge, tdDst);
2347 protected void unshadowTokens(AllocSite as, RefEdge edge) {
2348 edge.setBeta(edge.getBeta().unshadowTokens(as) );
2351 protected void unshadowTokens(AllocSite as, HeapRegionNode hrn) {
2352 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
2356 private ReachSet toShadowTokens(ReachGraph ogCallee,
2359 ReachSet rsOut = new ReachSet(rsIn).makeCanonical();
2361 Iterator<AllocSite> allocItr = ogCallee.allocSites.iterator();
2362 while( allocItr.hasNext() ) {
2363 AllocSite as = allocItr.next();
2365 rsOut = rsOut.toShadowTokens(as);
2368 return rsOut.makeCanonical();
2372 private void rewriteCallerReachability(Integer paramIndex,
2376 Hashtable<ReachTuple, ReachSet> tokens2states,
2377 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_p,
2378 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_s,
2379 Hashtable<Integer, ReachSet> paramIndex2rewriteD,
2380 ReachGraph ogCallee,
2381 boolean makeChangeSet,
2382 Hashtable<RefEdge, ChangeSet> edgePlannedChanges) {
2384 assert(hrn == null && edge != null) ||
2385 (hrn != null && edge == null);
2387 assert rules != null;
2388 assert tokens2states != null;
2390 ReachSet callerReachabilityNew = new ReachSet().makeCanonical();
2392 // for initializing structures in this method
2393 ReachState ttsEmpty = new ReachState().makeCanonical();
2395 // use this to construct a change set if required; the idea is to
2396 // map every partially rewritten token tuple set to the set of
2397 // caller-context token tuple sets that were used to generate it
2398 Hashtable<ReachState, HashSet<ReachState> > rewritten2source =
2399 new Hashtable<ReachState, HashSet<ReachState> >();
2400 rewritten2source.put( ttsEmpty, new HashSet<ReachState>() );
2403 Iterator<ReachState> rulesItr = rules.iterator();
2404 while(rulesItr.hasNext()) {
2405 ReachState rule = rulesItr.next();
2407 ReachSet rewrittenRule = new ReachSet(ttsEmpty).makeCanonical();
2409 Iterator<ReachTuple> ruleItr = rule.iterator();
2410 while(ruleItr.hasNext()) {
2411 ReachTuple ttCallee = ruleItr.next();
2413 // compute the possibilities for rewriting this callee token
2414 ReachSet ttCalleeRewrites = null;
2415 boolean callerSourceUsed = false;
2417 if( tokens2states.containsKey( ttCallee ) ) {
2418 callerSourceUsed = true;
2419 ttCalleeRewrites = tokens2states.get( ttCallee );
2420 assert ttCalleeRewrites != null;
2422 } else if( ogCallee.paramTokenPrimary2paramIndex.containsKey( ttCallee ) ) {
2424 Integer paramIndex_j = ogCallee.paramTokenPrimary2paramIndex.get( ttCallee );
2425 assert paramIndex_j != null;
2426 ttCalleeRewrites = paramIndex2rewrite_d_p.get( paramIndex_j );
2427 assert ttCalleeRewrites != null;
2429 } else if( ogCallee.paramTokenSecondary2paramIndex.containsKey( ttCallee ) ) {
2431 Integer paramIndex_j = ogCallee.paramTokenSecondary2paramIndex.get( ttCallee );
2432 assert paramIndex_j != null;
2433 ttCalleeRewrites = paramIndex2rewrite_d_s.get( paramIndex_j );
2434 assert ttCalleeRewrites != null;
2436 } else if( ogCallee.paramTokenSecondaryPlus2paramIndex.containsKey( ttCallee ) ) {
2438 Integer paramIndex_j = ogCallee.paramTokenSecondaryPlus2paramIndex.get( ttCallee );
2439 assert paramIndex_j != null;
2440 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
2441 assert ttCalleeRewrites != null;
2443 } else if( ogCallee.paramTokenSecondaryStar2paramIndex.containsKey( ttCallee ) ) {
2445 Integer paramIndex_j = ogCallee.paramTokenSecondaryStar2paramIndex.get( ttCallee );
2446 assert paramIndex_j != null;
2447 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
2448 assert ttCalleeRewrites != null;
2451 // otherwise there's no need for a rewrite, just pass this one on
2452 ReachState ttsCaller = new ReachState( ttCallee ).makeCanonical();
2453 ttCalleeRewrites = new ReachSet( ttsCaller ).makeCanonical();
2456 // branch every version of the working rewritten rule with
2457 // the possibilities for rewriting the current callee token
2458 ReachSet rewrittenRuleWithTTCallee = new ReachSet().makeCanonical();
2460 Iterator<ReachState> rewrittenRuleItr = rewrittenRule.iterator();
2461 while( rewrittenRuleItr.hasNext() ) {
2462 ReachState ttsRewritten = rewrittenRuleItr.next();
2464 Iterator<ReachState> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
2465 while( ttCalleeRewritesItr.hasNext() ) {
2466 ReachState ttsBranch = ttCalleeRewritesItr.next();
2468 ReachState ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
2470 if( makeChangeSet ) {
2471 // in order to keep the list of source token tuple sets
2472 // start with the sets used to make the partially rewritten
2473 // rule up to this point
2474 HashSet<ReachState> sourceSets = rewritten2source.get( ttsRewritten );
2475 assert sourceSets != null;
2477 // make a shallow copy for possible modification
2478 sourceSets = (HashSet<ReachState>) sourceSets.clone();
2480 // if we used something from the caller to rewrite it, remember
2481 if( callerSourceUsed ) {
2482 sourceSets.add( ttsBranch );
2485 // set mapping for the further rewritten rule
2486 rewritten2source.put( ttsRewrittenNext, sourceSets );
2489 rewrittenRuleWithTTCallee =
2490 rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
2494 // now the rewritten rule's possibilities have been extended by
2495 // rewriting the current callee token, remember result
2496 rewrittenRule = rewrittenRuleWithTTCallee;
2499 // the rule has been entirely rewritten into the caller context
2500 // now, so add it to the new reachability information
2501 callerReachabilityNew =
2502 callerReachabilityNew.union( rewrittenRule );
2505 if( makeChangeSet ) {
2506 ChangeSet callerChangeSet = new ChangeSet().makeCanonical();
2508 // each possibility for the final reachability should have a set of
2509 // caller sources mapped to it, use to create the change set
2510 Iterator<ReachState> callerReachabilityItr = callerReachabilityNew.iterator();
2511 while( callerReachabilityItr.hasNext() ) {
2512 ReachState ttsRewrittenFinal = callerReachabilityItr.next();
2513 HashSet<ReachState> sourceSets = rewritten2source.get( ttsRewrittenFinal );
2514 assert sourceSets != null;
2516 Iterator<ReachState> sourceSetsItr = sourceSets.iterator();
2517 while( sourceSetsItr.hasNext() ) {
2518 ReachState ttsSource = sourceSetsItr.next();
2521 callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
2525 assert edgePlannedChanges != null;
2526 edgePlannedChanges.put( edge, callerChangeSet );
2530 edge.setBetaNew( edge.getBetaNew().union( callerReachabilityNew ) );
2532 hrn.setAlphaNew( hrn.getAlphaNew().union( callerReachabilityNew ) );
2538 private HashSet<HeapRegionNode>
2539 getHRNSetThatPossiblyMapToCalleeHRN( ReachGraph ogCallee,
2540 HeapRegionNode hrnCallee,
2541 Hashtable<Integer, Set<HeapRegionNode> > pi2dr,
2542 Hashtable<Integer, Set<HeapRegionNode> > pi2r
2545 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
2547 Set<Integer> paramIndicesCallee_p = ogCallee.idPrimary2paramIndexSet .get( hrnCallee.getID() );
2548 Set<Integer> paramIndicesCallee_s = ogCallee.idSecondary2paramIndexSet.get( hrnCallee.getID() );
2550 if( paramIndicesCallee_p == null &&
2551 paramIndicesCallee_s == null ) {
2552 // this is a node allocated in the callee and it has
2553 // exactly one shadow node in the caller to map to
2554 AllocSite as = hrnCallee.getAllocSite();
2557 int age = as.getAgeCategory( hrnCallee.getID() );
2558 assert age != AllocSite.AGE_notInThisSite;
2561 if( age == AllocSite.AGE_summary ) {
2562 idCaller = as.getSummaryShadow();
2564 } else if( age == AllocSite.AGE_oldest ) {
2565 idCaller = as.getOldestShadow();
2568 assert age == AllocSite.AGE_in_I;
2570 Integer I = as.getAge( hrnCallee.getID() );
2573 idCaller = as.getIthOldestShadow( I );
2576 assert id2hrn.containsKey( idCaller );
2577 possibleCallerHRNs.add( id2hrn.get( idCaller ) );
2579 return possibleCallerHRNs;
2582 // find out what primary objects this might be
2583 if( paramIndicesCallee_p != null ) {
2584 // this is a node that was created to represent a parameter
2585 // so it maps to some regions directly reachable from the arg labels
2586 Iterator<Integer> itrIndex = paramIndicesCallee_p.iterator();
2587 while( itrIndex.hasNext() ) {
2588 Integer paramIndexCallee = itrIndex.next();
2589 assert pi2dr.containsKey( paramIndexCallee );
2590 possibleCallerHRNs.addAll( pi2dr.get( paramIndexCallee ) );
2594 // find out what secondary objects this might be
2595 if( paramIndicesCallee_s != null ) {
2596 // this is a node that was created to represent objs reachable from
2597 // some parameter, so it maps to regions reachable from the arg labels
2598 Iterator<Integer> itrIndex = paramIndicesCallee_s.iterator();
2599 while( itrIndex.hasNext() ) {
2600 Integer paramIndexCallee = itrIndex.next();
2601 assert pi2r.containsKey( paramIndexCallee );
2602 possibleCallerHRNs.addAll( pi2r.get( paramIndexCallee ) );
2606 // TODO: is this true?
2607 // one of the two cases above should have put something in here
2608 //assert !possibleCallerHRNs.isEmpty();
2610 return possibleCallerHRNs;
2615 ////////////////////////////////////////////////////
2617 // This global sweep is an optional step to prune
2618 // reachability sets that are not internally
2619 // consistent with the global graph. It should be
2620 // invoked after strong updates or method calls.
2622 ////////////////////////////////////////////////////
2623 public void globalSweep() {
2625 // boldB is part of the phase 1 sweep
2626 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
2627 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2629 // visit every heap region to initialize alphaNew and calculate boldB
2630 Set hrns = id2hrn.entrySet();
2631 Iterator itrHrns = hrns.iterator();
2632 while( itrHrns.hasNext() ) {
2633 Map.Entry me = (Map.Entry)itrHrns.next();
2634 Integer token = (Integer) me.getKey();
2635 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2637 // assert that this node and incoming edges have clean alphaNew
2638 // and betaNew sets, respectively
2639 assert rstateEmpty.equals( hrn.getAlphaNew() );
2641 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2642 while( itrRers.hasNext() ) {
2643 RefEdge edge = itrRers.next();
2644 assert rstateEmpty.equals( edge.getBetaNew() );
2647 // calculate boldB for this flagged node
2648 if( hrn.isFlagged() ) {
2650 Hashtable<RefEdge, ReachSet> boldB_f =
2651 new Hashtable<RefEdge, ReachSet>();
2653 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2655 // initial boldB_f constraints
2656 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2657 while( itrRees.hasNext() ) {
2658 RefEdge edge = itrRees.next();
2660 assert !boldB.containsKey( edge );
2661 boldB_f.put( edge, edge.getBeta() );
2663 assert !workSetEdges.contains( edge );
2664 workSetEdges.add( edge );
2667 // enforce the boldB_f constraint at edges until we reach a fixed point
2668 while( !workSetEdges.isEmpty() ) {
2669 RefEdge edge = workSetEdges.iterator().next();
2670 workSetEdges.remove( edge );
2672 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2673 while( itrPrime.hasNext() ) {
2674 RefEdge edgePrime = itrPrime.next();
2676 ReachSet prevResult = boldB_f.get( edgePrime );
2677 ReachSet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
2679 if( prevResult == null ||
2680 prevResult.union( intersection ).size() > prevResult.size() ) {
2682 if( prevResult == null ) {
2683 boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) );
2685 boldB_f.put( edgePrime, prevResult .union( intersection ) );
2687 workSetEdges.add( edgePrime );
2692 boldB.put( token, boldB_f );
2697 // use boldB to prune tokens from alpha states that are impossible
2698 // and propagate the differences backwards across edges
2699 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2701 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2702 new Hashtable<RefEdge, ChangeSet>();
2704 hrns = id2hrn.entrySet();
2705 itrHrns = hrns.iterator();
2706 while( itrHrns.hasNext() ) {
2707 Map.Entry me = (Map.Entry)itrHrns.next();
2708 Integer token = (Integer) me.getKey();
2709 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2711 // never remove the identity token from a flagged region
2712 // because it is trivially satisfied
2713 ReachTuple ttException = new ReachTuple( token,
2714 !hrn.isSingleObject(),
2715 ReachTuple.ARITY_ONE ).makeCanonical();
2717 ChangeSet cts = new ChangeSet().makeCanonical();
2719 // mark tokens for removal
2720 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2721 while( stateItr.hasNext() ) {
2722 ReachState ttsOld = stateItr.next();
2724 ReachState markedTokens = new ReachState().makeCanonical();
2726 Iterator<ReachTuple> ttItr = ttsOld.iterator();
2727 while( ttItr.hasNext() ) {
2728 ReachTuple ttOld = ttItr.next();
2730 // never remove the identity token from a flagged region
2731 // because it is trivially satisfied
2732 if( hrn.isFlagged() ) {
2733 if( ttOld == ttException ) {
2738 // does boldB_ttOld allow this token?
2739 boolean foundState = false;
2740 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2741 while( incidentEdgeItr.hasNext() ) {
2742 RefEdge incidentEdge = incidentEdgeItr.next();
2744 // if it isn't allowed, mark for removal
2745 Integer idOld = ttOld.getToken();
2746 assert id2hrn.containsKey( idOld );
2747 Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
2748 ReachSet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL!
2749 if( boldB_ttOld_incident != null &&
2750 boldB_ttOld_incident.contains( ttsOld ) ) {
2756 markedTokens = markedTokens.add( ttOld );
2760 // if there is nothing marked, just move on
2761 if( markedTokens.isEmpty() ) {
2762 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
2766 // remove all marked tokens and establish a change set that should
2767 // propagate backwards over edges from this node
2768 ReachState ttsPruned = new ReachState().makeCanonical();
2769 ttItr = ttsOld.iterator();
2770 while( ttItr.hasNext() ) {
2771 ReachTuple ttOld = ttItr.next();
2773 if( !markedTokens.containsTuple( ttOld ) ) {
2774 ttsPruned = ttsPruned.union( ttOld );
2777 assert !ttsOld.equals( ttsPruned );
2779 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
2780 ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
2781 cts = cts.union( ct );
2784 // throw change tuple set on all incident edges
2785 if( !cts.isEmpty() ) {
2786 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2787 while( incidentEdgeItr.hasNext() ) {
2788 RefEdge incidentEdge = incidentEdgeItr.next();
2790 edgesForPropagation.add( incidentEdge );
2792 if( edgePlannedChanges.get( incidentEdge ) == null ) {
2793 edgePlannedChanges.put( incidentEdge, cts );
2795 edgePlannedChanges.put(
2797 edgePlannedChanges.get( incidentEdge ).union( cts )
2804 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2806 propagateTokensOverEdges( edgesForPropagation,
2810 // at the end of the 1st phase reference edges have
2811 // beta, betaNew that correspond to beta and betaR
2813 // commit beta<-betaNew, so beta=betaR and betaNew
2814 // will represent the beta' calculation in 2nd phase
2816 // commit alpha<-alphaNew because it won't change
2817 HashSet<RefEdge> res = new HashSet<RefEdge>();
2819 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2820 while( nodeItr.hasNext() ) {
2821 HeapRegionNode hrn = nodeItr.next();
2822 hrn.applyAlphaNew();
2823 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
2824 while( itrRes.hasNext() ) {
2825 res.add( itrRes.next() );
2831 Iterator<RefEdge> edgeItr = res.iterator();
2832 while( edgeItr.hasNext() ) {
2833 RefEdge edge = edgeItr.next();
2834 HeapRegionNode hrn = edge.getDst();
2836 // commit results of last phase
2837 if( edgesUpdated.contains( edge ) ) {
2838 edge.applyBetaNew();
2841 // compute intial condition of 2nd phase
2842 edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
2845 // every edge in the graph is the initial workset
2846 Set<RefEdge> edgeWorkSet = (Set) res.clone();
2847 while( !edgeWorkSet.isEmpty() ) {
2848 RefEdge edgePrime = edgeWorkSet.iterator().next();
2849 edgeWorkSet.remove( edgePrime );
2851 RefSrcNode on = edgePrime.getSrc();
2852 if( !(on instanceof HeapRegionNode) ) {
2855 HeapRegionNode hrn = (HeapRegionNode) on;
2857 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
2858 while( itrEdge.hasNext() ) {
2859 RefEdge edge = itrEdge.next();
2861 ReachSet prevResult = edge.getBetaNew();
2862 assert prevResult != null;
2864 ReachSet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
2866 if( prevResult.union( intersection ).size() > prevResult.size() ) {
2867 edge.setBetaNew( prevResult.union( intersection ) );
2868 edgeWorkSet.add( edge );
2873 // commit beta' (beta<-betaNew)
2874 edgeItr = res.iterator();
2875 while( edgeItr.hasNext() ) {
2876 edgeItr.next().applyBetaNew();
2882 ////////////////////////////////////////////////////
2883 // in merge() and equals() methods the suffix A
2884 // represents the passed in graph and the suffix
2885 // B refers to the graph in this object
2886 // Merging means to take the incoming graph A and
2887 // merge it into B, so after the operation graph B
2888 // is the final result.
2889 ////////////////////////////////////////////////////
2890 public void merge( ReachGraph rg ) {
2897 mergeRefEdges ( rg );
2898 mergeAllocSites ( rg );
2899 mergeAccessPaths( rg );
2902 protected void mergeNodes( ReachGraph rg ) {
2904 // start with heap region nodes
2905 Set sA = rg.id2hrn.entrySet();
2906 Iterator iA = sA.iterator();
2907 while( iA.hasNext() ) {
2908 Map.Entry meA = (Map.Entry) iA.next();
2909 Integer idA = (Integer) meA.getKey();
2910 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2912 // if this graph doesn't have a node the
2913 // incoming graph has, allocate it
2914 if( !id2hrn.containsKey( idA ) ) {
2915 HeapRegionNode hrnB = hrnA.copy();
2916 id2hrn.put( idA, hrnB );
2919 // otherwise this is a node present in both graphs
2920 // so make the new reachability set a union of the
2921 // nodes' reachability sets
2922 HeapRegionNode hrnB = id2hrn.get( idA );
2923 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
2927 // now add any variable nodes that are in graph B but
2929 sA = rg.td2vn.entrySet();
2931 while( iA.hasNext() ) {
2932 Map.Entry meA = (Map.Entry) iA.next();
2933 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2934 VariableNode lnA = (VariableNode) meA.getValue();
2936 // if the variable doesn't exist in B, allocate and add it
2937 VariableNode lnB = getVariableNodeFromTemp( tdA );
2941 protected void mergeRefEdges( ReachGraph rg ) {
2943 // between heap regions
2944 Set sA = rg.id2hrn.entrySet();
2945 Iterator iA = sA.iterator();
2946 while( iA.hasNext() ) {
2947 Map.Entry meA = (Map.Entry) iA.next();
2948 Integer idA = (Integer) meA.getKey();
2949 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2951 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2952 while( heapRegionsItrA.hasNext() ) {
2953 RefEdge edgeA = heapRegionsItrA.next();
2954 HeapRegionNode hrnChildA = edgeA.getDst();
2955 Integer idChildA = hrnChildA.getID();
2957 // at this point we know an edge in graph A exists
2958 // idA -> idChildA, does this exist in B?
2959 assert id2hrn.containsKey( idA );
2960 HeapRegionNode hrnB = id2hrn.get( idA );
2961 RefEdge edgeToMerge = null;
2963 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2964 while( heapRegionsItrB.hasNext() &&
2965 edgeToMerge == null ) {
2967 RefEdge edgeB = heapRegionsItrB.next();
2968 HeapRegionNode hrnChildB = edgeB.getDst();
2969 Integer idChildB = hrnChildB.getID();
2971 // don't use the RefEdge.equals() here because
2972 // we're talking about existence between graphs,
2973 // not intragraph equal
2974 if( idChildB.equals( idChildA ) &&
2975 edgeB.typeAndFieldEquals( edgeA ) ) {
2977 edgeToMerge = edgeB;
2981 // if the edge from A was not found in B,
2983 if( edgeToMerge == null ) {
2984 assert id2hrn.containsKey( idChildA );
2985 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2986 edgeToMerge = edgeA.copy();
2987 edgeToMerge.setSrc( hrnB );
2988 edgeToMerge.setDst( hrnChildB );
2989 addRefEdge( hrnB, hrnChildB, edgeToMerge );
2991 // otherwise, the edge already existed in both graphs
2992 // so merge their reachability sets
2994 // just replace this beta set with the union
2995 assert edgeToMerge != null;
2996 edgeToMerge.setBeta(
2997 edgeToMerge.getBeta().union( edgeA.getBeta() )
2999 if( !edgeA.isInitialParam() ) {
3000 edgeToMerge.setIsInitialParam( false );
3006 // and then again from variable nodes
3007 sA = rg.td2vn.entrySet();
3009 while( iA.hasNext() ) {
3010 Map.Entry meA = (Map.Entry) iA.next();
3011 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3012 VariableNode vnA = (VariableNode) meA.getValue();
3014 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3015 while( heapRegionsItrA.hasNext() ) {
3016 RefEdge edgeA = heapRegionsItrA.next();
3017 HeapRegionNode hrnChildA = edgeA.getDst();
3018 Integer idChildA = hrnChildA.getID();
3020 // at this point we know an edge in graph A exists
3021 // tdA -> idChildA, does this exist in B?
3022 assert td2vn.containsKey( tdA );
3023 VariableNode vnB = td2vn.get( tdA );
3024 RefEdge edgeToMerge = null;
3026 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3027 while( heapRegionsItrB.hasNext() &&
3028 edgeToMerge == null ) {
3030 RefEdge edgeB = heapRegionsItrB.next();
3031 HeapRegionNode hrnChildB = edgeB.getDst();
3032 Integer idChildB = hrnChildB.getID();
3034 // don't use the RefEdge.equals() here because
3035 // we're talking about existence between graphs
3036 if( idChildB.equals( idChildA ) &&
3037 edgeB.typeAndFieldEquals( edgeA ) ) {
3039 edgeToMerge = edgeB;
3043 // if the edge from A was not found in B,
3045 if( edgeToMerge == null ) {
3046 assert id2hrn.containsKey( idChildA );
3047 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3048 edgeToMerge = edgeA.copy();
3049 edgeToMerge.setSrc( vnB );
3050 edgeToMerge.setDst( hrnChildB );
3051 addRefEdge( vnB, hrnChildB, edgeToMerge );
3053 // otherwise, the edge already existed in both graphs
3054 // so merge their reachability sets
3056 // just replace this beta set with the union
3057 edgeToMerge.setBeta(
3058 edgeToMerge.getBeta().union( edgeA.getBeta() )
3060 if( !edgeA.isInitialParam() ) {
3061 edgeToMerge.setIsInitialParam( false );
3068 protected void mergeAllocSites( ReachGraph rg ) {
3069 allocSites.addAll( rg.allocSites );
3072 protected void mergeAccessPaths( ReachGraph rg ) {
3073 UtilAlgorithms.mergeHashtablesWithHashSetValues( temp2accessPaths,
3074 rg.temp2accessPaths );
3078 // it is necessary in the equals() member functions
3079 // to "check both ways" when comparing the data
3080 // structures of two graphs. For instance, if all
3081 // edges between heap region nodes in graph A are
3082 // present and equal in graph B it is not sufficient
3083 // to say the graphs are equal. Consider that there
3084 // may be edges in graph B that are not in graph A.
3085 // the only way to know that all edges in both graphs
3086 // are equally present is to iterate over both data
3087 // structures and compare against the other graph.
3088 public boolean equals( ReachGraph rg ) {
3094 if( !areHeapRegionNodesEqual( rg ) ) {
3098 if( !areVariableNodesEqual( rg ) ) {
3102 if( !areRefEdgesEqual( rg ) ) {
3106 if( !areAccessPathsEqual( rg ) ) {
3110 // if everything is equal up to this point,
3111 // assert that allocSites is also equal--
3112 // this data is redundant but kept for efficiency
3113 assert allocSites.equals( rg.allocSites );
3119 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3121 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3125 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3132 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3134 Set sA = rgA.id2hrn.entrySet();
3135 Iterator iA = sA.iterator();
3136 while( iA.hasNext() ) {
3137 Map.Entry meA = (Map.Entry) iA.next();
3138 Integer idA = (Integer) meA.getKey();
3139 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3141 if( !rgB.id2hrn.containsKey( idA ) ) {
3145 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3146 if( !hrnA.equalsIncludingAlpha( hrnB ) ) {
3155 protected boolean areVariableNodesEqual( ReachGraph rg ) {
3157 if( !areallVNinAalsoinBandequal( this, rg ) ) {
3161 if( !areallVNinAalsoinBandequal( rg, this ) ) {
3168 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3170 Set sA = rgA.td2vn.entrySet();
3171 Iterator iA = sA.iterator();
3172 while( iA.hasNext() ) {
3173 Map.Entry meA = (Map.Entry) iA.next();
3174 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3176 if( !rgB.td2vn.containsKey( tdA ) ) {
3185 protected boolean areRefEdgesEqual( ReachGraph rg ) {
3186 if( !areallREinAandBequal( this, rg ) ) {
3193 static protected boolean areallREinAandBequal( ReachGraph rgA,
3196 // check all the heap region->heap region edges
3197 Set sA = rgA.id2hrn.entrySet();
3198 Iterator iA = sA.iterator();
3199 while( iA.hasNext() ) {
3200 Map.Entry meA = (Map.Entry) iA.next();
3201 Integer idA = (Integer) meA.getKey();
3202 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3204 // we should have already checked that the same
3205 // heap regions exist in both graphs
3206 assert rgB.id2hrn.containsKey( idA );
3208 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3212 // then check every edge in B for presence in A, starting
3213 // from the same parent HeapRegionNode
3214 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3216 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3221 // then check all the variable->heap region edges
3222 sA = rgA.td2vn.entrySet();
3224 while( iA.hasNext() ) {
3225 Map.Entry meA = (Map.Entry) iA.next();
3226 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3227 VariableNode vnA = (VariableNode) meA.getValue();
3229 // we should have already checked that the same
3230 // label nodes exist in both graphs
3231 assert rgB.td2vn.containsKey( tdA );
3233 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3237 // then check every edge in B for presence in A, starting
3238 // from the same parent VariableNode
3239 VariableNode vnB = rgB.td2vn.get( tdA );
3241 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3250 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3254 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3255 while( itrA.hasNext() ) {
3256 RefEdge edgeA = itrA.next();
3257 HeapRegionNode hrnChildA = edgeA.getDst();
3258 Integer idChildA = hrnChildA.getID();
3260 assert rgB.id2hrn.containsKey( idChildA );
3262 // at this point we know an edge in graph A exists
3263 // rnA -> idChildA, does this exact edge exist in B?
3264 boolean edgeFound = false;
3266 RefSrcNode rnB = null;
3267 if( rnA instanceof HeapRegionNode ) {
3268 HeapRegionNode hrnA = (HeapRegionNode) rnA;
3269 rnB = rgB.id2hrn.get( hrnA.getID() );
3271 VariableNode vnA = (VariableNode) rnA;
3272 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3275 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3276 while( itrB.hasNext() ) {
3277 RefEdge edgeB = itrB.next();
3278 HeapRegionNode hrnChildB = edgeB.getDst();
3279 Integer idChildB = hrnChildB.getID();
3281 if( idChildA.equals( idChildB ) &&
3282 edgeA.typeAndFieldEquals( edgeB ) ) {
3284 // there is an edge in the right place with the right field,
3285 // but do they have the same attributes?
3286 if( edgeA.getBeta().equals( edgeB.getBeta() ) ) {
3301 protected boolean areAccessPathsEqual( ReachGraph rg ) {
3302 return temp2accessPaths.equals( rg.temp2accessPaths );
3307 public Set<HeapRegionNode> findCommonReachableNodes( HeapRegionNode hrn1,
3308 HeapRegionNode hrn2 ) {
3310 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
3311 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
3313 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
3314 todoNodes1.add( hrn1 );
3316 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
3317 todoNodes2.add( hrn2 );
3319 // follow links until all reachable nodes have been found
3320 while( !todoNodes1.isEmpty() ) {
3321 HeapRegionNode hrn = todoNodes1.iterator().next();
3322 todoNodes1.remove( hrn );
3323 reachableNodes1.add(hrn);
3325 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
3326 while( edgeItr.hasNext() ) {
3327 RefEdge edge = edgeItr.next();
3329 if( !reachableNodes1.contains( edge.getDst() ) ) {
3330 todoNodes1.add( edge.getDst() );
3335 while( !todoNodes2.isEmpty() ) {
3336 HeapRegionNode hrn = todoNodes2.iterator().next();
3337 todoNodes2.remove( hrn );
3338 reachableNodes2.add(hrn);
3340 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
3341 while( edgeItr.hasNext() ) {
3342 RefEdge edge = edgeItr.next();
3344 if( !reachableNodes2.contains( edge.getDst() ) ) {
3345 todoNodes2.add( edge.getDst() );
3350 Set<HeapRegionNode> intersection =
3351 new HashSet<HeapRegionNode>( reachableNodes1 );
3353 intersection.retainAll( reachableNodes2 );
3355 return intersection;
3360 public void writeGraph( String graphName,
3361 boolean writeLabels,
3362 boolean labelSelect,
3363 boolean pruneGarbage,
3364 boolean writeReferencers,
3365 boolean hideSubsetReachability,
3366 boolean hideEdgeTaints
3367 ) throws java.io.IOException {
3369 // remove all non-word characters from the graph name so
3370 // the filename and identifier in dot don't cause errors
3371 graphName = graphName.replaceAll( "[\\W]", "" );
3374 new BufferedWriter( new FileWriter( graphName+".dot" ) );
3376 bw.write( "digraph "+graphName+" {\n" );
3378 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3380 // then visit every heap region node
3381 Set s = id2hrn.entrySet();
3382 Iterator i = s.iterator();
3383 while( i.hasNext() ) {
3384 Map.Entry me = (Map.Entry) i.next();
3385 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3387 if( !pruneGarbage ||
3388 (hrn.isFlagged() && hrn.getID() > 0) ||
3389 hrn.getDescription().startsWith( "param" )
3392 if( !visited.contains( hrn ) ) {
3393 traverseHeapRegionNodes( hrn,
3398 hideSubsetReachability,
3404 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
3407 // then visit every label node, useful for debugging
3409 s = td2vn.entrySet();
3411 while( i.hasNext() ) {
3412 Map.Entry me = (Map.Entry) i.next();
3413 VariableNode vn = (VariableNode) me.getValue();
3416 String labelStr = vn.getTempDescriptorString();
3417 if( labelStr.startsWith("___temp") ||
3418 labelStr.startsWith("___dst") ||
3419 labelStr.startsWith("___srctmp") ||
3420 labelStr.startsWith("___neverused")
3426 //bw.write(" "+vn.toString() + ";\n");
3428 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3429 while( heapRegionsItr.hasNext() ) {
3430 RefEdge edge = heapRegionsItr.next();
3431 HeapRegionNode hrn = edge.getDst();
3433 if( pruneGarbage && !visited.contains( hrn ) ) {
3434 traverseHeapRegionNodes( hrn,
3439 hideSubsetReachability,
3443 bw.write( " " + vn.toString() +
3444 " -> " + hrn.toString() +
3445 "[label=\"" + edge.toGraphEdgeString( hideSubsetReachability ) +
3446 "\",decorate];\n" );
3455 protected void traverseHeapRegionNodes( HeapRegionNode hrn,
3458 Set<HeapRegionNode> visited,
3459 boolean writeReferencers,
3460 boolean hideSubsetReachability,
3461 boolean hideEdgeTaints
3462 ) throws java.io.IOException {
3464 if( visited.contains( hrn ) ) {
3469 String attributes = "[";
3471 if( hrn.isSingleObject() ) {
3472 attributes += "shape=box";
3474 attributes += "shape=Msquare";
3477 if( hrn.isFlagged() ) {
3478 attributes += ",style=filled,fillcolor=lightgrey";
3481 attributes += ",label=\"ID" +
3485 if( hrn.getType() != null ) {
3486 attributes += hrn.getType().toPrettyString() + "\\n";
3489 attributes += hrn.getDescription() +
3491 hrn.getAlphaString( hideSubsetReachability ) +
3494 bw.write( " "+hrn.toString()+attributes+";\n" );
3497 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3498 while( childRegionsItr.hasNext() ) {
3499 RefEdge edge = childRegionsItr.next();
3500 HeapRegionNode hrnChild = edge.getDst();
3502 bw.write( " " +hrn.toString()+
3503 " -> " +hrnChild.toString()+
3504 "[label=\""+edge.toGraphEdgeString( hideSubsetReachability )+
3507 traverseHeapRegionNodes( hrnChild,
3512 hideSubsetReachability,
3518 // in this analysis specifically:
3519 // we have a notion that a null type is the "match any" type,
3520 // so wrap calls to the utility methods that deal with null
3521 public TypeDescriptor mostSpecificType( TypeDescriptor td1,
3522 TypeDescriptor td2 ) {
3529 if( td1.isNull() ) {
3532 if( td2.isNull() ) {
3535 return typeUtil.mostSpecific( td1, td2 );
3538 public TypeDescriptor mostSpecificType( TypeDescriptor td1,
3540 TypeDescriptor td3 ) {
3542 return mostSpecificType( td1,
3543 mostSpecificType( td2, td3 )
3547 public TypeDescriptor mostSpecificType( TypeDescriptor td1,
3550 TypeDescriptor td4 ) {
3552 return mostSpecificType( mostSpecificType( td1, td2 ),
3553 mostSpecificType( td3, td4 )
3557 // remember, in this analysis a null type means "any type"
3558 public boolean isSuperiorType( TypeDescriptor possibleSuper,
3559 TypeDescriptor possibleChild ) {
3560 if( possibleSuper == null ||
3561 possibleChild == null ) {
3565 if( possibleSuper.isNull() ||
3566 possibleChild.isNull() ) {
3570 return typeUtil.isSuperorType( possibleSuper, possibleChild );
3574 public String generateUniqueIdentifier(FlatMethod fm, int paramIdx, String type){
3576 //type: A->aliapsed parameter heap region
3577 // P -> primary paramter heap region
3578 // S -> secondary paramter heap region
3581 if(type.equals("A")){
3583 identifier="FM"+fm.hashCode()+".A";
3585 identifier="FM"+fm.hashCode()+"."+paramIdx+"."+type;
3591 public String generateUniqueIdentifier(AllocSite as, int age, boolean isSummary){
3595 FlatNew fn=as.getFlatNew();
3598 identifier="FN"+fn.hashCode()+".S";
3600 identifier="FN"+fn.hashCode()+"."+age;