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 */
23 package org.graalvm.compiler.core.test;
24
25 import org.graalvm.compiler.api.directives.GraalDirectives;
26 import org.graalvm.compiler.graph.Node;
27 import org.graalvm.compiler.graph.iterators.NodeIterable;
28 import org.graalvm.compiler.graph.spi.Canonicalizable;
29 import org.graalvm.compiler.graph.spi.SimplifierTool;
30 import org.graalvm.compiler.java.ComputeLoopFrequenciesClosure;
31 import org.graalvm.compiler.nodes.LoopBeginNode;
32 import org.graalvm.compiler.nodes.StructuredGraph;
33 import org.graalvm.compiler.nodes.ValueNode;
34 import org.graalvm.compiler.phases.BasePhase;
35 import org.graalvm.compiler.phases.common.CanonicalizerPhase;
36 import org.graalvm.compiler.phases.common.CanonicalizerPhase.CustomCanonicalizer;
37 import org.graalvm.compiler.phases.contract.NodeCostUtil;
38 import org.graalvm.compiler.phases.tiers.HighTierContext;
39 import org.graalvm.compiler.phases.tiers.PhaseContext;
40 import org.junit.Assert;
41 import org.junit.Test;
42
43 public 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 }