001/*
002 * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.compiler.test;
024
025import jdk.internal.jvmci.meta.*;
026
027import org.junit.*;
028
029import com.oracle.graal.api.directives.*;
030import com.oracle.graal.graph.*;
031import com.oracle.graal.graphbuilderconf.GraphBuilderConfiguration.Plugins;
032import com.oracle.graal.graphbuilderconf.*;
033import com.oracle.graal.graphbuilderconf.InvocationPlugins.Registration;
034import com.oracle.graal.loop.*;
035import com.oracle.graal.nodeinfo.*;
036import com.oracle.graal.nodes.*;
037import com.oracle.graal.nodes.calc.*;
038import com.oracle.graal.nodes.spi.*;
039
040public class CountedLoopTest extends GraalCompilerTest {
041
042    @FunctionalInterface
043    private interface IVProperty {
044        ValueNode get(InductionVariable iv);
045    }
046
047    /**
048     * Get a property of an induction variable.
049     *
050     * @param property
051     */
052    private static int get(IVProperty property, int iv) {
053        return iv;
054    }
055
056    private static class Result {
057        public int extremum;
058        public int exitValue;
059
060        @Override
061        public int hashCode() {
062            final int prime = 31;
063            int result = 1;
064            result = prime * result + exitValue;
065            result = prime * result + extremum;
066            return result;
067        }
068
069        @Override
070        public boolean equals(Object obj) {
071            if (!(obj instanceof Result)) {
072                return false;
073            }
074            Result other = (Result) obj;
075            return extremum == other.extremum && exitValue == other.exitValue;
076        }
077
078        @Override
079        public String toString() {
080            return String.format("extremum = %d, exitValue = %d", extremum, exitValue);
081        }
082    }
083
084    public static Result incrementSnippet(int start, int limit, int step) {
085        int i;
086        int inc = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
087        Result ret = new Result();
088        for (i = start; i < limit; i += inc) {
089            GraalDirectives.controlFlowAnchor();
090            ret.extremum = get(InductionVariable::extremumNode, i);
091        }
092        ret.exitValue = get(InductionVariable::exitValueNode, i);
093        return ret;
094    }
095
096    @Test
097    public void increment1() {
098        test("incrementSnippet", 0, 256, 1);
099    }
100
101    @Test
102    public void increment2() {
103        test("incrementSnippet", 0, 256, 2);
104    }
105
106    @Test
107    public void increment3() {
108        test("incrementSnippet", 0, 256, 3);
109    }
110
111    public static Result incrementEqSnippet(int start, int limit, int step) {
112        int i;
113        int inc = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
114        Result ret = new Result();
115        for (i = start; i <= limit; i += inc) {
116            GraalDirectives.controlFlowAnchor();
117            ret.extremum = get(InductionVariable::extremumNode, i);
118        }
119        ret.exitValue = get(InductionVariable::exitValueNode, i);
120        return ret;
121    }
122
123    @Test
124    public void incrementEq1() {
125        test("incrementEqSnippet", 0, 256, 1);
126    }
127
128    @Test
129    public void incrementEq2() {
130        test("incrementEqSnippet", 0, 256, 2);
131    }
132
133    @Test
134    public void incrementEq3() {
135        test("incrementEqSnippet", 0, 256, 3);
136    }
137
138    public static Result decrementSnippet(int start, int limit, int step) {
139        int i;
140        int dec = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
141        Result ret = new Result();
142        for (i = start; i > limit; i -= dec) {
143            GraalDirectives.controlFlowAnchor();
144            ret.extremum = get(InductionVariable::extremumNode, i);
145        }
146        ret.exitValue = get(InductionVariable::exitValueNode, i);
147        return ret;
148    }
149
150    @Test
151    public void decrement1() {
152        test("decrementSnippet", 256, 0, 1);
153    }
154
155    @Test
156    public void decrement2() {
157        test("decrementSnippet", 256, 0, 2);
158    }
159
160    @Test
161    public void decrement3() {
162        test("decrementSnippet", 256, 0, 3);
163    }
164
165    public static Result decrementEqSnippet(int start, int limit, int step) {
166        int i;
167        int dec = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive
168        Result ret = new Result();
169        for (i = start; i >= limit; i -= dec) {
170            GraalDirectives.controlFlowAnchor();
171            ret.extremum = get(InductionVariable::extremumNode, i);
172        }
173        ret.exitValue = get(InductionVariable::exitValueNode, i);
174        return ret;
175    }
176
177    @Test
178    public void decrementEq1() {
179        test("decrementEqSnippet", 256, 0, 1);
180    }
181
182    @Test
183    public void decrementEq2() {
184        test("decrementEqSnippet", 256, 0, 2);
185    }
186
187    @Test
188    public void decrementEq3() {
189        test("decrementEqSnippet", 256, 0, 3);
190    }
191
192    public static Result twoVariablesSnippet() {
193        Result ret = new Result();
194        int j = 0;
195        for (int i = 0; i < 1024; i++) {
196            j += 5;
197            ret.extremum = get(InductionVariable::extremumNode, j);
198        }
199        ret.exitValue = get(InductionVariable::exitValueNode, j);
200        return ret;
201    }
202
203    @Test
204    public void testTwoVariables() {
205        test("twoVariablesSnippet");
206    }
207
208    @NodeInfo
209    private static class IVPropertyNode extends FloatingNode implements LIRLowerable {
210
211        public static final NodeClass<IVPropertyNode> TYPE = NodeClass.create(IVPropertyNode.class);
212
213        private final IVProperty property;
214        @Input private ValueNode iv;
215
216        public IVPropertyNode(IVProperty property, ValueNode iv) {
217            super(TYPE, iv.stamp().unrestricted());
218            this.property = property;
219            this.iv = iv;
220        }
221
222        public void rewrite(LoopsData loops) {
223            InductionVariable inductionVariable = loops.getInductionVariable(iv);
224            ValueNode node = property.get(inductionVariable);
225            graph().replaceFloating(this, node);
226        }
227
228        public void generate(NodeLIRBuilderTool gen) {
229            gen.setResult(this, gen.operand(iv));
230        }
231
232        @NodeIntrinsic
233        public static native int get(@ConstantNodeParameter IVProperty property, int iv);
234    }
235
236    protected static int getIntrinsic(IVProperty property, int iv) {
237        return IVPropertyNode.get(property, iv);
238    }
239
240    @Override
241    protected Plugins getDefaultGraphBuilderPlugins() {
242        Plugins plugins = super.getDefaultGraphBuilderPlugins();
243        Registration r = new Registration(plugins.getInvocationPlugins(), CountedLoopTest.class);
244
245        ResolvedJavaMethod intrinsic = getResolvedJavaMethod("getIntrinsic");
246        r.register2("get", IVProperty.class, int.class, new InvocationPlugin() {
247            public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver, ValueNode arg1, ValueNode arg2) {
248                b.intrinsify(targetMethod, intrinsic, new ValueNode[]{arg1, arg2});
249                return true;
250            }
251        });
252
253        return plugins;
254    }
255
256    @Override
257    protected boolean checkMidTierGraph(StructuredGraph graph) {
258        LoopsData loops = new LoopsData(graph);
259        loops.detectedCountedLoops();
260        for (IVPropertyNode node : graph.getNodes().filter(IVPropertyNode.class)) {
261            node.rewrite(loops);
262        }
263        assert graph.getNodes().filter(IVPropertyNode.class).isEmpty();
264        return true;
265    }
266
267}