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 * Tests on loop optimizations related to induction. 19 */ 20 public class Main { 21 22 static int[] a = new int[10]; 23 24 static int[] novec = new int[20]; // to prevent vectorization 25 26 /// CHECK-START: void Main.deadSingleLoop() loop_optimization (before) 27 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none 28 // 29 /// CHECK-START: void Main.deadSingleLoop() loop_optimization (after) 30 /// CHECK-NOT: Phi 31 static void deadSingleLoop() { 32 for (int i = 0; i < 4; i++) { 33 } 34 } 35 36 /// CHECK-START: void Main.deadSingleLoop() loop_optimization (before) 37 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none 38 // 39 /// CHECK-START: void Main.deadSingleLoop() loop_optimization (after) 40 /// CHECK-NOT: Phi 41 static void deadSingleLoopN(int n) { 42 for (int i = 0; i < n; i++) { 43 } 44 } 45 46 /// CHECK-START: void Main.potentialInfiniteLoop(int) loop_optimization (before) 47 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none 48 // 49 /// CHECK-START: void Main.potentialInfiniteLoop(int) loop_optimization (after) 50 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none 51 static void potentialInfiniteLoop(int n) { 52 for (int i = 0; i <= n; i++) { // loops forever when n = MAX_INT 53 } 54 } 55 56 /// CHECK-START: void Main.deadNestedLoops() loop_optimization (before) 57 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 58 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop>> 59 // 60 /// CHECK-START: void Main.deadNestedLoops() loop_optimization (after) 61 /// CHECK-NOT: Phi 62 static void deadNestedLoops() { 63 for (int i = 0; i < 4; i++) { 64 for (int j = 0; j < 4; j++) { 65 } 66 } 67 } 68 69 /// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (before) 70 /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none 71 /// CHECK-DAG: Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>> 72 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop2>> 73 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop2>> 74 /// CHECK-DAG: Phi loop:<<Loop3:B\d+>> outer_loop:<<Loop1>> 75 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop3>> 76 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none 77 // 78 /// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (after) 79 /// CHECK-NOT: Phi 80 static void deadNestedAndFollowingLoops() { 81 for (int i = 0; i < 4; i++) { 82 for (int j = 0; j < 4; j++) { 83 for (int k = 0; k < 4; k++) { 84 } 85 for (int k = 0; k < 4; k++) { 86 } 87 } 88 for (int j = 0; j < 4; j++) { 89 for (int k = 0; k < 4; k++) { 90 } 91 } 92 } 93 for (int i = 0; i < 4; i++) { 94 } 95 } 96 97 /// CHECK-START: void Main.deadConditional(int) loop_optimization (before) 98 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none 99 // 100 /// CHECK-START: void Main.deadConditional(int) loop_optimization (after) 101 /// CHECK-NOT: Phi 102 public static void deadConditional(int n) { 103 int k = 0; 104 int m = 0; 105 for (int i = 0; i < n; i++) { 106 if (i == 3) 107 k = i; 108 else 109 m = i; 110 } 111 } 112 113 /// CHECK-START: void Main.deadConditionalCycle(int) loop_optimization (before) 114 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 115 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 116 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 117 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 118 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 119 // 120 /// CHECK-START: void Main.deadConditionalCycle(int) loop_optimization (after) 121 /// CHECK-NOT: Phi 122 public static void deadConditionalCycle(int n) { 123 int k = 0; 124 int m = 0; 125 for (int i = 0; i < n; i++) { 126 if (i == 3) 127 k--; 128 else 129 m++; 130 } 131 } 132 133 134 /// CHECK-START: void Main.deadInduction() loop_optimization (before) 135 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 136 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 137 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 138 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 139 // 140 /// CHECK-START: void Main.deadInduction() loop_optimization (after) 141 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 142 /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none 143 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 144 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 145 static void deadInduction() { 146 int dead = 0; 147 for (int i = 0; i < a.length; i++) { 148 a[i] = novec[2 * i] + 1; 149 dead += 5; 150 } 151 } 152 153 /// CHECK-START: void Main.deadManyInduction() loop_optimization (before) 154 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 155 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 156 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 157 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 158 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 159 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 160 // 161 /// CHECK-START: void Main.deadManyInduction() loop_optimization (after) 162 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 163 /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none 164 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 165 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 166 static void deadManyInduction() { 167 int dead1 = 0, dead2 = 1, dead3 = 3; 168 for (int i = 0; i < a.length; i++) { 169 dead1 += 5; 170 a[i] = novec[2 * i] + 2; 171 dead2 += 10; 172 dead3 += 100; 173 } 174 } 175 176 /// CHECK-START: void Main.deadSequence() loop_optimization (before) 177 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 178 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 179 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 180 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 181 // 182 /// CHECK-START: void Main.deadSequence() loop_optimization (after) 183 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 184 /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none 185 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 186 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 187 static void deadSequence() { 188 int dead = 0; 189 for (int i = 0; i < a.length; i++) { 190 a[i] = novec[2 * i] + 3; 191 // Increment value defined inside loop, 192 // but sequence itself not used anywhere. 193 dead += i; 194 } 195 } 196 197 /// CHECK-START: void Main.deadCycleWithException(int) loop_optimization (before) 198 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 199 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none 200 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 201 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 202 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 203 /// CHECK-NOT: BoundsCheck 204 // 205 /// CHECK-START: void Main.deadCycleWithException(int) loop_optimization (after) 206 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 207 /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none 208 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 209 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 210 /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none 211 static void deadCycleWithException(int k) { 212 int dead = 0; 213 for (int i = 0; i < a.length; i++) { 214 a[i] = novec[2 * i] + 4; 215 // Increment value of dead cycle may throw exception. Dynamic 216 // BCE takes care of the bounds check though, which enables 217 // removing the ArrayGet after removing the dead cycle. 218 dead += a[k]; 219 } 220 } 221 222 /// CHECK-START: int Main.closedFormInductionUp() loop_optimization (before) 223 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 224 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 225 /// CHECK-DAG: Return [<<Phi1>>] loop:none 226 // 227 /// CHECK-START: int Main.closedFormInductionUp() loop_optimization (after) 228 /// CHECK-NOT: Phi 229 // 230 /// CHECK-START: int Main.closedFormInductionUp() instruction_simplifier$after_bce (after) 231 /// CHECK-DAG: <<Int:i\d+>> IntConstant 12395 loop:none 232 /// CHECK-DAG: Return [<<Int>>] loop:none 233 static int closedFormInductionUp() { 234 int closed = 12345; 235 for (int i = 0; i < 10; i++) { 236 closed += 5; 237 } 238 return closed; // only needs last value 239 } 240 241 /// CHECK-START: int Main.closedFormInductionInAndDown(int) loop_optimization (before) 242 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 243 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 244 /// CHECK-DAG: Return [<<Phi2>>] loop:none 245 // 246 /// CHECK-START: int Main.closedFormInductionInAndDown(int) loop_optimization (after) 247 /// CHECK-NOT: Phi 248 // 249 /// CHECK-START: int Main.closedFormInductionInAndDown(int) instruction_simplifier$after_bce (after) 250 /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none 251 /// CHECK-DAG: <<Int:i\d+>> IntConstant -50 loop:none 252 /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Par>>] loop:none 253 /// CHECK-DAG: Return [<<Add>>] loop:none 254 static int closedFormInductionInAndDown(int closed) { 255 for (int i = 0; i < 10; i++) { 256 closed -= 5; 257 } 258 return closed; // only needs last value 259 } 260 261 /// CHECK-START: int Main.closedFormInductionTrivialIf() loop_optimization (before) 262 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 263 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 264 /// CHECK-DAG: Select loop:<<Loop>> outer_loop:none 265 /// CHECK-DAG: Return [<<Phi1>>] loop:none 266 // 267 /// CHECK-START: int Main.closedFormInductionTrivialIf() loop_optimization (after) 268 /// CHECK-NOT: Phi 269 /// CHECK-NOT: Select 270 // 271 /// CHECK-START: int Main.closedFormInductionTrivialIf() instruction_simplifier$after_bce (after) 272 /// CHECK-DAG: <<Int:i\d+>> IntConstant 81 loop:none 273 /// CHECK-DAG: Return [<<Int>>] loop:none 274 static int closedFormInductionTrivialIf() { 275 int closed = 11; 276 for (int i = 0; i < 10; i++) { 277 // Trivial if becomes trivial select at HIR level. 278 // Make sure this is still recognized as induction. 279 if (i < 5) { 280 closed += 7; 281 } else { 282 closed += 7; 283 } 284 } 285 return closed; // only needs last value 286 } 287 288 /// CHECK-START: int Main.closedFormNested() loop_optimization (before) 289 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none 290 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none 291 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>> 292 /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:<<Loop1>> 293 /// CHECK-DAG: Return [<<Phi1>>] loop:none 294 // 295 /// CHECK-START: int Main.closedFormNested() loop_optimization (after) 296 /// CHECK-NOT: Phi 297 // 298 /// CHECK-START: int Main.closedFormNested() instruction_simplifier$after_bce (after) 299 /// CHECK-DAG: <<Int:i\d+>> IntConstant 100 loop:none 300 /// CHECK-DAG: Return [<<Int>>] loop:none 301 static int closedFormNested() { 302 int closed = 0; 303 for (int i = 0; i < 10; i++) { 304 for (int j = 0; j < 10; j++) { 305 closed++; 306 } 307 } 308 return closed; // only needs last-value 309 } 310 311 /// CHECK-START: int Main.closedFormNestedAlt() loop_optimization (before) 312 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none 313 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none 314 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>> 315 /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:<<Loop1>> 316 /// CHECK-DAG: Return [<<Phi1>>] loop:none 317 // 318 /// CHECK-START: int Main.closedFormNestedAlt() loop_optimization (after) 319 /// CHECK-NOT: Phi 320 // 321 /// CHECK-START: int Main.closedFormNestedAlt() instruction_simplifier$after_bce (after) 322 /// CHECK-DAG: <<Int:i\d+>> IntConstant 15082 loop:none 323 /// CHECK-DAG: Return [<<Int>>] loop:none 324 static int closedFormNestedAlt() { 325 int closed = 12345; 326 for (int i = 0; i < 17; i++) { 327 for (int j = 0; j < 23; j++) { 328 closed += 7; 329 } 330 } 331 return closed; // only needs last-value 332 } 333 334 // TODO: taken test around closed form? 335 static int closedFormInductionUpN(int n) { 336 int closed = 12345; 337 for (int i = 0; i < n; i++) { 338 closed += 5; 339 } 340 return closed; // only needs last value 341 } 342 343 // TODO: taken test around closed form? 344 static int closedFormInductionInAndDownN(int closed, int n) { 345 for (int i = 0; i < n; i++) { 346 closed -= 5; 347 } 348 return closed; // only needs last value 349 } 350 351 // TODO: move closed form even further out? 352 static int closedFormNestedN(int n) { 353 int closed = 0; 354 for (int i = 0; i < n; i++) { 355 for (int j = 0; j < 10; j++) { 356 closed++; 357 } 358 } 359 return closed; // only needs last-value 360 } 361 362 // TODO: move closed form even further out? 363 static int closedFormNestedNAlt(int n) { 364 int closed = 12345; 365 for (int i = 0; i < n; i++) { 366 for (int j = 0; j < 23; j++) { 367 closed += 7; 368 } 369 } 370 return closed; // only needs last-value 371 } 372 373 // TODO: move closed form even further out? 374 static int closedFormNestedMN(int m, int n) { 375 int closed = 0; 376 for (int i = 0; i < m; i++) { 377 for (int j = 0; j < n; j++) { 378 closed++; 379 } 380 } 381 return closed; // only needs last-value 382 } 383 384 // TODO: move closed form even further out? 385 static int closedFormNestedMNAlt(int m, int n) { 386 int closed = 12345; 387 for (int i = 0; i < m; i++) { 388 for (int j = 0; j < n; j++) { 389 closed += 7; 390 } 391 } 392 return closed; // only needs last-value 393 } 394 395 /// CHECK-START: int Main.mainIndexReturned() loop_optimization (before) 396 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:{{B\d+}} outer_loop:none 397 /// CHECK-DAG: Return [<<Phi>>] loop:none 398 // 399 /// CHECK-START: int Main.mainIndexReturned() loop_optimization (after) 400 /// CHECK-NOT: Phi 401 // 402 /// CHECK-START: int Main.mainIndexReturned() instruction_simplifier$after_bce (after) 403 /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none 404 /// CHECK-DAG: Return [<<Int>>] loop:none 405 static int mainIndexReturned() { 406 int i; 407 for (i = 0; i < 10; i++); 408 return i; 409 } 410 411 /// CHECK-START: int Main.periodicReturned9() loop_optimization (before) 412 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 413 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 414 /// CHECK-DAG: Return [<<Phi1>>] loop:none 415 // 416 /// CHECK-START: int Main.periodicReturned9() loop_optimization (after) 417 /// CHECK-NOT: Phi 418 // 419 /// CHECK-START: int Main.periodicReturned9() instruction_simplifier$after_bce (after) 420 /// CHECK-DAG: <<Int:i\d+>> IntConstant 1 loop:none 421 /// CHECK-DAG: Return [<<Int>>] loop:none 422 static int periodicReturned9() { 423 int k = 0; 424 for (int i = 0; i < 9; i++) { 425 k = 1 - k; 426 } 427 return k; 428 } 429 430 /// CHECK-START: int Main.periodicReturned10() loop_optimization (before) 431 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 432 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 433 /// CHECK-DAG: Return [<<Phi1>>] loop:none 434 // 435 /// CHECK-START: int Main.periodicReturned10() loop_optimization (after) 436 /// CHECK-NOT: Phi 437 // 438 /// CHECK-START: int Main.periodicReturned10() instruction_simplifier$after_bce (after) 439 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none 440 /// CHECK-DAG: Return [<<Int>>] loop:none 441 static int periodicReturned10() { 442 int k = 0; 443 for (int i = 0; i < 10; i++) { 444 k = 1 - k; 445 } 446 return k; 447 } 448 449 /// CHECK-START: int Main.getSum21() loop_optimization (before) 450 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 451 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 452 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop>> outer_loop:none 453 /// CHECK-DAG: Return [<<Phi2>>] loop:none 454 // 455 /// CHECK-START: int Main.getSum21() loop_optimization (after) 456 /// CHECK-NOT: Phi 457 // 458 /// CHECK-START: int Main.getSum21() instruction_simplifier$after_bce (after) 459 /// CHECK-DAG: <<Int:i\d+>> IntConstant 21 loop:none 460 /// CHECK-DAG: Return [<<Int>>] loop:none 461 private static int getSum21() { 462 int k = 0; 463 int sum = 0; 464 for (int i = 0; i < 6; i++) { 465 k++; 466 sum += k; 467 } 468 return sum; 469 } 470 471 // Ensure double induction does not "overshoot" the subscript range. 472 private static int getIncr2(int[] arr) { 473 for (int i = 0; i < 12; ) { 474 arr[i++] = 30; 475 arr[i++] = 29; 476 } 477 int sum = 0; 478 for (int i = 0; i < 12; i++) { 479 sum += arr[i]; 480 } 481 return sum; 482 } 483 484 // TODO: handle as closed/empty eventually? 485 static int mainIndexReturnedN(int n) { 486 int i; 487 for (i = 0; i < n; i++); 488 return i; 489 } 490 491 // TODO: handle as closed/empty eventually? 492 static int mainIndexShort1(short s) { 493 int i = 0; 494 for (i = 0; i < s; i++) { } 495 return i; 496 } 497 498 // TODO: handle as closed/empty eventually? 499 static int mainIndexShort2(short s) { 500 int i = 0; 501 for (i = 0; s > i; i++) { } 502 return i; 503 } 504 505 /// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (before) 506 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 507 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 508 /// CHECK-DAG: Return [<<Phi1>>] loop:none 509 // 510 /// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (after) 511 /// CHECK-NOT: Phi 512 static int periodicReturnedN(int n) { 513 int k = 0; 514 for (int i = 0; i < n; i++) { 515 k = 1 - k; 516 } 517 return k; 518 } 519 520 // If ever replaced by closed form, last value should be correct! 521 private static int getSumN(int n) { 522 int k = 0; 523 int sum = 0; 524 for (int i = 0; i < n; i++) { 525 k++; 526 sum += k; 527 } 528 return sum; 529 } 530 531 // If ever replaced by closed form, last value should be correct! 532 private static int closedTwice() { 533 int closed = 0; 534 for (int i = 0; i < 10; i++) { 535 closed++; 536 } 537 // Closed form of first loop defines trip count of second loop. 538 int other_closed = 0; 539 for (int i = 0; i < closed; i++) { 540 other_closed++; 541 } 542 return other_closed; 543 } 544 545 /// CHECK-START: int Main.closedFeed() loop_optimization (before) 546 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none 547 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none 548 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:none 549 /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:none 550 /// CHECK-DAG: Return [<<Phi3>>] loop:none 551 /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>" 552 // 553 /// CHECK-START: int Main.closedFeed() loop_optimization (after) 554 /// CHECK-NOT: Phi 555 // 556 /// CHECK-START: int Main.closedFeed() instruction_simplifier$after_bce (after) 557 /// CHECK-DAG: <<Int:i\d+>> IntConstant 20 loop:none 558 /// CHECK-DAG: Return [<<Int>>] loop:none 559 private static int closedFeed() { 560 int closed = 0; 561 for (int i = 0; i < 10; i++) { 562 closed++; 563 } 564 // Closed form of first loop feeds into initial value of second loop, 565 // used when generating closed form for the latter. 566 for (int i = 0; i < 10; i++) { 567 closed++; 568 } 569 return closed; 570 } 571 572 /// CHECK-START: int Main.closedLargeUp() loop_optimization (before) 573 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 574 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 575 /// CHECK-DAG: Return [<<Phi1>>] loop:none 576 // 577 /// CHECK-START: int Main.closedLargeUp() loop_optimization (after) 578 /// CHECK-NOT: Phi 579 // 580 /// CHECK-START: int Main.closedLargeUp() instruction_simplifier$after_bce (after) 581 /// CHECK-DAG: <<Int:i\d+>> IntConstant -10 loop:none 582 /// CHECK-DAG: Return [<<Int>>] loop:none 583 private static int closedLargeUp() { 584 int closed = 0; 585 for (int i = 0; i < 10; i++) { 586 closed += 0x7fffffff; 587 } 588 return closed; 589 } 590 591 /// CHECK-START: int Main.closedLargeDown() loop_optimization (before) 592 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 593 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 594 /// CHECK-DAG: Return [<<Phi1>>] loop:none 595 // 596 /// CHECK-START: int Main.closedLargeDown() loop_optimization (after) 597 /// CHECK-NOT: Phi 598 // 599 /// CHECK-START: int Main.closedLargeDown() instruction_simplifier$after_bce (after) 600 /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none 601 /// CHECK-DAG: Return [<<Int>>] loop:none 602 private static int closedLargeDown() { 603 int closed = 0; 604 for (int i = 0; i < 10; i++) { 605 closed -= 0x7fffffff; 606 } 607 return closed; 608 } 609 610 /// CHECK-START: int Main.waterFall() loop_optimization (before) 611 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none 612 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:none 613 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop3:B\d+>> outer_loop:none 614 /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop4:B\d+>> outer_loop:none 615 /// CHECK-DAG: <<Phi5:i\d+>> Phi loop:<<Loop5:B\d+>> outer_loop:none 616 /// CHECK-DAG: Return [<<Phi5>>] loop:none 617 // 618 /// CHECK-START: int Main.waterFall() loop_optimization (after) 619 /// CHECK-NOT: Phi 620 // 621 /// CHECK-START: int Main.waterFall() instruction_simplifier$after_bce (after) 622 /// CHECK-DAG: <<Int:i\d+>> IntConstant 50 loop:none 623 /// CHECK-DAG: Return [<<Int>>] loop:none 624 private static int waterFall() { 625 int i = 0; 626 for (; i < 10; i++); 627 for (; i < 20; i++); 628 for (; i < 30; i++); 629 for (; i < 40; i++); 630 for (; i < 50; i++); 631 return i; // this should become just 50 632 } 633 634 /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (before) 635 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 636 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 637 /// CHECK-DAG: Return [<<Phi1>>] loop:none 638 // 639 /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (after) 640 /// CHECK-NOT: Phi 641 // 642 /// CHECK-START: boolean Main.periodicBoolIdiom1() instruction_simplifier$after_bce (after) 643 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none 644 /// CHECK-DAG: Return [<<Int>>] loop:none 645 private static boolean periodicBoolIdiom1() { 646 boolean x = true; 647 for (int i = 0; i < 7; i++) { 648 x = !x; 649 } 650 return x; 651 } 652 653 /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (before) 654 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 655 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 656 /// CHECK-DAG: Return [<<Phi1>>] loop:none 657 // 658 /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (after) 659 /// CHECK-NOT: Phi 660 // 661 /// CHECK-START: boolean Main.periodicBoolIdiom2() instruction_simplifier$after_bce (after) 662 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none 663 /// CHECK-DAG: Return [<<Int>>] loop:none 664 private static boolean periodicBoolIdiom2() { 665 boolean x = true; 666 for (int i = 0; i < 7; i++) { 667 x = (x != true); 668 } 669 return x; 670 } 671 672 /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (before) 673 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 674 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 675 /// CHECK-DAG: Return [<<Phi1>>] loop:none 676 // 677 /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (after) 678 /// CHECK-NOT: Phi 679 // 680 /// CHECK-START: boolean Main.periodicBoolIdiom3() instruction_simplifier$after_bce (after) 681 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none 682 /// CHECK-DAG: Return [<<Int>>] loop:none 683 private static boolean periodicBoolIdiom3() { 684 boolean x = true; 685 for (int i = 0; i < 7; i++) { 686 x = (x == false); 687 } 688 return x; 689 } 690 691 /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (before) 692 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 693 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 694 /// CHECK-DAG: Return [<<Phi2>>] loop:none 695 // 696 /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (after) 697 /// CHECK-NOT: Phi 698 private static boolean periodicBoolIdiom1N(boolean x, int n) { 699 for (int i = 0; i < n; i++) { 700 x = !x; 701 } 702 return x; 703 } 704 705 /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (before) 706 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 707 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 708 /// CHECK-DAG: Return [<<Phi2>>] loop:none 709 // 710 /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (after) 711 /// CHECK-NOT: Phi 712 private static boolean periodicBoolIdiom2N(boolean x, int n) { 713 for (int i = 0; i < n; i++) { 714 x = (x != true); 715 } 716 return x; 717 } 718 719 /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (before) 720 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 721 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 722 /// CHECK-DAG: Return [<<Phi2>>] loop:none 723 // 724 /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (after) 725 /// CHECK-NOT: Phi 726 private static boolean periodicBoolIdiom3N(boolean x, int n) { 727 for (int i = 0; i < n; i++) { 728 x = (x == false); 729 } 730 return x; 731 } 732 733 /// CHECK-START: float Main.periodicFloat10() loop_optimization (before) 734 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 735 /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none 736 /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none 737 /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none 738 /// CHECK-DAG: Return [<<Phi2>>] loop:none 739 // 740 /// CHECK-START: float Main.periodicFloat10() loop_optimization (after) 741 /// CHECK-NOT: Phi 742 // 743 /// CHECK-START: float Main.periodicFloat10() loop_optimization (after) 744 /// CHECK-DAG: <<Float:f\d+>> FloatConstant 2 loop:none 745 /// CHECK-DAG: Return [<<Float>>] loop:none 746 private static float periodicFloat10() { 747 float r = 4.5f; 748 float s = 2.0f; 749 float t = -1.0f; 750 for (int i = 0; i < 10; i++) { 751 float tmp = t; t = r; r = s; s = tmp; 752 } 753 return r; 754 } 755 756 /// CHECK-START: float Main.periodicFloat11() loop_optimization (before) 757 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 758 /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none 759 /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none 760 /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none 761 /// CHECK-DAG: Return [<<Phi2>>] loop:none 762 // 763 /// CHECK-START: float Main.periodicFloat11() loop_optimization (after) 764 /// CHECK-NOT: Phi 765 // 766 /// CHECK-START: float Main.periodicFloat11() loop_optimization (after) 767 /// CHECK-DAG: <<Float:f\d+>> FloatConstant -1 loop:none 768 /// CHECK-DAG: Return [<<Float>>] loop:none 769 private static float periodicFloat11() { 770 float r = 4.5f; 771 float s = 2.0f; 772 float t = -1.0f; 773 for (int i = 0; i < 11; i++) { 774 float tmp = t; t = r; r = s; s = tmp; 775 } 776 return r; 777 } 778 779 /// CHECK-START: float Main.periodicFloat12() loop_optimization (before) 780 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 781 /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none 782 /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none 783 /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none 784 /// CHECK-DAG: Return [<<Phi2>>] loop:none 785 // 786 /// CHECK-START: float Main.periodicFloat12() loop_optimization (after) 787 /// CHECK-NOT: Phi 788 // 789 /// CHECK-START: float Main.periodicFloat12() loop_optimization (after) 790 /// CHECK-DAG: <<Float:f\d+>> FloatConstant 4.5 loop:none 791 /// CHECK-DAG: Return [<<Float>>] loop:none 792 private static float periodicFloat12() { 793 float r = 4.5f; 794 float s = 2.0f; 795 float t = -1.0f; 796 for (int i = 0; i < 12; i++) { 797 float tmp = t; t = r; r = s; s = tmp; 798 } 799 return r; 800 } 801 802 private static int exceptionExitBeforeAdd() { 803 int k = 0; 804 try { 805 for (int i = 0; i < 10; i++) { 806 a[i] = 0; 807 k += 10; // increment last 808 } 809 } catch(Exception e) { 810 // Flag error by returning current 811 // value of k negated. 812 return -k-1; 813 } 814 return k; 815 } 816 817 private static int exceptionExitAfterAdd() { 818 int k = 0; 819 try { 820 for (int i = 0; i < 10; i++) { 821 k += 10; // increment first 822 a[i] = 0; 823 } 824 } catch(Exception e) { 825 // Flag error by returning current 826 // value of k negated. 827 return -k-1; 828 } 829 return k; 830 } 831 832 public static void main(String[] args) { 833 deadSingleLoop(); 834 deadSingleLoopN(4); 835 potentialInfiniteLoop(4); 836 deadNestedLoops(); 837 deadNestedAndFollowingLoops(); 838 deadConditional(4); 839 deadConditionalCycle(4); 840 841 deadInduction(); 842 for (int i = 0; i < a.length; i++) { 843 expectEquals(1, a[i]); 844 } 845 deadManyInduction(); 846 for (int i = 0; i < a.length; i++) { 847 expectEquals(2, a[i]); 848 } 849 deadSequence(); 850 for (int i = 0; i < a.length; i++) { 851 expectEquals(3, a[i]); 852 } 853 try { 854 deadCycleWithException(-1); 855 throw new Error("Expected: IOOB exception"); 856 } catch (IndexOutOfBoundsException e) { 857 } 858 for (int i = 0; i < a.length; i++) { 859 expectEquals(i == 0 ? 4 : 3, a[i]); 860 } 861 deadCycleWithException(0); 862 for (int i = 0; i < a.length; i++) { 863 expectEquals(4, a[i]); 864 } 865 866 expectEquals(12395, closedFormInductionUp()); 867 expectEquals(12295, closedFormInductionInAndDown(12345)); 868 expectEquals(81, closedFormInductionTrivialIf()); 869 expectEquals(10 * 10, closedFormNested()); 870 expectEquals(12345 + 17 * 23 * 7, closedFormNestedAlt()); 871 for (int n = -4; n < 10; n++) { 872 int tc = (n <= 0) ? 0 : n; 873 expectEquals(12345 + tc * 5, closedFormInductionUpN(n)); 874 expectEquals(12345 - tc * 5, closedFormInductionInAndDownN(12345, n)); 875 expectEquals(tc * 10, closedFormNestedN(n)); 876 expectEquals(12345 + tc * 23 * 7, closedFormNestedNAlt(n)); 877 expectEquals(tc * (tc + 1), closedFormNestedMN(n, n + 1)); 878 expectEquals(12345 + tc * (tc + 1) * 7, closedFormNestedMNAlt(n, n + 1)); 879 } 880 881 expectEquals(10, mainIndexReturned()); 882 expectEquals(1, periodicReturned9()); 883 expectEquals(0, periodicReturned10()); 884 expectEquals(21, getSum21()); 885 expectEquals(354, getIncr2(new int[12])); 886 for (int n = -4; n < 4; n++) { 887 int tc = (n <= 0) ? 0 : n; 888 expectEquals(tc, mainIndexReturnedN(n)); 889 expectEquals(tc, mainIndexShort1((short) n)); 890 expectEquals(tc, mainIndexShort2((short) n)); 891 expectEquals(tc & 1, periodicReturnedN(n)); 892 expectEquals((tc * (tc + 1)) / 2, getSumN(n)); 893 } 894 895 expectEquals(10, closedTwice()); 896 expectEquals(20, closedFeed()); 897 expectEquals(-10, closedLargeUp()); 898 expectEquals(10, closedLargeDown()); 899 expectEquals(50, waterFall()); 900 901 expectEquals(false, periodicBoolIdiom1()); 902 expectEquals(false, periodicBoolIdiom2()); 903 expectEquals(false, periodicBoolIdiom3()); 904 for (int n = -4; n < 10; n++) { 905 int tc = (n <= 0) ? 0 : n; 906 boolean even = (tc & 1) == 0; 907 expectEquals(even, periodicBoolIdiom1N(true, n)); 908 expectEquals(!even, periodicBoolIdiom1N(false, n)); 909 expectEquals(even, periodicBoolIdiom2N(true, n)); 910 expectEquals(!even, periodicBoolIdiom2N(false, n)); 911 expectEquals(even, periodicBoolIdiom3N(true, n)); 912 expectEquals(!even, periodicBoolIdiom3N(false, n)); 913 } 914 915 expectEquals( 2.0f, periodicFloat10()); 916 expectEquals(-1.0f, periodicFloat11()); 917 expectEquals( 4.5f, periodicFloat12()); 918 919 expectEquals(100, exceptionExitBeforeAdd()); 920 expectEquals(100, exceptionExitAfterAdd()); 921 a = null; 922 expectEquals(-1, exceptionExitBeforeAdd()); 923 expectEquals(-11, exceptionExitAfterAdd()); 924 a = new int[4]; 925 expectEquals(-41, exceptionExitBeforeAdd()); 926 expectEquals(-51, exceptionExitAfterAdd()); 927 928 System.out.println("passed"); 929 } 930 931 private static void expectEquals(float expected, float result) { 932 if (expected != result) { 933 throw new Error("Expected: " + expected + ", found: " + result); 934 } 935 } 936 937 private static void expectEquals(int expected, int result) { 938 if (expected != result) { 939 throw new Error("Expected: " + expected + ", found: " + result); 940 } 941 } 942 943 private static void expectEquals(boolean expected, boolean result) { 944 if (expected != result) { 945 throw new Error("Expected: " + expected + ", found: " + result); 946 } 947 } 948 } 949
