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( Canonical.changePredsTo( hrn0.getInherent(), predsTrue ) );
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 // NOTE! One argument may be passed in as more than one parameter,
1790 // so map to a set of parameter indices!
1791 Hashtable< RefEdge, Set<Integer> > reachableCallerArgEdges2paramIndices =
1792 new Hashtable< RefEdge, Set<Integer> >();
1794 // caller edges from local vars or callee-unreachable nodes
1795 // (out-of-context sources) to callee-reachable nodes
1796 Set<RefEdge> oocCallerEdges =
1797 new HashSet<RefEdge>();
1800 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1802 TempDescriptor tdArg = fc.getArgMatchingParamIndex(fmCallee, i);
1803 VariableNode vnArgCaller = this.getVariableNodeFromTemp(tdArg);
1805 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1806 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1808 toVisitInCaller.add(vnArgCaller);
1810 while( !toVisitInCaller.isEmpty() ) {
1811 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1812 toVisitInCaller.remove(rsnCaller);
1813 visitedInCaller.add(rsnCaller);
1815 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1816 while( itrRefEdges.hasNext() ) {
1817 RefEdge reCaller = itrRefEdges.next();
1818 HeapRegionNode hrnCaller = reCaller.getDst();
1820 callerNodeIDsCopiedToCallee.add(hrnCaller.getID() );
1821 reachableCallerNodes.add(hrnCaller);
1823 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1824 reachableCallerEdges.add(reCaller);
1827 if( rsnCaller.equals(vnArgCaller) ) {
1828 Set<Integer> pIndices =
1829 reachableCallerArgEdges2paramIndices.get( reCaller );
1831 if( pIndices == null ) {
1832 pIndices = new HashSet<Integer>();
1833 reachableCallerArgEdges2paramIndices.put( reCaller, pIndices );
1838 oocCallerEdges.add(reCaller);
1842 if( !visitedInCaller.contains(hrnCaller) ) {
1843 toVisitInCaller.add(hrnCaller);
1846 } // end edge iteration
1847 } // end visiting heap nodes in caller
1848 } // end iterating over parameters as starting points
1852 // now collect out-of-callee-context IDs and
1853 // map them to whether the ID is out of the caller
1855 Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1857 Iterator<Integer> itrInContext =
1858 callerNodeIDsCopiedToCallee.iterator();
1859 while( itrInContext.hasNext() ) {
1860 Integer hrnID = itrInContext.next();
1861 HeapRegionNode hrnCallerAndInContext = id2hrn.get(hrnID);
1863 Iterator<RefEdge> itrMightCross =
1864 hrnCallerAndInContext.iteratorToReferencers();
1865 while( itrMightCross.hasNext() ) {
1866 RefEdge edgeMightCross = itrMightCross.next();
1868 RefSrcNode rsnCallerAndOutContext =
1869 edgeMightCross.getSrc();
1871 if( rsnCallerAndOutContext instanceof VariableNode ) {
1872 // variables do not have out-of-context reach states,
1874 oocCallerEdges.add(edgeMightCross);
1878 HeapRegionNode hrnCallerAndOutContext =
1879 (HeapRegionNode) rsnCallerAndOutContext;
1881 // is this source node out-of-context?
1882 if( callerNodeIDsCopiedToCallee.contains(hrnCallerAndOutContext.getID() ) ) {
1883 // no, skip this edge
1888 oocCallerEdges.add(edgeMightCross);
1890 // add all reach tuples on the node to list
1891 // of things that are out-of-context: insight
1892 // if this node is reachable from someting that WAS
1893 // in-context, then this node should already be in-context
1894 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1895 while( stateItr.hasNext() ) {
1896 ReachState state = stateItr.next();
1898 Iterator<ReachTuple> rtItr = state.iterator();
1899 while( rtItr.hasNext() ) {
1900 ReachTuple rt = rtItr.next();
1902 oocHrnIdOoc2callee.add(new HrnIdOoc(rt.getHrnID(),
1911 // the callee view is a new graph: DON'T MODIFY *THIS* graph
1912 ReachGraph rg = new ReachGraph();
1914 // add nodes to callee graph
1915 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1916 while( hrnItr.hasNext() ) {
1917 HeapRegionNode hrnCaller = hrnItr.next();
1919 assert callerNodeIDsCopiedToCallee.contains(hrnCaller.getID() );
1920 assert !rg.id2hrn.containsKey(hrnCaller.getID() );
1922 ExistPred pred = ExistPred.factory(hrnCaller.getID(), null);
1923 ExistPredSet preds = ExistPredSet.factory(pred);
1925 rg.createNewHeapRegionNode(hrnCaller.getID(),
1926 hrnCaller.isSingleObject(),
1927 hrnCaller.isNewSummary(),
1928 false, // out-of-context?
1929 hrnCaller.getType(),
1930 hrnCaller.getAllocSite(),
1931 toCalleeContext(hrnCaller.getInherent(),
1935 toCalleeContext(hrnCaller.getAlpha(),
1940 hrnCaller.getDescription()
1944 // add param edges to callee graph
1946 reachableCallerArgEdges2paramIndices.entrySet().iterator();
1947 while( argEdges.hasNext() ) {
1948 Map.Entry me = (Map.Entry) argEdges.next();
1949 RefEdge reArg = (RefEdge) me.getKey();
1950 Set<Integer> pInxs = (Set<Integer>) me.getValue();
1952 VariableNode vnCaller = (VariableNode) reArg.getSrc();
1953 TempDescriptor argCaller = vnCaller.getTempDescriptor();
1955 HeapRegionNode hrnDstCaller = reArg.getDst();
1956 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
1957 assert hrnDstCallee != null;
1960 ExistPred.factory(argCaller,
1962 hrnDstCallee.getID(),
1967 true, // out-of-callee-context
1968 false // out-of-caller-context
1971 ExistPredSet preds =
1972 ExistPredSet.factory(pred);
1974 for( Integer index: pInxs ) {
1976 TempDescriptor paramCallee = fmCallee.getParameter(index);
1977 VariableNode vnCallee = rg.getVariableNodeFromTemp(paramCallee);
1980 new RefEdge(vnCallee,
1984 toCalleeContext(reArg.getBeta(),
1989 toCalleeContext(reArg.getTaints(),
1993 rg.addRefEdge(vnCallee,
2000 // add in-context edges to callee graph
2001 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
2002 while( reItr.hasNext() ) {
2003 RefEdge reCaller = reItr.next();
2004 RefSrcNode rsnCaller = reCaller.getSrc();
2005 assert rsnCaller instanceof HeapRegionNode;
2006 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2007 HeapRegionNode hrnDstCaller = reCaller.getDst();
2009 HeapRegionNode hrnSrcCallee = rg.id2hrn.get(hrnSrcCaller.getID() );
2010 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2011 assert hrnSrcCallee != null;
2012 assert hrnDstCallee != null;
2015 ExistPred.factory(null,
2016 hrnSrcCallee.getID(),
2017 hrnDstCallee.getID(),
2019 reCaller.getField(),
2022 false, // out-of-callee-context
2023 false // out-of-caller-context
2026 ExistPredSet preds =
2027 ExistPredSet.factory(pred);
2030 new RefEdge(hrnSrcCallee,
2033 reCaller.getField(),
2034 toCalleeContext(reCaller.getBeta(),
2039 toCalleeContext(reCaller.getTaints(),
2043 rg.addRefEdge(hrnSrcCallee,
2049 // add out-of-context edges to callee graph
2050 reItr = oocCallerEdges.iterator();
2051 while( reItr.hasNext() ) {
2052 RefEdge reCaller = reItr.next();
2053 RefSrcNode rsnCaller = reCaller.getSrc();
2054 HeapRegionNode hrnDstCaller = reCaller.getDst();
2055 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2056 assert hrnDstCallee != null;
2058 TypeDescriptor oocNodeType;
2060 TempDescriptor oocPredSrcTemp = null;
2061 Integer oocPredSrcID = null;
2062 boolean outOfCalleeContext;
2063 boolean outOfCallerContext;
2065 if( rsnCaller instanceof VariableNode ) {
2066 VariableNode vnCaller = (VariableNode) rsnCaller;
2068 oocReach = rsetEmpty;
2069 oocPredSrcTemp = vnCaller.getTempDescriptor();
2070 outOfCalleeContext = true;
2071 outOfCallerContext = false;
2074 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2075 assert !callerNodeIDsCopiedToCallee.contains(hrnSrcCaller.getID() );
2076 oocNodeType = hrnSrcCaller.getType();
2077 oocReach = hrnSrcCaller.getAlpha();
2078 oocPredSrcID = hrnSrcCaller.getID();
2079 if( hrnSrcCaller.isOutOfContext() ) {
2080 outOfCalleeContext = false;
2081 outOfCallerContext = true;
2083 outOfCalleeContext = true;
2084 outOfCallerContext = false;
2089 ExistPred.factory(oocPredSrcTemp,
2091 hrnDstCallee.getID(),
2093 reCaller.getField(),
2100 ExistPredSet preds =
2101 ExistPredSet.factory(pred);
2103 RefEdge oocEdgeExisting =
2104 rg.getOutOfContextReferenceTo(hrnDstCallee,
2110 if( oocEdgeExisting == null ) {
2111 // for consistency, map one out-of-context "identifier"
2112 // to one heap region node id, otherwise no convergence
2113 String oocid = "oocid"+
2115 hrnDstCallee.getIDString()+
2118 reCaller.getField();
2120 Integer oocHrnID = oocid2hrnid.get(oocid);
2122 HeapRegionNode hrnCalleeAndOutContext;
2124 if( oocHrnID == null ) {
2126 hrnCalleeAndOutContext =
2127 rg.createNewHeapRegionNode(null, // ID
2128 false, // single object?
2129 false, // new summary?
2130 true, // out-of-context?
2132 null, // alloc site, shouldn't be used
2133 toCalleeContext(oocReach,
2137 toCalleeContext(oocReach,
2145 oocid2hrnid.put(oocid, hrnCalleeAndOutContext.getID() );
2149 // the mapping already exists, so see if node is there
2150 hrnCalleeAndOutContext = rg.id2hrn.get(oocHrnID);
2152 if( hrnCalleeAndOutContext == null ) {
2154 hrnCalleeAndOutContext =
2155 rg.createNewHeapRegionNode(oocHrnID, // ID
2156 false, // single object?
2157 false, // new summary?
2158 true, // out-of-context?
2160 null, // alloc site, shouldn't be used
2161 toCalleeContext(oocReach,
2165 toCalleeContext(oocReach,
2174 // otherwise it is there, so merge reachability
2175 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2176 toCalleeContext(oocReach,
2185 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2187 rg.addRefEdge(hrnCalleeAndOutContext,
2189 new RefEdge(hrnCalleeAndOutContext,
2192 reCaller.getField(),
2193 toCalleeContext(reCaller.getBeta(),
2198 toCalleeContext(reCaller.getTaints(),
2204 // the out-of-context edge already exists
2205 oocEdgeExisting.setBeta(Canonical.unionORpreds(oocEdgeExisting.getBeta(),
2206 toCalleeContext(reCaller.getBeta(),
2213 oocEdgeExisting.setPreds(Canonical.join(oocEdgeExisting.getPreds(),
2218 oocEdgeExisting.setTaints(Canonical.unionORpreds(oocEdgeExisting.getTaints(),
2219 toCalleeContext(reCaller.getTaints(),
2225 HeapRegionNode hrnCalleeAndOutContext =
2226 (HeapRegionNode) oocEdgeExisting.getSrc();
2227 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2228 toCalleeContext(oocReach,
2235 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2240 if( writeDebugDOTs ) {
2241 debugGraphPrefix = String.format("call%03d", debugCallSiteVisitCounter);
2242 rg.writeGraph(debugGraphPrefix+"calleeview",
2243 resolveMethodDebugDOTwriteLabels,
2244 resolveMethodDebugDOTselectTemps,
2245 resolveMethodDebugDOTpruneGarbage,
2246 resolveMethodDebugDOThideReach,
2247 resolveMethodDebugDOThideSubsetReach,
2248 resolveMethodDebugDOThidePreds,
2249 resolveMethodDebugDOThideEdgeTaints);
2255 private static Hashtable<String, Integer> oocid2hrnid =
2256 new Hashtable<String, Integer>();
2259 // useful since many graphs writes in the method call debug code
2260 private static boolean resolveMethodDebugDOTwriteLabels = true;
2261 private static boolean resolveMethodDebugDOTselectTemps = true;
2262 private static boolean resolveMethodDebugDOTpruneGarbage = true;
2263 private static boolean resolveMethodDebugDOThideReach = false;
2264 private static boolean resolveMethodDebugDOThideSubsetReach = false;
2265 private static boolean resolveMethodDebugDOThidePreds = false;
2266 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
2268 static String debugGraphPrefix;
2269 static int debugCallSiteVisitCounter;
2270 static int debugCallSiteVisitStartCapture;
2271 static int debugCallSiteNumVisitsToCapture;
2272 static boolean debugCallSiteStopAfter;
2276 resolveMethodCall(FlatCall fc,
2277 FlatMethod fmCallee,
2278 ReachGraph rgCallee,
2279 Set<Integer> callerNodeIDsCopiedToCallee,
2280 boolean writeDebugDOTs
2283 if( writeDebugDOTs ) {
2285 System.out.println(" Writing out visit "+
2286 debugCallSiteVisitCounter+
2287 " to debug call site");
2289 debugGraphPrefix = String.format("call%03d",
2290 debugCallSiteVisitCounter);
2292 rgCallee.writeGraph(debugGraphPrefix+"callee",
2293 resolveMethodDebugDOTwriteLabels,
2294 resolveMethodDebugDOTselectTemps,
2295 resolveMethodDebugDOTpruneGarbage,
2296 resolveMethodDebugDOThideReach,
2297 resolveMethodDebugDOThideSubsetReach,
2298 resolveMethodDebugDOThidePreds,
2299 resolveMethodDebugDOThideEdgeTaints);
2301 writeGraph(debugGraphPrefix+"caller00In",
2302 resolveMethodDebugDOTwriteLabels,
2303 resolveMethodDebugDOTselectTemps,
2304 resolveMethodDebugDOTpruneGarbage,
2305 resolveMethodDebugDOThideReach,
2306 resolveMethodDebugDOThideSubsetReach,
2307 resolveMethodDebugDOThidePreds,
2308 resolveMethodDebugDOThideEdgeTaints,
2309 callerNodeIDsCopiedToCallee);
2314 // method call transfer function steps:
2315 // 1. Use current callee-reachable heap (CRH) to test callee
2316 // predicates and mark what will be coming in.
2317 // 2. Wipe CRH out of caller.
2318 // 3. Transplant marked callee parts in:
2319 // a) bring in nodes
2320 // b) bring in callee -> callee edges
2321 // c) resolve out-of-context -> callee edges
2322 // d) assign return value
2323 // 4. Collapse shadow nodes down
2324 // 5. Global sweep it.
2327 // 1. mark what callee elements have satisfied predicates
2328 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
2329 new Hashtable<HeapRegionNode, ExistPredSet>();
2331 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
2332 new Hashtable<RefEdge, ExistPredSet>();
2334 Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
2335 calleeNode2calleeStatesSatisfied =
2336 new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
2338 Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
2339 calleeEdge2calleeStatesSatisfied =
2340 new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
2342 Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
2343 calleeEdge2calleeTaintsSatisfied =
2344 new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
2346 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
2347 new Hashtable< RefEdge, Set<RefSrcNode> >();
2351 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2352 while( meItr.hasNext() ) {
2353 Map.Entry me = (Map.Entry)meItr.next();
2354 Integer id = (Integer) me.getKey();
2355 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2357 // if a callee element's predicates are satisfied then a set
2358 // of CALLER predicates is returned: they are the predicates
2359 // that the callee element moved into the caller context
2360 // should have, and it is inefficient to find this again later
2361 ExistPredSet predsIfSatis =
2362 hrnCallee.getPreds().isSatisfiedBy(this,
2363 callerNodeIDsCopiedToCallee,
2366 if( predsIfSatis != null ) {
2367 calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
2369 // otherwise don't bother looking at edges to this node
2375 // since the node is coming over, find out which reach
2376 // states on it should come over, too
2377 assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
2379 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2380 while( stateItr.hasNext() ) {
2381 ReachState stateCallee = stateItr.next();
2384 stateCallee.getPreds().isSatisfiedBy(this,
2385 callerNodeIDsCopiedToCallee,
2387 if( predsIfSatis != null ) {
2389 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2390 calleeNode2calleeStatesSatisfied.get(hrnCallee);
2392 if( calleeStatesSatisfied == null ) {
2393 calleeStatesSatisfied =
2394 new Hashtable<ReachState, ExistPredSet>();
2396 calleeNode2calleeStatesSatisfied.put(hrnCallee, calleeStatesSatisfied);
2399 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2403 // then look at edges to the node
2404 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2405 while( reItr.hasNext() ) {
2406 RefEdge reCallee = reItr.next();
2407 RefSrcNode rsnCallee = reCallee.getSrc();
2409 // (caller local variables to in-context heap regions)
2410 // have an (out-of-context heap region -> in-context heap region)
2411 // abstraction in the callEE, so its true we never need to
2412 // look at a (var node -> heap region) edge in callee to bring
2413 // those over for the call site transfer, except for the special
2414 // case of *RETURN var* -> heap region edges.
2415 // What about (param var->heap region)
2416 // edges in callee? They are dealt with below this loop.
2418 if( rsnCallee instanceof VariableNode ) {
2420 // looking for the return-value variable only
2421 VariableNode vnCallee = (VariableNode) rsnCallee;
2422 if( vnCallee.getTempDescriptor() != tdReturn ) {
2426 TempDescriptor returnTemp = fc.getReturnTemp();
2427 if( returnTemp == null ||
2428 !DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2433 // note that the assignment of the return value is to a
2434 // variable in the caller which is out-of-context with
2435 // respect to the callee
2436 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2437 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2438 rsnCallers.add(vnLhsCaller);
2439 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2443 // for HeapRegionNode callee sources...
2445 // first see if the source is out-of-context, and only
2446 // proceed with this edge if we find some caller-context
2448 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2449 boolean matchedOutOfContext = false;
2451 if( !hrnSrcCallee.isOutOfContext() ) {
2454 hrnSrcCallee.getPreds().isSatisfiedBy(this,
2455 callerNodeIDsCopiedToCallee,
2457 if( predsIfSatis != null ) {
2458 calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
2460 // otherwise forget this edge
2465 // hrnSrcCallee is out-of-context
2466 assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
2468 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2470 // use the isSatisfiedBy with a non-null callers set to capture
2471 // nodes in the caller that match the predicates
2472 reCallee.getPreds().isSatisfiedBy( this,
2473 callerNodeIDsCopiedToCallee,
2476 if( !rsnCallers.isEmpty() ) {
2477 matchedOutOfContext = true;
2478 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2482 if( hrnSrcCallee.isOutOfContext() &&
2483 !matchedOutOfContext ) {
2490 reCallee.getPreds().isSatisfiedBy(this,
2491 callerNodeIDsCopiedToCallee,
2495 if( predsIfSatis != null ) {
2496 calleeEdgesSatisfied.put(reCallee, predsIfSatis);
2498 // since the edge is coming over, find out which reach
2499 // states on it should come over, too
2500 assert calleeEdge2calleeStatesSatisfied.get(reCallee) == null;
2502 stateItr = reCallee.getBeta().iterator();
2503 while( stateItr.hasNext() ) {
2504 ReachState stateCallee = stateItr.next();
2507 stateCallee.getPreds().isSatisfiedBy(this,
2508 callerNodeIDsCopiedToCallee,
2510 if( predsIfSatis != null ) {
2512 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2513 calleeEdge2calleeStatesSatisfied.get(reCallee);
2515 if( calleeStatesSatisfied == null ) {
2516 calleeStatesSatisfied =
2517 new Hashtable<ReachState, ExistPredSet>();
2519 calleeEdge2calleeStatesSatisfied.put(reCallee, calleeStatesSatisfied);
2522 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2526 // since the edge is coming over, find out which taints
2527 // on it should come over, too
2528 assert calleeEdge2calleeTaintsSatisfied.get(reCallee) == null;
2530 Iterator<Taint> tItr = reCallee.getTaints().iterator();
2531 while( tItr.hasNext() ) {
2532 Taint tCallee = tItr.next();
2535 tCallee.getPreds().isSatisfiedBy(this,
2536 callerNodeIDsCopiedToCallee,
2538 if( predsIfSatis != null ) {
2540 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2541 calleeEdge2calleeTaintsSatisfied.get(reCallee);
2543 if( calleeTaintsSatisfied == null ) {
2544 calleeTaintsSatisfied =
2545 new Hashtable<Taint, ExistPredSet>();
2547 calleeEdge2calleeTaintsSatisfied.put(reCallee, calleeTaintsSatisfied);
2550 calleeTaintsSatisfied.put(tCallee, predsIfSatis);
2557 if( writeDebugDOTs ) {
2558 writeGraph(debugGraphPrefix+"caller20BeforeWipe",
2559 resolveMethodDebugDOTwriteLabels,
2560 resolveMethodDebugDOTselectTemps,
2561 resolveMethodDebugDOTpruneGarbage,
2562 resolveMethodDebugDOThideReach,
2563 resolveMethodDebugDOThideSubsetReach,
2564 resolveMethodDebugDOThidePreds,
2565 resolveMethodDebugDOThideEdgeTaints);
2569 // 2. predicates tested, ok to wipe out caller part
2570 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2571 while( hrnItr.hasNext() ) {
2572 Integer hrnID = hrnItr.next();
2573 HeapRegionNode hrnCaller = id2hrn.get(hrnID);
2574 assert hrnCaller != null;
2576 // when clearing off nodes, also eliminate variable
2578 wipeOut(hrnCaller, true);
2581 // if we are assigning the return value to something, clobber now
2582 // as part of the wipe
2583 TempDescriptor returnTemp = fc.getReturnTemp();
2584 if( returnTemp != null &&
2585 DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2588 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2589 clearRefEdgesFrom(vnLhsCaller, null, null, true);
2595 if( writeDebugDOTs ) {
2596 writeGraph(debugGraphPrefix+"caller30BeforeAddingNodes",
2597 resolveMethodDebugDOTwriteLabels,
2598 resolveMethodDebugDOTselectTemps,
2599 resolveMethodDebugDOTpruneGarbage,
2600 resolveMethodDebugDOThideReach,
2601 resolveMethodDebugDOThideSubsetReach,
2602 resolveMethodDebugDOThidePreds,
2603 resolveMethodDebugDOThideEdgeTaints);
2609 // 3. callee elements with satisfied preds come in, note that
2610 // the mapping of elements satisfied to preds is like this:
2611 // A callee element EE has preds EEp that are satisfied by
2612 // some caller element ER. We bring EE into the caller
2613 // context as ERee with the preds of ER, namely ERp, which
2614 // in the following algorithm is the value in the mapping
2617 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2618 while( satisItr.hasNext() ) {
2619 Map.Entry me = (Map.Entry)satisItr.next();
2620 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2621 ExistPredSet preds = (ExistPredSet) me.getValue();
2623 // TODO: I think its true that the current implementation uses
2624 // the type of the OOC region and the predicates OF THE EDGE from
2625 // it to link everything up in caller context, so that's why we're
2626 // skipping this... maybe that's a sillier way to do it?
2627 if( hrnCallee.isOutOfContext() ) {
2631 AllocSite as = hrnCallee.getAllocSite();
2634 Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
2636 HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
2637 if( hrnCaller == null ) {
2639 createNewHeapRegionNode(hrnIDshadow, // id or null to generate a new one
2640 hrnCallee.isSingleObject(), // single object?
2641 hrnCallee.isNewSummary(), // summary?
2642 false, // out-of-context?
2643 hrnCallee.getType(), // type
2644 hrnCallee.getAllocSite(), // allocation site
2645 toCallerContext(hrnCallee.getInherent(),
2646 calleeNode2calleeStatesSatisfied.get(hrnCallee) ), // inherent reach
2647 null, // current reach
2648 predsEmpty, // predicates
2649 hrnCallee.getDescription() // description
2652 assert hrnCaller.isWiped();
2655 hrnCaller.setAlpha(toCallerContext(hrnCallee.getAlpha(),
2656 calleeNode2calleeStatesSatisfied.get(hrnCallee)
2660 hrnCaller.setPreds(preds);
2667 if( writeDebugDOTs ) {
2668 writeGraph(debugGraphPrefix+"caller31BeforeAddingEdges",
2669 resolveMethodDebugDOTwriteLabels,
2670 resolveMethodDebugDOTselectTemps,
2671 resolveMethodDebugDOTpruneGarbage,
2672 resolveMethodDebugDOThideReach,
2673 resolveMethodDebugDOThideSubsetReach,
2674 resolveMethodDebugDOThidePreds,
2675 resolveMethodDebugDOThideEdgeTaints);
2679 // set these up during the next procedure so after
2680 // the caller has all of its nodes and edges put
2681 // back together we can propagate the callee's
2682 // reach changes backwards into the caller graph
2683 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2685 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2686 new Hashtable<RefEdge, ChangeSet>();
2689 // 3.b) callee -> callee edges AND out-of-context -> callee
2690 // which includes return temp -> callee edges now, too
2691 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2692 while( satisItr.hasNext() ) {
2693 Map.Entry me = (Map.Entry)satisItr.next();
2694 RefEdge reCallee = (RefEdge) me.getKey();
2695 ExistPredSet preds = (ExistPredSet) me.getValue();
2697 HeapRegionNode hrnDstCallee = reCallee.getDst();
2698 AllocSite asDst = hrnDstCallee.getAllocSite();
2699 allocSites.add(asDst);
2701 Integer hrnIDDstShadow =
2702 asDst.getShadowIDfromID(hrnDstCallee.getID() );
2704 HeapRegionNode hrnDstCaller = id2hrn.get(hrnIDDstShadow);
2705 assert hrnDstCaller != null;
2708 RefSrcNode rsnCallee = reCallee.getSrc();
2710 Set<RefSrcNode> rsnCallers =
2711 new HashSet<RefSrcNode>();
2713 Set<RefSrcNode> oocCallers =
2714 calleeEdges2oocCallerSrcMatches.get(reCallee);
2716 if( rsnCallee instanceof HeapRegionNode ) {
2717 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2718 if( hrnCalleeSrc.isOutOfContext() ) {
2719 assert oocCallers != null;
2724 if( oocCallers == null ) {
2725 // there are no out-of-context matches, so it's
2726 // either a param/arg var or one in-context heap region
2727 if( rsnCallee instanceof VariableNode ) {
2728 // variable -> node in the callee should only
2729 // come into the caller if its from a param var
2730 VariableNode vnCallee = (VariableNode) rsnCallee;
2731 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2732 TempDescriptor tdArg = fc.getArgMatchingParam(fmCallee,
2734 if( tdArg == null ) {
2735 // this means the variable isn't a parameter, its local
2736 // to the callee so we ignore it in call site transfer
2737 // shouldn't this NEVER HAPPEN?
2741 rsnCallers.add(this.getVariableNodeFromTemp(tdArg) );
2744 // otherwise source is in context, one region
2746 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2748 // translate an in-context node to shadow
2749 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2750 allocSites.add(asSrc);
2752 Integer hrnIDSrcShadow =
2753 asSrc.getShadowIDfromID(hrnSrcCallee.getID() );
2755 HeapRegionNode hrnSrcCallerShadow =
2756 this.id2hrn.get(hrnIDSrcShadow);
2758 assert hrnSrcCallerShadow != null;
2760 rsnCallers.add(hrnSrcCallerShadow);
2764 // otherwise we have a set of out-of-context srcs
2765 // that should NOT be translated to shadow nodes
2766 assert !oocCallers.isEmpty();
2767 rsnCallers.addAll(oocCallers);
2770 // now make all caller edges we've identified from
2771 // this callee edge with a satisfied predicate
2772 assert !rsnCallers.isEmpty();
2773 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2774 while( rsnItr.hasNext() ) {
2775 RefSrcNode rsnCaller = rsnItr.next();
2777 RefEdge reCaller = new RefEdge(rsnCaller,
2780 reCallee.getField(),
2781 toCallerContext(reCallee.getBeta(),
2782 calleeEdge2calleeStatesSatisfied.get(reCallee) ),
2784 toCallerContext(reCallee.getTaints(),
2785 calleeEdge2calleeTaintsSatisfied.get(reCallee) )
2788 ChangeSet cs = ChangeSet.factory();
2789 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2790 while( rsItr.hasNext() ) {
2791 ReachState state = rsItr.next();
2792 ExistPredSet predsPreCallee = state.getPreds();
2794 if( state.isEmpty() ) {
2798 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2799 while( predItr.hasNext() ) {
2800 ExistPred pred = predItr.next();
2801 ReachState old = pred.ne_state;
2807 cs = Canonical.add(cs,
2808 ChangeTuple.factory(old,
2815 // we're just going to use the convenient "merge-if-exists"
2816 // edge call below, but still take a separate look if there
2817 // is an existing caller edge to build change sets properly
2818 if( !cs.isEmpty() ) {
2819 RefEdge edgeExisting = rsnCaller.getReferenceTo(hrnDstCaller,
2823 if( edgeExisting != null ) {
2824 ChangeSet csExisting = edgePlannedChanges.get(edgeExisting);
2825 if( csExisting == null ) {
2826 csExisting = ChangeSet.factory();
2828 edgePlannedChanges.put(edgeExisting,
2829 Canonical.union(csExisting,
2834 edgesForPropagation.add(reCaller);
2835 assert !edgePlannedChanges.containsKey(reCaller);
2836 edgePlannedChanges.put(reCaller, cs);
2840 // then add new caller edge or merge
2841 addEdgeOrMergeWithExisting(reCaller);
2849 if( writeDebugDOTs ) {
2850 writeGraph(debugGraphPrefix+"caller38propagateReach",
2851 resolveMethodDebugDOTwriteLabels,
2852 resolveMethodDebugDOTselectTemps,
2853 resolveMethodDebugDOTpruneGarbage,
2854 resolveMethodDebugDOThideReach,
2855 resolveMethodDebugDOThideSubsetReach,
2856 resolveMethodDebugDOThidePreds,
2857 resolveMethodDebugDOThideEdgeTaints);
2860 // propagate callee reachability changes to the rest
2861 // of the caller graph edges
2862 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2864 propagateTokensOverEdges(edgesForPropagation, // source edges
2865 edgePlannedChanges, // map src edge to change set
2866 edgesUpdated); // list of updated edges
2868 // commit beta' (beta<-betaNew)
2869 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2870 while( edgeItr.hasNext() ) {
2871 edgeItr.next().applyBetaNew();
2880 if( writeDebugDOTs ) {
2881 writeGraph(debugGraphPrefix+"caller40BeforeShadowMerge",
2882 resolveMethodDebugDOTwriteLabels,
2883 resolveMethodDebugDOTselectTemps,
2884 resolveMethodDebugDOTpruneGarbage,
2885 resolveMethodDebugDOThideReach,
2886 resolveMethodDebugDOThideSubsetReach,
2887 resolveMethodDebugDOThidePreds,
2888 resolveMethodDebugDOThideEdgeTaints);
2892 // 4) merge shadow nodes so alloc sites are back to k
2893 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2894 while( asItr.hasNext() ) {
2895 // for each allocation site do the following to merge
2896 // shadow nodes (newest from callee) with any existing
2897 // look for the newest normal and newest shadow "slot"
2898 // not being used, transfer normal to shadow. Keep
2899 // doing this until there are no more normal nodes, or
2900 // no empty shadow slots: then merge all remaining normal
2901 // nodes into the shadow summary. Finally, convert all
2902 // shadow to their normal versions.
2903 AllocSite as = asItr.next();
2907 while( ageNorm < allocationDepth &&
2908 ageShad < allocationDepth ) {
2910 // first, are there any normal nodes left?
2911 Integer idNorm = as.getIthOldest(ageNorm);
2912 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2913 if( hrnNorm == null ) {
2914 // no, this age of normal node not in the caller graph
2919 // yes, a normal node exists, is there an empty shadow
2920 // "slot" to transfer it onto?
2921 HeapRegionNode hrnShad = getIthNode(as, ageShad, true);
2922 if( !hrnShad.isWiped() ) {
2923 // no, this age of shadow node is not empty
2928 // yes, this shadow node is empty
2929 transferOnto(hrnNorm, hrnShad);
2934 // now, while there are still normal nodes but no shadow
2935 // slots, merge normal nodes into the shadow summary
2936 while( ageNorm < allocationDepth ) {
2938 // first, are there any normal nodes left?
2939 Integer idNorm = as.getIthOldest(ageNorm);
2940 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2941 if( hrnNorm == null ) {
2942 // no, this age of normal node not in the caller graph
2947 // yes, a normal node exists, so get the shadow summary
2948 HeapRegionNode summShad = getSummaryNode(as, true);
2949 mergeIntoSummary(hrnNorm, summShad);
2951 // now tokens in reachability sets need to age also
2952 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2953 while( itrAllHRNodes.hasNext() ) {
2954 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
2955 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
2957 ageTuplesFrom(as, hrnToAge);
2959 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
2960 while( itrEdges.hasNext() ) {
2961 ageTuplesFrom(as, itrEdges.next() );
2968 // if there is a normal summary, merge it into shadow summary
2969 Integer idNorm = as.getSummary();
2970 HeapRegionNode summNorm = id2hrn.get(idNorm);
2971 if( summNorm != null ) {
2972 HeapRegionNode summShad = getSummaryNode(as, true);
2973 mergeIntoSummary(summNorm, summShad);
2976 // finally, flip all existing shadow nodes onto the normal
2977 for( int i = 0; i < allocationDepth; ++i ) {
2978 Integer idShad = as.getIthOldestShadow(i);
2979 HeapRegionNode hrnShad = id2hrn.get(idShad);
2980 if( hrnShad != null ) {
2982 HeapRegionNode hrnNorm = getIthNode(as, i, false);
2983 assert hrnNorm.isWiped();
2984 transferOnto(hrnShad, hrnNorm);
2988 Integer idShad = as.getSummaryShadow();
2989 HeapRegionNode summShad = id2hrn.get(idShad);
2990 if( summShad != null ) {
2991 summNorm = getSummaryNode(as, false);
2992 transferOnto(summShad, summNorm);
3001 if( writeDebugDOTs ) {
3002 writeGraph(debugGraphPrefix+"caller45BeforeUnshadow",
3003 resolveMethodDebugDOTwriteLabels,
3004 resolveMethodDebugDOTselectTemps,
3005 resolveMethodDebugDOTpruneGarbage,
3006 resolveMethodDebugDOThideReach,
3007 resolveMethodDebugDOThideSubsetReach,
3008 resolveMethodDebugDOThidePreds,
3009 resolveMethodDebugDOThideEdgeTaints);
3013 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3014 while( itrAllHRNodes.hasNext() ) {
3015 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
3016 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3018 hrn.setAlpha(unshadow(hrn.getAlpha() ) );
3020 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
3021 while( itrEdges.hasNext() ) {
3022 RefEdge re = itrEdges.next();
3023 re.setBeta(unshadow(re.getBeta() ) );
3030 if( writeDebugDOTs ) {
3031 writeGraph(debugGraphPrefix+"caller50BeforeGlobalSweep",
3032 resolveMethodDebugDOTwriteLabels,
3033 resolveMethodDebugDOTselectTemps,
3034 resolveMethodDebugDOTpruneGarbage,
3035 resolveMethodDebugDOThideReach,
3036 resolveMethodDebugDOThideSubsetReach,
3037 resolveMethodDebugDOThidePreds,
3038 resolveMethodDebugDOThideEdgeTaints);
3043 if( !DISABLE_GLOBAL_SWEEP ) {
3048 if( writeDebugDOTs ) {
3049 writeGraph(debugGraphPrefix+"caller90AfterTransfer",
3050 resolveMethodDebugDOTwriteLabels,
3051 resolveMethodDebugDOTselectTemps,
3052 resolveMethodDebugDOTpruneGarbage,
3053 resolveMethodDebugDOThideReach,
3054 resolveMethodDebugDOThideSubsetReach,
3055 resolveMethodDebugDOThidePreds,
3056 resolveMethodDebugDOThideEdgeTaints);
3062 ////////////////////////////////////////////////////
3064 // Abstract garbage collection simply removes
3065 // heap region nodes that are not mechanically
3066 // reachable from a root set. This step is
3067 // essential for testing node and edge existence
3068 // predicates efficiently
3070 ////////////////////////////////////////////////////
3071 public void abstractGarbageCollect(Set<TempDescriptor> liveSet) {
3073 // calculate a root set, will be different for Java
3074 // version of analysis versus Bamboo version
3075 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3077 // visit every variable in graph while building root
3078 // set, and do iterating on a copy, so we can remove
3079 // dead variables while we're at this
3080 Iterator makeCopyItr = td2vn.entrySet().iterator();
3081 Set entrysCopy = new HashSet();
3082 while( makeCopyItr.hasNext() ) {
3083 entrysCopy.add(makeCopyItr.next() );
3086 Iterator eItr = entrysCopy.iterator();
3087 while( eItr.hasNext() ) {
3088 Map.Entry me = (Map.Entry)eItr.next();
3089 TempDescriptor td = (TempDescriptor) me.getKey();
3090 VariableNode vn = (VariableNode) me.getValue();
3092 if( liveSet.contains(td) ) {
3096 // dead var, remove completely from graph
3098 clearRefEdgesFrom(vn, null, null, true);
3102 // everything visited in a traversal is
3103 // considered abstractly live
3104 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3106 while( !toVisit.isEmpty() ) {
3107 RefSrcNode rsn = toVisit.iterator().next();
3108 toVisit.remove(rsn);
3111 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3112 while( hrnItr.hasNext() ) {
3113 RefEdge edge = hrnItr.next();
3114 HeapRegionNode hrn = edge.getDst();
3116 if( !visited.contains(hrn) ) {
3122 // get a copy of the set to iterate over because
3123 // we're going to monkey with the graph when we
3124 // identify a garbage node
3125 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3126 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3127 while( hrnItr.hasNext() ) {
3128 hrnAllPrior.add(hrnItr.next() );
3131 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3132 while( hrnAllItr.hasNext() ) {
3133 HeapRegionNode hrn = hrnAllItr.next();
3135 if( !visited.contains(hrn) ) {
3137 // heap region nodes are compared across ReachGraph
3138 // objects by their integer ID, so when discarding
3139 // garbage nodes we must also discard entries in
3140 // the ID -> heap region hashtable.
3141 id2hrn.remove(hrn.getID() );
3143 // RefEdge objects are two-way linked between
3144 // nodes, so when a node is identified as garbage,
3145 // actively clear references to and from it so
3146 // live nodes won't have dangling RefEdge's
3149 // if we just removed the last node from an allocation
3150 // site, it should be taken out of the ReachGraph's list
3151 AllocSite as = hrn.getAllocSite();
3152 if( !hasNodesOf(as) ) {
3153 allocSites.remove(as);
3159 protected boolean hasNodesOf(AllocSite as) {
3160 if( id2hrn.containsKey(as.getSummary() ) ) {
3164 for( int i = 0; i < allocationDepth; ++i ) {
3165 if( id2hrn.containsKey(as.getIthOldest(i) ) ) {
3173 ////////////////////////////////////////////////////
3175 // This global sweep is an optional step to prune
3176 // reachability sets that are not internally
3177 // consistent with the global graph. It should be
3178 // invoked after strong updates or method calls.
3180 ////////////////////////////////////////////////////
3181 public void globalSweep() {
3183 // boldB is part of the phase 1 sweep
3184 // it has an in-context table and an out-of-context table
3185 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3186 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3188 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3189 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3191 // visit every heap region to initialize alphaNew and betaNew,
3192 // and make a map of every hrnID to the source nodes it should
3193 // propagate forward from. In-context flagged hrnID's propagate
3194 // from only the in-context node they name, but out-of-context
3195 // ID's may propagate from several out-of-context nodes
3196 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3197 new Hashtable< Integer, Set<HeapRegionNode> >();
3199 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3200 new Hashtable< Integer, Set<HeapRegionNode> >();
3203 Iterator itrHrns = id2hrn.entrySet().iterator();
3204 while( itrHrns.hasNext() ) {
3205 Map.Entry me = (Map.Entry)itrHrns.next();
3206 Integer hrnID = (Integer) me.getKey();
3207 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3209 // assert that this node and incoming edges have clean alphaNew
3210 // and betaNew sets, respectively
3211 assert rsetEmpty.equals(hrn.getAlphaNew() );
3213 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3214 while( itrRers.hasNext() ) {
3215 RefEdge edge = itrRers.next();
3216 assert rsetEmpty.equals(edge.getBetaNew() );
3219 // make a mapping of IDs to heap regions they propagate from
3220 if( hrn.isFlagged() ) {
3221 assert !hrn.isOutOfContext();
3222 assert !icID2srcs.containsKey(hrn.getID() );
3224 // in-context flagged node IDs simply propagate from the
3226 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3228 icID2srcs.put(hrn.getID(), srcs);
3231 if( hrn.isOutOfContext() ) {
3232 assert !hrn.isFlagged();
3234 // the reachability states on an out-of-context
3235 // node are not really important (combinations of
3236 // IDs or arity)--what matters is that the states
3237 // specify which nodes this out-of-context node
3238 // stands in for. For example, if the state [17?, 19*]
3239 // appears on the ooc node, it may serve as a source
3240 // for node 17? and a source for node 19.
3241 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3242 while( stateItr.hasNext() ) {
3243 ReachState state = stateItr.next();
3245 Iterator<ReachTuple> rtItr = state.iterator();
3246 while( rtItr.hasNext() ) {
3247 ReachTuple rt = rtItr.next();
3248 assert rt.isOutOfContext();
3250 Set<HeapRegionNode> srcs = oocID2srcs.get(rt.getHrnID() );
3251 if( srcs == null ) {
3252 srcs = new HashSet<HeapRegionNode>();
3255 oocID2srcs.put(rt.getHrnID(), srcs);
3261 // calculate boldB for all hrnIDs identified by the above
3262 // node traversal, propagating from every source
3263 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3266 Set<HeapRegionNode> srcs;
3269 if( !icID2srcs.isEmpty() ) {
3270 Map.Entry me = (Map.Entry)icID2srcs.entrySet().iterator().next();
3271 hrnID = (Integer) me.getKey();
3272 srcs = (Set<HeapRegionNode>)me.getValue();
3274 icID2srcs.remove(hrnID);
3277 assert !oocID2srcs.isEmpty();
3279 Map.Entry me = (Map.Entry)oocID2srcs.entrySet().iterator().next();
3280 hrnID = (Integer) me.getKey();
3281 srcs = (Set<HeapRegionNode>)me.getValue();
3283 oocID2srcs.remove(hrnID);
3287 Hashtable<RefEdge, ReachSet> boldB_f =
3288 new Hashtable<RefEdge, ReachSet>();
3290 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3292 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3293 while( hrnItr.hasNext() ) {
3294 HeapRegionNode hrn = hrnItr.next();
3296 assert workSetEdges.isEmpty();
3298 // initial boldB_f constraints
3299 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3300 while( itrRees.hasNext() ) {
3301 RefEdge edge = itrRees.next();
3303 assert !boldB_f.containsKey(edge);
3304 boldB_f.put(edge, edge.getBeta() );
3306 assert !workSetEdges.contains(edge);
3307 workSetEdges.add(edge);
3310 // enforce the boldB_f constraint at edges until we reach a fixed point
3311 while( !workSetEdges.isEmpty() ) {
3312 RefEdge edge = workSetEdges.iterator().next();
3313 workSetEdges.remove(edge);
3315 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3316 while( itrPrime.hasNext() ) {
3317 RefEdge edgePrime = itrPrime.next();
3319 ReachSet prevResult = boldB_f.get(edgePrime);
3320 ReachSet intersection = Canonical.intersection(boldB_f.get(edge),
3324 if( prevResult == null ||
3325 Canonical.unionORpreds(prevResult,
3326 intersection).size()
3330 if( prevResult == null ) {
3331 boldB_f.put(edgePrime,
3332 Canonical.unionORpreds(edgePrime.getBeta(),
3337 boldB_f.put(edgePrime,
3338 Canonical.unionORpreds(prevResult,
3343 workSetEdges.add(edgePrime);
3350 boldBic.put(hrnID, boldB_f);
3352 boldBooc.put(hrnID, boldB_f);
3357 // use boldB to prune hrnIDs from alpha states that are impossible
3358 // and propagate the differences backwards across edges
3359 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3361 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3362 new Hashtable<RefEdge, ChangeSet>();
3365 itrHrns = id2hrn.entrySet().iterator();
3366 while( itrHrns.hasNext() ) {
3367 Map.Entry me = (Map.Entry)itrHrns.next();
3368 Integer hrnID = (Integer) me.getKey();
3369 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3371 // out-of-context nodes don't participate in the
3372 // global sweep, they serve as sources for the pass
3374 if( hrn.isOutOfContext() ) {
3378 // the inherent states of a region are the exception
3379 // to removal as the global sweep prunes
3380 ReachTuple rtException = ReachTuple.factory(hrnID,
3381 !hrn.isSingleObject(),
3382 ReachTuple.ARITY_ONE,
3383 false // out-of-context
3386 ChangeSet cts = ChangeSet.factory();
3388 // mark hrnIDs for removal
3389 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3390 while( stateItr.hasNext() ) {
3391 ReachState stateOld = stateItr.next();
3393 ReachState markedHrnIDs = ReachState.factory();
3395 Iterator<ReachTuple> rtItr = stateOld.iterator();
3396 while( rtItr.hasNext() ) {
3397 ReachTuple rtOld = rtItr.next();
3399 // never remove the inherent hrnID from a flagged region
3400 // because it is trivially satisfied
3401 if( hrn.isFlagged() ) {
3402 if( rtOld == rtException ) {
3407 // does boldB allow this hrnID?
3408 boolean foundState = false;
3409 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3410 while( incidentEdgeItr.hasNext() ) {
3411 RefEdge incidentEdge = incidentEdgeItr.next();
3413 Hashtable<RefEdge, ReachSet> B;
3414 if( rtOld.isOutOfContext() ) {
3415 B = boldBooc.get(rtOld.getHrnID() );
3418 if( !id2hrn.containsKey(rtOld.getHrnID() ) ) {
3419 // let symbols not in the graph get pruned
3423 B = boldBic.get(rtOld.getHrnID() );
3427 ReachSet boldB_rtOld_incident = B.get(incidentEdge);
3428 if( boldB_rtOld_incident != null &&
3429 boldB_rtOld_incident.containsIgnorePreds(stateOld) != null
3437 markedHrnIDs = Canonical.addUpArity(markedHrnIDs, rtOld);
3441 // if there is nothing marked, just move on
3442 if( markedHrnIDs.isEmpty() ) {
3443 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3450 // remove all marked hrnIDs and establish a change set that should
3451 // propagate backwards over edges from this node
3452 ReachState statePruned = ReachState.factory();
3453 rtItr = stateOld.iterator();
3454 while( rtItr.hasNext() ) {
3455 ReachTuple rtOld = rtItr.next();
3457 if( !markedHrnIDs.containsTuple(rtOld) ) {
3458 statePruned = Canonical.addUpArity(statePruned, rtOld);
3461 assert !stateOld.equals(statePruned);
3463 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3467 ChangeTuple ct = ChangeTuple.factory(stateOld,
3470 cts = Canonical.add(cts, ct);
3473 // throw change tuple set on all incident edges
3474 if( !cts.isEmpty() ) {
3475 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3476 while( incidentEdgeItr.hasNext() ) {
3477 RefEdge incidentEdge = incidentEdgeItr.next();
3479 edgesForPropagation.add(incidentEdge);
3481 if( edgePlannedChanges.get(incidentEdge) == null ) {
3482 edgePlannedChanges.put(incidentEdge, cts);
3484 edgePlannedChanges.put(
3486 Canonical.union(edgePlannedChanges.get(incidentEdge),
3495 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3497 propagateTokensOverEdges(edgesForPropagation,
3501 // at the end of the 1st phase reference edges have
3502 // beta, betaNew that correspond to beta and betaR
3504 // commit beta<-betaNew, so beta=betaR and betaNew
3505 // will represent the beta' calculation in 2nd phase
3507 // commit alpha<-alphaNew because it won't change
3508 HashSet<RefEdge> res = new HashSet<RefEdge>();
3510 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3511 while( nodeItr.hasNext() ) {
3512 HeapRegionNode hrn = nodeItr.next();
3514 // as mentioned above, out-of-context nodes only serve
3515 // as sources of reach states for the sweep, not part
3517 if( hrn.isOutOfContext() ) {
3518 assert hrn.getAlphaNew().equals(rsetEmpty);
3520 hrn.applyAlphaNew();
3523 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3524 while( itrRes.hasNext() ) {
3525 res.add(itrRes.next() );
3531 Iterator<RefEdge> edgeItr = res.iterator();
3532 while( edgeItr.hasNext() ) {
3533 RefEdge edge = edgeItr.next();
3534 HeapRegionNode hrn = edge.getDst();
3536 // commit results of last phase
3537 if( edgesUpdated.contains(edge) ) {
3538 edge.applyBetaNew();
3541 // compute intial condition of 2nd phase
3542 edge.setBetaNew(Canonical.intersection(edge.getBeta(),
3548 // every edge in the graph is the initial workset
3549 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3550 while( !edgeWorkSet.isEmpty() ) {
3551 RefEdge edgePrime = edgeWorkSet.iterator().next();
3552 edgeWorkSet.remove(edgePrime);
3554 RefSrcNode rsn = edgePrime.getSrc();
3555 if( !(rsn instanceof HeapRegionNode) ) {
3558 HeapRegionNode hrn = (HeapRegionNode) rsn;
3560 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3561 while( itrEdge.hasNext() ) {
3562 RefEdge edge = itrEdge.next();
3564 ReachSet prevResult = edge.getBetaNew();
3565 assert prevResult != null;
3567 ReachSet intersection =
3568 Canonical.intersection(edge.getBeta(),
3569 edgePrime.getBetaNew()
3572 if( Canonical.unionORpreds(prevResult,
3579 Canonical.unionORpreds(prevResult,
3583 edgeWorkSet.add(edge);
3588 // commit beta' (beta<-betaNew)
3589 edgeItr = res.iterator();
3590 while( edgeItr.hasNext() ) {
3591 edgeItr.next().applyBetaNew();
3596 // a useful assertion for debugging:
3597 // every in-context tuple on any edge or
3598 // any node should name a node that is
3599 // part of the graph
3600 public boolean inContextTuplesInGraph() {
3602 Iterator hrnItr = id2hrn.entrySet().iterator();
3603 while( hrnItr.hasNext() ) {
3604 Map.Entry me = (Map.Entry)hrnItr.next();
3605 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3608 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3609 while( stateItr.hasNext() ) {
3610 ReachState state = stateItr.next();
3612 Iterator<ReachTuple> rtItr = state.iterator();
3613 while( rtItr.hasNext() ) {
3614 ReachTuple rt = rtItr.next();
3616 if( !rt.isOutOfContext() ) {
3617 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3618 System.out.println(rt.getHrnID()+" is missing");
3626 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3627 while( edgeItr.hasNext() ) {
3628 RefEdge edge = edgeItr.next();
3630 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3631 while( stateItr.hasNext() ) {
3632 ReachState state = stateItr.next();
3634 Iterator<ReachTuple> rtItr = state.iterator();
3635 while( rtItr.hasNext() ) {
3636 ReachTuple rt = rtItr.next();
3638 if( !rt.isOutOfContext() ) {
3639 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3640 System.out.println(rt.getHrnID()+" is missing");
3653 // another useful assertion for debugging
3654 public boolean noEmptyReachSetsInGraph() {
3656 Iterator hrnItr = id2hrn.entrySet().iterator();
3657 while( hrnItr.hasNext() ) {
3658 Map.Entry me = (Map.Entry)hrnItr.next();
3659 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3661 if( !hrn.isOutOfContext() &&
3663 hrn.getAlpha().isEmpty()
3665 System.out.println("!!! "+hrn+" has an empty ReachSet !!!");
3669 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3670 while( edgeItr.hasNext() ) {
3671 RefEdge edge = edgeItr.next();
3673 if( edge.getBeta().isEmpty() ) {
3674 System.out.println("!!! "+edge+" has an empty ReachSet !!!");
3684 public boolean everyReachStateWTrue() {
3686 Iterator hrnItr = id2hrn.entrySet().iterator();
3687 while( hrnItr.hasNext() ) {
3688 Map.Entry me = (Map.Entry)hrnItr.next();
3689 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3692 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3693 while( stateItr.hasNext() ) {
3694 ReachState state = stateItr.next();
3696 if( !state.getPreds().equals(predsTrue) ) {
3702 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3703 while( edgeItr.hasNext() ) {
3704 RefEdge edge = edgeItr.next();
3706 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3707 while( stateItr.hasNext() ) {
3708 ReachState state = stateItr.next();
3710 if( !state.getPreds().equals(predsTrue) ) {
3723 ////////////////////////////////////////////////////
3724 // in merge() and equals() methods the suffix A
3725 // represents the passed in graph and the suffix
3726 // B refers to the graph in this object
3727 // Merging means to take the incoming graph A and
3728 // merge it into B, so after the operation graph B
3729 // is the final result.
3730 ////////////////////////////////////////////////////
3731 protected void merge(ReachGraph rg) {
3739 mergeAllocSites(rg);
3740 mergeInaccessibleVars(rg);
3743 protected void mergeNodes(ReachGraph rg) {
3745 // start with heap region nodes
3746 Set sA = rg.id2hrn.entrySet();
3747 Iterator iA = sA.iterator();
3748 while( iA.hasNext() ) {
3749 Map.Entry meA = (Map.Entry)iA.next();
3750 Integer idA = (Integer) meA.getKey();
3751 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3753 // if this graph doesn't have a node the
3754 // incoming graph has, allocate it
3755 if( !id2hrn.containsKey(idA) ) {
3756 HeapRegionNode hrnB = hrnA.copy();
3757 id2hrn.put(idA, hrnB);
3760 // otherwise this is a node present in both graphs
3761 // so make the new reachability set a union of the
3762 // nodes' reachability sets
3763 HeapRegionNode hrnB = id2hrn.get(idA);
3764 hrnB.setAlpha(Canonical.unionORpreds(hrnB.getAlpha(),
3769 hrnB.setPreds(Canonical.join(hrnB.getPreds(),
3776 if( !hrnA.equals(hrnB) ) {
3777 rg.writeGraph("graphA");
3778 this.writeGraph("graphB");
3779 throw new Error("flagged not matching");
3787 // now add any variable nodes that are in graph B but
3789 sA = rg.td2vn.entrySet();
3791 while( iA.hasNext() ) {
3792 Map.Entry meA = (Map.Entry)iA.next();
3793 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3794 VariableNode lnA = (VariableNode) meA.getValue();
3796 // if the variable doesn't exist in B, allocate and add it
3797 VariableNode lnB = getVariableNodeFromTemp(tdA);
3801 protected void mergeRefEdges(ReachGraph rg) {
3803 // between heap regions
3804 Set sA = rg.id2hrn.entrySet();
3805 Iterator iA = sA.iterator();
3806 while( iA.hasNext() ) {
3807 Map.Entry meA = (Map.Entry)iA.next();
3808 Integer idA = (Integer) meA.getKey();
3809 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3811 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3812 while( heapRegionsItrA.hasNext() ) {
3813 RefEdge edgeA = heapRegionsItrA.next();
3814 HeapRegionNode hrnChildA = edgeA.getDst();
3815 Integer idChildA = hrnChildA.getID();
3817 // at this point we know an edge in graph A exists
3818 // idA -> idChildA, does this exist in B?
3819 assert id2hrn.containsKey(idA);
3820 HeapRegionNode hrnB = id2hrn.get(idA);
3821 RefEdge edgeToMerge = null;
3823 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3824 while( heapRegionsItrB.hasNext() &&
3825 edgeToMerge == null ) {
3827 RefEdge edgeB = heapRegionsItrB.next();
3828 HeapRegionNode hrnChildB = edgeB.getDst();
3829 Integer idChildB = hrnChildB.getID();
3831 // don't use the RefEdge.equals() here because
3832 // we're talking about existence between graphs,
3833 // not intragraph equal
3834 if( idChildB.equals(idChildA) &&
3835 edgeB.typeAndFieldEquals(edgeA) ) {
3837 edgeToMerge = edgeB;
3841 // if the edge from A was not found in B,
3843 if( edgeToMerge == null ) {
3844 assert id2hrn.containsKey(idChildA);
3845 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3846 edgeToMerge = edgeA.copy();
3847 edgeToMerge.setSrc(hrnB);
3848 edgeToMerge.setDst(hrnChildB);
3849 addRefEdge(hrnB, hrnChildB, edgeToMerge);
3851 // otherwise, the edge already existed in both graphs
3852 // so merge their reachability sets
3854 // just replace this beta set with the union
3855 assert edgeToMerge != null;
3856 edgeToMerge.setBeta(
3857 Canonical.unionORpreds(edgeToMerge.getBeta(),
3861 edgeToMerge.setPreds(
3862 Canonical.join(edgeToMerge.getPreds(),
3866 edgeToMerge.setTaints(
3867 Canonical.union(edgeToMerge.getTaints(),
3875 // and then again from variable nodes
3876 sA = rg.td2vn.entrySet();
3878 while( iA.hasNext() ) {
3879 Map.Entry meA = (Map.Entry)iA.next();
3880 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3881 VariableNode vnA = (VariableNode) meA.getValue();
3883 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3884 while( heapRegionsItrA.hasNext() ) {
3885 RefEdge edgeA = heapRegionsItrA.next();
3886 HeapRegionNode hrnChildA = edgeA.getDst();
3887 Integer idChildA = hrnChildA.getID();
3889 // at this point we know an edge in graph A exists
3890 // tdA -> idChildA, does this exist in B?
3891 assert td2vn.containsKey(tdA);
3892 VariableNode vnB = td2vn.get(tdA);
3893 RefEdge edgeToMerge = null;
3895 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3896 while( heapRegionsItrB.hasNext() &&
3897 edgeToMerge == null ) {
3899 RefEdge edgeB = heapRegionsItrB.next();
3900 HeapRegionNode hrnChildB = edgeB.getDst();
3901 Integer idChildB = hrnChildB.getID();
3903 // don't use the RefEdge.equals() here because
3904 // we're talking about existence between graphs
3905 if( idChildB.equals(idChildA) &&
3906 edgeB.typeAndFieldEquals(edgeA) ) {
3908 edgeToMerge = edgeB;
3912 // if the edge from A was not found in B,
3914 if( edgeToMerge == null ) {
3915 assert id2hrn.containsKey(idChildA);
3916 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3917 edgeToMerge = edgeA.copy();
3918 edgeToMerge.setSrc(vnB);
3919 edgeToMerge.setDst(hrnChildB);
3920 addRefEdge(vnB, hrnChildB, edgeToMerge);
3922 // otherwise, the edge already existed in both graphs
3923 // so merge their reachability sets
3925 // just replace this beta set with the union
3926 edgeToMerge.setBeta(Canonical.unionORpreds(edgeToMerge.getBeta(),
3930 edgeToMerge.setPreds(Canonical.join(edgeToMerge.getPreds(),
3934 edgeToMerge.setTaints(
3935 Canonical.union(edgeToMerge.getTaints(),
3944 protected void mergeAllocSites(ReachGraph rg) {
3945 allocSites.addAll(rg.allocSites);
3948 protected void mergeInaccessibleVars(ReachGraph rg) {
3949 inaccessibleVars.addAll(rg.inaccessibleVars);
3954 static boolean dbgEquals = false;
3957 // it is necessary in the equals() member functions
3958 // to "check both ways" when comparing the data
3959 // structures of two graphs. For instance, if all
3960 // edges between heap region nodes in graph A are
3961 // present and equal in graph B it is not sufficient
3962 // to say the graphs are equal. Consider that there
3963 // may be edges in graph B that are not in graph A.
3964 // the only way to know that all edges in both graphs
3965 // are equally present is to iterate over both data
3966 // structures and compare against the other graph.
3967 public boolean equals(ReachGraph rg) {
3971 System.out.println("rg is null");
3976 if( !areHeapRegionNodesEqual(rg) ) {
3978 System.out.println("hrn not equal");
3983 if( !areVariableNodesEqual(rg) ) {
3985 System.out.println("vars not equal");
3990 if( !areRefEdgesEqual(rg) ) {
3992 System.out.println("edges not equal");
3997 if( !inaccessibleVars.equals(rg.inaccessibleVars) ) {
4001 // if everything is equal up to this point,
4002 // assert that allocSites is also equal--
4003 // this data is redundant but kept for efficiency
4004 assert allocSites.equals(rg.allocSites);
4010 protected boolean areHeapRegionNodesEqual(ReachGraph rg) {
4012 if( !areallHRNinAalsoinBandequal(this, rg) ) {
4016 if( !areallHRNinAalsoinBandequal(rg, this) ) {
4023 static protected boolean areallHRNinAalsoinBandequal(ReachGraph rgA,
4025 Set sA = rgA.id2hrn.entrySet();
4026 Iterator iA = sA.iterator();
4027 while( iA.hasNext() ) {
4028 Map.Entry meA = (Map.Entry)iA.next();
4029 Integer idA = (Integer) meA.getKey();
4030 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4032 if( !rgB.id2hrn.containsKey(idA) ) {
4036 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4037 if( !hrnA.equalsIncludingAlphaAndPreds(hrnB) ) {
4045 protected boolean areVariableNodesEqual(ReachGraph rg) {
4047 if( !areallVNinAalsoinBandequal(this, rg) ) {
4051 if( !areallVNinAalsoinBandequal(rg, this) ) {
4058 static protected boolean areallVNinAalsoinBandequal(ReachGraph rgA,
4060 Set sA = rgA.td2vn.entrySet();
4061 Iterator iA = sA.iterator();
4062 while( iA.hasNext() ) {
4063 Map.Entry meA = (Map.Entry)iA.next();
4064 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4066 if( !rgB.td2vn.containsKey(tdA) ) {
4075 protected boolean areRefEdgesEqual(ReachGraph rg) {
4076 if( !areallREinAandBequal(this, rg) ) {
4080 if( !areallREinAandBequal(rg, this) ) {
4087 static protected boolean areallREinAandBequal(ReachGraph rgA,
4090 // check all the heap region->heap region edges
4091 Set sA = rgA.id2hrn.entrySet();
4092 Iterator iA = sA.iterator();
4093 while( iA.hasNext() ) {
4094 Map.Entry meA = (Map.Entry)iA.next();
4095 Integer idA = (Integer) meA.getKey();
4096 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4098 // we should have already checked that the same
4099 // heap regions exist in both graphs
4100 assert rgB.id2hrn.containsKey(idA);
4102 if( !areallREfromAequaltoB(rgA, hrnA, rgB) ) {
4106 // then check every edge in B for presence in A, starting
4107 // from the same parent HeapRegionNode
4108 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4110 if( !areallREfromAequaltoB(rgB, hrnB, rgA) ) {
4115 // then check all the variable->heap region edges
4116 sA = rgA.td2vn.entrySet();
4118 while( iA.hasNext() ) {
4119 Map.Entry meA = (Map.Entry)iA.next();
4120 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4121 VariableNode vnA = (VariableNode) meA.getValue();
4123 // we should have already checked that the same
4124 // label nodes exist in both graphs
4125 assert rgB.td2vn.containsKey(tdA);
4127 if( !areallREfromAequaltoB(rgA, vnA, rgB) ) {
4131 // then check every edge in B for presence in A, starting
4132 // from the same parent VariableNode
4133 VariableNode vnB = rgB.td2vn.get(tdA);
4135 if( !areallREfromAequaltoB(rgB, vnB, rgA) ) {
4144 static protected boolean areallREfromAequaltoB(ReachGraph rgA,
4148 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4149 while( itrA.hasNext() ) {
4150 RefEdge edgeA = itrA.next();
4151 HeapRegionNode hrnChildA = edgeA.getDst();
4152 Integer idChildA = hrnChildA.getID();
4154 assert rgB.id2hrn.containsKey(idChildA);
4156 // at this point we know an edge in graph A exists
4157 // rnA -> idChildA, does this exact edge exist in B?
4158 boolean edgeFound = false;
4160 RefSrcNode rnB = null;
4161 if( rnA instanceof HeapRegionNode ) {
4162 HeapRegionNode hrnA = (HeapRegionNode) rnA;
4163 rnB = rgB.id2hrn.get(hrnA.getID() );
4165 VariableNode vnA = (VariableNode) rnA;
4166 rnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4169 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4170 while( itrB.hasNext() ) {
4171 RefEdge edgeB = itrB.next();
4172 HeapRegionNode hrnChildB = edgeB.getDst();
4173 Integer idChildB = hrnChildB.getID();
4175 if( idChildA.equals(idChildB) &&
4176 edgeA.typeAndFieldEquals(edgeB) ) {
4178 // there is an edge in the right place with the right field,
4179 // but do they have the same attributes?
4180 if( edgeA.getBeta().equals(edgeB.getBeta() ) &&
4181 edgeA.equalsPreds(edgeB)
4197 // can be used to assert monotonicity
4198 static public boolean isNoSmallerThan(ReachGraph rgA,
4201 //System.out.println( "*** Asking if A is no smaller than B ***" );
4203 Iterator iA = rgA.id2hrn.entrySet().iterator();
4204 while( iA.hasNext() ) {
4205 Map.Entry meA = (Map.Entry)iA.next();
4206 Integer idA = (Integer) meA.getKey();
4207 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4209 if( !rgB.id2hrn.containsKey(idA) ) {
4210 System.out.println(" regions smaller");
4215 // this works just fine, no smaller than
4216 if( !areallVNinAalsoinBandequal(rgA, rgB) ) {
4217 System.out.println(" vars smaller:");
4218 System.out.println(" A:"+rgA.td2vn.keySet() );
4219 System.out.println(" B:"+rgB.td2vn.keySet() );
4224 iA = rgA.id2hrn.entrySet().iterator();
4225 while( iA.hasNext() ) {
4226 Map.Entry meA = (Map.Entry)iA.next();
4227 Integer idA = (Integer) meA.getKey();
4228 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4230 Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4231 while( reItr.hasNext() ) {
4232 RefEdge edgeA = reItr.next();
4233 RefSrcNode rsnA = edgeA.getSrc();
4235 // we already checked that nodes were present
4236 HeapRegionNode hrnB = rgB.id2hrn.get(hrnA.getID() );
4237 assert hrnB != null;
4240 if( rsnA instanceof VariableNode ) {
4241 VariableNode vnA = (VariableNode) rsnA;
4242 rsnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4245 HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4246 rsnB = rgB.id2hrn.get(hrnSrcA.getID() );
4248 assert rsnB != null;
4250 RefEdge edgeB = rsnB.getReferenceTo(hrnB,
4254 if( edgeB == null ) {
4255 System.out.println(" edges smaller:");
4269 // this analysis no longer has the "match anything"
4270 // type which was represented by null
4271 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4272 TypeDescriptor td2) {
4276 if( td1.isNull() ) {
4279 if( td2.isNull() ) {
4282 return typeUtil.mostSpecific(td1, td2);
4285 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4287 TypeDescriptor td3) {
4289 return mostSpecificType(td1,
4290 mostSpecificType(td2, td3)
4294 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4297 TypeDescriptor td4) {
4299 return mostSpecificType(mostSpecificType(td1, td2),
4300 mostSpecificType(td3, td4)
4304 protected boolean isSuperiorType(TypeDescriptor possibleSuper,
4305 TypeDescriptor possibleChild) {
4306 assert possibleSuper != null;
4307 assert possibleChild != null;
4309 if( possibleSuper.isNull() ||
4310 possibleChild.isNull() ) {
4314 return typeUtil.isSuperorType(possibleSuper, possibleChild);
4318 protected boolean hasMatchingField(HeapRegionNode src,
4321 TypeDescriptor tdSrc = src.getType();
4322 assert tdSrc != null;
4324 if( tdSrc.isArray() ) {
4325 TypeDescriptor td = edge.getType();
4328 TypeDescriptor tdSrcDeref = tdSrc.dereference();
4329 assert tdSrcDeref != null;
4331 if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
4335 return edge.getField().equals(DisjointAnalysis.arrayElementFieldName);
4338 // if it's not a class, it doesn't have any fields to match
4339 if( !tdSrc.isClass() ) {
4343 ClassDescriptor cd = tdSrc.getClassDesc();
4344 while( cd != null ) {
4345 Iterator fieldItr = cd.getFields();
4347 while( fieldItr.hasNext() ) {
4348 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4350 if( fd.getType().equals(edge.getType() ) &&
4351 fd.getSymbol().equals(edge.getField() ) ) {
4356 cd = cd.getSuperDesc();
4359 // otherwise it is a class with fields
4360 // but we didn't find a match
4364 protected boolean hasMatchingType(RefEdge edge,
4365 HeapRegionNode dst) {
4367 // if the region has no type, matches everything
4368 TypeDescriptor tdDst = dst.getType();
4369 assert tdDst != null;
4371 // if the type is not a class or an array, don't
4372 // match because primitives are copied, no aliases
4373 ClassDescriptor cdDst = tdDst.getClassDesc();
4374 if( cdDst == null && !tdDst.isArray() ) {
4378 // if the edge type is null, it matches everything
4379 TypeDescriptor tdEdge = edge.getType();
4380 assert tdEdge != null;
4382 return typeUtil.isSuperorType(tdEdge, tdDst);
4387 // the default signature for quick-and-dirty debugging
4388 public void writeGraph(String graphName) {
4389 writeGraph(graphName,
4390 true, // write labels
4391 true, // label select
4392 true, // prune garbage
4393 false, // hide reachability
4394 true, // hide subset reachability
4395 true, // hide predicates
4396 false, // hide edge taints
4397 null // in-context boundary
4401 public void writeGraph(String graphName,
4402 boolean writeLabels,
4403 boolean labelSelect,
4404 boolean pruneGarbage,
4405 boolean hideReachability,
4406 boolean hideSubsetReachability,
4407 boolean hidePredicates,
4408 boolean hideEdgeTaints
4410 writeGraph(graphName,
4415 hideSubsetReachability,
4421 public void writeGraph(String graphName,
4422 boolean writeLabels,
4423 boolean labelSelect,
4424 boolean pruneGarbage,
4425 boolean hideReachability,
4426 boolean hideSubsetReachability,
4427 boolean hidePredicates,
4428 boolean hideEdgeTaints,
4429 Set<Integer> callerNodeIDsCopiedToCallee
4432 // remove all non-word characters from the graph name so
4433 // the filename and identifier in dot don't cause errors
4434 // jjenista - also replace underscore '_' to prevent some
4435 // really, really long names from IHMS debugging
4436 graphName = graphName.replaceAll("[\\W_]", "");
4439 new BufferedWriter(new FileWriter(graphName+".dot") );
4441 bw.write("digraph "+graphName+" {\n");
4444 // this is an optional step to form the callee-reachable
4445 // "cut-out" into a DOT cluster for visualization
4446 if( callerNodeIDsCopiedToCallee != null ) {
4448 bw.write(" subgraph cluster0 {\n");
4449 bw.write(" color=blue;\n");
4451 Iterator i = id2hrn.entrySet().iterator();
4452 while( i.hasNext() ) {
4453 Map.Entry me = (Map.Entry)i.next();
4454 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4456 if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4459 hrn.toStringDOT(hideReachability,
4460 hideSubsetReachability,
4470 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4472 // then visit every heap region node
4473 Iterator i = id2hrn.entrySet().iterator();
4474 while( i.hasNext() ) {
4475 Map.Entry me = (Map.Entry)i.next();
4476 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4478 // only visit nodes worth writing out--for instance
4479 // not every node at an allocation is referenced
4480 // (think of it as garbage-collected), etc.
4481 if( !pruneGarbage ||
4482 hrn.isOutOfContext() ||
4483 (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4486 if( !visited.contains(hrn) ) {
4487 traverseHeapRegionNodes(hrn,
4492 hideSubsetReachability,
4495 callerNodeIDsCopiedToCallee);
4500 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4503 // then visit every label node, useful for debugging
4505 i = td2vn.entrySet().iterator();
4506 while( i.hasNext() ) {
4507 Map.Entry me = (Map.Entry)i.next();
4508 VariableNode vn = (VariableNode) me.getValue();
4511 String labelStr = vn.getTempDescriptorString();
4512 if( labelStr.startsWith("___temp") ||
4513 labelStr.startsWith("___dst") ||
4514 labelStr.startsWith("___srctmp") ||
4515 labelStr.startsWith("___neverused")
4521 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4522 while( heapRegionsItr.hasNext() ) {
4523 RefEdge edge = heapRegionsItr.next();
4524 HeapRegionNode hrn = edge.getDst();
4526 if( !visited.contains(hrn) ) {
4527 traverseHeapRegionNodes(hrn,
4532 hideSubsetReachability,
4535 callerNodeIDsCopiedToCallee);
4538 bw.write(" "+vn.toString()+
4539 " -> "+hrn.toString()+
4540 edge.toStringDOT(hideReachability,
4541 hideSubsetReachability,
4553 } catch( IOException e ) {
4554 throw new Error("Error writing out DOT graph "+graphName);
4559 traverseHeapRegionNodes(HeapRegionNode hrn,
4562 Set<HeapRegionNode> visited,
4563 boolean hideReachability,
4564 boolean hideSubsetReachability,
4565 boolean hidePredicates,
4566 boolean hideEdgeTaints,
4567 Set<Integer> callerNodeIDsCopiedToCallee
4568 ) throws java.io.IOException {
4570 if( visited.contains(hrn) ) {
4575 // if we're drawing the callee-view subgraph, only
4576 // write out the node info if it hasn't already been
4578 if( callerNodeIDsCopiedToCallee == null ||
4579 !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4583 hrn.toStringDOT(hideReachability,
4584 hideSubsetReachability,
4589 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4590 while( childRegionsItr.hasNext() ) {
4591 RefEdge edge = childRegionsItr.next();
4592 HeapRegionNode hrnChild = edge.getDst();
4594 if( callerNodeIDsCopiedToCallee != null &&
4595 (edge.getSrc() instanceof HeapRegionNode) ) {
4596 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4597 if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4598 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4600 bw.write(" "+hrn.toString()+
4601 " -> "+hrnChild.toString()+
4602 edge.toStringDOT(hideReachability,
4603 hideSubsetReachability,
4608 } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4609 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4611 bw.write(" "+hrn.toString()+
4612 " -> "+hrnChild.toString()+
4613 edge.toStringDOT(hideReachability,
4614 hideSubsetReachability,
4617 ",color=blue,style=dashed")+
4620 bw.write(" "+hrn.toString()+
4621 " -> "+hrnChild.toString()+
4622 edge.toStringDOT(hideReachability,
4623 hideSubsetReachability,
4630 bw.write(" "+hrn.toString()+
4631 " -> "+hrnChild.toString()+
4632 edge.toStringDOT(hideReachability,
4633 hideSubsetReachability,
4640 traverseHeapRegionNodes(hrnChild,
4645 hideSubsetReachability,
4648 callerNodeIDsCopiedToCallee);
4657 // return the set of heap regions from the given allocation
4658 // site, if any, that exist in this graph
4659 protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4661 Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4663 Integer idSum = as.getSummary();
4664 if( id2hrn.containsKey(idSum) ) {
4665 out.add(id2hrn.get(idSum) );
4668 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4669 Integer idI = as.getIthOldest(i);
4670 if( id2hrn.containsKey(idI) ) {
4671 out.add(id2hrn.get(idI) );
4678 // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4679 // from the given allocation site, if any, from regions for that
4680 // site that exist in this graph
4681 protected Set<ReachTuple> getAnyExisting(AllocSite as,
4682 boolean includeARITY_ZEROORMORE,
4683 boolean includeARITY_ONE) {
4685 Set<ReachTuple> out = new HashSet<ReachTuple>();
4687 Integer idSum = as.getSummary();
4688 if( id2hrn.containsKey(idSum) ) {
4690 HeapRegionNode hrn = id2hrn.get(idSum);
4691 assert !hrn.isOutOfContext();
4693 if( !includeARITY_ZEROORMORE ) {
4694 out.add(ReachTuple.factory(hrn.getID(),
4695 true, // multi-obj region
4696 ReachTuple.ARITY_ZEROORMORE,
4701 if( includeARITY_ONE ) {
4702 out.add(ReachTuple.factory(hrn.getID(),
4703 true, // multi-object region
4704 ReachTuple.ARITY_ONE,
4710 if( !includeARITY_ONE ) {
4711 // no need to do the single-object regions that
4712 // only have an ARITY ONE possible
4716 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4718 Integer idI = as.getIthOldest(i);
4719 if( id2hrn.containsKey(idI) ) {
4721 HeapRegionNode hrn = id2hrn.get(idI);
4722 assert !hrn.isOutOfContext();
4724 out.add(ReachTuple.factory(hrn.getID(),
4725 false, // multi-object region
4726 ReachTuple.ARITY_ONE,
4736 // if an object allocated at the target site may be
4737 // reachable from both an object from root1 and an
4738 // object allocated at root2, return TRUE
4739 public boolean mayBothReachTarget(AllocSite asRoot1,
4741 AllocSite asTarget) {
4743 // consider all heap regions of the target and look
4744 // for a reach state that indicates regions of root1
4745 // and root2 might be able to reach same object
4746 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4748 // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4749 Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4750 Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4752 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4753 while( hrnItr.hasNext() ) {
4754 HeapRegionNode hrn = hrnItr.next();
4756 Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4757 while( rtItr1.hasNext() ) {
4758 ReachTuple rt1 = rtItr1.next();
4760 Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4761 while( rtItr2.hasNext() ) {
4762 ReachTuple rt2 = rtItr2.next();
4764 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4774 // similar to the method above, return TRUE if ever
4775 // more than one object from the root allocation site
4776 // may reach an object from the target site
4777 public boolean mayManyReachTarget(AllocSite asRoot,
4778 AllocSite asTarget) {
4780 // consider all heap regions of the target and look
4781 // for a reach state that multiple objects of root
4782 // might be able to reach the same object
4783 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4785 // get relevant reach tuples
4786 Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true, false);
4787 Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4789 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4790 while( hrnItr.hasNext() ) {
4791 HeapRegionNode hrn = hrnItr.next();
4793 // if any ZERORMORE tuples are here, TRUE
4794 Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4795 while( rtItr.hasNext() ) {
4796 ReachTuple rtZOM = rtItr.next();
4798 if( hrn.getAlpha().containsTuple(rtZOM) ) {
4803 // otherwise, look for any pair of ONE tuples
4804 Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4805 while( rtItr1.hasNext() ) {
4806 ReachTuple rt1 = rtItr1.next();
4808 Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4809 while( rtItr2.hasNext() ) {
4810 ReachTuple rt2 = rtItr2.next();
4816 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4830 public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4832 Set<HeapRegionNode> exhibitProofState =
4833 new HashSet<HeapRegionNode>();
4835 Iterator hrnItr = id2hrn.entrySet().iterator();
4836 while( hrnItr.hasNext() ) {
4837 Map.Entry me = (Map.Entry)hrnItr.next();
4838 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4840 ReachSet intersection =
4841 Canonical.intersection(proofOfSharing,
4844 if( !intersection.isEmpty() ) {
4845 assert !hrn.isOutOfContext();
4846 exhibitProofState.add(hrn);
4850 return exhibitProofState;
4854 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4855 HeapRegionNode hrn2) {
4856 assert hrn1 != null;
4857 assert hrn2 != null;
4859 assert !hrn1.isOutOfContext();
4860 assert !hrn2.isOutOfContext();
4862 assert belongsToThis(hrn1);
4863 assert belongsToThis(hrn2);
4865 assert !hrn1.getID().equals(hrn2.getID() );
4868 // then get the various tokens for these heap regions
4870 ReachTuple.factory(hrn1.getID(),
4871 !hrn1.isSingleObject(), // multi?
4872 ReachTuple.ARITY_ONE,
4875 ReachTuple h1star = null;
4876 if( !hrn1.isSingleObject() ) {
4878 ReachTuple.factory(hrn1.getID(),
4879 !hrn1.isSingleObject(),
4880 ReachTuple.ARITY_ZEROORMORE,
4885 ReachTuple.factory(hrn2.getID(),
4886 !hrn2.isSingleObject(),
4887 ReachTuple.ARITY_ONE,
4890 ReachTuple h2star = null;
4891 if( !hrn2.isSingleObject() ) {
4893 ReachTuple.factory(hrn2.getID(),
4894 !hrn2.isSingleObject(),
4895 ReachTuple.ARITY_ZEROORMORE,
4899 // then get the merged beta of all out-going edges from these heap
4902 ReachSet beta1 = ReachSet.factory();
4903 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4904 while (itrEdge.hasNext()) {
4905 RefEdge edge = itrEdge.next();
4906 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4909 ReachSet beta2 = ReachSet.factory();
4910 itrEdge = hrn2.iteratorToReferencees();
4911 while (itrEdge.hasNext()) {
4912 RefEdge edge = itrEdge.next();
4913 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4916 ReachSet proofOfSharing = ReachSet.factory();
4919 Canonical.unionORpreds(proofOfSharing,
4920 beta1.getStatesWithBoth(h1, h2)
4923 Canonical.unionORpreds(proofOfSharing,
4924 beta2.getStatesWithBoth(h1, h2)
4927 if( !hrn1.isSingleObject() ) {
4929 Canonical.unionORpreds(proofOfSharing,
4930 beta1.getStatesWithBoth(h1star, h2)
4933 Canonical.unionORpreds(proofOfSharing,
4934 beta2.getStatesWithBoth(h1star, h2)
4938 if( !hrn2.isSingleObject() ) {
4940 Canonical.unionORpreds(proofOfSharing,
4941 beta1.getStatesWithBoth(h1, h2star)
4944 Canonical.unionORpreds(proofOfSharing,
4945 beta2.getStatesWithBoth(h1, h2star)
4949 if( !hrn1.isSingleObject() &&
4950 !hrn2.isSingleObject()
4953 Canonical.unionORpreds(proofOfSharing,
4954 beta1.getStatesWithBoth(h1star, h2star)
4957 Canonical.unionORpreds(proofOfSharing,
4958 beta2.getStatesWithBoth(h1star, h2star)
4962 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4963 if( !proofOfSharing.isEmpty() ) {
4964 common = findCommonReachableNodes(proofOfSharing);
4965 if( !DISABLE_STRONG_UPDATES &&
4966 !DISABLE_GLOBAL_SWEEP
4968 assert !common.isEmpty();
4975 // this version of the above method checks whether there is sharing
4976 // among the objects in a summary node
4977 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4979 assert hrn.isNewSummary();
4980 assert !hrn.isOutOfContext();
4981 assert belongsToThis(hrn);
4984 ReachTuple.factory(hrn.getID(),
4986 ReachTuple.ARITY_ZEROORMORE,
4989 // then get the merged beta of all out-going edges from
4992 ReachSet beta = ReachSet.factory();
4993 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4994 while (itrEdge.hasNext()) {
4995 RefEdge edge = itrEdge.next();
4996 beta = Canonical.unionORpreds(beta, edge.getBeta());
4999 ReachSet proofOfSharing = ReachSet.factory();
5002 Canonical.unionORpreds(proofOfSharing,
5003 beta.getStatesWithBoth(hstar, hstar)
5006 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5007 if( !proofOfSharing.isEmpty() ) {
5008 common = findCommonReachableNodes(proofOfSharing);
5009 if( !DISABLE_STRONG_UPDATES &&
5010 !DISABLE_GLOBAL_SWEEP
5012 assert !common.isEmpty();
5020 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5021 Integer paramIndex1,
5022 Integer paramIndex2) {
5024 // get parameter's heap regions
5025 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5026 assert this.hasVariable(paramTemp1);
5027 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5030 if( !(paramVar1.getNumReferencees() == 1) ) {
5031 System.out.println("\n fm="+fm+"\n param="+paramTemp1);
5032 writeGraph("whatup");
5036 assert paramVar1.getNumReferencees() == 1;
5037 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5038 HeapRegionNode hrnParam1 = paramEdge1.getDst();
5040 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5041 assert this.hasVariable(paramTemp2);
5042 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5044 if( !(paramVar2.getNumReferencees() == 1) ) {
5045 System.out.println("\n fm="+fm+"\n param="+paramTemp2);
5046 writeGraph("whatup");
5049 assert paramVar2.getNumReferencees() == 1;
5050 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5051 HeapRegionNode hrnParam2 = paramEdge2.getDst();
5053 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5054 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5059 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5063 // get parameter's heap regions
5064 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5065 assert this.hasVariable(paramTemp);
5066 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5067 assert paramVar.getNumReferencees() == 1;
5068 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5069 HeapRegionNode hrnParam = paramEdge.getDst();
5072 HeapRegionNode hrnSummary=null;
5073 if(id2hrn.containsKey(as.getSummary())) {
5074 // if summary node doesn't exist, ignore this case
5075 hrnSummary = id2hrn.get(as.getSummary());
5076 assert hrnSummary != null;
5079 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5080 if(hrnSummary!=null) {
5081 common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5084 // check for other nodes
5085 for (int i = 0; i < as.getAllocationDepth(); ++i) {
5087 assert id2hrn.containsKey(as.getIthOldest(i));
5088 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5089 assert hrnIthOldest != null;
5091 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5098 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5101 // get summary node 1's alpha
5102 Integer idSum1 = as1.getSummary();
5103 HeapRegionNode hrnSum1=null;
5104 if(id2hrn.containsKey(idSum1)) {
5105 hrnSum1 = id2hrn.get(idSum1);
5108 // get summary node 2's alpha
5109 Integer idSum2 = as2.getSummary();
5110 HeapRegionNode hrnSum2=null;
5111 if(id2hrn.containsKey(idSum2)) {
5112 hrnSum2 = id2hrn.get(idSum2);
5115 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5116 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5117 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5121 // ask if objects from this summary share among each other
5122 common.addAll(mayReachSharedObjects(hrnSum1));
5125 // check sum2 against alloc1 nodes
5127 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5128 Integer idI1 = as1.getIthOldest(i);
5129 assert id2hrn.containsKey(idI1);
5130 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5131 assert hrnI1 != null;
5132 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5135 // also ask if objects from this summary share among each other
5136 common.addAll(mayReachSharedObjects(hrnSum2));
5139 // check sum1 against alloc2 nodes
5140 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5141 Integer idI2 = as2.getIthOldest(i);
5142 assert id2hrn.containsKey(idI2);
5143 HeapRegionNode hrnI2 = id2hrn.get(idI2);
5144 assert hrnI2 != null;
5147 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5150 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5151 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5152 Integer idI1 = as1.getIthOldest(j);
5154 // if these are the same site, don't look for the same token, no
5156 // different tokens of the same site could alias together though
5157 if (idI1.equals(idI2)) {
5161 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5163 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5170 public void makeInaccessible(Set<TempDescriptor> vars) {
5171 inaccessibleVars.addAll(vars);
5174 public void makeInaccessible(TempDescriptor td) {
5175 inaccessibleVars.add(td);
5178 public void makeAccessible(TempDescriptor td) {
5179 inaccessibleVars.remove(td);
5182 public boolean isAccessible(TempDescriptor td) {
5183 return !inaccessibleVars.contains(td);
5186 public Set<TempDescriptor> getInaccessibleVars() {
5187 return inaccessibleVars;
5193 public Set<Alloc> canPointTo( TempDescriptor x ) {
5195 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5196 // if we don't care to track it, return null which means
5197 // "a client of this result shouldn't care either"
5198 return HeapAnalysis.DONTCARE_PTR;
5201 Set<Alloc> out = new HashSet<Alloc>();
5203 VariableNode vn = getVariableNodeNoMutation( x );
5205 // the empty set means "can't point to anything"
5209 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5210 while( edgeItr.hasNext() ) {
5211 HeapRegionNode hrn = edgeItr.next().getDst();
5212 out.add( hrn.getAllocSite() );
5220 public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5222 TypeDescriptor fieldType ) {
5224 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5225 // if we don't care to track it, return null which means
5226 // "a client of this result shouldn't care either"
5227 return HeapAnalysis.DONTCARE_DREF;
5230 Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5232 VariableNode vn = getVariableNodeNoMutation( x );
5234 // the empty table means "x can't point to anything"
5238 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5239 while( edgeItr.hasNext() ) {
5240 HeapRegionNode hrn = edgeItr.next().getDst();
5241 Alloc key = hrn.getAllocSite();
5243 if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5244 // if we don't care to track it, put no entry which means
5245 // "a client of this result shouldn't care either"
5246 out.put( key, HeapAnalysis.DONTCARE_PTR );
5250 Set<Alloc> moreValues = new HashSet<Alloc>();
5251 Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5252 while( edgeItr2.hasNext() ) {
5253 RefEdge edge = edgeItr2.next();
5255 if( field.equals( edge.getField() ) ) {
5256 moreValues.add( edge.getDst().getAllocSite() );
5260 if( out.containsKey( key ) ) {
5261 out.get( key ).addAll( moreValues );
5263 out.put( key, moreValues );
5273 public TempDescriptor findVariableByName( String name ) {
5275 for( TempDescriptor td: td2vn.keySet() ) {
5276 if( td.getSymbol().contains( name ) ) {