llvm/test/Transforms/IndVarSimplify/cycled_phis.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -passes=indvars -S | FileCheck %s
   3
   4 declare void @fail(i32)
   5 declare i1 @cond()
   6 declare i32 @switch.cond()
   7 declare i32 @llvm.smax.i32(i32 %a, i32 %b)
   8
   9 ; Unsigned comparison here is redundant and can be safely deleted.
  10 define i32 @trivial.case(ptr %len.ptr) {
  11 ; CHECK-LABEL: @trivial.case(
  12 ; CHECK-NEXT:  entry:
  13 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0:![0-9]+]]
  14 ; CHECK-NEXT:    br label [[PREHEADER:%.*]]
  15 ; CHECK:       preheader:
  16 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  17 ; CHECK:       loop:
  18 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
  19 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
  20 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
  21 ; CHECK:       signed.passed:
  22 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
  23 ; CHECK:       backedge:
  24 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
  25 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
  26 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]]
  27 ; CHECK:       failed.signed:
  28 ; CHECK-NEXT:    call void @fail(i32 1)
  29 ; CHECK-NEXT:    unreachable
  30 ; CHECK:       failed.unsigned:
  31 ; CHECK-NEXT:    call void @fail(i32 2)
  32 ; CHECK-NEXT:    unreachable
  33 ; CHECK:       done:
  34 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
  35 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
  36 ;
  37 entry:
  38   %len = load i32, ptr %len.ptr, !range !0
  39   br label %preheader
  40
  41 preheader:
  42   br label %loop
  43
  44 loop:
  45   %iv = phi i32 [0, %preheader], [%iv.next, %backedge]
  46   %signed.cmp = icmp slt i32 %iv, %len
  47   br i1 %signed.cmp, label %signed.passed, label %failed.signed
  48
  49 signed.passed:
  50   %unsigned.cmp = icmp ult i32 %iv, %len
  51   br i1 %unsigned.cmp, label %backedge, label %failed.unsigned
  52
  53 backedge:
  54   %iv.next = add i32 %iv, 1
  55   %cond = call i1 @cond()
  56   br i1 %cond, label %loop, label %done
  57
  58 failed.signed:
  59   call void @fail(i32 1)
  60   unreachable
  61
  62 failed.unsigned:
  63   call void @fail(i32 2)
  64   unreachable
  65
  66 done:
  67   ret i32 %iv
  68 }
  69
  70 ; TODO: The 2nd check can be made invariant.
  71 ; slt and ult checks are equivalent. When IV is negative, slt check will pass and ult will
  72 ; fail. Because IV is incrementing, this will fail on 1st iteration or never.
  73 define i32 @unknown.start(i32 %start, ptr %len.ptr) {
  74 ; CHECK-LABEL: @unknown.start(
  75 ; CHECK-NEXT:  entry:
  76 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
  77 ; CHECK-NEXT:    br label [[PREHEADER:%.*]]
  78 ; CHECK:       preheader:
  79 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  80 ; CHECK:       loop:
  81 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
  82 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
  83 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
  84 ; CHECK:       signed.passed:
  85 ; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
  86 ; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
  87 ; CHECK:       backedge:
  88 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
  89 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
  90 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]]
  91 ; CHECK:       failed.signed:
  92 ; CHECK-NEXT:    call void @fail(i32 1)
  93 ; CHECK-NEXT:    unreachable
  94 ; CHECK:       failed.unsigned:
  95 ; CHECK-NEXT:    call void @fail(i32 2)
  96 ; CHECK-NEXT:    unreachable
  97 ; CHECK:       done:
  98 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
  99 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 100 ;
 101 entry:
 102   %len = load i32, ptr %len.ptr, !range !0
 103   br label %preheader
 104
 105 preheader:
 106   br label %loop
 107
 108 loop:
 109   %iv = phi i32 [%start, %preheader], [%iv.next, %backedge]
 110   %signed.cmp = icmp slt i32 %iv, %len
 111   br i1 %signed.cmp, label %signed.passed, label %failed.signed
 112
 113 signed.passed:
 114   %unsigned.cmp = icmp ult i32 %iv, %len
 115   br i1 %unsigned.cmp, label %backedge, label %failed.unsigned
 116
 117 backedge:
 118   %iv.next = add i32 %iv, 1
 119   %cond = call i1 @cond()
 120   br i1 %cond, label %loop, label %done
 121
 122 failed.signed:
 123   call void @fail(i32 1)
 124   unreachable
 125
 126 failed.unsigned:
 127   call void @fail(i32 2)
 128   unreachable
 129
 130 done:
 131   ret i32 %iv
 132 }
 133
 134
 135 ; TODO: We should be able to prove that:
 136 ; - %sibling.iv.next is non-negative;
 137 ; - therefore, %iv is non-negative;
 138 ; - therefore, unsigned check can be removed.
 139 define i32 @start.from.sibling.iv(ptr %len.ptr, ptr %sibling.len.ptr) {
 140 ; CHECK-LABEL: @start.from.sibling.iv(
 141 ; CHECK-NEXT:  entry:
 142 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
 143 ; CHECK-NEXT:    [[SIBLING_LEN:%.*]] = load i32, ptr [[SIBLING_LEN_PTR:%.*]], align 4, !range [[RNG0]]
 144 ; CHECK-NEXT:    br label [[SIBLING_LOOP:%.*]]
 145 ; CHECK:       sibling.loop:
 146 ; CHECK-NEXT:    [[SIBLING_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SIBLING_IV_NEXT:%.*]], [[SIBLING_BACKEDGE:%.*]] ]
 147 ; CHECK-NEXT:    [[SIBLING_RC:%.*]] = icmp ult i32 [[SIBLING_IV]], [[SIBLING_LEN]]
 148 ; CHECK-NEXT:    br i1 [[SIBLING_RC]], label [[SIBLING_BACKEDGE]], label [[FAILED_SIBLING:%.*]]
 149 ; CHECK:       sibling.backedge:
 150 ; CHECK-NEXT:    [[SIBLING_IV_NEXT]] = add nuw nsw i32 [[SIBLING_IV]], 1
 151 ; CHECK-NEXT:    [[SIBLING_COND:%.*]] = call i1 @cond()
 152 ; CHECK-NEXT:    br i1 [[SIBLING_COND]], label [[SIBLING_LOOP]], label [[PREHEADER:%.*]]
 153 ; CHECK:       preheader:
 154 ; CHECK-NEXT:    [[SIBLING_IV_NEXT_LCSSA:%.*]] = phi i32 [ [[SIBLING_IV_NEXT]], [[SIBLING_BACKEDGE]] ]
 155 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 156 ; CHECK:       loop:
 157 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_LCSSA]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 158 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
 159 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 160 ; CHECK:       signed.passed:
 161 ; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
 162 ; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 163 ; CHECK:       backedge:
 164 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 165 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 166 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]]
 167 ; CHECK:       failed.signed:
 168 ; CHECK-NEXT:    call void @fail(i32 1)
 169 ; CHECK-NEXT:    unreachable
 170 ; CHECK:       failed.unsigned:
 171 ; CHECK-NEXT:    call void @fail(i32 2)
 172 ; CHECK-NEXT:    unreachable
 173 ; CHECK:       failed.sibling:
 174 ; CHECK-NEXT:    call void @fail(i32 3)
 175 ; CHECK-NEXT:    unreachable
 176 ; CHECK:       done:
 177 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 178 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 179 ;
 180 entry:
 181   %len = load i32, ptr %len.ptr, !range !0
 182   %sibling.len = load i32, ptr %sibling.len.ptr, !range !0
 183   br label %sibling.loop
 184
 185 sibling.loop:
 186   %sibling.iv = phi i32 [0, %entry], [%sibling.iv.next, %sibling.backedge]
 187   %sibling.rc = icmp ult i32 %sibling.iv, %sibling.len
 188   br i1 %sibling.rc, label %sibling.backedge, label %failed.sibling
 189
 190 sibling.backedge:
 191   %sibling.iv.next = add nuw nsw i32 %sibling.iv, 1
 192   %sibling.cond = call i1 @cond()
 193   br i1 %sibling.cond, label %sibling.loop, label %preheader
 194
 195 preheader:
 196   br label %loop
 197
 198 loop:
 199   %iv = phi i32 [%sibling.iv.next, %preheader], [%iv.next, %backedge]
 200   %signed.cmp = icmp slt i32 %iv, %len
 201   br i1 %signed.cmp, label %signed.passed, label %failed.signed
 202
 203 signed.passed:
 204   %unsigned.cmp = icmp ult i32 %iv, %len
 205   br i1 %unsigned.cmp, label %backedge, label %failed.unsigned
 206
 207 backedge:
 208   %iv.next = add i32 %iv, 1
 209   %cond = call i1 @cond()
 210   br i1 %cond, label %loop, label %done
 211
 212 failed.signed:
 213   call void @fail(i32 1)
 214   unreachable
 215
 216 failed.unsigned:
 217   call void @fail(i32 2)
 218   unreachable
 219
 220 failed.sibling:
 221   call void @fail(i32 3)
 222   unreachable
 223
 224 done:
 225   ret i32 %iv
 226 }
 227
 228 ; Same as above, but the sibling loop is now wide. We can eliminate the unsigned comparison here.
 229 define i32 @start.from.sibling.iv.wide(ptr %len.ptr, ptr %sibling.len.ptr) {
 230 ; CHECK-LABEL: @start.from.sibling.iv.wide(
 231 ; CHECK-NEXT:  entry:
 232 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
 233 ; CHECK-NEXT:    [[SIBLING_LEN:%.*]] = load i32, ptr [[SIBLING_LEN_PTR:%.*]], align 4, !range [[RNG0]]
 234 ; CHECK-NEXT:    [[SIBLING_LEN_WIDE:%.*]] = zext i32 [[SIBLING_LEN]] to i64
 235 ; CHECK-NEXT:    br label [[SIBLING_LOOP:%.*]]
 236 ; CHECK:       sibling.loop:
 237 ; CHECK-NEXT:    [[SIBLING_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[SIBLING_IV_NEXT:%.*]], [[SIBLING_BACKEDGE:%.*]] ]
 238 ; CHECK-NEXT:    [[SIBLING_RC:%.*]] = icmp ult i64 [[SIBLING_IV]], [[SIBLING_LEN_WIDE]]
 239 ; CHECK-NEXT:    br i1 [[SIBLING_RC]], label [[SIBLING_BACKEDGE]], label [[FAILED_SIBLING:%.*]]
 240 ; CHECK:       sibling.backedge:
 241 ; CHECK-NEXT:    [[SIBLING_IV_NEXT]] = add nuw nsw i64 [[SIBLING_IV]], 1
 242 ; CHECK-NEXT:    [[SIBLING_COND:%.*]] = call i1 @cond()
 243 ; CHECK-NEXT:    br i1 [[SIBLING_COND]], label [[SIBLING_LOOP]], label [[PREHEADER:%.*]]
 244 ; CHECK:       preheader:
 245 ; CHECK-NEXT:    [[SIBLING_IV_NEXT_LCSSA:%.*]] = phi i64 [ [[SIBLING_IV_NEXT]], [[SIBLING_BACKEDGE]] ]
 246 ; CHECK-NEXT:    [[SIBLING_IV_NEXT_TRUNC:%.*]] = trunc i64 [[SIBLING_IV_NEXT_LCSSA]] to i32
 247 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 248 ; CHECK:       loop:
 249 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_TRUNC]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 250 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
 251 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 252 ; CHECK:       signed.passed:
 253 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 254 ; CHECK:       backedge:
 255 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 256 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 257 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]]
 258 ; CHECK:       failed.signed:
 259 ; CHECK-NEXT:    call void @fail(i32 1)
 260 ; CHECK-NEXT:    unreachable
 261 ; CHECK:       failed.unsigned:
 262 ; CHECK-NEXT:    call void @fail(i32 2)
 263 ; CHECK-NEXT:    unreachable
 264 ; CHECK:       failed.sibling:
 265 ; CHECK-NEXT:    call void @fail(i32 3)
 266 ; CHECK-NEXT:    unreachable
 267 ; CHECK:       done:
 268 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 269 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 270 ;
 271 entry:
 272   %len = load i32, ptr %len.ptr, !range !0
 273   %sibling.len = load i32, ptr %sibling.len.ptr, !range !0
 274   %sibling.len.wide = zext i32 %sibling.len to i64
 275   br label %sibling.loop
 276
 277 sibling.loop:
 278   %sibling.iv = phi i64 [0, %entry], [%sibling.iv.next, %sibling.backedge]
 279   %sibling.rc = icmp ult i64 %sibling.iv, %sibling.len.wide
 280   br i1 %sibling.rc, label %sibling.backedge, label %failed.sibling
 281
 282 sibling.backedge:
 283   %sibling.iv.next = add nuw nsw i64 %sibling.iv, 1
 284   %sibling.cond = call i1 @cond()
 285   br i1 %sibling.cond, label %sibling.loop, label %preheader
 286
 287 preheader:
 288   %sibling.iv.next.trunc = trunc i64 %sibling.iv.next to i32
 289   br label %loop
 290
 291 loop:
 292   %iv = phi i32 [%sibling.iv.next.trunc, %preheader], [%iv.next, %backedge]
 293   %signed.cmp = icmp slt i32 %iv, %len
 294   br i1 %signed.cmp, label %signed.passed, label %failed.signed
 295
 296 signed.passed:
 297   %unsigned.cmp = icmp ult i32 %iv, %len
 298   br i1 %unsigned.cmp, label %backedge, label %failed.unsigned
 299
 300 backedge:
 301   %iv.next = add i32 %iv, 1
 302   %cond = call i1 @cond()
 303   br i1 %cond, label %loop, label %done
 304
 305 failed.signed:
 306   call void @fail(i32 1)
 307   unreachable
 308
 309 failed.unsigned:
 310   call void @fail(i32 2)
 311   unreachable
 312
 313 failed.sibling:
 314   call void @fail(i32 3)
 315   unreachable
 316
 317 done:
 318   ret i32 %iv
 319 }
 320
 321 ; Slightly more complex version of previous one (cycled phis).
 322 ; TODO: remove unsigned comparison by proving non-negativity of iv.start.
 323 ; TODO: When we check against IV_START, for some reason we then cannot infer nuw for IV.next.
 324 ;       It was possible while checking against IV. Missing inference logic somewhere.
 325 define i32 @start.from.sibling.iv.wide.cycled.phis(ptr %len.ptr, ptr %sibling.len.ptr) {
 326 ; CHECK-LABEL: @start.from.sibling.iv.wide.cycled.phis(
 327 ; CHECK-NEXT:  entry:
 328 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
 329 ; CHECK-NEXT:    [[SIBLING_LEN:%.*]] = load i32, ptr [[SIBLING_LEN_PTR:%.*]], align 4, !range [[RNG0]]
 330 ; CHECK-NEXT:    [[SIBLING_LEN_WIDE:%.*]] = zext i32 [[SIBLING_LEN]] to i64
 331 ; CHECK-NEXT:    br label [[SIBLING_LOOP:%.*]]
 332 ; CHECK:       sibling.loop:
 333 ; CHECK-NEXT:    [[SIBLING_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[SIBLING_IV_NEXT:%.*]], [[SIBLING_BACKEDGE:%.*]] ]
 334 ; CHECK-NEXT:    [[SIBLING_RC:%.*]] = icmp ult i64 [[SIBLING_IV]], [[SIBLING_LEN_WIDE]]
 335 ; CHECK-NEXT:    br i1 [[SIBLING_RC]], label [[SIBLING_BACKEDGE]], label [[FAILED_SIBLING:%.*]]
 336 ; CHECK:       sibling.backedge:
 337 ; CHECK-NEXT:    [[SIBLING_IV_NEXT]] = add nuw nsw i64 [[SIBLING_IV]], 1
 338 ; CHECK-NEXT:    [[SIBLING_COND:%.*]] = call i1 @cond()
 339 ; CHECK-NEXT:    br i1 [[SIBLING_COND]], label [[SIBLING_LOOP]], label [[OUTER_LOOP_PREHEADER:%.*]]
 340 ; CHECK:       outer.loop.preheader:
 341 ; CHECK-NEXT:    [[SIBLING_IV_NEXT_LCSSA:%.*]] = phi i64 [ [[SIBLING_IV_NEXT]], [[SIBLING_BACKEDGE]] ]
 342 ; CHECK-NEXT:    [[SIBLING_IV_NEXT_TRUNC:%.*]] = trunc i64 [[SIBLING_IV_NEXT_LCSSA]] to i32
 343 ; CHECK-NEXT:    br label [[OUTER_LOOP:%.*]]
 344 ; CHECK:       outer.loop:
 345 ; CHECK-NEXT:    [[IV_START:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_TRUNC]], [[OUTER_LOOP_PREHEADER]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_LOOP_BACKEDGE:%.*]] ]
 346 ; CHECK-NEXT:    br label [[PREHEADER:%.*]]
 347 ; CHECK:       preheader:
 348 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 349 ; CHECK:       loop:
 350 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_START]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 351 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
 352 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 353 ; CHECK:       signed.passed:
 354 ; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV_START]], [[LEN]]
 355 ; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 356 ; CHECK:       backedge:
 357 ; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 1
 358 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 359 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_BACKEDGE]]
 360 ; CHECK:       outer.loop.backedge:
 361 ; CHECK-NEXT:    [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 362 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 363 ; CHECK-NEXT:    [[OUTER_COND:%.*]] = call i1 @cond()
 364 ; CHECK-NEXT:    br i1 [[OUTER_COND]], label [[OUTER_LOOP]], label [[DONE:%.*]]
 365 ; CHECK:       failed.signed:
 366 ; CHECK-NEXT:    call void @fail(i32 1)
 367 ; CHECK-NEXT:    unreachable
 368 ; CHECK:       failed.unsigned:
 369 ; CHECK-NEXT:    call void @fail(i32 2)
 370 ; CHECK-NEXT:    unreachable
 371 ; CHECK:       failed.sibling:
 372 ; CHECK-NEXT:    call void @fail(i32 3)
 373 ; CHECK-NEXT:    unreachable
 374 ; CHECK:       done:
 375 ; CHECK-NEXT:    [[IV_LCSSA2_LCSSA:%.*]] = phi i32 [ [[IV_LCSSA2]], [[OUTER_LOOP_BACKEDGE]] ]
 376 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2_LCSSA]]
 377 ;
 378 entry:
 379   %len = load i32, ptr %len.ptr, !range !0
 380   %sibling.len = load i32, ptr %sibling.len.ptr, !range !0
 381   %sibling.len.wide = zext i32 %sibling.len to i64
 382   br label %sibling.loop
 383
 384 sibling.loop:
 385   %sibling.iv = phi i64 [0, %entry], [%sibling.iv.next, %sibling.backedge]
 386   %sibling.rc = icmp ult i64 %sibling.iv, %sibling.len.wide
 387   br i1 %sibling.rc, label %sibling.backedge, label %failed.sibling
 388
 389 sibling.backedge:
 390   %sibling.iv.next = add nuw nsw i64 %sibling.iv, 1
 391   %sibling.cond = call i1 @cond()
 392   br i1 %sibling.cond, label %sibling.loop, label %outer.loop.preheader
 393
 394 outer.loop.preheader:
 395   %sibling.iv.next.trunc = trunc i64 %sibling.iv.next to i32
 396   br label %outer.loop
 397
 398 outer.loop:
 399   %iv.start = phi i32 [%sibling.iv.next.trunc, %outer.loop.preheader], [%iv.next, %outer.loop.backedge]
 400   br label %preheader
 401
 402 preheader:
 403   br label %loop
 404
 405 loop:
 406   %iv = phi i32 [%iv.start, %preheader], [%iv.next, %backedge]
 407   %signed.cmp = icmp slt i32 %iv, %len
 408   br i1 %signed.cmp, label %signed.passed, label %failed.signed
 409
 410 signed.passed:
 411   %unsigned.cmp = icmp ult i32 %iv, %len
 412   br i1 %unsigned.cmp, label %backedge, label %failed.unsigned
 413
 414 backedge:
 415   %iv.next = add i32 %iv, 1
 416   %cond = call i1 @cond()
 417   br i1 %cond, label %loop, label %outer.loop.backedge
 418
 419
 420 outer.loop.backedge:
 421   %outer.cond = call i1 @cond()
 422   br i1 %outer.cond, label %outer.loop, label %done
 423
 424 failed.signed:
 425   call void @fail(i32 1)
 426   unreachable
 427
 428 failed.unsigned:
 429   call void @fail(i32 2)
 430   unreachable
 431
 432 failed.sibling:
 433   call void @fail(i32 3)
 434   unreachable
 435
 436 done:
 437   ret i32 %iv
 438 }
 439
 440
 441 ; Even more complex version of previous one (more sophisticated cycled phis).
 442 ; TODO: remove unsigned comparison by proving non-negativity of iv.start.
 443 define i32 @start.from.sibling.iv.wide.cycled.phis.complex.phis(ptr %len.ptr, ptr %sibling.len.ptr, i32 %some.random.value) {
 444 ; CHECK-LABEL: @start.from.sibling.iv.wide.cycled.phis.complex.phis(
 445 ; CHECK-NEXT:  entry:
 446 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
 447 ; CHECK-NEXT:    [[SIBLING_LEN:%.*]] = load i32, ptr [[SIBLING_LEN_PTR:%.*]], align 4, !range [[RNG0]]
 448 ; CHECK-NEXT:    [[SIBLING_LEN_WIDE:%.*]] = zext i32 [[SIBLING_LEN]] to i64
 449 ; CHECK-NEXT:    br label [[SIBLING_LOOP:%.*]]
 450 ; CHECK:       sibling.loop:
 451 ; CHECK-NEXT:    [[SIBLING_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[SIBLING_IV_NEXT:%.*]], [[SIBLING_BACKEDGE:%.*]] ]
 452 ; CHECK-NEXT:    [[SIBLING_RC:%.*]] = icmp ult i64 [[SIBLING_IV]], [[SIBLING_LEN_WIDE]]
 453 ; CHECK-NEXT:    br i1 [[SIBLING_RC]], label [[SIBLING_BACKEDGE]], label [[FAILED_SIBLING:%.*]]
 454 ; CHECK:       sibling.backedge:
 455 ; CHECK-NEXT:    [[SIBLING_IV_NEXT]] = add nuw nsw i64 [[SIBLING_IV]], 1
 456 ; CHECK-NEXT:    [[SIBLING_COND:%.*]] = call i1 @cond()
 457 ; CHECK-NEXT:    br i1 [[SIBLING_COND]], label [[SIBLING_LOOP]], label [[OUTER_LOOP_PREHEADER:%.*]]
 458 ; CHECK:       outer.loop.preheader:
 459 ; CHECK-NEXT:    [[SIBLING_IV_NEXT_LCSSA:%.*]] = phi i64 [ [[SIBLING_IV_NEXT]], [[SIBLING_BACKEDGE]] ]
 460 ; CHECK-NEXT:    [[SIBLING_IV_NEXT_TRUNC:%.*]] = trunc i64 [[SIBLING_IV_NEXT_LCSSA]] to i32
 461 ; CHECK-NEXT:    br label [[OUTER_LOOP:%.*]]
 462 ; CHECK:       outer.loop:
 463 ; CHECK-NEXT:    [[IV_START:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_TRUNC]], [[OUTER_LOOP_PREHEADER]] ], [ [[IV_START_UPDATED:%.*]], [[OUTER_LOOP_BACKEDGE:%.*]] ]
 464 ; CHECK-NEXT:    br label [[PREHEADER:%.*]]
 465 ; CHECK:       preheader:
 466 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 467 ; CHECK:       loop:
 468 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_START]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 469 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
 470 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 471 ; CHECK:       signed.passed:
 472 ; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV_START]], [[LEN]]
 473 ; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 474 ; CHECK:       backedge:
 475 ; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 1
 476 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 477 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_SELECTION:%.*]]
 478 ; CHECK:       outer.loop.selection:
 479 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 480 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 481 ; CHECK-NEXT:    [[SWITCH_COND:%.*]] = call i32 @switch.cond()
 482 ; CHECK-NEXT:    switch i32 [[SWITCH_COND]], label [[TAKE_SAME:%.*]] [
 483 ; CHECK-NEXT:      i32 1, label [[TAKE_INCREMENT:%.*]]
 484 ; CHECK-NEXT:      i32 2, label [[TAKE_SMAX:%.*]]
 485 ; CHECK-NEXT:    ]
 486 ; CHECK:       take.same:
 487 ; CHECK-NEXT:    br label [[OUTER_LOOP_BACKEDGE]]
 488 ; CHECK:       take.increment:
 489 ; CHECK-NEXT:    br label [[OUTER_LOOP_BACKEDGE]]
 490 ; CHECK:       take.smax:
 491 ; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[IV_START]], i32 [[SOME_RANDOM_VALUE:%.*]])
 492 ; CHECK-NEXT:    br label [[OUTER_LOOP_BACKEDGE]]
 493 ; CHECK:       outer.loop.backedge:
 494 ; CHECK-NEXT:    [[IV_START_UPDATED]] = phi i32 [ [[IV_START]], [[TAKE_SAME]] ], [ [[IV_NEXT_LCSSA]], [[TAKE_INCREMENT]] ], [ [[SMAX]], [[TAKE_SMAX]] ]
 495 ; CHECK-NEXT:    [[OUTER_COND:%.*]] = call i1 @cond()
 496 ; CHECK-NEXT:    br i1 [[OUTER_COND]], label [[OUTER_LOOP]], label [[DONE:%.*]]
 497 ; CHECK:       failed.signed:
 498 ; CHECK-NEXT:    call void @fail(i32 1)
 499 ; CHECK-NEXT:    unreachable
 500 ; CHECK:       failed.unsigned:
 501 ; CHECK-NEXT:    call void @fail(i32 2)
 502 ; CHECK-NEXT:    unreachable
 503 ; CHECK:       failed.sibling:
 504 ; CHECK-NEXT:    call void @fail(i32 3)
 505 ; CHECK-NEXT:    unreachable
 506 ; CHECK:       done:
 507 ; CHECK-NEXT:    [[IV_LCSSA2_LCSSA:%.*]] = phi i32 [ [[IV_LCSSA2]], [[OUTER_LOOP_BACKEDGE]] ]
 508 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2_LCSSA]]
 509 ;
 510 entry:
 511   %len = load i32, ptr %len.ptr, !range !0
 512   %sibling.len = load i32, ptr %sibling.len.ptr, !range !0
 513   %sibling.len.wide = zext i32 %sibling.len to i64
 514   br label %sibling.loop
 515
 516 sibling.loop:
 517   %sibling.iv = phi i64 [0, %entry], [%sibling.iv.next, %sibling.backedge]
 518   %sibling.rc = icmp ult i64 %sibling.iv, %sibling.len.wide
 519   br i1 %sibling.rc, label %sibling.backedge, label %failed.sibling
 520
 521 sibling.backedge:
 522   %sibling.iv.next = add nuw nsw i64 %sibling.iv, 1
 523   %sibling.cond = call i1 @cond()
 524   br i1 %sibling.cond, label %sibling.loop, label %outer.loop.preheader
 525
 526 outer.loop.preheader:
 527   %sibling.iv.next.trunc = trunc i64 %sibling.iv.next to i32
 528   br label %outer.loop
 529
 530 outer.loop:
 531   %iv.start = phi i32 [%sibling.iv.next.trunc, %outer.loop.preheader], [%iv.start.updated, %outer.loop.backedge]
 532   br label %preheader
 533
 534 preheader:
 535   br label %loop
 536
 537 loop:
 538   %iv = phi i32 [%iv.start, %preheader], [%iv.next, %backedge]
 539   %signed.cmp = icmp slt i32 %iv, %len
 540   br i1 %signed.cmp, label %signed.passed, label %failed.signed
 541
 542 signed.passed:
 543   %unsigned.cmp = icmp ult i32 %iv, %len
 544   br i1 %unsigned.cmp, label %backedge, label %failed.unsigned
 545
 546 backedge:
 547   %iv.next = add i32 %iv, 1
 548   %cond = call i1 @cond()
 549   br i1 %cond, label %loop, label %outer.loop.selection
 550
 551 outer.loop.selection:
 552   %switch.cond = call i32 @switch.cond()
 553   switch i32 %switch.cond, label %take.same
 554   [
 555   i32 1, label %take.increment
 556   i32 2, label %take.smax
 557   ]
 558
 559 take.same:
 560   br label %outer.loop.backedge
 561
 562 take.increment:
 563   br label %outer.loop.backedge
 564
 565 take.smax:
 566   %smax = call i32 @llvm.smax.i32(i32 %iv.start, i32 %some.random.value)
 567   br label %outer.loop.backedge
 568
 569 outer.loop.backedge:
 570   %iv.start.updated = phi i32 [%iv.start, %take.same],
 571   [%iv.next, %take.increment],
 572   [%smax, %take.smax]
 573   %outer.cond = call i1 @cond()
 574   br i1 %outer.cond, label %outer.loop, label %done
 575
 576 failed.signed:
 577   call void @fail(i32 1)
 578   unreachable
 579
 580 failed.unsigned:
 581   call void @fail(i32 2)
 582   unreachable
 583
 584 failed.sibling:
 585   call void @fail(i32 3)
 586   unreachable
 587
 588 done:
 589   ret i32 %iv
 590 }
 591
 592 !0 = !{ i32 0, i32 2147483646 }