changeset 5118:e5427faad192

Merge
author Christian Haeubl <christian.haeubl@oracle.com>
date Mon, 19 Mar 2012 15:51:49 -0700
parents b6d1ba51d163 09f638813477
children 352a95d5031c
files GRAAL_README graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ConvertDeoptimizeToGuardPhase.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/EscapeAnalysisPhase.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/PropagateTypesPhase.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/ri/HotSpotRuntime.java graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedGuardNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GuardNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SafeReadNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SafeWriteNode.java graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/GraphTest.java
diffstat 81 files changed, 3187 insertions(+), 483 deletions(-) [+]
line wrap: on
line diff
--- a/.hgignore	Mon Mar 19 15:47:35 2012 -0700
+++ b/.hgignore	Mon Mar 19 15:51:49 2012 -0700
@@ -1,4 +1,5 @@
 ^mx/env
+^mx/ecj.jar
 ^mx/includes
 ^build/
 ^dist/
@@ -49,5 +50,6 @@
 ^visualizer/build/
 ^visualizer/dist/
 ^visualizer/nbplatform/
+^src/share/tools/IdealGraphVisualizer/nbplatform/
 ^.hgtip
 .DS_Store
--- a/GRAAL_README	Mon Mar 19 15:47:35 2012 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,24 +0,0 @@
-For creating a Graal VM JDK, the file jre\lib\jvm.cfg has to be modified such that it includes the line:
--graal KNOWN
-
-Before running the Graal VM, the following environment variables is needed:
-- MAXINE: Pointing to a Maxine VM repository with compiled Java files.
-
-In particular, the VM will look for the compiled Java files in the following directories:
-${MAXINE}/com.oracle.max.cri/bin
-${MAXINE}/com.oracle.max.base/bin
-${MAXINE}/com.oracle.max.asmdis/bin
-${MAXINE}/com.oracle.max.asm/bin
-${MAXINE}/com.oracle.max.graal.graph/bin
-${MAXINE}/com.oracle.max.graal.compiler/bin
-${MAXINE}/com.oracle.max.graal.nodes/bin
-${MAXINE}/com.oracle.max.graal.extensions/bin
-${MAXINE}/com.oracle.max.graal.runtime/bin
-${MAXINE}/com.oracle.max.graal.graphviz/bin
-
-For starting the Graal VM, the flag "-graal" has to be specified. Additional flags that might be useful:
--G:Plot Sends the graphs of compiled methods via network stream to the IdealGraphVisualizer (NetBeans project at ${GRAAL}/src/share/tools/IdealGraphVisualizer that can be built and run with NetBeans 7.0, use "Graal Coloring" and "Graal Edge Coloring" filters)
--G:Time Prints timings for the different compilation phases
--G:Meter Prints metrics for the different compilation phases
-
-The usual HotSpot flags -Xcomp -XX:CompileOnly= -XX:CompileCommand= or -XX:+PrintCompilation can be used to control the compiled methods.
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Mon Mar 19 15:51:49 2012 -0700
@@ -133,6 +133,10 @@
 
         new PhiStampPhase().apply(graph);
 
+        if (GraalOptions.OptCanonicalizer) {
+            new CanonicalizerPhase(target, runtime, assumptions).apply(graph);
+        }
+
         if (GraalOptions.ProbabilityAnalysis && graph.start().probability() == 0) {
             new ComputeProbabilityPhase().apply(graph);
         }
@@ -146,7 +150,7 @@
                 new CanonicalizerPhase(target, runtime, assumptions).apply(graph);
             }
 
-            new PropagateTypesPhase(target, runtime, assumptions).apply(graph);
+            new PropagateTypeCachePhase(target, runtime, assumptions).apply(graph);
         }
 
         if (GraalOptions.Inline && !plan.isPhaseDisabled(InliningPhase.class)) {
@@ -160,7 +164,7 @@
         }
 
         if (GraalOptions.PropagateTypes) {
-            new PropagateTypesPhase(target, runtime, assumptions).apply(graph);
+            new PropagateTypeCachePhase(target, runtime, assumptions).apply(graph);
         }
 
         plan.runPhases(PhasePosition.HIGH_LEVEL, graph);
@@ -194,6 +198,13 @@
                 new ReadEliminationPhase().apply(graph);
             }
         }
+
+        if (GraalOptions.PropagateTypes) {
+            new PropagateTypeCachePhase(target, runtime, assumptions).apply(graph);
+        }
+        if (GraalOptions.OptGVN) {
+            new GlobalValueNumberingPhase().apply(graph);
+        }
         new DeadCodeEliminationPhase().apply(graph);
 
         plan.runPhases(PhasePosition.MID_LEVEL, graph);
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/graph/MergeableState.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/graph/MergeableState.java	Mon Mar 19 15:51:49 2012 -0700
@@ -28,8 +28,8 @@
 
 public interface MergeableState <T> {
     T clone();
-    boolean merge(MergeNode merge, Collection<T> withStates);
+    boolean merge(MergeNode merge, List<T> withStates);
     void loopBegin(LoopBeginNode loopBegin);
-    void loopEnds(LoopBeginNode loopBegin, Collection<T> loopEndStates);
+    void loopEnds(LoopBeginNode loopBegin, List<T> loopEndStates);
     void afterSplit(FixedNode node);
 }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ComputeProbabilityPhase.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ComputeProbabilityPhase.java	Mon Mar 19 15:51:49 2012 -0700
@@ -180,7 +180,7 @@
         }
 
         @Override
-        public boolean merge(MergeNode merge, Collection<Probability> withStates) {
+        public boolean merge(MergeNode merge, List<Probability> withStates) {
             if (merge.forwardEndCount() > 1) {
                 HashSet<LoopInfo> intersection = new HashSet<>(loops);
                 for (Probability other : withStates) {
@@ -223,7 +223,7 @@
         }
 
         @Override
-        public void loopEnds(LoopBeginNode loopBegin, Collection<Probability> loopEndStates) {
+        public void loopEnds(LoopBeginNode loopBegin, List<Probability> loopEndStates) {
             assert loopInfo != null;
             List<LoopEndNode> loopEnds = loopBegin.orderedLoopEnds();
             int i = 0;
@@ -291,7 +291,7 @@
         }
 
         @Override
-        public boolean merge(MergeNode merge, Collection<LoopCount> withStates) {
+        public boolean merge(MergeNode merge, List<LoopCount> withStates) {
             assert merge.forwardEndCount() == withStates.size() + 1;
             if (merge.forwardEndCount() > 1) {
                 Set<LoopInfo> loops = mergeLoops.get(merge);
@@ -311,7 +311,7 @@
         }
 
         @Override
-        public void loopEnds(LoopBeginNode loopBegin, Collection<LoopCount> loopEndStates) {
+        public void loopEnds(LoopBeginNode loopBegin, List<LoopCount> loopEndStates) {
             // nothing to do...
         }
 
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ConvertDeoptimizeToGuardPhase.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ConvertDeoptimizeToGuardPhase.java	Mon Mar 19 15:51:49 2012 -0700
@@ -49,25 +49,30 @@
         }
 
         for (DeoptimizeNode d : graph.getNodes(DeoptimizeNode.class)) {
-            visitDeoptBranch(findBeginNode(d), d, graph);
+            visitDeoptBegin(findBeginNode(d), d, graph);
         }
 
         new DeadCodeEliminationPhase().apply(graph);
     }
 
-    private void visitDeoptBranch(BeginNode deoptBegin, DeoptimizeNode deopt, StructuredGraph graph) {
+    private void visitDeoptBegin(BeginNode deoptBegin, DeoptimizeNode deopt, StructuredGraph graph) {
         if (deoptBegin instanceof MergeNode) {
             MergeNode mergeNode = (MergeNode) deoptBegin;
-            Debug.log("Eliminating %s followed by %s", mergeNode, deopt);
+            Debug.log("Visiting %s followed by %s", mergeNode, deopt);
             List<EndNode> ends = mergeNode.forwardEnds().snapshot();
             for (EndNode end : ends) {
                 if (!end.isDeleted()) {
                     BeginNode beginNode = findBeginNode(end);
-                    visitDeoptBranch(beginNode, deopt, graph);
+                    if (!(beginNode instanceof MergeNode)) {
+                        visitDeoptBegin(beginNode, deopt, graph);
+                    }
                 }
             }
-            if (!deopt.isDeleted()) {
-                visitDeoptBranch(findBeginNode(deopt), deopt, graph);
+            if (mergeNode.isDeleted()) {
+                if (!deopt.isDeleted()) {
+                    Debug.log("Merge deleted, deopt moved to %s", findBeginNode(deopt));
+                    visitDeoptBegin(findBeginNode(deopt), deopt, graph);
+                }
             }
         } else if (deoptBegin.predecessor() instanceof IfNode) {
             IfNode ifNode = (IfNode) deoptBegin.predecessor();
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/EscapeAnalysisPhase.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/EscapeAnalysisPhase.java	Mon Mar 19 15:51:49 2012 -0700
@@ -76,7 +76,7 @@
         }
 
         @Override
-        public boolean merge(MergeNode merge, Collection<BlockExitState> withStates) {
+        public boolean merge(MergeNode merge, List<BlockExitState> withStates) {
             PhiNode vobjPhi = null;
             PhiNode[] valuePhis = new PhiNode[fieldState.length];
             for (BlockExitState other : withStates) {
@@ -129,7 +129,7 @@
         }
 
         @Override
-        public void loopEnds(LoopBeginNode loopBegin, Collection<BlockExitState> loopEndStates) {
+        public void loopEnds(LoopBeginNode loopBegin, List<BlockExitState> loopEndStates) {
             while (!(virtualObjectField instanceof PhiNode)) {
                 virtualObjectField = ((VirtualObjectFieldNode) virtualObjectField).lastState();
             }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/FloatingReadPhase.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/FloatingReadPhase.java	Mon Mar 19 15:51:49 2012 -0700
@@ -145,9 +145,9 @@
             Debug.log("Register read to node %s.", readNode);
             FloatingReadNode floatingRead;
             if (readNode.location().locationIdentity() == LocationNode.FINAL_LOCATION) {
-                floatingRead = graph.unique(new FloatingReadNode(readNode.kind(), readNode.object(), readNode.guard(), readNode.location()));
+                floatingRead = graph.unique(new FloatingReadNode(readNode.object(), readNode.guard(), readNode.location(), readNode.stamp()));
             } else {
-                floatingRead = graph.unique(new FloatingReadNode(readNode.kind(), readNode.object(), readNode.guard(), readNode.location(), getLocationForRead(readNode)));
+                floatingRead = graph.unique(new FloatingReadNode(readNode.object(), readNode.guard(), readNode.location(), readNode.stamp(), getLocationForRead(readNode)));
             }
             graph.replaceFixedWithFloating(readNode, floatingRead);
         }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/UnscheduleNodes.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/UnscheduleNodes.java	Mon Mar 19 15:51:49 2012 -0700
@@ -33,7 +33,7 @@
     public FixedWithNextNode last;
 
     @Override
-    public boolean merge(MergeNode merge, Collection<UnscheduleState> withStates) {
+    public boolean merge(MergeNode merge, List<UnscheduleState> withStates) {
         last = null;
         return true;
     }
@@ -44,7 +44,7 @@
     }
 
     @Override
-    public void loopEnds(LoopBeginNode loop, Collection<UnscheduleState> loopEndStates) {
+    public void loopEnds(LoopBeginNode loop, List<UnscheduleState> loopEndStates) {
         last = null;
     }
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/NegateObjectTypeFeedback.java	Mon Mar 19 15:51:49 2012 -0700
@@ -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	Mon Mar 19 15:51:49 2012 -0700
@@ -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();
+    }
+}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/PostOrderBlockIterator.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/PostOrderBlockIterator.java	Mon Mar 19 15:51:49 2012 -0700
@@ -24,45 +24,85 @@
 
 import java.util.*;
 
-import com.oracle.graal.graph.*;
 import com.oracle.graal.lir.cfg.*;
 
 public abstract class PostOrderBlockIterator {
 
-    private final BitMap visitedEndBlocks;
-    private final Deque<Block> blockQueue;
-
-    public PostOrderBlockIterator(Block start, int blockCount) {
-        visitedEndBlocks = new BitMap(blockCount);
-        blockQueue = new ArrayDeque<>();
-        blockQueue.add(start);
+    private static class MergeInfo {
+        int endsVisited;
+        int loopVisited;
     }
 
-    public void apply() {
-        while (!blockQueue.isEmpty()) {
-            Block current = blockQueue.removeLast();
-            block(current);
+    private final Deque<Block> blockQueue = new ArrayDeque<>();
+    private final Deque<Block> epochs = new ArrayDeque<>();
+    private final HashMap<Block, MergeInfo> mergeInfo = new HashMap<>();
 
-            for (int i = 0; i < current.getSuccessors().size(); i++) {
-                Block successor = current.getSuccessors().get(i);
-                if (successor.getPredecessors().size() > 1) {
-                    queueMerge(current, successor);
+    public void apply(Block start) {
+        blockQueue.add(start);
+        while (true) {
+            while (!blockQueue.isEmpty()) {
+                Block current = blockQueue.removeLast();
+                boolean queueSuccessors = true;
+                if (current.isLoopHeader()) {
+                    MergeInfo info = mergeInfo.get(current);
+//                    System.out.println("loop header: " + info.loopVisited + " " + info.endsVisited + "-" + info.epoch + " " + epoch);
+                    if (info.endsVisited == 1) {
+                        loopHeaderInitial(current);
+                    } else {
+                        info.loopVisited++;
+                        if (loopHeader(current, info.loopVisited)) {
+                            epochs.addFirst(current);
+                        }
+                        queueSuccessors = false;
+                    }
                 } else {
-                    blockQueue.addLast(successor);
+                    block(current);
+                }
+
+                if (queueSuccessors) {
+                    for (int i = 0; i < current.getSuccessors().size(); i++) {
+                        Block successor = current.getSuccessors().get(i);
+                        if (successor.getPredecessors().size() > 1) {
+                            queueMerge(successor);
+                        } else {
+                            blockQueue.addLast(successor);
+                        }
+                    }
+                }
+            }
+            if (epochs.isEmpty()) {
+                return;
+            } else {
+                Block nextEpoch = epochs.removeLast();
+
+                for (int i = 0; i < nextEpoch.getSuccessors().size(); i++) {
+                    Block successor = nextEpoch.getSuccessors().get(i);
+                    if (successor.getPredecessors().size() > 1) {
+                        queueMerge(successor);
+                    } else {
+                        blockQueue.addLast(successor);
+                    }
                 }
             }
         }
     }
 
+    protected abstract void loopHeaderInitial(Block block);
+
+    protected abstract boolean loopHeader(Block block, int loopVisitedCount);
+
     protected abstract void block(Block block);
 
-    private void queueMerge(Block end, Block merge) {
-        visitedEndBlocks.set(end.getId());
-        for (Block pred : merge.getPredecessors()) {
-            if (!visitedEndBlocks.get(pred.getId())) {
-                return;
-            }
+    private void queueMerge(Block merge) {
+        if (!mergeInfo.containsKey(merge)) {
+            mergeInfo.put(merge, new MergeInfo());
         }
-        blockQueue.addFirst(merge);
+        MergeInfo info = mergeInfo.get(merge);
+        info.endsVisited++;
+        if (merge.isLoopHeader() && info.endsVisited == 1) {
+            blockQueue.addFirst(merge);
+        } else if (info.endsVisited == merge.getPredecessors().size()) {
+            blockQueue.addFirst(merge);
+        }
     }
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/PropagateTypeCachePhase.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,290 @@
+/*
+ * 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.io.*;
+import java.util.*;
+
+import com.oracle.max.cri.ci.*;
+import com.oracle.max.cri.ri.*;
+import com.oracle.graal.compiler.phases.*;
+import com.oracle.graal.compiler.schedule.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.graph.*;
+import com.oracle.graal.lir.cfg.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.spi.types.*;
+import com.oracle.graal.nodes.spi.types.TypeCanonicalizable.Result;
+
+public class PropagateTypeCachePhase extends Phase {
+
+    private static final boolean DUMP = false;
+
+    private final CiTarget target;
+    private final RiRuntime runtime;
+    private final CiAssumptions assumptions;
+
+    private NodeWorkList changedNodes;
+    private StructuredGraph currentGraph;
+    private SchedulePhase schedule;
+
+    private TypeFeedbackChanged changed = new TypeFeedbackChanged();
+    private static PrintStream out = System.out;
+
+    private int changes = 0;
+
+//    private static int totalChanges = 0;
+//
+//    static {
+//        Runtime.getRuntime().addShutdownHook(new Thread() {
+//            @Override
+//            public void run() {
+//                System.out.println("Total changes: " + totalChanges);
+//            }
+//        });
+//    }
+
+    public PropagateTypeCachePhase(CiTarget target, RiRuntime runtime, CiAssumptions assumptions) {
+        this.target = target;
+        this.runtime = runtime;
+        this.assumptions = assumptions;
+    }
+
+    @Override
+    protected void run(StructuredGraph graph) {
+
+// if (!graph.method().holder().name().contains("IntegerAddNode") || !graph.method().name().equals("canonical")) {
+// return;
+// }
+
+// if (!graph.method().name().equals("notifySourceElementRequestor")) {
+// return;
+// }
+
+//        if (graph.method().holder().name().contains("jj_3R_75")) {
+//            return;
+//        }
+
+        this.currentGraph = graph;
+        new DeadCodeEliminationPhase().apply(graph);
+
+        for (GuardNode guard : graph.getNodes(GuardNode.class)) {
+            if (guard.condition() != null && guard.condition().usages().size() > 1) {
+                BooleanNode clone = (BooleanNode) guard.condition().copyWithInputs();
+                if (DUMP) {
+                    out.println("replaced!! " + clone);
+                }
+                guard.setCondition(clone);
+            }
+        }
+        for (FixedGuardNode guard : graph.getNodes(FixedGuardNode.class)) {
+            for (int i = 0; i < guard.conditions().size(); i++) {
+                BooleanNode condition = guard.conditions().get(i);
+                if (condition != null && condition.usages().size() > 1) {
+                    BooleanNode clone = (BooleanNode) condition.copyWithInputs();
+                    if (DUMP) {
+                        out.println("replaced!! " + clone);
+                    }
+                    guard.conditions().set(i, clone);
+                }
+            }
+        }
+
+        changedNodes = graph.createNodeWorkList(false, 10);
+
+        schedule = new SchedulePhase();
+        schedule.apply(graph);
+
+        new Iterator().apply(schedule.getCFG().getStartBlock());
+
+        Debug.dump(graph, "After PropagateType iteration");
+        if (changes > 0) {
+//            totalChanges += changes;
+//            out.println(graph.method() + ": " + changes + " changes");
+        }
+
+        CanonicalizerPhase.canonicalize(graph, changedNodes, runtime, target, assumptions);
+// outputGraph(graph);
+    }
+
+    public void outputGraph(StructuredGraph graph) {
+        SchedulePhase printSchedule = new SchedulePhase();
+        printSchedule.apply(graph);
+        for (Block block : printSchedule.getCFG().getBlocks()) {
+            System.out.print("Block " + block + " ");
+            if (block == printSchedule.getCFG().getStartBlock()) {
+                out.print("* ");
+            }
+            System.out.print("-> ");
+            for (Block succ : block.getSuccessors()) {
+                out.print(succ + " ");
+            }
+            System.out.println();
+            for (Node node : printSchedule.getNodesFor().get(block)) {
+                out.println("  " + node + "    (" + node.usages().size() + ")");
+            }
+        }
+    }
+
+    private class Iterator extends PostOrderBlockIterator {
+
+        private final HashMap<Block, TypeFeedbackCache> caches = new HashMap<>();
+
+        @Override
+        protected void block(Block block) {
+            if (DUMP) {
+                out.println("======= block B" + block.getId());
+            }
+            final TypeFeedbackCache cache;
+            if (block.getPredecessors().isEmpty()) {
+                cache = new TypeFeedbackCache(runtime, currentGraph, changed);
+            } else {
+                if (block.getPredecessors().size() == 1) {
+                    cache = caches.get(block.getPredecessors().get(0)).clone();
+                    Node lastInstruction = block.getPredecessors().get(0).getEndNode();
+                    if (lastInstruction instanceof ControlSplitNode && lastInstruction instanceof SplitTypeFeedbackProvider) {
+                        ControlSplitNode split = (ControlSplitNode) lastInstruction;
+                        int successorIndex = -1;
+                        for (int i = 0; i < split.blockSuccessorCount(); i++) {
+                            if (split.blockSuccessor(i) == block.getBeginNode()) {
+                                successorIndex = i;
+                                break;
+                            }
+                        }
+                        assert successorIndex != -1;
+                        changed.node = block.getBeginNode();
+                        ((SplitTypeFeedbackProvider) split).typeFeedback(successorIndex, cache);
+                        if (DUMP) {
+                            out.println("split (edge " + successorIndex + ") " + split + ": " + cache);
+                        }
+                        changed.node = null;
+                    }
+                } else {
+                    TypeFeedbackCache[] cacheList = new TypeFeedbackCache[block.getPredecessors().size()];
+                    MergeNode merge = (MergeNode) block.getBeginNode();
+                    for (int i = 0; i < block.getPredecessors().size(); i++) {
+                        Block predecessor = block.getPredecessors().get(i);
+                        TypeFeedbackCache other = caches.get(predecessor);
+                        int endIndex = merge.forwardEndIndex((EndNode) predecessor.getEndNode());
+                        cacheList[endIndex] = other;
+                    }
+                    changed.node = merge;
+                    cache = TypeFeedbackCache.meet(cacheList, merge.phis());
+                    changed.node = null;
+                    if (DUMP) {
+                        out.println("merge " + merge + ": " + cache);
+                    }
+                }
+            }
+            processNodes(block, cache);
+        }
+
+        private void processNodes(Block block, TypeFeedbackCache cache) {
+            for (Node node : schedule.nodesFor(block)) {
+                if (node.isAlive()) {
+                    if (DUMP) {
+                        out.println(node);
+                    }
+                    if (node instanceof TypeCanonicalizable) {
+                        Result canonical = ((TypeCanonicalizable) node).canonical(cache);
+
+                        if (canonical != null) {
+                            changes++;
+// System.out.print("!");
+                            if (DUMP) {
+                                out.println("TypeCanonicalizable: replacing " + node + " with " + canonical);
+                            }
+                            if (canonical.dependencies.length > 0) {
+                                for (Node usage : node.usages()) {
+                                    if (usage instanceof ValueNode) {
+                                        for (Node dependency : canonical.dependencies) {
+                                            // TODO(lstadler) dead dependencies should be handled differently
+                                            if (dependency.isAlive()) {
+                                                ((ValueNode) usage).dependencies().add(dependency);
+                                            }
+                                        }
+                                    }
+                                }
+                            }
+                            ValueNode replacement = canonical.replacement;
+                            currentGraph.replaceFloating((FloatingNode) node, replacement);
+                            changedNodes.addAll(replacement.usages());
+                        }
+                    }
+                    if (node.isAlive() && node instanceof TypeFeedbackProvider) {
+                        changed.node = node;
+                        ((TypeFeedbackProvider) node).typeFeedback(cache);
+                        if (DUMP) {
+                            out.println("  " + cache);
+                        }
+                        changed.node = null;
+                    }
+                }
+            }
+            caches.put(block, cache);
+        }
+
+        @Override
+        protected void loopHeaderInitial(Block block) {
+            if (DUMP) {
+                out.println("======= loop block B" + block.getId());
+            }
+            assert block.getPredecessors().get(0) == block.getDominator();
+            TypeFeedbackCache cache = caches.get(block.getPredecessors().get(0)).clone();
+            processNodes(block, cache);
+        }
+
+        @Override
+        protected boolean loopHeader(Block block, int loopVisitedCount) {
+            if (DUMP) {
+                out.println("======= loop again block B" + block.getId());
+            }
+            if (loopVisitedCount == 1) {
+                TypeFeedbackCache[] cacheList = new TypeFeedbackCache[block.getPredecessors().size()];
+                LoopBeginNode loop = (LoopBeginNode) block.getBeginNode();
+                for (int i = 0; i < block.getPredecessors().size(); i++) {
+                    Block predecessor = block.getPredecessors().get(i);
+                    TypeFeedbackCache other = caches.get(predecessor);
+                    int endIndex;
+                    if (loop.forwardEnd() == predecessor.getEndNode()) {
+                        endIndex = 0;
+                    } else {
+                        endIndex = loop.orderedLoopEnds().indexOf(predecessor.getEndNode()) + 1;
+                        assert endIndex != 0;
+                    }
+                    cacheList[endIndex] = other;
+                }
+                TypeFeedbackCache cache = TypeFeedbackCache.meet(cacheList, loop.phis());
+                if (DUMP) {
+                    out.println("loop merge " + loop + ": " + cache);
+                }
+                processNodes(block, cache);
+                return true;
+            } else {
+                return false;
+            }
+        }
+    }
+
+}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/PropagateTypesPhase.java	Mon Mar 19 15:47:35 2012 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,264 +0,0 @@
-/*
- * 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.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.compiler.graph.*;
-import com.oracle.graal.compiler.phases.*;
-import com.oracle.graal.compiler.schedule.*;
-import com.oracle.graal.debug.*;
-import com.oracle.graal.graph.*;
-import com.oracle.graal.graph.NodeClass.NodeClassIterator;
-import com.oracle.graal.graph.NodeClass.Position;
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.calc.*;
-import com.oracle.graal.nodes.java.*;
-import com.oracle.graal.nodes.spi.*;
-import com.oracle.graal.nodes.type.*;
-
-public class PropagateTypesPhase extends Phase {
-
-    private final CiTarget target;
-    private final RiRuntime runtime;
-    private final CiAssumptions assumptions;
-
-    private NodeWorkList changedNodes;
-
-    public PropagateTypesPhase(CiTarget target, RiRuntime runtime, CiAssumptions assumptions) {
-        this.target = target;
-        this.runtime = runtime;
-        this.assumptions = assumptions;
-    }
-
-    @Override
-    protected void run(StructuredGraph graph) {
-
-        new DeadCodeEliminationPhase().apply(graph);
-
-        changedNodes = graph.createNodeWorkList(false, 10);
-
-        SchedulePhase schedule = new SchedulePhase();
-        schedule.apply(graph);
-
-        schedule.scheduleGraph();
-        Debug.dump(graph, "scheduled");
-
-        new PropagateTypes(graph.start()).apply();
-        Debug.dump(graph, "after propagation");
-
-        new UnscheduleNodes(graph.start()).apply();
-
-        CanonicalizerPhase.canonicalize(graph, changedNodes, runtime, target, assumptions);
-    }
-
-    private class PiNodeList {
-
-        public final PiNodeList last;
-        public final ValueNode replacement;
-        public final int depth;
-
-        public PiNodeList(ValueNode replacement, PiNodeList last) {
-            this.last = last;
-            this.replacement = replacement;
-            this.depth = last != null ? last.depth + 1 : 1;
-        }
-
-        public PiNodeList merge(PiNodeList other) {
-            PiNodeList thisList = this;
-            PiNodeList otherList = other;
-            while (thisList.depth > otherList.depth) {
-                thisList = thisList.last;
-            }
-            while (otherList.depth > thisList.depth) {
-                otherList = otherList.last;
-            }
-            while (thisList != otherList) {
-                thisList = thisList.last;
-                otherList = otherList.last;
-            }
-            return thisList;
-        }
-    }
-
-    private class TypeInfo implements MergeableState<TypeInfo> {
-
-        private HashMap<ValueNode, PiNodeList> piNodes = new HashMap<>();
-
-        public TypeInfo(HashMap<ValueNode, PiNodeList> piNodes) {
-            this.piNodes.putAll(piNodes);
-        }
-
-        @Override
-        public TypeInfo clone() {
-            return new TypeInfo(piNodes);
-        }
-
-        @Override
-        public boolean merge(MergeNode merge, Collection<TypeInfo> withStates) {
-            if (merge.forwardEndCount() > 1) {
-                HashMap<ValueNode, PiNodeList> newPiNodes = new HashMap<>();
-                for (Entry<ValueNode, PiNodeList> entry : piNodes.entrySet()) {
-                    PiNodeList list = entry.getValue();
-                    for (TypeInfo info : withStates) {
-                        PiNodeList other = info.piNodes.get(entry.getKey());
-                        if (other == null) {
-                            list = null;
-                        } else {
-                            list = list.merge(other);
-                        }
-                        if (list == null) {
-                            break;
-                        }
-                    }
-                    if (list != null) {
-                        newPiNodes.put(entry.getKey(), list);
-                    }
-                }
-                piNodes = newPiNodes;
-            }
-            return true;
-        }
-
-        @Override
-        public void loopBegin(LoopBeginNode loop) {
-        }
-
-        @Override
-        public void loopEnds(LoopBeginNode loop, Collection<TypeInfo> loopEndStates) {
-        }
-
-        @Override
-        public void afterSplit(FixedNode node) {
-            assert node.predecessor() != null;
-            assert node.predecessor() instanceof ControlSplitNode;
-//            TTY.println("after split: %s", node);
-            if (node.predecessor() instanceof IfNode) {
-                IfNode ifNode = (IfNode) node.predecessor();
-                if (ifNode.compare() instanceof InstanceOfNode) {
-                    InstanceOfNode instanceOf = (InstanceOfNode) ifNode.compare();
-                    assert node == ifNode.trueSuccessor() || node == ifNode.falseSuccessor();
-                    if ((node == ifNode.trueSuccessor() && !instanceOf.negated()) || (node == ifNode.falseSuccessor() && instanceOf.negated())) {
-                        ValueNode value = instanceOf.object();
-                        if (value.declaredType() != instanceOf.targetClass() || !value.stamp().nonNull()) {
-                            PiNode piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.declaredNonNull(instanceOf.targetClass())));
-                            PiNodeList list = piNodes.get(value);
-                            piNodes.put(value, new PiNodeList(piNode, list));
-                        }
-                    }
-                } else if (ifNode.compare() instanceof CompareNode) {
-                    CompareNode compare = (CompareNode) ifNode.compare();
-                    assert node == ifNode.trueSuccessor() || node == ifNode.falseSuccessor();
-                    if ((node == ifNode.trueSuccessor() && compare.condition() == Condition.EQ) || (node == ifNode.falseSuccessor() && compare.condition() == Condition.NE)) {
-                        if (compare.y().isConstant()) {
-                            ValueNode value = compare.x();
-                            PiNodeList list = piNodes.get(value);
-                            piNodes.put(value, new PiNodeList(compare.y(), list));
-                        }
-                    } else if ((node == ifNode.trueSuccessor() && compare.condition() == Condition.NE) || (node == ifNode.falseSuccessor() && compare.condition() == Condition.EQ)) {
-                        if (!compare.x().isConstant() && compare.y().isNullConstant() && !compare.x().stamp().nonNull()) {
-                            ValueNode value = compare.x();
-                            PiNode piNode;
-                            if (value.exactType() != null) {
-                                piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.declaredNonNull(value.exactType())));
-                            } else if (value.declaredType() != null) {
-                                piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.declaredNonNull(value.declaredType())));
-                            } else {
-                                piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.objectNonNull()));
-                            }
-                            PiNodeList list = piNodes.get(value);
-                            piNodes.put(value, new PiNodeList(piNode, list));
-                        }
-                    }
-                }
-            }
-        }
-    }
-
-    private class Tool implements CanonicalizerTool {
-        @Override
-        public CiTarget target() {
-            return target;
-        }
-
-        @Override
-        public CiAssumptions assumptions() {
-            return assumptions;
-        }
-
-        @Override
-        public RiRuntime runtime() {
-            return runtime;
-        }
-    }
-
-    private final Tool tool = new Tool();
-
-    private class PropagateTypes extends ScheduledNodeIterator<TypeInfo> {
-
-        public PropagateTypes(FixedNode start) {
-            super(start, new TypeInfo(new HashMap<ValueNode, PiNodeList>()));
-        }
-
-        @Override
-        protected void node(ScheduledNode node) {
-            if (node instanceof Canonicalizable || node instanceof Invoke) {
-                NodeClassIterator iter = node.inputs().iterator();
-                ArrayList<Node> changedInputs = new ArrayList<>();
-                while (iter.hasNext()) {
-                    Position pos = iter.nextPosition();
-                    Node value = pos.get(node);
-                    PiNodeList list = state.piNodes.get(value);
-                    if (list != null) {
-                        changedInputs.add(list.replacement instanceof PiNode ? value : null);
-                        pos.set(node, list.replacement);
-                    } else {
-                        changedInputs.add(null);
-                    }
-                }
-
-                ValueNode canonical = null;
-                if (node instanceof Canonicalizable) {
-                    canonical = ((Canonicalizable) node).canonical(tool);
-                }
-
-                if (canonical == node) {
-                    iter = node.inputs().iterator();
-                    int i = 0;
-                    while (iter.hasNext()) {
-                        Position pos = iter.nextPosition();
-                        if (changedInputs.get(i) != null) {
-                            pos.set(node, changedInputs.get(i));
-                        }
-                        i++;
-                    }
-                } else {
-                    changedNodes.add(node);
-                }
-            }
-        }
-    }
-}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/types/TypeFeedbackCache.java	Mon Mar 19 15:51:49 2012 -0700
@@ -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.graph/src/com/oracle/graal/graph/NodeInputList.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeInputList.java	Mon Mar 19 15:51:49 2012 -0700
@@ -57,7 +57,7 @@
 
     @Override
     public boolean add(T node) {
-        assert !node.isDeleted();
+        assert node == null || !node.isDeleted();
         self.incModCount();
         return super.add(node);
     }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeList.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeList.java	Mon Mar 19 15:51:49 2012 -0700
@@ -321,6 +321,13 @@
         return true;
     }
 
+    public boolean addAll(T[] c) {
+        for (T e : c) {
+            add(e);
+        }
+        return true;
+    }
+
     @Override
     public boolean addAll(int index, Collection< ? extends T> c) {
         throw new UnsupportedOperationException("not implemented");
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/ri/HotSpotRuntime.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/ri/HotSpotRuntime.java	Mon Mar 19 15:51:49 2012 -0700
@@ -38,6 +38,7 @@
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.extended.*;
 import com.oracle.graal.nodes.java.*;
+import com.oracle.graal.nodes.type.*;
 import com.oracle.graal.snippets.nodes.*;
 import com.oracle.max.cri.ci.*;
 import com.oracle.max.cri.ci.CiTargetMethod.Call;
@@ -217,7 +218,7 @@
 
         if (n instanceof ArrayLengthNode) {
             ArrayLengthNode arrayLengthNode = (ArrayLengthNode) n;
-            SafeReadNode safeReadArrayLength = safeReadArrayLength(arrayLengthNode.graph(), arrayLengthNode.array());
+            SafeReadNode safeReadArrayLength = safeReadArrayLength(arrayLengthNode.graph(), arrayLengthNode.array(), arrayLengthNode.stamp());
             graph.replaceFixedWithFixed(arrayLengthNode, safeReadArrayLength);
             safeReadArrayLength.lower(tool);
         } else if (n instanceof LoadFieldNode) {
@@ -227,7 +228,7 @@
             }
             int displacement = ((HotSpotField) field.field()).offset();
             assert field.kind() != CiKind.Illegal;
-            ReadNode memoryRead = graph.add(new ReadNode(field.field().kind(true).stackKind(), field.object(), LocationNode.create(field.field(), field.field().kind(true), displacement, graph)));
+            ReadNode memoryRead = graph.add(new ReadNode(field.object(), LocationNode.create(field.field(), field.field().kind(true), displacement, graph), field.stamp()));
             memoryRead.setGuard((GuardNode) tool.createGuard(graph.unique(new NullCheckNode(field.object(), false)), RiDeoptReason.NullCheckException));
             graph.replaceFixedWithFixed(field, memoryRead);
         } else if (n instanceof StoreFieldNode) {
@@ -250,7 +251,7 @@
 
             CiKind elementKind = loadIndexed.elementKind();
             LocationNode arrayLocation = createArrayLocation(graph, elementKind, loadIndexed.index());
-            ReadNode memoryRead = graph.add(new ReadNode(elementKind.stackKind(), loadIndexed.array(), arrayLocation));
+            ReadNode memoryRead = graph.add(new ReadNode(loadIndexed.array(), arrayLocation, loadIndexed.stamp()));
             memoryRead.setGuard(boundsCheck);
             graph.replaceFixedWithFixed(loadIndexed, memoryRead);
         } else if (n instanceof StoreIndexedNode) {
@@ -277,10 +278,10 @@
                     AnchorNode anchor = graph.add(new AnchorNode());
                     graph.addBeforeFixed(storeIndexed, anchor);
                     GuardNode guard = (GuardNode) tool.createGuard(graph.unique(new NullCheckNode(array, false)), RiDeoptReason.NullCheckException);
-                    ReadNode arrayClass = graph.add(new ReadNode(CiKind.Object, array, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Object, config.hubOffset, graph)));
+                    ReadNode arrayClass = graph.add(new ReadNode(array, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Object, config.hubOffset, graph), StampFactory.objectNonNull()));
                     arrayClass.setGuard(guard);
                     graph.addBeforeFixed(storeIndexed, arrayClass);
-                    ReadNode arrayElementKlass = graph.add(new ReadNode(CiKind.Object, arrayClass, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Object, config.arrayClassElementOffset, graph)));
+                    ReadNode arrayElementKlass = graph.add(new ReadNode(arrayClass, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Object, config.arrayClassElementOffset, graph), StampFactory.objectNonNull()));
                     value = graph.unique(new CheckCastNode(anchor, arrayElementKlass, null, value));
                 }
             }
@@ -298,7 +299,7 @@
             assert load.kind() != CiKind.Illegal;
             IndexedLocationNode location = IndexedLocationNode.create(LocationNode.ANY_LOCATION, load.loadKind(), load.displacement(), load.offset(), graph);
             location.setIndexScalingEnabled(false);
-            ReadNode memoryRead = graph.add(new ReadNode(load.kind(), load.object(), location));
+            ReadNode memoryRead = graph.add(new ReadNode(load.object(), location, load.stamp()));
             memoryRead.setGuard((GuardNode) tool.createGuard(graph.unique(new NullCheckNode(load.object(), false)), RiDeoptReason.NullCheckException));
             graph.replaceFixedWithFixed(load, memoryRead);
         } else if (n instanceof UnsafeStoreNode) {
@@ -316,7 +317,7 @@
         } else if (n instanceof ReadHubNode) {
             ReadHubNode objectClassNode = (ReadHubNode) n;
             LocationNode location = LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Object, config.hubOffset, graph);
-            ReadNode memoryRead = graph.add(new ReadNode(CiKind.Object, objectClassNode.object(), location));
+            ReadNode memoryRead = graph.add(new ReadNode(objectClassNode.object(), location, StampFactory.objectNonNull()));
             memoryRead.setGuard((GuardNode) tool.createGuard(graph.unique(new NullCheckNode(objectClassNode.object(), false)), RiDeoptReason.NullCheckException));
             graph.replaceFixed(objectClassNode, memoryRead);
         }
@@ -348,7 +349,7 @@
                 StructuredGraph graph = new StructuredGraph();
                 LocalNode receiver = graph.unique(new LocalNode(CiKind.Object, 0));
                 SafeReadNode klassOop = safeReadHub(graph, receiver);
-                ReadNode result = graph.add(new ReadNode(CiKind.Object, klassOop, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Object, config.classMirrorOffset, graph)));
+                FloatingReadNode result = graph.unique(new FloatingReadNode(klassOop, null, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Object, config.classMirrorOffset, graph), StampFactory.objectNonNull()));
                 ReturnNode ret = graph.add(new ReturnNode(result));
                 graph.start().setNext(klassOop);
                 klassOop.setNext(ret);
@@ -358,10 +359,10 @@
             if (fullName.equals("getModifiers()I")) {
                 StructuredGraph graph = new StructuredGraph();
                 LocalNode receiver = graph.unique(new LocalNode(CiKind.Object, 0));
-                SafeReadNode klassOop = safeRead(graph, CiKind.Object, receiver, config.klassOopOffset);
+                SafeReadNode klassOop = safeRead(graph, CiKind.Object, receiver, config.klassOopOffset, StampFactory.objectNonNull());
                 graph.start().setNext(klassOop);
-                // TODO (thomaswue): Care about primitive classes! Crashes for primitive classes at the moment (klassOop == null)
-                ReadNode result = graph.add(new ReadNode(CiKind.Int, klassOop, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Int, config.klassModifierFlagsOffset, graph)));
+                // TODO(thomaswue): Care about primitive classes! Crashes for primitive classes at the moment (klassOop == null)
+                ReadNode result = graph.add(new ReadNode(klassOop, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Int, config.klassModifierFlagsOffset, graph), StampFactory.forKind(CiKind.Int)));
                 ReturnNode ret = graph.add(new ReturnNode(result));
                 klassOop.setNext(ret);
                 return graph;
@@ -378,15 +379,15 @@
     }
 
     private SafeReadNode safeReadHub(Graph graph, ValueNode value) {
-        return safeRead(graph, CiKind.Object, value, config.hubOffset);
+        return safeRead(graph, CiKind.Object, value, config.hubOffset, StampFactory.objectNonNull());
     }
 
-    private SafeReadNode safeReadArrayLength(Graph graph, ValueNode value) {
-        return safeRead(graph, CiKind.Int, value, config.arrayLengthOffset);
+    private SafeReadNode safeReadArrayLength(Graph graph, ValueNode value, Stamp stamp) {
+        return safeRead(graph, CiKind.Int, value, config.arrayLengthOffset, stamp);
     }
 
-    private static SafeReadNode safeRead(Graph graph, CiKind kind, ValueNode value, int offset) {
-        return graph.add(new SafeReadNode(kind, value, LocationNode.create(LocationNode.FINAL_LOCATION, kind, offset, graph)));
+    private static SafeReadNode safeRead(Graph graph, CiKind kind, ValueNode value, int offset, Stamp stamp) {
+        return graph.add(new SafeReadNode(value, LocationNode.create(LocationNode.FINAL_LOCATION, kind, offset, graph), stamp));
     }
 
     public RiResolvedType getType(Class<?> clazz) {
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java	Mon Mar 19 15:51:49 2012 -0700
@@ -22,19 +22,19 @@
  */
 package com.oracle.graal.java;
 
+import static com.oracle.graal.graph.iterators.NodePredicates.*;
 import static com.oracle.graal.nodes.ValueUtil.*;
 import static java.lang.reflect.Modifier.*;
 
 import java.util.*;
 
-import com.oracle.max.cri.ci.*;
-import com.oracle.max.cri.ri.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.Node.Verbosity;
-import com.oracle.graal.graph.iterators.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.PhiNode.PhiType;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.max.cri.ci.*;
+import com.oracle.max.cri.ri.*;
 
 public class FrameStateBuilder {
     private final RiResolvedMethod method;
@@ -169,7 +169,7 @@
 
         } else if (block.isPhiAtMerge(currentValue)) {
             if (otherValue == null || currentValue.kind() != otherValue.kind()) {
-                deletePhi(currentValue);
+                deletePhi((PhiNode) currentValue);
                 return null;
             }
             ((PhiNode) currentValue).addInput(otherValue);
@@ -194,19 +194,19 @@
         }
     }
 
-    private void deletePhi(Node phi) {
+    private void deletePhi(PhiNode phi) {
         if (phi.isDeleted()) {
             return;
         }
         // Collect all phi functions that use this phi so that we can delete them recursively (after we delete ourselfs to avoid circles).
-        List<Node> phiUsages = phi.usages().filter(NodePredicates.isA(PhiNode.class)).snapshot();
+        List<PhiNode> phiUsages = phi.usages().filter(PhiNode.class).snapshot();
 
         // Remove the phi function from all FrameStates where it is used and then delete it.
-        assert phi.usages().filter(NodePredicates.isNotA(FrameState.class)).filter(NodePredicates.isNotA(PhiNode.class)).isEmpty() : "phi function that gets deletes must only be used in frame states";
+        assert phi.usages().filter(isNotA(FrameState.class).nor(PhiNode.class)).isEmpty() : "phi function that gets deletes must only be used in frame states";
         phi.replaceAtUsages(null);
         phi.safeDelete();
 
-        for (Node phiUsage : phiUsages) {
+        for (PhiNode phiUsage : phiUsages) {
             deletePhi(phiUsage);
         }
     }
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Mon Mar 19 15:51:49 2012 -0700
@@ -185,7 +185,7 @@
 
         connectLoopEndToBegin();
 
-        // remove Placeholders (except for loop exits)
+        // remove Placeholders
         for (BlockPlaceholderNode n : currentGraph.getNodes(BlockPlaceholderNode.class)) {
             currentGraph.removeFixed(n);
         }
@@ -1335,7 +1335,7 @@
                 currentGraph.reduceDegenerateLoopBegin(begin);
             } else {
                 // Delete unnecessary loop phi functions, i.e., phi functions where all inputs are either the same or the phi itself.
-                for (PhiNode phi : begin.stateAfter().values().filter(PhiNode.class).snapshot()) {
+                for (PhiNode phi : begin.phis().snapshot()) {
                     checkRedundantPhi(phi);
                 }
             }
--- a/graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/loop/LoopInline.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/loop/LoopInline.java	Mon Mar 19 15:51:49 2012 -0700
@@ -24,9 +24,6 @@
 
 import org.junit.*;
 
-/*
- * This test is meaningful only if you run it with 'forced' inlinning because running it in the harness with -Xcomp will not trigger any normal inlining
- */
 public class LoopInline {
 
     public static int test(int arg) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BooleanNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BooleanNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -22,6 +22,7 @@
  */
 package com.oracle.graal.nodes;
 
+import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.type.*;
 
@@ -32,5 +33,9 @@
         super(stamp);
     }
 
+    public BooleanNode(Stamp stamp, Node... dependencies) {
+        super(stamp, dependencies);
+    }
+
     public abstract BooleanNode negate();
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ConstantNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ConstantNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -39,7 +39,8 @@
     @Data public final CiConstant value;
 
     protected ConstantNode(CiConstant value) {
-        this(value, null);
+        super(StampFactory.forConstant(value));
+        this.value = value;
     }
 
     /**
@@ -65,7 +66,11 @@
     }
 
     public static ConstantNode forCiConstant(CiConstant constant, RiRuntime runtime, Graph graph) {
-        return graph.unique(new ConstantNode(constant, runtime));
+        if (constant.kind == CiKind.Object) {
+            return graph.unique(new ConstantNode(constant, runtime));
+        } else {
+            return graph.unique(new ConstantNode(constant));
+        }
     }
 
     /**
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedGuardNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedGuardNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -28,7 +28,7 @@
 import com.oracle.graal.nodes.type.*;
 import com.oracle.max.cri.ri.*;
 
-public final class FixedGuardNode extends FixedWithNextNode implements Simplifiable, Lowerable, LIRLowerable {
+public final class FixedGuardNode extends FixedWithNextNode implements Simplifiable, Lowerable, LIRLowerable, Node.IterableNodeType {
 
     @Input private final NodeInputList<BooleanNode> conditions;
     @Data  private final RiDeoptReason deoptReason;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java	Mon Mar 19 15:51:49 2012 -0700
@@ -209,7 +209,7 @@
             } else {
                 popSlots = 1;
             }
-            assert stackAt(stackSize() - popSlots).kind().stackKind() == popKind.stackKind();
+            assert stackAt(stackSize() - popSlots).kind().stackKind() == popKind.stackKind() || (stackAt(stackSize() - popSlots) instanceof BoxedVirtualObjectNode && popKind.isObject());
         }
 
         int pushSlots = pushedValues.length;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GuardNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GuardNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -22,12 +22,14 @@
  */
 package com.oracle.graal.nodes;
 
+import com.oracle.graal.graph.*;
 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.*;
 import com.oracle.max.cri.ri.*;
 
-public final class GuardNode extends FloatingNode implements Canonicalizable, LIRLowerable {
+public final class GuardNode extends FloatingNode implements Canonicalizable, LIRLowerable, TypeFeedbackProvider, Node.IterableNodeType {
 
     @Input private BooleanNode condition;
     @Input(notDataflow = true) private FixedNode anchor;
@@ -48,6 +50,11 @@
     public BooleanNode condition() {
         return condition;
     }
+    
+    public void setCondition(BooleanNode x) {
+        updateUsages(condition, x);
+        condition = x;
+    }
 
     public RiDeoptReason reason() {
         return reason;
@@ -70,10 +77,24 @@
         if (condition() instanceof ConstantNode) {
             ConstantNode c = (ConstantNode) condition();
             if (c.asConstant().asBoolean()) {
+                if (!dependencies().isEmpty()) {
+                    for (Node usage : usages()) {
+                        if (usage instanceof ValueNode) {
+                            ((ValueNode) usage).dependencies().addAll(dependencies());
+                        }
+                    }
+                }
                 this.replaceAtUsages(null);
                 return null;
             }
         }
         return this;
     }
+
+    @Override
+    public void typeFeedback(TypeFeedbackTool tool) {
+        if (condition instanceof ConditionalTypeFeedbackProvider) {
+            ((ConditionalTypeFeedbackProvider) condition).typeFeedback(tool);
+        }
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -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());
+        }
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -178,6 +178,11 @@
         if (node == null) {
             assert kind() == CiKind.Void && usages().isEmpty();
             ((StructuredGraph) graph()).removeSplit(this, NORMAL_EDGE);
+        } else if (node instanceof DeoptimizeNode) {
+            this.replaceAtPredecessors(node);
+            this.replaceAtUsages(null);
+            GraphUtil.killCFG(this);
+            return;
         } else {
             ((StructuredGraph) graph()).replaceSplit(this, node, NORMAL_EDGE);
         }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/MergeNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/MergeNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -115,7 +115,12 @@
     }
 
     public NodeIterable<PhiNode> phis() {
-        return this.usages().filter(PhiNode.class);
+        return this.usages().filter(new NodePredicate() {
+            @Override
+            public boolean apply(Node n) {
+                return n instanceof PhiNode && ((PhiNode) n).merge() == MergeNode.this;
+            }
+        }).filter(PhiNode.class);
     }
 
     @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PiNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PiNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -29,25 +29,25 @@
 
 public class PiNode extends FloatingNode implements LIRLowerable {
 
-    @Input private ValueNode value;
+    @Input private ValueNode object;
     @Input private BeginNode anchor;
 
-    public ValueNode value() {
-        return value;
+    public ValueNode object() {
+        return object;
     }
 
     public BeginNode anchor() {
         return anchor;
     }
 
-    public PiNode(ValueNode value, BeginNode anchor, Stamp stamp) {
+    public PiNode(ValueNode object, BeginNode anchor, Stamp stamp) {
         super(stamp);
-        this.value = value;
+        this.object = object;
         this.anchor = anchor;
     }
 
     @Override
     public void generate(LIRGeneratorTool generator) {
-        generator.setResult(this, generator.operand(value));
+        generator.setResult(this, generator.operand(object));
     }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -22,8 +22,11 @@
  */
 package com.oracle.graal.nodes;
 
+import java.util.*;
+
 import com.oracle.max.cri.ci.*;
 import com.oracle.max.cri.ri.*;
+import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.type.*;
 
 /**
@@ -38,15 +41,21 @@
      */
     @Data private Stamp stamp;
 
-    /**
-     * Creates a new value with the specified kind.
-     * @param kind the type of this value
-     * @param inputCount
-     * @param successorCount
-     * @param graph
-     */
+    @Input private NodeInputList<Node> dependencies;
+
+    public NodeInputList<Node> dependencies() {
+        return dependencies;
+    }
+
     public ValueNode(Stamp stamp) {
         this.stamp = stamp;
+        this.dependencies = new NodeInputList<>(this);
+        assert kind() != null && kind() == kind().stackKind() : kind() + " != " + kind().stackKind();
+    }
+
+    public ValueNode(Stamp stamp, Node... dependencies) {
+        this.stamp = stamp;
+        this.dependencies = new NodeInputList<>(this, dependencies);
         assert kind() != null && kind() == kind().stackKind() : kind() + " != " + kind().stackKind();
     }
 
@@ -105,4 +114,17 @@
     public final RiResolvedType declaredType() {
         return stamp.declaredType();
     }
+
+    @Override
+    public Map<Object, Object> getDebugProperties() {
+        Map<Object, Object> properties = super.getDebugProperties();
+        if (!dependencies.isEmpty()) {
+            StringBuilder str = new StringBuilder();
+            for (int i = 0; i < dependencies.size(); i++) {
+                str.append(i == 0 ? "" : ", ").append(dependencies.get(i).toString(Verbosity.Id));
+            }
+            properties.put("dependencies", str.toString());
+        }
+        return properties;
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -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;
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/Condition.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/Condition.java	Mon Mar 19 15:51:49 2012 -0700
@@ -141,13 +141,13 @@
         switch (this) {
             case EQ: return other == LE || other == GE || other == BE || other == AE;
             case NE: return false;
-            case LT: return other == LE;
+            case LT: return other == LE || other == NE;
             case LE: return false;
-            case GT: return other == GE;
+            case GT: return other == GE || other == NE;
             case GE: return false;
-            case BT: return other == BE;
+            case BT: return other == BE || other == NE;
             case BE: return false;
-            case AT: return other == AE;
+            case AT: return other == AE || other == NE;
             case AE: return false;
             case OF: return false;
             case NOF: return false;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatingNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatingNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -27,7 +27,12 @@
 import com.oracle.graal.nodes.type.*;
 
 public abstract class FloatingNode extends ValueNode implements Node.ValueNumberable {
+
     public FloatingNode(Stamp stamp) {
         super(stamp);
     }
+
+    public FloatingNode(Stamp stamp, Node... dependencies) {
+        super(stamp, dependencies);
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerAddNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerAddNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -26,9 +26,10 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.spi.types.*;
 
 @NodeInfo(shortName = "+")
-public class IntegerAddNode extends IntegerArithmeticNode implements Canonicalizable, LIRLowerable {
+public class IntegerAddNode extends IntegerArithmeticNode implements Canonicalizable, LIRLowerable, TypeFeedbackProvider {
 
     public IntegerAddNode(CiKind kind, ValueNode x, ValueNode y) {
         super(kind, x, y);
@@ -93,4 +94,13 @@
         }
         gen.setResult(this, gen.emitAdd(op1, op2));
     }
+
+    @Override
+    public void typeFeedback(TypeFeedbackTool tool) {
+        if (y().isConstant() && !x().isConstant()) {
+            tool.addScalar(this).setTranslated(y().asConstant(), tool.queryScalar(x()));
+        } else if (x().isConstant() && !y().isConstant()) {
+            tool.addScalar(this).setTranslated(x().asConstant(), tool.queryScalar(y()));
+        }
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NullCheckNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NullCheckNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -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;
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/AccessNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/AccessNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -22,7 +22,6 @@
  */
 package com.oracle.graal.nodes.extended;
 
-import com.oracle.max.cri.ci.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.type.*;
 
@@ -58,8 +57,8 @@
         this.nullCheck = check;
     }
 
-    public AccessNode(CiKind kind, ValueNode object, LocationNode location) {
-        super(StampFactory.forKind(kind));
+    public AccessNode(ValueNode object, LocationNode location, Stamp stamp) {
+        super(stamp);
         this.object = object;
         this.location = location;
     }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/FloatingAccessNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/FloatingAccessNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -22,7 +22,7 @@
  */
 package com.oracle.graal.nodes.extended;
 
-import com.oracle.max.cri.ci.*;
+import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.type.*;
@@ -59,8 +59,15 @@
         this.nullCheck = check;
     }
 
-    public FloatingAccessNode(CiKind kind, ValueNode object, GuardNode guard, LocationNode location) {
-        super(StampFactory.forKind(kind));
+    public FloatingAccessNode(ValueNode object, GuardNode guard, LocationNode location, Stamp stamp) {
+        super(stamp);
+        this.object = object;
+        this.guard = guard;
+        this.location = location;
+    }
+
+    public FloatingAccessNode(ValueNode object, GuardNode guard, LocationNode location, Stamp stamp, Node... dependencies) {
+        super(stamp, dependencies);
         this.object = object;
         this.guard = guard;
         this.location = location;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/FloatingReadNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/FloatingReadNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -27,19 +27,13 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.type.*;
 
 
 public final class FloatingReadNode extends FloatingAccessNode implements Node.IterableNodeType, LIRLowerable, Canonicalizable {
 
-    @Input private final NodeInputList<Node> dependencies;
-
-    public NodeInputList<Node> dependencies() {
-        return dependencies;
-    }
-
-    public FloatingReadNode(CiKind kind, ValueNode object, GuardNode guard, LocationNode location, Node... dependencies) {
-        super(kind, object, guard, location);
-        this.dependencies = new NodeInputList<>(this, dependencies);
+    public FloatingReadNode(ValueNode object, GuardNode guard, LocationNode location, Stamp stamp, Node... dependencies) {
+        super(object, guard, location, stamp, dependencies);
     }
 
     @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/ReadNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/ReadNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -27,12 +27,13 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.type.*;
 
 
 public final class ReadNode extends AccessNode implements Node.IterableNodeType, LIRLowerable, Canonicalizable {
 
-    public ReadNode(CiKind kind, ValueNode object, LocationNode location) {
-        super(kind, object, location);
+    public ReadNode(ValueNode object, LocationNode location, Stamp stamp) {
+        super(object, location, stamp);
     }
 
     @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SafeAccessNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SafeAccessNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -22,7 +22,6 @@
  */
 package com.oracle.graal.nodes.extended;
 
-import com.oracle.max.cri.ci.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.type.*;
 
@@ -32,8 +31,8 @@
     @Input private ValueNode object;
     @Input private LocationNode location;
 
-    public SafeAccessNode(CiKind kind, ValueNode object, LocationNode location) {
-        super(StampFactory.forKind(kind));
+    public SafeAccessNode(ValueNode object, LocationNode location, Stamp stamp) {
+        super(stamp);
         this.object = object;
         this.location = location;
     }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SafeReadNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SafeReadNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -26,14 +26,15 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.type.*;
 import com.oracle.max.cri.ci.*;
 import com.oracle.max.cri.ri.*;
 
 
 public class SafeReadNode extends SafeAccessNode implements Lowerable {
 
-    public SafeReadNode(CiKind kind, ValueNode object, LocationNode location) {
-        super(kind, object, location);
+    public SafeReadNode(ValueNode object, LocationNode location, Stamp stamp) {
+        super(object, location, stamp);
         assert object != null && location != null;
     }
 
@@ -41,7 +42,7 @@
     public void lower(CiLoweringTool tool) {
         StructuredGraph graph = (StructuredGraph) graph();
         GuardNode guard = (GuardNode) tool.createGuard(graph.unique(new NullCheckNode(object(), false)), RiDeoptReason.NullCheckException);
-        ReadNode read = graph.add(new ReadNode(kind(), object(), location()));
+        ReadNode read = graph.add(new ReadNode(object(), location(), stamp()));
         read.setGuard(guard);
 
         graph.replaceFixedWithFixed(this, read);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SafeWriteNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SafeWriteNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -27,6 +27,7 @@
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.max.cri.ci.*;
+import com.oracle.graal.nodes.type.*;
 import com.oracle.max.cri.ri.*;
 
 
@@ -35,7 +36,7 @@
     @Input private ValueNode value;
 
     public SafeWriteNode(ValueNode object, ValueNode value, LocationNode location) {
-        super(CiKind.Void, object, location);
+        super(object, location, StampFactory.forKind(CiKind.Void));
         this.value = value;
     }
 
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/UnsafeCastNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/UnsafeCastNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -34,30 +34,30 @@
  */
 public final class UnsafeCastNode extends FloatingNode implements Canonicalizable, Lowerable {
 
-    @Input private ValueNode x;
+    @Input private ValueNode object;
     @Data private RiResolvedType toType;
 
-    public ValueNode x() {
-        return x;
+    public ValueNode object() {
+        return object;
     }
 
-    public UnsafeCastNode(ValueNode x, RiResolvedType toType) {
+    public UnsafeCastNode(ValueNode object, RiResolvedType toType) {
         super(StampFactory.declared(toType));
-        this.x = x;
+        this.object = object;
         this.toType = toType;
     }
 
     @Override
     public ValueNode canonical(CanonicalizerTool tool) {
-        if (x != null && x.declaredType() != null && x.declaredType().isSubtypeOf(toType)) {
-            return x;
+        if (object != null && object.declaredType() != null && object.declaredType().isSubtypeOf(toType)) {
+            return object;
         }
         return this;
     }
 
     @Override
     public void lower(CiLoweringTool tool) {
-        ((StructuredGraph) graph()).replaceFloating(this, x);
+        ((StructuredGraph) graph()).replaceFloating(this, object);
     }
 
     @SuppressWarnings("unused")
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/ValueAnchorNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/ValueAnchorNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -48,7 +48,7 @@
 
     @Override
     public void generate(LIRGeneratorTool gen) {
-        // Nothing to emit, since this is node is used for structural purposes only.
+        // Nothing to emit, since this node is used for structural purposes only.
     }
 
     @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/WriteNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/WriteNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -25,6 +25,7 @@
 import com.oracle.max.cri.ci.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.type.*;
 
 
 public final class WriteNode extends AccessNode implements LIRLowerable {
@@ -35,7 +36,7 @@
     }
 
     public WriteNode(ValueNode object, ValueNode value, LocationNode location) {
-        super(CiKind.Void, object, location);
+        super(object, location, StampFactory.forKind(CiKind.Void));
         this.value = value;
     }
 
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/AccessIndexedNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/AccessIndexedNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -22,15 +22,17 @@
  */
 package com.oracle.graal.nodes.java;
 
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.spi.types.*;
+import com.oracle.graal.nodes.type.*;
 import com.oracle.max.cri.ci.*;
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.type.*;
 
 /**
  * The {@code AccessIndexedNode} class is the base class of instructions that read or write
  * elements of an array.
  */
-public abstract class AccessIndexedNode extends AccessArrayNode {
+public abstract class AccessIndexedNode extends AccessArrayNode implements TypeFeedbackProvider {
 
     @Input private ValueNode index;
     @Input private ValueNode length;
@@ -67,4 +69,10 @@
     public CiKind elementKind() {
         return elementType;
     }
+
+    @Override
+    public void typeFeedback(TypeFeedbackTool tool) {
+        tool.addScalar(index()).constantBound(Condition.GE, CiConstant.INT_0);
+        tool.addScalar(index()).valueBound(Condition.LT, length, tool.queryScalar(length));
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/ArrayLengthNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/ArrayLengthNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -41,7 +41,7 @@
     }
 
     public ArrayLengthNode(ValueNode array) {
-        super(StampFactory.intValue());
+        super(StampFactory.positiveInt());
         this.array = array;
     }
 
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -22,20 +22,22 @@
  */
 package com.oracle.graal.nodes.java;
 
+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.*;
-import com.oracle.graal.graph.*;
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.extended.*;
-import com.oracle.graal.nodes.spi.*;
-import com.oracle.graal.nodes.type.*;
 
 /**
  * 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;
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -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;
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/NewArrayNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/NewArrayNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -28,13 +28,15 @@
 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.spi.*;
+import com.oracle.graal.nodes.spi.types.*;
 import com.oracle.graal.nodes.type.*;
 
 /**
  * The {@code NewArrayNode} class is the base of all instructions that allocate arrays.
  */
-public abstract class NewArrayNode extends FixedWithNextNode implements EscapeAnalyzable{
+public abstract class NewArrayNode extends FixedWithNextNode implements EscapeAnalyzable, TypeFeedbackProvider {
 
     @Input private ValueNode length;
 
@@ -75,6 +77,12 @@
     public abstract RiResolvedType elementType();
 
     @Override
+    public void typeFeedback(TypeFeedbackTool tool) {
+        assert length.kind() == CiKind.Int;
+        tool.addScalar(length).constantBound(Condition.GE, CiConstant.INT_0);
+    }
+
+    @Override
     public Map<Object, Object> getDebugProperties() {
         Map<Object, Object> properties = super.getDebugProperties();
         properties.put("exactType", exactType());
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/NewMultiArrayNode.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/NewMultiArrayNode.java	Mon Mar 19 15:51:49 2012 -0700
@@ -22,17 +22,20 @@
  */
 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.spi.*;
+import com.oracle.graal.nodes.spi.types.*;
 import com.oracle.graal.nodes.type.*;
 
 /**
  * The {@code NewMultiArrayNode} represents an allocation of a multi-dimensional object
  * array.
  */
-public final class NewMultiArrayNode extends FixedWithNextNode implements LIRLowerable {
+public final class NewMultiArrayNode extends FixedWithNextNode implements LIRLowerable, TypeFeedbackProvider {
 
     @Input private final NodeInputList<ValueNode> dimensions;
     @Data private final RiResolvedType type;
@@ -67,4 +70,12 @@
     public RiResolvedType type() {
         return type;
     }
+
+    @Override
+    public void typeFeedback(TypeFeedbackTool tool) {
+        for (ValueNode length : dimensions) {
+            assert length.kind() == CiKind.Int;
+            tool.addScalar(length).constantBound(Condition.GE, CiConstant.INT_0);
+        }
+    }
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/CloneableTypeFeedback.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,28 @@
+/*
+ * 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;
+
+public interface CloneableTypeFeedback {
+
+    Object clone();
+}
--- /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	Mon Mar 19 15:51:49 2012 -0700
@@ -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);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ObjectTypeFeedbackStore.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,773 @@
+/*
+ * 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.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.*;
+
+public class ObjectTypeFeedbackStore extends TypeFeedbackStore<ObjectTypeFeedbackStore> implements ObjectTypeFeedbackTool, CloneableTypeFeedback {
+
+    private abstract static class BooleanPredicate <T> {
+        public abstract boolean evaluate(T element);
+    }
+
+    public static class Query implements ObjectTypeQuery {
+
+        private final ObjectTypeFeedbackStore store;
+
+        public Query(ObjectTypeFeedbackStore store) {
+            this.store = store;
+        }
+
+        @Override
+        public boolean constantBound(Condition condition, final CiConstant constant) {
+            assert condition == Condition.EQ || condition == Condition.NE;
+            if (condition == Condition.EQ) {
+                return store.prove(Equals.class, new BooleanPredicate<Equals>() {
+                    @Override
+                    public boolean evaluate(Equals element) {
+                        return element.constant.equals(constant);
+                    }
+                });
+            } else if (condition == Condition.NE) {
+                boolean result = store.prove(Equals.class, new BooleanPredicate<Equals>() {
+                    @Override
+                    public boolean evaluate(Equals element) {
+                        return !element.constant.equals(constant);
+                    }
+                });
+                if (result) {
+                    return true;
+                }
+                return store.prove(NotEquals.class, new BooleanPredicate<NotEquals>() {
+                    @Override
+                    public boolean evaluate(NotEquals element) {
+                        return element.constant.equals(constant);
+                    }
+                });
+            }
+            return false;
+        }
+
+        @Override
+        public boolean valueBound(Condition condition, ValueNode otherValue) {
+            Condition cond = store.valueBounds == null ? null : store.valueBounds.get(otherValue);
+            if (cond == null) {
+                return false;
+            } else {
+                return cond.implies(condition);
+            }
+        }
+
+        @Override
+        public boolean declaredType(final RiResolvedType type) {
+            return store.prove(Info.class, new BooleanPredicate<Info>() {
+                @Override
+                public boolean evaluate(Info element) {
+                    if (element instanceof ObjectType) {
+                        return ((ObjectType) element).type.isSubtypeOf(type);
+                    } else {
+                        return (element instanceof Equals) && ((Equals) element).constant.isNull();
+                    }
+                }
+            });
+        }
+
+        @Override
+        public boolean exactType(final RiResolvedType type) {
+            return store.prove(ObjectTypeExact.class, new BooleanPredicate<ObjectTypeExact>() {
+                @Override
+                public boolean evaluate(ObjectTypeExact element) {
+                    return type == element.type;
+                }
+            });
+        }
+
+        @Override
+        public boolean notDeclaredType(RiResolvedType type) {
+            return false;
+        }
+
+        @Override
+        public boolean notExactType(RiResolvedType type) {
+            return false;
+        }
+
+        @Override
+        public String toString() {
+            return store.toString();
+        }
+
+        @Override
+        public ObjectTypeFeedbackStore store() {
+            return store;
+        }
+
+        @Override
+        public Node dependency() {
+            return store.dependency;
+        }
+    }
+
+    private static final Info[] EMPTY_INFO_ARRAY = new Info[0];
+
+    private static class Info {
+
+    }
+
+    private static final class Equals extends Info {
+        public final CiConstant constant;
+
+        public Equals(CiConstant constant) {
+            this.constant = constant;
+        }
+
+        @Override
+        public String toString() {
+            return "== " + constant.asObject();
+        }
+    }
+
+    private static final class NotEquals extends Info {
+        public final CiConstant constant;
+
+        public NotEquals(CiConstant constant) {
+            this.constant = constant;
+        }
+
+        @Override
+        public String toString() {
+            return "!= " + constant.asObject();
+        }
+    }
+
+    private static class ObjectType extends Info {
+        public final RiResolvedType type;
+
+        public ObjectType(RiResolvedType type) {
+            this.type = type;
+        }
+    }
+
+    private static final class ObjectTypeDeclared extends ObjectType {
+
+        public ObjectTypeDeclared(RiResolvedType type) {
+            super(type);
+        }
+
+        @Override
+        public String toString() {
+            return "instanceof " + type;
+        }
+    }
+
+    private static final class ObjectTypeExact extends ObjectType {
+
+        public ObjectTypeExact(RiResolvedType type) {
+            super(type);
+        }
+
+        @Override
+        public String toString() {
+            return "exact " + type;
+        }
+    }
+
+    private static final class MergedTypeInfo extends Info {
+        public final Info[][] mergedInfos;
+
+        public MergedTypeInfo(Info[][] infos) {
+            mergedInfos = infos;
+        }
+
+        @Override
+        public String toString() {
+            return "merged type: [" + Arrays.deepToString(mergedInfos) + "]";
+        }
+    }
+
+    private final LinkedList<Info> infos = new LinkedList<>();
+    private HashMap<ValueNode, Condition> valueBounds;
+
+    private final TypeFeedbackChanged changed;
+
+    private Node dependency;
+
+    private void updateDependency() {
+        dependency = changed.node;
+    }
+
+    private static <T extends Info> boolean prove(Info[] infos, Class<T> clazz, IdentityHashMap<MergedTypeInfo, Boolean> cache, BooleanPredicate<T> predicate) {
+        for (Info info : infos) {
+            if (clazz.isAssignableFrom(info.getClass())) {
+                if (predicate.evaluate(clazz.cast(info))) {
+                    return true;
+                }
+            }
+            if (info instanceof MergedTypeInfo) {
+                if (cache.get(info) != null) {
+                    return cache.get(info);
+                }
+                for (Info[] subInfos : ((MergedTypeInfo) info).mergedInfos) {
+                    if (!prove(subInfos, clazz, cache, predicate)) {
+                        cache.put((MergedTypeInfo) info, false);
+                        return false;
+                    }
+                }
+                cache.put((MergedTypeInfo) info, true);
+                return true;
+            }
+        }
+        return false;
+    }
+
+    public <T extends Info> boolean prove(Class<T> clazz, BooleanPredicate<T> predicate) {
+        for (Info info : infos) {
+            if (clazz.isAssignableFrom(info.getClass())) {
+                if (predicate.evaluate(clazz.cast(info))) {
+                    return true;
+                }
+            }
+            if (info instanceof MergedTypeInfo) {
+                IdentityHashMap<MergedTypeInfo, Boolean> cache = new IdentityHashMap<>();
+                for (Info[] subInfos : ((MergedTypeInfo) info).mergedInfos) {
+                    if (!prove(subInfos, clazz, cache, predicate)) {
+                        return false;
+                    }
+                }
+                return true;
+            }
+        }
+        return false;
+    }
+
+    public ObjectTypeFeedbackStore(TypeFeedbackChanged changed) {
+        this.changed = changed;
+        this.dependency = null;
+    }
+
+    private ObjectTypeFeedbackStore(ObjectTypeFeedbackStore other) {
+        this.changed = other.changed;
+        if (other.valueBounds != null && !other.valueBounds.isEmpty()) {
+            valueBounds = new HashMap<>(other.valueBounds.size());
+            valueBounds.putAll(other.valueBounds);
+        }
+        infos.addAll(other.infos);
+        this.dependency = other.dependency;
+    }
+
+    @Override
+    public void constantBound(Condition condition, CiConstant constant) {
+        assert condition == Condition.EQ || condition == Condition.NE;
+
+        if (condition == Condition.EQ) {
+            if (infos.size() == 1 && infos.element() instanceof Equals && ((Equals) infos.element()).constant.equals(constant)) {
+                return;
+            }
+            infos.clear();
+            infos.add(new Equals(constant));
+            updateDependency();
+        } else if (condition == Condition.NE) {
+            for (ListIterator<Info> iter = infos.listIterator(); iter.hasNext();) {
+                int index = iter.nextIndex();
+                Info info = iter.next();
+                if (info instanceof NotEquals && ((NotEquals) info).constant.equals(constant)) {
+                    if (index == 0) {
+                        return;
+                    } else {
+                        iter.remove();
+                    }
+                }
+            }
+            infos.add(new NotEquals(constant));
+            updateDependency();
+        } else {
+            throw new GraalInternalError("unexpected condition: %s", condition);
+        }
+    }
+
+    @Override
+    public void valueBound(Condition condition, ValueNode otherValue) {
+        assert condition == Condition.EQ || condition == Condition.NE;
+
+        if (otherValue != null) {
+            if (valueBounds == null) {
+                valueBounds = new HashMap<>();
+            }
+            Condition cond = valueBounds.get(otherValue);
+            if (cond == null) {
+                valueBounds.put(otherValue, condition);
+                updateDependency();
+            } else {
+                Condition newCondition = cond.join(condition);
+                if (newCondition == null) {
+                    valueBounds.remove(otherValue);
+                } else {
+                    if (cond != newCondition) {
+                        valueBounds.put(otherValue, newCondition);
+                        updateDependency();
+                    }
+                }
+            }
+        }
+    }
+
+    @Override
+    public void declaredType(RiResolvedType type, boolean nonNull) {
+        assert type != null;
+
+        for (ListIterator<Info> iter = infos.listIterator(); iter.hasNext();) {
+            int index = iter.nextIndex();
+            Info info = iter.next();
+            if (info instanceof ObjectTypeDeclared) {
+                ObjectTypeDeclared typeInfo = (ObjectTypeDeclared) info;
+                if (typeInfo.type == type && index == 0) {
+                    if (index == 0) {
+                        if (nonNull) {
+                            constantBound(Condition.NE, CiConstant.NULL_OBJECT);
+                        }
+                        return;
+                    } else {
+                        iter.remove();
+                    }
+                }
+            }
+        }
+        infos.add(new ObjectTypeDeclared(type));
+        updateDependency();
+        if (nonNull) {
+            constantBound(Condition.NE, CiConstant.NULL_OBJECT);
+        }
+    }
+
+    @Override
+    public void exactType(RiResolvedType type) {
+        assert type != null;
+
+        for (ListIterator<Info> iter = infos.listIterator(); iter.hasNext();) {
+            int index = iter.nextIndex();
+            Info info = iter.next();
+            if (info instanceof ObjectTypeExact) {
+                ObjectTypeExact typeInfo = (ObjectTypeExact) info;
+                if (typeInfo.type == type && index == 0) {
+                    if (index == 0) {
+                        constantBound(Condition.NE, CiConstant.NULL_OBJECT);
+                        return;
+                    } else {
+                        iter.remove();
+                    }
+                }
+            }
+        }
+        infos.add(new ObjectTypeExact(type));
+        updateDependency();
+        constantBound(Condition.NE, CiConstant.NULL_OBJECT);
+    }
+
+    @Override
+    public void notDeclaredType(RiResolvedType type, boolean includesNull) {
+    }
+
+    @Override
+    public void notExactType(RiResolvedType type) {
+    }
+
+    public static ObjectTypeFeedbackStore meet(ObjectTypeFeedbackStore[] others) {
+        boolean emptyValueBounds = false;
+        for (int i = 0; i < others.length; i++) {
+            if (others[i] == null) {
+                return null;
+            }
+            if (others[i].valueBounds == null || others[i].valueBounds.isEmpty()) {
+                emptyValueBounds = true;
+            }
+        }
+
+        ObjectTypeFeedbackStore first = others[0];
+        ObjectTypeFeedbackStore result = new ObjectTypeFeedbackStore(first.changed);
+
+        if (!emptyValueBounds) {
+            for (Map.Entry<ValueNode, Condition> entry : first.valueBounds.entrySet()) {
+                Condition condition = entry.getValue();
+                for (int i = 1; i < others.length; i++) {
+                    Condition otherCond = others[i].valueBounds.get(entry.getKey());
+                    if (otherCond != null) {
+                        condition = null;
+                        break;
+                    }
+                    condition = condition.meet(otherCond);
+                    if (condition == null) {
+                        break;
+                    }
+                }
+                if (condition != null) {
+                    if (result.valueBounds == null) {
+                        result.valueBounds = new HashMap<>(first.valueBounds.size());
+                    }
+                    result.valueBounds.put(entry.getKey(), condition);
+                }
+            }
+        }
+
+        boolean simpleMerge = true;
+        for (int i = 1; i < others.length; i++) {
+            if (!others[i].infos.equals(others[i - 1].infos)) {
+                simpleMerge = false;
+                break;
+            }
+        }
+        if (simpleMerge) {
+            result.infos.addAll(others[0].infos);
+        } else {
+            Info[][] infos = new Info[others.length][];
+            for (int i = 0; i < others.length; i++) {
+                infos[i] = others[i].infos.toArray(EMPTY_INFO_ARRAY);
+            }
+            MergedTypeInfo merged = new MergedTypeInfo(infos);
+            result.infos.add(merged);
+        }
+        return result;
+    }
+
+    @Override
+    public ObjectTypeFeedbackStore clone() {
+        return new ObjectTypeFeedbackStore(this);
+    }
+
+    public ObjectTypeQuery query() {
+        return new Query(this);
+    }
+
+    public boolean isEmpty() {
+        return infos.isEmpty() && (valueBounds == null || valueBounds.isEmpty());
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder str = new StringBuilder();
+        for (Info info : infos) {
+            str.append(info).append(", ");
+        }
+        if (valueBounds != null) {
+            for (Map.Entry<ValueNode, Condition> entry : valueBounds.entrySet()) {
+                str.append(entry.getValue().operator).append(' ').append(entry.getKey()).append(", ");
+            }
+        }
+        if (str.length() > 1) {
+            str.setLength(str.length() - 2);
+        }
+        if (dependency != null) {
+            str.append(" @ ").append(dependency);
+        }
+        return str.toString();
+    }
+
+    /*
+//    equals contains all the values that might happen to be in this variable. If it is null then there is no information about possible values.
+//    If it is empty, then we're currently in a branch that will be removed by canonicalization later on.
+    private Set<CiConstant> equals;
+//    notEquals contains all the values that cannot be in this variable.
+    private Set<CiConstant> notEquals;
+
+    private HashMap<ValueNode, Condition> valueBounds;
+
+    private Set<RiResolvedType> exactTypes;
+
+    private Set<RiResolvedType> declaredTypes;
+    private final TypeFeedbackChanged changed;
+
+    private Node dependency;
+
+    private void updateDependency() {
+        dependency = changed.node;
+    }
+
+    public ObjectTypeFeedbackStore(TypeFeedbackChanged changed) {
+        this.changed = changed;
+        this.dependency = null;
+    }
+
+    private ObjectTypeFeedbackStore(ObjectTypeFeedbackStore other) {
+        this.changed = other.changed;
+        if (other.valueBounds != null && !other.valueBounds.isEmpty()) {
+            valueBounds = new HashMap<>(other.valueBounds.size());
+            valueBounds.putAll(other.valueBounds);
+        }
+        if (other.equals != null) {
+            equals = new HashSet<>(other.equals);
+        }
+        if (other.notEquals != null && !other.notEquals.isEmpty()) {
+            notEquals = new HashSet<>(other.notEquals);
+        }
+        this.dependency = other.dependency;
+    }
+
+    @Override
+    public void constantBound(Condition condition, CiConstant constant) {
+        assert condition == Condition.EQ || condition == Condition.NE;
+
+        if (condition == Condition.EQ) {
+            if (equals == null) {
+                equals = new HashSet<>();
+                equals.add(constant);
+                updateDependency();
+            } else {
+                if (equals.contains(constant)) {
+                    equals.clear();
+                    equals.add(constant);
+                    updateDependency();
+                } else {
+                    // join with a value that cannot exist: we're in a branch that will hopefully be canonicalized away
+                    equals.clear();
+                }
+            }
+        } else if (condition == Condition.NE) {
+            if (notEquals == null) {
+                notEquals = new HashSet<>();
+            }
+            if (equals != null && equals.contains(constant)) {
+                equals.remove(constant);
+            }
+            if (notEquals.add(constant)) {
+                updateDependency();
+            }
+        }
+    }
+
+    @Override
+    public void valueBound(Condition condition, ValueNode otherValue) {
+        assert condition == Condition.EQ || condition == Condition.NE;
+
+        if (otherValue != null) {
+            if (valueBounds == null) {
+                valueBounds = new HashMap<>();
+            }
+            Condition cond = valueBounds.get(otherValue);
+            if (cond == null) {
+                valueBounds.put(otherValue, condition);
+                updateDependency();
+            } else {
+                Condition newCondition = cond.join(condition);
+                if (newCondition == null) {
+                    valueBounds.remove(otherValue);
+                } else {
+                    if (cond != newCondition) {
+                        valueBounds.put(otherValue, newCondition);
+                        updateDependency();
+                    }
+                }
+            }
+        }
+    }
+
+    @Override
+    public void declaredType(RiResolvedType type, boolean nonNull) {
+        if (declaredTypes == null) {
+            declaredTypes = new HashSet<>();
+            declaredTypes.add(type);
+            updateDependency();
+        } else {
+            if (type.isInterface()) {
+                for (Iterator<RiResolvedType> iter = declaredTypes.iterator(); iter.hasNext();) {
+                    RiResolvedType declaredType = iter.next();
+                    if (declaredType.isInterface()) {
+                        if (type.isSubtypeOf(declaredType)) {
+                            iter.remove();
+                        } else if (declaredType.isSubtypeOf(type)) {
+                            // some more specific type is already in the list - nothing to do
+                            return;
+                        }
+                    }
+                }
+                if (declaredTypes.add(type)) {
+                    updateDependency();
+                }
+            } else {
+                for (Iterator<RiResolvedType> iter = declaredTypes.iterator(); iter.hasNext();) {
+                    RiResolvedType declaredType = iter.next();
+                    if (!declaredType.isInterface()) {
+                        if (type.isSubtypeOf(declaredType)) {
+                            iter.remove();
+                        } else if (declaredType.isSubtypeOf(type)) {
+                            // some more specific type is already in the list - nothing to do
+                            return;
+                        }
+                    }
+                }
+                if (declaredTypes.add(type)) {
+                    updateDependency();
+                }
+            }
+        }
+        if (nonNull) {
+            constantBound(Condition.NE, CiConstant.NULL_OBJECT);
+        }
+    }
+
+    @Override
+    public void exactType(RiResolvedType type) {
+        if (exactTypes == null) {
+            exactTypes = new HashSet<>();
+            exactTypes.add(type);
+            updateDependency();
+        } else {
+            if (exactTypes.contains(type)) {
+                exactTypes.clear();
+                exactTypes.add(type);
+                updateDependency();
+            } else {
+                // join with a value that cannot exist: we're in a branch that will hopefully be canonicalized away
+                exactTypes.clear();
+            }
+        }
+        constantBound(Condition.NE, CiConstant.NULL_OBJECT);
+    }
+
+    @Override
+    public void notDeclaredType(RiResolvedType type, boolean nonNull) {
+    }
+
+    @Override
+    public void notExactType(RiResolvedType type) {
+    }
+
+    @Override
+    public void meet(ObjectTypeFeedbackStore other) {
+        dependency = null;
+        if (equals != null && other.equals != null) {
+            equals.addAll(other.equals);
+        } else {
+            equals = null;
+        }
+        if (notEquals != null && !notEquals.isEmpty() && other.notEquals != null && !other.notEquals.isEmpty()) {
+            for (Iterator<CiConstant> iter = notEquals.iterator(); iter.hasNext();) {
+                CiConstant constant = iter.next();
+                if (!other.notEquals.contains(constant)) {
+                    iter.remove();
+                }
+            }
+        } else {
+            notEquals = null;
+        }
+        if (valueBounds != null && !valueBounds.isEmpty() && other.valueBounds != null && !other.valueBounds.isEmpty()) {
+            HashMap<ValueNode, Condition> newBounds = new HashMap<>(valueBounds.size());
+            for (Map.Entry<ValueNode, Condition> entry : valueBounds.entrySet()) {
+                Condition otherCond = other.valueBounds.get(entry.getKey());
+                if (otherCond != null) {
+                    Condition newCondition = entry.getValue().meet(otherCond);
+                    if (newCondition != null) {
+                        newBounds.put(entry.getKey(), newCondition);
+                    }
+                }
+            }
+            if (newBounds.isEmpty()) {
+                valueBounds = null;
+            } else {
+                valueBounds = newBounds;
+            }
+        } else {
+            valueBounds = null;
+        }
+        declaredTypes = null;
+        exactTypes = null;
+    }
+
+    @Override
+    public ObjectTypeFeedbackStore clone() {
+        return new ObjectTypeFeedbackStore(this);
+    }
+
+    public ObjectTypeQuery query() {
+        return new Query(this);
+    }
+
+    public boolean isEmpty() {
+        return equals == null && (notEquals == null || notEquals.isEmpty()) && (valueBounds == null || valueBounds.isEmpty());
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder str = new StringBuilder();
+        if (equals != null && !equals.isEmpty()) {
+            str.append("== ");
+            if (equals.size() == 1) {
+                str.append(equals.iterator().next());
+            } else {
+                str.append("(");
+                for (CiConstant constant : equals) {
+                    str.append(constant).append(',');
+                }
+                str.setLength(str.length() - 1);
+                str.append(')');
+            }
+            str.append(", ");
+        }
+        if (notEquals != null && !notEquals.isEmpty()) {
+            str.append("!= ");
+            if (notEquals.size() == 1) {
+                str.append(notEquals.iterator().next());
+            } else {
+                str.append("(");
+                for (CiConstant constant : notEquals) {
+                    str.append(constant).append(',');
+                }
+                str.setLength(str.length() - 1);
+                str.append(')');
+            }
+            str.append(", ");
+        }
+        if (valueBounds != null) {
+            for (Map.Entry<ValueNode, Condition> entry : valueBounds.entrySet()) {
+                str.append(entry.getValue().operator).append(' ').append(entry.getKey()).append(", ");
+            }
+        }
+        if (declaredTypes != null) {
+            str.append("declared (");
+            for (RiResolvedType type: declaredTypes) {
+                str.append(type).append(',');
+            }
+            str.setLength(str.length() - 1);
+            str.append("), ");
+        }
+        if (exactTypes != null) {
+            str.append("exact (");
+            for (RiResolvedType type: exactTypes) {
+                str.append(type).append(',');
+            }
+            str.setLength(str.length() - 1);
+            str.append("), ");
+        }
+        if (str.length() > 1) {
+            str.setLength(str.length() - 2);
+        }
+        if (dependency != null) {
+            str.append(" @ ").append(dependency);
+        }
+        return str.toString();
+    }*/
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ObjectTypeFeedbackTool.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,43 @@
+/*
+ * 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 com.oracle.max.cri.ci.*;
+import com.oracle.max.cri.ri.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
+
+public interface ObjectTypeFeedbackTool {
+
+    void constantBound(Condition condition, CiConstant constant);
+
+    void valueBound(Condition condition, ValueNode otherValue);
+
+    void declaredType(RiResolvedType type, boolean nonNull);
+
+    void exactType(RiResolvedType type);
+
+    void notDeclaredType(RiResolvedType type, boolean includesNull);
+
+    void notExactType(RiResolvedType type);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ObjectTypeQuery.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,45 @@
+/*
+ * 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 com.oracle.max.cri.ci.*;
+import com.oracle.max.cri.ri.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
+
+public interface ObjectTypeQuery extends TypeQuery {
+
+    boolean constantBound(Condition condition, CiConstant constant);
+
+    boolean valueBound(Condition condition, ValueNode otherValue);
+
+    boolean declaredType(RiResolvedType type);
+
+    boolean exactType(RiResolvedType type);
+
+    boolean notDeclaredType(RiResolvedType type);
+
+    boolean notExactType(RiResolvedType type);
+
+    ObjectTypeFeedbackStore store();
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ScalarTypeFeedbackStore.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,409 @@
+/*
+ * 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.nodes.calc.*;
+import com.oracle.max.cri.ci.*;
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.*;
+
+public class ScalarTypeFeedbackStore extends TypeFeedbackStore<ScalarTypeFeedbackStore> implements ScalarTypeFeedbackTool, CloneableTypeFeedback {
+
+    public static class Query implements ScalarTypeQuery {
+
+        private final ScalarTypeFeedbackStore store;
+
+        public Query(ScalarTypeFeedbackStore store) {
+            this.store = store;
+        }
+
+        @Override
+        public boolean constantBound(Condition condition, CiConstant constant) {
+            if (constant.kind == CiKind.Int || constant.kind == CiKind.Long) {
+                switch (condition) {
+                    case EQ:
+                        return store.constantBounds.lowerBound == constant.asLong() && store.constantBounds.upperBound == constant.asLong();
+                    case NE:
+                        return store.constantBounds.lowerBound > constant.asLong() || store.constantBounds.upperBound < constant.asLong();
+                    case LT:
+                        return store.constantBounds.upperBound < constant.asLong();
+                    case LE:
+                        return store.constantBounds.upperBound <= constant.asLong();
+                    case GT:
+                        return store.constantBounds.lowerBound > constant.asLong();
+                    case GE:
+                        return store.constantBounds.lowerBound >= constant.asLong();
+                    case BT:
+                        return constant.asLong() >= 0 && store.constantBounds.upperBound < constant.asLong() && store.constantBounds.lowerBound >= 0;
+                    case BE:
+                        return constant.asLong() >= 0 && store.constantBounds.upperBound <= constant.asLong() && store.constantBounds.lowerBound >= 0;
+                    case AT:
+                        return constant.asLong() < 0 && store.constantBounds.lowerBound > constant.asLong() && store.constantBounds.upperBound < 0;
+                    case AE:
+                        return constant.asLong() < 0 && store.constantBounds.lowerBound >= constant.asLong() && store.constantBounds.upperBound < 0;
+                }
+            }
+            return false;
+        }
+
+        @Override
+        public boolean valueBound(Condition condition, ValueNode otherValue) {
+            Condition cond = store.valueBounds == null ? null : store.valueBounds.get(otherValue);
+            if (cond == null) {
+                return false;
+            } else {
+                return cond.implies(condition);
+            }
+        }
+
+        @Override
+        public String toString() {
+            return store.toString();
+        }
+
+        @Override
+        public ScalarTypeFeedbackStore store() {
+            return store;
+        }
+
+        @Override
+        public Node dependency() {
+            return store.dependency;
+        }
+    }
+
+    private static class ConstantBound {
+
+        public long lowerBound;
+        public long upperBound;
+
+        public ConstantBound(long lowerBound, long upperBound) {
+            this.lowerBound = lowerBound;
+            this.upperBound = upperBound;
+        }
+
+        public void meet(ConstantBound other) {
+            lowerBound = Math.min(lowerBound, other.lowerBound);
+            upperBound = Math.max(upperBound, other.upperBound);
+        }
+
+        public boolean join(ConstantBound other) {
+            long oldLower = lowerBound;
+            long oldUpper = upperBound;
+            lowerBound = Math.max(lowerBound, other.lowerBound);
+            upperBound = Math.min(upperBound, other.upperBound);
+            return oldLower != lowerBound || oldUpper != upperBound;
+        }
+    }
+
+    private final CiKind kind;
+    private final ConstantBound constantBounds;
+    private final TypeFeedbackChanged changed;
+    private Node dependency;
+    private HashMap<ValueNode, Condition> valueBounds;
+
+    private void updateDependency() {
+        dependency = changed.node;
+    }
+
+    public ScalarTypeFeedbackStore(CiKind kind, TypeFeedbackChanged changed) {
+        this.kind = kind;
+        if (kind == CiKind.Int) {
+            constantBounds = new ConstantBound(Integer.MIN_VALUE, Integer.MAX_VALUE);
+        } else if (kind == CiKind.Long) {
+            constantBounds = new ConstantBound(Long.MIN_VALUE, Long.MAX_VALUE);
+        } else {
+            constantBounds = null;
+        }
+        this.changed = changed;
+        this.dependency = null;
+    }
+
+    private ScalarTypeFeedbackStore(ScalarTypeFeedbackStore other) {
+        this.kind = other.kind;
+        if (other.constantBounds == null) {
+            constantBounds = null;
+        } else {
+            constantBounds = new ConstantBound(other.constantBounds.lowerBound, other.constantBounds.upperBound);
+        }
+        if (other.valueBounds != null && !other.valueBounds.isEmpty()) {
+            valueBounds = new HashMap<>(other.valueBounds.size());
+            valueBounds.putAll(other.valueBounds);
+        }
+        this.changed = other.changed;
+        this.dependency = other.dependency;
+    }
+
+    @Override
+    public void constantBound(Condition condition, CiConstant constant) {
+        ConstantBound newBound = createBounds(condition, constant);
+        if (newBound != null) {
+            if (constantBounds.join(newBound)) {
+                updateDependency();
+            }
+        }
+    }
+
+    private static ConstantBound createBounds(Condition condition, CiConstant constant) {
+        ConstantBound newBound;
+        if (constant.kind == CiKind.Int || constant.kind == CiKind.Long) {
+            switch (condition) {
+                case EQ:
+                    newBound = new ConstantBound(constant.asLong(), constant.asLong());
+                    break;
+                case NE:
+                    newBound = null;
+                    break;
+                case GT:
+                    newBound = new ConstantBound(constant.asLong() + 1, Long.MAX_VALUE);
+                    break;
+                case GE:
+                    newBound = new ConstantBound(constant.asLong(), Long.MAX_VALUE);
+                    break;
+                case LT:
+                    newBound = new ConstantBound(Long.MIN_VALUE, constant.asLong() - 1);
+                    break;
+                case LE:
+                    newBound = new ConstantBound(Long.MIN_VALUE, constant.asLong());
+                    break;
+                default:
+                    newBound = null;
+                    break;
+            }
+        } else {
+            newBound = null;
+        }
+        return newBound;
+    }
+
+    private void simpleValueBound(Condition condition, ValueNode otherValue) {
+        if (otherValue != null) {
+            if (valueBounds == null) {
+                valueBounds = new HashMap<>();
+            }
+            Condition cond = valueBounds.get(otherValue);
+            if (cond == null) {
+                valueBounds.put(otherValue, condition);
+                updateDependency();
+            } else {
+                Condition newCondition = cond.join(condition);
+                if (newCondition == null) {
+                    valueBounds.remove(otherValue);
+                } else {
+                    if (cond != newCondition) {
+                        valueBounds.put(otherValue, newCondition);
+                        updateDependency();
+                    }
+                }
+            }
+        }
+    }
+
+    @Override
+    public void valueBound(Condition condition, ValueNode otherValue, ScalarTypeQuery type) {
+        ScalarTypeFeedbackStore other = type.store();
+        switch (condition) {
+            case EQ:
+                simpleValueBound(condition, otherValue);
+                if (constantBounds.join(other.constantBounds)) {
+                    updateDependency();
+                }
+                break;
+            case NE:
+                simpleValueBound(condition, otherValue);
+                break;
+            case LE:
+            case LT:
+                simpleValueBound(condition, otherValue);
+                constantBound(condition, new CiConstant(kind, other.constantBounds.upperBound));
+                break;
+            case GE:
+            case GT:
+                simpleValueBound(condition, otherValue);
+                constantBound(condition, new CiConstant(kind, other.constantBounds.lowerBound));
+                break;
+            case BT:
+                if (other.constantBounds.lowerBound >= 0) {
+                    simpleValueBound(Condition.LT, otherValue);
+                    constantBound(Condition.GE, new CiConstant(kind, 0));
+                    constantBound(Condition.LT, new CiConstant(kind, other.constantBounds.upperBound));
+                }
+                break;
+            case BE:
+                if (other.constantBounds.lowerBound >= 0) {
+                    simpleValueBound(Condition.LE, otherValue);
+                    constantBound(Condition.GE, new CiConstant(kind, 0));
+                    constantBound(Condition.LE, new CiConstant(kind, other.constantBounds.upperBound));
+                }
+                break;
+            case AT:
+                if (other.constantBounds.upperBound < 0) {
+                    simpleValueBound(Condition.GT, otherValue);
+                    constantBound(Condition.LT, new CiConstant(kind, 0));
+                    constantBound(Condition.GT, new CiConstant(kind, other.constantBounds.lowerBound));
+                }
+                break;
+            case AE:
+                if (other.constantBounds.upperBound < 0) {
+                    simpleValueBound(Condition.GE, otherValue);
+                    constantBound(Condition.LT, new CiConstant(kind, 0));
+                    constantBound(Condition.GE, new CiConstant(kind, other.constantBounds.lowerBound));
+                }
+                break;
+        }
+    }
+
+    public ScalarTypeQuery query() {
+        return new Query(this);
+    }
+
+    public static ScalarTypeFeedbackStore meet(ScalarTypeFeedbackStore[] others) {
+        boolean emptyValueBounds = false;
+        for (int i = 0; i < others.length; i++) {
+            if (others[i] == null) {
+                return null;
+            }
+            if (others[i].valueBounds == null || others[i].valueBounds.isEmpty()) {
+                emptyValueBounds = true;
+            }
+        }
+
+        ScalarTypeFeedbackStore first = others[0];
+        ScalarTypeFeedbackStore result = new ScalarTypeFeedbackStore(first.kind, first.changed);
+
+        if (!emptyValueBounds) {
+            for (Map.Entry<ValueNode, Condition> entry : first.valueBounds.entrySet()) {
+                Condition condition = entry.getValue();
+                for (int i = 1; i < others.length; i++) {
+                    Condition otherCond = others[i].valueBounds.get(entry.getKey());
+                    if (otherCond != null) {
+                        condition = null;
+                        break;
+                    }
+                    condition = condition.meet(otherCond);
+                    if (condition == null) {
+                        break;
+                    }
+                }
+                if (condition != null) {
+                    if (result.valueBounds == null) {
+                        result.valueBounds = new HashMap<>(first.valueBounds.size());
+                    }
+                    result.valueBounds.put(entry.getKey(), condition);
+                }
+            }
+        }
+
+        result.constantBounds.lowerBound = first.constantBounds.lowerBound;
+        result.constantBounds.upperBound = first.constantBounds.upperBound;
+
+        for (int i = 1; i < others.length; i++) {
+            result.constantBounds.meet(others[i].constantBounds);
+        }
+        return result;
+    }
+
+    @Override
+    public ScalarTypeFeedbackStore clone() {
+        return new ScalarTypeFeedbackStore(this);
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder str = new StringBuilder().append('(');
+        if (constantBounds.lowerBound == minValue(kind)) {
+            str.append('-');
+        } else {
+            str.append(constantBounds.lowerBound);
+        }
+        str.append(',');
+        if (constantBounds.upperBound == maxValue(kind)) {
+            str.append('-');
+        } else {
+            str.append(constantBounds.upperBound);
+        }
+        str.append(')');
+
+        if (valueBounds != null) {
+            for (Map.Entry<ValueNode, Condition> entry : valueBounds.entrySet()) {
+                str.append(", ").append(entry.getValue().operator).append(' ').append(entry.getKey());
+            }
+        }
+        if (dependency != null) {
+            str.append(" @ ").append(dependency);
+        }
+        return str.toString();
+    }
+
+    @Override
+    public void setTranslated(CiConstant deltaConstant, ScalarTypeQuery old) {
+        assert deltaConstant.kind == kind;
+        ScalarTypeFeedbackStore other = old.store();
+        assert other.kind == kind;
+        long lower = other.constantBounds.lowerBound;
+        long upper = other.constantBounds.upperBound;
+        if (kind == CiKind.Int) {
+            int delta = deltaConstant.asInt();
+            int newLower = (int) lower + delta;
+            int newUpper = (int) upper + delta;
+            if ((newLower <= lower && newUpper <= upper) || (newLower > lower && newUpper > upper)) {
+                constantBounds.join(new ConstantBound(newLower, newUpper));
+            }
+        } else if (kind == CiKind.Long) {
+            long delta = deltaConstant.asLong();
+            long newLower = lower + delta;
+            long newUpper = upper + delta;
+            if ((newLower <= lower && newUpper <= upper) || (newLower > lower && newUpper > upper)) {
+                constantBounds.join(new ConstantBound(newLower, newUpper));
+            }
+        } else {
+            // nothing yet
+        }
+    }
+
+    public boolean isEmpty() {
+        return constantBounds.lowerBound == minValue(kind) && constantBounds.upperBound == maxValue(kind) && (valueBounds == null || valueBounds.isEmpty());
+    }
+
+    private static long minValue(CiKind kind) {
+        if (kind == CiKind.Int) {
+            return Integer.MIN_VALUE;
+        } else if (kind == CiKind.Long) {
+            return Long.MIN_VALUE;
+        } else {
+            throw new UnsupportedOperationException();
+        }
+    }
+
+    private static long maxValue(CiKind kind) {
+        if (kind == CiKind.Int) {
+            return Integer.MAX_VALUE;
+        } else if (kind == CiKind.Long) {
+            return Long.MAX_VALUE;
+        } else {
+            throw new UnsupportedOperationException();
+        }
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ScalarTypeFeedbackTool.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,36 @@
+/*
+ * 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 com.oracle.max.cri.ci.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
+
+public interface ScalarTypeFeedbackTool {
+
+    void constantBound(Condition condition, CiConstant constant);
+
+    void valueBound(Condition condition, ValueNode otherValue, ScalarTypeQuery type);
+
+    void setTranslated(CiConstant delta, ScalarTypeQuery old);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ScalarTypeQuery.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,36 @@
+/*
+ * 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 com.oracle.max.cri.ci.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
+
+public interface ScalarTypeQuery extends TypeQuery {
+
+    boolean constantBound(Condition condition, CiConstant constant);
+
+    boolean valueBound(Condition condition, ValueNode otherValue);
+
+    ScalarTypeFeedbackStore store();
+}
--- /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	Mon Mar 19 15:51:49 2012 -0700
@@ -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);
+}
--- /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	Mon Mar 19 15:51:49 2012 -0700
@@ -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);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeFeedbackChanged.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,31 @@
+/*
+ * 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 com.oracle.graal.graph.*;
+
+public class TypeFeedbackChanged {
+
+    public Node node;
+
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeFeedbackProvider.java	Mon Mar 19 15:51:49 2012 -0700
@@ -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 TypeFeedbackProvider {
+
+    void typeFeedback(TypeFeedbackTool tool);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeFeedbackStore.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,28 @@
+/*
+ * 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;
+
+
+public abstract class TypeFeedbackStore<T> {
+
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeFeedbackTool.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,42 @@
+/*
+ * 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 com.oracle.max.cri.ri.*;
+import com.oracle.graal.nodes.*;
+
+public interface TypeFeedbackTool {
+
+    ScalarTypeFeedbackTool addScalar(ValueNode value);
+
+    ObjectTypeFeedbackTool addObject(ValueNode value);
+
+    ScalarTypeQuery queryScalar(ValueNode value);
+
+    ObjectTypeQuery queryObject(ValueNode value);
+
+    RiRuntime runtime();
+
+    TypeFeedbackTool negate();
+
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeQuery.java	Mon Mar 19 15:51:49 2012 -0700
@@ -0,0 +1,31 @@
+/*
+ * 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 com.oracle.graal.graph.*;
+
+public interface TypeQuery {
+
+    Node dependency();
+}
+
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/Stamp.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/Stamp.java	Mon Mar 19 15:51:49 2012 -0700
@@ -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	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java	Mon Mar 19 15:51:49 2012 -0700
@@ -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);
         }
     }
 
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java	Mon Mar 19 15:51:49 2012 -0700
@@ -60,9 +60,8 @@
                 loopend.predecessor().replaceFirstSuccessor(loopend, null);
                 loopend.safeDelete();
             }
-            FixedNode next = begin.next();
+            killCFG(begin.next());
             begin.safeDelete();
-            killCFG(next);
         } else if (merge instanceof LoopBeginNode && ((LoopBeginNode) merge).loopEnds().isEmpty()) { // not a loop anymore
             ((StructuredGraph) end.graph()).reduceDegenerateLoopBegin((LoopBeginNode) merge);
         } else if (merge.phiPredecessorCount() == 1) { // not a merge anymore
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BasicIdealGraphPrinter.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BasicIdealGraphPrinter.java	Mon Mar 19 15:51:49 2012 -0700
@@ -297,6 +297,20 @@
                             assert false;
                     }
                     break;
+                case '\u0000': case '\u0001': case '\u0002': case '\u0003':
+                case '\u0004': case '\u0005': case '\u0006': case '\u0007':
+                case '\u0008': case '\u000b': case '\u000c': case '\u000e':
+                case '\u000f': case '\u0010': case '\u0011': case '\u0012':
+                case '\u0013': case '\u0014': case '\u0015': case '\u0016':
+                case '\u0017': case '\u0018': case '\u0019': case '\u001a':
+                case '\u001b': case '\u001c': case '\u001d': case '\u001e':
+                case '\u001f':
+                    if (str == null) {
+                        str = new StringBuilder();
+                        str.append(s, 0, i);
+                    }
+                    str.append("'0x").append(Integer.toHexString(c));
+                    break;
                 default:
                     if (str != null) {
                         str.append(c);
--- a/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/GraphTest.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/GraphTest.java	Mon Mar 19 15:51:49 2012 -0700
@@ -56,6 +56,7 @@
     protected final GraalRuntime runtime;
 
     public GraphTest() {
+        Debug.enable();
         this.runtime = GraalRuntimeAccess.getGraalRuntime();
     }
 
@@ -63,7 +64,7 @@
         if (expected.getNodeCount() != graph.getNodeCount()) {
             Debug.dump(expected, "Node count not matching - expected");
             Debug.dump(graph, "Node count not matching - actual");
-            Assert.fail("Graphs do not have the same number of nodes");
+            Assert.fail("Graphs do not have the same number of nodes: " + expected.getNodeCount() + " vs. " + graph.getNodeCount());
         }
     }
 
--- a/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/ScalarTypeSystemTest.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/ScalarTypeSystemTest.java	Mon Mar 19 15:51:49 2012 -0700
@@ -27,6 +27,7 @@
 import org.junit.*;
 
 import com.oracle.graal.compiler.phases.*;
+import com.oracle.graal.compiler.types.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.nodes.*;
 
@@ -43,7 +44,7 @@
         }
     }
 
-    @Test(expected = AssertionFailedError.class)
+    @Test
     public void test1() {
         test("test1Snippet", "referenceSnippet1");
     }
@@ -60,7 +61,7 @@
         }
     }
 
-    @Test(expected = AssertionFailedError.class)
+    @Test
     public void test2() {
         test("test2Snippet", "referenceSnippet1");
     }
@@ -77,7 +78,7 @@
         }
     }
 
-    @Test(expected = AssertionFailedError.class)
+    @Test
     public void test3() {
         test("test3Snippet", "referenceSnippet2");
     }
@@ -102,7 +103,7 @@
         }
     }
 
-    @Test(expected = AssertionFailedError.class)
+    @Test
     public void test4() {
         test("test4Snippet", "referenceSnippet2");
     }
@@ -119,7 +120,7 @@
         }
     }
 
-    @Test(expected = AssertionFailedError.class)
+    @Test
     public void test5() {
         test("test5Snippet", "referenceSnippet3");
     }
@@ -162,9 +163,12 @@
     }
 
     private void test(String snippet, String referenceSnippet) {
+
         StructuredGraph graph = parse(snippet);
         Debug.dump(graph, "Graph");
+        System.out.println("==================== " + snippet);
         new CanonicalizerPhase(null, runtime(), null).apply(graph);
+        new PropagateTypeCachePhase(null, null, null).apply(graph);
         StructuredGraph referenceGraph = parse(referenceSnippet);
         assertEquals(referenceGraph, graph);
     }
--- a/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/TypeSystemTest.java	Mon Mar 19 15:47:35 2012 -0700
+++ b/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/TypeSystemTest.java	Mon Mar 19 15:51:49 2012 -0700
@@ -22,14 +22,21 @@
  */
 package com.oracle.graal.compiler.tests;
 
+import java.io.*;
+
+import junit.framework.Assert;
+
 import org.junit.*;
 
 import com.oracle.graal.compiler.phases.*;
+import com.oracle.graal.compiler.schedule.*;
 import com.oracle.graal.compiler.types.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
+import com.oracle.graal.lir.cfg.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.java.*;
+import com.oracle.graal.printer.*;
 
 /**
  * In the following tests, the scalar type system of the compiler should be complete enough to see the relation between the different conditions.
@@ -60,12 +67,181 @@
         return 1;
     }
 
+    @Test
+    public void test3() {
+        test("test3Snippet", "referenceSnippet3");
+    }
+
+    public static int referenceSnippet3(Object o) {
+        if (o == null) {
+            return 1;
+        } else {
+            return 2;
+        }
+    }
+
+    @SuppressWarnings("unused")
+    public static int test3Snippet(Object o) {
+        if (o == null) {
+            if (o != null) {
+                return 3;
+            } else {
+                return 1;
+            }
+        } else {
+            return 2;
+        }
+    }
+
+    @Test
+    public void test4() {
+        test("test4Snippet", "referenceSnippet3");
+    }
+
+    public static final Object constantObject1 = "1";
+    public static final Object constantObject2 = "2";
+    public static final Object constantObject3 = "3";
+
+    public static int test4Snippet(Object o) {
+        if (o == null) {
+            if (o == constantObject1) {
+                return 3;
+            } else {
+                return 1;
+            }
+        } else {
+            return 2;
+        }
+    }
+
+//    @Test
+    public void test5() {
+        test("test5Snippet", "referenceSnippet5");
+    }
+
+    public static int referenceSnippet5(Object o, Object a) {
+        if (o == null) {
+            if (a == constantObject1 || a == constantObject2) {
+                return 1;
+            }
+        } else {
+            if (a == constantObject2 || a == constantObject3) {
+                if (a != null) {
+                    return 11;
+                }
+                return 2;
+            }
+        }
+        if (a == constantObject1) {
+            return 3;
+        }
+        return 5;
+    }
+
+    public static int test5Snippet(Object o, Object a) {
+        if (o == null) {
+            if (a == constantObject1 || a == constantObject2) {
+                if (a == null) {
+                    return 10;
+                }
+                return 1;
+            }
+        } else {
+            if (a == constantObject2 || a == constantObject3) {
+                if (a != null) {
+                    return 11;
+                }
+                return 2;
+            }
+        }
+        if (a == constantObject1) {
+            return 3;
+        }
+        if (a == constantObject2) {
+            return 4;
+        }
+        return 5;
+    }
+
+    @Test
+    public void test6() {
+        test("test6Snippet", CheckCastNode.class);
+    }
+
+    public static int test6Snippet(int i) throws IOException {
+        Object o = null;
+
+        if (i == 5) {
+            o = new FileInputStream("asdf");
+        }
+        if (i < 10) {
+            o = new ByteArrayInputStream(new byte[]{1, 2, 3});
+        }
+        if (i > 0) {
+            o = new BufferedInputStream(null);
+        }
+
+        return ((InputStream) o).available();
+    }
+
+    private void test(String snippet, String referenceSnippet) {
+
+        StructuredGraph graph = parse(snippet);
+        Debug.dump(graph, "Graph");
+        System.out.println("==================== " + snippet);
+        new CanonicalizerPhase(null, runtime(), null).apply(graph);
+        new PropagateTypeCachePhase(null, runtime(), null).apply(graph);
+        new CanonicalizerPhase(null, runtime(), null).apply(graph);
+        new GlobalValueNumberingPhase().apply(graph);
+        StructuredGraph referenceGraph = parse(referenceSnippet);
+        new CanonicalizerPhase(null, runtime(), null).apply(referenceGraph);
+        new GlobalValueNumberingPhase().apply(referenceGraph);
+        assertEquals(referenceGraph, graph);
+    }
+
+    @Override
+    protected void assertEquals(StructuredGraph expected, StructuredGraph graph) {
+        if (expected.getNodeCount() != graph.getNodeCount()) {
+            Debug.dump(expected, "Node count not matching - expected");
+            Debug.dump(graph, "Node count not matching - actual");
+            System.out.println("================ expected");
+            outputGraph(expected);
+            System.out.println("================ actual");
+            outputGraph(graph);
+            new IdealGraphPrinterDumpHandler().dump(graph, "asdf");
+            Assert.fail("Graphs do not have the same number of nodes: " + expected.getNodeCount() + " vs. " + graph.getNodeCount());
+        }
+    }
+
+    public static void outputGraph(StructuredGraph graph) {
+        SchedulePhase schedule = new SchedulePhase();
+        schedule.apply(graph);
+        for (Block block : schedule.getCFG().getBlocks()) {
+            System.out.print("Block " + block + " ");
+            if (block == schedule.getCFG().getStartBlock()) {
+                System.out.print("* ");
+            }
+            System.out.print("-> ");
+            for (Block succ : block.getSuccessors()) {
+                System.out.print(succ + " ");
+            }
+            System.out.println();
+            for (Node node : schedule.getNodesFor().get(block)) {
+                System.out.println("  " + node + "    (" + node.usages().size() + ")");
+            }
+        }
+    }
+
+
     private <T extends Node & Node.IterableNodeType> void test(String snippet, Class<T> clazz) {
         StructuredGraph graph = parse(snippet);
         Debug.dump(graph, "Graph");
         new CanonicalizerPhase(null, runtime(), null).apply(graph);
-        new PropagateTypesPhase(null, null, null).apply(graph);
+        new PropagateTypeCachePhase(null, runtime(), null).apply(graph);
         Debug.dump(graph, "Graph");
+        if (graph.getNodes(clazz).iterator().hasNext()) {
+            outputGraph(graph);
+        }
         Assert.assertFalse("shouldn't have nodes of type " + clazz, graph.getNodes(clazz).iterator().hasNext());
     }
 }
--- a/hotspot/.cproject	Mon Mar 19 15:47:35 2012 -0700
+++ b/hotspot/.cproject	Mon Mar 19 15:51:49 2012 -0700
@@ -20,7 +20,7 @@
 					<folderInfo id="cdt.managedbuild.toolchain.gnu.solaris.base.945602881.305678577" name="/" resourcePath="">
 						<toolChain id="cdt.managedbuild.toolchain.gnu.base.1866612258" name="Linux GCC" superClass="cdt.managedbuild.toolchain.gnu.base">
 							<targetPlatform archList="all" binaryParser="org.eclipse.cdt.core.ELF" id="cdt.managedbuild.target.gnu.platform.base.2075405295" name="Debug Platform" osList="linux,hpux,aix,qnx" superClass="cdt.managedbuild.target.gnu.platform.base"/>
-							<builder arguments="${workspace_loc:/hotspot}/../mxtool/mx build" autoBuildTarget="debug" buildPath="${workspace_loc:/hotspot}/.." cleanBuildTarget="clean" command="bash" enableAutoBuild="true" enableCleanBuild="false" enabledIncrementalBuild="false" id="cdt.managedbuild.target.gnu.builder.base.81453037" incrementalBuildTarget="jvmg1" keepEnvironmentInBuildfile="false" managedBuildOn="false" name="Gnu Make Builder" parallelizationNumber="1" superClass="cdt.managedbuild.target.gnu.builder.base">
+							<builder arguments="${workspace_loc:/hotspot}/../mxtool/mx build" autoBuildTarget="ide-build-target" buildPath="${workspace_loc:/hotspot}/.." cleanBuildTarget="clean" command="bash" enableAutoBuild="true" enableCleanBuild="false" enabledIncrementalBuild="false" id="cdt.managedbuild.target.gnu.builder.base.81453037" incrementalBuildTarget="jvmg1" keepEnvironmentInBuildfile="false" managedBuildOn="false" name="Gnu Make Builder" parallelizationNumber="1" superClass="cdt.managedbuild.target.gnu.builder.base">
 								<outputEntries>
 									<entry flags="VALUE_WORKSPACE_PATH|RESOLVED" kind="outputPath" name=""/>
 								</outputEntries>
@@ -80,6 +80,7 @@
 			<storageModule moduleId="org.eclipse.cdt.internal.ui.text.commentOwnerProjectMappings"/>
 			<storageModule moduleId="org.eclipse.cdt.core.language.mapping"/>
 			<storageModule moduleId="org.eclipse.cdt.make.core.buildtargets"/>
+			<storageModule moduleId="scannerConfiguration"/>
 		</cconfiguration>
 	</storageModule>
 	<storageModule moduleId="cdtBuildSystem" version="4.0.0">
--- a/hotspot/.project	Mon Mar 19 15:47:35 2012 -0700
+++ b/hotspot/.project	Mon Mar 19 15:51:49 2012 -0700
@@ -23,7 +23,7 @@
 				</dictionary>
 				<dictionary>
 					<key>org.eclipse.cdt.make.core.autoBuildTarget</key>
-					<value>debug</value>
+					<value>ide-build-target</value>
 				</dictionary>
 				<dictionary>
 					<key>org.eclipse.cdt.make.core.buildArguments</key>
--- a/mx/commands.py	Mon Mar 19 15:47:35 2012 -0700
+++ b/mx/commands.py	Mon Mar 19 15:51:49 2012 -0700
@@ -414,6 +414,12 @@
         buildSuffix = 'graal'
         
     for build in builds:
+        if build == 'ide-build-target':
+            build = os.environ.get('IDE_BUILD_TARGET', 'product')
+            if len(build) == 0:
+                mx.log('[skipping build from IDE as IDE_BUILD_TARGET environment variable is ""]')
+                continue
+
         jdk = _jdk(build, create=True)
             
         vmDir = join(_vmLibDirInJdk(jdk), vm)
@@ -751,9 +757,19 @@
 def gv(args):
     """run the Graal Visualizer"""
     with open(join(_graal_home, '.graal_visualizer.log'), 'w') as fp:
-        mx.log('[Graal Visualizer output is in ' + fp.name + ']')
+        mx.log('[Graal Visualizer log is in ' + fp.name + ']')
+        if not exists(join(_graal_home, 'visualizer', 'build.xml')):
+            mx.log('[This initial execution may take a while as the NetBeans platform needs to be downloaded]')
         mx.run(['ant', '-f', join(_graal_home, 'visualizer', 'build.xml'), '-l', fp.name, 'run'])
     
+def igv(args):
+    """run the Ideal Graph Visualizer"""
+    with open(join(_graal_home, '.ideal_graph_visualizer.log'), 'w') as fp:
+        mx.log('[Ideal Graph Visualizer log is in ' + fp.name + ']')
+        if not exists(join(_graal_home, 'src', 'share', 'tools', 'IdealGraphVisualizer', 'nbplatform')):
+            mx.log('[This initial execution may take a while as the NetBeans platform needs to be downloaded]')
+        mx.run(['ant', '-f', join(_graal_home, 'src', 'share', 'tools', 'IdealGraphVisualizer', 'build.xml'), '-l', fp.name, 'run'])
+
 def bench(args):
     """run benchmarks and parse their output for results
 
@@ -876,11 +892,12 @@
         'buildvms': [buildvms, '[-options]'],
         'clean': [clean, ''],
         'hsdis': [hsdis, '[att]'],
+        'igv' : [igv, ''],
         'intro': [intro, ''],
         'dacapo': [dacapo, '[[n] benchmark] [VM options|@DaCapo options]'],
         'scaladacapo': [scaladacapo, '[[n] benchmark] [VM options|@Scala DaCapo options]'],
         'specjvm2008': [specjvm2008, '[VM options|@specjvm2008 options]'],
-        'example': [example, '[-v] example names...'],
+        #'example': [example, '[-v] example names...'],
         'gate' : [gate, '[-options]'],
         'gv' : [gv, ''],
         'bench' : [bench, '[-resultfile file] [all(default)|dacapo|specjvm2008|bootstrap]'],
--- a/mxtool/mx.py	Mon Mar 19 15:47:35 2012 -0700
+++ b/mxtool/mx.py	Mon Mar 19 15:51:49 2012 -0700
@@ -510,6 +510,7 @@
         ArgumentParser.__init__(self, prog='mx')
 
         self.add_argument('-v', action='store_true', dest='verbose', help='enable verbose output')
+        self.add_argument('-V', action='store_true', dest='very_verbose', help='enable very verbose output')
         self.add_argument('--dbg', type=int, dest='java_dbg_port', help='make Java processes wait on <port> for a debugger', metavar='<port>')
         self.add_argument('-d', action='store_const', const=8000, dest='java_dbg_port', help='alias for "-dbg 8000"')
         self.add_argument('--cp-pfx', dest='cp_prefix', help='class path prefix', metavar='<arg>')
@@ -536,6 +537,9 @@
         opts.__dict__.setdefault('timeout', 0)
         opts.__dict__.setdefault('ptimeout', 0)
 
+        if opts.very_verbose:
+            opts.verbose = True
+
         if opts.java_home is None:
             opts.java_home = os.environ.get('JAVA_HOME')
 
@@ -640,6 +644,10 @@
         assert isinstance(arg, types.StringTypes), 'argument is not a string: ' + str(arg)
 
     if _opts.verbose:
+        if _opts.very_verbose:
+            log('Environment variables:')
+            for key in sorted(os.environ.keys()):
+                log('    ' + key + '=' + os.environ[key])
         log(' '.join(args))
 
     if timeout is None and _opts.ptimeout != 0:
@@ -697,7 +705,10 @@
 
     if retcode and nonZeroIsFatal:
         if _opts.verbose:
-            raise subprocess.CalledProcessError(retcode, ' '.join(args))
+            if _opts.very_verbose:
+                raise subprocess.CalledProcessError(retcode, ' '.join(args))
+            else:
+                log('[exit code: ' + str(retcode)+ ']')
         abort(retcode)
 
     return retcode
@@ -727,7 +738,7 @@
 class JavaCompliance:
     def __init__(self, ver):
         m = re.match('1\.(\d+).*', ver)
-        assert m is not None, 'not a recognized version string: ' + vstring
+        assert m is not None, 'not a recognized version string: ' + ver
         self.value = int(m.group(1))
 
     def __str__ (self):
@@ -957,6 +968,8 @@
 
     javaCompliance = java().javaCompliance
 
+    defaultEcjPath = join(_mainSuite.dir, 'mx', 'ecj.jar')
+    
     parser = parser if parser is not None else ArgumentParser(prog='mx build')
     parser.add_argument('-f', action='store_true', dest='force', help='force compilation even if class files are up to date')
     parser.add_argument('-c', action='store_true', dest='clean', help='removes existing build output')
@@ -965,7 +978,7 @@
     parser.add_argument('--projects', action='store', help='comma separated projects to build (omit to build all projects)')
     parser.add_argument('--no-java', action='store_false', dest='java', help='do not build Java projects')
     parser.add_argument('--no-native', action='store_false', dest='native', help='do not build native projects')
-    parser.add_argument('--jdt', help='Eclipse installation or path to ecj.jar for using the Eclipse batch compiler instead of javac', metavar='<path>')
+    parser.add_argument('--jdt', help='Eclipse installation or path to ecj.jar for using the Eclipse batch compiler (default: ' + defaultEcjPath + ')', default=defaultEcjPath, metavar='<path>')
 
     if suppliedParser:
         parser.add_argument('remainder', nargs=REMAINDER, metavar='...')
@@ -976,6 +989,9 @@
     if args.jdt is not None:
         if args.jdt.endswith('.jar'):
             jdtJar=args.jdt
+            if not exists(jdtJar) and os.path.abspath(jdtJar) == os.path.abspath(defaultEcjPath):
+                # Silently ignore JDT if default location is used but not ecj.jar exists there
+                jdtJar = None
         elif isdir(args.jdt):
             plugins = join(args.jdt, 'plugins')
             choices = [f for f in os.listdir(plugins) if fnmatch.fnmatch(f, 'org.eclipse.jdt.core_*.jar')]
@@ -1053,7 +1069,7 @@
                                         with open(os.devnull) as devnull:
                                             subprocess.call('jasmin', stdout=devnull, stderr=subprocess.STDOUT)
                                         jasminAvailable = True
-                                    except OSError as e:
+                                    except OSError:
                                         jasminAvailable = False
 
                                 if jasminAvailable:
@@ -1119,15 +1135,21 @@
                 run([java().javac, '-g', '-J-Xmx1g', '-source', args.compliance, '-classpath', cp, '-d', outputDir, '@' + argfile.name], err=errFilt)
             else:
                 log('Compiling Java sources for {0} with JDT...'.format(p.name))
+                jdtArgs = [java().java, '-Xmx1g', '-jar', jdtJar,
+                         '-' + args.compliance,
+                         '-cp', cp, '-g', '-enableJavadoc',
+                         '-warn:-unusedImport,-unchecked',
+                         '-d', outputDir]
                 jdtProperties = join(p.dir, '.settings', 'org.eclipse.jdt.core.prefs')
                 if not exists(jdtProperties):
-                    raise SystemError('JDT properties file {0} not found'.format(jdtProperties))
-                run([java().java, '-Xmx1g', '-jar', jdtJar,
-                         '-properties', jdtProperties,
-                         '-' + args.compliance,
-                         '-cp', cp, '-g',
-                         '-warn:-unusedImport,-unchecked',
-                         '-d', outputDir, '@' + argfile.name])
+                    # Try to fix a missing properties file by running eclipseinit
+                    eclipseinit([])
+                if not exists(jdtProperties):
+                    log('JDT properties file {0} not found'.format(jdtProperties))
+                else:
+                    jdtArgs += ['-properties', jdtProperties]
+                jdtArgs.append('@' + argfile.name)
+                run(jdtArgs)
         finally:
             os.remove(argfileName)
 
@@ -1358,21 +1380,12 @@
         out.write(str(obj) + '\n')
 
     for p in projects():
+        if p.native:
+            continue
+        
         if not exists(p.dir):
             os.makedirs(p.dir)
 
-        if p.native:
-            eclipseNativeSettingsDir = join(suite.dir, 'mx', 'eclipse-native-settings')
-            if exists(eclipseNativeSettingsDir):
-                for name in os.listdir(eclipseNativeSettingsDir):
-                    path = join(eclipseNativeSettingsDir, name)
-                    if isfile(path):
-                        with open(join(eclipseNativeSettingsDir, name)) as f:
-                            content = f.read()
-                        content = content.replace('${javaHome}', java().jdk)
-                        update_file(join(p.dir, name), content)
-            continue
-
         out = StringIO.StringIO()
 
         println(out, '<?xml version="1.0" encoding="UTF-8"?>')
@@ -1402,8 +1415,10 @@
                         if isabs(path):
                             println(out, '\t<classpathentry exported="true" kind="lib" path="' + path + '"/>')
                         else:
-                            projRelPath = os.path.relpath(join(suite.dir, path), p.dir)
-                            println(out, '\t<classpathentry exported="true" kind="lib" path="' + projRelPath + '"/>')
+                            # Relative paths for "lib" class path entries have various semantics depending on the Eclipse
+                            # version being used (e.g. see https://bugs.eclipse.org/bugs/show_bug.cgi?id=274737) so it's
+                            # safest to simply use absolute paths.
+                            println(out, '\t<classpathentry exported="true" kind="lib" path="' + join(suite.dir, path) + '"/>')
             else:
                 println(out, '\t<classpathentry combineaccessrules="false" exported="true" kind="src" path="/' + dep.name + '"/>')
 
--- a/src/share/tools/IdealGraphVisualizer/nbproject/platform.properties	Mon Mar 19 15:47:35 2012 -0700
+++ b/src/share/tools/IdealGraphVisualizer/nbproject/platform.properties	Mon Mar 19 15:51:49 2012 -0700
@@ -1,3 +1,11 @@
+nbplatform.active=default
+bootstrap.url=http://deadlock.netbeans.org/hudson/job/nbms-and-javadoc/lastSuccessfulBuild/artifact/nbbuild/netbeans/harness/tasks.jar
+autoupdate.catalog.url=http://updates.netbeans.org/netbeans/updates/7.1.1/uc/final/distribution/catalog.xml.gz
+suite.dir=${basedir}
+nbplatform.active.dir=${suite.dir}/nbplatform
+nbplatform.default.netbeans.dest.dir=${suite.dir}/nbplatform
+nbplatform.default.harness.dir=${nbplatform.default.netbeans.dest.dir}/harness
+harness.dir=${nbplatform.active.dir}/harness
 cluster.path=\
     ${nbplatform.active.dir}/ide:\
     ${nbplatform.active.dir}/platform
@@ -201,4 +209,4 @@
 #   org.netbeans.core.netigso,\
 #   org.netbeans.libs.felix,\
 #   org.netbeans.libs.osgi,\
-nbplatform.active=default
+
--- a/src/share/vm/runtime/arguments.cpp	Mon Mar 19 15:47:35 2012 -0700
+++ b/src/share/vm/runtime/arguments.cpp	Mon Mar 19 15:51:49 2012 -0700
@@ -2127,7 +2127,7 @@
     }
     if (PrintVMOptions) tty->print_cr("GRAAL=%s", graal_dir);
     
-    SysClassPath scp_compiler(Arguments::get_sysclasspath());
+    SysClassPath scp_compiler("");
     struct dirent* dentry;
     char* tdbuf = NEW_C_HEAP_ARRAY(char, os::readdir_buf_size(graal_dir));
     errno = 0;
--- a/src/share/vm/utilities/ostream.cpp	Mon Mar 19 15:47:35 2012 -0700
+++ b/src/share/vm/utilities/ostream.cpp	Mon Mar 19 15:51:49 2012 -0700
@@ -616,9 +616,9 @@
       // Print it as a java-style property list.
       // System properties don't generally contain newlines, so don't bother with unparsing.
       for (SystemProperty* p = Arguments::system_properties(); p != NULL; p = p->next()) {
-        xs->text()->print(p->key());
+        xs->text()->print(p->key() ? p->key() : "");
         xs->text()->print("=");
-        xs->text()->print_cr(p->value());
+        xs->text()->print_cr(p->value() ? p->value() : "");
       }
       xs->tail("properties");
     }