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;
14 protected static int allocationDepth = -1;
15 protected static TypeUtil typeUtil = null;
16 protected static boolean debugCallMap = false;
17 protected static int debugCallMapCount = 0;
18 protected static String debugCallee = null;
19 protected static String debugCaller = null;
21 // there was already one other very similar reason
22 // for traversing heap nodes that is no longer needed
23 // instead of writing a new heap region visitor, use
24 // the existing method with a new mode to describe what
25 // actions to take during the traversal
26 protected static final int VISIT_HRN_WRITE_FULL = 0;
28 protected static final String qString = new String( "Q_spec_" );
29 protected static final String rString = new String( "R_spec_" );
30 protected static final String blobString = new String( "_AliasBlob___" );
32 protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
33 protected static final TempDescriptor tdAliasBlob = new TempDescriptor( blobString );
35 protected static final TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
36 protected static final ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical();
37 protected static final ReachabilitySet rsWttsEmpty = new ReachabilitySet( ttsEmpty ).makeCanonical();
39 // add a bogus entry with the identity rule for easy rewrite
40 // of new callee nodes and edges, doesn't belong to any parameter
41 protected static final int bogusParamIndexInt = -2;
42 protected static final Integer bogusID = new Integer( bogusParamIndexInt );
43 protected static final Integer bogusIndex = new Integer( bogusParamIndexInt );
44 protected static final TokenTuple bogusToken = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONE ).makeCanonical();
45 protected static final TokenTuple bogusTokenPlus = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONEORMORE ).makeCanonical();
46 protected static final TokenTuple bogusTokenStar = new TokenTuple( bogusID, true, TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
47 protected static final ReachabilitySet rsIdentity =
48 new ReachabilitySet( new TokenTupleSet( bogusToken ).makeCanonical() ).makeCanonical();
51 public Hashtable<Integer, HeapRegionNode> id2hrn;
52 public Hashtable<TempDescriptor, LabelNode > td2ln;
54 public Hashtable<Integer, Set<Integer> > idPrimary2paramIndexSet;
55 public Hashtable<Integer, Integer > paramIndex2idPrimary;
57 public Hashtable<Integer, Set<Integer> > idSecondary2paramIndexSet;
58 public Hashtable<Integer, Integer > paramIndex2idSecondary;
60 public Hashtable<Integer, TempDescriptor> paramIndex2tdQ;
61 public Hashtable<Integer, TempDescriptor> paramIndex2tdR;
64 public HashSet<AllocationSite> allocationSites;
67 public Hashtable<TokenTuple, Integer> paramTokenPrimary2paramIndex;
68 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenPrimary;
70 public Hashtable<TokenTuple, Integer> paramTokenSecondary2paramIndex;
71 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondary;
72 public Hashtable<TokenTuple, Integer> paramTokenSecondaryPlus2paramIndex;
73 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondaryPlus;
74 public Hashtable<TokenTuple, Integer> paramTokenSecondaryStar2paramIndex;
75 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondaryStar;
81 public OwnershipGraph() {
83 id2hrn = new Hashtable<Integer, HeapRegionNode>();
84 td2ln = new Hashtable<TempDescriptor, LabelNode >();
85 idPrimary2paramIndexSet = new Hashtable<Integer, Set<Integer> >();
86 paramIndex2idPrimary = new Hashtable<Integer, Integer >();
87 idSecondary2paramIndexSet = new Hashtable<Integer, Set<Integer> >();
88 paramIndex2idSecondary = new Hashtable<Integer, Integer >();
89 paramIndex2tdQ = new Hashtable<Integer, TempDescriptor>();
90 paramIndex2tdR = new Hashtable<Integer, TempDescriptor>();
92 paramTokenPrimary2paramIndex = new Hashtable<TokenTuple, Integer >();
93 paramIndex2paramTokenPrimary = new Hashtable<Integer, TokenTuple >();
95 paramTokenSecondary2paramIndex = new Hashtable<TokenTuple, Integer >();
96 paramIndex2paramTokenSecondary = new Hashtable<Integer, TokenTuple >();
97 paramTokenSecondaryPlus2paramIndex = new Hashtable<TokenTuple, Integer >();
98 paramIndex2paramTokenSecondaryPlus = new Hashtable<Integer, TokenTuple >();
99 paramTokenSecondaryStar2paramIndex = new Hashtable<TokenTuple, Integer >();
100 paramIndex2paramTokenSecondaryStar = new Hashtable<Integer, TokenTuple >();
102 allocationSites = new HashSet <AllocationSite>();
106 // label nodes are much easier to deal with than
107 // heap region nodes. Whenever there is a request
108 // for the label node that is associated with a
109 // temp descriptor we can either find it or make a
110 // new one and return it. This is because temp
111 // descriptors are globally unique and every label
112 // node is mapped to exactly one temp descriptor.
113 protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
116 if( !td2ln.containsKey(td) ) {
117 td2ln.put(td, new LabelNode(td) );
120 return td2ln.get(td);
124 // the reason for this method is to have the option
125 // creating new heap regions with specific IDs, or
126 // duplicating heap regions with specific IDs (especially
127 // in the merge() operation) or to create new heap
128 // regions with a new unique ID.
129 protected HeapRegionNode
130 createNewHeapRegionNode(Integer id,
131 boolean isSingleObject,
132 boolean isNewSummary,
136 AllocationSite allocSite,
137 ReachabilitySet alpha,
138 String description) {
140 boolean markForAnalysis = isFlagged || isParameter;
142 TypeDescriptor typeToUse = null;
143 if( allocSite != null ) {
144 typeToUse = allocSite.getType();
149 if( allocSite != null && allocSite.getDisjointId() != null ) {
150 markForAnalysis = true;
154 id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
157 if( alpha == null ) {
158 if( markForAnalysis ) {
159 alpha = new ReachabilitySet(
166 alpha = new ReachabilitySet(
167 new TokenTupleSet().makeCanonical()
172 HeapRegionNode hrn = new HeapRegionNode(id,
187 ////////////////////////////////////////////////
189 // Low-level referencee and referencer methods
191 // These methods provide the lowest level for
192 // creating references between ownership nodes
193 // and handling the details of maintaining both
194 // list of referencers and referencees.
196 ////////////////////////////////////////////////
197 protected void addReferenceEdge(OwnershipNode referencer,
198 HeapRegionNode referencee,
199 ReferenceEdge edge) {
200 assert referencer != null;
201 assert referencee != null;
203 assert edge.getSrc() == referencer;
204 assert edge.getDst() == referencee;
206 referencer.addReferencee(edge);
207 referencee.addReferencer(edge);
210 protected void removeReferenceEdge(OwnershipNode referencer,
211 HeapRegionNode referencee,
214 assert referencer != null;
215 assert referencee != null;
217 ReferenceEdge edge = referencer.getReferenceTo(referencee,
221 assert edge == referencee.getReferenceFrom(referencer,
225 // int oldTaint=edge.getTaintIdentifier();
226 // if(referencer instanceof HeapRegionNode){
227 // depropagateTaintIdentifier((HeapRegionNode)referencer,oldTaint,new HashSet<HeapRegionNode>());
230 referencer.removeReferencee(edge);
231 referencee.removeReferencer(edge);
234 protected void clearReferenceEdgesFrom(OwnershipNode referencer,
238 assert referencer != null;
240 // get a copy of the set to iterate over, otherwise
241 // we will be trying to take apart the set as we
242 // are iterating over it, which won't work
243 Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
244 while( i.hasNext() ) {
245 ReferenceEdge edge = i.next();
248 (edge.typeEquals( type ) && edge.fieldEquals( field ))
251 HeapRegionNode referencee = edge.getDst();
253 removeReferenceEdge(referencer,
261 protected void clearReferenceEdgesTo(HeapRegionNode referencee,
265 assert referencee != null;
267 // get a copy of the set to iterate over, otherwise
268 // we will be trying to take apart the set as we
269 // are iterating over it, which won't work
270 Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
271 while( i.hasNext() ) {
272 ReferenceEdge edge = i.next();
275 (edge.typeEquals( type ) && edge.fieldEquals( field ))
278 OwnershipNode referencer = edge.getSrc();
280 removeReferenceEdge(referencer,
289 ////////////////////////////////////////////////////
291 // Assignment Operation Methods
293 // These methods are high-level operations for
294 // modeling program assignment statements using
295 // the low-level reference create/remove methods
298 // The destination in an assignment statement is
299 // going to have new references. The method of
300 // determining the references depends on the type
301 // of the FlatNode assignment and the predicates
302 // of the nodes and edges involved.
304 ////////////////////////////////////////////////////
306 public void nullifyDeadVars( Set<TempDescriptor> liveIn ) {
308 // make a set of the temps that are out of scope, don't
309 // consider them when nullifying dead in-scope variables
310 Set<TempDescriptor> outOfScope = new HashSet<TempDescriptor>();
311 outOfScope.add( tdReturn );
312 outOfScope.add( tdAliasBlob );
313 outOfScope.addAll( paramIndex2tdQ.values() );
314 outOfScope.addAll( paramIndex2tdR.values() );
316 Iterator varItr = td2ln.entrySet().iterator();
317 while( varItr.hasNext() ) {
318 Map.Entry me = (Map.Entry) varItr.next();
319 TempDescriptor td = (TempDescriptor) me.getKey();
320 LabelNode ln = (LabelNode) me.getValue();
322 // if this variable is not out-of-scope or live
323 // in graph, nullify its references to anything
324 if( !outOfScope.contains( td ) &&
325 !liveIn.contains( td )
327 clearReferenceEdgesFrom( ln, null, null, true );
333 public void assignTempXEqualToTempY(TempDescriptor x,
336 LabelNode lnX = getLabelNodeFromTemp(x);
337 LabelNode lnY = getLabelNodeFromTemp(y);
339 clearReferenceEdgesFrom(lnX, null, null, true);
341 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
342 while( itrYhrn.hasNext() ) {
343 ReferenceEdge edgeY = itrYhrn.next();
344 HeapRegionNode referencee = edgeY.getDst();
345 ReferenceEdge edgeNew = edgeY.copy();
348 addReferenceEdge(lnX, referencee, edgeNew);
353 public void assignTypedTempXEqualToTempY(TempDescriptor x,
355 TypeDescriptor type) {
357 LabelNode lnX = getLabelNodeFromTemp(x);
358 LabelNode lnY = getLabelNodeFromTemp(y);
360 clearReferenceEdgesFrom(lnX, null, null, true);
362 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
363 while( itrYhrn.hasNext() ) {
364 ReferenceEdge edgeY = itrYhrn.next();
365 HeapRegionNode referencee = edgeY.getDst();
366 ReferenceEdge edgeNew = edgeY.copy();
367 edgeNew.setSrc( lnX );
368 edgeNew.setType( type );
369 edgeNew.setField( null );
371 addReferenceEdge(lnX, referencee, edgeNew);
376 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
379 LabelNode lnX = getLabelNodeFromTemp(x);
380 LabelNode lnY = getLabelNodeFromTemp(y);
382 clearReferenceEdgesFrom(lnX, null, null, true);
384 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
385 while( itrYhrn.hasNext() ) {
386 ReferenceEdge edgeY = itrYhrn.next();
387 HeapRegionNode hrnY = edgeY.getDst();
388 ReachabilitySet betaY = edgeY.getBeta();
390 Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
391 while( itrHrnFhrn.hasNext() ) {
392 ReferenceEdge edgeHrn = itrHrnFhrn.next();
393 HeapRegionNode hrnHrn = edgeHrn.getDst();
394 ReachabilitySet betaHrn = edgeHrn.getBeta();
396 if( edgeHrn.getType() == null ||
397 (edgeHrn.getType() .equals( f.getType() ) &&
398 edgeHrn.getField().equals( f.getSymbol() ) )
401 ReferenceEdge edgeNew = new ReferenceEdge(lnX,
406 betaY.intersection(betaHrn) );
408 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnHrn);
409 edgeNew.setTaintIdentifier(newTaintIdentifier);
411 addReferenceEdge(lnX, hrnHrn, edgeNew);
418 public void assignTempXFieldFEqualToTempY(TempDescriptor x,
421 LabelNode lnX = getLabelNodeFromTemp(x);
422 LabelNode lnY = getLabelNodeFromTemp(y);
424 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
425 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
427 // first look for possible strong updates and remove those edges
428 boolean strongUpdate = false;
430 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
431 while( itrXhrn.hasNext() ) {
432 ReferenceEdge edgeX = itrXhrn.next();
433 HeapRegionNode hrnX = edgeX.getDst();
435 // we can do a strong update here if one of two cases holds
437 f != OwnershipAnalysis.getArrayField( f.getType() ) &&
438 ( (hrnX.getNumReferencers() == 1) || // case 1
439 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
442 if( !DISABLE_STRONG_UPDATES ) {
444 clearReferenceEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
449 // then do all token propagation
450 itrXhrn = lnX.iteratorToReferencees();
451 while( itrXhrn.hasNext() ) {
452 ReferenceEdge edgeX = itrXhrn.next();
453 HeapRegionNode hrnX = edgeX.getDst();
454 ReachabilitySet betaX = edgeX.getBeta();
456 ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
458 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
459 while( itrYhrn.hasNext() ) {
460 ReferenceEdge edgeY = itrYhrn.next();
461 HeapRegionNode hrnY = edgeY.getDst();
462 ReachabilitySet O = edgeY.getBeta();
465 // propagate tokens over nodes starting from hrnSrc, and it will
466 // take care of propagating back up edges from any touched nodes
467 ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
468 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
471 // then propagate back just up the edges from hrn
472 ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
473 HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
475 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
476 new Hashtable<ReferenceEdge, ChangeTupleSet>();
478 Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
479 while( referItr.hasNext() ) {
480 ReferenceEdge edgeUpstream = referItr.next();
481 todoEdges.add(edgeUpstream);
482 edgePlannedChanges.put(edgeUpstream, Cx);
485 propagateTokensOverEdges(todoEdges,
492 // apply the updates to reachability
493 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
494 while( nodeItr.hasNext() ) {
495 nodeItr.next().applyAlphaNew();
498 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
499 while( edgeItr.hasNext() ) {
500 edgeItr.next().applyBetaNew();
504 // then go back through and add the new edges
505 itrXhrn = lnX.iteratorToReferencees();
506 while( itrXhrn.hasNext() ) {
507 ReferenceEdge edgeX = itrXhrn.next();
508 HeapRegionNode hrnX = edgeX.getDst();
510 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
511 while( itrYhrn.hasNext() ) {
512 ReferenceEdge edgeY = itrYhrn.next();
513 HeapRegionNode hrnY = edgeY.getDst();
515 // prepare the new reference edge hrnX.f -> hrnY
516 ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
521 edgeY.getBeta().pruneBy( hrnX.getAlpha() )
524 // look to see if an edge with same field exists
525 // and merge with it, otherwise just add the edge
526 ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY,
530 if( edgeExisting != null ) {
531 edgeExisting.setBeta(
532 edgeExisting.getBeta().union( edgeNew.getBeta() )
534 if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){
535 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY);
536 edgeExisting.unionTaintIdentifier(newTaintIdentifier);
538 // a new edge here cannot be reflexive, so existing will
539 // always be also not reflexive anymore
540 edgeExisting.setIsInitialParam( false );
543 if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){
544 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY);
545 edgeNew.setTaintIdentifier(newTaintIdentifier);
547 //currently, taint isn't propagated through the chain of refrences
548 //propagateTaintIdentifier(hrnX,newTaintIdentifier,new HashSet<HeapRegionNode>());
549 addReferenceEdge( hrnX, hrnY, edgeNew );
554 // if there was a strong update, make sure to improve
555 // reachability with a global sweep
557 if( !DISABLE_GLOBAL_SWEEP ) {
564 // the parameter model is to use a single-object heap region
565 // for the primary parameter, and a multiple-object heap
566 // region for the secondary objects reachable through the
567 // primary object, if necessary
568 public void assignTempEqualToParamAlloc( TempDescriptor td,
570 Integer paramIndex ) {
573 TypeDescriptor typeParam = td.getType();
574 assert typeParam != null;
576 // either the parameter is an array or a class to be in this method
577 assert typeParam.isArray() || typeParam.isClass();
579 // discover some info from the param type and use it below
580 // to get parameter model as precise as we can
581 boolean createSecondaryRegion = false;
582 Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
583 Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
585 // there might be an element reference for array types
586 if( typeParam.isArray() ) {
587 // only bother with this if the dereferenced type can
588 // affect reachability
589 TypeDescriptor typeDeref = typeParam.dereference();
590 if( !typeDeref.isImmutable() || typeDeref.isArray() ) {
591 primary2secondaryFields.add(
592 OwnershipAnalysis.getArrayField( typeDeref )
594 createSecondaryRegion = true;
596 // also handle a special case where an array of objects
597 // can point back to the array, which is an object!
598 if( typeParam.toPrettyString().equals( "Object[]" ) &&
599 typeDeref.toPrettyString().equals( "Object" ) ) {
601 primary2primaryFields.add(
602 OwnershipAnalysis.getArrayField( typeDeref )
608 // there might be member references for class types
609 if( typeParam.isClass() ) {
610 ClassDescriptor cd = typeParam.getClassDesc();
611 while( cd != null ) {
613 Iterator fieldItr = cd.getFields();
614 while( fieldItr.hasNext() ) {
616 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
617 TypeDescriptor typeField = fd.getType();
618 assert typeField != null;
620 if( !typeField.isImmutable() || typeField.isArray() ) {
621 primary2secondaryFields.add( fd );
622 createSecondaryRegion = true;
625 if( typeUtil.isSuperorType( typeField, typeParam ) ) {
626 primary2primaryFields.add( fd );
630 cd = cd.getSuperDesc();
635 // now build everything we need
636 LabelNode lnParam = getLabelNodeFromTemp( td );
637 HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
638 true, // single object?
641 true, // is a parameter?
643 null, // allocation site
644 null, // reachability set
645 "param"+paramIndex+" obj" );
647 // this is a non-program-accessible label that picks up beta
648 // info to be used for fixing a caller of this method
649 TempDescriptor tdParamQ = new TempDescriptor( td+qString );
650 paramIndex2tdQ.put( paramIndex, tdParamQ );
651 LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
653 // keep track of heap regions that were created for
654 // parameter labels, the index of the parameter they
655 // are for is important when resolving method calls
656 Integer newPrimaryID = hrnPrimary.getID();
657 assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
658 Set<Integer> s = new HashSet<Integer>();
660 idPrimary2paramIndexSet.put( newPrimaryID, s );
661 paramIndex2idPrimary.put( paramIndex, newPrimaryID );
664 TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
665 false, // multi-object
666 TokenTuple.ARITY_ONE ).makeCanonical();
668 HeapRegionNode hrnSecondary = null;
669 Integer newSecondaryID = null;
670 TokenTuple ttSecondary = null;
671 TempDescriptor tdParamR = null;
672 LabelNode lnParamR = null;
674 if( createSecondaryRegion ) {
675 tdParamR = new TempDescriptor( td+rString );
676 paramIndex2tdR.put( paramIndex, tdParamR );
677 lnParamR = getLabelNodeFromTemp( tdParamR );
679 hrnSecondary = createNewHeapRegionNode( null, // id or null to generate a new one
680 false, // single object?
683 true, // is a parameter?
685 null, // allocation site
686 null, // reachability set
687 "param"+paramIndex+" reachable" );
689 newSecondaryID = hrnSecondary.getID();
690 assert !idSecondary2paramIndexSet.containsKey( newSecondaryID );
691 Set<Integer> s2 = new HashSet<Integer>();
692 s2.add( paramIndex );
693 idSecondary2paramIndexSet.put( newSecondaryID, s2 );
694 paramIndex2idSecondary.put( paramIndex, newSecondaryID );
697 ttSecondary = new TokenTuple( newSecondaryID,
698 true, // multi-object
699 TokenTuple.ARITY_ONE ).makeCanonical();
702 // use a beta that has everything and put it all over the
703 // parameter model, then use a global sweep later to fix
704 // it up, since parameters can have different shapes
705 TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
706 ReachabilitySet betaSoup;
707 if( createSecondaryRegion ) {
708 TokenTupleSet tts1 = new TokenTupleSet( ttSecondary ).makeCanonical();
709 TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttSecondary );
710 betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 );
712 betaSoup = ReachabilitySet.factory( tts0 );
715 ReferenceEdge edgeFromLabel =
716 new ReferenceEdge( lnParam, // src
720 false, // special param initial (not needed on label->node)
721 betaSoup ); // reachability
722 edgeFromLabel.tainedBy(paramIndex);
723 addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
725 ReferenceEdge edgeFromLabelQ =
726 new ReferenceEdge( lnParamQ, // src
730 false, // special param initial (not needed on label->node)
731 betaSoup ); // reachability
732 edgeFromLabelQ.tainedBy(paramIndex);
733 addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
735 ReferenceEdge edgeSecondaryReflexive;
736 if( createSecondaryRegion ) {
737 edgeSecondaryReflexive =
738 new ReferenceEdge( hrnSecondary, // src
740 null, // match all types
741 null, // match all fields
742 true, // special param initial
743 betaSoup ); // reachability
744 addReferenceEdge( hrnSecondary, hrnSecondary, edgeSecondaryReflexive );
746 ReferenceEdge edgeSecondary2Primary =
747 new ReferenceEdge( hrnSecondary, // src
749 null, // match all types
750 null, // match all fields
751 true, // special param initial
752 betaSoup ); // reachability
753 addReferenceEdge( hrnSecondary, hrnPrimary, edgeSecondary2Primary );
755 ReferenceEdge edgeFromLabelR =
756 new ReferenceEdge( lnParamR, // src
760 false, // special param initial (not needed on label->node)
761 betaSoup ); // reachability
762 edgeFromLabelR.tainedBy(paramIndex);
763 addReferenceEdge( lnParamR, hrnSecondary, edgeFromLabelR );
766 Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
767 while( fieldItr.hasNext() ) {
768 FieldDescriptor fd = fieldItr.next();
770 ReferenceEdge edgePrimaryReflexive =
771 new ReferenceEdge( hrnPrimary, // src
773 fd.getType(), // type
774 fd.getSymbol(), // field
775 true, // special param initial
776 betaSoup ); // reachability
777 addReferenceEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive );
780 fieldItr = primary2secondaryFields.iterator();
781 while( fieldItr.hasNext() ) {
782 FieldDescriptor fd = fieldItr.next();
784 ReferenceEdge edgePrimary2Secondary =
785 new ReferenceEdge( hrnPrimary, // src
787 fd.getType(), // type
788 fd.getSymbol(), // field
789 true, // special param initial
790 betaSoup ); // reachability
791 addReferenceEdge( hrnPrimary, hrnSecondary, edgePrimary2Secondary );
796 public void makeAliasedParamHeapRegionNode() {
798 LabelNode lnBlob = getLabelNodeFromTemp( tdAliasBlob );
799 HeapRegionNode hrn = createNewHeapRegionNode( null, // id or null to generate a new one
800 false, // single object?
803 true, // is a parameter?
805 null, // allocation site
806 null, // reachability set
810 ReachabilitySet beta = new ReachabilitySet( new TokenTuple( hrn.getID(),
812 TokenTuple.ARITY_ONE).makeCanonical()
815 ReferenceEdge edgeFromLabel =
816 new ReferenceEdge( lnBlob, hrn, null, null, false, beta );
818 ReferenceEdge edgeReflexive =
819 new ReferenceEdge( hrn, hrn, null, null, true, beta );
821 addReferenceEdge( lnBlob, hrn, edgeFromLabel );
822 addReferenceEdge( hrn, hrn, edgeReflexive );
826 public void assignTempEqualToAliasedParam( TempDescriptor tdParam,
827 Integer paramIndex ) {
828 assert tdParam != null;
830 TypeDescriptor typeParam = tdParam.getType();
831 assert typeParam != null;
833 LabelNode lnParam = getLabelNodeFromTemp( tdParam );
834 LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob );
836 // this is a non-program-accessible label that picks up beta
837 // info to be used for fixing a caller of this method
838 TempDescriptor tdParamQ = new TempDescriptor( tdParam+qString );
839 TempDescriptor tdParamR = new TempDescriptor( tdParam+rString );
841 paramIndex2tdQ.put( paramIndex, tdParamQ );
842 paramIndex2tdR.put( paramIndex, tdParamR );
844 LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
845 LabelNode lnParamR = getLabelNodeFromTemp( tdParamR );
847 // the lnAliased should always only reference one node, and that
848 // heap region node is the aliased param blob
849 assert lnAliased.getNumReferencees() == 1;
850 HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
851 Integer idAliased = hrnAliasBlob.getID();
854 TokenTuple ttAliased = new TokenTuple( idAliased,
855 true, // multi-object
856 TokenTuple.ARITY_ONE ).makeCanonical();
859 HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
860 true, // single object?
863 true, // is a parameter?
865 null, // allocation site
866 null, // reachability set
867 "param"+paramIndex+" obj" );
869 Integer newPrimaryID = hrnPrimary.getID();
870 assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
871 Set<Integer> s1 = new HashSet<Integer>();
872 s1.add( paramIndex );
873 idPrimary2paramIndexSet.put( newPrimaryID, s1 );
874 paramIndex2idPrimary.put( paramIndex, newPrimaryID );
876 Set<Integer> s2 = idSecondary2paramIndexSet.get( idAliased );
878 s2 = new HashSet<Integer>();
880 s2.add( paramIndex );
881 idSecondary2paramIndexSet.put( idAliased, s2 );
882 paramIndex2idSecondary.put( paramIndex, idAliased );
886 TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
887 false, // multi-object
888 TokenTuple.ARITY_ONE ).makeCanonical();
891 TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
892 TokenTupleSet tts1 = new TokenTupleSet( ttAliased ).makeCanonical();
893 TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttAliased );
894 ReachabilitySet betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 );
897 ReferenceEdge edgeFromLabel =
898 new ReferenceEdge( lnParam, // src
902 false, // special param initial (not needed on label->node)
903 betaSoup ); // reachability
904 edgeFromLabel.tainedBy(paramIndex);
905 addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
907 ReferenceEdge edgeFromLabelQ =
908 new ReferenceEdge( lnParamQ, // src
912 false, // special param initial (not needed on label->node)
913 betaSoup ); // reachability
914 edgeFromLabelQ.tainedBy(paramIndex);
915 addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
917 ReferenceEdge edgeAliased2Primary =
918 new ReferenceEdge( hrnAliasBlob, // src
920 null, // match all types
921 null, // match all fields
922 true, // special param initial
923 betaSoup ); // reachability
924 addReferenceEdge( hrnAliasBlob, hrnPrimary, edgeAliased2Primary );
926 ReferenceEdge edgeFromLabelR =
927 new ReferenceEdge( lnParamR, // src
931 false, // special param initial (not needed on label->node)
932 betaSoup ); // reachability
933 edgeFromLabelR.tainedBy(paramIndex);
934 addReferenceEdge( lnParamR, hrnAliasBlob, edgeFromLabelR );
938 public void addParam2ParamAliasEdges( FlatMethod fm,
939 Set<Integer> aliasedParamIndices ) {
941 LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob );
943 // the lnAliased should always only reference one node, and that
944 // heap region node is the aliased param blob
945 assert lnAliased.getNumReferencees() == 1;
946 HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
947 Integer idAliased = hrnAliasBlob.getID();
950 TokenTuple ttAliased = new TokenTuple( idAliased,
951 true, // multi-object
952 TokenTuple.ARITY_ONE ).makeCanonical();
955 Iterator<Integer> apItrI = aliasedParamIndices.iterator();
956 while( apItrI.hasNext() ) {
957 Integer i = apItrI.next();
958 TempDescriptor tdParamI = fm.getParameter( i );
959 TypeDescriptor typeI = tdParamI.getType();
960 LabelNode lnParamI = getLabelNodeFromTemp( tdParamI );
962 Integer idPrimaryI = paramIndex2idPrimary.get( i );
963 assert idPrimaryI != null;
964 HeapRegionNode primaryI = id2hrn.get( idPrimaryI );
965 assert primaryI != null;
967 TokenTuple ttPrimaryI = new TokenTuple( idPrimaryI,
968 false, // multi-object
969 TokenTuple.ARITY_ONE ).makeCanonical();
971 TokenTupleSet ttsI = new TokenTupleSet( ttPrimaryI ).makeCanonical();
972 TokenTupleSet ttsA = new TokenTupleSet( ttAliased ).makeCanonical();
973 TokenTupleSet ttsIA = new TokenTupleSet( ttPrimaryI ).makeCanonical().union( ttAliased );
974 ReachabilitySet betaSoup = ReachabilitySet.factory( ttsI ).union( ttsA ).union( ttsIA );
977 // calculate whether fields of this aliased parameter are able to
978 // reference its own primary object, the blob, or other parameter's
980 Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
981 Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
983 // there might be an element reference for array types
984 if( typeI.isArray() ) {
985 // only bother with this if the dereferenced type can
986 // affect reachability
987 TypeDescriptor typeDeref = typeI.dereference();
991 /////////////////////////////////////////////////////////////
992 // NOTE! For the KMeans benchmark a parameter of type float
993 // array, which has an immutable dereferenced type, is causing
994 // this assertion to fail. I'm commenting it out for now which
995 // is safe, because it allows aliasing where no aliasing can occur,
996 // so it can only get a worse-but-not-wrong answer. FIX!
997 /////////////////////////////////////////////////////////////
998 // for this parameter to be aliased the following must be true
999 //assert !typeDeref.isImmutable() || typeDeref.isArray();
1003 primary2secondaryFields.add(
1004 OwnershipAnalysis.getArrayField( typeDeref )
1007 // also handle a special case where an array of objects
1008 // can point back to the array, which is an object!
1009 if( typeI .toPrettyString().equals( "Object[]" ) &&
1010 typeDeref.toPrettyString().equals( "Object" ) ) {
1011 primary2primaryFields.add(
1012 OwnershipAnalysis.getArrayField( typeDeref )
1017 // there might be member references for class types
1018 if( typeI.isClass() ) {
1019 ClassDescriptor cd = typeI.getClassDesc();
1020 while( cd != null ) {
1022 Iterator fieldItr = cd.getFields();
1023 while( fieldItr.hasNext() ) {
1025 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
1026 TypeDescriptor typeField = fd.getType();
1027 assert typeField != null;
1029 if( !typeField.isImmutable() || typeField.isArray() ) {
1030 primary2secondaryFields.add( fd );
1033 if( typeUtil.isSuperorType( typeField, typeI ) ) {
1034 primary2primaryFields.add( fd );
1038 cd = cd.getSuperDesc();
1042 Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
1043 while( fieldItr.hasNext() ) {
1044 FieldDescriptor fd = fieldItr.next();
1046 ReferenceEdge edgePrimaryReflexive =
1047 new ReferenceEdge( primaryI, // src
1049 fd.getType(), // type
1050 fd.getSymbol(), // field
1051 true, // special param initial
1052 betaSoup ); // reachability
1053 addReferenceEdge( primaryI, primaryI, edgePrimaryReflexive );
1056 fieldItr = primary2secondaryFields.iterator();
1057 while( fieldItr.hasNext() ) {
1058 FieldDescriptor fd = fieldItr.next();
1059 TypeDescriptor typeField = fd.getType();
1060 assert typeField != null;
1062 ReferenceEdge edgePrimary2Secondary =
1063 new ReferenceEdge( primaryI, // src
1064 hrnAliasBlob, // dst
1065 fd.getType(), // type
1066 fd.getSymbol(), // field
1067 true, // special param initial
1068 betaSoup ); // reachability
1069 addReferenceEdge( primaryI, hrnAliasBlob, edgePrimary2Secondary );
1071 // ask whether these fields might match any of the other aliased
1072 // parameters and make those edges too
1073 Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
1074 while( apItrJ.hasNext() ) {
1075 Integer j = apItrJ.next();
1076 TempDescriptor tdParamJ = fm.getParameter( j );
1077 TypeDescriptor typeJ = tdParamJ.getType();
1079 if( !i.equals( j ) && typeUtil.isSuperorType( typeField, typeJ ) ) {
1081 Integer idPrimaryJ = paramIndex2idPrimary.get( j );
1082 assert idPrimaryJ != null;
1083 HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
1084 assert primaryJ != null;
1086 TokenTuple ttPrimaryJ = new TokenTuple( idPrimaryJ,
1087 false, // multi-object
1088 TokenTuple.ARITY_ONE ).makeCanonical();
1090 TokenTupleSet ttsJ = new TokenTupleSet( ttPrimaryJ ).makeCanonical();
1091 TokenTupleSet ttsIJ = ttsI.union( ttsJ );
1092 TokenTupleSet ttsAJ = ttsA.union( ttsJ );
1093 TokenTupleSet ttsIAJ = ttsIA.union( ttsJ );
1094 ReachabilitySet betaSoupWJ = ReachabilitySet.factory( ttsJ ).union( ttsIJ ).union( ttsAJ ).union( ttsIAJ );
1096 ReferenceEdge edgePrimaryI2PrimaryJ =
1097 new ReferenceEdge( primaryI, // src
1099 fd.getType(), // type
1100 fd.getSymbol(), // field
1101 true, // special param initial
1102 betaSoupWJ ); // reachability
1103 addReferenceEdge( primaryI, primaryJ, edgePrimaryI2PrimaryJ );
1109 // look at whether aliased parameters i and j can
1110 // possibly be the same primary object, add edges
1111 Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
1112 while( apItrJ.hasNext() ) {
1113 Integer j = apItrJ.next();
1114 TempDescriptor tdParamJ = fm.getParameter( j );
1115 TypeDescriptor typeJ = tdParamJ.getType();
1116 LabelNode lnParamJ = getLabelNodeFromTemp( tdParamJ );
1118 if( !i.equals( j ) && typeUtil.isSuperorType( typeI, typeJ ) ) {
1120 Integer idPrimaryJ = paramIndex2idPrimary.get( j );
1121 assert idPrimaryJ != null;
1122 HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
1123 assert primaryJ != null;
1125 ReferenceEdge lnJ2PrimaryJ = lnParamJ.getReferenceTo( primaryJ,
1128 assert lnJ2PrimaryJ != null;
1130 ReferenceEdge lnI2PrimaryJ = lnJ2PrimaryJ.copy();
1131 lnI2PrimaryJ.setSrc( lnParamI );
1132 lnI2PrimaryJ.setType( tdParamI.getType() );
1133 lnI2PrimaryJ.tainedBy(new Integer(j));
1134 addReferenceEdge( lnParamI, primaryJ, lnI2PrimaryJ );
1140 public void prepareParamTokenMaps( FlatMethod fm ) {
1142 // always add the bogus mappings that are used to
1143 // rewrite "with respect to no parameter"
1144 paramTokenPrimary2paramIndex.put( bogusToken, bogusIndex );
1145 paramIndex2paramTokenPrimary.put( bogusIndex, bogusToken );
1147 paramTokenSecondary2paramIndex.put( bogusToken, bogusIndex );
1148 paramIndex2paramTokenSecondary.put( bogusIndex, bogusToken );
1149 paramTokenSecondaryPlus2paramIndex.put( bogusTokenPlus, bogusIndex );
1150 paramIndex2paramTokenSecondaryPlus.put( bogusIndex, bogusTokenPlus );
1151 paramTokenSecondaryStar2paramIndex.put( bogusTokenStar, bogusIndex );
1152 paramIndex2paramTokenSecondaryStar.put( bogusIndex, bogusTokenStar );
1154 for( int i = 0; i < fm.numParameters(); ++i ) {
1155 Integer paramIndex = new Integer( i );
1157 // immutable objects have no primary regions
1158 if( paramIndex2idPrimary.containsKey( paramIndex ) ) {
1159 Integer idPrimary = paramIndex2idPrimary.get( paramIndex );
1161 assert id2hrn.containsKey( idPrimary );
1162 HeapRegionNode hrnPrimary = id2hrn.get( idPrimary );
1164 TokenTuple p_i = new TokenTuple( hrnPrimary.getID(),
1165 false, // multiple-object?
1166 TokenTuple.ARITY_ONE ).makeCanonical();
1167 paramTokenPrimary2paramIndex.put( p_i, paramIndex );
1168 paramIndex2paramTokenPrimary.put( paramIndex, p_i );
1171 // any parameter object, by type, may have no secondary region
1172 if( paramIndex2idSecondary.containsKey( paramIndex ) ) {
1173 Integer idSecondary = paramIndex2idSecondary.get( paramIndex );
1175 assert id2hrn.containsKey( idSecondary );
1176 HeapRegionNode hrnSecondary = id2hrn.get( idSecondary );
1178 TokenTuple s_i = new TokenTuple( hrnSecondary.getID(),
1179 true, // multiple-object?
1180 TokenTuple.ARITY_ONE ).makeCanonical();
1181 paramTokenSecondary2paramIndex.put( s_i, paramIndex );
1182 paramIndex2paramTokenSecondary.put( paramIndex, s_i );
1184 TokenTuple s_i_plus = new TokenTuple( hrnSecondary.getID(),
1185 true, // multiple-object?
1186 TokenTuple.ARITY_ONEORMORE ).makeCanonical();
1187 paramTokenSecondaryPlus2paramIndex.put( s_i_plus, paramIndex );
1188 paramIndex2paramTokenSecondaryPlus.put( paramIndex, s_i_plus );
1190 TokenTuple s_i_star = new TokenTuple( hrnSecondary.getID(),
1191 true, // multiple-object?
1192 TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
1193 paramTokenSecondaryStar2paramIndex.put( s_i_star, paramIndex );
1194 paramIndex2paramTokenSecondaryStar.put( paramIndex, s_i_star );
1201 public void assignReturnEqualToTemp(TempDescriptor x) {
1203 LabelNode lnR = getLabelNodeFromTemp(tdReturn);
1204 LabelNode lnX = getLabelNodeFromTemp(x);
1206 clearReferenceEdgesFrom(lnR, null, null, true);
1208 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
1209 while( itrXhrn.hasNext() ) {
1210 ReferenceEdge edgeX = itrXhrn.next();
1211 HeapRegionNode referencee = edgeX.getDst();
1212 ReferenceEdge edgeNew = edgeX.copy();
1213 edgeNew.setSrc(lnR);
1215 addReferenceEdge(lnR, referencee, edgeNew);
1220 public void assignTempEqualToNewAlloc(TempDescriptor x,
1221 AllocationSite as) {
1227 // after the age operation the newest (or zero-ith oldest)
1228 // node associated with the allocation site should have
1229 // no references to it as if it were a newly allocated
1231 Integer idNewest = as.getIthOldest( 0 );
1232 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
1233 assert hrnNewest != null;
1235 LabelNode lnX = getLabelNodeFromTemp( x );
1236 clearReferenceEdgesFrom( lnX, null, null, true );
1238 // make a new reference to allocated node
1239 TypeDescriptor type = as.getType();
1240 ReferenceEdge edgeNew =
1241 new ReferenceEdge( lnX, // source
1245 false, // is initial param
1246 hrnNewest.getAlpha() // beta
1249 addReferenceEdge( lnX, hrnNewest, edgeNew );
1253 // use the allocation site (unique to entire analysis) to
1254 // locate the heap region nodes in this ownership graph
1255 // that should be aged. The process models the allocation
1256 // of new objects and collects all the oldest allocations
1257 // in a summary node to allow for a finite analysis
1259 // There is an additional property of this method. After
1260 // running it on a particular ownership graph (many graphs
1261 // may have heap regions related to the same allocation site)
1262 // the heap region node objects in this ownership graph will be
1263 // allocated. Therefore, after aging a graph for an allocation
1264 // site, attempts to retrieve the heap region nodes using the
1265 // integer id's contained in the allocation site should always
1266 // return non-null heap regions.
1267 public void age(AllocationSite as) {
1269 // aging adds this allocation site to the graph's
1270 // list of sites that exist in the graph, or does
1271 // nothing if the site is already in the list
1272 allocationSites.add(as);
1274 // get the summary node for the allocation site in the context
1275 // of this particular ownership graph
1276 HeapRegionNode hrnSummary = getSummaryNode(as);
1278 // merge oldest node into summary
1279 Integer idK = as.getOldest();
1280 HeapRegionNode hrnK = id2hrn.get(idK);
1281 mergeIntoSummary(hrnK, hrnSummary);
1283 // move down the line of heap region nodes
1284 // clobbering the ith and transferring all references
1285 // to and from i-1 to node i. Note that this clobbers
1286 // the oldest node (hrnK) that was just merged into
1288 for( int i = allocationDepth - 1; i > 0; --i ) {
1290 // move references from the i-1 oldest to the ith oldest
1291 Integer idIth = as.getIthOldest(i);
1292 HeapRegionNode hrnI = id2hrn.get(idIth);
1293 Integer idImin1th = as.getIthOldest(i - 1);
1294 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
1296 transferOnto(hrnImin1, hrnI);
1299 // as stated above, the newest node should have had its
1300 // references moved over to the second oldest, so we wipe newest
1301 // in preparation for being the new object to assign something to
1302 Integer id0th = as.getIthOldest(0);
1303 HeapRegionNode hrn0 = id2hrn.get(id0th);
1304 assert hrn0 != null;
1306 // clear all references in and out of newest node
1307 clearReferenceEdgesFrom(hrn0, null, null, true);
1308 clearReferenceEdgesTo(hrn0, null, null, true);
1311 // now tokens in reachability sets need to "age" also
1312 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1313 while( itrAllLabelNodes.hasNext() ) {
1314 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1315 LabelNode ln = (LabelNode) me.getValue();
1317 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1318 while( itrEdges.hasNext() ) {
1319 ageTokens(as, itrEdges.next() );
1323 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1324 while( itrAllHRNodes.hasNext() ) {
1325 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1326 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1328 ageTokens(as, hrnToAge);
1330 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1331 while( itrEdges.hasNext() ) {
1332 ageTokens(as, itrEdges.next() );
1337 // after tokens have been aged, reset newest node's reachability
1338 if( hrn0.isFlagged() ) {
1339 hrn0.setAlpha(new ReachabilitySet(
1341 new TokenTuple(hrn0).makeCanonical()
1346 hrn0.setAlpha(new ReachabilitySet(
1347 new TokenTupleSet().makeCanonical()
1354 protected HeapRegionNode getSummaryNode(AllocationSite as) {
1356 Integer idSummary = as.getSummary();
1357 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
1359 // If this is null then we haven't touched this allocation site
1360 // in the context of the current ownership graph, so allocate
1361 // heap region nodes appropriate for the entire allocation site.
1362 // This should only happen once per ownership graph per allocation site,
1363 // and a particular integer id can be used to locate the heap region
1364 // in different ownership graphs that represents the same part of an
1366 if( hrnSummary == null ) {
1368 boolean hasFlags = false;
1369 if( as.getType().isClass() ) {
1370 hasFlags = as.getType().getClassDesc().hasFlags();
1374 hasFlags=as.getFlag();
1377 hrnSummary = createNewHeapRegionNode(idSummary, // id or null to generate a new one
1378 false, // single object?
1380 hasFlags, // flagged?
1381 false, // is a parameter?
1382 as.getType(), // type
1383 as, // allocation site
1384 null, // reachability set
1385 as.toStringForDOT() + "\\nsummary");
1387 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1388 Integer idIth = as.getIthOldest(i);
1389 assert !id2hrn.containsKey(idIth);
1390 createNewHeapRegionNode(idIth, // id or null to generate a new one
1391 true, // single object?
1393 hasFlags, // flagged?
1394 false, // is a parameter?
1395 as.getType(), // type
1396 as, // allocation site
1397 null, // reachability set
1398 as.toStringForDOT() + "\\n" + i + " oldest");
1406 protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
1408 Integer idShadowSummary = as.getSummaryShadow();
1409 HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
1411 if( hrnShadowSummary == null ) {
1413 boolean hasFlags = false;
1414 if( as.getType().isClass() ) {
1415 hasFlags = as.getType().getClassDesc().hasFlags();
1418 hrnShadowSummary = createNewHeapRegionNode(idShadowSummary, // id or null to generate a new one
1419 false, // single object?
1421 hasFlags, // flagged?
1422 false, // is a parameter?
1423 as.getType(), // type
1424 as, // allocation site
1425 null, // reachability set
1426 as + "\\n" + as.getType() + "\\nshadowSum");
1428 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1429 Integer idShadowIth = as.getIthOldestShadow(i);
1430 assert !id2hrn.containsKey(idShadowIth);
1431 createNewHeapRegionNode(idShadowIth, // id or null to generate a new one
1432 true, // single object?
1434 hasFlags, // flagged?
1435 false, // is a parameter?
1436 as.getType(), // type
1437 as, // allocation site
1438 null, // reachability set
1439 as + "\\n" + as.getType() + "\\n" + i + " shadow");
1443 return hrnShadowSummary;
1447 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
1448 assert hrnSummary.isNewSummary();
1450 // transfer references _from_ hrn over to hrnSummary
1451 Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
1452 while( itrReferencee.hasNext() ) {
1453 ReferenceEdge edge = itrReferencee.next();
1454 ReferenceEdge edgeMerged = edge.copy();
1455 edgeMerged.setSrc(hrnSummary);
1457 HeapRegionNode hrnReferencee = edge.getDst();
1458 ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee,
1462 if( edgeSummary == null ) {
1463 // the merge is trivial, nothing to be done
1465 // otherwise an edge from the referencer to hrnSummary exists already
1466 // and the edge referencer->hrn should be merged with it
1467 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1470 addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
1473 // next transfer references _to_ hrn over to hrnSummary
1474 Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
1475 while( itrReferencer.hasNext() ) {
1476 ReferenceEdge edge = itrReferencer.next();
1477 ReferenceEdge edgeMerged = edge.copy();
1478 edgeMerged.setDst(hrnSummary);
1480 OwnershipNode onReferencer = edge.getSrc();
1481 ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary,
1485 if( edgeSummary == null ) {
1486 // the merge is trivial, nothing to be done
1488 // otherwise an edge from the referencer to alpha_S exists already
1489 // and the edge referencer->alpha_K should be merged with it
1490 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1493 addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
1496 // then merge hrn reachability into hrnSummary
1497 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
1501 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
1503 // clear references in and out of node b
1504 clearReferenceEdgesFrom(hrnB, null, null, true);
1505 clearReferenceEdgesTo(hrnB, null, null, true);
1507 // copy each edge in and out of A to B
1508 Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
1509 while( itrReferencee.hasNext() ) {
1510 ReferenceEdge edge = itrReferencee.next();
1511 HeapRegionNode hrnReferencee = edge.getDst();
1512 ReferenceEdge edgeNew = edge.copy();
1513 edgeNew.setSrc(hrnB);
1515 addReferenceEdge(hrnB, hrnReferencee, edgeNew);
1518 Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
1519 while( itrReferencer.hasNext() ) {
1520 ReferenceEdge edge = itrReferencer.next();
1521 OwnershipNode onReferencer = edge.getSrc();
1522 ReferenceEdge edgeNew = edge.copy();
1523 edgeNew.setDst(hrnB);
1525 addReferenceEdge(onReferencer, hrnB, edgeNew);
1528 // replace hrnB reachability with hrnA's
1529 hrnB.setAlpha(hrnA.getAlpha() );
1533 protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
1534 edge.setBeta(edge.getBeta().ageTokens(as) );
1537 protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
1538 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
1543 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1545 HashSet<HeapRegionNode> nodesWithNewAlpha,
1546 HashSet<ReferenceEdge> edgesWithNewBeta) {
1548 HashSet<HeapRegionNode> todoNodes
1549 = new HashSet<HeapRegionNode>();
1550 todoNodes.add(nPrime);
1552 HashSet<ReferenceEdge> todoEdges
1553 = new HashSet<ReferenceEdge>();
1555 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
1556 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
1557 nodePlannedChanges.put(nPrime, c0);
1559 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
1560 = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1562 // first propagate change sets everywhere they can go
1563 while( !todoNodes.isEmpty() ) {
1564 HeapRegionNode n = todoNodes.iterator().next();
1565 ChangeTupleSet C = nodePlannedChanges.get(n);
1567 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
1568 while( referItr.hasNext() ) {
1569 ReferenceEdge edge = referItr.next();
1570 todoEdges.add(edge);
1572 if( !edgePlannedChanges.containsKey(edge) ) {
1573 edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
1576 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
1579 Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
1580 while( refeeItr.hasNext() ) {
1581 ReferenceEdge edgeF = refeeItr.next();
1582 HeapRegionNode m = edgeF.getDst();
1584 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
1586 Iterator<ChangeTuple> itrCprime = C.iterator();
1587 while( itrCprime.hasNext() ) {
1588 ChangeTuple c = itrCprime.next();
1589 if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
1590 changesToPass = changesToPass.union(c);
1594 if( !changesToPass.isEmpty() ) {
1595 if( !nodePlannedChanges.containsKey(m) ) {
1596 nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
1599 ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
1601 if( !changesToPass.isSubset(currentChanges) ) {
1603 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
1609 todoNodes.remove(n);
1612 // then apply all of the changes for each node at once
1613 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1614 while( itrMap.hasNext() ) {
1615 Map.Entry me = (Map.Entry) itrMap.next();
1616 HeapRegionNode n = (HeapRegionNode) me.getKey();
1617 ChangeTupleSet C = (ChangeTupleSet) me.getValue();
1619 n.setAlphaNew( n.getAlpha().applyChangeSet( C, true ) );
1620 nodesWithNewAlpha.add( n );
1623 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
1627 protected void propagateTokensOverEdges(
1628 HashSet<ReferenceEdge> todoEdges,
1629 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
1630 HashSet<ReferenceEdge> edgesWithNewBeta) {
1632 // first propagate all change tuples everywhere they can go
1633 while( !todoEdges.isEmpty() ) {
1634 ReferenceEdge edgeE = todoEdges.iterator().next();
1635 todoEdges.remove(edgeE);
1637 if( !edgePlannedChanges.containsKey(edgeE) ) {
1638 edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
1641 ChangeTupleSet C = edgePlannedChanges.get(edgeE);
1643 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
1645 Iterator<ChangeTuple> itrC = C.iterator();
1646 while( itrC.hasNext() ) {
1647 ChangeTuple c = itrC.next();
1648 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1649 changesToPass = changesToPass.union(c);
1653 OwnershipNode onSrc = edgeE.getSrc();
1655 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
1656 HeapRegionNode n = (HeapRegionNode) onSrc;
1658 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
1659 while( referItr.hasNext() ) {
1660 ReferenceEdge edgeF = referItr.next();
1662 if( !edgePlannedChanges.containsKey(edgeF) ) {
1663 edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
1666 ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
1668 if( !changesToPass.isSubset(currentChanges) ) {
1669 todoEdges.add(edgeF);
1670 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
1676 // then apply all of the changes for each edge at once
1677 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1678 while( itrMap.hasNext() ) {
1679 Map.Entry me = (Map.Entry) itrMap.next();
1680 ReferenceEdge e = (ReferenceEdge) me.getKey();
1681 ChangeTupleSet C = (ChangeTupleSet) me.getValue();
1683 e.setBetaNew( e.getBetaNew().union( e.getBeta().applyChangeSet( C, true ) ) );
1684 edgesWithNewBeta.add( e );
1689 public Set<Integer> calculateAliasedParamSet( FlatCall fc,
1693 Hashtable<Integer, LabelNode> paramIndex2ln =
1694 new Hashtable<Integer, LabelNode>();
1696 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
1697 new Hashtable<Integer, HashSet<HeapRegionNode> >();
1699 for( int i = 0; i < fm.numParameters(); ++i ) {
1700 Integer paramIndex = new Integer( i );
1701 TempDescriptor tdParam = fm.getParameter( i );
1702 TypeDescriptor typeParam = tdParam.getType();
1704 if( typeParam.isImmutable() && !typeParam.isArray() ) {
1705 // don't bother with this primitive parameter, it
1706 // cannot affect reachability
1710 // now depending on whether the callee is static or not
1711 // we need to account for a "this" argument in order to
1712 // find the matching argument in the caller context
1713 TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, paramIndex );
1715 LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1716 paramIndex2ln.put(paramIndex, argLabel_i);
1719 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1720 while( lnArgItr.hasNext() ) {
1721 Map.Entry me = (Map.Entry)lnArgItr.next();
1722 Integer index = (Integer) me.getKey();
1723 LabelNode lnArg_i = (LabelNode) me.getValue();
1725 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1726 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1728 // to find all reachable nodes, start with label referencees
1729 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1730 while( edgeArgItr.hasNext() ) {
1731 ReferenceEdge edge = edgeArgItr.next();
1732 todoNodes.add( edge.getDst() );
1735 // then follow links until all reachable nodes have been found
1736 while( !todoNodes.isEmpty() ) {
1737 HeapRegionNode hrn = todoNodes.iterator().next();
1738 todoNodes.remove(hrn);
1739 reachableNodes.add(hrn);
1741 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1742 while( edgeItr.hasNext() ) {
1743 ReferenceEdge edge = edgeItr.next();
1745 if( !reachableNodes.contains(edge.getDst() ) ) {
1746 todoNodes.add(edge.getDst() );
1752 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1755 Set<Integer> aliasedIndices = new HashSet<Integer>();
1757 // check for arguments that are aliased
1758 for( int i = 0; i < fm.numParameters(); ++i ) {
1759 for( int j = 0; j < i; ++j ) {
1760 HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
1761 HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
1763 // some parameters are immutable or primitive, so skip em
1764 if( s1 == null || s2 == null ) {
1768 Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
1769 intersection.retainAll(s2);
1771 if( !intersection.isEmpty() ) {
1772 aliasedIndices.add( new Integer( i ) );
1773 aliasedIndices.add( new Integer( j ) );
1778 return aliasedIndices;
1782 private String makeMapKey( Integer i, Integer j, String field ) {
1783 return i+","+j+","+field;
1786 private String makeMapKey( Integer i, String field ) {
1790 // these hashtables are used during the mapping procedure to say that
1791 // with respect to some argument i there is an edge placed into some
1792 // category for mapping with respect to another argument index j
1793 // so the key into the hashtable is i, the value is a two-element vector
1794 // that contains in 0 the edge and in 1 the Integer index j
1795 private void ensureEmptyEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
1798 Set<Vector> ei = edge_index_pairs.get( indexI );
1800 ei = new HashSet<Vector>();
1802 edge_index_pairs.put( indexI, ei );
1805 private void addEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
1810 Vector v = new Vector(); v.setSize( 2 );
1812 v.set( 1 , indexJ );
1813 Set<Vector> ei = edge_index_pairs.get( indexI );
1815 ei = new HashSet<Vector>();
1818 edge_index_pairs.put( indexI, ei );
1821 private ReachabilitySet funcScriptR( ReachabilitySet rsIn,
1822 OwnershipGraph ogCallee,
1823 MethodContext mc ) {
1825 ReachabilitySet rsOut = new ReachabilitySet( rsIn );
1827 Iterator itr = ogCallee.paramIndex2paramTokenPrimary.entrySet().iterator();
1828 while( itr.hasNext() ) {
1829 Map.Entry me = (Map.Entry) itr.next();
1830 Integer i = (Integer) me.getKey();
1831 TokenTuple p_i = (TokenTuple) me.getValue();
1832 TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( i );
1834 // skip this if there is no secondary token or the parameter
1835 // is part of the aliasing context
1836 if( s_i == null || mc.getAliasedParamIndices().contains( i ) ) {
1840 rsOut = rsOut.removeTokenAIfTokenB( p_i, s_i );
1846 // detects strong updates to the primary parameter object and
1847 // effects the removal of old edges in the calling graph
1848 private void effectCalleeStrongUpdates( Integer paramIndex,
1849 OwnershipGraph ogCallee,
1850 HeapRegionNode hrnCaller
1852 Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
1853 assert idPrimary != null;
1855 HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
1856 assert hrnPrimary != null;
1858 TypeDescriptor typeParam = hrnPrimary.getType();
1859 assert typeParam.isClass();
1861 Set<String> fieldNamesToRemove = new HashSet<String>();
1863 ClassDescriptor cd = typeParam.getClassDesc();
1864 while( cd != null ) {
1866 Iterator fieldItr = cd.getFields();
1867 while( fieldItr.hasNext() ) {
1869 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
1870 TypeDescriptor typeField = fd.getType();
1871 assert typeField != null;
1873 if( ogCallee.hasFieldBeenUpdated( hrnPrimary, fd.getSymbol() ) ) {
1874 clearReferenceEdgesFrom( hrnCaller, fd.getType(), fd.getSymbol(), false );
1878 cd = cd.getSuperDesc();
1882 private boolean hasFieldBeenUpdated( HeapRegionNode hrnPrimary, String field ) {
1884 Iterator<ReferenceEdge> itr = hrnPrimary.iteratorToReferencees();
1885 while( itr.hasNext() ) {
1886 ReferenceEdge e = itr.next();
1887 if( e.fieldEquals( field ) && e.isInitialParam() ) {
1895 // resolveMethodCall() is used to incorporate a callee graph's effects into
1896 // *this* graph, which is the caller. This method can also be used, after
1897 // the entire analysis is complete, to perform parameter decomposition for
1898 // a given call chain.
1899 public void resolveMethodCall(FlatCall fc, // call site in caller method
1900 boolean isStatic, // whether it is a static method
1901 FlatMethod fm, // the callee method (when virtual, can be many)
1902 OwnershipGraph ogCallee, // the callee's current ownership graph
1903 MethodContext mc, // the aliasing context for this call
1904 ParameterDecomposition pd // if this is not null, we're calling after analysis
1908 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
1909 fm.getMethod().getSymbol().equals( debugCallee )
1913 writeGraph("debug1BeforeCall",
1914 true, // write labels (variables)
1915 true, // selectively hide intermediate temp vars
1916 true, // prune unreachable heap regions
1917 false, // show back edges to confirm graph validity
1918 false, // show parameter indices (unmaintained!)
1919 true, // hide subset reachability states
1920 true); // hide edge taints
1922 ogCallee.writeGraph("debug0Callee",
1923 true, // write labels (variables)
1924 true, // selectively hide intermediate temp vars
1925 true, // prune unreachable heap regions
1926 false, // show back edges to confirm graph validity
1927 false, // show parameter indices (unmaintained!)
1928 true, // hide subset reachability states
1929 true); // hide edge taints
1930 } catch( IOException e ) {}
1932 System.out.println( " "+mc+" is calling "+fm );
1937 // define rewrite rules and other structures to organize data by parameter/argument index
1938 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_p = new Hashtable<Integer, ReachabilitySet>();
1939 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_s = new Hashtable<Integer, ReachabilitySet>();
1941 Hashtable<String, ReachabilitySet> paramIndex2rewriteJ_p2p = new Hashtable<String, ReachabilitySet>(); // select( i, j, f )
1942 Hashtable<String, ReachabilitySet> paramIndex2rewriteJ_p2s = new Hashtable<String, ReachabilitySet>(); // select( i, f )
1943 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2p = new Hashtable<Integer, ReachabilitySet>();
1944 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2s = new Hashtable<Integer, ReachabilitySet>();
1946 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p = new Hashtable<Integer, ReachabilitySet>();
1947 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p2 = new Hashtable<Integer, ReachabilitySet>();
1948 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_s = new Hashtable<Integer, ReachabilitySet>();
1950 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_p = new Hashtable<Integer, ReachabilitySet>();
1951 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_s = new Hashtable<Integer, ReachabilitySet>();
1953 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD = new Hashtable<Integer, ReachabilitySet>();
1956 Hashtable<Integer, LabelNode> paramIndex2ln = new Hashtable<Integer, LabelNode>();
1959 paramIndex2rewriteH_p.put( bogusIndex, rsIdentity );
1960 paramIndex2rewriteH_s.put( bogusIndex, rsIdentity );
1962 paramIndex2rewriteJ_p2p.put( bogusIndex.toString(), rsIdentity );
1963 paramIndex2rewriteJ_p2s.put( bogusIndex.toString(), rsIdentity );
1964 paramIndex2rewriteJ_s2p.put( bogusIndex, rsIdentity );
1965 paramIndex2rewriteJ_s2s.put( bogusIndex, rsIdentity );
1968 for( int i = 0; i < fm.numParameters(); ++i ) {
1969 Integer paramIndex = new Integer(i);
1971 if( !ogCallee.paramIndex2idPrimary.containsKey( paramIndex ) ) {
1972 // skip this immutable parameter
1976 // setup H (primary)
1977 Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
1978 assert ogCallee.id2hrn.containsKey( idPrimary );
1979 HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
1980 assert hrnPrimary != null;
1981 paramIndex2rewriteH_p.put( paramIndex, toShadowTokens( ogCallee, hrnPrimary.getAlpha() ) );
1983 // setup J (primary->X)
1984 Iterator<ReferenceEdge> p2xItr = hrnPrimary.iteratorToReferencees();
1985 while( p2xItr.hasNext() ) {
1986 ReferenceEdge p2xEdge = p2xItr.next();
1988 // we only care about initial parameter edges here
1989 if( !p2xEdge.isInitialParam() ) { continue; }
1991 HeapRegionNode hrnDst = p2xEdge.getDst();
1993 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
1994 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
1995 while( jItr.hasNext() ) {
1996 Integer j = jItr.next();
1997 paramIndex2rewriteJ_p2p.put( makeMapKey( i, j, p2xEdge.getField() ),
1998 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
2002 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
2003 paramIndex2rewriteJ_p2s.put( makeMapKey( i, p2xEdge.getField() ),
2004 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
2008 // setup K (primary)
2009 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
2010 assert tdParamQ != null;
2011 LabelNode lnParamQ = ogCallee.td2ln.get( tdParamQ );
2012 assert lnParamQ != null;
2013 ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnPrimary, null, null );
2014 assert edgeSpecialQ_i != null;
2015 ReachabilitySet qBeta = toShadowTokens( ogCallee, edgeSpecialQ_i.getBeta() );
2017 TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary .get( paramIndex );
2018 TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( paramIndex );
2020 ReachabilitySet K_p = new ReachabilitySet().makeCanonical();
2021 ReachabilitySet K_p2 = new ReachabilitySet().makeCanonical();
2025 // sort qBeta into K_p1 and K_p2
2026 Iterator<TokenTupleSet> ttsItr = qBeta.iterator();
2027 while( ttsItr.hasNext() ) {
2028 TokenTupleSet tts = ttsItr.next();
2029 if( s_i != null && tts.containsBoth( p_i, s_i ) ) {
2030 K_p2 = K_p2.union( tts );
2032 K_p = K_p.union( tts );
2036 paramIndex2rewriteK_p .put( paramIndex, K_p );
2037 paramIndex2rewriteK_p2.put( paramIndex, K_p2 );
2040 // if there is a secondary node, compute the rest of the rewrite rules
2041 if( ogCallee.paramIndex2idSecondary.containsKey( paramIndex ) ) {
2043 // setup H (secondary)
2044 Integer idSecondary = ogCallee.paramIndex2idSecondary.get( paramIndex );
2045 assert ogCallee.id2hrn.containsKey( idSecondary );
2046 HeapRegionNode hrnSecondary = ogCallee.id2hrn.get( idSecondary );
2047 assert hrnSecondary != null;
2048 paramIndex2rewriteH_s.put( paramIndex, toShadowTokens( ogCallee, hrnSecondary.getAlpha() ) );
2050 // setup J (secondary->X)
2051 Iterator<ReferenceEdge> s2xItr = hrnSecondary.iteratorToReferencees();
2052 while( s2xItr.hasNext() ) {
2053 ReferenceEdge s2xEdge = s2xItr.next();
2055 if( !s2xEdge.isInitialParam() ) { continue; }
2057 HeapRegionNode hrnDst = s2xEdge.getDst();
2059 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
2060 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
2061 while( jItr.hasNext() ) {
2062 Integer j = jItr.next();
2063 paramIndex2rewriteJ_s2p.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
2067 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
2068 paramIndex2rewriteJ_s2s.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
2072 // setup K (secondary)
2073 TempDescriptor tdParamR = ogCallee.paramIndex2tdR.get( paramIndex );
2074 assert tdParamR != null;
2075 LabelNode lnParamR = ogCallee.td2ln.get( tdParamR );
2076 assert lnParamR != null;
2077 ReferenceEdge edgeSpecialR_i = lnParamR.getReferenceTo( hrnSecondary, null, null );
2078 assert edgeSpecialR_i != null;
2079 paramIndex2rewriteK_s.put( paramIndex,
2080 toShadowTokens( ogCallee, edgeSpecialR_i.getBeta() ) );
2084 // now depending on whether the callee is static or not
2085 // we need to account for a "this" argument in order to
2086 // find the matching argument in the caller context
2087 TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, paramIndex );
2089 // remember which caller arg label maps to param index
2090 LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i );
2091 paramIndex2ln.put( paramIndex, argLabel_i );
2093 // do a callee-effect strong update pre-pass here
2094 if( argTemp_i.getType().isClass() ) {
2096 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
2097 while( edgeItr.hasNext() ) {
2098 ReferenceEdge edge = edgeItr.next();
2099 HeapRegionNode hrn = edge.getDst();
2101 if( (hrn.getNumReferencers() == 1) || // case 1
2102 (hrn.isSingleObject() && argLabel_i.getNumReferencees() == 1) // case 2
2104 if( !DISABLE_STRONG_UPDATES ) {
2105 effectCalleeStrongUpdates( paramIndex, ogCallee, hrn );
2111 // then calculate the d and D rewrite rules
2112 ReachabilitySet d_i_p = new ReachabilitySet().makeCanonical();
2113 ReachabilitySet d_i_s = new ReachabilitySet().makeCanonical();
2114 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
2115 while( edgeItr.hasNext() ) {
2116 ReferenceEdge edge = edgeItr.next();
2118 d_i_p = d_i_p.union( edge.getBeta().intersection( edge.getDst().getAlpha() ) );
2119 d_i_s = d_i_s.union( edge.getBeta() );
2121 paramIndex2rewrite_d_p.put( paramIndex, d_i_p );
2122 paramIndex2rewrite_d_s.put( paramIndex, d_i_s );
2124 // TODO: we should only do this when we need it, and then
2125 // memoize it for the rest of the mapping procedure
2126 ReachabilitySet D_i = d_i_s.exhaustiveArityCombinations();
2127 paramIndex2rewriteD.put( paramIndex, D_i );
2131 // with respect to each argument, map parameter effects into caller
2132 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
2133 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
2135 Hashtable<Integer, Set<HeapRegionNode> > pi2dr =
2136 new Hashtable<Integer, Set<HeapRegionNode> >();
2138 Hashtable<Integer, Set<HeapRegionNode> > pi2r =
2139 new Hashtable<Integer, Set<HeapRegionNode> >();
2141 Set<HeapRegionNode> defParamObj = new HashSet<HeapRegionNode>();
2143 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
2144 while( lnArgItr.hasNext() ) {
2145 Map.Entry me = (Map.Entry) lnArgItr.next();
2146 Integer index = (Integer) me.getKey();
2147 LabelNode lnArg_i = (LabelNode) me.getValue();
2149 Set<HeapRegionNode> dr = new HashSet<HeapRegionNode>();
2150 Set<HeapRegionNode> r = new HashSet<HeapRegionNode>();
2151 Set<HeapRegionNode> todo = new HashSet<HeapRegionNode>();
2153 // find all reachable nodes starting with label referencees
2154 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
2155 while( edgeArgItr.hasNext() ) {
2156 ReferenceEdge edge = edgeArgItr.next();
2157 HeapRegionNode hrn = edge.getDst();
2161 if( lnArg_i.getNumReferencees() == 1 && hrn.isSingleObject() ) {
2162 defParamObj.add( hrn );
2165 Iterator<ReferenceEdge> edgeHrnItr = hrn.iteratorToReferencees();
2166 while( edgeHrnItr.hasNext() ) {
2167 ReferenceEdge edger = edgeHrnItr.next();
2168 todo.add( edger.getDst() );
2171 // then follow links until all reachable nodes have been found
2172 while( !todo.isEmpty() ) {
2173 HeapRegionNode hrnr = todo.iterator().next();
2174 todo.remove( hrnr );
2178 Iterator<ReferenceEdge> edgeItr = hrnr.iteratorToReferencees();
2179 while( edgeItr.hasNext() ) {
2180 ReferenceEdge edger = edgeItr.next();
2181 if( !r.contains( edger.getDst() ) ) {
2182 todo.add( edger.getDst() );
2187 if( hrn.isSingleObject() ) {
2192 pi2dr.put( index, dr );
2193 pi2r .put( index, r );
2196 assert defParamObj.size() <= fm.numParameters();
2198 // if we're in parameter decomposition mode, report some results here
2202 // report primary parameter object mappings
2203 mapItr = pi2dr.entrySet().iterator();
2204 while( mapItr.hasNext() ) {
2205 Map.Entry me = (Map.Entry) mapItr.next();
2206 Integer paramIndex = (Integer) me.getKey();
2207 Set<HeapRegionNode> hrnAset = (Set<HeapRegionNode>) me.getValue();
2209 Iterator<HeapRegionNode> hrnItr = hrnAset.iterator();
2210 while( hrnItr.hasNext() ) {
2211 HeapRegionNode hrnA = hrnItr.next();
2212 pd.mapRegionToParamObject( hrnA, paramIndex );
2216 // report parameter-reachable mappings
2217 mapItr = pi2r.entrySet().iterator();
2218 while( mapItr.hasNext() ) {
2219 Map.Entry me = (Map.Entry) mapItr.next();
2220 Integer paramIndex = (Integer) me.getKey();
2221 Set<HeapRegionNode> hrnRset = (Set<HeapRegionNode>) me.getValue();
2223 Iterator<HeapRegionNode> hrnItr = hrnRset.iterator();
2224 while( hrnItr.hasNext() ) {
2225 HeapRegionNode hrnR = hrnItr.next();
2226 pd.mapRegionToParamReachable( hrnR, paramIndex );
2230 // and we're done in this method for special param decomp mode
2235 // now iterate over reachable nodes to rewrite their alpha, and
2236 // classify edges found for beta rewrite
2237 Hashtable<TokenTuple, ReachabilitySet> tokens2states = new Hashtable<TokenTuple, ReachabilitySet>();
2239 Hashtable< Integer, Set<Vector> > edges_p2p = new Hashtable< Integer, Set<Vector> >();
2240 Hashtable< Integer, Set<Vector> > edges_p2s = new Hashtable< Integer, Set<Vector> >();
2241 Hashtable< Integer, Set<Vector> > edges_s2p = new Hashtable< Integer, Set<Vector> >();
2242 Hashtable< Integer, Set<Vector> > edges_s2s = new Hashtable< Integer, Set<Vector> >();
2243 Hashtable< Integer, Set<Vector> > edges_up_dr = new Hashtable< Integer, Set<Vector> >();
2244 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();
2754 while( iCallee.hasNext() ) {
2755 Map.Entry meCallee = (Map.Entry) iCallee.next();
2756 Integer idCallee = (Integer) meCallee.getKey();
2757 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
2759 Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
2760 while( heapRegionsItrCallee.hasNext() ) {
2761 ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
2762 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
2763 Integer idChildCallee = hrnChildCallee.getID();
2765 // only address this edge if it is not a special initial edge
2766 if( !edgeCallee.isInitialParam() ) {
2768 // now we know that in the callee method's ownership graph
2769 // there is a heap region->heap region reference edge given
2770 // by heap region pointers:
2771 // hrnCallee -> heapChildCallee
2773 // or by the ownership-graph independent ID's:
2774 // idCallee -> idChildCallee
2776 // make the edge with src and dst so beta info is
2777 // calculated once, then copy it for each new edge in caller
2779 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null,
2781 edgeCallee.getType(),
2782 edgeCallee.getField(),
2784 funcScriptR( toShadowTokens( ogCallee,
2785 edgeCallee.getBeta()
2791 rewriteCallerReachability( bogusIndex,
2793 edgeNewInCallerTemplate,
2794 edgeNewInCallerTemplate.getBeta(),
2796 paramIndex2rewrite_d_p,
2797 paramIndex2rewrite_d_s,
2798 paramIndex2rewriteD,
2803 edgeNewInCallerTemplate.applyBetaNew();
2806 // So now make a set of possible source heaps in the caller graph
2807 // and a set of destination heaps in the caller graph, and make
2808 // a reference edge in the caller for every possible (src,dst) pair
2809 HashSet<HeapRegionNode> possibleCallerSrcs =
2810 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2811 (HeapRegionNode) edgeCallee.getSrc(),
2815 HashSet<HeapRegionNode> possibleCallerDsts =
2816 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2817 edgeCallee.getDst(),
2821 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
2822 Iterator srcItr = possibleCallerSrcs.iterator();
2823 while( srcItr.hasNext() ) {
2824 HeapRegionNode src = (HeapRegionNode) srcItr.next();
2826 if( !hasMatchingField( src, edgeCallee ) ) {
2827 // prune this source node possibility
2831 Iterator dstItr = possibleCallerDsts.iterator();
2832 while( dstItr.hasNext() ) {
2833 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
2835 if( !hasMatchingType( edgeCallee, dst ) ) {
2840 // otherwise the caller src and dst pair can match the edge, so make it
2841 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2842 edgeNewInCaller.setSrc( src );
2843 edgeNewInCaller.setDst( dst );
2845 // handle taint info if callee created this edge
2847 Set<Integer> pParamSet=idPrimary2paramIndexSet.get(dst.getID());
2848 Set<Integer> sParamSet=idSecondary2paramIndexSet.get(dst.getID());
2849 HashSet<Integer> paramSet=new HashSet<Integer>();
2850 if(pParamSet!=null){
2851 paramSet.addAll(pParamSet);
2853 if(sParamSet!=null){
2854 paramSet.addAll(sParamSet);
2856 Iterator<Integer> paramIter=paramSet.iterator();
2857 int newTaintIdentifier=0;
2858 while(paramIter.hasNext()){
2859 Integer paramIdx=paramIter.next();
2860 edgeNewInCaller.tainedBy(paramIdx);
2863 ReferenceEdge edgeExisting = src.getReferenceTo( dst,
2864 edgeNewInCaller.getType(),
2865 edgeNewInCaller.getField() );
2866 if( edgeExisting == null ) {
2867 // if this edge doesn't exist in the caller, create it
2868 addReferenceEdge( src, dst, edgeNewInCaller );
2871 // if it already exists, merge with it
2872 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2882 // return value may need to be assigned in caller
2883 TempDescriptor returnTemp = fc.getReturnTemp();
2884 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2886 LabelNode lnLhsCaller = getLabelNodeFromTemp( returnTemp );
2887 clearReferenceEdgesFrom( lnLhsCaller, null, null, true );
2889 LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp( tdReturn );
2890 Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
2891 while( edgeCalleeItr.hasNext() ) {
2892 ReferenceEdge edgeCallee = edgeCalleeItr.next();
2894 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null,
2896 edgeCallee.getType(),
2897 edgeCallee.getField(),
2899 funcScriptR( toShadowTokens(ogCallee,
2900 edgeCallee.getBeta() ),
2904 rewriteCallerReachability( bogusIndex,
2906 edgeNewInCallerTemplate,
2907 edgeNewInCallerTemplate.getBeta(),
2909 paramIndex2rewrite_d_p,
2910 paramIndex2rewrite_d_s,
2911 paramIndex2rewriteD,
2916 edgeNewInCallerTemplate.applyBetaNew();
2919 HashSet<HeapRegionNode> assignCallerRhs =
2920 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2921 edgeCallee.getDst(),
2925 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
2926 while( itrHrn.hasNext() ) {
2927 HeapRegionNode hrnCaller = itrHrn.next();
2929 if( !hasMatchingType( edgeCallee, hrnCaller ) ) {
2934 // otherwise caller node can match callee edge, so make it
2935 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2936 edgeNewInCaller.setSrc( lnLhsCaller );
2937 edgeNewInCaller.setDst( hrnCaller );
2939 ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo( hrnCaller,
2940 edgeNewInCaller.getType(),
2941 edgeNewInCaller.getField() );
2942 if( edgeExisting == null ) {
2944 // if this edge doesn't exist in the caller, create it
2945 addReferenceEdge( lnLhsCaller, hrnCaller, edgeNewInCaller );
2947 // if it already exists, merge with it
2948 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2957 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
2958 fm.getMethod().getSymbol().equals( debugCallee )
2962 writeGraph("debug7JustBeforeMergeToKCapacity",
2963 true, // write labels (variables)
2964 true, // selectively hide intermediate temp vars
2965 true, // prune unreachable heap regions
2966 false, // show back edges to confirm graph validity
2967 false, // show parameter indices (unmaintained!)
2968 true, // hide subset reachability states
2969 true); // hide edge taints
2970 } catch( IOException e ) {}
2975 // merge the shadow nodes of allocation sites back down to normal capacity
2976 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
2977 while( allocItr.hasNext() ) {
2978 AllocationSite as = allocItr.next();
2980 // first age each allocation site enough times to make room for the shadow nodes
2981 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2985 // then merge the shadow summary into the normal summary
2986 HeapRegionNode hrnSummary = getSummaryNode( as );
2987 assert hrnSummary != null;
2989 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as );
2990 assert hrnSummaryShadow != null;
2992 mergeIntoSummary( hrnSummaryShadow, hrnSummary );
2994 // then clear off after merge
2995 clearReferenceEdgesFrom( hrnSummaryShadow, null, null, true );
2996 clearReferenceEdgesTo ( hrnSummaryShadow, null, null, true );
2997 hrnSummaryShadow.setAlpha( new ReachabilitySet().makeCanonical() );
2999 // then transplant shadow nodes onto the now clean normal nodes
3000 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
3002 Integer idIth = as.getIthOldest( i );
3003 HeapRegionNode hrnIth = id2hrn.get( idIth );
3004 Integer idIthShadow = as.getIthOldestShadow( i );
3005 HeapRegionNode hrnIthShadow = id2hrn.get( idIthShadow );
3007 transferOnto( hrnIthShadow, hrnIth );
3009 // clear off shadow nodes after transfer
3010 clearReferenceEdgesFrom( hrnIthShadow, null, null, true );
3011 clearReferenceEdgesTo ( hrnIthShadow, null, null, true );
3012 hrnIthShadow.setAlpha( new ReachabilitySet().makeCanonical() );
3015 // finally, globally change shadow tokens into normal tokens
3016 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
3017 while( itrAllLabelNodes.hasNext() ) {
3018 Map.Entry me = (Map.Entry) itrAllLabelNodes.next();
3019 LabelNode ln = (LabelNode) me.getValue();
3021 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
3022 while( itrEdges.hasNext() ) {
3023 unshadowTokens( as, itrEdges.next() );
3027 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3028 while( itrAllHRNodes.hasNext() ) {
3029 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
3030 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
3032 unshadowTokens( as, hrnToAge );
3034 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
3035 while( itrEdges.hasNext() ) {
3036 unshadowTokens( as, itrEdges.next() );
3044 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
3045 fm.getMethod().getSymbol().equals( debugCallee )
3049 writeGraph( "debug8JustBeforeSweep",
3050 true, // write labels (variables)
3051 true, // selectively hide intermediate temp vars
3052 true, // prune unreachable heap regions
3053 false, // show back edges to confirm graph validity
3054 false, // show parameter indices (unmaintained!)
3055 true, // hide subset reachability states
3056 true); // hide edge taints
3057 } catch( IOException e ) {}
3062 // improve reachability as much as possible
3063 if( !DISABLE_GLOBAL_SWEEP ) {
3069 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
3070 fm.getMethod().getSymbol().equals( debugCallee )
3074 writeGraph( "debug9endResolveCall",
3075 true, // write labels (variables)
3076 true, // selectively hide intermediate temp vars
3077 true, // prune unreachable heap regions
3078 false, // show back edges to confirm graph validity
3079 false, // show parameter indices (unmaintained!)
3080 true, // hide subset reachability states
3081 true); // hide edge taints
3082 } catch( IOException e ) {}
3083 System.out.println( " "+mc+" done calling "+fm );
3085 if( x == debugCallMapCount ) {
3094 protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
3096 // if no type, then it's a match-everything region
3097 TypeDescriptor tdSrc = src.getType();
3098 if( tdSrc == null ) {
3102 if( tdSrc.isArray() ) {
3103 TypeDescriptor td = edge.getType();
3106 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3107 assert tdSrcDeref != null;
3109 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3113 return edge.getField().equals( OwnershipAnalysis.arrayElementFieldName );
3116 // if it's not a class, it doesn't have any fields to match
3117 if( !tdSrc.isClass() ) {
3121 ClassDescriptor cd = tdSrc.getClassDesc();
3122 while( cd != null ) {
3123 Iterator fieldItr = cd.getFields();
3125 while( fieldItr.hasNext() ) {
3126 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3128 if( fd.getType().equals( edge.getType() ) &&
3129 fd.getSymbol().equals( edge.getField() ) ) {
3134 cd = cd.getSuperDesc();
3137 // otherwise it is a class with fields
3138 // but we didn't find a match
3143 protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
3145 // if the region has no type, matches everything
3146 TypeDescriptor tdDst = dst.getType();
3147 if( tdDst == null ) {
3151 // if the type is not a class or an array, don't
3152 // match because primitives are copied, no aliases
3153 ClassDescriptor cdDst = tdDst.getClassDesc();
3154 if( cdDst == null && !tdDst.isArray() ) {
3158 // if the edge type is null, it matches everything
3159 TypeDescriptor tdEdge = edge.getType();
3160 if( tdEdge == null ) {
3164 return typeUtil.isSuperorType(tdEdge, tdDst);
3169 protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
3170 edge.setBeta(edge.getBeta().unshadowTokens(as) );
3173 protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
3174 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
3178 private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
3179 ReachabilitySet rsIn) {
3181 ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical();
3183 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
3184 while( allocItr.hasNext() ) {
3185 AllocationSite as = allocItr.next();
3187 rsOut = rsOut.toShadowTokens(as);
3190 return rsOut.makeCanonical();
3194 private void rewriteCallerReachability(Integer paramIndex,
3197 ReachabilitySet rules,
3198 Hashtable<TokenTuple, ReachabilitySet> tokens2states,
3199 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_p,
3200 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_s,
3201 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
3202 OwnershipGraph ogCallee,
3203 boolean makeChangeSet,
3204 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
3206 assert(hrn == null && edge != null) ||
3207 (hrn != null && edge == null);
3209 assert rules != null;
3210 assert tokens2states != null;
3212 ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
3214 // for initializing structures in this method
3215 TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
3217 // use this to construct a change set if required; the idea is to
3218 // map every partially rewritten token tuple set to the set of
3219 // caller-context token tuple sets that were used to generate it
3220 Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
3221 new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
3222 rewritten2source.put( ttsEmpty, new HashSet<TokenTupleSet>() );
3225 Iterator<TokenTupleSet> rulesItr = rules.iterator();
3226 while(rulesItr.hasNext()) {
3227 TokenTupleSet rule = rulesItr.next();
3229 ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
3231 Iterator<TokenTuple> ruleItr = rule.iterator();
3232 while(ruleItr.hasNext()) {
3233 TokenTuple ttCallee = ruleItr.next();
3235 // compute the possibilities for rewriting this callee token
3236 ReachabilitySet ttCalleeRewrites = null;
3237 boolean callerSourceUsed = false;
3239 if( tokens2states.containsKey( ttCallee ) ) {
3240 callerSourceUsed = true;
3241 ttCalleeRewrites = tokens2states.get( ttCallee );
3242 assert ttCalleeRewrites != null;
3244 } else if( ogCallee.paramTokenPrimary2paramIndex.containsKey( ttCallee ) ) {
3246 Integer paramIndex_j = ogCallee.paramTokenPrimary2paramIndex.get( ttCallee );
3247 assert paramIndex_j != null;
3248 ttCalleeRewrites = paramIndex2rewrite_d_p.get( paramIndex_j );
3249 assert ttCalleeRewrites != null;
3251 } else if( ogCallee.paramTokenSecondary2paramIndex.containsKey( ttCallee ) ) {
3253 Integer paramIndex_j = ogCallee.paramTokenSecondary2paramIndex.get( ttCallee );
3254 assert paramIndex_j != null;
3255 ttCalleeRewrites = paramIndex2rewrite_d_s.get( paramIndex_j );
3256 assert ttCalleeRewrites != null;
3258 } else if( ogCallee.paramTokenSecondaryPlus2paramIndex.containsKey( ttCallee ) ) {
3260 Integer paramIndex_j = ogCallee.paramTokenSecondaryPlus2paramIndex.get( ttCallee );
3261 assert paramIndex_j != null;
3262 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
3263 assert ttCalleeRewrites != null;
3265 } else if( ogCallee.paramTokenSecondaryStar2paramIndex.containsKey( ttCallee ) ) {
3267 Integer paramIndex_j = ogCallee.paramTokenSecondaryStar2paramIndex.get( ttCallee );
3268 assert paramIndex_j != null;
3269 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
3270 assert ttCalleeRewrites != null;
3273 // otherwise there's no need for a rewrite, just pass this one on
3274 TokenTupleSet ttsCaller = new TokenTupleSet( ttCallee ).makeCanonical();
3275 ttCalleeRewrites = new ReachabilitySet( ttsCaller ).makeCanonical();
3278 // branch every version of the working rewritten rule with
3279 // the possibilities for rewriting the current callee token
3280 ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
3282 Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
3283 while( rewrittenRuleItr.hasNext() ) {
3284 TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
3286 Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
3287 while( ttCalleeRewritesItr.hasNext() ) {
3288 TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
3290 TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
3292 if( makeChangeSet ) {
3293 // in order to keep the list of source token tuple sets
3294 // start with the sets used to make the partially rewritten
3295 // rule up to this point
3296 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewritten );
3297 assert sourceSets != null;
3299 // make a shallow copy for possible modification
3300 sourceSets = (HashSet<TokenTupleSet>) sourceSets.clone();
3302 // if we used something from the caller to rewrite it, remember
3303 if( callerSourceUsed ) {
3304 sourceSets.add( ttsBranch );
3307 // set mapping for the further rewritten rule
3308 rewritten2source.put( ttsRewrittenNext, sourceSets );
3311 rewrittenRuleWithTTCallee =
3312 rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
3316 // now the rewritten rule's possibilities have been extended by
3317 // rewriting the current callee token, remember result
3318 rewrittenRule = rewrittenRuleWithTTCallee;
3321 // the rule has been entirely rewritten into the caller context
3322 // now, so add it to the new reachability information
3323 callerReachabilityNew =
3324 callerReachabilityNew.union( rewrittenRule );
3327 if( makeChangeSet ) {
3328 ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
3330 // each possibility for the final reachability should have a set of
3331 // caller sources mapped to it, use to create the change set
3332 Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
3333 while( callerReachabilityItr.hasNext() ) {
3334 TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
3335 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewrittenFinal );
3336 assert sourceSets != null;
3338 Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
3339 while( sourceSetsItr.hasNext() ) {
3340 TokenTupleSet ttsSource = sourceSetsItr.next();
3343 callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
3347 assert edgePlannedChanges != null;
3348 edgePlannedChanges.put( edge, callerChangeSet );
3352 edge.setBetaNew( edge.getBetaNew().union( callerReachabilityNew ) );
3354 hrn.setAlphaNew( hrn.getAlphaNew().union( callerReachabilityNew ) );
3360 private HashSet<HeapRegionNode>
3361 getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
3362 HeapRegionNode hrnCallee,
3363 Hashtable<Integer, Set<HeapRegionNode> > pi2dr,
3364 Hashtable<Integer, Set<HeapRegionNode> > pi2r
3367 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
3369 Set<Integer> paramIndicesCallee_p = ogCallee.idPrimary2paramIndexSet .get( hrnCallee.getID() );
3370 Set<Integer> paramIndicesCallee_s = ogCallee.idSecondary2paramIndexSet.get( hrnCallee.getID() );
3372 if( paramIndicesCallee_p == null &&
3373 paramIndicesCallee_s == null ) {
3374 // this is a node allocated in the callee and it has
3375 // exactly one shadow node in the caller to map to
3376 AllocationSite as = hrnCallee.getAllocationSite();
3379 int age = as.getAgeCategory( hrnCallee.getID() );
3380 assert age != AllocationSite.AGE_notInThisSite;
3383 if( age == AllocationSite.AGE_summary ) {
3384 idCaller = as.getSummaryShadow();
3386 } else if( age == AllocationSite.AGE_oldest ) {
3387 idCaller = as.getOldestShadow();
3390 assert age == AllocationSite.AGE_in_I;
3392 Integer I = as.getAge( hrnCallee.getID() );
3395 idCaller = as.getIthOldestShadow( I );
3398 assert id2hrn.containsKey( idCaller );
3399 possibleCallerHRNs.add( id2hrn.get( idCaller ) );
3401 return possibleCallerHRNs;
3404 // find out what primary objects this might be
3405 if( paramIndicesCallee_p != null ) {
3406 // this is a node that was created to represent a parameter
3407 // so it maps to some regions directly reachable from the arg labels
3408 Iterator<Integer> itrIndex = paramIndicesCallee_p.iterator();
3409 while( itrIndex.hasNext() ) {
3410 Integer paramIndexCallee = itrIndex.next();
3411 assert pi2dr.containsKey( paramIndexCallee );
3412 possibleCallerHRNs.addAll( pi2dr.get( paramIndexCallee ) );
3416 // find out what secondary objects this might be
3417 if( paramIndicesCallee_s != null ) {
3418 // this is a node that was created to represent objs reachable from
3419 // some parameter, so it maps to regions reachable from the arg labels
3420 Iterator<Integer> itrIndex = paramIndicesCallee_s.iterator();
3421 while( itrIndex.hasNext() ) {
3422 Integer paramIndexCallee = itrIndex.next();
3423 assert pi2r.containsKey( paramIndexCallee );
3424 possibleCallerHRNs.addAll( pi2r.get( paramIndexCallee ) );
3428 // TODO: is this true?
3429 // one of the two cases above should have put something in here
3430 //assert !possibleCallerHRNs.isEmpty();
3432 return possibleCallerHRNs;
3437 ////////////////////////////////////////////////////
3439 // This global sweep is an optional step to prune
3440 // reachability sets that are not internally
3441 // consistent with the global graph. It should be
3442 // invoked after strong updates or method calls.
3444 ////////////////////////////////////////////////////
3445 public void globalSweep() {
3447 // boldB is part of the phase 1 sweep
3448 Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> > boldB =
3449 new Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> >();
3451 // visit every heap region to initialize alphaNew and calculate boldB
3452 Set hrns = id2hrn.entrySet();
3453 Iterator itrHrns = hrns.iterator();
3454 while( itrHrns.hasNext() ) {
3455 Map.Entry me = (Map.Entry)itrHrns.next();
3456 Integer token = (Integer) me.getKey();
3457 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3459 // assert that this node and incoming edges have clean alphaNew
3460 // and betaNew sets, respectively
3461 assert rsEmpty.equals( hrn.getAlphaNew() );
3463 Iterator<ReferenceEdge> itrRers = hrn.iteratorToReferencers();
3464 while( itrRers.hasNext() ) {
3465 ReferenceEdge edge = itrRers.next();
3466 assert rsEmpty.equals( edge.getBetaNew() );
3469 // calculate boldB for this flagged node
3470 if( hrn.isFlagged() || hrn.isParameter() ) {
3472 Hashtable<ReferenceEdge, ReachabilitySet> boldB_f =
3473 new Hashtable<ReferenceEdge, ReachabilitySet>();
3475 Set<ReferenceEdge> workSetEdges = new HashSet<ReferenceEdge>();
3477 // initial boldB_f constraints
3478 Iterator<ReferenceEdge> itrRees = hrn.iteratorToReferencees();
3479 while( itrRees.hasNext() ) {
3480 ReferenceEdge edge = itrRees.next();
3482 assert !boldB.containsKey( edge );
3483 boldB_f.put( edge, edge.getBeta() );
3485 assert !workSetEdges.contains( edge );
3486 workSetEdges.add( edge );
3489 // enforce the boldB_f constraint at edges until we reach a fixed point
3490 while( !workSetEdges.isEmpty() ) {
3491 ReferenceEdge edge = workSetEdges.iterator().next();
3492 workSetEdges.remove( edge );
3494 Iterator<ReferenceEdge> itrPrime = edge.getDst().iteratorToReferencees();
3495 while( itrPrime.hasNext() ) {
3496 ReferenceEdge edgePrime = itrPrime.next();
3498 ReachabilitySet prevResult = boldB_f.get( edgePrime );
3499 ReachabilitySet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
3501 if( prevResult == null ||
3502 prevResult.union( intersection ).size() > prevResult.size() ) {
3504 if( prevResult == null ) {
3505 boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) );
3507 boldB_f.put( edgePrime, prevResult .union( intersection ) );
3509 workSetEdges.add( edgePrime );
3514 boldB.put( token, boldB_f );
3519 // use boldB to prune tokens from alpha states that are impossible
3520 // and propagate the differences backwards across edges
3521 HashSet<ReferenceEdge> edgesForPropagation = new HashSet<ReferenceEdge>();
3523 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
3524 new Hashtable<ReferenceEdge, ChangeTupleSet>();
3526 hrns = id2hrn.entrySet();
3527 itrHrns = hrns.iterator();
3528 while( itrHrns.hasNext() ) {
3529 Map.Entry me = (Map.Entry)itrHrns.next();
3530 Integer token = (Integer) me.getKey();
3531 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3533 // never remove the identity token from a flagged region
3534 // because it is trivially satisfied
3535 TokenTuple ttException = new TokenTuple( token,
3536 !hrn.isSingleObject(),
3537 TokenTuple.ARITY_ONE ).makeCanonical();
3539 ChangeTupleSet cts = new ChangeTupleSet().makeCanonical();
3541 // mark tokens for removal
3542 Iterator<TokenTupleSet> stateItr = hrn.getAlpha().iterator();
3543 while( stateItr.hasNext() ) {
3544 TokenTupleSet ttsOld = stateItr.next();
3546 TokenTupleSet markedTokens = new TokenTupleSet().makeCanonical();
3548 Iterator<TokenTuple> ttItr = ttsOld.iterator();
3549 while( ttItr.hasNext() ) {
3550 TokenTuple ttOld = ttItr.next();
3552 // never remove the identity token from a flagged region
3553 // because it is trivially satisfied
3554 if( hrn.isFlagged() || hrn.isParameter() ) {
3555 if( ttOld == ttException ) {
3560 // does boldB_ttOld allow this token?
3561 boolean foundState = false;
3562 Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3563 while( incidentEdgeItr.hasNext() ) {
3564 ReferenceEdge incidentEdge = incidentEdgeItr.next();
3566 // if it isn't allowed, mark for removal
3567 Integer idOld = ttOld.getToken();
3568 assert id2hrn.containsKey( idOld );
3569 Hashtable<ReferenceEdge, ReachabilitySet> B = boldB.get( idOld );
3570 ReachabilitySet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL!
3571 if( boldB_ttOld_incident != null &&
3572 boldB_ttOld_incident.contains( ttsOld ) ) {
3578 markedTokens = markedTokens.add( ttOld );
3582 // if there is nothing marked, just move on
3583 if( markedTokens.isEmpty() ) {
3584 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
3588 // remove all marked tokens and establish a change set that should
3589 // propagate backwards over edges from this node
3590 TokenTupleSet ttsPruned = new TokenTupleSet().makeCanonical();
3591 ttItr = ttsOld.iterator();
3592 while( ttItr.hasNext() ) {
3593 TokenTuple ttOld = ttItr.next();
3595 if( !markedTokens.containsTuple( ttOld ) ) {
3596 ttsPruned = ttsPruned.union( ttOld );
3599 assert !ttsOld.equals( ttsPruned );
3601 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
3602 ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
3603 cts = cts.union( ct );
3606 // throw change tuple set on all incident edges
3607 if( !cts.isEmpty() ) {
3608 Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3609 while( incidentEdgeItr.hasNext() ) {
3610 ReferenceEdge incidentEdge = incidentEdgeItr.next();
3612 edgesForPropagation.add( incidentEdge );
3614 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3615 edgePlannedChanges.put( incidentEdge, cts );
3617 edgePlannedChanges.put(
3619 edgePlannedChanges.get( incidentEdge ).union( cts )
3626 HashSet<ReferenceEdge> edgesUpdated = new HashSet<ReferenceEdge>();
3628 propagateTokensOverEdges( edgesForPropagation,
3632 // at the end of the 1st phase reference edges have
3633 // beta, betaNew that correspond to beta and betaR
3635 // commit beta<-betaNew, so beta=betaR and betaNew
3636 // will represent the beta' calculation in 2nd phase
3638 // commit alpha<-alphaNew because it won't change
3639 HashSet<ReferenceEdge> res = new HashSet<ReferenceEdge>();
3641 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3642 while( nodeItr.hasNext() ) {
3643 HeapRegionNode hrn = nodeItr.next();
3644 hrn.applyAlphaNew();
3645 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
3646 while( itrRes.hasNext() ) {
3647 res.add( itrRes.next() );
3653 Iterator<ReferenceEdge> edgeItr = res.iterator();
3654 while( edgeItr.hasNext() ) {
3655 ReferenceEdge edge = edgeItr.next();
3656 HeapRegionNode hrn = edge.getDst();
3658 // commit results of last phase
3659 if( edgesUpdated.contains( edge ) ) {
3660 edge.applyBetaNew();
3663 // compute intial condition of 2nd phase
3664 edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
3667 // every edge in the graph is the initial workset
3668 Set<ReferenceEdge> edgeWorkSet = (Set) res.clone();
3669 while( !edgeWorkSet.isEmpty() ) {
3670 ReferenceEdge edgePrime = edgeWorkSet.iterator().next();
3671 edgeWorkSet.remove( edgePrime );
3673 OwnershipNode on = edgePrime.getSrc();
3674 if( !(on instanceof HeapRegionNode) ) {
3677 HeapRegionNode hrn = (HeapRegionNode) on;
3679 Iterator<ReferenceEdge> itrEdge = hrn.iteratorToReferencers();
3680 while( itrEdge.hasNext() ) {
3681 ReferenceEdge edge = itrEdge.next();
3683 ReachabilitySet prevResult = edge.getBetaNew();
3684 assert prevResult != null;
3686 ReachabilitySet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
3688 if( prevResult.union( intersection ).size() > prevResult.size() ) {
3689 edge.setBetaNew( prevResult.union( intersection ) );
3690 edgeWorkSet.add( edge );
3695 // commit beta' (beta<-betaNew)
3696 edgeItr = res.iterator();
3697 while( edgeItr.hasNext() ) {
3698 edgeItr.next().applyBetaNew();
3704 ////////////////////////////////////////////////////
3705 // in merge() and equals() methods the suffix A
3706 // represents the passed in graph and the suffix
3707 // B refers to the graph in this object
3708 // Merging means to take the incoming graph A and
3709 // merge it into B, so after the operation graph B
3710 // is the final result.
3711 ////////////////////////////////////////////////////
3712 public void merge(OwnershipGraph og) {
3718 mergeOwnershipNodes(og);
3719 mergeReferenceEdges(og);
3720 mergeParamIndexMappings(og);
3721 mergeAllocationSites(og);
3725 protected void mergeOwnershipNodes(OwnershipGraph og) {
3726 Set sA = og.id2hrn.entrySet();
3727 Iterator iA = sA.iterator();
3728 while( iA.hasNext() ) {
3729 Map.Entry meA = (Map.Entry)iA.next();
3730 Integer idA = (Integer) meA.getKey();
3731 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3733 // if this graph doesn't have a node the
3734 // incoming graph has, allocate it
3735 if( !id2hrn.containsKey(idA) ) {
3736 HeapRegionNode hrnB = hrnA.copy();
3737 id2hrn.put(idA, hrnB);
3740 // otherwise this is a node present in both graphs
3741 // so make the new reachability set a union of the
3742 // nodes' reachability sets
3743 HeapRegionNode hrnB = id2hrn.get(idA);
3744 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
3748 // now add any label nodes that are in graph B but
3750 sA = og.td2ln.entrySet();
3752 while( iA.hasNext() ) {
3753 Map.Entry meA = (Map.Entry)iA.next();
3754 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3755 LabelNode lnA = (LabelNode) meA.getValue();
3757 // if the label doesn't exist in B, allocate and add it
3758 LabelNode lnB = getLabelNodeFromTemp(tdA);
3762 protected void mergeReferenceEdges(OwnershipGraph og) {
3765 Set sA = og.id2hrn.entrySet();
3766 Iterator iA = sA.iterator();
3767 while( iA.hasNext() ) {
3768 Map.Entry meA = (Map.Entry)iA.next();
3769 Integer idA = (Integer) meA.getKey();
3770 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3772 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3773 while( heapRegionsItrA.hasNext() ) {
3774 ReferenceEdge edgeA = heapRegionsItrA.next();
3775 HeapRegionNode hrnChildA = edgeA.getDst();
3776 Integer idChildA = hrnChildA.getID();
3778 // at this point we know an edge in graph A exists
3779 // idA -> idChildA, does this exist in B?
3780 assert id2hrn.containsKey(idA);
3781 HeapRegionNode hrnB = id2hrn.get(idA);
3782 ReferenceEdge edgeToMerge = null;
3784 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3785 while( heapRegionsItrB.hasNext() &&
3786 edgeToMerge == null ) {
3788 ReferenceEdge edgeB = heapRegionsItrB.next();
3789 HeapRegionNode hrnChildB = edgeB.getDst();
3790 Integer idChildB = hrnChildB.getID();
3792 // don't use the ReferenceEdge.equals() here because
3793 // we're talking about existence between graphs
3794 if( idChildB.equals( idChildA ) &&
3795 edgeB.typeAndFieldEquals( edgeA ) ) {
3797 edgeToMerge = edgeB;
3801 // if the edge from A was not found in B,
3803 if( edgeToMerge == null ) {
3804 assert id2hrn.containsKey(idChildA);
3805 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3806 edgeToMerge = edgeA.copy();
3807 edgeToMerge.setSrc(hrnB);
3808 edgeToMerge.setDst(hrnChildB);
3809 addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
3811 // otherwise, the edge already existed in both graphs
3812 // so merge their reachability sets
3814 // just replace this beta set with the union
3815 assert edgeToMerge != null;
3816 edgeToMerge.setBeta(
3817 edgeToMerge.getBeta().union(edgeA.getBeta() )
3820 edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
3821 if( !edgeA.isInitialParam() ) {
3822 edgeToMerge.setIsInitialParam(false);
3828 // and then again with label nodes
3829 sA = og.td2ln.entrySet();
3831 while( iA.hasNext() ) {
3832 Map.Entry meA = (Map.Entry)iA.next();
3833 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3834 LabelNode lnA = (LabelNode) meA.getValue();
3836 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
3837 while( heapRegionsItrA.hasNext() ) {
3838 ReferenceEdge edgeA = heapRegionsItrA.next();
3839 HeapRegionNode hrnChildA = edgeA.getDst();
3840 Integer idChildA = hrnChildA.getID();
3842 // at this point we know an edge in graph A exists
3843 // tdA -> idChildA, does this exist in B?
3844 assert td2ln.containsKey(tdA);
3845 LabelNode lnB = td2ln.get(tdA);
3846 ReferenceEdge edgeToMerge = null;
3848 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
3849 while( heapRegionsItrB.hasNext() &&
3850 edgeToMerge == null ) {
3852 ReferenceEdge edgeB = heapRegionsItrB.next();
3853 HeapRegionNode hrnChildB = edgeB.getDst();
3854 Integer idChildB = hrnChildB.getID();
3856 // don't use the ReferenceEdge.equals() here because
3857 // we're talking about existence between graphs
3858 if( idChildB.equals( idChildA ) &&
3859 edgeB.typeAndFieldEquals( edgeA ) ) {
3861 edgeToMerge = edgeB;
3865 // if the edge from A was not found in B,
3867 if( edgeToMerge == null ) {
3868 assert id2hrn.containsKey(idChildA);
3869 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3870 edgeToMerge = edgeA.copy();
3871 edgeToMerge.setSrc(lnB);
3872 edgeToMerge.setDst(hrnChildB);
3873 addReferenceEdge(lnB, hrnChildB, edgeToMerge);
3875 // otherwise, the edge already existed in both graphs
3876 // so merge their reachability sets
3878 // just replace this beta set with the union
3879 edgeToMerge.setBeta(
3880 edgeToMerge.getBeta().union(edgeA.getBeta() )
3882 edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
3883 if( !edgeA.isInitialParam() ) {
3884 edgeToMerge.setIsInitialParam(false);
3891 // you should only merge ownership graphs that have the
3892 // same number of parameters, or if one or both parameter
3893 // index tables are empty
3894 protected void mergeParamIndexMappings(OwnershipGraph og) {
3896 if( idPrimary2paramIndexSet.size() == 0 ) {
3898 idPrimary2paramIndexSet = og.idPrimary2paramIndexSet;
3899 paramIndex2idPrimary = og.paramIndex2idPrimary;
3901 idSecondary2paramIndexSet = og.idSecondary2paramIndexSet;
3902 paramIndex2idSecondary = og.paramIndex2idSecondary;
3904 paramIndex2tdQ = og.paramIndex2tdQ;
3905 paramIndex2tdR = og.paramIndex2tdR;
3907 paramTokenPrimary2paramIndex = og.paramTokenPrimary2paramIndex;
3908 paramIndex2paramTokenPrimary = og.paramIndex2paramTokenPrimary;
3910 paramTokenSecondary2paramIndex = og.paramTokenSecondary2paramIndex;
3911 paramIndex2paramTokenSecondary = og.paramIndex2paramTokenSecondary;
3912 paramTokenSecondaryPlus2paramIndex = og.paramTokenSecondaryPlus2paramIndex;
3913 paramIndex2paramTokenSecondaryPlus = og.paramIndex2paramTokenSecondaryPlus;
3914 paramTokenSecondaryStar2paramIndex = og.paramTokenSecondaryStar2paramIndex;
3915 paramIndex2paramTokenSecondaryStar = og.paramIndex2paramTokenSecondaryStar;
3920 if( og.idPrimary2paramIndexSet.size() == 0 ) {
3922 og.idPrimary2paramIndexSet = idPrimary2paramIndexSet;
3923 og.paramIndex2idPrimary = paramIndex2idPrimary;
3925 og.idSecondary2paramIndexSet = idSecondary2paramIndexSet;
3926 og.paramIndex2idSecondary = paramIndex2idSecondary;
3928 og.paramIndex2tdQ = paramIndex2tdQ;
3929 og.paramIndex2tdR = paramIndex2tdR;
3931 og.paramTokenPrimary2paramIndex = paramTokenPrimary2paramIndex;
3932 og.paramIndex2paramTokenPrimary = paramIndex2paramTokenPrimary;
3934 og.paramTokenSecondary2paramIndex = paramTokenSecondary2paramIndex;
3935 og.paramIndex2paramTokenSecondary = paramIndex2paramTokenSecondary;
3936 og.paramTokenSecondaryPlus2paramIndex = paramTokenSecondaryPlus2paramIndex;
3937 og.paramIndex2paramTokenSecondaryPlus = paramIndex2paramTokenSecondaryPlus;
3938 og.paramTokenSecondaryStar2paramIndex = paramTokenSecondaryStar2paramIndex;
3939 og.paramIndex2paramTokenSecondaryStar = paramIndex2paramTokenSecondaryStar;
3944 assert idPrimary2paramIndexSet.size() == og.idPrimary2paramIndexSet.size();
3945 assert idSecondary2paramIndexSet.size() == og.idSecondary2paramIndexSet.size();
3948 protected void mergeAllocationSites(OwnershipGraph og) {
3949 allocationSites.addAll(og.allocationSites);
3954 // it is necessary in the equals() member functions
3955 // to "check both ways" when comparing the data
3956 // structures of two graphs. For instance, if all
3957 // edges between heap region nodes in graph A are
3958 // present and equal in graph B it is not sufficient
3959 // to say the graphs are equal. Consider that there
3960 // may be edges in graph B that are not in graph A.
3961 // the only way to know that all edges in both graphs
3962 // are equally present is to iterate over both data
3963 // structures and compare against the other graph.
3964 public boolean equals(OwnershipGraph og) {
3970 if( !areHeapRegionNodesEqual(og) ) {
3974 if( !areLabelNodesEqual(og) ) {
3978 if( !areReferenceEdgesEqual(og) ) {
3982 if( !areParamIndexMappingsEqual(og) ) {
3986 // if everything is equal up to this point,
3987 // assert that allocationSites is also equal--
3988 // this data is redundant and kept for efficiency
3989 assert allocationSites.equals(og.allocationSites);
3994 protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
3996 if( !areallHRNinAalsoinBandequal(this, og) ) {
4000 if( !areallHRNinAalsoinBandequal(og, this) ) {
4007 static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
4008 OwnershipGraph ogB) {
4009 Set sA = ogA.id2hrn.entrySet();
4010 Iterator iA = sA.iterator();
4011 while( iA.hasNext() ) {
4012 Map.Entry meA = (Map.Entry)iA.next();
4013 Integer idA = (Integer) meA.getKey();
4014 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4016 if( !ogB.id2hrn.containsKey(idA) ) {
4020 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
4021 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
4030 protected boolean areLabelNodesEqual(OwnershipGraph og) {
4032 if( !areallLNinAalsoinBandequal(this, og) ) {
4036 if( !areallLNinAalsoinBandequal(og, this) ) {
4043 static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
4044 OwnershipGraph ogB) {
4045 Set sA = ogA.td2ln.entrySet();
4046 Iterator iA = sA.iterator();
4047 while( iA.hasNext() ) {
4048 Map.Entry meA = (Map.Entry)iA.next();
4049 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4051 if( !ogB.td2ln.containsKey(tdA) ) {
4060 protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
4061 if( !areallREinAandBequal(this, og) ) {
4068 static protected boolean areallREinAandBequal(OwnershipGraph ogA,
4069 OwnershipGraph ogB) {
4071 // check all the heap region->heap region edges
4072 Set sA = ogA.id2hrn.entrySet();
4073 Iterator iA = sA.iterator();
4074 while( iA.hasNext() ) {
4075 Map.Entry meA = (Map.Entry)iA.next();
4076 Integer idA = (Integer) meA.getKey();
4077 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4079 // we should have already checked that the same
4080 // heap regions exist in both graphs
4081 assert ogB.id2hrn.containsKey(idA);
4083 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
4087 // then check every edge in B for presence in A, starting
4088 // from the same parent HeapRegionNode
4089 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
4091 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
4096 // then check all the label->heap region edges
4097 sA = ogA.td2ln.entrySet();
4099 while( iA.hasNext() ) {
4100 Map.Entry meA = (Map.Entry)iA.next();
4101 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4102 LabelNode lnA = (LabelNode) meA.getValue();
4104 // we should have already checked that the same
4105 // label nodes exist in both graphs
4106 assert ogB.td2ln.containsKey(tdA);
4108 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
4112 // then check every edge in B for presence in A, starting
4113 // from the same parent LabelNode
4114 LabelNode lnB = ogB.td2ln.get(tdA);
4116 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
4125 static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
4127 OwnershipGraph ogB) {
4129 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
4130 while( itrA.hasNext() ) {
4131 ReferenceEdge edgeA = itrA.next();
4132 HeapRegionNode hrnChildA = edgeA.getDst();
4133 Integer idChildA = hrnChildA.getID();
4135 assert ogB.id2hrn.containsKey(idChildA);
4137 // at this point we know an edge in graph A exists
4138 // onA -> idChildA, does this exact edge exist in B?
4139 boolean edgeFound = false;
4141 OwnershipNode onB = null;
4142 if( onA instanceof HeapRegionNode ) {
4143 HeapRegionNode hrnA = (HeapRegionNode) onA;
4144 onB = ogB.id2hrn.get(hrnA.getID() );
4146 LabelNode lnA = (LabelNode) onA;
4147 onB = ogB.td2ln.get(lnA.getTempDescriptor() );
4150 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
4151 while( itrB.hasNext() ) {
4152 ReferenceEdge edgeB = itrB.next();
4153 HeapRegionNode hrnChildB = edgeB.getDst();
4154 Integer idChildB = hrnChildB.getID();
4156 if( idChildA.equals( idChildB ) &&
4157 edgeA.typeAndFieldEquals( edgeB ) ) {
4159 // there is an edge in the right place with the right field,
4160 // but do they have the same attributes?
4161 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
4176 protected boolean areParamIndexMappingsEqual(OwnershipGraph og) {
4178 if( idPrimary2paramIndexSet.size() != og.idPrimary2paramIndexSet.size() ) {
4182 if( idSecondary2paramIndexSet.size() != og.idSecondary2paramIndexSet.size() ) {
4190 public Set<HeapRegionNode> hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) {
4191 assert hrn1 != null;
4192 assert hrn2 != null;
4194 // then get the various tokens for these heap regions
4195 TokenTuple h1 = new TokenTuple(hrn1.getID(),
4196 !hrn1.isSingleObject(),
4197 TokenTuple.ARITY_ONE).makeCanonical();
4199 TokenTuple h1plus = new TokenTuple(hrn1.getID(),
4200 !hrn1.isSingleObject(),
4201 TokenTuple.ARITY_ONEORMORE).makeCanonical();
4203 TokenTuple h1star = new TokenTuple(hrn1.getID(),
4204 !hrn1.isSingleObject(),
4205 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
4207 TokenTuple h2 = new TokenTuple(hrn2.getID(),
4208 !hrn2.isSingleObject(),
4209 TokenTuple.ARITY_ONE).makeCanonical();
4211 TokenTuple h2plus = new TokenTuple(hrn2.getID(),
4212 !hrn2.isSingleObject(),
4213 TokenTuple.ARITY_ONEORMORE).makeCanonical();
4215 TokenTuple h2star = new TokenTuple(hrn2.getID(),
4216 !hrn2.isSingleObject(),
4217 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
4219 // then get the merged beta of all out-going edges from these heap regions
4220 ReachabilitySet beta1 = new ReachabilitySet().makeCanonical();
4221 Iterator<ReferenceEdge> itrEdge = hrn1.iteratorToReferencees();
4222 while( itrEdge.hasNext() ) {
4223 ReferenceEdge edge = itrEdge.next();
4224 beta1 = beta1.union( edge.getBeta() );
4227 ReachabilitySet beta2 = new ReachabilitySet().makeCanonical();
4228 itrEdge = hrn2.iteratorToReferencees();
4229 while( itrEdge.hasNext() ) {
4230 ReferenceEdge edge = itrEdge.next();
4231 beta2 = beta2.union( edge.getBeta() );
4234 boolean aliasDetected = false;
4236 // only do this one if they are different tokens
4238 beta1.containsTupleSetWithBoth(h1, h2) ) {
4239 aliasDetected = true;
4241 if( beta1.containsTupleSetWithBoth(h1plus, h2) ) {
4242 aliasDetected = true;
4244 if( beta1.containsTupleSetWithBoth(h1star, h2) ) {
4245 aliasDetected = true;
4247 if( beta1.containsTupleSetWithBoth(h1, h2plus) ) {
4248 aliasDetected = true;
4250 if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) {
4251 aliasDetected = true;
4253 if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) {
4254 aliasDetected = true;
4256 if( beta1.containsTupleSetWithBoth(h1, h2star) ) {
4257 aliasDetected = true;
4259 if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) {
4260 aliasDetected = true;
4262 if( beta1.containsTupleSetWithBoth(h1star, h2star) ) {
4263 aliasDetected = true;
4267 beta2.containsTupleSetWithBoth(h1, h2) ) {
4268 aliasDetected = true;
4270 if( beta2.containsTupleSetWithBoth(h1plus, h2) ) {
4271 aliasDetected = true;
4273 if( beta2.containsTupleSetWithBoth(h1star, h2) ) {
4274 aliasDetected = true;
4276 if( beta2.containsTupleSetWithBoth(h1, h2plus) ) {
4277 aliasDetected = true;
4279 if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) {
4280 aliasDetected = true;
4282 if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) {
4283 aliasDetected = true;
4285 if( beta2.containsTupleSetWithBoth(h1, h2star) ) {
4286 aliasDetected = true;
4288 if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) {
4289 aliasDetected = true;
4291 if( beta2.containsTupleSetWithBoth(h1star, h2star) ) {
4292 aliasDetected = true;
4295 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4296 if( aliasDetected ) {
4297 common = findCommonReachableNodes( hrn1, hrn2 );
4298 if( !(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP) ) {
4299 assert !common.isEmpty();
4307 public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
4309 // get parameter 1's heap regions
4310 assert paramIndex2idPrimary.containsKey(paramIndex1);
4311 Integer idParamPri1 = paramIndex2idPrimary.get(paramIndex1);
4313 assert id2hrn.containsKey(idParamPri1);
4314 HeapRegionNode hrnParamPri1 = id2hrn.get(idParamPri1);
4315 assert hrnParamPri1 != null;
4317 HeapRegionNode hrnParamSec1 = null;
4318 if( paramIndex2idSecondary.containsKey(paramIndex1) ) {
4319 Integer idParamSec1 = paramIndex2idSecondary.get(paramIndex1);
4321 assert id2hrn.containsKey(idParamSec1);
4322 hrnParamSec1 = id2hrn.get(idParamSec1);
4323 assert hrnParamSec1 != null;
4327 // get the other parameter
4328 assert paramIndex2idPrimary.containsKey(paramIndex2);
4329 Integer idParamPri2 = paramIndex2idPrimary.get(paramIndex2);
4331 assert id2hrn.containsKey(idParamPri2);
4332 HeapRegionNode hrnParamPri2 = id2hrn.get(idParamPri2);
4333 assert hrnParamPri2 != null;
4335 HeapRegionNode hrnParamSec2 = null;
4336 if( paramIndex2idSecondary.containsKey(paramIndex2) ) {
4337 Integer idParamSec2 = paramIndex2idSecondary.get(paramIndex2);
4339 assert id2hrn.containsKey(idParamSec2);
4340 hrnParamSec2 = id2hrn.get(idParamSec2);
4341 assert hrnParamSec2 != null;
4344 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4345 common.addAll( hasPotentialAlias( hrnParamPri1, hrnParamPri2 ) );
4347 if( hrnParamSec1 != null ) {
4348 common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamPri2 ) );
4351 if( hrnParamSec2 != null ) {
4352 common.addAll( hasPotentialAlias( hrnParamSec2, hrnParamPri1 ) );
4355 if( hrnParamSec1 != null && hrnParamSec2 != null ) {
4356 common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamSec2 ) );
4363 public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex, AllocationSite as) {
4365 // get parameter's heap regions
4366 assert paramIndex2idPrimary.containsKey(paramIndex);
4367 Integer idParamPri = paramIndex2idPrimary.get(paramIndex);
4369 assert id2hrn.containsKey(idParamPri);
4370 HeapRegionNode hrnParamPri = id2hrn.get(idParamPri);
4371 assert hrnParamPri != null;
4373 HeapRegionNode hrnParamSec = null;
4374 if( paramIndex2idSecondary.containsKey(paramIndex) ) {
4375 Integer idParamSec = paramIndex2idSecondary.get(paramIndex);
4377 assert id2hrn.containsKey(idParamSec);
4378 hrnParamSec = id2hrn.get(idParamSec);
4379 assert hrnParamSec != null;
4383 assert id2hrn.containsKey( as.getSummary() );
4384 HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() );
4385 assert hrnSummary != null;
4387 Set<HeapRegionNode> common = hasPotentialAlias( hrnParamPri, hrnSummary );
4389 if( hrnParamSec != null ) {
4390 common.addAll( hasPotentialAlias( hrnParamSec, hrnSummary ) );
4393 // check for other nodes
4394 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4396 assert id2hrn.containsKey( as.getIthOldest( i ) );
4397 HeapRegionNode hrnIthOldest = id2hrn.get( as.getIthOldest( i ) );
4398 assert hrnIthOldest != null;
4400 common = hasPotentialAlias( hrnParamPri, hrnIthOldest );
4402 if( hrnParamSec != null ) {
4403 common.addAll( hasPotentialAlias( hrnParamSec, hrnIthOldest ) );
4411 public Set<HeapRegionNode> hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
4413 // get summary node 1's alpha
4414 Integer idSum1 = as1.getSummary();
4415 assert id2hrn.containsKey(idSum1);
4416 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
4417 assert hrnSum1 != null;
4419 // get summary node 2's alpha
4420 Integer idSum2 = as2.getSummary();
4421 assert id2hrn.containsKey(idSum2);
4422 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
4423 assert hrnSum2 != null;
4425 Set<HeapRegionNode> common = hasPotentialAlias( hrnSum1, hrnSum2 );
4427 // check sum2 against alloc1 nodes
4428 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
4429 Integer idI1 = as1.getIthOldest(i);
4430 assert id2hrn.containsKey(idI1);
4431 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4432 assert hrnI1 != null;
4434 common.addAll( hasPotentialAlias( hrnI1, hrnSum2 ) );
4437 // check sum1 against alloc2 nodes
4438 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
4439 Integer idI2 = as2.getIthOldest(i);
4440 assert id2hrn.containsKey(idI2);
4441 HeapRegionNode hrnI2 = id2hrn.get(idI2);
4442 assert hrnI2 != null;
4444 common.addAll( hasPotentialAlias( hrnSum1, hrnI2 ) );
4446 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4447 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
4448 Integer idI1 = as1.getIthOldest(j);
4450 // if these are the same site, don't look for the same token, no alias.
4451 // different tokens of the same site could alias together though
4452 if( idI1.equals( idI2 ) ) {
4456 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4458 common.addAll( hasPotentialAlias( hrnI1, hrnI2 ) );
4466 public Set<HeapRegionNode> findCommonReachableNodes( HeapRegionNode hrn1,
4467 HeapRegionNode hrn2 ) {
4469 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
4470 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
4472 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
4473 todoNodes1.add( hrn1 );
4475 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
4476 todoNodes2.add( hrn2 );
4478 // follow links until all reachable nodes have been found
4479 while( !todoNodes1.isEmpty() ) {
4480 HeapRegionNode hrn = todoNodes1.iterator().next();
4481 todoNodes1.remove( hrn );
4482 reachableNodes1.add(hrn);
4484 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
4485 while( edgeItr.hasNext() ) {
4486 ReferenceEdge edge = edgeItr.next();
4488 if( !reachableNodes1.contains( edge.getDst() ) ) {
4489 todoNodes1.add( edge.getDst() );
4494 while( !todoNodes2.isEmpty() ) {
4495 HeapRegionNode hrn = todoNodes2.iterator().next();
4496 todoNodes2.remove( hrn );
4497 reachableNodes2.add(hrn);
4499 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
4500 while( edgeItr.hasNext() ) {
4501 ReferenceEdge edge = edgeItr.next();
4503 if( !reachableNodes2.contains( edge.getDst() ) ) {
4504 todoNodes2.add( edge.getDst() );
4509 Set<HeapRegionNode> intersection =
4510 new HashSet<HeapRegionNode>( reachableNodes1 );
4512 intersection.retainAll( reachableNodes2 );
4514 return intersection;
4518 public void writeGraph(String graphName,
4519 boolean writeLabels,
4520 boolean labelSelect,
4521 boolean pruneGarbage,
4522 boolean writeReferencers,
4523 boolean writeParamMappings,
4524 boolean hideSubsetReachability,
4525 boolean hideEdgeTaints
4526 ) throws java.io.IOException {
4528 // remove all non-word characters from the graph name so
4529 // the filename and identifier in dot don't cause errors
4530 graphName = graphName.replaceAll("[\\W]", "");
4532 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
4533 bw.write("digraph "+graphName+" {\n");
4535 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4537 // then visit every heap region node
4538 Set s = id2hrn.entrySet();
4539 Iterator i = s.iterator();
4540 while( i.hasNext() ) {
4541 Map.Entry me = (Map.Entry)i.next();
4542 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4544 if( !pruneGarbage ||
4545 (hrn.isFlagged() && hrn.getID() > 0) ||
4546 hrn.getDescription().startsWith("param")
4549 if( !visited.contains(hrn) ) {
4550 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4556 hideSubsetReachability,
4562 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4564 if( writeParamMappings ) {
4566 Set df = paramIndex2id.entrySet();
4567 Iterator ih = df.iterator();
4568 while( ih.hasNext() ) {
4569 Map.Entry meh = (Map.Entry)ih.next();
4570 Integer pi = (Integer) meh.getKey();
4571 Integer id = (Integer) meh.getValue();
4572 bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
4577 // then visit every label node, useful for debugging
4579 s = td2ln.entrySet();
4581 while( i.hasNext() ) {
4582 Map.Entry me = (Map.Entry)i.next();
4583 LabelNode ln = (LabelNode) me.getValue();
4586 String labelStr = ln.getTempDescriptorString();
4587 if( labelStr.startsWith("___temp") ||
4588 labelStr.startsWith("___dst") ||
4589 labelStr.startsWith("___srctmp") ||
4590 labelStr.startsWith("___neverused") ||
4591 labelStr.contains(qString) ||
4592 labelStr.contains(rString) ||
4593 labelStr.contains(blobString)
4599 //bw.write(" "+ln.toString() + ";\n");
4601 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
4602 while( heapRegionsItr.hasNext() ) {
4603 ReferenceEdge edge = heapRegionsItr.next();
4604 HeapRegionNode hrn = edge.getDst();
4606 if( pruneGarbage && !visited.contains(hrn) ) {
4607 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4613 hideSubsetReachability,
4617 bw.write(" " + ln.toString() +
4618 " -> " + hrn.toString() +
4619 "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
4631 protected void traverseHeapRegionNodes(int mode,
4635 HashSet<HeapRegionNode> visited,
4636 boolean writeReferencers,
4637 boolean hideSubsetReachability,
4638 boolean hideEdgeTaints
4639 ) throws java.io.IOException {
4641 if( visited.contains(hrn) ) {
4647 case VISIT_HRN_WRITE_FULL:
4649 String attributes = "[";
4651 if( hrn.isSingleObject() ) {
4652 attributes += "shape=box";
4654 attributes += "shape=Msquare";
4657 if( hrn.isFlagged() ) {
4658 attributes += ",style=filled,fillcolor=lightgrey";
4661 attributes += ",label=\"ID" +
4665 if( hrn.getType() != null ) {
4666 attributes += hrn.getType().toPrettyString() + "\\n";
4669 attributes += hrn.getDescription() +
4671 hrn.getAlphaString(hideSubsetReachability) +
4674 bw.write(" " + hrn.toString() + attributes + ";\n");
4679 // useful for debugging
4682 if( writeReferencers ) {
4683 OwnershipNode onRef = null;
4684 Iterator refItr = hrn.iteratorToReferencers();
4685 while( refItr.hasNext() ) {
4686 onRef = (OwnershipNode) refItr.next();
4689 case VISIT_HRN_WRITE_FULL:
4690 bw.write(" " + hrn.toString() +
4691 " -> " + onRef.toString() +
4692 "[color=lightgray];\n");
4699 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
4700 while( childRegionsItr.hasNext() ) {
4701 ReferenceEdge edge = childRegionsItr.next();
4702 HeapRegionNode hrnChild = edge.getDst();
4705 case VISIT_HRN_WRITE_FULL:
4706 bw.write(" " + hrn.toString() +
4707 " -> " + hrnChild.toString() +
4708 "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
4714 traverseHeapRegionNodes(mode,
4720 hideSubsetReachability,
4725 public int getTaintIdentifierFromHRN(HeapRegionNode hrn){
4726 HashSet<ReferenceEdge> referenceEdges=hrn.referencers;
4727 Iterator<ReferenceEdge> iter=referenceEdges.iterator();
4729 int taintIdentifier=0;
4730 while(iter.hasNext()){
4731 ReferenceEdge edge=iter.next();
4732 taintIdentifier=taintIdentifier | edge.getTaintIdentifier();
4735 return taintIdentifier;
4739 public void propagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet){
4741 HashSet<ReferenceEdge> setEdge=hrn.referencers;
4742 Iterator<ReferenceEdge> iter=setEdge.iterator();
4743 while(iter.hasNext()){
4744 ReferenceEdge edge= iter.next();
4745 edge.unionTaintIdentifier(newTaintIdentifier);
4746 if(edge.getSrc() instanceof HeapRegionNode){
4748 HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
4749 //check whether it is reflexive edge
4750 if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){
4751 visitedSet.add(refHRN);
4752 propagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);
4760 public void depropagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet){
4762 HashSet<ReferenceEdge> setEdge=hrn.referencers;
4763 Iterator<ReferenceEdge> iter=setEdge.iterator();
4764 while(iter.hasNext()){
4765 ReferenceEdge edge= iter.next();
4766 edge.minusTaintIdentifier(newTaintIdentifier);
4767 if(edge.getSrc() instanceof HeapRegionNode){
4769 HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
4770 //check whether it is reflexive edge
4771 if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){
4772 visitedSet.add(refHRN);
4773 depropagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);