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 temps
16 protected static TempDescriptor tdReturn;
17 protected static TempDescriptor tdStrLiteralBytes;
19 public static void initOutOfScopeTemps() {
20 tdReturn = new TempDescriptor("_Return___");
23 new TempDescriptor("_strLiteralBytes___",
24 new TypeDescriptor(TypeDescriptor.CHAR).makeArray( state )
28 // predicate constants
29 public static final ExistPred predTrue = ExistPred.factory(); // if no args, true
30 public static final ExistPredSet predsEmpty = ExistPredSet.factory();
31 public static final ExistPredSet predsTrue = ExistPredSet.factory(predTrue);
33 // some frequently used reachability constants
34 protected static final ReachState rstateEmpty = ReachState.factory();
35 protected static final ReachSet rsetEmpty = ReachSet.factory();
36 protected static final ReachSet rsetWithEmptyState = Canonical.changePredsTo(ReachSet.factory(rstateEmpty),
39 // from DisjointAnalysis for convenience
40 protected static int allocationDepth = -1;
41 protected static TypeUtil typeUtil = null;
42 protected static State state = null;
45 // variable and heap region nodes indexed by unique ID
46 public Hashtable<Integer, HeapRegionNode> id2hrn;
47 public Hashtable<TempDescriptor, VariableNode > td2vn;
49 // convenient set of alloc sites for all heap regions
50 // present in the graph without having to search
51 public Set<AllocSite> allocSites;
53 // set of inaccessible variables for current program statement
54 // with respect to stall-site analysis
55 public Set<TempDescriptor> inaccessibleVars;
59 id2hrn = new Hashtable<Integer, HeapRegionNode>();
60 td2vn = new Hashtable<TempDescriptor, VariableNode >();
61 allocSites = new HashSet<AllocSite>();
62 inaccessibleVars = new HashSet<TempDescriptor>();
66 // temp descriptors are globally unique and map to
67 // exactly one variable node, easy
68 protected VariableNode getVariableNodeFromTemp(TempDescriptor td) {
71 if( !td2vn.containsKey(td) ) {
72 td2vn.put(td, new VariableNode(td) );
78 //This method is created for client modules to access the Reachgraph
79 //after the analysis is done and no modifications are to be made.
80 public VariableNode getVariableNodeNoMutation(TempDescriptor td) {
83 if( !td2vn.containsKey(td) ) {
90 public boolean hasVariable(TempDescriptor td) {
91 return td2vn.containsKey(td);
95 // this suite of methods can be used to assert a
96 // very important property of ReachGraph objects:
97 // some element, HeapRegionNode, RefEdge etc.
98 // should be referenced by at most ONE ReachGraph!!
99 // If a heap region or edge or variable should be
100 // in another graph, make a new object with
101 // equivalent properties for a new graph
102 public boolean belongsToThis(RefSrcNode rsn) {
103 if( rsn instanceof VariableNode ) {
104 VariableNode vn = (VariableNode) rsn;
105 return this.td2vn.get(vn.getTempDescriptor() ) == vn;
107 HeapRegionNode hrn = (HeapRegionNode) rsn;
108 return this.id2hrn.get(hrn.getID() ) == hrn;
115 // the reason for this method is to have the option
116 // of creating new heap regions with specific IDs, or
117 // duplicating heap regions with specific IDs (especially
118 // in the merge() operation) or to create new heap
119 // regions with a new unique ID
120 protected HeapRegionNode
121 createNewHeapRegionNode(Integer id,
122 boolean isSingleObject,
123 boolean isNewSummary,
124 boolean isOutOfContext,
133 TypeDescriptor typeToUse = null;
134 if( allocSite != null ) {
135 typeToUse = allocSite.getType();
136 allocSites.add(allocSite);
141 boolean markForAnalysis = false;
142 if( allocSite != null && allocSite.isFlagged() ) {
143 markForAnalysis = true;
146 if( allocSite == null ) {
147 assert !markForAnalysis;
149 } else if( markForAnalysis != allocSite.isFlagged() ) {
155 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
158 if( inherent == null ) {
159 if( markForAnalysis ) {
161 Canonical.changePredsTo(
164 ReachTuple.factory(id,
166 ReachTuple.ARITY_ONE,
167 false // out-of-context
174 inherent = rsetWithEmptyState;
178 if( alpha == null ) {
182 assert preds != null;
184 HeapRegionNode hrn = new HeapRegionNode(id,
201 ////////////////////////////////////////////////
203 // Low-level referencee and referencer methods
205 // These methods provide the lowest level for
206 // creating references between reachability nodes
207 // and handling the details of maintaining both
208 // list of referencers and referencees.
210 ////////////////////////////////////////////////
211 protected void addRefEdge(RefSrcNode referencer,
212 HeapRegionNode referencee,
214 assert referencer != null;
215 assert referencee != null;
217 assert edge.getSrc() == referencer;
218 assert edge.getDst() == referencee;
219 assert belongsToThis(referencer);
220 assert belongsToThis(referencee);
222 // edges are getting added twice to graphs now, the
223 // kind that should have abstract facts merged--use
224 // this check to prevent that
225 assert referencer.getReferenceTo(referencee,
230 referencer.addReferencee(edge);
231 referencee.addReferencer(edge);
234 protected void removeRefEdge(RefEdge e) {
235 removeRefEdge(e.getSrc(),
241 protected void removeRefEdge(RefSrcNode referencer,
242 HeapRegionNode referencee,
245 assert referencer != null;
246 assert referencee != null;
248 RefEdge edge = referencer.getReferenceTo(referencee,
252 assert edge == referencee.getReferenceFrom(referencer,
256 referencer.removeReferencee(edge);
257 referencee.removeReferencer(edge);
260 // return whether at least one edge was removed
261 protected boolean clearRefEdgesFrom(RefSrcNode referencer,
265 assert referencer != null;
267 boolean atLeastOneEdgeRemoved = false;
269 // get a copy of the set to iterate over, otherwise
270 // we will be trying to take apart the set as we
271 // are iterating over it, which won't work
272 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
273 while( i.hasNext() ) {
274 RefEdge edge = i.next();
277 (edge.typeEquals(type) && edge.fieldEquals(field))
280 HeapRegionNode referencee = edge.getDst();
282 removeRefEdge(referencer,
287 atLeastOneEdgeRemoved = true;
291 return atLeastOneEdgeRemoved;
294 protected void clearRefEdgesTo(HeapRegionNode referencee,
298 assert referencee != null;
300 // get a copy of the set to iterate over, otherwise
301 // we will be trying to take apart the set as we
302 // are iterating over it, which won't work
303 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
304 while( i.hasNext() ) {
305 RefEdge edge = i.next();
308 (edge.typeEquals(type) && edge.fieldEquals(field))
311 RefSrcNode referencer = edge.getSrc();
313 removeRefEdge(referencer,
321 protected void clearNonVarRefEdgesTo(HeapRegionNode referencee) {
322 assert referencee != null;
324 // get a copy of the set to iterate over, otherwise
325 // we will be trying to take apart the set as we
326 // are iterating over it, which won't work
327 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
328 while( i.hasNext() ) {
329 RefEdge edge = i.next();
330 RefSrcNode referencer = edge.getSrc();
331 if( !(referencer instanceof VariableNode) ) {
332 removeRefEdge(referencer,
340 // this is a common operation in many transfer functions: we want
341 // to add an edge, but if there is already such an edge we should
342 // merge the properties of the existing and the new edges
343 protected void addEdgeOrMergeWithExisting(RefEdge edgeNew) {
345 RefSrcNode src = edgeNew.getSrc();
346 assert belongsToThis(src);
348 HeapRegionNode dst = edgeNew.getDst();
349 assert belongsToThis(dst);
351 // look to see if an edge with same field exists
352 // and merge with it, otherwise just add the edge
353 RefEdge edgeExisting = src.getReferenceTo(dst,
358 if( edgeExisting != null ) {
359 edgeExisting.setBeta(
360 Canonical.unionORpreds(edgeExisting.getBeta(),
364 edgeExisting.setPreds(
365 Canonical.join(edgeExisting.getPreds(),
369 edgeExisting.setTaints(
370 Canonical.unionORpreds(edgeExisting.getTaints(),
376 addRefEdge(src, dst, edgeNew);
382 ////////////////////////////////////////////////////
384 // Assignment Operation Methods
386 // These methods are high-level operations for
387 // modeling program assignment statements using
388 // the low-level reference create/remove methods
391 ////////////////////////////////////////////////////
393 public void assignTempEqualToStringLiteral(TempDescriptor x,
394 AllocSite asStringLiteral,
395 AllocSite asStringLiteralBytes,
396 FieldDescriptor fdStringBytesField) {
397 // model this to get points-to information right for
398 // pointers to string literals, even though it doesn't affect
399 // reachability paths in the heap
400 assignTempEqualToNewAlloc( x,
403 assignTempEqualToNewAlloc( tdStrLiteralBytes,
404 asStringLiteralBytes );
406 assignTempXFieldFEqualToTempY( x,
413 public void assignTempXEqualToTempY(TempDescriptor x,
415 assignTempXEqualToCastedTempY(x, y, null);
419 public void assignTempXEqualToCastedTempY(TempDescriptor x,
421 TypeDescriptor tdCast) {
423 VariableNode lnX = getVariableNodeFromTemp(x);
424 VariableNode lnY = getVariableNodeFromTemp(y);
426 clearRefEdgesFrom(lnX, null, null, true);
428 // note it is possible that the types of temps in the
429 // flat node to analyze will reveal that some typed
430 // edges in the reachability graph are impossible
431 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
433 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
434 while( itrYhrn.hasNext() ) {
435 RefEdge edgeY = itrYhrn.next();
436 HeapRegionNode referencee = edgeY.getDst();
437 RefEdge edgeNew = edgeY.copy();
439 if( !isSuperiorType(x.getType(), edgeY.getType() ) ) {
440 impossibleEdges.add(edgeY);
446 if( tdCast == null ) {
447 edgeNew.setType(mostSpecificType(y.getType(),
453 edgeNew.setType(mostSpecificType(y.getType(),
455 referencee.getType(),
461 edgeNew.setField(null);
463 addRefEdge(lnX, referencee, edgeNew);
466 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
467 while( itrImp.hasNext() ) {
468 RefEdge edgeImp = itrImp.next();
469 removeRefEdge(edgeImp);
474 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
477 FlatNode currentProgramPoint
480 VariableNode lnX = getVariableNodeFromTemp(x);
481 VariableNode lnY = getVariableNodeFromTemp(y);
483 clearRefEdgesFrom(lnX, null, null, true);
485 // note it is possible that the types of temps in the
486 // flat node to analyze will reveal that some typed
487 // edges in the reachability graph are impossible
488 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
490 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
491 while( itrYhrn.hasNext() ) {
492 RefEdge edgeY = itrYhrn.next();
493 HeapRegionNode hrnY = edgeY.getDst();
494 ReachSet betaY = edgeY.getBeta();
496 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
498 while( itrHrnFhrn.hasNext() ) {
499 RefEdge edgeHrn = itrHrnFhrn.next();
500 HeapRegionNode hrnHrn = edgeHrn.getDst();
501 ReachSet betaHrn = edgeHrn.getBeta();
503 // prune edges that are not a matching field
504 if( edgeHrn.getType() != null &&
505 !edgeHrn.getField().equals(f.getSymbol() )
510 // check for impossible edges
511 if( !isSuperiorType(x.getType(), edgeHrn.getType() ) ) {
512 impossibleEdges.add(edgeHrn);
516 TypeDescriptor tdNewEdge =
517 mostSpecificType(edgeHrn.getType(),
521 TaintSet taints = Canonical.unionORpreds(edgeHrn.getTaints(),
525 // the DFJ way to generate taints changes for field statements
526 taints = Canonical.changeWhereDefined(taints,
527 currentProgramPoint);
530 RefEdge edgeNew = new RefEdge(lnX,
534 Canonical.intersection(betaY, betaHrn),
539 addEdgeOrMergeWithExisting(edgeNew);
543 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
544 while( itrImp.hasNext() ) {
545 RefEdge edgeImp = itrImp.next();
546 removeRefEdge(edgeImp);
549 // anytime you might remove edges between heap regions
550 // you must global sweep to clean up broken reachability
551 if( !impossibleEdges.isEmpty() ) {
552 if( !DISABLE_GLOBAL_SWEEP ) {
560 // return whether a strong update was actually effected
561 public boolean assignTempXFieldFEqualToTempY(TempDescriptor x,
564 FlatNode currentProgramPoint
567 VariableNode lnX = getVariableNodeFromTemp(x);
568 VariableNode lnY = getVariableNodeFromTemp(y);
570 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
571 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
573 // note it is possible that the types of temps in the
574 // flat node to analyze will reveal that some typed
575 // edges in the reachability graph are impossible
576 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
578 // first look for possible strong updates and remove those edges
579 boolean strongUpdateCond = false;
580 boolean edgeRemovedByStrongUpdate = false;
582 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
583 while( itrXhrn.hasNext() ) {
584 RefEdge edgeX = itrXhrn.next();
585 HeapRegionNode hrnX = edgeX.getDst();
587 // we can do a strong update here if one of two cases holds
589 f != DisjointAnalysis.getArrayField(f.getType() ) &&
590 ( (hrnX.getNumReferencers() == 1) || // case 1
591 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
594 if( !DISABLE_STRONG_UPDATES ) {
595 strongUpdateCond = true;
598 clearRefEdgesFrom(hrnX,
603 edgeRemovedByStrongUpdate = true;
609 // then do all token propagation
610 itrXhrn = lnX.iteratorToReferencees();
611 while( itrXhrn.hasNext() ) {
612 RefEdge edgeX = itrXhrn.next();
613 HeapRegionNode hrnX = edgeX.getDst();
614 ReachSet betaX = edgeX.getBeta();
615 ReachSet R = Canonical.intersection(hrnX.getAlpha(),
619 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
620 while( itrYhrn.hasNext() ) {
621 RefEdge edgeY = itrYhrn.next();
622 HeapRegionNode hrnY = edgeY.getDst();
623 ReachSet O = edgeY.getBeta();
625 // check for impossible edges
626 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
627 impossibleEdges.add(edgeY);
631 // propagate tokens over nodes starting from hrnSrc, and it will
632 // take care of propagating back up edges from any touched nodes
633 ChangeSet Cy = Canonical.unionUpArityToChangeSet(O, R);
634 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
636 // then propagate back just up the edges from hrn
637 ChangeSet Cx = Canonical.unionUpArityToChangeSet(R, O);
638 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
640 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
641 new Hashtable<RefEdge, ChangeSet>();
643 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
644 while( referItr.hasNext() ) {
645 RefEdge edgeUpstream = referItr.next();
646 todoEdges.add(edgeUpstream);
647 edgePlannedChanges.put(edgeUpstream, Cx);
650 propagateTokensOverEdges(todoEdges,
657 // apply the updates to reachability
658 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
659 while( nodeItr.hasNext() ) {
660 nodeItr.next().applyAlphaNew();
663 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
664 while( edgeItr.hasNext() ) {
665 edgeItr.next().applyBetaNew();
669 // then go back through and add the new edges
670 itrXhrn = lnX.iteratorToReferencees();
671 while( itrXhrn.hasNext() ) {
672 RefEdge edgeX = itrXhrn.next();
673 HeapRegionNode hrnX = edgeX.getDst();
675 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
676 while( itrYhrn.hasNext() ) {
677 RefEdge edgeY = itrYhrn.next();
678 HeapRegionNode hrnY = edgeY.getDst();
680 // skip impossible edges here, we already marked them
681 // when computing reachability propagations above
682 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
686 // prepare the new reference edge hrnX.f -> hrnY
687 TypeDescriptor tdNewEdge =
688 mostSpecificType(y.getType(),
693 TaintSet taints = edgeY.getTaints();
696 // the DFJ way to generate taints changes for field statements
697 taints = Canonical.changeWhereDefined(taints,
698 currentProgramPoint);
706 Canonical.changePredsTo(
707 Canonical.pruneBy(edgeY.getBeta(),
716 addEdgeOrMergeWithExisting(edgeNew);
720 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
721 while( itrImp.hasNext() ) {
722 RefEdge edgeImp = itrImp.next();
723 removeRefEdge(edgeImp);
726 // if there was a strong update, make sure to improve
727 // reachability with a global sweep
728 if( edgeRemovedByStrongUpdate || !impossibleEdges.isEmpty() ) {
729 if( !DISABLE_GLOBAL_SWEEP ) {
734 return edgeRemovedByStrongUpdate;
738 public void assignReturnEqualToTemp(TempDescriptor x) {
740 VariableNode lnR = getVariableNodeFromTemp(tdReturn);
741 VariableNode lnX = getVariableNodeFromTemp(x);
743 clearRefEdgesFrom(lnR, null, null, true);
745 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
746 while( itrXhrn.hasNext() ) {
747 RefEdge edgeX = itrXhrn.next();
748 HeapRegionNode referencee = edgeX.getDst();
749 RefEdge edgeNew = edgeX.copy();
751 edgeNew.setTaints(Canonical.changePredsTo(edgeNew.getTaints(),
756 addRefEdge(lnR, referencee, edgeNew);
761 public void assignTempEqualToNewAlloc(TempDescriptor x,
768 // after the age operation the newest (or zero-ith oldest)
769 // node associated with the allocation site should have
770 // no references to it as if it were a newly allocated
772 Integer idNewest = as.getIthOldest(0);
773 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
774 assert hrnNewest != null;
776 VariableNode lnX = getVariableNodeFromTemp(x);
777 clearRefEdgesFrom(lnX, null, null, true);
779 // make a new reference to allocated node
780 TypeDescriptor type = as.getType();
783 new RefEdge(lnX, // source
787 hrnNewest.getAlpha(), // beta
788 predsTrue, // predicates
789 TaintSet.factory() // taints
792 addRefEdge(lnX, hrnNewest, edgeNew);
796 // use the allocation site (unique to entire analysis) to
797 // locate the heap region nodes in this reachability graph
798 // that should be aged. The process models the allocation
799 // of new objects and collects all the oldest allocations
800 // in a summary node to allow for a finite analysis
802 // There is an additional property of this method. After
803 // running it on a particular reachability graph (many graphs
804 // may have heap regions related to the same allocation site)
805 // the heap region node objects in this reachability graph will be
806 // allocated. Therefore, after aging a graph for an allocation
807 // site, attempts to retrieve the heap region nodes using the
808 // integer id's contained in the allocation site should always
809 // return non-null heap regions.
810 public void age(AllocSite as) {
812 // keep track of allocation sites that are represented
813 // in this graph for efficiency with other operations
816 // if there is a k-th oldest node, it merges into
818 Integer idK = as.getOldest();
819 if( id2hrn.containsKey(idK) ) {
820 HeapRegionNode hrnK = id2hrn.get(idK);
822 // retrieve the summary node, or make it
824 HeapRegionNode hrnSummary = getSummaryNode(as, false);
826 mergeIntoSummary(hrnK, hrnSummary);
829 // move down the line of heap region nodes
830 // clobbering the ith and transferring all references
831 // to and from i-1 to node i.
832 for( int i = allocationDepth - 1; i > 0; --i ) {
834 // only do the transfer if the i-1 node exists
835 Integer idImin1th = as.getIthOldest(i - 1);
836 if( id2hrn.containsKey(idImin1th) ) {
837 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
838 if( hrnImin1.isWiped() ) {
839 // there is no info on this node, just skip
843 // either retrieve or make target of transfer
844 HeapRegionNode hrnI = getIthNode(as, i, false);
846 transferOnto(hrnImin1, hrnI);
851 // as stated above, the newest node should have had its
852 // references moved over to the second oldest, so we wipe newest
853 // in preparation for being the new object to assign something to
854 HeapRegionNode hrn0 = getIthNode(as, 0, false);
857 // now tokens in reachability sets need to "age" also
858 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
859 while( itrAllHRNodes.hasNext() ) {
860 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
861 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
863 ageTuplesFrom(as, hrnToAge);
865 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
866 while( itrEdges.hasNext() ) {
867 ageTuplesFrom(as, itrEdges.next() );
872 // after tokens have been aged, reset newest node's reachability
873 // and a brand new node has a "true" predicate
874 hrn0.setAlpha(hrn0.getInherent() );
875 hrn0.setPreds(predsTrue);
879 // either retrieve or create the needed heap region node
880 protected HeapRegionNode getSummaryNode(AllocSite as,
885 idSummary = as.getSummaryShadow();
887 idSummary = as.getSummary();
890 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
892 if( hrnSummary == null ) {
894 String strDesc = as.toStringForDOT()+"\\nsummary";
897 createNewHeapRegionNode(idSummary, // id or null to generate a new one
898 false, // single object?
900 false, // out-of-context?
901 as.getType(), // type
902 as, // allocation site
903 null, // inherent reach
904 null, // current reach
905 predsEmpty, // predicates
906 strDesc // description
913 // either retrieve or create the needed heap region node
914 protected HeapRegionNode getIthNode(AllocSite as,
920 idIth = as.getIthOldestShadow(i);
922 idIth = as.getIthOldest(i);
925 HeapRegionNode hrnIth = id2hrn.get(idIth);
927 if( hrnIth == null ) {
929 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
931 hrnIth = createNewHeapRegionNode(idIth, // id or null to generate a new one
932 true, // single object?
934 false, // out-of-context?
935 as.getType(), // type
936 as, // allocation site
937 null, // inherent reach
938 null, // current reach
939 predsEmpty, // predicates
940 strDesc // description
948 protected void mergeIntoSummary(HeapRegionNode hrn,
949 HeapRegionNode hrnSummary) {
950 assert hrnSummary.isNewSummary();
952 // assert that these nodes belong to THIS graph
953 assert belongsToThis(hrn);
954 assert belongsToThis(hrnSummary);
956 assert hrn != hrnSummary;
958 // transfer references _from_ hrn over to hrnSummary
959 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
960 while( itrReferencee.hasNext() ) {
961 RefEdge edge = itrReferencee.next();
962 RefEdge edgeMerged = edge.copy();
963 edgeMerged.setSrc(hrnSummary);
965 HeapRegionNode hrnReferencee = edge.getDst();
966 RefEdge edgeSummary =
967 hrnSummary.getReferenceTo(hrnReferencee,
972 if( edgeSummary == null ) {
973 // the merge is trivial, nothing to be done
974 addRefEdge(hrnSummary, hrnReferencee, edgeMerged);
977 // otherwise an edge from the referencer to hrnSummary exists already
978 // and the edge referencer->hrn should be merged with it
980 Canonical.unionORpreds(edgeMerged.getBeta(),
981 edgeSummary.getBeta()
984 edgeSummary.setPreds(
985 Canonical.join(edgeMerged.getPreds(),
986 edgeSummary.getPreds()
992 // next transfer references _to_ hrn over to hrnSummary
993 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
994 while( itrReferencer.hasNext() ) {
995 RefEdge edge = itrReferencer.next();
996 RefEdge edgeMerged = edge.copy();
997 edgeMerged.setDst(hrnSummary);
999 RefSrcNode onReferencer = edge.getSrc();
1000 RefEdge edgeSummary =
1001 onReferencer.getReferenceTo(hrnSummary,
1006 if( edgeSummary == null ) {
1007 // the merge is trivial, nothing to be done
1008 addRefEdge(onReferencer, hrnSummary, edgeMerged);
1011 // otherwise an edge from the referencer to alpha_S exists already
1012 // and the edge referencer->alpha_K should be merged with it
1013 edgeSummary.setBeta(
1014 Canonical.unionORpreds(edgeMerged.getBeta(),
1015 edgeSummary.getBeta()
1018 edgeSummary.setPreds(
1019 Canonical.join(edgeMerged.getPreds(),
1020 edgeSummary.getPreds()
1026 // then merge hrn reachability into hrnSummary
1027 hrnSummary.setAlpha(
1028 Canonical.unionORpreds(hrnSummary.getAlpha(),
1033 hrnSummary.setPreds(
1034 Canonical.join(hrnSummary.getPreds(),
1039 // and afterward, this node is gone
1044 protected void transferOnto(HeapRegionNode hrnA,
1045 HeapRegionNode hrnB) {
1047 assert belongsToThis(hrnA);
1048 assert belongsToThis(hrnB);
1049 assert hrnA != hrnB;
1051 // clear references in and out of node b?
1052 assert hrnB.isWiped();
1054 // copy each: (edge in and out of A) to B
1055 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
1056 while( itrReferencee.hasNext() ) {
1057 RefEdge edge = itrReferencee.next();
1058 HeapRegionNode hrnReferencee = edge.getDst();
1059 RefEdge edgeNew = edge.copy();
1060 edgeNew.setSrc(hrnB);
1061 edgeNew.setDst(hrnReferencee);
1063 addRefEdge(hrnB, hrnReferencee, edgeNew);
1066 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
1067 while( itrReferencer.hasNext() ) {
1068 RefEdge edge = itrReferencer.next();
1069 RefSrcNode rsnReferencer = edge.getSrc();
1070 RefEdge edgeNew = edge.copy();
1071 edgeNew.setSrc(rsnReferencer);
1072 edgeNew.setDst(hrnB);
1074 addRefEdge(rsnReferencer, hrnB, edgeNew);
1077 // replace hrnB reachability and preds with hrnA's
1078 hrnB.setAlpha(hrnA.getAlpha() );
1079 hrnB.setPreds(hrnA.getPreds() );
1081 // after transfer, wipe out source
1082 wipeOut(hrnA, true);
1086 // the purpose of this method is to conceptually "wipe out"
1087 // a heap region from the graph--purposefully not called REMOVE
1088 // because the node is still hanging around in the graph, just
1089 // not mechanically connected or have any reach or predicate
1090 // information on it anymore--lots of ops can use this
1091 protected void wipeOut(HeapRegionNode hrn,
1092 boolean wipeVariableReferences) {
1094 assert belongsToThis(hrn);
1096 clearRefEdgesFrom(hrn, null, null, true);
1098 if( wipeVariableReferences ) {
1099 clearRefEdgesTo(hrn, null, null, true);
1101 clearNonVarRefEdgesTo(hrn);
1104 hrn.setAlpha(rsetEmpty);
1105 hrn.setPreds(predsEmpty);
1109 protected void ageTuplesFrom(AllocSite as, RefEdge edge) {
1111 Canonical.ageTuplesFrom(edge.getBeta(),
1117 protected void ageTuplesFrom(AllocSite as, HeapRegionNode hrn) {
1119 Canonical.ageTuplesFrom(hrn.getAlpha(),
1127 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1129 HashSet<HeapRegionNode> nodesWithNewAlpha,
1130 HashSet<RefEdge> edgesWithNewBeta) {
1132 HashSet<HeapRegionNode> todoNodes
1133 = new HashSet<HeapRegionNode>();
1134 todoNodes.add(nPrime);
1136 HashSet<RefEdge> todoEdges
1137 = new HashSet<RefEdge>();
1139 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1140 = new Hashtable<HeapRegionNode, ChangeSet>();
1141 nodePlannedChanges.put(nPrime, c0);
1143 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1144 = new Hashtable<RefEdge, ChangeSet>();
1146 // first propagate change sets everywhere they can go
1147 while( !todoNodes.isEmpty() ) {
1148 HeapRegionNode n = todoNodes.iterator().next();
1149 ChangeSet C = nodePlannedChanges.get(n);
1151 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1152 while( referItr.hasNext() ) {
1153 RefEdge edge = referItr.next();
1154 todoEdges.add(edge);
1156 if( !edgePlannedChanges.containsKey(edge) ) {
1157 edgePlannedChanges.put(edge,
1162 edgePlannedChanges.put(edge,
1163 Canonical.union(edgePlannedChanges.get(edge),
1169 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1170 while( refeeItr.hasNext() ) {
1171 RefEdge edgeF = refeeItr.next();
1172 HeapRegionNode m = edgeF.getDst();
1174 ChangeSet changesToPass = ChangeSet.factory();
1176 Iterator<ChangeTuple> itrCprime = C.iterator();
1177 while( itrCprime.hasNext() ) {
1178 ChangeTuple c = itrCprime.next();
1179 if( edgeF.getBeta().containsIgnorePreds(c.getStateToMatch() )
1182 changesToPass = Canonical.add(changesToPass, c);
1186 if( !changesToPass.isEmpty() ) {
1187 if( !nodePlannedChanges.containsKey(m) ) {
1188 nodePlannedChanges.put(m, ChangeSet.factory() );
1191 ChangeSet currentChanges = nodePlannedChanges.get(m);
1193 if( !changesToPass.isSubset(currentChanges) ) {
1195 nodePlannedChanges.put(m,
1196 Canonical.union(currentChanges,
1205 todoNodes.remove(n);
1208 // then apply all of the changes for each node at once
1209 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1210 while( itrMap.hasNext() ) {
1211 Map.Entry me = (Map.Entry)itrMap.next();
1212 HeapRegionNode n = (HeapRegionNode) me.getKey();
1213 ChangeSet C = (ChangeSet) me.getValue();
1215 // this propagation step is with respect to one change,
1216 // so we capture the full change from the old alpha:
1217 ReachSet localDelta = Canonical.applyChangeSet(n.getAlpha(),
1221 // but this propagation may be only one of many concurrent
1222 // possible changes, so keep a running union with the node's
1223 // partially updated new alpha set
1224 n.setAlphaNew(Canonical.unionORpreds(n.getAlphaNew(),
1229 nodesWithNewAlpha.add(n);
1232 propagateTokensOverEdges(todoEdges,
1239 protected void propagateTokensOverEdges(HashSet <RefEdge> todoEdges,
1240 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1241 HashSet <RefEdge> edgesWithNewBeta) {
1243 // first propagate all change tuples everywhere they can go
1244 while( !todoEdges.isEmpty() ) {
1245 RefEdge edgeE = todoEdges.iterator().next();
1246 todoEdges.remove(edgeE);
1248 if( !edgePlannedChanges.containsKey(edgeE) ) {
1249 edgePlannedChanges.put(edgeE,
1254 ChangeSet C = edgePlannedChanges.get(edgeE);
1256 ChangeSet changesToPass = ChangeSet.factory();
1258 Iterator<ChangeTuple> itrC = C.iterator();
1259 while( itrC.hasNext() ) {
1260 ChangeTuple c = itrC.next();
1261 if( edgeE.getBeta().containsIgnorePreds(c.getStateToMatch() )
1264 changesToPass = Canonical.add(changesToPass, c);
1268 RefSrcNode rsn = edgeE.getSrc();
1270 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1271 HeapRegionNode n = (HeapRegionNode) rsn;
1273 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1274 while( referItr.hasNext() ) {
1275 RefEdge edgeF = referItr.next();
1277 if( !edgePlannedChanges.containsKey(edgeF) ) {
1278 edgePlannedChanges.put(edgeF,
1283 ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
1285 if( !changesToPass.isSubset(currentChanges) ) {
1286 todoEdges.add(edgeF);
1287 edgePlannedChanges.put(edgeF,
1288 Canonical.union(currentChanges,
1297 // then apply all of the changes for each edge at once
1298 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1299 while( itrMap.hasNext() ) {
1300 Map.Entry me = (Map.Entry)itrMap.next();
1301 RefEdge e = (RefEdge) me.getKey();
1302 ChangeSet C = (ChangeSet) me.getValue();
1304 // this propagation step is with respect to one change,
1305 // so we capture the full change from the old beta:
1306 ReachSet localDelta =
1307 Canonical.applyChangeSet(e.getBeta(),
1312 // but this propagation may be only one of many concurrent
1313 // possible changes, so keep a running union with the edge's
1314 // partially updated new beta set
1315 e.setBetaNew(Canonical.unionORpreds(e.getBetaNew(),
1320 edgesWithNewBeta.add(e);
1325 public void taintInSetVars(FlatSESEEnterNode sese) {
1327 Iterator<TempDescriptor> isvItr = sese.getInVarSet().iterator();
1328 while( isvItr.hasNext() ) {
1329 TempDescriptor isv = isvItr.next();
1331 // use this where defined flatnode to support RCR/DFJ
1332 FlatNode whereDefined = null;
1334 // in-set var taints should NOT propagate back into callers
1335 // so give it FALSE(EMPTY) predicates
1345 public void taintStallSite(FlatNode stallSite,
1346 TempDescriptor var) {
1348 // use this where defined flatnode to support RCR/DFJ
1349 FlatNode whereDefined = null;
1351 // stall site taint should propagate back into callers
1352 // so give it TRUE predicates
1361 protected void taintTemp(FlatSESEEnterNode sese,
1364 FlatNode whereDefined,
1368 VariableNode vn = getVariableNodeFromTemp(var);
1370 Iterator<RefEdge> reItr = vn.iteratorToReferencees();
1371 while( reItr.hasNext() ) {
1372 RefEdge re = reItr.next();
1374 Taint taint = Taint.factory(sese,
1377 re.getDst().getAllocSite(),
1382 re.setTaints(Canonical.add(re.getTaints(),
1389 public void removeInContextTaints(FlatSESEEnterNode sese) {
1391 Iterator meItr = id2hrn.entrySet().iterator();
1392 while( meItr.hasNext() ) {
1393 Map.Entry me = (Map.Entry)meItr.next();
1394 Integer id = (Integer) me.getKey();
1395 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1397 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1398 while( reItr.hasNext() ) {
1399 RefEdge re = reItr.next();
1401 re.setTaints(Canonical.removeInContextTaints(re.getTaints(),
1409 public void removeAllStallSiteTaints() {
1411 Iterator meItr = id2hrn.entrySet().iterator();
1412 while( meItr.hasNext() ) {
1413 Map.Entry me = (Map.Entry)meItr.next();
1414 Integer id = (Integer) me.getKey();
1415 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1417 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1418 while( reItr.hasNext() ) {
1419 RefEdge re = reItr.next();
1421 re.setTaints(Canonical.removeStallSiteTaints(re.getTaints()
1429 // used in makeCalleeView below to decide if there is
1430 // already an appropriate out-of-context edge in a callee
1431 // view graph for merging, or null if a new one will be added
1433 getOutOfContextReferenceTo(HeapRegionNode hrn,
1434 TypeDescriptor srcType,
1435 TypeDescriptor refType,
1437 assert belongsToThis(hrn);
1439 HeapRegionNode hrnInContext = id2hrn.get(hrn.getID() );
1440 if( hrnInContext == null ) {
1444 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1445 while( refItr.hasNext() ) {
1446 RefEdge re = refItr.next();
1448 assert belongsToThis(re.getSrc() );
1449 assert belongsToThis(re.getDst() );
1451 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1455 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1456 if( !hrnSrc.isOutOfContext() ) {
1460 if( srcType == null ) {
1461 if( hrnSrc.getType() != null ) {
1465 if( !srcType.equals(hrnSrc.getType() ) ) {
1470 if( !re.typeEquals(refType) ) {
1474 if( !re.fieldEquals(refField) ) {
1478 // tada! We found it!
1485 // used below to convert a ReachSet to its callee-context
1486 // equivalent with respect to allocation sites in this graph
1487 protected ReachSet toCalleeContext(ReachSet rs,
1488 ExistPredSet predsNodeOrEdge,
1489 Set<HrnIdOoc> oocHrnIdOoc2callee
1491 ReachSet out = ReachSet.factory();
1493 Iterator<ReachState> itr = rs.iterator();
1494 while( itr.hasNext() ) {
1495 ReachState stateCaller = itr.next();
1497 ReachState stateCallee = stateCaller;
1499 Iterator<AllocSite> asItr = allocSites.iterator();
1500 while( asItr.hasNext() ) {
1501 AllocSite as = asItr.next();
1503 ReachState stateNew = ReachState.factory();
1504 Iterator<ReachTuple> rtItr = stateCallee.iterator();
1505 while( rtItr.hasNext() ) {
1506 ReachTuple rt = rtItr.next();
1508 // only translate this tuple if it is
1509 // in the out-callee-context bag
1510 HrnIdOoc hio = new HrnIdOoc(rt.getHrnID(),
1513 if( !oocHrnIdOoc2callee.contains(hio) ) {
1514 stateNew = Canonical.addUpArity(stateNew, rt);
1518 int age = as.getAgeCategory(rt.getHrnID() );
1520 // this is the current mapping, where 0, 1, 2S were allocated
1521 // in the current context, 0?, 1? and 2S? were allocated in a
1522 // previous context, and we're translating to a future context
1534 if( age == AllocSite.AGE_notInThisSite ) {
1535 // things not from the site just go back in
1536 stateNew = Canonical.addUpArity(stateNew, rt);
1538 } else if( age == AllocSite.AGE_summary ||
1542 stateNew = Canonical.addUpArity(stateNew,
1543 ReachTuple.factory(as.getSummary(),
1546 true // out-of-context
1551 // otherwise everything else just goes to an out-of-context
1552 // version, everything else the same
1553 Integer I = as.getAge(rt.getHrnID() );
1556 assert !rt.isMultiObject();
1558 stateNew = Canonical.addUpArity(stateNew,
1559 ReachTuple.factory(rt.getHrnID(),
1560 rt.isMultiObject(), // multi
1562 true // out-of-context
1568 stateCallee = stateNew;
1571 // make a predicate of the caller graph element
1572 // and the caller state we just converted
1573 ExistPredSet predsWithState = ExistPredSet.factory();
1575 Iterator<ExistPred> predItr = predsNodeOrEdge.iterator();
1576 while( predItr.hasNext() ) {
1577 ExistPred predNodeOrEdge = predItr.next();
1580 Canonical.add(predsWithState,
1581 ExistPred.factory(predNodeOrEdge.n_hrnID,
1582 predNodeOrEdge.e_tdSrc,
1583 predNodeOrEdge.e_hrnSrcID,
1584 predNodeOrEdge.e_hrnDstID,
1585 predNodeOrEdge.e_type,
1586 predNodeOrEdge.e_field,
1589 predNodeOrEdge.e_srcOutCalleeContext,
1590 predNodeOrEdge.e_srcOutCallerContext
1595 stateCallee = Canonical.changePredsTo(stateCallee,
1598 out = Canonical.add(out,
1602 assert out.isCanonical();
1606 // used below to convert a ReachSet to its caller-context
1607 // equivalent with respect to allocation sites in this graph
1609 toCallerContext(ReachSet rs,
1610 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1612 ReachSet out = ReachSet.factory();
1614 // when the mapping is null it means there were no
1615 // predicates satisfied
1616 if( calleeStatesSatisfied == null ) {
1620 Iterator<ReachState> itr = rs.iterator();
1621 while( itr.hasNext() ) {
1622 ReachState stateCallee = itr.next();
1624 if( calleeStatesSatisfied.containsKey(stateCallee) ) {
1626 // starting from one callee state...
1627 ReachSet rsCaller = ReachSet.factory(stateCallee);
1629 // possibly branch it into many states, which any
1630 // allocation site might do, so lots of derived states
1631 Iterator<AllocSite> asItr = allocSites.iterator();
1632 while( asItr.hasNext() ) {
1633 AllocSite as = asItr.next();
1634 rsCaller = Canonical.toCallerContext(rsCaller, as);
1637 // then before adding each derived, now caller-context
1638 // states to the output, attach the appropriate pred
1639 // based on the source callee state
1640 Iterator<ReachState> stateItr = rsCaller.iterator();
1641 while( stateItr.hasNext() ) {
1642 ReachState stateCaller = stateItr.next();
1643 stateCaller = Canonical.attach(stateCaller,
1644 calleeStatesSatisfied.get(stateCallee)
1646 out = Canonical.add(out,
1653 assert out.isCanonical();
1658 // used below to convert a ReachSet to an equivalent
1659 // version with shadow IDs merged into unshadowed IDs
1660 protected ReachSet unshadow(ReachSet rs) {
1662 Iterator<AllocSite> asItr = allocSites.iterator();
1663 while( asItr.hasNext() ) {
1664 AllocSite as = asItr.next();
1665 out = Canonical.unshadow(out, as);
1667 assert out.isCanonical();
1672 // convert a caller taint set into a callee taint set
1674 toCalleeContext(TaintSet ts,
1675 ExistPredSet predsEdge) {
1677 TaintSet out = TaintSet.factory();
1679 // the idea is easy, the taint identifier itself doesn't
1680 // change at all, but the predicates should be tautology:
1681 // start with the preds passed in from the caller edge
1682 // that host the taints, and alter them to have the taint
1683 // added, just becoming more specific than edge predicate alone
1685 Iterator<Taint> itr = ts.iterator();
1686 while( itr.hasNext() ) {
1687 Taint tCaller = itr.next();
1689 ExistPredSet predsWithTaint = ExistPredSet.factory();
1691 Iterator<ExistPred> predItr = predsEdge.iterator();
1692 while( predItr.hasNext() ) {
1693 ExistPred predEdge = predItr.next();
1696 Canonical.add(predsWithTaint,
1697 ExistPred.factory(predEdge.e_tdSrc,
1698 predEdge.e_hrnSrcID,
1699 predEdge.e_hrnDstID,
1704 predEdge.e_srcOutCalleeContext,
1705 predEdge.e_srcOutCallerContext
1710 Taint tCallee = Canonical.changePredsTo(tCaller,
1713 out = Canonical.add(out,
1718 assert out.isCanonical();
1723 // used below to convert a TaintSet to its caller-context
1724 // equivalent, just eliminate Taints with bad preds
1726 toCallerContext(TaintSet ts,
1727 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied
1730 TaintSet out = TaintSet.factory();
1732 // when the mapping is null it means there were no
1733 // predicates satisfied
1734 if( calleeTaintsSatisfied == null ) {
1738 Iterator<Taint> itr = ts.iterator();
1739 while( itr.hasNext() ) {
1740 Taint tCallee = itr.next();
1742 if( calleeTaintsSatisfied.containsKey(tCallee) ) {
1745 Canonical.attach(Taint.factory(tCallee.sese,
1750 ExistPredSet.factory() ),
1751 calleeTaintsSatisfied.get(tCallee)
1753 out = Canonical.add(out,
1759 assert out.isCanonical();
1766 // use this method to make a new reach graph that is
1767 // what heap the FlatMethod callee from the FlatCall
1768 // would start with reaching from its arguments in
1771 makeCalleeView(FlatCall fc,
1772 FlatMethod fmCallee,
1773 Set<Integer> callerNodeIDsCopiedToCallee,
1774 boolean writeDebugDOTs
1778 // first traverse this context to find nodes and edges
1779 // that will be callee-reachable
1780 Set<HeapRegionNode> reachableCallerNodes =
1781 new HashSet<HeapRegionNode>();
1783 // caller edges between callee-reachable nodes
1784 Set<RefEdge> reachableCallerEdges =
1785 new HashSet<RefEdge>();
1787 // caller edges from arg vars, and the matching param index
1788 // because these become a special edge in callee
1789 Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1790 new Hashtable<RefEdge, Integer>();
1792 // caller edges from local vars or callee-unreachable nodes
1793 // (out-of-context sources) to callee-reachable nodes
1794 Set<RefEdge> oocCallerEdges =
1795 new HashSet<RefEdge>();
1798 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1800 TempDescriptor tdArg = fc.getArgMatchingParamIndex(fmCallee, i);
1801 VariableNode vnArgCaller = this.getVariableNodeFromTemp(tdArg);
1803 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1804 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1806 toVisitInCaller.add(vnArgCaller);
1808 while( !toVisitInCaller.isEmpty() ) {
1809 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1810 toVisitInCaller.remove(rsnCaller);
1811 visitedInCaller.add(rsnCaller);
1813 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1814 while( itrRefEdges.hasNext() ) {
1815 RefEdge reCaller = itrRefEdges.next();
1816 HeapRegionNode hrnCaller = reCaller.getDst();
1818 callerNodeIDsCopiedToCallee.add(hrnCaller.getID() );
1819 reachableCallerNodes.add(hrnCaller);
1821 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1822 reachableCallerEdges.add(reCaller);
1824 if( rsnCaller.equals(vnArgCaller) ) {
1825 reachableCallerArgEdges2paramIndex.put(reCaller, i);
1827 oocCallerEdges.add(reCaller);
1831 if( !visitedInCaller.contains(hrnCaller) ) {
1832 toVisitInCaller.add(hrnCaller);
1835 } // end edge iteration
1836 } // end visiting heap nodes in caller
1837 } // end iterating over parameters as starting points
1840 // now collect out-of-callee-context IDs and
1841 // map them to whether the ID is out of the caller
1843 Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1845 Iterator<Integer> itrInContext =
1846 callerNodeIDsCopiedToCallee.iterator();
1847 while( itrInContext.hasNext() ) {
1848 Integer hrnID = itrInContext.next();
1849 HeapRegionNode hrnCallerAndInContext = id2hrn.get(hrnID);
1851 Iterator<RefEdge> itrMightCross =
1852 hrnCallerAndInContext.iteratorToReferencers();
1853 while( itrMightCross.hasNext() ) {
1854 RefEdge edgeMightCross = itrMightCross.next();
1856 RefSrcNode rsnCallerAndOutContext =
1857 edgeMightCross.getSrc();
1859 if( rsnCallerAndOutContext instanceof VariableNode ) {
1860 // variables do not have out-of-context reach states,
1862 oocCallerEdges.add(edgeMightCross);
1866 HeapRegionNode hrnCallerAndOutContext =
1867 (HeapRegionNode) rsnCallerAndOutContext;
1869 // is this source node out-of-context?
1870 if( callerNodeIDsCopiedToCallee.contains(hrnCallerAndOutContext.getID() ) ) {
1871 // no, skip this edge
1876 oocCallerEdges.add(edgeMightCross);
1878 // add all reach tuples on the node to list
1879 // of things that are out-of-context: insight
1880 // if this node is reachable from someting that WAS
1881 // in-context, then this node should already be in-context
1882 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1883 while( stateItr.hasNext() ) {
1884 ReachState state = stateItr.next();
1886 Iterator<ReachTuple> rtItr = state.iterator();
1887 while( rtItr.hasNext() ) {
1888 ReachTuple rt = rtItr.next();
1890 oocHrnIdOoc2callee.add(new HrnIdOoc(rt.getHrnID(),
1899 // the callee view is a new graph: DON'T MODIFY *THIS* graph
1900 ReachGraph rg = new ReachGraph();
1902 // add nodes to callee graph
1903 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1904 while( hrnItr.hasNext() ) {
1905 HeapRegionNode hrnCaller = hrnItr.next();
1907 assert callerNodeIDsCopiedToCallee.contains(hrnCaller.getID() );
1908 assert !rg.id2hrn.containsKey(hrnCaller.getID() );
1910 ExistPred pred = ExistPred.factory(hrnCaller.getID(), null);
1911 ExistPredSet preds = ExistPredSet.factory(pred);
1913 rg.createNewHeapRegionNode(hrnCaller.getID(),
1914 hrnCaller.isSingleObject(),
1915 hrnCaller.isNewSummary(),
1916 false, // out-of-context?
1917 hrnCaller.getType(),
1918 hrnCaller.getAllocSite(),
1919 toCalleeContext(hrnCaller.getInherent(),
1923 toCalleeContext(hrnCaller.getAlpha(),
1928 hrnCaller.getDescription()
1932 // add param edges to callee graph
1934 reachableCallerArgEdges2paramIndex.entrySet().iterator();
1935 while( argEdges.hasNext() ) {
1936 Map.Entry me = (Map.Entry)argEdges.next();
1937 RefEdge reArg = (RefEdge) me.getKey();
1938 Integer index = (Integer) me.getValue();
1940 VariableNode vnCaller = (VariableNode) reArg.getSrc();
1941 TempDescriptor argCaller = vnCaller.getTempDescriptor();
1943 TempDescriptor paramCallee = fmCallee.getParameter(index);
1944 VariableNode vnCallee = rg.getVariableNodeFromTemp(paramCallee);
1946 HeapRegionNode hrnDstCaller = reArg.getDst();
1947 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
1948 assert hrnDstCallee != null;
1951 ExistPred.factory(argCaller,
1953 hrnDstCallee.getID(),
1958 true, // out-of-callee-context
1959 false // out-of-caller-context
1962 ExistPredSet preds =
1963 ExistPredSet.factory(pred);
1966 new RefEdge(vnCallee,
1970 toCalleeContext(reArg.getBeta(),
1975 toCalleeContext(reArg.getTaints(),
1979 rg.addRefEdge(vnCallee,
1985 // add in-context edges to callee graph
1986 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1987 while( reItr.hasNext() ) {
1988 RefEdge reCaller = reItr.next();
1989 RefSrcNode rsnCaller = reCaller.getSrc();
1990 assert rsnCaller instanceof HeapRegionNode;
1991 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1992 HeapRegionNode hrnDstCaller = reCaller.getDst();
1994 HeapRegionNode hrnSrcCallee = rg.id2hrn.get(hrnSrcCaller.getID() );
1995 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
1996 assert hrnSrcCallee != null;
1997 assert hrnDstCallee != null;
2000 ExistPred.factory(null,
2001 hrnSrcCallee.getID(),
2002 hrnDstCallee.getID(),
2004 reCaller.getField(),
2007 false, // out-of-callee-context
2008 false // out-of-caller-context
2011 ExistPredSet preds =
2012 ExistPredSet.factory(pred);
2015 new RefEdge(hrnSrcCallee,
2018 reCaller.getField(),
2019 toCalleeContext(reCaller.getBeta(),
2024 toCalleeContext(reCaller.getTaints(),
2028 rg.addRefEdge(hrnSrcCallee,
2034 // add out-of-context edges to callee graph
2035 reItr = oocCallerEdges.iterator();
2036 while( reItr.hasNext() ) {
2037 RefEdge reCaller = reItr.next();
2038 RefSrcNode rsnCaller = reCaller.getSrc();
2039 HeapRegionNode hrnDstCaller = reCaller.getDst();
2040 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2041 assert hrnDstCallee != null;
2043 TypeDescriptor oocNodeType;
2045 TempDescriptor oocPredSrcTemp = null;
2046 Integer oocPredSrcID = null;
2047 boolean outOfCalleeContext;
2048 boolean outOfCallerContext;
2050 if( rsnCaller instanceof VariableNode ) {
2051 VariableNode vnCaller = (VariableNode) rsnCaller;
2053 oocReach = rsetEmpty;
2054 oocPredSrcTemp = vnCaller.getTempDescriptor();
2055 outOfCalleeContext = true;
2056 outOfCallerContext = false;
2059 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2060 assert !callerNodeIDsCopiedToCallee.contains(hrnSrcCaller.getID() );
2061 oocNodeType = hrnSrcCaller.getType();
2062 oocReach = hrnSrcCaller.getAlpha();
2063 oocPredSrcID = hrnSrcCaller.getID();
2064 if( hrnSrcCaller.isOutOfContext() ) {
2065 outOfCalleeContext = false;
2066 outOfCallerContext = true;
2068 outOfCalleeContext = true;
2069 outOfCallerContext = false;
2074 ExistPred.factory(oocPredSrcTemp,
2076 hrnDstCallee.getID(),
2078 reCaller.getField(),
2085 ExistPredSet preds =
2086 ExistPredSet.factory(pred);
2088 RefEdge oocEdgeExisting =
2089 rg.getOutOfContextReferenceTo(hrnDstCallee,
2095 if( oocEdgeExisting == null ) {
2096 // for consistency, map one out-of-context "identifier"
2097 // to one heap region node id, otherwise no convergence
2098 String oocid = "oocid"+
2100 hrnDstCallee.getIDString()+
2103 reCaller.getField();
2105 Integer oocHrnID = oocid2hrnid.get(oocid);
2107 HeapRegionNode hrnCalleeAndOutContext;
2109 if( oocHrnID == null ) {
2111 hrnCalleeAndOutContext =
2112 rg.createNewHeapRegionNode(null, // ID
2113 false, // single object?
2114 false, // new summary?
2115 true, // out-of-context?
2117 null, // alloc site, shouldn't be used
2118 toCalleeContext(oocReach,
2122 toCalleeContext(oocReach,
2130 oocid2hrnid.put(oocid, hrnCalleeAndOutContext.getID() );
2134 // the mapping already exists, so see if node is there
2135 hrnCalleeAndOutContext = rg.id2hrn.get(oocHrnID);
2137 if( hrnCalleeAndOutContext == null ) {
2139 hrnCalleeAndOutContext =
2140 rg.createNewHeapRegionNode(oocHrnID, // ID
2141 false, // single object?
2142 false, // new summary?
2143 true, // out-of-context?
2145 null, // alloc site, shouldn't be used
2146 toCalleeContext(oocReach,
2150 toCalleeContext(oocReach,
2159 // otherwise it is there, so merge reachability
2160 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2161 toCalleeContext(oocReach,
2170 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2172 rg.addRefEdge(hrnCalleeAndOutContext,
2174 new RefEdge(hrnCalleeAndOutContext,
2177 reCaller.getField(),
2178 toCalleeContext(reCaller.getBeta(),
2183 toCalleeContext(reCaller.getTaints(),
2189 // the out-of-context edge already exists
2190 oocEdgeExisting.setBeta(Canonical.unionORpreds(oocEdgeExisting.getBeta(),
2191 toCalleeContext(reCaller.getBeta(),
2198 oocEdgeExisting.setPreds(Canonical.join(oocEdgeExisting.getPreds(),
2203 oocEdgeExisting.setTaints(Canonical.unionORpreds(oocEdgeExisting.getTaints(),
2204 toCalleeContext(reCaller.getTaints(),
2210 HeapRegionNode hrnCalleeAndOutContext =
2211 (HeapRegionNode) oocEdgeExisting.getSrc();
2212 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2213 toCalleeContext(oocReach,
2220 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2225 if( writeDebugDOTs ) {
2226 debugGraphPrefix = String.format("call%03d", debugCallSiteVisitCounter);
2227 rg.writeGraph(debugGraphPrefix+"calleeview",
2228 resolveMethodDebugDOTwriteLabels,
2229 resolveMethodDebugDOTselectTemps,
2230 resolveMethodDebugDOTpruneGarbage,
2231 resolveMethodDebugDOThideReach,
2232 resolveMethodDebugDOThideSubsetReach,
2233 resolveMethodDebugDOThidePreds,
2234 resolveMethodDebugDOThideEdgeTaints);
2240 private static Hashtable<String, Integer> oocid2hrnid =
2241 new Hashtable<String, Integer>();
2244 // useful since many graphs writes in the method call debug code
2245 private static boolean resolveMethodDebugDOTwriteLabels = true;
2246 private static boolean resolveMethodDebugDOTselectTemps = true;
2247 private static boolean resolveMethodDebugDOTpruneGarbage = true;
2248 private static boolean resolveMethodDebugDOThideReach = true;
2249 private static boolean resolveMethodDebugDOThideSubsetReach = true;
2250 private static boolean resolveMethodDebugDOThidePreds = false;
2251 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
2253 static String debugGraphPrefix;
2254 static int debugCallSiteVisitCounter;
2255 static int debugCallSiteVisitStartCapture;
2256 static int debugCallSiteNumVisitsToCapture;
2257 static boolean debugCallSiteStopAfter;
2261 resolveMethodCall(FlatCall fc,
2262 FlatMethod fmCallee,
2263 ReachGraph rgCallee,
2264 Set<Integer> callerNodeIDsCopiedToCallee,
2265 boolean writeDebugDOTs
2268 if( writeDebugDOTs ) {
2270 System.out.println(" Writing out visit "+
2271 debugCallSiteVisitCounter+
2272 " to debug call site");
2274 debugGraphPrefix = String.format("call%03d",
2275 debugCallSiteVisitCounter);
2277 rgCallee.writeGraph(debugGraphPrefix+"callee",
2278 resolveMethodDebugDOTwriteLabels,
2279 resolveMethodDebugDOTselectTemps,
2280 resolveMethodDebugDOTpruneGarbage,
2281 resolveMethodDebugDOThideReach,
2282 resolveMethodDebugDOThideSubsetReach,
2283 resolveMethodDebugDOThidePreds,
2284 resolveMethodDebugDOThideEdgeTaints);
2286 writeGraph(debugGraphPrefix+"caller00In",
2287 resolveMethodDebugDOTwriteLabels,
2288 resolveMethodDebugDOTselectTemps,
2289 resolveMethodDebugDOTpruneGarbage,
2290 resolveMethodDebugDOThideReach,
2291 resolveMethodDebugDOThideSubsetReach,
2292 resolveMethodDebugDOThidePreds,
2293 resolveMethodDebugDOThideEdgeTaints,
2294 callerNodeIDsCopiedToCallee);
2299 // method call transfer function steps:
2300 // 1. Use current callee-reachable heap (CRH) to test callee
2301 // predicates and mark what will be coming in.
2302 // 2. Wipe CRH out of caller.
2303 // 3. Transplant marked callee parts in:
2304 // a) bring in nodes
2305 // b) bring in callee -> callee edges
2306 // c) resolve out-of-context -> callee edges
2307 // d) assign return value
2308 // 4. Collapse shadow nodes down
2309 // 5. Global sweep it.
2312 // 1. mark what callee elements have satisfied predicates
2313 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
2314 new Hashtable<HeapRegionNode, ExistPredSet>();
2316 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
2317 new Hashtable<RefEdge, ExistPredSet>();
2319 Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
2320 calleeNode2calleeStatesSatisfied =
2321 new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
2323 Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
2324 calleeEdge2calleeStatesSatisfied =
2325 new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
2327 Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
2328 calleeEdge2calleeTaintsSatisfied =
2329 new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
2331 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
2332 new Hashtable< RefEdge, Set<RefSrcNode> >();
2336 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2337 while( meItr.hasNext() ) {
2338 Map.Entry me = (Map.Entry)meItr.next();
2339 Integer id = (Integer) me.getKey();
2340 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2342 // if a callee element's predicates are satisfied then a set
2343 // of CALLER predicates is returned: they are the predicates
2344 // that the callee element moved into the caller context
2345 // should have, and it is inefficient to find this again later
2346 ExistPredSet predsIfSatis =
2347 hrnCallee.getPreds().isSatisfiedBy(this,
2348 callerNodeIDsCopiedToCallee,
2351 if( predsIfSatis != null ) {
2352 calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
2354 // otherwise don't bother looking at edges to this node
2358 // since the node is coming over, find out which reach
2359 // states on it should come over, too
2360 assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
2362 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2363 while( stateItr.hasNext() ) {
2364 ReachState stateCallee = stateItr.next();
2367 stateCallee.getPreds().isSatisfiedBy(this,
2368 callerNodeIDsCopiedToCallee,
2370 if( predsIfSatis != null ) {
2372 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2373 calleeNode2calleeStatesSatisfied.get(hrnCallee);
2375 if( calleeStatesSatisfied == null ) {
2376 calleeStatesSatisfied =
2377 new Hashtable<ReachState, ExistPredSet>();
2379 calleeNode2calleeStatesSatisfied.put(hrnCallee, calleeStatesSatisfied);
2382 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2386 // then look at edges to the node
2387 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2388 while( reItr.hasNext() ) {
2389 RefEdge reCallee = reItr.next();
2390 RefSrcNode rsnCallee = reCallee.getSrc();
2392 // (caller local variables to in-context heap regions)
2393 // have an (out-of-context heap region -> in-context heap region)
2394 // abstraction in the callEE, so its true we never need to
2395 // look at a (var node -> heap region) edge in callee to bring
2396 // those over for the call site transfer, except for the special
2397 // case of *RETURN var* -> heap region edges.
2398 // What about (param var->heap region)
2399 // edges in callee? They are dealt with below this loop.
2401 if( rsnCallee instanceof VariableNode ) {
2403 // looking for the return-value variable only
2404 VariableNode vnCallee = (VariableNode) rsnCallee;
2405 if( vnCallee.getTempDescriptor() != tdReturn ) {
2409 TempDescriptor returnTemp = fc.getReturnTemp();
2410 if( returnTemp == null ||
2411 !DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2416 // note that the assignment of the return value is to a
2417 // variable in the caller which is out-of-context with
2418 // respect to the callee
2419 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2420 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2421 rsnCallers.add(vnLhsCaller);
2422 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2426 // for HeapRegionNode callee sources...
2428 // first see if the source is out-of-context, and only
2429 // proceed with this edge if we find some caller-context
2431 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2432 boolean matchedOutOfContext = false;
2434 if( !hrnSrcCallee.isOutOfContext() ) {
2437 hrnSrcCallee.getPreds().isSatisfiedBy(this,
2438 callerNodeIDsCopiedToCallee,
2440 if( predsIfSatis != null ) {
2441 calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
2443 // otherwise forget this edge
2448 // hrnSrcCallee is out-of-context
2449 assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
2451 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2453 // use the isSatisfiedBy with a non-null callers set to capture
2454 // nodes in the caller that match the predicates
2455 reCallee.getPreds().isSatisfiedBy( this,
2456 callerNodeIDsCopiedToCallee,
2459 if( !rsnCallers.isEmpty() ) {
2460 matchedOutOfContext = true;
2461 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2465 if( hrnSrcCallee.isOutOfContext() &&
2466 !matchedOutOfContext ) {
2473 reCallee.getPreds().isSatisfiedBy(this,
2474 callerNodeIDsCopiedToCallee,
2478 if( predsIfSatis != null ) {
2479 calleeEdgesSatisfied.put(reCallee, predsIfSatis);
2481 // since the edge is coming over, find out which reach
2482 // states on it should come over, too
2483 assert calleeEdge2calleeStatesSatisfied.get(reCallee) == null;
2485 stateItr = reCallee.getBeta().iterator();
2486 while( stateItr.hasNext() ) {
2487 ReachState stateCallee = stateItr.next();
2490 stateCallee.getPreds().isSatisfiedBy(this,
2491 callerNodeIDsCopiedToCallee,
2493 if( predsIfSatis != null ) {
2495 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2496 calleeEdge2calleeStatesSatisfied.get(reCallee);
2498 if( calleeStatesSatisfied == null ) {
2499 calleeStatesSatisfied =
2500 new Hashtable<ReachState, ExistPredSet>();
2502 calleeEdge2calleeStatesSatisfied.put(reCallee, calleeStatesSatisfied);
2505 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2509 // since the edge is coming over, find out which taints
2510 // on it should come over, too
2511 assert calleeEdge2calleeTaintsSatisfied.get(reCallee) == null;
2513 Iterator<Taint> tItr = reCallee.getTaints().iterator();
2514 while( tItr.hasNext() ) {
2515 Taint tCallee = tItr.next();
2518 tCallee.getPreds().isSatisfiedBy(this,
2519 callerNodeIDsCopiedToCallee,
2521 if( predsIfSatis != null ) {
2523 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2524 calleeEdge2calleeTaintsSatisfied.get(reCallee);
2526 if( calleeTaintsSatisfied == null ) {
2527 calleeTaintsSatisfied =
2528 new Hashtable<Taint, ExistPredSet>();
2530 calleeEdge2calleeTaintsSatisfied.put(reCallee, calleeTaintsSatisfied);
2533 calleeTaintsSatisfied.put(tCallee, predsIfSatis);
2540 if( writeDebugDOTs ) {
2541 writeGraph(debugGraphPrefix+"caller20BeforeWipe",
2542 resolveMethodDebugDOTwriteLabels,
2543 resolveMethodDebugDOTselectTemps,
2544 resolveMethodDebugDOTpruneGarbage,
2545 resolveMethodDebugDOThideReach,
2546 resolveMethodDebugDOThideSubsetReach,
2547 resolveMethodDebugDOThidePreds,
2548 resolveMethodDebugDOThideEdgeTaints);
2552 // 2. predicates tested, ok to wipe out caller part
2553 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2554 while( hrnItr.hasNext() ) {
2555 Integer hrnID = hrnItr.next();
2556 HeapRegionNode hrnCaller = id2hrn.get(hrnID);
2557 assert hrnCaller != null;
2559 // when clearing off nodes, also eliminate variable
2561 wipeOut(hrnCaller, true);
2564 // if we are assigning the return value to something, clobber now
2565 // as part of the wipe
2566 TempDescriptor returnTemp = fc.getReturnTemp();
2567 if( returnTemp != null &&
2568 DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2571 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2572 clearRefEdgesFrom(vnLhsCaller, null, null, true);
2578 if( writeDebugDOTs ) {
2579 writeGraph(debugGraphPrefix+"caller30BeforeAddingNodes",
2580 resolveMethodDebugDOTwriteLabels,
2581 resolveMethodDebugDOTselectTemps,
2582 resolveMethodDebugDOTpruneGarbage,
2583 resolveMethodDebugDOThideReach,
2584 resolveMethodDebugDOThideSubsetReach,
2585 resolveMethodDebugDOThidePreds,
2586 resolveMethodDebugDOThideEdgeTaints);
2592 // 3. callee elements with satisfied preds come in, note that
2593 // the mapping of elements satisfied to preds is like this:
2594 // A callee element EE has preds EEp that are satisfied by
2595 // some caller element ER. We bring EE into the caller
2596 // context as ERee with the preds of ER, namely ERp, which
2597 // in the following algorithm is the value in the mapping
2600 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2601 while( satisItr.hasNext() ) {
2602 Map.Entry me = (Map.Entry)satisItr.next();
2603 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2604 ExistPredSet preds = (ExistPredSet) me.getValue();
2606 // TODO: I think its true that the current implementation uses
2607 // the type of the OOC region and the predicates OF THE EDGE from
2608 // it to link everything up in caller context, so that's why we're
2609 // skipping this... maybe that's a sillier way to do it?
2610 if( hrnCallee.isOutOfContext() ) {
2614 AllocSite as = hrnCallee.getAllocSite();
2617 Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
2619 HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
2620 if( hrnCaller == null ) {
2622 createNewHeapRegionNode(hrnIDshadow, // id or null to generate a new one
2623 hrnCallee.isSingleObject(), // single object?
2624 hrnCallee.isNewSummary(), // summary?
2625 false, // out-of-context?
2626 hrnCallee.getType(), // type
2627 hrnCallee.getAllocSite(), // allocation site
2628 toCallerContext(hrnCallee.getInherent(),
2629 calleeNode2calleeStatesSatisfied.get(hrnCallee) ), // inherent reach
2630 null, // current reach
2631 predsEmpty, // predicates
2632 hrnCallee.getDescription() // description
2635 assert hrnCaller.isWiped();
2638 hrnCaller.setAlpha(toCallerContext(hrnCallee.getAlpha(),
2639 calleeNode2calleeStatesSatisfied.get(hrnCallee)
2643 hrnCaller.setPreds(preds);
2650 if( writeDebugDOTs ) {
2651 writeGraph(debugGraphPrefix+"caller31BeforeAddingEdges",
2652 resolveMethodDebugDOTwriteLabels,
2653 resolveMethodDebugDOTselectTemps,
2654 resolveMethodDebugDOTpruneGarbage,
2655 resolveMethodDebugDOThideReach,
2656 resolveMethodDebugDOThideSubsetReach,
2657 resolveMethodDebugDOThidePreds,
2658 resolveMethodDebugDOThideEdgeTaints);
2662 // set these up during the next procedure so after
2663 // the caller has all of its nodes and edges put
2664 // back together we can propagate the callee's
2665 // reach changes backwards into the caller graph
2666 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2668 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2669 new Hashtable<RefEdge, ChangeSet>();
2672 // 3.b) callee -> callee edges AND out-of-context -> callee
2673 // which includes return temp -> callee edges now, too
2674 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2675 while( satisItr.hasNext() ) {
2676 Map.Entry me = (Map.Entry)satisItr.next();
2677 RefEdge reCallee = (RefEdge) me.getKey();
2678 ExistPredSet preds = (ExistPredSet) me.getValue();
2680 HeapRegionNode hrnDstCallee = reCallee.getDst();
2681 AllocSite asDst = hrnDstCallee.getAllocSite();
2682 allocSites.add(asDst);
2684 Integer hrnIDDstShadow =
2685 asDst.getShadowIDfromID(hrnDstCallee.getID() );
2687 HeapRegionNode hrnDstCaller = id2hrn.get(hrnIDDstShadow);
2688 assert hrnDstCaller != null;
2691 RefSrcNode rsnCallee = reCallee.getSrc();
2693 Set<RefSrcNode> rsnCallers =
2694 new HashSet<RefSrcNode>();
2696 Set<RefSrcNode> oocCallers =
2697 calleeEdges2oocCallerSrcMatches.get(reCallee);
2699 if( rsnCallee instanceof HeapRegionNode ) {
2700 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2701 if( hrnCalleeSrc.isOutOfContext() ) {
2702 assert oocCallers != null;
2707 if( oocCallers == null ) {
2708 // there are no out-of-context matches, so it's
2709 // either a param/arg var or one in-context heap region
2710 if( rsnCallee instanceof VariableNode ) {
2711 // variable -> node in the callee should only
2712 // come into the caller if its from a param var
2713 VariableNode vnCallee = (VariableNode) rsnCallee;
2714 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2715 TempDescriptor tdArg = fc.getArgMatchingParam(fmCallee,
2717 if( tdArg == null ) {
2718 // this means the variable isn't a parameter, its local
2719 // to the callee so we ignore it in call site transfer
2720 // shouldn't this NEVER HAPPEN?
2724 rsnCallers.add(this.getVariableNodeFromTemp(tdArg) );
2727 // otherwise source is in context, one region
2729 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2731 // translate an in-context node to shadow
2732 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2733 allocSites.add(asSrc);
2735 Integer hrnIDSrcShadow =
2736 asSrc.getShadowIDfromID(hrnSrcCallee.getID() );
2738 HeapRegionNode hrnSrcCallerShadow =
2739 this.id2hrn.get(hrnIDSrcShadow);
2741 assert hrnSrcCallerShadow != null;
2743 rsnCallers.add(hrnSrcCallerShadow);
2747 // otherwise we have a set of out-of-context srcs
2748 // that should NOT be translated to shadow nodes
2749 assert !oocCallers.isEmpty();
2750 rsnCallers.addAll(oocCallers);
2753 // now make all caller edges we've identified from
2754 // this callee edge with a satisfied predicate
2755 assert !rsnCallers.isEmpty();
2756 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2757 while( rsnItr.hasNext() ) {
2758 RefSrcNode rsnCaller = rsnItr.next();
2760 RefEdge reCaller = new RefEdge(rsnCaller,
2763 reCallee.getField(),
2764 toCallerContext(reCallee.getBeta(),
2765 calleeEdge2calleeStatesSatisfied.get(reCallee) ),
2767 toCallerContext(reCallee.getTaints(),
2768 calleeEdge2calleeTaintsSatisfied.get(reCallee) )
2771 ChangeSet cs = ChangeSet.factory();
2772 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2773 while( rsItr.hasNext() ) {
2774 ReachState state = rsItr.next();
2775 ExistPredSet predsPreCallee = state.getPreds();
2777 if( state.isEmpty() ) {
2781 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2782 while( predItr.hasNext() ) {
2783 ExistPred pred = predItr.next();
2784 ReachState old = pred.ne_state;
2790 cs = Canonical.add(cs,
2791 ChangeTuple.factory(old,
2798 // we're just going to use the convenient "merge-if-exists"
2799 // edge call below, but still take a separate look if there
2800 // is an existing caller edge to build change sets properly
2801 if( !cs.isEmpty() ) {
2802 RefEdge edgeExisting = rsnCaller.getReferenceTo(hrnDstCaller,
2806 if( edgeExisting != null ) {
2807 ChangeSet csExisting = edgePlannedChanges.get(edgeExisting);
2808 if( csExisting == null ) {
2809 csExisting = ChangeSet.factory();
2811 edgePlannedChanges.put(edgeExisting,
2812 Canonical.union(csExisting,
2817 edgesForPropagation.add(reCaller);
2818 assert !edgePlannedChanges.containsKey(reCaller);
2819 edgePlannedChanges.put(reCaller, cs);
2823 // then add new caller edge or merge
2824 addEdgeOrMergeWithExisting(reCaller);
2832 if( writeDebugDOTs ) {
2833 writeGraph(debugGraphPrefix+"caller38propagateReach",
2834 resolveMethodDebugDOTwriteLabels,
2835 resolveMethodDebugDOTselectTemps,
2836 resolveMethodDebugDOTpruneGarbage,
2837 resolveMethodDebugDOThideReach,
2838 resolveMethodDebugDOThideSubsetReach,
2839 resolveMethodDebugDOThidePreds,
2840 resolveMethodDebugDOThideEdgeTaints);
2843 // propagate callee reachability changes to the rest
2844 // of the caller graph edges
2845 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2847 propagateTokensOverEdges(edgesForPropagation, // source edges
2848 edgePlannedChanges, // map src edge to change set
2849 edgesUpdated); // list of updated edges
2851 // commit beta' (beta<-betaNew)
2852 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2853 while( edgeItr.hasNext() ) {
2854 edgeItr.next().applyBetaNew();
2863 if( writeDebugDOTs ) {
2864 writeGraph(debugGraphPrefix+"caller40BeforeShadowMerge",
2865 resolveMethodDebugDOTwriteLabels,
2866 resolveMethodDebugDOTselectTemps,
2867 resolveMethodDebugDOTpruneGarbage,
2868 resolveMethodDebugDOThideReach,
2869 resolveMethodDebugDOThideSubsetReach,
2870 resolveMethodDebugDOThidePreds,
2871 resolveMethodDebugDOThideEdgeTaints);
2875 // 4) merge shadow nodes so alloc sites are back to k
2876 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2877 while( asItr.hasNext() ) {
2878 // for each allocation site do the following to merge
2879 // shadow nodes (newest from callee) with any existing
2880 // look for the newest normal and newest shadow "slot"
2881 // not being used, transfer normal to shadow. Keep
2882 // doing this until there are no more normal nodes, or
2883 // no empty shadow slots: then merge all remaining normal
2884 // nodes into the shadow summary. Finally, convert all
2885 // shadow to their normal versions.
2886 AllocSite as = asItr.next();
2890 while( ageNorm < allocationDepth &&
2891 ageShad < allocationDepth ) {
2893 // first, are there any normal nodes left?
2894 Integer idNorm = as.getIthOldest(ageNorm);
2895 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2896 if( hrnNorm == null ) {
2897 // no, this age of normal node not in the caller graph
2902 // yes, a normal node exists, is there an empty shadow
2903 // "slot" to transfer it onto?
2904 HeapRegionNode hrnShad = getIthNode(as, ageShad, true);
2905 if( !hrnShad.isWiped() ) {
2906 // no, this age of shadow node is not empty
2911 // yes, this shadow node is empty
2912 transferOnto(hrnNorm, hrnShad);
2917 // now, while there are still normal nodes but no shadow
2918 // slots, merge normal nodes into the shadow summary
2919 while( ageNorm < allocationDepth ) {
2921 // first, are there any normal nodes left?
2922 Integer idNorm = as.getIthOldest(ageNorm);
2923 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2924 if( hrnNorm == null ) {
2925 // no, this age of normal node not in the caller graph
2930 // yes, a normal node exists, so get the shadow summary
2931 HeapRegionNode summShad = getSummaryNode(as, true);
2932 mergeIntoSummary(hrnNorm, summShad);
2934 // now tokens in reachability sets need to age also
2935 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2936 while( itrAllHRNodes.hasNext() ) {
2937 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
2938 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
2940 ageTuplesFrom(as, hrnToAge);
2942 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
2943 while( itrEdges.hasNext() ) {
2944 ageTuplesFrom(as, itrEdges.next() );
2951 // if there is a normal summary, merge it into shadow summary
2952 Integer idNorm = as.getSummary();
2953 HeapRegionNode summNorm = id2hrn.get(idNorm);
2954 if( summNorm != null ) {
2955 HeapRegionNode summShad = getSummaryNode(as, true);
2956 mergeIntoSummary(summNorm, summShad);
2959 // finally, flip all existing shadow nodes onto the normal
2960 for( int i = 0; i < allocationDepth; ++i ) {
2961 Integer idShad = as.getIthOldestShadow(i);
2962 HeapRegionNode hrnShad = id2hrn.get(idShad);
2963 if( hrnShad != null ) {
2965 HeapRegionNode hrnNorm = getIthNode(as, i, false);
2966 assert hrnNorm.isWiped();
2967 transferOnto(hrnShad, hrnNorm);
2971 Integer idShad = as.getSummaryShadow();
2972 HeapRegionNode summShad = id2hrn.get(idShad);
2973 if( summShad != null ) {
2974 summNorm = getSummaryNode(as, false);
2975 transferOnto(summShad, summNorm);
2984 if( writeDebugDOTs ) {
2985 writeGraph(debugGraphPrefix+"caller45BeforeUnshadow",
2986 resolveMethodDebugDOTwriteLabels,
2987 resolveMethodDebugDOTselectTemps,
2988 resolveMethodDebugDOTpruneGarbage,
2989 resolveMethodDebugDOThideReach,
2990 resolveMethodDebugDOThideSubsetReach,
2991 resolveMethodDebugDOThidePreds,
2992 resolveMethodDebugDOThideEdgeTaints);
2996 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2997 while( itrAllHRNodes.hasNext() ) {
2998 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
2999 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3001 hrn.setAlpha(unshadow(hrn.getAlpha() ) );
3003 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
3004 while( itrEdges.hasNext() ) {
3005 RefEdge re = itrEdges.next();
3006 re.setBeta(unshadow(re.getBeta() ) );
3013 if( writeDebugDOTs ) {
3014 writeGraph(debugGraphPrefix+"caller50BeforeGlobalSweep",
3015 resolveMethodDebugDOTwriteLabels,
3016 resolveMethodDebugDOTselectTemps,
3017 resolveMethodDebugDOTpruneGarbage,
3018 resolveMethodDebugDOThideReach,
3019 resolveMethodDebugDOThideSubsetReach,
3020 resolveMethodDebugDOThidePreds,
3021 resolveMethodDebugDOThideEdgeTaints);
3026 if( !DISABLE_GLOBAL_SWEEP ) {
3031 if( writeDebugDOTs ) {
3032 writeGraph(debugGraphPrefix+"caller90AfterTransfer",
3033 resolveMethodDebugDOTwriteLabels,
3034 resolveMethodDebugDOTselectTemps,
3035 resolveMethodDebugDOTpruneGarbage,
3036 resolveMethodDebugDOThideReach,
3037 resolveMethodDebugDOThideSubsetReach,
3038 resolveMethodDebugDOThidePreds,
3039 resolveMethodDebugDOThideEdgeTaints);
3045 ////////////////////////////////////////////////////
3047 // Abstract garbage collection simply removes
3048 // heap region nodes that are not mechanically
3049 // reachable from a root set. This step is
3050 // essential for testing node and edge existence
3051 // predicates efficiently
3053 ////////////////////////////////////////////////////
3054 public void abstractGarbageCollect(Set<TempDescriptor> liveSet) {
3056 // calculate a root set, will be different for Java
3057 // version of analysis versus Bamboo version
3058 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3060 // visit every variable in graph while building root
3061 // set, and do iterating on a copy, so we can remove
3062 // dead variables while we're at this
3063 Iterator makeCopyItr = td2vn.entrySet().iterator();
3064 Set entrysCopy = new HashSet();
3065 while( makeCopyItr.hasNext() ) {
3066 entrysCopy.add(makeCopyItr.next() );
3069 Iterator eItr = entrysCopy.iterator();
3070 while( eItr.hasNext() ) {
3071 Map.Entry me = (Map.Entry)eItr.next();
3072 TempDescriptor td = (TempDescriptor) me.getKey();
3073 VariableNode vn = (VariableNode) me.getValue();
3075 if( liveSet.contains(td) ) {
3079 // dead var, remove completely from graph
3081 clearRefEdgesFrom(vn, null, null, true);
3085 // everything visited in a traversal is
3086 // considered abstractly live
3087 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3089 while( !toVisit.isEmpty() ) {
3090 RefSrcNode rsn = toVisit.iterator().next();
3091 toVisit.remove(rsn);
3094 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3095 while( hrnItr.hasNext() ) {
3096 RefEdge edge = hrnItr.next();
3097 HeapRegionNode hrn = edge.getDst();
3099 if( !visited.contains(hrn) ) {
3105 // get a copy of the set to iterate over because
3106 // we're going to monkey with the graph when we
3107 // identify a garbage node
3108 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3109 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3110 while( hrnItr.hasNext() ) {
3111 hrnAllPrior.add(hrnItr.next() );
3114 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3115 while( hrnAllItr.hasNext() ) {
3116 HeapRegionNode hrn = hrnAllItr.next();
3118 if( !visited.contains(hrn) ) {
3120 // heap region nodes are compared across ReachGraph
3121 // objects by their integer ID, so when discarding
3122 // garbage nodes we must also discard entries in
3123 // the ID -> heap region hashtable.
3124 id2hrn.remove(hrn.getID() );
3126 // RefEdge objects are two-way linked between
3127 // nodes, so when a node is identified as garbage,
3128 // actively clear references to and from it so
3129 // live nodes won't have dangling RefEdge's
3132 // if we just removed the last node from an allocation
3133 // site, it should be taken out of the ReachGraph's list
3134 AllocSite as = hrn.getAllocSite();
3135 if( !hasNodesOf(as) ) {
3136 allocSites.remove(as);
3142 protected boolean hasNodesOf(AllocSite as) {
3143 if( id2hrn.containsKey(as.getSummary() ) ) {
3147 for( int i = 0; i < allocationDepth; ++i ) {
3148 if( id2hrn.containsKey(as.getIthOldest(i) ) ) {
3156 ////////////////////////////////////////////////////
3158 // This global sweep is an optional step to prune
3159 // reachability sets that are not internally
3160 // consistent with the global graph. It should be
3161 // invoked after strong updates or method calls.
3163 ////////////////////////////////////////////////////
3164 public void globalSweep() {
3166 // boldB is part of the phase 1 sweep
3167 // it has an in-context table and an out-of-context table
3168 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3169 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3171 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3172 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3174 // visit every heap region to initialize alphaNew and betaNew,
3175 // and make a map of every hrnID to the source nodes it should
3176 // propagate forward from. In-context flagged hrnID's propagate
3177 // from only the in-context node they name, but out-of-context
3178 // ID's may propagate from several out-of-context nodes
3179 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3180 new Hashtable< Integer, Set<HeapRegionNode> >();
3182 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3183 new Hashtable< Integer, Set<HeapRegionNode> >();
3186 Iterator itrHrns = id2hrn.entrySet().iterator();
3187 while( itrHrns.hasNext() ) {
3188 Map.Entry me = (Map.Entry)itrHrns.next();
3189 Integer hrnID = (Integer) me.getKey();
3190 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3192 // assert that this node and incoming edges have clean alphaNew
3193 // and betaNew sets, respectively
3194 assert rsetEmpty.equals(hrn.getAlphaNew() );
3196 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3197 while( itrRers.hasNext() ) {
3198 RefEdge edge = itrRers.next();
3199 assert rsetEmpty.equals(edge.getBetaNew() );
3202 // make a mapping of IDs to heap regions they propagate from
3203 if( hrn.isFlagged() ) {
3204 assert !hrn.isOutOfContext();
3205 assert !icID2srcs.containsKey(hrn.getID() );
3207 // in-context flagged node IDs simply propagate from the
3209 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3211 icID2srcs.put(hrn.getID(), srcs);
3214 if( hrn.isOutOfContext() ) {
3215 assert !hrn.isFlagged();
3217 // the reachability states on an out-of-context
3218 // node are not really important (combinations of
3219 // IDs or arity)--what matters is that the states
3220 // specify which nodes this out-of-context node
3221 // stands in for. For example, if the state [17?, 19*]
3222 // appears on the ooc node, it may serve as a source
3223 // for node 17? and a source for node 19.
3224 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3225 while( stateItr.hasNext() ) {
3226 ReachState state = stateItr.next();
3228 Iterator<ReachTuple> rtItr = state.iterator();
3229 while( rtItr.hasNext() ) {
3230 ReachTuple rt = rtItr.next();
3231 assert rt.isOutOfContext();
3233 Set<HeapRegionNode> srcs = oocID2srcs.get(rt.getHrnID() );
3234 if( srcs == null ) {
3235 srcs = new HashSet<HeapRegionNode>();
3238 oocID2srcs.put(rt.getHrnID(), srcs);
3244 // calculate boldB for all hrnIDs identified by the above
3245 // node traversal, propagating from every source
3246 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3249 Set<HeapRegionNode> srcs;
3252 if( !icID2srcs.isEmpty() ) {
3253 Map.Entry me = (Map.Entry)icID2srcs.entrySet().iterator().next();
3254 hrnID = (Integer) me.getKey();
3255 srcs = (Set<HeapRegionNode>)me.getValue();
3257 icID2srcs.remove(hrnID);
3260 assert !oocID2srcs.isEmpty();
3262 Map.Entry me = (Map.Entry)oocID2srcs.entrySet().iterator().next();
3263 hrnID = (Integer) me.getKey();
3264 srcs = (Set<HeapRegionNode>)me.getValue();
3266 oocID2srcs.remove(hrnID);
3270 Hashtable<RefEdge, ReachSet> boldB_f =
3271 new Hashtable<RefEdge, ReachSet>();
3273 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3275 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3276 while( hrnItr.hasNext() ) {
3277 HeapRegionNode hrn = hrnItr.next();
3279 assert workSetEdges.isEmpty();
3281 // initial boldB_f constraints
3282 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3283 while( itrRees.hasNext() ) {
3284 RefEdge edge = itrRees.next();
3286 assert !boldB_f.containsKey(edge);
3287 boldB_f.put(edge, edge.getBeta() );
3289 assert !workSetEdges.contains(edge);
3290 workSetEdges.add(edge);
3293 // enforce the boldB_f constraint at edges until we reach a fixed point
3294 while( !workSetEdges.isEmpty() ) {
3295 RefEdge edge = workSetEdges.iterator().next();
3296 workSetEdges.remove(edge);
3298 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3299 while( itrPrime.hasNext() ) {
3300 RefEdge edgePrime = itrPrime.next();
3302 ReachSet prevResult = boldB_f.get(edgePrime);
3303 ReachSet intersection = Canonical.intersection(boldB_f.get(edge),
3307 if( prevResult == null ||
3308 Canonical.unionORpreds(prevResult,
3309 intersection).size()
3313 if( prevResult == null ) {
3314 boldB_f.put(edgePrime,
3315 Canonical.unionORpreds(edgePrime.getBeta(),
3320 boldB_f.put(edgePrime,
3321 Canonical.unionORpreds(prevResult,
3326 workSetEdges.add(edgePrime);
3333 boldBic.put(hrnID, boldB_f);
3335 boldBooc.put(hrnID, boldB_f);
3340 // use boldB to prune hrnIDs from alpha states that are impossible
3341 // and propagate the differences backwards across edges
3342 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3344 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3345 new Hashtable<RefEdge, ChangeSet>();
3348 itrHrns = id2hrn.entrySet().iterator();
3349 while( itrHrns.hasNext() ) {
3350 Map.Entry me = (Map.Entry)itrHrns.next();
3351 Integer hrnID = (Integer) me.getKey();
3352 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3354 // out-of-context nodes don't participate in the
3355 // global sweep, they serve as sources for the pass
3357 if( hrn.isOutOfContext() ) {
3361 // the inherent states of a region are the exception
3362 // to removal as the global sweep prunes
3363 ReachTuple rtException = ReachTuple.factory(hrnID,
3364 !hrn.isSingleObject(),
3365 ReachTuple.ARITY_ONE,
3366 false // out-of-context
3369 ChangeSet cts = ChangeSet.factory();
3371 // mark hrnIDs for removal
3372 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3373 while( stateItr.hasNext() ) {
3374 ReachState stateOld = stateItr.next();
3376 ReachState markedHrnIDs = ReachState.factory();
3378 Iterator<ReachTuple> rtItr = stateOld.iterator();
3379 while( rtItr.hasNext() ) {
3380 ReachTuple rtOld = rtItr.next();
3382 // never remove the inherent hrnID from a flagged region
3383 // because it is trivially satisfied
3384 if( hrn.isFlagged() ) {
3385 if( rtOld == rtException ) {
3390 // does boldB allow this hrnID?
3391 boolean foundState = false;
3392 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3393 while( incidentEdgeItr.hasNext() ) {
3394 RefEdge incidentEdge = incidentEdgeItr.next();
3396 Hashtable<RefEdge, ReachSet> B;
3397 if( rtOld.isOutOfContext() ) {
3398 B = boldBooc.get(rtOld.getHrnID() );
3401 if( !id2hrn.containsKey(rtOld.getHrnID() ) ) {
3402 // let symbols not in the graph get pruned
3406 B = boldBic.get(rtOld.getHrnID() );
3410 ReachSet boldB_rtOld_incident = B.get(incidentEdge);
3411 if( boldB_rtOld_incident != null &&
3412 boldB_rtOld_incident.containsIgnorePreds(stateOld) != null
3420 markedHrnIDs = Canonical.addUpArity(markedHrnIDs, rtOld);
3424 // if there is nothing marked, just move on
3425 if( markedHrnIDs.isEmpty() ) {
3426 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3433 // remove all marked hrnIDs and establish a change set that should
3434 // propagate backwards over edges from this node
3435 ReachState statePruned = ReachState.factory();
3436 rtItr = stateOld.iterator();
3437 while( rtItr.hasNext() ) {
3438 ReachTuple rtOld = rtItr.next();
3440 if( !markedHrnIDs.containsTuple(rtOld) ) {
3441 statePruned = Canonical.addUpArity(statePruned, rtOld);
3444 assert !stateOld.equals(statePruned);
3446 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3450 ChangeTuple ct = ChangeTuple.factory(stateOld,
3453 cts = Canonical.add(cts, ct);
3456 // throw change tuple set on all incident edges
3457 if( !cts.isEmpty() ) {
3458 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3459 while( incidentEdgeItr.hasNext() ) {
3460 RefEdge incidentEdge = incidentEdgeItr.next();
3462 edgesForPropagation.add(incidentEdge);
3464 if( edgePlannedChanges.get(incidentEdge) == null ) {
3465 edgePlannedChanges.put(incidentEdge, cts);
3467 edgePlannedChanges.put(
3469 Canonical.union(edgePlannedChanges.get(incidentEdge),
3478 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3480 propagateTokensOverEdges(edgesForPropagation,
3484 // at the end of the 1st phase reference edges have
3485 // beta, betaNew that correspond to beta and betaR
3487 // commit beta<-betaNew, so beta=betaR and betaNew
3488 // will represent the beta' calculation in 2nd phase
3490 // commit alpha<-alphaNew because it won't change
3491 HashSet<RefEdge> res = new HashSet<RefEdge>();
3493 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3494 while( nodeItr.hasNext() ) {
3495 HeapRegionNode hrn = nodeItr.next();
3497 // as mentioned above, out-of-context nodes only serve
3498 // as sources of reach states for the sweep, not part
3500 if( hrn.isOutOfContext() ) {
3501 assert hrn.getAlphaNew().equals(rsetEmpty);
3503 hrn.applyAlphaNew();
3506 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3507 while( itrRes.hasNext() ) {
3508 res.add(itrRes.next() );
3514 Iterator<RefEdge> edgeItr = res.iterator();
3515 while( edgeItr.hasNext() ) {
3516 RefEdge edge = edgeItr.next();
3517 HeapRegionNode hrn = edge.getDst();
3519 // commit results of last phase
3520 if( edgesUpdated.contains(edge) ) {
3521 edge.applyBetaNew();
3524 // compute intial condition of 2nd phase
3525 edge.setBetaNew(Canonical.intersection(edge.getBeta(),
3531 // every edge in the graph is the initial workset
3532 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3533 while( !edgeWorkSet.isEmpty() ) {
3534 RefEdge edgePrime = edgeWorkSet.iterator().next();
3535 edgeWorkSet.remove(edgePrime);
3537 RefSrcNode rsn = edgePrime.getSrc();
3538 if( !(rsn instanceof HeapRegionNode) ) {
3541 HeapRegionNode hrn = (HeapRegionNode) rsn;
3543 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3544 while( itrEdge.hasNext() ) {
3545 RefEdge edge = itrEdge.next();
3547 ReachSet prevResult = edge.getBetaNew();
3548 assert prevResult != null;
3550 ReachSet intersection =
3551 Canonical.intersection(edge.getBeta(),
3552 edgePrime.getBetaNew()
3555 if( Canonical.unionORpreds(prevResult,
3562 Canonical.unionORpreds(prevResult,
3566 edgeWorkSet.add(edge);
3571 // commit beta' (beta<-betaNew)
3572 edgeItr = res.iterator();
3573 while( edgeItr.hasNext() ) {
3574 edgeItr.next().applyBetaNew();
3579 // a useful assertion for debugging:
3580 // every in-context tuple on any edge or
3581 // any node should name a node that is
3582 // part of the graph
3583 public boolean inContextTuplesInGraph() {
3585 Iterator hrnItr = id2hrn.entrySet().iterator();
3586 while( hrnItr.hasNext() ) {
3587 Map.Entry me = (Map.Entry)hrnItr.next();
3588 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3591 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3592 while( stateItr.hasNext() ) {
3593 ReachState state = stateItr.next();
3595 Iterator<ReachTuple> rtItr = state.iterator();
3596 while( rtItr.hasNext() ) {
3597 ReachTuple rt = rtItr.next();
3599 if( !rt.isOutOfContext() ) {
3600 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3601 System.out.println(rt.getHrnID()+" is missing");
3609 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3610 while( edgeItr.hasNext() ) {
3611 RefEdge edge = edgeItr.next();
3613 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3614 while( stateItr.hasNext() ) {
3615 ReachState state = stateItr.next();
3617 Iterator<ReachTuple> rtItr = state.iterator();
3618 while( rtItr.hasNext() ) {
3619 ReachTuple rt = rtItr.next();
3621 if( !rt.isOutOfContext() ) {
3622 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3623 System.out.println(rt.getHrnID()+" is missing");
3636 // another useful assertion for debugging
3637 public boolean noEmptyReachSetsInGraph() {
3639 Iterator hrnItr = id2hrn.entrySet().iterator();
3640 while( hrnItr.hasNext() ) {
3641 Map.Entry me = (Map.Entry)hrnItr.next();
3642 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3644 if( !hrn.isOutOfContext() &&
3646 hrn.getAlpha().isEmpty()
3648 System.out.println("!!! "+hrn+" has an empty ReachSet !!!");
3652 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3653 while( edgeItr.hasNext() ) {
3654 RefEdge edge = edgeItr.next();
3656 if( edge.getBeta().isEmpty() ) {
3657 System.out.println("!!! "+edge+" has an empty ReachSet !!!");
3667 public boolean everyReachStateWTrue() {
3669 Iterator hrnItr = id2hrn.entrySet().iterator();
3670 while( hrnItr.hasNext() ) {
3671 Map.Entry me = (Map.Entry)hrnItr.next();
3672 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3675 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3676 while( stateItr.hasNext() ) {
3677 ReachState state = stateItr.next();
3679 if( !state.getPreds().equals(predsTrue) ) {
3685 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3686 while( edgeItr.hasNext() ) {
3687 RefEdge edge = edgeItr.next();
3689 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3690 while( stateItr.hasNext() ) {
3691 ReachState state = stateItr.next();
3693 if( !state.getPreds().equals(predsTrue) ) {
3706 ////////////////////////////////////////////////////
3707 // in merge() and equals() methods the suffix A
3708 // represents the passed in graph and the suffix
3709 // B refers to the graph in this object
3710 // Merging means to take the incoming graph A and
3711 // merge it into B, so after the operation graph B
3712 // is the final result.
3713 ////////////////////////////////////////////////////
3714 protected void merge(ReachGraph rg) {
3722 mergeAllocSites(rg);
3723 mergeInaccessibleVars(rg);
3726 protected void mergeNodes(ReachGraph rg) {
3728 // start with heap region nodes
3729 Set sA = rg.id2hrn.entrySet();
3730 Iterator iA = sA.iterator();
3731 while( iA.hasNext() ) {
3732 Map.Entry meA = (Map.Entry)iA.next();
3733 Integer idA = (Integer) meA.getKey();
3734 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3736 // if this graph doesn't have a node the
3737 // incoming graph has, allocate it
3738 if( !id2hrn.containsKey(idA) ) {
3739 HeapRegionNode hrnB = hrnA.copy();
3740 id2hrn.put(idA, hrnB);
3743 // otherwise this is a node present in both graphs
3744 // so make the new reachability set a union of the
3745 // nodes' reachability sets
3746 HeapRegionNode hrnB = id2hrn.get(idA);
3747 hrnB.setAlpha(Canonical.unionORpreds(hrnB.getAlpha(),
3752 hrnB.setPreds(Canonical.join(hrnB.getPreds(),
3759 if( !hrnA.equals(hrnB) ) {
3760 rg.writeGraph("graphA");
3761 this.writeGraph("graphB");
3762 throw new Error("flagged not matching");
3770 // now add any variable nodes that are in graph B but
3772 sA = rg.td2vn.entrySet();
3774 while( iA.hasNext() ) {
3775 Map.Entry meA = (Map.Entry)iA.next();
3776 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3777 VariableNode lnA = (VariableNode) meA.getValue();
3779 // if the variable doesn't exist in B, allocate and add it
3780 VariableNode lnB = getVariableNodeFromTemp(tdA);
3784 protected void mergeRefEdges(ReachGraph rg) {
3786 // between heap regions
3787 Set sA = rg.id2hrn.entrySet();
3788 Iterator iA = sA.iterator();
3789 while( iA.hasNext() ) {
3790 Map.Entry meA = (Map.Entry)iA.next();
3791 Integer idA = (Integer) meA.getKey();
3792 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3794 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3795 while( heapRegionsItrA.hasNext() ) {
3796 RefEdge edgeA = heapRegionsItrA.next();
3797 HeapRegionNode hrnChildA = edgeA.getDst();
3798 Integer idChildA = hrnChildA.getID();
3800 // at this point we know an edge in graph A exists
3801 // idA -> idChildA, does this exist in B?
3802 assert id2hrn.containsKey(idA);
3803 HeapRegionNode hrnB = id2hrn.get(idA);
3804 RefEdge edgeToMerge = null;
3806 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3807 while( heapRegionsItrB.hasNext() &&
3808 edgeToMerge == null ) {
3810 RefEdge edgeB = heapRegionsItrB.next();
3811 HeapRegionNode hrnChildB = edgeB.getDst();
3812 Integer idChildB = hrnChildB.getID();
3814 // don't use the RefEdge.equals() here because
3815 // we're talking about existence between graphs,
3816 // not intragraph equal
3817 if( idChildB.equals(idChildA) &&
3818 edgeB.typeAndFieldEquals(edgeA) ) {
3820 edgeToMerge = edgeB;
3824 // if the edge from A was not found in B,
3826 if( edgeToMerge == null ) {
3827 assert id2hrn.containsKey(idChildA);
3828 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3829 edgeToMerge = edgeA.copy();
3830 edgeToMerge.setSrc(hrnB);
3831 edgeToMerge.setDst(hrnChildB);
3832 addRefEdge(hrnB, hrnChildB, edgeToMerge);
3834 // otherwise, the edge already existed in both graphs
3835 // so merge their reachability sets
3837 // just replace this beta set with the union
3838 assert edgeToMerge != null;
3839 edgeToMerge.setBeta(
3840 Canonical.unionORpreds(edgeToMerge.getBeta(),
3844 edgeToMerge.setPreds(
3845 Canonical.join(edgeToMerge.getPreds(),
3849 edgeToMerge.setTaints(
3850 Canonical.union(edgeToMerge.getTaints(),
3858 // and then again from variable nodes
3859 sA = rg.td2vn.entrySet();
3861 while( iA.hasNext() ) {
3862 Map.Entry meA = (Map.Entry)iA.next();
3863 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3864 VariableNode vnA = (VariableNode) meA.getValue();
3866 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3867 while( heapRegionsItrA.hasNext() ) {
3868 RefEdge edgeA = heapRegionsItrA.next();
3869 HeapRegionNode hrnChildA = edgeA.getDst();
3870 Integer idChildA = hrnChildA.getID();
3872 // at this point we know an edge in graph A exists
3873 // tdA -> idChildA, does this exist in B?
3874 assert td2vn.containsKey(tdA);
3875 VariableNode vnB = td2vn.get(tdA);
3876 RefEdge edgeToMerge = null;
3878 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3879 while( heapRegionsItrB.hasNext() &&
3880 edgeToMerge == null ) {
3882 RefEdge edgeB = heapRegionsItrB.next();
3883 HeapRegionNode hrnChildB = edgeB.getDst();
3884 Integer idChildB = hrnChildB.getID();
3886 // don't use the RefEdge.equals() here because
3887 // we're talking about existence between graphs
3888 if( idChildB.equals(idChildA) &&
3889 edgeB.typeAndFieldEquals(edgeA) ) {
3891 edgeToMerge = edgeB;
3895 // if the edge from A was not found in B,
3897 if( edgeToMerge == null ) {
3898 assert id2hrn.containsKey(idChildA);
3899 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3900 edgeToMerge = edgeA.copy();
3901 edgeToMerge.setSrc(vnB);
3902 edgeToMerge.setDst(hrnChildB);
3903 addRefEdge(vnB, hrnChildB, edgeToMerge);
3905 // otherwise, the edge already existed in both graphs
3906 // so merge their reachability sets
3908 // just replace this beta set with the union
3909 edgeToMerge.setBeta(Canonical.unionORpreds(edgeToMerge.getBeta(),
3913 edgeToMerge.setPreds(Canonical.join(edgeToMerge.getPreds(),
3917 edgeToMerge.setTaints(
3918 Canonical.union(edgeToMerge.getTaints(),
3927 protected void mergeAllocSites(ReachGraph rg) {
3928 allocSites.addAll(rg.allocSites);
3931 protected void mergeInaccessibleVars(ReachGraph rg) {
3932 inaccessibleVars.addAll(rg.inaccessibleVars);
3937 static boolean dbgEquals = false;
3940 // it is necessary in the equals() member functions
3941 // to "check both ways" when comparing the data
3942 // structures of two graphs. For instance, if all
3943 // edges between heap region nodes in graph A are
3944 // present and equal in graph B it is not sufficient
3945 // to say the graphs are equal. Consider that there
3946 // may be edges in graph B that are not in graph A.
3947 // the only way to know that all edges in both graphs
3948 // are equally present is to iterate over both data
3949 // structures and compare against the other graph.
3950 public boolean equals(ReachGraph rg) {
3954 System.out.println("rg is null");
3959 if( !areHeapRegionNodesEqual(rg) ) {
3961 System.out.println("hrn not equal");
3966 if( !areVariableNodesEqual(rg) ) {
3968 System.out.println("vars not equal");
3973 if( !areRefEdgesEqual(rg) ) {
3975 System.out.println("edges not equal");
3980 if( !inaccessibleVars.equals(rg.inaccessibleVars) ) {
3984 // if everything is equal up to this point,
3985 // assert that allocSites is also equal--
3986 // this data is redundant but kept for efficiency
3987 assert allocSites.equals(rg.allocSites);
3993 protected boolean areHeapRegionNodesEqual(ReachGraph rg) {
3995 if( !areallHRNinAalsoinBandequal(this, rg) ) {
3999 if( !areallHRNinAalsoinBandequal(rg, this) ) {
4006 static protected boolean areallHRNinAalsoinBandequal(ReachGraph rgA,
4008 Set sA = rgA.id2hrn.entrySet();
4009 Iterator iA = sA.iterator();
4010 while( iA.hasNext() ) {
4011 Map.Entry meA = (Map.Entry)iA.next();
4012 Integer idA = (Integer) meA.getKey();
4013 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4015 if( !rgB.id2hrn.containsKey(idA) ) {
4019 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4020 if( !hrnA.equalsIncludingAlphaAndPreds(hrnB) ) {
4028 protected boolean areVariableNodesEqual(ReachGraph rg) {
4030 if( !areallVNinAalsoinBandequal(this, rg) ) {
4034 if( !areallVNinAalsoinBandequal(rg, this) ) {
4041 static protected boolean areallVNinAalsoinBandequal(ReachGraph rgA,
4043 Set sA = rgA.td2vn.entrySet();
4044 Iterator iA = sA.iterator();
4045 while( iA.hasNext() ) {
4046 Map.Entry meA = (Map.Entry)iA.next();
4047 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4049 if( !rgB.td2vn.containsKey(tdA) ) {
4058 protected boolean areRefEdgesEqual(ReachGraph rg) {
4059 if( !areallREinAandBequal(this, rg) ) {
4063 if( !areallREinAandBequal(rg, this) ) {
4070 static protected boolean areallREinAandBequal(ReachGraph rgA,
4073 // check all the heap region->heap region edges
4074 Set sA = rgA.id2hrn.entrySet();
4075 Iterator iA = sA.iterator();
4076 while( iA.hasNext() ) {
4077 Map.Entry meA = (Map.Entry)iA.next();
4078 Integer idA = (Integer) meA.getKey();
4079 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4081 // we should have already checked that the same
4082 // heap regions exist in both graphs
4083 assert rgB.id2hrn.containsKey(idA);
4085 if( !areallREfromAequaltoB(rgA, hrnA, rgB) ) {
4089 // then check every edge in B for presence in A, starting
4090 // from the same parent HeapRegionNode
4091 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4093 if( !areallREfromAequaltoB(rgB, hrnB, rgA) ) {
4098 // then check all the variable->heap region edges
4099 sA = rgA.td2vn.entrySet();
4101 while( iA.hasNext() ) {
4102 Map.Entry meA = (Map.Entry)iA.next();
4103 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4104 VariableNode vnA = (VariableNode) meA.getValue();
4106 // we should have already checked that the same
4107 // label nodes exist in both graphs
4108 assert rgB.td2vn.containsKey(tdA);
4110 if( !areallREfromAequaltoB(rgA, vnA, rgB) ) {
4114 // then check every edge in B for presence in A, starting
4115 // from the same parent VariableNode
4116 VariableNode vnB = rgB.td2vn.get(tdA);
4118 if( !areallREfromAequaltoB(rgB, vnB, rgA) ) {
4127 static protected boolean areallREfromAequaltoB(ReachGraph rgA,
4131 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4132 while( itrA.hasNext() ) {
4133 RefEdge edgeA = itrA.next();
4134 HeapRegionNode hrnChildA = edgeA.getDst();
4135 Integer idChildA = hrnChildA.getID();
4137 assert rgB.id2hrn.containsKey(idChildA);
4139 // at this point we know an edge in graph A exists
4140 // rnA -> idChildA, does this exact edge exist in B?
4141 boolean edgeFound = false;
4143 RefSrcNode rnB = null;
4144 if( rnA instanceof HeapRegionNode ) {
4145 HeapRegionNode hrnA = (HeapRegionNode) rnA;
4146 rnB = rgB.id2hrn.get(hrnA.getID() );
4148 VariableNode vnA = (VariableNode) rnA;
4149 rnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4152 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4153 while( itrB.hasNext() ) {
4154 RefEdge edgeB = itrB.next();
4155 HeapRegionNode hrnChildB = edgeB.getDst();
4156 Integer idChildB = hrnChildB.getID();
4158 if( idChildA.equals(idChildB) &&
4159 edgeA.typeAndFieldEquals(edgeB) ) {
4161 // there is an edge in the right place with the right field,
4162 // but do they have the same attributes?
4163 if( edgeA.getBeta().equals(edgeB.getBeta() ) &&
4164 edgeA.equalsPreds(edgeB)
4180 // can be used to assert monotonicity
4181 static public boolean isNoSmallerThan(ReachGraph rgA,
4184 //System.out.println( "*** Asking if A is no smaller than B ***" );
4186 Iterator iA = rgA.id2hrn.entrySet().iterator();
4187 while( iA.hasNext() ) {
4188 Map.Entry meA = (Map.Entry)iA.next();
4189 Integer idA = (Integer) meA.getKey();
4190 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4192 if( !rgB.id2hrn.containsKey(idA) ) {
4193 System.out.println(" regions smaller");
4198 // this works just fine, no smaller than
4199 if( !areallVNinAalsoinBandequal(rgA, rgB) ) {
4200 System.out.println(" vars smaller:");
4201 System.out.println(" A:"+rgA.td2vn.keySet() );
4202 System.out.println(" B:"+rgB.td2vn.keySet() );
4207 iA = rgA.id2hrn.entrySet().iterator();
4208 while( iA.hasNext() ) {
4209 Map.Entry meA = (Map.Entry)iA.next();
4210 Integer idA = (Integer) meA.getKey();
4211 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4213 Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4214 while( reItr.hasNext() ) {
4215 RefEdge edgeA = reItr.next();
4216 RefSrcNode rsnA = edgeA.getSrc();
4218 // we already checked that nodes were present
4219 HeapRegionNode hrnB = rgB.id2hrn.get(hrnA.getID() );
4220 assert hrnB != null;
4223 if( rsnA instanceof VariableNode ) {
4224 VariableNode vnA = (VariableNode) rsnA;
4225 rsnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4228 HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4229 rsnB = rgB.id2hrn.get(hrnSrcA.getID() );
4231 assert rsnB != null;
4233 RefEdge edgeB = rsnB.getReferenceTo(hrnB,
4237 if( edgeB == null ) {
4238 System.out.println(" edges smaller:");
4252 // this analysis no longer has the "match anything"
4253 // type which was represented by null
4254 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4255 TypeDescriptor td2) {
4259 if( td1.isNull() ) {
4262 if( td2.isNull() ) {
4265 return typeUtil.mostSpecific(td1, td2);
4268 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4270 TypeDescriptor td3) {
4272 return mostSpecificType(td1,
4273 mostSpecificType(td2, td3)
4277 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4280 TypeDescriptor td4) {
4282 return mostSpecificType(mostSpecificType(td1, td2),
4283 mostSpecificType(td3, td4)
4287 protected boolean isSuperiorType(TypeDescriptor possibleSuper,
4288 TypeDescriptor possibleChild) {
4289 assert possibleSuper != null;
4290 assert possibleChild != null;
4292 if( possibleSuper.isNull() ||
4293 possibleChild.isNull() ) {
4297 return typeUtil.isSuperorType(possibleSuper, possibleChild);
4301 protected boolean hasMatchingField(HeapRegionNode src,
4304 TypeDescriptor tdSrc = src.getType();
4305 assert tdSrc != null;
4307 if( tdSrc.isArray() ) {
4308 TypeDescriptor td = edge.getType();
4311 TypeDescriptor tdSrcDeref = tdSrc.dereference();
4312 assert tdSrcDeref != null;
4314 if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
4318 return edge.getField().equals(DisjointAnalysis.arrayElementFieldName);
4321 // if it's not a class, it doesn't have any fields to match
4322 if( !tdSrc.isClass() ) {
4326 ClassDescriptor cd = tdSrc.getClassDesc();
4327 while( cd != null ) {
4328 Iterator fieldItr = cd.getFields();
4330 while( fieldItr.hasNext() ) {
4331 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4333 if( fd.getType().equals(edge.getType() ) &&
4334 fd.getSymbol().equals(edge.getField() ) ) {
4339 cd = cd.getSuperDesc();
4342 // otherwise it is a class with fields
4343 // but we didn't find a match
4347 protected boolean hasMatchingType(RefEdge edge,
4348 HeapRegionNode dst) {
4350 // if the region has no type, matches everything
4351 TypeDescriptor tdDst = dst.getType();
4352 assert tdDst != null;
4354 // if the type is not a class or an array, don't
4355 // match because primitives are copied, no aliases
4356 ClassDescriptor cdDst = tdDst.getClassDesc();
4357 if( cdDst == null && !tdDst.isArray() ) {
4361 // if the edge type is null, it matches everything
4362 TypeDescriptor tdEdge = edge.getType();
4363 assert tdEdge != null;
4365 return typeUtil.isSuperorType(tdEdge, tdDst);
4370 // the default signature for quick-and-dirty debugging
4371 public void writeGraph(String graphName) {
4372 writeGraph(graphName,
4373 true, // write labels
4374 true, // label select
4375 true, // prune garbage
4376 false, // hide reachability
4377 true, // hide subset reachability
4378 true, // hide predicates
4379 false, // hide edge taints
4380 null // in-context boundary
4384 public void writeGraph(String graphName,
4385 boolean writeLabels,
4386 boolean labelSelect,
4387 boolean pruneGarbage,
4388 boolean hideReachability,
4389 boolean hideSubsetReachability,
4390 boolean hidePredicates,
4391 boolean hideEdgeTaints
4393 writeGraph(graphName,
4398 hideSubsetReachability,
4404 public void writeGraph(String graphName,
4405 boolean writeLabels,
4406 boolean labelSelect,
4407 boolean pruneGarbage,
4408 boolean hideReachability,
4409 boolean hideSubsetReachability,
4410 boolean hidePredicates,
4411 boolean hideEdgeTaints,
4412 Set<Integer> callerNodeIDsCopiedToCallee
4415 // remove all non-word characters from the graph name so
4416 // the filename and identifier in dot don't cause errors
4417 // jjenista - also replace underscore '_' to prevent some
4418 // really, really long names from IHMS debugging
4419 graphName = graphName.replaceAll("[\\W_]", "");
4422 new BufferedWriter(new FileWriter(graphName+".dot") );
4424 bw.write("digraph "+graphName+" {\n");
4427 // this is an optional step to form the callee-reachable
4428 // "cut-out" into a DOT cluster for visualization
4429 if( callerNodeIDsCopiedToCallee != null ) {
4431 bw.write(" subgraph cluster0 {\n");
4432 bw.write(" color=blue;\n");
4434 Iterator i = id2hrn.entrySet().iterator();
4435 while( i.hasNext() ) {
4436 Map.Entry me = (Map.Entry)i.next();
4437 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4439 if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4442 hrn.toStringDOT(hideReachability,
4443 hideSubsetReachability,
4453 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4455 // then visit every heap region node
4456 Iterator i = id2hrn.entrySet().iterator();
4457 while( i.hasNext() ) {
4458 Map.Entry me = (Map.Entry)i.next();
4459 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4461 // only visit nodes worth writing out--for instance
4462 // not every node at an allocation is referenced
4463 // (think of it as garbage-collected), etc.
4464 if( !pruneGarbage ||
4465 hrn.isOutOfContext() ||
4466 (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4469 if( !visited.contains(hrn) ) {
4470 traverseHeapRegionNodes(hrn,
4475 hideSubsetReachability,
4478 callerNodeIDsCopiedToCallee);
4483 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4486 // then visit every label node, useful for debugging
4488 i = td2vn.entrySet().iterator();
4489 while( i.hasNext() ) {
4490 Map.Entry me = (Map.Entry)i.next();
4491 VariableNode vn = (VariableNode) me.getValue();
4494 String labelStr = vn.getTempDescriptorString();
4495 if( labelStr.startsWith("___temp") ||
4496 labelStr.startsWith("___dst") ||
4497 labelStr.startsWith("___srctmp") ||
4498 labelStr.startsWith("___neverused")
4504 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4505 while( heapRegionsItr.hasNext() ) {
4506 RefEdge edge = heapRegionsItr.next();
4507 HeapRegionNode hrn = edge.getDst();
4509 if( !visited.contains(hrn) ) {
4510 traverseHeapRegionNodes(hrn,
4515 hideSubsetReachability,
4518 callerNodeIDsCopiedToCallee);
4521 bw.write(" "+vn.toString()+
4522 " -> "+hrn.toString()+
4523 edge.toStringDOT(hideReachability,
4524 hideSubsetReachability,
4536 } catch( IOException e ) {
4537 throw new Error("Error writing out DOT graph "+graphName);
4542 traverseHeapRegionNodes(HeapRegionNode hrn,
4545 Set<HeapRegionNode> visited,
4546 boolean hideReachability,
4547 boolean hideSubsetReachability,
4548 boolean hidePredicates,
4549 boolean hideEdgeTaints,
4550 Set<Integer> callerNodeIDsCopiedToCallee
4551 ) throws java.io.IOException {
4553 if( visited.contains(hrn) ) {
4558 // if we're drawing the callee-view subgraph, only
4559 // write out the node info if it hasn't already been
4561 if( callerNodeIDsCopiedToCallee == null ||
4562 !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4566 hrn.toStringDOT(hideReachability,
4567 hideSubsetReachability,
4572 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4573 while( childRegionsItr.hasNext() ) {
4574 RefEdge edge = childRegionsItr.next();
4575 HeapRegionNode hrnChild = edge.getDst();
4577 if( callerNodeIDsCopiedToCallee != null &&
4578 (edge.getSrc() instanceof HeapRegionNode) ) {
4579 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4580 if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4581 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4583 bw.write(" "+hrn.toString()+
4584 " -> "+hrnChild.toString()+
4585 edge.toStringDOT(hideReachability,
4586 hideSubsetReachability,
4591 } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4592 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4594 bw.write(" "+hrn.toString()+
4595 " -> "+hrnChild.toString()+
4596 edge.toStringDOT(hideReachability,
4597 hideSubsetReachability,
4600 ",color=blue,style=dashed")+
4603 bw.write(" "+hrn.toString()+
4604 " -> "+hrnChild.toString()+
4605 edge.toStringDOT(hideReachability,
4606 hideSubsetReachability,
4613 bw.write(" "+hrn.toString()+
4614 " -> "+hrnChild.toString()+
4615 edge.toStringDOT(hideReachability,
4616 hideSubsetReachability,
4623 traverseHeapRegionNodes(hrnChild,
4628 hideSubsetReachability,
4631 callerNodeIDsCopiedToCallee);
4640 // return the set of heap regions from the given allocation
4641 // site, if any, that exist in this graph
4642 protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4644 Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4646 Integer idSum = as.getSummary();
4647 if( id2hrn.containsKey(idSum) ) {
4648 out.add(id2hrn.get(idSum) );
4651 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4652 Integer idI = as.getIthOldest(i);
4653 if( id2hrn.containsKey(idI) ) {
4654 out.add(id2hrn.get(idI) );
4661 // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4662 // from the given allocation site, if any, from regions for that
4663 // site that exist in this graph
4664 protected Set<ReachTuple> getAnyExisting(AllocSite as,
4665 boolean includeARITY_ZEROORMORE,
4666 boolean includeARITY_ONE) {
4668 Set<ReachTuple> out = new HashSet<ReachTuple>();
4670 Integer idSum = as.getSummary();
4671 if( id2hrn.containsKey(idSum) ) {
4673 HeapRegionNode hrn = id2hrn.get(idSum);
4674 assert !hrn.isOutOfContext();
4676 if( !includeARITY_ZEROORMORE ) {
4677 out.add(ReachTuple.factory(hrn.getID(),
4678 true, // multi-obj region
4679 ReachTuple.ARITY_ZEROORMORE,
4684 if( includeARITY_ONE ) {
4685 out.add(ReachTuple.factory(hrn.getID(),
4686 true, // multi-object region
4687 ReachTuple.ARITY_ONE,
4693 if( !includeARITY_ONE ) {
4694 // no need to do the single-object regions that
4695 // only have an ARITY ONE possible
4699 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4701 Integer idI = as.getIthOldest(i);
4702 if( id2hrn.containsKey(idI) ) {
4704 HeapRegionNode hrn = id2hrn.get(idI);
4705 assert !hrn.isOutOfContext();
4707 out.add(ReachTuple.factory(hrn.getID(),
4708 false, // multi-object region
4709 ReachTuple.ARITY_ONE,
4719 // if an object allocated at the target site may be
4720 // reachable from both an object from root1 and an
4721 // object allocated at root2, return TRUE
4722 public boolean mayBothReachTarget(AllocSite asRoot1,
4724 AllocSite asTarget) {
4726 // consider all heap regions of the target and look
4727 // for a reach state that indicates regions of root1
4728 // and root2 might be able to reach same object
4729 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4731 // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4732 Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4733 Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4735 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4736 while( hrnItr.hasNext() ) {
4737 HeapRegionNode hrn = hrnItr.next();
4739 Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4740 while( rtItr1.hasNext() ) {
4741 ReachTuple rt1 = rtItr1.next();
4743 Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4744 while( rtItr2.hasNext() ) {
4745 ReachTuple rt2 = rtItr2.next();
4747 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4757 // similar to the method above, return TRUE if ever
4758 // more than one object from the root allocation site
4759 // may reach an object from the target site
4760 public boolean mayManyReachTarget(AllocSite asRoot,
4761 AllocSite asTarget) {
4763 // consider all heap regions of the target and look
4764 // for a reach state that multiple objects of root
4765 // might be able to reach the same object
4766 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4768 // get relevant reach tuples
4769 Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true, false);
4770 Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4772 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4773 while( hrnItr.hasNext() ) {
4774 HeapRegionNode hrn = hrnItr.next();
4776 // if any ZERORMORE tuples are here, TRUE
4777 Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4778 while( rtItr.hasNext() ) {
4779 ReachTuple rtZOM = rtItr.next();
4781 if( hrn.getAlpha().containsTuple(rtZOM) ) {
4786 // otherwise, look for any pair of ONE tuples
4787 Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4788 while( rtItr1.hasNext() ) {
4789 ReachTuple rt1 = rtItr1.next();
4791 Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4792 while( rtItr2.hasNext() ) {
4793 ReachTuple rt2 = rtItr2.next();
4799 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4813 public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4815 Set<HeapRegionNode> exhibitProofState =
4816 new HashSet<HeapRegionNode>();
4818 Iterator hrnItr = id2hrn.entrySet().iterator();
4819 while( hrnItr.hasNext() ) {
4820 Map.Entry me = (Map.Entry)hrnItr.next();
4821 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4823 ReachSet intersection =
4824 Canonical.intersection(proofOfSharing,
4827 if( !intersection.isEmpty() ) {
4828 assert !hrn.isOutOfContext();
4829 exhibitProofState.add(hrn);
4833 return exhibitProofState;
4837 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4838 HeapRegionNode hrn2) {
4839 assert hrn1 != null;
4840 assert hrn2 != null;
4842 assert !hrn1.isOutOfContext();
4843 assert !hrn2.isOutOfContext();
4845 assert belongsToThis(hrn1);
4846 assert belongsToThis(hrn2);
4848 assert !hrn1.getID().equals(hrn2.getID() );
4851 // then get the various tokens for these heap regions
4853 ReachTuple.factory(hrn1.getID(),
4854 !hrn1.isSingleObject(), // multi?
4855 ReachTuple.ARITY_ONE,
4858 ReachTuple h1star = null;
4859 if( !hrn1.isSingleObject() ) {
4861 ReachTuple.factory(hrn1.getID(),
4862 !hrn1.isSingleObject(),
4863 ReachTuple.ARITY_ZEROORMORE,
4868 ReachTuple.factory(hrn2.getID(),
4869 !hrn2.isSingleObject(),
4870 ReachTuple.ARITY_ONE,
4873 ReachTuple h2star = null;
4874 if( !hrn2.isSingleObject() ) {
4876 ReachTuple.factory(hrn2.getID(),
4877 !hrn2.isSingleObject(),
4878 ReachTuple.ARITY_ZEROORMORE,
4882 // then get the merged beta of all out-going edges from these heap
4885 ReachSet beta1 = ReachSet.factory();
4886 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4887 while (itrEdge.hasNext()) {
4888 RefEdge edge = itrEdge.next();
4889 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4892 ReachSet beta2 = ReachSet.factory();
4893 itrEdge = hrn2.iteratorToReferencees();
4894 while (itrEdge.hasNext()) {
4895 RefEdge edge = itrEdge.next();
4896 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4899 ReachSet proofOfSharing = ReachSet.factory();
4902 Canonical.unionORpreds(proofOfSharing,
4903 beta1.getStatesWithBoth(h1, h2)
4906 Canonical.unionORpreds(proofOfSharing,
4907 beta2.getStatesWithBoth(h1, h2)
4910 if( !hrn1.isSingleObject() ) {
4912 Canonical.unionORpreds(proofOfSharing,
4913 beta1.getStatesWithBoth(h1star, h2)
4916 Canonical.unionORpreds(proofOfSharing,
4917 beta2.getStatesWithBoth(h1star, h2)
4921 if( !hrn2.isSingleObject() ) {
4923 Canonical.unionORpreds(proofOfSharing,
4924 beta1.getStatesWithBoth(h1, h2star)
4927 Canonical.unionORpreds(proofOfSharing,
4928 beta2.getStatesWithBoth(h1, h2star)
4932 if( !hrn1.isSingleObject() &&
4933 !hrn2.isSingleObject()
4936 Canonical.unionORpreds(proofOfSharing,
4937 beta1.getStatesWithBoth(h1star, h2star)
4940 Canonical.unionORpreds(proofOfSharing,
4941 beta2.getStatesWithBoth(h1star, h2star)
4945 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4946 if( !proofOfSharing.isEmpty() ) {
4947 common = findCommonReachableNodes(proofOfSharing);
4948 if( !DISABLE_STRONG_UPDATES &&
4949 !DISABLE_GLOBAL_SWEEP
4951 assert !common.isEmpty();
4958 // this version of the above method checks whether there is sharing
4959 // among the objects in a summary node
4960 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4962 assert hrn.isNewSummary();
4963 assert !hrn.isOutOfContext();
4964 assert belongsToThis(hrn);
4967 ReachTuple.factory(hrn.getID(),
4969 ReachTuple.ARITY_ZEROORMORE,
4972 // then get the merged beta of all out-going edges from
4975 ReachSet beta = ReachSet.factory();
4976 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4977 while (itrEdge.hasNext()) {
4978 RefEdge edge = itrEdge.next();
4979 beta = Canonical.unionORpreds(beta, edge.getBeta());
4982 ReachSet proofOfSharing = ReachSet.factory();
4985 Canonical.unionORpreds(proofOfSharing,
4986 beta.getStatesWithBoth(hstar, hstar)
4989 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4990 if( !proofOfSharing.isEmpty() ) {
4991 common = findCommonReachableNodes(proofOfSharing);
4992 if( !DISABLE_STRONG_UPDATES &&
4993 !DISABLE_GLOBAL_SWEEP
4995 assert !common.isEmpty();
5003 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5004 Integer paramIndex1,
5005 Integer paramIndex2) {
5007 // get parameter's heap regions
5008 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5009 assert this.hasVariable(paramTemp1);
5010 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5013 if( !(paramVar1.getNumReferencees() == 1) ) {
5014 System.out.println("\n fm="+fm+"\n param="+paramTemp1);
5015 writeGraph("whatup");
5019 assert paramVar1.getNumReferencees() == 1;
5020 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5021 HeapRegionNode hrnParam1 = paramEdge1.getDst();
5023 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5024 assert this.hasVariable(paramTemp2);
5025 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5027 if( !(paramVar2.getNumReferencees() == 1) ) {
5028 System.out.println("\n fm="+fm+"\n param="+paramTemp2);
5029 writeGraph("whatup");
5032 assert paramVar2.getNumReferencees() == 1;
5033 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5034 HeapRegionNode hrnParam2 = paramEdge2.getDst();
5036 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5037 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5042 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5046 // get parameter's heap regions
5047 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5048 assert this.hasVariable(paramTemp);
5049 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5050 assert paramVar.getNumReferencees() == 1;
5051 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5052 HeapRegionNode hrnParam = paramEdge.getDst();
5055 HeapRegionNode hrnSummary=null;
5056 if(id2hrn.containsKey(as.getSummary())) {
5057 // if summary node doesn't exist, ignore this case
5058 hrnSummary = id2hrn.get(as.getSummary());
5059 assert hrnSummary != null;
5062 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5063 if(hrnSummary!=null) {
5064 common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5067 // check for other nodes
5068 for (int i = 0; i < as.getAllocationDepth(); ++i) {
5070 assert id2hrn.containsKey(as.getIthOldest(i));
5071 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5072 assert hrnIthOldest != null;
5074 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5081 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5084 // get summary node 1's alpha
5085 Integer idSum1 = as1.getSummary();
5086 HeapRegionNode hrnSum1=null;
5087 if(id2hrn.containsKey(idSum1)) {
5088 hrnSum1 = id2hrn.get(idSum1);
5091 // get summary node 2's alpha
5092 Integer idSum2 = as2.getSummary();
5093 HeapRegionNode hrnSum2=null;
5094 if(id2hrn.containsKey(idSum2)) {
5095 hrnSum2 = id2hrn.get(idSum2);
5098 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5099 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5100 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5104 // ask if objects from this summary share among each other
5105 common.addAll(mayReachSharedObjects(hrnSum1));
5108 // check sum2 against alloc1 nodes
5110 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5111 Integer idI1 = as1.getIthOldest(i);
5112 assert id2hrn.containsKey(idI1);
5113 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5114 assert hrnI1 != null;
5115 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5118 // also ask if objects from this summary share among each other
5119 common.addAll(mayReachSharedObjects(hrnSum2));
5122 // check sum1 against alloc2 nodes
5123 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5124 Integer idI2 = as2.getIthOldest(i);
5125 assert id2hrn.containsKey(idI2);
5126 HeapRegionNode hrnI2 = id2hrn.get(idI2);
5127 assert hrnI2 != null;
5130 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5133 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5134 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5135 Integer idI1 = as1.getIthOldest(j);
5137 // if these are the same site, don't look for the same token, no
5139 // different tokens of the same site could alias together though
5140 if (idI1.equals(idI2)) {
5144 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5146 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5153 public void makeInaccessible(Set<TempDescriptor> vars) {
5154 inaccessibleVars.addAll(vars);
5157 public void makeInaccessible(TempDescriptor td) {
5158 inaccessibleVars.add(td);
5161 public void makeAccessible(TempDescriptor td) {
5162 inaccessibleVars.remove(td);
5165 public boolean isAccessible(TempDescriptor td) {
5166 return !inaccessibleVars.contains(td);
5169 public Set<TempDescriptor> getInaccessibleVars() {
5170 return inaccessibleVars;
5176 public Set<Alloc> canPointTo( TempDescriptor x ) {
5178 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5179 // if we don't care to track it, return null which means
5180 // "a client of this result shouldn't care either"
5181 return HeapAnalysis.DONTCARE_PTR;
5184 Set<Alloc> out = new HashSet<Alloc>();
5186 VariableNode vn = getVariableNodeNoMutation( x );
5188 // the empty set means "can't point to anything"
5192 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5193 while( edgeItr.hasNext() ) {
5194 HeapRegionNode hrn = edgeItr.next().getDst();
5195 out.add( hrn.getAllocSite() );
5203 public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5205 TypeDescriptor fieldType ) {
5207 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5208 // if we don't care to track it, return null which means
5209 // "a client of this result shouldn't care either"
5210 return HeapAnalysis.DONTCARE_DREF;
5213 Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5215 VariableNode vn = getVariableNodeNoMutation( x );
5217 // the empty table means "x can't point to anything"
5221 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5222 while( edgeItr.hasNext() ) {
5223 HeapRegionNode hrn = edgeItr.next().getDst();
5224 Alloc key = hrn.getAllocSite();
5226 if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5227 // if we don't care to track it, put no entry which means
5228 // "a client of this result shouldn't care either"
5229 out.put( key, HeapAnalysis.DONTCARE_PTR );
5233 Set<Alloc> moreValues = new HashSet<Alloc>();
5234 Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5235 while( edgeItr2.hasNext() ) {
5236 RefEdge edge = edgeItr2.next();
5238 if( field.equals( edge.getField() ) ) {
5239 moreValues.add( edge.getDst().getAllocSite() );
5243 if( out.containsKey( key ) ) {
5244 out.get( key ).addAll( moreValues );
5246 out.put( key, moreValues );
5256 public TempDescriptor findVariableByName( String name ) {
5258 for( TempDescriptor td: td2vn.keySet() ) {
5259 if( td.getSymbol().contains( name ) ) {