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 */
23package org.graalvm.compiler.core.test;
24
25import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
26import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
27
28import org.junit.Test;
29
30import org.graalvm.compiler.api.directives.GraalDirectives;
31import org.graalvm.compiler.graph.NodeClass;
32import org.graalvm.compiler.loop.InductionVariable;
33import org.graalvm.compiler.loop.LoopsData;
34import org.graalvm.compiler.nodeinfo.NodeInfo;
35import org.graalvm.compiler.nodes.StructuredGraph;
36import org.graalvm.compiler.nodes.ValueNode;
37import org.graalvm.compiler.nodes.calc.FloatingNode;
38import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins;
39import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderContext;
40import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugin;
41import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins.Registration;
42import org.graalvm.compiler.nodes.spi.LIRLowerable;
43import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
44
45import jdk.vm.ci.meta.JavaKind;
46import jdk.vm.ci.meta.ResolvedJavaMethod;
47
48public 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}
313