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 TempDescriptor tdReturn = new TempDescriptor("_Return___");
23 public Hashtable<Integer, HeapRegionNode> id2hrn;
24 public Hashtable<TempDescriptor, LabelNode > td2ln;
25 public Hashtable<Integer, Integer > id2paramIndex;
26 public Hashtable<Integer, Integer > paramIndex2id;
27 public Hashtable<Integer, TempDescriptor> paramIndex2tdQ;
29 public HashSet<AllocationSite> allocationSites;
34 public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
35 this.allocationDepth = allocationDepth;
36 this.typeUtil = typeUtil;
38 id2hrn = new Hashtable<Integer, HeapRegionNode>();
39 td2ln = new Hashtable<TempDescriptor, LabelNode >();
40 id2paramIndex = new Hashtable<Integer, Integer >();
41 paramIndex2id = new Hashtable<Integer, Integer >();
42 paramIndex2tdQ = new Hashtable<Integer, TempDescriptor>();
44 allocationSites = new HashSet <AllocationSite>();
48 // label nodes are much easier to deal with than
49 // heap region nodes. Whenever there is a request
50 // for the label node that is associated with a
51 // temp descriptor we can either find it or make a
52 // new one and return it. This is because temp
53 // descriptors are globally unique and every label
54 // node is mapped to exactly one temp descriptor.
55 protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
58 if( !td2ln.containsKey(td) ) {
59 td2ln.put(td, new LabelNode(td) );
66 // the reason for this method is to have the option
67 // creating new heap regions with specific IDs, or
68 // duplicating heap regions with specific IDs (especially
69 // in the merge() operation) or to create new heap
70 // regions with a new unique ID.
71 protected HeapRegionNode
72 createNewHeapRegionNode(Integer id,
73 boolean isSingleObject,
77 AllocationSite allocSite,
78 ReachabilitySet alpha,
82 id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
86 if( isFlagged || isParameter ) {
87 alpha = new ReachabilitySet(new TokenTuple(id,
92 alpha = new ReachabilitySet(new TokenTupleSet()
97 HeapRegionNode hrn = new HeapRegionNode(id,
110 ////////////////////////////////////////////////
112 // Low-level referencee and referencer methods
114 // These methods provide the lowest level for
115 // creating references between ownership nodes
116 // and handling the details of maintaining both
117 // list of referencers and referencees.
119 ////////////////////////////////////////////////
120 protected void addReferenceEdge(OwnershipNode referencer,
121 HeapRegionNode referencee,
122 ReferenceEdge edge) {
123 assert referencer != null;
124 assert referencee != null;
126 assert edge.getSrc() == referencer;
127 assert edge.getDst() == referencee;
129 referencer.addReferencee(edge);
130 referencee.addReferencer(edge);
133 protected void removeReferenceEdge(OwnershipNode referencer,
134 HeapRegionNode referencee,
135 FieldDescriptor fieldDesc) {
136 assert referencer != null;
137 assert referencee != null;
139 ReferenceEdge edge = referencer.getReferenceTo(referencee,
142 assert edge == referencee.getReferenceFrom(referencer,
145 referencer.removeReferencee(edge);
146 referencee.removeReferencer(edge);
149 protected void clearReferenceEdgesFrom(OwnershipNode referencer,
150 FieldDescriptor fieldDesc,
152 assert referencer != null;
154 // get a copy of the set to iterate over, otherwise
155 // we will be trying to take apart the set as we
156 // are iterating over it, which won't work
157 Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
158 while( i.hasNext() ) {
159 ReferenceEdge edge = i.next();
161 if( removeAll || edge.getFieldDesc() == fieldDesc ) {
162 HeapRegionNode referencee = edge.getDst();
164 removeReferenceEdge(referencer,
166 edge.getFieldDesc() );
171 protected void clearReferenceEdgesTo(HeapRegionNode referencee,
172 FieldDescriptor fieldDesc,
174 assert referencee != null;
176 // get a copy of the set to iterate over, otherwise
177 // we will be trying to take apart the set as we
178 // are iterating over it, which won't work
179 Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
180 while( i.hasNext() ) {
181 ReferenceEdge edge = i.next();
183 if( removeAll || edge.getFieldDesc() == fieldDesc ) {
184 OwnershipNode referencer = edge.getSrc();
185 removeReferenceEdge(referencer,
187 edge.getFieldDesc() );
193 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
195 HashSet<HeapRegionNode> nodesWithNewAlpha,
196 HashSet<ReferenceEdge> edgesWithNewBeta) {
198 HashSet<HeapRegionNode> todoNodes
199 = new HashSet<HeapRegionNode>();
200 todoNodes.add(nPrime);
202 HashSet<ReferenceEdge> todoEdges
203 = new HashSet<ReferenceEdge>();
205 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
206 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
207 nodePlannedChanges.put(nPrime, c0);
209 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
210 = new Hashtable<ReferenceEdge, ChangeTupleSet>();
213 while( !todoNodes.isEmpty() ) {
214 HeapRegionNode n = todoNodes.iterator().next();
215 ChangeTupleSet C = nodePlannedChanges.get(n);
217 Iterator itrC = C.iterator();
218 while( itrC.hasNext() ) {
219 ChangeTuple c = (ChangeTuple) itrC.next();
221 if( n.getAlpha().contains(c.getSetToMatch() ) ) {
222 ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
223 n.setAlphaNew(n.getAlphaNew().union(withChange) );
224 nodesWithNewAlpha.add(n);
228 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
229 while( referItr.hasNext() ) {
230 ReferenceEdge edge = referItr.next();
233 if( !edgePlannedChanges.containsKey(edge) ) {
234 edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
237 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
240 Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
241 while( refeeItr.hasNext() ) {
242 ReferenceEdge edgeF = refeeItr.next();
243 HeapRegionNode m = edgeF.getDst();
245 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
247 Iterator<ChangeTuple> itrCprime = C.iterator();
248 while( itrCprime.hasNext() ) {
249 ChangeTuple c = itrCprime.next();
250 if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
251 changesToPass = changesToPass.union(c);
255 if( !changesToPass.isEmpty() ) {
256 if( !nodePlannedChanges.containsKey(m) ) {
257 nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
260 ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
262 if( !changesToPass.isSubset(currentChanges) ) {
264 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
273 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
277 protected void propagateTokensOverEdges(
278 HashSet<ReferenceEdge> todoEdges,
279 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
280 HashSet<ReferenceEdge> edgesWithNewBeta) {
283 while( !todoEdges.isEmpty() ) {
284 ReferenceEdge edgeE = todoEdges.iterator().next();
285 todoEdges.remove(edgeE);
287 if( !edgePlannedChanges.containsKey(edgeE) ) {
288 edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
291 ChangeTupleSet C = edgePlannedChanges.get(edgeE);
293 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
295 Iterator<ChangeTuple> itrC = C.iterator();
296 while( itrC.hasNext() ) {
297 ChangeTuple c = itrC.next();
298 if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
299 ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
300 edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
301 edgesWithNewBeta.add(edgeE);
302 changesToPass = changesToPass.union(c);
306 OwnershipNode onSrc = edgeE.getSrc();
308 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
309 HeapRegionNode n = (HeapRegionNode) onSrc;
311 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
312 while( referItr.hasNext() ) {
313 ReferenceEdge edgeF = referItr.next();
315 if( !edgePlannedChanges.containsKey(edgeF) ) {
316 edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
319 ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
321 if( !changesToPass.isSubset(currentChanges) ) {
322 todoEdges.add(edgeF);
323 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
331 ////////////////////////////////////////////////////
333 // Assignment Operation Methods
335 // These methods are high-level operations for
336 // modeling program assignment statements using
337 // the low-level reference create/remove methods
340 // The destination in an assignment statement is
341 // going to have new references. The method of
342 // determining the references depends on the type
343 // of the FlatNode assignment and the predicates
344 // of the nodes and edges involved.
346 ////////////////////////////////////////////////////
347 public void assignTempXEqualToTempY(TempDescriptor x,
350 LabelNode lnX = getLabelNodeFromTemp(x);
351 LabelNode lnY = getLabelNodeFromTemp(y);
353 clearReferenceEdgesFrom(lnX, null, true);
355 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
356 while( itrYhrn.hasNext() ) {
357 ReferenceEdge edgeY = itrYhrn.next();
358 HeapRegionNode referencee = edgeY.getDst();
359 ReferenceEdge edgeNew = edgeY.copy();
362 addReferenceEdge(lnX, referencee, edgeNew);
367 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
370 LabelNode lnX = getLabelNodeFromTemp(x);
371 LabelNode lnY = getLabelNodeFromTemp(y);
373 clearReferenceEdgesFrom(lnX, null, true);
375 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
376 while( itrYhrn.hasNext() ) {
377 ReferenceEdge edgeY = itrYhrn.next();
378 HeapRegionNode hrnY = edgeY.getDst();
379 ReachabilitySet betaY = edgeY.getBeta();
381 Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
382 while( itrHrnFhrn.hasNext() ) {
383 ReferenceEdge edgeHrn = itrHrnFhrn.next();
384 HeapRegionNode hrnHrn = edgeHrn.getDst();
385 ReachabilitySet betaHrn = edgeHrn.getBeta();
387 if( edgeHrn.getFieldDesc() == null ||
388 edgeHrn.getFieldDesc() == f ) {
390 ReferenceEdge edgeNew = new ReferenceEdge(lnX,
394 betaY.intersection(betaHrn) );
396 addReferenceEdge(lnX, hrnHrn, edgeNew);
403 public void assignTempXFieldFEqualToTempY(TempDescriptor x,
406 LabelNode lnX = getLabelNodeFromTemp(x);
407 LabelNode lnY = getLabelNodeFromTemp(y);
409 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
410 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
412 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
413 while( itrXhrn.hasNext() ) {
414 ReferenceEdge edgeX = itrXhrn.next();
415 HeapRegionNode hrnX = edgeX.getDst();
416 ReachabilitySet betaX = edgeX.getBeta();
418 ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
420 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
421 while( itrYhrn.hasNext() ) {
422 ReferenceEdge edgeY = itrYhrn.next();
423 HeapRegionNode hrnY = edgeY.getDst();
424 ReachabilitySet O = edgeY.getBeta();
427 // propagate tokens over nodes starting from hrnSrc, and it will
428 // take care of propagating back up edges from any touched nodes
429 ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
430 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
433 // then propagate back just up the edges from hrn
434 ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
437 HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
439 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
440 new Hashtable<ReferenceEdge, ChangeTupleSet>();
442 Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
443 while( referItr.hasNext() ) {
444 ReferenceEdge edgeUpstream = referItr.next();
445 todoEdges.add(edgeUpstream);
446 edgePlannedChanges.put(edgeUpstream, Cx);
449 propagateTokensOverEdges(todoEdges,
454 if( edgeY.getBetaNew().equals( new ReachabilitySet() ) ) {
455 edgeY.setBetaNew( new ReachabilitySet( new TokenTupleSet().makeCanonical() ).makeCanonical() );
459 System.out.println( "---------------------------\n" +
461 "\nbeing pruned by\n" +
464 edgeY.getBetaNew().pruneBy(hrnX.getAlpha())
468 // create the actual reference edge hrnX.f -> hrnY
469 ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
473 edgeY.getBetaNew().pruneBy(hrnX.getAlpha() )
474 //edgeY.getBeta().pruneBy( hrnX.getAlpha() )
476 addReferenceEdge(hrnX, hrnY, edgeNew);
480 // we can do a strong update here if one of two cases holds
481 // SAVE FOR LATER, WITHOUT STILL CORRECT
482 if( (hrnX.getNumReferencers() == 1) ||
483 ( lnX.getNumReferencees() == 1 && hrnX.isSingleObject() )
485 clearReferenceEdgesFrom( hrnX, f, false );
488 addReferenceEdge( hrnX, hrnY, edgeNew );
491 // if the field is null, or "any" field, then
492 // look to see if an any field already exists
493 // and merge with it, otherwise just add the edge
494 ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
496 if( edgeExisting != null ) {
497 edgeExisting.setBetaNew(
498 edgeExisting.getBetaNew().union( edgeNew.getBeta() )
500 // a new edge here cannot be reflexive, so existing will
501 // always be also not reflexive anymore
502 edgeExisting.setIsInitialParamReflexive( false );
505 addReferenceEdge( hrnX, hrnY, edgeNew );
512 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
513 while( nodeItr.hasNext() ) {
514 nodeItr.next().applyAlphaNew();
517 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
518 while( edgeItr.hasNext() ) {
519 edgeItr.next().applyBetaNew();
524 public void assignTempEqualToParamAlloc(TempDescriptor td,
526 Integer paramIndex) {
529 LabelNode lnParam = getLabelNodeFromTemp(td);
530 HeapRegionNode hrn = createNewHeapRegionNode(null,
537 "param" + paramIndex);
539 // this is a non-program-accessible label that picks up beta
540 // info to be used for fixing a caller of this method
541 TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
542 LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
544 // keep track of heap regions that were created for
545 // parameter labels, the index of the parameter they
546 // are for is important when resolving method calls
547 Integer newID = hrn.getID();
548 assert !id2paramIndex.containsKey(newID);
549 assert !id2paramIndex.containsValue(paramIndex);
550 id2paramIndex.put(newID, paramIndex);
551 paramIndex2id.put(paramIndex, newID);
552 paramIndex2tdQ.put(paramIndex, tdParamQ);
554 ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
556 TokenTuple.ARITY_ONE) );
558 // heap regions for parameters are always multiple object (see above)
559 // and have a reference to themselves, because we can't know the
560 // structure of memory that is passed into the method. We're assuming
563 ReferenceEdge edgeFromLabel =
564 new ReferenceEdge(lnParam, hrn, null, false, beta);
566 ReferenceEdge edgeFromLabelQ =
567 new ReferenceEdge(lnParamQ, hrn, null, false, beta);
569 ReferenceEdge edgeReflexive =
570 new ReferenceEdge(hrn, hrn, null, true, beta);
572 addReferenceEdge(lnParam, hrn, edgeFromLabel);
573 addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
574 addReferenceEdge(hrn, hrn, edgeReflexive);
578 public void assignReturnEqualToTemp(TempDescriptor x) {
580 LabelNode lnR = getLabelNodeFromTemp(tdReturn);
581 LabelNode lnX = getLabelNodeFromTemp(x);
583 clearReferenceEdgesFrom(lnR, null, true);
585 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
586 while( itrXhrn.hasNext() ) {
587 ReferenceEdge edgeX = itrXhrn.next();
588 HeapRegionNode referencee = edgeX.getDst();
589 ReferenceEdge edgeNew = edgeX.copy();
592 addReferenceEdge(lnR, referencee, edgeNew);
597 public void assignTempEqualToNewAlloc(TempDescriptor x,
604 // after the age operation the newest (or zero-ith oldest)
605 // node associated with the allocation site should have
606 // no references to it as if it were a newly allocated
607 // heap region, so make a reference to it to complete
610 Integer idNewest = as.getIthOldest(0);
611 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
612 assert hrnNewest != null;
614 LabelNode lnX = getLabelNodeFromTemp(x);
615 clearReferenceEdgesFrom(lnX, null, true);
617 ReferenceEdge edgeNew =
618 new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
620 addReferenceEdge(lnX, hrnNewest, edgeNew);
624 // use the allocation site (unique to entire analysis) to
625 // locate the heap region nodes in this ownership graph
626 // that should be aged. The process models the allocation
627 // of new objects and collects all the oldest allocations
628 // in a summary node to allow for a finite analysis
630 // There is an additional property of this method. After
631 // running it on a particular ownership graph (many graphs
632 // may have heap regions related to the same allocation site)
633 // the heap region node objects in this ownership graph will be
634 // allocated. Therefore, after aging a graph for an allocation
635 // site, attempts to retrieve the heap region nodes using the
636 // integer id's contained in the allocation site should always
637 // return non-null heap regions.
638 public void age(AllocationSite as) {
640 // aging adds this allocation site to the graph's
641 // list of sites that exist in the graph, or does
642 // nothing if the site is already in the list
643 allocationSites.add(as);
645 // get the summary node for the allocation site in the context
646 // of this particular ownership graph
647 HeapRegionNode hrnSummary = getSummaryNode(as);
649 // merge oldest node into summary
650 Integer idK = as.getOldest();
651 HeapRegionNode hrnK = id2hrn.get(idK);
652 mergeIntoSummary(hrnK, hrnSummary);
654 // move down the line of heap region nodes
655 // clobbering the ith and transferring all references
656 // to and from i-1 to node i. Note that this clobbers
657 // the oldest node (hrnK) that was just merged into
659 for( int i = allocationDepth - 1; i > 0; --i ) {
661 // move references from the i-1 oldest to the ith oldest
662 Integer idIth = as.getIthOldest(i);
663 HeapRegionNode hrnI = id2hrn.get(idIth);
664 Integer idImin1th = as.getIthOldest(i - 1);
665 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
667 transferOnto(hrnImin1, hrnI);
670 // as stated above, the newest node should have had its
671 // references moved over to the second oldest, so we wipe newest
672 // in preparation for being the new object to assign something to
673 Integer id0th = as.getIthOldest(0);
674 HeapRegionNode hrn0 = id2hrn.get(id0th);
677 // clear all references in and out of newest node
678 clearReferenceEdgesFrom(hrn0, null, true);
679 clearReferenceEdgesTo(hrn0, null, true);
682 // now tokens in reachability sets need to "age" also
683 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
684 while( itrAllLabelNodes.hasNext() ) {
685 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
686 LabelNode ln = (LabelNode) me.getValue();
688 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
689 while( itrEdges.hasNext() ) {
690 ageTokens(as, itrEdges.next() );
694 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
695 while( itrAllHRNodes.hasNext() ) {
696 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
697 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
699 ageTokens(as, hrnToAge);
701 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
702 while( itrEdges.hasNext() ) {
703 ageTokens(as, itrEdges.next() );
708 // after tokens have been aged, reset newest node's reachability
709 if( hrn0.isFlagged() ) {
710 hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet(
716 hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet()
723 protected HeapRegionNode getSummaryNode(AllocationSite as) {
725 Integer idSummary = as.getSummary();
726 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
728 // If this is null then we haven't touched this allocation site
729 // in the context of the current ownership graph, so allocate
730 // heap region nodes appropriate for the entire allocation site.
731 // This should only happen once per ownership graph per allocation site,
732 // and a particular integer id can be used to locate the heap region
733 // in different ownership graphs that represents the same part of an
735 if( hrnSummary == null ) {
737 boolean hasFlags = false;
738 if( as.getType().isClass() ) {
739 hasFlags = as.getType().getClassDesc().hasFlags();
742 hrnSummary = createNewHeapRegionNode(idSummary,
749 as + "\\n" + as.getType() + "\\nsummary");
751 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
752 Integer idIth = as.getIthOldest(i);
753 assert !id2hrn.containsKey(idIth);
754 createNewHeapRegionNode(idIth,
761 as + "\\n" + as.getType() + "\\n" + i + " oldest");
769 protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
771 Integer idShadowSummary = as.getSummaryShadow();
772 HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
774 if( hrnShadowSummary == null ) {
776 boolean hasFlags = false;
777 if( as.getType().isClass() ) {
778 hasFlags = as.getType().getClassDesc().hasFlags();
781 hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
788 as + "\\n" + as.getType() + "\\nshadowSum");
790 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
791 Integer idShadowIth = as.getIthOldestShadow(i);
792 assert !id2hrn.containsKey(idShadowIth);
793 createNewHeapRegionNode(idShadowIth,
800 as + "\\n" + as.getType() + "\\n" + i + " shadow");
804 return hrnShadowSummary;
808 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
809 assert hrnSummary.isNewSummary();
811 // transfer references _from_ hrn over to hrnSummary
812 Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
813 while( itrReferencee.hasNext() ) {
814 ReferenceEdge edge = itrReferencee.next();
815 ReferenceEdge edgeMerged = edge.copy();
816 edgeMerged.setSrc(hrnSummary);
818 HeapRegionNode hrnReferencee = edge.getDst();
819 ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
821 if( edgeSummary == null ) {
822 // the merge is trivial, nothing to be done
824 // otherwise an edge from the referencer to hrnSummary exists already
825 // and the edge referencer->hrn should be merged with it
826 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
829 addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
832 // next transfer references _to_ hrn over to hrnSummary
833 Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
834 while( itrReferencer.hasNext() ) {
835 ReferenceEdge edge = itrReferencer.next();
836 ReferenceEdge edgeMerged = edge.copy();
837 edgeMerged.setDst(hrnSummary);
839 OwnershipNode onReferencer = edge.getSrc();
840 ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
842 if( edgeSummary == null ) {
843 // the merge is trivial, nothing to be done
845 // otherwise an edge from the referencer to alpha_S exists already
846 // and the edge referencer->alpha_K should be merged with it
847 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
850 addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
853 // then merge hrn reachability into hrnSummary
854 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
858 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
860 // clear references in and out of node i
861 clearReferenceEdgesFrom(hrnB, null, true);
862 clearReferenceEdgesTo(hrnB, null, true);
864 // copy each edge in and out of A to B
865 Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
866 while( itrReferencee.hasNext() ) {
867 ReferenceEdge edge = itrReferencee.next();
868 HeapRegionNode hrnReferencee = edge.getDst();
869 ReferenceEdge edgeNew = edge.copy();
870 edgeNew.setSrc(hrnB);
872 addReferenceEdge(hrnB, hrnReferencee, edgeNew);
875 Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
876 while( itrReferencer.hasNext() ) {
877 ReferenceEdge edge = itrReferencer.next();
878 OwnershipNode onReferencer = edge.getSrc();
879 ReferenceEdge edgeNew = edge.copy();
880 edgeNew.setDst(hrnB);
882 addReferenceEdge(onReferencer, hrnB, edgeNew);
885 // replace hrnB reachability with hrnA's
886 hrnB.setAlpha(hrnA.getAlpha() );
890 protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
891 edge.setBeta(edge.getBeta().ageTokens(as) );
894 protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
895 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
899 public void resolveMethodCall(FlatCall fc,
902 OwnershipGraph ogCallee) {
904 // define rewrite rules and other structures to organize
905 // data by parameter/argument index
906 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
907 new Hashtable<Integer, ReachabilitySet>();
909 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
910 new Hashtable<Integer, ReachabilitySet>();
912 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
913 new Hashtable<Integer, ReachabilitySet>();
915 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d =
916 new Hashtable<Integer, ReachabilitySet>();
918 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
919 new Hashtable<Integer, ReachabilitySet>();
921 // helpful structures
922 Hashtable<TokenTuple, Integer> paramToken2paramIndex =
923 new Hashtable<TokenTuple, Integer>();
925 Hashtable<Integer, TokenTuple> paramIndex2paramToken =
926 new Hashtable<Integer, TokenTuple>();
928 Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex =
929 new Hashtable<TokenTuple, Integer>();
931 Hashtable<Integer, TokenTuple> paramIndex2paramTokenPlus =
932 new Hashtable<Integer, TokenTuple>();
934 Hashtable<Integer, LabelNode> paramIndex2ln =
935 new Hashtable<Integer, LabelNode>();
937 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
938 new Hashtable<Integer, HashSet<HeapRegionNode> >();
941 // add a bogus entry with the identity rule for easy rewrite
942 // of new callee nodes and edges, doesn't belong to any parameter
943 Integer bogusID = new Integer(-1);
944 Integer bogusIndex = new Integer(-1);
945 TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE);
946 TokenTuple bogusTokenPlus = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONEORMORE);
947 ReachabilitySet rsIdentity =
948 new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical();
950 paramIndex2rewriteH.put(bogusIndex, rsIdentity);
951 paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
952 paramToken2paramIndex.put(bogusToken, bogusIndex);
953 paramIndex2paramToken.put(bogusIndex, bogusToken);
954 paramTokenPlus2paramIndex.put(bogusTokenPlus, bogusIndex);
955 paramIndex2paramTokenPlus.put(bogusIndex, bogusTokenPlus);
958 for( int i = 0; i < fm.numParameters(); ++i ) {
959 Integer paramIndex = new Integer(i);
961 assert ogCallee.paramIndex2id.containsKey(paramIndex);
962 Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
964 assert ogCallee.id2hrn.containsKey(idParam);
965 HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
966 assert hrnParam != null;
967 paramIndex2rewriteH.put(paramIndex,
969 toShadowTokens(ogCallee, hrnParam.getAlpha() )
972 ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
973 assert edgeReflexive_i != null;
974 paramIndex2rewriteJ.put(paramIndex,
975 toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
978 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
979 assert tdParamQ != null;
980 LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
981 assert lnParamQ != null;
982 ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
983 assert edgeSpecialQ_i != null;
984 paramIndex2rewriteK.put(paramIndex,
985 toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
988 TokenTuple p_i = new TokenTuple(hrnParam.getID(),
990 TokenTuple.ARITY_ONE).makeCanonical();
991 paramToken2paramIndex.put(p_i, paramIndex);
992 paramIndex2paramToken.put(paramIndex, p_i);
994 TokenTuple p_i_plus = new TokenTuple(hrnParam.getID(),
996 TokenTuple.ARITY_ONEORMORE).makeCanonical();
997 paramTokenPlus2paramIndex.put(p_i_plus, paramIndex);
998 paramIndex2paramTokenPlus.put(paramIndex, p_i_plus);
1000 // now depending on whether the callee is static or not
1001 // we need to account for a "this" argument in order to
1002 // find the matching argument in the caller context
1003 TempDescriptor argTemp_i;
1005 argTemp_i = fc.getArg(paramIndex);
1007 if( paramIndex.equals( 0 ) ) {
1008 argTemp_i = fc.getThis();
1010 argTemp_i = fc.getArg(paramIndex - 1);
1014 // in non-static methods there is a "this" pointer
1015 // that should be taken into account
1017 assert fc.numArgs() == fm.numParameters();
1019 assert fc.numArgs() + 1 == fm.numParameters();
1022 LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1023 paramIndex2ln.put(paramIndex, argLabel_i);
1025 ReachabilitySet d_i = new ReachabilitySet().makeCanonical();
1026 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1027 while( edgeItr.hasNext() ) {
1028 ReferenceEdge edge = edgeItr.next();
1029 d_i = d_i.union(edge.getBeta());
1031 paramIndex2rewrite_d.put(paramIndex, d_i);
1033 ReachabilitySet D_i = d_i.exhaustiveArityCombinations();
1034 paramIndex2rewriteD.put(paramIndex, D_i);
1038 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1039 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
1041 HashSet<ReferenceEdge> edgesReachable = new HashSet<ReferenceEdge>();
1042 HashSet<ReferenceEdge> edgesUpstream = new HashSet<ReferenceEdge>();
1044 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1045 while( lnArgItr.hasNext() ) {
1046 Map.Entry me = (Map.Entry)lnArgItr.next();
1047 Integer index = (Integer) me.getKey();
1048 LabelNode lnArg_i = (LabelNode) me.getValue();
1050 // rewrite alpha for the nodes reachable from argument label i
1051 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1052 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1054 // to find all reachable nodes, start with label referencees
1055 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1056 while( edgeArgItr.hasNext() ) {
1057 ReferenceEdge edge = edgeArgItr.next();
1058 todoNodes.add(edge.getDst() );
1061 // then follow links until all reachable nodes have been found
1062 while( !todoNodes.isEmpty() ) {
1063 HeapRegionNode hrn = todoNodes.iterator().next();
1064 todoNodes.remove(hrn);
1065 reachableNodes.add(hrn);
1067 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1068 while( edgeItr.hasNext() ) {
1069 ReferenceEdge edge = edgeItr.next();
1071 if( !reachableNodes.contains(edge.getDst() ) ) {
1072 todoNodes.add(edge.getDst() );
1078 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1080 // now iterate over reachable nodes to update their alpha, and
1081 // classify edges found as "argument reachable" or "upstream"
1082 Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1083 while( hrnItr.hasNext() ) {
1084 HeapRegionNode hrn = hrnItr.next();
1086 rewriteCallerReachability(index,
1089 paramIndex2rewriteH.get(index),
1090 paramIndex2rewrite_d,
1091 paramIndex2rewriteD,
1092 paramIndex2paramToken.get(index),
1093 paramToken2paramIndex,
1094 paramTokenPlus2paramIndex,
1098 nodesWithNewAlpha.add(hrn);
1100 // look at all incoming edges to the reachable nodes
1101 // and sort them as edges reachable from the argument
1102 // label node, or upstream edges
1103 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1104 while( edgeItr.hasNext() ) {
1105 ReferenceEdge edge = edgeItr.next();
1107 OwnershipNode on = edge.getSrc();
1109 if( on instanceof LabelNode ) {
1111 LabelNode ln0 = (LabelNode) on;
1112 if( ln0.equals(lnArg_i) ) {
1113 edgesReachable.add(edge);
1115 edgesUpstream.add(edge);
1120 HeapRegionNode hrn0 = (HeapRegionNode) on;
1121 if( reachableNodes.contains(hrn0) ) {
1122 edgesReachable.add(edge);
1124 edgesUpstream.add(edge);
1130 // update reachable edges
1131 Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1132 while( edgeReachableItr.hasNext() ) {
1133 ReferenceEdge edgeReachable = edgeReachableItr.next();
1135 rewriteCallerReachability(index,
1138 paramIndex2rewriteJ.get(index),
1139 paramIndex2rewrite_d,
1140 paramIndex2rewriteD,
1141 paramIndex2paramToken.get(index),
1142 paramToken2paramIndex,
1143 paramTokenPlus2paramIndex,
1147 edgesWithNewBeta.add(edgeReachable);
1150 // update upstream edges
1151 Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
1152 new Hashtable<ReferenceEdge, ChangeTupleSet>();
1154 Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1155 while( edgeUpstreamItr.hasNext() ) {
1156 ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1158 rewriteCallerReachability(index,
1161 paramIndex2rewriteK.get(index),
1162 paramIndex2rewrite_d,
1163 paramIndex2rewriteD,
1164 paramIndex2paramToken.get(index),
1165 paramToken2paramIndex,
1166 paramTokenPlus2paramIndex,
1168 edgeUpstreamPlannedChanges);
1170 edgesWithNewBeta.add(edgeUpstream);
1173 propagateTokensOverEdges(edgesUpstream,
1174 edgeUpstreamPlannedChanges,
1179 // commit changes to alpha and beta
1180 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1181 while( nodeItr.hasNext() ) {
1182 nodeItr.next().applyAlphaNew();
1185 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1186 while( edgeItr.hasNext() ) {
1187 edgeItr.next().applyBetaNew();
1191 // verify the existence of allocation sites and their
1192 // shadows from the callee in the context of this caller graph
1193 // then map allocated nodes of callee onto the caller shadows
1195 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1196 while( asItr.hasNext() ) {
1197 AllocationSite allocSite = asItr.next();
1198 HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1200 // assert that the shadow nodes have no reference edges
1201 // because they're brand new to the graph, or last time
1202 // they were used they should have been cleared of edges
1203 HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1204 assert hrnShadowSummary.getNumReferencers() == 0;
1205 assert hrnShadowSummary.getNumReferencees() == 0;
1207 // then bring g_ij onto g'_ij and rewrite
1208 transferOnto(hrnSummary, hrnShadowSummary);
1210 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1211 hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1213 // shadow nodes only are touched by a rewrite one time,
1214 // so rewrite and immediately commit--and they don't belong
1215 // to a particular parameter, so use a bogus param index
1216 // that pulls a self-rewrite out of H
1217 rewriteCallerReachability(bogusIndex,
1220 hrnShadowSummary.getAlpha(),
1221 paramIndex2rewrite_d,
1222 paramIndex2rewriteD,
1224 paramToken2paramIndex,
1225 paramTokenPlus2paramIndex,
1229 hrnShadowSummary.applyAlphaNew();
1232 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1233 Integer idIth = allocSite.getIthOldest(i);
1234 assert id2hrn.containsKey(idIth);
1235 HeapRegionNode hrnIth = id2hrn.get(idIth);
1237 Integer idShadowIth = -(allocSite.getIthOldest(i));
1238 assert id2hrn.containsKey(idShadowIth);
1239 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1240 assert hrnIthShadow.getNumReferencers() == 0;
1241 assert hrnIthShadow.getNumReferencees() == 0;
1243 transferOnto(hrnIth, hrnIthShadow);
1245 assert ogCallee.id2hrn.containsKey(idIth);
1246 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1247 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1249 rewriteCallerReachability(bogusIndex,
1252 hrnIthShadow.getAlpha(),
1253 paramIndex2rewrite_d,
1254 paramIndex2rewriteD,
1256 paramToken2paramIndex,
1257 paramTokenPlus2paramIndex,
1261 hrnIthShadow.applyAlphaNew();
1266 // for every heap region->heap region edge in the
1267 // callee graph, create the matching edge or edges
1268 // in the caller graph
1269 Set sCallee = ogCallee.id2hrn.entrySet();
1270 Iterator iCallee = sCallee.iterator();
1271 while( iCallee.hasNext() ) {
1272 Map.Entry meCallee = (Map.Entry)iCallee.next();
1273 Integer idCallee = (Integer) meCallee.getKey();
1274 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1276 Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1277 while( heapRegionsItrCallee.hasNext() ) {
1278 ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
1279 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1280 Integer idChildCallee = hrnChildCallee.getID();
1282 // only address this edge if it is not a special reflexive edge
1283 if( !edgeCallee.isInitialParamReflexive() ) {
1285 // now we know that in the callee method's ownership graph
1286 // there is a heap region->heap region reference edge given
1287 // by heap region pointers:
1288 // hrnCallee -> heapChildCallee
1290 // or by the ownership-graph independent ID's:
1291 // idCallee -> idChildCallee
1293 // make the edge with src and dst so beta info is
1294 // calculated once, then copy it for each new edge in caller
1295 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1297 edgeCallee.getFieldDesc(),
1299 toShadowTokens(ogCallee, edgeCallee.getBeta() )
1301 rewriteCallerReachability(bogusIndex,
1303 edgeNewInCallerTemplate,
1304 edgeNewInCallerTemplate.getBeta(),
1305 paramIndex2rewrite_d,
1306 paramIndex2rewriteD,
1308 paramToken2paramIndex,
1309 paramTokenPlus2paramIndex,
1313 edgeNewInCallerTemplate.applyBetaNew();
1316 // So now make a set of possible source heaps in the caller graph
1317 // and a set of destination heaps in the caller graph, and make
1318 // a reference edge in the caller for every possible (src,dst) pair
1319 HashSet<HeapRegionNode> possibleCallerSrcs =
1320 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1321 (HeapRegionNode) edgeCallee.getSrc(),
1322 paramIndex2reachableCallerNodes);
1324 HashSet<HeapRegionNode> possibleCallerDsts =
1325 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1326 edgeCallee.getDst(),
1327 paramIndex2reachableCallerNodes);
1330 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1331 Iterator srcItr = possibleCallerSrcs.iterator();
1332 while( srcItr.hasNext() ) {
1333 HeapRegionNode src = (HeapRegionNode) srcItr.next();
1335 if( !hasMatchingField(src, edgeCallee) ) {
1336 // prune this source node possibility
1340 Iterator dstItr = possibleCallerDsts.iterator();
1341 while( dstItr.hasNext() ) {
1342 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1344 if( !hasMatchingType(edgeCallee, dst) ) {
1349 // otherwise the caller src and dst pair can match the edge, so make it
1350 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1351 edgeNewInCaller.setSrc(src);
1352 edgeNewInCaller.setDst(dst);
1354 ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1355 if( edgeExisting == null ) {
1356 // if this edge doesn't exist in the caller, create it
1357 addReferenceEdge(src, dst, edgeNewInCaller);
1359 // if it already exists, merge with it
1360 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1369 // return value may need to be assigned in caller
1370 TempDescriptor returnTemp = fc.getReturnTemp();
1371 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
1373 LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
1374 clearReferenceEdgesFrom(lnLhsCaller, null, true);
1376 LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1377 Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1378 while( edgeCalleeItr.hasNext() ) {
1379 ReferenceEdge edgeCallee = edgeCalleeItr.next();
1381 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1383 edgeCallee.getFieldDesc(),
1385 toShadowTokens(ogCallee, edgeCallee.getBeta() )
1387 rewriteCallerReachability(bogusIndex,
1389 edgeNewInCallerTemplate,
1390 edgeNewInCallerTemplate.getBeta(),
1391 paramIndex2rewrite_d,
1392 paramIndex2rewriteD,
1394 paramToken2paramIndex,
1395 paramTokenPlus2paramIndex,
1399 edgeNewInCallerTemplate.applyBetaNew();
1402 HashSet<HeapRegionNode> assignCallerRhs =
1403 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1404 edgeCallee.getDst(),
1405 paramIndex2reachableCallerNodes);
1407 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1408 while( itrHrn.hasNext() ) {
1409 HeapRegionNode hrnCaller = itrHrn.next();
1411 if( !hasMatchingType(edgeCallee, hrnCaller) ) {
1416 // otherwise caller node can match callee edge, so make it
1417 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1418 edgeNewInCaller.setSrc(lnLhsCaller);
1419 edgeNewInCaller.setDst(hrnCaller);
1421 ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1422 if( edgeExisting == null ) {
1424 // if this edge doesn't exist in the caller, create it
1425 addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1427 // if it already exists, merge with it
1428 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1435 // merge the shadow nodes of allocation sites back down to normal capacity
1436 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1437 while( allocItr.hasNext() ) {
1438 AllocationSite as = allocItr.next();
1440 // first age each allocation site enough times to make room for the shadow nodes
1441 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1445 // then merge the shadow summary into the normal summary
1446 HeapRegionNode hrnSummary = getSummaryNode(as);
1447 assert hrnSummary != null;
1449 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1450 assert hrnSummaryShadow != null;
1452 mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1454 // then clear off after merge
1455 clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1456 clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1457 hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1459 // then transplant shadow nodes onto the now clean normal nodes
1460 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1462 Integer idIth = as.getIthOldest(i);
1463 HeapRegionNode hrnIth = id2hrn.get(idIth);
1465 Integer idIthShadow = as.getIthOldestShadow(i);
1466 HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1468 transferOnto(hrnIthShadow, hrnIth);
1470 // clear off shadow nodes after transfer
1471 clearReferenceEdgesFrom(hrnIthShadow, null, true);
1472 clearReferenceEdgesTo(hrnIthShadow, null, true);
1473 hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1476 // finally, globally change shadow tokens into normal tokens
1477 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1478 while( itrAllLabelNodes.hasNext() ) {
1479 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1480 LabelNode ln = (LabelNode) me.getValue();
1482 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1483 while( itrEdges.hasNext() ) {
1484 unshadowTokens(as, itrEdges.next() );
1488 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1489 while( itrAllHRNodes.hasNext() ) {
1490 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1491 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1493 unshadowTokens(as, hrnToAge);
1495 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1496 while( itrEdges.hasNext() ) {
1497 unshadowTokens(as, itrEdges.next() );
1504 protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
1506 // if no allocation site, then it's a match-everything region
1507 AllocationSite asSrc = src.getAllocationSite();
1508 if( asSrc == null ) {
1512 TypeDescriptor tdSrc = asSrc.getType();
1513 assert tdSrc != null;
1515 // if it's not a class, it doesn't have any fields to match
1516 if( !tdSrc.isClass() ) {
1520 Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
1521 while( fieldsSrcItr.hasNext() ) {
1522 FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1523 if( fd == edge.getFieldDesc() ) {
1528 // otherwise it is a class with fields
1529 // but we didn't find a match
1534 protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
1536 // if the region has no type, matches everything
1537 AllocationSite asDst = dst.getAllocationSite();
1538 if( asDst == null ) {
1542 TypeDescriptor tdDst = asDst.getType();
1543 assert tdDst != null;
1545 // if the type is not a class don't match because
1546 // primitives are copied, no memory aliases
1547 ClassDescriptor cdDst = tdDst.getClassDesc();
1548 if( cdDst == null ) {
1552 // if the field is null, it matches everything
1553 FieldDescriptor fd = edge.getFieldDesc();
1557 TypeDescriptor tdFd = fd.getType();
1558 assert tdFd != null;
1560 return typeUtil.isSuperorType(tdFd, tdDst);
1565 protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1566 edge.setBeta(edge.getBeta().unshadowTokens(as) );
1569 protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1570 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1574 private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1575 ReachabilitySet rsIn) {
1577 ReachabilitySet rsOut = new ReachabilitySet(rsIn);
1579 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1580 while( allocItr.hasNext() ) {
1581 AllocationSite as = allocItr.next();
1583 rsOut = rsOut.toShadowTokens(as);
1586 return rsOut.makeCanonical();
1590 private void rewriteCallerReachability(Integer paramIndex,
1593 ReachabilitySet rules,
1594 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d,
1595 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1597 Hashtable<TokenTuple, Integer> paramToken2paramIndex,
1598 Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex,
1599 boolean makeChangeSet,
1600 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1601 assert (hrn == null && edge != null) ||
1602 (hrn != null && edge == null);
1604 assert rules != null;
1607 ReachabilitySet callerReachabilityCurrent;
1609 callerReachabilityCurrent = edge.getBeta();
1611 callerReachabilityCurrent = hrn.getAlpha();
1614 ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
1616 // for initializing structures in this method
1617 TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
1619 // use this to construct a change set if required; the idea is to
1620 // map every partially rewritten token tuple set to the set of
1621 // caller-context token tuple sets that were used to generate it
1622 Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
1623 new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
1624 rewritten2source.put(ttsEmpty, new HashSet<TokenTupleSet>() );
1627 Iterator<TokenTupleSet> rulesItr = rules.iterator();
1628 while(rulesItr.hasNext()) {
1629 TokenTupleSet rule = rulesItr.next();
1631 ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
1633 Iterator<TokenTuple> ruleItr = rule.iterator();
1634 while(ruleItr.hasNext()) {
1635 TokenTuple ttCallee = ruleItr.next();
1637 // compute the possibilities for rewriting this callee token
1638 ReachabilitySet ttCalleeRewrites = null;
1639 boolean callerSourceUsed = false;
1641 if( ttCallee.equals( p_i ) ) {
1642 // replace the arity-one token of the current parameter with the reachability
1643 // information from the caller edge
1644 ttCalleeRewrites = callerReachabilityCurrent;
1645 callerSourceUsed = true;
1647 } else if( paramToken2paramIndex.containsKey( ttCallee ) ) {
1649 Integer paramIndex_j = paramToken2paramIndex.get( ttCallee );
1650 assert paramIndex_j != null;
1651 ttCalleeRewrites = paramIndex2rewrite_d.get( paramIndex_j );
1652 assert ttCalleeRewrites != null;
1654 } else if( paramTokenPlus2paramIndex.containsKey( ttCallee ) ) {
1656 Integer paramIndex_j = paramTokenPlus2paramIndex.get( ttCallee );
1657 assert paramIndex_j != null;
1658 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
1659 assert ttCalleeRewrites != null;
1662 // otherwise there's no need for a rewrite, just pass this one on
1663 TokenTupleSet ttsCaller = new TokenTupleSet(ttCallee).makeCanonical();
1664 ttCalleeRewrites = new ReachabilitySet(ttsCaller).makeCanonical();
1667 // branch every version of the working rewritten rule with
1668 // the possibilities for rewriting the current callee token
1669 ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
1671 Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
1672 while( rewrittenRuleItr.hasNext() ) {
1673 TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
1675 Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
1676 while( ttCalleeRewritesItr.hasNext() ) {
1677 TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
1679 TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
1681 if( makeChangeSet ) {
1682 // in order to keep the list of source token tuple sets
1683 // start with the sets used to make the partially rewritten
1684 // rule up to this point
1685 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewritten );
1686 assert sourceSets != null;
1688 // make a shallow copy for possible modification
1689 sourceSets = (HashSet<TokenTupleSet>) sourceSets.clone();
1691 // if we used something from the caller to rewrite it, remember
1692 if( callerSourceUsed ) {
1693 sourceSets.add( ttsBranch );
1696 // set mapping for the further rewritten rule
1697 rewritten2source.put( ttsRewrittenNext, sourceSets );
1700 rewrittenRuleWithTTCallee =
1701 rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
1705 // now the rewritten rule's possibilities have been extended by
1706 // rewriting the current callee token, remember result
1707 rewrittenRule = rewrittenRuleWithTTCallee;
1710 // the rule has been entirely rewritten into the caller context
1711 // now, so add it to the new reachability information
1712 callerReachabilityNew =
1713 callerReachabilityNew.union( rewrittenRule );
1716 if( makeChangeSet ) {
1717 ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
1719 // each possibility for the final reachability should have a set of
1720 // caller sources mapped to it, use to create the change set
1721 Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
1722 while( callerReachabilityItr.hasNext() ) {
1723 TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
1724 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewrittenFinal );
1725 assert sourceSets != null;
1727 Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
1728 while( sourceSetsItr.hasNext() ) {
1729 TokenTupleSet ttsSource = sourceSetsItr.next();
1732 callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
1736 assert edgePlannedChanges != null;
1737 edgePlannedChanges.put(edge, callerChangeSet);
1741 edge.setBetaNew(edge.getBetaNew().union(callerReachabilityNew) );
1743 hrn.setAlphaNew(hrn.getAlphaNew().union(callerReachabilityNew) );
1749 private HashSet<HeapRegionNode>
1750 getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1751 HeapRegionNode hrnCallee,
1752 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1755 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1757 Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
1759 if( paramIndexCallee == null ) {
1760 // this is a node allocated in the callee then and it has
1761 // exactly one shadow node in the caller to map to
1762 AllocationSite as = hrnCallee.getAllocationSite();
1765 int age = as.getAgeCategory(hrnCallee.getID() );
1766 assert age != AllocationSite.AGE_notInThisSite;
1769 if( age == AllocationSite.AGE_summary ) {
1770 idCaller = as.getSummaryShadow();
1771 } else if( age == AllocationSite.AGE_oldest ) {
1772 idCaller = as.getOldestShadow();
1774 assert age == AllocationSite.AGE_in_I;
1776 Integer I = as.getAge(hrnCallee.getID() );
1779 idCaller = as.getIthOldestShadow(I);
1782 assert id2hrn.containsKey(idCaller);
1783 HeapRegionNode hrnCaller = id2hrn.get(idCaller);
1784 possibleCallerHRNs.add(hrnCaller);
1787 // this is a node that was created to represent a parameter
1788 // so it maps to a whole mess of heap regions
1789 assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
1790 possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
1793 return possibleCallerHRNs;
1798 ////////////////////////////////////////////////////
1799 // in merge() and equals() methods the suffix A
1800 // represents the passed in graph and the suffix
1801 // B refers to the graph in this object
1802 // Merging means to take the incoming graph A and
1803 // merge it into B, so after the operation graph B
1804 // is the final result.
1805 ////////////////////////////////////////////////////
1806 public void merge(OwnershipGraph og) {
1812 mergeOwnershipNodes(og);
1813 mergeReferenceEdges(og);
1814 mergeId2paramIndex(og);
1815 mergeAllocationSites(og);
1819 protected void mergeOwnershipNodes(OwnershipGraph og) {
1820 Set sA = og.id2hrn.entrySet();
1821 Iterator iA = sA.iterator();
1822 while( iA.hasNext() ) {
1823 Map.Entry meA = (Map.Entry)iA.next();
1824 Integer idA = (Integer) meA.getKey();
1825 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1827 // if this graph doesn't have a node the
1828 // incoming graph has, allocate it
1829 if( !id2hrn.containsKey(idA) ) {
1830 HeapRegionNode hrnB = hrnA.copy();
1831 id2hrn.put(idA, hrnB);
1834 // otherwise this is a node present in both graphs
1835 // so make the new reachability set a union of the
1836 // nodes' reachability sets
1837 HeapRegionNode hrnB = id2hrn.get(idA);
1838 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1842 // now add any label nodes that are in graph B but
1844 sA = og.td2ln.entrySet();
1846 while( iA.hasNext() ) {
1847 Map.Entry meA = (Map.Entry)iA.next();
1848 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1849 LabelNode lnA = (LabelNode) meA.getValue();
1851 // if the label doesn't exist in B, allocate and add it
1852 LabelNode lnB = getLabelNodeFromTemp(tdA);
1856 protected void mergeReferenceEdges(OwnershipGraph og) {
1859 Set sA = og.id2hrn.entrySet();
1860 Iterator iA = sA.iterator();
1861 while( iA.hasNext() ) {
1862 Map.Entry meA = (Map.Entry)iA.next();
1863 Integer idA = (Integer) meA.getKey();
1864 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1866 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1867 while( heapRegionsItrA.hasNext() ) {
1868 ReferenceEdge edgeA = heapRegionsItrA.next();
1869 HeapRegionNode hrnChildA = edgeA.getDst();
1870 Integer idChildA = hrnChildA.getID();
1872 // at this point we know an edge in graph A exists
1873 // idA -> idChildA, does this exist in B?
1874 assert id2hrn.containsKey(idA);
1875 HeapRegionNode hrnB = id2hrn.get(idA);
1876 ReferenceEdge edgeToMerge = null;
1878 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1879 while( heapRegionsItrB.hasNext() &&
1880 edgeToMerge == null ) {
1882 ReferenceEdge edgeB = heapRegionsItrB.next();
1883 HeapRegionNode hrnChildB = edgeB.getDst();
1884 Integer idChildB = hrnChildB.getID();
1886 // don't use the ReferenceEdge.equals() here because
1887 // we're talking about existence between graphs
1888 if( idChildB.equals(idChildA) &&
1889 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1890 edgeToMerge = edgeB;
1894 // if the edge from A was not found in B,
1896 if( edgeToMerge == null ) {
1897 assert id2hrn.containsKey(idChildA);
1898 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1899 edgeToMerge = edgeA.copy();
1900 edgeToMerge.setSrc(hrnB);
1901 edgeToMerge.setDst(hrnChildB);
1902 addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1904 // otherwise, the edge already existed in both graphs
1905 // so merge their reachability sets
1907 // just replace this beta set with the union
1908 assert edgeToMerge != null;
1909 edgeToMerge.setBeta(
1910 edgeToMerge.getBeta().union(edgeA.getBeta() )
1912 if( !edgeA.isInitialParamReflexive() ) {
1913 edgeToMerge.setIsInitialParamReflexive(false);
1919 // and then again with label nodes
1920 sA = og.td2ln.entrySet();
1922 while( iA.hasNext() ) {
1923 Map.Entry meA = (Map.Entry)iA.next();
1924 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1925 LabelNode lnA = (LabelNode) meA.getValue();
1927 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1928 while( heapRegionsItrA.hasNext() ) {
1929 ReferenceEdge edgeA = heapRegionsItrA.next();
1930 HeapRegionNode hrnChildA = edgeA.getDst();
1931 Integer idChildA = hrnChildA.getID();
1933 // at this point we know an edge in graph A exists
1934 // tdA -> idChildA, does this exist in B?
1935 assert td2ln.containsKey(tdA);
1936 LabelNode lnB = td2ln.get(tdA);
1937 ReferenceEdge edgeToMerge = null;
1939 // labels never have edges with a field
1940 //assert edgeA.getFieldDesc() == null;
1942 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1943 while( heapRegionsItrB.hasNext() &&
1944 edgeToMerge == null ) {
1946 ReferenceEdge edgeB = heapRegionsItrB.next();
1947 HeapRegionNode hrnChildB = edgeB.getDst();
1948 Integer idChildB = hrnChildB.getID();
1950 // labels never have edges with a field
1951 //assert edgeB.getFieldDesc() == null;
1953 // don't use the ReferenceEdge.equals() here because
1954 // we're talking about existence between graphs
1955 if( idChildB.equals(idChildA) &&
1956 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1957 edgeToMerge = edgeB;
1961 // if the edge from A was not found in B,
1963 if( edgeToMerge == null ) {
1964 assert id2hrn.containsKey(idChildA);
1965 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1966 edgeToMerge = edgeA.copy();
1967 edgeToMerge.setSrc(lnB);
1968 edgeToMerge.setDst(hrnChildB);
1969 addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1971 // otherwise, the edge already existed in both graphs
1972 // so merge their reachability sets
1974 // just replace this beta set with the union
1975 edgeToMerge.setBeta(
1976 edgeToMerge.getBeta().union(edgeA.getBeta() )
1978 if( !edgeA.isInitialParamReflexive() ) {
1979 edgeToMerge.setIsInitialParamReflexive(false);
1986 // you should only merge ownership graphs that have the
1987 // same number of parameters, or if one or both parameter
1988 // index tables are empty
1989 protected void mergeId2paramIndex(OwnershipGraph og) {
1990 if( id2paramIndex.size() == 0 ) {
1991 id2paramIndex = og.id2paramIndex;
1992 paramIndex2id = og.paramIndex2id;
1993 paramIndex2tdQ = og.paramIndex2tdQ;
1997 if( og.id2paramIndex.size() == 0 ) {
2001 assert id2paramIndex.size() == og.id2paramIndex.size();
2004 protected void mergeAllocationSites(OwnershipGraph og) {
2005 allocationSites.addAll(og.allocationSites);
2010 // it is necessary in the equals() member functions
2011 // to "check both ways" when comparing the data
2012 // structures of two graphs. For instance, if all
2013 // edges between heap region nodes in graph A are
2014 // present and equal in graph B it is not sufficient
2015 // to say the graphs are equal. Consider that there
2016 // may be edges in graph B that are not in graph A.
2017 // the only way to know that all edges in both graphs
2018 // are equally present is to iterate over both data
2019 // structures and compare against the other graph.
2020 public boolean equals(OwnershipGraph og) {
2026 if( !areHeapRegionNodesEqual(og) ) {
2030 if( !areLabelNodesEqual(og) ) {
2034 if( !areReferenceEdgesEqual(og) ) {
2038 if( !areId2paramIndexEqual(og) ) {
2042 // if everything is equal up to this point,
2043 // assert that allocationSites is also equal--
2044 // this data is redundant and kept for efficiency
2045 assert allocationSites.equals(og.allocationSites);
2050 protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2052 if( !areallHRNinAalsoinBandequal(this, og) ) {
2056 if( !areallHRNinAalsoinBandequal(og, this) ) {
2063 static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2064 OwnershipGraph ogB) {
2065 Set sA = ogA.id2hrn.entrySet();
2066 Iterator iA = sA.iterator();
2067 while( iA.hasNext() ) {
2068 Map.Entry meA = (Map.Entry)iA.next();
2069 Integer idA = (Integer) meA.getKey();
2070 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2072 if( !ogB.id2hrn.containsKey(idA) ) {
2076 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2077 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2086 protected boolean areLabelNodesEqual(OwnershipGraph og) {
2088 if( !areallLNinAalsoinBandequal(this, og) ) {
2092 if( !areallLNinAalsoinBandequal(og, this) ) {
2099 static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2100 OwnershipGraph ogB) {
2101 Set sA = ogA.td2ln.entrySet();
2102 Iterator iA = sA.iterator();
2103 while( iA.hasNext() ) {
2104 Map.Entry meA = (Map.Entry)iA.next();
2105 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2107 if( !ogB.td2ln.containsKey(tdA) ) {
2116 protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2117 if( !areallREinAandBequal(this, og) ) {
2124 static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2125 OwnershipGraph ogB) {
2127 // check all the heap region->heap region edges
2128 Set sA = ogA.id2hrn.entrySet();
2129 Iterator iA = sA.iterator();
2130 while( iA.hasNext() ) {
2131 Map.Entry meA = (Map.Entry)iA.next();
2132 Integer idA = (Integer) meA.getKey();
2133 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2135 // we should have already checked that the same
2136 // heap regions exist in both graphs
2137 assert ogB.id2hrn.containsKey(idA);
2139 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2143 // then check every edge in B for presence in A, starting
2144 // from the same parent HeapRegionNode
2145 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2147 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2152 // then check all the label->heap region edges
2153 sA = ogA.td2ln.entrySet();
2155 while( iA.hasNext() ) {
2156 Map.Entry meA = (Map.Entry)iA.next();
2157 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2158 LabelNode lnA = (LabelNode) meA.getValue();
2160 // we should have already checked that the same
2161 // label nodes exist in both graphs
2162 assert ogB.td2ln.containsKey(tdA);
2164 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2168 // then check every edge in B for presence in A, starting
2169 // from the same parent LabelNode
2170 LabelNode lnB = ogB.td2ln.get(tdA);
2172 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2181 static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2183 OwnershipGraph ogB) {
2185 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2186 while( itrA.hasNext() ) {
2187 ReferenceEdge edgeA = itrA.next();
2188 HeapRegionNode hrnChildA = edgeA.getDst();
2189 Integer idChildA = hrnChildA.getID();
2191 assert ogB.id2hrn.containsKey(idChildA);
2193 // at this point we know an edge in graph A exists
2194 // onA -> idChildA, does this exact edge exist in B?
2195 boolean edgeFound = false;
2197 OwnershipNode onB = null;
2198 if( onA instanceof HeapRegionNode ) {
2199 HeapRegionNode hrnA = (HeapRegionNode) onA;
2200 onB = ogB.id2hrn.get(hrnA.getID() );
2202 LabelNode lnA = (LabelNode) onA;
2203 onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2206 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2207 while( itrB.hasNext() ) {
2208 ReferenceEdge edgeB = itrB.next();
2209 HeapRegionNode hrnChildB = edgeB.getDst();
2210 Integer idChildB = hrnChildB.getID();
2212 if( idChildA.equals(idChildB) &&
2213 edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2215 // there is an edge in the right place with the right field,
2216 // but do they have the same attributes?
2217 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2235 protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2236 return id2paramIndex.size() == og.id2paramIndex.size();
2240 public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
2242 // get parameter's heap region
2243 assert paramIndex2id.containsKey(paramIndex1);
2244 Integer idParam1 = paramIndex2id.get(paramIndex1);
2246 assert id2hrn.containsKey(idParam1);
2247 HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2248 assert hrnParam1 != null;
2250 // get tokens for this parameter
2251 TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2253 TokenTuple.ARITY_ONE).makeCanonical();
2255 TokenTuple pPlus1 = new TokenTuple(hrnParam1.getID(),
2257 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2259 TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2261 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2264 // get tokens for the other parameter
2265 assert paramIndex2id.containsKey(paramIndex2);
2266 Integer idParam2 = paramIndex2id.get(paramIndex2);
2268 assert id2hrn.containsKey(idParam2);
2269 HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2270 assert hrnParam2 != null;
2272 TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2274 TokenTuple.ARITY_ONE).makeCanonical();
2276 TokenTuple pPlus2 = new TokenTuple(hrnParam2.getID(),
2278 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2280 TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2282 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2285 // get special label p_q for first parameter
2286 TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2287 assert tdParamQ1 != null;
2288 LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2289 assert lnParamQ1 != null;
2291 // then get the edge from label q to parameter's hrn
2292 ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2293 assert edgeSpecialQ1 != null;
2295 // if the beta of this edge has tokens from both parameters in one
2296 // token tuple set, then there is a potential alias between them
2297 ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2298 assert beta1 != null;
2300 if( beta1.containsTupleSetWithBoth(p1, p2 ) ) { return true; }
2301 if( beta1.containsTupleSetWithBoth(pPlus1, p2 ) ) { return true; }
2302 if( beta1.containsTupleSetWithBoth(pStar1, p2 ) ) { return true; }
2303 if( beta1.containsTupleSetWithBoth(p1, pPlus2) ) { return true; }
2304 if( beta1.containsTupleSetWithBoth(pPlus1, pPlus2) ) { return true; }
2305 if( beta1.containsTupleSetWithBoth(pStar1, pPlus2) ) { return true; }
2306 if( beta1.containsTupleSetWithBoth(p1, pStar2) ) { return true; }
2307 if( beta1.containsTupleSetWithBoth(pPlus1, pStar2) ) { return true; }
2308 if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) { return true; }
2314 public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
2316 // get parameter's heap region
2317 assert paramIndex2id.containsKey(paramIndex);
2318 Integer idParam = paramIndex2id.get(paramIndex);
2320 assert id2hrn.containsKey(idParam);
2321 HeapRegionNode hrnParam = id2hrn.get(idParam);
2322 assert hrnParam != null;
2324 // get tokens for this parameter
2325 TokenTuple p = new TokenTuple(hrnParam.getID(),
2327 TokenTuple.ARITY_ONE).makeCanonical();
2329 TokenTuple pPlus = new TokenTuple(hrnParam.getID(),
2331 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2333 TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2335 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2337 // get special label p_q
2338 TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2339 assert tdParamQ != null;
2340 LabelNode lnParamQ = td2ln.get(tdParamQ);
2341 assert lnParamQ != null;
2343 // then get the edge from label q to parameter's hrn
2344 ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2345 assert edgeSpecialQ != null;
2347 // look through this beta set for potential aliases
2348 ReachabilitySet beta = edgeSpecialQ.getBeta();
2349 assert beta != null;
2352 // get tokens for summary node
2353 TokenTuple gs = new TokenTuple(as.getSummary(),
2355 TokenTuple.ARITY_ONE).makeCanonical();
2357 TokenTuple gsPlus = new TokenTuple(as.getSummary(),
2359 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2361 TokenTuple gsStar = new TokenTuple(as.getSummary(),
2363 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2366 if( beta.containsTupleSetWithBoth(p, gs ) ) { return true; }
2367 if( beta.containsTupleSetWithBoth(pPlus, gs ) ) { return true; }
2368 if( beta.containsTupleSetWithBoth(pStar, gs ) ) { return true; }
2369 if( beta.containsTupleSetWithBoth(p, gsPlus) ) { return true; }
2370 if( beta.containsTupleSetWithBoth(pPlus, gsPlus) ) { return true; }
2371 if( beta.containsTupleSetWithBoth(pStar, gsPlus) ) { return true; }
2372 if( beta.containsTupleSetWithBoth(p, gsStar) ) { return true; }
2373 if( beta.containsTupleSetWithBoth(pPlus, gsStar) ) { return true; }
2374 if( beta.containsTupleSetWithBoth(pStar, gsStar) ) { return true; }
2376 // check for other nodes
2377 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2379 // the other nodes of an allocation site are single, no plus
2380 TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2382 TokenTuple.ARITY_ONE).makeCanonical();
2384 TokenTuple giStar = new TokenTuple(as.getIthOldest(i),
2386 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2388 if( beta.containsTupleSetWithBoth(p, gi ) ) { return true; }
2389 if( beta.containsTupleSetWithBoth(pPlus, gi ) ) { return true; }
2390 if( beta.containsTupleSetWithBoth(pStar, gi ) ) { return true; }
2391 if( beta.containsTupleSetWithBoth(p, giStar) ) { return true; }
2392 if( beta.containsTupleSetWithBoth(pPlus, giStar) ) { return true; }
2393 if( beta.containsTupleSetWithBoth(pStar, giStar) ) { return true; }
2400 public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
2402 // get tokens for summary nodes
2403 TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2405 TokenTuple.ARITY_ONE).makeCanonical();
2407 TokenTuple gsPlus1 = new TokenTuple(as1.getSummary(),
2409 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2411 TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2413 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2415 // get summary node's alpha
2416 Integer idSum1 = as1.getSummary();
2417 assert id2hrn.containsKey(idSum1);
2418 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
2419 assert hrnSum1 != null;
2420 ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2421 assert alphaSum1 != null;
2424 // and for the other one
2425 TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2427 TokenTuple.ARITY_ONE).makeCanonical();
2429 TokenTuple gsPlus2 = new TokenTuple(as2.getSummary(),
2431 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2433 TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2435 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2437 // get summary node's alpha
2438 Integer idSum2 = as2.getSummary();
2439 assert id2hrn.containsKey(idSum2);
2440 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
2441 assert hrnSum2 != null;
2442 ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2443 assert alphaSum2 != null;
2445 // does either one report reachability from the other tokens?
2446 if( alphaSum1.containsTuple(gsPlus2) ) { return true; }
2447 if( alphaSum1.containsTuple(gsStar2) ) { return true; }
2448 if( alphaSum2.containsTuple(gsPlus1) ) { return true; }
2449 if( alphaSum2.containsTuple(gsStar1) ) { return true; }
2451 // only check ONE token if they are different sites
2453 if( alphaSum1.containsTuple(gs2) ) { return true; }
2454 if( alphaSum2.containsTuple(gs1) ) { return true; }
2458 // check sum2 against alloc1 nodes
2459 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2460 Integer idI1 = as1.getIthOldest(i);
2461 assert id2hrn.containsKey(idI1);
2462 HeapRegionNode hrnI1 = id2hrn.get(idI1);
2463 assert hrnI1 != null;
2464 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2465 assert alphaI1 != null;
2467 // the other nodes of an allocation site are single, no stars
2468 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2470 TokenTuple.ARITY_ONE).makeCanonical();
2472 TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(i),
2474 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2476 if( alphaSum2.containsTuple(gi1 ) ) { return true; }
2477 if( alphaSum2.containsTuple(giStar1) ) { return true; }
2478 if( alphaI1.containsTuple(gs2 ) ) { return true; }
2479 if( alphaI1.containsTuple(gsPlus2) ) { return true; }
2480 if( alphaI1.containsTuple(gsStar2) ) { return true; }
2483 // check sum1 against alloc2 nodes
2484 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2485 Integer idI2 = as2.getIthOldest(i);
2486 assert id2hrn.containsKey(idI2);
2487 HeapRegionNode hrnI2 = id2hrn.get(idI2);
2488 assert hrnI2 != null;
2489 ReachabilitySet alphaI2 = hrnI2.getAlpha();
2490 assert alphaI2 != null;
2492 TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2494 TokenTuple.ARITY_ONE).makeCanonical();
2496 TokenTuple giStar2 = new TokenTuple(as2.getIthOldest(i),
2498 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2500 if( alphaSum1.containsTuple(gi2 ) ) { return true; }
2501 if( alphaSum1.containsTuple(giStar2) ) { return true; }
2502 if( alphaI2.containsTuple(gs1 ) ) { return true; }
2503 if( alphaI2.containsTuple(gsPlus1) ) { return true; }
2504 if( alphaI2.containsTuple(gsStar1) ) { return true; }
2506 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
2507 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
2508 Integer idI1 = as1.getIthOldest(j);
2510 // if these are the same site, don't look for the same token, no alias.
2511 // different tokens of the same site could alias together though
2512 if( idI1 == idI2 ) {
2516 HeapRegionNode hrnI1 = id2hrn.get(idI1);
2517 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2518 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
2520 TokenTuple.ARITY_ONE).makeCanonical();
2522 TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(j),
2524 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2526 if( alphaI2.containsTuple(gi1 ) ) { return true; }
2527 if( alphaI2.containsTuple(giStar1) ) { return true; }
2528 if( alphaI1.containsTuple(gi2 ) ) { return true; }
2529 if( alphaI1.containsTuple(giStar2) ) { return true; }
2537 // for writing ownership graphs to dot files
2538 public void writeGraph(Descriptor methodDesc,
2540 boolean writeLabels,
2541 boolean labelSelect,
2542 boolean pruneGarbage,
2543 boolean writeReferencers,
2544 boolean writeParamMappings
2545 ) throws java.io.IOException {
2547 methodDesc.getSymbol() +
2548 methodDesc.getNum() +
2558 public void writeGraph(Descriptor methodDesc,
2559 boolean writeLabels,
2560 boolean labelSelect,
2561 boolean pruneGarbage,
2562 boolean writeReferencers,
2563 boolean writeParamMappings
2564 ) throws java.io.IOException {
2566 writeGraph(methodDesc+"COMPLETE",
2575 public void writeGraph(Descriptor methodDesc,
2577 boolean writeLabels,
2578 boolean labelSelect,
2579 boolean pruneGarbage,
2580 boolean writeReferencers,
2581 boolean writeParamMappings
2582 ) throws java.io.IOException {
2584 writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
2593 public void writeGraph(String graphName,
2594 boolean writeLabels,
2595 boolean labelSelect,
2596 boolean pruneGarbage,
2597 boolean writeReferencers,
2598 boolean writeParamMappings
2599 ) throws java.io.IOException {
2601 // remove all non-word characters from the graph name so
2602 // the filename and identifier in dot don't cause errors
2603 graphName = graphName.replaceAll("[\\W]", "");
2605 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2606 bw.write("digraph "+graphName+" {\n");
2608 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2610 // then visit every heap region node
2611 Set s = id2hrn.entrySet();
2612 Iterator i = s.iterator();
2613 while( i.hasNext() ) {
2614 Map.Entry me = (Map.Entry)i.next();
2615 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2616 if( !pruneGarbage ||
2618 hrn.getDescription().startsWith( "param" )
2621 if( !visited.contains(hrn) ) {
2622 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2632 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
2634 if( writeParamMappings ) {
2635 Set df = paramIndex2id.entrySet();
2636 Iterator ih = df.iterator();
2637 while( ih.hasNext() ) {
2638 Map.Entry meh = (Map.Entry)ih.next();
2639 Integer pi = (Integer) meh.getKey();
2640 Integer id = (Integer) meh.getValue();
2641 bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
2645 // then visit every label node, useful for debugging
2647 s = td2ln.entrySet();
2649 while( i.hasNext() ) {
2650 Map.Entry me = (Map.Entry)i.next();
2651 LabelNode ln = (LabelNode) me.getValue();
2654 String labelStr = ln.getTempDescriptorString();
2655 if( labelStr.startsWith("___temp") ||
2656 labelStr.startsWith("___dst") ||
2657 labelStr.startsWith("___srctmp") ||
2658 labelStr.startsWith("___neverused") ) {
2663 //bw.write(" "+ln.toString() + ";\n");
2665 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2666 while( heapRegionsItr.hasNext() ) {
2667 ReferenceEdge edge = heapRegionsItr.next();
2668 HeapRegionNode hrn = edge.getDst();
2670 if( pruneGarbage && !visited.contains(hrn) ) {
2671 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2679 bw.write(" " + ln.toString() +
2680 " -> " + hrn.toString() +
2681 "[label=\"" + edge.toGraphEdgeString() +
2692 protected void traverseHeapRegionNodes(int mode,
2696 HashSet<HeapRegionNode> visited,
2697 boolean writeReferencers
2698 ) throws java.io.IOException {
2700 if( visited.contains(hrn) ) {
2706 case VISIT_HRN_WRITE_FULL:
2708 String attributes = "[";
2710 if( hrn.isSingleObject() ) {
2711 attributes += "shape=box";
2713 attributes += "shape=Msquare";
2716 if( hrn.isFlagged() ) {
2717 attributes += ",style=filled,fillcolor=lightgrey";
2720 attributes += ",label=\"ID" +
2723 hrn.getDescription() +
2725 hrn.getAlphaString() +
2728 bw.write(" " + hrn.toString() + attributes + ";\n");
2733 // useful for debugging
2734 if( writeReferencers ) {
2735 OwnershipNode onRef = null;
2736 Iterator refItr = hrn.iteratorToReferencers();
2737 while( refItr.hasNext() ) {
2738 onRef = (OwnershipNode) refItr.next();
2741 case VISIT_HRN_WRITE_FULL:
2742 bw.write(" " + hrn.toString() +
2743 " -> " + onRef.toString() +
2744 "[color=lightgray];\n");
2750 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2751 while( childRegionsItr.hasNext() ) {
2752 ReferenceEdge edge = childRegionsItr.next();
2753 HeapRegionNode hrnChild = edge.getDst();
2756 case VISIT_HRN_WRITE_FULL:
2757 bw.write(" " + hrn.toString() +
2758 " -> " + hrnChild.toString() +
2759 "[label=\"" + edge.toGraphEdgeString() +
2764 traverseHeapRegionNodes(mode,