InstanceOfSnippetsTemplates.java revision 13264:48566d838608 
1/*
2 * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23package org.graalvm.compiler.replacements;
24
25import static org.graalvm.compiler.nodes.calc.CompareNode.createCompareNode;
26
27import java.util.List;
28
29import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;
30import org.graalvm.compiler.core.common.calc.Condition;
31import org.graalvm.compiler.debug.DebugHandlersFactory;
32import org.graalvm.compiler.graph.Node;
33import org.graalvm.compiler.nodes.ConditionAnchorNode;
34import org.graalvm.compiler.nodes.ConstantNode;
35import org.graalvm.compiler.nodes.FixedGuardNode;
36import org.graalvm.compiler.nodes.IfNode;
37import org.graalvm.compiler.nodes.LogicConstantNode;
38import org.graalvm.compiler.nodes.LogicNode;
39import org.graalvm.compiler.nodes.PhiNode;
40import org.graalvm.compiler.nodes.ShortCircuitOrNode;
41import org.graalvm.compiler.nodes.StructuredGraph;
42import org.graalvm.compiler.nodes.ValueNode;
43import org.graalvm.compiler.nodes.calc.CompareNode;
44import org.graalvm.compiler.nodes.calc.ConditionalNode;
45import org.graalvm.compiler.nodes.calc.FloatingNode;
46import org.graalvm.compiler.nodes.java.ClassIsAssignableFromNode;
47import org.graalvm.compiler.nodes.java.InstanceOfDynamicNode;
48import org.graalvm.compiler.nodes.java.InstanceOfNode;
49import org.graalvm.compiler.nodes.spi.LoweringTool;
50import org.graalvm.compiler.nodes.util.GraphUtil;
51import org.graalvm.compiler.options.OptionValues;
52import org.graalvm.compiler.phases.util.Providers;
53import org.graalvm.compiler.replacements.SnippetTemplate.AbstractTemplates;
54import org.graalvm.compiler.replacements.SnippetTemplate.Arguments;
55import org.graalvm.compiler.replacements.SnippetTemplate.UsageReplacer;
56
57import jdk.vm.ci.code.TargetDescription;
58
59/**
60 * Helper class for lowering {@link InstanceOfNode}s with snippets. The majority of the complexity
61 * in such a lowering derives from the fact that {@link InstanceOfNode} is a floating node. A
62 * snippet used to lower an {@link InstanceOfNode} will almost always incorporate control flow and
63 * replacing a floating node with control flow is not trivial.
64 * <p>
65 * The mechanism implemented in this class ensures that the graph for an instanceof snippet is
66 * instantiated once per {@link InstanceOfNode} being lowered. The result produced is then re-used
67 * by all usages of the node. Additionally, if there is a single usage that is an {@link IfNode},
68 * the control flow in the snippet is connected directly to the true and false successors of the
69 * {@link IfNode}. This avoids materializing the instanceof test as a boolean which is then retested
70 * by the {@link IfNode}.
71 */
72public abstract class InstanceOfSnippetsTemplates extends AbstractTemplates {
73
74    public InstanceOfSnippetsTemplates(OptionValues options, Iterable<DebugHandlersFactory> factories, Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target) {
75        super(options, factories, providers, snippetReflection, target);
76    }
77
78    /**
79     * Gets the arguments used to retrieve and instantiate an instanceof snippet template.
80     */
81    protected abstract Arguments makeArguments(InstanceOfUsageReplacer replacer, LoweringTool tool);
82
83    public void lower(FloatingNode instanceOf, LoweringTool tool) {
84        assert instanceOf instanceof InstanceOfNode || instanceOf instanceof InstanceOfDynamicNode || instanceOf instanceof ClassIsAssignableFromNode;
85        List<Node> usages = instanceOf.usages().snapshot();
86
87        Instantiation instantiation = new Instantiation();
88        for (Node usage : usages) {
89            final StructuredGraph graph = (StructuredGraph) usage.graph();
90
91            InstanceOfUsageReplacer replacer = createReplacer(instanceOf, instantiation, usage, graph);
92
93            if (instantiation.isInitialized()) {
94                // No need to re-instantiate the snippet - just re-use its result
95                replacer.replaceUsingInstantiation();
96            } else {
97                Arguments args = makeArguments(replacer, tool);
98                template(instanceOf.getDebug(), args).instantiate(providers.getMetaAccess(), instanceOf, replacer, tool, args);
99            }
100        }
101
102        assert instanceOf.hasNoUsages();
103        if (!instanceOf.isDeleted()) {
104            GraphUtil.killWithUnusedFloatingInputs(instanceOf);
105        }
106    }
107
108    /**
109     * Gets the specific replacer object used to replace the usage of an instanceof node with the
110     * result of an instantiated instanceof snippet.
111     */
112    protected InstanceOfUsageReplacer createReplacer(FloatingNode instanceOf, Instantiation instantiation, Node usage, final StructuredGraph graph) {
113        InstanceOfUsageReplacer replacer;
114        if (!canMaterialize(usage)) {
115            ValueNode trueValue = ConstantNode.forInt(1, graph);
116            ValueNode falseValue = ConstantNode.forInt(0, graph);
117            if (instantiation.isInitialized() && (trueValue != instantiation.trueValue || falseValue != instantiation.falseValue)) {
118                /*
119                 * This code doesn't really care what values are used so adopt the values from the
120                 * previous instantiation.
121                 */
122                trueValue = instantiation.trueValue;
123                falseValue = instantiation.falseValue;
124            }
125            replacer = new NonMaterializationUsageReplacer(instantiation, trueValue, falseValue, instanceOf, usage);
126        } else {
127            assert usage instanceof ConditionalNode : "unexpected usage of " + instanceOf + ": " + usage;
128            ConditionalNode c = (ConditionalNode) usage;
129            replacer = new MaterializationUsageReplacer(instantiation, c.trueValue(), c.falseValue(), instanceOf, c);
130        }
131        return replacer;
132    }
133
134    /**
135     * Determines if an {@code instanceof} usage can be materialized.
136     */
137    protected boolean canMaterialize(Node usage) {
138        if (usage instanceof ConditionalNode) {
139            ConditionalNode cn = (ConditionalNode) usage;
140            return cn.trueValue().isConstant() && cn.falseValue().isConstant();
141        }
142        if (usage instanceof IfNode || usage instanceof FixedGuardNode || usage instanceof ShortCircuitOrNode || usage instanceof ConditionAnchorNode) {
143            return false;
144        }
145        return true;
146    }
147
148    /**
149     * The result of instantiating an instanceof snippet. This enables a snippet instantiation to be
150     * re-used which reduces compile time and produces better code.
151     */
152    public static final class Instantiation {
153
154        private ValueNode result;
155        private LogicNode condition;
156        private ValueNode trueValue;
157        private ValueNode falseValue;
158
159        /**
160         * Determines if the instantiation has occurred.
161         */
162        boolean isInitialized() {
163            return result != null;
164        }
165
166        void initialize(ValueNode r, ValueNode t, ValueNode f) {
167            assert !isInitialized();
168            this.result = r;
169            this.trueValue = t;
170            this.falseValue = f;
171        }
172
173        /**
174         * Gets the result of this instantiation as a condition.
175         *
176         * @param testValue the returned condition is true if the result is equal to this value
177         */
178        LogicNode asCondition(ValueNode testValue) {
179            assert isInitialized();
180            if (result.isConstant()) {
181                assert testValue.isConstant();
182                return LogicConstantNode.forBoolean(result.asConstant().equals(testValue.asConstant()), result.graph());
183            }
184            if (condition == null || (!(condition instanceof CompareNode)) || ((CompareNode) condition).getY() != testValue) {
185                // Re-use previously generated condition if the trueValue for the test is the same
186                condition = createCompareNode(result.graph(), Condition.EQ, result, testValue, null);
187            }
188            return condition;
189        }
190
191        /**
192         * Gets the result of the instantiation as a materialized value.
193         *
194         * @param t the true value for the materialization
195         * @param f the false value for the materialization
196         */
197        ValueNode asMaterialization(StructuredGraph graph, ValueNode t, ValueNode f) {
198            assert isInitialized();
199            if (t == this.trueValue && f == this.falseValue) {
200                // Can simply use the phi result if the same materialized values are expected.
201                return result;
202            } else {
203                return graph.unique(new ConditionalNode(asCondition(trueValue), t, f));
204            }
205        }
206    }
207
208    /**
209     * Replaces a usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode}.
210     */
211    public abstract static class InstanceOfUsageReplacer implements UsageReplacer {
212
213        public final Instantiation instantiation;
214        public final FloatingNode instanceOf;
215        public final ValueNode trueValue;
216        public final ValueNode falseValue;
217
218        public InstanceOfUsageReplacer(Instantiation instantiation, FloatingNode instanceOf, ValueNode trueValue, ValueNode falseValue) {
219            assert instanceOf instanceof InstanceOfNode || instanceOf instanceof InstanceOfDynamicNode || instanceOf instanceof ClassIsAssignableFromNode;
220            this.instantiation = instantiation;
221            this.instanceOf = instanceOf;
222            this.trueValue = trueValue;
223            this.falseValue = falseValue;
224        }
225
226        /**
227         * Does the replacement based on a previously snippet instantiation.
228         */
229        public abstract void replaceUsingInstantiation();
230    }
231
232    /**
233     * Replaces the usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode} that does
234     * not materialize the result of the type test.
235     */
236    public static class NonMaterializationUsageReplacer extends InstanceOfUsageReplacer {
237
238        private final Node usage;
239
240        public NonMaterializationUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, Node usage) {
241            super(instantiation, instanceOf, trueValue, falseValue);
242            this.usage = usage;
243        }
244
245        @Override
246        public void replaceUsingInstantiation() {
247            usage.replaceFirstInput(instanceOf, instantiation.asCondition(trueValue));
248        }
249
250        @Override
251        public void replace(ValueNode oldNode, ValueNode newNode) {
252            assert newNode instanceof PhiNode;
253            assert oldNode == instanceOf;
254            newNode.inferStamp();
255            instantiation.initialize(newNode, trueValue, falseValue);
256            usage.replaceFirstInput(oldNode, instantiation.asCondition(trueValue));
257        }
258    }
259
260    /**
261     * Replaces the usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode} that does
262     * materializes the result of the type test.
263     */
264    public static class MaterializationUsageReplacer extends InstanceOfUsageReplacer {
265
266        public final ConditionalNode usage;
267
268        public MaterializationUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, ConditionalNode usage) {
269            super(instantiation, instanceOf, trueValue, falseValue);
270            this.usage = usage;
271        }
272
273        @Override
274        public void replaceUsingInstantiation() {
275            ValueNode newValue = instantiation.asMaterialization(usage.graph(), trueValue, falseValue);
276            usage.replaceAtUsages(newValue);
277            assert usage.hasNoUsages();
278            GraphUtil.killWithUnusedFloatingInputs(usage);
279        }
280
281        @Override
282        public void replace(ValueNode oldNode, ValueNode newNode) {
283            assert newNode instanceof PhiNode;
284            assert oldNode == instanceOf;
285            newNode.inferStamp();
286            instantiation.initialize(newNode, trueValue, falseValue);
287            usage.replaceAtUsages(newNode);
288            assert usage.hasNoUsages();
289            GraphUtil.killWithUnusedFloatingInputs(usage);
290        }
291    }
292}
293