+ }
+
+ if( !edgeFound ) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+
+ protected boolean areParamIndexMappingsEqual(OwnershipGraph og) {
+
+ if( idPrimary2paramIndexSet.size() != og.idPrimary2paramIndexSet.size() ) {
+ return false;
+ }
+
+ if( idSecondary2paramIndexSet.size() != og.idSecondary2paramIndexSet.size() ) {
+ return false;
+ }
+
+ return true;
+ }
+
+
+ public Set<HeapRegionNode> hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) {
+ assert hrn1 != null;
+ assert hrn2 != null;
+
+ // then get the various tokens for these heap regions
+ TokenTuple h1 = new TokenTuple(hrn1.getID(),
+ !hrn1.isSingleObject(),
+ TokenTuple.ARITY_ONE).makeCanonical();
+
+ TokenTuple h1plus = new TokenTuple(hrn1.getID(),
+ !hrn1.isSingleObject(),
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
+ TokenTuple h1star = new TokenTuple(hrn1.getID(),
+ !hrn1.isSingleObject(),
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+ TokenTuple h2 = new TokenTuple(hrn2.getID(),
+ !hrn2.isSingleObject(),
+ TokenTuple.ARITY_ONE).makeCanonical();
+
+ TokenTuple h2plus = new TokenTuple(hrn2.getID(),
+ !hrn2.isSingleObject(),
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
+ TokenTuple h2star = new TokenTuple(hrn2.getID(),
+ !hrn2.isSingleObject(),
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+ // then get the merged beta of all out-going edges from these heap regions
+ ReachabilitySet beta1 = new ReachabilitySet().makeCanonical();
+ Iterator<ReferenceEdge> itrEdge = hrn1.iteratorToReferencees();
+ while( itrEdge.hasNext() ) {
+ ReferenceEdge edge = itrEdge.next();
+ beta1 = beta1.union( edge.getBeta() );
+ }
+
+ ReachabilitySet beta2 = new ReachabilitySet().makeCanonical();
+ itrEdge = hrn2.iteratorToReferencees();
+ while( itrEdge.hasNext() ) {
+ ReferenceEdge edge = itrEdge.next();
+ beta2 = beta2.union( edge.getBeta() );
+ }
+
+ boolean aliasDetected = false;
+
+ // only do this one if they are different tokens
+ if( h1 != h2 &&
+ beta1.containsTupleSetWithBoth(h1, h2) ) {
+ aliasDetected = true;
+ }
+ if( beta1.containsTupleSetWithBoth(h1plus, h2) ) {
+ aliasDetected = true;
+ }
+ if( beta1.containsTupleSetWithBoth(h1star, h2) ) {
+ aliasDetected = true;
+ }
+ if( beta1.containsTupleSetWithBoth(h1, h2plus) ) {
+ aliasDetected = true;
+ }
+ if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) {
+ aliasDetected = true;
+ }
+ if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) {
+ aliasDetected = true;
+ }
+ if( beta1.containsTupleSetWithBoth(h1, h2star) ) {
+ aliasDetected = true;
+ }
+ if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) {
+ aliasDetected = true;
+ }
+ if( beta1.containsTupleSetWithBoth(h1star, h2star) ) {
+ aliasDetected = true;
+ }
+
+ if( h1 != h2 &&
+ beta2.containsTupleSetWithBoth(h1, h2) ) {
+ aliasDetected = true;
+ }
+ if( beta2.containsTupleSetWithBoth(h1plus, h2) ) {
+ aliasDetected = true;
+ }
+ if( beta2.containsTupleSetWithBoth(h1star, h2) ) {
+ aliasDetected = true;
+ }
+ if( beta2.containsTupleSetWithBoth(h1, h2plus) ) {
+ aliasDetected = true;
+ }
+ if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) {
+ aliasDetected = true;
+ }
+ if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) {
+ aliasDetected = true;
+ }
+ if( beta2.containsTupleSetWithBoth(h1, h2star) ) {
+ aliasDetected = true;
+ }
+ if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) {
+ aliasDetected = true;
+ }
+ if( beta2.containsTupleSetWithBoth(h1star, h2star) ) {
+ aliasDetected = true;
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if( aliasDetected ) {
+ common = findCommonReachableNodes( hrn1, hrn2 );
+ assert !common.isEmpty();
+ }
+
+ return common;
+ }
+
+
+ public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
+
+ // get parameter 1's heap regions
+ assert paramIndex2idPrimary.containsKey(paramIndex1);
+ Integer idParamPri1 = paramIndex2idPrimary.get(paramIndex1);
+
+ assert id2hrn.containsKey(idParamPri1);
+ HeapRegionNode hrnParamPri1 = id2hrn.get(idParamPri1);
+ assert hrnParamPri1 != null;
+
+ HeapRegionNode hrnParamSec1 = null;
+ if( paramIndex2idSecondary.containsKey(paramIndex1) ) {
+ Integer idParamSec1 = paramIndex2idSecondary.get(paramIndex1);
+
+ assert id2hrn.containsKey(idParamSec1);
+ hrnParamSec1 = id2hrn.get(idParamSec1);
+ assert hrnParamSec1 != null;
+ }
+
+
+ // get the other parameter
+ assert paramIndex2idPrimary.containsKey(paramIndex2);
+ Integer idParamPri2 = paramIndex2idPrimary.get(paramIndex2);
+
+ assert id2hrn.containsKey(idParamPri2);
+ HeapRegionNode hrnParamPri2 = id2hrn.get(idParamPri2);
+ assert hrnParamPri2 != null;
+
+ HeapRegionNode hrnParamSec2 = null;
+ if( paramIndex2idSecondary.containsKey(paramIndex2) ) {
+ Integer idParamSec2 = paramIndex2idSecondary.get(paramIndex2);
+
+ assert id2hrn.containsKey(idParamSec2);
+ hrnParamSec2 = id2hrn.get(idParamSec2);
+ assert hrnParamSec2 != null;
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ common.addAll( hasPotentialAlias( hrnParamPri1, hrnParamPri2 ) );
+
+ if( hrnParamSec1 != null ) {
+ common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamPri2 ) );
+ }
+
+ if( hrnParamSec2 != null ) {
+ common.addAll( hasPotentialAlias( hrnParamSec2, hrnParamPri1 ) );
+ }
+
+ if( hrnParamSec1 != null && hrnParamSec2 != null ) {
+ common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamSec2 ) );
+ }
+
+ return common;
+ }
+
+
+ public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex, AllocationSite as) {
+
+ // get parameter's heap regions
+ assert paramIndex2idPrimary.containsKey(paramIndex);
+ Integer idParamPri = paramIndex2idPrimary.get(paramIndex);
+
+ assert id2hrn.containsKey(idParamPri);
+ HeapRegionNode hrnParamPri = id2hrn.get(idParamPri);
+ assert hrnParamPri != null;
+
+ HeapRegionNode hrnParamSec = null;
+ if( paramIndex2idSecondary.containsKey(paramIndex) ) {
+ Integer idParamSec = paramIndex2idSecondary.get(paramIndex);
+
+ assert id2hrn.containsKey(idParamSec);
+ hrnParamSec = id2hrn.get(idParamSec);
+ assert hrnParamSec != null;
+ }
+
+ // get summary node
+ assert id2hrn.containsKey( as.getSummary() );
+ HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() );
+ assert hrnSummary != null;
+
+ Set<HeapRegionNode> common = hasPotentialAlias( hrnParamPri, hrnSummary );
+
+ if( hrnParamSec != null ) {
+ common.addAll( hasPotentialAlias( hrnParamSec, 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 = hasPotentialAlias( hrnParamPri, hrnIthOldest );
+
+ if( hrnParamSec != null ) {
+ common.addAll( hasPotentialAlias( hrnParamSec, hrnIthOldest ) );
+ }
+ }
+
+ return common;
+ }
+
+
+ public Set<HeapRegionNode> hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
+
+ // get summary node 1's alpha
+ Integer idSum1 = as1.getSummary();
+ assert id2hrn.containsKey(idSum1);
+ HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
+ assert hrnSum1 != null;
+
+ // get summary node 2's alpha
+ Integer idSum2 = as2.getSummary();
+ assert id2hrn.containsKey(idSum2);
+ HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
+ assert hrnSum2 != null;
+
+ Set<HeapRegionNode> common = hasPotentialAlias( hrnSum1, hrnSum2 );
+
+ // check sum2 against alloc1 nodes
+ 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( hasPotentialAlias( hrnI1, 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;
+
+ common.addAll( hasPotentialAlias( 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( hasPotentialAlias( hrnI1, hrnI2 ) );
+ }
+ }
+
+ return common;
+ }
+
+
+ public Set<HeapRegionNode> findCommonReachableNodes( HeapRegionNode hrn1,
+ HeapRegionNode hrn2 ) {
+
+ Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
+ Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
+
+ Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
+ todoNodes1.add( hrn1 );
+
+ Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
+ todoNodes2.add( hrn2 );
+
+ // follow links until all reachable nodes have been found
+ while( !todoNodes1.isEmpty() ) {
+ HeapRegionNode hrn = todoNodes1.iterator().next();
+ todoNodes1.remove( hrn );
+ reachableNodes1.add(hrn);
+
+ Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edge = edgeItr.next();
+
+ if( !reachableNodes1.contains( edge.getDst() ) ) {
+ todoNodes1.add( edge.getDst() );
+ }
+ }
+ }
+
+ while( !todoNodes2.isEmpty() ) {
+ HeapRegionNode hrn = todoNodes2.iterator().next();
+ todoNodes2.remove( hrn );
+ reachableNodes2.add(hrn);
+
+ Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edge = edgeItr.next();
+
+ if( !reachableNodes2.contains( edge.getDst() ) ) {
+ todoNodes2.add( edge.getDst() );
+ }
+ }
+ }
+
+ Set<HeapRegionNode> intersection =
+ new HashSet<HeapRegionNode>( reachableNodes1 );
+
+ intersection.retainAll( reachableNodes2 );
+
+ return intersection;
+ }
+
+
+ // for writing ownership graphs to dot files
+ public void writeGraph(MethodContext mc,
+ FlatNode fn,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings
+ ) throws java.io.IOException {
+ writeGraph(
+ mc.toString() +
+ fn.toString(),
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings
+ );
+ }
+
+ public void writeGraph(MethodContext mc,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings
+ ) throws java.io.IOException {
+
+ writeGraph(mc+"COMPLETE",
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings
+ );
+ }
+
+ public void writeGraph(MethodContext mc,
+ Integer numUpdate,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings
+ ) throws java.io.IOException {
+
+
+
+ writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate),
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings
+ );
+ }
+
+ public void writeGraph(String graphName,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings
+ ) throws java.io.IOException {
+
+ // remove all non-word characters from the graph name so
+ // the filename and identifier in dot don't cause errors
+ graphName = graphName.replaceAll("[\\W]", "");
+
+ BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
+ bw.write("digraph "+graphName+" {\n");
+
+ HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
+
+ // then visit every heap region node
+ Set s = id2hrn.entrySet();
+ Iterator i = s.iterator();
+ while( i.hasNext() ) {
+ Map.Entry me = (Map.Entry)i.next();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ if( !pruneGarbage ||
+ (hrn.isFlagged() && hrn.getID() > 0) ||
+ hrn.getDescription().startsWith("param")
+ ) {
+
+ if( !visited.contains(hrn) ) {
+ traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
+ hrn,
+ bw,
+ null,
+ visited,
+ writeReferencers);
+ }
+ }
+ }
+
+ bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
+
+ if( writeParamMappings ) {
+ /* UNMAINTAINED
+ Set df = paramIndex2id.entrySet();
+ Iterator ih = df.iterator();
+ while( ih.hasNext() ) {
+ Map.Entry meh = (Map.Entry)ih.next();
+ Integer pi = (Integer) meh.getKey();
+ Integer id = (Integer) meh.getValue();
+ bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
+ }
+ */
+ }
+
+ // then visit every label node, useful for debugging
+ if( writeLabels ) {
+ s = td2ln.entrySet();
+ i = s.iterator();
+ while( i.hasNext() ) {
+ Map.Entry me = (Map.Entry)i.next();
+ LabelNode ln = (LabelNode) me.getValue();
+
+ if( labelSelect ) {
+ String labelStr = ln.getTempDescriptorString();
+ if( labelStr.startsWith("___temp") ||
+ labelStr.startsWith("___dst") ||
+ labelStr.startsWith("___srctmp") ||
+ labelStr.startsWith("___neverused") ||
+ labelStr.contains(qString) ||
+ labelStr.contains(rString) ||
+ labelStr.contains(blobString)
+ ) {
+ continue;
+ }
+ }
+
+ //bw.write(" "+ln.toString() + ";\n");
+
+ Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
+ while( heapRegionsItr.hasNext() ) {
+ ReferenceEdge edge = heapRegionsItr.next();
+ HeapRegionNode hrn = edge.getDst();
+
+ if( pruneGarbage && !visited.contains(hrn) ) {
+ traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
+ hrn,
+ bw,
+ null,
+ visited,
+ writeReferencers);
+ }
+
+ bw.write(" " + ln.toString() +
+ " -> " + hrn.toString() +
+ "[label=\"" + edge.toGraphEdgeString() +
+ "\",decorate];\n");
+ }
+ }
+ }
+
+
+ bw.write("}\n");
+ bw.close();
+ }
+
+ protected void traverseHeapRegionNodes(int mode,
+ HeapRegionNode hrn,
+ BufferedWriter bw,
+ TempDescriptor td,
+ HashSet<HeapRegionNode> visited,
+ boolean writeReferencers
+ ) throws java.io.IOException {
+
+ if( visited.contains(hrn) ) {
+ return;
+ }
+ visited.add(hrn);
+
+ switch( mode ) {
+ case VISIT_HRN_WRITE_FULL:
+
+ String attributes = "[";
+
+ if( hrn.isSingleObject() ) {
+ attributes += "shape=box";
+ } else {
+ attributes += "shape=Msquare";
+ }
+
+ if( hrn.isFlagged() ) {
+ attributes += ",style=filled,fillcolor=lightgrey";
+ }
+
+ attributes += ",label=\"ID" +
+ hrn.getID() +
+ "\\n";
+
+ if( hrn.getType() != null ) {
+ attributes += hrn.getType().toPrettyString() + "\\n";
+ }
+
+ attributes += hrn.getDescription() +
+ "\\n" +
+ hrn.getAlphaString() +
+ "\"]";
+
+ bw.write(" " + hrn.toString() + attributes + ";\n");
+ break;
+ }
+
+
+ // useful for debugging
+ // UNMAINTAINED
+ /*
+ if( writeReferencers ) {
+ OwnershipNode onRef = null;
+ Iterator refItr = hrn.iteratorToReferencers();
+ while( refItr.hasNext() ) {
+ onRef = (OwnershipNode) refItr.next();
+
+ switch( mode ) {
+ case VISIT_HRN_WRITE_FULL:
+ bw.write(" " + hrn.toString() +
+ " -> " + onRef.toString() +
+ "[color=lightgray];\n");
+ break;
+ }
+ }
+ }
+ */
+
+ Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
+ while( childRegionsItr.hasNext() ) {
+ ReferenceEdge edge = childRegionsItr.next();
+ HeapRegionNode hrnChild = edge.getDst();
+
+ switch( mode ) {
+ case VISIT_HRN_WRITE_FULL:
+ bw.write(" " + hrn.toString() +
+ " -> " + hrnChild.toString() +
+ "[label=\"" + edge.toGraphEdgeString() +
+ "\",decorate];\n");
+ break;
+ }
+
+ traverseHeapRegionNodes(mode,
+ hrnChild,
+ bw,
+ td,
+ visited,
+ writeReferencers);