001/*
002 * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.replacements;
024
025import static com.oracle.graal.nodes.calc.CompareNode.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.code.*;
030
031import com.oracle.graal.api.replacements.*;
032import com.oracle.graal.compiler.common.calc.*;
033import com.oracle.graal.graph.*;
034import com.oracle.graal.nodes.*;
035import com.oracle.graal.nodes.calc.*;
036import com.oracle.graal.nodes.java.*;
037import com.oracle.graal.nodes.spi.*;
038import com.oracle.graal.nodes.util.*;
039import com.oracle.graal.phases.util.*;
040import com.oracle.graal.replacements.SnippetTemplate.AbstractTemplates;
041import com.oracle.graal.replacements.SnippetTemplate.Arguments;
042import com.oracle.graal.replacements.SnippetTemplate.UsageReplacer;
043
044/**
045 * Helper class for lowering {@link InstanceOfNode}s with snippets. The majority of the complexity
046 * in such a lowering derives from the fact that {@link InstanceOfNode} is a floating node. A
047 * snippet used to lower an {@link InstanceOfNode} will almost always incorporate control flow and
048 * replacing a floating node with control flow is not trivial.
049 * <p>
050 * The mechanism implemented in this class ensures that the graph for an instanceof snippet is
051 * instantiated once per {@link InstanceOfNode} being lowered. The result produced is then re-used
052 * by all usages of the node. Additionally, if there is a single usage that is an {@link IfNode},
053 * the control flow in the snippet is connected directly to the true and false successors of the
054 * {@link IfNode}. This avoids materializing the instanceof test as a boolean which is then retested
055 * by the {@link IfNode}.
056 */
057public abstract class InstanceOfSnippetsTemplates extends AbstractTemplates {
058
059    public InstanceOfSnippetsTemplates(Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target) {
060        super(providers, snippetReflection, target);
061    }
062
063    /**
064     * Gets the arguments used to retrieve and instantiate an instanceof snippet template.
065     */
066    protected abstract Arguments makeArguments(InstanceOfUsageReplacer replacer, LoweringTool tool);
067
068    public void lower(FloatingNode instanceOf, LoweringTool tool) {
069        assert instanceOf instanceof InstanceOfNode || instanceOf instanceof TypeCheckNode || instanceOf instanceof InstanceOfDynamicNode || instanceOf instanceof ClassIsAssignableFromNode;
070        List<Node> usages = instanceOf.usages().snapshot();
071
072        Instantiation instantiation = new Instantiation();
073        for (Node usage : usages) {
074            final StructuredGraph graph = (StructuredGraph) usage.graph();
075
076            InstanceOfUsageReplacer replacer = createReplacer(instanceOf, instantiation, usage, graph);
077
078            if (instantiation.isInitialized()) {
079                // No need to re-instantiate the snippet - just re-use its result
080                replacer.replaceUsingInstantiation();
081            } else {
082                Arguments args = makeArguments(replacer, tool);
083                template(args).instantiate(providers.getMetaAccess(), instanceOf, replacer, tool, args);
084            }
085        }
086
087        assert instanceOf.hasNoUsages();
088        if (!instanceOf.isDeleted()) {
089            GraphUtil.killWithUnusedFloatingInputs(instanceOf);
090        }
091    }
092
093    /**
094     * Gets the specific replacer object used to replace the usage of an instanceof node with the
095     * result of an instantiated instanceof snippet.
096     */
097    protected InstanceOfUsageReplacer createReplacer(FloatingNode instanceOf, Instantiation instantiation, Node usage, final StructuredGraph graph) {
098        InstanceOfUsageReplacer replacer;
099        if (usage instanceof IfNode || usage instanceof FixedGuardNode || usage instanceof ShortCircuitOrNode || usage instanceof ConditionAnchorNode) {
100            ValueNode trueValue = ConstantNode.forInt(1, graph);
101            ValueNode falseValue = ConstantNode.forInt(0, graph);
102            if (instantiation.isInitialized() && (trueValue != instantiation.trueValue || falseValue != instantiation.falseValue)) {
103                /*
104                 * This code doesn't really care what values are used so adopt the values from the
105                 * previous instantiation.
106                 */
107                trueValue = instantiation.trueValue;
108                falseValue = instantiation.falseValue;
109            }
110            replacer = new NonMaterializationUsageReplacer(instantiation, trueValue, falseValue, instanceOf, usage);
111        } else {
112            assert usage instanceof ConditionalNode : "unexpected usage of " + instanceOf + ": " + usage;
113            ConditionalNode c = (ConditionalNode) usage;
114            replacer = new MaterializationUsageReplacer(instantiation, c.trueValue(), c.falseValue(), instanceOf, c);
115        }
116        return replacer;
117    }
118
119    /**
120     * The result of instantiating an instanceof snippet. This enables a snippet instantiation to be
121     * re-used which reduces compile time and produces better code.
122     */
123    public static final class Instantiation {
124
125        private ValueNode result;
126        private LogicNode condition;
127        private ValueNode trueValue;
128        private ValueNode falseValue;
129
130        /**
131         * Determines if the instantiation has occurred.
132         */
133        boolean isInitialized() {
134            return result != null;
135        }
136
137        void initialize(ValueNode r, ValueNode t, ValueNode f) {
138            assert !isInitialized();
139            this.result = r;
140            this.trueValue = t;
141            this.falseValue = f;
142        }
143
144        /**
145         * Gets the result of this instantiation as a condition.
146         *
147         * @param testValue the returned condition is true if the result is equal to this value
148         */
149        LogicNode asCondition(ValueNode testValue) {
150            assert isInitialized();
151            if (result.isConstant()) {
152                assert testValue.isConstant();
153                return LogicConstantNode.forBoolean(result.asConstant().equals(testValue.asConstant()), result.graph());
154            }
155            if (condition == null || (!(condition instanceof CompareNode)) || ((CompareNode) condition).getY() != testValue) {
156                // Re-use previously generated condition if the trueValue for the test is the same
157                condition = createCompareNode(result.graph(), Condition.EQ, result, testValue, null);
158            }
159            return condition;
160        }
161
162        /**
163         * Gets the result of the instantiation as a materialized value.
164         *
165         * @param t the true value for the materialization
166         * @param f the false value for the materialization
167         */
168        ValueNode asMaterialization(StructuredGraph graph, ValueNode t, ValueNode f) {
169            assert isInitialized();
170            if (t == this.trueValue && f == this.falseValue) {
171                // Can simply use the phi result if the same materialized values are expected.
172                return result;
173            } else {
174                return graph.unique(new ConditionalNode(asCondition(trueValue), t, f));
175            }
176        }
177    }
178
179    /**
180     * Replaces a usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode}.
181     */
182    public abstract static class InstanceOfUsageReplacer implements UsageReplacer {
183
184        public final Instantiation instantiation;
185        public final FloatingNode instanceOf;
186        public final ValueNode trueValue;
187        public final ValueNode falseValue;
188
189        public InstanceOfUsageReplacer(Instantiation instantiation, FloatingNode instanceOf, ValueNode trueValue, ValueNode falseValue) {
190            assert instanceOf instanceof InstanceOfNode || instanceOf instanceof TypeCheckNode || instanceOf instanceof InstanceOfDynamicNode || instanceOf instanceof ClassIsAssignableFromNode;
191            this.instantiation = instantiation;
192            this.instanceOf = instanceOf;
193            this.trueValue = trueValue;
194            this.falseValue = falseValue;
195        }
196
197        /**
198         * Does the replacement based on a previously snippet instantiation.
199         */
200        public abstract void replaceUsingInstantiation();
201    }
202
203    /**
204     * Replaces the usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode} that does
205     * not materialize the result of the type test.
206     */
207    public static class NonMaterializationUsageReplacer extends InstanceOfUsageReplacer {
208
209        private final Node usage;
210
211        public NonMaterializationUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, Node usage) {
212            super(instantiation, instanceOf, trueValue, falseValue);
213            this.usage = usage;
214        }
215
216        @Override
217        public void replaceUsingInstantiation() {
218            usage.replaceFirstInput(instanceOf, instantiation.asCondition(trueValue));
219        }
220
221        @Override
222        public void replace(ValueNode oldNode, ValueNode newNode) {
223            assert newNode instanceof PhiNode;
224            assert oldNode == instanceOf;
225            newNode.inferStamp();
226            instantiation.initialize(newNode, trueValue, falseValue);
227            usage.replaceFirstInput(oldNode, instantiation.asCondition(trueValue));
228        }
229    }
230
231    /**
232     * Replaces the usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode} that does
233     * materializes the result of the type test.
234     */
235    public static class MaterializationUsageReplacer extends InstanceOfUsageReplacer {
236
237        public final ConditionalNode usage;
238
239        public MaterializationUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, ConditionalNode usage) {
240            super(instantiation, instanceOf, trueValue, falseValue);
241            this.usage = usage;
242        }
243
244        @Override
245        public void replaceUsingInstantiation() {
246            ValueNode newValue = instantiation.asMaterialization(usage.graph(), trueValue, falseValue);
247            usage.replaceAtUsages(newValue);
248            assert usage.hasNoUsages();
249            GraphUtil.killWithUnusedFloatingInputs(usage);
250        }
251
252        @Override
253        public void replace(ValueNode oldNode, ValueNode newNode) {
254            assert newNode instanceof PhiNode;
255            assert oldNode == instanceOf;
256            newNode.inferStamp();
257            instantiation.initialize(newNode, trueValue, falseValue);
258            usage.replaceAtUsages(newNode);
259            assert usage.hasNoUsages();
260            GraphUtil.killWithUnusedFloatingInputs(usage);
261        }
262    }
263}