1 package Analysis.OwnershipAnalysis;
8 public class OwnershipGraph {
10 private int allocationDepth;
11 private TypeUtil typeUtil;
13 // there was already one other very similar reason
14 // for traversing heap nodes that is no longer needed
15 // instead of writing a new heap region visitor, use
16 // the existing method with a new mode to describe what
17 // actions to take during the traversal
18 protected static final int VISIT_HRN_WRITE_FULL = 0;
20 protected static TempDescriptor tdReturn = new TempDescriptor("_Return___");
22 protected static final int bogusParamIndexInt = -2;
25 public Hashtable<Integer, HeapRegionNode> id2hrn;
26 public Hashtable<TempDescriptor, LabelNode > td2ln;
27 public Hashtable<Integer, Set<Integer> > id2paramIndexSet;
28 public Hashtable<Integer, Integer > paramIndex2id;
29 public Hashtable<Integer, TempDescriptor> paramIndex2tdQ;
31 public HashSet<AllocationSite> allocationSites;
36 public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
37 this.allocationDepth = allocationDepth;
38 this.typeUtil = typeUtil;
40 id2hrn = new Hashtable<Integer, HeapRegionNode>();
41 td2ln = new Hashtable<TempDescriptor, LabelNode >();
42 id2paramIndexSet = new Hashtable<Integer, Set<Integer> >();
43 paramIndex2id = new Hashtable<Integer, Integer >();
44 paramIndex2tdQ = new Hashtable<Integer, TempDescriptor>();
46 allocationSites = new HashSet <AllocationSite>();
50 // label nodes are much easier to deal with than
51 // heap region nodes. Whenever there is a request
52 // for the label node that is associated with a
53 // temp descriptor we can either find it or make a
54 // new one and return it. This is because temp
55 // descriptors are globally unique and every label
56 // node is mapped to exactly one temp descriptor.
57 protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
60 if( !td2ln.containsKey(td) ) {
61 td2ln.put(td, new LabelNode(td) );
68 // the reason for this method is to have the option
69 // creating new heap regions with specific IDs, or
70 // duplicating heap regions with specific IDs (especially
71 // in the merge() operation) or to create new heap
72 // regions with a new unique ID.
73 protected HeapRegionNode
74 createNewHeapRegionNode(Integer id,
75 boolean isSingleObject,
79 AllocationSite allocSite,
80 ReachabilitySet alpha,
83 boolean markForAnalysis = isFlagged || isParameter;
85 if( allocSite != null && allocSite.getDisjointId() != null ) {
86 markForAnalysis = true;
90 id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
94 if( markForAnalysis ) {
95 alpha = new ReachabilitySet(
102 alpha = new ReachabilitySet(
103 new TokenTupleSet().makeCanonical()
108 HeapRegionNode hrn = new HeapRegionNode(id,
122 ////////////////////////////////////////////////
124 // Low-level referencee and referencer methods
126 // These methods provide the lowest level for
127 // creating references between ownership nodes
128 // and handling the details of maintaining both
129 // list of referencers and referencees.
131 ////////////////////////////////////////////////
132 protected void addReferenceEdge(OwnershipNode referencer,
133 HeapRegionNode referencee,
134 ReferenceEdge edge) {
135 assert referencer != null;
136 assert referencee != null;
138 assert edge.getSrc() == referencer;
139 assert edge.getDst() == referencee;
141 referencer.addReferencee(edge);
142 referencee.addReferencer(edge);
145 protected void removeReferenceEdge(OwnershipNode referencer,
146 HeapRegionNode referencee,
147 FieldDescriptor fieldDesc) {
148 assert referencer != null;
149 assert referencee != null;
151 ReferenceEdge edge = referencer.getReferenceTo(referencee,
154 assert edge == referencee.getReferenceFrom(referencer,
157 referencer.removeReferencee(edge);
158 referencee.removeReferencer(edge);
161 protected void clearReferenceEdgesFrom(OwnershipNode referencer,
162 FieldDescriptor fieldDesc,
164 assert referencer != null;
166 // get a copy of the set to iterate over, otherwise
167 // we will be trying to take apart the set as we
168 // are iterating over it, which won't work
169 Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
170 while( i.hasNext() ) {
171 ReferenceEdge edge = i.next();
173 if( removeAll || edge.getFieldDesc() == fieldDesc ) {
174 HeapRegionNode referencee = edge.getDst();
176 removeReferenceEdge(referencer,
178 edge.getFieldDesc() );
183 protected void clearReferenceEdgesTo(HeapRegionNode referencee,
184 FieldDescriptor fieldDesc,
186 assert referencee != null;
188 // get a copy of the set to iterate over, otherwise
189 // we will be trying to take apart the set as we
190 // are iterating over it, which won't work
191 Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
192 while( i.hasNext() ) {
193 ReferenceEdge edge = i.next();
195 if( removeAll || edge.getFieldDesc() == fieldDesc ) {
196 OwnershipNode referencer = edge.getSrc();
197 removeReferenceEdge(referencer,
199 edge.getFieldDesc() );
205 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
207 HashSet<HeapRegionNode> nodesWithNewAlpha,
208 HashSet<ReferenceEdge> edgesWithNewBeta) {
210 HashSet<HeapRegionNode> todoNodes
211 = new HashSet<HeapRegionNode>();
212 todoNodes.add(nPrime);
214 HashSet<ReferenceEdge> todoEdges
215 = new HashSet<ReferenceEdge>();
217 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
218 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
219 nodePlannedChanges.put(nPrime, c0);
221 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
222 = new Hashtable<ReferenceEdge, ChangeTupleSet>();
225 while( !todoNodes.isEmpty() ) {
226 HeapRegionNode n = todoNodes.iterator().next();
227 ChangeTupleSet C = nodePlannedChanges.get(n);
229 Iterator itrC = C.iterator();
230 while( itrC.hasNext() ) {
231 ChangeTuple c = (ChangeTuple) itrC.next();
233 if( n.getAlpha().contains(c.getSetToMatch() ) ) {
234 ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
235 n.setAlphaNew(n.getAlphaNew().union(withChange) );
236 nodesWithNewAlpha.add(n);
240 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
241 while( referItr.hasNext() ) {
242 ReferenceEdge edge = referItr.next();
245 if( !edgePlannedChanges.containsKey(edge) ) {
246 edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
249 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
252 Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
253 while( refeeItr.hasNext() ) {
254 ReferenceEdge edgeF = refeeItr.next();
255 HeapRegionNode m = edgeF.getDst();
257 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
259 Iterator<ChangeTuple> itrCprime = C.iterator();
260 while( itrCprime.hasNext() ) {
261 ChangeTuple c = itrCprime.next();
262 if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
263 changesToPass = changesToPass.union(c);
267 if( !changesToPass.isEmpty() ) {
268 if( !nodePlannedChanges.containsKey(m) ) {
269 nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
272 ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
274 if( !changesToPass.isSubset(currentChanges) ) {
276 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
285 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
289 protected void propagateTokensOverEdges(
290 HashSet<ReferenceEdge> todoEdges,
291 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
292 HashSet<ReferenceEdge> edgesWithNewBeta) {
295 while( !todoEdges.isEmpty() ) {
296 ReferenceEdge edgeE = todoEdges.iterator().next();
297 todoEdges.remove(edgeE);
299 if( !edgePlannedChanges.containsKey(edgeE) ) {
300 edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
303 ChangeTupleSet C = edgePlannedChanges.get(edgeE);
305 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
307 Iterator<ChangeTuple> itrC = C.iterator();
308 while( itrC.hasNext() ) {
309 ChangeTuple c = itrC.next();
310 if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
311 ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
312 edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
313 edgesWithNewBeta.add(edgeE);
314 changesToPass = changesToPass.union(c);
318 OwnershipNode onSrc = edgeE.getSrc();
320 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
321 HeapRegionNode n = (HeapRegionNode) onSrc;
323 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
324 while( referItr.hasNext() ) {
325 ReferenceEdge edgeF = referItr.next();
327 if( !edgePlannedChanges.containsKey(edgeF) ) {
328 edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
331 ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
333 if( !changesToPass.isSubset(currentChanges) ) {
334 todoEdges.add(edgeF);
335 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
343 ////////////////////////////////////////////////////
345 // Assignment Operation Methods
347 // These methods are high-level operations for
348 // modeling program assignment statements using
349 // the low-level reference create/remove methods
352 // The destination in an assignment statement is
353 // going to have new references. The method of
354 // determining the references depends on the type
355 // of the FlatNode assignment and the predicates
356 // of the nodes and edges involved.
358 ////////////////////////////////////////////////////
359 public void assignTempXEqualToTempY(TempDescriptor x,
362 LabelNode lnX = getLabelNodeFromTemp(x);
363 LabelNode lnY = getLabelNodeFromTemp(y);
365 clearReferenceEdgesFrom(lnX, null, true);
367 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
368 while( itrYhrn.hasNext() ) {
369 ReferenceEdge edgeY = itrYhrn.next();
370 HeapRegionNode referencee = edgeY.getDst();
371 ReferenceEdge edgeNew = edgeY.copy();
374 addReferenceEdge(lnX, referencee, edgeNew);
379 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
382 LabelNode lnX = getLabelNodeFromTemp(x);
383 LabelNode lnY = getLabelNodeFromTemp(y);
385 clearReferenceEdgesFrom(lnX, null, true);
387 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
388 while( itrYhrn.hasNext() ) {
389 ReferenceEdge edgeY = itrYhrn.next();
390 HeapRegionNode hrnY = edgeY.getDst();
391 ReachabilitySet betaY = edgeY.getBeta();
393 Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
394 while( itrHrnFhrn.hasNext() ) {
395 ReferenceEdge edgeHrn = itrHrnFhrn.next();
396 HeapRegionNode hrnHrn = edgeHrn.getDst();
397 ReachabilitySet betaHrn = edgeHrn.getBeta();
399 if( edgeHrn.getFieldDesc() == null ||
400 edgeHrn.getFieldDesc() == f ) {
402 ReferenceEdge edgeNew = new ReferenceEdge(lnX,
406 betaY.intersection(betaHrn) );
408 addReferenceEdge(lnX, hrnHrn, edgeNew);
415 public void assignTempXFieldFEqualToTempY(TempDescriptor x,
418 LabelNode lnX = getLabelNodeFromTemp(x);
419 LabelNode lnY = getLabelNodeFromTemp(y);
421 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
422 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
425 // first look for possible strong updates and remove those edges
426 boolean strongUpdate = false;
428 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
429 while( itrXhrn.hasNext() ) {
430 ReferenceEdge edgeX = itrXhrn.next();
431 HeapRegionNode hrnX = edgeX.getDst();
433 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
434 while( itrYhrn.hasNext() ) {
435 ReferenceEdge edgeY = itrYhrn.next();
436 HeapRegionNode hrnY = edgeY.getDst();
438 // we can do a strong update here if one of two cases holds
440 hrnX.isSingleObject() &&
441 ( (hrnX.getNumReferencers() == 1) ||
442 ( lnX.getNumReferencees() == 1)
446 clearReferenceEdgesFrom( hrnX, f, false );
452 // then do all token propagation
453 itrXhrn = lnX.iteratorToReferencees();
454 while( itrXhrn.hasNext() ) {
455 ReferenceEdge edgeX = itrXhrn.next();
456 HeapRegionNode hrnX = edgeX.getDst();
457 ReachabilitySet betaX = edgeX.getBeta();
459 ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
461 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
462 while( itrYhrn.hasNext() ) {
463 ReferenceEdge edgeY = itrYhrn.next();
464 HeapRegionNode hrnY = edgeY.getDst();
465 ReachabilitySet O = edgeY.getBeta();
468 // propagate tokens over nodes starting from hrnSrc, and it will
469 // take care of propagating back up edges from any touched nodes
470 ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
471 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
474 // then propagate back just up the edges from hrn
475 ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
478 HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
480 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
481 new Hashtable<ReferenceEdge, ChangeTupleSet>();
483 Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
484 while( referItr.hasNext() ) {
485 ReferenceEdge edgeUpstream = referItr.next();
486 todoEdges.add(edgeUpstream);
487 edgePlannedChanges.put(edgeUpstream, Cx);
490 propagateTokensOverEdges(todoEdges,
497 // apply the updates to reachability
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();
509 // then go back through and add the new edges
510 itrXhrn = lnX.iteratorToReferencees();
511 while( itrXhrn.hasNext() ) {
512 ReferenceEdge edgeX = itrXhrn.next();
513 HeapRegionNode hrnX = edgeX.getDst();
515 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
516 while( itrYhrn.hasNext() ) {
517 ReferenceEdge edgeY = itrYhrn.next();
518 HeapRegionNode hrnY = edgeY.getDst();
520 // prepare the new reference edge hrnX.f -> hrnY
521 ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
525 edgeY.getBeta().pruneBy( hrnX.getAlpha() )
528 // look to see if an edge with same field exists
529 // and merge with it, otherwise just add the edge
530 ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
532 if( edgeExisting != null ) {
533 edgeExisting.setBeta(
534 edgeExisting.getBeta().union( edgeNew.getBeta() )
536 // a new edge here cannot be reflexive, so existing will
537 // always be also not reflexive anymore
538 edgeExisting.setIsInitialParamReflexive( false );
540 addReferenceEdge( hrnX, hrnY, edgeNew );
546 // if there was a strong update, make sure to improve
547 // reachability with a global sweep
554 public void assignTempEqualToParamAlloc(TempDescriptor td,
556 Integer paramIndex) {
559 LabelNode lnParam = getLabelNodeFromTemp(td);
560 HeapRegionNode hrn = createNewHeapRegionNode(null,
567 "param" + paramIndex);
569 // this is a non-program-accessible label that picks up beta
570 // info to be used for fixing a caller of this method
571 TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
572 LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
574 // keep track of heap regions that were created for
575 // parameter labels, the index of the parameter they
576 // are for is important when resolving method calls
577 Integer newID = hrn.getID();
578 assert !id2paramIndexSet.containsKey(newID);
579 Set s = new HashSet<Integer>();
581 id2paramIndexSet.put(newID, s);
582 paramIndex2id.put(paramIndex, newID);
583 paramIndex2tdQ.put(paramIndex, tdParamQ);
585 ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
587 TokenTuple.ARITY_ONE).makeCanonical()
590 // heap regions for parameters are always multiple object (see above)
591 // and have a reference to themselves, because we can't know the
592 // structure of memory that is passed into the method. We're assuming
595 ReferenceEdge edgeFromLabel =
596 new ReferenceEdge(lnParam, hrn, null, false, beta);
598 ReferenceEdge edgeFromLabelQ =
599 new ReferenceEdge(lnParamQ, hrn, null, false, beta);
601 ReferenceEdge edgeReflexive =
602 new ReferenceEdge(hrn, hrn, null, true, beta);
604 addReferenceEdge(lnParam, hrn, edgeFromLabel);
605 addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
606 addReferenceEdge(hrn, hrn, edgeReflexive);
609 public void makeAliasedParamHeapRegionNode(TempDescriptor td) {
612 LabelNode lnParam = getLabelNodeFromTemp(td);
613 HeapRegionNode hrn = createNewHeapRegionNode(null,
623 ReachabilitySet beta = new ReachabilitySet(new TokenTuple(hrn.getID(),
625 TokenTuple.ARITY_ONE).makeCanonical()
628 // heap regions for parameters are always multiple object (see above)
629 // and have a reference to themselves, because we can't know the
630 // structure of memory that is passed into the method. We're assuming
633 ReferenceEdge edgeFromLabel =
634 new ReferenceEdge(lnParam, hrn, null, false, beta);
636 ReferenceEdge edgeReflexive =
637 new ReferenceEdge(hrn, hrn, null, true, beta);
639 addReferenceEdge(lnParam, hrn, edgeFromLabel);
640 addReferenceEdge(hrn, hrn, edgeReflexive);
643 public void assignTempEqualToAliasedParam(TempDescriptor tdParam,
644 TempDescriptor tdAliased,
645 Integer paramIndex ) {
647 assert tdParam != null;
648 assert tdAliased != null;
650 LabelNode lnParam = getLabelNodeFromTemp(tdParam);
651 LabelNode lnAliased = getLabelNodeFromTemp(tdAliased);
653 // this is a non-program-accessible label that picks up beta
654 // info to be used for fixing a caller of this method
655 TempDescriptor tdParamQ = new TempDescriptor(tdParam+"specialQ");
656 LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
658 // the lnAliased should always only reference one node, and that
659 // heap region node is the aliased param blob
660 assert lnAliased.getNumReferencees() == 1;
661 HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
663 // keep track of heap regions that were created for
664 // parameter labels, the index of the parameter they
665 // are for is important when resolving method calls
666 Integer idAliased = hrnAliasBlob.getID();
667 Set s = id2paramIndexSet.get( idAliased );
669 s = new HashSet<Integer>();
672 id2paramIndexSet.put(idAliased, s);
673 paramIndex2id.put(paramIndex, idAliased);
674 paramIndex2tdQ.put(paramIndex, tdParamQ);
676 ReachabilitySet beta = new ReachabilitySet(new TokenTuple(idAliased,
678 TokenTuple.ARITY_ONE).makeCanonical()
681 // heap regions for parameters are always multiple object (see above)
682 // and have a reference to themselves, because we can't know the
683 // structure of memory that is passed into the method. We're assuming
686 ReferenceEdge edgeFromLabel =
687 new ReferenceEdge(lnParam, hrnAliasBlob, null, false, beta);
689 ReferenceEdge edgeFromLabelQ =
690 new ReferenceEdge(lnParamQ, hrnAliasBlob, null, false, beta);
692 addReferenceEdge(lnParam, hrnAliasBlob, edgeFromLabel);
693 addReferenceEdge(lnParamQ, hrnAliasBlob, edgeFromLabelQ);
698 public void assignReturnEqualToTemp(TempDescriptor x) {
700 LabelNode lnR = getLabelNodeFromTemp(tdReturn);
701 LabelNode lnX = getLabelNodeFromTemp(x);
703 clearReferenceEdgesFrom(lnR, null, true);
705 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
706 while( itrXhrn.hasNext() ) {
707 ReferenceEdge edgeX = itrXhrn.next();
708 HeapRegionNode referencee = edgeX.getDst();
709 ReferenceEdge edgeNew = edgeX.copy();
712 addReferenceEdge(lnR, referencee, edgeNew);
717 public void assignTempEqualToNewAlloc(TempDescriptor x,
724 // after the age operation the newest (or zero-ith oldest)
725 // node associated with the allocation site should have
726 // no references to it as if it were a newly allocated
727 // heap region, so make a reference to it to complete
730 Integer idNewest = as.getIthOldest(0);
731 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
732 assert hrnNewest != null;
734 LabelNode lnX = getLabelNodeFromTemp(x);
735 clearReferenceEdgesFrom(lnX, null, true);
737 ReferenceEdge edgeNew =
738 new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
740 addReferenceEdge(lnX, hrnNewest, edgeNew);
744 // use the allocation site (unique to entire analysis) to
745 // locate the heap region nodes in this ownership graph
746 // that should be aged. The process models the allocation
747 // of new objects and collects all the oldest allocations
748 // in a summary node to allow for a finite analysis
750 // There is an additional property of this method. After
751 // running it on a particular ownership graph (many graphs
752 // may have heap regions related to the same allocation site)
753 // the heap region node objects in this ownership graph will be
754 // allocated. Therefore, after aging a graph for an allocation
755 // site, attempts to retrieve the heap region nodes using the
756 // integer id's contained in the allocation site should always
757 // return non-null heap regions.
758 public void age(AllocationSite as) {
760 // aging adds this allocation site to the graph's
761 // list of sites that exist in the graph, or does
762 // nothing if the site is already in the list
763 allocationSites.add(as);
765 // get the summary node for the allocation site in the context
766 // of this particular ownership graph
767 HeapRegionNode hrnSummary = getSummaryNode(as);
769 // merge oldest node into summary
770 Integer idK = as.getOldest();
771 HeapRegionNode hrnK = id2hrn.get(idK);
772 mergeIntoSummary(hrnK, hrnSummary);
774 // move down the line of heap region nodes
775 // clobbering the ith and transferring all references
776 // to and from i-1 to node i. Note that this clobbers
777 // the oldest node (hrnK) that was just merged into
779 for( int i = allocationDepth - 1; i > 0; --i ) {
781 // move references from the i-1 oldest to the ith oldest
782 Integer idIth = as.getIthOldest(i);
783 HeapRegionNode hrnI = id2hrn.get(idIth);
784 Integer idImin1th = as.getIthOldest(i - 1);
785 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
787 transferOnto(hrnImin1, hrnI);
790 // as stated above, the newest node should have had its
791 // references moved over to the second oldest, so we wipe newest
792 // in preparation for being the new object to assign something to
793 Integer id0th = as.getIthOldest(0);
794 HeapRegionNode hrn0 = id2hrn.get(id0th);
797 // clear all references in and out of newest node
798 clearReferenceEdgesFrom(hrn0, null, true);
799 clearReferenceEdgesTo(hrn0, null, true);
802 // now tokens in reachability sets need to "age" also
803 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
804 while( itrAllLabelNodes.hasNext() ) {
805 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
806 LabelNode ln = (LabelNode) me.getValue();
808 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
809 while( itrEdges.hasNext() ) {
810 ageTokens(as, itrEdges.next() );
814 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
815 while( itrAllHRNodes.hasNext() ) {
816 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
817 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
819 ageTokens(as, hrnToAge);
821 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
822 while( itrEdges.hasNext() ) {
823 ageTokens(as, itrEdges.next() );
828 // after tokens have been aged, reset newest node's reachability
829 if( hrn0.isFlagged() ) {
830 hrn0.setAlpha(new ReachabilitySet(
832 new TokenTuple(hrn0).makeCanonical()
837 hrn0.setAlpha(new ReachabilitySet(
838 new TokenTupleSet().makeCanonical()
845 protected HeapRegionNode getSummaryNode(AllocationSite as) {
847 Integer idSummary = as.getSummary();
848 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
850 // If this is null then we haven't touched this allocation site
851 // in the context of the current ownership graph, so allocate
852 // heap region nodes appropriate for the entire allocation site.
853 // This should only happen once per ownership graph per allocation site,
854 // and a particular integer id can be used to locate the heap region
855 // in different ownership graphs that represents the same part of an
857 if( hrnSummary == null ) {
859 boolean hasFlags = false;
860 if( as.getType().isClass() ) {
861 hasFlags = as.getType().getClassDesc().hasFlags();
864 hrnSummary = createNewHeapRegionNode(idSummary,
871 as.toStringForDOT() + "\\nsummary");
873 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
874 Integer idIth = as.getIthOldest(i);
875 assert !id2hrn.containsKey(idIth);
876 createNewHeapRegionNode(idIth,
883 as.toStringForDOT() + "\\n" + i + " oldest");
891 protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
893 Integer idShadowSummary = as.getSummaryShadow();
894 HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
896 if( hrnShadowSummary == null ) {
898 boolean hasFlags = false;
899 if( as.getType().isClass() ) {
900 hasFlags = as.getType().getClassDesc().hasFlags();
903 hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
910 as + "\\n" + as.getType() + "\\nshadowSum");
912 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
913 Integer idShadowIth = as.getIthOldestShadow(i);
914 assert !id2hrn.containsKey(idShadowIth);
915 createNewHeapRegionNode(idShadowIth,
922 as + "\\n" + as.getType() + "\\n" + i + " shadow");
926 return hrnShadowSummary;
930 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
931 assert hrnSummary.isNewSummary();
933 // transfer references _from_ hrn over to hrnSummary
934 Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
935 while( itrReferencee.hasNext() ) {
936 ReferenceEdge edge = itrReferencee.next();
937 ReferenceEdge edgeMerged = edge.copy();
938 edgeMerged.setSrc(hrnSummary);
940 HeapRegionNode hrnReferencee = edge.getDst();
941 ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
943 if( edgeSummary == null ) {
944 // the merge is trivial, nothing to be done
946 // otherwise an edge from the referencer to hrnSummary exists already
947 // and the edge referencer->hrn should be merged with it
948 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
951 addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
954 // next transfer references _to_ hrn over to hrnSummary
955 Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
956 while( itrReferencer.hasNext() ) {
957 ReferenceEdge edge = itrReferencer.next();
958 ReferenceEdge edgeMerged = edge.copy();
959 edgeMerged.setDst(hrnSummary);
961 OwnershipNode onReferencer = edge.getSrc();
962 ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
964 if( edgeSummary == null ) {
965 // the merge is trivial, nothing to be done
967 // otherwise an edge from the referencer to alpha_S exists already
968 // and the edge referencer->alpha_K should be merged with it
969 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
972 addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
975 // then merge hrn reachability into hrnSummary
976 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
980 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
982 // clear references in and out of node b
983 clearReferenceEdgesFrom(hrnB, null, true);
984 clearReferenceEdgesTo(hrnB, null, true);
986 // copy each edge in and out of A to B
987 Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
988 while( itrReferencee.hasNext() ) {
989 ReferenceEdge edge = itrReferencee.next();
990 HeapRegionNode hrnReferencee = edge.getDst();
991 ReferenceEdge edgeNew = edge.copy();
992 edgeNew.setSrc(hrnB);
994 addReferenceEdge(hrnB, hrnReferencee, edgeNew);
997 Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
998 while( itrReferencer.hasNext() ) {
999 ReferenceEdge edge = itrReferencer.next();
1000 OwnershipNode onReferencer = edge.getSrc();
1001 ReferenceEdge edgeNew = edge.copy();
1002 edgeNew.setDst(hrnB);
1004 addReferenceEdge(onReferencer, hrnB, edgeNew);
1007 // replace hrnB reachability with hrnA's
1008 hrnB.setAlpha(hrnA.getAlpha() );
1012 protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
1013 edge.setBeta(edge.getBeta().ageTokens(as) );
1016 protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
1017 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
1021 public Set<Integer> calculateAliasedParamSet(FlatCall fc,
1025 Hashtable<Integer, LabelNode> paramIndex2ln =
1026 new Hashtable<Integer, LabelNode>();
1028 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
1029 new Hashtable<Integer, HashSet<HeapRegionNode> >();
1031 for( int i = 0; i < fm.numParameters(); ++i ) {
1032 Integer paramIndex = new Integer(i);
1034 // now depending on whether the callee is static or not
1035 // we need to account for a "this" argument in order to
1036 // find the matching argument in the caller context
1037 TempDescriptor argTemp_i;
1039 argTemp_i = fc.getArg(paramIndex);
1041 if( paramIndex.equals(0) ) {
1042 argTemp_i = fc.getThis();
1044 argTemp_i = fc.getArg(paramIndex - 1);
1048 // in non-static methods there is a "this" pointer
1049 // that should be taken into account
1051 assert fc.numArgs() == fm.numParameters();
1053 assert fc.numArgs() + 1 == fm.numParameters();
1056 LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1057 paramIndex2ln.put(paramIndex, argLabel_i);
1060 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1061 while( lnArgItr.hasNext() ) {
1062 Map.Entry me = (Map.Entry)lnArgItr.next();
1063 Integer index = (Integer) me.getKey();
1064 LabelNode lnArg_i = (LabelNode) me.getValue();
1066 // rewrite alpha for the nodes reachable from argument label i
1067 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1068 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1070 // to find all reachable nodes, start with label referencees
1071 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1072 while( edgeArgItr.hasNext() ) {
1073 ReferenceEdge edge = edgeArgItr.next();
1074 todoNodes.add(edge.getDst() );
1077 // then follow links until all reachable nodes have been found
1078 while( !todoNodes.isEmpty() ) {
1079 HeapRegionNode hrn = todoNodes.iterator().next();
1080 todoNodes.remove(hrn);
1081 reachableNodes.add(hrn);
1083 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1084 while( edgeItr.hasNext() ) {
1085 ReferenceEdge edge = edgeItr.next();
1087 if( !reachableNodes.contains(edge.getDst() ) ) {
1088 todoNodes.add(edge.getDst() );
1094 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1097 Set<Integer> aliasedIndices = new HashSet<Integer>();
1099 // check for arguments that are aliased
1100 for( int i = 0; i < fm.numParameters(); ++i ) {
1101 for( int j = 0; j < i; ++j ) {
1102 HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
1103 HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
1105 Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
1106 intersection.retainAll(s2);
1108 if( !intersection.isEmpty() ) {
1109 aliasedIndices.add( new Integer( i ) );
1110 aliasedIndices.add( new Integer( j ) );
1115 return aliasedIndices;
1119 public void resolveMethodCall(FlatCall fc,
1122 OwnershipGraph ogCallee) {
1124 // define rewrite rules and other structures to organize
1125 // data by parameter/argument index
1126 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
1127 new Hashtable<Integer, ReachabilitySet>();
1129 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
1130 new Hashtable<Integer, ReachabilitySet>();
1132 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
1133 new Hashtable<Integer, ReachabilitySet>();
1135 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d =
1136 new Hashtable<Integer, ReachabilitySet>();
1138 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
1139 new Hashtable<Integer, ReachabilitySet>();
1141 // helpful structures
1142 Hashtable<TokenTuple, Integer> paramToken2paramIndex =
1143 new Hashtable<TokenTuple, Integer>();
1145 Hashtable<Integer, TokenTuple> paramIndex2paramToken =
1146 new Hashtable<Integer, TokenTuple>();
1148 Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex =
1149 new Hashtable<TokenTuple, Integer>();
1151 Hashtable<Integer, TokenTuple> paramIndex2paramTokenPlus =
1152 new Hashtable<Integer, TokenTuple>();
1154 Hashtable<Integer, LabelNode> paramIndex2ln =
1155 new Hashtable<Integer, LabelNode>();
1157 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
1158 new Hashtable<Integer, HashSet<HeapRegionNode> >();
1161 // add a bogus entry with the identity rule for easy rewrite
1162 // of new callee nodes and edges, doesn't belong to any parameter
1163 Integer bogusID = new Integer(bogusParamIndexInt);
1164 Integer bogusIndex = new Integer(bogusParamIndexInt);
1165 TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE).makeCanonical();
1166 TokenTuple bogusTokenPlus = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONEORMORE).makeCanonical();
1167 ReachabilitySet rsIdentity =
1168 new ReachabilitySet(
1169 new TokenTupleSet(bogusToken).makeCanonical()
1172 paramIndex2rewriteH.put(bogusIndex, rsIdentity);
1173 paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
1174 paramToken2paramIndex.put(bogusToken, bogusIndex);
1175 paramIndex2paramToken.put(bogusIndex, bogusToken);
1176 paramTokenPlus2paramIndex.put(bogusTokenPlus, bogusIndex);
1177 paramIndex2paramTokenPlus.put(bogusIndex, bogusTokenPlus);
1180 for( int i = 0; i < fm.numParameters(); ++i ) {
1181 Integer paramIndex = new Integer(i);
1183 assert ogCallee.paramIndex2id.containsKey(paramIndex);
1184 Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
1186 assert ogCallee.id2hrn.containsKey(idParam);
1187 HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
1188 assert hrnParam != null;
1189 paramIndex2rewriteH.put(paramIndex,
1191 toShadowTokens(ogCallee, hrnParam.getAlpha() )
1194 ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
1195 assert edgeReflexive_i != null;
1196 paramIndex2rewriteJ.put(paramIndex,
1197 toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
1200 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
1201 assert tdParamQ != null;
1202 LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
1203 assert lnParamQ != null;
1204 ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
1205 assert edgeSpecialQ_i != null;
1206 paramIndex2rewriteK.put(paramIndex,
1207 toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
1210 TokenTuple p_i = new TokenTuple(hrnParam.getID(),
1212 TokenTuple.ARITY_ONE).makeCanonical();
1213 paramToken2paramIndex.put(p_i, paramIndex);
1214 paramIndex2paramToken.put(paramIndex, p_i);
1216 TokenTuple p_i_plus = new TokenTuple(hrnParam.getID(),
1218 TokenTuple.ARITY_ONEORMORE).makeCanonical();
1219 paramTokenPlus2paramIndex.put(p_i_plus, paramIndex);
1220 paramIndex2paramTokenPlus.put(paramIndex, p_i_plus);
1222 // now depending on whether the callee is static or not
1223 // we need to account for a "this" argument in order to
1224 // find the matching argument in the caller context
1225 TempDescriptor argTemp_i;
1227 argTemp_i = fc.getArg(paramIndex);
1229 if( paramIndex.equals(0) ) {
1230 argTemp_i = fc.getThis();
1232 argTemp_i = fc.getArg(paramIndex - 1);
1236 // in non-static methods there is a "this" pointer
1237 // that should be taken into account
1239 assert fc.numArgs() == fm.numParameters();
1241 assert fc.numArgs() + 1 == fm.numParameters();
1244 LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1245 paramIndex2ln.put(paramIndex, argLabel_i);
1247 ReachabilitySet d_i = new ReachabilitySet().makeCanonical();
1248 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1249 while( edgeItr.hasNext() ) {
1250 ReferenceEdge edge = edgeItr.next();
1251 d_i = d_i.union(edge.getBeta());
1253 paramIndex2rewrite_d.put(paramIndex, d_i);
1255 ReachabilitySet D_i = d_i.exhaustiveArityCombinations();
1256 paramIndex2rewriteD.put(paramIndex, D_i);
1260 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1261 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
1263 HashSet<ReferenceEdge> edgesReachable = new HashSet<ReferenceEdge>();
1264 HashSet<ReferenceEdge> edgesUpstream = new HashSet<ReferenceEdge>();
1266 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1267 while( lnArgItr.hasNext() ) {
1268 Map.Entry me = (Map.Entry)lnArgItr.next();
1269 Integer index = (Integer) me.getKey();
1270 LabelNode lnArg_i = (LabelNode) me.getValue();
1272 // rewrite alpha for the nodes reachable from argument label i
1273 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1274 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1276 // to find all reachable nodes, start with label referencees
1277 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1278 while( edgeArgItr.hasNext() ) {
1279 ReferenceEdge edge = edgeArgItr.next();
1280 todoNodes.add(edge.getDst() );
1283 // then follow links until all reachable nodes have been found
1284 while( !todoNodes.isEmpty() ) {
1285 HeapRegionNode hrn = todoNodes.iterator().next();
1286 todoNodes.remove(hrn);
1287 reachableNodes.add(hrn);
1289 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1290 while( edgeItr.hasNext() ) {
1291 ReferenceEdge edge = edgeItr.next();
1293 if( !reachableNodes.contains(edge.getDst() ) ) {
1294 todoNodes.add(edge.getDst() );
1300 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1302 // now iterate over reachable nodes to update their alpha, and
1303 // classify edges found as "argument reachable" or "upstream"
1304 Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1305 while( hrnItr.hasNext() ) {
1306 HeapRegionNode hrn = hrnItr.next();
1308 rewriteCallerReachability(index,
1311 paramIndex2rewriteH.get(index),
1312 paramIndex2rewrite_d,
1313 paramIndex2rewriteD,
1314 paramIndex2paramToken.get(index),
1315 paramToken2paramIndex,
1316 paramTokenPlus2paramIndex,
1320 nodesWithNewAlpha.add(hrn);
1322 // look at all incoming edges to the reachable nodes
1323 // and sort them as edges reachable from the argument
1324 // label node, or upstream edges
1325 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1326 while( edgeItr.hasNext() ) {
1327 ReferenceEdge edge = edgeItr.next();
1329 OwnershipNode on = edge.getSrc();
1331 if( on instanceof LabelNode ) {
1333 LabelNode ln0 = (LabelNode) on;
1334 if( ln0.equals(lnArg_i) ) {
1335 edgesReachable.add(edge);
1337 edgesUpstream.add(edge);
1342 HeapRegionNode hrn0 = (HeapRegionNode) on;
1343 if( reachableNodes.contains(hrn0) ) {
1344 edgesReachable.add(edge);
1346 edgesUpstream.add(edge);
1352 // update reachable edges
1353 Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1354 while( edgeReachableItr.hasNext() ) {
1355 ReferenceEdge edgeReachable = edgeReachableItr.next();
1357 rewriteCallerReachability(index,
1360 paramIndex2rewriteJ.get(index),
1361 paramIndex2rewrite_d,
1362 paramIndex2rewriteD,
1363 paramIndex2paramToken.get(index),
1364 paramToken2paramIndex,
1365 paramTokenPlus2paramIndex,
1369 edgesWithNewBeta.add(edgeReachable);
1372 // update upstream edges
1373 Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
1374 new Hashtable<ReferenceEdge, ChangeTupleSet>();
1376 Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1377 while( edgeUpstreamItr.hasNext() ) {
1378 ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1380 rewriteCallerReachability(index,
1383 paramIndex2rewriteK.get(index),
1384 paramIndex2rewrite_d,
1385 paramIndex2rewriteD,
1386 paramIndex2paramToken.get(index),
1387 paramToken2paramIndex,
1388 paramTokenPlus2paramIndex,
1390 edgeUpstreamPlannedChanges);
1392 edgesWithNewBeta.add(edgeUpstream);
1395 propagateTokensOverEdges(edgesUpstream,
1396 edgeUpstreamPlannedChanges,
1401 // commit changes to alpha and beta
1402 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1403 while( nodeItr.hasNext() ) {
1404 nodeItr.next().applyAlphaNew();
1407 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1408 while( edgeItr.hasNext() ) {
1409 edgeItr.next().applyBetaNew();
1413 // verify the existence of allocation sites and their
1414 // shadows from the callee in the context of this caller graph
1415 // then map allocated nodes of callee onto the caller shadows
1417 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1418 while( asItr.hasNext() ) {
1419 AllocationSite allocSite = asItr.next();
1421 // grab the summary in the caller just to make sure
1422 // the allocation site has nodes in the caller
1423 HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1425 // assert that the shadow nodes have no reference edges
1426 // because they're brand new to the graph, or last time
1427 // they were used they should have been cleared of edges
1428 HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1429 assert hrnShadowSummary.getNumReferencers() == 0;
1430 assert hrnShadowSummary.getNumReferencees() == 0;
1432 // then bring g_ij onto g'_ij and rewrite
1433 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1434 hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1436 // shadow nodes only are touched by a rewrite one time,
1437 // so rewrite and immediately commit--and they don't belong
1438 // to a particular parameter, so use a bogus param index
1439 // that pulls a self-rewrite out of H
1440 rewriteCallerReachability(bogusIndex,
1443 hrnShadowSummary.getAlpha(),
1444 paramIndex2rewrite_d,
1445 paramIndex2rewriteD,
1447 paramToken2paramIndex,
1448 paramTokenPlus2paramIndex,
1452 hrnShadowSummary.applyAlphaNew();
1455 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1456 Integer idIth = allocSite.getIthOldest(i);
1457 assert id2hrn.containsKey(idIth);
1458 HeapRegionNode hrnIth = id2hrn.get(idIth);
1460 Integer idShadowIth = -(allocSite.getIthOldest(i));
1461 assert id2hrn.containsKey(idShadowIth);
1462 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1463 assert hrnIthShadow.getNumReferencers() == 0;
1464 assert hrnIthShadow.getNumReferencees() == 0;
1466 assert ogCallee.id2hrn.containsKey(idIth);
1467 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1468 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1470 rewriteCallerReachability(bogusIndex,
1473 hrnIthShadow.getAlpha(),
1474 paramIndex2rewrite_d,
1475 paramIndex2rewriteD,
1477 paramToken2paramIndex,
1478 paramTokenPlus2paramIndex,
1482 hrnIthShadow.applyAlphaNew();
1487 // for every heap region->heap region edge in the
1488 // callee graph, create the matching edge or edges
1489 // in the caller graph
1490 Set sCallee = ogCallee.id2hrn.entrySet();
1491 Iterator iCallee = sCallee.iterator();
1492 while( iCallee.hasNext() ) {
1493 Map.Entry meCallee = (Map.Entry)iCallee.next();
1494 Integer idCallee = (Integer) meCallee.getKey();
1495 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1497 Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1498 while( heapRegionsItrCallee.hasNext() ) {
1499 ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
1500 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1501 Integer idChildCallee = hrnChildCallee.getID();
1503 // only address this edge if it is not a special reflexive edge
1504 if( !edgeCallee.isInitialParamReflexive() ) {
1506 // now we know that in the callee method's ownership graph
1507 // there is a heap region->heap region reference edge given
1508 // by heap region pointers:
1509 // hrnCallee -> heapChildCallee
1511 // or by the ownership-graph independent ID's:
1512 // idCallee -> idChildCallee
1514 // make the edge with src and dst so beta info is
1515 // calculated once, then copy it for each new edge in caller
1516 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1518 edgeCallee.getFieldDesc(),
1520 toShadowTokens(ogCallee,
1521 edgeCallee.getBeta() )
1523 rewriteCallerReachability(bogusIndex,
1525 edgeNewInCallerTemplate,
1526 edgeNewInCallerTemplate.getBeta(),
1527 paramIndex2rewrite_d,
1528 paramIndex2rewriteD,
1530 paramToken2paramIndex,
1531 paramTokenPlus2paramIndex,
1535 edgeNewInCallerTemplate.applyBetaNew();
1538 // So now make a set of possible source heaps in the caller graph
1539 // and a set of destination heaps in the caller graph, and make
1540 // a reference edge in the caller for every possible (src,dst) pair
1541 HashSet<HeapRegionNode> possibleCallerSrcs =
1542 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1543 (HeapRegionNode) edgeCallee.getSrc(),
1544 paramIndex2reachableCallerNodes);
1546 HashSet<HeapRegionNode> possibleCallerDsts =
1547 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1548 edgeCallee.getDst(),
1549 paramIndex2reachableCallerNodes);
1552 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1553 Iterator srcItr = possibleCallerSrcs.iterator();
1554 while( srcItr.hasNext() ) {
1555 HeapRegionNode src = (HeapRegionNode) srcItr.next();
1557 if( !hasMatchingField(src, edgeCallee) ) {
1558 // prune this source node possibility
1562 Iterator dstItr = possibleCallerDsts.iterator();
1563 while( dstItr.hasNext() ) {
1564 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1566 if( !hasMatchingType(edgeCallee, dst) ) {
1571 // otherwise the caller src and dst pair can match the edge, so make it
1572 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1573 edgeNewInCaller.setSrc(src);
1574 edgeNewInCaller.setDst(dst);
1576 ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1577 if( edgeExisting == null ) {
1578 // if this edge doesn't exist in the caller, create it
1579 addReferenceEdge(src, dst, edgeNewInCaller);
1581 // if it already exists, merge with it
1582 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1591 // return value may need to be assigned in caller
1592 TempDescriptor returnTemp = fc.getReturnTemp();
1593 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
1595 LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
1596 clearReferenceEdgesFrom(lnLhsCaller, null, true);
1598 LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1599 Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1600 while( edgeCalleeItr.hasNext() ) {
1601 ReferenceEdge edgeCallee = edgeCalleeItr.next();
1603 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1605 edgeCallee.getFieldDesc(),
1607 toShadowTokens(ogCallee,
1608 edgeCallee.getBeta() )
1610 rewriteCallerReachability(bogusIndex,
1612 edgeNewInCallerTemplate,
1613 edgeNewInCallerTemplate.getBeta(),
1614 paramIndex2rewrite_d,
1615 paramIndex2rewriteD,
1617 paramToken2paramIndex,
1618 paramTokenPlus2paramIndex,
1622 edgeNewInCallerTemplate.applyBetaNew();
1625 HashSet<HeapRegionNode> assignCallerRhs =
1626 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1627 edgeCallee.getDst(),
1628 paramIndex2reachableCallerNodes);
1630 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1631 while( itrHrn.hasNext() ) {
1632 HeapRegionNode hrnCaller = itrHrn.next();
1634 if( !hasMatchingType(edgeCallee, hrnCaller) ) {
1639 // otherwise caller node can match callee edge, so make it
1640 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1641 edgeNewInCaller.setSrc(lnLhsCaller);
1642 edgeNewInCaller.setDst(hrnCaller);
1644 ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1645 if( edgeExisting == null ) {
1647 // if this edge doesn't exist in the caller, create it
1648 addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1650 // if it already exists, merge with it
1651 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1658 // merge the shadow nodes of allocation sites back down to normal capacity
1659 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1660 while( allocItr.hasNext() ) {
1661 AllocationSite as = allocItr.next();
1663 // first age each allocation site enough times to make room for the shadow nodes
1664 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1668 // then merge the shadow summary into the normal summary
1669 HeapRegionNode hrnSummary = getSummaryNode(as);
1670 assert hrnSummary != null;
1672 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1673 assert hrnSummaryShadow != null;
1675 mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1677 // then clear off after merge
1678 clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1679 clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1680 hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1682 // then transplant shadow nodes onto the now clean normal nodes
1683 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1685 Integer idIth = as.getIthOldest(i);
1686 HeapRegionNode hrnIth = id2hrn.get(idIth);
1688 Integer idIthShadow = as.getIthOldestShadow(i);
1689 HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1691 transferOnto(hrnIthShadow, hrnIth);
1693 // clear off shadow nodes after transfer
1694 clearReferenceEdgesFrom(hrnIthShadow, null, true);
1695 clearReferenceEdgesTo(hrnIthShadow, null, true);
1696 hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1699 // finally, globally change shadow tokens into normal tokens
1700 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1701 while( itrAllLabelNodes.hasNext() ) {
1702 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1703 LabelNode ln = (LabelNode) me.getValue();
1705 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1706 while( itrEdges.hasNext() ) {
1707 unshadowTokens(as, itrEdges.next() );
1711 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1712 while( itrAllHRNodes.hasNext() ) {
1713 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1714 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1716 unshadowTokens(as, hrnToAge);
1718 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1719 while( itrEdges.hasNext() ) {
1720 unshadowTokens(as, itrEdges.next() );
1725 // improve reachability as much as possible
1730 protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
1732 // if no allocation site, then it's a match-everything region
1733 AllocationSite asSrc = src.getAllocationSite();
1734 if( asSrc == null ) {
1738 TypeDescriptor tdSrc = asSrc.getType();
1739 assert tdSrc != null;
1741 // if it's not a class, it doesn't have any fields to match
1742 if( !tdSrc.isClass() ) {
1746 Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
1747 while( fieldsSrcItr.hasNext() ) {
1748 FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1749 if( fd == edge.getFieldDesc() ) {
1754 // otherwise it is a class with fields
1755 // but we didn't find a match
1760 protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
1762 // if the region has no type, matches everything
1763 AllocationSite asDst = dst.getAllocationSite();
1764 if( asDst == null ) {
1768 TypeDescriptor tdDst = asDst.getType();
1769 assert tdDst != null;
1771 // if the type is not a class don't match because
1772 // primitives are copied, no memory aliases
1773 ClassDescriptor cdDst = tdDst.getClassDesc();
1774 if( cdDst == null ) {
1778 // if the field is null, it matches everything
1779 FieldDescriptor fd = edge.getFieldDesc();
1783 TypeDescriptor tdFd = fd.getType();
1784 assert tdFd != null;
1786 return typeUtil.isSuperorType(tdFd, tdDst);
1791 protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1792 edge.setBeta(edge.getBeta().unshadowTokens(as) );
1795 protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1796 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1800 private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1801 ReachabilitySet rsIn) {
1803 ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical();
1805 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1806 while( allocItr.hasNext() ) {
1807 AllocationSite as = allocItr.next();
1809 rsOut = rsOut.toShadowTokens(as);
1812 return rsOut.makeCanonical();
1816 private void rewriteCallerReachability(Integer paramIndex,
1819 ReachabilitySet rules,
1820 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d,
1821 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1823 Hashtable<TokenTuple, Integer> paramToken2paramIndex,
1824 Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex,
1825 boolean makeChangeSet,
1826 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1827 assert(hrn == null && edge != null) ||
1828 (hrn != null && edge == null);
1830 assert rules != null;
1833 ReachabilitySet callerReachabilityCurrent;
1835 callerReachabilityCurrent = edge.getBeta();
1837 callerReachabilityCurrent = hrn.getAlpha();
1840 ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
1842 // for initializing structures in this method
1843 TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
1845 // use this to construct a change set if required; the idea is to
1846 // map every partially rewritten token tuple set to the set of
1847 // caller-context token tuple sets that were used to generate it
1848 Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
1849 new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
1850 rewritten2source.put(ttsEmpty, new HashSet<TokenTupleSet>() );
1853 Iterator<TokenTupleSet> rulesItr = rules.iterator();
1854 while(rulesItr.hasNext()) {
1855 TokenTupleSet rule = rulesItr.next();
1857 ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
1859 Iterator<TokenTuple> ruleItr = rule.iterator();
1860 while(ruleItr.hasNext()) {
1861 TokenTuple ttCallee = ruleItr.next();
1863 // compute the possibilities for rewriting this callee token
1864 ReachabilitySet ttCalleeRewrites = null;
1865 boolean callerSourceUsed = false;
1867 if( ttCallee.equals(p_i) ) {
1868 // replace the arity-one token of the current parameter with the reachability
1869 // information from the caller edge
1870 ttCalleeRewrites = callerReachabilityCurrent;
1871 callerSourceUsed = true;
1873 } else if( paramToken2paramIndex.containsKey(ttCallee) ) {
1875 Integer paramIndex_j = paramToken2paramIndex.get(ttCallee);
1876 assert paramIndex_j != null;
1877 ttCalleeRewrites = paramIndex2rewrite_d.get(paramIndex_j);
1878 assert ttCalleeRewrites != null;
1880 } else if( paramTokenPlus2paramIndex.containsKey(ttCallee) ) {
1882 Integer paramIndex_j = paramTokenPlus2paramIndex.get(ttCallee);
1883 assert paramIndex_j != null;
1884 ttCalleeRewrites = paramIndex2rewriteD.get(paramIndex_j);
1885 assert ttCalleeRewrites != null;
1888 // otherwise there's no need for a rewrite, just pass this one on
1889 TokenTupleSet ttsCaller = new TokenTupleSet(ttCallee).makeCanonical();
1890 ttCalleeRewrites = new ReachabilitySet(ttsCaller).makeCanonical();
1893 // branch every version of the working rewritten rule with
1894 // the possibilities for rewriting the current callee token
1895 ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
1897 Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
1898 while( rewrittenRuleItr.hasNext() ) {
1899 TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
1901 Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
1902 while( ttCalleeRewritesItr.hasNext() ) {
1903 TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
1905 TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity(ttsBranch);
1907 if( makeChangeSet ) {
1908 // in order to keep the list of source token tuple sets
1909 // start with the sets used to make the partially rewritten
1910 // rule up to this point
1911 HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewritten);
1912 assert sourceSets != null;
1914 // make a shallow copy for possible modification
1915 sourceSets = (HashSet<TokenTupleSet>)sourceSets.clone();
1917 // if we used something from the caller to rewrite it, remember
1918 if( callerSourceUsed ) {
1919 sourceSets.add(ttsBranch);
1922 // set mapping for the further rewritten rule
1923 rewritten2source.put(ttsRewrittenNext, sourceSets);
1926 rewrittenRuleWithTTCallee =
1927 rewrittenRuleWithTTCallee.union(ttsRewrittenNext);
1931 // now the rewritten rule's possibilities have been extended by
1932 // rewriting the current callee token, remember result
1933 rewrittenRule = rewrittenRuleWithTTCallee;
1936 // the rule has been entirely rewritten into the caller context
1937 // now, so add it to the new reachability information
1938 callerReachabilityNew =
1939 callerReachabilityNew.union(rewrittenRule);
1942 if( makeChangeSet ) {
1943 ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
1945 // each possibility for the final reachability should have a set of
1946 // caller sources mapped to it, use to create the change set
1947 Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
1948 while( callerReachabilityItr.hasNext() ) {
1949 TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
1950 HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewrittenFinal);
1951 assert sourceSets != null;
1953 Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
1954 while( sourceSetsItr.hasNext() ) {
1955 TokenTupleSet ttsSource = sourceSetsItr.next();
1958 callerChangeSet.union(new ChangeTuple(ttsSource, ttsRewrittenFinal) );
1962 assert edgePlannedChanges != null;
1963 edgePlannedChanges.put(edge, callerChangeSet);
1967 edge.setBetaNew(edge.getBetaNew().union(callerReachabilityNew) );
1969 hrn.setAlphaNew(hrn.getAlphaNew().union(callerReachabilityNew) );
1975 private HashSet<HeapRegionNode>
1976 getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1977 HeapRegionNode hrnCallee,
1978 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1981 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1983 Set<Integer> paramIndicesCallee = ogCallee.id2paramIndexSet.get( hrnCallee.getID() );
1985 if( paramIndicesCallee == null ) {
1986 // this is a node allocated in the callee then and it has
1987 // exactly one shadow node in the caller to map to
1988 AllocationSite as = hrnCallee.getAllocationSite();
1991 int age = as.getAgeCategory(hrnCallee.getID() );
1992 assert age != AllocationSite.AGE_notInThisSite;
1995 if( age == AllocationSite.AGE_summary ) {
1996 idCaller = as.getSummaryShadow();
1997 } else if( age == AllocationSite.AGE_oldest ) {
1998 idCaller = as.getOldestShadow();
2000 assert age == AllocationSite.AGE_in_I;
2002 Integer I = as.getAge(hrnCallee.getID() );
2005 idCaller = as.getIthOldestShadow(I);
2008 assert id2hrn.containsKey(idCaller);
2009 HeapRegionNode hrnCaller = id2hrn.get(idCaller);
2010 possibleCallerHRNs.add(hrnCaller);
2013 // this is a node that was created to represent a parameter
2014 // so it maps to a whole mess of heap regions
2015 Iterator<Integer> itrIndex = paramIndicesCallee.iterator();
2016 while( itrIndex.hasNext() ) {
2017 Integer paramIndexCallee = itrIndex.next();
2018 assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
2019 possibleCallerHRNs.addAll( paramIndex2reachableCallerNodes.get(paramIndexCallee) );
2023 return possibleCallerHRNs;
2028 ////////////////////////////////////////////////////
2030 // This global sweep is an optional step to prune
2031 // reachability sets that are not internally
2032 // consistent with the global graph. It should be
2033 // invoked after strong updates or method calls.
2035 ////////////////////////////////////////////////////
2036 protected void globalSweep() {
2038 // a work set for performing the sweep
2039 Hashtable<HeapRegionNode, HashSet<TokenTupleSet> > workSet =
2040 new Hashtable<HeapRegionNode, HashSet<TokenTupleSet> >();
2042 // first initialize every alphaNew for a flagged region
2043 // (or parameter region) to a set with just that token
2044 Set hrns = id2hrn.entrySet();
2045 Iterator itrHrns = hrns.iterator();
2046 while( itrHrns.hasNext() ) {
2047 Map.Entry me = (Map.Entry)itrHrns.next();
2048 Integer token = (Integer) me.getKey();
2049 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2051 // assert that this node and incoming edges have clean alphaNew
2052 // and betaNew sets, respectively
2053 ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical();
2054 assert rsEmpty.equals( hrn.getAlphaNew() );
2056 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
2057 while( itrRes.hasNext() ) {
2058 ReferenceEdge edge = itrRes.next();
2059 assert rsEmpty.equals( edge.getBetaNew() );
2062 TokenTuple tt = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONE ).makeCanonical();
2063 TokenTuple ttPlus = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONEORMORE ).makeCanonical();
2064 TokenTuple ttStar = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
2066 TokenTupleSet tts = new TokenTupleSet( tt ).makeCanonical();
2067 TokenTupleSet ttsPlus = new TokenTupleSet( ttPlus ).makeCanonical();
2068 TokenTupleSet ttsStar = new TokenTupleSet( ttStar ).makeCanonical();
2069 TokenTupleSet ttsEmpty = new TokenTupleSet( ).makeCanonical();
2071 if( hrn.isFlagged() || hrn.isParameter() ) {
2072 HashSet<TokenTupleSet> subWorkSet = new HashSet<TokenTupleSet>();
2073 subWorkSet.add( tts );
2074 subWorkSet.add( ttsPlus );
2075 subWorkSet.add( ttsStar );
2076 workSet.put( hrn, subWorkSet );
2078 hrn.setAlphaNew( new ReachabilitySet( tts ).makeCanonical() );
2080 hrn.setAlphaNew( new ReachabilitySet( ttsEmpty ).makeCanonical() );
2084 // then propagate tokens forward one step at a time
2085 while( !workSet.isEmpty() ) {
2086 HeapRegionNode hrn = workSet.keySet().iterator().next();
2088 HashSet<TokenTupleSet> subWorkSet = workSet.get( hrn );
2089 assert subWorkSet != null;
2091 if( subWorkSet.isEmpty() ) {
2092 // we're currently done with sub work at this heap region, although
2093 // more work may get queued up later, but remove it for now and continue
2094 workSet.remove( hrn );
2098 TokenTupleSet tts = subWorkSet.iterator().next();
2099 subWorkSet.remove( tts );
2101 // try to push this TokenTupleSet over all outgoing edges
2102 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencees();
2103 while( itrRes.hasNext() ) {
2104 ReferenceEdge edge = itrRes.next();
2106 if( edge.getBeta().containsSuperSet( tts ) ) {
2107 HeapRegionNode dst = edge.getDst();
2109 // make a set of possible contributions this token
2110 // might have on the alpha set here
2111 HashSet<TokenTupleSet> ttsNewSet = new HashSet<TokenTupleSet>();
2113 Iterator<TokenTupleSet> itrDstAlphaNew = dst.getAlphaNew().iterator();
2114 while( itrDstAlphaNew.hasNext() ) {
2115 TokenTupleSet ttsDstAlphaNew = itrDstAlphaNew.next();
2116 ttsNewSet.add( tts.unionUpArity( ttsDstAlphaNew ) );
2119 // only add this to the dst alpha new if it is in the beta of
2120 // the edge we crossed to get here, and then only continue the
2121 // propagation if it isn't already in the dst alpha new
2122 Iterator<TokenTupleSet> itrNewSet = ttsNewSet.iterator();
2123 while( itrNewSet.hasNext() ) {
2124 TokenTupleSet ttsNew = itrNewSet.next();
2126 if( edge.getBeta().containsSuperSet( ttsNew ) &&
2127 !dst.getAlphaNew().contains( ttsNew ) ) {
2129 // okay, this is a valid propagation, and add to the
2130 // work set to further propagate it
2131 dst.setAlphaNew( dst.getAlphaNew().union( ttsNew ) );
2133 HashSet<TokenTupleSet> subWorkSetDst = workSet.get( dst );
2134 if( subWorkSetDst == null ) {
2135 subWorkSetDst = new HashSet<TokenTupleSet>();
2138 subWorkSetDst.add( ttsNew );
2139 workSet.put( dst, subWorkSetDst );
2146 // now prepare work sets to propagate token sets backwards
2147 // from heap regions across all edges
2148 assert workSet.isEmpty();
2149 hrns = id2hrn.entrySet();
2150 itrHrns = hrns.iterator();
2151 while( itrHrns.hasNext() ) {
2152 Map.Entry me = (Map.Entry)itrHrns.next();
2153 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2155 HashSet<TokenTupleSet> subWorkSet = new HashSet<TokenTupleSet>();
2157 Iterator<TokenTupleSet> itrAlphaNewSets = hrn.getAlphaNew().iterator();
2158 while( itrAlphaNewSets.hasNext() ) {
2159 TokenTupleSet tts = itrAlphaNewSets.next();
2160 subWorkSet.add( tts );
2163 workSet.put( hrn, subWorkSet );
2166 // propagate token sets backwards across edges one step at a time
2167 while( !workSet.isEmpty() ) {
2168 HeapRegionNode hrn = workSet.keySet().iterator().next();
2170 HashSet<TokenTupleSet> subWorkSet = workSet.get( hrn );
2171 assert subWorkSet != null;
2173 if( subWorkSet.isEmpty() ) {
2174 // we're currently done with sub work at this heap region, although
2175 // more work may get queued up later, but remove it for now and continue
2176 workSet.remove( hrn );
2180 TokenTupleSet tts = subWorkSet.iterator().next();
2181 subWorkSet.remove( tts );
2183 // try to push this TokenTupleSet back up incoming edges
2184 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
2185 while( itrRes.hasNext() ) {
2186 ReferenceEdge edge = itrRes.next();
2187 if( edge.getBeta().containsWithZeroes( tts ) &&
2188 !edge.getBetaNew().contains( tts ) ) {
2189 // okay, this is a valid propagation, and add to the
2190 // work set to further propagate it
2191 edge.setBetaNew( edge.getBetaNew().union( tts ) );
2193 OwnershipNode src = edge.getSrc();
2194 if( src instanceof HeapRegionNode ) {
2196 HashSet<TokenTupleSet> subWorkSetSrc = workSet.get( (HeapRegionNode) src );
2197 if( subWorkSetSrc == null ) {
2198 subWorkSetSrc = new HashSet<TokenTupleSet>();
2201 subWorkSetSrc.add( tts );
2202 workSet.put( (HeapRegionNode) src, subWorkSetSrc );
2208 // apply alphaNew and betaNew to all nodes and edges
2209 HashSet<ReferenceEdge> res = new HashSet<ReferenceEdge>();
2211 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2212 while( nodeItr.hasNext() ) {
2213 HeapRegionNode hrn = nodeItr.next();
2214 hrn.applyAlphaNew();
2215 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
2216 while( itrRes.hasNext() ) {
2217 res.add( itrRes.next() );
2221 Iterator<ReferenceEdge> edgeItr = res.iterator();
2222 while( edgeItr.hasNext() ) {
2223 edgeItr.next().applyBetaNew();
2229 ////////////////////////////////////////////////////
2230 // in merge() and equals() methods the suffix A
2231 // represents the passed in graph and the suffix
2232 // B refers to the graph in this object
2233 // Merging means to take the incoming graph A and
2234 // merge it into B, so after the operation graph B
2235 // is the final result.
2236 ////////////////////////////////////////////////////
2237 public void merge(OwnershipGraph og) {
2243 mergeOwnershipNodes(og);
2244 mergeReferenceEdges(og);
2245 mergeId2paramIndex(og);
2246 mergeAllocationSites(og);
2250 protected void mergeOwnershipNodes(OwnershipGraph og) {
2251 Set sA = og.id2hrn.entrySet();
2252 Iterator iA = sA.iterator();
2253 while( iA.hasNext() ) {
2254 Map.Entry meA = (Map.Entry)iA.next();
2255 Integer idA = (Integer) meA.getKey();
2256 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2258 // if this graph doesn't have a node the
2259 // incoming graph has, allocate it
2260 if( !id2hrn.containsKey(idA) ) {
2261 HeapRegionNode hrnB = hrnA.copy();
2262 id2hrn.put(idA, hrnB);
2265 // otherwise this is a node present in both graphs
2266 // so make the new reachability set a union of the
2267 // nodes' reachability sets
2268 HeapRegionNode hrnB = id2hrn.get(idA);
2269 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
2273 // now add any label nodes that are in graph B but
2275 sA = og.td2ln.entrySet();
2277 while( iA.hasNext() ) {
2278 Map.Entry meA = (Map.Entry)iA.next();
2279 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2280 LabelNode lnA = (LabelNode) meA.getValue();
2282 // if the label doesn't exist in B, allocate and add it
2283 LabelNode lnB = getLabelNodeFromTemp(tdA);
2287 protected void mergeReferenceEdges(OwnershipGraph og) {
2290 Set sA = og.id2hrn.entrySet();
2291 Iterator iA = sA.iterator();
2292 while( iA.hasNext() ) {
2293 Map.Entry meA = (Map.Entry)iA.next();
2294 Integer idA = (Integer) meA.getKey();
2295 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2297 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2298 while( heapRegionsItrA.hasNext() ) {
2299 ReferenceEdge edgeA = heapRegionsItrA.next();
2300 HeapRegionNode hrnChildA = edgeA.getDst();
2301 Integer idChildA = hrnChildA.getID();
2303 // at this point we know an edge in graph A exists
2304 // idA -> idChildA, does this exist in B?
2305 assert id2hrn.containsKey(idA);
2306 HeapRegionNode hrnB = id2hrn.get(idA);
2307 ReferenceEdge edgeToMerge = null;
2309 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2310 while( heapRegionsItrB.hasNext() &&
2311 edgeToMerge == null ) {
2313 ReferenceEdge edgeB = heapRegionsItrB.next();
2314 HeapRegionNode hrnChildB = edgeB.getDst();
2315 Integer idChildB = hrnChildB.getID();
2317 // don't use the ReferenceEdge.equals() here because
2318 // we're talking about existence between graphs
2319 if( idChildB.equals(idChildA) &&
2320 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
2321 edgeToMerge = edgeB;
2325 // if the edge from A was not found in B,
2327 if( edgeToMerge == null ) {
2328 assert id2hrn.containsKey(idChildA);
2329 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
2330 edgeToMerge = edgeA.copy();
2331 edgeToMerge.setSrc(hrnB);
2332 edgeToMerge.setDst(hrnChildB);
2333 addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
2335 // otherwise, the edge already existed in both graphs
2336 // so merge their reachability sets
2338 // just replace this beta set with the union
2339 assert edgeToMerge != null;
2340 edgeToMerge.setBeta(
2341 edgeToMerge.getBeta().union(edgeA.getBeta() )
2343 if( !edgeA.isInitialParamReflexive() ) {
2344 edgeToMerge.setIsInitialParamReflexive(false);
2350 // and then again with label nodes
2351 sA = og.td2ln.entrySet();
2353 while( iA.hasNext() ) {
2354 Map.Entry meA = (Map.Entry)iA.next();
2355 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2356 LabelNode lnA = (LabelNode) meA.getValue();
2358 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
2359 while( heapRegionsItrA.hasNext() ) {
2360 ReferenceEdge edgeA = heapRegionsItrA.next();
2361 HeapRegionNode hrnChildA = edgeA.getDst();
2362 Integer idChildA = hrnChildA.getID();
2364 // at this point we know an edge in graph A exists
2365 // tdA -> idChildA, does this exist in B?
2366 assert td2ln.containsKey(tdA);
2367 LabelNode lnB = td2ln.get(tdA);
2368 ReferenceEdge edgeToMerge = null;
2370 // labels never have edges with a field
2371 //assert edgeA.getFieldDesc() == null;
2373 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
2374 while( heapRegionsItrB.hasNext() &&
2375 edgeToMerge == null ) {
2377 ReferenceEdge edgeB = heapRegionsItrB.next();
2378 HeapRegionNode hrnChildB = edgeB.getDst();
2379 Integer idChildB = hrnChildB.getID();
2381 // labels never have edges with a field
2382 //assert edgeB.getFieldDesc() == null;
2384 // don't use the ReferenceEdge.equals() here because
2385 // we're talking about existence between graphs
2386 if( idChildB.equals(idChildA) &&
2387 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
2388 edgeToMerge = edgeB;
2392 // if the edge from A was not found in B,
2394 if( edgeToMerge == null ) {
2395 assert id2hrn.containsKey(idChildA);
2396 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
2397 edgeToMerge = edgeA.copy();
2398 edgeToMerge.setSrc(lnB);
2399 edgeToMerge.setDst(hrnChildB);
2400 addReferenceEdge(lnB, hrnChildB, edgeToMerge);
2402 // otherwise, the edge already existed in both graphs
2403 // so merge their reachability sets
2405 // just replace this beta set with the union
2406 edgeToMerge.setBeta(
2407 edgeToMerge.getBeta().union(edgeA.getBeta() )
2409 if( !edgeA.isInitialParamReflexive() ) {
2410 edgeToMerge.setIsInitialParamReflexive(false);
2417 // you should only merge ownership graphs that have the
2418 // same number of parameters, or if one or both parameter
2419 // index tables are empty
2420 protected void mergeId2paramIndex(OwnershipGraph og) {
2421 if( id2paramIndexSet.size() == 0 ) {
2422 id2paramIndexSet = og.id2paramIndexSet;
2423 paramIndex2id = og.paramIndex2id;
2424 paramIndex2tdQ = og.paramIndex2tdQ;
2428 if( og.id2paramIndexSet.size() == 0 ) {
2432 assert id2paramIndexSet.size() == og.id2paramIndexSet.size();
2435 protected void mergeAllocationSites(OwnershipGraph og) {
2436 allocationSites.addAll(og.allocationSites);
2441 // it is necessary in the equals() member functions
2442 // to "check both ways" when comparing the data
2443 // structures of two graphs. For instance, if all
2444 // edges between heap region nodes in graph A are
2445 // present and equal in graph B it is not sufficient
2446 // to say the graphs are equal. Consider that there
2447 // may be edges in graph B that are not in graph A.
2448 // the only way to know that all edges in both graphs
2449 // are equally present is to iterate over both data
2450 // structures and compare against the other graph.
2451 public boolean equals(OwnershipGraph og) {
2457 if( !areHeapRegionNodesEqual(og) ) {
2461 if( !areLabelNodesEqual(og) ) {
2465 if( !areReferenceEdgesEqual(og) ) {
2469 if( !areId2paramIndexEqual(og) ) {
2473 // if everything is equal up to this point,
2474 // assert that allocationSites is also equal--
2475 // this data is redundant and kept for efficiency
2476 assert allocationSites.equals(og.allocationSites);
2481 protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2483 if( !areallHRNinAalsoinBandequal(this, og) ) {
2487 if( !areallHRNinAalsoinBandequal(og, this) ) {
2494 static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2495 OwnershipGraph ogB) {
2496 Set sA = ogA.id2hrn.entrySet();
2497 Iterator iA = sA.iterator();
2498 while( iA.hasNext() ) {
2499 Map.Entry meA = (Map.Entry)iA.next();
2500 Integer idA = (Integer) meA.getKey();
2501 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2503 if( !ogB.id2hrn.containsKey(idA) ) {
2507 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2508 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2517 protected boolean areLabelNodesEqual(OwnershipGraph og) {
2519 if( !areallLNinAalsoinBandequal(this, og) ) {
2523 if( !areallLNinAalsoinBandequal(og, this) ) {
2530 static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2531 OwnershipGraph ogB) {
2532 Set sA = ogA.td2ln.entrySet();
2533 Iterator iA = sA.iterator();
2534 while( iA.hasNext() ) {
2535 Map.Entry meA = (Map.Entry)iA.next();
2536 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2538 if( !ogB.td2ln.containsKey(tdA) ) {
2547 protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2548 if( !areallREinAandBequal(this, og) ) {
2555 static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2556 OwnershipGraph ogB) {
2558 // check all the heap region->heap region edges
2559 Set sA = ogA.id2hrn.entrySet();
2560 Iterator iA = sA.iterator();
2561 while( iA.hasNext() ) {
2562 Map.Entry meA = (Map.Entry)iA.next();
2563 Integer idA = (Integer) meA.getKey();
2564 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2566 // we should have already checked that the same
2567 // heap regions exist in both graphs
2568 assert ogB.id2hrn.containsKey(idA);
2570 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2574 // then check every edge in B for presence in A, starting
2575 // from the same parent HeapRegionNode
2576 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2578 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2583 // then check all the label->heap region edges
2584 sA = ogA.td2ln.entrySet();
2586 while( iA.hasNext() ) {
2587 Map.Entry meA = (Map.Entry)iA.next();
2588 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2589 LabelNode lnA = (LabelNode) meA.getValue();
2591 // we should have already checked that the same
2592 // label nodes exist in both graphs
2593 assert ogB.td2ln.containsKey(tdA);
2595 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2599 // then check every edge in B for presence in A, starting
2600 // from the same parent LabelNode
2601 LabelNode lnB = ogB.td2ln.get(tdA);
2603 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2612 static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2614 OwnershipGraph ogB) {
2616 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2617 while( itrA.hasNext() ) {
2618 ReferenceEdge edgeA = itrA.next();
2619 HeapRegionNode hrnChildA = edgeA.getDst();
2620 Integer idChildA = hrnChildA.getID();
2622 assert ogB.id2hrn.containsKey(idChildA);
2624 // at this point we know an edge in graph A exists
2625 // onA -> idChildA, does this exact edge exist in B?
2626 boolean edgeFound = false;
2628 OwnershipNode onB = null;
2629 if( onA instanceof HeapRegionNode ) {
2630 HeapRegionNode hrnA = (HeapRegionNode) onA;
2631 onB = ogB.id2hrn.get(hrnA.getID() );
2633 LabelNode lnA = (LabelNode) onA;
2634 onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2637 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2638 while( itrB.hasNext() ) {
2639 ReferenceEdge edgeB = itrB.next();
2640 HeapRegionNode hrnChildB = edgeB.getDst();
2641 Integer idChildB = hrnChildB.getID();
2643 if( idChildA.equals(idChildB) &&
2644 edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2646 // there is an edge in the right place with the right field,
2647 // but do they have the same attributes?
2648 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2666 protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2667 return id2paramIndexSet.size() == og.id2paramIndexSet.size();
2670 public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
2672 // get parameter's heap region
2673 assert paramIndex2id.containsKey(paramIndex1);
2674 Integer idParam1 = paramIndex2id.get(paramIndex1);
2676 assert id2hrn.containsKey(idParam1);
2677 HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2678 assert hrnParam1 != null;
2680 // get tokens for this parameter
2681 TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2683 TokenTuple.ARITY_ONE).makeCanonical();
2685 TokenTuple pPlus1 = new TokenTuple(hrnParam1.getID(),
2687 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2689 TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2691 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2694 // get tokens for the other parameter
2695 assert paramIndex2id.containsKey(paramIndex2);
2696 Integer idParam2 = paramIndex2id.get(paramIndex2);
2698 assert id2hrn.containsKey(idParam2);
2699 HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2700 assert hrnParam2 != null;
2702 TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2704 TokenTuple.ARITY_ONE).makeCanonical();
2706 TokenTuple pPlus2 = new TokenTuple(hrnParam2.getID(),
2708 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2710 TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2712 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2715 // get special label p_q for first parameter
2716 TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2717 assert tdParamQ1 != null;
2718 LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2719 assert lnParamQ1 != null;
2721 // then get the edge from label q to parameter's hrn
2722 ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2723 assert edgeSpecialQ1 != null;
2725 // if the beta of this edge has tokens from both parameters in one
2726 // token tuple set, then there is a potential alias between them
2727 ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2728 assert beta1 != null;
2730 if( beta1.containsTupleSetWithBoth(p1, p2) ) {
2733 if( beta1.containsTupleSetWithBoth(pPlus1, p2) ) {
2736 if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
2739 if( beta1.containsTupleSetWithBoth(p1, pPlus2) ) {
2742 if( beta1.containsTupleSetWithBoth(pPlus1, pPlus2) ) {
2745 if( beta1.containsTupleSetWithBoth(pStar1, pPlus2) ) {
2748 if( beta1.containsTupleSetWithBoth(p1, pStar2) ) {
2751 if( beta1.containsTupleSetWithBoth(pPlus1, pStar2) ) {
2754 if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
2762 public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
2764 // get parameter's heap region
2765 assert paramIndex2id.containsKey(paramIndex);
2766 Integer idParam = paramIndex2id.get(paramIndex);
2768 assert id2hrn.containsKey(idParam);
2769 HeapRegionNode hrnParam = id2hrn.get(idParam);
2770 assert hrnParam != null;
2772 // get tokens for this parameter
2773 TokenTuple p = new TokenTuple(hrnParam.getID(),
2775 TokenTuple.ARITY_ONE).makeCanonical();
2777 TokenTuple pPlus = new TokenTuple(hrnParam.getID(),
2779 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2781 TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2783 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2785 // get special label p_q
2786 TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2787 assert tdParamQ != null;
2788 LabelNode lnParamQ = td2ln.get(tdParamQ);
2789 assert lnParamQ != null;
2791 // then get the edge from label q to parameter's hrn
2792 ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2793 assert edgeSpecialQ != null;
2795 // look through this beta set for potential aliases
2796 ReachabilitySet beta = edgeSpecialQ.getBeta();
2797 assert beta != null;
2800 // get tokens for summary node
2801 TokenTuple gs = new TokenTuple(as.getSummary(),
2803 TokenTuple.ARITY_ONE).makeCanonical();
2805 TokenTuple gsPlus = new TokenTuple(as.getSummary(),
2807 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2809 TokenTuple gsStar = new TokenTuple(as.getSummary(),
2811 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2814 if( beta.containsTupleSetWithBoth(p, gs) ) {
2817 if( beta.containsTupleSetWithBoth(pPlus, gs) ) {
2820 if( beta.containsTupleSetWithBoth(pStar, gs) ) {
2823 if( beta.containsTupleSetWithBoth(p, gsPlus) ) {
2826 if( beta.containsTupleSetWithBoth(pPlus, gsPlus) ) {
2829 if( beta.containsTupleSetWithBoth(pStar, gsPlus) ) {
2832 if( beta.containsTupleSetWithBoth(p, gsStar) ) {
2835 if( beta.containsTupleSetWithBoth(pPlus, gsStar) ) {
2838 if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
2842 // check for other nodes
2843 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2845 // the other nodes of an allocation site are single, no plus
2846 TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2848 TokenTuple.ARITY_ONE).makeCanonical();
2850 TokenTuple giStar = new TokenTuple(as.getIthOldest(i),
2852 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2854 if( beta.containsTupleSetWithBoth(p, gi) ) {
2857 if( beta.containsTupleSetWithBoth(pPlus, gi) ) {
2860 if( beta.containsTupleSetWithBoth(pStar, gi) ) {
2863 if( beta.containsTupleSetWithBoth(p, giStar) ) {
2866 if( beta.containsTupleSetWithBoth(pPlus, giStar) ) {
2869 if( beta.containsTupleSetWithBoth(pStar, giStar) ) {
2878 public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
2880 // get tokens for summary nodes
2881 TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2883 TokenTuple.ARITY_ONE).makeCanonical();
2885 TokenTuple gsPlus1 = new TokenTuple(as1.getSummary(),
2887 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2889 TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2891 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2893 // get summary node's alpha
2894 Integer idSum1 = as1.getSummary();
2895 assert id2hrn.containsKey(idSum1);
2896 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
2897 assert hrnSum1 != null;
2898 ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2899 assert alphaSum1 != null;
2902 // and for the other one
2903 TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2905 TokenTuple.ARITY_ONE).makeCanonical();
2907 TokenTuple gsPlus2 = new TokenTuple(as2.getSummary(),
2909 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2911 TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2913 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2915 // get summary node's alpha
2916 Integer idSum2 = as2.getSummary();
2917 assert id2hrn.containsKey(idSum2);
2918 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
2919 assert hrnSum2 != null;
2920 ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2921 assert alphaSum2 != null;
2923 // does either one report reachability from the other tokens?
2924 if( alphaSum1.containsTuple(gsPlus2) ) {
2927 if( alphaSum1.containsTuple(gsStar2) ) {
2930 if( alphaSum2.containsTuple(gsPlus1) ) {
2933 if( alphaSum2.containsTuple(gsStar1) ) {
2937 // only check ONE token if they are different sites
2939 if( alphaSum1.containsTuple(gs2) ) {
2942 if( alphaSum2.containsTuple(gs1) ) {
2948 // check sum2 against alloc1 nodes
2949 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2950 Integer idI1 = as1.getIthOldest(i);
2951 assert id2hrn.containsKey(idI1);
2952 HeapRegionNode hrnI1 = id2hrn.get(idI1);
2953 assert hrnI1 != null;
2954 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2955 assert alphaI1 != null;
2957 // the other nodes of an allocation site are single, no stars
2958 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2960 TokenTuple.ARITY_ONE).makeCanonical();
2962 TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(i),
2964 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2966 if( alphaSum2.containsTuple(gi1) ) {
2969 if( alphaSum2.containsTuple(giStar1) ) {
2972 if( alphaI1.containsTuple(gs2) ) {
2975 if( alphaI1.containsTuple(gsPlus2) ) {
2978 if( alphaI1.containsTuple(gsStar2) ) {
2983 // check sum1 against alloc2 nodes
2984 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2985 Integer idI2 = as2.getIthOldest(i);
2986 assert id2hrn.containsKey(idI2);
2987 HeapRegionNode hrnI2 = id2hrn.get(idI2);
2988 assert hrnI2 != null;
2989 ReachabilitySet alphaI2 = hrnI2.getAlpha();
2990 assert alphaI2 != null;
2992 TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2994 TokenTuple.ARITY_ONE).makeCanonical();
2996 TokenTuple giStar2 = new TokenTuple(as2.getIthOldest(i),
2998 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
3000 if( alphaSum1.containsTuple(gi2) ) {
3003 if( alphaSum1.containsTuple(giStar2) ) {
3006 if( alphaI2.containsTuple(gs1) ) {
3009 if( alphaI2.containsTuple(gsPlus1) ) {
3012 if( alphaI2.containsTuple(gsStar1) ) {
3016 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
3017 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
3018 Integer idI1 = as1.getIthOldest(j);
3020 // if these are the same site, don't look for the same token, no alias.
3021 // different tokens of the same site could alias together though
3022 if( idI1 == idI2 ) {
3026 HeapRegionNode hrnI1 = id2hrn.get(idI1);
3027 ReachabilitySet alphaI1 = hrnI1.getAlpha();
3028 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
3030 TokenTuple.ARITY_ONE).makeCanonical();
3032 TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(j),
3034 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
3036 if( alphaI2.containsTuple(gi1) ) {
3039 if( alphaI2.containsTuple(giStar1) ) {
3042 if( alphaI1.containsTuple(gi2) ) {
3045 if( alphaI1.containsTuple(giStar2) ) {
3055 // for writing ownership graphs to dot files
3056 public void writeGraph(MethodContext mc,
3058 boolean writeLabels,
3059 boolean labelSelect,
3060 boolean pruneGarbage,
3061 boolean writeReferencers,
3062 boolean writeParamMappings
3063 ) throws java.io.IOException {
3075 public void writeGraph(MethodContext mc,
3076 boolean writeLabels,
3077 boolean labelSelect,
3078 boolean pruneGarbage,
3079 boolean writeReferencers,
3080 boolean writeParamMappings
3081 ) throws java.io.IOException {
3083 writeGraph(mc+"COMPLETE",
3092 public void writeGraph(MethodContext mc,
3094 boolean writeLabels,
3095 boolean labelSelect,
3096 boolean pruneGarbage,
3097 boolean writeReferencers,
3098 boolean writeParamMappings
3099 ) throws java.io.IOException {
3101 writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate),
3110 public void writeGraph(String graphName,
3111 boolean writeLabels,
3112 boolean labelSelect,
3113 boolean pruneGarbage,
3114 boolean writeReferencers,
3115 boolean writeParamMappings
3116 ) throws java.io.IOException {
3118 // remove all non-word characters from the graph name so
3119 // the filename and identifier in dot don't cause errors
3120 graphName = graphName.replaceAll("[\\W]", "");
3122 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
3123 bw.write("digraph "+graphName+" {\n");
3125 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3127 // then visit every heap region node
3128 Set s = id2hrn.entrySet();
3129 Iterator i = s.iterator();
3130 while( i.hasNext() ) {
3131 Map.Entry me = (Map.Entry)i.next();
3132 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3133 if( !pruneGarbage ||
3135 hrn.getDescription().startsWith("param")
3138 if( !visited.contains(hrn) ) {
3139 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
3149 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
3151 if( writeParamMappings ) {
3152 Set df = paramIndex2id.entrySet();
3153 Iterator ih = df.iterator();
3154 while( ih.hasNext() ) {
3155 Map.Entry meh = (Map.Entry)ih.next();
3156 Integer pi = (Integer) meh.getKey();
3157 Integer id = (Integer) meh.getValue();
3158 bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
3162 // then visit every label node, useful for debugging
3164 s = td2ln.entrySet();
3166 while( i.hasNext() ) {
3167 Map.Entry me = (Map.Entry)i.next();
3168 LabelNode ln = (LabelNode) me.getValue();
3171 String labelStr = ln.getTempDescriptorString();
3172 if( labelStr.startsWith("___temp") ||
3173 labelStr.startsWith("___dst") ||
3174 labelStr.startsWith("___srctmp") ||
3175 labelStr.startsWith("___neverused") ) {
3180 //bw.write(" "+ln.toString() + ";\n");
3182 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
3183 while( heapRegionsItr.hasNext() ) {
3184 ReferenceEdge edge = heapRegionsItr.next();
3185 HeapRegionNode hrn = edge.getDst();
3187 if( pruneGarbage && !visited.contains(hrn) ) {
3188 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
3196 bw.write(" " + ln.toString() +
3197 " -> " + hrn.toString() +
3198 "[label=\"" + edge.toGraphEdgeString() +
3209 protected void traverseHeapRegionNodes(int mode,
3213 HashSet<HeapRegionNode> visited,
3214 boolean writeReferencers
3215 ) throws java.io.IOException {
3217 if( visited.contains(hrn) ) {
3223 case VISIT_HRN_WRITE_FULL:
3225 String attributes = "[";
3227 if( hrn.isSingleObject() ) {
3228 attributes += "shape=box";
3230 attributes += "shape=Msquare";
3233 if( hrn.isFlagged() ) {
3234 attributes += ",style=filled,fillcolor=lightgrey";
3237 attributes += ",label=\"ID" +
3240 hrn.getDescription() +
3242 hrn.getAlphaString() +
3245 bw.write(" " + hrn.toString() + attributes + ";\n");
3250 // useful for debugging
3251 if( writeReferencers ) {
3252 OwnershipNode onRef = null;
3253 Iterator refItr = hrn.iteratorToReferencers();
3254 while( refItr.hasNext() ) {
3255 onRef = (OwnershipNode) refItr.next();
3258 case VISIT_HRN_WRITE_FULL:
3259 bw.write(" " + hrn.toString() +
3260 " -> " + onRef.toString() +
3261 "[color=lightgray];\n");
3267 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
3268 while( childRegionsItr.hasNext() ) {
3269 ReferenceEdge edge = childRegionsItr.next();
3270 HeapRegionNode hrnChild = edge.getDst();
3273 case VISIT_HRN_WRITE_FULL:
3274 bw.write(" " + hrn.toString() +
3275 " -> " + hrnChild.toString() +
3276 "[label=\"" + edge.toGraphEdgeString() +
3281 traverseHeapRegionNodes(mode,