1 package Analysis.OwnershipAnalysis;
5 import Util.UtilAlgorithms;
9 public class OwnershipGraph {
11 // use to disable improvements for comparison
12 protected static final boolean DISABLE_STRONG_UPDATES = false;
13 protected static final boolean DISABLE_GLOBAL_SWEEP = false;
15 protected static int allocationDepth = -1;
16 protected static TypeUtil typeUtil = null;
17 protected static boolean debugCallMap = false;
18 protected static int debugCallMapCount = 0;
19 protected static String debugCallee = null;
20 protected static String debugCaller = null;
22 // there was already one other very similar reason
23 // for traversing heap nodes that is no longer needed
24 // instead of writing a new heap region visitor, use
25 // the existing method with a new mode to describe what
26 // actions to take during the traversal
27 protected static final int VISIT_HRN_WRITE_FULL = 0;
29 protected static final String qString = new String( "Q_spec_" );
30 protected static final String rString = new String( "R_spec_" );
31 protected static final String blobString = new String( "_AliasBlob___" );
33 protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
34 protected static final TempDescriptor tdAliasBlob = new TempDescriptor( blobString );
36 protected static final TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
37 protected static final ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical();
38 protected static final ReachabilitySet rsWttsEmpty = new ReachabilitySet( ttsEmpty ).makeCanonical();
40 // add a bogus entry with the identity rule for easy rewrite
41 // of new callee nodes and edges, doesn't belong to any parameter
42 protected static final int bogusParamIndexInt = -2;
43 protected static final Integer bogusID = new Integer( bogusParamIndexInt );
44 protected static final Integer bogusIndex = new Integer( bogusParamIndexInt );
45 protected static final TokenTuple bogusToken = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONE ).makeCanonical();
46 protected static final TokenTuple bogusTokenPlus = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONEORMORE ).makeCanonical();
47 protected static final TokenTuple bogusTokenStar = new TokenTuple( bogusID, true, TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
48 protected static final ReachabilitySet rsIdentity =
49 new ReachabilitySet( new TokenTupleSet( bogusToken ).makeCanonical() ).makeCanonical();
52 public Hashtable<Integer, HeapRegionNode> id2hrn;
53 public Hashtable<TempDescriptor, LabelNode > td2ln;
55 public Hashtable<Integer, Set<Integer> > idPrimary2paramIndexSet;
56 public Hashtable<Integer, Integer > paramIndex2idPrimary;
58 public Hashtable<Integer, Set<Integer> > idSecondary2paramIndexSet;
59 public Hashtable<Integer, Integer > paramIndex2idSecondary;
61 public Hashtable<Integer, TempDescriptor> paramIndex2tdQ;
62 public Hashtable<Integer, TempDescriptor> paramIndex2tdR;
65 public HashSet<AllocationSite> allocationSites;
68 public Hashtable<TokenTuple, Integer> paramTokenPrimary2paramIndex;
69 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenPrimary;
71 public Hashtable<TokenTuple, Integer> paramTokenSecondary2paramIndex;
72 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondary;
73 public Hashtable<TokenTuple, Integer> paramTokenSecondaryPlus2paramIndex;
74 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondaryPlus;
75 public Hashtable<TokenTuple, Integer> paramTokenSecondaryStar2paramIndex;
76 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondaryStar;
79 // consult these sets in algorithms when considering what
80 // to do with temps or their label nodes found in the graph
81 public Set<TempDescriptor> outOfScopeTemps;
82 public Set<LabelNode> outOfScopeLabels;
83 public Set<TempDescriptor> parameterTemps;
84 public Set<LabelNode> parameterLabels;
86 // this is kept to allow edges created from variables (a src and dst)
87 // to know the access paths that allowed it, to prune edges when
88 // mapping them back into the caller--an access path must appear
89 public Hashtable< TempDescriptor, Set<AccessPath> > temp2accessPaths;
93 public OwnershipGraph() {
95 id2hrn = new Hashtable<Integer, HeapRegionNode>();
96 td2ln = new Hashtable<TempDescriptor, LabelNode >();
97 idPrimary2paramIndexSet = new Hashtable<Integer, Set<Integer> >();
98 paramIndex2idPrimary = new Hashtable<Integer, Integer >();
99 idSecondary2paramIndexSet = new Hashtable<Integer, Set<Integer> >();
100 paramIndex2idSecondary = new Hashtable<Integer, Integer >();
101 paramIndex2tdQ = new Hashtable<Integer, TempDescriptor>();
102 paramIndex2tdR = new Hashtable<Integer, TempDescriptor>();
104 paramTokenPrimary2paramIndex = new Hashtable<TokenTuple, Integer >();
105 paramIndex2paramTokenPrimary = new Hashtable<Integer, TokenTuple >();
107 paramTokenSecondary2paramIndex = new Hashtable<TokenTuple, Integer >();
108 paramIndex2paramTokenSecondary = new Hashtable<Integer, TokenTuple >();
109 paramTokenSecondaryPlus2paramIndex = new Hashtable<TokenTuple, Integer >();
110 paramIndex2paramTokenSecondaryPlus = new Hashtable<Integer, TokenTuple >();
111 paramTokenSecondaryStar2paramIndex = new Hashtable<TokenTuple, Integer >();
112 paramIndex2paramTokenSecondaryStar = new Hashtable<Integer, TokenTuple >();
114 allocationSites = new HashSet <AllocationSite>();
116 outOfScopeTemps = new HashSet<TempDescriptor>();
117 outOfScopeLabels = new HashSet<LabelNode>();
118 parameterTemps = new HashSet<TempDescriptor>();
119 parameterLabels = new HashSet<LabelNode>();
121 outOfScopeTemps.add( tdReturn );
122 outOfScopeLabels.add( getLabelNodeFromTemp( tdReturn ) );
124 temp2accessPaths = new Hashtable< TempDescriptor, Set<AccessPath> >();
128 // label nodes are much easier to deal with than
129 // heap region nodes. Whenever there is a request
130 // for the label node that is associated with a
131 // temp descriptor we can either find it or make a
132 // new one and return it. This is because temp
133 // descriptors are globally unique and every label
134 // node is mapped to exactly one temp descriptor.
135 protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
138 if( !td2ln.containsKey(td) ) {
139 td2ln.put(td, new LabelNode(td) );
142 return td2ln.get(td);
146 // the reason for this method is to have the option
147 // creating new heap regions with specific IDs, or
148 // duplicating heap regions with specific IDs (especially
149 // in the merge() operation) or to create new heap
150 // regions with a new unique ID.
151 protected HeapRegionNode
152 createNewHeapRegionNode(Integer id,
153 boolean isSingleObject,
154 boolean isNewSummary,
158 AllocationSite allocSite,
159 ReachabilitySet alpha,
160 String description) {
162 boolean markForAnalysis = isFlagged || isParameter;
164 TypeDescriptor typeToUse = null;
165 if( allocSite != null ) {
166 typeToUse = allocSite.getType();
171 if( allocSite != null && allocSite.getDisjointId() != null ) {
172 markForAnalysis = true;
176 id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
179 if( alpha == null ) {
180 if( markForAnalysis ) {
181 alpha = new ReachabilitySet(
188 alpha = new ReachabilitySet(
189 new TokenTupleSet().makeCanonical()
194 HeapRegionNode hrn = new HeapRegionNode(id,
209 ////////////////////////////////////////////////
211 // Low-level referencee and referencer methods
213 // These methods provide the lowest level for
214 // creating references between ownership nodes
215 // and handling the details of maintaining both
216 // list of referencers and referencees.
218 ////////////////////////////////////////////////
219 protected void addReferenceEdge(OwnershipNode referencer,
220 HeapRegionNode referencee,
221 ReferenceEdge edge) {
222 assert referencer != null;
223 assert referencee != null;
225 assert edge.getSrc() == referencer;
226 assert edge.getDst() == referencee;
228 referencer.addReferencee(edge);
229 referencee.addReferencer(edge);
232 protected void removeReferenceEdge(OwnershipNode referencer,
233 HeapRegionNode referencee,
236 assert referencer != null;
237 assert referencee != null;
239 ReferenceEdge edge = referencer.getReferenceTo(referencee,
243 assert edge == referencee.getReferenceFrom(referencer,
247 // int oldTaint=edge.getTaintIdentifier();
248 // if(referencer instanceof HeapRegionNode){
249 // depropagateTaintIdentifier((HeapRegionNode)referencer,oldTaint,new HashSet<HeapRegionNode>());
252 referencer.removeReferencee(edge);
253 referencee.removeReferencer(edge);
256 protected void clearReferenceEdgesFrom(OwnershipNode referencer,
260 assert referencer != null;
262 // get a copy of the set to iterate over, otherwise
263 // we will be trying to take apart the set as we
264 // are iterating over it, which won't work
265 Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
266 while( i.hasNext() ) {
267 ReferenceEdge edge = i.next();
270 (edge.typeEquals( type ) && edge.fieldEquals( field ))
273 HeapRegionNode referencee = edge.getDst();
275 removeReferenceEdge(referencer,
283 protected void clearReferenceEdgesTo(HeapRegionNode referencee,
287 assert referencee != null;
289 // get a copy of the set to iterate over, otherwise
290 // we will be trying to take apart the set as we
291 // are iterating over it, which won't work
292 Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
293 while( i.hasNext() ) {
294 ReferenceEdge edge = i.next();
297 (edge.typeEquals( type ) && edge.fieldEquals( field ))
300 OwnershipNode referencer = edge.getSrc();
302 removeReferenceEdge(referencer,
311 ////////////////////////////////////////////////////
313 // Assignment Operation Methods
315 // These methods are high-level operations for
316 // modeling program assignment statements using
317 // the low-level reference create/remove methods
320 // The destination in an assignment statement is
321 // going to have new references. The method of
322 // determining the references depends on the type
323 // of the FlatNode assignment and the predicates
324 // of the nodes and edges involved.
326 ////////////////////////////////////////////////////
328 public void nullifyDeadVars( Set<TempDescriptor> liveIn ) {
330 // make a set of the temps that are out of scope, don't
331 // consider them when nullifying dead in-scope variables
332 Set<TempDescriptor> outOfScope = new HashSet<TempDescriptor>();
333 outOfScope.add( tdReturn );
334 outOfScope.add( tdAliasBlob );
335 outOfScope.addAll( paramIndex2tdQ.values() );
336 outOfScope.addAll( paramIndex2tdR.values() );
338 Iterator varItr = td2ln.entrySet().iterator();
339 while( varItr.hasNext() ) {
340 Map.Entry me = (Map.Entry) varItr.next();
341 TempDescriptor td = (TempDescriptor) me.getKey();
342 LabelNode ln = (LabelNode) me.getValue();
344 // if this variable is not out-of-scope or live
345 // in graph, nullify its references to anything
346 if( !outOfScope.contains( td ) &&
347 !liveIn.contains( td )
349 clearReferenceEdgesFrom( ln, null, null, true );
355 public void assignTempXEqualToTempY(TempDescriptor x,
357 assignTypedTempXEqualToTempY( x, y, null );
361 public void assignTypedTempXEqualToTempY(TempDescriptor x,
363 TypeDescriptor type) {
365 LabelNode lnX = getLabelNodeFromTemp(x);
366 LabelNode lnY = getLabelNodeFromTemp(y);
368 clearReferenceEdgesFrom(lnX, null, null, true);
370 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
371 while( itrYhrn.hasNext() ) {
372 ReferenceEdge edgeY = itrYhrn.next();
373 HeapRegionNode referencee = edgeY.getDst();
374 ReferenceEdge edgeNew = edgeY.copy();
375 edgeNew.setSrc( lnX );
378 edgeNew.setType( type );
379 edgeNew.setField( null );
382 addReferenceEdge(lnX, referencee, edgeNew);
387 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
390 LabelNode lnX = getLabelNodeFromTemp(x);
391 LabelNode lnY = getLabelNodeFromTemp(y);
393 clearReferenceEdgesFrom(lnX, null, null, true);
395 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
396 while( itrYhrn.hasNext() ) {
397 ReferenceEdge edgeY = itrYhrn.next();
398 HeapRegionNode hrnY = edgeY.getDst();
399 ReachabilitySet betaY = edgeY.getBeta();
401 Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
402 while( itrHrnFhrn.hasNext() ) {
403 ReferenceEdge edgeHrn = itrHrnFhrn.next();
404 HeapRegionNode hrnHrn = edgeHrn.getDst();
405 ReachabilitySet betaHrn = edgeHrn.getBeta();
407 if( edgeHrn.getType() == null ||
408 (edgeHrn.getType() .equals( f.getType() ) &&
409 edgeHrn.getField().equals( f.getSymbol() ) )
412 ReferenceEdge edgeNew = new ReferenceEdge(lnX,
417 betaY.intersection(betaHrn) );
419 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnHrn);
420 edgeNew.setTaintIdentifier(newTaintIdentifier);
422 addReferenceEdge(lnX, hrnHrn, edgeNew);
429 public void assignTempXFieldFEqualToTempY(TempDescriptor x,
432 LabelNode lnX = getLabelNodeFromTemp(x);
433 LabelNode lnY = getLabelNodeFromTemp(y);
435 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
436 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
438 // first look for possible strong updates and remove those edges
439 boolean strongUpdate = false;
441 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
442 while( itrXhrn.hasNext() ) {
443 ReferenceEdge edgeX = itrXhrn.next();
444 HeapRegionNode hrnX = edgeX.getDst();
446 // we can do a strong update here if one of two cases holds
448 f != OwnershipAnalysis.getArrayField( f.getType() ) &&
449 ( (hrnX.getNumReferencers() == 1) || // case 1
450 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
453 if( !DISABLE_STRONG_UPDATES ) {
455 clearReferenceEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
460 // then do all token propagation
461 itrXhrn = lnX.iteratorToReferencees();
462 while( itrXhrn.hasNext() ) {
463 ReferenceEdge edgeX = itrXhrn.next();
464 HeapRegionNode hrnX = edgeX.getDst();
465 ReachabilitySet betaX = edgeX.getBeta();
467 ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
469 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
470 while( itrYhrn.hasNext() ) {
471 ReferenceEdge edgeY = itrYhrn.next();
472 HeapRegionNode hrnY = edgeY.getDst();
473 ReachabilitySet O = edgeY.getBeta();
476 // propagate tokens over nodes starting from hrnSrc, and it will
477 // take care of propagating back up edges from any touched nodes
478 ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
479 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
482 // then propagate back just up the edges from hrn
483 ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
484 HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
486 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
487 new Hashtable<ReferenceEdge, ChangeTupleSet>();
489 Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
490 while( referItr.hasNext() ) {
491 ReferenceEdge edgeUpstream = referItr.next();
492 todoEdges.add(edgeUpstream);
493 edgePlannedChanges.put(edgeUpstream, Cx);
496 propagateTokensOverEdges(todoEdges,
503 // apply the updates to reachability
504 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
505 while( nodeItr.hasNext() ) {
506 nodeItr.next().applyAlphaNew();
509 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
510 while( edgeItr.hasNext() ) {
511 edgeItr.next().applyBetaNew();
515 // then go back through and add the new edges
516 itrXhrn = lnX.iteratorToReferencees();
517 while( itrXhrn.hasNext() ) {
518 ReferenceEdge edgeX = itrXhrn.next();
519 HeapRegionNode hrnX = edgeX.getDst();
521 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
522 while( itrYhrn.hasNext() ) {
523 ReferenceEdge edgeY = itrYhrn.next();
524 HeapRegionNode hrnY = edgeY.getDst();
526 // prepare the new reference edge hrnX.f -> hrnY
527 ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
532 edgeY.getBeta().pruneBy( hrnX.getAlpha() )
535 // look to see if an edge with same field exists
536 // and merge with it, otherwise just add the edge
537 ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY,
541 if( edgeExisting != null ) {
542 edgeExisting.setBeta(
543 edgeExisting.getBeta().union( edgeNew.getBeta() )
545 if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){
546 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY);
547 edgeExisting.unionTaintIdentifier(newTaintIdentifier);
549 // a new edge here cannot be reflexive, so existing will
550 // always be also not reflexive anymore
551 edgeExisting.setIsInitialParam( false );
554 if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){
555 int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY);
556 edgeNew.setTaintIdentifier(newTaintIdentifier);
558 //currently, taint isn't propagated through the chain of refrences
559 //propagateTaintIdentifier(hrnX,newTaintIdentifier,new HashSet<HeapRegionNode>());
560 addReferenceEdge( hrnX, hrnY, edgeNew );
565 // if there was a strong update, make sure to improve
566 // reachability with a global sweep
568 if( !DISABLE_GLOBAL_SWEEP ) {
575 // the parameter model is to use a single-object heap region
576 // for the primary parameter, and a multiple-object heap
577 // region for the secondary objects reachable through the
578 // primary object, if necessary
579 public void assignTempEqualToParamAlloc( TempDescriptor td,
581 Integer paramIndex ) {
584 TypeDescriptor typeParam = td.getType();
585 assert typeParam != null;
587 // either the parameter is an array or a class to be in this method
588 assert typeParam.isArray() || typeParam.isClass();
590 // discover some info from the param type and use it below
591 // to get parameter model as precise as we can
592 boolean createSecondaryRegion = false;
593 Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
594 Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
596 // there might be an element reference for array types
597 if( typeParam.isArray() ) {
598 // only bother with this if the dereferenced type can
599 // affect reachability
600 TypeDescriptor typeDeref = typeParam.dereference();
601 if( !typeDeref.isImmutable() || typeDeref.isArray() ) {
602 primary2secondaryFields.add(
603 OwnershipAnalysis.getArrayField( typeDeref )
605 createSecondaryRegion = true;
607 // also handle a special case where an array of objects
608 // can point back to the array, which is an object!
609 if( typeParam.toPrettyString().equals( "Object[]" ) &&
610 typeDeref.toPrettyString().equals( "Object" ) ) {
612 primary2primaryFields.add(
613 OwnershipAnalysis.getArrayField( typeDeref )
619 // there might be member references for class types
620 if( typeParam.isClass() ) {
621 ClassDescriptor cd = typeParam.getClassDesc();
622 while( cd != null ) {
624 Iterator fieldItr = cd.getFields();
625 while( fieldItr.hasNext() ) {
627 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
628 TypeDescriptor typeField = fd.getType();
629 assert typeField != null;
631 if( !typeField.isImmutable() || typeField.isArray() ) {
632 primary2secondaryFields.add( fd );
633 createSecondaryRegion = true;
636 if( typeUtil.isSuperorType( typeField, typeParam ) ) {
637 primary2primaryFields.add( fd );
641 cd = cd.getSuperDesc();
646 // now build everything we need
647 LabelNode lnParam = getLabelNodeFromTemp( td );
648 HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
649 true, // single object?
652 true, // is a parameter?
654 null, // allocation site
655 null, // reachability set
656 "param"+paramIndex+" obj" );
658 parameterTemps.add( td );
659 parameterLabels.add( lnParam );
662 // this is a non-program-accessible label that picks up beta
663 // info to be used for fixing a caller of this method
664 TempDescriptor tdParamQ = new TempDescriptor( td+qString );
665 paramIndex2tdQ.put( paramIndex, tdParamQ );
666 LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
668 outOfScopeTemps.add( tdParamQ );
669 outOfScopeLabels.add( lnParamQ );
671 // keep track of heap regions that were created for
672 // parameter labels, the index of the parameter they
673 // are for is important when resolving method calls
674 Integer newPrimaryID = hrnPrimary.getID();
675 assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
676 Set<Integer> s = new HashSet<Integer>();
678 idPrimary2paramIndexSet.put( newPrimaryID, s );
679 paramIndex2idPrimary.put( paramIndex, newPrimaryID );
681 TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
682 false, // multi-object
683 TokenTuple.ARITY_ONE ).makeCanonical();
686 HeapRegionNode hrnSecondary = null;
687 Integer newSecondaryID = null;
688 TokenTuple ttSecondary = null;
689 TempDescriptor tdParamR = null;
690 LabelNode lnParamR = null;
692 if( createSecondaryRegion ) {
693 tdParamR = new TempDescriptor( td+rString );
694 paramIndex2tdR.put( paramIndex, tdParamR );
695 lnParamR = getLabelNodeFromTemp( tdParamR );
697 outOfScopeTemps.add( tdParamR );
698 outOfScopeLabels.add( lnParamR );
700 hrnSecondary = createNewHeapRegionNode( null, // id or null to generate a new one
701 false, // single object?
704 true, // is a parameter?
706 null, // allocation site
707 null, // reachability set
708 "param"+paramIndex+" reachable" );
710 newSecondaryID = hrnSecondary.getID();
711 assert !idSecondary2paramIndexSet.containsKey( newSecondaryID );
712 Set<Integer> s2 = new HashSet<Integer>();
713 s2.add( paramIndex );
714 idSecondary2paramIndexSet.put( newSecondaryID, s2 );
715 paramIndex2idSecondary.put( paramIndex, newSecondaryID );
718 ttSecondary = new TokenTuple( newSecondaryID,
719 true, // multi-object
720 TokenTuple.ARITY_ONE ).makeCanonical();
723 // use a beta that has everything and put it all over the
724 // parameter model, then use a global sweep later to fix
725 // it up, since parameters can have different shapes
726 TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
727 ReachabilitySet betaSoup;
728 if( createSecondaryRegion ) {
729 TokenTupleSet tts1 = new TokenTupleSet( ttSecondary ).makeCanonical();
730 TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttSecondary );
731 betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 );
733 betaSoup = ReachabilitySet.factory( tts0 );
736 ReferenceEdge edgeFromLabel =
737 new ReferenceEdge( lnParam, // src
741 false, // special param initial (not needed on label->node)
742 betaSoup ); // reachability
743 edgeFromLabel.tainedBy(paramIndex);
744 addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
746 ReferenceEdge edgeFromLabelQ =
747 new ReferenceEdge( lnParamQ, // src
751 false, // special param initial (not needed on label->node)
752 betaSoup ); // reachability
753 edgeFromLabelQ.tainedBy(paramIndex);
754 addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
756 ReferenceEdge edgeSecondaryReflexive;
757 if( createSecondaryRegion ) {
758 edgeSecondaryReflexive =
759 new ReferenceEdge( hrnSecondary, // src
761 null, // match all types
762 null, // match all fields
763 true, // special param initial
764 betaSoup ); // reachability
765 addReferenceEdge( hrnSecondary, hrnSecondary, edgeSecondaryReflexive );
767 ReferenceEdge edgeSecondary2Primary =
768 new ReferenceEdge( hrnSecondary, // src
770 null, // match all types
771 null, // match all fields
772 true, // special param initial
773 betaSoup ); // reachability
774 addReferenceEdge( hrnSecondary, hrnPrimary, edgeSecondary2Primary );
776 ReferenceEdge edgeFromLabelR =
777 new ReferenceEdge( lnParamR, // src
781 false, // special param initial (not needed on label->node)
782 betaSoup ); // reachability
783 edgeFromLabelR.tainedBy(paramIndex);
784 addReferenceEdge( lnParamR, hrnSecondary, edgeFromLabelR );
787 Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
788 while( fieldItr.hasNext() ) {
789 FieldDescriptor fd = fieldItr.next();
791 ReferenceEdge edgePrimaryReflexive =
792 new ReferenceEdge( hrnPrimary, // src
794 fd.getType(), // type
795 fd.getSymbol(), // field
796 true, // special param initial
797 betaSoup ); // reachability
798 addReferenceEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive );
801 fieldItr = primary2secondaryFields.iterator();
802 while( fieldItr.hasNext() ) {
803 FieldDescriptor fd = fieldItr.next();
805 ReferenceEdge edgePrimary2Secondary =
806 new ReferenceEdge( hrnPrimary, // src
808 fd.getType(), // type
809 fd.getSymbol(), // field
810 true, // special param initial
811 betaSoup ); // reachability
812 addReferenceEdge( hrnPrimary, hrnSecondary, edgePrimary2Secondary );
817 public void makeAliasedParamHeapRegionNode() {
819 LabelNode lnBlob = getLabelNodeFromTemp( tdAliasBlob );
821 outOfScopeTemps.add( tdAliasBlob );
822 outOfScopeLabels.add( lnBlob );
824 HeapRegionNode hrn = createNewHeapRegionNode( null, // id or null to generate a new one
825 false, // single object?
828 true, // is a parameter?
830 null, // allocation site
831 null, // reachability set
835 ReachabilitySet beta = new ReachabilitySet( new TokenTuple( hrn.getID(),
837 TokenTuple.ARITY_ONE).makeCanonical()
840 ReferenceEdge edgeFromLabel =
841 new ReferenceEdge( lnBlob, hrn, null, null, false, beta );
843 ReferenceEdge edgeReflexive =
844 new ReferenceEdge( hrn, hrn, null, null, true, beta );
846 addReferenceEdge( lnBlob, hrn, edgeFromLabel );
847 addReferenceEdge( hrn, hrn, edgeReflexive );
851 public void assignTempEqualToAliasedParam( TempDescriptor tdParam,
852 Integer paramIndex ) {
853 assert tdParam != null;
855 TypeDescriptor typeParam = tdParam.getType();
856 assert typeParam != null;
858 LabelNode lnParam = getLabelNodeFromTemp( tdParam );
859 LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob );
861 parameterTemps.add( tdParam );
862 parameterLabels.add( lnParam );
864 // this is a non-program-accessible label that picks up beta
865 // info to be used for fixing a caller of this method
866 TempDescriptor tdParamQ = new TempDescriptor( tdParam+qString );
867 TempDescriptor tdParamR = new TempDescriptor( tdParam+rString );
869 paramIndex2tdQ.put( paramIndex, tdParamQ );
870 paramIndex2tdR.put( paramIndex, tdParamR );
872 LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
873 LabelNode lnParamR = getLabelNodeFromTemp( tdParamR );
875 outOfScopeTemps.add( tdParamR );
876 outOfScopeLabels.add( lnParamR );
877 outOfScopeTemps.add( tdParamQ );
878 outOfScopeLabels.add( lnParamQ );
880 // the lnAliased should always only reference one node, and that
881 // heap region node is the aliased param blob
882 assert lnAliased.getNumReferencees() == 1;
883 HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
884 Integer idAliased = hrnAliasBlob.getID();
887 TokenTuple ttAliased = new TokenTuple( idAliased,
888 true, // multi-object
889 TokenTuple.ARITY_ONE ).makeCanonical();
892 HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
893 true, // single object?
896 true, // is a parameter?
898 null, // allocation site
899 null, // reachability set
900 "param"+paramIndex+" obj" );
902 Integer newPrimaryID = hrnPrimary.getID();
903 assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
904 Set<Integer> s1 = new HashSet<Integer>();
905 s1.add( paramIndex );
906 idPrimary2paramIndexSet.put( newPrimaryID, s1 );
907 paramIndex2idPrimary.put( paramIndex, newPrimaryID );
909 Set<Integer> s2 = idSecondary2paramIndexSet.get( idAliased );
911 s2 = new HashSet<Integer>();
913 s2.add( paramIndex );
914 idSecondary2paramIndexSet.put( idAliased, s2 );
915 paramIndex2idSecondary.put( paramIndex, idAliased );
919 TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
920 false, // multi-object
921 TokenTuple.ARITY_ONE ).makeCanonical();
924 TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
925 TokenTupleSet tts1 = new TokenTupleSet( ttAliased ).makeCanonical();
926 TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttAliased );
927 ReachabilitySet betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 );
930 ReferenceEdge edgeFromLabel =
931 new ReferenceEdge( lnParam, // src
935 false, // special param initial (not needed on label->node)
936 betaSoup ); // reachability
937 edgeFromLabel.tainedBy(paramIndex);
938 addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
940 ReferenceEdge edgeFromLabelQ =
941 new ReferenceEdge( lnParamQ, // src
945 false, // special param initial (not needed on label->node)
946 betaSoup ); // reachability
947 edgeFromLabelQ.tainedBy(paramIndex);
948 addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
950 ReferenceEdge edgeAliased2Primary =
951 new ReferenceEdge( hrnAliasBlob, // src
953 null, // match all types
954 null, // match all fields
955 true, // special param initial
956 betaSoup ); // reachability
957 addReferenceEdge( hrnAliasBlob, hrnPrimary, edgeAliased2Primary );
959 ReferenceEdge edgeFromLabelR =
960 new ReferenceEdge( lnParamR, // src
964 false, // special param initial (not needed on label->node)
965 betaSoup ); // reachability
966 edgeFromLabelR.tainedBy(paramIndex);
967 addReferenceEdge( lnParamR, hrnAliasBlob, edgeFromLabelR );
971 public void addParam2ParamAliasEdges( FlatMethod fm,
972 Set<Integer> aliasedParamIndices ) {
974 LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob );
976 // the lnAliased should always only reference one node, and that
977 // heap region node is the aliased param blob
978 assert lnAliased.getNumReferencees() == 1;
979 HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
980 Integer idAliased = hrnAliasBlob.getID();
983 TokenTuple ttAliased = new TokenTuple( idAliased,
984 true, // multi-object
985 TokenTuple.ARITY_ONE ).makeCanonical();
988 Iterator<Integer> apItrI = aliasedParamIndices.iterator();
989 while( apItrI.hasNext() ) {
990 Integer i = apItrI.next();
991 TempDescriptor tdParamI = fm.getParameter( i );
992 TypeDescriptor typeI = tdParamI.getType();
993 LabelNode lnParamI = getLabelNodeFromTemp( tdParamI );
995 Integer idPrimaryI = paramIndex2idPrimary.get( i );
996 assert idPrimaryI != null;
997 HeapRegionNode primaryI = id2hrn.get( idPrimaryI );
998 assert primaryI != null;
1000 TokenTuple ttPrimaryI = new TokenTuple( idPrimaryI,
1001 false, // multi-object
1002 TokenTuple.ARITY_ONE ).makeCanonical();
1004 TokenTupleSet ttsI = new TokenTupleSet( ttPrimaryI ).makeCanonical();
1005 TokenTupleSet ttsA = new TokenTupleSet( ttAliased ).makeCanonical();
1006 TokenTupleSet ttsIA = new TokenTupleSet( ttPrimaryI ).makeCanonical().union( ttAliased );
1007 ReachabilitySet betaSoup = ReachabilitySet.factory( ttsI ).union( ttsA ).union( ttsIA );
1010 // calculate whether fields of this aliased parameter are able to
1011 // reference its own primary object, the blob, or other parameter's
1013 Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
1014 Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
1016 // there might be an element reference for array types
1017 if( typeI.isArray() ) {
1018 // only bother with this if the dereferenced type can
1019 // affect reachability
1020 TypeDescriptor typeDeref = typeI.dereference();
1024 /////////////////////////////////////////////////////////////
1025 // NOTE! For the KMeans benchmark a parameter of type float
1026 // array, which has an immutable dereferenced type, is causing
1027 // this assertion to fail. I'm commenting it out for now which
1028 // is safe, because it allows aliasing where no aliasing can occur,
1029 // so it can only get a worse-but-not-wrong answer. FIX!
1030 /////////////////////////////////////////////////////////////
1031 // for this parameter to be aliased the following must be true
1032 //assert !typeDeref.isImmutable() || typeDeref.isArray();
1036 primary2secondaryFields.add(
1037 OwnershipAnalysis.getArrayField( typeDeref )
1040 // also handle a special case where an array of objects
1041 // can point back to the array, which is an object!
1042 if( typeI .toPrettyString().equals( "Object[]" ) &&
1043 typeDeref.toPrettyString().equals( "Object" ) ) {
1044 primary2primaryFields.add(
1045 OwnershipAnalysis.getArrayField( typeDeref )
1050 // there might be member references for class types
1051 if( typeI.isClass() ) {
1052 ClassDescriptor cd = typeI.getClassDesc();
1053 while( cd != null ) {
1055 Iterator fieldItr = cd.getFields();
1056 while( fieldItr.hasNext() ) {
1058 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
1059 TypeDescriptor typeField = fd.getType();
1060 assert typeField != null;
1062 if( !typeField.isImmutable() || typeField.isArray() ) {
1063 primary2secondaryFields.add( fd );
1066 if( typeUtil.isSuperorType( typeField, typeI ) ) {
1067 primary2primaryFields.add( fd );
1071 cd = cd.getSuperDesc();
1075 Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
1076 while( fieldItr.hasNext() ) {
1077 FieldDescriptor fd = fieldItr.next();
1079 ReferenceEdge edgePrimaryReflexive =
1080 new ReferenceEdge( primaryI, // src
1082 fd.getType(), // type
1083 fd.getSymbol(), // field
1084 true, // special param initial
1085 betaSoup ); // reachability
1086 addReferenceEdge( primaryI, primaryI, edgePrimaryReflexive );
1089 fieldItr = primary2secondaryFields.iterator();
1090 while( fieldItr.hasNext() ) {
1091 FieldDescriptor fd = fieldItr.next();
1092 TypeDescriptor typeField = fd.getType();
1093 assert typeField != null;
1095 ReferenceEdge edgePrimary2Secondary =
1096 new ReferenceEdge( primaryI, // src
1097 hrnAliasBlob, // dst
1098 fd.getType(), // type
1099 fd.getSymbol(), // field
1100 true, // special param initial
1101 betaSoup ); // reachability
1102 addReferenceEdge( primaryI, hrnAliasBlob, edgePrimary2Secondary );
1104 // ask whether these fields might match any of the other aliased
1105 // parameters and make those edges too
1106 Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
1107 while( apItrJ.hasNext() ) {
1108 Integer j = apItrJ.next();
1109 TempDescriptor tdParamJ = fm.getParameter( j );
1110 TypeDescriptor typeJ = tdParamJ.getType();
1112 if( !i.equals( j ) && typeUtil.isSuperorType( typeField, typeJ ) ) {
1114 Integer idPrimaryJ = paramIndex2idPrimary.get( j );
1115 assert idPrimaryJ != null;
1116 HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
1117 assert primaryJ != null;
1119 TokenTuple ttPrimaryJ = new TokenTuple( idPrimaryJ,
1120 false, // multi-object
1121 TokenTuple.ARITY_ONE ).makeCanonical();
1123 TokenTupleSet ttsJ = new TokenTupleSet( ttPrimaryJ ).makeCanonical();
1124 TokenTupleSet ttsIJ = ttsI.union( ttsJ );
1125 TokenTupleSet ttsAJ = ttsA.union( ttsJ );
1126 TokenTupleSet ttsIAJ = ttsIA.union( ttsJ );
1127 ReachabilitySet betaSoupWJ = ReachabilitySet.factory( ttsJ ).union( ttsIJ ).union( ttsAJ ).union( ttsIAJ );
1129 ReferenceEdge edgePrimaryI2PrimaryJ =
1130 new ReferenceEdge( primaryI, // src
1132 fd.getType(), // type
1133 fd.getSymbol(), // field
1134 true, // special param initial
1135 betaSoupWJ ); // reachability
1136 addReferenceEdge( primaryI, primaryJ, edgePrimaryI2PrimaryJ );
1142 // look at whether aliased parameters i and j can
1143 // possibly be the same primary object, add edges
1144 Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
1145 while( apItrJ.hasNext() ) {
1146 Integer j = apItrJ.next();
1147 TempDescriptor tdParamJ = fm.getParameter( j );
1148 TypeDescriptor typeJ = tdParamJ.getType();
1149 LabelNode lnParamJ = getLabelNodeFromTemp( tdParamJ );
1151 if( !i.equals( j ) && typeUtil.isSuperorType( typeI, typeJ ) ) {
1153 Integer idPrimaryJ = paramIndex2idPrimary.get( j );
1154 assert idPrimaryJ != null;
1155 HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
1156 assert primaryJ != null;
1158 ReferenceEdge lnJ2PrimaryJ = lnParamJ.getReferenceTo( primaryJ,
1161 assert lnJ2PrimaryJ != null;
1163 ReferenceEdge lnI2PrimaryJ = lnJ2PrimaryJ.copy();
1164 lnI2PrimaryJ.setSrc( lnParamI );
1165 lnI2PrimaryJ.setType( tdParamI.getType() );
1166 lnI2PrimaryJ.tainedBy(new Integer(j));
1167 addReferenceEdge( lnParamI, primaryJ, lnI2PrimaryJ );
1173 public void prepareParamTokenMaps( FlatMethod fm ) {
1175 // always add the bogus mappings that are used to
1176 // rewrite "with respect to no parameter"
1177 paramTokenPrimary2paramIndex.put( bogusToken, bogusIndex );
1178 paramIndex2paramTokenPrimary.put( bogusIndex, bogusToken );
1180 paramTokenSecondary2paramIndex.put( bogusToken, bogusIndex );
1181 paramIndex2paramTokenSecondary.put( bogusIndex, bogusToken );
1182 paramTokenSecondaryPlus2paramIndex.put( bogusTokenPlus, bogusIndex );
1183 paramIndex2paramTokenSecondaryPlus.put( bogusIndex, bogusTokenPlus );
1184 paramTokenSecondaryStar2paramIndex.put( bogusTokenStar, bogusIndex );
1185 paramIndex2paramTokenSecondaryStar.put( bogusIndex, bogusTokenStar );
1187 for( int i = 0; i < fm.numParameters(); ++i ) {
1188 Integer paramIndex = new Integer( i );
1190 // immutable objects have no primary regions
1191 if( paramIndex2idPrimary.containsKey( paramIndex ) ) {
1192 Integer idPrimary = paramIndex2idPrimary.get( paramIndex );
1194 assert id2hrn.containsKey( idPrimary );
1195 HeapRegionNode hrnPrimary = id2hrn.get( idPrimary );
1197 TokenTuple p_i = new TokenTuple( hrnPrimary.getID(),
1198 false, // multiple-object?
1199 TokenTuple.ARITY_ONE ).makeCanonical();
1200 paramTokenPrimary2paramIndex.put( p_i, paramIndex );
1201 paramIndex2paramTokenPrimary.put( paramIndex, p_i );
1204 // any parameter object, by type, may have no secondary region
1205 if( paramIndex2idSecondary.containsKey( paramIndex ) ) {
1206 Integer idSecondary = paramIndex2idSecondary.get( paramIndex );
1208 assert id2hrn.containsKey( idSecondary );
1209 HeapRegionNode hrnSecondary = id2hrn.get( idSecondary );
1211 TokenTuple s_i = new TokenTuple( hrnSecondary.getID(),
1212 true, // multiple-object?
1213 TokenTuple.ARITY_ONE ).makeCanonical();
1214 paramTokenSecondary2paramIndex.put( s_i, paramIndex );
1215 paramIndex2paramTokenSecondary.put( paramIndex, s_i );
1217 TokenTuple s_i_plus = new TokenTuple( hrnSecondary.getID(),
1218 true, // multiple-object?
1219 TokenTuple.ARITY_ONEORMORE ).makeCanonical();
1220 paramTokenSecondaryPlus2paramIndex.put( s_i_plus, paramIndex );
1221 paramIndex2paramTokenSecondaryPlus.put( paramIndex, s_i_plus );
1223 TokenTuple s_i_star = new TokenTuple( hrnSecondary.getID(),
1224 true, // multiple-object?
1225 TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
1226 paramTokenSecondaryStar2paramIndex.put( s_i_star, paramIndex );
1227 paramIndex2paramTokenSecondaryStar.put( paramIndex, s_i_star );
1234 public void assignReturnEqualToTemp(TempDescriptor x) {
1236 LabelNode lnR = getLabelNodeFromTemp(tdReturn);
1237 LabelNode lnX = getLabelNodeFromTemp(x);
1239 clearReferenceEdgesFrom(lnR, null, null, true);
1241 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
1242 while( itrXhrn.hasNext() ) {
1243 ReferenceEdge edgeX = itrXhrn.next();
1244 HeapRegionNode referencee = edgeX.getDst();
1245 ReferenceEdge edgeNew = edgeX.copy();
1246 edgeNew.setSrc(lnR);
1248 addReferenceEdge(lnR, referencee, edgeNew);
1253 public void assignTempEqualToNewAlloc(TempDescriptor x,
1254 AllocationSite as) {
1260 // after the age operation the newest (or zero-ith oldest)
1261 // node associated with the allocation site should have
1262 // no references to it as if it were a newly allocated
1264 Integer idNewest = as.getIthOldest( 0 );
1265 HeapRegionNode hrnNewest = id2hrn.get( idNewest );
1266 assert hrnNewest != null;
1268 LabelNode lnX = getLabelNodeFromTemp( x );
1269 clearReferenceEdgesFrom( lnX, null, null, true );
1271 // make a new reference to allocated node
1272 TypeDescriptor type = as.getType();
1273 ReferenceEdge edgeNew =
1274 new ReferenceEdge( lnX, // source
1278 false, // is initial param
1279 hrnNewest.getAlpha() // beta
1282 addReferenceEdge( lnX, hrnNewest, edgeNew );
1286 // use the allocation site (unique to entire analysis) to
1287 // locate the heap region nodes in this ownership graph
1288 // that should be aged. The process models the allocation
1289 // of new objects and collects all the oldest allocations
1290 // in a summary node to allow for a finite analysis
1292 // There is an additional property of this method. After
1293 // running it on a particular ownership graph (many graphs
1294 // may have heap regions related to the same allocation site)
1295 // the heap region node objects in this ownership graph will be
1296 // allocated. Therefore, after aging a graph for an allocation
1297 // site, attempts to retrieve the heap region nodes using the
1298 // integer id's contained in the allocation site should always
1299 // return non-null heap regions.
1300 public void age(AllocationSite as) {
1302 // aging adds this allocation site to the graph's
1303 // list of sites that exist in the graph, or does
1304 // nothing if the site is already in the list
1305 allocationSites.add(as);
1307 // get the summary node for the allocation site in the context
1308 // of this particular ownership graph
1309 HeapRegionNode hrnSummary = getSummaryNode(as);
1311 // merge oldest node into summary
1312 Integer idK = as.getOldest();
1313 HeapRegionNode hrnK = id2hrn.get(idK);
1314 mergeIntoSummary(hrnK, hrnSummary);
1316 // move down the line of heap region nodes
1317 // clobbering the ith and transferring all references
1318 // to and from i-1 to node i. Note that this clobbers
1319 // the oldest node (hrnK) that was just merged into
1321 for( int i = allocationDepth - 1; i > 0; --i ) {
1323 // move references from the i-1 oldest to the ith oldest
1324 Integer idIth = as.getIthOldest(i);
1325 HeapRegionNode hrnI = id2hrn.get(idIth);
1326 Integer idImin1th = as.getIthOldest(i - 1);
1327 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
1329 transferOnto(hrnImin1, hrnI);
1332 // as stated above, the newest node should have had its
1333 // references moved over to the second oldest, so we wipe newest
1334 // in preparation for being the new object to assign something to
1335 Integer id0th = as.getIthOldest(0);
1336 HeapRegionNode hrn0 = id2hrn.get(id0th);
1337 assert hrn0 != null;
1339 // clear all references in and out of newest node
1340 clearReferenceEdgesFrom(hrn0, null, null, true);
1341 clearReferenceEdgesTo(hrn0, null, null, true);
1344 // now tokens in reachability sets need to "age" also
1345 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1346 while( itrAllLabelNodes.hasNext() ) {
1347 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1348 LabelNode ln = (LabelNode) me.getValue();
1350 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1351 while( itrEdges.hasNext() ) {
1352 ageTokens(as, itrEdges.next() );
1356 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1357 while( itrAllHRNodes.hasNext() ) {
1358 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1359 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1361 ageTokens(as, hrnToAge);
1363 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1364 while( itrEdges.hasNext() ) {
1365 ageTokens(as, itrEdges.next() );
1370 // after tokens have been aged, reset newest node's reachability
1371 if( hrn0.isFlagged() ) {
1372 hrn0.setAlpha(new ReachabilitySet(
1374 new TokenTuple(hrn0).makeCanonical()
1379 hrn0.setAlpha(new ReachabilitySet(
1380 new TokenTupleSet().makeCanonical()
1387 protected HeapRegionNode getSummaryNode(AllocationSite as) {
1389 Integer idSummary = as.getSummary();
1390 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
1392 // If this is null then we haven't touched this allocation site
1393 // in the context of the current ownership graph, so allocate
1394 // heap region nodes appropriate for the entire allocation site.
1395 // This should only happen once per ownership graph per allocation site,
1396 // and a particular integer id can be used to locate the heap region
1397 // in different ownership graphs that represents the same part of an
1399 if( hrnSummary == null ) {
1401 boolean hasFlags = false;
1402 if( as.getType().isClass() ) {
1403 hasFlags = as.getType().getClassDesc().hasFlags();
1407 hasFlags=as.getFlag();
1410 hrnSummary = createNewHeapRegionNode(idSummary, // id or null to generate a new one
1411 false, // single object?
1413 hasFlags, // flagged?
1414 false, // is a parameter?
1415 as.getType(), // type
1416 as, // allocation site
1417 null, // reachability set
1418 as.toStringForDOT() + "\\nsummary");
1420 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1421 Integer idIth = as.getIthOldest(i);
1422 assert !id2hrn.containsKey(idIth);
1423 createNewHeapRegionNode(idIth, // id or null to generate a new one
1424 true, // single object?
1426 hasFlags, // flagged?
1427 false, // is a parameter?
1428 as.getType(), // type
1429 as, // allocation site
1430 null, // reachability set
1431 as.toStringForDOT() + "\\n" + i + " oldest");
1439 protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
1441 Integer idShadowSummary = as.getSummaryShadow();
1442 HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
1444 if( hrnShadowSummary == null ) {
1446 boolean hasFlags = false;
1447 if( as.getType().isClass() ) {
1448 hasFlags = as.getType().getClassDesc().hasFlags();
1451 hrnShadowSummary = createNewHeapRegionNode(idShadowSummary, // id or null to generate a new one
1452 false, // single object?
1454 hasFlags, // flagged?
1455 false, // is a parameter?
1456 as.getType(), // type
1457 as, // allocation site
1458 null, // reachability set
1459 as + "\\n" + as.getType() + "\\nshadowSum");
1461 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1462 Integer idShadowIth = as.getIthOldestShadow(i);
1463 assert !id2hrn.containsKey(idShadowIth);
1464 createNewHeapRegionNode(idShadowIth, // id or null to generate a new one
1465 true, // single object?
1467 hasFlags, // flagged?
1468 false, // is a parameter?
1469 as.getType(), // type
1470 as, // allocation site
1471 null, // reachability set
1472 as + "\\n" + as.getType() + "\\n" + i + " shadow");
1476 return hrnShadowSummary;
1480 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
1481 assert hrnSummary.isNewSummary();
1483 // transfer references _from_ hrn over to hrnSummary
1484 Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
1485 while( itrReferencee.hasNext() ) {
1486 ReferenceEdge edge = itrReferencee.next();
1487 ReferenceEdge edgeMerged = edge.copy();
1488 edgeMerged.setSrc(hrnSummary);
1490 HeapRegionNode hrnReferencee = edge.getDst();
1491 ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee,
1495 if( edgeSummary == null ) {
1496 // the merge is trivial, nothing to be done
1498 // otherwise an edge from the referencer to hrnSummary exists already
1499 // and the edge referencer->hrn should be merged with it
1500 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1503 addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
1506 // next transfer references _to_ hrn over to hrnSummary
1507 Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
1508 while( itrReferencer.hasNext() ) {
1509 ReferenceEdge edge = itrReferencer.next();
1510 ReferenceEdge edgeMerged = edge.copy();
1511 edgeMerged.setDst(hrnSummary);
1513 OwnershipNode onReferencer = edge.getSrc();
1514 ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary,
1518 if( edgeSummary == null ) {
1519 // the merge is trivial, nothing to be done
1521 // otherwise an edge from the referencer to alpha_S exists already
1522 // and the edge referencer->alpha_K should be merged with it
1523 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1526 addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
1529 // then merge hrn reachability into hrnSummary
1530 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
1534 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
1536 // clear references in and out of node b
1537 clearReferenceEdgesFrom(hrnB, null, null, true);
1538 clearReferenceEdgesTo(hrnB, null, null, true);
1540 // copy each edge in and out of A to B
1541 Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
1542 while( itrReferencee.hasNext() ) {
1543 ReferenceEdge edge = itrReferencee.next();
1544 HeapRegionNode hrnReferencee = edge.getDst();
1545 ReferenceEdge edgeNew = edge.copy();
1546 edgeNew.setSrc(hrnB);
1548 addReferenceEdge(hrnB, hrnReferencee, edgeNew);
1551 Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
1552 while( itrReferencer.hasNext() ) {
1553 ReferenceEdge edge = itrReferencer.next();
1554 OwnershipNode onReferencer = edge.getSrc();
1555 ReferenceEdge edgeNew = edge.copy();
1556 edgeNew.setDst(hrnB);
1558 addReferenceEdge(onReferencer, hrnB, edgeNew);
1561 // replace hrnB reachability with hrnA's
1562 hrnB.setAlpha(hrnA.getAlpha() );
1566 protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
1567 edge.setBeta(edge.getBeta().ageTokens(as) );
1570 protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
1571 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
1576 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1578 HashSet<HeapRegionNode> nodesWithNewAlpha,
1579 HashSet<ReferenceEdge> edgesWithNewBeta) {
1581 HashSet<HeapRegionNode> todoNodes
1582 = new HashSet<HeapRegionNode>();
1583 todoNodes.add(nPrime);
1585 HashSet<ReferenceEdge> todoEdges
1586 = new HashSet<ReferenceEdge>();
1588 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
1589 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
1590 nodePlannedChanges.put(nPrime, c0);
1592 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
1593 = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1595 // first propagate change sets everywhere they can go
1596 while( !todoNodes.isEmpty() ) {
1597 HeapRegionNode n = todoNodes.iterator().next();
1598 ChangeTupleSet C = nodePlannedChanges.get(n);
1600 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
1601 while( referItr.hasNext() ) {
1602 ReferenceEdge edge = referItr.next();
1603 todoEdges.add(edge);
1605 if( !edgePlannedChanges.containsKey(edge) ) {
1606 edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
1609 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
1612 Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
1613 while( refeeItr.hasNext() ) {
1614 ReferenceEdge edgeF = refeeItr.next();
1615 HeapRegionNode m = edgeF.getDst();
1617 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
1619 Iterator<ChangeTuple> itrCprime = C.iterator();
1620 while( itrCprime.hasNext() ) {
1621 ChangeTuple c = itrCprime.next();
1622 if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
1623 changesToPass = changesToPass.union(c);
1627 if( !changesToPass.isEmpty() ) {
1628 if( !nodePlannedChanges.containsKey(m) ) {
1629 nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
1632 ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
1634 if( !changesToPass.isSubset(currentChanges) ) {
1636 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
1642 todoNodes.remove(n);
1645 // then apply all of the changes for each node at once
1646 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1647 while( itrMap.hasNext() ) {
1648 Map.Entry me = (Map.Entry) itrMap.next();
1649 HeapRegionNode n = (HeapRegionNode) me.getKey();
1650 ChangeTupleSet C = (ChangeTupleSet) me.getValue();
1652 // this propagation step is with respect to one change,
1653 // so we capture the full change from the old alpha:
1654 ReachabilitySet localDelta = n.getAlpha().applyChangeSet( C, true );
1656 // but this propagation may be only one of many concurrent
1657 // possible changes, so keep a running union with the node's
1658 // partially updated new alpha set
1659 n.setAlphaNew( n.getAlphaNew().union( localDelta ) );
1661 nodesWithNewAlpha.add( n );
1664 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
1668 protected void propagateTokensOverEdges(
1669 HashSet<ReferenceEdge> todoEdges,
1670 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
1671 HashSet<ReferenceEdge> edgesWithNewBeta) {
1673 // first propagate all change tuples everywhere they can go
1674 while( !todoEdges.isEmpty() ) {
1675 ReferenceEdge edgeE = todoEdges.iterator().next();
1676 todoEdges.remove(edgeE);
1678 if( !edgePlannedChanges.containsKey(edgeE) ) {
1679 edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
1682 ChangeTupleSet C = edgePlannedChanges.get(edgeE);
1684 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
1686 Iterator<ChangeTuple> itrC = C.iterator();
1687 while( itrC.hasNext() ) {
1688 ChangeTuple c = itrC.next();
1689 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1690 changesToPass = changesToPass.union(c);
1694 OwnershipNode onSrc = edgeE.getSrc();
1696 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
1697 HeapRegionNode n = (HeapRegionNode) onSrc;
1699 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
1700 while( referItr.hasNext() ) {
1701 ReferenceEdge edgeF = referItr.next();
1703 if( !edgePlannedChanges.containsKey(edgeF) ) {
1704 edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
1707 ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
1709 if( !changesToPass.isSubset(currentChanges) ) {
1710 todoEdges.add(edgeF);
1711 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
1717 // then apply all of the changes for each edge at once
1718 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1719 while( itrMap.hasNext() ) {
1720 Map.Entry me = (Map.Entry) itrMap.next();
1721 ReferenceEdge e = (ReferenceEdge) me.getKey();
1722 ChangeTupleSet C = (ChangeTupleSet) me.getValue();
1724 // this propagation step is with respect to one change,
1725 // so we capture the full change from the old beta:
1726 ReachabilitySet localDelta = e.getBeta().applyChangeSet( C, true );
1728 // but this propagation may be only one of many concurrent
1729 // possible changes, so keep a running union with the edge's
1730 // partially updated new beta set
1731 e.setBetaNew( e.getBetaNew().union( localDelta ) );
1733 edgesWithNewBeta.add( e );
1738 public Set<Integer> calculateAliasedParamSet( FlatCall fc,
1742 Hashtable<Integer, LabelNode> paramIndex2ln =
1743 new Hashtable<Integer, LabelNode>();
1745 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
1746 new Hashtable<Integer, HashSet<HeapRegionNode> >();
1748 for( int i = 0; i < fm.numParameters(); ++i ) {
1749 Integer paramIndex = new Integer( i );
1750 TempDescriptor tdParam = fm.getParameter( i );
1751 TypeDescriptor typeParam = tdParam.getType();
1753 if( typeParam.isImmutable() && !typeParam.isArray() ) {
1754 // don't bother with this primitive parameter, it
1755 // cannot affect reachability
1759 // now depending on whether the callee is static or not
1760 // we need to account for a "this" argument in order to
1761 // find the matching argument in the caller context
1762 TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, paramIndex );
1764 LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1765 paramIndex2ln.put(paramIndex, argLabel_i);
1768 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1769 while( lnArgItr.hasNext() ) {
1770 Map.Entry me = (Map.Entry)lnArgItr.next();
1771 Integer index = (Integer) me.getKey();
1772 LabelNode lnArg_i = (LabelNode) me.getValue();
1774 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1775 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1777 // to find all reachable nodes, start with label referencees
1778 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1779 while( edgeArgItr.hasNext() ) {
1780 ReferenceEdge edge = edgeArgItr.next();
1781 todoNodes.add( edge.getDst() );
1784 // then follow links until all reachable nodes have been found
1785 while( !todoNodes.isEmpty() ) {
1786 HeapRegionNode hrn = todoNodes.iterator().next();
1787 todoNodes.remove(hrn);
1788 reachableNodes.add(hrn);
1790 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1791 while( edgeItr.hasNext() ) {
1792 ReferenceEdge edge = edgeItr.next();
1794 if( !reachableNodes.contains(edge.getDst() ) ) {
1795 todoNodes.add(edge.getDst() );
1801 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1804 Set<Integer> aliasedIndices = new HashSet<Integer>();
1806 // check for arguments that are aliased
1807 for( int i = 0; i < fm.numParameters(); ++i ) {
1808 for( int j = 0; j < i; ++j ) {
1809 HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
1810 HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
1812 // some parameters are immutable or primitive, so skip em
1813 if( s1 == null || s2 == null ) {
1817 Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
1818 intersection.retainAll(s2);
1820 if( !intersection.isEmpty() ) {
1821 aliasedIndices.add( new Integer( i ) );
1822 aliasedIndices.add( new Integer( j ) );
1827 return aliasedIndices;
1831 private String makeMapKey( Integer i, Integer j, String field ) {
1832 return i+","+j+","+field;
1835 private String makeMapKey( Integer i, String field ) {
1839 // these hashtables are used during the mapping procedure to say that
1840 // with respect to some argument i there is an edge placed into some
1841 // category for mapping with respect to another argument index j
1842 // so the key into the hashtable is i, the value is a two-element vector
1843 // that contains in 0 the edge and in 1 the Integer index j
1844 private void ensureEmptyEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
1847 Set<Vector> ei = edge_index_pairs.get( indexI );
1849 ei = new HashSet<Vector>();
1851 edge_index_pairs.put( indexI, ei );
1854 private void addEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
1859 Vector v = new Vector(); v.setSize( 2 );
1861 v.set( 1 , indexJ );
1862 Set<Vector> ei = edge_index_pairs.get( indexI );
1864 ei = new HashSet<Vector>();
1867 edge_index_pairs.put( indexI, ei );
1870 private ReachabilitySet funcScriptR( ReachabilitySet rsIn,
1871 OwnershipGraph ogCallee,
1872 MethodContext mc ) {
1874 ReachabilitySet rsOut = new ReachabilitySet( rsIn );
1876 Iterator itr = ogCallee.paramIndex2paramTokenPrimary.entrySet().iterator();
1877 while( itr.hasNext() ) {
1878 Map.Entry me = (Map.Entry) itr.next();
1879 Integer i = (Integer) me.getKey();
1880 TokenTuple p_i = (TokenTuple) me.getValue();
1881 TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( i );
1883 // skip this if there is no secondary token or the parameter
1884 // is part of the aliasing context
1885 if( s_i == null || mc.getAliasedParamIndices().contains( i ) ) {
1889 rsOut = rsOut.removeTokenAIfTokenB( p_i, s_i );
1895 // detects strong updates to the primary parameter object and
1896 // effects the removal of old edges in the calling graph
1897 private void effectCalleeStrongUpdates( Integer paramIndex,
1898 OwnershipGraph ogCallee,
1899 HeapRegionNode hrnCaller
1901 Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
1902 assert idPrimary != null;
1904 HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
1905 assert hrnPrimary != null;
1907 TypeDescriptor typeParam = hrnPrimary.getType();
1908 assert typeParam.isClass();
1910 Set<String> fieldNamesToRemove = new HashSet<String>();
1912 ClassDescriptor cd = typeParam.getClassDesc();
1913 while( cd != null ) {
1915 Iterator fieldItr = cd.getFields();
1916 while( fieldItr.hasNext() ) {
1918 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
1919 TypeDescriptor typeField = fd.getType();
1920 assert typeField != null;
1922 if( ogCallee.hasFieldBeenUpdated( hrnPrimary, fd.getSymbol() ) ) {
1923 clearReferenceEdgesFrom( hrnCaller, fd.getType(), fd.getSymbol(), false );
1927 cd = cd.getSuperDesc();
1931 private boolean hasFieldBeenUpdated( HeapRegionNode hrnPrimary, String field ) {
1933 Iterator<ReferenceEdge> itr = hrnPrimary.iteratorToReferencees();
1934 while( itr.hasNext() ) {
1935 ReferenceEdge e = itr.next();
1936 if( e.fieldEquals( field ) && e.isInitialParam() ) {
1944 // resolveMethodCall() is used to incorporate a callee graph's effects into
1945 // *this* graph, which is the caller. This method can also be used, after
1946 // the entire analysis is complete, to perform parameter decomposition for
1947 // a given call chain.
1948 public void resolveMethodCall(FlatCall fc, // call site in caller method
1949 boolean isStatic, // whether it is a static method
1950 FlatMethod fm, // the callee method (when virtual, can be many)
1951 OwnershipGraph ogCallee, // the callee's current ownership graph
1952 MethodContext mc, // the aliasing context for this call
1953 ParameterDecomposition pd // if this is not null, we're calling after analysis
1957 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
1958 fm.getMethod().getSymbol().equals( debugCallee )
1962 writeGraph("debug1BeforeCall",
1963 true, // write labels (variables)
1964 true, // selectively hide intermediate temp vars
1965 true, // prune unreachable heap regions
1966 false, // show back edges to confirm graph validity
1967 false, // show parameter indices (unmaintained!)
1968 true, // hide subset reachability states
1969 true); // hide edge taints
1971 ogCallee.writeGraph("debug0Callee",
1972 true, // write labels (variables)
1973 true, // selectively hide intermediate temp vars
1974 true, // prune unreachable heap regions
1975 false, // show back edges to confirm graph validity
1976 false, // show parameter indices (unmaintained!)
1977 true, // hide subset reachability states
1978 true); // hide edge taints
1979 } catch( IOException e ) {}
1981 System.out.println( " "+mc+" is calling "+fm );
1986 // define rewrite rules and other structures to organize data by parameter/argument index
1987 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_p = new Hashtable<Integer, ReachabilitySet>();
1988 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_s = new Hashtable<Integer, ReachabilitySet>();
1990 Hashtable<String, ReachabilitySet> paramIndex2rewriteJ_p2p = new Hashtable<String, ReachabilitySet>(); // select( i, j, f )
1991 Hashtable<String, ReachabilitySet> paramIndex2rewriteJ_p2s = new Hashtable<String, ReachabilitySet>(); // select( i, f )
1992 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2p = new Hashtable<Integer, ReachabilitySet>();
1993 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2s = new Hashtable<Integer, ReachabilitySet>();
1995 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p = new Hashtable<Integer, ReachabilitySet>();
1996 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p2 = new Hashtable<Integer, ReachabilitySet>();
1997 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_s = new Hashtable<Integer, ReachabilitySet>();
1999 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_p = new Hashtable<Integer, ReachabilitySet>();
2000 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_s = new Hashtable<Integer, ReachabilitySet>();
2002 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD = new Hashtable<Integer, ReachabilitySet>();
2005 Hashtable<Integer, LabelNode> paramIndex2ln = new Hashtable<Integer, LabelNode>();
2008 paramIndex2rewriteH_p.put( bogusIndex, rsIdentity );
2009 paramIndex2rewriteH_s.put( bogusIndex, rsIdentity );
2011 paramIndex2rewriteJ_p2p.put( bogusIndex.toString(), rsIdentity );
2012 paramIndex2rewriteJ_p2s.put( bogusIndex.toString(), rsIdentity );
2013 paramIndex2rewriteJ_s2p.put( bogusIndex, rsIdentity );
2014 paramIndex2rewriteJ_s2s.put( bogusIndex, rsIdentity );
2017 for( int i = 0; i < fm.numParameters(); ++i ) {
2018 Integer paramIndex = new Integer(i);
2020 if( !ogCallee.paramIndex2idPrimary.containsKey( paramIndex ) ) {
2021 // skip this immutable parameter
2025 // setup H (primary)
2026 Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
2027 assert ogCallee.id2hrn.containsKey( idPrimary );
2028 HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
2029 assert hrnPrimary != null;
2030 paramIndex2rewriteH_p.put( paramIndex, toShadowTokens( ogCallee, hrnPrimary.getAlpha() ) );
2032 // setup J (primary->X)
2033 Iterator<ReferenceEdge> p2xItr = hrnPrimary.iteratorToReferencees();
2034 while( p2xItr.hasNext() ) {
2035 ReferenceEdge p2xEdge = p2xItr.next();
2037 // we only care about initial parameter edges here
2038 if( !p2xEdge.isInitialParam() ) { continue; }
2040 HeapRegionNode hrnDst = p2xEdge.getDst();
2042 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
2043 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
2044 while( jItr.hasNext() ) {
2045 Integer j = jItr.next();
2046 paramIndex2rewriteJ_p2p.put( makeMapKey( i, j, p2xEdge.getField() ),
2047 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
2051 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
2052 paramIndex2rewriteJ_p2s.put( makeMapKey( i, p2xEdge.getField() ),
2053 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
2057 // setup K (primary)
2058 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
2059 assert tdParamQ != null;
2060 LabelNode lnParamQ = ogCallee.td2ln.get( tdParamQ );
2061 assert lnParamQ != null;
2062 ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnPrimary, null, null );
2063 assert edgeSpecialQ_i != null;
2064 ReachabilitySet qBeta = toShadowTokens( ogCallee, edgeSpecialQ_i.getBeta() );
2066 TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary .get( paramIndex );
2067 TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( paramIndex );
2069 ReachabilitySet K_p = new ReachabilitySet().makeCanonical();
2070 ReachabilitySet K_p2 = new ReachabilitySet().makeCanonical();
2074 // sort qBeta into K_p1 and K_p2
2075 Iterator<TokenTupleSet> ttsItr = qBeta.iterator();
2076 while( ttsItr.hasNext() ) {
2077 TokenTupleSet tts = ttsItr.next();
2078 if( s_i != null && tts.containsBoth( p_i, s_i ) ) {
2079 K_p2 = K_p2.union( tts );
2081 K_p = K_p.union( tts );
2085 paramIndex2rewriteK_p .put( paramIndex, K_p );
2086 paramIndex2rewriteK_p2.put( paramIndex, K_p2 );
2089 // if there is a secondary node, compute the rest of the rewrite rules
2090 if( ogCallee.paramIndex2idSecondary.containsKey( paramIndex ) ) {
2092 // setup H (secondary)
2093 Integer idSecondary = ogCallee.paramIndex2idSecondary.get( paramIndex );
2094 assert ogCallee.id2hrn.containsKey( idSecondary );
2095 HeapRegionNode hrnSecondary = ogCallee.id2hrn.get( idSecondary );
2096 assert hrnSecondary != null;
2097 paramIndex2rewriteH_s.put( paramIndex, toShadowTokens( ogCallee, hrnSecondary.getAlpha() ) );
2099 // setup J (secondary->X)
2100 Iterator<ReferenceEdge> s2xItr = hrnSecondary.iteratorToReferencees();
2101 while( s2xItr.hasNext() ) {
2102 ReferenceEdge s2xEdge = s2xItr.next();
2104 if( !s2xEdge.isInitialParam() ) { continue; }
2106 HeapRegionNode hrnDst = s2xEdge.getDst();
2108 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
2109 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
2110 while( jItr.hasNext() ) {
2111 Integer j = jItr.next();
2112 paramIndex2rewriteJ_s2p.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
2116 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
2117 paramIndex2rewriteJ_s2s.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
2121 // setup K (secondary)
2122 TempDescriptor tdParamR = ogCallee.paramIndex2tdR.get( paramIndex );
2123 assert tdParamR != null;
2124 LabelNode lnParamR = ogCallee.td2ln.get( tdParamR );
2125 assert lnParamR != null;
2126 ReferenceEdge edgeSpecialR_i = lnParamR.getReferenceTo( hrnSecondary, null, null );
2127 assert edgeSpecialR_i != null;
2128 paramIndex2rewriteK_s.put( paramIndex,
2129 toShadowTokens( ogCallee, edgeSpecialR_i.getBeta() ) );
2133 // now depending on whether the callee is static or not
2134 // we need to account for a "this" argument in order to
2135 // find the matching argument in the caller context
2136 TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, paramIndex );
2138 // remember which caller arg label maps to param index
2139 LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i );
2140 paramIndex2ln.put( paramIndex, argLabel_i );
2142 // do a callee-effect strong update pre-pass here
2143 if( argTemp_i.getType().isClass() ) {
2145 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
2146 while( edgeItr.hasNext() ) {
2147 ReferenceEdge edge = edgeItr.next();
2148 HeapRegionNode hrn = edge.getDst();
2150 if( (hrn.getNumReferencers() == 1) || // case 1
2151 (hrn.isSingleObject() && argLabel_i.getNumReferencees() == 1) // case 2
2153 if( !DISABLE_STRONG_UPDATES ) {
2154 effectCalleeStrongUpdates( paramIndex, ogCallee, hrn );
2160 // then calculate the d and D rewrite rules
2161 ReachabilitySet d_i_p = new ReachabilitySet().makeCanonical();
2162 ReachabilitySet d_i_s = new ReachabilitySet().makeCanonical();
2163 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
2164 while( edgeItr.hasNext() ) {
2165 ReferenceEdge edge = edgeItr.next();
2167 d_i_p = d_i_p.union( edge.getBeta().intersection( edge.getDst().getAlpha() ) );
2168 d_i_s = d_i_s.union( edge.getBeta() );
2170 paramIndex2rewrite_d_p.put( paramIndex, d_i_p );
2171 paramIndex2rewrite_d_s.put( paramIndex, d_i_s );
2173 // TODO: we should only do this when we need it, and then
2174 // memoize it for the rest of the mapping procedure
2175 ReachabilitySet D_i = d_i_s.exhaustiveArityCombinations();
2176 paramIndex2rewriteD.put( paramIndex, D_i );
2180 // with respect to each argument, map parameter effects into caller
2181 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
2182 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
2184 Hashtable<Integer, Set<HeapRegionNode> > pi2dr =
2185 new Hashtable<Integer, Set<HeapRegionNode> >();
2187 Hashtable<Integer, Set<HeapRegionNode> > pi2r =
2188 new Hashtable<Integer, Set<HeapRegionNode> >();
2190 Set<HeapRegionNode> defParamObj = new HashSet<HeapRegionNode>();
2192 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
2193 while( lnArgItr.hasNext() ) {
2194 Map.Entry me = (Map.Entry) lnArgItr.next();
2195 Integer index = (Integer) me.getKey();
2196 LabelNode lnArg_i = (LabelNode) me.getValue();
2198 Set<HeapRegionNode> dr = new HashSet<HeapRegionNode>();
2199 Set<HeapRegionNode> r = new HashSet<HeapRegionNode>();
2200 Set<HeapRegionNode> todo = new HashSet<HeapRegionNode>();
2202 // find all reachable nodes starting with label referencees
2203 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
2204 while( edgeArgItr.hasNext() ) {
2205 ReferenceEdge edge = edgeArgItr.next();
2206 HeapRegionNode hrn = edge.getDst();
2210 if( lnArg_i.getNumReferencees() == 1 && hrn.isSingleObject() ) {
2211 defParamObj.add( hrn );
2214 Iterator<ReferenceEdge> edgeHrnItr = hrn.iteratorToReferencees();
2215 while( edgeHrnItr.hasNext() ) {
2216 ReferenceEdge edger = edgeHrnItr.next();
2217 todo.add( edger.getDst() );
2220 // then follow links until all reachable nodes have been found
2221 while( !todo.isEmpty() ) {
2222 HeapRegionNode hrnr = todo.iterator().next();
2223 todo.remove( hrnr );
2227 Iterator<ReferenceEdge> edgeItr = hrnr.iteratorToReferencees();
2228 while( edgeItr.hasNext() ) {
2229 ReferenceEdge edger = edgeItr.next();
2230 if( !r.contains( edger.getDst() ) ) {
2231 todo.add( edger.getDst() );
2236 if( hrn.isSingleObject() ) {
2241 pi2dr.put( index, dr );
2242 pi2r .put( index, r );
2245 assert defParamObj.size() <= fm.numParameters();
2247 // if we're in parameter decomposition mode, report some results here
2251 // report primary parameter object mappings
2252 mapItr = pi2dr.entrySet().iterator();
2253 while( mapItr.hasNext() ) {
2254 Map.Entry me = (Map.Entry) mapItr.next();
2255 Integer paramIndex = (Integer) me.getKey();
2256 Set<HeapRegionNode> hrnAset = (Set<HeapRegionNode>) me.getValue();
2258 Iterator<HeapRegionNode> hrnItr = hrnAset.iterator();
2259 while( hrnItr.hasNext() ) {
2260 HeapRegionNode hrnA = hrnItr.next();
2261 pd.mapRegionToParamObject( hrnA, paramIndex );
2265 // report parameter-reachable mappings
2266 mapItr = pi2r.entrySet().iterator();
2267 while( mapItr.hasNext() ) {
2268 Map.Entry me = (Map.Entry) mapItr.next();
2269 Integer paramIndex = (Integer) me.getKey();
2270 Set<HeapRegionNode> hrnRset = (Set<HeapRegionNode>) me.getValue();
2272 Iterator<HeapRegionNode> hrnItr = hrnRset.iterator();
2273 while( hrnItr.hasNext() ) {
2274 HeapRegionNode hrnR = hrnItr.next();
2275 pd.mapRegionToParamReachable( hrnR, paramIndex );
2279 // and we're done in this method for special param decomp mode
2284 // now iterate over reachable nodes to rewrite their alpha, and
2285 // classify edges found for beta rewrite
2286 Hashtable<TokenTuple, ReachabilitySet> tokens2states = new Hashtable<TokenTuple, ReachabilitySet>();
2288 Hashtable< Integer, Set<Vector> > edges_p2p = new Hashtable< Integer, Set<Vector> >();
2289 Hashtable< Integer, Set<Vector> > edges_p2s = new Hashtable< Integer, Set<Vector> >();
2290 Hashtable< Integer, Set<Vector> > edges_s2p = new Hashtable< Integer, Set<Vector> >();
2291 Hashtable< Integer, Set<Vector> > edges_s2s = new Hashtable< Integer, Set<Vector> >();
2292 Hashtable< Integer, Set<Vector> > edges_up_dr = new Hashtable< Integer, Set<Vector> >();
2293 Hashtable< Integer, Set<Vector> > edges_up_r = new Hashtable< Integer, Set<Vector> >();
2295 // so again, with respect to some arg i...
2296 lnArgItr = paramIndex2ln.entrySet().iterator();
2297 while( lnArgItr.hasNext() ) {
2298 Map.Entry me = (Map.Entry) lnArgItr.next();
2299 Integer index = (Integer) me.getKey();
2300 LabelNode lnArg_i = (LabelNode) me.getValue();
2302 TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary.get( index );
2303 TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( index );
2306 ensureEmptyEdgeIndexPair( edges_p2p, index );
2307 ensureEmptyEdgeIndexPair( edges_p2s, index );
2308 ensureEmptyEdgeIndexPair( edges_s2p, index );
2309 ensureEmptyEdgeIndexPair( edges_s2s, index );
2310 ensureEmptyEdgeIndexPair( edges_up_dr, index );
2311 ensureEmptyEdgeIndexPair( edges_up_r, index );
2313 Set<HeapRegionNode> dr = pi2dr.get( index );
2314 Iterator<HeapRegionNode> hrnItr = dr.iterator();
2315 while( hrnItr.hasNext() ) {
2316 // this heap region is definitely an "a_i" or primary by virtue of being in dr
2317 HeapRegionNode hrn = hrnItr.next();
2319 tokens2states.clear();
2320 tokens2states.put( p_i, hrn.getAlpha() );
2322 rewriteCallerReachability( index,
2325 paramIndex2rewriteH_p.get( index ),
2327 paramIndex2rewrite_d_p,
2328 paramIndex2rewrite_d_s,
2329 paramIndex2rewriteD,
2334 nodesWithNewAlpha.add( hrn );
2337 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
2338 while( edgeItr.hasNext() ) {
2339 ReferenceEdge edge = edgeItr.next();
2340 OwnershipNode on = edge.getSrc();
2342 boolean edge_classified = false;
2345 if( on instanceof HeapRegionNode ) {
2346 // hrn0 may be "a_j" and/or "r_j" or even neither
2347 HeapRegionNode hrn0 = (HeapRegionNode) on;
2349 Iterator itr = pi2dr.entrySet().iterator();
2350 while( itr.hasNext() ) {
2351 Map.Entry mo = (Map.Entry) itr.next();
2352 Integer pi = (Integer) mo.getKey();
2353 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
2355 if( dr_i.contains( hrn0 ) ) {
2356 addEdgeIndexPair( edges_p2p, pi, edge, index );
2357 edge_classified = true;
2361 itr = pi2r.entrySet().iterator();
2362 while( itr.hasNext() ) {
2363 Map.Entry mo = (Map.Entry) itr.next();
2364 Integer pi = (Integer) mo.getKey();
2365 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
2367 if( r_i.contains( hrn0 ) ) {
2368 addEdgeIndexPair( edges_s2p, pi, edge, index );
2369 edge_classified = true;
2374 // all of these edges are upstream of directly reachable objects
2375 if( !edge_classified ) {
2376 addEdgeIndexPair( edges_up_dr, index, edge, index );
2382 Set<HeapRegionNode> r = pi2r.get( index );
2383 hrnItr = r.iterator();
2384 while( hrnItr.hasNext() ) {
2385 // this heap region is definitely an "r_i" or secondary by virtue of being in r
2386 HeapRegionNode hrn = hrnItr.next();
2388 if( paramIndex2rewriteH_s.containsKey( index ) ) {
2390 tokens2states.clear();
2391 tokens2states.put( p_i, new ReachabilitySet().makeCanonical() );
2392 tokens2states.put( s_i, hrn.getAlpha() );
2394 rewriteCallerReachability( index,
2397 paramIndex2rewriteH_s.get( index ),
2399 paramIndex2rewrite_d_p,
2400 paramIndex2rewrite_d_s,
2401 paramIndex2rewriteD,
2406 nodesWithNewAlpha.add( hrn );
2410 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
2411 while( edgeItr.hasNext() ) {
2412 ReferenceEdge edge = edgeItr.next();
2413 OwnershipNode on = edge.getSrc();
2415 boolean edge_classified = false;
2417 if( on instanceof HeapRegionNode ) {
2418 // hrn0 may be "a_j" and/or "r_j" or even neither
2419 HeapRegionNode hrn0 = (HeapRegionNode) on;
2421 Iterator itr = pi2dr.entrySet().iterator();
2422 while( itr.hasNext() ) {
2423 Map.Entry mo = (Map.Entry) itr.next();
2424 Integer pi = (Integer) mo.getKey();
2425 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
2427 if( dr_i.contains( hrn0 ) ) {
2428 addEdgeIndexPair( edges_p2s, pi, edge, index );
2429 edge_classified = true;
2433 itr = pi2r.entrySet().iterator();
2434 while( itr.hasNext() ) {
2435 Map.Entry mo = (Map.Entry) itr.next();
2436 Integer pi = (Integer) mo.getKey();
2437 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
2439 if( r_i.contains( hrn0 ) ) {
2440 addEdgeIndexPair( edges_s2s, pi, edge, index );
2441 edge_classified = true;
2446 // these edges are all upstream of some reachable node
2447 if( !edge_classified ) {
2448 addEdgeIndexPair( edges_up_r, index, edge, index );
2455 // and again, with respect to some arg i...
2456 lnArgItr = paramIndex2ln.entrySet().iterator();
2457 while( lnArgItr.hasNext() ) {
2458 Map.Entry me = (Map.Entry) lnArgItr.next();
2459 Integer index = (Integer) me.getKey();
2460 LabelNode lnArg_i = (LabelNode) me.getValue();
2463 // update reachable edges
2464 Iterator edgeItr = edges_p2p.get( index ).iterator();
2465 while( edgeItr.hasNext() ) {
2466 Vector mo = (Vector) edgeItr.next();
2467 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2468 Integer indexJ = (Integer) mo.get( 1 );
2470 if( !paramIndex2rewriteJ_p2p.containsKey( makeMapKey( index,
2472 edge.getField() ) ) ) {
2476 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2479 tokens2states.clear();
2480 tokens2states.put( p_j, edge.getBeta() );
2482 rewriteCallerReachability( index,
2485 paramIndex2rewriteJ_p2p.get( makeMapKey( index,
2487 edge.getField() ) ),
2489 paramIndex2rewrite_d_p,
2490 paramIndex2rewrite_d_s,
2491 paramIndex2rewriteD,
2496 edgesWithNewBeta.add( edge );
2500 edgeItr = edges_p2s.get( index ).iterator();
2501 while( edgeItr.hasNext() ) {
2502 Vector mo = (Vector) edgeItr.next();
2503 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2504 Integer indexJ = (Integer) mo.get( 1 );
2506 if( !paramIndex2rewriteJ_p2s.containsKey( makeMapKey( index,
2507 edge.getField() ) ) ) {
2511 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2514 tokens2states.clear();
2515 tokens2states.put( s_j, edge.getBeta() );
2517 rewriteCallerReachability( index,
2520 paramIndex2rewriteJ_p2s.get( makeMapKey( index,
2521 edge.getField() ) ),
2523 paramIndex2rewrite_d_p,
2524 paramIndex2rewrite_d_s,
2525 paramIndex2rewriteD,
2530 edgesWithNewBeta.add( edge );
2534 edgeItr = edges_s2p.get( index ).iterator();
2535 while( edgeItr.hasNext() ) {
2536 Vector mo = (Vector) edgeItr.next();
2537 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2538 Integer indexJ = (Integer) mo.get( 1 );
2540 if( !paramIndex2rewriteJ_s2p.containsKey( index ) ) {
2544 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2547 tokens2states.clear();
2548 tokens2states.put( p_j, edge.getBeta() );
2550 rewriteCallerReachability( index,
2553 paramIndex2rewriteJ_s2p.get( index ),
2555 paramIndex2rewrite_d_p,
2556 paramIndex2rewrite_d_s,
2557 paramIndex2rewriteD,
2562 edgesWithNewBeta.add( edge );
2566 edgeItr = edges_s2s.get( index ).iterator();
2567 while( edgeItr.hasNext() ) {
2568 Vector mo = (Vector) edgeItr.next();
2569 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2570 Integer indexJ = (Integer) mo.get( 1 );
2572 if( !paramIndex2rewriteJ_s2s.containsKey( index ) ) {
2576 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2579 tokens2states.clear();
2580 tokens2states.put( s_j, edge.getBeta() );
2582 rewriteCallerReachability( index,
2585 paramIndex2rewriteJ_s2s.get( index ),
2587 paramIndex2rewrite_d_p,
2588 paramIndex2rewrite_d_s,
2589 paramIndex2rewriteD,
2594 edgesWithNewBeta.add( edge );
2598 // update directly upstream edges
2599 Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
2600 new Hashtable<ReferenceEdge, ChangeTupleSet>();
2602 HashSet<ReferenceEdge> edgesDirectlyUpstream =
2603 new HashSet<ReferenceEdge>();
2605 edgeItr = edges_up_dr.get( index ).iterator();
2606 while( edgeItr.hasNext() ) {
2607 Vector mo = (Vector) edgeItr.next();
2608 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2609 Integer indexJ = (Integer) mo.get( 1 );
2611 edgesDirectlyUpstream.add( edge );
2613 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2616 // start with K_p2 and p_j
2617 tokens2states.clear();
2618 tokens2states.put( p_j, edge.getBeta() );
2620 rewriteCallerReachability( index,
2623 paramIndex2rewriteK_p2.get( index ),
2625 paramIndex2rewrite_d_p,
2626 paramIndex2rewrite_d_s,
2627 paramIndex2rewriteD,
2630 edgeUpstreamPlannedChanges );
2632 // and add in s_j, if required, and do K_p
2633 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2635 tokens2states.put( s_j, edge.getBeta() );
2638 rewriteCallerReachability( index,
2641 paramIndex2rewriteK_p.get( index ),
2643 paramIndex2rewrite_d_p,
2644 paramIndex2rewrite_d_s,
2645 paramIndex2rewriteD,
2648 edgeUpstreamPlannedChanges );
2650 edgesWithNewBeta.add( edge );
2653 propagateTokensOverEdges( edgesDirectlyUpstream,
2654 edgeUpstreamPlannedChanges,
2658 // update upstream edges
2659 edgeUpstreamPlannedChanges =
2660 new Hashtable<ReferenceEdge, ChangeTupleSet>();
2662 HashSet<ReferenceEdge> edgesUpstream =
2663 new HashSet<ReferenceEdge>();
2665 edgeItr = edges_up_r.get( index ).iterator();
2666 while( edgeItr.hasNext() ) {
2667 Vector mo = (Vector) edgeItr.next();
2668 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2669 Integer indexJ = (Integer) mo.get( 1 );
2671 if( !paramIndex2rewriteK_s.containsKey( index ) ) {
2675 edgesUpstream.add( edge );
2677 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2680 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2683 tokens2states.clear();
2684 tokens2states.put( p_j, rsWttsEmpty );
2685 tokens2states.put( s_j, edge.getBeta() );
2687 rewriteCallerReachability( index,
2690 paramIndex2rewriteK_s.get( index ),
2692 paramIndex2rewrite_d_p,
2693 paramIndex2rewrite_d_s,
2694 paramIndex2rewriteD,
2697 edgeUpstreamPlannedChanges );
2699 edgesWithNewBeta.add( edge );
2702 propagateTokensOverEdges( edgesUpstream,
2703 edgeUpstreamPlannedChanges,
2706 } // end effects per argument/parameter map
2709 // commit changes to alpha and beta
2710 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
2711 while( nodeItr.hasNext() ) {
2712 nodeItr.next().applyAlphaNew();
2715 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
2716 while( edgeItr.hasNext() ) {
2717 edgeItr.next().applyBetaNew();
2721 // verify the existence of allocation sites and their
2722 // shadows from the callee in the context of this caller graph
2723 // then map allocated nodes of callee onto the caller shadows
2725 Hashtable<TokenTuple, ReachabilitySet> tokens2statesEmpty = new Hashtable<TokenTuple, ReachabilitySet>();
2727 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
2728 while( asItr.hasNext() ) {
2729 AllocationSite allocSite = asItr.next();
2731 // grab the summary in the caller just to make sure
2732 // the allocation site has nodes in the caller
2733 HeapRegionNode hrnSummary = getSummaryNode( allocSite );
2735 // assert that the shadow nodes have no reference edges
2736 // because they're brand new to the graph, or last time
2737 // they were used they should have been cleared of edges
2738 HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
2739 assert hrnShadowSummary.getNumReferencers() == 0;
2740 assert hrnShadowSummary.getNumReferencees() == 0;
2742 // then bring g_ij onto g'_ij and rewrite
2743 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode( allocSite );
2744 hrnShadowSummary.setAlpha( toShadowTokens( ogCallee, hrnSummaryCallee.getAlpha() ) );
2746 // shadow nodes only are touched by a rewrite one time,
2747 // so rewrite and immediately commit--and they don't belong
2748 // to a particular parameter, so use a bogus param index
2749 // that pulls a self-rewrite out of H
2750 rewriteCallerReachability( bogusIndex,
2753 funcScriptR( hrnShadowSummary.getAlpha(), ogCallee, mc ),
2755 paramIndex2rewrite_d_p,
2756 paramIndex2rewrite_d_s,
2757 paramIndex2rewriteD,
2762 hrnShadowSummary.applyAlphaNew();
2765 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
2766 Integer idIth = allocSite.getIthOldest(i);
2767 assert id2hrn.containsKey(idIth);
2768 HeapRegionNode hrnIth = id2hrn.get(idIth);
2770 Integer idShadowIth = -(allocSite.getIthOldest(i));
2771 assert id2hrn.containsKey(idShadowIth);
2772 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
2773 assert hrnIthShadow.getNumReferencers() == 0;
2774 assert hrnIthShadow.getNumReferencees() == 0;
2776 assert ogCallee.id2hrn.containsKey(idIth);
2777 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
2778 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
2780 rewriteCallerReachability( bogusIndex,
2783 funcScriptR( hrnIthShadow.getAlpha(), ogCallee, mc ),
2785 paramIndex2rewrite_d_p,
2786 paramIndex2rewrite_d_s,
2787 paramIndex2rewriteD,
2792 hrnIthShadow.applyAlphaNew();
2797 // for every heap region->heap region edge in the
2798 // callee graph, create the matching edge or edges
2799 // in the caller graph
2800 Set sCallee = ogCallee.id2hrn.entrySet();
2801 Iterator iCallee = sCallee.iterator();
2803 while( iCallee.hasNext() ) {
2804 Map.Entry meCallee = (Map.Entry) iCallee.next();
2805 Integer idCallee = (Integer) meCallee.getKey();
2806 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
2808 Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
2809 while( heapRegionsItrCallee.hasNext() ) {
2810 ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
2811 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
2812 Integer idChildCallee = hrnChildCallee.getID();
2814 // only address this edge if it is not a special initial edge
2815 if( !edgeCallee.isInitialParam() ) {
2817 // now we know that in the callee method's ownership graph
2818 // there is a heap region->heap region reference edge given
2819 // by heap region pointers:
2820 // hrnCallee -> heapChildCallee
2822 // or by the ownership-graph independent ID's:
2823 // idCallee -> idChildCallee
2825 // make the edge with src and dst so beta info is
2826 // calculated once, then copy it for each new edge in caller
2828 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null,
2830 edgeCallee.getType(),
2831 edgeCallee.getField(),
2833 funcScriptR( toShadowTokens( ogCallee,
2834 edgeCallee.getBeta()
2840 rewriteCallerReachability( bogusIndex,
2842 edgeNewInCallerTemplate,
2843 edgeNewInCallerTemplate.getBeta(),
2845 paramIndex2rewrite_d_p,
2846 paramIndex2rewrite_d_s,
2847 paramIndex2rewriteD,
2852 edgeNewInCallerTemplate.applyBetaNew();
2855 // So now make a set of possible source heaps in the caller graph
2856 // and a set of destination heaps in the caller graph, and make
2857 // a reference edge in the caller for every possible (src,dst) pair
2858 HashSet<HeapRegionNode> possibleCallerSrcs =
2859 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2860 (HeapRegionNode) edgeCallee.getSrc(),
2864 HashSet<HeapRegionNode> possibleCallerDsts =
2865 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2866 edgeCallee.getDst(),
2870 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
2871 Iterator srcItr = possibleCallerSrcs.iterator();
2872 while( srcItr.hasNext() ) {
2873 HeapRegionNode src = (HeapRegionNode) srcItr.next();
2875 if( !hasMatchingField( src, edgeCallee ) ) {
2876 // prune this source node possibility
2880 Iterator dstItr = possibleCallerDsts.iterator();
2881 while( dstItr.hasNext() ) {
2882 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
2884 if( !hasMatchingType( edgeCallee, dst ) ) {
2889 // otherwise the caller src and dst pair can match the edge, so make it
2890 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2891 edgeNewInCaller.setSrc( src );
2892 edgeNewInCaller.setDst( dst );
2894 // handle taint info if callee created this edge
2896 Set<Integer> pParamSet=idPrimary2paramIndexSet.get(dst.getID());
2897 Set<Integer> sParamSet=idSecondary2paramIndexSet.get(dst.getID());
2898 HashSet<Integer> paramSet=new HashSet<Integer>();
2899 if(pParamSet!=null){
2900 paramSet.addAll(pParamSet);
2902 if(sParamSet!=null){
2903 paramSet.addAll(sParamSet);
2905 Iterator<Integer> paramIter=paramSet.iterator();
2906 int newTaintIdentifier=0;
2907 while(paramIter.hasNext()){
2908 Integer paramIdx=paramIter.next();
2909 edgeNewInCaller.tainedBy(paramIdx);
2912 ReferenceEdge edgeExisting = src.getReferenceTo( dst,
2913 edgeNewInCaller.getType(),
2914 edgeNewInCaller.getField() );
2915 if( edgeExisting == null ) {
2916 // if this edge doesn't exist in the caller, create it
2917 addReferenceEdge( src, dst, edgeNewInCaller );
2920 // if it already exists, merge with it
2921 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2931 // return value may need to be assigned in caller
2932 TempDescriptor returnTemp = fc.getReturnTemp();
2933 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2935 LabelNode lnLhsCaller = getLabelNodeFromTemp( returnTemp );
2936 clearReferenceEdgesFrom( lnLhsCaller, null, null, true );
2938 LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp( tdReturn );
2939 Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
2940 while( edgeCalleeItr.hasNext() ) {
2941 ReferenceEdge edgeCallee = edgeCalleeItr.next();
2943 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null,
2945 edgeCallee.getType(),
2946 edgeCallee.getField(),
2948 funcScriptR( toShadowTokens(ogCallee,
2949 edgeCallee.getBeta() ),
2953 rewriteCallerReachability( bogusIndex,
2955 edgeNewInCallerTemplate,
2956 edgeNewInCallerTemplate.getBeta(),
2958 paramIndex2rewrite_d_p,
2959 paramIndex2rewrite_d_s,
2960 paramIndex2rewriteD,
2965 edgeNewInCallerTemplate.applyBetaNew();
2968 HashSet<HeapRegionNode> assignCallerRhs =
2969 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2970 edgeCallee.getDst(),
2974 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
2975 while( itrHrn.hasNext() ) {
2976 HeapRegionNode hrnCaller = itrHrn.next();
2978 if( !hasMatchingType( edgeCallee, hrnCaller ) ) {
2983 // otherwise caller node can match callee edge, so make it
2984 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2985 edgeNewInCaller.setSrc( lnLhsCaller );
2986 edgeNewInCaller.setDst( hrnCaller );
2988 ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo( hrnCaller,
2989 edgeNewInCaller.getType(),
2990 edgeNewInCaller.getField() );
2991 if( edgeExisting == null ) {
2993 // if this edge doesn't exist in the caller, create it
2994 addReferenceEdge( lnLhsCaller, hrnCaller, edgeNewInCaller );
2996 // if it already exists, merge with it
2997 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
3006 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
3007 fm.getMethod().getSymbol().equals( debugCallee )
3011 writeGraph("debug7JustBeforeMergeToKCapacity",
3012 true, // write labels (variables)
3013 true, // selectively hide intermediate temp vars
3014 true, // prune unreachable heap regions
3015 false, // show back edges to confirm graph validity
3016 false, // show parameter indices (unmaintained!)
3017 true, // hide subset reachability states
3018 true); // hide edge taints
3019 } catch( IOException e ) {}
3024 // merge the shadow nodes of allocation sites back down to normal capacity
3025 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
3026 while( allocItr.hasNext() ) {
3027 AllocationSite as = allocItr.next();
3029 // first age each allocation site enough times to make room for the shadow nodes
3030 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
3034 // then merge the shadow summary into the normal summary
3035 HeapRegionNode hrnSummary = getSummaryNode( as );
3036 assert hrnSummary != null;
3038 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as );
3039 assert hrnSummaryShadow != null;
3041 mergeIntoSummary( hrnSummaryShadow, hrnSummary );
3043 // then clear off after merge
3044 clearReferenceEdgesFrom( hrnSummaryShadow, null, null, true );
3045 clearReferenceEdgesTo ( hrnSummaryShadow, null, null, true );
3046 hrnSummaryShadow.setAlpha( new ReachabilitySet().makeCanonical() );
3048 // then transplant shadow nodes onto the now clean normal nodes
3049 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
3051 Integer idIth = as.getIthOldest( i );
3052 HeapRegionNode hrnIth = id2hrn.get( idIth );
3053 Integer idIthShadow = as.getIthOldestShadow( i );
3054 HeapRegionNode hrnIthShadow = id2hrn.get( idIthShadow );
3056 transferOnto( hrnIthShadow, hrnIth );
3058 // clear off shadow nodes after transfer
3059 clearReferenceEdgesFrom( hrnIthShadow, null, null, true );
3060 clearReferenceEdgesTo ( hrnIthShadow, null, null, true );
3061 hrnIthShadow.setAlpha( new ReachabilitySet().makeCanonical() );
3064 // finally, globally change shadow tokens into normal tokens
3065 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
3066 while( itrAllLabelNodes.hasNext() ) {
3067 Map.Entry me = (Map.Entry) itrAllLabelNodes.next();
3068 LabelNode ln = (LabelNode) me.getValue();
3070 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
3071 while( itrEdges.hasNext() ) {
3072 unshadowTokens( as, itrEdges.next() );
3076 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3077 while( itrAllHRNodes.hasNext() ) {
3078 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
3079 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
3081 unshadowTokens( as, hrnToAge );
3083 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
3084 while( itrEdges.hasNext() ) {
3085 unshadowTokens( as, itrEdges.next() );
3093 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
3094 fm.getMethod().getSymbol().equals( debugCallee )
3098 writeGraph( "debug8JustBeforeSweep",
3099 true, // write labels (variables)
3100 true, // selectively hide intermediate temp vars
3101 true, // prune unreachable heap regions
3102 false, // show back edges to confirm graph validity
3103 false, // show parameter indices (unmaintained!)
3104 true, // hide subset reachability states
3105 true); // hide edge taints
3106 } catch( IOException e ) {}
3111 // improve reachability as much as possible
3112 if( !DISABLE_GLOBAL_SWEEP ) {
3118 mc.getDescriptor().getSymbol().equals( debugCaller ) &&
3119 fm.getMethod().getSymbol().equals( debugCallee )
3123 writeGraph( "debug9endResolveCall",
3124 true, // write labels (variables)
3125 true, // selectively hide intermediate temp vars
3126 true, // prune unreachable heap regions
3127 false, // show back edges to confirm graph validity
3128 false, // show parameter indices (unmaintained!)
3129 true, // hide subset reachability states
3130 true); // hide edge taints
3131 } catch( IOException e ) {}
3132 System.out.println( " "+mc+" done calling "+fm );
3134 if( x == debugCallMapCount ) {
3143 protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
3145 // if no type, then it's a match-everything region
3146 TypeDescriptor tdSrc = src.getType();
3147 if( tdSrc == null ) {
3151 if( tdSrc.isArray() ) {
3152 TypeDescriptor td = edge.getType();
3155 TypeDescriptor tdSrcDeref = tdSrc.dereference();
3156 assert tdSrcDeref != null;
3158 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3162 return edge.getField().equals( OwnershipAnalysis.arrayElementFieldName );
3165 // if it's not a class, it doesn't have any fields to match
3166 if( !tdSrc.isClass() ) {
3170 ClassDescriptor cd = tdSrc.getClassDesc();
3171 while( cd != null ) {
3172 Iterator fieldItr = cd.getFields();
3174 while( fieldItr.hasNext() ) {
3175 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3177 if( fd.getType().equals( edge.getType() ) &&
3178 fd.getSymbol().equals( edge.getField() ) ) {
3183 cd = cd.getSuperDesc();
3186 // otherwise it is a class with fields
3187 // but we didn't find a match
3192 protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
3194 // if the region has no type, matches everything
3195 TypeDescriptor tdDst = dst.getType();
3196 if( tdDst == null ) {
3200 // if the type is not a class or an array, don't
3201 // match because primitives are copied, no aliases
3202 ClassDescriptor cdDst = tdDst.getClassDesc();
3203 if( cdDst == null && !tdDst.isArray() ) {
3207 // if the edge type is null, it matches everything
3208 TypeDescriptor tdEdge = edge.getType();
3209 if( tdEdge == null ) {
3213 return typeUtil.isSuperorType(tdEdge, tdDst);
3218 protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
3219 edge.setBeta(edge.getBeta().unshadowTokens(as) );
3222 protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
3223 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
3227 private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
3228 ReachabilitySet rsIn) {
3230 ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical();
3232 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
3233 while( allocItr.hasNext() ) {
3234 AllocationSite as = allocItr.next();
3236 rsOut = rsOut.toShadowTokens(as);
3239 return rsOut.makeCanonical();
3243 private void rewriteCallerReachability(Integer paramIndex,
3246 ReachabilitySet rules,
3247 Hashtable<TokenTuple, ReachabilitySet> tokens2states,
3248 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_p,
3249 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_s,
3250 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
3251 OwnershipGraph ogCallee,
3252 boolean makeChangeSet,
3253 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
3255 assert(hrn == null && edge != null) ||
3256 (hrn != null && edge == null);
3258 assert rules != null;
3259 assert tokens2states != null;
3261 ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
3263 // for initializing structures in this method
3264 TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
3266 // use this to construct a change set if required; the idea is to
3267 // map every partially rewritten token tuple set to the set of
3268 // caller-context token tuple sets that were used to generate it
3269 Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
3270 new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
3271 rewritten2source.put( ttsEmpty, new HashSet<TokenTupleSet>() );
3274 Iterator<TokenTupleSet> rulesItr = rules.iterator();
3275 while(rulesItr.hasNext()) {
3276 TokenTupleSet rule = rulesItr.next();
3278 ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
3280 Iterator<TokenTuple> ruleItr = rule.iterator();
3281 while(ruleItr.hasNext()) {
3282 TokenTuple ttCallee = ruleItr.next();
3284 // compute the possibilities for rewriting this callee token
3285 ReachabilitySet ttCalleeRewrites = null;
3286 boolean callerSourceUsed = false;
3288 if( tokens2states.containsKey( ttCallee ) ) {
3289 callerSourceUsed = true;
3290 ttCalleeRewrites = tokens2states.get( ttCallee );
3291 assert ttCalleeRewrites != null;
3293 } else if( ogCallee.paramTokenPrimary2paramIndex.containsKey( ttCallee ) ) {
3295 Integer paramIndex_j = ogCallee.paramTokenPrimary2paramIndex.get( ttCallee );
3296 assert paramIndex_j != null;
3297 ttCalleeRewrites = paramIndex2rewrite_d_p.get( paramIndex_j );
3298 assert ttCalleeRewrites != null;
3300 } else if( ogCallee.paramTokenSecondary2paramIndex.containsKey( ttCallee ) ) {
3302 Integer paramIndex_j = ogCallee.paramTokenSecondary2paramIndex.get( ttCallee );
3303 assert paramIndex_j != null;
3304 ttCalleeRewrites = paramIndex2rewrite_d_s.get( paramIndex_j );
3305 assert ttCalleeRewrites != null;
3307 } else if( ogCallee.paramTokenSecondaryPlus2paramIndex.containsKey( ttCallee ) ) {
3309 Integer paramIndex_j = ogCallee.paramTokenSecondaryPlus2paramIndex.get( ttCallee );
3310 assert paramIndex_j != null;
3311 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
3312 assert ttCalleeRewrites != null;
3314 } else if( ogCallee.paramTokenSecondaryStar2paramIndex.containsKey( ttCallee ) ) {
3316 Integer paramIndex_j = ogCallee.paramTokenSecondaryStar2paramIndex.get( ttCallee );
3317 assert paramIndex_j != null;
3318 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
3319 assert ttCalleeRewrites != null;
3322 // otherwise there's no need for a rewrite, just pass this one on
3323 TokenTupleSet ttsCaller = new TokenTupleSet( ttCallee ).makeCanonical();
3324 ttCalleeRewrites = new ReachabilitySet( ttsCaller ).makeCanonical();
3327 // branch every version of the working rewritten rule with
3328 // the possibilities for rewriting the current callee token
3329 ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
3331 Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
3332 while( rewrittenRuleItr.hasNext() ) {
3333 TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
3335 Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
3336 while( ttCalleeRewritesItr.hasNext() ) {
3337 TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
3339 TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
3341 if( makeChangeSet ) {
3342 // in order to keep the list of source token tuple sets
3343 // start with the sets used to make the partially rewritten
3344 // rule up to this point
3345 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewritten );
3346 assert sourceSets != null;
3348 // make a shallow copy for possible modification
3349 sourceSets = (HashSet<TokenTupleSet>) sourceSets.clone();
3351 // if we used something from the caller to rewrite it, remember
3352 if( callerSourceUsed ) {
3353 sourceSets.add( ttsBranch );
3356 // set mapping for the further rewritten rule
3357 rewritten2source.put( ttsRewrittenNext, sourceSets );
3360 rewrittenRuleWithTTCallee =
3361 rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
3365 // now the rewritten rule's possibilities have been extended by
3366 // rewriting the current callee token, remember result
3367 rewrittenRule = rewrittenRuleWithTTCallee;
3370 // the rule has been entirely rewritten into the caller context
3371 // now, so add it to the new reachability information
3372 callerReachabilityNew =
3373 callerReachabilityNew.union( rewrittenRule );
3376 if( makeChangeSet ) {
3377 ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
3379 // each possibility for the final reachability should have a set of
3380 // caller sources mapped to it, use to create the change set
3381 Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
3382 while( callerReachabilityItr.hasNext() ) {
3383 TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
3384 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewrittenFinal );
3385 assert sourceSets != null;
3387 Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
3388 while( sourceSetsItr.hasNext() ) {
3389 TokenTupleSet ttsSource = sourceSetsItr.next();
3392 callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
3396 assert edgePlannedChanges != null;
3397 edgePlannedChanges.put( edge, callerChangeSet );
3401 edge.setBetaNew( edge.getBetaNew().union( callerReachabilityNew ) );
3403 hrn.setAlphaNew( hrn.getAlphaNew().union( callerReachabilityNew ) );
3409 private HashSet<HeapRegionNode>
3410 getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
3411 HeapRegionNode hrnCallee,
3412 Hashtable<Integer, Set<HeapRegionNode> > pi2dr,
3413 Hashtable<Integer, Set<HeapRegionNode> > pi2r
3416 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
3418 Set<Integer> paramIndicesCallee_p = ogCallee.idPrimary2paramIndexSet .get( hrnCallee.getID() );
3419 Set<Integer> paramIndicesCallee_s = ogCallee.idSecondary2paramIndexSet.get( hrnCallee.getID() );
3421 if( paramIndicesCallee_p == null &&
3422 paramIndicesCallee_s == null ) {
3423 // this is a node allocated in the callee and it has
3424 // exactly one shadow node in the caller to map to
3425 AllocationSite as = hrnCallee.getAllocationSite();
3428 int age = as.getAgeCategory( hrnCallee.getID() );
3429 assert age != AllocationSite.AGE_notInThisSite;
3432 if( age == AllocationSite.AGE_summary ) {
3433 idCaller = as.getSummaryShadow();
3435 } else if( age == AllocationSite.AGE_oldest ) {
3436 idCaller = as.getOldestShadow();
3439 assert age == AllocationSite.AGE_in_I;
3441 Integer I = as.getAge( hrnCallee.getID() );
3444 idCaller = as.getIthOldestShadow( I );
3447 assert id2hrn.containsKey( idCaller );
3448 possibleCallerHRNs.add( id2hrn.get( idCaller ) );
3450 return possibleCallerHRNs;
3453 // find out what primary objects this might be
3454 if( paramIndicesCallee_p != null ) {
3455 // this is a node that was created to represent a parameter
3456 // so it maps to some regions directly reachable from the arg labels
3457 Iterator<Integer> itrIndex = paramIndicesCallee_p.iterator();
3458 while( itrIndex.hasNext() ) {
3459 Integer paramIndexCallee = itrIndex.next();
3460 assert pi2dr.containsKey( paramIndexCallee );
3461 possibleCallerHRNs.addAll( pi2dr.get( paramIndexCallee ) );
3465 // find out what secondary objects this might be
3466 if( paramIndicesCallee_s != null ) {
3467 // this is a node that was created to represent objs reachable from
3468 // some parameter, so it maps to regions reachable from the arg labels
3469 Iterator<Integer> itrIndex = paramIndicesCallee_s.iterator();
3470 while( itrIndex.hasNext() ) {
3471 Integer paramIndexCallee = itrIndex.next();
3472 assert pi2r.containsKey( paramIndexCallee );
3473 possibleCallerHRNs.addAll( pi2r.get( paramIndexCallee ) );
3477 // TODO: is this true?
3478 // one of the two cases above should have put something in here
3479 //assert !possibleCallerHRNs.isEmpty();
3481 return possibleCallerHRNs;
3486 ////////////////////////////////////////////////////
3488 // This global sweep is an optional step to prune
3489 // reachability sets that are not internally
3490 // consistent with the global graph. It should be
3491 // invoked after strong updates or method calls.
3493 ////////////////////////////////////////////////////
3494 public void globalSweep() {
3496 // boldB is part of the phase 1 sweep
3497 Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> > boldB =
3498 new Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> >();
3500 // visit every heap region to initialize alphaNew and calculate boldB
3501 Set hrns = id2hrn.entrySet();
3502 Iterator itrHrns = hrns.iterator();
3503 while( itrHrns.hasNext() ) {
3504 Map.Entry me = (Map.Entry)itrHrns.next();
3505 Integer token = (Integer) me.getKey();
3506 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3508 // assert that this node and incoming edges have clean alphaNew
3509 // and betaNew sets, respectively
3510 assert rsEmpty.equals( hrn.getAlphaNew() );
3512 Iterator<ReferenceEdge> itrRers = hrn.iteratorToReferencers();
3513 while( itrRers.hasNext() ) {
3514 ReferenceEdge edge = itrRers.next();
3515 assert rsEmpty.equals( edge.getBetaNew() );
3518 // calculate boldB for this flagged node
3519 if( hrn.isFlagged() || hrn.isParameter() ) {
3521 Hashtable<ReferenceEdge, ReachabilitySet> boldB_f =
3522 new Hashtable<ReferenceEdge, ReachabilitySet>();
3524 Set<ReferenceEdge> workSetEdges = new HashSet<ReferenceEdge>();
3526 // initial boldB_f constraints
3527 Iterator<ReferenceEdge> itrRees = hrn.iteratorToReferencees();
3528 while( itrRees.hasNext() ) {
3529 ReferenceEdge edge = itrRees.next();
3531 assert !boldB.containsKey( edge );
3532 boldB_f.put( edge, edge.getBeta() );
3534 assert !workSetEdges.contains( edge );
3535 workSetEdges.add( edge );
3538 // enforce the boldB_f constraint at edges until we reach a fixed point
3539 while( !workSetEdges.isEmpty() ) {
3540 ReferenceEdge edge = workSetEdges.iterator().next();
3541 workSetEdges.remove( edge );
3543 Iterator<ReferenceEdge> itrPrime = edge.getDst().iteratorToReferencees();
3544 while( itrPrime.hasNext() ) {
3545 ReferenceEdge edgePrime = itrPrime.next();
3547 ReachabilitySet prevResult = boldB_f.get( edgePrime );
3548 ReachabilitySet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
3550 if( prevResult == null ||
3551 prevResult.union( intersection ).size() > prevResult.size() ) {
3553 if( prevResult == null ) {
3554 boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) );
3556 boldB_f.put( edgePrime, prevResult .union( intersection ) );
3558 workSetEdges.add( edgePrime );
3563 boldB.put( token, boldB_f );
3568 // use boldB to prune tokens from alpha states that are impossible
3569 // and propagate the differences backwards across edges
3570 HashSet<ReferenceEdge> edgesForPropagation = new HashSet<ReferenceEdge>();
3572 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
3573 new Hashtable<ReferenceEdge, ChangeTupleSet>();
3575 hrns = id2hrn.entrySet();
3576 itrHrns = hrns.iterator();
3577 while( itrHrns.hasNext() ) {
3578 Map.Entry me = (Map.Entry)itrHrns.next();
3579 Integer token = (Integer) me.getKey();
3580 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3582 // never remove the identity token from a flagged region
3583 // because it is trivially satisfied
3584 TokenTuple ttException = new TokenTuple( token,
3585 !hrn.isSingleObject(),
3586 TokenTuple.ARITY_ONE ).makeCanonical();
3588 ChangeTupleSet cts = new ChangeTupleSet().makeCanonical();
3590 // mark tokens for removal
3591 Iterator<TokenTupleSet> stateItr = hrn.getAlpha().iterator();
3592 while( stateItr.hasNext() ) {
3593 TokenTupleSet ttsOld = stateItr.next();
3595 TokenTupleSet markedTokens = new TokenTupleSet().makeCanonical();
3597 Iterator<TokenTuple> ttItr = ttsOld.iterator();
3598 while( ttItr.hasNext() ) {
3599 TokenTuple ttOld = ttItr.next();
3601 // never remove the identity token from a flagged region
3602 // because it is trivially satisfied
3603 if( hrn.isFlagged() || hrn.isParameter() ) {
3604 if( ttOld == ttException ) {
3609 // does boldB_ttOld allow this token?
3610 boolean foundState = false;
3611 Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3612 while( incidentEdgeItr.hasNext() ) {
3613 ReferenceEdge incidentEdge = incidentEdgeItr.next();
3615 // if it isn't allowed, mark for removal
3616 Integer idOld = ttOld.getToken();
3617 assert id2hrn.containsKey( idOld );
3618 Hashtable<ReferenceEdge, ReachabilitySet> B = boldB.get( idOld );
3619 ReachabilitySet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL!
3620 if( boldB_ttOld_incident != null &&
3621 boldB_ttOld_incident.contains( ttsOld ) ) {
3627 markedTokens = markedTokens.add( ttOld );
3631 // if there is nothing marked, just move on
3632 if( markedTokens.isEmpty() ) {
3633 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
3637 // remove all marked tokens and establish a change set that should
3638 // propagate backwards over edges from this node
3639 TokenTupleSet ttsPruned = new TokenTupleSet().makeCanonical();
3640 ttItr = ttsOld.iterator();
3641 while( ttItr.hasNext() ) {
3642 TokenTuple ttOld = ttItr.next();
3644 if( !markedTokens.containsTuple( ttOld ) ) {
3645 ttsPruned = ttsPruned.union( ttOld );
3648 assert !ttsOld.equals( ttsPruned );
3650 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
3651 ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
3652 cts = cts.union( ct );
3655 // throw change tuple set on all incident edges
3656 if( !cts.isEmpty() ) {
3657 Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3658 while( incidentEdgeItr.hasNext() ) {
3659 ReferenceEdge incidentEdge = incidentEdgeItr.next();
3661 edgesForPropagation.add( incidentEdge );
3663 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3664 edgePlannedChanges.put( incidentEdge, cts );
3666 edgePlannedChanges.put(
3668 edgePlannedChanges.get( incidentEdge ).union( cts )
3675 HashSet<ReferenceEdge> edgesUpdated = new HashSet<ReferenceEdge>();
3677 propagateTokensOverEdges( edgesForPropagation,
3681 // at the end of the 1st phase reference edges have
3682 // beta, betaNew that correspond to beta and betaR
3684 // commit beta<-betaNew, so beta=betaR and betaNew
3685 // will represent the beta' calculation in 2nd phase
3687 // commit alpha<-alphaNew because it won't change
3688 HashSet<ReferenceEdge> res = new HashSet<ReferenceEdge>();
3690 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3691 while( nodeItr.hasNext() ) {
3692 HeapRegionNode hrn = nodeItr.next();
3693 hrn.applyAlphaNew();
3694 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
3695 while( itrRes.hasNext() ) {
3696 res.add( itrRes.next() );
3702 Iterator<ReferenceEdge> edgeItr = res.iterator();
3703 while( edgeItr.hasNext() ) {
3704 ReferenceEdge edge = edgeItr.next();
3705 HeapRegionNode hrn = edge.getDst();
3707 // commit results of last phase
3708 if( edgesUpdated.contains( edge ) ) {
3709 edge.applyBetaNew();
3712 // compute intial condition of 2nd phase
3713 edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
3716 // every edge in the graph is the initial workset
3717 Set<ReferenceEdge> edgeWorkSet = (Set) res.clone();
3718 while( !edgeWorkSet.isEmpty() ) {
3719 ReferenceEdge edgePrime = edgeWorkSet.iterator().next();
3720 edgeWorkSet.remove( edgePrime );
3722 OwnershipNode on = edgePrime.getSrc();
3723 if( !(on instanceof HeapRegionNode) ) {
3726 HeapRegionNode hrn = (HeapRegionNode) on;
3728 Iterator<ReferenceEdge> itrEdge = hrn.iteratorToReferencers();
3729 while( itrEdge.hasNext() ) {
3730 ReferenceEdge edge = itrEdge.next();
3732 ReachabilitySet prevResult = edge.getBetaNew();
3733 assert prevResult != null;
3735 ReachabilitySet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
3737 if( prevResult.union( intersection ).size() > prevResult.size() ) {
3738 edge.setBetaNew( prevResult.union( intersection ) );
3739 edgeWorkSet.add( edge );
3744 // commit beta' (beta<-betaNew)
3745 edgeItr = res.iterator();
3746 while( edgeItr.hasNext() ) {
3747 edgeItr.next().applyBetaNew();
3753 ////////////////////////////////////////////////////
3754 // in merge() and equals() methods the suffix A
3755 // represents the passed in graph and the suffix
3756 // B refers to the graph in this object
3757 // Merging means to take the incoming graph A and
3758 // merge it into B, so after the operation graph B
3759 // is the final result.
3760 ////////////////////////////////////////////////////
3761 public void merge(OwnershipGraph og) {
3767 mergeOwnershipNodes(og);
3768 mergeReferenceEdges(og);
3769 mergeParamIndexMappings(og);
3770 mergeAllocationSites(og);
3771 mergeAccessPaths(og);
3772 mergeTempAndLabelCategories(og);
3776 protected void mergeOwnershipNodes(OwnershipGraph og) {
3777 Set sA = og.id2hrn.entrySet();
3778 Iterator iA = sA.iterator();
3779 while( iA.hasNext() ) {
3780 Map.Entry meA = (Map.Entry)iA.next();
3781 Integer idA = (Integer) meA.getKey();
3782 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3784 // if this graph doesn't have a node the
3785 // incoming graph has, allocate it
3786 if( !id2hrn.containsKey(idA) ) {
3787 HeapRegionNode hrnB = hrnA.copy();
3788 id2hrn.put(idA, hrnB);
3791 // otherwise this is a node present in both graphs
3792 // so make the new reachability set a union of the
3793 // nodes' reachability sets
3794 HeapRegionNode hrnB = id2hrn.get(idA);
3795 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
3799 // now add any label nodes that are in graph B but
3801 sA = og.td2ln.entrySet();
3803 while( iA.hasNext() ) {
3804 Map.Entry meA = (Map.Entry)iA.next();
3805 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3806 LabelNode lnA = (LabelNode) meA.getValue();
3808 // if the label doesn't exist in B, allocate and add it
3809 LabelNode lnB = getLabelNodeFromTemp(tdA);
3813 protected void mergeReferenceEdges(OwnershipGraph og) {
3816 Set sA = og.id2hrn.entrySet();
3817 Iterator iA = sA.iterator();
3818 while( iA.hasNext() ) {
3819 Map.Entry meA = (Map.Entry)iA.next();
3820 Integer idA = (Integer) meA.getKey();
3821 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3823 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3824 while( heapRegionsItrA.hasNext() ) {
3825 ReferenceEdge edgeA = heapRegionsItrA.next();
3826 HeapRegionNode hrnChildA = edgeA.getDst();
3827 Integer idChildA = hrnChildA.getID();
3829 // at this point we know an edge in graph A exists
3830 // idA -> idChildA, does this exist in B?
3831 assert id2hrn.containsKey(idA);
3832 HeapRegionNode hrnB = id2hrn.get(idA);
3833 ReferenceEdge edgeToMerge = null;
3835 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3836 while( heapRegionsItrB.hasNext() &&
3837 edgeToMerge == null ) {
3839 ReferenceEdge edgeB = heapRegionsItrB.next();
3840 HeapRegionNode hrnChildB = edgeB.getDst();
3841 Integer idChildB = hrnChildB.getID();
3843 // don't use the ReferenceEdge.equals() here because
3844 // we're talking about existence between graphs
3845 if( idChildB.equals( idChildA ) &&
3846 edgeB.typeAndFieldEquals( edgeA ) ) {
3848 edgeToMerge = edgeB;
3852 // if the edge from A was not found in B,
3854 if( edgeToMerge == null ) {
3855 assert id2hrn.containsKey(idChildA);
3856 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3857 edgeToMerge = edgeA.copy();
3858 edgeToMerge.setSrc(hrnB);
3859 edgeToMerge.setDst(hrnChildB);
3860 addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
3862 // otherwise, the edge already existed in both graphs
3863 // so merge their reachability sets
3865 // just replace this beta set with the union
3866 assert edgeToMerge != null;
3867 edgeToMerge.setBeta(
3868 edgeToMerge.getBeta().union(edgeA.getBeta() )
3871 edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
3872 if( !edgeA.isInitialParam() ) {
3873 edgeToMerge.setIsInitialParam(false);
3879 // and then again with label nodes
3880 sA = og.td2ln.entrySet();
3882 while( iA.hasNext() ) {
3883 Map.Entry meA = (Map.Entry)iA.next();
3884 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3885 LabelNode lnA = (LabelNode) meA.getValue();
3887 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
3888 while( heapRegionsItrA.hasNext() ) {
3889 ReferenceEdge edgeA = heapRegionsItrA.next();
3890 HeapRegionNode hrnChildA = edgeA.getDst();
3891 Integer idChildA = hrnChildA.getID();
3893 // at this point we know an edge in graph A exists
3894 // tdA -> idChildA, does this exist in B?
3895 assert td2ln.containsKey(tdA);
3896 LabelNode lnB = td2ln.get(tdA);
3897 ReferenceEdge edgeToMerge = null;
3899 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
3900 while( heapRegionsItrB.hasNext() &&
3901 edgeToMerge == null ) {
3903 ReferenceEdge edgeB = heapRegionsItrB.next();
3904 HeapRegionNode hrnChildB = edgeB.getDst();
3905 Integer idChildB = hrnChildB.getID();
3907 // don't use the ReferenceEdge.equals() here because
3908 // we're talking about existence between graphs
3909 if( idChildB.equals( idChildA ) &&
3910 edgeB.typeAndFieldEquals( edgeA ) ) {
3912 edgeToMerge = edgeB;
3916 // if the edge from A was not found in B,
3918 if( edgeToMerge == null ) {
3919 assert id2hrn.containsKey(idChildA);
3920 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3921 edgeToMerge = edgeA.copy();
3922 edgeToMerge.setSrc(lnB);
3923 edgeToMerge.setDst(hrnChildB);
3924 addReferenceEdge(lnB, hrnChildB, edgeToMerge);
3926 // otherwise, the edge already existed in both graphs
3927 // so merge their reachability sets
3929 // just replace this beta set with the union
3930 edgeToMerge.setBeta(
3931 edgeToMerge.getBeta().union(edgeA.getBeta() )
3933 edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
3934 if( !edgeA.isInitialParam() ) {
3935 edgeToMerge.setIsInitialParam(false);
3942 // you should only merge ownership graphs that have the
3943 // same number of parameters, or if one or both parameter
3944 // index tables are empty
3945 protected void mergeParamIndexMappings(OwnershipGraph og) {
3947 if( idPrimary2paramIndexSet.size() == 0 ) {
3949 idPrimary2paramIndexSet = og.idPrimary2paramIndexSet;
3950 paramIndex2idPrimary = og.paramIndex2idPrimary;
3952 idSecondary2paramIndexSet = og.idSecondary2paramIndexSet;
3953 paramIndex2idSecondary = og.paramIndex2idSecondary;
3955 paramIndex2tdQ = og.paramIndex2tdQ;
3956 paramIndex2tdR = og.paramIndex2tdR;
3958 paramTokenPrimary2paramIndex = og.paramTokenPrimary2paramIndex;
3959 paramIndex2paramTokenPrimary = og.paramIndex2paramTokenPrimary;
3961 paramTokenSecondary2paramIndex = og.paramTokenSecondary2paramIndex;
3962 paramIndex2paramTokenSecondary = og.paramIndex2paramTokenSecondary;
3963 paramTokenSecondaryPlus2paramIndex = og.paramTokenSecondaryPlus2paramIndex;
3964 paramIndex2paramTokenSecondaryPlus = og.paramIndex2paramTokenSecondaryPlus;
3965 paramTokenSecondaryStar2paramIndex = og.paramTokenSecondaryStar2paramIndex;
3966 paramIndex2paramTokenSecondaryStar = og.paramIndex2paramTokenSecondaryStar;
3971 if( og.idPrimary2paramIndexSet.size() == 0 ) {
3973 og.idPrimary2paramIndexSet = idPrimary2paramIndexSet;
3974 og.paramIndex2idPrimary = paramIndex2idPrimary;
3976 og.idSecondary2paramIndexSet = idSecondary2paramIndexSet;
3977 og.paramIndex2idSecondary = paramIndex2idSecondary;
3979 og.paramIndex2tdQ = paramIndex2tdQ;
3980 og.paramIndex2tdR = paramIndex2tdR;
3982 og.paramTokenPrimary2paramIndex = paramTokenPrimary2paramIndex;
3983 og.paramIndex2paramTokenPrimary = paramIndex2paramTokenPrimary;
3985 og.paramTokenSecondary2paramIndex = paramTokenSecondary2paramIndex;
3986 og.paramIndex2paramTokenSecondary = paramIndex2paramTokenSecondary;
3987 og.paramTokenSecondaryPlus2paramIndex = paramTokenSecondaryPlus2paramIndex;
3988 og.paramIndex2paramTokenSecondaryPlus = paramIndex2paramTokenSecondaryPlus;
3989 og.paramTokenSecondaryStar2paramIndex = paramTokenSecondaryStar2paramIndex;
3990 og.paramIndex2paramTokenSecondaryStar = paramIndex2paramTokenSecondaryStar;
3995 assert idPrimary2paramIndexSet.size() == og.idPrimary2paramIndexSet.size();
3996 assert idSecondary2paramIndexSet.size() == og.idSecondary2paramIndexSet.size();
3999 protected void mergeAllocationSites(OwnershipGraph og) {
4000 allocationSites.addAll(og.allocationSites);
4003 protected void mergeAccessPaths(OwnershipGraph og) {
4004 UtilAlgorithms.mergeHashtablesWithHashSetValues(temp2accessPaths,
4005 og.temp2accessPaths);
4008 protected void mergeTempAndLabelCategories(OwnershipGraph og) {
4009 outOfScopeTemps.addAll(og.outOfScopeTemps);
4010 outOfScopeLabels.addAll(og.outOfScopeLabels);
4011 parameterTemps.addAll(og.parameterTemps);
4012 parameterLabels.addAll(og.parameterLabels);
4017 // it is necessary in the equals() member functions
4018 // to "check both ways" when comparing the data
4019 // structures of two graphs. For instance, if all
4020 // edges between heap region nodes in graph A are
4021 // present and equal in graph B it is not sufficient
4022 // to say the graphs are equal. Consider that there
4023 // may be edges in graph B that are not in graph A.
4024 // the only way to know that all edges in both graphs
4025 // are equally present is to iterate over both data
4026 // structures and compare against the other graph.
4027 public boolean equals(OwnershipGraph og) {
4033 if( !areHeapRegionNodesEqual(og) ) {
4037 if( !areLabelNodesEqual(og) ) {
4041 if( !areReferenceEdgesEqual(og) ) {
4045 if( !areParamIndexMappingsEqual(og) ) {
4049 if( !areAccessPathsEqual(og) ) {
4053 // if everything is equal up to this point,
4054 // assert that allocationSites is also equal--
4055 // this data is redundant and kept for efficiency
4056 assert allocationSites .equals(og.allocationSites );
4057 assert outOfScopeTemps .equals(og.outOfScopeTemps );
4058 assert outOfScopeLabels.equals(og.outOfScopeLabels);
4059 assert parameterTemps .equals(og.parameterTemps );
4060 assert parameterLabels .equals(og.parameterLabels );
4065 protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
4067 if( !areallHRNinAalsoinBandequal(this, og) ) {
4071 if( !areallHRNinAalsoinBandequal(og, this) ) {
4078 static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
4079 OwnershipGraph ogB) {
4080 Set sA = ogA.id2hrn.entrySet();
4081 Iterator iA = sA.iterator();
4082 while( iA.hasNext() ) {
4083 Map.Entry meA = (Map.Entry)iA.next();
4084 Integer idA = (Integer) meA.getKey();
4085 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4087 if( !ogB.id2hrn.containsKey(idA) ) {
4091 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
4092 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
4101 protected boolean areLabelNodesEqual(OwnershipGraph og) {
4103 if( !areallLNinAalsoinBandequal(this, og) ) {
4107 if( !areallLNinAalsoinBandequal(og, this) ) {
4114 static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
4115 OwnershipGraph ogB) {
4116 Set sA = ogA.td2ln.entrySet();
4117 Iterator iA = sA.iterator();
4118 while( iA.hasNext() ) {
4119 Map.Entry meA = (Map.Entry)iA.next();
4120 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4122 if( !ogB.td2ln.containsKey(tdA) ) {
4131 protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
4132 if( !areallREinAandBequal(this, og) ) {
4139 static protected boolean areallREinAandBequal(OwnershipGraph ogA,
4140 OwnershipGraph ogB) {
4142 // check all the heap region->heap region edges
4143 Set sA = ogA.id2hrn.entrySet();
4144 Iterator iA = sA.iterator();
4145 while( iA.hasNext() ) {
4146 Map.Entry meA = (Map.Entry)iA.next();
4147 Integer idA = (Integer) meA.getKey();
4148 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4150 // we should have already checked that the same
4151 // heap regions exist in both graphs
4152 assert ogB.id2hrn.containsKey(idA);
4154 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
4158 // then check every edge in B for presence in A, starting
4159 // from the same parent HeapRegionNode
4160 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
4162 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
4167 // then check all the label->heap region edges
4168 sA = ogA.td2ln.entrySet();
4170 while( iA.hasNext() ) {
4171 Map.Entry meA = (Map.Entry)iA.next();
4172 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4173 LabelNode lnA = (LabelNode) meA.getValue();
4175 // we should have already checked that the same
4176 // label nodes exist in both graphs
4177 assert ogB.td2ln.containsKey(tdA);
4179 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
4183 // then check every edge in B for presence in A, starting
4184 // from the same parent LabelNode
4185 LabelNode lnB = ogB.td2ln.get(tdA);
4187 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
4196 static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
4198 OwnershipGraph ogB) {
4200 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
4201 while( itrA.hasNext() ) {
4202 ReferenceEdge edgeA = itrA.next();
4203 HeapRegionNode hrnChildA = edgeA.getDst();
4204 Integer idChildA = hrnChildA.getID();
4206 assert ogB.id2hrn.containsKey(idChildA);
4208 // at this point we know an edge in graph A exists
4209 // onA -> idChildA, does this exact edge exist in B?
4210 boolean edgeFound = false;
4212 OwnershipNode onB = null;
4213 if( onA instanceof HeapRegionNode ) {
4214 HeapRegionNode hrnA = (HeapRegionNode) onA;
4215 onB = ogB.id2hrn.get(hrnA.getID() );
4217 LabelNode lnA = (LabelNode) onA;
4218 onB = ogB.td2ln.get(lnA.getTempDescriptor() );
4221 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
4222 while( itrB.hasNext() ) {
4223 ReferenceEdge edgeB = itrB.next();
4224 HeapRegionNode hrnChildB = edgeB.getDst();
4225 Integer idChildB = hrnChildB.getID();
4227 if( idChildA.equals( idChildB ) &&
4228 edgeA.typeAndFieldEquals( edgeB ) ) {
4230 // there is an edge in the right place with the right field,
4231 // but do they have the same attributes?
4232 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
4247 protected boolean areParamIndexMappingsEqual(OwnershipGraph og) {
4249 if( idPrimary2paramIndexSet.size() != og.idPrimary2paramIndexSet.size() ) {
4253 if( idSecondary2paramIndexSet.size() != og.idSecondary2paramIndexSet.size() ) {
4261 protected boolean areAccessPathsEqual(OwnershipGraph og) {
4262 return temp2accessPaths.equals( og.temp2accessPaths );
4267 public Set<HeapRegionNode> hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) {
4268 assert hrn1 != null;
4269 assert hrn2 != null;
4271 // then get the various tokens for these heap regions
4272 TokenTuple h1 = new TokenTuple(hrn1.getID(),
4273 !hrn1.isSingleObject(),
4274 TokenTuple.ARITY_ONE).makeCanonical();
4276 TokenTuple h1plus = new TokenTuple(hrn1.getID(),
4277 !hrn1.isSingleObject(),
4278 TokenTuple.ARITY_ONEORMORE).makeCanonical();
4280 TokenTuple h1star = new TokenTuple(hrn1.getID(),
4281 !hrn1.isSingleObject(),
4282 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
4284 TokenTuple h2 = new TokenTuple(hrn2.getID(),
4285 !hrn2.isSingleObject(),
4286 TokenTuple.ARITY_ONE).makeCanonical();
4288 TokenTuple h2plus = new TokenTuple(hrn2.getID(),
4289 !hrn2.isSingleObject(),
4290 TokenTuple.ARITY_ONEORMORE).makeCanonical();
4292 TokenTuple h2star = new TokenTuple(hrn2.getID(),
4293 !hrn2.isSingleObject(),
4294 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
4296 // then get the merged beta of all out-going edges from these heap regions
4297 ReachabilitySet beta1 = new ReachabilitySet().makeCanonical();
4298 Iterator<ReferenceEdge> itrEdge = hrn1.iteratorToReferencees();
4299 while( itrEdge.hasNext() ) {
4300 ReferenceEdge edge = itrEdge.next();
4301 beta1 = beta1.union( edge.getBeta() );
4304 ReachabilitySet beta2 = new ReachabilitySet().makeCanonical();
4305 itrEdge = hrn2.iteratorToReferencees();
4306 while( itrEdge.hasNext() ) {
4307 ReferenceEdge edge = itrEdge.next();
4308 beta2 = beta2.union( edge.getBeta() );
4311 boolean aliasDetected = false;
4313 // only do this one if they are different tokens
4315 beta1.containsTupleSetWithBoth(h1, h2) ) {
4316 aliasDetected = true;
4318 if( beta1.containsTupleSetWithBoth(h1plus, h2) ) {
4319 aliasDetected = true;
4321 if( beta1.containsTupleSetWithBoth(h1star, h2) ) {
4322 aliasDetected = true;
4324 if( beta1.containsTupleSetWithBoth(h1, h2plus) ) {
4325 aliasDetected = true;
4327 if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) {
4328 aliasDetected = true;
4330 if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) {
4331 aliasDetected = true;
4333 if( beta1.containsTupleSetWithBoth(h1, h2star) ) {
4334 aliasDetected = true;
4336 if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) {
4337 aliasDetected = true;
4339 if( beta1.containsTupleSetWithBoth(h1star, h2star) ) {
4340 aliasDetected = true;
4344 beta2.containsTupleSetWithBoth(h1, h2) ) {
4345 aliasDetected = true;
4347 if( beta2.containsTupleSetWithBoth(h1plus, h2) ) {
4348 aliasDetected = true;
4350 if( beta2.containsTupleSetWithBoth(h1star, h2) ) {
4351 aliasDetected = true;
4353 if( beta2.containsTupleSetWithBoth(h1, h2plus) ) {
4354 aliasDetected = true;
4356 if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) {
4357 aliasDetected = true;
4359 if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) {
4360 aliasDetected = true;
4362 if( beta2.containsTupleSetWithBoth(h1, h2star) ) {
4363 aliasDetected = true;
4365 if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) {
4366 aliasDetected = true;
4368 if( beta2.containsTupleSetWithBoth(h1star, h2star) ) {
4369 aliasDetected = true;
4372 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4373 if( aliasDetected ) {
4374 common = findCommonReachableNodes( hrn1, hrn2 );
4375 if( !(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP) ) {
4376 assert !common.isEmpty();
4384 public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
4386 // get parameter 1's heap regions
4387 assert paramIndex2idPrimary.containsKey(paramIndex1);
4388 Integer idParamPri1 = paramIndex2idPrimary.get(paramIndex1);
4390 assert id2hrn.containsKey(idParamPri1);
4391 HeapRegionNode hrnParamPri1 = id2hrn.get(idParamPri1);
4392 assert hrnParamPri1 != null;
4394 HeapRegionNode hrnParamSec1 = null;
4395 if( paramIndex2idSecondary.containsKey(paramIndex1) ) {
4396 Integer idParamSec1 = paramIndex2idSecondary.get(paramIndex1);
4398 assert id2hrn.containsKey(idParamSec1);
4399 hrnParamSec1 = id2hrn.get(idParamSec1);
4400 assert hrnParamSec1 != null;
4404 // get the other parameter
4405 assert paramIndex2idPrimary.containsKey(paramIndex2);
4406 Integer idParamPri2 = paramIndex2idPrimary.get(paramIndex2);
4408 assert id2hrn.containsKey(idParamPri2);
4409 HeapRegionNode hrnParamPri2 = id2hrn.get(idParamPri2);
4410 assert hrnParamPri2 != null;
4412 HeapRegionNode hrnParamSec2 = null;
4413 if( paramIndex2idSecondary.containsKey(paramIndex2) ) {
4414 Integer idParamSec2 = paramIndex2idSecondary.get(paramIndex2);
4416 assert id2hrn.containsKey(idParamSec2);
4417 hrnParamSec2 = id2hrn.get(idParamSec2);
4418 assert hrnParamSec2 != null;
4421 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4422 common.addAll( hasPotentialAlias( hrnParamPri1, hrnParamPri2 ) );
4424 if( hrnParamSec1 != null ) {
4425 common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamPri2 ) );
4428 if( hrnParamSec2 != null ) {
4429 common.addAll( hasPotentialAlias( hrnParamSec2, hrnParamPri1 ) );
4432 if( hrnParamSec1 != null && hrnParamSec2 != null ) {
4433 common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamSec2 ) );
4440 public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex, AllocationSite as) {
4442 // get parameter's heap regions
4443 assert paramIndex2idPrimary.containsKey(paramIndex);
4444 Integer idParamPri = paramIndex2idPrimary.get(paramIndex);
4446 assert id2hrn.containsKey(idParamPri);
4447 HeapRegionNode hrnParamPri = id2hrn.get(idParamPri);
4448 assert hrnParamPri != null;
4450 HeapRegionNode hrnParamSec = null;
4451 if( paramIndex2idSecondary.containsKey(paramIndex) ) {
4452 Integer idParamSec = paramIndex2idSecondary.get(paramIndex);
4454 assert id2hrn.containsKey(idParamSec);
4455 hrnParamSec = id2hrn.get(idParamSec);
4456 assert hrnParamSec != null;
4460 assert id2hrn.containsKey( as.getSummary() );
4461 HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() );
4462 assert hrnSummary != null;
4464 Set<HeapRegionNode> common = hasPotentialAlias( hrnParamPri, hrnSummary );
4466 if( hrnParamSec != null ) {
4467 common.addAll( hasPotentialAlias( hrnParamSec, hrnSummary ) );
4470 // check for other nodes
4471 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4473 assert id2hrn.containsKey( as.getIthOldest( i ) );
4474 HeapRegionNode hrnIthOldest = id2hrn.get( as.getIthOldest( i ) );
4475 assert hrnIthOldest != null;
4477 common = hasPotentialAlias( hrnParamPri, hrnIthOldest );
4479 if( hrnParamSec != null ) {
4480 common.addAll( hasPotentialAlias( hrnParamSec, hrnIthOldest ) );
4488 public Set<HeapRegionNode> hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
4490 // get summary node 1's alpha
4491 Integer idSum1 = as1.getSummary();
4492 assert id2hrn.containsKey(idSum1);
4493 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
4494 assert hrnSum1 != null;
4496 // get summary node 2's alpha
4497 Integer idSum2 = as2.getSummary();
4498 assert id2hrn.containsKey(idSum2);
4499 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
4500 assert hrnSum2 != null;
4502 Set<HeapRegionNode> common = hasPotentialAlias( hrnSum1, hrnSum2 );
4504 // check sum2 against alloc1 nodes
4505 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
4506 Integer idI1 = as1.getIthOldest(i);
4507 assert id2hrn.containsKey(idI1);
4508 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4509 assert hrnI1 != null;
4511 common.addAll( hasPotentialAlias( hrnI1, hrnSum2 ) );
4514 // check sum1 against alloc2 nodes
4515 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
4516 Integer idI2 = as2.getIthOldest(i);
4517 assert id2hrn.containsKey(idI2);
4518 HeapRegionNode hrnI2 = id2hrn.get(idI2);
4519 assert hrnI2 != null;
4521 common.addAll( hasPotentialAlias( hrnSum1, hrnI2 ) );
4523 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4524 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
4525 Integer idI1 = as1.getIthOldest(j);
4527 // if these are the same site, don't look for the same token, no alias.
4528 // different tokens of the same site could alias together though
4529 if( idI1.equals( idI2 ) ) {
4533 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4535 common.addAll( hasPotentialAlias( hrnI1, hrnI2 ) );
4543 public Set<HeapRegionNode> findCommonReachableNodes( HeapRegionNode hrn1,
4544 HeapRegionNode hrn2 ) {
4546 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
4547 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
4549 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
4550 todoNodes1.add( hrn1 );
4552 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
4553 todoNodes2.add( hrn2 );
4555 // follow links until all reachable nodes have been found
4556 while( !todoNodes1.isEmpty() ) {
4557 HeapRegionNode hrn = todoNodes1.iterator().next();
4558 todoNodes1.remove( hrn );
4559 reachableNodes1.add(hrn);
4561 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
4562 while( edgeItr.hasNext() ) {
4563 ReferenceEdge edge = edgeItr.next();
4565 if( !reachableNodes1.contains( edge.getDst() ) ) {
4566 todoNodes1.add( edge.getDst() );
4571 while( !todoNodes2.isEmpty() ) {
4572 HeapRegionNode hrn = todoNodes2.iterator().next();
4573 todoNodes2.remove( hrn );
4574 reachableNodes2.add(hrn);
4576 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
4577 while( edgeItr.hasNext() ) {
4578 ReferenceEdge edge = edgeItr.next();
4580 if( !reachableNodes2.contains( edge.getDst() ) ) {
4581 todoNodes2.add( edge.getDst() );
4586 Set<HeapRegionNode> intersection =
4587 new HashSet<HeapRegionNode>( reachableNodes1 );
4589 intersection.retainAll( reachableNodes2 );
4591 return intersection;
4595 public void writeGraph(String graphName,
4596 boolean writeLabels,
4597 boolean labelSelect,
4598 boolean pruneGarbage,
4599 boolean writeReferencers,
4600 boolean writeParamMappings,
4601 boolean hideSubsetReachability,
4602 boolean hideEdgeTaints
4603 ) throws java.io.IOException {
4605 // remove all non-word characters from the graph name so
4606 // the filename and identifier in dot don't cause errors
4607 graphName = graphName.replaceAll("[\\W]", "");
4609 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
4610 bw.write("digraph "+graphName+" {\n");
4612 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4614 // then visit every heap region node
4615 Set s = id2hrn.entrySet();
4616 Iterator i = s.iterator();
4617 while( i.hasNext() ) {
4618 Map.Entry me = (Map.Entry)i.next();
4619 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4621 if( !pruneGarbage ||
4622 (hrn.isFlagged() && hrn.getID() > 0) ||
4623 hrn.getDescription().startsWith("param")
4626 if( !visited.contains(hrn) ) {
4627 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4633 hideSubsetReachability,
4639 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4641 if( writeParamMappings ) {
4643 Set df = paramIndex2id.entrySet();
4644 Iterator ih = df.iterator();
4645 while( ih.hasNext() ) {
4646 Map.Entry meh = (Map.Entry)ih.next();
4647 Integer pi = (Integer) meh.getKey();
4648 Integer id = (Integer) meh.getValue();
4649 bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
4654 // then visit every label node, useful for debugging
4656 s = td2ln.entrySet();
4658 while( i.hasNext() ) {
4659 Map.Entry me = (Map.Entry)i.next();
4660 LabelNode ln = (LabelNode) me.getValue();
4663 String labelStr = ln.getTempDescriptorString();
4664 if( labelStr.startsWith("___temp") ||
4665 labelStr.startsWith("___dst") ||
4666 labelStr.startsWith("___srctmp") ||
4667 labelStr.startsWith("___neverused") ||
4668 labelStr.contains(qString) ||
4669 labelStr.contains(rString) ||
4670 labelStr.contains(blobString)
4676 //bw.write(" "+ln.toString() + ";\n");
4678 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
4679 while( heapRegionsItr.hasNext() ) {
4680 ReferenceEdge edge = heapRegionsItr.next();
4681 HeapRegionNode hrn = edge.getDst();
4683 if( pruneGarbage && !visited.contains(hrn) ) {
4684 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4690 hideSubsetReachability,
4694 bw.write(" " + ln.toString() +
4695 " -> " + hrn.toString() +
4696 "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
4708 protected void traverseHeapRegionNodes(int mode,
4712 HashSet<HeapRegionNode> visited,
4713 boolean writeReferencers,
4714 boolean hideSubsetReachability,
4715 boolean hideEdgeTaints
4716 ) throws java.io.IOException {
4718 if( visited.contains(hrn) ) {
4724 case VISIT_HRN_WRITE_FULL:
4726 String attributes = "[";
4728 if( hrn.isSingleObject() ) {
4729 attributes += "shape=box";
4731 attributes += "shape=Msquare";
4734 if( hrn.isFlagged() ) {
4735 attributes += ",style=filled,fillcolor=lightgrey";
4738 attributes += ",label=\"ID" +
4742 if( hrn.getType() != null ) {
4743 attributes += hrn.getType().toPrettyString() + "\\n";
4746 attributes += hrn.getDescription() +
4748 hrn.getAlphaString(hideSubsetReachability) +
4751 bw.write(" " + hrn.toString() + attributes + ";\n");
4756 // useful for debugging
4759 if( writeReferencers ) {
4760 OwnershipNode onRef = null;
4761 Iterator refItr = hrn.iteratorToReferencers();
4762 while( refItr.hasNext() ) {
4763 onRef = (OwnershipNode) refItr.next();
4766 case VISIT_HRN_WRITE_FULL:
4767 bw.write(" " + hrn.toString() +
4768 " -> " + onRef.toString() +
4769 "[color=lightgray];\n");
4776 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
4777 while( childRegionsItr.hasNext() ) {
4778 ReferenceEdge edge = childRegionsItr.next();
4779 HeapRegionNode hrnChild = edge.getDst();
4782 case VISIT_HRN_WRITE_FULL:
4783 bw.write(" " + hrn.toString() +
4784 " -> " + hrnChild.toString() +
4785 "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
4791 traverseHeapRegionNodes(mode,
4797 hideSubsetReachability,
4802 public int getTaintIdentifierFromHRN(HeapRegionNode hrn){
4803 HashSet<ReferenceEdge> referenceEdges=hrn.referencers;
4804 Iterator<ReferenceEdge> iter=referenceEdges.iterator();
4806 int taintIdentifier=0;
4807 while(iter.hasNext()){
4808 ReferenceEdge edge=iter.next();
4809 taintIdentifier=taintIdentifier | edge.getTaintIdentifier();
4812 return taintIdentifier;
4816 public void propagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet){
4818 HashSet<ReferenceEdge> setEdge=hrn.referencers;
4819 Iterator<ReferenceEdge> iter=setEdge.iterator();
4820 while(iter.hasNext()){
4821 ReferenceEdge edge= iter.next();
4822 edge.unionTaintIdentifier(newTaintIdentifier);
4823 if(edge.getSrc() instanceof HeapRegionNode){
4825 HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
4826 //check whether it is reflexive edge
4827 if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){
4828 visitedSet.add(refHRN);
4829 propagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);
4837 public void depropagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet){
4839 HashSet<ReferenceEdge> setEdge=hrn.referencers;
4840 Iterator<ReferenceEdge> iter=setEdge.iterator();
4841 while(iter.hasNext()){
4842 ReferenceEdge edge= iter.next();
4843 edge.minusTaintIdentifier(newTaintIdentifier);
4844 if(edge.getSrc() instanceof HeapRegionNode){
4846 HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
4847 //check whether it is reflexive edge
4848 if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){
4849 visitedSet.add(refHRN);
4850 depropagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);