1 ; RUN: opt -indvars -S < %s | FileCheck %s 2 3 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" 4 5 @X = external global [0 x double] 6 7 ; Indvars should be able to simplify simple comparisons involving 8 ; induction variables. 9 10 ; CHECK-LABEL: @foo( 11 ; CHECK: %cond = and i1 %tobool.not, true 12 13 define void @foo(i64 %n, i32* nocapture %p) nounwind { 14 entry: 15 %cmp9 = icmp sgt i64 %n, 0 16 br i1 %cmp9, label %pre, label %return 17 18 pre: 19 %t3 = load i32, i32* %p 20 %tobool.not = icmp ne i32 %t3, 0 21 br label %loop 22 23 loop: 24 %i = phi i64 [ 0, %pre ], [ %inc, %for.inc ] 25 %cmp6 = icmp slt i64 %i, %n 26 %cond = and i1 %tobool.not, %cmp6 27 br i1 %cond, label %if.then, label %for.inc 28 29 if.then: 30 %arrayidx = getelementptr [0 x double], [0 x double]* @X, i64 0, i64 %i 31 store double 3.200000e+00, double* %arrayidx 32 br label %for.inc 33 34 for.inc: 35 %inc = add nsw i64 %i, 1 36 %exitcond = icmp sge i64 %inc, %n 37 br i1 %exitcond, label %return, label %loop 38 39 return: 40 ret void 41 } 42 43 ; Don't eliminate an icmp that's contributing to the loop exit test though. 44 45 ; CHECK-LABEL: @_ZNK4llvm5APInt3ultERKS0_( 46 ; CHECK: %tmp99 = icmp sgt i32 %i, -1 47 48 define i32 @_ZNK4llvm5APInt3ultERKS0_(i32 %tmp2.i1, i64** %tmp65, i64** %tmp73, i64** %tmp82, i64** %tmp90) { 49 entry: 50 br label %bb18 51 52 bb13: 53 %tmp66 = load i64*, i64** %tmp65, align 4 54 %tmp68 = getelementptr inbounds i64, i64* %tmp66, i32 %i 55 %tmp69 = load i64, i64* %tmp68, align 4 56 %tmp74 = load i64*, i64** %tmp73, align 4 57 %tmp76 = getelementptr inbounds i64, i64* %tmp74, i32 %i 58 %tmp77 = load i64, i64* %tmp76, align 4 59 %tmp78 = icmp ugt i64 %tmp69, %tmp77 60 br i1 %tmp78, label %bb20.loopexit, label %bb15 61 62 bb15: 63 %tmp83 = load i64*, i64** %tmp82, align 4 64 %tmp85 = getelementptr inbounds i64, i64* %tmp83, i32 %i 65 %tmp86 = load i64, i64* %tmp85, align 4 66 %tmp91 = load i64*, i64** %tmp90, align 4 67 %tmp93 = getelementptr inbounds i64, i64* %tmp91, i32 %i 68 %tmp94 = load i64, i64* %tmp93, align 4 69 %tmp95 = icmp ult i64 %tmp86, %tmp94 70 br i1 %tmp95, label %bb20.loopexit, label %bb17 71 72 bb17: 73 %tmp97 = add nsw i32 %i, -1 74 br label %bb18 75 76 bb18: 77 %i = phi i32 [ %tmp2.i1, %entry ], [ %tmp97, %bb17 ] 78 %tmp99 = icmp sgt i32 %i, -1 79 br i1 %tmp99, label %bb13, label %bb20.loopexit 80 81 bb20.loopexit: 82 %tmp.0.ph = phi i32 [ 0, %bb18 ], [ 1, %bb15 ], [ 0, %bb13 ] 83 ret i32 %tmp.0.ph 84 } 85 86 ; Indvars should eliminate the icmp here. 87 88 ; CHECK-LABEL: @func_10( 89 ; CHECK-NOT: icmp 90 ; CHECK: ret void 91 92 define void @func_10() nounwind { 93 entry: 94 br label %loop 95 96 loop: 97 %i = phi i32 [ %i.next, %loop ], [ 0, %entry ] 98 %t0 = icmp slt i32 %i, 0 99 %t1 = zext i1 %t0 to i32 100 %t2 = add i32 %t1, %i 101 %u3 = zext i32 %t2 to i64 102 store i64 %u3, i64* null 103 %i.next = add i32 %i, 1 104 br i1 undef, label %loop, label %return 105 106 return: 107 ret void 108 } 109 110 ; PR14432 111 ; Indvars should not turn the second loop into an infinite one. 112 113 ; CHECK-LABEL: @func_11( 114 ; CHECK: %tmp5 = icmp ult i32 %__key6.0, 10 115 ; CHECK-NOT: br i1 true, label %noassert68, label %unrolledend 116 117 define i32 @func_11() nounwind uwtable { 118 entry: 119 br label %forcond 120 121 forcond: ; preds = %noassert, %entry 122 %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ] 123 %tmp5 = icmp slt i32 %__key6.0, 10 124 br i1 %tmp5, label %noassert, label %forcond38.preheader 125 126 forcond38.preheader: ; preds = %forcond 127 br label %forcond38 128 129 noassert: ; preds = %forbody 130 %tmp13 = sdiv i32 -32768, %__key6.0 131 %tmp2936 = shl i32 %tmp13, 24 132 %sext23 = shl i32 %tmp13, 24 133 %tmp32 = icmp eq i32 %tmp2936, %sext23 134 %tmp37 = add i32 %__key6.0, 1 135 br i1 %tmp32, label %forcond, label %assert33 136 137 assert33: ; preds = %noassert 138 tail call void @llvm.trap() 139 unreachable 140 141 forcond38: ; preds = %noassert68, %forcond38.preheader 142 %__key8.0 = phi i32 [ %tmp81, %noassert68 ], [ 2, %forcond38.preheader ] 143 %tmp46 = icmp slt i32 %__key8.0, 10 144 br i1 %tmp46, label %noassert68, label %unrolledend 145 146 noassert68: ; preds = %forbody39 147 %tmp57 = sdiv i32 -32768, %__key8.0 148 %sext34 = shl i32 %tmp57, 16 149 %sext21 = shl i32 %tmp57, 16 150 %tmp76 = icmp eq i32 %sext34, %sext21 151 %tmp81 = add i32 %__key8.0, 1 152 br i1 %tmp76, label %forcond38, label %assert77 153 154 assert77: ; preds = %noassert68 155 tail call void @llvm.trap() 156 unreachable 157 158 unrolledend: ; preds = %forcond38 159 ret i32 0 160 } 161 162 declare void @llvm.trap() noreturn nounwind 163 164 ; In this case the second loop only has a single iteration, fold the header away 165 ; CHECK-LABEL: @func_12( 166 ; CHECK: %tmp5 = icmp ult i32 %__key6.0, 10 167 ; CHECK: br i1 true, label %noassert68, label %unrolledend 168 define i32 @func_12() nounwind uwtable { 169 entry: 170 br label %forcond 171 172 forcond: ; preds = %noassert, %entry 173 %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ] 174 %tmp5 = icmp slt i32 %__key6.0, 10 175 br i1 %tmp5, label %noassert, label %forcond38.preheader 176 177 forcond38.preheader: ; preds = %forcond 178 br label %forcond38 179 180 noassert: ; preds = %forbody 181 %tmp13 = sdiv i32 -32768, %__key6.0 182 %tmp2936 = shl i32 %tmp13, 24 183 %sext23 = shl i32 %tmp13, 24 184 %tmp32 = icmp eq i32 %tmp2936, %sext23 185 %tmp37 = add i32 %__key6.0, 1 186 br i1 %tmp32, label %forcond, label %assert33 187 188 assert33: ; preds = %noassert 189 tail call void @llvm.trap() 190 unreachable 191 192 forcond38: ; preds = %noassert68, %forcond38.preheader 193 %__key8.0 = phi i32 [ %tmp81, %noassert68 ], [ 2, %forcond38.preheader ] 194 %tmp46 = icmp slt i32 %__key8.0, 10 195 br i1 %tmp46, label %noassert68, label %unrolledend 196 197 noassert68: ; preds = %forbody39 198 %tmp57 = sdiv i32 -32768, %__key8.0 199 %sext34 = shl i32 %tmp57, 16 200 %sext21 = shl i32 %tmp57, 16 201 %tmp76 = icmp ne i32 %sext34, %sext21 202 %tmp81 = add i32 %__key8.0, 1 203 br i1 %tmp76, label %forcond38, label %assert77 204 205 assert77: ; preds = %noassert68 206 tail call void @llvm.trap() 207 unreachable 208 209 unrolledend: ; preds = %forcond38 210 ret i32 0 211 } 212 213 declare void @side_effect() 214 215 define void @func_13(i32* %len.ptr) { 216 ; CHECK-LABEL: @func_13( 217 entry: 218 %len = load i32, i32* %len.ptr, !range !0 219 %len.sub.1 = add i32 %len, -1 220 %len.is.zero = icmp eq i32 %len, 0 221 br i1 %len.is.zero, label %leave, label %loop 222 223 loop: 224 ; CHECK: loop: 225 %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] 226 call void @side_effect() 227 %iv.inc = add i32 %iv, 1 228 %iv.cmp = icmp ult i32 %iv, %len 229 br i1 %iv.cmp, label %be, label %leave 230 ; CHECK: br i1 true, label %be, label %leave 231 232 be: 233 call void @side_effect() 234 %be.cond = icmp ult i32 %iv, %len.sub.1 235 br i1 %be.cond, label %loop, label %leave 236 237 leave: 238 ret void 239 } 240 241 define void @func_14(i32* %len.ptr) { 242 ; CHECK-LABEL: @func_14( 243 entry: 244 %len = load i32, i32* %len.ptr, !range !0 245 %len.sub.1 = add i32 %len, -1 246 %len.is.zero = icmp eq i32 %len, 0 247 %len.is.int_min = icmp eq i32 %len, 2147483648 248 %no.entry = or i1 %len.is.zero, %len.is.int_min 249 br i1 %no.entry, label %leave, label %loop 250 251 loop: 252 ; CHECK: loop: 253 %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] 254 call void @side_effect() 255 %iv.inc = add i32 %iv, 1 256 %iv.cmp = icmp slt i32 %iv, %len 257 br i1 %iv.cmp, label %be, label %leave 258 ; CHECK: br i1 true, label %be, label %leave 259 260 be: 261 call void @side_effect() 262 %be.cond = icmp slt i32 %iv, %len.sub.1 263 br i1 %be.cond, label %loop, label %leave 264 265 leave: 266 ret void 267 } 268 269 define void @func_15(i32* %len.ptr) { 270 ; CHECK-LABEL: @func_15( 271 entry: 272 %len = load i32, i32* %len.ptr, !range !0 273 %len.add.1 = add i32 %len, 1 274 %len.add.1.is.zero = icmp eq i32 %len.add.1, 0 275 br i1 %len.add.1.is.zero, label %leave, label %loop 276 277 loop: 278 ; CHECK: loop: 279 %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] 280 call void @side_effect() 281 %iv.inc = add i32 %iv, 1 282 %iv.cmp = icmp ult i32 %iv, %len.add.1 283 br i1 %iv.cmp, label %be, label %leave 284 ; CHECK: br i1 true, label %be, label %leave 285 286 be: 287 call void @side_effect() 288 %be.cond = icmp ult i32 %iv, %len 289 br i1 %be.cond, label %loop, label %leave 290 291 leave: 292 ret void 293 } 294 295 define void @func_16(i32* %len.ptr) { 296 ; CHECK-LABEL: @func_16( 297 entry: 298 %len = load i32, i32* %len.ptr, !range !0 299 %len.add.5 = add i32 %len, 5 300 %entry.cond.0 = icmp slt i32 %len, 2147483643 301 %entry.cond.1 = icmp slt i32 4, %len.add.5 302 %entry.cond = and i1 %entry.cond.0, %entry.cond.1 303 br i1 %entry.cond, label %loop, label %leave 304 305 loop: 306 ; CHECK: loop: 307 %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] 308 call void @side_effect() 309 %iv.inc = add i32 %iv, 1 310 %iv.add.4 = add i32 %iv, 4 311 %iv.cmp = icmp slt i32 %iv.add.4, %len.add.5 312 br i1 %iv.cmp, label %be, label %leave 313 ; CHECK: br i1 true, label %be, label %leave 314 315 be: 316 call void @side_effect() 317 %be.cond = icmp slt i32 %iv, %len 318 br i1 %be.cond, label %loop, label %leave 319 320 leave: 321 ret void 322 } 323 324 define void @func_17(i32* %len.ptr) { 325 ; CHECK-LABEL: @func_17( 326 entry: 327 %len = load i32, i32* %len.ptr 328 %len.add.5 = add i32 %len, -5 329 %entry.cond.0 = icmp slt i32 %len, 2147483653 ;; 2147483653 == INT_MIN - (-5) 330 %entry.cond.1 = icmp slt i32 -6, %len.add.5 331 %entry.cond = and i1 %entry.cond.0, %entry.cond.1 332 br i1 %entry.cond, label %loop, label %leave 333 334 loop: 335 ; CHECK: loop: 336 %iv.2 = phi i32 [ 0, %entry ], [ %iv.2.inc, %be ] 337 %iv = phi i32 [ -6, %entry ], [ %iv.inc, %be ] 338 call void @side_effect() 339 %iv.inc = add i32 %iv, 1 340 %iv.2.inc = add i32 %iv.2, 1 341 %iv.cmp = icmp slt i32 %iv, %len.add.5 342 343 ; Deduces {-5,+,1} s< (-5 + %len) from {0,+,1} < %len 344 ; since %len s< INT_MIN - (-5) from the entry condition 345 346 ; CHECK: br i1 true, label %be, label %leave 347 br i1 %iv.cmp, label %be, label %leave 348 349 be: 350 ; CHECK: be: 351 call void @side_effect() 352 %be.cond = icmp slt i32 %iv.2, %len 353 br i1 %be.cond, label %loop, label %leave 354 355 leave: 356 ret void 357 } 358 359 define i1 @func_18(i16* %tmp20, i32* %len.addr) { 360 ; CHECK-LABEL: @func_18( 361 entry: 362 %len = load i32, i32* %len.addr, !range !0 363 %tmp18 = icmp eq i32 %len, 0 364 br i1 %tmp18, label %bb2, label %bb0.preheader 365 366 bb0.preheader: 367 br label %bb0 368 369 bb0: 370 ; CHECK: bb0: 371 %var_0.in = phi i32 [ %var_0, %bb1 ], [ %len, %bb0.preheader ] 372 %var_1 = phi i32 [ %tmp30, %bb1 ], [ 0, %bb0.preheader ] 373 %var_0 = add nsw i32 %var_0.in, -1 374 %tmp23 = icmp ult i32 %var_1, %len 375 ; CHECK: br i1 true, label %stay, label %bb2.loopexit 376 br i1 %tmp23, label %stay, label %bb2 377 378 stay: 379 ; CHECK: stay: 380 %tmp25 = getelementptr inbounds i16, i16* %tmp20, i32 %var_1 381 %tmp26 = load i16, i16* %tmp25 382 %tmp29 = icmp eq i16 %tmp26, 0 383 br i1 %tmp29, label %bb1, label %bb2 384 385 bb1: 386 %tmp30 = add i32 %var_1, 1 387 %tmp31 = icmp eq i32 %var_0, 0 388 br i1 %tmp31, label %bb3, label %bb0 389 390 bb2: 391 ret i1 false 392 393 bb3: 394 ret i1 true 395 } 396 397 define void @func_19(i32* %length.ptr) { 398 ; CHECK-LABEL: @func_19( 399 entry: 400 %length = load i32, i32* %length.ptr, !range !0 401 %length.is.nonzero = icmp ne i32 %length, 0 402 br i1 %length.is.nonzero, label %loop, label %leave 403 404 loop: 405 ; CHECK: loop: 406 %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] 407 %iv.inc = add i32 %iv, 1 408 %range.check = icmp ult i32 %iv, %length 409 br i1 %range.check, label %be, label %leave 410 ; CHECK: br i1 true, label %be, label %leave.loopexit 411 ; CHECK: be: 412 413 be: 414 call void @side_effect() 415 %be.cond = icmp slt i32 %iv.inc, %length 416 br i1 %be.cond, label %loop, label %leave 417 418 leave: 419 ret void 420 } 421 422 define void @func_20(i32* %length.ptr) { 423 ; Like @func_19, but %length is no longer provably positive, so 424 ; %range.check cannot be proved to be always true. 425 426 ; CHECK-LABEL: @func_20( 427 entry: 428 %length = load i32, i32* %length.ptr 429 %length.is.nonzero = icmp ne i32 %length, 0 430 br i1 %length.is.nonzero, label %loop, label %leave 431 432 loop: 433 ; CHECK: loop: 434 %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] 435 %iv.inc = add i32 %iv, 1 436 %range.check = icmp ult i32 %iv, %length 437 br i1 %range.check, label %be, label %leave 438 ; CHECK: br i1 %range.check, label %be, label %leave.loopexit 439 ; CHECK: be: 440 441 be: 442 call void @side_effect() 443 %be.cond = icmp slt i32 %iv.inc, %length 444 br i1 %be.cond, label %loop, label %leave 445 446 leave: 447 ret void 448 } 449 450 define void @func_21(i32* %length.ptr) { 451 ; CHECK-LABEL: @func_21( 452 453 ; This checks that the backedge condition, (I + 1) < Length - 1 implies 454 ; (I + 1) < Length 455 entry: 456 %length = load i32, i32* %length.ptr, !range !0 457 %lim = sub i32 %length, 1 458 %entry.cond = icmp sgt i32 %length, 1 459 br i1 %entry.cond, label %loop, label %leave 460 461 loop: 462 ; CHECK: loop: 463 %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] 464 %iv.inc = add i32 %iv, 1 465 %range.check = icmp slt i32 %iv, %length 466 br i1 %range.check, label %be, label %leave 467 ; CHECK: br i1 true, label %be, label %leave.loopexit 468 ; CHECK: be: 469 470 be: 471 call void @side_effect() 472 %be.cond = icmp slt i32 %iv.inc, %lim 473 br i1 %be.cond, label %loop, label %leave 474 475 leave: 476 ret void 477 } 478 479 define void @func_22(i32* %length.ptr) { 480 ; CHECK-LABEL: @func_22( 481 482 ; This checks that the backedge condition, (I + 1) < Length - 1 implies 483 ; (I + 1) < Length 484 entry: 485 %length = load i32, i32* %length.ptr, !range !0 486 %lim = sub i32 %length, 1 487 %entry.cond = icmp sgt i32 %length, 1 488 br i1 %entry.cond, label %loop, label %leave 489 490 loop: 491 ; CHECK: loop: 492 %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] 493 %iv.inc = add i32 %iv, 1 494 %range.check = icmp sle i32 %iv, %length 495 br i1 %range.check, label %be, label %leave 496 ; CHECK: br i1 true, label %be, label %leave.loopexit 497 ; CHECK: be: 498 499 be: 500 call void @side_effect() 501 %be.cond = icmp sle i32 %iv.inc, %lim 502 br i1 %be.cond, label %loop, label %leave 503 504 leave: 505 ret void 506 } 507 508 define void @func_23(i32* %length.ptr) { 509 ; CHECK-LABEL: @func_23( 510 entry: 511 %length = load i32, i32* %length.ptr, !range !0 512 %entry.cond = icmp ult i32 4, %length 513 br i1 %entry.cond, label %loop, label %leave 514 515 loop: 516 ; CHECK: loop: 517 %iv = phi i32 [ 4, %entry ], [ %iv.inc, %be ] 518 %iv.inc = add i32 %iv, 1 519 %range.check = icmp slt i32 %iv, %length 520 br i1 %range.check, label %be, label %leave 521 ; CHECK: br i1 true, label %be, label %leave.loopexit 522 ; CHECK: be: 523 524 be: 525 call void @side_effect() 526 %be.cond = icmp slt i32 %iv.inc, %length 527 br i1 %be.cond, label %loop, label %leave 528 529 leave: 530 ret void 531 } 532 533 define void @func_24(i32* %init.ptr) { 534 ; CHECK-LABEL: @func_24( 535 entry: 536 %init = load i32, i32* %init.ptr, !range !0 537 %entry.cond = icmp ugt i32 %init, 4 538 br i1 %entry.cond, label %loop, label %leave 539 540 loop: 541 ; CHECK: loop: 542 %iv = phi i32 [ %init, %entry ], [ %iv.dec, %be ] 543 %iv.dec = add i32 %iv, -1 544 %range.check = icmp sgt i32 %iv, 4 545 br i1 %range.check, label %be, label %leave 546 ; CHECK: br i1 true, label %be, label %leave.loopexit 547 ; CHECK: be: 548 549 be: 550 call void @side_effect() 551 %be.cond = icmp sgt i32 %iv.dec, 4 552 br i1 %be.cond, label %loop, label %leave 553 554 leave: 555 ret void 556 } 557 558 559 !0 = !{i32 0, i32 2147483647} 560
