1 package Analysis.Disjoint;
5 import Util.UtilAlgorithms;
9 public class ReachGraph {
11 protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
13 // some frequently used reachability constants
14 protected static final ReachState rstateEmpty = new ReachState().makeCanonical();
15 protected static final ReachSet rsetEmpty = new ReachSet().makeCanonical();
16 protected static final ReachSet rsetWithEmptyState = new ReachSet( rstateEmpty ).makeCanonical();
18 public Hashtable<Integer, HeapRegionNode> id2hrn;
19 public Hashtable<TempDescriptor, VariableNode > td2vn;
21 public HashSet<AllocSite> allocSites;
24 // use to disable improvements for comparison
25 protected static final boolean DISABLE_STRONG_UPDATES = false;
26 protected static final boolean DISABLE_GLOBAL_SWEEP = false;
28 protected static int allocationDepth = -1;
29 protected static TypeUtil typeUtil = null;
30 protected static boolean debugCallMap = false;
31 protected static int debugCallMapCount = 0;
32 protected static String debugCallee = null;
33 protected static String debugCaller = null;
39 id2hrn = new Hashtable<Integer, HeapRegionNode>();
40 td2vn = new Hashtable<TempDescriptor, VariableNode >();
42 allocSites = new HashSet<AllocSite>();
47 // temp descriptors are globally unique and maps to
48 // exactly one variable node, easy
49 protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
52 if( !td2vn.containsKey( td ) ) {
53 td2vn.put( td, new VariableNode( td ) );
56 return td2vn.get( td );
60 // the reason for this method is to have the option
61 // of creating new heap regions with specific IDs, or
62 // duplicating heap regions with specific IDs (especially
63 // in the merge() operation) or to create new heap
64 // regions with a new unique ID
65 protected HeapRegionNode
66 createNewHeapRegionNode( Integer id,
67 boolean isSingleObject,
74 String globalIdentifier ) {
76 boolean markForAnalysis = isFlagged;
78 TypeDescriptor typeToUse = null;
79 if( allocSite != null ) {
80 typeToUse = allocSite.getType();
85 if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
86 markForAnalysis = true;
90 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
94 if( markForAnalysis ) {
102 alpha = new ReachSet(
103 new ReachState().makeCanonical()
108 HeapRegionNode hrn = new HeapRegionNode( id,
117 id2hrn.put( id, hrn );
123 ////////////////////////////////////////////////
125 // Low-level referencee and referencer methods
127 // These methods provide the lowest level for
128 // creating references between ownership nodes
129 // and handling the details of maintaining both
130 // list of referencers and referencees.
132 ////////////////////////////////////////////////
133 protected void addRefEdge(RefSrcNode referencer,
134 HeapRegionNode referencee,
136 assert referencer != null;
137 assert referencee != null;
139 assert edge.getSrc() == referencer;
140 assert edge.getDst() == referencee;
142 referencer.addReferencee(edge);
143 referencee.addReferencer(edge);
146 protected void removeRefEdge(RefEdge e) {
147 removeRefEdge(e.getSrc(),
153 protected void removeRefEdge(RefSrcNode referencer,
154 HeapRegionNode referencee,
157 assert referencer != null;
158 assert referencee != null;
160 RefEdge edge = referencer.getReferenceTo(referencee,
164 assert edge == referencee.getReferenceFrom(referencer,
168 // int oldTaint=edge.getTaintIdentifier();
169 // if(referencer instanceof HeapRegionNode){
170 // depropagateTaintIdentifier((HeapRegionNode)referencer,oldTaint,new HashSet<HeapRegionNode>());
173 referencer.removeReferencee(edge);
174 referencee.removeReferencer(edge);
177 protected void clearRefEdgesFrom(RefSrcNode referencer,
181 assert referencer != null;
183 // get a copy of the set to iterate over, otherwise
184 // we will be trying to take apart the set as we
185 // are iterating over it, which won't work
186 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
187 while( i.hasNext() ) {
188 RefEdge edge = i.next();
191 (edge.typeEquals( type ) && edge.fieldEquals( field ))
194 HeapRegionNode referencee = edge.getDst();
196 removeRefEdge(referencer,
204 protected void clearRefEdgesTo(HeapRegionNode referencee,
208 assert referencee != null;
210 // get a copy of the set to iterate over, otherwise
211 // we will be trying to take apart the set as we
212 // are iterating over it, which won't work
213 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
214 while( i.hasNext() ) {
215 RefEdge edge = i.next();
218 (edge.typeEquals( type ) && edge.fieldEquals( field ))
221 RefSrcNode referencer = edge.getSrc();
223 removeRefEdge(referencer,
232 ////////////////////////////////////////////////////
234 // Assignment Operation Methods
236 // These methods are high-level operations for
237 // modeling program assignment statements using
238 // the low-level reference create/remove methods
241 // The destination in an assignment statement is
242 // going to have new references. The method of
243 // determining the references depends on the type
244 // of the FlatNode assignment and the predicates
245 // of the nodes and edges involved.
247 ////////////////////////////////////////////////////
249 public void nullifyDeadVars( Set<TempDescriptor> liveIn ) {
251 // make a set of the temps that are out of scope, don't
252 // consider them when nullifying dead in-scope variables
253 Set<TempDescriptor> outOfScope = new HashSet<TempDescriptor>();
254 outOfScope.add( tdReturn );
255 outOfScope.add( tdAliasBlob );
256 outOfScope.addAll( paramIndex2tdQ.values() );
257 outOfScope.addAll( paramIndex2tdR.values() );
259 Iterator varItr = td2vn.entrySet().iterator();
260 while( varItr.hasNext() ) {
261 Map.Entry me = (Map.Entry) varItr.next();
262 TempDescriptor td = (TempDescriptor) me.getKey();
263 VariableNode ln = (VariableNode) me.getValue();
265 // if this variable is not out-of-scope or live
266 // in graph, nullify its references to anything
267 if( !outOfScope.contains( td ) &&
268 !liveIn.contains( td )
270 clearRefEdgesFrom( ln, null, null, true );
276 public void assignTempXEqualToTempY( TempDescriptor x,
278 assignTempXEqualToCastedTempY( x, y, null );
281 public void assignTempXEqualToCastedTempY( TempDescriptor x,
283 TypeDescriptor tdCast ) {
285 VariableNode lnX = getVariableNodeFromTemp( x );
286 VariableNode lnY = getVariableNodeFromTemp( y );
288 clearRefEdgesFrom( lnX, null, null, true );
290 // note it is possible that the types of temps in the
291 // flat node to analyze will reveal that some typed
292 // edges in the reachability graph are impossible
293 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
295 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
296 while( itrYhrn.hasNext() ) {
297 RefEdge edgeY = itrYhrn.next();
298 HeapRegionNode referencee = edgeY.getDst();
299 RefEdge edgeNew = edgeY.copy();
301 if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
302 impossibleEdges.add( edgeY );
306 edgeNew.setSrc( lnX );
308 edgeNew.setType( mostSpecificType( y.getType(),
315 edgeNew.setField( null );
317 addRefEdge( lnX, referencee, edgeNew );
320 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
321 while( itrImp.hasNext() ) {
322 RefEdge edgeImp = itrImp.next();
323 removeRefEdge( edgeImp );
328 public void assignTempXEqualToTempYFieldF( TempDescriptor x,
330 FieldDescriptor f ) {
331 VariableNode lnX = getVariableNodeFromTemp( x );
332 VariableNode lnY = getVariableNodeFromTemp( y );
334 clearRefEdgesFrom( lnX, null, null, true );
336 // note it is possible that the types of temps in the
337 // flat node to analyze will reveal that some typed
338 // edges in the reachability graph are impossible
339 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
341 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
342 while( itrYhrn.hasNext() ) {
343 RefEdge edgeY = itrYhrn.next();
344 HeapRegionNode hrnY = edgeY.getDst();
345 ReachSet betaY = edgeY.getBeta();
347 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
348 while( itrHrnFhrn.hasNext() ) {
349 RefEdge edgeHrn = itrHrnFhrn.next();
350 HeapRegionNode hrnHrn = edgeHrn.getDst();
351 ReachSet betaHrn = edgeHrn.getBeta();
353 // prune edges that are not a matching field
354 if( edgeHrn.getType() != null &&
355 !edgeHrn.getField().equals( f.getSymbol() )
360 // check for impossible edges
361 if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
362 impossibleEdges.add( edgeHrn );
366 TypeDescriptor tdNewEdge =
367 mostSpecificType( edgeHrn.getType(),
371 RefEdge edgeNew = new RefEdge( lnX,
376 betaY.intersection( betaHrn )
379 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnHrn);
380 edgeNew.setTaintIdentifier(newTaintIdentifier);
382 addRefEdge( lnX, hrnHrn, edgeNew );
386 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
387 while( itrImp.hasNext() ) {
388 RefEdge edgeImp = itrImp.next();
389 removeRefEdge( edgeImp );
392 // anytime you might remove edges between heap regions
393 // you must global sweep to clean up broken reachability
394 if( !impossibleEdges.isEmpty() ) {
395 if( !DISABLE_GLOBAL_SWEEP ) {
402 public void assignTempXFieldFEqualToTempY( TempDescriptor x,
406 VariableNode lnX = getVariableNodeFromTemp( x );
407 VariableNode lnY = getVariableNodeFromTemp( y );
409 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
410 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
412 // note it is possible that the types of temps in the
413 // flat node to analyze will reveal that some typed
414 // edges in the reachability graph are impossible
415 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
417 // first look for possible strong updates and remove those edges
418 boolean strongUpdate = false;
420 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
421 while( itrXhrn.hasNext() ) {
422 RefEdge edgeX = itrXhrn.next();
423 HeapRegionNode hrnX = edgeX.getDst();
425 // we can do a strong update here if one of two cases holds
427 f != DisjointAnalysis.getArrayField( f.getType() ) &&
428 ( (hrnX.getNumReferencers() == 1) || // case 1
429 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
432 if( !DISABLE_STRONG_UPDATES ) {
434 clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
439 // then do all token propagation
440 itrXhrn = lnX.iteratorToReferencees();
441 while( itrXhrn.hasNext() ) {
442 RefEdge edgeX = itrXhrn.next();
443 HeapRegionNode hrnX = edgeX.getDst();
444 ReachSet betaX = edgeX.getBeta();
445 ReachSet R = hrnX.getAlpha().intersection( edgeX.getBeta() );
447 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
448 while( itrYhrn.hasNext() ) {
449 RefEdge edgeY = itrYhrn.next();
450 HeapRegionNode hrnY = edgeY.getDst();
451 ReachSet O = edgeY.getBeta();
453 // check for impossible edges
454 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
455 impossibleEdges.add( edgeY );
459 // propagate tokens over nodes starting from hrnSrc, and it will
460 // take care of propagating back up edges from any touched nodes
461 ChangeSet Cy = O.unionUpArityToChangeSet( R );
462 propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
465 // then propagate back just up the edges from hrn
466 ChangeSet Cx = R.unionUpArityToChangeSet(O);
467 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
469 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
470 new Hashtable<RefEdge, ChangeSet>();
472 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
473 while( referItr.hasNext() ) {
474 RefEdge edgeUpstream = referItr.next();
475 todoEdges.add( edgeUpstream );
476 edgePlannedChanges.put( edgeUpstream, Cx );
479 propagateTokensOverEdges( todoEdges,
486 // apply the updates to reachability
487 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
488 while( nodeItr.hasNext() ) {
489 nodeItr.next().applyAlphaNew();
492 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
493 while( edgeItr.hasNext() ) {
494 edgeItr.next().applyBetaNew();
498 // then go back through and add the new edges
499 itrXhrn = lnX.iteratorToReferencees();
500 while( itrXhrn.hasNext() ) {
501 RefEdge edgeX = itrXhrn.next();
502 HeapRegionNode hrnX = edgeX.getDst();
504 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
505 while( itrYhrn.hasNext() ) {
506 RefEdge edgeY = itrYhrn.next();
507 HeapRegionNode hrnY = edgeY.getDst();
509 // skip impossible edges here, we already marked them
510 // when computing reachability propagations above
511 if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
515 // prepare the new reference edge hrnX.f -> hrnY
516 TypeDescriptor tdNewEdge =
517 mostSpecificType( y.getType(),
522 RefEdge edgeNew = new RefEdge( hrnX,
527 edgeY.getBeta().pruneBy( hrnX.getAlpha() )
530 // look to see if an edge with same field exists
531 // and merge with it, otherwise just add the edge
532 RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
536 if( edgeExisting != null ) {
537 edgeExisting.setBeta(
538 edgeExisting.getBeta().union( edgeNew.getBeta() )
541 if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){
542 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY);
543 edgeExisting.unionTaintIdentifier(newTaintIdentifier);
545 // a new edge here cannot be reflexive, so existing will
546 // always be also not reflexive anymore
547 edgeExisting.setIsInitialParam( false );
550 if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){
551 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY);
552 edgeNew.setTaintIdentifier(newTaintIdentifier);
554 //currently, taint isn't propagated through the chain of refrences
555 //propagateTaintIdentifier(hrnX,newTaintIdentifier,new HashSet<HeapRegionNode>());
557 addRefEdge( hrnX, hrnY, edgeNew );
562 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
563 while( itrImp.hasNext() ) {
564 RefEdge edgeImp = itrImp.next();
565 removeRefEdge( edgeImp );
568 // if there was a strong update, make sure to improve
569 // reachability with a global sweep
570 if( strongUpdate || !impossibleEdges.isEmpty() ) {
571 if( !DISABLE_GLOBAL_SWEEP ) {
578 // the parameter model is to use a single-object heap region
579 // for the primary parameter, and a multiple-object heap
580 // region for the secondary objects reachable through the
581 // primary object, if necessary
582 public void assignTempEqualToParamAlloc( TempDescriptor td,
584 Integer paramIndex, FlatMethod fm ) {
587 TypeDescriptor typeParam = td.getType();
588 assert typeParam != null;
590 // either the parameter is an array or a class to be in this method
591 assert typeParam.isArray() || typeParam.isClass();
593 // discover some info from the param type and use it below
594 // to get parameter model as precise as we can
595 boolean createSecondaryRegion = false;
596 Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
597 Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
599 // there might be an element reference for array types
600 if( typeParam.isArray() ) {
601 // only bother with this if the dereferenced type can
602 // affect reachability
603 TypeDescriptor typeDeref = typeParam.dereference();
604 if( !typeDeref.isImmutable() || typeDeref.isArray() ) {
605 primary2secondaryFields.add(
606 DisjointAnalysis.getArrayField( typeDeref )
608 createSecondaryRegion = true;
610 // also handle a special case where an array of objects
611 // can point back to the array, which is an object!
612 if( typeParam.toPrettyString().equals( "Object[]" ) &&
613 typeDeref.toPrettyString().equals( "Object" ) ) {
615 primary2primaryFields.add(
616 DisjointAnalysis.getArrayField( typeDeref )
622 // there might be member references for class types
623 if( typeParam.isClass() ) {
624 ClassDescriptor cd = typeParam.getClassDesc();
625 while( cd != null ) {
627 Iterator fieldItr = cd.getFields();
628 while( fieldItr.hasNext() ) {
630 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
631 TypeDescriptor typeField = fd.getType();
632 assert typeField != null;
634 if( !typeField.isImmutable() || typeField.isArray() ) {
635 primary2secondaryFields.add( fd );
636 createSecondaryRegion = true;
639 if( typeUtil.isSuperorType( typeField, typeParam ) ) {
640 primary2primaryFields.add( fd );
644 cd = cd.getSuperDesc();
649 // now build everything we need
650 VariableNode lnParam = getVariableNodeFromTemp( td );
651 HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
652 true, // single object?
655 true, // is a parameter?
657 null, // allocation site
658 null, // reachability set
659 "param"+paramIndex+" obj",
660 generateUniqueIdentifier(fm,paramIndex,"P"));
662 parameterTemps.add( td );
663 parameterLabels.add( lnParam );
666 // this is a non-program-accessible label that picks up beta
667 // info to be used for fixing a caller of this method
668 TempDescriptor tdParamQ = new TempDescriptor( td+qString );
669 paramIndex2tdQ.put( paramIndex, tdParamQ );
670 VariableNode lnParamQ = getVariableNodeFromTemp( tdParamQ );
672 outOfScopeTemps.add( tdParamQ );
673 outOfScopeLabels.add( lnParamQ );
675 // keep track of heap regions that were created for
676 // parameter labels, the index of the parameter they
677 // are for is important when resolving method calls
678 Integer newPrimaryID = hrnPrimary.getID();
679 assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
680 Set<Integer> s = new HashSet<Integer>();
682 idPrimary2paramIndexSet.put( newPrimaryID, s );
683 paramIndex2idPrimary.put( paramIndex, newPrimaryID );
685 ReachTuple ttPrimary = new ReachTuple( newPrimaryID,
686 false, // multi-object
687 ReachTuple.ARITY_ONE ).makeCanonical();
690 HeapRegionNode hrnSecondary = null;
691 Integer newSecondaryID = null;
692 ReachTuple ttSecondary = null;
693 TempDescriptor tdParamR = null;
694 VariableNode lnParamR = null;
696 if( createSecondaryRegion ) {
697 tdParamR = new TempDescriptor( td+rString );
698 paramIndex2tdR.put( paramIndex, tdParamR );
699 lnParamR = getVariableNodeFromTemp( tdParamR );
701 outOfScopeTemps.add( tdParamR );
702 outOfScopeLabels.add( lnParamR );
704 hrnSecondary = createNewHeapRegionNode( null, // id or null to generate a new one
705 false, // single object?
708 true, // is a parameter?
710 null, // allocation site
711 null, // reachability set
712 "param"+paramIndex+" reachable",
713 generateUniqueIdentifier(fm,paramIndex,"S"));
715 newSecondaryID = hrnSecondary.getID();
716 assert !idSecondary2paramIndexSet.containsKey( newSecondaryID );
717 Set<Integer> s2 = new HashSet<Integer>();
718 s2.add( paramIndex );
719 idSecondary2paramIndexSet.put( newSecondaryID, s2 );
720 paramIndex2idSecondary.put( paramIndex, newSecondaryID );
723 ttSecondary = new ReachTuple( newSecondaryID,
724 true, // multi-object
725 ReachTuple.ARITY_ONE ).makeCanonical();
728 // use a beta that has everything and put it all over the
729 // parameter model, then use a global sweep later to fix
730 // it up, since parameters can have different shapes
731 ReachState tts0 = new ReachState( ttPrimary ).makeCanonical();
733 if( createSecondaryRegion ) {
734 ReachState tts1 = new ReachState( ttSecondary ).makeCanonical();
735 ReachState tts2 = new ReachState( ttPrimary ).makeCanonical().union( ttSecondary );
736 betaSoup = ReachSet.factory( tts0 ).union( tts1 ).union( tts2 );
738 betaSoup = ReachSet.factory( tts0 );
741 RefEdge edgeFromLabel =
742 new RefEdge( lnParam, // src
746 false, // special param initial (not needed on label->node)
747 betaSoup ); // reachability
748 edgeFromLabel.tainedBy(paramIndex);
749 addRefEdge( lnParam, hrnPrimary, edgeFromLabel );
751 RefEdge edgeFromLabelQ =
752 new RefEdge( lnParamQ, // src
756 false, // special param initial (not needed on label->node)
757 betaSoup ); // reachability
758 edgeFromLabelQ.tainedBy(paramIndex);
759 addRefEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
761 RefEdge edgeSecondaryReflexive;
762 if( createSecondaryRegion ) {
763 edgeSecondaryReflexive =
764 new RefEdge( hrnSecondary, // src
766 null, // match all types
767 null, // match all fields
768 true, // special param initial
769 betaSoup ); // reachability
770 addRefEdge( hrnSecondary, hrnSecondary, edgeSecondaryReflexive );
772 RefEdge edgeSecondary2Primary =
773 new RefEdge( hrnSecondary, // src
775 null, // match all types
776 null, // match all fields
777 true, // special param initial
778 betaSoup ); // reachability
779 addRefEdge( hrnSecondary, hrnPrimary, edgeSecondary2Primary );
781 RefEdge edgeFromLabelR =
782 new RefEdge( lnParamR, // src
786 false, // special param initial (not needed on label->node)
787 betaSoup ); // reachability
788 edgeFromLabelR.tainedBy(paramIndex);
789 addRefEdge( lnParamR, hrnSecondary, edgeFromLabelR );
792 Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
793 while( fieldItr.hasNext() ) {
794 FieldDescriptor fd = fieldItr.next();
796 RefEdge edgePrimaryReflexive =
797 new RefEdge( hrnPrimary, // src
799 fd.getType(), // type
800 fd.getSymbol(), // field
801 true, // special param initial
802 betaSoup ); // reachability
803 addRefEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive );
806 fieldItr = primary2secondaryFields.iterator();
807 while( fieldItr.hasNext() ) {
808 FieldDescriptor fd = fieldItr.next();
810 RefEdge edgePrimary2Secondary =
811 new RefEdge( hrnPrimary, // src
813 fd.getType(), // type
814 fd.getSymbol(), // field
815 true, // special param initial
816 betaSoup ); // reachability
817 addRefEdge( hrnPrimary, hrnSecondary, edgePrimary2Secondary );
822 public void makeAliasedParamHeapRegionNode(FlatMethod fm) {
824 VariableNode lnBlob = getVariableNodeFromTemp( tdAliasBlob );
826 outOfScopeTemps.add( tdAliasBlob );
827 outOfScopeLabels.add( lnBlob );
829 HeapRegionNode hrn = createNewHeapRegionNode( null, // id or null to generate a new one
830 false, // single object?
833 true, // is a parameter?
835 null, // allocation site
836 null, // reachability set
838 generateUniqueIdentifier(fm,0,"A"));
841 ReachSet beta = new ReachSet( new ReachTuple( hrn.getID(),
843 ReachTuple.ARITY_ONE).makeCanonical()
846 RefEdge edgeFromLabel =
847 new RefEdge( lnBlob, hrn, null, null, false, beta );
849 RefEdge edgeReflexive =
850 new RefEdge( hrn, hrn, null, null, true, beta );
852 addRefEdge( lnBlob, hrn, edgeFromLabel );
853 addRefEdge( hrn, hrn, edgeReflexive );
857 public void assignTempEqualToAliasedParam( TempDescriptor tdParam,
858 Integer paramIndex, FlatMethod fm ) {
859 assert tdParam != null;
861 TypeDescriptor typeParam = tdParam.getType();
862 assert typeParam != null;
864 VariableNode lnParam = getVariableNodeFromTemp( tdParam );
865 VariableNode lnAliased = getVariableNodeFromTemp( tdAliasBlob );
867 parameterTemps.add( tdParam );
868 parameterLabels.add( lnParam );
870 // this is a non-program-accessible label that picks up beta
871 // info to be used for fixing a caller of this method
872 TempDescriptor tdParamQ = new TempDescriptor( tdParam+qString );
873 TempDescriptor tdParamR = new TempDescriptor( tdParam+rString );
875 paramIndex2tdQ.put( paramIndex, tdParamQ );
876 paramIndex2tdR.put( paramIndex, tdParamR );
878 VariableNode lnParamQ = getVariableNodeFromTemp( tdParamQ );
879 VariableNode lnParamR = getVariableNodeFromTemp( tdParamR );
881 outOfScopeTemps.add( tdParamR );
882 outOfScopeLabels.add( lnParamR );
883 outOfScopeTemps.add( tdParamQ );
884 outOfScopeLabels.add( lnParamQ );
886 // the lnAliased should always only reference one node, and that
887 // heap region node is the aliased param blob
888 assert lnAliased.getNumReferencees() == 1;
889 HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
890 Integer idAliased = hrnAliasBlob.getID();
893 ReachTuple ttAliased = new ReachTuple( idAliased,
894 true, // multi-object
895 ReachTuple.ARITY_ONE ).makeCanonical();
898 HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
899 true, // single object?
902 true, // is a parameter?
904 null, // allocation site
905 null, // reachability set
906 "param"+paramIndex+" obj",
907 generateUniqueIdentifier(fm, paramIndex.intValue(), "P"));
909 Integer newPrimaryID = hrnPrimary.getID();
910 assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
911 Set<Integer> s1 = new HashSet<Integer>();
912 s1.add( paramIndex );
913 idPrimary2paramIndexSet.put( newPrimaryID, s1 );
914 paramIndex2idPrimary.put( paramIndex, newPrimaryID );
916 Set<Integer> s2 = idSecondary2paramIndexSet.get( idAliased );
918 s2 = new HashSet<Integer>();
920 s2.add( paramIndex );
921 idSecondary2paramIndexSet.put( idAliased, s2 );
922 paramIndex2idSecondary.put( paramIndex, idAliased );
926 ReachTuple ttPrimary = new ReachTuple( newPrimaryID,
927 false, // multi-object
928 ReachTuple.ARITY_ONE ).makeCanonical();
931 ReachState tts0 = new ReachState( ttPrimary ).makeCanonical();
932 ReachState tts1 = new ReachState( ttAliased ).makeCanonical();
933 ReachState tts2 = new ReachState( ttPrimary ).makeCanonical().union( ttAliased );
934 ReachSet betaSoup = ReachSet.factory( tts0 ).union( tts1 ).union( tts2 );
937 RefEdge edgeFromLabel =
938 new RefEdge( lnParam, // src
942 false, // special param initial (not needed on label->node)
943 betaSoup ); // reachability
944 edgeFromLabel.tainedBy(paramIndex);
945 addRefEdge( lnParam, hrnPrimary, edgeFromLabel );
947 RefEdge edgeFromLabelQ =
948 new RefEdge( lnParamQ, // src
952 false, // special param initial (not needed on label->node)
953 betaSoup ); // reachability
954 edgeFromLabelQ.tainedBy(paramIndex);
955 addRefEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
957 RefEdge edgeAliased2Primary =
958 new RefEdge( hrnAliasBlob, // src
960 null, // match all types
961 null, // match all fields
962 true, // special param initial
963 betaSoup ); // reachability
964 addRefEdge( hrnAliasBlob, hrnPrimary, edgeAliased2Primary );
966 RefEdge edgeFromLabelR =
967 new RefEdge( lnParamR, // src
971 false, // special param initial (not needed on label->node)
972 betaSoup ); // reachability
973 edgeFromLabelR.tainedBy(paramIndex);
974 addRefEdge( lnParamR, hrnAliasBlob, edgeFromLabelR );
978 public void addParam2ParamAliasEdges( FlatMethod fm,
979 Set<Integer> aliasedParamIndices ) {
981 VariableNode lnAliased = getVariableNodeFromTemp( tdAliasBlob );
983 // the lnAliased should always only reference one node, and that
984 // heap region node is the aliased param blob
985 assert lnAliased.getNumReferencees() == 1;
986 HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
987 Integer idAliased = hrnAliasBlob.getID();
990 ReachTuple ttAliased = new ReachTuple( idAliased,
991 true, // multi-object
992 ReachTuple.ARITY_ONE ).makeCanonical();
995 Iterator<Integer> apItrI = aliasedParamIndices.iterator();
996 while( apItrI.hasNext() ) {
997 Integer i = apItrI.next();
998 TempDescriptor tdParamI = fm.getParameter( i );
999 TypeDescriptor typeI = tdParamI.getType();
1000 VariableNode lnParamI = getVariableNodeFromTemp( tdParamI );
1002 Integer idPrimaryI = paramIndex2idPrimary.get( i );
1003 assert idPrimaryI != null;
1004 HeapRegionNode primaryI = id2hrn.get( idPrimaryI );
1005 assert primaryI != null;
1007 ReachTuple ttPrimaryI = new ReachTuple( idPrimaryI,
1008 false, // multi-object
1009 ReachTuple.ARITY_ONE ).makeCanonical();
1011 ReachState ttsI = new ReachState( ttPrimaryI ).makeCanonical();
1012 ReachState ttsA = new ReachState( ttAliased ).makeCanonical();
1013 ReachState ttsIA = new ReachState( ttPrimaryI ).makeCanonical().union( ttAliased );
1014 ReachSet betaSoup = ReachSet.factory( ttsI ).union( ttsA ).union( ttsIA );
1017 // calculate whether fields of this aliased parameter are able to
1018 // reference its own primary object, the blob, or other parameter's
1020 Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
1021 Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
1023 // there might be an element reference for array types
1024 if( typeI.isArray() ) {
1025 // only bother with this if the dereferenced type can
1026 // affect reachability
1027 TypeDescriptor typeDeref = typeI.dereference();
1031 /////////////////////////////////////////////////////////////
1032 // NOTE! For the KMeans benchmark a parameter of type float
1033 // array, which has an immutable dereferenced type, is causing
1034 // this assertion to fail. I'm commenting it out for now which
1035 // is safe, because it allows aliasing where no aliasing can occur,
1036 // so it can only get a worse-but-not-wrong answer. FIX!
1037 /////////////////////////////////////////////////////////////
1038 // for this parameter to be aliased the following must be true
1039 //assert !typeDeref.isImmutable() || typeDeref.isArray();
1043 primary2secondaryFields.add(
1044 DisjointAnalysis.getArrayField( typeDeref )
1047 // also handle a special case where an array of objects
1048 // can point back to the array, which is an object!
1049 if( typeI .toPrettyString().equals( "Object[]" ) &&
1050 typeDeref.toPrettyString().equals( "Object" ) ) {
1051 primary2primaryFields.add(
1052 DisjointAnalysis.getArrayField( typeDeref )
1057 // there might be member references for class types
1058 if( typeI.isClass() ) {
1059 ClassDescriptor cd = typeI.getClassDesc();
1060 while( cd != null ) {
1062 Iterator fieldItr = cd.getFields();
1063 while( fieldItr.hasNext() ) {
1065 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
1066 TypeDescriptor typeField = fd.getType();
1067 assert typeField != null;
1069 if( !typeField.isImmutable() || typeField.isArray() ) {
1070 primary2secondaryFields.add( fd );
1073 if( typeUtil.isSuperorType( typeField, typeI ) ) {
1074 primary2primaryFields.add( fd );
1078 cd = cd.getSuperDesc();
1082 Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
1083 while( fieldItr.hasNext() ) {
1084 FieldDescriptor fd = fieldItr.next();
1086 RefEdge edgePrimaryReflexive =
1087 new RefEdge( primaryI, // src
1089 fd.getType(), // type
1090 fd.getSymbol(), // field
1091 true, // special param initial
1092 betaSoup ); // reachability
1093 addRefEdge( primaryI, primaryI, edgePrimaryReflexive );
1096 fieldItr = primary2secondaryFields.iterator();
1097 while( fieldItr.hasNext() ) {
1098 FieldDescriptor fd = fieldItr.next();
1099 TypeDescriptor typeField = fd.getType();
1100 assert typeField != null;
1102 RefEdge edgePrimary2Secondary =
1103 new RefEdge( primaryI, // src
1104 hrnAliasBlob, // dst
1105 fd.getType(), // type
1106 fd.getSymbol(), // field
1107 true, // special param initial
1108 betaSoup ); // reachability
1109 addRefEdge( primaryI, hrnAliasBlob, edgePrimary2Secondary );
1111 // ask whether these fields might match any of the other aliased
1112 // parameters and make those edges too
1113 Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
1114 while( apItrJ.hasNext() ) {
1115 Integer j = apItrJ.next();
1116 TempDescriptor tdParamJ = fm.getParameter( j );
1117 TypeDescriptor typeJ = tdParamJ.getType();
1119 if( !i.equals( j ) && typeUtil.isSuperorType( typeField, typeJ ) ) {
1121 Integer idPrimaryJ = paramIndex2idPrimary.get( j );
1122 assert idPrimaryJ != null;
1123 HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
1124 assert primaryJ != null;
1126 ReachTuple ttPrimaryJ = new ReachTuple( idPrimaryJ,
1127 false, // multi-object
1128 ReachTuple.ARITY_ONE ).makeCanonical();
1130 ReachState ttsJ = new ReachState( ttPrimaryJ ).makeCanonical();
1131 ReachState ttsIJ = ttsI.union( ttsJ );
1132 ReachState ttsAJ = ttsA.union( ttsJ );
1133 ReachState ttsIAJ = ttsIA.union( ttsJ );
1134 ReachSet betaSoupWJ = ReachSet.factory( ttsJ ).union( ttsIJ ).union( ttsAJ ).union( ttsIAJ );
1136 RefEdge edgePrimaryI2PrimaryJ =
1137 new RefEdge( primaryI, // src
1139 fd.getType(), // type
1140 fd.getSymbol(), // field
1141 true, // special param initial
1142 betaSoupWJ ); // reachability
1143 addRefEdge( primaryI, primaryJ, edgePrimaryI2PrimaryJ );
1149 // look at whether aliased parameters i and j can
1150 // possibly be the same primary object, add edges
1151 Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
1152 while( apItrJ.hasNext() ) {
1153 Integer j = apItrJ.next();
1154 TempDescriptor tdParamJ = fm.getParameter( j );
1155 TypeDescriptor typeJ = tdParamJ.getType();
1156 VariableNode lnParamJ = getVariableNodeFromTemp( tdParamJ );
1158 if( !i.equals( j ) && typeUtil.isSuperorType( typeI, typeJ ) ) {
1160 Integer idPrimaryJ = paramIndex2idPrimary.get( j );
1161 assert idPrimaryJ != null;
1162 HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
1163 assert primaryJ != null;
1165 RefEdge lnJ2PrimaryJ = lnParamJ.getReferenceTo( primaryJ,
1168 assert lnJ2PrimaryJ != null;
1170 RefEdge lnI2PrimaryJ = lnJ2PrimaryJ.copy();
1171 lnI2PrimaryJ.setSrc( lnParamI );
1172 lnI2PrimaryJ.setType( tdParamI.getType() );
1173 lnI2PrimaryJ.tainedBy(new Integer(j));
1174 addRefEdge( lnParamI, primaryJ, lnI2PrimaryJ );
1180 public void prepareParamTokenMaps( FlatMethod fm ) {
1182 // always add the bogus mappings that are used to
1183 // rewrite "with respect to no parameter"
1184 paramTokenPrimary2paramIndex.put( bogusToken, bogusIndex );
1185 paramIndex2paramTokenPrimary.put( bogusIndex, bogusToken );
1187 paramTokenSecondary2paramIndex.put( bogusToken, bogusIndex );
1188 paramIndex2paramTokenSecondary.put( bogusIndex, bogusToken );
1189 paramTokenSecondaryPlus2paramIndex.put( bogusTokenPlus, bogusIndex );
1190 paramIndex2paramTokenSecondaryPlus.put( bogusIndex, bogusTokenPlus );
1191 paramTokenSecondaryStar2paramIndex.put( bogusTokenStar, bogusIndex );
1192 paramIndex2paramTokenSecondaryStar.put( bogusIndex, bogusTokenStar );
1194 for( int i = 0; i < fm.numParameters(); ++i ) {
1195 Integer paramIndex = new Integer( i );
1197 // immutable objects have no primary regions
1198 if( paramIndex2idPrimary.containsKey( paramIndex ) ) {
1199 Integer idPrimary = paramIndex2idPrimary.get( paramIndex );
1201 assert id2hrn.containsKey( idPrimary );
1202 HeapRegionNode hrnPrimary = id2hrn.get( idPrimary );
1204 ReachTuple p_i = new ReachTuple( hrnPrimary.getID(),
1205 false, // multiple-object?
1206 ReachTuple.ARITY_ONE ).makeCanonical();
1207 paramTokenPrimary2paramIndex.put( p_i, paramIndex );
1208 paramIndex2paramTokenPrimary.put( paramIndex, p_i );
1211 // any parameter object, by type, may have no secondary region
1212 if( paramIndex2idSecondary.containsKey( paramIndex ) ) {
1213 Integer idSecondary = paramIndex2idSecondary.get( paramIndex );
1215 assert id2hrn.containsKey( idSecondary );
1216 HeapRegionNode hrnSecondary = id2hrn.get( idSecondary );
1218 ReachTuple s_i = new ReachTuple( hrnSecondary.getID(),
1219 true, // multiple-object?
1220 ReachTuple.ARITY_ONE ).makeCanonical();
1221 paramTokenSecondary2paramIndex.put( s_i, paramIndex );
1222 paramIndex2paramTokenSecondary.put( paramIndex, s_i );
1224 ReachTuple s_i_plus = new ReachTuple( hrnSecondary.getID(),
1225 true, // multiple-object?
1226 ReachTuple.ARITY_ONEORMORE ).makeCanonical();
1227 paramTokenSecondaryPlus2paramIndex.put( s_i_plus, paramIndex );
1228 paramIndex2paramTokenSecondaryPlus.put( paramIndex, s_i_plus );
1230 ReachTuple s_i_star = new ReachTuple( hrnSecondary.getID(),
1231 true, // multiple-object?
1232 ReachTuple.ARITY_ZEROORMORE ).makeCanonical();
1233 paramTokenSecondaryStar2paramIndex.put( s_i_star, paramIndex );
1234 paramIndex2paramTokenSecondaryStar.put( paramIndex, s_i_star );
1241 public void assignReturnEqualToTemp(TempDescriptor x) {
1243 VariableNode lnR = getVariableNodeFromTemp(tdReturn);
1244 VariableNode lnX = getVariableNodeFromTemp(x);
1246 clearRefEdgesFrom(lnR, null, null, true);
1248 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
1249 while( itrXhrn.hasNext() ) {
1250 RefEdge edgeX = itrXhrn.next();
1251 HeapRegionNode referencee = edgeX.getDst();
1252 RefEdge edgeNew = edgeX.copy();
1253 edgeNew.setSrc(lnR);
1255 addRefEdge(lnR, referencee, edgeNew);
1260 public void assignTempEqualToNewAlloc(TempDescriptor x,
1267 // after the age operation the newest (or zero-ith oldest)
1268 // node associated with the allocation site should have
1269 // no references to it as if it were a newly allocated
1271 Integer idNewest = as.getIthOldest( 0 );
1272 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
1273 assert hrnNewest != null;
1275 VariableNode lnX = getVariableNodeFromTemp( x );
1276 clearRefEdgesFrom( lnX, null, null, true );
1278 // make a new reference to allocated node
1279 TypeDescriptor type = as.getType();
1281 new RefEdge( lnX, // source
1285 false, // is initial param
1286 hrnNewest.getAlpha() // beta
1289 addRefEdge( lnX, hrnNewest, edgeNew );
1293 // use the allocation site (unique to entire analysis) to
1294 // locate the heap region nodes in this ownership graph
1295 // that should be aged. The process models the allocation
1296 // of new objects and collects all the oldest allocations
1297 // in a summary node to allow for a finite analysis
1299 // There is an additional property of this method. After
1300 // running it on a particular ownership graph (many graphs
1301 // may have heap regions related to the same allocation site)
1302 // the heap region node objects in this ownership graph will be
1303 // allocated. Therefore, after aging a graph for an allocation
1304 // site, attempts to retrieve the heap region nodes using the
1305 // integer id's contained in the allocation site should always
1306 // return non-null heap regions.
1307 public void age(AllocSite as) {
1309 // aging adds this allocation site to the graph's
1310 // list of sites that exist in the graph, or does
1311 // nothing if the site is already in the list
1314 // get the summary node for the allocation site in the context
1315 // of this particular ownership graph
1316 HeapRegionNode hrnSummary = getSummaryNode(as);
1318 // merge oldest node into summary
1319 Integer idK = as.getOldest();
1320 HeapRegionNode hrnK = id2hrn.get(idK);
1321 mergeIntoSummary(hrnK, hrnSummary);
1323 // move down the line of heap region nodes
1324 // clobbering the ith and transferring all references
1325 // to and from i-1 to node i. Note that this clobbers
1326 // the oldest node (hrnK) that was just merged into
1328 for( int i = allocationDepth - 1; i > 0; --i ) {
1330 // move references from the i-1 oldest to the ith oldest
1331 Integer idIth = as.getIthOldest(i);
1332 HeapRegionNode hrnI = id2hrn.get(idIth);
1333 Integer idImin1th = as.getIthOldest(i - 1);
1334 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
1336 transferOnto(hrnImin1, hrnI);
1339 // as stated above, the newest node should have had its
1340 // references moved over to the second oldest, so we wipe newest
1341 // in preparation for being the new object to assign something to
1342 Integer id0th = as.getIthOldest(0);
1343 HeapRegionNode hrn0 = id2hrn.get(id0th);
1344 assert hrn0 != null;
1346 // clear all references in and out of newest node
1347 clearRefEdgesFrom(hrn0, null, null, true);
1348 clearRefEdgesTo(hrn0, null, null, true);
1351 // now tokens in reachability sets need to "age" also
1352 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
1353 while( itrAllVariableNodes.hasNext() ) {
1354 Map.Entry me = (Map.Entry)itrAllVariableNodes.next();
1355 VariableNode ln = (VariableNode) me.getValue();
1357 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
1358 while( itrEdges.hasNext() ) {
1359 ageTokens(as, itrEdges.next() );
1363 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1364 while( itrAllHRNodes.hasNext() ) {
1365 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1366 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1368 ageTokens(as, hrnToAge);
1370 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
1371 while( itrEdges.hasNext() ) {
1372 ageTokens(as, itrEdges.next() );
1377 // after tokens have been aged, reset newest node's reachability
1378 if( hrn0.isFlagged() ) {
1379 hrn0.setAlpha(new ReachSet(
1381 new ReachTuple(hrn0).makeCanonical()
1386 hrn0.setAlpha(new ReachSet(
1387 new ReachState().makeCanonical()
1394 protected HeapRegionNode getSummaryNode(AllocSite as) {
1396 Integer idSummary = as.getSummary();
1397 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
1399 // If this is null then we haven't touched this allocation site
1400 // in the context of the current ownership graph, so allocate
1401 // heap region nodes appropriate for the entire allocation site.
1402 // This should only happen once per ownership graph per allocation site,
1403 // and a particular integer id can be used to locate the heap region
1404 // in different ownership graphs that represents the same part of an
1406 if( hrnSummary == null ) {
1408 boolean hasFlags = false;
1409 if( as.getType().isClass() ) {
1410 hasFlags = as.getType().getClassDesc().hasFlags();
1414 hasFlags=as.getFlag();
1417 hrnSummary = createNewHeapRegionNode(idSummary, // id or null to generate a new one
1418 false, // single object?
1420 hasFlags, // flagged?
1421 false, // is a parameter?
1422 as.getType(), // type
1423 as, // allocation site
1424 null, // reachability set
1425 as.toStringForDOT() + "\\nsummary",
1426 generateUniqueIdentifier(as,0,true));
1428 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1429 Integer idIth = as.getIthOldest(i);
1430 assert !id2hrn.containsKey(idIth);
1431 createNewHeapRegionNode(idIth, // id or null to generate a new one
1432 true, // single object?
1434 hasFlags, // flagged?
1435 false, // is a parameter?
1436 as.getType(), // type
1437 as, // allocation site
1438 null, // reachability set
1439 as.toStringForDOT() + "\\n" + i + " oldest",
1440 generateUniqueIdentifier(as,i,false));
1448 protected HeapRegionNode getShadowSummaryNode(AllocSite as) {
1450 Integer idShadowSummary = as.getSummaryShadow();
1451 HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
1453 if( hrnShadowSummary == null ) {
1455 boolean hasFlags = false;
1456 if( as.getType().isClass() ) {
1457 hasFlags = as.getType().getClassDesc().hasFlags();
1460 hrnShadowSummary = createNewHeapRegionNode(idShadowSummary, // id or null to generate a new one
1461 false, // single object?
1463 hasFlags, // flagged?
1464 false, // is a parameter?
1465 as.getType(), // type
1466 as, // allocation site
1467 null, // reachability set
1468 as + "\\n" + as.getType() + "\\nshadowSum",
1471 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1472 Integer idShadowIth = as.getIthOldestShadow(i);
1473 assert !id2hrn.containsKey(idShadowIth);
1474 createNewHeapRegionNode(idShadowIth, // id or null to generate a new one
1475 true, // single object?
1477 hasFlags, // flagged?
1478 false, // is a parameter?
1479 as.getType(), // type
1480 as, // allocation site
1481 null, // reachability set
1482 as + "\\n" + as.getType() + "\\n" + i + " shadow",
1487 return hrnShadowSummary;
1491 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
1492 assert hrnSummary.isNewSummary();
1494 // transfer references _from_ hrn over to hrnSummary
1495 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
1496 while( itrReferencee.hasNext() ) {
1497 RefEdge edge = itrReferencee.next();
1498 RefEdge edgeMerged = edge.copy();
1499 edgeMerged.setSrc(hrnSummary);
1501 HeapRegionNode hrnReferencee = edge.getDst();
1502 RefEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee,
1506 if( edgeSummary == null ) {
1507 // the merge is trivial, nothing to be done
1509 // otherwise an edge from the referencer to hrnSummary exists already
1510 // and the edge referencer->hrn should be merged with it
1511 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1514 addRefEdge(hrnSummary, hrnReferencee, edgeMerged);
1517 // next transfer references _to_ hrn over to hrnSummary
1518 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
1519 while( itrReferencer.hasNext() ) {
1520 RefEdge edge = itrReferencer.next();
1521 RefEdge edgeMerged = edge.copy();
1522 edgeMerged.setDst(hrnSummary);
1524 RefSrcNode onReferencer = edge.getSrc();
1525 RefEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary,
1529 if( edgeSummary == null ) {
1530 // the merge is trivial, nothing to be done
1532 // otherwise an edge from the referencer to alpha_S exists already
1533 // and the edge referencer->alpha_K should be merged with it
1534 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1537 addRefEdge(onReferencer, hrnSummary, edgeMerged);
1540 // then merge hrn reachability into hrnSummary
1541 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
1545 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
1547 // clear references in and out of node b
1548 clearRefEdgesFrom(hrnB, null, null, true);
1549 clearRefEdgesTo(hrnB, null, null, true);
1551 // copy each edge in and out of A to B
1552 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
1553 while( itrReferencee.hasNext() ) {
1554 RefEdge edge = itrReferencee.next();
1555 HeapRegionNode hrnReferencee = edge.getDst();
1556 RefEdge edgeNew = edge.copy();
1557 edgeNew.setSrc(hrnB);
1559 addRefEdge(hrnB, hrnReferencee, edgeNew);
1562 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
1563 while( itrReferencer.hasNext() ) {
1564 RefEdge edge = itrReferencer.next();
1565 RefSrcNode onReferencer = edge.getSrc();
1566 RefEdge edgeNew = edge.copy();
1567 edgeNew.setDst(hrnB);
1569 addRefEdge(onReferencer, hrnB, edgeNew);
1572 // replace hrnB reachability with hrnA's
1573 hrnB.setAlpha(hrnA.getAlpha() );
1577 protected void ageTokens(AllocSite as, RefEdge edge) {
1578 edge.setBeta(edge.getBeta().ageTokens(as) );
1581 protected void ageTokens(AllocSite as, HeapRegionNode hrn) {
1582 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
1587 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1589 HashSet<HeapRegionNode> nodesWithNewAlpha,
1590 HashSet<RefEdge> edgesWithNewBeta) {
1592 HashSet<HeapRegionNode> todoNodes
1593 = new HashSet<HeapRegionNode>();
1594 todoNodes.add(nPrime);
1596 HashSet<RefEdge> todoEdges
1597 = new HashSet<RefEdge>();
1599 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1600 = new Hashtable<HeapRegionNode, ChangeSet>();
1601 nodePlannedChanges.put(nPrime, c0);
1603 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1604 = new Hashtable<RefEdge, ChangeSet>();
1606 // first propagate change sets everywhere they can go
1607 while( !todoNodes.isEmpty() ) {
1608 HeapRegionNode n = todoNodes.iterator().next();
1609 ChangeSet C = nodePlannedChanges.get(n);
1611 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1612 while( referItr.hasNext() ) {
1613 RefEdge edge = referItr.next();
1614 todoEdges.add(edge);
1616 if( !edgePlannedChanges.containsKey(edge) ) {
1617 edgePlannedChanges.put(edge, new ChangeSet().makeCanonical() );
1620 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
1623 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1624 while( refeeItr.hasNext() ) {
1625 RefEdge edgeF = refeeItr.next();
1626 HeapRegionNode m = edgeF.getDst();
1628 ChangeSet changesToPass = new ChangeSet().makeCanonical();
1630 Iterator<ChangeTuple> itrCprime = C.iterator();
1631 while( itrCprime.hasNext() ) {
1632 ChangeTuple c = itrCprime.next();
1633 if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
1634 changesToPass = changesToPass.union(c);
1638 if( !changesToPass.isEmpty() ) {
1639 if( !nodePlannedChanges.containsKey(m) ) {
1640 nodePlannedChanges.put(m, new ChangeSet().makeCanonical() );
1643 ChangeSet currentChanges = nodePlannedChanges.get(m);
1645 if( !changesToPass.isSubset(currentChanges) ) {
1647 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
1653 todoNodes.remove(n);
1656 // then apply all of the changes for each node at once
1657 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1658 while( itrMap.hasNext() ) {
1659 Map.Entry me = (Map.Entry) itrMap.next();
1660 HeapRegionNode n = (HeapRegionNode) me.getKey();
1661 ChangeSet C = (ChangeSet) me.getValue();
1663 // this propagation step is with respect to one change,
1664 // so we capture the full change from the old alpha:
1665 ReachSet localDelta = n.getAlpha().applyChangeSet( C, true );
1667 // but this propagation may be only one of many concurrent
1668 // possible changes, so keep a running union with the node's
1669 // partially updated new alpha set
1670 n.setAlphaNew( n.getAlphaNew().union( localDelta ) );
1672 nodesWithNewAlpha.add( n );
1675 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
1679 protected void propagateTokensOverEdges(
1680 HashSet<RefEdge> todoEdges,
1681 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1682 HashSet<RefEdge> edgesWithNewBeta) {
1684 // first propagate all change tuples everywhere they can go
1685 while( !todoEdges.isEmpty() ) {
1686 RefEdge edgeE = todoEdges.iterator().next();
1687 todoEdges.remove(edgeE);
1689 if( !edgePlannedChanges.containsKey(edgeE) ) {
1690 edgePlannedChanges.put(edgeE, new ChangeSet().makeCanonical() );
1693 ChangeSet C = edgePlannedChanges.get(edgeE);
1695 ChangeSet changesToPass = new ChangeSet().makeCanonical();
1697 Iterator<ChangeTuple> itrC = C.iterator();
1698 while( itrC.hasNext() ) {
1699 ChangeTuple c = itrC.next();
1700 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1701 changesToPass = changesToPass.union(c);
1705 RefSrcNode onSrc = edgeE.getSrc();
1707 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
1708 HeapRegionNode n = (HeapRegionNode) onSrc;
1710 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1711 while( referItr.hasNext() ) {
1712 RefEdge edgeF = referItr.next();
1714 if( !edgePlannedChanges.containsKey(edgeF) ) {
1715 edgePlannedChanges.put(edgeF, new ChangeSet().makeCanonical() );
1718 ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
1720 if( !changesToPass.isSubset(currentChanges) ) {
1721 todoEdges.add(edgeF);
1722 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
1728 // then apply all of the changes for each edge at once
1729 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1730 while( itrMap.hasNext() ) {
1731 Map.Entry me = (Map.Entry) itrMap.next();
1732 RefEdge e = (RefEdge) me.getKey();
1733 ChangeSet C = (ChangeSet) me.getValue();
1735 // this propagation step is with respect to one change,
1736 // so we capture the full change from the old beta:
1737 ReachSet localDelta = e.getBeta().applyChangeSet( C, true );
1739 // but this propagation may be only one of many concurrent
1740 // possible changes, so keep a running union with the edge's
1741 // partially updated new beta set
1742 e.setBetaNew( e.getBetaNew().union( localDelta ) );
1744 edgesWithNewBeta.add( e );
1749 public Set<Integer> calculateAliasedParamSet( FlatCall fc,
1753 Hashtable<Integer, VariableNode> paramIndex2ln =
1754 new Hashtable<Integer, VariableNode>();
1756 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
1757 new Hashtable<Integer, HashSet<HeapRegionNode> >();
1759 for( int i = 0; i < fm.numParameters(); ++i ) {
1760 Integer paramIndex = new Integer( i );
1761 TempDescriptor tdParam = fm.getParameter( i );
1762 TypeDescriptor typeParam = tdParam.getType();
1764 if( typeParam.isImmutable() && !typeParam.isArray() ) {
1765 // don't bother with this primitive parameter, it
1766 // cannot affect reachability
1770 // now depending on whether the callee is static or not
1771 // we need to account for a "this" argument in order to
1772 // find the matching argument in the caller context
1773 TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, paramIndex );
1775 VariableNode argLabel_i = getVariableNodeFromTemp(argTemp_i);
1776 paramIndex2ln.put(paramIndex, argLabel_i);
1779 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1780 while( lnArgItr.hasNext() ) {
1781 Map.Entry me = (Map.Entry)lnArgItr.next();
1782 Integer index = (Integer) me.getKey();
1783 VariableNode lnArg_i = (VariableNode) me.getValue();
1785 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1786 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1788 // to find all reachable nodes, start with label referencees
1789 Iterator<RefEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1790 while( edgeArgItr.hasNext() ) {
1791 RefEdge edge = edgeArgItr.next();
1792 todoNodes.add( edge.getDst() );
1795 // then follow links until all reachable nodes have been found
1796 while( !todoNodes.isEmpty() ) {
1797 HeapRegionNode hrn = todoNodes.iterator().next();
1798 todoNodes.remove(hrn);
1799 reachableNodes.add(hrn);
1801 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
1802 while( edgeItr.hasNext() ) {
1803 RefEdge edge = edgeItr.next();
1805 if( !reachableNodes.contains(edge.getDst() ) ) {
1806 todoNodes.add(edge.getDst() );
1812 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1815 Set<Integer> aliasedIndices = new HashSet<Integer>();
1817 // check for arguments that are aliased
1818 for( int i = 0; i < fm.numParameters(); ++i ) {
1819 for( int j = 0; j < i; ++j ) {
1820 HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
1821 HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
1823 // some parameters are immutable or primitive, so skip em
1824 if( s1 == null || s2 == null ) {
1828 Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
1829 intersection.retainAll(s2);
1831 if( !intersection.isEmpty() ) {
1832 aliasedIndices.add( new Integer( i ) );
1833 aliasedIndices.add( new Integer( j ) );
1838 return aliasedIndices;
1842 private String makeMapKey( Integer i, Integer j, String field ) {
1843 return i+","+j+","+field;
1846 private String makeMapKey( Integer i, String field ) {
1850 // these hashtables are used during the mapping procedure to say that
1851 // with respect to some argument i there is an edge placed into some
1852 // category for mapping with respect to another argument index j
1853 // so the key into the hashtable is i, the value is a two-element vector
1854 // that contains in 0 the edge and in 1 the Integer index j
1855 private void ensureEmptyEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
1858 Set<Vector> ei = edge_index_pairs.get( indexI );
1860 ei = new HashSet<Vector>();
1862 edge_index_pairs.put( indexI, ei );
1865 private void addEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
1870 Vector v = new Vector(); v.setSize( 2 );
1872 v.set( 1 , indexJ );
1873 Set<Vector> ei = edge_index_pairs.get( indexI );
1875 ei = new HashSet<Vector>();
1878 edge_index_pairs.put( indexI, ei );
1881 private ReachSet funcScriptR( ReachSet rsIn,
1882 ReachGraph ogCallee,
1883 MethodContext mc ) {
1885 ReachSet rsOut = new ReachSet( rsIn );
1887 Iterator itr = ogCallee.paramIndex2paramTokenPrimary.entrySet().iterator();
1888 while( itr.hasNext() ) {
1889 Map.Entry me = (Map.Entry) itr.next();
1890 Integer i = (Integer) me.getKey();
1891 ReachTuple p_i = (ReachTuple) me.getValue();
1892 ReachTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( i );
1894 // skip this if there is no secondary token or the parameter
1895 // is part of the aliasing context
1896 if( s_i == null || mc.getAliasedParamIndices().contains( i ) ) {
1900 rsOut = rsOut.removeTokenAIfTokenB( p_i, s_i );
1906 // detects strong updates to the primary parameter object and
1907 // effects the removal of old edges in the calling graph
1908 private void effectCalleeStrongUpdates( Integer paramIndex,
1909 ReachGraph ogCallee,
1910 HeapRegionNode hrnCaller
1912 Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
1913 assert idPrimary != null;
1915 HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
1916 assert hrnPrimary != null;
1918 TypeDescriptor typeParam = hrnPrimary.getType();
1919 assert typeParam.isClass();
1921 Set<String> fieldNamesToRemove = new HashSet<String>();
1923 ClassDescriptor cd = typeParam.getClassDesc();
1924 while( cd != null ) {
1926 Iterator fieldItr = cd.getFields();
1927 while( fieldItr.hasNext() ) {
1929 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
1930 TypeDescriptor typeField = fd.getType();
1931 assert typeField != null;
1933 if( ogCallee.hasFieldBeenUpdated( hrnPrimary, fd.getSymbol() ) ) {
1934 clearRefEdgesFrom( hrnCaller, fd.getType(), fd.getSymbol(), false );
1938 cd = cd.getSuperDesc();
1942 private boolean hasFieldBeenUpdated( HeapRegionNode hrnPrimary, String field ) {
1944 Iterator<RefEdge> itr = hrnPrimary.iteratorToReferencees();
1945 while( itr.hasNext() ) {
1946 RefEdge e = itr.next();
1947 if( e.fieldEquals( field ) && e.isInitialParam() ) {
1955 // resolveMethodCall() is used to incorporate a callee graph's effects into
1956 // *this* graph, which is the caller. This method can also be used, after
1957 // the entire analysis is complete, to perform parameter decomposition for
1958 // a given call chain.
1959 public void resolveMethodCall(FlatCall fc, // call site in caller method
1960 boolean isStatic, // whether it is a static method
1961 FlatMethod fm, // the callee method (when virtual, can be many)
1962 ReachGraph ogCallee, // the callee's current ownership graph
1963 MethodContext mc, // the aliasing context for this call
1964 ParameterDecomposition pd // if this is not null, we're calling after analysis
1968 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
1969 fm.getMethod().getSymbol().equals( debugCallee )
1973 writeGraph("debug1BeforeCall",
1974 true, // write labels (variables)
1975 true, // selectively hide intermediate temp vars
1976 true, // prune unreachable heap regions
1977 false, // show back edges to confirm graph validity
1978 false, // show parameter indices (unmaintained!)
1979 true, // hide subset reachability states
1980 true); // hide edge taints
1982 ogCallee.writeGraph("debug0Callee",
1983 true, // write labels (variables)
1984 true, // selectively hide intermediate temp vars
1985 true, // prune unreachable heap regions
1986 false, // show back edges to confirm graph validity
1987 false, // show parameter indices (unmaintained!)
1988 true, // hide subset reachability states
1989 true); // hide edge taints
1990 } catch( IOException e ) {}
1992 System.out.println( " "+mc+" is calling "+fm );
1997 // define rewrite rules and other structures to organize data by parameter/argument index
1998 Hashtable<Integer, ReachSet> paramIndex2rewriteH_p = new Hashtable<Integer, ReachSet>();
1999 Hashtable<Integer, ReachSet> paramIndex2rewriteH_s = new Hashtable<Integer, ReachSet>();
2001 Hashtable<String, ReachSet> paramIndex2rewriteJ_p2p = new Hashtable<String, ReachSet>(); // select( i, j, f )
2002 Hashtable<String, ReachSet> paramIndex2rewriteJ_p2s = new Hashtable<String, ReachSet>(); // select( i, f )
2003 Hashtable<Integer, ReachSet> paramIndex2rewriteJ_s2p = new Hashtable<Integer, ReachSet>();
2004 Hashtable<Integer, ReachSet> paramIndex2rewriteJ_s2s = new Hashtable<Integer, ReachSet>();
2006 Hashtable<Integer, ReachSet> paramIndex2rewriteK_p = new Hashtable<Integer, ReachSet>();
2007 Hashtable<Integer, ReachSet> paramIndex2rewriteK_p2 = new Hashtable<Integer, ReachSet>();
2008 Hashtable<Integer, ReachSet> paramIndex2rewriteK_s = new Hashtable<Integer, ReachSet>();
2010 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_p = new Hashtable<Integer, ReachSet>();
2011 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_s = new Hashtable<Integer, ReachSet>();
2013 Hashtable<Integer, ReachSet> paramIndex2rewriteD = new Hashtable<Integer, ReachSet>();
2016 Hashtable<Integer, VariableNode> paramIndex2ln = new Hashtable<Integer, VariableNode>();
2019 paramIndex2rewriteH_p.put( bogusIndex, rsIdentity );
2020 paramIndex2rewriteH_s.put( bogusIndex, rsIdentity );
2022 paramIndex2rewriteJ_p2p.put( bogusIndex.toString(), rsIdentity );
2023 paramIndex2rewriteJ_p2s.put( bogusIndex.toString(), rsIdentity );
2024 paramIndex2rewriteJ_s2p.put( bogusIndex, rsIdentity );
2025 paramIndex2rewriteJ_s2s.put( bogusIndex, rsIdentity );
2028 for( int i = 0; i < fm.numParameters(); ++i ) {
2029 Integer paramIndex = new Integer(i);
2031 if( !ogCallee.paramIndex2idPrimary.containsKey( paramIndex ) ) {
2032 // skip this immutable parameter
2036 // setup H (primary)
2037 Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
2038 assert ogCallee.id2hrn.containsKey( idPrimary );
2039 HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
2040 assert hrnPrimary != null;
2041 paramIndex2rewriteH_p.put( paramIndex, toShadowTokens( ogCallee, hrnPrimary.getAlpha() ) );
2043 // setup J (primary->X)
2044 Iterator<RefEdge> p2xItr = hrnPrimary.iteratorToReferencees();
2045 while( p2xItr.hasNext() ) {
2046 RefEdge p2xEdge = p2xItr.next();
2048 // we only care about initial parameter edges here
2049 if( !p2xEdge.isInitialParam() ) { continue; }
2051 HeapRegionNode hrnDst = p2xEdge.getDst();
2053 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
2054 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
2055 while( jItr.hasNext() ) {
2056 Integer j = jItr.next();
2057 paramIndex2rewriteJ_p2p.put( makeMapKey( i, j, p2xEdge.getField() ),
2058 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
2062 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
2063 paramIndex2rewriteJ_p2s.put( makeMapKey( i, p2xEdge.getField() ),
2064 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
2068 // setup K (primary)
2069 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
2070 assert tdParamQ != null;
2071 VariableNode lnParamQ = ogCallee.td2vn.get( tdParamQ );
2072 assert lnParamQ != null;
2073 RefEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnPrimary, null, null );
2074 assert edgeSpecialQ_i != null;
2075 ReachSet qBeta = toShadowTokens( ogCallee, edgeSpecialQ_i.getBeta() );
2077 ReachTuple p_i = ogCallee.paramIndex2paramTokenPrimary .get( paramIndex );
2078 ReachTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( paramIndex );
2080 ReachSet K_p = new ReachSet().makeCanonical();
2081 ReachSet K_p2 = new ReachSet().makeCanonical();
2085 // sort qBeta into K_p1 and K_p2
2086 Iterator<ReachState> ttsItr = qBeta.iterator();
2087 while( ttsItr.hasNext() ) {
2088 ReachState tts = ttsItr.next();
2089 if( s_i != null && tts.containsBoth( p_i, s_i ) ) {
2090 K_p2 = K_p2.union( tts );
2092 K_p = K_p.union( tts );
2096 paramIndex2rewriteK_p .put( paramIndex, K_p );
2097 paramIndex2rewriteK_p2.put( paramIndex, K_p2 );
2100 // if there is a secondary node, compute the rest of the rewrite rules
2101 if( ogCallee.paramIndex2idSecondary.containsKey( paramIndex ) ) {
2103 // setup H (secondary)
2104 Integer idSecondary = ogCallee.paramIndex2idSecondary.get( paramIndex );
2105 assert ogCallee.id2hrn.containsKey( idSecondary );
2106 HeapRegionNode hrnSecondary = ogCallee.id2hrn.get( idSecondary );
2107 assert hrnSecondary != null;
2108 paramIndex2rewriteH_s.put( paramIndex, toShadowTokens( ogCallee, hrnSecondary.getAlpha() ) );
2110 // setup J (secondary->X)
2111 Iterator<RefEdge> s2xItr = hrnSecondary.iteratorToReferencees();
2112 while( s2xItr.hasNext() ) {
2113 RefEdge s2xEdge = s2xItr.next();
2115 if( !s2xEdge.isInitialParam() ) { continue; }
2117 HeapRegionNode hrnDst = s2xEdge.getDst();
2119 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
2120 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
2121 while( jItr.hasNext() ) {
2122 Integer j = jItr.next();
2123 paramIndex2rewriteJ_s2p.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
2127 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
2128 paramIndex2rewriteJ_s2s.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
2132 // setup K (secondary)
2133 TempDescriptor tdParamR = ogCallee.paramIndex2tdR.get( paramIndex );
2134 assert tdParamR != null;
2135 VariableNode lnParamR = ogCallee.td2vn.get( tdParamR );
2136 assert lnParamR != null;
2137 RefEdge edgeSpecialR_i = lnParamR.getReferenceTo( hrnSecondary, null, null );
2138 assert edgeSpecialR_i != null;
2139 paramIndex2rewriteK_s.put( paramIndex,
2140 toShadowTokens( ogCallee, edgeSpecialR_i.getBeta() ) );
2144 // now depending on whether the callee is static or not
2145 // we need to account for a "this" argument in order to
2146 // find the matching argument in the caller context
2147 TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, paramIndex );
2149 // remember which caller arg label maps to param index
2150 VariableNode argLabel_i = getVariableNodeFromTemp( argTemp_i );
2151 paramIndex2ln.put( paramIndex, argLabel_i );
2153 // do a callee-effect strong update pre-pass here
2154 if( argTemp_i.getType().isClass() ) {
2156 Iterator<RefEdge> edgeItr = argLabel_i.iteratorToReferencees();
2157 while( edgeItr.hasNext() ) {
2158 RefEdge edge = edgeItr.next();
2159 HeapRegionNode hrn = edge.getDst();
2161 if( (hrn.getNumReferencers() == 1) || // case 1
2162 (hrn.isSingleObject() && argLabel_i.getNumReferencees() == 1) // case 2
2164 if( !DISABLE_STRONG_UPDATES ) {
2165 effectCalleeStrongUpdates( paramIndex, ogCallee, hrn );
2171 // then calculate the d and D rewrite rules
2172 ReachSet d_i_p = new ReachSet().makeCanonical();
2173 ReachSet d_i_s = new ReachSet().makeCanonical();
2174 Iterator<RefEdge> edgeItr = argLabel_i.iteratorToReferencees();
2175 while( edgeItr.hasNext() ) {
2176 RefEdge edge = edgeItr.next();
2178 d_i_p = d_i_p.union( edge.getBeta().intersection( edge.getDst().getAlpha() ) );
2179 d_i_s = d_i_s.union( edge.getBeta() );
2181 paramIndex2rewrite_d_p.put( paramIndex, d_i_p );
2182 paramIndex2rewrite_d_s.put( paramIndex, d_i_s );
2184 // TODO: we should only do this when we need it, and then
2185 // memoize it for the rest of the mapping procedure
2186 ReachSet D_i = d_i_s.exhaustiveArityCombinations();
2187 paramIndex2rewriteD.put( paramIndex, D_i );
2191 // with respect to each argument, map parameter effects into caller
2192 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
2193 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
2195 Hashtable<Integer, Set<HeapRegionNode> > pi2dr =
2196 new Hashtable<Integer, Set<HeapRegionNode> >();
2198 Hashtable<Integer, Set<HeapRegionNode> > pi2r =
2199 new Hashtable<Integer, Set<HeapRegionNode> >();
2201 Set<HeapRegionNode> defParamObj = new HashSet<HeapRegionNode>();
2203 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
2204 while( lnArgItr.hasNext() ) {
2205 Map.Entry me = (Map.Entry) lnArgItr.next();
2206 Integer index = (Integer) me.getKey();
2207 VariableNode lnArg_i = (VariableNode) me.getValue();
2209 Set<HeapRegionNode> dr = new HashSet<HeapRegionNode>();
2210 Set<HeapRegionNode> r = new HashSet<HeapRegionNode>();
2211 Set<HeapRegionNode> todo = new HashSet<HeapRegionNode>();
2213 // find all reachable nodes starting with label referencees
2214 Iterator<RefEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
2215 while( edgeArgItr.hasNext() ) {
2216 RefEdge edge = edgeArgItr.next();
2217 HeapRegionNode hrn = edge.getDst();
2221 if( lnArg_i.getNumReferencees() == 1 && hrn.isSingleObject() ) {
2222 defParamObj.add( hrn );
2225 Iterator<RefEdge> edgeHrnItr = hrn.iteratorToReferencees();
2226 while( edgeHrnItr.hasNext() ) {
2227 RefEdge edger = edgeHrnItr.next();
2228 todo.add( edger.getDst() );
2231 // then follow links until all reachable nodes have been found
2232 while( !todo.isEmpty() ) {
2233 HeapRegionNode hrnr = todo.iterator().next();
2234 todo.remove( hrnr );
2238 Iterator<RefEdge> edgeItr = hrnr.iteratorToReferencees();
2239 while( edgeItr.hasNext() ) {
2240 RefEdge edger = edgeItr.next();
2241 if( !r.contains( edger.getDst() ) ) {
2242 todo.add( edger.getDst() );
2247 if( hrn.isSingleObject() ) {
2252 pi2dr.put( index, dr );
2253 pi2r .put( index, r );
2256 assert defParamObj.size() <= fm.numParameters();
2258 // if we're in parameter decomposition mode, report some results here
2262 // report primary parameter object mappings
2263 mapItr = pi2dr.entrySet().iterator();
2264 while( mapItr.hasNext() ) {
2265 Map.Entry me = (Map.Entry) mapItr.next();
2266 Integer paramIndex = (Integer) me.getKey();
2267 Set<HeapRegionNode> hrnAset = (Set<HeapRegionNode>) me.getValue();
2269 Iterator<HeapRegionNode> hrnItr = hrnAset.iterator();
2270 while( hrnItr.hasNext() ) {
2271 HeapRegionNode hrnA = hrnItr.next();
2272 pd.mapRegionToParamObject( hrnA, paramIndex );
2276 // report parameter-reachable mappings
2277 mapItr = pi2r.entrySet().iterator();
2278 while( mapItr.hasNext() ) {
2279 Map.Entry me = (Map.Entry) mapItr.next();
2280 Integer paramIndex = (Integer) me.getKey();
2281 Set<HeapRegionNode> hrnRset = (Set<HeapRegionNode>) me.getValue();
2283 Iterator<HeapRegionNode> hrnItr = hrnRset.iterator();
2284 while( hrnItr.hasNext() ) {
2285 HeapRegionNode hrnR = hrnItr.next();
2286 pd.mapRegionToParamReachable( hrnR, paramIndex );
2290 // and we're done in this method for special param decomp mode
2295 // now iterate over reachable nodes to rewrite their alpha, and
2296 // classify edges found for beta rewrite
2297 Hashtable<ReachTuple, ReachSet> tokens2states = new Hashtable<ReachTuple, ReachSet>();
2299 Hashtable< Integer, Set<Vector> > edges_p2p = new Hashtable< Integer, Set<Vector> >();
2300 Hashtable< Integer, Set<Vector> > edges_p2s = new Hashtable< Integer, Set<Vector> >();
2301 Hashtable< Integer, Set<Vector> > edges_s2p = new Hashtable< Integer, Set<Vector> >();
2302 Hashtable< Integer, Set<Vector> > edges_s2s = new Hashtable< Integer, Set<Vector> >();
2303 Hashtable< Integer, Set<Vector> > edges_up_dr = new Hashtable< Integer, Set<Vector> >();
2304 Hashtable< Integer, Set<Vector> > edges_up_r = new Hashtable< Integer, Set<Vector> >();
2306 // so again, with respect to some arg i...
2307 lnArgItr = paramIndex2ln.entrySet().iterator();
2308 while( lnArgItr.hasNext() ) {
2309 Map.Entry me = (Map.Entry) lnArgItr.next();
2310 Integer index = (Integer) me.getKey();
2311 VariableNode lnArg_i = (VariableNode) me.getValue();
2313 ReachTuple p_i = ogCallee.paramIndex2paramTokenPrimary.get( index );
2314 ReachTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( index );
2317 ensureEmptyEdgeIndexPair( edges_p2p, index );
2318 ensureEmptyEdgeIndexPair( edges_p2s, index );
2319 ensureEmptyEdgeIndexPair( edges_s2p, index );
2320 ensureEmptyEdgeIndexPair( edges_s2s, index );
2321 ensureEmptyEdgeIndexPair( edges_up_dr, index );
2322 ensureEmptyEdgeIndexPair( edges_up_r, index );
2324 Set<HeapRegionNode> dr = pi2dr.get( index );
2325 Iterator<HeapRegionNode> hrnItr = dr.iterator();
2326 while( hrnItr.hasNext() ) {
2327 // this heap region is definitely an "a_i" or primary by virtue of being in dr
2328 HeapRegionNode hrn = hrnItr.next();
2330 tokens2states.clear();
2331 tokens2states.put( p_i, hrn.getAlpha() );
2333 rewriteCallerReachability( index,
2336 paramIndex2rewriteH_p.get( index ),
2338 paramIndex2rewrite_d_p,
2339 paramIndex2rewrite_d_s,
2340 paramIndex2rewriteD,
2345 nodesWithNewAlpha.add( hrn );
2348 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
2349 while( edgeItr.hasNext() ) {
2350 RefEdge edge = edgeItr.next();
2351 RefSrcNode on = edge.getSrc();
2353 boolean edge_classified = false;
2356 if( on instanceof HeapRegionNode ) {
2357 // hrn0 may be "a_j" and/or "r_j" or even neither
2358 HeapRegionNode hrn0 = (HeapRegionNode) on;
2360 Iterator itr = pi2dr.entrySet().iterator();
2361 while( itr.hasNext() ) {
2362 Map.Entry mo = (Map.Entry) itr.next();
2363 Integer pi = (Integer) mo.getKey();
2364 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
2366 if( dr_i.contains( hrn0 ) ) {
2367 addEdgeIndexPair( edges_p2p, pi, edge, index );
2368 edge_classified = true;
2372 itr = pi2r.entrySet().iterator();
2373 while( itr.hasNext() ) {
2374 Map.Entry mo = (Map.Entry) itr.next();
2375 Integer pi = (Integer) mo.getKey();
2376 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
2378 if( r_i.contains( hrn0 ) ) {
2379 addEdgeIndexPair( edges_s2p, pi, edge, index );
2380 edge_classified = true;
2385 // all of these edges are upstream of directly reachable objects
2386 if( !edge_classified ) {
2387 addEdgeIndexPair( edges_up_dr, index, edge, index );
2393 Set<HeapRegionNode> r = pi2r.get( index );
2394 hrnItr = r.iterator();
2395 while( hrnItr.hasNext() ) {
2396 // this heap region is definitely an "r_i" or secondary by virtue of being in r
2397 HeapRegionNode hrn = hrnItr.next();
2399 if( paramIndex2rewriteH_s.containsKey( index ) ) {
2401 tokens2states.clear();
2402 tokens2states.put( p_i, new ReachSet().makeCanonical() );
2403 tokens2states.put( s_i, hrn.getAlpha() );
2405 rewriteCallerReachability( index,
2408 paramIndex2rewriteH_s.get( index ),
2410 paramIndex2rewrite_d_p,
2411 paramIndex2rewrite_d_s,
2412 paramIndex2rewriteD,
2417 nodesWithNewAlpha.add( hrn );
2421 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
2422 while( edgeItr.hasNext() ) {
2423 RefEdge edge = edgeItr.next();
2424 RefSrcNode on = edge.getSrc();
2426 boolean edge_classified = false;
2428 if( on instanceof HeapRegionNode ) {
2429 // hrn0 may be "a_j" and/or "r_j" or even neither
2430 HeapRegionNode hrn0 = (HeapRegionNode) on;
2432 Iterator itr = pi2dr.entrySet().iterator();
2433 while( itr.hasNext() ) {
2434 Map.Entry mo = (Map.Entry) itr.next();
2435 Integer pi = (Integer) mo.getKey();
2436 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
2438 if( dr_i.contains( hrn0 ) ) {
2439 addEdgeIndexPair( edges_p2s, pi, edge, index );
2440 edge_classified = true;
2444 itr = pi2r.entrySet().iterator();
2445 while( itr.hasNext() ) {
2446 Map.Entry mo = (Map.Entry) itr.next();
2447 Integer pi = (Integer) mo.getKey();
2448 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
2450 if( r_i.contains( hrn0 ) ) {
2451 addEdgeIndexPair( edges_s2s, pi, edge, index );
2452 edge_classified = true;
2457 // these edges are all upstream of some reachable node
2458 if( !edge_classified ) {
2459 addEdgeIndexPair( edges_up_r, index, edge, index );
2466 // and again, with respect to some arg i...
2467 lnArgItr = paramIndex2ln.entrySet().iterator();
2468 while( lnArgItr.hasNext() ) {
2469 Map.Entry me = (Map.Entry) lnArgItr.next();
2470 Integer index = (Integer) me.getKey();
2471 VariableNode lnArg_i = (VariableNode) me.getValue();
2474 // update reachable edges
2475 Iterator edgeItr = edges_p2p.get( index ).iterator();
2476 while( edgeItr.hasNext() ) {
2477 Vector mo = (Vector) edgeItr.next();
2478 RefEdge edge = (RefEdge) mo.get( 0 );
2479 Integer indexJ = (Integer) mo.get( 1 );
2481 if( !paramIndex2rewriteJ_p2p.containsKey( makeMapKey( index,
2483 edge.getField() ) ) ) {
2487 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2490 tokens2states.clear();
2491 tokens2states.put( p_j, edge.getBeta() );
2493 rewriteCallerReachability( index,
2496 paramIndex2rewriteJ_p2p.get( makeMapKey( index,
2498 edge.getField() ) ),
2500 paramIndex2rewrite_d_p,
2501 paramIndex2rewrite_d_s,
2502 paramIndex2rewriteD,
2507 edgesWithNewBeta.add( edge );
2511 edgeItr = edges_p2s.get( index ).iterator();
2512 while( edgeItr.hasNext() ) {
2513 Vector mo = (Vector) edgeItr.next();
2514 RefEdge edge = (RefEdge) mo.get( 0 );
2515 Integer indexJ = (Integer) mo.get( 1 );
2517 if( !paramIndex2rewriteJ_p2s.containsKey( makeMapKey( index,
2518 edge.getField() ) ) ) {
2522 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2525 tokens2states.clear();
2526 tokens2states.put( s_j, edge.getBeta() );
2528 rewriteCallerReachability( index,
2531 paramIndex2rewriteJ_p2s.get( makeMapKey( index,
2532 edge.getField() ) ),
2534 paramIndex2rewrite_d_p,
2535 paramIndex2rewrite_d_s,
2536 paramIndex2rewriteD,
2541 edgesWithNewBeta.add( edge );
2545 edgeItr = edges_s2p.get( index ).iterator();
2546 while( edgeItr.hasNext() ) {
2547 Vector mo = (Vector) edgeItr.next();
2548 RefEdge edge = (RefEdge) mo.get( 0 );
2549 Integer indexJ = (Integer) mo.get( 1 );
2551 if( !paramIndex2rewriteJ_s2p.containsKey( index ) ) {
2555 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2558 tokens2states.clear();
2559 tokens2states.put( p_j, edge.getBeta() );
2561 rewriteCallerReachability( index,
2564 paramIndex2rewriteJ_s2p.get( index ),
2566 paramIndex2rewrite_d_p,
2567 paramIndex2rewrite_d_s,
2568 paramIndex2rewriteD,
2573 edgesWithNewBeta.add( edge );
2577 edgeItr = edges_s2s.get( index ).iterator();
2578 while( edgeItr.hasNext() ) {
2579 Vector mo = (Vector) edgeItr.next();
2580 RefEdge edge = (RefEdge) mo.get( 0 );
2581 Integer indexJ = (Integer) mo.get( 1 );
2583 if( !paramIndex2rewriteJ_s2s.containsKey( index ) ) {
2587 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2590 tokens2states.clear();
2591 tokens2states.put( s_j, edge.getBeta() );
2593 rewriteCallerReachability( index,
2596 paramIndex2rewriteJ_s2s.get( index ),
2598 paramIndex2rewrite_d_p,
2599 paramIndex2rewrite_d_s,
2600 paramIndex2rewriteD,
2605 edgesWithNewBeta.add( edge );
2609 // update directly upstream edges
2610 Hashtable<RefEdge, ChangeSet> edgeUpstreamPlannedChanges =
2611 new Hashtable<RefEdge, ChangeSet>();
2613 HashSet<RefEdge> edgesDirectlyUpstream =
2614 new HashSet<RefEdge>();
2616 edgeItr = edges_up_dr.get( index ).iterator();
2617 while( edgeItr.hasNext() ) {
2618 Vector mo = (Vector) edgeItr.next();
2619 RefEdge edge = (RefEdge) mo.get( 0 );
2620 Integer indexJ = (Integer) mo.get( 1 );
2622 edgesDirectlyUpstream.add( edge );
2624 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2627 // start with K_p2 and p_j
2628 tokens2states.clear();
2629 tokens2states.put( p_j, edge.getBeta() );
2631 rewriteCallerReachability( index,
2634 paramIndex2rewriteK_p2.get( index ),
2636 paramIndex2rewrite_d_p,
2637 paramIndex2rewrite_d_s,
2638 paramIndex2rewriteD,
2641 edgeUpstreamPlannedChanges );
2643 // and add in s_j, if required, and do K_p
2644 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2646 tokens2states.put( s_j, edge.getBeta() );
2649 rewriteCallerReachability( index,
2652 paramIndex2rewriteK_p.get( index ),
2654 paramIndex2rewrite_d_p,
2655 paramIndex2rewrite_d_s,
2656 paramIndex2rewriteD,
2659 edgeUpstreamPlannedChanges );
2661 edgesWithNewBeta.add( edge );
2664 propagateTokensOverEdges( edgesDirectlyUpstream,
2665 edgeUpstreamPlannedChanges,
2669 // update upstream edges
2670 edgeUpstreamPlannedChanges =
2671 new Hashtable<RefEdge, ChangeSet>();
2673 HashSet<RefEdge> edgesUpstream =
2674 new HashSet<RefEdge>();
2676 edgeItr = edges_up_r.get( index ).iterator();
2677 while( edgeItr.hasNext() ) {
2678 Vector mo = (Vector) edgeItr.next();
2679 RefEdge edge = (RefEdge) mo.get( 0 );
2680 Integer indexJ = (Integer) mo.get( 1 );
2682 if( !paramIndex2rewriteK_s.containsKey( index ) ) {
2686 edgesUpstream.add( edge );
2688 ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2691 ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2694 tokens2states.clear();
2695 tokens2states.put( p_j, rsWttsEmpty );
2696 tokens2states.put( s_j, edge.getBeta() );
2698 rewriteCallerReachability( index,
2701 paramIndex2rewriteK_s.get( index ),
2703 paramIndex2rewrite_d_p,
2704 paramIndex2rewrite_d_s,
2705 paramIndex2rewriteD,
2708 edgeUpstreamPlannedChanges );
2710 edgesWithNewBeta.add( edge );
2713 propagateTokensOverEdges( edgesUpstream,
2714 edgeUpstreamPlannedChanges,
2717 } // end effects per argument/parameter map
2720 // commit changes to alpha and beta
2721 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
2722 while( nodeItr.hasNext() ) {
2723 nodeItr.next().applyAlphaNew();
2726 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
2727 while( edgeItr.hasNext() ) {
2728 edgeItr.next().applyBetaNew();
2732 // verify the existence of allocation sites and their
2733 // shadows from the callee in the context of this caller graph
2734 // then map allocated nodes of callee onto the caller shadows
2736 Hashtable<ReachTuple, ReachSet> tokens2statesEmpty = new Hashtable<ReachTuple, ReachSet>();
2738 Iterator<AllocSite> asItr = ogCallee.allocSites.iterator();
2739 while( asItr.hasNext() ) {
2740 AllocSite allocSite = asItr.next();
2742 // grab the summary in the caller just to make sure
2743 // the allocation site has nodes in the caller
2744 HeapRegionNode hrnSummary = getSummaryNode( allocSite );
2746 // assert that the shadow nodes have no reference edges
2747 // because they're brand new to the graph, or last time
2748 // they were used they should have been cleared of edges
2749 HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
2750 assert hrnShadowSummary.getNumReferencers() == 0;
2751 assert hrnShadowSummary.getNumReferencees() == 0;
2753 // then bring g_ij onto g'_ij and rewrite
2754 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode( allocSite );
2755 hrnShadowSummary.setAlpha( toShadowTokens( ogCallee, hrnSummaryCallee.getAlpha() ) );
2757 // shadow nodes only are touched by a rewrite one time,
2758 // so rewrite and immediately commit--and they don't belong
2759 // to a particular parameter, so use a bogus param index
2760 // that pulls a self-rewrite out of H
2761 rewriteCallerReachability( bogusIndex,
2764 funcScriptR( hrnShadowSummary.getAlpha(), ogCallee, mc ),
2766 paramIndex2rewrite_d_p,
2767 paramIndex2rewrite_d_s,
2768 paramIndex2rewriteD,
2773 hrnShadowSummary.applyAlphaNew();
2776 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
2777 Integer idIth = allocSite.getIthOldest(i);
2778 assert id2hrn.containsKey(idIth);
2779 HeapRegionNode hrnIth = id2hrn.get(idIth);
2781 Integer idShadowIth = -(allocSite.getIthOldest(i));
2782 assert id2hrn.containsKey(idShadowIth);
2783 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
2784 assert hrnIthShadow.getNumReferencers() == 0;
2785 assert hrnIthShadow.getNumReferencees() == 0;
2787 assert ogCallee.id2hrn.containsKey(idIth);
2788 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
2789 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
2791 rewriteCallerReachability( bogusIndex,
2794 funcScriptR( hrnIthShadow.getAlpha(), ogCallee, mc ),
2796 paramIndex2rewrite_d_p,
2797 paramIndex2rewrite_d_s,
2798 paramIndex2rewriteD,
2803 hrnIthShadow.applyAlphaNew();
2808 // for every heap region->heap region edge in the
2809 // callee graph, create the matching edge or edges
2810 // in the caller graph
2811 Set sCallee = ogCallee.id2hrn.entrySet();
2812 Iterator iCallee = sCallee.iterator();
2814 while( iCallee.hasNext() ) {
2815 Map.Entry meCallee = (Map.Entry) iCallee.next();
2816 Integer idCallee = (Integer) meCallee.getKey();
2817 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
2819 Iterator<RefEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
2820 while( heapRegionsItrCallee.hasNext() ) {
2821 RefEdge edgeCallee = heapRegionsItrCallee.next();
2822 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
2823 Integer idChildCallee = hrnChildCallee.getID();
2825 // only address this edge if it is not a special initial edge
2826 if( !edgeCallee.isInitialParam() ) {
2828 // now we know that in the callee method's ownership graph
2829 // there is a heap region->heap region reference edge given
2830 // by heap region pointers:
2831 // hrnCallee -> heapChildCallee
2833 // or by the ownership-graph independent ID's:
2834 // idCallee -> idChildCallee
2836 // make the edge with src and dst so beta info is
2837 // calculated once, then copy it for each new edge in caller
2839 RefEdge edgeNewInCallerTemplate = new RefEdge( null,
2841 edgeCallee.getType(),
2842 edgeCallee.getField(),
2844 funcScriptR( toShadowTokens( ogCallee,
2845 edgeCallee.getBeta()
2851 rewriteCallerReachability( bogusIndex,
2853 edgeNewInCallerTemplate,
2854 edgeNewInCallerTemplate.getBeta(),
2856 paramIndex2rewrite_d_p,
2857 paramIndex2rewrite_d_s,
2858 paramIndex2rewriteD,
2863 edgeNewInCallerTemplate.applyBetaNew();
2866 // So now make a set of possible source heaps in the caller graph
2867 // and a set of destination heaps in the caller graph, and make
2868 // a reference edge in the caller for every possible (src,dst) pair
2869 HashSet<HeapRegionNode> possibleCallerSrcs =
2870 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2871 (HeapRegionNode) edgeCallee.getSrc(),
2875 HashSet<HeapRegionNode> possibleCallerDsts =
2876 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2877 edgeCallee.getDst(),
2881 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
2882 Iterator srcItr = possibleCallerSrcs.iterator();
2883 while( srcItr.hasNext() ) {
2884 HeapRegionNode src = (HeapRegionNode) srcItr.next();
2886 if( !hasMatchingField( src, edgeCallee ) ) {
2887 // prune this source node possibility
2891 Iterator dstItr = possibleCallerDsts.iterator();
2892 while( dstItr.hasNext() ) {
2893 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
2895 if( !hasMatchingType( edgeCallee, dst ) ) {
2904 // otherwise the caller src and dst pair can match the edge, so make it
2905 TypeDescriptor tdNewEdge =
2906 mostSpecificType( edgeCallee.getType(),
2907 hrnChildCallee.getType(),
2911 RefEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2912 edgeNewInCaller.setSrc( src );
2913 edgeNewInCaller.setDst( dst );
2914 edgeNewInCaller.setType( tdNewEdge );
2917 // handle taint info if callee created this edge
2919 Set<Integer> pParamSet=idPrimary2paramIndexSet.get(dst.getID());
2920 Set<Integer> sParamSet=idSecondary2paramIndexSet.get(dst.getID());
2921 HashSet<Integer> paramSet=new HashSet<Integer>();
2922 if(pParamSet!=null){
2923 paramSet.addAll(pParamSet);
2925 if(sParamSet!=null){
2926 paramSet.addAll(sParamSet);
2928 Iterator<Integer> paramIter=paramSet.iterator();
2929 int newTaintIdentifier=0;
2930 while(paramIter.hasNext()){
2931 Integer paramIdx=paramIter.next();
2932 edgeNewInCaller.tainedBy(paramIdx);
2935 RefEdge edgeExisting = src.getReferenceTo( dst,
2936 edgeNewInCaller.getType(),
2937 edgeNewInCaller.getField() );
2938 if( edgeExisting == null ) {
2939 // if this edge doesn't exist in the caller, create it
2940 addRefEdge( src, dst, edgeNewInCaller );
2943 // if it already exists, merge with it
2944 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2954 // return value may need to be assigned in caller
2955 TempDescriptor returnTemp = fc.getReturnTemp();
2956 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2958 VariableNode lnLhsCaller = getVariableNodeFromTemp( returnTemp );
2959 clearRefEdgesFrom( lnLhsCaller, null, null, true );
2961 VariableNode lnReturnCallee = ogCallee.getVariableNodeFromTemp( tdReturn );
2962 Iterator<RefEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
2963 while( edgeCalleeItr.hasNext() ) {
2964 RefEdge edgeCallee = edgeCalleeItr.next();
2965 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
2967 // some edge types are not possible return values when we can
2968 // see what type variable we are assigning it to
2969 if( !isSuperiorType( returnTemp.getType(), edgeCallee.getType() ) ) {
2970 System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+edgeCallee+" for return temp "+returnTemp );
2975 RefEdge edgeNewInCallerTemplate = new RefEdge( null,
2977 edgeCallee.getType(),
2978 edgeCallee.getField(),
2980 funcScriptR( toShadowTokens(ogCallee,
2981 edgeCallee.getBeta() ),
2985 rewriteCallerReachability( bogusIndex,
2987 edgeNewInCallerTemplate,
2988 edgeNewInCallerTemplate.getBeta(),
2990 paramIndex2rewrite_d_p,
2991 paramIndex2rewrite_d_s,
2992 paramIndex2rewriteD,
2997 edgeNewInCallerTemplate.applyBetaNew();
3000 HashSet<HeapRegionNode> assignCallerRhs =
3001 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
3002 edgeCallee.getDst(),
3006 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
3007 while( itrHrn.hasNext() ) {
3008 HeapRegionNode hrnCaller = itrHrn.next();
3010 // don't make edge in caller if it is disallowed by types
3011 if( !isSuperiorType( returnTemp.getType(), hrnCaller.getType() ) ) {
3016 if( !isSuperiorType( returnTemp.getType(), hrnChildCallee.getType() ) ) {
3021 if( !isSuperiorType( edgeCallee.getType(), hrnCaller.getType() ) ) {
3026 TypeDescriptor tdNewEdge =
3027 mostSpecificType( edgeCallee.getType(),
3028 hrnChildCallee.getType(),
3032 // otherwise caller node can match callee edge, so make it
3033 RefEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
3034 edgeNewInCaller.setSrc( lnLhsCaller );
3035 edgeNewInCaller.setDst( hrnCaller );
3036 edgeNewInCaller.setType( tdNewEdge );
3038 RefEdge edgeExisting = lnLhsCaller.getReferenceTo( hrnCaller,
3040 edgeNewInCaller.getField() );
3041 if( edgeExisting == null ) {
3043 // if this edge doesn't exist in the caller, create it
3044 addRefEdge( lnLhsCaller, hrnCaller, edgeNewInCaller );
3046 // if it already exists, merge with it
3047 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
3055 // merge the shadow nodes of allocation sites back down to normal capacity
3056 Iterator<AllocSite> allocItr = ogCallee.allocSites.iterator();
3057 while( allocItr.hasNext() ) {
3058 AllocSite as = allocItr.next();
3060 // first age each allocation site enough times to make room for the shadow nodes
3061 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
3065 // then merge the shadow summary into the normal summary
3066 HeapRegionNode hrnSummary = getSummaryNode( as );
3067 assert hrnSummary != null;
3069 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as );
3070 assert hrnSummaryShadow != null;
3072 mergeIntoSummary( hrnSummaryShadow, hrnSummary );
3074 // then clear off after merge
3075 clearRefEdgesFrom( hrnSummaryShadow, null, null, true );
3076 clearRefEdgesTo ( hrnSummaryShadow, null, null, true );
3077 hrnSummaryShadow.setAlpha( new ReachSet().makeCanonical() );
3079 // then transplant shadow nodes onto the now clean normal nodes
3080 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
3082 Integer idIth = as.getIthOldest( i );
3083 HeapRegionNode hrnIth = id2hrn.get( idIth );
3084 Integer idIthShadow = as.getIthOldestShadow( i );
3085 HeapRegionNode hrnIthShadow = id2hrn.get( idIthShadow );
3087 transferOnto( hrnIthShadow, hrnIth );
3089 // clear off shadow nodes after transfer
3090 clearRefEdgesFrom( hrnIthShadow, null, null, true );
3091 clearRefEdgesTo ( hrnIthShadow, null, null, true );
3092 hrnIthShadow.setAlpha( new ReachSet().makeCanonical() );
3095 // finally, globally change shadow tokens into normal tokens
3096 Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
3097 while( itrAllVariableNodes.hasNext() ) {
3098 Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
3099 VariableNode ln = (VariableNode) me.getValue();
3101 Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
3102 while( itrEdges.hasNext() ) {
3103 unshadowTokens( as, itrEdges.next() );
3107 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3108 while( itrAllHRNodes.hasNext() ) {
3109 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
3110 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
3112 unshadowTokens( as, hrnToAge );
3114 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
3115 while( itrEdges.hasNext() ) {
3116 unshadowTokens( as, itrEdges.next() );
3123 // improve reachability as much as possible
3124 if( !DISABLE_GLOBAL_SWEEP ) {
3130 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
3131 fm.getMethod().getSymbol().equals( debugCallee )
3135 writeGraph( "debug9endResolveCall",
3136 true, // write labels (variables)
3137 true, // selectively hide intermediate temp vars
3138 true, // prune unreachable heap regions
3139 false, // show back edges to confirm graph validity
3140 false, // show parameter indices (unmaintained!)
3141 true, // hide subset reachability states
3142 true); // hide edge taints
3143 } catch( IOException e ) {}
3144 System.out.println( " "+mc+" done calling "+fm );
3146 if( x == debugCallMapCount ) {
3155 protected boolean hasMatchingField(HeapRegionNode src, RefEdge edge) {
3157 // if no type, then it's a match-everything region
3158 TypeDescriptor tdSrc = src.getType();
3159 if( tdSrc == null ) {
3163 if( tdSrc.isArray() ) {
3164 TypeDescriptor td = edge.getType();
3167 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3168 assert tdSrcDeref != null;
3170 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3174 return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3177 // if it's not a class, it doesn't have any fields to match
3178 if( !tdSrc.isClass() ) {
3182 ClassDescriptor cd = tdSrc.getClassDesc();
3183 while( cd != null ) {
3184 Iterator fieldItr = cd.getFields();
3186 while( fieldItr.hasNext() ) {
3187 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3189 if( fd.getType().equals( edge.getType() ) &&
3190 fd.getSymbol().equals( edge.getField() ) ) {
3195 cd = cd.getSuperDesc();
3198 // otherwise it is a class with fields
3199 // but we didn't find a match
3204 protected boolean hasMatchingType(RefEdge edge, HeapRegionNode dst) {
3206 // if the region has no type, matches everything
3207 TypeDescriptor tdDst = dst.getType();
3208 if( tdDst == null ) {
3212 // if the type is not a class or an array, don't
3213 // match because primitives are copied, no aliases
3214 ClassDescriptor cdDst = tdDst.getClassDesc();
3215 if( cdDst == null && !tdDst.isArray() ) {
3219 // if the edge type is null, it matches everything
3220 TypeDescriptor tdEdge = edge.getType();
3221 if( tdEdge == null ) {
3225 return typeUtil.isSuperorType(tdEdge, tdDst);
3229 protected void unshadowTokens(AllocSite as, RefEdge edge) {
3230 edge.setBeta(edge.getBeta().unshadowTokens(as) );
3233 protected void unshadowTokens(AllocSite as, HeapRegionNode hrn) {
3234 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
3238 private ReachSet toShadowTokens(ReachGraph ogCallee,
3241 ReachSet rsOut = new ReachSet(rsIn).makeCanonical();
3243 Iterator<AllocSite> allocItr = ogCallee.allocSites.iterator();
3244 while( allocItr.hasNext() ) {
3245 AllocSite as = allocItr.next();
3247 rsOut = rsOut.toShadowTokens(as);
3250 return rsOut.makeCanonical();
3254 private void rewriteCallerReachability(Integer paramIndex,
3258 Hashtable<ReachTuple, ReachSet> tokens2states,
3259 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_p,
3260 Hashtable<Integer, ReachSet> paramIndex2rewrite_d_s,
3261 Hashtable<Integer, ReachSet> paramIndex2rewriteD,
3262 ReachGraph ogCallee,
3263 boolean makeChangeSet,
3264 Hashtable<RefEdge, ChangeSet> edgePlannedChanges) {
3266 assert(hrn == null && edge != null) ||
3267 (hrn != null && edge == null);
3269 assert rules != null;
3270 assert tokens2states != null;
3272 ReachSet callerReachabilityNew = new ReachSet().makeCanonical();
3274 // for initializing structures in this method
3275 ReachState ttsEmpty = new ReachState().makeCanonical();
3277 // use this to construct a change set if required; the idea is to
3278 // map every partially rewritten token tuple set to the set of
3279 // caller-context token tuple sets that were used to generate it
3280 Hashtable<ReachState, HashSet<ReachState> > rewritten2source =
3281 new Hashtable<ReachState, HashSet<ReachState> >();
3282 rewritten2source.put( ttsEmpty, new HashSet<ReachState>() );
3285 Iterator<ReachState> rulesItr = rules.iterator();
3286 while(rulesItr.hasNext()) {
3287 ReachState rule = rulesItr.next();
3289 ReachSet rewrittenRule = new ReachSet(ttsEmpty).makeCanonical();
3291 Iterator<ReachTuple> ruleItr = rule.iterator();
3292 while(ruleItr.hasNext()) {
3293 ReachTuple ttCallee = ruleItr.next();
3295 // compute the possibilities for rewriting this callee token
3296 ReachSet ttCalleeRewrites = null;
3297 boolean callerSourceUsed = false;
3299 if( tokens2states.containsKey( ttCallee ) ) {
3300 callerSourceUsed = true;
3301 ttCalleeRewrites = tokens2states.get( ttCallee );
3302 assert ttCalleeRewrites != null;
3304 } else if( ogCallee.paramTokenPrimary2paramIndex.containsKey( ttCallee ) ) {
3306 Integer paramIndex_j = ogCallee.paramTokenPrimary2paramIndex.get( ttCallee );
3307 assert paramIndex_j != null;
3308 ttCalleeRewrites = paramIndex2rewrite_d_p.get( paramIndex_j );
3309 assert ttCalleeRewrites != null;
3311 } else if( ogCallee.paramTokenSecondary2paramIndex.containsKey( ttCallee ) ) {
3313 Integer paramIndex_j = ogCallee.paramTokenSecondary2paramIndex.get( ttCallee );
3314 assert paramIndex_j != null;
3315 ttCalleeRewrites = paramIndex2rewrite_d_s.get( paramIndex_j );
3316 assert ttCalleeRewrites != null;
3318 } else if( ogCallee.paramTokenSecondaryPlus2paramIndex.containsKey( ttCallee ) ) {
3320 Integer paramIndex_j = ogCallee.paramTokenSecondaryPlus2paramIndex.get( ttCallee );
3321 assert paramIndex_j != null;
3322 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
3323 assert ttCalleeRewrites != null;
3325 } else if( ogCallee.paramTokenSecondaryStar2paramIndex.containsKey( ttCallee ) ) {
3327 Integer paramIndex_j = ogCallee.paramTokenSecondaryStar2paramIndex.get( ttCallee );
3328 assert paramIndex_j != null;
3329 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
3330 assert ttCalleeRewrites != null;
3333 // otherwise there's no need for a rewrite, just pass this one on
3334 ReachState ttsCaller = new ReachState( ttCallee ).makeCanonical();
3335 ttCalleeRewrites = new ReachSet( ttsCaller ).makeCanonical();
3338 // branch every version of the working rewritten rule with
3339 // the possibilities for rewriting the current callee token
3340 ReachSet rewrittenRuleWithTTCallee = new ReachSet().makeCanonical();
3342 Iterator<ReachState> rewrittenRuleItr = rewrittenRule.iterator();
3343 while( rewrittenRuleItr.hasNext() ) {
3344 ReachState ttsRewritten = rewrittenRuleItr.next();
3346 Iterator<ReachState> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
3347 while( ttCalleeRewritesItr.hasNext() ) {
3348 ReachState ttsBranch = ttCalleeRewritesItr.next();
3350 ReachState ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
3352 if( makeChangeSet ) {
3353 // in order to keep the list of source token tuple sets
3354 // start with the sets used to make the partially rewritten
3355 // rule up to this point
3356 HashSet<ReachState> sourceSets = rewritten2source.get( ttsRewritten );
3357 assert sourceSets != null;
3359 // make a shallow copy for possible modification
3360 sourceSets = (HashSet<ReachState>) sourceSets.clone();
3362 // if we used something from the caller to rewrite it, remember
3363 if( callerSourceUsed ) {
3364 sourceSets.add( ttsBranch );
3367 // set mapping for the further rewritten rule
3368 rewritten2source.put( ttsRewrittenNext, sourceSets );
3371 rewrittenRuleWithTTCallee =
3372 rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
3376 // now the rewritten rule's possibilities have been extended by
3377 // rewriting the current callee token, remember result
3378 rewrittenRule = rewrittenRuleWithTTCallee;
3381 // the rule has been entirely rewritten into the caller context
3382 // now, so add it to the new reachability information
3383 callerReachabilityNew =
3384 callerReachabilityNew.union( rewrittenRule );
3387 if( makeChangeSet ) {
3388 ChangeSet callerChangeSet = new ChangeSet().makeCanonical();
3390 // each possibility for the final reachability should have a set of
3391 // caller sources mapped to it, use to create the change set
3392 Iterator<ReachState> callerReachabilityItr = callerReachabilityNew.iterator();
3393 while( callerReachabilityItr.hasNext() ) {
3394 ReachState ttsRewrittenFinal = callerReachabilityItr.next();
3395 HashSet<ReachState> sourceSets = rewritten2source.get( ttsRewrittenFinal );
3396 assert sourceSets != null;
3398 Iterator<ReachState> sourceSetsItr = sourceSets.iterator();
3399 while( sourceSetsItr.hasNext() ) {
3400 ReachState ttsSource = sourceSetsItr.next();
3403 callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
3407 assert edgePlannedChanges != null;
3408 edgePlannedChanges.put( edge, callerChangeSet );
3412 edge.setBetaNew( edge.getBetaNew().union( callerReachabilityNew ) );
3414 hrn.setAlphaNew( hrn.getAlphaNew().union( callerReachabilityNew ) );
3420 private HashSet<HeapRegionNode>
3421 getHRNSetThatPossiblyMapToCalleeHRN( ReachGraph ogCallee,
3422 HeapRegionNode hrnCallee,
3423 Hashtable<Integer, Set<HeapRegionNode> > pi2dr,
3424 Hashtable<Integer, Set<HeapRegionNode> > pi2r
3427 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
3429 Set<Integer> paramIndicesCallee_p = ogCallee.idPrimary2paramIndexSet .get( hrnCallee.getID() );
3430 Set<Integer> paramIndicesCallee_s = ogCallee.idSecondary2paramIndexSet.get( hrnCallee.getID() );
3432 if( paramIndicesCallee_p == null &&
3433 paramIndicesCallee_s == null ) {
3434 // this is a node allocated in the callee and it has
3435 // exactly one shadow node in the caller to map to
3436 AllocSite as = hrnCallee.getAllocSite();
3439 int age = as.getAgeCategory( hrnCallee.getID() );
3440 assert age != AllocSite.AGE_notInThisSite;
3443 if( age == AllocSite.AGE_summary ) {
3444 idCaller = as.getSummaryShadow();
3446 } else if( age == AllocSite.AGE_oldest ) {
3447 idCaller = as.getOldestShadow();
3450 assert age == AllocSite.AGE_in_I;
3452 Integer I = as.getAge( hrnCallee.getID() );
3455 idCaller = as.getIthOldestShadow( I );
3458 assert id2hrn.containsKey( idCaller );
3459 possibleCallerHRNs.add( id2hrn.get( idCaller ) );
3461 return possibleCallerHRNs;
3464 // find out what primary objects this might be
3465 if( paramIndicesCallee_p != null ) {
3466 // this is a node that was created to represent a parameter
3467 // so it maps to some regions directly reachable from the arg labels
3468 Iterator<Integer> itrIndex = paramIndicesCallee_p.iterator();
3469 while( itrIndex.hasNext() ) {
3470 Integer paramIndexCallee = itrIndex.next();
3471 assert pi2dr.containsKey( paramIndexCallee );
3472 possibleCallerHRNs.addAll( pi2dr.get( paramIndexCallee ) );
3476 // find out what secondary objects this might be
3477 if( paramIndicesCallee_s != null ) {
3478 // this is a node that was created to represent objs reachable from
3479 // some parameter, so it maps to regions reachable from the arg labels
3480 Iterator<Integer> itrIndex = paramIndicesCallee_s.iterator();
3481 while( itrIndex.hasNext() ) {
3482 Integer paramIndexCallee = itrIndex.next();
3483 assert pi2r.containsKey( paramIndexCallee );
3484 possibleCallerHRNs.addAll( pi2r.get( paramIndexCallee ) );
3488 // TODO: is this true?
3489 // one of the two cases above should have put something in here
3490 //assert !possibleCallerHRNs.isEmpty();
3492 return possibleCallerHRNs;
3497 ////////////////////////////////////////////////////
3499 // This global sweep is an optional step to prune
3500 // reachability sets that are not internally
3501 // consistent with the global graph. It should be
3502 // invoked after strong updates or method calls.
3504 ////////////////////////////////////////////////////
3505 public void globalSweep() {
3507 // boldB is part of the phase 1 sweep
3508 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
3509 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3511 // visit every heap region to initialize alphaNew and calculate boldB
3512 Set hrns = id2hrn.entrySet();
3513 Iterator itrHrns = hrns.iterator();
3514 while( itrHrns.hasNext() ) {
3515 Map.Entry me = (Map.Entry)itrHrns.next();
3516 Integer token = (Integer) me.getKey();
3517 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3519 // assert that this node and incoming edges have clean alphaNew
3520 // and betaNew sets, respectively
3521 assert rsEmpty.equals( hrn.getAlphaNew() );
3523 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3524 while( itrRers.hasNext() ) {
3525 RefEdge edge = itrRers.next();
3526 assert rsEmpty.equals( edge.getBetaNew() );
3529 // calculate boldB for this flagged node
3530 if( hrn.isFlagged() || hrn.isParameter() ) {
3532 Hashtable<RefEdge, ReachSet> boldB_f =
3533 new Hashtable<RefEdge, ReachSet>();
3535 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3537 // initial boldB_f constraints
3538 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3539 while( itrRees.hasNext() ) {
3540 RefEdge edge = itrRees.next();
3542 assert !boldB.containsKey( edge );
3543 boldB_f.put( edge, edge.getBeta() );
3545 assert !workSetEdges.contains( edge );
3546 workSetEdges.add( edge );
3549 // enforce the boldB_f constraint at edges until we reach a fixed point
3550 while( !workSetEdges.isEmpty() ) {
3551 RefEdge edge = workSetEdges.iterator().next();
3552 workSetEdges.remove( edge );
3554 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3555 while( itrPrime.hasNext() ) {
3556 RefEdge edgePrime = itrPrime.next();
3558 ReachSet prevResult = boldB_f.get( edgePrime );
3559 ReachSet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
3561 if( prevResult == null ||
3562 prevResult.union( intersection ).size() > prevResult.size() ) {
3564 if( prevResult == null ) {
3565 boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) );
3567 boldB_f.put( edgePrime, prevResult .union( intersection ) );
3569 workSetEdges.add( edgePrime );
3574 boldB.put( token, boldB_f );
3579 // use boldB to prune tokens from alpha states that are impossible
3580 // and propagate the differences backwards across edges
3581 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3583 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3584 new Hashtable<RefEdge, ChangeSet>();
3586 hrns = id2hrn.entrySet();
3587 itrHrns = hrns.iterator();
3588 while( itrHrns.hasNext() ) {
3589 Map.Entry me = (Map.Entry)itrHrns.next();
3590 Integer token = (Integer) me.getKey();
3591 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3593 // never remove the identity token from a flagged region
3594 // because it is trivially satisfied
3595 ReachTuple ttException = new ReachTuple( token,
3596 !hrn.isSingleObject(),
3597 ReachTuple.ARITY_ONE ).makeCanonical();
3599 ChangeSet cts = new ChangeSet().makeCanonical();
3601 // mark tokens for removal
3602 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3603 while( stateItr.hasNext() ) {
3604 ReachState ttsOld = stateItr.next();
3606 ReachState markedTokens = new ReachState().makeCanonical();
3608 Iterator<ReachTuple> ttItr = ttsOld.iterator();
3609 while( ttItr.hasNext() ) {
3610 ReachTuple ttOld = ttItr.next();
3612 // never remove the identity token from a flagged region
3613 // because it is trivially satisfied
3614 if( hrn.isFlagged() || hrn.isParameter() ) {
3615 if( ttOld == ttException ) {
3620 // does boldB_ttOld allow this token?
3621 boolean foundState = false;
3622 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3623 while( incidentEdgeItr.hasNext() ) {
3624 RefEdge incidentEdge = incidentEdgeItr.next();
3626 // if it isn't allowed, mark for removal
3627 Integer idOld = ttOld.getToken();
3628 assert id2hrn.containsKey( idOld );
3629 Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
3630 ReachSet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL!
3631 if( boldB_ttOld_incident != null &&
3632 boldB_ttOld_incident.contains( ttsOld ) ) {
3638 markedTokens = markedTokens.add( ttOld );
3642 // if there is nothing marked, just move on
3643 if( markedTokens.isEmpty() ) {
3644 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
3648 // remove all marked tokens and establish a change set that should
3649 // propagate backwards over edges from this node
3650 ReachState ttsPruned = new ReachState().makeCanonical();
3651 ttItr = ttsOld.iterator();
3652 while( ttItr.hasNext() ) {
3653 ReachTuple ttOld = ttItr.next();
3655 if( !markedTokens.containsTuple( ttOld ) ) {
3656 ttsPruned = ttsPruned.union( ttOld );
3659 assert !ttsOld.equals( ttsPruned );
3661 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
3662 ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
3663 cts = cts.union( ct );
3666 // throw change tuple set on all incident edges
3667 if( !cts.isEmpty() ) {
3668 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3669 while( incidentEdgeItr.hasNext() ) {
3670 RefEdge incidentEdge = incidentEdgeItr.next();
3672 edgesForPropagation.add( incidentEdge );
3674 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3675 edgePlannedChanges.put( incidentEdge, cts );
3677 edgePlannedChanges.put(
3679 edgePlannedChanges.get( incidentEdge ).union( cts )
3686 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3688 propagateTokensOverEdges( edgesForPropagation,
3692 // at the end of the 1st phase reference edges have
3693 // beta, betaNew that correspond to beta and betaR
3695 // commit beta<-betaNew, so beta=betaR and betaNew
3696 // will represent the beta' calculation in 2nd phase
3698 // commit alpha<-alphaNew because it won't change
3699 HashSet<RefEdge> res = new HashSet<RefEdge>();
3701 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3702 while( nodeItr.hasNext() ) {
3703 HeapRegionNode hrn = nodeItr.next();
3704 hrn.applyAlphaNew();
3705 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3706 while( itrRes.hasNext() ) {
3707 res.add( itrRes.next() );
3713 Iterator<RefEdge> edgeItr = res.iterator();
3714 while( edgeItr.hasNext() ) {
3715 RefEdge edge = edgeItr.next();
3716 HeapRegionNode hrn = edge.getDst();
3718 // commit results of last phase
3719 if( edgesUpdated.contains( edge ) ) {
3720 edge.applyBetaNew();
3723 // compute intial condition of 2nd phase
3724 edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
3727 // every edge in the graph is the initial workset
3728 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3729 while( !edgeWorkSet.isEmpty() ) {
3730 RefEdge edgePrime = edgeWorkSet.iterator().next();
3731 edgeWorkSet.remove( edgePrime );
3733 RefSrcNode on = edgePrime.getSrc();
3734 if( !(on instanceof HeapRegionNode) ) {
3737 HeapRegionNode hrn = (HeapRegionNode) on;
3739 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3740 while( itrEdge.hasNext() ) {
3741 RefEdge edge = itrEdge.next();
3743 ReachSet prevResult = edge.getBetaNew();
3744 assert prevResult != null;
3746 ReachSet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
3748 if( prevResult.union( intersection ).size() > prevResult.size() ) {
3749 edge.setBetaNew( prevResult.union( intersection ) );
3750 edgeWorkSet.add( edge );
3755 // commit beta' (beta<-betaNew)
3756 edgeItr = res.iterator();
3757 while( edgeItr.hasNext() ) {
3758 edgeItr.next().applyBetaNew();
3764 ////////////////////////////////////////////////////
3765 // in merge() and equals() methods the suffix A
3766 // represents the passed in graph and the suffix
3767 // B refers to the graph in this object
3768 // Merging means to take the incoming graph A and
3769 // merge it into B, so after the operation graph B
3770 // is the final result.
3771 ////////////////////////////////////////////////////
3772 public void merge( ReachGraph rg ) {
3779 mergeRefSrcNodes(og);
3781 mergeParamIndexMappings(og);
3782 mergeAllocSites(og);
3783 mergeAccessPaths(og);
3784 mergeTempAndLabelCategories(og);
3789 protected void mergeRefSrcNodes(ReachGraph og) {
3790 Set sA = og.id2hrn.entrySet();
3791 Iterator iA = sA.iterator();
3792 while( iA.hasNext() ) {
3793 Map.Entry meA = (Map.Entry)iA.next();
3794 Integer idA = (Integer) meA.getKey();
3795 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3797 // if this graph doesn't have a node the
3798 // incoming graph has, allocate it
3799 if( !id2hrn.containsKey(idA) ) {
3800 HeapRegionNode hrnB = hrnA.copy();
3801 id2hrn.put(idA, hrnB);
3804 // otherwise this is a node present in both graphs
3805 // so make the new reachability set a union of the
3806 // nodes' reachability sets
3807 HeapRegionNode hrnB = id2hrn.get(idA);
3808 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
3812 // now add any label nodes that are in graph B but
3814 sA = og.td2vn.entrySet();
3816 while( iA.hasNext() ) {
3817 Map.Entry meA = (Map.Entry)iA.next();
3818 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3819 VariableNode lnA = (VariableNode) meA.getValue();
3821 // if the label doesn't exist in B, allocate and add it
3822 VariableNode lnB = getVariableNodeFromTemp(tdA);
3826 protected void mergeRefEdges(ReachGraph og) {
3829 Set sA = og.id2hrn.entrySet();
3830 Iterator iA = sA.iterator();
3831 while( iA.hasNext() ) {
3832 Map.Entry meA = (Map.Entry)iA.next();
3833 Integer idA = (Integer) meA.getKey();
3834 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3836 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3837 while( heapRegionsItrA.hasNext() ) {
3838 RefEdge edgeA = heapRegionsItrA.next();
3839 HeapRegionNode hrnChildA = edgeA.getDst();
3840 Integer idChildA = hrnChildA.getID();
3842 // at this point we know an edge in graph A exists
3843 // idA -> idChildA, does this exist in B?
3844 assert id2hrn.containsKey(idA);
3845 HeapRegionNode hrnB = id2hrn.get(idA);
3846 RefEdge edgeToMerge = null;
3848 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3849 while( heapRegionsItrB.hasNext() &&
3850 edgeToMerge == null ) {
3852 RefEdge edgeB = heapRegionsItrB.next();
3853 HeapRegionNode hrnChildB = edgeB.getDst();
3854 Integer idChildB = hrnChildB.getID();
3856 // don't use the RefEdge.equals() here because
3857 // we're talking about existence between graphs
3858 if( idChildB.equals( idChildA ) &&
3859 edgeB.typeAndFieldEquals( edgeA ) ) {
3861 edgeToMerge = edgeB;
3865 // if the edge from A was not found in B,
3867 if( edgeToMerge == null ) {
3868 assert id2hrn.containsKey(idChildA);
3869 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3870 edgeToMerge = edgeA.copy();
3871 edgeToMerge.setSrc(hrnB);
3872 edgeToMerge.setDst(hrnChildB);
3873 addRefEdge(hrnB, hrnChildB, edgeToMerge);
3875 // otherwise, the edge already existed in both graphs
3876 // so merge their reachability sets
3878 // just replace this beta set with the union
3879 assert edgeToMerge != null;
3880 edgeToMerge.setBeta(
3881 edgeToMerge.getBeta().union(edgeA.getBeta() )
3884 edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
3885 if( !edgeA.isInitialParam() ) {
3886 edgeToMerge.setIsInitialParam(false);
3892 // and then again with label nodes
3893 sA = og.td2vn.entrySet();
3895 while( iA.hasNext() ) {
3896 Map.Entry meA = (Map.Entry)iA.next();
3897 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3898 VariableNode lnA = (VariableNode) meA.getValue();
3900 Iterator<RefEdge> heapRegionsItrA = lnA.iteratorToReferencees();
3901 while( heapRegionsItrA.hasNext() ) {
3902 RefEdge edgeA = heapRegionsItrA.next();
3903 HeapRegionNode hrnChildA = edgeA.getDst();
3904 Integer idChildA = hrnChildA.getID();
3906 // at this point we know an edge in graph A exists
3907 // tdA -> idChildA, does this exist in B?
3908 assert td2vn.containsKey(tdA);
3909 VariableNode lnB = td2vn.get(tdA);
3910 RefEdge edgeToMerge = null;
3912 Iterator<RefEdge> heapRegionsItrB = lnB.iteratorToReferencees();
3913 while( heapRegionsItrB.hasNext() &&
3914 edgeToMerge == null ) {
3916 RefEdge edgeB = heapRegionsItrB.next();
3917 HeapRegionNode hrnChildB = edgeB.getDst();
3918 Integer idChildB = hrnChildB.getID();
3920 // don't use the RefEdge.equals() here because
3921 // we're talking about existence between graphs
3922 if( idChildB.equals( idChildA ) &&
3923 edgeB.typeAndFieldEquals( edgeA ) ) {
3925 edgeToMerge = edgeB;
3929 // if the edge from A was not found in B,
3931 if( edgeToMerge == null ) {
3932 assert id2hrn.containsKey(idChildA);
3933 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3934 edgeToMerge = edgeA.copy();
3935 edgeToMerge.setSrc(lnB);
3936 edgeToMerge.setDst(hrnChildB);
3937 addRefEdge(lnB, hrnChildB, edgeToMerge);
3939 // otherwise, the edge already existed in both graphs
3940 // so merge their reachability sets
3942 // just replace this beta set with the union
3943 edgeToMerge.setBeta(
3944 edgeToMerge.getBeta().union(edgeA.getBeta() )
3946 edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
3947 if( !edgeA.isInitialParam() ) {
3948 edgeToMerge.setIsInitialParam(false);
3955 // you should only merge ownership graphs that have the
3956 // same number of parameters, or if one or both parameter
3957 // index tables are empty
3958 protected void mergeParamIndexMappings(ReachGraph og) {
3960 if( idPrimary2paramIndexSet.size() == 0 ) {
3962 idPrimary2paramIndexSet = og.idPrimary2paramIndexSet;
3963 paramIndex2idPrimary = og.paramIndex2idPrimary;
3965 idSecondary2paramIndexSet = og.idSecondary2paramIndexSet;
3966 paramIndex2idSecondary = og.paramIndex2idSecondary;
3968 paramIndex2tdQ = og.paramIndex2tdQ;
3969 paramIndex2tdR = og.paramIndex2tdR;
3971 paramTokenPrimary2paramIndex = og.paramTokenPrimary2paramIndex;
3972 paramIndex2paramTokenPrimary = og.paramIndex2paramTokenPrimary;
3974 paramTokenSecondary2paramIndex = og.paramTokenSecondary2paramIndex;
3975 paramIndex2paramTokenSecondary = og.paramIndex2paramTokenSecondary;
3976 paramTokenSecondaryPlus2paramIndex = og.paramTokenSecondaryPlus2paramIndex;
3977 paramIndex2paramTokenSecondaryPlus = og.paramIndex2paramTokenSecondaryPlus;
3978 paramTokenSecondaryStar2paramIndex = og.paramTokenSecondaryStar2paramIndex;
3979 paramIndex2paramTokenSecondaryStar = og.paramIndex2paramTokenSecondaryStar;
3984 if( og.idPrimary2paramIndexSet.size() == 0 ) {
3986 og.idPrimary2paramIndexSet = idPrimary2paramIndexSet;
3987 og.paramIndex2idPrimary = paramIndex2idPrimary;
3989 og.idSecondary2paramIndexSet = idSecondary2paramIndexSet;
3990 og.paramIndex2idSecondary = paramIndex2idSecondary;
3992 og.paramIndex2tdQ = paramIndex2tdQ;
3993 og.paramIndex2tdR = paramIndex2tdR;
3995 og.paramTokenPrimary2paramIndex = paramTokenPrimary2paramIndex;
3996 og.paramIndex2paramTokenPrimary = paramIndex2paramTokenPrimary;
3998 og.paramTokenSecondary2paramIndex = paramTokenSecondary2paramIndex;
3999 og.paramIndex2paramTokenSecondary = paramIndex2paramTokenSecondary;
4000 og.paramTokenSecondaryPlus2paramIndex = paramTokenSecondaryPlus2paramIndex;
4001 og.paramIndex2paramTokenSecondaryPlus = paramIndex2paramTokenSecondaryPlus;
4002 og.paramTokenSecondaryStar2paramIndex = paramTokenSecondaryStar2paramIndex;
4003 og.paramIndex2paramTokenSecondaryStar = paramIndex2paramTokenSecondaryStar;
4008 assert idPrimary2paramIndexSet.size() == og.idPrimary2paramIndexSet.size();
4009 assert idSecondary2paramIndexSet.size() == og.idSecondary2paramIndexSet.size();
4012 protected void mergeAllocSites(ReachGraph og) {
4013 allocSites.addAll(og.allocSites);
4016 protected void mergeAccessPaths(ReachGraph og) {
4017 UtilAlgorithms.mergeHashtablesWithHashSetValues(temp2accessPaths,
4018 og.temp2accessPaths);
4021 protected void mergeTempAndLabelCategories(ReachGraph og) {
4022 outOfScopeTemps.addAll(og.outOfScopeTemps);
4023 outOfScopeLabels.addAll(og.outOfScopeLabels);
4024 parameterTemps.addAll(og.parameterTemps);
4025 parameterLabels.addAll(og.parameterLabels);
4030 // it is necessary in the equals() member functions
4031 // to "check both ways" when comparing the data
4032 // structures of two graphs. For instance, if all
4033 // edges between heap region nodes in graph A are
4034 // present and equal in graph B it is not sufficient
4035 // to say the graphs are equal. Consider that there
4036 // may be edges in graph B that are not in graph A.
4037 // the only way to know that all edges in both graphs
4038 // are equally present is to iterate over both data
4039 // structures and compare against the other graph.
4040 public boolean equals( ReachGraph rg ) {
4047 if( !areHeapRegionNodesEqual(og) ) {
4051 if( !areVariableNodesEqual(og) ) {
4055 if( !areRefEdgesEqual(og) ) {
4059 if( !areParamIndexMappingsEqual(og) ) {
4063 if( !areAccessPathsEqual(og) ) {
4067 // if everything is equal up to this point,
4068 // assert that allocSites is also equal--
4069 // this data is redundant and kept for efficiency
4070 assert allocSites .equals(og.allocSites );
4071 assert outOfScopeTemps .equals(og.outOfScopeTemps );
4072 assert outOfScopeLabels.equals(og.outOfScopeLabels);
4073 assert parameterTemps .equals(og.parameterTemps );
4074 assert parameterLabels .equals(og.parameterLabels );
4081 protected boolean areHeapRegionNodesEqual(ReachGraph og) {
4083 if( !areallHRNinAalsoinBandequal(this, og) ) {
4087 if( !areallHRNinAalsoinBandequal(og, this) ) {
4094 static protected boolean areallHRNinAalsoinBandequal(ReachGraph ogA,
4096 Set sA = ogA.id2hrn.entrySet();
4097 Iterator iA = sA.iterator();
4098 while( iA.hasNext() ) {
4099 Map.Entry meA = (Map.Entry)iA.next();
4100 Integer idA = (Integer) meA.getKey();
4101 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4103 if( !ogB.id2hrn.containsKey(idA) ) {
4107 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
4108 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
4117 protected boolean areVariableNodesEqual(ReachGraph og) {
4119 if( !areallLNinAalsoinBandequal(this, og) ) {
4123 if( !areallLNinAalsoinBandequal(og, this) ) {
4130 static protected boolean areallLNinAalsoinBandequal(ReachGraph ogA,
4132 Set sA = ogA.td2vn.entrySet();
4133 Iterator iA = sA.iterator();
4134 while( iA.hasNext() ) {
4135 Map.Entry meA = (Map.Entry)iA.next();
4136 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4138 if( !ogB.td2vn.containsKey(tdA) ) {
4147 protected boolean areRefEdgesEqual(ReachGraph og) {
4148 if( !areallREinAandBequal(this, og) ) {
4155 static protected boolean areallREinAandBequal(ReachGraph ogA,
4158 // check all the heap region->heap region edges
4159 Set sA = ogA.id2hrn.entrySet();
4160 Iterator iA = sA.iterator();
4161 while( iA.hasNext() ) {
4162 Map.Entry meA = (Map.Entry)iA.next();
4163 Integer idA = (Integer) meA.getKey();
4164 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4166 // we should have already checked that the same
4167 // heap regions exist in both graphs
4168 assert ogB.id2hrn.containsKey(idA);
4170 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
4174 // then check every edge in B for presence in A, starting
4175 // from the same parent HeapRegionNode
4176 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
4178 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
4183 // then check all the label->heap region edges
4184 sA = ogA.td2vn.entrySet();
4186 while( iA.hasNext() ) {
4187 Map.Entry meA = (Map.Entry)iA.next();
4188 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4189 VariableNode lnA = (VariableNode) meA.getValue();
4191 // we should have already checked that the same
4192 // label nodes exist in both graphs
4193 assert ogB.td2vn.containsKey(tdA);
4195 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
4199 // then check every edge in B for presence in A, starting
4200 // from the same parent VariableNode
4201 VariableNode lnB = ogB.td2vn.get(tdA);
4203 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
4212 static protected boolean areallREfromAequaltoB(ReachGraph ogA,
4216 Iterator<RefEdge> itrA = onA.iteratorToReferencees();
4217 while( itrA.hasNext() ) {
4218 RefEdge edgeA = itrA.next();
4219 HeapRegionNode hrnChildA = edgeA.getDst();
4220 Integer idChildA = hrnChildA.getID();
4222 assert ogB.id2hrn.containsKey(idChildA);
4224 // at this point we know an edge in graph A exists
4225 // onA -> idChildA, does this exact edge exist in B?
4226 boolean edgeFound = false;
4228 RefSrcNode onB = null;
4229 if( onA instanceof HeapRegionNode ) {
4230 HeapRegionNode hrnA = (HeapRegionNode) onA;
4231 onB = ogB.id2hrn.get(hrnA.getID() );
4233 VariableNode lnA = (VariableNode) onA;
4234 onB = ogB.td2vn.get(lnA.getTempDescriptor() );
4237 Iterator<RefEdge> itrB = onB.iteratorToReferencees();
4238 while( itrB.hasNext() ) {
4239 RefEdge edgeB = itrB.next();
4240 HeapRegionNode hrnChildB = edgeB.getDst();
4241 Integer idChildB = hrnChildB.getID();
4243 if( idChildA.equals( idChildB ) &&
4244 edgeA.typeAndFieldEquals( edgeB ) ) {
4246 // there is an edge in the right place with the right field,
4247 // but do they have the same attributes?
4248 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
4263 protected boolean areParamIndexMappingsEqual(ReachGraph og) {
4265 if( idPrimary2paramIndexSet.size() != og.idPrimary2paramIndexSet.size() ) {
4269 if( idSecondary2paramIndexSet.size() != og.idSecondary2paramIndexSet.size() ) {
4277 protected boolean areAccessPathsEqual(ReachGraph og) {
4278 return temp2accessPaths.equals( og.temp2accessPaths );
4283 public Set<HeapRegionNode> hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) {
4284 assert hrn1 != null;
4285 assert hrn2 != null;
4287 // then get the various tokens for these heap regions
4288 ReachTuple h1 = new ReachTuple(hrn1.getID(),
4289 !hrn1.isSingleObject(),
4290 ReachTuple.ARITY_ONE).makeCanonical();
4292 ReachTuple h1plus = new ReachTuple(hrn1.getID(),
4293 !hrn1.isSingleObject(),
4294 ReachTuple.ARITY_ONEORMORE).makeCanonical();
4296 ReachTuple h1star = new ReachTuple(hrn1.getID(),
4297 !hrn1.isSingleObject(),
4298 ReachTuple.ARITY_ZEROORMORE).makeCanonical();
4300 ReachTuple h2 = new ReachTuple(hrn2.getID(),
4301 !hrn2.isSingleObject(),
4302 ReachTuple.ARITY_ONE).makeCanonical();
4304 ReachTuple h2plus = new ReachTuple(hrn2.getID(),
4305 !hrn2.isSingleObject(),
4306 ReachTuple.ARITY_ONEORMORE).makeCanonical();
4308 ReachTuple h2star = new ReachTuple(hrn2.getID(),
4309 !hrn2.isSingleObject(),
4310 ReachTuple.ARITY_ZEROORMORE).makeCanonical();
4312 // then get the merged beta of all out-going edges from these heap regions
4313 ReachSet beta1 = new ReachSet().makeCanonical();
4314 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4315 while( itrEdge.hasNext() ) {
4316 RefEdge edge = itrEdge.next();
4317 beta1 = beta1.union( edge.getBeta() );
4320 ReachSet beta2 = new ReachSet().makeCanonical();
4321 itrEdge = hrn2.iteratorToReferencees();
4322 while( itrEdge.hasNext() ) {
4323 RefEdge edge = itrEdge.next();
4324 beta2 = beta2.union( edge.getBeta() );
4327 boolean aliasDetected = false;
4329 // only do this one if they are different tokens
4331 beta1.containsTupleSetWithBoth(h1, h2) ) {
4332 aliasDetected = true;
4334 if( beta1.containsTupleSetWithBoth(h1plus, h2) ) {
4335 aliasDetected = true;
4337 if( beta1.containsTupleSetWithBoth(h1star, h2) ) {
4338 aliasDetected = true;
4340 if( beta1.containsTupleSetWithBoth(h1, h2plus) ) {
4341 aliasDetected = true;
4343 if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) {
4344 aliasDetected = true;
4346 if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) {
4347 aliasDetected = true;
4349 if( beta1.containsTupleSetWithBoth(h1, h2star) ) {
4350 aliasDetected = true;
4352 if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) {
4353 aliasDetected = true;
4355 if( beta1.containsTupleSetWithBoth(h1star, h2star) ) {
4356 aliasDetected = true;
4360 beta2.containsTupleSetWithBoth(h1, h2) ) {
4361 aliasDetected = true;
4363 if( beta2.containsTupleSetWithBoth(h1plus, h2) ) {
4364 aliasDetected = true;
4366 if( beta2.containsTupleSetWithBoth(h1star, h2) ) {
4367 aliasDetected = true;
4369 if( beta2.containsTupleSetWithBoth(h1, h2plus) ) {
4370 aliasDetected = true;
4372 if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) {
4373 aliasDetected = true;
4375 if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) {
4376 aliasDetected = true;
4378 if( beta2.containsTupleSetWithBoth(h1, h2star) ) {
4379 aliasDetected = true;
4381 if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) {
4382 aliasDetected = true;
4384 if( beta2.containsTupleSetWithBoth(h1star, h2star) ) {
4385 aliasDetected = true;
4388 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4389 if( aliasDetected ) {
4390 common = findCommonReachableNodes( hrn1, hrn2 );
4391 if( !(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP) ) {
4392 assert !common.isEmpty();
4400 public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
4402 // get parameter 1's heap regions
4403 assert paramIndex2idPrimary.containsKey(paramIndex1);
4404 Integer idParamPri1 = paramIndex2idPrimary.get(paramIndex1);
4406 assert id2hrn.containsKey(idParamPri1);
4407 HeapRegionNode hrnParamPri1 = id2hrn.get(idParamPri1);
4408 assert hrnParamPri1 != null;
4410 HeapRegionNode hrnParamSec1 = null;
4411 if( paramIndex2idSecondary.containsKey(paramIndex1) ) {
4412 Integer idParamSec1 = paramIndex2idSecondary.get(paramIndex1);
4414 assert id2hrn.containsKey(idParamSec1);
4415 hrnParamSec1 = id2hrn.get(idParamSec1);
4416 assert hrnParamSec1 != null;
4420 // get the other parameter
4421 assert paramIndex2idPrimary.containsKey(paramIndex2);
4422 Integer idParamPri2 = paramIndex2idPrimary.get(paramIndex2);
4424 assert id2hrn.containsKey(idParamPri2);
4425 HeapRegionNode hrnParamPri2 = id2hrn.get(idParamPri2);
4426 assert hrnParamPri2 != null;
4428 HeapRegionNode hrnParamSec2 = null;
4429 if( paramIndex2idSecondary.containsKey(paramIndex2) ) {
4430 Integer idParamSec2 = paramIndex2idSecondary.get(paramIndex2);
4432 assert id2hrn.containsKey(idParamSec2);
4433 hrnParamSec2 = id2hrn.get(idParamSec2);
4434 assert hrnParamSec2 != null;
4437 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4438 common.addAll( hasPotentialAlias( hrnParamPri1, hrnParamPri2 ) );
4440 if( hrnParamSec1 != null ) {
4441 common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamPri2 ) );
4444 if( hrnParamSec2 != null ) {
4445 common.addAll( hasPotentialAlias( hrnParamSec2, hrnParamPri1 ) );
4448 if( hrnParamSec1 != null && hrnParamSec2 != null ) {
4449 common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamSec2 ) );
4456 public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex, AllocSite as) {
4458 // get parameter's heap regions
4459 assert paramIndex2idPrimary.containsKey(paramIndex);
4460 Integer idParamPri = paramIndex2idPrimary.get(paramIndex);
4462 assert id2hrn.containsKey(idParamPri);
4463 HeapRegionNode hrnParamPri = id2hrn.get(idParamPri);
4464 assert hrnParamPri != null;
4466 HeapRegionNode hrnParamSec = null;
4467 if( paramIndex2idSecondary.containsKey(paramIndex) ) {
4468 Integer idParamSec = paramIndex2idSecondary.get(paramIndex);
4470 assert id2hrn.containsKey(idParamSec);
4471 hrnParamSec = id2hrn.get(idParamSec);
4472 assert hrnParamSec != null;
4476 assert id2hrn.containsKey( as.getSummary() );
4477 HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() );
4478 assert hrnSummary != null;
4480 Set<HeapRegionNode> common = hasPotentialAlias( hrnParamPri, hrnSummary );
4482 if( hrnParamSec != null ) {
4483 common.addAll( hasPotentialAlias( hrnParamSec, hrnSummary ) );
4486 // check for other nodes
4487 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4489 assert id2hrn.containsKey( as.getIthOldest( i ) );
4490 HeapRegionNode hrnIthOldest = id2hrn.get( as.getIthOldest( i ) );
4491 assert hrnIthOldest != null;
4493 common = hasPotentialAlias( hrnParamPri, hrnIthOldest );
4495 if( hrnParamSec != null ) {
4496 common.addAll( hasPotentialAlias( hrnParamSec, hrnIthOldest ) );
4504 public Set<HeapRegionNode> hasPotentialAlias(AllocSite as1, AllocSite as2) {
4506 // get summary node 1's alpha
4507 Integer idSum1 = as1.getSummary();
4508 assert id2hrn.containsKey(idSum1);
4509 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
4510 assert hrnSum1 != null;
4512 // get summary node 2's alpha
4513 Integer idSum2 = as2.getSummary();
4514 assert id2hrn.containsKey(idSum2);
4515 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
4516 assert hrnSum2 != null;
4518 Set<HeapRegionNode> common = hasPotentialAlias( hrnSum1, hrnSum2 );
4520 // check sum2 against alloc1 nodes
4521 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
4522 Integer idI1 = as1.getIthOldest(i);
4523 assert id2hrn.containsKey(idI1);
4524 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4525 assert hrnI1 != null;
4527 common.addAll( hasPotentialAlias( hrnI1, hrnSum2 ) );
4530 // check sum1 against alloc2 nodes
4531 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
4532 Integer idI2 = as2.getIthOldest(i);
4533 assert id2hrn.containsKey(idI2);
4534 HeapRegionNode hrnI2 = id2hrn.get(idI2);
4535 assert hrnI2 != null;
4537 common.addAll( hasPotentialAlias( hrnSum1, hrnI2 ) );
4539 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4540 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
4541 Integer idI1 = as1.getIthOldest(j);
4543 // if these are the same site, don't look for the same token, no alias.
4544 // different tokens of the same site could alias together though
4545 if( idI1.equals( idI2 ) ) {
4549 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4551 common.addAll( hasPotentialAlias( hrnI1, hrnI2 ) );
4559 public Set<HeapRegionNode> findCommonReachableNodes( HeapRegionNode hrn1,
4560 HeapRegionNode hrn2 ) {
4562 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
4563 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
4565 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
4566 todoNodes1.add( hrn1 );
4568 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
4569 todoNodes2.add( hrn2 );
4571 // follow links until all reachable nodes have been found
4572 while( !todoNodes1.isEmpty() ) {
4573 HeapRegionNode hrn = todoNodes1.iterator().next();
4574 todoNodes1.remove( hrn );
4575 reachableNodes1.add(hrn);
4577 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
4578 while( edgeItr.hasNext() ) {
4579 RefEdge edge = edgeItr.next();
4581 if( !reachableNodes1.contains( edge.getDst() ) ) {
4582 todoNodes1.add( edge.getDst() );
4587 while( !todoNodes2.isEmpty() ) {
4588 HeapRegionNode hrn = todoNodes2.iterator().next();
4589 todoNodes2.remove( hrn );
4590 reachableNodes2.add(hrn);
4592 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
4593 while( edgeItr.hasNext() ) {
4594 RefEdge edge = edgeItr.next();
4596 if( !reachableNodes2.contains( edge.getDst() ) ) {
4597 todoNodes2.add( edge.getDst() );
4602 Set<HeapRegionNode> intersection =
4603 new HashSet<HeapRegionNode>( reachableNodes1 );
4605 intersection.retainAll( reachableNodes2 );
4607 return intersection;
4611 public void writeGraph(String graphName,
4612 boolean writeLabels,
4613 boolean labelSelect,
4614 boolean pruneGarbage,
4615 boolean writeReferencers,
4616 boolean writeParamMappings,
4617 boolean hideSubsetReachability,
4618 boolean hideEdgeTaints
4619 ) throws java.io.IOException {
4621 // remove all non-word characters from the graph name so
4622 // the filename and identifier in dot don't cause errors
4623 graphName = graphName.replaceAll("[\\W]", "");
4625 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
4626 bw.write("digraph "+graphName+" {\n");
4628 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4630 // then visit every heap region node
4631 Set s = id2hrn.entrySet();
4632 Iterator i = s.iterator();
4633 while( i.hasNext() ) {
4634 Map.Entry me = (Map.Entry)i.next();
4635 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4637 if( !pruneGarbage ||
4638 (hrn.isFlagged() && hrn.getID() > 0) ||
4639 hrn.getDescription().startsWith("param")
4642 if( !visited.contains(hrn) ) {
4643 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4649 hideSubsetReachability,
4655 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4658 // then visit every label node, useful for debugging
4660 s = td2vn.entrySet();
4662 while( i.hasNext() ) {
4663 Map.Entry me = (Map.Entry)i.next();
4664 VariableNode ln = (VariableNode) me.getValue();
4667 String labelStr = ln.getTempDescriptorString();
4668 if( labelStr.startsWith("___temp") ||
4669 labelStr.startsWith("___dst") ||
4670 labelStr.startsWith("___srctmp") ||
4671 labelStr.startsWith("___neverused") ||
4672 labelStr.contains(qString) ||
4673 labelStr.contains(rString) ||
4674 labelStr.contains(blobString)
4680 //bw.write(" "+ln.toString() + ";\n");
4682 Iterator<RefEdge> heapRegionsItr = ln.iteratorToReferencees();
4683 while( heapRegionsItr.hasNext() ) {
4684 RefEdge edge = heapRegionsItr.next();
4685 HeapRegionNode hrn = edge.getDst();
4687 if( pruneGarbage && !visited.contains(hrn) ) {
4688 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4694 hideSubsetReachability,
4698 bw.write(" " + ln.toString() +
4699 " -> " + hrn.toString() +
4700 "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
4712 protected void traverseHeapRegionNodes(int mode,
4716 HashSet<HeapRegionNode> visited,
4717 boolean writeReferencers,
4718 boolean hideSubsetReachability,
4719 boolean hideEdgeTaints
4720 ) throws java.io.IOException {
4722 if( visited.contains(hrn) ) {
4728 case VISIT_HRN_WRITE_FULL:
4730 String attributes = "[";
4732 if( hrn.isSingleObject() ) {
4733 attributes += "shape=box";
4735 attributes += "shape=Msquare";
4738 if( hrn.isFlagged() ) {
4739 attributes += ",style=filled,fillcolor=lightgrey";
4742 attributes += ",label=\"ID" +
4746 if( hrn.getType() != null ) {
4747 attributes += hrn.getType().toPrettyString() + "\\n";
4750 attributes += hrn.getDescription() +
4752 hrn.getAlphaString(hideSubsetReachability) +
4755 bw.write(" " + hrn.toString() + attributes + ";\n");
4761 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4762 while( childRegionsItr.hasNext() ) {
4763 RefEdge edge = childRegionsItr.next();
4764 HeapRegionNode hrnChild = edge.getDst();
4767 case VISIT_HRN_WRITE_FULL:
4768 bw.write(" " + hrn.toString() +
4769 " -> " + hrnChild.toString() +
4770 "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
4776 traverseHeapRegionNodes(mode,
4782 hideSubsetReachability,
4787 public int getTaintIdentifierFromHRN(HeapRegionNode hrn){
4788 HashSet<RefEdge> referenceEdges=hrn.referencers;
4789 Iterator<RefEdge> iter=referenceEdges.iterator();
4791 int taintIdentifier=0;
4792 while(iter.hasNext()){
4793 RefEdge edge=iter.next();
4794 taintIdentifier=taintIdentifier | edge.getTaintIdentifier();
4797 return taintIdentifier;
4801 public void propagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet){
4803 HashSet<RefEdge> setEdge=hrn.referencers;
4804 Iterator<RefEdge> iter=setEdge.iterator();
4805 while(iter.hasNext()){
4806 RefEdge edge= iter.next();
4807 edge.unionTaintIdentifier(newTaintIdentifier);
4808 if(edge.getSrc() instanceof HeapRegionNode){
4810 HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
4811 //check whether it is reflexive edge
4812 if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){
4813 visitedSet.add(refHRN);
4814 propagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);
4822 public void depropagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet){
4824 HashSet<RefEdge> setEdge=hrn.referencers;
4825 Iterator<RefEdge> iter=setEdge.iterator();
4826 while(iter.hasNext()){
4827 RefEdge edge= iter.next();
4828 edge.minusTaintIdentifier(newTaintIdentifier);
4829 if(edge.getSrc() instanceof HeapRegionNode){
4831 HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
4832 //check whether it is reflexive edge
4833 if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){
4834 visitedSet.add(refHRN);
4835 depropagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);
4844 // in this analysis specifically:
4845 // we have a notion that a null type is the "match any" type,
4846 // so wrap calls to the utility methods that deal with null
4847 public TypeDescriptor mostSpecificType( TypeDescriptor td1,
4848 TypeDescriptor td2 ) {
4855 if( td1.isNull() ) {
4858 if( td2.isNull() ) {
4861 return typeUtil.mostSpecific( td1, td2 );
4864 public TypeDescriptor mostSpecificType( TypeDescriptor td1,
4866 TypeDescriptor td3 ) {
4868 return mostSpecificType( td1,
4869 mostSpecificType( td2, td3 )
4873 public TypeDescriptor mostSpecificType( TypeDescriptor td1,
4876 TypeDescriptor td4 ) {
4878 return mostSpecificType( mostSpecificType( td1, td2 ),
4879 mostSpecificType( td3, td4 )
4883 // remember, in this analysis a null type means "any type"
4884 public boolean isSuperiorType( TypeDescriptor possibleSuper,
4885 TypeDescriptor possibleChild ) {
4886 if( possibleSuper == null ||
4887 possibleChild == null ) {
4891 if( possibleSuper.isNull() ||
4892 possibleChild.isNull() ) {
4896 return typeUtil.isSuperorType( possibleSuper, possibleChild );
4899 public String generateUniqueIdentifier(FlatMethod fm, int paramIdx, String type){
4901 //type: A->aliapsed parameter heap region
4902 // P -> primary paramter heap region
4903 // S -> secondary paramter heap region
4906 if(type.equals("A")){
4908 identifier="FM"+fm.hashCode()+".A";
4910 identifier="FM"+fm.hashCode()+"."+paramIdx+"."+type;
4916 public String generateUniqueIdentifier(AllocSite as, int age, boolean isSummary){
4920 FlatNew fn=as.getFlatNew();
4923 identifier="FN"+fn.hashCode()+".S";
4925 identifier="FN"+fn.hashCode()+"."+age;