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