1 package Analysis.OwnershipAnalysis;
8 public class OwnershipGraph {
10 private int allocationDepth;
11 private TypeUtil typeUtil;
13 // there was already one other very similar reason
14 // for traversing heap nodes that is no longer needed
15 // instead of writing a new heap region visitor, use
16 // the existing method with a new mode to describe what
17 // actions to take during the traversal
18 protected static final int VISIT_HRN_WRITE_FULL = 0;
20 protected static TempDescriptor tdReturn = new TempDescriptor("_Return___");
23 public Hashtable<Integer, HeapRegionNode> id2hrn;
24 public Hashtable<TempDescriptor, LabelNode > td2ln;
25 public Hashtable<Integer, Integer > id2paramIndex;
26 public Hashtable<Integer, Integer > paramIndex2id;
27 public Hashtable<Integer, TempDescriptor> paramIndex2tdQ;
29 public HashSet<AllocationSite> allocationSites;
34 public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
35 this.allocationDepth = allocationDepth;
36 this.typeUtil = typeUtil;
38 id2hrn = new Hashtable<Integer, HeapRegionNode>();
39 td2ln = new Hashtable<TempDescriptor, LabelNode >();
40 id2paramIndex = new Hashtable<Integer, Integer >();
41 paramIndex2id = new Hashtable<Integer, Integer >();
42 paramIndex2tdQ = new Hashtable<Integer, TempDescriptor>();
44 allocationSites = new HashSet <AllocationSite>();
48 // label nodes are much easier to deal with than
49 // heap region nodes. Whenever there is a request
50 // for the label node that is associated with a
51 // temp descriptor we can either find it or make a
52 // new one and return it. This is because temp
53 // descriptors are globally unique and every label
54 // node is mapped to exactly one temp descriptor.
55 protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
58 if( !td2ln.containsKey(td) ) {
59 td2ln.put(td, new LabelNode(td) );
66 // the reason for this method is to have the option
67 // creating new heap regions with specific IDs, or
68 // duplicating heap regions with specific IDs (especially
69 // in the merge() operation) or to create new heap
70 // regions with a new unique ID.
71 protected HeapRegionNode
72 createNewHeapRegionNode(Integer id,
73 boolean isSingleObject,
77 AllocationSite allocSite,
78 ReachabilitySet alpha,
82 id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
86 if( isFlagged || isParameter ) {
87 alpha = new ReachabilitySet(
94 alpha = new ReachabilitySet(
95 new TokenTupleSet().makeCanonical()
100 HeapRegionNode hrn = new HeapRegionNode(id,
114 ////////////////////////////////////////////////
116 // Low-level referencee and referencer methods
118 // These methods provide the lowest level for
119 // creating references between ownership nodes
120 // and handling the details of maintaining both
121 // list of referencers and referencees.
123 ////////////////////////////////////////////////
124 protected void addReferenceEdge(OwnershipNode referencer,
125 HeapRegionNode referencee,
126 ReferenceEdge edge) {
127 assert referencer != null;
128 assert referencee != null;
130 assert edge.getSrc() == referencer;
131 assert edge.getDst() == referencee;
133 referencer.addReferencee(edge);
134 referencee.addReferencer(edge);
137 protected void removeReferenceEdge(OwnershipNode referencer,
138 HeapRegionNode referencee,
139 FieldDescriptor fieldDesc) {
140 assert referencer != null;
141 assert referencee != null;
143 ReferenceEdge edge = referencer.getReferenceTo(referencee,
146 assert edge == referencee.getReferenceFrom(referencer,
149 referencer.removeReferencee(edge);
150 referencee.removeReferencer(edge);
153 protected void clearReferenceEdgesFrom(OwnershipNode referencer,
154 FieldDescriptor fieldDesc,
156 assert referencer != null;
158 // get a copy of the set to iterate over, otherwise
159 // we will be trying to take apart the set as we
160 // are iterating over it, which won't work
161 Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
162 while( i.hasNext() ) {
163 ReferenceEdge edge = i.next();
165 if( removeAll || edge.getFieldDesc() == fieldDesc ) {
166 HeapRegionNode referencee = edge.getDst();
168 removeReferenceEdge(referencer,
170 edge.getFieldDesc() );
175 protected void clearReferenceEdgesTo(HeapRegionNode referencee,
176 FieldDescriptor fieldDesc,
178 assert referencee != null;
180 // get a copy of the set to iterate over, otherwise
181 // we will be trying to take apart the set as we
182 // are iterating over it, which won't work
183 Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
184 while( i.hasNext() ) {
185 ReferenceEdge edge = i.next();
187 if( removeAll || edge.getFieldDesc() == fieldDesc ) {
188 OwnershipNode referencer = edge.getSrc();
189 removeReferenceEdge(referencer,
191 edge.getFieldDesc() );
197 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
199 HashSet<HeapRegionNode> nodesWithNewAlpha,
200 HashSet<ReferenceEdge> edgesWithNewBeta) {
202 HashSet<HeapRegionNode> todoNodes
203 = new HashSet<HeapRegionNode>();
204 todoNodes.add(nPrime);
206 HashSet<ReferenceEdge> todoEdges
207 = new HashSet<ReferenceEdge>();
209 Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
210 = new Hashtable<HeapRegionNode, ChangeTupleSet>();
211 nodePlannedChanges.put(nPrime, c0);
213 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
214 = new Hashtable<ReferenceEdge, ChangeTupleSet>();
217 while( !todoNodes.isEmpty() ) {
218 HeapRegionNode n = todoNodes.iterator().next();
219 ChangeTupleSet C = nodePlannedChanges.get(n);
221 Iterator itrC = C.iterator();
222 while( itrC.hasNext() ) {
223 ChangeTuple c = (ChangeTuple) itrC.next();
225 if( n.getAlpha().contains(c.getSetToMatch() ) ) {
226 ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
227 n.setAlphaNew(n.getAlphaNew().union(withChange) );
228 nodesWithNewAlpha.add(n);
232 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
233 while( referItr.hasNext() ) {
234 ReferenceEdge edge = referItr.next();
237 if( !edgePlannedChanges.containsKey(edge) ) {
238 edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
241 edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
244 Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
245 while( refeeItr.hasNext() ) {
246 ReferenceEdge edgeF = refeeItr.next();
247 HeapRegionNode m = edgeF.getDst();
249 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
251 Iterator<ChangeTuple> itrCprime = C.iterator();
252 while( itrCprime.hasNext() ) {
253 ChangeTuple c = itrCprime.next();
254 if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
255 changesToPass = changesToPass.union(c);
259 if( !changesToPass.isEmpty() ) {
260 if( !nodePlannedChanges.containsKey(m) ) {
261 nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
264 ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
266 if( !changesToPass.isSubset(currentChanges) ) {
268 nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
277 propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
281 protected void propagateTokensOverEdges(
282 HashSet<ReferenceEdge> todoEdges,
283 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
284 HashSet<ReferenceEdge> edgesWithNewBeta) {
287 while( !todoEdges.isEmpty() ) {
288 ReferenceEdge edgeE = todoEdges.iterator().next();
289 todoEdges.remove(edgeE);
291 if( !edgePlannedChanges.containsKey(edgeE) ) {
292 edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
295 ChangeTupleSet C = edgePlannedChanges.get(edgeE);
297 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
299 Iterator<ChangeTuple> itrC = C.iterator();
300 while( itrC.hasNext() ) {
301 ChangeTuple c = itrC.next();
302 if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
303 ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
304 edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
305 edgesWithNewBeta.add(edgeE);
306 changesToPass = changesToPass.union(c);
310 OwnershipNode onSrc = edgeE.getSrc();
312 if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
313 HeapRegionNode n = (HeapRegionNode) onSrc;
315 Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
316 while( referItr.hasNext() ) {
317 ReferenceEdge edgeF = referItr.next();
319 if( !edgePlannedChanges.containsKey(edgeF) ) {
320 edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
323 ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
325 if( !changesToPass.isSubset(currentChanges) ) {
326 todoEdges.add(edgeF);
327 edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
335 ////////////////////////////////////////////////////
337 // Assignment Operation Methods
339 // These methods are high-level operations for
340 // modeling program assignment statements using
341 // the low-level reference create/remove methods
344 // The destination in an assignment statement is
345 // going to have new references. The method of
346 // determining the references depends on the type
347 // of the FlatNode assignment and the predicates
348 // of the nodes and edges involved.
350 ////////////////////////////////////////////////////
351 public void assignTempXEqualToTempY(TempDescriptor x,
354 LabelNode lnX = getLabelNodeFromTemp(x);
355 LabelNode lnY = getLabelNodeFromTemp(y);
357 clearReferenceEdgesFrom(lnX, null, true);
359 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
360 while( itrYhrn.hasNext() ) {
361 ReferenceEdge edgeY = itrYhrn.next();
362 HeapRegionNode referencee = edgeY.getDst();
363 ReferenceEdge edgeNew = edgeY.copy();
366 addReferenceEdge(lnX, referencee, edgeNew);
371 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
374 LabelNode lnX = getLabelNodeFromTemp(x);
375 LabelNode lnY = getLabelNodeFromTemp(y);
377 clearReferenceEdgesFrom(lnX, null, true);
379 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
380 while( itrYhrn.hasNext() ) {
381 ReferenceEdge edgeY = itrYhrn.next();
382 HeapRegionNode hrnY = edgeY.getDst();
383 ReachabilitySet betaY = edgeY.getBeta();
385 Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
386 while( itrHrnFhrn.hasNext() ) {
387 ReferenceEdge edgeHrn = itrHrnFhrn.next();
388 HeapRegionNode hrnHrn = edgeHrn.getDst();
389 ReachabilitySet betaHrn = edgeHrn.getBeta();
391 if( edgeHrn.getFieldDesc() == null ||
392 edgeHrn.getFieldDesc() == f ) {
394 ReferenceEdge edgeNew = new ReferenceEdge(lnX,
398 betaY.intersection(betaHrn) );
400 addReferenceEdge(lnX, hrnHrn, edgeNew);
407 public void assignTempXFieldFEqualToTempY(TempDescriptor x,
410 LabelNode lnX = getLabelNodeFromTemp(x);
411 LabelNode lnY = getLabelNodeFromTemp(y);
413 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
414 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
417 // first look for possible strong updates and remove those edges
418 boolean strongUpdate = false;
420 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
421 while( itrXhrn.hasNext() ) {
422 ReferenceEdge edgeX = itrXhrn.next();
423 HeapRegionNode hrnX = edgeX.getDst();
425 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
426 while( itrYhrn.hasNext() ) {
427 ReferenceEdge edgeY = itrYhrn.next();
428 HeapRegionNode hrnY = edgeY.getDst();
430 // we can do a strong update here if one of two cases holds
432 hrnX.isSingleObject() &&
433 ( (hrnX.getNumReferencers() == 1) ||
434 ( lnX.getNumReferencees() == 1)
438 clearReferenceEdgesFrom( hrnX, f, false );
444 // then do all token propagation
445 itrXhrn = lnX.iteratorToReferencees();
446 while( itrXhrn.hasNext() ) {
447 ReferenceEdge edgeX = itrXhrn.next();
448 HeapRegionNode hrnX = edgeX.getDst();
449 ReachabilitySet betaX = edgeX.getBeta();
451 ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
453 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
454 while( itrYhrn.hasNext() ) {
455 ReferenceEdge edgeY = itrYhrn.next();
456 HeapRegionNode hrnY = edgeY.getDst();
457 ReachabilitySet O = edgeY.getBeta();
460 // propagate tokens over nodes starting from hrnSrc, and it will
461 // take care of propagating back up edges from any touched nodes
462 ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
463 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
466 // then propagate back just up the edges from hrn
467 ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
470 HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
472 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
473 new Hashtable<ReferenceEdge, ChangeTupleSet>();
475 Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
476 while( referItr.hasNext() ) {
477 ReferenceEdge edgeUpstream = referItr.next();
478 todoEdges.add(edgeUpstream);
479 edgePlannedChanges.put(edgeUpstream, Cx);
482 propagateTokensOverEdges(todoEdges,
489 // apply the updates to reachability
490 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
491 while( nodeItr.hasNext() ) {
492 nodeItr.next().applyAlphaNew();
495 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
496 while( edgeItr.hasNext() ) {
497 edgeItr.next().applyBetaNew();
501 // then go back through and add the new edges
502 itrXhrn = lnX.iteratorToReferencees();
503 while( itrXhrn.hasNext() ) {
504 ReferenceEdge edgeX = itrXhrn.next();
505 HeapRegionNode hrnX = edgeX.getDst();
507 Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
508 while( itrYhrn.hasNext() ) {
509 ReferenceEdge edgeY = itrYhrn.next();
510 HeapRegionNode hrnY = edgeY.getDst();
512 // prepare the new reference edge hrnX.f -> hrnY
513 ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
517 edgeY.getBeta().pruneBy( hrnX.getAlpha() )
520 // look to see if an edge with same field exists
521 // and merge with it, otherwise just add the edge
522 ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
524 if( edgeExisting != null ) {
525 edgeExisting.setBeta(
526 edgeExisting.getBeta().union( edgeNew.getBeta() )
528 // a new edge here cannot be reflexive, so existing will
529 // always be also not reflexive anymore
530 edgeExisting.setIsInitialParamReflexive( false );
532 addReferenceEdge( hrnX, hrnY, edgeNew );
538 // if there was a strong update, make sure to improve
539 // reachability with a global sweep
546 public void assignTempEqualToParamAlloc(TempDescriptor td,
548 Integer paramIndex) {
551 LabelNode lnParam = getLabelNodeFromTemp(td);
552 HeapRegionNode hrn = createNewHeapRegionNode(null,
559 "param" + paramIndex);
561 // this is a non-program-accessible label that picks up beta
562 // info to be used for fixing a caller of this method
563 TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
564 LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
566 // keep track of heap regions that were created for
567 // parameter labels, the index of the parameter they
568 // are for is important when resolving method calls
569 Integer newID = hrn.getID();
570 assert !id2paramIndex.containsKey(newID);
571 assert !id2paramIndex.containsValue(paramIndex);
572 id2paramIndex.put(newID, paramIndex);
573 paramIndex2id.put(paramIndex, newID);
574 paramIndex2tdQ.put(paramIndex, tdParamQ);
576 ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
578 TokenTuple.ARITY_ONE).makeCanonical()
581 // heap regions for parameters are always multiple object (see above)
582 // and have a reference to themselves, because we can't know the
583 // structure of memory that is passed into the method. We're assuming
586 ReferenceEdge edgeFromLabel =
587 new ReferenceEdge(lnParam, hrn, null, false, beta);
589 ReferenceEdge edgeFromLabelQ =
590 new ReferenceEdge(lnParamQ, hrn, null, false, beta);
592 ReferenceEdge edgeReflexive =
593 new ReferenceEdge(hrn, hrn, null, true, beta);
595 addReferenceEdge(lnParam, hrn, edgeFromLabel);
596 addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
597 addReferenceEdge(hrn, hrn, edgeReflexive);
601 public void assignReturnEqualToTemp(TempDescriptor x) {
603 LabelNode lnR = getLabelNodeFromTemp(tdReturn);
604 LabelNode lnX = getLabelNodeFromTemp(x);
606 clearReferenceEdgesFrom(lnR, null, true);
608 Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
609 while( itrXhrn.hasNext() ) {
610 ReferenceEdge edgeX = itrXhrn.next();
611 HeapRegionNode referencee = edgeX.getDst();
612 ReferenceEdge edgeNew = edgeX.copy();
615 addReferenceEdge(lnR, referencee, edgeNew);
620 public void assignTempEqualToNewAlloc(TempDescriptor x,
627 // after the age operation the newest (or zero-ith oldest)
628 // node associated with the allocation site should have
629 // no references to it as if it were a newly allocated
630 // heap region, so make a reference to it to complete
633 Integer idNewest = as.getIthOldest(0);
634 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
635 assert hrnNewest != null;
637 LabelNode lnX = getLabelNodeFromTemp(x);
638 clearReferenceEdgesFrom(lnX, null, true);
640 ReferenceEdge edgeNew =
641 new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
643 addReferenceEdge(lnX, hrnNewest, edgeNew);
647 // use the allocation site (unique to entire analysis) to
648 // locate the heap region nodes in this ownership graph
649 // that should be aged. The process models the allocation
650 // of new objects and collects all the oldest allocations
651 // in a summary node to allow for a finite analysis
653 // There is an additional property of this method. After
654 // running it on a particular ownership graph (many graphs
655 // may have heap regions related to the same allocation site)
656 // the heap region node objects in this ownership graph will be
657 // allocated. Therefore, after aging a graph for an allocation
658 // site, attempts to retrieve the heap region nodes using the
659 // integer id's contained in the allocation site should always
660 // return non-null heap regions.
661 public void age(AllocationSite as) {
663 // aging adds this allocation site to the graph's
664 // list of sites that exist in the graph, or does
665 // nothing if the site is already in the list
666 allocationSites.add(as);
668 // get the summary node for the allocation site in the context
669 // of this particular ownership graph
670 HeapRegionNode hrnSummary = getSummaryNode(as);
672 // merge oldest node into summary
673 Integer idK = as.getOldest();
674 HeapRegionNode hrnK = id2hrn.get(idK);
675 mergeIntoSummary(hrnK, hrnSummary);
677 // move down the line of heap region nodes
678 // clobbering the ith and transferring all references
679 // to and from i-1 to node i. Note that this clobbers
680 // the oldest node (hrnK) that was just merged into
682 for( int i = allocationDepth - 1; i > 0; --i ) {
684 // move references from the i-1 oldest to the ith oldest
685 Integer idIth = as.getIthOldest(i);
686 HeapRegionNode hrnI = id2hrn.get(idIth);
687 Integer idImin1th = as.getIthOldest(i - 1);
688 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
690 transferOnto(hrnImin1, hrnI);
693 // as stated above, the newest node should have had its
694 // references moved over to the second oldest, so we wipe newest
695 // in preparation for being the new object to assign something to
696 Integer id0th = as.getIthOldest(0);
697 HeapRegionNode hrn0 = id2hrn.get(id0th);
700 // clear all references in and out of newest node
701 clearReferenceEdgesFrom(hrn0, null, true);
702 clearReferenceEdgesTo(hrn0, null, true);
705 // now tokens in reachability sets need to "age" also
706 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
707 while( itrAllLabelNodes.hasNext() ) {
708 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
709 LabelNode ln = (LabelNode) me.getValue();
711 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
712 while( itrEdges.hasNext() ) {
713 ageTokens(as, itrEdges.next() );
717 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
718 while( itrAllHRNodes.hasNext() ) {
719 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
720 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
722 ageTokens(as, hrnToAge);
724 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
725 while( itrEdges.hasNext() ) {
726 ageTokens(as, itrEdges.next() );
731 // after tokens have been aged, reset newest node's reachability
732 if( hrn0.isFlagged() ) {
733 hrn0.setAlpha(new ReachabilitySet(
735 new TokenTuple(hrn0).makeCanonical()
740 hrn0.setAlpha(new ReachabilitySet(
741 new TokenTupleSet().makeCanonical()
748 protected HeapRegionNode getSummaryNode(AllocationSite as) {
750 Integer idSummary = as.getSummary();
751 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
753 // If this is null then we haven't touched this allocation site
754 // in the context of the current ownership graph, so allocate
755 // heap region nodes appropriate for the entire allocation site.
756 // This should only happen once per ownership graph per allocation site,
757 // and a particular integer id can be used to locate the heap region
758 // in different ownership graphs that represents the same part of an
760 if( hrnSummary == null ) {
762 boolean hasFlags = false;
763 if( as.getType().isClass() ) {
764 hasFlags = as.getType().getClassDesc().hasFlags();
767 hrnSummary = createNewHeapRegionNode(idSummary,
774 as + "\\n" + as.getType() + "\\nsummary");
776 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
777 Integer idIth = as.getIthOldest(i);
778 assert !id2hrn.containsKey(idIth);
779 createNewHeapRegionNode(idIth,
786 as + "\\n" + as.getType() + "\\n" + i + " oldest");
794 protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
796 Integer idShadowSummary = as.getSummaryShadow();
797 HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
799 if( hrnShadowSummary == null ) {
801 boolean hasFlags = false;
802 if( as.getType().isClass() ) {
803 hasFlags = as.getType().getClassDesc().hasFlags();
806 hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
813 as + "\\n" + as.getType() + "\\nshadowSum");
815 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
816 Integer idShadowIth = as.getIthOldestShadow(i);
817 assert !id2hrn.containsKey(idShadowIth);
818 createNewHeapRegionNode(idShadowIth,
825 as + "\\n" + as.getType() + "\\n" + i + " shadow");
829 return hrnShadowSummary;
833 protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
834 assert hrnSummary.isNewSummary();
836 // transfer references _from_ hrn over to hrnSummary
837 Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
838 while( itrReferencee.hasNext() ) {
839 ReferenceEdge edge = itrReferencee.next();
840 ReferenceEdge edgeMerged = edge.copy();
841 edgeMerged.setSrc(hrnSummary);
843 HeapRegionNode hrnReferencee = edge.getDst();
844 ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
846 if( edgeSummary == null ) {
847 // the merge is trivial, nothing to be done
849 // otherwise an edge from the referencer to hrnSummary exists already
850 // and the edge referencer->hrn should be merged with it
851 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
854 addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
857 // next transfer references _to_ hrn over to hrnSummary
858 Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
859 while( itrReferencer.hasNext() ) {
860 ReferenceEdge edge = itrReferencer.next();
861 ReferenceEdge edgeMerged = edge.copy();
862 edgeMerged.setDst(hrnSummary);
864 OwnershipNode onReferencer = edge.getSrc();
865 ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
867 if( edgeSummary == null ) {
868 // the merge is trivial, nothing to be done
870 // otherwise an edge from the referencer to alpha_S exists already
871 // and the edge referencer->alpha_K should be merged with it
872 edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
875 addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
878 // then merge hrn reachability into hrnSummary
879 hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
883 protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
885 // clear references in and out of node b
886 clearReferenceEdgesFrom(hrnB, null, true);
887 clearReferenceEdgesTo(hrnB, null, true);
889 // copy each edge in and out of A to B
890 Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
891 while( itrReferencee.hasNext() ) {
892 ReferenceEdge edge = itrReferencee.next();
893 HeapRegionNode hrnReferencee = edge.getDst();
894 ReferenceEdge edgeNew = edge.copy();
895 edgeNew.setSrc(hrnB);
897 addReferenceEdge(hrnB, hrnReferencee, edgeNew);
900 Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
901 while( itrReferencer.hasNext() ) {
902 ReferenceEdge edge = itrReferencer.next();
903 OwnershipNode onReferencer = edge.getSrc();
904 ReferenceEdge edgeNew = edge.copy();
905 edgeNew.setDst(hrnB);
907 addReferenceEdge(onReferencer, hrnB, edgeNew);
910 // replace hrnB reachability with hrnA's
911 hrnB.setAlpha(hrnA.getAlpha() );
915 protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
916 edge.setBeta(edge.getBeta().ageTokens(as) );
919 protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
920 hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
924 public void resolveMethodCall(FlatCall fc,
927 OwnershipGraph ogCallee) {
929 // define rewrite rules and other structures to organize
930 // data by parameter/argument index
931 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
932 new Hashtable<Integer, ReachabilitySet>();
934 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
935 new Hashtable<Integer, ReachabilitySet>();
937 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
938 new Hashtable<Integer, ReachabilitySet>();
940 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d =
941 new Hashtable<Integer, ReachabilitySet>();
943 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
944 new Hashtable<Integer, ReachabilitySet>();
946 // helpful structures
947 Hashtable<TokenTuple, Integer> paramToken2paramIndex =
948 new Hashtable<TokenTuple, Integer>();
950 Hashtable<Integer, TokenTuple> paramIndex2paramToken =
951 new Hashtable<Integer, TokenTuple>();
953 Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex =
954 new Hashtable<TokenTuple, Integer>();
956 Hashtable<Integer, TokenTuple> paramIndex2paramTokenPlus =
957 new Hashtable<Integer, TokenTuple>();
959 Hashtable<Integer, LabelNode> paramIndex2ln =
960 new Hashtable<Integer, LabelNode>();
962 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
963 new Hashtable<Integer, HashSet<HeapRegionNode> >();
966 // add a bogus entry with the identity rule for easy rewrite
967 // of new callee nodes and edges, doesn't belong to any parameter
968 Integer bogusID = new Integer(-1);
969 Integer bogusIndex = new Integer(-1);
970 TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE).makeCanonical();
971 TokenTuple bogusTokenPlus = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONEORMORE).makeCanonical();
972 ReachabilitySet rsIdentity =
974 new TokenTupleSet(bogusToken).makeCanonical()
977 paramIndex2rewriteH.put(bogusIndex, rsIdentity);
978 paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
979 paramToken2paramIndex.put(bogusToken, bogusIndex);
980 paramIndex2paramToken.put(bogusIndex, bogusToken);
981 paramTokenPlus2paramIndex.put(bogusTokenPlus, bogusIndex);
982 paramIndex2paramTokenPlus.put(bogusIndex, bogusTokenPlus);
985 for( int i = 0; i < fm.numParameters(); ++i ) {
986 Integer paramIndex = new Integer(i);
988 assert ogCallee.paramIndex2id.containsKey(paramIndex);
989 Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
991 assert ogCallee.id2hrn.containsKey(idParam);
992 HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
993 assert hrnParam != null;
994 paramIndex2rewriteH.put(paramIndex,
996 toShadowTokens(ogCallee, hrnParam.getAlpha() )
999 ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
1000 assert edgeReflexive_i != null;
1001 paramIndex2rewriteJ.put(paramIndex,
1002 toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
1005 TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
1006 assert tdParamQ != null;
1007 LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
1008 assert lnParamQ != null;
1009 ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
1010 assert edgeSpecialQ_i != null;
1011 paramIndex2rewriteK.put(paramIndex,
1012 toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
1015 TokenTuple p_i = new TokenTuple(hrnParam.getID(),
1017 TokenTuple.ARITY_ONE).makeCanonical();
1018 paramToken2paramIndex.put(p_i, paramIndex);
1019 paramIndex2paramToken.put(paramIndex, p_i);
1021 TokenTuple p_i_plus = new TokenTuple(hrnParam.getID(),
1023 TokenTuple.ARITY_ONEORMORE).makeCanonical();
1024 paramTokenPlus2paramIndex.put(p_i_plus, paramIndex);
1025 paramIndex2paramTokenPlus.put(paramIndex, p_i_plus);
1027 // now depending on whether the callee is static or not
1028 // we need to account for a "this" argument in order to
1029 // find the matching argument in the caller context
1030 TempDescriptor argTemp_i;
1032 argTemp_i = fc.getArg(paramIndex);
1034 if( paramIndex.equals(0) ) {
1035 argTemp_i = fc.getThis();
1037 argTemp_i = fc.getArg(paramIndex - 1);
1041 // in non-static methods there is a "this" pointer
1042 // that should be taken into account
1044 assert fc.numArgs() == fm.numParameters();
1046 assert fc.numArgs() + 1 == fm.numParameters();
1049 LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1050 paramIndex2ln.put(paramIndex, argLabel_i);
1052 ReachabilitySet d_i = new ReachabilitySet().makeCanonical();
1053 Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1054 while( edgeItr.hasNext() ) {
1055 ReferenceEdge edge = edgeItr.next();
1056 d_i = d_i.union(edge.getBeta());
1058 paramIndex2rewrite_d.put(paramIndex, d_i);
1060 ReachabilitySet D_i = d_i.exhaustiveArityCombinations();
1061 paramIndex2rewriteD.put(paramIndex, D_i);
1065 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1066 HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
1068 HashSet<ReferenceEdge> edgesReachable = new HashSet<ReferenceEdge>();
1069 HashSet<ReferenceEdge> edgesUpstream = new HashSet<ReferenceEdge>();
1071 Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1072 while( lnArgItr.hasNext() ) {
1073 Map.Entry me = (Map.Entry)lnArgItr.next();
1074 Integer index = (Integer) me.getKey();
1075 LabelNode lnArg_i = (LabelNode) me.getValue();
1077 // rewrite alpha for the nodes reachable from argument label i
1078 HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1079 HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1081 // to find all reachable nodes, start with label referencees
1082 Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1083 while( edgeArgItr.hasNext() ) {
1084 ReferenceEdge edge = edgeArgItr.next();
1085 todoNodes.add(edge.getDst() );
1088 // then follow links until all reachable nodes have been found
1089 while( !todoNodes.isEmpty() ) {
1090 HeapRegionNode hrn = todoNodes.iterator().next();
1091 todoNodes.remove(hrn);
1092 reachableNodes.add(hrn);
1094 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1095 while( edgeItr.hasNext() ) {
1096 ReferenceEdge edge = edgeItr.next();
1098 if( !reachableNodes.contains(edge.getDst() ) ) {
1099 todoNodes.add(edge.getDst() );
1105 paramIndex2reachableCallerNodes.put(index, reachableNodes);
1107 // now iterate over reachable nodes to update their alpha, and
1108 // classify edges found as "argument reachable" or "upstream"
1109 Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1110 while( hrnItr.hasNext() ) {
1111 HeapRegionNode hrn = hrnItr.next();
1113 rewriteCallerReachability(index,
1116 paramIndex2rewriteH.get(index),
1117 paramIndex2rewrite_d,
1118 paramIndex2rewriteD,
1119 paramIndex2paramToken.get(index),
1120 paramToken2paramIndex,
1121 paramTokenPlus2paramIndex,
1125 nodesWithNewAlpha.add(hrn);
1127 // look at all incoming edges to the reachable nodes
1128 // and sort them as edges reachable from the argument
1129 // label node, or upstream edges
1130 Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1131 while( edgeItr.hasNext() ) {
1132 ReferenceEdge edge = edgeItr.next();
1134 OwnershipNode on = edge.getSrc();
1136 if( on instanceof LabelNode ) {
1138 LabelNode ln0 = (LabelNode) on;
1139 if( ln0.equals(lnArg_i) ) {
1140 edgesReachable.add(edge);
1142 edgesUpstream.add(edge);
1147 HeapRegionNode hrn0 = (HeapRegionNode) on;
1148 if( reachableNodes.contains(hrn0) ) {
1149 edgesReachable.add(edge);
1151 edgesUpstream.add(edge);
1157 // update reachable edges
1158 Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1159 while( edgeReachableItr.hasNext() ) {
1160 ReferenceEdge edgeReachable = edgeReachableItr.next();
1162 rewriteCallerReachability(index,
1165 paramIndex2rewriteJ.get(index),
1166 paramIndex2rewrite_d,
1167 paramIndex2rewriteD,
1168 paramIndex2paramToken.get(index),
1169 paramToken2paramIndex,
1170 paramTokenPlus2paramIndex,
1174 edgesWithNewBeta.add(edgeReachable);
1177 // update upstream edges
1178 Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
1179 new Hashtable<ReferenceEdge, ChangeTupleSet>();
1181 Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1182 while( edgeUpstreamItr.hasNext() ) {
1183 ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1185 rewriteCallerReachability(index,
1188 paramIndex2rewriteK.get(index),
1189 paramIndex2rewrite_d,
1190 paramIndex2rewriteD,
1191 paramIndex2paramToken.get(index),
1192 paramToken2paramIndex,
1193 paramTokenPlus2paramIndex,
1195 edgeUpstreamPlannedChanges);
1197 edgesWithNewBeta.add(edgeUpstream);
1200 propagateTokensOverEdges(edgesUpstream,
1201 edgeUpstreamPlannedChanges,
1206 // commit changes to alpha and beta
1207 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1208 while( nodeItr.hasNext() ) {
1209 nodeItr.next().applyAlphaNew();
1212 Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1213 while( edgeItr.hasNext() ) {
1214 edgeItr.next().applyBetaNew();
1220 // check for parameters that are aliased prior to this call site
1221 // if so, come to a grinding halt. Later, we should move this
1222 // up before doing any alpha/beta updates
1223 for( int i = 0; i < fm.numParameters(); ++i ) {
1224 for( int j = 0; j < i; ++j ) {
1225 HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
1226 HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
1228 Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
1229 intersection.retainAll(s2);
1231 if( !intersection.isEmpty() ) {
1233 System.out.println( " Arguments "+j+" and "+i+" are aliased just before" );
1234 System.out.println( " "+fc+" calls "+fm+"\n" );
1235 //System.exit( -1 );
1243 // verify the existence of allocation sites and their
1244 // shadows from the callee in the context of this caller graph
1245 // then map allocated nodes of callee onto the caller shadows
1247 Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1248 while( asItr.hasNext() ) {
1249 AllocationSite allocSite = asItr.next();
1251 // grab the summary in the caller just to make sure
1252 // the allocation site has nodes in the caller
1253 HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1255 // assert that the shadow nodes have no reference edges
1256 // because they're brand new to the graph, or last time
1257 // they were used they should have been cleared of edges
1258 HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1259 assert hrnShadowSummary.getNumReferencers() == 0;
1260 assert hrnShadowSummary.getNumReferencees() == 0;
1262 // then bring g_ij onto g'_ij and rewrite
1263 HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1264 hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1266 // shadow nodes only are touched by a rewrite one time,
1267 // so rewrite and immediately commit--and they don't belong
1268 // to a particular parameter, so use a bogus param index
1269 // that pulls a self-rewrite out of H
1270 rewriteCallerReachability(bogusIndex,
1273 hrnShadowSummary.getAlpha(),
1274 paramIndex2rewrite_d,
1275 paramIndex2rewriteD,
1277 paramToken2paramIndex,
1278 paramTokenPlus2paramIndex,
1282 hrnShadowSummary.applyAlphaNew();
1285 for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1286 Integer idIth = allocSite.getIthOldest(i);
1287 assert id2hrn.containsKey(idIth);
1288 HeapRegionNode hrnIth = id2hrn.get(idIth);
1290 Integer idShadowIth = -(allocSite.getIthOldest(i));
1291 assert id2hrn.containsKey(idShadowIth);
1292 HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1293 assert hrnIthShadow.getNumReferencers() == 0;
1294 assert hrnIthShadow.getNumReferencees() == 0;
1296 assert ogCallee.id2hrn.containsKey(idIth);
1297 HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1298 hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1300 rewriteCallerReachability(bogusIndex,
1303 hrnIthShadow.getAlpha(),
1304 paramIndex2rewrite_d,
1305 paramIndex2rewriteD,
1307 paramToken2paramIndex,
1308 paramTokenPlus2paramIndex,
1312 hrnIthShadow.applyAlphaNew();
1317 // for every heap region->heap region edge in the
1318 // callee graph, create the matching edge or edges
1319 // in the caller graph
1320 Set sCallee = ogCallee.id2hrn.entrySet();
1321 Iterator iCallee = sCallee.iterator();
1322 while( iCallee.hasNext() ) {
1323 Map.Entry meCallee = (Map.Entry)iCallee.next();
1324 Integer idCallee = (Integer) meCallee.getKey();
1325 HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1327 Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1328 while( heapRegionsItrCallee.hasNext() ) {
1329 ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
1330 HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1331 Integer idChildCallee = hrnChildCallee.getID();
1333 // only address this edge if it is not a special reflexive edge
1334 if( !edgeCallee.isInitialParamReflexive() ) {
1336 // now we know that in the callee method's ownership graph
1337 // there is a heap region->heap region reference edge given
1338 // by heap region pointers:
1339 // hrnCallee -> heapChildCallee
1341 // or by the ownership-graph independent ID's:
1342 // idCallee -> idChildCallee
1344 // make the edge with src and dst so beta info is
1345 // calculated once, then copy it for each new edge in caller
1346 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1348 edgeCallee.getFieldDesc(),
1350 toShadowTokens(ogCallee,
1351 edgeCallee.getBeta() )
1353 rewriteCallerReachability(bogusIndex,
1355 edgeNewInCallerTemplate,
1356 edgeNewInCallerTemplate.getBeta(),
1357 paramIndex2rewrite_d,
1358 paramIndex2rewriteD,
1360 paramToken2paramIndex,
1361 paramTokenPlus2paramIndex,
1365 edgeNewInCallerTemplate.applyBetaNew();
1368 // So now make a set of possible source heaps in the caller graph
1369 // and a set of destination heaps in the caller graph, and make
1370 // a reference edge in the caller for every possible (src,dst) pair
1371 HashSet<HeapRegionNode> possibleCallerSrcs =
1372 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1373 (HeapRegionNode) edgeCallee.getSrc(),
1374 paramIndex2reachableCallerNodes);
1376 HashSet<HeapRegionNode> possibleCallerDsts =
1377 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1378 edgeCallee.getDst(),
1379 paramIndex2reachableCallerNodes);
1382 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1383 Iterator srcItr = possibleCallerSrcs.iterator();
1384 while( srcItr.hasNext() ) {
1385 HeapRegionNode src = (HeapRegionNode) srcItr.next();
1387 if( !hasMatchingField(src, edgeCallee) ) {
1388 // prune this source node possibility
1392 Iterator dstItr = possibleCallerDsts.iterator();
1393 while( dstItr.hasNext() ) {
1394 HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1396 if( !hasMatchingType(edgeCallee, dst) ) {
1401 // otherwise the caller src and dst pair can match the edge, so make it
1402 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1403 edgeNewInCaller.setSrc(src);
1404 edgeNewInCaller.setDst(dst);
1406 ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1407 if( edgeExisting == null ) {
1408 // if this edge doesn't exist in the caller, create it
1409 addReferenceEdge(src, dst, edgeNewInCaller);
1411 // if it already exists, merge with it
1412 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1421 // return value may need to be assigned in caller
1422 TempDescriptor returnTemp = fc.getReturnTemp();
1423 if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
1425 LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
1426 clearReferenceEdgesFrom(lnLhsCaller, null, true);
1428 LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1429 Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1430 while( edgeCalleeItr.hasNext() ) {
1431 ReferenceEdge edgeCallee = edgeCalleeItr.next();
1433 ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1435 edgeCallee.getFieldDesc(),
1437 toShadowTokens(ogCallee,
1438 edgeCallee.getBeta() )
1440 rewriteCallerReachability(bogusIndex,
1442 edgeNewInCallerTemplate,
1443 edgeNewInCallerTemplate.getBeta(),
1444 paramIndex2rewrite_d,
1445 paramIndex2rewriteD,
1447 paramToken2paramIndex,
1448 paramTokenPlus2paramIndex,
1452 edgeNewInCallerTemplate.applyBetaNew();
1455 HashSet<HeapRegionNode> assignCallerRhs =
1456 getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1457 edgeCallee.getDst(),
1458 paramIndex2reachableCallerNodes);
1460 Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1461 while( itrHrn.hasNext() ) {
1462 HeapRegionNode hrnCaller = itrHrn.next();
1464 if( !hasMatchingType(edgeCallee, hrnCaller) ) {
1469 // otherwise caller node can match callee edge, so make it
1470 ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1471 edgeNewInCaller.setSrc(lnLhsCaller);
1472 edgeNewInCaller.setDst(hrnCaller);
1474 ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1475 if( edgeExisting == null ) {
1477 // if this edge doesn't exist in the caller, create it
1478 addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1480 // if it already exists, merge with it
1481 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1488 // merge the shadow nodes of allocation sites back down to normal capacity
1489 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1490 while( allocItr.hasNext() ) {
1491 AllocationSite as = allocItr.next();
1493 // first age each allocation site enough times to make room for the shadow nodes
1494 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1498 // then merge the shadow summary into the normal summary
1499 HeapRegionNode hrnSummary = getSummaryNode(as);
1500 assert hrnSummary != null;
1502 HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1503 assert hrnSummaryShadow != null;
1505 mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1507 // then clear off after merge
1508 clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1509 clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1510 hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1512 // then transplant shadow nodes onto the now clean normal nodes
1513 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1515 Integer idIth = as.getIthOldest(i);
1516 HeapRegionNode hrnIth = id2hrn.get(idIth);
1518 Integer idIthShadow = as.getIthOldestShadow(i);
1519 HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1521 transferOnto(hrnIthShadow, hrnIth);
1523 // clear off shadow nodes after transfer
1524 clearReferenceEdgesFrom(hrnIthShadow, null, true);
1525 clearReferenceEdgesTo(hrnIthShadow, null, true);
1526 hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1529 // finally, globally change shadow tokens into normal tokens
1530 Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1531 while( itrAllLabelNodes.hasNext() ) {
1532 Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1533 LabelNode ln = (LabelNode) me.getValue();
1535 Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1536 while( itrEdges.hasNext() ) {
1537 unshadowTokens(as, itrEdges.next() );
1541 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1542 while( itrAllHRNodes.hasNext() ) {
1543 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
1544 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1546 unshadowTokens(as, hrnToAge);
1548 Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1549 while( itrEdges.hasNext() ) {
1550 unshadowTokens(as, itrEdges.next() );
1555 // improve reachability as much as possible
1560 protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
1562 // if no allocation site, then it's a match-everything region
1563 AllocationSite asSrc = src.getAllocationSite();
1564 if( asSrc == null ) {
1568 TypeDescriptor tdSrc = asSrc.getType();
1569 assert tdSrc != null;
1571 // if it's not a class, it doesn't have any fields to match
1572 if( !tdSrc.isClass() ) {
1576 Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
1577 while( fieldsSrcItr.hasNext() ) {
1578 FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1579 if( fd == edge.getFieldDesc() ) {
1584 // otherwise it is a class with fields
1585 // but we didn't find a match
1590 protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
1592 // if the region has no type, matches everything
1593 AllocationSite asDst = dst.getAllocationSite();
1594 if( asDst == null ) {
1598 TypeDescriptor tdDst = asDst.getType();
1599 assert tdDst != null;
1601 // if the type is not a class don't match because
1602 // primitives are copied, no memory aliases
1603 ClassDescriptor cdDst = tdDst.getClassDesc();
1604 if( cdDst == null ) {
1608 // if the field is null, it matches everything
1609 FieldDescriptor fd = edge.getFieldDesc();
1613 TypeDescriptor tdFd = fd.getType();
1614 assert tdFd != null;
1616 return typeUtil.isSuperorType(tdFd, tdDst);
1621 protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1622 edge.setBeta(edge.getBeta().unshadowTokens(as) );
1625 protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1626 hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1630 private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1631 ReachabilitySet rsIn) {
1633 ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical();
1635 Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1636 while( allocItr.hasNext() ) {
1637 AllocationSite as = allocItr.next();
1639 rsOut = rsOut.toShadowTokens(as);
1642 return rsOut.makeCanonical();
1646 private void rewriteCallerReachability(Integer paramIndex,
1649 ReachabilitySet rules,
1650 Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d,
1651 Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1653 Hashtable<TokenTuple, Integer> paramToken2paramIndex,
1654 Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex,
1655 boolean makeChangeSet,
1656 Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1657 assert(hrn == null && edge != null) ||
1658 (hrn != null && edge == null);
1660 assert rules != null;
1663 ReachabilitySet callerReachabilityCurrent;
1665 callerReachabilityCurrent = edge.getBeta();
1667 callerReachabilityCurrent = hrn.getAlpha();
1670 ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
1672 // for initializing structures in this method
1673 TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
1675 // use this to construct a change set if required; the idea is to
1676 // map every partially rewritten token tuple set to the set of
1677 // caller-context token tuple sets that were used to generate it
1678 Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
1679 new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
1680 rewritten2source.put(ttsEmpty, new HashSet<TokenTupleSet>() );
1683 Iterator<TokenTupleSet> rulesItr = rules.iterator();
1684 while(rulesItr.hasNext()) {
1685 TokenTupleSet rule = rulesItr.next();
1687 ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
1689 Iterator<TokenTuple> ruleItr = rule.iterator();
1690 while(ruleItr.hasNext()) {
1691 TokenTuple ttCallee = ruleItr.next();
1693 // compute the possibilities for rewriting this callee token
1694 ReachabilitySet ttCalleeRewrites = null;
1695 boolean callerSourceUsed = false;
1697 if( ttCallee.equals(p_i) ) {
1698 // replace the arity-one token of the current parameter with the reachability
1699 // information from the caller edge
1700 ttCalleeRewrites = callerReachabilityCurrent;
1701 callerSourceUsed = true;
1703 } else if( paramToken2paramIndex.containsKey(ttCallee) ) {
1705 Integer paramIndex_j = paramToken2paramIndex.get(ttCallee);
1706 assert paramIndex_j != null;
1707 ttCalleeRewrites = paramIndex2rewrite_d.get(paramIndex_j);
1708 assert ttCalleeRewrites != null;
1710 } else if( paramTokenPlus2paramIndex.containsKey(ttCallee) ) {
1712 Integer paramIndex_j = paramTokenPlus2paramIndex.get(ttCallee);
1713 assert paramIndex_j != null;
1714 ttCalleeRewrites = paramIndex2rewriteD.get(paramIndex_j);
1715 assert ttCalleeRewrites != null;
1718 // otherwise there's no need for a rewrite, just pass this one on
1719 TokenTupleSet ttsCaller = new TokenTupleSet(ttCallee).makeCanonical();
1720 ttCalleeRewrites = new ReachabilitySet(ttsCaller).makeCanonical();
1723 // branch every version of the working rewritten rule with
1724 // the possibilities for rewriting the current callee token
1725 ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
1727 Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
1728 while( rewrittenRuleItr.hasNext() ) {
1729 TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
1731 Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
1732 while( ttCalleeRewritesItr.hasNext() ) {
1733 TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
1735 TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity(ttsBranch);
1737 if( makeChangeSet ) {
1738 // in order to keep the list of source token tuple sets
1739 // start with the sets used to make the partially rewritten
1740 // rule up to this point
1741 HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewritten);
1742 assert sourceSets != null;
1744 // make a shallow copy for possible modification
1745 sourceSets = (HashSet<TokenTupleSet>)sourceSets.clone();
1747 // if we used something from the caller to rewrite it, remember
1748 if( callerSourceUsed ) {
1749 sourceSets.add(ttsBranch);
1752 // set mapping for the further rewritten rule
1753 rewritten2source.put(ttsRewrittenNext, sourceSets);
1756 rewrittenRuleWithTTCallee =
1757 rewrittenRuleWithTTCallee.union(ttsRewrittenNext);
1761 // now the rewritten rule's possibilities have been extended by
1762 // rewriting the current callee token, remember result
1763 rewrittenRule = rewrittenRuleWithTTCallee;
1766 // the rule has been entirely rewritten into the caller context
1767 // now, so add it to the new reachability information
1768 callerReachabilityNew =
1769 callerReachabilityNew.union(rewrittenRule);
1772 if( makeChangeSet ) {
1773 ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
1775 // each possibility for the final reachability should have a set of
1776 // caller sources mapped to it, use to create the change set
1777 Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
1778 while( callerReachabilityItr.hasNext() ) {
1779 TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
1780 HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewrittenFinal);
1781 assert sourceSets != null;
1783 Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
1784 while( sourceSetsItr.hasNext() ) {
1785 TokenTupleSet ttsSource = sourceSetsItr.next();
1788 callerChangeSet.union(new ChangeTuple(ttsSource, ttsRewrittenFinal) );
1792 assert edgePlannedChanges != null;
1793 edgePlannedChanges.put(edge, callerChangeSet);
1797 edge.setBetaNew(edge.getBetaNew().union(callerReachabilityNew) );
1799 hrn.setAlphaNew(hrn.getAlphaNew().union(callerReachabilityNew) );
1805 private HashSet<HeapRegionNode>
1806 getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1807 HeapRegionNode hrnCallee,
1808 Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1811 HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1813 Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
1815 if( paramIndexCallee == null ) {
1816 // this is a node allocated in the callee then and it has
1817 // exactly one shadow node in the caller to map to
1818 AllocationSite as = hrnCallee.getAllocationSite();
1821 int age = as.getAgeCategory(hrnCallee.getID() );
1822 assert age != AllocationSite.AGE_notInThisSite;
1825 if( age == AllocationSite.AGE_summary ) {
1826 idCaller = as.getSummaryShadow();
1827 } else if( age == AllocationSite.AGE_oldest ) {
1828 idCaller = as.getOldestShadow();
1830 assert age == AllocationSite.AGE_in_I;
1832 Integer I = as.getAge(hrnCallee.getID() );
1835 idCaller = as.getIthOldestShadow(I);
1838 assert id2hrn.containsKey(idCaller);
1839 HeapRegionNode hrnCaller = id2hrn.get(idCaller);
1840 possibleCallerHRNs.add(hrnCaller);
1843 // this is a node that was created to represent a parameter
1844 // so it maps to a whole mess of heap regions
1845 assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
1846 possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
1849 return possibleCallerHRNs;
1854 ////////////////////////////////////////////////////
1856 // This global sweep is an optional step to prune
1857 // reachability sets that are not internally
1858 // consistent with the global graph. It should be
1859 // invoked after strong updates or method calls.
1861 ////////////////////////////////////////////////////
1862 protected void globalSweep() {
1864 // a work set for performing the sweep
1865 Hashtable<HeapRegionNode, HashSet<TokenTupleSet> > workSet =
1866 new Hashtable<HeapRegionNode, HashSet<TokenTupleSet> >();
1868 // first initialize every alphaNew for a flagged region
1869 // (or parameter region) to a set with just that token
1870 Set hrns = id2hrn.entrySet();
1871 Iterator itrHrns = hrns.iterator();
1872 while( itrHrns.hasNext() ) {
1873 Map.Entry me = (Map.Entry)itrHrns.next();
1874 Integer token = (Integer) me.getKey();
1875 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1877 // assert that this node and incoming edges have clean alphaNew
1878 // and betaNew sets, respectively
1879 ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical();
1880 assert rsEmpty.equals( hrn.getAlphaNew() );
1882 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
1883 while( itrRes.hasNext() ) {
1884 ReferenceEdge edge = itrRes.next();
1885 assert rsEmpty.equals( edge.getBetaNew() );
1888 TokenTuple tt = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONE ).makeCanonical();
1889 TokenTuple ttPlus = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONEORMORE ).makeCanonical();
1890 TokenTuple ttStar = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
1892 TokenTupleSet tts = new TokenTupleSet( tt ).makeCanonical();
1893 TokenTupleSet ttsPlus = new TokenTupleSet( ttPlus ).makeCanonical();
1894 TokenTupleSet ttsStar = new TokenTupleSet( ttStar ).makeCanonical();
1895 TokenTupleSet ttsEmpty = new TokenTupleSet( ).makeCanonical();
1897 if( hrn.isFlagged() || hrn.isParameter() ) {
1898 HashSet<TokenTupleSet> subWorkSet = new HashSet<TokenTupleSet>();
1899 subWorkSet.add( tts );
1900 subWorkSet.add( ttsPlus );
1901 subWorkSet.add( ttsStar );
1902 workSet.put( hrn, subWorkSet );
1904 hrn.setAlphaNew( new ReachabilitySet( tts ).makeCanonical() );
1906 hrn.setAlphaNew( new ReachabilitySet( ttsEmpty ).makeCanonical() );
1910 // then propagate tokens forward one step at a time
1911 while( !workSet.isEmpty() ) {
1912 HeapRegionNode hrn = workSet.keySet().iterator().next();
1914 HashSet<TokenTupleSet> subWorkSet = workSet.get( hrn );
1915 assert subWorkSet != null;
1917 if( subWorkSet.isEmpty() ) {
1918 // we're currently done with sub work at this heap region, although
1919 // more work may get queued up later, but remove it for now and continue
1920 workSet.remove( hrn );
1924 TokenTupleSet tts = subWorkSet.iterator().next();
1925 subWorkSet.remove( tts );
1927 // try to push this TokenTupleSet over all outgoing edges
1928 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencees();
1929 while( itrRes.hasNext() ) {
1930 ReferenceEdge edge = itrRes.next();
1932 if( edge.getBeta().containsSuperSet( tts ) ) {
1933 HeapRegionNode dst = edge.getDst();
1935 // make a set of possible contributions this token
1936 // might have on the alpha set here
1937 HashSet<TokenTupleSet> ttsNewSet = new HashSet<TokenTupleSet>();
1939 Iterator<TokenTupleSet> itrDstAlphaNew = dst.getAlphaNew().iterator();
1940 while( itrDstAlphaNew.hasNext() ) {
1941 TokenTupleSet ttsDstAlphaNew = itrDstAlphaNew.next();
1942 ttsNewSet.add( tts.unionUpArity( ttsDstAlphaNew ) );
1945 // only add this to the dst alpha new if it is in the beta of
1946 // the edge we crossed to get here, and then only continue the
1947 // propagation if it isn't already in the dst alpha new
1948 Iterator<TokenTupleSet> itrNewSet = ttsNewSet.iterator();
1949 while( itrNewSet.hasNext() ) {
1950 TokenTupleSet ttsNew = itrNewSet.next();
1952 if( edge.getBeta().containsSuperSet( ttsNew ) &&
1953 !dst.getAlphaNew().contains( ttsNew ) ) {
1955 // okay, this is a valid propagation, and add to the
1956 // work set to further propagate it
1957 dst.setAlphaNew( dst.getAlphaNew().union( ttsNew ) );
1959 HashSet<TokenTupleSet> subWorkSetDst = workSet.get( dst );
1960 if( subWorkSetDst == null ) {
1961 subWorkSetDst = new HashSet<TokenTupleSet>();
1964 subWorkSetDst.add( ttsNew );
1965 workSet.put( dst, subWorkSetDst );
1972 // now prepare work sets to propagate token sets backwards
1973 // from heap regions across all edges
1974 assert workSet.isEmpty();
1975 hrns = id2hrn.entrySet();
1976 itrHrns = hrns.iterator();
1977 while( itrHrns.hasNext() ) {
1978 Map.Entry me = (Map.Entry)itrHrns.next();
1979 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1981 HashSet<TokenTupleSet> subWorkSet = new HashSet<TokenTupleSet>();
1983 Iterator<TokenTupleSet> itrAlphaNewSets = hrn.getAlphaNew().iterator();
1984 while( itrAlphaNewSets.hasNext() ) {
1985 TokenTupleSet tts = itrAlphaNewSets.next();
1986 subWorkSet.add( tts );
1989 workSet.put( hrn, subWorkSet );
1992 // propagate token sets backwards across edges one step at a time
1993 while( !workSet.isEmpty() ) {
1994 HeapRegionNode hrn = workSet.keySet().iterator().next();
1996 HashSet<TokenTupleSet> subWorkSet = workSet.get( hrn );
1997 assert subWorkSet != null;
1999 if( subWorkSet.isEmpty() ) {
2000 // we're currently done with sub work at this heap region, although
2001 // more work may get queued up later, but remove it for now and continue
2002 workSet.remove( hrn );
2006 TokenTupleSet tts = subWorkSet.iterator().next();
2007 subWorkSet.remove( tts );
2009 // try to push this TokenTupleSet back up incoming edges
2010 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
2011 while( itrRes.hasNext() ) {
2012 ReferenceEdge edge = itrRes.next();
2013 if( edge.getBeta().containsWithZeroes( tts ) &&
2014 !edge.getBetaNew().contains( tts ) ) {
2015 // okay, this is a valid propagation, and add to the
2016 // work set to further propagate it
2017 edge.setBetaNew( edge.getBetaNew().union( tts ) );
2019 OwnershipNode src = edge.getSrc();
2020 if( src instanceof HeapRegionNode ) {
2022 HashSet<TokenTupleSet> subWorkSetSrc = workSet.get( (HeapRegionNode) src );
2023 if( subWorkSetSrc == null ) {
2024 subWorkSetSrc = new HashSet<TokenTupleSet>();
2027 subWorkSetSrc.add( tts );
2028 workSet.put( (HeapRegionNode) src, subWorkSetSrc );
2034 // apply alphaNew and betaNew to all nodes and edges
2035 HashSet<ReferenceEdge> res = new HashSet<ReferenceEdge>();
2037 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2038 while( nodeItr.hasNext() ) {
2039 HeapRegionNode hrn = nodeItr.next();
2040 hrn.applyAlphaNew();
2041 Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
2042 while( itrRes.hasNext() ) {
2043 res.add( itrRes.next() );
2047 Iterator<ReferenceEdge> edgeItr = res.iterator();
2048 while( edgeItr.hasNext() ) {
2049 edgeItr.next().applyBetaNew();
2055 ////////////////////////////////////////////////////
2056 // in merge() and equals() methods the suffix A
2057 // represents the passed in graph and the suffix
2058 // B refers to the graph in this object
2059 // Merging means to take the incoming graph A and
2060 // merge it into B, so after the operation graph B
2061 // is the final result.
2062 ////////////////////////////////////////////////////
2063 public void merge(OwnershipGraph og) {
2069 mergeOwnershipNodes(og);
2070 mergeReferenceEdges(og);
2071 mergeId2paramIndex(og);
2072 mergeAllocationSites(og);
2076 protected void mergeOwnershipNodes(OwnershipGraph og) {
2077 Set sA = og.id2hrn.entrySet();
2078 Iterator iA = sA.iterator();
2079 while( iA.hasNext() ) {
2080 Map.Entry meA = (Map.Entry)iA.next();
2081 Integer idA = (Integer) meA.getKey();
2082 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2084 // if this graph doesn't have a node the
2085 // incoming graph has, allocate it
2086 if( !id2hrn.containsKey(idA) ) {
2087 HeapRegionNode hrnB = hrnA.copy();
2088 id2hrn.put(idA, hrnB);
2091 // otherwise this is a node present in both graphs
2092 // so make the new reachability set a union of the
2093 // nodes' reachability sets
2094 HeapRegionNode hrnB = id2hrn.get(idA);
2095 hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
2099 // now add any label nodes that are in graph B but
2101 sA = og.td2ln.entrySet();
2103 while( iA.hasNext() ) {
2104 Map.Entry meA = (Map.Entry)iA.next();
2105 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2106 LabelNode lnA = (LabelNode) meA.getValue();
2108 // if the label doesn't exist in B, allocate and add it
2109 LabelNode lnB = getLabelNodeFromTemp(tdA);
2113 protected void mergeReferenceEdges(OwnershipGraph og) {
2116 Set sA = og.id2hrn.entrySet();
2117 Iterator iA = sA.iterator();
2118 while( iA.hasNext() ) {
2119 Map.Entry meA = (Map.Entry)iA.next();
2120 Integer idA = (Integer) meA.getKey();
2121 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2123 Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2124 while( heapRegionsItrA.hasNext() ) {
2125 ReferenceEdge edgeA = heapRegionsItrA.next();
2126 HeapRegionNode hrnChildA = edgeA.getDst();
2127 Integer idChildA = hrnChildA.getID();
2129 // at this point we know an edge in graph A exists
2130 // idA -> idChildA, does this exist in B?
2131 assert id2hrn.containsKey(idA);
2132 HeapRegionNode hrnB = id2hrn.get(idA);
2133 ReferenceEdge edgeToMerge = null;
2135 Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2136 while( heapRegionsItrB.hasNext() &&
2137 edgeToMerge == null ) {
2139 ReferenceEdge edgeB = heapRegionsItrB.next();
2140 HeapRegionNode hrnChildB = edgeB.getDst();
2141 Integer idChildB = hrnChildB.getID();
2143 // don't use the ReferenceEdge.equals() here because
2144 // we're talking about existence between graphs
2145 if( idChildB.equals(idChildA) &&
2146 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
2147 edgeToMerge = edgeB;
2151 // if the edge from A was not found in B,
2153 if( edgeToMerge == null ) {
2154 assert id2hrn.containsKey(idChildA);
2155 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
2156 edgeToMerge = edgeA.copy();
2157 edgeToMerge.setSrc(hrnB);
2158 edgeToMerge.setDst(hrnChildB);
2159 addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
2161 // otherwise, the edge already existed in both graphs
2162 // so merge their reachability sets
2164 // just replace this beta set with the union
2165 assert edgeToMerge != null;
2166 edgeToMerge.setBeta(
2167 edgeToMerge.getBeta().union(edgeA.getBeta() )
2169 if( !edgeA.isInitialParamReflexive() ) {
2170 edgeToMerge.setIsInitialParamReflexive(false);
2176 // and then again with label nodes
2177 sA = og.td2ln.entrySet();
2179 while( iA.hasNext() ) {
2180 Map.Entry meA = (Map.Entry)iA.next();
2181 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2182 LabelNode lnA = (LabelNode) meA.getValue();
2184 Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
2185 while( heapRegionsItrA.hasNext() ) {
2186 ReferenceEdge edgeA = heapRegionsItrA.next();
2187 HeapRegionNode hrnChildA = edgeA.getDst();
2188 Integer idChildA = hrnChildA.getID();
2190 // at this point we know an edge in graph A exists
2191 // tdA -> idChildA, does this exist in B?
2192 assert td2ln.containsKey(tdA);
2193 LabelNode lnB = td2ln.get(tdA);
2194 ReferenceEdge edgeToMerge = null;
2196 // labels never have edges with a field
2197 //assert edgeA.getFieldDesc() == null;
2199 Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
2200 while( heapRegionsItrB.hasNext() &&
2201 edgeToMerge == null ) {
2203 ReferenceEdge edgeB = heapRegionsItrB.next();
2204 HeapRegionNode hrnChildB = edgeB.getDst();
2205 Integer idChildB = hrnChildB.getID();
2207 // labels never have edges with a field
2208 //assert edgeB.getFieldDesc() == null;
2210 // don't use the ReferenceEdge.equals() here because
2211 // we're talking about existence between graphs
2212 if( idChildB.equals(idChildA) &&
2213 edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
2214 edgeToMerge = edgeB;
2218 // if the edge from A was not found in B,
2220 if( edgeToMerge == null ) {
2221 assert id2hrn.containsKey(idChildA);
2222 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
2223 edgeToMerge = edgeA.copy();
2224 edgeToMerge.setSrc(lnB);
2225 edgeToMerge.setDst(hrnChildB);
2226 addReferenceEdge(lnB, hrnChildB, edgeToMerge);
2228 // otherwise, the edge already existed in both graphs
2229 // so merge their reachability sets
2231 // just replace this beta set with the union
2232 edgeToMerge.setBeta(
2233 edgeToMerge.getBeta().union(edgeA.getBeta() )
2235 if( !edgeA.isInitialParamReflexive() ) {
2236 edgeToMerge.setIsInitialParamReflexive(false);
2243 // you should only merge ownership graphs that have the
2244 // same number of parameters, or if one or both parameter
2245 // index tables are empty
2246 protected void mergeId2paramIndex(OwnershipGraph og) {
2247 if( id2paramIndex.size() == 0 ) {
2248 id2paramIndex = og.id2paramIndex;
2249 paramIndex2id = og.paramIndex2id;
2250 paramIndex2tdQ = og.paramIndex2tdQ;
2254 if( og.id2paramIndex.size() == 0 ) {
2258 assert id2paramIndex.size() == og.id2paramIndex.size();
2261 protected void mergeAllocationSites(OwnershipGraph og) {
2262 allocationSites.addAll(og.allocationSites);
2267 // it is necessary in the equals() member functions
2268 // to "check both ways" when comparing the data
2269 // structures of two graphs. For instance, if all
2270 // edges between heap region nodes in graph A are
2271 // present and equal in graph B it is not sufficient
2272 // to say the graphs are equal. Consider that there
2273 // may be edges in graph B that are not in graph A.
2274 // the only way to know that all edges in both graphs
2275 // are equally present is to iterate over both data
2276 // structures and compare against the other graph.
2277 public boolean equals(OwnershipGraph og) {
2283 if( !areHeapRegionNodesEqual(og) ) {
2287 if( !areLabelNodesEqual(og) ) {
2291 if( !areReferenceEdgesEqual(og) ) {
2295 if( !areId2paramIndexEqual(og) ) {
2299 // if everything is equal up to this point,
2300 // assert that allocationSites is also equal--
2301 // this data is redundant and kept for efficiency
2302 assert allocationSites.equals(og.allocationSites);
2307 protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2309 if( !areallHRNinAalsoinBandequal(this, og) ) {
2313 if( !areallHRNinAalsoinBandequal(og, this) ) {
2320 static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2321 OwnershipGraph ogB) {
2322 Set sA = ogA.id2hrn.entrySet();
2323 Iterator iA = sA.iterator();
2324 while( iA.hasNext() ) {
2325 Map.Entry meA = (Map.Entry)iA.next();
2326 Integer idA = (Integer) meA.getKey();
2327 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2329 if( !ogB.id2hrn.containsKey(idA) ) {
2333 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2334 if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2343 protected boolean areLabelNodesEqual(OwnershipGraph og) {
2345 if( !areallLNinAalsoinBandequal(this, og) ) {
2349 if( !areallLNinAalsoinBandequal(og, this) ) {
2356 static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2357 OwnershipGraph ogB) {
2358 Set sA = ogA.td2ln.entrySet();
2359 Iterator iA = sA.iterator();
2360 while( iA.hasNext() ) {
2361 Map.Entry meA = (Map.Entry)iA.next();
2362 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2364 if( !ogB.td2ln.containsKey(tdA) ) {
2373 protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2374 if( !areallREinAandBequal(this, og) ) {
2381 static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2382 OwnershipGraph ogB) {
2384 // check all the heap region->heap region edges
2385 Set sA = ogA.id2hrn.entrySet();
2386 Iterator iA = sA.iterator();
2387 while( iA.hasNext() ) {
2388 Map.Entry meA = (Map.Entry)iA.next();
2389 Integer idA = (Integer) meA.getKey();
2390 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2392 // we should have already checked that the same
2393 // heap regions exist in both graphs
2394 assert ogB.id2hrn.containsKey(idA);
2396 if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2400 // then check every edge in B for presence in A, starting
2401 // from the same parent HeapRegionNode
2402 HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2404 if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2409 // then check all the label->heap region edges
2410 sA = ogA.td2ln.entrySet();
2412 while( iA.hasNext() ) {
2413 Map.Entry meA = (Map.Entry)iA.next();
2414 TempDescriptor tdA = (TempDescriptor) meA.getKey();
2415 LabelNode lnA = (LabelNode) meA.getValue();
2417 // we should have already checked that the same
2418 // label nodes exist in both graphs
2419 assert ogB.td2ln.containsKey(tdA);
2421 if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2425 // then check every edge in B for presence in A, starting
2426 // from the same parent LabelNode
2427 LabelNode lnB = ogB.td2ln.get(tdA);
2429 if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2438 static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2440 OwnershipGraph ogB) {
2442 Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2443 while( itrA.hasNext() ) {
2444 ReferenceEdge edgeA = itrA.next();
2445 HeapRegionNode hrnChildA = edgeA.getDst();
2446 Integer idChildA = hrnChildA.getID();
2448 assert ogB.id2hrn.containsKey(idChildA);
2450 // at this point we know an edge in graph A exists
2451 // onA -> idChildA, does this exact edge exist in B?
2452 boolean edgeFound = false;
2454 OwnershipNode onB = null;
2455 if( onA instanceof HeapRegionNode ) {
2456 HeapRegionNode hrnA = (HeapRegionNode) onA;
2457 onB = ogB.id2hrn.get(hrnA.getID() );
2459 LabelNode lnA = (LabelNode) onA;
2460 onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2463 Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2464 while( itrB.hasNext() ) {
2465 ReferenceEdge edgeB = itrB.next();
2466 HeapRegionNode hrnChildB = edgeB.getDst();
2467 Integer idChildB = hrnChildB.getID();
2469 if( idChildA.equals(idChildB) &&
2470 edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2472 // there is an edge in the right place with the right field,
2473 // but do they have the same attributes?
2474 if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2492 protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2493 return id2paramIndex.size() == og.id2paramIndex.size();
2496 public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
2498 // get parameter's heap region
2499 assert paramIndex2id.containsKey(paramIndex1);
2500 Integer idParam1 = paramIndex2id.get(paramIndex1);
2502 assert id2hrn.containsKey(idParam1);
2503 HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2504 assert hrnParam1 != null;
2506 // get tokens for this parameter
2507 TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2509 TokenTuple.ARITY_ONE).makeCanonical();
2511 TokenTuple pPlus1 = new TokenTuple(hrnParam1.getID(),
2513 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2515 TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2517 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2520 // get tokens for the other parameter
2521 assert paramIndex2id.containsKey(paramIndex2);
2522 Integer idParam2 = paramIndex2id.get(paramIndex2);
2524 assert id2hrn.containsKey(idParam2);
2525 HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2526 assert hrnParam2 != null;
2528 TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2530 TokenTuple.ARITY_ONE).makeCanonical();
2532 TokenTuple pPlus2 = new TokenTuple(hrnParam2.getID(),
2534 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2536 TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2538 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2541 // get special label p_q for first parameter
2542 TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2543 assert tdParamQ1 != null;
2544 LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2545 assert lnParamQ1 != null;
2547 // then get the edge from label q to parameter's hrn
2548 ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2549 assert edgeSpecialQ1 != null;
2551 // if the beta of this edge has tokens from both parameters in one
2552 // token tuple set, then there is a potential alias between them
2553 ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2554 assert beta1 != null;
2556 if( beta1.containsTupleSetWithBoth(p1, p2) ) {
2559 if( beta1.containsTupleSetWithBoth(pPlus1, p2) ) {
2562 if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
2565 if( beta1.containsTupleSetWithBoth(p1, pPlus2) ) {
2568 if( beta1.containsTupleSetWithBoth(pPlus1, pPlus2) ) {
2571 if( beta1.containsTupleSetWithBoth(pStar1, pPlus2) ) {
2574 if( beta1.containsTupleSetWithBoth(p1, pStar2) ) {
2577 if( beta1.containsTupleSetWithBoth(pPlus1, pStar2) ) {
2580 if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
2588 public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
2590 // get parameter's heap region
2591 assert paramIndex2id.containsKey(paramIndex);
2592 Integer idParam = paramIndex2id.get(paramIndex);
2594 assert id2hrn.containsKey(idParam);
2595 HeapRegionNode hrnParam = id2hrn.get(idParam);
2596 assert hrnParam != null;
2598 // get tokens for this parameter
2599 TokenTuple p = new TokenTuple(hrnParam.getID(),
2601 TokenTuple.ARITY_ONE).makeCanonical();
2603 TokenTuple pPlus = new TokenTuple(hrnParam.getID(),
2605 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2607 TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2609 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2611 // get special label p_q
2612 TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2613 assert tdParamQ != null;
2614 LabelNode lnParamQ = td2ln.get(tdParamQ);
2615 assert lnParamQ != null;
2617 // then get the edge from label q to parameter's hrn
2618 ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2619 assert edgeSpecialQ != null;
2621 // look through this beta set for potential aliases
2622 ReachabilitySet beta = edgeSpecialQ.getBeta();
2623 assert beta != null;
2626 // get tokens for summary node
2627 TokenTuple gs = new TokenTuple(as.getSummary(),
2629 TokenTuple.ARITY_ONE).makeCanonical();
2631 TokenTuple gsPlus = new TokenTuple(as.getSummary(),
2633 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2635 TokenTuple gsStar = new TokenTuple(as.getSummary(),
2637 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2640 if( beta.containsTupleSetWithBoth(p, gs) ) {
2643 if( beta.containsTupleSetWithBoth(pPlus, gs) ) {
2646 if( beta.containsTupleSetWithBoth(pStar, gs) ) {
2649 if( beta.containsTupleSetWithBoth(p, gsPlus) ) {
2652 if( beta.containsTupleSetWithBoth(pPlus, gsPlus) ) {
2655 if( beta.containsTupleSetWithBoth(pStar, gsPlus) ) {
2658 if( beta.containsTupleSetWithBoth(p, gsStar) ) {
2661 if( beta.containsTupleSetWithBoth(pPlus, gsStar) ) {
2664 if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
2668 // check for other nodes
2669 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2671 // the other nodes of an allocation site are single, no plus
2672 TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2674 TokenTuple.ARITY_ONE).makeCanonical();
2676 TokenTuple giStar = new TokenTuple(as.getIthOldest(i),
2678 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2680 if( beta.containsTupleSetWithBoth(p, gi) ) {
2683 if( beta.containsTupleSetWithBoth(pPlus, gi) ) {
2686 if( beta.containsTupleSetWithBoth(pStar, gi) ) {
2689 if( beta.containsTupleSetWithBoth(p, giStar) ) {
2692 if( beta.containsTupleSetWithBoth(pPlus, giStar) ) {
2695 if( beta.containsTupleSetWithBoth(pStar, giStar) ) {
2704 public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
2706 // get tokens for summary nodes
2707 TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2709 TokenTuple.ARITY_ONE).makeCanonical();
2711 TokenTuple gsPlus1 = new TokenTuple(as1.getSummary(),
2713 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2715 TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2717 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2719 // get summary node's alpha
2720 Integer idSum1 = as1.getSummary();
2721 assert id2hrn.containsKey(idSum1);
2722 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
2723 assert hrnSum1 != null;
2724 ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2725 assert alphaSum1 != null;
2728 // and for the other one
2729 TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2731 TokenTuple.ARITY_ONE).makeCanonical();
2733 TokenTuple gsPlus2 = new TokenTuple(as2.getSummary(),
2735 TokenTuple.ARITY_ONEORMORE).makeCanonical();
2737 TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2739 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2741 // get summary node's alpha
2742 Integer idSum2 = as2.getSummary();
2743 assert id2hrn.containsKey(idSum2);
2744 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
2745 assert hrnSum2 != null;
2746 ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2747 assert alphaSum2 != null;
2749 // does either one report reachability from the other tokens?
2750 if( alphaSum1.containsTuple(gsPlus2) ) {
2753 if( alphaSum1.containsTuple(gsStar2) ) {
2756 if( alphaSum2.containsTuple(gsPlus1) ) {
2759 if( alphaSum2.containsTuple(gsStar1) ) {
2763 // only check ONE token if they are different sites
2765 if( alphaSum1.containsTuple(gs2) ) {
2768 if( alphaSum2.containsTuple(gs1) ) {
2774 // check sum2 against alloc1 nodes
2775 for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2776 Integer idI1 = as1.getIthOldest(i);
2777 assert id2hrn.containsKey(idI1);
2778 HeapRegionNode hrnI1 = id2hrn.get(idI1);
2779 assert hrnI1 != null;
2780 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2781 assert alphaI1 != null;
2783 // the other nodes of an allocation site are single, no stars
2784 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2786 TokenTuple.ARITY_ONE).makeCanonical();
2788 TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(i),
2790 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2792 if( alphaSum2.containsTuple(gi1) ) {
2795 if( alphaSum2.containsTuple(giStar1) ) {
2798 if( alphaI1.containsTuple(gs2) ) {
2801 if( alphaI1.containsTuple(gsPlus2) ) {
2804 if( alphaI1.containsTuple(gsStar2) ) {
2809 // check sum1 against alloc2 nodes
2810 for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2811 Integer idI2 = as2.getIthOldest(i);
2812 assert id2hrn.containsKey(idI2);
2813 HeapRegionNode hrnI2 = id2hrn.get(idI2);
2814 assert hrnI2 != null;
2815 ReachabilitySet alphaI2 = hrnI2.getAlpha();
2816 assert alphaI2 != null;
2818 TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2820 TokenTuple.ARITY_ONE).makeCanonical();
2822 TokenTuple giStar2 = new TokenTuple(as2.getIthOldest(i),
2824 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2826 if( alphaSum1.containsTuple(gi2) ) {
2829 if( alphaSum1.containsTuple(giStar2) ) {
2832 if( alphaI2.containsTuple(gs1) ) {
2835 if( alphaI2.containsTuple(gsPlus1) ) {
2838 if( alphaI2.containsTuple(gsStar1) ) {
2842 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
2843 for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
2844 Integer idI1 = as1.getIthOldest(j);
2846 // if these are the same site, don't look for the same token, no alias.
2847 // different tokens of the same site could alias together though
2848 if( idI1 == idI2 ) {
2852 HeapRegionNode hrnI1 = id2hrn.get(idI1);
2853 ReachabilitySet alphaI1 = hrnI1.getAlpha();
2854 TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
2856 TokenTuple.ARITY_ONE).makeCanonical();
2858 TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(j),
2860 TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2862 if( alphaI2.containsTuple(gi1) ) {
2865 if( alphaI2.containsTuple(giStar1) ) {
2868 if( alphaI1.containsTuple(gi2) ) {
2871 if( alphaI1.containsTuple(giStar2) ) {
2881 // for writing ownership graphs to dot files
2882 public void writeGraph(Descriptor methodDesc,
2884 boolean writeLabels,
2885 boolean labelSelect,
2886 boolean pruneGarbage,
2887 boolean writeReferencers,
2888 boolean writeParamMappings
2889 ) throws java.io.IOException {
2891 methodDesc.getSymbol() +
2892 methodDesc.getNum() +
2902 public void writeGraph(Descriptor methodDesc,
2903 boolean writeLabels,
2904 boolean labelSelect,
2905 boolean pruneGarbage,
2906 boolean writeReferencers,
2907 boolean writeParamMappings
2908 ) throws java.io.IOException {
2910 writeGraph(methodDesc+"COMPLETE",
2919 public void writeGraph(Descriptor methodDesc,
2921 boolean writeLabels,
2922 boolean labelSelect,
2923 boolean pruneGarbage,
2924 boolean writeReferencers,
2925 boolean writeParamMappings
2926 ) throws java.io.IOException {
2928 writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
2937 public void writeGraph(String graphName,
2938 boolean writeLabels,
2939 boolean labelSelect,
2940 boolean pruneGarbage,
2941 boolean writeReferencers,
2942 boolean writeParamMappings
2943 ) throws java.io.IOException {
2945 // remove all non-word characters from the graph name so
2946 // the filename and identifier in dot don't cause errors
2947 graphName = graphName.replaceAll("[\\W]", "");
2949 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2950 bw.write("digraph "+graphName+" {\n");
2952 HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2954 // then visit every heap region node
2955 Set s = id2hrn.entrySet();
2956 Iterator i = s.iterator();
2957 while( i.hasNext() ) {
2958 Map.Entry me = (Map.Entry)i.next();
2959 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2960 if( !pruneGarbage ||
2962 hrn.getDescription().startsWith("param")
2965 if( !visited.contains(hrn) ) {
2966 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2976 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
2978 if( writeParamMappings ) {
2979 Set df = paramIndex2id.entrySet();
2980 Iterator ih = df.iterator();
2981 while( ih.hasNext() ) {
2982 Map.Entry meh = (Map.Entry)ih.next();
2983 Integer pi = (Integer) meh.getKey();
2984 Integer id = (Integer) meh.getValue();
2985 bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
2989 // then visit every label node, useful for debugging
2991 s = td2ln.entrySet();
2993 while( i.hasNext() ) {
2994 Map.Entry me = (Map.Entry)i.next();
2995 LabelNode ln = (LabelNode) me.getValue();
2998 String labelStr = ln.getTempDescriptorString();
2999 if( labelStr.startsWith("___temp") ||
3000 labelStr.startsWith("___dst") ||
3001 labelStr.startsWith("___srctmp") ||
3002 labelStr.startsWith("___neverused") ) {
3007 //bw.write(" "+ln.toString() + ";\n");
3009 Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
3010 while( heapRegionsItr.hasNext() ) {
3011 ReferenceEdge edge = heapRegionsItr.next();
3012 HeapRegionNode hrn = edge.getDst();
3014 if( pruneGarbage && !visited.contains(hrn) ) {
3015 traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
3023 bw.write(" " + ln.toString() +
3024 " -> " + hrn.toString() +
3025 "[label=\"" + edge.toGraphEdgeString() +
3036 protected void traverseHeapRegionNodes(int mode,
3040 HashSet<HeapRegionNode> visited,
3041 boolean writeReferencers
3042 ) throws java.io.IOException {
3044 if( visited.contains(hrn) ) {
3050 case VISIT_HRN_WRITE_FULL:
3052 String attributes = "[";
3054 if( hrn.isSingleObject() ) {
3055 attributes += "shape=box";
3057 attributes += "shape=Msquare";
3060 if( hrn.isFlagged() ) {
3061 attributes += ",style=filled,fillcolor=lightgrey";
3064 attributes += ",label=\"ID" +
3067 hrn.getDescription() +
3069 hrn.getAlphaString() +
3072 bw.write(" " + hrn.toString() + attributes + ";\n");
3077 // useful for debugging
3078 if( writeReferencers ) {
3079 OwnershipNode onRef = null;
3080 Iterator refItr = hrn.iteratorToReferencers();
3081 while( refItr.hasNext() ) {
3082 onRef = (OwnershipNode) refItr.next();
3085 case VISIT_HRN_WRITE_FULL:
3086 bw.write(" " + hrn.toString() +
3087 " -> " + onRef.toString() +
3088 "[color=lightgray];\n");
3094 Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
3095 while( childRegionsItr.hasNext() ) {
3096 ReferenceEdge edge = childRegionsItr.next();
3097 HeapRegionNode hrnChild = edge.getDst();
3100 case VISIT_HRN_WRITE_FULL:
3101 bw.write(" " + hrn.toString() +
3102 " -> " + hrnChild.toString() +
3103 "[label=\"" + edge.toGraphEdgeString() +
3108 traverseHeapRegionNodes(mode,