1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -indvars -S < %s | FileCheck %s 3 4define void @ult(i64 %n, i64 %m) { 5; CHECK-LABEL: @ult( 6; CHECK-NEXT: entry: 7; CHECK-NEXT: [[CMP0:%.*]] = icmp ult i64 [[N:%.*]], [[M:%.*]] 8; CHECK-NEXT: br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 9; CHECK: loop.preheader: 10; CHECK-NEXT: br label [[LOOP:%.*]] 11; CHECK: loop: 12; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] 13; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1 14; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i64 [[IV]], [[N]] 15; CHECK-NEXT: br i1 [[CMP1]], label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]] 16; CHECK: latch: 17; CHECK-NEXT: call void @side_effect() 18; CHECK-NEXT: br i1 true, label [[LOOP]], label [[EXIT_LOOPEXIT]] 19; CHECK: exit.loopexit: 20; CHECK-NEXT: br label [[EXIT]] 21; CHECK: exit: 22; CHECK-NEXT: ret void 23; 24entry: 25 %cmp0 = icmp ult i64 %n, %m 26 br i1 %cmp0, label %loop, label %exit 27loop: 28 %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ] 29 %iv.next = add i64 %iv, 1 30 %cmp1 = icmp ult i64 %iv, %n 31 br i1 %cmp1, label %latch, label %exit 32latch: 33 call void @side_effect() 34 %cmp2 = icmp ult i64 %iv, %m 35 br i1 %cmp2, label %loop, label %exit 36exit: 37 ret void 38} 39 40define void @ugt(i64 %n, i64 %m) { 41; CHECK-LABEL: @ugt( 42; CHECK-NEXT: entry: 43; CHECK-NEXT: [[CMP0:%.*]] = icmp ugt i64 [[N:%.*]], [[M:%.*]] 44; CHECK-NEXT: br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 45; CHECK: loop.preheader: 46; CHECK-NEXT: br label [[LOOP:%.*]] 47; CHECK: loop: 48; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] 49; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1 50; CHECK-NEXT: br i1 true, label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]] 51; CHECK: latch: 52; CHECK-NEXT: call void @side_effect() 53; CHECK-NEXT: [[CMP2:%.*]] = icmp ult i64 [[IV]], [[M]] 54; CHECK-NEXT: br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]] 55; CHECK: exit.loopexit: 56; CHECK-NEXT: br label [[EXIT]] 57; CHECK: exit: 58; CHECK-NEXT: ret void 59; 60entry: 61 %cmp0 = icmp ugt i64 %n, %m 62 br i1 %cmp0, label %loop, label %exit 63loop: 64 %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ] 65 %iv.next = add i64 %iv, 1 66 %cmp1 = icmp ult i64 %iv, %n 67 br i1 %cmp1, label %latch, label %exit 68latch: 69 call void @side_effect() 70 %cmp2 = icmp ult i64 %iv, %m 71 br i1 %cmp2, label %loop, label %exit 72exit: 73 ret void 74} 75 76define void @ule(i64 %n, i64 %m) { 77; CHECK-LABEL: @ule( 78; CHECK-NEXT: entry: 79; CHECK-NEXT: [[CMP0:%.*]] = icmp ule i64 [[N:%.*]], [[M:%.*]] 80; CHECK-NEXT: br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 81; CHECK: loop.preheader: 82; CHECK-NEXT: br label [[LOOP:%.*]] 83; CHECK: loop: 84; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] 85; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1 86; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i64 [[IV]], [[N]] 87; CHECK-NEXT: br i1 [[CMP1]], label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]] 88; CHECK: latch: 89; CHECK-NEXT: call void @side_effect() 90; CHECK-NEXT: [[CMP2:%.*]] = icmp ult i64 [[IV]], [[M]] 91; CHECK-NEXT: br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]] 92; CHECK: exit.loopexit: 93; CHECK-NEXT: br label [[EXIT]] 94; CHECK: exit: 95; CHECK-NEXT: ret void 96; 97entry: 98 %cmp0 = icmp ule i64 %n, %m 99 br i1 %cmp0, label %loop, label %exit 100loop: 101 %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ] 102 %iv.next = add i64 %iv, 1 103 %cmp1 = icmp ult i64 %iv, %n 104 br i1 %cmp1, label %latch, label %exit 105latch: 106 call void @side_effect() 107 %cmp2 = icmp ult i64 %iv, %m 108 br i1 %cmp2, label %loop, label %exit 109exit: 110 ret void 111} 112 113define void @uge(i64 %n, i64 %m) { 114; CHECK-LABEL: @uge( 115; CHECK-NEXT: entry: 116; CHECK-NEXT: [[CMP0:%.*]] = icmp uge i64 [[N:%.*]], [[M:%.*]] 117; CHECK-NEXT: br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 118; CHECK: loop.preheader: 119; CHECK-NEXT: br label [[LOOP:%.*]] 120; CHECK: loop: 121; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] 122; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1 123; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i64 [[IV]], [[N]] 124; CHECK-NEXT: br i1 [[CMP1]], label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]] 125; CHECK: latch: 126; CHECK-NEXT: call void @side_effect() 127; CHECK-NEXT: [[CMP2:%.*]] = icmp ult i64 [[IV]], [[M]] 128; CHECK-NEXT: br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]] 129; CHECK: exit.loopexit: 130; CHECK-NEXT: br label [[EXIT]] 131; CHECK: exit: 132; CHECK-NEXT: ret void 133; 134entry: 135 %cmp0 = icmp uge i64 %n, %m 136 br i1 %cmp0, label %loop, label %exit 137loop: 138 %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ] 139 %iv.next = add i64 %iv, 1 140 %cmp1 = icmp ult i64 %iv, %n 141 br i1 %cmp1, label %latch, label %exit 142latch: 143 call void @side_effect() 144 %cmp2 = icmp ult i64 %iv, %m 145 br i1 %cmp2, label %loop, label %exit 146exit: 147 ret void 148} 149 150 151define void @ult_const_max(i64 %n) { 152; CHECK-LABEL: @ult_const_max( 153; CHECK-NEXT: entry: 154; CHECK-NEXT: [[CMP0:%.*]] = icmp ult i64 [[N:%.*]], 20 155; CHECK-NEXT: br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 156; CHECK: loop.preheader: 157; CHECK-NEXT: br label [[LOOP:%.*]] 158; CHECK: loop: 159; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] 160; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1 161; CHECK-NEXT: br i1 true, label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]] 162; CHECK: latch: 163; CHECK-NEXT: call void @side_effect() 164; CHECK-NEXT: [[CMP2:%.*]] = icmp ult i64 [[IV]], [[N]] 165; CHECK-NEXT: br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]] 166; CHECK: exit.loopexit: 167; CHECK-NEXT: br label [[EXIT]] 168; CHECK: exit: 169; CHECK-NEXT: ret void 170; 171entry: 172 %cmp0 = icmp ult i64 %n, 20 173 br i1 %cmp0, label %loop, label %exit 174loop: 175 %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ] 176 %iv.next = add i64 %iv, 1 177 %udiv = udiv i64 %iv, 10 178 %cmp1 = icmp ult i64 %udiv, 2 179 br i1 %cmp1, label %latch, label %exit 180latch: 181 call void @side_effect() 182 %cmp2 = icmp ult i64 %iv, %n 183 br i1 %cmp2, label %loop, label %exit 184exit: 185 ret void 186} 187 188define void @mixed_width(i32 %len) { 189; CHECK-LABEL: @mixed_width( 190; CHECK-NEXT: entry: 191; CHECK-NEXT: [[LEN_ZEXT:%.*]] = zext i32 [[LEN:%.*]] to i64 192; CHECK-NEXT: br label [[LOOP:%.*]] 193; CHECK: loop: 194; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] 195; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1 196; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i64 [[IV]], [[LEN_ZEXT]] 197; CHECK-NEXT: br i1 [[CMP1]], label [[BACKEDGE]], label [[EXIT:%.*]] 198; CHECK: backedge: 199; CHECK-NEXT: call void @side_effect() 200; CHECK-NEXT: br i1 true, label [[LOOP]], label [[EXIT]] 201; CHECK: exit: 202; CHECK-NEXT: ret void 203; 204entry: 205 %len.zext = zext i32 %len to i64 206 br label %loop 207loop: 208 %iv = phi i64 [0, %entry], [%iv.next, %backedge] 209 %iv2 = phi i32 [0, %entry], [%iv2.next, %backedge] 210 %iv.next = add i64 %iv, 1 211 %iv2.next = add i32 %iv2, 1 212 %cmp1 = icmp ult i64 %iv, %len.zext 213 br i1 %cmp1, label %backedge, label %exit 214 215backedge: 216 call void @side_effect() 217 %cmp2 = icmp ult i32 %iv2, %len 218 br i1 %cmp2, label %loop, label %exit 219exit: 220 ret void 221} 222 223define void @many_exits([100 x i64] %len) { 224entry: 225 br label %loop 226loop: 227 %iv = phi i64 [0, %entry], [%iv.next, %backedge] 228 %len0 = extractvalue [100 x i64] %len, 0 229 %early0 = icmp eq i64 %iv, %len0 230 call void @side_effect() 231 br i1 %early0, label %exit, label %cont0 232cont0: 233 %len1 = extractvalue [100 x i64] %len, 1 234 %early1 = icmp eq i64 %iv, %len1 235 call void @side_effect() 236 br i1 %early1, label %exit, label %cont1 237cont1: 238 %len2 = extractvalue [100 x i64] %len, 2 239 %early2 = icmp eq i64 %iv, %len2 240 call void @side_effect() 241 br i1 %early2, label %exit, label %cont2 242cont2: 243 %len3 = extractvalue [100 x i64] %len, 3 244 %early3 = icmp eq i64 %iv, %len3 245 call void @side_effect() 246 br i1 %early3, label %exit, label %cont3 247cont3: 248 %len4 = extractvalue [100 x i64] %len, 4 249 %early4 = icmp eq i64 %iv, %len4 250 call void @side_effect() 251 br i1 %early4, label %exit, label %cont4 252cont4: 253 %len5 = extractvalue [100 x i64] %len, 5 254 %early5 = icmp eq i64 %iv, %len5 255 call void @side_effect() 256 br i1 %early5, label %exit, label %cont5 257cont5: 258 %len6 = extractvalue [100 x i64] %len, 6 259 %early6 = icmp eq i64 %iv, %len6 260 call void @side_effect() 261 br i1 %early6, label %exit, label %cont6 262cont6: 263 %len7 = extractvalue [100 x i64] %len, 7 264 %early7 = icmp eq i64 %iv, %len7 265 call void @side_effect() 266 br i1 %early7, label %exit, label %cont7 267cont7: 268 %len8 = extractvalue [100 x i64] %len, 8 269 %early8 = icmp eq i64 %iv, %len8 270 call void @side_effect() 271 br i1 %early8, label %exit, label %cont8 272cont8: 273 %len9 = extractvalue [100 x i64] %len, 9 274 %early9 = icmp eq i64 %iv, %len9 275 call void @side_effect() 276 br i1 %early9, label %exit, label %cont9 277cont9: 278 %len10 = extractvalue [100 x i64] %len, 10 279 %early10 = icmp eq i64 %iv, %len10 280 call void @side_effect() 281 br i1 %early10, label %exit, label %cont10 282cont10: 283 %len11 = extractvalue [100 x i64] %len, 11 284 %early11 = icmp eq i64 %iv, %len11 285 call void @side_effect() 286 br i1 %early11, label %exit, label %cont11 287cont11: 288 %len12 = extractvalue [100 x i64] %len, 12 289 %early12 = icmp eq i64 %iv, %len12 290 call void @side_effect() 291 br i1 %early12, label %exit, label %cont12 292cont12: 293 %len13 = extractvalue [100 x i64] %len, 13 294 %early13 = icmp eq i64 %iv, %len13 295 call void @side_effect() 296 br i1 %early13, label %exit, label %cont13 297cont13: 298 %len14 = extractvalue [100 x i64] %len, 14 299 %early14 = icmp eq i64 %iv, %len14 300 call void @side_effect() 301 br i1 %early14, label %exit, label %cont14 302cont14: 303 %len15 = extractvalue [100 x i64] %len, 15 304 %early15 = icmp eq i64 %iv, %len15 305 call void @side_effect() 306 br i1 %early15, label %exit, label %cont15 307cont15: 308 %len16 = extractvalue [100 x i64] %len, 16 309 %early16 = icmp eq i64 %iv, %len16 310 call void @side_effect() 311 br i1 %early16, label %exit, label %cont16 312cont16: 313 %len17 = extractvalue [100 x i64] %len, 17 314 %early17 = icmp eq i64 %iv, %len17 315 call void @side_effect() 316 br i1 %early17, label %exit, label %cont17 317cont17: 318 %len18 = extractvalue [100 x i64] %len, 18 319 %early18 = icmp eq i64 %iv, %len18 320 call void @side_effect() 321 br i1 %early18, label %exit, label %cont18 322cont18: 323 %len19 = extractvalue [100 x i64] %len, 19 324 %early19 = icmp eq i64 %iv, %len19 325 call void @side_effect() 326 br i1 %early19, label %exit, label %cont19 327cont19: 328 %len20 = extractvalue [100 x i64] %len, 20 329 %early20 = icmp eq i64 %iv, %len20 330 call void @side_effect() 331 br i1 %early20, label %exit, label %cont20 332cont20: 333 %len21 = extractvalue [100 x i64] %len, 21 334 %early21 = icmp eq i64 %iv, %len21 335 call void @side_effect() 336 br i1 %early21, label %exit, label %cont21 337cont21: 338 %len22 = extractvalue [100 x i64] %len, 22 339 %early22 = icmp eq i64 %iv, %len22 340 call void @side_effect() 341 br i1 %early22, label %exit, label %cont22 342cont22: 343 %len23 = extractvalue [100 x i64] %len, 23 344 %early23 = icmp eq i64 %iv, %len23 345 call void @side_effect() 346 br i1 %early23, label %exit, label %cont23 347cont23: 348 %len24 = extractvalue [100 x i64] %len, 24 349 %early24 = icmp eq i64 %iv, %len24 350 call void @side_effect() 351 br i1 %early24, label %exit, label %cont24 352cont24: 353 %len25 = extractvalue [100 x i64] %len, 25 354 %early25 = icmp eq i64 %iv, %len25 355 call void @side_effect() 356 br i1 %early25, label %exit, label %cont25 357cont25: 358 %len26 = extractvalue [100 x i64] %len, 26 359 %early26 = icmp eq i64 %iv, %len26 360 call void @side_effect() 361 br i1 %early26, label %exit, label %cont26 362cont26: 363 %len27 = extractvalue [100 x i64] %len, 27 364 %early27 = icmp eq i64 %iv, %len27 365 call void @side_effect() 366 br i1 %early27, label %exit, label %cont27 367cont27: 368 %len28 = extractvalue [100 x i64] %len, 28 369 %early28 = icmp eq i64 %iv, %len28 370 call void @side_effect() 371 br i1 %early28, label %exit, label %cont28 372cont28: 373 %len29 = extractvalue [100 x i64] %len, 29 374 %early29 = icmp eq i64 %iv, %len29 375 call void @side_effect() 376 br i1 %early29, label %exit, label %cont29 377cont29: 378 %len30 = extractvalue [100 x i64] %len, 30 379 %early30 = icmp eq i64 %iv, %len30 380 call void @side_effect() 381 br i1 %early30, label %exit, label %cont30 382cont30: 383 %len31 = extractvalue [100 x i64] %len, 31 384 %early31 = icmp eq i64 %iv, %len31 385 call void @side_effect() 386 br i1 %early31, label %exit, label %cont31 387cont31: 388 %len32 = extractvalue [100 x i64] %len, 32 389 %early32 = icmp eq i64 %iv, %len32 390 call void @side_effect() 391 br i1 %early32, label %exit, label %cont32 392cont32: 393 %len33 = extractvalue [100 x i64] %len, 33 394 %early33 = icmp eq i64 %iv, %len33 395 call void @side_effect() 396 br i1 %early33, label %exit, label %cont33 397cont33: 398 %len34 = extractvalue [100 x i64] %len, 34 399 %early34 = icmp eq i64 %iv, %len34 400 call void @side_effect() 401 br i1 %early34, label %exit, label %cont34 402cont34: 403 %len35 = extractvalue [100 x i64] %len, 35 404 %early35 = icmp eq i64 %iv, %len35 405 call void @side_effect() 406 br i1 %early35, label %exit, label %cont35 407cont35: 408 %len36 = extractvalue [100 x i64] %len, 36 409 %early36 = icmp eq i64 %iv, %len36 410 call void @side_effect() 411 br i1 %early36, label %exit, label %cont36 412cont36: 413 %len37 = extractvalue [100 x i64] %len, 37 414 %early37 = icmp eq i64 %iv, %len37 415 call void @side_effect() 416 br i1 %early37, label %exit, label %cont37 417cont37: 418 %len38 = extractvalue [100 x i64] %len, 38 419 %early38 = icmp eq i64 %iv, %len38 420 call void @side_effect() 421 br i1 %early38, label %exit, label %cont38 422cont38: 423 %len39 = extractvalue [100 x i64] %len, 39 424 %early39 = icmp eq i64 %iv, %len39 425 call void @side_effect() 426 br i1 %early39, label %exit, label %cont39 427cont39: 428 br label %backedge 429backedge: 430 call void @side_effect() 431 %cmp2 = icmp ult i64 %iv, 999 432 %iv.next = add i64 %iv, 1 433 br i1 %cmp2, label %loop, label %exit 434exit: 435 ret void 436} 437 438declare void @side_effect() 439 440; The exit condition %outer.cond.1 depends on a phi in %inner. Make sure we do 441; not incorrectly determine %x.lcssa <= -1. 442define i32 @exit_cond_depends_on_inner_loop() { 443; CHECK-LABEL: @exit_cond_depends_on_inner_loop( 444; CHECK-NEXT: entry: 445; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] 446; CHECK: outer.header: 447; CHECK-NEXT: [[IV_OUTER:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_OUTER_NEXT:%.*]], [[OUTER_LATCH:%.*]] ] 448; CHECK-NEXT: br label [[INNER:%.*]] 449; CHECK: inner: 450; CHECK-NEXT: [[X:%.*]] = phi i32 [ -1, [[OUTER_HEADER]] ], [ [[CALL:%.*]], [[INNER]] ] 451; CHECK-NEXT: [[CALL]] = call i32 @match() 452; CHECK-NEXT: [[INNER_COND:%.*]] = icmp sgt i32 [[CALL]], -1 453; CHECK-NEXT: br i1 [[INNER_COND]], label [[INNER]], label [[OUTER_EXITING_1:%.*]] 454; CHECK: outer.exiting.1: 455; CHECK-NEXT: [[X_LCSSA:%.*]] = phi i32 [ [[X]], [[INNER]] ] 456; CHECK-NEXT: [[OUTER_COND_1:%.*]] = icmp sgt i32 [[X_LCSSA]], -1 457; CHECK-NEXT: br i1 [[OUTER_COND_1]], label [[EXIT:%.*]], label [[OUTER_LATCH]] 458; CHECK: outer.latch: 459; CHECK-NEXT: [[IV_OUTER_NEXT]] = add nuw nsw i32 [[IV_OUTER]], 1 460; CHECK-NEXT: [[OUTER_COND_2:%.*]] = icmp ult i32 [[IV_OUTER]], 100 461; CHECK-NEXT: br i1 [[OUTER_COND_2]], label [[OUTER_HEADER]], label [[EXIT]] 462; CHECK: exit: 463; CHECK-NEXT: [[X_RES:%.*]] = phi i32 [ [[X_LCSSA]], [[OUTER_EXITING_1]] ], [ -1, [[OUTER_LATCH]] ] 464; CHECK-NEXT: ret i32 [[X_RES]] 465; 466entry: 467 br label %outer.header 468 469outer.header: 470 %iv.outer = phi i32 [ 0, %entry ], [ %iv.outer.next , %outer.latch ] 471 br label %inner 472 473inner: 474 %x = phi i32 [ -1, %outer.header ], [ %call, %inner ] 475 %call = call i32 @match() 476 %inner.cond = icmp sgt i32 %call, -1 477 br i1 %inner.cond, label %inner, label %outer.exiting.1 478 479outer.exiting.1: 480 %x.lcssa = phi i32 [ %x, %inner ] 481 %outer.cond.1 = icmp sgt i32 %x.lcssa, -1 482 br i1 %outer.cond.1, label %exit, label %outer.latch 483 484outer.latch: 485 %iv.outer.next = add nuw nsw i32 %iv.outer, 1 486 %outer.cond.2 = icmp ult i32 %iv.outer, 100 487 br i1 %outer.cond.2, label %outer.header, label %exit 488 489exit: 490 %x.res = phi i32 [ %x.lcssa, %outer.exiting.1 ], [ -1, %outer.latch ] 491 ret i32 %x.res 492} 493 494declare i32 @match() 495