1 /*
2 * Copyright (c) 2017, 2018, 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
24
25 package org.graalvm.compiler.loop.test;
26
27 import java.util.ListIterator;
28
29 import org.graalvm.compiler.api.directives.GraalDirectives;
30 import org.graalvm.compiler.core.common.CompilationIdentifier;
31 import org.graalvm.compiler.core.common.GraalOptions;
32 import org.graalvm.compiler.core.test.GraalCompilerTest;
33 import org.graalvm.compiler.debug.DebugContext;
34 import org.graalvm.compiler.graph.iterators.NodeIterable;
35 import org.graalvm.compiler.java.ComputeLoopFrequenciesClosure;
36 import org.graalvm.compiler.loop.DefaultLoopPolicies;
37 import org.graalvm.compiler.loop.LoopEx;
38 import org.graalvm.compiler.loop.LoopFragmentInside;
39 import org.graalvm.compiler.loop.LoopsData;
40 import org.graalvm.compiler.loop.phases.LoopPartialUnrollPhase;
41 import org.graalvm.compiler.nodes.LoopBeginNode;
42 import org.graalvm.compiler.nodes.StructuredGraph;
43 import org.graalvm.compiler.nodes.spi.LoweringTool;
44 import org.graalvm.compiler.options.OptionValues;
45 import org.graalvm.compiler.phases.BasePhase;
46 import org.graalvm.compiler.phases.OptimisticOptimizations;
47 import org.graalvm.compiler.phases.PhaseSuite;
48 import org.graalvm.compiler.phases.common.CanonicalizerPhase;
49 import org.graalvm.compiler.phases.common.ConditionalEliminationPhase;
50 import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase;
51 import org.graalvm.compiler.phases.common.DeoptimizationGroupingPhase;
52 import org.graalvm.compiler.phases.common.FloatingReadPhase;
53 import org.graalvm.compiler.phases.common.FrameStateAssignmentPhase;
54 import org.graalvm.compiler.phases.common.GuardLoweringPhase;
55 import org.graalvm.compiler.phases.common.LoweringPhase;
56 import org.graalvm.compiler.phases.common.RemoveValueProxyPhase;
57 import org.graalvm.compiler.phases.tiers.MidTierContext;
58 import org.graalvm.compiler.phases.tiers.Suites;
59 import org.junit.Ignore;
60 import org.junit.Test;
61
62 import jdk.vm.ci.meta.ResolvedJavaMethod;
63
64 public class LoopPartialUnrollTest extends GraalCompilerTest {
65
66 @Override
67 protected void checkMidTierGraph(StructuredGraph graph) {
68 NodeIterable<LoopBeginNode> loops = graph.getNodes().filter(LoopBeginNode.class);
69 for (LoopBeginNode loop : loops) {
70 if (loop.isMainLoop()) {
71 return;
72 }
73 }
74 fail("expected a main loop");
75 }
76
77 public static long sumWithEqualityLimit(int[] text) {
78 long sum = 0;
79 for (int i = 0; branchProbability(0.99, i != text.length); ++i) {
80 sum += volatileInt;
81 }
82 return sum;
83 }
84
85 @Ignore("equality limits aren't working properly")
86 @Test
87 public void testSumWithEqualityLimit() {
88 for (int i = -1; i < 128; i++) {
89 int[] data = new int[i];
90 test("sumWithEqualityLimit", data);
91 }
92 }
93
94 @Test
95 public void testLoopCarried() {
96 for (int i = -1; i < 64; i++) {
97 test("testLoopCarriedSnippet", i);
98 }
99 }
100
101 @Test
102 public void testLoopCarriedDuplication() {
103 testDuplicateBody("testLoopCarriedReference", "testLoopCarriedSnippet");
104 }
105
106 static volatile int volatileInt = 3;
107
108 public static int testLoopCarriedSnippet(int iterations) {
109 int a = 0;
110 int b = 0;
111 int c = 0;
112
113 for (int i = 0; branchProbability(0.99, i < iterations); i++) {
114 int t1 = volatileInt;
115 int t2 = a + b;
116 c = b;
117 b = a;
118 a = t1 + t2;
119 }
120
121 return c;
122 }
123
124 public static int testLoopCarriedReference(int iterations) {
125 int a = 0;
126 int b = 0;
127 int c = 0;
128
129 for (int i = 0; branchProbability(0.99, i < iterations); i += 2) {
130 int t1 = volatileInt;
131 int t2 = a + b;
132 c = b;
133 b = a;
134 a = t1 + t2;
135 t1 = volatileInt;
136 t2 = a + b;
137 c = b;
138 b = a;
139 a = t1 + t2;
140 }
141
142 return c;
143 }
144
145 @Test
146 public void testLoopCarried2() {
147 for (int i = -1; i < 64; i++) {
148 for (int j = -1; j < 64; j++) {
149 test("testLoopCarried2Snippet", i, j);
150 }
151 }
152 test("testLoopCarried2Snippet", Integer.MAX_VALUE - 32, Integer.MAX_VALUE);
153 test("testLoopCarried2Snippet", Integer.MAX_VALUE - 4, Integer.MAX_VALUE);
154 test("testLoopCarried2Snippet", Integer.MAX_VALUE, 0);
155 test("testLoopCarried2Snippet", Integer.MIN_VALUE, Integer.MIN_VALUE + 32);
156 test("testLoopCarried2Snippet", Integer.MIN_VALUE, Integer.MIN_VALUE + 4);
157 test("testLoopCarried2Snippet", 0, Integer.MIN_VALUE);
158 }
159
160 public static int testLoopCarried2Snippet(int start, int end) {
161 int a = 0;
162 int b = 0;
163 int c = 0;
164
165 for (int i = start; branchProbability(0.99, i < end); i++) {
166 int t1 = volatileInt;
167 int t2 = a + b;
168 c = b;
169 b = a;
170 a = t1 + t2;
171 }
172
173 return c;
174 }
175
176 public static long init = Runtime.getRuntime().totalMemory();
177 private int x;
178 private int z;
179
180 public int[] testComplexSnippet(int d) {
181 x = 3;
182 int y = 5;
183 z = 7;
184 for (int i = 0; i < d; i++) {
185 for (int j = 0; branchProbability(0.99, j < i); j++) {
186 z += x;
187 }
188 y = x ^ z;
189 if ((i & 4) == 0) {
190 z--;
191 } else if ((i & 8) == 0) {
192 Runtime.getRuntime().totalMemory();
193 }
194 }
195 return new int[]{x, y, z};
196 }
197
198 @Test
199 public void testComplex() {
200 for (int i = -1; i < 10; i++) {
201 test("testComplexSnippet", i);
202 }
203 test("testComplexSnippet", 10);
204 test("testComplexSnippet", 100);
205 test("testComplexSnippet", 1000);
206 }
207
208 public static long testSignExtensionSnippet(long arg) {
209 long r = 1;
210 for (int i = 0; branchProbability(0.99, i < arg); i++) {
211 r *= i;
212 }
213 return r;
214 }
215
216 @Test
217 public void testSignExtension() {
218 test("testSignExtensionSnippet", 9L);
219 }
220
221 public static Object objectPhi(int n) {
222 Integer v = Integer.valueOf(200);
223 GraalDirectives.blackhole(v); // Prevents PEA
224 Integer r = 1;
225
226 for (int i = 0; iterationCount(100, i < n); i++) {
227 GraalDirectives.blackhole(r); // Create a phi of two loop invariants
228 r = v;
229 }
230
231 return r;
232 }
233
234 @Test
235 public void testObjectPhi() {
236 OptionValues options = new OptionValues(getInitialOptions(), GraalOptions.LoopPeeling, false);
237 test(options, "objectPhi", 1);
238 }
239
240 @Override
241 protected Suites createSuites(OptionValues opts) {
242 Suites suites = super.createSuites(opts).copy();
243 PhaseSuite<MidTierContext> mid = suites.getMidTier();
244 ListIterator<BasePhase<? super MidTierContext>> iter = mid.findPhase(LoopPartialUnrollPhase.class);
245 BasePhase<? super MidTierContext> partialUnoll = iter.previous();
246 if (iter.previous().getClass() != FrameStateAssignmentPhase.class) {
247 // Ensure LoopPartialUnrollPhase runs immediately after FrameStateAssignment, so it gets
248 // priority over other optimizations in these tests.
249 mid.findPhase(LoopPartialUnrollPhase.class).remove();
250 ListIterator<BasePhase<? super MidTierContext>> fsa = mid.findPhase(FrameStateAssignmentPhase.class);
251 fsa.add(partialUnoll);
252 }
253 return suites;
254 }
255
256 public void testGraph(String reference, String test) {
257 StructuredGraph referenceGraph = buildGraph(reference, false);
258 StructuredGraph testGraph = buildGraph(test, true);
259 assertEquals(referenceGraph, testGraph, false, false);
260 }
261
262 @SuppressWarnings("try")
263 public StructuredGraph buildGraph(String name, boolean partialUnroll) {
264 CompilationIdentifier id = new CompilationIdentifier() {
265 @Override
266 public String toString(Verbosity verbosity) {
267 return name;
268 }
269 };
270 ResolvedJavaMethod method = getResolvedJavaMethod(name);
271 OptionValues options = new OptionValues(getInitialOptions(), DefaultLoopPolicies.Options.UnrollMaxIterations, 2);
272 StructuredGraph graph = parse(builder(method, StructuredGraph.AllowAssumptions.YES, id, options), getEagerGraphBuilderSuite());
273 try (DebugContext.Scope buildScope = graph.getDebug().scope(name, method, graph)) {
274 MidTierContext context = new MidTierContext(getProviders(), getTargetProvider(), OptimisticOptimizations.ALL, null);
275
276 CanonicalizerPhase canonicalizer = new CanonicalizerPhase();
277 canonicalizer.apply(graph, context);
278 new RemoveValueProxyPhase().apply(graph);
279 new LoweringPhase(canonicalizer, LoweringTool.StandardLoweringStage.HIGH_TIER).apply(graph, context);
280 new FloatingReadPhase().apply(graph);
281 new DeadCodeEliminationPhase().apply(graph);
282 new ConditionalEliminationPhase(true).apply(graph, context);
283 ComputeLoopFrequenciesClosure.compute(graph);
284 new GuardLoweringPhase().apply(graph, context);
285 new LoweringPhase(canonicalizer, LoweringTool.StandardLoweringStage.MID_TIER).apply(graph, context);
286 new FrameStateAssignmentPhase().apply(graph);
287 new DeoptimizationGroupingPhase().apply(graph, context);
288 canonicalizer.apply(graph, context);
289 new ConditionalEliminationPhase(true).apply(graph, context);
290 if (partialUnroll) {
291 LoopsData dataCounted = new LoopsData(graph);
292 dataCounted.detectedCountedLoops();
293 for (LoopEx loop : dataCounted.countedLoops()) {
294 LoopFragmentInside newSegment = loop.inside().duplicate();
295 newSegment.insertWithinAfter(loop, null);
296 }
297 canonicalizer.apply(graph, getDefaultMidTierContext());
298 }
299 new DeadCodeEliminationPhase().apply(graph);
300 canonicalizer.apply(graph, context);
301 graph.getDebug().dump(DebugContext.BASIC_LEVEL, graph, "before compare");
302 return graph;
303 } catch (Throwable e) {
304 throw getDebugContext().handle(e);
305 }
306 }
307
308 public void testDuplicateBody(String reference, String test) {
309
310 StructuredGraph referenceGraph = buildGraph(reference, false);
311 StructuredGraph testGraph = buildGraph(test, true);
312 CanonicalizerPhase canonicalizer = new CanonicalizerPhase();
313 canonicalizer.apply(testGraph, getDefaultMidTierContext());
314 canonicalizer.apply(referenceGraph, getDefaultMidTierContext());
315 assertEquals(referenceGraph, testGraph);
316 }
317 }