1 package Analysis.OwnershipAnalysis;
8 public class OwnershipGraph {
10 private int allocationDepth;
12 // there was already one other very similar reason
13 // for traversing heap nodes that is no longer needed
14 // instead of writing a new heap region visitor, use
15 // the existing method with a new mode to describe what
16 // actions to take during the traversal
17 protected static final int VISIT_HRN_WRITE_FULL = 0;
19 protected static TempDescriptor tdReturn = new TempDescriptor("_Return___");
22 public Hashtable<Integer, HeapRegionNode> id2hrn;
23 public Hashtable<TempDescriptor, LabelNode > td2ln;
24 public Hashtable<Integer, Integer > id2paramIndex;
25 public Hashtable<Integer, Integer > paramIndex2id;
26 public Hashtable<Integer, TempDescriptor> paramIndex2tdQ;
28 public HashSet<AllocationSite> allocationSites;
33 public OwnershipGraph(int allocationDepth) {
34 this.allocationDepth = allocationDepth;
36 id2hrn = new Hashtable<Integer, HeapRegionNode>();
37 td2ln = new Hashtable<TempDescriptor, LabelNode >();
38 id2paramIndex = new Hashtable<Integer, Integer >();
39 paramIndex2id = new Hashtable<Integer, Integer >();
40 paramIndex2tdQ = new Hashtable<Integer, TempDescriptor>();
42 allocationSites = new HashSet <AllocationSite>();
46 // label nodes are much easier to deal with than
47 // heap region nodes. Whenever there is a request
48 // for the label node that is associated with a
49 // temp descriptor we can either find it or make a
50 // new one and return it. This is because temp
51 // descriptors are globally unique and every label
52 // node is mapped to exactly one temp descriptor.
53 protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
56 if( !td2ln.containsKey(td) ) {
57 td2ln.put(td, new LabelNode(td) );
64 // the reason for this method is to have the option
65 // creating new heap regions with specific IDs, or
66 // duplicating heap regions with specific IDs (especially
67 // in the merge() operation) or to create new heap
68 // regions with a new unique ID.
69 protected HeapRegionNode
70 createNewHeapRegionNode(Integer id,
71 boolean isSingleObject,
75 AllocationSite allocSite,
76 ReachabilitySet alpha,
80 id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
84 if( isFlagged || isParameter ) {
85 alpha = new ReachabilitySet(new TokenTuple(id,
90 alpha = new ReachabilitySet(new TokenTupleSet()
95 HeapRegionNode hrn = new HeapRegionNode(id,
108 ////////////////////////////////////////////////
110 // Low-level referencee and referencer methods
112 // These methods provide the lowest level for
113 // creating references between ownership nodes
114 // and handling the details of maintaining both
115 // list of referencers and referencees.
117 ////////////////////////////////////////////////
118 protected void addReferenceEdge(OwnershipNode referencer,
119 HeapRegionNode referencee,
120 ReferenceEdge edge) {
121 assert referencer != null;
122 assert referencee != null;
124 assert edge.getSrc() == referencer;
125 assert edge.getDst() == referencee;
127 referencer.addReferencee(edge);
128 referencee.addReferencer(edge);
131 protected void removeReferenceEdge(OwnershipNode referencer,
132 HeapRegionNode referencee,
133 FieldDescriptor fieldDesc) {
134 assert referencer != null;
135 assert referencee != null;
137 ReferenceEdge edge = referencer.getReferenceTo(referencee,
140 assert edge == referencee.getReferenceFrom(referencer,
143 referencer.removeReferencee(edge);
144 referencee.removeReferencer(edge);
147 protected void clearReferenceEdgesFrom(OwnershipNode referencer,
148 FieldDescriptor fieldDesc,
150 assert referencer != null;
152 // get a copy of the set to iterate over, otherwise
153 // we will be trying to take apart the set as we
154 // are iterating over it, which won't work
155 Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
156 while( i.hasNext() ) {
157 ReferenceEdge edge = i.next();
159 if( removeAll || edge.getFieldDesc() == fieldDesc ) {
160 HeapRegionNode referencee = edge.getDst();
162 removeReferenceEdge(referencer,
164 edge.getFieldDesc() );
169 protected void clearReferenceEdgesTo(HeapRegionNode referencee,
170 FieldDescriptor fieldDesc,
172 assert referencee != null;
174 // get a copy of the set to iterate over, otherwise
175 // we will be trying to take apart the set as we
176 // are iterating over it, which won't work
177 Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
178 while( i.hasNext() ) {
179 ReferenceEdge edge = i.next();
181 if( removeAll || edge.getFieldDesc() == fieldDesc ) {
182 OwnershipNode referencer = edge.getSrc();
183 removeReferenceEdge(referencer,
185 edge.getFieldDesc() );
191 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
193 HashSet<HeapRegionNode> nodesWithNewAlpha,
194 HashSet<ReferenceEdge> edgesWithNewBeta) {
196 HashSet<HeapRegionNode> todoNodes
197 = new HashSet<HeapRegionNode>();
198 todoNodes.add(nPrime);
200 HashSet<ReferenceEdge> todoEdges
201 = new HashSet<ReferenceEdge>();
203 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
204 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
205 nodePlannedChanges.put(nPrime, c0);
207 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
208 = new Hashtable<ReferenceEdge, ChangeTupleSet>();
211 while( !todoNodes.isEmpty() ) {
212 HeapRegionNode n = todoNodes.iterator().next();
213 ChangeTupleSet C = nodePlannedChanges.get(n);
215 Iterator itrC = C.iterator();
216 while( itrC.hasNext() ) {
217 ChangeTuple c = (ChangeTuple) itrC.next();
219 if( n.getAlpha().contains(c.getSetToMatch() ) ) {
220 ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
221 n.setAlphaNew(n.getAlphaNew().union(withChange) );
222 nodesWithNewAlpha.add(n);
226 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
227 while( referItr.hasNext() ) {
228 ReferenceEdge edge = referItr.next();
231 if( !edgePlannedChanges.containsKey(edge) ) {
232 edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
235 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
238 Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
239 while( refeeItr.hasNext() ) {
240 ReferenceEdge edgeF = refeeItr.next();
241 HeapRegionNode m = edgeF.getDst();
243 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
245 Iterator<ChangeTuple> itrCprime = C.iterator();
246 while( itrCprime.hasNext() ) {
247 ChangeTuple c = itrCprime.next();
248 if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
249 changesToPass = changesToPass.union(c);
253 if( !changesToPass.isEmpty() ) {
254 if( !nodePlannedChanges.containsKey(m) ) {
255 nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
258 ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
260 if( !changesToPass.isSubset(currentChanges) ) {
262 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
271 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
275 protected void propagateTokensOverEdges(
276 HashSet<ReferenceEdge> todoEdges,
277 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
278 HashSet<ReferenceEdge> edgesWithNewBeta) {
281 while( !todoEdges.isEmpty() ) {
282 ReferenceEdge edgeE = todoEdges.iterator().next();
283 todoEdges.remove(edgeE);
285 if( !edgePlannedChanges.containsKey(edgeE) ) {
286 edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
289 ChangeTupleSet C = edgePlannedChanges.get(edgeE);
291 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
293 Iterator<ChangeTuple> itrC = C.iterator();
294 while( itrC.hasNext() ) {
295 ChangeTuple c = itrC.next();
296 if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
297 ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
298 edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
299 edgesWithNewBeta.add(edgeE);
300 changesToPass = changesToPass.union(c);
304 OwnershipNode onSrc = edgeE.getSrc();
306 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
307 HeapRegionNode n = (HeapRegionNode) onSrc;
309 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
310 while( referItr.hasNext() ) {
311 ReferenceEdge edgeF = referItr.next();
313 if( !edgePlannedChanges.containsKey(edgeF) ) {
314 edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
317 ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
319 if( !changesToPass.isSubset(currentChanges) ) {
320 todoEdges.add(edgeF);
321 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
329 ////////////////////////////////////////////////////
331 // Assignment Operation Methods
333 // These methods are high-level operations for
334 // modeling program assignment statements using
335 // the low-level reference create/remove methods
338 // The destination in an assignment statement is
339 // going to have new references. The method of
340 // determining the references depends on the type
341 // of the FlatNode assignment and the predicates
342 // of the nodes and edges involved.
344 ////////////////////////////////////////////////////
345 public void assignTempXEqualToTempY(TempDescriptor x,
348 LabelNode lnX = getLabelNodeFromTemp(x);
349 LabelNode lnY = getLabelNodeFromTemp(y);
351 clearReferenceEdgesFrom(lnX, null, true);
353 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
354 while( itrYhrn.hasNext() ) {
355 ReferenceEdge edgeY = itrYhrn.next();
356 HeapRegionNode referencee = edgeY.getDst();
357 ReferenceEdge edgeNew = edgeY.copy();
360 addReferenceEdge(lnX, referencee, edgeNew);
365 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
368 LabelNode lnX = getLabelNodeFromTemp(x);
369 LabelNode lnY = getLabelNodeFromTemp(y);
371 clearReferenceEdgesFrom(lnX, null, true);
373 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
374 while( itrYhrn.hasNext() ) {
375 ReferenceEdge edgeY = itrYhrn.next();
376 HeapRegionNode hrnY = edgeY.getDst();
377 ReachabilitySet betaY = edgeY.getBeta();
379 Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
380 while( itrHrnFhrn.hasNext() ) {
381 ReferenceEdge edgeHrn = itrHrnFhrn.next();
382 HeapRegionNode hrnHrn = edgeHrn.getDst();
383 ReachabilitySet betaHrn = edgeHrn.getBeta();
385 if( edgeHrn.getFieldDesc() == null ||
386 edgeHrn.getFieldDesc() == f ) {
388 ReferenceEdge edgeNew = new ReferenceEdge(lnX,
392 betaY.intersection(betaHrn) );
394 addReferenceEdge(lnX, hrnHrn, edgeNew);
401 public void assignTempXFieldFEqualToTempY(TempDescriptor x,
404 LabelNode lnX = getLabelNodeFromTemp(x);
405 LabelNode lnY = getLabelNodeFromTemp(y);
407 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
408 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
410 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
411 while( itrXhrn.hasNext() ) {
412 ReferenceEdge edgeX = itrXhrn.next();
413 HeapRegionNode hrnX = edgeX.getDst();
414 ReachabilitySet betaX = edgeX.getBeta();
416 ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
418 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
419 while( itrYhrn.hasNext() ) {
420 ReferenceEdge edgeY = itrYhrn.next();
421 HeapRegionNode hrnY = edgeY.getDst();
422 ReachabilitySet O = edgeY.getBeta();
425 // propagate tokens over nodes starting from hrnSrc, and it will
426 // take care of propagating back up edges from any touched nodes
427 ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
428 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
431 // then propagate back just up the edges from hrn
432 ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
434 HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
436 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
437 new Hashtable<ReferenceEdge, ChangeTupleSet>();
439 Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
440 while( referItr.hasNext() ) {
441 ReferenceEdge edgeUpstream = referItr.next();
442 todoEdges.add(edgeUpstream);
443 edgePlannedChanges.put(edgeUpstream, Cx);
446 propagateTokensOverEdges(todoEdges,
452 //System.out.println( edgeY.getBetaNew() + "\nbeing pruned by\n" + hrnX.getAlpha() );
454 // create the actual reference edge hrnX.f -> hrnY
455 ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
459 edgeY.getBetaNew().pruneBy(hrnX.getAlpha() )
460 //edgeY.getBeta().pruneBy( hrnX.getAlpha() )
462 addReferenceEdge(hrnX, hrnY, edgeNew);
466 // we can do a strong update here if one of two cases holds
467 // SAVE FOR LATER, WITHOUT STILL CORRECT
468 if( (hrnX.getNumReferencers() == 1) ||
469 ( lnX.getNumReferencees() == 1 && hrnX.isSingleObject() )
471 clearReferenceEdgesFrom( hrnX, f, false );
474 addReferenceEdge( hrnX, hrnY, edgeNew );
477 // if the field is null, or "any" field, then
478 // look to see if an any field already exists
479 // and merge with it, otherwise just add the edge
480 ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
482 if( edgeExisting != null ) {
483 edgeExisting.setBetaNew(
484 edgeExisting.getBetaNew().union( edgeNew.getBeta() )
486 // a new edge here cannot be reflexive, so existing will
487 // always be also not reflexive anymore
488 edgeExisting.setIsInitialParamReflexive( false );
491 addReferenceEdge( hrnX, hrnY, edgeNew );
498 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
499 while( nodeItr.hasNext() ) {
500 nodeItr.next().applyAlphaNew();
503 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
504 while( edgeItr.hasNext() ) {
505 edgeItr.next().applyBetaNew();
510 public void assignTempEqualToParamAlloc(TempDescriptor td,
512 Integer paramIndex) {
515 LabelNode lnParam = getLabelNodeFromTemp(td);
516 HeapRegionNode hrn = createNewHeapRegionNode(null,
523 "param" + paramIndex);
525 // this is a non-program-accessible label that picks up beta
526 // info to be used for fixing a caller of this method
527 TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
528 LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
530 // keep track of heap regions that were created for
531 // parameter labels, the index of the parameter they
532 // are for is important when resolving method calls
533 Integer newID = hrn.getID();
534 assert !id2paramIndex.containsKey(newID);
535 assert !id2paramIndex.containsValue(paramIndex);
536 id2paramIndex.put(newID, paramIndex);
537 paramIndex2id.put(paramIndex, newID);
538 paramIndex2tdQ.put(paramIndex, tdParamQ);
540 ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
542 TokenTuple.ARITY_ONE) );
544 // heap regions for parameters are always multiple object (see above)
545 // and have a reference to themselves, because we can't know the
546 // structure of memory that is passed into the method. We're assuming
549 ReferenceEdge edgeFromLabel =
550 new ReferenceEdge(lnParam, hrn, null, false, beta);
552 ReferenceEdge edgeFromLabelQ =
553 new ReferenceEdge(lnParamQ, hrn, null, false, beta);
555 ReferenceEdge edgeReflexive =
556 new ReferenceEdge(hrn, hrn, null, true, beta);
558 addReferenceEdge(lnParam, hrn, edgeFromLabel);
559 addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
560 addReferenceEdge(hrn, hrn, edgeReflexive);
564 public void assignReturnEqualToTemp(TempDescriptor x) {
566 LabelNode lnR = getLabelNodeFromTemp(tdReturn);
567 LabelNode lnX = getLabelNodeFromTemp(x);
569 clearReferenceEdgesFrom(lnR, null, true);
571 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
572 while( itrXhrn.hasNext() ) {
573 ReferenceEdge edgeX = itrXhrn.next();
574 HeapRegionNode referencee = edgeX.getDst();
575 ReferenceEdge edgeNew = edgeX.copy();
578 addReferenceEdge(lnR, referencee, edgeNew);
583 public void assignTempEqualToNewAlloc(TempDescriptor x,
590 // after the age operation the newest (or zero-ith oldest)
591 // node associated with the allocation site should have
592 // no references to it as if it were a newly allocated
593 // heap region, so make a reference to it to complete
596 Integer idNewest = as.getIthOldest(0);
597 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
598 assert hrnNewest != null;
600 LabelNode lnX = getLabelNodeFromTemp(x);
601 clearReferenceEdgesFrom(lnX, null, true);
603 ReferenceEdge edgeNew =
604 new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
606 addReferenceEdge(lnX, hrnNewest, edgeNew);
610 // use the allocation site (unique to entire analysis) to
611 // locate the heap region nodes in this ownership graph
612 // that should be aged. The process models the allocation
613 // of new objects and collects all the oldest allocations
614 // in a summary node to allow for a finite analysis
616 // There is an additional property of this method. After
617 // running it on a particular ownership graph (many graphs
618 // may have heap regions related to the same allocation site)
619 // the heap region node objects in this ownership graph will be
620 // allocated. Therefore, after aging a graph for an allocation
621 // site, attempts to retrieve the heap region nodes using the
622 // integer id's contained in the allocation site should always
623 // return non-null heap regions.
624 public void age(AllocationSite as) {
626 // aging adds this allocation site to the graph's
627 // list of sites that exist in the graph, or does
628 // nothing if the site is already in the list
629 allocationSites.add(as);
631 // get the summary node for the allocation site in the context
632 // of this particular ownership graph
633 HeapRegionNode hrnSummary = getSummaryNode(as);
635 // merge oldest node into summary
636 Integer idK = as.getOldest();
637 HeapRegionNode hrnK = id2hrn.get(idK);
638 mergeIntoSummary(hrnK, hrnSummary);
640 // move down the line of heap region nodes
641 // clobbering the ith and transferring all references
642 // to and from i-1 to node i. Note that this clobbers
643 // the oldest node (hrnK) that was just merged into
645 for( int i = allocationDepth - 1; i > 0; --i ) {
647 // move references from the i-1 oldest to the ith oldest
648 Integer idIth = as.getIthOldest(i);
649 HeapRegionNode hrnI = id2hrn.get(idIth);
650 Integer idImin1th = as.getIthOldest(i - 1);
651 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
653 transferOnto(hrnImin1, hrnI);
656 // as stated above, the newest node should have had its
657 // references moved over to the second oldest, so we wipe newest
658 // in preparation for being the new object to assign something to
659 Integer id0th = as.getIthOldest(0);
660 HeapRegionNode hrn0 = id2hrn.get(id0th);
663 // clear all references in and out of newest node
664 clearReferenceEdgesFrom(hrn0, null, true);
665 clearReferenceEdgesTo(hrn0, null, true);
668 // now tokens in reachability sets need to "age" also
669 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
670 while( itrAllLabelNodes.hasNext() ) {
671 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
672 LabelNode ln = (LabelNode) me.getValue();
674 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
675 while( itrEdges.hasNext() ) {
676 ageTokens(as, itrEdges.next() );
680 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
681 while( itrAllHRNodes.hasNext() ) {
682 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
683 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
685 ageTokens(as, hrnToAge);
687 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
688 while( itrEdges.hasNext() ) {
689 ageTokens(as, itrEdges.next() );
694 // after tokens have been aged, reset newest node's reachability
695 if( hrn0.isFlagged() ) {
696 hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet(
702 hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet()
709 protected HeapRegionNode getSummaryNode(AllocationSite as) {
711 Integer idSummary = as.getSummary();
712 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
714 // If this is null then we haven't touched this allocation site
715 // in the context of the current ownership graph, so allocate
716 // heap region nodes appropriate for the entire allocation site.
717 // This should only happen once per ownership graph per allocation site,
718 // and a particular integer id can be used to locate the heap region
719 // in different ownership graphs that represents the same part of an
721 if( hrnSummary == null ) {
723 boolean hasFlags = false;
724 if( as.getType().isClass() ) {
725 hasFlags = as.getType().getClassDesc().hasFlags();
728 hrnSummary = createNewHeapRegionNode(idSummary,
735 as + "\\n" + as.getType() + "\\nsummary");
737 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
738 Integer idIth = as.getIthOldest(i);
739 assert !id2hrn.containsKey(idIth);
740 createNewHeapRegionNode(idIth,
747 as + "\\n" + as.getType() + "\\n" + i + " oldest");
755 protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
757 Integer idShadowSummary = as.getSummaryShadow();
758 HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
760 if( hrnShadowSummary == null ) {
762 boolean hasFlags = false;
763 if( as.getType().isClass() ) {
764 hasFlags = as.getType().getClassDesc().hasFlags();
767 hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
774 as + "\\n" + as.getType() + "\\nshadowSum");
776 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
777 Integer idShadowIth = as.getIthOldestShadow(i);
778 assert !id2hrn.containsKey(idShadowIth);
779 createNewHeapRegionNode(idShadowIth,
786 as + "\\n" + as.getType() + "\\n" + i + " shadow");
790 return hrnShadowSummary;
794 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
795 assert hrnSummary.isNewSummary();
797 // transfer references _from_ hrn over to hrnSummary
798 Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
799 while( itrReferencee.hasNext() ) {
800 ReferenceEdge edge = itrReferencee.next();
801 ReferenceEdge edgeMerged = edge.copy();
802 edgeMerged.setSrc(hrnSummary);
804 HeapRegionNode hrnReferencee = edge.getDst();
805 ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
807 if( edgeSummary == null ) {
808 // the merge is trivial, nothing to be done
810 // otherwise an edge from the referencer to hrnSummary exists already
811 // and the edge referencer->hrn should be merged with it
812 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
815 addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
818 // next transfer references _to_ hrn over to hrnSummary
819 Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
820 while( itrReferencer.hasNext() ) {
821 ReferenceEdge edge = itrReferencer.next();
822 ReferenceEdge edgeMerged = edge.copy();
823 edgeMerged.setDst(hrnSummary);
825 OwnershipNode onReferencer = edge.getSrc();
826 ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
828 if( edgeSummary == null ) {
829 // the merge is trivial, nothing to be done
831 // otherwise an edge from the referencer to alpha_S exists already
832 // and the edge referencer->alpha_K should be merged with it
833 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
836 addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
839 // then merge hrn reachability into hrnSummary
840 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
844 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
846 // clear references in and out of node i
847 clearReferenceEdgesFrom(hrnB, null, true);
848 clearReferenceEdgesTo(hrnB, null, true);
850 // copy each edge in and out of A to B
851 Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
852 while( itrReferencee.hasNext() ) {
853 ReferenceEdge edge = itrReferencee.next();
854 HeapRegionNode hrnReferencee = edge.getDst();
855 ReferenceEdge edgeNew = edge.copy();
856 edgeNew.setSrc(hrnB);
858 addReferenceEdge(hrnB, hrnReferencee, edgeNew);
861 Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
862 while( itrReferencer.hasNext() ) {
863 ReferenceEdge edge = itrReferencer.next();
864 OwnershipNode onReferencer = edge.getSrc();
865 ReferenceEdge edgeNew = edge.copy();
866 edgeNew.setDst(hrnB);
868 addReferenceEdge(onReferencer, hrnB, edgeNew);
871 // replace hrnB reachability with hrnA's
872 hrnB.setAlpha(hrnA.getAlpha() );
876 protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
877 edge.setBeta(edge.getBeta().ageTokens(as) );
880 protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
881 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
885 public void resolveMethodCall(FlatCall fc,
888 OwnershipGraph ogCallee) {
891 // define rewrite rules and other structures to organize
892 // data by parameter/argument index
893 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
894 new Hashtable<Integer, ReachabilitySet>();
896 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
897 new Hashtable<Integer, ReachabilitySet>();
899 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
900 new Hashtable<Integer, ReachabilitySet>();
902 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
903 new Hashtable<Integer, ReachabilitySet>();
905 // helpful structures
906 Hashtable<TokenTuple, Integer> paramToken2paramIndex =
907 new Hashtable<TokenTuple, Integer>();
909 Hashtable<Integer, TokenTuple> paramIndex2paramToken =
910 new Hashtable<Integer, TokenTuple>();
912 Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
913 new Hashtable<TokenTuple, Integer>();
915 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
916 new Hashtable<Integer, TokenTuple>();
918 Hashtable<Integer, LabelNode> paramIndex2ln =
919 new Hashtable<Integer, LabelNode>();
921 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
922 new Hashtable<Integer, HashSet<HeapRegionNode> >();
925 // add a bogus entry with the identity rule for easy rewrite
926 // of new callee nodes and edges, doesn't belong to any parameter
927 Integer bogusID = new Integer(-1);
928 Integer bogusIndex = new Integer(-1);
929 TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE);
930 TokenTuple bogusTokenStar = new TokenTuple(bogusID, true, TokenTuple.ARITY_MANY);
931 ReachabilitySet rsIdentity =
932 new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical();
934 paramIndex2rewriteH.put(bogusIndex, rsIdentity);
935 paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
936 paramToken2paramIndex.put(bogusToken, bogusIndex);
937 paramIndex2paramToken.put(bogusIndex, bogusToken);
938 paramTokenStar2paramIndex.put(bogusTokenStar, bogusIndex);
939 paramIndex2paramTokenStar.put(bogusIndex, bogusTokenStar);
942 for( int i = 0; i < fm.numParameters(); ++i ) {
943 Integer paramIndex = new Integer(i);
945 assert ogCallee.paramIndex2id.containsKey(paramIndex);
946 Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
948 assert ogCallee.id2hrn.containsKey(idParam);
949 HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
950 assert hrnParam != null;
951 paramIndex2rewriteH.put(paramIndex,
953 toShadowTokens(ogCallee, hrnParam.getAlpha() )
956 ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
957 assert edgeReflexive_i != null;
958 paramIndex2rewriteJ.put(paramIndex,
959 toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
962 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
963 assert tdParamQ != null;
964 LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
965 assert lnParamQ != null;
966 ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
967 assert edgeSpecialQ_i != null;
968 paramIndex2rewriteK.put(paramIndex,
969 toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
972 TokenTuple p_i = new TokenTuple(hrnParam.getID(),
974 TokenTuple.ARITY_ONE).makeCanonical();
975 paramToken2paramIndex.put(p_i, paramIndex);
976 paramIndex2paramToken.put(paramIndex, p_i);
978 TokenTuple p_i_star = new TokenTuple(hrnParam.getID(),
980 TokenTuple.ARITY_MANY).makeCanonical();
981 paramTokenStar2paramIndex.put(p_i_star, paramIndex);
982 paramIndex2paramTokenStar.put(paramIndex, p_i_star);
984 // now depending on whether the callee is static or not
985 // we need to account for a "this" argument in order to
986 // find the matching argument in the caller context
987 TempDescriptor argTemp_i;
989 argTemp_i = fc.getArg(paramIndex);
991 if( paramIndex == 0 ) {
992 argTemp_i = fc.getThis();
994 argTemp_i = fc.getArg(paramIndex - 1);
998 // in non-static methods there is a "this" pointer
999 // that should be taken into account
1001 assert fc.numArgs() == fm.numParameters();
1003 assert fc.numArgs() + 1 == fm.numParameters();
1006 LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1007 paramIndex2ln.put(paramIndex, argLabel_i);
1009 ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
1010 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1011 while( edgeItr.hasNext() ) {
1012 ReferenceEdge edge = edgeItr.next();
1013 D_i = D_i.union(edge.getBeta() );
1015 D_i = D_i.exhaustiveArityCombinations();
1016 paramIndex2rewriteD.put(paramIndex, D_i);
1020 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1021 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
1023 HashSet<ReferenceEdge> edgesReachable = new HashSet<ReferenceEdge>();
1024 HashSet<ReferenceEdge> edgesUpstream = new HashSet<ReferenceEdge>();
1026 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1027 while( lnArgItr.hasNext() ) {
1028 Map.Entry me = (Map.Entry)lnArgItr.next();
1029 Integer index = (Integer) me.getKey();
1030 LabelNode lnArg_i = (LabelNode) me.getValue();
1032 // rewrite alpha for the nodes reachable from argument label i
1033 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1034 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1036 // to find all reachable nodes, start with label referencees
1037 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1038 while( edgeArgItr.hasNext() ) {
1039 ReferenceEdge edge = edgeArgItr.next();
1040 todoNodes.add(edge.getDst() );
1043 // then follow links until all reachable nodes have been found
1044 while( !todoNodes.isEmpty() ) {
1045 HeapRegionNode hrn = todoNodes.iterator().next();
1046 todoNodes.remove(hrn);
1047 reachableNodes.add(hrn);
1049 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1050 while( edgeItr.hasNext() ) {
1051 ReferenceEdge edge = edgeItr.next();
1053 if( !reachableNodes.contains(edge.getDst() ) ) {
1054 todoNodes.add(edge.getDst() );
1060 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1062 // now iterate over reachable nodes to update their alpha, and
1063 // classify edges found as "argument reachable" or "upstream"
1064 Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1065 while( hrnItr.hasNext() ) {
1066 HeapRegionNode hrn = hrnItr.next();
1068 rewriteCallerNodeAlpha(fm.numParameters(),
1071 paramIndex2rewriteH,
1072 paramIndex2rewriteD,
1073 paramIndex2paramToken,
1074 paramIndex2paramTokenStar);
1076 nodesWithNewAlpha.add(hrn);
1078 // look at all incoming edges to the reachable nodes
1079 // and sort them as edges reachable from the argument
1080 // label node, or upstream edges
1081 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1082 while( edgeItr.hasNext() ) {
1083 ReferenceEdge edge = edgeItr.next();
1085 OwnershipNode on = edge.getSrc();
1087 if( on instanceof LabelNode ) {
1089 LabelNode ln0 = (LabelNode) on;
1090 if( ln0.equals(lnArg_i) ) {
1091 edgesReachable.add(edge);
1093 edgesUpstream.add(edge);
1098 HeapRegionNode hrn0 = (HeapRegionNode) on;
1099 if( reachableNodes.contains(hrn0) ) {
1100 edgesReachable.add(edge);
1102 edgesUpstream.add(edge);
1109 // update reachable edges
1110 Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1111 while( edgeReachableItr.hasNext() ) {
1112 ReferenceEdge edgeReachable = edgeReachableItr.next();
1114 rewriteCallerEdgeBeta(fm.numParameters(),
1117 paramIndex2rewriteJ,
1118 paramIndex2rewriteD,
1119 paramIndex2paramToken,
1120 paramIndex2paramTokenStar,
1124 edgesWithNewBeta.add(edgeReachable);
1128 // update upstream edges
1129 Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges
1130 = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1132 Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1133 while( edgeUpstreamItr.hasNext() ) {
1134 ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1136 rewriteCallerEdgeBeta(fm.numParameters(),
1139 paramIndex2rewriteK,
1140 paramIndex2rewriteD,
1141 paramIndex2paramToken,
1142 paramIndex2paramTokenStar,
1144 edgeUpstreamPlannedChanges);
1146 edgesWithNewBeta.add(edgeUpstream);
1149 propagateTokensOverEdges(edgesUpstream,
1150 edgeUpstreamPlannedChanges,
1155 // commit changes to alpha and beta
1156 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1157 while( nodeItr.hasNext() ) {
1158 nodeItr.next().applyAlphaNew();
1161 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1162 while( edgeItr.hasNext() ) {
1163 edgeItr.next().applyBetaNew();
1168 // verify the existence of allocation sites and their
1169 // shadows from the callee in the context of this caller graph
1170 // then map allocated nodes of callee onto the caller shadows
1172 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1173 while( asItr.hasNext() ) {
1174 AllocationSite allocSite = asItr.next();
1175 HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1177 // assert that the shadow nodes have no reference edges
1178 // because they're brand new to the graph, or last time
1179 // they were used they should have been cleared of edges
1180 HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1181 assert hrnShadowSummary.getNumReferencers() == 0;
1182 assert hrnShadowSummary.getNumReferencees() == 0;
1184 // then bring g_ij onto g'_ij and rewrite
1185 transferOnto(hrnSummary, hrnShadowSummary);
1187 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1188 hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1190 // shadow nodes only are touched by a rewrite one time,
1191 // so rewrite and immediately commit--and they don't belong
1192 // to a particular parameter, so use a bogus param index
1193 // that pulls a self-rewrite out of H
1194 rewriteCallerNodeAlpha(fm.numParameters(),
1197 paramIndex2rewriteH,
1198 paramIndex2rewriteD,
1199 paramIndex2paramToken,
1200 paramIndex2paramTokenStar);
1202 hrnShadowSummary.applyAlphaNew();
1205 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1206 Integer idIth = allocSite.getIthOldest(i);
1207 assert id2hrn.containsKey(idIth);
1208 HeapRegionNode hrnIth = id2hrn.get(idIth);
1210 Integer idShadowIth = -(allocSite.getIthOldest(i));
1211 assert id2hrn.containsKey(idShadowIth);
1212 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1213 assert hrnIthShadow.getNumReferencers() == 0;
1214 assert hrnIthShadow.getNumReferencees() == 0;
1216 transferOnto(hrnIth, hrnIthShadow);
1218 assert ogCallee.id2hrn.containsKey(idIth);
1219 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1220 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1222 rewriteCallerNodeAlpha(fm.numParameters(),
1225 paramIndex2rewriteH,
1226 paramIndex2rewriteD,
1227 paramIndex2paramToken,
1228 paramIndex2paramTokenStar);
1230 hrnIthShadow.applyAlphaNew();
1235 // for every heap region->heap region edge in the
1236 // callee graph, create the matching edge or edges
1237 // in the caller graph
1238 Set sCallee = ogCallee.id2hrn.entrySet();
1239 Iterator iCallee = sCallee.iterator();
1240 while( iCallee.hasNext() ) {
1241 Map.Entry meCallee = (Map.Entry)iCallee.next();
1242 Integer idCallee = (Integer) meCallee.getKey();
1243 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1245 Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1246 while( heapRegionsItrCallee.hasNext() ) {
1247 ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
1248 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1249 Integer idChildCallee = hrnChildCallee.getID();
1251 // only address this edge if it is not a special reflexive edge
1252 if( !edgeCallee.isInitialParamReflexive() ) {
1254 // now we know that in the callee method's ownership graph
1255 // there is a heap region->heap region reference edge given
1256 // by heap region pointers:
1257 // hrnCallee -> heapChildCallee
1259 // or by the ownership-graph independent ID's:
1260 // idCallee -> idChildCallee
1262 // make the edge with src and dst so beta info is
1263 // calculated once, then copy it for each new edge in caller
1264 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1266 edgeCallee.getFieldDesc(),
1268 toShadowTokens(ogCallee, edgeCallee.getBeta() )
1270 rewriteCallerEdgeBeta(fm.numParameters(),
1272 edgeNewInCallerTemplate,
1273 paramIndex2rewriteJ,
1274 paramIndex2rewriteD,
1275 paramIndex2paramToken,
1276 paramIndex2paramTokenStar,
1280 edgeNewInCallerTemplate.applyBetaNew();
1283 // So now make a set of possible source heaps in the caller graph
1284 // and a set of destination heaps in the caller graph, and make
1285 // a reference edge in the caller for every possible (src,dst) pair
1286 HashSet<HeapRegionNode> possibleCallerSrcs =
1287 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1288 (HeapRegionNode) edgeCallee.getSrc(),
1289 paramIndex2reachableCallerNodes);
1291 HashSet<HeapRegionNode> possibleCallerDsts =
1292 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1293 edgeCallee.getDst(),
1294 paramIndex2reachableCallerNodes);
1297 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1298 Iterator srcItr = possibleCallerSrcs.iterator();
1299 while( srcItr.hasNext() ) {
1300 HeapRegionNode src = (HeapRegionNode) srcItr.next();
1302 // check that if this source node has a definite type that
1303 // it also has the appropriate field, otherwise prune this
1304 AllocationSite asSrc = src.getAllocationSite();
1305 if( asSrc != null ) {
1306 boolean foundField = false;
1307 Iterator fieldsSrcItr = asSrc.getType().getClassDesc().getFields();
1308 while( fieldsSrcItr.hasNext() ) {
1309 FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1310 if( fd == edgeCallee.getFieldDesc() ) {
1316 // prune this source node possibility
1321 Iterator dstItr = possibleCallerDsts.iterator();
1322 while( dstItr.hasNext() ) {
1323 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1325 // check if this dst node has a definite type and
1326 // if it matches the callee edge
1327 AllocationSite asDst = dst.getAllocationSite();
1328 if( asDst != null && edgeCallee.getFieldDesc() != null ) {
1329 if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) { continue; }
1330 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) { continue; }
1331 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
1332 if( !asDst.getType().equals( edgeCallee.getFieldDesc().getType() ) ) { continue; }
1336 // otherwise the caller src and dst pair can match the edge, so make it
1337 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1338 edgeNewInCaller.setSrc(src);
1339 edgeNewInCaller.setDst(dst);
1341 ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1342 if( edgeExisting == null ) {
1343 // if this edge doesn't exist in the caller, create it
1344 addReferenceEdge(src, dst, edgeNewInCaller);
1346 // if it already exists, merge with it
1347 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1357 // return value may need to be assigned in caller
1358 if( fc.getReturnTemp() != null ) {
1360 LabelNode lnLhsCaller = getLabelNodeFromTemp(fc.getReturnTemp() );
1361 clearReferenceEdgesFrom(lnLhsCaller, null, true);
1363 LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1364 Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1365 while( edgeCalleeItr.hasNext() ) {
1366 ReferenceEdge edgeCallee = edgeCalleeItr.next();
1368 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1370 edgeCallee.getFieldDesc(),
1372 toShadowTokens(ogCallee, edgeCallee.getBeta() )
1374 rewriteCallerEdgeBeta(fm.numParameters(),
1376 edgeNewInCallerTemplate,
1377 paramIndex2rewriteJ,
1378 paramIndex2rewriteD,
1379 paramIndex2paramToken,
1380 paramIndex2paramTokenStar,
1384 edgeNewInCallerTemplate.applyBetaNew();
1387 HashSet<HeapRegionNode> assignCallerRhs =
1388 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1389 edgeCallee.getDst(),
1390 paramIndex2reachableCallerNodes);
1392 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1393 while( itrHrn.hasNext() ) {
1394 HeapRegionNode hrnCaller = itrHrn.next();
1396 // check if this dst node has a definite type and
1397 // if it matches the callee edge
1398 // check if this dst node has a definite type and
1399 // if it matches the callee edge
1400 AllocationSite asDst = hrnCaller.getAllocationSite();
1401 if( asDst != null && edgeCallee.getFieldDesc() != null ) {
1402 if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) { continue; }
1403 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) { continue; }
1404 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
1405 if( !asDst.getType().equals( edgeCallee.getFieldDesc().getType() ) ) { continue; }
1409 // otherwise caller node can match callee edge, so make it
1410 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1411 edgeNewInCaller.setSrc(lnLhsCaller);
1412 edgeNewInCaller.setDst(hrnCaller);
1414 ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1415 if( edgeExisting == null ) {
1416 // if this edge doesn't exist in the caller, create it
1417 addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1419 // if it already exists, merge with it
1420 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1428 // merge the shadow nodes of allocation sites back down to normal capacity
1429 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1430 while( allocItr.hasNext() ) {
1431 AllocationSite as = allocItr.next();
1433 // first age each allocation site enough times to make room for the shadow nodes
1434 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1438 // then merge the shadow summary into the normal summary
1439 HeapRegionNode hrnSummary = getSummaryNode(as);
1440 assert hrnSummary != null;
1442 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1443 assert hrnSummaryShadow != null;
1445 mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1447 // then clear off after merge
1448 clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1449 clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1450 hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1452 // then transplant shadow nodes onto the now clean normal nodes
1453 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1455 Integer idIth = as.getIthOldest(i);
1456 HeapRegionNode hrnIth = id2hrn.get(idIth);
1458 Integer idIthShadow = as.getIthOldestShadow(i);
1459 HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1461 transferOnto(hrnIthShadow, hrnIth);
1463 // clear off shadow nodes after transfer
1464 clearReferenceEdgesFrom(hrnIthShadow, null, true);
1465 clearReferenceEdgesTo(hrnIthShadow, null, true);
1466 hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1469 // finally, globally change shadow tokens into normal tokens
1470 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1471 while( itrAllLabelNodes.hasNext() ) {
1472 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1473 LabelNode ln = (LabelNode) me.getValue();
1475 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1476 while( itrEdges.hasNext() ) {
1477 unshadowTokens(as, itrEdges.next() );
1481 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1482 while( itrAllHRNodes.hasNext() ) {
1483 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1484 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1486 unshadowTokens(as, hrnToAge);
1488 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1489 while( itrEdges.hasNext() ) {
1490 unshadowTokens(as, itrEdges.next() );
1497 protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1498 edge.setBeta(edge.getBeta().unshadowTokens(as) );
1501 protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1502 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1506 private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1507 ReachabilitySet rsIn) {
1509 ReachabilitySet rsOut = new ReachabilitySet(rsIn);
1511 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1512 while( allocItr.hasNext() ) {
1513 AllocationSite as = allocItr.next();
1515 rsOut = rsOut.toShadowTokens(as);
1518 return rsOut.makeCanonical();
1522 private void rewriteCallerNodeAlpha(int numParameters,
1525 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
1526 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1527 Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1528 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1530 ReachabilitySet rules = paramIndex2rewriteH.get(paramIndex);
1531 assert rules != null;
1533 TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1534 assert tokenToRewrite != null;
1536 ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
1537 Iterator<TokenTupleSet> ttsItr = rules.iterator();
1538 while( ttsItr.hasNext() ) {
1539 TokenTupleSet tts = ttsItr.next();
1540 r0 = r0.union(tts.rewriteToken(tokenToRewrite,
1546 ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1547 ttsItr = r0.iterator();
1548 while( ttsItr.hasNext() ) {
1549 TokenTupleSet tts = ttsItr.next();
1550 r1 = r1.union(rewriteDpass(numParameters,
1553 paramIndex2rewriteD,
1554 paramIndex2paramToken,
1555 paramIndex2paramTokenStar) );
1558 hrn.setAlphaNew(hrn.getAlphaNew().union(r1) );
1562 private void rewriteCallerEdgeBeta(int numParameters,
1565 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJorK,
1566 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1567 Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1568 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar,
1569 boolean makeChangeSet,
1570 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1572 ReachabilitySet rules = paramIndex2rewriteJorK.get(paramIndex);
1573 assert rules != null;
1575 TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1576 assert tokenToRewrite != null;
1578 ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
1580 Iterator<TokenTupleSet> ttsItr = rules.iterator();
1581 while( ttsItr.hasNext() ) {
1582 TokenTupleSet tts = ttsItr.next();
1584 Hashtable<TokenTupleSet, TokenTupleSet> forChangeSet =
1585 new Hashtable<TokenTupleSet, TokenTupleSet>();
1587 ReachabilitySet rTemp = tts.rewriteToken(tokenToRewrite,
1592 Iterator fcsItr = forChangeSet.entrySet().iterator();
1593 while( fcsItr.hasNext() ) {
1594 Map.Entry me = (Map.Entry)fcsItr.next();
1595 TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey();
1596 TokenTupleSet ttsAdd = (TokenTupleSet) me.getValue();
1598 ChangeTuple ct = new ChangeTuple(ttsMatch,
1602 cts0 = cts0.union(ct);
1607 ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1608 ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical();
1610 Iterator<ChangeTuple> ctItr = cts0.iterator();
1611 while( ctItr.hasNext() ) {
1612 ChangeTuple ct = ctItr.next();
1614 ReachabilitySet rTemp = rewriteDpass(numParameters,
1617 paramIndex2rewriteD,
1618 paramIndex2paramToken,
1619 paramIndex2paramTokenStar
1621 r1 = r1.union(rTemp);
1623 if( makeChangeSet ) {
1624 assert edgePlannedChanges != null;
1626 Iterator<TokenTupleSet> ttsTempItr = rTemp.iterator();
1627 while( ttsTempItr.hasNext() ) {
1628 TokenTupleSet tts = ttsTempItr.next();
1630 ChangeTuple ctFinal = new ChangeTuple(ct.getSetToMatch(),
1634 cts1 = cts1.union(ctFinal);
1639 if( makeChangeSet ) {
1640 edgePlannedChanges.put(edge, cts1);
1643 edge.setBetaNew(edge.getBetaNew().union(r1) );
1647 private ReachabilitySet rewriteDpass(int numParameters,
1649 TokenTupleSet ttsIn,
1650 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1651 Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1652 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1654 ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
1656 boolean rewritten = false;
1658 for( int j = 0; j < numParameters; ++j ) {
1659 Integer paramIndexJ = new Integer(j);
1660 ReachabilitySet D_j = paramIndex2rewriteD.get(paramIndexJ);
1663 if( paramIndexJ != paramIndex ) {
1664 TokenTuple tokenToRewriteJ = paramIndex2paramToken.get(paramIndexJ);
1665 assert tokenToRewriteJ != null;
1666 if( ttsIn.containsTuple(tokenToRewriteJ) ) {
1667 ReachabilitySet r = ttsIn.rewriteToken(tokenToRewriteJ,
1671 Iterator<TokenTupleSet> ttsItr = r.iterator();
1672 while( ttsItr.hasNext() ) {
1673 TokenTupleSet tts = ttsItr.next();
1674 rsOut = rsOut.union(rewriteDpass(numParameters,
1677 paramIndex2rewriteD,
1678 paramIndex2paramToken,
1679 paramIndex2paramTokenStar) );
1685 TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get(paramIndexJ);
1686 assert tokenStarToRewriteJ != null;
1687 if( ttsIn.containsTuple(tokenStarToRewriteJ) ) {
1688 ReachabilitySet r = ttsIn.rewriteToken(tokenStarToRewriteJ,
1692 Iterator<TokenTupleSet> ttsItr = r.iterator();
1693 while( ttsItr.hasNext() ) {
1694 TokenTupleSet tts = ttsItr.next();
1695 rsOut = rsOut.union(rewriteDpass(numParameters,
1698 paramIndex2rewriteD,
1699 paramIndex2paramToken,
1700 paramIndex2paramTokenStar) );
1707 rsOut = rsOut.union(ttsIn);
1714 private HashSet<HeapRegionNode>
1715 getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1716 HeapRegionNode hrnCallee,
1717 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1720 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1722 Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
1724 if( paramIndexCallee == null ) {
1725 // this is a node allocated in the callee then and it has
1726 // exactly one shadow node in the caller to map to
1727 AllocationSite as = hrnCallee.getAllocationSite();
1730 int age = as.getAgeCategory(hrnCallee.getID() );
1731 assert age != AllocationSite.AGE_notInThisSite;
1734 if( age == AllocationSite.AGE_summary ) {
1735 idCaller = as.getSummaryShadow();
1736 } else if( age == AllocationSite.AGE_oldest ) {
1737 idCaller = as.getOldestShadow();
1739 assert age == AllocationSite.AGE_in_I;
1741 Integer I = as.getAge(hrnCallee.getID() );
1744 idCaller = as.getIthOldestShadow(I);
1747 assert id2hrn.containsKey(idCaller);
1748 HeapRegionNode hrnCaller = id2hrn.get(idCaller);
1749 possibleCallerHRNs.add(hrnCaller);
1752 // this is a node that was created to represent a parameter
1753 // so it maps to a whole mess of heap regions
1754 assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
1755 possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
1758 return possibleCallerHRNs;
1763 ////////////////////////////////////////////////////
1764 // in merge() and equals() methods the suffix A
1765 // represents the passed in graph and the suffix
1766 // B refers to the graph in this object
1767 // Merging means to take the incoming graph A and
1768 // merge it into B, so after the operation graph B
1769 // is the final result.
1770 ////////////////////////////////////////////////////
1771 public void merge(OwnershipGraph og) {
1777 mergeOwnershipNodes(og);
1778 mergeReferenceEdges(og);
1779 mergeId2paramIndex(og);
1780 mergeAllocationSites(og);
1784 protected void mergeOwnershipNodes(OwnershipGraph og) {
1785 Set sA = og.id2hrn.entrySet();
1786 Iterator iA = sA.iterator();
1787 while( iA.hasNext() ) {
1788 Map.Entry meA = (Map.Entry)iA.next();
1789 Integer idA = (Integer) meA.getKey();
1790 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1792 // if this graph doesn't have a node the
1793 // incoming graph has, allocate it
1794 if( !id2hrn.containsKey(idA) ) {
1795 HeapRegionNode hrnB = hrnA.copy();
1796 id2hrn.put(idA, hrnB);
1799 // otherwise this is a node present in both graphs
1800 // so make the new reachability set a union of the
1801 // nodes' reachability sets
1802 HeapRegionNode hrnB = id2hrn.get(idA);
1803 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1807 // now add any label nodes that are in graph B but
1809 sA = og.td2ln.entrySet();
1811 while( iA.hasNext() ) {
1812 Map.Entry meA = (Map.Entry)iA.next();
1813 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1814 LabelNode lnA = (LabelNode) meA.getValue();
1816 // if the label doesn't exist in B, allocate and add it
1817 LabelNode lnB = getLabelNodeFromTemp(tdA);
1821 protected void mergeReferenceEdges(OwnershipGraph og) {
1824 Set sA = og.id2hrn.entrySet();
1825 Iterator iA = sA.iterator();
1826 while( iA.hasNext() ) {
1827 Map.Entry meA = (Map.Entry)iA.next();
1828 Integer idA = (Integer) meA.getKey();
1829 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1831 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1832 while( heapRegionsItrA.hasNext() ) {
1833 ReferenceEdge edgeA = heapRegionsItrA.next();
1834 HeapRegionNode hrnChildA = edgeA.getDst();
1835 Integer idChildA = hrnChildA.getID();
1837 // at this point we know an edge in graph A exists
1838 // idA -> idChildA, does this exist in B?
1839 assert id2hrn.containsKey(idA);
1840 HeapRegionNode hrnB = id2hrn.get(idA);
1841 ReferenceEdge edgeToMerge = null;
1843 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1844 while( heapRegionsItrB.hasNext() &&
1845 edgeToMerge == null ) {
1847 ReferenceEdge edgeB = heapRegionsItrB.next();
1848 HeapRegionNode hrnChildB = edgeB.getDst();
1849 Integer idChildB = hrnChildB.getID();
1851 // don't use the ReferenceEdge.equals() here because
1852 // we're talking about existence between graphs
1853 if( idChildB.equals(idChildA) &&
1854 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1855 edgeToMerge = edgeB;
1859 // if the edge from A was not found in B,
1861 if( edgeToMerge == null ) {
1862 assert id2hrn.containsKey(idChildA);
1863 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1864 edgeToMerge = edgeA.copy();
1865 edgeToMerge.setSrc(hrnB);
1866 edgeToMerge.setDst(hrnChildB);
1867 addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1869 // otherwise, the edge already existed in both graphs
1870 // so merge their reachability sets
1872 // just replace this beta set with the union
1873 assert edgeToMerge != null;
1874 edgeToMerge.setBeta(
1875 edgeToMerge.getBeta().union(edgeA.getBeta() )
1877 if( !edgeA.isInitialParamReflexive() ) {
1878 edgeToMerge.setIsInitialParamReflexive(false);
1884 // and then again with label nodes
1885 sA = og.td2ln.entrySet();
1887 while( iA.hasNext() ) {
1888 Map.Entry meA = (Map.Entry)iA.next();
1889 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1890 LabelNode lnA = (LabelNode) meA.getValue();
1892 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1893 while( heapRegionsItrA.hasNext() ) {
1894 ReferenceEdge edgeA = heapRegionsItrA.next();
1895 HeapRegionNode hrnChildA = edgeA.getDst();
1896 Integer idChildA = hrnChildA.getID();
1898 // at this point we know an edge in graph A exists
1899 // tdA -> idChildA, does this exist in B?
1900 assert td2ln.containsKey(tdA);
1901 LabelNode lnB = td2ln.get(tdA);
1902 ReferenceEdge edgeToMerge = null;
1904 // labels never have edges with a field
1905 //assert edgeA.getFieldDesc() == null;
1907 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1908 while( heapRegionsItrB.hasNext() &&
1909 edgeToMerge == null ) {
1911 ReferenceEdge edgeB = heapRegionsItrB.next();
1912 HeapRegionNode hrnChildB = edgeB.getDst();
1913 Integer idChildB = hrnChildB.getID();
1915 // labels never have edges with a field
1916 //assert edgeB.getFieldDesc() == null;
1918 // don't use the ReferenceEdge.equals() here because
1919 // we're talking about existence between graphs
1920 if( idChildB.equals(idChildA) &&
1921 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1922 edgeToMerge = edgeB;
1926 // if the edge from A was not found in B,
1928 if( edgeToMerge == null ) {
1929 assert id2hrn.containsKey(idChildA);
1930 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1931 edgeToMerge = edgeA.copy();
1932 edgeToMerge.setSrc(lnB);
1933 edgeToMerge.setDst(hrnChildB);
1934 addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1936 // otherwise, the edge already existed in both graphs
1937 // so merge their reachability sets
1939 // just replace this beta set with the union
1940 edgeToMerge.setBeta(
1941 edgeToMerge.getBeta().union(edgeA.getBeta() )
1943 if( !edgeA.isInitialParamReflexive() ) {
1944 edgeToMerge.setIsInitialParamReflexive(false);
1951 // you should only merge ownership graphs that have the
1952 // same number of parameters, or if one or both parameter
1953 // index tables are empty
1954 protected void mergeId2paramIndex(OwnershipGraph og) {
1955 if( id2paramIndex.size() == 0 ) {
1956 id2paramIndex = og.id2paramIndex;
1957 paramIndex2id = og.paramIndex2id;
1958 paramIndex2tdQ = og.paramIndex2tdQ;
1962 if( og.id2paramIndex.size() == 0 ) {
1966 assert id2paramIndex.size() == og.id2paramIndex.size();
1969 protected void mergeAllocationSites(OwnershipGraph og) {
1970 allocationSites.addAll(og.allocationSites);
1975 // it is necessary in the equals() member functions
1976 // to "check both ways" when comparing the data
1977 // structures of two graphs. For instance, if all
1978 // edges between heap region nodes in graph A are
1979 // present and equal in graph B it is not sufficient
1980 // to say the graphs are equal. Consider that there
1981 // may be edges in graph B that are not in graph A.
1982 // the only way to know that all edges in both graphs
1983 // are equally present is to iterate over both data
1984 // structures and compare against the other graph.
1985 public boolean equals(OwnershipGraph og) {
1991 if( !areHeapRegionNodesEqual(og) ) {
1995 if( !areLabelNodesEqual(og) ) {
1999 if( !areReferenceEdgesEqual(og) ) {
2003 if( !areId2paramIndexEqual(og) ) {
2007 // if everything is equal up to this point,
2008 // assert that allocationSites is also equal--
2009 // this data is redundant and kept for efficiency
2010 assert allocationSites.equals(og.allocationSites);
2015 protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2017 if( !areallHRNinAalsoinBandequal(this, og) ) {
2021 if( !areallHRNinAalsoinBandequal(og, this) ) {
2028 static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2029 OwnershipGraph ogB) {
2030 Set sA = ogA.id2hrn.entrySet();
2031 Iterator iA = sA.iterator();
2032 while( iA.hasNext() ) {
2033 Map.Entry meA = (Map.Entry)iA.next();
2034 Integer idA = (Integer) meA.getKey();
2035 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2037 if( !ogB.id2hrn.containsKey(idA) ) {
2041 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2042 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2051 protected boolean areLabelNodesEqual(OwnershipGraph og) {
2053 if( !areallLNinAalsoinBandequal(this, og) ) {
2057 if( !areallLNinAalsoinBandequal(og, this) ) {
2064 static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2065 OwnershipGraph ogB) {
2066 Set sA = ogA.td2ln.entrySet();
2067 Iterator iA = sA.iterator();
2068 while( iA.hasNext() ) {
2069 Map.Entry meA = (Map.Entry)iA.next();
2070 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2072 if( !ogB.td2ln.containsKey(tdA) ) {
2081 protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2082 if( !areallREinAandBequal(this, og) ) {
2089 static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2090 OwnershipGraph ogB) {
2092 // check all the heap region->heap region edges
2093 Set sA = ogA.id2hrn.entrySet();
2094 Iterator iA = sA.iterator();
2095 while( iA.hasNext() ) {
2096 Map.Entry meA = (Map.Entry)iA.next();
2097 Integer idA = (Integer) meA.getKey();
2098 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2100 // we should have already checked that the same
2101 // heap regions exist in both graphs
2102 assert ogB.id2hrn.containsKey(idA);
2104 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2108 // then check every edge in B for presence in A, starting
2109 // from the same parent HeapRegionNode
2110 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2112 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2117 // then check all the label->heap region edges
2118 sA = ogA.td2ln.entrySet();
2120 while( iA.hasNext() ) {
2121 Map.Entry meA = (Map.Entry)iA.next();
2122 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2123 LabelNode lnA = (LabelNode) meA.getValue();
2125 // we should have already checked that the same
2126 // label nodes exist in both graphs
2127 assert ogB.td2ln.containsKey(tdA);
2129 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2133 // then check every edge in B for presence in A, starting
2134 // from the same parent LabelNode
2135 LabelNode lnB = ogB.td2ln.get(tdA);
2137 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2146 static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2148 OwnershipGraph ogB) {
2150 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2151 while( itrA.hasNext() ) {
2152 ReferenceEdge edgeA = itrA.next();
2153 HeapRegionNode hrnChildA = edgeA.getDst();
2154 Integer idChildA = hrnChildA.getID();
2156 assert ogB.id2hrn.containsKey(idChildA);
2158 // at this point we know an edge in graph A exists
2159 // onA -> idChildA, does this exact edge exist in B?
2160 boolean edgeFound = false;
2162 OwnershipNode onB = null;
2163 if( onA instanceof HeapRegionNode ) {
2164 HeapRegionNode hrnA = (HeapRegionNode) onA;
2165 onB = ogB.id2hrn.get(hrnA.getID() );
2167 LabelNode lnA = (LabelNode) onA;
2168 onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2171 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2172 while( itrB.hasNext() ) {
2173 ReferenceEdge edgeB = itrB.next();
2174 HeapRegionNode hrnChildB = edgeB.getDst();
2175 Integer idChildB = hrnChildB.getID();
2177 if( idChildA.equals(idChildB) &&
2178 edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2180 // there is an edge in the right place with the right field,
2181 // but do they have the same attributes?
2182 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2200 protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2201 return id2paramIndex.size() == og.id2paramIndex.size();
2205 public boolean hasPotentialAlias( Integer paramIndex1, Integer paramIndex2 ) {
2207 // get parameter's heap region
2208 assert paramIndex2id.containsKey(paramIndex1);
2209 Integer idParam1 = paramIndex2id.get(paramIndex1);
2211 assert id2hrn.containsKey(idParam1);
2212 HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2213 assert hrnParam1 != null;
2215 // get tokens for this parameter
2216 TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2218 TokenTuple.ARITY_ONE).makeCanonical();
2220 TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2222 TokenTuple.ARITY_MANY).makeCanonical();
2225 // get tokens for the other parameter
2226 assert paramIndex2id.containsKey(paramIndex2);
2227 Integer idParam2 = paramIndex2id.get(paramIndex2);
2229 assert id2hrn.containsKey(idParam2);
2230 HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2231 assert hrnParam2 != null;
2233 TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2235 TokenTuple.ARITY_ONE).makeCanonical();
2237 TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2239 TokenTuple.ARITY_MANY).makeCanonical();
2242 // get special label p_q for first parameter
2243 TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2244 assert tdParamQ1 != null;
2245 LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2246 assert lnParamQ1 != null;
2248 // then get the edge from label q to parameter's hrn
2249 ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2250 assert edgeSpecialQ1 != null;
2252 // if the beta of this edge has tokens from both parameters in one
2253 // token tuple set, then there is a potential alias between them
2254 ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2255 assert beta1 != null;
2257 if( beta1.containsTupleSetWithBoth( p1, p2 ) ) { return true; }
2258 if( beta1.containsTupleSetWithBoth( pStar1, p2 ) ) { return true; }
2259 if( beta1.containsTupleSetWithBoth( p1, pStar2 ) ) { return true; }
2260 if( beta1.containsTupleSetWithBoth( pStar1, pStar2 ) ) { return true; }
2266 public boolean hasPotentialAlias( Integer paramIndex, AllocationSite as ) {
2268 // get parameter's heap region
2269 assert paramIndex2id.containsKey(paramIndex);
2270 Integer idParam = paramIndex2id.get(paramIndex);
2272 assert id2hrn.containsKey(idParam);
2273 HeapRegionNode hrnParam = id2hrn.get(idParam);
2274 assert hrnParam != null;
2276 // get tokens for this parameter
2277 TokenTuple p = new TokenTuple(hrnParam.getID(),
2279 TokenTuple.ARITY_ONE).makeCanonical();
2281 TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2283 TokenTuple.ARITY_MANY).makeCanonical();
2285 // get special label p_q
2286 TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2287 assert tdParamQ != null;
2288 LabelNode lnParamQ = td2ln.get(tdParamQ);
2289 assert lnParamQ != null;
2291 // then get the edge from label q to parameter's hrn
2292 ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2293 assert edgeSpecialQ != null;
2295 // look through this beta set for potential aliases
2296 ReachabilitySet beta = edgeSpecialQ.getBeta();
2297 assert beta != null;
2300 // get tokens for summary node
2301 TokenTuple gs = new TokenTuple(as.getSummary(),
2303 TokenTuple.ARITY_ONE).makeCanonical();
2305 TokenTuple gsStar = new TokenTuple(as.getSummary(),
2307 TokenTuple.ARITY_MANY).makeCanonical();
2309 if( beta.containsTupleSetWithBoth( p, gs ) ) { return true; }
2310 if( beta.containsTupleSetWithBoth( pStar, gs ) ) { return true; }
2311 if( beta.containsTupleSetWithBoth( p, gsStar ) ) { return true; }
2312 if( beta.containsTupleSetWithBoth( pStar, gsStar ) ) { return true; }
2314 // check for other nodes
2315 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2317 // the other nodes of an allocation site are single, no stars
2318 TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2320 TokenTuple.ARITY_ONE).makeCanonical();
2322 if( beta.containsTupleSetWithBoth( p, gi ) ) { return true; }
2323 if( beta.containsTupleSetWithBoth( pStar, gi ) ) { return true; }
2330 public boolean hasPotentialAlias( AllocationSite as1, AllocationSite as2 ) {
2332 // get tokens for summary nodes
2333 TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2335 TokenTuple.ARITY_ONE).makeCanonical();
2337 TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2339 TokenTuple.ARITY_MANY).makeCanonical();
2341 // get summary node's alpha
2342 Integer idSum1 = as1.getSummary();
2343 assert id2hrn.containsKey( idSum1 );
2344 HeapRegionNode hrnSum1 = id2hrn.get( idSum1 );
2345 assert hrnSum1 != null;
2346 ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2347 assert alphaSum1 != null;
2350 // and for the other one
2351 TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2353 TokenTuple.ARITY_ONE).makeCanonical();
2355 TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2357 TokenTuple.ARITY_MANY).makeCanonical();
2359 // get summary node's alpha
2360 Integer idSum2 = as2.getSummary();
2361 assert id2hrn.containsKey( idSum2 );
2362 HeapRegionNode hrnSum2 = id2hrn.get( idSum2 );
2363 assert hrnSum2 != null;
2364 ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2365 assert alphaSum2 != null;
2367 // does either one report reachability from the other tokens?
2368 if( alphaSum1.containsTuple( gsStar2 ) ) { return true; }
2369 if( alphaSum2.containsTuple( gsStar1 ) ) { return true; }
2371 // only check non-star token if they are different sites
2373 if( alphaSum1.containsTuple( gs2 ) ) { return true; }
2374 if( alphaSum2.containsTuple( gs1 ) ) { return true; }
2378 // check sum2 against alloc1 nodes
2379 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2380 Integer idI1 = as1.getIthOldest(i);
2381 assert id2hrn.containsKey( idI1 );
2382 HeapRegionNode hrnI1 = id2hrn.get( idI1 );
2383 assert hrnI1 != null;
2384 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2385 assert alphaI1 != null;
2387 // the other nodes of an allocation site are single, no stars
2388 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2390 TokenTuple.ARITY_ONE).makeCanonical();
2392 if( alphaSum2.containsTuple( gi1 ) ) { return true; }
2393 if( alphaI1.containsTuple ( gs2 ) ) { return true; }
2394 if( alphaI1.containsTuple ( gsStar2 ) ) { return true; }
2397 // check sum1 against alloc2 nodes
2398 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2399 Integer idI2 = as2.getIthOldest(i);
2400 assert id2hrn.containsKey( idI2 );
2401 HeapRegionNode hrnI2 = id2hrn.get( idI2 );
2402 assert hrnI2 != null;
2403 ReachabilitySet alphaI2 = hrnI2.getAlpha();
2404 assert alphaI2 != null;
2406 TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2408 TokenTuple.ARITY_ONE).makeCanonical();
2410 if( alphaSum1.containsTuple( gi2 ) ) { return true; }
2411 if( alphaI2.containsTuple ( gs1 ) ) { return true; }
2412 if( alphaI2.containsTuple ( gsStar1 ) ) { return true; }
2414 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
2415 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
2416 Integer idI1 = as1.getIthOldest(j);
2418 // if these are the same site, don't look for the same token, no alias
2419 // different tokens of the same site could alias together though
2420 if( idI1 == idI2 ) { continue; }
2422 HeapRegionNode hrnI1 = id2hrn.get( idI1 );
2423 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2424 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
2426 TokenTuple.ARITY_ONE).makeCanonical();
2427 if( alphaI2.containsTuple( gi1 ) ) { return true; }
2428 if( alphaI1.containsTuple( gi2 ) ) { return true; }
2436 // for writing ownership graphs to dot files
2437 public void writeGraph(Descriptor methodDesc,
2439 boolean writeLabels,
2440 boolean labelSelect,
2441 boolean pruneGarbage,
2442 boolean writeReferencers
2443 ) throws java.io.IOException {
2445 methodDesc.getSymbol() +
2446 methodDesc.getNum() +
2455 public void writeGraph(Descriptor methodDesc,
2456 boolean writeLabels,
2457 boolean labelSelect,
2458 boolean pruneGarbage,
2459 boolean writeReferencers
2460 ) throws java.io.IOException {
2462 writeGraph(methodDesc+"COMPLETE",
2470 public void writeGraph(String graphName,
2471 boolean writeLabels,
2472 boolean labelSelect,
2473 boolean pruneGarbage,
2474 boolean writeReferencers
2475 ) throws java.io.IOException {
2477 // remove all non-word characters from the graph name so
2478 // the filename and identifier in dot don't cause errors
2479 graphName = graphName.replaceAll("[\\W]", "");
2481 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2482 bw.write("digraph "+graphName+" {\n");
2483 //bw.write( " size=\"7.5,10\";\n" );
2485 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2487 // then visit every heap region node
2488 if( !pruneGarbage ) {
2489 Set s = id2hrn.entrySet();
2490 Iterator i = s.iterator();
2491 while( i.hasNext() ) {
2492 Map.Entry me = (Map.Entry)i.next();
2493 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2494 if( !visited.contains(hrn) ) {
2495 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2505 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
2508 // then visit every label node, useful for debugging
2510 Set s = td2ln.entrySet();
2511 Iterator i = s.iterator();
2512 while( i.hasNext() ) {
2513 Map.Entry me = (Map.Entry)i.next();
2514 LabelNode ln = (LabelNode) me.getValue();
2517 String labelStr = ln.getTempDescriptorString();
2518 if( labelStr.startsWith("___temp") ||
2519 labelStr.startsWith("___dst") ||
2520 labelStr.startsWith("___srctmp") ||
2521 labelStr.startsWith("___neverused") ) {
2526 bw.write(ln.toString() + ";\n");
2528 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2529 while( heapRegionsItr.hasNext() ) {
2530 ReferenceEdge edge = heapRegionsItr.next();
2531 HeapRegionNode hrn = edge.getDst();
2533 if( pruneGarbage && !visited.contains(hrn) ) {
2534 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2542 bw.write(" " + ln.toString() +
2543 " -> " + hrn.toString() +
2544 "[label=\"" + edge.toGraphEdgeString() +
2555 protected void traverseHeapRegionNodes(int mode,
2559 HashSet<HeapRegionNode> visited,
2560 boolean writeReferencers
2561 ) throws java.io.IOException {
2563 if( visited.contains(hrn) ) {
2569 case VISIT_HRN_WRITE_FULL:
2571 String attributes = "[";
2573 if( hrn.isSingleObject() ) {
2574 attributes += "shape=box";
2576 attributes += "shape=Msquare";
2579 if( hrn.isFlagged() ) {
2580 attributes += ",style=filled,fillcolor=lightgrey";
2583 attributes += ",label=\"ID" +
2586 hrn.getDescription() +
2588 hrn.getAlphaString() +
2591 bw.write(" " + hrn.toString() + attributes + ";\n");
2596 // useful for debugging
2597 if( writeReferencers ) {
2598 OwnershipNode onRef = null;
2599 Iterator refItr = hrn.iteratorToReferencers();
2600 while( refItr.hasNext() ) {
2601 onRef = (OwnershipNode) refItr.next();
2604 case VISIT_HRN_WRITE_FULL:
2605 bw.write(" " + hrn.toString() +
2606 " -> " + onRef.toString() +
2607 "[color=lightgray];\n");
2613 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2614 while( childRegionsItr.hasNext() ) {
2615 ReferenceEdge edge = childRegionsItr.next();
2616 HeapRegionNode hrnChild = edge.getDst();
2619 case VISIT_HRN_WRITE_FULL:
2620 bw.write(" " + hrn.toString() +
2621 " -> " + hrnChild.toString() +
2622 "[label=\"" + edge.toGraphEdgeString() +
2627 traverseHeapRegionNodes(mode,