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 */ 23package org.graalvm.compiler.core.test; 24 25import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED; 26import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED; 27 28import org.junit.Test; 29 30import org.graalvm.compiler.api.directives.GraalDirectives; 31import org.graalvm.compiler.graph.NodeClass; 32import org.graalvm.compiler.loop.InductionVariable; 33import org.graalvm.compiler.loop.LoopsData; 34import org.graalvm.compiler.nodeinfo.NodeInfo; 35import org.graalvm.compiler.nodes.StructuredGraph; 36import org.graalvm.compiler.nodes.ValueNode; 37import org.graalvm.compiler.nodes.calc.FloatingNode; 38import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins; 39import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderContext; 40import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugin; 41import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins.Registration; 42import org.graalvm.compiler.nodes.spi.LIRLowerable; 43import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool; 44 45import jdk.vm.ci.meta.JavaKind; 46import jdk.vm.ci.meta.ResolvedJavaMethod; 47 48public class CountedLoopTest extends GraalCompilerTest { 49 50 @FunctionalInterface 51 private interface IVProperty { 52 ValueNode get(InductionVariable iv); 53 } 54 55 /** 56 * Get a property of an induction variable. 57 * 58 * @param property 59 */ 60 private static int get(IVProperty property, int iv) { 61 return iv; 62 } 63 64 private static class Result { 65 public int extremum; 66 public int exitValue; 67 68 @Override 69 public int hashCode() { 70 final int prime = 31; 71 int result = 1; 72 result = prime * result + exitValue; 73 result = prime * result + extremum; 74 return result; 75 } 76 77 @Override 78 public boolean equals(Object obj) { 79 if (!(obj instanceof Result)) { 80 return false; 81 } 82 Result other = (Result) obj; 83 return extremum == other.extremum && exitValue == other.exitValue; 84 } 85 86 @Override 87 public String toString() { 88 return String.format("extremum = %d, exitValue = %d", extremum, exitValue); 89 } 90 } 91 92 public static Result incrementSnippet(int start, int limit, int step) { 93 int i; 94 int inc = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive 95 Result ret = new Result(); 96 for (i = start; i < limit; i += inc) { 97 GraalDirectives.controlFlowAnchor(); 98 ret.extremum = get(InductionVariable::extremumNode, i); 99 } 100 ret.exitValue = get(InductionVariable::exitValueNode, i); 101 return ret; 102 } 103 104 @Test 105 public void increment1() { 106 test("incrementSnippet", 0, 256, 1); 107 } 108 109 @Test 110 public void increment2() { 111 test("incrementSnippet", 0, 256, 2); 112 } 113 114 @Test 115 public void increment3() { 116 test("incrementSnippet", 0, 256, 3); 117 } 118 119 public static Result incrementEqSnippet(int start, int limit, int step) { 120 int i; 121 int inc = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive 122 Result ret = new Result(); 123 for (i = start; i <= limit; i += inc) { 124 GraalDirectives.controlFlowAnchor(); 125 ret.extremum = get(InductionVariable::extremumNode, i); 126 } 127 ret.exitValue = get(InductionVariable::exitValueNode, i); 128 return ret; 129 } 130 131 @Test 132 public void incrementEq1() { 133 test("incrementEqSnippet", 0, 256, 1); 134 } 135 136 @Test 137 public void incrementEq2() { 138 test("incrementEqSnippet", 0, 256, 2); 139 } 140 141 @Test 142 public void incrementEq3() { 143 test("incrementEqSnippet", 0, 256, 3); 144 } 145 146 public static Result decrementSnippet(int start, int limit, int step) { 147 int i; 148 int dec = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive 149 Result ret = new Result(); 150 for (i = start; i > limit; i -= dec) { 151 GraalDirectives.controlFlowAnchor(); 152 ret.extremum = get(InductionVariable::extremumNode, i); 153 } 154 ret.exitValue = get(InductionVariable::exitValueNode, i); 155 return ret; 156 } 157 158 @Test 159 public void decrement1() { 160 test("decrementSnippet", 256, 0, 1); 161 } 162 163 @Test 164 public void decrement2() { 165 test("decrementSnippet", 256, 0, 2); 166 } 167 168 @Test 169 public void decrement3() { 170 test("decrementSnippet", 256, 0, 3); 171 } 172 173 public static Result decrementEqSnippet(int start, int limit, int step) { 174 int i; 175 int dec = ((step - 1) & 0xFFFF) + 1; // make sure this value is always strictly positive 176 Result ret = new Result(); 177 for (i = start; i >= limit; i -= dec) { 178 GraalDirectives.controlFlowAnchor(); 179 ret.extremum = get(InductionVariable::extremumNode, i); 180 } 181 ret.exitValue = get(InductionVariable::exitValueNode, i); 182 return ret; 183 } 184 185 @Test 186 public void decrementEq1() { 187 test("decrementEqSnippet", 256, 0, 1); 188 } 189 190 @Test 191 public void decrementEq2() { 192 test("decrementEqSnippet", 256, 0, 2); 193 } 194 195 @Test 196 public void decrementEq3() { 197 test("decrementEqSnippet", 256, 0, 3); 198 } 199 200 public static Result twoVariablesSnippet() { 201 Result ret = new Result(); 202 int j = 0; 203 for (int i = 0; i < 1024; i++) { 204 j += 5; 205 GraalDirectives.controlFlowAnchor(); 206 ret.extremum = get(InductionVariable::extremumNode, j); 207 } 208 ret.exitValue = get(InductionVariable::exitValueNode, j); 209 return ret; 210 } 211 212 @Test 213 public void testTwoVariables() { 214 test("twoVariablesSnippet"); 215 } 216 217 @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED) 218 private static class IVPropertyNode extends FloatingNode implements LIRLowerable { 219 220 public static final NodeClass<IVPropertyNode> TYPE = NodeClass.create(IVPropertyNode.class); 221 222 private final IVProperty property; 223 @Input private ValueNode iv; 224 225 protected IVPropertyNode(IVProperty property, ValueNode iv) { 226 super(TYPE, iv.stamp().unrestricted()); 227 this.property = property; 228 this.iv = iv; 229 } 230 231 public void rewrite(LoopsData loops) { 232 InductionVariable inductionVariable = loops.getInductionVariable(iv); 233 assert inductionVariable != null; 234 ValueNode node = property.get(inductionVariable); 235 replaceAtUsagesAndDelete(node); 236 } 237 238 @Override 239 public void generate(NodeLIRBuilderTool gen) { 240 gen.setResult(this, gen.operand(iv)); 241 } 242 } 243 244 @Override 245 protected Plugins getDefaultGraphBuilderPlugins() { 246 Plugins plugins = super.getDefaultGraphBuilderPlugins(); 247 Registration r = new Registration(plugins.getInvocationPlugins(), CountedLoopTest.class); 248 249 r.register2("get", IVProperty.class, int.class, new InvocationPlugin() { 250 @Override 251 public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver, ValueNode arg1, ValueNode arg2) { 252 IVProperty property = null; 253 if (arg1.isConstant()) { 254 property = getSnippetReflection().asObject(IVProperty.class, arg1.asJavaConstant()); 255 } 256 if (property != null) { 257 b.addPush(JavaKind.Int, new IVPropertyNode(property, arg2)); 258 return true; 259 } else { 260 return false; 261 } 262 } 263 }); 264 265 return plugins; 266 } 267 268 @Override 269 protected boolean checkMidTierGraph(StructuredGraph graph) { 270 LoopsData loops = new LoopsData(graph); 271 loops.detectedCountedLoops(); 272 for (IVPropertyNode node : graph.getNodes().filter(IVPropertyNode.class)) { 273 node.rewrite(loops); 274 } 275 assert graph.getNodes().filter(IVPropertyNode.class).isEmpty(); 276 return true; 277 } 278 279 public static Result incrementNeqSnippet(int limit) { 280 int i; 281 int posLimit = ((limit - 1) & 0xFFFF) + 1; // make sure limit is always strictly positive 282 Result ret = new Result(); 283 for (i = 0; i != posLimit; i++) { 284 GraalDirectives.controlFlowAnchor(); 285 ret.extremum = get(InductionVariable::extremumNode, i); 286 } 287 ret.exitValue = get(InductionVariable::exitValueNode, i); 288 return ret; 289 } 290 291 @Test 292 public void decrementNeq() { 293 test("decrementNeqSnippet", 256); 294 } 295 296 public static Result decrementNeqSnippet(int limit) { 297 int i; 298 int posLimit = ((limit - 1) & 0xFFFF) + 1; // make sure limit is always strictly positive 299 Result ret = new Result(); 300 for (i = posLimit; i != 0; i--) { 301 GraalDirectives.controlFlowAnchor(); 302 ret.extremum = get(InductionVariable::extremumNode, i); 303 } 304 ret.exitValue = get(InductionVariable::exitValueNode, i); 305 return ret; 306 } 307 308 @Test 309 public void incrementNeq() { 310 test("incrementNeqSnippet", 256); 311 } 312} 313