1 package Analysis.Disjoint;
5 import Util.UtilAlgorithms;
9 public class ReachGraph {
11 // use to disable improvements for comparison
12 protected static final boolean DISABLE_STRONG_UPDATES = false;
13 protected static final boolean DISABLE_GLOBAL_SWEEP = false;
15 // a special out-of-scope temp
16 protected static final TempDescriptor tdReturn = new TempDescriptor("_Return___");
18 // predicate constants
19 public static final ExistPred predTrue = ExistPred.factory(); // if no args, true
20 public static final ExistPredSet predsEmpty = ExistPredSet.factory();
21 public static final ExistPredSet predsTrue = ExistPredSet.factory(predTrue);
23 // some frequently used reachability constants
24 protected static final ReachState rstateEmpty = ReachState.factory();
25 protected static final ReachSet rsetEmpty = ReachSet.factory();
26 protected static final ReachSet rsetWithEmptyState = Canonical.changePredsTo(ReachSet.factory(rstateEmpty),
29 // from DisjointAnalysis for convenience
30 protected static int allocationDepth = -1;
31 protected static TypeUtil typeUtil = null;
32 protected static State state = null;
35 // variable and heap region nodes indexed by unique ID
36 public Hashtable<Integer, HeapRegionNode> id2hrn;
37 public Hashtable<TempDescriptor, VariableNode > td2vn;
39 // convenient set of alloc sites for all heap regions
40 // present in the graph without having to search
41 public Set<AllocSite> allocSites;
43 // set of inaccessible variables for current program statement
44 // with respect to stall-site analysis
45 public Set<TempDescriptor> inaccessibleVars;
49 id2hrn = new Hashtable<Integer, HeapRegionNode>();
50 td2vn = new Hashtable<TempDescriptor, VariableNode >();
51 allocSites = new HashSet<AllocSite>();
52 inaccessibleVars = new HashSet<TempDescriptor>();
56 // temp descriptors are globally unique and map to
57 // exactly one variable node, easy
58 protected VariableNode getVariableNodeFromTemp(TempDescriptor td) {
61 if( !td2vn.containsKey(td) ) {
62 td2vn.put(td, new VariableNode(td) );
68 //This method is created for client modules to access the Reachgraph
69 //after the analysis is done and no modifications are to be made.
70 public VariableNode getVariableNodeNoMutation(TempDescriptor td) {
73 if( !td2vn.containsKey(td) ) {
80 public boolean hasVariable(TempDescriptor td) {
81 return td2vn.containsKey(td);
85 // this suite of methods can be used to assert a
86 // very important property of ReachGraph objects:
87 // some element, HeapRegionNode, RefEdge etc.
88 // should be referenced by at most ONE ReachGraph!!
89 // If a heap region or edge or variable should be
90 // in another graph, make a new object with
91 // equivalent properties for a new graph
92 public boolean belongsToThis(RefSrcNode rsn) {
93 if( rsn instanceof VariableNode ) {
94 VariableNode vn = (VariableNode) rsn;
95 return this.td2vn.get(vn.getTempDescriptor() ) == vn;
97 HeapRegionNode hrn = (HeapRegionNode) rsn;
98 return this.id2hrn.get(hrn.getID() ) == hrn;
105 // the reason for this method is to have the option
106 // of creating new heap regions with specific IDs, or
107 // duplicating heap regions with specific IDs (especially
108 // in the merge() operation) or to create new heap
109 // regions with a new unique ID
110 protected HeapRegionNode
111 createNewHeapRegionNode(Integer id,
112 boolean isSingleObject,
113 boolean isNewSummary,
114 boolean isOutOfContext,
123 TypeDescriptor typeToUse = null;
124 if( allocSite != null ) {
125 typeToUse = allocSite.getType();
126 allocSites.add(allocSite);
131 boolean markForAnalysis = false;
132 if( allocSite != null && allocSite.isFlagged() ) {
133 markForAnalysis = true;
136 if( allocSite == null ) {
137 assert !markForAnalysis;
139 } else if( markForAnalysis != allocSite.isFlagged() ) {
145 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
148 if( inherent == null ) {
149 if( markForAnalysis ) {
151 Canonical.changePredsTo(
154 ReachTuple.factory(id,
156 ReachTuple.ARITY_ONE,
157 false // out-of-context
164 inherent = rsetWithEmptyState;
168 if( alpha == null ) {
172 assert preds != null;
174 HeapRegionNode hrn = new HeapRegionNode(id,
191 ////////////////////////////////////////////////
193 // Low-level referencee and referencer methods
195 // These methods provide the lowest level for
196 // creating references between reachability nodes
197 // and handling the details of maintaining both
198 // list of referencers and referencees.
200 ////////////////////////////////////////////////
201 protected void addRefEdge(RefSrcNode referencer,
202 HeapRegionNode referencee,
204 assert referencer != null;
205 assert referencee != null;
207 assert edge.getSrc() == referencer;
208 assert edge.getDst() == referencee;
209 assert belongsToThis(referencer);
210 assert belongsToThis(referencee);
212 // edges are getting added twice to graphs now, the
213 // kind that should have abstract facts merged--use
214 // this check to prevent that
215 assert referencer.getReferenceTo(referencee,
220 referencer.addReferencee(edge);
221 referencee.addReferencer(edge);
224 protected void removeRefEdge(RefEdge e) {
225 removeRefEdge(e.getSrc(),
231 protected void removeRefEdge(RefSrcNode referencer,
232 HeapRegionNode referencee,
235 assert referencer != null;
236 assert referencee != null;
238 RefEdge edge = referencer.getReferenceTo(referencee,
242 assert edge == referencee.getReferenceFrom(referencer,
246 referencer.removeReferencee(edge);
247 referencee.removeReferencer(edge);
250 // return whether at least one edge was removed
251 protected boolean clearRefEdgesFrom(RefSrcNode referencer,
255 assert referencer != null;
257 boolean atLeastOneEdgeRemoved = false;
259 // get a copy of the set to iterate over, otherwise
260 // we will be trying to take apart the set as we
261 // are iterating over it, which won't work
262 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
263 while( i.hasNext() ) {
264 RefEdge edge = i.next();
267 (edge.typeEquals(type) && edge.fieldEquals(field))
270 HeapRegionNode referencee = edge.getDst();
272 removeRefEdge(referencer,
277 atLeastOneEdgeRemoved = true;
281 return atLeastOneEdgeRemoved;
284 protected void clearRefEdgesTo(HeapRegionNode referencee,
288 assert referencee != null;
290 // get a copy of the set to iterate over, otherwise
291 // we will be trying to take apart the set as we
292 // are iterating over it, which won't work
293 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
294 while( i.hasNext() ) {
295 RefEdge edge = i.next();
298 (edge.typeEquals(type) && edge.fieldEquals(field))
301 RefSrcNode referencer = edge.getSrc();
303 removeRefEdge(referencer,
311 protected void clearNonVarRefEdgesTo(HeapRegionNode referencee) {
312 assert referencee != null;
314 // get a copy of the set to iterate over, otherwise
315 // we will be trying to take apart the set as we
316 // are iterating over it, which won't work
317 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
318 while( i.hasNext() ) {
319 RefEdge edge = i.next();
320 RefSrcNode referencer = edge.getSrc();
321 if( !(referencer instanceof VariableNode) ) {
322 removeRefEdge(referencer,
330 // this is a common operation in many transfer functions: we want
331 // to add an edge, but if there is already such an edge we should
332 // merge the properties of the existing and the new edges
333 protected void addEdgeOrMergeWithExisting(RefEdge edgeNew) {
335 RefSrcNode src = edgeNew.getSrc();
336 assert belongsToThis(src);
338 HeapRegionNode dst = edgeNew.getDst();
339 assert belongsToThis(dst);
341 // look to see if an edge with same field exists
342 // and merge with it, otherwise just add the edge
343 RefEdge edgeExisting = src.getReferenceTo(dst,
348 if( edgeExisting != null ) {
349 edgeExisting.setBeta(
350 Canonical.unionORpreds(edgeExisting.getBeta(),
354 edgeExisting.setPreds(
355 Canonical.join(edgeExisting.getPreds(),
359 edgeExisting.setTaints(
360 Canonical.unionORpreds(edgeExisting.getTaints(),
366 addRefEdge(src, dst, edgeNew);
372 ////////////////////////////////////////////////////
374 // Assignment Operation Methods
376 // These methods are high-level operations for
377 // modeling program assignment statements using
378 // the low-level reference create/remove methods
381 ////////////////////////////////////////////////////
383 public void assignTempXEqualToTempY(TempDescriptor x,
385 assignTempXEqualToCastedTempY(x, y, null);
389 public void assignTempXEqualToCastedTempY(TempDescriptor x,
391 TypeDescriptor tdCast) {
393 VariableNode lnX = getVariableNodeFromTemp(x);
394 VariableNode lnY = getVariableNodeFromTemp(y);
396 clearRefEdgesFrom(lnX, null, null, true);
398 // note it is possible that the types of temps in the
399 // flat node to analyze will reveal that some typed
400 // edges in the reachability graph are impossible
401 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
403 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
404 while( itrYhrn.hasNext() ) {
405 RefEdge edgeY = itrYhrn.next();
406 HeapRegionNode referencee = edgeY.getDst();
407 RefEdge edgeNew = edgeY.copy();
409 if( !isSuperiorType(x.getType(), edgeY.getType() ) ) {
410 impossibleEdges.add(edgeY);
416 if( tdCast == null ) {
417 edgeNew.setType(mostSpecificType(y.getType(),
423 edgeNew.setType(mostSpecificType(y.getType(),
425 referencee.getType(),
431 edgeNew.setField(null);
433 addRefEdge(lnX, referencee, edgeNew);
436 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
437 while( itrImp.hasNext() ) {
438 RefEdge edgeImp = itrImp.next();
439 removeRefEdge(edgeImp);
444 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
447 FlatNode currentProgramPoint
450 VariableNode lnX = getVariableNodeFromTemp(x);
451 VariableNode lnY = getVariableNodeFromTemp(y);
453 clearRefEdgesFrom(lnX, null, null, true);
455 // note it is possible that the types of temps in the
456 // flat node to analyze will reveal that some typed
457 // edges in the reachability graph are impossible
458 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
460 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
461 while( itrYhrn.hasNext() ) {
462 RefEdge edgeY = itrYhrn.next();
463 HeapRegionNode hrnY = edgeY.getDst();
464 ReachSet betaY = edgeY.getBeta();
466 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
468 while( itrHrnFhrn.hasNext() ) {
469 RefEdge edgeHrn = itrHrnFhrn.next();
470 HeapRegionNode hrnHrn = edgeHrn.getDst();
471 ReachSet betaHrn = edgeHrn.getBeta();
473 // prune edges that are not a matching field
474 if( edgeHrn.getType() != null &&
475 !edgeHrn.getField().equals(f.getSymbol() )
480 // check for impossible edges
481 if( !isSuperiorType(x.getType(), edgeHrn.getType() ) ) {
482 impossibleEdges.add(edgeHrn);
486 TypeDescriptor tdNewEdge =
487 mostSpecificType(edgeHrn.getType(),
491 TaintSet taints = Canonical.unionORpreds(edgeHrn.getTaints(),
495 // the DFJ way to generate taints changes for field statements
496 taints = Canonical.changeWhereDefined(taints,
497 currentProgramPoint);
500 RefEdge edgeNew = new RefEdge(lnX,
504 Canonical.intersection(betaY, betaHrn),
509 addEdgeOrMergeWithExisting(edgeNew);
513 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
514 while( itrImp.hasNext() ) {
515 RefEdge edgeImp = itrImp.next();
516 removeRefEdge(edgeImp);
519 // anytime you might remove edges between heap regions
520 // you must global sweep to clean up broken reachability
521 if( !impossibleEdges.isEmpty() ) {
522 if( !DISABLE_GLOBAL_SWEEP ) {
530 // return whether a strong update was actually effected
531 public boolean assignTempXFieldFEqualToTempY(TempDescriptor x,
534 FlatNode currentProgramPoint
537 VariableNode lnX = getVariableNodeFromTemp(x);
538 VariableNode lnY = getVariableNodeFromTemp(y);
540 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
541 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
543 // note it is possible that the types of temps in the
544 // flat node to analyze will reveal that some typed
545 // edges in the reachability graph are impossible
546 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
548 // first look for possible strong updates and remove those edges
549 boolean strongUpdateCond = false;
550 boolean edgeRemovedByStrongUpdate = false;
552 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
553 while( itrXhrn.hasNext() ) {
554 RefEdge edgeX = itrXhrn.next();
555 HeapRegionNode hrnX = edgeX.getDst();
557 // we can do a strong update here if one of two cases holds
559 f != DisjointAnalysis.getArrayField(f.getType() ) &&
560 ( (hrnX.getNumReferencers() == 1) || // case 1
561 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
564 if( !DISABLE_STRONG_UPDATES ) {
565 strongUpdateCond = true;
568 clearRefEdgesFrom(hrnX,
573 edgeRemovedByStrongUpdate = true;
579 // then do all token propagation
580 itrXhrn = lnX.iteratorToReferencees();
581 while( itrXhrn.hasNext() ) {
582 RefEdge edgeX = itrXhrn.next();
583 HeapRegionNode hrnX = edgeX.getDst();
584 ReachSet betaX = edgeX.getBeta();
585 ReachSet R = Canonical.intersection(hrnX.getAlpha(),
589 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
590 while( itrYhrn.hasNext() ) {
591 RefEdge edgeY = itrYhrn.next();
592 HeapRegionNode hrnY = edgeY.getDst();
593 ReachSet O = edgeY.getBeta();
595 // check for impossible edges
596 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
597 impossibleEdges.add(edgeY);
601 // propagate tokens over nodes starting from hrnSrc, and it will
602 // take care of propagating back up edges from any touched nodes
603 ChangeSet Cy = Canonical.unionUpArityToChangeSet(O, R);
604 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
606 // then propagate back just up the edges from hrn
607 ChangeSet Cx = Canonical.unionUpArityToChangeSet(R, O);
608 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
610 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
611 new Hashtable<RefEdge, ChangeSet>();
613 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
614 while( referItr.hasNext() ) {
615 RefEdge edgeUpstream = referItr.next();
616 todoEdges.add(edgeUpstream);
617 edgePlannedChanges.put(edgeUpstream, Cx);
620 propagateTokensOverEdges(todoEdges,
627 // apply the updates to reachability
628 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
629 while( nodeItr.hasNext() ) {
630 nodeItr.next().applyAlphaNew();
633 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
634 while( edgeItr.hasNext() ) {
635 edgeItr.next().applyBetaNew();
639 // then go back through and add the new edges
640 itrXhrn = lnX.iteratorToReferencees();
641 while( itrXhrn.hasNext() ) {
642 RefEdge edgeX = itrXhrn.next();
643 HeapRegionNode hrnX = edgeX.getDst();
645 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
646 while( itrYhrn.hasNext() ) {
647 RefEdge edgeY = itrYhrn.next();
648 HeapRegionNode hrnY = edgeY.getDst();
650 // skip impossible edges here, we already marked them
651 // when computing reachability propagations above
652 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
656 // prepare the new reference edge hrnX.f -> hrnY
657 TypeDescriptor tdNewEdge =
658 mostSpecificType(y.getType(),
663 TaintSet taints = edgeY.getTaints();
666 // the DFJ way to generate taints changes for field statements
667 taints = Canonical.changeWhereDefined(taints,
668 currentProgramPoint);
676 Canonical.changePredsTo(
677 Canonical.pruneBy(edgeY.getBeta(),
686 addEdgeOrMergeWithExisting(edgeNew);
690 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
691 while( itrImp.hasNext() ) {
692 RefEdge edgeImp = itrImp.next();
693 removeRefEdge(edgeImp);
696 // if there was a strong update, make sure to improve
697 // reachability with a global sweep
698 if( edgeRemovedByStrongUpdate || !impossibleEdges.isEmpty() ) {
699 if( !DISABLE_GLOBAL_SWEEP ) {
704 return edgeRemovedByStrongUpdate;
708 public void assignReturnEqualToTemp(TempDescriptor x) {
710 VariableNode lnR = getVariableNodeFromTemp(tdReturn);
711 VariableNode lnX = getVariableNodeFromTemp(x);
713 clearRefEdgesFrom(lnR, null, null, true);
715 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
716 while( itrXhrn.hasNext() ) {
717 RefEdge edgeX = itrXhrn.next();
718 HeapRegionNode referencee = edgeX.getDst();
719 RefEdge edgeNew = edgeX.copy();
721 edgeNew.setTaints(Canonical.changePredsTo(edgeNew.getTaints(),
726 addRefEdge(lnR, referencee, edgeNew);
731 public void assignTempEqualToNewAlloc(TempDescriptor x,
738 // after the age operation the newest (or zero-ith oldest)
739 // node associated with the allocation site should have
740 // no references to it as if it were a newly allocated
742 Integer idNewest = as.getIthOldest(0);
743 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
744 assert hrnNewest != null;
746 VariableNode lnX = getVariableNodeFromTemp(x);
747 clearRefEdgesFrom(lnX, null, null, true);
749 // make a new reference to allocated node
750 TypeDescriptor type = as.getType();
753 new RefEdge(lnX, // source
757 hrnNewest.getAlpha(), // beta
758 predsTrue, // predicates
759 TaintSet.factory() // taints
762 addRefEdge(lnX, hrnNewest, edgeNew);
766 // use the allocation site (unique to entire analysis) to
767 // locate the heap region nodes in this reachability graph
768 // that should be aged. The process models the allocation
769 // of new objects and collects all the oldest allocations
770 // in a summary node to allow for a finite analysis
772 // There is an additional property of this method. After
773 // running it on a particular reachability graph (many graphs
774 // may have heap regions related to the same allocation site)
775 // the heap region node objects in this reachability graph will be
776 // allocated. Therefore, after aging a graph for an allocation
777 // site, attempts to retrieve the heap region nodes using the
778 // integer id's contained in the allocation site should always
779 // return non-null heap regions.
780 public void age(AllocSite as) {
782 // keep track of allocation sites that are represented
783 // in this graph for efficiency with other operations
786 // if there is a k-th oldest node, it merges into
788 Integer idK = as.getOldest();
789 if( id2hrn.containsKey(idK) ) {
790 HeapRegionNode hrnK = id2hrn.get(idK);
792 // retrieve the summary node, or make it
794 HeapRegionNode hrnSummary = getSummaryNode(as, false);
796 mergeIntoSummary(hrnK, hrnSummary);
799 // move down the line of heap region nodes
800 // clobbering the ith and transferring all references
801 // to and from i-1 to node i.
802 for( int i = allocationDepth - 1; i > 0; --i ) {
804 // only do the transfer if the i-1 node exists
805 Integer idImin1th = as.getIthOldest(i - 1);
806 if( id2hrn.containsKey(idImin1th) ) {
807 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
808 if( hrnImin1.isWiped() ) {
809 // there is no info on this node, just skip
813 // either retrieve or make target of transfer
814 HeapRegionNode hrnI = getIthNode(as, i, false);
816 transferOnto(hrnImin1, hrnI);
821 // as stated above, the newest node should have had its
822 // references moved over to the second oldest, so we wipe newest
823 // in preparation for being the new object to assign something to
824 HeapRegionNode hrn0 = getIthNode(as, 0, false);
827 // now tokens in reachability sets need to "age" also
828 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
829 while( itrAllHRNodes.hasNext() ) {
830 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
831 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
833 ageTuplesFrom(as, hrnToAge);
835 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
836 while( itrEdges.hasNext() ) {
837 ageTuplesFrom(as, itrEdges.next() );
842 // after tokens have been aged, reset newest node's reachability
843 // and a brand new node has a "true" predicate
844 hrn0.setAlpha(hrn0.getInherent() );
845 hrn0.setPreds(predsTrue);
849 // either retrieve or create the needed heap region node
850 protected HeapRegionNode getSummaryNode(AllocSite as,
855 idSummary = as.getSummaryShadow();
857 idSummary = as.getSummary();
860 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
862 if( hrnSummary == null ) {
864 String strDesc = as.toStringForDOT()+"\\nsummary";
867 createNewHeapRegionNode(idSummary, // id or null to generate a new one
868 false, // single object?
870 false, // out-of-context?
871 as.getType(), // type
872 as, // allocation site
873 null, // inherent reach
874 null, // current reach
875 predsEmpty, // predicates
876 strDesc // description
883 // either retrieve or create the needed heap region node
884 protected HeapRegionNode getIthNode(AllocSite as,
890 idIth = as.getIthOldestShadow(i);
892 idIth = as.getIthOldest(i);
895 HeapRegionNode hrnIth = id2hrn.get(idIth);
897 if( hrnIth == null ) {
899 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
901 hrnIth = createNewHeapRegionNode(idIth, // id or null to generate a new one
902 true, // single object?
904 false, // out-of-context?
905 as.getType(), // type
906 as, // allocation site
907 null, // inherent reach
908 null, // current reach
909 predsEmpty, // predicates
910 strDesc // description
918 protected void mergeIntoSummary(HeapRegionNode hrn,
919 HeapRegionNode hrnSummary) {
920 assert hrnSummary.isNewSummary();
922 // assert that these nodes belong to THIS graph
923 assert belongsToThis(hrn);
924 assert belongsToThis(hrnSummary);
926 assert hrn != hrnSummary;
928 // transfer references _from_ hrn over to hrnSummary
929 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
930 while( itrReferencee.hasNext() ) {
931 RefEdge edge = itrReferencee.next();
932 RefEdge edgeMerged = edge.copy();
933 edgeMerged.setSrc(hrnSummary);
935 HeapRegionNode hrnReferencee = edge.getDst();
936 RefEdge edgeSummary =
937 hrnSummary.getReferenceTo(hrnReferencee,
942 if( edgeSummary == null ) {
943 // the merge is trivial, nothing to be done
944 addRefEdge(hrnSummary, hrnReferencee, edgeMerged);
947 // otherwise an edge from the referencer to hrnSummary exists already
948 // and the edge referencer->hrn should be merged with it
950 Canonical.unionORpreds(edgeMerged.getBeta(),
951 edgeSummary.getBeta()
954 edgeSummary.setPreds(
955 Canonical.join(edgeMerged.getPreds(),
956 edgeSummary.getPreds()
962 // next transfer references _to_ hrn over to hrnSummary
963 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
964 while( itrReferencer.hasNext() ) {
965 RefEdge edge = itrReferencer.next();
966 RefEdge edgeMerged = edge.copy();
967 edgeMerged.setDst(hrnSummary);
969 RefSrcNode onReferencer = edge.getSrc();
970 RefEdge edgeSummary =
971 onReferencer.getReferenceTo(hrnSummary,
976 if( edgeSummary == null ) {
977 // the merge is trivial, nothing to be done
978 addRefEdge(onReferencer, hrnSummary, edgeMerged);
981 // otherwise an edge from the referencer to alpha_S exists already
982 // and the edge referencer->alpha_K should be merged with it
984 Canonical.unionORpreds(edgeMerged.getBeta(),
985 edgeSummary.getBeta()
988 edgeSummary.setPreds(
989 Canonical.join(edgeMerged.getPreds(),
990 edgeSummary.getPreds()
996 // then merge hrn reachability into hrnSummary
998 Canonical.unionORpreds(hrnSummary.getAlpha(),
1003 hrnSummary.setPreds(
1004 Canonical.join(hrnSummary.getPreds(),
1009 // and afterward, this node is gone
1014 protected void transferOnto(HeapRegionNode hrnA,
1015 HeapRegionNode hrnB) {
1017 assert belongsToThis(hrnA);
1018 assert belongsToThis(hrnB);
1019 assert hrnA != hrnB;
1021 // clear references in and out of node b?
1022 assert hrnB.isWiped();
1024 // copy each: (edge in and out of A) to B
1025 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
1026 while( itrReferencee.hasNext() ) {
1027 RefEdge edge = itrReferencee.next();
1028 HeapRegionNode hrnReferencee = edge.getDst();
1029 RefEdge edgeNew = edge.copy();
1030 edgeNew.setSrc(hrnB);
1031 edgeNew.setDst(hrnReferencee);
1033 addRefEdge(hrnB, hrnReferencee, edgeNew);
1036 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
1037 while( itrReferencer.hasNext() ) {
1038 RefEdge edge = itrReferencer.next();
1039 RefSrcNode rsnReferencer = edge.getSrc();
1040 RefEdge edgeNew = edge.copy();
1041 edgeNew.setSrc(rsnReferencer);
1042 edgeNew.setDst(hrnB);
1044 addRefEdge(rsnReferencer, hrnB, edgeNew);
1047 // replace hrnB reachability and preds with hrnA's
1048 hrnB.setAlpha(hrnA.getAlpha() );
1049 hrnB.setPreds(hrnA.getPreds() );
1051 // after transfer, wipe out source
1052 wipeOut(hrnA, true);
1056 // the purpose of this method is to conceptually "wipe out"
1057 // a heap region from the graph--purposefully not called REMOVE
1058 // because the node is still hanging around in the graph, just
1059 // not mechanically connected or have any reach or predicate
1060 // information on it anymore--lots of ops can use this
1061 protected void wipeOut(HeapRegionNode hrn,
1062 boolean wipeVariableReferences) {
1064 assert belongsToThis(hrn);
1066 clearRefEdgesFrom(hrn, null, null, true);
1068 if( wipeVariableReferences ) {
1069 clearRefEdgesTo(hrn, null, null, true);
1071 clearNonVarRefEdgesTo(hrn);
1074 hrn.setAlpha(rsetEmpty);
1075 hrn.setPreds(predsEmpty);
1079 protected void ageTuplesFrom(AllocSite as, RefEdge edge) {
1081 Canonical.ageTuplesFrom(edge.getBeta(),
1087 protected void ageTuplesFrom(AllocSite as, HeapRegionNode hrn) {
1089 Canonical.ageTuplesFrom(hrn.getAlpha(),
1097 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1099 HashSet<HeapRegionNode> nodesWithNewAlpha,
1100 HashSet<RefEdge> edgesWithNewBeta) {
1102 HashSet<HeapRegionNode> todoNodes
1103 = new HashSet<HeapRegionNode>();
1104 todoNodes.add(nPrime);
1106 HashSet<RefEdge> todoEdges
1107 = new HashSet<RefEdge>();
1109 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1110 = new Hashtable<HeapRegionNode, ChangeSet>();
1111 nodePlannedChanges.put(nPrime, c0);
1113 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1114 = new Hashtable<RefEdge, ChangeSet>();
1116 // first propagate change sets everywhere they can go
1117 while( !todoNodes.isEmpty() ) {
1118 HeapRegionNode n = todoNodes.iterator().next();
1119 ChangeSet C = nodePlannedChanges.get(n);
1121 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1122 while( referItr.hasNext() ) {
1123 RefEdge edge = referItr.next();
1124 todoEdges.add(edge);
1126 if( !edgePlannedChanges.containsKey(edge) ) {
1127 edgePlannedChanges.put(edge,
1132 edgePlannedChanges.put(edge,
1133 Canonical.union(edgePlannedChanges.get(edge),
1139 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1140 while( refeeItr.hasNext() ) {
1141 RefEdge edgeF = refeeItr.next();
1142 HeapRegionNode m = edgeF.getDst();
1144 ChangeSet changesToPass = ChangeSet.factory();
1146 Iterator<ChangeTuple> itrCprime = C.iterator();
1147 while( itrCprime.hasNext() ) {
1148 ChangeTuple c = itrCprime.next();
1149 if( edgeF.getBeta().containsIgnorePreds(c.getStateToMatch() )
1152 changesToPass = Canonical.add(changesToPass, c);
1156 if( !changesToPass.isEmpty() ) {
1157 if( !nodePlannedChanges.containsKey(m) ) {
1158 nodePlannedChanges.put(m, ChangeSet.factory() );
1161 ChangeSet currentChanges = nodePlannedChanges.get(m);
1163 if( !changesToPass.isSubset(currentChanges) ) {
1165 nodePlannedChanges.put(m,
1166 Canonical.union(currentChanges,
1175 todoNodes.remove(n);
1178 // then apply all of the changes for each node at once
1179 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1180 while( itrMap.hasNext() ) {
1181 Map.Entry me = (Map.Entry)itrMap.next();
1182 HeapRegionNode n = (HeapRegionNode) me.getKey();
1183 ChangeSet C = (ChangeSet) me.getValue();
1185 // this propagation step is with respect to one change,
1186 // so we capture the full change from the old alpha:
1187 ReachSet localDelta = Canonical.applyChangeSet(n.getAlpha(),
1191 // but this propagation may be only one of many concurrent
1192 // possible changes, so keep a running union with the node's
1193 // partially updated new alpha set
1194 n.setAlphaNew(Canonical.unionORpreds(n.getAlphaNew(),
1199 nodesWithNewAlpha.add(n);
1202 propagateTokensOverEdges(todoEdges,
1209 protected void propagateTokensOverEdges(HashSet <RefEdge> todoEdges,
1210 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1211 HashSet <RefEdge> edgesWithNewBeta) {
1213 // first propagate all change tuples everywhere they can go
1214 while( !todoEdges.isEmpty() ) {
1215 RefEdge edgeE = todoEdges.iterator().next();
1216 todoEdges.remove(edgeE);
1218 if( !edgePlannedChanges.containsKey(edgeE) ) {
1219 edgePlannedChanges.put(edgeE,
1224 ChangeSet C = edgePlannedChanges.get(edgeE);
1226 ChangeSet changesToPass = ChangeSet.factory();
1228 Iterator<ChangeTuple> itrC = C.iterator();
1229 while( itrC.hasNext() ) {
1230 ChangeTuple c = itrC.next();
1231 if( edgeE.getBeta().containsIgnorePreds(c.getStateToMatch() )
1234 changesToPass = Canonical.add(changesToPass, c);
1238 RefSrcNode rsn = edgeE.getSrc();
1240 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1241 HeapRegionNode n = (HeapRegionNode) rsn;
1243 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1244 while( referItr.hasNext() ) {
1245 RefEdge edgeF = referItr.next();
1247 if( !edgePlannedChanges.containsKey(edgeF) ) {
1248 edgePlannedChanges.put(edgeF,
1253 ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
1255 if( !changesToPass.isSubset(currentChanges) ) {
1256 todoEdges.add(edgeF);
1257 edgePlannedChanges.put(edgeF,
1258 Canonical.union(currentChanges,
1267 // then apply all of the changes for each edge at once
1268 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1269 while( itrMap.hasNext() ) {
1270 Map.Entry me = (Map.Entry)itrMap.next();
1271 RefEdge e = (RefEdge) me.getKey();
1272 ChangeSet C = (ChangeSet) me.getValue();
1274 // this propagation step is with respect to one change,
1275 // so we capture the full change from the old beta:
1276 ReachSet localDelta =
1277 Canonical.applyChangeSet(e.getBeta(),
1282 // but this propagation may be only one of many concurrent
1283 // possible changes, so keep a running union with the edge's
1284 // partially updated new beta set
1285 e.setBetaNew(Canonical.unionORpreds(e.getBetaNew(),
1290 edgesWithNewBeta.add(e);
1295 public void taintInSetVars(FlatSESEEnterNode sese) {
1297 Iterator<TempDescriptor> isvItr = sese.getInVarSet().iterator();
1298 while( isvItr.hasNext() ) {
1299 TempDescriptor isv = isvItr.next();
1301 // use this where defined flatnode to support RCR/DFJ
1302 FlatNode whereDefined = null;
1304 // in-set var taints should NOT propagate back into callers
1305 // so give it FALSE(EMPTY) predicates
1315 public void taintStallSite(FlatNode stallSite,
1316 TempDescriptor var) {
1318 // use this where defined flatnode to support RCR/DFJ
1319 FlatNode whereDefined = null;
1321 // stall site taint should propagate back into callers
1322 // so give it TRUE predicates
1331 protected void taintTemp(FlatSESEEnterNode sese,
1334 FlatNode whereDefined,
1338 VariableNode vn = getVariableNodeFromTemp(var);
1340 Iterator<RefEdge> reItr = vn.iteratorToReferencees();
1341 while( reItr.hasNext() ) {
1342 RefEdge re = reItr.next();
1344 Taint taint = Taint.factory(sese,
1347 re.getDst().getAllocSite(),
1352 re.setTaints(Canonical.add(re.getTaints(),
1359 public void removeInContextTaints(FlatSESEEnterNode sese) {
1361 Iterator meItr = id2hrn.entrySet().iterator();
1362 while( meItr.hasNext() ) {
1363 Map.Entry me = (Map.Entry)meItr.next();
1364 Integer id = (Integer) me.getKey();
1365 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1367 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1368 while( reItr.hasNext() ) {
1369 RefEdge re = reItr.next();
1371 re.setTaints(Canonical.removeInContextTaints(re.getTaints(),
1379 public void removeAllStallSiteTaints() {
1381 Iterator meItr = id2hrn.entrySet().iterator();
1382 while( meItr.hasNext() ) {
1383 Map.Entry me = (Map.Entry)meItr.next();
1384 Integer id = (Integer) me.getKey();
1385 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1387 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1388 while( reItr.hasNext() ) {
1389 RefEdge re = reItr.next();
1391 re.setTaints(Canonical.removeStallSiteTaints(re.getTaints()
1399 // used in makeCalleeView below to decide if there is
1400 // already an appropriate out-of-context edge in a callee
1401 // view graph for merging, or null if a new one will be added
1403 getOutOfContextReferenceTo(HeapRegionNode hrn,
1404 TypeDescriptor srcType,
1405 TypeDescriptor refType,
1407 assert belongsToThis(hrn);
1409 HeapRegionNode hrnInContext = id2hrn.get(hrn.getID() );
1410 if( hrnInContext == null ) {
1414 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1415 while( refItr.hasNext() ) {
1416 RefEdge re = refItr.next();
1418 assert belongsToThis(re.getSrc() );
1419 assert belongsToThis(re.getDst() );
1421 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1425 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1426 if( !hrnSrc.isOutOfContext() ) {
1430 if( srcType == null ) {
1431 if( hrnSrc.getType() != null ) {
1435 if( !srcType.equals(hrnSrc.getType() ) ) {
1440 if( !re.typeEquals(refType) ) {
1444 if( !re.fieldEquals(refField) ) {
1448 // tada! We found it!
1455 // used below to convert a ReachSet to its callee-context
1456 // equivalent with respect to allocation sites in this graph
1457 protected ReachSet toCalleeContext(ReachSet rs,
1458 ExistPredSet predsNodeOrEdge,
1459 Set<HrnIdOoc> oocHrnIdOoc2callee
1461 ReachSet out = ReachSet.factory();
1463 Iterator<ReachState> itr = rs.iterator();
1464 while( itr.hasNext() ) {
1465 ReachState stateCaller = itr.next();
1467 ReachState stateCallee = stateCaller;
1469 Iterator<AllocSite> asItr = allocSites.iterator();
1470 while( asItr.hasNext() ) {
1471 AllocSite as = asItr.next();
1473 ReachState stateNew = ReachState.factory();
1474 Iterator<ReachTuple> rtItr = stateCallee.iterator();
1475 while( rtItr.hasNext() ) {
1476 ReachTuple rt = rtItr.next();
1478 // only translate this tuple if it is
1479 // in the out-callee-context bag
1480 HrnIdOoc hio = new HrnIdOoc(rt.getHrnID(),
1483 if( !oocHrnIdOoc2callee.contains(hio) ) {
1484 stateNew = Canonical.addUpArity(stateNew, rt);
1488 int age = as.getAgeCategory(rt.getHrnID() );
1490 // this is the current mapping, where 0, 1, 2S were allocated
1491 // in the current context, 0?, 1? and 2S? were allocated in a
1492 // previous context, and we're translating to a future context
1504 if( age == AllocSite.AGE_notInThisSite ) {
1505 // things not from the site just go back in
1506 stateNew = Canonical.addUpArity(stateNew, rt);
1508 } else if( age == AllocSite.AGE_summary ||
1512 stateNew = Canonical.addUpArity(stateNew,
1513 ReachTuple.factory(as.getSummary(),
1516 true // out-of-context
1521 // otherwise everything else just goes to an out-of-context
1522 // version, everything else the same
1523 Integer I = as.getAge(rt.getHrnID() );
1526 assert !rt.isMultiObject();
1528 stateNew = Canonical.addUpArity(stateNew,
1529 ReachTuple.factory(rt.getHrnID(),
1530 rt.isMultiObject(), // multi
1532 true // out-of-context
1538 stateCallee = stateNew;
1541 // make a predicate of the caller graph element
1542 // and the caller state we just converted
1543 ExistPredSet predsWithState = ExistPredSet.factory();
1545 Iterator<ExistPred> predItr = predsNodeOrEdge.iterator();
1546 while( predItr.hasNext() ) {
1547 ExistPred predNodeOrEdge = predItr.next();
1550 Canonical.add(predsWithState,
1551 ExistPred.factory(predNodeOrEdge.n_hrnID,
1552 predNodeOrEdge.e_tdSrc,
1553 predNodeOrEdge.e_hrnSrcID,
1554 predNodeOrEdge.e_hrnDstID,
1555 predNodeOrEdge.e_type,
1556 predNodeOrEdge.e_field,
1559 predNodeOrEdge.e_srcOutCalleeContext,
1560 predNodeOrEdge.e_srcOutCallerContext
1565 stateCallee = Canonical.changePredsTo(stateCallee,
1568 out = Canonical.add(out,
1572 assert out.isCanonical();
1576 // used below to convert a ReachSet to its caller-context
1577 // equivalent with respect to allocation sites in this graph
1579 toCallerContext(ReachSet rs,
1580 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1582 ReachSet out = ReachSet.factory();
1584 // when the mapping is null it means there were no
1585 // predicates satisfied
1586 if( calleeStatesSatisfied == null ) {
1590 Iterator<ReachState> itr = rs.iterator();
1591 while( itr.hasNext() ) {
1592 ReachState stateCallee = itr.next();
1594 if( calleeStatesSatisfied.containsKey(stateCallee) ) {
1596 // starting from one callee state...
1597 ReachSet rsCaller = ReachSet.factory(stateCallee);
1599 // possibly branch it into many states, which any
1600 // allocation site might do, so lots of derived states
1601 Iterator<AllocSite> asItr = allocSites.iterator();
1602 while( asItr.hasNext() ) {
1603 AllocSite as = asItr.next();
1604 rsCaller = Canonical.toCallerContext(rsCaller, as);
1607 // then before adding each derived, now caller-context
1608 // states to the output, attach the appropriate pred
1609 // based on the source callee state
1610 Iterator<ReachState> stateItr = rsCaller.iterator();
1611 while( stateItr.hasNext() ) {
1612 ReachState stateCaller = stateItr.next();
1613 stateCaller = Canonical.attach(stateCaller,
1614 calleeStatesSatisfied.get(stateCallee)
1616 out = Canonical.add(out,
1623 assert out.isCanonical();
1628 // used below to convert a ReachSet to an equivalent
1629 // version with shadow IDs merged into unshadowed IDs
1630 protected ReachSet unshadow(ReachSet rs) {
1632 Iterator<AllocSite> asItr = allocSites.iterator();
1633 while( asItr.hasNext() ) {
1634 AllocSite as = asItr.next();
1635 out = Canonical.unshadow(out, as);
1637 assert out.isCanonical();
1642 // convert a caller taint set into a callee taint set
1644 toCalleeContext(TaintSet ts,
1645 ExistPredSet predsEdge) {
1647 TaintSet out = TaintSet.factory();
1649 // the idea is easy, the taint identifier itself doesn't
1650 // change at all, but the predicates should be tautology:
1651 // start with the preds passed in from the caller edge
1652 // that host the taints, and alter them to have the taint
1653 // added, just becoming more specific than edge predicate alone
1655 Iterator<Taint> itr = ts.iterator();
1656 while( itr.hasNext() ) {
1657 Taint tCaller = itr.next();
1659 ExistPredSet predsWithTaint = ExistPredSet.factory();
1661 Iterator<ExistPred> predItr = predsEdge.iterator();
1662 while( predItr.hasNext() ) {
1663 ExistPred predEdge = predItr.next();
1666 Canonical.add(predsWithTaint,
1667 ExistPred.factory(predEdge.e_tdSrc,
1668 predEdge.e_hrnSrcID,
1669 predEdge.e_hrnDstID,
1674 predEdge.e_srcOutCalleeContext,
1675 predEdge.e_srcOutCallerContext
1680 Taint tCallee = Canonical.changePredsTo(tCaller,
1683 out = Canonical.add(out,
1688 assert out.isCanonical();
1693 // used below to convert a TaintSet to its caller-context
1694 // equivalent, just eliminate Taints with bad preds
1696 toCallerContext(TaintSet ts,
1697 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied
1700 TaintSet out = TaintSet.factory();
1702 // when the mapping is null it means there were no
1703 // predicates satisfied
1704 if( calleeTaintsSatisfied == null ) {
1708 Iterator<Taint> itr = ts.iterator();
1709 while( itr.hasNext() ) {
1710 Taint tCallee = itr.next();
1712 if( calleeTaintsSatisfied.containsKey(tCallee) ) {
1715 Canonical.attach(Taint.factory(tCallee.sese,
1720 ExistPredSet.factory() ),
1721 calleeTaintsSatisfied.get(tCallee)
1723 out = Canonical.add(out,
1729 assert out.isCanonical();
1736 // use this method to make a new reach graph that is
1737 // what heap the FlatMethod callee from the FlatCall
1738 // would start with reaching from its arguments in
1741 makeCalleeView(FlatCall fc,
1742 FlatMethod fmCallee,
1743 Set<Integer> callerNodeIDsCopiedToCallee,
1744 boolean writeDebugDOTs
1748 // first traverse this context to find nodes and edges
1749 // that will be callee-reachable
1750 Set<HeapRegionNode> reachableCallerNodes =
1751 new HashSet<HeapRegionNode>();
1753 // caller edges between callee-reachable nodes
1754 Set<RefEdge> reachableCallerEdges =
1755 new HashSet<RefEdge>();
1757 // caller edges from arg vars, and the matching param index
1758 // because these become a special edge in callee
1759 Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1760 new Hashtable<RefEdge, Integer>();
1762 // caller edges from local vars or callee-unreachable nodes
1763 // (out-of-context sources) to callee-reachable nodes
1764 Set<RefEdge> oocCallerEdges =
1765 new HashSet<RefEdge>();
1768 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1770 TempDescriptor tdArg = fc.getArgMatchingParamIndex(fmCallee, i);
1771 VariableNode vnArgCaller = this.getVariableNodeFromTemp(tdArg);
1773 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1774 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1776 toVisitInCaller.add(vnArgCaller);
1778 while( !toVisitInCaller.isEmpty() ) {
1779 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1780 toVisitInCaller.remove(rsnCaller);
1781 visitedInCaller.add(rsnCaller);
1783 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1784 while( itrRefEdges.hasNext() ) {
1785 RefEdge reCaller = itrRefEdges.next();
1786 HeapRegionNode hrnCaller = reCaller.getDst();
1788 callerNodeIDsCopiedToCallee.add(hrnCaller.getID() );
1789 reachableCallerNodes.add(hrnCaller);
1791 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1792 reachableCallerEdges.add(reCaller);
1794 if( rsnCaller.equals(vnArgCaller) ) {
1795 reachableCallerArgEdges2paramIndex.put(reCaller, i);
1797 oocCallerEdges.add(reCaller);
1801 if( !visitedInCaller.contains(hrnCaller) ) {
1802 toVisitInCaller.add(hrnCaller);
1805 } // end edge iteration
1806 } // end visiting heap nodes in caller
1807 } // end iterating over parameters as starting points
1810 // now collect out-of-callee-context IDs and
1811 // map them to whether the ID is out of the caller
1813 Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1815 Iterator<Integer> itrInContext =
1816 callerNodeIDsCopiedToCallee.iterator();
1817 while( itrInContext.hasNext() ) {
1818 Integer hrnID = itrInContext.next();
1819 HeapRegionNode hrnCallerAndInContext = id2hrn.get(hrnID);
1821 Iterator<RefEdge> itrMightCross =
1822 hrnCallerAndInContext.iteratorToReferencers();
1823 while( itrMightCross.hasNext() ) {
1824 RefEdge edgeMightCross = itrMightCross.next();
1826 RefSrcNode rsnCallerAndOutContext =
1827 edgeMightCross.getSrc();
1829 if( rsnCallerAndOutContext instanceof VariableNode ) {
1830 // variables do not have out-of-context reach states,
1832 oocCallerEdges.add(edgeMightCross);
1836 HeapRegionNode hrnCallerAndOutContext =
1837 (HeapRegionNode) rsnCallerAndOutContext;
1839 // is this source node out-of-context?
1840 if( callerNodeIDsCopiedToCallee.contains(hrnCallerAndOutContext.getID() ) ) {
1841 // no, skip this edge
1846 oocCallerEdges.add(edgeMightCross);
1848 // add all reach tuples on the node to list
1849 // of things that are out-of-context: insight
1850 // if this node is reachable from someting that WAS
1851 // in-context, then this node should already be in-context
1852 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1853 while( stateItr.hasNext() ) {
1854 ReachState state = stateItr.next();
1856 Iterator<ReachTuple> rtItr = state.iterator();
1857 while( rtItr.hasNext() ) {
1858 ReachTuple rt = rtItr.next();
1860 oocHrnIdOoc2callee.add(new HrnIdOoc(rt.getHrnID(),
1869 // the callee view is a new graph: DON'T MODIFY *THIS* graph
1870 ReachGraph rg = new ReachGraph();
1872 // add nodes to callee graph
1873 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1874 while( hrnItr.hasNext() ) {
1875 HeapRegionNode hrnCaller = hrnItr.next();
1877 assert callerNodeIDsCopiedToCallee.contains(hrnCaller.getID() );
1878 assert !rg.id2hrn.containsKey(hrnCaller.getID() );
1880 ExistPred pred = ExistPred.factory(hrnCaller.getID(), null);
1881 ExistPredSet preds = ExistPredSet.factory(pred);
1883 rg.createNewHeapRegionNode(hrnCaller.getID(),
1884 hrnCaller.isSingleObject(),
1885 hrnCaller.isNewSummary(),
1886 false, // out-of-context?
1887 hrnCaller.getType(),
1888 hrnCaller.getAllocSite(),
1889 toCalleeContext(hrnCaller.getInherent(),
1893 toCalleeContext(hrnCaller.getAlpha(),
1898 hrnCaller.getDescription()
1902 // add param edges to callee graph
1904 reachableCallerArgEdges2paramIndex.entrySet().iterator();
1905 while( argEdges.hasNext() ) {
1906 Map.Entry me = (Map.Entry)argEdges.next();
1907 RefEdge reArg = (RefEdge) me.getKey();
1908 Integer index = (Integer) me.getValue();
1910 VariableNode vnCaller = (VariableNode) reArg.getSrc();
1911 TempDescriptor argCaller = vnCaller.getTempDescriptor();
1913 TempDescriptor paramCallee = fmCallee.getParameter(index);
1914 VariableNode vnCallee = rg.getVariableNodeFromTemp(paramCallee);
1916 HeapRegionNode hrnDstCaller = reArg.getDst();
1917 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
1918 assert hrnDstCallee != null;
1921 ExistPred.factory(argCaller,
1923 hrnDstCallee.getID(),
1928 true, // out-of-callee-context
1929 false // out-of-caller-context
1932 ExistPredSet preds =
1933 ExistPredSet.factory(pred);
1936 new RefEdge(vnCallee,
1940 toCalleeContext(reArg.getBeta(),
1945 toCalleeContext(reArg.getTaints(),
1949 rg.addRefEdge(vnCallee,
1955 // add in-context edges to callee graph
1956 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1957 while( reItr.hasNext() ) {
1958 RefEdge reCaller = reItr.next();
1959 RefSrcNode rsnCaller = reCaller.getSrc();
1960 assert rsnCaller instanceof HeapRegionNode;
1961 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1962 HeapRegionNode hrnDstCaller = reCaller.getDst();
1964 HeapRegionNode hrnSrcCallee = rg.id2hrn.get(hrnSrcCaller.getID() );
1965 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
1966 assert hrnSrcCallee != null;
1967 assert hrnDstCallee != null;
1970 ExistPred.factory(null,
1971 hrnSrcCallee.getID(),
1972 hrnDstCallee.getID(),
1974 reCaller.getField(),
1977 false, // out-of-callee-context
1978 false // out-of-caller-context
1981 ExistPredSet preds =
1982 ExistPredSet.factory(pred);
1985 new RefEdge(hrnSrcCallee,
1988 reCaller.getField(),
1989 toCalleeContext(reCaller.getBeta(),
1994 toCalleeContext(reCaller.getTaints(),
1998 rg.addRefEdge(hrnSrcCallee,
2004 // add out-of-context edges to callee graph
2005 reItr = oocCallerEdges.iterator();
2006 while( reItr.hasNext() ) {
2007 RefEdge reCaller = reItr.next();
2008 RefSrcNode rsnCaller = reCaller.getSrc();
2009 HeapRegionNode hrnDstCaller = reCaller.getDst();
2010 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2011 assert hrnDstCallee != null;
2013 TypeDescriptor oocNodeType;
2015 TempDescriptor oocPredSrcTemp = null;
2016 Integer oocPredSrcID = null;
2017 boolean outOfCalleeContext;
2018 boolean outOfCallerContext;
2020 if( rsnCaller instanceof VariableNode ) {
2021 VariableNode vnCaller = (VariableNode) rsnCaller;
2023 oocReach = rsetEmpty;
2024 oocPredSrcTemp = vnCaller.getTempDescriptor();
2025 outOfCalleeContext = true;
2026 outOfCallerContext = false;
2029 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2030 assert !callerNodeIDsCopiedToCallee.contains(hrnSrcCaller.getID() );
2031 oocNodeType = hrnSrcCaller.getType();
2032 oocReach = hrnSrcCaller.getAlpha();
2033 oocPredSrcID = hrnSrcCaller.getID();
2034 if( hrnSrcCaller.isOutOfContext() ) {
2035 outOfCalleeContext = false;
2036 outOfCallerContext = true;
2038 outOfCalleeContext = true;
2039 outOfCallerContext = false;
2044 ExistPred.factory(oocPredSrcTemp,
2046 hrnDstCallee.getID(),
2048 reCaller.getField(),
2055 ExistPredSet preds =
2056 ExistPredSet.factory(pred);
2058 RefEdge oocEdgeExisting =
2059 rg.getOutOfContextReferenceTo(hrnDstCallee,
2065 if( oocEdgeExisting == null ) {
2066 // for consistency, map one out-of-context "identifier"
2067 // to one heap region node id, otherwise no convergence
2068 String oocid = "oocid"+
2070 hrnDstCallee.getIDString()+
2073 reCaller.getField();
2075 Integer oocHrnID = oocid2hrnid.get(oocid);
2077 HeapRegionNode hrnCalleeAndOutContext;
2079 if( oocHrnID == null ) {
2081 hrnCalleeAndOutContext =
2082 rg.createNewHeapRegionNode(null, // ID
2083 false, // single object?
2084 false, // new summary?
2085 true, // out-of-context?
2087 null, // alloc site, shouldn't be used
2088 toCalleeContext(oocReach,
2092 toCalleeContext(oocReach,
2100 oocid2hrnid.put(oocid, hrnCalleeAndOutContext.getID() );
2104 // the mapping already exists, so see if node is there
2105 hrnCalleeAndOutContext = rg.id2hrn.get(oocHrnID);
2107 if( hrnCalleeAndOutContext == null ) {
2109 hrnCalleeAndOutContext =
2110 rg.createNewHeapRegionNode(oocHrnID, // ID
2111 false, // single object?
2112 false, // new summary?
2113 true, // out-of-context?
2115 null, // alloc site, shouldn't be used
2116 toCalleeContext(oocReach,
2120 toCalleeContext(oocReach,
2129 // otherwise it is there, so merge reachability
2130 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2131 toCalleeContext(oocReach,
2140 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2142 rg.addRefEdge(hrnCalleeAndOutContext,
2144 new RefEdge(hrnCalleeAndOutContext,
2147 reCaller.getField(),
2148 toCalleeContext(reCaller.getBeta(),
2153 toCalleeContext(reCaller.getTaints(),
2159 // the out-of-context edge already exists
2160 oocEdgeExisting.setBeta(Canonical.unionORpreds(oocEdgeExisting.getBeta(),
2161 toCalleeContext(reCaller.getBeta(),
2168 oocEdgeExisting.setPreds(Canonical.join(oocEdgeExisting.getPreds(),
2173 oocEdgeExisting.setTaints(Canonical.unionORpreds(oocEdgeExisting.getTaints(),
2174 toCalleeContext(reCaller.getTaints(),
2180 HeapRegionNode hrnCalleeAndOutContext =
2181 (HeapRegionNode) oocEdgeExisting.getSrc();
2182 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2183 toCalleeContext(oocReach,
2190 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2195 if( writeDebugDOTs ) {
2196 debugGraphPrefix = String.format("call%03d", debugCallSiteVisitCounter);
2197 rg.writeGraph(debugGraphPrefix+"calleeview",
2198 resolveMethodDebugDOTwriteLabels,
2199 resolveMethodDebugDOTselectTemps,
2200 resolveMethodDebugDOTpruneGarbage,
2201 resolveMethodDebugDOThideReach,
2202 resolveMethodDebugDOThideSubsetReach,
2203 resolveMethodDebugDOThidePreds,
2204 resolveMethodDebugDOThideEdgeTaints);
2210 private static Hashtable<String, Integer> oocid2hrnid =
2211 new Hashtable<String, Integer>();
2214 // useful since many graphs writes in the method call debug code
2215 private static boolean resolveMethodDebugDOTwriteLabels = true;
2216 private static boolean resolveMethodDebugDOTselectTemps = true;
2217 private static boolean resolveMethodDebugDOTpruneGarbage = true;
2218 private static boolean resolveMethodDebugDOThideReach = true;
2219 private static boolean resolveMethodDebugDOThideSubsetReach = true;
2220 private static boolean resolveMethodDebugDOThidePreds = true;
2221 private static boolean resolveMethodDebugDOThideEdgeTaints = false;
2223 static String debugGraphPrefix;
2224 static int debugCallSiteVisitCounter;
2225 static int debugCallSiteVisitStartCapture;
2226 static int debugCallSiteNumVisitsToCapture;
2227 static boolean debugCallSiteStopAfter;
2231 resolveMethodCall(FlatCall fc,
2232 FlatMethod fmCallee,
2233 ReachGraph rgCallee,
2234 Set<Integer> callerNodeIDsCopiedToCallee,
2235 boolean writeDebugDOTs
2238 if( writeDebugDOTs ) {
2240 System.out.println(" Writing out visit "+
2241 debugCallSiteVisitCounter+
2242 " to debug call site");
2244 debugGraphPrefix = String.format("call%03d",
2245 debugCallSiteVisitCounter);
2247 rgCallee.writeGraph(debugGraphPrefix+"callee",
2248 resolveMethodDebugDOTwriteLabels,
2249 resolveMethodDebugDOTselectTemps,
2250 resolveMethodDebugDOTpruneGarbage,
2251 resolveMethodDebugDOThideReach,
2252 resolveMethodDebugDOThideSubsetReach,
2253 resolveMethodDebugDOThidePreds,
2254 resolveMethodDebugDOThideEdgeTaints);
2256 writeGraph(debugGraphPrefix+"caller00In",
2257 resolveMethodDebugDOTwriteLabels,
2258 resolveMethodDebugDOTselectTemps,
2259 resolveMethodDebugDOTpruneGarbage,
2260 resolveMethodDebugDOThideReach,
2261 resolveMethodDebugDOThideSubsetReach,
2262 resolveMethodDebugDOThidePreds,
2263 resolveMethodDebugDOThideEdgeTaints,
2264 callerNodeIDsCopiedToCallee);
2269 // method call transfer function steps:
2270 // 1. Use current callee-reachable heap (CRH) to test callee
2271 // predicates and mark what will be coming in.
2272 // 2. Wipe CRH out of caller.
2273 // 3. Transplant marked callee parts in:
2274 // a) bring in nodes
2275 // b) bring in callee -> callee edges
2276 // c) resolve out-of-context -> callee edges
2277 // d) assign return value
2278 // 4. Collapse shadow nodes down
2279 // 5. Global sweep it.
2282 // 1. mark what callee elements have satisfied predicates
2283 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
2284 new Hashtable<HeapRegionNode, ExistPredSet>();
2286 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
2287 new Hashtable<RefEdge, ExistPredSet>();
2289 Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
2290 calleeNode2calleeStatesSatisfied =
2291 new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
2293 Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
2294 calleeEdge2calleeStatesSatisfied =
2295 new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
2297 Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
2298 calleeEdge2calleeTaintsSatisfied =
2299 new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
2301 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
2302 new Hashtable< RefEdge, Set<RefSrcNode> >();
2305 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2306 while( meItr.hasNext() ) {
2307 Map.Entry me = (Map.Entry)meItr.next();
2308 Integer id = (Integer) me.getKey();
2309 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2311 // if a callee element's predicates are satisfied then a set
2312 // of CALLER predicates is returned: they are the predicates
2313 // that the callee element moved into the caller context
2314 // should have, and it is inefficient to find this again later
2315 ExistPredSet predsIfSatis =
2316 hrnCallee.getPreds().isSatisfiedBy(this,
2317 callerNodeIDsCopiedToCallee
2320 if( predsIfSatis != null ) {
2321 calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
2323 // otherwise don't bother looking at edges to this node
2327 // since the node is coming over, find out which reach
2328 // states on it should come over, too
2329 assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
2331 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2332 while( stateItr.hasNext() ) {
2333 ReachState stateCallee = stateItr.next();
2336 stateCallee.getPreds().isSatisfiedBy(this,
2337 callerNodeIDsCopiedToCallee
2339 if( predsIfSatis != null ) {
2341 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2342 calleeNode2calleeStatesSatisfied.get(hrnCallee);
2344 if( calleeStatesSatisfied == null ) {
2345 calleeStatesSatisfied =
2346 new Hashtable<ReachState, ExistPredSet>();
2348 calleeNode2calleeStatesSatisfied.put(hrnCallee, calleeStatesSatisfied);
2351 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2355 // then look at edges to the node
2356 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2357 while( reItr.hasNext() ) {
2358 RefEdge reCallee = reItr.next();
2359 RefSrcNode rsnCallee = reCallee.getSrc();
2361 // (caller local variables to in-context heap regions)
2362 // have an (out-of-context heap region -> in-context heap region)
2363 // abstraction in the callEE, so its true we never need to
2364 // look at a (var node -> heap region) edge in callee to bring
2365 // those over for the call site transfer, except for the special
2366 // case of *RETURN var* -> heap region edges.
2367 // What about (param var->heap region)
2368 // edges in callee? They are dealt with below this loop.
2370 if( rsnCallee instanceof VariableNode ) {
2372 // looking for the return-value variable only
2373 VariableNode vnCallee = (VariableNode) rsnCallee;
2374 if( vnCallee.getTempDescriptor() != tdReturn ) {
2378 TempDescriptor returnTemp = fc.getReturnTemp();
2379 if( returnTemp == null ||
2380 !DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2385 // note that the assignment of the return value is to a
2386 // variable in the caller which is out-of-context with
2387 // respect to the callee
2388 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2389 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2390 rsnCallers.add(vnLhsCaller);
2391 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2395 // for HeapRegionNode callee sources...
2397 // first see if the source is out-of-context, and only
2398 // proceed with this edge if we find some caller-context
2400 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2401 boolean matchedOutOfContext = false;
2403 if( !hrnSrcCallee.isOutOfContext() ) {
2406 hrnSrcCallee.getPreds().isSatisfiedBy(this,
2407 callerNodeIDsCopiedToCallee
2409 if( predsIfSatis != null ) {
2410 calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
2412 // otherwise forget this edge
2417 // hrnSrcCallee is out-of-context
2419 assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
2421 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2423 // is the target node in the caller?
2424 HeapRegionNode hrnDstCaller = this.id2hrn.get(hrnCallee.getID() );
2425 if( hrnDstCaller == null ) {
2429 Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2430 while( reDstItr.hasNext() ) {
2431 // the edge and field (either possibly null) must match
2432 RefEdge reCaller = reDstItr.next();
2434 if( !reCaller.typeEquals(reCallee.getType() ) ||
2435 !reCaller.fieldEquals(reCallee.getField() )
2440 RefSrcNode rsnCaller = reCaller.getSrc();
2441 if( rsnCaller instanceof VariableNode ) {
2443 // a variable node matches an OOC region with null type
2444 if( hrnSrcCallee.getType() != null ) {
2449 // otherwise types should match
2450 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2451 if( hrnSrcCallee.getType() == null ) {
2452 if( hrnCallerSrc.getType() != null ) {
2456 if( !hrnSrcCallee.getType().equals(hrnCallerSrc.getType() ) ) {
2462 rsnCallers.add(rsnCaller);
2463 matchedOutOfContext = true;
2466 if( !rsnCallers.isEmpty() ) {
2467 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2471 if( hrnSrcCallee.isOutOfContext() &&
2472 !matchedOutOfContext ) {
2479 reCallee.getPreds().isSatisfiedBy(this,
2480 callerNodeIDsCopiedToCallee
2483 if( predsIfSatis != null ) {
2484 calleeEdgesSatisfied.put(reCallee, predsIfSatis);
2486 // since the edge is coming over, find out which reach
2487 // states on it should come over, too
2488 assert calleeEdge2calleeStatesSatisfied.get(reCallee) == null;
2490 stateItr = reCallee.getBeta().iterator();
2491 while( stateItr.hasNext() ) {
2492 ReachState stateCallee = stateItr.next();
2495 stateCallee.getPreds().isSatisfiedBy(this,
2496 callerNodeIDsCopiedToCallee
2498 if( predsIfSatis != null ) {
2500 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2501 calleeEdge2calleeStatesSatisfied.get(reCallee);
2503 if( calleeStatesSatisfied == null ) {
2504 calleeStatesSatisfied =
2505 new Hashtable<ReachState, ExistPredSet>();
2507 calleeEdge2calleeStatesSatisfied.put(reCallee, calleeStatesSatisfied);
2510 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2514 // since the edge is coming over, find out which taints
2515 // on it should come over, too
2516 assert calleeEdge2calleeTaintsSatisfied.get(reCallee) == null;
2518 Iterator<Taint> tItr = reCallee.getTaints().iterator();
2519 while( tItr.hasNext() ) {
2520 Taint tCallee = tItr.next();
2523 tCallee.getPreds().isSatisfiedBy(this,
2524 callerNodeIDsCopiedToCallee
2526 if( predsIfSatis != null ) {
2528 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2529 calleeEdge2calleeTaintsSatisfied.get(reCallee);
2531 if( calleeTaintsSatisfied == null ) {
2532 calleeTaintsSatisfied =
2533 new Hashtable<Taint, ExistPredSet>();
2535 calleeEdge2calleeTaintsSatisfied.put(reCallee, calleeTaintsSatisfied);
2538 calleeTaintsSatisfied.put(tCallee, predsIfSatis);
2545 if( writeDebugDOTs ) {
2546 writeGraph(debugGraphPrefix+"caller20BeforeWipe",
2547 resolveMethodDebugDOTwriteLabels,
2548 resolveMethodDebugDOTselectTemps,
2549 resolveMethodDebugDOTpruneGarbage,
2550 resolveMethodDebugDOThideReach,
2551 resolveMethodDebugDOThideSubsetReach,
2552 resolveMethodDebugDOThidePreds,
2553 resolveMethodDebugDOThideEdgeTaints);
2557 // 2. predicates tested, ok to wipe out caller part
2558 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2559 while( hrnItr.hasNext() ) {
2560 Integer hrnID = hrnItr.next();
2561 HeapRegionNode hrnCaller = id2hrn.get(hrnID);
2562 assert hrnCaller != null;
2564 // when clearing off nodes, also eliminate variable
2566 wipeOut(hrnCaller, true);
2569 // if we are assigning the return value to something, clobber now
2570 // as part of the wipe
2571 TempDescriptor returnTemp = fc.getReturnTemp();
2572 if( returnTemp != null &&
2573 DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2576 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2577 clearRefEdgesFrom(vnLhsCaller, null, null, true);
2583 if( writeDebugDOTs ) {
2584 writeGraph(debugGraphPrefix+"caller30BeforeAddingNodes",
2585 resolveMethodDebugDOTwriteLabels,
2586 resolveMethodDebugDOTselectTemps,
2587 resolveMethodDebugDOTpruneGarbage,
2588 resolveMethodDebugDOThideReach,
2589 resolveMethodDebugDOThideSubsetReach,
2590 resolveMethodDebugDOThidePreds,
2591 resolveMethodDebugDOThideEdgeTaints);
2597 // 3. callee elements with satisfied preds come in, note that
2598 // the mapping of elements satisfied to preds is like this:
2599 // A callee element EE has preds EEp that are satisfied by
2600 // some caller element ER. We bring EE into the caller
2601 // context as ERee with the preds of ER, namely ERp, which
2602 // in the following algorithm is the value in the mapping
2605 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2606 while( satisItr.hasNext() ) {
2607 Map.Entry me = (Map.Entry)satisItr.next();
2608 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2609 ExistPredSet preds = (ExistPredSet) me.getValue();
2611 // TODO: I think its true that the current implementation uses
2612 // the type of the OOC region and the predicates OF THE EDGE from
2613 // it to link everything up in caller context, so that's why we're
2614 // skipping this... maybe that's a sillier way to do it?
2615 if( hrnCallee.isOutOfContext() ) {
2619 AllocSite as = hrnCallee.getAllocSite();
2622 Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
2624 HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
2625 if( hrnCaller == null ) {
2627 createNewHeapRegionNode(hrnIDshadow, // id or null to generate a new one
2628 hrnCallee.isSingleObject(), // single object?
2629 hrnCallee.isNewSummary(), // summary?
2630 false, // out-of-context?
2631 hrnCallee.getType(), // type
2632 hrnCallee.getAllocSite(), // allocation site
2633 toCallerContext(hrnCallee.getInherent(),
2634 calleeNode2calleeStatesSatisfied.get(hrnCallee) ), // inherent reach
2635 null, // current reach
2636 predsEmpty, // predicates
2637 hrnCallee.getDescription() // description
2640 assert hrnCaller.isWiped();
2643 hrnCaller.setAlpha(toCallerContext(hrnCallee.getAlpha(),
2644 calleeNode2calleeStatesSatisfied.get(hrnCallee)
2648 hrnCaller.setPreds(preds);
2655 if( writeDebugDOTs ) {
2656 writeGraph(debugGraphPrefix+"caller31BeforeAddingEdges",
2657 resolveMethodDebugDOTwriteLabels,
2658 resolveMethodDebugDOTselectTemps,
2659 resolveMethodDebugDOTpruneGarbage,
2660 resolveMethodDebugDOThideReach,
2661 resolveMethodDebugDOThideSubsetReach,
2662 resolveMethodDebugDOThidePreds,
2663 resolveMethodDebugDOThideEdgeTaints);
2667 // set these up during the next procedure so after
2668 // the caller has all of its nodes and edges put
2669 // back together we can propagate the callee's
2670 // reach changes backwards into the caller graph
2671 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2673 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2674 new Hashtable<RefEdge, ChangeSet>();
2677 // 3.b) callee -> callee edges AND out-of-context -> callee
2678 // which includes return temp -> callee edges now, too
2679 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2680 while( satisItr.hasNext() ) {
2681 Map.Entry me = (Map.Entry)satisItr.next();
2682 RefEdge reCallee = (RefEdge) me.getKey();
2683 ExistPredSet preds = (ExistPredSet) me.getValue();
2685 HeapRegionNode hrnDstCallee = reCallee.getDst();
2686 AllocSite asDst = hrnDstCallee.getAllocSite();
2687 allocSites.add(asDst);
2689 Integer hrnIDDstShadow =
2690 asDst.getShadowIDfromID(hrnDstCallee.getID() );
2692 HeapRegionNode hrnDstCaller = id2hrn.get(hrnIDDstShadow);
2693 assert hrnDstCaller != null;
2696 RefSrcNode rsnCallee = reCallee.getSrc();
2698 Set<RefSrcNode> rsnCallers =
2699 new HashSet<RefSrcNode>();
2701 Set<RefSrcNode> oocCallers =
2702 calleeEdges2oocCallerSrcMatches.get(reCallee);
2704 if( rsnCallee instanceof HeapRegionNode ) {
2705 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2706 if( hrnCalleeSrc.isOutOfContext() ) {
2707 assert oocCallers != null;
2712 if( oocCallers == null ) {
2713 // there are no out-of-context matches, so it's
2714 // either a param/arg var or one in-context heap region
2715 if( rsnCallee instanceof VariableNode ) {
2716 // variable -> node in the callee should only
2717 // come into the caller if its from a param var
2718 VariableNode vnCallee = (VariableNode) rsnCallee;
2719 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2720 TempDescriptor tdArg = fc.getArgMatchingParam(fmCallee,
2722 if( tdArg == null ) {
2723 // this means the variable isn't a parameter, its local
2724 // to the callee so we ignore it in call site transfer
2725 // shouldn't this NEVER HAPPEN?
2729 rsnCallers.add(this.getVariableNodeFromTemp(tdArg) );
2732 // otherwise source is in context, one region
2734 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2736 // translate an in-context node to shadow
2737 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2738 allocSites.add(asSrc);
2740 Integer hrnIDSrcShadow =
2741 asSrc.getShadowIDfromID(hrnSrcCallee.getID() );
2743 HeapRegionNode hrnSrcCallerShadow =
2744 this.id2hrn.get(hrnIDSrcShadow);
2746 assert hrnSrcCallerShadow != null;
2748 rsnCallers.add(hrnSrcCallerShadow);
2752 // otherwise we have a set of out-of-context srcs
2753 // that should NOT be translated to shadow nodes
2754 assert !oocCallers.isEmpty();
2755 rsnCallers.addAll(oocCallers);
2758 // now make all caller edges we've identified from
2759 // this callee edge with a satisfied predicate
2760 assert !rsnCallers.isEmpty();
2761 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2762 while( rsnItr.hasNext() ) {
2763 RefSrcNode rsnCaller = rsnItr.next();
2765 RefEdge reCaller = new RefEdge(rsnCaller,
2768 reCallee.getField(),
2769 toCallerContext(reCallee.getBeta(),
2770 calleeEdge2calleeStatesSatisfied.get(reCallee) ),
2772 toCallerContext(reCallee.getTaints(),
2773 calleeEdge2calleeTaintsSatisfied.get(reCallee) )
2776 ChangeSet cs = ChangeSet.factory();
2777 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2778 while( rsItr.hasNext() ) {
2779 ReachState state = rsItr.next();
2780 ExistPredSet predsPreCallee = state.getPreds();
2782 if( state.isEmpty() ) {
2786 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2787 while( predItr.hasNext() ) {
2788 ExistPred pred = predItr.next();
2789 ReachState old = pred.ne_state;
2795 cs = Canonical.add(cs,
2796 ChangeTuple.factory(old,
2803 // we're just going to use the convenient "merge-if-exists"
2804 // edge call below, but still take a separate look if there
2805 // is an existing caller edge to build change sets properly
2806 if( !cs.isEmpty() ) {
2807 RefEdge edgeExisting = rsnCaller.getReferenceTo(hrnDstCaller,
2811 if( edgeExisting != null ) {
2812 ChangeSet csExisting = edgePlannedChanges.get(edgeExisting);
2813 if( csExisting == null ) {
2814 csExisting = ChangeSet.factory();
2816 edgePlannedChanges.put(edgeExisting,
2817 Canonical.union(csExisting,
2822 edgesForPropagation.add(reCaller);
2823 assert !edgePlannedChanges.containsKey(reCaller);
2824 edgePlannedChanges.put(reCaller, cs);
2828 // then add new caller edge or merge
2829 addEdgeOrMergeWithExisting(reCaller);
2837 if( writeDebugDOTs ) {
2838 writeGraph(debugGraphPrefix+"caller38propagateReach",
2839 resolveMethodDebugDOTwriteLabels,
2840 resolveMethodDebugDOTselectTemps,
2841 resolveMethodDebugDOTpruneGarbage,
2842 resolveMethodDebugDOThideReach,
2843 resolveMethodDebugDOThideSubsetReach,
2844 resolveMethodDebugDOThidePreds,
2845 resolveMethodDebugDOThideEdgeTaints);
2848 // propagate callee reachability changes to the rest
2849 // of the caller graph edges
2850 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2852 propagateTokensOverEdges(edgesForPropagation, // source edges
2853 edgePlannedChanges, // map src edge to change set
2854 edgesUpdated); // list of updated edges
2856 // commit beta' (beta<-betaNew)
2857 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2858 while( edgeItr.hasNext() ) {
2859 edgeItr.next().applyBetaNew();
2868 if( writeDebugDOTs ) {
2869 writeGraph(debugGraphPrefix+"caller40BeforeShadowMerge",
2870 resolveMethodDebugDOTwriteLabels,
2871 resolveMethodDebugDOTselectTemps,
2872 resolveMethodDebugDOTpruneGarbage,
2873 resolveMethodDebugDOThideReach,
2874 resolveMethodDebugDOThideSubsetReach,
2875 resolveMethodDebugDOThidePreds,
2876 resolveMethodDebugDOThideEdgeTaints);
2880 // 4) merge shadow nodes so alloc sites are back to k
2881 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2882 while( asItr.hasNext() ) {
2883 // for each allocation site do the following to merge
2884 // shadow nodes (newest from callee) with any existing
2885 // look for the newest normal and newest shadow "slot"
2886 // not being used, transfer normal to shadow. Keep
2887 // doing this until there are no more normal nodes, or
2888 // no empty shadow slots: then merge all remaining normal
2889 // nodes into the shadow summary. Finally, convert all
2890 // shadow to their normal versions.
2891 AllocSite as = asItr.next();
2895 while( ageNorm < allocationDepth &&
2896 ageShad < allocationDepth ) {
2898 // first, are there any normal nodes left?
2899 Integer idNorm = as.getIthOldest(ageNorm);
2900 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2901 if( hrnNorm == null ) {
2902 // no, this age of normal node not in the caller graph
2907 // yes, a normal node exists, is there an empty shadow
2908 // "slot" to transfer it onto?
2909 HeapRegionNode hrnShad = getIthNode(as, ageShad, true);
2910 if( !hrnShad.isWiped() ) {
2911 // no, this age of shadow node is not empty
2916 // yes, this shadow node is empty
2917 transferOnto(hrnNorm, hrnShad);
2922 // now, while there are still normal nodes but no shadow
2923 // slots, merge normal nodes into the shadow summary
2924 while( ageNorm < allocationDepth ) {
2926 // first, are there any normal nodes left?
2927 Integer idNorm = as.getIthOldest(ageNorm);
2928 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2929 if( hrnNorm == null ) {
2930 // no, this age of normal node not in the caller graph
2935 // yes, a normal node exists, so get the shadow summary
2936 HeapRegionNode summShad = getSummaryNode(as, true);
2937 mergeIntoSummary(hrnNorm, summShad);
2939 // now tokens in reachability sets need to age also
2940 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2941 while( itrAllHRNodes.hasNext() ) {
2942 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
2943 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
2945 ageTuplesFrom(as, hrnToAge);
2947 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
2948 while( itrEdges.hasNext() ) {
2949 ageTuplesFrom(as, itrEdges.next() );
2956 // if there is a normal summary, merge it into shadow summary
2957 Integer idNorm = as.getSummary();
2958 HeapRegionNode summNorm = id2hrn.get(idNorm);
2959 if( summNorm != null ) {
2960 HeapRegionNode summShad = getSummaryNode(as, true);
2961 mergeIntoSummary(summNorm, summShad);
2964 // finally, flip all existing shadow nodes onto the normal
2965 for( int i = 0; i < allocationDepth; ++i ) {
2966 Integer idShad = as.getIthOldestShadow(i);
2967 HeapRegionNode hrnShad = id2hrn.get(idShad);
2968 if( hrnShad != null ) {
2970 HeapRegionNode hrnNorm = getIthNode(as, i, false);
2971 assert hrnNorm.isWiped();
2972 transferOnto(hrnShad, hrnNorm);
2976 Integer idShad = as.getSummaryShadow();
2977 HeapRegionNode summShad = id2hrn.get(idShad);
2978 if( summShad != null ) {
2979 summNorm = getSummaryNode(as, false);
2980 transferOnto(summShad, summNorm);
2989 if( writeDebugDOTs ) {
2990 writeGraph(debugGraphPrefix+"caller45BeforeUnshadow",
2991 resolveMethodDebugDOTwriteLabels,
2992 resolveMethodDebugDOTselectTemps,
2993 resolveMethodDebugDOTpruneGarbage,
2994 resolveMethodDebugDOThideReach,
2995 resolveMethodDebugDOThideSubsetReach,
2996 resolveMethodDebugDOThidePreds,
2997 resolveMethodDebugDOThideEdgeTaints);
3001 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3002 while( itrAllHRNodes.hasNext() ) {
3003 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
3004 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3006 hrn.setAlpha(unshadow(hrn.getAlpha() ) );
3008 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
3009 while( itrEdges.hasNext() ) {
3010 RefEdge re = itrEdges.next();
3011 re.setBeta(unshadow(re.getBeta() ) );
3018 if( writeDebugDOTs ) {
3019 writeGraph(debugGraphPrefix+"caller50BeforeGlobalSweep",
3020 resolveMethodDebugDOTwriteLabels,
3021 resolveMethodDebugDOTselectTemps,
3022 resolveMethodDebugDOTpruneGarbage,
3023 resolveMethodDebugDOThideReach,
3024 resolveMethodDebugDOThideSubsetReach,
3025 resolveMethodDebugDOThidePreds,
3026 resolveMethodDebugDOThideEdgeTaints);
3031 if( !DISABLE_GLOBAL_SWEEP ) {
3036 if( writeDebugDOTs ) {
3037 writeGraph(debugGraphPrefix+"caller90AfterTransfer",
3038 resolveMethodDebugDOTwriteLabels,
3039 resolveMethodDebugDOTselectTemps,
3040 resolveMethodDebugDOTpruneGarbage,
3041 resolveMethodDebugDOThideReach,
3042 resolveMethodDebugDOThideSubsetReach,
3043 resolveMethodDebugDOThidePreds,
3044 resolveMethodDebugDOThideEdgeTaints);
3050 ////////////////////////////////////////////////////
3052 // Abstract garbage collection simply removes
3053 // heap region nodes that are not mechanically
3054 // reachable from a root set. This step is
3055 // essential for testing node and edge existence
3056 // predicates efficiently
3058 ////////////////////////////////////////////////////
3059 public void abstractGarbageCollect(Set<TempDescriptor> liveSet) {
3061 // calculate a root set, will be different for Java
3062 // version of analysis versus Bamboo version
3063 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3065 // visit every variable in graph while building root
3066 // set, and do iterating on a copy, so we can remove
3067 // dead variables while we're at this
3068 Iterator makeCopyItr = td2vn.entrySet().iterator();
3069 Set entrysCopy = new HashSet();
3070 while( makeCopyItr.hasNext() ) {
3071 entrysCopy.add(makeCopyItr.next() );
3074 Iterator eItr = entrysCopy.iterator();
3075 while( eItr.hasNext() ) {
3076 Map.Entry me = (Map.Entry)eItr.next();
3077 TempDescriptor td = (TempDescriptor) me.getKey();
3078 VariableNode vn = (VariableNode) me.getValue();
3080 if( liveSet.contains(td) ) {
3084 // dead var, remove completely from graph
3086 clearRefEdgesFrom(vn, null, null, true);
3090 // everything visited in a traversal is
3091 // considered abstractly live
3092 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3094 while( !toVisit.isEmpty() ) {
3095 RefSrcNode rsn = toVisit.iterator().next();
3096 toVisit.remove(rsn);
3099 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3100 while( hrnItr.hasNext() ) {
3101 RefEdge edge = hrnItr.next();
3102 HeapRegionNode hrn = edge.getDst();
3104 if( !visited.contains(hrn) ) {
3110 // get a copy of the set to iterate over because
3111 // we're going to monkey with the graph when we
3112 // identify a garbage node
3113 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3114 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3115 while( hrnItr.hasNext() ) {
3116 hrnAllPrior.add(hrnItr.next() );
3119 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3120 while( hrnAllItr.hasNext() ) {
3121 HeapRegionNode hrn = hrnAllItr.next();
3123 if( !visited.contains(hrn) ) {
3125 // heap region nodes are compared across ReachGraph
3126 // objects by their integer ID, so when discarding
3127 // garbage nodes we must also discard entries in
3128 // the ID -> heap region hashtable.
3129 id2hrn.remove(hrn.getID() );
3131 // RefEdge objects are two-way linked between
3132 // nodes, so when a node is identified as garbage,
3133 // actively clear references to and from it so
3134 // live nodes won't have dangling RefEdge's
3137 // if we just removed the last node from an allocation
3138 // site, it should be taken out of the ReachGraph's list
3139 AllocSite as = hrn.getAllocSite();
3140 if( !hasNodesOf(as) ) {
3141 allocSites.remove(as);
3147 protected boolean hasNodesOf(AllocSite as) {
3148 if( id2hrn.containsKey(as.getSummary() ) ) {
3152 for( int i = 0; i < allocationDepth; ++i ) {
3153 if( id2hrn.containsKey(as.getIthOldest(i) ) ) {
3161 ////////////////////////////////////////////////////
3163 // This global sweep is an optional step to prune
3164 // reachability sets that are not internally
3165 // consistent with the global graph. It should be
3166 // invoked after strong updates or method calls.
3168 ////////////////////////////////////////////////////
3169 public void globalSweep() {
3171 // boldB is part of the phase 1 sweep
3172 // it has an in-context table and an out-of-context table
3173 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3174 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3176 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3177 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3179 // visit every heap region to initialize alphaNew and betaNew,
3180 // and make a map of every hrnID to the source nodes it should
3181 // propagate forward from. In-context flagged hrnID's propagate
3182 // from only the in-context node they name, but out-of-context
3183 // ID's may propagate from several out-of-context nodes
3184 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3185 new Hashtable< Integer, Set<HeapRegionNode> >();
3187 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3188 new Hashtable< Integer, Set<HeapRegionNode> >();
3191 Iterator itrHrns = id2hrn.entrySet().iterator();
3192 while( itrHrns.hasNext() ) {
3193 Map.Entry me = (Map.Entry)itrHrns.next();
3194 Integer hrnID = (Integer) me.getKey();
3195 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3197 // assert that this node and incoming edges have clean alphaNew
3198 // and betaNew sets, respectively
3199 assert rsetEmpty.equals(hrn.getAlphaNew() );
3201 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3202 while( itrRers.hasNext() ) {
3203 RefEdge edge = itrRers.next();
3204 assert rsetEmpty.equals(edge.getBetaNew() );
3207 // make a mapping of IDs to heap regions they propagate from
3208 if( hrn.isFlagged() ) {
3209 assert !hrn.isOutOfContext();
3210 assert !icID2srcs.containsKey(hrn.getID() );
3212 // in-context flagged node IDs simply propagate from the
3214 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3216 icID2srcs.put(hrn.getID(), srcs);
3219 if( hrn.isOutOfContext() ) {
3220 assert !hrn.isFlagged();
3222 // the reachability states on an out-of-context
3223 // node are not really important (combinations of
3224 // IDs or arity)--what matters is that the states
3225 // specify which nodes this out-of-context node
3226 // stands in for. For example, if the state [17?, 19*]
3227 // appears on the ooc node, it may serve as a source
3228 // for node 17? and a source for node 19.
3229 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3230 while( stateItr.hasNext() ) {
3231 ReachState state = stateItr.next();
3233 Iterator<ReachTuple> rtItr = state.iterator();
3234 while( rtItr.hasNext() ) {
3235 ReachTuple rt = rtItr.next();
3236 assert rt.isOutOfContext();
3238 Set<HeapRegionNode> srcs = oocID2srcs.get(rt.getHrnID() );
3239 if( srcs == null ) {
3240 srcs = new HashSet<HeapRegionNode>();
3243 oocID2srcs.put(rt.getHrnID(), srcs);
3249 // calculate boldB for all hrnIDs identified by the above
3250 // node traversal, propagating from every source
3251 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3254 Set<HeapRegionNode> srcs;
3257 if( !icID2srcs.isEmpty() ) {
3258 Map.Entry me = (Map.Entry)icID2srcs.entrySet().iterator().next();
3259 hrnID = (Integer) me.getKey();
3260 srcs = (Set<HeapRegionNode>)me.getValue();
3262 icID2srcs.remove(hrnID);
3265 assert !oocID2srcs.isEmpty();
3267 Map.Entry me = (Map.Entry)oocID2srcs.entrySet().iterator().next();
3268 hrnID = (Integer) me.getKey();
3269 srcs = (Set<HeapRegionNode>)me.getValue();
3271 oocID2srcs.remove(hrnID);
3275 Hashtable<RefEdge, ReachSet> boldB_f =
3276 new Hashtable<RefEdge, ReachSet>();
3278 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3280 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3281 while( hrnItr.hasNext() ) {
3282 HeapRegionNode hrn = hrnItr.next();
3284 assert workSetEdges.isEmpty();
3286 // initial boldB_f constraints
3287 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3288 while( itrRees.hasNext() ) {
3289 RefEdge edge = itrRees.next();
3291 assert !boldB_f.containsKey(edge);
3292 boldB_f.put(edge, edge.getBeta() );
3294 assert !workSetEdges.contains(edge);
3295 workSetEdges.add(edge);
3298 // enforce the boldB_f constraint at edges until we reach a fixed point
3299 while( !workSetEdges.isEmpty() ) {
3300 RefEdge edge = workSetEdges.iterator().next();
3301 workSetEdges.remove(edge);
3303 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3304 while( itrPrime.hasNext() ) {
3305 RefEdge edgePrime = itrPrime.next();
3307 ReachSet prevResult = boldB_f.get(edgePrime);
3308 ReachSet intersection = Canonical.intersection(boldB_f.get(edge),
3312 if( prevResult == null ||
3313 Canonical.unionORpreds(prevResult,
3314 intersection).size()
3318 if( prevResult == null ) {
3319 boldB_f.put(edgePrime,
3320 Canonical.unionORpreds(edgePrime.getBeta(),
3325 boldB_f.put(edgePrime,
3326 Canonical.unionORpreds(prevResult,
3331 workSetEdges.add(edgePrime);
3338 boldBic.put(hrnID, boldB_f);
3340 boldBooc.put(hrnID, boldB_f);
3345 // use boldB to prune hrnIDs from alpha states that are impossible
3346 // and propagate the differences backwards across edges
3347 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3349 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3350 new Hashtable<RefEdge, ChangeSet>();
3353 itrHrns = id2hrn.entrySet().iterator();
3354 while( itrHrns.hasNext() ) {
3355 Map.Entry me = (Map.Entry)itrHrns.next();
3356 Integer hrnID = (Integer) me.getKey();
3357 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3359 // out-of-context nodes don't participate in the
3360 // global sweep, they serve as sources for the pass
3362 if( hrn.isOutOfContext() ) {
3366 // the inherent states of a region are the exception
3367 // to removal as the global sweep prunes
3368 ReachTuple rtException = ReachTuple.factory(hrnID,
3369 !hrn.isSingleObject(),
3370 ReachTuple.ARITY_ONE,
3371 false // out-of-context
3374 ChangeSet cts = ChangeSet.factory();
3376 // mark hrnIDs for removal
3377 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3378 while( stateItr.hasNext() ) {
3379 ReachState stateOld = stateItr.next();
3381 ReachState markedHrnIDs = ReachState.factory();
3383 Iterator<ReachTuple> rtItr = stateOld.iterator();
3384 while( rtItr.hasNext() ) {
3385 ReachTuple rtOld = rtItr.next();
3387 // never remove the inherent hrnID from a flagged region
3388 // because it is trivially satisfied
3389 if( hrn.isFlagged() ) {
3390 if( rtOld == rtException ) {
3395 // does boldB allow this hrnID?
3396 boolean foundState = false;
3397 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3398 while( incidentEdgeItr.hasNext() ) {
3399 RefEdge incidentEdge = incidentEdgeItr.next();
3401 Hashtable<RefEdge, ReachSet> B;
3402 if( rtOld.isOutOfContext() ) {
3403 B = boldBooc.get(rtOld.getHrnID() );
3406 if( !id2hrn.containsKey(rtOld.getHrnID() ) ) {
3407 // let symbols not in the graph get pruned
3411 B = boldBic.get(rtOld.getHrnID() );
3415 ReachSet boldB_rtOld_incident = B.get(incidentEdge);
3416 if( boldB_rtOld_incident != null &&
3417 boldB_rtOld_incident.containsIgnorePreds(stateOld) != null
3425 markedHrnIDs = Canonical.addUpArity(markedHrnIDs, rtOld);
3429 // if there is nothing marked, just move on
3430 if( markedHrnIDs.isEmpty() ) {
3431 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3438 // remove all marked hrnIDs and establish a change set that should
3439 // propagate backwards over edges from this node
3440 ReachState statePruned = ReachState.factory();
3441 rtItr = stateOld.iterator();
3442 while( rtItr.hasNext() ) {
3443 ReachTuple rtOld = rtItr.next();
3445 if( !markedHrnIDs.containsTuple(rtOld) ) {
3446 statePruned = Canonical.addUpArity(statePruned, rtOld);
3449 assert !stateOld.equals(statePruned);
3451 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3455 ChangeTuple ct = ChangeTuple.factory(stateOld,
3458 cts = Canonical.add(cts, ct);
3461 // throw change tuple set on all incident edges
3462 if( !cts.isEmpty() ) {
3463 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3464 while( incidentEdgeItr.hasNext() ) {
3465 RefEdge incidentEdge = incidentEdgeItr.next();
3467 edgesForPropagation.add(incidentEdge);
3469 if( edgePlannedChanges.get(incidentEdge) == null ) {
3470 edgePlannedChanges.put(incidentEdge, cts);
3472 edgePlannedChanges.put(
3474 Canonical.union(edgePlannedChanges.get(incidentEdge),
3483 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3485 propagateTokensOverEdges(edgesForPropagation,
3489 // at the end of the 1st phase reference edges have
3490 // beta, betaNew that correspond to beta and betaR
3492 // commit beta<-betaNew, so beta=betaR and betaNew
3493 // will represent the beta' calculation in 2nd phase
3495 // commit alpha<-alphaNew because it won't change
3496 HashSet<RefEdge> res = new HashSet<RefEdge>();
3498 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3499 while( nodeItr.hasNext() ) {
3500 HeapRegionNode hrn = nodeItr.next();
3502 // as mentioned above, out-of-context nodes only serve
3503 // as sources of reach states for the sweep, not part
3505 if( hrn.isOutOfContext() ) {
3506 assert hrn.getAlphaNew().equals(rsetEmpty);
3508 hrn.applyAlphaNew();
3511 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3512 while( itrRes.hasNext() ) {
3513 res.add(itrRes.next() );
3519 Iterator<RefEdge> edgeItr = res.iterator();
3520 while( edgeItr.hasNext() ) {
3521 RefEdge edge = edgeItr.next();
3522 HeapRegionNode hrn = edge.getDst();
3524 // commit results of last phase
3525 if( edgesUpdated.contains(edge) ) {
3526 edge.applyBetaNew();
3529 // compute intial condition of 2nd phase
3530 edge.setBetaNew(Canonical.intersection(edge.getBeta(),
3536 // every edge in the graph is the initial workset
3537 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3538 while( !edgeWorkSet.isEmpty() ) {
3539 RefEdge edgePrime = edgeWorkSet.iterator().next();
3540 edgeWorkSet.remove(edgePrime);
3542 RefSrcNode rsn = edgePrime.getSrc();
3543 if( !(rsn instanceof HeapRegionNode) ) {
3546 HeapRegionNode hrn = (HeapRegionNode) rsn;
3548 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3549 while( itrEdge.hasNext() ) {
3550 RefEdge edge = itrEdge.next();
3552 ReachSet prevResult = edge.getBetaNew();
3553 assert prevResult != null;
3555 ReachSet intersection =
3556 Canonical.intersection(edge.getBeta(),
3557 edgePrime.getBetaNew()
3560 if( Canonical.unionORpreds(prevResult,
3567 Canonical.unionORpreds(prevResult,
3571 edgeWorkSet.add(edge);
3576 // commit beta' (beta<-betaNew)
3577 edgeItr = res.iterator();
3578 while( edgeItr.hasNext() ) {
3579 edgeItr.next().applyBetaNew();
3584 // a useful assertion for debugging:
3585 // every in-context tuple on any edge or
3586 // any node should name a node that is
3587 // part of the graph
3588 public boolean inContextTuplesInGraph() {
3590 Iterator hrnItr = id2hrn.entrySet().iterator();
3591 while( hrnItr.hasNext() ) {
3592 Map.Entry me = (Map.Entry)hrnItr.next();
3593 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3596 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3597 while( stateItr.hasNext() ) {
3598 ReachState state = stateItr.next();
3600 Iterator<ReachTuple> rtItr = state.iterator();
3601 while( rtItr.hasNext() ) {
3602 ReachTuple rt = rtItr.next();
3604 if( !rt.isOutOfContext() ) {
3605 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3606 System.out.println(rt.getHrnID()+" is missing");
3614 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3615 while( edgeItr.hasNext() ) {
3616 RefEdge edge = edgeItr.next();
3618 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3619 while( stateItr.hasNext() ) {
3620 ReachState state = stateItr.next();
3622 Iterator<ReachTuple> rtItr = state.iterator();
3623 while( rtItr.hasNext() ) {
3624 ReachTuple rt = rtItr.next();
3626 if( !rt.isOutOfContext() ) {
3627 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3628 System.out.println(rt.getHrnID()+" is missing");
3641 // another useful assertion for debugging
3642 public boolean noEmptyReachSetsInGraph() {
3644 Iterator hrnItr = id2hrn.entrySet().iterator();
3645 while( hrnItr.hasNext() ) {
3646 Map.Entry me = (Map.Entry)hrnItr.next();
3647 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3649 if( !hrn.isOutOfContext() &&
3651 hrn.getAlpha().isEmpty()
3653 System.out.println("!!! "+hrn+" has an empty ReachSet !!!");
3657 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3658 while( edgeItr.hasNext() ) {
3659 RefEdge edge = edgeItr.next();
3661 if( edge.getBeta().isEmpty() ) {
3662 System.out.println("!!! "+edge+" has an empty ReachSet !!!");
3672 public boolean everyReachStateWTrue() {
3674 Iterator hrnItr = id2hrn.entrySet().iterator();
3675 while( hrnItr.hasNext() ) {
3676 Map.Entry me = (Map.Entry)hrnItr.next();
3677 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3680 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3681 while( stateItr.hasNext() ) {
3682 ReachState state = stateItr.next();
3684 if( !state.getPreds().equals(predsTrue) ) {
3690 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3691 while( edgeItr.hasNext() ) {
3692 RefEdge edge = edgeItr.next();
3694 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3695 while( stateItr.hasNext() ) {
3696 ReachState state = stateItr.next();
3698 if( !state.getPreds().equals(predsTrue) ) {
3711 ////////////////////////////////////////////////////
3712 // in merge() and equals() methods the suffix A
3713 // represents the passed in graph and the suffix
3714 // B refers to the graph in this object
3715 // Merging means to take the incoming graph A and
3716 // merge it into B, so after the operation graph B
3717 // is the final result.
3718 ////////////////////////////////////////////////////
3719 protected void merge(ReachGraph rg) {
3727 mergeAllocSites(rg);
3728 mergeInaccessibleVars(rg);
3731 protected void mergeNodes(ReachGraph rg) {
3733 // start with heap region nodes
3734 Set sA = rg.id2hrn.entrySet();
3735 Iterator iA = sA.iterator();
3736 while( iA.hasNext() ) {
3737 Map.Entry meA = (Map.Entry)iA.next();
3738 Integer idA = (Integer) meA.getKey();
3739 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3741 // if this graph doesn't have a node the
3742 // incoming graph has, allocate it
3743 if( !id2hrn.containsKey(idA) ) {
3744 HeapRegionNode hrnB = hrnA.copy();
3745 id2hrn.put(idA, hrnB);
3748 // otherwise this is a node present in both graphs
3749 // so make the new reachability set a union of the
3750 // nodes' reachability sets
3751 HeapRegionNode hrnB = id2hrn.get(idA);
3752 hrnB.setAlpha(Canonical.unionORpreds(hrnB.getAlpha(),
3757 hrnB.setPreds(Canonical.join(hrnB.getPreds(),
3764 if( !hrnA.equals(hrnB) ) {
3765 rg.writeGraph("graphA");
3766 this.writeGraph("graphB");
3767 throw new Error("flagged not matching");
3775 // now add any variable nodes that are in graph B but
3777 sA = rg.td2vn.entrySet();
3779 while( iA.hasNext() ) {
3780 Map.Entry meA = (Map.Entry)iA.next();
3781 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3782 VariableNode lnA = (VariableNode) meA.getValue();
3784 // if the variable doesn't exist in B, allocate and add it
3785 VariableNode lnB = getVariableNodeFromTemp(tdA);
3789 protected void mergeRefEdges(ReachGraph rg) {
3791 // between heap regions
3792 Set sA = rg.id2hrn.entrySet();
3793 Iterator iA = sA.iterator();
3794 while( iA.hasNext() ) {
3795 Map.Entry meA = (Map.Entry)iA.next();
3796 Integer idA = (Integer) meA.getKey();
3797 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3799 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3800 while( heapRegionsItrA.hasNext() ) {
3801 RefEdge edgeA = heapRegionsItrA.next();
3802 HeapRegionNode hrnChildA = edgeA.getDst();
3803 Integer idChildA = hrnChildA.getID();
3805 // at this point we know an edge in graph A exists
3806 // idA -> idChildA, does this exist in B?
3807 assert id2hrn.containsKey(idA);
3808 HeapRegionNode hrnB = id2hrn.get(idA);
3809 RefEdge edgeToMerge = null;
3811 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3812 while( heapRegionsItrB.hasNext() &&
3813 edgeToMerge == null ) {
3815 RefEdge edgeB = heapRegionsItrB.next();
3816 HeapRegionNode hrnChildB = edgeB.getDst();
3817 Integer idChildB = hrnChildB.getID();
3819 // don't use the RefEdge.equals() here because
3820 // we're talking about existence between graphs,
3821 // not intragraph equal
3822 if( idChildB.equals(idChildA) &&
3823 edgeB.typeAndFieldEquals(edgeA) ) {
3825 edgeToMerge = edgeB;
3829 // if the edge from A was not found in B,
3831 if( edgeToMerge == null ) {
3832 assert id2hrn.containsKey(idChildA);
3833 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3834 edgeToMerge = edgeA.copy();
3835 edgeToMerge.setSrc(hrnB);
3836 edgeToMerge.setDst(hrnChildB);
3837 addRefEdge(hrnB, hrnChildB, edgeToMerge);
3839 // otherwise, the edge already existed in both graphs
3840 // so merge their reachability sets
3842 // just replace this beta set with the union
3843 assert edgeToMerge != null;
3844 edgeToMerge.setBeta(
3845 Canonical.unionORpreds(edgeToMerge.getBeta(),
3849 edgeToMerge.setPreds(
3850 Canonical.join(edgeToMerge.getPreds(),
3854 edgeToMerge.setTaints(
3855 Canonical.union(edgeToMerge.getTaints(),
3863 // and then again from variable nodes
3864 sA = rg.td2vn.entrySet();
3866 while( iA.hasNext() ) {
3867 Map.Entry meA = (Map.Entry)iA.next();
3868 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3869 VariableNode vnA = (VariableNode) meA.getValue();
3871 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3872 while( heapRegionsItrA.hasNext() ) {
3873 RefEdge edgeA = heapRegionsItrA.next();
3874 HeapRegionNode hrnChildA = edgeA.getDst();
3875 Integer idChildA = hrnChildA.getID();
3877 // at this point we know an edge in graph A exists
3878 // tdA -> idChildA, does this exist in B?
3879 assert td2vn.containsKey(tdA);
3880 VariableNode vnB = td2vn.get(tdA);
3881 RefEdge edgeToMerge = null;
3883 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3884 while( heapRegionsItrB.hasNext() &&
3885 edgeToMerge == null ) {
3887 RefEdge edgeB = heapRegionsItrB.next();
3888 HeapRegionNode hrnChildB = edgeB.getDst();
3889 Integer idChildB = hrnChildB.getID();
3891 // don't use the RefEdge.equals() here because
3892 // we're talking about existence between graphs
3893 if( idChildB.equals(idChildA) &&
3894 edgeB.typeAndFieldEquals(edgeA) ) {
3896 edgeToMerge = edgeB;
3900 // if the edge from A was not found in B,
3902 if( edgeToMerge == null ) {
3903 assert id2hrn.containsKey(idChildA);
3904 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3905 edgeToMerge = edgeA.copy();
3906 edgeToMerge.setSrc(vnB);
3907 edgeToMerge.setDst(hrnChildB);
3908 addRefEdge(vnB, hrnChildB, edgeToMerge);
3910 // otherwise, the edge already existed in both graphs
3911 // so merge their reachability sets
3913 // just replace this beta set with the union
3914 edgeToMerge.setBeta(Canonical.unionORpreds(edgeToMerge.getBeta(),
3918 edgeToMerge.setPreds(Canonical.join(edgeToMerge.getPreds(),
3922 edgeToMerge.setTaints(
3923 Canonical.union(edgeToMerge.getTaints(),
3932 protected void mergeAllocSites(ReachGraph rg) {
3933 allocSites.addAll(rg.allocSites);
3936 protected void mergeInaccessibleVars(ReachGraph rg) {
3937 inaccessibleVars.addAll(rg.inaccessibleVars);
3942 static boolean dbgEquals = false;
3945 // it is necessary in the equals() member functions
3946 // to "check both ways" when comparing the data
3947 // structures of two graphs. For instance, if all
3948 // edges between heap region nodes in graph A are
3949 // present and equal in graph B it is not sufficient
3950 // to say the graphs are equal. Consider that there
3951 // may be edges in graph B that are not in graph A.
3952 // the only way to know that all edges in both graphs
3953 // are equally present is to iterate over both data
3954 // structures and compare against the other graph.
3955 public boolean equals(ReachGraph rg) {
3959 System.out.println("rg is null");
3964 if( !areHeapRegionNodesEqual(rg) ) {
3966 System.out.println("hrn not equal");
3971 if( !areVariableNodesEqual(rg) ) {
3973 System.out.println("vars not equal");
3978 if( !areRefEdgesEqual(rg) ) {
3980 System.out.println("edges not equal");
3985 if( !inaccessibleVars.equals(rg.inaccessibleVars) ) {
3989 // if everything is equal up to this point,
3990 // assert that allocSites is also equal--
3991 // this data is redundant but kept for efficiency
3992 assert allocSites.equals(rg.allocSites);
3998 protected boolean areHeapRegionNodesEqual(ReachGraph rg) {
4000 if( !areallHRNinAalsoinBandequal(this, rg) ) {
4004 if( !areallHRNinAalsoinBandequal(rg, this) ) {
4011 static protected boolean areallHRNinAalsoinBandequal(ReachGraph rgA,
4013 Set sA = rgA.id2hrn.entrySet();
4014 Iterator iA = sA.iterator();
4015 while( iA.hasNext() ) {
4016 Map.Entry meA = (Map.Entry)iA.next();
4017 Integer idA = (Integer) meA.getKey();
4018 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4020 if( !rgB.id2hrn.containsKey(idA) ) {
4024 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4025 if( !hrnA.equalsIncludingAlphaAndPreds(hrnB) ) {
4033 protected boolean areVariableNodesEqual(ReachGraph rg) {
4035 if( !areallVNinAalsoinBandequal(this, rg) ) {
4039 if( !areallVNinAalsoinBandequal(rg, this) ) {
4046 static protected boolean areallVNinAalsoinBandequal(ReachGraph rgA,
4048 Set sA = rgA.td2vn.entrySet();
4049 Iterator iA = sA.iterator();
4050 while( iA.hasNext() ) {
4051 Map.Entry meA = (Map.Entry)iA.next();
4052 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4054 if( !rgB.td2vn.containsKey(tdA) ) {
4063 protected boolean areRefEdgesEqual(ReachGraph rg) {
4064 if( !areallREinAandBequal(this, rg) ) {
4068 if( !areallREinAandBequal(rg, this) ) {
4075 static protected boolean areallREinAandBequal(ReachGraph rgA,
4078 // check all the heap region->heap region edges
4079 Set sA = rgA.id2hrn.entrySet();
4080 Iterator iA = sA.iterator();
4081 while( iA.hasNext() ) {
4082 Map.Entry meA = (Map.Entry)iA.next();
4083 Integer idA = (Integer) meA.getKey();
4084 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4086 // we should have already checked that the same
4087 // heap regions exist in both graphs
4088 assert rgB.id2hrn.containsKey(idA);
4090 if( !areallREfromAequaltoB(rgA, hrnA, rgB) ) {
4094 // then check every edge in B for presence in A, starting
4095 // from the same parent HeapRegionNode
4096 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4098 if( !areallREfromAequaltoB(rgB, hrnB, rgA) ) {
4103 // then check all the variable->heap region edges
4104 sA = rgA.td2vn.entrySet();
4106 while( iA.hasNext() ) {
4107 Map.Entry meA = (Map.Entry)iA.next();
4108 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4109 VariableNode vnA = (VariableNode) meA.getValue();
4111 // we should have already checked that the same
4112 // label nodes exist in both graphs
4113 assert rgB.td2vn.containsKey(tdA);
4115 if( !areallREfromAequaltoB(rgA, vnA, rgB) ) {
4119 // then check every edge in B for presence in A, starting
4120 // from the same parent VariableNode
4121 VariableNode vnB = rgB.td2vn.get(tdA);
4123 if( !areallREfromAequaltoB(rgB, vnB, rgA) ) {
4132 static protected boolean areallREfromAequaltoB(ReachGraph rgA,
4136 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4137 while( itrA.hasNext() ) {
4138 RefEdge edgeA = itrA.next();
4139 HeapRegionNode hrnChildA = edgeA.getDst();
4140 Integer idChildA = hrnChildA.getID();
4142 assert rgB.id2hrn.containsKey(idChildA);
4144 // at this point we know an edge in graph A exists
4145 // rnA -> idChildA, does this exact edge exist in B?
4146 boolean edgeFound = false;
4148 RefSrcNode rnB = null;
4149 if( rnA instanceof HeapRegionNode ) {
4150 HeapRegionNode hrnA = (HeapRegionNode) rnA;
4151 rnB = rgB.id2hrn.get(hrnA.getID() );
4153 VariableNode vnA = (VariableNode) rnA;
4154 rnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4157 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4158 while( itrB.hasNext() ) {
4159 RefEdge edgeB = itrB.next();
4160 HeapRegionNode hrnChildB = edgeB.getDst();
4161 Integer idChildB = hrnChildB.getID();
4163 if( idChildA.equals(idChildB) &&
4164 edgeA.typeAndFieldEquals(edgeB) ) {
4166 // there is an edge in the right place with the right field,
4167 // but do they have the same attributes?
4168 if( edgeA.getBeta().equals(edgeB.getBeta() ) &&
4169 edgeA.equalsPreds(edgeB)
4185 // can be used to assert monotonicity
4186 static public boolean isNoSmallerThan(ReachGraph rgA,
4189 //System.out.println( "*** Asking if A is no smaller than B ***" );
4192 Iterator iA = rgA.id2hrn.entrySet().iterator();
4193 while( iA.hasNext() ) {
4194 Map.Entry meA = (Map.Entry)iA.next();
4195 Integer idA = (Integer) meA.getKey();
4196 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4198 if( !rgB.id2hrn.containsKey(idA) ) {
4199 System.out.println(" regions smaller");
4203 //HeapRegionNode hrnB = rgB.id2hrn.get( idA );
4204 /* NOT EQUALS, NO SMALLER THAN!
4205 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
4206 System.out.println( " regions smaller" );
4212 // this works just fine, no smaller than
4213 if( !areallVNinAalsoinBandequal(rgA, rgB) ) {
4214 System.out.println(" vars smaller:");
4215 System.out.println(" A:"+rgA.td2vn.keySet() );
4216 System.out.println(" B:"+rgB.td2vn.keySet() );
4221 iA = rgA.id2hrn.entrySet().iterator();
4222 while( iA.hasNext() ) {
4223 Map.Entry meA = (Map.Entry)iA.next();
4224 Integer idA = (Integer) meA.getKey();
4225 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4227 Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4228 while( reItr.hasNext() ) {
4229 RefEdge edgeA = reItr.next();
4230 RefSrcNode rsnA = edgeA.getSrc();
4232 // we already checked that nodes were present
4233 HeapRegionNode hrnB = rgB.id2hrn.get(hrnA.getID() );
4234 assert hrnB != null;
4237 if( rsnA instanceof VariableNode ) {
4238 VariableNode vnA = (VariableNode) rsnA;
4239 rsnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4242 HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4243 rsnB = rgB.id2hrn.get(hrnSrcA.getID() );
4245 assert rsnB != null;
4247 RefEdge edgeB = rsnB.getReferenceTo(hrnB,
4251 if( edgeB == null ) {
4252 System.out.println(" edges smaller:");
4256 // REMEMBER, IS NO SMALLER THAN
4258 System.out.println( " edges smaller" );
4274 // this analysis no longer has the "match anything"
4275 // type which was represented by null
4276 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4277 TypeDescriptor td2) {
4281 if( td1.isNull() ) {
4284 if( td2.isNull() ) {
4287 return typeUtil.mostSpecific(td1, td2);
4290 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4292 TypeDescriptor td3) {
4294 return mostSpecificType(td1,
4295 mostSpecificType(td2, td3)
4299 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4302 TypeDescriptor td4) {
4304 return mostSpecificType(mostSpecificType(td1, td2),
4305 mostSpecificType(td3, td4)
4309 protected boolean isSuperiorType(TypeDescriptor possibleSuper,
4310 TypeDescriptor possibleChild) {
4311 assert possibleSuper != null;
4312 assert possibleChild != null;
4314 if( possibleSuper.isNull() ||
4315 possibleChild.isNull() ) {
4319 return typeUtil.isSuperorType(possibleSuper, possibleChild);
4323 protected boolean hasMatchingField(HeapRegionNode src,
4326 TypeDescriptor tdSrc = src.getType();
4327 assert tdSrc != null;
4329 if( tdSrc.isArray() ) {
4330 TypeDescriptor td = edge.getType();
4333 TypeDescriptor tdSrcDeref = tdSrc.dereference();
4334 assert tdSrcDeref != null;
4336 if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
4340 return edge.getField().equals(DisjointAnalysis.arrayElementFieldName);
4343 // if it's not a class, it doesn't have any fields to match
4344 if( !tdSrc.isClass() ) {
4348 ClassDescriptor cd = tdSrc.getClassDesc();
4349 while( cd != null ) {
4350 Iterator fieldItr = cd.getFields();
4352 while( fieldItr.hasNext() ) {
4353 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4355 if( fd.getType().equals(edge.getType() ) &&
4356 fd.getSymbol().equals(edge.getField() ) ) {
4361 cd = cd.getSuperDesc();
4364 // otherwise it is a class with fields
4365 // but we didn't find a match
4369 protected boolean hasMatchingType(RefEdge edge,
4370 HeapRegionNode dst) {
4372 // if the region has no type, matches everything
4373 TypeDescriptor tdDst = dst.getType();
4374 assert tdDst != null;
4376 // if the type is not a class or an array, don't
4377 // match because primitives are copied, no aliases
4378 ClassDescriptor cdDst = tdDst.getClassDesc();
4379 if( cdDst == null && !tdDst.isArray() ) {
4383 // if the edge type is null, it matches everything
4384 TypeDescriptor tdEdge = edge.getType();
4385 assert tdEdge != null;
4387 return typeUtil.isSuperorType(tdEdge, tdDst);
4392 // the default signature for quick-and-dirty debugging
4393 public void writeGraph(String graphName) {
4394 writeGraph(graphName,
4395 true, // write labels
4396 true, // label select
4397 true, // prune garbage
4398 false, // hide reachability
4399 true, // hide subset reachability
4400 true, // hide predicates
4401 false, // hide edge taints
4402 null // in-context boundary
4406 public void writeGraph(String graphName,
4407 boolean writeLabels,
4408 boolean labelSelect,
4409 boolean pruneGarbage,
4410 boolean hideReachability,
4411 boolean hideSubsetReachability,
4412 boolean hidePredicates,
4413 boolean hideEdgeTaints
4415 writeGraph(graphName,
4420 hideSubsetReachability,
4426 public void writeGraph(String graphName,
4427 boolean writeLabels,
4428 boolean labelSelect,
4429 boolean pruneGarbage,
4430 boolean hideReachability,
4431 boolean hideSubsetReachability,
4432 boolean hidePredicates,
4433 boolean hideEdgeTaints,
4434 Set<Integer> callerNodeIDsCopiedToCallee
4437 // remove all non-word characters from the graph name so
4438 // the filename and identifier in dot don't cause errors
4439 graphName = graphName.replaceAll("[\\W]", "");
4442 new BufferedWriter(new FileWriter(graphName+".dot") );
4444 bw.write("digraph "+graphName+" {\n");
4447 // this is an optional step to form the callee-reachable
4448 // "cut-out" into a DOT cluster for visualization
4449 if( callerNodeIDsCopiedToCallee != null ) {
4451 bw.write(" subgraph cluster0 {\n");
4452 bw.write(" color=blue;\n");
4454 Iterator i = id2hrn.entrySet().iterator();
4455 while( i.hasNext() ) {
4456 Map.Entry me = (Map.Entry)i.next();
4457 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4459 if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4462 hrn.toStringDOT(hideReachability,
4463 hideSubsetReachability,
4473 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4475 // then visit every heap region node
4476 Iterator i = id2hrn.entrySet().iterator();
4477 while( i.hasNext() ) {
4478 Map.Entry me = (Map.Entry)i.next();
4479 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4481 // only visit nodes worth writing out--for instance
4482 // not every node at an allocation is referenced
4483 // (think of it as garbage-collected), etc.
4484 if( !pruneGarbage ||
4485 hrn.isOutOfContext() ||
4486 (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4489 if( !visited.contains(hrn) ) {
4490 traverseHeapRegionNodes(hrn,
4495 hideSubsetReachability,
4498 callerNodeIDsCopiedToCallee);
4503 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4506 // then visit every label node, useful for debugging
4508 i = td2vn.entrySet().iterator();
4509 while( i.hasNext() ) {
4510 Map.Entry me = (Map.Entry)i.next();
4511 VariableNode vn = (VariableNode) me.getValue();
4514 String labelStr = vn.getTempDescriptorString();
4515 if( labelStr.startsWith("___temp") ||
4516 labelStr.startsWith("___dst") ||
4517 labelStr.startsWith("___srctmp") ||
4518 labelStr.startsWith("___neverused")
4524 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4525 while( heapRegionsItr.hasNext() ) {
4526 RefEdge edge = heapRegionsItr.next();
4527 HeapRegionNode hrn = edge.getDst();
4529 if( !visited.contains(hrn) ) {
4530 traverseHeapRegionNodes(hrn,
4535 hideSubsetReachability,
4538 callerNodeIDsCopiedToCallee);
4541 bw.write(" "+vn.toString()+
4542 " -> "+hrn.toString()+
4543 edge.toStringDOT(hideReachability,
4544 hideSubsetReachability,
4556 } catch( IOException e ) {
4557 throw new Error("Error writing out DOT graph "+graphName);
4562 traverseHeapRegionNodes(HeapRegionNode hrn,
4565 Set<HeapRegionNode> visited,
4566 boolean hideReachability,
4567 boolean hideSubsetReachability,
4568 boolean hidePredicates,
4569 boolean hideEdgeTaints,
4570 Set<Integer> callerNodeIDsCopiedToCallee
4571 ) throws java.io.IOException {
4573 if( visited.contains(hrn) ) {
4578 // if we're drawing the callee-view subgraph, only
4579 // write out the node info if it hasn't already been
4581 if( callerNodeIDsCopiedToCallee == null ||
4582 !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4586 hrn.toStringDOT(hideReachability,
4587 hideSubsetReachability,
4592 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4593 while( childRegionsItr.hasNext() ) {
4594 RefEdge edge = childRegionsItr.next();
4595 HeapRegionNode hrnChild = edge.getDst();
4597 if( callerNodeIDsCopiedToCallee != null &&
4598 (edge.getSrc() instanceof HeapRegionNode) ) {
4599 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4600 if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4601 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4603 bw.write(" "+hrn.toString()+
4604 " -> "+hrnChild.toString()+
4605 edge.toStringDOT(hideReachability,
4606 hideSubsetReachability,
4611 } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4612 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4614 bw.write(" "+hrn.toString()+
4615 " -> "+hrnChild.toString()+
4616 edge.toStringDOT(hideReachability,
4617 hideSubsetReachability,
4620 ",color=blue,style=dashed")+
4623 bw.write(" "+hrn.toString()+
4624 " -> "+hrnChild.toString()+
4625 edge.toStringDOT(hideReachability,
4626 hideSubsetReachability,
4633 bw.write(" "+hrn.toString()+
4634 " -> "+hrnChild.toString()+
4635 edge.toStringDOT(hideReachability,
4636 hideSubsetReachability,
4643 traverseHeapRegionNodes(hrnChild,
4648 hideSubsetReachability,
4651 callerNodeIDsCopiedToCallee);
4660 // return the set of heap regions from the given allocation
4661 // site, if any, that exist in this graph
4662 protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4664 Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4666 Integer idSum = as.getSummary();
4667 if( id2hrn.containsKey(idSum) ) {
4668 out.add(id2hrn.get(idSum) );
4671 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4672 Integer idI = as.getIthOldest(i);
4673 if( id2hrn.containsKey(idI) ) {
4674 out.add(id2hrn.get(idI) );
4681 // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4682 // from the given allocation site, if any, from regions for that
4683 // site that exist in this graph
4684 protected Set<ReachTuple> getAnyExisting(AllocSite as,
4685 boolean includeARITY_ZEROORMORE,
4686 boolean includeARITY_ONE) {
4688 Set<ReachTuple> out = new HashSet<ReachTuple>();
4690 Integer idSum = as.getSummary();
4691 if( id2hrn.containsKey(idSum) ) {
4693 HeapRegionNode hrn = id2hrn.get(idSum);
4694 assert !hrn.isOutOfContext();
4696 if( !includeARITY_ZEROORMORE ) {
4697 out.add(ReachTuple.factory(hrn.getID(),
4698 true, // multi-obj region
4699 ReachTuple.ARITY_ZEROORMORE,
4704 if( includeARITY_ONE ) {
4705 out.add(ReachTuple.factory(hrn.getID(),
4706 true, // multi-object region
4707 ReachTuple.ARITY_ONE,
4713 if( !includeARITY_ONE ) {
4714 // no need to do the single-object regions that
4715 // only have an ARITY ONE possible
4719 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4721 Integer idI = as.getIthOldest(i);
4722 if( id2hrn.containsKey(idI) ) {
4724 HeapRegionNode hrn = id2hrn.get(idI);
4725 assert !hrn.isOutOfContext();
4727 out.add(ReachTuple.factory(hrn.getID(),
4728 false, // multi-object region
4729 ReachTuple.ARITY_ONE,
4739 // if an object allocated at the target site may be
4740 // reachable from both an object from root1 and an
4741 // object allocated at root2, return TRUE
4742 public boolean mayBothReachTarget(AllocSite asRoot1,
4744 AllocSite asTarget) {
4746 // consider all heap regions of the target and look
4747 // for a reach state that indicates regions of root1
4748 // and root2 might be able to reach same object
4749 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4751 // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4752 Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4753 Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4755 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4756 while( hrnItr.hasNext() ) {
4757 HeapRegionNode hrn = hrnItr.next();
4759 Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4760 while( rtItr1.hasNext() ) {
4761 ReachTuple rt1 = rtItr1.next();
4763 Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4764 while( rtItr2.hasNext() ) {
4765 ReachTuple rt2 = rtItr2.next();
4767 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4777 // similar to the method above, return TRUE if ever
4778 // more than one object from the root allocation site
4779 // may reach an object from the target site
4780 public boolean mayManyReachTarget(AllocSite asRoot,
4781 AllocSite asTarget) {
4783 // consider all heap regions of the target and look
4784 // for a reach state that multiple objects of root
4785 // might be able to reach the same object
4786 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4788 // get relevant reach tuples
4789 Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true, false);
4790 Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4792 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4793 while( hrnItr.hasNext() ) {
4794 HeapRegionNode hrn = hrnItr.next();
4796 // if any ZERORMORE tuples are here, TRUE
4797 Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4798 while( rtItr.hasNext() ) {
4799 ReachTuple rtZOM = rtItr.next();
4801 if( hrn.getAlpha().containsTuple(rtZOM) ) {
4806 // otherwise, look for any pair of ONE tuples
4807 Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4808 while( rtItr1.hasNext() ) {
4809 ReachTuple rt1 = rtItr1.next();
4811 Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4812 while( rtItr2.hasNext() ) {
4813 ReachTuple rt2 = rtItr2.next();
4819 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4833 public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4835 Set<HeapRegionNode> exhibitProofState =
4836 new HashSet<HeapRegionNode>();
4838 Iterator hrnItr = id2hrn.entrySet().iterator();
4839 while( hrnItr.hasNext() ) {
4840 Map.Entry me = (Map.Entry)hrnItr.next();
4841 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4843 ReachSet intersection =
4844 Canonical.intersection(proofOfSharing,
4847 if( !intersection.isEmpty() ) {
4848 assert !hrn.isOutOfContext();
4849 exhibitProofState.add(hrn);
4853 return exhibitProofState;
4857 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4858 HeapRegionNode hrn2) {
4859 assert hrn1 != null;
4860 assert hrn2 != null;
4862 assert !hrn1.isOutOfContext();
4863 assert !hrn2.isOutOfContext();
4865 assert belongsToThis(hrn1);
4866 assert belongsToThis(hrn2);
4868 assert !hrn1.getID().equals(hrn2.getID() );
4871 // then get the various tokens for these heap regions
4873 ReachTuple.factory(hrn1.getID(),
4874 !hrn1.isSingleObject(), // multi?
4875 ReachTuple.ARITY_ONE,
4878 ReachTuple h1star = null;
4879 if( !hrn1.isSingleObject() ) {
4881 ReachTuple.factory(hrn1.getID(),
4882 !hrn1.isSingleObject(),
4883 ReachTuple.ARITY_ZEROORMORE,
4888 ReachTuple.factory(hrn2.getID(),
4889 !hrn2.isSingleObject(),
4890 ReachTuple.ARITY_ONE,
4893 ReachTuple h2star = null;
4894 if( !hrn2.isSingleObject() ) {
4896 ReachTuple.factory(hrn2.getID(),
4897 !hrn2.isSingleObject(),
4898 ReachTuple.ARITY_ZEROORMORE,
4902 // then get the merged beta of all out-going edges from these heap
4905 ReachSet beta1 = ReachSet.factory();
4906 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4907 while (itrEdge.hasNext()) {
4908 RefEdge edge = itrEdge.next();
4909 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4912 ReachSet beta2 = ReachSet.factory();
4913 itrEdge = hrn2.iteratorToReferencees();
4914 while (itrEdge.hasNext()) {
4915 RefEdge edge = itrEdge.next();
4916 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4919 ReachSet proofOfSharing = ReachSet.factory();
4922 Canonical.unionORpreds(proofOfSharing,
4923 beta1.getStatesWithBoth(h1, h2)
4926 Canonical.unionORpreds(proofOfSharing,
4927 beta2.getStatesWithBoth(h1, h2)
4930 if( !hrn1.isSingleObject() ) {
4932 Canonical.unionORpreds(proofOfSharing,
4933 beta1.getStatesWithBoth(h1star, h2)
4936 Canonical.unionORpreds(proofOfSharing,
4937 beta2.getStatesWithBoth(h1star, h2)
4941 if( !hrn2.isSingleObject() ) {
4943 Canonical.unionORpreds(proofOfSharing,
4944 beta1.getStatesWithBoth(h1, h2star)
4947 Canonical.unionORpreds(proofOfSharing,
4948 beta2.getStatesWithBoth(h1, h2star)
4952 if( !hrn1.isSingleObject() &&
4953 !hrn2.isSingleObject()
4956 Canonical.unionORpreds(proofOfSharing,
4957 beta1.getStatesWithBoth(h1star, h2star)
4960 Canonical.unionORpreds(proofOfSharing,
4961 beta2.getStatesWithBoth(h1star, h2star)
4965 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4966 if( !proofOfSharing.isEmpty() ) {
4967 common = findCommonReachableNodes(proofOfSharing);
4968 if( !DISABLE_STRONG_UPDATES &&
4969 !DISABLE_GLOBAL_SWEEP
4971 assert !common.isEmpty();
4978 // this version of the above method checks whether there is sharing
4979 // among the objects in a summary node
4980 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4982 assert hrn.isNewSummary();
4983 assert !hrn.isOutOfContext();
4984 assert belongsToThis(hrn);
4987 ReachTuple.factory(hrn.getID(),
4989 ReachTuple.ARITY_ZEROORMORE,
4992 // then get the merged beta of all out-going edges from
4995 ReachSet beta = ReachSet.factory();
4996 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4997 while (itrEdge.hasNext()) {
4998 RefEdge edge = itrEdge.next();
4999 beta = Canonical.unionORpreds(beta, edge.getBeta());
5002 ReachSet proofOfSharing = ReachSet.factory();
5005 Canonical.unionORpreds(proofOfSharing,
5006 beta.getStatesWithBoth(hstar, hstar)
5009 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5010 if( !proofOfSharing.isEmpty() ) {
5011 common = findCommonReachableNodes(proofOfSharing);
5012 if( !DISABLE_STRONG_UPDATES &&
5013 !DISABLE_GLOBAL_SWEEP
5015 assert !common.isEmpty();
5023 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5024 Integer paramIndex1,
5025 Integer paramIndex2) {
5027 // get parameter's heap regions
5028 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5029 assert this.hasVariable(paramTemp1);
5030 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5033 if( !(paramVar1.getNumReferencees() == 1) ) {
5034 System.out.println("\n fm="+fm+"\n param="+paramTemp1);
5035 writeGraph("whatup");
5039 assert paramVar1.getNumReferencees() == 1;
5040 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5041 HeapRegionNode hrnParam1 = paramEdge1.getDst();
5043 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5044 assert this.hasVariable(paramTemp2);
5045 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5047 if( !(paramVar2.getNumReferencees() == 1) ) {
5048 System.out.println("\n fm="+fm+"\n param="+paramTemp2);
5049 writeGraph("whatup");
5052 assert paramVar2.getNumReferencees() == 1;
5053 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5054 HeapRegionNode hrnParam2 = paramEdge2.getDst();
5056 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5057 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5062 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5066 // get parameter's heap regions
5067 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5068 assert this.hasVariable(paramTemp);
5069 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5070 assert paramVar.getNumReferencees() == 1;
5071 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5072 HeapRegionNode hrnParam = paramEdge.getDst();
5075 HeapRegionNode hrnSummary=null;
5076 if(id2hrn.containsKey(as.getSummary())) {
5077 // if summary node doesn't exist, ignore this case
5078 hrnSummary = id2hrn.get(as.getSummary());
5079 assert hrnSummary != null;
5082 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5083 if(hrnSummary!=null) {
5084 common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5087 // check for other nodes
5088 for (int i = 0; i < as.getAllocationDepth(); ++i) {
5090 assert id2hrn.containsKey(as.getIthOldest(i));
5091 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5092 assert hrnIthOldest != null;
5094 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5101 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5104 // get summary node 1's alpha
5105 Integer idSum1 = as1.getSummary();
5106 HeapRegionNode hrnSum1=null;
5107 if(id2hrn.containsKey(idSum1)) {
5108 hrnSum1 = id2hrn.get(idSum1);
5111 // get summary node 2's alpha
5112 Integer idSum2 = as2.getSummary();
5113 HeapRegionNode hrnSum2=null;
5114 if(id2hrn.containsKey(idSum2)) {
5115 hrnSum2 = id2hrn.get(idSum2);
5118 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5119 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5120 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5124 // ask if objects from this summary share among each other
5125 common.addAll(mayReachSharedObjects(hrnSum1));
5128 // check sum2 against alloc1 nodes
5130 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5131 Integer idI1 = as1.getIthOldest(i);
5132 assert id2hrn.containsKey(idI1);
5133 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5134 assert hrnI1 != null;
5135 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5138 // also ask if objects from this summary share among each other
5139 common.addAll(mayReachSharedObjects(hrnSum2));
5142 // check sum1 against alloc2 nodes
5143 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5144 Integer idI2 = as2.getIthOldest(i);
5145 assert id2hrn.containsKey(idI2);
5146 HeapRegionNode hrnI2 = id2hrn.get(idI2);
5147 assert hrnI2 != null;
5150 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5153 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5154 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5155 Integer idI1 = as1.getIthOldest(j);
5157 // if these are the same site, don't look for the same token, no
5159 // different tokens of the same site could alias together though
5160 if (idI1.equals(idI2)) {
5164 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5166 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5173 public void makeInaccessible(Set<TempDescriptor> vars) {
5174 inaccessibleVars.addAll(vars);
5177 public void makeInaccessible(TempDescriptor td) {
5178 inaccessibleVars.add(td);
5181 public void makeAccessible(TempDescriptor td) {
5182 inaccessibleVars.remove(td);
5185 public boolean isAccessible(TempDescriptor td) {
5186 return !inaccessibleVars.contains(td);
5189 public Set<TempDescriptor> getInaccessibleVars() {
5190 return inaccessibleVars;
5196 public Set<Alloc> canPointTo( TempDescriptor x ) {
5198 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5199 // if we don't care to track it, return null which means
5200 // "a client of this result shouldn't care either"
5201 return HeapAnalysis.DONTCARE_PTR;
5204 Set<Alloc> out = new HashSet<Alloc>();
5206 VariableNode vn = getVariableNodeNoMutation( x );
5208 // the empty set means "can't point to anything"
5212 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5213 while( edgeItr.hasNext() ) {
5214 HeapRegionNode hrn = edgeItr.next().getDst();
5215 out.add( hrn.getAllocSite() );
5223 public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5225 TypeDescriptor fieldType ) {
5227 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5228 // if we don't care to track it, return null which means
5229 // "a client of this result shouldn't care either"
5230 return HeapAnalysis.DONTCARE_DREF;
5233 Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5235 VariableNode vn = getVariableNodeNoMutation( x );
5237 // the empty table means "x can't point to anything"
5241 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5242 while( edgeItr.hasNext() ) {
5243 HeapRegionNode hrn = edgeItr.next().getDst();
5244 Alloc key = hrn.getAllocSite();
5246 if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5247 // if we don't care to track it, put no entry which means
5248 // "a client of this result shouldn't care either"
5249 out.put( key, HeapAnalysis.DONTCARE_PTR );
5253 Set<Alloc> moreValues = new HashSet<Alloc>();
5254 Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5255 while( edgeItr2.hasNext() ) {
5256 RefEdge edge = edgeItr2.next();
5258 if( field.equals( edge.getField() ) ) {
5259 moreValues.add( edge.getDst().getAllocSite() );
5263 if( out.containsKey( key ) ) {
5264 out.get( key ).addAll( moreValues );
5266 out.put( key, moreValues );
5276 public TempDescriptor findVariableByName( String name ) {
5278 for( TempDescriptor td: td2vn.keySet() ) {
5279 if( td.getSymbol().contains( name ) ) {