--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/PushNodesThroughPiTest.java	Wed Jul 10 17:46:03 2013 +0200
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/PushNodesThroughPiTest.java	Wed Jul 10 17:46:27 2013 +0200
@@ -75,7 +75,7 @@
                             if (field.getName().equals("x")) {
                                 Assert.assertTrue(rn.object() instanceof LocalNode);
                             } else {
-                                Assert.assertTrue(rn.object() instanceof UnsafeCastNode);
+                                Assert.assertTrue(rn.object().toString(), rn.object() instanceof PiNode);
                             }
                             counter++;
                         }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java	Wed Jul 10 17:46:03 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java	Wed Jul 10 17:46:27 2013 +0200
@@ -22,9 +22,13 @@
  */
 package com.oracle.graal.nodes.java;
 
+import static com.oracle.graal.api.code.DeoptimizationAction.*;
+import static com.oracle.graal.api.meta.DeoptimizationReason.*;
+
 import com.oracle.graal.api.meta.*;
 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.type.*;
 
@@ -62,9 +66,48 @@
         return forStoreCheck;
     }
 
+    /**
+     * Lowers a {@link CheckCastNode} to a {@link GuardingPiNode}. That is:
+     * 
+     * <pre>
+     * 1: A a = ...
+     * 2: B b = (B) a;
+     * </pre>
+     * 
+     * is lowered to:
+     * 
+     * <pre>
+     * 1: A a = ...
+     * 2: B b = guardingPi(a == null || a instanceof B, a, stamp(B))
+     * </pre>
+     * 
+     * or if a is known to be non-null:
+     * 
+     * <pre>
+     * 1: A a = ...
+     * 2: B b = guardingPi(a instanceof B, a, stamp(B, non-null))
+     * </pre>
+     * 
+     * Note: we use {@link Graph#add} as opposed to {@link Graph#unique} for the new
+     * {@link InstanceOfNode} to maintain the invariant checked by
+     * {@code LoweringPhase.checkUsagesAreScheduled()}.
+     */
     @Override
     public void lower(LoweringTool tool, LoweringType loweringType) {
-        tool.getRuntime().lower(this, tool);
+        InstanceOfNode typeTest = graph().add(new InstanceOfNode(type, object, profile));
+        Stamp stamp = object.stamp().join(StampFactory.declared(type));
+        ValueNode condition;
+        if (stamp == null) {
+            // This is a check cast that will always fail
+            condition = LogicConstantNode.contradiction(graph());
+            stamp = StampFactory.declared(type);
+        } else if (object.stamp().nonNull()) {
+            condition = typeTest;
+        } else {
+            condition = graph().unique(new LogicDisjunctionNode(graph().unique(new IsNullNode(object)), typeTest));
+        }
+        GuardingPiNode checkedObject = graph().add(new GuardingPiNode(object, condition, false, forStoreCheck ? ArrayStoreException : ClassCastException, InvalidateReprofile, stamp));
+        graph().replaceFixedWithFixed(this, checkedObject);
     }
 
     @Override

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java	Wed Jul 10 17:46:03 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java	Wed Jul 10 17:46:27 2013 +0200
@@ -116,7 +116,8 @@
     @Override
     public boolean verify() {
         for (Node usage : usages()) {
-            assertTrue(usage instanceof IfNode || usage instanceof FixedGuardNode || usage instanceof ConditionalNode, "unsupported usage: ", usage);
+            assertTrue(usage instanceof IfNode || usage instanceof FixedGuardNode || usage instanceof GuardingPiNode || usage instanceof ConditionalNode || usage instanceof LogicBinaryNode,
+                            "unsupported usage: %s", usage);
         }
         return super.verify();
     }

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Wed Jul 10 17:46:03 2013 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Wed Jul 10 17:46:27 2013 +0200
@@ -253,11 +253,34 @@
                 }
 
                 if (node instanceof Lowerable) {
+                    assert checkUsagesAreScheduled(node);
                     ((Lowerable) node).lower(loweringTool, loweringType);
                 }
 
                 loweringTool.setLastFixedNode((FixedWithNextNode) nextNode.predecessor());
             }
         }
+
+        /**
+         * Checks that all usages of a floating, lowerable node are scheduled.
+         * <p>
+         * Given that the lowering of such nodes may introduce fixed nodes, they must be lowered in
+         * the context of a usage that dominates all other usages. The fixed nodes resulting from
+         * lowering are attached to the fixed node context of the dominating usage. This ensures the
+         * post-lowering graph still has a valid schedule.
+         * 
+         * @param node a {@link Lowerable} node
+         */
+        private boolean checkUsagesAreScheduled(Node node) {
+            if (node instanceof FloatingNode) {
+                for (Node usage : node.usages()) {
+                    if (usage instanceof ScheduledNode) {
+                        Block usageBlock = schedule.getCFG().blockFor(usage);
+                        assert usageBlock != null : node.graph() + ": cannot lower floatable node " + node + " that has non-scheduled usage " + usage;
+                    }
+                }
+            }
+            return true;
+        }
     }
 }

--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/InstanceOfSnippetsTemplates.java	Wed Jul 10 17:46:03 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/InstanceOfSnippetsTemplates.java	Wed Jul 10 17:46:27 2013 +0200
@@ -65,13 +65,12 @@
     public void lower(FloatingNode instanceOf, LoweringTool tool) {
         assert instanceOf instanceof InstanceOfNode || instanceOf instanceof InstanceOfDynamicNode;
         List<Node> usages = instanceOf.usages().snapshot();
-        int nUsages = usages.size();
 
         Instantiation instantiation = new Instantiation();
         for (Node usage : usages) {
             final StructuredGraph graph = (StructuredGraph) usage.graph();
 
-            InstanceOfUsageReplacer replacer = createReplacer(instanceOf, tool, nUsages, instantiation, usage, graph);
+            InstanceOfUsageReplacer replacer = createReplacer(instanceOf, instantiation, usage, graph);
 
             if (instantiation.isInitialized()) {
                 // No need to re-instantiate the snippet - just re-use its result
@@ -91,18 +90,15 @@
     /**
      * Gets the specific replacer object used to replace the usage of an instanceof node with the
      * result of an instantiated instanceof snippet.
-     * 
-     * @param nUsages
-     * @param tool
      */
-    protected InstanceOfUsageReplacer createReplacer(FloatingNode instanceOf, LoweringTool tool, int nUsages, Instantiation instantiation, Node usage, final StructuredGraph graph) {
+    protected InstanceOfUsageReplacer createReplacer(FloatingNode instanceOf, Instantiation instantiation, Node usage, final StructuredGraph graph) {
         InstanceOfUsageReplacer replacer;
-        if (usage instanceof IfNode || usage instanceof FixedGuardNode) {
-            replacer = new IfUsageReplacer(instantiation, ConstantNode.forInt(1, graph), ConstantNode.forInt(0, graph), instanceOf, (FixedNode) usage);
+        if (usage instanceof IfNode || usage instanceof FixedGuardNode || usage instanceof LogicBinaryNode || usage instanceof GuardingPiNode) {
+            replacer = new NonMaterializationUsageReplacer(instantiation, ConstantNode.forInt(1, graph), ConstantNode.forInt(0, graph), instanceOf, usage);
         } else {
             assert usage instanceof ConditionalNode : "unexpected usage of " + instanceOf + ": " + usage;
             ConditionalNode c = (ConditionalNode) usage;
-            replacer = new ConditionalUsageReplacer(instantiation, c.trueValue(), c.falseValue(), instanceOf, c);
+            replacer = new MaterializationUsageReplacer(instantiation, c.trueValue(), c.falseValue(), instanceOf, c);
         }
         return replacer;
     }
@@ -192,14 +188,14 @@
     }
 
     /**
-     * Replaces an {@link IfNode} usage of an {@link InstanceOfNode} or
-     * {@link InstanceOfDynamicNode}.
+     * Replaces the usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode} that does
+     * not materialize the result of the type test.
      */
-    public static class IfUsageReplacer extends InstanceOfUsageReplacer {
+    public static class NonMaterializationUsageReplacer extends InstanceOfUsageReplacer {
 
-        private final FixedNode usage;
+        private final Node usage;
 
-        public IfUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, FixedNode usage) {
+        public NonMaterializationUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, Node usage) {
             super(instantiation, instanceOf, trueValue, falseValue);
             this.usage = usage;
         }
@@ -211,14 +207,6 @@
 
         @Override
         public void replace(ValueNode oldNode, ValueNode newNode) {
-            if (newNode.isConstant()) {
-                LogicConstantNode logicConstant = LogicConstantNode.forBoolean(newNode.asConstant().asInt() != 0, newNode.graph());
-                usage.replaceFirstInput(oldNode, logicConstant);
-                // PrintStream out = System.out;
-                // out.println(newNode.graph() + ": " + this);
-                GraalInternalError.shouldNotReachHere(instanceOf.graph().toString());
-                return;
-            }
             assert newNode instanceof PhiNode;
             assert oldNode == instanceOf;
             newNode.inferStamp();
@@ -228,14 +216,14 @@
     }
 
     /**
-     * Replaces a {@link ConditionalNode} usage of an {@link InstanceOfNode} or
-     * {@link InstanceOfDynamicNode}.
+     * Replaces the usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode} that does
+     * materializes the result of the type test.
      */
-    public static class ConditionalUsageReplacer extends InstanceOfUsageReplacer {
+    public static class MaterializationUsageReplacer extends InstanceOfUsageReplacer {
 
         public final ConditionalNode usage;
 
-        public ConditionalUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, ConditionalNode usage) {
+        public MaterializationUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, ConditionalNode usage) {
             super(instantiation, instanceOf, trueValue, falseValue);
             this.usage = usage;
         }
@@ -251,14 +239,6 @@
 
         @Override
         public void replace(ValueNode oldNode, ValueNode newNode) {
-            if (newNode.isConstant()) {
-                LogicConstantNode logicConstant = LogicConstantNode.forBoolean(newNode.asConstant().asInt() != 0, newNode.graph());
-                usage.replaceFirstInput(oldNode, logicConstant);
-                // PrintStream out = System.out;
-                // out.println(newNode.graph() + ": " + this);
-                GraalInternalError.shouldNotReachHere(instanceOf.graph().toString());
-                return;
-            }
             assert newNode instanceof PhiNode;
             assert oldNode == instanceOf;
             newNode.inferStamp();