--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/NegateObjectTypeFeedback.java	Wed Mar 14 17:55:33 2012 +0100
@@ -0,0 +1,70 @@
+/*
+ * 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.compiler.types;
+
+import com.oracle.max.cri.ci.*;
+import com.oracle.max.cri.ri.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.spi.types.*;
+
+
+public class NegateObjectTypeFeedback implements ObjectTypeFeedbackTool {
+
+    private final ObjectTypeFeedbackTool delegate;
+
+    public NegateObjectTypeFeedback(ObjectTypeFeedbackTool delegate) {
+        this.delegate = delegate;
+    }
+
+    @Override
+    public void constantBound(Condition condition, CiConstant constant) {
+        delegate.constantBound(condition.negate(), constant);
+    }
+
+    @Override
+    public void valueBound(Condition condition, ValueNode otherValue) {
+        delegate.valueBound(condition.negate(), otherValue);
+    }
+
+    @Override
+    public void declaredType(RiResolvedType type, boolean nonNull) {
+        delegate.notDeclaredType(type, nonNull);
+    }
+
+    @Override
+    public void exactType(RiResolvedType type) {
+        delegate.notExactType(type);
+    }
+
+    @Override
+    public void notDeclaredType(RiResolvedType type, boolean includesNull) {
+        delegate.declaredType(type, includesNull);
+    }
+
+    @Override
+    public void notExactType(RiResolvedType type) {
+        delegate.exactType(type);
+    }
+
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/NegateScalarTypeFeedback.java	Wed Mar 14 17:55:33 2012 +0100
@@ -0,0 +1,53 @@
+/*
+ * 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.compiler.types;
+
+import com.oracle.max.cri.ci.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.spi.types.*;
+
+
+public class NegateScalarTypeFeedback implements ScalarTypeFeedbackTool {
+
+    private final ScalarTypeFeedbackTool delegate;
+
+    public NegateScalarTypeFeedback(ScalarTypeFeedbackTool delegate) {
+        this.delegate = delegate;
+    }
+
+    @Override
+    public void constantBound(Condition condition, CiConstant constant) {
+        delegate.constantBound(condition.negate(), constant);
+    }
+
+    @Override
+    public void valueBound(Condition condition, ValueNode otherValue, ScalarTypeQuery type) {
+        delegate.valueBound(condition.negate(), otherValue, type);
+    }
+
+    @Override
+    public void setTranslated(CiConstant delta, ScalarTypeQuery old) {
+        throw new UnsupportedOperationException();
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/TypeFeedbackCache.java	Wed Mar 14 17:55:33 2012 +0100
@@ -0,0 +1,239 @@
+/*
+ * 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.compiler.types;
+
+import java.util.*;
+import java.util.Map.Entry;
+
+import com.oracle.max.cri.ci.*;
+import com.oracle.max.cri.ri.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.spi.types.*;
+import com.oracle.graal.nodes.type.*;
+
+public class TypeFeedbackCache implements TypeFeedbackTool, Cloneable {
+
+    public static final boolean NO_OBJECT_TYPES = false;
+    public static final boolean NO_SCALAR_TYPES = false;
+
+    private final RiRuntime runtime;
+    private final StructuredGraph graph;
+    private final HashMap<ValueNode, ScalarTypeFeedbackStore> scalarTypeFeedback;
+    private final HashMap<ValueNode, ObjectTypeFeedbackStore> objectTypeFeedback;
+    private final TypeFeedbackChanged changed;
+    private final boolean negated;
+
+    public TypeFeedbackCache(RiRuntime runtime, StructuredGraph graph, TypeFeedbackChanged changed) {
+        this.runtime = runtime;
+        this.graph = graph;
+        scalarTypeFeedback = new HashMap<>();
+        objectTypeFeedback = new HashMap<>();
+        negated = false;
+        this.changed = changed;
+    }
+
+    public TypeFeedbackCache(RiRuntime runtime, StructuredGraph graph, HashMap<ValueNode, ScalarTypeFeedbackStore> scalarTypeFeedback, HashMap<ValueNode, ObjectTypeFeedbackStore> objectTypeFeedback, boolean negated, TypeFeedbackChanged changed) {
+        this.runtime = runtime;
+        this.graph = graph;
+        this.scalarTypeFeedback = scalarTypeFeedback;
+        this.objectTypeFeedback = objectTypeFeedback;
+        this.negated = negated;
+        this.changed = changed;
+    }
+
+    @Override
+    public ScalarTypeFeedbackTool addScalar(ValueNode value) {
+        assert value.kind() == CiKind.Int || value.kind() == CiKind.Long || value.kind() == CiKind.Float || value.kind() == CiKind.Double;
+        ScalarTypeFeedbackStore result = scalarTypeFeedback.get(value);
+        if (result == null) {
+            if (value.stamp().scalarType() != null) {
+                result = value.stamp().scalarType().store().clone();
+            } else {
+                result = new ScalarTypeFeedbackStore(value.kind(), changed);
+            }
+            scalarTypeFeedback.put(value, result);
+        }
+        return negated ? new NegateScalarTypeFeedback(result) : result;
+    }
+
+    @Override
+    public ObjectTypeFeedbackTool addObject(ValueNode value) {
+        assert value.kind() == CiKind.Object;
+        ObjectTypeFeedbackStore result = objectTypeFeedback.get(value);
+        if (result == null) {
+            if (value.stamp().objectType() != null) {
+                result = value.stamp().objectType().store().clone();
+            } else {
+                result = new ObjectTypeFeedbackStore(changed);
+            }
+            objectTypeFeedback.put(value, result);
+        }
+        return negated ? new NegateObjectTypeFeedback(result) : result;
+    }
+
+    @Override
+    public TypeFeedbackTool negate() {
+        return new TypeFeedbackCache(runtime, graph, scalarTypeFeedback, objectTypeFeedback, !negated, changed);
+    }
+
+    @Override
+    public RiRuntime runtime() {
+        return runtime;
+    }
+
+    @Override
+    public TypeFeedbackCache clone() {
+        return new TypeFeedbackCache(runtime, graph, deepClone(scalarTypeFeedback), deepClone(objectTypeFeedback), negated, changed);
+    }
+
+    @SuppressWarnings("unchecked")
+    private static <KeyT, ValueT extends CloneableTypeFeedback> HashMap<KeyT, ValueT> deepClone(HashMap<KeyT, ValueT> map) {
+        HashMap<KeyT, ValueT> result = new HashMap<>();
+        for (Map.Entry<KeyT, ValueT> entry : map.entrySet()) {
+            if (entry.getValue() == null) {
+                System.out.println(entry.getKey());
+            } else {
+                result.put(entry.getKey(), (ValueT) entry.getValue().clone());
+            }
+        }
+        return result;
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder str = new StringBuilder().append("types [\n");
+        for (Map.Entry<ValueNode, ScalarTypeFeedbackStore> entry : scalarTypeFeedback.entrySet()) {
+            if (!entry.getValue().isEmpty()) {
+                str.append("    ").append(entry.getKey()).append(": ").append(entry.getValue()).append("\n");
+            }
+        }
+        for (Map.Entry<ValueNode, ObjectTypeFeedbackStore> entry : objectTypeFeedback.entrySet()) {
+            if (!entry.getValue().isEmpty()) {
+                str.append("    ").append(entry.getKey()).append(": ").append(entry.getValue()).append("\n");
+            }
+        }
+        str.setLength(str.length() - 1);
+        return str.append(" ]").toString();
+    }
+
+    public static TypeFeedbackCache meet(TypeFeedbackCache[] cacheList, Iterable<PhiNode> phis) {
+        TypeFeedbackCache result = new TypeFeedbackCache(cacheList[0].runtime, cacheList[0].graph, cacheList[0].changed);
+
+        for (int i = 1; i < cacheList.length; i++) {
+            assert result.runtime == cacheList[i].runtime;
+            assert !result.negated && !cacheList[i].negated : "cannot meet negated type feedback caches";
+        }
+
+        // meet the scalar types
+        for (Entry<ValueNode, ScalarTypeFeedbackStore> entry : cacheList[0].scalarTypeFeedback.entrySet()) {
+            ScalarTypeFeedbackStore[] types = new ScalarTypeFeedbackStore[cacheList.length];
+            for (int i = 0; i < cacheList.length; i++) {
+                types[i] = cacheList[i].scalarTypeFeedback.get(entry.getKey());
+            }
+            ScalarTypeFeedbackStore scalar = ScalarTypeFeedbackStore.meet(types);
+            if (scalar != null && !scalar.isEmpty()) {
+                result.scalarTypeFeedback.put(entry.getKey(), scalar);
+            }
+        }
+        // meet the object types
+        for (Entry<ValueNode, ObjectTypeFeedbackStore> entry : cacheList[0].objectTypeFeedback.entrySet()) {
+            ObjectTypeFeedbackStore[] types = new ObjectTypeFeedbackStore[cacheList.length];
+            for (int i = 0; i < cacheList.length; i++) {
+                types[i] = cacheList[i].objectTypeFeedback.get(entry.getKey());
+            }
+            ObjectTypeFeedbackStore object = ObjectTypeFeedbackStore.meet(types);
+            if (object != null && !object.isEmpty()) {
+                result.objectTypeFeedback.put(entry.getKey(), object);
+            }
+        }
+        // meet the phi nodes
+        for (PhiNode phi : phis) {
+            assert phi.valueCount() == cacheList.length;
+            if (phi.kind() == CiKind.Int || phi.kind() == CiKind.Long) {
+                ScalarTypeFeedbackStore[] types = new ScalarTypeFeedbackStore[phi.valueCount()];
+                for (int i = 0; i < phi.valueCount(); i++) {
+                    ScalarTypeFeedbackStore other = cacheList[i].scalarTypeFeedback.get(phi.valueAt(i));
+                    if (other == null && phi.valueAt(i).stamp().scalarType() != null) {
+                        other = phi.valueAt(i).stamp().scalarType().store();
+                    }
+                    types[i] = other;
+                }
+                ScalarTypeFeedbackStore scalar = ScalarTypeFeedbackStore.meet(types);
+                if (scalar != null && !scalar.isEmpty()) {
+                    result.scalarTypeFeedback.put(phi, scalar);
+                    phi.setStamp(StampFactory.forKind(phi.kind(), scalar.query(), null));
+                }
+            } else if (phi.kind() == CiKind.Object) {
+                ObjectTypeFeedbackStore[] types = new ObjectTypeFeedbackStore[phi.valueCount()];
+                for (int i = 0; i < phi.valueCount(); i++) {
+                    ObjectTypeFeedbackStore other = cacheList[i].objectTypeFeedback.get(phi.valueAt(i));
+                    if (other == null && phi.valueAt(i).stamp().objectType() != null) {
+                        other = phi.valueAt(i).stamp().objectType().store();
+                    }
+                    types[i] = other;
+                }
+                ObjectTypeFeedbackStore object = ObjectTypeFeedbackStore.meet(types);
+                if (object != null && !object.isEmpty()) {
+                    result.objectTypeFeedback.put(phi, object);
+                    phi.setStamp(StampFactory.forKind(phi.kind(), null, object.query()));
+                }
+            }
+        }
+        return result;
+    }
+
+    @Override
+    public ScalarTypeQuery queryScalar(ValueNode value) {
+        assert value.kind() == CiKind.Int || value.kind() == CiKind.Long || value.kind() == CiKind.Float || value.kind() == CiKind.Double;
+        if (NO_SCALAR_TYPES) {
+            return new ScalarTypeFeedbackStore(value.kind(), changed).query();
+        }
+        ScalarTypeFeedbackStore result = scalarTypeFeedback.get(value);
+        if (result == null) {
+            if (value.stamp().scalarType() != null) {
+                return value.stamp().scalarType();
+            }
+            result = new ScalarTypeFeedbackStore(value.kind(), changed);
+            scalarTypeFeedback.put(value, result);
+        }
+        return result.query();
+    }
+
+    @Override
+    public ObjectTypeQuery queryObject(ValueNode value) {
+        assert value != null;
+        assert value.kind() == CiKind.Object;
+        if (NO_OBJECT_TYPES) {
+            return new ObjectTypeFeedbackStore(changed).query();
+        }
+        ObjectTypeFeedbackStore result = objectTypeFeedback.get(value);
+        if (result == null) {
+            if (value.stamp().objectType() != null) {
+                return value.stamp().objectType();
+            }
+            result = new ObjectTypeFeedbackStore(changed);
+            objectTypeFeedback.put(value, result);
+        }
+        return result.query();
+    }
+}

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/Stamp.java	Wed Mar 14 17:50:59 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/Stamp.java	Wed Mar 14 17:55:33 2012 +0100
@@ -24,6 +24,7 @@
 
 import com.oracle.max.cri.ci.*;
 import com.oracle.max.cri.ri.*;
+import com.oracle.graal.nodes.spi.types.*;
 
 
 public interface Stamp {
@@ -32,4 +33,7 @@
     RiResolvedType exactType();
     CiKind kind();
     boolean alwaysDistinct(Stamp other);
+
+    ScalarTypeQuery scalarType();
+    ObjectTypeQuery objectType();
 }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java	Wed Mar 14 17:50:59 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java	Wed Mar 14 17:55:33 2012 +0100
@@ -26,6 +26,9 @@
 
 import com.oracle.max.cri.ci.*;
 import com.oracle.max.cri.ri.*;
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.spi.types.*;
 
 
 public class StampFactory {
@@ -36,16 +39,24 @@
         private final boolean nonNull;
         private RiResolvedType declaredType;
         private RiResolvedType exactType;
+        private final ScalarTypeQuery scalarType;
+        private final ObjectTypeQuery objectType;
 
         public BasicValueStamp(CiKind kind) {
             this(kind, false, null, null);
         }
 
         public BasicValueStamp(CiKind kind, boolean nonNull, RiResolvedType declaredType, RiResolvedType exactType) {
+            this(kind, nonNull, declaredType, exactType, null, null);
+        }
+
+        public BasicValueStamp(CiKind kind, boolean nonNull, RiResolvedType declaredType, RiResolvedType exactType, ScalarTypeQuery scalarType, ObjectTypeQuery objectType) {
             this.kind = kind;
             this.nonNull = nonNull;
             this.declaredType = declaredType;
             this.exactType = exactType;
+            this.scalarType = scalarType;
+            this.objectType = objectType;
         }
 
         @Override
@@ -87,7 +98,18 @@
 
         @Override
         public String toString() {
-            return String.format("%c%s %s %s", kind().typeChar, nonNull ? "!" : "", declaredType == null ? "-" : declaredType.name(), exactType == null ? "-" : exactType.name());
+            StringBuilder str = new StringBuilder();
+            str.append(kind().typeChar);
+            if (nonNull || declaredType != null || exactType != null) {
+                str.append(nonNull ? "!" : "").append(' ').append(declaredType == null ? "-" : declaredType.name()).append(' ').append(exactType == null ? "-" : exactType.name());
+            }
+            if (scalarType != null) {
+                str.append(' ').append(scalarType);
+            }
+            if (objectType != null) {
+                str.append(' ').append(objectType);
+            }
+            return str.toString();
         }
 
         @Override
@@ -107,6 +129,16 @@
                 return false;
             }
         }
+
+        @Override
+        public ScalarTypeQuery scalarType() {
+            return scalarType;
+        }
+
+        @Override
+        public ObjectTypeQuery objectType() {
+            return objectType;
+        }
     }
 
     private static final Stamp[] stampCache = new Stamp[CiKind.values().length];
@@ -128,17 +160,68 @@
         return stampCache[kind.stackKind().ordinal()];
     }
 
+    public static Stamp forKind(CiKind kind, ScalarTypeQuery scalarTypeFeedback, ObjectTypeQuery objectTypeFeedback) {
+        if (scalarTypeFeedback == null && objectTypeFeedback == null) {
+            return forKind(kind);
+        } else {
+            return new BasicValueStamp(kind, false, null, null, scalarTypeFeedback, objectTypeFeedback);
+        }
+    }
+
+    public static final Stamp positiveInt = forInt(0, Integer.MAX_VALUE);
+
+    public static Stamp positiveInt() {
+        return positiveInt;
+    }
+
+    public static Stamp forInt(int lowerBound, int upperBound) {
+        ScalarTypeFeedbackStore scalarType = new ScalarTypeFeedbackStore(CiKind.Int, new TypeFeedbackChanged());
+        scalarType.constantBound(Condition.GE, CiConstant.forInt(lowerBound));
+        scalarType.constantBound(Condition.LE, CiConstant.forInt(upperBound));
+
+        return new BasicValueStamp(CiKind.Int, false, null, null, scalarType.query(), null);
+    }
+
+    public static Stamp forLong(long lowerBound, long upperBound) {
+        ScalarTypeFeedbackStore scalarType = new ScalarTypeFeedbackStore(CiKind.Long, new TypeFeedbackChanged());
+        scalarType.constantBound(Condition.GE, CiConstant.forLong(lowerBound));
+        scalarType.constantBound(Condition.LE, CiConstant.forLong(upperBound));
+
+        return new BasicValueStamp(CiKind.Long, false, null, null, scalarType.query(), null);
+    }
+
     public static Stamp exactNonNull(final RiResolvedType type) {
         // (cwimmer) type can be null for certain Maxine-internal objects such as the static hub. Is this a problem here?
         assert type == null || type.kind(false) == CiKind.Object;
-        return new BasicValueStamp(CiKind.Object, true, type, type);
+        ObjectTypeFeedbackStore objectType = new ObjectTypeFeedbackStore(new TypeFeedbackChanged());
+        objectType.constantBound(Condition.NE, CiConstant.NULL_OBJECT);
+        objectType.exactType(type);
+        return new BasicValueStamp(CiKind.Object, true, type, type, null, objectType.query());
+    }
+
+    public static Stamp forConstant(CiConstant value) {
+        assert value.kind != CiKind.Object;
+        if (value.kind == CiKind.Object) {
+            throw new GraalInternalError("unexpected kind: %s", value.kind);
+        } else {
+            if (value.kind == CiKind.Int) {
+                return forInt(value.asInt(), value.asInt());
+            } else if (value.kind == CiKind.Long) {
+                return forLong(value.asLong(), value.asLong());
+            }
+            return forKind(value.kind.stackKind());
+        }
     }
 
     public static Stamp forConstant(CiConstant value, RiRuntime runtime) {
-        if (runtime != null && value.kind == CiKind.Object && !value.isNull()) {
-            return exactNonNull(runtime.getTypeOf(value));
+        assert value.kind == CiKind.Object;
+        if (value.kind == CiKind.Object) {
+            ObjectTypeFeedbackStore objectType = new ObjectTypeFeedbackStore(new TypeFeedbackChanged());
+            objectType.constantBound(Condition.EQ, value);
+            RiResolvedType type = value.isNull() ? null : runtime.getTypeOf(value);
+            return new BasicValueStamp(CiKind.Object, value.isNonNull(), type, type, null, objectType.query());
         } else {
-            return forKind(value.kind.stackKind());
+            throw new GraalInternalError("CiKind.Object expected, actual kind: %s", value.kind);
         }
     }