1 package Analysis.Disjoint;
5 import Util.UtilAlgorithms;
9 public class ReachGraph {
11 // use to disable improvements for comparison
12 protected static final boolean DISABLE_STRONG_UPDATES = false;
13 protected static final boolean DISABLE_GLOBAL_SWEEP = false;
15 // a special out-of-scope temp
16 protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
18 // predicate constants
19 public static final ExistPred predTrue = ExistPred.factory(); // if no args, true
20 public static final ExistPredSet predsEmpty = ExistPredSet.factory();
21 public static final ExistPredSet predsTrue = ExistPredSet.factory( predTrue );
23 // some frequently used reachability constants
24 protected static final ReachState rstateEmpty = ReachState.factory();
25 protected static final ReachSet rsetEmpty = ReachSet.factory();
26 protected static final ReachSet rsetWithEmptyState = Canonical.changePredsTo( ReachSet.factory( rstateEmpty ),
29 // from DisjointAnalysis for convenience
30 protected static int allocationDepth = -1;
31 protected static TypeUtil typeUtil = null;
34 // variable and heap region nodes indexed by unique ID
35 public Hashtable<Integer, HeapRegionNode> id2hrn;
36 public Hashtable<TempDescriptor, VariableNode > td2vn;
38 // convenient set of alloc sites for all heap regions
39 // present in the graph without having to search
40 public HashSet<AllocSite> allocSites;
42 // set of accessible variables for current program statement
43 // if not contains, it is an inaccessible variable
44 public HashSet<TempDescriptor> accessibleVars;
47 id2hrn = new Hashtable<Integer, HeapRegionNode>();
48 td2vn = new Hashtable<TempDescriptor, VariableNode >();
49 allocSites = new HashSet<AllocSite>();
50 accessibleVars = new HashSet<TempDescriptor>();
54 // temp descriptors are globally unique and map to
55 // exactly one variable node, easy
56 protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
59 if( !td2vn.containsKey( td ) ) {
60 td2vn.put( td, new VariableNode( td ) );
63 return td2vn.get( td );
66 public boolean hasVariable( TempDescriptor td ) {
67 return td2vn.containsKey( td );
71 // this suite of methods can be used to assert a
72 // very important property of ReachGraph objects:
73 // some element, HeapRegionNode, RefEdge etc.
74 // should be referenced by at most ONE ReachGraph!!
75 // If a heap region or edge or variable should be
76 // in another graph, make a new object with
77 // equivalent properties for a new graph
78 public boolean belongsToThis( RefSrcNode rsn ) {
79 if( rsn instanceof VariableNode ) {
80 VariableNode vn = (VariableNode) rsn;
81 return this.td2vn.get( vn.getTempDescriptor() ) == vn;
83 HeapRegionNode hrn = (HeapRegionNode) rsn;
84 return this.id2hrn.get( hrn.getID() ) == hrn;
91 // the reason for this method is to have the option
92 // of creating new heap regions with specific IDs, or
93 // duplicating heap regions with specific IDs (especially
94 // in the merge() operation) or to create new heap
95 // regions with a new unique ID
96 protected HeapRegionNode
97 createNewHeapRegionNode( Integer id,
98 boolean isSingleObject,
100 boolean isOutOfContext,
109 TypeDescriptor typeToUse = null;
110 if( allocSite != null ) {
111 typeToUse = allocSite.getType();
112 allocSites.add( allocSite );
117 boolean markForAnalysis = false;
118 if( allocSite != null && allocSite.isFlagged() ) {
119 markForAnalysis = true;
122 if( allocSite == null ) {
123 assert !markForAnalysis;
125 } else if( markForAnalysis != allocSite.isFlagged() ) {
131 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
134 if( inherent == null ) {
135 if( markForAnalysis ) {
137 Canonical.changePredsTo(
140 ReachTuple.factory( id,
142 ReachTuple.ARITY_ONE,
143 false // out-of-context
150 inherent = rsetWithEmptyState;
154 if( alpha == null ) {
158 assert preds != null;
160 HeapRegionNode hrn = new HeapRegionNode( id,
171 id2hrn.put( id, hrn );
177 ////////////////////////////////////////////////
179 // Low-level referencee and referencer methods
181 // These methods provide the lowest level for
182 // creating references between reachability nodes
183 // and handling the details of maintaining both
184 // list of referencers and referencees.
186 ////////////////////////////////////////////////
187 protected void addRefEdge( RefSrcNode referencer,
188 HeapRegionNode referencee,
190 assert referencer != null;
191 assert referencee != null;
193 assert edge.getSrc() == referencer;
194 assert edge.getDst() == referencee;
195 assert belongsToThis( referencer );
196 assert belongsToThis( referencee );
198 // edges are getting added twice to graphs now, the
199 // kind that should have abstract facts merged--use
200 // this check to prevent that
201 assert referencer.getReferenceTo( referencee,
206 referencer.addReferencee( edge );
207 referencee.addReferencer( edge );
210 protected void removeRefEdge( RefEdge e ) {
211 removeRefEdge( e.getSrc(),
217 protected void removeRefEdge( RefSrcNode referencer,
218 HeapRegionNode referencee,
221 assert referencer != null;
222 assert referencee != null;
224 RefEdge edge = referencer.getReferenceTo( referencee,
228 assert edge == referencee.getReferenceFrom( referencer,
232 referencer.removeReferencee( edge );
233 referencee.removeReferencer( edge );
237 // int oldTaint=edge.getTaintIdentifier();
238 // if(referencer instanceof HeapRegionNode){
239 // depropagateTaintIdentifier((HeapRegionNode)referencer,oldTaint,new HashSet<HeapRegionNode>());
245 // return whether at least one edge was removed
246 protected boolean clearRefEdgesFrom( RefSrcNode referencer,
249 boolean removeAll ) {
250 assert referencer != null;
252 boolean atLeastOneEdgeRemoved = false;
254 // get a copy of the set to iterate over, otherwise
255 // we will be trying to take apart the set as we
256 // are iterating over it, which won't work
257 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
258 while( i.hasNext() ) {
259 RefEdge edge = i.next();
262 (edge.typeEquals( type ) && edge.fieldEquals( field ))
265 HeapRegionNode referencee = edge.getDst();
267 removeRefEdge( referencer,
272 atLeastOneEdgeRemoved = true;
276 return atLeastOneEdgeRemoved;
279 protected void clearRefEdgesTo( HeapRegionNode referencee,
282 boolean removeAll ) {
283 assert referencee != null;
285 // get a copy of the set to iterate over, otherwise
286 // we will be trying to take apart the set as we
287 // are iterating over it, which won't work
288 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
289 while( i.hasNext() ) {
290 RefEdge edge = i.next();
293 (edge.typeEquals( type ) && edge.fieldEquals( field ))
296 RefSrcNode referencer = edge.getSrc();
298 removeRefEdge( referencer,
306 protected void clearNonVarRefEdgesTo( HeapRegionNode referencee ) {
307 assert referencee != null;
309 // get a copy of the set to iterate over, otherwise
310 // we will be trying to take apart the set as we
311 // are iterating over it, which won't work
312 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
313 while( i.hasNext() ) {
314 RefEdge edge = i.next();
315 RefSrcNode referencer = edge.getSrc();
316 if( !(referencer instanceof VariableNode) ) {
317 removeRefEdge( referencer,
325 // this is a common operation in many transfer functions: we want
326 // to add an edge, but if there is already such an edge we should
327 // merge the properties of the existing and the new edges
328 protected void addEdgeOrMergeWithExisting( RefEdge edgeNew ) {
330 RefSrcNode src = edgeNew.getSrc();
331 assert belongsToThis( src );
333 HeapRegionNode dst = edgeNew.getDst();
334 assert belongsToThis( dst );
336 // look to see if an edge with same field exists
337 // and merge with it, otherwise just add the edge
338 RefEdge edgeExisting = src.getReferenceTo( dst,
343 if( edgeExisting != null ) {
344 edgeExisting.setBeta(
345 Canonical.unionORpreds( edgeExisting.getBeta(),
349 edgeExisting.setPreds(
350 Canonical.join( edgeExisting.getPreds(),
354 edgeExisting.setTaints(
355 Canonical.unionORpreds( edgeExisting.getTaints(),
361 addRefEdge( src, dst, edgeNew );
367 ////////////////////////////////////////////////////
369 // Assignment Operation Methods
371 // These methods are high-level operations for
372 // modeling program assignment statements using
373 // the low-level reference create/remove methods
376 ////////////////////////////////////////////////////
378 public void assignTempXEqualToTempY( TempDescriptor x,
380 assignTempXEqualToCastedTempY( x, y, null );
382 // x gets status of y
383 // if it is in region,
384 //if(accessibleVars.contains(y)){
385 // accessibleVars.add(x);
389 public void assignTempXEqualToCastedTempY( TempDescriptor x,
391 TypeDescriptor tdCast ) {
393 VariableNode lnX = getVariableNodeFromTemp( x );
394 VariableNode lnY = getVariableNodeFromTemp( y );
396 clearRefEdgesFrom( lnX, null, null, true );
398 // note it is possible that the types of temps in the
399 // flat node to analyze will reveal that some typed
400 // edges in the reachability graph are impossible
401 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
403 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
404 while( itrYhrn.hasNext() ) {
405 RefEdge edgeY = itrYhrn.next();
406 HeapRegionNode referencee = edgeY.getDst();
407 RefEdge edgeNew = edgeY.copy();
409 if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
410 impossibleEdges.add( edgeY );
414 edgeNew.setSrc( lnX );
416 if( tdCast == null ) {
417 edgeNew.setType( mostSpecificType( y.getType(),
423 edgeNew.setType( mostSpecificType( y.getType(),
425 referencee.getType(),
431 edgeNew.setField( null );
433 addRefEdge( lnX, referencee, edgeNew );
436 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
437 while( itrImp.hasNext() ) {
438 RefEdge edgeImp = itrImp.next();
439 removeRefEdge( edgeImp );
444 public void assignTempXEqualToTempYFieldF( TempDescriptor x,
446 FieldDescriptor f ) {
447 VariableNode lnX = getVariableNodeFromTemp( x );
448 VariableNode lnY = getVariableNodeFromTemp( y );
450 clearRefEdgesFrom( lnX, null, null, true );
452 // note it is possible that the types of temps in the
453 // flat node to analyze will reveal that some typed
454 // edges in the reachability graph are impossible
455 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
457 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
458 while( itrYhrn.hasNext() ) {
459 RefEdge edgeY = itrYhrn.next();
460 HeapRegionNode hrnY = edgeY.getDst();
461 ReachSet betaY = edgeY.getBeta();
463 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
464 while( itrHrnFhrn.hasNext() ) {
465 RefEdge edgeHrn = itrHrnFhrn.next();
466 HeapRegionNode hrnHrn = edgeHrn.getDst();
467 ReachSet betaHrn = edgeHrn.getBeta();
469 // prune edges that are not a matching field
470 if( edgeHrn.getType() != null &&
471 !edgeHrn.getField().equals( f.getSymbol() )
476 // check for impossible edges
477 if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
478 impossibleEdges.add( edgeHrn );
482 TypeDescriptor tdNewEdge =
483 mostSpecificType( edgeHrn.getType(),
487 RefEdge edgeNew = new RefEdge( lnX,
491 Canonical.intersection( betaY, betaHrn ),
496 addEdgeOrMergeWithExisting( edgeNew );
500 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
501 while( itrImp.hasNext() ) {
502 RefEdge edgeImp = itrImp.next();
503 removeRefEdge( edgeImp );
506 // anytime you might remove edges between heap regions
507 // you must global sweep to clean up broken reachability
508 if( !impossibleEdges.isEmpty() ) {
509 if( !DISABLE_GLOBAL_SWEEP ) {
514 // accessible status update
515 // if it is in region,
516 //accessibleVars.add(x);
517 //accessibleVars.add(y);
521 // return whether a strong update was actually effected
522 public boolean assignTempXFieldFEqualToTempY( TempDescriptor x,
526 VariableNode lnX = getVariableNodeFromTemp( x );
527 VariableNode lnY = getVariableNodeFromTemp( y );
529 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
530 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
532 // note it is possible that the types of temps in the
533 // flat node to analyze will reveal that some typed
534 // edges in the reachability graph are impossible
535 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
537 // first look for possible strong updates and remove those edges
538 boolean strongUpdateCond = false;
539 boolean edgeRemovedByStrongUpdate = false;
541 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
542 while( itrXhrn.hasNext() ) {
543 RefEdge edgeX = itrXhrn.next();
544 HeapRegionNode hrnX = edgeX.getDst();
546 // we can do a strong update here if one of two cases holds
548 f != DisjointAnalysis.getArrayField( f.getType() ) &&
549 ( (hrnX.getNumReferencers() == 1) || // case 1
550 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
553 if( !DISABLE_STRONG_UPDATES ) {
554 strongUpdateCond = true;
557 clearRefEdgesFrom( hrnX,
562 edgeRemovedByStrongUpdate = true;
568 // then do all token propagation
569 itrXhrn = lnX.iteratorToReferencees();
570 while( itrXhrn.hasNext() ) {
571 RefEdge edgeX = itrXhrn.next();
572 HeapRegionNode hrnX = edgeX.getDst();
573 ReachSet betaX = edgeX.getBeta();
574 ReachSet R = Canonical.intersection( hrnX.getAlpha(),
578 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
579 while( itrYhrn.hasNext() ) {
580 RefEdge edgeY = itrYhrn.next();
581 HeapRegionNode hrnY = edgeY.getDst();
582 ReachSet O = edgeY.getBeta();
584 // check for impossible edges
585 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
586 impossibleEdges.add( edgeY );
590 // propagate tokens over nodes starting from hrnSrc, and it will
591 // take care of propagating back up edges from any touched nodes
592 ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
593 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
595 // then propagate back just up the edges from hrn
596 ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
597 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
599 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
600 new Hashtable<RefEdge, ChangeSet>();
602 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
603 while( referItr.hasNext() ) {
604 RefEdge edgeUpstream = referItr.next();
605 todoEdges.add( edgeUpstream );
606 edgePlannedChanges.put( edgeUpstream, Cx );
609 propagateTokensOverEdges( todoEdges,
616 // apply the updates to reachability
617 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
618 while( nodeItr.hasNext() ) {
619 nodeItr.next().applyAlphaNew();
622 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
623 while( edgeItr.hasNext() ) {
624 edgeItr.next().applyBetaNew();
628 // then go back through and add the new edges
629 itrXhrn = lnX.iteratorToReferencees();
630 while( itrXhrn.hasNext() ) {
631 RefEdge edgeX = itrXhrn.next();
632 HeapRegionNode hrnX = edgeX.getDst();
634 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
635 while( itrYhrn.hasNext() ) {
636 RefEdge edgeY = itrYhrn.next();
637 HeapRegionNode hrnY = edgeY.getDst();
639 // skip impossible edges here, we already marked them
640 // when computing reachability propagations above
641 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
645 // prepare the new reference edge hrnX.f -> hrnY
646 TypeDescriptor tdNewEdge =
647 mostSpecificType( y.getType(),
657 Canonical.changePredsTo(
658 Canonical.pruneBy( edgeY.getBeta(),
664 Canonical.changePredsTo( edgeY.getTaints(),
668 addEdgeOrMergeWithExisting( edgeNew );
672 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
673 while( itrImp.hasNext() ) {
674 RefEdge edgeImp = itrImp.next();
675 removeRefEdge( edgeImp );
678 // if there was a strong update, make sure to improve
679 // reachability with a global sweep
680 if( edgeRemovedByStrongUpdate || !impossibleEdges.isEmpty() ) {
681 if( !DISABLE_GLOBAL_SWEEP ) {
687 // after x.y=f , stall x and y if they are not accessible
688 // also contribute write effects on stall site of x
689 // accessible status update
690 // if it is in region
691 //accessibleVars.add(x);
692 //accessibleVars.add(y);
694 return edgeRemovedByStrongUpdate;
698 public void assignReturnEqualToTemp( TempDescriptor x ) {
700 VariableNode lnR = getVariableNodeFromTemp( tdReturn );
701 VariableNode lnX = getVariableNodeFromTemp( x );
703 clearRefEdgesFrom( lnR, null, null, true );
705 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
706 while( itrXhrn.hasNext() ) {
707 RefEdge edgeX = itrXhrn.next();
708 HeapRegionNode referencee = edgeX.getDst();
709 RefEdge edgeNew = edgeX.copy();
710 edgeNew.setSrc( lnR );
711 edgeNew.setTaints( Canonical.changePredsTo( edgeNew.getTaints(),
716 addRefEdge( lnR, referencee, edgeNew );
721 public void assignTempEqualToNewAlloc( TempDescriptor x,
728 // after the age operation the newest (or zero-ith oldest)
729 // node associated with the allocation site should have
730 // no references to it as if it were a newly allocated
732 Integer idNewest = as.getIthOldest( 0 );
733 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
734 assert hrnNewest != null;
736 VariableNode lnX = getVariableNodeFromTemp( x );
737 clearRefEdgesFrom( lnX, null, null, true );
739 // make a new reference to allocated node
740 TypeDescriptor type = as.getType();
743 new RefEdge( lnX, // source
747 hrnNewest.getAlpha(), // beta
748 predsTrue, // predicates
749 TaintSet.factory() // taints
752 addRefEdge( lnX, hrnNewest, edgeNew );
754 // after x=new , x is accessible
755 // if (isInRegion()) {
756 //accessibleVars.add(x);
760 // use the allocation site (unique to entire analysis) to
761 // locate the heap region nodes in this reachability graph
762 // that should be aged. The process models the allocation
763 // of new objects and collects all the oldest allocations
764 // in a summary node to allow for a finite analysis
766 // There is an additional property of this method. After
767 // running it on a particular reachability graph (many graphs
768 // may have heap regions related to the same allocation site)
769 // the heap region node objects in this reachability graph will be
770 // allocated. Therefore, after aging a graph for an allocation
771 // site, attempts to retrieve the heap region nodes using the
772 // integer id's contained in the allocation site should always
773 // return non-null heap regions.
774 public void age( AllocSite as ) {
776 // keep track of allocation sites that are represented
777 // in this graph for efficiency with other operations
778 allocSites.add( as );
780 // if there is a k-th oldest node, it merges into
782 Integer idK = as.getOldest();
783 if( id2hrn.containsKey( idK ) ) {
784 HeapRegionNode hrnK = id2hrn.get( idK );
786 // retrieve the summary node, or make it
788 HeapRegionNode hrnSummary = getSummaryNode( as, false );
790 mergeIntoSummary( hrnK, hrnSummary );
793 // move down the line of heap region nodes
794 // clobbering the ith and transferring all references
795 // to and from i-1 to node i.
796 for( int i = allocationDepth - 1; i > 0; --i ) {
798 // only do the transfer if the i-1 node exists
799 Integer idImin1th = as.getIthOldest( i - 1 );
800 if( id2hrn.containsKey( idImin1th ) ) {
801 HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
802 if( hrnImin1.isWiped() ) {
803 // there is no info on this node, just skip
807 // either retrieve or make target of transfer
808 HeapRegionNode hrnI = getIthNode( as, i, false );
810 transferOnto( hrnImin1, hrnI );
815 // as stated above, the newest node should have had its
816 // references moved over to the second oldest, so we wipe newest
817 // in preparation for being the new object to assign something to
818 HeapRegionNode hrn0 = getIthNode( as, 0, false );
819 wipeOut( hrn0, true );
821 // now tokens in reachability sets need to "age" also
822 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
823 while( itrAllVariableNodes.hasNext() ) {
824 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
825 VariableNode ln = (VariableNode) me.getValue();
827 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
828 while( itrEdges.hasNext() ) {
829 ageTuplesFrom( as, itrEdges.next() );
833 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
834 while( itrAllHRNodes.hasNext() ) {
835 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
836 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
838 ageTuplesFrom( as, hrnToAge );
840 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
841 while( itrEdges.hasNext() ) {
842 ageTuplesFrom( as, itrEdges.next() );
847 // after tokens have been aged, reset newest node's reachability
848 // and a brand new node has a "true" predicate
849 hrn0.setAlpha( hrn0.getInherent() );
850 hrn0.setPreds( predsTrue );
854 // either retrieve or create the needed heap region node
855 protected HeapRegionNode getSummaryNode( AllocSite as,
860 idSummary = as.getSummaryShadow();
862 idSummary = as.getSummary();
865 HeapRegionNode hrnSummary = id2hrn.get( idSummary );
867 if( hrnSummary == null ) {
869 String strDesc = as.toStringForDOT()+"\\nsummary";
872 createNewHeapRegionNode( idSummary, // id or null to generate a new one
873 false, // single object?
875 false, // out-of-context?
876 as.getType(), // type
877 as, // allocation site
878 null, // inherent reach
879 null, // current reach
880 predsEmpty, // predicates
881 strDesc // description
888 // either retrieve or create the needed heap region node
889 protected HeapRegionNode getIthNode( AllocSite as,
895 idIth = as.getIthOldestShadow( i );
897 idIth = as.getIthOldest( i );
900 HeapRegionNode hrnIth = id2hrn.get( idIth );
902 if( hrnIth == null ) {
904 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
906 hrnIth = createNewHeapRegionNode( idIth, // id or null to generate a new one
907 true, // single object?
909 false, // out-of-context?
910 as.getType(), // type
911 as, // allocation site
912 null, // inherent reach
913 null, // current reach
914 predsEmpty, // predicates
915 strDesc // description
923 protected void mergeIntoSummary( HeapRegionNode hrn,
924 HeapRegionNode hrnSummary ) {
925 assert hrnSummary.isNewSummary();
927 // assert that these nodes belong to THIS graph
928 assert belongsToThis( hrn );
929 assert belongsToThis( hrnSummary );
931 assert hrn != hrnSummary;
933 // transfer references _from_ hrn over to hrnSummary
934 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
935 while( itrReferencee.hasNext() ) {
936 RefEdge edge = itrReferencee.next();
937 RefEdge edgeMerged = edge.copy();
938 edgeMerged.setSrc( hrnSummary );
940 HeapRegionNode hrnReferencee = edge.getDst();
941 RefEdge edgeSummary =
942 hrnSummary.getReferenceTo( hrnReferencee,
947 if( edgeSummary == null ) {
948 // the merge is trivial, nothing to be done
949 addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
952 // otherwise an edge from the referencer to hrnSummary exists already
953 // and the edge referencer->hrn should be merged with it
955 Canonical.unionORpreds( edgeMerged.getBeta(),
956 edgeSummary.getBeta()
959 edgeSummary.setPreds(
960 Canonical.join( edgeMerged.getPreds(),
961 edgeSummary.getPreds()
967 // next transfer references _to_ hrn over to hrnSummary
968 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
969 while( itrReferencer.hasNext() ) {
970 RefEdge edge = itrReferencer.next();
971 RefEdge edgeMerged = edge.copy();
972 edgeMerged.setDst( hrnSummary );
974 RefSrcNode onReferencer = edge.getSrc();
975 RefEdge edgeSummary =
976 onReferencer.getReferenceTo( hrnSummary,
981 if( edgeSummary == null ) {
982 // the merge is trivial, nothing to be done
983 addRefEdge( onReferencer, hrnSummary, edgeMerged );
986 // otherwise an edge from the referencer to alpha_S exists already
987 // and the edge referencer->alpha_K should be merged with it
989 Canonical.unionORpreds( edgeMerged.getBeta(),
990 edgeSummary.getBeta()
993 edgeSummary.setPreds(
994 Canonical.join( edgeMerged.getPreds(),
995 edgeSummary.getPreds()
1001 // then merge hrn reachability into hrnSummary
1002 hrnSummary.setAlpha(
1003 Canonical.unionORpreds( hrnSummary.getAlpha(),
1008 hrnSummary.setPreds(
1009 Canonical.join( hrnSummary.getPreds(),
1014 // and afterward, this node is gone
1015 wipeOut( hrn, true );
1019 protected void transferOnto( HeapRegionNode hrnA,
1020 HeapRegionNode hrnB ) {
1022 assert belongsToThis( hrnA );
1023 assert belongsToThis( hrnB );
1024 assert hrnA != hrnB;
1026 // clear references in and out of node b?
1027 assert hrnB.isWiped();
1029 // copy each: (edge in and out of A) to B
1030 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
1031 while( itrReferencee.hasNext() ) {
1032 RefEdge edge = itrReferencee.next();
1033 HeapRegionNode hrnReferencee = edge.getDst();
1034 RefEdge edgeNew = edge.copy();
1035 edgeNew.setSrc( hrnB );
1036 edgeNew.setDst( hrnReferencee );
1038 addRefEdge( hrnB, hrnReferencee, edgeNew );
1041 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
1042 while( itrReferencer.hasNext() ) {
1043 RefEdge edge = itrReferencer.next();
1044 RefSrcNode rsnReferencer = edge.getSrc();
1045 RefEdge edgeNew = edge.copy();
1046 edgeNew.setSrc( rsnReferencer );
1047 edgeNew.setDst( hrnB );
1049 addRefEdge( rsnReferencer, hrnB, edgeNew );
1052 // replace hrnB reachability and preds with hrnA's
1053 hrnB.setAlpha( hrnA.getAlpha() );
1054 hrnB.setPreds( hrnA.getPreds() );
1056 // after transfer, wipe out source
1057 wipeOut( hrnA, true );
1061 // the purpose of this method is to conceptually "wipe out"
1062 // a heap region from the graph--purposefully not called REMOVE
1063 // because the node is still hanging around in the graph, just
1064 // not mechanically connected or have any reach or predicate
1065 // information on it anymore--lots of ops can use this
1066 protected void wipeOut( HeapRegionNode hrn,
1067 boolean wipeVariableReferences ) {
1069 assert belongsToThis( hrn );
1071 clearRefEdgesFrom( hrn, null, null, true );
1073 if( wipeVariableReferences ) {
1074 clearRefEdgesTo( hrn, null, null, true );
1076 clearNonVarRefEdgesTo( hrn );
1079 hrn.setAlpha( rsetEmpty );
1080 hrn.setPreds( predsEmpty );
1084 protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
1086 Canonical.ageTuplesFrom( edge.getBeta(),
1092 protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
1094 Canonical.ageTuplesFrom( hrn.getAlpha(),
1102 protected void propagateTokensOverNodes( HeapRegionNode nPrime,
1104 HashSet<HeapRegionNode> nodesWithNewAlpha,
1105 HashSet<RefEdge> edgesWithNewBeta ) {
1107 HashSet<HeapRegionNode> todoNodes
1108 = new HashSet<HeapRegionNode>();
1109 todoNodes.add( nPrime );
1111 HashSet<RefEdge> todoEdges
1112 = new HashSet<RefEdge>();
1114 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1115 = new Hashtable<HeapRegionNode, ChangeSet>();
1116 nodePlannedChanges.put( nPrime, c0 );
1118 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1119 = new Hashtable<RefEdge, ChangeSet>();
1121 // first propagate change sets everywhere they can go
1122 while( !todoNodes.isEmpty() ) {
1123 HeapRegionNode n = todoNodes.iterator().next();
1124 ChangeSet C = nodePlannedChanges.get( n );
1126 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1127 while( referItr.hasNext() ) {
1128 RefEdge edge = referItr.next();
1129 todoEdges.add( edge );
1131 if( !edgePlannedChanges.containsKey( edge ) ) {
1132 edgePlannedChanges.put( edge,
1137 edgePlannedChanges.put( edge,
1138 Canonical.union( edgePlannedChanges.get( edge ),
1144 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1145 while( refeeItr.hasNext() ) {
1146 RefEdge edgeF = refeeItr.next();
1147 HeapRegionNode m = edgeF.getDst();
1149 ChangeSet changesToPass = ChangeSet.factory();
1151 Iterator<ChangeTuple> itrCprime = C.iterator();
1152 while( itrCprime.hasNext() ) {
1153 ChangeTuple c = itrCprime.next();
1154 if( edgeF.getBeta().containsIgnorePreds( c.getStateToMatch() )
1157 changesToPass = Canonical.add( changesToPass, c );
1161 if( !changesToPass.isEmpty() ) {
1162 if( !nodePlannedChanges.containsKey( m ) ) {
1163 nodePlannedChanges.put( m, ChangeSet.factory() );
1166 ChangeSet currentChanges = nodePlannedChanges.get( m );
1168 if( !changesToPass.isSubset( currentChanges ) ) {
1170 nodePlannedChanges.put( m,
1171 Canonical.union( currentChanges,
1180 todoNodes.remove( n );
1183 // then apply all of the changes for each node at once
1184 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1185 while( itrMap.hasNext() ) {
1186 Map.Entry me = (Map.Entry) itrMap.next();
1187 HeapRegionNode n = (HeapRegionNode) me.getKey();
1188 ChangeSet C = (ChangeSet) me.getValue();
1190 // this propagation step is with respect to one change,
1191 // so we capture the full change from the old alpha:
1192 ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1196 // but this propagation may be only one of many concurrent
1197 // possible changes, so keep a running union with the node's
1198 // partially updated new alpha set
1199 n.setAlphaNew( Canonical.unionORpreds( n.getAlphaNew(),
1204 nodesWithNewAlpha.add( n );
1207 propagateTokensOverEdges( todoEdges,
1214 protected void propagateTokensOverEdges( HashSet <RefEdge> todoEdges,
1215 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1216 HashSet <RefEdge> edgesWithNewBeta ) {
1218 // first propagate all change tuples everywhere they can go
1219 while( !todoEdges.isEmpty() ) {
1220 RefEdge edgeE = todoEdges.iterator().next();
1221 todoEdges.remove( edgeE );
1223 if( !edgePlannedChanges.containsKey( edgeE ) ) {
1224 edgePlannedChanges.put( edgeE,
1229 ChangeSet C = edgePlannedChanges.get( edgeE );
1231 ChangeSet changesToPass = ChangeSet.factory();
1233 Iterator<ChangeTuple> itrC = C.iterator();
1234 while( itrC.hasNext() ) {
1235 ChangeTuple c = itrC.next();
1236 if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
1239 changesToPass = Canonical.add( changesToPass, c );
1243 RefSrcNode rsn = edgeE.getSrc();
1245 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1246 HeapRegionNode n = (HeapRegionNode) rsn;
1248 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1249 while( referItr.hasNext() ) {
1250 RefEdge edgeF = referItr.next();
1252 if( !edgePlannedChanges.containsKey( edgeF ) ) {
1253 edgePlannedChanges.put( edgeF,
1258 ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1260 if( !changesToPass.isSubset( currentChanges ) ) {
1261 todoEdges.add( edgeF );
1262 edgePlannedChanges.put( edgeF,
1263 Canonical.union( currentChanges,
1272 // then apply all of the changes for each edge at once
1273 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1274 while( itrMap.hasNext() ) {
1275 Map.Entry me = (Map.Entry) itrMap.next();
1276 RefEdge e = (RefEdge) me.getKey();
1277 ChangeSet C = (ChangeSet) me.getValue();
1279 // this propagation step is with respect to one change,
1280 // so we capture the full change from the old beta:
1281 ReachSet localDelta =
1282 Canonical.applyChangeSet( e.getBeta(),
1287 // but this propagation may be only one of many concurrent
1288 // possible changes, so keep a running union with the edge's
1289 // partially updated new beta set
1290 e.setBetaNew( Canonical.unionORpreds( e.getBetaNew(),
1295 edgesWithNewBeta.add( e );
1300 public void taintInSetVars( FlatSESEEnterNode sese ) {
1301 if( sese.getIsCallerSESEplaceholder() ) {
1305 Iterator<TempDescriptor> isvItr = sese.getInVarSet().iterator();
1306 while( isvItr.hasNext() ) {
1307 TempDescriptor isv = isvItr.next();
1308 VariableNode vn = getVariableNodeFromTemp( isv );
1310 Iterator<RefEdge> reItr = vn.iteratorToReferencees();
1311 while( reItr.hasNext() ) {
1312 RefEdge re = reItr.next();
1314 // these in-set taints should have empty
1315 // predicates so they never propagate
1317 Taint t = Taint.factory( sese,
1320 re.getDst().getAllocSite(),
1321 ExistPredSet.factory()
1324 re.setTaints( Canonical.add( re.getTaints(),
1332 // this is useful for more general tainting
1333 public void taintTemp( Taint taint,
1338 VariableNode vn = getVariableNodeFromTemp( td );
1340 Iterator<RefEdge> reItr = vn.iteratorToReferencees();
1341 while( reItr.hasNext() ) {
1342 RefEdge re = reItr.next();
1344 re.setTaints( Canonical.add( re.getTaints(),
1351 public void removeInContextTaints( FlatSESEEnterNode sese ) {
1352 if( sese.getIsCallerSESEplaceholder() ) {
1356 Iterator meItr = id2hrn.entrySet().iterator();
1357 while( meItr.hasNext() ) {
1358 Map.Entry me = (Map.Entry) meItr.next();
1359 Integer id = (Integer) me.getKey();
1360 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1362 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1363 while( reItr.hasNext() ) {
1364 RefEdge re = reItr.next();
1366 re.setTaints( Canonical.removeTaintsBy( re.getTaints(),
1375 // used in makeCalleeView below to decide if there is
1376 // already an appropriate out-of-context edge in a callee
1377 // view graph for merging, or null if a new one will be added
1379 getOutOfContextReferenceTo( HeapRegionNode hrn,
1380 TypeDescriptor srcType,
1381 TypeDescriptor refType,
1383 assert belongsToThis( hrn );
1385 HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1386 if( hrnInContext == null ) {
1390 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1391 while( refItr.hasNext() ) {
1392 RefEdge re = refItr.next();
1394 assert belongsToThis( re.getSrc() );
1395 assert belongsToThis( re.getDst() );
1397 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1401 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1402 if( !hrnSrc.isOutOfContext() ) {
1406 if( srcType == null ) {
1407 if( hrnSrc.getType() != null ) {
1411 if( !srcType.equals( hrnSrc.getType() ) ) {
1416 if( !re.typeEquals( refType ) ) {
1420 if( !re.fieldEquals( refField ) ) {
1424 // tada! We found it!
1431 // used below to convert a ReachSet to its callee-context
1432 // equivalent with respect to allocation sites in this graph
1433 protected ReachSet toCalleeContext( ReachSet rs,
1434 ExistPredSet predsNodeOrEdge,
1435 Set<HrnIdOoc> oocHrnIdOoc2callee
1437 ReachSet out = ReachSet.factory();
1439 Iterator<ReachState> itr = rs.iterator();
1440 while( itr.hasNext() ) {
1441 ReachState stateCaller = itr.next();
1443 ReachState stateCallee = stateCaller;
1445 Iterator<AllocSite> asItr = allocSites.iterator();
1446 while( asItr.hasNext() ) {
1447 AllocSite as = asItr.next();
1449 ReachState stateNew = ReachState.factory();
1450 Iterator<ReachTuple> rtItr = stateCallee.iterator();
1451 while( rtItr.hasNext() ) {
1452 ReachTuple rt = rtItr.next();
1454 // only translate this tuple if it is
1455 // in the out-callee-context bag
1456 HrnIdOoc hio = new HrnIdOoc( rt.getHrnID(),
1459 if( !oocHrnIdOoc2callee.contains( hio ) ) {
1460 stateNew = Canonical.add( stateNew, rt );
1464 int age = as.getAgeCategory( rt.getHrnID() );
1466 // this is the current mapping, where 0, 1, 2S were allocated
1467 // in the current context, 0?, 1? and 2S? were allocated in a
1468 // previous context, and we're translating to a future context
1480 if( age == AllocSite.AGE_notInThisSite ) {
1481 // things not from the site just go back in
1482 stateNew = Canonical.add( stateNew, rt );
1484 } else if( age == AllocSite.AGE_summary ||
1487 // the in-context summary and all existing out-of-context
1489 stateNew = Canonical.add( stateNew,
1490 ReachTuple.factory( as.getSummary(),
1493 true // out-of-context
1497 // otherwise everything else just goes to an out-of-context
1498 // version, everything else the same
1499 Integer I = as.getAge( rt.getHrnID() );
1502 assert !rt.isMultiObject();
1504 stateNew = Canonical.add( stateNew,
1505 ReachTuple.factory( rt.getHrnID(),
1508 true // out-of-context
1514 stateCallee = stateNew;
1517 // make a predicate of the caller graph element
1518 // and the caller state we just converted
1519 ExistPredSet predsWithState = ExistPredSet.factory();
1521 Iterator<ExistPred> predItr = predsNodeOrEdge.iterator();
1522 while( predItr.hasNext() ) {
1523 ExistPred predNodeOrEdge = predItr.next();
1526 Canonical.add( predsWithState,
1527 ExistPred.factory( predNodeOrEdge.n_hrnID,
1528 predNodeOrEdge.e_tdSrc,
1529 predNodeOrEdge.e_hrnSrcID,
1530 predNodeOrEdge.e_hrnDstID,
1531 predNodeOrEdge.e_type,
1532 predNodeOrEdge.e_field,
1535 predNodeOrEdge.e_srcOutCalleeContext,
1536 predNodeOrEdge.e_srcOutCallerContext
1541 stateCallee = Canonical.changePredsTo( stateCallee,
1544 out = Canonical.add( out,
1548 assert out.isCanonical();
1552 // used below to convert a ReachSet to its caller-context
1553 // equivalent with respect to allocation sites in this graph
1555 toCallerContext( ReachSet rs,
1556 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1558 ReachSet out = ReachSet.factory();
1560 // when the mapping is null it means there were no
1561 // predicates satisfied
1562 if( calleeStatesSatisfied == null ) {
1566 Iterator<ReachState> itr = rs.iterator();
1567 while( itr.hasNext() ) {
1568 ReachState stateCallee = itr.next();
1570 if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
1572 // starting from one callee state...
1573 ReachSet rsCaller = ReachSet.factory( stateCallee );
1575 // possibly branch it into many states, which any
1576 // allocation site might do, so lots of derived states
1577 Iterator<AllocSite> asItr = allocSites.iterator();
1578 while( asItr.hasNext() ) {
1579 AllocSite as = asItr.next();
1580 rsCaller = Canonical.toCallerContext( rsCaller, as );
1583 // then before adding each derived, now caller-context
1584 // states to the output, attach the appropriate pred
1585 // based on the source callee state
1586 Iterator<ReachState> stateItr = rsCaller.iterator();
1587 while( stateItr.hasNext() ) {
1588 ReachState stateCaller = stateItr.next();
1589 stateCaller = Canonical.attach( stateCaller,
1590 calleeStatesSatisfied.get( stateCallee )
1592 out = Canonical.add( out,
1599 assert out.isCanonical();
1604 // used below to convert a ReachSet to an equivalent
1605 // version with shadow IDs merged into unshadowed IDs
1606 protected ReachSet unshadow( ReachSet rs ) {
1608 Iterator<AllocSite> asItr = allocSites.iterator();
1609 while( asItr.hasNext() ) {
1610 AllocSite as = asItr.next();
1611 out = Canonical.unshadow( out, as );
1613 assert out.isCanonical();
1618 // convert a caller taint set into a callee taint set
1620 toCalleeContext( TaintSet ts,
1621 ExistPredSet predsEdge ) {
1623 TaintSet out = TaintSet.factory();
1625 // the idea is easy, the taint identifier itself doesn't
1626 // change at all, but the predicates should be tautology:
1627 // start with the preds passed in from the caller edge
1628 // that host the taints, and alter them to have the taint
1629 // added, just becoming more specific than edge predicate alone
1631 Iterator<Taint> itr = ts.iterator();
1632 while( itr.hasNext() ) {
1633 Taint tCaller = itr.next();
1635 ExistPredSet predsWithTaint = ExistPredSet.factory();
1637 Iterator<ExistPred> predItr = predsEdge.iterator();
1638 while( predItr.hasNext() ) {
1639 ExistPred predEdge = predItr.next();
1642 Canonical.add( predsWithTaint,
1643 ExistPred.factory( predEdge.e_tdSrc,
1644 predEdge.e_hrnSrcID,
1645 predEdge.e_hrnDstID,
1650 predEdge.e_srcOutCalleeContext,
1651 predEdge.e_srcOutCallerContext
1656 Taint tCallee = Canonical.changePredsTo( tCaller,
1659 out = Canonical.add( out,
1664 assert out.isCanonical();
1669 // used below to convert a TaintSet to its caller-context
1670 // equivalent, just eliminate Taints with bad preds
1672 toCallerContext( TaintSet ts,
1673 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied
1676 TaintSet out = TaintSet.factory();
1678 // when the mapping is null it means there were no
1679 // predicates satisfied
1680 if( calleeTaintsSatisfied == null ) {
1684 Iterator<Taint> itr = ts.iterator();
1685 while( itr.hasNext() ) {
1686 Taint tCallee = itr.next();
1688 if( calleeTaintsSatisfied.containsKey( tCallee ) ) {
1691 Canonical.attach( Taint.factory( tCallee.sese,
1695 ExistPredSet.factory() ),
1696 calleeTaintsSatisfied.get( tCallee )
1698 out = Canonical.add( out,
1704 assert out.isCanonical();
1711 // use this method to make a new reach graph that is
1712 // what heap the FlatMethod callee from the FlatCall
1713 // would start with reaching from its arguments in
1716 makeCalleeView( FlatCall fc,
1717 FlatMethod fmCallee,
1718 Set<Integer> callerNodeIDsCopiedToCallee,
1719 boolean writeDebugDOTs
1723 // first traverse this context to find nodes and edges
1724 // that will be callee-reachable
1725 Set<HeapRegionNode> reachableCallerNodes =
1726 new HashSet<HeapRegionNode>();
1728 // caller edges between callee-reachable nodes
1729 Set<RefEdge> reachableCallerEdges =
1730 new HashSet<RefEdge>();
1732 // caller edges from arg vars, and the matching param index
1733 // because these become a special edge in callee
1734 Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1735 new Hashtable<RefEdge, Integer>();
1737 // caller edges from local vars or callee-unreachable nodes
1738 // (out-of-context sources) to callee-reachable nodes
1739 Set<RefEdge> oocCallerEdges =
1740 new HashSet<RefEdge>();
1743 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1745 TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1746 VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
1748 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1749 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1751 toVisitInCaller.add( vnArgCaller );
1753 while( !toVisitInCaller.isEmpty() ) {
1754 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1755 toVisitInCaller.remove( rsnCaller );
1756 visitedInCaller.add( rsnCaller );
1758 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1759 while( itrRefEdges.hasNext() ) {
1760 RefEdge reCaller = itrRefEdges.next();
1761 HeapRegionNode hrnCaller = reCaller.getDst();
1763 callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
1764 reachableCallerNodes.add( hrnCaller );
1766 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1767 reachableCallerEdges.add( reCaller );
1769 if( rsnCaller.equals( vnArgCaller ) ) {
1770 reachableCallerArgEdges2paramIndex.put( reCaller, i );
1772 oocCallerEdges.add( reCaller );
1776 if( !visitedInCaller.contains( hrnCaller ) ) {
1777 toVisitInCaller.add( hrnCaller );
1780 } // end edge iteration
1781 } // end visiting heap nodes in caller
1782 } // end iterating over parameters as starting points
1785 // now collect out-of-callee-context IDs and
1786 // map them to whether the ID is out of the caller
1788 Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1790 Iterator<Integer> itrInContext =
1791 callerNodeIDsCopiedToCallee.iterator();
1792 while( itrInContext.hasNext() ) {
1793 Integer hrnID = itrInContext.next();
1794 HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1796 Iterator<RefEdge> itrMightCross =
1797 hrnCallerAndInContext.iteratorToReferencers();
1798 while( itrMightCross.hasNext() ) {
1799 RefEdge edgeMightCross = itrMightCross.next();
1801 RefSrcNode rsnCallerAndOutContext =
1802 edgeMightCross.getSrc();
1804 if( rsnCallerAndOutContext instanceof VariableNode ) {
1805 // variables do not have out-of-context reach states,
1807 oocCallerEdges.add( edgeMightCross );
1811 HeapRegionNode hrnCallerAndOutContext =
1812 (HeapRegionNode) rsnCallerAndOutContext;
1814 // is this source node out-of-context?
1815 if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1816 // no, skip this edge
1821 oocCallerEdges.add( edgeMightCross );
1823 // add all reach tuples on the node to list
1824 // of things that are out-of-context: insight
1825 // if this node is reachable from someting that WAS
1826 // in-context, then this node should already be in-context
1827 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1828 while( stateItr.hasNext() ) {
1829 ReachState state = stateItr.next();
1831 Iterator<ReachTuple> rtItr = state.iterator();
1832 while( rtItr.hasNext() ) {
1833 ReachTuple rt = rtItr.next();
1835 oocHrnIdOoc2callee.add( new HrnIdOoc( rt.getHrnID(),
1844 // the callee view is a new graph: DON'T MODIFY *THIS* graph
1845 ReachGraph rg = new ReachGraph();
1847 // add nodes to callee graph
1848 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1849 while( hrnItr.hasNext() ) {
1850 HeapRegionNode hrnCaller = hrnItr.next();
1852 assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
1853 assert !rg.id2hrn.containsKey( hrnCaller.getID() );
1855 ExistPred pred = ExistPred.factory( hrnCaller.getID(), null );
1856 ExistPredSet preds = ExistPredSet.factory( pred );
1858 rg.createNewHeapRegionNode( hrnCaller.getID(),
1859 hrnCaller.isSingleObject(),
1860 hrnCaller.isNewSummary(),
1861 false, // out-of-context?
1862 hrnCaller.getType(),
1863 hrnCaller.getAllocSite(),
1864 toCalleeContext( hrnCaller.getInherent(),
1868 toCalleeContext( hrnCaller.getAlpha(),
1873 hrnCaller.getDescription()
1877 // add param edges to callee graph
1879 reachableCallerArgEdges2paramIndex.entrySet().iterator();
1880 while( argEdges.hasNext() ) {
1881 Map.Entry me = (Map.Entry) argEdges.next();
1882 RefEdge reArg = (RefEdge) me.getKey();
1883 Integer index = (Integer) me.getValue();
1885 VariableNode vnCaller = (VariableNode) reArg.getSrc();
1886 TempDescriptor argCaller = vnCaller.getTempDescriptor();
1888 TempDescriptor paramCallee = fmCallee.getParameter( index );
1889 VariableNode vnCallee = rg.getVariableNodeFromTemp( paramCallee );
1891 HeapRegionNode hrnDstCaller = reArg.getDst();
1892 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1893 assert hrnDstCallee != null;
1896 ExistPred.factory( argCaller,
1898 hrnDstCallee.getID(),
1903 true, // out-of-callee-context
1904 false // out-of-caller-context
1907 ExistPredSet preds =
1908 ExistPredSet.factory( pred );
1911 new RefEdge( vnCallee,
1915 toCalleeContext( reArg.getBeta(),
1920 toCalleeContext( reArg.getTaints(),
1924 rg.addRefEdge( vnCallee,
1930 // add in-context edges to callee graph
1931 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1932 while( reItr.hasNext() ) {
1933 RefEdge reCaller = reItr.next();
1934 RefSrcNode rsnCaller = reCaller.getSrc();
1935 assert rsnCaller instanceof HeapRegionNode;
1936 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1937 HeapRegionNode hrnDstCaller = reCaller.getDst();
1939 HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
1940 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1941 assert hrnSrcCallee != null;
1942 assert hrnDstCallee != null;
1945 ExistPred.factory( null,
1946 hrnSrcCallee.getID(),
1947 hrnDstCallee.getID(),
1949 reCaller.getField(),
1952 false, // out-of-callee-context
1953 false // out-of-caller-context
1956 ExistPredSet preds =
1957 ExistPredSet.factory( pred );
1960 new RefEdge( hrnSrcCallee,
1963 reCaller.getField(),
1964 toCalleeContext( reCaller.getBeta(),
1969 TaintSet.factory() // no taints for in-context edges
1972 rg.addRefEdge( hrnSrcCallee,
1978 // add out-of-context edges to callee graph
1979 reItr = oocCallerEdges.iterator();
1980 while( reItr.hasNext() ) {
1981 RefEdge reCaller = reItr.next();
1982 RefSrcNode rsnCaller = reCaller.getSrc();
1983 HeapRegionNode hrnDstCaller = reCaller.getDst();
1984 HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1985 assert hrnDstCallee != null;
1987 TypeDescriptor oocNodeType;
1989 TempDescriptor oocPredSrcTemp = null;
1990 Integer oocPredSrcID = null;
1991 boolean outOfCalleeContext;
1992 boolean outOfCallerContext;
1994 if( rsnCaller instanceof VariableNode ) {
1995 VariableNode vnCaller = (VariableNode) rsnCaller;
1997 oocReach = rsetEmpty;
1998 oocPredSrcTemp = vnCaller.getTempDescriptor();
1999 outOfCalleeContext = true;
2000 outOfCallerContext = false;
2003 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2004 assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
2005 oocNodeType = hrnSrcCaller.getType();
2006 oocReach = hrnSrcCaller.getAlpha();
2007 oocPredSrcID = hrnSrcCaller.getID();
2008 if( hrnSrcCaller.isOutOfContext() ) {
2009 outOfCalleeContext = false;
2010 outOfCallerContext = true;
2012 outOfCalleeContext = true;
2013 outOfCallerContext = false;
2018 ExistPred.factory( oocPredSrcTemp,
2020 hrnDstCallee.getID(),
2022 reCaller.getField(),
2029 ExistPredSet preds =
2030 ExistPredSet.factory( pred );
2032 RefEdge oocEdgeExisting =
2033 rg.getOutOfContextReferenceTo( hrnDstCallee,
2039 if( oocEdgeExisting == null ) {
2040 // for consistency, map one out-of-context "identifier"
2041 // to one heap region node id, otherwise no convergence
2042 String oocid = "oocid"+
2044 hrnDstCallee.getIDString()+
2047 reCaller.getField();
2049 Integer oocHrnID = oocid2hrnid.get( oocid );
2051 HeapRegionNode hrnCalleeAndOutContext;
2053 if( oocHrnID == null ) {
2055 hrnCalleeAndOutContext =
2056 rg.createNewHeapRegionNode( null, // ID
2057 false, // single object?
2058 false, // new summary?
2059 true, // out-of-context?
2061 null, // alloc site, shouldn't be used
2062 toCalleeContext( oocReach,
2066 toCalleeContext( oocReach,
2074 oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
2078 // the mapping already exists, so see if node is there
2079 hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
2081 if( hrnCalleeAndOutContext == null ) {
2083 hrnCalleeAndOutContext =
2084 rg.createNewHeapRegionNode( oocHrnID, // ID
2085 false, // single object?
2086 false, // new summary?
2087 true, // out-of-context?
2089 null, // alloc site, shouldn't be used
2090 toCalleeContext( oocReach,
2094 toCalleeContext( oocReach,
2103 // otherwise it is there, so merge reachability
2104 hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
2105 toCalleeContext( oocReach,
2114 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2116 rg.addRefEdge( hrnCalleeAndOutContext,
2118 new RefEdge( hrnCalleeAndOutContext,
2121 reCaller.getField(),
2122 toCalleeContext( reCaller.getBeta(),
2127 toCalleeContext( reCaller.getTaints(),
2133 // the out-of-context edge already exists
2134 oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
2135 toCalleeContext( reCaller.getBeta(),
2142 oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
2147 oocEdgeExisting.setTaints( Canonical.unionORpreds( oocEdgeExisting.getTaints(),
2148 toCalleeContext( reCaller.getTaints(),
2154 HeapRegionNode hrnCalleeAndOutContext =
2155 (HeapRegionNode) oocEdgeExisting.getSrc();
2156 hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
2157 toCalleeContext( oocReach,
2164 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2169 if( writeDebugDOTs ) {
2170 debugGraphPrefix = String.format( "call%03d", debugCallSiteVisitCounter );
2171 rg.writeGraph( debugGraphPrefix+"calleeview",
2172 resolveMethodDebugDOTwriteLabels,
2173 resolveMethodDebugDOTselectTemps,
2174 resolveMethodDebugDOTpruneGarbage,
2175 resolveMethodDebugDOThideReach,
2176 resolveMethodDebugDOThideSubsetReach,
2177 resolveMethodDebugDOThidePreds,
2178 resolveMethodDebugDOThideEdgeTaints );
2184 private static Hashtable<String, Integer> oocid2hrnid =
2185 new Hashtable<String, Integer>();
2188 // useful since many graphs writes in the method call debug code
2189 private static boolean resolveMethodDebugDOTwriteLabels = true;
2190 private static boolean resolveMethodDebugDOTselectTemps = true;
2191 private static boolean resolveMethodDebugDOTpruneGarbage = true;
2192 private static boolean resolveMethodDebugDOThideReach = true;
2193 private static boolean resolveMethodDebugDOThideSubsetReach = true;
2194 private static boolean resolveMethodDebugDOThidePreds = true;
2195 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
2197 static String debugGraphPrefix;
2198 static int debugCallSiteVisitCounter;
2199 static int debugCallSiteVisitStartCapture;
2200 static int debugCallSiteNumVisitsToCapture;
2201 static boolean debugCallSiteStopAfter;
2205 resolveMethodCall( FlatCall fc,
2206 FlatMethod fmCallee,
2207 ReachGraph rgCallee,
2208 Set<Integer> callerNodeIDsCopiedToCallee,
2209 boolean writeDebugDOTs
2212 if( writeDebugDOTs ) {
2213 System.out.println( " Writing out visit "+
2214 debugCallSiteVisitCounter+
2215 " to debug call site" );
2217 debugGraphPrefix = String.format( "call%03d",
2218 debugCallSiteVisitCounter );
2220 rgCallee.writeGraph( debugGraphPrefix+"callee",
2221 resolveMethodDebugDOTwriteLabels,
2222 resolveMethodDebugDOTselectTemps,
2223 resolveMethodDebugDOTpruneGarbage,
2224 resolveMethodDebugDOThideReach,
2225 resolveMethodDebugDOThideSubsetReach,
2226 resolveMethodDebugDOThidePreds,
2227 resolveMethodDebugDOThideEdgeTaints );
2229 writeGraph( debugGraphPrefix+"caller00In",
2230 resolveMethodDebugDOTwriteLabels,
2231 resolveMethodDebugDOTselectTemps,
2232 resolveMethodDebugDOTpruneGarbage,
2233 resolveMethodDebugDOThideReach,
2234 resolveMethodDebugDOThideSubsetReach,
2235 resolveMethodDebugDOThidePreds,
2236 resolveMethodDebugDOThideEdgeTaints,
2237 callerNodeIDsCopiedToCallee );
2242 // method call transfer function steps:
2243 // 1. Use current callee-reachable heap (CRH) to test callee
2244 // predicates and mark what will be coming in.
2245 // 2. Wipe CRH out of caller.
2246 // 3. Transplant marked callee parts in:
2247 // a) bring in nodes
2248 // b) bring in callee -> callee edges
2249 // c) resolve out-of-context -> callee edges
2250 // d) assign return value
2251 // 4. Collapse shadow nodes down
2252 // 5. Global sweep it.
2255 // 1. mark what callee elements have satisfied predicates
2256 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
2257 new Hashtable<HeapRegionNode, ExistPredSet>();
2259 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
2260 new Hashtable<RefEdge, ExistPredSet>();
2262 Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
2263 calleeNode2calleeStatesSatisfied =
2264 new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
2266 Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
2267 calleeEdge2calleeStatesSatisfied =
2268 new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
2270 Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
2271 calleeEdge2calleeTaintsSatisfied =
2272 new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
2274 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
2275 new Hashtable< RefEdge, Set<RefSrcNode> >();
2278 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2279 while( meItr.hasNext() ) {
2280 Map.Entry me = (Map.Entry) meItr.next();
2281 Integer id = (Integer) me.getKey();
2282 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2284 // if a callee element's predicates are satisfied then a set
2285 // of CALLER predicates is returned: they are the predicates
2286 // that the callee element moved into the caller context
2287 // should have, and it is inefficient to find this again later
2288 ExistPredSet predsIfSatis =
2289 hrnCallee.getPreds().isSatisfiedBy( this,
2290 callerNodeIDsCopiedToCallee
2293 if( predsIfSatis != null ) {
2294 calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
2296 // otherwise don't bother looking at edges to this node
2300 // since the node is coming over, find out which reach
2301 // states on it should come over, too
2302 assert calleeNode2calleeStatesSatisfied.get( hrnCallee ) == null;
2304 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2305 while( stateItr.hasNext() ) {
2306 ReachState stateCallee = stateItr.next();
2309 stateCallee.getPreds().isSatisfiedBy( this,
2310 callerNodeIDsCopiedToCallee
2312 if( predsIfSatis != null ) {
2314 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2315 calleeNode2calleeStatesSatisfied.get( hrnCallee );
2317 if( calleeStatesSatisfied == null ) {
2318 calleeStatesSatisfied =
2319 new Hashtable<ReachState, ExistPredSet>();
2321 calleeNode2calleeStatesSatisfied.put( hrnCallee, calleeStatesSatisfied );
2324 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2328 // then look at edges to the node
2329 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2330 while( reItr.hasNext() ) {
2331 RefEdge reCallee = reItr.next();
2332 RefSrcNode rsnCallee = reCallee.getSrc();
2334 // (caller local variables to in-context heap regions)
2335 // have an (out-of-context heap region -> in-context heap region)
2336 // abstraction in the callEE, so its true we never need to
2337 // look at a (var node -> heap region) edge in callee to bring
2338 // those over for the call site transfer, except for the special
2339 // case of *RETURN var* -> heap region edges.
2340 // What about (param var->heap region)
2341 // edges in callee? They are dealt with below this loop.
2343 if( rsnCallee instanceof VariableNode ) {
2345 // looking for the return-value variable only
2346 VariableNode vnCallee = (VariableNode) rsnCallee;
2347 if( vnCallee.getTempDescriptor() != tdReturn ) {
2351 TempDescriptor returnTemp = fc.getReturnTemp();
2352 if( returnTemp == null ||
2353 !DisjointAnalysis.shouldAnalysisTrack( returnTemp.getType() )
2358 // note that the assignment of the return value is to a
2359 // variable in the caller which is out-of-context with
2360 // respect to the callee
2361 VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2362 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2363 rsnCallers.add( vnLhsCaller );
2364 calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2368 // for HeapRegionNode callee sources...
2370 // first see if the source is out-of-context, and only
2371 // proceed with this edge if we find some caller-context
2373 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2374 boolean matchedOutOfContext = false;
2376 if( !hrnSrcCallee.isOutOfContext() ) {
2379 hrnSrcCallee.getPreds().isSatisfiedBy( this,
2380 callerNodeIDsCopiedToCallee
2382 if( predsIfSatis != null ) {
2383 calleeNodesSatisfied.put( hrnSrcCallee, predsIfSatis );
2385 // otherwise forget this edge
2390 // hrnSrcCallee is out-of-context
2392 assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2394 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2396 // is the target node in the caller?
2397 HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2398 if( hrnDstCaller == null ) {
2402 Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2403 while( reDstItr.hasNext() ) {
2404 // the edge and field (either possibly null) must match
2405 RefEdge reCaller = reDstItr.next();
2407 if( !reCaller.typeEquals ( reCallee.getType() ) ||
2408 !reCaller.fieldEquals( reCallee.getField() )
2413 RefSrcNode rsnCaller = reCaller.getSrc();
2414 if( rsnCaller instanceof VariableNode ) {
2416 // a variable node matches an OOC region with null type
2417 if( hrnSrcCallee.getType() != null ) {
2422 // otherwise types should match
2423 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2424 if( hrnSrcCallee.getType() == null ) {
2425 if( hrnCallerSrc.getType() != null ) {
2429 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2435 rsnCallers.add( rsnCaller );
2436 matchedOutOfContext = true;
2439 if( !rsnCallers.isEmpty() ) {
2440 calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2444 if( hrnSrcCallee.isOutOfContext() &&
2445 !matchedOutOfContext ) {
2452 reCallee.getPreds().isSatisfiedBy( this,
2453 callerNodeIDsCopiedToCallee
2456 if( predsIfSatis != null ) {
2457 calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2459 // since the edge is coming over, find out which reach
2460 // states on it should come over, too
2461 assert calleeEdge2calleeStatesSatisfied.get( reCallee ) == null;
2463 stateItr = reCallee.getBeta().iterator();
2464 while( stateItr.hasNext() ) {
2465 ReachState stateCallee = stateItr.next();
2468 stateCallee.getPreds().isSatisfiedBy( this,
2469 callerNodeIDsCopiedToCallee
2471 if( predsIfSatis != null ) {
2473 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2474 calleeEdge2calleeStatesSatisfied.get( reCallee );
2476 if( calleeStatesSatisfied == null ) {
2477 calleeStatesSatisfied =
2478 new Hashtable<ReachState, ExistPredSet>();
2480 calleeEdge2calleeStatesSatisfied.put( reCallee, calleeStatesSatisfied );
2483 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2487 // since the edge is coming over, find out which taints
2488 // on it should come over, too
2489 assert calleeEdge2calleeTaintsSatisfied.get( reCallee ) == null;
2491 Iterator<Taint> tItr = reCallee.getTaints().iterator();
2492 while( tItr.hasNext() ) {
2493 Taint tCallee = tItr.next();
2496 tCallee.getPreds().isSatisfiedBy( this,
2497 callerNodeIDsCopiedToCallee
2499 if( predsIfSatis != null ) {
2501 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2502 calleeEdge2calleeTaintsSatisfied.get( reCallee );
2504 if( calleeTaintsSatisfied == null ) {
2505 calleeTaintsSatisfied =
2506 new Hashtable<Taint, ExistPredSet>();
2508 calleeEdge2calleeTaintsSatisfied.put( reCallee, calleeTaintsSatisfied );
2511 calleeTaintsSatisfied.put( tCallee, predsIfSatis );
2518 if( writeDebugDOTs ) {
2519 writeGraph( debugGraphPrefix+"caller20BeforeWipe",
2520 resolveMethodDebugDOTwriteLabels,
2521 resolveMethodDebugDOTselectTemps,
2522 resolveMethodDebugDOTpruneGarbage,
2523 resolveMethodDebugDOThideReach,
2524 resolveMethodDebugDOThideSubsetReach,
2525 resolveMethodDebugDOThidePreds,
2526 resolveMethodDebugDOThideEdgeTaints );
2530 // 2. predicates tested, ok to wipe out caller part
2531 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2532 while( hrnItr.hasNext() ) {
2533 Integer hrnID = hrnItr.next();
2534 HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2535 assert hrnCaller != null;
2537 // when clearing off nodes, also eliminate variable
2539 wipeOut( hrnCaller, true );
2542 // if we are assigning the return value to something, clobber now
2543 // as part of the wipe
2544 TempDescriptor returnTemp = fc.getReturnTemp();
2545 if( returnTemp != null &&
2546 DisjointAnalysis.shouldAnalysisTrack( returnTemp.getType() )
2549 VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2550 clearRefEdgesFrom( vnLhsCaller, null, null, true );
2556 if( writeDebugDOTs ) {
2557 writeGraph( debugGraphPrefix+"caller30BeforeAddingNodes",
2558 resolveMethodDebugDOTwriteLabels,
2559 resolveMethodDebugDOTselectTemps,
2560 resolveMethodDebugDOTpruneGarbage,
2561 resolveMethodDebugDOThideReach,
2562 resolveMethodDebugDOThideSubsetReach,
2563 resolveMethodDebugDOThidePreds,
2564 resolveMethodDebugDOThideEdgeTaints );
2570 // 3. callee elements with satisfied preds come in, note that
2571 // the mapping of elements satisfied to preds is like this:
2572 // A callee element EE has preds EEp that are satisfied by
2573 // some caller element ER. We bring EE into the caller
2574 // context as ERee with the preds of ER, namely ERp, which
2575 // in the following algorithm is the value in the mapping
2578 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2579 while( satisItr.hasNext() ) {
2580 Map.Entry me = (Map.Entry) satisItr.next();
2581 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2582 ExistPredSet preds = (ExistPredSet) me.getValue();
2584 // TODO: I think its true that the current implementation uses
2585 // the type of the OOC region and the predicates OF THE EDGE from
2586 // it to link everything up in caller context, so that's why we're
2587 // skipping this... maybe that's a sillier way to do it?
2588 if( hrnCallee.isOutOfContext() ) {
2592 AllocSite as = hrnCallee.getAllocSite();
2593 allocSites.add( as );
2595 Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2597 HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2598 if( hrnCaller == null ) {
2600 createNewHeapRegionNode( hrnIDshadow, // id or null to generate a new one
2601 hrnCallee.isSingleObject(), // single object?
2602 hrnCallee.isNewSummary(), // summary?
2603 false, // out-of-context?
2604 hrnCallee.getType(), // type
2605 hrnCallee.getAllocSite(), // allocation site
2606 toCallerContext( hrnCallee.getInherent(),
2607 calleeNode2calleeStatesSatisfied.get( hrnCallee ) ), // inherent reach
2608 null, // current reach
2609 predsEmpty, // predicates
2610 hrnCallee.getDescription() // description
2613 assert hrnCaller.isWiped();
2616 hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2617 calleeNode2calleeStatesSatisfied.get( hrnCallee )
2621 hrnCaller.setPreds( preds );
2628 if( writeDebugDOTs ) {
2629 writeGraph( debugGraphPrefix+"caller31BeforeAddingEdges",
2630 resolveMethodDebugDOTwriteLabels,
2631 resolveMethodDebugDOTselectTemps,
2632 resolveMethodDebugDOTpruneGarbage,
2633 resolveMethodDebugDOThideReach,
2634 resolveMethodDebugDOThideSubsetReach,
2635 resolveMethodDebugDOThidePreds,
2636 resolveMethodDebugDOThideEdgeTaints );
2640 // set these up during the next procedure so after
2641 // the caller has all of its nodes and edges put
2642 // back together we can propagate the callee's
2643 // reach changes backwards into the caller graph
2644 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2646 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2647 new Hashtable<RefEdge, ChangeSet>();
2650 // 3.b) callee -> callee edges AND out-of-context -> callee
2651 // which includes return temp -> callee edges now, too
2652 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2653 while( satisItr.hasNext() ) {
2654 Map.Entry me = (Map.Entry) satisItr.next();
2655 RefEdge reCallee = (RefEdge) me.getKey();
2656 ExistPredSet preds = (ExistPredSet) me.getValue();
2658 HeapRegionNode hrnDstCallee = reCallee.getDst();
2659 AllocSite asDst = hrnDstCallee.getAllocSite();
2660 allocSites.add( asDst );
2662 Integer hrnIDDstShadow =
2663 asDst.getShadowIDfromID( hrnDstCallee.getID() );
2665 HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2666 assert hrnDstCaller != null;
2669 RefSrcNode rsnCallee = reCallee.getSrc();
2671 Set<RefSrcNode> rsnCallers =
2672 new HashSet<RefSrcNode>();
2674 Set<RefSrcNode> oocCallers =
2675 calleeEdges2oocCallerSrcMatches.get( reCallee );
2677 if( rsnCallee instanceof HeapRegionNode ) {
2678 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2679 if( hrnCalleeSrc.isOutOfContext() ) {
2680 assert oocCallers != null;
2685 if( oocCallers == null ) {
2686 // there are no out-of-context matches, so it's
2687 // either a param/arg var or one in-context heap region
2688 if( rsnCallee instanceof VariableNode ) {
2689 // variable -> node in the callee should only
2690 // come into the caller if its from a param var
2691 VariableNode vnCallee = (VariableNode) rsnCallee;
2692 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2693 TempDescriptor tdArg = fc.getArgMatchingParam( fmCallee,
2695 if( tdArg == null ) {
2696 // this means the variable isn't a parameter, its local
2697 // to the callee so we ignore it in call site transfer
2698 // shouldn't this NEVER HAPPEN?
2702 rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2705 // otherwise source is in context, one region
2707 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2709 // translate an in-context node to shadow
2710 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2711 allocSites.add( asSrc );
2713 Integer hrnIDSrcShadow =
2714 asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2716 HeapRegionNode hrnSrcCallerShadow =
2717 this.id2hrn.get( hrnIDSrcShadow );
2719 assert hrnSrcCallerShadow != null;
2721 rsnCallers.add( hrnSrcCallerShadow );
2725 // otherwise we have a set of out-of-context srcs
2726 // that should NOT be translated to shadow nodes
2727 assert !oocCallers.isEmpty();
2728 rsnCallers.addAll( oocCallers );
2731 // now make all caller edges we've identified from
2732 // this callee edge with a satisfied predicate
2733 assert !rsnCallers.isEmpty();
2734 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2735 while( rsnItr.hasNext() ) {
2736 RefSrcNode rsnCaller = rsnItr.next();
2738 RefEdge reCaller = new RefEdge( rsnCaller,
2741 reCallee.getField(),
2742 toCallerContext( reCallee.getBeta(),
2743 calleeEdge2calleeStatesSatisfied.get( reCallee ) ),
2745 toCallerContext( reCallee.getTaints(),
2746 calleeEdge2calleeTaintsSatisfied.get( reCallee ) )
2749 ChangeSet cs = ChangeSet.factory();
2750 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2751 while( rsItr.hasNext() ) {
2752 ReachState state = rsItr.next();
2753 ExistPredSet predsPreCallee = state.getPreds();
2755 if( state.isEmpty() ) {
2759 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2760 while( predItr.hasNext() ) {
2761 ExistPred pred = predItr.next();
2762 ReachState old = pred.ne_state;
2768 cs = Canonical.add( cs,
2769 ChangeTuple.factory( old,
2776 // we're just going to use the convenient "merge-if-exists"
2777 // edge call below, but still take a separate look if there
2778 // is an existing caller edge to build change sets properly
2779 if( !cs.isEmpty() ) {
2780 RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2784 if( edgeExisting != null ) {
2785 ChangeSet csExisting = edgePlannedChanges.get( edgeExisting );
2786 if( csExisting == null ) {
2787 csExisting = ChangeSet.factory();
2789 edgePlannedChanges.put( edgeExisting,
2790 Canonical.union( csExisting,
2795 edgesForPropagation.add( reCaller );
2796 assert !edgePlannedChanges.containsKey( reCaller );
2797 edgePlannedChanges.put( reCaller, cs );
2801 // then add new caller edge or merge
2802 addEdgeOrMergeWithExisting( reCaller );
2810 if( writeDebugDOTs ) {
2811 writeGraph( debugGraphPrefix+"caller38propagateReach",
2812 resolveMethodDebugDOTwriteLabels,
2813 resolveMethodDebugDOTselectTemps,
2814 resolveMethodDebugDOTpruneGarbage,
2815 resolveMethodDebugDOThideReach,
2816 resolveMethodDebugDOThideSubsetReach,
2817 resolveMethodDebugDOThidePreds,
2818 resolveMethodDebugDOThideEdgeTaints );
2821 // propagate callee reachability changes to the rest
2822 // of the caller graph edges
2823 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2825 propagateTokensOverEdges( edgesForPropagation, // source edges
2826 edgePlannedChanges, // map src edge to change set
2827 edgesUpdated ); // list of updated edges
2829 // commit beta' (beta<-betaNew)
2830 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2831 while( edgeItr.hasNext() ) {
2832 edgeItr.next().applyBetaNew();
2841 if( writeDebugDOTs ) {
2842 writeGraph( debugGraphPrefix+"caller40BeforeShadowMerge",
2843 resolveMethodDebugDOTwriteLabels,
2844 resolveMethodDebugDOTselectTemps,
2845 resolveMethodDebugDOTpruneGarbage,
2846 resolveMethodDebugDOThideReach,
2847 resolveMethodDebugDOThideSubsetReach,
2848 resolveMethodDebugDOThidePreds,
2849 resolveMethodDebugDOThideEdgeTaints );
2853 // 4) merge shadow nodes so alloc sites are back to k
2854 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2855 while( asItr.hasNext() ) {
2856 // for each allocation site do the following to merge
2857 // shadow nodes (newest from callee) with any existing
2858 // look for the newest normal and newest shadow "slot"
2859 // not being used, transfer normal to shadow. Keep
2860 // doing this until there are no more normal nodes, or
2861 // no empty shadow slots: then merge all remaining normal
2862 // nodes into the shadow summary. Finally, convert all
2863 // shadow to their normal versions.
2864 AllocSite as = asItr.next();
2867 while( ageNorm < allocationDepth &&
2868 ageShad < allocationDepth ) {
2870 // first, are there any normal nodes left?
2871 Integer idNorm = as.getIthOldest( ageNorm );
2872 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2873 if( hrnNorm == null ) {
2874 // no, this age of normal node not in the caller graph
2879 // yes, a normal node exists, is there an empty shadow
2880 // "slot" to transfer it onto?
2881 HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2882 if( !hrnShad.isWiped() ) {
2883 // no, this age of shadow node is not empty
2888 // yes, this shadow node is empty
2889 transferOnto( hrnNorm, hrnShad );
2894 // now, while there are still normal nodes but no shadow
2895 // slots, merge normal nodes into the shadow summary
2896 while( ageNorm < allocationDepth ) {
2898 // first, are there any normal nodes left?
2899 Integer idNorm = as.getIthOldest( ageNorm );
2900 HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2901 if( hrnNorm == null ) {
2902 // no, this age of normal node not in the caller graph
2907 // yes, a normal node exists, so get the shadow summary
2908 HeapRegionNode summShad = getSummaryNode( as, true );
2909 mergeIntoSummary( hrnNorm, summShad );
2913 // if there is a normal summary, merge it into shadow summary
2914 Integer idNorm = as.getSummary();
2915 HeapRegionNode summNorm = id2hrn.get( idNorm );
2916 if( summNorm != null ) {
2917 HeapRegionNode summShad = getSummaryNode( as, true );
2918 mergeIntoSummary( summNorm, summShad );
2921 // finally, flip all existing shadow nodes onto the normal
2922 for( int i = 0; i < allocationDepth; ++i ) {
2923 Integer idShad = as.getIthOldestShadow( i );
2924 HeapRegionNode hrnShad = id2hrn.get( idShad );
2925 if( hrnShad != null ) {
2927 HeapRegionNode hrnNorm = getIthNode( as, i, false );
2928 assert hrnNorm.isWiped();
2929 transferOnto( hrnShad, hrnNorm );
2933 Integer idShad = as.getSummaryShadow();
2934 HeapRegionNode summShad = id2hrn.get( idShad );
2935 if( summShad != null ) {
2936 summNorm = getSummaryNode( as, false );
2937 transferOnto( summShad, summNorm );
2946 if( writeDebugDOTs ) {
2947 writeGraph( debugGraphPrefix+"caller45BeforeUnshadow",
2948 resolveMethodDebugDOTwriteLabels,
2949 resolveMethodDebugDOTselectTemps,
2950 resolveMethodDebugDOTpruneGarbage,
2951 resolveMethodDebugDOThideReach,
2952 resolveMethodDebugDOThideSubsetReach,
2953 resolveMethodDebugDOThidePreds,
2954 resolveMethodDebugDOThideEdgeTaints );
2958 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2959 while( itrAllHRNodes.hasNext() ) {
2960 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
2961 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2963 hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2965 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2966 while( itrEdges.hasNext() ) {
2967 RefEdge re = itrEdges.next();
2968 re.setBeta( unshadow( re.getBeta() ) );
2975 if( writeDebugDOTs ) {
2976 writeGraph( debugGraphPrefix+"caller50BeforeGlobalSweep",
2977 resolveMethodDebugDOTwriteLabels,
2978 resolveMethodDebugDOTselectTemps,
2979 resolveMethodDebugDOTpruneGarbage,
2980 resolveMethodDebugDOThideReach,
2981 resolveMethodDebugDOThideSubsetReach,
2982 resolveMethodDebugDOThidePreds,
2983 resolveMethodDebugDOThideEdgeTaints );
2988 if( !DISABLE_GLOBAL_SWEEP ) {
2993 if( writeDebugDOTs ) {
2994 writeGraph( debugGraphPrefix+"caller90AfterTransfer",
2995 resolveMethodDebugDOTwriteLabels,
2996 resolveMethodDebugDOTselectTemps,
2997 resolveMethodDebugDOTpruneGarbage,
2998 resolveMethodDebugDOThideReach,
2999 resolveMethodDebugDOThideSubsetReach,
3000 resolveMethodDebugDOThidePreds,
3001 resolveMethodDebugDOThideEdgeTaints );
3007 ////////////////////////////////////////////////////
3009 // Abstract garbage collection simply removes
3010 // heap region nodes that are not mechanically
3011 // reachable from a root set. This step is
3012 // essential for testing node and edge existence
3013 // predicates efficiently
3015 ////////////////////////////////////////////////////
3016 public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
3018 // calculate a root set, will be different for Java
3019 // version of analysis versus Bamboo version
3020 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3022 // visit every variable in graph while building root
3023 // set, and do iterating on a copy, so we can remove
3024 // dead variables while we're at this
3025 Iterator makeCopyItr = td2vn.entrySet().iterator();
3026 Set entrysCopy = new HashSet();
3027 while( makeCopyItr.hasNext() ) {
3028 entrysCopy.add( makeCopyItr.next() );
3031 Iterator eItr = entrysCopy.iterator();
3032 while( eItr.hasNext() ) {
3033 Map.Entry me = (Map.Entry) eItr.next();
3034 TempDescriptor td = (TempDescriptor) me.getKey();
3035 VariableNode vn = (VariableNode) me.getValue();
3037 if( liveSet.contains( td ) ) {
3041 // dead var, remove completely from graph
3043 clearRefEdgesFrom( vn, null, null, true );
3047 // everything visited in a traversal is
3048 // considered abstractly live
3049 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3051 while( !toVisit.isEmpty() ) {
3052 RefSrcNode rsn = toVisit.iterator().next();
3053 toVisit.remove( rsn );
3056 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3057 while( hrnItr.hasNext() ) {
3058 RefEdge edge = hrnItr.next();
3059 HeapRegionNode hrn = edge.getDst();
3061 if( !visited.contains( hrn ) ) {
3067 // get a copy of the set to iterate over because
3068 // we're going to monkey with the graph when we
3069 // identify a garbage node
3070 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3071 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3072 while( hrnItr.hasNext() ) {
3073 hrnAllPrior.add( hrnItr.next() );
3076 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3077 while( hrnAllItr.hasNext() ) {
3078 HeapRegionNode hrn = hrnAllItr.next();
3080 if( !visited.contains( hrn ) ) {
3082 // heap region nodes are compared across ReachGraph
3083 // objects by their integer ID, so when discarding
3084 // garbage nodes we must also discard entries in
3085 // the ID -> heap region hashtable.
3086 id2hrn.remove( hrn.getID() );
3088 // RefEdge objects are two-way linked between
3089 // nodes, so when a node is identified as garbage,
3090 // actively clear references to and from it so
3091 // live nodes won't have dangling RefEdge's
3092 wipeOut( hrn, true );
3094 // if we just removed the last node from an allocation
3095 // site, it should be taken out of the ReachGraph's list
3096 AllocSite as = hrn.getAllocSite();
3097 if( !hasNodesOf( as ) ) {
3098 allocSites.remove( as );
3104 protected boolean hasNodesOf( AllocSite as ) {
3105 if( id2hrn.containsKey( as.getSummary() ) ) {
3109 for( int i = 0; i < allocationDepth; ++i ) {
3110 if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
3118 ////////////////////////////////////////////////////
3120 // This global sweep is an optional step to prune
3121 // reachability sets that are not internally
3122 // consistent with the global graph. It should be
3123 // invoked after strong updates or method calls.
3125 ////////////////////////////////////////////////////
3126 public void globalSweep() {
3128 // boldB is part of the phase 1 sweep
3129 // it has an in-context table and an out-of-context table
3130 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3131 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3133 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3134 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3136 // visit every heap region to initialize alphaNew and betaNew,
3137 // and make a map of every hrnID to the source nodes it should
3138 // propagate forward from. In-context flagged hrnID's propagate
3139 // from only the in-context node they name, but out-of-context
3140 // ID's may propagate from several out-of-context nodes
3141 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3142 new Hashtable< Integer, Set<HeapRegionNode> >();
3144 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3145 new Hashtable< Integer, Set<HeapRegionNode> >();
3148 Iterator itrHrns = id2hrn.entrySet().iterator();
3149 while( itrHrns.hasNext() ) {
3150 Map.Entry me = (Map.Entry) itrHrns.next();
3151 Integer hrnID = (Integer) me.getKey();
3152 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3154 // assert that this node and incoming edges have clean alphaNew
3155 // and betaNew sets, respectively
3156 assert rsetEmpty.equals( hrn.getAlphaNew() );
3158 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3159 while( itrRers.hasNext() ) {
3160 RefEdge edge = itrRers.next();
3161 assert rsetEmpty.equals( edge.getBetaNew() );
3164 // make a mapping of IDs to heap regions they propagate from
3165 if( hrn.isFlagged() ) {
3166 assert !hrn.isOutOfContext();
3167 assert !icID2srcs.containsKey( hrn.getID() );
3169 // in-context flagged node IDs simply propagate from the
3171 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3173 icID2srcs.put( hrn.getID(), srcs );
3176 if( hrn.isOutOfContext() ) {
3177 assert !hrn.isFlagged();
3179 // the reachability states on an out-of-context
3180 // node are not really important (combinations of
3181 // IDs or arity)--what matters is that the states
3182 // specify which nodes this out-of-context node
3183 // stands in for. For example, if the state [17?, 19*]
3184 // appears on the ooc node, it may serve as a source
3185 // for node 17? and a source for node 19.
3186 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3187 while( stateItr.hasNext() ) {
3188 ReachState state = stateItr.next();
3190 Iterator<ReachTuple> rtItr = state.iterator();
3191 while( rtItr.hasNext() ) {
3192 ReachTuple rt = rtItr.next();
3193 assert rt.isOutOfContext();
3195 Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
3196 if( srcs == null ) {
3197 srcs = new HashSet<HeapRegionNode>();
3200 oocID2srcs.put( rt.getHrnID(), srcs );
3206 // calculate boldB for all hrnIDs identified by the above
3207 // node traversal, propagating from every source
3208 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3211 Set<HeapRegionNode> srcs;
3214 if( !icID2srcs.isEmpty() ) {
3215 Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
3216 hrnID = (Integer) me.getKey();
3217 srcs = (Set<HeapRegionNode>) me.getValue();
3219 icID2srcs.remove( hrnID );
3222 assert !oocID2srcs.isEmpty();
3224 Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
3225 hrnID = (Integer) me.getKey();
3226 srcs = (Set<HeapRegionNode>) me.getValue();
3228 oocID2srcs.remove( hrnID );
3232 Hashtable<RefEdge, ReachSet> boldB_f =
3233 new Hashtable<RefEdge, ReachSet>();
3235 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3237 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3238 while( hrnItr.hasNext() ) {
3239 HeapRegionNode hrn = hrnItr.next();
3241 assert workSetEdges.isEmpty();
3243 // initial boldB_f constraints
3244 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3245 while( itrRees.hasNext() ) {
3246 RefEdge edge = itrRees.next();
3248 assert !boldB_f.containsKey( edge );
3249 boldB_f.put( edge, edge.getBeta() );
3251 assert !workSetEdges.contains( edge );
3252 workSetEdges.add( edge );
3255 // enforce the boldB_f constraint at edges until we reach a fixed point
3256 while( !workSetEdges.isEmpty() ) {
3257 RefEdge edge = workSetEdges.iterator().next();
3258 workSetEdges.remove( edge );
3260 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3261 while( itrPrime.hasNext() ) {
3262 RefEdge edgePrime = itrPrime.next();
3264 ReachSet prevResult = boldB_f.get( edgePrime );
3265 ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
3269 if( prevResult == null ||
3270 Canonical.unionORpreds( prevResult,
3271 intersection ).size()
3275 if( prevResult == null ) {
3276 boldB_f.put( edgePrime,
3277 Canonical.unionORpreds( edgePrime.getBeta(),
3282 boldB_f.put( edgePrime,
3283 Canonical.unionORpreds( prevResult,
3288 workSetEdges.add( edgePrime );
3295 boldBic.put( hrnID, boldB_f );
3297 boldBooc.put( hrnID, boldB_f );
3302 // use boldB to prune hrnIDs from alpha states that are impossible
3303 // and propagate the differences backwards across edges
3304 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3306 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3307 new Hashtable<RefEdge, ChangeSet>();
3310 itrHrns = id2hrn.entrySet().iterator();
3311 while( itrHrns.hasNext() ) {
3312 Map.Entry me = (Map.Entry) itrHrns.next();
3313 Integer hrnID = (Integer) me.getKey();
3314 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3316 // out-of-context nodes don't participate in the
3317 // global sweep, they serve as sources for the pass
3319 if( hrn.isOutOfContext() ) {
3323 // the inherent states of a region are the exception
3324 // to removal as the global sweep prunes
3325 ReachTuple rtException = ReachTuple.factory( hrnID,
3326 !hrn.isSingleObject(),
3327 ReachTuple.ARITY_ONE,
3328 false // out-of-context
3331 ChangeSet cts = ChangeSet.factory();
3333 // mark hrnIDs for removal
3334 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3335 while( stateItr.hasNext() ) {
3336 ReachState stateOld = stateItr.next();
3338 ReachState markedHrnIDs = ReachState.factory();
3340 Iterator<ReachTuple> rtItr = stateOld.iterator();
3341 while( rtItr.hasNext() ) {
3342 ReachTuple rtOld = rtItr.next();
3344 // never remove the inherent hrnID from a flagged region
3345 // because it is trivially satisfied
3346 if( hrn.isFlagged() ) {
3347 if( rtOld == rtException ) {
3352 // does boldB allow this hrnID?
3353 boolean foundState = false;
3354 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3355 while( incidentEdgeItr.hasNext() ) {
3356 RefEdge incidentEdge = incidentEdgeItr.next();
3358 Hashtable<RefEdge, ReachSet> B;
3359 if( rtOld.isOutOfContext() ) {
3360 B = boldBooc.get( rtOld.getHrnID() );
3363 if( !id2hrn.containsKey( rtOld.getHrnID() ) ) {
3364 // let symbols not in the graph get pruned
3368 B = boldBic.get( rtOld.getHrnID() );
3372 ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3373 if( boldB_rtOld_incident != null &&
3374 boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
3382 markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3386 // if there is nothing marked, just move on
3387 if( markedHrnIDs.isEmpty() ) {
3388 hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3395 // remove all marked hrnIDs and establish a change set that should
3396 // propagate backwards over edges from this node
3397 ReachState statePruned = ReachState.factory();
3398 rtItr = stateOld.iterator();
3399 while( rtItr.hasNext() ) {
3400 ReachTuple rtOld = rtItr.next();
3402 if( !markedHrnIDs.containsTuple( rtOld ) ) {
3403 statePruned = Canonical.add( statePruned, rtOld );
3406 assert !stateOld.equals( statePruned );
3408 hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3412 ChangeTuple ct = ChangeTuple.factory( stateOld,
3415 cts = Canonical.add( cts, ct );
3418 // throw change tuple set on all incident edges
3419 if( !cts.isEmpty() ) {
3420 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3421 while( incidentEdgeItr.hasNext() ) {
3422 RefEdge incidentEdge = incidentEdgeItr.next();
3424 edgesForPropagation.add( incidentEdge );
3426 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3427 edgePlannedChanges.put( incidentEdge, cts );
3429 edgePlannedChanges.put(
3431 Canonical.union( edgePlannedChanges.get( incidentEdge ),
3440 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3442 propagateTokensOverEdges( edgesForPropagation,
3446 // at the end of the 1st phase reference edges have
3447 // beta, betaNew that correspond to beta and betaR
3449 // commit beta<-betaNew, so beta=betaR and betaNew
3450 // will represent the beta' calculation in 2nd phase
3452 // commit alpha<-alphaNew because it won't change
3453 HashSet<RefEdge> res = new HashSet<RefEdge>();
3455 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3456 while( nodeItr.hasNext() ) {
3457 HeapRegionNode hrn = nodeItr.next();
3459 // as mentioned above, out-of-context nodes only serve
3460 // as sources of reach states for the sweep, not part
3462 if( hrn.isOutOfContext() ) {
3463 assert hrn.getAlphaNew().equals( rsetEmpty );
3465 hrn.applyAlphaNew();
3468 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3469 while( itrRes.hasNext() ) {
3470 res.add( itrRes.next() );
3476 Iterator<RefEdge> edgeItr = res.iterator();
3477 while( edgeItr.hasNext() ) {
3478 RefEdge edge = edgeItr.next();
3479 HeapRegionNode hrn = edge.getDst();
3481 // commit results of last phase
3482 if( edgesUpdated.contains( edge ) ) {
3483 edge.applyBetaNew();
3486 // compute intial condition of 2nd phase
3487 edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3493 // every edge in the graph is the initial workset
3494 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3495 while( !edgeWorkSet.isEmpty() ) {
3496 RefEdge edgePrime = edgeWorkSet.iterator().next();
3497 edgeWorkSet.remove( edgePrime );
3499 RefSrcNode rsn = edgePrime.getSrc();
3500 if( !(rsn instanceof HeapRegionNode) ) {
3503 HeapRegionNode hrn = (HeapRegionNode) rsn;
3505 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3506 while( itrEdge.hasNext() ) {
3507 RefEdge edge = itrEdge.next();
3509 ReachSet prevResult = edge.getBetaNew();
3510 assert prevResult != null;
3512 ReachSet intersection =
3513 Canonical.intersection( edge.getBeta(),
3514 edgePrime.getBetaNew()
3517 if( Canonical.unionORpreds( prevResult,
3524 Canonical.unionORpreds( prevResult,
3528 edgeWorkSet.add( edge );
3533 // commit beta' (beta<-betaNew)
3534 edgeItr = res.iterator();
3535 while( edgeItr.hasNext() ) {
3536 edgeItr.next().applyBetaNew();
3541 // a useful assertion for debugging:
3542 // every in-context tuple on any edge or
3543 // any node should name a node that is
3544 // part of the graph
3545 public boolean inContextTuplesInGraph() {
3547 Iterator hrnItr = id2hrn.entrySet().iterator();
3548 while( hrnItr.hasNext() ) {
3549 Map.Entry me = (Map.Entry) hrnItr.next();
3550 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3553 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3554 while( stateItr.hasNext() ) {
3555 ReachState state = stateItr.next();
3557 Iterator<ReachTuple> rtItr = state.iterator();
3558 while( rtItr.hasNext() ) {
3559 ReachTuple rt = rtItr.next();
3561 if( !rt.isOutOfContext() ) {
3562 if( !id2hrn.containsKey( rt.getHrnID() ) ) {
3563 System.out.println( rt.getHrnID()+" is missing" );
3571 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3572 while( edgeItr.hasNext() ) {
3573 RefEdge edge = edgeItr.next();
3575 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3576 while( stateItr.hasNext() ) {
3577 ReachState state = stateItr.next();
3579 Iterator<ReachTuple> rtItr = state.iterator();
3580 while( rtItr.hasNext() ) {
3581 ReachTuple rt = rtItr.next();
3583 if( !rt.isOutOfContext() ) {
3584 if( !id2hrn.containsKey( rt.getHrnID() ) ) {
3585 System.out.println( rt.getHrnID()+" is missing" );
3598 // another useful assertion for debugging
3599 public boolean noEmptyReachSetsInGraph() {
3601 Iterator hrnItr = id2hrn.entrySet().iterator();
3602 while( hrnItr.hasNext() ) {
3603 Map.Entry me = (Map.Entry) hrnItr.next();
3604 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3606 if( !hrn.isOutOfContext() &&
3608 hrn.getAlpha().isEmpty()
3610 System.out.println( "!!! "+hrn+" has an empty ReachSet !!!" );
3614 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3615 while( edgeItr.hasNext() ) {
3616 RefEdge edge = edgeItr.next();
3618 if( edge.getBeta().isEmpty() ) {
3619 System.out.println( "!!! "+edge+" has an empty ReachSet !!!" );
3629 public boolean everyReachStateWTrue() {
3631 Iterator hrnItr = id2hrn.entrySet().iterator();
3632 while( hrnItr.hasNext() ) {
3633 Map.Entry me = (Map.Entry) hrnItr.next();
3634 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3637 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3638 while( stateItr.hasNext() ) {
3639 ReachState state = stateItr.next();
3641 if( !state.getPreds().equals( predsTrue ) ) {
3647 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3648 while( edgeItr.hasNext() ) {
3649 RefEdge edge = edgeItr.next();
3651 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3652 while( stateItr.hasNext() ) {
3653 ReachState state = stateItr.next();
3655 if( !state.getPreds().equals( predsTrue ) ) {
3668 ////////////////////////////////////////////////////
3669 // in merge() and equals() methods the suffix A
3670 // represents the passed in graph and the suffix
3671 // B refers to the graph in this object
3672 // Merging means to take the incoming graph A and
3673 // merge it into B, so after the operation graph B
3674 // is the final result.
3675 ////////////////////////////////////////////////////
3676 protected void merge( ReachGraph rg ) {
3683 mergeRefEdges ( rg );
3684 mergeAllocSites( rg );
3685 mergeAccessibleSet( rg );
3688 protected void mergeNodes( ReachGraph rg ) {
3690 // start with heap region nodes
3691 Set sA = rg.id2hrn.entrySet();
3692 Iterator iA = sA.iterator();
3693 while( iA.hasNext() ) {
3694 Map.Entry meA = (Map.Entry) iA.next();
3695 Integer idA = (Integer) meA.getKey();
3696 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3698 // if this graph doesn't have a node the
3699 // incoming graph has, allocate it
3700 if( !id2hrn.containsKey( idA ) ) {
3701 HeapRegionNode hrnB = hrnA.copy();
3702 id2hrn.put( idA, hrnB );
3705 // otherwise this is a node present in both graphs
3706 // so make the new reachability set a union of the
3707 // nodes' reachability sets
3708 HeapRegionNode hrnB = id2hrn.get( idA );
3709 hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3714 hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3721 if( !hrnA.equals( hrnB ) ) {
3722 rg.writeGraph( "graphA" );
3723 this.writeGraph( "graphB" );
3724 throw new Error( "flagged not matching" );
3732 // now add any variable nodes that are in graph B but
3734 sA = rg.td2vn.entrySet();
3736 while( iA.hasNext() ) {
3737 Map.Entry meA = (Map.Entry) iA.next();
3738 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3739 VariableNode lnA = (VariableNode) meA.getValue();
3741 // if the variable doesn't exist in B, allocate and add it
3742 VariableNode lnB = getVariableNodeFromTemp( tdA );
3746 protected void mergeRefEdges( ReachGraph rg ) {
3748 // between heap regions
3749 Set sA = rg.id2hrn.entrySet();
3750 Iterator iA = sA.iterator();
3751 while( iA.hasNext() ) {
3752 Map.Entry meA = (Map.Entry) iA.next();
3753 Integer idA = (Integer) meA.getKey();
3754 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3756 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3757 while( heapRegionsItrA.hasNext() ) {
3758 RefEdge edgeA = heapRegionsItrA.next();
3759 HeapRegionNode hrnChildA = edgeA.getDst();
3760 Integer idChildA = hrnChildA.getID();
3762 // at this point we know an edge in graph A exists
3763 // idA -> idChildA, does this exist in B?
3764 assert id2hrn.containsKey( idA );
3765 HeapRegionNode hrnB = id2hrn.get( idA );
3766 RefEdge edgeToMerge = null;
3768 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3769 while( heapRegionsItrB.hasNext() &&
3770 edgeToMerge == null ) {
3772 RefEdge edgeB = heapRegionsItrB.next();
3773 HeapRegionNode hrnChildB = edgeB.getDst();
3774 Integer idChildB = hrnChildB.getID();
3776 // don't use the RefEdge.equals() here because
3777 // we're talking about existence between graphs,
3778 // not intragraph equal
3779 if( idChildB.equals( idChildA ) &&
3780 edgeB.typeAndFieldEquals( edgeA ) ) {
3782 edgeToMerge = edgeB;
3786 // if the edge from A was not found in B,
3788 if( edgeToMerge == null ) {
3789 assert id2hrn.containsKey( idChildA );
3790 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3791 edgeToMerge = edgeA.copy();
3792 edgeToMerge.setSrc( hrnB );
3793 edgeToMerge.setDst( hrnChildB );
3794 addRefEdge( hrnB, hrnChildB, edgeToMerge );
3796 // otherwise, the edge already existed in both graphs
3797 // so merge their reachability sets
3799 // just replace this beta set with the union
3800 assert edgeToMerge != null;
3801 edgeToMerge.setBeta(
3802 Canonical.unionORpreds( edgeToMerge.getBeta(),
3806 edgeToMerge.setPreds(
3807 Canonical.join( edgeToMerge.getPreds(),
3811 edgeToMerge.setTaints(
3812 Canonical.union( edgeToMerge.getTaints(),
3820 // and then again from variable nodes
3821 sA = rg.td2vn.entrySet();
3823 while( iA.hasNext() ) {
3824 Map.Entry meA = (Map.Entry) iA.next();
3825 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3826 VariableNode vnA = (VariableNode) meA.getValue();
3828 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3829 while( heapRegionsItrA.hasNext() ) {
3830 RefEdge edgeA = heapRegionsItrA.next();
3831 HeapRegionNode hrnChildA = edgeA.getDst();
3832 Integer idChildA = hrnChildA.getID();
3834 // at this point we know an edge in graph A exists
3835 // tdA -> idChildA, does this exist in B?
3836 assert td2vn.containsKey( tdA );
3837 VariableNode vnB = td2vn.get( tdA );
3838 RefEdge edgeToMerge = null;
3840 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3841 while( heapRegionsItrB.hasNext() &&
3842 edgeToMerge == null ) {
3844 RefEdge edgeB = heapRegionsItrB.next();
3845 HeapRegionNode hrnChildB = edgeB.getDst();
3846 Integer idChildB = hrnChildB.getID();
3848 // don't use the RefEdge.equals() here because
3849 // we're talking about existence between graphs
3850 if( idChildB.equals( idChildA ) &&
3851 edgeB.typeAndFieldEquals( edgeA ) ) {
3853 edgeToMerge = edgeB;
3857 // if the edge from A was not found in B,
3859 if( edgeToMerge == null ) {
3860 assert id2hrn.containsKey( idChildA );
3861 HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3862 edgeToMerge = edgeA.copy();
3863 edgeToMerge.setSrc( vnB );
3864 edgeToMerge.setDst( hrnChildB );
3865 addRefEdge( vnB, hrnChildB, edgeToMerge );
3867 // otherwise, the edge already existed in both graphs
3868 // so merge their reachability sets
3870 // just replace this beta set with the union
3871 edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3875 edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3879 edgeToMerge.setTaints(
3880 Canonical.union( edgeToMerge.getTaints(),
3889 protected void mergeAllocSites( ReachGraph rg ) {
3890 allocSites.addAll( rg.allocSites );
3893 protected void mergeAccessibleSet( ReachGraph rg ){
3894 // inaccesible status is prior to accessible status
3896 Set<TempDescriptor> varsToMerge=rg.getAccessibleVar();
3897 Set<TempDescriptor> varsRemoved=new HashSet<TempDescriptor>();
3899 for (Iterator iterator = accessibleVars.iterator(); iterator.hasNext();) {
3900 TempDescriptor accessibleVar = (TempDescriptor) iterator.next();
3901 if(!varsToMerge.contains(accessibleVar)){
3902 varsRemoved.add(accessibleVar);
3906 accessibleVars.removeAll(varsRemoved);
3912 static boolean dbgEquals = false;
3915 // it is necessary in the equals() member functions
3916 // to "check both ways" when comparing the data
3917 // structures of two graphs. For instance, if all
3918 // edges between heap region nodes in graph A are
3919 // present and equal in graph B it is not sufficient
3920 // to say the graphs are equal. Consider that there
3921 // may be edges in graph B that are not in graph A.
3922 // the only way to know that all edges in both graphs
3923 // are equally present is to iterate over both data
3924 // structures and compare against the other graph.
3925 public boolean equals( ReachGraph rg ) {
3929 System.out.println( "rg is null" );
3934 if( !areHeapRegionNodesEqual( rg ) ) {
3936 System.out.println( "hrn not equal" );
3941 if( !areVariableNodesEqual( rg ) ) {
3943 System.out.println( "vars not equal" );
3948 if( !areRefEdgesEqual( rg ) ) {
3950 System.out.println( "edges not equal" );
3955 if( !accessibleVars.equals( rg.accessibleVars) ){
3959 // if everything is equal up to this point,
3960 // assert that allocSites is also equal--
3961 // this data is redundant but kept for efficiency
3962 assert allocSites.equals( rg.allocSites );
3968 protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3970 if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3974 if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3981 static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3983 Set sA = rgA.id2hrn.entrySet();
3984 Iterator iA = sA.iterator();
3985 while( iA.hasNext() ) {
3986 Map.Entry meA = (Map.Entry) iA.next();
3987 Integer idA = (Integer) meA.getKey();
3988 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3990 if( !rgB.id2hrn.containsKey( idA ) ) {
3994 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3995 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
4003 protected boolean areVariableNodesEqual( ReachGraph rg ) {
4005 if( !areallVNinAalsoinBandequal( this, rg ) ) {
4009 if( !areallVNinAalsoinBandequal( rg, this ) ) {
4016 static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
4018 Set sA = rgA.td2vn.entrySet();
4019 Iterator iA = sA.iterator();
4020 while( iA.hasNext() ) {
4021 Map.Entry meA = (Map.Entry) iA.next();
4022 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4024 if( !rgB.td2vn.containsKey( tdA ) ) {
4033 protected boolean areRefEdgesEqual( ReachGraph rg ) {
4034 if( !areallREinAandBequal( this, rg ) ) {
4038 if( !areallREinAandBequal( rg, this ) ) {
4045 static protected boolean areallREinAandBequal( ReachGraph rgA,
4048 // check all the heap region->heap region edges
4049 Set sA = rgA.id2hrn.entrySet();
4050 Iterator iA = sA.iterator();
4051 while( iA.hasNext() ) {
4052 Map.Entry meA = (Map.Entry) iA.next();
4053 Integer idA = (Integer) meA.getKey();
4054 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4056 // we should have already checked that the same
4057 // heap regions exist in both graphs
4058 assert rgB.id2hrn.containsKey( idA );
4060 if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
4064 // then check every edge in B for presence in A, starting
4065 // from the same parent HeapRegionNode
4066 HeapRegionNode hrnB = rgB.id2hrn.get( idA );
4068 if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
4073 // then check all the variable->heap region edges
4074 sA = rgA.td2vn.entrySet();
4076 while( iA.hasNext() ) {
4077 Map.Entry meA = (Map.Entry) iA.next();
4078 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4079 VariableNode vnA = (VariableNode) meA.getValue();
4081 // we should have already checked that the same
4082 // label nodes exist in both graphs
4083 assert rgB.td2vn.containsKey( tdA );
4085 if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
4089 // then check every edge in B for presence in A, starting
4090 // from the same parent VariableNode
4091 VariableNode vnB = rgB.td2vn.get( tdA );
4093 if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
4102 static protected boolean areallREfromAequaltoB( ReachGraph rgA,
4106 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4107 while( itrA.hasNext() ) {
4108 RefEdge edgeA = itrA.next();
4109 HeapRegionNode hrnChildA = edgeA.getDst();
4110 Integer idChildA = hrnChildA.getID();
4112 assert rgB.id2hrn.containsKey( idChildA );
4114 // at this point we know an edge in graph A exists
4115 // rnA -> idChildA, does this exact edge exist in B?
4116 boolean edgeFound = false;
4118 RefSrcNode rnB = null;
4119 if( rnA instanceof HeapRegionNode ) {
4120 HeapRegionNode hrnA = (HeapRegionNode) rnA;
4121 rnB = rgB.id2hrn.get( hrnA.getID() );
4123 VariableNode vnA = (VariableNode) rnA;
4124 rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
4127 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4128 while( itrB.hasNext() ) {
4129 RefEdge edgeB = itrB.next();
4130 HeapRegionNode hrnChildB = edgeB.getDst();
4131 Integer idChildB = hrnChildB.getID();
4133 if( idChildA.equals( idChildB ) &&
4134 edgeA.typeAndFieldEquals( edgeB ) ) {
4136 // there is an edge in the right place with the right field,
4137 // but do they have the same attributes?
4138 if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
4139 edgeA.equalsPreds( edgeB )
4155 // can be used to assert monotonicity
4156 static public boolean isNoSmallerThan( ReachGraph rgA,
4159 //System.out.println( "*** Asking if A is no smaller than B ***" );
4162 Iterator iA = rgA.id2hrn.entrySet().iterator();
4163 while( iA.hasNext() ) {
4164 Map.Entry meA = (Map.Entry) iA.next();
4165 Integer idA = (Integer) meA.getKey();
4166 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4168 if( !rgB.id2hrn.containsKey( idA ) ) {
4169 System.out.println( " regions smaller" );
4173 //HeapRegionNode hrnB = rgB.id2hrn.get( idA );
4174 /* NOT EQUALS, NO SMALLER THAN!
4175 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
4176 System.out.println( " regions smaller" );
4182 // this works just fine, no smaller than
4183 if( !areallVNinAalsoinBandequal( rgA, rgB ) ) {
4184 System.out.println( " vars smaller:" );
4185 System.out.println( " A:"+rgA.td2vn.keySet() );
4186 System.out.println( " B:"+rgB.td2vn.keySet() );
4191 iA = rgA.id2hrn.entrySet().iterator();
4192 while( iA.hasNext() ) {
4193 Map.Entry meA = (Map.Entry) iA.next();
4194 Integer idA = (Integer) meA.getKey();
4195 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4197 Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4198 while( reItr.hasNext() ) {
4199 RefEdge edgeA = reItr.next();
4200 RefSrcNode rsnA = edgeA.getSrc();
4202 // we already checked that nodes were present
4203 HeapRegionNode hrnB = rgB.id2hrn.get( hrnA.getID() );
4204 assert hrnB != null;
4207 if( rsnA instanceof VariableNode ) {
4208 VariableNode vnA = (VariableNode) rsnA;
4209 rsnB = rgB.td2vn.get( vnA.getTempDescriptor() );
4212 HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4213 rsnB = rgB.id2hrn.get( hrnSrcA.getID() );
4215 assert rsnB != null;
4217 RefEdge edgeB = rsnB.getReferenceTo( hrnB,
4221 if( edgeB == null ) {
4222 System.out.println( " edges smaller:" );
4226 // REMEMBER, IS NO SMALLER THAN
4228 System.out.println( " edges smaller" );
4244 // this analysis no longer has the "match anything"
4245 // type which was represented by null
4246 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
4247 TypeDescriptor td2 ) {
4251 if( td1.isNull() ) {
4254 if( td2.isNull() ) {
4257 return typeUtil.mostSpecific( td1, td2 );
4260 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
4262 TypeDescriptor td3 ) {
4264 return mostSpecificType( td1,
4265 mostSpecificType( td2, td3 )
4269 protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
4272 TypeDescriptor td4 ) {
4274 return mostSpecificType( mostSpecificType( td1, td2 ),
4275 mostSpecificType( td3, td4 )
4279 protected boolean isSuperiorType( TypeDescriptor possibleSuper,
4280 TypeDescriptor possibleChild ) {
4281 assert possibleSuper != null;
4282 assert possibleChild != null;
4284 if( possibleSuper.isNull() ||
4285 possibleChild.isNull() ) {
4289 return typeUtil.isSuperorType( possibleSuper, possibleChild );
4293 protected boolean hasMatchingField( HeapRegionNode src,
4296 TypeDescriptor tdSrc = src.getType();
4297 assert tdSrc != null;
4299 if( tdSrc.isArray() ) {
4300 TypeDescriptor td = edge.getType();
4303 TypeDescriptor tdSrcDeref = tdSrc.dereference();
4304 assert tdSrcDeref != null;
4306 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
4310 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
4313 // if it's not a class, it doesn't have any fields to match
4314 if( !tdSrc.isClass() ) {
4318 ClassDescriptor cd = tdSrc.getClassDesc();
4319 while( cd != null ) {
4320 Iterator fieldItr = cd.getFields();
4322 while( fieldItr.hasNext() ) {
4323 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4325 if( fd.getType().equals( edge.getType() ) &&
4326 fd.getSymbol().equals( edge.getField() ) ) {
4331 cd = cd.getSuperDesc();
4334 // otherwise it is a class with fields
4335 // but we didn't find a match
4339 protected boolean hasMatchingType( RefEdge edge,
4340 HeapRegionNode dst ) {
4342 // if the region has no type, matches everything
4343 TypeDescriptor tdDst = dst.getType();
4344 assert tdDst != null;
4346 // if the type is not a class or an array, don't
4347 // match because primitives are copied, no aliases
4348 ClassDescriptor cdDst = tdDst.getClassDesc();
4349 if( cdDst == null && !tdDst.isArray() ) {
4353 // if the edge type is null, it matches everything
4354 TypeDescriptor tdEdge = edge.getType();
4355 assert tdEdge != null;
4357 return typeUtil.isSuperorType( tdEdge, tdDst );
4362 // the default signature for quick-and-dirty debugging
4363 public void writeGraph( String graphName ) {
4364 writeGraph( graphName,
4365 true, // write labels
4366 true, // label select
4367 true, // prune garbage
4368 false, // hide reachability
4369 true, // hide subset reachability
4370 true, // hide predicates
4371 true, // hide edge taints
4372 null // in-context boundary
4376 public void writeGraph( String graphName,
4377 boolean writeLabels,
4378 boolean labelSelect,
4379 boolean pruneGarbage,
4380 boolean hideReachability,
4381 boolean hideSubsetReachability,
4382 boolean hidePredicates,
4383 boolean hideEdgeTaints
4385 writeGraph( graphName,
4390 hideSubsetReachability,
4396 public void writeGraph( String graphName,
4397 boolean writeLabels,
4398 boolean labelSelect,
4399 boolean pruneGarbage,
4400 boolean hideReachability,
4401 boolean hideSubsetReachability,
4402 boolean hidePredicates,
4403 boolean hideEdgeTaints,
4404 Set<Integer> callerNodeIDsCopiedToCallee
4408 // remove all non-word characters from the graph name so
4409 // the filename and identifier in dot don't cause errors
4410 graphName = graphName.replaceAll( "[\\W]", "" );
4413 new BufferedWriter( new FileWriter( graphName+".dot" ) );
4415 bw.write( "digraph "+graphName+" {\n" );
4418 // this is an optional step to form the callee-reachable
4419 // "cut-out" into a DOT cluster for visualization
4420 if( callerNodeIDsCopiedToCallee != null ) {
4422 bw.write( " subgraph cluster0 {\n" );
4423 bw.write( " color=blue;\n" );
4425 Iterator i = id2hrn.entrySet().iterator();
4426 while( i.hasNext() ) {
4427 Map.Entry me = (Map.Entry) i.next();
4428 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4430 if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
4433 hrn.toStringDOT( hideReachability,
4434 hideSubsetReachability,
4444 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4446 // then visit every heap region node
4447 Iterator i = id2hrn.entrySet().iterator();
4448 while( i.hasNext() ) {
4449 Map.Entry me = (Map.Entry) i.next();
4450 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4452 // only visit nodes worth writing out--for instance
4453 // not every node at an allocation is referenced
4454 // (think of it as garbage-collected), etc.
4455 if( !pruneGarbage ||
4456 hrn.isOutOfContext() ||
4457 (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4460 if( !visited.contains( hrn ) ) {
4461 traverseHeapRegionNodes( hrn,
4466 hideSubsetReachability,
4469 callerNodeIDsCopiedToCallee );
4474 bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
4477 // then visit every label node, useful for debugging
4479 i = td2vn.entrySet().iterator();
4480 while( i.hasNext() ) {
4481 Map.Entry me = (Map.Entry) i.next();
4482 VariableNode vn = (VariableNode) me.getValue();
4485 String labelStr = vn.getTempDescriptorString();
4486 if( labelStr.startsWith( "___temp" ) ||
4487 labelStr.startsWith( "___dst" ) ||
4488 labelStr.startsWith( "___srctmp" ) ||
4489 labelStr.startsWith( "___neverused" )
4495 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4496 while( heapRegionsItr.hasNext() ) {
4497 RefEdge edge = heapRegionsItr.next();
4498 HeapRegionNode hrn = edge.getDst();
4500 if( !visited.contains( hrn ) ) {
4501 traverseHeapRegionNodes( hrn,
4506 hideSubsetReachability,
4509 callerNodeIDsCopiedToCallee );
4512 bw.write( " "+vn.toString()+
4513 " -> "+hrn.toString()+
4514 edge.toStringDOT( hideReachability,
4515 hideSubsetReachability,
4527 } catch( IOException e ) {
4528 throw new Error( "Error writing out DOT graph "+graphName );
4533 traverseHeapRegionNodes( HeapRegionNode hrn,
4536 Set<HeapRegionNode> visited,
4537 boolean hideReachability,
4538 boolean hideSubsetReachability,
4539 boolean hidePredicates,
4540 boolean hideEdgeTaints,
4541 Set<Integer> callerNodeIDsCopiedToCallee
4542 ) throws java.io.IOException {
4544 if( visited.contains( hrn ) ) {
4549 // if we're drawing the callee-view subgraph, only
4550 // write out the node info if it hasn't already been
4552 if( callerNodeIDsCopiedToCallee == null ||
4553 !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
4557 hrn.toStringDOT( hideReachability,
4558 hideSubsetReachability,
4563 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4564 while( childRegionsItr.hasNext() ) {
4565 RefEdge edge = childRegionsItr.next();
4566 HeapRegionNode hrnChild = edge.getDst();
4568 if( callerNodeIDsCopiedToCallee != null &&
4569 (edge.getSrc() instanceof HeapRegionNode) ) {
4570 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4571 if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
4572 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4574 bw.write( " "+hrn.toString()+
4575 " -> "+hrnChild.toString()+
4576 edge.toStringDOT( hideReachability,
4577 hideSubsetReachability,
4582 } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
4583 callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4585 bw.write( " "+hrn.toString()+
4586 " -> "+hrnChild.toString()+
4587 edge.toStringDOT( hideReachability,
4588 hideSubsetReachability,
4591 ",color=blue,style=dashed" )+
4594 bw.write( " "+hrn.toString()+
4595 " -> "+hrnChild.toString()+
4596 edge.toStringDOT( hideReachability,
4597 hideSubsetReachability,
4604 bw.write( " "+hrn.toString()+
4605 " -> "+hrnChild.toString()+
4606 edge.toStringDOT( hideReachability,
4607 hideSubsetReachability,
4614 traverseHeapRegionNodes( hrnChild,
4619 hideSubsetReachability,
4622 callerNodeIDsCopiedToCallee );
4630 public Set<HeapRegionNode> findCommonReachableNodes( ReachSet proofOfSharing ) {
4632 Set<HeapRegionNode> exhibitProofState =
4633 new HashSet<HeapRegionNode>();
4635 Iterator hrnItr = id2hrn.entrySet().iterator();
4636 while( hrnItr.hasNext() ) {
4637 Map.Entry me = (Map.Entry) hrnItr.next();
4638 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4640 ReachSet intersection =
4641 Canonical.intersection( proofOfSharing,
4644 if( !intersection.isEmpty() ) {
4645 assert !hrn.isOutOfContext();
4646 exhibitProofState.add( hrn );
4650 return exhibitProofState;
4654 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4655 HeapRegionNode hrn2) {
4656 assert hrn1 != null;
4657 assert hrn2 != null;
4659 assert !hrn1.isOutOfContext();
4660 assert !hrn2.isOutOfContext();
4662 assert belongsToThis( hrn1 );
4663 assert belongsToThis( hrn2 );
4665 assert !hrn1.getID().equals( hrn2.getID() );
4668 // then get the various tokens for these heap regions
4670 ReachTuple.factory( hrn1.getID(),
4671 !hrn1.isSingleObject(), // multi?
4672 ReachTuple.ARITY_ONE,
4675 ReachTuple h1star = null;
4676 if( !hrn1.isSingleObject() ) {
4678 ReachTuple.factory( hrn1.getID(),
4679 !hrn1.isSingleObject(),
4680 ReachTuple.ARITY_ZEROORMORE,
4685 ReachTuple.factory( hrn2.getID(),
4686 !hrn2.isSingleObject(),
4687 ReachTuple.ARITY_ONE,
4690 ReachTuple h2star = null;
4691 if( !hrn2.isSingleObject() ) {
4693 ReachTuple.factory( hrn2.getID(),
4694 !hrn2.isSingleObject(),
4695 ReachTuple.ARITY_ZEROORMORE,
4699 // then get the merged beta of all out-going edges from these heap
4702 ReachSet beta1 = ReachSet.factory();
4703 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4704 while (itrEdge.hasNext()) {
4705 RefEdge edge = itrEdge.next();
4706 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4709 ReachSet beta2 = ReachSet.factory();
4710 itrEdge = hrn2.iteratorToReferencees();
4711 while (itrEdge.hasNext()) {
4712 RefEdge edge = itrEdge.next();
4713 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4716 ReachSet proofOfSharing = ReachSet.factory();
4719 Canonical.unionORpreds( proofOfSharing,
4720 beta1.getStatesWithBoth( h1, h2 )
4723 Canonical.unionORpreds( proofOfSharing,
4724 beta2.getStatesWithBoth( h1, h2 )
4727 if( !hrn1.isSingleObject() ) {
4729 Canonical.unionORpreds( proofOfSharing,
4730 beta1.getStatesWithBoth( h1star, h2 )
4733 Canonical.unionORpreds( proofOfSharing,
4734 beta2.getStatesWithBoth( h1star, h2 )
4738 if( !hrn2.isSingleObject() ) {
4740 Canonical.unionORpreds( proofOfSharing,
4741 beta1.getStatesWithBoth( h1, h2star )
4744 Canonical.unionORpreds( proofOfSharing,
4745 beta2.getStatesWithBoth( h1, h2star )
4749 if( !hrn1.isSingleObject() &&
4750 !hrn2.isSingleObject()
4753 Canonical.unionORpreds( proofOfSharing,
4754 beta1.getStatesWithBoth( h1star, h2star )
4757 Canonical.unionORpreds( proofOfSharing,
4758 beta2.getStatesWithBoth( h1star, h2star )
4762 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4763 if( !proofOfSharing.isEmpty() ) {
4764 common = findCommonReachableNodes( proofOfSharing );
4765 if( !DISABLE_STRONG_UPDATES &&
4766 !DISABLE_GLOBAL_SWEEP
4768 assert !common.isEmpty();
4775 // this version of the above method checks whether there is sharing
4776 // among the objects in a summary node
4777 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4779 assert hrn.isNewSummary();
4780 assert !hrn.isOutOfContext();
4781 assert belongsToThis( hrn );
4784 ReachTuple.factory( hrn.getID(),
4786 ReachTuple.ARITY_ZEROORMORE,
4789 // then get the merged beta of all out-going edges from
4792 ReachSet beta = ReachSet.factory();
4793 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4794 while (itrEdge.hasNext()) {
4795 RefEdge edge = itrEdge.next();
4796 beta = Canonical.unionORpreds(beta, edge.getBeta());
4799 ReachSet proofOfSharing = ReachSet.factory();
4802 Canonical.unionORpreds( proofOfSharing,
4803 beta.getStatesWithBoth( hstar, hstar )
4806 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4807 if( !proofOfSharing.isEmpty() ) {
4808 common = findCommonReachableNodes( proofOfSharing );
4809 if( !DISABLE_STRONG_UPDATES &&
4810 !DISABLE_GLOBAL_SWEEP
4812 assert !common.isEmpty();
4820 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4821 Integer paramIndex1,
4822 Integer paramIndex2) {
4824 // get parameter's heap regions
4825 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4826 assert this.hasVariable( paramTemp1 );
4827 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
4830 if( !(paramVar1.getNumReferencees() == 1) ) {
4831 System.out.println( "\n fm="+fm+"\n param="+paramTemp1 );
4832 writeGraph( "whatup" );
4836 assert paramVar1.getNumReferencees() == 1;
4837 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
4838 HeapRegionNode hrnParam1 = paramEdge1.getDst();
4840 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4841 assert this.hasVariable( paramTemp2 );
4842 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
4844 if( !(paramVar2.getNumReferencees() == 1) ) {
4845 System.out.println( "\n fm="+fm+"\n param="+paramTemp2 );
4846 writeGraph( "whatup" );
4849 assert paramVar2.getNumReferencees() == 1;
4850 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
4851 HeapRegionNode hrnParam2 = paramEdge2.getDst();
4853 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4854 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4859 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4863 // get parameter's heap regions
4864 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4865 assert this.hasVariable( paramTemp );
4866 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
4867 assert paramVar.getNumReferencees() == 1;
4868 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
4869 HeapRegionNode hrnParam = paramEdge.getDst();
4872 HeapRegionNode hrnSummary=null;
4873 if(id2hrn.containsKey(as.getSummary())){
4874 // if summary node doesn't exist, ignore this case
4875 hrnSummary = id2hrn.get(as.getSummary());
4876 assert hrnSummary != null;
4879 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4880 if(hrnSummary!=null){
4881 common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4884 // check for other nodes
4885 for (int i = 0; i < as.getAllocationDepth(); ++i) {
4887 assert id2hrn.containsKey(as.getIthOldest(i));
4888 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4889 assert hrnIthOldest != null;
4891 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4898 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4901 // get summary node 1's alpha
4902 Integer idSum1 = as1.getSummary();
4903 HeapRegionNode hrnSum1=null;
4904 if(id2hrn.containsKey(idSum1)){
4905 hrnSum1 = id2hrn.get(idSum1);
4908 // get summary node 2's alpha
4909 Integer idSum2 = as2.getSummary();
4910 HeapRegionNode hrnSum2=null;
4911 if(id2hrn.containsKey(idSum2)){
4912 hrnSum2 = id2hrn.get(idSum2);
4915 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4916 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2){
4917 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4921 // ask if objects from this summary share among each other
4922 common.addAll(mayReachSharedObjects(hrnSum1));
4925 // check sum2 against alloc1 nodes
4927 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4928 Integer idI1 = as1.getIthOldest(i);
4929 assert id2hrn.containsKey(idI1);
4930 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4931 assert hrnI1 != null;
4932 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4935 // also ask if objects from this summary share among each other
4936 common.addAll(mayReachSharedObjects(hrnSum2));
4939 // check sum1 against alloc2 nodes
4940 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4941 Integer idI2 = as2.getIthOldest(i);
4942 assert id2hrn.containsKey(idI2);
4943 HeapRegionNode hrnI2 = id2hrn.get(idI2);
4944 assert hrnI2 != null;
4947 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4950 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4951 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4952 Integer idI1 = as1.getIthOldest(j);
4954 // if these are the same site, don't look for the same token, no
4956 // different tokens of the same site could alias together though
4957 if (idI1.equals(idI2)) {
4961 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4963 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
4970 public void addAccessibleVar(TempDescriptor td){
4971 accessibleVars.add(td);
4974 public Set<TempDescriptor> getAccessibleVar(){
4975 return accessibleVars;
4978 public void clearAccessibleVarSet(){
4979 accessibleVars.clear();