+ return false;
+ }
+
+
+
+
+
+ public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
+
+ Set<HeapRegionNode> exhibitProofState =
+ new HashSet<HeapRegionNode>();
+
+ Iterator hrnItr = id2hrn.entrySet().iterator();
+ while( hrnItr.hasNext() ) {
+ Map.Entry me = (Map.Entry)hrnItr.next();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ ReachSet intersection =
+ Canonical.intersection(proofOfSharing,
+ hrn.getAlpha()
+ );
+ if( !intersection.isEmpty() ) {
+ assert !hrn.isOutOfContext();
+ exhibitProofState.add(hrn);
+ }
+ }
+
+ return exhibitProofState;
+ }
+
+
+ public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
+ HeapRegionNode hrn2) {
+ assert hrn1 != null;
+ assert hrn2 != null;
+
+ assert !hrn1.isOutOfContext();
+ assert !hrn2.isOutOfContext();
+
+ assert belongsToThis(hrn1);
+ assert belongsToThis(hrn2);
+
+ assert !hrn1.getID().equals(hrn2.getID() );
+
+
+ // then get the various tokens for these heap regions
+ ReachTuple h1 =
+ ReachTuple.factory(hrn1.getID(),
+ !hrn1.isSingleObject(), // multi?
+ ReachTuple.ARITY_ONE,
+ false); // ooc?
+
+ ReachTuple h1star = null;
+ if( !hrn1.isSingleObject() ) {
+ h1star =
+ ReachTuple.factory(hrn1.getID(),
+ !hrn1.isSingleObject(),
+ ReachTuple.ARITY_ZEROORMORE,
+ false);
+ }
+
+ ReachTuple h2 =
+ ReachTuple.factory(hrn2.getID(),
+ !hrn2.isSingleObject(),
+ ReachTuple.ARITY_ONE,
+ false);
+
+ ReachTuple h2star = null;
+ if( !hrn2.isSingleObject() ) {
+ h2star =
+ ReachTuple.factory(hrn2.getID(),
+ !hrn2.isSingleObject(),
+ ReachTuple.ARITY_ZEROORMORE,
+ false);
+ }
+
+ // then get the merged beta of all out-going edges from these heap
+ // regions
+
+ ReachSet beta1 = ReachSet.factory();
+ Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
+ while (itrEdge.hasNext()) {
+ RefEdge edge = itrEdge.next();
+ beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
+ }
+
+ ReachSet beta2 = ReachSet.factory();
+ itrEdge = hrn2.iteratorToReferencees();
+ while (itrEdge.hasNext()) {
+ RefEdge edge = itrEdge.next();
+ beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
+ }
+
+ ReachSet proofOfSharing = ReachSet.factory();
+
+ proofOfSharing =
+ Canonical.unionORpreds(proofOfSharing,
+ beta1.getStatesWithBoth(h1, h2)
+ );
+ proofOfSharing =
+ Canonical.unionORpreds(proofOfSharing,
+ beta2.getStatesWithBoth(h1, h2)
+ );
+
+ if( !hrn1.isSingleObject() ) {
+ proofOfSharing =
+ Canonical.unionORpreds(proofOfSharing,
+ beta1.getStatesWithBoth(h1star, h2)
+ );
+ proofOfSharing =
+ Canonical.unionORpreds(proofOfSharing,
+ beta2.getStatesWithBoth(h1star, h2)
+ );
+ }
+
+ if( !hrn2.isSingleObject() ) {
+ proofOfSharing =
+ Canonical.unionORpreds(proofOfSharing,
+ beta1.getStatesWithBoth(h1, h2star)
+ );
+ proofOfSharing =
+ Canonical.unionORpreds(proofOfSharing,
+ beta2.getStatesWithBoth(h1, h2star)
+ );
+ }
+
+ if( !hrn1.isSingleObject() &&
+ !hrn2.isSingleObject()
+ ) {
+ proofOfSharing =
+ Canonical.unionORpreds(proofOfSharing,
+ beta1.getStatesWithBoth(h1star, h2star)
+ );
+ proofOfSharing =
+ Canonical.unionORpreds(proofOfSharing,
+ beta2.getStatesWithBoth(h1star, h2star)
+ );
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if( !proofOfSharing.isEmpty() ) {
+ common = findCommonReachableNodes(proofOfSharing);
+ if( !DISABLE_STRONG_UPDATES &&
+ !DISABLE_GLOBAL_SWEEP
+ ) {
+ assert !common.isEmpty();
+ }
+ }
+
+ return common;
+ }
+
+ // this version of the above method checks whether there is sharing
+ // among the objects in a summary node
+ public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
+ assert hrn != null;
+ assert hrn.isNewSummary();
+ assert !hrn.isOutOfContext();
+ assert belongsToThis(hrn);
+
+ ReachTuple hstar =
+ ReachTuple.factory(hrn.getID(),
+ true, // multi
+ ReachTuple.ARITY_ZEROORMORE,
+ false); // ooc
+
+ // then get the merged beta of all out-going edges from
+ // this heap region
+
+ ReachSet beta = ReachSet.factory();
+ Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
+ while (itrEdge.hasNext()) {
+ RefEdge edge = itrEdge.next();
+ beta = Canonical.unionORpreds(beta, edge.getBeta());
+ }
+
+ ReachSet proofOfSharing = ReachSet.factory();
+
+ proofOfSharing =
+ Canonical.unionORpreds(proofOfSharing,
+ beta.getStatesWithBoth(hstar, hstar)
+ );
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if( !proofOfSharing.isEmpty() ) {
+ common = findCommonReachableNodes(proofOfSharing);
+ if( !DISABLE_STRONG_UPDATES &&
+ !DISABLE_GLOBAL_SWEEP
+ ) {
+ assert !common.isEmpty();
+ }
+ }
+
+ return common;
+ }
+
+
+ public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
+ Integer paramIndex1,
+ Integer paramIndex2) {
+
+ // get parameter's heap regions
+ TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
+ assert this.hasVariable(paramTemp1);
+ VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
+
+
+ if( !(paramVar1.getNumReferencees() == 1) ) {
+ System.out.println("\n fm="+fm+"\n param="+paramTemp1);
+ writeGraph("whatup");
+ }
+
+
+ assert paramVar1.getNumReferencees() == 1;
+ RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
+ HeapRegionNode hrnParam1 = paramEdge1.getDst();
+
+ TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
+ assert this.hasVariable(paramTemp2);
+ VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
+
+ if( !(paramVar2.getNumReferencees() == 1) ) {
+ System.out.println("\n fm="+fm+"\n param="+paramTemp2);
+ writeGraph("whatup");
+ }
+
+ assert paramVar2.getNumReferencees() == 1;
+ RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
+ HeapRegionNode hrnParam2 = paramEdge2.getDst();
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
+
+ return common;
+ }
+
+ public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
+ Integer paramIndex,
+ AllocSite as) {
+
+ // get parameter's heap regions
+ TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
+ assert this.hasVariable(paramTemp);
+ VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
+ assert paramVar.getNumReferencees() == 1;
+ RefEdge paramEdge = paramVar.iteratorToReferencees().next();
+ HeapRegionNode hrnParam = paramEdge.getDst();
+
+ // get summary node
+ HeapRegionNode hrnSummary=null;
+ if(id2hrn.containsKey(as.getSummary())) {
+ // if summary node doesn't exist, ignore this case
+ hrnSummary = id2hrn.get(as.getSummary());
+ assert hrnSummary != null;
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if(hrnSummary!=null) {
+ common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
+ }
+
+ // check for other nodes
+ for (int i = 0; i < as.getAllocationDepth(); ++i) {
+
+ assert id2hrn.containsKey(as.getIthOldest(i));
+ HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
+ assert hrnIthOldest != null;
+
+ common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
+
+ }
+
+ return common;
+ }
+
+ public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
+ AllocSite as2) {
+
+ // get summary node 1's alpha
+ Integer idSum1 = as1.getSummary();
+ HeapRegionNode hrnSum1=null;
+ if(id2hrn.containsKey(idSum1)) {
+ hrnSum1 = id2hrn.get(idSum1);
+ }
+
+ // get summary node 2's alpha
+ Integer idSum2 = as2.getSummary();
+ HeapRegionNode hrnSum2=null;
+ if(id2hrn.containsKey(idSum2)) {
+ hrnSum2 = id2hrn.get(idSum2);
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
+ common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
+ }
+
+ if(hrnSum1!=null) {
+ // ask if objects from this summary share among each other
+ common.addAll(mayReachSharedObjects(hrnSum1));
+ }
+
+ // check sum2 against alloc1 nodes
+ if(hrnSum2!=null) {
+ for (int i = 0; i < as1.getAllocationDepth(); ++i) {
+ Integer idI1 = as1.getIthOldest(i);
+ assert id2hrn.containsKey(idI1);
+ HeapRegionNode hrnI1 = id2hrn.get(idI1);
+ assert hrnI1 != null;
+ common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
+ }
+
+ // also ask if objects from this summary share among each other
+ common.addAll(mayReachSharedObjects(hrnSum2));
+ }
+
+ // check sum1 against alloc2 nodes
+ for (int i = 0; i < as2.getAllocationDepth(); ++i) {
+ Integer idI2 = as2.getIthOldest(i);
+ assert id2hrn.containsKey(idI2);
+ HeapRegionNode hrnI2 = id2hrn.get(idI2);
+ assert hrnI2 != null;
+
+ if(hrnSum1!=null) {
+ common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
+ }
+
+ // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
+ for (int j = 0; j < as1.getAllocationDepth(); ++j) {
+ Integer idI1 = as1.getIthOldest(j);
+
+ // if these are the same site, don't look for the same token, no
+ // alias.
+ // different tokens of the same site could alias together though
+ if (idI1.equals(idI2)) {
+ continue;
+ }
+
+ HeapRegionNode hrnI1 = id2hrn.get(idI1);
+
+ common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
+ }
+ }
+
+ return common;
+ }
+
+ public void makeInaccessible(Set<TempDescriptor> vars) {
+ inaccessibleVars.addAll(vars);
+ }
+
+ public void makeInaccessible(TempDescriptor td) {
+ inaccessibleVars.add(td);
+ }
+
+ public void makeAccessible(TempDescriptor td) {
+ inaccessibleVars.remove(td);
+ }
+
+ public boolean isAccessible(TempDescriptor td) {
+ return !inaccessibleVars.contains(td);
+ }
+
+ public Set<TempDescriptor> getInaccessibleVars() {
+ return inaccessibleVars;
+ }
+
+
+
+
+ public Set<Alloc> canPointTo( TempDescriptor x ) {
+
+ if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
+ // if we don't care to track it, return null which means
+ // "a client of this result shouldn't care either"
+ return HeapAnalysis.DONTCARE_PTR;
+ }
+
+ Set<Alloc> out = new HashSet<Alloc>();
+
+ VariableNode vn = getVariableNodeNoMutation( x );
+ if( vn == null ) {
+ // the empty set means "can't point to anything"
+ return out;
+ }
+
+ Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ HeapRegionNode hrn = edgeItr.next().getDst();
+ out.add( hrn.getAllocSite() );
+ }
+
+ return out;
+ }
+
+
+
+ public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
+ String field,
+ TypeDescriptor fieldType ) {
+
+ if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
+ // if we don't care to track it, return null which means
+ // "a client of this result shouldn't care either"
+ return HeapAnalysis.DONTCARE_DREF;
+ }
+
+ Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
+
+ VariableNode vn = getVariableNodeNoMutation( x );
+ if( vn == null ) {
+ // the empty table means "x can't point to anything"
+ return out;
+ }
+
+ Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ HeapRegionNode hrn = edgeItr.next().getDst();
+ Alloc key = hrn.getAllocSite();
+
+ if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
+ // if we don't care to track it, put no entry which means
+ // "a client of this result shouldn't care either"
+ out.put( key, HeapAnalysis.DONTCARE_PTR );
+ continue;
+ }
+
+ Set<Alloc> moreValues = new HashSet<Alloc>();
+ Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
+ while( edgeItr2.hasNext() ) {
+ RefEdge edge = edgeItr2.next();
+
+ if( field.equals( edge.getField() ) ) {
+ moreValues.add( edge.getDst().getAllocSite() );
+ }
+ }
+
+ if( out.containsKey( key ) ) {
+ out.get( key ).addAll( moreValues );
+ } else {
+ out.put( key, moreValues );
+ }
+ }
+
+ return out;
+ }
+
+
+
+ // for debugging
+ public TempDescriptor findVariableByName( String name ) {
+
+ for( TempDescriptor td: td2vn.keySet() ) {
+ if( td.getSymbol().contains( name ) ) {
+ return td;
+ }
+ }
+
+ return null;
+ }