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 private static boolean resolveMethodDebugDOTwriteLabels = true;
2260 private static boolean resolveMethodDebugDOTselectTemps = true;
2261 private static boolean resolveMethodDebugDOTpruneGarbage = true;
2262 private static boolean resolveMethodDebugDOThideReach = false;
2263 private static boolean resolveMethodDebugDOThideSubsetReach = true;
2264 private static boolean resolveMethodDebugDOThidePreds = false;
2265 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
2267 static String debugGraphPrefix;
2268 static int debugCallSiteVisitCounter;
2269 static int debugCallSiteVisitStartCapture;
2270 static int debugCallSiteNumVisitsToCapture;
2271 static boolean debugCallSiteStopAfter;
2275 resolveMethodCall(FlatCall fc,
2276 FlatMethod fmCallee,
2277 ReachGraph rgCallee,
2278 Set<Integer> callerNodeIDsCopiedToCallee,
2279 boolean writeDebugDOTs
2282 if( writeDebugDOTs ) {
2284 System.out.println(" Writing out visit "+
2285 debugCallSiteVisitCounter+
2286 " to debug call site");
2288 debugGraphPrefix = String.format("call%03d",
2289 debugCallSiteVisitCounter);
2291 rgCallee.writeGraph(debugGraphPrefix+"callee",
2292 resolveMethodDebugDOTwriteLabels,
2293 resolveMethodDebugDOTselectTemps,
2294 resolveMethodDebugDOTpruneGarbage,
2295 resolveMethodDebugDOThideReach,
2296 resolveMethodDebugDOThideSubsetReach,
2297 resolveMethodDebugDOThidePreds,
2298 resolveMethodDebugDOThideEdgeTaints);
2300 writeGraph(debugGraphPrefix+"caller00In",
2301 resolveMethodDebugDOTwriteLabels,
2302 resolveMethodDebugDOTselectTemps,
2303 resolveMethodDebugDOTpruneGarbage,
2304 resolveMethodDebugDOThideReach,
2305 resolveMethodDebugDOThideSubsetReach,
2306 resolveMethodDebugDOThidePreds,
2307 resolveMethodDebugDOThideEdgeTaints,
2308 callerNodeIDsCopiedToCallee);
2313 // method call transfer function steps:
2314 // 1. Use current callee-reachable heap (CRH) to test callee
2315 // predicates and mark what will be coming in.
2316 // 2. Wipe CRH out of caller.
2317 // 3. Transplant marked callee parts in:
2318 // a) bring in nodes
2319 // b) bring in callee -> callee edges
2320 // c) resolve out-of-context -> callee edges
2321 // d) assign return value
2322 // 4. Collapse shadow nodes down
2323 // 5. Global sweep it.
2326 // 1. mark what callee elements have satisfied predicates
2327 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
2328 new Hashtable<HeapRegionNode, ExistPredSet>();
2330 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
2331 new Hashtable<RefEdge, ExistPredSet>();
2333 Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
2334 calleeNode2calleeStatesSatisfied =
2335 new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
2337 Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
2338 calleeEdge2calleeStatesSatisfied =
2339 new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
2341 Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
2342 calleeEdge2calleeTaintsSatisfied =
2343 new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
2345 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
2346 new Hashtable< RefEdge, Set<RefSrcNode> >();
2350 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2351 while( meItr.hasNext() ) {
2352 Map.Entry me = (Map.Entry)meItr.next();
2353 Integer id = (Integer) me.getKey();
2354 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2356 // if a callee element's predicates are satisfied then a set
2357 // of CALLER predicates is returned: they are the predicates
2358 // that the callee element moved into the caller context
2359 // should have, and it is inefficient to find this again later
2360 ExistPredSet predsIfSatis =
2361 hrnCallee.getPreds().isSatisfiedBy(this,
2362 callerNodeIDsCopiedToCallee,
2365 if( predsIfSatis != null ) {
2366 calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
2368 // otherwise don't bother looking at edges to this node
2374 // since the node is coming over, find out which reach
2375 // states on it should come over, too
2376 assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
2378 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2379 while( stateItr.hasNext() ) {
2380 ReachState stateCallee = stateItr.next();
2383 stateCallee.getPreds().isSatisfiedBy(this,
2384 callerNodeIDsCopiedToCallee,
2386 if( predsIfSatis != null ) {
2388 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2389 calleeNode2calleeStatesSatisfied.get(hrnCallee);
2391 if( calleeStatesSatisfied == null ) {
2392 calleeStatesSatisfied =
2393 new Hashtable<ReachState, ExistPredSet>();
2395 calleeNode2calleeStatesSatisfied.put(hrnCallee, calleeStatesSatisfied);
2398 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2402 // then look at edges to the node
2403 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2404 while( reItr.hasNext() ) {
2405 RefEdge reCallee = reItr.next();
2406 RefSrcNode rsnCallee = reCallee.getSrc();
2408 // (caller local variables to in-context heap regions)
2409 // have an (out-of-context heap region -> in-context heap region)
2410 // abstraction in the callEE, so its true we never need to
2411 // look at a (var node -> heap region) edge in callee to bring
2412 // those over for the call site transfer, except for the special
2413 // case of *RETURN var* -> heap region edges.
2414 // What about (param var->heap region)
2415 // edges in callee? They are dealt with below this loop.
2417 if( rsnCallee instanceof VariableNode ) {
2419 // looking for the return-value variable only
2420 VariableNode vnCallee = (VariableNode) rsnCallee;
2421 if( vnCallee.getTempDescriptor() != tdReturn ) {
2425 TempDescriptor returnTemp = fc.getReturnTemp();
2426 if( returnTemp == null ||
2427 !DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2432 // note that the assignment of the return value is to a
2433 // variable in the caller which is out-of-context with
2434 // respect to the callee
2435 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2436 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2437 rsnCallers.add(vnLhsCaller);
2438 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2442 // for HeapRegionNode callee sources...
2444 // first see if the source is out-of-context, and only
2445 // proceed with this edge if we find some caller-context
2447 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2448 boolean matchedOutOfContext = false;
2450 if( !hrnSrcCallee.isOutOfContext() ) {
2453 hrnSrcCallee.getPreds().isSatisfiedBy(this,
2454 callerNodeIDsCopiedToCallee,
2456 if( predsIfSatis != null ) {
2457 calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
2459 // otherwise forget this edge
2464 // hrnSrcCallee is out-of-context
2465 assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
2467 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2469 // use the isSatisfiedBy with a non-null callers set to capture
2470 // nodes in the caller that match the predicates
2471 reCallee.getPreds().isSatisfiedBy( this,
2472 callerNodeIDsCopiedToCallee,
2475 if( !rsnCallers.isEmpty() ) {
2476 matchedOutOfContext = true;
2477 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2481 if( hrnSrcCallee.isOutOfContext() &&
2482 !matchedOutOfContext ) {
2489 reCallee.getPreds().isSatisfiedBy(this,
2490 callerNodeIDsCopiedToCallee,
2494 if( predsIfSatis != null ) {
2495 calleeEdgesSatisfied.put(reCallee, predsIfSatis);
2497 // since the edge is coming over, find out which reach
2498 // states on it should come over, too
2499 assert calleeEdge2calleeStatesSatisfied.get(reCallee) == null;
2501 stateItr = reCallee.getBeta().iterator();
2502 while( stateItr.hasNext() ) {
2503 ReachState stateCallee = stateItr.next();
2506 stateCallee.getPreds().isSatisfiedBy(this,
2507 callerNodeIDsCopiedToCallee,
2509 if( predsIfSatis != null ) {
2511 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2512 calleeEdge2calleeStatesSatisfied.get(reCallee);
2514 if( calleeStatesSatisfied == null ) {
2515 calleeStatesSatisfied =
2516 new Hashtable<ReachState, ExistPredSet>();
2518 calleeEdge2calleeStatesSatisfied.put(reCallee, calleeStatesSatisfied);
2521 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2525 // since the edge is coming over, find out which taints
2526 // on it should come over, too
2527 assert calleeEdge2calleeTaintsSatisfied.get(reCallee) == null;
2529 Iterator<Taint> tItr = reCallee.getTaints().iterator();
2530 while( tItr.hasNext() ) {
2531 Taint tCallee = tItr.next();
2534 tCallee.getPreds().isSatisfiedBy(this,
2535 callerNodeIDsCopiedToCallee,
2537 if( predsIfSatis != null ) {
2539 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2540 calleeEdge2calleeTaintsSatisfied.get(reCallee);
2542 if( calleeTaintsSatisfied == null ) {
2543 calleeTaintsSatisfied =
2544 new Hashtable<Taint, ExistPredSet>();
2546 calleeEdge2calleeTaintsSatisfied.put(reCallee, calleeTaintsSatisfied);
2549 calleeTaintsSatisfied.put(tCallee, predsIfSatis);
2556 if( writeDebugDOTs ) {
2557 writeGraph(debugGraphPrefix+"caller20BeforeWipe",
2558 resolveMethodDebugDOTwriteLabels,
2559 resolveMethodDebugDOTselectTemps,
2560 resolveMethodDebugDOTpruneGarbage,
2561 resolveMethodDebugDOThideReach,
2562 resolveMethodDebugDOThideSubsetReach,
2563 resolveMethodDebugDOThidePreds,
2564 resolveMethodDebugDOThideEdgeTaints);
2568 // 2. predicates tested, ok to wipe out caller part
2569 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2570 while( hrnItr.hasNext() ) {
2571 Integer hrnID = hrnItr.next();
2572 HeapRegionNode hrnCaller = id2hrn.get(hrnID);
2573 assert hrnCaller != null;
2575 // when clearing off nodes, also eliminate variable
2577 wipeOut(hrnCaller, true);
2580 // if we are assigning the return value to something, clobber now
2581 // as part of the wipe
2582 TempDescriptor returnTemp = fc.getReturnTemp();
2583 if( returnTemp != null &&
2584 DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2587 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2588 clearRefEdgesFrom(vnLhsCaller, null, null, true);
2594 if( writeDebugDOTs ) {
2595 writeGraph(debugGraphPrefix+"caller30BeforeAddingNodes",
2596 resolveMethodDebugDOTwriteLabels,
2597 resolveMethodDebugDOTselectTemps,
2598 resolveMethodDebugDOTpruneGarbage,
2599 resolveMethodDebugDOThideReach,
2600 resolveMethodDebugDOThideSubsetReach,
2601 resolveMethodDebugDOThidePreds,
2602 resolveMethodDebugDOThideEdgeTaints);
2608 // 3. callee elements with satisfied preds come in, note that
2609 // the mapping of elements satisfied to preds is like this:
2610 // A callee element EE has preds EEp that are satisfied by
2611 // some caller element ER. We bring EE into the caller
2612 // context as ERee with the preds of ER, namely ERp, which
2613 // in the following algorithm is the value in the mapping
2616 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2617 while( satisItr.hasNext() ) {
2618 Map.Entry me = (Map.Entry)satisItr.next();
2619 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2620 ExistPredSet preds = (ExistPredSet) me.getValue();
2622 // TODO: I think its true that the current implementation uses
2623 // the type of the OOC region and the predicates OF THE EDGE from
2624 // it to link everything up in caller context, so that's why we're
2625 // skipping this... maybe that's a sillier way to do it?
2626 if( hrnCallee.isOutOfContext() ) {
2630 AllocSite as = hrnCallee.getAllocSite();
2633 Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
2635 HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
2636 if( hrnCaller == null ) {
2638 createNewHeapRegionNode(hrnIDshadow, // id or null to generate a new one
2639 hrnCallee.isSingleObject(), // single object?
2640 hrnCallee.isNewSummary(), // summary?
2641 false, // out-of-context?
2642 hrnCallee.getType(), // type
2643 hrnCallee.getAllocSite(), // allocation site
2644 toCallerContext(hrnCallee.getInherent(),
2645 calleeNode2calleeStatesSatisfied.get(hrnCallee) ), // inherent reach
2646 null, // current reach
2647 predsEmpty, // predicates
2648 hrnCallee.getDescription() // description
2651 assert hrnCaller.isWiped();
2654 hrnCaller.setAlpha(toCallerContext(hrnCallee.getAlpha(),
2655 calleeNode2calleeStatesSatisfied.get(hrnCallee)
2659 hrnCaller.setPreds(preds);
2666 if( writeDebugDOTs ) {
2667 writeGraph(debugGraphPrefix+"caller31BeforeAddingEdges",
2668 resolveMethodDebugDOTwriteLabels,
2669 resolveMethodDebugDOTselectTemps,
2670 resolveMethodDebugDOTpruneGarbage,
2671 resolveMethodDebugDOThideReach,
2672 resolveMethodDebugDOThideSubsetReach,
2673 resolveMethodDebugDOThidePreds,
2674 resolveMethodDebugDOThideEdgeTaints);
2678 // set these up during the next procedure so after
2679 // the caller has all of its nodes and edges put
2680 // back together we can propagate the callee's
2681 // reach changes backwards into the caller graph
2682 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2684 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2685 new Hashtable<RefEdge, ChangeSet>();
2688 // 3.b) callee -> callee edges AND out-of-context -> callee
2689 // which includes return temp -> callee edges now, too
2690 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2691 while( satisItr.hasNext() ) {
2692 Map.Entry me = (Map.Entry)satisItr.next();
2693 RefEdge reCallee = (RefEdge) me.getKey();
2694 ExistPredSet preds = (ExistPredSet) me.getValue();
2696 HeapRegionNode hrnDstCallee = reCallee.getDst();
2697 AllocSite asDst = hrnDstCallee.getAllocSite();
2698 allocSites.add(asDst);
2700 Integer hrnIDDstShadow =
2701 asDst.getShadowIDfromID(hrnDstCallee.getID() );
2703 HeapRegionNode hrnDstCaller = id2hrn.get(hrnIDDstShadow);
2704 assert hrnDstCaller != null;
2707 RefSrcNode rsnCallee = reCallee.getSrc();
2709 Set<RefSrcNode> rsnCallers =
2710 new HashSet<RefSrcNode>();
2712 Set<RefSrcNode> oocCallers =
2713 calleeEdges2oocCallerSrcMatches.get(reCallee);
2715 if( rsnCallee instanceof HeapRegionNode ) {
2716 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2717 if( hrnCalleeSrc.isOutOfContext() ) {
2718 assert oocCallers != null;
2723 if( oocCallers == null ) {
2724 // there are no out-of-context matches, so it's
2725 // either a param/arg var or one in-context heap region
2726 if( rsnCallee instanceof VariableNode ) {
2727 // variable -> node in the callee should only
2728 // come into the caller if its from a param var
2729 VariableNode vnCallee = (VariableNode) rsnCallee;
2730 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2731 TempDescriptor tdArg = fc.getArgMatchingParam(fmCallee,
2733 if( tdArg == null ) {
2734 // this means the variable isn't a parameter, its local
2735 // to the callee so we ignore it in call site transfer
2736 // shouldn't this NEVER HAPPEN?
2740 rsnCallers.add(this.getVariableNodeFromTemp(tdArg) );
2743 // otherwise source is in context, one region
2745 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2747 // translate an in-context node to shadow
2748 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2749 allocSites.add(asSrc);
2751 Integer hrnIDSrcShadow =
2752 asSrc.getShadowIDfromID(hrnSrcCallee.getID() );
2754 HeapRegionNode hrnSrcCallerShadow =
2755 this.id2hrn.get(hrnIDSrcShadow);
2757 assert hrnSrcCallerShadow != null;
2759 rsnCallers.add(hrnSrcCallerShadow);
2763 // otherwise we have a set of out-of-context srcs
2764 // that should NOT be translated to shadow nodes
2765 assert !oocCallers.isEmpty();
2766 rsnCallers.addAll(oocCallers);
2769 // now make all caller edges we've identified from
2770 // this callee edge with a satisfied predicate
2771 assert !rsnCallers.isEmpty();
2772 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2773 while( rsnItr.hasNext() ) {
2774 RefSrcNode rsnCaller = rsnItr.next();
2776 RefEdge reCaller = new RefEdge(rsnCaller,
2779 reCallee.getField(),
2780 toCallerContext(reCallee.getBeta(),
2781 calleeEdge2calleeStatesSatisfied.get(reCallee) ),
2783 toCallerContext(reCallee.getTaints(),
2784 calleeEdge2calleeTaintsSatisfied.get(reCallee) )
2787 ChangeSet cs = ChangeSet.factory();
2788 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2789 while( rsItr.hasNext() ) {
2790 ReachState state = rsItr.next();
2791 ExistPredSet predsPreCallee = state.getPreds();
2793 if( state.isEmpty() ) {
2797 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2798 while( predItr.hasNext() ) {
2799 ExistPred pred = predItr.next();
2800 ReachState old = pred.ne_state;
2806 cs = Canonical.add(cs,
2807 ChangeTuple.factory(old,
2814 // we're just going to use the convenient "merge-if-exists"
2815 // edge call below, but still take a separate look if there
2816 // is an existing caller edge to build change sets properly
2817 if( !cs.isEmpty() ) {
2818 RefEdge edgeExisting = rsnCaller.getReferenceTo(hrnDstCaller,
2822 if( edgeExisting != null ) {
2823 ChangeSet csExisting = edgePlannedChanges.get(edgeExisting);
2824 if( csExisting == null ) {
2825 csExisting = ChangeSet.factory();
2827 edgePlannedChanges.put(edgeExisting,
2828 Canonical.union(csExisting,
2833 edgesForPropagation.add(reCaller);
2834 assert !edgePlannedChanges.containsKey(reCaller);
2835 edgePlannedChanges.put(reCaller, cs);
2839 // then add new caller edge or merge
2840 addEdgeOrMergeWithExisting(reCaller);
2848 if( writeDebugDOTs ) {
2849 writeGraph(debugGraphPrefix+"caller38propagateReach",
2850 resolveMethodDebugDOTwriteLabels,
2851 resolveMethodDebugDOTselectTemps,
2852 resolveMethodDebugDOTpruneGarbage,
2853 resolveMethodDebugDOThideReach,
2854 resolveMethodDebugDOThideSubsetReach,
2855 resolveMethodDebugDOThidePreds,
2856 resolveMethodDebugDOThideEdgeTaints);
2859 // propagate callee reachability changes to the rest
2860 // of the caller graph edges
2861 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2863 propagateTokensOverEdges(edgesForPropagation, // source edges
2864 edgePlannedChanges, // map src edge to change set
2865 edgesUpdated); // list of updated edges
2867 // commit beta' (beta<-betaNew)
2868 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2869 while( edgeItr.hasNext() ) {
2870 edgeItr.next().applyBetaNew();
2879 if( writeDebugDOTs ) {
2880 writeGraph(debugGraphPrefix+"caller40BeforeShadowMerge",
2881 resolveMethodDebugDOTwriteLabels,
2882 resolveMethodDebugDOTselectTemps,
2883 resolveMethodDebugDOTpruneGarbage,
2884 resolveMethodDebugDOThideReach,
2885 resolveMethodDebugDOThideSubsetReach,
2886 resolveMethodDebugDOThidePreds,
2887 resolveMethodDebugDOThideEdgeTaints);
2891 // 4) merge shadow nodes so alloc sites are back to k
2892 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2893 while( asItr.hasNext() ) {
2894 // for each allocation site do the following to merge
2895 // shadow nodes (newest from callee) with any existing
2896 // look for the newest normal and newest shadow "slot"
2897 // not being used, transfer normal to shadow. Keep
2898 // doing this until there are no more normal nodes, or
2899 // no empty shadow slots: then merge all remaining normal
2900 // nodes into the shadow summary. Finally, convert all
2901 // shadow to their normal versions.
2902 AllocSite as = asItr.next();
2906 while( ageNorm < allocationDepth &&
2907 ageShad < allocationDepth ) {
2909 // first, are there any normal nodes left?
2910 Integer idNorm = as.getIthOldest(ageNorm);
2911 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2912 if( hrnNorm == null ) {
2913 // no, this age of normal node not in the caller graph
2918 // yes, a normal node exists, is there an empty shadow
2919 // "slot" to transfer it onto?
2920 HeapRegionNode hrnShad = getIthNode(as, ageShad, true);
2921 if( !hrnShad.isWiped() ) {
2922 // no, this age of shadow node is not empty
2927 // yes, this shadow node is empty
2928 transferOnto(hrnNorm, hrnShad);
2933 // now, while there are still normal nodes but no shadow
2934 // slots, merge normal nodes into the shadow summary
2935 while( ageNorm < allocationDepth ) {
2937 // first, are there any normal nodes left?
2938 Integer idNorm = as.getIthOldest(ageNorm);
2939 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2940 if( hrnNorm == null ) {
2941 // no, this age of normal node not in the caller graph
2946 // yes, a normal node exists, so get the shadow summary
2947 HeapRegionNode summShad = getSummaryNode(as, true);
2948 mergeIntoSummary(hrnNorm, summShad);
2950 // now tokens in reachability sets need to age also
2951 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2952 while( itrAllHRNodes.hasNext() ) {
2953 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
2954 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
2956 ageTuplesFrom(as, hrnToAge);
2958 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
2959 while( itrEdges.hasNext() ) {
2960 ageTuplesFrom(as, itrEdges.next() );
2967 // if there is a normal summary, merge it into shadow summary
2968 Integer idNorm = as.getSummary();
2969 HeapRegionNode summNorm = id2hrn.get(idNorm);
2970 if( summNorm != null ) {
2971 HeapRegionNode summShad = getSummaryNode(as, true);
2972 mergeIntoSummary(summNorm, summShad);
2975 // finally, flip all existing shadow nodes onto the normal
2976 for( int i = 0; i < allocationDepth; ++i ) {
2977 Integer idShad = as.getIthOldestShadow(i);
2978 HeapRegionNode hrnShad = id2hrn.get(idShad);
2979 if( hrnShad != null ) {
2981 HeapRegionNode hrnNorm = getIthNode(as, i, false);
2982 assert hrnNorm.isWiped();
2983 transferOnto(hrnShad, hrnNorm);
2987 Integer idShad = as.getSummaryShadow();
2988 HeapRegionNode summShad = id2hrn.get(idShad);
2989 if( summShad != null ) {
2990 summNorm = getSummaryNode(as, false);
2991 transferOnto(summShad, summNorm);
3000 if( writeDebugDOTs ) {
3001 writeGraph(debugGraphPrefix+"caller45BeforeUnshadow",
3002 resolveMethodDebugDOTwriteLabels,
3003 resolveMethodDebugDOTselectTemps,
3004 resolveMethodDebugDOTpruneGarbage,
3005 resolveMethodDebugDOThideReach,
3006 resolveMethodDebugDOThideSubsetReach,
3007 resolveMethodDebugDOThidePreds,
3008 resolveMethodDebugDOThideEdgeTaints);
3012 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3013 while( itrAllHRNodes.hasNext() ) {
3014 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
3015 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3017 hrn.setAlpha(unshadow(hrn.getAlpha() ) );
3019 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
3020 while( itrEdges.hasNext() ) {
3021 RefEdge re = itrEdges.next();
3022 re.setBeta(unshadow(re.getBeta() ) );
3029 if( writeDebugDOTs ) {
3030 writeGraph(debugGraphPrefix+"caller50BeforeGlobalSweep",
3031 resolveMethodDebugDOTwriteLabels,
3032 resolveMethodDebugDOTselectTemps,
3033 resolveMethodDebugDOTpruneGarbage,
3034 resolveMethodDebugDOThideReach,
3035 resolveMethodDebugDOThideSubsetReach,
3036 resolveMethodDebugDOThidePreds,
3037 resolveMethodDebugDOThideEdgeTaints);
3042 if( !DISABLE_GLOBAL_SWEEP ) {
3047 if( writeDebugDOTs ) {
3048 writeGraph(debugGraphPrefix+"caller90AfterTransfer",
3049 resolveMethodDebugDOTwriteLabels,
3050 resolveMethodDebugDOTselectTemps,
3051 resolveMethodDebugDOTpruneGarbage,
3052 resolveMethodDebugDOThideReach,
3053 resolveMethodDebugDOThideSubsetReach,
3054 resolveMethodDebugDOThidePreds,
3055 resolveMethodDebugDOThideEdgeTaints);
3061 ////////////////////////////////////////////////////
3063 // Abstract garbage collection simply removes
3064 // heap region nodes that are not mechanically
3065 // reachable from a root set. This step is
3066 // essential for testing node and edge existence
3067 // predicates efficiently
3069 ////////////////////////////////////////////////////
3070 public void abstractGarbageCollect(Set<TempDescriptor> liveSet) {
3072 // calculate a root set, will be different for Java
3073 // version of analysis versus Bamboo version
3074 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3076 // visit every variable in graph while building root
3077 // set, and do iterating on a copy, so we can remove
3078 // dead variables while we're at this
3079 Iterator makeCopyItr = td2vn.entrySet().iterator();
3080 Set entrysCopy = new HashSet();
3081 while( makeCopyItr.hasNext() ) {
3082 entrysCopy.add(makeCopyItr.next() );
3085 Iterator eItr = entrysCopy.iterator();
3086 while( eItr.hasNext() ) {
3087 Map.Entry me = (Map.Entry)eItr.next();
3088 TempDescriptor td = (TempDescriptor) me.getKey();
3089 VariableNode vn = (VariableNode) me.getValue();
3091 if( liveSet.contains(td) ) {
3095 // dead var, remove completely from graph
3097 clearRefEdgesFrom(vn, null, null, true);
3101 // everything visited in a traversal is
3102 // considered abstractly live
3103 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3105 while( !toVisit.isEmpty() ) {
3106 RefSrcNode rsn = toVisit.iterator().next();
3107 toVisit.remove(rsn);
3110 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3111 while( hrnItr.hasNext() ) {
3112 RefEdge edge = hrnItr.next();
3113 HeapRegionNode hrn = edge.getDst();
3115 if( !visited.contains(hrn) ) {
3121 // get a copy of the set to iterate over because
3122 // we're going to monkey with the graph when we
3123 // identify a garbage node
3124 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3125 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3126 while( hrnItr.hasNext() ) {
3127 hrnAllPrior.add(hrnItr.next() );
3130 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3131 while( hrnAllItr.hasNext() ) {
3132 HeapRegionNode hrn = hrnAllItr.next();
3134 if( !visited.contains(hrn) ) {
3136 // heap region nodes are compared across ReachGraph
3137 // objects by their integer ID, so when discarding
3138 // garbage nodes we must also discard entries in
3139 // the ID -> heap region hashtable.
3140 id2hrn.remove(hrn.getID() );
3142 // RefEdge objects are two-way linked between
3143 // nodes, so when a node is identified as garbage,
3144 // actively clear references to and from it so
3145 // live nodes won't have dangling RefEdge's
3148 // if we just removed the last node from an allocation
3149 // site, it should be taken out of the ReachGraph's list
3150 AllocSite as = hrn.getAllocSite();
3151 if( !hasNodesOf(as) ) {
3152 allocSites.remove(as);
3158 protected boolean hasNodesOf(AllocSite as) {
3159 if( id2hrn.containsKey(as.getSummary() ) ) {
3163 for( int i = 0; i < allocationDepth; ++i ) {
3164 if( id2hrn.containsKey(as.getIthOldest(i) ) ) {
3172 ////////////////////////////////////////////////////
3174 // This global sweep is an optional step to prune
3175 // reachability sets that are not internally
3176 // consistent with the global graph. It should be
3177 // invoked after strong updates or method calls.
3179 ////////////////////////////////////////////////////
3180 public void globalSweep() {
3182 // boldB is part of the phase 1 sweep
3183 // it has an in-context table and an out-of-context table
3184 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3185 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3187 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3188 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3190 // visit every heap region to initialize alphaNew and betaNew,
3191 // and make a map of every hrnID to the source nodes it should
3192 // propagate forward from. In-context flagged hrnID's propagate
3193 // from only the in-context node they name, but out-of-context
3194 // ID's may propagate from several out-of-context nodes
3195 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3196 new Hashtable< Integer, Set<HeapRegionNode> >();
3198 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3199 new Hashtable< Integer, Set<HeapRegionNode> >();
3202 Iterator itrHrns = id2hrn.entrySet().iterator();
3203 while( itrHrns.hasNext() ) {
3204 Map.Entry me = (Map.Entry)itrHrns.next();
3205 Integer hrnID = (Integer) me.getKey();
3206 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3208 // assert that this node and incoming edges have clean alphaNew
3209 // and betaNew sets, respectively
3210 assert rsetEmpty.equals(hrn.getAlphaNew() );
3212 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3213 while( itrRers.hasNext() ) {
3214 RefEdge edge = itrRers.next();
3215 assert rsetEmpty.equals(edge.getBetaNew() );
3218 // make a mapping of IDs to heap regions they propagate from
3219 if( hrn.isFlagged() ) {
3220 assert !hrn.isOutOfContext();
3221 assert !icID2srcs.containsKey(hrn.getID() );
3223 // in-context flagged node IDs simply propagate from the
3225 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3227 icID2srcs.put(hrn.getID(), srcs);
3230 if( hrn.isOutOfContext() ) {
3231 assert !hrn.isFlagged();
3233 // the reachability states on an out-of-context
3234 // node are not really important (combinations of
3235 // IDs or arity)--what matters is that the states
3236 // specify which nodes this out-of-context node
3237 // stands in for. For example, if the state [17?, 19*]
3238 // appears on the ooc node, it may serve as a source
3239 // for node 17? and a source for node 19.
3240 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3241 while( stateItr.hasNext() ) {
3242 ReachState state = stateItr.next();
3244 Iterator<ReachTuple> rtItr = state.iterator();
3245 while( rtItr.hasNext() ) {
3246 ReachTuple rt = rtItr.next();
3247 assert rt.isOutOfContext();
3249 Set<HeapRegionNode> srcs = oocID2srcs.get(rt.getHrnID() );
3250 if( srcs == null ) {
3251 srcs = new HashSet<HeapRegionNode>();
3254 oocID2srcs.put(rt.getHrnID(), srcs);
3260 // calculate boldB for all hrnIDs identified by the above
3261 // node traversal, propagating from every source
3262 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3265 Set<HeapRegionNode> srcs;
3268 if( !icID2srcs.isEmpty() ) {
3269 Map.Entry me = (Map.Entry)icID2srcs.entrySet().iterator().next();
3270 hrnID = (Integer) me.getKey();
3271 srcs = (Set<HeapRegionNode>)me.getValue();
3273 icID2srcs.remove(hrnID);
3276 assert !oocID2srcs.isEmpty();
3278 Map.Entry me = (Map.Entry)oocID2srcs.entrySet().iterator().next();
3279 hrnID = (Integer) me.getKey();
3280 srcs = (Set<HeapRegionNode>)me.getValue();
3282 oocID2srcs.remove(hrnID);
3286 Hashtable<RefEdge, ReachSet> boldB_f =
3287 new Hashtable<RefEdge, ReachSet>();
3289 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3291 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3292 while( hrnItr.hasNext() ) {
3293 HeapRegionNode hrn = hrnItr.next();
3295 assert workSetEdges.isEmpty();
3297 // initial boldB_f constraints
3298 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3299 while( itrRees.hasNext() ) {
3300 RefEdge edge = itrRees.next();
3302 assert !boldB_f.containsKey(edge);
3303 boldB_f.put(edge, edge.getBeta() );
3305 assert !workSetEdges.contains(edge);
3306 workSetEdges.add(edge);
3309 // enforce the boldB_f constraint at edges until we reach a fixed point
3310 while( !workSetEdges.isEmpty() ) {
3311 RefEdge edge = workSetEdges.iterator().next();
3312 workSetEdges.remove(edge);
3314 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3315 while( itrPrime.hasNext() ) {
3316 RefEdge edgePrime = itrPrime.next();
3318 ReachSet prevResult = boldB_f.get(edgePrime);
3319 ReachSet intersection = Canonical.intersection(boldB_f.get(edge),
3323 if( prevResult == null ||
3324 Canonical.unionORpreds(prevResult,
3325 intersection).size()
3329 if( prevResult == null ) {
3330 boldB_f.put(edgePrime,
3331 Canonical.unionORpreds(edgePrime.getBeta(),
3336 boldB_f.put(edgePrime,
3337 Canonical.unionORpreds(prevResult,
3342 workSetEdges.add(edgePrime);
3349 boldBic.put(hrnID, boldB_f);
3351 boldBooc.put(hrnID, boldB_f);
3356 // use boldB to prune hrnIDs from alpha states that are impossible
3357 // and propagate the differences backwards across edges
3358 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3360 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3361 new Hashtable<RefEdge, ChangeSet>();
3364 itrHrns = id2hrn.entrySet().iterator();
3365 while( itrHrns.hasNext() ) {
3366 Map.Entry me = (Map.Entry)itrHrns.next();
3367 Integer hrnID = (Integer) me.getKey();
3368 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3370 // out-of-context nodes don't participate in the
3371 // global sweep, they serve as sources for the pass
3373 if( hrn.isOutOfContext() ) {
3377 // the inherent states of a region are the exception
3378 // to removal as the global sweep prunes
3379 ReachTuple rtException = ReachTuple.factory(hrnID,
3380 !hrn.isSingleObject(),
3381 ReachTuple.ARITY_ONE,
3382 false // out-of-context
3385 ChangeSet cts = ChangeSet.factory();
3387 // mark hrnIDs for removal
3388 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3389 while( stateItr.hasNext() ) {
3390 ReachState stateOld = stateItr.next();
3392 ReachState markedHrnIDs = ReachState.factory();
3394 Iterator<ReachTuple> rtItr = stateOld.iterator();
3395 while( rtItr.hasNext() ) {
3396 ReachTuple rtOld = rtItr.next();
3398 // never remove the inherent hrnID from a flagged region
3399 // because it is trivially satisfied
3400 if( hrn.isFlagged() ) {
3401 if( rtOld == rtException ) {
3406 // does boldB allow this hrnID?
3407 boolean foundState = false;
3408 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3409 while( incidentEdgeItr.hasNext() ) {
3410 RefEdge incidentEdge = incidentEdgeItr.next();
3412 Hashtable<RefEdge, ReachSet> B;
3413 if( rtOld.isOutOfContext() ) {
3414 B = boldBooc.get(rtOld.getHrnID() );
3417 if( !id2hrn.containsKey(rtOld.getHrnID() ) ) {
3418 // let symbols not in the graph get pruned
3422 B = boldBic.get(rtOld.getHrnID() );
3426 ReachSet boldB_rtOld_incident = B.get(incidentEdge);
3427 if( boldB_rtOld_incident != null &&
3428 boldB_rtOld_incident.containsIgnorePreds(stateOld) != null
3436 markedHrnIDs = Canonical.addUpArity(markedHrnIDs, rtOld);
3440 // if there is nothing marked, just move on
3441 if( markedHrnIDs.isEmpty() ) {
3442 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3449 // remove all marked hrnIDs and establish a change set that should
3450 // propagate backwards over edges from this node
3451 ReachState statePruned = ReachState.factory();
3452 rtItr = stateOld.iterator();
3453 while( rtItr.hasNext() ) {
3454 ReachTuple rtOld = rtItr.next();
3456 if( !markedHrnIDs.containsTuple(rtOld) ) {
3457 statePruned = Canonical.addUpArity(statePruned, rtOld);
3460 assert !stateOld.equals(statePruned);
3462 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3466 ChangeTuple ct = ChangeTuple.factory(stateOld,
3469 cts = Canonical.add(cts, ct);
3472 // throw change tuple set on all incident edges
3473 if( !cts.isEmpty() ) {
3474 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3475 while( incidentEdgeItr.hasNext() ) {
3476 RefEdge incidentEdge = incidentEdgeItr.next();
3478 edgesForPropagation.add(incidentEdge);
3480 if( edgePlannedChanges.get(incidentEdge) == null ) {
3481 edgePlannedChanges.put(incidentEdge, cts);
3483 edgePlannedChanges.put(
3485 Canonical.union(edgePlannedChanges.get(incidentEdge),
3494 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3496 propagateTokensOverEdges(edgesForPropagation,
3500 // at the end of the 1st phase reference edges have
3501 // beta, betaNew that correspond to beta and betaR
3503 // commit beta<-betaNew, so beta=betaR and betaNew
3504 // will represent the beta' calculation in 2nd phase
3506 // commit alpha<-alphaNew because it won't change
3507 HashSet<RefEdge> res = new HashSet<RefEdge>();
3509 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3510 while( nodeItr.hasNext() ) {
3511 HeapRegionNode hrn = nodeItr.next();
3513 // as mentioned above, out-of-context nodes only serve
3514 // as sources of reach states for the sweep, not part
3516 if( hrn.isOutOfContext() ) {
3517 assert hrn.getAlphaNew().equals(rsetEmpty);
3519 hrn.applyAlphaNew();
3522 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3523 while( itrRes.hasNext() ) {
3524 res.add(itrRes.next() );
3530 Iterator<RefEdge> edgeItr = res.iterator();
3531 while( edgeItr.hasNext() ) {
3532 RefEdge edge = edgeItr.next();
3533 HeapRegionNode hrn = edge.getDst();
3535 // commit results of last phase
3536 if( edgesUpdated.contains(edge) ) {
3537 edge.applyBetaNew();
3540 // compute intial condition of 2nd phase
3541 edge.setBetaNew(Canonical.intersection(edge.getBeta(),
3547 // every edge in the graph is the initial workset
3548 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3549 while( !edgeWorkSet.isEmpty() ) {
3550 RefEdge edgePrime = edgeWorkSet.iterator().next();
3551 edgeWorkSet.remove(edgePrime);
3553 RefSrcNode rsn = edgePrime.getSrc();
3554 if( !(rsn instanceof HeapRegionNode) ) {
3557 HeapRegionNode hrn = (HeapRegionNode) rsn;
3559 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3560 while( itrEdge.hasNext() ) {
3561 RefEdge edge = itrEdge.next();
3563 ReachSet prevResult = edge.getBetaNew();
3564 assert prevResult != null;
3566 ReachSet intersection =
3567 Canonical.intersection(edge.getBeta(),
3568 edgePrime.getBetaNew()
3571 if( Canonical.unionORpreds(prevResult,
3578 Canonical.unionORpreds(prevResult,
3582 edgeWorkSet.add(edge);
3587 // commit beta' (beta<-betaNew)
3588 edgeItr = res.iterator();
3589 while( edgeItr.hasNext() ) {
3590 edgeItr.next().applyBetaNew();
3595 // a useful assertion for debugging:
3596 // every in-context tuple on any edge or
3597 // any node should name a node that is
3598 // part of the graph
3599 public boolean inContextTuplesInGraph() {
3601 Iterator hrnItr = id2hrn.entrySet().iterator();
3602 while( hrnItr.hasNext() ) {
3603 Map.Entry me = (Map.Entry)hrnItr.next();
3604 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3607 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3608 while( stateItr.hasNext() ) {
3609 ReachState state = stateItr.next();
3611 Iterator<ReachTuple> rtItr = state.iterator();
3612 while( rtItr.hasNext() ) {
3613 ReachTuple rt = rtItr.next();
3615 if( !rt.isOutOfContext() ) {
3616 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3617 System.out.println(rt.getHrnID()+" is missing");
3625 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3626 while( edgeItr.hasNext() ) {
3627 RefEdge edge = edgeItr.next();
3629 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3630 while( stateItr.hasNext() ) {
3631 ReachState state = stateItr.next();
3633 Iterator<ReachTuple> rtItr = state.iterator();
3634 while( rtItr.hasNext() ) {
3635 ReachTuple rt = rtItr.next();
3637 if( !rt.isOutOfContext() ) {
3638 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3639 System.out.println(rt.getHrnID()+" is missing");
3652 // another useful assertion for debugging
3653 public boolean noEmptyReachSetsInGraph() {
3655 Iterator hrnItr = id2hrn.entrySet().iterator();
3656 while( hrnItr.hasNext() ) {
3657 Map.Entry me = (Map.Entry)hrnItr.next();
3658 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3660 if( !hrn.isOutOfContext() &&
3662 hrn.getAlpha().isEmpty()
3664 System.out.println("!!! "+hrn+" has an empty ReachSet !!!");
3668 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3669 while( edgeItr.hasNext() ) {
3670 RefEdge edge = edgeItr.next();
3672 if( edge.getBeta().isEmpty() ) {
3673 System.out.println("!!! "+edge+" has an empty ReachSet !!!");
3683 public boolean everyReachStateWTrue() {
3685 Iterator hrnItr = id2hrn.entrySet().iterator();
3686 while( hrnItr.hasNext() ) {
3687 Map.Entry me = (Map.Entry)hrnItr.next();
3688 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3691 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3692 while( stateItr.hasNext() ) {
3693 ReachState state = stateItr.next();
3695 if( !state.getPreds().equals(predsTrue) ) {
3701 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3702 while( edgeItr.hasNext() ) {
3703 RefEdge edge = edgeItr.next();
3705 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3706 while( stateItr.hasNext() ) {
3707 ReachState state = stateItr.next();
3709 if( !state.getPreds().equals(predsTrue) ) {
3722 ////////////////////////////////////////////////////
3723 // in merge() and equals() methods the suffix A
3724 // represents the passed in graph and the suffix
3725 // B refers to the graph in this object
3726 // Merging means to take the incoming graph A and
3727 // merge it into B, so after the operation graph B
3728 // is the final result.
3729 ////////////////////////////////////////////////////
3730 protected void merge(ReachGraph rg) {
3738 mergeAllocSites(rg);
3739 mergeInaccessibleVars(rg);
3742 protected void mergeNodes(ReachGraph rg) {
3744 // start with heap region nodes
3745 Set sA = rg.id2hrn.entrySet();
3746 Iterator iA = sA.iterator();
3747 while( iA.hasNext() ) {
3748 Map.Entry meA = (Map.Entry)iA.next();
3749 Integer idA = (Integer) meA.getKey();
3750 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3752 // if this graph doesn't have a node the
3753 // incoming graph has, allocate it
3754 if( !id2hrn.containsKey(idA) ) {
3755 HeapRegionNode hrnB = hrnA.copy();
3756 id2hrn.put(idA, hrnB);
3759 // otherwise this is a node present in both graphs
3760 // so make the new reachability set a union of the
3761 // nodes' reachability sets
3762 HeapRegionNode hrnB = id2hrn.get(idA);
3763 hrnB.setAlpha(Canonical.unionORpreds(hrnB.getAlpha(),
3768 hrnB.setPreds(Canonical.join(hrnB.getPreds(),
3775 if( !hrnA.equals(hrnB) ) {
3776 rg.writeGraph("graphA");
3777 this.writeGraph("graphB");
3778 throw new Error("flagged not matching");
3786 // now add any variable nodes that are in graph B but
3788 sA = rg.td2vn.entrySet();
3790 while( iA.hasNext() ) {
3791 Map.Entry meA = (Map.Entry)iA.next();
3792 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3793 VariableNode lnA = (VariableNode) meA.getValue();
3795 // if the variable doesn't exist in B, allocate and add it
3796 VariableNode lnB = getVariableNodeFromTemp(tdA);
3800 protected void mergeRefEdges(ReachGraph rg) {
3802 // between heap regions
3803 Set sA = rg.id2hrn.entrySet();
3804 Iterator iA = sA.iterator();
3805 while( iA.hasNext() ) {
3806 Map.Entry meA = (Map.Entry)iA.next();
3807 Integer idA = (Integer) meA.getKey();
3808 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3810 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3811 while( heapRegionsItrA.hasNext() ) {
3812 RefEdge edgeA = heapRegionsItrA.next();
3813 HeapRegionNode hrnChildA = edgeA.getDst();
3814 Integer idChildA = hrnChildA.getID();
3816 // at this point we know an edge in graph A exists
3817 // idA -> idChildA, does this exist in B?
3818 assert id2hrn.containsKey(idA);
3819 HeapRegionNode hrnB = id2hrn.get(idA);
3820 RefEdge edgeToMerge = null;
3822 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3823 while( heapRegionsItrB.hasNext() &&
3824 edgeToMerge == null ) {
3826 RefEdge edgeB = heapRegionsItrB.next();
3827 HeapRegionNode hrnChildB = edgeB.getDst();
3828 Integer idChildB = hrnChildB.getID();
3830 // don't use the RefEdge.equals() here because
3831 // we're talking about existence between graphs,
3832 // not intragraph equal
3833 if( idChildB.equals(idChildA) &&
3834 edgeB.typeAndFieldEquals(edgeA) ) {
3836 edgeToMerge = edgeB;
3840 // if the edge from A was not found in B,
3842 if( edgeToMerge == null ) {
3843 assert id2hrn.containsKey(idChildA);
3844 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3845 edgeToMerge = edgeA.copy();
3846 edgeToMerge.setSrc(hrnB);
3847 edgeToMerge.setDst(hrnChildB);
3848 addRefEdge(hrnB, hrnChildB, edgeToMerge);
3850 // otherwise, the edge already existed in both graphs
3851 // so merge their reachability sets
3853 // just replace this beta set with the union
3854 assert edgeToMerge != null;
3855 edgeToMerge.setBeta(
3856 Canonical.unionORpreds(edgeToMerge.getBeta(),
3860 edgeToMerge.setPreds(
3861 Canonical.join(edgeToMerge.getPreds(),
3865 edgeToMerge.setTaints(
3866 Canonical.union(edgeToMerge.getTaints(),
3874 // and then again from variable nodes
3875 sA = rg.td2vn.entrySet();
3877 while( iA.hasNext() ) {
3878 Map.Entry meA = (Map.Entry)iA.next();
3879 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3880 VariableNode vnA = (VariableNode) meA.getValue();
3882 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3883 while( heapRegionsItrA.hasNext() ) {
3884 RefEdge edgeA = heapRegionsItrA.next();
3885 HeapRegionNode hrnChildA = edgeA.getDst();
3886 Integer idChildA = hrnChildA.getID();
3888 // at this point we know an edge in graph A exists
3889 // tdA -> idChildA, does this exist in B?
3890 assert td2vn.containsKey(tdA);
3891 VariableNode vnB = td2vn.get(tdA);
3892 RefEdge edgeToMerge = null;
3894 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3895 while( heapRegionsItrB.hasNext() &&
3896 edgeToMerge == null ) {
3898 RefEdge edgeB = heapRegionsItrB.next();
3899 HeapRegionNode hrnChildB = edgeB.getDst();
3900 Integer idChildB = hrnChildB.getID();
3902 // don't use the RefEdge.equals() here because
3903 // we're talking about existence between graphs
3904 if( idChildB.equals(idChildA) &&
3905 edgeB.typeAndFieldEquals(edgeA) ) {
3907 edgeToMerge = edgeB;
3911 // if the edge from A was not found in B,
3913 if( edgeToMerge == null ) {
3914 assert id2hrn.containsKey(idChildA);
3915 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3916 edgeToMerge = edgeA.copy();
3917 edgeToMerge.setSrc(vnB);
3918 edgeToMerge.setDst(hrnChildB);
3919 addRefEdge(vnB, hrnChildB, edgeToMerge);
3921 // otherwise, the edge already existed in both graphs
3922 // so merge their reachability sets
3924 // just replace this beta set with the union
3925 edgeToMerge.setBeta(Canonical.unionORpreds(edgeToMerge.getBeta(),
3929 edgeToMerge.setPreds(Canonical.join(edgeToMerge.getPreds(),
3933 edgeToMerge.setTaints(
3934 Canonical.union(edgeToMerge.getTaints(),
3943 protected void mergeAllocSites(ReachGraph rg) {
3944 allocSites.addAll(rg.allocSites);
3947 protected void mergeInaccessibleVars(ReachGraph rg) {
3948 inaccessibleVars.addAll(rg.inaccessibleVars);
3953 static public boolean dbgEquals = false;
3956 // it is necessary in the equals() member functions
3957 // to "check both ways" when comparing the data
3958 // structures of two graphs. For instance, if all
3959 // edges between heap region nodes in graph A are
3960 // present and equal in graph B it is not sufficient
3961 // to say the graphs are equal. Consider that there
3962 // may be edges in graph B that are not in graph A.
3963 // the only way to know that all edges in both graphs
3964 // are equally present is to iterate over both data
3965 // structures and compare against the other graph.
3966 public boolean equals(ReachGraph rg) {
3970 System.out.println("rg is null");
3975 if( !areHeapRegionNodesEqual(rg) ) {
3977 System.out.println("hrn not equal");
3982 if( !areVariableNodesEqual(rg) ) {
3984 System.out.println("vars not equal");
3989 if( !areRefEdgesEqual(rg) ) {
3991 System.out.println("edges not equal");
3996 if( !inaccessibleVars.equals(rg.inaccessibleVars) ) {
4000 // if everything is equal up to this point,
4001 // assert that allocSites is also equal--
4002 // this data is redundant but kept for efficiency
4003 assert allocSites.equals(rg.allocSites);
4009 protected boolean areHeapRegionNodesEqual(ReachGraph rg) {
4011 if( !areallHRNinAalsoinBandequal(this, rg) ) {
4015 if( !areallHRNinAalsoinBandequal(rg, this) ) {
4022 static protected boolean areallHRNinAalsoinBandequal(ReachGraph rgA,
4024 Set sA = rgA.id2hrn.entrySet();
4025 Iterator iA = sA.iterator();
4026 while( iA.hasNext() ) {
4027 Map.Entry meA = (Map.Entry)iA.next();
4028 Integer idA = (Integer) meA.getKey();
4029 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4031 if( !rgB.id2hrn.containsKey(idA) ) {
4035 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4036 if( !hrnA.equalsIncludingAlphaAndPreds(hrnB) ) {
4044 protected boolean areVariableNodesEqual(ReachGraph rg) {
4046 if( !areallVNinAalsoinBandequal(this, rg) ) {
4050 if( !areallVNinAalsoinBandequal(rg, this) ) {
4057 static protected boolean areallVNinAalsoinBandequal(ReachGraph rgA,
4059 Set sA = rgA.td2vn.entrySet();
4060 Iterator iA = sA.iterator();
4061 while( iA.hasNext() ) {
4062 Map.Entry meA = (Map.Entry)iA.next();
4063 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4065 if( !rgB.td2vn.containsKey(tdA) ) {
4074 protected boolean areRefEdgesEqual(ReachGraph rg) {
4075 if( !areallREinAandBequal(this, rg) ) {
4079 if( !areallREinAandBequal(rg, this) ) {
4086 static protected boolean areallREinAandBequal(ReachGraph rgA,
4089 // check all the heap region->heap region edges
4090 Set sA = rgA.id2hrn.entrySet();
4091 Iterator iA = sA.iterator();
4092 while( iA.hasNext() ) {
4093 Map.Entry meA = (Map.Entry)iA.next();
4094 Integer idA = (Integer) meA.getKey();
4095 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4097 // we should have already checked that the same
4098 // heap regions exist in both graphs
4099 assert rgB.id2hrn.containsKey(idA);
4101 if( !areallREfromAequaltoB(rgA, hrnA, rgB) ) {
4105 // then check every edge in B for presence in A, starting
4106 // from the same parent HeapRegionNode
4107 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4109 if( !areallREfromAequaltoB(rgB, hrnB, rgA) ) {
4114 // then check all the variable->heap region edges
4115 sA = rgA.td2vn.entrySet();
4117 while( iA.hasNext() ) {
4118 Map.Entry meA = (Map.Entry)iA.next();
4119 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4120 VariableNode vnA = (VariableNode) meA.getValue();
4122 // we should have already checked that the same
4123 // label nodes exist in both graphs
4124 assert rgB.td2vn.containsKey(tdA);
4126 if( !areallREfromAequaltoB(rgA, vnA, rgB) ) {
4130 // then check every edge in B for presence in A, starting
4131 // from the same parent VariableNode
4132 VariableNode vnB = rgB.td2vn.get(tdA);
4134 if( !areallREfromAequaltoB(rgB, vnB, rgA) ) {
4143 static protected boolean areallREfromAequaltoB(ReachGraph rgA,
4147 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4148 while( itrA.hasNext() ) {
4149 RefEdge edgeA = itrA.next();
4150 HeapRegionNode hrnChildA = edgeA.getDst();
4151 Integer idChildA = hrnChildA.getID();
4153 assert rgB.id2hrn.containsKey(idChildA);
4155 // at this point we know an edge in graph A exists
4156 // rnA -> idChildA, does this exact edge exist in B?
4157 boolean edgeFound = false;
4159 RefSrcNode rnB = null;
4160 if( rnA instanceof HeapRegionNode ) {
4161 HeapRegionNode hrnA = (HeapRegionNode) rnA;
4162 rnB = rgB.id2hrn.get(hrnA.getID() );
4164 VariableNode vnA = (VariableNode) rnA;
4165 rnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4168 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4169 while( itrB.hasNext() ) {
4170 RefEdge edgeB = itrB.next();
4171 HeapRegionNode hrnChildB = edgeB.getDst();
4172 Integer idChildB = hrnChildB.getID();
4174 if( idChildA.equals(idChildB) &&
4175 edgeA.typeAndFieldEquals(edgeB) ) {
4177 // there is an edge in the right place with the right field,
4178 // but do they have the same attributes?
4179 if( edgeA.equalsIncludingBetaPredsTaints( edgeB ) ) {
4194 // can be used to assert monotonicity
4195 static public boolean isNoSmallerThan(ReachGraph rgA,
4198 //System.out.println( "*** Asking if A is no smaller than B ***" );
4200 Iterator iA = rgA.id2hrn.entrySet().iterator();
4201 while( iA.hasNext() ) {
4202 Map.Entry meA = (Map.Entry)iA.next();
4203 Integer idA = (Integer) meA.getKey();
4204 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4206 if( !rgB.id2hrn.containsKey(idA) ) {
4207 System.out.println(" regions smaller");
4212 // this works just fine, no smaller than
4213 if( !areallVNinAalsoinBandequal(rgA, rgB) ) {
4214 System.out.println(" vars smaller:");
4215 System.out.println(" A:"+rgA.td2vn.keySet() );
4216 System.out.println(" B:"+rgB.td2vn.keySet() );
4221 iA = rgA.id2hrn.entrySet().iterator();
4222 while( iA.hasNext() ) {
4223 Map.Entry meA = (Map.Entry)iA.next();
4224 Integer idA = (Integer) meA.getKey();
4225 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4227 Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4228 while( reItr.hasNext() ) {
4229 RefEdge edgeA = reItr.next();
4230 RefSrcNode rsnA = edgeA.getSrc();
4232 // we already checked that nodes were present
4233 HeapRegionNode hrnB = rgB.id2hrn.get(hrnA.getID() );
4234 assert hrnB != null;
4237 if( rsnA instanceof VariableNode ) {
4238 VariableNode vnA = (VariableNode) rsnA;
4239 rsnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4242 HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4243 rsnB = rgB.id2hrn.get(hrnSrcA.getID() );
4245 assert rsnB != null;
4247 RefEdge edgeB = rsnB.getReferenceTo(hrnB,
4251 if( edgeB == null ) {
4252 System.out.println(" edges smaller:");
4266 // this analysis no longer has the "match anything"
4267 // type which was represented by null
4268 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4269 TypeDescriptor td2) {
4273 if( td1.isNull() ) {
4276 if( td2.isNull() ) {
4279 return typeUtil.mostSpecific(td1, td2);
4282 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4284 TypeDescriptor td3) {
4286 return mostSpecificType(td1,
4287 mostSpecificType(td2, td3)
4291 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4294 TypeDescriptor td4) {
4296 return mostSpecificType(mostSpecificType(td1, td2),
4297 mostSpecificType(td3, td4)
4301 protected boolean isSuperiorType(TypeDescriptor possibleSuper,
4302 TypeDescriptor possibleChild) {
4303 assert possibleSuper != null;
4304 assert possibleChild != null;
4306 if( possibleSuper.isNull() ||
4307 possibleChild.isNull() ) {
4311 return typeUtil.isSuperorType(possibleSuper, possibleChild);
4315 protected boolean hasMatchingField(HeapRegionNode src,
4318 TypeDescriptor tdSrc = src.getType();
4319 assert tdSrc != null;
4321 if( tdSrc.isArray() ) {
4322 TypeDescriptor td = edge.getType();
4325 TypeDescriptor tdSrcDeref = tdSrc.dereference();
4326 assert tdSrcDeref != null;
4328 if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
4332 return edge.getField().equals(DisjointAnalysis.arrayElementFieldName);
4335 // if it's not a class, it doesn't have any fields to match
4336 if( !tdSrc.isClass() ) {
4340 ClassDescriptor cd = tdSrc.getClassDesc();
4341 while( cd != null ) {
4342 Iterator fieldItr = cd.getFields();
4344 while( fieldItr.hasNext() ) {
4345 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4347 if( fd.getType().equals(edge.getType() ) &&
4348 fd.getSymbol().equals(edge.getField() ) ) {
4353 cd = cd.getSuperDesc();
4356 // otherwise it is a class with fields
4357 // but we didn't find a match
4361 protected boolean hasMatchingType(RefEdge edge,
4362 HeapRegionNode dst) {
4364 // if the region has no type, matches everything
4365 TypeDescriptor tdDst = dst.getType();
4366 assert tdDst != null;
4368 // if the type is not a class or an array, don't
4369 // match because primitives are copied, no aliases
4370 ClassDescriptor cdDst = tdDst.getClassDesc();
4371 if( cdDst == null && !tdDst.isArray() ) {
4375 // if the edge type is null, it matches everything
4376 TypeDescriptor tdEdge = edge.getType();
4377 assert tdEdge != null;
4379 return typeUtil.isSuperorType(tdEdge, tdDst);
4384 // the default signature for quick-and-dirty debugging
4385 public void writeGraph(String graphName) {
4386 writeGraph(graphName,
4387 true, // write labels
4388 true, // label select
4389 true, // prune garbage
4390 false, // hide reachability
4391 true, // hide subset reachability
4392 true, // hide predicates
4393 false, // hide edge taints
4394 null // in-context boundary
4398 public void writeGraph(String graphName,
4399 boolean writeLabels,
4400 boolean labelSelect,
4401 boolean pruneGarbage,
4402 boolean hideReachability,
4403 boolean hideSubsetReachability,
4404 boolean hidePredicates,
4405 boolean hideEdgeTaints
4407 writeGraph(graphName,
4412 hideSubsetReachability,
4418 public void writeGraph(String graphName,
4419 boolean writeLabels,
4420 boolean labelSelect,
4421 boolean pruneGarbage,
4422 boolean hideReachability,
4423 boolean hideSubsetReachability,
4424 boolean hidePredicates,
4425 boolean hideEdgeTaints,
4426 Set<Integer> callerNodeIDsCopiedToCallee
4429 // remove all non-word characters from the graph name so
4430 // the filename and identifier in dot don't cause errors
4431 // jjenista - also replace underscore '_' to prevent some
4432 // really, really long names from IHMS debugging
4433 graphName = graphName.replaceAll("[\\W_]", "");
4436 new BufferedWriter(new FileWriter(graphName+".dot") );
4438 bw.write("digraph "+graphName+" {\n");
4441 // this is an optional step to form the callee-reachable
4442 // "cut-out" into a DOT cluster for visualization
4443 if( callerNodeIDsCopiedToCallee != null ) {
4445 bw.write(" subgraph cluster0 {\n");
4446 bw.write(" color=blue;\n");
4448 Iterator i = id2hrn.entrySet().iterator();
4449 while( i.hasNext() ) {
4450 Map.Entry me = (Map.Entry)i.next();
4451 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4453 if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4456 hrn.toStringDOT(hideReachability,
4457 hideSubsetReachability,
4467 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4469 // then visit every heap region node
4470 Iterator i = id2hrn.entrySet().iterator();
4471 while( i.hasNext() ) {
4472 Map.Entry me = (Map.Entry)i.next();
4473 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4475 // only visit nodes worth writing out--for instance
4476 // not every node at an allocation is referenced
4477 // (think of it as garbage-collected), etc.
4478 if( !pruneGarbage ||
4479 hrn.isOutOfContext() ||
4480 (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4483 if( !visited.contains(hrn) ) {
4484 traverseHeapRegionNodes(hrn,
4489 hideSubsetReachability,
4492 callerNodeIDsCopiedToCallee);
4497 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4500 // then visit every label node, useful for debugging
4502 i = td2vn.entrySet().iterator();
4503 while( i.hasNext() ) {
4504 Map.Entry me = (Map.Entry)i.next();
4505 VariableNode vn = (VariableNode) me.getValue();
4508 String labelStr = vn.getTempDescriptorString();
4509 if( labelStr.startsWith("___temp") ||
4510 labelStr.startsWith("___dst") ||
4511 labelStr.startsWith("___srctmp") ||
4512 labelStr.startsWith("___neverused")
4518 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4519 while( heapRegionsItr.hasNext() ) {
4520 RefEdge edge = heapRegionsItr.next();
4521 HeapRegionNode hrn = edge.getDst();
4523 if( !visited.contains(hrn) ) {
4524 traverseHeapRegionNodes(hrn,
4529 hideSubsetReachability,
4532 callerNodeIDsCopiedToCallee);
4535 bw.write(" "+vn.toString()+
4536 " -> "+hrn.toString()+
4537 edge.toStringDOT(hideReachability,
4538 hideSubsetReachability,
4550 } catch( IOException e ) {
4551 throw new Error("Error writing out DOT graph "+graphName);
4556 traverseHeapRegionNodes(HeapRegionNode hrn,
4559 Set<HeapRegionNode> visited,
4560 boolean hideReachability,
4561 boolean hideSubsetReachability,
4562 boolean hidePredicates,
4563 boolean hideEdgeTaints,
4564 Set<Integer> callerNodeIDsCopiedToCallee
4565 ) throws java.io.IOException {
4567 if( visited.contains(hrn) ) {
4572 // if we're drawing the callee-view subgraph, only
4573 // write out the node info if it hasn't already been
4575 if( callerNodeIDsCopiedToCallee == null ||
4576 !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4580 hrn.toStringDOT(hideReachability,
4581 hideSubsetReachability,
4586 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4587 while( childRegionsItr.hasNext() ) {
4588 RefEdge edge = childRegionsItr.next();
4589 HeapRegionNode hrnChild = edge.getDst();
4591 if( callerNodeIDsCopiedToCallee != null &&
4592 (edge.getSrc() instanceof HeapRegionNode) ) {
4593 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4594 if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4595 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4597 bw.write(" "+hrn.toString()+
4598 " -> "+hrnChild.toString()+
4599 edge.toStringDOT(hideReachability,
4600 hideSubsetReachability,
4605 } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4606 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4608 bw.write(" "+hrn.toString()+
4609 " -> "+hrnChild.toString()+
4610 edge.toStringDOT(hideReachability,
4611 hideSubsetReachability,
4614 ",color=blue,style=dashed")+
4617 bw.write(" "+hrn.toString()+
4618 " -> "+hrnChild.toString()+
4619 edge.toStringDOT(hideReachability,
4620 hideSubsetReachability,
4627 bw.write(" "+hrn.toString()+
4628 " -> "+hrnChild.toString()+
4629 edge.toStringDOT(hideReachability,
4630 hideSubsetReachability,
4637 traverseHeapRegionNodes(hrnChild,
4642 hideSubsetReachability,
4645 callerNodeIDsCopiedToCallee);
4654 // return the set of heap regions from the given allocation
4655 // site, if any, that exist in this graph
4656 protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4658 Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4660 Integer idSum = as.getSummary();
4661 if( id2hrn.containsKey(idSum) ) {
4662 out.add(id2hrn.get(idSum) );
4665 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4666 Integer idI = as.getIthOldest(i);
4667 if( id2hrn.containsKey(idI) ) {
4668 out.add(id2hrn.get(idI) );
4675 // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4676 // from the given allocation site, if any, from regions for that
4677 // site that exist in this graph
4678 protected Set<ReachTuple> getAnyExisting(AllocSite as,
4679 boolean includeARITY_ZEROORMORE,
4680 boolean includeARITY_ONE) {
4682 Set<ReachTuple> out = new HashSet<ReachTuple>();
4684 Integer idSum = as.getSummary();
4685 if( id2hrn.containsKey(idSum) ) {
4687 HeapRegionNode hrn = id2hrn.get(idSum);
4688 assert !hrn.isOutOfContext();
4690 if( !includeARITY_ZEROORMORE ) {
4691 out.add(ReachTuple.factory(hrn.getID(),
4692 true, // multi-obj region
4693 ReachTuple.ARITY_ZEROORMORE,
4698 if( includeARITY_ONE ) {
4699 out.add(ReachTuple.factory(hrn.getID(),
4700 true, // multi-object region
4701 ReachTuple.ARITY_ONE,
4707 if( !includeARITY_ONE ) {
4708 // no need to do the single-object regions that
4709 // only have an ARITY ONE possible
4713 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4715 Integer idI = as.getIthOldest(i);
4716 if( id2hrn.containsKey(idI) ) {
4718 HeapRegionNode hrn = id2hrn.get(idI);
4719 assert !hrn.isOutOfContext();
4721 out.add(ReachTuple.factory(hrn.getID(),
4722 false, // multi-object region
4723 ReachTuple.ARITY_ONE,
4733 // if an object allocated at the target site may be
4734 // reachable from both an object from root1 and an
4735 // object allocated at root2, return TRUE
4736 public boolean mayBothReachTarget(AllocSite asRoot1,
4738 AllocSite asTarget) {
4740 // consider all heap regions of the target and look
4741 // for a reach state that indicates regions of root1
4742 // and root2 might be able to reach same object
4743 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4745 // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4746 Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4747 Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4749 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4750 while( hrnItr.hasNext() ) {
4751 HeapRegionNode hrn = hrnItr.next();
4753 Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4754 while( rtItr1.hasNext() ) {
4755 ReachTuple rt1 = rtItr1.next();
4757 Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4758 while( rtItr2.hasNext() ) {
4759 ReachTuple rt2 = rtItr2.next();
4761 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4771 // similar to the method above, return TRUE if ever
4772 // more than one object from the root allocation site
4773 // may reach an object from the target site
4774 public boolean mayManyReachTarget(AllocSite asRoot,
4775 AllocSite asTarget) {
4777 // consider all heap regions of the target and look
4778 // for a reach state that multiple objects of root
4779 // might be able to reach the same object
4780 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4782 // get relevant reach tuples
4783 Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true, false);
4784 Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4786 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4787 while( hrnItr.hasNext() ) {
4788 HeapRegionNode hrn = hrnItr.next();
4790 // if any ZERORMORE tuples are here, TRUE
4791 Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4792 while( rtItr.hasNext() ) {
4793 ReachTuple rtZOM = rtItr.next();
4795 if( hrn.getAlpha().containsTuple(rtZOM) ) {
4800 // otherwise, look for any pair of ONE tuples
4801 Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4802 while( rtItr1.hasNext() ) {
4803 ReachTuple rt1 = rtItr1.next();
4805 Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4806 while( rtItr2.hasNext() ) {
4807 ReachTuple rt2 = rtItr2.next();
4813 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4827 public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4829 Set<HeapRegionNode> exhibitProofState =
4830 new HashSet<HeapRegionNode>();
4832 Iterator hrnItr = id2hrn.entrySet().iterator();
4833 while( hrnItr.hasNext() ) {
4834 Map.Entry me = (Map.Entry)hrnItr.next();
4835 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4837 ReachSet intersection =
4838 Canonical.intersection(proofOfSharing,
4841 if( !intersection.isEmpty() ) {
4842 assert !hrn.isOutOfContext();
4843 exhibitProofState.add(hrn);
4847 return exhibitProofState;
4851 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4852 HeapRegionNode hrn2) {
4853 assert hrn1 != null;
4854 assert hrn2 != null;
4856 assert !hrn1.isOutOfContext();
4857 assert !hrn2.isOutOfContext();
4859 assert belongsToThis(hrn1);
4860 assert belongsToThis(hrn2);
4862 assert !hrn1.getID().equals(hrn2.getID() );
4865 // then get the various tokens for these heap regions
4867 ReachTuple.factory(hrn1.getID(),
4868 !hrn1.isSingleObject(), // multi?
4869 ReachTuple.ARITY_ONE,
4872 ReachTuple h1star = null;
4873 if( !hrn1.isSingleObject() ) {
4875 ReachTuple.factory(hrn1.getID(),
4876 !hrn1.isSingleObject(),
4877 ReachTuple.ARITY_ZEROORMORE,
4882 ReachTuple.factory(hrn2.getID(),
4883 !hrn2.isSingleObject(),
4884 ReachTuple.ARITY_ONE,
4887 ReachTuple h2star = null;
4888 if( !hrn2.isSingleObject() ) {
4890 ReachTuple.factory(hrn2.getID(),
4891 !hrn2.isSingleObject(),
4892 ReachTuple.ARITY_ZEROORMORE,
4896 // then get the merged beta of all out-going edges from these heap
4899 ReachSet beta1 = ReachSet.factory();
4900 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4901 while (itrEdge.hasNext()) {
4902 RefEdge edge = itrEdge.next();
4903 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4906 ReachSet beta2 = ReachSet.factory();
4907 itrEdge = hrn2.iteratorToReferencees();
4908 while (itrEdge.hasNext()) {
4909 RefEdge edge = itrEdge.next();
4910 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4913 ReachSet proofOfSharing = ReachSet.factory();
4916 Canonical.unionORpreds(proofOfSharing,
4917 beta1.getStatesWithBoth(h1, h2)
4920 Canonical.unionORpreds(proofOfSharing,
4921 beta2.getStatesWithBoth(h1, h2)
4924 if( !hrn1.isSingleObject() ) {
4926 Canonical.unionORpreds(proofOfSharing,
4927 beta1.getStatesWithBoth(h1star, h2)
4930 Canonical.unionORpreds(proofOfSharing,
4931 beta2.getStatesWithBoth(h1star, h2)
4935 if( !hrn2.isSingleObject() ) {
4937 Canonical.unionORpreds(proofOfSharing,
4938 beta1.getStatesWithBoth(h1, h2star)
4941 Canonical.unionORpreds(proofOfSharing,
4942 beta2.getStatesWithBoth(h1, h2star)
4946 if( !hrn1.isSingleObject() &&
4947 !hrn2.isSingleObject()
4950 Canonical.unionORpreds(proofOfSharing,
4951 beta1.getStatesWithBoth(h1star, h2star)
4954 Canonical.unionORpreds(proofOfSharing,
4955 beta2.getStatesWithBoth(h1star, h2star)
4959 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4960 if( !proofOfSharing.isEmpty() ) {
4961 common = findCommonReachableNodes(proofOfSharing);
4962 if( !DISABLE_STRONG_UPDATES &&
4963 !DISABLE_GLOBAL_SWEEP
4965 assert !common.isEmpty();
4972 // this version of the above method checks whether there is sharing
4973 // among the objects in a summary node
4974 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4976 assert hrn.isNewSummary();
4977 assert !hrn.isOutOfContext();
4978 assert belongsToThis(hrn);
4981 ReachTuple.factory(hrn.getID(),
4983 ReachTuple.ARITY_ZEROORMORE,
4986 // then get the merged beta of all out-going edges from
4989 ReachSet beta = ReachSet.factory();
4990 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4991 while (itrEdge.hasNext()) {
4992 RefEdge edge = itrEdge.next();
4993 beta = Canonical.unionORpreds(beta, edge.getBeta());
4996 ReachSet proofOfSharing = ReachSet.factory();
4999 Canonical.unionORpreds(proofOfSharing,
5000 beta.getStatesWithBoth(hstar, hstar)
5003 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5004 if( !proofOfSharing.isEmpty() ) {
5005 common = findCommonReachableNodes(proofOfSharing);
5006 if( !DISABLE_STRONG_UPDATES &&
5007 !DISABLE_GLOBAL_SWEEP
5009 assert !common.isEmpty();
5017 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5018 Integer paramIndex1,
5019 Integer paramIndex2) {
5021 // get parameter's heap regions
5022 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5023 assert this.hasVariable(paramTemp1);
5024 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5027 if( !(paramVar1.getNumReferencees() == 1) ) {
5028 System.out.println("\n fm="+fm+"\n param="+paramTemp1);
5029 writeGraph("whatup");
5033 assert paramVar1.getNumReferencees() == 1;
5034 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5035 HeapRegionNode hrnParam1 = paramEdge1.getDst();
5037 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5038 assert this.hasVariable(paramTemp2);
5039 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5041 if( !(paramVar2.getNumReferencees() == 1) ) {
5042 System.out.println("\n fm="+fm+"\n param="+paramTemp2);
5043 writeGraph("whatup");
5046 assert paramVar2.getNumReferencees() == 1;
5047 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5048 HeapRegionNode hrnParam2 = paramEdge2.getDst();
5050 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5051 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5056 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5060 // get parameter's heap regions
5061 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5062 assert this.hasVariable(paramTemp);
5063 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5064 assert paramVar.getNumReferencees() == 1;
5065 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5066 HeapRegionNode hrnParam = paramEdge.getDst();
5069 HeapRegionNode hrnSummary=null;
5070 if(id2hrn.containsKey(as.getSummary())) {
5071 // if summary node doesn't exist, ignore this case
5072 hrnSummary = id2hrn.get(as.getSummary());
5073 assert hrnSummary != null;
5076 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5077 if(hrnSummary!=null) {
5078 common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5081 // check for other nodes
5082 for (int i = 0; i < as.getAllocationDepth(); ++i) {
5084 assert id2hrn.containsKey(as.getIthOldest(i));
5085 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5086 assert hrnIthOldest != null;
5088 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5095 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5098 // get summary node 1's alpha
5099 Integer idSum1 = as1.getSummary();
5100 HeapRegionNode hrnSum1=null;
5101 if(id2hrn.containsKey(idSum1)) {
5102 hrnSum1 = id2hrn.get(idSum1);
5105 // get summary node 2's alpha
5106 Integer idSum2 = as2.getSummary();
5107 HeapRegionNode hrnSum2=null;
5108 if(id2hrn.containsKey(idSum2)) {
5109 hrnSum2 = id2hrn.get(idSum2);
5112 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5113 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5114 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5118 // ask if objects from this summary share among each other
5119 common.addAll(mayReachSharedObjects(hrnSum1));
5122 // check sum2 against alloc1 nodes
5124 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5125 Integer idI1 = as1.getIthOldest(i);
5126 assert id2hrn.containsKey(idI1);
5127 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5128 assert hrnI1 != null;
5129 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5132 // also ask if objects from this summary share among each other
5133 common.addAll(mayReachSharedObjects(hrnSum2));
5136 // check sum1 against alloc2 nodes
5137 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5138 Integer idI2 = as2.getIthOldest(i);
5139 assert id2hrn.containsKey(idI2);
5140 HeapRegionNode hrnI2 = id2hrn.get(idI2);
5141 assert hrnI2 != null;
5144 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5147 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5148 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5149 Integer idI1 = as1.getIthOldest(j);
5151 // if these are the same site, don't look for the same token, no
5153 // different tokens of the same site could alias together though
5154 if (idI1.equals(idI2)) {
5158 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5160 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5167 public void makeInaccessible(Set<TempDescriptor> vars) {
5168 inaccessibleVars.addAll(vars);
5171 public void makeInaccessible(TempDescriptor td) {
5172 inaccessibleVars.add(td);
5175 public void makeAccessible(TempDescriptor td) {
5176 inaccessibleVars.remove(td);
5179 public boolean isAccessible(TempDescriptor td) {
5180 return !inaccessibleVars.contains(td);
5183 public Set<TempDescriptor> getInaccessibleVars() {
5184 return inaccessibleVars;
5190 public Set<Alloc> canPointTo( TempDescriptor x ) {
5192 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5193 // if we don't care to track it, return null which means
5194 // "a client of this result shouldn't care either"
5195 return HeapAnalysis.DONTCARE_PTR;
5198 Set<Alloc> out = new HashSet<Alloc>();
5200 VariableNode vn = getVariableNodeNoMutation( x );
5202 // the empty set means "can't point to anything"
5206 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5207 while( edgeItr.hasNext() ) {
5208 HeapRegionNode hrn = edgeItr.next().getDst();
5209 out.add( hrn.getAllocSite() );
5217 public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5219 TypeDescriptor fieldType ) {
5221 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5222 // if we don't care to track it, return null which means
5223 // "a client of this result shouldn't care either"
5224 return HeapAnalysis.DONTCARE_DREF;
5227 Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5229 VariableNode vn = getVariableNodeNoMutation( x );
5231 // the empty table means "x can't point to anything"
5235 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5236 while( edgeItr.hasNext() ) {
5237 HeapRegionNode hrn = edgeItr.next().getDst();
5238 Alloc key = hrn.getAllocSite();
5240 if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5241 // if we don't care to track it, put no entry which means
5242 // "a client of this result shouldn't care either"
5243 out.put( key, HeapAnalysis.DONTCARE_PTR );
5247 Set<Alloc> moreValues = new HashSet<Alloc>();
5248 Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5249 while( edgeItr2.hasNext() ) {
5250 RefEdge edge = edgeItr2.next();
5252 if( field.equals( edge.getField() ) ) {
5253 moreValues.add( edge.getDst().getAllocSite() );
5257 if( out.containsKey( key ) ) {
5258 out.get( key ).addAll( moreValues );
5260 out.put( key, moreValues );
5270 public TempDescriptor findVariableByName( String name ) {
5272 for( TempDescriptor td: td2vn.keySet() ) {
5273 if( td.getSymbol().contains( name ) ) {