1 /*
2 * Copyright (c) 2015, 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.core.test;
26
27 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
28 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
29
30 import org.graalvm.compiler.api.directives.GraalDirectives;
31 import org.graalvm.compiler.graph.NodeClass;
32 import org.graalvm.compiler.loop.InductionVariable;
33 import org.graalvm.compiler.loop.LoopsData;
34 import org.graalvm.compiler.nodeinfo.NodeInfo;
35 import org.graalvm.compiler.nodes.ConstantNode;
36 import org.graalvm.compiler.nodes.NodeView;
37 import org.graalvm.compiler.nodes.StructuredGraph;
38 import org.graalvm.compiler.nodes.ValueNode;
39 import org.graalvm.compiler.nodes.calc.FloatingNode;
40 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderContext;
41 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugin;
42 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins;
43 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins.Registration;
44 import org.graalvm.compiler.nodes.spi.LIRLowerable;
45 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
46 import org.graalvm.compiler.phases.OptimisticOptimizations;
47 import org.graalvm.compiler.phases.tiers.HighTierContext;
48 import org.junit.Test;
49
50 import jdk.vm.ci.meta.JavaKind;
51 import jdk.vm.ci.meta.ResolvedJavaMethod;
52
53 public class CountedLoopTest extends GraalCompilerTest {
54
55 @FunctionalInterface
56 private interface IVProperty {
57 ValueNode get(InductionVariable iv);
58 }
59
60 @FunctionalInterface
61 private interface StaticIVProperty {
62 long get(InductionVariable iv);
63 }
64
65 @FunctionalInterface
66 private interface IVPredicate {
67 boolean test(InductionVariable iv);
68 }
69
70 /**
71 * Get a property of an induction variable.
72 */
73 private static int get(@SuppressWarnings("unused") IVProperty property, @SuppressWarnings("unused") StaticIVProperty staticProperty, @SuppressWarnings("unused") IVPredicate constantCheck,
74 int iv) {
75 return iv;
76 }
77
78 private static int get(@SuppressWarnings("unused") IVProperty property, int iv) {
79 return iv;
80 }
81
82 private static long get(@SuppressWarnings("unused") IVProperty property, @SuppressWarnings("unused") StaticIVProperty staticProperty, @SuppressWarnings("unused") IVPredicate constantCheck,
83 long iv) {
84 return iv;
85 }
86
87 private static long get(@SuppressWarnings("unused") IVProperty property, long iv) {
88 return iv;
89 }
90
91 private static class Result {
92 public long extremum;
93 public long exitValue;
94
95 @Override
96 public int hashCode() {
97 final int prime = 31;
98 int result = 1;
99 result = prime * result + Long.hashCode(exitValue);
100 result = prime * result + Long.hashCode(extremum);
101 return result;
102 }
103
104 @Override
105 public boolean equals(Object obj) {
106 if (!(obj instanceof Result)) {
107 return false;
108 }
109 Result other = (Result) obj;
110 return extremum == other.extremum && exitValue == other.exitValue;
111 }
112
113 @Override
114 public String toString() {
115 return String.format("extremum = %d, exitValue = %d", extremum, exitValue);
116 }
117 }
118
119 public static Result incrementSnippet(int start, int limit, int step) {
120 int i;
121 int inc = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
122 Result ret = new Result();
123 for (i = start; i < limit; i += inc) {
124 GraalDirectives.controlFlowAnchor();
125 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i);
126 }
127 ret.exitValue = get(InductionVariable::exitValueNode, i);
128 return ret;
129 }
130
131 @Test
132 public void increment1() {
133 testCounted("incrementSnippet", 0, 256, 1);
134 }
135
136 @Test
137 public void increment2() {
138 testCounted("incrementSnippet", 0, 256, 2);
139 }
140
141 @Test
142 public void increment3() {
143 testCounted("incrementSnippet", 0, 256, 3);
144 }
145
146 @Test
147 public void increment4() {
148 testCounted("incrementSnippet", -10, 1, Integer.MAX_VALUE);
149 }
150
151 @Test
152 public void increment5() {
153 testCounted("incrementSnippet", 256, 256, 1);
154 }
155
156 @Test
157 public void increment6() {
158 testCounted("incrementSnippet", 257, 256, 1);
159 }
160
161 @Test
162 public void increment7() {
163 testCounted("incrementSnippet", -10, Integer.MAX_VALUE, 1);
164 }
165
166 @Test
167 public void increment8() {
168 testCounted("incrementSnippet", -10, Integer.MAX_VALUE - 1, 2);
169 }
170
171 public static Result incrementEqSnippet(int start, int limit, int step) {
172 int i;
173 int inc = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
174 Result ret = new Result();
175 for (i = start; i <= limit; i += inc) {
176 GraalDirectives.controlFlowAnchor();
177 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i);
178 }
179 ret.exitValue = get(InductionVariable::exitValueNode, i);
180 return ret;
181 }
182
183 @Test
184 public void incrementEq1() {
185 testCounted("incrementEqSnippet", 0, 256, 1);
186 }
187
188 @Test
189 public void incrementEq2() {
190 testCounted("incrementEqSnippet", 0, 256, 2);
191 }
192
193 @Test
194 public void incrementEq3() {
195 testCounted("incrementEqSnippet", 0, 256, 3);
196 }
197
198 @Test
199 public void incrementEq4() {
200 testCounted("incrementEqSnippet", -10, 0, Integer.MAX_VALUE);
201 }
202
203 @Test
204 public void incrementEq5() {
205 testCounted("incrementEqSnippet", 256, 256, 1);
206 }
207
208 @Test
209 public void incrementEq6() {
210 testCounted("incrementEqSnippet", 257, 256, 1);
211 }
212
213 @Test
214 public void incrementEq7() {
215 testCounted("incrementEqSnippet", -10, Integer.MAX_VALUE - 1, 1);
216 }
217
218 @Test
219 public void incrementEq8() {
220 testCounted("incrementEqSnippet", -10, Integer.MAX_VALUE - 2, 2);
221 }
222
223 public static Result decrementSnippet(int start, int limit, int step) {
224 int i;
225 int dec = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
226 Result ret = new Result();
227 for (i = start; i > limit; i -= dec) {
228 GraalDirectives.controlFlowAnchor();
229 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i);
230 }
231 ret.exitValue = get(InductionVariable::exitValueNode, i);
232 return ret;
233 }
234
235 @Test
236 public void decrement1() {
237 testCounted("decrementSnippet", 256, 0, 1);
238 }
239
240 @Test
241 public void decrement2() {
242 testCounted("decrementSnippet", 256, 0, 2);
243 }
244
245 @Test
246 public void decrement3() {
247 testCounted("decrementSnippet", 256, 0, 3);
248 }
249
250 @Test
251 public void decrement4() {
252 testCounted("decrementSnippet", Integer.MAX_VALUE, -10, 1);
253 }
254
255 @Test
256 public void decrement5() {
257 testCounted("decrementSnippet", Integer.MAX_VALUE, -10, 2);
258 }
259
260 public static Result decrementEqSnippet(int start, int limit, int step) {
261 int i;
262 int dec = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
263 Result ret = new Result();
264 for (i = start; i >= limit; i -= dec) {
265 GraalDirectives.controlFlowAnchor();
266 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i);
267 }
268 ret.exitValue = get(InductionVariable::exitValueNode, i);
269 return ret;
270 }
271
272 @Test
273 public void decrementEq1() {
274 testCounted("decrementEqSnippet", 256, 0, 1);
275 }
276
277 @Test
278 public void decrementEq2() {
279 testCounted("decrementEqSnippet", 256, 0, 2);
280 }
281
282 @Test
283 public void decrementEq3() {
284 testCounted("decrementEqSnippet", 256, 0, 3);
285 }
286
287 @Test
288 public void decrementEq4() {
289 testCounted("decrementEqSnippet", -10, 0, Integer.MAX_VALUE);
290 }
291
292 @Test
293 public void decrementEq5() {
294 testCounted("decrementEqSnippet", Integer.MAX_VALUE, -10, 1);
295 }
296
297 @Test
298 public void decrementEq6() {
299 testCounted("decrementEqSnippet", Integer.MAX_VALUE, -10, 2);
300 }
301
302 public static Result twoVariablesSnippet() {
303 Result ret = new Result();
304 int j = 0;
305 for (int i = 0; i < 1024; i++) {
306 j += 5;
307 GraalDirectives.controlFlowAnchor();
308 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, j);
309 }
310 ret.exitValue = get(InductionVariable::exitValueNode, j);
311 return ret;
312 }
313
314 @Test
315 public void testTwoVariables() {
316 testCounted("twoVariablesSnippet");
317 }
318
319 public static Result incrementNeqSnippet(int limit) {
320 int i;
321 int posLimit = ((limit - 1) & 0xFFFF) + 1; // make sure limit is always strictly positive
322 Result ret = new Result();
323 for (i = 0; i != posLimit; i++) {
324 GraalDirectives.controlFlowAnchor();
325 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i);
326 }
327 ret.exitValue = get(InductionVariable::exitValueNode, i);
328 return ret;
329 }
330
331 @Test
332 public void decrementNeq() {
333 testCounted("decrementNeqSnippet", 256);
334 }
335
336 public static Result decrementNeqSnippet(int limit) {
337 int i;
338 int posLimit = ((limit - 1) & 0xFFFF) + 1; // make sure limit is always strictly positive
339 Result ret = new Result();
340 for (i = posLimit; i != 0; i--) {
341 GraalDirectives.controlFlowAnchor();
342 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i);
343 }
344 ret.exitValue = get(InductionVariable::exitValueNode, i);
345 return ret;
346 }
347
348 @Test
349 public void incrementNeq() {
350 testCounted("incrementNeqSnippet", 256);
351 }
352
353 public static Result incrementLongSnippet(long start, long limit, long step) {
354 long i;
355 long inc = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
356 Result ret = new Result();
357 for (i = start; i < limit; i += inc) {
358 GraalDirectives.controlFlowAnchor();
359 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i);
360 }
361 ret.exitValue = get(InductionVariable::exitValueNode, i);
362 return ret;
363 }
364
365 @Test
366 public void incrementLong1() {
367 testCounted("incrementLongSnippet", 0L, 256L, 1L);
368 }
369
370 @Test
371 public void incrementLong2() {
372 testCounted("incrementLongSnippet", 0L, 256L, 2L);
373 }
374
375 @Test
376 public void incrementLong3() {
377 testCounted("incrementLongSnippet", 0L, 256L, 3L);
378 }
379
380 @Test
381 public void incrementLong4() {
382 testCounted("incrementLongSnippet", -10L, 1L, Long.MAX_VALUE);
383 }
384
385 @Test
386 public void incrementLong5() {
387 testCounted("incrementLongSnippet", 256L, 256L, 1L);
388 }
389
390 @Test
391 public void incrementLong6() {
392 testCounted("incrementLongSnippet", 257L, 256L, 1L);
393 }
394
395 @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)
396 private static class IVPropertyNode extends FloatingNode implements LIRLowerable {
397
398 public static final NodeClass<IVPropertyNode> TYPE = NodeClass.create(IVPropertyNode.class);
399
400 private final IVProperty property;
401 private final StaticIVProperty staticProperty;
402 private final IVPredicate staticCheck;
403 @Input private ValueNode iv;
404
405 protected IVPropertyNode(IVProperty property, StaticIVProperty staticProperty, IVPredicate staticCheck, ValueNode iv) {
406 super(TYPE, iv.stamp(NodeView.DEFAULT).unrestricted());
407 this.property = property;
408 this.staticProperty = staticProperty;
409 this.staticCheck = staticCheck;
410 this.iv = iv;
411 }
412
413 public void rewrite(LoopsData loops) {
414 InductionVariable inductionVariable = loops.getInductionVariable(iv);
415 assert inductionVariable != null;
416 assertTrue(inductionVariable.getLoop().isCounted(), "must be counted");
417 ValueNode node = null;
418 if (staticCheck != null) {
419 assert staticProperty != null;
420 if (staticCheck.test(inductionVariable)) {
421 node = ConstantNode.forLong(staticProperty.get(inductionVariable), graph());
422 }
423 }
424 if (node == null) {
425 node = property.get(inductionVariable);
426 }
427 replaceAtUsagesAndDelete(node);
428 }
429
430 @Override
431 public void generate(NodeLIRBuilderTool gen) {
432 gen.setResult(this, gen.operand(iv));
433 }
434 }
435
436 @Override
437 protected void registerInvocationPlugins(InvocationPlugins invocationPlugins) {
438 Registration r = new Registration(invocationPlugins, CountedLoopTest.class);
439 registerPlugins(r, JavaKind.Int);
440 registerPlugins(r, JavaKind.Long);
441 super.registerInvocationPlugins(invocationPlugins);
442 }
443
444 private void registerPlugins(Registration r, JavaKind ivKind) {
445 r.register2("get", IVProperty.class, ivKind.toJavaClass(), new InvocationPlugin() {
446 @Override
447 public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver, ValueNode arg1, ValueNode arg2) {
448 IVProperty property = null;
449 if (arg1.isConstant()) {
450 property = getSnippetReflection().asObject(IVProperty.class, arg1.asJavaConstant());
451 }
452 if (property != null) {
453 b.addPush(ivKind, new IVPropertyNode(property, null, null, arg2));
454 return true;
455 } else {
456 return false;
457 }
458 }
459 });
460 r.register4("get", IVProperty.class, StaticIVProperty.class, IVPredicate.class, ivKind.toJavaClass(), new InvocationPlugin() {
461 @Override
462 public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver, ValueNode arg1, ValueNode arg2, ValueNode arg3, ValueNode arg4) {
463 IVProperty property = null;
464 StaticIVProperty staticProperty = null;
465 IVPredicate staticCheck = null;
466 if (arg1.isConstant()) {
467 property = getSnippetReflection().asObject(IVProperty.class, arg1.asJavaConstant());
468 }
469 if (arg2.isConstant()) {
470 staticProperty = getSnippetReflection().asObject(StaticIVProperty.class, arg2.asJavaConstant());
471 }
472 if (arg3.isConstant()) {
473 staticCheck = getSnippetReflection().asObject(IVPredicate.class, arg3.asJavaConstant());
474 }
475 if (property != null && staticProperty != null && staticCheck != null) {
476 b.addPush(ivKind, new IVPropertyNode(property, staticProperty, staticCheck, arg4));
477 return true;
478 } else {
479 return false;
480 }
481 }
482 });
483 }
484
485 @Override
486 protected void checkHighTierGraph(StructuredGraph graph) {
487 LoopsData loops = new LoopsData(graph);
488 loops.detectedCountedLoops();
489 for (IVPropertyNode node : graph.getNodes().filter(IVPropertyNode.class)) {
490 node.rewrite(loops);
491 }
492 assert graph.getNodes().filter(IVPropertyNode.class).isEmpty();
493 }
494
495 @Override
496 protected HighTierContext getDefaultHighTierContext() {
497 // Don't convert unreached paths into Guard
498 return new HighTierContext(getProviders(), getDefaultGraphBuilderSuite(), OptimisticOptimizations.NONE);
499 }
500
501 private Object[] argsToBind;
502
503 @Override
504 protected Object[] getArgumentToBind() {
505 return argsToBind;
506 }
507
508 public void testCounted(String snippetName, Object... args) {
509 test(snippetName, args);
510 argsToBind = args;
511 test(snippetName, args);
512 argsToBind = null;
513 }
514 }