--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/replacements/InstanceOfSnippetsTemplates.java	Wed Mar 20 22:23:14 2013 +0100
@@ -0,0 +1,338 @@
+/*
+ * Copyright (c) 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.replacements;
+
+import static com.oracle.graal.nodes.calc.CompareNode.*;
+
+import java.util.*;
+
+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.calc.*;
+import com.oracle.graal.nodes.java.*;
+import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.util.*;
+import com.oracle.graal.replacements.SnippetTemplate.*;
+
+/**
+ * Helper class for lowering {@link InstanceOfNode}s with snippets. The majority of the complexity
+ * in such a lowering derives from the fact that {@link InstanceOfNode} is a floating node. A
+ * snippet used to lower an {@link InstanceOfNode} will almost always incorporate control flow and
+ * replacing a floating node with control flow is not trivial.
+ * <p>
+ * The mechanism implemented in this class ensures that the graph for an instanceof snippet is
+ * instantiated once per {@link InstanceOfNode} being lowered. The result produced is then re-used
+ * by all usages of the node. Additionally, if there is a single usage that is an {@link IfNode},
+ * the control flow in the snippet is connected directly to the true and false successors of the
+ * {@link IfNode}. This avoids materializing the instanceof test as a boolean which is then retested
+ * by the {@link IfNode}.
+ */
+public abstract class InstanceOfSnippetsTemplates<T extends Snippets> extends AbstractTemplates<T> {
+
+    public InstanceOfSnippetsTemplates(MetaAccessProvider runtime, Assumptions assumptions, TargetDescription target, Class<T> snippetsClass) {
+        super(runtime, assumptions, target, snippetsClass);
+    }
+
+    /**
+     * The key and arguments used to retrieve and instantiate an instanceof snippet template.
+     */
+    public static class KeyAndArguments {
+
+        public final Key key;
+        public final Arguments arguments;
+
+        public KeyAndArguments(Key key, Arguments arguments) {
+            this.key = key;
+            this.arguments = arguments;
+        }
+
+    }
+
+    /**
+     * Gets the key and arguments used to retrieve and instantiate an instanceof snippet template.
+     */
+    protected abstract KeyAndArguments getKeyAndArguments(InstanceOfUsageReplacer replacer, LoweringTool tool);
+
+    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);
+
+            if (instantiation.isInitialized()) {
+                // No need to re-instantiate the snippet - just re-use its result
+                replacer.replaceUsingInstantiation();
+            } else {
+                KeyAndArguments keyAndArguments = getKeyAndArguments(replacer, tool);
+                SnippetTemplate template = cache.get(keyAndArguments.key, assumptions);
+                template.instantiate(runtime, instanceOf, replacer, tool, keyAndArguments.arguments);
+            }
+        }
+
+        assert instanceOf.usages().isEmpty();
+        if (!instanceOf.isDeleted()) {
+            GraphUtil.killWithUnusedFloatingInputs(instanceOf);
+        }
+    }
+
+    /**
+     * Gets the specific replacer object used to replace the usage of an instanceof node with the
+     * result of an instantiated instanceof snippet.
+     */
+    protected InstanceOfUsageReplacer createReplacer(FloatingNode instanceOf, LoweringTool tool, int nUsages, Instantiation instantiation, Node usage, final StructuredGraph graph) {
+        InstanceOfUsageReplacer replacer;
+        if (usage instanceof IfNode) {
+            replacer = new IfUsageReplacer(instantiation, ConstantNode.forInt(1, graph), ConstantNode.forInt(0, graph), instanceOf, (IfNode) usage, nUsages == 1, tool);
+        } else {
+            assert usage instanceof ConditionalNode : "unexpected usage of " + instanceOf + ": " + usage;
+            ConditionalNode c = (ConditionalNode) usage;
+            replacer = new ConditionalUsageReplacer(instantiation, c.trueValue(), c.falseValue(), instanceOf, c);
+        }
+        return replacer;
+    }
+
+    /**
+     * The result of an instantiating an instanceof snippet. This enables a snippet instantiation to
+     * be re-used which reduces compile time and produces better code.
+     */
+    public static final class Instantiation {
+
+        private PhiNode result;
+        private CompareNode condition;
+        private ValueNode trueValue;
+        private ValueNode falseValue;
+
+        /**
+         * Determines if the instantiation has occurred.
+         */
+        boolean isInitialized() {
+            return result != null;
+        }
+
+        void initialize(PhiNode phi, ValueNode t, ValueNode f) {
+            assert !isInitialized();
+            this.result = phi;
+            this.trueValue = t;
+            this.falseValue = f;
+        }
+
+        /**
+         * Gets the result of this instantiation as a condition.
+         * 
+         * @param testValue the returned condition is true if the result is equal to this value
+         */
+        CompareNode asCondition(ValueNode testValue) {
+            assert isInitialized();
+            if (condition == null || condition.y() != testValue) {
+                // Re-use previously generated condition if the trueValue for the test is the same
+                condition = createCompareNode(Condition.EQ, result, testValue);
+            }
+            return condition;
+        }
+
+        /**
+         * Gets the result of the instantiation as a materialized value.
+         * 
+         * @param t the true value for the materialization
+         * @param f the false value for the materialization
+         */
+        ValueNode asMaterialization(ValueNode t, ValueNode f) {
+            assert isInitialized();
+            if (t == this.trueValue && f == this.falseValue) {
+                // Can simply use the phi result if the same materialized values are expected.
+                return result;
+            } else {
+                return t.graph().unique(new ConditionalNode(asCondition(trueValue), t, f));
+            }
+        }
+    }
+
+    /**
+     * Replaces a usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode}.
+     */
+    public abstract static class InstanceOfUsageReplacer implements UsageReplacer {
+
+        public final Instantiation instantiation;
+        public final FloatingNode instanceOf;
+        public final ValueNode trueValue;
+        public final ValueNode falseValue;
+
+        public InstanceOfUsageReplacer(Instantiation instantiation, FloatingNode instanceOf, ValueNode trueValue, ValueNode falseValue) {
+            assert instanceOf instanceof InstanceOfNode || instanceOf instanceof InstanceOfDynamicNode;
+            this.instantiation = instantiation;
+            this.instanceOf = instanceOf;
+            this.trueValue = trueValue;
+            this.falseValue = falseValue;
+        }
+
+        /**
+         * Does the replacement based on a previously snippet instantiation.
+         */
+        public abstract void replaceUsingInstantiation();
+    }
+
+    /**
+     * Replaces an {@link IfNode} usage of an {@link InstanceOfNode} or
+     * {@link InstanceOfDynamicNode}.
+     */
+    public static class IfUsageReplacer extends InstanceOfUsageReplacer {
+
+        private final boolean solitaryUsage;
+        private final IfNode usage;
+        private final boolean sameBlock;
+
+        public IfUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, IfNode usage, boolean solitaryUsage, LoweringTool tool) {
+            super(instantiation, instanceOf, trueValue, falseValue);
+            this.sameBlock = tool.getBlockFor(usage) == tool.getBlockFor(instanceOf);
+            this.solitaryUsage = solitaryUsage;
+            this.usage = usage;
+        }
+
+        @Override
+        public void replaceUsingInstantiation() {
+            usage.replaceFirstInput(instanceOf, instantiation.asCondition(trueValue));
+        }
+
+        private boolean usageFollowsInstantiation() {
+            return instantiation.result != null && instantiation.result.merge().next() == usage;
+        }
+
+        @Override
+        public void replace(ValueNode oldNode, ValueNode newNode) {
+            assert newNode instanceof PhiNode;
+            assert oldNode == instanceOf;
+            if (sameBlock && solitaryUsage && usageFollowsInstantiation()) {
+                removeIntermediateMaterialization(newNode);
+            } else {
+                newNode.inferStamp();
+                instantiation.initialize((PhiNode) newNode, trueValue, falseValue);
+                usage.replaceFirstInput(oldNode, instantiation.asCondition(trueValue));
+            }
+        }
+
+        /**
+         * 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 == trueValue) {
+                    trueEnds.add(end);
+                } else {
+                    assert endValue == 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() == 0) {
+                // InstanceOf has been lowered to always true or always false - this successor is
+                // therefore unreachable.
+                GraphUtil.killCFG(successor);
+            } else 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} or
+     * {@link InstanceOfDynamicNode}.
+     */
+    public static class ConditionalUsageReplacer extends InstanceOfUsageReplacer {
+
+        public final ConditionalNode usage;
+
+        public ConditionalUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, ConditionalNode usage) {
+            super(instantiation, instanceOf, trueValue, falseValue);
+            this.usage = usage;
+        }
+
+        @Override
+        public void replaceUsingInstantiation() {
+            ValueNode newValue = instantiation.asMaterialization(trueValue, falseValue);
+            usage.replaceAtUsages(newValue);
+            usage.clearInputs();
+            assert usage.usages().isEmpty();
+            GraphUtil.killWithUnusedFloatingInputs(usage);
+        }
+
+        @Override
+        public void replace(ValueNode oldNode, ValueNode newNode) {
+            assert newNode instanceof PhiNode;
+            assert oldNode == instanceOf;
+            newNode.inferStamp();
+            instantiation.initialize((PhiNode) newNode, trueValue, falseValue);
+            usage.replaceAtUsages(newNode);
+            usage.clearInputs();
+            assert usage.usages().isEmpty();
+            GraphUtil.killWithUnusedFloatingInputs(usage);
+        }
+    }
+}