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 deadSingleLoop()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 deadSingleLoopN(int n)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 potentialInfiniteLoop(int n)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 deadNestedLoops()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 deadNestedAndFollowingLoops()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 deadConditional(int n)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 deadConditionalCycle(int n)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 deadInduction()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 deadManyInduction()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 deadSequence()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 deadCycleWithException(int k)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$before_codegen (after) 231 /// CHECK-DAG: <<Int:i\d+>> IntConstant 12395 loop:none 232 /// CHECK-DAG: Return [<<Int>>] loop:none closedFormInductionUp()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$before_codegen (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 closedFormInductionInAndDown(int closed)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$before_codegen (after) 272 /// CHECK-DAG: <<Int:i\d+>> IntConstant 81 loop:none 273 /// CHECK-DAG: Return [<<Int>>] loop:none closedFormInductionTrivialIf()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$before_codegen (after) 299 /// CHECK-DAG: <<Int:i\d+>> IntConstant 100 loop:none 300 /// CHECK-DAG: Return [<<Int>>] loop:none closedFormNested()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$before_codegen (after) 322 /// CHECK-DAG: <<Int:i\d+>> IntConstant 15082 loop:none 323 /// CHECK-DAG: Return [<<Int>>] loop:none closedFormNestedAlt()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 // closedFormInductionUpN turns into `if n < 0 then 12345 else 12345 + n * 5`. 335 336 /// CHECK-START: int Main.closedFormInductionUpN(int) loop_optimization (before) 337 /// CHECK: Phi 338 /// CHECK: Phi 339 /// CHECK-NOT: Phi 340 // 341 /// CHECK-START: int Main.closedFormInductionUpN(int) loop_optimization (after) 342 /// CHECK-NOT: Phi 343 // 344 /// CHECK-START: int Main.closedFormInductionUpN(int) loop_optimization (after) 345 /// CHECK-DAG: <<N:i\d+>> ParameterValue 346 /// CHECK-DAG: <<Int5:i\d+>> IntConstant 5 347 /// CHECK-DAG: <<Int12345:i\d+>> IntConstant 12345 348 /// CHECK-DAG: <<Int0:i\d+>> IntConstant 0 349 /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Int5>>,<<N>>] 350 /// CHECK-DAG: <<Add:i\d+>> Add [<<Mul>>,<<Int12345>>] 351 /// CHECK-DAG: <<LT:z\d+>> LessThan [<<Int0>>,<<N>>] 352 /// CHECK-DAG: <<Sel:i\d+>> Select [<<Int12345>>,<<Add>>,<<LT>>] 353 /// CHECK-DAG: Return [<<Sel>>] closedFormInductionUpN(int n)354 static int closedFormInductionUpN(int n) { 355 int closed = 12345; 356 for (int i = 0; i < n; i++) { 357 closed += 5; 358 } 359 return closed; // only needs last value 360 } 361 362 // closedFormInductionInAndDownN turns into `if n < 0 then closed else closed - n * 5`. 363 364 /// CHECK-START: int Main.closedFormInductionInAndDownN(int, int) loop_optimization (before) 365 /// CHECK: Phi 366 /// CHECK: Phi 367 /// CHECK-NOT: Phi 368 // 369 /// CHECK-START: int Main.closedFormInductionInAndDownN(int, int) loop_optimization (after) 370 /// CHECK-NOT: Phi 371 // 372 /// CHECK-START: int Main.closedFormInductionInAndDownN(int, int) loop_optimization (after) 373 /// CHECK-DAG: <<Closed:i\d+>> ParameterValue 374 /// CHECK-DAG: <<N:i\d+>> ParameterValue 375 /// CHECK-DAG: <<IntNeg5:i\d+>> IntConstant -5 376 /// CHECK-DAG: <<Int0:i\d+>> IntConstant 0 377 /// CHECK-DAG: <<Mul:i\d+>> Mul [<<IntNeg5>>,<<N>>] 378 /// CHECK-DAG: <<Add:i\d+>> Add [<<Mul>>,<<Closed>>] 379 /// CHECK-DAG: <<LT:z\d+>> LessThan [<<Int0>>,<<N>>] 380 /// CHECK-DAG: <<Sel:i\d+>> Select [<<Closed>>,<<Add>>,<<LT>>] 381 /// CHECK-DAG: Return [<<Sel>>] closedFormInductionInAndDownN(int closed, int n)382 static int closedFormInductionInAndDownN(int closed, int n) { 383 for (int i = 0; i < n; i++) { 384 closed -= 5; 385 } 386 return closed; // only needs last value 387 } 388 389 // closedFormNestedN turns into `if (n < 0) then 0 else n * 10` 390 391 /// CHECK-START: int Main.closedFormNestedN(int) loop_optimization (before) 392 /// CHECK: Phi 393 /// CHECK: Phi 394 /// CHECK: Phi 395 /// CHECK: Phi 396 /// CHECK-NOT: Phi 397 // 398 /// CHECK-START: int Main.closedFormNestedN(int) loop_optimization (after) 399 /// CHECK-NOT: Phi 400 // 401 /// CHECK-START: int Main.closedFormNestedN(int) loop_optimization (after) 402 /// CHECK-DAG: <<N:i\d+>> ParameterValue 403 /// CHECK-DAG: <<Int10:i\d+>> IntConstant 10 404 /// CHECK-DAG: <<Int0:i\d+>> IntConstant 0 405 /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Int10>>,<<N>>] 406 /// CHECK-DAG: <<Add:i\d+>> Add [<<Mul>>,<<Int0>>] 407 /// CHECK-DAG: <<LT:z\d+>> LessThan [<<Int0>>,<<N>>] 408 /// CHECK-DAG: <<Sel:i\d+>> Select [<<Int0>>,<<Add>>,<<LT>>] 409 /// CHECK-DAG: Return [<<Sel>>] closedFormNestedN(int n)410 static int closedFormNestedN(int n) { 411 int closed = 0; 412 for (int i = 0; i < n; i++) { 413 for (int j = 0; j < 10; j++) { 414 closed++; 415 } 416 } 417 return closed; // only needs last-value 418 } 419 420 // closedFormNestedNAlt turns into `if (n < 0) then 12345 else 12345 + n * 161` 421 422 /// CHECK-START: int Main.closedFormNestedNAlt(int) loop_optimization (before) 423 /// CHECK: Phi 424 /// CHECK: Phi 425 /// CHECK: Phi 426 /// CHECK: Phi 427 /// CHECK-NOT: Phi 428 // 429 /// CHECK-START: int Main.closedFormNestedNAlt(int) loop_optimization (after) 430 /// CHECK-NOT: Phi 431 // 432 /// CHECK-START: int Main.closedFormNestedNAlt(int) loop_optimization (after) 433 /// CHECK-DAG: <<N:i\d+>> ParameterValue 434 /// CHECK-DAG: <<Int161:i\d+>> IntConstant 161 435 /// CHECK-DAG: <<Int12345:i\d+>> IntConstant 12345 436 /// CHECK-DAG: <<Int0:i\d+>> IntConstant 0 437 /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Int161>>,<<N>>] 438 /// CHECK-DAG: <<Add:i\d+>> Add [<<Mul>>,<<Int12345>>] 439 /// CHECK-DAG: <<LT:z\d+>> LessThan [<<Int0>>,<<N>>] 440 /// CHECK-DAG: <<Sel:i\d+>> Select [<<Int12345>>,<<Add>>,<<LT>>] 441 /// CHECK-DAG: Return [<<Sel>>] closedFormNestedNAlt(int n)442 static int closedFormNestedNAlt(int n) { 443 int closed = 12345; 444 for (int i = 0; i < n; i++) { 445 for (int j = 0; j < 23; j++) { 446 closed += 7; 447 } 448 } 449 return closed; // only needs last-value 450 } 451 452 // We optimize only the inner loop. It turns into `if (n < 0) then closed else closed + n`. 453 // Potentially we can also update the outer loop turning into if (m < 0) then 0 else if (n < 0) 454 // then 0 else m * n`. 455 /// CHECK-START: int Main.closedFormNestedMN(int, int) loop_optimization (before) 456 /// CHECK: Phi 457 /// CHECK: Phi 458 /// CHECK: Phi 459 /// CHECK: Phi 460 /// CHECK-NOT: Phi 461 // 462 /// CHECK-START: int Main.closedFormNestedMN(int, int) loop_optimization (after) 463 /// CHECK: Phi 464 /// CHECK: Phi 465 /// CHECK-NOT: Phi 466 // 467 // Inner loop optimization 468 /// CHECK-START: int Main.closedFormNestedMN(int, int) loop_optimization (after) 469 /// CHECK-DAG: <<M:i\d+>> ParameterValue 470 /// CHECK-DAG: <<N:i\d+>> ParameterValue 471 /// CHECK-DAG: <<Int0:i\d+>> IntConstant 0 472 /// CHECK-DAG: <<Phi:i\d+>> Phi 473 /// CHECK-DAG: <<Add:i\d+>> Add [<<N>>,<<Phi>>] 474 /// CHECK-DAG: <<LT:z\d+>> LessThan [<<Int0>>,<<N>>] 475 /// CHECK-DAG: <<Sel:i\d+>> Select [<<Phi>>,<<Add>>,<<LT>>] closedFormNestedMN(int m, int n)476 static int closedFormNestedMN(int m, int n) { 477 int closed = 0; 478 for (int i = 0; i < m; i++) { 479 for (int j = 0; j < n; j++) { 480 closed++; 481 } 482 } 483 return closed; // only needs last-value 484 } 485 486 // We optimize only the inner loop. It turns into `if (n < 0) then closed else closed + n * 7`. 487 // Potentially we can also update the outer loop turning into if (m < 0) then 0 else if (n < 0) 488 // then 1245 else 12345 + m * n * 7`. 489 /// CHECK-START: int Main.closedFormNestedMNAlt(int, int) loop_optimization (before) 490 /// CHECK: Phi 491 /// CHECK: Phi 492 /// CHECK: Phi 493 /// CHECK: Phi 494 /// CHECK-NOT: Phi 495 // 496 /// CHECK-START: int Main.closedFormNestedMNAlt(int, int) loop_optimization (after) 497 /// CHECK: Phi 498 /// CHECK: Phi 499 /// CHECK-NOT: Phi 500 // 501 // Inner loop optimization 502 /// CHECK-START: int Main.closedFormNestedMNAlt(int, int) loop_optimization (after) 503 /// CHECK-DAG: <<M:i\d+>> ParameterValue 504 /// CHECK-DAG: <<N:i\d+>> ParameterValue 505 /// CHECK-DAG: <<Int7:i\d+>> IntConstant 7 506 /// CHECK-DAG: <<Int0:i\d+>> IntConstant 0 507 /// CHECK-DAG: <<Phi:i\d+>> Phi 508 /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Int7>>,<<N>>] 509 /// CHECK-DAG: <<Add:i\d+>> Add [<<Mul>>,<<Phi>>] 510 /// CHECK-DAG: <<LT:z\d+>> LessThan [<<Int0>>,<<N>>] 511 /// CHECK-DAG: <<Sel:i\d+>> Select [<<Phi>>,<<Add>>,<<LT>>] closedFormNestedMNAlt(int m, int n)512 static int closedFormNestedMNAlt(int m, int n) { 513 int closed = 12345; 514 for (int i = 0; i < m; i++) { 515 // if n < 0 then closed else closed + n * 7 516 for (int j = 0; j < n; j++) { 517 closed += 7; 518 } 519 } 520 return closed; // only needs last-value 521 } 522 523 /// CHECK-START: int Main.mainIndexReturned() loop_optimization (before) 524 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:{{B\d+}} outer_loop:none 525 /// CHECK-DAG: Return [<<Phi>>] loop:none 526 // 527 /// CHECK-START: int Main.mainIndexReturned() loop_optimization (after) 528 /// CHECK-NOT: Phi 529 // 530 /// CHECK-START: int Main.mainIndexReturned() instruction_simplifier$before_codegen (after) 531 /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none 532 /// CHECK-DAG: Return [<<Int>>] loop:none mainIndexReturned()533 static int mainIndexReturned() { 534 int i; 535 for (i = 0; i < 10; i++); 536 return i; 537 } 538 539 /// CHECK-START: int Main.periodicReturned9() loop_optimization (before) 540 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 541 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 542 /// CHECK-DAG: Return [<<Phi1>>] loop:none 543 // 544 /// CHECK-START: int Main.periodicReturned9() loop_optimization (after) 545 /// CHECK-NOT: Phi 546 // 547 /// CHECK-START: int Main.periodicReturned9() instruction_simplifier$before_codegen (after) 548 /// CHECK-DAG: <<Int:i\d+>> IntConstant 1 loop:none 549 /// CHECK-DAG: Return [<<Int>>] loop:none periodicReturned9()550 static int periodicReturned9() { 551 int k = 0; 552 for (int i = 0; i < 9; i++) { 553 k = 1 - k; 554 } 555 return k; 556 } 557 558 /// CHECK-START: int Main.periodicReturned10() loop_optimization (before) 559 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 560 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 561 /// CHECK-DAG: Return [<<Phi1>>] loop:none 562 // 563 /// CHECK-START: int Main.periodicReturned10() loop_optimization (after) 564 /// CHECK-NOT: Phi 565 // 566 /// CHECK-START: int Main.periodicReturned10() instruction_simplifier$before_codegen (after) 567 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none 568 /// CHECK-DAG: Return [<<Int>>] loop:none periodicReturned10()569 static int periodicReturned10() { 570 int k = 0; 571 for (int i = 0; i < 10; i++) { 572 k = 1 - k; 573 } 574 return k; 575 } 576 577 /// CHECK-START: int Main.getSum21() loop_optimization (before) 578 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 579 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 580 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop>> outer_loop:none 581 /// CHECK-DAG: Return [<<Phi2>>] loop:none 582 // 583 /// CHECK-START: int Main.getSum21() loop_optimization (after) 584 /// CHECK-NOT: Phi 585 // 586 /// CHECK-START: int Main.getSum21() instruction_simplifier$before_codegen (after) 587 /// CHECK-DAG: <<Int:i\d+>> IntConstant 21 loop:none 588 /// CHECK-DAG: Return [<<Int>>] loop:none getSum21()589 private static int getSum21() { 590 int k = 0; 591 int sum = 0; 592 for (int i = 0; i < 6; i++) { 593 k++; 594 sum += k; 595 } 596 return sum; 597 } 598 599 // Ensure double induction does not "overshoot" the subscript range. getIncr2(int[] arr)600 private static int getIncr2(int[] arr) { 601 for (int i = 0; i < 12; ) { 602 arr[i++] = 30; 603 arr[i++] = 29; 604 } 605 int sum = 0; 606 for (int i = 0; i < 12; i++) { 607 sum += arr[i]; 608 } 609 return sum; 610 } 611 612 // We can generate a select, which then DCE detects it is redundant. Therefore, we eliminate 613 // these loops. 614 615 /// CHECK-START: int Main.mainIndexReturnedN(int) loop_optimization (before) 616 /// CHECK: Phi 617 /// CHECK-NOT: Phi 618 // 619 /// CHECK-START: int Main.mainIndexReturnedN(int) loop_optimization (after) 620 /// CHECK-NOT: Phi 621 // 622 /// CHECK-START: int Main.mainIndexReturnedN(int) loop_optimization (after) 623 /// CHECK: Select mainIndexReturnedN(int n)624 static int mainIndexReturnedN(int n) { 625 int i; 626 for (i = 0; i < n; i++); 627 return i; 628 } 629 630 /// CHECK-START: int Main.mainIndexShort1(short) loop_optimization (before) 631 /// CHECK: Phi 632 /// CHECK-NOT: Phi 633 // 634 /// CHECK-START: int Main.mainIndexShort1(short) loop_optimization (after) 635 /// CHECK-NOT: Phi 636 // 637 /// CHECK-START: int Main.mainIndexShort1(short) loop_optimization (after) 638 /// CHECK: Select mainIndexShort1(short s)639 static int mainIndexShort1(short s) { 640 int i = 0; 641 for (i = 0; i < s; i++) { } 642 return i; 643 } 644 645 /// CHECK-START: int Main.mainIndexShort2(short) loop_optimization (before) 646 /// CHECK: Phi 647 /// CHECK-NOT: Phi 648 // 649 /// CHECK-START: int Main.mainIndexShort2(short) loop_optimization (after) 650 /// CHECK-NOT: Phi 651 // 652 /// CHECK-START: int Main.mainIndexShort2(short) loop_optimization (after) 653 /// CHECK: Select mainIndexShort2(short s)654 static int mainIndexShort2(short s) { 655 int i = 0; 656 for (i = 0; s > i; i++) { } 657 return i; 658 } 659 660 /// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (before) 661 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 662 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 663 /// CHECK-DAG: Return [<<Phi1>>] loop:none 664 // 665 /// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (after) 666 /// CHECK-NOT: Phi periodicReturnedN(int n)667 static int periodicReturnedN(int n) { 668 int k = 0; 669 for (int i = 0; i < n; i++) { 670 k = 1 - k; 671 } 672 return k; 673 } 674 675 /// CHECK-START: int Main.periodicOverflowTripCountNotOptimized() loop_optimization (before) 676 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 677 /// CHECK-DAG: {{i\d+}} Phi loop:<<Loop>> outer_loop:none 678 /// CHECK-DAG: Return [<<Phi1>>] loop:none 679 // 680 /// CHECK-START: int Main.periodicOverflowTripCountNotOptimized() loop_optimization (after) 681 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 682 /// CHECK-DAG: {{i\d+}} Phi loop:<<Loop>> outer_loop:none 683 /// CHECK-DAG: Return [<<Phi1>>] loop:none periodicOverflowTripCountNotOptimized()684 static int periodicOverflowTripCountNotOptimized() { 685 int k = 0; 686 for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE - 81; i += 80) { 687 k = 1 - k; 688 } 689 return k; 690 } 691 692 /// CHECK-START: int Main.periodicCouldOverflowTripCountNotOptimized(int) loop_optimization (before) 693 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 694 /// CHECK-DAG: {{i\d+}} Phi loop:<<Loop>> outer_loop:none 695 /// CHECK-DAG: Return [<<Phi1>>] loop:none 696 // 697 /// CHECK-START: int Main.periodicCouldOverflowTripCountNotOptimized(int) loop_optimization (after) 698 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 699 /// CHECK-DAG: {{i\d+}} Phi loop:<<Loop>> outer_loop:none 700 /// CHECK-DAG: Return [<<Phi1>>] loop:none periodicCouldOverflowTripCountNotOptimized(int start)701 static int periodicCouldOverflowTripCountNotOptimized(int start) { 702 int k = 0; 703 for (int i = start; i < Integer.MAX_VALUE - 81; i += 80) { 704 k = 1 - k; 705 } 706 return k; 707 } 708 709 // If ever replaced by closed form, last value should be correct! getSumN(int n)710 private static int getSumN(int n) { 711 int k = 0; 712 int sum = 0; 713 for (int i = 0; i < n; i++) { 714 k++; 715 sum += k; 716 } 717 return sum; 718 } 719 720 // If ever replaced by closed form, last value should be correct! closedTwice()721 private static int closedTwice() { 722 int closed = 0; 723 for (int i = 0; i < 10; i++) { 724 closed++; 725 } 726 // Closed form of first loop defines trip count of second loop. 727 int other_closed = 0; 728 for (int i = 0; i < closed; i++) { 729 other_closed++; 730 } 731 return other_closed; 732 } 733 734 /// CHECK-START: int Main.closedFeed() loop_optimization (before) 735 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none 736 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none 737 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:none 738 /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:none 739 /// CHECK-DAG: Return [<<Phi3>>] loop:none 740 /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>" 741 // 742 /// CHECK-START: int Main.closedFeed() loop_optimization (after) 743 /// CHECK-NOT: Phi 744 // 745 /// CHECK-START: int Main.closedFeed() instruction_simplifier$before_codegen (after) 746 /// CHECK-DAG: <<Int:i\d+>> IntConstant 20 loop:none 747 /// CHECK-DAG: Return [<<Int>>] loop:none closedFeed()748 private static int closedFeed() { 749 int closed = 0; 750 for (int i = 0; i < 10; i++) { 751 closed++; 752 } 753 // Closed form of first loop feeds into initial value of second loop, 754 // used when generating closed form for the latter. 755 for (int i = 0; i < 10; i++) { 756 closed++; 757 } 758 return closed; 759 } 760 761 /// CHECK-START: int Main.closedLargeUp() loop_optimization (before) 762 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 763 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 764 /// CHECK-DAG: Return [<<Phi1>>] loop:none 765 // 766 /// CHECK-START: int Main.closedLargeUp() loop_optimization (after) 767 /// CHECK-NOT: Phi 768 // 769 /// CHECK-START: int Main.closedLargeUp() instruction_simplifier$before_codegen (after) 770 /// CHECK-DAG: <<Int:i\d+>> IntConstant -10 loop:none 771 /// CHECK-DAG: Return [<<Int>>] loop:none closedLargeUp()772 private static int closedLargeUp() { 773 int closed = 0; 774 for (int i = 0; i < 10; i++) { 775 closed += 0x7fffffff; 776 } 777 return closed; 778 } 779 780 /// CHECK-START: int Main.closedLargeDown() loop_optimization (before) 781 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 782 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 783 /// CHECK-DAG: Return [<<Phi1>>] loop:none 784 // 785 /// CHECK-START: int Main.closedLargeDown() loop_optimization (after) 786 /// CHECK-NOT: Phi 787 // 788 /// CHECK-START: int Main.closedLargeDown() instruction_simplifier$before_codegen (after) 789 /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none 790 /// CHECK-DAG: Return [<<Int>>] loop:none closedLargeDown()791 private static int closedLargeDown() { 792 int closed = 0; 793 for (int i = 0; i < 10; i++) { 794 closed -= 0x7fffffff; 795 } 796 return closed; 797 } 798 799 // Checks that we do not loop optimize if the calculation of the trip count would overflow. 800 /// CHECK-START: int Main.closedLinearStepOverflow() loop_optimization (before) 801 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 802 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 803 /// CHECK-DAG: Return [<<Phi1>>] loop:none 804 // 805 /// CHECK-START: int Main.closedLinearStepOverflow() loop_optimization (after) 806 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 807 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 808 /// CHECK-DAG: Return [<<Phi1>>] loop:none closedLinearStepOverflow()809 private static int closedLinearStepOverflow() { 810 int closed = 0; 811 // Note that this isn't a "one-off" error. 812 // We are using MIN and MAX to make sure we overflow. 813 for (int i = Integer.MIN_VALUE; i < (Integer.MAX_VALUE - 80); i += 79) { 814 closed++; 815 } 816 return closed; 817 } 818 819 // Since we cannot guarantee that the start/end wouldn't overflow we do not perform loop 820 // optimization. 821 /// CHECK-START: int Main.$inline$closedByParameters(int, int) loop_optimization (before) 822 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 823 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 824 /// CHECK-DAG: Return [<<Phi1>>] loop:none 825 // 826 /// CHECK-START: int Main.$inline$closedByParameters(int, int) loop_optimization (after) 827 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 828 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 829 /// CHECK-DAG: Return [<<Phi1>>] loop:none $inline$closedByParameters(int start, int end)830 private static int $inline$closedByParameters(int start, int end) { 831 int closed = 0; 832 for (int i = start; i < end; i++) { 833 closed++; 834 } 835 return closed; 836 } 837 838 // Since we are inlining `closedByParameters` we know that the parameters are fixed and 839 // therefore we can perform loop optimization. 840 /// CHECK-START: int Main.closedByParametersWithInline() loop_optimization (before) 841 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 842 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 843 /// CHECK-DAG: Return [<<Phi1>>] loop:none 844 // 845 /// CHECK-START: int Main.closedByParametersWithInline() loop_optimization (after) 846 /// CHECK-NOT: Phi 847 // 848 /// CHECK-START: int Main.closedByParametersWithInline() instruction_simplifier$before_codegen (after) 849 /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none 850 /// CHECK-DAG: Return [<<Int>>] loop:none closedByParametersWithInline()851 private static int closedByParametersWithInline() { 852 return $inline$closedByParameters(0, 10); 853 } 854 855 /// CHECK-START: int Main.waterFall() loop_optimization (before) 856 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none 857 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:none 858 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop3:B\d+>> outer_loop:none 859 /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop4:B\d+>> outer_loop:none 860 /// CHECK-DAG: <<Phi5:i\d+>> Phi loop:<<Loop5:B\d+>> outer_loop:none 861 /// CHECK-DAG: Return [<<Phi5>>] loop:none 862 // 863 /// CHECK-START: int Main.waterFall() loop_optimization (after) 864 /// CHECK-NOT: Phi 865 // 866 /// CHECK-START: int Main.waterFall() instruction_simplifier$before_codegen (after) 867 /// CHECK-DAG: <<Int:i\d+>> IntConstant 50 loop:none 868 /// CHECK-DAG: Return [<<Int>>] loop:none waterFall()869 private static int waterFall() { 870 int i = 0; 871 for (; i < 10; i++); 872 for (; i < 20; i++); 873 for (; i < 30; i++); 874 for (; i < 40; i++); 875 for (; i < 50; i++); 876 return i; // this should become just 50 877 } 878 879 /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (before) 880 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 881 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 882 /// CHECK-DAG: Return [<<Phi1>>] loop:none 883 // 884 /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (after) 885 /// CHECK-NOT: Phi 886 // 887 /// CHECK-START: boolean Main.periodicBoolIdiom1() instruction_simplifier$before_codegen (after) 888 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none 889 /// CHECK-DAG: Return [<<Int>>] loop:none periodicBoolIdiom1()890 private static boolean periodicBoolIdiom1() { 891 boolean x = true; 892 for (int i = 0; i < 7; i++) { 893 x = !x; 894 } 895 return x; 896 } 897 898 /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (before) 899 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 900 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 901 /// CHECK-DAG: Return [<<Phi1>>] loop:none 902 // 903 /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (after) 904 /// CHECK-NOT: Phi 905 // 906 /// CHECK-START: boolean Main.periodicBoolIdiom2() instruction_simplifier$before_codegen (after) 907 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none 908 /// CHECK-DAG: Return [<<Int>>] loop:none periodicBoolIdiom2()909 private static boolean periodicBoolIdiom2() { 910 boolean x = true; 911 for (int i = 0; i < 7; i++) { 912 x = (x != true); 913 } 914 return x; 915 } 916 917 /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (before) 918 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 919 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 920 /// CHECK-DAG: Return [<<Phi1>>] loop:none 921 // 922 /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (after) 923 /// CHECK-NOT: Phi 924 // 925 /// CHECK-START: boolean Main.periodicBoolIdiom3() instruction_simplifier$before_codegen (after) 926 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none 927 /// CHECK-DAG: Return [<<Int>>] loop:none periodicBoolIdiom3()928 private static boolean periodicBoolIdiom3() { 929 boolean x = true; 930 for (int i = 0; i < 7; i++) { 931 x = (x == false); 932 } 933 return x; 934 } 935 936 /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (before) 937 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 938 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 939 /// CHECK-DAG: Return [<<Phi2>>] loop:none 940 // 941 /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (after) 942 /// CHECK-NOT: Phi periodicBoolIdiom1N(boolean x, int n)943 private static boolean periodicBoolIdiom1N(boolean x, int n) { 944 for (int i = 0; i < n; i++) { 945 x = !x; 946 } 947 return x; 948 } 949 950 /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (before) 951 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 952 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 953 /// CHECK-DAG: Return [<<Phi2>>] loop:none 954 // 955 /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (after) 956 /// CHECK-NOT: Phi periodicBoolIdiom2N(boolean x, int n)957 private static boolean periodicBoolIdiom2N(boolean x, int n) { 958 for (int i = 0; i < n; i++) { 959 x = (x != true); 960 } 961 return x; 962 } 963 964 /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (before) 965 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 966 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none 967 /// CHECK-DAG: Return [<<Phi2>>] loop:none 968 // 969 /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (after) 970 /// CHECK-NOT: Phi periodicBoolIdiom3N(boolean x, int n)971 private static boolean periodicBoolIdiom3N(boolean x, int n) { 972 for (int i = 0; i < n; i++) { 973 x = (x == false); 974 } 975 return x; 976 } 977 978 /// CHECK-START: float Main.periodicFloat10() loop_optimization (before) 979 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 980 /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none 981 /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none 982 /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none 983 /// CHECK-DAG: Return [<<Phi2>>] loop:none 984 // 985 /// CHECK-START: float Main.periodicFloat10() loop_optimization (after) 986 /// CHECK-NOT: Phi 987 // 988 /// CHECK-START: float Main.periodicFloat10() loop_optimization (after) 989 /// CHECK-DAG: <<Float:f\d+>> FloatConstant 2 loop:none 990 /// CHECK-DAG: Return [<<Float>>] loop:none periodicFloat10()991 private static float periodicFloat10() { 992 float r = 4.5f; 993 float s = 2.0f; 994 float t = -1.0f; 995 for (int i = 0; i < 10; i++) { 996 float tmp = t; 997 t = r; 998 r = s; 999 s = tmp; 1000 } 1001 return r; 1002 } 1003 1004 /// CHECK-START: float Main.periodicFloat11() loop_optimization (before) 1005 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 1006 /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none 1007 /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none 1008 /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none 1009 /// CHECK-DAG: Return [<<Phi2>>] loop:none 1010 // 1011 /// CHECK-START: float Main.periodicFloat11() loop_optimization (after) 1012 /// CHECK-NOT: Phi 1013 // 1014 /// CHECK-START: float Main.periodicFloat11() loop_optimization (after) 1015 /// CHECK-DAG: <<Float:f\d+>> FloatConstant -1 loop:none 1016 /// CHECK-DAG: Return [<<Float>>] loop:none periodicFloat11()1017 private static float periodicFloat11() { 1018 float r = 4.5f; 1019 float s = 2.0f; 1020 float t = -1.0f; 1021 for (int i = 0; i < 11; i++) { 1022 float tmp = t; 1023 t = r; 1024 r = s; 1025 s = tmp; 1026 } 1027 return r; 1028 } 1029 1030 /// CHECK-START: float Main.periodicFloat12() loop_optimization (before) 1031 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 1032 /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none 1033 /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none 1034 /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none 1035 /// CHECK-DAG: Return [<<Phi2>>] loop:none 1036 // 1037 /// CHECK-START: float Main.periodicFloat12() loop_optimization (after) 1038 /// CHECK-NOT: Phi 1039 // 1040 /// CHECK-START: float Main.periodicFloat12() loop_optimization (after) 1041 /// CHECK-DAG: <<Float:f\d+>> FloatConstant 4.5 loop:none 1042 /// CHECK-DAG: Return [<<Float>>] loop:none periodicFloat12()1043 private static float periodicFloat12() { 1044 float r = 4.5f; 1045 float s = 2.0f; 1046 float t = -1.0f; 1047 for (int i = 0; i < 12; i++) { 1048 float tmp = t; 1049 t = r; 1050 r = s; 1051 s = tmp; 1052 } 1053 return r; 1054 } 1055 exceptionExitBeforeAdd()1056 private static int exceptionExitBeforeAdd() { 1057 int k = 0; 1058 try { 1059 for (int i = 0; i < 10; i++) { 1060 a[i] = 0; 1061 k += 10; // increment last 1062 } 1063 } catch (Exception e) { 1064 // Flag error by returning current 1065 // value of k negated. 1066 return -k - 1; 1067 } 1068 return k; 1069 } 1070 exceptionExitAfterAdd()1071 private static int exceptionExitAfterAdd() { 1072 int k = 0; 1073 try { 1074 for (int i = 0; i < 10; i++) { 1075 k += 10; // increment first 1076 a[i] = 0; 1077 } 1078 } catch (Exception e) { 1079 // Flag error by returning current 1080 // value of k negated. 1081 return -k - 1; 1082 } 1083 return k; 1084 } 1085 1086 /// CHECK-START: long Main.closedLinearInductionUnmatchedTypesNotOptimized() loop_optimization (before) 1087 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 1088 /// CHECK-DAG: <<Phi2:j\d+>> Phi loop:<<Loop>> outer_loop:none 1089 // 1090 /// CHECK-START: long Main.closedLinearInductionUnmatchedTypesNotOptimized() loop_optimization (after) 1091 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 1092 /// CHECK-DAG: <<Phi2:j\d+>> Phi loop:<<Loop>> outer_loop:none closedLinearInductionUnmatchedTypesNotOptimized()1093 private static long closedLinearInductionUnmatchedTypesNotOptimized() { 1094 long sum = 0; 1095 for (int i = 0; i < 10; ++i) { 1096 ++sum; 1097 } 1098 return sum; 1099 } 1100 1101 /// CHECK-START: short Main.closedLinearInductionNarrowingNotOptimized() loop_optimization (before) 1102 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 1103 // 1104 /// CHECK-START: short Main.closedLinearInductionNarrowingNotOptimized() loop_optimization (after) 1105 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none closedLinearInductionNarrowingNotOptimized()1106 private static short closedLinearInductionNarrowingNotOptimized() { 1107 short i = 0; 1108 for (; i < 10; ++i); 1109 return i; 1110 } 1111 main(String[] args)1112 public static void main(String[] args) { 1113 deadSingleLoop(); 1114 deadSingleLoopN(4); 1115 potentialInfiniteLoop(4); 1116 deadNestedLoops(); 1117 deadNestedAndFollowingLoops(); 1118 deadConditional(4); 1119 deadConditionalCycle(4); 1120 1121 deadInduction(); 1122 for (int i = 0; i < a.length; i++) { 1123 expectEquals(1, a[i]); 1124 } 1125 deadManyInduction(); 1126 for (int i = 0; i < a.length; i++) { 1127 expectEquals(2, a[i]); 1128 } 1129 deadSequence(); 1130 for (int i = 0; i < a.length; i++) { 1131 expectEquals(3, a[i]); 1132 } 1133 try { 1134 deadCycleWithException(-1); 1135 throw new Error("Expected: IOOB exception"); 1136 } catch (IndexOutOfBoundsException e) { 1137 } 1138 for (int i = 0; i < a.length; i++) { 1139 expectEquals(i == 0 ? 4 : 3, a[i]); 1140 } 1141 deadCycleWithException(0); 1142 for (int i = 0; i < a.length; i++) { 1143 expectEquals(4, a[i]); 1144 } 1145 1146 expectEquals(12395, closedFormInductionUp()); 1147 expectEquals(12295, closedFormInductionInAndDown(12345)); 1148 expectEquals(81, closedFormInductionTrivialIf()); 1149 expectEquals(10 * 10, closedFormNested()); 1150 expectEquals(12345 + 17 * 23 * 7, closedFormNestedAlt()); 1151 for (int n = -4; n < 10; n++) { 1152 int tc = (n <= 0) ? 0 : n; 1153 expectEquals(12345 + tc * 5, closedFormInductionUpN(n)); 1154 expectEquals(12345 - tc * 5, closedFormInductionInAndDownN(12345, n)); 1155 expectEquals(tc * 10, closedFormNestedN(n)); 1156 expectEquals(12345 + tc * 23 * 7, closedFormNestedNAlt(n)); 1157 expectEquals(tc * (tc + 1), closedFormNestedMN(n, n + 1)); 1158 expectEquals(12345 + tc * (tc + 1) * 7, closedFormNestedMNAlt(n, n + 1)); 1159 } 1160 1161 expectEquals(10, mainIndexReturned()); 1162 expectEquals(1, periodicReturned9()); 1163 expectEquals(0, periodicReturned10()); 1164 expectEquals(21, getSum21()); 1165 expectEquals(354, getIncr2(new int[12])); 1166 for (int n = -4; n < 4; n++) { 1167 int tc = (n <= 0) ? 0 : n; 1168 expectEquals(tc, mainIndexReturnedN(n)); 1169 expectEquals(tc, mainIndexShort1((short) n)); 1170 expectEquals(tc, mainIndexShort2((short) n)); 1171 expectEquals(tc & 1, periodicReturnedN(n)); 1172 expectEquals((tc * (tc + 1)) / 2, getSumN(n)); 1173 } 1174 1175 expectEquals(1, periodicOverflowTripCountNotOptimized()); 1176 expectEquals(1, periodicCouldOverflowTripCountNotOptimized(Integer.MIN_VALUE)); 1177 1178 expectEquals(10, closedTwice()); 1179 expectEquals(20, closedFeed()); 1180 expectEquals(-10, closedLargeUp()); 1181 expectEquals(10, closedLargeDown()); 1182 expectEquals(54366674, closedLinearStepOverflow()); 1183 expectEquals(10, $inline$closedByParameters(0, 10)); 1184 expectEquals(10, closedByParametersWithInline()); 1185 expectEquals(50, waterFall()); 1186 1187 expectEquals(false, periodicBoolIdiom1()); 1188 expectEquals(false, periodicBoolIdiom2()); 1189 expectEquals(false, periodicBoolIdiom3()); 1190 for (int n = -4; n < 10; n++) { 1191 int tc = (n <= 0) ? 0 : n; 1192 boolean even = (tc & 1) == 0; 1193 expectEquals(even, periodicBoolIdiom1N(true, n)); 1194 expectEquals(!even, periodicBoolIdiom1N(false, n)); 1195 expectEquals(even, periodicBoolIdiom2N(true, n)); 1196 expectEquals(!even, periodicBoolIdiom2N(false, n)); 1197 expectEquals(even, periodicBoolIdiom3N(true, n)); 1198 expectEquals(!even, periodicBoolIdiom3N(false, n)); 1199 } 1200 1201 expectEquals( 2.0f, periodicFloat10()); 1202 expectEquals(-1.0f, periodicFloat11()); 1203 expectEquals( 4.5f, periodicFloat12()); 1204 1205 expectEquals(100, exceptionExitBeforeAdd()); 1206 expectEquals(100, exceptionExitAfterAdd()); 1207 a = null; 1208 expectEquals(-1, exceptionExitBeforeAdd()); 1209 expectEquals(-11, exceptionExitAfterAdd()); 1210 a = new int[4]; 1211 expectEquals(-41, exceptionExitBeforeAdd()); 1212 expectEquals(-51, exceptionExitAfterAdd()); 1213 1214 expectEquals(10, closedLinearInductionUnmatchedTypesNotOptimized()); 1215 expectEquals(10, closedLinearInductionNarrowingNotOptimized()); 1216 1217 System.out.println("passed"); 1218 } 1219 expectEquals(float expected, float result)1220 private static void expectEquals(float expected, float result) { 1221 if (expected != result) { 1222 throw new Error("Expected: " + expected + ", found: " + result); 1223 } 1224 } 1225 expectEquals(int expected, int result)1226 private static void expectEquals(int expected, int result) { 1227 if (expected != result) { 1228 throw new Error("Expected: " + expected + ", found: " + result); 1229 } 1230 } 1231 expectEquals(boolean expected, boolean result)1232 private static void expectEquals(boolean expected, boolean result) { 1233 if (expected != result) { 1234 throw new Error("Expected: " + expected + ", found: " + result); 1235 } 1236 } 1237 } 1238