# HG changeset patch
# User Lukas Stadler <lukas.stadler@jku.at>
# Date 1331743859 -3600
# Node ID 1093243c09ad44f3581618078a4de34a3b90f92e
# Parent  f29e75070bb6d1a0d7aeae37de4502742c6e47b0
experimental type storage/query infrastructure, part 3:
split/conditional type feedback, type canonicalization

diff -r f29e75070bb6 -r 1093243c09ad 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	Wed Mar 14 17:46:39 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Wed Mar 14 17:50:59 2012 +0100
@@ -26,13 +26,14 @@
 
 import com.oracle.max.cri.ci.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.spi.types.*;
 import com.oracle.graal.nodes.type.*;
 
 /**
  * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome of a
  * comparison.
  */
-public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable {
+public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable, SplitTypeFeedbackProvider {
     public static final int TRUE_EDGE = 0;
     public static final int FALSE_EDGE = 1;
 
@@ -176,4 +177,11 @@
         falseEnd.safeDelete();
         tool.addToWorkList(next);
     }
+
+    @Override
+    public void typeFeedback(int blockSuccessor, TypeFeedbackTool tool) {
+        if (compare instanceof ConditionalTypeFeedbackProvider) {
+            ((ConditionalTypeFeedbackProvider) compare).typeFeedback(blockSuccessor == TRUE_EDGE ? tool : tool.negate());
+        }
+    }
 }
diff -r f29e75070bb6 -r 1093243c09ad graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java	Wed Mar 14 17:46:39 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java	Wed Mar 14 17:50:59 2012 +0100
@@ -26,6 +26,7 @@
 import com.oracle.max.cri.ri.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.spi.types.*;
 import com.oracle.graal.nodes.type.*;
 
 /* TODO (thomaswue/gdub) For high-level optimization purpose the compare node should be a boolean *value* (it is currently only a helper node)
@@ -34,7 +35,7 @@
  * Compare should probably be made a value (so that it can be canonicalized for example) and in later stages some Compare usage should be transformed
  * into variants that do not materialize the value (CompareIf, CompareGuard...)
  */
-public final class CompareNode extends BooleanNode implements Canonicalizable, LIRLowerable {
+public final class CompareNode extends BooleanNode implements Canonicalizable, LIRLowerable, ConditionalTypeFeedbackProvider, TypeCanonicalizable {
 
     @Input private ValueNode x;
     @Input private ValueNode y;
@@ -197,4 +198,108 @@
         }
         return this;
     }
+
+    @Override
+    public void typeFeedback(TypeFeedbackTool tool) {
+        CiKind kind = x().kind();
+        assert y().kind() == kind;
+        if (kind == CiKind.Object) {
+            assert condition == Condition.EQ || condition == Condition.NE;
+            if (y().isConstant() && !x().isConstant()) {
+                tool.addObject(x()).constantBound(condition, y().asConstant());
+            } else if (x().isConstant() && !y().isConstant()) {
+                tool.addObject(y()).constantBound(condition.mirror(), x().asConstant());
+            } else if (!x().isConstant() && !y.isConstant()) {
+                tool.addObject(x()).valueBound(condition, y());
+                tool.addObject(y()).valueBound(condition.mirror(), x());
+            } else {
+                // both are constant, this should be canonicalized...
+            }
+        } else if (kind == CiKind.Int || kind == CiKind.Long) {
+            assert condition != Condition.NOF && condition != Condition.OF;
+            if (y().isConstant() && !x().isConstant()) {
+                tool.addScalar(x()).constantBound(condition, y().asConstant());
+            } else if (x().isConstant() && !y().isConstant()) {
+                tool.addScalar(y()).constantBound(condition.mirror(), x().asConstant());
+            } else if (!x().isConstant() && !y.isConstant()) {
+                tool.addScalar(x()).valueBound(condition, y(), tool.queryScalar(y()));
+                tool.addScalar(y()).valueBound(condition.mirror(), x(), tool.queryScalar(x()));
+            } else {
+                // both are constant, this should be canonicalized...
+            }
+        } else if (kind == CiKind.Float || kind == CiKind.Double) {
+            // nothing yet...
+        }
+    }
+
+    @Override
+    public Result canonical(TypeFeedbackTool tool) {
+        CiKind kind = x().kind();
+        if (kind == CiKind.Int || kind == CiKind.Long) {
+            assert condition != Condition.NOF && condition != Condition.OF;
+            ScalarTypeQuery queryX = tool.queryScalar(x());
+            if (y().isConstant() && !x().isConstant()) {
+                if (queryX.constantBound(condition, y().asConstant())) {
+                    return new Result(ConstantNode.forBoolean(true, graph()), queryX);
+                } else if (queryX.constantBound(condition.negate(), y().asConstant())) {
+                    return new Result(ConstantNode.forBoolean(false, graph()), queryX);
+                }
+            } else {
+                ScalarTypeQuery queryY = tool.queryScalar(y());
+                if (x().isConstant() && !y().isConstant()) {
+                    if (queryY.constantBound(condition.mirror(), x().asConstant())) {
+                        return new Result(ConstantNode.forBoolean(true, graph()), queryY);
+                    } else if (queryY.constantBound(condition.mirror().negate(), x().asConstant())) {
+                        return new Result(ConstantNode.forBoolean(false, graph()), queryY);
+                    }
+                } else if (!x().isConstant() && !y.isConstant()) {
+                    if (condition == Condition.BT || condition == Condition.BE) {
+                        if (queryY.constantBound(Condition.GE, new CiConstant(kind, 0))) {
+                            if (queryX.constantBound(Condition.GE, new CiConstant(kind, 0))) {
+                                if (queryX.valueBound(condition == Condition.BT ? Condition.LT : Condition.LE, y())) {
+                                    return new Result(ConstantNode.forBoolean(true, graph()), queryX, queryY);
+                                }
+                            }
+                        }
+                    }
+
+                    if (queryX.valueBound(condition, y())) {
+                        return new Result(ConstantNode.forBoolean(true, graph()), queryX);
+                    } else if (queryX.valueBound(condition.negate(), y())) {
+                        return new Result(ConstantNode.forBoolean(false, graph()), queryX);
+                    }
+                } else {
+                    // both are constant, this should be canonicalized...
+                }
+            }
+        } else  if (kind == CiKind.Object) {
+            assert condition == Condition.EQ || condition == Condition.NE;
+            ObjectTypeQuery queryX = tool.queryObject(x());
+            if (y().isConstant() && !x().isConstant()) {
+                if (queryX.constantBound(condition, y().asConstant())) {
+                    return new Result(ConstantNode.forBoolean(true, graph()), queryX);
+                } else if (queryX.constantBound(condition.negate(), y().asConstant())) {
+                    return new Result(ConstantNode.forBoolean(false, graph()), queryX);
+                }
+            } else {
+                ObjectTypeQuery queryY = tool.queryObject(y());
+                if (x().isConstant() && !y().isConstant()) {
+                    if (queryY.constantBound(condition.mirror(), x().asConstant())) {
+                        return new Result(ConstantNode.forBoolean(true, graph()), queryY);
+                    } else if (queryY.constantBound(condition.mirror().negate(), x().asConstant())) {
+                        return new Result(ConstantNode.forBoolean(false, graph()), queryY);
+                    }
+                } else if (!x().isConstant() && !y.isConstant()) {
+                    if (queryX.valueBound(condition, y())) {
+                        return new Result(ConstantNode.forBoolean(true, graph()), queryX);
+                    } else if (queryX.valueBound(condition.negate(), y())) {
+                        return new Result(ConstantNode.forBoolean(false, graph()), queryX);
+                    }
+                } else {
+                    // both are constant, this should be canonicalized...
+                }
+            }
+        }
+        return null;
+    }
 }
diff -r f29e75070bb6 -r 1093243c09ad graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NullCheckNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NullCheckNode.java	Wed Mar 14 17:46:39 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NullCheckNode.java	Wed Mar 14 17:50:59 2012 +0100
@@ -25,9 +25,10 @@
 import com.oracle.max.cri.ci.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.spi.types.*;
 import com.oracle.graal.nodes.type.*;
 
-public final class NullCheckNode extends BooleanNode implements Canonicalizable, LIRLowerable {
+public final class NullCheckNode extends BooleanNode implements Canonicalizable, LIRLowerable, ConditionalTypeFeedbackProvider, TypeCanonicalizable {
 
     @Input private ValueNode object;
     @Data public final boolean expectedNull;
@@ -77,4 +78,22 @@
     public BooleanNode negate() {
         return graph().unique(new NullCheckNode(object(), !expectedNull));
     }
+
+    @Override
+    public void typeFeedback(TypeFeedbackTool tool) {
+        Condition expectedCondition = expectedNull ? Condition.EQ : Condition.NE;
+        tool.addObject(object()).constantBound(expectedCondition, CiConstant.NULL_OBJECT);
+    }
+
+    @Override
+    public Result canonical(TypeFeedbackTool tool) {
+        Condition expectedCondition = expectedNull ? Condition.EQ : Condition.NE;
+        ObjectTypeQuery query = tool.queryObject(object());
+        if (query.constantBound(expectedCondition, CiConstant.NULL_OBJECT)) {
+            return new Result(ConstantNode.forBoolean(true, graph()), query);
+        } else if (query.constantBound(expectedCondition.negate(), CiConstant.NULL_OBJECT)) {
+            return new Result(ConstantNode.forBoolean(false, graph()), query);
+        }
+        return null;
+    }
 }
diff -r f29e75070bb6 -r 1093243c09ad graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java	Wed Mar 14 17:46:39 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java	Wed Mar 14 17:50:59 2012 +0100
@@ -22,20 +22,22 @@
  */
 package com.oracle.graal.nodes.java;
 
-import com.oracle.max.cri.ci.*;
-import com.oracle.max.cri.ri.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.extended.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.spi.types.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.max.cri.ci.*;
+import com.oracle.max.cri.ri.*;
 
 /**
  * The {@code CheckCastNode} represents a {@link Bytecodes#CHECKCAST}.
  *
  * The {@link #targetClass()} of a CheckCastNode can be null for array store checks!
  */
-public final class CheckCastNode extends TypeCheckNode implements Canonicalizable, LIRLowerable, Node.IterableNodeType {
+public final class CheckCastNode extends TypeCheckNode implements Canonicalizable, LIRLowerable, Node.IterableNodeType, TypeFeedbackProvider, TypeCanonicalizable {
 
     @Input protected final FixedNode anchor;
     @Data  protected final boolean emitCode;
@@ -116,4 +118,24 @@
     public BooleanNode negate() {
         throw new Error("A CheckCast does not produce a boolean value, so it should actually not be a subclass of BooleanNode");
     }
+
+    @Override
+    public void typeFeedback(TypeFeedbackTool tool) {
+        if (targetClass() != null) {
+            tool.addObject(object()).declaredType(targetClass(), false);
+        }
+    }
+
+    @Override
+    public Result canonical(TypeFeedbackTool tool) {
+        ObjectTypeQuery query = tool.queryObject(object());
+        if (query.constantBound(Condition.EQ, CiConstant.NULL_OBJECT)) {
+            return new Result(object(), query);
+        } else if (targetClass() != null) {
+            if (query.declaredType(targetClass())) {
+                return new Result(object(), query);
+            }
+        }
+        return null;
+    }
 }
diff -r f29e75070bb6 -r 1093243c09ad graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java	Wed Mar 14 17:46:39 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java	Wed Mar 14 17:50:59 2012 +0100
@@ -27,12 +27,13 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.spi.types.*;
 import com.oracle.graal.nodes.type.*;
 
 /**
  * The {@code InstanceOfNode} represents an instanceof test.
  */
-public final class InstanceOfNode extends TypeCheckNode implements Canonicalizable, LIRLowerable {
+public final class InstanceOfNode extends TypeCheckNode implements Canonicalizable, LIRLowerable, ConditionalTypeFeedbackProvider, TypeCanonicalizable {
 
     @Data private final boolean negated;
 
@@ -97,4 +98,31 @@
     public BooleanNode negate() {
         return graph().unique(new InstanceOfNode(targetClassInstruction(), targetClass(), object(), hints(), hintsExact(), !negated));
     }
+
+    @Override
+    public void typeFeedback(TypeFeedbackTool tool) {
+        if (negated) {
+            tool.addObject(object()).notDeclaredType(targetClass(), true);
+        } else {
+            tool.addObject(object()).declaredType(targetClass(), true);
+        }
+    }
+
+    @Override
+    public Result canonical(TypeFeedbackTool tool) {
+        ObjectTypeQuery query = tool.queryObject(object());
+        if (query.constantBound(Condition.EQ, CiConstant.NULL_OBJECT)) {
+            return new Result(ConstantNode.forBoolean(negated, graph()), query);
+        } else if (targetClass() != null) {
+            if (query.notDeclaredType(targetClass())) {
+                return new Result(ConstantNode.forBoolean(negated, graph()), query);
+            }
+            if (query.constantBound(Condition.NE, CiConstant.NULL_OBJECT)) {
+                if (query.declaredType(targetClass())) {
+                    return new Result(ConstantNode.forBoolean(!negated, graph()), query);
+                }
+            }
+        }
+        return null;
+    }
 }
diff -r f29e75070bb6 -r 1093243c09ad graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ConditionalTypeFeedbackProvider.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ConditionalTypeFeedbackProvider.java	Wed Mar 14 17:50:59 2012 +0100
@@ -0,0 +1,28 @@
+/*
+ * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.nodes.spi.types;
+
+public interface ConditionalTypeFeedbackProvider {
+
+    void typeFeedback(TypeFeedbackTool tool);
+}
diff -r f29e75070bb6 -r 1093243c09ad graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/SplitTypeFeedbackProvider.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/SplitTypeFeedbackProvider.java	Wed Mar 14 17:50:59 2012 +0100
@@ -0,0 +1,28 @@
+/*
+ * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.nodes.spi.types;
+
+public interface SplitTypeFeedbackProvider {
+
+    void typeFeedback(int blockSuccessor, TypeFeedbackTool tool);
+}
diff -r f29e75070bb6 -r 1093243c09ad graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeCanonicalizable.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeCanonicalizable.java	Wed Mar 14 17:50:59 2012 +0100
@@ -0,0 +1,79 @@
+/*
+ * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.nodes.spi.types;
+
+import java.util.*;
+
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.*;
+
+public interface TypeCanonicalizable {
+
+    Node[] EMPTY_ARRAY = new Node[0];
+
+    public static class Result {
+        public final ValueNode replacement;
+        public final Node[] dependencies;
+
+        public Result(ValueNode replacement) {
+            this.replacement = replacement;
+            this.dependencies = EMPTY_ARRAY;
+        }
+
+        public Result(ValueNode replacement, TypeQuery query) {
+            assert query != null;
+            this.replacement = replacement;
+            if (query.dependency() != null) {
+                this.dependencies = new Node[] {query.dependency()};
+            } else {
+                this.dependencies = EMPTY_ARRAY;
+            }
+        }
+
+        public Result(ValueNode replacement, TypeQuery... queries) {
+            this.replacement = replacement;
+            HashSet<Node> deps = new HashSet<>();
+            for (TypeQuery query : queries) {
+                if (query.dependency() != null) {
+                    deps.add(query.dependency());
+                }
+            }
+            this.dependencies = deps.toArray(new Node[deps.size()]);
+        }
+
+        @Override
+        public String toString() {
+            StringBuilder str = new StringBuilder().append('[');
+            str.append(replacement);
+            if (dependencies.length > 0) {
+                str.append(" @");
+                for (Node dep : dependencies) {
+                    str.append(' ').append(dep);
+                }
+            }
+            return str.append(']').toString();
+        }
+    }
+
+    Result canonical(TypeFeedbackTool tool);
+}
diff -r f29e75070bb6 -r 1093243c09ad graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeFeedbackTool.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeFeedbackTool.java	Wed Mar 14 17:46:39 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeFeedbackTool.java	Wed Mar 14 17:50:59 2012 +0100
@@ -23,7 +23,6 @@
 package com.oracle.graal.nodes.spi.types;
 
 import com.oracle.max.cri.ri.*;
-import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 
 public interface TypeFeedbackTool {