1 package Analysis.Disjoint;
5 import Util.UtilAlgorithms;
9 public class ReachGraph {
11 // use to disable improvements for comparison
12 protected static final boolean DISABLE_STRONG_UPDATES = false;
13 protected static final boolean DISABLE_GLOBAL_SWEEP = false;
15 // a special out-of-scope temps
16 protected static TempDescriptor tdReturn;
17 protected static TempDescriptor tdStrLiteralBytes;
19 public static void initOutOfScopeTemps() {
20 tdReturn = new TempDescriptor("_Return___");
23 new TempDescriptor("_strLiteralBytes___",
24 new TypeDescriptor(TypeDescriptor.CHAR).makeArray( state )
28 // predicate constants
29 public static final ExistPred predTrue = ExistPred.factory(); // if no args, true
30 public static final ExistPredSet predsEmpty = ExistPredSet.factory();
31 public static final ExistPredSet predsTrue = ExistPredSet.factory(predTrue);
33 // some frequently used reachability constants
34 protected static final ReachState rstateEmpty = ReachState.factory();
35 protected static final ReachSet rsetEmpty = ReachSet.factory();
36 protected static final ReachSet rsetWithEmptyState = Canonical.changePredsTo(ReachSet.factory(rstateEmpty),
39 // from DisjointAnalysis for convenience
40 protected static int allocationDepth = -1;
41 protected static TypeUtil typeUtil = null;
42 protected static State state = null;
45 // variable and heap region nodes indexed by unique ID
46 public Hashtable<Integer, HeapRegionNode> id2hrn;
47 public Hashtable<TempDescriptor, VariableNode > td2vn;
49 // convenient set of alloc sites for all heap regions
50 // present in the graph without having to search
51 public Set<AllocSite> allocSites;
53 // set of inaccessible variables for current program statement
54 // with respect to stall-site analysis
55 public Set<TempDescriptor> inaccessibleVars;
59 id2hrn = new Hashtable<Integer, HeapRegionNode>();
60 td2vn = new Hashtable<TempDescriptor, VariableNode >();
61 allocSites = new HashSet<AllocSite>();
62 inaccessibleVars = new HashSet<TempDescriptor>();
66 // temp descriptors are globally unique and map to
67 // exactly one variable node, easy
68 protected VariableNode getVariableNodeFromTemp(TempDescriptor td) {
71 if( !td2vn.containsKey(td) ) {
72 td2vn.put(td, new VariableNode(td) );
78 //This method is created for client modules to access the Reachgraph
79 //after the analysis is done and no modifications are to be made.
80 public VariableNode getVariableNodeNoMutation(TempDescriptor td) {
83 if( !td2vn.containsKey(td) ) {
90 public boolean hasVariable(TempDescriptor td) {
91 return td2vn.containsKey(td);
95 // this suite of methods can be used to assert a
96 // very important property of ReachGraph objects:
97 // some element, HeapRegionNode, RefEdge etc.
98 // should be referenced by at most ONE ReachGraph!!
99 // If a heap region or edge or variable should be
100 // in another graph, make a new object with
101 // equivalent properties for a new graph
102 public boolean belongsToThis(RefSrcNode rsn) {
103 if( rsn instanceof VariableNode ) {
104 VariableNode vn = (VariableNode) rsn;
105 return this.td2vn.get(vn.getTempDescriptor() ) == vn;
107 HeapRegionNode hrn = (HeapRegionNode) rsn;
108 return this.id2hrn.get(hrn.getID() ) == hrn;
115 // the reason for this method is to have the option
116 // of creating new heap regions with specific IDs, or
117 // duplicating heap regions with specific IDs (especially
118 // in the merge() operation) or to create new heap
119 // regions with a new unique ID
120 protected HeapRegionNode
121 createNewHeapRegionNode(Integer id,
122 boolean isSingleObject,
123 boolean isNewSummary,
124 boolean isOutOfContext,
133 TypeDescriptor typeToUse = null;
134 if( allocSite != null ) {
135 typeToUse = allocSite.getType();
136 allocSites.add(allocSite);
141 boolean markForAnalysis = false;
142 if( allocSite != null && allocSite.isFlagged() ) {
143 markForAnalysis = true;
146 if( allocSite == null ) {
147 assert !markForAnalysis;
149 } else if( markForAnalysis != allocSite.isFlagged() ) {
155 id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
158 if( inherent == null ) {
159 if( markForAnalysis ) {
161 Canonical.changePredsTo(
164 ReachTuple.factory(id,
166 ReachTuple.ARITY_ONE,
167 false // out-of-context
174 inherent = rsetWithEmptyState;
178 if( alpha == null ) {
182 assert preds != null;
184 HeapRegionNode hrn = new HeapRegionNode(id,
201 ////////////////////////////////////////////////
203 // Low-level referencee and referencer methods
205 // These methods provide the lowest level for
206 // creating references between reachability nodes
207 // and handling the details of maintaining both
208 // list of referencers and referencees.
210 ////////////////////////////////////////////////
211 protected void addRefEdge(RefSrcNode referencer,
212 HeapRegionNode referencee,
214 assert referencer != null;
215 assert referencee != null;
217 assert edge.getSrc() == referencer;
218 assert edge.getDst() == referencee;
219 assert belongsToThis(referencer);
220 assert belongsToThis(referencee);
222 // edges are getting added twice to graphs now, the
223 // kind that should have abstract facts merged--use
224 // this check to prevent that
225 assert referencer.getReferenceTo(referencee,
230 referencer.addReferencee(edge);
231 referencee.addReferencer(edge);
234 protected void removeRefEdge(RefEdge e) {
235 removeRefEdge(e.getSrc(),
241 protected void removeRefEdge(RefSrcNode referencer,
242 HeapRegionNode referencee,
245 assert referencer != null;
246 assert referencee != null;
248 RefEdge edge = referencer.getReferenceTo(referencee,
252 assert edge == referencee.getReferenceFrom(referencer,
256 referencer.removeReferencee(edge);
257 referencee.removeReferencer(edge);
261 protected boolean clearRefEdgesFrom(RefSrcNode referencer,
265 return clearRefEdgesFrom( referencer, type, field, removeAll, null, null );
268 // return whether at least one edge was removed
269 protected boolean clearRefEdgesFrom(RefSrcNode referencer,
273 Set<EdgeKey> edgeKeysRemoved,
274 FieldDescriptor fd) {
275 assert referencer != null;
277 boolean atLeastOneEdgeRemoved = false;
279 // get a copy of the set to iterate over, otherwise
280 // we will be trying to take apart the set as we
281 // are iterating over it, which won't work
282 Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
283 while( i.hasNext() ) {
284 RefEdge edge = i.next();
287 (edge.typeEquals(type) && edge.fieldEquals(field))
290 HeapRegionNode referencee = edge.getDst();
292 if( edgeKeysRemoved != null ) {
294 assert referencer instanceof HeapRegionNode;
295 edgeKeysRemoved.add( new EdgeKey( ((HeapRegionNode)referencer).getID(),
301 removeRefEdge(referencer,
306 atLeastOneEdgeRemoved = true;
310 return atLeastOneEdgeRemoved;
313 protected void clearRefEdgesTo(HeapRegionNode referencee,
317 assert referencee != null;
319 // get a copy of the set to iterate over, otherwise
320 // we will be trying to take apart the set as we
321 // are iterating over it, which won't work
322 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
323 while( i.hasNext() ) {
324 RefEdge edge = i.next();
327 (edge.typeEquals(type) && edge.fieldEquals(field))
330 RefSrcNode referencer = edge.getSrc();
332 removeRefEdge(referencer,
340 protected void clearNonVarRefEdgesTo(HeapRegionNode referencee) {
341 assert referencee != null;
343 // get a copy of the set to iterate over, otherwise
344 // we will be trying to take apart the set as we
345 // are iterating over it, which won't work
346 Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
347 while( i.hasNext() ) {
348 RefEdge edge = i.next();
349 RefSrcNode referencer = edge.getSrc();
350 if( !(referencer instanceof VariableNode) ) {
351 removeRefEdge(referencer,
359 // this is a common operation in many transfer functions: we want
360 // to add an edge, but if there is already such an edge we should
361 // merge the properties of the existing and the new edges
362 protected void addEdgeOrMergeWithExisting(RefEdge edgeNew) {
364 RefSrcNode src = edgeNew.getSrc();
365 assert belongsToThis(src);
367 HeapRegionNode dst = edgeNew.getDst();
368 assert belongsToThis(dst);
370 // look to see if an edge with same field exists
371 // and merge with it, otherwise just add the edge
372 RefEdge edgeExisting = src.getReferenceTo(dst,
377 if( edgeExisting != null ) {
378 edgeExisting.setBeta(
379 Canonical.unionORpreds(edgeExisting.getBeta(),
383 edgeExisting.setPreds(
384 Canonical.join(edgeExisting.getPreds(),
388 edgeExisting.setTaints(
389 Canonical.unionORpreds(edgeExisting.getTaints(),
395 addRefEdge(src, dst, edgeNew);
401 ////////////////////////////////////////////////////
403 // Assignment Operation Methods
405 // These methods are high-level operations for
406 // modeling program assignment statements using
407 // the low-level reference create/remove methods
410 ////////////////////////////////////////////////////
412 public void assignTempEqualToStringLiteral(TempDescriptor x,
413 AllocSite asStringLiteral,
414 AllocSite asStringLiteralBytes,
415 FieldDescriptor fdStringBytesField) {
416 // model this to get points-to information right for
417 // pointers to string literals, even though it doesn't affect
418 // reachability paths in the heap
419 assignTempEqualToNewAlloc( x,
422 assignTempEqualToNewAlloc( tdStrLiteralBytes,
423 asStringLiteralBytes );
425 assignTempXFieldFEqualToTempY( x,
436 public void assignTempXEqualToTempY(TempDescriptor x,
438 assignTempXEqualToCastedTempY(x, y, null);
442 public void assignTempXEqualToCastedTempY(TempDescriptor x,
444 TypeDescriptor tdCast) {
446 VariableNode lnX = getVariableNodeFromTemp(x);
447 VariableNode lnY = getVariableNodeFromTemp(y);
449 clearRefEdgesFrom(lnX, null, null, true);
451 // note it is possible that the types of temps in the
452 // flat node to analyze will reveal that some typed
453 // edges in the reachability graph are impossible
454 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
456 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
457 while( itrYhrn.hasNext() ) {
458 RefEdge edgeY = itrYhrn.next();
459 HeapRegionNode referencee = edgeY.getDst();
460 RefEdge edgeNew = edgeY.copy();
462 if( !isSuperiorType(x.getType(), edgeY.getType() ) ) {
463 impossibleEdges.add(edgeY);
469 if( tdCast == null ) {
470 edgeNew.setType(mostSpecificType(y.getType(),
476 edgeNew.setType(mostSpecificType(y.getType(),
478 referencee.getType(),
484 edgeNew.setField(null);
486 addRefEdge(lnX, referencee, edgeNew);
489 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
490 while( itrImp.hasNext() ) {
491 RefEdge edgeImp = itrImp.next();
492 removeRefEdge(edgeImp);
497 public void assignTempXEqualToTempYFieldF(TempDescriptor x,
500 FlatNode currentProgramPoint,
501 Set<EdgeKey> edgeKeysForLoad
504 VariableNode lnX = getVariableNodeFromTemp(x);
505 VariableNode lnY = getVariableNodeFromTemp(y);
507 clearRefEdgesFrom(lnX, null, null, true);
509 // note it is possible that the types of temps in the
510 // flat node to analyze will reveal that some typed
511 // edges in the reachability graph are impossible
512 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
514 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
515 while( itrYhrn.hasNext() ) {
516 RefEdge edgeY = itrYhrn.next();
517 HeapRegionNode hrnY = edgeY.getDst();
518 ReachSet betaY = edgeY.getBeta();
520 Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
522 while( itrHrnFhrn.hasNext() ) {
523 RefEdge edgeHrn = itrHrnFhrn.next();
524 HeapRegionNode hrnHrn = edgeHrn.getDst();
525 ReachSet betaHrn = edgeHrn.getBeta();
527 // prune edges that are not a matching field
528 if( edgeHrn.getType() != null &&
529 !edgeHrn.getField().equals(f.getSymbol() )
534 // check for impossible edges
535 if( !isSuperiorType(x.getType(), edgeHrn.getType() ) ) {
536 impossibleEdges.add(edgeHrn);
540 // for definite reach analysis only
541 if( edgeKeysForLoad != null ) {
543 edgeKeysForLoad.add( new EdgeKey( hrnY.getID(),
550 TypeDescriptor tdNewEdge =
551 mostSpecificType(edgeHrn.getType(),
555 TaintSet taints = Canonical.unionORpreds(edgeHrn.getTaints(),
559 // the DFJ way to generate taints changes for field statements
560 taints = Canonical.changeWhereDefined(taints,
561 currentProgramPoint);
564 RefEdge edgeNew = new RefEdge(lnX,
568 Canonical.intersection(betaY, betaHrn),
573 addEdgeOrMergeWithExisting(edgeNew);
577 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
578 while( itrImp.hasNext() ) {
579 RefEdge edgeImp = itrImp.next();
580 removeRefEdge(edgeImp);
583 // anytime you might remove edges between heap regions
584 // you must global sweep to clean up broken reachability
585 if( !impossibleEdges.isEmpty() ) {
586 if( !DISABLE_GLOBAL_SWEEP ) {
594 // return whether a strong update was actually effected
595 public boolean assignTempXFieldFEqualToTempY(TempDescriptor x,
598 FlatNode currentProgramPoint,
599 boolean alreadyReachable,
600 Set<EdgeKey> edgeKeysRemoved,
601 Set<EdgeKey> edgeKeysAdded,
602 Set<DefiniteReachState.FdEntry> edgesToElideFromPropFd
605 VariableNode lnX = getVariableNodeFromTemp(x);
606 VariableNode lnY = getVariableNodeFromTemp(y);
608 HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
609 HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
611 // note it is possible that the types of temps in the
612 // flat node to analyze will reveal that some typed
613 // edges in the reachability graph are impossible
614 Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
616 // first look for possible strong updates and remove those edges
617 boolean strongUpdateCond = false;
618 boolean edgeRemovedByStrongUpdate = false;
620 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
621 while( itrXhrn.hasNext() ) {
622 RefEdge edgeX = itrXhrn.next();
623 HeapRegionNode hrnX = edgeX.getDst();
625 // we can do a strong update here if one of two cases holds
627 f != DisjointAnalysis.getArrayField(f.getType() ) &&
628 ( (hrnX.getNumReferencers() == 1) || // case 1
629 (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
632 if( !DISABLE_STRONG_UPDATES ) {
633 strongUpdateCond = true;
635 boolean atLeastOne = clearRefEdgesFrom(hrnX,
642 edgeRemovedByStrongUpdate = true;
649 // definite reachability analysis can elide some edges from
650 // propagating reach information
651 Set<RefEdge> edgesToElideFromProp = null;
652 if( edgesToElideFromPropFd != null ) {
653 edgesToElideFromProp = new HashSet<RefEdge>();
654 Iterator<RefEdge> itrY = lnY.iteratorToReferencees();
655 while( itrY.hasNext() ) {
656 HeapRegionNode hrnSrc = itrY.next().getDst();
658 Iterator<RefEdge> itrhrn = hrnSrc.iteratorToReferencees();
659 while( itrhrn.hasNext() ) {
660 RefEdge edgeToElide = itrhrn.next();
661 String f0 = edgeToElide.getField();
662 HeapRegionNode hrnDst = edgeToElide.getDst();
664 // does this graph edge match a statically-named edge
665 // that def reach says we don't have to prop over?
666 for( DefiniteReachState.FdEntry entry : edgesToElideFromPropFd ) {
667 if( !entry.f0.getSymbol().equals( f0 ) ) {
670 boolean refByZ = false;
671 Iterator<RefEdge> itrRef = hrnDst.iteratorToReferencers();
672 while( itrRef.hasNext() ) {
673 RefEdge edgeZ = itrRef.next();
674 if( edgeZ.getSrc() instanceof VariableNode ) {
675 VariableNode vnZ = (VariableNode) edgeZ.getSrc();
676 if( vnZ.getTempDescriptor().equals( entry.z ) ) {
683 // this graph edge matches the def reach edge, mark it for
685 edgesToElideFromProp.add( edgeToElide );
694 // definite reachability analysis can elide reachability propagation
695 if( !alreadyReachable ) {
697 // then do all token propagation
698 itrXhrn = lnX.iteratorToReferencees();
699 while( itrXhrn.hasNext() ) {
700 RefEdge edgeX = itrXhrn.next();
701 HeapRegionNode hrnX = edgeX.getDst();
702 ReachSet betaX = edgeX.getBeta();
703 ReachSet R = Canonical.intersection(hrnX.getAlpha(),
707 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
708 while( itrYhrn.hasNext() ) {
709 RefEdge edgeY = itrYhrn.next();
710 HeapRegionNode hrnY = edgeY.getDst();
711 ReachSet O = edgeY.getBeta();
713 // check for impossible edges
714 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
715 impossibleEdges.add(edgeY);
719 // propagate tokens over nodes starting from hrnSrc, and it will
720 // take care of propagating back up edges from any touched nodes
721 ChangeSet Cy = Canonical.unionUpArityToChangeSet(O, R);
722 propagateTokensOverNodes( hrnY,
726 edgesToElideFromProp );
728 // then propagate back just up the edges from hrn
729 ChangeSet Cx = Canonical.unionUpArityToChangeSet(R, O);
730 HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
732 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
733 new Hashtable<RefEdge, ChangeSet>();
735 Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
736 while( referItr.hasNext() ) {
737 RefEdge edgeUpstream = referItr.next();
738 todoEdges.add(edgeUpstream);
739 edgePlannedChanges.put(edgeUpstream, Cx);
742 propagateTokensOverEdges( todoEdges,
745 edgesToElideFromProp );
751 // apply the updates to reachability
752 Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
753 while( nodeItr.hasNext() ) {
754 nodeItr.next().applyAlphaNew();
757 Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
758 while( edgeItr.hasNext() ) {
759 edgeItr.next().applyBetaNew();
763 // then go back through and add the new edges
764 itrXhrn = lnX.iteratorToReferencees();
765 while( itrXhrn.hasNext() ) {
766 RefEdge edgeX = itrXhrn.next();
767 HeapRegionNode hrnX = edgeX.getDst();
769 Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
770 while( itrYhrn.hasNext() ) {
771 RefEdge edgeY = itrYhrn.next();
772 HeapRegionNode hrnY = edgeY.getDst();
774 // skip impossible edges here, we already marked them
775 // when computing reachability propagations above
776 if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
781 // for definite reach analysis only
782 if( edgeKeysAdded != null ) {
784 edgeKeysAdded.add( new EdgeKey( hrnX.getID(),
792 // prepare the new reference edge hrnX.f -> hrnY
793 TypeDescriptor tdNewEdge =
794 mostSpecificType(y.getType(),
799 TaintSet taints = edgeY.getTaints();
802 // the DFJ way to generate taints changes for field statements
803 taints = Canonical.changeWhereDefined(taints,
804 currentProgramPoint);
809 if( alreadyReachable ) {
810 betaNew = edgeY.getBeta();
812 betaNew = Canonical.pruneBy( edgeY.getBeta(),
822 Canonical.changePredsTo( betaNew,
828 addEdgeOrMergeWithExisting(edgeNew);
832 Iterator<RefEdge> itrImp = impossibleEdges.iterator();
833 while( itrImp.hasNext() ) {
834 RefEdge edgeImp = itrImp.next();
835 removeRefEdge(edgeImp);
838 // if there was a strong update, make sure to improve
839 // reachability with a global sweep
840 if( edgeRemovedByStrongUpdate || !impossibleEdges.isEmpty() ) {
841 if( !DISABLE_GLOBAL_SWEEP ) {
846 return edgeRemovedByStrongUpdate;
850 public void assignReturnEqualToTemp(TempDescriptor x) {
852 VariableNode lnR = getVariableNodeFromTemp(tdReturn);
853 VariableNode lnX = getVariableNodeFromTemp(x);
855 clearRefEdgesFrom(lnR, null, null, true);
857 Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
858 while( itrXhrn.hasNext() ) {
859 RefEdge edgeX = itrXhrn.next();
860 HeapRegionNode referencee = edgeX.getDst();
861 RefEdge edgeNew = edgeX.copy();
863 edgeNew.setTaints(Canonical.changePredsTo(edgeNew.getTaints(),
868 addRefEdge(lnR, referencee, edgeNew);
873 public void assignTempEqualToNewAlloc(TempDescriptor x,
880 // after the age operation the newest (or zero-ith oldest)
881 // node associated with the allocation site should have
882 // no references to it as if it were a newly allocated
884 Integer idNewest = as.getIthOldest(0);
885 HeapRegionNode hrnNewest = id2hrn.get(idNewest);
886 assert hrnNewest != null;
888 VariableNode lnX = getVariableNodeFromTemp(x);
889 clearRefEdgesFrom(lnX, null, null, true);
891 // make a new reference to allocated node
892 TypeDescriptor type = as.getType();
895 new RefEdge(lnX, // source
899 hrnNewest.getAlpha(), // beta
900 predsTrue, // predicates
901 TaintSet.factory() // taints
904 addRefEdge(lnX, hrnNewest, edgeNew);
908 // use the allocation site (unique to entire analysis) to
909 // locate the heap region nodes in this reachability graph
910 // that should be aged. The process models the allocation
911 // of new objects and collects all the oldest allocations
912 // in a summary node to allow for a finite analysis
914 // There is an additional property of this method. After
915 // running it on a particular reachability graph (many graphs
916 // may have heap regions related to the same allocation site)
917 // the heap region node objects in this reachability graph will be
918 // allocated. Therefore, after aging a graph for an allocation
919 // site, attempts to retrieve the heap region nodes using the
920 // integer id's contained in the allocation site should always
921 // return non-null heap regions.
922 public void age(AllocSite as) {
924 // keep track of allocation sites that are represented
925 // in this graph for efficiency with other operations
928 // if there is a k-th oldest node, it merges into
930 Integer idK = as.getOldest();
931 if( id2hrn.containsKey(idK) ) {
932 HeapRegionNode hrnK = id2hrn.get(idK);
934 // retrieve the summary node, or make it
936 HeapRegionNode hrnSummary = getSummaryNode(as, false);
938 mergeIntoSummary(hrnK, hrnSummary);
941 // move down the line of heap region nodes
942 // clobbering the ith and transferring all references
943 // to and from i-1 to node i.
944 for( int i = allocationDepth - 1; i > 0; --i ) {
946 // only do the transfer if the i-1 node exists
947 Integer idImin1th = as.getIthOldest(i - 1);
948 if( id2hrn.containsKey(idImin1th) ) {
949 HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
950 if( hrnImin1.isWiped() ) {
951 // there is no info on this node, just skip
955 // either retrieve or make target of transfer
956 HeapRegionNode hrnI = getIthNode(as, i, false);
958 transferOnto(hrnImin1, hrnI);
963 // as stated above, the newest node should have had its
964 // references moved over to the second oldest, so we wipe newest
965 // in preparation for being the new object to assign something to
966 HeapRegionNode hrn0 = getIthNode(as, 0, false);
969 // now tokens in reachability sets need to "age" also
970 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
971 while( itrAllHRNodes.hasNext() ) {
972 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
973 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
975 ageTuplesFrom(as, hrnToAge);
977 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
978 while( itrEdges.hasNext() ) {
979 ageTuplesFrom(as, itrEdges.next() );
984 // after tokens have been aged, reset newest node's reachability
985 // and a brand new node has a "true" predicate
986 hrn0.setAlpha( Canonical.changePredsTo( hrn0.getInherent(), predsTrue ) );
987 hrn0.setPreds( predsTrue);
991 // either retrieve or create the needed heap region node
992 protected HeapRegionNode getSummaryNode(AllocSite as,
997 idSummary = as.getSummaryShadow();
999 idSummary = as.getSummary();
1002 HeapRegionNode hrnSummary = id2hrn.get(idSummary);
1004 if( hrnSummary == null ) {
1006 String strDesc = as.toStringForDOT()+"\\nsummary";
1009 createNewHeapRegionNode(idSummary, // id or null to generate a new one
1010 false, // single object?
1012 false, // out-of-context?
1013 as.getType(), // type
1014 as, // allocation site
1015 null, // inherent reach
1016 null, // current reach
1017 predsEmpty, // predicates
1018 strDesc // description
1025 // either retrieve or create the needed heap region node
1026 protected HeapRegionNode getIthNode(AllocSite as,
1032 idIth = as.getIthOldestShadow(i);
1034 idIth = as.getIthOldest(i);
1037 HeapRegionNode hrnIth = id2hrn.get(idIth);
1039 if( hrnIth == null ) {
1041 String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
1043 hrnIth = createNewHeapRegionNode(idIth, // id or null to generate a new one
1044 true, // single object?
1046 false, // out-of-context?
1047 as.getType(), // type
1048 as, // allocation site
1049 null, // inherent reach
1050 null, // current reach
1051 predsEmpty, // predicates
1052 strDesc // description
1060 protected void mergeIntoSummary(HeapRegionNode hrn,
1061 HeapRegionNode hrnSummary) {
1062 assert hrnSummary.isNewSummary();
1064 // assert that these nodes belong to THIS graph
1065 assert belongsToThis(hrn);
1066 assert belongsToThis(hrnSummary);
1068 assert hrn != hrnSummary;
1070 // transfer references _from_ hrn over to hrnSummary
1071 Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
1072 while( itrReferencee.hasNext() ) {
1073 RefEdge edge = itrReferencee.next();
1074 RefEdge edgeMerged = edge.copy();
1075 edgeMerged.setSrc(hrnSummary);
1077 HeapRegionNode hrnReferencee = edge.getDst();
1078 RefEdge edgeSummary =
1079 hrnSummary.getReferenceTo(hrnReferencee,
1084 if( edgeSummary == null ) {
1085 // the merge is trivial, nothing to be done
1086 addRefEdge(hrnSummary, hrnReferencee, edgeMerged);
1089 // otherwise an edge from the referencer to hrnSummary exists already
1090 // and the edge referencer->hrn should be merged with it
1091 edgeSummary.setBeta(
1092 Canonical.unionORpreds(edgeMerged.getBeta(),
1093 edgeSummary.getBeta()
1096 edgeSummary.setPreds(
1097 Canonical.join(edgeMerged.getPreds(),
1098 edgeSummary.getPreds()
1104 // next transfer references _to_ hrn over to hrnSummary
1105 Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
1106 while( itrReferencer.hasNext() ) {
1107 RefEdge edge = itrReferencer.next();
1108 RefEdge edgeMerged = edge.copy();
1109 edgeMerged.setDst(hrnSummary);
1111 RefSrcNode onReferencer = edge.getSrc();
1112 RefEdge edgeSummary =
1113 onReferencer.getReferenceTo(hrnSummary,
1118 if( edgeSummary == null ) {
1119 // the merge is trivial, nothing to be done
1120 addRefEdge(onReferencer, hrnSummary, edgeMerged);
1123 // otherwise an edge from the referencer to alpha_S exists already
1124 // and the edge referencer->alpha_K should be merged with it
1125 edgeSummary.setBeta(
1126 Canonical.unionORpreds(edgeMerged.getBeta(),
1127 edgeSummary.getBeta()
1130 edgeSummary.setPreds(
1131 Canonical.join(edgeMerged.getPreds(),
1132 edgeSummary.getPreds()
1138 // then merge hrn reachability into hrnSummary
1139 hrnSummary.setAlpha(
1140 Canonical.unionORpreds(hrnSummary.getAlpha(),
1145 hrnSummary.setPreds(
1146 Canonical.join(hrnSummary.getPreds(),
1151 // and afterward, this node is gone
1156 protected void transferOnto(HeapRegionNode hrnA,
1157 HeapRegionNode hrnB) {
1159 assert belongsToThis(hrnA);
1160 assert belongsToThis(hrnB);
1161 assert hrnA != hrnB;
1163 // clear references in and out of node b?
1164 assert hrnB.isWiped();
1166 // copy each: (edge in and out of A) to B
1167 Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
1168 while( itrReferencee.hasNext() ) {
1169 RefEdge edge = itrReferencee.next();
1170 HeapRegionNode hrnReferencee = edge.getDst();
1171 RefEdge edgeNew = edge.copy();
1172 edgeNew.setSrc(hrnB);
1173 edgeNew.setDst(hrnReferencee);
1175 addRefEdge(hrnB, hrnReferencee, edgeNew);
1178 Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
1179 while( itrReferencer.hasNext() ) {
1180 RefEdge edge = itrReferencer.next();
1181 RefSrcNode rsnReferencer = edge.getSrc();
1182 RefEdge edgeNew = edge.copy();
1183 edgeNew.setSrc(rsnReferencer);
1184 edgeNew.setDst(hrnB);
1186 addRefEdge(rsnReferencer, hrnB, edgeNew);
1189 // replace hrnB reachability and preds with hrnA's
1190 hrnB.setAlpha(hrnA.getAlpha() );
1191 hrnB.setPreds(hrnA.getPreds() );
1193 // after transfer, wipe out source
1194 wipeOut(hrnA, true);
1198 // the purpose of this method is to conceptually "wipe out"
1199 // a heap region from the graph--purposefully not called REMOVE
1200 // because the node is still hanging around in the graph, just
1201 // not mechanically connected or have any reach or predicate
1202 // information on it anymore--lots of ops can use this
1203 protected void wipeOut(HeapRegionNode hrn,
1204 boolean wipeVariableReferences) {
1206 assert belongsToThis(hrn);
1208 clearRefEdgesFrom(hrn, null, null, true);
1210 if( wipeVariableReferences ) {
1211 clearRefEdgesTo(hrn, null, null, true);
1213 clearNonVarRefEdgesTo(hrn);
1216 hrn.setAlpha(rsetEmpty);
1217 hrn.setPreds(predsEmpty);
1221 protected void ageTuplesFrom(AllocSite as, RefEdge edge) {
1223 Canonical.ageTuplesFrom(edge.getBeta(),
1229 protected void ageTuplesFrom(AllocSite as, HeapRegionNode hrn) {
1231 Canonical.ageTuplesFrom(hrn.getAlpha(),
1239 protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1241 HashSet<HeapRegionNode> nodesWithNewAlpha,
1242 HashSet<RefEdge> edgesWithNewBeta,
1243 Set<RefEdge> edgesToElideProp ) {
1245 HashSet<HeapRegionNode> todoNodes
1246 = new HashSet<HeapRegionNode>();
1247 todoNodes.add(nPrime);
1249 HashSet<RefEdge> todoEdges
1250 = new HashSet<RefEdge>();
1252 Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1253 = new Hashtable<HeapRegionNode, ChangeSet>();
1254 nodePlannedChanges.put(nPrime, c0);
1256 Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1257 = new Hashtable<RefEdge, ChangeSet>();
1259 // first propagate change sets everywhere they can go
1260 while( !todoNodes.isEmpty() ) {
1261 HeapRegionNode n = todoNodes.iterator().next();
1262 ChangeSet C = nodePlannedChanges.get(n);
1264 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1265 while( referItr.hasNext() ) {
1266 RefEdge edge = referItr.next();
1268 if( edgesToElideProp != null && edgesToElideProp.contains( edge ) ) {
1271 todoEdges.add(edge);
1273 if( !edgePlannedChanges.containsKey(edge) ) {
1274 edgePlannedChanges.put(edge,
1279 edgePlannedChanges.put(edge,
1280 Canonical.union(edgePlannedChanges.get(edge),
1286 Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1287 while( refeeItr.hasNext() ) {
1288 RefEdge edgeF = refeeItr.next();
1290 if( edgesToElideProp != null && edgesToElideProp.contains( edgeF ) ) {
1294 HeapRegionNode m = edgeF.getDst();
1296 ChangeSet changesToPass = ChangeSet.factory();
1298 Iterator<ChangeTuple> itrCprime = C.iterator();
1299 while( itrCprime.hasNext() ) {
1300 ChangeTuple c = itrCprime.next();
1301 if( edgeF.getBeta().containsIgnorePreds(c.getStateToMatch() )
1304 changesToPass = Canonical.add(changesToPass, c);
1308 if( !changesToPass.isEmpty() ) {
1309 if( !nodePlannedChanges.containsKey(m) ) {
1310 nodePlannedChanges.put(m, ChangeSet.factory() );
1313 ChangeSet currentChanges = nodePlannedChanges.get(m);
1315 if( !changesToPass.isSubset(currentChanges) ) {
1317 nodePlannedChanges.put(m,
1318 Canonical.union(currentChanges,
1327 todoNodes.remove(n);
1330 // then apply all of the changes for each node at once
1331 Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1332 while( itrMap.hasNext() ) {
1333 Map.Entry me = (Map.Entry)itrMap.next();
1334 HeapRegionNode n = (HeapRegionNode) me.getKey();
1335 ChangeSet C = (ChangeSet) me.getValue();
1337 // this propagation step is with respect to one change,
1338 // so we capture the full change from the old alpha:
1339 ReachSet localDelta = Canonical.applyChangeSet(n.getAlpha(),
1343 // but this propagation may be only one of many concurrent
1344 // possible changes, so keep a running union with the node's
1345 // partially updated new alpha set
1346 n.setAlphaNew(Canonical.unionORpreds(n.getAlphaNew(),
1351 nodesWithNewAlpha.add(n);
1354 propagateTokensOverEdges(todoEdges,
1361 protected void propagateTokensOverEdges(HashSet <RefEdge> todoEdges,
1362 Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1363 HashSet <RefEdge> edgesWithNewBeta,
1364 Set<RefEdge> edgesToElideProp ) {
1366 // first propagate all change tuples everywhere they can go
1367 while( !todoEdges.isEmpty() ) {
1368 RefEdge edgeE = todoEdges.iterator().next();
1369 todoEdges.remove(edgeE);
1371 if( !edgePlannedChanges.containsKey(edgeE) ) {
1372 edgePlannedChanges.put(edgeE,
1377 ChangeSet C = edgePlannedChanges.get(edgeE);
1379 ChangeSet changesToPass = ChangeSet.factory();
1381 Iterator<ChangeTuple> itrC = C.iterator();
1382 while( itrC.hasNext() ) {
1383 ChangeTuple c = itrC.next();
1384 if( edgeE.getBeta().containsIgnorePreds(c.getStateToMatch() )
1387 changesToPass = Canonical.add(changesToPass, c);
1391 RefSrcNode rsn = edgeE.getSrc();
1393 if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1394 HeapRegionNode n = (HeapRegionNode) rsn;
1396 Iterator<RefEdge> referItr = n.iteratorToReferencers();
1397 while( referItr.hasNext() ) {
1398 RefEdge edgeF = referItr.next();
1400 if( edgesToElideProp != null && edgesToElideProp.contains( edgeF ) ) {
1404 if( !edgePlannedChanges.containsKey(edgeF) ) {
1405 edgePlannedChanges.put(edgeF,
1410 ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
1412 if( !changesToPass.isSubset(currentChanges) ) {
1413 todoEdges.add(edgeF);
1414 edgePlannedChanges.put(edgeF,
1415 Canonical.union(currentChanges,
1424 // then apply all of the changes for each edge at once
1425 Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1426 while( itrMap.hasNext() ) {
1427 Map.Entry me = (Map.Entry)itrMap.next();
1428 RefEdge e = (RefEdge) me.getKey();
1429 ChangeSet C = (ChangeSet) me.getValue();
1431 // this propagation step is with respect to one change,
1432 // so we capture the full change from the old beta:
1433 ReachSet localDelta =
1434 Canonical.applyChangeSet(e.getBeta(),
1439 // but this propagation may be only one of many concurrent
1440 // possible changes, so keep a running union with the edge's
1441 // partially updated new beta set
1442 e.setBetaNew(Canonical.unionORpreds(e.getBetaNew(),
1447 edgesWithNewBeta.add(e);
1452 public void taintInSetVars(FlatSESEEnterNode sese) {
1454 Iterator<TempDescriptor> isvItr = sese.getInVarSet().iterator();
1455 while( isvItr.hasNext() ) {
1456 TempDescriptor isv = isvItr.next();
1458 // use this where defined flatnode to support RCR/DFJ
1459 FlatNode whereDefined = null;
1461 // in-set var taints should NOT propagate back into callers
1462 // so give it FALSE(EMPTY) predicates
1472 public void taintStallSite(FlatNode stallSite,
1473 TempDescriptor var) {
1475 // use this where defined flatnode to support RCR/DFJ
1476 FlatNode whereDefined = null;
1478 // stall site taint should propagate back into callers
1479 // so give it TRUE predicates
1488 protected void taintTemp(FlatSESEEnterNode sese,
1491 FlatNode whereDefined,
1495 VariableNode vn = getVariableNodeFromTemp(var);
1497 Iterator<RefEdge> reItr = vn.iteratorToReferencees();
1498 while( reItr.hasNext() ) {
1499 RefEdge re = reItr.next();
1501 Taint taint = Taint.factory(sese,
1504 re.getDst().getAllocSite(),
1509 re.setTaints(Canonical.add(re.getTaints(),
1516 public void removeInContextTaints(FlatSESEEnterNode sese) {
1518 Iterator meItr = id2hrn.entrySet().iterator();
1519 while( meItr.hasNext() ) {
1520 Map.Entry me = (Map.Entry)meItr.next();
1521 Integer id = (Integer) me.getKey();
1522 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1524 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1525 while( reItr.hasNext() ) {
1526 RefEdge re = reItr.next();
1528 re.setTaints(Canonical.removeInContextTaints(re.getTaints(),
1536 public void removeAllStallSiteTaints() {
1538 Iterator meItr = id2hrn.entrySet().iterator();
1539 while( meItr.hasNext() ) {
1540 Map.Entry me = (Map.Entry)meItr.next();
1541 Integer id = (Integer) me.getKey();
1542 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1544 Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
1545 while( reItr.hasNext() ) {
1546 RefEdge re = reItr.next();
1548 re.setTaints(Canonical.removeStallSiteTaints(re.getTaints()
1556 // used in makeCalleeView below to decide if there is
1557 // already an appropriate out-of-context edge in a callee
1558 // view graph for merging, or null if a new one will be added
1560 getOutOfContextReferenceTo(HeapRegionNode hrn,
1561 TypeDescriptor srcType,
1562 TypeDescriptor refType,
1564 assert belongsToThis(hrn);
1566 HeapRegionNode hrnInContext = id2hrn.get(hrn.getID() );
1567 if( hrnInContext == null ) {
1571 Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1572 while( refItr.hasNext() ) {
1573 RefEdge re = refItr.next();
1575 assert belongsToThis(re.getSrc() );
1576 assert belongsToThis(re.getDst() );
1578 if( !(re.getSrc() instanceof HeapRegionNode) ) {
1582 HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1583 if( !hrnSrc.isOutOfContext() ) {
1587 if( srcType == null ) {
1588 if( hrnSrc.getType() != null ) {
1592 if( !srcType.equals(hrnSrc.getType() ) ) {
1597 if( !re.typeEquals(refType) ) {
1601 if( !re.fieldEquals(refField) ) {
1605 // tada! We found it!
1612 // used below to convert a ReachSet to its callee-context
1613 // equivalent with respect to allocation sites in this graph
1614 protected ReachSet toCalleeContext(ReachSet rs,
1615 ExistPredSet predsNodeOrEdge,
1616 Set<HrnIdOoc> oocHrnIdOoc2callee
1618 ReachSet out = ReachSet.factory();
1620 Iterator<ReachState> itr = rs.iterator();
1621 while( itr.hasNext() ) {
1622 ReachState stateCaller = itr.next();
1624 ReachState stateCallee = stateCaller;
1626 Iterator<AllocSite> asItr = allocSites.iterator();
1627 while( asItr.hasNext() ) {
1628 AllocSite as = asItr.next();
1630 ReachState stateNew = ReachState.factory();
1631 Iterator<ReachTuple> rtItr = stateCallee.iterator();
1632 while( rtItr.hasNext() ) {
1633 ReachTuple rt = rtItr.next();
1635 // only translate this tuple if it is
1636 // in the out-callee-context bag
1637 HrnIdOoc hio = new HrnIdOoc(rt.getHrnID(),
1640 if( !oocHrnIdOoc2callee.contains(hio) ) {
1641 stateNew = Canonical.addUpArity(stateNew, rt);
1645 int age = as.getAgeCategory(rt.getHrnID() );
1647 // this is the current mapping, where 0, 1, 2S were allocated
1648 // in the current context, 0?, 1? and 2S? were allocated in a
1649 // previous context, and we're translating to a future context
1661 if( age == AllocSite.AGE_notInThisSite ) {
1662 // things not from the site just go back in
1663 stateNew = Canonical.addUpArity(stateNew, rt);
1665 } else if( age == AllocSite.AGE_summary ||
1669 stateNew = Canonical.addUpArity(stateNew,
1670 ReachTuple.factory(as.getSummary(),
1673 true // out-of-context
1678 // otherwise everything else just goes to an out-of-context
1679 // version, everything else the same
1680 Integer I = as.getAge(rt.getHrnID() );
1683 assert !rt.isMultiObject();
1685 stateNew = Canonical.addUpArity(stateNew,
1686 ReachTuple.factory(rt.getHrnID(),
1687 rt.isMultiObject(), // multi
1689 true // out-of-context
1695 stateCallee = stateNew;
1698 // make a predicate of the caller graph element
1699 // and the caller state we just converted
1700 ExistPredSet predsWithState = ExistPredSet.factory();
1702 Iterator<ExistPred> predItr = predsNodeOrEdge.iterator();
1703 while( predItr.hasNext() ) {
1704 ExistPred predNodeOrEdge = predItr.next();
1707 Canonical.add(predsWithState,
1708 ExistPred.factory(predNodeOrEdge.n_hrnID,
1709 predNodeOrEdge.e_tdSrc,
1710 predNodeOrEdge.e_hrnSrcID,
1711 predNodeOrEdge.e_hrnDstID,
1712 predNodeOrEdge.e_type,
1713 predNodeOrEdge.e_field,
1716 predNodeOrEdge.e_srcOutCalleeContext,
1717 predNodeOrEdge.e_srcOutCallerContext
1722 stateCallee = Canonical.changePredsTo(stateCallee,
1725 out = Canonical.add(out,
1729 assert out.isCanonical();
1733 // used below to convert a ReachSet to its caller-context
1734 // equivalent with respect to allocation sites in this graph
1736 toCallerContext(ReachSet rs,
1737 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1739 ReachSet out = ReachSet.factory();
1741 // when the mapping is null it means there were no
1742 // predicates satisfied
1743 if( calleeStatesSatisfied == null ) {
1747 Iterator<ReachState> itr = rs.iterator();
1748 while( itr.hasNext() ) {
1749 ReachState stateCallee = itr.next();
1751 if( calleeStatesSatisfied.containsKey(stateCallee) ) {
1753 // starting from one callee state...
1754 ReachSet rsCaller = ReachSet.factory(stateCallee);
1756 // possibly branch it into many states, which any
1757 // allocation site might do, so lots of derived states
1758 Iterator<AllocSite> asItr = allocSites.iterator();
1759 while( asItr.hasNext() ) {
1760 AllocSite as = asItr.next();
1761 rsCaller = Canonical.toCallerContext(rsCaller, as);
1764 // then before adding each derived, now caller-context
1765 // states to the output, attach the appropriate pred
1766 // based on the source callee state
1767 Iterator<ReachState> stateItr = rsCaller.iterator();
1768 while( stateItr.hasNext() ) {
1769 ReachState stateCaller = stateItr.next();
1770 stateCaller = Canonical.attach(stateCaller,
1771 calleeStatesSatisfied.get(stateCallee)
1773 out = Canonical.add(out,
1780 assert out.isCanonical();
1785 // used below to convert a ReachSet to an equivalent
1786 // version with shadow IDs merged into unshadowed IDs
1787 protected ReachSet unshadow(ReachSet rs) {
1789 Iterator<AllocSite> asItr = allocSites.iterator();
1790 while( asItr.hasNext() ) {
1791 AllocSite as = asItr.next();
1792 out = Canonical.unshadow(out, as);
1794 assert out.isCanonical();
1799 // convert a caller taint set into a callee taint set
1801 toCalleeContext(TaintSet ts,
1802 ExistPredSet predsEdge) {
1804 TaintSet out = TaintSet.factory();
1806 // the idea is easy, the taint identifier itself doesn't
1807 // change at all, but the predicates should be tautology:
1808 // start with the preds passed in from the caller edge
1809 // that host the taints, and alter them to have the taint
1810 // added, just becoming more specific than edge predicate alone
1812 Iterator<Taint> itr = ts.iterator();
1813 while( itr.hasNext() ) {
1814 Taint tCaller = itr.next();
1816 ExistPredSet predsWithTaint = ExistPredSet.factory();
1818 Iterator<ExistPred> predItr = predsEdge.iterator();
1819 while( predItr.hasNext() ) {
1820 ExistPred predEdge = predItr.next();
1823 Canonical.add(predsWithTaint,
1824 ExistPred.factory(predEdge.e_tdSrc,
1825 predEdge.e_hrnSrcID,
1826 predEdge.e_hrnDstID,
1831 predEdge.e_srcOutCalleeContext,
1832 predEdge.e_srcOutCallerContext
1837 Taint tCallee = Canonical.changePredsTo(tCaller,
1840 out = Canonical.add(out,
1845 assert out.isCanonical();
1850 // used below to convert a TaintSet to its caller-context
1851 // equivalent, just eliminate Taints with bad preds
1853 toCallerContext(TaintSet ts,
1854 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied
1857 TaintSet out = TaintSet.factory();
1859 // when the mapping is null it means there were no
1860 // predicates satisfied
1861 if( calleeTaintsSatisfied == null ) {
1865 Iterator<Taint> itr = ts.iterator();
1866 while( itr.hasNext() ) {
1867 Taint tCallee = itr.next();
1869 if( calleeTaintsSatisfied.containsKey(tCallee) ) {
1872 Canonical.attach(Taint.factory(tCallee.sese,
1877 ExistPredSet.factory() ),
1878 calleeTaintsSatisfied.get(tCallee)
1880 out = Canonical.add(out,
1886 assert out.isCanonical();
1893 // use this method to make a new reach graph that is
1894 // what heap the FlatMethod callee from the FlatCall
1895 // would start with reaching from its arguments in
1898 makeCalleeView(FlatCall fc,
1899 FlatMethod fmCallee,
1900 Set<Integer> callerNodeIDsCopiedToCallee,
1901 boolean writeDebugDOTs
1905 // first traverse this context to find nodes and edges
1906 // that will be callee-reachable
1907 Set<HeapRegionNode> reachableCallerNodes =
1908 new HashSet<HeapRegionNode>();
1910 // caller edges between callee-reachable nodes
1911 Set<RefEdge> reachableCallerEdges =
1912 new HashSet<RefEdge>();
1914 // caller edges from arg vars, and the matching param index
1915 // because these become a special edge in callee
1916 // NOTE! One argument may be passed in as more than one parameter,
1917 // so map to a set of parameter indices!
1918 Hashtable< RefEdge, Set<Integer> > reachableCallerArgEdges2paramIndices =
1919 new Hashtable< RefEdge, Set<Integer> >();
1921 // caller edges from local vars or callee-unreachable nodes
1922 // (out-of-context sources) to callee-reachable nodes
1923 Set<RefEdge> oocCallerEdges =
1924 new HashSet<RefEdge>();
1927 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1929 TempDescriptor tdArg = fc.getArgMatchingParamIndex(fmCallee, i);
1930 VariableNode vnArgCaller = this.getVariableNodeFromTemp(tdArg);
1932 Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1933 Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1935 toVisitInCaller.add(vnArgCaller);
1937 while( !toVisitInCaller.isEmpty() ) {
1938 RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1939 toVisitInCaller.remove(rsnCaller);
1940 visitedInCaller.add(rsnCaller);
1942 Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1943 while( itrRefEdges.hasNext() ) {
1944 RefEdge reCaller = itrRefEdges.next();
1945 HeapRegionNode hrnCaller = reCaller.getDst();
1947 callerNodeIDsCopiedToCallee.add(hrnCaller.getID() );
1948 reachableCallerNodes.add(hrnCaller);
1950 if( reCaller.getSrc() instanceof HeapRegionNode ) {
1951 reachableCallerEdges.add(reCaller);
1954 if( rsnCaller.equals(vnArgCaller) ) {
1955 Set<Integer> pIndices =
1956 reachableCallerArgEdges2paramIndices.get( reCaller );
1958 if( pIndices == null ) {
1959 pIndices = new HashSet<Integer>();
1960 reachableCallerArgEdges2paramIndices.put( reCaller, pIndices );
1965 oocCallerEdges.add(reCaller);
1969 if( !visitedInCaller.contains(hrnCaller) ) {
1970 toVisitInCaller.add(hrnCaller);
1973 } // end edge iteration
1974 } // end visiting heap nodes in caller
1975 } // end iterating over parameters as starting points
1979 // now collect out-of-callee-context IDs and
1980 // map them to whether the ID is out of the caller
1982 Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1984 Iterator<Integer> itrInContext =
1985 callerNodeIDsCopiedToCallee.iterator();
1986 while( itrInContext.hasNext() ) {
1987 Integer hrnID = itrInContext.next();
1988 HeapRegionNode hrnCallerAndInContext = id2hrn.get(hrnID);
1990 Iterator<RefEdge> itrMightCross =
1991 hrnCallerAndInContext.iteratorToReferencers();
1992 while( itrMightCross.hasNext() ) {
1993 RefEdge edgeMightCross = itrMightCross.next();
1995 RefSrcNode rsnCallerAndOutContext =
1996 edgeMightCross.getSrc();
1998 if( rsnCallerAndOutContext instanceof VariableNode ) {
1999 // variables do not have out-of-context reach states,
2001 oocCallerEdges.add(edgeMightCross);
2005 HeapRegionNode hrnCallerAndOutContext =
2006 (HeapRegionNode) rsnCallerAndOutContext;
2008 // is this source node out-of-context?
2009 if( callerNodeIDsCopiedToCallee.contains(hrnCallerAndOutContext.getID() ) ) {
2010 // no, skip this edge
2015 oocCallerEdges.add(edgeMightCross);
2017 // add all reach tuples on the node to list
2018 // of things that are out-of-context: insight
2019 // if this node is reachable from someting that WAS
2020 // in-context, then this node should already be in-context
2021 Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
2022 while( stateItr.hasNext() ) {
2023 ReachState state = stateItr.next();
2025 Iterator<ReachTuple> rtItr = state.iterator();
2026 while( rtItr.hasNext() ) {
2027 ReachTuple rt = rtItr.next();
2029 oocHrnIdOoc2callee.add(new HrnIdOoc(rt.getHrnID(),
2038 // the callee view is a new graph: DON'T MODIFY *THIS* graph
2039 ReachGraph rg = new ReachGraph();
2041 // add nodes to callee graph
2042 Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
2043 while( hrnItr.hasNext() ) {
2044 HeapRegionNode hrnCaller = hrnItr.next();
2046 assert callerNodeIDsCopiedToCallee.contains(hrnCaller.getID() );
2047 assert !rg.id2hrn.containsKey(hrnCaller.getID() );
2049 ExistPred pred = ExistPred.factory(hrnCaller.getID(), null);
2050 ExistPredSet preds = ExistPredSet.factory(pred);
2052 rg.createNewHeapRegionNode(hrnCaller.getID(),
2053 hrnCaller.isSingleObject(),
2054 hrnCaller.isNewSummary(),
2055 false, // out-of-context?
2056 hrnCaller.getType(),
2057 hrnCaller.getAllocSite(),
2058 toCalleeContext(hrnCaller.getInherent(),
2062 toCalleeContext(hrnCaller.getAlpha(),
2067 hrnCaller.getDescription()
2071 // add param edges to callee graph
2073 reachableCallerArgEdges2paramIndices.entrySet().iterator();
2074 while( argEdges.hasNext() ) {
2075 Map.Entry me = (Map.Entry) argEdges.next();
2076 RefEdge reArg = (RefEdge) me.getKey();
2077 Set<Integer> pInxs = (Set<Integer>) me.getValue();
2079 VariableNode vnCaller = (VariableNode) reArg.getSrc();
2080 TempDescriptor argCaller = vnCaller.getTempDescriptor();
2082 HeapRegionNode hrnDstCaller = reArg.getDst();
2083 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2084 assert hrnDstCallee != null;
2087 ExistPred.factory(argCaller,
2089 hrnDstCallee.getID(),
2094 true, // out-of-callee-context
2095 false // out-of-caller-context
2098 ExistPredSet preds =
2099 ExistPredSet.factory(pred);
2101 for( Integer index: pInxs ) {
2103 TempDescriptor paramCallee = fmCallee.getParameter(index);
2104 VariableNode vnCallee = rg.getVariableNodeFromTemp(paramCallee);
2107 new RefEdge(vnCallee,
2111 toCalleeContext(reArg.getBeta(),
2116 toCalleeContext(reArg.getTaints(),
2120 rg.addRefEdge(vnCallee,
2127 // add in-context edges to callee graph
2128 Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
2129 while( reItr.hasNext() ) {
2130 RefEdge reCaller = reItr.next();
2131 RefSrcNode rsnCaller = reCaller.getSrc();
2132 assert rsnCaller instanceof HeapRegionNode;
2133 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2134 HeapRegionNode hrnDstCaller = reCaller.getDst();
2136 HeapRegionNode hrnSrcCallee = rg.id2hrn.get(hrnSrcCaller.getID() );
2137 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2138 assert hrnSrcCallee != null;
2139 assert hrnDstCallee != null;
2142 ExistPred.factory(null,
2143 hrnSrcCallee.getID(),
2144 hrnDstCallee.getID(),
2146 reCaller.getField(),
2149 false, // out-of-callee-context
2150 false // out-of-caller-context
2153 ExistPredSet preds =
2154 ExistPredSet.factory(pred);
2157 new RefEdge(hrnSrcCallee,
2160 reCaller.getField(),
2161 toCalleeContext(reCaller.getBeta(),
2166 toCalleeContext(reCaller.getTaints(),
2170 rg.addRefEdge(hrnSrcCallee,
2176 // add out-of-context edges to callee graph
2177 reItr = oocCallerEdges.iterator();
2178 while( reItr.hasNext() ) {
2179 RefEdge reCaller = reItr.next();
2180 RefSrcNode rsnCaller = reCaller.getSrc();
2181 HeapRegionNode hrnDstCaller = reCaller.getDst();
2182 HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
2183 assert hrnDstCallee != null;
2185 TypeDescriptor oocNodeType;
2187 TempDescriptor oocPredSrcTemp = null;
2188 Integer oocPredSrcID = null;
2189 boolean outOfCalleeContext;
2190 boolean outOfCallerContext;
2192 if( rsnCaller instanceof VariableNode ) {
2193 VariableNode vnCaller = (VariableNode) rsnCaller;
2195 oocReach = rsetEmpty;
2196 oocPredSrcTemp = vnCaller.getTempDescriptor();
2197 outOfCalleeContext = true;
2198 outOfCallerContext = false;
2201 HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
2202 assert !callerNodeIDsCopiedToCallee.contains(hrnSrcCaller.getID() );
2203 oocNodeType = hrnSrcCaller.getType();
2204 oocReach = hrnSrcCaller.getAlpha();
2205 oocPredSrcID = hrnSrcCaller.getID();
2206 if( hrnSrcCaller.isOutOfContext() ) {
2207 outOfCalleeContext = false;
2208 outOfCallerContext = true;
2210 outOfCalleeContext = true;
2211 outOfCallerContext = false;
2216 ExistPred.factory(oocPredSrcTemp,
2218 hrnDstCallee.getID(),
2220 reCaller.getField(),
2227 ExistPredSet preds =
2228 ExistPredSet.factory(pred);
2230 RefEdge oocEdgeExisting =
2231 rg.getOutOfContextReferenceTo(hrnDstCallee,
2237 if( oocEdgeExisting == null ) {
2238 // for consistency, map one out-of-context "identifier"
2239 // to one heap region node id, otherwise no convergence
2240 String oocid = "oocid"+
2242 hrnDstCallee.getIDString()+
2245 reCaller.getField();
2247 Integer oocHrnID = oocid2hrnid.get(oocid);
2249 HeapRegionNode hrnCalleeAndOutContext;
2251 if( oocHrnID == null ) {
2253 hrnCalleeAndOutContext =
2254 rg.createNewHeapRegionNode(null, // ID
2255 false, // single object?
2256 false, // new summary?
2257 true, // out-of-context?
2259 null, // alloc site, shouldn't be used
2260 toCalleeContext(oocReach,
2264 toCalleeContext(oocReach,
2272 oocid2hrnid.put(oocid, hrnCalleeAndOutContext.getID() );
2276 // the mapping already exists, so see if node is there
2277 hrnCalleeAndOutContext = rg.id2hrn.get(oocHrnID);
2279 if( hrnCalleeAndOutContext == null ) {
2281 hrnCalleeAndOutContext =
2282 rg.createNewHeapRegionNode(oocHrnID, // ID
2283 false, // single object?
2284 false, // new summary?
2285 true, // out-of-context?
2287 null, // alloc site, shouldn't be used
2288 toCalleeContext(oocReach,
2292 toCalleeContext(oocReach,
2301 // otherwise it is there, so merge reachability
2302 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2303 toCalleeContext(oocReach,
2312 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2314 rg.addRefEdge(hrnCalleeAndOutContext,
2316 new RefEdge(hrnCalleeAndOutContext,
2319 reCaller.getField(),
2320 toCalleeContext(reCaller.getBeta(),
2325 toCalleeContext(reCaller.getTaints(),
2331 // the out-of-context edge already exists
2332 oocEdgeExisting.setBeta(Canonical.unionORpreds(oocEdgeExisting.getBeta(),
2333 toCalleeContext(reCaller.getBeta(),
2340 oocEdgeExisting.setPreds(Canonical.join(oocEdgeExisting.getPreds(),
2345 oocEdgeExisting.setTaints(Canonical.unionORpreds(oocEdgeExisting.getTaints(),
2346 toCalleeContext(reCaller.getTaints(),
2352 HeapRegionNode hrnCalleeAndOutContext =
2353 (HeapRegionNode) oocEdgeExisting.getSrc();
2354 hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2355 toCalleeContext(oocReach,
2362 assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2367 if( writeDebugDOTs ) {
2368 debugGraphPrefix = String.format("call%03d", debugCallSiteVisitCounter);
2369 rg.writeGraph(debugGraphPrefix+"calleeview",
2370 resolveMethodDebugDOTwriteLabels,
2371 resolveMethodDebugDOTselectTemps,
2372 resolveMethodDebugDOTpruneGarbage,
2373 resolveMethodDebugDOThideReach,
2374 resolveMethodDebugDOThideSubsetReach,
2375 resolveMethodDebugDOThidePreds,
2376 resolveMethodDebugDOThideEdgeTaints);
2382 private static Hashtable<String, Integer> oocid2hrnid =
2383 new Hashtable<String, Integer>();
2386 private static boolean resolveMethodDebugDOTwriteLabels = true;
2387 private static boolean resolveMethodDebugDOTselectTemps = true;
2388 private static boolean resolveMethodDebugDOTpruneGarbage = true;
2389 private static boolean resolveMethodDebugDOThideReach = false;
2390 private static boolean resolveMethodDebugDOThideSubsetReach = true;
2391 private static boolean resolveMethodDebugDOThidePreds = false;
2392 private static boolean resolveMethodDebugDOThideEdgeTaints = true;
2394 static String debugGraphPrefix;
2395 static int debugCallSiteVisitCounter;
2396 static int debugCallSiteVisitStartCapture;
2397 static int debugCallSiteNumVisitsToCapture;
2398 static boolean debugCallSiteStopAfter;
2402 resolveMethodCall(FlatCall fc,
2403 FlatMethod fmCallee,
2404 ReachGraph rgCallee,
2405 Set<Integer> callerNodeIDsCopiedToCallee,
2406 boolean writeDebugDOTs
2409 if( writeDebugDOTs ) {
2411 System.out.println(" Writing out visit "+
2412 debugCallSiteVisitCounter+
2413 " to debug call site");
2415 debugGraphPrefix = String.format("call%03d",
2416 debugCallSiteVisitCounter);
2418 rgCallee.writeGraph(debugGraphPrefix+"callee",
2419 resolveMethodDebugDOTwriteLabels,
2420 resolveMethodDebugDOTselectTemps,
2421 resolveMethodDebugDOTpruneGarbage,
2422 resolveMethodDebugDOThideReach,
2423 resolveMethodDebugDOThideSubsetReach,
2424 resolveMethodDebugDOThidePreds,
2425 resolveMethodDebugDOThideEdgeTaints);
2427 writeGraph(debugGraphPrefix+"caller00In",
2428 resolveMethodDebugDOTwriteLabels,
2429 resolveMethodDebugDOTselectTemps,
2430 resolveMethodDebugDOTpruneGarbage,
2431 resolveMethodDebugDOThideReach,
2432 resolveMethodDebugDOThideSubsetReach,
2433 resolveMethodDebugDOThidePreds,
2434 resolveMethodDebugDOThideEdgeTaints,
2435 callerNodeIDsCopiedToCallee);
2440 // method call transfer function steps:
2441 // 1. Use current callee-reachable heap (CRH) to test callee
2442 // predicates and mark what will be coming in.
2443 // 2. Wipe CRH out of caller.
2444 // 3. Transplant marked callee parts in:
2445 // a) bring in nodes
2446 // b) bring in callee -> callee edges
2447 // c) resolve out-of-context -> callee edges
2448 // d) assign return value
2449 // 4. Collapse shadow nodes down
2450 // 5. Global sweep it.
2453 // 1. mark what callee elements have satisfied predicates
2454 Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
2455 new Hashtable<HeapRegionNode, ExistPredSet>();
2457 Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
2458 new Hashtable<RefEdge, ExistPredSet>();
2460 Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
2461 calleeNode2calleeStatesSatisfied =
2462 new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
2464 Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
2465 calleeEdge2calleeStatesSatisfied =
2466 new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
2468 Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
2469 calleeEdge2calleeTaintsSatisfied =
2470 new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
2472 Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
2473 new Hashtable< RefEdge, Set<RefSrcNode> >();
2477 Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2478 while( meItr.hasNext() ) {
2479 Map.Entry me = (Map.Entry)meItr.next();
2480 Integer id = (Integer) me.getKey();
2481 HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2483 // if a callee element's predicates are satisfied then a set
2484 // of CALLER predicates is returned: they are the predicates
2485 // that the callee element moved into the caller context
2486 // should have, and it is inefficient to find this again later
2487 ExistPredSet predsIfSatis =
2488 hrnCallee.getPreds().isSatisfiedBy(this,
2489 callerNodeIDsCopiedToCallee,
2492 if( predsIfSatis != null ) {
2493 calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
2495 // otherwise don't bother looking at edges to this node
2501 // since the node is coming over, find out which reach
2502 // states on it should come over, too
2503 assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
2505 Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2506 while( stateItr.hasNext() ) {
2507 ReachState stateCallee = stateItr.next();
2510 stateCallee.getPreds().isSatisfiedBy(this,
2511 callerNodeIDsCopiedToCallee,
2513 if( predsIfSatis != null ) {
2515 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2516 calleeNode2calleeStatesSatisfied.get(hrnCallee);
2518 if( calleeStatesSatisfied == null ) {
2519 calleeStatesSatisfied =
2520 new Hashtable<ReachState, ExistPredSet>();
2522 calleeNode2calleeStatesSatisfied.put(hrnCallee, calleeStatesSatisfied);
2525 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2529 // then look at edges to the node
2530 Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2531 while( reItr.hasNext() ) {
2532 RefEdge reCallee = reItr.next();
2533 RefSrcNode rsnCallee = reCallee.getSrc();
2535 // (caller local variables to in-context heap regions)
2536 // have an (out-of-context heap region -> in-context heap region)
2537 // abstraction in the callEE, so its true we never need to
2538 // look at a (var node -> heap region) edge in callee to bring
2539 // those over for the call site transfer, except for the special
2540 // case of *RETURN var* -> heap region edges.
2541 // What about (param var->heap region)
2542 // edges in callee? They are dealt with below this loop.
2544 if( rsnCallee instanceof VariableNode ) {
2546 // looking for the return-value variable only
2547 VariableNode vnCallee = (VariableNode) rsnCallee;
2548 if( vnCallee.getTempDescriptor() != tdReturn ) {
2552 TempDescriptor returnTemp = fc.getReturnTemp();
2553 if( returnTemp == null ||
2554 !DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2559 // note that the assignment of the return value is to a
2560 // variable in the caller which is out-of-context with
2561 // respect to the callee
2562 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2563 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2564 rsnCallers.add(vnLhsCaller);
2565 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2569 // for HeapRegionNode callee sources...
2571 // first see if the source is out-of-context, and only
2572 // proceed with this edge if we find some caller-context
2574 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2575 boolean matchedOutOfContext = false;
2577 if( !hrnSrcCallee.isOutOfContext() ) {
2580 hrnSrcCallee.getPreds().isSatisfiedBy(this,
2581 callerNodeIDsCopiedToCallee,
2583 if( predsIfSatis != null ) {
2584 calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
2586 // otherwise forget this edge
2591 // hrnSrcCallee is out-of-context
2592 assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
2594 Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2596 // use the isSatisfiedBy with a non-null callers set to capture
2597 // nodes in the caller that match the predicates
2598 reCallee.getPreds().isSatisfiedBy( this,
2599 callerNodeIDsCopiedToCallee,
2602 if( !rsnCallers.isEmpty() ) {
2603 matchedOutOfContext = true;
2604 calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2608 if( hrnSrcCallee.isOutOfContext() &&
2609 !matchedOutOfContext ) {
2616 reCallee.getPreds().isSatisfiedBy(this,
2617 callerNodeIDsCopiedToCallee,
2621 if( predsIfSatis != null ) {
2622 calleeEdgesSatisfied.put(reCallee, predsIfSatis);
2624 // since the edge is coming over, find out which reach
2625 // states on it should come over, too
2626 assert calleeEdge2calleeStatesSatisfied.get(reCallee) == null;
2628 stateItr = reCallee.getBeta().iterator();
2629 while( stateItr.hasNext() ) {
2630 ReachState stateCallee = stateItr.next();
2633 stateCallee.getPreds().isSatisfiedBy(this,
2634 callerNodeIDsCopiedToCallee,
2636 if( predsIfSatis != null ) {
2638 Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2639 calleeEdge2calleeStatesSatisfied.get(reCallee);
2641 if( calleeStatesSatisfied == null ) {
2642 calleeStatesSatisfied =
2643 new Hashtable<ReachState, ExistPredSet>();
2645 calleeEdge2calleeStatesSatisfied.put(reCallee, calleeStatesSatisfied);
2648 calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2652 // since the edge is coming over, find out which taints
2653 // on it should come over, too
2654 assert calleeEdge2calleeTaintsSatisfied.get(reCallee) == null;
2656 Iterator<Taint> tItr = reCallee.getTaints().iterator();
2657 while( tItr.hasNext() ) {
2658 Taint tCallee = tItr.next();
2661 tCallee.getPreds().isSatisfiedBy(this,
2662 callerNodeIDsCopiedToCallee,
2664 if( predsIfSatis != null ) {
2666 Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2667 calleeEdge2calleeTaintsSatisfied.get(reCallee);
2669 if( calleeTaintsSatisfied == null ) {
2670 calleeTaintsSatisfied =
2671 new Hashtable<Taint, ExistPredSet>();
2673 calleeEdge2calleeTaintsSatisfied.put(reCallee, calleeTaintsSatisfied);
2676 calleeTaintsSatisfied.put(tCallee, predsIfSatis);
2683 if( writeDebugDOTs ) {
2684 writeGraph(debugGraphPrefix+"caller20BeforeWipe",
2685 resolveMethodDebugDOTwriteLabels,
2686 resolveMethodDebugDOTselectTemps,
2687 resolveMethodDebugDOTpruneGarbage,
2688 resolveMethodDebugDOThideReach,
2689 resolveMethodDebugDOThideSubsetReach,
2690 resolveMethodDebugDOThidePreds,
2691 resolveMethodDebugDOThideEdgeTaints);
2695 // 2. predicates tested, ok to wipe out caller part
2696 Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2697 while( hrnItr.hasNext() ) {
2698 Integer hrnID = hrnItr.next();
2699 HeapRegionNode hrnCaller = id2hrn.get(hrnID);
2700 assert hrnCaller != null;
2702 // when clearing off nodes, also eliminate variable
2704 wipeOut(hrnCaller, true);
2707 // if we are assigning the return value to something, clobber now
2708 // as part of the wipe
2709 TempDescriptor returnTemp = fc.getReturnTemp();
2710 if( returnTemp != null &&
2711 DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2714 VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2715 clearRefEdgesFrom(vnLhsCaller, null, null, true);
2721 if( writeDebugDOTs ) {
2722 writeGraph(debugGraphPrefix+"caller30BeforeAddingNodes",
2723 resolveMethodDebugDOTwriteLabels,
2724 resolveMethodDebugDOTselectTemps,
2725 resolveMethodDebugDOTpruneGarbage,
2726 resolveMethodDebugDOThideReach,
2727 resolveMethodDebugDOThideSubsetReach,
2728 resolveMethodDebugDOThidePreds,
2729 resolveMethodDebugDOThideEdgeTaints);
2735 // 3. callee elements with satisfied preds come in, note that
2736 // the mapping of elements satisfied to preds is like this:
2737 // A callee element EE has preds EEp that are satisfied by
2738 // some caller element ER. We bring EE into the caller
2739 // context as ERee with the preds of ER, namely ERp, which
2740 // in the following algorithm is the value in the mapping
2743 Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2744 while( satisItr.hasNext() ) {
2745 Map.Entry me = (Map.Entry)satisItr.next();
2746 HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2747 ExistPredSet preds = (ExistPredSet) me.getValue();
2749 // TODO: I think its true that the current implementation uses
2750 // the type of the OOC region and the predicates OF THE EDGE from
2751 // it to link everything up in caller context, so that's why we're
2752 // skipping this... maybe that's a sillier way to do it?
2753 if( hrnCallee.isOutOfContext() ) {
2757 AllocSite as = hrnCallee.getAllocSite();
2760 Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
2762 HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
2763 if( hrnCaller == null ) {
2765 createNewHeapRegionNode(hrnIDshadow, // id or null to generate a new one
2766 hrnCallee.isSingleObject(), // single object?
2767 hrnCallee.isNewSummary(), // summary?
2768 false, // out-of-context?
2769 hrnCallee.getType(), // type
2770 hrnCallee.getAllocSite(), // allocation site
2771 toCallerContext(hrnCallee.getInherent(),
2772 calleeNode2calleeStatesSatisfied.get(hrnCallee) ), // inherent reach
2773 null, // current reach
2774 predsEmpty, // predicates
2775 hrnCallee.getDescription() // description
2778 assert hrnCaller.isWiped();
2781 hrnCaller.setAlpha(toCallerContext(hrnCallee.getAlpha(),
2782 calleeNode2calleeStatesSatisfied.get(hrnCallee)
2786 hrnCaller.setPreds(preds);
2793 if( writeDebugDOTs ) {
2794 writeGraph(debugGraphPrefix+"caller31BeforeAddingEdges",
2795 resolveMethodDebugDOTwriteLabels,
2796 resolveMethodDebugDOTselectTemps,
2797 resolveMethodDebugDOTpruneGarbage,
2798 resolveMethodDebugDOThideReach,
2799 resolveMethodDebugDOThideSubsetReach,
2800 resolveMethodDebugDOThidePreds,
2801 resolveMethodDebugDOThideEdgeTaints);
2805 // set these up during the next procedure so after
2806 // the caller has all of its nodes and edges put
2807 // back together we can propagate the callee's
2808 // reach changes backwards into the caller graph
2809 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2811 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2812 new Hashtable<RefEdge, ChangeSet>();
2815 // 3.b) callee -> callee edges AND out-of-context -> callee
2816 // which includes return temp -> callee edges now, too
2817 satisItr = calleeEdgesSatisfied.entrySet().iterator();
2818 while( satisItr.hasNext() ) {
2819 Map.Entry me = (Map.Entry)satisItr.next();
2820 RefEdge reCallee = (RefEdge) me.getKey();
2821 ExistPredSet preds = (ExistPredSet) me.getValue();
2823 HeapRegionNode hrnDstCallee = reCallee.getDst();
2824 AllocSite asDst = hrnDstCallee.getAllocSite();
2825 allocSites.add(asDst);
2827 Integer hrnIDDstShadow =
2828 asDst.getShadowIDfromID(hrnDstCallee.getID() );
2830 HeapRegionNode hrnDstCaller = id2hrn.get(hrnIDDstShadow);
2831 assert hrnDstCaller != null;
2834 RefSrcNode rsnCallee = reCallee.getSrc();
2836 Set<RefSrcNode> rsnCallers =
2837 new HashSet<RefSrcNode>();
2839 Set<RefSrcNode> oocCallers =
2840 calleeEdges2oocCallerSrcMatches.get(reCallee);
2842 if( rsnCallee instanceof HeapRegionNode ) {
2843 HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2844 if( hrnCalleeSrc.isOutOfContext() ) {
2845 assert oocCallers != null;
2850 if( oocCallers == null ) {
2851 // there are no out-of-context matches, so it's
2852 // either a param/arg var or one in-context heap region
2853 if( rsnCallee instanceof VariableNode ) {
2854 // variable -> node in the callee should only
2855 // come into the caller if its from a param var
2856 VariableNode vnCallee = (VariableNode) rsnCallee;
2857 TempDescriptor tdParam = vnCallee.getTempDescriptor();
2858 TempDescriptor tdArg = fc.getArgMatchingParam(fmCallee,
2860 if( tdArg == null ) {
2861 // this means the variable isn't a parameter, its local
2862 // to the callee so we ignore it in call site transfer
2863 // shouldn't this NEVER HAPPEN?
2867 rsnCallers.add(this.getVariableNodeFromTemp(tdArg) );
2870 // otherwise source is in context, one region
2872 HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2874 // translate an in-context node to shadow
2875 AllocSite asSrc = hrnSrcCallee.getAllocSite();
2876 allocSites.add(asSrc);
2878 Integer hrnIDSrcShadow =
2879 asSrc.getShadowIDfromID(hrnSrcCallee.getID() );
2881 HeapRegionNode hrnSrcCallerShadow =
2882 this.id2hrn.get(hrnIDSrcShadow);
2884 assert hrnSrcCallerShadow != null;
2886 rsnCallers.add(hrnSrcCallerShadow);
2890 // otherwise we have a set of out-of-context srcs
2891 // that should NOT be translated to shadow nodes
2892 assert !oocCallers.isEmpty();
2893 rsnCallers.addAll(oocCallers);
2896 // now make all caller edges we've identified from
2897 // this callee edge with a satisfied predicate
2898 assert !rsnCallers.isEmpty();
2899 Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2900 while( rsnItr.hasNext() ) {
2901 RefSrcNode rsnCaller = rsnItr.next();
2903 RefEdge reCaller = new RefEdge(rsnCaller,
2906 reCallee.getField(),
2907 toCallerContext(reCallee.getBeta(),
2908 calleeEdge2calleeStatesSatisfied.get(reCallee) ),
2910 toCallerContext(reCallee.getTaints(),
2911 calleeEdge2calleeTaintsSatisfied.get(reCallee) )
2914 ChangeSet cs = ChangeSet.factory();
2915 Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2916 while( rsItr.hasNext() ) {
2917 ReachState state = rsItr.next();
2918 ExistPredSet predsPreCallee = state.getPreds();
2920 if( state.isEmpty() ) {
2924 Iterator<ExistPred> predItr = predsPreCallee.iterator();
2925 while( predItr.hasNext() ) {
2926 ExistPred pred = predItr.next();
2927 ReachState old = pred.ne_state;
2933 cs = Canonical.add(cs,
2934 ChangeTuple.factory(old,
2941 // we're just going to use the convenient "merge-if-exists"
2942 // edge call below, but still take a separate look if there
2943 // is an existing caller edge to build change sets properly
2944 if( !cs.isEmpty() ) {
2945 RefEdge edgeExisting = rsnCaller.getReferenceTo(hrnDstCaller,
2949 if( edgeExisting != null ) {
2950 ChangeSet csExisting = edgePlannedChanges.get(edgeExisting);
2951 if( csExisting == null ) {
2952 csExisting = ChangeSet.factory();
2954 edgePlannedChanges.put(edgeExisting,
2955 Canonical.union(csExisting,
2960 edgesForPropagation.add(reCaller);
2961 assert !edgePlannedChanges.containsKey(reCaller);
2962 edgePlannedChanges.put(reCaller, cs);
2966 // then add new caller edge or merge
2967 addEdgeOrMergeWithExisting(reCaller);
2975 if( writeDebugDOTs ) {
2976 writeGraph(debugGraphPrefix+"caller38propagateReach",
2977 resolveMethodDebugDOTwriteLabels,
2978 resolveMethodDebugDOTselectTemps,
2979 resolveMethodDebugDOTpruneGarbage,
2980 resolveMethodDebugDOThideReach,
2981 resolveMethodDebugDOThideSubsetReach,
2982 resolveMethodDebugDOThidePreds,
2983 resolveMethodDebugDOThideEdgeTaints);
2986 // propagate callee reachability changes to the rest
2987 // of the caller graph edges
2988 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2990 propagateTokensOverEdges( edgesForPropagation, // source edges
2991 edgePlannedChanges, // map src edge to change set
2992 edgesUpdated, // list of updated edges
2995 // commit beta' (beta<-betaNew)
2996 Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2997 while( edgeItr.hasNext() ) {
2998 edgeItr.next().applyBetaNew();
3007 if( writeDebugDOTs ) {
3008 writeGraph(debugGraphPrefix+"caller40BeforeShadowMerge",
3009 resolveMethodDebugDOTwriteLabels,
3010 resolveMethodDebugDOTselectTemps,
3011 resolveMethodDebugDOTpruneGarbage,
3012 resolveMethodDebugDOThideReach,
3013 resolveMethodDebugDOThideSubsetReach,
3014 resolveMethodDebugDOThidePreds,
3015 resolveMethodDebugDOThideEdgeTaints);
3019 // 4) merge shadow nodes so alloc sites are back to k
3020 Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
3021 while( asItr.hasNext() ) {
3022 // for each allocation site do the following to merge
3023 // shadow nodes (newest from callee) with any existing
3024 // look for the newest normal and newest shadow "slot"
3025 // not being used, transfer normal to shadow. Keep
3026 // doing this until there are no more normal nodes, or
3027 // no empty shadow slots: then merge all remaining normal
3028 // nodes into the shadow summary. Finally, convert all
3029 // shadow to their normal versions.
3030 AllocSite as = asItr.next();
3034 while( ageNorm < allocationDepth &&
3035 ageShad < allocationDepth ) {
3037 // first, are there any normal nodes left?
3038 Integer idNorm = as.getIthOldest(ageNorm);
3039 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
3040 if( hrnNorm == null ) {
3041 // no, this age of normal node not in the caller graph
3046 // yes, a normal node exists, is there an empty shadow
3047 // "slot" to transfer it onto?
3048 HeapRegionNode hrnShad = getIthNode(as, ageShad, true);
3049 if( !hrnShad.isWiped() ) {
3050 // no, this age of shadow node is not empty
3055 // yes, this shadow node is empty
3056 transferOnto(hrnNorm, hrnShad);
3061 // now, while there are still normal nodes but no shadow
3062 // slots, merge normal nodes into the shadow summary
3063 while( ageNorm < allocationDepth ) {
3065 // first, are there any normal nodes left?
3066 Integer idNorm = as.getIthOldest(ageNorm);
3067 HeapRegionNode hrnNorm = id2hrn.get(idNorm);
3068 if( hrnNorm == null ) {
3069 // no, this age of normal node not in the caller graph
3074 // yes, a normal node exists, so get the shadow summary
3075 HeapRegionNode summShad = getSummaryNode(as, true);
3076 mergeIntoSummary(hrnNorm, summShad);
3078 // now tokens in reachability sets need to age also
3079 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3080 while( itrAllHRNodes.hasNext() ) {
3081 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
3082 HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
3084 ageTuplesFrom(as, hrnToAge);
3086 Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
3087 while( itrEdges.hasNext() ) {
3088 ageTuplesFrom(as, itrEdges.next() );
3095 // if there is a normal summary, merge it into shadow summary
3096 Integer idNorm = as.getSummary();
3097 HeapRegionNode summNorm = id2hrn.get(idNorm);
3098 if( summNorm != null ) {
3099 HeapRegionNode summShad = getSummaryNode(as, true);
3100 mergeIntoSummary(summNorm, summShad);
3103 // finally, flip all existing shadow nodes onto the normal
3104 for( int i = 0; i < allocationDepth; ++i ) {
3105 Integer idShad = as.getIthOldestShadow(i);
3106 HeapRegionNode hrnShad = id2hrn.get(idShad);
3107 if( hrnShad != null ) {
3109 HeapRegionNode hrnNorm = getIthNode(as, i, false);
3110 assert hrnNorm.isWiped();
3111 transferOnto(hrnShad, hrnNorm);
3115 Integer idShad = as.getSummaryShadow();
3116 HeapRegionNode summShad = id2hrn.get(idShad);
3117 if( summShad != null ) {
3118 summNorm = getSummaryNode(as, false);
3119 transferOnto(summShad, summNorm);
3128 if( writeDebugDOTs ) {
3129 writeGraph(debugGraphPrefix+"caller45BeforeUnshadow",
3130 resolveMethodDebugDOTwriteLabels,
3131 resolveMethodDebugDOTselectTemps,
3132 resolveMethodDebugDOTpruneGarbage,
3133 resolveMethodDebugDOThideReach,
3134 resolveMethodDebugDOThideSubsetReach,
3135 resolveMethodDebugDOThidePreds,
3136 resolveMethodDebugDOThideEdgeTaints);
3140 Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3141 while( itrAllHRNodes.hasNext() ) {
3142 Map.Entry me = (Map.Entry)itrAllHRNodes.next();
3143 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3145 hrn.setAlpha(unshadow(hrn.getAlpha() ) );
3147 Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
3148 while( itrEdges.hasNext() ) {
3149 RefEdge re = itrEdges.next();
3150 re.setBeta(unshadow(re.getBeta() ) );
3157 if( writeDebugDOTs ) {
3158 writeGraph(debugGraphPrefix+"caller50BeforeGlobalSweep",
3159 resolveMethodDebugDOTwriteLabels,
3160 resolveMethodDebugDOTselectTemps,
3161 resolveMethodDebugDOTpruneGarbage,
3162 resolveMethodDebugDOThideReach,
3163 resolveMethodDebugDOThideSubsetReach,
3164 resolveMethodDebugDOThidePreds,
3165 resolveMethodDebugDOThideEdgeTaints);
3170 if( !DISABLE_GLOBAL_SWEEP ) {
3175 if( writeDebugDOTs ) {
3176 writeGraph(debugGraphPrefix+"caller90AfterTransfer",
3177 resolveMethodDebugDOTwriteLabels,
3178 resolveMethodDebugDOTselectTemps,
3179 resolveMethodDebugDOTpruneGarbage,
3180 resolveMethodDebugDOThideReach,
3181 resolveMethodDebugDOThideSubsetReach,
3182 resolveMethodDebugDOThidePreds,
3183 resolveMethodDebugDOThideEdgeTaints);
3189 ////////////////////////////////////////////////////
3191 // Abstract garbage collection simply removes
3192 // heap region nodes that are not mechanically
3193 // reachable from a root set. This step is
3194 // essential for testing node and edge existence
3195 // predicates efficiently
3197 ////////////////////////////////////////////////////
3198 public void abstractGarbageCollect(Set<TempDescriptor> liveSet) {
3200 // calculate a root set, will be different for Java
3201 // version of analysis versus Bamboo version
3202 Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3204 // visit every variable in graph while building root
3205 // set, and do iterating on a copy, so we can remove
3206 // dead variables while we're at this
3207 Iterator makeCopyItr = td2vn.entrySet().iterator();
3208 Set entrysCopy = new HashSet();
3209 while( makeCopyItr.hasNext() ) {
3210 entrysCopy.add(makeCopyItr.next() );
3213 Iterator eItr = entrysCopy.iterator();
3214 while( eItr.hasNext() ) {
3215 Map.Entry me = (Map.Entry)eItr.next();
3216 TempDescriptor td = (TempDescriptor) me.getKey();
3217 VariableNode vn = (VariableNode) me.getValue();
3219 if( liveSet.contains(td) ) {
3223 // dead var, remove completely from graph
3225 clearRefEdgesFrom(vn, null, null, true);
3229 // everything visited in a traversal is
3230 // considered abstractly live
3231 Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3233 while( !toVisit.isEmpty() ) {
3234 RefSrcNode rsn = toVisit.iterator().next();
3235 toVisit.remove(rsn);
3238 Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3239 while( hrnItr.hasNext() ) {
3240 RefEdge edge = hrnItr.next();
3241 HeapRegionNode hrn = edge.getDst();
3243 if( !visited.contains(hrn) ) {
3249 // get a copy of the set to iterate over because
3250 // we're going to monkey with the graph when we
3251 // identify a garbage node
3252 Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3253 Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3254 while( hrnItr.hasNext() ) {
3255 hrnAllPrior.add(hrnItr.next() );
3258 Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3259 while( hrnAllItr.hasNext() ) {
3260 HeapRegionNode hrn = hrnAllItr.next();
3262 if( !visited.contains(hrn) ) {
3264 // heap region nodes are compared across ReachGraph
3265 // objects by their integer ID, so when discarding
3266 // garbage nodes we must also discard entries in
3267 // the ID -> heap region hashtable.
3268 id2hrn.remove(hrn.getID() );
3270 // RefEdge objects are two-way linked between
3271 // nodes, so when a node is identified as garbage,
3272 // actively clear references to and from it so
3273 // live nodes won't have dangling RefEdge's
3276 // if we just removed the last node from an allocation
3277 // site, it should be taken out of the ReachGraph's list
3278 AllocSite as = hrn.getAllocSite();
3279 if( !hasNodesOf(as) ) {
3280 allocSites.remove(as);
3286 protected boolean hasNodesOf(AllocSite as) {
3287 if( id2hrn.containsKey(as.getSummary() ) ) {
3291 for( int i = 0; i < allocationDepth; ++i ) {
3292 if( id2hrn.containsKey(as.getIthOldest(i) ) ) {
3300 ////////////////////////////////////////////////////
3302 // This global sweep is an optional step to prune
3303 // reachability sets that are not internally
3304 // consistent with the global graph. It should be
3305 // invoked after strong updates or method calls.
3307 ////////////////////////////////////////////////////
3308 public void globalSweep() {
3310 // boldB is part of the phase 1 sweep
3311 // it has an in-context table and an out-of-context table
3312 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3313 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3315 Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3316 new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3318 // visit every heap region to initialize alphaNew and betaNew,
3319 // and make a map of every hrnID to the source nodes it should
3320 // propagate forward from. In-context flagged hrnID's propagate
3321 // from only the in-context node they name, but out-of-context
3322 // ID's may propagate from several out-of-context nodes
3323 Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3324 new Hashtable< Integer, Set<HeapRegionNode> >();
3326 Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3327 new Hashtable< Integer, Set<HeapRegionNode> >();
3330 Iterator itrHrns = id2hrn.entrySet().iterator();
3331 while( itrHrns.hasNext() ) {
3332 Map.Entry me = (Map.Entry)itrHrns.next();
3333 Integer hrnID = (Integer) me.getKey();
3334 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3336 // assert that this node and incoming edges have clean alphaNew
3337 // and betaNew sets, respectively
3338 assert rsetEmpty.equals(hrn.getAlphaNew() );
3340 Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3341 while( itrRers.hasNext() ) {
3342 RefEdge edge = itrRers.next();
3343 assert rsetEmpty.equals(edge.getBetaNew() );
3346 // make a mapping of IDs to heap regions they propagate from
3347 if( hrn.isFlagged() ) {
3348 assert !hrn.isOutOfContext();
3349 assert !icID2srcs.containsKey(hrn.getID() );
3351 // in-context flagged node IDs simply propagate from the
3353 Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3355 icID2srcs.put(hrn.getID(), srcs);
3358 if( hrn.isOutOfContext() ) {
3359 assert !hrn.isFlagged();
3361 // the reachability states on an out-of-context
3362 // node are not really important (combinations of
3363 // IDs or arity)--what matters is that the states
3364 // specify which nodes this out-of-context node
3365 // stands in for. For example, if the state [17?, 19*]
3366 // appears on the ooc node, it may serve as a source
3367 // for node 17? and a source for node 19.
3368 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3369 while( stateItr.hasNext() ) {
3370 ReachState state = stateItr.next();
3372 Iterator<ReachTuple> rtItr = state.iterator();
3373 while( rtItr.hasNext() ) {
3374 ReachTuple rt = rtItr.next();
3375 assert rt.isOutOfContext();
3377 Set<HeapRegionNode> srcs = oocID2srcs.get(rt.getHrnID() );
3378 if( srcs == null ) {
3379 srcs = new HashSet<HeapRegionNode>();
3382 oocID2srcs.put(rt.getHrnID(), srcs);
3388 // calculate boldB for all hrnIDs identified by the above
3389 // node traversal, propagating from every source
3390 while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3393 Set<HeapRegionNode> srcs;
3396 if( !icID2srcs.isEmpty() ) {
3397 Map.Entry me = (Map.Entry)icID2srcs.entrySet().iterator().next();
3398 hrnID = (Integer) me.getKey();
3399 srcs = (Set<HeapRegionNode>)me.getValue();
3401 icID2srcs.remove(hrnID);
3404 assert !oocID2srcs.isEmpty();
3406 Map.Entry me = (Map.Entry)oocID2srcs.entrySet().iterator().next();
3407 hrnID = (Integer) me.getKey();
3408 srcs = (Set<HeapRegionNode>)me.getValue();
3410 oocID2srcs.remove(hrnID);
3414 Hashtable<RefEdge, ReachSet> boldB_f =
3415 new Hashtable<RefEdge, ReachSet>();
3417 Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3419 Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3420 while( hrnItr.hasNext() ) {
3421 HeapRegionNode hrn = hrnItr.next();
3423 assert workSetEdges.isEmpty();
3425 // initial boldB_f constraints
3426 Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3427 while( itrRees.hasNext() ) {
3428 RefEdge edge = itrRees.next();
3430 assert !boldB_f.containsKey(edge);
3431 boldB_f.put(edge, edge.getBeta() );
3433 assert !workSetEdges.contains(edge);
3434 workSetEdges.add(edge);
3437 // enforce the boldB_f constraint at edges until we reach a fixed point
3438 while( !workSetEdges.isEmpty() ) {
3439 RefEdge edge = workSetEdges.iterator().next();
3440 workSetEdges.remove(edge);
3442 Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3443 while( itrPrime.hasNext() ) {
3444 RefEdge edgePrime = itrPrime.next();
3446 ReachSet prevResult = boldB_f.get(edgePrime);
3447 ReachSet intersection = Canonical.intersection(boldB_f.get(edge),
3451 if( prevResult == null ||
3452 Canonical.unionORpreds(prevResult,
3453 intersection).size()
3457 if( prevResult == null ) {
3458 boldB_f.put(edgePrime,
3459 Canonical.unionORpreds(edgePrime.getBeta(),
3464 boldB_f.put(edgePrime,
3465 Canonical.unionORpreds(prevResult,
3470 workSetEdges.add(edgePrime);
3477 boldBic.put(hrnID, boldB_f);
3479 boldBooc.put(hrnID, boldB_f);
3484 // use boldB to prune hrnIDs from alpha states that are impossible
3485 // and propagate the differences backwards across edges
3486 HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3488 Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3489 new Hashtable<RefEdge, ChangeSet>();
3492 itrHrns = id2hrn.entrySet().iterator();
3493 while( itrHrns.hasNext() ) {
3494 Map.Entry me = (Map.Entry)itrHrns.next();
3495 Integer hrnID = (Integer) me.getKey();
3496 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3498 // out-of-context nodes don't participate in the
3499 // global sweep, they serve as sources for the pass
3501 if( hrn.isOutOfContext() ) {
3505 // the inherent states of a region are the exception
3506 // to removal as the global sweep prunes
3507 ReachTuple rtException = ReachTuple.factory(hrnID,
3508 !hrn.isSingleObject(),
3509 ReachTuple.ARITY_ONE,
3510 false // out-of-context
3513 ChangeSet cts = ChangeSet.factory();
3515 // mark hrnIDs for removal
3516 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3517 while( stateItr.hasNext() ) {
3518 ReachState stateOld = stateItr.next();
3520 ReachState markedHrnIDs = ReachState.factory();
3522 Iterator<ReachTuple> rtItr = stateOld.iterator();
3523 while( rtItr.hasNext() ) {
3524 ReachTuple rtOld = rtItr.next();
3526 // never remove the inherent hrnID from a flagged region
3527 // because it is trivially satisfied
3528 if( hrn.isFlagged() ) {
3529 if( rtOld == rtException ) {
3534 // does boldB allow this hrnID?
3535 boolean foundState = false;
3536 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3537 while( incidentEdgeItr.hasNext() ) {
3538 RefEdge incidentEdge = incidentEdgeItr.next();
3540 Hashtable<RefEdge, ReachSet> B;
3541 if( rtOld.isOutOfContext() ) {
3542 B = boldBooc.get(rtOld.getHrnID() );
3545 if( !id2hrn.containsKey(rtOld.getHrnID() ) ) {
3546 // let symbols not in the graph get pruned
3550 B = boldBic.get(rtOld.getHrnID() );
3554 ReachSet boldB_rtOld_incident = B.get(incidentEdge);
3555 if( boldB_rtOld_incident != null &&
3556 boldB_rtOld_incident.containsIgnorePreds(stateOld) != null
3564 markedHrnIDs = Canonical.addUpArity(markedHrnIDs, rtOld);
3568 // if there is nothing marked, just move on
3569 if( markedHrnIDs.isEmpty() ) {
3570 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3577 // remove all marked hrnIDs and establish a change set that should
3578 // propagate backwards over edges from this node
3579 ReachState statePruned = ReachState.factory();
3580 rtItr = stateOld.iterator();
3581 while( rtItr.hasNext() ) {
3582 ReachTuple rtOld = rtItr.next();
3584 if( !markedHrnIDs.containsTuple(rtOld) ) {
3585 statePruned = Canonical.addUpArity(statePruned, rtOld);
3588 assert !stateOld.equals(statePruned);
3590 hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3594 ChangeTuple ct = ChangeTuple.factory(stateOld,
3597 cts = Canonical.add(cts, ct);
3600 // throw change tuple set on all incident edges
3601 if( !cts.isEmpty() ) {
3602 Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3603 while( incidentEdgeItr.hasNext() ) {
3604 RefEdge incidentEdge = incidentEdgeItr.next();
3606 edgesForPropagation.add(incidentEdge);
3608 if( edgePlannedChanges.get(incidentEdge) == null ) {
3609 edgePlannedChanges.put(incidentEdge, cts);
3611 edgePlannedChanges.put(
3613 Canonical.union(edgePlannedChanges.get(incidentEdge),
3622 HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3624 propagateTokensOverEdges(edgesForPropagation,
3629 // at the end of the 1st phase reference edges have
3630 // beta, betaNew that correspond to beta and betaR
3632 // commit beta<-betaNew, so beta=betaR and betaNew
3633 // will represent the beta' calculation in 2nd phase
3635 // commit alpha<-alphaNew because it won't change
3636 HashSet<RefEdge> res = new HashSet<RefEdge>();
3638 Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3639 while( nodeItr.hasNext() ) {
3640 HeapRegionNode hrn = nodeItr.next();
3642 // as mentioned above, out-of-context nodes only serve
3643 // as sources of reach states for the sweep, not part
3645 if( hrn.isOutOfContext() ) {
3646 assert hrn.getAlphaNew().equals(rsetEmpty);
3648 hrn.applyAlphaNew();
3651 Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3652 while( itrRes.hasNext() ) {
3653 res.add(itrRes.next() );
3659 Iterator<RefEdge> edgeItr = res.iterator();
3660 while( edgeItr.hasNext() ) {
3661 RefEdge edge = edgeItr.next();
3662 HeapRegionNode hrn = edge.getDst();
3664 // commit results of last phase
3665 if( edgesUpdated.contains(edge) ) {
3666 edge.applyBetaNew();
3669 // compute intial condition of 2nd phase
3670 edge.setBetaNew(Canonical.intersection(edge.getBeta(),
3676 // every edge in the graph is the initial workset
3677 Set<RefEdge> edgeWorkSet = (Set) res.clone();
3678 while( !edgeWorkSet.isEmpty() ) {
3679 RefEdge edgePrime = edgeWorkSet.iterator().next();
3680 edgeWorkSet.remove(edgePrime);
3682 RefSrcNode rsn = edgePrime.getSrc();
3683 if( !(rsn instanceof HeapRegionNode) ) {
3686 HeapRegionNode hrn = (HeapRegionNode) rsn;
3688 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3689 while( itrEdge.hasNext() ) {
3690 RefEdge edge = itrEdge.next();
3692 ReachSet prevResult = edge.getBetaNew();
3693 assert prevResult != null;
3695 ReachSet intersection =
3696 Canonical.intersection(edge.getBeta(),
3697 edgePrime.getBetaNew()
3700 if( Canonical.unionORpreds(prevResult,
3707 Canonical.unionORpreds(prevResult,
3711 edgeWorkSet.add(edge);
3716 // commit beta' (beta<-betaNew)
3717 edgeItr = res.iterator();
3718 while( edgeItr.hasNext() ) {
3719 edgeItr.next().applyBetaNew();
3724 // a useful assertion for debugging:
3725 // every in-context tuple on any edge or
3726 // any node should name a node that is
3727 // part of the graph
3728 public boolean inContextTuplesInGraph() {
3730 Iterator hrnItr = id2hrn.entrySet().iterator();
3731 while( hrnItr.hasNext() ) {
3732 Map.Entry me = (Map.Entry)hrnItr.next();
3733 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3736 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3737 while( stateItr.hasNext() ) {
3738 ReachState state = stateItr.next();
3740 Iterator<ReachTuple> rtItr = state.iterator();
3741 while( rtItr.hasNext() ) {
3742 ReachTuple rt = rtItr.next();
3744 if( !rt.isOutOfContext() ) {
3745 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3746 System.out.println(rt.getHrnID()+" is missing");
3754 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3755 while( edgeItr.hasNext() ) {
3756 RefEdge edge = edgeItr.next();
3758 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3759 while( stateItr.hasNext() ) {
3760 ReachState state = stateItr.next();
3762 Iterator<ReachTuple> rtItr = state.iterator();
3763 while( rtItr.hasNext() ) {
3764 ReachTuple rt = rtItr.next();
3766 if( !rt.isOutOfContext() ) {
3767 if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3768 System.out.println(rt.getHrnID()+" is missing");
3781 // another useful assertion for debugging
3782 public boolean noEmptyReachSetsInGraph() {
3784 Iterator hrnItr = id2hrn.entrySet().iterator();
3785 while( hrnItr.hasNext() ) {
3786 Map.Entry me = (Map.Entry)hrnItr.next();
3787 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3789 if( !hrn.isOutOfContext() &&
3791 hrn.getAlpha().isEmpty()
3793 System.out.println("!!! "+hrn+" has an empty ReachSet !!!");
3797 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3798 while( edgeItr.hasNext() ) {
3799 RefEdge edge = edgeItr.next();
3801 if( edge.getBeta().isEmpty() ) {
3802 System.out.println("!!! "+edge+" has an empty ReachSet !!!");
3812 public boolean everyReachStateWTrue() {
3814 Iterator hrnItr = id2hrn.entrySet().iterator();
3815 while( hrnItr.hasNext() ) {
3816 Map.Entry me = (Map.Entry)hrnItr.next();
3817 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3820 Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3821 while( stateItr.hasNext() ) {
3822 ReachState state = stateItr.next();
3824 if( !state.getPreds().equals(predsTrue) ) {
3830 Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3831 while( edgeItr.hasNext() ) {
3832 RefEdge edge = edgeItr.next();
3834 Iterator<ReachState> stateItr = edge.getBeta().iterator();
3835 while( stateItr.hasNext() ) {
3836 ReachState state = stateItr.next();
3838 if( !state.getPreds().equals(predsTrue) ) {
3851 ////////////////////////////////////////////////////
3852 // in merge() and equals() methods the suffix A
3853 // represents the passed in graph and the suffix
3854 // B refers to the graph in this object
3855 // Merging means to take the incoming graph A and
3856 // merge it into B, so after the operation graph B
3857 // is the final result.
3858 ////////////////////////////////////////////////////
3859 protected void merge(ReachGraph rg) {
3867 mergeAllocSites(rg);
3868 mergeInaccessibleVars(rg);
3871 protected void mergeNodes(ReachGraph rg) {
3873 // start with heap region nodes
3874 Set sA = rg.id2hrn.entrySet();
3875 Iterator iA = sA.iterator();
3876 while( iA.hasNext() ) {
3877 Map.Entry meA = (Map.Entry)iA.next();
3878 Integer idA = (Integer) meA.getKey();
3879 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3881 // if this graph doesn't have a node the
3882 // incoming graph has, allocate it
3883 if( !id2hrn.containsKey(idA) ) {
3884 HeapRegionNode hrnB = hrnA.copy();
3885 id2hrn.put(idA, hrnB);
3888 // otherwise this is a node present in both graphs
3889 // so make the new reachability set a union of the
3890 // nodes' reachability sets
3891 HeapRegionNode hrnB = id2hrn.get(idA);
3892 hrnB.setAlpha(Canonical.unionORpreds(hrnB.getAlpha(),
3897 hrnB.setPreds(Canonical.join(hrnB.getPreds(),
3904 if( !hrnA.equals(hrnB) ) {
3905 rg.writeGraph("graphA");
3906 this.writeGraph("graphB");
3907 throw new Error("flagged not matching");
3915 // now add any variable nodes that are in graph B but
3917 sA = rg.td2vn.entrySet();
3919 while( iA.hasNext() ) {
3920 Map.Entry meA = (Map.Entry)iA.next();
3921 TempDescriptor tdA = (TempDescriptor) meA.getKey();
3922 VariableNode lnA = (VariableNode) meA.getValue();
3924 // if the variable doesn't exist in B, allocate and add it
3925 VariableNode lnB = getVariableNodeFromTemp(tdA);
3929 protected void mergeRefEdges(ReachGraph rg) {
3931 // between heap regions
3932 Set sA = rg.id2hrn.entrySet();
3933 Iterator iA = sA.iterator();
3934 while( iA.hasNext() ) {
3935 Map.Entry meA = (Map.Entry)iA.next();
3936 Integer idA = (Integer) meA.getKey();
3937 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3939 Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3940 while( heapRegionsItrA.hasNext() ) {
3941 RefEdge edgeA = heapRegionsItrA.next();
3942 HeapRegionNode hrnChildA = edgeA.getDst();
3943 Integer idChildA = hrnChildA.getID();
3945 // at this point we know an edge in graph A exists
3946 // idA -> idChildA, does this exist in B?
3947 assert id2hrn.containsKey(idA);
3948 HeapRegionNode hrnB = id2hrn.get(idA);
3949 RefEdge edgeToMerge = null;
3951 Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3952 while( heapRegionsItrB.hasNext() &&
3953 edgeToMerge == null ) {
3955 RefEdge edgeB = heapRegionsItrB.next();
3956 HeapRegionNode hrnChildB = edgeB.getDst();
3957 Integer idChildB = hrnChildB.getID();
3959 // don't use the RefEdge.equals() here because
3960 // we're talking about existence between graphs,
3961 // not intragraph equal
3962 if( idChildB.equals(idChildA) &&
3963 edgeB.typeAndFieldEquals(edgeA) ) {
3965 edgeToMerge = edgeB;
3969 // if the edge from A was not found in B,
3971 if( edgeToMerge == null ) {
3972 assert id2hrn.containsKey(idChildA);
3973 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3974 edgeToMerge = edgeA.copy();
3975 edgeToMerge.setSrc(hrnB);
3976 edgeToMerge.setDst(hrnChildB);
3977 addRefEdge(hrnB, hrnChildB, edgeToMerge);
3979 // otherwise, the edge already existed in both graphs
3980 // so merge their reachability sets
3982 // just replace this beta set with the union
3983 assert edgeToMerge != null;
3984 edgeToMerge.setBeta(
3985 Canonical.unionORpreds(edgeToMerge.getBeta(),
3989 edgeToMerge.setPreds(
3990 Canonical.join(edgeToMerge.getPreds(),
3994 edgeToMerge.setTaints(
3995 Canonical.union(edgeToMerge.getTaints(),
4003 // and then again from variable nodes
4004 sA = rg.td2vn.entrySet();
4006 while( iA.hasNext() ) {
4007 Map.Entry meA = (Map.Entry)iA.next();
4008 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4009 VariableNode vnA = (VariableNode) meA.getValue();
4011 Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
4012 while( heapRegionsItrA.hasNext() ) {
4013 RefEdge edgeA = heapRegionsItrA.next();
4014 HeapRegionNode hrnChildA = edgeA.getDst();
4015 Integer idChildA = hrnChildA.getID();
4017 // at this point we know an edge in graph A exists
4018 // tdA -> idChildA, does this exist in B?
4019 assert td2vn.containsKey(tdA);
4020 VariableNode vnB = td2vn.get(tdA);
4021 RefEdge edgeToMerge = null;
4023 Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
4024 while( heapRegionsItrB.hasNext() &&
4025 edgeToMerge == null ) {
4027 RefEdge edgeB = heapRegionsItrB.next();
4028 HeapRegionNode hrnChildB = edgeB.getDst();
4029 Integer idChildB = hrnChildB.getID();
4031 // don't use the RefEdge.equals() here because
4032 // we're talking about existence between graphs
4033 if( idChildB.equals(idChildA) &&
4034 edgeB.typeAndFieldEquals(edgeA) ) {
4036 edgeToMerge = edgeB;
4040 // if the edge from A was not found in B,
4042 if( edgeToMerge == null ) {
4043 assert id2hrn.containsKey(idChildA);
4044 HeapRegionNode hrnChildB = id2hrn.get(idChildA);
4045 edgeToMerge = edgeA.copy();
4046 edgeToMerge.setSrc(vnB);
4047 edgeToMerge.setDst(hrnChildB);
4048 addRefEdge(vnB, hrnChildB, edgeToMerge);
4050 // otherwise, the edge already existed in both graphs
4051 // so merge their reachability sets
4053 // just replace this beta set with the union
4054 edgeToMerge.setBeta(Canonical.unionORpreds(edgeToMerge.getBeta(),
4058 edgeToMerge.setPreds(Canonical.join(edgeToMerge.getPreds(),
4062 edgeToMerge.setTaints(
4063 Canonical.union(edgeToMerge.getTaints(),
4072 protected void mergeAllocSites(ReachGraph rg) {
4073 allocSites.addAll(rg.allocSites);
4076 protected void mergeInaccessibleVars(ReachGraph rg) {
4077 inaccessibleVars.addAll(rg.inaccessibleVars);
4082 static public boolean dbgEquals = false;
4085 // it is necessary in the equals() member functions
4086 // to "check both ways" when comparing the data
4087 // structures of two graphs. For instance, if all
4088 // edges between heap region nodes in graph A are
4089 // present and equal in graph B it is not sufficient
4090 // to say the graphs are equal. Consider that there
4091 // may be edges in graph B that are not in graph A.
4092 // the only way to know that all edges in both graphs
4093 // are equally present is to iterate over both data
4094 // structures and compare against the other graph.
4095 public boolean equals(ReachGraph rg) {
4099 System.out.println("rg is null");
4104 if( !areHeapRegionNodesEqual(rg) ) {
4106 System.out.println("hrn not equal");
4111 if( !areVariableNodesEqual(rg) ) {
4113 System.out.println("vars not equal");
4118 if( !areRefEdgesEqual(rg) ) {
4120 System.out.println("edges not equal");
4125 if( !inaccessibleVars.equals(rg.inaccessibleVars) ) {
4129 // if everything is equal up to this point,
4130 // assert that allocSites is also equal--
4131 // this data is redundant but kept for efficiency
4132 assert allocSites.equals(rg.allocSites);
4138 protected boolean areHeapRegionNodesEqual(ReachGraph rg) {
4140 if( !areallHRNinAalsoinBandequal(this, rg) ) {
4144 if( !areallHRNinAalsoinBandequal(rg, this) ) {
4151 static protected boolean areallHRNinAalsoinBandequal(ReachGraph rgA,
4153 Set sA = rgA.id2hrn.entrySet();
4154 Iterator iA = sA.iterator();
4155 while( iA.hasNext() ) {
4156 Map.Entry meA = (Map.Entry)iA.next();
4157 Integer idA = (Integer) meA.getKey();
4158 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4160 if( !rgB.id2hrn.containsKey(idA) ) {
4164 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4165 if( !hrnA.equalsIncludingAlphaAndPreds(hrnB) ) {
4173 protected boolean areVariableNodesEqual(ReachGraph rg) {
4175 if( !areallVNinAalsoinBandequal(this, rg) ) {
4179 if( !areallVNinAalsoinBandequal(rg, this) ) {
4186 static protected boolean areallVNinAalsoinBandequal(ReachGraph rgA,
4188 Set sA = rgA.td2vn.entrySet();
4189 Iterator iA = sA.iterator();
4190 while( iA.hasNext() ) {
4191 Map.Entry meA = (Map.Entry)iA.next();
4192 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4194 if( !rgB.td2vn.containsKey(tdA) ) {
4203 protected boolean areRefEdgesEqual(ReachGraph rg) {
4204 if( !areallREinAandBequal(this, rg) ) {
4208 if( !areallREinAandBequal(rg, this) ) {
4215 static protected boolean areallREinAandBequal(ReachGraph rgA,
4218 // check all the heap region->heap region edges
4219 Set sA = rgA.id2hrn.entrySet();
4220 Iterator iA = sA.iterator();
4221 while( iA.hasNext() ) {
4222 Map.Entry meA = (Map.Entry)iA.next();
4223 Integer idA = (Integer) meA.getKey();
4224 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4226 // we should have already checked that the same
4227 // heap regions exist in both graphs
4228 assert rgB.id2hrn.containsKey(idA);
4230 if( !areallREfromAequaltoB(rgA, hrnA, rgB) ) {
4234 // then check every edge in B for presence in A, starting
4235 // from the same parent HeapRegionNode
4236 HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4238 if( !areallREfromAequaltoB(rgB, hrnB, rgA) ) {
4243 // then check all the variable->heap region edges
4244 sA = rgA.td2vn.entrySet();
4246 while( iA.hasNext() ) {
4247 Map.Entry meA = (Map.Entry)iA.next();
4248 TempDescriptor tdA = (TempDescriptor) meA.getKey();
4249 VariableNode vnA = (VariableNode) meA.getValue();
4251 // we should have already checked that the same
4252 // label nodes exist in both graphs
4253 assert rgB.td2vn.containsKey(tdA);
4255 if( !areallREfromAequaltoB(rgA, vnA, rgB) ) {
4259 // then check every edge in B for presence in A, starting
4260 // from the same parent VariableNode
4261 VariableNode vnB = rgB.td2vn.get(tdA);
4263 if( !areallREfromAequaltoB(rgB, vnB, rgA) ) {
4272 static protected boolean areallREfromAequaltoB(ReachGraph rgA,
4276 Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4277 while( itrA.hasNext() ) {
4278 RefEdge edgeA = itrA.next();
4279 HeapRegionNode hrnChildA = edgeA.getDst();
4280 Integer idChildA = hrnChildA.getID();
4282 assert rgB.id2hrn.containsKey(idChildA);
4284 // at this point we know an edge in graph A exists
4285 // rnA -> idChildA, does this exact edge exist in B?
4286 boolean edgeFound = false;
4288 RefSrcNode rnB = null;
4289 if( rnA instanceof HeapRegionNode ) {
4290 HeapRegionNode hrnA = (HeapRegionNode) rnA;
4291 rnB = rgB.id2hrn.get(hrnA.getID() );
4293 VariableNode vnA = (VariableNode) rnA;
4294 rnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4297 Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4298 while( itrB.hasNext() ) {
4299 RefEdge edgeB = itrB.next();
4300 HeapRegionNode hrnChildB = edgeB.getDst();
4301 Integer idChildB = hrnChildB.getID();
4303 if( idChildA.equals(idChildB) &&
4304 edgeA.typeAndFieldEquals(edgeB) ) {
4306 // there is an edge in the right place with the right field,
4307 // but do they have the same attributes?
4308 if( edgeA.equalsIncludingBetaPredsTaints( edgeB ) ) {
4323 // can be used to assert monotonicity
4324 static public boolean isNoSmallerThan(ReachGraph rgA,
4327 //System.out.println( "*** Asking if A is no smaller than B ***" );
4329 Iterator iA = rgA.id2hrn.entrySet().iterator();
4330 while( iA.hasNext() ) {
4331 Map.Entry meA = (Map.Entry)iA.next();
4332 Integer idA = (Integer) meA.getKey();
4333 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4335 if( !rgB.id2hrn.containsKey(idA) ) {
4336 System.out.println(" regions smaller");
4341 // this works just fine, no smaller than
4342 if( !areallVNinAalsoinBandequal(rgA, rgB) ) {
4343 System.out.println(" vars smaller:");
4344 System.out.println(" A:"+rgA.td2vn.keySet() );
4345 System.out.println(" B:"+rgB.td2vn.keySet() );
4350 iA = rgA.id2hrn.entrySet().iterator();
4351 while( iA.hasNext() ) {
4352 Map.Entry meA = (Map.Entry)iA.next();
4353 Integer idA = (Integer) meA.getKey();
4354 HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4356 Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4357 while( reItr.hasNext() ) {
4358 RefEdge edgeA = reItr.next();
4359 RefSrcNode rsnA = edgeA.getSrc();
4361 // we already checked that nodes were present
4362 HeapRegionNode hrnB = rgB.id2hrn.get(hrnA.getID() );
4363 assert hrnB != null;
4366 if( rsnA instanceof VariableNode ) {
4367 VariableNode vnA = (VariableNode) rsnA;
4368 rsnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4371 HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4372 rsnB = rgB.id2hrn.get(hrnSrcA.getID() );
4374 assert rsnB != null;
4376 RefEdge edgeB = rsnB.getReferenceTo(hrnB,
4380 if( edgeB == null ) {
4381 System.out.println(" edges smaller:");
4395 // this analysis no longer has the "match anything"
4396 // type which was represented by null
4397 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4398 TypeDescriptor td2) {
4402 if( td1.isNull() ) {
4405 if( td2.isNull() ) {
4408 return typeUtil.mostSpecific(td1, td2);
4411 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4413 TypeDescriptor td3) {
4415 return mostSpecificType(td1,
4416 mostSpecificType(td2, td3)
4420 protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4423 TypeDescriptor td4) {
4425 return mostSpecificType(mostSpecificType(td1, td2),
4426 mostSpecificType(td3, td4)
4430 protected boolean isSuperiorType(TypeDescriptor possibleSuper,
4431 TypeDescriptor possibleChild) {
4432 assert possibleSuper != null;
4433 assert possibleChild != null;
4435 if( possibleSuper.isNull() ||
4436 possibleChild.isNull() ) {
4440 return typeUtil.isSuperorType(possibleSuper, possibleChild);
4444 protected boolean hasMatchingField(HeapRegionNode src,
4447 TypeDescriptor tdSrc = src.getType();
4448 assert tdSrc != null;
4450 if( tdSrc.isArray() ) {
4451 TypeDescriptor td = edge.getType();
4454 TypeDescriptor tdSrcDeref = tdSrc.dereference();
4455 assert tdSrcDeref != null;
4457 if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
4461 return edge.getField().equals(DisjointAnalysis.arrayElementFieldName);
4464 // if it's not a class, it doesn't have any fields to match
4465 if( !tdSrc.isClass() ) {
4469 ClassDescriptor cd = tdSrc.getClassDesc();
4470 while( cd != null ) {
4471 Iterator fieldItr = cd.getFields();
4473 while( fieldItr.hasNext() ) {
4474 FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4476 if( fd.getType().equals(edge.getType() ) &&
4477 fd.getSymbol().equals(edge.getField() ) ) {
4482 cd = cd.getSuperDesc();
4485 // otherwise it is a class with fields
4486 // but we didn't find a match
4490 protected boolean hasMatchingType(RefEdge edge,
4491 HeapRegionNode dst) {
4493 // if the region has no type, matches everything
4494 TypeDescriptor tdDst = dst.getType();
4495 assert tdDst != null;
4497 // if the type is not a class or an array, don't
4498 // match because primitives are copied, no aliases
4499 ClassDescriptor cdDst = tdDst.getClassDesc();
4500 if( cdDst == null && !tdDst.isArray() ) {
4504 // if the edge type is null, it matches everything
4505 TypeDescriptor tdEdge = edge.getType();
4506 assert tdEdge != null;
4508 return typeUtil.isSuperorType(tdEdge, tdDst);
4513 // the default signature for quick-and-dirty debugging
4514 public void writeGraph(String graphName) {
4515 writeGraph(graphName,
4516 true, // write labels
4517 true, // label select
4518 true, // prune garbage
4519 false, // hide reachability
4520 true, // hide subset reachability
4521 true, // hide predicates
4522 false, // hide edge taints
4523 null // in-context boundary
4527 public void writeGraph(String graphName,
4528 boolean writeLabels,
4529 boolean labelSelect,
4530 boolean pruneGarbage,
4531 boolean hideReachability,
4532 boolean hideSubsetReachability,
4533 boolean hidePredicates,
4534 boolean hideEdgeTaints
4536 writeGraph(graphName,
4541 hideSubsetReachability,
4547 public void writeGraph(String graphName,
4548 boolean writeLabels,
4549 boolean labelSelect,
4550 boolean pruneGarbage,
4551 boolean hideReachability,
4552 boolean hideSubsetReachability,
4553 boolean hidePredicates,
4554 boolean hideEdgeTaints,
4555 Set<Integer> callerNodeIDsCopiedToCallee
4558 // remove all non-word characters from the graph name so
4559 // the filename and identifier in dot don't cause errors
4560 // jjenista - also replace underscore '_' to prevent some
4561 // really, really long names from IHMS debugging
4562 graphName = graphName.replaceAll("[\\W_]", "");
4565 new BufferedWriter(new FileWriter(graphName+".dot") );
4567 bw.write("digraph "+graphName+" {\n");
4570 // this is an optional step to form the callee-reachable
4571 // "cut-out" into a DOT cluster for visualization
4572 if( callerNodeIDsCopiedToCallee != null ) {
4574 bw.write(" subgraph cluster0 {\n");
4575 bw.write(" color=blue;\n");
4577 Iterator i = id2hrn.entrySet().iterator();
4578 while( i.hasNext() ) {
4579 Map.Entry me = (Map.Entry)i.next();
4580 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4582 if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4585 hrn.toStringDOT(hideReachability,
4586 hideSubsetReachability,
4596 Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4598 // then visit every heap region node
4599 Iterator i = id2hrn.entrySet().iterator();
4600 while( i.hasNext() ) {
4601 Map.Entry me = (Map.Entry)i.next();
4602 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4604 // only visit nodes worth writing out--for instance
4605 // not every node at an allocation is referenced
4606 // (think of it as garbage-collected), etc.
4607 if( !pruneGarbage ||
4608 hrn.isOutOfContext() ||
4609 (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4612 if( !visited.contains(hrn) ) {
4613 traverseHeapRegionNodes(hrn,
4618 hideSubsetReachability,
4621 callerNodeIDsCopiedToCallee);
4626 bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
4629 // then visit every label node, useful for debugging
4631 i = td2vn.entrySet().iterator();
4632 while( i.hasNext() ) {
4633 Map.Entry me = (Map.Entry)i.next();
4634 VariableNode vn = (VariableNode) me.getValue();
4637 String labelStr = vn.getTempDescriptorString();
4638 if( labelStr.startsWith("___temp") ||
4639 labelStr.startsWith("___dst") ||
4640 labelStr.startsWith("___srctmp") ||
4641 labelStr.startsWith("___neverused")
4647 Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4648 while( heapRegionsItr.hasNext() ) {
4649 RefEdge edge = heapRegionsItr.next();
4650 HeapRegionNode hrn = edge.getDst();
4652 if( !visited.contains(hrn) ) {
4653 traverseHeapRegionNodes(hrn,
4658 hideSubsetReachability,
4661 callerNodeIDsCopiedToCallee);
4664 bw.write(" "+vn.toString()+
4665 " -> "+hrn.toString()+
4666 edge.toStringDOT(hideReachability,
4667 hideSubsetReachability,
4679 } catch( IOException e ) {
4680 throw new Error("Error writing out DOT graph "+graphName);
4685 traverseHeapRegionNodes(HeapRegionNode hrn,
4688 Set<HeapRegionNode> visited,
4689 boolean hideReachability,
4690 boolean hideSubsetReachability,
4691 boolean hidePredicates,
4692 boolean hideEdgeTaints,
4693 Set<Integer> callerNodeIDsCopiedToCallee
4694 ) throws java.io.IOException {
4696 if( visited.contains(hrn) ) {
4701 // if we're drawing the callee-view subgraph, only
4702 // write out the node info if it hasn't already been
4704 if( callerNodeIDsCopiedToCallee == null ||
4705 !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4709 hrn.toStringDOT(hideReachability,
4710 hideSubsetReachability,
4715 Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4716 while( childRegionsItr.hasNext() ) {
4717 RefEdge edge = childRegionsItr.next();
4718 HeapRegionNode hrnChild = edge.getDst();
4720 if( callerNodeIDsCopiedToCallee != null &&
4721 (edge.getSrc() instanceof HeapRegionNode) ) {
4722 HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4723 if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4724 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4726 bw.write(" "+hrn.toString()+
4727 " -> "+hrnChild.toString()+
4728 edge.toStringDOT(hideReachability,
4729 hideSubsetReachability,
4734 } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID() ) &&
4735 callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4737 bw.write(" "+hrn.toString()+
4738 " -> "+hrnChild.toString()+
4739 edge.toStringDOT(hideReachability,
4740 hideSubsetReachability,
4743 ",color=blue,style=dashed")+
4746 bw.write(" "+hrn.toString()+
4747 " -> "+hrnChild.toString()+
4748 edge.toStringDOT(hideReachability,
4749 hideSubsetReachability,
4756 bw.write(" "+hrn.toString()+
4757 " -> "+hrnChild.toString()+
4758 edge.toStringDOT(hideReachability,
4759 hideSubsetReachability,
4766 traverseHeapRegionNodes(hrnChild,
4771 hideSubsetReachability,
4774 callerNodeIDsCopiedToCallee);
4783 // return the set of heap regions from the given allocation
4784 // site, if any, that exist in this graph
4785 protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4787 Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4789 Integer idSum = as.getSummary();
4790 if( id2hrn.containsKey(idSum) ) {
4791 out.add(id2hrn.get(idSum) );
4794 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4795 Integer idI = as.getIthOldest(i);
4796 if( id2hrn.containsKey(idI) ) {
4797 out.add(id2hrn.get(idI) );
4804 // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4805 // from the given allocation site, if any, from regions for that
4806 // site that exist in this graph
4807 protected Set<ReachTuple> getAnyExisting(AllocSite as,
4808 boolean includeARITY_ZEROORMORE,
4809 boolean includeARITY_ONE) {
4811 Set<ReachTuple> out = new HashSet<ReachTuple>();
4813 Integer idSum = as.getSummary();
4814 if( id2hrn.containsKey(idSum) ) {
4816 HeapRegionNode hrn = id2hrn.get(idSum);
4817 assert !hrn.isOutOfContext();
4819 if( !includeARITY_ZEROORMORE ) {
4820 out.add(ReachTuple.factory(hrn.getID(),
4821 true, // multi-obj region
4822 ReachTuple.ARITY_ZEROORMORE,
4827 if( includeARITY_ONE ) {
4828 out.add(ReachTuple.factory(hrn.getID(),
4829 true, // multi-object region
4830 ReachTuple.ARITY_ONE,
4836 if( !includeARITY_ONE ) {
4837 // no need to do the single-object regions that
4838 // only have an ARITY ONE possible
4842 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4844 Integer idI = as.getIthOldest(i);
4845 if( id2hrn.containsKey(idI) ) {
4847 HeapRegionNode hrn = id2hrn.get(idI);
4848 assert !hrn.isOutOfContext();
4850 out.add(ReachTuple.factory(hrn.getID(),
4851 false, // multi-object region
4852 ReachTuple.ARITY_ONE,
4862 // if an object allocated at the target site may be
4863 // reachable from both an object from root1 and an
4864 // object allocated at root2, return TRUE
4865 public boolean mayBothReachTarget(AllocSite asRoot1,
4867 AllocSite asTarget) {
4869 // consider all heap regions of the target and look
4870 // for a reach state that indicates regions of root1
4871 // and root2 might be able to reach same object
4872 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4874 // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4875 Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4876 Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4878 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4879 while( hrnItr.hasNext() ) {
4880 HeapRegionNode hrn = hrnItr.next();
4882 Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4883 while( rtItr1.hasNext() ) {
4884 ReachTuple rt1 = rtItr1.next();
4886 Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4887 while( rtItr2.hasNext() ) {
4888 ReachTuple rt2 = rtItr2.next();
4890 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4900 // similar to the method above, return TRUE if ever
4901 // more than one object from the root allocation site
4902 // may reach an object from the target site
4903 public boolean mayManyReachTarget(AllocSite asRoot,
4904 AllocSite asTarget) {
4906 // consider all heap regions of the target and look
4907 // for a reach state that multiple objects of root
4908 // might be able to reach the same object
4909 Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4911 // get relevant reach tuples
4912 Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true, false);
4913 Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4915 Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4916 while( hrnItr.hasNext() ) {
4917 HeapRegionNode hrn = hrnItr.next();
4919 // if any ZERORMORE tuples are here, TRUE
4920 Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4921 while( rtItr.hasNext() ) {
4922 ReachTuple rtZOM = rtItr.next();
4924 if( hrn.getAlpha().containsTuple(rtZOM) ) {
4929 // otherwise, look for any pair of ONE tuples
4930 Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4931 while( rtItr1.hasNext() ) {
4932 ReachTuple rt1 = rtItr1.next();
4934 Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4935 while( rtItr2.hasNext() ) {
4936 ReachTuple rt2 = rtItr2.next();
4942 if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4956 public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4958 Set<HeapRegionNode> exhibitProofState =
4959 new HashSet<HeapRegionNode>();
4961 Iterator hrnItr = id2hrn.entrySet().iterator();
4962 while( hrnItr.hasNext() ) {
4963 Map.Entry me = (Map.Entry)hrnItr.next();
4964 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4966 ReachSet intersection =
4967 Canonical.intersection(proofOfSharing,
4970 if( !intersection.isEmpty() ) {
4971 assert !hrn.isOutOfContext();
4972 exhibitProofState.add(hrn);
4976 return exhibitProofState;
4980 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4981 HeapRegionNode hrn2) {
4982 assert hrn1 != null;
4983 assert hrn2 != null;
4985 assert !hrn1.isOutOfContext();
4986 assert !hrn2.isOutOfContext();
4988 assert belongsToThis(hrn1);
4989 assert belongsToThis(hrn2);
4991 assert !hrn1.getID().equals(hrn2.getID() );
4994 // then get the various tokens for these heap regions
4996 ReachTuple.factory(hrn1.getID(),
4997 !hrn1.isSingleObject(), // multi?
4998 ReachTuple.ARITY_ONE,
5001 ReachTuple h1star = null;
5002 if( !hrn1.isSingleObject() ) {
5004 ReachTuple.factory(hrn1.getID(),
5005 !hrn1.isSingleObject(),
5006 ReachTuple.ARITY_ZEROORMORE,
5011 ReachTuple.factory(hrn2.getID(),
5012 !hrn2.isSingleObject(),
5013 ReachTuple.ARITY_ONE,
5016 ReachTuple h2star = null;
5017 if( !hrn2.isSingleObject() ) {
5019 ReachTuple.factory(hrn2.getID(),
5020 !hrn2.isSingleObject(),
5021 ReachTuple.ARITY_ZEROORMORE,
5025 // then get the merged beta of all out-going edges from these heap
5028 ReachSet beta1 = ReachSet.factory();
5029 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
5030 while (itrEdge.hasNext()) {
5031 RefEdge edge = itrEdge.next();
5032 beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
5035 ReachSet beta2 = ReachSet.factory();
5036 itrEdge = hrn2.iteratorToReferencees();
5037 while (itrEdge.hasNext()) {
5038 RefEdge edge = itrEdge.next();
5039 beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
5042 ReachSet proofOfSharing = ReachSet.factory();
5045 Canonical.unionORpreds(proofOfSharing,
5046 beta1.getStatesWithBoth(h1, h2)
5049 Canonical.unionORpreds(proofOfSharing,
5050 beta2.getStatesWithBoth(h1, h2)
5053 if( !hrn1.isSingleObject() ) {
5055 Canonical.unionORpreds(proofOfSharing,
5056 beta1.getStatesWithBoth(h1star, h2)
5059 Canonical.unionORpreds(proofOfSharing,
5060 beta2.getStatesWithBoth(h1star, h2)
5064 if( !hrn2.isSingleObject() ) {
5066 Canonical.unionORpreds(proofOfSharing,
5067 beta1.getStatesWithBoth(h1, h2star)
5070 Canonical.unionORpreds(proofOfSharing,
5071 beta2.getStatesWithBoth(h1, h2star)
5075 if( !hrn1.isSingleObject() &&
5076 !hrn2.isSingleObject()
5079 Canonical.unionORpreds(proofOfSharing,
5080 beta1.getStatesWithBoth(h1star, h2star)
5083 Canonical.unionORpreds(proofOfSharing,
5084 beta2.getStatesWithBoth(h1star, h2star)
5088 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5089 if( !proofOfSharing.isEmpty() ) {
5090 common = findCommonReachableNodes(proofOfSharing);
5091 if( !DISABLE_STRONG_UPDATES &&
5092 !DISABLE_GLOBAL_SWEEP
5094 assert !common.isEmpty();
5101 // this version of the above method checks whether there is sharing
5102 // among the objects in a summary node
5103 public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
5105 assert hrn.isNewSummary();
5106 assert !hrn.isOutOfContext();
5107 assert belongsToThis(hrn);
5110 ReachTuple.factory(hrn.getID(),
5112 ReachTuple.ARITY_ZEROORMORE,
5115 // then get the merged beta of all out-going edges from
5118 ReachSet beta = ReachSet.factory();
5119 Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
5120 while (itrEdge.hasNext()) {
5121 RefEdge edge = itrEdge.next();
5122 beta = Canonical.unionORpreds(beta, edge.getBeta());
5125 ReachSet proofOfSharing = ReachSet.factory();
5128 Canonical.unionORpreds(proofOfSharing,
5129 beta.getStatesWithBoth(hstar, hstar)
5132 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5133 if( !proofOfSharing.isEmpty() ) {
5134 common = findCommonReachableNodes(proofOfSharing);
5135 if( !DISABLE_STRONG_UPDATES &&
5136 !DISABLE_GLOBAL_SWEEP
5138 assert !common.isEmpty();
5146 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5147 Integer paramIndex1,
5148 Integer paramIndex2) {
5150 // get parameter's heap regions
5151 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5152 assert this.hasVariable(paramTemp1);
5153 VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5156 if( !(paramVar1.getNumReferencees() == 1) ) {
5157 System.out.println("\n fm="+fm+"\n param="+paramTemp1);
5158 writeGraph("whatup");
5162 assert paramVar1.getNumReferencees() == 1;
5163 RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5164 HeapRegionNode hrnParam1 = paramEdge1.getDst();
5166 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5167 assert this.hasVariable(paramTemp2);
5168 VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5170 if( !(paramVar2.getNumReferencees() == 1) ) {
5171 System.out.println("\n fm="+fm+"\n param="+paramTemp2);
5172 writeGraph("whatup");
5175 assert paramVar2.getNumReferencees() == 1;
5176 RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5177 HeapRegionNode hrnParam2 = paramEdge2.getDst();
5179 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5180 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5185 public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5189 // get parameter's heap regions
5190 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5191 assert this.hasVariable(paramTemp);
5192 VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5193 assert paramVar.getNumReferencees() == 1;
5194 RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5195 HeapRegionNode hrnParam = paramEdge.getDst();
5198 HeapRegionNode hrnSummary=null;
5199 if(id2hrn.containsKey(as.getSummary())) {
5200 // if summary node doesn't exist, ignore this case
5201 hrnSummary = id2hrn.get(as.getSummary());
5202 assert hrnSummary != null;
5205 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5206 if(hrnSummary!=null) {
5207 common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5210 // check for other nodes
5211 for (int i = 0; i < as.getAllocationDepth(); ++i) {
5213 assert id2hrn.containsKey(as.getIthOldest(i));
5214 HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5215 assert hrnIthOldest != null;
5217 common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5224 public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5227 // get summary node 1's alpha
5228 Integer idSum1 = as1.getSummary();
5229 HeapRegionNode hrnSum1=null;
5230 if(id2hrn.containsKey(idSum1)) {
5231 hrnSum1 = id2hrn.get(idSum1);
5234 // get summary node 2's alpha
5235 Integer idSum2 = as2.getSummary();
5236 HeapRegionNode hrnSum2=null;
5237 if(id2hrn.containsKey(idSum2)) {
5238 hrnSum2 = id2hrn.get(idSum2);
5241 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5242 if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5243 common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5247 // ask if objects from this summary share among each other
5248 common.addAll(mayReachSharedObjects(hrnSum1));
5251 // check sum2 against alloc1 nodes
5253 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5254 Integer idI1 = as1.getIthOldest(i);
5255 assert id2hrn.containsKey(idI1);
5256 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5257 assert hrnI1 != null;
5258 common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5261 // also ask if objects from this summary share among each other
5262 common.addAll(mayReachSharedObjects(hrnSum2));
5265 // check sum1 against alloc2 nodes
5266 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5267 Integer idI2 = as2.getIthOldest(i);
5268 assert id2hrn.containsKey(idI2);
5269 HeapRegionNode hrnI2 = id2hrn.get(idI2);
5270 assert hrnI2 != null;
5273 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5276 // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5277 for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5278 Integer idI1 = as1.getIthOldest(j);
5280 // if these are the same site, don't look for the same token, no
5282 // different tokens of the same site could alias together though
5283 if (idI1.equals(idI2)) {
5287 HeapRegionNode hrnI1 = id2hrn.get(idI1);
5289 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5296 public void makeInaccessible(Set<TempDescriptor> vars) {
5297 inaccessibleVars.addAll(vars);
5300 public void makeInaccessible(TempDescriptor td) {
5301 inaccessibleVars.add(td);
5304 public void makeAccessible(TempDescriptor td) {
5305 inaccessibleVars.remove(td);
5308 public boolean isAccessible(TempDescriptor td) {
5309 return !inaccessibleVars.contains(td);
5312 public Set<TempDescriptor> getInaccessibleVars() {
5313 return inaccessibleVars;
5319 public Set<Alloc> canPointTo( TempDescriptor x ) {
5321 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5322 // if we don't care to track it, return null which means
5323 // "a client of this result shouldn't care either"
5324 return HeapAnalysis.DONTCARE_PTR;
5327 Set<Alloc> out = new HashSet<Alloc>();
5329 VariableNode vn = getVariableNodeNoMutation( x );
5331 // the empty set means "can't point to anything"
5335 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5336 while( edgeItr.hasNext() ) {
5337 HeapRegionNode hrn = edgeItr.next().getDst();
5338 out.add( hrn.getAllocSite() );
5346 public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5348 TypeDescriptor fieldType ) {
5350 if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5351 // if we don't care to track it, return null which means
5352 // "a client of this result shouldn't care either"
5353 return HeapAnalysis.DONTCARE_DREF;
5356 Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5358 VariableNode vn = getVariableNodeNoMutation( x );
5360 // the empty table means "x can't point to anything"
5364 Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5365 while( edgeItr.hasNext() ) {
5366 HeapRegionNode hrn = edgeItr.next().getDst();
5367 Alloc key = hrn.getAllocSite();
5369 if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5370 // if we don't care to track it, put no entry which means
5371 // "a client of this result shouldn't care either"
5372 out.put( key, HeapAnalysis.DONTCARE_PTR );
5376 Set<Alloc> moreValues = new HashSet<Alloc>();
5377 Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5378 while( edgeItr2.hasNext() ) {
5379 RefEdge edge = edgeItr2.next();
5381 if( field.equals( edge.getField() ) ) {
5382 moreValues.add( edge.getDst().getAllocSite() );
5386 if( out.containsKey( key ) ) {
5387 out.get( key ).addAll( moreValues );
5389 out.put( key, moreValues );
5399 public TempDescriptor findVariableByName( String name ) {
5401 for( TempDescriptor td: td2vn.keySet() ) {
5402 if( td.getSymbol().contains( name ) ) {