1 package Analysis.Disjoint;
5 import Util.UtilAlgorithms;
9 public class ReachGraph {
11 // use to disable improvements for comparison
12 protected static final boolean DISABLE_STRONG_UPDATES = false;
13 protected static final boolean DISABLE_GLOBAL_SWEEP = false;
15 // a special out-of-scope temps
16 protected static TempDescriptor tdReturn;
17 protected static TempDescriptor tdStrLiteralBytes;
19 public static void initOutOfScopeTemps() {
20 tdReturn = new TempDescriptor("_Return___");
23 new TempDescriptor("_strLiteralBytes___",
24 new TypeDescriptor(TypeDescriptor.CHAR).makeArray( state )
28 // predicate constants
29 public static final ExistPred predTrue = ExistPred.factory(); // if no args, true
30 public static final ExistPredSet predsEmpty = ExistPredSet.factory();
31 public static final ExistPredSet predsTrue = ExistPredSet.factory(predTrue);
33 // some frequently used reachability constants
34 protected static final ReachState rstateEmpty = ReachState.factory();
35 protected static final ReachSet rsetEmpty = ReachSet.factory();
36 protected static final ReachSet rsetWithEmptyState = Canonical.changePredsTo(ReachSet.factory(rstateEmpty),
39 // from DisjointAnalysis for convenience
40 protected static int allocationDepth = -1;
41 protected static TypeUtil typeUtil = null;
42 protected static State state = null;
45 // variable and heap region nodes indexed by unique ID
46 public Hashtable<Integer, HeapRegionNode> id2hrn;
47 public Hashtable<TempDescriptor, VariableNode > td2vn;
49 // convenient set of alloc sites for all heap regions
50 // present in the graph without having to search
51 public Set<AllocSite> allocSites;
53 // set of inaccessible variables for current program statement
54 // with respect to stall-site analysis
55 public Set<TempDescriptor> inaccessibleVars;
59 id2hrn = new Hashtable<Integer, HeapRegionNode>();
60 td2vn = new Hashtable<TempDescriptor, VariableNode >();
61 allocSites = new HashSet<AllocSite>();
62 inaccessibleVars = new HashSet<TempDescriptor>();
66 // temp descriptors are globally unique and map to
67 // exactly one variable node, easy
68 protected VariableNode getVariableNodeFromTemp(TempDescriptor td) {
71 if( !td2vn.containsKey(td) ) {
72 td2vn.put(td, new VariableNode(td) );
78 //This method is created for client modules to access the Reachgraph
79 //after the analysis is done and no modifications are to be made.
80 public VariableNode getVariableNodeNoMutation(TempDescriptor td) {
83 if( !td2vn.containsKey(td) ) {
90 public boolean hasVariable(TempDescriptor td) {
91 return td2vn.containsKey(td);
95 // this suite of methods can be used to assert a
96 // very important property of ReachGraph objects:
97 // some element, HeapRegionNode, RefEdge etc.
98 // should be referenced by at most ONE ReachGraph!!
99 // If a heap region or edge or variable should be
100 // in another graph, make a new object with
101 // equivalent properties for a new graph
102 public boolean belongsToThis(RefSrcNode rsn) {
103 if( rsn instanceof VariableNode ) {
104 VariableNode vn = (VariableNode) rsn;
105 return this.td2vn.get(vn.getTempDescriptor() ) == vn;
107 HeapRegionNode hrn = (HeapRegionNode) rsn;
108 return this.id2hrn.get(hrn.getID() ) == hrn;
115 // the reason for this method is to have the option
116 // of creating new heap regions with specific IDs, or
117 // duplicating heap regions with specific IDs (especially
118 // in the merge() operation) or to create new heap
119 // regions with a new unique ID
120 protected HeapRegionNode
121 createNewHeapRegionNode(Integer id,
122 boolean isSingleObject,
123 boolean isNewSummary,
124 boolean isOutOfContext,
133 TypeDescriptor typeToUse = null;
134 if( allocSite != null ) {
135 typeToUse = allocSite.getType();
136 allocSites.add(allocSite);
141 boolean markForAnalysis = false;
142 if( allocSite != null && allocSite.isFlagged() ) {
143 markForAnalysis = true;
146 if( allocSite == null ) {
147 assert !markForAnalysis;
149 } else if( markForAnalysis != allocSite.isFlagged() ) {
155 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
158 if( inherent == null ) {
159 if( markForAnalysis ) {
161 Canonical.changePredsTo(
164 ReachTuple.factory(id,
166 ReachTuple.ARITY_ONE,
167 false // out-of-context
174 inherent = rsetWithEmptyState;
178 if( alpha == null ) {
182 assert preds != null;
184 HeapRegionNode hrn = new HeapRegionNode(id,
201 ////////////////////////////////////////////////
203 // Low-level referencee and referencer methods
205 // These methods provide the lowest level for
206 // creating references between reachability nodes
207 // and handling the details of maintaining both
208 // list of referencers and referencees.
210 ////////////////////////////////////////////////
211 protected void addRefEdge(RefSrcNode referencer,
212 HeapRegionNode referencee,
214 assert referencer != null;
215 assert referencee != null;
217 assert edge.getSrc() == referencer;
218 assert edge.getDst() == referencee;
219 assert belongsToThis(referencer);
220 assert belongsToThis(referencee);
222 // edges are getting added twice to graphs now, the
223 // kind that should have abstract facts merged--use
224 // this check to prevent that
225 assert referencer.getReferenceTo(referencee,
230 referencer.addReferencee(edge);
231 referencee.addReferencer(edge);
234 protected void removeRefEdge(RefEdge e) {
235 removeRefEdge(e.getSrc(),
241 protected void removeRefEdge(RefSrcNode referencer,
242 HeapRegionNode referencee,
245 assert referencer != null;
246 assert referencee != null;
248 RefEdge edge = referencer.getReferenceTo(referencee,
252 assert edge == referencee.getReferenceFrom(referencer,
256 referencer.removeReferencee(edge);
257 referencee.removeReferencer(edge);
260 // return whether at least one edge was removed
261 protected boolean clearRefEdgesFrom(RefSrcNode referencer,
265 assert referencer != null;
267 boolean atLeastOneEdgeRemoved = false;
269 // get a copy of the set to iterate over, otherwise
270 // we will be trying to take apart the set as we
271 // are iterating over it, which won't work
272 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
273 while( i.hasNext() ) {
274 RefEdge edge = i.next();
277 (edge.typeEquals(type) && edge.fieldEquals(field))
280 HeapRegionNode referencee = edge.getDst();
282 removeRefEdge(referencer,
287 atLeastOneEdgeRemoved = true;
291 return atLeastOneEdgeRemoved;
294 protected void clearRefEdgesTo(HeapRegionNode referencee,
298 assert referencee != null;
300 // get a copy of the set to iterate over, otherwise
301 // we will be trying to take apart the set as we
302 // are iterating over it, which won't work
303 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
304 while( i.hasNext() ) {
305 RefEdge edge = i.next();
308 (edge.typeEquals(type) && edge.fieldEquals(field))
311 RefSrcNode referencer = edge.getSrc();
313 removeRefEdge(referencer,
321 protected void clearNonVarRefEdgesTo(HeapRegionNode referencee) {
322 assert referencee != null;
324 // get a copy of the set to iterate over, otherwise
325 // we will be trying to take apart the set as we
326 // are iterating over it, which won't work
327 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
328 while( i.hasNext() ) {
329 RefEdge edge = i.next();
330 RefSrcNode referencer = edge.getSrc();
331 if( !(referencer instanceof VariableNode) ) {
332 removeRefEdge(referencer,
340 // this is a common operation in many transfer functions: we want
341 // to add an edge, but if there is already such an edge we should
342 // merge the properties of the existing and the new edges
343 protected void addEdgeOrMergeWithExisting(RefEdge edgeNew) {
345 RefSrcNode src = edgeNew.getSrc();
346 assert belongsToThis(src);
348 HeapRegionNode dst = edgeNew.getDst();
349 assert belongsToThis(dst);
351 // look to see if an edge with same field exists
352 // and merge with it, otherwise just add the edge
353 RefEdge edgeExisting = src.getReferenceTo(dst,
358 if( edgeExisting != null ) {
359 edgeExisting.setBeta(
360 Canonical.unionORpreds(edgeExisting.getBeta(),
364 edgeExisting.setPreds(
365 Canonical.join(edgeExisting.getPreds(),
369 edgeExisting.setTaints(
370 Canonical.unionORpreds(edgeExisting.getTaints(),
376 addRefEdge(src, dst, edgeNew);
382 ////////////////////////////////////////////////////
384 // Assignment Operation Methods
386 // These methods are high-level operations for
387 // modeling program assignment statements using
388 // the low-level reference create/remove methods
391 ////////////////////////////////////////////////////
393 public void assignTempEqualToStringLiteral(TempDescriptor x,
394 AllocSite asStringLiteral,
395 AllocSite asStringLiteralBytes,
396 FieldDescriptor fdStringBytesField) {
397 // model this to get points-to information right for
398 // pointers to string literals, even though it doesn't affect
399 // reachability paths in the heap
400 assignTempEqualToNewAlloc( x,
403 assignTempEqualToNewAlloc( tdStrLiteralBytes,
404 asStringLiteralBytes );
406 assignTempXFieldFEqualToTempY( x,
413 public void assignTempXEqualToTempY(TempDescriptor x,
415 assignTempXEqualToCastedTempY(x, y, null);
419 public void assignTempXEqualToCastedTempY(TempDescriptor x,
421 TypeDescriptor tdCast) {
423 VariableNode lnX = getVariableNodeFromTemp(x);
424 VariableNode lnY = getVariableNodeFromTemp(y);
426 clearRefEdgesFrom(lnX, null, null, true);
428 // note it is possible that the types of temps in the
429 // flat node to analyze will reveal that some typed
430 // edges in the reachability graph are impossible
431 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
433 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
434 while( itrYhrn.hasNext() ) {
435 RefEdge edgeY = itrYhrn.next();
436 HeapRegionNode referencee = edgeY.getDst();
437 RefEdge edgeNew = edgeY.copy();
439 if( !isSuperiorType(x.getType(), edgeY.getType() ) ) {
440 impossibleEdges.add(edgeY);
446 if( tdCast == null ) {
447 edgeNew.setType(mostSpecificType(y.getType(),
453 edgeNew.setType(mostSpecificType(y.getType(),
455 referencee.getType(),
461 edgeNew.setField(null);
463 addRefEdge(lnX, referencee, edgeNew);
466 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
467 while( itrImp.hasNext() ) {
468 RefEdge edgeImp = itrImp.next();
469 removeRefEdge(edgeImp);
474 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
477 FlatNode currentProgramPoint
480 VariableNode lnX = getVariableNodeFromTemp(x);
481 VariableNode lnY = getVariableNodeFromTemp(y);
483 clearRefEdgesFrom(lnX, null, null, true);
485 // note it is possible that the types of temps in the
486 // flat node to analyze will reveal that some typed
487 // edges in the reachability graph are impossible
488 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
490 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
491 while( itrYhrn.hasNext() ) {
492 RefEdge edgeY = itrYhrn.next();
493 HeapRegionNode hrnY = edgeY.getDst();
494 ReachSet betaY = edgeY.getBeta();
496 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
498 while( itrHrnFhrn.hasNext() ) {
499 RefEdge edgeHrn = itrHrnFhrn.next();
500 HeapRegionNode hrnHrn = edgeHrn.getDst();
501 ReachSet betaHrn = edgeHrn.getBeta();
503 // prune edges that are not a matching field
504 if( edgeHrn.getType() != null &&
505 !edgeHrn.getField().equals(f.getSymbol() )
510 // check for impossible edges
511 if( !isSuperiorType(x.getType(), edgeHrn.getType() ) ) {
512 impossibleEdges.add(edgeHrn);
516 TypeDescriptor tdNewEdge =
517 mostSpecificType(edgeHrn.getType(),
521 TaintSet taints = Canonical.unionORpreds(edgeHrn.getTaints(),
525 // the DFJ way to generate taints changes for field statements
526 taints = Canonical.changeWhereDefined(taints,
527 currentProgramPoint);
530 RefEdge edgeNew = new RefEdge(lnX,
534 Canonical.intersection(betaY, betaHrn),
539 addEdgeOrMergeWithExisting(edgeNew);
543 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
544 while( itrImp.hasNext() ) {
545 RefEdge edgeImp = itrImp.next();
546 removeRefEdge(edgeImp);
549 // anytime you might remove edges between heap regions
550 // you must global sweep to clean up broken reachability
551 if( !impossibleEdges.isEmpty() ) {
552 if( !DISABLE_GLOBAL_SWEEP ) {
560 // return whether a strong update was actually effected
561 public boolean assignTempXFieldFEqualToTempY(TempDescriptor x,
564 FlatNode currentProgramPoint
567 VariableNode lnX = getVariableNodeFromTemp(x);
568 VariableNode lnY = getVariableNodeFromTemp(y);
570 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
571 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
573 // note it is possible that the types of temps in the
574 // flat node to analyze will reveal that some typed
575 // edges in the reachability graph are impossible
576 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
578 // first look for possible strong updates and remove those edges
579 boolean strongUpdateCond = false;
580 boolean edgeRemovedByStrongUpdate = false;
582 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
583 while( itrXhrn.hasNext() ) {
584 RefEdge edgeX = itrXhrn.next();
585 HeapRegionNode hrnX = edgeX.getDst();
587 // we can do a strong update here if one of two cases holds
589 f != DisjointAnalysis.getArrayField(f.getType() ) &&
590 ( (hrnX.getNumReferencers() == 1) || // case 1
591 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
594 if( !DISABLE_STRONG_UPDATES ) {
595 strongUpdateCond = true;
598 clearRefEdgesFrom(hrnX,
603 edgeRemovedByStrongUpdate = true;
609 // then do all token propagation
610 itrXhrn = lnX.iteratorToReferencees();
611 while( itrXhrn.hasNext() ) {
612 RefEdge edgeX = itrXhrn.next();
613 HeapRegionNode hrnX = edgeX.getDst();
614 ReachSet betaX = edgeX.getBeta();
615 ReachSet R = Canonical.intersection(hrnX.getAlpha(),
619 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
620 while( itrYhrn.hasNext() ) {
621 RefEdge edgeY = itrYhrn.next();
622 HeapRegionNode hrnY = edgeY.getDst();
623 ReachSet O = edgeY.getBeta();
625 // check for impossible edges
626 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
627 impossibleEdges.add(edgeY);
631 // propagate tokens over nodes starting from hrnSrc, and it will
632 // take care of propagating back up edges from any touched nodes
633 ChangeSet Cy = Canonical.unionUpArityToChangeSet(O, R);
634 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
636 // then propagate back just up the edges from hrn
637 ChangeSet Cx = Canonical.unionUpArityToChangeSet(R, O);
638 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
640 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
641 new Hashtable<RefEdge, ChangeSet>();
643 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
644 while( referItr.hasNext() ) {
645 RefEdge edgeUpstream = referItr.next();
646 todoEdges.add(edgeUpstream);
647 edgePlannedChanges.put(edgeUpstream, Cx);
650 propagateTokensOverEdges(todoEdges,
657 // apply the updates to reachability
658 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
659 while( nodeItr.hasNext() ) {
660 nodeItr.next().applyAlphaNew();
663 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
664 while( edgeItr.hasNext() ) {
665 edgeItr.next().applyBetaNew();
669 // then go back through and add the new edges
670 itrXhrn = lnX.iteratorToReferencees();
671 while( itrXhrn.hasNext() ) {
672 RefEdge edgeX = itrXhrn.next();
673 HeapRegionNode hrnX = edgeX.getDst();
675 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
676 while( itrYhrn.hasNext() ) {
677 RefEdge edgeY = itrYhrn.next();
678 HeapRegionNode hrnY = edgeY.getDst();
680 // skip impossible edges here, we already marked them
681 // when computing reachability propagations above
682 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
686 // prepare the new reference edge hrnX.f -> hrnY
687 TypeDescriptor tdNewEdge =
688 mostSpecificType(y.getType(),
693 TaintSet taints = edgeY.getTaints();
696 // the DFJ way to generate taints changes for field statements
697 taints = Canonical.changeWhereDefined(taints,
698 currentProgramPoint);
706 Canonical.changePredsTo(
707 Canonical.pruneBy(edgeY.getBeta(),
716 addEdgeOrMergeWithExisting(edgeNew);
720 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
721 while( itrImp.hasNext() ) {
722 RefEdge edgeImp = itrImp.next();
723 removeRefEdge(edgeImp);
726 // if there was a strong update, make sure to improve
727 // reachability with a global sweep
728 if( edgeRemovedByStrongUpdate || !impossibleEdges.isEmpty() ) {
729 if( !DISABLE_GLOBAL_SWEEP ) {
734 return edgeRemovedByStrongUpdate;
738 public void assignReturnEqualToTemp(TempDescriptor x) {
740 VariableNode lnR = getVariableNodeFromTemp(tdReturn);
741 VariableNode lnX = getVariableNodeFromTemp(x);
743 clearRefEdgesFrom(lnR, null, null, true);
745 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
746 while( itrXhrn.hasNext() ) {
747 RefEdge edgeX = itrXhrn.next();
748 HeapRegionNode referencee = edgeX.getDst();
749 RefEdge edgeNew = edgeX.copy();
751 edgeNew.setTaints(Canonical.changePredsTo(edgeNew.getTaints(),
756 addRefEdge(lnR, referencee, edgeNew);
761 public void assignTempEqualToNewAlloc(TempDescriptor x,
768 // after the age operation the newest (or zero-ith oldest)
769 // node associated with the allocation site should have
770 // no references to it as if it were a newly allocated
772 Integer idNewest = as.getIthOldest(0);
773 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
774 assert hrnNewest != null;
776 VariableNode lnX = getVariableNodeFromTemp(x);
777 clearRefEdgesFrom(lnX, null, null, true);
779 // make a new reference to allocated node
780 TypeDescriptor type = as.getType();
783 new RefEdge(lnX, // source
787 hrnNewest.getAlpha(), // beta
788 predsTrue, // predicates
789 TaintSet.factory() // taints
792 addRefEdge(lnX, hrnNewest, edgeNew);
796 // use the allocation site (unique to entire analysis) to
797 // locate the heap region nodes in this reachability graph
798 // that should be aged. The process models the allocation
799 // of new objects and collects all the oldest allocations
800 // in a summary node to allow for a finite analysis
802 // There is an additional property of this method. After
803 // running it on a particular reachability graph (many graphs
804 // may have heap regions related to the same allocation site)
805 // the heap region node objects in this reachability graph will be
806 // allocated. Therefore, after aging a graph for an allocation
807 // site, attempts to retrieve the heap region nodes using the
808 // integer id's contained in the allocation site should always
809 // return non-null heap regions.
810 public void age(AllocSite as) {
812 // keep track of allocation sites that are represented
813 // in this graph for efficiency with other operations
816 // if there is a k-th oldest node, it merges into
818 Integer idK = as.getOldest();
819 if( id2hrn.containsKey(idK) ) {
820 HeapRegionNode hrnK = id2hrn.get(idK);
822 // retrieve the summary node, or make it
824 HeapRegionNode hrnSummary = getSummaryNode(as, false);
826 mergeIntoSummary(hrnK, hrnSummary);
829 // move down the line of heap region nodes
830 // clobbering the ith and transferring all references
831 // to and from i-1 to node i.
832 for( int i = allocationDepth - 1; i > 0; --i ) {
834 // only do the transfer if the i-1 node exists
835 Integer idImin1th = as.getIthOldest(i - 1);
836 if( id2hrn.containsKey(idImin1th) ) {
837 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
838 if( hrnImin1.isWiped() ) {
839 // there is no info on this node, just skip
843 // either retrieve or make target of transfer
844 HeapRegionNode hrnI = getIthNode(as, i, false);
846 transferOnto(hrnImin1, hrnI);
851 // as stated above, the newest node should have had its
852 // references moved over to the second oldest, so we wipe newest
853 // in preparation for being the new object to assign something to
854 HeapRegionNode hrn0 = getIthNode(as, 0, false);
857 // now tokens in reachability sets need to "age" also
858 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
859 while( itrAllHRNodes.hasNext() ) {
860 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
861 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
863 ageTuplesFrom(as, hrnToAge);
865 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
866 while( itrEdges.hasNext() ) {
867 ageTuplesFrom(as, itrEdges.next() );
872 // after tokens have been aged, reset newest node's reachability
873 // and a brand new node has a "true" predicate
874 hrn0.setAlpha(hrn0.getInherent() );
875 hrn0.setPreds(predsTrue);
879 // either retrieve or create the needed heap region node
880 protected HeapRegionNode getSummaryNode(AllocSite as,
885 idSummary = as.getSummaryShadow();
887 idSummary = as.getSummary();
890 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
892 if( hrnSummary == null ) {
894 String strDesc = as.toStringForDOT()+"\\nsummary";
897 createNewHeapRegionNode(idSummary, // id or null to generate a new one
898 false, // single object?
900 false, // out-of-context?
901 as.getType(), // type
902 as, // allocation site
903 null, // inherent reach
904 null, // current reach
905 predsEmpty, // predicates
906 strDesc // description
913 // either retrieve or create the needed heap region node
914 protected HeapRegionNode getIthNode(AllocSite as,
920 idIth = as.getIthOldestShadow(i);
922 idIth = as.getIthOldest(i);
925 HeapRegionNode hrnIth = id2hrn.get(idIth);
927 if( hrnIth == null ) {
929 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
931 hrnIth = createNewHeapRegionNode(idIth, // id or null to generate a new one
932 true, // single object?
934 false, // out-of-context?
935 as.getType(), // type
936 as, // allocation site
937 null, // inherent reach
938 null, // current reach
939 predsEmpty, // predicates
940 strDesc // description
948 protected void mergeIntoSummary(HeapRegionNode hrn,
949 HeapRegionNode hrnSummary) {
950 assert hrnSummary.isNewSummary();
952 // assert that these nodes belong to THIS graph
953 assert belongsToThis(hrn);
954 assert belongsToThis(hrnSummary);
956 assert hrn != hrnSummary;
958 // transfer references _from_ hrn over to hrnSummary
959 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
960 while( itrReferencee.hasNext() ) {
961 RefEdge edge = itrReferencee.next();
962 RefEdge edgeMerged = edge.copy();
963 edgeMerged.setSrc(hrnSummary);
965 HeapRegionNode hrnReferencee = edge.getDst();
966 RefEdge edgeSummary =
967 hrnSummary.getReferenceTo(hrnReferencee,
972 if( edgeSummary == null ) {
973 // the merge is trivial, nothing to be done
974 addRefEdge(hrnSummary, hrnReferencee, edgeMerged);
977 // otherwise an edge from the referencer to hrnSummary exists already
978 // and the edge referencer->hrn should be merged with it
980 Canonical.unionORpreds(edgeMerged.getBeta(),
981 edgeSummary.getBeta()
984 edgeSummary.setPreds(
985 Canonical.join(edgeMerged.getPreds(),
986 edgeSummary.getPreds()
992 // next transfer references _to_ hrn over to hrnSummary
993 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
994 while( itrReferencer.hasNext() ) {
995 RefEdge edge = itrReferencer.next();
996 RefEdge edgeMerged = edge.copy();
997 edgeMerged.setDst(hrnSummary);
999 RefSrcNode onReferencer = edge.getSrc();
1000 RefEdge edgeSummary =
1001 onReferencer.getReferenceTo(hrnSummary,
1006 if( edgeSummary == null ) {
1007 // the merge is trivial, nothing to be done
1008 addRefEdge(onReferencer, hrnSummary, edgeMerged);
1011 // otherwise an edge from the referencer to alpha_S exists already
1012 // and the edge referencer->alpha_K should be merged with it
1013 edgeSummary.setBeta(
1014 Canonical.unionORpreds(edgeMerged.getBeta(),
1015 edgeSummary.getBeta()
1018 edgeSummary.setPreds(
1019 Canonical.join(edgeMerged.getPreds(),
1020 edgeSummary.getPreds()
1026 // then merge hrn reachability into hrnSummary
1027 hrnSummary.setAlpha(
1028 Canonical.unionORpreds(hrnSummary.getAlpha(),
1033 hrnSummary.setPreds(
1034 Canonical.join(hrnSummary.getPreds(),
1039 // and afterward, this node is gone
1044 protected void transferOnto(HeapRegionNode hrnA,
1045 HeapRegionNode hrnB) {
1047 assert belongsToThis(hrnA);
1048 assert belongsToThis(hrnB);
1049 assert hrnA != hrnB;
1051 // clear references in and out of node b?
1052 assert hrnB.isWiped();
1054 // copy each: (edge in and out of A) to B
1055 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
1056 while( itrReferencee.hasNext() ) {
1057 RefEdge edge = itrReferencee.next();
1058 HeapRegionNode hrnReferencee = edge.getDst();
1059 RefEdge edgeNew = edge.copy();
1060 edgeNew.setSrc(hrnB);
1061 edgeNew.setDst(hrnReferencee);
1063 addRefEdge(hrnB, hrnReferencee, edgeNew);
1066 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
1067 while( itrReferencer.hasNext() ) {
1068 RefEdge edge = itrReferencer.next();
1069 RefSrcNode rsnReferencer = edge.getSrc();
1070 RefEdge edgeNew = edge.copy();
1071 edgeNew.setSrc(rsnReferencer);
1072 edgeNew.setDst(hrnB);
1074 addRefEdge(rsnReferencer, hrnB, edgeNew);
1077 // replace hrnB reachability and preds with hrnA's
1078 hrnB.setAlpha(hrnA.getAlpha() );
1079 hrnB.setPreds(hrnA.getPreds() );
1081 // after transfer, wipe out source
1082 wipeOut(hrnA, true);
1086 // the purpose of this method is to conceptually "wipe out"
1087 // a heap region from the graph--purposefully not called REMOVE
1088 // because the node is still hanging around in the graph, just
1089 // not mechanically connected or have any reach or predicate
1090 // information on it anymore--lots of ops can use this
1091 protected void wipeOut(HeapRegionNode hrn,
1092 boolean wipeVariableReferences) {
1094 assert belongsToThis(hrn);
1096 clearRefEdgesFrom(hrn, null, null, true);
1098 if( wipeVariableReferences ) {
1099 clearRefEdgesTo(hrn, null, null, true);
1101 clearNonVarRefEdgesTo(hrn);
1104 hrn.setAlpha(rsetEmpty);
1105 hrn.setPreds(predsEmpty);
1109 protected void ageTuplesFrom(AllocSite as, RefEdge edge) {
1111 Canonical.ageTuplesFrom(edge.getBeta(),
1117 protected void ageTuplesFrom(AllocSite as, HeapRegionNode hrn) {
1119 Canonical.ageTuplesFrom(hrn.getAlpha(),
1127 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1129 HashSet<HeapRegionNode> nodesWithNewAlpha,
1130 HashSet<RefEdge> edgesWithNewBeta) {
1132 HashSet<HeapRegionNode> todoNodes
1133 = new HashSet<HeapRegionNode>();
1134 todoNodes.add(nPrime);
1136 HashSet<RefEdge> todoEdges
1137 = new HashSet<RefEdge>();
1139 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1140 = new Hashtable<HeapRegionNode, ChangeSet>();
1141 nodePlannedChanges.put(nPrime, c0);
1143 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1144 = new Hashtable<RefEdge, ChangeSet>();
1146 // first propagate change sets everywhere they can go
1147 while( !todoNodes.isEmpty() ) {
1148 HeapRegionNode n = todoNodes.iterator().next();
1149 ChangeSet C = nodePlannedChanges.get(n);
1151 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1152 while( referItr.hasNext() ) {
1153 RefEdge edge = referItr.next();
1154 todoEdges.add(edge);
1156 if( !edgePlannedChanges.containsKey(edge) ) {
1157 edgePlannedChanges.put(edge,
1162 edgePlannedChanges.put(edge,
1163 Canonical.union(edgePlannedChanges.get(edge),
1169 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1170 while( refeeItr.hasNext() ) {
1171 RefEdge edgeF = refeeItr.next();
1172 HeapRegionNode m = edgeF.getDst();
1174 ChangeSet changesToPass = ChangeSet.factory();
1176 Iterator<ChangeTuple> itrCprime = C.iterator();
1177 while( itrCprime.hasNext() ) {
1178 ChangeTuple c = itrCprime.next();
1179 if( edgeF.getBeta().containsIgnorePreds(c.getStateToMatch() )
1182 changesToPass = Canonical.add(changesToPass, c);
1186 if( !changesToPass.isEmpty() ) {
1187 if( !nodePlannedChanges.containsKey(m) ) {
1188 nodePlannedChanges.put(m, ChangeSet.factory() );
1191 ChangeSet currentChanges = nodePlannedChanges.get(m);
1193 if( !changesToPass.isSubset(currentChanges) ) {
1195 nodePlannedChanges.put(m,
1196 Canonical.union(currentChanges,
1205 todoNodes.remove(n);
1208 // then apply all of the changes for each node at once
1209 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1210 while( itrMap.hasNext() ) {
1211 Map.Entry me = (Map.Entry)itrMap.next();
1212 HeapRegionNode n = (HeapRegionNode) me.getKey();
1213 ChangeSet C = (ChangeSet) me.getValue();
1215 // this propagation step is with respect to one change,
1216 // so we capture the full change from the old alpha:
1217 ReachSet localDelta = Canonical.applyChangeSet(n.getAlpha(),
1221 // but this propagation may be only one of many concurrent
1222 // possible changes, so keep a running union with the node's
1223 // partially updated new alpha set
1224 n.setAlphaNew(Canonical.unionORpreds(n.getAlphaNew(),
1229 nodesWithNewAlpha.add(n);
1232 propagateTokensOverEdges(todoEdges,
1239 protected void propagateTokensOverEdges(HashSet <RefEdge> todoEdges,
1240 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1241 HashSet <RefEdge> edgesWithNewBeta) {
1243 // first propagate all change tuples everywhere they can go
1244 while( !todoEdges.isEmpty() ) {
1245 RefEdge edgeE = todoEdges.iterator().next();
1246 todoEdges.remove(edgeE);
1248 if( !edgePlannedChanges.containsKey(edgeE) ) {
1249 edgePlannedChanges.put(edgeE,
1254 ChangeSet C = edgePlannedChanges.get(edgeE);
1256 ChangeSet changesToPass = ChangeSet.factory();
1258 Iterator<ChangeTuple> itrC = C.iterator();
1259 while( itrC.hasNext() ) {
1260 ChangeTuple c = itrC.next();
1261 if( edgeE.getBeta().containsIgnorePreds(c.getStateToMatch() )
1264 changesToPass = Canonical.add(changesToPass, c);
1268 RefSrcNode rsn = edgeE.getSrc();
1270 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1271 HeapRegionNode n = (HeapRegionNode) rsn;
1273 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1274 while( referItr.hasNext() ) {
1275 RefEdge edgeF = referItr.next();
1277 if( !edgePlannedChanges.containsKey(edgeF) ) {
1278 edgePlannedChanges.put(edgeF,
1283 ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
1285 if( !changesToPass.isSubset(currentChanges) ) {
1286 todoEdges.add(edgeF);
1287 edgePlannedChanges.put(edgeF,
1288 Canonical.union(currentChanges,
1297 // then apply all of the changes for each edge at once
1298 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1299 while( itrMap.hasNext() ) {
1300 Map.Entry me = (Map.Entry)itrMap.next();
1301 RefEdge e = (RefEdge) me.getKey();
1302 ChangeSet C = (ChangeSet) me.getValue();
1304 // this propagation step is with respect to one change,
1305 // so we capture the full change from the old beta:
1306 ReachSet localDelta =
1307 Canonical.applyChangeSet(e.getBeta(),
1312 // but this propagation may be only one of many concurrent
1313 // possible changes, so keep a running union with the edge's
1314 // partially updated new beta set
1315 e.setBetaNew(Canonical.unionORpreds(e.getBetaNew(),
1320 edgesWithNewBeta.add(e);
1325 public void taintInSetVars(FlatSESEEnterNode sese) {
1327 Iterator<TempDescriptor> isvItr = sese.getInVarSet().iterator();
1328 while( isvItr.hasNext() ) {
1329 TempDescriptor isv = isvItr.next();
1331 // use this where defined flatnode to support RCR/DFJ
1332 FlatNode whereDefined = null;
1334 // in-set var taints should NOT propagate back into callers
1335 // so give it FALSE(EMPTY) predicates
1345 public void taintStallSite(FlatNode stallSite,
1346 TempDescriptor var) {
1348 // use this where defined flatnode to support RCR/DFJ
1349 FlatNode whereDefined = null;
1351 // stall site taint should propagate back into callers
1352 // so give it TRUE predicates
1361 protected void taintTemp(FlatSESEEnterNode sese,
1364 FlatNode whereDefined,
1368 VariableNode vn = getVariableNodeFromTemp(var);
1370 Iterator<RefEdge> reItr = vn.iteratorToReferencees();
1371 while( reItr.hasNext() ) {
1372 RefEdge re = reItr.next();
1374 Taint taint = Taint.factory(sese,
1377 re.getDst().getAllocSite(),
1382 re.setTaints(Canonical.add(re.getTaints(),
1389 public void removeInContextTaints(FlatSESEEnterNode sese) {
1391 Iterator meItr = id2hrn.entrySet().iterator();
1392 while( meItr.hasNext() ) {
1393 Map.Entry me = (Map.Entry)meItr.next();
1394 Integer id = (Integer) me.getKey();
1395 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1397 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1398 while( reItr.hasNext() ) {
1399 RefEdge re = reItr.next();
1401 re.setTaints(Canonical.removeInContextTaints(re.getTaints(),
1409 public void removeAllStallSiteTaints() {
1411 Iterator meItr = id2hrn.entrySet().iterator();
1412 while( meItr.hasNext() ) {
1413 Map.Entry me = (Map.Entry)meItr.next();
1414 Integer id = (Integer) me.getKey();
1415 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1417 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1418 while( reItr.hasNext() ) {
1419 RefEdge re = reItr.next();
1421 re.setTaints(Canonical.removeStallSiteTaints(re.getTaints()
1429 // used in makeCalleeView below to decide if there is
1430 // already an appropriate out-of-context edge in a callee
1431 // view graph for merging, or null if a new one will be added
1433 getOutOfContextReferenceTo(HeapRegionNode hrn,
1434 TypeDescriptor srcType,
1435 TypeDescriptor refType,
1437 assert belongsToThis(hrn);
1439 HeapRegionNode hrnInContext = id2hrn.get(hrn.getID() );
1440 if( hrnInContext == null ) {
1444 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1445 while( refItr.hasNext() ) {
1446 RefEdge re = refItr.next();
1448 assert belongsToThis(re.getSrc() );
1449 assert belongsToThis(re.getDst() );
1451 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1455 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1456 if( !hrnSrc.isOutOfContext() ) {
1460 if( srcType == null ) {
1461 if( hrnSrc.getType() != null ) {
1465 if( !srcType.equals(hrnSrc.getType() ) ) {
1470 if( !re.typeEquals(refType) ) {
1474 if( !re.fieldEquals(refField) ) {
1478 // tada! We found it!
1485 // used below to convert a ReachSet to its callee-context
1486 // equivalent with respect to allocation sites in this graph
1487 protected ReachSet toCalleeContext(ReachSet rs,
1488 ExistPredSet predsNodeOrEdge,
1489 Set<HrnIdOoc> oocHrnIdOoc2callee
1491 ReachSet out = ReachSet.factory();
1493 Iterator<ReachState> itr = rs.iterator();
1494 while( itr.hasNext() ) {
1495 ReachState stateCaller = itr.next();
1497 ReachState stateCallee = stateCaller;
1499 Iterator<AllocSite> asItr = allocSites.iterator();
1500 while( asItr.hasNext() ) {
1501 AllocSite as = asItr.next();
1503 ReachState stateNew = ReachState.factory();
1504 Iterator<ReachTuple> rtItr = stateCallee.iterator();
1505 while( rtItr.hasNext() ) {
1506 ReachTuple rt = rtItr.next();
1508 // only translate this tuple if it is
1509 // in the out-callee-context bag
1510 HrnIdOoc hio = new HrnIdOoc(rt.getHrnID(),
1513 if( !oocHrnIdOoc2callee.contains(hio) ) {
1514 stateNew = Canonical.addUpArity(stateNew, rt);
1518 int age = as.getAgeCategory(rt.getHrnID() );
1520 // this is the current mapping, where 0, 1, 2S were allocated
1521 // in the current context, 0?, 1? and 2S? were allocated in a
1522 // previous context, and we're translating to a future context
1534 if( age == AllocSite.AGE_notInThisSite ) {
1535 // things not from the site just go back in
1536 stateNew = Canonical.addUpArity(stateNew, rt);
1538 } else if( age == AllocSite.AGE_summary ||
1542 stateNew = Canonical.addUpArity(stateNew,
1543 ReachTuple.factory(as.getSummary(),
1546 true // out-of-context
1551 // otherwise everything else just goes to an out-of-context
1552 // version, everything else the same
1553 Integer I = as.getAge(rt.getHrnID() );
1556 assert !rt.isMultiObject();
1558 stateNew = Canonical.addUpArity(stateNew,
1559 ReachTuple.factory(rt.getHrnID(),
1560 rt.isMultiObject(), // multi
1562 true // out-of-context
1568 stateCallee = stateNew;
1571 // make a predicate of the caller graph element
1572 // and the caller state we just converted
1573 ExistPredSet predsWithState = ExistPredSet.factory();
1575 Iterator<ExistPred> predItr = predsNodeOrEdge.iterator();
1576 while( predItr.hasNext() ) {
1577 ExistPred predNodeOrEdge = predItr.next();
1580 Canonical.add(predsWithState,
1581 ExistPred.factory(predNodeOrEdge.n_hrnID,
1582 predNodeOrEdge.e_tdSrc,
1583 predNodeOrEdge.e_hrnSrcID,
1584 predNodeOrEdge.e_hrnDstID,
1585 predNodeOrEdge.e_type,
1586 predNodeOrEdge.e_field,
1589 predNodeOrEdge.e_srcOutCalleeContext,
1590 predNodeOrEdge.e_srcOutCallerContext
1595 stateCallee = Canonical.changePredsTo(stateCallee,
1598 out = Canonical.add(out,
1602 assert out.isCanonical();
1606 // used below to convert a ReachSet to its caller-context
1607 // equivalent with respect to allocation sites in this graph
1609 toCallerContext(ReachSet rs,
1610 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1612 ReachSet out = ReachSet.factory();
1614 // when the mapping is null it means there were no
1615 // predicates satisfied
1616 if( calleeStatesSatisfied == null ) {
1620 Iterator<ReachState> itr = rs.iterator();
1621 while( itr.hasNext() ) {
1622 ReachState stateCallee = itr.next();
1624 if( calleeStatesSatisfied.containsKey(stateCallee) ) {
1626 // starting from one callee state...
1627 ReachSet rsCaller = ReachSet.factory(stateCallee);
1629 // possibly branch it into many states, which any
1630 // allocation site might do, so lots of derived states
1631 Iterator<AllocSite> asItr = allocSites.iterator();
1632 while( asItr.hasNext() ) {
1633 AllocSite as = asItr.next();
1634 rsCaller = Canonical.toCallerContext(rsCaller, as);
1637 // then before adding each derived, now caller-context
1638 // states to the output, attach the appropriate pred
1639 // based on the source callee state
1640 Iterator<ReachState> stateItr = rsCaller.iterator();
1641 while( stateItr.hasNext() ) {
1642 ReachState stateCaller = stateItr.next();
1643 stateCaller = Canonical.attach(stateCaller,
1644 calleeStatesSatisfied.get(stateCallee)
1646 out = Canonical.add(out,
1653 assert out.isCanonical();
1658 // used below to convert a ReachSet to an equivalent
1659 // version with shadow IDs merged into unshadowed IDs
1660 protected ReachSet unshadow(ReachSet rs) {
1662 Iterator<AllocSite> asItr = allocSites.iterator();
1663 while( asItr.hasNext() ) {
1664 AllocSite as = asItr.next();
1665 out = Canonical.unshadow(out, as);
1667 assert out.isCanonical();
1672 // convert a caller taint set into a callee taint set
1674 toCalleeContext(TaintSet ts,
1675 ExistPredSet predsEdge) {
1677 TaintSet out = TaintSet.factory();
1679 // the idea is easy, the taint identifier itself doesn't
1680 // change at all, but the predicates should be tautology:
1681 // start with the preds passed in from the caller edge
1682 // that host the taints, and alter them to have the taint
1683 // added, just becoming more specific than edge predicate alone
1685 Iterator<Taint> itr = ts.iterator();
1686 while( itr.hasNext() ) {
1687 Taint tCaller = itr.next();
1689 ExistPredSet predsWithTaint = ExistPredSet.factory();
1691 Iterator<ExistPred> predItr = predsEdge.iterator();
1692 while( predItr.hasNext() ) {
1693 ExistPred predEdge = predItr.next();
1696 Canonical.add(predsWithTaint,
1697 ExistPred.factory(predEdge.e_tdSrc,
1698 predEdge.e_hrnSrcID,
1699 predEdge.e_hrnDstID,
1704 predEdge.e_srcOutCalleeContext,
1705 predEdge.e_srcOutCallerContext
1710 Taint tCallee = Canonical.changePredsTo(tCaller,
1713 out = Canonical.add(out,
1718 assert out.isCanonical();
1723 // used below to convert a TaintSet to its caller-context
1724 // equivalent, just eliminate Taints with bad preds
1726 toCallerContext(TaintSet ts,
1727 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied
1730 TaintSet out = TaintSet.factory();
1732 // when the mapping is null it means there were no
1733 // predicates satisfied
1734 if( calleeTaintsSatisfied == null ) {
1738 Iterator<Taint> itr = ts.iterator();
1739 while( itr.hasNext() ) {
1740 Taint tCallee = itr.next();
1742 if( calleeTaintsSatisfied.containsKey(tCallee) ) {
1745 Canonical.attach(Taint.factory(tCallee.sese,
1750 ExistPredSet.factory() ),
1751 calleeTaintsSatisfied.get(tCallee)
1753 out = Canonical.add(out,
1759 assert out.isCanonical();
1766 // use this method to make a new reach graph that is
1767 // what heap the FlatMethod callee from the FlatCall
1768 // would start with reaching from its arguments in
1771 makeCalleeView(FlatCall fc,
1772 FlatMethod fmCallee,
1773 Set<Integer> callerNodeIDsCopiedToCallee,
1774 boolean writeDebugDOTs
1778 // first traverse this context to find nodes and edges
1779 // that will be callee-reachable
1780 Set<HeapRegionNode> reachableCallerNodes =
1781 new HashSet<HeapRegionNode>();
1783 // caller edges between callee-reachable nodes
1784 Set<RefEdge> reachableCallerEdges =
1785 new HashSet<RefEdge>();
1787 // caller edges from arg vars, and the matching param index
1788 // because these become a special edge in callee
1789 Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1790 new Hashtable<RefEdge, Integer>();
1792 // caller edges from local vars or callee-unreachable nodes
1793 // (out-of-context sources) to callee-reachable nodes
1794 Set<RefEdge> oocCallerEdges =
1795 new HashSet<RefEdge>();
1798 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1800 TempDescriptor tdArg = fc.getArgMatchingParamIndex(fmCallee, i);
1801 VariableNode vnArgCaller = this.getVariableNodeFromTemp(tdArg);
1803 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1804 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1806 toVisitInCaller.add(vnArgCaller);
1808 while( !toVisitInCaller.isEmpty() ) {
1809 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1810 toVisitInCaller.remove(rsnCaller);
1811 visitedInCaller.add(rsnCaller);
1813 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1814 while( itrRefEdges.hasNext() ) {
1815 RefEdge reCaller = itrRefEdges.next();
1816 HeapRegionNode hrnCaller = reCaller.getDst();
1818 callerNodeIDsCopiedToCallee.add(hrnCaller.getID() );
1819 reachableCallerNodes.add(hrnCaller);
1821 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1822 reachableCallerEdges.add(reCaller);
1824 if( rsnCaller.equals(vnArgCaller) ) {
1825 reachableCallerArgEdges2paramIndex.put(reCaller, i);
1827 oocCallerEdges.add(reCaller);
1831 if( !visitedInCaller.contains(hrnCaller) ) {
1832 toVisitInCaller.add(hrnCaller);
1835 } // end edge iteration
1836 } // end visiting heap nodes in caller
1837 } // end iterating over parameters as starting points
1840 // now collect out-of-callee-context IDs and
1841 // map them to whether the ID is out of the caller
1843 Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1845 Iterator<Integer> itrInContext =
1846 callerNodeIDsCopiedToCallee.iterator();
1847 while( itrInContext.hasNext() ) {
1848 Integer hrnID = itrInContext.next();
1849 HeapRegionNode hrnCallerAndInContext = id2hrn.get(hrnID);
1851 Iterator<RefEdge> itrMightCross =
1852 hrnCallerAndInContext.iteratorToReferencers();
1853 while( itrMightCross.hasNext() ) {
1854 RefEdge edgeMightCross = itrMightCross.next();
1856 RefSrcNode rsnCallerAndOutContext =
1857 edgeMightCross.getSrc();
1859 if( rsnCallerAndOutContext instanceof VariableNode ) {
1860 // variables do not have out-of-context reach states,
1862 oocCallerEdges.add(edgeMightCross);
1866 HeapRegionNode hrnCallerAndOutContext =
1867 (HeapRegionNode) rsnCallerAndOutContext;
1869 // is this source node out-of-context?
1870 if( callerNodeIDsCopiedToCallee.contains(hrnCallerAndOutContext.getID() ) ) {
1871 // no, skip this edge
1876 oocCallerEdges.add(edgeMightCross);
1878 // add all reach tuples on the node to list
1879 // of things that are out-of-context: insight
1880 // if this node is reachable from someting that WAS
1881 // in-context, then this node should already be in-context
1882 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1883 while( stateItr.hasNext() ) {
1884 ReachState state = stateItr.next();
1886 Iterator<ReachTuple> rtItr = state.iterator();
1887 while( rtItr.hasNext() ) {
1888 ReachTuple rt = rtItr.next();
1890 oocHrnIdOoc2callee.add(new HrnIdOoc(rt.getHrnID(),
1899 // the callee view is a new graph: DON'T MODIFY *THIS* graph
1900 ReachGraph rg = new ReachGraph();
1902 // add nodes to callee graph
1903 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1904 while( hrnItr.hasNext() ) {
1905 HeapRegionNode hrnCaller = hrnItr.next();
1907 assert callerNodeIDsCopiedToCallee.contains(hrnCaller.getID() );
1908 assert !rg.id2hrn.containsKey(hrnCaller.getID() );
1910 ExistPred pred = ExistPred.factory(hrnCaller.getID(), null);
1911 ExistPredSet preds = ExistPredSet.factory(pred);
1913 rg.createNewHeapRegionNode(hrnCaller.getID(),
1914 hrnCaller.isSingleObject(),
1915 hrnCaller.isNewSummary(),
1916 false, // out-of-context?
1917 hrnCaller.getType(),
1918 hrnCaller.getAllocSite(),
1919 toCalleeContext(hrnCaller.getInherent(),
1923 toCalleeContext(hrnCaller.getAlpha(),
1928 hrnCaller.getDescription()
1932 // add param edges to callee graph
1934 reachableCallerArgEdges2paramIndex.entrySet().iterator();
1935 while( argEdges.hasNext() ) {
1936 Map.Entry me = (Map.Entry)argEdges.next();
1937 RefEdge reArg = (RefEdge) me.getKey();
1938 Integer index = (Integer) me.getValue();
1940 VariableNode vnCaller = (VariableNode) reArg.getSrc();
1941 TempDescriptor argCaller = vnCaller.getTempDescriptor();
1943 TempDescriptor paramCallee = fmCallee.getParameter(index);
1944 VariableNode vnCallee = rg.getVariableNodeFromTemp(paramCallee);
1946 HeapRegionNode hrnDstCaller = reArg.getDst();
1947 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
1948 assert hrnDstCallee != null;
1951 ExistPred.factory(argCaller,
1953 hrnDstCallee.getID(),
1958 true, // out-of-callee-context
1959 false // out-of-caller-context
1962 ExistPredSet preds =
1963 ExistPredSet.factory(pred);
1966 new RefEdge(vnCallee,
1970 toCalleeContext(reArg.getBeta(),
1975 toCalleeContext(reArg.getTaints(),
1979 rg.addRefEdge(vnCallee,
1985 // add in-context edges to callee graph
1986 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1987 while( reItr.hasNext() ) {
1988 RefEdge reCaller = reItr.next();
1989 RefSrcNode rsnCaller = reCaller.getSrc();
1990 assert rsnCaller instanceof HeapRegionNode;
1991 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1992 HeapRegionNode hrnDstCaller = reCaller.getDst();
1994 HeapRegionNode hrnSrcCallee = rg.id2hrn.get(hrnSrcCaller.getID() );
1995 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
1996 assert hrnSrcCallee != null;
1997 assert hrnDstCallee != null;
2000 ExistPred.factory(null,
2001 hrnSrcCallee.getID(),
2002 hrnDstCallee.getID(),
2004 reCaller.getField(),
2007 false, // out-of-callee-context
2008 false // out-of-caller-context
2011 ExistPredSet preds =
2012 ExistPredSet.factory(pred);
2015 new RefEdge(hrnSrcCallee,
2018 reCaller.getField(),
2019 toCalleeContext(reCaller.getBeta(),
2024 toCalleeContext(reCaller.getTaints(),
2028 rg.addRefEdge(hrnSrcCallee,
2034 // add out-of-context edges to callee graph
2035 reItr = oocCallerEdges.iterator();
2036 while( reItr.hasNext() ) {
2037 RefEdge reCaller = reItr.next();
2038 RefSrcNode rsnCaller = reCaller.getSrc();
2039 HeapRegionNode hrnDstCaller = reCaller.getDst();
2040 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2041 assert hrnDstCallee != null;
2043 TypeDescriptor oocNodeType;
2045 TempDescriptor oocPredSrcTemp = null;
2046 Integer oocPredSrcID = null;
2047 boolean outOfCalleeContext;
2048 boolean outOfCallerContext;
2050 if( rsnCaller instanceof VariableNode ) {
2051 VariableNode vnCaller = (VariableNode) rsnCaller;
2053 oocReach = rsetEmpty;
2054 oocPredSrcTemp = vnCaller.getTempDescriptor();
2055 outOfCalleeContext = true;
2056 outOfCallerContext = false;
2059 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2060 assert !callerNodeIDsCopiedToCallee.contains(hrnSrcCaller.getID() );
2061 oocNodeType = hrnSrcCaller.getType();
2062 oocReach = hrnSrcCaller.getAlpha();
2063 oocPredSrcID = hrnSrcCaller.getID();
2064 if( hrnSrcCaller.isOutOfContext() ) {
2065 outOfCalleeContext = false;
2066 outOfCallerContext = true;
2068 outOfCalleeContext = true;
2069 outOfCallerContext = false;
2074 ExistPred.factory(oocPredSrcTemp,
2076 hrnDstCallee.getID(),
2078 reCaller.getField(),
2085 ExistPredSet preds =
2086 ExistPredSet.factory(pred);
2088 RefEdge oocEdgeExisting =
2089 rg.getOutOfContextReferenceTo(hrnDstCallee,
2095 if( oocEdgeExisting == null ) {
2096 // for consistency, map one out-of-context "identifier"
2097 // to one heap region node id, otherwise no convergence
2098 String oocid = "oocid"+
2100 hrnDstCallee.getIDString()+
2103 reCaller.getField();
2105 Integer oocHrnID = oocid2hrnid.get(oocid);
2107 HeapRegionNode hrnCalleeAndOutContext;
2109 if( oocHrnID == null ) {
2111 hrnCalleeAndOutContext =
2112 rg.createNewHeapRegionNode(null, // ID
2113 false, // single object?
2114 false, // new summary?
2115 true, // out-of-context?
2117 null, // alloc site, shouldn't be used
2118 toCalleeContext(oocReach,
2122 toCalleeContext(oocReach,
2130 oocid2hrnid.put(oocid, hrnCalleeAndOutContext.getID() );
2134 // the mapping already exists, so see if node is there
2135 hrnCalleeAndOutContext = rg.id2hrn.get(oocHrnID);
2137 if( hrnCalleeAndOutContext == null ) {
2139 hrnCalleeAndOutContext =
2140 rg.createNewHeapRegionNode(oocHrnID, // ID
2141 false, // single object?
2142 false, // new summary?
2143 true, // out-of-context?
2145 null, // alloc site, shouldn't be used
2146 toCalleeContext(oocReach,
2150 toCalleeContext(oocReach,
2159 // otherwise it is there, so merge reachability
2160 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2161 toCalleeContext(oocReach,
2170 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2172 rg.addRefEdge(hrnCalleeAndOutContext,
2174 new RefEdge(hrnCalleeAndOutContext,
2177 reCaller.getField(),
2178 toCalleeContext(reCaller.getBeta(),
2183 toCalleeContext(reCaller.getTaints(),
2189 // the out-of-context edge already exists
2190 oocEdgeExisting.setBeta(Canonical.unionORpreds(oocEdgeExisting.getBeta(),
2191 toCalleeContext(reCaller.getBeta(),
2198 oocEdgeExisting.setPreds(Canonical.join(oocEdgeExisting.getPreds(),
2203 oocEdgeExisting.setTaints(Canonical.unionORpreds(oocEdgeExisting.getTaints(),
2204 toCalleeContext(reCaller.getTaints(),
2210 HeapRegionNode hrnCalleeAndOutContext =
2211 (HeapRegionNode) oocEdgeExisting.getSrc();
2212 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2213 toCalleeContext(oocReach,
2220 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2225 if( writeDebugDOTs ) {
2226 debugGraphPrefix = String.format("call%03d", debugCallSiteVisitCounter);
2227 rg.writeGraph(debugGraphPrefix+"calleeview",
2228 resolveMethodDebugDOTwriteLabels,
2229 resolveMethodDebugDOTselectTemps,
2230 resolveMethodDebugDOTpruneGarbage,
2231 resolveMethodDebugDOThideReach,
2232 resolveMethodDebugDOThideSubsetReach,
2233 resolveMethodDebugDOThidePreds,
2234 resolveMethodDebugDOThideEdgeTaints);
2240 private static Hashtable<String, Integer> oocid2hrnid =
2241 new Hashtable<String, Integer>();
2244 // useful since many graphs writes in the method call debug code
2245 private static boolean resolveMethodDebugDOTwriteLabels = true;
2246 private static boolean resolveMethodDebugDOTselectTemps = true;
2247 private static boolean resolveMethodDebugDOTpruneGarbage = true;
2248 private static boolean resolveMethodDebugDOThideReach = true;
2249 private static boolean resolveMethodDebugDOThideSubsetReach = true;
2250 private static boolean resolveMethodDebugDOThidePreds = true;
2251 private static boolean resolveMethodDebugDOThideEdgeTaints = false;
2253 static String debugGraphPrefix;
2254 static int debugCallSiteVisitCounter;
2255 static int debugCallSiteVisitStartCapture;
2256 static int debugCallSiteNumVisitsToCapture;
2257 static boolean debugCallSiteStopAfter;
2261 resolveMethodCall(FlatCall fc,
2262 FlatMethod fmCallee,
2263 ReachGraph rgCallee,
2264 Set<Integer> callerNodeIDsCopiedToCallee,
2265 boolean writeDebugDOTs
2268 if( writeDebugDOTs ) {
2270 System.out.println(" Writing out visit "+
2271 debugCallSiteVisitCounter+
2272 " to debug call site");
2274 debugGraphPrefix = String.format("call%03d",
2275 debugCallSiteVisitCounter);
2277 rgCallee.writeGraph(debugGraphPrefix+"callee",
2278 resolveMethodDebugDOTwriteLabels,
2279 resolveMethodDebugDOTselectTemps,
2280 resolveMethodDebugDOTpruneGarbage,
2281 resolveMethodDebugDOThideReach,
2282 resolveMethodDebugDOThideSubsetReach,
2283 resolveMethodDebugDOThidePreds,
2284 resolveMethodDebugDOThideEdgeTaints);
2286 writeGraph(debugGraphPrefix+"caller00In",
2287 resolveMethodDebugDOTwriteLabels,
2288 resolveMethodDebugDOTselectTemps,
2289 resolveMethodDebugDOTpruneGarbage,
2290 resolveMethodDebugDOThideReach,
2291 resolveMethodDebugDOThideSubsetReach,
2292 resolveMethodDebugDOThidePreds,
2293 resolveMethodDebugDOThideEdgeTaints,
2294 callerNodeIDsCopiedToCallee);
2299 // method call transfer function steps:
2300 // 1. Use current callee-reachable heap (CRH) to test callee
2301 // predicates and mark what will be coming in.
2302 // 2. Wipe CRH out of caller.
2303 // 3. Transplant marked callee parts in:
2304 // a) bring in nodes
2305 // b) bring in callee -> callee edges
2306 // c) resolve out-of-context -> callee edges
2307 // d) assign return value
2308 // 4. Collapse shadow nodes down
2309 // 5. Global sweep it.
2312 // 1. mark what callee elements have satisfied predicates
2313 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
2314 new Hashtable<HeapRegionNode, ExistPredSet>();
2316 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
2317 new Hashtable<RefEdge, ExistPredSet>();
2319 Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
2320 calleeNode2calleeStatesSatisfied =
2321 new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
2323 Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
2324 calleeEdge2calleeStatesSatisfied =
2325 new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
2327 Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
2328 calleeEdge2calleeTaintsSatisfied =
2329 new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
2331 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
2332 new Hashtable< RefEdge, Set<RefSrcNode> >();
2335 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2336 while( meItr.hasNext() ) {
2337 Map.Entry me = (Map.Entry)meItr.next();
2338 Integer id = (Integer) me.getKey();
2339 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2341 // if a callee element's predicates are satisfied then a set
2342 // of CALLER predicates is returned: they are the predicates
2343 // that the callee element moved into the caller context
2344 // should have, and it is inefficient to find this again later
2345 ExistPredSet predsIfSatis =
2346 hrnCallee.getPreds().isSatisfiedBy(this,
2347 callerNodeIDsCopiedToCallee
2350 if( predsIfSatis != null ) {
2351 calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
2353 // otherwise don't bother looking at edges to this node
2357 // since the node is coming over, find out which reach
2358 // states on it should come over, too
2359 assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
2361 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2362 while( stateItr.hasNext() ) {
2363 ReachState stateCallee = stateItr.next();
2366 stateCallee.getPreds().isSatisfiedBy(this,
2367 callerNodeIDsCopiedToCallee
2369 if( predsIfSatis != null ) {
2371 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2372 calleeNode2calleeStatesSatisfied.get(hrnCallee);
2374 if( calleeStatesSatisfied == null ) {
2375 calleeStatesSatisfied =
2376 new Hashtable<ReachState, ExistPredSet>();
2378 calleeNode2calleeStatesSatisfied.put(hrnCallee, calleeStatesSatisfied);
2381 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2385 // then look at edges to the node
2386 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2387 while( reItr.hasNext() ) {
2388 RefEdge reCallee = reItr.next();
2389 RefSrcNode rsnCallee = reCallee.getSrc();
2391 // (caller local variables to in-context heap regions)
2392 // have an (out-of-context heap region -> in-context heap region)
2393 // abstraction in the callEE, so its true we never need to
2394 // look at a (var node -> heap region) edge in callee to bring
2395 // those over for the call site transfer, except for the special
2396 // case of *RETURN var* -> heap region edges.
2397 // What about (param var->heap region)
2398 // edges in callee? They are dealt with below this loop.
2400 if( rsnCallee instanceof VariableNode ) {
2402 // looking for the return-value variable only
2403 VariableNode vnCallee = (VariableNode) rsnCallee;
2404 if( vnCallee.getTempDescriptor() != tdReturn ) {
2408 TempDescriptor returnTemp = fc.getReturnTemp();
2409 if( returnTemp == null ||
2410 !DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2415 // note that the assignment of the return value is to a
2416 // variable in the caller which is out-of-context with
2417 // respect to the callee
2418 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2419 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2420 rsnCallers.add(vnLhsCaller);
2421 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2425 // for HeapRegionNode callee sources...
2427 // first see if the source is out-of-context, and only
2428 // proceed with this edge if we find some caller-context
2430 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2431 boolean matchedOutOfContext = false;
2433 if( !hrnSrcCallee.isOutOfContext() ) {
2436 hrnSrcCallee.getPreds().isSatisfiedBy(this,
2437 callerNodeIDsCopiedToCallee
2439 if( predsIfSatis != null ) {
2440 calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
2442 // otherwise forget this edge
2447 // hrnSrcCallee is out-of-context
2449 assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
2451 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2453 // is the target node in the caller?
2454 HeapRegionNode hrnDstCaller = this.id2hrn.get(hrnCallee.getID() );
2455 if( hrnDstCaller == null ) {
2459 Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2460 while( reDstItr.hasNext() ) {
2461 // the edge and field (either possibly null) must match
2462 RefEdge reCaller = reDstItr.next();
2464 if( !reCaller.typeEquals(reCallee.getType() ) ||
2465 !reCaller.fieldEquals(reCallee.getField() )
2470 RefSrcNode rsnCaller = reCaller.getSrc();
2471 if( rsnCaller instanceof VariableNode ) {
2473 // a variable node matches an OOC region with null type
2474 if( hrnSrcCallee.getType() != null ) {
2479 // otherwise types should match
2480 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2481 if( hrnSrcCallee.getType() == null ) {
2482 if( hrnCallerSrc.getType() != null ) {
2486 if( !hrnSrcCallee.getType().equals(hrnCallerSrc.getType() ) ) {
2492 rsnCallers.add(rsnCaller);
2493 matchedOutOfContext = true;
2496 if( !rsnCallers.isEmpty() ) {
2497 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2501 if( hrnSrcCallee.isOutOfContext() &&
2502 !matchedOutOfContext ) {
2509 reCallee.getPreds().isSatisfiedBy(this,
2510 callerNodeIDsCopiedToCallee
2513 if( predsIfSatis != null ) {
2514 calleeEdgesSatisfied.put(reCallee, predsIfSatis);
2516 // since the edge is coming over, find out which reach
2517 // states on it should come over, too
2518 assert calleeEdge2calleeStatesSatisfied.get(reCallee) == null;
2520 stateItr = reCallee.getBeta().iterator();
2521 while( stateItr.hasNext() ) {
2522 ReachState stateCallee = stateItr.next();
2525 stateCallee.getPreds().isSatisfiedBy(this,
2526 callerNodeIDsCopiedToCallee
2528 if( predsIfSatis != null ) {
2530 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2531 calleeEdge2calleeStatesSatisfied.get(reCallee);
2533 if( calleeStatesSatisfied == null ) {
2534 calleeStatesSatisfied =
2535 new Hashtable<ReachState, ExistPredSet>();
2537 calleeEdge2calleeStatesSatisfied.put(reCallee, calleeStatesSatisfied);
2540 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2544 // since the edge is coming over, find out which taints
2545 // on it should come over, too
2546 assert calleeEdge2calleeTaintsSatisfied.get(reCallee) == null;
2548 Iterator<Taint> tItr = reCallee.getTaints().iterator();
2549 while( tItr.hasNext() ) {
2550 Taint tCallee = tItr.next();
2553 tCallee.getPreds().isSatisfiedBy(this,
2554 callerNodeIDsCopiedToCallee
2556 if( predsIfSatis != null ) {
2558 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2559 calleeEdge2calleeTaintsSatisfied.get(reCallee);
2561 if( calleeTaintsSatisfied == null ) {
2562 calleeTaintsSatisfied =
2563 new Hashtable<Taint, ExistPredSet>();
2565 calleeEdge2calleeTaintsSatisfied.put(reCallee, calleeTaintsSatisfied);
2568 calleeTaintsSatisfied.put(tCallee, predsIfSatis);
2575 if( writeDebugDOTs ) {
2576 writeGraph(debugGraphPrefix+"caller20BeforeWipe",
2577 resolveMethodDebugDOTwriteLabels,
2578 resolveMethodDebugDOTselectTemps,
2579 resolveMethodDebugDOTpruneGarbage,
2580 resolveMethodDebugDOThideReach,
2581 resolveMethodDebugDOThideSubsetReach,
2582 resolveMethodDebugDOThidePreds,
2583 resolveMethodDebugDOThideEdgeTaints);
2587 // 2. predicates tested, ok to wipe out caller part
2588 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2589 while( hrnItr.hasNext() ) {
2590 Integer hrnID = hrnItr.next();
2591 HeapRegionNode hrnCaller = id2hrn.get(hrnID);
2592 assert hrnCaller != null;
2594 // when clearing off nodes, also eliminate variable
2596 wipeOut(hrnCaller, true);
2599 // if we are assigning the return value to something, clobber now
2600 // as part of the wipe
2601 TempDescriptor returnTemp = fc.getReturnTemp();
2602 if( returnTemp != null &&
2603 DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2606 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2607 clearRefEdgesFrom(vnLhsCaller, null, null, true);
2613 if( writeDebugDOTs ) {
2614 writeGraph(debugGraphPrefix+"caller30BeforeAddingNodes",
2615 resolveMethodDebugDOTwriteLabels,
2616 resolveMethodDebugDOTselectTemps,
2617 resolveMethodDebugDOTpruneGarbage,
2618 resolveMethodDebugDOThideReach,
2619 resolveMethodDebugDOThideSubsetReach,
2620 resolveMethodDebugDOThidePreds,
2621 resolveMethodDebugDOThideEdgeTaints);
2627 // 3. callee elements with satisfied preds come in, note that
2628 // the mapping of elements satisfied to preds is like this:
2629 // A callee element EE has preds EEp that are satisfied by
2630 // some caller element ER. We bring EE into the caller
2631 // context as ERee with the preds of ER, namely ERp, which
2632 // in the following algorithm is the value in the mapping
2635 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2636 while( satisItr.hasNext() ) {
2637 Map.Entry me = (Map.Entry)satisItr.next();
2638 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2639 ExistPredSet preds = (ExistPredSet) me.getValue();
2641 // TODO: I think its true that the current implementation uses
2642 // the type of the OOC region and the predicates OF THE EDGE from
2643 // it to link everything up in caller context, so that's why we're
2644 // skipping this... maybe that's a sillier way to do it?
2645 if( hrnCallee.isOutOfContext() ) {
2649 AllocSite as = hrnCallee.getAllocSite();
2652 Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
2654 HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
2655 if( hrnCaller == null ) {
2657 createNewHeapRegionNode(hrnIDshadow, // id or null to generate a new one
2658 hrnCallee.isSingleObject(), // single object?
2659 hrnCallee.isNewSummary(), // summary?
2660 false, // out-of-context?
2661 hrnCallee.getType(), // type
2662 hrnCallee.getAllocSite(), // allocation site
2663 toCallerContext(hrnCallee.getInherent(),
2664 calleeNode2calleeStatesSatisfied.get(hrnCallee) ), // inherent reach
2665 null, // current reach
2666 predsEmpty, // predicates
2667 hrnCallee.getDescription() // description
2670 assert hrnCaller.isWiped();
2673 hrnCaller.setAlpha(toCallerContext(hrnCallee.getAlpha(),
2674 calleeNode2calleeStatesSatisfied.get(hrnCallee)
2678 hrnCaller.setPreds(preds);
2685 if( writeDebugDOTs ) {
2686 writeGraph(debugGraphPrefix+"caller31BeforeAddingEdges",
2687 resolveMethodDebugDOTwriteLabels,
2688 resolveMethodDebugDOTselectTemps,
2689 resolveMethodDebugDOTpruneGarbage,
2690 resolveMethodDebugDOThideReach,
2691 resolveMethodDebugDOThideSubsetReach,
2692 resolveMethodDebugDOThidePreds,
2693 resolveMethodDebugDOThideEdgeTaints);
2697 // set these up during the next procedure so after
2698 // the caller has all of its nodes and edges put
2699 // back together we can propagate the callee's
2700 // reach changes backwards into the caller graph
2701 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2703 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2704 new Hashtable<RefEdge, ChangeSet>();
2707 // 3.b) callee -> callee edges AND out-of-context -> callee
2708 // which includes return temp -> callee edges now, too
2709 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2710 while( satisItr.hasNext() ) {
2711 Map.Entry me = (Map.Entry)satisItr.next();
2712 RefEdge reCallee = (RefEdge) me.getKey();
2713 ExistPredSet preds = (ExistPredSet) me.getValue();
2715 HeapRegionNode hrnDstCallee = reCallee.getDst();
2716 AllocSite asDst = hrnDstCallee.getAllocSite();
2717 allocSites.add(asDst);
2719 Integer hrnIDDstShadow =
2720 asDst.getShadowIDfromID(hrnDstCallee.getID() );
2722 HeapRegionNode hrnDstCaller = id2hrn.get(hrnIDDstShadow);
2723 assert hrnDstCaller != null;
2726 RefSrcNode rsnCallee = reCallee.getSrc();
2728 Set<RefSrcNode> rsnCallers =
2729 new HashSet<RefSrcNode>();
2731 Set<RefSrcNode> oocCallers =
2732 calleeEdges2oocCallerSrcMatches.get(reCallee);
2734 if( rsnCallee instanceof HeapRegionNode ) {
2735 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2736 if( hrnCalleeSrc.isOutOfContext() ) {
2737 assert oocCallers != null;
2742 if( oocCallers == null ) {
2743 // there are no out-of-context matches, so it's
2744 // either a param/arg var or one in-context heap region
2745 if( rsnCallee instanceof VariableNode ) {
2746 // variable -> node in the callee should only
2747 // come into the caller if its from a param var
2748 VariableNode vnCallee = (VariableNode) rsnCallee;
2749 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2750 TempDescriptor tdArg = fc.getArgMatchingParam(fmCallee,
2752 if( tdArg == null ) {
2753 // this means the variable isn't a parameter, its local
2754 // to the callee so we ignore it in call site transfer
2755 // shouldn't this NEVER HAPPEN?
2759 rsnCallers.add(this.getVariableNodeFromTemp(tdArg) );
2762 // otherwise source is in context, one region
2764 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2766 // translate an in-context node to shadow
2767 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2768 allocSites.add(asSrc);
2770 Integer hrnIDSrcShadow =
2771 asSrc.getShadowIDfromID(hrnSrcCallee.getID() );
2773 HeapRegionNode hrnSrcCallerShadow =
2774 this.id2hrn.get(hrnIDSrcShadow);
2776 assert hrnSrcCallerShadow != null;
2778 rsnCallers.add(hrnSrcCallerShadow);
2782 // otherwise we have a set of out-of-context srcs
2783 // that should NOT be translated to shadow nodes
2784 assert !oocCallers.isEmpty();
2785 rsnCallers.addAll(oocCallers);
2788 // now make all caller edges we've identified from
2789 // this callee edge with a satisfied predicate
2790 assert !rsnCallers.isEmpty();
2791 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2792 while( rsnItr.hasNext() ) {
2793 RefSrcNode rsnCaller = rsnItr.next();
2795 RefEdge reCaller = new RefEdge(rsnCaller,
2798 reCallee.getField(),
2799 toCallerContext(reCallee.getBeta(),
2800 calleeEdge2calleeStatesSatisfied.get(reCallee) ),
2802 toCallerContext(reCallee.getTaints(),
2803 calleeEdge2calleeTaintsSatisfied.get(reCallee) )
2806 ChangeSet cs = ChangeSet.factory();
2807 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2808 while( rsItr.hasNext() ) {
2809 ReachState state = rsItr.next();
2810 ExistPredSet predsPreCallee = state.getPreds();
2812 if( state.isEmpty() ) {
2816 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2817 while( predItr.hasNext() ) {
2818 ExistPred pred = predItr.next();
2819 ReachState old = pred.ne_state;
2825 cs = Canonical.add(cs,
2826 ChangeTuple.factory(old,
2833 // we're just going to use the convenient "merge-if-exists"
2834 // edge call below, but still take a separate look if there
2835 // is an existing caller edge to build change sets properly
2836 if( !cs.isEmpty() ) {
2837 RefEdge edgeExisting = rsnCaller.getReferenceTo(hrnDstCaller,
2841 if( edgeExisting != null ) {
2842 ChangeSet csExisting = edgePlannedChanges.get(edgeExisting);
2843 if( csExisting == null ) {
2844 csExisting = ChangeSet.factory();
2846 edgePlannedChanges.put(edgeExisting,
2847 Canonical.union(csExisting,
2852 edgesForPropagation.add(reCaller);
2853 assert !edgePlannedChanges.containsKey(reCaller);
2854 edgePlannedChanges.put(reCaller, cs);
2858 // then add new caller edge or merge
2859 addEdgeOrMergeWithExisting(reCaller);
2867 if( writeDebugDOTs ) {
2868 writeGraph(debugGraphPrefix+"caller38propagateReach",
2869 resolveMethodDebugDOTwriteLabels,
2870 resolveMethodDebugDOTselectTemps,
2871 resolveMethodDebugDOTpruneGarbage,
2872 resolveMethodDebugDOThideReach,
2873 resolveMethodDebugDOThideSubsetReach,
2874 resolveMethodDebugDOThidePreds,
2875 resolveMethodDebugDOThideEdgeTaints);
2878 // propagate callee reachability changes to the rest
2879 // of the caller graph edges
2880 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2882 propagateTokensOverEdges(edgesForPropagation, // source edges
2883 edgePlannedChanges, // map src edge to change set
2884 edgesUpdated); // list of updated edges
2886 // commit beta' (beta<-betaNew)
2887 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2888 while( edgeItr.hasNext() ) {
2889 edgeItr.next().applyBetaNew();
2898 if( writeDebugDOTs ) {
2899 writeGraph(debugGraphPrefix+"caller40BeforeShadowMerge",
2900 resolveMethodDebugDOTwriteLabels,
2901 resolveMethodDebugDOTselectTemps,
2902 resolveMethodDebugDOTpruneGarbage,
2903 resolveMethodDebugDOThideReach,
2904 resolveMethodDebugDOThideSubsetReach,
2905 resolveMethodDebugDOThidePreds,
2906 resolveMethodDebugDOThideEdgeTaints);
2910 // 4) merge shadow nodes so alloc sites are back to k
2911 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2912 while( asItr.hasNext() ) {
2913 // for each allocation site do the following to merge
2914 // shadow nodes (newest from callee) with any existing
2915 // look for the newest normal and newest shadow "slot"
2916 // not being used, transfer normal to shadow. Keep
2917 // doing this until there are no more normal nodes, or
2918 // no empty shadow slots: then merge all remaining normal
2919 // nodes into the shadow summary. Finally, convert all
2920 // shadow to their normal versions.
2921 AllocSite as = asItr.next();
2925 while( ageNorm < allocationDepth &&
2926 ageShad < allocationDepth ) {
2928 // first, are there any normal nodes left?
2929 Integer idNorm = as.getIthOldest(ageNorm);
2930 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2931 if( hrnNorm == null ) {
2932 // no, this age of normal node not in the caller graph
2937 // yes, a normal node exists, is there an empty shadow
2938 // "slot" to transfer it onto?
2939 HeapRegionNode hrnShad = getIthNode(as, ageShad, true);
2940 if( !hrnShad.isWiped() ) {
2941 // no, this age of shadow node is not empty
2946 // yes, this shadow node is empty
2947 transferOnto(hrnNorm, hrnShad);
2952 // now, while there are still normal nodes but no shadow
2953 // slots, merge normal nodes into the shadow summary
2954 while( ageNorm < allocationDepth ) {
2956 // first, are there any normal nodes left?
2957 Integer idNorm = as.getIthOldest(ageNorm);
2958 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2959 if( hrnNorm == null ) {
2960 // no, this age of normal node not in the caller graph
2965 // yes, a normal node exists, so get the shadow summary
2966 HeapRegionNode summShad = getSummaryNode(as, true);
2967 mergeIntoSummary(hrnNorm, summShad);
2969 // now tokens in reachability sets need to age also
2970 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2971 while( itrAllHRNodes.hasNext() ) {
2972 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
2973 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
2975 ageTuplesFrom(as, hrnToAge);
2977 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
2978 while( itrEdges.hasNext() ) {
2979 ageTuplesFrom(as, itrEdges.next() );
2986 // if there is a normal summary, merge it into shadow summary
2987 Integer idNorm = as.getSummary();
2988 HeapRegionNode summNorm = id2hrn.get(idNorm);
2989 if( summNorm != null ) {
2990 HeapRegionNode summShad = getSummaryNode(as, true);
2991 mergeIntoSummary(summNorm, summShad);
2994 // finally, flip all existing shadow nodes onto the normal
2995 for( int i = 0; i < allocationDepth; ++i ) {
2996 Integer idShad = as.getIthOldestShadow(i);
2997 HeapRegionNode hrnShad = id2hrn.get(idShad);
2998 if( hrnShad != null ) {
3000 HeapRegionNode hrnNorm = getIthNode(as, i, false);
3001 assert hrnNorm.isWiped();
3002 transferOnto(hrnShad, hrnNorm);
3006 Integer idShad = as.getSummaryShadow();
3007 HeapRegionNode summShad = id2hrn.get(idShad);
3008 if( summShad != null ) {
3009 summNorm = getSummaryNode(as, false);
3010 transferOnto(summShad, summNorm);
3019 if( writeDebugDOTs ) {
3020 writeGraph(debugGraphPrefix+"caller45BeforeUnshadow",
3021 resolveMethodDebugDOTwriteLabels,
3022 resolveMethodDebugDOTselectTemps,
3023 resolveMethodDebugDOTpruneGarbage,
3024 resolveMethodDebugDOThideReach,
3025 resolveMethodDebugDOThideSubsetReach,
3026 resolveMethodDebugDOThidePreds,
3027 resolveMethodDebugDOThideEdgeTaints);
3031 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3032 while( itrAllHRNodes.hasNext() ) {
3033 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
3034 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3036 hrn.setAlpha(unshadow(hrn.getAlpha() ) );
3038 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
3039 while( itrEdges.hasNext() ) {
3040 RefEdge re = itrEdges.next();
3041 re.setBeta(unshadow(re.getBeta() ) );
3048 if( writeDebugDOTs ) {
3049 writeGraph(debugGraphPrefix+"caller50BeforeGlobalSweep",
3050 resolveMethodDebugDOTwriteLabels,
3051 resolveMethodDebugDOTselectTemps,
3052 resolveMethodDebugDOTpruneGarbage,
3053 resolveMethodDebugDOThideReach,
3054 resolveMethodDebugDOThideSubsetReach,
3055 resolveMethodDebugDOThidePreds,
3056 resolveMethodDebugDOThideEdgeTaints);
3061 if( !DISABLE_GLOBAL_SWEEP ) {
3066 if( writeDebugDOTs ) {
3067 writeGraph(debugGraphPrefix+"caller90AfterTransfer",
3068 resolveMethodDebugDOTwriteLabels,
3069 resolveMethodDebugDOTselectTemps,
3070 resolveMethodDebugDOTpruneGarbage,
3071 resolveMethodDebugDOThideReach,
3072 resolveMethodDebugDOThideSubsetReach,
3073 resolveMethodDebugDOThidePreds,
3074 resolveMethodDebugDOThideEdgeTaints);
3080 ////////////////////////////////////////////////////
3082 // Abstract garbage collection simply removes
3083 // heap region nodes that are not mechanically
3084 // reachable from a root set. This step is
3085 // essential for testing node and edge existence
3086 // predicates efficiently
3088 ////////////////////////////////////////////////////
3089 public void abstractGarbageCollect(Set<TempDescriptor> liveSet) {
3091 // calculate a root set, will be different for Java
3092 // version of analysis versus Bamboo version
3093 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3095 // visit every variable in graph while building root
3096 // set, and do iterating on a copy, so we can remove
3097 // dead variables while we're at this
3098 Iterator makeCopyItr = td2vn.entrySet().iterator();
3099 Set entrysCopy = new HashSet();
3100 while( makeCopyItr.hasNext() ) {
3101 entrysCopy.add(makeCopyItr.next() );
3104 Iterator eItr = entrysCopy.iterator();
3105 while( eItr.hasNext() ) {
3106 Map.Entry me = (Map.Entry)eItr.next();
3107 TempDescriptor td = (TempDescriptor) me.getKey();
3108 VariableNode vn = (VariableNode) me.getValue();
3110 if( liveSet.contains(td) ) {
3114 // dead var, remove completely from graph
3116 clearRefEdgesFrom(vn, null, null, true);
3120 // everything visited in a traversal is
3121 // considered abstractly live
3122 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3124 while( !toVisit.isEmpty() ) {
3125 RefSrcNode rsn = toVisit.iterator().next();
3126 toVisit.remove(rsn);
3129 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3130 while( hrnItr.hasNext() ) {
3131 RefEdge edge = hrnItr.next();
3132 HeapRegionNode hrn = edge.getDst();
3134 if( !visited.contains(hrn) ) {
3140 // get a copy of the set to iterate over because
3141 // we're going to monkey with the graph when we
3142 // identify a garbage node
3143 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3144 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3145 while( hrnItr.hasNext() ) {
3146 hrnAllPrior.add(hrnItr.next() );
3149 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3150 while( hrnAllItr.hasNext() ) {
3151 HeapRegionNode hrn = hrnAllItr.next();
3153 if( !visited.contains(hrn) ) {
3155 // heap region nodes are compared across ReachGraph
3156 // objects by their integer ID, so when discarding
3157 // garbage nodes we must also discard entries in
3158 // the ID -> heap region hashtable.
3159 id2hrn.remove(hrn.getID() );
3161 // RefEdge objects are two-way linked between
3162 // nodes, so when a node is identified as garbage,
3163 // actively clear references to and from it so
3164 // live nodes won't have dangling RefEdge's
3167 // if we just removed the last node from an allocation
3168 // site, it should be taken out of the ReachGraph's list
3169 AllocSite as = hrn.getAllocSite();
3170 if( !hasNodesOf(as) ) {
3171 allocSites.remove(as);
3177 protected boolean hasNodesOf(AllocSite as) {
3178 if( id2hrn.containsKey(as.getSummary() ) ) {
3182 for( int i = 0; i < allocationDepth; ++i ) {
3183 if( id2hrn.containsKey(as.getIthOldest(i) ) ) {
3191 ////////////////////////////////////////////////////
3193 // This global sweep is an optional step to prune
3194 // reachability sets that are not internally
3195 // consistent with the global graph. It should be
3196 // invoked after strong updates or method calls.
3198 ////////////////////////////////////////////////////
3199 public void globalSweep() {
3201 // boldB is part of the phase 1 sweep
3202 // it has an in-context table and an out-of-context table
3203 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3204 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3206 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3207 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3209 // visit every heap region to initialize alphaNew and betaNew,
3210 // and make a map of every hrnID to the source nodes it should
3211 // propagate forward from. In-context flagged hrnID's propagate
3212 // from only the in-context node they name, but out-of-context
3213 // ID's may propagate from several out-of-context nodes
3214 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3215 new Hashtable< Integer, Set<HeapRegionNode> >();
3217 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3218 new Hashtable< Integer, Set<HeapRegionNode> >();
3221 Iterator itrHrns = id2hrn.entrySet().iterator();
3222 while( itrHrns.hasNext() ) {
3223 Map.Entry me = (Map.Entry)itrHrns.next();
3224 Integer hrnID = (Integer) me.getKey();
3225 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3227 // assert that this node and incoming edges have clean alphaNew
3228 // and betaNew sets, respectively
3229 assert rsetEmpty.equals(hrn.getAlphaNew() );
3231 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3232 while( itrRers.hasNext() ) {
3233 RefEdge edge = itrRers.next();
3234 assert rsetEmpty.equals(edge.getBetaNew() );
3237 // make a mapping of IDs to heap regions they propagate from
3238 if( hrn.isFlagged() ) {
3239 assert !hrn.isOutOfContext();
3240 assert !icID2srcs.containsKey(hrn.getID() );
3242 // in-context flagged node IDs simply propagate from the
3244 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3246 icID2srcs.put(hrn.getID(), srcs);
3249 if( hrn.isOutOfContext() ) {
3250 assert !hrn.isFlagged();
3252 // the reachability states on an out-of-context
3253 // node are not really important (combinations of
3254 // IDs or arity)--what matters is that the states
3255 // specify which nodes this out-of-context node
3256 // stands in for. For example, if the state [17?, 19*]
3257 // appears on the ooc node, it may serve as a source
3258 // for node 17? and a source for node 19.
3259 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3260 while( stateItr.hasNext() ) {
3261 ReachState state = stateItr.next();
3263 Iterator<ReachTuple> rtItr = state.iterator();
3264 while( rtItr.hasNext() ) {
3265 ReachTuple rt = rtItr.next();
3266 assert rt.isOutOfContext();
3268 Set<HeapRegionNode> srcs = oocID2srcs.get(rt.getHrnID() );
3269 if( srcs == null ) {
3270 srcs = new HashSet<HeapRegionNode>();
3273 oocID2srcs.put(rt.getHrnID(), srcs);
3279 // calculate boldB for all hrnIDs identified by the above
3280 // node traversal, propagating from every source
3281 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3284 Set<HeapRegionNode> srcs;
3287 if( !icID2srcs.isEmpty() ) {
3288 Map.Entry me = (Map.Entry)icID2srcs.entrySet().iterator().next();
3289 hrnID = (Integer) me.getKey();
3290 srcs = (Set<HeapRegionNode>)me.getValue();
3292 icID2srcs.remove(hrnID);
3295 assert !oocID2srcs.isEmpty();
3297 Map.Entry me = (Map.Entry)oocID2srcs.entrySet().iterator().next();
3298 hrnID = (Integer) me.getKey();
3299 srcs = (Set<HeapRegionNode>)me.getValue();
3301 oocID2srcs.remove(hrnID);
3305 Hashtable<RefEdge, ReachSet> boldB_f =
3306 new Hashtable<RefEdge, ReachSet>();
3308 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3310 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3311 while( hrnItr.hasNext() ) {
3312 HeapRegionNode hrn = hrnItr.next();
3314 assert workSetEdges.isEmpty();
3316 // initial boldB_f constraints
3317 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3318 while( itrRees.hasNext() ) {
3319 RefEdge edge = itrRees.next();
3321 assert !boldB_f.containsKey(edge);
3322 boldB_f.put(edge, edge.getBeta() );
3324 assert !workSetEdges.contains(edge);
3325 workSetEdges.add(edge);
3328 // enforce the boldB_f constraint at edges until we reach a fixed point
3329 while( !workSetEdges.isEmpty() ) {
3330 RefEdge edge = workSetEdges.iterator().next();
3331 workSetEdges.remove(edge);
3333 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3334 while( itrPrime.hasNext() ) {
3335 RefEdge edgePrime = itrPrime.next();
3337 ReachSet prevResult = boldB_f.get(edgePrime);
3338 ReachSet intersection = Canonical.intersection(boldB_f.get(edge),
3342 if( prevResult == null ||
3343 Canonical.unionORpreds(prevResult,
3344 intersection).size()
3348 if( prevResult == null ) {
3349 boldB_f.put(edgePrime,
3350 Canonical.unionORpreds(edgePrime.getBeta(),
3355 boldB_f.put(edgePrime,
3356 Canonical.unionORpreds(prevResult,
3361 workSetEdges.add(edgePrime);
3368 boldBic.put(hrnID, boldB_f);
3370 boldBooc.put(hrnID, boldB_f);
3375 // use boldB to prune hrnIDs from alpha states that are impossible
3376 // and propagate the differences backwards across edges
3377 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3379 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3380 new Hashtable<RefEdge, ChangeSet>();
3383 itrHrns = id2hrn.entrySet().iterator();
3384 while( itrHrns.hasNext() ) {
3385 Map.Entry me = (Map.Entry)itrHrns.next();
3386 Integer hrnID = (Integer) me.getKey();
3387 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3389 // out-of-context nodes don't participate in the
3390 // global sweep, they serve as sources for the pass
3392 if( hrn.isOutOfContext() ) {
3396 // the inherent states of a region are the exception
3397 // to removal as the global sweep prunes
3398 ReachTuple rtException = ReachTuple.factory(hrnID,
3399 !hrn.isSingleObject(),
3400 ReachTuple.ARITY_ONE,
3401 false // out-of-context
3404 ChangeSet cts = ChangeSet.factory();
3406 // mark hrnIDs for removal
3407 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3408 while( stateItr.hasNext() ) {
3409 ReachState stateOld = stateItr.next();
3411 ReachState markedHrnIDs = ReachState.factory();
3413 Iterator<ReachTuple> rtItr = stateOld.iterator();
3414 while( rtItr.hasNext() ) {
3415 ReachTuple rtOld = rtItr.next();
3417 // never remove the inherent hrnID from a flagged region
3418 // because it is trivially satisfied
3419 if( hrn.isFlagged() ) {
3420 if( rtOld == rtException ) {
3425 // does boldB allow this hrnID?
3426 boolean foundState = false;
3427 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3428 while( incidentEdgeItr.hasNext() ) {
3429 RefEdge incidentEdge = incidentEdgeItr.next();
3431 Hashtable<RefEdge, ReachSet> B;
3432 if( rtOld.isOutOfContext() ) {
3433 B = boldBooc.get(rtOld.getHrnID() );
3436 if( !id2hrn.containsKey(rtOld.getHrnID() ) ) {
3437 // let symbols not in the graph get pruned
3441 B = boldBic.get(rtOld.getHrnID() );
3445 ReachSet boldB_rtOld_incident = B.get(incidentEdge);
3446 if( boldB_rtOld_incident != null &&
3447 boldB_rtOld_incident.containsIgnorePreds(stateOld) != null
3455 markedHrnIDs = Canonical.addUpArity(markedHrnIDs, rtOld);
3459 // if there is nothing marked, just move on
3460 if( markedHrnIDs.isEmpty() ) {
3461 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3468 // remove all marked hrnIDs and establish a change set that should
3469 // propagate backwards over edges from this node
3470 ReachState statePruned = ReachState.factory();
3471 rtItr = stateOld.iterator();
3472 while( rtItr.hasNext() ) {
3473 ReachTuple rtOld = rtItr.next();
3475 if( !markedHrnIDs.containsTuple(rtOld) ) {
3476 statePruned = Canonical.addUpArity(statePruned, rtOld);
3479 assert !stateOld.equals(statePruned);
3481 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3485 ChangeTuple ct = ChangeTuple.factory(stateOld,
3488 cts = Canonical.add(cts, ct);
3491 // throw change tuple set on all incident edges
3492 if( !cts.isEmpty() ) {
3493 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3494 while( incidentEdgeItr.hasNext() ) {
3495 RefEdge incidentEdge = incidentEdgeItr.next();
3497 edgesForPropagation.add(incidentEdge);
3499 if( edgePlannedChanges.get(incidentEdge) == null ) {
3500 edgePlannedChanges.put(incidentEdge, cts);
3502 edgePlannedChanges.put(
3504 Canonical.union(edgePlannedChanges.get(incidentEdge),
3513 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3515 propagateTokensOverEdges(edgesForPropagation,
3519 // at the end of the 1st phase reference edges have
3520 // beta, betaNew that correspond to beta and betaR
3522 // commit beta<-betaNew, so beta=betaR and betaNew
3523 // will represent the beta' calculation in 2nd phase
3525 // commit alpha<-alphaNew because it won't change
3526 HashSet<RefEdge> res = new HashSet<RefEdge>();
3528 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3529 while( nodeItr.hasNext() ) {
3530 HeapRegionNode hrn = nodeItr.next();
3532 // as mentioned above, out-of-context nodes only serve
3533 // as sources of reach states for the sweep, not part
3535 if( hrn.isOutOfContext() ) {
3536 assert hrn.getAlphaNew().equals(rsetEmpty);
3538 hrn.applyAlphaNew();
3541 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3542 while( itrRes.hasNext() ) {
3543 res.add(itrRes.next() );
3549 Iterator<RefEdge> edgeItr = res.iterator();
3550 while( edgeItr.hasNext() ) {
3551 RefEdge edge = edgeItr.next();
3552 HeapRegionNode hrn = edge.getDst();
3554 // commit results of last phase
3555 if( edgesUpdated.contains(edge) ) {
3556 edge.applyBetaNew();
3559 // compute intial condition of 2nd phase
3560 edge.setBetaNew(Canonical.intersection(edge.getBeta(),
3566 // every edge in the graph is the initial workset
3567 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3568 while( !edgeWorkSet.isEmpty() ) {
3569 RefEdge edgePrime = edgeWorkSet.iterator().next();
3570 edgeWorkSet.remove(edgePrime);
3572 RefSrcNode rsn = edgePrime.getSrc();
3573 if( !(rsn instanceof HeapRegionNode) ) {
3576 HeapRegionNode hrn = (HeapRegionNode) rsn;
3578 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3579 while( itrEdge.hasNext() ) {
3580 RefEdge edge = itrEdge.next();
3582 ReachSet prevResult = edge.getBetaNew();
3583 assert prevResult != null;
3585 ReachSet intersection =
3586 Canonical.intersection(edge.getBeta(),
3587 edgePrime.getBetaNew()
3590 if( Canonical.unionORpreds(prevResult,
3597 Canonical.unionORpreds(prevResult,
3601 edgeWorkSet.add(edge);
3606 // commit beta' (beta<-betaNew)
3607 edgeItr = res.iterator();
3608 while( edgeItr.hasNext() ) {
3609 edgeItr.next().applyBetaNew();
3614 // a useful assertion for debugging:
3615 // every in-context tuple on any edge or
3616 // any node should name a node that is
3617 // part of the graph
3618 public boolean inContextTuplesInGraph() {
3620 Iterator hrnItr = id2hrn.entrySet().iterator();
3621 while( hrnItr.hasNext() ) {
3622 Map.Entry me = (Map.Entry)hrnItr.next();
3623 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3626 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3627 while( stateItr.hasNext() ) {
3628 ReachState state = stateItr.next();
3630 Iterator<ReachTuple> rtItr = state.iterator();
3631 while( rtItr.hasNext() ) {
3632 ReachTuple rt = rtItr.next();
3634 if( !rt.isOutOfContext() ) {
3635 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3636 System.out.println(rt.getHrnID()+" is missing");
3644 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3645 while( edgeItr.hasNext() ) {
3646 RefEdge edge = edgeItr.next();
3648 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3649 while( stateItr.hasNext() ) {
3650 ReachState state = stateItr.next();
3652 Iterator<ReachTuple> rtItr = state.iterator();
3653 while( rtItr.hasNext() ) {
3654 ReachTuple rt = rtItr.next();
3656 if( !rt.isOutOfContext() ) {
3657 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3658 System.out.println(rt.getHrnID()+" is missing");
3671 // another useful assertion for debugging
3672 public boolean noEmptyReachSetsInGraph() {
3674 Iterator hrnItr = id2hrn.entrySet().iterator();
3675 while( hrnItr.hasNext() ) {
3676 Map.Entry me = (Map.Entry)hrnItr.next();
3677 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3679 if( !hrn.isOutOfContext() &&
3681 hrn.getAlpha().isEmpty()
3683 System.out.println("!!! "+hrn+" has an empty ReachSet !!!");
3687 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3688 while( edgeItr.hasNext() ) {
3689 RefEdge edge = edgeItr.next();
3691 if( edge.getBeta().isEmpty() ) {
3692 System.out.println("!!! "+edge+" has an empty ReachSet !!!");
3702 public boolean everyReachStateWTrue() {
3704 Iterator hrnItr = id2hrn.entrySet().iterator();
3705 while( hrnItr.hasNext() ) {
3706 Map.Entry me = (Map.Entry)hrnItr.next();
3707 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3710 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3711 while( stateItr.hasNext() ) {
3712 ReachState state = stateItr.next();
3714 if( !state.getPreds().equals(predsTrue) ) {
3720 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3721 while( edgeItr.hasNext() ) {
3722 RefEdge edge = edgeItr.next();
3724 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3725 while( stateItr.hasNext() ) {
3726 ReachState state = stateItr.next();
3728 if( !state.getPreds().equals(predsTrue) ) {
3741 ////////////////////////////////////////////////////
3742 // in merge() and equals() methods the suffix A
3743 // represents the passed in graph and the suffix
3744 // B refers to the graph in this object
3745 // Merging means to take the incoming graph A and
3746 // merge it into B, so after the operation graph B
3747 // is the final result.
3748 ////////////////////////////////////////////////////
3749 protected void merge(ReachGraph rg) {
3757 mergeAllocSites(rg);
3758 mergeInaccessibleVars(rg);
3761 protected void mergeNodes(ReachGraph rg) {
3763 // start with heap region nodes
3764 Set sA = rg.id2hrn.entrySet();
3765 Iterator iA = sA.iterator();
3766 while( iA.hasNext() ) {
3767 Map.Entry meA = (Map.Entry)iA.next();
3768 Integer idA = (Integer) meA.getKey();
3769 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3771 // if this graph doesn't have a node the
3772 // incoming graph has, allocate it
3773 if( !id2hrn.containsKey(idA) ) {
3774 HeapRegionNode hrnB = hrnA.copy();
3775 id2hrn.put(idA, hrnB);
3778 // otherwise this is a node present in both graphs
3779 // so make the new reachability set a union of the
3780 // nodes' reachability sets
3781 HeapRegionNode hrnB = id2hrn.get(idA);
3782 hrnB.setAlpha(Canonical.unionORpreds(hrnB.getAlpha(),
3787 hrnB.setPreds(Canonical.join(hrnB.getPreds(),
3794 if( !hrnA.equals(hrnB) ) {
3795 rg.writeGraph("graphA");
3796 this.writeGraph("graphB");
3797 throw new Error("flagged not matching");
3805 // now add any variable nodes that are in graph B but
3807 sA = rg.td2vn.entrySet();
3809 while( iA.hasNext() ) {
3810 Map.Entry meA = (Map.Entry)iA.next();
3811 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3812 VariableNode lnA = (VariableNode) meA.getValue();
3814 // if the variable doesn't exist in B, allocate and add it
3815 VariableNode lnB = getVariableNodeFromTemp(tdA);
3819 protected void mergeRefEdges(ReachGraph rg) {
3821 // between heap regions
3822 Set sA = rg.id2hrn.entrySet();
3823 Iterator iA = sA.iterator();
3824 while( iA.hasNext() ) {
3825 Map.Entry meA = (Map.Entry)iA.next();
3826 Integer idA = (Integer) meA.getKey();
3827 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3829 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3830 while( heapRegionsItrA.hasNext() ) {
3831 RefEdge edgeA = heapRegionsItrA.next();
3832 HeapRegionNode hrnChildA = edgeA.getDst();
3833 Integer idChildA = hrnChildA.getID();
3835 // at this point we know an edge in graph A exists
3836 // idA -> idChildA, does this exist in B?
3837 assert id2hrn.containsKey(idA);
3838 HeapRegionNode hrnB = id2hrn.get(idA);
3839 RefEdge edgeToMerge = null;
3841 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3842 while( heapRegionsItrB.hasNext() &&
3843 edgeToMerge == null ) {
3845 RefEdge edgeB = heapRegionsItrB.next();
3846 HeapRegionNode hrnChildB = edgeB.getDst();
3847 Integer idChildB = hrnChildB.getID();
3849 // don't use the RefEdge.equals() here because
3850 // we're talking about existence between graphs,
3851 // not intragraph equal
3852 if( idChildB.equals(idChildA) &&
3853 edgeB.typeAndFieldEquals(edgeA) ) {
3855 edgeToMerge = edgeB;
3859 // if the edge from A was not found in B,
3861 if( edgeToMerge == null ) {
3862 assert id2hrn.containsKey(idChildA);
3863 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3864 edgeToMerge = edgeA.copy();
3865 edgeToMerge.setSrc(hrnB);
3866 edgeToMerge.setDst(hrnChildB);
3867 addRefEdge(hrnB, hrnChildB, edgeToMerge);
3869 // otherwise, the edge already existed in both graphs
3870 // so merge their reachability sets
3872 // just replace this beta set with the union
3873 assert edgeToMerge != null;
3874 edgeToMerge.setBeta(
3875 Canonical.unionORpreds(edgeToMerge.getBeta(),
3879 edgeToMerge.setPreds(
3880 Canonical.join(edgeToMerge.getPreds(),
3884 edgeToMerge.setTaints(
3885 Canonical.union(edgeToMerge.getTaints(),
3893 // and then again from variable nodes
3894 sA = rg.td2vn.entrySet();
3896 while( iA.hasNext() ) {
3897 Map.Entry meA = (Map.Entry)iA.next();
3898 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3899 VariableNode vnA = (VariableNode) meA.getValue();
3901 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3902 while( heapRegionsItrA.hasNext() ) {
3903 RefEdge edgeA = heapRegionsItrA.next();
3904 HeapRegionNode hrnChildA = edgeA.getDst();
3905 Integer idChildA = hrnChildA.getID();
3907 // at this point we know an edge in graph A exists
3908 // tdA -> idChildA, does this exist in B?
3909 assert td2vn.containsKey(tdA);
3910 VariableNode vnB = td2vn.get(tdA);
3911 RefEdge edgeToMerge = null;
3913 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3914 while( heapRegionsItrB.hasNext() &&
3915 edgeToMerge == null ) {
3917 RefEdge edgeB = heapRegionsItrB.next();
3918 HeapRegionNode hrnChildB = edgeB.getDst();
3919 Integer idChildB = hrnChildB.getID();
3921 // don't use the RefEdge.equals() here because
3922 // we're talking about existence between graphs
3923 if( idChildB.equals(idChildA) &&
3924 edgeB.typeAndFieldEquals(edgeA) ) {
3926 edgeToMerge = edgeB;
3930 // if the edge from A was not found in B,
3932 if( edgeToMerge == null ) {
3933 assert id2hrn.containsKey(idChildA);
3934 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3935 edgeToMerge = edgeA.copy();
3936 edgeToMerge.setSrc(vnB);
3937 edgeToMerge.setDst(hrnChildB);
3938 addRefEdge(vnB, hrnChildB, edgeToMerge);
3940 // otherwise, the edge already existed in both graphs
3941 // so merge their reachability sets
3943 // just replace this beta set with the union
3944 edgeToMerge.setBeta(Canonical.unionORpreds(edgeToMerge.getBeta(),
3948 edgeToMerge.setPreds(Canonical.join(edgeToMerge.getPreds(),
3952 edgeToMerge.setTaints(
3953 Canonical.union(edgeToMerge.getTaints(),
3962 protected void mergeAllocSites(ReachGraph rg) {
3963 allocSites.addAll(rg.allocSites);
3966 protected void mergeInaccessibleVars(ReachGraph rg) {
3967 inaccessibleVars.addAll(rg.inaccessibleVars);
3972 static boolean dbgEquals = false;
3975 // it is necessary in the equals() member functions
3976 // to "check both ways" when comparing the data
3977 // structures of two graphs. For instance, if all
3978 // edges between heap region nodes in graph A are
3979 // present and equal in graph B it is not sufficient
3980 // to say the graphs are equal. Consider that there
3981 // may be edges in graph B that are not in graph A.
3982 // the only way to know that all edges in both graphs
3983 // are equally present is to iterate over both data
3984 // structures and compare against the other graph.
3985 public boolean equals(ReachGraph rg) {
3989 System.out.println("rg is null");
3994 if( !areHeapRegionNodesEqual(rg) ) {
3996 System.out.println("hrn not equal");
4001 if( !areVariableNodesEqual(rg) ) {
4003 System.out.println("vars not equal");
4008 if( !areRefEdgesEqual(rg) ) {
4010 System.out.println("edges not equal");
4015 if( !inaccessibleVars.equals(rg.inaccessibleVars) ) {
4019 // if everything is equal up to this point,
4020 // assert that allocSites is also equal--
4021 // this data is redundant but kept for efficiency
4022 assert allocSites.equals(rg.allocSites);
4028 protected boolean areHeapRegionNodesEqual(ReachGraph rg) {
4030 if( !areallHRNinAalsoinBandequal(this, rg) ) {
4034 if( !areallHRNinAalsoinBandequal(rg, this) ) {
4041 static protected boolean areallHRNinAalsoinBandequal(ReachGraph rgA,
4043 Set sA = rgA.id2hrn.entrySet();
4044 Iterator iA = sA.iterator();
4045 while( iA.hasNext() ) {
4046 Map.Entry meA = (Map.Entry)iA.next();
4047 Integer idA = (Integer) meA.getKey();
4048 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4050 if( !rgB.id2hrn.containsKey(idA) ) {
4054 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4055 if( !hrnA.equalsIncludingAlphaAndPreds(hrnB) ) {
4063 protected boolean areVariableNodesEqual(ReachGraph rg) {
4065 if( !areallVNinAalsoinBandequal(this, rg) ) {
4069 if( !areallVNinAalsoinBandequal(rg, this) ) {
4076 static protected boolean areallVNinAalsoinBandequal(ReachGraph rgA,
4078 Set sA = rgA.td2vn.entrySet();
4079 Iterator iA = sA.iterator();
4080 while( iA.hasNext() ) {
4081 Map.Entry meA = (Map.Entry)iA.next();
4082 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4084 if( !rgB.td2vn.containsKey(tdA) ) {
4093 protected boolean areRefEdgesEqual(ReachGraph rg) {
4094 if( !areallREinAandBequal(this, rg) ) {
4098 if( !areallREinAandBequal(rg, this) ) {
4105 static protected boolean areallREinAandBequal(ReachGraph rgA,
4108 // check all the heap region->heap region edges
4109 Set sA = rgA.id2hrn.entrySet();
4110 Iterator iA = sA.iterator();
4111 while( iA.hasNext() ) {
4112 Map.Entry meA = (Map.Entry)iA.next();
4113 Integer idA = (Integer) meA.getKey();
4114 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4116 // we should have already checked that the same
4117 // heap regions exist in both graphs
4118 assert rgB.id2hrn.containsKey(idA);
4120 if( !areallREfromAequaltoB(rgA, hrnA, rgB) ) {
4124 // then check every edge in B for presence in A, starting
4125 // from the same parent HeapRegionNode
4126 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4128 if( !areallREfromAequaltoB(rgB, hrnB, rgA) ) {
4133 // then check all the variable->heap region edges
4134 sA = rgA.td2vn.entrySet();
4136 while( iA.hasNext() ) {
4137 Map.Entry meA = (Map.Entry)iA.next();
4138 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4139 VariableNode vnA = (VariableNode) meA.getValue();
4141 // we should have already checked that the same
4142 // label nodes exist in both graphs
4143 assert rgB.td2vn.containsKey(tdA);
4145 if( !areallREfromAequaltoB(rgA, vnA, rgB) ) {
4149 // then check every edge in B for presence in A, starting
4150 // from the same parent VariableNode
4151 VariableNode vnB = rgB.td2vn.get(tdA);
4153 if( !areallREfromAequaltoB(rgB, vnB, rgA) ) {
4162 static protected boolean areallREfromAequaltoB(ReachGraph rgA,
4166 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4167 while( itrA.hasNext() ) {
4168 RefEdge edgeA = itrA.next();
4169 HeapRegionNode hrnChildA = edgeA.getDst();
4170 Integer idChildA = hrnChildA.getID();
4172 assert rgB.id2hrn.containsKey(idChildA);
4174 // at this point we know an edge in graph A exists
4175 // rnA -> idChildA, does this exact edge exist in B?
4176 boolean edgeFound = false;
4178 RefSrcNode rnB = null;
4179 if( rnA instanceof HeapRegionNode ) {
4180 HeapRegionNode hrnA = (HeapRegionNode) rnA;
4181 rnB = rgB.id2hrn.get(hrnA.getID() );
4183 VariableNode vnA = (VariableNode) rnA;
4184 rnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4187 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4188 while( itrB.hasNext() ) {
4189 RefEdge edgeB = itrB.next();
4190 HeapRegionNode hrnChildB = edgeB.getDst();
4191 Integer idChildB = hrnChildB.getID();
4193 if( idChildA.equals(idChildB) &&
4194 edgeA.typeAndFieldEquals(edgeB) ) {
4196 // there is an edge in the right place with the right field,
4197 // but do they have the same attributes?
4198 if( edgeA.getBeta().equals(edgeB.getBeta() ) &&
4199 edgeA.equalsPreds(edgeB)
4215 // can be used to assert monotonicity
4216 static public boolean isNoSmallerThan(ReachGraph rgA,
4219 //System.out.println( "*** Asking if A is no smaller than B ***" );
4222 Iterator iA = rgA.id2hrn.entrySet().iterator();
4223 while( iA.hasNext() ) {
4224 Map.Entry meA = (Map.Entry)iA.next();
4225 Integer idA = (Integer) meA.getKey();
4226 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4228 if( !rgB.id2hrn.containsKey(idA) ) {
4229 System.out.println(" regions smaller");
4233 //HeapRegionNode hrnB = rgB.id2hrn.get( idA );
4234 /* NOT EQUALS, NO SMALLER THAN!
4235 if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
4236 System.out.println( " regions smaller" );
4242 // this works just fine, no smaller than
4243 if( !areallVNinAalsoinBandequal(rgA, rgB) ) {
4244 System.out.println(" vars smaller:");
4245 System.out.println(" A:"+rgA.td2vn.keySet() );
4246 System.out.println(" B:"+rgB.td2vn.keySet() );
4251 iA = rgA.id2hrn.entrySet().iterator();
4252 while( iA.hasNext() ) {
4253 Map.Entry meA = (Map.Entry)iA.next();
4254 Integer idA = (Integer) meA.getKey();
4255 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4257 Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4258 while( reItr.hasNext() ) {
4259 RefEdge edgeA = reItr.next();
4260 RefSrcNode rsnA = edgeA.getSrc();
4262 // we already checked that nodes were present
4263 HeapRegionNode hrnB = rgB.id2hrn.get(hrnA.getID() );
4264 assert hrnB != null;
4267 if( rsnA instanceof VariableNode ) {
4268 VariableNode vnA = (VariableNode) rsnA;
4269 rsnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4272 HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4273 rsnB = rgB.id2hrn.get(hrnSrcA.getID() );
4275 assert rsnB != null;
4277 RefEdge edgeB = rsnB.getReferenceTo(hrnB,
4281 if( edgeB == null ) {
4282 System.out.println(" edges smaller:");
4286 // REMEMBER, IS NO SMALLER THAN
4288 System.out.println( " edges smaller" );
4304 // this analysis no longer has the "match anything"
4305 // type which was represented by null
4306 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4307 TypeDescriptor td2) {
4311 if( td1.isNull() ) {
4314 if( td2.isNull() ) {
4317 return typeUtil.mostSpecific(td1, td2);
4320 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4322 TypeDescriptor td3) {
4324 return mostSpecificType(td1,
4325 mostSpecificType(td2, td3)
4329 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4332 TypeDescriptor td4) {
4334 return mostSpecificType(mostSpecificType(td1, td2),
4335 mostSpecificType(td3, td4)
4339 protected boolean isSuperiorType(TypeDescriptor possibleSuper,
4340 TypeDescriptor possibleChild) {
4341 assert possibleSuper != null;
4342 assert possibleChild != null;
4344 if( possibleSuper.isNull() ||
4345 possibleChild.isNull() ) {
4349 return typeUtil.isSuperorType(possibleSuper, possibleChild);
4353 protected boolean hasMatchingField(HeapRegionNode src,
4356 TypeDescriptor tdSrc = src.getType();
4357 assert tdSrc != null;
4359 if( tdSrc.isArray() ) {
4360 TypeDescriptor td = edge.getType();
4363 TypeDescriptor tdSrcDeref = tdSrc.dereference();
4364 assert tdSrcDeref != null;
4366 if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
4370 return edge.getField().equals(DisjointAnalysis.arrayElementFieldName);
4373 // if it's not a class, it doesn't have any fields to match
4374 if( !tdSrc.isClass() ) {
4378 ClassDescriptor cd = tdSrc.getClassDesc();
4379 while( cd != null ) {
4380 Iterator fieldItr = cd.getFields();
4382 while( fieldItr.hasNext() ) {
4383 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4385 if( fd.getType().equals(edge.getType() ) &&
4386 fd.getSymbol().equals(edge.getField() ) ) {
4391 cd = cd.getSuperDesc();
4394 // otherwise it is a class with fields
4395 // but we didn't find a match
4399 protected boolean hasMatchingType(RefEdge edge,
4400 HeapRegionNode dst) {
4402 // if the region has no type, matches everything
4403 TypeDescriptor tdDst = dst.getType();
4404 assert tdDst != null;
4406 // if the type is not a class or an array, don't
4407 // match because primitives are copied, no aliases
4408 ClassDescriptor cdDst = tdDst.getClassDesc();
4409 if( cdDst == null && !tdDst.isArray() ) {
4413 // if the edge type is null, it matches everything
4414 TypeDescriptor tdEdge = edge.getType();
4415 assert tdEdge != null;
4417 return typeUtil.isSuperorType(tdEdge, tdDst);
4422 // the default signature for quick-and-dirty debugging
4423 public void writeGraph(String graphName) {
4424 writeGraph(graphName,
4425 true, // write labels
4426 true, // label select
4427 true, // prune garbage
4428 false, // hide reachability
4429 true, // hide subset reachability
4430 true, // hide predicates
4431 false, // hide edge taints
4432 null // in-context boundary
4436 public void writeGraph(String graphName,
4437 boolean writeLabels,
4438 boolean labelSelect,
4439 boolean pruneGarbage,
4440 boolean hideReachability,
4441 boolean hideSubsetReachability,
4442 boolean hidePredicates,
4443 boolean hideEdgeTaints
4445 writeGraph(graphName,
4450 hideSubsetReachability,
4456 public void writeGraph(String graphName,
4457 boolean writeLabels,
4458 boolean labelSelect,
4459 boolean pruneGarbage,
4460 boolean hideReachability,
4461 boolean hideSubsetReachability,
4462 boolean hidePredicates,
4463 boolean hideEdgeTaints,
4464 Set<Integer> callerNodeIDsCopiedToCallee
4467 // remove all non-word characters from the graph name so
4468 // the filename and identifier in dot don't cause errors
4469 // jjenista - also replace underscore '_' to prevent some
4470 // really, really long names from IHMS debugging
4471 graphName = graphName.replaceAll("[\\W_]", "");
4474 new BufferedWriter(new FileWriter(graphName+".dot") );
4476 bw.write("digraph "+graphName+" {\n");
4479 // this is an optional step to form the callee-reachable
4480 // "cut-out" into a DOT cluster for visualization
4481 if( callerNodeIDsCopiedToCallee != null ) {
4483 bw.write(" subgraph cluster0 {\n");
4484 bw.write(" color=blue;\n");
4486 Iterator i = id2hrn.entrySet().iterator();
4487 while( i.hasNext() ) {
4488 Map.Entry me = (Map.Entry)i.next();
4489 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4491 if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4494 hrn.toStringDOT(hideReachability,
4495 hideSubsetReachability,
4505 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4507 // then visit every heap region node
4508 Iterator i = id2hrn.entrySet().iterator();
4509 while( i.hasNext() ) {
4510 Map.Entry me = (Map.Entry)i.next();
4511 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4513 // only visit nodes worth writing out--for instance
4514 // not every node at an allocation is referenced
4515 // (think of it as garbage-collected), etc.
4516 if( !pruneGarbage ||
4517 hrn.isOutOfContext() ||
4518 (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4521 if( !visited.contains(hrn) ) {
4522 traverseHeapRegionNodes(hrn,
4527 hideSubsetReachability,
4530 callerNodeIDsCopiedToCallee);
4535 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4538 // then visit every label node, useful for debugging
4540 i = td2vn.entrySet().iterator();
4541 while( i.hasNext() ) {
4542 Map.Entry me = (Map.Entry)i.next();
4543 VariableNode vn = (VariableNode) me.getValue();
4546 String labelStr = vn.getTempDescriptorString();
4547 if( labelStr.startsWith("___temp") ||
4548 labelStr.startsWith("___dst") ||
4549 labelStr.startsWith("___srctmp") ||
4550 labelStr.startsWith("___neverused")
4556 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4557 while( heapRegionsItr.hasNext() ) {
4558 RefEdge edge = heapRegionsItr.next();
4559 HeapRegionNode hrn = edge.getDst();
4561 if( !visited.contains(hrn) ) {
4562 traverseHeapRegionNodes(hrn,
4567 hideSubsetReachability,
4570 callerNodeIDsCopiedToCallee);
4573 bw.write(" "+vn.toString()+
4574 " -> "+hrn.toString()+
4575 edge.toStringDOT(hideReachability,
4576 hideSubsetReachability,
4588 } catch( IOException e ) {
4589 throw new Error("Error writing out DOT graph "+graphName);
4594 traverseHeapRegionNodes(HeapRegionNode hrn,
4597 Set<HeapRegionNode> visited,
4598 boolean hideReachability,
4599 boolean hideSubsetReachability,
4600 boolean hidePredicates,
4601 boolean hideEdgeTaints,
4602 Set<Integer> callerNodeIDsCopiedToCallee
4603 ) throws java.io.IOException {
4605 if( visited.contains(hrn) ) {
4610 // if we're drawing the callee-view subgraph, only
4611 // write out the node info if it hasn't already been
4613 if( callerNodeIDsCopiedToCallee == null ||
4614 !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4618 hrn.toStringDOT(hideReachability,
4619 hideSubsetReachability,
4624 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4625 while( childRegionsItr.hasNext() ) {
4626 RefEdge edge = childRegionsItr.next();
4627 HeapRegionNode hrnChild = edge.getDst();
4629 if( callerNodeIDsCopiedToCallee != null &&
4630 (edge.getSrc() instanceof HeapRegionNode) ) {
4631 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4632 if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4633 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4635 bw.write(" "+hrn.toString()+
4636 " -> "+hrnChild.toString()+
4637 edge.toStringDOT(hideReachability,
4638 hideSubsetReachability,
4643 } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4644 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4646 bw.write(" "+hrn.toString()+
4647 " -> "+hrnChild.toString()+
4648 edge.toStringDOT(hideReachability,
4649 hideSubsetReachability,
4652 ",color=blue,style=dashed")+
4655 bw.write(" "+hrn.toString()+
4656 " -> "+hrnChild.toString()+
4657 edge.toStringDOT(hideReachability,
4658 hideSubsetReachability,
4665 bw.write(" "+hrn.toString()+
4666 " -> "+hrnChild.toString()+
4667 edge.toStringDOT(hideReachability,
4668 hideSubsetReachability,
4675 traverseHeapRegionNodes(hrnChild,
4680 hideSubsetReachability,
4683 callerNodeIDsCopiedToCallee);
4692 // return the set of heap regions from the given allocation
4693 // site, if any, that exist in this graph
4694 protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4696 Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4698 Integer idSum = as.getSummary();
4699 if( id2hrn.containsKey(idSum) ) {
4700 out.add(id2hrn.get(idSum) );
4703 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4704 Integer idI = as.getIthOldest(i);
4705 if( id2hrn.containsKey(idI) ) {
4706 out.add(id2hrn.get(idI) );
4713 // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4714 // from the given allocation site, if any, from regions for that
4715 // site that exist in this graph
4716 protected Set<ReachTuple> getAnyExisting(AllocSite as,
4717 boolean includeARITY_ZEROORMORE,
4718 boolean includeARITY_ONE) {
4720 Set<ReachTuple> out = new HashSet<ReachTuple>();
4722 Integer idSum = as.getSummary();
4723 if( id2hrn.containsKey(idSum) ) {
4725 HeapRegionNode hrn = id2hrn.get(idSum);
4726 assert !hrn.isOutOfContext();
4728 if( !includeARITY_ZEROORMORE ) {
4729 out.add(ReachTuple.factory(hrn.getID(),
4730 true, // multi-obj region
4731 ReachTuple.ARITY_ZEROORMORE,
4736 if( includeARITY_ONE ) {
4737 out.add(ReachTuple.factory(hrn.getID(),
4738 true, // multi-object region
4739 ReachTuple.ARITY_ONE,
4745 if( !includeARITY_ONE ) {
4746 // no need to do the single-object regions that
4747 // only have an ARITY ONE possible
4751 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4753 Integer idI = as.getIthOldest(i);
4754 if( id2hrn.containsKey(idI) ) {
4756 HeapRegionNode hrn = id2hrn.get(idI);
4757 assert !hrn.isOutOfContext();
4759 out.add(ReachTuple.factory(hrn.getID(),
4760 false, // multi-object region
4761 ReachTuple.ARITY_ONE,
4771 // if an object allocated at the target site may be
4772 // reachable from both an object from root1 and an
4773 // object allocated at root2, return TRUE
4774 public boolean mayBothReachTarget(AllocSite asRoot1,
4776 AllocSite asTarget) {
4778 // consider all heap regions of the target and look
4779 // for a reach state that indicates regions of root1
4780 // and root2 might be able to reach same object
4781 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4783 // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4784 Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4785 Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4787 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4788 while( hrnItr.hasNext() ) {
4789 HeapRegionNode hrn = hrnItr.next();
4791 Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4792 while( rtItr1.hasNext() ) {
4793 ReachTuple rt1 = rtItr1.next();
4795 Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4796 while( rtItr2.hasNext() ) {
4797 ReachTuple rt2 = rtItr2.next();
4799 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4809 // similar to the method above, return TRUE if ever
4810 // more than one object from the root allocation site
4811 // may reach an object from the target site
4812 public boolean mayManyReachTarget(AllocSite asRoot,
4813 AllocSite asTarget) {
4815 // consider all heap regions of the target and look
4816 // for a reach state that multiple objects of root
4817 // might be able to reach the same object
4818 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4820 // get relevant reach tuples
4821 Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true, false);
4822 Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4824 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4825 while( hrnItr.hasNext() ) {
4826 HeapRegionNode hrn = hrnItr.next();
4828 // if any ZERORMORE tuples are here, TRUE
4829 Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4830 while( rtItr.hasNext() ) {
4831 ReachTuple rtZOM = rtItr.next();
4833 if( hrn.getAlpha().containsTuple(rtZOM) ) {
4838 // otherwise, look for any pair of ONE tuples
4839 Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4840 while( rtItr1.hasNext() ) {
4841 ReachTuple rt1 = rtItr1.next();
4843 Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4844 while( rtItr2.hasNext() ) {
4845 ReachTuple rt2 = rtItr2.next();
4851 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4865 public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4867 Set<HeapRegionNode> exhibitProofState =
4868 new HashSet<HeapRegionNode>();
4870 Iterator hrnItr = id2hrn.entrySet().iterator();
4871 while( hrnItr.hasNext() ) {
4872 Map.Entry me = (Map.Entry)hrnItr.next();
4873 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4875 ReachSet intersection =
4876 Canonical.intersection(proofOfSharing,
4879 if( !intersection.isEmpty() ) {
4880 assert !hrn.isOutOfContext();
4881 exhibitProofState.add(hrn);
4885 return exhibitProofState;
4889 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4890 HeapRegionNode hrn2) {
4891 assert hrn1 != null;
4892 assert hrn2 != null;
4894 assert !hrn1.isOutOfContext();
4895 assert !hrn2.isOutOfContext();
4897 assert belongsToThis(hrn1);
4898 assert belongsToThis(hrn2);
4900 assert !hrn1.getID().equals(hrn2.getID() );
4903 // then get the various tokens for these heap regions
4905 ReachTuple.factory(hrn1.getID(),
4906 !hrn1.isSingleObject(), // multi?
4907 ReachTuple.ARITY_ONE,
4910 ReachTuple h1star = null;
4911 if( !hrn1.isSingleObject() ) {
4913 ReachTuple.factory(hrn1.getID(),
4914 !hrn1.isSingleObject(),
4915 ReachTuple.ARITY_ZEROORMORE,
4920 ReachTuple.factory(hrn2.getID(),
4921 !hrn2.isSingleObject(),
4922 ReachTuple.ARITY_ONE,
4925 ReachTuple h2star = null;
4926 if( !hrn2.isSingleObject() ) {
4928 ReachTuple.factory(hrn2.getID(),
4929 !hrn2.isSingleObject(),
4930 ReachTuple.ARITY_ZEROORMORE,
4934 // then get the merged beta of all out-going edges from these heap
4937 ReachSet beta1 = ReachSet.factory();
4938 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4939 while (itrEdge.hasNext()) {
4940 RefEdge edge = itrEdge.next();
4941 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4944 ReachSet beta2 = ReachSet.factory();
4945 itrEdge = hrn2.iteratorToReferencees();
4946 while (itrEdge.hasNext()) {
4947 RefEdge edge = itrEdge.next();
4948 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4951 ReachSet proofOfSharing = ReachSet.factory();
4954 Canonical.unionORpreds(proofOfSharing,
4955 beta1.getStatesWithBoth(h1, h2)
4958 Canonical.unionORpreds(proofOfSharing,
4959 beta2.getStatesWithBoth(h1, h2)
4962 if( !hrn1.isSingleObject() ) {
4964 Canonical.unionORpreds(proofOfSharing,
4965 beta1.getStatesWithBoth(h1star, h2)
4968 Canonical.unionORpreds(proofOfSharing,
4969 beta2.getStatesWithBoth(h1star, h2)
4973 if( !hrn2.isSingleObject() ) {
4975 Canonical.unionORpreds(proofOfSharing,
4976 beta1.getStatesWithBoth(h1, h2star)
4979 Canonical.unionORpreds(proofOfSharing,
4980 beta2.getStatesWithBoth(h1, h2star)
4984 if( !hrn1.isSingleObject() &&
4985 !hrn2.isSingleObject()
4988 Canonical.unionORpreds(proofOfSharing,
4989 beta1.getStatesWithBoth(h1star, h2star)
4992 Canonical.unionORpreds(proofOfSharing,
4993 beta2.getStatesWithBoth(h1star, h2star)
4997 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4998 if( !proofOfSharing.isEmpty() ) {
4999 common = findCommonReachableNodes(proofOfSharing);
5000 if( !DISABLE_STRONG_UPDATES &&
5001 !DISABLE_GLOBAL_SWEEP
5003 assert !common.isEmpty();
5010 // this version of the above method checks whether there is sharing
5011 // among the objects in a summary node
5012 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
5014 assert hrn.isNewSummary();
5015 assert !hrn.isOutOfContext();
5016 assert belongsToThis(hrn);
5019 ReachTuple.factory(hrn.getID(),
5021 ReachTuple.ARITY_ZEROORMORE,
5024 // then get the merged beta of all out-going edges from
5027 ReachSet beta = ReachSet.factory();
5028 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
5029 while (itrEdge.hasNext()) {
5030 RefEdge edge = itrEdge.next();
5031 beta = Canonical.unionORpreds(beta, edge.getBeta());
5034 ReachSet proofOfSharing = ReachSet.factory();
5037 Canonical.unionORpreds(proofOfSharing,
5038 beta.getStatesWithBoth(hstar, hstar)
5041 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5042 if( !proofOfSharing.isEmpty() ) {
5043 common = findCommonReachableNodes(proofOfSharing);
5044 if( !DISABLE_STRONG_UPDATES &&
5045 !DISABLE_GLOBAL_SWEEP
5047 assert !common.isEmpty();
5055 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5056 Integer paramIndex1,
5057 Integer paramIndex2) {
5059 // get parameter's heap regions
5060 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5061 assert this.hasVariable(paramTemp1);
5062 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5065 if( !(paramVar1.getNumReferencees() == 1) ) {
5066 System.out.println("\n fm="+fm+"\n param="+paramTemp1);
5067 writeGraph("whatup");
5071 assert paramVar1.getNumReferencees() == 1;
5072 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5073 HeapRegionNode hrnParam1 = paramEdge1.getDst();
5075 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5076 assert this.hasVariable(paramTemp2);
5077 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5079 if( !(paramVar2.getNumReferencees() == 1) ) {
5080 System.out.println("\n fm="+fm+"\n param="+paramTemp2);
5081 writeGraph("whatup");
5084 assert paramVar2.getNumReferencees() == 1;
5085 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5086 HeapRegionNode hrnParam2 = paramEdge2.getDst();
5088 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5089 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5094 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5098 // get parameter's heap regions
5099 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5100 assert this.hasVariable(paramTemp);
5101 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5102 assert paramVar.getNumReferencees() == 1;
5103 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5104 HeapRegionNode hrnParam = paramEdge.getDst();
5107 HeapRegionNode hrnSummary=null;
5108 if(id2hrn.containsKey(as.getSummary())) {
5109 // if summary node doesn't exist, ignore this case
5110 hrnSummary = id2hrn.get(as.getSummary());
5111 assert hrnSummary != null;
5114 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5115 if(hrnSummary!=null) {
5116 common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5119 // check for other nodes
5120 for (int i = 0; i < as.getAllocationDepth(); ++i) {
5122 assert id2hrn.containsKey(as.getIthOldest(i));
5123 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5124 assert hrnIthOldest != null;
5126 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5133 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5136 // get summary node 1's alpha
5137 Integer idSum1 = as1.getSummary();
5138 HeapRegionNode hrnSum1=null;
5139 if(id2hrn.containsKey(idSum1)) {
5140 hrnSum1 = id2hrn.get(idSum1);
5143 // get summary node 2's alpha
5144 Integer idSum2 = as2.getSummary();
5145 HeapRegionNode hrnSum2=null;
5146 if(id2hrn.containsKey(idSum2)) {
5147 hrnSum2 = id2hrn.get(idSum2);
5150 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5151 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5152 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5156 // ask if objects from this summary share among each other
5157 common.addAll(mayReachSharedObjects(hrnSum1));
5160 // check sum2 against alloc1 nodes
5162 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5163 Integer idI1 = as1.getIthOldest(i);
5164 assert id2hrn.containsKey(idI1);
5165 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5166 assert hrnI1 != null;
5167 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5170 // also ask if objects from this summary share among each other
5171 common.addAll(mayReachSharedObjects(hrnSum2));
5174 // check sum1 against alloc2 nodes
5175 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5176 Integer idI2 = as2.getIthOldest(i);
5177 assert id2hrn.containsKey(idI2);
5178 HeapRegionNode hrnI2 = id2hrn.get(idI2);
5179 assert hrnI2 != null;
5182 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5185 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5186 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5187 Integer idI1 = as1.getIthOldest(j);
5189 // if these are the same site, don't look for the same token, no
5191 // different tokens of the same site could alias together though
5192 if (idI1.equals(idI2)) {
5196 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5198 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5205 public void makeInaccessible(Set<TempDescriptor> vars) {
5206 inaccessibleVars.addAll(vars);
5209 public void makeInaccessible(TempDescriptor td) {
5210 inaccessibleVars.add(td);
5213 public void makeAccessible(TempDescriptor td) {
5214 inaccessibleVars.remove(td);
5217 public boolean isAccessible(TempDescriptor td) {
5218 return !inaccessibleVars.contains(td);
5221 public Set<TempDescriptor> getInaccessibleVars() {
5222 return inaccessibleVars;
5228 public Set<Alloc> canPointTo( TempDescriptor x ) {
5230 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5231 // if we don't care to track it, return null which means
5232 // "a client of this result shouldn't care either"
5233 return HeapAnalysis.DONTCARE_PTR;
5236 Set<Alloc> out = new HashSet<Alloc>();
5238 VariableNode vn = getVariableNodeNoMutation( x );
5240 // the empty set means "can't point to anything"
5244 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5245 while( edgeItr.hasNext() ) {
5246 HeapRegionNode hrn = edgeItr.next().getDst();
5247 out.add( hrn.getAllocSite() );
5255 public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5257 TypeDescriptor fieldType ) {
5259 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5260 // if we don't care to track it, return null which means
5261 // "a client of this result shouldn't care either"
5262 return HeapAnalysis.DONTCARE_DREF;
5265 Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5267 VariableNode vn = getVariableNodeNoMutation( x );
5269 // the empty table means "x can't point to anything"
5273 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5274 while( edgeItr.hasNext() ) {
5275 HeapRegionNode hrn = edgeItr.next().getDst();
5276 Alloc key = hrn.getAllocSite();
5278 if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5279 // if we don't care to track it, put no entry which means
5280 // "a client of this result shouldn't care either"
5281 out.put( key, HeapAnalysis.DONTCARE_PTR );
5285 Set<Alloc> moreValues = new HashSet<Alloc>();
5286 Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5287 while( edgeItr2.hasNext() ) {
5288 RefEdge edge = edgeItr2.next();
5290 if( field.equals( edge.getField() ) ) {
5291 moreValues.add( edge.getDst().getAllocSite() );
5295 if( out.containsKey( key ) ) {
5296 out.get( key ).addAll( moreValues );
5298 out.put( key, moreValues );
5308 public TempDescriptor findVariableByName( String name ) {
5310 for( TempDescriptor td: td2vn.keySet() ) {
5311 if( td.getSymbol().contains( name ) ) {