1/*
2 * Copyright (c) 2016, 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 org.graalvm.compiler.api.directives.GraalDirectives;
26import org.graalvm.compiler.graph.Node;
27import org.graalvm.compiler.graph.iterators.NodeIterable;
28import org.graalvm.compiler.graph.spi.Canonicalizable;
29import org.graalvm.compiler.graph.spi.SimplifierTool;
30import org.graalvm.compiler.java.ComputeLoopFrequenciesClosure;
31import org.graalvm.compiler.nodes.LoopBeginNode;
32import org.graalvm.compiler.nodes.StructuredGraph;
33import org.graalvm.compiler.nodes.ValueNode;
34import org.graalvm.compiler.phases.BasePhase;
35import org.graalvm.compiler.phases.common.CanonicalizerPhase;
36import org.graalvm.compiler.phases.common.CanonicalizerPhase.CustomCanonicalizer;
37import org.graalvm.compiler.phases.contract.NodeCostUtil;
38import org.graalvm.compiler.phases.tiers.HighTierContext;
39import org.graalvm.compiler.phases.tiers.PhaseContext;
40import org.junit.Assert;
41import org.junit.Test;
42
43public class NodePropertiesTest extends GraalCompilerTest {
44
45    public static Object sideEffect;
46
47    public static Object[] array = new Object[]{new Object(), new Object(), new Object()};
48
49    public static int test1Snippet(int a) {
50        int x = 0;
51        if (a > 0) {
52            x = 1;
53            sideEffect = null;
54        } else {
55            x = 2;
56            sideEffect = null;
57        }
58        int b = 4;
59        sideEffect = null;
60        int c = b % 5;
61        // can shift
62        return a * x * c;
63    }
64
65    public static int test2Snippet(int a) {
66        int x = 0;
67        if (a > 0) {
68            x = 1;
69            sideEffect = null;
70        } else {
71            x = 2;
72            sideEffect = null;
73        }
74        sideEffect = null;
75        // cannot shift
76        return a * x * 41;
77    }
78
79    public static final int ITERATIONS_LOOP_1 = 128;
80    public static final int ITERATIONS_LOOP_2 = 256;
81
82    public static int testLoop01(int a) {
83        int res = 0;
84        for (int i = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_1, i < a); i++) {
85            res += i;
86        }
87        return res;
88    }
89
90    public static int testLoop02(int a) {
91        int res = 0;
92        for (int i = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_2, i < a); i++) {
93            res += i;
94        }
95        return res;
96    }
97
98    public static int testLoop03(int a) {
99        int res = 0;
100        for (int i = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_1, i < a); i++) {
101            res *= i;
102        }
103        return res;
104    }
105
106    public static int testLoop04(int a) {
107        int res = 0;
108        for (int i = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_1 * ITERATIONS_LOOP_2, i < a); i++) {
109            res += i;
110        }
111        return res;
112    }
113
114    public static int testLoop05(int a) {
115        int res = 0;
116        for (int i = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_1, i < a); i++) {
117            res += i;
118            for (int j = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_2, j < ITERATIONS_LOOP_2); j++) {
119                res += i;
120            }
121        }
122        return res;
123    }
124
125    public static int dontInline(int a) {
126        int res = 1;
127        for (int i = 0; i < a; i++) {
128            for (int j = 0; j < i; j++) {
129                for (int k = 0; k < j; k++) {
130                    res += i + j + k;
131                }
132            }
133        }
134        sideEffect = res;
135        return (Integer) sideEffect;
136    }
137
138    public static int untrused01(int a) {
139        return dontInline(a);
140    }
141
142    public static int arrayLoadTest(int a) {
143        return array[a].hashCode();
144    }
145
146    public static int arrayStoreTest(int a) {
147        array[2] = a;
148        return a;
149    }
150
151    public static int fieldLoad(int a) {
152        return sideEffect.hashCode() * a;
153    }
154
155    public static int fieldStore(int a) {
156        sideEffect = a;
157        return a;
158    }
159
160    @Test
161    public void testCanonicalizationExample() {
162        HighTierContext htc = getDefaultHighTierContext();
163        ImprovementSavingCanonicalizer c1 = new ImprovementSavingCanonicalizer();
164        StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("test1Snippet"));
165        new CanonicalizerPhase(c1).apply(g1, htc);
166        ImprovementSavingCanonicalizer c2 = new ImprovementSavingCanonicalizer();
167        StructuredGraph g2 = parseForCompile(getResolvedJavaMethod("test2Snippet"));
168        new CanonicalizerPhase(c2).apply(g2, htc);
169        Assert.assertTrue(c1.savedCycles > c2.savedCycles);
170    }
171
172    private static void prepareGraphForLoopFrequencies(StructuredGraph g, HighTierContext htc) {
173        // let canonicalizer work away branch probability nodes
174        new CanonicalizerPhase().apply(g, htc);
175        // recompute the loop frequencies
176        ComputeLoopFrequenciesClosure.compute(g);
177    }
178
179    private static void assertFrequency(StructuredGraph g, int iterations) {
180        NodeIterable<LoopBeginNode> loopBeginNodes = g.getNodes(LoopBeginNode.TYPE);
181        LoopBeginNode loopBeginNode = loopBeginNodes.first();
182        Assert.assertEquals("loop frequency of " + loopBeginNode, iterations, loopBeginNode.loopFrequency(), 0);
183    }
184
185    @Test
186    public void testDifferentLoopFaster() {
187        HighTierContext htc = getDefaultHighTierContext();
188        StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("testLoop01"));
189        StructuredGraph g2 = parseForCompile(getResolvedJavaMethod("testLoop03"));
190        prepareGraphForLoopFrequencies(g1, htc);
191        prepareGraphForLoopFrequencies(g2, htc);
192        assertFrequency(g1, ITERATIONS_LOOP_1);
193        assertFrequency(g2, ITERATIONS_LOOP_1);
194        GraphCostPhase gc1 = new GraphCostPhase();
195        GraphCostPhase gc2 = new GraphCostPhase();
196        gc1.apply(g1, htc);
197        gc2.apply(g2, htc);
198        g1.getDebug().log("Test testDifferentLoopFaster --> 1.Graph cycles:%f size:%f vs. 2.Graph cycles:%f size:%f\n", gc1.finalCycles, gc1.finalSize, gc2.finalCycles, gc2.finalSize);
199        Assert.assertTrue(gc2.finalCycles > gc1.finalCycles);
200        Assert.assertTrue(gc2.finalSize == gc1.finalSize);
201    }
202
203    @Test
204    public void testSameLoopMoreIterationsCostlier() {
205        HighTierContext htc = getDefaultHighTierContext();
206        StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("testLoop01"));
207        StructuredGraph g2 = parseForCompile(getResolvedJavaMethod("testLoop02"));
208        prepareGraphForLoopFrequencies(g1, htc);
209        prepareGraphForLoopFrequencies(g2, htc);
210        assertFrequency(g1, ITERATIONS_LOOP_1);
211        assertFrequency(g2, ITERATIONS_LOOP_2);
212        GraphCostPhase gc1 = new GraphCostPhase();
213        GraphCostPhase gc2 = new GraphCostPhase();
214        gc1.apply(g1, htc);
215        gc2.apply(g2, htc);
216        g1.getDebug().log("Test testSameLoopMoreIterationsCostlier --> 1.Graph cycles:%f size:%f vs. 2.Graph cycles:%f size:%f\n", gc1.finalCycles, gc1.finalSize, gc2.finalCycles, gc2.finalSize);
217        Assert.assertTrue(gc2.finalCycles > gc1.finalCycles);
218        Assert.assertTrue(gc2.finalSize == gc1.finalSize);
219    }
220
221    @Test
222    public void testDifferentLoopsInnerOuter() {
223        HighTierContext htc = getDefaultHighTierContext();
224        StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("testLoop04"));
225        StructuredGraph g2 = parseForCompile(getResolvedJavaMethod("testLoop05"));
226        prepareGraphForLoopFrequencies(g1, htc);
227        prepareGraphForLoopFrequencies(g2, htc);
228        assertFrequency(g1, ITERATIONS_LOOP_1 * ITERATIONS_LOOP_2);
229        GraphCostPhase gc1 = new GraphCostPhase();
230        GraphCostPhase gc2 = new GraphCostPhase();
231        gc1.apply(g1, htc);
232        gc2.apply(g2, htc);
233        g1.getDebug().log("Test testDifferentLoopsInnerOuter --> 1.Graph cycles:%f size:%f vs. 2.Graph cycles:%f size:%f\n", gc1.finalCycles, gc1.finalSize, gc2.finalCycles, gc2.finalSize);
234        Assert.assertTrue(gc2.finalSize > gc1.finalSize);
235    }
236
237    @Test
238    public void testGraphCost() {
239        StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("test1Snippet"));
240        StructuredGraph g2 = parseForCompile(getResolvedJavaMethod("test2Snippet"));
241        HighTierContext htc = getDefaultHighTierContext();
242        new CanonicalizerPhase().apply(g1, htc);
243        new CanonicalizerPhase().apply(g2, htc);
244        GraphCostPhase gc1 = new GraphCostPhase();
245        GraphCostPhase gc2 = new GraphCostPhase();
246        gc1.apply(g1, htc);
247        gc2.apply(g2, htc);
248        g1.getDebug().log("Test Graph Cost --> 1.Graph cost:%f vs. 2.Graph cost:%f\n", gc1.finalCycles, gc2.finalCycles);
249        Assert.assertTrue(gc2.finalCycles > gc1.finalCycles);
250        Assert.assertTrue(gc2.finalSize == gc1.finalSize);
251    }
252
253    @Test
254    public void testExpectUntrusted() {
255        StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("untrused01"));
256        HighTierContext htc = getDefaultHighTierContext();
257        new CanonicalizerPhase().apply(g1, htc);
258        GraphCostPhase gc1 = new GraphCostPhase();
259        gc1.apply(g1, htc);
260    }
261
262    @Test
263    public void testArrayLoad() {
264        StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("arrayLoadTest"));
265        HighTierContext htc = getDefaultHighTierContext();
266        new CanonicalizerPhase().apply(g1, htc);
267        GraphCostPhase gc1 = new GraphCostPhase();
268        gc1.apply(g1, htc);
269        Assert.assertEquals(15, gc1.finalCycles, 25);
270    }
271
272    @Test
273    public void testArrayStore() {
274        StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("arrayStoreTest"));
275        HighTierContext htc = getDefaultHighTierContext();
276        new CanonicalizerPhase().apply(g1, htc);
277        GraphCostPhase gc1 = new GraphCostPhase();
278        gc1.apply(g1, htc);
279        Assert.assertEquals(15, gc1.finalCycles, 25);
280    }
281
282    @Test
283    public void testFieldLoad() {
284        StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("fieldLoad"));
285        HighTierContext htc = getDefaultHighTierContext();
286        new CanonicalizerPhase().apply(g1, htc);
287        GraphCostPhase gc1 = new GraphCostPhase();
288        gc1.apply(g1, htc);
289        Assert.assertEquals(15, gc1.finalCycles, 25);
290    }
291
292    @Test
293    public void testFieldStore() {
294        StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("fieldStore"));
295        HighTierContext htc = getDefaultHighTierContext();
296        new CanonicalizerPhase().apply(g1, htc);
297        GraphCostPhase gc1 = new GraphCostPhase();
298        gc1.apply(g1, htc);
299        Assert.assertEquals(15, gc1.finalCycles, 25);
300    }
301
302    static class ImprovementSavingCanonicalizer extends CustomCanonicalizer {
303        private int savedCycles;
304
305        @Override
306        public void simplify(Node node, SimplifierTool tool) {
307            if (node instanceof Canonicalizable.Binary<?>) {
308                @SuppressWarnings("unchecked")
309                Canonicalizable.Binary<ValueNode> bc = (Canonicalizable.Binary<ValueNode>) node;
310                Node canonicalized = bc.canonical(tool, bc.getX(), bc.getY());
311                if (canonicalized != node) {
312                    savedCycles += node.estimatedNodeCycles().value - canonicalized.estimatedNodeCycles().value;
313                }
314            }
315        }
316    }
317
318    private static class GraphCostPhase extends BasePhase<PhaseContext> {
319        private double finalCycles;
320        private double finalSize;
321
322        @Override
323        protected void run(StructuredGraph graph, PhaseContext context) {
324            finalCycles = NodeCostUtil.computeGraphCycles(graph, true);
325            finalSize = NodeCostUtil.computeGraphSize(graph);
326        }
327
328    }
329
330}
331