1/*
2 * Copyright (c) 2011, 2016, 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.core.common.CompilationIdentifier.INVALID_COMPILATION_ID;
26import static org.graalvm.compiler.core.common.GraalOptions.DeoptALot;
27import static org.graalvm.compiler.core.common.GraalOptions.UseSnippetGraphCache;
28import static org.graalvm.compiler.java.BytecodeParserOptions.InlineDuringParsing;
29import static org.graalvm.compiler.java.BytecodeParserOptions.InlineIntrinsicsDuringParsing;
30import static org.graalvm.compiler.nodes.StructuredGraph.NO_PROFILING_INFO;
31import static org.graalvm.compiler.nodes.graphbuilderconf.InlineInvokePlugin.InlineInfo.createIntrinsicInlineInfo;
32import static org.graalvm.compiler.nodes.graphbuilderconf.IntrinsicContext.CompilationContext.INLINE_AFTER_PARSING;
33import static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Required;
34
35import java.util.Map;
36import java.util.concurrent.ConcurrentHashMap;
37import java.util.concurrent.ConcurrentMap;
38
39import org.graalvm.compiler.api.replacements.Fold;
40import org.graalvm.compiler.api.replacements.MethodSubstitution;
41import org.graalvm.compiler.api.replacements.Snippet;
42import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;
43import org.graalvm.compiler.api.replacements.SnippetTemplateCache;
44import org.graalvm.compiler.bytecode.BytecodeProvider;
45import org.graalvm.compiler.bytecode.ResolvedJavaMethodBytecode;
46import org.graalvm.compiler.core.common.CollectionsFactory;
47import org.graalvm.compiler.core.common.GraalOptions;
48import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
49import org.graalvm.compiler.debug.Debug;
50import org.graalvm.compiler.debug.Debug.Scope;
51import org.graalvm.compiler.debug.DebugCloseable;
52import org.graalvm.compiler.debug.DebugTimer;
53import org.graalvm.compiler.debug.GraalError;
54import org.graalvm.compiler.graph.Node;
55import org.graalvm.compiler.graph.Node.NodeIntrinsic;
56import org.graalvm.compiler.java.GraphBuilderPhase;
57import org.graalvm.compiler.java.GraphBuilderPhase.Instance;
58import org.graalvm.compiler.nodes.CallTargetNode;
59import org.graalvm.compiler.nodes.Invoke;
60import org.graalvm.compiler.nodes.StateSplit;
61import org.graalvm.compiler.nodes.StructuredGraph;
62import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;
63import org.graalvm.compiler.nodes.ValueNode;
64import org.graalvm.compiler.nodes.graphbuilderconf.GeneratedInvocationPlugin;
65import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration;
66import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins;
67import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderContext;
68import org.graalvm.compiler.nodes.graphbuilderconf.InlineInvokePlugin;
69import org.graalvm.compiler.nodes.graphbuilderconf.IntrinsicContext;
70import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugin;
71import org.graalvm.compiler.nodes.graphbuilderconf.MethodSubstitutionPlugin;
72import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
73import org.graalvm.compiler.nodes.spi.Replacements;
74import org.graalvm.compiler.nodes.spi.StampProvider;
75import org.graalvm.compiler.options.OptionValue;
76import org.graalvm.compiler.options.OptionValue.OverrideScope;
77import org.graalvm.compiler.phases.OptimisticOptimizations;
78import org.graalvm.compiler.phases.common.CanonicalizerPhase;
79import org.graalvm.compiler.phases.common.ConvertDeoptimizeToGuardPhase;
80import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase;
81import org.graalvm.compiler.phases.tiers.PhaseContext;
82import org.graalvm.compiler.phases.util.Providers;
83import org.graalvm.compiler.word.Word;
84
85import jdk.vm.ci.code.TargetDescription;
86import jdk.vm.ci.meta.ConstantReflectionProvider;
87import jdk.vm.ci.meta.MetaAccessProvider;
88import jdk.vm.ci.meta.ResolvedJavaMethod;
89import jdk.vm.ci.meta.ResolvedJavaType;
90
91public class ReplacementsImpl implements Replacements, InlineInvokePlugin {
92
93    public final Providers providers;
94    public final SnippetReflectionProvider snippetReflection;
95    public final TargetDescription target;
96    private GraphBuilderConfiguration.Plugins graphBuilderPlugins;
97
98    /**
99     * The preprocessed replacement graphs.
100     */
101    protected final ConcurrentMap<ResolvedJavaMethod, StructuredGraph> graphs;
102
103    protected final BytecodeProvider bytecodeProvider;
104
105    public void setGraphBuilderPlugins(GraphBuilderConfiguration.Plugins plugins) {
106        assert this.graphBuilderPlugins == null;
107        this.graphBuilderPlugins = plugins;
108    }
109
110    public GraphBuilderConfiguration.Plugins getGraphBuilderPlugins() {
111        return graphBuilderPlugins;
112    }
113
114    protected boolean hasGeneratedInvocationPluginAnnotation(ResolvedJavaMethod method) {
115        return method.getAnnotation(Node.NodeIntrinsic.class) != null || method.getAnnotation(Fold.class) != null;
116    }
117
118    protected boolean hasGenericInvocationPluginAnnotation(ResolvedJavaMethod method) {
119        return method.getAnnotation(Word.Operation.class) != null;
120    }
121
122    private static final int MAX_GRAPH_INLINING_DEPTH = 100; // more than enough
123
124    /**
125     * Determines whether a given method should be inlined based on whether it has a substitution or
126     * whether the inlining context is already within a substitution.
127     *
128     * @return an object specifying how {@code method} is to be inlined or null if it should not be
129     *         inlined based on substitution related criteria
130     */
131    @Override
132    public InlineInfo shouldInlineInvoke(GraphBuilderContext b, ResolvedJavaMethod method, ValueNode[] args) {
133        ResolvedJavaMethod subst = getSubstitutionMethod(method);
134        if (subst != null) {
135            if (b.parsingIntrinsic() || InlineDuringParsing.getValue() || InlineIntrinsicsDuringParsing.getValue()) {
136                // Forced inlining of intrinsics
137                return createIntrinsicInlineInfo(subst, bytecodeProvider);
138            }
139            return null;
140        }
141        if (b.parsingIntrinsic()) {
142            if (hasGeneratedInvocationPluginAnnotation(method)) {
143                throw new GraalError("%s should have been handled by a %s", method.format("%H.%n(%p)"), GeneratedInvocationPlugin.class.getSimpleName());
144            }
145            if (hasGenericInvocationPluginAnnotation(method)) {
146                throw new GraalError("%s should have been handled by %s", method.format("%H.%n(%p)"), WordOperationPlugin.class.getSimpleName());
147            }
148
149            assert b.getDepth() < MAX_GRAPH_INLINING_DEPTH : "inlining limit exceeded";
150
151            if (method.getName().startsWith("$jacoco")) {
152                throw new GraalError("Found call to JaCoCo instrumentation method " + method.format("%H.%n(%p)") + ". Placing \"//JaCoCo Exclude\" anywhere in " +
153                                b.getMethod().getDeclaringClass().getSourceFileName() + " should fix this.");
154            }
155
156            // Force inlining when parsing replacements
157            return createIntrinsicInlineInfo(method, bytecodeProvider);
158        } else {
159            assert method.getAnnotation(NodeIntrinsic.class) == null : String.format("@%s method %s must only be called from within a replacement%n%s", NodeIntrinsic.class.getSimpleName(),
160                            method.format("%h.%n"), b);
161        }
162        return null;
163    }
164
165    @Override
166    public void notifyNotInlined(GraphBuilderContext b, ResolvedJavaMethod method, Invoke invoke) {
167        if (b.parsingIntrinsic()) {
168            IntrinsicContext intrinsic = b.getIntrinsic();
169            if (!intrinsic.isCallToOriginal(method)) {
170                throw new GraalError("All non-recursive calls in the intrinsic %s must be inlined or intrinsified: found call to %s",
171                                intrinsic.getIntrinsicMethod().format("%H.%n(%p)"), method.format("%h.%n(%p)"));
172            }
173        }
174    }
175
176    // This map is key'ed by a class name instead of a Class object so that
177    // it is stable across VM executions (in support of replay compilation).
178    private final Map<String, SnippetTemplateCache> snippetTemplateCache;
179
180    public ReplacementsImpl(Providers providers, SnippetReflectionProvider snippetReflection, BytecodeProvider bytecodeProvider, TargetDescription target) {
181        this.providers = providers.copyWith(this);
182        this.snippetReflection = snippetReflection;
183        this.target = target;
184        this.graphs = new ConcurrentHashMap<>();
185        this.snippetTemplateCache = CollectionsFactory.newMap();
186        this.bytecodeProvider = bytecodeProvider;
187    }
188
189    private static final DebugTimer SnippetPreparationTime = Debug.timer("SnippetPreparationTime");
190
191    @Override
192    public StructuredGraph getSnippet(ResolvedJavaMethod method, Object[] args) {
193        return getSnippet(method, null, args);
194    }
195
196    @Override
197    @SuppressWarnings("try")
198    public StructuredGraph getSnippet(ResolvedJavaMethod method, ResolvedJavaMethod recursiveEntry, Object[] args) {
199        assert method.getAnnotation(Snippet.class) != null : "Snippet must be annotated with @" + Snippet.class.getSimpleName();
200        assert method.hasBytecodes() : "Snippet must not be abstract or native";
201
202        StructuredGraph graph = UseSnippetGraphCache.getValue() ? graphs.get(method) : null;
203        if (graph == null) {
204            try (DebugCloseable a = SnippetPreparationTime.start()) {
205                StructuredGraph newGraph = makeGraph(method, args, recursiveEntry);
206                Debug.counter("SnippetNodeCount[%#s]", method).add(newGraph.getNodeCount());
207                if (!UseSnippetGraphCache.getValue() || args != null) {
208                    return newGraph;
209                }
210                graphs.putIfAbsent(method, newGraph);
211                graph = graphs.get(method);
212            }
213        }
214        return graph;
215    }
216
217    @Override
218    public void registerSnippet(ResolvedJavaMethod method) {
219        // No initialization needed as snippet graphs are created on demand in getSnippet
220    }
221
222    @Override
223    public boolean hasSubstitution(ResolvedJavaMethod method, int invokeBci) {
224        InvocationPlugin plugin = graphBuilderPlugins.getInvocationPlugins().lookupInvocation(method);
225        return plugin != null && (!plugin.inlineOnly() || invokeBci >= 0);
226    }
227
228    @Override
229    public BytecodeProvider getReplacementBytecodeProvider() {
230        return bytecodeProvider;
231    }
232
233    @Override
234    public ResolvedJavaMethod getSubstitutionMethod(ResolvedJavaMethod method) {
235        InvocationPlugin plugin = graphBuilderPlugins.getInvocationPlugins().lookupInvocation(method);
236        if (plugin instanceof MethodSubstitutionPlugin) {
237            MethodSubstitutionPlugin msPlugin = (MethodSubstitutionPlugin) plugin;
238            return msPlugin.getSubstitute(providers.getMetaAccess());
239        }
240        return null;
241    }
242
243    @Override
244    public StructuredGraph getSubstitution(ResolvedJavaMethod method, int invokeBci) {
245        StructuredGraph result;
246        InvocationPlugin plugin = graphBuilderPlugins.getInvocationPlugins().lookupInvocation(method);
247        if (plugin != null && (!plugin.inlineOnly() || invokeBci >= 0)) {
248            MetaAccessProvider metaAccess = providers.getMetaAccess();
249            if (plugin instanceof MethodSubstitutionPlugin) {
250                MethodSubstitutionPlugin msPlugin = (MethodSubstitutionPlugin) plugin;
251                ResolvedJavaMethod substitute = msPlugin.getSubstitute(metaAccess);
252                StructuredGraph graph = graphs.get(substitute);
253                if (graph == null) {
254                    graph = makeGraph(substitute, null, method);
255                    graph.freeze();
256                    graphs.putIfAbsent(substitute, graph);
257                    graph = graphs.get(substitute);
258                }
259                assert graph.isFrozen();
260                result = graph;
261            } else {
262                ResolvedJavaMethodBytecode code = new ResolvedJavaMethodBytecode(method);
263                ConstantReflectionProvider constantReflection = providers.getConstantReflection();
264                ConstantFieldProvider constantFieldProvider = providers.getConstantFieldProvider();
265                StampProvider stampProvider = providers.getStampProvider();
266                result = new IntrinsicGraphBuilder(metaAccess, constantReflection, constantFieldProvider, stampProvider, code, invokeBci).buildGraph(plugin);
267            }
268        } else {
269            result = null;
270        }
271        return result;
272    }
273
274    /**
275     * Creates a preprocessed graph for a snippet or method substitution.
276     *
277     * @param method the snippet or method substitution for which a graph will be created
278     * @param args
279     * @param original the original method if {@code method} is a {@linkplain MethodSubstitution
280     *            substitution} otherwise null
281     */
282    @SuppressWarnings("try")
283    public StructuredGraph makeGraph(ResolvedJavaMethod method, Object[] args, ResolvedJavaMethod original) {
284        try (OverrideScope s = OptionValue.override(DeoptALot, false)) {
285            return createGraphMaker(method, original).makeGraph(args);
286        }
287    }
288
289    /**
290     * Can be overridden to return an object that specializes various parts of graph preprocessing.
291     */
292    protected GraphMaker createGraphMaker(ResolvedJavaMethod substitute, ResolvedJavaMethod original) {
293        return new GraphMaker(this, substitute, original);
294    }
295
296    /**
297     * Creates and preprocesses a graph for a replacement.
298     */
299    public static class GraphMaker {
300
301        /** The replacements object that the graphs are created for. */
302        protected final ReplacementsImpl replacements;
303
304        /**
305         * The method for which a graph is being created.
306         */
307        protected final ResolvedJavaMethod method;
308
309        /**
310         * The original method which {@link #method} is substituting. Calls to {@link #method} or
311         * {@link #substitutedMethod} will be replaced with a forced inline of
312         * {@link #substitutedMethod}.
313         */
314        protected final ResolvedJavaMethod substitutedMethod;
315
316        protected GraphMaker(ReplacementsImpl replacements, ResolvedJavaMethod substitute, ResolvedJavaMethod substitutedMethod) {
317            this.replacements = replacements;
318            this.method = substitute;
319            this.substitutedMethod = substitutedMethod;
320        }
321
322        @SuppressWarnings("try")
323        public StructuredGraph makeGraph(Object[] args) {
324            try (Scope s = Debug.scope("BuildSnippetGraph", method)) {
325                assert method.hasBytecodes() : method;
326                StructuredGraph graph = buildInitialGraph(method, args);
327
328                finalizeGraph(graph);
329
330                Debug.dump(Debug.INFO_LOG_LEVEL, graph, "%s: Final", method.getName());
331
332                return graph;
333            } catch (Throwable e) {
334                throw Debug.handle(e);
335            }
336        }
337
338        /**
339         * Does final processing of a snippet graph.
340         */
341        protected void finalizeGraph(StructuredGraph graph) {
342            if (!GraalOptions.SnippetCounters.getValue() || graph.getNodes().filter(SnippetCounterNode.class).isEmpty()) {
343                int sideEffectCount = 0;
344                assert (sideEffectCount = graph.getNodes().filter(e -> hasSideEffect(e)).count()) >= 0;
345                new ConvertDeoptimizeToGuardPhase().apply(graph, null);
346                assert sideEffectCount == graph.getNodes().filter(e -> hasSideEffect(e)).count() : "deleted side effecting node";
347
348                new DeadCodeEliminationPhase(Required).apply(graph);
349            } else {
350                // ConvertDeoptimizeToGuardPhase will eliminate snippet counters on paths
351                // that terminate in a deopt so we disable it if the graph contains
352                // snippet counters. The trade off is that we miss out on guard
353                // coalescing opportunities.
354            }
355        }
356
357        /**
358         * Filter nodes which have side effects and shouldn't be deleted from snippets when
359         * converting deoptimizations to guards. Currently this only allows exception constructors
360         * to be eliminated to cover the case when Java assertions are in the inlined code.
361         *
362         * @param node
363         * @return true for nodes that have side effects and are unsafe to delete
364         */
365        private boolean hasSideEffect(Node node) {
366            if (node instanceof StateSplit) {
367                if (((StateSplit) node).hasSideEffect()) {
368                    if (node instanceof Invoke) {
369                        CallTargetNode callTarget = ((Invoke) node).callTarget();
370                        if (callTarget instanceof MethodCallTargetNode) {
371                            ResolvedJavaMethod targetMethod = ((MethodCallTargetNode) callTarget).targetMethod();
372                            if (targetMethod.isConstructor()) {
373                                ResolvedJavaType throwableType = replacements.providers.getMetaAccess().lookupJavaType(Throwable.class);
374                                return !throwableType.isAssignableFrom(targetMethod.getDeclaringClass());
375                            }
376                        }
377                    }
378                    // Not an exception constructor call
379                    return true;
380                }
381            }
382            // Not a StateSplit
383            return false;
384        }
385
386        /**
387         * Builds the initial graph for a snippet.
388         */
389        @SuppressWarnings("try")
390        protected StructuredGraph buildInitialGraph(final ResolvedJavaMethod methodToParse, Object[] args) {
391            // Replacements cannot have optimistic assumptions since they have
392            // to be valid for the entire run of the VM.
393
394            final StructuredGraph graph = new StructuredGraph(methodToParse, AllowAssumptions.NO, NO_PROFILING_INFO, INVALID_COMPILATION_ID);
395
396            // They are not user code so they do not participate in unsafe access tracking
397            graph.disableUnsafeAccessTracking();
398
399            try (Scope s = Debug.scope("buildInitialGraph", graph)) {
400                MetaAccessProvider metaAccess = replacements.providers.getMetaAccess();
401
402                Plugins plugins = new Plugins(replacements.graphBuilderPlugins);
403                GraphBuilderConfiguration config = GraphBuilderConfiguration.getSnippetDefault(plugins);
404                if (args != null) {
405                    plugins.prependParameterPlugin(new ConstantBindingParameterPlugin(args, metaAccess, replacements.snippetReflection));
406                }
407
408                IntrinsicContext initialIntrinsicContext = null;
409                if (method.getAnnotation(Snippet.class) == null) {
410                    // Post-parse inlined intrinsic
411                    initialIntrinsicContext = new IntrinsicContext(substitutedMethod, method, replacements.bytecodeProvider, INLINE_AFTER_PARSING);
412                } else {
413                    // Snippet
414                    ResolvedJavaMethod original = substitutedMethod != null ? substitutedMethod : method;
415                    initialIntrinsicContext = new IntrinsicContext(original, method, replacements.bytecodeProvider, INLINE_AFTER_PARSING);
416                }
417
418                createGraphBuilder(metaAccess, replacements.providers.getStampProvider(), replacements.providers.getConstantReflection(), replacements.providers.getConstantFieldProvider(), config,
419                                OptimisticOptimizations.NONE, initialIntrinsicContext).apply(graph);
420
421                new CanonicalizerPhase().apply(graph, new PhaseContext(replacements.providers));
422            } catch (Throwable e) {
423                throw Debug.handle(e);
424            }
425            return graph;
426        }
427
428        protected Instance createGraphBuilder(MetaAccessProvider metaAccess, StampProvider stampProvider, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider,
429                        GraphBuilderConfiguration graphBuilderConfig, OptimisticOptimizations optimisticOpts, IntrinsicContext initialIntrinsicContext) {
430            return new GraphBuilderPhase.Instance(metaAccess, stampProvider, constantReflection, constantFieldProvider, graphBuilderConfig, optimisticOpts,
431                            initialIntrinsicContext);
432        }
433    }
434
435    @Override
436    public void registerSnippetTemplateCache(SnippetTemplateCache templates) {
437        assert snippetTemplateCache.get(templates.getClass().getName()) == null;
438        snippetTemplateCache.put(templates.getClass().getName(), templates);
439    }
440
441    @Override
442    public <T extends SnippetTemplateCache> T getSnippetTemplateCache(Class<T> templatesClass) {
443        SnippetTemplateCache ret = snippetTemplateCache.get(templatesClass.getName());
444        return templatesClass.cast(ret);
445    }
446}
447