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) {
890 // define rewrite rules and other structures to organize
891 // data by parameter/argument index
892 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
893 new Hashtable<Integer, ReachabilitySet>();
895 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
896 new Hashtable<Integer, ReachabilitySet>();
898 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
899 new Hashtable<Integer, ReachabilitySet>();
901 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
902 new Hashtable<Integer, ReachabilitySet>();
904 // helpful structures
905 Hashtable<TokenTuple, Integer> paramToken2paramIndex =
906 new Hashtable<TokenTuple, Integer>();
908 Hashtable<Integer, TokenTuple> paramIndex2paramToken =
909 new Hashtable<Integer, TokenTuple>();
911 Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
912 new Hashtable<TokenTuple, Integer>();
914 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
915 new Hashtable<Integer, TokenTuple>();
917 Hashtable<Integer, LabelNode> paramIndex2ln =
918 new Hashtable<Integer, LabelNode>();
920 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
921 new Hashtable<Integer, HashSet<HeapRegionNode> >();
924 // add a bogus entry with the identity rule for easy rewrite
925 // of new callee nodes and edges, doesn't belong to any parameter
926 Integer bogusID = new Integer(-1);
927 Integer bogusIndex = new Integer(-1);
928 TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE);
929 TokenTuple bogusTokenStar = new TokenTuple(bogusID, true, TokenTuple.ARITY_MANY);
930 ReachabilitySet rsIdentity =
931 new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical();
933 paramIndex2rewriteH.put(bogusIndex, rsIdentity);
934 paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
935 paramToken2paramIndex.put(bogusToken, bogusIndex);
936 paramIndex2paramToken.put(bogusIndex, bogusToken);
937 paramTokenStar2paramIndex.put(bogusTokenStar, bogusIndex);
938 paramIndex2paramTokenStar.put(bogusIndex, bogusTokenStar);
941 for( int i = 0; i < fm.numParameters(); ++i ) {
942 Integer paramIndex = new Integer(i);
944 assert ogCallee.paramIndex2id.containsKey(paramIndex);
945 Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
947 assert ogCallee.id2hrn.containsKey(idParam);
948 HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
949 assert hrnParam != null;
950 paramIndex2rewriteH.put(paramIndex,
952 toShadowTokens(ogCallee, hrnParam.getAlpha() )
955 ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
956 assert edgeReflexive_i != null;
957 paramIndex2rewriteJ.put(paramIndex,
958 toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
961 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
962 assert tdParamQ != null;
963 LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
964 assert lnParamQ != null;
965 ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
966 assert edgeSpecialQ_i != null;
967 paramIndex2rewriteK.put(paramIndex,
968 toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
971 TokenTuple p_i = new TokenTuple(hrnParam.getID(),
973 TokenTuple.ARITY_ONE).makeCanonical();
974 paramToken2paramIndex.put(p_i, paramIndex);
975 paramIndex2paramToken.put(paramIndex, p_i);
977 TokenTuple p_i_star = new TokenTuple(hrnParam.getID(),
979 TokenTuple.ARITY_MANY).makeCanonical();
980 paramTokenStar2paramIndex.put(p_i_star, paramIndex);
981 paramIndex2paramTokenStar.put(paramIndex, p_i_star);
983 // now depending on whether the callee is static or not
984 // we need to account for a "this" argument in order to
985 // find the matching argument in the caller context
986 TempDescriptor argTemp_i;
988 argTemp_i = fc.getArg(paramIndex);
990 if( paramIndex == 0 ) {
991 argTemp_i = fc.getThis();
993 argTemp_i = fc.getArg(paramIndex - 1);
997 // in non-static methods there is a "this" pointer
998 // that should be taken into account
1000 assert fc.numArgs() == fm.numParameters();
1002 assert fc.numArgs() + 1 == fm.numParameters();
1005 LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1006 paramIndex2ln.put(paramIndex, argLabel_i);
1008 ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
1009 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1010 while( edgeItr.hasNext() ) {
1011 ReferenceEdge edge = edgeItr.next();
1012 D_i = D_i.union(edge.getBeta() );
1014 D_i = D_i.exhaustiveArityCombinations();
1015 paramIndex2rewriteD.put(paramIndex, D_i);
1019 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1020 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
1022 HashSet<ReferenceEdge> edgesReachable = new HashSet<ReferenceEdge>();
1023 HashSet<ReferenceEdge> edgesUpstream = new HashSet<ReferenceEdge>();
1025 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1026 while( lnArgItr.hasNext() ) {
1027 Map.Entry me = (Map.Entry)lnArgItr.next();
1028 Integer index = (Integer) me.getKey();
1029 LabelNode lnArg_i = (LabelNode) me.getValue();
1031 // rewrite alpha for the nodes reachable from argument label i
1032 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1033 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1035 // to find all reachable nodes, start with label referencees
1036 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1037 while( edgeArgItr.hasNext() ) {
1038 ReferenceEdge edge = edgeArgItr.next();
1039 todoNodes.add(edge.getDst() );
1042 // then follow links until all reachable nodes have been found
1043 while( !todoNodes.isEmpty() ) {
1044 HeapRegionNode hrn = todoNodes.iterator().next();
1045 todoNodes.remove(hrn);
1046 reachableNodes.add(hrn);
1048 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1049 while( edgeItr.hasNext() ) {
1050 ReferenceEdge edge = edgeItr.next();
1052 if( !reachableNodes.contains(edge.getDst() ) ) {
1053 todoNodes.add(edge.getDst() );
1059 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1061 // now iterate over reachable nodes to update their alpha, and
1062 // classify edges found as "argument reachable" or "upstream"
1063 Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1064 while( hrnItr.hasNext() ) {
1065 HeapRegionNode hrn = hrnItr.next();
1067 rewriteCallerNodeAlpha(fm.numParameters(),
1070 paramIndex2rewriteH,
1071 paramIndex2rewriteD,
1072 paramIndex2paramToken,
1073 paramIndex2paramTokenStar);
1075 nodesWithNewAlpha.add(hrn);
1077 // look at all incoming edges to the reachable nodes
1078 // and sort them as edges reachable from the argument
1079 // label node, or upstream edges
1080 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1081 while( edgeItr.hasNext() ) {
1082 ReferenceEdge edge = edgeItr.next();
1084 OwnershipNode on = edge.getSrc();
1086 if( on instanceof LabelNode ) {
1088 LabelNode ln0 = (LabelNode) on;
1089 if( ln0.equals(lnArg_i) ) {
1090 edgesReachable.add(edge);
1092 edgesUpstream.add(edge);
1097 HeapRegionNode hrn0 = (HeapRegionNode) on;
1098 if( reachableNodes.contains(hrn0) ) {
1099 edgesReachable.add(edge);
1101 edgesUpstream.add(edge);
1108 // update reachable edges
1109 Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1110 while( edgeReachableItr.hasNext() ) {
1111 ReferenceEdge edgeReachable = edgeReachableItr.next();
1113 rewriteCallerEdgeBeta(fm.numParameters(),
1116 paramIndex2rewriteJ,
1117 paramIndex2rewriteD,
1118 paramIndex2paramToken,
1119 paramIndex2paramTokenStar,
1123 edgesWithNewBeta.add(edgeReachable);
1127 // update upstream edges
1128 Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges
1129 = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1131 Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1132 while( edgeUpstreamItr.hasNext() ) {
1133 ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1135 rewriteCallerEdgeBeta(fm.numParameters(),
1138 paramIndex2rewriteK,
1139 paramIndex2rewriteD,
1140 paramIndex2paramToken,
1141 paramIndex2paramTokenStar,
1143 edgeUpstreamPlannedChanges);
1145 edgesWithNewBeta.add(edgeUpstream);
1148 propagateTokensOverEdges(edgesUpstream,
1149 edgeUpstreamPlannedChanges,
1154 // commit changes to alpha and beta
1155 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1156 while( nodeItr.hasNext() ) {
1157 nodeItr.next().applyAlphaNew();
1160 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1161 while( edgeItr.hasNext() ) {
1162 edgeItr.next().applyBetaNew();
1167 // verify the existence of allocation sites and their
1168 // shadows from the callee in the context of this caller graph
1169 // then map allocated nodes of callee onto the caller shadows
1171 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1172 while( asItr.hasNext() ) {
1173 AllocationSite allocSite = asItr.next();
1174 HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1176 // assert that the shadow nodes have no reference edges
1177 // because they're brand new to the graph, or last time
1178 // they were used they should have been cleared of edges
1179 HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1180 assert hrnShadowSummary.getNumReferencers() == 0;
1181 assert hrnShadowSummary.getNumReferencees() == 0;
1183 // then bring g_ij onto g'_ij and rewrite
1184 transferOnto(hrnSummary, hrnShadowSummary);
1186 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1187 hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1189 // shadow nodes only are touched by a rewrite one time,
1190 // so rewrite and immediately commit--and they don't belong
1191 // to a particular parameter, so use a bogus param index
1192 // that pulls a self-rewrite out of H
1193 rewriteCallerNodeAlpha(fm.numParameters(),
1196 paramIndex2rewriteH,
1197 paramIndex2rewriteD,
1198 paramIndex2paramToken,
1199 paramIndex2paramTokenStar);
1201 hrnShadowSummary.applyAlphaNew();
1204 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1205 Integer idIth = allocSite.getIthOldest(i);
1206 assert id2hrn.containsKey(idIth);
1207 HeapRegionNode hrnIth = id2hrn.get(idIth);
1209 Integer idShadowIth = -(allocSite.getIthOldest(i));
1210 assert id2hrn.containsKey(idShadowIth);
1211 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1212 assert hrnIthShadow.getNumReferencers() == 0;
1213 assert hrnIthShadow.getNumReferencees() == 0;
1215 transferOnto(hrnIth, hrnIthShadow);
1217 assert ogCallee.id2hrn.containsKey(idIth);
1218 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1219 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1221 rewriteCallerNodeAlpha(fm.numParameters(),
1224 paramIndex2rewriteH,
1225 paramIndex2rewriteD,
1226 paramIndex2paramToken,
1227 paramIndex2paramTokenStar);
1229 hrnIthShadow.applyAlphaNew();
1234 // for every heap region->heap region edge in the
1235 // callee graph, create the matching edge or edges
1236 // in the caller graph
1237 Set sCallee = ogCallee.id2hrn.entrySet();
1238 Iterator iCallee = sCallee.iterator();
1239 while( iCallee.hasNext() ) {
1240 Map.Entry meCallee = (Map.Entry)iCallee.next();
1241 Integer idCallee = (Integer) meCallee.getKey();
1242 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1244 Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1245 while( heapRegionsItrCallee.hasNext() ) {
1246 ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
1247 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1248 Integer idChildCallee = hrnChildCallee.getID();
1250 // only address this edge if it is not a special reflexive edge
1251 if( !edgeCallee.isInitialParamReflexive() ) {
1253 // now we know that in the callee method's ownership graph
1254 // there is a heap region->heap region reference edge given
1255 // by heap region pointers:
1256 // hrnCallee -> heapChildCallee
1258 // or by the ownership-graph independent ID's:
1259 // idCallee -> idChildCallee
1261 // make the edge with src and dst so beta info is
1262 // calculated once, then copy it for each new edge in caller
1263 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1265 edgeCallee.getFieldDesc(),
1267 toShadowTokens(ogCallee, edgeCallee.getBeta() )
1269 rewriteCallerEdgeBeta(fm.numParameters(),
1271 edgeNewInCallerTemplate,
1272 paramIndex2rewriteJ,
1273 paramIndex2rewriteD,
1274 paramIndex2paramToken,
1275 paramIndex2paramTokenStar,
1279 edgeNewInCallerTemplate.applyBetaNew();
1282 // So now make a set of possible source heaps in the caller graph
1283 // and a set of destination heaps in the caller graph, and make
1284 // a reference edge in the caller for every possible (src,dst) pair
1285 HashSet<HeapRegionNode> possibleCallerSrcs =
1286 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1287 (HeapRegionNode) edgeCallee.getSrc(),
1288 paramIndex2reachableCallerNodes);
1290 HashSet<HeapRegionNode> possibleCallerDsts =
1291 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1292 edgeCallee.getDst(),
1293 paramIndex2reachableCallerNodes);
1296 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1297 Iterator srcItr = possibleCallerSrcs.iterator();
1298 while( srcItr.hasNext() ) {
1299 HeapRegionNode src = (HeapRegionNode) srcItr.next();
1301 // check that if this source node has a definite type that
1302 // it also has the appropriate field, otherwise prune this
1303 AllocationSite asSrc = src.getAllocationSite();
1304 if( asSrc != null ) {
1305 boolean foundField = false;
1306 TypeDescriptor tdSrc = asSrc.getType();
1307 if( tdSrc != null && tdSrc.isClass() ) {
1308 Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
1309 while( fieldsSrcItr.hasNext() ) {
1310 FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1311 if( fd == edgeCallee.getFieldDesc() ) {
1317 // prune this source node possibility
1323 Iterator dstItr = possibleCallerDsts.iterator();
1324 while( dstItr.hasNext() ) {
1325 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1327 // check if this dst node has a definite type and
1328 // if it matches the callee edge
1329 AllocationSite asDst = dst.getAllocationSite();
1330 if( asDst != null && edgeCallee.getFieldDesc() != null ) {
1331 if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) {
1334 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) {
1337 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
1338 if( !asDst.getType().equals(edgeCallee.getFieldDesc().getType() ) ) {
1344 // otherwise the caller src and dst pair can match the edge, so make it
1345 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1346 edgeNewInCaller.setSrc(src);
1347 edgeNewInCaller.setDst(dst);
1349 ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1350 if( edgeExisting == null ) {
1351 // if this edge doesn't exist in the caller, create it
1352 addReferenceEdge(src, dst, edgeNewInCaller);
1354 // if it already exists, merge with it
1355 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1365 // return value may need to be assigned in caller
1366 if( fc.getReturnTemp() != null ) {
1368 LabelNode lnLhsCaller = getLabelNodeFromTemp(fc.getReturnTemp() );
1369 clearReferenceEdgesFrom(lnLhsCaller, null, true);
1371 LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1372 Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1373 while( edgeCalleeItr.hasNext() ) {
1374 ReferenceEdge edgeCallee = edgeCalleeItr.next();
1376 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1378 edgeCallee.getFieldDesc(),
1380 toShadowTokens(ogCallee, edgeCallee.getBeta() )
1382 rewriteCallerEdgeBeta(fm.numParameters(),
1384 edgeNewInCallerTemplate,
1385 paramIndex2rewriteJ,
1386 paramIndex2rewriteD,
1387 paramIndex2paramToken,
1388 paramIndex2paramTokenStar,
1392 edgeNewInCallerTemplate.applyBetaNew();
1395 HashSet<HeapRegionNode> assignCallerRhs =
1396 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1397 edgeCallee.getDst(),
1398 paramIndex2reachableCallerNodes);
1400 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1401 while( itrHrn.hasNext() ) {
1402 HeapRegionNode hrnCaller = itrHrn.next();
1404 // check if this dst node has a definite type and
1405 // if it matches the callee edge
1406 // check if this dst node has a definite type and
1407 // if it matches the callee edge
1408 AllocationSite asDst = hrnCaller.getAllocationSite();
1409 if( asDst != null && edgeCallee.getFieldDesc() != null ) {
1410 if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) {
1413 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) {
1416 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
1417 if( !asDst.getType().equals(edgeCallee.getFieldDesc().getType() ) ) {
1423 // otherwise caller node can match callee edge, so make it
1424 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1425 edgeNewInCaller.setSrc(lnLhsCaller);
1426 edgeNewInCaller.setDst(hrnCaller);
1428 ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1429 if( edgeExisting == null ) {
1430 // if this edge doesn't exist in the caller, create it
1431 addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1433 // if it already exists, merge with it
1434 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1442 // merge the shadow nodes of allocation sites back down to normal capacity
1443 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1444 while( allocItr.hasNext() ) {
1445 AllocationSite as = allocItr.next();
1447 // first age each allocation site enough times to make room for the shadow nodes
1448 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1452 // then merge the shadow summary into the normal summary
1453 HeapRegionNode hrnSummary = getSummaryNode(as);
1454 assert hrnSummary != null;
1456 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1457 assert hrnSummaryShadow != null;
1459 mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1461 // then clear off after merge
1462 clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1463 clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1464 hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1466 // then transplant shadow nodes onto the now clean normal nodes
1467 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1469 Integer idIth = as.getIthOldest(i);
1470 HeapRegionNode hrnIth = id2hrn.get(idIth);
1472 Integer idIthShadow = as.getIthOldestShadow(i);
1473 HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1475 transferOnto(hrnIthShadow, hrnIth);
1477 // clear off shadow nodes after transfer
1478 clearReferenceEdgesFrom(hrnIthShadow, null, true);
1479 clearReferenceEdgesTo(hrnIthShadow, null, true);
1480 hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1483 // finally, globally change shadow tokens into normal tokens
1484 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1485 while( itrAllLabelNodes.hasNext() ) {
1486 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1487 LabelNode ln = (LabelNode) me.getValue();
1489 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1490 while( itrEdges.hasNext() ) {
1491 unshadowTokens(as, itrEdges.next() );
1495 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1496 while( itrAllHRNodes.hasNext() ) {
1497 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1498 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1500 unshadowTokens(as, hrnToAge);
1502 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1503 while( itrEdges.hasNext() ) {
1504 unshadowTokens(as, itrEdges.next() );
1511 protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1512 edge.setBeta(edge.getBeta().unshadowTokens(as) );
1515 protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1516 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1520 private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1521 ReachabilitySet rsIn) {
1523 ReachabilitySet rsOut = new ReachabilitySet(rsIn);
1525 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1526 while( allocItr.hasNext() ) {
1527 AllocationSite as = allocItr.next();
1529 rsOut = rsOut.toShadowTokens(as);
1532 return rsOut.makeCanonical();
1536 private void rewriteCallerNodeAlpha(int numParameters,
1539 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
1540 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1541 Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1542 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1544 ReachabilitySet rules = paramIndex2rewriteH.get(paramIndex);
1545 assert rules != null;
1547 TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1548 assert tokenToRewrite != null;
1550 ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
1551 Iterator<TokenTupleSet> ttsItr = rules.iterator();
1552 while( ttsItr.hasNext() ) {
1553 TokenTupleSet tts = ttsItr.next();
1554 r0 = r0.union(tts.rewriteToken(tokenToRewrite,
1560 ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1561 ttsItr = r0.iterator();
1562 while( ttsItr.hasNext() ) {
1563 TokenTupleSet tts = ttsItr.next();
1564 r1 = r1.union(rewriteDpass(numParameters,
1567 paramIndex2rewriteD,
1568 paramIndex2paramToken,
1569 paramIndex2paramTokenStar) );
1572 hrn.setAlphaNew(hrn.getAlphaNew().union(r1) );
1576 private void rewriteCallerEdgeBeta(int numParameters,
1579 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJorK,
1580 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1581 Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1582 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar,
1583 boolean makeChangeSet,
1584 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1586 ReachabilitySet rules = paramIndex2rewriteJorK.get(paramIndex);
1587 assert rules != null;
1589 TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1590 assert tokenToRewrite != null;
1592 ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
1594 Iterator<TokenTupleSet> ttsItr = rules.iterator();
1595 while( ttsItr.hasNext() ) {
1596 TokenTupleSet tts = ttsItr.next();
1598 Hashtable<TokenTupleSet, TokenTupleSet> forChangeSet =
1599 new Hashtable<TokenTupleSet, TokenTupleSet>();
1601 ReachabilitySet rTemp = tts.rewriteToken(tokenToRewrite,
1606 Iterator fcsItr = forChangeSet.entrySet().iterator();
1607 while( fcsItr.hasNext() ) {
1608 Map.Entry me = (Map.Entry)fcsItr.next();
1609 TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey();
1610 TokenTupleSet ttsAdd = (TokenTupleSet) me.getValue();
1612 ChangeTuple ct = new ChangeTuple(ttsMatch,
1616 cts0 = cts0.union(ct);
1621 ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1622 ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical();
1624 Iterator<ChangeTuple> ctItr = cts0.iterator();
1625 while( ctItr.hasNext() ) {
1626 ChangeTuple ct = ctItr.next();
1628 ReachabilitySet rTemp = rewriteDpass(numParameters,
1631 paramIndex2rewriteD,
1632 paramIndex2paramToken,
1633 paramIndex2paramTokenStar
1635 r1 = r1.union(rTemp);
1637 if( makeChangeSet ) {
1638 assert edgePlannedChanges != null;
1640 Iterator<TokenTupleSet> ttsTempItr = rTemp.iterator();
1641 while( ttsTempItr.hasNext() ) {
1642 TokenTupleSet tts = ttsTempItr.next();
1644 ChangeTuple ctFinal = new ChangeTuple(ct.getSetToMatch(),
1648 cts1 = cts1.union(ctFinal);
1653 if( makeChangeSet ) {
1654 edgePlannedChanges.put(edge, cts1);
1657 edge.setBetaNew(edge.getBetaNew().union(r1) );
1661 private ReachabilitySet rewriteDpass(int numParameters,
1663 TokenTupleSet ttsIn,
1664 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1665 Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1666 Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1668 ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
1670 boolean rewritten = false;
1672 for( int j = 0; j < numParameters; ++j ) {
1673 Integer paramIndexJ = new Integer(j);
1674 ReachabilitySet D_j = paramIndex2rewriteD.get(paramIndexJ);
1677 if( paramIndexJ != paramIndex ) {
1678 TokenTuple tokenToRewriteJ = paramIndex2paramToken.get(paramIndexJ);
1679 assert tokenToRewriteJ != null;
1680 if( ttsIn.containsTuple(tokenToRewriteJ) ) {
1681 ReachabilitySet r = ttsIn.rewriteToken(tokenToRewriteJ,
1685 Iterator<TokenTupleSet> ttsItr = r.iterator();
1686 while( ttsItr.hasNext() ) {
1687 TokenTupleSet tts = ttsItr.next();
1688 rsOut = rsOut.union(rewriteDpass(numParameters,
1691 paramIndex2rewriteD,
1692 paramIndex2paramToken,
1693 paramIndex2paramTokenStar) );
1699 TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get(paramIndexJ);
1700 assert tokenStarToRewriteJ != null;
1701 if( ttsIn.containsTuple(tokenStarToRewriteJ) ) {
1702 ReachabilitySet r = ttsIn.rewriteToken(tokenStarToRewriteJ,
1706 Iterator<TokenTupleSet> ttsItr = r.iterator();
1707 while( ttsItr.hasNext() ) {
1708 TokenTupleSet tts = ttsItr.next();
1709 rsOut = rsOut.union(rewriteDpass(numParameters,
1712 paramIndex2rewriteD,
1713 paramIndex2paramToken,
1714 paramIndex2paramTokenStar) );
1721 rsOut = rsOut.union(ttsIn);
1728 private HashSet<HeapRegionNode>
1729 getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1730 HeapRegionNode hrnCallee,
1731 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1734 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1736 Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
1738 if( paramIndexCallee == null ) {
1739 // this is a node allocated in the callee then and it has
1740 // exactly one shadow node in the caller to map to
1741 AllocationSite as = hrnCallee.getAllocationSite();
1744 int age = as.getAgeCategory(hrnCallee.getID() );
1745 assert age != AllocationSite.AGE_notInThisSite;
1748 if( age == AllocationSite.AGE_summary ) {
1749 idCaller = as.getSummaryShadow();
1750 } else if( age == AllocationSite.AGE_oldest ) {
1751 idCaller = as.getOldestShadow();
1753 assert age == AllocationSite.AGE_in_I;
1755 Integer I = as.getAge(hrnCallee.getID() );
1758 idCaller = as.getIthOldestShadow(I);
1761 assert id2hrn.containsKey(idCaller);
1762 HeapRegionNode hrnCaller = id2hrn.get(idCaller);
1763 possibleCallerHRNs.add(hrnCaller);
1766 // this is a node that was created to represent a parameter
1767 // so it maps to a whole mess of heap regions
1768 assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
1769 possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
1772 return possibleCallerHRNs;
1777 ////////////////////////////////////////////////////
1778 // in merge() and equals() methods the suffix A
1779 // represents the passed in graph and the suffix
1780 // B refers to the graph in this object
1781 // Merging means to take the incoming graph A and
1782 // merge it into B, so after the operation graph B
1783 // is the final result.
1784 ////////////////////////////////////////////////////
1785 public void merge(OwnershipGraph og) {
1791 mergeOwnershipNodes(og);
1792 mergeReferenceEdges(og);
1793 mergeId2paramIndex(og);
1794 mergeAllocationSites(og);
1798 protected void mergeOwnershipNodes(OwnershipGraph og) {
1799 Set sA = og.id2hrn.entrySet();
1800 Iterator iA = sA.iterator();
1801 while( iA.hasNext() ) {
1802 Map.Entry meA = (Map.Entry)iA.next();
1803 Integer idA = (Integer) meA.getKey();
1804 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1806 // if this graph doesn't have a node the
1807 // incoming graph has, allocate it
1808 if( !id2hrn.containsKey(idA) ) {
1809 HeapRegionNode hrnB = hrnA.copy();
1810 id2hrn.put(idA, hrnB);
1813 // otherwise this is a node present in both graphs
1814 // so make the new reachability set a union of the
1815 // nodes' reachability sets
1816 HeapRegionNode hrnB = id2hrn.get(idA);
1817 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1821 // now add any label nodes that are in graph B but
1823 sA = og.td2ln.entrySet();
1825 while( iA.hasNext() ) {
1826 Map.Entry meA = (Map.Entry)iA.next();
1827 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1828 LabelNode lnA = (LabelNode) meA.getValue();
1830 // if the label doesn't exist in B, allocate and add it
1831 LabelNode lnB = getLabelNodeFromTemp(tdA);
1835 protected void mergeReferenceEdges(OwnershipGraph og) {
1838 Set sA = og.id2hrn.entrySet();
1839 Iterator iA = sA.iterator();
1840 while( iA.hasNext() ) {
1841 Map.Entry meA = (Map.Entry)iA.next();
1842 Integer idA = (Integer) meA.getKey();
1843 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1845 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1846 while( heapRegionsItrA.hasNext() ) {
1847 ReferenceEdge edgeA = heapRegionsItrA.next();
1848 HeapRegionNode hrnChildA = edgeA.getDst();
1849 Integer idChildA = hrnChildA.getID();
1851 // at this point we know an edge in graph A exists
1852 // idA -> idChildA, does this exist in B?
1853 assert id2hrn.containsKey(idA);
1854 HeapRegionNode hrnB = id2hrn.get(idA);
1855 ReferenceEdge edgeToMerge = null;
1857 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1858 while( heapRegionsItrB.hasNext() &&
1859 edgeToMerge == null ) {
1861 ReferenceEdge edgeB = heapRegionsItrB.next();
1862 HeapRegionNode hrnChildB = edgeB.getDst();
1863 Integer idChildB = hrnChildB.getID();
1865 // don't use the ReferenceEdge.equals() here because
1866 // we're talking about existence between graphs
1867 if( idChildB.equals(idChildA) &&
1868 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1869 edgeToMerge = edgeB;
1873 // if the edge from A was not found in B,
1875 if( edgeToMerge == null ) {
1876 assert id2hrn.containsKey(idChildA);
1877 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1878 edgeToMerge = edgeA.copy();
1879 edgeToMerge.setSrc(hrnB);
1880 edgeToMerge.setDst(hrnChildB);
1881 addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1883 // otherwise, the edge already existed in both graphs
1884 // so merge their reachability sets
1886 // just replace this beta set with the union
1887 assert edgeToMerge != null;
1888 edgeToMerge.setBeta(
1889 edgeToMerge.getBeta().union(edgeA.getBeta() )
1891 if( !edgeA.isInitialParamReflexive() ) {
1892 edgeToMerge.setIsInitialParamReflexive(false);
1898 // and then again with label nodes
1899 sA = og.td2ln.entrySet();
1901 while( iA.hasNext() ) {
1902 Map.Entry meA = (Map.Entry)iA.next();
1903 TempDescriptor tdA = (TempDescriptor) meA.getKey();
1904 LabelNode lnA = (LabelNode) meA.getValue();
1906 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1907 while( heapRegionsItrA.hasNext() ) {
1908 ReferenceEdge edgeA = heapRegionsItrA.next();
1909 HeapRegionNode hrnChildA = edgeA.getDst();
1910 Integer idChildA = hrnChildA.getID();
1912 // at this point we know an edge in graph A exists
1913 // tdA -> idChildA, does this exist in B?
1914 assert td2ln.containsKey(tdA);
1915 LabelNode lnB = td2ln.get(tdA);
1916 ReferenceEdge edgeToMerge = null;
1918 // labels never have edges with a field
1919 //assert edgeA.getFieldDesc() == null;
1921 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1922 while( heapRegionsItrB.hasNext() &&
1923 edgeToMerge == null ) {
1925 ReferenceEdge edgeB = heapRegionsItrB.next();
1926 HeapRegionNode hrnChildB = edgeB.getDst();
1927 Integer idChildB = hrnChildB.getID();
1929 // labels never have edges with a field
1930 //assert edgeB.getFieldDesc() == null;
1932 // don't use the ReferenceEdge.equals() here because
1933 // we're talking about existence between graphs
1934 if( idChildB.equals(idChildA) &&
1935 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1936 edgeToMerge = edgeB;
1940 // if the edge from A was not found in B,
1942 if( edgeToMerge == null ) {
1943 assert id2hrn.containsKey(idChildA);
1944 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1945 edgeToMerge = edgeA.copy();
1946 edgeToMerge.setSrc(lnB);
1947 edgeToMerge.setDst(hrnChildB);
1948 addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1950 // otherwise, the edge already existed in both graphs
1951 // so merge their reachability sets
1953 // just replace this beta set with the union
1954 edgeToMerge.setBeta(
1955 edgeToMerge.getBeta().union(edgeA.getBeta() )
1957 if( !edgeA.isInitialParamReflexive() ) {
1958 edgeToMerge.setIsInitialParamReflexive(false);
1965 // you should only merge ownership graphs that have the
1966 // same number of parameters, or if one or both parameter
1967 // index tables are empty
1968 protected void mergeId2paramIndex(OwnershipGraph og) {
1969 if( id2paramIndex.size() == 0 ) {
1970 id2paramIndex = og.id2paramIndex;
1971 paramIndex2id = og.paramIndex2id;
1972 paramIndex2tdQ = og.paramIndex2tdQ;
1976 if( og.id2paramIndex.size() == 0 ) {
1980 assert id2paramIndex.size() == og.id2paramIndex.size();
1983 protected void mergeAllocationSites(OwnershipGraph og) {
1984 allocationSites.addAll(og.allocationSites);
1989 // it is necessary in the equals() member functions
1990 // to "check both ways" when comparing the data
1991 // structures of two graphs. For instance, if all
1992 // edges between heap region nodes in graph A are
1993 // present and equal in graph B it is not sufficient
1994 // to say the graphs are equal. Consider that there
1995 // may be edges in graph B that are not in graph A.
1996 // the only way to know that all edges in both graphs
1997 // are equally present is to iterate over both data
1998 // structures and compare against the other graph.
1999 public boolean equals(OwnershipGraph og) {
2005 if( !areHeapRegionNodesEqual(og) ) {
2009 if( !areLabelNodesEqual(og) ) {
2013 if( !areReferenceEdgesEqual(og) ) {
2017 if( !areId2paramIndexEqual(og) ) {
2021 // if everything is equal up to this point,
2022 // assert that allocationSites is also equal--
2023 // this data is redundant and kept for efficiency
2024 assert allocationSites.equals(og.allocationSites);
2029 protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2031 if( !areallHRNinAalsoinBandequal(this, og) ) {
2035 if( !areallHRNinAalsoinBandequal(og, this) ) {
2042 static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2043 OwnershipGraph ogB) {
2044 Set sA = ogA.id2hrn.entrySet();
2045 Iterator iA = sA.iterator();
2046 while( iA.hasNext() ) {
2047 Map.Entry meA = (Map.Entry)iA.next();
2048 Integer idA = (Integer) meA.getKey();
2049 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2051 if( !ogB.id2hrn.containsKey(idA) ) {
2055 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2056 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2065 protected boolean areLabelNodesEqual(OwnershipGraph og) {
2067 if( !areallLNinAalsoinBandequal(this, og) ) {
2071 if( !areallLNinAalsoinBandequal(og, this) ) {
2078 static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2079 OwnershipGraph ogB) {
2080 Set sA = ogA.td2ln.entrySet();
2081 Iterator iA = sA.iterator();
2082 while( iA.hasNext() ) {
2083 Map.Entry meA = (Map.Entry)iA.next();
2084 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2086 if( !ogB.td2ln.containsKey(tdA) ) {
2095 protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2096 if( !areallREinAandBequal(this, og) ) {
2103 static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2104 OwnershipGraph ogB) {
2106 // check all the heap region->heap region edges
2107 Set sA = ogA.id2hrn.entrySet();
2108 Iterator iA = sA.iterator();
2109 while( iA.hasNext() ) {
2110 Map.Entry meA = (Map.Entry)iA.next();
2111 Integer idA = (Integer) meA.getKey();
2112 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2114 // we should have already checked that the same
2115 // heap regions exist in both graphs
2116 assert ogB.id2hrn.containsKey(idA);
2118 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2122 // then check every edge in B for presence in A, starting
2123 // from the same parent HeapRegionNode
2124 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2126 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2131 // then check all the label->heap region edges
2132 sA = ogA.td2ln.entrySet();
2134 while( iA.hasNext() ) {
2135 Map.Entry meA = (Map.Entry)iA.next();
2136 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2137 LabelNode lnA = (LabelNode) meA.getValue();
2139 // we should have already checked that the same
2140 // label nodes exist in both graphs
2141 assert ogB.td2ln.containsKey(tdA);
2143 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2147 // then check every edge in B for presence in A, starting
2148 // from the same parent LabelNode
2149 LabelNode lnB = ogB.td2ln.get(tdA);
2151 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2160 static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2162 OwnershipGraph ogB) {
2164 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2165 while( itrA.hasNext() ) {
2166 ReferenceEdge edgeA = itrA.next();
2167 HeapRegionNode hrnChildA = edgeA.getDst();
2168 Integer idChildA = hrnChildA.getID();
2170 assert ogB.id2hrn.containsKey(idChildA);
2172 // at this point we know an edge in graph A exists
2173 // onA -> idChildA, does this exact edge exist in B?
2174 boolean edgeFound = false;
2176 OwnershipNode onB = null;
2177 if( onA instanceof HeapRegionNode ) {
2178 HeapRegionNode hrnA = (HeapRegionNode) onA;
2179 onB = ogB.id2hrn.get(hrnA.getID() );
2181 LabelNode lnA = (LabelNode) onA;
2182 onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2185 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2186 while( itrB.hasNext() ) {
2187 ReferenceEdge edgeB = itrB.next();
2188 HeapRegionNode hrnChildB = edgeB.getDst();
2189 Integer idChildB = hrnChildB.getID();
2191 if( idChildA.equals(idChildB) &&
2192 edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2194 // there is an edge in the right place with the right field,
2195 // but do they have the same attributes?
2196 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2214 protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2215 return id2paramIndex.size() == og.id2paramIndex.size();
2219 public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
2221 // get parameter's heap region
2222 assert paramIndex2id.containsKey(paramIndex1);
2223 Integer idParam1 = paramIndex2id.get(paramIndex1);
2225 assert id2hrn.containsKey(idParam1);
2226 HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2227 assert hrnParam1 != null;
2229 // get tokens for this parameter
2230 TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2232 TokenTuple.ARITY_ONE).makeCanonical();
2234 TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2236 TokenTuple.ARITY_MANY).makeCanonical();
2239 // get tokens for the other parameter
2240 assert paramIndex2id.containsKey(paramIndex2);
2241 Integer idParam2 = paramIndex2id.get(paramIndex2);
2243 assert id2hrn.containsKey(idParam2);
2244 HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2245 assert hrnParam2 != null;
2247 TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2249 TokenTuple.ARITY_ONE).makeCanonical();
2251 TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2253 TokenTuple.ARITY_MANY).makeCanonical();
2256 // get special label p_q for first parameter
2257 TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2258 assert tdParamQ1 != null;
2259 LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2260 assert lnParamQ1 != null;
2262 // then get the edge from label q to parameter's hrn
2263 ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2264 assert edgeSpecialQ1 != null;
2266 // if the beta of this edge has tokens from both parameters in one
2267 // token tuple set, then there is a potential alias between them
2268 ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2269 assert beta1 != null;
2271 if( beta1.containsTupleSetWithBoth(p1, p2) ) {
2274 if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
2277 if( beta1.containsTupleSetWithBoth(p1, pStar2) ) {
2280 if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
2288 public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
2290 // get parameter's heap region
2291 assert paramIndex2id.containsKey(paramIndex);
2292 Integer idParam = paramIndex2id.get(paramIndex);
2294 assert id2hrn.containsKey(idParam);
2295 HeapRegionNode hrnParam = id2hrn.get(idParam);
2296 assert hrnParam != null;
2298 // get tokens for this parameter
2299 TokenTuple p = new TokenTuple(hrnParam.getID(),
2301 TokenTuple.ARITY_ONE).makeCanonical();
2303 TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2305 TokenTuple.ARITY_MANY).makeCanonical();
2307 // get special label p_q
2308 TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2309 assert tdParamQ != null;
2310 LabelNode lnParamQ = td2ln.get(tdParamQ);
2311 assert lnParamQ != null;
2313 // then get the edge from label q to parameter's hrn
2314 ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2315 assert edgeSpecialQ != null;
2317 // look through this beta set for potential aliases
2318 ReachabilitySet beta = edgeSpecialQ.getBeta();
2319 assert beta != null;
2322 // get tokens for summary node
2323 TokenTuple gs = new TokenTuple(as.getSummary(),
2325 TokenTuple.ARITY_ONE).makeCanonical();
2327 TokenTuple gsStar = new TokenTuple(as.getSummary(),
2329 TokenTuple.ARITY_MANY).makeCanonical();
2331 if( beta.containsTupleSetWithBoth(p, gs) ) {
2334 if( beta.containsTupleSetWithBoth(pStar, gs) ) {
2337 if( beta.containsTupleSetWithBoth(p, gsStar) ) {
2340 if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
2344 // check for other nodes
2345 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2347 // the other nodes of an allocation site are single, no stars
2348 TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2350 TokenTuple.ARITY_ONE).makeCanonical();
2352 if( beta.containsTupleSetWithBoth(p, gi) ) {
2355 if( beta.containsTupleSetWithBoth(pStar, gi) ) {
2364 public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
2366 // get tokens for summary nodes
2367 TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2369 TokenTuple.ARITY_ONE).makeCanonical();
2371 TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2373 TokenTuple.ARITY_MANY).makeCanonical();
2375 // get summary node's alpha
2376 Integer idSum1 = as1.getSummary();
2377 assert id2hrn.containsKey(idSum1);
2378 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
2379 assert hrnSum1 != null;
2380 ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2381 assert alphaSum1 != null;
2384 // and for the other one
2385 TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2387 TokenTuple.ARITY_ONE).makeCanonical();
2389 TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2391 TokenTuple.ARITY_MANY).makeCanonical();
2393 // get summary node's alpha
2394 Integer idSum2 = as2.getSummary();
2395 assert id2hrn.containsKey(idSum2);
2396 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
2397 assert hrnSum2 != null;
2398 ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2399 assert alphaSum2 != null;
2401 // does either one report reachability from the other tokens?
2402 if( alphaSum1.containsTuple(gsStar2) ) {
2405 if( alphaSum2.containsTuple(gsStar1) ) {
2409 // only check non-star token if they are different sites
2411 if( alphaSum1.containsTuple(gs2) ) {
2414 if( alphaSum2.containsTuple(gs1) ) {
2420 // check sum2 against alloc1 nodes
2421 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2422 Integer idI1 = as1.getIthOldest(i);
2423 assert id2hrn.containsKey(idI1);
2424 HeapRegionNode hrnI1 = id2hrn.get(idI1);
2425 assert hrnI1 != null;
2426 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2427 assert alphaI1 != null;
2429 // the other nodes of an allocation site are single, no stars
2430 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2432 TokenTuple.ARITY_ONE).makeCanonical();
2434 if( alphaSum2.containsTuple(gi1) ) {
2437 if( alphaI1.containsTuple(gs2) ) {
2440 if( alphaI1.containsTuple(gsStar2) ) {
2445 // check sum1 against alloc2 nodes
2446 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2447 Integer idI2 = as2.getIthOldest(i);
2448 assert id2hrn.containsKey(idI2);
2449 HeapRegionNode hrnI2 = id2hrn.get(idI2);
2450 assert hrnI2 != null;
2451 ReachabilitySet alphaI2 = hrnI2.getAlpha();
2452 assert alphaI2 != null;
2454 TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2456 TokenTuple.ARITY_ONE).makeCanonical();
2458 if( alphaSum1.containsTuple(gi2) ) {
2461 if( alphaI2.containsTuple(gs1) ) {
2464 if( alphaI2.containsTuple(gsStar1) ) {
2468 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
2469 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
2470 Integer idI1 = as1.getIthOldest(j);
2472 // if these are the same site, don't look for the same token, no alias
2473 // different tokens of the same site could alias together though
2474 if( idI1 == idI2 ) {
2478 HeapRegionNode hrnI1 = id2hrn.get(idI1);
2479 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2480 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
2482 TokenTuple.ARITY_ONE).makeCanonical();
2483 if( alphaI2.containsTuple(gi1) ) {
2486 if( alphaI1.containsTuple(gi2) ) {
2496 // for writing ownership graphs to dot files
2497 public void writeGraph(Descriptor methodDesc,
2499 boolean writeLabels,
2500 boolean labelSelect,
2501 boolean pruneGarbage,
2502 boolean writeReferencers
2503 ) throws java.io.IOException {
2505 methodDesc.getSymbol() +
2506 methodDesc.getNum() +
2515 public void writeGraph(Descriptor methodDesc,
2516 boolean writeLabels,
2517 boolean labelSelect,
2518 boolean pruneGarbage,
2519 boolean writeReferencers
2520 ) throws java.io.IOException {
2522 writeGraph(methodDesc+"COMPLETE",
2530 public void writeGraph(Descriptor methodDesc,
2532 boolean writeLabels,
2533 boolean labelSelect,
2534 boolean pruneGarbage,
2535 boolean writeReferencers
2536 ) throws java.io.IOException {
2538 writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
2546 public void writeGraph(String graphName,
2547 boolean writeLabels,
2548 boolean labelSelect,
2549 boolean pruneGarbage,
2550 boolean writeReferencers
2551 ) throws java.io.IOException {
2553 // remove all non-word characters from the graph name so
2554 // the filename and identifier in dot don't cause errors
2555 graphName = graphName.replaceAll("[\\W]", "");
2557 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2558 bw.write("digraph "+graphName+" {\n");
2559 //bw.write( " size=\"7.5,10\";\n" );
2561 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2563 // then visit every heap region node
2564 if( !pruneGarbage ) {
2565 Set s = id2hrn.entrySet();
2566 Iterator i = s.iterator();
2567 while( i.hasNext() ) {
2568 Map.Entry me = (Map.Entry)i.next();
2569 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2570 if( !visited.contains(hrn) ) {
2571 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2581 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
2583 Set df = paramIndex2id.entrySet();
2584 Iterator ih = df.iterator();
2585 while( ih.hasNext() ) {
2586 Map.Entry meh = (Map.Entry)ih.next();
2587 Integer pi = (Integer) meh.getKey();
2588 Integer id = (Integer) meh.getValue();
2589 bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
2592 // then visit every label node, useful for debugging
2594 Set s = td2ln.entrySet();
2595 Iterator i = s.iterator();
2596 while( i.hasNext() ) {
2597 Map.Entry me = (Map.Entry)i.next();
2598 LabelNode ln = (LabelNode) me.getValue();
2601 String labelStr = ln.getTempDescriptorString();
2602 if( labelStr.startsWith("___temp") ||
2603 labelStr.startsWith("___dst") ||
2604 labelStr.startsWith("___srctmp") ||
2605 labelStr.startsWith("___neverused") ) {
2610 bw.write(ln.toString() + ";\n");
2612 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2613 while( heapRegionsItr.hasNext() ) {
2614 ReferenceEdge edge = heapRegionsItr.next();
2615 HeapRegionNode hrn = edge.getDst();
2617 if( pruneGarbage && !visited.contains(hrn) ) {
2618 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2626 bw.write(" " + ln.toString() +
2627 " -> " + hrn.toString() +
2628 "[label=\"" + edge.toGraphEdgeString() +
2639 protected void traverseHeapRegionNodes(int mode,
2643 HashSet<HeapRegionNode> visited,
2644 boolean writeReferencers
2645 ) throws java.io.IOException {
2647 if( visited.contains(hrn) ) {
2653 case VISIT_HRN_WRITE_FULL:
2655 String attributes = "[";
2657 if( hrn.isSingleObject() ) {
2658 attributes += "shape=box";
2660 attributes += "shape=Msquare";
2663 if( hrn.isFlagged() ) {
2664 attributes += ",style=filled,fillcolor=lightgrey";
2667 attributes += ",label=\"ID" +
2670 hrn.getDescription() +
2672 hrn.getAlphaString() +
2675 bw.write(" " + hrn.toString() + attributes + ";\n");
2680 // useful for debugging
2681 if( writeReferencers ) {
2682 OwnershipNode onRef = null;
2683 Iterator refItr = hrn.iteratorToReferencers();
2684 while( refItr.hasNext() ) {
2685 onRef = (OwnershipNode) refItr.next();
2688 case VISIT_HRN_WRITE_FULL:
2689 bw.write(" " + hrn.toString() +
2690 " -> " + onRef.toString() +
2691 "[color=lightgray];\n");
2697 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2698 while( childRegionsItr.hasNext() ) {
2699 ReferenceEdge edge = childRegionsItr.next();
2700 HeapRegionNode hrnChild = edge.getDst();
2703 case VISIT_HRN_WRITE_FULL:
2704 bw.write(" " + hrn.toString() +
2705 " -> " + hrnChild.toString() +
2706 "[label=\"" + edge.toGraphEdgeString() +
2711 traverseHeapRegionNodes(mode,