1 /* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 /** 18 * Regression tests for loop optimizations. 19 */ 20 public class Main { 21 22 /// CHECK-START: int Main.earlyExitFirst(int) loop_optimization (before) 23 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 24 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 25 // 26 /// CHECK-START: int Main.earlyExitFirst(int) loop_optimization (after) 27 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 28 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none earlyExitFirst(int m)29 static int earlyExitFirst(int m) { 30 int k = 0; 31 for (int i = 0; i < 10; i++) { 32 if (i == m) { 33 return k; 34 } 35 k++; 36 } 37 return k; 38 } 39 40 /// CHECK-START: int Main.earlyExitLast(int) loop_optimization (before) 41 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 42 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 43 // 44 /// CHECK-START: int Main.earlyExitLast(int) loop_optimization (after) 45 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 46 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none earlyExitLast(int m)47 static int earlyExitLast(int m) { 48 int k = 0; 49 for (int i = 0; i < 10; i++) { 50 k++; 51 if (i == m) { 52 return k; 53 } 54 } 55 return k; 56 } 57 58 /// CHECK-START: int Main.earlyExitNested() loop_optimization (before) 59 /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none 60 /// CHECK-DAG: Phi loop:<<Loop1>> outer_loop:none 61 /// CHECK-DAG: Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>> 62 /// CHECK-DAG: Phi loop:<<Loop2>> outer_loop:<<Loop1>> 63 // 64 /// CHECK-START: int Main.earlyExitNested() loop_optimization (after) 65 /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none 66 /// CHECK-DAG: Phi loop:<<Loop1>> outer_loop:none 67 // 68 /// CHECK-START: int Main.earlyExitNested() loop_optimization (after) 69 /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:{{B\d+}} earlyExitNested()70 static int earlyExitNested() { 71 int offset = 0; 72 for (int i = 0; i < 2; i++) { 73 int start = offset; 74 // This loop can be removed. 75 for (int j = 0; j < 2; j++) { 76 offset++; 77 } 78 if (i == 1) { 79 return start; 80 } 81 } 82 return 0; 83 } 84 85 // Regression test for b/33774618: transfer operations involving 86 // narrowing linear induction should be done correctly. 87 // 88 /// CHECK-START: int Main.transferNarrowWrap() loop_optimization (before) 89 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 90 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 91 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 92 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 93 // 94 /// CHECK-START: int Main.transferNarrowWrap() loop_optimization (after) 95 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 96 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 97 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 98 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none transferNarrowWrap()99 static int transferNarrowWrap() { 100 short x = 0; 101 int w = 10; 102 int v = 3; 103 for (int i = 0; i < 10; i++) { 104 v = w + 1; // transfer on wrap-around 105 w = x; // wrap-around 106 x += 2; // narrowing linear 107 } 108 return v; 109 } 110 111 // Regression test for b/33774618: transfer operations involving 112 // narrowing linear induction should be done correctly 113 // (currently rejected, could be improved). 114 // 115 /// CHECK-START: int Main.polynomialShort() loop_optimization (before) 116 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 117 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 118 // 119 /// CHECK-START: int Main.polynomialShort() loop_optimization (after) 120 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 121 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none polynomialShort()122 static int polynomialShort() { 123 int x = 0; 124 for (short i = 0; i < 10; i++) { 125 x = x - i; // polynomial on narrowing linear 126 } 127 return x; 128 } 129 130 // Regression test for b/33774618: transfer operations involving 131 // narrowing linear induction should be done correctly 132 // (currently rejected, could be improved). 133 // 134 /// CHECK-START: int Main.polynomialIntFromLong() loop_optimization (before) 135 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 136 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 137 // 138 /// CHECK-START: int Main.polynomialIntFromLong() loop_optimization (after) 139 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 140 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none polynomialIntFromLong()141 static int polynomialIntFromLong() { 142 int x = 0; 143 for (long i = 0; i < 10; i++) { 144 x = x - (int) i; // polynomial on narrowing linear 145 } 146 return x; 147 } 148 149 /// CHECK-START: int Main.polynomialInt() loop_optimization (before) 150 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 151 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 152 // 153 /// CHECK-START: int Main.polynomialInt() loop_optimization (after) 154 /// CHECK-NOT: Phi 155 // 156 /// CHECK-START: int Main.polynomialInt() instruction_simplifier$after_bce (after) 157 /// CHECK-DAG: <<Int:i\d+>> IntConstant -45 loop:none 158 /// CHECK-DAG: Return [<<Int>>] loop:none polynomialInt()159 static int polynomialInt() { 160 int x = 0; 161 for (int i = 0; i < 10; i++) { 162 x = x - i; 163 } 164 return x; 165 } 166 167 // Regression test for b/34779592 (found with fuzz testing): overflow for last value 168 // of division truncates to zero, for multiplication it simply truncates. 169 // 170 /// CHECK-START: int Main.geoIntDivLastValue(int) loop_optimization (before) 171 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 172 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 173 // 174 /// CHECK-START: int Main.geoIntDivLastValue(int) loop_optimization (after) 175 /// CHECK-NOT: Phi 176 // 177 /// CHECK-START: int Main.geoIntDivLastValue(int) instruction_simplifier$after_bce (after) 178 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none 179 /// CHECK-DAG: Return [<<Int>>] loop:none geoIntDivLastValue(int x)180 static int geoIntDivLastValue(int x) { 181 for (int i = 0; i < 2; i++) { 182 x /= 1081788608; 183 } 184 return x; 185 } 186 187 /// CHECK-START: int Main.geoIntMulLastValue(int) loop_optimization (before) 188 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 189 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 190 // 191 /// CHECK-START: int Main.geoIntMulLastValue(int) loop_optimization (after) 192 /// CHECK-NOT: Phi 193 // 194 /// CHECK-START: int Main.geoIntMulLastValue(int) instruction_simplifier$after_bce (after) 195 /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none 196 /// CHECK-DAG: <<Int:i\d+>> IntConstant -194211840 loop:none 197 /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Par>>,<<Int>>] loop:none 198 /// CHECK-DAG: Return [<<Mul>>] loop:none geoIntMulLastValue(int x)199 static int geoIntMulLastValue(int x) { 200 for (int i = 0; i < 2; i++) { 201 x *= 1081788608; 202 } 203 return x; 204 } 205 206 /// CHECK-START: long Main.geoLongDivLastValue(long) loop_optimization (before) 207 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 208 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 209 // 210 /// CHECK-START: long Main.geoLongDivLastValue(long) loop_optimization (after) 211 /// CHECK-NOT: Phi 212 // 213 /// CHECK-START: long Main.geoLongDivLastValue(long) instruction_simplifier$after_bce (after) 214 /// CHECK-DAG: <<Long:j\d+>> LongConstant 0 loop:none 215 /// CHECK-DAG: Return [<<Long>>] loop:none 216 // 217 // Tests overflow in the divisor (while updating intermediate result). geoLongDivLastValue(long x)218 static long geoLongDivLastValue(long x) { 219 for (int i = 0; i < 10; i++) { 220 x /= 1081788608; 221 } 222 return x; 223 } 224 225 /// CHECK-START: long Main.geoLongDivLastValue() loop_optimization (before) 226 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 227 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 228 // 229 /// CHECK-START: long Main.geoLongDivLastValue() loop_optimization (after) 230 /// CHECK-NOT: Phi 231 // 232 /// CHECK-START: long Main.geoLongDivLastValue() instruction_simplifier$after_bce (after) 233 /// CHECK-DAG: <<Long:j\d+>> LongConstant 0 loop:none 234 /// CHECK-DAG: Return [<<Long>>] loop:none 235 // 236 // Tests overflow in the divisor (while updating base). geoLongDivLastValue()237 static long geoLongDivLastValue() { 238 long x = -1; 239 for (int i2 = 0; i2 < 2; i2++) { 240 x /= (Long.MAX_VALUE); 241 } 242 return x; 243 } 244 245 /// CHECK-START: long Main.geoLongMulLastValue(long) loop_optimization (before) 246 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 247 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 248 // 249 /// CHECK-START: long Main.geoLongMulLastValue(long) loop_optimization (after) 250 /// CHECK-NOT: Phi 251 // 252 /// CHECK-START: long Main.geoLongMulLastValue(long) instruction_simplifier$after_bce (after) 253 /// CHECK-DAG: <<Par:j\d+>> ParameterValue loop:none 254 /// CHECK-DAG: <<Long:j\d+>> LongConstant -8070450532247928832 loop:none 255 /// CHECK-DAG: <<Mul:j\d+>> Mul [<<Par>>,<<Long>>] loop:none 256 /// CHECK-DAG: Return [<<Mul>>] loop:none geoLongMulLastValue(long x)257 static long geoLongMulLastValue(long x) { 258 for (int i = 0; i < 10; i++) { 259 x *= 1081788608; 260 } 261 return x; 262 } 263 264 // If vectorized, the narrowing subscript should not cause 265 // type inconsistencies in the synthesized code. narrowingSubscript(float[] a)266 static void narrowingSubscript(float[] a) { 267 float val = 2.0f; 268 for (long i = 0; i < a.length; i++) { 269 a[(int) i] += val; 270 } 271 } 272 273 // If vectorized, invariant stride should be recognized 274 // as a reduction, not a unit stride in outer loop. reduc(int[] xx, int[] yy)275 static void reduc(int[] xx, int[] yy) { 276 for (int i0 = 0; i0 < 2; i0++) { 277 for (int i1 = 0; i1 < 469; i1++) { 278 xx[i0] -= (++yy[i1]); 279 } 280 } 281 } 282 283 // If vectorized, string encoding should be dealt with. string2Bytes(char[] a, String b)284 private static void string2Bytes(char[] a, String b) { 285 int min = Math.min(a.length, b.length()); 286 for (int i = 0; i < min; i++) { 287 a[i] = b.charAt(i); 288 } 289 } 290 291 // A strange function that does not inline. $noinline$foo(boolean x, int n)292 private static void $noinline$foo(boolean x, int n) { 293 if (n < 0) 294 throw new Error("oh no"); 295 if (n > 100) { 296 $noinline$foo(!x, n - 1); 297 $noinline$foo(!x, n - 2); 298 $noinline$foo(!x, n - 3); 299 $noinline$foo(!x, n - 4); 300 } 301 } 302 303 // A loop with environment uses of x (the terminating condition). As exposed by bug 304 // b/37247891, the loop can be unrolled, but should handle the (unlikely, but clearly 305 // not impossible) environment uses of the terminating condition in a correct manner. envUsesInCond()306 private static void envUsesInCond() { 307 boolean x = false; 308 for (int i = 0; !(x = i >= 1); i++) { 309 $noinline$foo(true, i); 310 } 311 } 312 313 /// CHECK-START: void Main.oneBoth(short[], char[]) loop_optimization (before) 314 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 315 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 316 /// CHECK-DAG: ArraySet [{{l\d+}},<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none 317 /// CHECK-DAG: ArraySet [{{l\d+}},<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none 318 // 319 /// CHECK-START-ARM64: void Main.oneBoth(short[], char[]) loop_optimization (after) 320 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 321 /// CHECK-DAG: <<Repl:d\d+>> VecReplicateScalar [<<One>>] loop:none 322 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 323 /// CHECK-DAG: VecStore [{{l\d+}},<<Phi>>,<<Repl>>] loop:<<Loop>> outer_loop:none 324 /// CHECK-DAG: VecStore [{{l\d+}},<<Phi>>,<<Repl>>] loop:<<Loop>> outer_loop:none 325 // 326 // Bug b/37764324: integral same-length packed types can be mixed freely. oneBoth(short[] a, char[] b)327 private static void oneBoth(short[] a, char[] b) { 328 for (int i = 0; i < Math.min(a.length, b.length); i++) { 329 a[i] = 1; 330 b[i] = 1; 331 } 332 } 333 334 // Bug b/37768917: potential dynamic BCE vs. loop optimizations 335 // case should be deal with correctly (used to DCHECK fail). arrayInTripCount(int[] a, byte[] b, int n)336 private static void arrayInTripCount(int[] a, byte[] b, int n) { 337 for (int k = 0; k < n; k++) { 338 for (int i = 0, u = a[0]; i < u; i++) { 339 b[i] += 2; 340 } 341 } 342 } 343 main(String[] args)344 public static void main(String[] args) { 345 expectEquals(10, earlyExitFirst(-1)); 346 for (int i = 0; i <= 10; i++) { 347 expectEquals(i, earlyExitFirst(i)); 348 } 349 expectEquals(10, earlyExitFirst(11)); 350 351 expectEquals(10, earlyExitLast(-1)); 352 for (int i = 0; i < 10; i++) { 353 expectEquals(i + 1, earlyExitLast(i)); 354 } 355 expectEquals(10, earlyExitLast(10)); 356 expectEquals(10, earlyExitLast(11)); 357 358 expectEquals(2, earlyExitNested()); 359 360 expectEquals(17, transferNarrowWrap()); 361 expectEquals(-45, polynomialShort()); 362 expectEquals(-45, polynomialIntFromLong()); 363 expectEquals(-45, polynomialInt()); 364 365 expectEquals(0, geoIntDivLastValue(0)); 366 expectEquals(0, geoIntDivLastValue(1)); 367 expectEquals(0, geoIntDivLastValue(2)); 368 expectEquals(0, geoIntDivLastValue(1081788608)); 369 expectEquals(0, geoIntDivLastValue(-1081788608)); 370 expectEquals(0, geoIntDivLastValue(2147483647)); 371 expectEquals(0, geoIntDivLastValue(-2147483648)); 372 373 expectEquals( 0, geoIntMulLastValue(0)); 374 expectEquals( -194211840, geoIntMulLastValue(1)); 375 expectEquals( -388423680, geoIntMulLastValue(2)); 376 expectEquals(-1041498112, geoIntMulLastValue(1081788608)); 377 expectEquals( 1041498112, geoIntMulLastValue(-1081788608)); 378 expectEquals( 194211840, geoIntMulLastValue(2147483647)); 379 expectEquals( 0, geoIntMulLastValue(-2147483648)); 380 381 expectEquals(0L, geoLongDivLastValue(0L)); 382 expectEquals(0L, geoLongDivLastValue(1L)); 383 expectEquals(0L, geoLongDivLastValue(2L)); 384 expectEquals(0L, geoLongDivLastValue(1081788608L)); 385 expectEquals(0L, geoLongDivLastValue(-1081788608L)); 386 expectEquals(0L, geoLongDivLastValue(2147483647L)); 387 expectEquals(0L, geoLongDivLastValue(-2147483648L)); 388 expectEquals(0L, geoLongDivLastValue(9223372036854775807L)); 389 expectEquals(0L, geoLongDivLastValue(-9223372036854775808L)); 390 391 expectEquals(0L, geoLongDivLastValue()); 392 393 expectEquals( 0L, geoLongMulLastValue(0L)); 394 expectEquals(-8070450532247928832L, geoLongMulLastValue(1L)); 395 expectEquals( 2305843009213693952L, geoLongMulLastValue(2L)); 396 expectEquals( 0L, geoLongMulLastValue(1081788608L)); 397 expectEquals( 0L, geoLongMulLastValue(-1081788608L)); 398 expectEquals( 8070450532247928832L, geoLongMulLastValue(2147483647L)); 399 expectEquals( 0L, geoLongMulLastValue(-2147483648L)); 400 expectEquals( 8070450532247928832L, geoLongMulLastValue(9223372036854775807L)); 401 expectEquals( 0L, geoLongMulLastValue(-9223372036854775808L)); 402 403 float[] a = new float[16]; 404 narrowingSubscript(a); 405 for (int i = 0; i < 16; i++) { 406 expectEquals(2.0f, a[i]); 407 } 408 409 int[] xx = new int[2]; 410 int[] yy = new int[469]; 411 reduc(xx, yy); 412 expectEquals(-469, xx[0]); 413 expectEquals(-938, xx[1]); 414 for (int i = 0; i < 469; i++) { 415 expectEquals(2, yy[i]); 416 } 417 418 char[] aa = new char[23]; 419 String bb = "hello world how are you"; 420 string2Bytes(aa, bb); 421 for (int i = 0; i < aa.length; i++) { 422 expectEquals(aa[i], bb.charAt(i)); 423 } 424 425 envUsesInCond(); 426 427 short[] dd = new short[23]; 428 oneBoth(dd, aa); 429 for (int i = 0; i < aa.length; i++) { 430 expectEquals(aa[i], 1); 431 expectEquals(dd[i], 1); 432 } 433 434 xx[0] = 10; 435 byte[] bt = new byte[10]; 436 arrayInTripCount(xx, bt, 20); 437 for (int i = 0; i < bt.length; i++) { 438 expectEquals(40, bt[i]); 439 } 440 441 System.out.println("passed"); 442 } 443 expectEquals(int expected, int result)444 private static void expectEquals(int expected, int result) { 445 if (expected != result) { 446 throw new Error("Expected: " + expected + ", found: " + result); 447 } 448 } 449 expectEquals(long expected, long result)450 private static void expectEquals(long expected, long result) { 451 if (expected != result) { 452 throw new Error("Expected: " + expected + ", found: " + result); 453 } 454 } 455 expectEquals(float expected, float result)456 private static void expectEquals(float expected, float result) { 457 if (expected != result) { 458 throw new Error("Expected: " + expected + ", found: " + result); 459 } 460 } 461 } 462