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);
436 HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
438 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
439 new Hashtable<ReferenceEdge, ChangeTupleSet>();
441 Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
442 while( referItr.hasNext() ) {
443 ReferenceEdge edgeUpstream = referItr.next();
444 todoEdges.add(edgeUpstream);
445 edgePlannedChanges.put(edgeUpstream, Cx);
448 propagateTokensOverEdges(todoEdges,
454 //System.out.println( edgeY.getBetaNew() + "\nbeing pruned by\n" + hrnX.getAlpha() );
456 // create the actual reference edge hrnX.f -> hrnY
457 ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
461 edgeY.getBetaNew().pruneBy(hrnX.getAlpha() )
462 //edgeY.getBeta().pruneBy( hrnX.getAlpha() )
464 addReferenceEdge(hrnX, hrnY, edgeNew);
468 // we can do a strong update here if one of two cases holds
469 // SAVE FOR LATER, WITHOUT STILL CORRECT
470 if( (hrnX.getNumReferencers() == 1) ||
471 ( lnX.getNumReferencees() == 1 && hrnX.isSingleObject() )
473 clearReferenceEdgesFrom( hrnX, f, false );
476 addReferenceEdge( hrnX, hrnY, edgeNew );
479 // if the field is null, or "any" field, then
480 // look to see if an any field already exists
481 // and merge with it, otherwise just add the edge
482 ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
484 if( edgeExisting != null ) {
485 edgeExisting.setBetaNew(
486 edgeExisting.getBetaNew().union( edgeNew.getBeta() )
488 // a new edge here cannot be reflexive, so existing will
489 // always be also not reflexive anymore
490 edgeExisting.setIsInitialParamReflexive( false );
493 addReferenceEdge( hrnX, hrnY, edgeNew );
500 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
501 while( nodeItr.hasNext() ) {
502 nodeItr.next().applyAlphaNew();
505 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
506 while( edgeItr.hasNext() ) {
507 edgeItr.next().applyBetaNew();
512 public void assignTempEqualToParamAlloc(TempDescriptor td,
514 Integer paramIndex) {
517 LabelNode lnParam = getLabelNodeFromTemp(td);
518 HeapRegionNode hrn = createNewHeapRegionNode(null,
525 "param" + paramIndex);
527 // this is a non-program-accessible label that picks up beta
528 // info to be used for fixing a caller of this method
529 TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
530 LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
532 // keep track of heap regions that were created for
533 // parameter labels, the index of the parameter they
534 // are for is important when resolving method calls
535 Integer newID = hrn.getID();
536 assert !id2paramIndex.containsKey(newID);
537 assert !id2paramIndex.containsValue(paramIndex);
538 id2paramIndex.put(newID, paramIndex);
539 paramIndex2id.put(paramIndex, newID);
540 paramIndex2tdQ.put(paramIndex, tdParamQ);
542 ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
544 TokenTuple.ARITY_ONE) );
546 // heap regions for parameters are always multiple object (see above)
547 // and have a reference to themselves, because we can't know the
548 // structure of memory that is passed into the method. We're assuming
551 ReferenceEdge edgeFromLabel =
552 new ReferenceEdge(lnParam, hrn, null, false, beta);
554 ReferenceEdge edgeFromLabelQ =
555 new ReferenceEdge(lnParamQ, hrn, null, false, beta);
557 ReferenceEdge edgeReflexive =
558 new ReferenceEdge(hrn, hrn, null, true, beta);
560 addReferenceEdge(lnParam, hrn, edgeFromLabel);
561 addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
562 addReferenceEdge(hrn, hrn, edgeReflexive);
566 public void assignReturnEqualToTemp(TempDescriptor x) {
568 LabelNode lnR = getLabelNodeFromTemp(tdReturn);
569 LabelNode lnX = getLabelNodeFromTemp(x);
571 clearReferenceEdgesFrom(lnR, null, true);
573 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
574 while( itrXhrn.hasNext() ) {
575 ReferenceEdge edgeX = itrXhrn.next();
576 HeapRegionNode referencee = edgeX.getDst();
577 ReferenceEdge edgeNew = edgeX.copy();
580 addReferenceEdge(lnR, referencee, edgeNew);
585 public void assignTempEqualToNewAlloc(TempDescriptor x,
592 // after the age operation the newest (or zero-ith oldest)
593 // node associated with the allocation site should have
594 // no references to it as if it were a newly allocated
595 // heap region, so make a reference to it to complete
598 Integer idNewest = as.getIthOldest(0);
599 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
600 assert hrnNewest != null;
602 LabelNode lnX = getLabelNodeFromTemp(x);
603 clearReferenceEdgesFrom(lnX, null, true);
605 ReferenceEdge edgeNew =
606 new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
608 addReferenceEdge(lnX, hrnNewest, edgeNew);
612 // use the allocation site (unique to entire analysis) to
613 // locate the heap region nodes in this ownership graph
614 // that should be aged. The process models the allocation
615 // of new objects and collects all the oldest allocations
616 // in a summary node to allow for a finite analysis
618 // There is an additional property of this method. After
619 // running it on a particular ownership graph (many graphs
620 // may have heap regions related to the same allocation site)
621 // the heap region node objects in this ownership graph will be
622 // allocated. Therefore, after aging a graph for an allocation
623 // site, attempts to retrieve the heap region nodes using the
624 // integer id's contained in the allocation site should always
625 // return non-null heap regions.
626 public void age(AllocationSite as) {
628 // aging adds this allocation site to the graph's
629 // list of sites that exist in the graph, or does
630 // nothing if the site is already in the list
631 allocationSites.add(as);
633 // get the summary node for the allocation site in the context
634 // of this particular ownership graph
635 HeapRegionNode hrnSummary = getSummaryNode(as);
637 // merge oldest node into summary
638 Integer idK = as.getOldest();
639 HeapRegionNode hrnK = id2hrn.get(idK);
640 mergeIntoSummary(hrnK, hrnSummary);
642 // move down the line of heap region nodes
643 // clobbering the ith and transferring all references
644 // to and from i-1 to node i. Note that this clobbers
645 // the oldest node (hrnK) that was just merged into
647 for( int i = allocationDepth - 1; i > 0; --i ) {
649 // move references from the i-1 oldest to the ith oldest
650 Integer idIth = as.getIthOldest(i);
651 HeapRegionNode hrnI = id2hrn.get(idIth);
652 Integer idImin1th = as.getIthOldest(i - 1);
653 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
655 transferOnto(hrnImin1, hrnI);
658 // as stated above, the newest node should have had its
659 // references moved over to the second oldest, so we wipe newest
660 // in preparation for being the new object to assign something to
661 Integer id0th = as.getIthOldest(0);
662 HeapRegionNode hrn0 = id2hrn.get(id0th);
665 // clear all references in and out of newest node
666 clearReferenceEdgesFrom(hrn0, null, true);
667 clearReferenceEdgesTo(hrn0, null, true);
670 // now tokens in reachability sets need to "age" also
671 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
672 while( itrAllLabelNodes.hasNext() ) {
673 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
674 LabelNode ln = (LabelNode) me.getValue();
676 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
677 while( itrEdges.hasNext() ) {
678 ageTokens(as, itrEdges.next() );
682 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
683 while( itrAllHRNodes.hasNext() ) {
684 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
685 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
687 ageTokens(as, hrnToAge);
689 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
690 while( itrEdges.hasNext() ) {
691 ageTokens(as, itrEdges.next() );
696 // after tokens have been aged, reset newest node's reachability
697 if( hrn0.isFlagged() ) {
698 hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet(
704 hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet()
711 protected HeapRegionNode getSummaryNode(AllocationSite as) {
713 Integer idSummary = as.getSummary();
714 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
716 // If this is null then we haven't touched this allocation site
717 // in the context of the current ownership graph, so allocate
718 // heap region nodes appropriate for the entire allocation site.
719 // This should only happen once per ownership graph per allocation site,
720 // and a particular integer id can be used to locate the heap region
721 // in different ownership graphs that represents the same part of an
723 if( hrnSummary == null ) {
725 boolean hasFlags = false;
726 if( as.getType().isClass() ) {
727 hasFlags = as.getType().getClassDesc().hasFlags();
730 hrnSummary = createNewHeapRegionNode(idSummary,
737 as + "\\n" + as.getType() + "\\nsummary");
739 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
740 Integer idIth = as.getIthOldest(i);
741 assert !id2hrn.containsKey(idIth);
742 createNewHeapRegionNode(idIth,
749 as + "\\n" + as.getType() + "\\n" + i + " oldest");
757 protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
759 Integer idShadowSummary = as.getSummaryShadow();
760 HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
762 if( hrnShadowSummary == null ) {
764 boolean hasFlags = false;
765 if( as.getType().isClass() ) {
766 hasFlags = as.getType().getClassDesc().hasFlags();
769 hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
776 as + "\\n" + as.getType() + "\\nshadowSum");
778 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
779 Integer idShadowIth = as.getIthOldestShadow(i);
780 assert !id2hrn.containsKey(idShadowIth);
781 createNewHeapRegionNode(idShadowIth,
788 as + "\\n" + as.getType() + "\\n" + i + " shadow");
792 return hrnShadowSummary;
796 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
797 assert hrnSummary.isNewSummary();
799 // transfer references _from_ hrn over to hrnSummary
800 Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
801 while( itrReferencee.hasNext() ) {
802 ReferenceEdge edge = itrReferencee.next();
803 ReferenceEdge edgeMerged = edge.copy();
804 edgeMerged.setSrc(hrnSummary);
806 HeapRegionNode hrnReferencee = edge.getDst();
807 ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
809 if( edgeSummary == null ) {
810 // the merge is trivial, nothing to be done
812 // otherwise an edge from the referencer to hrnSummary exists already
813 // and the edge referencer->hrn should be merged with it
814 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
817 addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
820 // next transfer references _to_ hrn over to hrnSummary
821 Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
822 while( itrReferencer.hasNext() ) {
823 ReferenceEdge edge = itrReferencer.next();
824 ReferenceEdge edgeMerged = edge.copy();
825 edgeMerged.setDst(hrnSummary);
827 OwnershipNode onReferencer = edge.getSrc();
828 ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
830 if( edgeSummary == null ) {
831 // the merge is trivial, nothing to be done
833 // otherwise an edge from the referencer to alpha_S exists already
834 // and the edge referencer->alpha_K should be merged with it
835 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
838 addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
841 // then merge hrn reachability into hrnSummary
842 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
846 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
848 // clear references in and out of node i
849 clearReferenceEdgesFrom(hrnB, null, true);
850 clearReferenceEdgesTo(hrnB, null, true);
852 // copy each edge in and out of A to B
853 Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
854 while( itrReferencee.hasNext() ) {
855 ReferenceEdge edge = itrReferencee.next();
856 HeapRegionNode hrnReferencee = edge.getDst();
857 ReferenceEdge edgeNew = edge.copy();
858 edgeNew.setSrc(hrnB);
860 addReferenceEdge(hrnB, hrnReferencee, edgeNew);
863 Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
864 while( itrReferencer.hasNext() ) {
865 ReferenceEdge edge = itrReferencer.next();
866 OwnershipNode onReferencer = edge.getSrc();
867 ReferenceEdge edgeNew = edge.copy();
868 edgeNew.setDst(hrnB);
870 addReferenceEdge(onReferencer, hrnB, edgeNew);
873 // replace hrnB reachability with hrnA's
874 hrnB.setAlpha(hrnA.getAlpha() );
878 protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
879 edge.setBeta(edge.getBeta().ageTokens(as) );
882 protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
883 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
887 public void resolveMethodCall(FlatCall fc,
890 OwnershipGraph ogCallee) {
892 // define rewrite rules and other structures to organize
893 // data by parameter/argument index
894 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
895 new Hashtable<Integer, ReachabilitySet>();
897 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
898 new Hashtable<Integer, ReachabilitySet>();
900 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
901 new Hashtable<Integer, ReachabilitySet>();
903 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
904 new Hashtable<Integer, ReachabilitySet>();
906 // helpful structures
907 Hashtable<TokenTuple, Integer> paramToken2paramIndex =
908 new Hashtable<TokenTuple, Integer>();
910 Hashtable<Integer, TokenTuple> paramIndex2paramToken =
911 new Hashtable<Integer, TokenTuple>();
913 Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
914 new Hashtable<TokenTuple, Integer>();
916 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
917 new Hashtable<Integer, TokenTuple>();
919 Hashtable<Integer, LabelNode> paramIndex2ln =
920 new Hashtable<Integer, LabelNode>();
922 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
923 new Hashtable<Integer, HashSet<HeapRegionNode> >();
926 // add a bogus entry with the identity rule for easy rewrite
927 // of new callee nodes and edges, doesn't belong to any parameter
928 Integer bogusID = new Integer(-1);
929 Integer bogusIndex = new Integer(-1);
930 TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE);
931 TokenTuple bogusTokenStar = new TokenTuple(bogusID, true, TokenTuple.ARITY_MANY);
932 ReachabilitySet rsIdentity =
933 new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical();
935 paramIndex2rewriteH.put(bogusIndex, rsIdentity);
936 paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
937 paramToken2paramIndex.put(bogusToken, bogusIndex);
938 paramIndex2paramToken.put(bogusIndex, bogusToken);
939 paramTokenStar2paramIndex.put(bogusTokenStar, bogusIndex);
940 paramIndex2paramTokenStar.put(bogusIndex, bogusTokenStar);
943 for( int i = 0; i < fm.numParameters(); ++i ) {
944 Integer paramIndex = new Integer(i);
946 assert ogCallee.paramIndex2id.containsKey(paramIndex);
947 Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
949 assert ogCallee.id2hrn.containsKey(idParam);
950 HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
951 assert hrnParam != null;
952 paramIndex2rewriteH.put(paramIndex,
954 toShadowTokens(ogCallee, hrnParam.getAlpha() )
957 ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
958 assert edgeReflexive_i != null;
959 paramIndex2rewriteJ.put(paramIndex,
960 toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
963 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
964 assert tdParamQ != null;
965 LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
966 assert lnParamQ != null;
967 ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
968 assert edgeSpecialQ_i != null;
969 paramIndex2rewriteK.put(paramIndex,
970 toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
973 TokenTuple p_i = new TokenTuple(hrnParam.getID(),
975 TokenTuple.ARITY_ONE).makeCanonical();
976 paramToken2paramIndex.put(p_i, paramIndex);
977 paramIndex2paramToken.put(paramIndex, p_i);
979 TokenTuple p_i_star = new TokenTuple(hrnParam.getID(),
981 TokenTuple.ARITY_MANY).makeCanonical();
982 paramTokenStar2paramIndex.put(p_i_star, paramIndex);
983 paramIndex2paramTokenStar.put(paramIndex, p_i_star);
985 // now depending on whether the callee is static or not
986 // we need to account for a "this" argument in order to
987 // find the matching argument in the caller context
988 TempDescriptor argTemp_i;
990 argTemp_i = fc.getArg(paramIndex);
992 if( paramIndex.equals( 0 ) ) {
993 argTemp_i = fc.getThis();
995 argTemp_i = fc.getArg(paramIndex - 1);
999 // in non-static methods there is a "this" pointer
1000 // that should be taken into account
1002 assert fc.numArgs() == fm.numParameters();
1004 assert fc.numArgs() + 1 == fm.numParameters();
1007 LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1008 paramIndex2ln.put(paramIndex, argLabel_i);
1010 ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
1011 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1012 while( edgeItr.hasNext() ) {
1013 ReferenceEdge edge = edgeItr.next();
1014 D_i = D_i.union(edge.getBeta());
1017 D_i = D_i.exhaustiveArityCombinations();
1019 paramIndex2rewriteD.put(paramIndex, D_i);
1023 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1024 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
1026 HashSet<ReferenceEdge> edgesReachable = new HashSet<ReferenceEdge>();
1027 HashSet<ReferenceEdge> edgesUpstream = new HashSet<ReferenceEdge>();
1029 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1030 while( lnArgItr.hasNext() ) {
1031 Map.Entry me = (Map.Entry)lnArgItr.next();
1032 Integer index = (Integer) me.getKey();
1033 LabelNode lnArg_i = (LabelNode) me.getValue();
1035 // rewrite alpha for the nodes reachable from argument label i
1036 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1037 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1039 // to find all reachable nodes, start with label referencees
1040 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1041 while( edgeArgItr.hasNext() ) {
1042 ReferenceEdge edge = edgeArgItr.next();
1043 todoNodes.add(edge.getDst() );
1046 // then follow links until all reachable nodes have been found
1047 while( !todoNodes.isEmpty() ) {
1048 HeapRegionNode hrn = todoNodes.iterator().next();
1049 todoNodes.remove(hrn);
1050 reachableNodes.add(hrn);
1052 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1053 while( edgeItr.hasNext() ) {
1054 ReferenceEdge edge = edgeItr.next();
1056 if( !reachableNodes.contains(edge.getDst() ) ) {
1057 todoNodes.add(edge.getDst() );
1063 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1065 // now iterate over reachable nodes to update their alpha, and
1066 // classify edges found as "argument reachable" or "upstream"
1067 Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1068 while( hrnItr.hasNext() ) {
1069 HeapRegionNode hrn = hrnItr.next();
1071 rewriteCallerReachability(index,
1074 paramIndex2rewriteH.get(index),
1075 paramIndex2rewriteD,
1076 paramIndex2paramToken.get(index),
1077 paramToken2paramIndex,
1078 paramTokenStar2paramIndex,
1082 nodesWithNewAlpha.add(hrn);
1084 // look at all incoming edges to the reachable nodes
1085 // and sort them as edges reachable from the argument
1086 // label node, or upstream edges
1087 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1088 while( edgeItr.hasNext() ) {
1089 ReferenceEdge edge = edgeItr.next();
1091 OwnershipNode on = edge.getSrc();
1093 if( on instanceof LabelNode ) {
1095 LabelNode ln0 = (LabelNode) on;
1096 if( ln0.equals(lnArg_i) ) {
1097 edgesReachable.add(edge);
1099 edgesUpstream.add(edge);
1104 HeapRegionNode hrn0 = (HeapRegionNode) on;
1105 if( reachableNodes.contains(hrn0) ) {
1106 edgesReachable.add(edge);
1108 edgesUpstream.add(edge);
1114 // update reachable edges
1115 Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1116 while( edgeReachableItr.hasNext() ) {
1117 ReferenceEdge edgeReachable = edgeReachableItr.next();
1119 rewriteCallerReachability(index,
1122 paramIndex2rewriteJ.get(index),
1123 paramIndex2rewriteD,
1124 paramIndex2paramToken.get(index),
1125 paramToken2paramIndex,
1126 paramTokenStar2paramIndex,
1130 edgesWithNewBeta.add(edgeReachable);
1133 // update upstream edges
1134 Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
1135 new Hashtable<ReferenceEdge, ChangeTupleSet>();
1137 Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1138 while( edgeUpstreamItr.hasNext() ) {
1139 ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1141 rewriteCallerReachability(index,
1144 paramIndex2rewriteK.get(index),
1145 paramIndex2rewriteD,
1146 paramIndex2paramToken.get(index),
1147 paramToken2paramIndex,
1148 paramTokenStar2paramIndex,
1150 edgeUpstreamPlannedChanges);
1152 edgesWithNewBeta.add(edgeUpstream);
1155 propagateTokensOverEdges(edgesUpstream,
1156 edgeUpstreamPlannedChanges,
1161 // commit changes to alpha and beta
1162 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1163 while( nodeItr.hasNext() ) {
1164 nodeItr.next().applyAlphaNew();
1167 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1168 while( edgeItr.hasNext() ) {
1169 edgeItr.next().applyBetaNew();
1173 // verify the existence of allocation sites and their
1174 // shadows from the callee in the context of this caller graph
1175 // then map allocated nodes of callee onto the caller shadows
1177 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1178 while( asItr.hasNext() ) {
1179 AllocationSite allocSite = asItr.next();
1180 HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1182 // assert that the shadow nodes have no reference edges
1183 // because they're brand new to the graph, or last time
1184 // they were used they should have been cleared of edges
1185 HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1186 assert hrnShadowSummary.getNumReferencers() == 0;
1187 assert hrnShadowSummary.getNumReferencees() == 0;
1189 // then bring g_ij onto g'_ij and rewrite
1190 transferOnto(hrnSummary, hrnShadowSummary);
1192 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1193 hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1195 // shadow nodes only are touched by a rewrite one time,
1196 // so rewrite and immediately commit--and they don't belong
1197 // to a particular parameter, so use a bogus param index
1198 // that pulls a self-rewrite out of H
1199 rewriteCallerReachability(bogusIndex,
1202 hrnShadowSummary.getAlpha(),
1203 paramIndex2rewriteD,
1205 paramToken2paramIndex,
1206 paramTokenStar2paramIndex,
1210 hrnShadowSummary.applyAlphaNew();
1213 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1214 Integer idIth = allocSite.getIthOldest(i);
1215 assert id2hrn.containsKey(idIth);
1216 HeapRegionNode hrnIth = id2hrn.get(idIth);
1218 Integer idShadowIth = -(allocSite.getIthOldest(i));
1219 assert id2hrn.containsKey(idShadowIth);
1220 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1221 assert hrnIthShadow.getNumReferencers() == 0;
1222 assert hrnIthShadow.getNumReferencees() == 0;
1224 transferOnto(hrnIth, hrnIthShadow);
1226 assert ogCallee.id2hrn.containsKey(idIth);
1227 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1228 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1230 rewriteCallerReachability(bogusIndex,
1233 hrnIthShadow.getAlpha(),
1234 paramIndex2rewriteD,
1236 paramToken2paramIndex,
1237 paramTokenStar2paramIndex,
1241 hrnIthShadow.applyAlphaNew();
1246 // for every heap region->heap region edge in the
1247 // callee graph, create the matching edge or edges
1248 // in the caller graph
1249 Set sCallee = ogCallee.id2hrn.entrySet();
1250 Iterator iCallee = sCallee.iterator();
1251 while( iCallee.hasNext() ) {
1252 Map.Entry meCallee = (Map.Entry)iCallee.next();
1253 Integer idCallee = (Integer) meCallee.getKey();
1254 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1256 Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1257 while( heapRegionsItrCallee.hasNext() ) {
1258 ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
1259 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1260 Integer idChildCallee = hrnChildCallee.getID();
1262 // only address this edge if it is not a special reflexive edge
1263 if( !edgeCallee.isInitialParamReflexive() ) {
1265 // now we know that in the callee method's ownership graph
1266 // there is a heap region->heap region reference edge given
1267 // by heap region pointers:
1268 // hrnCallee -> heapChildCallee
1270 // or by the ownership-graph independent ID's:
1271 // idCallee -> idChildCallee
1273 // make the edge with src and dst so beta info is
1274 // calculated once, then copy it for each new edge in caller
1275 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1277 edgeCallee.getFieldDesc(),
1279 toShadowTokens(ogCallee, edgeCallee.getBeta() )
1281 rewriteCallerReachability(bogusIndex,
1283 edgeNewInCallerTemplate,
1284 edgeNewInCallerTemplate.getBeta(),
1285 paramIndex2rewriteD,
1287 paramToken2paramIndex,
1288 paramTokenStar2paramIndex,
1292 edgeNewInCallerTemplate.applyBetaNew();
1295 // So now make a set of possible source heaps in the caller graph
1296 // and a set of destination heaps in the caller graph, and make
1297 // a reference edge in the caller for every possible (src,dst) pair
1298 HashSet<HeapRegionNode> possibleCallerSrcs =
1299 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1300 (HeapRegionNode) edgeCallee.getSrc(),
1301 paramIndex2reachableCallerNodes);
1303 HashSet<HeapRegionNode> possibleCallerDsts =
1304 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1305 edgeCallee.getDst(),
1306 paramIndex2reachableCallerNodes);
1309 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1310 Iterator srcItr = possibleCallerSrcs.iterator();
1311 while( srcItr.hasNext() ) {
1312 HeapRegionNode src = (HeapRegionNode) srcItr.next();
1314 if( !hasMatchingField(src, edgeCallee) ) {
1315 // prune this source node possibility
1319 Iterator dstItr = possibleCallerDsts.iterator();
1320 while( dstItr.hasNext() ) {
1321 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1323 if( !hasMatchingType(edgeCallee, dst) ) {
1328 // otherwise the caller src and dst pair can match the edge, so make it
1329 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1330 edgeNewInCaller.setSrc(src);
1331 edgeNewInCaller.setDst(dst);
1333 ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1334 if( edgeExisting == null ) {
1335 // if this edge doesn't exist in the caller, create it
1336 addReferenceEdge(src, dst, edgeNewInCaller);
1338 // if it already exists, merge with it
1339 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1348 // return value may need to be assigned in caller
1349 TempDescriptor returnTemp = fc.getReturnTemp();
1350 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
1352 LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
1353 clearReferenceEdgesFrom(lnLhsCaller, null, true);
1355 LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1356 Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1357 while( edgeCalleeItr.hasNext() ) {
1358 ReferenceEdge edgeCallee = edgeCalleeItr.next();
1360 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1362 edgeCallee.getFieldDesc(),
1364 toShadowTokens(ogCallee, edgeCallee.getBeta() )
1366 rewriteCallerReachability(bogusIndex,
1368 edgeNewInCallerTemplate,
1369 edgeNewInCallerTemplate.getBeta(),
1370 paramIndex2rewriteD,
1372 paramToken2paramIndex,
1373 paramTokenStar2paramIndex,
1377 edgeNewInCallerTemplate.applyBetaNew();
1380 HashSet<HeapRegionNode> assignCallerRhs =
1381 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1382 edgeCallee.getDst(),
1383 paramIndex2reachableCallerNodes);
1385 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1386 while( itrHrn.hasNext() ) {
1387 HeapRegionNode hrnCaller = itrHrn.next();
1389 if( !hasMatchingType(edgeCallee, hrnCaller) ) {
1394 // otherwise caller node can match callee edge, so make it
1395 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1396 edgeNewInCaller.setSrc(lnLhsCaller);
1397 edgeNewInCaller.setDst(hrnCaller);
1399 ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1400 if( edgeExisting == null ) {
1402 // if this edge doesn't exist in the caller, create it
1403 addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1405 // if it already exists, merge with it
1406 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1413 // merge the shadow nodes of allocation sites back down to normal capacity
1414 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1415 while( allocItr.hasNext() ) {
1416 AllocationSite as = allocItr.next();
1418 // first age each allocation site enough times to make room for the shadow nodes
1419 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1423 // then merge the shadow summary into the normal summary
1424 HeapRegionNode hrnSummary = getSummaryNode(as);
1425 assert hrnSummary != null;
1427 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1428 assert hrnSummaryShadow != null;
1430 mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1432 // then clear off after merge
1433 clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1434 clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1435 hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1437 // then transplant shadow nodes onto the now clean normal nodes
1438 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1440 Integer idIth = as.getIthOldest(i);
1441 HeapRegionNode hrnIth = id2hrn.get(idIth);
1443 Integer idIthShadow = as.getIthOldestShadow(i);
1444 HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1446 transferOnto(hrnIthShadow, hrnIth);
1448 // clear off shadow nodes after transfer
1449 clearReferenceEdgesFrom(hrnIthShadow, null, true);
1450 clearReferenceEdgesTo(hrnIthShadow, null, true);
1451 hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1454 // finally, globally change shadow tokens into normal tokens
1455 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1456 while( itrAllLabelNodes.hasNext() ) {
1457 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1458 LabelNode ln = (LabelNode) me.getValue();
1460 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1461 while( itrEdges.hasNext() ) {
1462 unshadowTokens(as, itrEdges.next() );
1466 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1467 while( itrAllHRNodes.hasNext() ) {
1468 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1469 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1471 unshadowTokens(as, hrnToAge);
1473 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1474 while( itrEdges.hasNext() ) {
1475 unshadowTokens(as, itrEdges.next() );
1482 protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
1484 // if no allocation site, then it's a match-everything region
1485 AllocationSite asSrc = src.getAllocationSite();
1486 if( asSrc == null ) {
1490 TypeDescriptor tdSrc = asSrc.getType();
1491 assert tdSrc != null;
1493 // if it's not a class, it doesn't have any fields to match
1494 if( !tdSrc.isClass() ) {
1498 Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
1499 while( fieldsSrcItr.hasNext() ) {
1500 FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1501 if( fd == edge.getFieldDesc() ) {
1506 // otherwise it is a class with fields
1507 // but we didn't find a match
1512 protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
1514 // if the region has no type, matches everything
1515 AllocationSite asDst = dst.getAllocationSite();
1516 if( asDst == null ) {
1520 TypeDescriptor tdDst = asDst.getType();
1521 assert tdDst != null;
1523 // if the type is not a class don't match because
1524 // primitives are copied, no memory aliases
1525 ClassDescriptor cdDst = tdDst.getClassDesc();
1526 if( cdDst == null ) {
1530 // if the field is null, it matches everything
1531 FieldDescriptor fd = edge.getFieldDesc();
1535 TypeDescriptor tdFd = fd.getType();
1536 assert tdFd != null;
1538 return typeUtil.isSuperorType(tdFd, tdDst);
1543 protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1544 edge.setBeta(edge.getBeta().unshadowTokens(as) );
1547 protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1548 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1552 private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1553 ReachabilitySet rsIn) {
1555 ReachabilitySet rsOut = new ReachabilitySet(rsIn);
1557 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1558 while( allocItr.hasNext() ) {
1559 AllocationSite as = allocItr.next();
1561 rsOut = rsOut.toShadowTokens(as);
1564 return rsOut.makeCanonical();
1568 private void rewriteCallerReachability(Integer paramIndex,
1571 ReachabilitySet rules,
1572 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1574 Hashtable<TokenTuple, Integer> paramToken2paramIndex,
1575 Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex,
1576 boolean makeChangeSet,
1577 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1578 assert (hrn == null && edge != null) ||
1579 (hrn != null && edge == null);
1581 assert rules != null;
1584 ReachabilitySet callerReachabilityCurrent;
1586 callerReachabilityCurrent = edge.getBeta();
1588 callerReachabilityCurrent = hrn.getAlpha();
1591 ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
1593 // for initializing structures in this method
1594 TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
1596 // use this to construct a change set if required; the idea is to
1597 // map every partially rewritten token tuple set to the set of
1598 // caller-context token tuple sets that were used to generate it
1599 Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
1600 new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
1601 rewritten2source.put(ttsEmpty, new HashSet<TokenTupleSet>() );
1604 Iterator<TokenTupleSet> rulesItr = rules.iterator();
1605 while(rulesItr.hasNext()) {
1606 TokenTupleSet rule = rulesItr.next();
1608 ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
1610 Iterator<TokenTuple> ruleItr = rule.iterator();
1611 while(ruleItr.hasNext()) {
1612 TokenTuple ttCallee = ruleItr.next();
1614 // compute the possibilities for rewriting this callee token
1615 ReachabilitySet ttCalleeRewrites = null;
1616 boolean callerSourceUsed = false;
1618 if( ttCallee.equals( p_i ) ) {
1619 // replace the arity-one token of the current parameter with the reachability
1620 // information from the caller edge
1621 ttCalleeRewrites = callerReachabilityCurrent;
1622 callerSourceUsed = true;
1624 } else if( paramToken2paramIndex.containsKey( ttCallee ) ||
1625 paramTokenStar2paramIndex.containsKey( ttCallee ) ) {
1627 // this token is another callee parameter, or any ARITY_MANY callee parameter,
1628 // so rewrite it with the D rules for that parameter
1629 Integer paramIndex_j;
1630 if( paramToken2paramIndex.containsKey( ttCallee ) ) {
1631 paramIndex_j = paramToken2paramIndex.get( ttCallee );
1633 paramIndex_j = paramTokenStar2paramIndex.get( ttCallee );
1636 ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
1637 assert ttCalleeRewrites != null;
1641 // otherwise there's no need for a rewrite, just pass this one on
1642 TokenTupleSet ttsCaller = new TokenTupleSet(ttCallee).makeCanonical();
1643 ttCalleeRewrites = new ReachabilitySet(ttsCaller).makeCanonical();
1646 // branch every version of the working rewritten rule with
1647 // the possibilities for rewriting the current callee token
1648 ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
1650 Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
1651 while( rewrittenRuleItr.hasNext() ) {
1652 TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
1654 Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
1655 while( ttCalleeRewritesItr.hasNext() ) {
1656 TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
1658 TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
1660 if( makeChangeSet ) {
1661 // in order to keep the list of source token tuple sets
1662 // start with the sets used to make the partially rewritten
1663 // rule up to this point
1664 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewritten );
1665 assert sourceSets != null;
1667 // make a shallow copy for possible modification
1668 sourceSets = (HashSet<TokenTupleSet>) sourceSets.clone();
1670 // if we used something from the caller to rewrite it, remember
1671 if( callerSourceUsed ) {
1672 sourceSets.add( ttsBranch );
1675 // set mapping for the further rewritten rule
1676 rewritten2source.put( ttsRewrittenNext, sourceSets );
1679 rewrittenRuleWithTTCallee =
1680 rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
1684 // now the rewritten rule's possibilities have been extended by
1685 // rewriting the current callee token, remember result
1686 rewrittenRule = rewrittenRuleWithTTCallee;
1689 // the rule has been entirely rewritten into the caller context
1690 // now, so add it to the new reachability information
1691 callerReachabilityNew =
1692 callerReachabilityNew.union( rewrittenRule );
1695 if( makeChangeSet ) {
1696 ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
1698 // each possibility for the final reachability should have a set of
1699 // caller sources mapped to it, use to create the change set
1700 Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
1701 while( callerReachabilityItr.hasNext() ) {
1702 TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
1703 HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewrittenFinal );
1704 assert sourceSets != null;
1706 Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
1707 while( sourceSetsItr.hasNext() ) {
1708 TokenTupleSet ttsSource = sourceSetsItr.next();
1711 callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
1715 assert edgePlannedChanges != null;
1716 edgePlannedChanges.put(edge, callerChangeSet);
1720 edge.setBetaNew(edge.getBetaNew().union(callerReachabilityNew) );
1722 hrn.setAlphaNew(hrn.getAlphaNew().union(callerReachabilityNew) );
1728 private HashSet<HeapRegionNode>
1729 getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1730 HeapRegionNode hrnCallee,
1731 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1734 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1736 Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
1738 if( paramIndexCallee == null ) {
1739 // this is a node allocated in the callee then and it has
1740 // exactly one shadow node in the caller to map to
1741 AllocationSite as = hrnCallee.getAllocationSite();
1744 int age = as.getAgeCategory(hrnCallee.getID() );
1745 assert age != AllocationSite.AGE_notInThisSite;
1748 if( age == AllocationSite.AGE_summary ) {
1749 idCaller = as.getSummaryShadow();
1750 } else if( age == AllocationSite.AGE_oldest ) {
1751 idCaller = as.getOldestShadow();
1753 assert age == AllocationSite.AGE_in_I;
1755 Integer I = as.getAge(hrnCallee.getID() );
1758 idCaller = as.getIthOldestShadow(I);
1761 assert id2hrn.containsKey(idCaller);
1762 HeapRegionNode hrnCaller = id2hrn.get(idCaller);
1763 possibleCallerHRNs.add(hrnCaller);
1766 // this is a node that was created to represent a parameter
1767 // so it maps to a whole mess of heap regions
1768 assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
1769 possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
1772 return possibleCallerHRNs;
1777 ////////////////////////////////////////////////////
1778 // in merge() and equals() methods the suffix A
1779 // represents the passed in graph and the suffix
1780 // B refers to the graph in this object
1781 // Merging means to take the incoming graph A and
1782 // merge it into B, so after the operation graph B
1783 // is the final result.
1784 ////////////////////////////////////////////////////
1785 public void merge(OwnershipGraph og) {
1791 mergeOwnershipNodes(og);
1792 mergeReferenceEdges(og);
1793 mergeId2paramIndex(og);
1794 mergeAllocationSites(og);
1798 protected void mergeOwnershipNodes(OwnershipGraph og) {
1799 Set sA = og.id2hrn.entrySet();
1800 Iterator iA = sA.iterator();
1801 while( iA.hasNext() ) {
1802 Map.Entry meA = (Map.Entry)iA.next();
1803 Integer idA = (Integer) meA.getKey();
1804 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1806 // if this graph doesn't have a node the
1807 // incoming graph has, allocate it
1808 if( !id2hrn.containsKey(idA) ) {
1809 HeapRegionNode hrnB = hrnA.copy();
1810 id2hrn.put(idA, hrnB);
1813 // otherwise this is a node present in both graphs
1814 // so make the new reachability set a union of the
1815 // nodes' reachability sets
1816 HeapRegionNode hrnB = id2hrn.get(idA);
1817 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1821 // now add any label nodes that are in graph B but
1823 sA = og.td2ln.entrySet();
1825 while( iA.hasNext() ) {
1826 Map.Entry meA = (Map.Entry)iA.next();
1827 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1828 LabelNode lnA = (LabelNode) meA.getValue();
1830 // if the label doesn't exist in B, allocate and add it
1831 LabelNode lnB = getLabelNodeFromTemp(tdA);
1835 protected void mergeReferenceEdges(OwnershipGraph og) {
1838 Set sA = og.id2hrn.entrySet();
1839 Iterator iA = sA.iterator();
1840 while( iA.hasNext() ) {
1841 Map.Entry meA = (Map.Entry)iA.next();
1842 Integer idA = (Integer) meA.getKey();
1843 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1845 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1846 while( heapRegionsItrA.hasNext() ) {
1847 ReferenceEdge edgeA = heapRegionsItrA.next();
1848 HeapRegionNode hrnChildA = edgeA.getDst();
1849 Integer idChildA = hrnChildA.getID();
1851 // at this point we know an edge in graph A exists
1852 // idA -> idChildA, does this exist in B?
1853 assert id2hrn.containsKey(idA);
1854 HeapRegionNode hrnB = id2hrn.get(idA);
1855 ReferenceEdge edgeToMerge = null;
1857 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1858 while( heapRegionsItrB.hasNext() &&
1859 edgeToMerge == null ) {
1861 ReferenceEdge edgeB = heapRegionsItrB.next();
1862 HeapRegionNode hrnChildB = edgeB.getDst();
1863 Integer idChildB = hrnChildB.getID();
1865 // don't use the ReferenceEdge.equals() here because
1866 // we're talking about existence between graphs
1867 if( idChildB.equals(idChildA) &&
1868 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1869 edgeToMerge = edgeB;
1873 // if the edge from A was not found in B,
1875 if( edgeToMerge == null ) {
1876 assert id2hrn.containsKey(idChildA);
1877 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1878 edgeToMerge = edgeA.copy();
1879 edgeToMerge.setSrc(hrnB);
1880 edgeToMerge.setDst(hrnChildB);
1881 addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1883 // otherwise, the edge already existed in both graphs
1884 // so merge their reachability sets
1886 // just replace this beta set with the union
1887 assert edgeToMerge != null;
1888 edgeToMerge.setBeta(
1889 edgeToMerge.getBeta().union(edgeA.getBeta() )
1891 if( !edgeA.isInitialParamReflexive() ) {
1892 edgeToMerge.setIsInitialParamReflexive(false);
1898 // and then again with label nodes
1899 sA = og.td2ln.entrySet();
1901 while( iA.hasNext() ) {
1902 Map.Entry meA = (Map.Entry)iA.next();
1903 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1904 LabelNode lnA = (LabelNode) meA.getValue();
1906 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1907 while( heapRegionsItrA.hasNext() ) {
1908 ReferenceEdge edgeA = heapRegionsItrA.next();
1909 HeapRegionNode hrnChildA = edgeA.getDst();
1910 Integer idChildA = hrnChildA.getID();
1912 // at this point we know an edge in graph A exists
1913 // tdA -> idChildA, does this exist in B?
1914 assert td2ln.containsKey(tdA);
1915 LabelNode lnB = td2ln.get(tdA);
1916 ReferenceEdge edgeToMerge = null;
1918 // labels never have edges with a field
1919 //assert edgeA.getFieldDesc() == null;
1921 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1922 while( heapRegionsItrB.hasNext() &&
1923 edgeToMerge == null ) {
1925 ReferenceEdge edgeB = heapRegionsItrB.next();
1926 HeapRegionNode hrnChildB = edgeB.getDst();
1927 Integer idChildB = hrnChildB.getID();
1929 // labels never have edges with a field
1930 //assert edgeB.getFieldDesc() == null;
1932 // don't use the ReferenceEdge.equals() here because
1933 // we're talking about existence between graphs
1934 if( idChildB.equals(idChildA) &&
1935 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1936 edgeToMerge = edgeB;
1940 // if the edge from A was not found in B,
1942 if( edgeToMerge == null ) {
1943 assert id2hrn.containsKey(idChildA);
1944 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1945 edgeToMerge = edgeA.copy();
1946 edgeToMerge.setSrc(lnB);
1947 edgeToMerge.setDst(hrnChildB);
1948 addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1950 // otherwise, the edge already existed in both graphs
1951 // so merge their reachability sets
1953 // just replace this beta set with the union
1954 edgeToMerge.setBeta(
1955 edgeToMerge.getBeta().union(edgeA.getBeta() )
1957 if( !edgeA.isInitialParamReflexive() ) {
1958 edgeToMerge.setIsInitialParamReflexive(false);
1965 // you should only merge ownership graphs that have the
1966 // same number of parameters, or if one or both parameter
1967 // index tables are empty
1968 protected void mergeId2paramIndex(OwnershipGraph og) {
1969 if( id2paramIndex.size() == 0 ) {
1970 id2paramIndex = og.id2paramIndex;
1971 paramIndex2id = og.paramIndex2id;
1972 paramIndex2tdQ = og.paramIndex2tdQ;
1976 if( og.id2paramIndex.size() == 0 ) {
1980 assert id2paramIndex.size() == og.id2paramIndex.size();
1983 protected void mergeAllocationSites(OwnershipGraph og) {
1984 allocationSites.addAll(og.allocationSites);
1989 // it is necessary in the equals() member functions
1990 // to "check both ways" when comparing the data
1991 // structures of two graphs. For instance, if all
1992 // edges between heap region nodes in graph A are
1993 // present and equal in graph B it is not sufficient
1994 // to say the graphs are equal. Consider that there
1995 // may be edges in graph B that are not in graph A.
1996 // the only way to know that all edges in both graphs
1997 // are equally present is to iterate over both data
1998 // structures and compare against the other graph.
1999 public boolean equals(OwnershipGraph og) {
2005 if( !areHeapRegionNodesEqual(og) ) {
2009 if( !areLabelNodesEqual(og) ) {
2013 if( !areReferenceEdgesEqual(og) ) {
2017 if( !areId2paramIndexEqual(og) ) {
2021 // if everything is equal up to this point,
2022 // assert that allocationSites is also equal--
2023 // this data is redundant and kept for efficiency
2024 assert allocationSites.equals(og.allocationSites);
2029 protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2031 if( !areallHRNinAalsoinBandequal(this, og) ) {
2035 if( !areallHRNinAalsoinBandequal(og, this) ) {
2042 static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2043 OwnershipGraph ogB) {
2044 Set sA = ogA.id2hrn.entrySet();
2045 Iterator iA = sA.iterator();
2046 while( iA.hasNext() ) {
2047 Map.Entry meA = (Map.Entry)iA.next();
2048 Integer idA = (Integer) meA.getKey();
2049 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2051 if( !ogB.id2hrn.containsKey(idA) ) {
2055 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2056 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2065 protected boolean areLabelNodesEqual(OwnershipGraph og) {
2067 if( !areallLNinAalsoinBandequal(this, og) ) {
2071 if( !areallLNinAalsoinBandequal(og, this) ) {
2078 static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2079 OwnershipGraph ogB) {
2080 Set sA = ogA.td2ln.entrySet();
2081 Iterator iA = sA.iterator();
2082 while( iA.hasNext() ) {
2083 Map.Entry meA = (Map.Entry)iA.next();
2084 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2086 if( !ogB.td2ln.containsKey(tdA) ) {
2095 protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2096 if( !areallREinAandBequal(this, og) ) {
2103 static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2104 OwnershipGraph ogB) {
2106 // check all the heap region->heap region edges
2107 Set sA = ogA.id2hrn.entrySet();
2108 Iterator iA = sA.iterator();
2109 while( iA.hasNext() ) {
2110 Map.Entry meA = (Map.Entry)iA.next();
2111 Integer idA = (Integer) meA.getKey();
2112 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2114 // we should have already checked that the same
2115 // heap regions exist in both graphs
2116 assert ogB.id2hrn.containsKey(idA);
2118 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2122 // then check every edge in B for presence in A, starting
2123 // from the same parent HeapRegionNode
2124 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2126 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2131 // then check all the label->heap region edges
2132 sA = ogA.td2ln.entrySet();
2134 while( iA.hasNext() ) {
2135 Map.Entry meA = (Map.Entry)iA.next();
2136 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2137 LabelNode lnA = (LabelNode) meA.getValue();
2139 // we should have already checked that the same
2140 // label nodes exist in both graphs
2141 assert ogB.td2ln.containsKey(tdA);
2143 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2147 // then check every edge in B for presence in A, starting
2148 // from the same parent LabelNode
2149 LabelNode lnB = ogB.td2ln.get(tdA);
2151 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2160 static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2162 OwnershipGraph ogB) {
2164 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2165 while( itrA.hasNext() ) {
2166 ReferenceEdge edgeA = itrA.next();
2167 HeapRegionNode hrnChildA = edgeA.getDst();
2168 Integer idChildA = hrnChildA.getID();
2170 assert ogB.id2hrn.containsKey(idChildA);
2172 // at this point we know an edge in graph A exists
2173 // onA -> idChildA, does this exact edge exist in B?
2174 boolean edgeFound = false;
2176 OwnershipNode onB = null;
2177 if( onA instanceof HeapRegionNode ) {
2178 HeapRegionNode hrnA = (HeapRegionNode) onA;
2179 onB = ogB.id2hrn.get(hrnA.getID() );
2181 LabelNode lnA = (LabelNode) onA;
2182 onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2185 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2186 while( itrB.hasNext() ) {
2187 ReferenceEdge edgeB = itrB.next();
2188 HeapRegionNode hrnChildB = edgeB.getDst();
2189 Integer idChildB = hrnChildB.getID();
2191 if( idChildA.equals(idChildB) &&
2192 edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2194 // there is an edge in the right place with the right field,
2195 // but do they have the same attributes?
2196 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2214 protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2215 return id2paramIndex.size() == og.id2paramIndex.size();
2219 public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
2221 // get parameter's heap region
2222 assert paramIndex2id.containsKey(paramIndex1);
2223 Integer idParam1 = paramIndex2id.get(paramIndex1);
2225 assert id2hrn.containsKey(idParam1);
2226 HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2227 assert hrnParam1 != null;
2229 // get tokens for this parameter
2230 TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2232 TokenTuple.ARITY_ONE).makeCanonical();
2234 TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2236 TokenTuple.ARITY_MANY).makeCanonical();
2239 // get tokens for the other parameter
2240 assert paramIndex2id.containsKey(paramIndex2);
2241 Integer idParam2 = paramIndex2id.get(paramIndex2);
2243 assert id2hrn.containsKey(idParam2);
2244 HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2245 assert hrnParam2 != null;
2247 TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2249 TokenTuple.ARITY_ONE).makeCanonical();
2251 TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2253 TokenTuple.ARITY_MANY).makeCanonical();
2256 // get special label p_q for first parameter
2257 TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2258 assert tdParamQ1 != null;
2259 LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2260 assert lnParamQ1 != null;
2262 // then get the edge from label q to parameter's hrn
2263 ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2264 assert edgeSpecialQ1 != null;
2266 // if the beta of this edge has tokens from both parameters in one
2267 // token tuple set, then there is a potential alias between them
2268 ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2269 assert beta1 != null;
2271 if( beta1.containsTupleSetWithBoth(p1, p2) ) {
2274 if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
2277 if( beta1.containsTupleSetWithBoth(p1, pStar2) ) {
2280 if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
2288 public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
2290 // get parameter's heap region
2291 assert paramIndex2id.containsKey(paramIndex);
2292 Integer idParam = paramIndex2id.get(paramIndex);
2294 assert id2hrn.containsKey(idParam);
2295 HeapRegionNode hrnParam = id2hrn.get(idParam);
2296 assert hrnParam != null;
2298 // get tokens for this parameter
2299 TokenTuple p = new TokenTuple(hrnParam.getID(),
2301 TokenTuple.ARITY_ONE).makeCanonical();
2303 TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2305 TokenTuple.ARITY_MANY).makeCanonical();
2307 // get special label p_q
2308 TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2309 assert tdParamQ != null;
2310 LabelNode lnParamQ = td2ln.get(tdParamQ);
2311 assert lnParamQ != null;
2313 // then get the edge from label q to parameter's hrn
2314 ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2315 assert edgeSpecialQ != null;
2317 // look through this beta set for potential aliases
2318 ReachabilitySet beta = edgeSpecialQ.getBeta();
2319 assert beta != null;
2322 // get tokens for summary node
2323 TokenTuple gs = new TokenTuple(as.getSummary(),
2325 TokenTuple.ARITY_ONE).makeCanonical();
2327 TokenTuple gsStar = new TokenTuple(as.getSummary(),
2329 TokenTuple.ARITY_MANY).makeCanonical();
2331 if( beta.containsTupleSetWithBoth(p, gs) ) {
2334 if( beta.containsTupleSetWithBoth(pStar, gs) ) {
2337 if( beta.containsTupleSetWithBoth(p, gsStar) ) {
2340 if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
2344 // check for other nodes
2345 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2347 // the other nodes of an allocation site are single, no stars
2348 TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2350 TokenTuple.ARITY_ONE).makeCanonical();
2352 if( beta.containsTupleSetWithBoth(p, gi) ) {
2355 if( beta.containsTupleSetWithBoth(pStar, gi) ) {
2364 public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
2366 // get tokens for summary nodes
2367 TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2369 TokenTuple.ARITY_ONE).makeCanonical();
2371 TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2373 TokenTuple.ARITY_MANY).makeCanonical();
2375 // get summary node's alpha
2376 Integer idSum1 = as1.getSummary();
2377 assert id2hrn.containsKey(idSum1);
2378 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
2379 assert hrnSum1 != null;
2380 ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2381 assert alphaSum1 != null;
2384 // and for the other one
2385 TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2387 TokenTuple.ARITY_ONE).makeCanonical();
2389 TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2391 TokenTuple.ARITY_MANY).makeCanonical();
2393 // get summary node's alpha
2394 Integer idSum2 = as2.getSummary();
2395 assert id2hrn.containsKey(idSum2);
2396 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
2397 assert hrnSum2 != null;
2398 ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2399 assert alphaSum2 != null;
2401 // does either one report reachability from the other tokens?
2402 if( alphaSum1.containsTuple(gsStar2) ) {
2405 if( alphaSum2.containsTuple(gsStar1) ) {
2409 // only check non-star token if they are different sites
2411 if( alphaSum1.containsTuple(gs2) ) {
2414 if( alphaSum2.containsTuple(gs1) ) {
2420 // check sum2 against alloc1 nodes
2421 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2422 Integer idI1 = as1.getIthOldest(i);
2423 assert id2hrn.containsKey(idI1);
2424 HeapRegionNode hrnI1 = id2hrn.get(idI1);
2425 assert hrnI1 != null;
2426 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2427 assert alphaI1 != null;
2429 // the other nodes of an allocation site are single, no stars
2430 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2432 TokenTuple.ARITY_ONE).makeCanonical();
2434 if( alphaSum2.containsTuple(gi1) ) {
2437 if( alphaI1.containsTuple(gs2) ) {
2440 if( alphaI1.containsTuple(gsStar2) ) {
2445 // check sum1 against alloc2 nodes
2446 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2447 Integer idI2 = as2.getIthOldest(i);
2448 assert id2hrn.containsKey(idI2);
2449 HeapRegionNode hrnI2 = id2hrn.get(idI2);
2450 assert hrnI2 != null;
2451 ReachabilitySet alphaI2 = hrnI2.getAlpha();
2452 assert alphaI2 != null;
2454 TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2456 TokenTuple.ARITY_ONE).makeCanonical();
2458 if( alphaSum1.containsTuple(gi2) ) {
2461 if( alphaI2.containsTuple(gs1) ) {
2464 if( alphaI2.containsTuple(gsStar1) ) {
2468 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
2469 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
2470 Integer idI1 = as1.getIthOldest(j);
2472 // if these are the same site, don't look for the same token, no alias
2473 // different tokens of the same site could alias together though
2474 if( idI1 == idI2 ) {
2478 HeapRegionNode hrnI1 = id2hrn.get(idI1);
2479 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2480 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
2482 TokenTuple.ARITY_ONE).makeCanonical();
2483 if( alphaI2.containsTuple(gi1) ) {
2486 if( alphaI1.containsTuple(gi2) ) {
2496 // for writing ownership graphs to dot files
2497 public void writeGraph(Descriptor methodDesc,
2499 boolean writeLabels,
2500 boolean labelSelect,
2501 boolean pruneGarbage,
2502 boolean writeReferencers,
2503 boolean writeParamMappings
2504 ) throws java.io.IOException {
2506 methodDesc.getSymbol() +
2507 methodDesc.getNum() +
2517 public void writeGraph(Descriptor methodDesc,
2518 boolean writeLabels,
2519 boolean labelSelect,
2520 boolean pruneGarbage,
2521 boolean writeReferencers,
2522 boolean writeParamMappings
2523 ) throws java.io.IOException {
2525 writeGraph(methodDesc+"COMPLETE",
2534 public void writeGraph(Descriptor methodDesc,
2536 boolean writeLabels,
2537 boolean labelSelect,
2538 boolean pruneGarbage,
2539 boolean writeReferencers,
2540 boolean writeParamMappings
2541 ) throws java.io.IOException {
2543 writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
2552 public void writeGraph(String graphName,
2553 boolean writeLabels,
2554 boolean labelSelect,
2555 boolean pruneGarbage,
2556 boolean writeReferencers,
2557 boolean writeParamMappings
2558 ) throws java.io.IOException {
2560 // remove all non-word characters from the graph name so
2561 // the filename and identifier in dot don't cause errors
2562 graphName = graphName.replaceAll("[\\W]", "");
2564 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2565 bw.write("digraph "+graphName+" {\n");
2567 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2569 // then visit every heap region node
2570 if( !pruneGarbage ) {
2571 Set s = id2hrn.entrySet();
2572 Iterator i = s.iterator();
2573 while( i.hasNext() ) {
2574 Map.Entry me = (Map.Entry)i.next();
2575 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2576 if( !visited.contains(hrn) ) {
2577 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2587 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
2589 if( writeParamMappings ) {
2590 Set df = paramIndex2id.entrySet();
2591 Iterator ih = df.iterator();
2592 while( ih.hasNext() ) {
2593 Map.Entry meh = (Map.Entry)ih.next();
2594 Integer pi = (Integer) meh.getKey();
2595 Integer id = (Integer) meh.getValue();
2596 bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
2600 // then visit every label node, useful for debugging
2602 Set s = td2ln.entrySet();
2603 Iterator i = s.iterator();
2604 while( i.hasNext() ) {
2605 Map.Entry me = (Map.Entry)i.next();
2606 LabelNode ln = (LabelNode) me.getValue();
2609 String labelStr = ln.getTempDescriptorString();
2610 if( labelStr.startsWith("___temp") ||
2611 labelStr.startsWith("___dst") ||
2612 labelStr.startsWith("___srctmp") ||
2613 labelStr.startsWith("___neverused") ) {
2618 //bw.write(" "+ln.toString() + ";\n");
2620 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2621 while( heapRegionsItr.hasNext() ) {
2622 ReferenceEdge edge = heapRegionsItr.next();
2623 HeapRegionNode hrn = edge.getDst();
2625 if( pruneGarbage && !visited.contains(hrn) ) {
2626 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2634 bw.write(" " + ln.toString() +
2635 " -> " + hrn.toString() +
2636 "[label=\"" + edge.toGraphEdgeString() +
2647 protected void traverseHeapRegionNodes(int mode,
2651 HashSet<HeapRegionNode> visited,
2652 boolean writeReferencers
2653 ) throws java.io.IOException {
2655 if( visited.contains(hrn) ) {
2661 case VISIT_HRN_WRITE_FULL:
2663 String attributes = "[";
2665 if( hrn.isSingleObject() ) {
2666 attributes += "shape=box";
2668 attributes += "shape=Msquare";
2671 if( hrn.isFlagged() ) {
2672 attributes += ",style=filled,fillcolor=lightgrey";
2675 attributes += ",label=\"ID" +
2678 hrn.getDescription() +
2680 hrn.getAlphaString() +
2683 bw.write(" " + hrn.toString() + attributes + ";\n");
2688 // useful for debugging
2689 if( writeReferencers ) {
2690 OwnershipNode onRef = null;
2691 Iterator refItr = hrn.iteratorToReferencers();
2692 while( refItr.hasNext() ) {
2693 onRef = (OwnershipNode) refItr.next();
2696 case VISIT_HRN_WRITE_FULL:
2697 bw.write(" " + hrn.toString() +
2698 " -> " + onRef.toString() +
2699 "[color=lightgray];\n");
2705 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2706 while( childRegionsItr.hasNext() ) {
2707 ReferenceEdge edge = childRegionsItr.next();
2708 HeapRegionNode hrnChild = edge.getDst();
2711 case VISIT_HRN_WRITE_FULL:
2712 bw.write(" " + hrn.toString() +
2713 " -> " + hrnChild.toString() +
2714 "[label=\"" + edge.toGraphEdgeString() +
2719 traverseHeapRegionNodes(mode,