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);
261 protected boolean clearRefEdgesFrom(RefSrcNode referencer,
265 return clearRefEdgesFrom( referencer, type, field, removeAll, null, null );
268 // return whether at least one edge was removed
269 protected boolean clearRefEdgesFrom(RefSrcNode referencer,
273 Set<EdgeKey> edgeKeysRemoved,
274 FieldDescriptor fd) {
275 assert referencer != null;
277 boolean atLeastOneEdgeRemoved = false;
279 // get a copy of the set to iterate over, otherwise
280 // we will be trying to take apart the set as we
281 // are iterating over it, which won't work
282 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
283 while( i.hasNext() ) {
284 RefEdge edge = i.next();
287 (edge.typeEquals(type) && edge.fieldEquals(field))
290 HeapRegionNode referencee = edge.getDst();
292 if( edgeKeysRemoved != null ) {
294 assert referencer instanceof HeapRegionNode;
295 edgeKeysRemoved.add( new EdgeKey( ((HeapRegionNode)referencer).getID(),
301 removeRefEdge(referencer,
306 atLeastOneEdgeRemoved = true;
310 return atLeastOneEdgeRemoved;
313 protected void clearRefEdgesTo(HeapRegionNode referencee,
317 assert referencee != null;
319 // get a copy of the set to iterate over, otherwise
320 // we will be trying to take apart the set as we
321 // are iterating over it, which won't work
322 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
323 while( i.hasNext() ) {
324 RefEdge edge = i.next();
327 (edge.typeEquals(type) && edge.fieldEquals(field))
330 RefSrcNode referencer = edge.getSrc();
332 removeRefEdge(referencer,
340 protected void clearNonVarRefEdgesTo(HeapRegionNode referencee) {
341 assert referencee != null;
343 // get a copy of the set to iterate over, otherwise
344 // we will be trying to take apart the set as we
345 // are iterating over it, which won't work
346 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
347 while( i.hasNext() ) {
348 RefEdge edge = i.next();
349 RefSrcNode referencer = edge.getSrc();
350 if( !(referencer instanceof VariableNode) ) {
351 removeRefEdge(referencer,
359 // this is a common operation in many transfer functions: we want
360 // to add an edge, but if there is already such an edge we should
361 // merge the properties of the existing and the new edges
362 protected void addEdgeOrMergeWithExisting(RefEdge edgeNew) {
364 RefSrcNode src = edgeNew.getSrc();
365 assert belongsToThis(src);
367 HeapRegionNode dst = edgeNew.getDst();
368 assert belongsToThis(dst);
370 // look to see if an edge with same field exists
371 // and merge with it, otherwise just add the edge
372 RefEdge edgeExisting = src.getReferenceTo(dst,
377 if( edgeExisting != null ) {
378 edgeExisting.setBeta(
379 Canonical.unionORpreds(edgeExisting.getBeta(),
383 edgeExisting.setPreds(
384 Canonical.join(edgeExisting.getPreds(),
388 edgeExisting.setTaints(
389 Canonical.unionORpreds(edgeExisting.getTaints(),
395 addRefEdge(src, dst, edgeNew);
401 ////////////////////////////////////////////////////
403 // Assignment Operation Methods
405 // These methods are high-level operations for
406 // modeling program assignment statements using
407 // the low-level reference create/remove methods
410 ////////////////////////////////////////////////////
412 public void assignTempEqualToStringLiteral(TempDescriptor x,
413 AllocSite asStringLiteral,
414 AllocSite asStringLiteralBytes,
415 FieldDescriptor fdStringBytesField) {
416 // model this to get points-to information right for
417 // pointers to string literals, even though it doesn't affect
418 // reachability paths in the heap
419 assignTempEqualToNewAlloc( x,
422 assignTempEqualToNewAlloc( tdStrLiteralBytes,
423 asStringLiteralBytes );
425 assignTempXFieldFEqualToTempY( x,
434 public void assignTempXEqualToTempY(TempDescriptor x,
436 assignTempXEqualToCastedTempY(x, y, null);
440 public void assignTempXEqualToCastedTempY(TempDescriptor x,
442 TypeDescriptor tdCast) {
444 VariableNode lnX = getVariableNodeFromTemp(x);
445 VariableNode lnY = getVariableNodeFromTemp(y);
447 clearRefEdgesFrom(lnX, null, null, true);
449 // note it is possible that the types of temps in the
450 // flat node to analyze will reveal that some typed
451 // edges in the reachability graph are impossible
452 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
454 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
455 while( itrYhrn.hasNext() ) {
456 RefEdge edgeY = itrYhrn.next();
457 HeapRegionNode referencee = edgeY.getDst();
458 RefEdge edgeNew = edgeY.copy();
460 if( !isSuperiorType(x.getType(), edgeY.getType() ) ) {
461 impossibleEdges.add(edgeY);
467 if( tdCast == null ) {
468 edgeNew.setType(mostSpecificType(y.getType(),
474 edgeNew.setType(mostSpecificType(y.getType(),
476 referencee.getType(),
482 edgeNew.setField(null);
484 addRefEdge(lnX, referencee, edgeNew);
487 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
488 while( itrImp.hasNext() ) {
489 RefEdge edgeImp = itrImp.next();
490 removeRefEdge(edgeImp);
495 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
498 FlatNode currentProgramPoint,
499 Set<EdgeKey> edgeKeysForLoad
502 VariableNode lnX = getVariableNodeFromTemp(x);
503 VariableNode lnY = getVariableNodeFromTemp(y);
505 clearRefEdgesFrom(lnX, null, null, true);
507 // note it is possible that the types of temps in the
508 // flat node to analyze will reveal that some typed
509 // edges in the reachability graph are impossible
510 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
512 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
513 while( itrYhrn.hasNext() ) {
514 RefEdge edgeY = itrYhrn.next();
515 HeapRegionNode hrnY = edgeY.getDst();
516 ReachSet betaY = edgeY.getBeta();
518 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
520 while( itrHrnFhrn.hasNext() ) {
521 RefEdge edgeHrn = itrHrnFhrn.next();
522 HeapRegionNode hrnHrn = edgeHrn.getDst();
523 ReachSet betaHrn = edgeHrn.getBeta();
525 // prune edges that are not a matching field
526 if( edgeHrn.getType() != null &&
527 !edgeHrn.getField().equals(f.getSymbol() )
532 // check for impossible edges
533 if( !isSuperiorType(x.getType(), edgeHrn.getType() ) ) {
534 impossibleEdges.add(edgeHrn);
538 // for definite reach analysis only
539 if( edgeKeysForLoad != null ) {
541 edgeKeysForLoad.add( new EdgeKey( hrnY.getID(),
548 TypeDescriptor tdNewEdge =
549 mostSpecificType(edgeHrn.getType(),
553 TaintSet taints = Canonical.unionORpreds(edgeHrn.getTaints(),
557 // the DFJ way to generate taints changes for field statements
558 taints = Canonical.changeWhereDefined(taints,
559 currentProgramPoint);
562 RefEdge edgeNew = new RefEdge(lnX,
566 Canonical.intersection(betaY, betaHrn),
571 addEdgeOrMergeWithExisting(edgeNew);
575 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
576 while( itrImp.hasNext() ) {
577 RefEdge edgeImp = itrImp.next();
578 removeRefEdge(edgeImp);
581 // anytime you might remove edges between heap regions
582 // you must global sweep to clean up broken reachability
583 if( !impossibleEdges.isEmpty() ) {
584 if( !DISABLE_GLOBAL_SWEEP ) {
592 // return whether a strong update was actually effected
593 public boolean assignTempXFieldFEqualToTempY(TempDescriptor x,
596 FlatNode currentProgramPoint,
597 Set<EdgeKey> edgeKeysRemoved,
598 Set<EdgeKey> edgeKeysAdded
601 VariableNode lnX = getVariableNodeFromTemp(x);
602 VariableNode lnY = getVariableNodeFromTemp(y);
604 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
605 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
607 // note it is possible that the types of temps in the
608 // flat node to analyze will reveal that some typed
609 // edges in the reachability graph are impossible
610 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
612 // first look for possible strong updates and remove those edges
613 boolean strongUpdateCond = false;
614 boolean edgeRemovedByStrongUpdate = false;
616 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
617 while( itrXhrn.hasNext() ) {
618 RefEdge edgeX = itrXhrn.next();
619 HeapRegionNode hrnX = edgeX.getDst();
621 // we can do a strong update here if one of two cases holds
623 f != DisjointAnalysis.getArrayField(f.getType() ) &&
624 ( (hrnX.getNumReferencers() == 1) || // case 1
625 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
628 if( !DISABLE_STRONG_UPDATES ) {
629 strongUpdateCond = true;
631 boolean atLeastOne = clearRefEdgesFrom(hrnX,
638 edgeRemovedByStrongUpdate = true;
644 // then do all token propagation
645 itrXhrn = lnX.iteratorToReferencees();
646 while( itrXhrn.hasNext() ) {
647 RefEdge edgeX = itrXhrn.next();
648 HeapRegionNode hrnX = edgeX.getDst();
649 ReachSet betaX = edgeX.getBeta();
650 ReachSet R = Canonical.intersection(hrnX.getAlpha(),
654 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
655 while( itrYhrn.hasNext() ) {
656 RefEdge edgeY = itrYhrn.next();
657 HeapRegionNode hrnY = edgeY.getDst();
658 ReachSet O = edgeY.getBeta();
660 // check for impossible edges
661 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
662 impossibleEdges.add(edgeY);
666 // propagate tokens over nodes starting from hrnSrc, and it will
667 // take care of propagating back up edges from any touched nodes
668 ChangeSet Cy = Canonical.unionUpArityToChangeSet(O, R);
669 propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
671 // then propagate back just up the edges from hrn
672 ChangeSet Cx = Canonical.unionUpArityToChangeSet(R, O);
673 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
675 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
676 new Hashtable<RefEdge, ChangeSet>();
678 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
679 while( referItr.hasNext() ) {
680 RefEdge edgeUpstream = referItr.next();
681 todoEdges.add(edgeUpstream);
682 edgePlannedChanges.put(edgeUpstream, Cx);
685 propagateTokensOverEdges(todoEdges,
692 // apply the updates to reachability
693 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
694 while( nodeItr.hasNext() ) {
695 nodeItr.next().applyAlphaNew();
698 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
699 while( edgeItr.hasNext() ) {
700 edgeItr.next().applyBetaNew();
704 // then go back through and add the new edges
705 itrXhrn = lnX.iteratorToReferencees();
706 while( itrXhrn.hasNext() ) {
707 RefEdge edgeX = itrXhrn.next();
708 HeapRegionNode hrnX = edgeX.getDst();
710 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
711 while( itrYhrn.hasNext() ) {
712 RefEdge edgeY = itrYhrn.next();
713 HeapRegionNode hrnY = edgeY.getDst();
715 // skip impossible edges here, we already marked them
716 // when computing reachability propagations above
717 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
721 // for definite reach analysis only
722 if( edgeKeysAdded != null ) {
724 edgeKeysAdded.add( new EdgeKey( hrnX.getID(),
730 // prepare the new reference edge hrnX.f -> hrnY
731 TypeDescriptor tdNewEdge =
732 mostSpecificType(y.getType(),
737 TaintSet taints = edgeY.getTaints();
740 // the DFJ way to generate taints changes for field statements
741 taints = Canonical.changeWhereDefined(taints,
742 currentProgramPoint);
750 Canonical.changePredsTo(
751 Canonical.pruneBy(edgeY.getBeta(),
760 addEdgeOrMergeWithExisting(edgeNew);
764 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
765 while( itrImp.hasNext() ) {
766 RefEdge edgeImp = itrImp.next();
767 removeRefEdge(edgeImp);
770 // if there was a strong update, make sure to improve
771 // reachability with a global sweep
772 if( edgeRemovedByStrongUpdate || !impossibleEdges.isEmpty() ) {
773 if( !DISABLE_GLOBAL_SWEEP ) {
778 return edgeRemovedByStrongUpdate;
782 public void assignReturnEqualToTemp(TempDescriptor x) {
784 VariableNode lnR = getVariableNodeFromTemp(tdReturn);
785 VariableNode lnX = getVariableNodeFromTemp(x);
787 clearRefEdgesFrom(lnR, null, null, true);
789 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
790 while( itrXhrn.hasNext() ) {
791 RefEdge edgeX = itrXhrn.next();
792 HeapRegionNode referencee = edgeX.getDst();
793 RefEdge edgeNew = edgeX.copy();
795 edgeNew.setTaints(Canonical.changePredsTo(edgeNew.getTaints(),
800 addRefEdge(lnR, referencee, edgeNew);
805 public void assignTempEqualToNewAlloc(TempDescriptor x,
812 // after the age operation the newest (or zero-ith oldest)
813 // node associated with the allocation site should have
814 // no references to it as if it were a newly allocated
816 Integer idNewest = as.getIthOldest(0);
817 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
818 assert hrnNewest != null;
820 VariableNode lnX = getVariableNodeFromTemp(x);
821 clearRefEdgesFrom(lnX, null, null, true);
823 // make a new reference to allocated node
824 TypeDescriptor type = as.getType();
827 new RefEdge(lnX, // source
831 hrnNewest.getAlpha(), // beta
832 predsTrue, // predicates
833 TaintSet.factory() // taints
836 addRefEdge(lnX, hrnNewest, edgeNew);
840 // use the allocation site (unique to entire analysis) to
841 // locate the heap region nodes in this reachability graph
842 // that should be aged. The process models the allocation
843 // of new objects and collects all the oldest allocations
844 // in a summary node to allow for a finite analysis
846 // There is an additional property of this method. After
847 // running it on a particular reachability graph (many graphs
848 // may have heap regions related to the same allocation site)
849 // the heap region node objects in this reachability graph will be
850 // allocated. Therefore, after aging a graph for an allocation
851 // site, attempts to retrieve the heap region nodes using the
852 // integer id's contained in the allocation site should always
853 // return non-null heap regions.
854 public void age(AllocSite as) {
856 // keep track of allocation sites that are represented
857 // in this graph for efficiency with other operations
860 // if there is a k-th oldest node, it merges into
862 Integer idK = as.getOldest();
863 if( id2hrn.containsKey(idK) ) {
864 HeapRegionNode hrnK = id2hrn.get(idK);
866 // retrieve the summary node, or make it
868 HeapRegionNode hrnSummary = getSummaryNode(as, false);
870 mergeIntoSummary(hrnK, hrnSummary);
873 // move down the line of heap region nodes
874 // clobbering the ith and transferring all references
875 // to and from i-1 to node i.
876 for( int i = allocationDepth - 1; i > 0; --i ) {
878 // only do the transfer if the i-1 node exists
879 Integer idImin1th = as.getIthOldest(i - 1);
880 if( id2hrn.containsKey(idImin1th) ) {
881 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
882 if( hrnImin1.isWiped() ) {
883 // there is no info on this node, just skip
887 // either retrieve or make target of transfer
888 HeapRegionNode hrnI = getIthNode(as, i, false);
890 transferOnto(hrnImin1, hrnI);
895 // as stated above, the newest node should have had its
896 // references moved over to the second oldest, so we wipe newest
897 // in preparation for being the new object to assign something to
898 HeapRegionNode hrn0 = getIthNode(as, 0, false);
901 // now tokens in reachability sets need to "age" also
902 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
903 while( itrAllHRNodes.hasNext() ) {
904 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
905 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
907 ageTuplesFrom(as, hrnToAge);
909 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
910 while( itrEdges.hasNext() ) {
911 ageTuplesFrom(as, itrEdges.next() );
916 // after tokens have been aged, reset newest node's reachability
917 // and a brand new node has a "true" predicate
918 hrn0.setAlpha( Canonical.changePredsTo( hrn0.getInherent(), predsTrue ) );
919 hrn0.setPreds( predsTrue);
923 // either retrieve or create the needed heap region node
924 protected HeapRegionNode getSummaryNode(AllocSite as,
929 idSummary = as.getSummaryShadow();
931 idSummary = as.getSummary();
934 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
936 if( hrnSummary == null ) {
938 String strDesc = as.toStringForDOT()+"\\nsummary";
941 createNewHeapRegionNode(idSummary, // id or null to generate a new one
942 false, // single object?
944 false, // out-of-context?
945 as.getType(), // type
946 as, // allocation site
947 null, // inherent reach
948 null, // current reach
949 predsEmpty, // predicates
950 strDesc // description
957 // either retrieve or create the needed heap region node
958 protected HeapRegionNode getIthNode(AllocSite as,
964 idIth = as.getIthOldestShadow(i);
966 idIth = as.getIthOldest(i);
969 HeapRegionNode hrnIth = id2hrn.get(idIth);
971 if( hrnIth == null ) {
973 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
975 hrnIth = createNewHeapRegionNode(idIth, // id or null to generate a new one
976 true, // single object?
978 false, // out-of-context?
979 as.getType(), // type
980 as, // allocation site
981 null, // inherent reach
982 null, // current reach
983 predsEmpty, // predicates
984 strDesc // description
992 protected void mergeIntoSummary(HeapRegionNode hrn,
993 HeapRegionNode hrnSummary) {
994 assert hrnSummary.isNewSummary();
996 // assert that these nodes belong to THIS graph
997 assert belongsToThis(hrn);
998 assert belongsToThis(hrnSummary);
1000 assert hrn != hrnSummary;
1002 // transfer references _from_ hrn over to hrnSummary
1003 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
1004 while( itrReferencee.hasNext() ) {
1005 RefEdge edge = itrReferencee.next();
1006 RefEdge edgeMerged = edge.copy();
1007 edgeMerged.setSrc(hrnSummary);
1009 HeapRegionNode hrnReferencee = edge.getDst();
1010 RefEdge edgeSummary =
1011 hrnSummary.getReferenceTo(hrnReferencee,
1016 if( edgeSummary == null ) {
1017 // the merge is trivial, nothing to be done
1018 addRefEdge(hrnSummary, hrnReferencee, edgeMerged);
1021 // otherwise an edge from the referencer to hrnSummary exists already
1022 // and the edge referencer->hrn should be merged with it
1023 edgeSummary.setBeta(
1024 Canonical.unionORpreds(edgeMerged.getBeta(),
1025 edgeSummary.getBeta()
1028 edgeSummary.setPreds(
1029 Canonical.join(edgeMerged.getPreds(),
1030 edgeSummary.getPreds()
1036 // next transfer references _to_ hrn over to hrnSummary
1037 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
1038 while( itrReferencer.hasNext() ) {
1039 RefEdge edge = itrReferencer.next();
1040 RefEdge edgeMerged = edge.copy();
1041 edgeMerged.setDst(hrnSummary);
1043 RefSrcNode onReferencer = edge.getSrc();
1044 RefEdge edgeSummary =
1045 onReferencer.getReferenceTo(hrnSummary,
1050 if( edgeSummary == null ) {
1051 // the merge is trivial, nothing to be done
1052 addRefEdge(onReferencer, hrnSummary, edgeMerged);
1055 // otherwise an edge from the referencer to alpha_S exists already
1056 // and the edge referencer->alpha_K should be merged with it
1057 edgeSummary.setBeta(
1058 Canonical.unionORpreds(edgeMerged.getBeta(),
1059 edgeSummary.getBeta()
1062 edgeSummary.setPreds(
1063 Canonical.join(edgeMerged.getPreds(),
1064 edgeSummary.getPreds()
1070 // then merge hrn reachability into hrnSummary
1071 hrnSummary.setAlpha(
1072 Canonical.unionORpreds(hrnSummary.getAlpha(),
1077 hrnSummary.setPreds(
1078 Canonical.join(hrnSummary.getPreds(),
1083 // and afterward, this node is gone
1088 protected void transferOnto(HeapRegionNode hrnA,
1089 HeapRegionNode hrnB) {
1091 assert belongsToThis(hrnA);
1092 assert belongsToThis(hrnB);
1093 assert hrnA != hrnB;
1095 // clear references in and out of node b?
1096 assert hrnB.isWiped();
1098 // copy each: (edge in and out of A) to B
1099 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
1100 while( itrReferencee.hasNext() ) {
1101 RefEdge edge = itrReferencee.next();
1102 HeapRegionNode hrnReferencee = edge.getDst();
1103 RefEdge edgeNew = edge.copy();
1104 edgeNew.setSrc(hrnB);
1105 edgeNew.setDst(hrnReferencee);
1107 addRefEdge(hrnB, hrnReferencee, edgeNew);
1110 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
1111 while( itrReferencer.hasNext() ) {
1112 RefEdge edge = itrReferencer.next();
1113 RefSrcNode rsnReferencer = edge.getSrc();
1114 RefEdge edgeNew = edge.copy();
1115 edgeNew.setSrc(rsnReferencer);
1116 edgeNew.setDst(hrnB);
1118 addRefEdge(rsnReferencer, hrnB, edgeNew);
1121 // replace hrnB reachability and preds with hrnA's
1122 hrnB.setAlpha(hrnA.getAlpha() );
1123 hrnB.setPreds(hrnA.getPreds() );
1125 // after transfer, wipe out source
1126 wipeOut(hrnA, true);
1130 // the purpose of this method is to conceptually "wipe out"
1131 // a heap region from the graph--purposefully not called REMOVE
1132 // because the node is still hanging around in the graph, just
1133 // not mechanically connected or have any reach or predicate
1134 // information on it anymore--lots of ops can use this
1135 protected void wipeOut(HeapRegionNode hrn,
1136 boolean wipeVariableReferences) {
1138 assert belongsToThis(hrn);
1140 clearRefEdgesFrom(hrn, null, null, true);
1142 if( wipeVariableReferences ) {
1143 clearRefEdgesTo(hrn, null, null, true);
1145 clearNonVarRefEdgesTo(hrn);
1148 hrn.setAlpha(rsetEmpty);
1149 hrn.setPreds(predsEmpty);
1153 protected void ageTuplesFrom(AllocSite as, RefEdge edge) {
1155 Canonical.ageTuplesFrom(edge.getBeta(),
1161 protected void ageTuplesFrom(AllocSite as, HeapRegionNode hrn) {
1163 Canonical.ageTuplesFrom(hrn.getAlpha(),
1171 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1173 HashSet<HeapRegionNode> nodesWithNewAlpha,
1174 HashSet<RefEdge> edgesWithNewBeta) {
1176 HashSet<HeapRegionNode> todoNodes
1177 = new HashSet<HeapRegionNode>();
1178 todoNodes.add(nPrime);
1180 HashSet<RefEdge> todoEdges
1181 = new HashSet<RefEdge>();
1183 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1184 = new Hashtable<HeapRegionNode, ChangeSet>();
1185 nodePlannedChanges.put(nPrime, c0);
1187 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1188 = new Hashtable<RefEdge, ChangeSet>();
1190 // first propagate change sets everywhere they can go
1191 while( !todoNodes.isEmpty() ) {
1192 HeapRegionNode n = todoNodes.iterator().next();
1193 ChangeSet C = nodePlannedChanges.get(n);
1195 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1196 while( referItr.hasNext() ) {
1197 RefEdge edge = referItr.next();
1198 todoEdges.add(edge);
1200 if( !edgePlannedChanges.containsKey(edge) ) {
1201 edgePlannedChanges.put(edge,
1206 edgePlannedChanges.put(edge,
1207 Canonical.union(edgePlannedChanges.get(edge),
1213 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1214 while( refeeItr.hasNext() ) {
1215 RefEdge edgeF = refeeItr.next();
1216 HeapRegionNode m = edgeF.getDst();
1218 ChangeSet changesToPass = ChangeSet.factory();
1220 Iterator<ChangeTuple> itrCprime = C.iterator();
1221 while( itrCprime.hasNext() ) {
1222 ChangeTuple c = itrCprime.next();
1223 if( edgeF.getBeta().containsIgnorePreds(c.getStateToMatch() )
1226 changesToPass = Canonical.add(changesToPass, c);
1230 if( !changesToPass.isEmpty() ) {
1231 if( !nodePlannedChanges.containsKey(m) ) {
1232 nodePlannedChanges.put(m, ChangeSet.factory() );
1235 ChangeSet currentChanges = nodePlannedChanges.get(m);
1237 if( !changesToPass.isSubset(currentChanges) ) {
1239 nodePlannedChanges.put(m,
1240 Canonical.union(currentChanges,
1249 todoNodes.remove(n);
1252 // then apply all of the changes for each node at once
1253 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1254 while( itrMap.hasNext() ) {
1255 Map.Entry me = (Map.Entry)itrMap.next();
1256 HeapRegionNode n = (HeapRegionNode) me.getKey();
1257 ChangeSet C = (ChangeSet) me.getValue();
1259 // this propagation step is with respect to one change,
1260 // so we capture the full change from the old alpha:
1261 ReachSet localDelta = Canonical.applyChangeSet(n.getAlpha(),
1265 // but this propagation may be only one of many concurrent
1266 // possible changes, so keep a running union with the node's
1267 // partially updated new alpha set
1268 n.setAlphaNew(Canonical.unionORpreds(n.getAlphaNew(),
1273 nodesWithNewAlpha.add(n);
1276 propagateTokensOverEdges(todoEdges,
1283 protected void propagateTokensOverEdges(HashSet <RefEdge> todoEdges,
1284 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1285 HashSet <RefEdge> edgesWithNewBeta) {
1287 // first propagate all change tuples everywhere they can go
1288 while( !todoEdges.isEmpty() ) {
1289 RefEdge edgeE = todoEdges.iterator().next();
1290 todoEdges.remove(edgeE);
1292 if( !edgePlannedChanges.containsKey(edgeE) ) {
1293 edgePlannedChanges.put(edgeE,
1298 ChangeSet C = edgePlannedChanges.get(edgeE);
1300 ChangeSet changesToPass = ChangeSet.factory();
1302 Iterator<ChangeTuple> itrC = C.iterator();
1303 while( itrC.hasNext() ) {
1304 ChangeTuple c = itrC.next();
1305 if( edgeE.getBeta().containsIgnorePreds(c.getStateToMatch() )
1308 changesToPass = Canonical.add(changesToPass, c);
1312 RefSrcNode rsn = edgeE.getSrc();
1314 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1315 HeapRegionNode n = (HeapRegionNode) rsn;
1317 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1318 while( referItr.hasNext() ) {
1319 RefEdge edgeF = referItr.next();
1321 if( !edgePlannedChanges.containsKey(edgeF) ) {
1322 edgePlannedChanges.put(edgeF,
1327 ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
1329 if( !changesToPass.isSubset(currentChanges) ) {
1330 todoEdges.add(edgeF);
1331 edgePlannedChanges.put(edgeF,
1332 Canonical.union(currentChanges,
1341 // then apply all of the changes for each edge at once
1342 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1343 while( itrMap.hasNext() ) {
1344 Map.Entry me = (Map.Entry)itrMap.next();
1345 RefEdge e = (RefEdge) me.getKey();
1346 ChangeSet C = (ChangeSet) me.getValue();
1348 // this propagation step is with respect to one change,
1349 // so we capture the full change from the old beta:
1350 ReachSet localDelta =
1351 Canonical.applyChangeSet(e.getBeta(),
1356 // but this propagation may be only one of many concurrent
1357 // possible changes, so keep a running union with the edge's
1358 // partially updated new beta set
1359 e.setBetaNew(Canonical.unionORpreds(e.getBetaNew(),
1364 edgesWithNewBeta.add(e);
1369 public void taintInSetVars(FlatSESEEnterNode sese) {
1371 Iterator<TempDescriptor> isvItr = sese.getInVarSet().iterator();
1372 while( isvItr.hasNext() ) {
1373 TempDescriptor isv = isvItr.next();
1375 // use this where defined flatnode to support RCR/DFJ
1376 FlatNode whereDefined = null;
1378 // in-set var taints should NOT propagate back into callers
1379 // so give it FALSE(EMPTY) predicates
1389 public void taintStallSite(FlatNode stallSite,
1390 TempDescriptor var) {
1392 // use this where defined flatnode to support RCR/DFJ
1393 FlatNode whereDefined = null;
1395 // stall site taint should propagate back into callers
1396 // so give it TRUE predicates
1405 protected void taintTemp(FlatSESEEnterNode sese,
1408 FlatNode whereDefined,
1412 VariableNode vn = getVariableNodeFromTemp(var);
1414 Iterator<RefEdge> reItr = vn.iteratorToReferencees();
1415 while( reItr.hasNext() ) {
1416 RefEdge re = reItr.next();
1418 Taint taint = Taint.factory(sese,
1421 re.getDst().getAllocSite(),
1426 re.setTaints(Canonical.add(re.getTaints(),
1433 public void removeInContextTaints(FlatSESEEnterNode sese) {
1435 Iterator meItr = id2hrn.entrySet().iterator();
1436 while( meItr.hasNext() ) {
1437 Map.Entry me = (Map.Entry)meItr.next();
1438 Integer id = (Integer) me.getKey();
1439 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1441 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1442 while( reItr.hasNext() ) {
1443 RefEdge re = reItr.next();
1445 re.setTaints(Canonical.removeInContextTaints(re.getTaints(),
1453 public void removeAllStallSiteTaints() {
1455 Iterator meItr = id2hrn.entrySet().iterator();
1456 while( meItr.hasNext() ) {
1457 Map.Entry me = (Map.Entry)meItr.next();
1458 Integer id = (Integer) me.getKey();
1459 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1461 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1462 while( reItr.hasNext() ) {
1463 RefEdge re = reItr.next();
1465 re.setTaints(Canonical.removeStallSiteTaints(re.getTaints()
1473 // used in makeCalleeView below to decide if there is
1474 // already an appropriate out-of-context edge in a callee
1475 // view graph for merging, or null if a new one will be added
1477 getOutOfContextReferenceTo(HeapRegionNode hrn,
1478 TypeDescriptor srcType,
1479 TypeDescriptor refType,
1481 assert belongsToThis(hrn);
1483 HeapRegionNode hrnInContext = id2hrn.get(hrn.getID() );
1484 if( hrnInContext == null ) {
1488 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1489 while( refItr.hasNext() ) {
1490 RefEdge re = refItr.next();
1492 assert belongsToThis(re.getSrc() );
1493 assert belongsToThis(re.getDst() );
1495 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1499 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1500 if( !hrnSrc.isOutOfContext() ) {
1504 if( srcType == null ) {
1505 if( hrnSrc.getType() != null ) {
1509 if( !srcType.equals(hrnSrc.getType() ) ) {
1514 if( !re.typeEquals(refType) ) {
1518 if( !re.fieldEquals(refField) ) {
1522 // tada! We found it!
1529 // used below to convert a ReachSet to its callee-context
1530 // equivalent with respect to allocation sites in this graph
1531 protected ReachSet toCalleeContext(ReachSet rs,
1532 ExistPredSet predsNodeOrEdge,
1533 Set<HrnIdOoc> oocHrnIdOoc2callee
1535 ReachSet out = ReachSet.factory();
1537 Iterator<ReachState> itr = rs.iterator();
1538 while( itr.hasNext() ) {
1539 ReachState stateCaller = itr.next();
1541 ReachState stateCallee = stateCaller;
1543 Iterator<AllocSite> asItr = allocSites.iterator();
1544 while( asItr.hasNext() ) {
1545 AllocSite as = asItr.next();
1547 ReachState stateNew = ReachState.factory();
1548 Iterator<ReachTuple> rtItr = stateCallee.iterator();
1549 while( rtItr.hasNext() ) {
1550 ReachTuple rt = rtItr.next();
1552 // only translate this tuple if it is
1553 // in the out-callee-context bag
1554 HrnIdOoc hio = new HrnIdOoc(rt.getHrnID(),
1557 if( !oocHrnIdOoc2callee.contains(hio) ) {
1558 stateNew = Canonical.addUpArity(stateNew, rt);
1562 int age = as.getAgeCategory(rt.getHrnID() );
1564 // this is the current mapping, where 0, 1, 2S were allocated
1565 // in the current context, 0?, 1? and 2S? were allocated in a
1566 // previous context, and we're translating to a future context
1578 if( age == AllocSite.AGE_notInThisSite ) {
1579 // things not from the site just go back in
1580 stateNew = Canonical.addUpArity(stateNew, rt);
1582 } else if( age == AllocSite.AGE_summary ||
1586 stateNew = Canonical.addUpArity(stateNew,
1587 ReachTuple.factory(as.getSummary(),
1590 true // out-of-context
1595 // otherwise everything else just goes to an out-of-context
1596 // version, everything else the same
1597 Integer I = as.getAge(rt.getHrnID() );
1600 assert !rt.isMultiObject();
1602 stateNew = Canonical.addUpArity(stateNew,
1603 ReachTuple.factory(rt.getHrnID(),
1604 rt.isMultiObject(), // multi
1606 true // out-of-context
1612 stateCallee = stateNew;
1615 // make a predicate of the caller graph element
1616 // and the caller state we just converted
1617 ExistPredSet predsWithState = ExistPredSet.factory();
1619 Iterator<ExistPred> predItr = predsNodeOrEdge.iterator();
1620 while( predItr.hasNext() ) {
1621 ExistPred predNodeOrEdge = predItr.next();
1624 Canonical.add(predsWithState,
1625 ExistPred.factory(predNodeOrEdge.n_hrnID,
1626 predNodeOrEdge.e_tdSrc,
1627 predNodeOrEdge.e_hrnSrcID,
1628 predNodeOrEdge.e_hrnDstID,
1629 predNodeOrEdge.e_type,
1630 predNodeOrEdge.e_field,
1633 predNodeOrEdge.e_srcOutCalleeContext,
1634 predNodeOrEdge.e_srcOutCallerContext
1639 stateCallee = Canonical.changePredsTo(stateCallee,
1642 out = Canonical.add(out,
1646 assert out.isCanonical();
1650 // used below to convert a ReachSet to its caller-context
1651 // equivalent with respect to allocation sites in this graph
1653 toCallerContext(ReachSet rs,
1654 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1656 ReachSet out = ReachSet.factory();
1658 // when the mapping is null it means there were no
1659 // predicates satisfied
1660 if( calleeStatesSatisfied == null ) {
1664 Iterator<ReachState> itr = rs.iterator();
1665 while( itr.hasNext() ) {
1666 ReachState stateCallee = itr.next();
1668 if( calleeStatesSatisfied.containsKey(stateCallee) ) {
1670 // starting from one callee state...
1671 ReachSet rsCaller = ReachSet.factory(stateCallee);
1673 // possibly branch it into many states, which any
1674 // allocation site might do, so lots of derived states
1675 Iterator<AllocSite> asItr = allocSites.iterator();
1676 while( asItr.hasNext() ) {
1677 AllocSite as = asItr.next();
1678 rsCaller = Canonical.toCallerContext(rsCaller, as);
1681 // then before adding each derived, now caller-context
1682 // states to the output, attach the appropriate pred
1683 // based on the source callee state
1684 Iterator<ReachState> stateItr = rsCaller.iterator();
1685 while( stateItr.hasNext() ) {
1686 ReachState stateCaller = stateItr.next();
1687 stateCaller = Canonical.attach(stateCaller,
1688 calleeStatesSatisfied.get(stateCallee)
1690 out = Canonical.add(out,
1697 assert out.isCanonical();
1702 // used below to convert a ReachSet to an equivalent
1703 // version with shadow IDs merged into unshadowed IDs
1704 protected ReachSet unshadow(ReachSet rs) {
1706 Iterator<AllocSite> asItr = allocSites.iterator();
1707 while( asItr.hasNext() ) {
1708 AllocSite as = asItr.next();
1709 out = Canonical.unshadow(out, as);
1711 assert out.isCanonical();
1716 // convert a caller taint set into a callee taint set
1718 toCalleeContext(TaintSet ts,
1719 ExistPredSet predsEdge) {
1721 TaintSet out = TaintSet.factory();
1723 // the idea is easy, the taint identifier itself doesn't
1724 // change at all, but the predicates should be tautology:
1725 // start with the preds passed in from the caller edge
1726 // that host the taints, and alter them to have the taint
1727 // added, just becoming more specific than edge predicate alone
1729 Iterator<Taint> itr = ts.iterator();
1730 while( itr.hasNext() ) {
1731 Taint tCaller = itr.next();
1733 ExistPredSet predsWithTaint = ExistPredSet.factory();
1735 Iterator<ExistPred> predItr = predsEdge.iterator();
1736 while( predItr.hasNext() ) {
1737 ExistPred predEdge = predItr.next();
1740 Canonical.add(predsWithTaint,
1741 ExistPred.factory(predEdge.e_tdSrc,
1742 predEdge.e_hrnSrcID,
1743 predEdge.e_hrnDstID,
1748 predEdge.e_srcOutCalleeContext,
1749 predEdge.e_srcOutCallerContext
1754 Taint tCallee = Canonical.changePredsTo(tCaller,
1757 out = Canonical.add(out,
1762 assert out.isCanonical();
1767 // used below to convert a TaintSet to its caller-context
1768 // equivalent, just eliminate Taints with bad preds
1770 toCallerContext(TaintSet ts,
1771 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied
1774 TaintSet out = TaintSet.factory();
1776 // when the mapping is null it means there were no
1777 // predicates satisfied
1778 if( calleeTaintsSatisfied == null ) {
1782 Iterator<Taint> itr = ts.iterator();
1783 while( itr.hasNext() ) {
1784 Taint tCallee = itr.next();
1786 if( calleeTaintsSatisfied.containsKey(tCallee) ) {
1789 Canonical.attach(Taint.factory(tCallee.sese,
1794 ExistPredSet.factory() ),
1795 calleeTaintsSatisfied.get(tCallee)
1797 out = Canonical.add(out,
1803 assert out.isCanonical();
1810 // use this method to make a new reach graph that is
1811 // what heap the FlatMethod callee from the FlatCall
1812 // would start with reaching from its arguments in
1815 makeCalleeView(FlatCall fc,
1816 FlatMethod fmCallee,
1817 Set<Integer> callerNodeIDsCopiedToCallee,
1818 boolean writeDebugDOTs
1822 // first traverse this context to find nodes and edges
1823 // that will be callee-reachable
1824 Set<HeapRegionNode> reachableCallerNodes =
1825 new HashSet<HeapRegionNode>();
1827 // caller edges between callee-reachable nodes
1828 Set<RefEdge> reachableCallerEdges =
1829 new HashSet<RefEdge>();
1831 // caller edges from arg vars, and the matching param index
1832 // because these become a special edge in callee
1833 // NOTE! One argument may be passed in as more than one parameter,
1834 // so map to a set of parameter indices!
1835 Hashtable< RefEdge, Set<Integer> > reachableCallerArgEdges2paramIndices =
1836 new Hashtable< RefEdge, Set<Integer> >();
1838 // caller edges from local vars or callee-unreachable nodes
1839 // (out-of-context sources) to callee-reachable nodes
1840 Set<RefEdge> oocCallerEdges =
1841 new HashSet<RefEdge>();
1844 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1846 TempDescriptor tdArg = fc.getArgMatchingParamIndex(fmCallee, i);
1847 VariableNode vnArgCaller = this.getVariableNodeFromTemp(tdArg);
1849 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1850 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1852 toVisitInCaller.add(vnArgCaller);
1854 while( !toVisitInCaller.isEmpty() ) {
1855 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1856 toVisitInCaller.remove(rsnCaller);
1857 visitedInCaller.add(rsnCaller);
1859 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1860 while( itrRefEdges.hasNext() ) {
1861 RefEdge reCaller = itrRefEdges.next();
1862 HeapRegionNode hrnCaller = reCaller.getDst();
1864 callerNodeIDsCopiedToCallee.add(hrnCaller.getID() );
1865 reachableCallerNodes.add(hrnCaller);
1867 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1868 reachableCallerEdges.add(reCaller);
1871 if( rsnCaller.equals(vnArgCaller) ) {
1872 Set<Integer> pIndices =
1873 reachableCallerArgEdges2paramIndices.get( reCaller );
1875 if( pIndices == null ) {
1876 pIndices = new HashSet<Integer>();
1877 reachableCallerArgEdges2paramIndices.put( reCaller, pIndices );
1882 oocCallerEdges.add(reCaller);
1886 if( !visitedInCaller.contains(hrnCaller) ) {
1887 toVisitInCaller.add(hrnCaller);
1890 } // end edge iteration
1891 } // end visiting heap nodes in caller
1892 } // end iterating over parameters as starting points
1896 // now collect out-of-callee-context IDs and
1897 // map them to whether the ID is out of the caller
1899 Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1901 Iterator<Integer> itrInContext =
1902 callerNodeIDsCopiedToCallee.iterator();
1903 while( itrInContext.hasNext() ) {
1904 Integer hrnID = itrInContext.next();
1905 HeapRegionNode hrnCallerAndInContext = id2hrn.get(hrnID);
1907 Iterator<RefEdge> itrMightCross =
1908 hrnCallerAndInContext.iteratorToReferencers();
1909 while( itrMightCross.hasNext() ) {
1910 RefEdge edgeMightCross = itrMightCross.next();
1912 RefSrcNode rsnCallerAndOutContext =
1913 edgeMightCross.getSrc();
1915 if( rsnCallerAndOutContext instanceof VariableNode ) {
1916 // variables do not have out-of-context reach states,
1918 oocCallerEdges.add(edgeMightCross);
1922 HeapRegionNode hrnCallerAndOutContext =
1923 (HeapRegionNode) rsnCallerAndOutContext;
1925 // is this source node out-of-context?
1926 if( callerNodeIDsCopiedToCallee.contains(hrnCallerAndOutContext.getID() ) ) {
1927 // no, skip this edge
1932 oocCallerEdges.add(edgeMightCross);
1934 // add all reach tuples on the node to list
1935 // of things that are out-of-context: insight
1936 // if this node is reachable from someting that WAS
1937 // in-context, then this node should already be in-context
1938 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1939 while( stateItr.hasNext() ) {
1940 ReachState state = stateItr.next();
1942 Iterator<ReachTuple> rtItr = state.iterator();
1943 while( rtItr.hasNext() ) {
1944 ReachTuple rt = rtItr.next();
1946 oocHrnIdOoc2callee.add(new HrnIdOoc(rt.getHrnID(),
1955 // the callee view is a new graph: DON'T MODIFY *THIS* graph
1956 ReachGraph rg = new ReachGraph();
1958 // add nodes to callee graph
1959 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1960 while( hrnItr.hasNext() ) {
1961 HeapRegionNode hrnCaller = hrnItr.next();
1963 assert callerNodeIDsCopiedToCallee.contains(hrnCaller.getID() );
1964 assert !rg.id2hrn.containsKey(hrnCaller.getID() );
1966 ExistPred pred = ExistPred.factory(hrnCaller.getID(), null);
1967 ExistPredSet preds = ExistPredSet.factory(pred);
1969 rg.createNewHeapRegionNode(hrnCaller.getID(),
1970 hrnCaller.isSingleObject(),
1971 hrnCaller.isNewSummary(),
1972 false, // out-of-context?
1973 hrnCaller.getType(),
1974 hrnCaller.getAllocSite(),
1975 toCalleeContext(hrnCaller.getInherent(),
1979 toCalleeContext(hrnCaller.getAlpha(),
1984 hrnCaller.getDescription()
1988 // add param edges to callee graph
1990 reachableCallerArgEdges2paramIndices.entrySet().iterator();
1991 while( argEdges.hasNext() ) {
1992 Map.Entry me = (Map.Entry) argEdges.next();
1993 RefEdge reArg = (RefEdge) me.getKey();
1994 Set<Integer> pInxs = (Set<Integer>) me.getValue();
1996 VariableNode vnCaller = (VariableNode) reArg.getSrc();
1997 TempDescriptor argCaller = vnCaller.getTempDescriptor();
1999 HeapRegionNode hrnDstCaller = reArg.getDst();
2000 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2001 assert hrnDstCallee != null;
2004 ExistPred.factory(argCaller,
2006 hrnDstCallee.getID(),
2011 true, // out-of-callee-context
2012 false // out-of-caller-context
2015 ExistPredSet preds =
2016 ExistPredSet.factory(pred);
2018 for( Integer index: pInxs ) {
2020 TempDescriptor paramCallee = fmCallee.getParameter(index);
2021 VariableNode vnCallee = rg.getVariableNodeFromTemp(paramCallee);
2024 new RefEdge(vnCallee,
2028 toCalleeContext(reArg.getBeta(),
2033 toCalleeContext(reArg.getTaints(),
2037 rg.addRefEdge(vnCallee,
2044 // add in-context edges to callee graph
2045 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
2046 while( reItr.hasNext() ) {
2047 RefEdge reCaller = reItr.next();
2048 RefSrcNode rsnCaller = reCaller.getSrc();
2049 assert rsnCaller instanceof HeapRegionNode;
2050 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2051 HeapRegionNode hrnDstCaller = reCaller.getDst();
2053 HeapRegionNode hrnSrcCallee = rg.id2hrn.get(hrnSrcCaller.getID() );
2054 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2055 assert hrnSrcCallee != null;
2056 assert hrnDstCallee != null;
2059 ExistPred.factory(null,
2060 hrnSrcCallee.getID(),
2061 hrnDstCallee.getID(),
2063 reCaller.getField(),
2066 false, // out-of-callee-context
2067 false // out-of-caller-context
2070 ExistPredSet preds =
2071 ExistPredSet.factory(pred);
2074 new RefEdge(hrnSrcCallee,
2077 reCaller.getField(),
2078 toCalleeContext(reCaller.getBeta(),
2083 toCalleeContext(reCaller.getTaints(),
2087 rg.addRefEdge(hrnSrcCallee,
2093 // add out-of-context edges to callee graph
2094 reItr = oocCallerEdges.iterator();
2095 while( reItr.hasNext() ) {
2096 RefEdge reCaller = reItr.next();
2097 RefSrcNode rsnCaller = reCaller.getSrc();
2098 HeapRegionNode hrnDstCaller = reCaller.getDst();
2099 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2100 assert hrnDstCallee != null;
2102 TypeDescriptor oocNodeType;
2104 TempDescriptor oocPredSrcTemp = null;
2105 Integer oocPredSrcID = null;
2106 boolean outOfCalleeContext;
2107 boolean outOfCallerContext;
2109 if( rsnCaller instanceof VariableNode ) {
2110 VariableNode vnCaller = (VariableNode) rsnCaller;
2112 oocReach = rsetEmpty;
2113 oocPredSrcTemp = vnCaller.getTempDescriptor();
2114 outOfCalleeContext = true;
2115 outOfCallerContext = false;
2118 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2119 assert !callerNodeIDsCopiedToCallee.contains(hrnSrcCaller.getID() );
2120 oocNodeType = hrnSrcCaller.getType();
2121 oocReach = hrnSrcCaller.getAlpha();
2122 oocPredSrcID = hrnSrcCaller.getID();
2123 if( hrnSrcCaller.isOutOfContext() ) {
2124 outOfCalleeContext = false;
2125 outOfCallerContext = true;
2127 outOfCalleeContext = true;
2128 outOfCallerContext = false;
2133 ExistPred.factory(oocPredSrcTemp,
2135 hrnDstCallee.getID(),
2137 reCaller.getField(),
2144 ExistPredSet preds =
2145 ExistPredSet.factory(pred);
2147 RefEdge oocEdgeExisting =
2148 rg.getOutOfContextReferenceTo(hrnDstCallee,
2154 if( oocEdgeExisting == null ) {
2155 // for consistency, map one out-of-context "identifier"
2156 // to one heap region node id, otherwise no convergence
2157 String oocid = "oocid"+
2159 hrnDstCallee.getIDString()+
2162 reCaller.getField();
2164 Integer oocHrnID = oocid2hrnid.get(oocid);
2166 HeapRegionNode hrnCalleeAndOutContext;
2168 if( oocHrnID == null ) {
2170 hrnCalleeAndOutContext =
2171 rg.createNewHeapRegionNode(null, // ID
2172 false, // single object?
2173 false, // new summary?
2174 true, // out-of-context?
2176 null, // alloc site, shouldn't be used
2177 toCalleeContext(oocReach,
2181 toCalleeContext(oocReach,
2189 oocid2hrnid.put(oocid, hrnCalleeAndOutContext.getID() );
2193 // the mapping already exists, so see if node is there
2194 hrnCalleeAndOutContext = rg.id2hrn.get(oocHrnID);
2196 if( hrnCalleeAndOutContext == null ) {
2198 hrnCalleeAndOutContext =
2199 rg.createNewHeapRegionNode(oocHrnID, // ID
2200 false, // single object?
2201 false, // new summary?
2202 true, // out-of-context?
2204 null, // alloc site, shouldn't be used
2205 toCalleeContext(oocReach,
2209 toCalleeContext(oocReach,
2218 // otherwise it is there, so merge reachability
2219 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2220 toCalleeContext(oocReach,
2229 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2231 rg.addRefEdge(hrnCalleeAndOutContext,
2233 new RefEdge(hrnCalleeAndOutContext,
2236 reCaller.getField(),
2237 toCalleeContext(reCaller.getBeta(),
2242 toCalleeContext(reCaller.getTaints(),
2248 // the out-of-context edge already exists
2249 oocEdgeExisting.setBeta(Canonical.unionORpreds(oocEdgeExisting.getBeta(),
2250 toCalleeContext(reCaller.getBeta(),
2257 oocEdgeExisting.setPreds(Canonical.join(oocEdgeExisting.getPreds(),
2262 oocEdgeExisting.setTaints(Canonical.unionORpreds(oocEdgeExisting.getTaints(),
2263 toCalleeContext(reCaller.getTaints(),
2269 HeapRegionNode hrnCalleeAndOutContext =
2270 (HeapRegionNode) oocEdgeExisting.getSrc();
2271 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2272 toCalleeContext(oocReach,
2279 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2284 if( writeDebugDOTs ) {
2285 debugGraphPrefix = String.format("call%03d", debugCallSiteVisitCounter);
2286 rg.writeGraph(debugGraphPrefix+"calleeview",
2287 resolveMethodDebugDOTwriteLabels,
2288 resolveMethodDebugDOTselectTemps,
2289 resolveMethodDebugDOTpruneGarbage,
2290 resolveMethodDebugDOThideReach,
2291 resolveMethodDebugDOThideSubsetReach,
2292 resolveMethodDebugDOThidePreds,
2293 resolveMethodDebugDOThideEdgeTaints);
2299 private static Hashtable<String, Integer> oocid2hrnid =
2300 new Hashtable<String, Integer>();
2303 private static boolean resolveMethodDebugDOTwriteLabels = true;
2304 private static boolean resolveMethodDebugDOTselectTemps = true;
2305 private static boolean resolveMethodDebugDOTpruneGarbage = true;
2306 private static boolean resolveMethodDebugDOThideReach = false;
2307 private static boolean resolveMethodDebugDOThideSubsetReach = true;
2308 private static boolean resolveMethodDebugDOThidePreds = false;
2309 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
2311 static String debugGraphPrefix;
2312 static int debugCallSiteVisitCounter;
2313 static int debugCallSiteVisitStartCapture;
2314 static int debugCallSiteNumVisitsToCapture;
2315 static boolean debugCallSiteStopAfter;
2319 resolveMethodCall(FlatCall fc,
2320 FlatMethod fmCallee,
2321 ReachGraph rgCallee,
2322 Set<Integer> callerNodeIDsCopiedToCallee,
2323 boolean writeDebugDOTs
2326 if( writeDebugDOTs ) {
2328 System.out.println(" Writing out visit "+
2329 debugCallSiteVisitCounter+
2330 " to debug call site");
2332 debugGraphPrefix = String.format("call%03d",
2333 debugCallSiteVisitCounter);
2335 rgCallee.writeGraph(debugGraphPrefix+"callee",
2336 resolveMethodDebugDOTwriteLabels,
2337 resolveMethodDebugDOTselectTemps,
2338 resolveMethodDebugDOTpruneGarbage,
2339 resolveMethodDebugDOThideReach,
2340 resolveMethodDebugDOThideSubsetReach,
2341 resolveMethodDebugDOThidePreds,
2342 resolveMethodDebugDOThideEdgeTaints);
2344 writeGraph(debugGraphPrefix+"caller00In",
2345 resolveMethodDebugDOTwriteLabels,
2346 resolveMethodDebugDOTselectTemps,
2347 resolveMethodDebugDOTpruneGarbage,
2348 resolveMethodDebugDOThideReach,
2349 resolveMethodDebugDOThideSubsetReach,
2350 resolveMethodDebugDOThidePreds,
2351 resolveMethodDebugDOThideEdgeTaints,
2352 callerNodeIDsCopiedToCallee);
2357 // method call transfer function steps:
2358 // 1. Use current callee-reachable heap (CRH) to test callee
2359 // predicates and mark what will be coming in.
2360 // 2. Wipe CRH out of caller.
2361 // 3. Transplant marked callee parts in:
2362 // a) bring in nodes
2363 // b) bring in callee -> callee edges
2364 // c) resolve out-of-context -> callee edges
2365 // d) assign return value
2366 // 4. Collapse shadow nodes down
2367 // 5. Global sweep it.
2370 // 1. mark what callee elements have satisfied predicates
2371 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
2372 new Hashtable<HeapRegionNode, ExistPredSet>();
2374 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
2375 new Hashtable<RefEdge, ExistPredSet>();
2377 Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
2378 calleeNode2calleeStatesSatisfied =
2379 new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
2381 Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
2382 calleeEdge2calleeStatesSatisfied =
2383 new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
2385 Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
2386 calleeEdge2calleeTaintsSatisfied =
2387 new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
2389 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
2390 new Hashtable< RefEdge, Set<RefSrcNode> >();
2394 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2395 while( meItr.hasNext() ) {
2396 Map.Entry me = (Map.Entry)meItr.next();
2397 Integer id = (Integer) me.getKey();
2398 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2400 // if a callee element's predicates are satisfied then a set
2401 // of CALLER predicates is returned: they are the predicates
2402 // that the callee element moved into the caller context
2403 // should have, and it is inefficient to find this again later
2404 ExistPredSet predsIfSatis =
2405 hrnCallee.getPreds().isSatisfiedBy(this,
2406 callerNodeIDsCopiedToCallee,
2409 if( predsIfSatis != null ) {
2410 calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
2412 // otherwise don't bother looking at edges to this node
2418 // since the node is coming over, find out which reach
2419 // states on it should come over, too
2420 assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
2422 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2423 while( stateItr.hasNext() ) {
2424 ReachState stateCallee = stateItr.next();
2427 stateCallee.getPreds().isSatisfiedBy(this,
2428 callerNodeIDsCopiedToCallee,
2430 if( predsIfSatis != null ) {
2432 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2433 calleeNode2calleeStatesSatisfied.get(hrnCallee);
2435 if( calleeStatesSatisfied == null ) {
2436 calleeStatesSatisfied =
2437 new Hashtable<ReachState, ExistPredSet>();
2439 calleeNode2calleeStatesSatisfied.put(hrnCallee, calleeStatesSatisfied);
2442 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2446 // then look at edges to the node
2447 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2448 while( reItr.hasNext() ) {
2449 RefEdge reCallee = reItr.next();
2450 RefSrcNode rsnCallee = reCallee.getSrc();
2452 // (caller local variables to in-context heap regions)
2453 // have an (out-of-context heap region -> in-context heap region)
2454 // abstraction in the callEE, so its true we never need to
2455 // look at a (var node -> heap region) edge in callee to bring
2456 // those over for the call site transfer, except for the special
2457 // case of *RETURN var* -> heap region edges.
2458 // What about (param var->heap region)
2459 // edges in callee? They are dealt with below this loop.
2461 if( rsnCallee instanceof VariableNode ) {
2463 // looking for the return-value variable only
2464 VariableNode vnCallee = (VariableNode) rsnCallee;
2465 if( vnCallee.getTempDescriptor() != tdReturn ) {
2469 TempDescriptor returnTemp = fc.getReturnTemp();
2470 if( returnTemp == null ||
2471 !DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2476 // note that the assignment of the return value is to a
2477 // variable in the caller which is out-of-context with
2478 // respect to the callee
2479 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2480 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2481 rsnCallers.add(vnLhsCaller);
2482 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2486 // for HeapRegionNode callee sources...
2488 // first see if the source is out-of-context, and only
2489 // proceed with this edge if we find some caller-context
2491 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2492 boolean matchedOutOfContext = false;
2494 if( !hrnSrcCallee.isOutOfContext() ) {
2497 hrnSrcCallee.getPreds().isSatisfiedBy(this,
2498 callerNodeIDsCopiedToCallee,
2500 if( predsIfSatis != null ) {
2501 calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
2503 // otherwise forget this edge
2508 // hrnSrcCallee is out-of-context
2509 assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
2511 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2513 // use the isSatisfiedBy with a non-null callers set to capture
2514 // nodes in the caller that match the predicates
2515 reCallee.getPreds().isSatisfiedBy( this,
2516 callerNodeIDsCopiedToCallee,
2519 if( !rsnCallers.isEmpty() ) {
2520 matchedOutOfContext = true;
2521 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2525 if( hrnSrcCallee.isOutOfContext() &&
2526 !matchedOutOfContext ) {
2533 reCallee.getPreds().isSatisfiedBy(this,
2534 callerNodeIDsCopiedToCallee,
2538 if( predsIfSatis != null ) {
2539 calleeEdgesSatisfied.put(reCallee, predsIfSatis);
2541 // since the edge is coming over, find out which reach
2542 // states on it should come over, too
2543 assert calleeEdge2calleeStatesSatisfied.get(reCallee) == null;
2545 stateItr = reCallee.getBeta().iterator();
2546 while( stateItr.hasNext() ) {
2547 ReachState stateCallee = stateItr.next();
2550 stateCallee.getPreds().isSatisfiedBy(this,
2551 callerNodeIDsCopiedToCallee,
2553 if( predsIfSatis != null ) {
2555 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2556 calleeEdge2calleeStatesSatisfied.get(reCallee);
2558 if( calleeStatesSatisfied == null ) {
2559 calleeStatesSatisfied =
2560 new Hashtable<ReachState, ExistPredSet>();
2562 calleeEdge2calleeStatesSatisfied.put(reCallee, calleeStatesSatisfied);
2565 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2569 // since the edge is coming over, find out which taints
2570 // on it should come over, too
2571 assert calleeEdge2calleeTaintsSatisfied.get(reCallee) == null;
2573 Iterator<Taint> tItr = reCallee.getTaints().iterator();
2574 while( tItr.hasNext() ) {
2575 Taint tCallee = tItr.next();
2578 tCallee.getPreds().isSatisfiedBy(this,
2579 callerNodeIDsCopiedToCallee,
2581 if( predsIfSatis != null ) {
2583 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2584 calleeEdge2calleeTaintsSatisfied.get(reCallee);
2586 if( calleeTaintsSatisfied == null ) {
2587 calleeTaintsSatisfied =
2588 new Hashtable<Taint, ExistPredSet>();
2590 calleeEdge2calleeTaintsSatisfied.put(reCallee, calleeTaintsSatisfied);
2593 calleeTaintsSatisfied.put(tCallee, predsIfSatis);
2600 if( writeDebugDOTs ) {
2601 writeGraph(debugGraphPrefix+"caller20BeforeWipe",
2602 resolveMethodDebugDOTwriteLabels,
2603 resolveMethodDebugDOTselectTemps,
2604 resolveMethodDebugDOTpruneGarbage,
2605 resolveMethodDebugDOThideReach,
2606 resolveMethodDebugDOThideSubsetReach,
2607 resolveMethodDebugDOThidePreds,
2608 resolveMethodDebugDOThideEdgeTaints);
2612 // 2. predicates tested, ok to wipe out caller part
2613 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2614 while( hrnItr.hasNext() ) {
2615 Integer hrnID = hrnItr.next();
2616 HeapRegionNode hrnCaller = id2hrn.get(hrnID);
2617 assert hrnCaller != null;
2619 // when clearing off nodes, also eliminate variable
2621 wipeOut(hrnCaller, true);
2624 // if we are assigning the return value to something, clobber now
2625 // as part of the wipe
2626 TempDescriptor returnTemp = fc.getReturnTemp();
2627 if( returnTemp != null &&
2628 DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2631 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2632 clearRefEdgesFrom(vnLhsCaller, null, null, true);
2638 if( writeDebugDOTs ) {
2639 writeGraph(debugGraphPrefix+"caller30BeforeAddingNodes",
2640 resolveMethodDebugDOTwriteLabels,
2641 resolveMethodDebugDOTselectTemps,
2642 resolveMethodDebugDOTpruneGarbage,
2643 resolveMethodDebugDOThideReach,
2644 resolveMethodDebugDOThideSubsetReach,
2645 resolveMethodDebugDOThidePreds,
2646 resolveMethodDebugDOThideEdgeTaints);
2652 // 3. callee elements with satisfied preds come in, note that
2653 // the mapping of elements satisfied to preds is like this:
2654 // A callee element EE has preds EEp that are satisfied by
2655 // some caller element ER. We bring EE into the caller
2656 // context as ERee with the preds of ER, namely ERp, which
2657 // in the following algorithm is the value in the mapping
2660 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2661 while( satisItr.hasNext() ) {
2662 Map.Entry me = (Map.Entry)satisItr.next();
2663 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2664 ExistPredSet preds = (ExistPredSet) me.getValue();
2666 // TODO: I think its true that the current implementation uses
2667 // the type of the OOC region and the predicates OF THE EDGE from
2668 // it to link everything up in caller context, so that's why we're
2669 // skipping this... maybe that's a sillier way to do it?
2670 if( hrnCallee.isOutOfContext() ) {
2674 AllocSite as = hrnCallee.getAllocSite();
2677 Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
2679 HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
2680 if( hrnCaller == null ) {
2682 createNewHeapRegionNode(hrnIDshadow, // id or null to generate a new one
2683 hrnCallee.isSingleObject(), // single object?
2684 hrnCallee.isNewSummary(), // summary?
2685 false, // out-of-context?
2686 hrnCallee.getType(), // type
2687 hrnCallee.getAllocSite(), // allocation site
2688 toCallerContext(hrnCallee.getInherent(),
2689 calleeNode2calleeStatesSatisfied.get(hrnCallee) ), // inherent reach
2690 null, // current reach
2691 predsEmpty, // predicates
2692 hrnCallee.getDescription() // description
2695 assert hrnCaller.isWiped();
2698 hrnCaller.setAlpha(toCallerContext(hrnCallee.getAlpha(),
2699 calleeNode2calleeStatesSatisfied.get(hrnCallee)
2703 hrnCaller.setPreds(preds);
2710 if( writeDebugDOTs ) {
2711 writeGraph(debugGraphPrefix+"caller31BeforeAddingEdges",
2712 resolveMethodDebugDOTwriteLabels,
2713 resolveMethodDebugDOTselectTemps,
2714 resolveMethodDebugDOTpruneGarbage,
2715 resolveMethodDebugDOThideReach,
2716 resolveMethodDebugDOThideSubsetReach,
2717 resolveMethodDebugDOThidePreds,
2718 resolveMethodDebugDOThideEdgeTaints);
2722 // set these up during the next procedure so after
2723 // the caller has all of its nodes and edges put
2724 // back together we can propagate the callee's
2725 // reach changes backwards into the caller graph
2726 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2728 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2729 new Hashtable<RefEdge, ChangeSet>();
2732 // 3.b) callee -> callee edges AND out-of-context -> callee
2733 // which includes return temp -> callee edges now, too
2734 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2735 while( satisItr.hasNext() ) {
2736 Map.Entry me = (Map.Entry)satisItr.next();
2737 RefEdge reCallee = (RefEdge) me.getKey();
2738 ExistPredSet preds = (ExistPredSet) me.getValue();
2740 HeapRegionNode hrnDstCallee = reCallee.getDst();
2741 AllocSite asDst = hrnDstCallee.getAllocSite();
2742 allocSites.add(asDst);
2744 Integer hrnIDDstShadow =
2745 asDst.getShadowIDfromID(hrnDstCallee.getID() );
2747 HeapRegionNode hrnDstCaller = id2hrn.get(hrnIDDstShadow);
2748 assert hrnDstCaller != null;
2751 RefSrcNode rsnCallee = reCallee.getSrc();
2753 Set<RefSrcNode> rsnCallers =
2754 new HashSet<RefSrcNode>();
2756 Set<RefSrcNode> oocCallers =
2757 calleeEdges2oocCallerSrcMatches.get(reCallee);
2759 if( rsnCallee instanceof HeapRegionNode ) {
2760 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2761 if( hrnCalleeSrc.isOutOfContext() ) {
2762 assert oocCallers != null;
2767 if( oocCallers == null ) {
2768 // there are no out-of-context matches, so it's
2769 // either a param/arg var or one in-context heap region
2770 if( rsnCallee instanceof VariableNode ) {
2771 // variable -> node in the callee should only
2772 // come into the caller if its from a param var
2773 VariableNode vnCallee = (VariableNode) rsnCallee;
2774 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2775 TempDescriptor tdArg = fc.getArgMatchingParam(fmCallee,
2777 if( tdArg == null ) {
2778 // this means the variable isn't a parameter, its local
2779 // to the callee so we ignore it in call site transfer
2780 // shouldn't this NEVER HAPPEN?
2784 rsnCallers.add(this.getVariableNodeFromTemp(tdArg) );
2787 // otherwise source is in context, one region
2789 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2791 // translate an in-context node to shadow
2792 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2793 allocSites.add(asSrc);
2795 Integer hrnIDSrcShadow =
2796 asSrc.getShadowIDfromID(hrnSrcCallee.getID() );
2798 HeapRegionNode hrnSrcCallerShadow =
2799 this.id2hrn.get(hrnIDSrcShadow);
2801 assert hrnSrcCallerShadow != null;
2803 rsnCallers.add(hrnSrcCallerShadow);
2807 // otherwise we have a set of out-of-context srcs
2808 // that should NOT be translated to shadow nodes
2809 assert !oocCallers.isEmpty();
2810 rsnCallers.addAll(oocCallers);
2813 // now make all caller edges we've identified from
2814 // this callee edge with a satisfied predicate
2815 assert !rsnCallers.isEmpty();
2816 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2817 while( rsnItr.hasNext() ) {
2818 RefSrcNode rsnCaller = rsnItr.next();
2820 RefEdge reCaller = new RefEdge(rsnCaller,
2823 reCallee.getField(),
2824 toCallerContext(reCallee.getBeta(),
2825 calleeEdge2calleeStatesSatisfied.get(reCallee) ),
2827 toCallerContext(reCallee.getTaints(),
2828 calleeEdge2calleeTaintsSatisfied.get(reCallee) )
2831 ChangeSet cs = ChangeSet.factory();
2832 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2833 while( rsItr.hasNext() ) {
2834 ReachState state = rsItr.next();
2835 ExistPredSet predsPreCallee = state.getPreds();
2837 if( state.isEmpty() ) {
2841 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2842 while( predItr.hasNext() ) {
2843 ExistPred pred = predItr.next();
2844 ReachState old = pred.ne_state;
2850 cs = Canonical.add(cs,
2851 ChangeTuple.factory(old,
2858 // we're just going to use the convenient "merge-if-exists"
2859 // edge call below, but still take a separate look if there
2860 // is an existing caller edge to build change sets properly
2861 if( !cs.isEmpty() ) {
2862 RefEdge edgeExisting = rsnCaller.getReferenceTo(hrnDstCaller,
2866 if( edgeExisting != null ) {
2867 ChangeSet csExisting = edgePlannedChanges.get(edgeExisting);
2868 if( csExisting == null ) {
2869 csExisting = ChangeSet.factory();
2871 edgePlannedChanges.put(edgeExisting,
2872 Canonical.union(csExisting,
2877 edgesForPropagation.add(reCaller);
2878 assert !edgePlannedChanges.containsKey(reCaller);
2879 edgePlannedChanges.put(reCaller, cs);
2883 // then add new caller edge or merge
2884 addEdgeOrMergeWithExisting(reCaller);
2892 if( writeDebugDOTs ) {
2893 writeGraph(debugGraphPrefix+"caller38propagateReach",
2894 resolveMethodDebugDOTwriteLabels,
2895 resolveMethodDebugDOTselectTemps,
2896 resolveMethodDebugDOTpruneGarbage,
2897 resolveMethodDebugDOThideReach,
2898 resolveMethodDebugDOThideSubsetReach,
2899 resolveMethodDebugDOThidePreds,
2900 resolveMethodDebugDOThideEdgeTaints);
2903 // propagate callee reachability changes to the rest
2904 // of the caller graph edges
2905 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2907 propagateTokensOverEdges(edgesForPropagation, // source edges
2908 edgePlannedChanges, // map src edge to change set
2909 edgesUpdated); // list of updated edges
2911 // commit beta' (beta<-betaNew)
2912 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2913 while( edgeItr.hasNext() ) {
2914 edgeItr.next().applyBetaNew();
2923 if( writeDebugDOTs ) {
2924 writeGraph(debugGraphPrefix+"caller40BeforeShadowMerge",
2925 resolveMethodDebugDOTwriteLabels,
2926 resolveMethodDebugDOTselectTemps,
2927 resolveMethodDebugDOTpruneGarbage,
2928 resolveMethodDebugDOThideReach,
2929 resolveMethodDebugDOThideSubsetReach,
2930 resolveMethodDebugDOThidePreds,
2931 resolveMethodDebugDOThideEdgeTaints);
2935 // 4) merge shadow nodes so alloc sites are back to k
2936 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2937 while( asItr.hasNext() ) {
2938 // for each allocation site do the following to merge
2939 // shadow nodes (newest from callee) with any existing
2940 // look for the newest normal and newest shadow "slot"
2941 // not being used, transfer normal to shadow. Keep
2942 // doing this until there are no more normal nodes, or
2943 // no empty shadow slots: then merge all remaining normal
2944 // nodes into the shadow summary. Finally, convert all
2945 // shadow to their normal versions.
2946 AllocSite as = asItr.next();
2950 while( ageNorm < allocationDepth &&
2951 ageShad < allocationDepth ) {
2953 // first, are there any normal nodes left?
2954 Integer idNorm = as.getIthOldest(ageNorm);
2955 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2956 if( hrnNorm == null ) {
2957 // no, this age of normal node not in the caller graph
2962 // yes, a normal node exists, is there an empty shadow
2963 // "slot" to transfer it onto?
2964 HeapRegionNode hrnShad = getIthNode(as, ageShad, true);
2965 if( !hrnShad.isWiped() ) {
2966 // no, this age of shadow node is not empty
2971 // yes, this shadow node is empty
2972 transferOnto(hrnNorm, hrnShad);
2977 // now, while there are still normal nodes but no shadow
2978 // slots, merge normal nodes into the shadow summary
2979 while( ageNorm < allocationDepth ) {
2981 // first, are there any normal nodes left?
2982 Integer idNorm = as.getIthOldest(ageNorm);
2983 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2984 if( hrnNorm == null ) {
2985 // no, this age of normal node not in the caller graph
2990 // yes, a normal node exists, so get the shadow summary
2991 HeapRegionNode summShad = getSummaryNode(as, true);
2992 mergeIntoSummary(hrnNorm, summShad);
2994 // now tokens in reachability sets need to age also
2995 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2996 while( itrAllHRNodes.hasNext() ) {
2997 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
2998 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
3000 ageTuplesFrom(as, hrnToAge);
3002 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
3003 while( itrEdges.hasNext() ) {
3004 ageTuplesFrom(as, itrEdges.next() );
3011 // if there is a normal summary, merge it into shadow summary
3012 Integer idNorm = as.getSummary();
3013 HeapRegionNode summNorm = id2hrn.get(idNorm);
3014 if( summNorm != null ) {
3015 HeapRegionNode summShad = getSummaryNode(as, true);
3016 mergeIntoSummary(summNorm, summShad);
3019 // finally, flip all existing shadow nodes onto the normal
3020 for( int i = 0; i < allocationDepth; ++i ) {
3021 Integer idShad = as.getIthOldestShadow(i);
3022 HeapRegionNode hrnShad = id2hrn.get(idShad);
3023 if( hrnShad != null ) {
3025 HeapRegionNode hrnNorm = getIthNode(as, i, false);
3026 assert hrnNorm.isWiped();
3027 transferOnto(hrnShad, hrnNorm);
3031 Integer idShad = as.getSummaryShadow();
3032 HeapRegionNode summShad = id2hrn.get(idShad);
3033 if( summShad != null ) {
3034 summNorm = getSummaryNode(as, false);
3035 transferOnto(summShad, summNorm);
3044 if( writeDebugDOTs ) {
3045 writeGraph(debugGraphPrefix+"caller45BeforeUnshadow",
3046 resolveMethodDebugDOTwriteLabels,
3047 resolveMethodDebugDOTselectTemps,
3048 resolveMethodDebugDOTpruneGarbage,
3049 resolveMethodDebugDOThideReach,
3050 resolveMethodDebugDOThideSubsetReach,
3051 resolveMethodDebugDOThidePreds,
3052 resolveMethodDebugDOThideEdgeTaints);
3056 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3057 while( itrAllHRNodes.hasNext() ) {
3058 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
3059 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3061 hrn.setAlpha(unshadow(hrn.getAlpha() ) );
3063 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
3064 while( itrEdges.hasNext() ) {
3065 RefEdge re = itrEdges.next();
3066 re.setBeta(unshadow(re.getBeta() ) );
3073 if( writeDebugDOTs ) {
3074 writeGraph(debugGraphPrefix+"caller50BeforeGlobalSweep",
3075 resolveMethodDebugDOTwriteLabels,
3076 resolveMethodDebugDOTselectTemps,
3077 resolveMethodDebugDOTpruneGarbage,
3078 resolveMethodDebugDOThideReach,
3079 resolveMethodDebugDOThideSubsetReach,
3080 resolveMethodDebugDOThidePreds,
3081 resolveMethodDebugDOThideEdgeTaints);
3086 if( !DISABLE_GLOBAL_SWEEP ) {
3091 if( writeDebugDOTs ) {
3092 writeGraph(debugGraphPrefix+"caller90AfterTransfer",
3093 resolveMethodDebugDOTwriteLabels,
3094 resolveMethodDebugDOTselectTemps,
3095 resolveMethodDebugDOTpruneGarbage,
3096 resolveMethodDebugDOThideReach,
3097 resolveMethodDebugDOThideSubsetReach,
3098 resolveMethodDebugDOThidePreds,
3099 resolveMethodDebugDOThideEdgeTaints);
3105 ////////////////////////////////////////////////////
3107 // Abstract garbage collection simply removes
3108 // heap region nodes that are not mechanically
3109 // reachable from a root set. This step is
3110 // essential for testing node and edge existence
3111 // predicates efficiently
3113 ////////////////////////////////////////////////////
3114 public void abstractGarbageCollect(Set<TempDescriptor> liveSet) {
3116 // calculate a root set, will be different for Java
3117 // version of analysis versus Bamboo version
3118 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3120 // visit every variable in graph while building root
3121 // set, and do iterating on a copy, so we can remove
3122 // dead variables while we're at this
3123 Iterator makeCopyItr = td2vn.entrySet().iterator();
3124 Set entrysCopy = new HashSet();
3125 while( makeCopyItr.hasNext() ) {
3126 entrysCopy.add(makeCopyItr.next() );
3129 Iterator eItr = entrysCopy.iterator();
3130 while( eItr.hasNext() ) {
3131 Map.Entry me = (Map.Entry)eItr.next();
3132 TempDescriptor td = (TempDescriptor) me.getKey();
3133 VariableNode vn = (VariableNode) me.getValue();
3135 if( liveSet.contains(td) ) {
3139 // dead var, remove completely from graph
3141 clearRefEdgesFrom(vn, null, null, true);
3145 // everything visited in a traversal is
3146 // considered abstractly live
3147 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3149 while( !toVisit.isEmpty() ) {
3150 RefSrcNode rsn = toVisit.iterator().next();
3151 toVisit.remove(rsn);
3154 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3155 while( hrnItr.hasNext() ) {
3156 RefEdge edge = hrnItr.next();
3157 HeapRegionNode hrn = edge.getDst();
3159 if( !visited.contains(hrn) ) {
3165 // get a copy of the set to iterate over because
3166 // we're going to monkey with the graph when we
3167 // identify a garbage node
3168 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3169 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3170 while( hrnItr.hasNext() ) {
3171 hrnAllPrior.add(hrnItr.next() );
3174 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3175 while( hrnAllItr.hasNext() ) {
3176 HeapRegionNode hrn = hrnAllItr.next();
3178 if( !visited.contains(hrn) ) {
3180 // heap region nodes are compared across ReachGraph
3181 // objects by their integer ID, so when discarding
3182 // garbage nodes we must also discard entries in
3183 // the ID -> heap region hashtable.
3184 id2hrn.remove(hrn.getID() );
3186 // RefEdge objects are two-way linked between
3187 // nodes, so when a node is identified as garbage,
3188 // actively clear references to and from it so
3189 // live nodes won't have dangling RefEdge's
3192 // if we just removed the last node from an allocation
3193 // site, it should be taken out of the ReachGraph's list
3194 AllocSite as = hrn.getAllocSite();
3195 if( !hasNodesOf(as) ) {
3196 allocSites.remove(as);
3202 protected boolean hasNodesOf(AllocSite as) {
3203 if( id2hrn.containsKey(as.getSummary() ) ) {
3207 for( int i = 0; i < allocationDepth; ++i ) {
3208 if( id2hrn.containsKey(as.getIthOldest(i) ) ) {
3216 ////////////////////////////////////////////////////
3218 // This global sweep is an optional step to prune
3219 // reachability sets that are not internally
3220 // consistent with the global graph. It should be
3221 // invoked after strong updates or method calls.
3223 ////////////////////////////////////////////////////
3224 public void globalSweep() {
3226 // boldB is part of the phase 1 sweep
3227 // it has an in-context table and an out-of-context table
3228 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3229 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3231 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3232 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3234 // visit every heap region to initialize alphaNew and betaNew,
3235 // and make a map of every hrnID to the source nodes it should
3236 // propagate forward from. In-context flagged hrnID's propagate
3237 // from only the in-context node they name, but out-of-context
3238 // ID's may propagate from several out-of-context nodes
3239 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3240 new Hashtable< Integer, Set<HeapRegionNode> >();
3242 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3243 new Hashtable< Integer, Set<HeapRegionNode> >();
3246 Iterator itrHrns = id2hrn.entrySet().iterator();
3247 while( itrHrns.hasNext() ) {
3248 Map.Entry me = (Map.Entry)itrHrns.next();
3249 Integer hrnID = (Integer) me.getKey();
3250 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3252 // assert that this node and incoming edges have clean alphaNew
3253 // and betaNew sets, respectively
3254 assert rsetEmpty.equals(hrn.getAlphaNew() );
3256 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3257 while( itrRers.hasNext() ) {
3258 RefEdge edge = itrRers.next();
3259 assert rsetEmpty.equals(edge.getBetaNew() );
3262 // make a mapping of IDs to heap regions they propagate from
3263 if( hrn.isFlagged() ) {
3264 assert !hrn.isOutOfContext();
3265 assert !icID2srcs.containsKey(hrn.getID() );
3267 // in-context flagged node IDs simply propagate from the
3269 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3271 icID2srcs.put(hrn.getID(), srcs);
3274 if( hrn.isOutOfContext() ) {
3275 assert !hrn.isFlagged();
3277 // the reachability states on an out-of-context
3278 // node are not really important (combinations of
3279 // IDs or arity)--what matters is that the states
3280 // specify which nodes this out-of-context node
3281 // stands in for. For example, if the state [17?, 19*]
3282 // appears on the ooc node, it may serve as a source
3283 // for node 17? and a source for node 19.
3284 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3285 while( stateItr.hasNext() ) {
3286 ReachState state = stateItr.next();
3288 Iterator<ReachTuple> rtItr = state.iterator();
3289 while( rtItr.hasNext() ) {
3290 ReachTuple rt = rtItr.next();
3291 assert rt.isOutOfContext();
3293 Set<HeapRegionNode> srcs = oocID2srcs.get(rt.getHrnID() );
3294 if( srcs == null ) {
3295 srcs = new HashSet<HeapRegionNode>();
3298 oocID2srcs.put(rt.getHrnID(), srcs);
3304 // calculate boldB for all hrnIDs identified by the above
3305 // node traversal, propagating from every source
3306 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3309 Set<HeapRegionNode> srcs;
3312 if( !icID2srcs.isEmpty() ) {
3313 Map.Entry me = (Map.Entry)icID2srcs.entrySet().iterator().next();
3314 hrnID = (Integer) me.getKey();
3315 srcs = (Set<HeapRegionNode>)me.getValue();
3317 icID2srcs.remove(hrnID);
3320 assert !oocID2srcs.isEmpty();
3322 Map.Entry me = (Map.Entry)oocID2srcs.entrySet().iterator().next();
3323 hrnID = (Integer) me.getKey();
3324 srcs = (Set<HeapRegionNode>)me.getValue();
3326 oocID2srcs.remove(hrnID);
3330 Hashtable<RefEdge, ReachSet> boldB_f =
3331 new Hashtable<RefEdge, ReachSet>();
3333 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3335 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3336 while( hrnItr.hasNext() ) {
3337 HeapRegionNode hrn = hrnItr.next();
3339 assert workSetEdges.isEmpty();
3341 // initial boldB_f constraints
3342 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3343 while( itrRees.hasNext() ) {
3344 RefEdge edge = itrRees.next();
3346 assert !boldB_f.containsKey(edge);
3347 boldB_f.put(edge, edge.getBeta() );
3349 assert !workSetEdges.contains(edge);
3350 workSetEdges.add(edge);
3353 // enforce the boldB_f constraint at edges until we reach a fixed point
3354 while( !workSetEdges.isEmpty() ) {
3355 RefEdge edge = workSetEdges.iterator().next();
3356 workSetEdges.remove(edge);
3358 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3359 while( itrPrime.hasNext() ) {
3360 RefEdge edgePrime = itrPrime.next();
3362 ReachSet prevResult = boldB_f.get(edgePrime);
3363 ReachSet intersection = Canonical.intersection(boldB_f.get(edge),
3367 if( prevResult == null ||
3368 Canonical.unionORpreds(prevResult,
3369 intersection).size()
3373 if( prevResult == null ) {
3374 boldB_f.put(edgePrime,
3375 Canonical.unionORpreds(edgePrime.getBeta(),
3380 boldB_f.put(edgePrime,
3381 Canonical.unionORpreds(prevResult,
3386 workSetEdges.add(edgePrime);
3393 boldBic.put(hrnID, boldB_f);
3395 boldBooc.put(hrnID, boldB_f);
3400 // use boldB to prune hrnIDs from alpha states that are impossible
3401 // and propagate the differences backwards across edges
3402 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3404 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3405 new Hashtable<RefEdge, ChangeSet>();
3408 itrHrns = id2hrn.entrySet().iterator();
3409 while( itrHrns.hasNext() ) {
3410 Map.Entry me = (Map.Entry)itrHrns.next();
3411 Integer hrnID = (Integer) me.getKey();
3412 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3414 // out-of-context nodes don't participate in the
3415 // global sweep, they serve as sources for the pass
3417 if( hrn.isOutOfContext() ) {
3421 // the inherent states of a region are the exception
3422 // to removal as the global sweep prunes
3423 ReachTuple rtException = ReachTuple.factory(hrnID,
3424 !hrn.isSingleObject(),
3425 ReachTuple.ARITY_ONE,
3426 false // out-of-context
3429 ChangeSet cts = ChangeSet.factory();
3431 // mark hrnIDs for removal
3432 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3433 while( stateItr.hasNext() ) {
3434 ReachState stateOld = stateItr.next();
3436 ReachState markedHrnIDs = ReachState.factory();
3438 Iterator<ReachTuple> rtItr = stateOld.iterator();
3439 while( rtItr.hasNext() ) {
3440 ReachTuple rtOld = rtItr.next();
3442 // never remove the inherent hrnID from a flagged region
3443 // because it is trivially satisfied
3444 if( hrn.isFlagged() ) {
3445 if( rtOld == rtException ) {
3450 // does boldB allow this hrnID?
3451 boolean foundState = false;
3452 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3453 while( incidentEdgeItr.hasNext() ) {
3454 RefEdge incidentEdge = incidentEdgeItr.next();
3456 Hashtable<RefEdge, ReachSet> B;
3457 if( rtOld.isOutOfContext() ) {
3458 B = boldBooc.get(rtOld.getHrnID() );
3461 if( !id2hrn.containsKey(rtOld.getHrnID() ) ) {
3462 // let symbols not in the graph get pruned
3466 B = boldBic.get(rtOld.getHrnID() );
3470 ReachSet boldB_rtOld_incident = B.get(incidentEdge);
3471 if( boldB_rtOld_incident != null &&
3472 boldB_rtOld_incident.containsIgnorePreds(stateOld) != null
3480 markedHrnIDs = Canonical.addUpArity(markedHrnIDs, rtOld);
3484 // if there is nothing marked, just move on
3485 if( markedHrnIDs.isEmpty() ) {
3486 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3493 // remove all marked hrnIDs and establish a change set that should
3494 // propagate backwards over edges from this node
3495 ReachState statePruned = ReachState.factory();
3496 rtItr = stateOld.iterator();
3497 while( rtItr.hasNext() ) {
3498 ReachTuple rtOld = rtItr.next();
3500 if( !markedHrnIDs.containsTuple(rtOld) ) {
3501 statePruned = Canonical.addUpArity(statePruned, rtOld);
3504 assert !stateOld.equals(statePruned);
3506 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3510 ChangeTuple ct = ChangeTuple.factory(stateOld,
3513 cts = Canonical.add(cts, ct);
3516 // throw change tuple set on all incident edges
3517 if( !cts.isEmpty() ) {
3518 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3519 while( incidentEdgeItr.hasNext() ) {
3520 RefEdge incidentEdge = incidentEdgeItr.next();
3522 edgesForPropagation.add(incidentEdge);
3524 if( edgePlannedChanges.get(incidentEdge) == null ) {
3525 edgePlannedChanges.put(incidentEdge, cts);
3527 edgePlannedChanges.put(
3529 Canonical.union(edgePlannedChanges.get(incidentEdge),
3538 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3540 propagateTokensOverEdges(edgesForPropagation,
3544 // at the end of the 1st phase reference edges have
3545 // beta, betaNew that correspond to beta and betaR
3547 // commit beta<-betaNew, so beta=betaR and betaNew
3548 // will represent the beta' calculation in 2nd phase
3550 // commit alpha<-alphaNew because it won't change
3551 HashSet<RefEdge> res = new HashSet<RefEdge>();
3553 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3554 while( nodeItr.hasNext() ) {
3555 HeapRegionNode hrn = nodeItr.next();
3557 // as mentioned above, out-of-context nodes only serve
3558 // as sources of reach states for the sweep, not part
3560 if( hrn.isOutOfContext() ) {
3561 assert hrn.getAlphaNew().equals(rsetEmpty);
3563 hrn.applyAlphaNew();
3566 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3567 while( itrRes.hasNext() ) {
3568 res.add(itrRes.next() );
3574 Iterator<RefEdge> edgeItr = res.iterator();
3575 while( edgeItr.hasNext() ) {
3576 RefEdge edge = edgeItr.next();
3577 HeapRegionNode hrn = edge.getDst();
3579 // commit results of last phase
3580 if( edgesUpdated.contains(edge) ) {
3581 edge.applyBetaNew();
3584 // compute intial condition of 2nd phase
3585 edge.setBetaNew(Canonical.intersection(edge.getBeta(),
3591 // every edge in the graph is the initial workset
3592 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3593 while( !edgeWorkSet.isEmpty() ) {
3594 RefEdge edgePrime = edgeWorkSet.iterator().next();
3595 edgeWorkSet.remove(edgePrime);
3597 RefSrcNode rsn = edgePrime.getSrc();
3598 if( !(rsn instanceof HeapRegionNode) ) {
3601 HeapRegionNode hrn = (HeapRegionNode) rsn;
3603 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3604 while( itrEdge.hasNext() ) {
3605 RefEdge edge = itrEdge.next();
3607 ReachSet prevResult = edge.getBetaNew();
3608 assert prevResult != null;
3610 ReachSet intersection =
3611 Canonical.intersection(edge.getBeta(),
3612 edgePrime.getBetaNew()
3615 if( Canonical.unionORpreds(prevResult,
3622 Canonical.unionORpreds(prevResult,
3626 edgeWorkSet.add(edge);
3631 // commit beta' (beta<-betaNew)
3632 edgeItr = res.iterator();
3633 while( edgeItr.hasNext() ) {
3634 edgeItr.next().applyBetaNew();
3639 // a useful assertion for debugging:
3640 // every in-context tuple on any edge or
3641 // any node should name a node that is
3642 // part of the graph
3643 public boolean inContextTuplesInGraph() {
3645 Iterator hrnItr = id2hrn.entrySet().iterator();
3646 while( hrnItr.hasNext() ) {
3647 Map.Entry me = (Map.Entry)hrnItr.next();
3648 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3651 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3652 while( stateItr.hasNext() ) {
3653 ReachState state = stateItr.next();
3655 Iterator<ReachTuple> rtItr = state.iterator();
3656 while( rtItr.hasNext() ) {
3657 ReachTuple rt = rtItr.next();
3659 if( !rt.isOutOfContext() ) {
3660 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3661 System.out.println(rt.getHrnID()+" is missing");
3669 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3670 while( edgeItr.hasNext() ) {
3671 RefEdge edge = edgeItr.next();
3673 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3674 while( stateItr.hasNext() ) {
3675 ReachState state = stateItr.next();
3677 Iterator<ReachTuple> rtItr = state.iterator();
3678 while( rtItr.hasNext() ) {
3679 ReachTuple rt = rtItr.next();
3681 if( !rt.isOutOfContext() ) {
3682 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3683 System.out.println(rt.getHrnID()+" is missing");
3696 // another useful assertion for debugging
3697 public boolean noEmptyReachSetsInGraph() {
3699 Iterator hrnItr = id2hrn.entrySet().iterator();
3700 while( hrnItr.hasNext() ) {
3701 Map.Entry me = (Map.Entry)hrnItr.next();
3702 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3704 if( !hrn.isOutOfContext() &&
3706 hrn.getAlpha().isEmpty()
3708 System.out.println("!!! "+hrn+" has an empty ReachSet !!!");
3712 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3713 while( edgeItr.hasNext() ) {
3714 RefEdge edge = edgeItr.next();
3716 if( edge.getBeta().isEmpty() ) {
3717 System.out.println("!!! "+edge+" has an empty ReachSet !!!");
3727 public boolean everyReachStateWTrue() {
3729 Iterator hrnItr = id2hrn.entrySet().iterator();
3730 while( hrnItr.hasNext() ) {
3731 Map.Entry me = (Map.Entry)hrnItr.next();
3732 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3735 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3736 while( stateItr.hasNext() ) {
3737 ReachState state = stateItr.next();
3739 if( !state.getPreds().equals(predsTrue) ) {
3745 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3746 while( edgeItr.hasNext() ) {
3747 RefEdge edge = edgeItr.next();
3749 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3750 while( stateItr.hasNext() ) {
3751 ReachState state = stateItr.next();
3753 if( !state.getPreds().equals(predsTrue) ) {
3766 ////////////////////////////////////////////////////
3767 // in merge() and equals() methods the suffix A
3768 // represents the passed in graph and the suffix
3769 // B refers to the graph in this object
3770 // Merging means to take the incoming graph A and
3771 // merge it into B, so after the operation graph B
3772 // is the final result.
3773 ////////////////////////////////////////////////////
3774 protected void merge(ReachGraph rg) {
3782 mergeAllocSites(rg);
3783 mergeInaccessibleVars(rg);
3786 protected void mergeNodes(ReachGraph rg) {
3788 // start with heap region nodes
3789 Set sA = rg.id2hrn.entrySet();
3790 Iterator iA = sA.iterator();
3791 while( iA.hasNext() ) {
3792 Map.Entry meA = (Map.Entry)iA.next();
3793 Integer idA = (Integer) meA.getKey();
3794 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3796 // if this graph doesn't have a node the
3797 // incoming graph has, allocate it
3798 if( !id2hrn.containsKey(idA) ) {
3799 HeapRegionNode hrnB = hrnA.copy();
3800 id2hrn.put(idA, hrnB);
3803 // otherwise this is a node present in both graphs
3804 // so make the new reachability set a union of the
3805 // nodes' reachability sets
3806 HeapRegionNode hrnB = id2hrn.get(idA);
3807 hrnB.setAlpha(Canonical.unionORpreds(hrnB.getAlpha(),
3812 hrnB.setPreds(Canonical.join(hrnB.getPreds(),
3819 if( !hrnA.equals(hrnB) ) {
3820 rg.writeGraph("graphA");
3821 this.writeGraph("graphB");
3822 throw new Error("flagged not matching");
3830 // now add any variable nodes that are in graph B but
3832 sA = rg.td2vn.entrySet();
3834 while( iA.hasNext() ) {
3835 Map.Entry meA = (Map.Entry)iA.next();
3836 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3837 VariableNode lnA = (VariableNode) meA.getValue();
3839 // if the variable doesn't exist in B, allocate and add it
3840 VariableNode lnB = getVariableNodeFromTemp(tdA);
3844 protected void mergeRefEdges(ReachGraph rg) {
3846 // between heap regions
3847 Set sA = rg.id2hrn.entrySet();
3848 Iterator iA = sA.iterator();
3849 while( iA.hasNext() ) {
3850 Map.Entry meA = (Map.Entry)iA.next();
3851 Integer idA = (Integer) meA.getKey();
3852 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3854 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3855 while( heapRegionsItrA.hasNext() ) {
3856 RefEdge edgeA = heapRegionsItrA.next();
3857 HeapRegionNode hrnChildA = edgeA.getDst();
3858 Integer idChildA = hrnChildA.getID();
3860 // at this point we know an edge in graph A exists
3861 // idA -> idChildA, does this exist in B?
3862 assert id2hrn.containsKey(idA);
3863 HeapRegionNode hrnB = id2hrn.get(idA);
3864 RefEdge edgeToMerge = null;
3866 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3867 while( heapRegionsItrB.hasNext() &&
3868 edgeToMerge == null ) {
3870 RefEdge edgeB = heapRegionsItrB.next();
3871 HeapRegionNode hrnChildB = edgeB.getDst();
3872 Integer idChildB = hrnChildB.getID();
3874 // don't use the RefEdge.equals() here because
3875 // we're talking about existence between graphs,
3876 // not intragraph equal
3877 if( idChildB.equals(idChildA) &&
3878 edgeB.typeAndFieldEquals(edgeA) ) {
3880 edgeToMerge = edgeB;
3884 // if the edge from A was not found in B,
3886 if( edgeToMerge == null ) {
3887 assert id2hrn.containsKey(idChildA);
3888 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3889 edgeToMerge = edgeA.copy();
3890 edgeToMerge.setSrc(hrnB);
3891 edgeToMerge.setDst(hrnChildB);
3892 addRefEdge(hrnB, hrnChildB, edgeToMerge);
3894 // otherwise, the edge already existed in both graphs
3895 // so merge their reachability sets
3897 // just replace this beta set with the union
3898 assert edgeToMerge != null;
3899 edgeToMerge.setBeta(
3900 Canonical.unionORpreds(edgeToMerge.getBeta(),
3904 edgeToMerge.setPreds(
3905 Canonical.join(edgeToMerge.getPreds(),
3909 edgeToMerge.setTaints(
3910 Canonical.union(edgeToMerge.getTaints(),
3918 // and then again from variable nodes
3919 sA = rg.td2vn.entrySet();
3921 while( iA.hasNext() ) {
3922 Map.Entry meA = (Map.Entry)iA.next();
3923 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3924 VariableNode vnA = (VariableNode) meA.getValue();
3926 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3927 while( heapRegionsItrA.hasNext() ) {
3928 RefEdge edgeA = heapRegionsItrA.next();
3929 HeapRegionNode hrnChildA = edgeA.getDst();
3930 Integer idChildA = hrnChildA.getID();
3932 // at this point we know an edge in graph A exists
3933 // tdA -> idChildA, does this exist in B?
3934 assert td2vn.containsKey(tdA);
3935 VariableNode vnB = td2vn.get(tdA);
3936 RefEdge edgeToMerge = null;
3938 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3939 while( heapRegionsItrB.hasNext() &&
3940 edgeToMerge == null ) {
3942 RefEdge edgeB = heapRegionsItrB.next();
3943 HeapRegionNode hrnChildB = edgeB.getDst();
3944 Integer idChildB = hrnChildB.getID();
3946 // don't use the RefEdge.equals() here because
3947 // we're talking about existence between graphs
3948 if( idChildB.equals(idChildA) &&
3949 edgeB.typeAndFieldEquals(edgeA) ) {
3951 edgeToMerge = edgeB;
3955 // if the edge from A was not found in B,
3957 if( edgeToMerge == null ) {
3958 assert id2hrn.containsKey(idChildA);
3959 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3960 edgeToMerge = edgeA.copy();
3961 edgeToMerge.setSrc(vnB);
3962 edgeToMerge.setDst(hrnChildB);
3963 addRefEdge(vnB, hrnChildB, edgeToMerge);
3965 // otherwise, the edge already existed in both graphs
3966 // so merge their reachability sets
3968 // just replace this beta set with the union
3969 edgeToMerge.setBeta(Canonical.unionORpreds(edgeToMerge.getBeta(),
3973 edgeToMerge.setPreds(Canonical.join(edgeToMerge.getPreds(),
3977 edgeToMerge.setTaints(
3978 Canonical.union(edgeToMerge.getTaints(),
3987 protected void mergeAllocSites(ReachGraph rg) {
3988 allocSites.addAll(rg.allocSites);
3991 protected void mergeInaccessibleVars(ReachGraph rg) {
3992 inaccessibleVars.addAll(rg.inaccessibleVars);
3997 static public boolean dbgEquals = false;
4000 // it is necessary in the equals() member functions
4001 // to "check both ways" when comparing the data
4002 // structures of two graphs. For instance, if all
4003 // edges between heap region nodes in graph A are
4004 // present and equal in graph B it is not sufficient
4005 // to say the graphs are equal. Consider that there
4006 // may be edges in graph B that are not in graph A.
4007 // the only way to know that all edges in both graphs
4008 // are equally present is to iterate over both data
4009 // structures and compare against the other graph.
4010 public boolean equals(ReachGraph rg) {
4014 System.out.println("rg is null");
4019 if( !areHeapRegionNodesEqual(rg) ) {
4021 System.out.println("hrn not equal");
4026 if( !areVariableNodesEqual(rg) ) {
4028 System.out.println("vars not equal");
4033 if( !areRefEdgesEqual(rg) ) {
4035 System.out.println("edges not equal");
4040 if( !inaccessibleVars.equals(rg.inaccessibleVars) ) {
4044 // if everything is equal up to this point,
4045 // assert that allocSites is also equal--
4046 // this data is redundant but kept for efficiency
4047 assert allocSites.equals(rg.allocSites);
4053 protected boolean areHeapRegionNodesEqual(ReachGraph rg) {
4055 if( !areallHRNinAalsoinBandequal(this, rg) ) {
4059 if( !areallHRNinAalsoinBandequal(rg, this) ) {
4066 static protected boolean areallHRNinAalsoinBandequal(ReachGraph rgA,
4068 Set sA = rgA.id2hrn.entrySet();
4069 Iterator iA = sA.iterator();
4070 while( iA.hasNext() ) {
4071 Map.Entry meA = (Map.Entry)iA.next();
4072 Integer idA = (Integer) meA.getKey();
4073 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4075 if( !rgB.id2hrn.containsKey(idA) ) {
4079 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4080 if( !hrnA.equalsIncludingAlphaAndPreds(hrnB) ) {
4088 protected boolean areVariableNodesEqual(ReachGraph rg) {
4090 if( !areallVNinAalsoinBandequal(this, rg) ) {
4094 if( !areallVNinAalsoinBandequal(rg, this) ) {
4101 static protected boolean areallVNinAalsoinBandequal(ReachGraph rgA,
4103 Set sA = rgA.td2vn.entrySet();
4104 Iterator iA = sA.iterator();
4105 while( iA.hasNext() ) {
4106 Map.Entry meA = (Map.Entry)iA.next();
4107 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4109 if( !rgB.td2vn.containsKey(tdA) ) {
4118 protected boolean areRefEdgesEqual(ReachGraph rg) {
4119 if( !areallREinAandBequal(this, rg) ) {
4123 if( !areallREinAandBequal(rg, this) ) {
4130 static protected boolean areallREinAandBequal(ReachGraph rgA,
4133 // check all the heap region->heap region edges
4134 Set sA = rgA.id2hrn.entrySet();
4135 Iterator iA = sA.iterator();
4136 while( iA.hasNext() ) {
4137 Map.Entry meA = (Map.Entry)iA.next();
4138 Integer idA = (Integer) meA.getKey();
4139 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4141 // we should have already checked that the same
4142 // heap regions exist in both graphs
4143 assert rgB.id2hrn.containsKey(idA);
4145 if( !areallREfromAequaltoB(rgA, hrnA, rgB) ) {
4149 // then check every edge in B for presence in A, starting
4150 // from the same parent HeapRegionNode
4151 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4153 if( !areallREfromAequaltoB(rgB, hrnB, rgA) ) {
4158 // then check all the variable->heap region edges
4159 sA = rgA.td2vn.entrySet();
4161 while( iA.hasNext() ) {
4162 Map.Entry meA = (Map.Entry)iA.next();
4163 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4164 VariableNode vnA = (VariableNode) meA.getValue();
4166 // we should have already checked that the same
4167 // label nodes exist in both graphs
4168 assert rgB.td2vn.containsKey(tdA);
4170 if( !areallREfromAequaltoB(rgA, vnA, rgB) ) {
4174 // then check every edge in B for presence in A, starting
4175 // from the same parent VariableNode
4176 VariableNode vnB = rgB.td2vn.get(tdA);
4178 if( !areallREfromAequaltoB(rgB, vnB, rgA) ) {
4187 static protected boolean areallREfromAequaltoB(ReachGraph rgA,
4191 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4192 while( itrA.hasNext() ) {
4193 RefEdge edgeA = itrA.next();
4194 HeapRegionNode hrnChildA = edgeA.getDst();
4195 Integer idChildA = hrnChildA.getID();
4197 assert rgB.id2hrn.containsKey(idChildA);
4199 // at this point we know an edge in graph A exists
4200 // rnA -> idChildA, does this exact edge exist in B?
4201 boolean edgeFound = false;
4203 RefSrcNode rnB = null;
4204 if( rnA instanceof HeapRegionNode ) {
4205 HeapRegionNode hrnA = (HeapRegionNode) rnA;
4206 rnB = rgB.id2hrn.get(hrnA.getID() );
4208 VariableNode vnA = (VariableNode) rnA;
4209 rnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4212 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4213 while( itrB.hasNext() ) {
4214 RefEdge edgeB = itrB.next();
4215 HeapRegionNode hrnChildB = edgeB.getDst();
4216 Integer idChildB = hrnChildB.getID();
4218 if( idChildA.equals(idChildB) &&
4219 edgeA.typeAndFieldEquals(edgeB) ) {
4221 // there is an edge in the right place with the right field,
4222 // but do they have the same attributes?
4223 if( edgeA.equalsIncludingBetaPredsTaints( edgeB ) ) {
4238 // can be used to assert monotonicity
4239 static public boolean isNoSmallerThan(ReachGraph rgA,
4242 //System.out.println( "*** Asking if A is no smaller than B ***" );
4244 Iterator iA = rgA.id2hrn.entrySet().iterator();
4245 while( iA.hasNext() ) {
4246 Map.Entry meA = (Map.Entry)iA.next();
4247 Integer idA = (Integer) meA.getKey();
4248 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4250 if( !rgB.id2hrn.containsKey(idA) ) {
4251 System.out.println(" regions smaller");
4256 // this works just fine, no smaller than
4257 if( !areallVNinAalsoinBandequal(rgA, rgB) ) {
4258 System.out.println(" vars smaller:");
4259 System.out.println(" A:"+rgA.td2vn.keySet() );
4260 System.out.println(" B:"+rgB.td2vn.keySet() );
4265 iA = rgA.id2hrn.entrySet().iterator();
4266 while( iA.hasNext() ) {
4267 Map.Entry meA = (Map.Entry)iA.next();
4268 Integer idA = (Integer) meA.getKey();
4269 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4271 Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4272 while( reItr.hasNext() ) {
4273 RefEdge edgeA = reItr.next();
4274 RefSrcNode rsnA = edgeA.getSrc();
4276 // we already checked that nodes were present
4277 HeapRegionNode hrnB = rgB.id2hrn.get(hrnA.getID() );
4278 assert hrnB != null;
4281 if( rsnA instanceof VariableNode ) {
4282 VariableNode vnA = (VariableNode) rsnA;
4283 rsnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4286 HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4287 rsnB = rgB.id2hrn.get(hrnSrcA.getID() );
4289 assert rsnB != null;
4291 RefEdge edgeB = rsnB.getReferenceTo(hrnB,
4295 if( edgeB == null ) {
4296 System.out.println(" edges smaller:");
4310 // this analysis no longer has the "match anything"
4311 // type which was represented by null
4312 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4313 TypeDescriptor td2) {
4317 if( td1.isNull() ) {
4320 if( td2.isNull() ) {
4323 return typeUtil.mostSpecific(td1, td2);
4326 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4328 TypeDescriptor td3) {
4330 return mostSpecificType(td1,
4331 mostSpecificType(td2, td3)
4335 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4338 TypeDescriptor td4) {
4340 return mostSpecificType(mostSpecificType(td1, td2),
4341 mostSpecificType(td3, td4)
4345 protected boolean isSuperiorType(TypeDescriptor possibleSuper,
4346 TypeDescriptor possibleChild) {
4347 assert possibleSuper != null;
4348 assert possibleChild != null;
4350 if( possibleSuper.isNull() ||
4351 possibleChild.isNull() ) {
4355 return typeUtil.isSuperorType(possibleSuper, possibleChild);
4359 protected boolean hasMatchingField(HeapRegionNode src,
4362 TypeDescriptor tdSrc = src.getType();
4363 assert tdSrc != null;
4365 if( tdSrc.isArray() ) {
4366 TypeDescriptor td = edge.getType();
4369 TypeDescriptor tdSrcDeref = tdSrc.dereference();
4370 assert tdSrcDeref != null;
4372 if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
4376 return edge.getField().equals(DisjointAnalysis.arrayElementFieldName);
4379 // if it's not a class, it doesn't have any fields to match
4380 if( !tdSrc.isClass() ) {
4384 ClassDescriptor cd = tdSrc.getClassDesc();
4385 while( cd != null ) {
4386 Iterator fieldItr = cd.getFields();
4388 while( fieldItr.hasNext() ) {
4389 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4391 if( fd.getType().equals(edge.getType() ) &&
4392 fd.getSymbol().equals(edge.getField() ) ) {
4397 cd = cd.getSuperDesc();
4400 // otherwise it is a class with fields
4401 // but we didn't find a match
4405 protected boolean hasMatchingType(RefEdge edge,
4406 HeapRegionNode dst) {
4408 // if the region has no type, matches everything
4409 TypeDescriptor tdDst = dst.getType();
4410 assert tdDst != null;
4412 // if the type is not a class or an array, don't
4413 // match because primitives are copied, no aliases
4414 ClassDescriptor cdDst = tdDst.getClassDesc();
4415 if( cdDst == null && !tdDst.isArray() ) {
4419 // if the edge type is null, it matches everything
4420 TypeDescriptor tdEdge = edge.getType();
4421 assert tdEdge != null;
4423 return typeUtil.isSuperorType(tdEdge, tdDst);
4428 // the default signature for quick-and-dirty debugging
4429 public void writeGraph(String graphName) {
4430 writeGraph(graphName,
4431 true, // write labels
4432 true, // label select
4433 true, // prune garbage
4434 false, // hide reachability
4435 true, // hide subset reachability
4436 true, // hide predicates
4437 false, // hide edge taints
4438 null // in-context boundary
4442 public void writeGraph(String graphName,
4443 boolean writeLabels,
4444 boolean labelSelect,
4445 boolean pruneGarbage,
4446 boolean hideReachability,
4447 boolean hideSubsetReachability,
4448 boolean hidePredicates,
4449 boolean hideEdgeTaints
4451 writeGraph(graphName,
4456 hideSubsetReachability,
4462 public void writeGraph(String graphName,
4463 boolean writeLabels,
4464 boolean labelSelect,
4465 boolean pruneGarbage,
4466 boolean hideReachability,
4467 boolean hideSubsetReachability,
4468 boolean hidePredicates,
4469 boolean hideEdgeTaints,
4470 Set<Integer> callerNodeIDsCopiedToCallee
4473 // remove all non-word characters from the graph name so
4474 // the filename and identifier in dot don't cause errors
4475 // jjenista - also replace underscore '_' to prevent some
4476 // really, really long names from IHMS debugging
4477 graphName = graphName.replaceAll("[\\W_]", "");
4480 new BufferedWriter(new FileWriter(graphName+".dot") );
4482 bw.write("digraph "+graphName+" {\n");
4485 // this is an optional step to form the callee-reachable
4486 // "cut-out" into a DOT cluster for visualization
4487 if( callerNodeIDsCopiedToCallee != null ) {
4489 bw.write(" subgraph cluster0 {\n");
4490 bw.write(" color=blue;\n");
4492 Iterator i = id2hrn.entrySet().iterator();
4493 while( i.hasNext() ) {
4494 Map.Entry me = (Map.Entry)i.next();
4495 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4497 if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4500 hrn.toStringDOT(hideReachability,
4501 hideSubsetReachability,
4511 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4513 // then visit every heap region node
4514 Iterator i = id2hrn.entrySet().iterator();
4515 while( i.hasNext() ) {
4516 Map.Entry me = (Map.Entry)i.next();
4517 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4519 // only visit nodes worth writing out--for instance
4520 // not every node at an allocation is referenced
4521 // (think of it as garbage-collected), etc.
4522 if( !pruneGarbage ||
4523 hrn.isOutOfContext() ||
4524 (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4527 if( !visited.contains(hrn) ) {
4528 traverseHeapRegionNodes(hrn,
4533 hideSubsetReachability,
4536 callerNodeIDsCopiedToCallee);
4541 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4544 // then visit every label node, useful for debugging
4546 i = td2vn.entrySet().iterator();
4547 while( i.hasNext() ) {
4548 Map.Entry me = (Map.Entry)i.next();
4549 VariableNode vn = (VariableNode) me.getValue();
4552 String labelStr = vn.getTempDescriptorString();
4553 if( labelStr.startsWith("___temp") ||
4554 labelStr.startsWith("___dst") ||
4555 labelStr.startsWith("___srctmp") ||
4556 labelStr.startsWith("___neverused")
4562 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4563 while( heapRegionsItr.hasNext() ) {
4564 RefEdge edge = heapRegionsItr.next();
4565 HeapRegionNode hrn = edge.getDst();
4567 if( !visited.contains(hrn) ) {
4568 traverseHeapRegionNodes(hrn,
4573 hideSubsetReachability,
4576 callerNodeIDsCopiedToCallee);
4579 bw.write(" "+vn.toString()+
4580 " -> "+hrn.toString()+
4581 edge.toStringDOT(hideReachability,
4582 hideSubsetReachability,
4594 } catch( IOException e ) {
4595 throw new Error("Error writing out DOT graph "+graphName);
4600 traverseHeapRegionNodes(HeapRegionNode hrn,
4603 Set<HeapRegionNode> visited,
4604 boolean hideReachability,
4605 boolean hideSubsetReachability,
4606 boolean hidePredicates,
4607 boolean hideEdgeTaints,
4608 Set<Integer> callerNodeIDsCopiedToCallee
4609 ) throws java.io.IOException {
4611 if( visited.contains(hrn) ) {
4616 // if we're drawing the callee-view subgraph, only
4617 // write out the node info if it hasn't already been
4619 if( callerNodeIDsCopiedToCallee == null ||
4620 !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4624 hrn.toStringDOT(hideReachability,
4625 hideSubsetReachability,
4630 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4631 while( childRegionsItr.hasNext() ) {
4632 RefEdge edge = childRegionsItr.next();
4633 HeapRegionNode hrnChild = edge.getDst();
4635 if( callerNodeIDsCopiedToCallee != null &&
4636 (edge.getSrc() instanceof HeapRegionNode) ) {
4637 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4638 if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4639 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4641 bw.write(" "+hrn.toString()+
4642 " -> "+hrnChild.toString()+
4643 edge.toStringDOT(hideReachability,
4644 hideSubsetReachability,
4649 } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4650 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4652 bw.write(" "+hrn.toString()+
4653 " -> "+hrnChild.toString()+
4654 edge.toStringDOT(hideReachability,
4655 hideSubsetReachability,
4658 ",color=blue,style=dashed")+
4661 bw.write(" "+hrn.toString()+
4662 " -> "+hrnChild.toString()+
4663 edge.toStringDOT(hideReachability,
4664 hideSubsetReachability,
4671 bw.write(" "+hrn.toString()+
4672 " -> "+hrnChild.toString()+
4673 edge.toStringDOT(hideReachability,
4674 hideSubsetReachability,
4681 traverseHeapRegionNodes(hrnChild,
4686 hideSubsetReachability,
4689 callerNodeIDsCopiedToCallee);
4698 // return the set of heap regions from the given allocation
4699 // site, if any, that exist in this graph
4700 protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4702 Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4704 Integer idSum = as.getSummary();
4705 if( id2hrn.containsKey(idSum) ) {
4706 out.add(id2hrn.get(idSum) );
4709 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4710 Integer idI = as.getIthOldest(i);
4711 if( id2hrn.containsKey(idI) ) {
4712 out.add(id2hrn.get(idI) );
4719 // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4720 // from the given allocation site, if any, from regions for that
4721 // site that exist in this graph
4722 protected Set<ReachTuple> getAnyExisting(AllocSite as,
4723 boolean includeARITY_ZEROORMORE,
4724 boolean includeARITY_ONE) {
4726 Set<ReachTuple> out = new HashSet<ReachTuple>();
4728 Integer idSum = as.getSummary();
4729 if( id2hrn.containsKey(idSum) ) {
4731 HeapRegionNode hrn = id2hrn.get(idSum);
4732 assert !hrn.isOutOfContext();
4734 if( !includeARITY_ZEROORMORE ) {
4735 out.add(ReachTuple.factory(hrn.getID(),
4736 true, // multi-obj region
4737 ReachTuple.ARITY_ZEROORMORE,
4742 if( includeARITY_ONE ) {
4743 out.add(ReachTuple.factory(hrn.getID(),
4744 true, // multi-object region
4745 ReachTuple.ARITY_ONE,
4751 if( !includeARITY_ONE ) {
4752 // no need to do the single-object regions that
4753 // only have an ARITY ONE possible
4757 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4759 Integer idI = as.getIthOldest(i);
4760 if( id2hrn.containsKey(idI) ) {
4762 HeapRegionNode hrn = id2hrn.get(idI);
4763 assert !hrn.isOutOfContext();
4765 out.add(ReachTuple.factory(hrn.getID(),
4766 false, // multi-object region
4767 ReachTuple.ARITY_ONE,
4777 // if an object allocated at the target site may be
4778 // reachable from both an object from root1 and an
4779 // object allocated at root2, return TRUE
4780 public boolean mayBothReachTarget(AllocSite asRoot1,
4782 AllocSite asTarget) {
4784 // consider all heap regions of the target and look
4785 // for a reach state that indicates regions of root1
4786 // and root2 might be able to reach same object
4787 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4789 // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4790 Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4791 Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4793 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4794 while( hrnItr.hasNext() ) {
4795 HeapRegionNode hrn = hrnItr.next();
4797 Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4798 while( rtItr1.hasNext() ) {
4799 ReachTuple rt1 = rtItr1.next();
4801 Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4802 while( rtItr2.hasNext() ) {
4803 ReachTuple rt2 = rtItr2.next();
4805 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4815 // similar to the method above, return TRUE if ever
4816 // more than one object from the root allocation site
4817 // may reach an object from the target site
4818 public boolean mayManyReachTarget(AllocSite asRoot,
4819 AllocSite asTarget) {
4821 // consider all heap regions of the target and look
4822 // for a reach state that multiple objects of root
4823 // might be able to reach the same object
4824 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4826 // get relevant reach tuples
4827 Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true, false);
4828 Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4830 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4831 while( hrnItr.hasNext() ) {
4832 HeapRegionNode hrn = hrnItr.next();
4834 // if any ZERORMORE tuples are here, TRUE
4835 Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4836 while( rtItr.hasNext() ) {
4837 ReachTuple rtZOM = rtItr.next();
4839 if( hrn.getAlpha().containsTuple(rtZOM) ) {
4844 // otherwise, look for any pair of ONE tuples
4845 Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4846 while( rtItr1.hasNext() ) {
4847 ReachTuple rt1 = rtItr1.next();
4849 Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4850 while( rtItr2.hasNext() ) {
4851 ReachTuple rt2 = rtItr2.next();
4857 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4871 public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4873 Set<HeapRegionNode> exhibitProofState =
4874 new HashSet<HeapRegionNode>();
4876 Iterator hrnItr = id2hrn.entrySet().iterator();
4877 while( hrnItr.hasNext() ) {
4878 Map.Entry me = (Map.Entry)hrnItr.next();
4879 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4881 ReachSet intersection =
4882 Canonical.intersection(proofOfSharing,
4885 if( !intersection.isEmpty() ) {
4886 assert !hrn.isOutOfContext();
4887 exhibitProofState.add(hrn);
4891 return exhibitProofState;
4895 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4896 HeapRegionNode hrn2) {
4897 assert hrn1 != null;
4898 assert hrn2 != null;
4900 assert !hrn1.isOutOfContext();
4901 assert !hrn2.isOutOfContext();
4903 assert belongsToThis(hrn1);
4904 assert belongsToThis(hrn2);
4906 assert !hrn1.getID().equals(hrn2.getID() );
4909 // then get the various tokens for these heap regions
4911 ReachTuple.factory(hrn1.getID(),
4912 !hrn1.isSingleObject(), // multi?
4913 ReachTuple.ARITY_ONE,
4916 ReachTuple h1star = null;
4917 if( !hrn1.isSingleObject() ) {
4919 ReachTuple.factory(hrn1.getID(),
4920 !hrn1.isSingleObject(),
4921 ReachTuple.ARITY_ZEROORMORE,
4926 ReachTuple.factory(hrn2.getID(),
4927 !hrn2.isSingleObject(),
4928 ReachTuple.ARITY_ONE,
4931 ReachTuple h2star = null;
4932 if( !hrn2.isSingleObject() ) {
4934 ReachTuple.factory(hrn2.getID(),
4935 !hrn2.isSingleObject(),
4936 ReachTuple.ARITY_ZEROORMORE,
4940 // then get the merged beta of all out-going edges from these heap
4943 ReachSet beta1 = ReachSet.factory();
4944 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4945 while (itrEdge.hasNext()) {
4946 RefEdge edge = itrEdge.next();
4947 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4950 ReachSet beta2 = ReachSet.factory();
4951 itrEdge = hrn2.iteratorToReferencees();
4952 while (itrEdge.hasNext()) {
4953 RefEdge edge = itrEdge.next();
4954 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4957 ReachSet proofOfSharing = ReachSet.factory();
4960 Canonical.unionORpreds(proofOfSharing,
4961 beta1.getStatesWithBoth(h1, h2)
4964 Canonical.unionORpreds(proofOfSharing,
4965 beta2.getStatesWithBoth(h1, h2)
4968 if( !hrn1.isSingleObject() ) {
4970 Canonical.unionORpreds(proofOfSharing,
4971 beta1.getStatesWithBoth(h1star, h2)
4974 Canonical.unionORpreds(proofOfSharing,
4975 beta2.getStatesWithBoth(h1star, h2)
4979 if( !hrn2.isSingleObject() ) {
4981 Canonical.unionORpreds(proofOfSharing,
4982 beta1.getStatesWithBoth(h1, h2star)
4985 Canonical.unionORpreds(proofOfSharing,
4986 beta2.getStatesWithBoth(h1, h2star)
4990 if( !hrn1.isSingleObject() &&
4991 !hrn2.isSingleObject()
4994 Canonical.unionORpreds(proofOfSharing,
4995 beta1.getStatesWithBoth(h1star, h2star)
4998 Canonical.unionORpreds(proofOfSharing,
4999 beta2.getStatesWithBoth(h1star, h2star)
5003 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5004 if( !proofOfSharing.isEmpty() ) {
5005 common = findCommonReachableNodes(proofOfSharing);
5006 if( !DISABLE_STRONG_UPDATES &&
5007 !DISABLE_GLOBAL_SWEEP
5009 assert !common.isEmpty();
5016 // this version of the above method checks whether there is sharing
5017 // among the objects in a summary node
5018 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
5020 assert hrn.isNewSummary();
5021 assert !hrn.isOutOfContext();
5022 assert belongsToThis(hrn);
5025 ReachTuple.factory(hrn.getID(),
5027 ReachTuple.ARITY_ZEROORMORE,
5030 // then get the merged beta of all out-going edges from
5033 ReachSet beta = ReachSet.factory();
5034 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
5035 while (itrEdge.hasNext()) {
5036 RefEdge edge = itrEdge.next();
5037 beta = Canonical.unionORpreds(beta, edge.getBeta());
5040 ReachSet proofOfSharing = ReachSet.factory();
5043 Canonical.unionORpreds(proofOfSharing,
5044 beta.getStatesWithBoth(hstar, hstar)
5047 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5048 if( !proofOfSharing.isEmpty() ) {
5049 common = findCommonReachableNodes(proofOfSharing);
5050 if( !DISABLE_STRONG_UPDATES &&
5051 !DISABLE_GLOBAL_SWEEP
5053 assert !common.isEmpty();
5061 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5062 Integer paramIndex1,
5063 Integer paramIndex2) {
5065 // get parameter's heap regions
5066 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5067 assert this.hasVariable(paramTemp1);
5068 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5071 if( !(paramVar1.getNumReferencees() == 1) ) {
5072 System.out.println("\n fm="+fm+"\n param="+paramTemp1);
5073 writeGraph("whatup");
5077 assert paramVar1.getNumReferencees() == 1;
5078 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5079 HeapRegionNode hrnParam1 = paramEdge1.getDst();
5081 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5082 assert this.hasVariable(paramTemp2);
5083 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5085 if( !(paramVar2.getNumReferencees() == 1) ) {
5086 System.out.println("\n fm="+fm+"\n param="+paramTemp2);
5087 writeGraph("whatup");
5090 assert paramVar2.getNumReferencees() == 1;
5091 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5092 HeapRegionNode hrnParam2 = paramEdge2.getDst();
5094 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5095 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5100 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5104 // get parameter's heap regions
5105 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5106 assert this.hasVariable(paramTemp);
5107 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5108 assert paramVar.getNumReferencees() == 1;
5109 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5110 HeapRegionNode hrnParam = paramEdge.getDst();
5113 HeapRegionNode hrnSummary=null;
5114 if(id2hrn.containsKey(as.getSummary())) {
5115 // if summary node doesn't exist, ignore this case
5116 hrnSummary = id2hrn.get(as.getSummary());
5117 assert hrnSummary != null;
5120 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5121 if(hrnSummary!=null) {
5122 common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5125 // check for other nodes
5126 for (int i = 0; i < as.getAllocationDepth(); ++i) {
5128 assert id2hrn.containsKey(as.getIthOldest(i));
5129 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5130 assert hrnIthOldest != null;
5132 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5139 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5142 // get summary node 1's alpha
5143 Integer idSum1 = as1.getSummary();
5144 HeapRegionNode hrnSum1=null;
5145 if(id2hrn.containsKey(idSum1)) {
5146 hrnSum1 = id2hrn.get(idSum1);
5149 // get summary node 2's alpha
5150 Integer idSum2 = as2.getSummary();
5151 HeapRegionNode hrnSum2=null;
5152 if(id2hrn.containsKey(idSum2)) {
5153 hrnSum2 = id2hrn.get(idSum2);
5156 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5157 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5158 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5162 // ask if objects from this summary share among each other
5163 common.addAll(mayReachSharedObjects(hrnSum1));
5166 // check sum2 against alloc1 nodes
5168 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5169 Integer idI1 = as1.getIthOldest(i);
5170 assert id2hrn.containsKey(idI1);
5171 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5172 assert hrnI1 != null;
5173 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5176 // also ask if objects from this summary share among each other
5177 common.addAll(mayReachSharedObjects(hrnSum2));
5180 // check sum1 against alloc2 nodes
5181 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5182 Integer idI2 = as2.getIthOldest(i);
5183 assert id2hrn.containsKey(idI2);
5184 HeapRegionNode hrnI2 = id2hrn.get(idI2);
5185 assert hrnI2 != null;
5188 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5191 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5192 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5193 Integer idI1 = as1.getIthOldest(j);
5195 // if these are the same site, don't look for the same token, no
5197 // different tokens of the same site could alias together though
5198 if (idI1.equals(idI2)) {
5202 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5204 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5211 public void makeInaccessible(Set<TempDescriptor> vars) {
5212 inaccessibleVars.addAll(vars);
5215 public void makeInaccessible(TempDescriptor td) {
5216 inaccessibleVars.add(td);
5219 public void makeAccessible(TempDescriptor td) {
5220 inaccessibleVars.remove(td);
5223 public boolean isAccessible(TempDescriptor td) {
5224 return !inaccessibleVars.contains(td);
5227 public Set<TempDescriptor> getInaccessibleVars() {
5228 return inaccessibleVars;
5234 public Set<Alloc> canPointTo( TempDescriptor x ) {
5236 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5237 // if we don't care to track it, return null which means
5238 // "a client of this result shouldn't care either"
5239 return HeapAnalysis.DONTCARE_PTR;
5242 Set<Alloc> out = new HashSet<Alloc>();
5244 VariableNode vn = getVariableNodeNoMutation( x );
5246 // the empty set means "can't point to anything"
5250 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5251 while( edgeItr.hasNext() ) {
5252 HeapRegionNode hrn = edgeItr.next().getDst();
5253 out.add( hrn.getAllocSite() );
5261 public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5263 TypeDescriptor fieldType ) {
5265 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5266 // if we don't care to track it, return null which means
5267 // "a client of this result shouldn't care either"
5268 return HeapAnalysis.DONTCARE_DREF;
5271 Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5273 VariableNode vn = getVariableNodeNoMutation( x );
5275 // the empty table means "x can't point to anything"
5279 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5280 while( edgeItr.hasNext() ) {
5281 HeapRegionNode hrn = edgeItr.next().getDst();
5282 Alloc key = hrn.getAllocSite();
5284 if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5285 // if we don't care to track it, put no entry which means
5286 // "a client of this result shouldn't care either"
5287 out.put( key, HeapAnalysis.DONTCARE_PTR );
5291 Set<Alloc> moreValues = new HashSet<Alloc>();
5292 Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5293 while( edgeItr2.hasNext() ) {
5294 RefEdge edge = edgeItr2.next();
5296 if( field.equals( edge.getField() ) ) {
5297 moreValues.add( edge.getDst().getAllocSite() );
5301 if( out.containsKey( key ) ) {
5302 out.get( key ).addAll( moreValues );
5304 out.put( key, moreValues );
5314 public TempDescriptor findVariableByName( String name ) {
5316 for( TempDescriptor td: td2vn.keySet() ) {
5317 if( td.getSymbol().contains( name ) ) {