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 {
  55         ValueNode get(InductionVariable iv);
  56     }
  57 
  58     @FunctionalInterface
  59     private interface StaticIVProperty {
  60         long get(InductionVariable iv);
  61     }
  62 
  63     @FunctionalInterface
  64     private interface IVPredicate {
  65         boolean test(InductionVariable iv);
  66     }
  67 
  68     /**
  69      * Get a property of an induction variable.
  70      */
  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 
  76     private static int get(@SuppressWarnings("unused") IVProperty property, int iv) {
  77         return iv;
  78     }
  79 
  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 
  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
  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
 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
 112         public String toString() {
 113             return String.format("extremum = %d, exitValue = %d", extremum, exitValue);
 114         }
 115     }
 116 
 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
 130     public void increment1() {
 131         testCounted("incrementSnippet", 0, 256, 1);
 132     }
 133 
 134     @Test
 135     public void increment2() {
 136         testCounted("incrementSnippet", 0, 256, 2);
 137     }
 138 
 139     @Test
 140     public void increment3() {
 141         testCounted("incrementSnippet", 0, 256, 3);
 142     }
 143 
 144     @Test
 145     public void increment4() {
 146         testCounted("incrementSnippet", -10, 1, Integer.MAX_VALUE);
 147     }
 148 
 149     @Test
 150     public void increment5() {
 151         testCounted("incrementSnippet", 256, 256, 1);
 152     }
 153 
 154     @Test
 155     public void increment6() {
 156         testCounted("incrementSnippet", 257, 256, 1);
 157     }
 158 
 159     @Test
 160     public void increment7() {
 161         testCounted("incrementSnippet", -10, Integer.MAX_VALUE, 1);
 162     }
 163 
 164     @Test
 165     public void increment8() {
 166         testCounted("incrementSnippet", -10, Integer.MAX_VALUE - 1, 2);
 167     }
 168 
 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
 182     public void incrementEq1() {
 183         testCounted("incrementEqSnippet", 0, 256, 1);
 184     }
 185 
 186     @Test
 187     public void incrementEq2() {
 188         testCounted("incrementEqSnippet", 0, 256, 2);
 189     }
 190 
 191     @Test
 192     public void incrementEq3() {
 193         testCounted("incrementEqSnippet", 0, 256, 3);
 194     }
 195 
 196     @Test
 197     public void incrementEq4() {
 198         testCounted("incrementEqSnippet", -10, 0, Integer.MAX_VALUE);
 199     }
 200 
 201     @Test
 202     public void incrementEq5() {
 203         testCounted("incrementEqSnippet", 256, 256, 1);
 204     }
 205 
 206     @Test
 207     public void incrementEq6() {
 208         testCounted("incrementEqSnippet", 257, 256, 1);
 209     }
 210 
 211     @Test
 212     public void incrementEq7() {
 213         testCounted("incrementEqSnippet", -10, Integer.MAX_VALUE - 1, 1);
 214     }
 215 
 216     @Test
 217     public void incrementEq8() {
 218         testCounted("incrementEqSnippet", -10, Integer.MAX_VALUE - 2, 2);
 219     }
 220 
 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
 234     public void decrement1() {
 235         testCounted("decrementSnippet", 256, 0, 1);
 236     }
 237 
 238     @Test
 239     public void decrement2() {
 240         testCounted("decrementSnippet", 256, 0, 2);
 241     }
 242 
 243     @Test
 244     public void decrement3() {
 245         testCounted("decrementSnippet", 256, 0, 3);
 246     }
 247 
 248     @Test
 249     public void decrement4() {
 250         testCounted("decrementSnippet", Integer.MAX_VALUE, -10, 1);
 251     }
 252 
 253     @Test
 254     public void decrement5() {
 255         testCounted("decrementSnippet", Integer.MAX_VALUE, -10, 2);
 256     }
 257 
 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
 271     public void decrementEq1() {
 272         testCounted("decrementEqSnippet", 256, 0, 1);
 273     }
 274 
 275     @Test
 276     public void decrementEq2() {
 277         testCounted("decrementEqSnippet", 256, 0, 2);
 278     }
 279 
 280     @Test
 281     public void decrementEq3() {
 282         testCounted("decrementEqSnippet", 256, 0, 3);
 283     }
 284 
 285     @Test
 286     public void decrementEq4() {
 287         testCounted("decrementEqSnippet", -10, 0, Integer.MAX_VALUE);
 288     }
 289 
 290     @Test
 291     public void decrementEq5() {
 292         testCounted("decrementEqSnippet", Integer.MAX_VALUE, -10, 1);
 293     }
 294 
 295     @Test
 296     public void decrementEq6() {
 297         testCounted("decrementEqSnippet", Integer.MAX_VALUE, -10, 2);
 298     }
 299 
 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
 313     public void testTwoVariables() {
 314         testCounted("twoVariablesSnippet");
 315     }
 316 
 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
 330     public void decrementNeq() {
 331         testCounted("decrementNeqSnippet", 256);
 332     }
 333 
 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
 347     public void incrementNeq() {
 348         testCounted("incrementNeqSnippet", 256);
 349     }
 350 
 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
 364     public void incrementLong1() {
 365         testCounted("incrementLongSnippet", 0L, 256L, 1L);
 366     }
 367 
 368     @Test
 369     public void incrementLong2() {
 370         testCounted("incrementLongSnippet", 0L, 256L, 2L);
 371     }
 372 
 373     @Test
 374     public void incrementLong3() {
 375         testCounted("incrementLongSnippet", 0L, 256L, 3L);
 376     }
 377 
 378     @Test
 379     public void incrementLong4() {
 380         testCounted("incrementLongSnippet", -10L, 1L, Long.MAX_VALUE);
 381     }
 382 
 383     @Test
 384     public void incrementLong5() {
 385         testCounted("incrementLongSnippet", 256L, 256L, 1L);
 386     }
 387 
 388     @Test
 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 
 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 
 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
 428         public void generate(NodeLIRBuilderTool gen) {
 429             gen.setResult(this, gen.operand(iv));
 430         }
 431     }
 432 
 433     @Override
 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 
 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
 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
 496     protected Object[] getArgumentToBind() {
 497         return argsToBind;
 498     }
 499 
 500     public void testCounted(String snippetName, Object... args) {
 501         test(snippetName, args);
 502         argsToBind = args;
 503         test(snippetName, args);
 504         argsToBind = null;
 505     }
 506 }