1 /*
2 * Copyright (c) 2015, 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;
24
25 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
26 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
27
28 import org.junit.Test;
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.StructuredGraph;
36 import org.graalvm.compiler.nodes.ValueNode;
37 import org.graalvm.compiler.nodes.calc.FloatingNode;
38 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins;
39 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderContext;
40 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugin;
41 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins.Registration;
42 import org.graalvm.compiler.nodes.spi.LIRLowerable;
43 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
44
45 import jdk.vm.ci.meta.JavaKind;
46 import jdk.vm.ci.meta.ResolvedJavaMethod;
47
48 public class CountedLoopTest extends GraalCompilerTest {
49
50 @FunctionalInterface
51 private interface IVProperty {
52 ValueNode get(InductionVariable iv);
53 }
54
55 /**
56 * Get a property of an induction variable.
57 *
58 * @param property
59 */
60 private static int get(IVProperty property, int iv) {
61 return iv;
62 }
63
64 private static class Result {
65 public int extremum;
66 public int exitValue;
67
68 @Override
69 public int hashCode() {
70 final int prime = 31;
71 int result = 1;
72 result = prime * result + exitValue;
73 result = prime * result + extremum;
74 return result;
75 }
76
77 @Override
78 public boolean equals(Object obj) {
79 if (!(obj instanceof Result)) {
80 return false;
81 }
82 Result other = (Result) obj;
83 return extremum == other.extremum && exitValue == other.exitValue;
84 }
85
86 @Override
87 public String toString() {
88 return String.format("extremum = %d, exitValue = %d", extremum, exitValue);
89 }
90 }
91
92 public static Result incrementSnippet(int start, int limit, int step) {
93 int i;
94 int inc = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
95 Result ret = new Result();
96 for (i = start; i < limit; i += inc) {
97 GraalDirectives.controlFlowAnchor();
98 ret.extremum = get(InductionVariable::extremumNode, i);
99 }
100 ret.exitValue = get(InductionVariable::exitValueNode, i);
101 return ret;
102 }
103
104 @Test
105 public void increment1() {
106 test("incrementSnippet", 0, 256, 1);
107 }
108
109 @Test
110 public void increment2() {
111 test("incrementSnippet", 0, 256, 2);
112 }
113
114 @Test
115 public void increment3() {
116 test("incrementSnippet", 0, 256, 3);
117 }
118
119 public static Result incrementEqSnippet(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, i);
126 }
127 ret.exitValue = get(InductionVariable::exitValueNode, i);
128 return ret;
129 }
130
131 @Test
132 public void incrementEq1() {
133 test("incrementEqSnippet", 0, 256, 1);
134 }
135
136 @Test
137 public void incrementEq2() {
138 test("incrementEqSnippet", 0, 256, 2);
139 }
140
141 @Test
142 public void incrementEq3() {
143 test("incrementEqSnippet", 0, 256, 3);
144 }
145
146 public static Result decrementSnippet(int start, int limit, int step) {
147 int i;
148 int dec = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
149 Result ret = new Result();
150 for (i = start; i > limit; i -= dec) {
151 GraalDirectives.controlFlowAnchor();
152 ret.extremum = get(InductionVariable::extremumNode, i);
153 }
154 ret.exitValue = get(InductionVariable::exitValueNode, i);
155 return ret;
156 }
157
158 @Test
159 public void decrement1() {
160 test("decrementSnippet", 256, 0, 1);
161 }
162
163 @Test
164 public void decrement2() {
165 test("decrementSnippet", 256, 0, 2);
166 }
167
168 @Test
169 public void decrement3() {
170 test("decrementSnippet", 256, 0, 3);
171 }
172
173 public static Result decrementEqSnippet(int start, int limit, int step) {
174 int i;
175 int dec = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
176 Result ret = new Result();
177 for (i = start; i >= limit; i -= dec) {
178 GraalDirectives.controlFlowAnchor();
179 ret.extremum = get(InductionVariable::extremumNode, i);
180 }
181 ret.exitValue = get(InductionVariable::exitValueNode, i);
182 return ret;
183 }
184
185 @Test
186 public void decrementEq1() {
187 test("decrementEqSnippet", 256, 0, 1);
188 }
189
190 @Test
191 public void decrementEq2() {
192 test("decrementEqSnippet", 256, 0, 2);
193 }
194
195 @Test
196 public void decrementEq3() {
197 test("decrementEqSnippet", 256, 0, 3);
198 }
199
200 public static Result twoVariablesSnippet() {
201 Result ret = new Result();
202 int j = 0;
203 for (int i = 0; i < 1024; i++) {
204 j += 5;
205 GraalDirectives.controlFlowAnchor();
206 ret.extremum = get(InductionVariable::extremumNode, j);
207 }
208 ret.exitValue = get(InductionVariable::exitValueNode, j);
209 return ret;
210 }
211
212 @Test
213 public void testTwoVariables() {
214 test("twoVariablesSnippet");
215 }
216
217 @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)
218 private static class IVPropertyNode extends FloatingNode implements LIRLowerable {
219
220 public static final NodeClass<IVPropertyNode> TYPE = NodeClass.create(IVPropertyNode.class);
221
222 private final IVProperty property;
223 @Input private ValueNode iv;
224
225 protected IVPropertyNode(IVProperty property, ValueNode iv) {
226 super(TYPE, iv.stamp().unrestricted());
227 this.property = property;
228 this.iv = iv;
229 }
230
231 public void rewrite(LoopsData loops) {
232 InductionVariable inductionVariable = loops.getInductionVariable(iv);
233 assert inductionVariable != null;
234 ValueNode node = property.get(inductionVariable);
235 replaceAtUsagesAndDelete(node);
236 }
237
238 @Override
239 public void generate(NodeLIRBuilderTool gen) {
240 gen.setResult(this, gen.operand(iv));
241 }
242 }
243
244 @Override
245 protected Plugins getDefaultGraphBuilderPlugins() {
246 Plugins plugins = super.getDefaultGraphBuilderPlugins();
247 Registration r = new Registration(plugins.getInvocationPlugins(), CountedLoopTest.class);
248
249 r.register2("get", IVProperty.class, int.class, new InvocationPlugin() {
250 @Override
251 public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver, ValueNode arg1, ValueNode arg2) {
252 IVProperty property = null;
253 if (arg1.isConstant()) {
254 property = getSnippetReflection().asObject(IVProperty.class, arg1.asJavaConstant());
255 }
256 if (property != null) {
257 b.addPush(JavaKind.Int, new IVPropertyNode(property, arg2));
258 return true;
259 } else {
260 return false;
261 }
262 }
263 });
264
265 return plugins;
266 }
267
268 @Override
269 protected boolean checkMidTierGraph(StructuredGraph graph) {
270 LoopsData loops = new LoopsData(graph);
271 loops.detectedCountedLoops();
272 for (IVPropertyNode node : graph.getNodes().filter(IVPropertyNode.class)) {
273 node.rewrite(loops);
274 }
275 assert graph.getNodes().filter(IVPropertyNode.class).isEmpty();
276 return true;
277 }
278
279 public static Result incrementNeqSnippet(int limit) {
280 int i;
281 int posLimit = ((limit - 1) & 0xFFFF) + 1; // make sure limit is always strictly positive
282 Result ret = new Result();
283 for (i = 0; i != posLimit; i++) {
284 GraalDirectives.controlFlowAnchor();
285 ret.extremum = get(InductionVariable::extremumNode, i);
286 }
287 ret.exitValue = get(InductionVariable::exitValueNode, i);
288 return ret;
289 }
290
291 @Test
292 public void decrementNeq() {
293 test("decrementNeqSnippet", 256);
294 }
295
296 public static Result decrementNeqSnippet(int limit) {
297 int i;
298 int posLimit = ((limit - 1) & 0xFFFF) + 1; // make sure limit is always strictly positive
299 Result ret = new Result();
300 for (i = posLimit; i != 0; i--) {
301 GraalDirectives.controlFlowAnchor();
302 ret.extremum = get(InductionVariable::extremumNode, i);
303 }
304 ret.exitValue = get(InductionVariable::exitValueNode, i);
305 return ret;
306 }
307
308 @Test
309 public void incrementNeq() {
310 test("incrementNeqSnippet", 256);
311 }
312 }