1/*
2 * Copyright (c) 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.core.test.inlining;
24
25import static org.graalvm.compiler.core.common.CompilationIdentifier.INVALID_COMPILATION_ID;
26import static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Optional;
27
28import java.lang.reflect.Field;
29import java.util.ArrayList;
30import java.util.List;
31
32import org.junit.Test;
33
34import org.graalvm.compiler.core.test.GraalCompilerTest;
35import org.graalvm.compiler.debug.Debug;
36import org.graalvm.compiler.debug.Debug.Scope;
37import org.graalvm.compiler.debug.DebugDumpScope;
38import org.graalvm.compiler.graph.Node;
39import org.graalvm.compiler.nodes.InvokeNode;
40import org.graalvm.compiler.nodes.StructuredGraph;
41import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;
42import org.graalvm.compiler.phases.OptimisticOptimizations;
43import org.graalvm.compiler.phases.PhaseSuite;
44import org.graalvm.compiler.phases.common.CanonicalizerPhase;
45import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase;
46import org.graalvm.compiler.phases.common.inlining.InliningUtil;
47import org.graalvm.compiler.phases.schedule.SchedulePhase;
48import org.graalvm.compiler.phases.tiers.HighTierContext;
49import org.graalvm.compiler.virtual.phases.ea.EarlyReadEliminationPhase;
50import org.graalvm.compiler.virtual.phases.ea.PartialEscapePhase;
51
52import jdk.vm.ci.meta.ResolvedJavaMethod;
53import sun.misc.Unsafe;
54
55public class RecursiveInliningTest extends GraalCompilerTest {
56
57    public static int SideEffectI;
58    public static int[] Memory = new int[]{1, 2};
59
60    public static final Unsafe UNSAFE;
61    static {
62        try {
63            Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
64            theUnsafe.setAccessible(true);
65            UNSAFE = (Unsafe) theUnsafe.get(Unsafe.class);
66        } catch (Exception e) {
67            throw new RuntimeException("Exception while trying to get Unsafe", e);
68        }
69    }
70
71    public static void recursiveLoopMethodUnsafeLoad(int a) {
72        if (UNSAFE.getInt(Memory, (long) Unsafe.ARRAY_LONG_BASE_OFFSET) == 0) {
73            return;
74        }
75        for (int i = 0; i < a; i++) {
76            recursiveLoopMethodUnsafeLoad(i);
77        }
78    }
79
80    public static void recursiveLoopMethodFieldLoad(int a) {
81        if (SideEffectI == 0) {
82            return;
83        }
84        for (int i = 0; i < a; i++) {
85            recursiveLoopMethodFieldLoad(i);
86        }
87    }
88
89    public static void recursiveLoopMethod(int a) {
90        if (a == 0) {
91            return;
92        }
93        for (int i = 0; i < a; i++) {
94            recursiveLoopMethod(i);
95        }
96    }
97
98    public static final boolean LOG = false;
99
100    public static int IterationsStart = 1;
101    public static int IterationsEnd = 128;
102
103    @Test(timeout = 120_000)
104    public void inlineDirectRecursiveLoopCallUnsafeLoad() {
105        testAndTime("recursiveLoopMethodUnsafeLoad");
106    }
107
108    @Test(timeout = 120_000)
109    public void inlineDirectRecursiveLoopCallFieldLoad() {
110        testAndTime("recursiveLoopMethodFieldLoad");
111    }
112
113    @Test(timeout = 120_000)
114    public void inlineDirectRecursiveLoopCallNoReads() {
115        testAndTime("recursiveLoopMethod");
116    }
117
118    private void testAndTime(String snippet) {
119        for (int i = IterationsStart; i < IterationsEnd; i++) {
120            StructuredGraph graph = getGraph(snippet, i);
121            long elapsed = runAndTimeEarlyReadEliminationPhase(graph);
122            if (LOG) {
123                System.out.printf("Needed %dms to run early read elimination on a graph with %d recursive inlined calls of method %s\n", elapsed, i, graph.method());
124            }
125        }
126        for (int i = IterationsStart; i < IterationsEnd; i++) {
127            StructuredGraph graph = getGraph(snippet, i);
128            long elapsed = runAndTimePartialEscapeAnalysis(graph);
129            if (LOG) {
130                System.out.printf("Needed %dms to run early partial escape analysis on a graph with %d recursive inlined calls of method %s\n", elapsed, i, graph.method());
131            }
132        }
133    }
134
135    private long runAndTimePartialEscapeAnalysis(StructuredGraph g) {
136        PartialEscapePhase p = new PartialEscapePhase(true, new CanonicalizerPhase());
137        HighTierContext context = getDefaultHighTierContext();
138        long start = System.currentTimeMillis();
139        p.apply(g, context);
140        long end = System.currentTimeMillis();
141        Debug.dump(Debug.BASIC_LOG_LEVEL, g, "After PEA");
142        return end - start;
143    }
144
145    private long runAndTimeEarlyReadEliminationPhase(StructuredGraph g) {
146        EarlyReadEliminationPhase er = new EarlyReadEliminationPhase(new CanonicalizerPhase());
147        HighTierContext context = getDefaultHighTierContext();
148        long start = System.currentTimeMillis();
149        er.apply(g, context);
150        long end = System.currentTimeMillis();
151        Debug.dump(Debug.BASIC_LOG_LEVEL, g, "After Early Read Elimination");
152        return end - start;
153    }
154
155    @SuppressWarnings("try")
156    private StructuredGraph getGraph(final String snippet, int nrOfInlinings) {
157        try (Scope s = Debug.scope("RecursiveInliningTest", new DebugDumpScope(snippet, true))) {
158            ResolvedJavaMethod callerMethod = getResolvedJavaMethod(snippet);
159            StructuredGraph callerGraph = parseEager(callerMethod, AllowAssumptions.YES);
160            PhaseSuite<HighTierContext> graphBuilderSuite = getDefaultGraphBuilderSuite();
161            HighTierContext context = new HighTierContext(getProviders(), graphBuilderSuite, OptimisticOptimizations.ALL);
162            CanonicalizerPhase canonicalizer = new CanonicalizerPhase();
163
164            for (int i = 0; i < nrOfInlinings; i++) {
165                InvokeNode next = getNextInvoke(callerGraph);
166                ResolvedJavaMethod calleeMethod = next.callTarget().targetMethod();
167                StructuredGraph calleeGraph = getInlineeGraph(next, callerGraph, context, canonicalizer);
168                List<Node> canonicalizeNodes = new ArrayList<>();
169                InliningUtil.inline(next, calleeGraph, false, canonicalizeNodes, calleeMethod);
170                canonicalizer.applyIncremental(callerGraph, context, canonicalizeNodes);
171                Debug.dump(Debug.BASIC_LOG_LEVEL, callerGraph, "After inlining %s into %s iteration %d", calleeMethod, callerMethod, i);
172            }
173            new SchedulePhase().apply(callerGraph);
174            return callerGraph;
175        } catch (Throwable e) {
176            throw Debug.handle(e);
177        }
178    }
179
180    private static StructuredGraph getInlineeGraph(InvokeNode invoke, StructuredGraph caller, HighTierContext context, CanonicalizerPhase canonicalizer) {
181        StructuredGraph result = InliningUtil.getIntrinsicGraph(context.getReplacements(), invoke.callTarget().targetMethod(), invoke.bci());
182        if (result != null) {
183            return result;
184        }
185        return parseBytecodes(invoke.callTarget().targetMethod(), context, canonicalizer, caller);
186    }
187
188    @SuppressWarnings("try")
189    private static StructuredGraph parseBytecodes(ResolvedJavaMethod method, HighTierContext context, CanonicalizerPhase canonicalizer, StructuredGraph caller) {
190        StructuredGraph newGraph = new StructuredGraph(method, AllowAssumptions.from(caller.getAssumptions() != null), INVALID_COMPILATION_ID);
191        if (!caller.isUnsafeAccessTrackingEnabled()) {
192            newGraph.disableUnsafeAccessTracking();
193        }
194        if (context.getGraphBuilderSuite() != null) {
195            context.getGraphBuilderSuite().apply(newGraph, context);
196        }
197        assert newGraph.start().next() != null : "graph needs to be populated by the GraphBuilderSuite " + method + ", " + method.canBeInlined();
198        new DeadCodeEliminationPhase(Optional).apply(newGraph);
199        canonicalizer.apply(newGraph, context);
200        return newGraph;
201    }
202
203    private static InvokeNode getNextInvoke(StructuredGraph graph) {
204        return graph.getNodes().filter(InvokeNode.class).first();
205    }
206}
207