1 package Analysis.Disjoint;
5 import Util.UtilAlgorithms;
9 public class ReachGraph {
11 // use to disable improvements for comparison
12 protected static boolean DISABLE_STRONG_UPDATES = false;
13 protected static boolean DISABLE_GLOBAL_SWEEP = false;
14 protected static boolean DISABLE_PREDICATES = false;
16 // a special out-of-scope temps
17 protected static TempDescriptor tdReturn;
18 protected static TempDescriptor tdStrLiteralBytes;
20 public static void initOutOfScopeTemps() {
21 tdReturn = new TempDescriptor("_Return___");
24 new TempDescriptor("_strLiteralBytes___",
25 new TypeDescriptor(TypeDescriptor.CHAR).makeArray( state )
29 // predicate constants
30 public static final ExistPred predTrue = ExistPred.factory(); // if no args, true
31 public static final ExistPredSet predsEmpty = ExistPredSet.factory();
32 public static final ExistPredSet predsTrue = ExistPredSet.factory(predTrue);
34 // some frequently used reachability constants
35 protected static final ReachState rstateEmpty = ReachState.factory();
36 protected static final ReachSet rsetEmpty = ReachSet.factory();
37 protected static final ReachSet rsetWithEmptyState = Canonical.changePredsTo(ReachSet.factory(rstateEmpty),
40 // from DisjointAnalysis for convenience
41 protected static int allocationDepth = -1;
42 protected static TypeUtil typeUtil = null;
43 protected static State state = null;
46 // variable and heap region nodes indexed by unique ID
47 public Hashtable<Integer, HeapRegionNode> id2hrn;
48 public Hashtable<TempDescriptor, VariableNode > td2vn;
50 // convenient set of alloc sites for all heap regions
51 // present in the graph without having to search
52 public Set<AllocSite> allocSites;
54 // set of inaccessible variables for current program statement
55 // with respect to stall-site analysis
56 public Set<TempDescriptor> inaccessibleVars;
60 id2hrn = new Hashtable<Integer, HeapRegionNode>();
61 td2vn = new Hashtable<TempDescriptor, VariableNode >();
62 allocSites = new HashSet<AllocSite>();
63 inaccessibleVars = new HashSet<TempDescriptor>();
67 // temp descriptors are globally unique and map to
68 // exactly one variable node, easy
69 protected VariableNode getVariableNodeFromTemp(TempDescriptor td) {
72 if( !td2vn.containsKey(td) ) {
73 td2vn.put(td, new VariableNode(td) );
79 //This method is created for client modules to access the Reachgraph
80 //after the analysis is done and no modifications are to be made.
81 public VariableNode getVariableNodeNoMutation(TempDescriptor td) {
84 if( !td2vn.containsKey(td) ) {
91 public boolean hasVariable(TempDescriptor td) {
92 return td2vn.containsKey(td);
96 // this suite of methods can be used to assert a
97 // very important property of ReachGraph objects:
98 // some element, HeapRegionNode, RefEdge etc.
99 // should be referenced by at most ONE ReachGraph!!
100 // If a heap region or edge or variable should be
101 // in another graph, make a new object with
102 // equivalent properties for a new graph
103 public boolean belongsToThis(RefSrcNode rsn) {
104 if( rsn instanceof VariableNode ) {
105 VariableNode vn = (VariableNode) rsn;
106 return this.td2vn.get(vn.getTempDescriptor() ) == vn;
108 HeapRegionNode hrn = (HeapRegionNode) rsn;
109 return this.id2hrn.get(hrn.getID() ) == hrn;
116 // the reason for this method is to have the option
117 // of creating new heap regions with specific IDs, or
118 // duplicating heap regions with specific IDs (especially
119 // in the merge() operation) or to create new heap
120 // regions with a new unique ID
121 protected HeapRegionNode
122 createNewHeapRegionNode(Integer id,
123 boolean isSingleObject,
124 boolean isNewSummary,
125 boolean isOutOfContext,
134 TypeDescriptor typeToUse = null;
135 if( allocSite != null ) {
136 typeToUse = allocSite.getType();
137 allocSites.add(allocSite);
142 boolean markForAnalysis = false;
143 if( allocSite != null && allocSite.isFlagged() ) {
144 markForAnalysis = true;
147 if( allocSite == null ) {
148 assert !markForAnalysis;
150 } else if( markForAnalysis != allocSite.isFlagged() ) {
156 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
159 if( inherent == null ) {
160 if( markForAnalysis ) {
162 Canonical.changePredsTo(
165 ReachTuple.factory(id,
167 ReachTuple.ARITY_ONE,
168 false // out-of-context
175 inherent = rsetWithEmptyState;
179 if( alpha == null ) {
183 assert preds != null;
185 HeapRegionNode hrn = new HeapRegionNode(id,
202 ////////////////////////////////////////////////
204 // Low-level referencee and referencer methods
206 // These methods provide the lowest level for
207 // creating references between reachability nodes
208 // and handling the details of maintaining both
209 // list of referencers and referencees.
211 ////////////////////////////////////////////////
212 protected void addRefEdge(RefSrcNode referencer,
213 HeapRegionNode referencee,
215 assert referencer != null;
216 assert referencee != null;
218 assert edge.getSrc() == referencer;
219 assert edge.getDst() == referencee;
220 assert belongsToThis(referencer);
221 assert belongsToThis(referencee);
223 // edges are getting added twice to graphs now, the
224 // kind that should have abstract facts merged--use
225 // this check to prevent that
226 assert referencer.getReferenceTo(referencee,
231 referencer.addReferencee(edge);
232 referencee.addReferencer(edge);
235 protected void removeRefEdge(RefEdge e) {
236 removeRefEdge(e.getSrc(),
242 protected void removeRefEdge(RefSrcNode referencer,
243 HeapRegionNode referencee,
246 assert referencer != null;
247 assert referencee != null;
249 RefEdge edge = referencer.getReferenceTo(referencee,
253 assert edge == referencee.getReferenceFrom(referencer,
257 referencer.removeReferencee(edge);
258 referencee.removeReferencer(edge);
262 protected boolean clearRefEdgesFrom(RefSrcNode referencer,
266 return clearRefEdgesFrom( referencer, type, field, removeAll, null, null );
269 // return whether at least one edge was removed
270 protected boolean clearRefEdgesFrom(RefSrcNode referencer,
274 Set<EdgeKey> edgeKeysRemoved,
275 FieldDescriptor fd) {
276 assert referencer != null;
278 boolean atLeastOneEdgeRemoved = false;
280 // get a copy of the set to iterate over, otherwise
281 // we will be trying to take apart the set as we
282 // are iterating over it, which won't work
283 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
284 while( i.hasNext() ) {
285 RefEdge edge = i.next();
288 (edge.typeEquals(type) && edge.fieldEquals(field))
291 HeapRegionNode referencee = edge.getDst();
293 if( edgeKeysRemoved != null ) {
295 assert referencer instanceof HeapRegionNode;
296 edgeKeysRemoved.add( new EdgeKey( ((HeapRegionNode)referencer).getID(),
302 removeRefEdge(referencer,
307 atLeastOneEdgeRemoved = true;
311 return atLeastOneEdgeRemoved;
314 protected void clearRefEdgesTo(HeapRegionNode referencee,
318 assert referencee != null;
320 // get a copy of the set to iterate over, otherwise
321 // we will be trying to take apart the set as we
322 // are iterating over it, which won't work
323 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
324 while( i.hasNext() ) {
325 RefEdge edge = i.next();
328 (edge.typeEquals(type) && edge.fieldEquals(field))
331 RefSrcNode referencer = edge.getSrc();
333 removeRefEdge(referencer,
341 protected void clearNonVarRefEdgesTo(HeapRegionNode referencee) {
342 assert referencee != null;
344 // get a copy of the set to iterate over, otherwise
345 // we will be trying to take apart the set as we
346 // are iterating over it, which won't work
347 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
348 while( i.hasNext() ) {
349 RefEdge edge = i.next();
350 RefSrcNode referencer = edge.getSrc();
351 if( !(referencer instanceof VariableNode) ) {
352 removeRefEdge(referencer,
360 // this is a common operation in many transfer functions: we want
361 // to add an edge, but if there is already such an edge we should
362 // merge the properties of the existing and the new edges
363 protected void addEdgeOrMergeWithExisting(RefEdge edgeNew) {
365 RefSrcNode src = edgeNew.getSrc();
366 assert belongsToThis(src);
368 HeapRegionNode dst = edgeNew.getDst();
369 assert belongsToThis(dst);
371 // look to see if an edge with same field exists
372 // and merge with it, otherwise just add the edge
373 RefEdge edgeExisting = src.getReferenceTo(dst,
378 if( edgeExisting != null ) {
379 edgeExisting.setBeta(
380 Canonical.unionORpreds(edgeExisting.getBeta(),
384 edgeExisting.setPreds(
385 Canonical.join(edgeExisting.getPreds(),
389 edgeExisting.setTaints(
390 Canonical.unionORpreds(edgeExisting.getTaints(),
396 addRefEdge(src, dst, edgeNew);
402 ////////////////////////////////////////////////////
404 // Assignment Operation Methods
406 // These methods are high-level operations for
407 // modeling program assignment statements using
408 // the low-level reference create/remove methods
411 ////////////////////////////////////////////////////
413 public void assignTempEqualToStringLiteral(TempDescriptor x,
414 AllocSite asStringLiteral,
415 AllocSite asStringLiteralBytes,
416 FieldDescriptor fdStringBytesField) {
417 // model this to get points-to information right for
418 // pointers to string literals, even though it doesn't affect
419 // reachability paths in the heap
420 assignTempEqualToNewAlloc( x,
423 assignTempEqualToNewAlloc( tdStrLiteralBytes,
424 asStringLiteralBytes );
426 assignTempXFieldFEqualToTempY( x,
437 public void assignTempXEqualToTempY(TempDescriptor x,
439 assignTempXEqualToCastedTempY(x, y, null);
443 public void assignTempXEqualToCastedTempY(TempDescriptor x,
445 TypeDescriptor tdCast) {
447 VariableNode lnX = getVariableNodeFromTemp(x);
448 VariableNode lnY = getVariableNodeFromTemp(y);
450 clearRefEdgesFrom(lnX, null, null, true);
452 // note it is possible that the types of temps in the
453 // flat node to analyze will reveal that some typed
454 // edges in the reachability graph are impossible
455 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
457 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
458 while( itrYhrn.hasNext() ) {
459 RefEdge edgeY = itrYhrn.next();
460 HeapRegionNode referencee = edgeY.getDst();
461 RefEdge edgeNew = edgeY.copy();
463 if( !isSuperiorType(x.getType(), edgeY.getType() ) ) {
464 impossibleEdges.add(edgeY);
470 if( tdCast == null ) {
471 edgeNew.setType(mostSpecificType(y.getType(),
477 edgeNew.setType(mostSpecificType(y.getType(),
479 referencee.getType(),
485 edgeNew.setField(null);
487 addRefEdge(lnX, referencee, edgeNew);
490 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
491 while( itrImp.hasNext() ) {
492 RefEdge edgeImp = itrImp.next();
493 removeRefEdge(edgeImp);
498 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
501 FlatNode currentProgramPoint,
502 Set<EdgeKey> edgeKeysForLoad
505 VariableNode lnX = getVariableNodeFromTemp(x);
506 VariableNode lnY = getVariableNodeFromTemp(y);
508 clearRefEdgesFrom(lnX, null, null, true);
510 // note it is possible that the types of temps in the
511 // flat node to analyze will reveal that some typed
512 // edges in the reachability graph are impossible
513 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
515 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
516 while( itrYhrn.hasNext() ) {
517 RefEdge edgeY = itrYhrn.next();
518 HeapRegionNode hrnY = edgeY.getDst();
519 ReachSet betaY = edgeY.getBeta();
521 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
523 while( itrHrnFhrn.hasNext() ) {
524 RefEdge edgeHrn = itrHrnFhrn.next();
525 HeapRegionNode hrnHrn = edgeHrn.getDst();
526 ReachSet betaHrn = edgeHrn.getBeta();
528 // prune edges that are not a matching field
529 if( edgeHrn.getType() != null &&
530 !edgeHrn.getField().equals(f.getSymbol() )
535 // check for impossible edges
536 if( !isSuperiorType(x.getType(), edgeHrn.getType() ) ) {
537 impossibleEdges.add(edgeHrn);
541 // for definite reach analysis only
542 if( edgeKeysForLoad != null ) {
544 edgeKeysForLoad.add( new EdgeKey( hrnY.getID(),
551 TypeDescriptor tdNewEdge =
552 mostSpecificType(edgeHrn.getType(),
556 TaintSet taints = Canonical.unionORpreds(edgeHrn.getTaints(),
560 // the DFJ way to generate taints changes for field statements
561 taints = Canonical.changeWhereDefined(taints,
562 currentProgramPoint);
565 RefEdge edgeNew = new RefEdge(lnX,
569 Canonical.intersection(betaY, betaHrn),
574 addEdgeOrMergeWithExisting(edgeNew);
578 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
579 while( itrImp.hasNext() ) {
580 RefEdge edgeImp = itrImp.next();
581 removeRefEdge(edgeImp);
584 // anytime you might remove edges between heap regions
585 // you must global sweep to clean up broken reachability
586 if( !impossibleEdges.isEmpty() ) {
587 if( !DISABLE_GLOBAL_SWEEP ) {
595 // return whether a strong update was actually effected
596 public boolean assignTempXFieldFEqualToTempY(TempDescriptor x,
599 FlatNode currentProgramPoint,
600 boolean alreadyReachable,
601 Set<EdgeKey> edgeKeysRemoved,
602 Set<EdgeKey> edgeKeysAdded,
603 Set<DefiniteReachState.FdEntry> edgesToElideFromPropFd
606 VariableNode lnX = getVariableNodeFromTemp(x);
607 VariableNode lnY = getVariableNodeFromTemp(y);
609 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
610 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
612 // note it is possible that the types of temps in the
613 // flat node to analyze will reveal that some typed
614 // edges in the reachability graph are impossible
615 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
617 // first look for possible strong updates and remove those edges
618 boolean strongUpdateCond = false;
619 boolean edgeRemovedByStrongUpdate = false;
621 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
622 while( itrXhrn.hasNext() ) {
623 RefEdge edgeX = itrXhrn.next();
624 HeapRegionNode hrnX = edgeX.getDst();
626 // we can do a strong update here if one of two cases holds
628 f != DisjointAnalysis.getArrayField(f.getType() ) &&
629 ( (hrnX.getNumReferencers() == 1) || // case 1
630 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
633 if( !DISABLE_STRONG_UPDATES ) {
634 strongUpdateCond = true;
636 boolean atLeastOne = clearRefEdgesFrom(hrnX,
643 edgeRemovedByStrongUpdate = true;
650 // definite reachability analysis can elide some edges from
651 // propagating reach information
652 Set<RefEdge> edgesToElideFromProp = null;
653 if( edgesToElideFromPropFd != null ) {
654 edgesToElideFromProp = new HashSet<RefEdge>();
655 Iterator<RefEdge> itrY = lnY.iteratorToReferencees();
656 while( itrY.hasNext() ) {
657 HeapRegionNode hrnSrc = itrY.next().getDst();
659 Iterator<RefEdge> itrhrn = hrnSrc.iteratorToReferencees();
660 while( itrhrn.hasNext() ) {
661 RefEdge edgeToElide = itrhrn.next();
662 String f0 = edgeToElide.getField();
663 HeapRegionNode hrnDst = edgeToElide.getDst();
665 // does this graph edge match a statically-named edge
666 // that def reach says we don't have to prop over?
667 for( DefiniteReachState.FdEntry entry : edgesToElideFromPropFd ) {
668 if( !entry.f0.getSymbol().equals( f0 ) ) {
671 boolean refByZ = false;
672 Iterator<RefEdge> itrRef = hrnDst.iteratorToReferencers();
673 while( itrRef.hasNext() ) {
674 RefEdge edgeZ = itrRef.next();
675 if( edgeZ.getSrc() instanceof VariableNode ) {
676 VariableNode vnZ = (VariableNode) edgeZ.getSrc();
677 if( vnZ.getTempDescriptor().equals( entry.z ) ) {
684 // this graph edge matches the def reach edge, mark it for
686 edgesToElideFromProp.add( edgeToElide );
695 // definite reachability analysis can elide reachability propagation
696 if( !alreadyReachable ) {
698 // then do all token propagation
699 itrXhrn = lnX.iteratorToReferencees();
700 while( itrXhrn.hasNext() ) {
701 RefEdge edgeX = itrXhrn.next();
702 HeapRegionNode hrnX = edgeX.getDst();
703 ReachSet betaX = edgeX.getBeta();
704 ReachSet R = Canonical.intersection(hrnX.getAlpha(),
708 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
709 while( itrYhrn.hasNext() ) {
710 RefEdge edgeY = itrYhrn.next();
711 HeapRegionNode hrnY = edgeY.getDst();
712 ReachSet O = edgeY.getBeta();
714 // check for impossible edges
715 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
716 impossibleEdges.add(edgeY);
720 // propagate tokens over nodes starting from hrnSrc, and it will
721 // take care of propagating back up edges from any touched nodes
722 ChangeSet Cy = Canonical.unionUpArityToChangeSet(O, R);
723 propagateTokensOverNodes( hrnY,
727 edgesToElideFromProp );
729 // then propagate back just up the edges from hrn
730 ChangeSet Cx = Canonical.unionUpArityToChangeSet(R, O);
731 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
733 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
734 new Hashtable<RefEdge, ChangeSet>();
736 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
737 while( referItr.hasNext() ) {
738 RefEdge edgeUpstream = referItr.next();
739 todoEdges.add(edgeUpstream);
740 edgePlannedChanges.put(edgeUpstream, Cx);
743 propagateTokensOverEdges( todoEdges,
746 edgesToElideFromProp );
752 // apply the updates to reachability
753 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
754 while( nodeItr.hasNext() ) {
755 nodeItr.next().applyAlphaNew();
758 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
759 while( edgeItr.hasNext() ) {
760 edgeItr.next().applyBetaNew();
764 // then go back through and add the new edges
765 itrXhrn = lnX.iteratorToReferencees();
766 while( itrXhrn.hasNext() ) {
767 RefEdge edgeX = itrXhrn.next();
768 HeapRegionNode hrnX = edgeX.getDst();
770 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
771 while( itrYhrn.hasNext() ) {
772 RefEdge edgeY = itrYhrn.next();
773 HeapRegionNode hrnY = edgeY.getDst();
775 // skip impossible edges here, we already marked them
776 // when computing reachability propagations above
777 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
782 // for definite reach analysis only
783 if( edgeKeysAdded != null ) {
785 edgeKeysAdded.add( new EdgeKey( hrnX.getID(),
793 // prepare the new reference edge hrnX.f -> hrnY
794 TypeDescriptor tdNewEdge =
795 mostSpecificType(y.getType(),
800 TaintSet taints = edgeY.getTaints();
803 // the DFJ way to generate taints changes for field statements
804 taints = Canonical.changeWhereDefined(taints,
805 currentProgramPoint);
810 if( alreadyReachable ) {
811 betaNew = edgeY.getBeta();
813 betaNew = Canonical.pruneBy( edgeY.getBeta(),
823 Canonical.changePredsTo( betaNew,
829 addEdgeOrMergeWithExisting(edgeNew);
833 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
834 while( itrImp.hasNext() ) {
835 RefEdge edgeImp = itrImp.next();
836 removeRefEdge(edgeImp);
839 // if there was a strong update, make sure to improve
840 // reachability with a global sweep
841 if( edgeRemovedByStrongUpdate || !impossibleEdges.isEmpty() ) {
842 if( !DISABLE_GLOBAL_SWEEP ) {
847 return edgeRemovedByStrongUpdate;
851 public void assignReturnEqualToTemp(TempDescriptor x) {
853 VariableNode lnR = getVariableNodeFromTemp(tdReturn);
854 VariableNode lnX = getVariableNodeFromTemp(x);
856 clearRefEdgesFrom(lnR, null, null, true);
858 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
859 while( itrXhrn.hasNext() ) {
860 RefEdge edgeX = itrXhrn.next();
861 HeapRegionNode referencee = edgeX.getDst();
862 RefEdge edgeNew = edgeX.copy();
864 edgeNew.setTaints(Canonical.changePredsTo(edgeNew.getTaints(),
869 addRefEdge(lnR, referencee, edgeNew);
874 public void assignTempEqualToNewAlloc(TempDescriptor x,
881 // after the age operation the newest (or zero-ith oldest)
882 // node associated with the allocation site should have
883 // no references to it as if it were a newly allocated
885 Integer idNewest = as.getIthOldest(0);
886 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
887 assert hrnNewest != null;
889 VariableNode lnX = getVariableNodeFromTemp(x);
890 clearRefEdgesFrom(lnX, null, null, true);
892 // make a new reference to allocated node
893 TypeDescriptor type = as.getType();
896 new RefEdge(lnX, // source
900 hrnNewest.getAlpha(), // beta
901 predsTrue, // predicates
902 TaintSet.factory() // taints
905 addRefEdge(lnX, hrnNewest, edgeNew);
909 // use the allocation site (unique to entire analysis) to
910 // locate the heap region nodes in this reachability graph
911 // that should be aged. The process models the allocation
912 // of new objects and collects all the oldest allocations
913 // in a summary node to allow for a finite analysis
915 // There is an additional property of this method. After
916 // running it on a particular reachability graph (many graphs
917 // may have heap regions related to the same allocation site)
918 // the heap region node objects in this reachability graph will be
919 // allocated. Therefore, after aging a graph for an allocation
920 // site, attempts to retrieve the heap region nodes using the
921 // integer id's contained in the allocation site should always
922 // return non-null heap regions.
923 public void age(AllocSite as) {
925 // keep track of allocation sites that are represented
926 // in this graph for efficiency with other operations
929 // if there is a k-th oldest node, it merges into
931 Integer idK = as.getOldest();
932 if( id2hrn.containsKey(idK) ) {
933 HeapRegionNode hrnK = id2hrn.get(idK);
935 // retrieve the summary node, or make it
937 HeapRegionNode hrnSummary = getSummaryNode(as, false);
939 mergeIntoSummary(hrnK, hrnSummary);
942 // move down the line of heap region nodes
943 // clobbering the ith and transferring all references
944 // to and from i-1 to node i.
945 for( int i = allocationDepth - 1; i > 0; --i ) {
947 // only do the transfer if the i-1 node exists
948 Integer idImin1th = as.getIthOldest(i - 1);
949 if( id2hrn.containsKey(idImin1th) ) {
950 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
951 if( hrnImin1.isWiped() ) {
952 // there is no info on this node, just skip
956 // either retrieve or make target of transfer
957 HeapRegionNode hrnI = getIthNode(as, i, false);
959 transferOnto(hrnImin1, hrnI);
964 // as stated above, the newest node should have had its
965 // references moved over to the second oldest, so we wipe newest
966 // in preparation for being the new object to assign something to
967 HeapRegionNode hrn0 = getIthNode(as, 0, false);
970 // now tokens in reachability sets need to "age" also
971 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
972 while( itrAllHRNodes.hasNext() ) {
973 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
974 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
976 ageTuplesFrom(as, hrnToAge);
978 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
979 while( itrEdges.hasNext() ) {
980 ageTuplesFrom(as, itrEdges.next() );
985 // after tokens have been aged, reset newest node's reachability
986 // and a brand new node has a "true" predicate
987 hrn0.setAlpha( Canonical.changePredsTo( hrn0.getInherent(), predsTrue ) );
988 hrn0.setPreds( predsTrue);
992 // either retrieve or create the needed heap region node
993 protected HeapRegionNode getSummaryNode(AllocSite as,
998 idSummary = as.getSummaryShadow();
1000 idSummary = as.getSummary();
1003 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
1005 if( hrnSummary == null ) {
1007 String strDesc = as.toStringForDOT()+"\\nsummary";
1010 createNewHeapRegionNode(idSummary, // id or null to generate a new one
1011 false, // single object?
1013 false, // out-of-context?
1014 as.getType(), // type
1015 as, // allocation site
1016 null, // inherent reach
1017 null, // current reach
1018 predsEmpty, // predicates
1019 strDesc // description
1026 // either retrieve or create the needed heap region node
1027 protected HeapRegionNode getIthNode(AllocSite as,
1033 idIth = as.getIthOldestShadow(i);
1035 idIth = as.getIthOldest(i);
1038 HeapRegionNode hrnIth = id2hrn.get(idIth);
1040 if( hrnIth == null ) {
1042 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
1044 hrnIth = createNewHeapRegionNode(idIth, // id or null to generate a new one
1045 true, // single object?
1047 false, // out-of-context?
1048 as.getType(), // type
1049 as, // allocation site
1050 null, // inherent reach
1051 null, // current reach
1052 predsEmpty, // predicates
1053 strDesc // description
1061 protected void mergeIntoSummary(HeapRegionNode hrn,
1062 HeapRegionNode hrnSummary) {
1063 assert hrnSummary.isNewSummary();
1065 // assert that these nodes belong to THIS graph
1066 assert belongsToThis(hrn);
1067 assert belongsToThis(hrnSummary);
1069 assert hrn != hrnSummary;
1071 // transfer references _from_ hrn over to hrnSummary
1072 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
1073 while( itrReferencee.hasNext() ) {
1074 RefEdge edge = itrReferencee.next();
1075 RefEdge edgeMerged = edge.copy();
1076 edgeMerged.setSrc(hrnSummary);
1078 HeapRegionNode hrnReferencee = edge.getDst();
1079 RefEdge edgeSummary =
1080 hrnSummary.getReferenceTo(hrnReferencee,
1085 if( edgeSummary == null ) {
1086 // the merge is trivial, nothing to be done
1087 addRefEdge(hrnSummary, hrnReferencee, edgeMerged);
1090 // otherwise an edge from the referencer to hrnSummary exists already
1091 // and the edge referencer->hrn should be merged with it
1092 edgeSummary.setBeta(
1093 Canonical.unionORpreds(edgeMerged.getBeta(),
1094 edgeSummary.getBeta()
1097 edgeSummary.setPreds(
1098 Canonical.join(edgeMerged.getPreds(),
1099 edgeSummary.getPreds()
1105 // next transfer references _to_ hrn over to hrnSummary
1106 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
1107 while( itrReferencer.hasNext() ) {
1108 RefEdge edge = itrReferencer.next();
1109 RefEdge edgeMerged = edge.copy();
1110 edgeMerged.setDst(hrnSummary);
1112 RefSrcNode onReferencer = edge.getSrc();
1113 RefEdge edgeSummary =
1114 onReferencer.getReferenceTo(hrnSummary,
1119 if( edgeSummary == null ) {
1120 // the merge is trivial, nothing to be done
1121 addRefEdge(onReferencer, hrnSummary, edgeMerged);
1124 // otherwise an edge from the referencer to alpha_S exists already
1125 // and the edge referencer->alpha_K should be merged with it
1126 edgeSummary.setBeta(
1127 Canonical.unionORpreds(edgeMerged.getBeta(),
1128 edgeSummary.getBeta()
1131 edgeSummary.setPreds(
1132 Canonical.join(edgeMerged.getPreds(),
1133 edgeSummary.getPreds()
1139 // then merge hrn reachability into hrnSummary
1140 hrnSummary.setAlpha(
1141 Canonical.unionORpreds(hrnSummary.getAlpha(),
1146 hrnSummary.setPreds(
1147 Canonical.join(hrnSummary.getPreds(),
1152 // and afterward, this node is gone
1157 protected void transferOnto(HeapRegionNode hrnA,
1158 HeapRegionNode hrnB) {
1160 assert belongsToThis(hrnA);
1161 assert belongsToThis(hrnB);
1162 assert hrnA != hrnB;
1164 // clear references in and out of node b?
1165 assert hrnB.isWiped();
1167 // copy each: (edge in and out of A) to B
1168 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
1169 while( itrReferencee.hasNext() ) {
1170 RefEdge edge = itrReferencee.next();
1171 HeapRegionNode hrnReferencee = edge.getDst();
1172 RefEdge edgeNew = edge.copy();
1173 edgeNew.setSrc(hrnB);
1174 edgeNew.setDst(hrnReferencee);
1176 addRefEdge(hrnB, hrnReferencee, edgeNew);
1179 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
1180 while( itrReferencer.hasNext() ) {
1181 RefEdge edge = itrReferencer.next();
1182 RefSrcNode rsnReferencer = edge.getSrc();
1183 RefEdge edgeNew = edge.copy();
1184 edgeNew.setSrc(rsnReferencer);
1185 edgeNew.setDst(hrnB);
1187 addRefEdge(rsnReferencer, hrnB, edgeNew);
1190 // replace hrnB reachability and preds with hrnA's
1191 hrnB.setAlpha(hrnA.getAlpha() );
1192 hrnB.setPreds(hrnA.getPreds() );
1194 // after transfer, wipe out source
1195 wipeOut(hrnA, true);
1199 // the purpose of this method is to conceptually "wipe out"
1200 // a heap region from the graph--purposefully not called REMOVE
1201 // because the node is still hanging around in the graph, just
1202 // not mechanically connected or have any reach or predicate
1203 // information on it anymore--lots of ops can use this
1204 protected void wipeOut(HeapRegionNode hrn,
1205 boolean wipeVariableReferences) {
1207 assert belongsToThis(hrn);
1209 clearRefEdgesFrom(hrn, null, null, true);
1211 if( wipeVariableReferences ) {
1212 clearRefEdgesTo(hrn, null, null, true);
1214 clearNonVarRefEdgesTo(hrn);
1217 hrn.setAlpha(rsetEmpty);
1218 hrn.setPreds(predsEmpty);
1222 protected void ageTuplesFrom(AllocSite as, RefEdge edge) {
1224 Canonical.ageTuplesFrom(edge.getBeta(),
1230 protected void ageTuplesFrom(AllocSite as, HeapRegionNode hrn) {
1232 Canonical.ageTuplesFrom(hrn.getAlpha(),
1240 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1242 HashSet<HeapRegionNode> nodesWithNewAlpha,
1243 HashSet<RefEdge> edgesWithNewBeta,
1244 Set<RefEdge> edgesToElideProp ) {
1246 HashSet<HeapRegionNode> todoNodes
1247 = new HashSet<HeapRegionNode>();
1248 todoNodes.add(nPrime);
1250 HashSet<RefEdge> todoEdges
1251 = new HashSet<RefEdge>();
1253 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1254 = new Hashtable<HeapRegionNode, ChangeSet>();
1255 nodePlannedChanges.put(nPrime, c0);
1257 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1258 = new Hashtable<RefEdge, ChangeSet>();
1260 // first propagate change sets everywhere they can go
1261 while( !todoNodes.isEmpty() ) {
1262 HeapRegionNode n = todoNodes.iterator().next();
1263 ChangeSet C = nodePlannedChanges.get(n);
1265 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1266 while( referItr.hasNext() ) {
1267 RefEdge edge = referItr.next();
1269 if( edgesToElideProp != null && edgesToElideProp.contains( edge ) ) {
1272 todoEdges.add(edge);
1274 if( !edgePlannedChanges.containsKey(edge) ) {
1275 edgePlannedChanges.put(edge,
1280 edgePlannedChanges.put(edge,
1281 Canonical.union(edgePlannedChanges.get(edge),
1287 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1288 while( refeeItr.hasNext() ) {
1289 RefEdge edgeF = refeeItr.next();
1291 if( edgesToElideProp != null && edgesToElideProp.contains( edgeF ) ) {
1295 HeapRegionNode m = edgeF.getDst();
1297 ChangeSet changesToPass = ChangeSet.factory();
1299 Iterator<ChangeTuple> itrCprime = C.iterator();
1300 while( itrCprime.hasNext() ) {
1301 ChangeTuple c = itrCprime.next();
1302 if( edgeF.getBeta().containsIgnorePreds(c.getStateToMatch() )
1305 changesToPass = Canonical.add(changesToPass, c);
1309 if( !changesToPass.isEmpty() ) {
1310 if( !nodePlannedChanges.containsKey(m) ) {
1311 nodePlannedChanges.put(m, ChangeSet.factory() );
1314 ChangeSet currentChanges = nodePlannedChanges.get(m);
1316 if( !changesToPass.isSubset(currentChanges) ) {
1318 nodePlannedChanges.put(m,
1319 Canonical.union(currentChanges,
1328 todoNodes.remove(n);
1331 // then apply all of the changes for each node at once
1332 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1333 while( itrMap.hasNext() ) {
1334 Map.Entry me = (Map.Entry)itrMap.next();
1335 HeapRegionNode n = (HeapRegionNode) me.getKey();
1336 ChangeSet C = (ChangeSet) me.getValue();
1338 // this propagation step is with respect to one change,
1339 // so we capture the full change from the old alpha:
1340 ReachSet localDelta = Canonical.applyChangeSet(n.getAlpha(),
1344 // but this propagation may be only one of many concurrent
1345 // possible changes, so keep a running union with the node's
1346 // partially updated new alpha set
1347 n.setAlphaNew(Canonical.unionORpreds(n.getAlphaNew(),
1352 nodesWithNewAlpha.add(n);
1355 propagateTokensOverEdges(todoEdges,
1362 protected void propagateTokensOverEdges(HashSet <RefEdge> todoEdges,
1363 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1364 HashSet <RefEdge> edgesWithNewBeta,
1365 Set<RefEdge> edgesToElideProp ) {
1367 // first propagate all change tuples everywhere they can go
1368 while( !todoEdges.isEmpty() ) {
1369 RefEdge edgeE = todoEdges.iterator().next();
1370 todoEdges.remove(edgeE);
1372 if( !edgePlannedChanges.containsKey(edgeE) ) {
1373 edgePlannedChanges.put(edgeE,
1378 ChangeSet C = edgePlannedChanges.get(edgeE);
1380 ChangeSet changesToPass = ChangeSet.factory();
1382 Iterator<ChangeTuple> itrC = C.iterator();
1383 while( itrC.hasNext() ) {
1384 ChangeTuple c = itrC.next();
1385 if( edgeE.getBeta().containsIgnorePreds(c.getStateToMatch() )
1388 changesToPass = Canonical.add(changesToPass, c);
1392 RefSrcNode rsn = edgeE.getSrc();
1394 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1395 HeapRegionNode n = (HeapRegionNode) rsn;
1397 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1398 while( referItr.hasNext() ) {
1399 RefEdge edgeF = referItr.next();
1401 if( edgesToElideProp != null && edgesToElideProp.contains( edgeF ) ) {
1405 if( !edgePlannedChanges.containsKey(edgeF) ) {
1406 edgePlannedChanges.put(edgeF,
1411 ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
1413 if( !changesToPass.isSubset(currentChanges) ) {
1414 todoEdges.add(edgeF);
1415 edgePlannedChanges.put(edgeF,
1416 Canonical.union(currentChanges,
1425 // then apply all of the changes for each edge at once
1426 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1427 while( itrMap.hasNext() ) {
1428 Map.Entry me = (Map.Entry)itrMap.next();
1429 RefEdge e = (RefEdge) me.getKey();
1430 ChangeSet C = (ChangeSet) me.getValue();
1432 // this propagation step is with respect to one change,
1433 // so we capture the full change from the old beta:
1434 ReachSet localDelta =
1435 Canonical.applyChangeSet(e.getBeta(),
1440 // but this propagation may be only one of many concurrent
1441 // possible changes, so keep a running union with the edge's
1442 // partially updated new beta set
1443 e.setBetaNew(Canonical.unionORpreds(e.getBetaNew(),
1448 edgesWithNewBeta.add(e);
1453 public void taintInSetVars(FlatSESEEnterNode sese) {
1455 Iterator<TempDescriptor> isvItr = sese.getInVarSet().iterator();
1456 while( isvItr.hasNext() ) {
1457 TempDescriptor isv = isvItr.next();
1459 // use this where defined flatnode to support RCR/DFJ
1460 FlatNode whereDefined = null;
1462 // in-set var taints should NOT propagate back into callers
1463 // so give it FALSE(EMPTY) predicates
1473 public void taintStallSite(FlatNode stallSite,
1474 TempDescriptor var) {
1476 // use this where defined flatnode to support RCR/DFJ
1477 FlatNode whereDefined = null;
1479 // stall site taint should propagate back into callers
1480 // so give it TRUE predicates
1489 protected void taintTemp(FlatSESEEnterNode sese,
1492 FlatNode whereDefined,
1496 VariableNode vn = getVariableNodeFromTemp(var);
1498 Iterator<RefEdge> reItr = vn.iteratorToReferencees();
1499 while( reItr.hasNext() ) {
1500 RefEdge re = reItr.next();
1502 Taint taint = Taint.factory(sese,
1505 re.getDst().getAllocSite(),
1510 re.setTaints(Canonical.add(re.getTaints(),
1517 public void removeInContextTaints(FlatSESEEnterNode sese) {
1519 Iterator meItr = id2hrn.entrySet().iterator();
1520 while( meItr.hasNext() ) {
1521 Map.Entry me = (Map.Entry)meItr.next();
1522 Integer id = (Integer) me.getKey();
1523 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1525 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1526 while( reItr.hasNext() ) {
1527 RefEdge re = reItr.next();
1529 re.setTaints(Canonical.removeInContextTaints(re.getTaints(),
1537 public void removeAllStallSiteTaints() {
1539 Iterator meItr = id2hrn.entrySet().iterator();
1540 while( meItr.hasNext() ) {
1541 Map.Entry me = (Map.Entry)meItr.next();
1542 Integer id = (Integer) me.getKey();
1543 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1545 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1546 while( reItr.hasNext() ) {
1547 RefEdge re = reItr.next();
1549 re.setTaints(Canonical.removeStallSiteTaints(re.getTaints()
1557 // used in makeCalleeView below to decide if there is
1558 // already an appropriate out-of-context edge in a callee
1559 // view graph for merging, or null if a new one will be added
1561 getOutOfContextReferenceTo(HeapRegionNode hrn,
1562 TypeDescriptor srcType,
1563 TypeDescriptor refType,
1565 assert belongsToThis(hrn);
1567 HeapRegionNode hrnInContext = id2hrn.get(hrn.getID() );
1568 if( hrnInContext == null ) {
1572 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1573 while( refItr.hasNext() ) {
1574 RefEdge re = refItr.next();
1576 assert belongsToThis(re.getSrc() );
1577 assert belongsToThis(re.getDst() );
1579 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1583 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1584 if( !hrnSrc.isOutOfContext() ) {
1588 if( srcType == null ) {
1589 if( hrnSrc.getType() != null ) {
1593 if( !srcType.equals(hrnSrc.getType() ) ) {
1598 if( !re.typeEquals(refType) ) {
1602 if( !re.fieldEquals(refField) ) {
1606 // tada! We found it!
1613 // used below to convert a ReachSet to its callee-context
1614 // equivalent with respect to allocation sites in this graph
1615 protected ReachSet toCalleeContext(ReachSet rs,
1616 ExistPredSet predsNodeOrEdge,
1617 Set<HrnIdOoc> oocHrnIdOoc2callee
1619 ReachSet out = ReachSet.factory();
1621 Iterator<ReachState> itr = rs.iterator();
1622 while( itr.hasNext() ) {
1623 ReachState stateCaller = itr.next();
1625 ReachState stateCallee = stateCaller;
1627 Iterator<AllocSite> asItr = allocSites.iterator();
1628 while( asItr.hasNext() ) {
1629 AllocSite as = asItr.next();
1631 ReachState stateNew = ReachState.factory();
1632 Iterator<ReachTuple> rtItr = stateCallee.iterator();
1633 while( rtItr.hasNext() ) {
1634 ReachTuple rt = rtItr.next();
1636 // only translate this tuple if it is
1637 // in the out-callee-context bag
1638 HrnIdOoc hio = new HrnIdOoc(rt.getHrnID(),
1641 if( !oocHrnIdOoc2callee.contains(hio) ) {
1642 stateNew = Canonical.addUpArity(stateNew, rt);
1646 int age = as.getAgeCategory(rt.getHrnID() );
1648 // this is the current mapping, where 0, 1, 2S were allocated
1649 // in the current context, 0?, 1? and 2S? were allocated in a
1650 // previous context, and we're translating to a future context
1662 if( age == AllocSite.AGE_notInThisSite ) {
1663 // things not from the site just go back in
1664 stateNew = Canonical.addUpArity(stateNew, rt);
1666 } else if( age == AllocSite.AGE_summary ||
1670 stateNew = Canonical.addUpArity(stateNew,
1671 ReachTuple.factory(as.getSummary(),
1674 true // out-of-context
1679 // otherwise everything else just goes to an out-of-context
1680 // version, everything else the same
1681 Integer I = as.getAge(rt.getHrnID() );
1684 assert !rt.isMultiObject();
1686 stateNew = Canonical.addUpArity(stateNew,
1687 ReachTuple.factory(rt.getHrnID(),
1688 rt.isMultiObject(), // multi
1690 true // out-of-context
1696 stateCallee = stateNew;
1699 // make a predicate of the caller graph element
1700 // and the caller state we just converted
1701 ExistPredSet predsWithState = ExistPredSet.factory();
1703 Iterator<ExistPred> predItr = predsNodeOrEdge.iterator();
1704 while( predItr.hasNext() ) {
1705 ExistPred predNodeOrEdge = predItr.next();
1708 Canonical.add(predsWithState,
1709 ExistPred.factory(predNodeOrEdge.n_hrnID,
1710 predNodeOrEdge.e_tdSrc,
1711 predNodeOrEdge.e_hrnSrcID,
1712 predNodeOrEdge.e_hrnDstID,
1713 predNodeOrEdge.e_type,
1714 predNodeOrEdge.e_field,
1717 predNodeOrEdge.e_srcOutCalleeContext,
1718 predNodeOrEdge.e_srcOutCallerContext
1723 stateCallee = Canonical.changePredsTo(stateCallee,
1726 out = Canonical.add(out,
1730 assert out.isCanonical();
1734 // used below to convert a ReachSet to its caller-context
1735 // equivalent with respect to allocation sites in this graph
1737 toCallerContext(ReachSet rs,
1738 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1740 ReachSet out = ReachSet.factory();
1742 // when the mapping is null it means there were no
1743 // predicates satisfied
1744 if( calleeStatesSatisfied == null ) {
1748 Iterator<ReachState> itr = rs.iterator();
1749 while( itr.hasNext() ) {
1750 ReachState stateCallee = itr.next();
1752 if( calleeStatesSatisfied.containsKey(stateCallee) ) {
1754 // starting from one callee state...
1755 ReachSet rsCaller = ReachSet.factory(stateCallee);
1757 // possibly branch it into many states, which any
1758 // allocation site might do, so lots of derived states
1759 Iterator<AllocSite> asItr = allocSites.iterator();
1760 while( asItr.hasNext() ) {
1761 AllocSite as = asItr.next();
1762 rsCaller = Canonical.toCallerContext(rsCaller, as);
1765 // then before adding each derived, now caller-context
1766 // states to the output, attach the appropriate pred
1767 // based on the source callee state
1768 Iterator<ReachState> stateItr = rsCaller.iterator();
1769 while( stateItr.hasNext() ) {
1770 ReachState stateCaller = stateItr.next();
1771 stateCaller = Canonical.attach(stateCaller,
1772 calleeStatesSatisfied.get(stateCallee)
1774 out = Canonical.add(out,
1781 assert out.isCanonical();
1786 // used below to convert a ReachSet to an equivalent
1787 // version with shadow IDs merged into unshadowed IDs
1788 protected ReachSet unshadow(ReachSet rs) {
1790 Iterator<AllocSite> asItr = allocSites.iterator();
1791 while( asItr.hasNext() ) {
1792 AllocSite as = asItr.next();
1793 out = Canonical.unshadow(out, as);
1795 assert out.isCanonical();
1800 // convert a caller taint set into a callee taint set
1802 toCalleeContext(TaintSet ts,
1803 ExistPredSet predsEdge) {
1805 TaintSet out = TaintSet.factory();
1807 // the idea is easy, the taint identifier itself doesn't
1808 // change at all, but the predicates should be tautology:
1809 // start with the preds passed in from the caller edge
1810 // that host the taints, and alter them to have the taint
1811 // added, just becoming more specific than edge predicate alone
1813 Iterator<Taint> itr = ts.iterator();
1814 while( itr.hasNext() ) {
1815 Taint tCaller = itr.next();
1817 ExistPredSet predsWithTaint = ExistPredSet.factory();
1819 Iterator<ExistPred> predItr = predsEdge.iterator();
1820 while( predItr.hasNext() ) {
1821 ExistPred predEdge = predItr.next();
1824 Canonical.add(predsWithTaint,
1825 ExistPred.factory(predEdge.e_tdSrc,
1826 predEdge.e_hrnSrcID,
1827 predEdge.e_hrnDstID,
1832 predEdge.e_srcOutCalleeContext,
1833 predEdge.e_srcOutCallerContext
1838 Taint tCallee = Canonical.changePredsTo(tCaller,
1841 out = Canonical.add(out,
1846 assert out.isCanonical();
1851 // used below to convert a TaintSet to its caller-context
1852 // equivalent, just eliminate Taints with bad preds
1854 toCallerContext(TaintSet ts,
1855 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied
1858 TaintSet out = TaintSet.factory();
1860 // when the mapping is null it means there were no
1861 // predicates satisfied
1862 if( calleeTaintsSatisfied == null ) {
1866 Iterator<Taint> itr = ts.iterator();
1867 while( itr.hasNext() ) {
1868 Taint tCallee = itr.next();
1870 if( calleeTaintsSatisfied.containsKey(tCallee) ) {
1873 Canonical.attach(Taint.factory(tCallee.sese,
1878 ExistPredSet.factory() ),
1879 calleeTaintsSatisfied.get(tCallee)
1881 out = Canonical.add(out,
1887 assert out.isCanonical();
1894 // use this method to make a new reach graph that is
1895 // what heap the FlatMethod callee from the FlatCall
1896 // would start with reaching from its arguments in
1899 makeCalleeView(FlatCall fc,
1900 FlatMethod fmCallee,
1901 Set<Integer> callerNodeIDsCopiedToCallee,
1902 boolean writeDebugDOTs
1906 // first traverse this context to find nodes and edges
1907 // that will be callee-reachable
1908 Set<HeapRegionNode> reachableCallerNodes =
1909 new HashSet<HeapRegionNode>();
1911 // caller edges between callee-reachable nodes
1912 Set<RefEdge> reachableCallerEdges =
1913 new HashSet<RefEdge>();
1915 // caller edges from arg vars, and the matching param index
1916 // because these become a special edge in callee
1917 // NOTE! One argument may be passed in as more than one parameter,
1918 // so map to a set of parameter indices!
1919 Hashtable< RefEdge, Set<Integer> > reachableCallerArgEdges2paramIndices =
1920 new Hashtable< RefEdge, Set<Integer> >();
1922 // caller edges from local vars or callee-unreachable nodes
1923 // (out-of-context sources) to callee-reachable nodes
1924 Set<RefEdge> oocCallerEdges =
1925 new HashSet<RefEdge>();
1928 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1930 TempDescriptor tdArg = fc.getArgMatchingParamIndex(fmCallee, i);
1931 VariableNode vnArgCaller = this.getVariableNodeFromTemp(tdArg);
1933 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1934 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1936 toVisitInCaller.add(vnArgCaller);
1938 while( !toVisitInCaller.isEmpty() ) {
1939 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1940 toVisitInCaller.remove(rsnCaller);
1941 visitedInCaller.add(rsnCaller);
1943 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1944 while( itrRefEdges.hasNext() ) {
1945 RefEdge reCaller = itrRefEdges.next();
1946 HeapRegionNode hrnCaller = reCaller.getDst();
1948 callerNodeIDsCopiedToCallee.add(hrnCaller.getID() );
1949 reachableCallerNodes.add(hrnCaller);
1951 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1952 reachableCallerEdges.add(reCaller);
1955 if( rsnCaller.equals(vnArgCaller) ) {
1956 Set<Integer> pIndices =
1957 reachableCallerArgEdges2paramIndices.get( reCaller );
1959 if( pIndices == null ) {
1960 pIndices = new HashSet<Integer>();
1961 reachableCallerArgEdges2paramIndices.put( reCaller, pIndices );
1966 oocCallerEdges.add(reCaller);
1970 if( !visitedInCaller.contains(hrnCaller) ) {
1971 toVisitInCaller.add(hrnCaller);
1974 } // end edge iteration
1975 } // end visiting heap nodes in caller
1976 } // end iterating over parameters as starting points
1980 // now collect out-of-callee-context IDs and
1981 // map them to whether the ID is out of the caller
1983 Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1985 Iterator<Integer> itrInContext =
1986 callerNodeIDsCopiedToCallee.iterator();
1987 while( itrInContext.hasNext() ) {
1988 Integer hrnID = itrInContext.next();
1989 HeapRegionNode hrnCallerAndInContext = id2hrn.get(hrnID);
1991 Iterator<RefEdge> itrMightCross =
1992 hrnCallerAndInContext.iteratorToReferencers();
1993 while( itrMightCross.hasNext() ) {
1994 RefEdge edgeMightCross = itrMightCross.next();
1996 RefSrcNode rsnCallerAndOutContext =
1997 edgeMightCross.getSrc();
1999 if( rsnCallerAndOutContext instanceof VariableNode ) {
2000 // variables do not have out-of-context reach states,
2002 oocCallerEdges.add(edgeMightCross);
2006 HeapRegionNode hrnCallerAndOutContext =
2007 (HeapRegionNode) rsnCallerAndOutContext;
2009 // is this source node out-of-context?
2010 if( callerNodeIDsCopiedToCallee.contains(hrnCallerAndOutContext.getID() ) ) {
2011 // no, skip this edge
2016 oocCallerEdges.add(edgeMightCross);
2018 // add all reach tuples on the node to list
2019 // of things that are out-of-context: insight
2020 // if this node is reachable from someting that WAS
2021 // in-context, then this node should already be in-context
2022 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
2023 while( stateItr.hasNext() ) {
2024 ReachState state = stateItr.next();
2026 Iterator<ReachTuple> rtItr = state.iterator();
2027 while( rtItr.hasNext() ) {
2028 ReachTuple rt = rtItr.next();
2030 oocHrnIdOoc2callee.add(new HrnIdOoc(rt.getHrnID(),
2039 // the callee view is a new graph: DON'T MODIFY *THIS* graph
2040 ReachGraph rg = new ReachGraph();
2042 // add nodes to callee graph
2043 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
2044 while( hrnItr.hasNext() ) {
2045 HeapRegionNode hrnCaller = hrnItr.next();
2047 assert callerNodeIDsCopiedToCallee.contains(hrnCaller.getID() );
2048 assert !rg.id2hrn.containsKey(hrnCaller.getID() );
2050 ExistPred pred = ExistPred.factory(hrnCaller.getID(), null);
2051 ExistPredSet preds = ExistPredSet.factory(pred);
2053 rg.createNewHeapRegionNode(hrnCaller.getID(),
2054 hrnCaller.isSingleObject(),
2055 hrnCaller.isNewSummary(),
2056 false, // out-of-context?
2057 hrnCaller.getType(),
2058 hrnCaller.getAllocSite(),
2059 toCalleeContext(hrnCaller.getInherent(),
2063 toCalleeContext(hrnCaller.getAlpha(),
2068 hrnCaller.getDescription()
2072 // add param edges to callee graph
2074 reachableCallerArgEdges2paramIndices.entrySet().iterator();
2075 while( argEdges.hasNext() ) {
2076 Map.Entry me = (Map.Entry) argEdges.next();
2077 RefEdge reArg = (RefEdge) me.getKey();
2078 Set<Integer> pInxs = (Set<Integer>) me.getValue();
2080 VariableNode vnCaller = (VariableNode) reArg.getSrc();
2081 TempDescriptor argCaller = vnCaller.getTempDescriptor();
2083 HeapRegionNode hrnDstCaller = reArg.getDst();
2084 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2085 assert hrnDstCallee != null;
2088 ExistPred.factory(argCaller,
2090 hrnDstCallee.getID(),
2095 true, // out-of-callee-context
2096 false // out-of-caller-context
2099 ExistPredSet preds =
2100 ExistPredSet.factory(pred);
2102 for( Integer index: pInxs ) {
2104 TempDescriptor paramCallee = fmCallee.getParameter(index);
2105 VariableNode vnCallee = rg.getVariableNodeFromTemp(paramCallee);
2108 new RefEdge(vnCallee,
2112 toCalleeContext(reArg.getBeta(),
2117 toCalleeContext(reArg.getTaints(),
2121 rg.addRefEdge(vnCallee,
2128 // add in-context edges to callee graph
2129 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
2130 while( reItr.hasNext() ) {
2131 RefEdge reCaller = reItr.next();
2132 RefSrcNode rsnCaller = reCaller.getSrc();
2133 assert rsnCaller instanceof HeapRegionNode;
2134 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2135 HeapRegionNode hrnDstCaller = reCaller.getDst();
2137 HeapRegionNode hrnSrcCallee = rg.id2hrn.get(hrnSrcCaller.getID() );
2138 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2139 assert hrnSrcCallee != null;
2140 assert hrnDstCallee != null;
2143 ExistPred.factory(null,
2144 hrnSrcCallee.getID(),
2145 hrnDstCallee.getID(),
2147 reCaller.getField(),
2150 false, // out-of-callee-context
2151 false // out-of-caller-context
2154 ExistPredSet preds =
2155 ExistPredSet.factory(pred);
2158 new RefEdge(hrnSrcCallee,
2161 reCaller.getField(),
2162 toCalleeContext(reCaller.getBeta(),
2167 toCalleeContext(reCaller.getTaints(),
2171 rg.addRefEdge(hrnSrcCallee,
2177 // add out-of-context edges to callee graph
2178 reItr = oocCallerEdges.iterator();
2179 while( reItr.hasNext() ) {
2180 RefEdge reCaller = reItr.next();
2181 RefSrcNode rsnCaller = reCaller.getSrc();
2182 HeapRegionNode hrnDstCaller = reCaller.getDst();
2183 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2184 assert hrnDstCallee != null;
2186 TypeDescriptor oocNodeType;
2188 TempDescriptor oocPredSrcTemp = null;
2189 Integer oocPredSrcID = null;
2190 boolean outOfCalleeContext;
2191 boolean outOfCallerContext;
2193 if( rsnCaller instanceof VariableNode ) {
2194 VariableNode vnCaller = (VariableNode) rsnCaller;
2196 oocReach = rsetEmpty;
2197 oocPredSrcTemp = vnCaller.getTempDescriptor();
2198 outOfCalleeContext = true;
2199 outOfCallerContext = false;
2202 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2203 assert !callerNodeIDsCopiedToCallee.contains(hrnSrcCaller.getID() );
2204 oocNodeType = hrnSrcCaller.getType();
2205 oocReach = hrnSrcCaller.getAlpha();
2206 oocPredSrcID = hrnSrcCaller.getID();
2207 if( hrnSrcCaller.isOutOfContext() ) {
2208 outOfCalleeContext = false;
2209 outOfCallerContext = true;
2211 outOfCalleeContext = true;
2212 outOfCallerContext = false;
2217 ExistPred.factory(oocPredSrcTemp,
2219 hrnDstCallee.getID(),
2221 reCaller.getField(),
2228 ExistPredSet preds =
2229 ExistPredSet.factory(pred);
2231 RefEdge oocEdgeExisting =
2232 rg.getOutOfContextReferenceTo(hrnDstCallee,
2238 if( oocEdgeExisting == null ) {
2239 // for consistency, map one out-of-context "identifier"
2240 // to one heap region node id, otherwise no convergence
2241 String oocid = "oocid"+
2243 hrnDstCallee.getIDString()+
2246 reCaller.getField();
2248 Integer oocHrnID = oocid2hrnid.get(oocid);
2250 HeapRegionNode hrnCalleeAndOutContext;
2252 if( oocHrnID == null ) {
2254 hrnCalleeAndOutContext =
2255 rg.createNewHeapRegionNode(null, // ID
2256 false, // single object?
2257 false, // new summary?
2258 true, // out-of-context?
2260 null, // alloc site, shouldn't be used
2261 toCalleeContext(oocReach,
2265 toCalleeContext(oocReach,
2273 oocid2hrnid.put(oocid, hrnCalleeAndOutContext.getID() );
2277 // the mapping already exists, so see if node is there
2278 hrnCalleeAndOutContext = rg.id2hrn.get(oocHrnID);
2280 if( hrnCalleeAndOutContext == null ) {
2282 hrnCalleeAndOutContext =
2283 rg.createNewHeapRegionNode(oocHrnID, // ID
2284 false, // single object?
2285 false, // new summary?
2286 true, // out-of-context?
2288 null, // alloc site, shouldn't be used
2289 toCalleeContext(oocReach,
2293 toCalleeContext(oocReach,
2302 // otherwise it is there, so merge reachability
2303 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2304 toCalleeContext(oocReach,
2313 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2315 rg.addRefEdge(hrnCalleeAndOutContext,
2317 new RefEdge(hrnCalleeAndOutContext,
2320 reCaller.getField(),
2321 toCalleeContext(reCaller.getBeta(),
2326 toCalleeContext(reCaller.getTaints(),
2332 // the out-of-context edge already exists
2333 oocEdgeExisting.setBeta(Canonical.unionORpreds(oocEdgeExisting.getBeta(),
2334 toCalleeContext(reCaller.getBeta(),
2341 oocEdgeExisting.setPreds(Canonical.join(oocEdgeExisting.getPreds(),
2346 oocEdgeExisting.setTaints(Canonical.unionORpreds(oocEdgeExisting.getTaints(),
2347 toCalleeContext(reCaller.getTaints(),
2353 HeapRegionNode hrnCalleeAndOutContext =
2354 (HeapRegionNode) oocEdgeExisting.getSrc();
2355 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2356 toCalleeContext(oocReach,
2363 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2368 if( writeDebugDOTs ) {
2369 debugGraphPrefix = String.format("call%03d", debugCallSiteVisitCounter);
2370 rg.writeGraph(debugGraphPrefix+"calleeview",
2371 resolveMethodDebugDOTwriteLabels,
2372 resolveMethodDebugDOTselectTemps,
2373 resolveMethodDebugDOTpruneGarbage,
2374 resolveMethodDebugDOThideReach,
2375 resolveMethodDebugDOThideSubsetReach,
2376 resolveMethodDebugDOThidePreds,
2377 resolveMethodDebugDOThideEdgeTaints);
2383 private static Hashtable<String, Integer> oocid2hrnid =
2384 new Hashtable<String, Integer>();
2387 private static boolean resolveMethodDebugDOTwriteLabels = true;
2388 private static boolean resolveMethodDebugDOTselectTemps = true;
2389 private static boolean resolveMethodDebugDOTpruneGarbage = true;
2390 private static boolean resolveMethodDebugDOThideReach = false;
2391 private static boolean resolveMethodDebugDOThideSubsetReach = true;
2392 private static boolean resolveMethodDebugDOThidePreds = false;
2393 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
2395 static String debugGraphPrefix;
2396 static int debugCallSiteVisitCounter;
2397 static int debugCallSiteVisitStartCapture;
2398 static int debugCallSiteNumVisitsToCapture;
2399 static boolean debugCallSiteStopAfter;
2403 resolveMethodCall(FlatCall fc,
2404 FlatMethod fmCallee,
2405 ReachGraph rgCallee,
2406 Set<Integer> callerNodeIDsCopiedToCallee,
2407 boolean writeDebugDOTs
2410 if( writeDebugDOTs ) {
2412 System.out.println(" Writing out visit "+
2413 debugCallSiteVisitCounter+
2414 " to debug call site");
2416 debugGraphPrefix = String.format("call%03d",
2417 debugCallSiteVisitCounter);
2419 rgCallee.writeGraph(debugGraphPrefix+"callee",
2420 resolveMethodDebugDOTwriteLabels,
2421 resolveMethodDebugDOTselectTemps,
2422 resolveMethodDebugDOTpruneGarbage,
2423 resolveMethodDebugDOThideReach,
2424 resolveMethodDebugDOThideSubsetReach,
2425 resolveMethodDebugDOThidePreds,
2426 resolveMethodDebugDOThideEdgeTaints);
2428 writeGraph(debugGraphPrefix+"caller00In",
2429 resolveMethodDebugDOTwriteLabels,
2430 resolveMethodDebugDOTselectTemps,
2431 resolveMethodDebugDOTpruneGarbage,
2432 resolveMethodDebugDOThideReach,
2433 resolveMethodDebugDOThideSubsetReach,
2434 resolveMethodDebugDOThidePreds,
2435 resolveMethodDebugDOThideEdgeTaints,
2436 callerNodeIDsCopiedToCallee);
2441 // method call transfer function steps:
2442 // 1. Use current callee-reachable heap (CRH) to test callee
2443 // predicates and mark what will be coming in.
2444 // 2. Wipe CRH out of caller.
2445 // 3. Transplant marked callee parts in:
2446 // a) bring in nodes
2447 // b) bring in callee -> callee edges
2448 // c) resolve out-of-context -> callee edges
2449 // d) assign return value
2450 // 4. Collapse shadow nodes down
2451 // 5. Global sweep it.
2454 // 1. mark what callee elements have satisfied predicates
2455 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
2456 new Hashtable<HeapRegionNode, ExistPredSet>();
2458 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
2459 new Hashtable<RefEdge, ExistPredSet>();
2461 Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
2462 calleeNode2calleeStatesSatisfied =
2463 new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
2465 Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
2466 calleeEdge2calleeStatesSatisfied =
2467 new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
2469 Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
2470 calleeEdge2calleeTaintsSatisfied =
2471 new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
2473 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
2474 new Hashtable< RefEdge, Set<RefSrcNode> >();
2478 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2479 while( meItr.hasNext() ) {
2480 Map.Entry me = (Map.Entry)meItr.next();
2481 Integer id = (Integer) me.getKey();
2482 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2484 // if a callee element's predicates are satisfied then a set
2485 // of CALLER predicates is returned: they are the predicates
2486 // that the callee element moved into the caller context
2487 // should have, and it is inefficient to find this again later
2488 ExistPredSet predsIfSatis =
2489 hrnCallee.getPreds().isSatisfiedBy(this,
2490 callerNodeIDsCopiedToCallee,
2493 if( predsIfSatis != null ) {
2494 calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
2496 // otherwise don't bother looking at edges to this node
2502 // since the node is coming over, find out which reach
2503 // states on it should come over, too
2504 assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
2506 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2507 while( stateItr.hasNext() ) {
2508 ReachState stateCallee = stateItr.next();
2511 stateCallee.getPreds().isSatisfiedBy(this,
2512 callerNodeIDsCopiedToCallee,
2514 if( predsIfSatis != null ) {
2516 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2517 calleeNode2calleeStatesSatisfied.get(hrnCallee);
2519 if( calleeStatesSatisfied == null ) {
2520 calleeStatesSatisfied =
2521 new Hashtable<ReachState, ExistPredSet>();
2523 calleeNode2calleeStatesSatisfied.put(hrnCallee, calleeStatesSatisfied);
2526 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2530 // then look at edges to the node
2531 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2532 while( reItr.hasNext() ) {
2533 RefEdge reCallee = reItr.next();
2534 RefSrcNode rsnCallee = reCallee.getSrc();
2536 // (caller local variables to in-context heap regions)
2537 // have an (out-of-context heap region -> in-context heap region)
2538 // abstraction in the callEE, so its true we never need to
2539 // look at a (var node -> heap region) edge in callee to bring
2540 // those over for the call site transfer, except for the special
2541 // case of *RETURN var* -> heap region edges.
2542 // What about (param var->heap region)
2543 // edges in callee? They are dealt with below this loop.
2545 if( rsnCallee instanceof VariableNode ) {
2547 // looking for the return-value variable only
2548 VariableNode vnCallee = (VariableNode) rsnCallee;
2549 if( vnCallee.getTempDescriptor() != tdReturn ) {
2553 TempDescriptor returnTemp = fc.getReturnTemp();
2554 if( returnTemp == null ||
2555 !DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2560 // note that the assignment of the return value is to a
2561 // variable in the caller which is out-of-context with
2562 // respect to the callee
2563 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2564 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2565 rsnCallers.add(vnLhsCaller);
2566 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2570 // for HeapRegionNode callee sources...
2572 // first see if the source is out-of-context, and only
2573 // proceed with this edge if we find some caller-context
2575 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2576 boolean matchedOutOfContext = false;
2578 if( !hrnSrcCallee.isOutOfContext() ) {
2581 hrnSrcCallee.getPreds().isSatisfiedBy(this,
2582 callerNodeIDsCopiedToCallee,
2584 if( predsIfSatis != null ) {
2585 calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
2587 // otherwise forget this edge
2592 // hrnSrcCallee is out-of-context
2593 assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
2595 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2597 // use the isSatisfiedBy with a non-null callers set to capture
2598 // nodes in the caller that match the predicates
2599 reCallee.getPreds().isSatisfiedBy( this,
2600 callerNodeIDsCopiedToCallee,
2603 if( !rsnCallers.isEmpty() ) {
2604 matchedOutOfContext = true;
2605 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2609 if( hrnSrcCallee.isOutOfContext() &&
2610 !matchedOutOfContext ) {
2617 reCallee.getPreds().isSatisfiedBy(this,
2618 callerNodeIDsCopiedToCallee,
2622 if( predsIfSatis != null ) {
2623 calleeEdgesSatisfied.put(reCallee, predsIfSatis);
2625 // since the edge is coming over, find out which reach
2626 // states on it should come over, too
2627 assert calleeEdge2calleeStatesSatisfied.get(reCallee) == null;
2629 stateItr = reCallee.getBeta().iterator();
2630 while( stateItr.hasNext() ) {
2631 ReachState stateCallee = stateItr.next();
2634 stateCallee.getPreds().isSatisfiedBy(this,
2635 callerNodeIDsCopiedToCallee,
2637 if( predsIfSatis != null ) {
2639 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2640 calleeEdge2calleeStatesSatisfied.get(reCallee);
2642 if( calleeStatesSatisfied == null ) {
2643 calleeStatesSatisfied =
2644 new Hashtable<ReachState, ExistPredSet>();
2646 calleeEdge2calleeStatesSatisfied.put(reCallee, calleeStatesSatisfied);
2649 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2653 // since the edge is coming over, find out which taints
2654 // on it should come over, too
2655 assert calleeEdge2calleeTaintsSatisfied.get(reCallee) == null;
2657 Iterator<Taint> tItr = reCallee.getTaints().iterator();
2658 while( tItr.hasNext() ) {
2659 Taint tCallee = tItr.next();
2662 tCallee.getPreds().isSatisfiedBy(this,
2663 callerNodeIDsCopiedToCallee,
2665 if( predsIfSatis != null ) {
2667 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2668 calleeEdge2calleeTaintsSatisfied.get(reCallee);
2670 if( calleeTaintsSatisfied == null ) {
2671 calleeTaintsSatisfied =
2672 new Hashtable<Taint, ExistPredSet>();
2674 calleeEdge2calleeTaintsSatisfied.put(reCallee, calleeTaintsSatisfied);
2677 calleeTaintsSatisfied.put(tCallee, predsIfSatis);
2684 if( writeDebugDOTs ) {
2685 writeGraph(debugGraphPrefix+"caller20BeforeWipe",
2686 resolveMethodDebugDOTwriteLabels,
2687 resolveMethodDebugDOTselectTemps,
2688 resolveMethodDebugDOTpruneGarbage,
2689 resolveMethodDebugDOThideReach,
2690 resolveMethodDebugDOThideSubsetReach,
2691 resolveMethodDebugDOThidePreds,
2692 resolveMethodDebugDOThideEdgeTaints);
2696 // 2. predicates tested, ok to wipe out caller part
2697 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2698 while( hrnItr.hasNext() ) {
2699 Integer hrnID = hrnItr.next();
2700 HeapRegionNode hrnCaller = id2hrn.get(hrnID);
2701 assert hrnCaller != null;
2703 // when clearing off nodes, also eliminate variable
2705 wipeOut(hrnCaller, true);
2708 // if we are assigning the return value to something, clobber now
2709 // as part of the wipe
2710 TempDescriptor returnTemp = fc.getReturnTemp();
2711 if( returnTemp != null &&
2712 DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2715 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2716 clearRefEdgesFrom(vnLhsCaller, null, null, true);
2722 if( writeDebugDOTs ) {
2723 writeGraph(debugGraphPrefix+"caller30BeforeAddingNodes",
2724 resolveMethodDebugDOTwriteLabels,
2725 resolveMethodDebugDOTselectTemps,
2726 resolveMethodDebugDOTpruneGarbage,
2727 resolveMethodDebugDOThideReach,
2728 resolveMethodDebugDOThideSubsetReach,
2729 resolveMethodDebugDOThidePreds,
2730 resolveMethodDebugDOThideEdgeTaints);
2736 // 3. callee elements with satisfied preds come in, note that
2737 // the mapping of elements satisfied to preds is like this:
2738 // A callee element EE has preds EEp that are satisfied by
2739 // some caller element ER. We bring EE into the caller
2740 // context as ERee with the preds of ER, namely ERp, which
2741 // in the following algorithm is the value in the mapping
2744 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2745 while( satisItr.hasNext() ) {
2746 Map.Entry me = (Map.Entry)satisItr.next();
2747 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2748 ExistPredSet preds = (ExistPredSet) me.getValue();
2750 // TODO: I think its true that the current implementation uses
2751 // the type of the OOC region and the predicates OF THE EDGE from
2752 // it to link everything up in caller context, so that's why we're
2753 // skipping this... maybe that's a sillier way to do it?
2754 if( hrnCallee.isOutOfContext() ) {
2758 AllocSite as = hrnCallee.getAllocSite();
2761 Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
2763 HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
2764 if( hrnCaller == null ) {
2766 createNewHeapRegionNode(hrnIDshadow, // id or null to generate a new one
2767 hrnCallee.isSingleObject(), // single object?
2768 hrnCallee.isNewSummary(), // summary?
2769 false, // out-of-context?
2770 hrnCallee.getType(), // type
2771 hrnCallee.getAllocSite(), // allocation site
2772 toCallerContext(hrnCallee.getInherent(),
2773 calleeNode2calleeStatesSatisfied.get(hrnCallee) ), // inherent reach
2774 null, // current reach
2775 predsEmpty, // predicates
2776 hrnCallee.getDescription() // description
2779 assert hrnCaller.isWiped();
2782 hrnCaller.setAlpha(toCallerContext(hrnCallee.getAlpha(),
2783 calleeNode2calleeStatesSatisfied.get(hrnCallee)
2787 hrnCaller.setPreds(preds);
2794 if( writeDebugDOTs ) {
2795 writeGraph(debugGraphPrefix+"caller31BeforeAddingEdges",
2796 resolveMethodDebugDOTwriteLabels,
2797 resolveMethodDebugDOTselectTemps,
2798 resolveMethodDebugDOTpruneGarbage,
2799 resolveMethodDebugDOThideReach,
2800 resolveMethodDebugDOThideSubsetReach,
2801 resolveMethodDebugDOThidePreds,
2802 resolveMethodDebugDOThideEdgeTaints);
2806 // set these up during the next procedure so after
2807 // the caller has all of its nodes and edges put
2808 // back together we can propagate the callee's
2809 // reach changes backwards into the caller graph
2810 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2812 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2813 new Hashtable<RefEdge, ChangeSet>();
2816 // 3.b) callee -> callee edges AND out-of-context -> callee
2817 // which includes return temp -> callee edges now, too
2818 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2819 while( satisItr.hasNext() ) {
2820 Map.Entry me = (Map.Entry)satisItr.next();
2821 RefEdge reCallee = (RefEdge) me.getKey();
2822 ExistPredSet preds = (ExistPredSet) me.getValue();
2824 HeapRegionNode hrnDstCallee = reCallee.getDst();
2825 AllocSite asDst = hrnDstCallee.getAllocSite();
2826 allocSites.add(asDst);
2828 Integer hrnIDDstShadow =
2829 asDst.getShadowIDfromID(hrnDstCallee.getID() );
2831 HeapRegionNode hrnDstCaller = id2hrn.get(hrnIDDstShadow);
2832 assert hrnDstCaller != null;
2835 RefSrcNode rsnCallee = reCallee.getSrc();
2837 Set<RefSrcNode> rsnCallers =
2838 new HashSet<RefSrcNode>();
2840 Set<RefSrcNode> oocCallers =
2841 calleeEdges2oocCallerSrcMatches.get(reCallee);
2843 if( rsnCallee instanceof HeapRegionNode ) {
2844 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2845 if( hrnCalleeSrc.isOutOfContext() ) {
2846 assert oocCallers != null;
2851 if( oocCallers == null ) {
2852 // there are no out-of-context matches, so it's
2853 // either a param/arg var or one in-context heap region
2854 if( rsnCallee instanceof VariableNode ) {
2855 // variable -> node in the callee should only
2856 // come into the caller if its from a param var
2857 VariableNode vnCallee = (VariableNode) rsnCallee;
2858 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2859 TempDescriptor tdArg = fc.getArgMatchingParam(fmCallee,
2861 if( tdArg == null ) {
2862 // this means the variable isn't a parameter, its local
2863 // to the callee so we ignore it in call site transfer
2864 // shouldn't this NEVER HAPPEN?
2868 rsnCallers.add(this.getVariableNodeFromTemp(tdArg) );
2871 // otherwise source is in context, one region
2873 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2875 // translate an in-context node to shadow
2876 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2877 allocSites.add(asSrc);
2879 Integer hrnIDSrcShadow =
2880 asSrc.getShadowIDfromID(hrnSrcCallee.getID() );
2882 HeapRegionNode hrnSrcCallerShadow =
2883 this.id2hrn.get(hrnIDSrcShadow);
2885 assert hrnSrcCallerShadow != null;
2887 rsnCallers.add(hrnSrcCallerShadow);
2891 // otherwise we have a set of out-of-context srcs
2892 // that should NOT be translated to shadow nodes
2893 assert !oocCallers.isEmpty();
2894 rsnCallers.addAll(oocCallers);
2897 // now make all caller edges we've identified from
2898 // this callee edge with a satisfied predicate
2899 assert !rsnCallers.isEmpty();
2900 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2901 while( rsnItr.hasNext() ) {
2902 RefSrcNode rsnCaller = rsnItr.next();
2904 RefEdge reCaller = new RefEdge(rsnCaller,
2907 reCallee.getField(),
2908 toCallerContext(reCallee.getBeta(),
2909 calleeEdge2calleeStatesSatisfied.get(reCallee) ),
2911 toCallerContext(reCallee.getTaints(),
2912 calleeEdge2calleeTaintsSatisfied.get(reCallee) )
2915 ChangeSet cs = ChangeSet.factory();
2916 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2917 while( rsItr.hasNext() ) {
2918 ReachState state = rsItr.next();
2919 ExistPredSet predsPreCallee = state.getPreds();
2921 if( state.isEmpty() ) {
2925 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2926 while( predItr.hasNext() ) {
2927 ExistPred pred = predItr.next();
2928 ReachState old = pred.ne_state;
2934 cs = Canonical.add(cs,
2935 ChangeTuple.factory(old,
2942 // we're just going to use the convenient "merge-if-exists"
2943 // edge call below, but still take a separate look if there
2944 // is an existing caller edge to build change sets properly
2945 if( !cs.isEmpty() ) {
2946 RefEdge edgeExisting = rsnCaller.getReferenceTo(hrnDstCaller,
2950 if( edgeExisting != null ) {
2951 ChangeSet csExisting = edgePlannedChanges.get(edgeExisting);
2952 if( csExisting == null ) {
2953 csExisting = ChangeSet.factory();
2955 edgePlannedChanges.put(edgeExisting,
2956 Canonical.union(csExisting,
2961 edgesForPropagation.add(reCaller);
2962 assert !edgePlannedChanges.containsKey(reCaller);
2963 edgePlannedChanges.put(reCaller, cs);
2967 // then add new caller edge or merge
2968 addEdgeOrMergeWithExisting(reCaller);
2976 if( writeDebugDOTs ) {
2977 writeGraph(debugGraphPrefix+"caller38propagateReach",
2978 resolveMethodDebugDOTwriteLabels,
2979 resolveMethodDebugDOTselectTemps,
2980 resolveMethodDebugDOTpruneGarbage,
2981 resolveMethodDebugDOThideReach,
2982 resolveMethodDebugDOThideSubsetReach,
2983 resolveMethodDebugDOThidePreds,
2984 resolveMethodDebugDOThideEdgeTaints);
2987 // propagate callee reachability changes to the rest
2988 // of the caller graph edges
2989 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2991 propagateTokensOverEdges( edgesForPropagation, // source edges
2992 edgePlannedChanges, // map src edge to change set
2993 edgesUpdated, // list of updated edges
2996 // commit beta' (beta<-betaNew)
2997 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2998 while( edgeItr.hasNext() ) {
2999 edgeItr.next().applyBetaNew();
3008 if( writeDebugDOTs ) {
3009 writeGraph(debugGraphPrefix+"caller40BeforeShadowMerge",
3010 resolveMethodDebugDOTwriteLabels,
3011 resolveMethodDebugDOTselectTemps,
3012 resolveMethodDebugDOTpruneGarbage,
3013 resolveMethodDebugDOThideReach,
3014 resolveMethodDebugDOThideSubsetReach,
3015 resolveMethodDebugDOThidePreds,
3016 resolveMethodDebugDOThideEdgeTaints);
3020 // 4) merge shadow nodes so alloc sites are back to k
3021 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
3022 while( asItr.hasNext() ) {
3023 // for each allocation site do the following to merge
3024 // shadow nodes (newest from callee) with any existing
3025 // look for the newest normal and newest shadow "slot"
3026 // not being used, transfer normal to shadow. Keep
3027 // doing this until there are no more normal nodes, or
3028 // no empty shadow slots: then merge all remaining normal
3029 // nodes into the shadow summary. Finally, convert all
3030 // shadow to their normal versions.
3031 AllocSite as = asItr.next();
3035 while( ageNorm < allocationDepth &&
3036 ageShad < allocationDepth ) {
3038 // first, are there any normal nodes left?
3039 Integer idNorm = as.getIthOldest(ageNorm);
3040 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
3041 if( hrnNorm == null ) {
3042 // no, this age of normal node not in the caller graph
3047 // yes, a normal node exists, is there an empty shadow
3048 // "slot" to transfer it onto?
3049 HeapRegionNode hrnShad = getIthNode(as, ageShad, true);
3050 if( !hrnShad.isWiped() ) {
3051 // no, this age of shadow node is not empty
3056 // yes, this shadow node is empty
3057 transferOnto(hrnNorm, hrnShad);
3062 // now, while there are still normal nodes but no shadow
3063 // slots, merge normal nodes into the shadow summary
3064 while( ageNorm < allocationDepth ) {
3066 // first, are there any normal nodes left?
3067 Integer idNorm = as.getIthOldest(ageNorm);
3068 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
3069 if( hrnNorm == null ) {
3070 // no, this age of normal node not in the caller graph
3075 // yes, a normal node exists, so get the shadow summary
3076 HeapRegionNode summShad = getSummaryNode(as, true);
3077 mergeIntoSummary(hrnNorm, summShad);
3079 // now tokens in reachability sets need to age also
3080 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3081 while( itrAllHRNodes.hasNext() ) {
3082 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
3083 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
3085 ageTuplesFrom(as, hrnToAge);
3087 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
3088 while( itrEdges.hasNext() ) {
3089 ageTuplesFrom(as, itrEdges.next() );
3096 // if there is a normal summary, merge it into shadow summary
3097 Integer idNorm = as.getSummary();
3098 HeapRegionNode summNorm = id2hrn.get(idNorm);
3099 if( summNorm != null ) {
3100 HeapRegionNode summShad = getSummaryNode(as, true);
3101 mergeIntoSummary(summNorm, summShad);
3104 // finally, flip all existing shadow nodes onto the normal
3105 for( int i = 0; i < allocationDepth; ++i ) {
3106 Integer idShad = as.getIthOldestShadow(i);
3107 HeapRegionNode hrnShad = id2hrn.get(idShad);
3108 if( hrnShad != null ) {
3110 HeapRegionNode hrnNorm = getIthNode(as, i, false);
3111 assert hrnNorm.isWiped();
3112 transferOnto(hrnShad, hrnNorm);
3116 Integer idShad = as.getSummaryShadow();
3117 HeapRegionNode summShad = id2hrn.get(idShad);
3118 if( summShad != null ) {
3119 summNorm = getSummaryNode(as, false);
3120 transferOnto(summShad, summNorm);
3129 if( writeDebugDOTs ) {
3130 writeGraph(debugGraphPrefix+"caller45BeforeUnshadow",
3131 resolveMethodDebugDOTwriteLabels,
3132 resolveMethodDebugDOTselectTemps,
3133 resolveMethodDebugDOTpruneGarbage,
3134 resolveMethodDebugDOThideReach,
3135 resolveMethodDebugDOThideSubsetReach,
3136 resolveMethodDebugDOThidePreds,
3137 resolveMethodDebugDOThideEdgeTaints);
3141 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3142 while( itrAllHRNodes.hasNext() ) {
3143 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
3144 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3146 hrn.setAlpha(unshadow(hrn.getAlpha() ) );
3148 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
3149 while( itrEdges.hasNext() ) {
3150 RefEdge re = itrEdges.next();
3151 re.setBeta(unshadow(re.getBeta() ) );
3158 if( writeDebugDOTs ) {
3159 writeGraph(debugGraphPrefix+"caller50BeforeGlobalSweep",
3160 resolveMethodDebugDOTwriteLabels,
3161 resolveMethodDebugDOTselectTemps,
3162 resolveMethodDebugDOTpruneGarbage,
3163 resolveMethodDebugDOThideReach,
3164 resolveMethodDebugDOThideSubsetReach,
3165 resolveMethodDebugDOThidePreds,
3166 resolveMethodDebugDOThideEdgeTaints);
3171 if( !DISABLE_GLOBAL_SWEEP ) {
3176 if( writeDebugDOTs ) {
3177 writeGraph(debugGraphPrefix+"caller90AfterTransfer",
3178 resolveMethodDebugDOTwriteLabels,
3179 resolveMethodDebugDOTselectTemps,
3180 resolveMethodDebugDOTpruneGarbage,
3181 resolveMethodDebugDOThideReach,
3182 resolveMethodDebugDOThideSubsetReach,
3183 resolveMethodDebugDOThidePreds,
3184 resolveMethodDebugDOThideEdgeTaints);
3190 ////////////////////////////////////////////////////
3192 // Abstract garbage collection simply removes
3193 // heap region nodes that are not mechanically
3194 // reachable from a root set. This step is
3195 // essential for testing node and edge existence
3196 // predicates efficiently
3198 ////////////////////////////////////////////////////
3199 public void abstractGarbageCollect(Set<TempDescriptor> liveSet) {
3201 // calculate a root set, will be different for Java
3202 // version of analysis versus Bamboo version
3203 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3205 // visit every variable in graph while building root
3206 // set, and do iterating on a copy, so we can remove
3207 // dead variables while we're at this
3208 Iterator makeCopyItr = td2vn.entrySet().iterator();
3209 Set entrysCopy = new HashSet();
3210 while( makeCopyItr.hasNext() ) {
3211 entrysCopy.add(makeCopyItr.next() );
3214 Iterator eItr = entrysCopy.iterator();
3215 while( eItr.hasNext() ) {
3216 Map.Entry me = (Map.Entry)eItr.next();
3217 TempDescriptor td = (TempDescriptor) me.getKey();
3218 VariableNode vn = (VariableNode) me.getValue();
3220 if( liveSet.contains(td) ) {
3224 // dead var, remove completely from graph
3226 clearRefEdgesFrom(vn, null, null, true);
3230 // everything visited in a traversal is
3231 // considered abstractly live
3232 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3234 while( !toVisit.isEmpty() ) {
3235 RefSrcNode rsn = toVisit.iterator().next();
3236 toVisit.remove(rsn);
3239 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3240 while( hrnItr.hasNext() ) {
3241 RefEdge edge = hrnItr.next();
3242 HeapRegionNode hrn = edge.getDst();
3244 if( !visited.contains(hrn) ) {
3250 // get a copy of the set to iterate over because
3251 // we're going to monkey with the graph when we
3252 // identify a garbage node
3253 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3254 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3255 while( hrnItr.hasNext() ) {
3256 hrnAllPrior.add(hrnItr.next() );
3259 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3260 while( hrnAllItr.hasNext() ) {
3261 HeapRegionNode hrn = hrnAllItr.next();
3263 if( !visited.contains(hrn) ) {
3265 // heap region nodes are compared across ReachGraph
3266 // objects by their integer ID, so when discarding
3267 // garbage nodes we must also discard entries in
3268 // the ID -> heap region hashtable.
3269 id2hrn.remove(hrn.getID() );
3271 // RefEdge objects are two-way linked between
3272 // nodes, so when a node is identified as garbage,
3273 // actively clear references to and from it so
3274 // live nodes won't have dangling RefEdge's
3277 // if we just removed the last node from an allocation
3278 // site, it should be taken out of the ReachGraph's list
3279 AllocSite as = hrn.getAllocSite();
3280 if( !hasNodesOf(as) ) {
3281 allocSites.remove(as);
3287 protected boolean hasNodesOf(AllocSite as) {
3288 if( id2hrn.containsKey(as.getSummary() ) ) {
3292 for( int i = 0; i < allocationDepth; ++i ) {
3293 if( id2hrn.containsKey(as.getIthOldest(i) ) ) {
3301 ////////////////////////////////////////////////////
3303 // This global sweep is an optional step to prune
3304 // reachability sets that are not internally
3305 // consistent with the global graph. It should be
3306 // invoked after strong updates or method calls.
3308 ////////////////////////////////////////////////////
3309 public void globalSweep() {
3311 // boldB is part of the phase 1 sweep
3312 // it has an in-context table and an out-of-context table
3313 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3314 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3316 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3317 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3319 // visit every heap region to initialize alphaNew and betaNew,
3320 // and make a map of every hrnID to the source nodes it should
3321 // propagate forward from. In-context flagged hrnID's propagate
3322 // from only the in-context node they name, but out-of-context
3323 // ID's may propagate from several out-of-context nodes
3324 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3325 new Hashtable< Integer, Set<HeapRegionNode> >();
3327 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3328 new Hashtable< Integer, Set<HeapRegionNode> >();
3331 Iterator itrHrns = id2hrn.entrySet().iterator();
3332 while( itrHrns.hasNext() ) {
3333 Map.Entry me = (Map.Entry)itrHrns.next();
3334 Integer hrnID = (Integer) me.getKey();
3335 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3337 // assert that this node and incoming edges have clean alphaNew
3338 // and betaNew sets, respectively
3339 assert rsetEmpty.equals(hrn.getAlphaNew() );
3341 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3342 while( itrRers.hasNext() ) {
3343 RefEdge edge = itrRers.next();
3344 assert rsetEmpty.equals(edge.getBetaNew() );
3347 // make a mapping of IDs to heap regions they propagate from
3348 if( hrn.isFlagged() ) {
3349 assert !hrn.isOutOfContext();
3350 assert !icID2srcs.containsKey(hrn.getID() );
3352 // in-context flagged node IDs simply propagate from the
3354 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3356 icID2srcs.put(hrn.getID(), srcs);
3359 if( hrn.isOutOfContext() ) {
3360 assert !hrn.isFlagged();
3362 // the reachability states on an out-of-context
3363 // node are not really important (combinations of
3364 // IDs or arity)--what matters is that the states
3365 // specify which nodes this out-of-context node
3366 // stands in for. For example, if the state [17?, 19*]
3367 // appears on the ooc node, it may serve as a source
3368 // for node 17? and a source for node 19.
3369 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3370 while( stateItr.hasNext() ) {
3371 ReachState state = stateItr.next();
3373 Iterator<ReachTuple> rtItr = state.iterator();
3374 while( rtItr.hasNext() ) {
3375 ReachTuple rt = rtItr.next();
3376 assert rt.isOutOfContext();
3378 Set<HeapRegionNode> srcs = oocID2srcs.get(rt.getHrnID() );
3379 if( srcs == null ) {
3380 srcs = new HashSet<HeapRegionNode>();
3383 oocID2srcs.put(rt.getHrnID(), srcs);
3389 // calculate boldB for all hrnIDs identified by the above
3390 // node traversal, propagating from every source
3391 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3394 Set<HeapRegionNode> srcs;
3397 if( !icID2srcs.isEmpty() ) {
3398 Map.Entry me = (Map.Entry)icID2srcs.entrySet().iterator().next();
3399 hrnID = (Integer) me.getKey();
3400 srcs = (Set<HeapRegionNode>)me.getValue();
3402 icID2srcs.remove(hrnID);
3405 assert !oocID2srcs.isEmpty();
3407 Map.Entry me = (Map.Entry)oocID2srcs.entrySet().iterator().next();
3408 hrnID = (Integer) me.getKey();
3409 srcs = (Set<HeapRegionNode>)me.getValue();
3411 oocID2srcs.remove(hrnID);
3415 Hashtable<RefEdge, ReachSet> boldB_f =
3416 new Hashtable<RefEdge, ReachSet>();
3418 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3420 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3421 while( hrnItr.hasNext() ) {
3422 HeapRegionNode hrn = hrnItr.next();
3424 assert workSetEdges.isEmpty();
3426 // initial boldB_f constraints
3427 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3428 while( itrRees.hasNext() ) {
3429 RefEdge edge = itrRees.next();
3431 assert !boldB_f.containsKey(edge);
3432 boldB_f.put(edge, edge.getBeta() );
3434 assert !workSetEdges.contains(edge);
3435 workSetEdges.add(edge);
3438 // enforce the boldB_f constraint at edges until we reach a fixed point
3439 while( !workSetEdges.isEmpty() ) {
3440 RefEdge edge = workSetEdges.iterator().next();
3441 workSetEdges.remove(edge);
3443 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3444 while( itrPrime.hasNext() ) {
3445 RefEdge edgePrime = itrPrime.next();
3447 ReachSet prevResult = boldB_f.get(edgePrime);
3448 ReachSet intersection = Canonical.intersection(boldB_f.get(edge),
3452 if( prevResult == null ||
3453 Canonical.unionORpreds(prevResult,
3454 intersection).size()
3458 if( prevResult == null ) {
3459 boldB_f.put(edgePrime,
3460 Canonical.unionORpreds(edgePrime.getBeta(),
3465 boldB_f.put(edgePrime,
3466 Canonical.unionORpreds(prevResult,
3471 workSetEdges.add(edgePrime);
3478 boldBic.put(hrnID, boldB_f);
3480 boldBooc.put(hrnID, boldB_f);
3485 // use boldB to prune hrnIDs from alpha states that are impossible
3486 // and propagate the differences backwards across edges
3487 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3489 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3490 new Hashtable<RefEdge, ChangeSet>();
3493 itrHrns = id2hrn.entrySet().iterator();
3494 while( itrHrns.hasNext() ) {
3495 Map.Entry me = (Map.Entry)itrHrns.next();
3496 Integer hrnID = (Integer) me.getKey();
3497 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3499 // out-of-context nodes don't participate in the
3500 // global sweep, they serve as sources for the pass
3502 if( hrn.isOutOfContext() ) {
3506 // the inherent states of a region are the exception
3507 // to removal as the global sweep prunes
3508 ReachTuple rtException = ReachTuple.factory(hrnID,
3509 !hrn.isSingleObject(),
3510 ReachTuple.ARITY_ONE,
3511 false // out-of-context
3514 ChangeSet cts = ChangeSet.factory();
3516 // mark hrnIDs for removal
3517 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3518 while( stateItr.hasNext() ) {
3519 ReachState stateOld = stateItr.next();
3521 ReachState markedHrnIDs = ReachState.factory();
3523 Iterator<ReachTuple> rtItr = stateOld.iterator();
3524 while( rtItr.hasNext() ) {
3525 ReachTuple rtOld = rtItr.next();
3527 // never remove the inherent hrnID from a flagged region
3528 // because it is trivially satisfied
3529 if( hrn.isFlagged() ) {
3530 if( rtOld == rtException ) {
3535 // does boldB allow this hrnID?
3536 boolean foundState = false;
3537 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3538 while( incidentEdgeItr.hasNext() ) {
3539 RefEdge incidentEdge = incidentEdgeItr.next();
3541 Hashtable<RefEdge, ReachSet> B;
3542 if( rtOld.isOutOfContext() ) {
3543 B = boldBooc.get(rtOld.getHrnID() );
3546 if( !id2hrn.containsKey(rtOld.getHrnID() ) ) {
3547 // let symbols not in the graph get pruned
3551 B = boldBic.get(rtOld.getHrnID() );
3555 ReachSet boldB_rtOld_incident = B.get(incidentEdge);
3556 if( boldB_rtOld_incident != null &&
3557 boldB_rtOld_incident.containsIgnorePreds(stateOld) != null
3565 markedHrnIDs = Canonical.addUpArity(markedHrnIDs, rtOld);
3569 // if there is nothing marked, just move on
3570 if( markedHrnIDs.isEmpty() ) {
3571 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3578 // remove all marked hrnIDs and establish a change set that should
3579 // propagate backwards over edges from this node
3580 ReachState statePruned = ReachState.factory();
3581 rtItr = stateOld.iterator();
3582 while( rtItr.hasNext() ) {
3583 ReachTuple rtOld = rtItr.next();
3585 if( !markedHrnIDs.containsTuple(rtOld) ) {
3586 statePruned = Canonical.addUpArity(statePruned, rtOld);
3589 assert !stateOld.equals(statePruned);
3591 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3595 ChangeTuple ct = ChangeTuple.factory(stateOld,
3598 cts = Canonical.add(cts, ct);
3601 // throw change tuple set on all incident edges
3602 if( !cts.isEmpty() ) {
3603 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3604 while( incidentEdgeItr.hasNext() ) {
3605 RefEdge incidentEdge = incidentEdgeItr.next();
3607 edgesForPropagation.add(incidentEdge);
3609 if( edgePlannedChanges.get(incidentEdge) == null ) {
3610 edgePlannedChanges.put(incidentEdge, cts);
3612 edgePlannedChanges.put(
3614 Canonical.union(edgePlannedChanges.get(incidentEdge),
3623 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3625 propagateTokensOverEdges(edgesForPropagation,
3630 // at the end of the 1st phase reference edges have
3631 // beta, betaNew that correspond to beta and betaR
3633 // commit beta<-betaNew, so beta=betaR and betaNew
3634 // will represent the beta' calculation in 2nd phase
3636 // commit alpha<-alphaNew because it won't change
3637 HashSet<RefEdge> res = new HashSet<RefEdge>();
3639 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3640 while( nodeItr.hasNext() ) {
3641 HeapRegionNode hrn = nodeItr.next();
3643 // as mentioned above, out-of-context nodes only serve
3644 // as sources of reach states for the sweep, not part
3646 if( hrn.isOutOfContext() ) {
3647 assert hrn.getAlphaNew().equals(rsetEmpty);
3649 hrn.applyAlphaNew();
3652 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3653 while( itrRes.hasNext() ) {
3654 res.add(itrRes.next() );
3660 Iterator<RefEdge> edgeItr = res.iterator();
3661 while( edgeItr.hasNext() ) {
3662 RefEdge edge = edgeItr.next();
3663 HeapRegionNode hrn = edge.getDst();
3665 // commit results of last phase
3666 if( edgesUpdated.contains(edge) ) {
3667 edge.applyBetaNew();
3670 // compute intial condition of 2nd phase
3671 edge.setBetaNew(Canonical.intersection(edge.getBeta(),
3677 // every edge in the graph is the initial workset
3678 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3679 while( !edgeWorkSet.isEmpty() ) {
3680 RefEdge edgePrime = edgeWorkSet.iterator().next();
3681 edgeWorkSet.remove(edgePrime);
3683 RefSrcNode rsn = edgePrime.getSrc();
3684 if( !(rsn instanceof HeapRegionNode) ) {
3687 HeapRegionNode hrn = (HeapRegionNode) rsn;
3689 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3690 while( itrEdge.hasNext() ) {
3691 RefEdge edge = itrEdge.next();
3693 ReachSet prevResult = edge.getBetaNew();
3694 assert prevResult != null;
3696 ReachSet intersection =
3697 Canonical.intersection(edge.getBeta(),
3698 edgePrime.getBetaNew()
3701 if( Canonical.unionORpreds(prevResult,
3708 Canonical.unionORpreds(prevResult,
3712 edgeWorkSet.add(edge);
3717 // commit beta' (beta<-betaNew)
3718 edgeItr = res.iterator();
3719 while( edgeItr.hasNext() ) {
3720 edgeItr.next().applyBetaNew();
3725 // a useful assertion for debugging:
3726 // every in-context tuple on any edge or
3727 // any node should name a node that is
3728 // part of the graph
3729 public boolean inContextTuplesInGraph() {
3731 Iterator hrnItr = id2hrn.entrySet().iterator();
3732 while( hrnItr.hasNext() ) {
3733 Map.Entry me = (Map.Entry)hrnItr.next();
3734 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3737 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3738 while( stateItr.hasNext() ) {
3739 ReachState state = stateItr.next();
3741 Iterator<ReachTuple> rtItr = state.iterator();
3742 while( rtItr.hasNext() ) {
3743 ReachTuple rt = rtItr.next();
3745 if( !rt.isOutOfContext() ) {
3746 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3747 System.out.println(rt.getHrnID()+" is missing");
3755 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3756 while( edgeItr.hasNext() ) {
3757 RefEdge edge = edgeItr.next();
3759 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3760 while( stateItr.hasNext() ) {
3761 ReachState state = stateItr.next();
3763 Iterator<ReachTuple> rtItr = state.iterator();
3764 while( rtItr.hasNext() ) {
3765 ReachTuple rt = rtItr.next();
3767 if( !rt.isOutOfContext() ) {
3768 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3769 System.out.println(rt.getHrnID()+" is missing");
3782 // another useful assertion for debugging
3783 public boolean noEmptyReachSetsInGraph() {
3785 Iterator hrnItr = id2hrn.entrySet().iterator();
3786 while( hrnItr.hasNext() ) {
3787 Map.Entry me = (Map.Entry)hrnItr.next();
3788 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3790 if( !hrn.isOutOfContext() &&
3792 hrn.getAlpha().isEmpty()
3794 System.out.println("!!! "+hrn+" has an empty ReachSet !!!");
3798 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3799 while( edgeItr.hasNext() ) {
3800 RefEdge edge = edgeItr.next();
3802 if( edge.getBeta().isEmpty() ) {
3803 System.out.println("!!! "+edge+" has an empty ReachSet !!!");
3813 public boolean everyReachStateWTrue() {
3815 Iterator hrnItr = id2hrn.entrySet().iterator();
3816 while( hrnItr.hasNext() ) {
3817 Map.Entry me = (Map.Entry)hrnItr.next();
3818 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3821 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3822 while( stateItr.hasNext() ) {
3823 ReachState state = stateItr.next();
3825 if( !state.getPreds().equals(predsTrue) ) {
3831 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3832 while( edgeItr.hasNext() ) {
3833 RefEdge edge = edgeItr.next();
3835 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3836 while( stateItr.hasNext() ) {
3837 ReachState state = stateItr.next();
3839 if( !state.getPreds().equals(predsTrue) ) {
3852 ////////////////////////////////////////////////////
3853 // in merge() and equals() methods the suffix A
3854 // represents the passed in graph and the suffix
3855 // B refers to the graph in this object
3856 // Merging means to take the incoming graph A and
3857 // merge it into B, so after the operation graph B
3858 // is the final result.
3859 ////////////////////////////////////////////////////
3860 protected void merge(ReachGraph rg) {
3868 mergeAllocSites(rg);
3869 mergeInaccessibleVars(rg);
3872 protected void mergeNodes(ReachGraph rg) {
3874 // start with heap region nodes
3875 Set sA = rg.id2hrn.entrySet();
3876 Iterator iA = sA.iterator();
3877 while( iA.hasNext() ) {
3878 Map.Entry meA = (Map.Entry)iA.next();
3879 Integer idA = (Integer) meA.getKey();
3880 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3882 // if this graph doesn't have a node the
3883 // incoming graph has, allocate it
3884 if( !id2hrn.containsKey(idA) ) {
3885 HeapRegionNode hrnB = hrnA.copy();
3886 id2hrn.put(idA, hrnB);
3889 // otherwise this is a node present in both graphs
3890 // so make the new reachability set a union of the
3891 // nodes' reachability sets
3892 HeapRegionNode hrnB = id2hrn.get(idA);
3893 hrnB.setAlpha(Canonical.unionORpreds(hrnB.getAlpha(),
3898 hrnB.setPreds(Canonical.join(hrnB.getPreds(),
3905 if( !hrnA.equals(hrnB) ) {
3906 rg.writeGraph("graphA");
3907 this.writeGraph("graphB");
3908 throw new Error("flagged not matching");
3916 // now add any variable nodes that are in graph B but
3918 sA = rg.td2vn.entrySet();
3920 while( iA.hasNext() ) {
3921 Map.Entry meA = (Map.Entry)iA.next();
3922 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3923 VariableNode lnA = (VariableNode) meA.getValue();
3925 // if the variable doesn't exist in B, allocate and add it
3926 VariableNode lnB = getVariableNodeFromTemp(tdA);
3930 protected void mergeRefEdges(ReachGraph rg) {
3932 // between heap regions
3933 Set sA = rg.id2hrn.entrySet();
3934 Iterator iA = sA.iterator();
3935 while( iA.hasNext() ) {
3936 Map.Entry meA = (Map.Entry)iA.next();
3937 Integer idA = (Integer) meA.getKey();
3938 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3940 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3941 while( heapRegionsItrA.hasNext() ) {
3942 RefEdge edgeA = heapRegionsItrA.next();
3943 HeapRegionNode hrnChildA = edgeA.getDst();
3944 Integer idChildA = hrnChildA.getID();
3946 // at this point we know an edge in graph A exists
3947 // idA -> idChildA, does this exist in B?
3948 assert id2hrn.containsKey(idA);
3949 HeapRegionNode hrnB = id2hrn.get(idA);
3950 RefEdge edgeToMerge = null;
3952 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3953 while( heapRegionsItrB.hasNext() &&
3954 edgeToMerge == null ) {
3956 RefEdge edgeB = heapRegionsItrB.next();
3957 HeapRegionNode hrnChildB = edgeB.getDst();
3958 Integer idChildB = hrnChildB.getID();
3960 // don't use the RefEdge.equals() here because
3961 // we're talking about existence between graphs,
3962 // not intragraph equal
3963 if( idChildB.equals(idChildA) &&
3964 edgeB.typeAndFieldEquals(edgeA) ) {
3966 edgeToMerge = edgeB;
3970 // if the edge from A was not found in B,
3972 if( edgeToMerge == null ) {
3973 assert id2hrn.containsKey(idChildA);
3974 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3975 edgeToMerge = edgeA.copy();
3976 edgeToMerge.setSrc(hrnB);
3977 edgeToMerge.setDst(hrnChildB);
3978 addRefEdge(hrnB, hrnChildB, edgeToMerge);
3980 // otherwise, the edge already existed in both graphs
3981 // so merge their reachability sets
3983 // just replace this beta set with the union
3984 assert edgeToMerge != null;
3985 edgeToMerge.setBeta(
3986 Canonical.unionORpreds(edgeToMerge.getBeta(),
3990 edgeToMerge.setPreds(
3991 Canonical.join(edgeToMerge.getPreds(),
3995 edgeToMerge.setTaints(
3996 Canonical.union(edgeToMerge.getTaints(),
4004 // and then again from variable nodes
4005 sA = rg.td2vn.entrySet();
4007 while( iA.hasNext() ) {
4008 Map.Entry meA = (Map.Entry)iA.next();
4009 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4010 VariableNode vnA = (VariableNode) meA.getValue();
4012 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
4013 while( heapRegionsItrA.hasNext() ) {
4014 RefEdge edgeA = heapRegionsItrA.next();
4015 HeapRegionNode hrnChildA = edgeA.getDst();
4016 Integer idChildA = hrnChildA.getID();
4018 // at this point we know an edge in graph A exists
4019 // tdA -> idChildA, does this exist in B?
4020 assert td2vn.containsKey(tdA);
4021 VariableNode vnB = td2vn.get(tdA);
4022 RefEdge edgeToMerge = null;
4024 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
4025 while( heapRegionsItrB.hasNext() &&
4026 edgeToMerge == null ) {
4028 RefEdge edgeB = heapRegionsItrB.next();
4029 HeapRegionNode hrnChildB = edgeB.getDst();
4030 Integer idChildB = hrnChildB.getID();
4032 // don't use the RefEdge.equals() here because
4033 // we're talking about existence between graphs
4034 if( idChildB.equals(idChildA) &&
4035 edgeB.typeAndFieldEquals(edgeA) ) {
4037 edgeToMerge = edgeB;
4041 // if the edge from A was not found in B,
4043 if( edgeToMerge == null ) {
4044 assert id2hrn.containsKey(idChildA);
4045 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
4046 edgeToMerge = edgeA.copy();
4047 edgeToMerge.setSrc(vnB);
4048 edgeToMerge.setDst(hrnChildB);
4049 addRefEdge(vnB, hrnChildB, edgeToMerge);
4051 // otherwise, the edge already existed in both graphs
4052 // so merge their reachability sets
4054 // just replace this beta set with the union
4055 edgeToMerge.setBeta(Canonical.unionORpreds(edgeToMerge.getBeta(),
4059 edgeToMerge.setPreds(Canonical.join(edgeToMerge.getPreds(),
4063 edgeToMerge.setTaints(
4064 Canonical.union(edgeToMerge.getTaints(),
4073 protected void mergeAllocSites(ReachGraph rg) {
4074 allocSites.addAll(rg.allocSites);
4077 protected void mergeInaccessibleVars(ReachGraph rg) {
4078 inaccessibleVars.addAll(rg.inaccessibleVars);
4083 static public boolean dbgEquals = false;
4086 // it is necessary in the equals() member functions
4087 // to "check both ways" when comparing the data
4088 // structures of two graphs. For instance, if all
4089 // edges between heap region nodes in graph A are
4090 // present and equal in graph B it is not sufficient
4091 // to say the graphs are equal. Consider that there
4092 // may be edges in graph B that are not in graph A.
4093 // the only way to know that all edges in both graphs
4094 // are equally present is to iterate over both data
4095 // structures and compare against the other graph.
4096 public boolean equals(ReachGraph rg) {
4100 System.out.println("rg is null");
4105 if( !areHeapRegionNodesEqual(rg) ) {
4107 System.out.println("hrn not equal");
4112 if( !areVariableNodesEqual(rg) ) {
4114 System.out.println("vars not equal");
4119 if( !areRefEdgesEqual(rg) ) {
4121 System.out.println("edges not equal");
4126 if( !inaccessibleVars.equals(rg.inaccessibleVars) ) {
4130 // if everything is equal up to this point,
4131 // assert that allocSites is also equal--
4132 // this data is redundant but kept for efficiency
4133 assert allocSites.equals(rg.allocSites);
4139 protected boolean areHeapRegionNodesEqual(ReachGraph rg) {
4141 if( !areallHRNinAalsoinBandequal(this, rg) ) {
4145 if( !areallHRNinAalsoinBandequal(rg, this) ) {
4152 static protected boolean areallHRNinAalsoinBandequal(ReachGraph rgA,
4154 Set sA = rgA.id2hrn.entrySet();
4155 Iterator iA = sA.iterator();
4156 while( iA.hasNext() ) {
4157 Map.Entry meA = (Map.Entry)iA.next();
4158 Integer idA = (Integer) meA.getKey();
4159 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4161 if( !rgB.id2hrn.containsKey(idA) ) {
4165 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4166 if( !hrnA.equalsIncludingAlphaAndPreds(hrnB) ) {
4174 protected boolean areVariableNodesEqual(ReachGraph rg) {
4176 if( !areallVNinAalsoinBandequal(this, rg) ) {
4180 if( !areallVNinAalsoinBandequal(rg, this) ) {
4187 static protected boolean areallVNinAalsoinBandequal(ReachGraph rgA,
4189 Set sA = rgA.td2vn.entrySet();
4190 Iterator iA = sA.iterator();
4191 while( iA.hasNext() ) {
4192 Map.Entry meA = (Map.Entry)iA.next();
4193 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4195 if( !rgB.td2vn.containsKey(tdA) ) {
4204 protected boolean areRefEdgesEqual(ReachGraph rg) {
4205 if( !areallREinAandBequal(this, rg) ) {
4209 if( !areallREinAandBequal(rg, this) ) {
4216 static protected boolean areallREinAandBequal(ReachGraph rgA,
4219 // check all the heap region->heap region edges
4220 Set sA = rgA.id2hrn.entrySet();
4221 Iterator iA = sA.iterator();
4222 while( iA.hasNext() ) {
4223 Map.Entry meA = (Map.Entry)iA.next();
4224 Integer idA = (Integer) meA.getKey();
4225 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4227 // we should have already checked that the same
4228 // heap regions exist in both graphs
4229 assert rgB.id2hrn.containsKey(idA);
4231 if( !areallREfromAequaltoB(rgA, hrnA, rgB) ) {
4235 // then check every edge in B for presence in A, starting
4236 // from the same parent HeapRegionNode
4237 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4239 if( !areallREfromAequaltoB(rgB, hrnB, rgA) ) {
4244 // then check all the variable->heap region edges
4245 sA = rgA.td2vn.entrySet();
4247 while( iA.hasNext() ) {
4248 Map.Entry meA = (Map.Entry)iA.next();
4249 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4250 VariableNode vnA = (VariableNode) meA.getValue();
4252 // we should have already checked that the same
4253 // label nodes exist in both graphs
4254 assert rgB.td2vn.containsKey(tdA);
4256 if( !areallREfromAequaltoB(rgA, vnA, rgB) ) {
4260 // then check every edge in B for presence in A, starting
4261 // from the same parent VariableNode
4262 VariableNode vnB = rgB.td2vn.get(tdA);
4264 if( !areallREfromAequaltoB(rgB, vnB, rgA) ) {
4273 static protected boolean areallREfromAequaltoB(ReachGraph rgA,
4277 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4278 while( itrA.hasNext() ) {
4279 RefEdge edgeA = itrA.next();
4280 HeapRegionNode hrnChildA = edgeA.getDst();
4281 Integer idChildA = hrnChildA.getID();
4283 assert rgB.id2hrn.containsKey(idChildA);
4285 // at this point we know an edge in graph A exists
4286 // rnA -> idChildA, does this exact edge exist in B?
4287 boolean edgeFound = false;
4289 RefSrcNode rnB = null;
4290 if( rnA instanceof HeapRegionNode ) {
4291 HeapRegionNode hrnA = (HeapRegionNode) rnA;
4292 rnB = rgB.id2hrn.get(hrnA.getID() );
4294 VariableNode vnA = (VariableNode) rnA;
4295 rnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4298 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4299 while( itrB.hasNext() ) {
4300 RefEdge edgeB = itrB.next();
4301 HeapRegionNode hrnChildB = edgeB.getDst();
4302 Integer idChildB = hrnChildB.getID();
4304 if( idChildA.equals(idChildB) &&
4305 edgeA.typeAndFieldEquals(edgeB) ) {
4307 // there is an edge in the right place with the right field,
4308 // but do they have the same attributes?
4309 if( edgeA.equalsIncludingBetaPredsTaints( edgeB ) ) {
4324 // can be used to assert monotonicity
4325 static public boolean isNoSmallerThan(ReachGraph rgA,
4328 //System.out.println( "*** Asking if A is no smaller than B ***" );
4330 Iterator iA = rgA.id2hrn.entrySet().iterator();
4331 while( iA.hasNext() ) {
4332 Map.Entry meA = (Map.Entry)iA.next();
4333 Integer idA = (Integer) meA.getKey();
4334 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4336 if( !rgB.id2hrn.containsKey(idA) ) {
4337 System.out.println(" regions smaller");
4342 // this works just fine, no smaller than
4343 if( !areallVNinAalsoinBandequal(rgA, rgB) ) {
4344 System.out.println(" vars smaller:");
4345 System.out.println(" A:"+rgA.td2vn.keySet() );
4346 System.out.println(" B:"+rgB.td2vn.keySet() );
4351 iA = rgA.id2hrn.entrySet().iterator();
4352 while( iA.hasNext() ) {
4353 Map.Entry meA = (Map.Entry)iA.next();
4354 Integer idA = (Integer) meA.getKey();
4355 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4357 Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4358 while( reItr.hasNext() ) {
4359 RefEdge edgeA = reItr.next();
4360 RefSrcNode rsnA = edgeA.getSrc();
4362 // we already checked that nodes were present
4363 HeapRegionNode hrnB = rgB.id2hrn.get(hrnA.getID() );
4364 assert hrnB != null;
4367 if( rsnA instanceof VariableNode ) {
4368 VariableNode vnA = (VariableNode) rsnA;
4369 rsnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4372 HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4373 rsnB = rgB.id2hrn.get(hrnSrcA.getID() );
4375 assert rsnB != null;
4377 RefEdge edgeB = rsnB.getReferenceTo(hrnB,
4381 if( edgeB == null ) {
4382 System.out.println(" edges smaller:");
4396 // this analysis no longer has the "match anything"
4397 // type which was represented by null
4398 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4399 TypeDescriptor td2) {
4403 if( td1.isNull() ) {
4406 if( td2.isNull() ) {
4409 return typeUtil.mostSpecific(td1, td2);
4412 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4414 TypeDescriptor td3) {
4416 return mostSpecificType(td1,
4417 mostSpecificType(td2, td3)
4421 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4424 TypeDescriptor td4) {
4426 return mostSpecificType(mostSpecificType(td1, td2),
4427 mostSpecificType(td3, td4)
4431 protected boolean isSuperiorType(TypeDescriptor possibleSuper,
4432 TypeDescriptor possibleChild) {
4433 assert possibleSuper != null;
4434 assert possibleChild != null;
4436 if( possibleSuper.isNull() ||
4437 possibleChild.isNull() ) {
4441 return typeUtil.isSuperorType(possibleSuper, possibleChild);
4445 protected boolean hasMatchingField(HeapRegionNode src,
4448 TypeDescriptor tdSrc = src.getType();
4449 assert tdSrc != null;
4451 if( tdSrc.isArray() ) {
4452 TypeDescriptor td = edge.getType();
4455 TypeDescriptor tdSrcDeref = tdSrc.dereference();
4456 assert tdSrcDeref != null;
4458 if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
4462 return edge.getField().equals(DisjointAnalysis.arrayElementFieldName);
4465 // if it's not a class, it doesn't have any fields to match
4466 if( !tdSrc.isClass() ) {
4470 ClassDescriptor cd = tdSrc.getClassDesc();
4471 while( cd != null ) {
4472 Iterator fieldItr = cd.getFields();
4474 while( fieldItr.hasNext() ) {
4475 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4477 if( fd.getType().equals(edge.getType() ) &&
4478 fd.getSymbol().equals(edge.getField() ) ) {
4483 cd = cd.getSuperDesc();
4486 // otherwise it is a class with fields
4487 // but we didn't find a match
4491 protected boolean hasMatchingType(RefEdge edge,
4492 HeapRegionNode dst) {
4494 // if the region has no type, matches everything
4495 TypeDescriptor tdDst = dst.getType();
4496 assert tdDst != null;
4498 // if the type is not a class or an array, don't
4499 // match because primitives are copied, no aliases
4500 ClassDescriptor cdDst = tdDst.getClassDesc();
4501 if( cdDst == null && !tdDst.isArray() ) {
4505 // if the edge type is null, it matches everything
4506 TypeDescriptor tdEdge = edge.getType();
4507 assert tdEdge != null;
4509 return typeUtil.isSuperorType(tdEdge, tdDst);
4514 // the default signature for quick-and-dirty debugging
4515 public void writeGraph(String graphName) {
4516 writeGraph(graphName,
4517 true, // write labels
4518 true, // label select
4519 true, // prune garbage
4520 false, // hide reachability
4521 true, // hide subset reachability
4522 true, // hide predicates
4523 false, // hide edge taints
4524 null // in-context boundary
4528 public void writeGraph(String graphName,
4529 boolean writeLabels,
4530 boolean labelSelect,
4531 boolean pruneGarbage,
4532 boolean hideReachability,
4533 boolean hideSubsetReachability,
4534 boolean hidePredicates,
4535 boolean hideEdgeTaints
4537 writeGraph(graphName,
4542 hideSubsetReachability,
4548 public void writeGraph(String graphName,
4549 boolean writeLabels,
4550 boolean labelSelect,
4551 boolean pruneGarbage,
4552 boolean hideReachability,
4553 boolean hideSubsetReachability,
4554 boolean hidePredicates,
4555 boolean hideEdgeTaints,
4556 Set<Integer> callerNodeIDsCopiedToCallee
4559 // remove all non-word characters from the graph name so
4560 // the filename and identifier in dot don't cause errors
4561 // jjenista - also replace underscore '_' to prevent some
4562 // really, really long names from IHMS debugging
4563 graphName = graphName.replaceAll("[\\W_]", "");
4566 new BufferedWriter(new FileWriter(graphName+".dot") );
4568 bw.write("digraph "+graphName+" {\n");
4571 // this is an optional step to form the callee-reachable
4572 // "cut-out" into a DOT cluster for visualization
4573 if( callerNodeIDsCopiedToCallee != null ) {
4575 bw.write(" subgraph cluster0 {\n");
4576 bw.write(" color=blue;\n");
4578 Iterator i = id2hrn.entrySet().iterator();
4579 while( i.hasNext() ) {
4580 Map.Entry me = (Map.Entry)i.next();
4581 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4583 if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4586 hrn.toStringDOT(hideReachability,
4587 hideSubsetReachability,
4597 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4599 // then visit every heap region node
4600 Iterator i = id2hrn.entrySet().iterator();
4601 while( i.hasNext() ) {
4602 Map.Entry me = (Map.Entry)i.next();
4603 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4605 // only visit nodes worth writing out--for instance
4606 // not every node at an allocation is referenced
4607 // (think of it as garbage-collected), etc.
4608 if( !pruneGarbage ||
4609 hrn.isOutOfContext() ||
4610 (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4613 if( !visited.contains(hrn) ) {
4614 traverseHeapRegionNodes(hrn,
4619 hideSubsetReachability,
4622 callerNodeIDsCopiedToCallee);
4627 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4630 // then visit every label node, useful for debugging
4632 i = td2vn.entrySet().iterator();
4633 while( i.hasNext() ) {
4634 Map.Entry me = (Map.Entry)i.next();
4635 VariableNode vn = (VariableNode) me.getValue();
4638 String labelStr = vn.getTempDescriptorString();
4639 if( labelStr.startsWith("___temp") ||
4640 labelStr.startsWith("___dst") ||
4641 labelStr.startsWith("___srctmp") ||
4642 labelStr.startsWith("___neverused")
4648 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4649 while( heapRegionsItr.hasNext() ) {
4650 RefEdge edge = heapRegionsItr.next();
4651 HeapRegionNode hrn = edge.getDst();
4653 if( !visited.contains(hrn) ) {
4654 traverseHeapRegionNodes(hrn,
4659 hideSubsetReachability,
4662 callerNodeIDsCopiedToCallee);
4665 bw.write(" "+vn.toString()+
4666 " -> "+hrn.toString()+
4667 edge.toStringDOT(hideReachability,
4668 hideSubsetReachability,
4680 } catch( IOException e ) {
4681 throw new Error("Error writing out DOT graph "+graphName);
4686 traverseHeapRegionNodes(HeapRegionNode hrn,
4689 Set<HeapRegionNode> visited,
4690 boolean hideReachability,
4691 boolean hideSubsetReachability,
4692 boolean hidePredicates,
4693 boolean hideEdgeTaints,
4694 Set<Integer> callerNodeIDsCopiedToCallee
4695 ) throws java.io.IOException {
4697 if( visited.contains(hrn) ) {
4702 // if we're drawing the callee-view subgraph, only
4703 // write out the node info if it hasn't already been
4705 if( callerNodeIDsCopiedToCallee == null ||
4706 !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4710 hrn.toStringDOT(hideReachability,
4711 hideSubsetReachability,
4716 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4717 while( childRegionsItr.hasNext() ) {
4718 RefEdge edge = childRegionsItr.next();
4719 HeapRegionNode hrnChild = edge.getDst();
4721 if( callerNodeIDsCopiedToCallee != null &&
4722 (edge.getSrc() instanceof HeapRegionNode) ) {
4723 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4724 if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4725 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4727 bw.write(" "+hrn.toString()+
4728 " -> "+hrnChild.toString()+
4729 edge.toStringDOT(hideReachability,
4730 hideSubsetReachability,
4735 } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4736 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4738 bw.write(" "+hrn.toString()+
4739 " -> "+hrnChild.toString()+
4740 edge.toStringDOT(hideReachability,
4741 hideSubsetReachability,
4744 ",color=blue,style=dashed")+
4747 bw.write(" "+hrn.toString()+
4748 " -> "+hrnChild.toString()+
4749 edge.toStringDOT(hideReachability,
4750 hideSubsetReachability,
4757 bw.write(" "+hrn.toString()+
4758 " -> "+hrnChild.toString()+
4759 edge.toStringDOT(hideReachability,
4760 hideSubsetReachability,
4767 traverseHeapRegionNodes(hrnChild,
4772 hideSubsetReachability,
4775 callerNodeIDsCopiedToCallee);
4784 // return the set of heap regions from the given allocation
4785 // site, if any, that exist in this graph
4786 protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4788 Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4790 Integer idSum = as.getSummary();
4791 if( id2hrn.containsKey(idSum) ) {
4792 out.add(id2hrn.get(idSum) );
4795 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4796 Integer idI = as.getIthOldest(i);
4797 if( id2hrn.containsKey(idI) ) {
4798 out.add(id2hrn.get(idI) );
4805 // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4806 // from the given allocation site, if any, from regions for that
4807 // site that exist in this graph
4808 protected Set<ReachTuple> getAnyExisting(AllocSite as,
4809 boolean includeARITY_ZEROORMORE,
4810 boolean includeARITY_ONE) {
4812 Set<ReachTuple> out = new HashSet<ReachTuple>();
4814 Integer idSum = as.getSummary();
4815 if( id2hrn.containsKey(idSum) ) {
4817 HeapRegionNode hrn = id2hrn.get(idSum);
4818 assert !hrn.isOutOfContext();
4820 if( !includeARITY_ZEROORMORE ) {
4821 out.add(ReachTuple.factory(hrn.getID(),
4822 true, // multi-obj region
4823 ReachTuple.ARITY_ZEROORMORE,
4828 if( includeARITY_ONE ) {
4829 out.add(ReachTuple.factory(hrn.getID(),
4830 true, // multi-object region
4831 ReachTuple.ARITY_ONE,
4837 if( !includeARITY_ONE ) {
4838 // no need to do the single-object regions that
4839 // only have an ARITY ONE possible
4843 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4845 Integer idI = as.getIthOldest(i);
4846 if( id2hrn.containsKey(idI) ) {
4848 HeapRegionNode hrn = id2hrn.get(idI);
4849 assert !hrn.isOutOfContext();
4851 out.add(ReachTuple.factory(hrn.getID(),
4852 false, // multi-object region
4853 ReachTuple.ARITY_ONE,
4863 // if an object allocated at the target site may be
4864 // reachable from both an object from root1 and an
4865 // object allocated at root2, return TRUE
4866 public boolean mayBothReachTarget(AllocSite asRoot1,
4868 AllocSite asTarget) {
4870 // consider all heap regions of the target and look
4871 // for a reach state that indicates regions of root1
4872 // and root2 might be able to reach same object
4873 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4875 // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4876 Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4877 Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4879 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4880 while( hrnItr.hasNext() ) {
4881 HeapRegionNode hrn = hrnItr.next();
4883 Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4884 while( rtItr1.hasNext() ) {
4885 ReachTuple rt1 = rtItr1.next();
4887 Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4888 while( rtItr2.hasNext() ) {
4889 ReachTuple rt2 = rtItr2.next();
4891 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4901 // similar to the method above, return TRUE if ever
4902 // more than one object from the root allocation site
4903 // may reach an object from the target site
4904 public boolean mayManyReachTarget(AllocSite asRoot,
4905 AllocSite asTarget) {
4907 // consider all heap regions of the target and look
4908 // for a reach state that multiple objects of root
4909 // might be able to reach the same object
4910 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4912 // get relevant reach tuples
4913 Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true, false);
4914 Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4916 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4917 while( hrnItr.hasNext() ) {
4918 HeapRegionNode hrn = hrnItr.next();
4920 // if any ZERORMORE tuples are here, TRUE
4921 Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4922 while( rtItr.hasNext() ) {
4923 ReachTuple rtZOM = rtItr.next();
4925 if( hrn.getAlpha().containsTuple(rtZOM) ) {
4930 // otherwise, look for any pair of ONE tuples
4931 Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4932 while( rtItr1.hasNext() ) {
4933 ReachTuple rt1 = rtItr1.next();
4935 Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4936 while( rtItr2.hasNext() ) {
4937 ReachTuple rt2 = rtItr2.next();
4943 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4957 public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4959 Set<HeapRegionNode> exhibitProofState =
4960 new HashSet<HeapRegionNode>();
4962 Iterator hrnItr = id2hrn.entrySet().iterator();
4963 while( hrnItr.hasNext() ) {
4964 Map.Entry me = (Map.Entry)hrnItr.next();
4965 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4967 ReachSet intersection =
4968 Canonical.intersection(proofOfSharing,
4971 if( !intersection.isEmpty() ) {
4972 assert !hrn.isOutOfContext();
4973 exhibitProofState.add(hrn);
4977 return exhibitProofState;
4981 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4982 HeapRegionNode hrn2) {
4983 assert hrn1 != null;
4984 assert hrn2 != null;
4986 assert !hrn1.isOutOfContext();
4987 assert !hrn2.isOutOfContext();
4989 assert belongsToThis(hrn1);
4990 assert belongsToThis(hrn2);
4992 assert !hrn1.getID().equals(hrn2.getID() );
4995 // then get the various tokens for these heap regions
4997 ReachTuple.factory(hrn1.getID(),
4998 !hrn1.isSingleObject(), // multi?
4999 ReachTuple.ARITY_ONE,
5002 ReachTuple h1star = null;
5003 if( !hrn1.isSingleObject() ) {
5005 ReachTuple.factory(hrn1.getID(),
5006 !hrn1.isSingleObject(),
5007 ReachTuple.ARITY_ZEROORMORE,
5012 ReachTuple.factory(hrn2.getID(),
5013 !hrn2.isSingleObject(),
5014 ReachTuple.ARITY_ONE,
5017 ReachTuple h2star = null;
5018 if( !hrn2.isSingleObject() ) {
5020 ReachTuple.factory(hrn2.getID(),
5021 !hrn2.isSingleObject(),
5022 ReachTuple.ARITY_ZEROORMORE,
5026 // then get the merged beta of all out-going edges from these heap
5029 ReachSet beta1 = ReachSet.factory();
5030 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
5031 while (itrEdge.hasNext()) {
5032 RefEdge edge = itrEdge.next();
5033 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
5036 ReachSet beta2 = ReachSet.factory();
5037 itrEdge = hrn2.iteratorToReferencees();
5038 while (itrEdge.hasNext()) {
5039 RefEdge edge = itrEdge.next();
5040 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
5043 ReachSet proofOfSharing = ReachSet.factory();
5046 Canonical.unionORpreds(proofOfSharing,
5047 beta1.getStatesWithBoth(h1, h2)
5050 Canonical.unionORpreds(proofOfSharing,
5051 beta2.getStatesWithBoth(h1, h2)
5054 if( !hrn1.isSingleObject() ) {
5056 Canonical.unionORpreds(proofOfSharing,
5057 beta1.getStatesWithBoth(h1star, h2)
5060 Canonical.unionORpreds(proofOfSharing,
5061 beta2.getStatesWithBoth(h1star, h2)
5065 if( !hrn2.isSingleObject() ) {
5067 Canonical.unionORpreds(proofOfSharing,
5068 beta1.getStatesWithBoth(h1, h2star)
5071 Canonical.unionORpreds(proofOfSharing,
5072 beta2.getStatesWithBoth(h1, h2star)
5076 if( !hrn1.isSingleObject() &&
5077 !hrn2.isSingleObject()
5080 Canonical.unionORpreds(proofOfSharing,
5081 beta1.getStatesWithBoth(h1star, h2star)
5084 Canonical.unionORpreds(proofOfSharing,
5085 beta2.getStatesWithBoth(h1star, h2star)
5089 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5090 if( !proofOfSharing.isEmpty() ) {
5091 common = findCommonReachableNodes(proofOfSharing);
5092 if( !DISABLE_STRONG_UPDATES &&
5093 !DISABLE_GLOBAL_SWEEP
5095 assert !common.isEmpty();
5102 // this version of the above method checks whether there is sharing
5103 // among the objects in a summary node
5104 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
5106 assert hrn.isNewSummary();
5107 assert !hrn.isOutOfContext();
5108 assert belongsToThis(hrn);
5111 ReachTuple.factory(hrn.getID(),
5113 ReachTuple.ARITY_ZEROORMORE,
5116 // then get the merged beta of all out-going edges from
5119 ReachSet beta = ReachSet.factory();
5120 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
5121 while (itrEdge.hasNext()) {
5122 RefEdge edge = itrEdge.next();
5123 beta = Canonical.unionORpreds(beta, edge.getBeta());
5126 ReachSet proofOfSharing = ReachSet.factory();
5129 Canonical.unionORpreds(proofOfSharing,
5130 beta.getStatesWithBoth(hstar, hstar)
5133 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5134 if( !proofOfSharing.isEmpty() ) {
5135 common = findCommonReachableNodes(proofOfSharing);
5136 if( !DISABLE_STRONG_UPDATES &&
5137 !DISABLE_GLOBAL_SWEEP
5139 assert !common.isEmpty();
5147 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5148 Integer paramIndex1,
5149 Integer paramIndex2) {
5151 // get parameter's heap regions
5152 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5153 assert this.hasVariable(paramTemp1);
5154 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5157 if( !(paramVar1.getNumReferencees() == 1) ) {
5158 System.out.println("\n fm="+fm+"\n param="+paramTemp1);
5159 writeGraph("whatup");
5163 assert paramVar1.getNumReferencees() == 1;
5164 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5165 HeapRegionNode hrnParam1 = paramEdge1.getDst();
5167 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5168 assert this.hasVariable(paramTemp2);
5169 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5171 if( !(paramVar2.getNumReferencees() == 1) ) {
5172 System.out.println("\n fm="+fm+"\n param="+paramTemp2);
5173 writeGraph("whatup");
5176 assert paramVar2.getNumReferencees() == 1;
5177 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5178 HeapRegionNode hrnParam2 = paramEdge2.getDst();
5180 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5181 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5186 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5190 // get parameter's heap regions
5191 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5192 assert this.hasVariable(paramTemp);
5193 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5194 assert paramVar.getNumReferencees() == 1;
5195 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5196 HeapRegionNode hrnParam = paramEdge.getDst();
5199 HeapRegionNode hrnSummary=null;
5200 if(id2hrn.containsKey(as.getSummary())) {
5201 // if summary node doesn't exist, ignore this case
5202 hrnSummary = id2hrn.get(as.getSummary());
5203 assert hrnSummary != null;
5206 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5207 if(hrnSummary!=null) {
5208 common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5211 // check for other nodes
5212 for (int i = 0; i < as.getAllocationDepth(); ++i) {
5214 assert id2hrn.containsKey(as.getIthOldest(i));
5215 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5216 assert hrnIthOldest != null;
5218 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5225 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5228 // get summary node 1's alpha
5229 Integer idSum1 = as1.getSummary();
5230 HeapRegionNode hrnSum1=null;
5231 if(id2hrn.containsKey(idSum1)) {
5232 hrnSum1 = id2hrn.get(idSum1);
5235 // get summary node 2's alpha
5236 Integer idSum2 = as2.getSummary();
5237 HeapRegionNode hrnSum2=null;
5238 if(id2hrn.containsKey(idSum2)) {
5239 hrnSum2 = id2hrn.get(idSum2);
5242 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5243 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5244 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5248 // ask if objects from this summary share among each other
5249 common.addAll(mayReachSharedObjects(hrnSum1));
5252 // check sum2 against alloc1 nodes
5254 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5255 Integer idI1 = as1.getIthOldest(i);
5256 assert id2hrn.containsKey(idI1);
5257 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5258 assert hrnI1 != null;
5259 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5262 // also ask if objects from this summary share among each other
5263 common.addAll(mayReachSharedObjects(hrnSum2));
5266 // check sum1 against alloc2 nodes
5267 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5268 Integer idI2 = as2.getIthOldest(i);
5269 assert id2hrn.containsKey(idI2);
5270 HeapRegionNode hrnI2 = id2hrn.get(idI2);
5271 assert hrnI2 != null;
5274 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5277 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5278 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5279 Integer idI1 = as1.getIthOldest(j);
5281 // if these are the same site, don't look for the same token, no
5283 // different tokens of the same site could alias together though
5284 if (idI1.equals(idI2)) {
5288 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5290 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5297 public void makeInaccessible(Set<TempDescriptor> vars) {
5298 inaccessibleVars.addAll(vars);
5301 public void makeInaccessible(TempDescriptor td) {
5302 inaccessibleVars.add(td);
5305 public void makeAccessible(TempDescriptor td) {
5306 inaccessibleVars.remove(td);
5309 public boolean isAccessible(TempDescriptor td) {
5310 return !inaccessibleVars.contains(td);
5313 public Set<TempDescriptor> getInaccessibleVars() {
5314 return inaccessibleVars;
5320 public Set<Alloc> canPointTo( TempDescriptor x ) {
5322 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5323 // if we don't care to track it, return null which means
5324 // "a client of this result shouldn't care either"
5325 return HeapAnalysis.DONTCARE_PTR;
5328 Set<Alloc> out = new HashSet<Alloc>();
5330 VariableNode vn = getVariableNodeNoMutation( x );
5332 // the empty set means "can't point to anything"
5336 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5337 while( edgeItr.hasNext() ) {
5338 HeapRegionNode hrn = edgeItr.next().getDst();
5339 out.add( hrn.getAllocSite() );
5347 public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5349 TypeDescriptor fieldType ) {
5351 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5352 // if we don't care to track it, return null which means
5353 // "a client of this result shouldn't care either"
5354 return HeapAnalysis.DONTCARE_DREF;
5357 Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5359 VariableNode vn = getVariableNodeNoMutation( x );
5361 // the empty table means "x can't point to anything"
5365 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5366 while( edgeItr.hasNext() ) {
5367 HeapRegionNode hrn = edgeItr.next().getDst();
5368 Alloc key = hrn.getAllocSite();
5370 if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5371 // if we don't care to track it, put no entry which means
5372 // "a client of this result shouldn't care either"
5373 out.put( key, HeapAnalysis.DONTCARE_PTR );
5377 Set<Alloc> moreValues = new HashSet<Alloc>();
5378 Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5379 while( edgeItr2.hasNext() ) {
5380 RefEdge edge = edgeItr2.next();
5382 if( field.equals( edge.getField() ) ) {
5383 moreValues.add( edge.getDst().getAllocSite() );
5387 if( out.containsKey( key ) ) {
5388 out.get( key ).addAll( moreValues );
5390 out.put( key, moreValues );
5400 public TempDescriptor findVariableByName( String name ) {
5402 for( TempDescriptor td: td2vn.keySet() ) {
5403 if( td.getSymbol().contains( name ) ) {