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