--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/InstanceOfSnippets.java	Tue Oct 30 10:45:00 2012 +0100
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/InstanceOfSnippets.java	Tue Oct 30 23:58:53 2012 +0100
@@ -25,9 +25,10 @@
 import static com.oracle.graal.hotspot.snippets.CheckCastSnippets.Templates.*;
 import static com.oracle.graal.hotspot.snippets.HotSpotSnippetUtils.*;
 import static com.oracle.graal.snippets.Snippet.Varargs.*;
-import static com.oracle.graal.snippets.SnippetTemplate.*;
 import static com.oracle.graal.snippets.SnippetTemplate.Arguments.*;
 
+import java.util.*;
+
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.graph.*;
@@ -185,83 +186,236 @@
             ConstantNode hub = ConstantNode.forObject(type.klassOop(), runtime, instanceOf.graph());
             boolean checkNull = !object.stamp().nonNull();
 
-            for (Node usage : instanceOf.usages().snapshot()) {
-                Arguments arguments = null;
-                Key key = null;
+            List<Node> usages = instanceOf.usages().snapshot();
+            int nUsages = usages.size();
+            Map<MaterializationKey, Materialization> materializations = nUsages == 1 ? null : new HashMap<MaterializationKey, Materialization>(nUsages);
+
+            for (Node usage : usages) {
+                final StructuredGraph graph = (StructuredGraph) usage.graph();
 
-                // instanceof nodes are lowered separately for each usage. To simply graph modifications,
-                // we duplicate the instanceof node for each usage.
-                final InstanceOfNode duplicate = instanceOf.graph().add(new InstanceOfNode(instanceOf.type(), instanceOf.object(), instanceOf.profile()));
-                usage.replaceFirstInput(instanceOf, duplicate);
+                UsageReplacer replacer;
+                MaterializationKey mkey;
+                if (usage instanceof IfNode) {
+                    mkey = new MaterializationKey(ConstantNode.forInt(1, graph), ConstantNode.forInt(0, graph));
+                    replacer = new IfUsageReplacer(materializations, mkey, instanceOf, (IfNode) usage, tool);
+                } else {
+                    assert usage instanceof ConditionalNode : "unexpected usage of " + instanceOf + ": " + usage;
+                    ConditionalNode conditional = (ConditionalNode) usage;
+                    mkey = new MaterializationKey(conditional.trueValue(), conditional.falseValue());
+                    replacer = new ConditionalUsageReplacer(materializations, mkey, instanceOf, conditional);
+                }
 
-                if (usage instanceof IfNode) {
-                    final StructuredGraph graph = (StructuredGraph) usage.graph();
-                    final ValueNode falseValue = ConstantNode.forInt(0, graph);
-                    final ValueNode trueValue = ConstantNode.forInt(1, graph);
-
+                Materialization materialization = materializations == null ? null : materializations.get(mkey);
+                if (materialization != null) {
+                    usage.replaceFirstInput(instanceOf, materialization.condition(mkey));
+                } else {
+                    Arguments arguments;
+                    Key key;
                     if (hintInfo.exact) {
                         HotSpotKlassOop[] hints = createHints(hintInfo);
                         assert hints.length == 1;
                         key = new Key(instanceofExact).add("checkNull", checkNull);
-                        arguments = arguments("object", object).add("exactHub", hints[0]).add("trueValue", trueValue).add("falseValue", falseValue);
+                        arguments = arguments("object", object).add("exactHub", hints[0]).add("trueValue", mkey.trueValue).add("falseValue", mkey.falseValue);
                     } else if (type.isPrimaryType()) {
                         key = new Key(instanceofPrimary).add("checkNull", checkNull).add("superCheckOffset", type.superCheckOffset());
-                        arguments = arguments("hub", hub).add("object", object).add("trueValue", trueValue).add("falseValue", falseValue);
+                        arguments = arguments("hub", hub).add("object", object).add("trueValue", mkey.trueValue).add("falseValue", mkey.falseValue);
                     } else {
                         HotSpotKlassOop[] hints = createHints(hintInfo);
                         key = new Key(instanceofSecondary).add("hints", vargargs(Object.class, hints.length)).add("checkNull", checkNull);
-                        arguments = arguments("hub", hub).add("object", object).add("hints", hints).add("trueValue", trueValue).add("falseValue", falseValue);
-                    }
-
-                    UsageReplacer replacer = new UsageReplacer() {
-                        @Override
-                        public void replace(ValueNode oldNode, ValueNode newNode) {
-                            assert oldNode == duplicate;
-                            newNode.inferStamp();
-                            IntegerEqualsNode condition = graph.add(new IntegerEqualsNode(newNode, trueValue));
-                            oldNode.replaceAtUsages(condition);
-                        }
-                    };
-
-                    SnippetTemplate template = cache.get(key);
-                    template.instantiate(runtime, duplicate, replacer, tool.lastFixedNode(), arguments);
-
-                } else if (usage instanceof ConditionalNode) {
-
-                    ConditionalNode materialize = (ConditionalNode) usage;
-                    materialize.replaceAtUsages(duplicate);
-                    ValueNode falseValue = materialize.falseValue();
-                    ValueNode trueValue = materialize.trueValue();
-
-                    // The materialize node is no longer connected to anyone -> kill it
-                    materialize.clearInputs();
-                    assert materialize.usages().isEmpty();
-                    GraphUtil.killWithUnusedFloatingInputs(materialize);
-
-                    if (hintInfo.exact) {
-                        HotSpotKlassOop[] hints = createHints(hintInfo);
-                        assert hints.length == 1;
-                        key = new Key(instanceofExact).add("checkNull", checkNull);
-                        arguments = arguments("object", object).add("exactHub", hints[0]).add("trueValue", trueValue).add("falseValue", falseValue);
-                    } else if (type.isPrimaryType()) {
-                        key = new Key(instanceofPrimary).add("checkNull", checkNull).add("superCheckOffset", type.superCheckOffset());
-                        arguments = arguments("hub", hub).add("object", object).add("trueValue", trueValue).add("falseValue", falseValue);
-                    } else {
-                        HotSpotKlassOop[] hints = createHints(hintInfo);
-                        key = new Key(instanceofSecondary).add("hints", vargargs(Object.class, hints.length)).add("checkNull", checkNull);
-                        arguments = arguments("hub", hub).add("object", object).add("hints", hints).add("trueValue", trueValue).add("falseValue", falseValue);
+                        arguments = arguments("hub", hub).add("object", object).add("hints", hints).add("trueValue", mkey.trueValue).add("falseValue", mkey.falseValue);
                     }
 
                     SnippetTemplate template = cache.get(key);
-                    template.instantiate(runtime, duplicate, DEFAULT_REPLACER, tool.lastFixedNode(), arguments);
-                } else {
-                    throw new GraalInternalError("Unexpected usage of %s: %s", instanceOf, usage);
+                    template.instantiate(runtime, instanceOf, replacer, tool.lastFixedNode(), arguments);
                 }
             }
 
-            assert !instanceOf.isDeleted();
             assert instanceOf.usages().isEmpty();
-            GraphUtil.killWithUnusedFloatingInputs(instanceOf);
+            if (!instanceOf.isDeleted()) {
+                GraphUtil.killWithUnusedFloatingInputs(instanceOf);
+            }
+        }
+
+        /**
+         * The materialized result of an instanceof snippet.
+         * All usages of an {@link InstanceOfNode} that have the same key can share the result.
+         */
+        static final class Materialization {
+            private final PhiNode phi;
+            private CompareNode condition;
+
+
+            public Materialization(PhiNode phi) {
+                this.phi = phi;
+            }
+
+            CompareNode condition(MaterializationKey key) {
+                if (condition == null) {
+                    StructuredGraph graph = (StructuredGraph) phi.graph();
+                    condition = graph.add(new IntegerEqualsNode(phi, key.trueValue));
+                }
+                return condition;
+            }
+        }
+
+        static final class MaterializationKey {
+            final ValueNode trueValue;
+            final ValueNode falseValue;
+            public MaterializationKey(ValueNode trueValue, ValueNode falseValue) {
+                this.trueValue = trueValue;
+                this.falseValue = falseValue;
+            }
+
+            @Override
+            public int hashCode() {
+                return trueValue.hashCode();
+            }
+
+            @Override
+            public boolean equals(Object obj) {
+                if (obj instanceof MaterializationKey) {
+                    MaterializationKey mk = (MaterializationKey) obj;
+                    return mk.trueValue == trueValue && mk.falseValue == falseValue;
+                }
+                return false;
+            }
+
+            @Override
+            public String toString() {
+                return "[true=" + trueValue + ", false=" + falseValue + "]";
+            }
+        }
+
+        /**
+         * Replaces an {@link IfNode} usage of an {@link InstanceOfNode}.
+         */
+        static final class IfUsageReplacer implements UsageReplacer {
+
+            private final boolean solitaryUsage;
+            private final InstanceOfNode instanceOf;
+            private final IfNode usage;
+            private final Map<MaterializationKey, Materialization> materializations;
+            private final MaterializationKey key;
+            private final boolean sameBlock;
+
+            private IfUsageReplacer(Map<MaterializationKey, Materialization> materializations, MaterializationKey key, InstanceOfNode instanceOf, IfNode usage, LoweringTool tool) {
+                this.materializations = materializations;
+                this.key = key;
+                this.sameBlock = tool.getBlockFor(usage) == tool.getBlockFor(instanceOf);
+                this.solitaryUsage = materializations == null;
+                this.instanceOf = instanceOf;
+                this.usage = usage;
+            }
+
+            @Override
+            public void replace(ValueNode oldNode, ValueNode newNode) {
+                assert newNode instanceof PhiNode;
+                assert oldNode == instanceOf;
+                if (sameBlock && solitaryUsage) {
+                    removeIntermediateMaterialization(newNode);
+                } else {
+                    newNode.inferStamp();
+                    Materialization m = new Materialization((PhiNode) newNode);
+                    if (materializations != null) {
+                        Materialization oldValue = materializations.put(key, m);
+                        assert oldValue == null;
+                    }
+                    usage.replaceFirstInput(oldNode, m.condition(key));
+                }
+            }
+
+            /**
+             * Directly wires the incoming edges of the merge at the end of the snippet to
+             * the outgoing edges of the IfNode that uses the materialized result.
+             */
+            private void removeIntermediateMaterialization(ValueNode newNode) {
+                IfNode ifNode = usage;
+                PhiNode phi = (PhiNode) newNode;
+                MergeNode merge = phi.merge();
+                assert merge.stateAfter() == null;
+
+                List<EndNode> mergePredecessors = merge.cfgPredecessors().snapshot();
+                assert phi.valueCount() == mergePredecessors.size();
+
+                List<EndNode> falseEnds = new ArrayList<>(mergePredecessors.size());
+                List<EndNode> trueEnds = new ArrayList<>(mergePredecessors.size());
+
+                int endIndex = 0;
+                for (EndNode end : mergePredecessors) {
+                    ValueNode endValue = phi.valueAt(endIndex++);
+                    if (endValue == key.trueValue) {
+                        trueEnds.add(end);
+                    } else {
+                        assert endValue == key.falseValue;
+                        falseEnds.add(end);
+                    }
+                }
+
+                BeginNode trueSuccessor = ifNode.trueSuccessor();
+                BeginNode falseSuccessor = ifNode.falseSuccessor();
+                ifNode.setTrueSuccessor(null);
+                ifNode.setFalseSuccessor(null);
+
+                connectEnds(merge, trueEnds, trueSuccessor);
+                connectEnds(merge, falseEnds, falseSuccessor);
+
+                GraphUtil.killCFG(merge);
+                GraphUtil.killCFG(ifNode);
+
+                assert !merge.isAlive() : merge;
+                assert !phi.isAlive() : phi;
+            }
+
+            private static void connectEnds(MergeNode merge, List<EndNode> ends, BeginNode successor) {
+                if (ends.size() == 1) {
+                    EndNode end = ends.get(0);
+                    ((FixedWithNextNode) end.predecessor()).setNext(successor);
+                    merge.removeEnd(end);
+                    GraphUtil.killCFG(end);
+                } else {
+                    assert ends.size() > 1;
+                    MergeNode newMerge = merge.graph().add(new MergeNode());
+
+                    for (EndNode end : ends) {
+                        newMerge.addForwardEnd(end);
+                    }
+                    newMerge.setNext(successor);
+                }
+            }
+        }
+
+        /**
+         * Replaces a {@link ConditionalNode} usage of an {@link InstanceOfNode}.
+         */
+        static final class ConditionalUsageReplacer implements UsageReplacer {
+
+            private final InstanceOfNode instanceOf;
+            private final ConditionalNode usage;
+            private final Map<MaterializationKey, Materialization> materializations;
+            private final MaterializationKey key;
+
+            private ConditionalUsageReplacer(Map<MaterializationKey, Materialization> materializations, MaterializationKey key, InstanceOfNode instanceOf, ConditionalNode usage) {
+                this.materializations = materializations;
+                this.key = key;
+                this.instanceOf = instanceOf;
+                this.usage = usage;
+            }
+
+            @Override
+            public void replace(ValueNode oldNode, ValueNode newNode) {
+                assert newNode instanceof PhiNode;
+                assert oldNode == instanceOf;
+                newNode.inferStamp();
+                if (materializations != null) {
+                    Materialization m = new Materialization((PhiNode) newNode);
+                    Materialization oldValue = materializations.put(key, m);
+                    assert oldValue == null;
+                }
+                usage.replaceAtUsages(newNode);
+                usage.clearInputs();
+                assert usage.usages().isEmpty();
+                GraphUtil.killWithUnusedFloatingInputs(usage);
+            }
         }
     }
 

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/LoweringTool.java	Tue Oct 30 10:45:00 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/LoweringTool.java	Tue Oct 30 23:58:53 2012 +0100
@@ -24,7 +24,9 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.cfg.*;
 
 public interface LoweringTool {
     GraalCodeCacheProvider getRuntime();
@@ -33,6 +35,8 @@
     ValueNode createGuard(BooleanNode condition, DeoptimizationReason deoptReason, DeoptimizationAction action, boolean negated, long leafGraphId);
     Assumptions assumptions();
 
+    Block getBlockFor(Node node);
+
     /**
      * Gets the closest fixed node preceding the node currently being lowered.
      */

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Tue Oct 30 10:45:00 2012 +0100
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Tue Oct 30 23:58:53 2012 +0100
@@ -46,10 +46,12 @@
         final FixedNode guardAnchor;
         final NodeBitMap activeGuards;
         FixedWithNextNode lastFixedNode;
+        ControlFlowGraph cfg;
 
-        public LoweringToolImpl(FixedNode guardAnchor, NodeBitMap activeGuards) {
+        public LoweringToolImpl(FixedNode guardAnchor, NodeBitMap activeGuards, ControlFlowGraph cfg) {
             this.guardAnchor = guardAnchor;
             this.activeGuards = activeGuards;
+            this.cfg = cfg;
         }
 
         @Override
@@ -89,6 +91,11 @@
             return newGuard;
         }
 
+        @Override
+        public Block getBlockFor(Node node) {
+            return cfg.blockFor(node);
+        }
+
         public FixedWithNextNode lastFixedNode() {
             return lastFixedNode;
         }
@@ -164,7 +171,7 @@
 
     private void process(final Block b, final NodeBitMap activeGuards, final FixedNode anchor, SchedulePhase schedule, NodeBitMap processed) {
 
-        final LoweringToolImpl loweringTool = new LoweringToolImpl(anchor, activeGuards);
+        final LoweringToolImpl loweringTool = new LoweringToolImpl(anchor, activeGuards, schedule.getCFG());
 
         // Lower the instructions of this block.
         List<ScheduledNode> nodes = schedule.nodesFor(b);

--- a/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java	Tue Oct 30 10:45:00 2012 +0100
+++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java	Tue Oct 30 23:58:53 2012 +0100
@@ -556,8 +556,10 @@
             replacer.replace(replacee, returnValue);
 
             Node returnDuplicate = duplicates.get(returnNode);
-            returnDuplicate.clearInputs();
-            returnDuplicate.replaceAndDelete(next);
+            if (returnDuplicate.isAlive()) {
+                returnDuplicate.clearInputs();
+                returnDuplicate.replaceAndDelete(next);
+            }
         }
 
         // Remove the replacee from its graph
@@ -621,8 +623,10 @@
         replacer.replace(replacee, returnValue);
 
         Node returnDuplicate = duplicates.get(returnNode);
-        returnDuplicate.clearInputs();
-        returnDuplicate.replaceAndDelete(next);
+        if (returnDuplicate.isAlive()) {
+            returnDuplicate.clearInputs();
+            returnDuplicate.replaceAndDelete(next);
+        }
 
         Debug.dump(replaceeGraph, "After lowering %s with %s", replacee, this);
     }