1 /* 2 * Copyright (c) 2015, 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 static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED; 28 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED; 29 30 import org.graalvm.compiler.api.directives.GraalDirectives; 31 import org.graalvm.compiler.graph.NodeClass; 32 import org.graalvm.compiler.loop.InductionVariable; 33 import org.graalvm.compiler.loop.LoopsData; 34 import org.graalvm.compiler.nodeinfo.NodeInfo; 35 import org.graalvm.compiler.nodes.ConstantNode; 36 import org.graalvm.compiler.nodes.NodeView; 37 import org.graalvm.compiler.nodes.StructuredGraph; 38 import org.graalvm.compiler.nodes.ValueNode; 39 import org.graalvm.compiler.nodes.calc.FloatingNode; 40 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderContext; 41 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugin; 42 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins; 43 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins.Registration; 44 import org.graalvm.compiler.nodes.spi.LIRLowerable; 45 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool; 46 import org.junit.Test; 47 48 import jdk.vm.ci.meta.JavaKind; 49 import jdk.vm.ci.meta.ResolvedJavaMethod; 50 51 public class CountedLoopTest extends GraalCompilerTest { 52 53 @FunctionalInterface 54 private interface IVProperty { get(InductionVariable iv)55 ValueNode get(InductionVariable iv); 56 } 57 58 @FunctionalInterface 59 private interface StaticIVProperty { get(InductionVariable iv)60 long get(InductionVariable iv); 61 } 62 63 @FunctionalInterface 64 private interface IVPredicate { test(InductionVariable iv)65 boolean test(InductionVariable iv); 66 } 67 68 /** 69 * Get a property of an induction variable. 70 */ get(@uppressWarningsR) IVProperty property, @SuppressWarnings(R) StaticIVProperty staticProperty, @SuppressWarnings(R) IVPredicate constantCheck, int iv)71 private static int get(@SuppressWarnings("unused") IVProperty property, @SuppressWarnings("unused") StaticIVProperty staticProperty, @SuppressWarnings("unused") IVPredicate constantCheck, 72 int iv) { 73 return iv; 74 } 75 get(@uppressWarningsR) IVProperty property, int iv)76 private static int get(@SuppressWarnings("unused") IVProperty property, int iv) { 77 return iv; 78 } 79 get(@uppressWarningsR) IVProperty property, @SuppressWarnings(R) StaticIVProperty staticProperty, @SuppressWarnings(R) IVPredicate constantCheck, long iv)80 private static long get(@SuppressWarnings("unused") IVProperty property, @SuppressWarnings("unused") StaticIVProperty staticProperty, @SuppressWarnings("unused") IVPredicate constantCheck, 81 long iv) { 82 return iv; 83 } 84 get(@uppressWarningsR) IVProperty property, long iv)85 private static long get(@SuppressWarnings("unused") IVProperty property, long iv) { 86 return iv; 87 } 88 89 private static class Result { 90 public long extremum; 91 public long exitValue; 92 93 @Override hashCode()94 public int hashCode() { 95 final int prime = 31; 96 int result = 1; 97 result = prime * result + Long.hashCode(exitValue); 98 result = prime * result + Long.hashCode(extremum); 99 return result; 100 } 101 102 @Override equals(Object obj)103 public boolean equals(Object obj) { 104 if (!(obj instanceof Result)) { 105 return false; 106 } 107 Result other = (Result) obj; 108 return extremum == other.extremum && exitValue == other.exitValue; 109 } 110 111 @Override toString()112 public String toString() { 113 return String.format("extremum = %d, exitValue = %d", extremum, exitValue); 114 } 115 } 116 incrementSnippet(int start, int limit, int step)117 public static Result incrementSnippet(int start, int limit, int step) { 118 int i; 119 int inc = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive 120 Result ret = new Result(); 121 for (i = start; i < limit; i += inc) { 122 GraalDirectives.controlFlowAnchor(); 123 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i); 124 } 125 ret.exitValue = get(InductionVariable::exitValueNode, i); 126 return ret; 127 } 128 129 @Test increment1()130 public void increment1() { 131 testCounted("incrementSnippet", 0, 256, 1); 132 } 133 134 @Test increment2()135 public void increment2() { 136 testCounted("incrementSnippet", 0, 256, 2); 137 } 138 139 @Test increment3()140 public void increment3() { 141 testCounted("incrementSnippet", 0, 256, 3); 142 } 143 144 @Test increment4()145 public void increment4() { 146 testCounted("incrementSnippet", -10, 1, Integer.MAX_VALUE); 147 } 148 149 @Test increment5()150 public void increment5() { 151 testCounted("incrementSnippet", 256, 256, 1); 152 } 153 154 @Test increment6()155 public void increment6() { 156 testCounted("incrementSnippet", 257, 256, 1); 157 } 158 159 @Test increment7()160 public void increment7() { 161 testCounted("incrementSnippet", -10, Integer.MAX_VALUE, 1); 162 } 163 164 @Test increment8()165 public void increment8() { 166 testCounted("incrementSnippet", -10, Integer.MAX_VALUE - 1, 2); 167 } 168 incrementEqSnippet(int start, int limit, int step)169 public static Result incrementEqSnippet(int start, int limit, int step) { 170 int i; 171 int inc = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive 172 Result ret = new Result(); 173 for (i = start; i <= limit; i += inc) { 174 GraalDirectives.controlFlowAnchor(); 175 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i); 176 } 177 ret.exitValue = get(InductionVariable::exitValueNode, i); 178 return ret; 179 } 180 181 @Test incrementEq1()182 public void incrementEq1() { 183 testCounted("incrementEqSnippet", 0, 256, 1); 184 } 185 186 @Test incrementEq2()187 public void incrementEq2() { 188 testCounted("incrementEqSnippet", 0, 256, 2); 189 } 190 191 @Test incrementEq3()192 public void incrementEq3() { 193 testCounted("incrementEqSnippet", 0, 256, 3); 194 } 195 196 @Test incrementEq4()197 public void incrementEq4() { 198 testCounted("incrementEqSnippet", -10, 0, Integer.MAX_VALUE); 199 } 200 201 @Test incrementEq5()202 public void incrementEq5() { 203 testCounted("incrementEqSnippet", 256, 256, 1); 204 } 205 206 @Test incrementEq6()207 public void incrementEq6() { 208 testCounted("incrementEqSnippet", 257, 256, 1); 209 } 210 211 @Test incrementEq7()212 public void incrementEq7() { 213 testCounted("incrementEqSnippet", -10, Integer.MAX_VALUE - 1, 1); 214 } 215 216 @Test incrementEq8()217 public void incrementEq8() { 218 testCounted("incrementEqSnippet", -10, Integer.MAX_VALUE - 2, 2); 219 } 220 decrementSnippet(int start, int limit, int step)221 public static Result decrementSnippet(int start, int limit, int step) { 222 int i; 223 int dec = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive 224 Result ret = new Result(); 225 for (i = start; i > limit; i -= dec) { 226 GraalDirectives.controlFlowAnchor(); 227 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i); 228 } 229 ret.exitValue = get(InductionVariable::exitValueNode, i); 230 return ret; 231 } 232 233 @Test decrement1()234 public void decrement1() { 235 testCounted("decrementSnippet", 256, 0, 1); 236 } 237 238 @Test decrement2()239 public void decrement2() { 240 testCounted("decrementSnippet", 256, 0, 2); 241 } 242 243 @Test decrement3()244 public void decrement3() { 245 testCounted("decrementSnippet", 256, 0, 3); 246 } 247 248 @Test decrement4()249 public void decrement4() { 250 testCounted("decrementSnippet", Integer.MAX_VALUE, -10, 1); 251 } 252 253 @Test decrement5()254 public void decrement5() { 255 testCounted("decrementSnippet", Integer.MAX_VALUE, -10, 2); 256 } 257 decrementEqSnippet(int start, int limit, int step)258 public static Result decrementEqSnippet(int start, int limit, int step) { 259 int i; 260 int dec = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive 261 Result ret = new Result(); 262 for (i = start; i >= limit; i -= dec) { 263 GraalDirectives.controlFlowAnchor(); 264 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i); 265 } 266 ret.exitValue = get(InductionVariable::exitValueNode, i); 267 return ret; 268 } 269 270 @Test decrementEq1()271 public void decrementEq1() { 272 testCounted("decrementEqSnippet", 256, 0, 1); 273 } 274 275 @Test decrementEq2()276 public void decrementEq2() { 277 testCounted("decrementEqSnippet", 256, 0, 2); 278 } 279 280 @Test decrementEq3()281 public void decrementEq3() { 282 testCounted("decrementEqSnippet", 256, 0, 3); 283 } 284 285 @Test decrementEq4()286 public void decrementEq4() { 287 testCounted("decrementEqSnippet", -10, 0, Integer.MAX_VALUE); 288 } 289 290 @Test decrementEq5()291 public void decrementEq5() { 292 testCounted("decrementEqSnippet", Integer.MAX_VALUE, -10, 1); 293 } 294 295 @Test decrementEq6()296 public void decrementEq6() { 297 testCounted("decrementEqSnippet", Integer.MAX_VALUE, -10, 2); 298 } 299 twoVariablesSnippet()300 public static Result twoVariablesSnippet() { 301 Result ret = new Result(); 302 int j = 0; 303 for (int i = 0; i < 1024; i++) { 304 j += 5; 305 GraalDirectives.controlFlowAnchor(); 306 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, j); 307 } 308 ret.exitValue = get(InductionVariable::exitValueNode, j); 309 return ret; 310 } 311 312 @Test testTwoVariables()313 public void testTwoVariables() { 314 testCounted("twoVariablesSnippet"); 315 } 316 incrementNeqSnippet(int limit)317 public static Result incrementNeqSnippet(int limit) { 318 int i; 319 int posLimit = ((limit - 1) & 0xFFFF) + 1; // make sure limit is always strictly positive 320 Result ret = new Result(); 321 for (i = 0; i != posLimit; i++) { 322 GraalDirectives.controlFlowAnchor(); 323 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i); 324 } 325 ret.exitValue = get(InductionVariable::exitValueNode, i); 326 return ret; 327 } 328 329 @Test decrementNeq()330 public void decrementNeq() { 331 testCounted("decrementNeqSnippet", 256); 332 } 333 decrementNeqSnippet(int limit)334 public static Result decrementNeqSnippet(int limit) { 335 int i; 336 int posLimit = ((limit - 1) & 0xFFFF) + 1; // make sure limit is always strictly positive 337 Result ret = new Result(); 338 for (i = posLimit; i != 0; i--) { 339 GraalDirectives.controlFlowAnchor(); 340 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i); 341 } 342 ret.exitValue = get(InductionVariable::exitValueNode, i); 343 return ret; 344 } 345 346 @Test incrementNeq()347 public void incrementNeq() { 348 testCounted("incrementNeqSnippet", 256); 349 } 350 incrementLongSnippet(long start, long limit, long step)351 public static Result incrementLongSnippet(long start, long limit, long step) { 352 long i; 353 long inc = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive 354 Result ret = new Result(); 355 for (i = start; i < limit; i += inc) { 356 GraalDirectives.controlFlowAnchor(); 357 ret.extremum = get(InductionVariable::extremumNode, InductionVariable::constantExtremum, InductionVariable::isConstantExtremum, i); 358 } 359 ret.exitValue = get(InductionVariable::exitValueNode, i); 360 return ret; 361 } 362 363 @Test incrementLong1()364 public void incrementLong1() { 365 testCounted("incrementLongSnippet", 0L, 256L, 1L); 366 } 367 368 @Test incrementLong2()369 public void incrementLong2() { 370 testCounted("incrementLongSnippet", 0L, 256L, 2L); 371 } 372 373 @Test incrementLong3()374 public void incrementLong3() { 375 testCounted("incrementLongSnippet", 0L, 256L, 3L); 376 } 377 378 @Test incrementLong4()379 public void incrementLong4() { 380 testCounted("incrementLongSnippet", -10L, 1L, Long.MAX_VALUE); 381 } 382 383 @Test incrementLong5()384 public void incrementLong5() { 385 testCounted("incrementLongSnippet", 256L, 256L, 1L); 386 } 387 388 @Test incrementLong6()389 public void incrementLong6() { 390 testCounted("incrementLongSnippet", 257L, 256L, 1L); 391 } 392 393 @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED) 394 private static class IVPropertyNode extends FloatingNode implements LIRLowerable { 395 396 public static final NodeClass<IVPropertyNode> TYPE = NodeClass.create(IVPropertyNode.class); 397 398 private final IVProperty property; 399 private final StaticIVProperty staticProperty; 400 private final IVPredicate staticCheck; 401 @Input private ValueNode iv; 402 IVPropertyNode(IVProperty property, StaticIVProperty staticProperty, IVPredicate staticCheck, ValueNode iv)403 protected IVPropertyNode(IVProperty property, StaticIVProperty staticProperty, IVPredicate staticCheck, ValueNode iv) { 404 super(TYPE, iv.stamp(NodeView.DEFAULT).unrestricted()); 405 this.property = property; 406 this.staticProperty = staticProperty; 407 this.staticCheck = staticCheck; 408 this.iv = iv; 409 } 410 rewrite(LoopsData loops)411 public void rewrite(LoopsData loops) { 412 InductionVariable inductionVariable = loops.getInductionVariable(iv); 413 assert inductionVariable != null; 414 ValueNode node = null; 415 if (staticCheck != null) { 416 assert staticProperty != null; 417 if (staticCheck.test(inductionVariable)) { 418 node = ConstantNode.forLong(staticProperty.get(inductionVariable), graph()); 419 } 420 } 421 if (node == null) { 422 node = property.get(inductionVariable); 423 } 424 replaceAtUsagesAndDelete(node); 425 } 426 427 @Override generate(NodeLIRBuilderTool gen)428 public void generate(NodeLIRBuilderTool gen) { 429 gen.setResult(this, gen.operand(iv)); 430 } 431 } 432 433 @Override registerInvocationPlugins(InvocationPlugins invocationPlugins)434 protected void registerInvocationPlugins(InvocationPlugins invocationPlugins) { 435 Registration r = new Registration(invocationPlugins, CountedLoopTest.class); 436 registerPlugins(r, JavaKind.Int); 437 registerPlugins(r, JavaKind.Long); 438 super.registerInvocationPlugins(invocationPlugins); 439 } 440 registerPlugins(Registration r, JavaKind ivKind)441 private void registerPlugins(Registration r, JavaKind ivKind) { 442 r.register2("get", IVProperty.class, ivKind.toJavaClass(), new InvocationPlugin() { 443 @Override 444 public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver, ValueNode arg1, ValueNode arg2) { 445 IVProperty property = null; 446 if (arg1.isConstant()) { 447 property = getSnippetReflection().asObject(IVProperty.class, arg1.asJavaConstant()); 448 } 449 if (property != null) { 450 b.addPush(ivKind, new IVPropertyNode(property, null, null, arg2)); 451 return true; 452 } else { 453 return false; 454 } 455 } 456 }); 457 r.register4("get", IVProperty.class, StaticIVProperty.class, IVPredicate.class, ivKind.toJavaClass(), new InvocationPlugin() { 458 @Override 459 public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver, ValueNode arg1, ValueNode arg2, ValueNode arg3, ValueNode arg4) { 460 IVProperty property = null; 461 StaticIVProperty staticProperty = null; 462 IVPredicate staticCheck = null; 463 if (arg1.isConstant()) { 464 property = getSnippetReflection().asObject(IVProperty.class, arg1.asJavaConstant()); 465 } 466 if (arg2.isConstant()) { 467 staticProperty = getSnippetReflection().asObject(StaticIVProperty.class, arg2.asJavaConstant()); 468 } 469 if (arg3.isConstant()) { 470 staticCheck = getSnippetReflection().asObject(IVPredicate.class, arg3.asJavaConstant()); 471 } 472 if (property != null && staticProperty != null && staticCheck != null) { 473 b.addPush(ivKind, new IVPropertyNode(property, staticProperty, staticCheck, arg4)); 474 return true; 475 } else { 476 return false; 477 } 478 } 479 }); 480 } 481 482 @Override checkHighTierGraph(StructuredGraph graph)483 protected boolean checkHighTierGraph(StructuredGraph graph) { 484 LoopsData loops = new LoopsData(graph); 485 loops.detectedCountedLoops(); 486 for (IVPropertyNode node : graph.getNodes().filter(IVPropertyNode.class)) { 487 node.rewrite(loops); 488 } 489 assert graph.getNodes().filter(IVPropertyNode.class).isEmpty(); 490 return true; 491 } 492 493 private Object[] argsToBind; 494 495 @Override getArgumentToBind()496 protected Object[] getArgumentToBind() { 497 return argsToBind; 498 } 499 testCounted(String snippetName, Object... args)500 public void testCounted(String snippetName, Object... args) { 501 test(snippetName, args); 502 argsToBind = args; 503 test(snippetName, args); 504 argsToBind = null; 505 } 506 } 507