1 package Analysis.OwnershipAnalysis;
8 public class OwnershipGraph {
10 // use to disable improvements for comparison
11 protected static final boolean DISABLE_STRONG_UPDATES = false;
12 protected static final boolean DISABLE_GLOBAL_SWEEP = false;
15 private int allocationDepth;
16 private TypeUtil typeUtil;
18 // there was already one other very similar reason
19 // for traversing heap nodes that is no longer needed
20 // instead of writing a new heap region visitor, use
21 // the existing method with a new mode to describe what
22 // actions to take during the traversal
23 protected static final int VISIT_HRN_WRITE_FULL = 0;
25 protected static final String qString = new String( "Q_spec_" );
26 protected static final String rString = new String( "R_spec_" );
27 protected static final String blobString = new String( "_AliasBlob___" );
29 protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
30 protected static final TempDescriptor tdAliasBlob = new TempDescriptor( blobString );
32 protected static final TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
33 protected static final ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical();
34 protected static final ReachabilitySet rsWttsEmpty = new ReachabilitySet( ttsEmpty ).makeCanonical();
36 // add a bogus entry with the identity rule for easy rewrite
37 // of new callee nodes and edges, doesn't belong to any parameter
38 protected static final int bogusParamIndexInt = -2;
39 protected static final Integer bogusID = new Integer( bogusParamIndexInt );
40 protected static final Integer bogusIndex = new Integer( bogusParamIndexInt );
41 protected static final TokenTuple bogusToken = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONE ).makeCanonical();
42 protected static final TokenTuple bogusTokenPlus = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONEORMORE ).makeCanonical();
43 protected static final TokenTuple bogusTokenStar = new TokenTuple( bogusID, true, TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
44 protected static final ReachabilitySet rsIdentity =
45 new ReachabilitySet( new TokenTupleSet( bogusToken ).makeCanonical() ).makeCanonical();
48 public Hashtable<Integer, HeapRegionNode> id2hrn;
49 public Hashtable<TempDescriptor, LabelNode > td2ln;
51 public Hashtable<Integer, Set<Integer> > idPrimary2paramIndexSet;
52 public Hashtable<Integer, Integer > paramIndex2idPrimary;
54 public Hashtable<Integer, Set<Integer> > idSecondary2paramIndexSet;
55 public Hashtable<Integer, Integer > paramIndex2idSecondary;
57 public Hashtable<Integer, TempDescriptor> paramIndex2tdQ;
58 public Hashtable<Integer, TempDescriptor> paramIndex2tdR;
61 public HashSet<AllocationSite> allocationSites;
64 public Hashtable<TokenTuple, Integer> paramTokenPrimary2paramIndex;
65 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenPrimary;
67 public Hashtable<TokenTuple, Integer> paramTokenSecondary2paramIndex;
68 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondary;
69 public Hashtable<TokenTuple, Integer> paramTokenSecondaryPlus2paramIndex;
70 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondaryPlus;
71 public Hashtable<TokenTuple, Integer> paramTokenSecondaryStar2paramIndex;
72 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondaryStar;
75 public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
76 this.allocationDepth = allocationDepth;
77 this.typeUtil = typeUtil;
79 id2hrn = new Hashtable<Integer, HeapRegionNode>();
80 td2ln = new Hashtable<TempDescriptor, LabelNode >();
81 idPrimary2paramIndexSet = new Hashtable<Integer, Set<Integer> >();
82 paramIndex2idPrimary = new Hashtable<Integer, Integer >();
83 idSecondary2paramIndexSet = new Hashtable<Integer, Set<Integer> >();
84 paramIndex2idSecondary = new Hashtable<Integer, Integer >();
85 paramIndex2tdQ = new Hashtable<Integer, TempDescriptor>();
86 paramIndex2tdR = new Hashtable<Integer, TempDescriptor>();
88 paramTokenPrimary2paramIndex = new Hashtable<TokenTuple, Integer >();
89 paramIndex2paramTokenPrimary = new Hashtable<Integer, TokenTuple >();
91 paramTokenSecondary2paramIndex = new Hashtable<TokenTuple, Integer >();
92 paramIndex2paramTokenSecondary = new Hashtable<Integer, TokenTuple >();
93 paramTokenSecondaryPlus2paramIndex = new Hashtable<TokenTuple, Integer >();
94 paramIndex2paramTokenSecondaryPlus = new Hashtable<Integer, TokenTuple >();
95 paramTokenSecondaryStar2paramIndex = new Hashtable<TokenTuple, Integer >();
96 paramIndex2paramTokenSecondaryStar = new Hashtable<Integer, TokenTuple >();
98 allocationSites = new HashSet <AllocationSite>();
102 // label nodes are much easier to deal with than
103 // heap region nodes. Whenever there is a request
104 // for the label node that is associated with a
105 // temp descriptor we can either find it or make a
106 // new one and return it. This is because temp
107 // descriptors are globally unique and every label
108 // node is mapped to exactly one temp descriptor.
109 protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
112 if( !td2ln.containsKey(td) ) {
113 td2ln.put(td, new LabelNode(td) );
116 return td2ln.get(td);
120 // the reason for this method is to have the option
121 // creating new heap regions with specific IDs, or
122 // duplicating heap regions with specific IDs (especially
123 // in the merge() operation) or to create new heap
124 // regions with a new unique ID.
125 protected HeapRegionNode
126 createNewHeapRegionNode(Integer id,
127 boolean isSingleObject,
128 boolean isNewSummary,
132 AllocationSite allocSite,
133 ReachabilitySet alpha,
134 String description) {
136 boolean markForAnalysis = isFlagged || isParameter;
138 TypeDescriptor typeToUse = null;
139 if( allocSite != null ) {
140 typeToUse = allocSite.getType();
145 if( allocSite != null && allocSite.getDisjointId() != null ) {
146 markForAnalysis = true;
150 id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
153 if( alpha == null ) {
154 if( markForAnalysis ) {
155 alpha = new ReachabilitySet(
162 alpha = new ReachabilitySet(
163 new TokenTupleSet().makeCanonical()
168 HeapRegionNode hrn = new HeapRegionNode(id,
183 ////////////////////////////////////////////////
185 // Low-level referencee and referencer methods
187 // These methods provide the lowest level for
188 // creating references between ownership nodes
189 // and handling the details of maintaining both
190 // list of referencers and referencees.
192 ////////////////////////////////////////////////
193 protected void addReferenceEdge(OwnershipNode referencer,
194 HeapRegionNode referencee,
195 ReferenceEdge edge) {
196 assert referencer != null;
197 assert referencee != null;
199 assert edge.getSrc() == referencer;
200 assert edge.getDst() == referencee;
202 referencer.addReferencee(edge);
203 referencee.addReferencer(edge);
206 protected void removeReferenceEdge(OwnershipNode referencer,
207 HeapRegionNode referencee,
210 assert referencer != null;
211 assert referencee != null;
213 ReferenceEdge edge = referencer.getReferenceTo(referencee,
217 assert edge == referencee.getReferenceFrom(referencer,
221 // int oldTaint=edge.getTaintIdentifier();
222 // if(referencer instanceof HeapRegionNode){
223 // depropagateTaintIdentifier((HeapRegionNode)referencer,oldTaint,new HashSet<HeapRegionNode>());
226 referencer.removeReferencee(edge);
227 referencee.removeReferencer(edge);
230 protected void clearReferenceEdgesFrom(OwnershipNode referencer,
234 assert referencer != null;
236 // get a copy of the set to iterate over, otherwise
237 // we will be trying to take apart the set as we
238 // are iterating over it, which won't work
239 Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
240 while( i.hasNext() ) {
241 ReferenceEdge edge = i.next();
244 (edge.typeEquals( type ) && edge.fieldEquals( field ))
247 HeapRegionNode referencee = edge.getDst();
249 removeReferenceEdge(referencer,
257 protected void clearReferenceEdgesTo(HeapRegionNode referencee,
261 assert referencee != null;
263 // get a copy of the set to iterate over, otherwise
264 // we will be trying to take apart the set as we
265 // are iterating over it, which won't work
266 Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
267 while( i.hasNext() ) {
268 ReferenceEdge edge = i.next();
271 (edge.typeEquals( type ) && edge.fieldEquals( field ))
274 OwnershipNode referencer = edge.getSrc();
276 removeReferenceEdge(referencer,
285 ////////////////////////////////////////////////////
287 // Assignment Operation Methods
289 // These methods are high-level operations for
290 // modeling program assignment statements using
291 // the low-level reference create/remove methods
294 // The destination in an assignment statement is
295 // going to have new references. The method of
296 // determining the references depends on the type
297 // of the FlatNode assignment and the predicates
298 // of the nodes and edges involved.
300 ////////////////////////////////////////////////////
301 public void assignTempXEqualToTempY(TempDescriptor x,
304 LabelNode lnX = getLabelNodeFromTemp(x);
305 LabelNode lnY = getLabelNodeFromTemp(y);
307 clearReferenceEdgesFrom(lnX, null, null, true);
309 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
310 while( itrYhrn.hasNext() ) {
311 ReferenceEdge edgeY = itrYhrn.next();
312 HeapRegionNode referencee = edgeY.getDst();
313 ReferenceEdge edgeNew = edgeY.copy();
316 addReferenceEdge(lnX, referencee, edgeNew);
321 public void assignTypedTempXEqualToTempY(TempDescriptor x,
323 TypeDescriptor type) {
325 LabelNode lnX = getLabelNodeFromTemp(x);
326 LabelNode lnY = getLabelNodeFromTemp(y);
328 clearReferenceEdgesFrom(lnX, null, null, true);
330 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
331 while( itrYhrn.hasNext() ) {
332 ReferenceEdge edgeY = itrYhrn.next();
333 HeapRegionNode referencee = edgeY.getDst();
334 ReferenceEdge edgeNew = edgeY.copy();
335 edgeNew.setSrc( lnX );
336 edgeNew.setType( type );
337 edgeNew.setField( null );
339 addReferenceEdge(lnX, referencee, edgeNew);
344 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
347 LabelNode lnX = getLabelNodeFromTemp(x);
348 LabelNode lnY = getLabelNodeFromTemp(y);
350 clearReferenceEdgesFrom(lnX, null, null, true);
352 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
353 while( itrYhrn.hasNext() ) {
354 ReferenceEdge edgeY = itrYhrn.next();
355 HeapRegionNode hrnY = edgeY.getDst();
356 ReachabilitySet betaY = edgeY.getBeta();
358 Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
359 while( itrHrnFhrn.hasNext() ) {
360 ReferenceEdge edgeHrn = itrHrnFhrn.next();
361 HeapRegionNode hrnHrn = edgeHrn.getDst();
362 ReachabilitySet betaHrn = edgeHrn.getBeta();
364 if( edgeHrn.getType() == null ||
365 (edgeHrn.getType() .equals( f.getType() ) &&
366 edgeHrn.getField().equals( f.getSymbol() ) )
369 ReferenceEdge edgeNew = new ReferenceEdge(lnX,
374 betaY.intersection(betaHrn) );
376 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnHrn);
377 edgeNew.setTaintIdentifier(newTaintIdentifier);
379 addReferenceEdge(lnX, hrnHrn, edgeNew);
386 public void assignTempXFieldFEqualToTempY(TempDescriptor x,
389 LabelNode lnX = getLabelNodeFromTemp(x);
390 LabelNode lnY = getLabelNodeFromTemp(y);
392 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
393 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
395 // first look for possible strong updates and remove those edges
396 boolean strongUpdate = false;
398 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
399 while( itrXhrn.hasNext() ) {
400 ReferenceEdge edgeX = itrXhrn.next();
401 HeapRegionNode hrnX = edgeX.getDst();
403 // we can do a strong update here if one of two cases holds
405 f != OwnershipAnalysis.getArrayField( f.getType() ) &&
406 ( (hrnX.getNumReferencers() == 1) || // case 1
407 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
410 if( !DISABLE_STRONG_UPDATES ) {
412 clearReferenceEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
417 // then do all token propagation
418 itrXhrn = lnX.iteratorToReferencees();
419 while( itrXhrn.hasNext() ) {
420 ReferenceEdge edgeX = itrXhrn.next();
421 HeapRegionNode hrnX = edgeX.getDst();
422 ReachabilitySet betaX = edgeX.getBeta();
424 ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
426 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
427 while( itrYhrn.hasNext() ) {
428 ReferenceEdge edgeY = itrYhrn.next();
429 HeapRegionNode hrnY = edgeY.getDst();
430 ReachabilitySet O = edgeY.getBeta();
433 // propagate tokens over nodes starting from hrnSrc, and it will
434 // take care of propagating back up edges from any touched nodes
435 ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
436 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
439 // then propagate back just up the edges from hrn
440 ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
441 HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
443 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
444 new Hashtable<ReferenceEdge, ChangeTupleSet>();
446 Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
447 while( referItr.hasNext() ) {
448 ReferenceEdge edgeUpstream = referItr.next();
449 todoEdges.add(edgeUpstream);
450 edgePlannedChanges.put(edgeUpstream, Cx);
453 propagateTokensOverEdges(todoEdges,
460 // apply the updates to reachability
461 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
462 while( nodeItr.hasNext() ) {
463 nodeItr.next().applyAlphaNew();
466 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
467 while( edgeItr.hasNext() ) {
468 edgeItr.next().applyBetaNew();
472 // then go back through and add the new edges
473 itrXhrn = lnX.iteratorToReferencees();
474 while( itrXhrn.hasNext() ) {
475 ReferenceEdge edgeX = itrXhrn.next();
476 HeapRegionNode hrnX = edgeX.getDst();
478 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
479 while( itrYhrn.hasNext() ) {
480 ReferenceEdge edgeY = itrYhrn.next();
481 HeapRegionNode hrnY = edgeY.getDst();
483 // prepare the new reference edge hrnX.f -> hrnY
484 ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
489 edgeY.getBeta().pruneBy( hrnX.getAlpha() )
492 // look to see if an edge with same field exists
493 // and merge with it, otherwise just add the edge
494 ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY,
498 if( edgeExisting != null ) {
499 edgeExisting.setBeta(
500 edgeExisting.getBeta().union( edgeNew.getBeta() )
502 if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){
503 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY);
504 edgeExisting.unionTaintIdentifier(newTaintIdentifier);
506 // a new edge here cannot be reflexive, so existing will
507 // always be also not reflexive anymore
508 edgeExisting.setIsInitialParam( false );
511 if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){
512 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY);
513 edgeNew.setTaintIdentifier(newTaintIdentifier);
515 //currently, taint isn't propagated through the chain of refrences
516 //propagateTaintIdentifier(hrnX,newTaintIdentifier,new HashSet<HeapRegionNode>());
517 addReferenceEdge( hrnX, hrnY, edgeNew );
522 // if there was a strong update, make sure to improve
523 // reachability with a global sweep
525 if( !DISABLE_GLOBAL_SWEEP ) {
534 // the parameter model is to use a single-object heap region
535 // for the primary parameter, and a multiple-object heap
536 // region for the secondary objects reachable through the
537 // primary object, if necessary
538 public void assignTempEqualToParamAlloc( TempDescriptor td,
540 Integer paramIndex ) {
543 TypeDescriptor typeParam = td.getType();
544 assert typeParam != null;
546 // either the parameter is an array or a class to be in this method
547 assert typeParam.isArray() || typeParam.isClass();
549 // discover some info from the param type and use it below
550 // to get parameter model as precise as we can
551 boolean createSecondaryRegion = false;
552 Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
553 Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
555 // there might be an element reference for array types
556 if( typeParam.isArray() ) {
557 // only bother with this if the dereferenced type can
558 // affect reachability
559 TypeDescriptor typeDeref = typeParam.dereference();
560 if( !typeDeref.isImmutable() || typeDeref.isArray() ) {
561 primary2secondaryFields.add(
562 OwnershipAnalysis.getArrayField( typeDeref )
564 createSecondaryRegion = true;
566 // also handle a special case where an array of objects
567 // can point back to the array, which is an object!
568 if( typeParam.toPrettyString().equals( "Object[]" ) &&
569 typeDeref.toPrettyString().equals( "Object" ) ) {
571 primary2primaryFields.add(
572 OwnershipAnalysis.getArrayField( typeDeref )
578 // there might be member references for class types
579 if( typeParam.isClass() ) {
580 ClassDescriptor cd = typeParam.getClassDesc();
581 while( cd != null ) {
583 Iterator fieldItr = cd.getFields();
584 while( fieldItr.hasNext() ) {
586 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
587 TypeDescriptor typeField = fd.getType();
588 assert typeField != null;
590 if( !typeField.isImmutable() || typeField.isArray() ) {
591 primary2secondaryFields.add( fd );
592 createSecondaryRegion = true;
595 if( typeUtil.isSuperorType( typeField, typeParam ) ) {
596 primary2primaryFields.add( fd );
600 cd = cd.getSuperDesc();
605 // now build everything we need
606 LabelNode lnParam = getLabelNodeFromTemp( td );
607 HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
608 true, // single object?
611 true, // is a parameter?
613 null, // allocation site
614 null, // reachability set
615 "param"+paramIndex+" obj" );
617 // this is a non-program-accessible label that picks up beta
618 // info to be used for fixing a caller of this method
619 TempDescriptor tdParamQ = new TempDescriptor( td+qString );
620 paramIndex2tdQ.put( paramIndex, tdParamQ );
621 LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
623 // keep track of heap regions that were created for
624 // parameter labels, the index of the parameter they
625 // are for is important when resolving method calls
626 Integer newPrimaryID = hrnPrimary.getID();
627 assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
628 Set<Integer> s = new HashSet<Integer>();
630 idPrimary2paramIndexSet.put( newPrimaryID, s );
631 paramIndex2idPrimary.put( paramIndex, newPrimaryID );
634 TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
635 false, // multi-object
636 TokenTuple.ARITY_ONE ).makeCanonical();
638 HeapRegionNode hrnSecondary = null;
639 Integer newSecondaryID = null;
640 TokenTuple ttSecondary = null;
641 TempDescriptor tdParamR = null;
642 LabelNode lnParamR = null;
644 if( createSecondaryRegion ) {
645 tdParamR = new TempDescriptor( td+rString );
646 paramIndex2tdR.put( paramIndex, tdParamR );
647 lnParamR = getLabelNodeFromTemp( tdParamR );
649 hrnSecondary = createNewHeapRegionNode( null, // id or null to generate a new one
650 false, // single object?
653 true, // is a parameter?
655 null, // allocation site
656 null, // reachability set
657 "param"+paramIndex+" reachable" );
659 newSecondaryID = hrnSecondary.getID();
660 assert !idSecondary2paramIndexSet.containsKey( newSecondaryID );
661 Set<Integer> s2 = new HashSet<Integer>();
662 s2.add( paramIndex );
663 idSecondary2paramIndexSet.put( newSecondaryID, s2 );
664 paramIndex2idSecondary.put( paramIndex, newSecondaryID );
667 ttSecondary = new TokenTuple( newSecondaryID,
668 true, // multi-object
669 TokenTuple.ARITY_ONE ).makeCanonical();
672 // use a beta that has everything and put it all over the
673 // parameter model, then use a global sweep later to fix
674 // it up, since parameters can have different shapes
675 TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
676 ReachabilitySet betaSoup;
677 if( createSecondaryRegion ) {
678 TokenTupleSet tts1 = new TokenTupleSet( ttSecondary ).makeCanonical();
679 TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttSecondary );
680 betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 );
682 betaSoup = ReachabilitySet.factory( tts0 );
685 ReferenceEdge edgeFromLabel =
686 new ReferenceEdge( lnParam, // src
690 false, // special param initial (not needed on label->node)
691 betaSoup ); // reachability
692 edgeFromLabel.tainedBy(paramIndex);
693 addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
695 ReferenceEdge edgeFromLabelQ =
696 new ReferenceEdge( lnParamQ, // src
700 false, // special param initial (not needed on label->node)
701 betaSoup ); // reachability
702 edgeFromLabelQ.tainedBy(paramIndex);
703 addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
705 ReferenceEdge edgeSecondaryReflexive;
706 if( createSecondaryRegion ) {
707 edgeSecondaryReflexive =
708 new ReferenceEdge( hrnSecondary, // src
710 null, // match all types
711 null, // match all fields
712 true, // special param initial
713 betaSoup ); // reachability
714 addReferenceEdge( hrnSecondary, hrnSecondary, edgeSecondaryReflexive );
716 ReferenceEdge edgeSecondary2Primary =
717 new ReferenceEdge( hrnSecondary, // src
719 null, // match all types
720 null, // match all fields
721 true, // special param initial
722 betaSoup ); // reachability
723 addReferenceEdge( hrnSecondary, hrnPrimary, edgeSecondary2Primary );
725 ReferenceEdge edgeFromLabelR =
726 new ReferenceEdge( lnParamR, // src
730 false, // special param initial (not needed on label->node)
731 betaSoup ); // reachability
732 edgeFromLabelR.tainedBy(paramIndex);
733 addReferenceEdge( lnParamR, hrnSecondary, edgeFromLabelR );
736 Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
737 while( fieldItr.hasNext() ) {
738 FieldDescriptor fd = fieldItr.next();
740 ReferenceEdge edgePrimaryReflexive =
741 new ReferenceEdge( hrnPrimary, // src
743 fd.getType(), // type
744 fd.getSymbol(), // field
745 true, // special param initial
746 betaSoup ); // reachability
747 addReferenceEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive );
750 fieldItr = primary2secondaryFields.iterator();
751 while( fieldItr.hasNext() ) {
752 FieldDescriptor fd = fieldItr.next();
754 ReferenceEdge edgePrimary2Secondary =
755 new ReferenceEdge( hrnPrimary, // src
757 fd.getType(), // type
758 fd.getSymbol(), // field
759 true, // special param initial
760 betaSoup ); // reachability
761 addReferenceEdge( hrnPrimary, hrnSecondary, edgePrimary2Secondary );
766 public void makeAliasedParamHeapRegionNode() {
768 LabelNode lnBlob = getLabelNodeFromTemp( tdAliasBlob );
769 HeapRegionNode hrn = createNewHeapRegionNode( null, // id or null to generate a new one
770 false, // single object?
773 true, // is a parameter?
775 null, // allocation site
776 null, // reachability set
780 ReachabilitySet beta = new ReachabilitySet( new TokenTuple( hrn.getID(),
782 TokenTuple.ARITY_ONE).makeCanonical()
785 ReferenceEdge edgeFromLabel =
786 new ReferenceEdge( lnBlob, hrn, null, null, false, beta );
788 ReferenceEdge edgeReflexive =
789 new ReferenceEdge( hrn, hrn, null, null, true, beta );
791 addReferenceEdge( lnBlob, hrn, edgeFromLabel );
792 addReferenceEdge( hrn, hrn, edgeReflexive );
796 public void assignTempEqualToAliasedParam( TempDescriptor tdParam,
797 Integer paramIndex ) {
798 assert tdParam != null;
800 TypeDescriptor typeParam = tdParam.getType();
801 assert typeParam != null;
803 LabelNode lnParam = getLabelNodeFromTemp( tdParam );
804 LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob );
806 // this is a non-program-accessible label that picks up beta
807 // info to be used for fixing a caller of this method
808 TempDescriptor tdParamQ = new TempDescriptor( tdParam+qString );
809 TempDescriptor tdParamR = new TempDescriptor( tdParam+rString );
811 paramIndex2tdQ.put( paramIndex, tdParamQ );
812 paramIndex2tdR.put( paramIndex, tdParamR );
814 LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
815 LabelNode lnParamR = getLabelNodeFromTemp( tdParamR );
817 // the lnAliased should always only reference one node, and that
818 // heap region node is the aliased param blob
819 assert lnAliased.getNumReferencees() == 1;
820 HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
821 Integer idAliased = hrnAliasBlob.getID();
824 TokenTuple ttAliased = new TokenTuple( idAliased,
825 true, // multi-object
826 TokenTuple.ARITY_ONE ).makeCanonical();
829 HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
830 true, // single object?
833 true, // is a parameter?
835 null, // allocation site
836 null, // reachability set
837 "param"+paramIndex+" obj" );
839 Integer newPrimaryID = hrnPrimary.getID();
840 assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
841 Set<Integer> s1 = new HashSet<Integer>();
842 s1.add( paramIndex );
843 idPrimary2paramIndexSet.put( newPrimaryID, s1 );
844 paramIndex2idPrimary.put( paramIndex, newPrimaryID );
846 Set<Integer> s2 = idSecondary2paramIndexSet.get( idAliased );
848 s2 = new HashSet<Integer>();
850 s2.add( paramIndex );
851 idSecondary2paramIndexSet.put( idAliased, s2 );
852 paramIndex2idSecondary.put( paramIndex, idAliased );
856 TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
857 false, // multi-object
858 TokenTuple.ARITY_ONE ).makeCanonical();
861 TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
862 TokenTupleSet tts1 = new TokenTupleSet( ttAliased ).makeCanonical();
863 TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttAliased );
864 ReachabilitySet betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 );
867 ReferenceEdge edgeFromLabel =
868 new ReferenceEdge( lnParam, // src
872 false, // special param initial (not needed on label->node)
873 betaSoup ); // reachability
874 edgeFromLabel.tainedBy(paramIndex);
875 addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
877 ReferenceEdge edgeFromLabelQ =
878 new ReferenceEdge( lnParamQ, // src
882 false, // special param initial (not needed on label->node)
883 betaSoup ); // reachability
884 edgeFromLabelQ.tainedBy(paramIndex);
885 addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
887 ReferenceEdge edgeAliased2Primary =
888 new ReferenceEdge( hrnAliasBlob, // src
890 null, // match all types
891 null, // match all fields
892 true, // special param initial
893 betaSoup ); // reachability
894 addReferenceEdge( hrnAliasBlob, hrnPrimary, edgeAliased2Primary );
896 ReferenceEdge edgeFromLabelR =
897 new ReferenceEdge( lnParamR, // src
901 false, // special param initial (not needed on label->node)
902 betaSoup ); // reachability
903 edgeFromLabelR.tainedBy(paramIndex);
904 addReferenceEdge( lnParamR, hrnAliasBlob, edgeFromLabelR );
908 public void addParam2ParamAliasEdges( FlatMethod fm,
909 Set<Integer> aliasedParamIndices ) {
911 LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob );
913 // the lnAliased should always only reference one node, and that
914 // heap region node is the aliased param blob
915 assert lnAliased.getNumReferencees() == 1;
916 HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
917 Integer idAliased = hrnAliasBlob.getID();
920 TokenTuple ttAliased = new TokenTuple( idAliased,
921 true, // multi-object
922 TokenTuple.ARITY_ONE ).makeCanonical();
925 Iterator<Integer> apItrI = aliasedParamIndices.iterator();
926 while( apItrI.hasNext() ) {
927 Integer i = apItrI.next();
928 TempDescriptor tdParamI = fm.getParameter( i );
929 TypeDescriptor typeI = tdParamI.getType();
930 LabelNode lnParamI = getLabelNodeFromTemp( tdParamI );
932 Integer idPrimaryI = paramIndex2idPrimary.get( i );
933 assert idPrimaryI != null;
934 HeapRegionNode primaryI = id2hrn.get( idPrimaryI );
935 assert primaryI != null;
937 TokenTuple ttPrimaryI = new TokenTuple( idPrimaryI,
938 false, // multi-object
939 TokenTuple.ARITY_ONE ).makeCanonical();
941 TokenTupleSet ttsI = new TokenTupleSet( ttPrimaryI ).makeCanonical();
942 TokenTupleSet ttsA = new TokenTupleSet( ttAliased ).makeCanonical();
943 TokenTupleSet ttsIA = new TokenTupleSet( ttPrimaryI ).makeCanonical().union( ttAliased );
944 ReachabilitySet betaSoup = ReachabilitySet.factory( ttsI ).union( ttsA ).union( ttsIA );
947 // calculate whether fields of this aliased parameter are able to
948 // reference its own primary object, the blob, or other parameter's
950 Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
951 Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
953 // there might be an element reference for array types
954 if( typeI.isArray() ) {
955 // only bother with this if the dereferenced type can
956 // affect reachability
957 TypeDescriptor typeDeref = typeI.dereference();
961 /////////////////////////////////////////////////////////////
962 // NOTE! For the KMeans benchmark a parameter of type float
963 // array, which has an immutable dereferenced type, is causing
964 // this assertion to fail. I'm commenting it out for now which
965 // is safe, because it allows aliasing where no aliasing can occur,
966 // so it can only get a worse-but-not-wrong answer. FIX!
967 /////////////////////////////////////////////////////////////
968 // for this parameter to be aliased the following must be true
969 //assert !typeDeref.isImmutable() || typeDeref.isArray();
973 primary2secondaryFields.add(
974 OwnershipAnalysis.getArrayField( typeDeref )
977 // also handle a special case where an array of objects
978 // can point back to the array, which is an object!
979 if( typeI .toPrettyString().equals( "Object[]" ) &&
980 typeDeref.toPrettyString().equals( "Object" ) ) {
981 primary2primaryFields.add(
982 OwnershipAnalysis.getArrayField( typeDeref )
987 // there might be member references for class types
988 if( typeI.isClass() ) {
989 ClassDescriptor cd = typeI.getClassDesc();
990 while( cd != null ) {
992 Iterator fieldItr = cd.getFields();
993 while( fieldItr.hasNext() ) {
995 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
996 TypeDescriptor typeField = fd.getType();
997 assert typeField != null;
999 if( !typeField.isImmutable() || typeField.isArray() ) {
1000 primary2secondaryFields.add( fd );
1003 if( typeUtil.isSuperorType( typeField, typeI ) ) {
1004 primary2primaryFields.add( fd );
1008 cd = cd.getSuperDesc();
1012 Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
1013 while( fieldItr.hasNext() ) {
1014 FieldDescriptor fd = fieldItr.next();
1016 ReferenceEdge edgePrimaryReflexive =
1017 new ReferenceEdge( primaryI, // src
1019 fd.getType(), // type
1020 fd.getSymbol(), // field
1021 true, // special param initial
1022 betaSoup ); // reachability
1023 addReferenceEdge( primaryI, primaryI, edgePrimaryReflexive );
1026 fieldItr = primary2secondaryFields.iterator();
1027 while( fieldItr.hasNext() ) {
1028 FieldDescriptor fd = fieldItr.next();
1029 TypeDescriptor typeField = fd.getType();
1030 assert typeField != null;
1032 ReferenceEdge edgePrimary2Secondary =
1033 new ReferenceEdge( primaryI, // src
1034 hrnAliasBlob, // dst
1035 fd.getType(), // type
1036 fd.getSymbol(), // field
1037 true, // special param initial
1038 betaSoup ); // reachability
1039 addReferenceEdge( primaryI, hrnAliasBlob, edgePrimary2Secondary );
1041 // ask whether these fields might match any of the other aliased
1042 // parameters and make those edges too
1043 Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
1044 while( apItrJ.hasNext() ) {
1045 Integer j = apItrJ.next();
1046 TempDescriptor tdParamJ = fm.getParameter( j );
1047 TypeDescriptor typeJ = tdParamJ.getType();
1049 if( !i.equals( j ) && typeUtil.isSuperorType( typeField, typeJ ) ) {
1051 Integer idPrimaryJ = paramIndex2idPrimary.get( j );
1052 assert idPrimaryJ != null;
1053 HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
1054 assert primaryJ != null;
1056 TokenTuple ttPrimaryJ = new TokenTuple( idPrimaryJ,
1057 false, // multi-object
1058 TokenTuple.ARITY_ONE ).makeCanonical();
1060 TokenTupleSet ttsJ = new TokenTupleSet( ttPrimaryJ ).makeCanonical();
1061 TokenTupleSet ttsIJ = ttsI.union( ttsJ );
1062 TokenTupleSet ttsAJ = ttsA.union( ttsJ );
1063 TokenTupleSet ttsIAJ = ttsIA.union( ttsJ );
1064 ReachabilitySet betaSoupWJ = ReachabilitySet.factory( ttsJ ).union( ttsIJ ).union( ttsAJ ).union( ttsIAJ );
1066 ReferenceEdge edgePrimaryI2PrimaryJ =
1067 new ReferenceEdge( primaryI, // src
1069 fd.getType(), // type
1070 fd.getSymbol(), // field
1071 true, // special param initial
1072 betaSoupWJ ); // reachability
1073 addReferenceEdge( primaryI, primaryJ, edgePrimaryI2PrimaryJ );
1079 // look at whether aliased parameters i and j can
1080 // possibly be the same primary object, add edges
1081 Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
1082 while( apItrJ.hasNext() ) {
1083 Integer j = apItrJ.next();
1084 TempDescriptor tdParamJ = fm.getParameter( j );
1085 TypeDescriptor typeJ = tdParamJ.getType();
1086 LabelNode lnParamJ = getLabelNodeFromTemp( tdParamJ );
1088 if( !i.equals( j ) && typeUtil.isSuperorType( typeI, typeJ ) ) {
1090 Integer idPrimaryJ = paramIndex2idPrimary.get( j );
1091 assert idPrimaryJ != null;
1092 HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
1093 assert primaryJ != null;
1095 ReferenceEdge lnJ2PrimaryJ = lnParamJ.getReferenceTo( primaryJ,
1098 assert lnJ2PrimaryJ != null;
1100 ReferenceEdge lnI2PrimaryJ = lnJ2PrimaryJ.copy();
1101 lnI2PrimaryJ.setSrc( lnParamI );
1102 lnI2PrimaryJ.setType( tdParamI.getType() );
1103 lnI2PrimaryJ.tainedBy(new Integer(j));
1104 addReferenceEdge( lnParamI, primaryJ, lnI2PrimaryJ );
1110 public void prepareParamTokenMaps( FlatMethod fm ) {
1112 // always add the bogus mappings that are used to
1113 // rewrite "with respect to no parameter"
1114 paramTokenPrimary2paramIndex.put( bogusToken, bogusIndex );
1115 paramIndex2paramTokenPrimary.put( bogusIndex, bogusToken );
1117 paramTokenSecondary2paramIndex.put( bogusToken, bogusIndex );
1118 paramIndex2paramTokenSecondary.put( bogusIndex, bogusToken );
1119 paramTokenSecondaryPlus2paramIndex.put( bogusTokenPlus, bogusIndex );
1120 paramIndex2paramTokenSecondaryPlus.put( bogusIndex, bogusTokenPlus );
1121 paramTokenSecondaryStar2paramIndex.put( bogusTokenStar, bogusIndex );
1122 paramIndex2paramTokenSecondaryStar.put( bogusIndex, bogusTokenStar );
1124 for( int i = 0; i < fm.numParameters(); ++i ) {
1125 Integer paramIndex = new Integer( i );
1127 // immutable objects have no primary regions
1128 if( paramIndex2idPrimary.containsKey( paramIndex ) ) {
1129 Integer idPrimary = paramIndex2idPrimary.get( paramIndex );
1131 assert id2hrn.containsKey( idPrimary );
1132 HeapRegionNode hrnPrimary = id2hrn.get( idPrimary );
1134 TokenTuple p_i = new TokenTuple( hrnPrimary.getID(),
1135 false, // multiple-object?
1136 TokenTuple.ARITY_ONE ).makeCanonical();
1137 paramTokenPrimary2paramIndex.put( p_i, paramIndex );
1138 paramIndex2paramTokenPrimary.put( paramIndex, p_i );
1141 // any parameter object, by type, may have no secondary region
1142 if( paramIndex2idSecondary.containsKey( paramIndex ) ) {
1143 Integer idSecondary = paramIndex2idSecondary.get( paramIndex );
1145 assert id2hrn.containsKey( idSecondary );
1146 HeapRegionNode hrnSecondary = id2hrn.get( idSecondary );
1148 TokenTuple s_i = new TokenTuple( hrnSecondary.getID(),
1149 true, // multiple-object?
1150 TokenTuple.ARITY_ONE ).makeCanonical();
1151 paramTokenSecondary2paramIndex.put( s_i, paramIndex );
1152 paramIndex2paramTokenSecondary.put( paramIndex, s_i );
1154 TokenTuple s_i_plus = new TokenTuple( hrnSecondary.getID(),
1155 true, // multiple-object?
1156 TokenTuple.ARITY_ONEORMORE ).makeCanonical();
1157 paramTokenSecondaryPlus2paramIndex.put( s_i_plus, paramIndex );
1158 paramIndex2paramTokenSecondaryPlus.put( paramIndex, s_i_plus );
1160 TokenTuple s_i_star = new TokenTuple( hrnSecondary.getID(),
1161 true, // multiple-object?
1162 TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
1163 paramTokenSecondaryStar2paramIndex.put( s_i_star, paramIndex );
1164 paramIndex2paramTokenSecondaryStar.put( paramIndex, s_i_star );
1171 public void assignReturnEqualToTemp(TempDescriptor x) {
1173 LabelNode lnR = getLabelNodeFromTemp(tdReturn);
1174 LabelNode lnX = getLabelNodeFromTemp(x);
1176 clearReferenceEdgesFrom(lnR, null, null, true);
1178 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
1179 while( itrXhrn.hasNext() ) {
1180 ReferenceEdge edgeX = itrXhrn.next();
1181 HeapRegionNode referencee = edgeX.getDst();
1182 ReferenceEdge edgeNew = edgeX.copy();
1183 edgeNew.setSrc(lnR);
1185 addReferenceEdge(lnR, referencee, edgeNew);
1190 public void assignTempEqualToNewAlloc(TempDescriptor x,
1191 AllocationSite as) {
1197 // after the age operation the newest (or zero-ith oldest)
1198 // node associated with the allocation site should have
1199 // no references to it as if it were a newly allocated
1201 Integer idNewest = as.getIthOldest( 0 );
1202 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
1203 assert hrnNewest != null;
1205 LabelNode lnX = getLabelNodeFromTemp( x );
1206 clearReferenceEdgesFrom( lnX, null, null, true );
1208 // make a new reference to allocated node
1209 TypeDescriptor type = as.getType();
1210 ReferenceEdge edgeNew =
1211 new ReferenceEdge( lnX, // source
1215 false, // is initial param
1216 hrnNewest.getAlpha() // beta
1219 addReferenceEdge( lnX, hrnNewest, edgeNew );
1223 // use the allocation site (unique to entire analysis) to
1224 // locate the heap region nodes in this ownership graph
1225 // that should be aged. The process models the allocation
1226 // of new objects and collects all the oldest allocations
1227 // in a summary node to allow for a finite analysis
1229 // There is an additional property of this method. After
1230 // running it on a particular ownership graph (many graphs
1231 // may have heap regions related to the same allocation site)
1232 // the heap region node objects in this ownership graph will be
1233 // allocated. Therefore, after aging a graph for an allocation
1234 // site, attempts to retrieve the heap region nodes using the
1235 // integer id's contained in the allocation site should always
1236 // return non-null heap regions.
1237 public void age(AllocationSite as) {
1239 // aging adds this allocation site to the graph's
1240 // list of sites that exist in the graph, or does
1241 // nothing if the site is already in the list
1242 allocationSites.add(as);
1244 // get the summary node for the allocation site in the context
1245 // of this particular ownership graph
1246 HeapRegionNode hrnSummary = getSummaryNode(as);
1248 // merge oldest node into summary
1249 Integer idK = as.getOldest();
1250 HeapRegionNode hrnK = id2hrn.get(idK);
1251 mergeIntoSummary(hrnK, hrnSummary);
1253 // move down the line of heap region nodes
1254 // clobbering the ith and transferring all references
1255 // to and from i-1 to node i. Note that this clobbers
1256 // the oldest node (hrnK) that was just merged into
1258 for( int i = allocationDepth - 1; i > 0; --i ) {
1260 // move references from the i-1 oldest to the ith oldest
1261 Integer idIth = as.getIthOldest(i);
1262 HeapRegionNode hrnI = id2hrn.get(idIth);
1263 Integer idImin1th = as.getIthOldest(i - 1);
1264 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
1266 transferOnto(hrnImin1, hrnI);
1269 // as stated above, the newest node should have had its
1270 // references moved over to the second oldest, so we wipe newest
1271 // in preparation for being the new object to assign something to
1272 Integer id0th = as.getIthOldest(0);
1273 HeapRegionNode hrn0 = id2hrn.get(id0th);
1274 assert hrn0 != null;
1276 // clear all references in and out of newest node
1277 clearReferenceEdgesFrom(hrn0, null, null, true);
1278 clearReferenceEdgesTo(hrn0, null, null, true);
1281 // now tokens in reachability sets need to "age" also
1282 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1283 while( itrAllLabelNodes.hasNext() ) {
1284 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1285 LabelNode ln = (LabelNode) me.getValue();
1287 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1288 while( itrEdges.hasNext() ) {
1289 ageTokens(as, itrEdges.next() );
1293 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1294 while( itrAllHRNodes.hasNext() ) {
1295 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1296 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1298 ageTokens(as, hrnToAge);
1300 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1301 while( itrEdges.hasNext() ) {
1302 ageTokens(as, itrEdges.next() );
1307 // after tokens have been aged, reset newest node's reachability
1308 if( hrn0.isFlagged() ) {
1309 hrn0.setAlpha(new ReachabilitySet(
1311 new TokenTuple(hrn0).makeCanonical()
1316 hrn0.setAlpha(new ReachabilitySet(
1317 new TokenTupleSet().makeCanonical()
1324 protected HeapRegionNode getSummaryNode(AllocationSite as) {
1326 Integer idSummary = as.getSummary();
1327 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
1329 // If this is null then we haven't touched this allocation site
1330 // in the context of the current ownership graph, so allocate
1331 // heap region nodes appropriate for the entire allocation site.
1332 // This should only happen once per ownership graph per allocation site,
1333 // and a particular integer id can be used to locate the heap region
1334 // in different ownership graphs that represents the same part of an
1336 if( hrnSummary == null ) {
1338 boolean hasFlags = false;
1339 if( as.getType().isClass() ) {
1340 hasFlags = as.getType().getClassDesc().hasFlags();
1344 hasFlags=as.getFlag();
1347 hrnSummary = createNewHeapRegionNode(idSummary, // id or null to generate a new one
1348 false, // single object?
1350 hasFlags, // flagged?
1351 false, // is a parameter?
1352 as.getType(), // type
1353 as, // allocation site
1354 null, // reachability set
1355 as.toStringForDOT() + "\\nsummary");
1357 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1358 Integer idIth = as.getIthOldest(i);
1359 assert !id2hrn.containsKey(idIth);
1360 createNewHeapRegionNode(idIth, // id or null to generate a new one
1361 true, // single object?
1363 hasFlags, // flagged?
1364 false, // is a parameter?
1365 as.getType(), // type
1366 as, // allocation site
1367 null, // reachability set
1368 as.toStringForDOT() + "\\n" + i + " oldest");
1376 protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
1378 Integer idShadowSummary = as.getSummaryShadow();
1379 HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
1381 if( hrnShadowSummary == null ) {
1383 boolean hasFlags = false;
1384 if( as.getType().isClass() ) {
1385 hasFlags = as.getType().getClassDesc().hasFlags();
1388 hrnShadowSummary = createNewHeapRegionNode(idShadowSummary, // id or null to generate a new one
1389 false, // single object?
1391 hasFlags, // flagged?
1392 false, // is a parameter?
1393 as.getType(), // type
1394 as, // allocation site
1395 null, // reachability set
1396 as + "\\n" + as.getType() + "\\nshadowSum");
1398 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1399 Integer idShadowIth = as.getIthOldestShadow(i);
1400 assert !id2hrn.containsKey(idShadowIth);
1401 createNewHeapRegionNode(idShadowIth, // id or null to generate a new one
1402 true, // single object?
1404 hasFlags, // flagged?
1405 false, // is a parameter?
1406 as.getType(), // type
1407 as, // allocation site
1408 null, // reachability set
1409 as + "\\n" + as.getType() + "\\n" + i + " shadow");
1413 return hrnShadowSummary;
1417 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
1418 assert hrnSummary.isNewSummary();
1420 // transfer references _from_ hrn over to hrnSummary
1421 Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
1422 while( itrReferencee.hasNext() ) {
1423 ReferenceEdge edge = itrReferencee.next();
1424 ReferenceEdge edgeMerged = edge.copy();
1425 edgeMerged.setSrc(hrnSummary);
1427 HeapRegionNode hrnReferencee = edge.getDst();
1428 ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee,
1432 if( edgeSummary == null ) {
1433 // the merge is trivial, nothing to be done
1435 // otherwise an edge from the referencer to hrnSummary exists already
1436 // and the edge referencer->hrn should be merged with it
1437 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1440 addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
1443 // next transfer references _to_ hrn over to hrnSummary
1444 Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
1445 while( itrReferencer.hasNext() ) {
1446 ReferenceEdge edge = itrReferencer.next();
1447 ReferenceEdge edgeMerged = edge.copy();
1448 edgeMerged.setDst(hrnSummary);
1450 OwnershipNode onReferencer = edge.getSrc();
1451 ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary,
1455 if( edgeSummary == null ) {
1456 // the merge is trivial, nothing to be done
1458 // otherwise an edge from the referencer to alpha_S exists already
1459 // and the edge referencer->alpha_K should be merged with it
1460 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1463 addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
1466 // then merge hrn reachability into hrnSummary
1467 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
1471 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
1473 // clear references in and out of node b
1474 clearReferenceEdgesFrom(hrnB, null, null, true);
1475 clearReferenceEdgesTo(hrnB, null, null, true);
1477 // copy each edge in and out of A to B
1478 Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
1479 while( itrReferencee.hasNext() ) {
1480 ReferenceEdge edge = itrReferencee.next();
1481 HeapRegionNode hrnReferencee = edge.getDst();
1482 ReferenceEdge edgeNew = edge.copy();
1483 edgeNew.setSrc(hrnB);
1485 addReferenceEdge(hrnB, hrnReferencee, edgeNew);
1488 Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
1489 while( itrReferencer.hasNext() ) {
1490 ReferenceEdge edge = itrReferencer.next();
1491 OwnershipNode onReferencer = edge.getSrc();
1492 ReferenceEdge edgeNew = edge.copy();
1493 edgeNew.setDst(hrnB);
1495 addReferenceEdge(onReferencer, hrnB, edgeNew);
1498 // replace hrnB reachability with hrnA's
1499 hrnB.setAlpha(hrnA.getAlpha() );
1503 protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
1504 edge.setBeta(edge.getBeta().ageTokens(as) );
1507 protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
1508 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
1513 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1515 HashSet<HeapRegionNode> nodesWithNewAlpha,
1516 HashSet<ReferenceEdge> edgesWithNewBeta) {
1518 HashSet<HeapRegionNode> todoNodes
1519 = new HashSet<HeapRegionNode>();
1520 todoNodes.add(nPrime);
1522 HashSet<ReferenceEdge> todoEdges
1523 = new HashSet<ReferenceEdge>();
1525 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
1526 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
1527 nodePlannedChanges.put(nPrime, c0);
1529 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
1530 = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1532 // first propagate change sets everywhere they can go
1533 while( !todoNodes.isEmpty() ) {
1534 HeapRegionNode n = todoNodes.iterator().next();
1535 ChangeTupleSet C = nodePlannedChanges.get(n);
1537 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
1538 while( referItr.hasNext() ) {
1539 ReferenceEdge edge = referItr.next();
1540 todoEdges.add(edge);
1542 if( !edgePlannedChanges.containsKey(edge) ) {
1543 edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
1546 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
1549 Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
1550 while( refeeItr.hasNext() ) {
1551 ReferenceEdge edgeF = refeeItr.next();
1552 HeapRegionNode m = edgeF.getDst();
1554 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
1556 Iterator<ChangeTuple> itrCprime = C.iterator();
1557 while( itrCprime.hasNext() ) {
1558 ChangeTuple c = itrCprime.next();
1559 if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
1560 changesToPass = changesToPass.union(c);
1564 if( !changesToPass.isEmpty() ) {
1565 if( !nodePlannedChanges.containsKey(m) ) {
1566 nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
1569 ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
1571 if( !changesToPass.isSubset(currentChanges) ) {
1573 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
1579 todoNodes.remove(n);
1582 // then apply all of the changes for each node at once
1583 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1584 while( itrMap.hasNext() ) {
1585 Map.Entry me = (Map.Entry) itrMap.next();
1586 HeapRegionNode n = (HeapRegionNode) me.getKey();
1587 ChangeTupleSet C = (ChangeTupleSet) me.getValue();
1589 n.setAlphaNew( n.getAlpha().applyChangeSet( C, true ) );
1590 nodesWithNewAlpha.add( n );
1593 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
1597 protected void propagateTokensOverEdges(
1598 HashSet<ReferenceEdge> todoEdges,
1599 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
1600 HashSet<ReferenceEdge> edgesWithNewBeta) {
1602 // first propagate all change tuples everywhere they can go
1603 while( !todoEdges.isEmpty() ) {
1604 ReferenceEdge edgeE = todoEdges.iterator().next();
1605 todoEdges.remove(edgeE);
1607 if( !edgePlannedChanges.containsKey(edgeE) ) {
1608 edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
1611 ChangeTupleSet C = edgePlannedChanges.get(edgeE);
1613 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
1615 Iterator<ChangeTuple> itrC = C.iterator();
1616 while( itrC.hasNext() ) {
1617 ChangeTuple c = itrC.next();
1618 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1619 changesToPass = changesToPass.union(c);
1623 OwnershipNode onSrc = edgeE.getSrc();
1625 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
1626 HeapRegionNode n = (HeapRegionNode) onSrc;
1628 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
1629 while( referItr.hasNext() ) {
1630 ReferenceEdge edgeF = referItr.next();
1632 if( !edgePlannedChanges.containsKey(edgeF) ) {
1633 edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
1636 ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
1638 if( !changesToPass.isSubset(currentChanges) ) {
1639 todoEdges.add(edgeF);
1640 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
1646 // then apply all of the changes for each edge at once
1647 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1648 while( itrMap.hasNext() ) {
1649 Map.Entry me = (Map.Entry) itrMap.next();
1650 ReferenceEdge e = (ReferenceEdge) me.getKey();
1651 ChangeTupleSet C = (ChangeTupleSet) me.getValue();
1653 e.setBetaNew( e.getBetaNew().union( e.getBeta().applyChangeSet( C, true ) ) );
1654 edgesWithNewBeta.add( e );
1659 public Set<Integer> calculateAliasedParamSet( FlatCall fc,
1663 Hashtable<Integer, LabelNode> paramIndex2ln =
1664 new Hashtable<Integer, LabelNode>();
1666 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
1667 new Hashtable<Integer, HashSet<HeapRegionNode> >();
1669 for( int i = 0; i < fm.numParameters(); ++i ) {
1670 Integer paramIndex = new Integer( i );
1671 TempDescriptor tdParam = fm.getParameter( i );
1672 TypeDescriptor typeParam = tdParam.getType();
1674 if( typeParam.isImmutable() && !typeParam.isArray() ) {
1675 // don't bother with this primitive parameter, it
1676 // cannot affect reachability
1680 // now depending on whether the callee is static or not
1681 // we need to account for a "this" argument in order to
1682 // find the matching argument in the caller context
1683 TempDescriptor argTemp_i;
1685 argTemp_i = fc.getArg(paramIndex);
1687 if( paramIndex.equals(0) ) {
1688 argTemp_i = fc.getThis();
1690 argTemp_i = fc.getArg(paramIndex - 1);
1694 // in non-static methods there is a "this" pointer
1695 // that should be taken into account
1697 assert fc.numArgs() == fm.numParameters();
1699 assert fc.numArgs() + 1 == fm.numParameters();
1702 LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1703 paramIndex2ln.put(paramIndex, argLabel_i);
1706 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1707 while( lnArgItr.hasNext() ) {
1708 Map.Entry me = (Map.Entry)lnArgItr.next();
1709 Integer index = (Integer) me.getKey();
1710 LabelNode lnArg_i = (LabelNode) me.getValue();
1712 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1713 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1715 // to find all reachable nodes, start with label referencees
1716 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1717 while( edgeArgItr.hasNext() ) {
1718 ReferenceEdge edge = edgeArgItr.next();
1719 todoNodes.add( edge.getDst() );
1722 // then follow links until all reachable nodes have been found
1723 while( !todoNodes.isEmpty() ) {
1724 HeapRegionNode hrn = todoNodes.iterator().next();
1725 todoNodes.remove(hrn);
1726 reachableNodes.add(hrn);
1728 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1729 while( edgeItr.hasNext() ) {
1730 ReferenceEdge edge = edgeItr.next();
1732 if( !reachableNodes.contains(edge.getDst() ) ) {
1733 todoNodes.add(edge.getDst() );
1739 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1742 Set<Integer> aliasedIndices = new HashSet<Integer>();
1744 // check for arguments that are aliased
1745 for( int i = 0; i < fm.numParameters(); ++i ) {
1746 for( int j = 0; j < i; ++j ) {
1747 HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
1748 HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
1750 // some parameters are immutable or primitive, so skip em
1751 if( s1 == null || s2 == null ) {
1755 Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
1756 intersection.retainAll(s2);
1758 if( !intersection.isEmpty() ) {
1759 aliasedIndices.add( new Integer( i ) );
1760 aliasedIndices.add( new Integer( j ) );
1765 return aliasedIndices;
1769 private String makeMapKey( Integer i, Integer j, String field ) {
1770 return i+","+j+","+field;
1773 private String makeMapKey( Integer i, String field ) {
1777 // these hashtables are used during the mapping procedure to say that
1778 // with respect to some argument i there is an edge placed into some
1779 // category for mapping with respect to another argument index j
1780 // so the key into the hashtable is i, the value is a two-element vector
1781 // that contains in 0 the edge and in 1 the Integer index j
1782 private void ensureEmptyEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
1785 Set<Vector> ei = edge_index_pairs.get( indexI );
1787 ei = new HashSet<Vector>();
1789 edge_index_pairs.put( indexI, ei );
1792 private void addEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
1797 Vector v = new Vector(); v.setSize( 2 );
1799 v.set( 1 , indexJ );
1800 Set<Vector> ei = edge_index_pairs.get( indexI );
1802 ei = new HashSet<Vector>();
1805 edge_index_pairs.put( indexI, ei );
1808 private ReachabilitySet funcScriptR( ReachabilitySet rsIn,
1809 OwnershipGraph ogCallee,
1810 MethodContext mc ) {
1812 ReachabilitySet rsOut = new ReachabilitySet( rsIn );
1814 Iterator itr = ogCallee.paramIndex2paramTokenPrimary.entrySet().iterator();
1815 while( itr.hasNext() ) {
1816 Map.Entry me = (Map.Entry) itr.next();
1817 Integer i = (Integer) me.getKey();
1818 TokenTuple p_i = (TokenTuple) me.getValue();
1819 TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( i );
1821 // skip this if there is no secondary token or the parameter
1822 // is part of the aliasing context
1823 if( s_i == null || mc.getAliasedParamIndices().contains( i ) ) {
1827 rsOut = rsOut.removeTokenAIfTokenB( p_i, s_i );
1833 // detects strong updates to the primary parameter object and
1834 // effects the removal of old edges in the calling graph
1835 private void effectCalleeStrongUpdates( Integer paramIndex,
1836 OwnershipGraph ogCallee,
1837 HeapRegionNode hrnCaller
1839 Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
1840 assert idPrimary != null;
1842 HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
1843 assert hrnPrimary != null;
1845 TypeDescriptor typeParam = hrnPrimary.getType();
1846 assert typeParam.isClass();
1848 Set<String> fieldNamesToRemove = new HashSet<String>();
1850 ClassDescriptor cd = typeParam.getClassDesc();
1851 while( cd != null ) {
1853 Iterator fieldItr = cd.getFields();
1854 while( fieldItr.hasNext() ) {
1856 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
1857 TypeDescriptor typeField = fd.getType();
1858 assert typeField != null;
1860 if( ogCallee.hasFieldBeenUpdated( hrnPrimary, fd.getSymbol() ) ) {
1861 clearReferenceEdgesFrom( hrnCaller, fd.getType(), fd.getSymbol(), false );
1865 cd = cd.getSuperDesc();
1869 private boolean hasFieldBeenUpdated( HeapRegionNode hrnPrimary, String field ) {
1871 Iterator<ReferenceEdge> itr = hrnPrimary.iteratorToReferencees();
1872 while( itr.hasNext() ) {
1873 ReferenceEdge e = itr.next();
1874 if( e.fieldEquals( field ) && e.isInitialParam() ) {
1882 // resolveMethodCall() is used to incorporate a callee graph's effects into
1883 // *this* graph, which is the caller. This method can also be used, after
1884 // the entire analysis is complete, to perform parameter decomposition for
1885 // a given call chain.
1886 public void resolveMethodCall(FlatCall fc, // call site in caller method
1887 boolean isStatic, // whether it is a static method
1888 FlatMethod fm, // the callee method (when virtual, can be many)
1889 OwnershipGraph ogCallee, // the callee's current ownership graph
1890 MethodContext mc, // the aliasing context for this call
1891 ParameterDecomposition pd // if this is not null, we're calling after analysis
1895 // this debug snippet is harmless for regular use and INVALUABLE at debug time
1896 // to see what potentially goes wrong when a specific method calls another
1897 String debugCaller = "foo";
1898 String debugCallee = "bar";
1899 //String debugCaller = "StandardEngine";
1900 //String debugCaller = "register_by_type";
1901 //String debugCaller = "register_by_type_front";
1902 //String debugCaller = "addFirst";
1903 //String debugCallee = "LinkedListElement";
1905 if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
1906 fm.getMethod().getSymbol().equals( debugCallee ) ) {
1909 writeGraph( "debug1BeforeCall", true, true, true, false, false );
1910 ogCallee.writeGraph( "debug0Callee", true, true, true, false, false );
1911 } catch( IOException e ) {}
1913 System.out.println( " "+mc+" is calling "+fm );
1918 // define rewrite rules and other structures to organize data by parameter/argument index
1919 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_p = new Hashtable<Integer, ReachabilitySet>();
1920 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_s = new Hashtable<Integer, ReachabilitySet>();
1922 Hashtable<String, ReachabilitySet> paramIndex2rewriteJ_p2p = new Hashtable<String, ReachabilitySet>(); // select( i, j, f )
1923 Hashtable<String, ReachabilitySet> paramIndex2rewriteJ_p2s = new Hashtable<String, ReachabilitySet>(); // select( i, f )
1924 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2p = new Hashtable<Integer, ReachabilitySet>();
1925 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2s = new Hashtable<Integer, ReachabilitySet>();
1927 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p = new Hashtable<Integer, ReachabilitySet>();
1928 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p2 = new Hashtable<Integer, ReachabilitySet>();
1929 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_s = new Hashtable<Integer, ReachabilitySet>();
1931 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_p = new Hashtable<Integer, ReachabilitySet>();
1932 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_s = new Hashtable<Integer, ReachabilitySet>();
1934 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD = new Hashtable<Integer, ReachabilitySet>();
1937 Hashtable<Integer, LabelNode> paramIndex2ln = new Hashtable<Integer, LabelNode>();
1940 paramIndex2rewriteH_p.put( bogusIndex, rsIdentity );
1941 paramIndex2rewriteH_s.put( bogusIndex, rsIdentity );
1943 paramIndex2rewriteJ_p2p.put( bogusIndex.toString(), rsIdentity );
1944 paramIndex2rewriteJ_p2s.put( bogusIndex.toString(), rsIdentity );
1945 paramIndex2rewriteJ_s2p.put( bogusIndex, rsIdentity );
1946 paramIndex2rewriteJ_s2s.put( bogusIndex, rsIdentity );
1949 for( int i = 0; i < fm.numParameters(); ++i ) {
1950 Integer paramIndex = new Integer(i);
1952 if( !ogCallee.paramIndex2idPrimary.containsKey( paramIndex ) ) {
1953 // skip this immutable parameter
1957 // setup H (primary)
1958 Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
1959 assert ogCallee.id2hrn.containsKey( idPrimary );
1960 HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
1961 assert hrnPrimary != null;
1962 paramIndex2rewriteH_p.put( paramIndex, toShadowTokens( ogCallee, hrnPrimary.getAlpha() ) );
1964 // setup J (primary->X)
1965 Iterator<ReferenceEdge> p2xItr = hrnPrimary.iteratorToReferencees();
1966 while( p2xItr.hasNext() ) {
1967 ReferenceEdge p2xEdge = p2xItr.next();
1969 // we only care about initial parameter edges here
1970 if( !p2xEdge.isInitialParam() ) { continue; }
1972 HeapRegionNode hrnDst = p2xEdge.getDst();
1974 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
1975 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
1976 while( jItr.hasNext() ) {
1977 Integer j = jItr.next();
1978 paramIndex2rewriteJ_p2p.put( makeMapKey( i, j, p2xEdge.getField() ),
1979 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
1983 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
1984 paramIndex2rewriteJ_p2s.put( makeMapKey( i, p2xEdge.getField() ),
1985 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
1989 // setup K (primary)
1990 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
1991 assert tdParamQ != null;
1992 LabelNode lnParamQ = ogCallee.td2ln.get( tdParamQ );
1993 assert lnParamQ != null;
1994 ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnPrimary, null, null );
1995 assert edgeSpecialQ_i != null;
1996 ReachabilitySet qBeta = toShadowTokens( ogCallee, edgeSpecialQ_i.getBeta() );
1998 TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary .get( paramIndex );
1999 TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( paramIndex );
2001 ReachabilitySet K_p = new ReachabilitySet().makeCanonical();
2002 ReachabilitySet K_p2 = new ReachabilitySet().makeCanonical();
2006 // sort qBeta into K_p1 and K_p2
2007 Iterator<TokenTupleSet> ttsItr = qBeta.iterator();
2008 while( ttsItr.hasNext() ) {
2009 TokenTupleSet tts = ttsItr.next();
2010 if( s_i != null && tts.containsBoth( p_i, s_i ) ) {
2011 K_p2 = K_p2.union( tts );
2013 K_p = K_p.union( tts );
2017 paramIndex2rewriteK_p .put( paramIndex, K_p );
2018 paramIndex2rewriteK_p2.put( paramIndex, K_p2 );
2021 // if there is a secondary node, compute the rest of the rewrite rules
2022 if( ogCallee.paramIndex2idSecondary.containsKey( paramIndex ) ) {
2024 // setup H (secondary)
2025 Integer idSecondary = ogCallee.paramIndex2idSecondary.get( paramIndex );
2026 assert ogCallee.id2hrn.containsKey( idSecondary );
2027 HeapRegionNode hrnSecondary = ogCallee.id2hrn.get( idSecondary );
2028 assert hrnSecondary != null;
2029 paramIndex2rewriteH_s.put( paramIndex, toShadowTokens( ogCallee, hrnSecondary.getAlpha() ) );
2032 // setup J (secondary->X)
2033 Iterator<ReferenceEdge> s2xItr = hrnSecondary.iteratorToReferencees();
2034 while( s2xItr.hasNext() ) {
2035 ReferenceEdge s2xEdge = s2xItr.next();
2037 if( !s2xEdge.isInitialParam() ) { continue; }
2039 HeapRegionNode hrnDst = s2xEdge.getDst();
2041 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
2042 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
2043 while( jItr.hasNext() ) {
2044 Integer j = jItr.next();
2045 paramIndex2rewriteJ_s2p.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
2049 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
2050 paramIndex2rewriteJ_s2s.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
2054 // setup K (secondary)
2055 TempDescriptor tdParamR = ogCallee.paramIndex2tdR.get( paramIndex );
2056 assert tdParamR != null;
2057 LabelNode lnParamR = ogCallee.td2ln.get( tdParamR );
2058 assert lnParamR != null;
2059 ReferenceEdge edgeSpecialR_i = lnParamR.getReferenceTo( hrnSecondary, null, null );
2060 assert edgeSpecialR_i != null;
2061 paramIndex2rewriteK_s.put( paramIndex,
2062 toShadowTokens( ogCallee, edgeSpecialR_i.getBeta() ) );
2066 // now depending on whether the callee is static or not
2067 // we need to account for a "this" argument in order to
2068 // find the matching argument in the caller context
2069 TempDescriptor argTemp_i;
2071 argTemp_i = fc.getArg( paramIndex );
2073 if( paramIndex.equals( 0 ) ) {
2074 argTemp_i = fc.getThis();
2076 argTemp_i = fc.getArg( paramIndex - 1 );
2080 // in non-static methods there is a "this" pointer
2081 // that should be taken into account
2083 assert fc.numArgs() == fm.numParameters();
2085 assert fc.numArgs() + 1 == fm.numParameters();
2088 // remember which caller arg label maps to param index
2089 LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i );
2090 paramIndex2ln.put( paramIndex, argLabel_i );
2092 // do a callee-effect strong update pre-pass here
2093 if( argTemp_i.getType().isClass() ) {
2095 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
2096 while( edgeItr.hasNext() ) {
2097 ReferenceEdge edge = edgeItr.next();
2098 HeapRegionNode hrn = edge.getDst();
2100 if( (hrn.getNumReferencers() == 1) || // case 1
2101 (hrn.isSingleObject() && argLabel_i.getNumReferencees() == 1) // case 2
2103 if( !DISABLE_STRONG_UPDATES ) {
2104 effectCalleeStrongUpdates( paramIndex, ogCallee, hrn );
2110 // then calculate the d and D rewrite rules
2111 ReachabilitySet d_i_p = new ReachabilitySet().makeCanonical();
2112 ReachabilitySet d_i_s = new ReachabilitySet().makeCanonical();
2113 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
2114 while( edgeItr.hasNext() ) {
2115 ReferenceEdge edge = edgeItr.next();
2117 d_i_p = d_i_p.union( edge.getBeta().intersection( edge.getDst().getAlpha() ) );
2118 d_i_s = d_i_s.union( edge.getBeta() );
2120 paramIndex2rewrite_d_p.put( paramIndex, d_i_p );
2121 paramIndex2rewrite_d_s.put( paramIndex, d_i_s );
2123 // TODO: we should only do this when we need it, and then
2124 // memoize it for the rest of the mapping procedure
2125 ReachabilitySet D_i = d_i_s.exhaustiveArityCombinations();
2126 paramIndex2rewriteD.put( paramIndex, D_i );
2130 // with respect to each argument, map parameter effects into caller
2131 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
2132 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
2134 Hashtable<Integer, Set<HeapRegionNode> > pi2dr =
2135 new Hashtable<Integer, Set<HeapRegionNode> >();
2137 Hashtable<Integer, Set<HeapRegionNode> > pi2r =
2138 new Hashtable<Integer, Set<HeapRegionNode> >();
2140 Set<HeapRegionNode> defParamObj = new HashSet<HeapRegionNode>();
2142 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
2143 while( lnArgItr.hasNext() ) {
2144 Map.Entry me = (Map.Entry) lnArgItr.next();
2145 Integer index = (Integer) me.getKey();
2146 LabelNode lnArg_i = (LabelNode) me.getValue();
2148 Set<HeapRegionNode> dr = new HashSet<HeapRegionNode>();
2149 Set<HeapRegionNode> r = new HashSet<HeapRegionNode>();
2150 Set<HeapRegionNode> todo = new HashSet<HeapRegionNode>();
2152 // find all reachable nodes starting with label referencees
2153 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
2154 while( edgeArgItr.hasNext() ) {
2155 ReferenceEdge edge = edgeArgItr.next();
2156 HeapRegionNode hrn = edge.getDst();
2160 if( lnArg_i.getNumReferencees() == 1 && hrn.isSingleObject() ) {
2161 defParamObj.add( hrn );
2164 Iterator<ReferenceEdge> edgeHrnItr = hrn.iteratorToReferencees();
2165 while( edgeHrnItr.hasNext() ) {
2166 ReferenceEdge edger = edgeHrnItr.next();
2167 todo.add( edger.getDst() );
2170 // then follow links until all reachable nodes have been found
2171 while( !todo.isEmpty() ) {
2172 HeapRegionNode hrnr = todo.iterator().next();
2173 todo.remove( hrnr );
2177 Iterator<ReferenceEdge> edgeItr = hrnr.iteratorToReferencees();
2178 while( edgeItr.hasNext() ) {
2179 ReferenceEdge edger = edgeItr.next();
2180 if( !r.contains( edger.getDst() ) ) {
2181 todo.add( edger.getDst() );
2186 if( hrn.isSingleObject() ) {
2191 pi2dr.put( index, dr );
2192 pi2r .put( index, r );
2195 assert defParamObj.size() <= fm.numParameters();
2197 // if we're in parameter decomposition mode, report some results here
2201 // report primary parameter object mappings
2202 mapItr = pi2dr.entrySet().iterator();
2203 while( mapItr.hasNext() ) {
2204 Map.Entry me = (Map.Entry) mapItr.next();
2205 Integer paramIndex = (Integer) me.getKey();
2206 Set<HeapRegionNode> hrnAset = (Set<HeapRegionNode>) me.getValue();
2208 Iterator<HeapRegionNode> hrnItr = hrnAset.iterator();
2209 while( hrnItr.hasNext() ) {
2210 HeapRegionNode hrnA = hrnItr.next();
2211 pd.mapRegionToParamObject( hrnA, paramIndex );
2215 // report parameter-reachable mappings
2216 mapItr = pi2r.entrySet().iterator();
2217 while( mapItr.hasNext() ) {
2218 Map.Entry me = (Map.Entry) mapItr.next();
2219 Integer paramIndex = (Integer) me.getKey();
2220 Set<HeapRegionNode> hrnRset = (Set<HeapRegionNode>) me.getValue();
2222 Iterator<HeapRegionNode> hrnItr = hrnRset.iterator();
2223 while( hrnItr.hasNext() ) {
2224 HeapRegionNode hrnR = hrnItr.next();
2225 pd.mapRegionToParamReachable( hrnR, paramIndex );
2229 // and we're done in this method for special param decomp mode
2234 // now iterate over reachable nodes to rewrite their alpha, and
2235 // classify edges found for beta rewrite
2236 Hashtable<TokenTuple, ReachabilitySet> tokens2states = new Hashtable<TokenTuple, ReachabilitySet>();
2238 Hashtable< Integer, Set<Vector> > edges_p2p = new Hashtable< Integer, Set<Vector> >();
2239 Hashtable< Integer, Set<Vector> > edges_p2s = new Hashtable< Integer, Set<Vector> >();
2240 Hashtable< Integer, Set<Vector> > edges_s2p = new Hashtable< Integer, Set<Vector> >();
2241 Hashtable< Integer, Set<Vector> > edges_s2s = new Hashtable< Integer, Set<Vector> >();
2242 Hashtable< Integer, Set<Vector> > edges_up_dr = new Hashtable< Integer, Set<Vector> >();
2243 Hashtable< Integer, Set<Vector> > edges_up_r = new Hashtable< Integer, Set<Vector> >();
2246 // so again, with respect to some arg i...
2247 lnArgItr = paramIndex2ln.entrySet().iterator();
2248 while( lnArgItr.hasNext() ) {
2249 Map.Entry me = (Map.Entry) lnArgItr.next();
2250 Integer index = (Integer) me.getKey();
2251 LabelNode lnArg_i = (LabelNode) me.getValue();
2253 TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary.get( index );
2254 TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( index );
2257 ensureEmptyEdgeIndexPair( edges_p2p, index );
2258 ensureEmptyEdgeIndexPair( edges_p2s, index );
2259 ensureEmptyEdgeIndexPair( edges_s2p, index );
2260 ensureEmptyEdgeIndexPair( edges_s2s, index );
2261 ensureEmptyEdgeIndexPair( edges_up_dr, index );
2262 ensureEmptyEdgeIndexPair( edges_up_r, index );
2264 Set<HeapRegionNode> dr = pi2dr.get( index );
2265 Iterator<HeapRegionNode> hrnItr = dr.iterator();
2266 while( hrnItr.hasNext() ) {
2267 // this heap region is definitely an "a_i" or primary by virtue of being in dr
2268 HeapRegionNode hrn = hrnItr.next();
2270 tokens2states.clear();
2271 tokens2states.put( p_i, hrn.getAlpha() );
2273 rewriteCallerReachability( index,
2276 paramIndex2rewriteH_p.get( index ),
2278 paramIndex2rewrite_d_p,
2279 paramIndex2rewrite_d_s,
2280 paramIndex2rewriteD,
2285 nodesWithNewAlpha.add( hrn );
2288 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
2289 while( edgeItr.hasNext() ) {
2290 ReferenceEdge edge = edgeItr.next();
2291 OwnershipNode on = edge.getSrc();
2293 boolean edge_classified = false;
2296 if( on instanceof HeapRegionNode ) {
2297 // hrn0 may be "a_j" and/or "r_j" or even neither
2298 HeapRegionNode hrn0 = (HeapRegionNode) on;
2300 Iterator itr = pi2dr.entrySet().iterator();
2301 while( itr.hasNext() ) {
2302 Map.Entry mo = (Map.Entry) itr.next();
2303 Integer pi = (Integer) mo.getKey();
2304 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
2306 if( dr_i.contains( hrn0 ) ) {
2307 addEdgeIndexPair( edges_p2p, pi, edge, index );
2308 edge_classified = true;
2312 itr = pi2r.entrySet().iterator();
2313 while( itr.hasNext() ) {
2314 Map.Entry mo = (Map.Entry) itr.next();
2315 Integer pi = (Integer) mo.getKey();
2316 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
2318 if( r_i.contains( hrn0 ) ) {
2319 addEdgeIndexPair( edges_s2p, pi, edge, index );
2320 edge_classified = true;
2325 // all of these edges are upstream of directly reachable objects
2326 if( !edge_classified ) {
2327 addEdgeIndexPair( edges_up_dr, index, edge, index );
2333 Set<HeapRegionNode> r = pi2r.get( index );
2334 hrnItr = r.iterator();
2335 while( hrnItr.hasNext() ) {
2336 // this heap region is definitely an "r_i" or secondary by virtue of being in r
2337 HeapRegionNode hrn = hrnItr.next();
2339 if( paramIndex2rewriteH_s.containsKey( index ) ) {
2341 tokens2states.clear();
2342 tokens2states.put( p_i, new ReachabilitySet().makeCanonical() );
2343 tokens2states.put( s_i, hrn.getAlpha() );
2345 rewriteCallerReachability( index,
2348 paramIndex2rewriteH_s.get( index ),
2350 paramIndex2rewrite_d_p,
2351 paramIndex2rewrite_d_s,
2352 paramIndex2rewriteD,
2357 nodesWithNewAlpha.add( hrn );
2361 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
2362 while( edgeItr.hasNext() ) {
2363 ReferenceEdge edge = edgeItr.next();
2364 OwnershipNode on = edge.getSrc();
2366 boolean edge_classified = false;
2368 if( on instanceof HeapRegionNode ) {
2369 // hrn0 may be "a_j" and/or "r_j" or even neither
2370 HeapRegionNode hrn0 = (HeapRegionNode) on;
2372 Iterator itr = pi2dr.entrySet().iterator();
2373 while( itr.hasNext() ) {
2374 Map.Entry mo = (Map.Entry) itr.next();
2375 Integer pi = (Integer) mo.getKey();
2376 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
2378 if( dr_i.contains( hrn0 ) ) {
2379 addEdgeIndexPair( edges_p2s, pi, edge, index );
2380 edge_classified = true;
2384 itr = pi2r.entrySet().iterator();
2385 while( itr.hasNext() ) {
2386 Map.Entry mo = (Map.Entry) itr.next();
2387 Integer pi = (Integer) mo.getKey();
2388 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
2390 if( r_i.contains( hrn0 ) ) {
2391 addEdgeIndexPair( edges_s2s, pi, edge, index );
2392 edge_classified = true;
2397 // these edges are all upstream of some reachable node
2398 if( !edge_classified ) {
2399 addEdgeIndexPair( edges_up_r, index, edge, index );
2406 // and again, with respect to some arg i...
2407 lnArgItr = paramIndex2ln.entrySet().iterator();
2408 while( lnArgItr.hasNext() ) {
2409 Map.Entry me = (Map.Entry) lnArgItr.next();
2410 Integer index = (Integer) me.getKey();
2411 LabelNode lnArg_i = (LabelNode) me.getValue();
2414 // update reachable edges
2415 Iterator edgeItr = edges_p2p.get( index ).iterator();
2416 while( edgeItr.hasNext() ) {
2417 Vector mo = (Vector) edgeItr.next();
2418 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2419 Integer indexJ = (Integer) mo.get( 1 );
2421 if( !paramIndex2rewriteJ_p2p.containsKey( makeMapKey( index,
2423 edge.getField() ) ) ) {
2427 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2430 tokens2states.clear();
2431 tokens2states.put( p_j, edge.getBeta() );
2433 rewriteCallerReachability( index,
2436 paramIndex2rewriteJ_p2p.get( makeMapKey( index,
2438 edge.getField() ) ),
2440 paramIndex2rewrite_d_p,
2441 paramIndex2rewrite_d_s,
2442 paramIndex2rewriteD,
2447 edgesWithNewBeta.add( edge );
2451 edgeItr = edges_p2s.get( index ).iterator();
2452 while( edgeItr.hasNext() ) {
2453 Vector mo = (Vector) edgeItr.next();
2454 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2455 Integer indexJ = (Integer) mo.get( 1 );
2457 if( !paramIndex2rewriteJ_p2s.containsKey( makeMapKey( index,
2458 edge.getField() ) ) ) {
2462 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2465 tokens2states.clear();
2466 tokens2states.put( s_j, edge.getBeta() );
2468 rewriteCallerReachability( index,
2471 paramIndex2rewriteJ_p2s.get( makeMapKey( index,
2472 edge.getField() ) ),
2474 paramIndex2rewrite_d_p,
2475 paramIndex2rewrite_d_s,
2476 paramIndex2rewriteD,
2481 edgesWithNewBeta.add( edge );
2485 edgeItr = edges_s2p.get( index ).iterator();
2486 while( edgeItr.hasNext() ) {
2487 Vector mo = (Vector) edgeItr.next();
2488 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2489 Integer indexJ = (Integer) mo.get( 1 );
2491 if( !paramIndex2rewriteJ_s2p.containsKey( index ) ) {
2495 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2498 tokens2states.clear();
2499 tokens2states.put( p_j, edge.getBeta() );
2501 rewriteCallerReachability( index,
2504 paramIndex2rewriteJ_s2p.get( index ),
2506 paramIndex2rewrite_d_p,
2507 paramIndex2rewrite_d_s,
2508 paramIndex2rewriteD,
2513 edgesWithNewBeta.add( edge );
2517 edgeItr = edges_s2s.get( index ).iterator();
2518 while( edgeItr.hasNext() ) {
2519 Vector mo = (Vector) edgeItr.next();
2520 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2521 Integer indexJ = (Integer) mo.get( 1 );
2523 if( !paramIndex2rewriteJ_s2s.containsKey( index ) ) {
2527 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2530 tokens2states.clear();
2531 tokens2states.put( s_j, edge.getBeta() );
2533 rewriteCallerReachability( index,
2536 paramIndex2rewriteJ_s2s.get( index ),
2538 paramIndex2rewrite_d_p,
2539 paramIndex2rewrite_d_s,
2540 paramIndex2rewriteD,
2545 edgesWithNewBeta.add( edge );
2549 // update directly upstream edges
2550 Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
2551 new Hashtable<ReferenceEdge, ChangeTupleSet>();
2553 HashSet<ReferenceEdge> edgesDirectlyUpstream =
2554 new HashSet<ReferenceEdge>();
2556 edgeItr = edges_up_dr.get( index ).iterator();
2557 while( edgeItr.hasNext() ) {
2558 Vector mo = (Vector) edgeItr.next();
2559 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2560 Integer indexJ = (Integer) mo.get( 1 );
2562 edgesDirectlyUpstream.add( edge );
2564 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2567 // start with K_p2 and p_j
2568 tokens2states.clear();
2569 tokens2states.put( p_j, edge.getBeta() );
2571 rewriteCallerReachability( index,
2574 paramIndex2rewriteK_p2.get( index ),
2576 paramIndex2rewrite_d_p,
2577 paramIndex2rewrite_d_s,
2578 paramIndex2rewriteD,
2581 edgeUpstreamPlannedChanges );
2583 // and add in s_j, if required, and do K_p
2584 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2586 tokens2states.put( s_j, edge.getBeta() );
2589 rewriteCallerReachability( index,
2592 paramIndex2rewriteK_p.get( index ),
2594 paramIndex2rewrite_d_p,
2595 paramIndex2rewrite_d_s,
2596 paramIndex2rewriteD,
2599 edgeUpstreamPlannedChanges );
2601 edgesWithNewBeta.add( edge );
2604 propagateTokensOverEdges( edgesDirectlyUpstream,
2605 edgeUpstreamPlannedChanges,
2609 // update upstream edges
2610 edgeUpstreamPlannedChanges =
2611 new Hashtable<ReferenceEdge, ChangeTupleSet>();
2613 HashSet<ReferenceEdge> edgesUpstream =
2614 new HashSet<ReferenceEdge>();
2616 edgeItr = edges_up_r.get( index ).iterator();
2617 while( edgeItr.hasNext() ) {
2618 Vector mo = (Vector) edgeItr.next();
2619 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2620 Integer indexJ = (Integer) mo.get( 1 );
2622 if( !paramIndex2rewriteK_s.containsKey( index ) ) {
2626 edgesUpstream.add( edge );
2628 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2631 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2634 tokens2states.clear();
2635 tokens2states.put( p_j, rsWttsEmpty );
2636 tokens2states.put( s_j, edge.getBeta() );
2638 rewriteCallerReachability( index,
2641 paramIndex2rewriteK_s.get( index ),
2643 paramIndex2rewrite_d_p,
2644 paramIndex2rewrite_d_s,
2645 paramIndex2rewriteD,
2648 edgeUpstreamPlannedChanges );
2650 edgesWithNewBeta.add( edge );
2653 propagateTokensOverEdges( edgesUpstream,
2654 edgeUpstreamPlannedChanges,
2657 } // end effects per argument/parameter map
2660 // commit changes to alpha and beta
2661 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
2662 while( nodeItr.hasNext() ) {
2663 nodeItr.next().applyAlphaNew();
2666 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
2667 while( edgeItr.hasNext() ) {
2668 edgeItr.next().applyBetaNew();
2672 // verify the existence of allocation sites and their
2673 // shadows from the callee in the context of this caller graph
2674 // then map allocated nodes of callee onto the caller shadows
2676 Hashtable<TokenTuple, ReachabilitySet> tokens2statesEmpty = new Hashtable<TokenTuple, ReachabilitySet>();
2678 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
2679 while( asItr.hasNext() ) {
2680 AllocationSite allocSite = asItr.next();
2682 // grab the summary in the caller just to make sure
2683 // the allocation site has nodes in the caller
2684 HeapRegionNode hrnSummary = getSummaryNode( allocSite );
2686 // assert that the shadow nodes have no reference edges
2687 // because they're brand new to the graph, or last time
2688 // they were used they should have been cleared of edges
2689 HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
2690 assert hrnShadowSummary.getNumReferencers() == 0;
2691 assert hrnShadowSummary.getNumReferencees() == 0;
2693 // then bring g_ij onto g'_ij and rewrite
2694 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode( allocSite );
2695 hrnShadowSummary.setAlpha( toShadowTokens( ogCallee, hrnSummaryCallee.getAlpha() ) );
2697 // shadow nodes only are touched by a rewrite one time,
2698 // so rewrite and immediately commit--and they don't belong
2699 // to a particular parameter, so use a bogus param index
2700 // that pulls a self-rewrite out of H
2701 rewriteCallerReachability( bogusIndex,
2704 funcScriptR( hrnShadowSummary.getAlpha(), ogCallee, mc ),
2706 paramIndex2rewrite_d_p,
2707 paramIndex2rewrite_d_s,
2708 paramIndex2rewriteD,
2713 hrnShadowSummary.applyAlphaNew();
2716 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
2717 Integer idIth = allocSite.getIthOldest(i);
2718 assert id2hrn.containsKey(idIth);
2719 HeapRegionNode hrnIth = id2hrn.get(idIth);
2721 Integer idShadowIth = -(allocSite.getIthOldest(i));
2722 assert id2hrn.containsKey(idShadowIth);
2723 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
2724 assert hrnIthShadow.getNumReferencers() == 0;
2725 assert hrnIthShadow.getNumReferencees() == 0;
2727 assert ogCallee.id2hrn.containsKey(idIth);
2728 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
2729 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
2731 rewriteCallerReachability( bogusIndex,
2734 funcScriptR( hrnIthShadow.getAlpha(), ogCallee, mc ),
2736 paramIndex2rewrite_d_p,
2737 paramIndex2rewrite_d_s,
2738 paramIndex2rewriteD,
2743 hrnIthShadow.applyAlphaNew();
2748 // for every heap region->heap region edge in the
2749 // callee graph, create the matching edge or edges
2750 // in the caller graph
2751 Set sCallee = ogCallee.id2hrn.entrySet();
2752 Iterator iCallee = sCallee.iterator();
2753 while( iCallee.hasNext() ) {
2754 Map.Entry meCallee = (Map.Entry) iCallee.next();
2755 Integer idCallee = (Integer) meCallee.getKey();
2756 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
2758 Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
2759 while( heapRegionsItrCallee.hasNext() ) {
2760 ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
2761 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
2762 Integer idChildCallee = hrnChildCallee.getID();
2764 // only address this edge if it is not a special initial edge
2765 if( !edgeCallee.isInitialParam() ) {
2767 // now we know that in the callee method's ownership graph
2768 // there is a heap region->heap region reference edge given
2769 // by heap region pointers:
2770 // hrnCallee -> heapChildCallee
2772 // or by the ownership-graph independent ID's:
2773 // idCallee -> idChildCallee
2775 // make the edge with src and dst so beta info is
2776 // calculated once, then copy it for each new edge in caller
2778 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null,
2780 edgeCallee.getType(),
2781 edgeCallee.getField(),
2783 funcScriptR( toShadowTokens( ogCallee,
2784 edgeCallee.getBeta()
2790 rewriteCallerReachability( bogusIndex,
2792 edgeNewInCallerTemplate,
2793 edgeNewInCallerTemplate.getBeta(),
2795 paramIndex2rewrite_d_p,
2796 paramIndex2rewrite_d_s,
2797 paramIndex2rewriteD,
2802 edgeNewInCallerTemplate.applyBetaNew();
2805 // So now make a set of possible source heaps in the caller graph
2806 // and a set of destination heaps in the caller graph, and make
2807 // a reference edge in the caller for every possible (src,dst) pair
2808 HashSet<HeapRegionNode> possibleCallerSrcs =
2809 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2810 (HeapRegionNode) edgeCallee.getSrc(),
2814 HashSet<HeapRegionNode> possibleCallerDsts =
2815 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2816 edgeCallee.getDst(),
2820 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
2821 Iterator srcItr = possibleCallerSrcs.iterator();
2822 while( srcItr.hasNext() ) {
2823 HeapRegionNode src = (HeapRegionNode) srcItr.next();
2825 if( !hasMatchingField( src, edgeCallee ) ) {
2826 // prune this source node possibility
2830 Iterator dstItr = possibleCallerDsts.iterator();
2831 while( dstItr.hasNext() ) {
2832 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
2834 if( !hasMatchingType( edgeCallee, dst ) ) {
2839 // otherwise the caller src and dst pair can match the edge, so make it
2840 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2841 edgeNewInCaller.setSrc( src );
2842 edgeNewInCaller.setDst( dst );
2844 // handle taint info if callee created this edge
2846 Set<Integer> pParamSet=idPrimary2paramIndexSet.get(dst.getID());
2847 Set<Integer> sParamSet=idSecondary2paramIndexSet.get(dst.getID());
2848 HashSet<Integer> paramSet=new HashSet<Integer>();
2849 if(pParamSet!=null){
2850 paramSet.addAll(pParamSet);
2852 if(sParamSet!=null){
2853 paramSet.addAll(sParamSet);
2855 Iterator<Integer> paramIter=paramSet.iterator();
2856 int newTaintIdentifier=0;
2857 while(paramIter.hasNext()){
2858 Integer paramIdx=paramIter.next();
2859 edgeNewInCaller.tainedBy(paramIdx);
2862 ReferenceEdge edgeExisting = src.getReferenceTo( dst,
2863 edgeNewInCaller.getType(),
2864 edgeNewInCaller.getField() );
2865 if( edgeExisting == null ) {
2866 // if this edge doesn't exist in the caller, create it
2867 addReferenceEdge( src, dst, edgeNewInCaller );
2870 // if it already exists, merge with it
2871 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2880 // return value may need to be assigned in caller
2881 TempDescriptor returnTemp = fc.getReturnTemp();
2882 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2884 LabelNode lnLhsCaller = getLabelNodeFromTemp( returnTemp );
2885 clearReferenceEdgesFrom( lnLhsCaller, null, null, true );
2887 LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp( tdReturn );
2888 Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
2889 while( edgeCalleeItr.hasNext() ) {
2890 ReferenceEdge edgeCallee = edgeCalleeItr.next();
2892 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null,
2894 edgeCallee.getType(),
2895 edgeCallee.getField(),
2897 funcScriptR( toShadowTokens(ogCallee,
2898 edgeCallee.getBeta() ),
2902 rewriteCallerReachability( bogusIndex,
2904 edgeNewInCallerTemplate,
2905 edgeNewInCallerTemplate.getBeta(),
2907 paramIndex2rewrite_d_p,
2908 paramIndex2rewrite_d_s,
2909 paramIndex2rewriteD,
2914 edgeNewInCallerTemplate.applyBetaNew();
2917 HashSet<HeapRegionNode> assignCallerRhs =
2918 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2919 edgeCallee.getDst(),
2923 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
2924 while( itrHrn.hasNext() ) {
2925 HeapRegionNode hrnCaller = itrHrn.next();
2927 if( !hasMatchingType( edgeCallee, hrnCaller ) ) {
2932 // otherwise caller node can match callee edge, so make it
2933 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2934 edgeNewInCaller.setSrc( lnLhsCaller );
2935 edgeNewInCaller.setDst( hrnCaller );
2937 ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo( hrnCaller,
2938 edgeNewInCaller.getType(),
2939 edgeNewInCaller.getField() );
2940 if( edgeExisting == null ) {
2942 // if this edge doesn't exist in the caller, create it
2943 addReferenceEdge( lnLhsCaller, hrnCaller, edgeNewInCaller );
2945 // if it already exists, merge with it
2946 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2953 if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
2954 fm.getMethod().getSymbol().equals( debugCallee ) ) {
2956 writeGraph( "debug7JustBeforeMergeToKCapacity", true, true, true, false, false );
2957 } catch( IOException e ) {}
2962 // merge the shadow nodes of allocation sites back down to normal capacity
2963 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
2964 while( allocItr.hasNext() ) {
2965 AllocationSite as = allocItr.next();
2967 // first age each allocation site enough times to make room for the shadow nodes
2968 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2972 // then merge the shadow summary into the normal summary
2973 HeapRegionNode hrnSummary = getSummaryNode( as );
2974 assert hrnSummary != null;
2976 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as );
2977 assert hrnSummaryShadow != null;
2979 mergeIntoSummary( hrnSummaryShadow, hrnSummary );
2981 // then clear off after merge
2982 clearReferenceEdgesFrom( hrnSummaryShadow, null, null, true );
2983 clearReferenceEdgesTo ( hrnSummaryShadow, null, null, true );
2984 hrnSummaryShadow.setAlpha( new ReachabilitySet().makeCanonical() );
2986 // then transplant shadow nodes onto the now clean normal nodes
2987 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2989 Integer idIth = as.getIthOldest( i );
2990 HeapRegionNode hrnIth = id2hrn.get( idIth );
2991 Integer idIthShadow = as.getIthOldestShadow( i );
2992 HeapRegionNode hrnIthShadow = id2hrn.get( idIthShadow );
2994 transferOnto( hrnIthShadow, hrnIth );
2996 // clear off shadow nodes after transfer
2997 clearReferenceEdgesFrom( hrnIthShadow, null, null, true );
2998 clearReferenceEdgesTo ( hrnIthShadow, null, null, true );
2999 hrnIthShadow.setAlpha( new ReachabilitySet().makeCanonical() );
3002 // finally, globally change shadow tokens into normal tokens
3003 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
3004 while( itrAllLabelNodes.hasNext() ) {
3005 Map.Entry me = (Map.Entry) itrAllLabelNodes.next();
3006 LabelNode ln = (LabelNode) me.getValue();
3008 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
3009 while( itrEdges.hasNext() ) {
3010 unshadowTokens( as, itrEdges.next() );
3014 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3015 while( itrAllHRNodes.hasNext() ) {
3016 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
3017 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
3019 unshadowTokens( as, hrnToAge );
3021 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
3022 while( itrEdges.hasNext() ) {
3023 unshadowTokens( as, itrEdges.next() );
3029 if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
3030 fm.getMethod().getSymbol().equals( debugCallee ) ) {
3032 writeGraph( "debug8JustBeforeSweep", true, true, true, false, false );
3033 } catch( IOException e ) {}
3037 // improve reachability as much as possible
3038 if( !DISABLE_GLOBAL_SWEEP ) {
3043 if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
3044 fm.getMethod().getSymbol().equals( debugCallee ) ) {
3046 writeGraph( "debug9endResolveCall", true, true, true, false, false );
3047 } catch( IOException e ) {}
3048 System.out.println( " "+mc+" done calling "+fm );
3059 protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
3061 // if no type, then it's a match-everything region
3062 TypeDescriptor tdSrc = src.getType();
3063 if( tdSrc == null ) {
3067 if( tdSrc.isArray() ) {
3068 TypeDescriptor td = edge.getType();
3071 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3072 assert tdSrcDeref != null;
3074 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3078 return edge.getField().equals( OwnershipAnalysis.arrayElementFieldName );
3081 // if it's not a class, it doesn't have any fields to match
3082 if( !tdSrc.isClass() ) {
3086 ClassDescriptor cd = tdSrc.getClassDesc();
3087 while( cd != null ) {
3088 Iterator fieldItr = cd.getFields();
3090 while( fieldItr.hasNext() ) {
3091 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3093 if( fd.getType().equals( edge.getType() ) &&
3094 fd.getSymbol().equals( edge.getField() ) ) {
3099 cd = cd.getSuperDesc();
3102 // otherwise it is a class with fields
3103 // but we didn't find a match
3108 protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
3110 // if the region has no type, matches everything
3111 TypeDescriptor tdDst = dst.getType();
3112 if( tdDst == null ) {
3116 // if the type is not a class or an array, don't
3117 // match because primitives are copied, no aliases
3118 ClassDescriptor cdDst = tdDst.getClassDesc();
3119 if( cdDst == null && !tdDst.isArray() ) {
3123 // if the edge type is null, it matches everything
3124 TypeDescriptor tdEdge = edge.getType();
3125 if( tdEdge == null ) {
3129 return typeUtil.isSuperorType(tdEdge, tdDst);
3134 protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
3135 edge.setBeta(edge.getBeta().unshadowTokens(as) );
3138 protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
3139 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
3143 private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
3144 ReachabilitySet rsIn) {
3146 ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical();
3148 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
3149 while( allocItr.hasNext() ) {
3150 AllocationSite as = allocItr.next();
3152 rsOut = rsOut.toShadowTokens(as);
3155 return rsOut.makeCanonical();
3159 private void rewriteCallerReachability(Integer paramIndex,
3162 ReachabilitySet rules,
3163 Hashtable<TokenTuple, ReachabilitySet> tokens2states,
3164 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_p,
3165 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_s,
3166 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
3167 OwnershipGraph ogCallee,
3168 boolean makeChangeSet,
3169 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
3171 assert(hrn == null && edge != null) ||
3172 (hrn != null && edge == null);
3174 assert rules != null;
3175 assert tokens2states != null;
3177 ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
3179 // for initializing structures in this method
3180 TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
3182 // use this to construct a change set if required; the idea is to
3183 // map every partially rewritten token tuple set to the set of
3184 // caller-context token tuple sets that were used to generate it
3185 Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
3186 new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
3187 rewritten2source.put( ttsEmpty, new HashSet<TokenTupleSet>() );
3190 Iterator<TokenTupleSet> rulesItr = rules.iterator();
3191 while(rulesItr.hasNext()) {
3192 TokenTupleSet rule = rulesItr.next();
3194 ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
3196 Iterator<TokenTuple> ruleItr = rule.iterator();
3197 while(ruleItr.hasNext()) {
3198 TokenTuple ttCallee = ruleItr.next();
3200 // compute the possibilities for rewriting this callee token
3201 ReachabilitySet ttCalleeRewrites = null;
3202 boolean callerSourceUsed = false;
3204 if( tokens2states.containsKey( ttCallee ) ) {
3205 callerSourceUsed = true;
3206 ttCalleeRewrites = tokens2states.get( ttCallee );
3207 assert ttCalleeRewrites != null;
3209 } else if( ogCallee.paramTokenPrimary2paramIndex.containsKey( ttCallee ) ) {
3211 Integer paramIndex_j = ogCallee.paramTokenPrimary2paramIndex.get( ttCallee );
3212 assert paramIndex_j != null;
3213 ttCalleeRewrites = paramIndex2rewrite_d_p.get( paramIndex_j );
3214 assert ttCalleeRewrites != null;
3216 } else if( ogCallee.paramTokenSecondary2paramIndex.containsKey( ttCallee ) ) {
3218 Integer paramIndex_j = ogCallee.paramTokenSecondary2paramIndex.get( ttCallee );
3219 assert paramIndex_j != null;
3220 ttCalleeRewrites = paramIndex2rewrite_d_s.get( paramIndex_j );
3221 assert ttCalleeRewrites != null;
3223 } else if( ogCallee.paramTokenSecondaryPlus2paramIndex.containsKey( ttCallee ) ) {
3225 Integer paramIndex_j = ogCallee.paramTokenSecondaryPlus2paramIndex.get( ttCallee );
3226 assert paramIndex_j != null;
3227 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
3228 assert ttCalleeRewrites != null;
3230 } else if( ogCallee.paramTokenSecondaryStar2paramIndex.containsKey( ttCallee ) ) {
3232 Integer paramIndex_j = ogCallee.paramTokenSecondaryStar2paramIndex.get( ttCallee );
3233 assert paramIndex_j != null;
3234 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
3235 assert ttCalleeRewrites != null;
3238 // otherwise there's no need for a rewrite, just pass this one on
3239 TokenTupleSet ttsCaller = new TokenTupleSet( ttCallee ).makeCanonical();
3240 ttCalleeRewrites = new ReachabilitySet( ttsCaller ).makeCanonical();
3243 // branch every version of the working rewritten rule with
3244 // the possibilities for rewriting the current callee token
3245 ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
3247 Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
3248 while( rewrittenRuleItr.hasNext() ) {
3249 TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
3251 Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
3252 while( ttCalleeRewritesItr.hasNext() ) {
3253 TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
3255 TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
3257 if( makeChangeSet ) {
3258 // in order to keep the list of source token tuple sets
3259 // start with the sets used to make the partially rewritten
3260 // rule up to this point
3261 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewritten );
3262 assert sourceSets != null;
3264 // make a shallow copy for possible modification
3265 sourceSets = (HashSet<TokenTupleSet>) sourceSets.clone();
3267 // if we used something from the caller to rewrite it, remember
3268 if( callerSourceUsed ) {
3269 sourceSets.add( ttsBranch );
3272 // set mapping for the further rewritten rule
3273 rewritten2source.put( ttsRewrittenNext, sourceSets );
3276 rewrittenRuleWithTTCallee =
3277 rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
3281 // now the rewritten rule's possibilities have been extended by
3282 // rewriting the current callee token, remember result
3283 rewrittenRule = rewrittenRuleWithTTCallee;
3286 // the rule has been entirely rewritten into the caller context
3287 // now, so add it to the new reachability information
3288 callerReachabilityNew =
3289 callerReachabilityNew.union( rewrittenRule );
3292 if( makeChangeSet ) {
3293 ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
3295 // each possibility for the final reachability should have a set of
3296 // caller sources mapped to it, use to create the change set
3297 Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
3298 while( callerReachabilityItr.hasNext() ) {
3299 TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
3300 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewrittenFinal );
3301 assert sourceSets != null;
3303 Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
3304 while( sourceSetsItr.hasNext() ) {
3305 TokenTupleSet ttsSource = sourceSetsItr.next();
3308 callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
3312 assert edgePlannedChanges != null;
3313 edgePlannedChanges.put( edge, callerChangeSet );
3317 edge.setBetaNew( edge.getBetaNew().union( callerReachabilityNew ) );
3319 hrn.setAlphaNew( hrn.getAlphaNew().union( callerReachabilityNew ) );
3325 private HashSet<HeapRegionNode>
3326 getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
3327 HeapRegionNode hrnCallee,
3328 Hashtable<Integer, Set<HeapRegionNode> > pi2dr,
3329 Hashtable<Integer, Set<HeapRegionNode> > pi2r
3332 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
3334 Set<Integer> paramIndicesCallee_p = ogCallee.idPrimary2paramIndexSet .get( hrnCallee.getID() );
3335 Set<Integer> paramIndicesCallee_s = ogCallee.idSecondary2paramIndexSet.get( hrnCallee.getID() );
3337 if( paramIndicesCallee_p == null &&
3338 paramIndicesCallee_s == null ) {
3339 // this is a node allocated in the callee and it has
3340 // exactly one shadow node in the caller to map to
3341 AllocationSite as = hrnCallee.getAllocationSite();
3344 int age = as.getAgeCategory( hrnCallee.getID() );
3345 assert age != AllocationSite.AGE_notInThisSite;
3348 if( age == AllocationSite.AGE_summary ) {
3349 idCaller = as.getSummaryShadow();
3351 } else if( age == AllocationSite.AGE_oldest ) {
3352 idCaller = as.getOldestShadow();
3355 assert age == AllocationSite.AGE_in_I;
3357 Integer I = as.getAge( hrnCallee.getID() );
3360 idCaller = as.getIthOldestShadow( I );
3363 assert id2hrn.containsKey( idCaller );
3364 possibleCallerHRNs.add( id2hrn.get( idCaller ) );
3366 return possibleCallerHRNs;
3369 // find out what primary objects this might be
3370 if( paramIndicesCallee_p != null ) {
3371 // this is a node that was created to represent a parameter
3372 // so it maps to some regions directly reachable from the arg labels
3373 Iterator<Integer> itrIndex = paramIndicesCallee_p.iterator();
3374 while( itrIndex.hasNext() ) {
3375 Integer paramIndexCallee = itrIndex.next();
3376 assert pi2dr.containsKey( paramIndexCallee );
3377 possibleCallerHRNs.addAll( pi2dr.get( paramIndexCallee ) );
3381 // find out what secondary objects this might be
3382 if( paramIndicesCallee_s != null ) {
3383 // this is a node that was created to represent objs reachable from
3384 // some parameter, so it maps to regions reachable from the arg labels
3385 Iterator<Integer> itrIndex = paramIndicesCallee_s.iterator();
3386 while( itrIndex.hasNext() ) {
3387 Integer paramIndexCallee = itrIndex.next();
3388 assert pi2r.containsKey( paramIndexCallee );
3389 possibleCallerHRNs.addAll( pi2r.get( paramIndexCallee ) );
3393 // TODO: is this true?
3394 // one of the two cases above should have put something in here
3395 //assert !possibleCallerHRNs.isEmpty();
3397 return possibleCallerHRNs;
3402 ////////////////////////////////////////////////////
3404 // This global sweep is an optional step to prune
3405 // reachability sets that are not internally
3406 // consistent with the global graph. It should be
3407 // invoked after strong updates or method calls.
3409 ////////////////////////////////////////////////////
3410 public void globalSweep() {
3412 // boldB is part of the phase 1 sweep
3413 Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> > boldB =
3414 new Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> >();
3416 // visit every heap region to initialize alphaNew and calculate boldB
3417 Set hrns = id2hrn.entrySet();
3418 Iterator itrHrns = hrns.iterator();
3419 while( itrHrns.hasNext() ) {
3420 Map.Entry me = (Map.Entry)itrHrns.next();
3421 Integer token = (Integer) me.getKey();
3422 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3424 // assert that this node and incoming edges have clean alphaNew
3425 // and betaNew sets, respectively
3426 assert rsEmpty.equals( hrn.getAlphaNew() );
3428 Iterator<ReferenceEdge> itrRers = hrn.iteratorToReferencers();
3429 while( itrRers.hasNext() ) {
3430 ReferenceEdge edge = itrRers.next();
3431 assert rsEmpty.equals( edge.getBetaNew() );
3434 // calculate boldB for this flagged node
3435 if( hrn.isFlagged() || hrn.isParameter() ) {
3437 Hashtable<ReferenceEdge, ReachabilitySet> boldB_f =
3438 new Hashtable<ReferenceEdge, ReachabilitySet>();
3440 Set<ReferenceEdge> workSetEdges = new HashSet<ReferenceEdge>();
3442 // initial boldB_f constraints
3443 Iterator<ReferenceEdge> itrRees = hrn.iteratorToReferencees();
3444 while( itrRees.hasNext() ) {
3445 ReferenceEdge edge = itrRees.next();
3447 assert !boldB.containsKey( edge );
3448 boldB_f.put( edge, edge.getBeta() );
3450 assert !workSetEdges.contains( edge );
3451 workSetEdges.add( edge );
3454 // enforce the boldB_f constraint at edges until we reach a fixed point
3455 while( !workSetEdges.isEmpty() ) {
3456 ReferenceEdge edge = workSetEdges.iterator().next();
3457 workSetEdges.remove( edge );
3459 Iterator<ReferenceEdge> itrPrime = edge.getDst().iteratorToReferencees();
3460 while( itrPrime.hasNext() ) {
3461 ReferenceEdge edgePrime = itrPrime.next();
3463 ReachabilitySet prevResult = boldB_f.get( edgePrime );
3464 ReachabilitySet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
3466 if( prevResult == null ||
3467 prevResult.union( intersection ).size() > prevResult.size() ) {
3469 if( prevResult == null ) {
3470 boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) );
3472 boldB_f.put( edgePrime, prevResult .union( intersection ) );
3474 workSetEdges.add( edgePrime );
3479 boldB.put( token, boldB_f );
3484 // use boldB to prune tokens from alpha states that are impossible
3485 // and propagate the differences backwards across edges
3486 HashSet<ReferenceEdge> edgesForPropagation = new HashSet<ReferenceEdge>();
3488 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
3489 new Hashtable<ReferenceEdge, ChangeTupleSet>();
3491 hrns = id2hrn.entrySet();
3492 itrHrns = hrns.iterator();
3493 while( itrHrns.hasNext() ) {
3494 Map.Entry me = (Map.Entry)itrHrns.next();
3495 Integer token = (Integer) me.getKey();
3496 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3498 // never remove the identity token from a flagged region
3499 // because it is trivially satisfied
3500 TokenTuple ttException = new TokenTuple( token,
3501 !hrn.isSingleObject(),
3502 TokenTuple.ARITY_ONE ).makeCanonical();
3504 ChangeTupleSet cts = new ChangeTupleSet().makeCanonical();
3506 // mark tokens for removal
3507 Iterator<TokenTupleSet> stateItr = hrn.getAlpha().iterator();
3508 while( stateItr.hasNext() ) {
3509 TokenTupleSet ttsOld = stateItr.next();
3511 TokenTupleSet markedTokens = new TokenTupleSet().makeCanonical();
3513 Iterator<TokenTuple> ttItr = ttsOld.iterator();
3514 while( ttItr.hasNext() ) {
3515 TokenTuple ttOld = ttItr.next();
3517 // never remove the identity token from a flagged region
3518 // because it is trivially satisfied
3519 if( hrn.isFlagged() || hrn.isParameter() ) {
3520 if( ttOld == ttException ) {
3525 // does boldB_ttOld allow this token?
3526 boolean foundState = false;
3527 Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3528 while( incidentEdgeItr.hasNext() ) {
3529 ReferenceEdge incidentEdge = incidentEdgeItr.next();
3531 // if it isn't allowed, mark for removal
3532 Integer idOld = ttOld.getToken();
3533 assert id2hrn.containsKey( idOld );
3534 Hashtable<ReferenceEdge, ReachabilitySet> B = boldB.get( idOld );
3535 ReachabilitySet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL!
3536 if( boldB_ttOld_incident != null &&
3537 boldB_ttOld_incident.contains( ttsOld ) ) {
3543 markedTokens = markedTokens.add( ttOld );
3547 // if there is nothing marked, just move on
3548 if( markedTokens.isEmpty() ) {
3549 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
3553 // remove all marked tokens and establish a change set that should
3554 // propagate backwards over edges from this node
3555 TokenTupleSet ttsPruned = new TokenTupleSet().makeCanonical();
3556 ttItr = ttsOld.iterator();
3557 while( ttItr.hasNext() ) {
3558 TokenTuple ttOld = ttItr.next();
3560 if( !markedTokens.containsTuple( ttOld ) ) {
3561 ttsPruned = ttsPruned.union( ttOld );
3564 assert !ttsOld.equals( ttsPruned );
3566 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
3567 ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
3568 cts = cts.union( ct );
3571 // throw change tuple set on all incident edges
3572 if( !cts.isEmpty() ) {
3573 Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3574 while( incidentEdgeItr.hasNext() ) {
3575 ReferenceEdge incidentEdge = incidentEdgeItr.next();
3577 edgesForPropagation.add( incidentEdge );
3579 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3580 edgePlannedChanges.put( incidentEdge, cts );
3582 edgePlannedChanges.put(
3584 edgePlannedChanges.get( incidentEdge ).union( cts )
3591 HashSet<ReferenceEdge> edgesUpdated = new HashSet<ReferenceEdge>();
3593 propagateTokensOverEdges( edgesForPropagation,
3597 // at the end of the 1st phase reference edges have
3598 // beta, betaNew that correspond to beta and betaR
3600 // commit beta<-betaNew, so beta=betaR and betaNew
3601 // will represent the beta' calculation in 2nd phase
3603 // commit alpha<-alphaNew because it won't change
3604 HashSet<ReferenceEdge> res = new HashSet<ReferenceEdge>();
3606 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3607 while( nodeItr.hasNext() ) {
3608 HeapRegionNode hrn = nodeItr.next();
3609 hrn.applyAlphaNew();
3610 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
3611 while( itrRes.hasNext() ) {
3612 res.add( itrRes.next() );
3618 Iterator<ReferenceEdge> edgeItr = res.iterator();
3619 while( edgeItr.hasNext() ) {
3620 ReferenceEdge edge = edgeItr.next();
3621 HeapRegionNode hrn = edge.getDst();
3623 // commit results of last phase
3624 if( edgesUpdated.contains( edge ) ) {
3625 edge.applyBetaNew();
3628 // compute intial condition of 2nd phase
3629 edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
3632 // every edge in the graph is the initial workset
3633 Set<ReferenceEdge> edgeWorkSet = (Set) res.clone();
3634 while( !edgeWorkSet.isEmpty() ) {
3635 ReferenceEdge edgePrime = edgeWorkSet.iterator().next();
3636 edgeWorkSet.remove( edgePrime );
3638 OwnershipNode on = edgePrime.getSrc();
3639 if( !(on instanceof HeapRegionNode) ) {
3642 HeapRegionNode hrn = (HeapRegionNode) on;
3644 Iterator<ReferenceEdge> itrEdge = hrn.iteratorToReferencers();
3645 while( itrEdge.hasNext() ) {
3646 ReferenceEdge edge = itrEdge.next();
3648 ReachabilitySet prevResult = edge.getBetaNew();
3649 assert prevResult != null;
3651 ReachabilitySet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
3653 if( prevResult.union( intersection ).size() > prevResult.size() ) {
3654 edge.setBetaNew( prevResult.union( intersection ) );
3655 edgeWorkSet.add( edge );
3660 // commit beta' (beta<-betaNew)
3661 edgeItr = res.iterator();
3662 while( edgeItr.hasNext() ) {
3663 edgeItr.next().applyBetaNew();
3669 ////////////////////////////////////////////////////
3670 // in merge() and equals() methods the suffix A
3671 // represents the passed in graph and the suffix
3672 // B refers to the graph in this object
3673 // Merging means to take the incoming graph A and
3674 // merge it into B, so after the operation graph B
3675 // is the final result.
3676 ////////////////////////////////////////////////////
3677 public void merge(OwnershipGraph og) {
3683 mergeOwnershipNodes(og);
3684 mergeReferenceEdges(og);
3685 mergeParamIndexMappings(og);
3686 mergeAllocationSites(og);
3690 protected void mergeOwnershipNodes(OwnershipGraph og) {
3691 Set sA = og.id2hrn.entrySet();
3692 Iterator iA = sA.iterator();
3693 while( iA.hasNext() ) {
3694 Map.Entry meA = (Map.Entry)iA.next();
3695 Integer idA = (Integer) meA.getKey();
3696 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3698 // if this graph doesn't have a node the
3699 // incoming graph has, allocate it
3700 if( !id2hrn.containsKey(idA) ) {
3701 HeapRegionNode hrnB = hrnA.copy();
3702 id2hrn.put(idA, hrnB);
3705 // otherwise this is a node present in both graphs
3706 // so make the new reachability set a union of the
3707 // nodes' reachability sets
3708 HeapRegionNode hrnB = id2hrn.get(idA);
3709 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
3713 // now add any label nodes that are in graph B but
3715 sA = og.td2ln.entrySet();
3717 while( iA.hasNext() ) {
3718 Map.Entry meA = (Map.Entry)iA.next();
3719 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3720 LabelNode lnA = (LabelNode) meA.getValue();
3722 // if the label doesn't exist in B, allocate and add it
3723 LabelNode lnB = getLabelNodeFromTemp(tdA);
3727 protected void mergeReferenceEdges(OwnershipGraph og) {
3730 Set sA = og.id2hrn.entrySet();
3731 Iterator iA = sA.iterator();
3732 while( iA.hasNext() ) {
3733 Map.Entry meA = (Map.Entry)iA.next();
3734 Integer idA = (Integer) meA.getKey();
3735 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3737 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3738 while( heapRegionsItrA.hasNext() ) {
3739 ReferenceEdge edgeA = heapRegionsItrA.next();
3740 HeapRegionNode hrnChildA = edgeA.getDst();
3741 Integer idChildA = hrnChildA.getID();
3743 // at this point we know an edge in graph A exists
3744 // idA -> idChildA, does this exist in B?
3745 assert id2hrn.containsKey(idA);
3746 HeapRegionNode hrnB = id2hrn.get(idA);
3747 ReferenceEdge edgeToMerge = null;
3749 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3750 while( heapRegionsItrB.hasNext() &&
3751 edgeToMerge == null ) {
3753 ReferenceEdge edgeB = heapRegionsItrB.next();
3754 HeapRegionNode hrnChildB = edgeB.getDst();
3755 Integer idChildB = hrnChildB.getID();
3757 // don't use the ReferenceEdge.equals() here because
3758 // we're talking about existence between graphs
3759 if( idChildB.equals( idChildA ) &&
3760 edgeB.typeAndFieldEquals( edgeA ) ) {
3762 edgeToMerge = edgeB;
3766 // if the edge from A was not found in B,
3768 if( edgeToMerge == null ) {
3769 assert id2hrn.containsKey(idChildA);
3770 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3771 edgeToMerge = edgeA.copy();
3772 edgeToMerge.setSrc(hrnB);
3773 edgeToMerge.setDst(hrnChildB);
3774 addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
3776 // otherwise, the edge already existed in both graphs
3777 // so merge their reachability sets
3779 // just replace this beta set with the union
3780 assert edgeToMerge != null;
3781 edgeToMerge.setBeta(
3782 edgeToMerge.getBeta().union(edgeA.getBeta() )
3785 edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
3786 if( !edgeA.isInitialParam() ) {
3787 edgeToMerge.setIsInitialParam(false);
3793 // and then again with label nodes
3794 sA = og.td2ln.entrySet();
3796 while( iA.hasNext() ) {
3797 Map.Entry meA = (Map.Entry)iA.next();
3798 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3799 LabelNode lnA = (LabelNode) meA.getValue();
3801 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
3802 while( heapRegionsItrA.hasNext() ) {
3803 ReferenceEdge edgeA = heapRegionsItrA.next();
3804 HeapRegionNode hrnChildA = edgeA.getDst();
3805 Integer idChildA = hrnChildA.getID();
3807 // at this point we know an edge in graph A exists
3808 // tdA -> idChildA, does this exist in B?
3809 assert td2ln.containsKey(tdA);
3810 LabelNode lnB = td2ln.get(tdA);
3811 ReferenceEdge edgeToMerge = null;
3813 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
3814 while( heapRegionsItrB.hasNext() &&
3815 edgeToMerge == null ) {
3817 ReferenceEdge edgeB = heapRegionsItrB.next();
3818 HeapRegionNode hrnChildB = edgeB.getDst();
3819 Integer idChildB = hrnChildB.getID();
3821 // don't use the ReferenceEdge.equals() here because
3822 // we're talking about existence between graphs
3823 if( idChildB.equals( idChildA ) &&
3824 edgeB.typeAndFieldEquals( edgeA ) ) {
3826 edgeToMerge = edgeB;
3830 // if the edge from A was not found in B,
3832 if( edgeToMerge == null ) {
3833 assert id2hrn.containsKey(idChildA);
3834 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3835 edgeToMerge = edgeA.copy();
3836 edgeToMerge.setSrc(lnB);
3837 edgeToMerge.setDst(hrnChildB);
3838 addReferenceEdge(lnB, hrnChildB, edgeToMerge);
3840 // otherwise, the edge already existed in both graphs
3841 // so merge their reachability sets
3843 // just replace this beta set with the union
3844 edgeToMerge.setBeta(
3845 edgeToMerge.getBeta().union(edgeA.getBeta() )
3847 edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
3848 if( !edgeA.isInitialParam() ) {
3849 edgeToMerge.setIsInitialParam(false);
3856 // you should only merge ownership graphs that have the
3857 // same number of parameters, or if one or both parameter
3858 // index tables are empty
3859 protected void mergeParamIndexMappings(OwnershipGraph og) {
3861 if( idPrimary2paramIndexSet.size() == 0 ) {
3863 idPrimary2paramIndexSet = og.idPrimary2paramIndexSet;
3864 paramIndex2idPrimary = og.paramIndex2idPrimary;
3866 idSecondary2paramIndexSet = og.idSecondary2paramIndexSet;
3867 paramIndex2idSecondary = og.paramIndex2idSecondary;
3869 paramIndex2tdQ = og.paramIndex2tdQ;
3870 paramIndex2tdR = og.paramIndex2tdR;
3872 paramTokenPrimary2paramIndex = og.paramTokenPrimary2paramIndex;
3873 paramIndex2paramTokenPrimary = og.paramIndex2paramTokenPrimary;
3875 paramTokenSecondary2paramIndex = og.paramTokenSecondary2paramIndex;
3876 paramIndex2paramTokenSecondary = og.paramIndex2paramTokenSecondary;
3877 paramTokenSecondaryPlus2paramIndex = og.paramTokenSecondaryPlus2paramIndex;
3878 paramIndex2paramTokenSecondaryPlus = og.paramIndex2paramTokenSecondaryPlus;
3879 paramTokenSecondaryStar2paramIndex = og.paramTokenSecondaryStar2paramIndex;
3880 paramIndex2paramTokenSecondaryStar = og.paramIndex2paramTokenSecondaryStar;
3885 if( og.idPrimary2paramIndexSet.size() == 0 ) {
3887 og.idPrimary2paramIndexSet = idPrimary2paramIndexSet;
3888 og.paramIndex2idPrimary = paramIndex2idPrimary;
3890 og.idSecondary2paramIndexSet = idSecondary2paramIndexSet;
3891 og.paramIndex2idSecondary = paramIndex2idSecondary;
3893 og.paramIndex2tdQ = paramIndex2tdQ;
3894 og.paramIndex2tdR = paramIndex2tdR;
3896 og.paramTokenPrimary2paramIndex = paramTokenPrimary2paramIndex;
3897 og.paramIndex2paramTokenPrimary = paramIndex2paramTokenPrimary;
3899 og.paramTokenSecondary2paramIndex = paramTokenSecondary2paramIndex;
3900 og.paramIndex2paramTokenSecondary = paramIndex2paramTokenSecondary;
3901 og.paramTokenSecondaryPlus2paramIndex = paramTokenSecondaryPlus2paramIndex;
3902 og.paramIndex2paramTokenSecondaryPlus = paramIndex2paramTokenSecondaryPlus;
3903 og.paramTokenSecondaryStar2paramIndex = paramTokenSecondaryStar2paramIndex;
3904 og.paramIndex2paramTokenSecondaryStar = paramIndex2paramTokenSecondaryStar;
3909 assert idPrimary2paramIndexSet.size() == og.idPrimary2paramIndexSet.size();
3910 assert idSecondary2paramIndexSet.size() == og.idSecondary2paramIndexSet.size();
3913 protected void mergeAllocationSites(OwnershipGraph og) {
3914 allocationSites.addAll(og.allocationSites);
3919 // it is necessary in the equals() member functions
3920 // to "check both ways" when comparing the data
3921 // structures of two graphs. For instance, if all
3922 // edges between heap region nodes in graph A are
3923 // present and equal in graph B it is not sufficient
3924 // to say the graphs are equal. Consider that there
3925 // may be edges in graph B that are not in graph A.
3926 // the only way to know that all edges in both graphs
3927 // are equally present is to iterate over both data
3928 // structures and compare against the other graph.
3929 public boolean equals(OwnershipGraph og) {
3935 if( !areHeapRegionNodesEqual(og) ) {
3939 if( !areLabelNodesEqual(og) ) {
3943 if( !areReferenceEdgesEqual(og) ) {
3947 if( !areParamIndexMappingsEqual(og) ) {
3951 // if everything is equal up to this point,
3952 // assert that allocationSites is also equal--
3953 // this data is redundant and kept for efficiency
3954 assert allocationSites.equals(og.allocationSites);
3959 protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
3961 if( !areallHRNinAalsoinBandequal(this, og) ) {
3965 if( !areallHRNinAalsoinBandequal(og, this) ) {
3972 static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
3973 OwnershipGraph ogB) {
3974 Set sA = ogA.id2hrn.entrySet();
3975 Iterator iA = sA.iterator();
3976 while( iA.hasNext() ) {
3977 Map.Entry meA = (Map.Entry)iA.next();
3978 Integer idA = (Integer) meA.getKey();
3979 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3981 if( !ogB.id2hrn.containsKey(idA) ) {
3985 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
3986 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
3995 protected boolean areLabelNodesEqual(OwnershipGraph og) {
3997 if( !areallLNinAalsoinBandequal(this, og) ) {
4001 if( !areallLNinAalsoinBandequal(og, this) ) {
4008 static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
4009 OwnershipGraph ogB) {
4010 Set sA = ogA.td2ln.entrySet();
4011 Iterator iA = sA.iterator();
4012 while( iA.hasNext() ) {
4013 Map.Entry meA = (Map.Entry)iA.next();
4014 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4016 if( !ogB.td2ln.containsKey(tdA) ) {
4025 protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
4026 if( !areallREinAandBequal(this, og) ) {
4033 static protected boolean areallREinAandBequal(OwnershipGraph ogA,
4034 OwnershipGraph ogB) {
4036 // check all the heap region->heap region edges
4037 Set sA = ogA.id2hrn.entrySet();
4038 Iterator iA = sA.iterator();
4039 while( iA.hasNext() ) {
4040 Map.Entry meA = (Map.Entry)iA.next();
4041 Integer idA = (Integer) meA.getKey();
4042 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4044 // we should have already checked that the same
4045 // heap regions exist in both graphs
4046 assert ogB.id2hrn.containsKey(idA);
4048 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
4052 // then check every edge in B for presence in A, starting
4053 // from the same parent HeapRegionNode
4054 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
4056 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
4061 // then check all the label->heap region edges
4062 sA = ogA.td2ln.entrySet();
4064 while( iA.hasNext() ) {
4065 Map.Entry meA = (Map.Entry)iA.next();
4066 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4067 LabelNode lnA = (LabelNode) meA.getValue();
4069 // we should have already checked that the same
4070 // label nodes exist in both graphs
4071 assert ogB.td2ln.containsKey(tdA);
4073 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
4077 // then check every edge in B for presence in A, starting
4078 // from the same parent LabelNode
4079 LabelNode lnB = ogB.td2ln.get(tdA);
4081 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
4090 static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
4092 OwnershipGraph ogB) {
4094 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
4095 while( itrA.hasNext() ) {
4096 ReferenceEdge edgeA = itrA.next();
4097 HeapRegionNode hrnChildA = edgeA.getDst();
4098 Integer idChildA = hrnChildA.getID();
4100 assert ogB.id2hrn.containsKey(idChildA);
4102 // at this point we know an edge in graph A exists
4103 // onA -> idChildA, does this exact edge exist in B?
4104 boolean edgeFound = false;
4106 OwnershipNode onB = null;
4107 if( onA instanceof HeapRegionNode ) {
4108 HeapRegionNode hrnA = (HeapRegionNode) onA;
4109 onB = ogB.id2hrn.get(hrnA.getID() );
4111 LabelNode lnA = (LabelNode) onA;
4112 onB = ogB.td2ln.get(lnA.getTempDescriptor() );
4115 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
4116 while( itrB.hasNext() ) {
4117 ReferenceEdge edgeB = itrB.next();
4118 HeapRegionNode hrnChildB = edgeB.getDst();
4119 Integer idChildB = hrnChildB.getID();
4121 if( idChildA.equals( idChildB ) &&
4122 edgeA.typeAndFieldEquals( edgeB ) ) {
4124 // there is an edge in the right place with the right field,
4125 // but do they have the same attributes?
4126 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
4141 protected boolean areParamIndexMappingsEqual(OwnershipGraph og) {
4143 if( idPrimary2paramIndexSet.size() != og.idPrimary2paramIndexSet.size() ) {
4147 if( idSecondary2paramIndexSet.size() != og.idSecondary2paramIndexSet.size() ) {
4155 public Set<HeapRegionNode> hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) {
4156 assert hrn1 != null;
4157 assert hrn2 != null;
4159 // then get the various tokens for these heap regions
4160 TokenTuple h1 = new TokenTuple(hrn1.getID(),
4161 !hrn1.isSingleObject(),
4162 TokenTuple.ARITY_ONE).makeCanonical();
4164 TokenTuple h1plus = new TokenTuple(hrn1.getID(),
4165 !hrn1.isSingleObject(),
4166 TokenTuple.ARITY_ONEORMORE).makeCanonical();
4168 TokenTuple h1star = new TokenTuple(hrn1.getID(),
4169 !hrn1.isSingleObject(),
4170 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
4172 TokenTuple h2 = new TokenTuple(hrn2.getID(),
4173 !hrn2.isSingleObject(),
4174 TokenTuple.ARITY_ONE).makeCanonical();
4176 TokenTuple h2plus = new TokenTuple(hrn2.getID(),
4177 !hrn2.isSingleObject(),
4178 TokenTuple.ARITY_ONEORMORE).makeCanonical();
4180 TokenTuple h2star = new TokenTuple(hrn2.getID(),
4181 !hrn2.isSingleObject(),
4182 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
4184 // then get the merged beta of all out-going edges from these heap regions
4185 ReachabilitySet beta1 = new ReachabilitySet().makeCanonical();
4186 Iterator<ReferenceEdge> itrEdge = hrn1.iteratorToReferencees();
4187 while( itrEdge.hasNext() ) {
4188 ReferenceEdge edge = itrEdge.next();
4189 beta1 = beta1.union( edge.getBeta() );
4192 ReachabilitySet beta2 = new ReachabilitySet().makeCanonical();
4193 itrEdge = hrn2.iteratorToReferencees();
4194 while( itrEdge.hasNext() ) {
4195 ReferenceEdge edge = itrEdge.next();
4196 beta2 = beta2.union( edge.getBeta() );
4199 boolean aliasDetected = false;
4201 // only do this one if they are different tokens
4203 beta1.containsTupleSetWithBoth(h1, h2) ) {
4204 aliasDetected = true;
4206 if( beta1.containsTupleSetWithBoth(h1plus, h2) ) {
4207 aliasDetected = true;
4209 if( beta1.containsTupleSetWithBoth(h1star, h2) ) {
4210 aliasDetected = true;
4212 if( beta1.containsTupleSetWithBoth(h1, h2plus) ) {
4213 aliasDetected = true;
4215 if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) {
4216 aliasDetected = true;
4218 if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) {
4219 aliasDetected = true;
4221 if( beta1.containsTupleSetWithBoth(h1, h2star) ) {
4222 aliasDetected = true;
4224 if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) {
4225 aliasDetected = true;
4227 if( beta1.containsTupleSetWithBoth(h1star, h2star) ) {
4228 aliasDetected = true;
4232 beta2.containsTupleSetWithBoth(h1, h2) ) {
4233 aliasDetected = true;
4235 if( beta2.containsTupleSetWithBoth(h1plus, h2) ) {
4236 aliasDetected = true;
4238 if( beta2.containsTupleSetWithBoth(h1star, h2) ) {
4239 aliasDetected = true;
4241 if( beta2.containsTupleSetWithBoth(h1, h2plus) ) {
4242 aliasDetected = true;
4244 if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) {
4245 aliasDetected = true;
4247 if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) {
4248 aliasDetected = true;
4250 if( beta2.containsTupleSetWithBoth(h1, h2star) ) {
4251 aliasDetected = true;
4253 if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) {
4254 aliasDetected = true;
4256 if( beta2.containsTupleSetWithBoth(h1star, h2star) ) {
4257 aliasDetected = true;
4260 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4261 if( aliasDetected ) {
4262 common = findCommonReachableNodes( hrn1, hrn2 );
4263 if( !(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP) ) {
4264 assert !common.isEmpty();
4272 public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
4274 // get parameter 1's heap regions
4275 assert paramIndex2idPrimary.containsKey(paramIndex1);
4276 Integer idParamPri1 = paramIndex2idPrimary.get(paramIndex1);
4278 assert id2hrn.containsKey(idParamPri1);
4279 HeapRegionNode hrnParamPri1 = id2hrn.get(idParamPri1);
4280 assert hrnParamPri1 != null;
4282 HeapRegionNode hrnParamSec1 = null;
4283 if( paramIndex2idSecondary.containsKey(paramIndex1) ) {
4284 Integer idParamSec1 = paramIndex2idSecondary.get(paramIndex1);
4286 assert id2hrn.containsKey(idParamSec1);
4287 hrnParamSec1 = id2hrn.get(idParamSec1);
4288 assert hrnParamSec1 != null;
4292 // get the other parameter
4293 assert paramIndex2idPrimary.containsKey(paramIndex2);
4294 Integer idParamPri2 = paramIndex2idPrimary.get(paramIndex2);
4296 assert id2hrn.containsKey(idParamPri2);
4297 HeapRegionNode hrnParamPri2 = id2hrn.get(idParamPri2);
4298 assert hrnParamPri2 != null;
4300 HeapRegionNode hrnParamSec2 = null;
4301 if( paramIndex2idSecondary.containsKey(paramIndex2) ) {
4302 Integer idParamSec2 = paramIndex2idSecondary.get(paramIndex2);
4304 assert id2hrn.containsKey(idParamSec2);
4305 hrnParamSec2 = id2hrn.get(idParamSec2);
4306 assert hrnParamSec2 != null;
4309 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4310 common.addAll( hasPotentialAlias( hrnParamPri1, hrnParamPri2 ) );
4312 if( hrnParamSec1 != null ) {
4313 common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamPri2 ) );
4316 if( hrnParamSec2 != null ) {
4317 common.addAll( hasPotentialAlias( hrnParamSec2, hrnParamPri1 ) );
4320 if( hrnParamSec1 != null && hrnParamSec2 != null ) {
4321 common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamSec2 ) );
4328 public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex, AllocationSite as) {
4330 // get parameter's heap regions
4331 assert paramIndex2idPrimary.containsKey(paramIndex);
4332 Integer idParamPri = paramIndex2idPrimary.get(paramIndex);
4334 assert id2hrn.containsKey(idParamPri);
4335 HeapRegionNode hrnParamPri = id2hrn.get(idParamPri);
4336 assert hrnParamPri != null;
4338 HeapRegionNode hrnParamSec = null;
4339 if( paramIndex2idSecondary.containsKey(paramIndex) ) {
4340 Integer idParamSec = paramIndex2idSecondary.get(paramIndex);
4342 assert id2hrn.containsKey(idParamSec);
4343 hrnParamSec = id2hrn.get(idParamSec);
4344 assert hrnParamSec != null;
4348 assert id2hrn.containsKey( as.getSummary() );
4349 HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() );
4350 assert hrnSummary != null;
4352 Set<HeapRegionNode> common = hasPotentialAlias( hrnParamPri, hrnSummary );
4354 if( hrnParamSec != null ) {
4355 common.addAll( hasPotentialAlias( hrnParamSec, hrnSummary ) );
4358 // check for other nodes
4359 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4361 assert id2hrn.containsKey( as.getIthOldest( i ) );
4362 HeapRegionNode hrnIthOldest = id2hrn.get( as.getIthOldest( i ) );
4363 assert hrnIthOldest != null;
4365 common = hasPotentialAlias( hrnParamPri, hrnIthOldest );
4367 if( hrnParamSec != null ) {
4368 common.addAll( hasPotentialAlias( hrnParamSec, hrnIthOldest ) );
4376 public Set<HeapRegionNode> hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
4378 // get summary node 1's alpha
4379 Integer idSum1 = as1.getSummary();
4380 assert id2hrn.containsKey(idSum1);
4381 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
4382 assert hrnSum1 != null;
4384 // get summary node 2's alpha
4385 Integer idSum2 = as2.getSummary();
4386 assert id2hrn.containsKey(idSum2);
4387 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
4388 assert hrnSum2 != null;
4390 Set<HeapRegionNode> common = hasPotentialAlias( hrnSum1, hrnSum2 );
4392 // check sum2 against alloc1 nodes
4393 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
4394 Integer idI1 = as1.getIthOldest(i);
4395 assert id2hrn.containsKey(idI1);
4396 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4397 assert hrnI1 != null;
4399 common.addAll( hasPotentialAlias( hrnI1, hrnSum2 ) );
4402 // check sum1 against alloc2 nodes
4403 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
4404 Integer idI2 = as2.getIthOldest(i);
4405 assert id2hrn.containsKey(idI2);
4406 HeapRegionNode hrnI2 = id2hrn.get(idI2);
4407 assert hrnI2 != null;
4409 common.addAll( hasPotentialAlias( hrnSum1, hrnI2 ) );
4411 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4412 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
4413 Integer idI1 = as1.getIthOldest(j);
4415 // if these are the same site, don't look for the same token, no alias.
4416 // different tokens of the same site could alias together though
4417 if( idI1.equals( idI2 ) ) {
4421 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4423 common.addAll( hasPotentialAlias( hrnI1, hrnI2 ) );
4431 public Set<HeapRegionNode> findCommonReachableNodes( HeapRegionNode hrn1,
4432 HeapRegionNode hrn2 ) {
4434 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
4435 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
4437 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
4438 todoNodes1.add( hrn1 );
4440 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
4441 todoNodes2.add( hrn2 );
4443 // follow links until all reachable nodes have been found
4444 while( !todoNodes1.isEmpty() ) {
4445 HeapRegionNode hrn = todoNodes1.iterator().next();
4446 todoNodes1.remove( hrn );
4447 reachableNodes1.add(hrn);
4449 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
4450 while( edgeItr.hasNext() ) {
4451 ReferenceEdge edge = edgeItr.next();
4453 if( !reachableNodes1.contains( edge.getDst() ) ) {
4454 todoNodes1.add( edge.getDst() );
4459 while( !todoNodes2.isEmpty() ) {
4460 HeapRegionNode hrn = todoNodes2.iterator().next();
4461 todoNodes2.remove( hrn );
4462 reachableNodes2.add(hrn);
4464 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
4465 while( edgeItr.hasNext() ) {
4466 ReferenceEdge edge = edgeItr.next();
4468 if( !reachableNodes2.contains( edge.getDst() ) ) {
4469 todoNodes2.add( edge.getDst() );
4474 Set<HeapRegionNode> intersection =
4475 new HashSet<HeapRegionNode>( reachableNodes1 );
4477 intersection.retainAll( reachableNodes2 );
4479 return intersection;
4483 // for writing ownership graphs to dot files
4484 public void writeGraph(MethodContext mc,
4486 boolean writeLabels,
4487 boolean labelSelect,
4488 boolean pruneGarbage,
4489 boolean writeReferencers,
4490 boolean writeParamMappings
4491 ) throws java.io.IOException {
4503 public void writeGraph(MethodContext mc,
4504 boolean writeLabels,
4505 boolean labelSelect,
4506 boolean pruneGarbage,
4507 boolean writeReferencers,
4508 boolean writeParamMappings
4509 ) throws java.io.IOException {
4511 writeGraph(mc+"COMPLETE",
4520 public void writeGraph(MethodContext mc,
4521 boolean writeLabels,
4522 boolean labelSelect,
4523 boolean pruneGarbage,
4524 boolean writeReferencers,
4525 boolean writeParamMappings,
4526 boolean hideSubsetReachability
4527 ) throws java.io.IOException {
4529 writeGraph(mc+"COMPLETE",
4535 hideSubsetReachability
4539 public void writeGraph(MethodContext mc,
4541 boolean writeLabels,
4542 boolean labelSelect,
4543 boolean pruneGarbage,
4544 boolean writeReferencers,
4545 boolean writeParamMappings
4546 ) throws java.io.IOException {
4548 writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate),
4557 public void writeGraph(MethodContext mc,
4559 boolean writeLabels,
4560 boolean labelSelect,
4561 boolean pruneGarbage,
4562 boolean writeReferencers,
4563 boolean writeParamMappings,
4564 boolean hideSubsetReachability
4565 ) throws java.io.IOException {
4567 writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate),
4573 hideSubsetReachability
4577 public void writeGraph(String graphName,
4578 boolean writeLabels,
4579 boolean labelSelect,
4580 boolean pruneGarbage,
4581 boolean writeReferencers,
4582 boolean writeParamMappings
4583 ) throws java.io.IOException {
4584 writeGraph(graphName,
4594 public void writeGraph(String graphName,
4595 boolean writeLabels,
4596 boolean labelSelect,
4597 boolean pruneGarbage,
4598 boolean writeReferencers,
4599 boolean writeParamMappings,
4600 boolean hideSubsetReachability
4601 ) throws java.io.IOException {
4603 // remove all non-word characters from the graph name so
4604 // the filename and identifier in dot don't cause errors
4605 graphName = graphName.replaceAll("[\\W]", "");
4607 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
4608 bw.write("digraph "+graphName+" {\n");
4610 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4612 // then visit every heap region node
4613 Set s = id2hrn.entrySet();
4614 Iterator i = s.iterator();
4615 while( i.hasNext() ) {
4616 Map.Entry me = (Map.Entry)i.next();
4617 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4619 if( !pruneGarbage ||
4620 (hrn.isFlagged() && hrn.getID() > 0) ||
4621 hrn.getDescription().startsWith("param")
4624 if( !visited.contains(hrn) ) {
4625 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4631 hideSubsetReachability);
4636 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4638 if( writeParamMappings ) {
4640 Set df = paramIndex2id.entrySet();
4641 Iterator ih = df.iterator();
4642 while( ih.hasNext() ) {
4643 Map.Entry meh = (Map.Entry)ih.next();
4644 Integer pi = (Integer) meh.getKey();
4645 Integer id = (Integer) meh.getValue();
4646 bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
4651 // then visit every label node, useful for debugging
4653 s = td2ln.entrySet();
4655 while( i.hasNext() ) {
4656 Map.Entry me = (Map.Entry)i.next();
4657 LabelNode ln = (LabelNode) me.getValue();
4660 String labelStr = ln.getTempDescriptorString();
4661 if( labelStr.startsWith("___temp") ||
4662 labelStr.startsWith("___dst") ||
4663 labelStr.startsWith("___srctmp") ||
4664 labelStr.startsWith("___neverused") ||
4665 labelStr.contains(qString) ||
4666 labelStr.contains(rString) ||
4667 labelStr.contains(blobString)
4673 //bw.write(" "+ln.toString() + ";\n");
4675 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
4676 while( heapRegionsItr.hasNext() ) {
4677 ReferenceEdge edge = heapRegionsItr.next();
4678 HeapRegionNode hrn = edge.getDst();
4680 if( pruneGarbage && !visited.contains(hrn) ) {
4681 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4687 hideSubsetReachability);
4690 bw.write(" " + ln.toString() +
4691 " -> " + hrn.toString() +
4692 "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability) +
4703 protected void traverseHeapRegionNodes(int mode,
4707 HashSet<HeapRegionNode> visited,
4708 boolean writeReferencers,
4709 boolean hideSubsetReachability
4710 ) throws java.io.IOException {
4712 if( visited.contains(hrn) ) {
4718 case VISIT_HRN_WRITE_FULL:
4720 String attributes = "[";
4722 if( hrn.isSingleObject() ) {
4723 attributes += "shape=box";
4725 attributes += "shape=Msquare";
4728 if( hrn.isFlagged() ) {
4729 attributes += ",style=filled,fillcolor=lightgrey";
4732 attributes += ",label=\"ID" +
4736 if( hrn.getType() != null ) {
4737 attributes += hrn.getType().toPrettyString() + "\\n";
4740 attributes += hrn.getDescription() +
4742 hrn.getAlphaString(hideSubsetReachability) +
4745 bw.write(" " + hrn.toString() + attributes + ";\n");
4750 // useful for debugging
4753 if( writeReferencers ) {
4754 OwnershipNode onRef = null;
4755 Iterator refItr = hrn.iteratorToReferencers();
4756 while( refItr.hasNext() ) {
4757 onRef = (OwnershipNode) refItr.next();
4760 case VISIT_HRN_WRITE_FULL:
4761 bw.write(" " + hrn.toString() +
4762 " -> " + onRef.toString() +
4763 "[color=lightgray];\n");
4770 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
4771 while( childRegionsItr.hasNext() ) {
4772 ReferenceEdge edge = childRegionsItr.next();
4773 HeapRegionNode hrnChild = edge.getDst();
4776 case VISIT_HRN_WRITE_FULL:
4777 bw.write(" " + hrn.toString() +
4778 " -> " + hrnChild.toString() +
4779 "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability) +
4784 traverseHeapRegionNodes(mode,
4790 hideSubsetReachability);
4794 public int getTaintIdentifierFromHRN(HeapRegionNode hrn){
4795 HashSet<ReferenceEdge> referenceEdges=hrn.referencers;
4796 Iterator<ReferenceEdge> iter=referenceEdges.iterator();
4798 int taintIdentifier=0;
4799 while(iter.hasNext()){
4800 ReferenceEdge edge=iter.next();
4801 taintIdentifier=taintIdentifier | edge.getTaintIdentifier();
4804 return taintIdentifier;
4808 public void propagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet){
4810 HashSet<ReferenceEdge> setEdge=hrn.referencers;
4811 Iterator<ReferenceEdge> iter=setEdge.iterator();
4812 while(iter.hasNext()){
4813 ReferenceEdge edge= iter.next();
4814 edge.unionTaintIdentifier(newTaintIdentifier);
4815 if(edge.getSrc() instanceof HeapRegionNode){
4817 HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
4818 //check whether it is reflexive edge
4819 if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){
4820 visitedSet.add(refHRN);
4821 propagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);
4829 public void depropagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet){
4831 HashSet<ReferenceEdge> setEdge=hrn.referencers;
4832 Iterator<ReferenceEdge> iter=setEdge.iterator();
4833 while(iter.hasNext()){
4834 ReferenceEdge edge= iter.next();
4835 edge.minusTaintIdentifier(newTaintIdentifier);
4836 if(edge.getSrc() instanceof HeapRegionNode){
4838 HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
4839 //check whether it is reflexive edge
4840 if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){
4841 visitedSet.add(refHRN);
4842 depropagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);