+ 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;
+ }