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 */
23 package org.graalvm.compiler.core.test.inlining;
24
25 import static org.graalvm.compiler.core.common.CompilationIdentifier.INVALID_COMPILATION_ID;
26 import static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Optional;
27
28 import java.lang.reflect.Field;
29 import java.util.ArrayList;
30 import java.util.List;
31
32 import org.junit.Test;
33
34 import org.graalvm.compiler.core.test.GraalCompilerTest;
35 import org.graalvm.compiler.debug.Debug;
36 import org.graalvm.compiler.debug.Debug.Scope;
37 import org.graalvm.compiler.debug.DebugDumpScope;
38 import org.graalvm.compiler.graph.Node;
39 import org.graalvm.compiler.nodes.InvokeNode;
40 import org.graalvm.compiler.nodes.StructuredGraph;
41 import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;
42 import org.graalvm.compiler.phases.OptimisticOptimizations;
43 import org.graalvm.compiler.phases.PhaseSuite;
44 import org.graalvm.compiler.phases.common.CanonicalizerPhase;
45 import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase;
46 import org.graalvm.compiler.phases.common.inlining.InliningUtil;
47 import org.graalvm.compiler.phases.schedule.SchedulePhase;
48 import org.graalvm.compiler.phases.tiers.HighTierContext;
49 import org.graalvm.compiler.virtual.phases.ea.EarlyReadEliminationPhase;
50 import org.graalvm.compiler.virtual.phases.ea.PartialEscapePhase;
51
52 import jdk.vm.ci.meta.ResolvedJavaMethod;
53 import sun.misc.Unsafe;
54
55 public 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 }