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 == 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() );
1016 D_i = D_i.exhaustiveArityCombinations();
1017 paramIndex2rewriteD.put(paramIndex, D_i);
1021 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1022 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
1024 HashSet<ReferenceEdge> edgesReachable = new HashSet<ReferenceEdge>();
1025 HashSet<ReferenceEdge> edgesUpstream = new HashSet<ReferenceEdge>();
1027 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1028 while( lnArgItr.hasNext() ) {
1029 Map.Entry me = (Map.Entry)lnArgItr.next();
1030 Integer index = (Integer) me.getKey();
1031 LabelNode lnArg_i = (LabelNode) me.getValue();
1033 // rewrite alpha for the nodes reachable from argument label i
1034 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1035 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1037 // to find all reachable nodes, start with label referencees
1038 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1039 while( edgeArgItr.hasNext() ) {
1040 ReferenceEdge edge = edgeArgItr.next();
1041 todoNodes.add(edge.getDst() );
1044 // then follow links until all reachable nodes have been found
1045 while( !todoNodes.isEmpty() ) {
1046 HeapRegionNode hrn = todoNodes.iterator().next();
1047 todoNodes.remove(hrn);
1048 reachableNodes.add(hrn);
1050 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1051 while( edgeItr.hasNext() ) {
1052 ReferenceEdge edge = edgeItr.next();
1054 if( !reachableNodes.contains(edge.getDst() ) ) {
1055 todoNodes.add(edge.getDst() );
1061 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1063 // now iterate over reachable nodes to update their alpha, and
1064 // classify edges found as "argument reachable" or "upstream"
1065 Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1066 while( hrnItr.hasNext() ) {
1067 HeapRegionNode hrn = hrnItr.next();
1069 rewriteCallerNodeAlpha(fm.numParameters(),
1072 paramIndex2rewriteH,
1073 paramIndex2rewriteD,
1074 paramIndex2paramToken,
1075 paramIndex2paramTokenStar);
1077 nodesWithNewAlpha.add(hrn);
1079 // look at all incoming edges to the reachable nodes
1080 // and sort them as edges reachable from the argument
1081 // label node, or upstream edges
1082 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1083 while( edgeItr.hasNext() ) {
1084 ReferenceEdge edge = edgeItr.next();
1086 OwnershipNode on = edge.getSrc();
1088 if( on instanceof LabelNode ) {
1090 LabelNode ln0 = (LabelNode) on;
1091 if( ln0.equals(lnArg_i) ) {
1092 edgesReachable.add(edge);
1094 edgesUpstream.add(edge);
1099 HeapRegionNode hrn0 = (HeapRegionNode) on;
1100 if( reachableNodes.contains(hrn0) ) {
1101 edgesReachable.add(edge);
1103 edgesUpstream.add(edge);
1110 // update reachable edges
1111 Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1112 while( edgeReachableItr.hasNext() ) {
1113 ReferenceEdge edgeReachable = edgeReachableItr.next();
1115 rewriteCallerEdgeBeta(fm.numParameters(),
1118 paramIndex2rewriteJ,
1119 paramIndex2rewriteD,
1120 paramIndex2paramToken,
1121 paramIndex2paramTokenStar,
1125 edgesWithNewBeta.add(edgeReachable);
1129 // update upstream edges
1130 Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges
1131 = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1133 Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1134 while( edgeUpstreamItr.hasNext() ) {
1135 ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1137 rewriteCallerEdgeBeta(fm.numParameters(),
1140 paramIndex2rewriteK,
1141 paramIndex2rewriteD,
1142 paramIndex2paramToken,
1143 paramIndex2paramTokenStar,
1145 edgeUpstreamPlannedChanges);
1147 edgesWithNewBeta.add(edgeUpstream);
1150 propagateTokensOverEdges(edgesUpstream,
1151 edgeUpstreamPlannedChanges,
1156 // commit changes to alpha and beta
1157 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1158 while( nodeItr.hasNext() ) {
1159 nodeItr.next().applyAlphaNew();
1162 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1163 while( edgeItr.hasNext() ) {
1164 edgeItr.next().applyBetaNew();
1169 // verify the existence of allocation sites and their
1170 // shadows from the callee in the context of this caller graph
1171 // then map allocated nodes of callee onto the caller shadows
1173 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1174 while( asItr.hasNext() ) {
1175 AllocationSite allocSite = asItr.next();
1176 HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1178 // assert that the shadow nodes have no reference edges
1179 // because they're brand new to the graph, or last time
1180 // they were used they should have been cleared of edges
1181 HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1182 assert hrnShadowSummary.getNumReferencers() == 0;
1183 assert hrnShadowSummary.getNumReferencees() == 0;
1185 // then bring g_ij onto g'_ij and rewrite
1186 transferOnto(hrnSummary, hrnShadowSummary);
1188 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1189 hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1191 // shadow nodes only are touched by a rewrite one time,
1192 // so rewrite and immediately commit--and they don't belong
1193 // to a particular parameter, so use a bogus param index
1194 // that pulls a self-rewrite out of H
1195 rewriteCallerNodeAlpha(fm.numParameters(),
1198 paramIndex2rewriteH,
1199 paramIndex2rewriteD,
1200 paramIndex2paramToken,
1201 paramIndex2paramTokenStar);
1203 hrnShadowSummary.applyAlphaNew();
1206 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1207 Integer idIth = allocSite.getIthOldest(i);
1208 assert id2hrn.containsKey(idIth);
1209 HeapRegionNode hrnIth = id2hrn.get(idIth);
1211 Integer idShadowIth = -(allocSite.getIthOldest(i));
1212 assert id2hrn.containsKey(idShadowIth);
1213 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1214 assert hrnIthShadow.getNumReferencers() == 0;
1215 assert hrnIthShadow.getNumReferencees() == 0;
1217 transferOnto(hrnIth, hrnIthShadow);
1219 assert ogCallee.id2hrn.containsKey(idIth);
1220 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1221 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1223 rewriteCallerNodeAlpha(fm.numParameters(),
1226 paramIndex2rewriteH,
1227 paramIndex2rewriteD,
1228 paramIndex2paramToken,
1229 paramIndex2paramTokenStar);
1231 hrnIthShadow.applyAlphaNew();
1236 // for every heap region->heap region edge in the
1237 // callee graph, create the matching edge or edges
1238 // in the caller graph
1239 Set sCallee = ogCallee.id2hrn.entrySet();
1240 Iterator iCallee = sCallee.iterator();
1241 while( iCallee.hasNext() ) {
1242 Map.Entry meCallee = (Map.Entry)iCallee.next();
1243 Integer idCallee = (Integer) meCallee.getKey();
1244 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1246 Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1247 while( heapRegionsItrCallee.hasNext() ) {
1248 ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
1249 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1250 Integer idChildCallee = hrnChildCallee.getID();
1252 // only address this edge if it is not a special reflexive edge
1253 if( !edgeCallee.isInitialParamReflexive() ) {
1255 // now we know that in the callee method's ownership graph
1256 // there is a heap region->heap region reference edge given
1257 // by heap region pointers:
1258 // hrnCallee -> heapChildCallee
1260 // or by the ownership-graph independent ID's:
1261 // idCallee -> idChildCallee
1263 // make the edge with src and dst so beta info is
1264 // calculated once, then copy it for each new edge in caller
1265 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1267 edgeCallee.getFieldDesc(),
1269 toShadowTokens(ogCallee, edgeCallee.getBeta() )
1271 rewriteCallerEdgeBeta(fm.numParameters(),
1273 edgeNewInCallerTemplate,
1274 paramIndex2rewriteJ,
1275 paramIndex2rewriteD,
1276 paramIndex2paramToken,
1277 paramIndex2paramTokenStar,
1281 edgeNewInCallerTemplate.applyBetaNew();
1284 // So now make a set of possible source heaps in the caller graph
1285 // and a set of destination heaps in the caller graph, and make
1286 // a reference edge in the caller for every possible (src,dst) pair
1287 HashSet<HeapRegionNode> possibleCallerSrcs =
1288 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1289 (HeapRegionNode) edgeCallee.getSrc(),
1290 paramIndex2reachableCallerNodes);
1292 HashSet<HeapRegionNode> possibleCallerDsts =
1293 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1294 edgeCallee.getDst(),
1295 paramIndex2reachableCallerNodes);
1298 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1299 Iterator srcItr = possibleCallerSrcs.iterator();
1300 while( srcItr.hasNext() ) {
1301 HeapRegionNode src = (HeapRegionNode) srcItr.next();
1303 if( !hasMatchingField( src, edgeCallee ) ) {
1304 // prune this source node possibility
1308 Iterator dstItr = possibleCallerDsts.iterator();
1309 while( dstItr.hasNext() ) {
1310 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1312 if( !hasMatchingType( edgeCallee, dst ) ) {
1317 // otherwise the caller src and dst pair can match the edge, so make it
1318 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1319 edgeNewInCaller.setSrc(src);
1320 edgeNewInCaller.setDst(dst);
1322 ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1323 if( edgeExisting == null ) {
1324 // if this edge doesn't exist in the caller, create it
1325 addReferenceEdge(src, dst, edgeNewInCaller);
1327 // if it already exists, merge with it
1328 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1338 // return value may need to be assigned in caller
1339 if( fc.getReturnTemp() != null ) {
1341 LabelNode lnLhsCaller = getLabelNodeFromTemp(fc.getReturnTemp() );
1342 clearReferenceEdgesFrom(lnLhsCaller, null, true);
1344 LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1345 Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1346 while( edgeCalleeItr.hasNext() ) {
1347 ReferenceEdge edgeCallee = edgeCalleeItr.next();
1349 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1351 edgeCallee.getFieldDesc(),
1353 toShadowTokens(ogCallee, edgeCallee.getBeta() )
1355 rewriteCallerEdgeBeta(fm.numParameters(),
1357 edgeNewInCallerTemplate,
1358 paramIndex2rewriteJ,
1359 paramIndex2rewriteD,
1360 paramIndex2paramToken,
1361 paramIndex2paramTokenStar,
1365 edgeNewInCallerTemplate.applyBetaNew();
1368 HashSet<HeapRegionNode> assignCallerRhs =
1369 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1370 edgeCallee.getDst(),
1371 paramIndex2reachableCallerNodes);
1373 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1374 while( itrHrn.hasNext() ) {
1375 HeapRegionNode hrnCaller = itrHrn.next();
1377 if( !hasMatchingType( edgeCallee, hrnCaller ) ) {
1382 // otherwise caller node can match callee edge, so make it
1383 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1384 edgeNewInCaller.setSrc(lnLhsCaller);
1385 edgeNewInCaller.setDst(hrnCaller);
1387 ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1388 if( edgeExisting == null ) {
1390 // if this edge doesn't exist in the caller, create it
1391 addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1393 // if it already exists, merge with it
1394 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1402 // merge the shadow nodes of allocation sites back down to normal capacity
1403 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1404 while( allocItr.hasNext() ) {
1405 AllocationSite as = allocItr.next();
1407 // first age each allocation site enough times to make room for the shadow nodes
1408 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1412 // then merge the shadow summary into the normal summary
1413 HeapRegionNode hrnSummary = getSummaryNode(as);
1414 assert hrnSummary != null;
1416 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1417 assert hrnSummaryShadow != null;
1419 mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1421 // then clear off after merge
1422 clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1423 clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1424 hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1426 // then transplant shadow nodes onto the now clean normal nodes
1427 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1429 Integer idIth = as.getIthOldest(i);
1430 HeapRegionNode hrnIth = id2hrn.get(idIth);
1432 Integer idIthShadow = as.getIthOldestShadow(i);
1433 HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1435 transferOnto(hrnIthShadow, hrnIth);
1437 // clear off shadow nodes after transfer
1438 clearReferenceEdgesFrom(hrnIthShadow, null, true);
1439 clearReferenceEdgesTo(hrnIthShadow, null, true);
1440 hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1443 // finally, globally change shadow tokens into normal tokens
1444 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1445 while( itrAllLabelNodes.hasNext() ) {
1446 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1447 LabelNode ln = (LabelNode) me.getValue();
1449 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1450 while( itrEdges.hasNext() ) {
1451 unshadowTokens(as, itrEdges.next() );
1455 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1456 while( itrAllHRNodes.hasNext() ) {
1457 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1458 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1460 unshadowTokens(as, hrnToAge);
1462 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1463 while( itrEdges.hasNext() ) {
1464 unshadowTokens(as, itrEdges.next() );
1471 protected boolean hasMatchingField( HeapRegionNode src, ReferenceEdge edge ) {
1473 // if no allocation site, then it's a match-everything region
1474 AllocationSite asSrc = src.getAllocationSite();
1475 if( asSrc == null ) { return true; }
1477 TypeDescriptor tdSrc = asSrc.getType();
1478 assert tdSrc != null;
1480 // if it's not a class, it doesn't have any fields to match
1481 if( !tdSrc.isClass() ) { return false; }
1483 Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
1484 while( fieldsSrcItr.hasNext() ) {
1485 FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1486 if( fd == edge.getFieldDesc() ) {
1491 // otherwise it is a class with fields
1492 // but we didn't find a match
1497 protected boolean hasMatchingType( ReferenceEdge edge, HeapRegionNode dst ) {
1499 // if the region has no type, matches everything
1500 AllocationSite asDst = dst.getAllocationSite();
1501 if( asDst == null ) { return true; }
1503 TypeDescriptor tdDst = asDst.getType();
1504 assert tdDst != null;
1506 // if the type is not a class don't match because
1507 // primitives are copied, no memory aliases
1508 ClassDescriptor cdDst = tdDst.getClassDesc();
1509 if( cdDst == null ) { return false; }
1511 // if the field is null, it matches everything
1512 FieldDescriptor fd = edge.getFieldDesc();
1513 if( fd == null ) { return true; }
1514 TypeDescriptor tdFd = fd.getType();
1515 assert tdFd != null;
1517 return typeUtil.isSuperorType( tdFd, tdDst );
1522 protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1523 edge.setBeta(edge.getBeta().unshadowTokens(as) );
1526 protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1527 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1531 private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1532 ReachabilitySet rsIn) {
1534 ReachabilitySet rsOut = new ReachabilitySet(rsIn);
1536 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1537 while( allocItr.hasNext() ) {
1538 AllocationSite as = allocItr.next();
1540 rsOut = rsOut.toShadowTokens(as);
1543 return rsOut.makeCanonical();
1547 private void rewriteCallerNodeAlpha(int numParameters,
1550 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
1551 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1552 Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1553 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1555 ReachabilitySet rules = paramIndex2rewriteH.get(paramIndex);
1556 assert rules != null;
1558 TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1559 assert tokenToRewrite != null;
1561 ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
1562 Iterator<TokenTupleSet> ttsItr = rules.iterator();
1563 while( ttsItr.hasNext() ) {
1564 TokenTupleSet tts = ttsItr.next();
1565 r0 = r0.union(tts.rewriteToken(tokenToRewrite,
1571 ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1572 ttsItr = r0.iterator();
1573 while( ttsItr.hasNext() ) {
1574 TokenTupleSet tts = ttsItr.next();
1575 r1 = r1.union(rewriteDpass(numParameters,
1578 paramIndex2rewriteD,
1579 paramIndex2paramToken,
1580 paramIndex2paramTokenStar) );
1583 hrn.setAlphaNew(hrn.getAlphaNew().union(r1) );
1587 private void rewriteCallerEdgeBeta(int numParameters,
1590 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJorK,
1591 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1592 Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1593 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar,
1594 boolean makeChangeSet,
1595 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1597 ReachabilitySet rules = paramIndex2rewriteJorK.get(paramIndex);
1598 assert rules != null;
1600 TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1601 assert tokenToRewrite != null;
1603 ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
1605 Iterator<TokenTupleSet> ttsItr = rules.iterator();
1606 while( ttsItr.hasNext() ) {
1607 TokenTupleSet tts = ttsItr.next();
1609 Hashtable<TokenTupleSet, TokenTupleSet> forChangeSet =
1610 new Hashtable<TokenTupleSet, TokenTupleSet>();
1612 ReachabilitySet rTemp = tts.rewriteToken(tokenToRewrite,
1617 Iterator fcsItr = forChangeSet.entrySet().iterator();
1618 while( fcsItr.hasNext() ) {
1619 Map.Entry me = (Map.Entry)fcsItr.next();
1620 TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey();
1621 TokenTupleSet ttsAdd = (TokenTupleSet) me.getValue();
1623 ChangeTuple ct = new ChangeTuple(ttsMatch,
1627 cts0 = cts0.union(ct);
1632 ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1633 ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical();
1635 Iterator<ChangeTuple> ctItr = cts0.iterator();
1636 while( ctItr.hasNext() ) {
1637 ChangeTuple ct = ctItr.next();
1639 ReachabilitySet rTemp = rewriteDpass(numParameters,
1642 paramIndex2rewriteD,
1643 paramIndex2paramToken,
1644 paramIndex2paramTokenStar
1646 r1 = r1.union(rTemp);
1648 if( makeChangeSet ) {
1649 assert edgePlannedChanges != null;
1651 Iterator<TokenTupleSet> ttsTempItr = rTemp.iterator();
1652 while( ttsTempItr.hasNext() ) {
1653 TokenTupleSet tts = ttsTempItr.next();
1655 ChangeTuple ctFinal = new ChangeTuple(ct.getSetToMatch(),
1659 cts1 = cts1.union(ctFinal);
1664 if( makeChangeSet ) {
1665 edgePlannedChanges.put(edge, cts1);
1668 edge.setBetaNew(edge.getBetaNew().union(r1) );
1672 private ReachabilitySet rewriteDpass(int numParameters,
1674 TokenTupleSet ttsIn,
1675 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1676 Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1677 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1679 ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
1681 boolean rewritten = false;
1683 for( int j = 0; j < numParameters; ++j ) {
1684 Integer paramIndexJ = new Integer(j);
1685 ReachabilitySet D_j = paramIndex2rewriteD.get(paramIndexJ);
1688 if( paramIndexJ != paramIndex ) {
1689 TokenTuple tokenToRewriteJ = paramIndex2paramToken.get(paramIndexJ);
1690 assert tokenToRewriteJ != null;
1691 if( ttsIn.containsTuple(tokenToRewriteJ) ) {
1692 ReachabilitySet r = ttsIn.rewriteToken(tokenToRewriteJ,
1696 Iterator<TokenTupleSet> ttsItr = r.iterator();
1697 while( ttsItr.hasNext() ) {
1698 TokenTupleSet tts = ttsItr.next();
1699 rsOut = rsOut.union(rewriteDpass(numParameters,
1702 paramIndex2rewriteD,
1703 paramIndex2paramToken,
1704 paramIndex2paramTokenStar) );
1710 TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get(paramIndexJ);
1711 assert tokenStarToRewriteJ != null;
1712 if( ttsIn.containsTuple(tokenStarToRewriteJ) ) {
1713 ReachabilitySet r = ttsIn.rewriteToken(tokenStarToRewriteJ,
1717 Iterator<TokenTupleSet> ttsItr = r.iterator();
1718 while( ttsItr.hasNext() ) {
1719 TokenTupleSet tts = ttsItr.next();
1720 rsOut = rsOut.union(rewriteDpass(numParameters,
1723 paramIndex2rewriteD,
1724 paramIndex2paramToken,
1725 paramIndex2paramTokenStar) );
1732 rsOut = rsOut.union(ttsIn);
1739 private HashSet<HeapRegionNode>
1740 getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1741 HeapRegionNode hrnCallee,
1742 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1745 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1747 Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
1749 if( paramIndexCallee == null ) {
1750 // this is a node allocated in the callee then and it has
1751 // exactly one shadow node in the caller to map to
1752 AllocationSite as = hrnCallee.getAllocationSite();
1755 int age = as.getAgeCategory(hrnCallee.getID() );
1756 assert age != AllocationSite.AGE_notInThisSite;
1759 if( age == AllocationSite.AGE_summary ) {
1760 idCaller = as.getSummaryShadow();
1761 } else if( age == AllocationSite.AGE_oldest ) {
1762 idCaller = as.getOldestShadow();
1764 assert age == AllocationSite.AGE_in_I;
1766 Integer I = as.getAge(hrnCallee.getID() );
1769 idCaller = as.getIthOldestShadow(I);
1772 assert id2hrn.containsKey(idCaller);
1773 HeapRegionNode hrnCaller = id2hrn.get(idCaller);
1774 possibleCallerHRNs.add(hrnCaller);
1777 // this is a node that was created to represent a parameter
1778 // so it maps to a whole mess of heap regions
1779 assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
1780 possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
1783 return possibleCallerHRNs;
1788 ////////////////////////////////////////////////////
1789 // in merge() and equals() methods the suffix A
1790 // represents the passed in graph and the suffix
1791 // B refers to the graph in this object
1792 // Merging means to take the incoming graph A and
1793 // merge it into B, so after the operation graph B
1794 // is the final result.
1795 ////////////////////////////////////////////////////
1796 public void merge(OwnershipGraph og) {
1802 mergeOwnershipNodes(og);
1803 mergeReferenceEdges(og);
1804 mergeId2paramIndex(og);
1805 mergeAllocationSites(og);
1809 protected void mergeOwnershipNodes(OwnershipGraph og) {
1810 Set sA = og.id2hrn.entrySet();
1811 Iterator iA = sA.iterator();
1812 while( iA.hasNext() ) {
1813 Map.Entry meA = (Map.Entry)iA.next();
1814 Integer idA = (Integer) meA.getKey();
1815 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1817 // if this graph doesn't have a node the
1818 // incoming graph has, allocate it
1819 if( !id2hrn.containsKey(idA) ) {
1820 HeapRegionNode hrnB = hrnA.copy();
1821 id2hrn.put(idA, hrnB);
1824 // otherwise this is a node present in both graphs
1825 // so make the new reachability set a union of the
1826 // nodes' reachability sets
1827 HeapRegionNode hrnB = id2hrn.get(idA);
1828 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1832 // now add any label nodes that are in graph B but
1834 sA = og.td2ln.entrySet();
1836 while( iA.hasNext() ) {
1837 Map.Entry meA = (Map.Entry)iA.next();
1838 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1839 LabelNode lnA = (LabelNode) meA.getValue();
1841 // if the label doesn't exist in B, allocate and add it
1842 LabelNode lnB = getLabelNodeFromTemp(tdA);
1846 protected void mergeReferenceEdges(OwnershipGraph og) {
1849 Set sA = og.id2hrn.entrySet();
1850 Iterator iA = sA.iterator();
1851 while( iA.hasNext() ) {
1852 Map.Entry meA = (Map.Entry)iA.next();
1853 Integer idA = (Integer) meA.getKey();
1854 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1856 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1857 while( heapRegionsItrA.hasNext() ) {
1858 ReferenceEdge edgeA = heapRegionsItrA.next();
1859 HeapRegionNode hrnChildA = edgeA.getDst();
1860 Integer idChildA = hrnChildA.getID();
1862 // at this point we know an edge in graph A exists
1863 // idA -> idChildA, does this exist in B?
1864 assert id2hrn.containsKey(idA);
1865 HeapRegionNode hrnB = id2hrn.get(idA);
1866 ReferenceEdge edgeToMerge = null;
1868 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1869 while( heapRegionsItrB.hasNext() &&
1870 edgeToMerge == null ) {
1872 ReferenceEdge edgeB = heapRegionsItrB.next();
1873 HeapRegionNode hrnChildB = edgeB.getDst();
1874 Integer idChildB = hrnChildB.getID();
1876 // don't use the ReferenceEdge.equals() here because
1877 // we're talking about existence between graphs
1878 if( idChildB.equals(idChildA) &&
1879 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1880 edgeToMerge = edgeB;
1884 // if the edge from A was not found in B,
1886 if( edgeToMerge == null ) {
1887 assert id2hrn.containsKey(idChildA);
1888 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1889 edgeToMerge = edgeA.copy();
1890 edgeToMerge.setSrc(hrnB);
1891 edgeToMerge.setDst(hrnChildB);
1892 addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1894 // otherwise, the edge already existed in both graphs
1895 // so merge their reachability sets
1897 // just replace this beta set with the union
1898 assert edgeToMerge != null;
1899 edgeToMerge.setBeta(
1900 edgeToMerge.getBeta().union(edgeA.getBeta() )
1902 if( !edgeA.isInitialParamReflexive() ) {
1903 edgeToMerge.setIsInitialParamReflexive(false);
1909 // and then again with label nodes
1910 sA = og.td2ln.entrySet();
1912 while( iA.hasNext() ) {
1913 Map.Entry meA = (Map.Entry)iA.next();
1914 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1915 LabelNode lnA = (LabelNode) meA.getValue();
1917 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1918 while( heapRegionsItrA.hasNext() ) {
1919 ReferenceEdge edgeA = heapRegionsItrA.next();
1920 HeapRegionNode hrnChildA = edgeA.getDst();
1921 Integer idChildA = hrnChildA.getID();
1923 // at this point we know an edge in graph A exists
1924 // tdA -> idChildA, does this exist in B?
1925 assert td2ln.containsKey(tdA);
1926 LabelNode lnB = td2ln.get(tdA);
1927 ReferenceEdge edgeToMerge = null;
1929 // labels never have edges with a field
1930 //assert edgeA.getFieldDesc() == null;
1932 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1933 while( heapRegionsItrB.hasNext() &&
1934 edgeToMerge == null ) {
1936 ReferenceEdge edgeB = heapRegionsItrB.next();
1937 HeapRegionNode hrnChildB = edgeB.getDst();
1938 Integer idChildB = hrnChildB.getID();
1940 // labels never have edges with a field
1941 //assert edgeB.getFieldDesc() == null;
1943 // don't use the ReferenceEdge.equals() here because
1944 // we're talking about existence between graphs
1945 if( idChildB.equals(idChildA) &&
1946 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1947 edgeToMerge = edgeB;
1951 // if the edge from A was not found in B,
1953 if( edgeToMerge == null ) {
1954 assert id2hrn.containsKey(idChildA);
1955 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1956 edgeToMerge = edgeA.copy();
1957 edgeToMerge.setSrc(lnB);
1958 edgeToMerge.setDst(hrnChildB);
1959 addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1961 // otherwise, the edge already existed in both graphs
1962 // so merge their reachability sets
1964 // just replace this beta set with the union
1965 edgeToMerge.setBeta(
1966 edgeToMerge.getBeta().union(edgeA.getBeta() )
1968 if( !edgeA.isInitialParamReflexive() ) {
1969 edgeToMerge.setIsInitialParamReflexive(false);
1976 // you should only merge ownership graphs that have the
1977 // same number of parameters, or if one or both parameter
1978 // index tables are empty
1979 protected void mergeId2paramIndex(OwnershipGraph og) {
1980 if( id2paramIndex.size() == 0 ) {
1981 id2paramIndex = og.id2paramIndex;
1982 paramIndex2id = og.paramIndex2id;
1983 paramIndex2tdQ = og.paramIndex2tdQ;
1987 if( og.id2paramIndex.size() == 0 ) {
1991 assert id2paramIndex.size() == og.id2paramIndex.size();
1994 protected void mergeAllocationSites(OwnershipGraph og) {
1995 allocationSites.addAll(og.allocationSites);
2000 // it is necessary in the equals() member functions
2001 // to "check both ways" when comparing the data
2002 // structures of two graphs. For instance, if all
2003 // edges between heap region nodes in graph A are
2004 // present and equal in graph B it is not sufficient
2005 // to say the graphs are equal. Consider that there
2006 // may be edges in graph B that are not in graph A.
2007 // the only way to know that all edges in both graphs
2008 // are equally present is to iterate over both data
2009 // structures and compare against the other graph.
2010 public boolean equals(OwnershipGraph og) {
2016 if( !areHeapRegionNodesEqual(og) ) {
2020 if( !areLabelNodesEqual(og) ) {
2024 if( !areReferenceEdgesEqual(og) ) {
2028 if( !areId2paramIndexEqual(og) ) {
2032 // if everything is equal up to this point,
2033 // assert that allocationSites is also equal--
2034 // this data is redundant and kept for efficiency
2035 assert allocationSites.equals(og.allocationSites);
2040 protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2042 if( !areallHRNinAalsoinBandequal(this, og) ) {
2046 if( !areallHRNinAalsoinBandequal(og, this) ) {
2053 static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2054 OwnershipGraph ogB) {
2055 Set sA = ogA.id2hrn.entrySet();
2056 Iterator iA = sA.iterator();
2057 while( iA.hasNext() ) {
2058 Map.Entry meA = (Map.Entry)iA.next();
2059 Integer idA = (Integer) meA.getKey();
2060 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2062 if( !ogB.id2hrn.containsKey(idA) ) {
2066 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2067 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2076 protected boolean areLabelNodesEqual(OwnershipGraph og) {
2078 if( !areallLNinAalsoinBandequal(this, og) ) {
2082 if( !areallLNinAalsoinBandequal(og, this) ) {
2089 static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2090 OwnershipGraph ogB) {
2091 Set sA = ogA.td2ln.entrySet();
2092 Iterator iA = sA.iterator();
2093 while( iA.hasNext() ) {
2094 Map.Entry meA = (Map.Entry)iA.next();
2095 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2097 if( !ogB.td2ln.containsKey(tdA) ) {
2106 protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2107 if( !areallREinAandBequal(this, og) ) {
2114 static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2115 OwnershipGraph ogB) {
2117 // check all the heap region->heap region edges
2118 Set sA = ogA.id2hrn.entrySet();
2119 Iterator iA = sA.iterator();
2120 while( iA.hasNext() ) {
2121 Map.Entry meA = (Map.Entry)iA.next();
2122 Integer idA = (Integer) meA.getKey();
2123 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2125 // we should have already checked that the same
2126 // heap regions exist in both graphs
2127 assert ogB.id2hrn.containsKey(idA);
2129 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2133 // then check every edge in B for presence in A, starting
2134 // from the same parent HeapRegionNode
2135 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2137 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2142 // then check all the label->heap region edges
2143 sA = ogA.td2ln.entrySet();
2145 while( iA.hasNext() ) {
2146 Map.Entry meA = (Map.Entry)iA.next();
2147 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2148 LabelNode lnA = (LabelNode) meA.getValue();
2150 // we should have already checked that the same
2151 // label nodes exist in both graphs
2152 assert ogB.td2ln.containsKey(tdA);
2154 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2158 // then check every edge in B for presence in A, starting
2159 // from the same parent LabelNode
2160 LabelNode lnB = ogB.td2ln.get(tdA);
2162 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2171 static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2173 OwnershipGraph ogB) {
2175 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2176 while( itrA.hasNext() ) {
2177 ReferenceEdge edgeA = itrA.next();
2178 HeapRegionNode hrnChildA = edgeA.getDst();
2179 Integer idChildA = hrnChildA.getID();
2181 assert ogB.id2hrn.containsKey(idChildA);
2183 // at this point we know an edge in graph A exists
2184 // onA -> idChildA, does this exact edge exist in B?
2185 boolean edgeFound = false;
2187 OwnershipNode onB = null;
2188 if( onA instanceof HeapRegionNode ) {
2189 HeapRegionNode hrnA = (HeapRegionNode) onA;
2190 onB = ogB.id2hrn.get(hrnA.getID() );
2192 LabelNode lnA = (LabelNode) onA;
2193 onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2196 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2197 while( itrB.hasNext() ) {
2198 ReferenceEdge edgeB = itrB.next();
2199 HeapRegionNode hrnChildB = edgeB.getDst();
2200 Integer idChildB = hrnChildB.getID();
2202 if( idChildA.equals(idChildB) &&
2203 edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2205 // there is an edge in the right place with the right field,
2206 // but do they have the same attributes?
2207 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2225 protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2226 return id2paramIndex.size() == og.id2paramIndex.size();
2230 public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
2232 // get parameter's heap region
2233 assert paramIndex2id.containsKey(paramIndex1);
2234 Integer idParam1 = paramIndex2id.get(paramIndex1);
2236 assert id2hrn.containsKey(idParam1);
2237 HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2238 assert hrnParam1 != null;
2240 // get tokens for this parameter
2241 TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2243 TokenTuple.ARITY_ONE).makeCanonical();
2245 TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2247 TokenTuple.ARITY_MANY).makeCanonical();
2250 // get tokens for the other parameter
2251 assert paramIndex2id.containsKey(paramIndex2);
2252 Integer idParam2 = paramIndex2id.get(paramIndex2);
2254 assert id2hrn.containsKey(idParam2);
2255 HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2256 assert hrnParam2 != null;
2258 TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2260 TokenTuple.ARITY_ONE).makeCanonical();
2262 TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2264 TokenTuple.ARITY_MANY).makeCanonical();
2267 // get special label p_q for first parameter
2268 TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2269 assert tdParamQ1 != null;
2270 LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2271 assert lnParamQ1 != null;
2273 // then get the edge from label q to parameter's hrn
2274 ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2275 assert edgeSpecialQ1 != null;
2277 // if the beta of this edge has tokens from both parameters in one
2278 // token tuple set, then there is a potential alias between them
2279 ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2280 assert beta1 != null;
2282 if( beta1.containsTupleSetWithBoth(p1, p2) ) {
2285 if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
2288 if( beta1.containsTupleSetWithBoth(p1, pStar2) ) {
2291 if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
2299 public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
2301 // get parameter's heap region
2302 assert paramIndex2id.containsKey(paramIndex);
2303 Integer idParam = paramIndex2id.get(paramIndex);
2305 assert id2hrn.containsKey(idParam);
2306 HeapRegionNode hrnParam = id2hrn.get(idParam);
2307 assert hrnParam != null;
2309 // get tokens for this parameter
2310 TokenTuple p = new TokenTuple(hrnParam.getID(),
2312 TokenTuple.ARITY_ONE).makeCanonical();
2314 TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2316 TokenTuple.ARITY_MANY).makeCanonical();
2318 // get special label p_q
2319 TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2320 assert tdParamQ != null;
2321 LabelNode lnParamQ = td2ln.get(tdParamQ);
2322 assert lnParamQ != null;
2324 // then get the edge from label q to parameter's hrn
2325 ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2326 assert edgeSpecialQ != null;
2328 // look through this beta set for potential aliases
2329 ReachabilitySet beta = edgeSpecialQ.getBeta();
2330 assert beta != null;
2333 // get tokens for summary node
2334 TokenTuple gs = new TokenTuple(as.getSummary(),
2336 TokenTuple.ARITY_ONE).makeCanonical();
2338 TokenTuple gsStar = new TokenTuple(as.getSummary(),
2340 TokenTuple.ARITY_MANY).makeCanonical();
2342 if( beta.containsTupleSetWithBoth(p, gs) ) {
2345 if( beta.containsTupleSetWithBoth(pStar, gs) ) {
2348 if( beta.containsTupleSetWithBoth(p, gsStar) ) {
2351 if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
2355 // check for other nodes
2356 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2358 // the other nodes of an allocation site are single, no stars
2359 TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2361 TokenTuple.ARITY_ONE).makeCanonical();
2363 if( beta.containsTupleSetWithBoth(p, gi) ) {
2366 if( beta.containsTupleSetWithBoth(pStar, gi) ) {
2375 public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
2377 // get tokens for summary nodes
2378 TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2380 TokenTuple.ARITY_ONE).makeCanonical();
2382 TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2384 TokenTuple.ARITY_MANY).makeCanonical();
2386 // get summary node's alpha
2387 Integer idSum1 = as1.getSummary();
2388 assert id2hrn.containsKey(idSum1);
2389 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
2390 assert hrnSum1 != null;
2391 ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2392 assert alphaSum1 != null;
2395 // and for the other one
2396 TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2398 TokenTuple.ARITY_ONE).makeCanonical();
2400 TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2402 TokenTuple.ARITY_MANY).makeCanonical();
2404 // get summary node's alpha
2405 Integer idSum2 = as2.getSummary();
2406 assert id2hrn.containsKey(idSum2);
2407 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
2408 assert hrnSum2 != null;
2409 ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2410 assert alphaSum2 != null;
2412 // does either one report reachability from the other tokens?
2413 if( alphaSum1.containsTuple(gsStar2) ) {
2416 if( alphaSum2.containsTuple(gsStar1) ) {
2420 // only check non-star token if they are different sites
2422 if( alphaSum1.containsTuple(gs2) ) {
2425 if( alphaSum2.containsTuple(gs1) ) {
2431 // check sum2 against alloc1 nodes
2432 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2433 Integer idI1 = as1.getIthOldest(i);
2434 assert id2hrn.containsKey(idI1);
2435 HeapRegionNode hrnI1 = id2hrn.get(idI1);
2436 assert hrnI1 != null;
2437 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2438 assert alphaI1 != null;
2440 // the other nodes of an allocation site are single, no stars
2441 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2443 TokenTuple.ARITY_ONE).makeCanonical();
2445 if( alphaSum2.containsTuple(gi1) ) {
2448 if( alphaI1.containsTuple(gs2) ) {
2451 if( alphaI1.containsTuple(gsStar2) ) {
2456 // check sum1 against alloc2 nodes
2457 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2458 Integer idI2 = as2.getIthOldest(i);
2459 assert id2hrn.containsKey(idI2);
2460 HeapRegionNode hrnI2 = id2hrn.get(idI2);
2461 assert hrnI2 != null;
2462 ReachabilitySet alphaI2 = hrnI2.getAlpha();
2463 assert alphaI2 != null;
2465 TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2467 TokenTuple.ARITY_ONE).makeCanonical();
2469 if( alphaSum1.containsTuple(gi2) ) {
2472 if( alphaI2.containsTuple(gs1) ) {
2475 if( alphaI2.containsTuple(gsStar1) ) {
2479 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
2480 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
2481 Integer idI1 = as1.getIthOldest(j);
2483 // if these are the same site, don't look for the same token, no alias
2484 // different tokens of the same site could alias together though
2485 if( idI1 == idI2 ) {
2489 HeapRegionNode hrnI1 = id2hrn.get(idI1);
2490 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2491 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
2493 TokenTuple.ARITY_ONE).makeCanonical();
2494 if( alphaI2.containsTuple(gi1) ) {
2497 if( alphaI1.containsTuple(gi2) ) {
2507 // for writing ownership graphs to dot files
2508 public void writeGraph(Descriptor methodDesc,
2510 boolean writeLabels,
2511 boolean labelSelect,
2512 boolean pruneGarbage,
2513 boolean writeReferencers
2514 ) throws java.io.IOException {
2516 methodDesc.getSymbol() +
2517 methodDesc.getNum() +
2526 public void writeGraph(Descriptor methodDesc,
2527 boolean writeLabels,
2528 boolean labelSelect,
2529 boolean pruneGarbage,
2530 boolean writeReferencers
2531 ) throws java.io.IOException {
2533 writeGraph(methodDesc+"COMPLETE",
2541 public void writeGraph(Descriptor methodDesc,
2543 boolean writeLabels,
2544 boolean labelSelect,
2545 boolean pruneGarbage,
2546 boolean writeReferencers
2547 ) throws java.io.IOException {
2549 writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
2557 public void writeGraph(String graphName,
2558 boolean writeLabels,
2559 boolean labelSelect,
2560 boolean pruneGarbage,
2561 boolean writeReferencers
2562 ) throws java.io.IOException {
2564 // remove all non-word characters from the graph name so
2565 // the filename and identifier in dot don't cause errors
2566 graphName = graphName.replaceAll("[\\W]", "");
2568 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2569 bw.write("digraph "+graphName+" {\n");
2570 //bw.write( " size=\"7.5,10\";\n" );
2572 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2574 // then visit every heap region node
2575 if( !pruneGarbage ) {
2576 Set s = id2hrn.entrySet();
2577 Iterator i = s.iterator();
2578 while( i.hasNext() ) {
2579 Map.Entry me = (Map.Entry)i.next();
2580 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2581 if( !visited.contains(hrn) ) {
2582 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2592 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
2594 Set df = paramIndex2id.entrySet();
2595 Iterator ih = df.iterator();
2596 while( ih.hasNext() ) {
2597 Map.Entry meh = (Map.Entry)ih.next();
2598 Integer pi = (Integer) meh.getKey();
2599 Integer id = (Integer) meh.getValue();
2600 bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
2603 // then visit every label node, useful for debugging
2605 Set s = td2ln.entrySet();
2606 Iterator i = s.iterator();
2607 while( i.hasNext() ) {
2608 Map.Entry me = (Map.Entry)i.next();
2609 LabelNode ln = (LabelNode) me.getValue();
2612 String labelStr = ln.getTempDescriptorString();
2613 if( labelStr.startsWith("___temp") ||
2614 labelStr.startsWith("___dst") ||
2615 labelStr.startsWith("___srctmp") ||
2616 labelStr.startsWith("___neverused") ) {
2621 bw.write(ln.toString() + ";\n");
2623 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2624 while( heapRegionsItr.hasNext() ) {
2625 ReferenceEdge edge = heapRegionsItr.next();
2626 HeapRegionNode hrn = edge.getDst();
2628 if( pruneGarbage && !visited.contains(hrn) ) {
2629 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2637 bw.write(" " + ln.toString() +
2638 " -> " + hrn.toString() +
2639 "[label=\"" + edge.toGraphEdgeString() +
2650 protected void traverseHeapRegionNodes(int mode,
2654 HashSet<HeapRegionNode> visited,
2655 boolean writeReferencers
2656 ) throws java.io.IOException {
2658 if( visited.contains(hrn) ) {
2664 case VISIT_HRN_WRITE_FULL:
2666 String attributes = "[";
2668 if( hrn.isSingleObject() ) {
2669 attributes += "shape=box";
2671 attributes += "shape=Msquare";
2674 if( hrn.isFlagged() ) {
2675 attributes += ",style=filled,fillcolor=lightgrey";
2678 attributes += ",label=\"ID" +
2681 hrn.getDescription() +
2683 hrn.getAlphaString() +
2686 bw.write(" " + hrn.toString() + attributes + ";\n");
2691 // useful for debugging
2692 if( writeReferencers ) {
2693 OwnershipNode onRef = null;
2694 Iterator refItr = hrn.iteratorToReferencers();
2695 while( refItr.hasNext() ) {
2696 onRef = (OwnershipNode) refItr.next();
2699 case VISIT_HRN_WRITE_FULL:
2700 bw.write(" " + hrn.toString() +
2701 " -> " + onRef.toString() +
2702 "[color=lightgray];\n");
2708 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2709 while( childRegionsItr.hasNext() ) {
2710 ReferenceEdge edge = childRegionsItr.next();
2711 HeapRegionNode hrnChild = edge.getDst();
2714 case VISIT_HRN_WRITE_FULL:
2715 bw.write(" " + hrn.toString() +
2716 " -> " + hrnChild.toString() +
2717 "[label=\"" + edge.toGraphEdgeString() +
2722 traverseHeapRegionNodes(mode,