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 if( !DISABLE_GLOBAL_SWEEP ) {
2314 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2317 rg.addRefEdge(hrnCalleeAndOutContext,
2319 new RefEdge(hrnCalleeAndOutContext,
2322 reCaller.getField(),
2323 toCalleeContext(reCaller.getBeta(),
2328 toCalleeContext(reCaller.getTaints(),
2334 // the out-of-context edge already exists
2335 oocEdgeExisting.setBeta(Canonical.unionORpreds(oocEdgeExisting.getBeta(),
2336 toCalleeContext(reCaller.getBeta(),
2343 oocEdgeExisting.setPreds(Canonical.join(oocEdgeExisting.getPreds(),
2348 oocEdgeExisting.setTaints(Canonical.unionORpreds(oocEdgeExisting.getTaints(),
2349 toCalleeContext(reCaller.getTaints(),
2355 HeapRegionNode hrnCalleeAndOutContext =
2356 (HeapRegionNode) oocEdgeExisting.getSrc();
2357 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2358 toCalleeContext(oocReach,
2365 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2370 if( writeDebugDOTs ) {
2371 debugGraphPrefix = String.format("call%03d", debugCallSiteVisitCounter);
2372 rg.writeGraph(debugGraphPrefix+"calleeview",
2373 resolveMethodDebugDOTwriteLabels,
2374 resolveMethodDebugDOTselectTemps,
2375 resolveMethodDebugDOTpruneGarbage,
2376 resolveMethodDebugDOThideReach,
2377 resolveMethodDebugDOThideSubsetReach,
2378 resolveMethodDebugDOThidePreds,
2379 resolveMethodDebugDOThideEdgeTaints);
2385 private static Hashtable<String, Integer> oocid2hrnid =
2386 new Hashtable<String, Integer>();
2389 private static boolean resolveMethodDebugDOTwriteLabels = true;
2390 private static boolean resolveMethodDebugDOTselectTemps = true;
2391 private static boolean resolveMethodDebugDOTpruneGarbage = true;
2392 private static boolean resolveMethodDebugDOThideReach = false;
2393 private static boolean resolveMethodDebugDOThideSubsetReach = true;
2394 private static boolean resolveMethodDebugDOThidePreds = false;
2395 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
2397 static String debugGraphPrefix;
2398 static int debugCallSiteVisitCounter;
2399 static int debugCallSiteVisitStartCapture;
2400 static int debugCallSiteNumVisitsToCapture;
2401 static boolean debugCallSiteStopAfter;
2405 resolveMethodCall(FlatCall fc,
2406 FlatMethod fmCallee,
2407 ReachGraph rgCallee,
2408 Set<Integer> callerNodeIDsCopiedToCallee,
2409 boolean writeDebugDOTs
2412 if( writeDebugDOTs ) {
2414 System.out.println(" Writing out visit "+
2415 debugCallSiteVisitCounter+
2416 " to debug call site");
2418 debugGraphPrefix = String.format("call%03d",
2419 debugCallSiteVisitCounter);
2421 rgCallee.writeGraph(debugGraphPrefix+"callee",
2422 resolveMethodDebugDOTwriteLabels,
2423 resolveMethodDebugDOTselectTemps,
2424 resolveMethodDebugDOTpruneGarbage,
2425 resolveMethodDebugDOThideReach,
2426 resolveMethodDebugDOThideSubsetReach,
2427 resolveMethodDebugDOThidePreds,
2428 resolveMethodDebugDOThideEdgeTaints);
2430 writeGraph(debugGraphPrefix+"caller00In",
2431 resolveMethodDebugDOTwriteLabels,
2432 resolveMethodDebugDOTselectTemps,
2433 resolveMethodDebugDOTpruneGarbage,
2434 resolveMethodDebugDOThideReach,
2435 resolveMethodDebugDOThideSubsetReach,
2436 resolveMethodDebugDOThidePreds,
2437 resolveMethodDebugDOThideEdgeTaints,
2438 callerNodeIDsCopiedToCallee);
2443 // method call transfer function steps:
2444 // 1. Use current callee-reachable heap (CRH) to test callee
2445 // predicates and mark what will be coming in.
2446 // 2. Wipe CRH out of caller.
2447 // 3. Transplant marked callee parts in:
2448 // a) bring in nodes
2449 // b) bring in callee -> callee edges
2450 // c) resolve out-of-context -> callee edges
2451 // d) assign return value
2452 // 4. Collapse shadow nodes down
2453 // 5. Global sweep it.
2456 // 1. mark what callee elements have satisfied predicates
2457 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
2458 new Hashtable<HeapRegionNode, ExistPredSet>();
2460 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
2461 new Hashtable<RefEdge, ExistPredSet>();
2463 Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
2464 calleeNode2calleeStatesSatisfied =
2465 new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
2467 Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
2468 calleeEdge2calleeStatesSatisfied =
2469 new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
2471 Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
2472 calleeEdge2calleeTaintsSatisfied =
2473 new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
2475 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
2476 new Hashtable< RefEdge, Set<RefSrcNode> >();
2480 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2481 while( meItr.hasNext() ) {
2482 Map.Entry me = (Map.Entry)meItr.next();
2483 Integer id = (Integer) me.getKey();
2484 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2486 // if a callee element's predicates are satisfied then a set
2487 // of CALLER predicates is returned: they are the predicates
2488 // that the callee element moved into the caller context
2489 // should have, and it is inefficient to find this again later
2490 ExistPredSet predsIfSatis =
2491 hrnCallee.getPreds().isSatisfiedBy(this,
2492 callerNodeIDsCopiedToCallee,
2495 if( predsIfSatis != null ) {
2496 calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
2498 // otherwise don't bother looking at edges to this node
2504 // since the node is coming over, find out which reach
2505 // states on it should come over, too
2506 assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
2508 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2509 while( stateItr.hasNext() ) {
2510 ReachState stateCallee = stateItr.next();
2513 stateCallee.getPreds().isSatisfiedBy(this,
2514 callerNodeIDsCopiedToCallee,
2516 if( predsIfSatis != null ) {
2518 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2519 calleeNode2calleeStatesSatisfied.get(hrnCallee);
2521 if( calleeStatesSatisfied == null ) {
2522 calleeStatesSatisfied =
2523 new Hashtable<ReachState, ExistPredSet>();
2525 calleeNode2calleeStatesSatisfied.put(hrnCallee, calleeStatesSatisfied);
2528 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2532 // then look at edges to the node
2533 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2534 while( reItr.hasNext() ) {
2535 RefEdge reCallee = reItr.next();
2536 RefSrcNode rsnCallee = reCallee.getSrc();
2538 // (caller local variables to in-context heap regions)
2539 // have an (out-of-context heap region -> in-context heap region)
2540 // abstraction in the callEE, so its true we never need to
2541 // look at a (var node -> heap region) edge in callee to bring
2542 // those over for the call site transfer, except for the special
2543 // case of *RETURN var* -> heap region edges.
2544 // What about (param var->heap region)
2545 // edges in callee? They are dealt with below this loop.
2547 if( rsnCallee instanceof VariableNode ) {
2549 // looking for the return-value variable only
2550 VariableNode vnCallee = (VariableNode) rsnCallee;
2551 if( vnCallee.getTempDescriptor() != tdReturn ) {
2555 TempDescriptor returnTemp = fc.getReturnTemp();
2556 if( returnTemp == null ||
2557 !DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2562 // note that the assignment of the return value is to a
2563 // variable in the caller which is out-of-context with
2564 // respect to the callee
2565 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2566 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2567 rsnCallers.add(vnLhsCaller);
2568 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2572 // for HeapRegionNode callee sources...
2574 // first see if the source is out-of-context, and only
2575 // proceed with this edge if we find some caller-context
2577 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2578 boolean matchedOutOfContext = false;
2580 if( !hrnSrcCallee.isOutOfContext() ) {
2583 hrnSrcCallee.getPreds().isSatisfiedBy(this,
2584 callerNodeIDsCopiedToCallee,
2586 if( predsIfSatis != null ) {
2587 calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
2589 // otherwise forget this edge
2594 // hrnSrcCallee is out-of-context
2595 assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
2597 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2599 // use the isSatisfiedBy with a non-null callers set to capture
2600 // nodes in the caller that match the predicates
2601 reCallee.getPreds().isSatisfiedBy( this,
2602 callerNodeIDsCopiedToCallee,
2605 if( !rsnCallers.isEmpty() ) {
2606 matchedOutOfContext = true;
2607 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2611 if( hrnSrcCallee.isOutOfContext() &&
2612 !matchedOutOfContext ) {
2619 reCallee.getPreds().isSatisfiedBy(this,
2620 callerNodeIDsCopiedToCallee,
2624 if( predsIfSatis != null ) {
2625 calleeEdgesSatisfied.put(reCallee, predsIfSatis);
2627 // since the edge is coming over, find out which reach
2628 // states on it should come over, too
2629 assert calleeEdge2calleeStatesSatisfied.get(reCallee) == null;
2631 stateItr = reCallee.getBeta().iterator();
2632 while( stateItr.hasNext() ) {
2633 ReachState stateCallee = stateItr.next();
2636 stateCallee.getPreds().isSatisfiedBy(this,
2637 callerNodeIDsCopiedToCallee,
2639 if( predsIfSatis != null ) {
2641 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2642 calleeEdge2calleeStatesSatisfied.get(reCallee);
2644 if( calleeStatesSatisfied == null ) {
2645 calleeStatesSatisfied =
2646 new Hashtable<ReachState, ExistPredSet>();
2648 calleeEdge2calleeStatesSatisfied.put(reCallee, calleeStatesSatisfied);
2651 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2655 // since the edge is coming over, find out which taints
2656 // on it should come over, too
2657 assert calleeEdge2calleeTaintsSatisfied.get(reCallee) == null;
2659 Iterator<Taint> tItr = reCallee.getTaints().iterator();
2660 while( tItr.hasNext() ) {
2661 Taint tCallee = tItr.next();
2664 tCallee.getPreds().isSatisfiedBy(this,
2665 callerNodeIDsCopiedToCallee,
2667 if( predsIfSatis != null ) {
2669 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2670 calleeEdge2calleeTaintsSatisfied.get(reCallee);
2672 if( calleeTaintsSatisfied == null ) {
2673 calleeTaintsSatisfied =
2674 new Hashtable<Taint, ExistPredSet>();
2676 calleeEdge2calleeTaintsSatisfied.put(reCallee, calleeTaintsSatisfied);
2679 calleeTaintsSatisfied.put(tCallee, predsIfSatis);
2686 if( writeDebugDOTs ) {
2687 writeGraph(debugGraphPrefix+"caller20BeforeWipe",
2688 resolveMethodDebugDOTwriteLabels,
2689 resolveMethodDebugDOTselectTemps,
2690 resolveMethodDebugDOTpruneGarbage,
2691 resolveMethodDebugDOThideReach,
2692 resolveMethodDebugDOThideSubsetReach,
2693 resolveMethodDebugDOThidePreds,
2694 resolveMethodDebugDOThideEdgeTaints);
2698 // 2. predicates tested, ok to wipe out caller part
2699 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2700 while( hrnItr.hasNext() ) {
2701 Integer hrnID = hrnItr.next();
2702 HeapRegionNode hrnCaller = id2hrn.get(hrnID);
2703 assert hrnCaller != null;
2705 // when clearing off nodes, also eliminate variable
2707 wipeOut(hrnCaller, true);
2710 // if we are assigning the return value to something, clobber now
2711 // as part of the wipe
2712 TempDescriptor returnTemp = fc.getReturnTemp();
2713 if( returnTemp != null &&
2714 DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2717 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2718 clearRefEdgesFrom(vnLhsCaller, null, null, true);
2724 if( writeDebugDOTs ) {
2725 writeGraph(debugGraphPrefix+"caller30BeforeAddingNodes",
2726 resolveMethodDebugDOTwriteLabels,
2727 resolveMethodDebugDOTselectTemps,
2728 resolveMethodDebugDOTpruneGarbage,
2729 resolveMethodDebugDOThideReach,
2730 resolveMethodDebugDOThideSubsetReach,
2731 resolveMethodDebugDOThidePreds,
2732 resolveMethodDebugDOThideEdgeTaints);
2738 // 3. callee elements with satisfied preds come in, note that
2739 // the mapping of elements satisfied to preds is like this:
2740 // A callee element EE has preds EEp that are satisfied by
2741 // some caller element ER. We bring EE into the caller
2742 // context as ERee with the preds of ER, namely ERp, which
2743 // in the following algorithm is the value in the mapping
2746 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2747 while( satisItr.hasNext() ) {
2748 Map.Entry me = (Map.Entry)satisItr.next();
2749 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2750 ExistPredSet preds = (ExistPredSet) me.getValue();
2752 // TODO: I think its true that the current implementation uses
2753 // the type of the OOC region and the predicates OF THE EDGE from
2754 // it to link everything up in caller context, so that's why we're
2755 // skipping this... maybe that's a sillier way to do it?
2756 if( hrnCallee.isOutOfContext() ) {
2760 AllocSite as = hrnCallee.getAllocSite();
2763 Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
2765 HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
2766 if( hrnCaller == null ) {
2768 createNewHeapRegionNode(hrnIDshadow, // id or null to generate a new one
2769 hrnCallee.isSingleObject(), // single object?
2770 hrnCallee.isNewSummary(), // summary?
2771 false, // out-of-context?
2772 hrnCallee.getType(), // type
2773 hrnCallee.getAllocSite(), // allocation site
2774 toCallerContext(hrnCallee.getInherent(),
2775 calleeNode2calleeStatesSatisfied.get(hrnCallee) ), // inherent reach
2776 null, // current reach
2777 predsEmpty, // predicates
2778 hrnCallee.getDescription() // description
2781 assert hrnCaller.isWiped();
2784 hrnCaller.setAlpha(toCallerContext(hrnCallee.getAlpha(),
2785 calleeNode2calleeStatesSatisfied.get(hrnCallee)
2789 hrnCaller.setPreds(preds);
2796 if( writeDebugDOTs ) {
2797 writeGraph(debugGraphPrefix+"caller31BeforeAddingEdges",
2798 resolveMethodDebugDOTwriteLabels,
2799 resolveMethodDebugDOTselectTemps,
2800 resolveMethodDebugDOTpruneGarbage,
2801 resolveMethodDebugDOThideReach,
2802 resolveMethodDebugDOThideSubsetReach,
2803 resolveMethodDebugDOThidePreds,
2804 resolveMethodDebugDOThideEdgeTaints);
2808 // set these up during the next procedure so after
2809 // the caller has all of its nodes and edges put
2810 // back together we can propagate the callee's
2811 // reach changes backwards into the caller graph
2812 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2814 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2815 new Hashtable<RefEdge, ChangeSet>();
2818 // 3.b) callee -> callee edges AND out-of-context -> callee
2819 // which includes return temp -> callee edges now, too
2820 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2821 while( satisItr.hasNext() ) {
2822 Map.Entry me = (Map.Entry)satisItr.next();
2823 RefEdge reCallee = (RefEdge) me.getKey();
2824 ExistPredSet preds = (ExistPredSet) me.getValue();
2826 HeapRegionNode hrnDstCallee = reCallee.getDst();
2827 AllocSite asDst = hrnDstCallee.getAllocSite();
2828 allocSites.add(asDst);
2830 Integer hrnIDDstShadow =
2831 asDst.getShadowIDfromID(hrnDstCallee.getID() );
2833 HeapRegionNode hrnDstCaller = id2hrn.get(hrnIDDstShadow);
2834 assert hrnDstCaller != null;
2837 RefSrcNode rsnCallee = reCallee.getSrc();
2839 Set<RefSrcNode> rsnCallers =
2840 new HashSet<RefSrcNode>();
2842 Set<RefSrcNode> oocCallers =
2843 calleeEdges2oocCallerSrcMatches.get(reCallee);
2845 if( rsnCallee instanceof HeapRegionNode ) {
2846 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2847 if( hrnCalleeSrc.isOutOfContext() ) {
2848 assert oocCallers != null;
2853 if( oocCallers == null ) {
2854 // there are no out-of-context matches, so it's
2855 // either a param/arg var or one in-context heap region
2856 if( rsnCallee instanceof VariableNode ) {
2857 // variable -> node in the callee should only
2858 // come into the caller if its from a param var
2859 VariableNode vnCallee = (VariableNode) rsnCallee;
2860 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2861 TempDescriptor tdArg = fc.getArgMatchingParam(fmCallee,
2863 if( tdArg == null ) {
2864 // this means the variable isn't a parameter, its local
2865 // to the callee so we ignore it in call site transfer
2866 // shouldn't this NEVER HAPPEN?
2870 rsnCallers.add(this.getVariableNodeFromTemp(tdArg) );
2873 // otherwise source is in context, one region
2875 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2877 // translate an in-context node to shadow
2878 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2879 allocSites.add(asSrc);
2881 Integer hrnIDSrcShadow =
2882 asSrc.getShadowIDfromID(hrnSrcCallee.getID() );
2884 HeapRegionNode hrnSrcCallerShadow =
2885 this.id2hrn.get(hrnIDSrcShadow);
2887 assert hrnSrcCallerShadow != null;
2889 rsnCallers.add(hrnSrcCallerShadow);
2893 // otherwise we have a set of out-of-context srcs
2894 // that should NOT be translated to shadow nodes
2895 assert !oocCallers.isEmpty();
2896 rsnCallers.addAll(oocCallers);
2899 // now make all caller edges we've identified from
2900 // this callee edge with a satisfied predicate
2901 assert !rsnCallers.isEmpty();
2902 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2903 while( rsnItr.hasNext() ) {
2904 RefSrcNode rsnCaller = rsnItr.next();
2906 RefEdge reCaller = new RefEdge(rsnCaller,
2909 reCallee.getField(),
2910 toCallerContext(reCallee.getBeta(),
2911 calleeEdge2calleeStatesSatisfied.get(reCallee) ),
2913 toCallerContext(reCallee.getTaints(),
2914 calleeEdge2calleeTaintsSatisfied.get(reCallee) )
2917 ChangeSet cs = ChangeSet.factory();
2918 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2919 while( rsItr.hasNext() ) {
2920 ReachState state = rsItr.next();
2921 ExistPredSet predsPreCallee = state.getPreds();
2923 if( state.isEmpty() ) {
2927 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2928 while( predItr.hasNext() ) {
2929 ExistPred pred = predItr.next();
2930 ReachState old = pred.ne_state;
2936 cs = Canonical.add(cs,
2937 ChangeTuple.factory(old,
2944 // we're just going to use the convenient "merge-if-exists"
2945 // edge call below, but still take a separate look if there
2946 // is an existing caller edge to build change sets properly
2947 if( !cs.isEmpty() ) {
2948 RefEdge edgeExisting = rsnCaller.getReferenceTo(hrnDstCaller,
2952 if( edgeExisting != null ) {
2953 ChangeSet csExisting = edgePlannedChanges.get(edgeExisting);
2954 if( csExisting == null ) {
2955 csExisting = ChangeSet.factory();
2957 edgePlannedChanges.put(edgeExisting,
2958 Canonical.union(csExisting,
2963 edgesForPropagation.add(reCaller);
2964 assert !edgePlannedChanges.containsKey(reCaller);
2965 edgePlannedChanges.put(reCaller, cs);
2969 // then add new caller edge or merge
2970 addEdgeOrMergeWithExisting(reCaller);
2978 if( writeDebugDOTs ) {
2979 writeGraph(debugGraphPrefix+"caller38propagateReach",
2980 resolveMethodDebugDOTwriteLabels,
2981 resolveMethodDebugDOTselectTemps,
2982 resolveMethodDebugDOTpruneGarbage,
2983 resolveMethodDebugDOThideReach,
2984 resolveMethodDebugDOThideSubsetReach,
2985 resolveMethodDebugDOThidePreds,
2986 resolveMethodDebugDOThideEdgeTaints);
2989 // propagate callee reachability changes to the rest
2990 // of the caller graph edges
2991 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2993 propagateTokensOverEdges( edgesForPropagation, // source edges
2994 edgePlannedChanges, // map src edge to change set
2995 edgesUpdated, // list of updated edges
2998 // commit beta' (beta<-betaNew)
2999 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
3000 while( edgeItr.hasNext() ) {
3001 edgeItr.next().applyBetaNew();
3010 if( writeDebugDOTs ) {
3011 writeGraph(debugGraphPrefix+"caller40BeforeShadowMerge",
3012 resolveMethodDebugDOTwriteLabels,
3013 resolveMethodDebugDOTselectTemps,
3014 resolveMethodDebugDOTpruneGarbage,
3015 resolveMethodDebugDOThideReach,
3016 resolveMethodDebugDOThideSubsetReach,
3017 resolveMethodDebugDOThidePreds,
3018 resolveMethodDebugDOThideEdgeTaints);
3022 // 4) merge shadow nodes so alloc sites are back to k
3023 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
3024 while( asItr.hasNext() ) {
3025 // for each allocation site do the following to merge
3026 // shadow nodes (newest from callee) with any existing
3027 // look for the newest normal and newest shadow "slot"
3028 // not being used, transfer normal to shadow. Keep
3029 // doing this until there are no more normal nodes, or
3030 // no empty shadow slots: then merge all remaining normal
3031 // nodes into the shadow summary. Finally, convert all
3032 // shadow to their normal versions.
3033 AllocSite as = asItr.next();
3037 while( ageNorm < allocationDepth &&
3038 ageShad < allocationDepth ) {
3040 // first, are there any normal nodes left?
3041 Integer idNorm = as.getIthOldest(ageNorm);
3042 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
3043 if( hrnNorm == null ) {
3044 // no, this age of normal node not in the caller graph
3049 // yes, a normal node exists, is there an empty shadow
3050 // "slot" to transfer it onto?
3051 HeapRegionNode hrnShad = getIthNode(as, ageShad, true);
3052 if( !hrnShad.isWiped() ) {
3053 // no, this age of shadow node is not empty
3058 // yes, this shadow node is empty
3059 transferOnto(hrnNorm, hrnShad);
3064 // now, while there are still normal nodes but no shadow
3065 // slots, merge normal nodes into the shadow summary
3066 while( ageNorm < allocationDepth ) {
3068 // first, are there any normal nodes left?
3069 Integer idNorm = as.getIthOldest(ageNorm);
3070 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
3071 if( hrnNorm == null ) {
3072 // no, this age of normal node not in the caller graph
3077 // yes, a normal node exists, so get the shadow summary
3078 HeapRegionNode summShad = getSummaryNode(as, true);
3079 mergeIntoSummary(hrnNorm, summShad);
3081 // now tokens in reachability sets need to age also
3082 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3083 while( itrAllHRNodes.hasNext() ) {
3084 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
3085 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
3087 ageTuplesFrom(as, hrnToAge);
3089 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
3090 while( itrEdges.hasNext() ) {
3091 ageTuplesFrom(as, itrEdges.next() );
3098 // if there is a normal summary, merge it into shadow summary
3099 Integer idNorm = as.getSummary();
3100 HeapRegionNode summNorm = id2hrn.get(idNorm);
3101 if( summNorm != null ) {
3102 HeapRegionNode summShad = getSummaryNode(as, true);
3103 mergeIntoSummary(summNorm, summShad);
3106 // finally, flip all existing shadow nodes onto the normal
3107 for( int i = 0; i < allocationDepth; ++i ) {
3108 Integer idShad = as.getIthOldestShadow(i);
3109 HeapRegionNode hrnShad = id2hrn.get(idShad);
3110 if( hrnShad != null ) {
3112 HeapRegionNode hrnNorm = getIthNode(as, i, false);
3113 assert hrnNorm.isWiped();
3114 transferOnto(hrnShad, hrnNorm);
3118 Integer idShad = as.getSummaryShadow();
3119 HeapRegionNode summShad = id2hrn.get(idShad);
3120 if( summShad != null ) {
3121 summNorm = getSummaryNode(as, false);
3122 transferOnto(summShad, summNorm);
3131 if( writeDebugDOTs ) {
3132 writeGraph(debugGraphPrefix+"caller45BeforeUnshadow",
3133 resolveMethodDebugDOTwriteLabels,
3134 resolveMethodDebugDOTselectTemps,
3135 resolveMethodDebugDOTpruneGarbage,
3136 resolveMethodDebugDOThideReach,
3137 resolveMethodDebugDOThideSubsetReach,
3138 resolveMethodDebugDOThidePreds,
3139 resolveMethodDebugDOThideEdgeTaints);
3143 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3144 while( itrAllHRNodes.hasNext() ) {
3145 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
3146 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3148 hrn.setAlpha(unshadow(hrn.getAlpha() ) );
3150 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
3151 while( itrEdges.hasNext() ) {
3152 RefEdge re = itrEdges.next();
3153 re.setBeta(unshadow(re.getBeta() ) );
3160 if( writeDebugDOTs ) {
3161 writeGraph(debugGraphPrefix+"caller50BeforeGlobalSweep",
3162 resolveMethodDebugDOTwriteLabels,
3163 resolveMethodDebugDOTselectTemps,
3164 resolveMethodDebugDOTpruneGarbage,
3165 resolveMethodDebugDOThideReach,
3166 resolveMethodDebugDOThideSubsetReach,
3167 resolveMethodDebugDOThidePreds,
3168 resolveMethodDebugDOThideEdgeTaints);
3173 if( !DISABLE_GLOBAL_SWEEP ) {
3178 if( writeDebugDOTs ) {
3179 writeGraph(debugGraphPrefix+"caller90AfterTransfer",
3180 resolveMethodDebugDOTwriteLabels,
3181 resolveMethodDebugDOTselectTemps,
3182 resolveMethodDebugDOTpruneGarbage,
3183 resolveMethodDebugDOThideReach,
3184 resolveMethodDebugDOThideSubsetReach,
3185 resolveMethodDebugDOThidePreds,
3186 resolveMethodDebugDOThideEdgeTaints);
3192 ////////////////////////////////////////////////////
3194 // Abstract garbage collection simply removes
3195 // heap region nodes that are not mechanically
3196 // reachable from a root set. This step is
3197 // essential for testing node and edge existence
3198 // predicates efficiently
3200 ////////////////////////////////////////////////////
3201 public void abstractGarbageCollect(Set<TempDescriptor> liveSet) {
3203 // calculate a root set, will be different for Java
3204 // version of analysis versus Bamboo version
3205 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3207 // visit every variable in graph while building root
3208 // set, and do iterating on a copy, so we can remove
3209 // dead variables while we're at this
3210 Iterator makeCopyItr = td2vn.entrySet().iterator();
3211 Set entrysCopy = new HashSet();
3212 while( makeCopyItr.hasNext() ) {
3213 entrysCopy.add(makeCopyItr.next() );
3216 Iterator eItr = entrysCopy.iterator();
3217 while( eItr.hasNext() ) {
3218 Map.Entry me = (Map.Entry)eItr.next();
3219 TempDescriptor td = (TempDescriptor) me.getKey();
3220 VariableNode vn = (VariableNode) me.getValue();
3222 if( liveSet.contains(td) ) {
3226 // dead var, remove completely from graph
3228 clearRefEdgesFrom(vn, null, null, true);
3232 // everything visited in a traversal is
3233 // considered abstractly live
3234 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3236 while( !toVisit.isEmpty() ) {
3237 RefSrcNode rsn = toVisit.iterator().next();
3238 toVisit.remove(rsn);
3241 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3242 while( hrnItr.hasNext() ) {
3243 RefEdge edge = hrnItr.next();
3244 HeapRegionNode hrn = edge.getDst();
3246 if( !visited.contains(hrn) ) {
3252 // get a copy of the set to iterate over because
3253 // we're going to monkey with the graph when we
3254 // identify a garbage node
3255 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3256 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3257 while( hrnItr.hasNext() ) {
3258 hrnAllPrior.add(hrnItr.next() );
3261 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3262 while( hrnAllItr.hasNext() ) {
3263 HeapRegionNode hrn = hrnAllItr.next();
3265 if( !visited.contains(hrn) ) {
3267 // heap region nodes are compared across ReachGraph
3268 // objects by their integer ID, so when discarding
3269 // garbage nodes we must also discard entries in
3270 // the ID -> heap region hashtable.
3271 id2hrn.remove(hrn.getID() );
3273 // RefEdge objects are two-way linked between
3274 // nodes, so when a node is identified as garbage,
3275 // actively clear references to and from it so
3276 // live nodes won't have dangling RefEdge's
3279 // if we just removed the last node from an allocation
3280 // site, it should be taken out of the ReachGraph's list
3281 AllocSite as = hrn.getAllocSite();
3282 if( !hasNodesOf(as) ) {
3283 allocSites.remove(as);
3289 protected boolean hasNodesOf(AllocSite as) {
3290 if( id2hrn.containsKey(as.getSummary() ) ) {
3294 for( int i = 0; i < allocationDepth; ++i ) {
3295 if( id2hrn.containsKey(as.getIthOldest(i) ) ) {
3303 ////////////////////////////////////////////////////
3305 // This global sweep is an optional step to prune
3306 // reachability sets that are not internally
3307 // consistent with the global graph. It should be
3308 // invoked after strong updates or method calls.
3310 ////////////////////////////////////////////////////
3311 public void globalSweep() {
3313 // boldB is part of the phase 1 sweep
3314 // it has an in-context table and an out-of-context table
3315 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3316 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3318 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3319 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3321 // visit every heap region to initialize alphaNew and betaNew,
3322 // and make a map of every hrnID to the source nodes it should
3323 // propagate forward from. In-context flagged hrnID's propagate
3324 // from only the in-context node they name, but out-of-context
3325 // ID's may propagate from several out-of-context nodes
3326 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3327 new Hashtable< Integer, Set<HeapRegionNode> >();
3329 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3330 new Hashtable< Integer, Set<HeapRegionNode> >();
3333 Iterator itrHrns = id2hrn.entrySet().iterator();
3334 while( itrHrns.hasNext() ) {
3335 Map.Entry me = (Map.Entry)itrHrns.next();
3336 Integer hrnID = (Integer) me.getKey();
3337 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3339 // assert that this node and incoming edges have clean alphaNew
3340 // and betaNew sets, respectively
3341 assert rsetEmpty.equals(hrn.getAlphaNew() );
3343 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3344 while( itrRers.hasNext() ) {
3345 RefEdge edge = itrRers.next();
3346 assert rsetEmpty.equals(edge.getBetaNew() );
3349 // make a mapping of IDs to heap regions they propagate from
3350 if( hrn.isFlagged() ) {
3351 assert !hrn.isOutOfContext();
3352 assert !icID2srcs.containsKey(hrn.getID() );
3354 // in-context flagged node IDs simply propagate from the
3356 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3358 icID2srcs.put(hrn.getID(), srcs);
3361 if( hrn.isOutOfContext() ) {
3362 assert !hrn.isFlagged();
3364 // the reachability states on an out-of-context
3365 // node are not really important (combinations of
3366 // IDs or arity)--what matters is that the states
3367 // specify which nodes this out-of-context node
3368 // stands in for. For example, if the state [17?, 19*]
3369 // appears on the ooc node, it may serve as a source
3370 // for node 17? and a source for node 19.
3371 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3372 while( stateItr.hasNext() ) {
3373 ReachState state = stateItr.next();
3375 Iterator<ReachTuple> rtItr = state.iterator();
3376 while( rtItr.hasNext() ) {
3377 ReachTuple rt = rtItr.next();
3378 assert rt.isOutOfContext();
3380 Set<HeapRegionNode> srcs = oocID2srcs.get(rt.getHrnID() );
3381 if( srcs == null ) {
3382 srcs = new HashSet<HeapRegionNode>();
3385 oocID2srcs.put(rt.getHrnID(), srcs);
3391 // calculate boldB for all hrnIDs identified by the above
3392 // node traversal, propagating from every source
3393 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3396 Set<HeapRegionNode> srcs;
3399 if( !icID2srcs.isEmpty() ) {
3400 Map.Entry me = (Map.Entry)icID2srcs.entrySet().iterator().next();
3401 hrnID = (Integer) me.getKey();
3402 srcs = (Set<HeapRegionNode>)me.getValue();
3404 icID2srcs.remove(hrnID);
3407 assert !oocID2srcs.isEmpty();
3409 Map.Entry me = (Map.Entry)oocID2srcs.entrySet().iterator().next();
3410 hrnID = (Integer) me.getKey();
3411 srcs = (Set<HeapRegionNode>)me.getValue();
3413 oocID2srcs.remove(hrnID);
3417 Hashtable<RefEdge, ReachSet> boldB_f =
3418 new Hashtable<RefEdge, ReachSet>();
3420 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3422 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3423 while( hrnItr.hasNext() ) {
3424 HeapRegionNode hrn = hrnItr.next();
3426 assert workSetEdges.isEmpty();
3428 // initial boldB_f constraints
3429 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3430 while( itrRees.hasNext() ) {
3431 RefEdge edge = itrRees.next();
3433 assert !boldB_f.containsKey(edge);
3434 boldB_f.put(edge, edge.getBeta() );
3436 assert !workSetEdges.contains(edge);
3437 workSetEdges.add(edge);
3440 // enforce the boldB_f constraint at edges until we reach a fixed point
3441 while( !workSetEdges.isEmpty() ) {
3442 RefEdge edge = workSetEdges.iterator().next();
3443 workSetEdges.remove(edge);
3445 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3446 while( itrPrime.hasNext() ) {
3447 RefEdge edgePrime = itrPrime.next();
3449 ReachSet prevResult = boldB_f.get(edgePrime);
3450 ReachSet intersection = Canonical.intersection(boldB_f.get(edge),
3454 if( prevResult == null ||
3455 Canonical.unionORpreds(prevResult,
3456 intersection).size()
3460 if( prevResult == null ) {
3461 boldB_f.put(edgePrime,
3462 Canonical.unionORpreds(edgePrime.getBeta(),
3467 boldB_f.put(edgePrime,
3468 Canonical.unionORpreds(prevResult,
3473 workSetEdges.add(edgePrime);
3480 boldBic.put(hrnID, boldB_f);
3482 boldBooc.put(hrnID, boldB_f);
3487 // use boldB to prune hrnIDs from alpha states that are impossible
3488 // and propagate the differences backwards across edges
3489 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3491 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3492 new Hashtable<RefEdge, ChangeSet>();
3495 itrHrns = id2hrn.entrySet().iterator();
3496 while( itrHrns.hasNext() ) {
3497 Map.Entry me = (Map.Entry)itrHrns.next();
3498 Integer hrnID = (Integer) me.getKey();
3499 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3501 // out-of-context nodes don't participate in the
3502 // global sweep, they serve as sources for the pass
3504 if( hrn.isOutOfContext() ) {
3508 // the inherent states of a region are the exception
3509 // to removal as the global sweep prunes
3510 ReachTuple rtException = ReachTuple.factory(hrnID,
3511 !hrn.isSingleObject(),
3512 ReachTuple.ARITY_ONE,
3513 false // out-of-context
3516 ChangeSet cts = ChangeSet.factory();
3518 // mark hrnIDs for removal
3519 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3520 while( stateItr.hasNext() ) {
3521 ReachState stateOld = stateItr.next();
3523 ReachState markedHrnIDs = ReachState.factory();
3525 Iterator<ReachTuple> rtItr = stateOld.iterator();
3526 while( rtItr.hasNext() ) {
3527 ReachTuple rtOld = rtItr.next();
3529 // never remove the inherent hrnID from a flagged region
3530 // because it is trivially satisfied
3531 if( hrn.isFlagged() ) {
3532 if( rtOld == rtException ) {
3537 // does boldB allow this hrnID?
3538 boolean foundState = false;
3539 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3540 while( incidentEdgeItr.hasNext() ) {
3541 RefEdge incidentEdge = incidentEdgeItr.next();
3543 Hashtable<RefEdge, ReachSet> B;
3544 if( rtOld.isOutOfContext() ) {
3545 B = boldBooc.get(rtOld.getHrnID() );
3548 if( !id2hrn.containsKey(rtOld.getHrnID() ) ) {
3549 // let symbols not in the graph get pruned
3553 B = boldBic.get(rtOld.getHrnID() );
3557 ReachSet boldB_rtOld_incident = B.get(incidentEdge);
3558 if( boldB_rtOld_incident != null &&
3559 boldB_rtOld_incident.containsIgnorePreds(stateOld) != null
3567 markedHrnIDs = Canonical.addUpArity(markedHrnIDs, rtOld);
3571 // if there is nothing marked, just move on
3572 if( markedHrnIDs.isEmpty() ) {
3573 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3580 // remove all marked hrnIDs and establish a change set that should
3581 // propagate backwards over edges from this node
3582 ReachState statePruned = ReachState.factory();
3583 rtItr = stateOld.iterator();
3584 while( rtItr.hasNext() ) {
3585 ReachTuple rtOld = rtItr.next();
3587 if( !markedHrnIDs.containsTuple(rtOld) ) {
3588 statePruned = Canonical.addUpArity(statePruned, rtOld);
3591 assert !stateOld.equals(statePruned);
3593 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3597 ChangeTuple ct = ChangeTuple.factory(stateOld,
3600 cts = Canonical.add(cts, ct);
3603 // throw change tuple set on all incident edges
3604 if( !cts.isEmpty() ) {
3605 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3606 while( incidentEdgeItr.hasNext() ) {
3607 RefEdge incidentEdge = incidentEdgeItr.next();
3609 edgesForPropagation.add(incidentEdge);
3611 if( edgePlannedChanges.get(incidentEdge) == null ) {
3612 edgePlannedChanges.put(incidentEdge, cts);
3614 edgePlannedChanges.put(
3616 Canonical.union(edgePlannedChanges.get(incidentEdge),
3625 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3627 propagateTokensOverEdges(edgesForPropagation,
3632 // at the end of the 1st phase reference edges have
3633 // beta, betaNew that correspond to beta and betaR
3635 // commit beta<-betaNew, so beta=betaR and betaNew
3636 // will represent the beta' calculation in 2nd phase
3638 // commit alpha<-alphaNew because it won't change
3639 HashSet<RefEdge> res = new HashSet<RefEdge>();
3641 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3642 while( nodeItr.hasNext() ) {
3643 HeapRegionNode hrn = nodeItr.next();
3645 // as mentioned above, out-of-context nodes only serve
3646 // as sources of reach states for the sweep, not part
3648 if( hrn.isOutOfContext() ) {
3649 assert hrn.getAlphaNew().equals(rsetEmpty);
3651 hrn.applyAlphaNew();
3654 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3655 while( itrRes.hasNext() ) {
3656 res.add(itrRes.next() );
3662 Iterator<RefEdge> edgeItr = res.iterator();
3663 while( edgeItr.hasNext() ) {
3664 RefEdge edge = edgeItr.next();
3665 HeapRegionNode hrn = edge.getDst();
3667 // commit results of last phase
3668 if( edgesUpdated.contains(edge) ) {
3669 edge.applyBetaNew();
3672 // compute intial condition of 2nd phase
3673 edge.setBetaNew(Canonical.intersection(edge.getBeta(),
3679 // every edge in the graph is the initial workset
3680 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3681 while( !edgeWorkSet.isEmpty() ) {
3682 RefEdge edgePrime = edgeWorkSet.iterator().next();
3683 edgeWorkSet.remove(edgePrime);
3685 RefSrcNode rsn = edgePrime.getSrc();
3686 if( !(rsn instanceof HeapRegionNode) ) {
3689 HeapRegionNode hrn = (HeapRegionNode) rsn;
3691 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3692 while( itrEdge.hasNext() ) {
3693 RefEdge edge = itrEdge.next();
3695 ReachSet prevResult = edge.getBetaNew();
3696 assert prevResult != null;
3698 ReachSet intersection =
3699 Canonical.intersection(edge.getBeta(),
3700 edgePrime.getBetaNew()
3703 if( Canonical.unionORpreds(prevResult,
3710 Canonical.unionORpreds(prevResult,
3714 edgeWorkSet.add(edge);
3719 // commit beta' (beta<-betaNew)
3720 edgeItr = res.iterator();
3721 while( edgeItr.hasNext() ) {
3722 edgeItr.next().applyBetaNew();
3727 // a useful assertion for debugging:
3728 // every in-context tuple on any edge or
3729 // any node should name a node that is
3730 // part of the graph
3731 public boolean inContextTuplesInGraph() {
3733 Iterator hrnItr = id2hrn.entrySet().iterator();
3734 while( hrnItr.hasNext() ) {
3735 Map.Entry me = (Map.Entry)hrnItr.next();
3736 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3739 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3740 while( stateItr.hasNext() ) {
3741 ReachState state = stateItr.next();
3743 Iterator<ReachTuple> rtItr = state.iterator();
3744 while( rtItr.hasNext() ) {
3745 ReachTuple rt = rtItr.next();
3747 if( !rt.isOutOfContext() ) {
3748 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3749 System.out.println(rt.getHrnID()+" is missing");
3757 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3758 while( edgeItr.hasNext() ) {
3759 RefEdge edge = edgeItr.next();
3761 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3762 while( stateItr.hasNext() ) {
3763 ReachState state = stateItr.next();
3765 Iterator<ReachTuple> rtItr = state.iterator();
3766 while( rtItr.hasNext() ) {
3767 ReachTuple rt = rtItr.next();
3769 if( !rt.isOutOfContext() ) {
3770 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3771 System.out.println(rt.getHrnID()+" is missing");
3784 // another useful assertion for debugging
3785 public boolean noEmptyReachSetsInGraph() {
3787 Iterator hrnItr = id2hrn.entrySet().iterator();
3788 while( hrnItr.hasNext() ) {
3789 Map.Entry me = (Map.Entry)hrnItr.next();
3790 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3792 if( !hrn.isOutOfContext() &&
3794 hrn.getAlpha().isEmpty()
3796 System.out.println("!!! "+hrn+" has an empty ReachSet !!!");
3800 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3801 while( edgeItr.hasNext() ) {
3802 RefEdge edge = edgeItr.next();
3804 if( edge.getBeta().isEmpty() ) {
3805 System.out.println("!!! "+edge+" has an empty ReachSet !!!");
3815 public boolean everyReachStateWTrue() {
3817 Iterator hrnItr = id2hrn.entrySet().iterator();
3818 while( hrnItr.hasNext() ) {
3819 Map.Entry me = (Map.Entry)hrnItr.next();
3820 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3823 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3824 while( stateItr.hasNext() ) {
3825 ReachState state = stateItr.next();
3827 if( !state.getPreds().equals(predsTrue) ) {
3833 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3834 while( edgeItr.hasNext() ) {
3835 RefEdge edge = edgeItr.next();
3837 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3838 while( stateItr.hasNext() ) {
3839 ReachState state = stateItr.next();
3841 if( !state.getPreds().equals(predsTrue) ) {
3854 ////////////////////////////////////////////////////
3855 // in merge() and equals() methods the suffix A
3856 // represents the passed in graph and the suffix
3857 // B refers to the graph in this object
3858 // Merging means to take the incoming graph A and
3859 // merge it into B, so after the operation graph B
3860 // is the final result.
3861 ////////////////////////////////////////////////////
3862 protected void merge(ReachGraph rg) {
3870 mergeAllocSites(rg);
3871 mergeInaccessibleVars(rg);
3874 protected void mergeNodes(ReachGraph rg) {
3876 // start with heap region nodes
3877 Set sA = rg.id2hrn.entrySet();
3878 Iterator iA = sA.iterator();
3879 while( iA.hasNext() ) {
3880 Map.Entry meA = (Map.Entry)iA.next();
3881 Integer idA = (Integer) meA.getKey();
3882 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3884 // if this graph doesn't have a node the
3885 // incoming graph has, allocate it
3886 if( !id2hrn.containsKey(idA) ) {
3887 HeapRegionNode hrnB = hrnA.copy();
3888 id2hrn.put(idA, hrnB);
3891 // otherwise this is a node present in both graphs
3892 // so make the new reachability set a union of the
3893 // nodes' reachability sets
3894 HeapRegionNode hrnB = id2hrn.get(idA);
3895 hrnB.setAlpha(Canonical.unionORpreds(hrnB.getAlpha(),
3900 hrnB.setPreds(Canonical.join(hrnB.getPreds(),
3907 if( !hrnA.equals(hrnB) ) {
3908 rg.writeGraph("graphA");
3909 this.writeGraph("graphB");
3910 throw new Error("flagged not matching");
3918 // now add any variable nodes that are in graph B but
3920 sA = rg.td2vn.entrySet();
3922 while( iA.hasNext() ) {
3923 Map.Entry meA = (Map.Entry)iA.next();
3924 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3925 VariableNode lnA = (VariableNode) meA.getValue();
3927 // if the variable doesn't exist in B, allocate and add it
3928 VariableNode lnB = getVariableNodeFromTemp(tdA);
3932 protected void mergeRefEdges(ReachGraph rg) {
3934 // between heap regions
3935 Set sA = rg.id2hrn.entrySet();
3936 Iterator iA = sA.iterator();
3937 while( iA.hasNext() ) {
3938 Map.Entry meA = (Map.Entry)iA.next();
3939 Integer idA = (Integer) meA.getKey();
3940 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3942 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3943 while( heapRegionsItrA.hasNext() ) {
3944 RefEdge edgeA = heapRegionsItrA.next();
3945 HeapRegionNode hrnChildA = edgeA.getDst();
3946 Integer idChildA = hrnChildA.getID();
3948 // at this point we know an edge in graph A exists
3949 // idA -> idChildA, does this exist in B?
3950 assert id2hrn.containsKey(idA);
3951 HeapRegionNode hrnB = id2hrn.get(idA);
3952 RefEdge edgeToMerge = null;
3954 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3955 while( heapRegionsItrB.hasNext() &&
3956 edgeToMerge == null ) {
3958 RefEdge edgeB = heapRegionsItrB.next();
3959 HeapRegionNode hrnChildB = edgeB.getDst();
3960 Integer idChildB = hrnChildB.getID();
3962 // don't use the RefEdge.equals() here because
3963 // we're talking about existence between graphs,
3964 // not intragraph equal
3965 if( idChildB.equals(idChildA) &&
3966 edgeB.typeAndFieldEquals(edgeA) ) {
3968 edgeToMerge = edgeB;
3972 // if the edge from A was not found in B,
3974 if( edgeToMerge == null ) {
3975 assert id2hrn.containsKey(idChildA);
3976 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3977 edgeToMerge = edgeA.copy();
3978 edgeToMerge.setSrc(hrnB);
3979 edgeToMerge.setDst(hrnChildB);
3980 addRefEdge(hrnB, hrnChildB, edgeToMerge);
3982 // otherwise, the edge already existed in both graphs
3983 // so merge their reachability sets
3985 // just replace this beta set with the union
3986 assert edgeToMerge != null;
3987 edgeToMerge.setBeta(
3988 Canonical.unionORpreds(edgeToMerge.getBeta(),
3992 edgeToMerge.setPreds(
3993 Canonical.join(edgeToMerge.getPreds(),
3997 edgeToMerge.setTaints(
3998 Canonical.union(edgeToMerge.getTaints(),
4006 // and then again from variable nodes
4007 sA = rg.td2vn.entrySet();
4009 while( iA.hasNext() ) {
4010 Map.Entry meA = (Map.Entry)iA.next();
4011 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4012 VariableNode vnA = (VariableNode) meA.getValue();
4014 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
4015 while( heapRegionsItrA.hasNext() ) {
4016 RefEdge edgeA = heapRegionsItrA.next();
4017 HeapRegionNode hrnChildA = edgeA.getDst();
4018 Integer idChildA = hrnChildA.getID();
4020 // at this point we know an edge in graph A exists
4021 // tdA -> idChildA, does this exist in B?
4022 assert td2vn.containsKey(tdA);
4023 VariableNode vnB = td2vn.get(tdA);
4024 RefEdge edgeToMerge = null;
4026 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
4027 while( heapRegionsItrB.hasNext() &&
4028 edgeToMerge == null ) {
4030 RefEdge edgeB = heapRegionsItrB.next();
4031 HeapRegionNode hrnChildB = edgeB.getDst();
4032 Integer idChildB = hrnChildB.getID();
4034 // don't use the RefEdge.equals() here because
4035 // we're talking about existence between graphs
4036 if( idChildB.equals(idChildA) &&
4037 edgeB.typeAndFieldEquals(edgeA) ) {
4039 edgeToMerge = edgeB;
4043 // if the edge from A was not found in B,
4045 if( edgeToMerge == null ) {
4046 assert id2hrn.containsKey(idChildA);
4047 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
4048 edgeToMerge = edgeA.copy();
4049 edgeToMerge.setSrc(vnB);
4050 edgeToMerge.setDst(hrnChildB);
4051 addRefEdge(vnB, hrnChildB, edgeToMerge);
4053 // otherwise, the edge already existed in both graphs
4054 // so merge their reachability sets
4056 // just replace this beta set with the union
4057 edgeToMerge.setBeta(Canonical.unionORpreds(edgeToMerge.getBeta(),
4061 edgeToMerge.setPreds(Canonical.join(edgeToMerge.getPreds(),
4065 edgeToMerge.setTaints(
4066 Canonical.union(edgeToMerge.getTaints(),
4075 protected void mergeAllocSites(ReachGraph rg) {
4076 allocSites.addAll(rg.allocSites);
4079 protected void mergeInaccessibleVars(ReachGraph rg) {
4080 inaccessibleVars.addAll(rg.inaccessibleVars);
4085 static public boolean dbgEquals = false;
4088 // it is necessary in the equals() member functions
4089 // to "check both ways" when comparing the data
4090 // structures of two graphs. For instance, if all
4091 // edges between heap region nodes in graph A are
4092 // present and equal in graph B it is not sufficient
4093 // to say the graphs are equal. Consider that there
4094 // may be edges in graph B that are not in graph A.
4095 // the only way to know that all edges in both graphs
4096 // are equally present is to iterate over both data
4097 // structures and compare against the other graph.
4098 public boolean equals(ReachGraph rg) {
4102 System.out.println("rg is null");
4107 if( !areHeapRegionNodesEqual(rg) ) {
4109 System.out.println("hrn not equal");
4114 if( !areVariableNodesEqual(rg) ) {
4116 System.out.println("vars not equal");
4121 if( !areRefEdgesEqual(rg) ) {
4123 System.out.println("edges not equal");
4128 if( !inaccessibleVars.equals(rg.inaccessibleVars) ) {
4132 // if everything is equal up to this point,
4133 // assert that allocSites is also equal--
4134 // this data is redundant but kept for efficiency
4135 assert allocSites.equals(rg.allocSites);
4141 protected boolean areHeapRegionNodesEqual(ReachGraph rg) {
4143 if( !areallHRNinAalsoinBandequal(this, rg) ) {
4147 if( !areallHRNinAalsoinBandequal(rg, this) ) {
4154 static protected boolean areallHRNinAalsoinBandequal(ReachGraph rgA,
4156 Set sA = rgA.id2hrn.entrySet();
4157 Iterator iA = sA.iterator();
4158 while( iA.hasNext() ) {
4159 Map.Entry meA = (Map.Entry)iA.next();
4160 Integer idA = (Integer) meA.getKey();
4161 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4163 if( !rgB.id2hrn.containsKey(idA) ) {
4167 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4168 if( !hrnA.equalsIncludingAlphaAndPreds(hrnB) ) {
4176 protected boolean areVariableNodesEqual(ReachGraph rg) {
4178 if( !areallVNinAalsoinBandequal(this, rg) ) {
4182 if( !areallVNinAalsoinBandequal(rg, this) ) {
4189 static protected boolean areallVNinAalsoinBandequal(ReachGraph rgA,
4191 Set sA = rgA.td2vn.entrySet();
4192 Iterator iA = sA.iterator();
4193 while( iA.hasNext() ) {
4194 Map.Entry meA = (Map.Entry)iA.next();
4195 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4197 if( !rgB.td2vn.containsKey(tdA) ) {
4206 protected boolean areRefEdgesEqual(ReachGraph rg) {
4207 if( !areallREinAandBequal(this, rg) ) {
4211 if( !areallREinAandBequal(rg, this) ) {
4218 static protected boolean areallREinAandBequal(ReachGraph rgA,
4221 // check all the heap region->heap region edges
4222 Set sA = rgA.id2hrn.entrySet();
4223 Iterator iA = sA.iterator();
4224 while( iA.hasNext() ) {
4225 Map.Entry meA = (Map.Entry)iA.next();
4226 Integer idA = (Integer) meA.getKey();
4227 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4229 // we should have already checked that the same
4230 // heap regions exist in both graphs
4231 assert rgB.id2hrn.containsKey(idA);
4233 if( !areallREfromAequaltoB(rgA, hrnA, rgB) ) {
4237 // then check every edge in B for presence in A, starting
4238 // from the same parent HeapRegionNode
4239 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4241 if( !areallREfromAequaltoB(rgB, hrnB, rgA) ) {
4246 // then check all the variable->heap region edges
4247 sA = rgA.td2vn.entrySet();
4249 while( iA.hasNext() ) {
4250 Map.Entry meA = (Map.Entry)iA.next();
4251 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4252 VariableNode vnA = (VariableNode) meA.getValue();
4254 // we should have already checked that the same
4255 // label nodes exist in both graphs
4256 assert rgB.td2vn.containsKey(tdA);
4258 if( !areallREfromAequaltoB(rgA, vnA, rgB) ) {
4262 // then check every edge in B for presence in A, starting
4263 // from the same parent VariableNode
4264 VariableNode vnB = rgB.td2vn.get(tdA);
4266 if( !areallREfromAequaltoB(rgB, vnB, rgA) ) {
4275 static protected boolean areallREfromAequaltoB(ReachGraph rgA,
4279 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4280 while( itrA.hasNext() ) {
4281 RefEdge edgeA = itrA.next();
4282 HeapRegionNode hrnChildA = edgeA.getDst();
4283 Integer idChildA = hrnChildA.getID();
4285 assert rgB.id2hrn.containsKey(idChildA);
4287 // at this point we know an edge in graph A exists
4288 // rnA -> idChildA, does this exact edge exist in B?
4289 boolean edgeFound = false;
4291 RefSrcNode rnB = null;
4292 if( rnA instanceof HeapRegionNode ) {
4293 HeapRegionNode hrnA = (HeapRegionNode) rnA;
4294 rnB = rgB.id2hrn.get(hrnA.getID() );
4296 VariableNode vnA = (VariableNode) rnA;
4297 rnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4300 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4301 while( itrB.hasNext() ) {
4302 RefEdge edgeB = itrB.next();
4303 HeapRegionNode hrnChildB = edgeB.getDst();
4304 Integer idChildB = hrnChildB.getID();
4306 if( idChildA.equals(idChildB) &&
4307 edgeA.typeAndFieldEquals(edgeB) ) {
4309 // there is an edge in the right place with the right field,
4310 // but do they have the same attributes?
4311 if( edgeA.equalsIncludingBetaPredsTaints( edgeB ) ) {
4326 // can be used to assert monotonicity
4327 static public boolean isNoSmallerThan(ReachGraph rgA,
4330 //System.out.println( "*** Asking if A is no smaller than B ***" );
4332 Iterator iA = rgA.id2hrn.entrySet().iterator();
4333 while( iA.hasNext() ) {
4334 Map.Entry meA = (Map.Entry)iA.next();
4335 Integer idA = (Integer) meA.getKey();
4336 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4338 if( !rgB.id2hrn.containsKey(idA) ) {
4339 System.out.println(" regions smaller");
4344 // this works just fine, no smaller than
4345 if( !areallVNinAalsoinBandequal(rgA, rgB) ) {
4346 System.out.println(" vars smaller:");
4347 System.out.println(" A:"+rgA.td2vn.keySet() );
4348 System.out.println(" B:"+rgB.td2vn.keySet() );
4353 iA = rgA.id2hrn.entrySet().iterator();
4354 while( iA.hasNext() ) {
4355 Map.Entry meA = (Map.Entry)iA.next();
4356 Integer idA = (Integer) meA.getKey();
4357 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4359 Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4360 while( reItr.hasNext() ) {
4361 RefEdge edgeA = reItr.next();
4362 RefSrcNode rsnA = edgeA.getSrc();
4364 // we already checked that nodes were present
4365 HeapRegionNode hrnB = rgB.id2hrn.get(hrnA.getID() );
4366 assert hrnB != null;
4369 if( rsnA instanceof VariableNode ) {
4370 VariableNode vnA = (VariableNode) rsnA;
4371 rsnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4374 HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4375 rsnB = rgB.id2hrn.get(hrnSrcA.getID() );
4377 assert rsnB != null;
4379 RefEdge edgeB = rsnB.getReferenceTo(hrnB,
4383 if( edgeB == null ) {
4384 System.out.println(" edges smaller:");
4398 // this analysis no longer has the "match anything"
4399 // type which was represented by null
4400 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4401 TypeDescriptor td2) {
4405 if( td1.isNull() ) {
4408 if( td2.isNull() ) {
4411 return typeUtil.mostSpecific(td1, td2);
4414 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4416 TypeDescriptor td3) {
4418 return mostSpecificType(td1,
4419 mostSpecificType(td2, td3)
4423 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4426 TypeDescriptor td4) {
4428 return mostSpecificType(mostSpecificType(td1, td2),
4429 mostSpecificType(td3, td4)
4433 protected boolean isSuperiorType(TypeDescriptor possibleSuper,
4434 TypeDescriptor possibleChild) {
4435 assert possibleSuper != null;
4436 assert possibleChild != null;
4438 if( possibleSuper.isNull() ||
4439 possibleChild.isNull() ) {
4443 return typeUtil.isSuperorType(possibleSuper, possibleChild);
4447 protected boolean hasMatchingField(HeapRegionNode src,
4450 TypeDescriptor tdSrc = src.getType();
4451 assert tdSrc != null;
4453 if( tdSrc.isArray() ) {
4454 TypeDescriptor td = edge.getType();
4457 TypeDescriptor tdSrcDeref = tdSrc.dereference();
4458 assert tdSrcDeref != null;
4460 if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
4464 return edge.getField().equals(DisjointAnalysis.arrayElementFieldName);
4467 // if it's not a class, it doesn't have any fields to match
4468 if( !tdSrc.isClass() ) {
4472 ClassDescriptor cd = tdSrc.getClassDesc();
4473 while( cd != null ) {
4474 Iterator fieldItr = cd.getFields();
4476 while( fieldItr.hasNext() ) {
4477 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4479 if( fd.getType().equals(edge.getType() ) &&
4480 fd.getSymbol().equals(edge.getField() ) ) {
4485 cd = cd.getSuperDesc();
4488 // otherwise it is a class with fields
4489 // but we didn't find a match
4493 protected boolean hasMatchingType(RefEdge edge,
4494 HeapRegionNode dst) {
4496 // if the region has no type, matches everything
4497 TypeDescriptor tdDst = dst.getType();
4498 assert tdDst != null;
4500 // if the type is not a class or an array, don't
4501 // match because primitives are copied, no aliases
4502 ClassDescriptor cdDst = tdDst.getClassDesc();
4503 if( cdDst == null && !tdDst.isArray() ) {
4507 // if the edge type is null, it matches everything
4508 TypeDescriptor tdEdge = edge.getType();
4509 assert tdEdge != null;
4511 return typeUtil.isSuperorType(tdEdge, tdDst);
4516 // the default signature for quick-and-dirty debugging
4517 public void writeGraph(String graphName) {
4518 writeGraph(graphName,
4519 true, // write labels
4520 true, // label select
4521 true, // prune garbage
4522 false, // hide reachability
4523 true, // hide subset reachability
4524 true, // hide predicates
4525 false, // hide edge taints
4526 null // in-context boundary
4530 public void writeGraph(String graphName,
4531 boolean writeLabels,
4532 boolean labelSelect,
4533 boolean pruneGarbage,
4534 boolean hideReachability,
4535 boolean hideSubsetReachability,
4536 boolean hidePredicates,
4537 boolean hideEdgeTaints
4539 writeGraph(graphName,
4544 hideSubsetReachability,
4550 public void writeGraph(String graphName,
4551 boolean writeLabels,
4552 boolean labelSelect,
4553 boolean pruneGarbage,
4554 boolean hideReachability,
4555 boolean hideSubsetReachability,
4556 boolean hidePredicates,
4557 boolean hideEdgeTaints,
4558 Set<Integer> callerNodeIDsCopiedToCallee
4561 // remove all non-word characters from the graph name so
4562 // the filename and identifier in dot don't cause errors
4563 // jjenista - also replace underscore '_' to prevent some
4564 // really, really long names from IHMS debugging
4565 graphName = graphName.replaceAll("[\\W_]", "");
4568 new BufferedWriter(new FileWriter(graphName+".dot") );
4570 bw.write("digraph "+graphName+" {\n");
4573 // this is an optional step to form the callee-reachable
4574 // "cut-out" into a DOT cluster for visualization
4575 if( callerNodeIDsCopiedToCallee != null ) {
4577 bw.write(" subgraph cluster0 {\n");
4578 bw.write(" color=blue;\n");
4580 Iterator i = id2hrn.entrySet().iterator();
4581 while( i.hasNext() ) {
4582 Map.Entry me = (Map.Entry)i.next();
4583 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4585 if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4588 hrn.toStringDOT(hideReachability,
4589 hideSubsetReachability,
4599 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4601 // then visit every heap region node
4602 Iterator i = id2hrn.entrySet().iterator();
4603 while( i.hasNext() ) {
4604 Map.Entry me = (Map.Entry)i.next();
4605 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4607 // only visit nodes worth writing out--for instance
4608 // not every node at an allocation is referenced
4609 // (think of it as garbage-collected), etc.
4610 if( !pruneGarbage ||
4611 hrn.isOutOfContext() ||
4612 (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4615 if( !visited.contains(hrn) ) {
4616 traverseHeapRegionNodes(hrn,
4621 hideSubsetReachability,
4624 callerNodeIDsCopiedToCallee);
4629 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4632 // then visit every label node, useful for debugging
4634 i = td2vn.entrySet().iterator();
4635 while( i.hasNext() ) {
4636 Map.Entry me = (Map.Entry)i.next();
4637 VariableNode vn = (VariableNode) me.getValue();
4640 String labelStr = vn.getTempDescriptorString();
4641 if( labelStr.startsWith("___temp") ||
4642 labelStr.startsWith("___dst") ||
4643 labelStr.startsWith("___srctmp") ||
4644 labelStr.startsWith("___neverused")
4650 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4651 while( heapRegionsItr.hasNext() ) {
4652 RefEdge edge = heapRegionsItr.next();
4653 HeapRegionNode hrn = edge.getDst();
4655 if( !visited.contains(hrn) ) {
4656 traverseHeapRegionNodes(hrn,
4661 hideSubsetReachability,
4664 callerNodeIDsCopiedToCallee);
4667 bw.write(" "+vn.toString()+
4668 " -> "+hrn.toString()+
4669 edge.toStringDOT(hideReachability,
4670 hideSubsetReachability,
4682 } catch( IOException e ) {
4683 throw new Error("Error writing out DOT graph "+graphName);
4688 traverseHeapRegionNodes(HeapRegionNode hrn,
4691 Set<HeapRegionNode> visited,
4692 boolean hideReachability,
4693 boolean hideSubsetReachability,
4694 boolean hidePredicates,
4695 boolean hideEdgeTaints,
4696 Set<Integer> callerNodeIDsCopiedToCallee
4697 ) throws java.io.IOException {
4699 if( visited.contains(hrn) ) {
4704 // if we're drawing the callee-view subgraph, only
4705 // write out the node info if it hasn't already been
4707 if( callerNodeIDsCopiedToCallee == null ||
4708 !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4712 hrn.toStringDOT(hideReachability,
4713 hideSubsetReachability,
4718 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4719 while( childRegionsItr.hasNext() ) {
4720 RefEdge edge = childRegionsItr.next();
4721 HeapRegionNode hrnChild = edge.getDst();
4723 if( callerNodeIDsCopiedToCallee != null &&
4724 (edge.getSrc() instanceof HeapRegionNode) ) {
4725 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4726 if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4727 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4729 bw.write(" "+hrn.toString()+
4730 " -> "+hrnChild.toString()+
4731 edge.toStringDOT(hideReachability,
4732 hideSubsetReachability,
4737 } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4738 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4740 bw.write(" "+hrn.toString()+
4741 " -> "+hrnChild.toString()+
4742 edge.toStringDOT(hideReachability,
4743 hideSubsetReachability,
4746 ",color=blue,style=dashed")+
4749 bw.write(" "+hrn.toString()+
4750 " -> "+hrnChild.toString()+
4751 edge.toStringDOT(hideReachability,
4752 hideSubsetReachability,
4759 bw.write(" "+hrn.toString()+
4760 " -> "+hrnChild.toString()+
4761 edge.toStringDOT(hideReachability,
4762 hideSubsetReachability,
4769 traverseHeapRegionNodes(hrnChild,
4774 hideSubsetReachability,
4777 callerNodeIDsCopiedToCallee);
4786 // return the set of heap regions from the given allocation
4787 // site, if any, that exist in this graph
4788 protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4790 Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4792 Integer idSum = as.getSummary();
4793 if( id2hrn.containsKey(idSum) ) {
4794 out.add(id2hrn.get(idSum) );
4797 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4798 Integer idI = as.getIthOldest(i);
4799 if( id2hrn.containsKey(idI) ) {
4800 out.add(id2hrn.get(idI) );
4807 // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4808 // from the given allocation site, if any, from regions for that
4809 // site that exist in this graph
4810 protected Set<ReachTuple> getAnyExisting(AllocSite as,
4811 boolean includeARITY_ZEROORMORE,
4812 boolean includeARITY_ONE) {
4814 Set<ReachTuple> out = new HashSet<ReachTuple>();
4816 Integer idSum = as.getSummary();
4817 if( id2hrn.containsKey(idSum) ) {
4819 HeapRegionNode hrn = id2hrn.get(idSum);
4820 assert !hrn.isOutOfContext();
4822 if( !includeARITY_ZEROORMORE ) {
4823 out.add(ReachTuple.factory(hrn.getID(),
4824 true, // multi-obj region
4825 ReachTuple.ARITY_ZEROORMORE,
4830 if( includeARITY_ONE ) {
4831 out.add(ReachTuple.factory(hrn.getID(),
4832 true, // multi-object region
4833 ReachTuple.ARITY_ONE,
4839 if( !includeARITY_ONE ) {
4840 // no need to do the single-object regions that
4841 // only have an ARITY ONE possible
4845 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4847 Integer idI = as.getIthOldest(i);
4848 if( id2hrn.containsKey(idI) ) {
4850 HeapRegionNode hrn = id2hrn.get(idI);
4851 assert !hrn.isOutOfContext();
4853 out.add(ReachTuple.factory(hrn.getID(),
4854 false, // multi-object region
4855 ReachTuple.ARITY_ONE,
4865 // if an object allocated at the target site may be
4866 // reachable from both an object from root1 and an
4867 // object allocated at root2, return TRUE
4868 public boolean mayBothReachTarget(AllocSite asRoot1,
4870 AllocSite asTarget) {
4872 // consider all heap regions of the target and look
4873 // for a reach state that indicates regions of root1
4874 // and root2 might be able to reach same object
4875 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4877 // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4878 Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4879 Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4881 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4882 while( hrnItr.hasNext() ) {
4883 HeapRegionNode hrn = hrnItr.next();
4885 Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4886 while( rtItr1.hasNext() ) {
4887 ReachTuple rt1 = rtItr1.next();
4889 Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4890 while( rtItr2.hasNext() ) {
4891 ReachTuple rt2 = rtItr2.next();
4893 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4903 // similar to the method above, return TRUE if ever
4904 // more than one object from the root allocation site
4905 // may reach an object from the target site
4906 public boolean mayManyReachTarget(AllocSite asRoot,
4907 AllocSite asTarget) {
4909 // consider all heap regions of the target and look
4910 // for a reach state that multiple objects of root
4911 // might be able to reach the same object
4912 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4914 // get relevant reach tuples
4915 Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true, false);
4916 Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4918 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4919 while( hrnItr.hasNext() ) {
4920 HeapRegionNode hrn = hrnItr.next();
4922 // if any ZERORMORE tuples are here, TRUE
4923 Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4924 while( rtItr.hasNext() ) {
4925 ReachTuple rtZOM = rtItr.next();
4927 if( hrn.getAlpha().containsTuple(rtZOM) ) {
4932 // otherwise, look for any pair of ONE tuples
4933 Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4934 while( rtItr1.hasNext() ) {
4935 ReachTuple rt1 = rtItr1.next();
4937 Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4938 while( rtItr2.hasNext() ) {
4939 ReachTuple rt2 = rtItr2.next();
4945 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4959 public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4961 Set<HeapRegionNode> exhibitProofState =
4962 new HashSet<HeapRegionNode>();
4964 Iterator hrnItr = id2hrn.entrySet().iterator();
4965 while( hrnItr.hasNext() ) {
4966 Map.Entry me = (Map.Entry)hrnItr.next();
4967 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4969 ReachSet intersection =
4970 Canonical.intersection(proofOfSharing,
4973 if( !intersection.isEmpty() ) {
4974 assert !hrn.isOutOfContext();
4975 exhibitProofState.add(hrn);
4979 return exhibitProofState;
4983 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4984 HeapRegionNode hrn2) {
4985 assert hrn1 != null;
4986 assert hrn2 != null;
4988 assert !hrn1.isOutOfContext();
4989 assert !hrn2.isOutOfContext();
4991 assert belongsToThis(hrn1);
4992 assert belongsToThis(hrn2);
4994 assert !hrn1.getID().equals(hrn2.getID() );
4997 // then get the various tokens for these heap regions
4999 ReachTuple.factory(hrn1.getID(),
5000 !hrn1.isSingleObject(), // multi?
5001 ReachTuple.ARITY_ONE,
5004 ReachTuple h1star = null;
5005 if( !hrn1.isSingleObject() ) {
5007 ReachTuple.factory(hrn1.getID(),
5008 !hrn1.isSingleObject(),
5009 ReachTuple.ARITY_ZEROORMORE,
5014 ReachTuple.factory(hrn2.getID(),
5015 !hrn2.isSingleObject(),
5016 ReachTuple.ARITY_ONE,
5019 ReachTuple h2star = null;
5020 if( !hrn2.isSingleObject() ) {
5022 ReachTuple.factory(hrn2.getID(),
5023 !hrn2.isSingleObject(),
5024 ReachTuple.ARITY_ZEROORMORE,
5028 // then get the merged beta of all out-going edges from these heap
5031 ReachSet beta1 = ReachSet.factory();
5032 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
5033 while (itrEdge.hasNext()) {
5034 RefEdge edge = itrEdge.next();
5035 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
5038 ReachSet beta2 = ReachSet.factory();
5039 itrEdge = hrn2.iteratorToReferencees();
5040 while (itrEdge.hasNext()) {
5041 RefEdge edge = itrEdge.next();
5042 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
5045 ReachSet proofOfSharing = ReachSet.factory();
5048 Canonical.unionORpreds(proofOfSharing,
5049 beta1.getStatesWithBoth(h1, h2)
5052 Canonical.unionORpreds(proofOfSharing,
5053 beta2.getStatesWithBoth(h1, h2)
5056 if( !hrn1.isSingleObject() ) {
5058 Canonical.unionORpreds(proofOfSharing,
5059 beta1.getStatesWithBoth(h1star, h2)
5062 Canonical.unionORpreds(proofOfSharing,
5063 beta2.getStatesWithBoth(h1star, h2)
5067 if( !hrn2.isSingleObject() ) {
5069 Canonical.unionORpreds(proofOfSharing,
5070 beta1.getStatesWithBoth(h1, h2star)
5073 Canonical.unionORpreds(proofOfSharing,
5074 beta2.getStatesWithBoth(h1, h2star)
5078 if( !hrn1.isSingleObject() &&
5079 !hrn2.isSingleObject()
5082 Canonical.unionORpreds(proofOfSharing,
5083 beta1.getStatesWithBoth(h1star, h2star)
5086 Canonical.unionORpreds(proofOfSharing,
5087 beta2.getStatesWithBoth(h1star, h2star)
5091 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5092 if( !proofOfSharing.isEmpty() ) {
5093 common = findCommonReachableNodes(proofOfSharing);
5094 if( !DISABLE_STRONG_UPDATES &&
5095 !DISABLE_GLOBAL_SWEEP
5097 assert !common.isEmpty();
5104 // this version of the above method checks whether there is sharing
5105 // among the objects in a summary node
5106 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
5108 assert hrn.isNewSummary();
5109 assert !hrn.isOutOfContext();
5110 assert belongsToThis(hrn);
5113 ReachTuple.factory(hrn.getID(),
5115 ReachTuple.ARITY_ZEROORMORE,
5118 // then get the merged beta of all out-going edges from
5121 ReachSet beta = ReachSet.factory();
5122 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
5123 while (itrEdge.hasNext()) {
5124 RefEdge edge = itrEdge.next();
5125 beta = Canonical.unionORpreds(beta, edge.getBeta());
5128 ReachSet proofOfSharing = ReachSet.factory();
5131 Canonical.unionORpreds(proofOfSharing,
5132 beta.getStatesWithBoth(hstar, hstar)
5135 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5136 if( !proofOfSharing.isEmpty() ) {
5137 common = findCommonReachableNodes(proofOfSharing);
5138 if( !DISABLE_STRONG_UPDATES &&
5139 !DISABLE_GLOBAL_SWEEP
5141 assert !common.isEmpty();
5149 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5150 Integer paramIndex1,
5151 Integer paramIndex2) {
5153 // get parameter's heap regions
5154 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5155 assert this.hasVariable(paramTemp1);
5156 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5159 if( !(paramVar1.getNumReferencees() == 1) ) {
5160 System.out.println("\n fm="+fm+"\n param="+paramTemp1);
5161 writeGraph("whatup");
5165 assert paramVar1.getNumReferencees() == 1;
5166 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5167 HeapRegionNode hrnParam1 = paramEdge1.getDst();
5169 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5170 assert this.hasVariable(paramTemp2);
5171 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5173 if( !(paramVar2.getNumReferencees() == 1) ) {
5174 System.out.println("\n fm="+fm+"\n param="+paramTemp2);
5175 writeGraph("whatup");
5178 assert paramVar2.getNumReferencees() == 1;
5179 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5180 HeapRegionNode hrnParam2 = paramEdge2.getDst();
5182 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5183 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5188 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5192 // get parameter's heap regions
5193 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5194 assert this.hasVariable(paramTemp);
5195 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5196 assert paramVar.getNumReferencees() == 1;
5197 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5198 HeapRegionNode hrnParam = paramEdge.getDst();
5201 HeapRegionNode hrnSummary=null;
5202 if(id2hrn.containsKey(as.getSummary())) {
5203 // if summary node doesn't exist, ignore this case
5204 hrnSummary = id2hrn.get(as.getSummary());
5205 assert hrnSummary != null;
5208 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5209 if(hrnSummary!=null) {
5210 common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5213 // check for other nodes
5214 for (int i = 0; i < as.getAllocationDepth(); ++i) {
5216 assert id2hrn.containsKey(as.getIthOldest(i));
5217 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5218 assert hrnIthOldest != null;
5220 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5227 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5230 // get summary node 1's alpha
5231 Integer idSum1 = as1.getSummary();
5232 HeapRegionNode hrnSum1=null;
5233 if(id2hrn.containsKey(idSum1)) {
5234 hrnSum1 = id2hrn.get(idSum1);
5237 // get summary node 2's alpha
5238 Integer idSum2 = as2.getSummary();
5239 HeapRegionNode hrnSum2=null;
5240 if(id2hrn.containsKey(idSum2)) {
5241 hrnSum2 = id2hrn.get(idSum2);
5244 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5245 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5246 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5250 // ask if objects from this summary share among each other
5251 common.addAll(mayReachSharedObjects(hrnSum1));
5254 // check sum2 against alloc1 nodes
5256 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5257 Integer idI1 = as1.getIthOldest(i);
5258 assert id2hrn.containsKey(idI1);
5259 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5260 assert hrnI1 != null;
5261 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5264 // also ask if objects from this summary share among each other
5265 common.addAll(mayReachSharedObjects(hrnSum2));
5268 // check sum1 against alloc2 nodes
5269 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5270 Integer idI2 = as2.getIthOldest(i);
5271 assert id2hrn.containsKey(idI2);
5272 HeapRegionNode hrnI2 = id2hrn.get(idI2);
5273 assert hrnI2 != null;
5276 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5279 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5280 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5281 Integer idI1 = as1.getIthOldest(j);
5283 // if these are the same site, don't look for the same token, no
5285 // different tokens of the same site could alias together though
5286 if (idI1.equals(idI2)) {
5290 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5292 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5299 public void makeInaccessible(Set<TempDescriptor> vars) {
5300 inaccessibleVars.addAll(vars);
5303 public void makeInaccessible(TempDescriptor td) {
5304 inaccessibleVars.add(td);
5307 public void makeAccessible(TempDescriptor td) {
5308 inaccessibleVars.remove(td);
5311 public boolean isAccessible(TempDescriptor td) {
5312 return !inaccessibleVars.contains(td);
5315 public Set<TempDescriptor> getInaccessibleVars() {
5316 return inaccessibleVars;
5322 public Set<Alloc> canPointTo( TempDescriptor x ) {
5324 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5325 // if we don't care to track it, return null which means
5326 // "a client of this result shouldn't care either"
5327 return HeapAnalysis.DONTCARE_PTR;
5330 Set<Alloc> out = new HashSet<Alloc>();
5332 VariableNode vn = getVariableNodeNoMutation( x );
5334 // the empty set means "can't point to anything"
5338 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5339 while( edgeItr.hasNext() ) {
5340 HeapRegionNode hrn = edgeItr.next().getDst();
5341 out.add( hrn.getAllocSite() );
5349 public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5351 TypeDescriptor fieldType ) {
5353 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5354 // if we don't care to track it, return null which means
5355 // "a client of this result shouldn't care either"
5356 return HeapAnalysis.DONTCARE_DREF;
5359 Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5361 VariableNode vn = getVariableNodeNoMutation( x );
5363 // the empty table means "x can't point to anything"
5367 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5368 while( edgeItr.hasNext() ) {
5369 HeapRegionNode hrn = edgeItr.next().getDst();
5370 Alloc key = hrn.getAllocSite();
5372 if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5373 // if we don't care to track it, put no entry which means
5374 // "a client of this result shouldn't care either"
5375 out.put( key, HeapAnalysis.DONTCARE_PTR );
5379 Set<Alloc> moreValues = new HashSet<Alloc>();
5380 Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5381 while( edgeItr2.hasNext() ) {
5382 RefEdge edge = edgeItr2.next();
5384 if( field.equals( edge.getField() ) ) {
5385 moreValues.add( edge.getDst().getAllocSite() );
5389 if( out.containsKey( key ) ) {
5390 out.get( key ).addAll( moreValues );
5392 out.put( key, moreValues );
5402 public TempDescriptor findVariableByName( String name ) {
5404 for( TempDescriptor td: td2vn.keySet() ) {
5405 if( td.getSymbol().contains( name ) ) {
5414 public void countGraphElements( GraphElementCount c ) {
5416 for( HeapRegionNode node : id2hrn.values() ) {
5418 if( node.isShadow() || node.isWiped() ) {
5419 // do not count nodes that are not functionally part of the
5420 // abstraction (they are in the graph for implementation
5421 // convenience when needed next)
5426 c.nodeStateInc( node.getAlpha().numStates() );
5427 c.nodeStateNonzeroInc( node.getAlpha().numNonzeroTuples() );
5429 // all edges in the graph point TO a heap node, so scanning
5430 // all referencers of all nodes gets every edge
5431 Iterator<RefEdge> refItr = node.iteratorToReferencers();
5432 while( refItr.hasNext() ) {
5433 RefEdge edge = refItr.next();
5436 c.edgeStateInc( edge.getBeta().numStates() );
5437 c.edgeStateNonzeroInc( edge.getBeta().numNonzeroTuples() );
5443 public void writeNodes( String filename ) {
5447 BufferedWriter bw = new BufferedWriter( new FileWriter( filename ) );
5449 for( AllocSite as : allocSites ) {
5450 bw.write( "--------------------------\n" );
5452 // allocation site ID, full type, assigned heap node IDs
5453 bw.write( as.toStringVerbose()+"\n"+
5454 " "+as.toStringJustIDs()+"\n" );
5456 DisjointAnalysis.fn2filename.get( as.getFlatNew() )+":"+
5457 as.getFlatNew().getNumLine()+"\n" );
5459 // which of the nodes are actually in this graph?
5460 for( int i = 0; i < allocationDepth; ++i ) {
5461 Integer id = as.getIthOldest( i );
5462 String s = writeNodeFormat( id );
5467 Integer id = as.getSummary();
5468 String s = writeNodeFormat( id );
5476 } catch( IOException e ) {
5477 System.out.println( "Error writing nodes to file: "+filename );
5481 private String writeNodeFormat( Integer id ) {
5484 if( !id2hrn.containsKey( id ) ) {
5488 s = " "+id+" is present and refrenced by variables:\n";
5490 HeapRegionNode hrn = id2hrn.get( id );
5491 Iterator<RefEdge> refItr = hrn.iteratorToReferencers();
5492 while( refItr.hasNext() ) {
5493 RefEdge edge = refItr.next();
5494 RefSrcNode rsn = edge.getSrc();
5495 if( rsn instanceof VariableNode ) {
5496 VariableNode vn = (VariableNode)rsn;
5499 HeapRegionNode hrnSrc = (HeapRegionNode)rsn;
5501 if( hrnSrc.isOutOfContext() ) {
5504 s += hrnSrc.getID()+"."+edge.getField()+"\n";