1 package Analysis.OwnershipAnalysis;
8 public class OwnershipGraph {
10 private int allocationDepth;
11 private TypeUtil typeUtil;
13 // there was already one other very similar reason
14 // for traversing heap nodes that is no longer needed
15 // instead of writing a new heap region visitor, use
16 // the existing method with a new mode to describe what
17 // actions to take during the traversal
18 protected static final int VISIT_HRN_WRITE_FULL = 0;
20 protected static final String qString = new String( "Q_spec_" );
21 protected static final String rString = new String( "R_spec_" );
22 protected static final String blobString = new String( "_AliasBlob___" );
24 protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
25 protected static final TempDescriptor tdAliasBlob = new TempDescriptor( blobString );
27 protected static final TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
28 protected static final ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical();
29 protected static final ReachabilitySet rsWttsEmpty = new ReachabilitySet( ttsEmpty ).makeCanonical();
31 // add a bogus entry with the identity rule for easy rewrite
32 // of new callee nodes and edges, doesn't belong to any parameter
33 protected static final int bogusParamIndexInt = -2;
34 protected static final Integer bogusID = new Integer( bogusParamIndexInt );
35 protected static final Integer bogusIndex = new Integer( bogusParamIndexInt );
36 protected static final TokenTuple bogusToken = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONE ).makeCanonical();
37 protected static final TokenTuple bogusTokenPlus = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONEORMORE ).makeCanonical();
38 protected static final TokenTuple bogusTokenStar = new TokenTuple( bogusID, true, TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
39 protected static final ReachabilitySet rsIdentity =
40 new ReachabilitySet( new TokenTupleSet( bogusToken ).makeCanonical() ).makeCanonical();
43 public Hashtable<Integer, HeapRegionNode> id2hrn;
44 public Hashtable<TempDescriptor, LabelNode > td2ln;
46 public Hashtable<Integer, Set<Integer> > idPrimary2paramIndexSet;
47 public Hashtable<Integer, Integer > paramIndex2idPrimary;
49 public Hashtable<Integer, Set<Integer> > idSecondary2paramIndexSet;
50 public Hashtable<Integer, Integer > paramIndex2idSecondary;
52 public Hashtable<Integer, TempDescriptor> paramIndex2tdQ;
53 public Hashtable<Integer, TempDescriptor> paramIndex2tdR;
56 public HashSet<AllocationSite> allocationSites;
59 public Hashtable<TokenTuple, Integer> paramTokenPrimary2paramIndex;
60 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenPrimary;
62 public Hashtable<TokenTuple, Integer> paramTokenSecondary2paramIndex;
63 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondary;
64 public Hashtable<TokenTuple, Integer> paramTokenSecondaryPlus2paramIndex;
65 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondaryPlus;
66 public Hashtable<TokenTuple, Integer> paramTokenSecondaryStar2paramIndex;
67 public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondaryStar;
70 public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
71 this.allocationDepth = allocationDepth;
72 this.typeUtil = typeUtil;
74 id2hrn = new Hashtable<Integer, HeapRegionNode>();
75 td2ln = new Hashtable<TempDescriptor, LabelNode >();
76 idPrimary2paramIndexSet = new Hashtable<Integer, Set<Integer> >();
77 paramIndex2idPrimary = new Hashtable<Integer, Integer >();
78 idSecondary2paramIndexSet = new Hashtable<Integer, Set<Integer> >();
79 paramIndex2idSecondary = new Hashtable<Integer, Integer >();
80 paramIndex2tdQ = new Hashtable<Integer, TempDescriptor>();
81 paramIndex2tdR = new Hashtable<Integer, TempDescriptor>();
83 paramTokenPrimary2paramIndex = new Hashtable<TokenTuple, Integer >();
84 paramIndex2paramTokenPrimary = new Hashtable<Integer, TokenTuple >();
86 paramTokenSecondary2paramIndex = new Hashtable<TokenTuple, Integer >();
87 paramIndex2paramTokenSecondary = new Hashtable<Integer, TokenTuple >();
88 paramTokenSecondaryPlus2paramIndex = new Hashtable<TokenTuple, Integer >();
89 paramIndex2paramTokenSecondaryPlus = new Hashtable<Integer, TokenTuple >();
90 paramTokenSecondaryStar2paramIndex = new Hashtable<TokenTuple, Integer >();
91 paramIndex2paramTokenSecondaryStar = new Hashtable<Integer, TokenTuple >();
93 allocationSites = new HashSet <AllocationSite>();
97 // label nodes are much easier to deal with than
98 // heap region nodes. Whenever there is a request
99 // for the label node that is associated with a
100 // temp descriptor we can either find it or make a
101 // new one and return it. This is because temp
102 // descriptors are globally unique and every label
103 // node is mapped to exactly one temp descriptor.
104 protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
107 if( !td2ln.containsKey(td) ) {
108 td2ln.put(td, new LabelNode(td) );
111 return td2ln.get(td);
115 // the reason for this method is to have the option
116 // creating new heap regions with specific IDs, or
117 // duplicating heap regions with specific IDs (especially
118 // in the merge() operation) or to create new heap
119 // regions with a new unique ID.
120 protected HeapRegionNode
121 createNewHeapRegionNode(Integer id,
122 boolean isSingleObject,
123 boolean isNewSummary,
127 AllocationSite allocSite,
128 ReachabilitySet alpha,
129 String description) {
131 boolean markForAnalysis = isFlagged || isParameter;
133 TypeDescriptor typeToUse = null;
134 if( allocSite != null ) {
135 typeToUse = allocSite.getType();
140 if( allocSite != null && allocSite.getDisjointId() != null ) {
141 markForAnalysis = true;
145 id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
148 if( alpha == null ) {
149 if( markForAnalysis ) {
150 alpha = new ReachabilitySet(
157 alpha = new ReachabilitySet(
158 new TokenTupleSet().makeCanonical()
163 HeapRegionNode hrn = new HeapRegionNode(id,
178 ////////////////////////////////////////////////
180 // Low-level referencee and referencer methods
182 // These methods provide the lowest level for
183 // creating references between ownership nodes
184 // and handling the details of maintaining both
185 // list of referencers and referencees.
187 ////////////////////////////////////////////////
188 protected void addReferenceEdge(OwnershipNode referencer,
189 HeapRegionNode referencee,
190 ReferenceEdge edge) {
191 assert referencer != null;
192 assert referencee != null;
194 assert edge.getSrc() == referencer;
195 assert edge.getDst() == referencee;
197 referencer.addReferencee(edge);
198 referencee.addReferencer(edge);
201 protected void removeReferenceEdge(OwnershipNode referencer,
202 HeapRegionNode referencee,
205 assert referencer != null;
206 assert referencee != null;
208 ReferenceEdge edge = referencer.getReferenceTo(referencee,
212 assert edge == referencee.getReferenceFrom(referencer,
216 referencer.removeReferencee(edge);
217 referencee.removeReferencer(edge);
220 protected void clearReferenceEdgesFrom(OwnershipNode referencer,
224 assert referencer != null;
226 // get a copy of the set to iterate over, otherwise
227 // we will be trying to take apart the set as we
228 // are iterating over it, which won't work
229 Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
230 while( i.hasNext() ) {
231 ReferenceEdge edge = i.next();
234 (type != null && edge.getType() .equals( type )) ||
235 (field != null && edge.getField().equals( field ))
238 HeapRegionNode referencee = edge.getDst();
240 removeReferenceEdge(referencer,
248 protected void clearReferenceEdgesTo(HeapRegionNode referencee,
252 assert referencee != null;
254 // get a copy of the set to iterate over, otherwise
255 // we will be trying to take apart the set as we
256 // are iterating over it, which won't work
257 Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
258 while( i.hasNext() ) {
259 ReferenceEdge edge = i.next();
262 (type != null && edge.getType() .equals( type )) ||
263 (field != null && edge.getField().equals( field ))
266 OwnershipNode referencer = edge.getSrc();
268 removeReferenceEdge(referencer,
277 ////////////////////////////////////////////////////
279 // Assignment Operation Methods
281 // These methods are high-level operations for
282 // modeling program assignment statements using
283 // the low-level reference create/remove methods
286 // The destination in an assignment statement is
287 // going to have new references. The method of
288 // determining the references depends on the type
289 // of the FlatNode assignment and the predicates
290 // of the nodes and edges involved.
292 ////////////////////////////////////////////////////
293 public void assignTempXEqualToTempY(TempDescriptor x,
296 LabelNode lnX = getLabelNodeFromTemp(x);
297 LabelNode lnY = getLabelNodeFromTemp(y);
299 clearReferenceEdgesFrom(lnX, null, null, true);
301 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
302 while( itrYhrn.hasNext() ) {
303 ReferenceEdge edgeY = itrYhrn.next();
304 HeapRegionNode referencee = edgeY.getDst();
305 ReferenceEdge edgeNew = edgeY.copy();
308 addReferenceEdge(lnX, referencee, edgeNew);
313 public void assignTypedTempXEqualToTempY(TempDescriptor x,
315 TypeDescriptor type) {
317 LabelNode lnX = getLabelNodeFromTemp(x);
318 LabelNode lnY = getLabelNodeFromTemp(y);
320 clearReferenceEdgesFrom(lnX, null, null, true);
322 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
323 while( itrYhrn.hasNext() ) {
324 ReferenceEdge edgeY = itrYhrn.next();
325 HeapRegionNode referencee = edgeY.getDst();
326 ReferenceEdge edgeNew = edgeY.copy();
327 edgeNew.setSrc( lnX );
328 edgeNew.setType( type );
329 edgeNew.setField( null );
331 addReferenceEdge(lnX, referencee, edgeNew);
336 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
339 LabelNode lnX = getLabelNodeFromTemp(x);
340 LabelNode lnY = getLabelNodeFromTemp(y);
342 clearReferenceEdgesFrom(lnX, null, null, true);
344 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
345 while( itrYhrn.hasNext() ) {
346 ReferenceEdge edgeY = itrYhrn.next();
347 HeapRegionNode hrnY = edgeY.getDst();
348 ReachabilitySet betaY = edgeY.getBeta();
350 Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
351 while( itrHrnFhrn.hasNext() ) {
352 ReferenceEdge edgeHrn = itrHrnFhrn.next();
353 HeapRegionNode hrnHrn = edgeHrn.getDst();
354 ReachabilitySet betaHrn = edgeHrn.getBeta();
356 if( edgeHrn.getType() == null ||
357 edgeHrn.getType().equals( f.getType() ) ) {
359 ReferenceEdge edgeNew = new ReferenceEdge(lnX,
364 betaY.intersection(betaHrn) );
366 addReferenceEdge(lnX, hrnHrn, edgeNew);
373 public void assignTempXFieldFEqualToTempY(TempDescriptor x,
376 LabelNode lnX = getLabelNodeFromTemp(x);
377 LabelNode lnY = getLabelNodeFromTemp(y);
379 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
380 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
383 // first look for possible strong updates and remove those edges
384 boolean strongUpdate = false;
386 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
387 while( itrXhrn.hasNext() ) {
388 ReferenceEdge edgeX = itrXhrn.next();
389 HeapRegionNode hrnX = edgeX.getDst();
391 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
392 while( itrYhrn.hasNext() ) {
393 ReferenceEdge edgeY = itrYhrn.next();
394 HeapRegionNode hrnY = edgeY.getDst();
396 // we can do a strong update here if one of two cases holds
398 hrnX.isSingleObject() &&
399 ( (hrnX.getNumReferencers() == 1) ||
400 ( lnX.getNumReferencees() == 1)
404 clearReferenceEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
409 // then do all token propagation
410 itrXhrn = lnX.iteratorToReferencees();
411 while( itrXhrn.hasNext() ) {
412 ReferenceEdge edgeX = itrXhrn.next();
413 HeapRegionNode hrnX = edgeX.getDst();
414 ReachabilitySet betaX = edgeX.getBeta();
416 ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
418 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
419 while( itrYhrn.hasNext() ) {
420 ReferenceEdge edgeY = itrYhrn.next();
421 HeapRegionNode hrnY = edgeY.getDst();
422 ReachabilitySet O = edgeY.getBeta();
425 // propagate tokens over nodes starting from hrnSrc, and it will
426 // take care of propagating back up edges from any touched nodes
427 ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
428 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
431 // then propagate back just up the edges from hrn
432 ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
435 HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
437 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
438 new Hashtable<ReferenceEdge, ChangeTupleSet>();
440 Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
441 while( referItr.hasNext() ) {
442 ReferenceEdge edgeUpstream = referItr.next();
443 todoEdges.add(edgeUpstream);
444 edgePlannedChanges.put(edgeUpstream, Cx);
447 propagateTokensOverEdges(todoEdges,
454 // apply the updates to reachability
455 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
456 while( nodeItr.hasNext() ) {
457 nodeItr.next().applyAlphaNew();
460 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
461 while( edgeItr.hasNext() ) {
462 edgeItr.next().applyBetaNew();
465 // then go back through and add the new edges
466 itrXhrn = lnX.iteratorToReferencees();
467 while( itrXhrn.hasNext() ) {
468 ReferenceEdge edgeX = itrXhrn.next();
469 HeapRegionNode hrnX = edgeX.getDst();
471 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
472 while( itrYhrn.hasNext() ) {
473 ReferenceEdge edgeY = itrYhrn.next();
474 HeapRegionNode hrnY = edgeY.getDst();
476 // prepare the new reference edge hrnX.f -> hrnY
477 ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
482 edgeY.getBeta().pruneBy( hrnX.getAlpha() )
485 // look to see if an edge with same field exists
486 // and merge with it, otherwise just add the edge
487 ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY,
491 if( edgeExisting != null ) {
492 edgeExisting.setBeta(
493 edgeExisting.getBeta().union( edgeNew.getBeta() )
495 // a new edge here cannot be reflexive, so existing will
496 // always be also not reflexive anymore
497 edgeExisting.setIsInitialParam( false );
499 addReferenceEdge( hrnX, hrnY, edgeNew );
504 // if there was a strong update, make sure to improve
505 // reachability with a global sweep
512 // the parameter model is to use a single-object heap region
513 // for the primary parameter, and a multiple-object heap
514 // region for the secondary objects reachable through the
515 // primary object, if necessary
516 public void assignTempEqualToParamAlloc( TempDescriptor td,
518 Integer paramIndex ) {
521 TypeDescriptor typeParam = td.getType();
522 assert typeParam != null;
524 // either the parameter is an array or a class to be in this method
525 assert typeParam.isArray() || typeParam.isClass();
527 // discover some info from the param type and use it below
528 // to get parameter model as precise as we can
529 boolean createSecondaryRegion = false;
530 Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
531 Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
533 // there might be an element reference for array types
534 if( typeParam.isArray() ) {
535 // only bother with this if the dereferenced type can
536 // affect reachability
537 TypeDescriptor typeDeref = typeParam.dereference();
538 if( !typeDeref.isImmutable() || typeDeref.isArray() ) {
539 primary2secondaryFields.add(
540 OwnershipAnalysis.getArrayField( typeDeref )
542 createSecondaryRegion = true;
546 // there might be member references for class types
547 if( typeParam.isClass() ) {
548 ClassDescriptor cd = typeParam.getClassDesc();
549 while( cd != null ) {
551 Iterator fieldItr = cd.getFields();
552 while( fieldItr.hasNext() ) {
554 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
555 TypeDescriptor typeField = fd.getType();
556 assert typeField != null;
558 if( !typeField.isImmutable() || typeField.isArray() ) {
559 primary2secondaryFields.add( fd );
560 createSecondaryRegion = true;
563 if( typeUtil.isSuperorType( typeField, typeParam ) ) {
564 primary2primaryFields.add( fd );
568 cd = cd.getSuperDesc();
573 // now build everything we need
574 LabelNode lnParam = getLabelNodeFromTemp( td );
575 HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
576 true, // single object?
579 true, // is a parameter?
581 null, // allocation site
582 null, // reachability set
583 "param"+paramIndex+" obj" );
585 // this is a non-program-accessible label that picks up beta
586 // info to be used for fixing a caller of this method
587 TempDescriptor tdParamQ = new TempDescriptor( td+qString );
588 paramIndex2tdQ.put( paramIndex, tdParamQ );
589 LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
591 // keep track of heap regions that were created for
592 // parameter labels, the index of the parameter they
593 // are for is important when resolving method calls
594 Integer newPrimaryID = hrnPrimary.getID();
595 assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
596 Set<Integer> s = new HashSet<Integer>();
598 idPrimary2paramIndexSet.put( newPrimaryID, s );
599 paramIndex2idPrimary.put( paramIndex, newPrimaryID );
601 TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
602 false, // multi-object
603 TokenTuple.ARITY_ONE ).makeCanonical();
605 HeapRegionNode hrnSecondary = null;
606 Integer newSecondaryID = null;
607 TokenTuple ttSecondary = null;
608 TempDescriptor tdParamR = null;
609 LabelNode lnParamR = null;
611 if( createSecondaryRegion ) {
612 tdParamR = new TempDescriptor( td+rString );
613 paramIndex2tdR.put( paramIndex, tdParamR );
614 lnParamR = getLabelNodeFromTemp( tdParamR );
616 hrnSecondary = createNewHeapRegionNode( null, // id or null to generate a new one
617 false, // single object?
620 true, // is a parameter?
622 null, // allocation site
623 null, // reachability set
624 "param"+paramIndex+" reachable" );
626 newSecondaryID = hrnSecondary.getID();
627 assert !idSecondary2paramIndexSet.containsKey( newSecondaryID );
628 Set<Integer> s2 = new HashSet<Integer>();
629 s2.add( paramIndex );
630 idSecondary2paramIndexSet.put( newSecondaryID, s2 );
631 paramIndex2idSecondary.put( paramIndex, newSecondaryID );
633 ttSecondary = new TokenTuple( newSecondaryID,
634 true, // multi-object
635 TokenTuple.ARITY_ONE ).makeCanonical();
638 // use a beta that has everything and put it all over the
639 // parameter model, then use a global sweep later to fix
640 // it up, since parameters can have different shapes
641 TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
642 ReachabilitySet betaSoup;
643 if( createSecondaryRegion ) {
644 TokenTupleSet tts1 = new TokenTupleSet( ttSecondary ).makeCanonical();
645 TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).union( ttSecondary );
646 betaSoup = new ReachabilitySet().union( tts0 ).union( tts1 ).union( tts2 );
648 betaSoup = new ReachabilitySet().union( tts0 );
651 ReferenceEdge edgeFromLabel =
652 new ReferenceEdge( lnParam, // src
656 false, // special param initial (not needed on label->node)
657 betaSoup ); // reachability
658 addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
660 ReferenceEdge edgeFromLabelQ =
661 new ReferenceEdge( lnParamQ, // src
665 false, // special param initial (not needed on label->node)
666 betaSoup ); // reachability
667 addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
669 ReferenceEdge edgeSecondaryReflexive;
670 if( createSecondaryRegion ) {
671 edgeSecondaryReflexive =
672 new ReferenceEdge( hrnSecondary, // src
674 null, // match all types
675 null, // match all fields
676 true, // special param initial
677 betaSoup ); // reachability
678 addReferenceEdge( hrnSecondary, hrnSecondary, edgeSecondaryReflexive );
680 ReferenceEdge edgeSecondary2Primary =
681 new ReferenceEdge( hrnSecondary, // src
683 null, // match all types
684 null, // match all fields
685 true, // special param initial
686 betaSoup ); // reachability
687 addReferenceEdge( hrnSecondary, hrnPrimary, edgeSecondary2Primary );
689 ReferenceEdge edgeFromLabelR =
690 new ReferenceEdge( lnParamR, // src
694 false, // special param initial (not needed on label->node)
695 betaSoup ); // reachability
696 addReferenceEdge( lnParamR, hrnSecondary, edgeFromLabelR );
699 Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
700 while( fieldItr.hasNext() ) {
701 FieldDescriptor fd = fieldItr.next();
703 ReferenceEdge edgePrimaryReflexive =
704 new ReferenceEdge( hrnPrimary, // src
706 fd.getType(), // type
707 fd.getSymbol(), // field
708 true, // special param initial
709 betaSoup ); // reachability
710 addReferenceEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive );
713 fieldItr = primary2secondaryFields.iterator();
714 while( fieldItr.hasNext() ) {
715 FieldDescriptor fd = fieldItr.next();
717 ReferenceEdge edgePrimary2Secondary =
718 new ReferenceEdge( hrnPrimary, // src
720 fd.getType(), // type
721 fd.getSymbol(), // field
722 true, // special param initial
723 betaSoup ); // reachability
724 addReferenceEdge( hrnPrimary, hrnSecondary, edgePrimary2Secondary );
729 public void makeAliasedParamHeapRegionNode() {
731 LabelNode lnBlob = getLabelNodeFromTemp( tdAliasBlob );
732 HeapRegionNode hrn = createNewHeapRegionNode( null, // id or null to generate a new one
733 false, // single object?
736 true, // is a parameter?
738 null, // allocation site
739 null, // reachability set
742 ReachabilitySet beta = new ReachabilitySet( new TokenTuple( hrn.getID(),
744 TokenTuple.ARITY_ONE).makeCanonical()
747 ReferenceEdge edgeFromLabel =
748 new ReferenceEdge( lnBlob, hrn, null, null, false, beta );
750 ReferenceEdge edgeReflexive =
751 new ReferenceEdge( hrn, hrn, null, null, true, beta );
753 addReferenceEdge( lnBlob, hrn, edgeFromLabel );
754 addReferenceEdge( hrn, hrn, edgeReflexive );
758 public void assignTempEqualToAliasedParam( TempDescriptor tdParam,
759 Integer paramIndex ) {
760 assert tdParam != null;
762 TypeDescriptor typeParam = tdParam.getType();
763 assert typeParam != null;
765 LabelNode lnParam = getLabelNodeFromTemp( tdParam );
766 LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob );
768 // this is a non-program-accessible label that picks up beta
769 // info to be used for fixing a caller of this method
770 TempDescriptor tdParamQ = new TempDescriptor( tdParam+qString );
771 TempDescriptor tdParamR = new TempDescriptor( tdParam+rString );
773 paramIndex2tdQ.put( paramIndex, tdParamQ );
774 paramIndex2tdR.put( paramIndex, tdParamR );
776 LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
777 LabelNode lnParamR = getLabelNodeFromTemp( tdParamR );
779 // the lnAliased should always only reference one node, and that
780 // heap region node is the aliased param blob
781 assert lnAliased.getNumReferencees() == 1;
782 HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
783 Integer idAliased = hrnAliasBlob.getID();
785 TokenTuple ttAliased = new TokenTuple( idAliased,
786 true, // multi-object
787 TokenTuple.ARITY_ONE ).makeCanonical();
789 HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
790 true, // single object?
793 true, // is a parameter?
795 null, // allocation site
796 null, // reachability set
797 "param"+paramIndex+" obj" );
799 Integer newPrimaryID = hrnPrimary.getID();
800 assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
801 Set<Integer> s1 = new HashSet<Integer>();
802 s1.add( paramIndex );
803 idPrimary2paramIndexSet.put( newPrimaryID, s1 );
804 paramIndex2idPrimary.put( paramIndex, newPrimaryID );
806 Set<Integer> s2 = idSecondary2paramIndexSet.get( idAliased );
808 s2 = new HashSet<Integer>();
810 s2.add( paramIndex );
811 idSecondary2paramIndexSet.put( idAliased, s2 );
812 paramIndex2idSecondary.put( paramIndex, idAliased );
815 TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
816 false, // multi-object
817 TokenTuple.ARITY_ONE ).makeCanonical();
819 TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
820 TokenTupleSet tts1 = new TokenTupleSet( ttAliased ).makeCanonical();
821 TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).union( ttAliased );
822 ReachabilitySet betaSoup = new ReachabilitySet().union( tts0 ).union( tts1 ).union( tts2 );
825 ReferenceEdge edgeFromLabel =
826 new ReferenceEdge( lnParam, // src
830 false, // special param initial (not needed on label->node)
831 betaSoup ); // reachability
832 addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
834 ReferenceEdge edgeFromLabelQ =
835 new ReferenceEdge( lnParamQ, // src
839 false, // special param initial (not needed on label->node)
840 betaSoup ); // reachability
841 addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
843 ReferenceEdge edgeAliased2Primary =
844 new ReferenceEdge( hrnAliasBlob, // src
846 null, // match all types
847 null, // match all fields
848 true, // special param initial
849 betaSoup ); // reachability
850 addReferenceEdge( hrnAliasBlob, hrnPrimary, edgeAliased2Primary );
852 ReferenceEdge edgeFromLabelR =
853 new ReferenceEdge( lnParamR, // src
857 false, // special param initial (not needed on label->node)
858 betaSoup ); // reachability
859 addReferenceEdge( lnParamR, hrnAliasBlob, edgeFromLabelR );
863 public void addParam2ParamAliasEdges( FlatMethod fm,
864 Set<Integer> aliasedParamIndices ) {
866 LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob );
868 // the lnAliased should always only reference one node, and that
869 // heap region node is the aliased param blob
870 assert lnAliased.getNumReferencees() == 1;
871 HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
872 Integer idAliased = hrnAliasBlob.getID();
873 TokenTuple ttAliased = new TokenTuple( idAliased,
874 true, // multi-object
875 TokenTuple.ARITY_ONE ).makeCanonical();
878 Iterator<Integer> apItrI = aliasedParamIndices.iterator();
879 while( apItrI.hasNext() ) {
880 Integer i = apItrI.next();
881 TempDescriptor tdParamI = fm.getParameter( i );
882 TypeDescriptor typeI = tdParamI.getType();
883 LabelNode lnParamI = getLabelNodeFromTemp( tdParamI );
885 Integer idPrimaryI = paramIndex2idPrimary.get( i );
886 assert idPrimaryI != null;
887 HeapRegionNode primaryI = id2hrn.get( idPrimaryI );
888 assert primaryI != null;
890 TokenTuple ttPrimaryI = new TokenTuple( idPrimaryI,
891 false, // multi-object
892 TokenTuple.ARITY_ONE ).makeCanonical();
894 TokenTupleSet ttsI = new TokenTupleSet( ttPrimaryI ).makeCanonical();
895 TokenTupleSet ttsA = new TokenTupleSet( ttAliased ).makeCanonical();
896 TokenTupleSet ttsIA = new TokenTupleSet( ttPrimaryI ).union( ttAliased );
897 ReachabilitySet betaSoup = new ReachabilitySet().union( ttsI ).union( ttsA ).union( ttsIA );
900 // calculate whether fields of this aliased parameter are able to
901 // reference its own primary object, the blob, or other parameter's
903 Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
904 Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
906 // there might be an element reference for array types
907 if( typeI.isArray() ) {
908 // only bother with this if the dereferenced type can
909 // affect reachability
910 TypeDescriptor typeDeref = typeI.dereference();
912 // for this parameter to be aliased the following must be true
913 assert !typeDeref.isImmutable() || typeDeref.isArray();
915 primary2secondaryFields.add(
916 OwnershipAnalysis.getArrayField( typeDeref )
920 // there might be member references for class types
921 if( typeI.isClass() ) {
922 ClassDescriptor cd = typeI.getClassDesc();
923 while( cd != null ) {
925 Iterator fieldItr = cd.getFields();
926 while( fieldItr.hasNext() ) {
928 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
929 TypeDescriptor typeField = fd.getType();
930 assert typeField != null;
932 if( !typeField.isImmutable() || typeField.isArray() ) {
933 primary2secondaryFields.add( fd );
936 if( typeUtil.isSuperorType( typeField, typeI ) ) {
937 primary2primaryFields.add( fd );
941 cd = cd.getSuperDesc();
945 Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
946 while( fieldItr.hasNext() ) {
947 FieldDescriptor fd = fieldItr.next();
949 ReferenceEdge edgePrimaryReflexive =
950 new ReferenceEdge( primaryI, // src
952 fd.getType(), // type
953 fd.getSymbol(), // field
954 true, // special param initial
955 betaSoup ); // reachability
956 addReferenceEdge( primaryI, primaryI, edgePrimaryReflexive );
959 fieldItr = primary2secondaryFields.iterator();
960 while( fieldItr.hasNext() ) {
961 FieldDescriptor fd = fieldItr.next();
962 TypeDescriptor typeField = fd.getType();
963 assert typeField != null;
965 ReferenceEdge edgePrimary2Secondary =
966 new ReferenceEdge( primaryI, // src
968 fd.getType(), // type
969 fd.getSymbol(), // field
970 true, // special param initial
971 betaSoup ); // reachability
972 addReferenceEdge( primaryI, hrnAliasBlob, edgePrimary2Secondary );
974 // ask whether these fields might match any of the other aliased
975 // parameters and make those edges too
976 Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
977 while( apItrJ.hasNext() ) {
978 Integer j = apItrJ.next();
979 TempDescriptor tdParamJ = fm.getParameter( j );
980 TypeDescriptor typeJ = tdParamJ.getType();
982 if( !i.equals( j ) && typeUtil.isSuperorType( typeField, typeJ ) ) {
984 Integer idPrimaryJ = paramIndex2idPrimary.get( j );
985 assert idPrimaryJ != null;
986 HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
987 assert primaryJ != null;
989 TokenTuple ttPrimaryJ = new TokenTuple( idPrimaryJ,
990 false, // multi-object
991 TokenTuple.ARITY_ONE ).makeCanonical();
993 TokenTupleSet ttsJ = new TokenTupleSet( ttPrimaryJ ).makeCanonical();
994 TokenTupleSet ttsIJ = ttsI.union( ttsJ );
995 TokenTupleSet ttsAJ = ttsA.union( ttsJ );
996 TokenTupleSet ttsIAJ = ttsIA.union( ttsJ );
997 ReachabilitySet betaSoupWJ = new ReachabilitySet().union( ttsJ ).union( ttsIJ ).union( ttsAJ ).union( ttsIAJ );
999 ReferenceEdge edgePrimaryI2PrimaryJ =
1000 new ReferenceEdge( primaryI, // src
1002 fd.getType(), // type
1003 fd.getSymbol(), // field
1004 true, // special param initial
1005 betaSoupWJ ); // reachability
1006 addReferenceEdge( primaryI, primaryJ, edgePrimaryI2PrimaryJ );
1012 // look at whether aliased parameters i and j can
1013 // possibly be the same primary object, add edges
1014 Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
1015 while( apItrJ.hasNext() ) {
1016 Integer j = apItrJ.next();
1017 TempDescriptor tdParamJ = fm.getParameter( j );
1018 TypeDescriptor typeJ = tdParamJ.getType();
1019 LabelNode lnParamJ = getLabelNodeFromTemp( tdParamJ );
1021 if( !i.equals( j ) && typeUtil.isSuperorType( typeI, typeJ ) ) {
1023 Integer idPrimaryJ = paramIndex2idPrimary.get( j );
1024 assert idPrimaryJ != null;
1025 HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
1026 assert primaryJ != null;
1028 ReferenceEdge lnJ2PrimaryJ = lnParamJ.getReferenceTo( primaryJ,
1031 assert lnJ2PrimaryJ != null;
1033 ReferenceEdge lnI2PrimaryJ = lnJ2PrimaryJ.copy();
1034 lnI2PrimaryJ.setSrc( lnParamI );
1035 lnI2PrimaryJ.setType( tdParamI.getType() );
1036 addReferenceEdge( lnParamI, primaryJ, lnI2PrimaryJ );
1042 public void prepareParamTokenMaps( FlatMethod fm ) {
1044 // always add the bogus mappings that are used to
1045 // rewrite "with respect to no parameter"
1046 paramTokenPrimary2paramIndex.put( bogusToken, bogusIndex );
1047 paramIndex2paramTokenPrimary.put( bogusIndex, bogusToken );
1049 paramTokenSecondary2paramIndex.put( bogusToken, bogusIndex );
1050 paramIndex2paramTokenSecondary.put( bogusIndex, bogusToken );
1051 paramTokenSecondaryPlus2paramIndex.put( bogusTokenPlus, bogusIndex );
1052 paramIndex2paramTokenSecondaryPlus.put( bogusIndex, bogusTokenPlus );
1053 paramTokenSecondaryStar2paramIndex.put( bogusTokenStar, bogusIndex );
1054 paramIndex2paramTokenSecondaryStar.put( bogusIndex, bogusTokenStar );
1056 for( int i = 0; i < fm.numParameters(); ++i ) {
1057 Integer paramIndex = new Integer( i );
1059 // immutable objects have no primary regions
1060 if( paramIndex2idPrimary.containsKey( paramIndex ) ) {
1061 Integer idPrimary = paramIndex2idPrimary.get( paramIndex );
1063 assert id2hrn.containsKey( idPrimary );
1064 HeapRegionNode hrnPrimary = id2hrn.get( idPrimary );
1066 TokenTuple p_i = new TokenTuple( hrnPrimary.getID(),
1067 false, // multiple-object?
1068 TokenTuple.ARITY_ONE ).makeCanonical();
1069 paramTokenPrimary2paramIndex.put( p_i, paramIndex );
1070 paramIndex2paramTokenPrimary.put( paramIndex, p_i );
1073 // any parameter object, by type, may have no secondary region
1074 if( paramIndex2idSecondary.containsKey( paramIndex ) ) {
1075 Integer idSecondary = paramIndex2idSecondary.get( paramIndex );
1077 assert id2hrn.containsKey( idSecondary );
1078 HeapRegionNode hrnSecondary = id2hrn.get( idSecondary );
1080 TokenTuple s_i = new TokenTuple( hrnSecondary.getID(),
1081 true, // multiple-object?
1082 TokenTuple.ARITY_ONE ).makeCanonical();
1083 paramTokenSecondary2paramIndex.put( s_i, paramIndex );
1084 paramIndex2paramTokenSecondary.put( paramIndex, s_i );
1086 TokenTuple s_i_plus = new TokenTuple( hrnSecondary.getID(),
1087 true, // multiple-object?
1088 TokenTuple.ARITY_ONEORMORE ).makeCanonical();
1089 paramTokenSecondaryPlus2paramIndex.put( s_i_plus, paramIndex );
1090 paramIndex2paramTokenSecondaryPlus.put( paramIndex, s_i_plus );
1092 TokenTuple s_i_star = new TokenTuple( hrnSecondary.getID(),
1093 true, // multiple-object?
1094 TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
1095 paramTokenSecondaryStar2paramIndex.put( s_i_star, paramIndex );
1096 paramIndex2paramTokenSecondaryStar.put( paramIndex, s_i_star );
1103 public void assignReturnEqualToTemp(TempDescriptor x) {
1105 LabelNode lnR = getLabelNodeFromTemp(tdReturn);
1106 LabelNode lnX = getLabelNodeFromTemp(x);
1108 clearReferenceEdgesFrom(lnR, null, null, true);
1110 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
1111 while( itrXhrn.hasNext() ) {
1112 ReferenceEdge edgeX = itrXhrn.next();
1113 HeapRegionNode referencee = edgeX.getDst();
1114 ReferenceEdge edgeNew = edgeX.copy();
1115 edgeNew.setSrc(lnR);
1117 addReferenceEdge(lnR, referencee, edgeNew);
1122 public void assignTempEqualToNewAlloc(TempDescriptor x,
1123 AllocationSite as) {
1129 // after the age operation the newest (or zero-ith oldest)
1130 // node associated with the allocation site should have
1131 // no references to it as if it were a newly allocated
1132 // heap region, so make a reference to it to complete
1135 Integer idNewest = as.getIthOldest(0);
1136 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
1137 assert hrnNewest != null;
1139 LabelNode lnX = getLabelNodeFromTemp(x);
1140 clearReferenceEdgesFrom(lnX, null, null, true);
1142 ReferenceEdge edgeNew =
1143 new ReferenceEdge(lnX, hrnNewest, null, null, false, hrnNewest.getAlpha() );
1145 addReferenceEdge(lnX, hrnNewest, edgeNew);
1149 // use the allocation site (unique to entire analysis) to
1150 // locate the heap region nodes in this ownership graph
1151 // that should be aged. The process models the allocation
1152 // of new objects and collects all the oldest allocations
1153 // in a summary node to allow for a finite analysis
1155 // There is an additional property of this method. After
1156 // running it on a particular ownership graph (many graphs
1157 // may have heap regions related to the same allocation site)
1158 // the heap region node objects in this ownership graph will be
1159 // allocated. Therefore, after aging a graph for an allocation
1160 // site, attempts to retrieve the heap region nodes using the
1161 // integer id's contained in the allocation site should always
1162 // return non-null heap regions.
1163 public void age(AllocationSite as) {
1165 // aging adds this allocation site to the graph's
1166 // list of sites that exist in the graph, or does
1167 // nothing if the site is already in the list
1168 allocationSites.add(as);
1170 // get the summary node for the allocation site in the context
1171 // of this particular ownership graph
1172 HeapRegionNode hrnSummary = getSummaryNode(as);
1174 // merge oldest node into summary
1175 Integer idK = as.getOldest();
1176 HeapRegionNode hrnK = id2hrn.get(idK);
1177 mergeIntoSummary(hrnK, hrnSummary);
1179 // move down the line of heap region nodes
1180 // clobbering the ith and transferring all references
1181 // to and from i-1 to node i. Note that this clobbers
1182 // the oldest node (hrnK) that was just merged into
1184 for( int i = allocationDepth - 1; i > 0; --i ) {
1186 // move references from the i-1 oldest to the ith oldest
1187 Integer idIth = as.getIthOldest(i);
1188 HeapRegionNode hrnI = id2hrn.get(idIth);
1189 Integer idImin1th = as.getIthOldest(i - 1);
1190 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
1192 transferOnto(hrnImin1, hrnI);
1195 // as stated above, the newest node should have had its
1196 // references moved over to the second oldest, so we wipe newest
1197 // in preparation for being the new object to assign something to
1198 Integer id0th = as.getIthOldest(0);
1199 HeapRegionNode hrn0 = id2hrn.get(id0th);
1200 assert hrn0 != null;
1202 // clear all references in and out of newest node
1203 clearReferenceEdgesFrom(hrn0, null, null, true);
1204 clearReferenceEdgesTo(hrn0, null, null, true);
1207 // now tokens in reachability sets need to "age" also
1208 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1209 while( itrAllLabelNodes.hasNext() ) {
1210 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1211 LabelNode ln = (LabelNode) me.getValue();
1213 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1214 while( itrEdges.hasNext() ) {
1215 ageTokens(as, itrEdges.next() );
1219 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1220 while( itrAllHRNodes.hasNext() ) {
1221 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1222 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1224 ageTokens(as, hrnToAge);
1226 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1227 while( itrEdges.hasNext() ) {
1228 ageTokens(as, itrEdges.next() );
1233 // after tokens have been aged, reset newest node's reachability
1234 if( hrn0.isFlagged() ) {
1235 hrn0.setAlpha(new ReachabilitySet(
1237 new TokenTuple(hrn0).makeCanonical()
1242 hrn0.setAlpha(new ReachabilitySet(
1243 new TokenTupleSet().makeCanonical()
1250 protected HeapRegionNode getSummaryNode(AllocationSite as) {
1252 Integer idSummary = as.getSummary();
1253 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
1255 // If this is null then we haven't touched this allocation site
1256 // in the context of the current ownership graph, so allocate
1257 // heap region nodes appropriate for the entire allocation site.
1258 // This should only happen once per ownership graph per allocation site,
1259 // and a particular integer id can be used to locate the heap region
1260 // in different ownership graphs that represents the same part of an
1262 if( hrnSummary == null ) {
1264 boolean hasFlags = false;
1265 if( as.getType().isClass() ) {
1266 hasFlags = as.getType().getClassDesc().hasFlags();
1269 hrnSummary = createNewHeapRegionNode(idSummary, // id or null to generate a new one
1270 false, // single object?
1272 hasFlags, // flagged?
1273 false, // is a parameter?
1274 as.getType(), // type
1275 as, // allocation site
1276 null, // reachability set
1277 as.toStringForDOT() + "\\nsummary");
1279 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1280 Integer idIth = as.getIthOldest(i);
1281 assert !id2hrn.containsKey(idIth);
1282 createNewHeapRegionNode(idIth, // id or null to generate a new one
1283 true, // single object?
1285 hasFlags, // flagged?
1286 false, // is a parameter?
1287 as.getType(), // type
1288 as, // allocation site
1289 null, // reachability set
1290 as.toStringForDOT() + "\\n" + i + " oldest");
1298 protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
1300 Integer idShadowSummary = as.getSummaryShadow();
1301 HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
1303 if( hrnShadowSummary == null ) {
1305 boolean hasFlags = false;
1306 if( as.getType().isClass() ) {
1307 hasFlags = as.getType().getClassDesc().hasFlags();
1310 hrnShadowSummary = createNewHeapRegionNode(idShadowSummary, // id or null to generate a new one
1311 false, // single object?
1313 hasFlags, // flagged?
1314 false, // is a parameter?
1315 as.getType(), // type
1316 as, // allocation site
1317 null, // reachability set
1318 as + "\\n" + as.getType() + "\\nshadowSum");
1320 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1321 Integer idShadowIth = as.getIthOldestShadow(i);
1322 assert !id2hrn.containsKey(idShadowIth);
1323 createNewHeapRegionNode(idShadowIth, // id or null to generate a new one
1324 true, // single object?
1326 hasFlags, // flagged?
1327 false, // is a parameter?
1328 as.getType(), // type
1329 as, // allocation site
1330 null, // reachability set
1331 as + "\\n" + as.getType() + "\\n" + i + " shadow");
1335 return hrnShadowSummary;
1339 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
1340 assert hrnSummary.isNewSummary();
1342 // transfer references _from_ hrn over to hrnSummary
1343 Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
1344 while( itrReferencee.hasNext() ) {
1345 ReferenceEdge edge = itrReferencee.next();
1346 ReferenceEdge edgeMerged = edge.copy();
1347 edgeMerged.setSrc(hrnSummary);
1349 HeapRegionNode hrnReferencee = edge.getDst();
1350 ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee,
1354 if( edgeSummary == null ) {
1355 // the merge is trivial, nothing to be done
1357 // otherwise an edge from the referencer to hrnSummary exists already
1358 // and the edge referencer->hrn should be merged with it
1359 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1362 addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
1365 // next transfer references _to_ hrn over to hrnSummary
1366 Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
1367 while( itrReferencer.hasNext() ) {
1368 ReferenceEdge edge = itrReferencer.next();
1369 ReferenceEdge edgeMerged = edge.copy();
1370 edgeMerged.setDst(hrnSummary);
1372 OwnershipNode onReferencer = edge.getSrc();
1373 ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary,
1377 if( edgeSummary == null ) {
1378 // the merge is trivial, nothing to be done
1380 // otherwise an edge from the referencer to alpha_S exists already
1381 // and the edge referencer->alpha_K should be merged with it
1382 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1385 addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
1388 // then merge hrn reachability into hrnSummary
1389 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
1393 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
1395 // clear references in and out of node b
1396 clearReferenceEdgesFrom(hrnB, null, null, true);
1397 clearReferenceEdgesTo(hrnB, null, null, true);
1399 // copy each edge in and out of A to B
1400 Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
1401 while( itrReferencee.hasNext() ) {
1402 ReferenceEdge edge = itrReferencee.next();
1403 HeapRegionNode hrnReferencee = edge.getDst();
1404 ReferenceEdge edgeNew = edge.copy();
1405 edgeNew.setSrc(hrnB);
1407 addReferenceEdge(hrnB, hrnReferencee, edgeNew);
1410 Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
1411 while( itrReferencer.hasNext() ) {
1412 ReferenceEdge edge = itrReferencer.next();
1413 OwnershipNode onReferencer = edge.getSrc();
1414 ReferenceEdge edgeNew = edge.copy();
1415 edgeNew.setDst(hrnB);
1417 addReferenceEdge(onReferencer, hrnB, edgeNew);
1420 // replace hrnB reachability with hrnA's
1421 hrnB.setAlpha(hrnA.getAlpha() );
1425 protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
1426 edge.setBeta(edge.getBeta().ageTokens(as) );
1429 protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
1430 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
1435 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1437 HashSet<HeapRegionNode> nodesWithNewAlpha,
1438 HashSet<ReferenceEdge> edgesWithNewBeta) {
1440 HashSet<HeapRegionNode> todoNodes
1441 = new HashSet<HeapRegionNode>();
1442 todoNodes.add(nPrime);
1444 HashSet<ReferenceEdge> todoEdges
1445 = new HashSet<ReferenceEdge>();
1447 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
1448 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
1449 nodePlannedChanges.put(nPrime, c0);
1451 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
1452 = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1454 // first propagate change sets everywhere they can go
1455 while( !todoNodes.isEmpty() ) {
1456 HeapRegionNode n = todoNodes.iterator().next();
1457 ChangeTupleSet C = nodePlannedChanges.get(n);
1459 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
1460 while( referItr.hasNext() ) {
1461 ReferenceEdge edge = referItr.next();
1462 todoEdges.add(edge);
1464 if( !edgePlannedChanges.containsKey(edge) ) {
1465 edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
1468 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
1471 Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
1472 while( refeeItr.hasNext() ) {
1473 ReferenceEdge edgeF = refeeItr.next();
1474 HeapRegionNode m = edgeF.getDst();
1476 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
1478 Iterator<ChangeTuple> itrCprime = C.iterator();
1479 while( itrCprime.hasNext() ) {
1480 ChangeTuple c = itrCprime.next();
1481 if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
1482 changesToPass = changesToPass.union(c);
1486 if( !changesToPass.isEmpty() ) {
1487 if( !nodePlannedChanges.containsKey(m) ) {
1488 nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
1491 ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
1493 if( !changesToPass.isSubset(currentChanges) ) {
1495 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
1501 todoNodes.remove(n);
1504 // then apply all of the changes for each node at once
1505 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1506 while( itrMap.hasNext() ) {
1507 Map.Entry me = (Map.Entry) itrMap.next();
1508 HeapRegionNode n = (HeapRegionNode) me.getKey();
1509 ChangeTupleSet C = (ChangeTupleSet) me.getValue();
1511 n.setAlphaNew( n.getAlpha().applyChangeSet( C, false ) );
1512 nodesWithNewAlpha.add( n );
1515 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
1519 protected void propagateTokensOverEdges(
1520 HashSet<ReferenceEdge> todoEdges,
1521 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
1522 HashSet<ReferenceEdge> edgesWithNewBeta) {
1524 // first propagate all change tuples everywhere they can go
1525 while( !todoEdges.isEmpty() ) {
1526 ReferenceEdge edgeE = todoEdges.iterator().next();
1527 todoEdges.remove(edgeE);
1529 if( !edgePlannedChanges.containsKey(edgeE) ) {
1530 edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
1533 ChangeTupleSet C = edgePlannedChanges.get(edgeE);
1535 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
1538 Iterator<ChangeTuple> itrC = C.iterator();
1539 while( itrC.hasNext() ) {
1540 ChangeTuple c = itrC.next();
1541 if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1542 changesToPass = changesToPass.union(c);
1546 OwnershipNode onSrc = edgeE.getSrc();
1548 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
1549 HeapRegionNode n = (HeapRegionNode) onSrc;
1551 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
1552 while( referItr.hasNext() ) {
1553 ReferenceEdge edgeF = referItr.next();
1555 if( !edgePlannedChanges.containsKey(edgeF) ) {
1556 edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
1559 ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
1561 if( !changesToPass.isSubset(currentChanges) ) {
1562 todoEdges.add(edgeF);
1563 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
1569 // then apply all of the changes for each edge at once
1570 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1571 while( itrMap.hasNext() ) {
1572 Map.Entry me = (Map.Entry) itrMap.next();
1573 ReferenceEdge e = (ReferenceEdge) me.getKey();
1574 ChangeTupleSet C = (ChangeTupleSet) me.getValue();
1576 e.setBetaNew( e.getBeta().applyChangeSet( C, true ) );
1577 edgesWithNewBeta.add( e );
1582 public Set<Integer> calculateAliasedParamSet(FlatCall fc,
1586 Hashtable<Integer, LabelNode> paramIndex2ln =
1587 new Hashtable<Integer, LabelNode>();
1589 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
1590 new Hashtable<Integer, HashSet<HeapRegionNode> >();
1592 for( int i = 0; i < fm.numParameters(); ++i ) {
1593 Integer paramIndex = new Integer(i);
1595 // now depending on whether the callee is static or not
1596 // we need to account for a "this" argument in order to
1597 // find the matching argument in the caller context
1598 TempDescriptor argTemp_i;
1600 argTemp_i = fc.getArg(paramIndex);
1602 if( paramIndex.equals(0) ) {
1603 argTemp_i = fc.getThis();
1605 argTemp_i = fc.getArg(paramIndex - 1);
1609 // in non-static methods there is a "this" pointer
1610 // that should be taken into account
1612 assert fc.numArgs() == fm.numParameters();
1614 assert fc.numArgs() + 1 == fm.numParameters();
1617 LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1618 paramIndex2ln.put(paramIndex, argLabel_i);
1621 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1622 while( lnArgItr.hasNext() ) {
1623 Map.Entry me = (Map.Entry)lnArgItr.next();
1624 Integer index = (Integer) me.getKey();
1625 LabelNode lnArg_i = (LabelNode) me.getValue();
1627 // rewrite alpha for the nodes reachable from argument label i
1628 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1629 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1631 // to find all reachable nodes, start with label referencees
1632 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1633 while( edgeArgItr.hasNext() ) {
1634 ReferenceEdge edge = edgeArgItr.next();
1635 todoNodes.add(edge.getDst() );
1638 // then follow links until all reachable nodes have been found
1639 while( !todoNodes.isEmpty() ) {
1640 HeapRegionNode hrn = todoNodes.iterator().next();
1641 todoNodes.remove(hrn);
1642 reachableNodes.add(hrn);
1644 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1645 while( edgeItr.hasNext() ) {
1646 ReferenceEdge edge = edgeItr.next();
1648 if( !reachableNodes.contains(edge.getDst() ) ) {
1649 todoNodes.add(edge.getDst() );
1655 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1658 Set<Integer> aliasedIndices = new HashSet<Integer>();
1660 // check for arguments that are aliased
1661 for( int i = 0; i < fm.numParameters(); ++i ) {
1662 for( int j = 0; j < i; ++j ) {
1663 HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
1664 HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
1666 Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
1667 intersection.retainAll(s2);
1669 if( !intersection.isEmpty() ) {
1670 aliasedIndices.add( new Integer( i ) );
1671 aliasedIndices.add( new Integer( j ) );
1676 return aliasedIndices;
1680 private String makeMapKey( Integer i, Integer j, String field ) {
1681 return i+","+j+","+field;
1684 private String makeMapKey( Integer i, String field ) {
1688 // these hashtables are used during the mapping procedure to say that
1689 // with respect to some argument i there is an edge placed into some
1690 // category for mapping with respect to another argument index j
1691 // so the key into the hashtable is i, the value is a two-element vector
1692 // that contains in 0 the edge and in 1 the Integer index j
1693 private void ensureEmptyEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
1696 Set<Vector> ei = edge_index_pairs.get( indexI );
1698 ei = new HashSet<Vector>();
1700 edge_index_pairs.put( indexI, ei );
1703 private void addEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
1708 Vector v = new Vector(); v.setSize( 2 );
1710 v.set( 1 , indexJ );
1711 Set<Vector> ei = edge_index_pairs.get( indexI );
1713 ei = new HashSet<Vector>();
1716 edge_index_pairs.put( indexI, ei );
1719 private ReachabilitySet funcScriptR( ReachabilitySet rsIn,
1720 OwnershipGraph ogCallee,
1721 MethodContext mc ) {
1723 ReachabilitySet rsOut = new ReachabilitySet( rsIn );
1725 Iterator itr = ogCallee.paramIndex2paramTokenPrimary.entrySet().iterator();
1726 while( itr.hasNext() ) {
1727 Map.Entry me = (Map.Entry) itr.next();
1728 Integer i = (Integer) me.getKey();
1729 TokenTuple p_i = (TokenTuple) me.getValue();
1730 TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( i );
1732 // skip this if there is no secondary token or the parameter
1733 // is part of the aliasing context
1734 if( s_i == null || mc.getAliasedParamIndices().contains( i ) ) {
1738 rsOut = rsOut.removeTokenAIfTokenB( p_i, s_i );
1744 public void resolveMethodCall(FlatCall fc,
1747 OwnershipGraph ogCallee,
1751 String debugCaller = "foo";
1752 String debugCallee = "bar";
1754 if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
1755 fm.getMethod().getSymbol().equals( debugCallee ) ) {
1758 writeGraph( "debug1Before", true, true, true, false, false );
1759 ogCallee.writeGraph( "debug0Callee", true, true, true, false, false );
1760 } catch( IOException e ) {}
1762 System.out.println( " "+mc+" is calling "+fm );
1766 // define rewrite rules and other structures to organize data by parameter/argument index
1767 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_p = new Hashtable<Integer, ReachabilitySet>();
1768 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_s = new Hashtable<Integer, ReachabilitySet>();
1770 Hashtable<String, ReachabilitySet> paramIndex2rewriteJ_p2p = new Hashtable<String, ReachabilitySet>(); // select( i, j, f )
1771 Hashtable<String, ReachabilitySet> paramIndex2rewriteJ_p2s = new Hashtable<String, ReachabilitySet>(); // select( i, f )
1772 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2p = new Hashtable<Integer, ReachabilitySet>();
1773 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2s = new Hashtable<Integer, ReachabilitySet>();
1775 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p = new Hashtable<Integer, ReachabilitySet>();
1776 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p2 = new Hashtable<Integer, ReachabilitySet>();
1777 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_s = new Hashtable<Integer, ReachabilitySet>();
1779 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_p = new Hashtable<Integer, ReachabilitySet>();
1780 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_s = new Hashtable<Integer, ReachabilitySet>();
1782 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD = new Hashtable<Integer, ReachabilitySet>();
1785 Hashtable<Integer, LabelNode> paramIndex2ln = new Hashtable<Integer, LabelNode>();
1788 paramIndex2rewriteH_p.put( bogusIndex, rsIdentity );
1789 paramIndex2rewriteH_s.put( bogusIndex, rsIdentity );
1791 paramIndex2rewriteJ_p2p.put( bogusIndex.toString(), rsIdentity );
1792 paramIndex2rewriteJ_p2s.put( bogusIndex.toString(), rsIdentity );
1793 paramIndex2rewriteJ_s2p.put( bogusIndex, rsIdentity );
1794 paramIndex2rewriteJ_s2s.put( bogusIndex, rsIdentity );
1797 for( int i = 0; i < fm.numParameters(); ++i ) {
1798 Integer paramIndex = new Integer(i);
1800 if( !ogCallee.paramIndex2idPrimary.containsKey( paramIndex ) ) {
1801 // skip this immutable parameter
1805 // setup H (primary)
1806 Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
1807 assert ogCallee.id2hrn.containsKey( idPrimary );
1808 HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
1809 assert hrnPrimary != null;
1810 paramIndex2rewriteH_p.put( paramIndex, toShadowTokens( ogCallee, hrnPrimary.getAlpha() ) );
1812 // setup J (primary->X)
1813 Iterator<ReferenceEdge> p2xItr = hrnPrimary.iteratorToReferencees();
1814 while( p2xItr.hasNext() ) {
1815 ReferenceEdge p2xEdge = p2xItr.next();
1817 // we only care about initial parameter edges here
1818 if( !p2xEdge.isInitialParam() ) { continue; }
1820 HeapRegionNode hrnDst = p2xEdge.getDst();
1822 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
1823 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
1824 while( jItr.hasNext() ) {
1825 Integer j = jItr.next();
1826 paramIndex2rewriteJ_p2p.put( makeMapKey( i, j, p2xEdge.getField() ),
1827 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
1831 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
1832 paramIndex2rewriteJ_p2s.put( makeMapKey( i, p2xEdge.getField() ),
1833 toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
1837 // setup K (primary)
1838 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
1839 assert tdParamQ != null;
1840 LabelNode lnParamQ = ogCallee.td2ln.get( tdParamQ );
1841 assert lnParamQ != null;
1842 ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnPrimary, null, null );
1843 assert edgeSpecialQ_i != null;
1844 ReachabilitySet qBeta = toShadowTokens( ogCallee, edgeSpecialQ_i.getBeta() );
1846 TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary .get( paramIndex );
1847 TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( paramIndex );
1849 ReachabilitySet K_p = new ReachabilitySet().makeCanonical();
1850 ReachabilitySet K_p2 = new ReachabilitySet().makeCanonical();
1854 // sort qBeta into K_p1 and K_p2
1855 Iterator<TokenTupleSet> ttsItr = qBeta.iterator();
1856 while( ttsItr.hasNext() ) {
1857 TokenTupleSet tts = ttsItr.next();
1858 if( s_i != null && tts.containsBoth( p_i, s_i ) ) {
1859 K_p2 = K_p2.union( tts );
1861 K_p = K_p.union( tts );
1865 paramIndex2rewriteK_p .put( paramIndex, K_p );
1866 paramIndex2rewriteK_p2.put( paramIndex, K_p2 );
1869 // if there is a secondary node, compute the rest of the rewrite rules
1870 if( ogCallee.paramIndex2idSecondary.containsKey( paramIndex ) ) {
1872 // setup H (secondary)
1873 Integer idSecondary = ogCallee.paramIndex2idSecondary.get( paramIndex );
1874 assert ogCallee.id2hrn.containsKey( idSecondary );
1875 HeapRegionNode hrnSecondary = ogCallee.id2hrn.get( idSecondary );
1876 assert hrnSecondary != null;
1877 paramIndex2rewriteH_s.put( paramIndex, toShadowTokens( ogCallee, hrnSecondary.getAlpha() ) );
1879 // setup J (secondary->X)
1880 Iterator<ReferenceEdge> s2xItr = hrnSecondary.iteratorToReferencees();
1881 while( s2xItr.hasNext() ) {
1882 ReferenceEdge s2xEdge = s2xItr.next();
1884 if( !s2xEdge.isInitialParam() ) { continue; }
1886 HeapRegionNode hrnDst = s2xEdge.getDst();
1888 if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
1889 Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
1890 while( jItr.hasNext() ) {
1891 Integer j = jItr.next();
1892 paramIndex2rewriteJ_s2p.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
1896 assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
1897 paramIndex2rewriteJ_s2s.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
1901 // setup K (secondary)
1902 TempDescriptor tdParamR = ogCallee.paramIndex2tdR.get( paramIndex );
1903 assert tdParamR != null;
1904 LabelNode lnParamR = ogCallee.td2ln.get( tdParamR );
1905 assert lnParamR != null;
1906 ReferenceEdge edgeSpecialR_i = lnParamR.getReferenceTo( hrnSecondary, null, null );
1907 assert edgeSpecialR_i != null;
1908 paramIndex2rewriteK_s.put( paramIndex,
1909 toShadowTokens( ogCallee, edgeSpecialR_i.getBeta() ) );
1913 // now depending on whether the callee is static or not
1914 // we need to account for a "this" argument in order to
1915 // find the matching argument in the caller context
1916 TempDescriptor argTemp_i;
1918 argTemp_i = fc.getArg( paramIndex );
1920 if( paramIndex.equals( 0 ) ) {
1921 argTemp_i = fc.getThis();
1923 argTemp_i = fc.getArg( paramIndex - 1 );
1927 // in non-static methods there is a "this" pointer
1928 // that should be taken into account
1930 assert fc.numArgs() == fm.numParameters();
1932 assert fc.numArgs() + 1 == fm.numParameters();
1935 // remember which caller arg label maps to param index
1936 LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i );
1937 paramIndex2ln.put( paramIndex, argLabel_i );
1939 ReachabilitySet d_i_p = new ReachabilitySet().makeCanonical();
1940 ReachabilitySet d_i_s = new ReachabilitySet().makeCanonical();
1941 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1942 while( edgeItr.hasNext() ) {
1943 ReferenceEdge edge = edgeItr.next();
1945 d_i_p = d_i_p.union( edge.getBeta().intersection( edge.getDst().getAlpha() ) );
1946 d_i_s = d_i_s.union( edge.getBeta() );
1948 paramIndex2rewrite_d_p.put( paramIndex, d_i_p );
1949 paramIndex2rewrite_d_s.put( paramIndex, d_i_s );
1951 // TODO: we should only do this when we need it, and then
1952 // memoize it for the rest of the mapping procedure
1953 ReachabilitySet D_i = d_i_s.exhaustiveArityCombinations();
1954 paramIndex2rewriteD.put( paramIndex, D_i );
1958 // with respect to each argument, map parameter effects into caller
1959 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1960 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
1962 Hashtable<Integer, Set<HeapRegionNode> > pi2dr =
1963 new Hashtable<Integer, Set<HeapRegionNode> >();
1965 Hashtable<Integer, Set<HeapRegionNode> > pi2r =
1966 new Hashtable<Integer, Set<HeapRegionNode> >();
1968 Set<HeapRegionNode> defParamObj = new HashSet<HeapRegionNode>();
1970 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1971 while( lnArgItr.hasNext() ) {
1972 Map.Entry me = (Map.Entry) lnArgItr.next();
1973 Integer index = (Integer) me.getKey();
1974 LabelNode lnArg_i = (LabelNode) me.getValue();
1976 Set<HeapRegionNode> dr = new HashSet<HeapRegionNode>();
1977 Set<HeapRegionNode> r = new HashSet<HeapRegionNode>();
1978 Set<HeapRegionNode> todo = new HashSet<HeapRegionNode>();
1980 // find all reachable nodes starting with label referencees
1981 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1982 while( edgeArgItr.hasNext() ) {
1983 ReferenceEdge edge = edgeArgItr.next();
1984 HeapRegionNode hrn = edge.getDst();
1988 if( lnArg_i.getNumReferencees() == 1 && hrn.isSingleObject() ) {
1989 defParamObj.add( hrn );
1992 Iterator<ReferenceEdge> edgeHrnItr = hrn.iteratorToReferencees();
1993 while( edgeHrnItr.hasNext() ) {
1994 ReferenceEdge edger = edgeHrnItr.next();
1995 todo.add( edger.getDst() );
1998 // then follow links until all reachable nodes have been found
1999 while( !todo.isEmpty() ) {
2000 HeapRegionNode hrnr = todo.iterator().next();
2001 todo.remove( hrnr );
2005 Iterator<ReferenceEdge> edgeItr = hrnr.iteratorToReferencees();
2006 while( edgeItr.hasNext() ) {
2007 ReferenceEdge edger = edgeItr.next();
2008 if( !r.contains( edger.getDst() ) ) {
2009 todo.add( edger.getDst() );
2014 if( hrn.isSingleObject() ) {
2019 pi2dr.put( index, dr );
2020 pi2r .put( index, r );
2023 assert defParamObj.size() <= fm.numParameters();
2026 // now iterate over reachable nodes to rewrite their alpha, and
2027 // classify edges found for beta rewrite
2028 Hashtable<TokenTuple, ReachabilitySet> tokens2states = new Hashtable<TokenTuple, ReachabilitySet>();
2030 Hashtable< Integer, Set<Vector> > edges_p2p = new Hashtable< Integer, Set<Vector> >();
2031 Hashtable< Integer, Set<Vector> > edges_p2s = new Hashtable< Integer, Set<Vector> >();
2032 Hashtable< Integer, Set<Vector> > edges_s2p = new Hashtable< Integer, Set<Vector> >();
2033 Hashtable< Integer, Set<Vector> > edges_s2s = new Hashtable< Integer, Set<Vector> >();
2034 Hashtable< Integer, Set<Vector> > edges_up_dr = new Hashtable< Integer, Set<Vector> >();
2035 Hashtable< Integer, Set<Vector> > edges_up_r = new Hashtable< Integer, Set<Vector> >();
2038 // so again, with respect to some arg i...
2039 lnArgItr = paramIndex2ln.entrySet().iterator();
2040 while( lnArgItr.hasNext() ) {
2041 Map.Entry me = (Map.Entry) lnArgItr.next();
2042 Integer index = (Integer) me.getKey();
2043 LabelNode lnArg_i = (LabelNode) me.getValue();
2045 TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary.get( index );
2046 TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( index );
2049 ensureEmptyEdgeIndexPair( edges_p2p, index );
2050 ensureEmptyEdgeIndexPair( edges_p2s, index );
2051 ensureEmptyEdgeIndexPair( edges_s2p, index );
2052 ensureEmptyEdgeIndexPair( edges_s2s, index );
2053 ensureEmptyEdgeIndexPair( edges_up_dr, index );
2054 ensureEmptyEdgeIndexPair( edges_up_r, index );
2056 Set<HeapRegionNode> dr = pi2dr.get( index );
2057 Iterator<HeapRegionNode> hrnItr = dr.iterator();
2058 while( hrnItr.hasNext() ) {
2059 // this heap region is definitely an "a_i" or primary by virtue of being in dr
2060 HeapRegionNode hrn = hrnItr.next();
2062 tokens2states.clear();
2063 tokens2states.put( p_i, hrn.getAlpha() );
2065 rewriteCallerReachability( index,
2068 paramIndex2rewriteH_p.get( index ),
2070 paramIndex2rewrite_d_p,
2071 paramIndex2rewrite_d_s,
2072 paramIndex2rewriteD,
2077 nodesWithNewAlpha.add( hrn );
2080 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
2081 while( edgeItr.hasNext() ) {
2082 ReferenceEdge edge = edgeItr.next();
2083 OwnershipNode on = edge.getSrc();
2085 boolean edge_classified = false;
2087 if( on instanceof HeapRegionNode ) {
2088 // hrn0 may be "a_j" and/or "r_j" or even neither
2089 HeapRegionNode hrn0 = (HeapRegionNode) on;
2091 Iterator itr = pi2dr.entrySet().iterator();
2092 while( itr.hasNext() ) {
2093 Map.Entry mo = (Map.Entry) itr.next();
2094 Integer pi = (Integer) mo.getKey();
2095 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
2097 if( dr_i.contains( hrn0 ) ) {
2098 addEdgeIndexPair( edges_p2p, pi, edge, index );
2099 edge_classified = true;
2103 itr = pi2r.entrySet().iterator();
2104 while( itr.hasNext() ) {
2105 Map.Entry mo = (Map.Entry) itr.next();
2106 Integer pi = (Integer) mo.getKey();
2107 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
2109 if( r_i.contains( hrn0 ) ) {
2110 addEdgeIndexPair( edges_s2p, pi, edge, index );
2111 edge_classified = true;
2116 // all of these edges are upstream of directly reachable objects
2117 if( !edge_classified ) {
2118 addEdgeIndexPair( edges_up_dr, index, edge, index );
2124 Set<HeapRegionNode> r = pi2r.get( index );
2125 hrnItr = r.iterator();
2126 while( hrnItr.hasNext() ) {
2127 // this heap region is definitely an "r_i" or secondary by virtue of being in r
2128 HeapRegionNode hrn = hrnItr.next();
2131 assert paramIndex2rewriteH_s.get( index ) != null;
2133 tokens2states.clear();
2134 tokens2states.put( p_i, new ReachabilitySet().makeCanonical() );
2135 tokens2states.put( s_i, hrn.getAlpha() );
2137 rewriteCallerReachability( index,
2140 paramIndex2rewriteH_s.get( index ),
2142 paramIndex2rewrite_d_p,
2143 paramIndex2rewrite_d_s,
2144 paramIndex2rewriteD,
2149 nodesWithNewAlpha.add( hrn );
2152 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
2153 while( edgeItr.hasNext() ) {
2154 ReferenceEdge edge = edgeItr.next();
2155 OwnershipNode on = edge.getSrc();
2157 boolean edge_classified = false;
2159 if( on instanceof HeapRegionNode ) {
2160 // hrn0 may be "a_j" and/or "r_j" or even neither
2161 HeapRegionNode hrn0 = (HeapRegionNode) on;
2163 Iterator itr = pi2dr.entrySet().iterator();
2164 while( itr.hasNext() ) {
2165 Map.Entry mo = (Map.Entry) itr.next();
2166 Integer pi = (Integer) mo.getKey();
2167 Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
2169 if( dr_i.contains( hrn0 ) ) {
2170 addEdgeIndexPair( edges_p2s, pi, edge, index );
2171 edge_classified = true;
2175 itr = pi2r.entrySet().iterator();
2176 while( itr.hasNext() ) {
2177 Map.Entry mo = (Map.Entry) itr.next();
2178 Integer pi = (Integer) mo.getKey();
2179 Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
2181 if( r_i.contains( hrn0 ) ) {
2182 addEdgeIndexPair( edges_s2s, pi, edge, index );
2183 edge_classified = true;
2188 // these edges are all upstream of some reachable node
2189 if( !edge_classified ) {
2190 addEdgeIndexPair( edges_up_r, index, edge, index );
2197 // and again, with respect to some arg i...
2198 lnArgItr = paramIndex2ln.entrySet().iterator();
2199 while( lnArgItr.hasNext() ) {
2200 Map.Entry me = (Map.Entry) lnArgItr.next();
2201 Integer index = (Integer) me.getKey();
2202 LabelNode lnArg_i = (LabelNode) me.getValue();
2205 // update reachable edges
2206 Iterator edgeItr = edges_p2p.get( index ).iterator();
2207 while( edgeItr.hasNext() ) {
2208 Vector mo = (Vector) edgeItr.next();
2209 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2210 Integer indexJ = (Integer) mo.get( 1 );
2212 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2215 tokens2states.clear();
2216 tokens2states.put( p_j, edge.getBeta() );
2218 rewriteCallerReachability( index,
2221 paramIndex2rewriteJ_p2p.get( makeMapKey( index,
2223 edge.getField() ) ),
2225 paramIndex2rewrite_d_p,
2226 paramIndex2rewrite_d_s,
2227 paramIndex2rewriteD,
2232 edgesWithNewBeta.add( edge );
2236 edgeItr = edges_p2s.get( index ).iterator();
2237 while( edgeItr.hasNext() ) {
2238 Vector mo = (Vector) edgeItr.next();
2239 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2240 Integer indexJ = (Integer) mo.get( 1 );
2242 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2245 tokens2states.clear();
2246 tokens2states.put( s_j, edge.getBeta() );
2248 rewriteCallerReachability( index,
2251 paramIndex2rewriteJ_p2s.get( makeMapKey( index,
2252 edge.getField() ) ),
2254 paramIndex2rewrite_d_p,
2255 paramIndex2rewrite_d_s,
2256 paramIndex2rewriteD,
2261 edgesWithNewBeta.add( edge );
2265 edgeItr = edges_s2p.get( index ).iterator();
2266 while( edgeItr.hasNext() ) {
2267 Vector mo = (Vector) edgeItr.next();
2268 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2269 Integer indexJ = (Integer) mo.get( 1 );
2271 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2274 tokens2states.clear();
2275 tokens2states.put( p_j, edge.getBeta() );
2277 rewriteCallerReachability( index,
2280 paramIndex2rewriteJ_s2p.get( index ),
2282 paramIndex2rewrite_d_p,
2283 paramIndex2rewrite_d_s,
2284 paramIndex2rewriteD,
2289 edgesWithNewBeta.add( edge );
2293 edgeItr = edges_s2s.get( index ).iterator();
2294 while( edgeItr.hasNext() ) {
2295 Vector mo = (Vector) edgeItr.next();
2296 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2297 Integer indexJ = (Integer) mo.get( 1 );
2299 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2302 tokens2states.clear();
2303 tokens2states.put( s_j, edge.getBeta() );
2305 rewriteCallerReachability( index,
2308 paramIndex2rewriteJ_s2s.get( index ),
2310 paramIndex2rewrite_d_p,
2311 paramIndex2rewrite_d_s,
2312 paramIndex2rewriteD,
2317 edgesWithNewBeta.add( edge );
2321 // update directly upstream edges
2322 Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
2323 new Hashtable<ReferenceEdge, ChangeTupleSet>();
2325 HashSet<ReferenceEdge> edgesDirectlyUpstream =
2326 new HashSet<ReferenceEdge>();
2328 edgeItr = edges_up_dr.get( index ).iterator();
2329 while( edgeItr.hasNext() ) {
2330 Vector mo = (Vector) edgeItr.next();
2331 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2332 Integer indexJ = (Integer) mo.get( 1 );
2334 edgesDirectlyUpstream.add( edge );
2336 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2339 // start with K_p2 and p_j
2340 tokens2states.clear();
2341 tokens2states.put( p_j, edge.getBeta() );
2343 rewriteCallerReachability( index,
2346 paramIndex2rewriteK_p2.get( index ),
2348 paramIndex2rewrite_d_p,
2349 paramIndex2rewrite_d_s,
2350 paramIndex2rewriteD,
2353 edgeUpstreamPlannedChanges );
2355 // and add in s_j, if required, and do K_p
2356 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2358 tokens2states.put( s_j, edge.getBeta() );
2361 rewriteCallerReachability( index,
2364 paramIndex2rewriteK_p.get( index ),
2366 paramIndex2rewrite_d_p,
2367 paramIndex2rewrite_d_s,
2368 paramIndex2rewriteD,
2371 edgeUpstreamPlannedChanges );
2373 edgesWithNewBeta.add( edge );
2376 propagateTokensOverEdges( edgesDirectlyUpstream,
2377 edgeUpstreamPlannedChanges,
2381 // update upstream edges
2382 edgeUpstreamPlannedChanges =
2383 new Hashtable<ReferenceEdge, ChangeTupleSet>();
2385 HashSet<ReferenceEdge> edgesUpstream =
2386 new HashSet<ReferenceEdge>();
2388 edgeItr = edges_up_r.get( index ).iterator();
2389 while( edgeItr.hasNext() ) {
2390 Vector mo = (Vector) edgeItr.next();
2391 ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
2392 Integer indexJ = (Integer) mo.get( 1 );
2394 edgesUpstream.add( edge );
2396 TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
2399 TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
2402 tokens2states.clear();
2403 tokens2states.put( p_j, rsWttsEmpty );
2404 tokens2states.put( s_j, edge.getBeta() );
2406 rewriteCallerReachability( index,
2409 paramIndex2rewriteK_s.get( index ),
2411 paramIndex2rewrite_d_p,
2412 paramIndex2rewrite_d_s,
2413 paramIndex2rewriteD,
2416 edgeUpstreamPlannedChanges );
2418 edgesWithNewBeta.add( edge );
2421 propagateTokensOverEdges( edgesUpstream,
2422 edgeUpstreamPlannedChanges,
2425 } // end effects per argument/parameter map
2428 // commit changes to alpha and beta
2429 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
2430 while( nodeItr.hasNext() ) {
2431 nodeItr.next().applyAlphaNew();
2434 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
2435 while( edgeItr.hasNext() ) {
2436 edgeItr.next().applyBetaNew();
2440 // verify the existence of allocation sites and their
2441 // shadows from the callee in the context of this caller graph
2442 // then map allocated nodes of callee onto the caller shadows
2444 Hashtable<TokenTuple, ReachabilitySet> tokens2statesEmpty = new Hashtable<TokenTuple, ReachabilitySet>();
2446 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
2447 while( asItr.hasNext() ) {
2448 AllocationSite allocSite = asItr.next();
2450 // grab the summary in the caller just to make sure
2451 // the allocation site has nodes in the caller
2452 HeapRegionNode hrnSummary = getSummaryNode( allocSite );
2454 // assert that the shadow nodes have no reference edges
2455 // because they're brand new to the graph, or last time
2456 // they were used they should have been cleared of edges
2457 HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
2458 assert hrnShadowSummary.getNumReferencers() == 0;
2459 assert hrnShadowSummary.getNumReferencees() == 0;
2461 // then bring g_ij onto g'_ij and rewrite
2462 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode( allocSite );
2463 hrnShadowSummary.setAlpha( toShadowTokens( ogCallee, hrnSummaryCallee.getAlpha() ) );
2465 // shadow nodes only are touched by a rewrite one time,
2466 // so rewrite and immediately commit--and they don't belong
2467 // to a particular parameter, so use a bogus param index
2468 // that pulls a self-rewrite out of H
2469 rewriteCallerReachability( bogusIndex,
2472 funcScriptR( hrnShadowSummary.getAlpha(), ogCallee, mc ),
2474 paramIndex2rewrite_d_p,
2475 paramIndex2rewrite_d_s,
2476 paramIndex2rewriteD,
2481 hrnShadowSummary.applyAlphaNew();
2484 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
2485 Integer idIth = allocSite.getIthOldest(i);
2486 assert id2hrn.containsKey(idIth);
2487 HeapRegionNode hrnIth = id2hrn.get(idIth);
2489 Integer idShadowIth = -(allocSite.getIthOldest(i));
2490 assert id2hrn.containsKey(idShadowIth);
2491 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
2492 assert hrnIthShadow.getNumReferencers() == 0;
2493 assert hrnIthShadow.getNumReferencees() == 0;
2495 assert ogCallee.id2hrn.containsKey(idIth);
2496 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
2497 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
2499 rewriteCallerReachability( bogusIndex,
2502 funcScriptR( hrnIthShadow.getAlpha(), ogCallee, mc ),
2504 paramIndex2rewrite_d_p,
2505 paramIndex2rewrite_d_s,
2506 paramIndex2rewriteD,
2511 hrnIthShadow.applyAlphaNew();
2516 // for every heap region->heap region edge in the
2517 // callee graph, create the matching edge or edges
2518 // in the caller graph
2519 Set sCallee = ogCallee.id2hrn.entrySet();
2520 Iterator iCallee = sCallee.iterator();
2521 while( iCallee.hasNext() ) {
2522 Map.Entry meCallee = (Map.Entry) iCallee.next();
2523 Integer idCallee = (Integer) meCallee.getKey();
2524 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
2526 Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
2527 while( heapRegionsItrCallee.hasNext() ) {
2528 ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
2529 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
2530 Integer idChildCallee = hrnChildCallee.getID();
2532 // only address this edge if it is not a special initial edge
2533 if( !edgeCallee.isInitialParam() ) {
2535 // now we know that in the callee method's ownership graph
2536 // there is a heap region->heap region reference edge given
2537 // by heap region pointers:
2538 // hrnCallee -> heapChildCallee
2540 // or by the ownership-graph independent ID's:
2541 // idCallee -> idChildCallee
2543 // make the edge with src and dst so beta info is
2544 // calculated once, then copy it for each new edge in caller
2545 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null,
2547 edgeCallee.getType(),
2548 edgeCallee.getField(),
2550 funcScriptR( toShadowTokens( ogCallee,
2551 edgeCallee.getBeta()
2556 rewriteCallerReachability( bogusIndex,
2558 edgeNewInCallerTemplate,
2559 edgeNewInCallerTemplate.getBeta(),
2561 paramIndex2rewrite_d_p,
2562 paramIndex2rewrite_d_s,
2563 paramIndex2rewriteD,
2568 edgeNewInCallerTemplate.applyBetaNew();
2571 // So now make a set of possible source heaps in the caller graph
2572 // and a set of destination heaps in the caller graph, and make
2573 // a reference edge in the caller for every possible (src,dst) pair
2574 HashSet<HeapRegionNode> possibleCallerSrcs =
2575 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2576 (HeapRegionNode) edgeCallee.getSrc(),
2580 HashSet<HeapRegionNode> possibleCallerDsts =
2581 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2582 edgeCallee.getDst(),
2586 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
2587 Iterator srcItr = possibleCallerSrcs.iterator();
2588 while( srcItr.hasNext() ) {
2589 HeapRegionNode src = (HeapRegionNode) srcItr.next();
2591 if( !hasMatchingField( src, edgeCallee ) ) {
2592 // prune this source node possibility
2596 Iterator dstItr = possibleCallerDsts.iterator();
2597 while( dstItr.hasNext() ) {
2598 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
2600 if( !hasMatchingType( edgeCallee, dst ) ) {
2605 // otherwise the caller src and dst pair can match the edge, so make it
2606 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2607 edgeNewInCaller.setSrc( src );
2608 edgeNewInCaller.setDst( dst );
2610 ReferenceEdge edgeExisting = src.getReferenceTo( dst,
2611 edgeNewInCaller.getType(),
2612 edgeNewInCaller.getField() );
2613 if( edgeExisting == null ) {
2614 // if this edge doesn't exist in the caller, create it
2615 addReferenceEdge( src, dst, edgeNewInCaller );
2618 // if it already exists, merge with it
2619 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2628 // return value may need to be assigned in caller
2629 TempDescriptor returnTemp = fc.getReturnTemp();
2630 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2632 LabelNode lnLhsCaller = getLabelNodeFromTemp( returnTemp );
2633 clearReferenceEdgesFrom( lnLhsCaller, null, null, true );
2635 LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp( tdReturn );
2636 Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
2637 while( edgeCalleeItr.hasNext() ) {
2638 ReferenceEdge edgeCallee = edgeCalleeItr.next();
2640 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null,
2642 edgeCallee.getType(),
2643 edgeCallee.getField(),
2645 funcScriptR( toShadowTokens(ogCallee,
2646 edgeCallee.getBeta() ),
2650 rewriteCallerReachability( bogusIndex,
2652 edgeNewInCallerTemplate,
2653 edgeNewInCallerTemplate.getBeta(),
2655 paramIndex2rewrite_d_p,
2656 paramIndex2rewrite_d_s,
2657 paramIndex2rewriteD,
2662 edgeNewInCallerTemplate.applyBetaNew();
2665 HashSet<HeapRegionNode> assignCallerRhs =
2666 getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
2667 edgeCallee.getDst(),
2671 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
2672 while( itrHrn.hasNext() ) {
2673 HeapRegionNode hrnCaller = itrHrn.next();
2675 if( !hasMatchingType( edgeCallee, hrnCaller ) ) {
2680 // otherwise caller node can match callee edge, so make it
2681 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2682 edgeNewInCaller.setSrc( lnLhsCaller );
2683 edgeNewInCaller.setDst( hrnCaller );
2685 ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo( hrnCaller,
2686 edgeNewInCaller.getType(),
2687 edgeNewInCaller.getField() );
2688 if( edgeExisting == null ) {
2690 // if this edge doesn't exist in the caller, create it
2691 addReferenceEdge( lnLhsCaller, hrnCaller, edgeNewInCaller );
2693 // if it already exists, merge with it
2694 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
2701 // merge the shadow nodes of allocation sites back down to normal capacity
2702 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
2703 while( allocItr.hasNext() ) {
2704 AllocationSite as = allocItr.next();
2706 // first age each allocation site enough times to make room for the shadow nodes
2707 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2711 // then merge the shadow summary into the normal summary
2712 HeapRegionNode hrnSummary = getSummaryNode( as );
2713 assert hrnSummary != null;
2715 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as );
2716 assert hrnSummaryShadow != null;
2718 mergeIntoSummary( hrnSummaryShadow, hrnSummary );
2720 // then clear off after merge
2721 clearReferenceEdgesFrom( hrnSummaryShadow, null, null, true );
2722 clearReferenceEdgesTo ( hrnSummaryShadow, null, null, true );
2723 hrnSummaryShadow.setAlpha( new ReachabilitySet().makeCanonical() );
2725 // then transplant shadow nodes onto the now clean normal nodes
2726 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2728 Integer idIth = as.getIthOldest( i );
2729 HeapRegionNode hrnIth = id2hrn.get( idIth );
2730 Integer idIthShadow = as.getIthOldestShadow( i );
2731 HeapRegionNode hrnIthShadow = id2hrn.get( idIthShadow );
2733 transferOnto( hrnIthShadow, hrnIth );
2735 // clear off shadow nodes after transfer
2736 clearReferenceEdgesFrom( hrnIthShadow, null, null, true );
2737 clearReferenceEdgesTo ( hrnIthShadow, null, null, true );
2738 hrnIthShadow.setAlpha( new ReachabilitySet().makeCanonical() );
2741 // finally, globally change shadow tokens into normal tokens
2742 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
2743 while( itrAllLabelNodes.hasNext() ) {
2744 Map.Entry me = (Map.Entry) itrAllLabelNodes.next();
2745 LabelNode ln = (LabelNode) me.getValue();
2747 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
2748 while( itrEdges.hasNext() ) {
2749 unshadowTokens( as, itrEdges.next() );
2753 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2754 while( itrAllHRNodes.hasNext() ) {
2755 Map.Entry me = (Map.Entry) itrAllHRNodes.next();
2756 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
2758 unshadowTokens( as, hrnToAge );
2760 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
2761 while( itrEdges.hasNext() ) {
2762 unshadowTokens( as, itrEdges.next() );
2768 if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
2769 fm.getMethod().getSymbol().equals( debugCallee ) ) {
2771 writeGraph( "debug2JustBeforeSweep", true, true, true, false, false );
2772 } catch( IOException e ) {}
2776 // improve reachability as much as possible
2781 if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
2782 fm.getMethod().getSymbol().equals( debugCallee ) ) {
2784 writeGraph( "debug9endResolveCall", true, true, true, false, false );
2785 } catch( IOException e ) {}
2786 System.out.println( " "+mc+" done calling "+fm );
2791 protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
2793 // if no type, then it's a match-everything region
2794 TypeDescriptor tdSrc = src.getType();
2795 if( tdSrc == null ) {
2799 if( tdSrc.isArray() ) {
2800 TypeDescriptor td = edge.getType();
2803 TypeDescriptor tdSrcDeref = tdSrc.dereference();
2804 assert tdSrcDeref != null;
2806 if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
2810 return edge.getField().equals( OwnershipAnalysis.arrayElementFieldName );
2813 // if it's not a class, it doesn't have any fields to match
2814 if( !tdSrc.isClass() ) {
2818 Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
2819 while( fieldsSrcItr.hasNext() ) {
2820 FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
2821 if( fd.getType().equals( edge.getType() ) &&
2822 fd.getSymbol().equals( edge.getField() ) ) {
2827 // otherwise it is a class with fields
2828 // but we didn't find a match
2833 protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
2835 // if the region has no type, matches everything
2836 TypeDescriptor tdDst = dst.getType();
2837 if( tdDst == null ) {
2841 // if the type is not a class or an array, don't
2842 // match because primitives are copied, no aliases
2843 ClassDescriptor cdDst = tdDst.getClassDesc();
2844 if( cdDst == null && !tdDst.isArray() ) {
2848 // if the edge type is null, it matches everything
2849 TypeDescriptor tdEdge = edge.getType();
2850 if( tdEdge == null ) {
2854 return typeUtil.isSuperorType(tdEdge, tdDst);
2859 protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
2860 edge.setBeta(edge.getBeta().unshadowTokens(as) );
2863 protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
2864 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
2868 private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
2869 ReachabilitySet rsIn) {
2871 ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical();
2873 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
2874 while( allocItr.hasNext() ) {
2875 AllocationSite as = allocItr.next();
2877 rsOut = rsOut.toShadowTokens(as);
2880 return rsOut.makeCanonical();
2884 private void rewriteCallerReachability(Integer paramIndex,
2887 ReachabilitySet rules,
2888 Hashtable<TokenTuple, ReachabilitySet> tokens2states,
2889 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_p,
2890 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_s,
2891 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
2892 OwnershipGraph ogCallee,
2893 boolean makeChangeSet,
2894 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
2896 assert(hrn == null && edge != null) ||
2897 (hrn != null && edge == null);
2899 assert rules != null;
2900 assert tokens2states != null;
2902 ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
2904 // for initializing structures in this method
2905 TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
2907 // use this to construct a change set if required; the idea is to
2908 // map every partially rewritten token tuple set to the set of
2909 // caller-context token tuple sets that were used to generate it
2910 Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
2911 new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
2912 rewritten2source.put( ttsEmpty, new HashSet<TokenTupleSet>() );
2915 Iterator<TokenTupleSet> rulesItr = rules.iterator();
2916 while(rulesItr.hasNext()) {
2917 TokenTupleSet rule = rulesItr.next();
2919 ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
2921 Iterator<TokenTuple> ruleItr = rule.iterator();
2922 while(ruleItr.hasNext()) {
2923 TokenTuple ttCallee = ruleItr.next();
2925 // compute the possibilities for rewriting this callee token
2926 ReachabilitySet ttCalleeRewrites = null;
2927 boolean callerSourceUsed = false;
2929 if( tokens2states.containsKey( ttCallee ) ) {
2930 callerSourceUsed = true;
2931 ttCalleeRewrites = tokens2states.get( ttCallee );
2932 assert ttCalleeRewrites != null;
2934 } else if( ogCallee.paramTokenPrimary2paramIndex.containsKey( ttCallee ) ) {
2936 Integer paramIndex_j = ogCallee.paramTokenPrimary2paramIndex.get( ttCallee );
2937 assert paramIndex_j != null;
2938 ttCalleeRewrites = paramIndex2rewrite_d_p.get( paramIndex_j );
2939 assert ttCalleeRewrites != null;
2941 } else if( ogCallee.paramTokenSecondary2paramIndex.containsKey( ttCallee ) ) {
2943 Integer paramIndex_j = ogCallee.paramTokenSecondary2paramIndex.get( ttCallee );
2944 assert paramIndex_j != null;
2945 ttCalleeRewrites = paramIndex2rewrite_d_s.get( paramIndex_j );
2946 assert ttCalleeRewrites != null;
2948 } else if( ogCallee.paramTokenSecondaryPlus2paramIndex.containsKey( ttCallee ) ) {
2950 Integer paramIndex_j = ogCallee.paramTokenSecondaryPlus2paramIndex.get( ttCallee );
2951 assert paramIndex_j != null;
2952 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
2953 assert ttCalleeRewrites != null;
2955 } else if( ogCallee.paramTokenSecondaryStar2paramIndex.containsKey( ttCallee ) ) {
2957 Integer paramIndex_j = ogCallee.paramTokenSecondaryStar2paramIndex.get( ttCallee );
2958 assert paramIndex_j != null;
2959 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
2960 assert ttCalleeRewrites != null;
2963 // otherwise there's no need for a rewrite, just pass this one on
2964 TokenTupleSet ttsCaller = new TokenTupleSet( ttCallee ).makeCanonical();
2965 ttCalleeRewrites = new ReachabilitySet( ttsCaller ).makeCanonical();
2968 // branch every version of the working rewritten rule with
2969 // the possibilities for rewriting the current callee token
2970 ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
2972 Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
2973 while( rewrittenRuleItr.hasNext() ) {
2974 TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
2976 Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
2977 while( ttCalleeRewritesItr.hasNext() ) {
2978 TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
2980 TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
2982 if( makeChangeSet ) {
2983 // in order to keep the list of source token tuple sets
2984 // start with the sets used to make the partially rewritten
2985 // rule up to this point
2986 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewritten );
2987 assert sourceSets != null;
2989 // make a shallow copy for possible modification
2990 sourceSets = (HashSet<TokenTupleSet>) sourceSets.clone();
2992 // if we used something from the caller to rewrite it, remember
2993 if( callerSourceUsed ) {
2994 sourceSets.add( ttsBranch );
2997 // set mapping for the further rewritten rule
2998 rewritten2source.put( ttsRewrittenNext, sourceSets );
3001 rewrittenRuleWithTTCallee =
3002 rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
3006 // now the rewritten rule's possibilities have been extended by
3007 // rewriting the current callee token, remember result
3008 rewrittenRule = rewrittenRuleWithTTCallee;
3011 // the rule has been entirely rewritten into the caller context
3012 // now, so add it to the new reachability information
3013 callerReachabilityNew =
3014 callerReachabilityNew.union( rewrittenRule );
3017 if( makeChangeSet ) {
3018 ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
3020 // each possibility for the final reachability should have a set of
3021 // caller sources mapped to it, use to create the change set
3022 Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
3023 while( callerReachabilityItr.hasNext() ) {
3024 TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
3025 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewrittenFinal );
3026 assert sourceSets != null;
3028 Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
3029 while( sourceSetsItr.hasNext() ) {
3030 TokenTupleSet ttsSource = sourceSetsItr.next();
3033 callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
3037 assert edgePlannedChanges != null;
3038 edgePlannedChanges.put( edge, callerChangeSet );
3042 edge.setBetaNew( edge.getBetaNew().union( callerReachabilityNew ) );
3044 hrn.setAlphaNew( hrn.getAlphaNew().union( callerReachabilityNew ) );
3050 private HashSet<HeapRegionNode>
3051 getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
3052 HeapRegionNode hrnCallee,
3053 Hashtable<Integer, Set<HeapRegionNode> > pi2dr,
3054 Hashtable<Integer, Set<HeapRegionNode> > pi2r
3057 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
3059 Set<Integer> paramIndicesCallee_p = ogCallee.idPrimary2paramIndexSet .get( hrnCallee.getID() );
3060 Set<Integer> paramIndicesCallee_s = ogCallee.idSecondary2paramIndexSet.get( hrnCallee.getID() );
3062 if( paramIndicesCallee_p == null &&
3063 paramIndicesCallee_s == null ) {
3064 // this is a node allocated in the callee and it has
3065 // exactly one shadow node in the caller to map to
3066 AllocationSite as = hrnCallee.getAllocationSite();
3069 int age = as.getAgeCategory( hrnCallee.getID() );
3070 assert age != AllocationSite.AGE_notInThisSite;
3073 if( age == AllocationSite.AGE_summary ) {
3074 idCaller = as.getSummaryShadow();
3076 } else if( age == AllocationSite.AGE_oldest ) {
3077 idCaller = as.getOldestShadow();
3080 assert age == AllocationSite.AGE_in_I;
3082 Integer I = as.getAge( hrnCallee.getID() );
3085 idCaller = as.getIthOldestShadow( I );
3088 assert id2hrn.containsKey( idCaller );
3089 possibleCallerHRNs.add( id2hrn.get( idCaller ) );
3091 return possibleCallerHRNs;
3094 // find out what primary objects this might be
3095 if( paramIndicesCallee_p != null ) {
3096 // this is a node that was created to represent a parameter
3097 // so it maps to some regions directly reachable from the arg labels
3098 Iterator<Integer> itrIndex = paramIndicesCallee_p.iterator();
3099 while( itrIndex.hasNext() ) {
3100 Integer paramIndexCallee = itrIndex.next();
3101 assert pi2dr.containsKey( paramIndexCallee );
3102 possibleCallerHRNs.addAll( pi2dr.get( paramIndexCallee ) );
3106 // find out what secondary objects this might be
3107 if( paramIndicesCallee_s != null ) {
3108 // this is a node that was created to represent objs reachable from
3109 // some parameter, so it maps to regions reachable from the arg labels
3110 Iterator<Integer> itrIndex = paramIndicesCallee_s.iterator();
3111 while( itrIndex.hasNext() ) {
3112 Integer paramIndexCallee = itrIndex.next();
3113 assert pi2r.containsKey( paramIndexCallee );
3114 possibleCallerHRNs.addAll( pi2r.get( paramIndexCallee ) );
3118 // one of the two cases above should have put something in here
3119 assert !possibleCallerHRNs.isEmpty();
3121 return possibleCallerHRNs;
3126 ////////////////////////////////////////////////////
3128 // This global sweep is an optional step to prune
3129 // reachability sets that are not internally
3130 // consistent with the global graph. It should be
3131 // invoked after strong updates or method calls.
3133 ////////////////////////////////////////////////////
3134 public void globalSweep() {
3136 // boldB is part of the phase 1 sweep
3137 Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> > boldB =
3138 new Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> >();
3140 // visit every heap region to initialize alphaNew and calculate boldB
3141 Set hrns = id2hrn.entrySet();
3142 Iterator itrHrns = hrns.iterator();
3143 while( itrHrns.hasNext() ) {
3144 Map.Entry me = (Map.Entry)itrHrns.next();
3145 Integer token = (Integer) me.getKey();
3146 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3148 // assert that this node and incoming edges have clean alphaNew
3149 // and betaNew sets, respectively
3150 assert rsEmpty.equals( hrn.getAlphaNew() );
3152 Iterator<ReferenceEdge> itrRers = hrn.iteratorToReferencers();
3153 while( itrRers.hasNext() ) {
3154 ReferenceEdge edge = itrRers.next();
3155 assert rsEmpty.equals( edge.getBetaNew() );
3158 // calculate boldB for this flagged node
3159 if( hrn.isFlagged() || hrn.isParameter() ) {
3161 Hashtable<ReferenceEdge, ReachabilitySet> boldB_f =
3162 new Hashtable<ReferenceEdge, ReachabilitySet>();
3164 Set<ReferenceEdge> workSetEdges = new HashSet<ReferenceEdge>();
3166 // initial boldB_f constraints
3167 Iterator<ReferenceEdge> itrRees = hrn.iteratorToReferencees();
3168 while( itrRees.hasNext() ) {
3169 ReferenceEdge edge = itrRees.next();
3171 assert !boldB.containsKey( edge );
3172 boldB_f.put( edge, edge.getBeta() );
3174 assert !workSetEdges.contains( edge );
3175 workSetEdges.add( edge );
3178 // enforce the boldB_f constraint at edges until we reach a fixed point
3179 while( !workSetEdges.isEmpty() ) {
3180 ReferenceEdge edge = workSetEdges.iterator().next();
3181 workSetEdges.remove( edge );
3183 Iterator<ReferenceEdge> itrPrime = edge.getDst().iteratorToReferencees();
3184 while( itrPrime.hasNext() ) {
3185 ReferenceEdge edgePrime = itrPrime.next();
3187 ReachabilitySet prevResult = boldB_f.get( edgePrime );
3188 ReachabilitySet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
3190 if( prevResult == null ||
3191 prevResult.union( intersection ).size() > prevResult.size() ) {
3193 if( prevResult == null ) {
3194 boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) );
3196 boldB_f.put( edgePrime, prevResult.union( intersection ) );
3198 workSetEdges.add( edgePrime );
3203 boldB.put( token, boldB_f );
3208 // use boldB to prune tokens from alpha states that are impossible
3209 // and propagate the differences backwards across edges
3210 HashSet<ReferenceEdge> edgesForPropagation = new HashSet<ReferenceEdge>();
3212 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
3213 new Hashtable<ReferenceEdge, ChangeTupleSet>();
3215 hrns = id2hrn.entrySet();
3216 itrHrns = hrns.iterator();
3217 while( itrHrns.hasNext() ) {
3218 Map.Entry me = (Map.Entry)itrHrns.next();
3219 Integer token = (Integer) me.getKey();
3220 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3222 // never remove the identity token from a flagged region
3223 // because it is trivially satisfied
3224 TokenTuple ttException = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONE ).makeCanonical();
3226 ChangeTupleSet cts = new ChangeTupleSet().makeCanonical();
3228 // mark tokens for removal
3229 Iterator<TokenTupleSet> stateItr = hrn.getAlpha().iterator();
3230 while( stateItr.hasNext() ) {
3231 TokenTupleSet ttsOld = stateItr.next();
3233 TokenTupleSet markedTokens = new TokenTupleSet().makeCanonical();
3235 Iterator<TokenTuple> ttItr = ttsOld.iterator();
3236 while( ttItr.hasNext() ) {
3237 TokenTuple ttOld = ttItr.next();
3239 // never remove the identity token from a flagged region
3240 // because it is trivially satisfied
3241 if( hrn.isFlagged() || hrn.isParameter() ) {
3242 if( ttOld == ttException ) {
3247 // does boldB_ttOld allow this token?
3248 boolean foundState = false;
3249 Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3250 while( incidentEdgeItr.hasNext() ) {
3251 ReferenceEdge incidentEdge = incidentEdgeItr.next();
3253 // if it isn't allowed, mark for removal
3254 ReachabilitySet boldB_ttOld_incident = boldB.get( ttOld.getToken() ).get( incidentEdge );
3255 if( boldB_ttOld_incident != null &&
3256 boldB_ttOld_incident.contains( ttsOld ) ) {
3262 markedTokens = markedTokens.add( ttOld );
3266 // if there is nothing marked, just move on
3267 if( markedTokens.isEmpty() ) {
3268 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
3272 // remove all marked tokens and establish a change set that should
3273 // propagate backwards over edges from this node
3274 TokenTupleSet ttsPruned = new TokenTupleSet().makeCanonical();
3275 ttItr = ttsOld.iterator();
3276 while( ttItr.hasNext() ) {
3277 TokenTuple ttOld = ttItr.next();
3279 if( !markedTokens.containsTuple( ttOld ) ) {
3280 ttsPruned = ttsPruned.union( ttOld );
3283 assert !ttsOld.equals( ttsPruned );
3285 hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
3286 ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
3287 cts = cts.union( ct );
3290 // throw change tuple set on all incident edges
3291 if( !cts.isEmpty() ) {
3292 Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3293 while( incidentEdgeItr.hasNext() ) {
3294 ReferenceEdge incidentEdge = incidentEdgeItr.next();
3296 edgesForPropagation.add( incidentEdge );
3298 if( edgePlannedChanges.get( incidentEdge ) == null ) {
3299 edgePlannedChanges.put( incidentEdge, cts );
3301 edgePlannedChanges.put(
3303 edgePlannedChanges.get( incidentEdge ).union( cts )
3310 HashSet<ReferenceEdge> edgesUpdated = new HashSet<ReferenceEdge>();
3312 propagateTokensOverEdges( edgesForPropagation,
3316 // at the end of the 1st phase reference edges have
3317 // beta, betaNew that correspond to beta and betaR
3319 // commit beta<-betaNew, so beta=betaR and betaNew
3320 // will represent the beta' calculation in 2nd phase
3322 // commit alpha<-alphaNew because it won't change
3323 HashSet<ReferenceEdge> res = new HashSet<ReferenceEdge>();
3325 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3326 while( nodeItr.hasNext() ) {
3327 HeapRegionNode hrn = nodeItr.next();
3328 hrn.applyAlphaNew();
3329 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
3330 while( itrRes.hasNext() ) {
3331 res.add( itrRes.next() );
3337 Iterator<ReferenceEdge> edgeItr = res.iterator();
3338 while( edgeItr.hasNext() ) {
3339 ReferenceEdge edge = edgeItr.next();
3340 HeapRegionNode hrn = edge.getDst();
3342 // commit results of last phase
3343 if( edgesUpdated.contains( edge ) ) {
3344 edge.applyBetaNew();
3347 // compute intial condition of 2nd phase
3348 edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
3351 // every edge in the graph is the initial workset
3352 Set<ReferenceEdge> edgeWorkSet = (Set) res.clone();
3353 while( !edgeWorkSet.isEmpty() ) {
3354 ReferenceEdge edgePrime = edgeWorkSet.iterator().next();
3355 edgeWorkSet.remove( edgePrime );
3357 OwnershipNode on = edgePrime.getSrc();
3358 if( !(on instanceof HeapRegionNode) ) {
3361 HeapRegionNode hrn = (HeapRegionNode) on;
3363 Iterator<ReferenceEdge> itrEdge = hrn.iteratorToReferencers();
3364 while( itrEdge.hasNext() ) {
3365 ReferenceEdge edge = itrEdge.next();
3367 ReachabilitySet prevResult = edge.getBetaNew();
3368 assert prevResult != null;
3370 ReachabilitySet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
3372 if( prevResult.union( intersection ).size() > prevResult.size() ) {
3373 edge.setBetaNew( prevResult.union( intersection ) );
3374 edgeWorkSet.add( edge );
3379 // commit beta' (beta<-betaNew)
3380 edgeItr = res.iterator();
3381 while( edgeItr.hasNext() ) {
3382 edgeItr.next().applyBetaNew();
3388 ////////////////////////////////////////////////////
3389 // in merge() and equals() methods the suffix A
3390 // represents the passed in graph and the suffix
3391 // B refers to the graph in this object
3392 // Merging means to take the incoming graph A and
3393 // merge it into B, so after the operation graph B
3394 // is the final result.
3395 ////////////////////////////////////////////////////
3396 public void merge(OwnershipGraph og) {
3402 mergeOwnershipNodes(og);
3403 mergeReferenceEdges(og);
3404 mergeParamIndexMappings(og);
3405 mergeAllocationSites(og);
3409 protected void mergeOwnershipNodes(OwnershipGraph og) {
3410 Set sA = og.id2hrn.entrySet();
3411 Iterator iA = sA.iterator();
3412 while( iA.hasNext() ) {
3413 Map.Entry meA = (Map.Entry)iA.next();
3414 Integer idA = (Integer) meA.getKey();
3415 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3417 // if this graph doesn't have a node the
3418 // incoming graph has, allocate it
3419 if( !id2hrn.containsKey(idA) ) {
3420 HeapRegionNode hrnB = hrnA.copy();
3421 id2hrn.put(idA, hrnB);
3424 // otherwise this is a node present in both graphs
3425 // so make the new reachability set a union of the
3426 // nodes' reachability sets
3427 HeapRegionNode hrnB = id2hrn.get(idA);
3428 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
3432 // now add any label nodes that are in graph B but
3434 sA = og.td2ln.entrySet();
3436 while( iA.hasNext() ) {
3437 Map.Entry meA = (Map.Entry)iA.next();
3438 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3439 LabelNode lnA = (LabelNode) meA.getValue();
3441 // if the label doesn't exist in B, allocate and add it
3442 LabelNode lnB = getLabelNodeFromTemp(tdA);
3446 protected void mergeReferenceEdges(OwnershipGraph og) {
3449 Set sA = og.id2hrn.entrySet();
3450 Iterator iA = sA.iterator();
3451 while( iA.hasNext() ) {
3452 Map.Entry meA = (Map.Entry)iA.next();
3453 Integer idA = (Integer) meA.getKey();
3454 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3456 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3457 while( heapRegionsItrA.hasNext() ) {
3458 ReferenceEdge edgeA = heapRegionsItrA.next();
3459 HeapRegionNode hrnChildA = edgeA.getDst();
3460 Integer idChildA = hrnChildA.getID();
3462 // at this point we know an edge in graph A exists
3463 // idA -> idChildA, does this exist in B?
3464 assert id2hrn.containsKey(idA);
3465 HeapRegionNode hrnB = id2hrn.get(idA);
3466 ReferenceEdge edgeToMerge = null;
3468 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3469 while( heapRegionsItrB.hasNext() &&
3470 edgeToMerge == null ) {
3472 ReferenceEdge edgeB = heapRegionsItrB.next();
3473 HeapRegionNode hrnChildB = edgeB.getDst();
3474 Integer idChildB = hrnChildB.getID();
3476 // don't use the ReferenceEdge.equals() here because
3477 // we're talking about existence between graphs
3478 if( idChildB.equals( idChildA ) &&
3479 edgeB.typeAndFieldEquals( edgeA ) ) {
3481 edgeToMerge = edgeB;
3485 // if the edge from A was not found in B,
3487 if( edgeToMerge == null ) {
3488 assert id2hrn.containsKey(idChildA);
3489 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3490 edgeToMerge = edgeA.copy();
3491 edgeToMerge.setSrc(hrnB);
3492 edgeToMerge.setDst(hrnChildB);
3493 addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
3495 // otherwise, the edge already existed in both graphs
3496 // so merge their reachability sets
3498 // just replace this beta set with the union
3499 assert edgeToMerge != null;
3500 edgeToMerge.setBeta(
3501 edgeToMerge.getBeta().union(edgeA.getBeta() )
3503 if( !edgeA.isInitialParam() ) {
3504 edgeToMerge.setIsInitialParam(false);
3510 // and then again with label nodes
3511 sA = og.td2ln.entrySet();
3513 while( iA.hasNext() ) {
3514 Map.Entry meA = (Map.Entry)iA.next();
3515 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3516 LabelNode lnA = (LabelNode) meA.getValue();
3518 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
3519 while( heapRegionsItrA.hasNext() ) {
3520 ReferenceEdge edgeA = heapRegionsItrA.next();
3521 HeapRegionNode hrnChildA = edgeA.getDst();
3522 Integer idChildA = hrnChildA.getID();
3524 // at this point we know an edge in graph A exists
3525 // tdA -> idChildA, does this exist in B?
3526 assert td2ln.containsKey(tdA);
3527 LabelNode lnB = td2ln.get(tdA);
3528 ReferenceEdge edgeToMerge = null;
3530 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
3531 while( heapRegionsItrB.hasNext() &&
3532 edgeToMerge == null ) {
3534 ReferenceEdge edgeB = heapRegionsItrB.next();
3535 HeapRegionNode hrnChildB = edgeB.getDst();
3536 Integer idChildB = hrnChildB.getID();
3538 // don't use the ReferenceEdge.equals() here because
3539 // we're talking about existence between graphs
3540 if( idChildB.equals( idChildA ) &&
3541 edgeB.typeAndFieldEquals( edgeA ) ) {
3543 edgeToMerge = edgeB;
3547 // if the edge from A was not found in B,
3549 if( edgeToMerge == null ) {
3550 assert id2hrn.containsKey(idChildA);
3551 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3552 edgeToMerge = edgeA.copy();
3553 edgeToMerge.setSrc(lnB);
3554 edgeToMerge.setDst(hrnChildB);
3555 addReferenceEdge(lnB, hrnChildB, edgeToMerge);
3557 // otherwise, the edge already existed in both graphs
3558 // so merge their reachability sets
3560 // just replace this beta set with the union
3561 edgeToMerge.setBeta(
3562 edgeToMerge.getBeta().union(edgeA.getBeta() )
3564 if( !edgeA.isInitialParam() ) {
3565 edgeToMerge.setIsInitialParam(false);
3572 // you should only merge ownership graphs that have the
3573 // same number of parameters, or if one or both parameter
3574 // index tables are empty
3575 protected void mergeParamIndexMappings(OwnershipGraph og) {
3577 if( idPrimary2paramIndexSet.size() == 0 ) {
3579 idPrimary2paramIndexSet = og.idPrimary2paramIndexSet;
3580 paramIndex2idPrimary = og.paramIndex2idPrimary;
3582 idSecondary2paramIndexSet = og.idSecondary2paramIndexSet;
3583 paramIndex2idSecondary = og.paramIndex2idSecondary;
3585 paramIndex2tdQ = og.paramIndex2tdQ;
3586 paramIndex2tdR = og.paramIndex2tdR;
3588 paramTokenPrimary2paramIndex = og.paramTokenPrimary2paramIndex;
3589 paramIndex2paramTokenPrimary = og.paramIndex2paramTokenPrimary;
3591 paramTokenSecondary2paramIndex = og.paramTokenSecondary2paramIndex;
3592 paramIndex2paramTokenSecondary = og.paramIndex2paramTokenSecondary;
3593 paramTokenSecondaryPlus2paramIndex = og.paramTokenSecondaryPlus2paramIndex;
3594 paramIndex2paramTokenSecondaryPlus = og.paramIndex2paramTokenSecondaryPlus;
3595 paramTokenSecondaryStar2paramIndex = og.paramTokenSecondaryStar2paramIndex;
3596 paramIndex2paramTokenSecondaryStar = og.paramIndex2paramTokenSecondaryStar;
3601 if( og.idPrimary2paramIndexSet.size() == 0 ) {
3603 og.idPrimary2paramIndexSet = idPrimary2paramIndexSet;
3604 og.paramIndex2idPrimary = paramIndex2idPrimary;
3606 og.idSecondary2paramIndexSet = idSecondary2paramIndexSet;
3607 og.paramIndex2idSecondary = paramIndex2idSecondary;
3609 og.paramIndex2tdQ = paramIndex2tdQ;
3610 og.paramIndex2tdR = paramIndex2tdR;
3612 og.paramTokenPrimary2paramIndex = paramTokenPrimary2paramIndex;
3613 og.paramIndex2paramTokenPrimary = paramIndex2paramTokenPrimary;
3615 og.paramTokenSecondary2paramIndex = paramTokenSecondary2paramIndex;
3616 og.paramIndex2paramTokenSecondary = paramIndex2paramTokenSecondary;
3617 og.paramTokenSecondaryPlus2paramIndex = paramTokenSecondaryPlus2paramIndex;
3618 og.paramIndex2paramTokenSecondaryPlus = paramIndex2paramTokenSecondaryPlus;
3619 og.paramTokenSecondaryStar2paramIndex = paramTokenSecondaryStar2paramIndex;
3620 og.paramIndex2paramTokenSecondaryStar = paramIndex2paramTokenSecondaryStar;
3625 assert idPrimary2paramIndexSet.size() == og.idPrimary2paramIndexSet.size();
3626 assert idSecondary2paramIndexSet.size() == og.idSecondary2paramIndexSet.size();
3629 protected void mergeAllocationSites(OwnershipGraph og) {
3630 allocationSites.addAll(og.allocationSites);
3635 // it is necessary in the equals() member functions
3636 // to "check both ways" when comparing the data
3637 // structures of two graphs. For instance, if all
3638 // edges between heap region nodes in graph A are
3639 // present and equal in graph B it is not sufficient
3640 // to say the graphs are equal. Consider that there
3641 // may be edges in graph B that are not in graph A.
3642 // the only way to know that all edges in both graphs
3643 // are equally present is to iterate over both data
3644 // structures and compare against the other graph.
3645 public boolean equals(OwnershipGraph og) {
3651 if( !areHeapRegionNodesEqual(og) ) {
3655 if( !areLabelNodesEqual(og) ) {
3659 if( !areReferenceEdgesEqual(og) ) {
3663 if( !areParamIndexMappingsEqual(og) ) {
3667 // if everything is equal up to this point,
3668 // assert that allocationSites is also equal--
3669 // this data is redundant and kept for efficiency
3670 assert allocationSites.equals(og.allocationSites);
3675 protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
3677 if( !areallHRNinAalsoinBandequal(this, og) ) {
3681 if( !areallHRNinAalsoinBandequal(og, this) ) {
3688 static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
3689 OwnershipGraph ogB) {
3690 Set sA = ogA.id2hrn.entrySet();
3691 Iterator iA = sA.iterator();
3692 while( iA.hasNext() ) {
3693 Map.Entry meA = (Map.Entry)iA.next();
3694 Integer idA = (Integer) meA.getKey();
3695 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3697 if( !ogB.id2hrn.containsKey(idA) ) {
3701 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
3702 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
3711 protected boolean areLabelNodesEqual(OwnershipGraph og) {
3713 if( !areallLNinAalsoinBandequal(this, og) ) {
3717 if( !areallLNinAalsoinBandequal(og, this) ) {
3724 static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
3725 OwnershipGraph ogB) {
3726 Set sA = ogA.td2ln.entrySet();
3727 Iterator iA = sA.iterator();
3728 while( iA.hasNext() ) {
3729 Map.Entry meA = (Map.Entry)iA.next();
3730 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3732 if( !ogB.td2ln.containsKey(tdA) ) {
3741 protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
3742 if( !areallREinAandBequal(this, og) ) {
3749 static protected boolean areallREinAandBequal(OwnershipGraph ogA,
3750 OwnershipGraph ogB) {
3752 // check all the heap region->heap region edges
3753 Set sA = ogA.id2hrn.entrySet();
3754 Iterator iA = sA.iterator();
3755 while( iA.hasNext() ) {
3756 Map.Entry meA = (Map.Entry)iA.next();
3757 Integer idA = (Integer) meA.getKey();
3758 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3760 // we should have already checked that the same
3761 // heap regions exist in both graphs
3762 assert ogB.id2hrn.containsKey(idA);
3764 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
3768 // then check every edge in B for presence in A, starting
3769 // from the same parent HeapRegionNode
3770 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
3772 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
3777 // then check all the label->heap region edges
3778 sA = ogA.td2ln.entrySet();
3780 while( iA.hasNext() ) {
3781 Map.Entry meA = (Map.Entry)iA.next();
3782 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3783 LabelNode lnA = (LabelNode) meA.getValue();
3785 // we should have already checked that the same
3786 // label nodes exist in both graphs
3787 assert ogB.td2ln.containsKey(tdA);
3789 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
3793 // then check every edge in B for presence in A, starting
3794 // from the same parent LabelNode
3795 LabelNode lnB = ogB.td2ln.get(tdA);
3797 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
3806 static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
3808 OwnershipGraph ogB) {
3810 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
3811 while( itrA.hasNext() ) {
3812 ReferenceEdge edgeA = itrA.next();
3813 HeapRegionNode hrnChildA = edgeA.getDst();
3814 Integer idChildA = hrnChildA.getID();
3816 assert ogB.id2hrn.containsKey(idChildA);
3818 // at this point we know an edge in graph A exists
3819 // onA -> idChildA, does this exact edge exist in B?
3820 boolean edgeFound = false;
3822 OwnershipNode onB = null;
3823 if( onA instanceof HeapRegionNode ) {
3824 HeapRegionNode hrnA = (HeapRegionNode) onA;
3825 onB = ogB.id2hrn.get(hrnA.getID() );
3827 LabelNode lnA = (LabelNode) onA;
3828 onB = ogB.td2ln.get(lnA.getTempDescriptor() );
3831 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
3832 while( itrB.hasNext() ) {
3833 ReferenceEdge edgeB = itrB.next();
3834 HeapRegionNode hrnChildB = edgeB.getDst();
3835 Integer idChildB = hrnChildB.getID();
3837 if( idChildA.equals( idChildB ) &&
3838 edgeA.typeAndFieldEquals( edgeB ) ) {
3840 // there is an edge in the right place with the right field,
3841 // but do they have the same attributes?
3842 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
3857 protected boolean areParamIndexMappingsEqual(OwnershipGraph og) {
3859 if( idPrimary2paramIndexSet.size() != og.idPrimary2paramIndexSet.size() ) {
3863 if( idSecondary2paramIndexSet.size() != og.idSecondary2paramIndexSet.size() ) {
3871 public Set<HeapRegionNode> hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) {
3873 assert hrn1 != null;
3874 assert hrn2 != null;
3876 // then get the various tokens for these heap regions
3877 TokenTuple h1 = new TokenTuple(hrn1.getID(),
3878 !hrn1.isSingleObject(),
3879 TokenTuple.ARITY_ONE).makeCanonical();
3881 TokenTuple h1plus = new TokenTuple(hrn1.getID(),
3882 !hrn1.isSingleObject(),
3883 TokenTuple.ARITY_ONEORMORE).makeCanonical();
3885 TokenTuple h1star = new TokenTuple(hrn1.getID(),
3886 !hrn1.isSingleObject(),
3887 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
3889 TokenTuple h2 = new TokenTuple(hrn2.getID(),
3890 !hrn2.isSingleObject(),
3891 TokenTuple.ARITY_ONE).makeCanonical();
3893 TokenTuple h2plus = new TokenTuple(hrn2.getID(),
3894 !hrn2.isSingleObject(),
3895 TokenTuple.ARITY_ONEORMORE).makeCanonical();
3897 TokenTuple h2star = new TokenTuple(hrn2.getID(),
3898 !hrn2.isSingleObject(),
3899 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
3901 // then get the merged beta of all out-going edges from these heap regions
3902 ReachabilitySet beta1 = new ReachabilitySet();
3903 Iterator<ReferenceEdge> itrEdge = hrn1.iteratorToReferencees();
3904 while( itrEdge.hasNext() ) {
3905 ReferenceEdge edge = itrEdge.next();
3906 beta1 = beta1.union( edge.getBeta() );
3909 ReachabilitySet beta2 = new ReachabilitySet();
3910 itrEdge = hrn2.iteratorToReferencees();
3911 while( itrEdge.hasNext() ) {
3912 ReferenceEdge edge = itrEdge.next();
3913 beta2 = beta2.union( edge.getBeta() );
3916 boolean aliasDetected = false;
3918 // only do this one if they are different tokens
3920 beta1.containsTupleSetWithBoth(h1, h2) ) {
3921 aliasDetected = true;
3923 if( beta1.containsTupleSetWithBoth(h1plus, h2) ) {
3924 aliasDetected = true;
3926 if( beta1.containsTupleSetWithBoth(h1star, h2) ) {
3927 aliasDetected = true;
3929 if( beta1.containsTupleSetWithBoth(h1, h2plus) ) {
3930 aliasDetected = true;
3932 if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) {
3933 aliasDetected = true;
3935 if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) {
3936 aliasDetected = true;
3938 if( beta1.containsTupleSetWithBoth(h1, h2star) ) {
3939 aliasDetected = true;
3941 if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) {
3942 aliasDetected = true;
3944 if( beta1.containsTupleSetWithBoth(h1star, h2star) ) {
3945 aliasDetected = true;
3949 beta2.containsTupleSetWithBoth(h1, h2) ) {
3950 aliasDetected = true;
3952 if( beta2.containsTupleSetWithBoth(h1plus, h2) ) {
3953 aliasDetected = true;
3955 if( beta2.containsTupleSetWithBoth(h1star, h2) ) {
3956 aliasDetected = true;
3958 if( beta2.containsTupleSetWithBoth(h1, h2plus) ) {
3959 aliasDetected = true;
3961 if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) {
3962 aliasDetected = true;
3964 if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) {
3965 aliasDetected = true;
3967 if( beta2.containsTupleSetWithBoth(h1, h2star) ) {
3968 aliasDetected = true;
3970 if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) {
3971 aliasDetected = true;
3973 if( beta2.containsTupleSetWithBoth(h1star, h2star) ) {
3974 aliasDetected = true;
3977 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
3978 if( aliasDetected ) {
3979 common = findCommonReachableNodes( hrn1, hrn2 );
3980 assert !common.isEmpty();
3985 return new HashSet<HeapRegionNode>();
3989 public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
3991 // get parameter's heap region
3992 assert paramIndex2id.containsKey(paramIndex1);
3993 Integer idParam1 = paramIndex2id.get(paramIndex1);
3995 assert id2hrn.containsKey(idParam1);
3996 HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
3997 assert hrnParam1 != null;
4000 // get tokens for the other parameter
4001 assert paramIndex2id.containsKey(paramIndex2);
4002 Integer idParam2 = paramIndex2id.get(paramIndex2);
4004 assert id2hrn.containsKey(idParam2);
4005 HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
4006 assert hrnParam2 != null;
4008 return hasPotentialAlias( hrnParam1, hrnParam2 );
4010 return new HashSet<HeapRegionNode>();
4014 public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex, AllocationSite as) {
4016 // get parameter's heap region
4017 assert paramIndex2id.containsKey(paramIndex);
4018 Integer idParam = paramIndex2id.get(paramIndex);
4020 assert id2hrn.containsKey(idParam);
4021 HeapRegionNode hrnParam = id2hrn.get(idParam);
4022 assert hrnParam != null;
4025 assert id2hrn.containsKey( as.getSummary() );
4026 HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() );
4027 assert hrnSummary != null;
4029 Set<HeapRegionNode> common = hasPotentialAlias( hrnParam, hrnSummary );
4030 if( !common.isEmpty() ) {
4034 // check for other nodes
4035 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4037 assert id2hrn.containsKey( as.getIthOldest( i ) );
4038 HeapRegionNode hrnIthOldest = id2hrn.get( as.getIthOldest( i ) );
4039 assert hrnIthOldest != null;
4041 common = hasPotentialAlias( hrnParam, hrnIthOldest );
4042 if( !common.isEmpty() ) {
4047 return new HashSet<HeapRegionNode>();
4051 public Set<HeapRegionNode> hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
4053 // get summary node 1's alpha
4054 Integer idSum1 = as1.getSummary();
4055 assert id2hrn.containsKey(idSum1);
4056 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
4057 assert hrnSum1 != null;
4059 // get summary node 2's alpha
4060 Integer idSum2 = as2.getSummary();
4061 assert id2hrn.containsKey(idSum2);
4062 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
4063 assert hrnSum2 != null;
4065 Set<HeapRegionNode> common = hasPotentialAlias( hrnSum1, hrnSum2 );
4066 if( !common.isEmpty() ) {
4070 // check sum2 against alloc1 nodes
4071 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
4072 Integer idI1 = as1.getIthOldest(i);
4073 assert id2hrn.containsKey(idI1);
4074 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4075 assert hrnI1 != null;
4077 common = hasPotentialAlias( hrnI1, hrnSum2 );
4078 if( !common.isEmpty() ) {
4083 // check sum1 against alloc2 nodes
4084 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
4085 Integer idI2 = as2.getIthOldest(i);
4086 assert id2hrn.containsKey(idI2);
4087 HeapRegionNode hrnI2 = id2hrn.get(idI2);
4088 assert hrnI2 != null;
4090 common = hasPotentialAlias( hrnSum1, hrnI2 );
4091 if( common.isEmpty() ) {
4095 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4096 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
4097 Integer idI1 = as1.getIthOldest(j);
4099 // if these are the same site, don't look for the same token, no alias.
4100 // different tokens of the same site could alias together though
4101 if( idI1.equals( idI2 ) ) {
4105 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4107 common = hasPotentialAlias( hrnI1, hrnI2 );
4108 if( !common.isEmpty() ) {
4114 return new HashSet<HeapRegionNode>();
4118 public Set<HeapRegionNode> findCommonReachableNodes( HeapRegionNode hrn1,
4119 HeapRegionNode hrn2 ) {
4120 //assert hrn1 != hrn2;
4122 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
4123 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
4125 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
4126 todoNodes1.add( hrn1 );
4128 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
4129 todoNodes2.add( hrn2 );
4131 // follow links until all reachable nodes have been found
4132 while( !todoNodes1.isEmpty() ) {
4133 HeapRegionNode hrn = todoNodes1.iterator().next();
4134 todoNodes1.remove( hrn );
4135 reachableNodes1.add(hrn);
4137 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
4138 while( edgeItr.hasNext() ) {
4139 ReferenceEdge edge = edgeItr.next();
4141 if( !reachableNodes1.contains( edge.getDst() ) ) {
4142 todoNodes1.add( edge.getDst() );
4147 while( !todoNodes2.isEmpty() ) {
4148 HeapRegionNode hrn = todoNodes2.iterator().next();
4149 todoNodes2.remove( hrn );
4150 reachableNodes2.add(hrn);
4152 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
4153 while( edgeItr.hasNext() ) {
4154 ReferenceEdge edge = edgeItr.next();
4156 if( !reachableNodes2.contains( edge.getDst() ) ) {
4157 todoNodes2.add( edge.getDst() );
4162 Set<HeapRegionNode> intersection =
4163 new HashSet<HeapRegionNode>( reachableNodes1 );
4165 intersection.retainAll( reachableNodes2 );
4167 return intersection;
4171 // for writing ownership graphs to dot files
4172 public void writeGraph(MethodContext mc,
4174 boolean writeLabels,
4175 boolean labelSelect,
4176 boolean pruneGarbage,
4177 boolean writeReferencers,
4178 boolean writeParamMappings
4179 ) throws java.io.IOException {
4191 public void writeGraph(MethodContext mc,
4192 boolean writeLabels,
4193 boolean labelSelect,
4194 boolean pruneGarbage,
4195 boolean writeReferencers,
4196 boolean writeParamMappings
4197 ) throws java.io.IOException {
4199 writeGraph(mc+"COMPLETE",
4208 public void writeGraph(MethodContext mc,
4210 boolean writeLabels,
4211 boolean labelSelect,
4212 boolean pruneGarbage,
4213 boolean writeReferencers,
4214 boolean writeParamMappings
4215 ) throws java.io.IOException {
4219 writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate),
4228 public void writeGraph(String graphName,
4229 boolean writeLabels,
4230 boolean labelSelect,
4231 boolean pruneGarbage,
4232 boolean writeReferencers,
4233 boolean writeParamMappings
4234 ) throws java.io.IOException {
4236 // remove all non-word characters from the graph name so
4237 // the filename and identifier in dot don't cause errors
4238 graphName = graphName.replaceAll("[\\W]", "");
4240 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
4241 bw.write("digraph "+graphName+" {\n");
4243 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4245 // then visit every heap region node
4246 Set s = id2hrn.entrySet();
4247 Iterator i = s.iterator();
4248 while( i.hasNext() ) {
4249 Map.Entry me = (Map.Entry)i.next();
4250 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4252 if( !pruneGarbage ||
4253 (hrn.isFlagged() && hrn.getID() > 0) ||
4254 hrn.getDescription().startsWith("param")
4257 if( !visited.contains(hrn) ) {
4258 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4268 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4270 if( writeParamMappings ) {
4272 Set df = paramIndex2id.entrySet();
4273 Iterator ih = df.iterator();
4274 while( ih.hasNext() ) {
4275 Map.Entry meh = (Map.Entry)ih.next();
4276 Integer pi = (Integer) meh.getKey();
4277 Integer id = (Integer) meh.getValue();
4278 bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
4283 // then visit every label node, useful for debugging
4285 s = td2ln.entrySet();
4287 while( i.hasNext() ) {
4288 Map.Entry me = (Map.Entry)i.next();
4289 LabelNode ln = (LabelNode) me.getValue();
4292 String labelStr = ln.getTempDescriptorString();
4293 if( labelStr.startsWith("___temp") ||
4294 labelStr.startsWith("___dst") ||
4295 labelStr.startsWith("___srctmp") ||
4296 labelStr.startsWith("___neverused") ||
4297 labelStr.contains(qString) ||
4298 labelStr.contains(rString) ||
4299 labelStr.contains(blobString)
4305 //bw.write(" "+ln.toString() + ";\n");
4307 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
4308 while( heapRegionsItr.hasNext() ) {
4309 ReferenceEdge edge = heapRegionsItr.next();
4310 HeapRegionNode hrn = edge.getDst();
4312 if( pruneGarbage && !visited.contains(hrn) ) {
4313 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4321 bw.write(" " + ln.toString() +
4322 " -> " + hrn.toString() +
4323 "[label=\"" + edge.toGraphEdgeString() +
4334 protected void traverseHeapRegionNodes(int mode,
4338 HashSet<HeapRegionNode> visited,
4339 boolean writeReferencers
4340 ) throws java.io.IOException {
4342 if( visited.contains(hrn) ) {
4348 case VISIT_HRN_WRITE_FULL:
4350 String attributes = "[";
4352 if( hrn.isSingleObject() ) {
4353 attributes += "shape=box";
4355 attributes += "shape=Msquare";
4358 if( hrn.isFlagged() ) {
4359 attributes += ",style=filled,fillcolor=lightgrey";
4362 attributes += ",label=\"ID" +
4366 if( hrn.getType() != null ) {
4367 attributes += hrn.getType() + "\\n";
4370 attributes += hrn.getDescription() +
4372 hrn.getAlphaString() +
4375 bw.write(" " + hrn.toString() + attributes + ";\n");
4380 // useful for debugging
4383 if( writeReferencers ) {
4384 OwnershipNode onRef = null;
4385 Iterator refItr = hrn.iteratorToReferencers();
4386 while( refItr.hasNext() ) {
4387 onRef = (OwnershipNode) refItr.next();
4390 case VISIT_HRN_WRITE_FULL:
4391 bw.write(" " + hrn.toString() +
4392 " -> " + onRef.toString() +
4393 "[color=lightgray];\n");
4400 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
4401 while( childRegionsItr.hasNext() ) {
4402 ReferenceEdge edge = childRegionsItr.next();
4403 HeapRegionNode hrnChild = edge.getDst();
4406 case VISIT_HRN_WRITE_FULL:
4407 bw.write(" " + hrn.toString() +
4408 " -> " + hrnChild.toString() +
4409 "[label=\"" + edge.toGraphEdgeString() +
4414 traverseHeapRegionNodes(mode,