001/*
002 * Copyright (c) 2013, 2015, 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.truffle;
024
025import static com.oracle.graal.truffle.TruffleCompilerOptions.*;
026
027import java.lang.invoke.*;
028import java.util.*;
029
030import jdk.internal.jvmci.code.*;
031import jdk.internal.jvmci.common.*;
032import com.oracle.graal.debug.*;
033import com.oracle.graal.debug.Debug.*;
034import jdk.internal.jvmci.meta.*;
035import jdk.internal.jvmci.options.*;
036
037import com.oracle.graal.api.replacements.*;
038import com.oracle.graal.compiler.common.type.*;
039import com.oracle.graal.graphbuilderconf.*;
040import com.oracle.graal.graphbuilderconf.GraphBuilderConfiguration.Plugins;
041import com.oracle.graal.java.*;
042import com.oracle.graal.nodes.*;
043import com.oracle.graal.nodes.StructuredGraph.AllowAssumptions;
044import com.oracle.graal.nodes.calc.*;
045import com.oracle.graal.nodes.java.*;
046import com.oracle.graal.nodes.virtual.*;
047import com.oracle.graal.phases.*;
048import com.oracle.graal.phases.common.*;
049import com.oracle.graal.phases.common.inlining.*;
050import com.oracle.graal.phases.tiers.*;
051import com.oracle.graal.phases.util.*;
052import com.oracle.graal.replacements.*;
053import com.oracle.graal.truffle.debug.*;
054import com.oracle.graal.truffle.nodes.*;
055import com.oracle.graal.truffle.nodes.asserts.*;
056import com.oracle.graal.truffle.nodes.frame.*;
057import com.oracle.graal.truffle.nodes.frame.NewFrameNode.VirtualOnlyInstanceNode;
058import com.oracle.graal.truffle.phases.*;
059import com.oracle.graal.truffle.substitutions.*;
060import com.oracle.graal.virtual.phases.ea.*;
061import com.oracle.truffle.api.*;
062import com.oracle.truffle.api.CompilerDirectives.TruffleBoundary;
063import com.oracle.truffle.api.nodes.*;
064
065/**
066 * Class performing the partial evaluation starting from the root node of an AST.
067 */
068public class PartialEvaluator {
069
070    @Option(help = "New partial evaluation on Graal graphs", type = OptionType.Expert)//
071    public static final StableOptionValue<Boolean> GraphPE = new StableOptionValue<>(true);
072
073    protected final Providers providers;
074    protected final Architecture architecture;
075    private final CanonicalizerPhase canonicalizer;
076    private final SnippetReflectionProvider snippetReflection;
077    private final ResolvedJavaMethod callDirectMethod;
078    private final ResolvedJavaMethod callInlinedMethod;
079    private final ResolvedJavaMethod callSiteProxyMethod;
080    private final ResolvedJavaMethod callRootMethod;
081    private final GraphBuilderConfiguration configForRoot;
082
083    public PartialEvaluator(Providers providers, GraphBuilderConfiguration configForRoot, SnippetReflectionProvider snippetReflection, Architecture architecture) {
084        this.providers = providers;
085        this.architecture = architecture;
086        this.canonicalizer = new CanonicalizerPhase();
087        this.snippetReflection = snippetReflection;
088        this.callDirectMethod = providers.getMetaAccess().lookupJavaMethod(OptimizedCallTarget.getCallDirectMethod());
089        this.callInlinedMethod = providers.getMetaAccess().lookupJavaMethod(OptimizedCallTarget.getCallInlinedMethod());
090        this.callSiteProxyMethod = providers.getMetaAccess().lookupJavaMethod(GraalFrameInstance.CallNodeFrame.METHOD);
091        this.configForRoot = configForRoot;
092
093        try {
094            callRootMethod = providers.getMetaAccess().lookupJavaMethod(OptimizedCallTarget.class.getDeclaredMethod("callRoot", Object[].class));
095        } catch (NoSuchMethodException ex) {
096            throw new RuntimeException(ex);
097        }
098    }
099
100    public Providers getProviders() {
101        return providers;
102    }
103
104    public SnippetReflectionProvider getSnippetReflection() {
105        return snippetReflection;
106    }
107
108    public ResolvedJavaMethod[] getCompilationRootMethods() {
109        return new ResolvedJavaMethod[]{callRootMethod, callInlinedMethod};
110    }
111
112    public ResolvedJavaMethod[] getNeverInlineMethods() {
113        return new ResolvedJavaMethod[]{callSiteProxyMethod, callDirectMethod};
114    }
115
116    public StructuredGraph createGraph(final OptimizedCallTarget callTarget, AllowAssumptions allowAssumptions) {
117        try (Scope c = Debug.scope("TruffleTree")) {
118            Debug.dump(callTarget, "truffle tree");
119        } catch (Throwable e) {
120            throw Debug.handle(e);
121        }
122
123        final StructuredGraph graph = new StructuredGraph(callTarget.toString(), callRootMethod, allowAssumptions, callTarget.getSpeculationLog());
124        assert graph != null : "no graph for root method";
125
126        try (Scope s = Debug.scope("CreateGraph", graph); Indent indent = Debug.logAndIndent("createGraph %s", graph)) {
127
128            PhaseContext baseContext = new PhaseContext(providers);
129            HighTierContext tierContext = new HighTierContext(providers, new PhaseSuite<HighTierContext>(), OptimisticOptimizations.NONE);
130
131            fastPartialEvaluation(callTarget, graph, baseContext, tierContext);
132
133            if (Thread.currentThread().isInterrupted()) {
134                return null;
135            }
136
137            new VerifyFrameDoesNotEscapePhase().apply(graph, false);
138            postPartialEvaluation(graph);
139
140        } catch (Throwable e) {
141            throw Debug.handle(e);
142        }
143
144        return graph;
145    }
146
147    private class InterceptReceiverPlugin implements ParameterPlugin {
148
149        private final Object receiver;
150
151        public InterceptReceiverPlugin(Object receiver) {
152            this.receiver = receiver;
153        }
154
155        public FloatingNode interceptParameter(GraphBuilderContext b, int index, Stamp stamp) {
156            if (index == 0) {
157                return ConstantNode.forConstant(snippetReflection.forObject(receiver), providers.getMetaAccess());
158            }
159            return null;
160        }
161    }
162
163    private class PEInlineInvokePlugin implements InlineInvokePlugin {
164
165        private Deque<TruffleInlining> inlining;
166        private OptimizedDirectCallNode lastDirectCallNode;
167        private final ReplacementsImpl replacements;
168
169        public PEInlineInvokePlugin(TruffleInlining inlining, ReplacementsImpl replacements) {
170            this.inlining = new ArrayDeque<>();
171            this.inlining.push(inlining);
172            this.replacements = replacements;
173        }
174
175        @Override
176        public InlineInfo shouldInlineInvoke(GraphBuilderContext builder, ResolvedJavaMethod original, ValueNode[] arguments, JavaType returnType) {
177            TruffleBoundary truffleBoundary = original.getAnnotation(TruffleBoundary.class);
178            if (truffleBoundary != null) {
179                return truffleBoundary.throwsControlFlowException() ? InlineInfo.DO_NOT_INLINE_WITH_EXCEPTION : InlineInfo.DO_NOT_INLINE_NO_EXCEPTION;
180            }
181            if (replacements.hasSubstitution(original, builder.bci())) {
182                return InlineInfo.DO_NOT_INLINE_NO_EXCEPTION;
183            }
184            assert !builder.parsingIntrinsic();
185
186            if (TruffleCompilerOptions.TruffleFunctionInlining.getValue()) {
187                if (original.equals(callSiteProxyMethod)) {
188                    ValueNode arg1 = arguments[0];
189                    if (!arg1.isConstant()) {
190                        JVMCIError.shouldNotReachHere("The direct call node does not resolve to a constant!");
191                    }
192
193                    Object callNode = snippetReflection.asObject(Object.class, (JavaConstant) arg1.asConstant());
194                    if (callNode instanceof OptimizedDirectCallNode) {
195                        OptimizedDirectCallNode directCallNode = (OptimizedDirectCallNode) callNode;
196                        lastDirectCallNode = directCallNode;
197                    }
198                } else if (original.equals(callDirectMethod)) {
199                    TruffleInliningDecision decision = getDecision(inlining.peek(), lastDirectCallNode);
200                    lastDirectCallNode = null;
201                    if (decision != null && decision.isInline()) {
202                        inlining.push(decision);
203                        builder.getAssumptions().record(new AssumptionValidAssumption((OptimizedAssumption) decision.getTarget().getNodeRewritingAssumption()));
204                        return new InlineInfo(callInlinedMethod, false);
205                    }
206                }
207            }
208
209            return new InlineInfo(original, false);
210        }
211
212        @Override
213        public void notifyAfterInline(ResolvedJavaMethod inlinedTargetMethod) {
214            if (inlinedTargetMethod.equals(callInlinedMethod)) {
215                inlining.pop();
216            }
217        }
218    }
219
220    private class ParsingInlineInvokePlugin implements InlineInvokePlugin {
221
222        private final ReplacementsImpl replacements;
223        private final InvocationPlugins invocationPlugins;
224        private final LoopExplosionPlugin loopExplosionPlugin;
225
226        public ParsingInlineInvokePlugin(ReplacementsImpl replacements, InvocationPlugins invocationPlugins, LoopExplosionPlugin loopExplosionPlugin) {
227            this.replacements = replacements;
228            this.invocationPlugins = invocationPlugins;
229            this.loopExplosionPlugin = loopExplosionPlugin;
230        }
231
232        private boolean hasMethodHandleArgument(ValueNode[] arguments) {
233            for (ValueNode argument : arguments) {
234                if (argument.isConstant()) {
235                    JavaConstant constant = argument.asJavaConstant();
236                    if (constant.getKind() == Kind.Object && snippetReflection.asObject(MethodHandle.class, constant) != null) {
237                        return true;
238                    }
239                }
240            }
241            return false;
242        }
243
244        @Override
245        public InlineInfo shouldInlineInvoke(GraphBuilderContext builder, ResolvedJavaMethod original, ValueNode[] arguments, JavaType returnType) {
246            if (invocationPlugins.lookupInvocation(original) != null) {
247                return InlineInfo.DO_NOT_INLINE_NO_EXCEPTION;
248            } else if (loopExplosionPlugin.shouldExplodeLoops(original)) {
249                return InlineInfo.DO_NOT_INLINE_WITH_EXCEPTION;
250            }
251            TruffleBoundary truffleBoundary = original.getAnnotation(TruffleBoundary.class);
252            if (truffleBoundary != null) {
253                return truffleBoundary.throwsControlFlowException() ? InlineInfo.DO_NOT_INLINE_WITH_EXCEPTION : InlineInfo.DO_NOT_INLINE_NO_EXCEPTION;
254            }
255            if (replacements.hasSubstitution(original, builder.bci())) {
256                return InlineInfo.DO_NOT_INLINE_NO_EXCEPTION;
257            }
258
259            if (original.equals(callSiteProxyMethod) || original.equals(callDirectMethod)) {
260                return InlineInfo.DO_NOT_INLINE_WITH_EXCEPTION;
261            }
262            if (hasMethodHandleArgument(arguments)) {
263                /*
264                 * We want to inline invokes that have a constant MethodHandle parameter to remove
265                 * invokedynamic related calls as early as possible.
266                 */
267                return new InlineInfo(original, false);
268            }
269            return null;
270        }
271    }
272
273    private class PELoopExplosionPlugin implements LoopExplosionPlugin {
274
275        public boolean shouldExplodeLoops(ResolvedJavaMethod method) {
276            return method.getAnnotation(ExplodeLoop.class) != null;
277        }
278
279        public boolean shouldMergeExplosions(ResolvedJavaMethod method) {
280            ExplodeLoop explodeLoop = method.getAnnotation(ExplodeLoop.class);
281            if (explodeLoop != null) {
282                return explodeLoop.merge();
283            }
284            return false;
285        }
286
287    }
288
289    protected void doFastPE(OptimizedCallTarget callTarget, StructuredGraph graph) {
290        GraphBuilderConfiguration newConfig = configForRoot.copy();
291        InvocationPlugins invocationPlugins = newConfig.getPlugins().getInvocationPlugins();
292        TruffleGraphBuilderPlugins.registerInvocationPlugins(providers.getMetaAccess(), invocationPlugins, false, snippetReflection);
293
294        newConfig.setUseProfiling(false);
295        Plugins plugins = newConfig.getPlugins();
296        plugins.prependParameterPlugin(new InterceptReceiverPlugin(callTarget));
297        callTarget.setInlining(new TruffleInlining(callTarget, new DefaultInliningPolicy()));
298        plugins.setLoopExplosionPlugin(new PELoopExplosionPlugin());
299
300        ReplacementsImpl replacements = (ReplacementsImpl) providers.getReplacements();
301        plugins.clearInlineInvokePlugins();
302        plugins.appendInlineInvokePlugin(replacements);
303        plugins.appendInlineInvokePlugin(new PEInlineInvokePlugin(callTarget.getInlining(), replacements));
304        HistogramInlineInvokePlugin histogramPlugin = null;
305        if (PrintTruffleExpansionHistogram.getValue()) {
306            histogramPlugin = new HistogramInlineInvokePlugin(graph);
307            plugins.appendInlineInvokePlugin(histogramPlugin);
308        }
309
310        new GraphBuilderPhase.Instance(providers.getMetaAccess(), providers.getStampProvider(), providers.getConstantReflection(), newConfig, TruffleCompiler.Optimizations, null).apply(graph);
311
312        if (PrintTruffleExpansionHistogram.getValue()) {
313            histogramPlugin.print(callTarget);
314        }
315    }
316
317    protected PEGraphDecoder createGraphDecoder(StructuredGraph graph) {
318        GraphBuilderConfiguration newConfig = configForRoot.copy();
319        InvocationPlugins parsingInvocationPlugins = newConfig.getPlugins().getInvocationPlugins();
320        TruffleGraphBuilderPlugins.registerInvocationPlugins(providers.getMetaAccess(), parsingInvocationPlugins, true, snippetReflection);
321
322        LoopExplosionPlugin loopExplosionPlugin = new PELoopExplosionPlugin();
323
324        newConfig.setUseProfiling(false);
325        Plugins plugins = newConfig.getPlugins();
326        ReplacementsImpl replacements = (ReplacementsImpl) providers.getReplacements();
327        plugins.clearInlineInvokePlugins();
328        plugins.appendInlineInvokePlugin(replacements);
329        plugins.appendInlineInvokePlugin(new ParsingInlineInvokePlugin(replacements, parsingInvocationPlugins, loopExplosionPlugin));
330        if (!PrintTruffleExpansionHistogram.getValue()) {
331            plugins.appendInlineInvokePlugin(new InlineDuringParsingPlugin());
332        }
333
334        return new CachingPEGraphDecoder(providers, newConfig, TruffleCompiler.Optimizations, AllowAssumptions.from(graph.getAssumptions() != null), architecture);
335    }
336
337    protected void doGraphPE(OptimizedCallTarget callTarget, StructuredGraph graph) {
338        callTarget.setInlining(new TruffleInlining(callTarget, new DefaultInliningPolicy()));
339
340        PEGraphDecoder decoder = createGraphDecoder(graph);
341
342        LoopExplosionPlugin loopExplosionPlugin = new PELoopExplosionPlugin();
343        ParameterPlugin parameterPlugin = new InterceptReceiverPlugin(callTarget);
344        InvocationPlugins invocationPlugins = createDecodingInvocationPlugins();
345
346        ReplacementsImpl replacements = (ReplacementsImpl) providers.getReplacements();
347        InlineInvokePlugin[] inlineInvokePlugins;
348        InlineInvokePlugin inlineInvokePlugin = new PEInlineInvokePlugin(callTarget.getInlining(), replacements);
349
350        HistogramInlineInvokePlugin histogramPlugin = null;
351        if (PrintTruffleExpansionHistogram.getValue()) {
352            histogramPlugin = new HistogramInlineInvokePlugin(graph);
353            inlineInvokePlugins = new InlineInvokePlugin[]{replacements, inlineInvokePlugin, histogramPlugin};
354        } else {
355            inlineInvokePlugins = new InlineInvokePlugin[]{replacements, inlineInvokePlugin};
356        }
357
358        decoder.decode(graph, graph.method(), loopExplosionPlugin, invocationPlugins, inlineInvokePlugins, parameterPlugin);
359
360        if (PrintTruffleExpansionHistogram.getValue()) {
361            histogramPlugin.print(callTarget);
362        }
363    }
364
365    protected InvocationPlugins createDecodingInvocationPlugins() {
366        InvocationPlugins decodingInvocationPlugins = new InvocationPlugins(providers.getMetaAccess());
367        TruffleGraphBuilderPlugins.registerInvocationPlugins(providers.getMetaAccess(), decodingInvocationPlugins, false, snippetReflection);
368        return decodingInvocationPlugins;
369    }
370
371    @SuppressWarnings("unused")
372    private void fastPartialEvaluation(OptimizedCallTarget callTarget, StructuredGraph graph, PhaseContext baseContext, HighTierContext tierContext) {
373        if (GraphPE.getValue()) {
374            doGraphPE(callTarget, graph);
375        } else {
376            doFastPE(callTarget, graph);
377        }
378        Debug.dump(graph, "After FastPE");
379
380        graph.maybeCompress();
381
382        // Perform deoptimize to guard conversion.
383        new ConvertDeoptimizeToGuardPhase().apply(graph, tierContext);
384
385        for (MethodCallTargetNode methodCallTargetNode : graph.getNodes(MethodCallTargetNode.TYPE)) {
386            StructuredGraph inlineGraph = providers.getReplacements().getSubstitution(methodCallTargetNode.targetMethod(), methodCallTargetNode.invoke().bci());
387            if (inlineGraph != null) {
388                InliningUtil.inline(methodCallTargetNode.invoke(), inlineGraph, true, null);
389            }
390        }
391
392        // Perform conditional elimination.
393        new DominatorConditionalEliminationPhase(false).apply(graph);
394
395        canonicalizer.apply(graph, tierContext);
396
397        // Do single partial escape and canonicalization pass.
398        try (Scope pe = Debug.scope("TrufflePartialEscape", graph)) {
399            new PartialEscapePhase(false, canonicalizer).apply(graph, tierContext);
400        } catch (Throwable t) {
401            Debug.handle(t);
402        }
403
404        // recompute loop frequencies now that BranchProbabilities have had time to canonicalize
405        ComputeLoopFrequenciesClosure.compute(graph);
406
407        graph.maybeCompress();
408
409        if (TruffleCompilerOptions.TraceTrufflePerformanceWarnings.getValue()) {
410            reportPerformanceWarnings(callTarget, graph);
411        }
412    }
413
414    private static void reportPerformanceWarnings(OptimizedCallTarget target, StructuredGraph graph) {
415        ArrayList<ValueNode> warnings = new ArrayList<>();
416        for (MethodCallTargetNode call : graph.getNodes(MethodCallTargetNode.TYPE)) {
417            if (call.targetMethod().getAnnotation(TruffleBoundary.class) == null && call.targetMethod().getAnnotation(TruffleCallBoundary.class) == null) {
418                TracePerformanceWarningsListener.logPerformanceWarning(target, String.format("not inlined %s call to %s (%s)", call.invokeKind(), call.targetMethod(), call), null);
419                warnings.add(call);
420            }
421        }
422
423        for (CheckCastNode cast : graph.getNodes().filter(CheckCastNode.class)) {
424            if (cast.type().findLeafConcreteSubtype() == null) {
425                TracePerformanceWarningsListener.logPerformanceWarning(target, String.format("non-leaf type checkcast: %s (%s)", cast.type().getName(), cast), null);
426                warnings.add(cast);
427            }
428        }
429
430        for (InstanceOfNode instanceOf : graph.getNodes().filter(InstanceOfNode.class)) {
431            if (instanceOf.type().findLeafConcreteSubtype() == null) {
432                TracePerformanceWarningsListener.logPerformanceWarning(target, String.format("non-leaf type instanceof: %s (%s)", instanceOf.type().getName(), instanceOf), null);
433                warnings.add(instanceOf);
434            }
435        }
436
437        if (Debug.isEnabled() && !warnings.isEmpty()) {
438            try (Scope s = Debug.scope("TrufflePerformanceWarnings", graph)) {
439                Debug.dump(graph, "performance warnings %s", warnings);
440            } catch (Throwable t) {
441                Debug.handle(t);
442            }
443        }
444    }
445
446    private static void postPartialEvaluation(final StructuredGraph graph) {
447        NeverPartOfCompilationNode.verifyNotFoundIn(graph);
448        for (MaterializeFrameNode materializeNode : graph.getNodes(MaterializeFrameNode.TYPE).snapshot()) {
449            materializeNode.replaceAtUsages(materializeNode.getFrame());
450            graph.removeFixed(materializeNode);
451        }
452        for (VirtualObjectNode virtualObjectNode : graph.getNodes(VirtualObjectNode.TYPE)) {
453            if (virtualObjectNode instanceof VirtualOnlyInstanceNode) {
454                VirtualOnlyInstanceNode virtualOnlyInstanceNode = (VirtualOnlyInstanceNode) virtualObjectNode;
455                virtualOnlyInstanceNode.setAllowMaterialization(true);
456            } else if (virtualObjectNode instanceof VirtualInstanceNode) {
457                VirtualInstanceNode virtualInstanceNode = (VirtualInstanceNode) virtualObjectNode;
458                ResolvedJavaType type = virtualInstanceNode.type();
459                if (type.getAnnotation(CompilerDirectives.ValueType.class) != null) {
460                    virtualInstanceNode.setIdentity(false);
461                }
462            }
463        }
464
465        if (!TruffleCompilerOptions.TruffleInlineAcrossTruffleBoundary.getValue()) {
466            // Do not inline across Truffle boundaries.
467            for (MethodCallTargetNode mct : graph.getNodes(MethodCallTargetNode.TYPE)) {
468                if (mct.targetMethod().getAnnotation(TruffleBoundary.class) != null) {
469                    mct.invoke().setUseForInlining(false);
470                }
471            }
472        }
473    }
474
475    private static TruffleInliningDecision getDecision(TruffleInlining inlining, OptimizedDirectCallNode callNode) {
476        OptimizedCallTarget target = callNode.getCallTarget();
477        TruffleInliningDecision decision = inlining.findByCall(callNode);
478        if (decision == null) {
479            if (TruffleCompilerOptions.TraceTrufflePerformanceWarnings.getValue()) {
480                Map<String, Object> properties = new LinkedHashMap<>();
481                properties.put("callNode", callNode);
482                TracePerformanceWarningsListener.logPerformanceWarning(target, "A direct call within the Truffle AST is not reachable anymore. Call node could not be inlined.", properties);
483            }
484        }
485
486        if (decision != null && decision.getTarget() != decision.getProfile().getCallNode().getCurrentCallTarget()) {
487            if (TruffleCompilerOptions.TraceTrufflePerformanceWarnings.getValue()) {
488                Map<String, Object> properties = new LinkedHashMap<>();
489                properties.put("originalTarget", decision.getTarget());
490                properties.put("callNode", callNode);
491                TracePerformanceWarningsListener.logPerformanceWarning(target, String.format("CallTarget changed during compilation. Call node could not be inlined."), properties);
492            }
493            return null;
494        }
495        return decision;
496    }
497}