+ LabelNode lnR = getLabelNodeFromTemp(tdReturn);
+ LabelNode lnX = getLabelNodeFromTemp(x);
+
+ clearReferenceEdgesFrom(lnR, null, true);
+
+ Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
+ while( itrXhrn.hasNext() ) {
+ ReferenceEdge edgeX = itrXhrn.next();
+ HeapRegionNode referencee = edgeX.getDst();
+ ReferenceEdge edgeNew = edgeX.copy();
+ edgeNew.setSrc(lnR);
+
+ addReferenceEdge(lnR, referencee, edgeNew);
+ }
+ }
+
+
+ public void assignTempEqualToNewAlloc(TempDescriptor x,
+ AllocationSite as) {
+ assert x != null;
+ assert as != null;
+
+ age(as);
+
+ // after the age operation the newest (or zero-ith oldest)
+ // node associated with the allocation site should have
+ // no references to it as if it were a newly allocated
+ // heap region, so make a reference to it to complete
+ // this operation
+
+ Integer idNewest = as.getIthOldest(0);
+ HeapRegionNode hrnNewest = id2hrn.get(idNewest);
+ assert hrnNewest != null;
+
+ LabelNode lnX = getLabelNodeFromTemp(x);
+ clearReferenceEdgesFrom(lnX, null, true);
+
+ ReferenceEdge edgeNew =
+ new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
+
+ addReferenceEdge(lnX, hrnNewest, edgeNew);
+ }
+
+
+ // use the allocation site (unique to entire analysis) to
+ // locate the heap region nodes in this ownership graph
+ // that should be aged. The process models the allocation
+ // of new objects and collects all the oldest allocations
+ // in a summary node to allow for a finite analysis
+ //
+ // There is an additional property of this method. After
+ // running it on a particular ownership graph (many graphs
+ // may have heap regions related to the same allocation site)
+ // the heap region node objects in this ownership graph will be
+ // allocated. Therefore, after aging a graph for an allocation
+ // site, attempts to retrieve the heap region nodes using the
+ // integer id's contained in the allocation site should always
+ // return non-null heap regions.
+ public void age(AllocationSite as) {
+
+ // aging adds this allocation site to the graph's
+ // list of sites that exist in the graph, or does
+ // nothing if the site is already in the list
+ allocationSites.add(as);
+
+ // get the summary node for the allocation site in the context
+ // of this particular ownership graph
+ HeapRegionNode hrnSummary = getSummaryNode(as);
+
+ // merge oldest node into summary
+ Integer idK = as.getOldest();
+ HeapRegionNode hrnK = id2hrn.get(idK);
+ mergeIntoSummary(hrnK, hrnSummary);
+
+ // move down the line of heap region nodes
+ // clobbering the ith and transferring all references
+ // to and from i-1 to node i. Note that this clobbers
+ // the oldest node (hrnK) that was just merged into
+ // the summary
+ for( int i = allocationDepth - 1; i > 0; --i ) {
+
+ // move references from the i-1 oldest to the ith oldest
+ Integer idIth = as.getIthOldest(i);
+ HeapRegionNode hrnI = id2hrn.get(idIth);
+ Integer idImin1th = as.getIthOldest(i - 1);
+ HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
+
+ transferOnto(hrnImin1, hrnI);
+ }
+
+ // as stated above, the newest node should have had its
+ // references moved over to the second oldest, so we wipe newest
+ // in preparation for being the new object to assign something to
+ Integer id0th = as.getIthOldest(0);
+ HeapRegionNode hrn0 = id2hrn.get(id0th);
+ assert hrn0 != null;
+
+ // clear all references in and out of newest node
+ clearReferenceEdgesFrom(hrn0, null, true);
+ clearReferenceEdgesTo(hrn0, null, true);
+
+
+ // now tokens in reachability sets need to "age" also
+ Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
+ while( itrAllLabelNodes.hasNext() ) {
+ Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
+ LabelNode ln = (LabelNode) me.getValue();
+
+ Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
+ while( itrEdges.hasNext() ) {
+ ageTokens(as, itrEdges.next() );
+ }
+ }
+
+ Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
+ while( itrAllHRNodes.hasNext() ) {
+ Map.Entry me = (Map.Entry)itrAllHRNodes.next();
+ HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
+
+ ageTokens(as, hrnToAge);
+
+ Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
+ while( itrEdges.hasNext() ) {
+ ageTokens(as, itrEdges.next() );
+ }
+ }
+
+
+ // after tokens have been aged, reset newest node's reachability
+ if( hrn0.isFlagged() ) {
+ hrn0.setAlpha(new ReachabilitySet(
+ new TokenTupleSet(
+ new TokenTuple(hrn0).makeCanonical()
+ ).makeCanonical()
+ ).makeCanonical()
+ );
+ } else {
+ hrn0.setAlpha(new ReachabilitySet(
+ new TokenTupleSet().makeCanonical()
+ ).makeCanonical()
+ );
+ }
+ }
+
+
+ protected HeapRegionNode getSummaryNode(AllocationSite as) {
+
+ Integer idSummary = as.getSummary();
+ HeapRegionNode hrnSummary = id2hrn.get(idSummary);
+
+ // If this is null then we haven't touched this allocation site
+ // in the context of the current ownership graph, so allocate
+ // heap region nodes appropriate for the entire allocation site.
+ // This should only happen once per ownership graph per allocation site,
+ // and a particular integer id can be used to locate the heap region
+ // in different ownership graphs that represents the same part of an
+ // allocation site.
+ if( hrnSummary == null ) {
+
+ boolean hasFlags = false;
+ if( as.getType().isClass() ) {
+ hasFlags = as.getType().getClassDesc().hasFlags();
+ }
+
+ hrnSummary = createNewHeapRegionNode(idSummary,
+ false,
+ hasFlags,
+ true,
+ false,
+ as,
+ null,
+ as + "\\n" + as.getType() + "\\nsummary");
+
+ for( int i = 0; i < as.getAllocationDepth(); ++i ) {
+ Integer idIth = as.getIthOldest(i);
+ assert !id2hrn.containsKey(idIth);
+ createNewHeapRegionNode(idIth,
+ true,
+ hasFlags,
+ false,
+ false,
+ as,
+ null,
+ as + "\\n" + as.getType() + "\\n" + i + " oldest");
+ }
+ }
+
+ return hrnSummary;
+ }
+
+
+ protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
+
+ Integer idShadowSummary = as.getSummaryShadow();
+ HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
+
+ if( hrnShadowSummary == null ) {
+
+ boolean hasFlags = false;
+ if( as.getType().isClass() ) {
+ hasFlags = as.getType().getClassDesc().hasFlags();
+ }
+
+ hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
+ false,
+ hasFlags,
+ true,
+ false,
+ as,
+ null,
+ as + "\\n" + as.getType() + "\\nshadowSum");
+
+ for( int i = 0; i < as.getAllocationDepth(); ++i ) {
+ Integer idShadowIth = as.getIthOldestShadow(i);
+ assert !id2hrn.containsKey(idShadowIth);
+ createNewHeapRegionNode(idShadowIth,
+ true,
+ hasFlags,
+ false,
+ false,
+ as,
+ null,
+ as + "\\n" + as.getType() + "\\n" + i + " shadow");
+ }
+ }
+
+ return hrnShadowSummary;
+ }
+
+
+ protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
+ assert hrnSummary.isNewSummary();
+
+ // transfer references _from_ hrn over to hrnSummary
+ Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
+ while( itrReferencee.hasNext() ) {
+ ReferenceEdge edge = itrReferencee.next();
+ ReferenceEdge edgeMerged = edge.copy();
+ edgeMerged.setSrc(hrnSummary);
+
+ HeapRegionNode hrnReferencee = edge.getDst();
+ ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
+
+ if( edgeSummary == null ) {
+ // the merge is trivial, nothing to be done
+ } else {
+ // otherwise an edge from the referencer to hrnSummary exists already
+ // and the edge referencer->hrn should be merged with it
+ edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
+ }
+
+ addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
+ }
+
+ // next transfer references _to_ hrn over to hrnSummary
+ Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
+ while( itrReferencer.hasNext() ) {
+ ReferenceEdge edge = itrReferencer.next();
+ ReferenceEdge edgeMerged = edge.copy();
+ edgeMerged.setDst(hrnSummary);
+
+ OwnershipNode onReferencer = edge.getSrc();
+ ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
+
+ if( edgeSummary == null ) {
+ // the merge is trivial, nothing to be done
+ } else {
+ // otherwise an edge from the referencer to alpha_S exists already
+ // and the edge referencer->alpha_K should be merged with it
+ edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
+ }
+
+ addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
+ }
+
+ // then merge hrn reachability into hrnSummary
+ hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
+ }
+
+
+ protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
+
+ // clear references in and out of node b
+ clearReferenceEdgesFrom(hrnB, null, true);
+ clearReferenceEdgesTo(hrnB, null, true);
+
+ // copy each edge in and out of A to B
+ Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
+ while( itrReferencee.hasNext() ) {
+ ReferenceEdge edge = itrReferencee.next();
+ HeapRegionNode hrnReferencee = edge.getDst();
+ ReferenceEdge edgeNew = edge.copy();
+ edgeNew.setSrc(hrnB);
+
+ addReferenceEdge(hrnB, hrnReferencee, edgeNew);
+ }
+
+ Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
+ while( itrReferencer.hasNext() ) {
+ ReferenceEdge edge = itrReferencer.next();
+ OwnershipNode onReferencer = edge.getSrc();
+ ReferenceEdge edgeNew = edge.copy();
+ edgeNew.setDst(hrnB);
+
+ addReferenceEdge(onReferencer, hrnB, edgeNew);
+ }
+
+ // replace hrnB reachability with hrnA's
+ hrnB.setAlpha(hrnA.getAlpha() );
+ }