# HG changeset patch # User Doug Simon # Date 1412252536 -7200 # Node ID e6e678c3818fed24646ae80894f655b05ac8fe4a # Parent 979bf76f0fe35157795437432a3ce4083c279040 only generate data fields equality method for leaf ValueNumberable nodes; no longer generate Node.isLeafNode() diff -r 979bf76f0fe3 -r e6e678c3818f graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Thu Oct 02 13:13:00 2014 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Thu Oct 02 14:22:16 2014 +0200 @@ -78,7 +78,12 @@ int compressions; NodeEventListener nodeEventListener; - private final HashMap cachedNodes = new HashMap<>(); + + /** + * Used to global value number {@link ValueNumberable} {@linkplain NodeClass#isLeafNode() leaf} + * nodes. + */ + private final HashMap cachedLeafNodes = new HashMap<>(); /* * Indicates that the graph should no longer be modified. Frozen graphs can be used my multiple @@ -86,19 +91,22 @@ */ private boolean isFrozen = false; + /** + * Entry in {@link Graph#cachedLeafNodes}. + */ private static final class CacheEntry { private final Node node; public CacheEntry(Node node) { - assert node instanceof ValueNumberable; - assert node.isLeafNode(); + assert node.getNodeClass().valueNumberable(); + assert node.getNodeClass().isLeafNode(); this.node = node; } @Override public int hashCode() { - return Node.USE_GENERATED_NODES ? node.getValueNumber() : node.getNodeClass().valueNumber(node); + return Node.USE_GENERATED_NODES ? node.valueNumberLeaf() : node.getNodeClass().valueNumber(node); } @Override @@ -446,7 +454,7 @@ return (T) other; } else { Node result = addIfMissing ? addHelper(node) : node; - if (node.isLeafNode()) { + if (node.getNodeClass().isLeafNode()) { putNodeIntoCache(result); } return (T) result; @@ -456,15 +464,15 @@ void putNodeIntoCache(Node node) { assert node.graph() == this || node.graph() == null; assert node.getNodeClass().valueNumberable(); - assert node.isLeafNode() : node.getClass(); - cachedNodes.put(new CacheEntry(node), node); + assert node.getNodeClass().isLeafNode() : node.getClass(); + cachedLeafNodes.put(new CacheEntry(node), node); } Node findNodeInCache(Node node) { CacheEntry key = new CacheEntry(node); - Node result = cachedNodes.get(key); + Node result = cachedLeafNodes.get(key); if (result != null && result.isDeleted()) { - cachedNodes.remove(key); + cachedLeafNodes.remove(key); return null; } return result; @@ -473,7 +481,8 @@ public Node findDuplicate(Node node) { NodeClass nodeClass = node.getNodeClass(); assert nodeClass.valueNumberable(); - if (node.isLeafNode()) { + if (nodeClass.isLeafNode()) { + // Leaf node: look up in cache Node cachedNode = findNodeInCache(node); if (cachedNode != null) { return cachedNode; @@ -481,6 +490,10 @@ return null; } } else { + // Non-leaf node: look for another usage of the node's inputs that + // has the same data, inputs and successors as the node. To reduce + // the cost of this computation, only the input with estimated highest + // usage count is considered. int minCount = Integer.MAX_VALUE; Node minCountNode = null; diff -r 979bf76f0fe3 -r e6e678c3818f graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java Thu Oct 02 13:13:00 2014 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java Thu Oct 02 14:22:16 2014 +0200 @@ -143,6 +143,14 @@ boolean setStampFromReturnType() default false; } + /** + * Marker for a node that can be replaced by another node via global value numbering. A + * {@linkplain NodeClass#isLeafNode() leaf} node can be replaced by another node of the same + * type that has exactly the same {@linkplain NodeClass#getData() data} values. A non-leaf node + * can be replaced by another node of the same type that has exactly the same data values as + * well as the same {@linkplain Node#inputs() inputs} and {@linkplain Node#successors() + * successors}. + */ public interface ValueNumberable { } @@ -739,7 +747,7 @@ final Node clone(Graph into, boolean clearInputsAndSuccessors) { NodeClass nodeClass = getNodeClass(); - if (into != null && nodeClass.valueNumberable() && isLeafNode()) { + if (into != null && nodeClass.valueNumberable() && nodeClass.isLeafNode()) { Node otherNode = into.findNodeInCache(this); if (otherNode != null) { return otherNode; @@ -767,20 +775,13 @@ newNode.extraUsages = NO_NODES; newNode.predecessor = null; - if (into != null && nodeClass.valueNumberable() && isLeafNode()) { + if (into != null && nodeClass.valueNumberable() && nodeClass.isLeafNode()) { into.putNodeIntoCache(newNode); } newNode.afterClone(this); return newNode; } - /** - * @returns true if this node has no inputs and no successors - */ - public boolean isLeafNode() { - return USE_GENERATED_NODES || getNodeClass().isLeafNode(); - } - protected void afterClone(@SuppressWarnings("unused") Node other) { } @@ -996,14 +997,13 @@ } /** - * If this node is {@link ValueNumberable}, gets a digest for this node based on the current - * value of it's {@link NodeClass#getData() data} fields. If this node is not - * {@link ValueNumberable}, 0 is returned. + * If this node is a {@linkplain NodeClass#isLeafNode() leaf} node, returns a hash for this node + * based on its {@linkplain NodeClass#getData() data} fields otherwise return 0. * - * Overridden by a method generated for {@link ValueNumberable} subclasses. + * Overridden by a method generated for leaf nodes. */ - public int getValueNumber() { - assert !(this instanceof ValueNumberable); + protected int valueNumberLeaf() { + assert !getNodeClass().isLeafNode(); return 0; } @@ -1012,7 +1012,7 @@ * * @param other */ - protected boolean valueEqualsGen(Node other) { + protected boolean dataEquals(Node other) { return true; } @@ -1021,13 +1021,12 @@ * fields of another node of the same type. Primitive fields are compared by value and * non-primitive fields are compared by {@link Objects#equals(Object, Object)}. * - * The result of this method undefined if {@code other.getClass() != this.getClass()} or if this - * node is not {@link ValueNumberable} + * The result of this method undefined if {@code other.getClass() != this.getClass()}. * * @param other a node of exactly the same type as this node * @return true if the data fields of this object and {@code other} are equal */ public boolean valueEquals(Node other) { - return USE_GENERATED_NODES ? valueEqualsGen(other) : getNodeClass().valueEqual(this, other); + return USE_GENERATED_NODES ? dataEquals(other) : getNodeClass().dataEquals(this, other); } } diff -r 979bf76f0fe3 -r e6e678c3818f graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Thu Oct 02 13:13:00 2014 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Thu Oct 02 14:22:16 2014 +0200 @@ -553,7 +553,7 @@ return eq; } - public boolean valueEqual(Node a, Node b) { + public boolean dataEquals(Node a, Node b) { assert a.getClass() == b.getClass(); for (int i = 0; i < data.getCount(); ++i) { Class type = data.getType(i); @@ -827,6 +827,9 @@ } } + /** + * @returns true if the node has no inputs and no successors + */ public boolean isLeafNode() { return isLeafNode; } diff -r 979bf76f0fe3 -r e6e678c3818f graal/com.oracle.graal.nodeinfo.processor/src/com/oracle/graal/nodeinfo/processor/GraphNodeGenerator.java --- a/graal/com.oracle.graal.nodeinfo.processor/src/com/oracle/graal/nodeinfo/processor/GraphNodeGenerator.java Thu Oct 02 13:13:00 2014 +0200 +++ b/graal/com.oracle.graal.nodeinfo.processor/src/com/oracle/graal/nodeinfo/processor/GraphNodeGenerator.java Thu Oct 02 14:22:16 2014 +0200 @@ -334,12 +334,12 @@ boolean hasInputs = !inputFields.isEmpty() || !inputListFields.isEmpty(); boolean hasSuccessors = !successorFields.isEmpty() || !successorListFields.isEmpty(); - if (hasInputs || hasSuccessors) { - createIsLeafNodeMethod(); + boolean isLeaf = !(hasInputs || hasSuccessors); + + if (isLeaf && isAssignableWithErasure(node, ValueNumberable)) { + createValueNumberLeafMethod(node); } - - createValueNumberMethod(node); - createValueEqualsMethod(); + createDataEqualsMethod(); } compilationUnit.add(genClass); return compilationUnit; @@ -430,65 +430,56 @@ } } - private void createIsLeafNodeMethod() { - CodeExecutableElement method = new CodeExecutableElement(modifiers(PUBLIC), getType(boolean.class), "isLeafNode"); - method.createBuilder().startReturn().string("false").end(); + private void createValueNumberLeafMethod(TypeElement node) { + CodeExecutableElement method = new CodeExecutableElement(modifiers(PUBLIC), getType(int.class), "valueNumberLeaf"); + CodeTreeBuilder b = method.createBuilder(); + b.startStatement().string("int number = " + node.hashCode()).end(); + for (VariableElement f : dataFields) { + String fname = f.getSimpleName().toString(); + switch (f.asType().getKind()) { + case BOOLEAN: + b.startIf().string(fname).end().startBlock(); + b.startStatement().string("number += 7").end(); + b.end(); + break; + case BYTE: + case SHORT: + case CHAR: + case INT: + b.startStatement().string("number += 13 * ", fname).end(); + break; + case FLOAT: + b.startStatement().string("number += 17 * Float.floatToRawIntBits(", fname, ")").end(); + break; + case LONG: + b.startStatement().string("number += 19 * ", fname + " ^ (", fname, " >>> 32)").end(); + break; + case DOUBLE: + b.startStatement().string("long longValue = Double.doubleToRawLongBits(", fname, ")").end(); + b.startStatement().string("number += 23 * longValue ^ (longValue >>> 32)").end(); + break; + case ARRAY: + if (((ArrayType) f.asType()).getComponentType().getKind().isPrimitive()) { + b.startStatement().string("number += 31 * Arrays.hashCode(", fname, ")").end(); + } else { + b.startStatement().string("number += 31 * Arrays.deepHashCode(", fname, ")").end(); + } + break; + default: + b.startIf().string(fname, " != null").end().startBlock(); + b.startStatement().string("number += 29 * ", fname + ".hashCode()").end(); + b.end(); + break; + } + } + b.end(); + b.startReturn().string("number").end(); genClass.add(method); checkOnlyInGenNode(method); } - private void createValueNumberMethod(TypeElement node) { - if (isAssignableWithErasure(node, ValueNumberable)) { - CodeExecutableElement method = new CodeExecutableElement(modifiers(PUBLIC), getType(int.class), "getValueNumber"); - CodeTreeBuilder b = method.createBuilder(); - b.startStatement().string("int number = " + node.hashCode()).end(); - for (VariableElement f : dataFields) { - String fname = f.getSimpleName().toString(); - switch (f.asType().getKind()) { - case BOOLEAN: - b.startIf().string(fname).end().startBlock(); - b.startStatement().string("number += 7").end(); - b.end(); - break; - case BYTE: - case SHORT: - case CHAR: - case INT: - b.startStatement().string("number += 13 * ", fname).end(); - break; - case FLOAT: - b.startStatement().string("number += 17 * Float.floatToRawIntBits(", fname, ")").end(); - break; - case LONG: - b.startStatement().string("number += 19 * ", fname + " ^ (", fname, " >>> 32)").end(); - break; - case DOUBLE: - b.startStatement().string("long longValue = Double.doubleToRawLongBits(", fname, ")").end(); - b.startStatement().string("number += 23 * longValue ^ (longValue >>> 32)").end(); - break; - case ARRAY: - if (((ArrayType) f.asType()).getComponentType().getKind().isPrimitive()) { - b.startStatement().string("number += 31 * Arrays.hashCode(", fname, ")").end(); - } else { - b.startStatement().string("number += 31 * Arrays.deepHashCode(", fname, ")").end(); - } - break; - default: - b.startIf().string(fname, " != null").end().startBlock(); - b.startStatement().string("number += 29 * ", fname + ".hashCode()").end(); - b.end(); - break; - } - } - b.end(); - b.startReturn().string("number").end(); - genClass.add(method); - checkOnlyInGenNode(method); - } - } - - private void createValueEqualsMethod() { - CodeExecutableElement method = new CodeExecutableElement(modifiers(PUBLIC), getType(boolean.class), "valueEqualsGen"); + private void createDataEqualsMethod() { + CodeExecutableElement method = new CodeExecutableElement(modifiers(PUBLIC), getType(boolean.class), "dataEquals"); addParameter(method, Node.asType(), "other"); CodeTreeBuilder b = method.createBuilder(); if (!dataFields.isEmpty()) { diff -r 979bf76f0fe3 -r e6e678c3818f graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Thu Oct 02 13:13:00 2014 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Thu Oct 02 14:22:16 2014 +0200 @@ -235,7 +235,8 @@ graph().addBeforeFixed(this, trueNext); for (Node usage : trueNext.usages().snapshot()) { if (usage.isAlive()) { - if (usage.getNodeClass().valueNumberable() && !usage.isLeafNode()) { + NodeClass usageNodeClass = usage.getNodeClass(); + if (usageNodeClass.valueNumberable() && !usageNodeClass.isLeafNode()) { Node newNode = graph().findDuplicate(usage); if (newNode != null) { usage.replaceAtUsages(newNode); diff -r 979bf76f0fe3 -r e6e678c3818f graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java Thu Oct 02 13:13:00 2014 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java Thu Oct 02 14:22:16 2014 +0200 @@ -213,7 +213,7 @@ } public static boolean tryGlobalValueNumbering(Node node, NodeClass nodeClass) { - if (nodeClass.valueNumberable() && !node.isLeafNode()) { + if (nodeClass.valueNumberable() && !nodeClass.isLeafNode()) { Node newNode = node.graph().findDuplicate(node); if (newNode != null) { assert !(node instanceof FixedNode || newNode instanceof FixedNode);