1 /* 2 * Copyright (C) 2015 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 // Test on loop optimizations, in particular around common induction. 19 // 20 public class Main { 21 22 static int sResult; 23 24 // 25 // Various sequence variables used in bound checks. 26 // 27 28 /// CHECK-START: int Main.linear(int[]) BCE (before) 29 /// CHECK-DAG: BoundsCheck 30 // 31 /// CHECK-START: int Main.linear(int[]) BCE (after) 32 /// CHECK-NOT: BoundsCheck 33 /// CHECK-NOT: Deoptimize linear(int[] x)34 private static int linear(int[] x) { 35 int result = 0; 36 for (int i = 0; i < x.length; i++) { 37 result += x[i]; 38 } 39 return result; 40 } 41 42 /// CHECK-START: int Main.linearDown(int[]) BCE (before) 43 /// CHECK-DAG: BoundsCheck 44 // 45 /// CHECK-START: int Main.linearDown(int[]) BCE (after) 46 /// CHECK-NOT: BoundsCheck 47 /// CHECK-NOT: Deoptimize linearDown(int[] x)48 private static int linearDown(int[] x) { 49 int result = 0; 50 for (int i = x.length - 1; i >= 0; i--) { 51 result += x[i]; 52 } 53 return result; 54 } 55 56 /// CHECK-START: int Main.linearObscure(int[]) BCE (before) 57 /// CHECK-DAG: BoundsCheck 58 // 59 /// CHECK-START: int Main.linearObscure(int[]) BCE (after) 60 /// CHECK-NOT: BoundsCheck 61 /// CHECK-NOT: Deoptimize linearObscure(int[] x)62 private static int linearObscure(int[] x) { 63 int result = 0; 64 for (int i = x.length - 1; i >= 0; i--) { 65 int k = i + 5; 66 result += x[k - 5]; 67 } 68 return result; 69 } 70 71 /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (before) 72 /// CHECK-DAG: BoundsCheck 73 // 74 /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (after) 75 /// CHECK-NOT: BoundsCheck 76 /// CHECK-NOT: Deoptimize linearVeryObscure(int[] x)77 private static int linearVeryObscure(int[] x) { 78 int result = 0; 79 for (int i = 0; i < x.length; i++) { 80 int k = (-i) + (i << 5) + i - (32 * i) + 5 + (int) i; 81 result += x[k - 5]; 82 } 83 return result; 84 } 85 86 /// CHECK-START: int Main.hiddenStride(int[]) BCE (before) 87 /// CHECK-DAG: BoundsCheck 88 // 89 /// CHECK-START: int Main.hiddenStride(int[]) BCE (after) 90 /// CHECK-NOT: BoundsCheck 91 /// CHECK-NOT: Deoptimize hiddenStride(int[] a)92 static int hiddenStride(int[] a) { 93 int result = 0; 94 for (int i = 1; i <= 1; i++) { 95 // Obscured unit stride. 96 for (int j = 0; j < a.length; j += i) { 97 result += a[j]; 98 } 99 } 100 return result; 101 } 102 103 /// CHECK-START: int Main.linearWhile(int[]) BCE (before) 104 /// CHECK-DAG: BoundsCheck 105 // 106 /// CHECK-START: int Main.linearWhile(int[]) BCE (after) 107 /// CHECK-NOT: BoundsCheck 108 /// CHECK-NOT: Deoptimize linearWhile(int[] x)109 private static int linearWhile(int[] x) { 110 int i = 0; 111 int result = 0; 112 while (i < x.length) { 113 result += x[i++]; 114 } 115 return result; 116 } 117 118 /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (before) 119 /// CHECK-DAG: BoundsCheck 120 // 121 /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (after) 122 /// CHECK-NOT: BoundsCheck 123 /// CHECK-NOT: Deoptimize linearThreeWayPhi(int[] x)124 private static int linearThreeWayPhi(int[] x) { 125 int result = 0; 126 for (int i = 0; i < x.length; ) { 127 if (x[i] == 5) { 128 i++; 129 continue; 130 } 131 result += x[i++]; 132 } 133 return result; 134 } 135 136 /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (before) 137 /// CHECK-DAG: BoundsCheck 138 // 139 /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (after) 140 /// CHECK-NOT: BoundsCheck 141 /// CHECK-NOT: Deoptimize linearFourWayPhi(int[] x)142 private static int linearFourWayPhi(int[] x) { 143 int result = 0; 144 for (int i = 0; i < x.length; ) { 145 if (x[i] == 5) { 146 i++; 147 continue; 148 } else if (x[i] == 6) { 149 i++; 150 result += 7; 151 continue; 152 } 153 result += x[i++]; 154 } 155 return result; 156 } 157 158 /// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (before) 159 /// CHECK-DAG: BoundsCheck 160 // 161 /// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (after) 162 /// CHECK-NOT: BoundsCheck 163 /// CHECK-NOT: Deoptimize wrapAroundThenLinear(int[] x)164 private static int wrapAroundThenLinear(int[] x) { 165 // Loop with wrap around (length - 1, 0, 1, 2, ..). 166 int w = x.length - 1; 167 int result = 0; 168 for (int i = 0; i < x.length; i++) { 169 result += x[w]; 170 w = i; 171 } 172 return result; 173 } 174 175 /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (before) 176 /// CHECK-DAG: BoundsCheck 177 // 178 /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (after) 179 /// CHECK-NOT: BoundsCheck 180 /// CHECK-NOT: Deoptimize wrapAroundThenLinearThreeWayPhi(int[] x)181 private static int wrapAroundThenLinearThreeWayPhi(int[] x) { 182 // Loop with wrap around (length - 1, 0, 1, 2, ..). 183 int w = x.length - 1; 184 int result = 0; 185 for (int i = 0; i < x.length; ) { 186 if (x[w] == 1) { 187 w = i++; 188 continue; 189 } 190 result += x[w]; 191 w = i++; 192 } 193 return result; 194 } 195 196 /// CHECK-START: int[] Main.linearWithParameter(int) BCE (before) 197 /// CHECK-DAG: BoundsCheck 198 // 199 /// CHECK-START: int[] Main.linearWithParameter(int) BCE (after) 200 /// CHECK-NOT: BoundsCheck 201 /// CHECK-NOT: Deoptimize linearWithParameter(int n)202 private static int[] linearWithParameter(int n) { 203 int[] x = new int[n]; 204 for (int i = 0; i < n; i++) { 205 x[i] = i; 206 } 207 return x; 208 } 209 210 /// CHECK-START: int[] Main.linearCopy(int[]) BCE (before) 211 /// CHECK-DAG: BoundsCheck 212 // 213 /// CHECK-START: int[] Main.linearCopy(int[]) BCE (after) 214 /// CHECK-NOT: BoundsCheck 215 /// CHECK-NOT: Deoptimize linearCopy(int x[])216 private static int[] linearCopy(int x[]) { 217 int n = x.length; 218 int y[] = new int[n]; 219 for (int i = 0; i < n; i++) { 220 y[i] = x[i]; 221 } 222 return y; 223 } 224 225 /// CHECK-START: int Main.linearByTwo(int[]) BCE (before) 226 /// CHECK-DAG: BoundsCheck 227 /// CHECK-DAG: BoundsCheck 228 // 229 /// CHECK-START: int Main.linearByTwo(int[]) BCE (after) 230 /// CHECK-NOT: BoundsCheck 231 /// CHECK-NOT: Deoptimize linearByTwo(int x[])232 private static int linearByTwo(int x[]) { 233 int n = x.length / 2; 234 int result = 0; 235 for (int i = 0; i < n; i++) { 236 int ii = i << 1; 237 result += x[ii]; 238 result += x[ii + 1]; 239 } 240 return result; 241 } 242 243 /// CHECK-START: int Main.linearByTwoSkip1(int[]) BCE (before) 244 /// CHECK-DAG: BoundsCheck 245 // 246 /// CHECK-START: int Main.linearByTwoSkip1(int[]) BCE (after) 247 /// CHECK-NOT: BoundsCheck 248 /// CHECK-NOT: Deoptimize linearByTwoSkip1(int x[])249 private static int linearByTwoSkip1(int x[]) { 250 int result = 0; 251 for (int i = 0; i < x.length / 2; i++) { 252 result += x[2 * i]; 253 } 254 return result; 255 } 256 257 /// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (before) 258 /// CHECK-DAG: BoundsCheck 259 // 260 /// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (after) 261 /// CHECK-DAG: BoundsCheck 262 // 263 /// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (after) 264 /// CHECK-NOT: Deoptimize linearByTwoSkip2(int x[])265 private static int linearByTwoSkip2(int x[]) { 266 int result = 0; 267 // This case is not optimized. 268 for (int i = 0; i < x.length; i+=2) { 269 result += x[i]; 270 } 271 return result; 272 } 273 274 /// CHECK-START: int Main.linearWithCompoundStride() BCE (before) 275 /// CHECK-DAG: BoundsCheck 276 // 277 /// CHECK-START: int Main.linearWithCompoundStride() BCE (after) 278 /// CHECK-NOT: BoundsCheck 279 /// CHECK-NOT: Deoptimize linearWithCompoundStride()280 private static int linearWithCompoundStride() { 281 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }; 282 int result = 0; 283 for (int i = 0; i <= 12; ) { 284 i++; 285 result += x[i]; 286 i++; 287 } 288 return result; 289 } 290 291 /// CHECK-START: int Main.linearWithLargePositiveStride() BCE (before) 292 /// CHECK-DAG: BoundsCheck 293 // 294 /// CHECK-START: int Main.linearWithLargePositiveStride() BCE (after) 295 /// CHECK-NOT: BoundsCheck 296 /// CHECK-NOT: Deoptimize linearWithLargePositiveStride()297 private static int linearWithLargePositiveStride() { 298 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; 299 int result = 0; 300 int k = 0; 301 // Range analysis has no problem with a trip-count defined by a 302 // reasonably large positive stride far away from upper bound. 303 for (int i = 1; i <= 10 * 10000000 + 1; i += 10000000) { 304 result += x[k++]; 305 } 306 return result; 307 } 308 309 /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (before) 310 /// CHECK-DAG: BoundsCheck 311 // 312 /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (after) 313 /// CHECK-DAG: BoundsCheck 314 // 315 /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (after) 316 /// CHECK-NOT: Deoptimize linearWithVeryLargePositiveStride()317 private static int linearWithVeryLargePositiveStride() { 318 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; 319 int result = 0; 320 int k = 0; 321 // Range analysis conservatively bails due to potential of wrap-around 322 // arithmetic while computing the trip-count for this very large stride. 323 for (int i = 1; i < Integer.MAX_VALUE; i += 195225786) { 324 result += x[k++]; 325 } 326 return result; 327 } 328 329 /// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (before) 330 /// CHECK-DAG: BoundsCheck 331 // 332 /// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (after) 333 /// CHECK-NOT: BoundsCheck 334 /// CHECK-NOT: Deoptimize linearWithLargeNegativeStride()335 private static int linearWithLargeNegativeStride() { 336 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; 337 int result = 0; 338 int k = 0; 339 // Range analysis has no problem with a trip-count defined by a 340 // reasonably large negative stride far away from lower bound. 341 for (int i = -1; i >= -10 * 10000000 - 1; i -= 10000000) { 342 result += x[k++]; 343 } 344 return result; 345 } 346 347 /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (before) 348 /// CHECK-DAG: BoundsCheck 349 // 350 /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (after) 351 /// CHECK-DAG: BoundsCheck 352 // 353 /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (after) 354 /// CHECK-NOT: Deoptimize linearWithVeryLargeNegativeStride()355 private static int linearWithVeryLargeNegativeStride() { 356 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; 357 int result = 0; 358 int k = 0; 359 // Range analysis conservatively bails due to potential of wrap-around 360 // arithmetic while computing the trip-count for this very large stride. 361 for (int i = -2; i > Integer.MIN_VALUE; i -= 195225786) { 362 result += x[k++]; 363 } 364 return result; 365 } 366 367 /// CHECK-START: int Main.linearForNEUp() BCE (before) 368 /// CHECK-DAG: BoundsCheck 369 // 370 /// CHECK-START: int Main.linearForNEUp() BCE (after) 371 /// CHECK-NOT: BoundsCheck 372 /// CHECK-NOT: Deoptimize linearForNEUp()373 private static int linearForNEUp() { 374 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 375 int result = 0; 376 for (int i = 0; i != 10; i++) { 377 result += x[i]; 378 } 379 return result; 380 } 381 382 /// CHECK-START: int Main.linearForNEDown() BCE (before) 383 /// CHECK-DAG: BoundsCheck 384 // 385 /// CHECK-START: int Main.linearForNEDown() BCE (after) 386 /// CHECK-NOT: BoundsCheck 387 /// CHECK-NOT: Deoptimize linearForNEDown()388 private static int linearForNEDown() { 389 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 390 int result = 0; 391 for (int i = 9; i != -1; i--) { 392 result += x[i]; 393 } 394 return result; 395 } 396 397 /// CHECK-START: int Main.linearForNEArrayLengthUp(int[]) BCE (before) 398 /// CHECK-DAG: BoundsCheck 399 // 400 /// CHECK-START: int Main.linearForNEArrayLengthUp(int[]) BCE (after) 401 /// CHECK-NOT: BoundsCheck 402 /// CHECK-NOT: Deoptimize linearForNEArrayLengthUp(int[] x)403 private static int linearForNEArrayLengthUp(int[] x) { 404 int result = 0; 405 for (int i = 0; i != x.length; i++) { 406 result += x[i]; 407 } 408 return result; 409 } 410 411 /// CHECK-START: int Main.linearForNEArrayLengthDown(int[]) BCE (before) 412 /// CHECK-DAG: BoundsCheck 413 // 414 /// CHECK-START: int Main.linearForNEArrayLengthDown(int[]) BCE (after) 415 /// CHECK-NOT: BoundsCheck 416 /// CHECK-NOT: Deoptimize linearForNEArrayLengthDown(int[] x)417 private static int linearForNEArrayLengthDown(int[] x) { 418 int result = 0; 419 for (int i = x.length - 1; i != -1; i--) { 420 result += x[i]; 421 } 422 return result; 423 } 424 425 /// CHECK-START: int Main.linearDoWhileUp() BCE (before) 426 /// CHECK-DAG: BoundsCheck 427 // 428 /// CHECK-START: int Main.linearDoWhileUp() BCE (after) 429 /// CHECK-NOT: BoundsCheck 430 /// CHECK-NOT: Deoptimize linearDoWhileUp()431 private static int linearDoWhileUp() { 432 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 433 int result = 0; 434 int i = 0; 435 do { 436 result += x[i++]; 437 } while (i < 10); 438 return result; 439 } 440 441 /// CHECK-START: int Main.linearDoWhileDown() BCE (before) 442 /// CHECK-DAG: BoundsCheck 443 // 444 /// CHECK-START: int Main.linearDoWhileDown() BCE (after) 445 /// CHECK-NOT: BoundsCheck 446 /// CHECK-NOT: Deoptimize linearDoWhileDown()447 private static int linearDoWhileDown() { 448 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 449 int result = 0; 450 int i = 9; 451 do { 452 result += x[i--]; 453 } while (0 <= i); 454 return result; 455 } 456 457 /// CHECK-START: int Main.linearLong() BCE (before) 458 /// CHECK-DAG: BoundsCheck 459 // 460 /// CHECK-START: int Main.linearLong() BCE (after) 461 /// CHECK-NOT: BoundsCheck 462 /// CHECK-NOT: Deoptimize linearLong()463 private static int linearLong() { 464 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 465 int result = 0; 466 // Induction on constant interval is done in higher precision than necessary, 467 // but truncated at the use as subscript. 468 for (long i = 0; i < 10; i++) { 469 result += x[(int)i]; 470 } 471 return result; 472 } 473 474 /// CHECK-START: int Main.linearLongAlt(int[]) BCE (before) 475 /// CHECK-DAG: BoundsCheck 476 // 477 /// CHECK-START: int Main.linearLongAlt(int[]) BCE (after) 478 /// CHECK-NOT: BoundsCheck 479 /// CHECK-NOT: Deoptimize linearLongAlt(int[] x)480 private static int linearLongAlt(int[] x) { 481 int result = 0; 482 // Induction on array length is done in higher precision than necessary, 483 // but truncated at the use as subscript. 484 for (long i = 0; i < x.length; i++) { 485 result += x[(int)i]; 486 } 487 return result; 488 } 489 490 /// CHECK-START: int Main.linearShort() BCE (before) 491 /// CHECK-DAG: BoundsCheck 492 // 493 /// CHECK-START: int Main.linearShort() BCE (after) 494 /// CHECK-NOT: BoundsCheck 495 /// CHECK-NOT: Deoptimize linearShort()496 private static int linearShort() { 497 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 498 int result = 0; 499 // Induction is done in short precision, but fits. 500 for (short i = 0; i < 10; i++) { 501 result += x[i]; 502 } 503 return result; 504 } 505 506 /// CHECK-START: int Main.linearChar() BCE (before) 507 /// CHECK-DAG: BoundsCheck 508 // 509 /// CHECK-START: int Main.linearChar() BCE (after) 510 /// CHECK-NOT: BoundsCheck 511 /// CHECK-NOT: Deoptimize linearChar()512 private static int linearChar() { 513 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 514 int result = 0; 515 // Induction is done in char precision, but fits. 516 for (char i = 0; i < 10; i++) { 517 result += x[i]; 518 } 519 return result; 520 } 521 522 /// CHECK-START: int Main.linearByte() BCE (before) 523 /// CHECK-DAG: BoundsCheck 524 // 525 /// CHECK-START: int Main.linearByte() BCE (after) 526 /// CHECK-NOT: BoundsCheck 527 /// CHECK-NOT: Deoptimize linearByte()528 private static int linearByte() { 529 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 530 int result = 0; 531 // Induction is done in byte precision, but fits. 532 for (byte i = 0; i < 10; i++) { 533 result += x[i]; 534 } 535 return result; 536 } 537 538 /// CHECK-START: int Main.invariantFromPreLoop(int[], int) BCE (before) 539 /// CHECK-DAG: BoundsCheck 540 // 541 /// CHECK-START: int Main.invariantFromPreLoop(int[], int) BCE (after) 542 /// CHECK-NOT: BoundsCheck 543 /// CHECK-NOT: Deoptimize invariantFromPreLoop(int[] x, int y)544 private static int invariantFromPreLoop(int[] x, int y) { 545 int result = 0; 546 // Strange pre-loop that sets upper bound. 547 int hi; 548 while (true) { 549 y = y % 3; 550 hi = x.length; 551 if (y != 123) break; 552 } 553 for (int i = 0; i < hi; i++) { 554 result += x[i]; 555 } 556 return result; 557 } 558 559 /// CHECK-START: void Main.linearTriangularOnTwoArrayLengths(int) BCE (before) 560 /// CHECK-DAG: BoundsCheck 561 /// CHECK-DAG: BoundsCheck 562 // 563 /// CHECK-START: void Main.linearTriangularOnTwoArrayLengths(int) BCE (after) 564 /// CHECK-NOT: BoundsCheck 565 /// CHECK-NOT: Deoptimize linearTriangularOnTwoArrayLengths(int n)566 private static void linearTriangularOnTwoArrayLengths(int n) { 567 int[] a = new int[n]; 568 for (int i = 0; i < a.length; i++) { 569 int[] b = new int[i]; 570 for (int j = 0; j < b.length; j++) { 571 // Need to know j < b.length < a.length for static bce. 572 a[j] += 1; 573 // Need to know just j < b.length for static bce. 574 b[j] += 1; 575 } 576 verifyTriangular(a, b, i, n); 577 } 578 } 579 580 /// CHECK-START: void Main.linearTriangularOnOneArrayLength(int) BCE (before) 581 /// CHECK-DAG: BoundsCheck 582 /// CHECK-DAG: BoundsCheck 583 // 584 /// CHECK-START: void Main.linearTriangularOnOneArrayLength(int) BCE (after) 585 /// CHECK-NOT: BoundsCheck 586 /// CHECK-NOT: Deoptimize linearTriangularOnOneArrayLength(int n)587 private static void linearTriangularOnOneArrayLength(int n) { 588 int[] a = new int[n]; 589 for (int i = 0; i < a.length; i++) { 590 int[] b = new int[i]; 591 for (int j = 0; j < i; j++) { 592 // Need to know j < i < a.length for static bce. 593 a[j] += 1; 594 // Need to know just j < i for static bce. 595 b[j] += 1; 596 } 597 verifyTriangular(a, b, i, n); 598 } 599 } 600 601 /// CHECK-START: void Main.linearTriangularOnParameter(int) BCE (before) 602 /// CHECK-DAG: BoundsCheck 603 /// CHECK-DAG: BoundsCheck 604 // 605 /// CHECK-START: void Main.linearTriangularOnParameter(int) BCE (after) 606 /// CHECK-NOT: BoundsCheck 607 /// CHECK-NOT: Deoptimize linearTriangularOnParameter(int n)608 private static void linearTriangularOnParameter(int n) { 609 int[] a = new int[n]; 610 for (int i = 0; i < n; i++) { 611 int[] b = new int[i]; 612 for (int j = 0; j < i; j++) { 613 // Need to know j < i < n for static bce. 614 a[j] += 1; 615 // Need to know just j < i for static bce. 616 b[j] += 1; 617 } 618 verifyTriangular(a, b, i, n); 619 } 620 } 621 622 /// CHECK-START: void Main.linearTriangularStrictLower(int) BCE (before) 623 /// CHECK-DAG: BoundsCheck 624 /// CHECK-DAG: BoundsCheck 625 /// CHECK-DAG: BoundsCheck 626 /// CHECK-DAG: BoundsCheck 627 // 628 /// CHECK-START: void Main.linearTriangularStrictLower(int) BCE (after) 629 /// CHECK-NOT: BoundsCheck 630 /// CHECK-NOT: Deoptimize linearTriangularStrictLower(int n)631 private static void linearTriangularStrictLower(int n) { 632 int[] a = new int[n]; 633 for (int i = 0; i < n; i++) { 634 for (int j = 0; j < i; j++) { 635 a[j] += 1; 636 } 637 for (int j = i - 1; j >= 0; j--) { 638 a[j] += 1; 639 } 640 for (int j = i; j < n; j++) { 641 a[j] += 1; 642 } 643 for (int j = n - 1; j >= i; j--) { 644 a[j] += 1; 645 } 646 } 647 verifyTriangular(a); 648 } 649 650 /// CHECK-START: void Main.linearTriangularStrictUpper(int) BCE (before) 651 /// CHECK-DAG: BoundsCheck 652 /// CHECK-DAG: BoundsCheck 653 /// CHECK-DAG: BoundsCheck 654 /// CHECK-DAG: BoundsCheck 655 // 656 /// CHECK-START: void Main.linearTriangularStrictUpper(int) BCE (after) 657 /// CHECK-NOT: BoundsCheck 658 /// CHECK-NOT: Deoptimize linearTriangularStrictUpper(int n)659 private static void linearTriangularStrictUpper(int n) { 660 int[] a = new int[n]; 661 for (int i = 0; i < n; i++) { 662 for (int j = 0; j <= i; j++) { 663 a[j] += 1; 664 } 665 for (int j = i; j >= 0; j--) { 666 a[j] += 1; 667 } 668 for (int j = i + 1; j < n; j++) { 669 a[j] += 1; 670 } 671 for (int j = n - 1; j >= i + 1; j--) { 672 a[j] += 1; 673 } 674 } 675 verifyTriangular(a); 676 } 677 678 // Verifier for triangular loops. verifyTriangular(int[] a, int[] b, int m, int n)679 private static void verifyTriangular(int[] a, int[] b, int m, int n) { 680 expectEquals(n, a.length); 681 for (int i = 0, k = m; i < n; i++) { 682 expectEquals(a[i], k); 683 if (k > 0) k--; 684 } 685 expectEquals(m, b.length); 686 for (int i = 0; i < m; i++) { 687 expectEquals(b[i], 1); 688 } 689 } 690 691 // Verifier for triangular loops. verifyTriangular(int[] a)692 private static void verifyTriangular(int[] a) { 693 int n = a.length; 694 for (int i = 0; i < n; i++) { 695 expectEquals(a[i], n + n); 696 } 697 } 698 699 /// CHECK-START: int[] Main.linearTriangularOOB() BCE (before) 700 /// CHECK-DAG: BoundsCheck 701 // 702 /// CHECK-START: int[] Main.linearTriangularOOB() BCE (after) 703 /// CHECK-DAG: BoundsCheck 704 // 705 /// CHECK-START: int[] Main.linearTriangularOOB() BCE (after) 706 /// CHECK-NOT: Deoptimize linearTriangularOOB()707 private static int[] linearTriangularOOB() { 708 int[] a = new int[200]; 709 try { 710 for (int i = 0; i < 200; i++) { 711 // Lower bound must be recognized as lower precision induction with arithmetic 712 // wrap-around to -128 when i exceeds 127. 713 for (int j = (byte) i; j < 200; j++) { 714 a[j] += 1; 715 } 716 } 717 } catch (ArrayIndexOutOfBoundsException e) { 718 return a; 719 } 720 return null; // failure if this is reached 721 } 722 723 // 724 // Verifier. 725 // 726 main(String[] args)727 public static void main(String[] args) { 728 int[] empty = { }; 729 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 730 731 // Linear and wrap-around. 732 expectEquals(0, linear(empty)); 733 expectEquals(55, linear(x)); 734 expectEquals(0, linearDown(empty)); 735 expectEquals(55, linearDown(x)); 736 expectEquals(0, linearObscure(empty)); 737 expectEquals(55, linearObscure(x)); 738 expectEquals(0, linearVeryObscure(empty)); 739 expectEquals(55, linearVeryObscure(x)); 740 expectEquals(0, hiddenStride(empty)); 741 expectEquals(55, hiddenStride(x)); 742 expectEquals(0, linearWhile(empty)); 743 expectEquals(55, linearWhile(x)); 744 expectEquals(0, linearThreeWayPhi(empty)); 745 expectEquals(50, linearThreeWayPhi(x)); 746 expectEquals(0, linearFourWayPhi(empty)); 747 expectEquals(51, linearFourWayPhi(x)); 748 expectEquals(0, wrapAroundThenLinear(empty)); 749 expectEquals(55, wrapAroundThenLinear(x)); 750 expectEquals(0, wrapAroundThenLinearThreeWayPhi(empty)); 751 expectEquals(54, wrapAroundThenLinearThreeWayPhi(x)); 752 753 // Linear with parameter. 754 sResult = 0; 755 try { 756 linearWithParameter(-1); 757 } catch (NegativeArraySizeException e) { 758 sResult = 1; 759 } 760 expectEquals(1, sResult); 761 for (int n = 0; n < 32; n++) { 762 int[] r = linearWithParameter(n); 763 expectEquals(n, r.length); 764 for (int i = 0; i < n; i++) { 765 expectEquals(i, r[i]); 766 } 767 } 768 769 // Linear copy. 770 expectEquals(0, linearCopy(empty).length); 771 { 772 int[] r = linearCopy(x); 773 expectEquals(x.length, r.length); 774 for (int i = 0; i < x.length; i++) { 775 expectEquals(x[i], r[i]); 776 } 777 } 778 779 // Linear with non-unit strides. 780 expectEquals(55, linearByTwo(x)); 781 expectEquals(25, linearByTwoSkip1(x)); 782 expectEquals(25, linearByTwoSkip2(x)); 783 expectEquals(56, linearWithCompoundStride()); 784 expectEquals(66, linearWithLargePositiveStride()); 785 expectEquals(66, linearWithVeryLargePositiveStride()); 786 expectEquals(66, linearWithLargeNegativeStride()); 787 expectEquals(66, linearWithVeryLargeNegativeStride()); 788 789 // Special forms. 790 expectEquals(55, linearForNEUp()); 791 expectEquals(55, linearForNEDown()); 792 expectEquals(55, linearForNEArrayLengthUp(x)); 793 expectEquals(55, linearForNEArrayLengthDown(x)); 794 expectEquals(55, linearDoWhileUp()); 795 expectEquals(55, linearDoWhileDown()); 796 expectEquals(55, linearLong()); 797 expectEquals(55, linearLongAlt(x)); 798 expectEquals(55, linearShort()); 799 expectEquals(55, linearChar()); 800 expectEquals(55, linearByte()); 801 expectEquals(55, invariantFromPreLoop(x, 1)); 802 linearTriangularOnTwoArrayLengths(10); 803 linearTriangularOnOneArrayLength(10); 804 linearTriangularOnParameter(10); 805 linearTriangularStrictLower(10); 806 linearTriangularStrictUpper(10); 807 { 808 int[] t = linearTriangularOOB(); 809 for (int i = 0; i < 200; i++) { 810 expectEquals(i <= 127 ? i + 1 : 128, t[i]); 811 } 812 } 813 814 System.out.println("passed"); 815 } 816 expectEquals(int expected, int result)817 private static void expectEquals(int expected, int result) { 818 if (expected != result) { 819 throw new Error("Expected: " + expected + ", found: " + result); 820 } 821 } 822 } 823