llvm/test/Analysis/ValueTracking/known-non-equal.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -passes=instsimplify < %s -S | FileCheck %s
   3
   4 define i1 @test(ptr %pq, i8 %B) {
   5 ; CHECK-LABEL: @test(
   6 ; CHECK-NEXT:    ret i1 false
   7 ;
   8   %q = load i8, ptr %pq, !range !0 ; %q is known nonzero; no known bits
   9   %A = add nsw i8 %B, %q
  10   %cmp = icmp eq i8 %A, %B
  11   ret i1 %cmp
  12 }
  13
  14 define i1 @test2(i8 %a, i8 %b) {
  15 ; CHECK-LABEL: @test2(
  16 ; CHECK-NEXT:    ret i1 false
  17 ;
  18   %A = or i8 %a, 2    ; %A[1] = 1
  19   %B = and i8 %b, -3  ; %B[1] = 0
  20   %cmp = icmp eq i8 %A, %B ; %A[1] and %B[1] are contradictory.
  21   ret i1 %cmp
  22 }
  23
  24 define i1 @test3(i8 %B) {
  25 ; CHECK-LABEL: @test3(
  26 ; CHECK-NEXT:    ret i1 false
  27 ;
  28   %A = add nsw i8 %B, 1
  29   %cmp = icmp eq i8 %A, %B
  30   ret i1 %cmp
  31 }
  32
  33 define i1 @sext(i8 %B) {
  34 ; CHECK-LABEL: @sext(
  35 ; CHECK-NEXT:    ret i1 false
  36 ;
  37   %A = add nsw i8 %B, 1
  38   %A.cast = sext i8 %A to i32
  39   %B.cast = sext i8 %B to i32
  40   %cmp = icmp eq i32 %A.cast, %B.cast
  41   ret i1 %cmp
  42 }
  43
  44 define i1 @zext(i8 %B) {
  45 ; CHECK-LABEL: @zext(
  46 ; CHECK-NEXT:    ret i1 false
  47 ;
  48   %A = add nsw i8 %B, 1
  49   %A.cast = zext i8 %A to i32
  50   %B.cast = zext i8 %B to i32
  51   %cmp = icmp eq i32 %A.cast, %B.cast
  52   ret i1 %cmp
  53 }
  54
  55 define i1 @inttoptr(i32 %B) {
  56 ; CHECK-LABEL: @inttoptr(
  57 ; CHECK-NEXT:    [[A:%.*]] = add nsw i32 [[B:%.*]], 1
  58 ; CHECK-NEXT:    [[A_CAST:%.*]] = inttoptr i32 [[A]] to ptr
  59 ; CHECK-NEXT:    [[B_CAST:%.*]] = inttoptr i32 [[B]] to ptr
  60 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq ptr [[A_CAST]], [[B_CAST]]
  61 ; CHECK-NEXT:    ret i1 [[CMP]]
  62 ;
  63   %A = add nsw i32 %B, 1
  64   %A.cast = inttoptr i32 %A to ptr
  65   %B.cast = inttoptr i32 %B to ptr
  66   %cmp = icmp eq ptr %A.cast, %B.cast
  67   ret i1 %cmp
  68 }
  69
  70 define i1 @ptrtoint(ptr %B) {
  71 ; CHECK-LABEL: @ptrtoint(
  72 ; CHECK-NEXT:    [[A:%.*]] = getelementptr inbounds i32, ptr [[B:%.*]], i32 1
  73 ; CHECK-NEXT:    [[A_CAST:%.*]] = ptrtoint ptr [[A]] to i32
  74 ; CHECK-NEXT:    [[B_CAST:%.*]] = ptrtoint ptr [[B]] to i32
  75 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[A_CAST]], [[B_CAST]]
  76 ; CHECK-NEXT:    ret i1 [[CMP]]
  77 ;
  78   %A = getelementptr inbounds i32, ptr %B, i32 1
  79   %A.cast = ptrtoint ptr %A to i32
  80   %B.cast = ptrtoint ptr %B to i32
  81   %cmp = icmp eq i32 %A.cast, %B.cast
  82   ret i1 %cmp
  83 }
  84
  85 define i1 @add1(i8 %B, i8 %C) {
  86 ; CHECK-LABEL: @add1(
  87 ; CHECK-NEXT:    ret i1 false
  88 ;
  89   %A = add i8 %B, 1
  90   %A.op = add i8 %A, %C
  91   %B.op = add i8 %B, %C
  92
  93   %cmp = icmp eq i8 %A.op, %B.op
  94   ret i1 %cmp
  95 }
  96
  97 define i1 @add2(i8 %B, i8 %C) {
  98 ; CHECK-LABEL: @add2(
  99 ; CHECK-NEXT:    ret i1 false
 100 ;
 101   %A = add i8 %B, 1
 102   %A.op = add i8 %C, %A
 103   %B.op = add i8 %C, %B
 104
 105   %cmp = icmp eq i8 %A.op, %B.op
 106   ret i1 %cmp
 107 }
 108
 109 define i1 @sub1(i8 %B, i8 %C) {
 110 ; CHECK-LABEL: @sub1(
 111 ; CHECK-NEXT:    ret i1 false
 112 ;
 113   %A = add i8 %B, 1
 114   %A.op = sub i8 %A, %C
 115   %B.op = sub i8 %B, %C
 116
 117   %cmp = icmp eq i8 %A.op, %B.op
 118   ret i1 %cmp
 119 }
 120
 121 define i1 @sub2(i8 %B, i8 %C) {
 122 ; CHECK-LABEL: @sub2(
 123 ; CHECK-NEXT:    ret i1 false
 124 ;
 125   %A = add i8 %B, 1
 126   %A.op = sub i8 %C, %A
 127   %B.op = sub i8 %C, %B
 128
 129   %cmp = icmp eq i8 %A.op, %B.op
 130   ret i1 %cmp
 131 }
 132
 133 ; op could wrap mapping two values to the same output value.
 134 define i1 @mul1(i8 %B) {
 135 ; CHECK-LABEL: @mul1(
 136 ; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
 137 ; CHECK-NEXT:    [[A_OP:%.*]] = mul i8 [[A]], 27
 138 ; CHECK-NEXT:    [[B_OP:%.*]] = mul i8 [[B]], 27
 139 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP]], [[B_OP]]
 140 ; CHECK-NEXT:    ret i1 [[CMP]]
 141 ;
 142   %A = add i8 %B, 1
 143   %A.op = mul i8 %A, 27
 144   %B.op = mul i8 %B, 27
 145
 146   %cmp = icmp eq i8 %A.op, %B.op
 147   ret i1 %cmp
 148 }
 149
 150 define i1 @mul2(i8 %B) {
 151 ; CHECK-LABEL: @mul2(
 152 ; CHECK-NEXT:    ret i1 false
 153 ;
 154   %A = add i8 %B, 1
 155   %A.op = mul nuw i8 %A, 27
 156   %B.op = mul nuw i8 %B, 27
 157
 158   %cmp = icmp eq i8 %A.op, %B.op
 159   ret i1 %cmp
 160 }
 161
 162 define i1 @mul3(i8 %B) {
 163 ; CHECK-LABEL: @mul3(
 164 ; CHECK-NEXT:    ret i1 false
 165 ;
 166   %A = add i8 %B, 1
 167   %A.op = mul nsw i8 %A, 27
 168   %B.op = mul nsw i8 %B, 27
 169
 170   %cmp = icmp eq i8 %A.op, %B.op
 171   ret i1 %cmp
 172 }
 173
 174 ; Multiply by zero collapses all values to one
 175 define i1 @mul4(i8 %B) {
 176 ; CHECK-LABEL: @mul4(
 177 ; CHECK-NEXT:    ret i1 true
 178 ;
 179   %A = add i8 %B, 1
 180   %A.op = mul nuw i8 %A, 0
 181   %B.op = mul nuw i8 %B, 0
 182
 183   %cmp = icmp eq i8 %A.op, %B.op
 184   ret i1 %cmp
 185 }
 186
 187 ; C might be zero, we can't tell
 188 define i1 @mul5(i8 %B, i8 %C) {
 189 ; CHECK-LABEL: @mul5(
 190 ; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
 191 ; CHECK-NEXT:    [[A_OP:%.*]] = mul nuw nsw i8 [[A]], [[C:%.*]]
 192 ; CHECK-NEXT:    [[B_OP:%.*]] = mul nuw nsw i8 [[B]], [[C]]
 193 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP]], [[B_OP]]
 194 ; CHECK-NEXT:    ret i1 [[CMP]]
 195 ;
 196   %A = add i8 %B, 1
 197   %A.op = mul nsw nuw i8 %A, %C
 198   %B.op = mul nsw nuw i8 %B, %C
 199
 200   %cmp = icmp eq i8 %A.op, %B.op
 201   ret i1 %cmp
 202 }
 203
 204 @g = external global i16, align 1
 205
 206 define i1 @mul_constantexpr(i16 %a) {
 207 ; CHECK-LABEL: @mul_constantexpr(
 208 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i16 [[A:%.*]], 3
 209 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 mul nsw (i16 ptrtoint (ptr @g to i16), i16 -1), [[MUL]]
 210 ; CHECK-NEXT:    ret i1 [[CMP]]
 211 ;
 212   %mul = mul nsw i16 %a, 3
 213   %cmp = icmp eq i16 mul nsw (i16 ptrtoint (ptr @g to i16), i16 -1), %mul
 214   ret i1 %cmp
 215 }
 216
 217 define i1 @mul_nuw(i16 %x) {
 218 ; CHECK-LABEL: @mul_nuw(
 219 ; CHECK-NEXT:    ret i1 false
 220 ;
 221   %nz = or i16 %x, 2
 222   %mul = mul nuw i16 %nz, 2
 223   %cmp = icmp eq i16 %nz, %mul
 224   ret i1 %cmp
 225 }
 226
 227 define i1 @mul_nuw_comm(i16 %x) {
 228 ; CHECK-LABEL: @mul_nuw_comm(
 229 ; CHECK-NEXT:    ret i1 false
 230 ;
 231   %nz = or i16 %x, 2
 232   %mul = mul nuw i16 %nz, 2
 233   %cmp = icmp eq i16 %mul, %nz
 234   ret i1 %cmp
 235 }
 236
 237 define i1 @mul_nsw(i16 %x) {
 238 ; CHECK-LABEL: @mul_nsw(
 239 ; CHECK-NEXT:    ret i1 false
 240 ;
 241   %nz = or i16 %x, 2
 242   %mul = mul nsw i16 %nz, 2
 243   %cmp = icmp eq i16 %nz, %mul
 244   ret i1 %cmp
 245 }
 246
 247 define i1 @mul_nsw_comm(i16 %x) {
 248 ; CHECK-LABEL: @mul_nsw_comm(
 249 ; CHECK-NEXT:    ret i1 false
 250 ;
 251   %nz = or i16 %x, 2
 252   %mul = mul nsw i16 %nz, 2
 253   %cmp = icmp eq i16 %mul, %nz
 254   ret i1 %cmp
 255 }
 256
 257 define i1 @mul_may_wrap(i16 %x) {
 258 ; CHECK-LABEL: @mul_may_wrap(
 259 ; CHECK-NEXT:    [[NZ:%.*]] = or i16 [[X:%.*]], 2
 260 ; CHECK-NEXT:    [[MUL:%.*]] = mul i16 [[NZ]], 2
 261 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]
 262 ; CHECK-NEXT:    ret i1 [[CMP]]
 263 ;
 264   %nz = or i16 %x, 2
 265   %mul = mul i16 %nz, 2
 266   %cmp = icmp eq i16 %nz, %mul
 267   ret i1 %cmp
 268 }
 269
 270 define i1 @mul_may_be_zero(i16 %x) {
 271 ; CHECK-LABEL: @mul_may_be_zero(
 272 ; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i16 [[X:%.*]], 2
 273 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[X]], [[MUL]]
 274 ; CHECK-NEXT:    ret i1 [[CMP]]
 275 ;
 276   %mul = mul nuw i16 %x, 2
 277   %cmp = icmp eq i16 %x, %mul
 278   ret i1 %cmp
 279 }
 280
 281 define i1 @mul_other_may_be_zero_or_one(i16 %x, i16 %y) {
 282 ; CHECK-LABEL: @mul_other_may_be_zero_or_one(
 283 ; CHECK-NEXT:    [[NZ:%.*]] = or i16 [[X:%.*]], 2
 284 ; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i16 [[NZ]], [[Y:%.*]]
 285 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]
 286 ; CHECK-NEXT:    ret i1 [[CMP]]
 287 ;
 288   %nz = or i16 %x, 2
 289   %mul = mul nuw i16 %nz, %y
 290   %cmp = icmp eq i16 %nz, %mul
 291   ret i1 %cmp
 292 }
 293
 294 define i1 @known_non_equal_phis(i8 %p, ptr %pq, i8 %n, i8 %r) {
 295 ; CHECK-LABEL: @known_non_equal_phis(
 296 ; CHECK-NEXT:  entry:
 297 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 298 ; CHECK:       loop:
 299 ; CHECK-NEXT:    [[A:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
 300 ; CHECK-NEXT:    [[NEXT]] = mul nsw i8 [[A]], 2
 301 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
 302 ; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
 303 ; CHECK:       exit:
 304 ; CHECK-NEXT:    ret i1 true
 305 ;
 306 entry:
 307   br label %loop
 308 loop:
 309   %A = phi i8 [ 2, %entry ], [ %next, %loop ]
 310   %B = phi i8 [ 3, %entry ], [ %A, %loop ]
 311   %next = mul nsw i8 %A, 2
 312   %cmp1 = icmp eq i8 %A, %n
 313   br i1 %cmp1, label %exit, label %loop
 314 exit:
 315   %cmp = icmp ne i8 %A, %B
 316   ret i1 %cmp
 317 }
 318
 319 define i1 @known_non_equal_phis_max_recursion_limit(i1 %cond, i32 %switch.cond) {
 320 ; CHECK-LABEL: @known_non_equal_phis_max_recursion_limit(
 321 ; CHECK-NEXT:  entry:
 322 ; CHECK-NEXT:    br label [[BB0:%.*]]
 323 ; CHECK:       bb0:
 324 ; CHECK-NEXT:    [[PHIA_0:%.*]] = phi i32 [ [[PHIA_1:%.*]], [[BB1:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 325 ; CHECK-NEXT:    [[PHIB_0:%.*]] = phi i32 [ [[PHIB_1:%.*]], [[BB1]] ], [ 0, [[ENTRY]] ]
 326 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH_BLOCK:%.*]], label [[EXIT:%.*]]
 327 ; CHECK:       switch.block:
 328 ; CHECK-NEXT:    switch i32 [[SWITCH_COND:%.*]], label [[BB1]] [
 329 ; CHECK-NEXT:      i32 0, label [[EPILOGUE:%.*]]
 330 ; CHECK-NEXT:      i32 1, label [[EPILOGUE]]
 331 ; CHECK-NEXT:    ]
 332 ; CHECK:       bb1:
 333 ; CHECK-NEXT:    [[PHIA_1]] = phi i32 [ [[PHIA_0]], [[SWITCH_BLOCK]] ], [ 0, [[EPILOGUE]] ]
 334 ; CHECK-NEXT:    [[PHIB_1]] = phi i32 [ [[PHIB_0]], [[SWITCH_BLOCK]] ], [ 0, [[EPILOGUE]] ]
 335 ; CHECK-NEXT:    br label [[BB0]]
 336 ; CHECK:       epilogue:
 337 ; CHECK-NEXT:    br label [[BB1]]
 338 ; CHECK:       exit:
 339 ; CHECK-NEXT:    [[RET:%.*]] = icmp eq i32 [[PHIA_0]], [[PHIB_0]]
 340 ; CHECK-NEXT:    ret i1 [[RET]]
 341 ;
 342 entry:
 343   br label %bb0
 344
 345 bb0:
 346   %phiA.0 = phi i32 [ %phiA.1, %bb1 ], [ 0, %entry ]
 347   %phiB.0 = phi i32 [ %phiB.1, %bb1 ], [ 0, %entry ]
 348   br i1 %cond, label %switch.block, label %exit
 349
 350 switch.block:
 351   switch i32 %switch.cond, label %bb1 [
 352   i32 0, label %epilogue
 353   i32 1, label %epilogue
 354   ]
 355
 356 bb1:
 357   %phiA.1 = phi i32 [ %phiA.0, %switch.block ], [ 0, %epilogue ]
 358   %phiB.1 = phi i32 [ %phiB.0, %switch.block ], [ 0, %epilogue ]
 359   br label %bb0
 360
 361 epilogue:
 362   br label %bb1
 363
 364 exit:
 365   %ret = icmp eq i32 %phiA.0, %phiB.0
 366   ret i1 %ret
 367 }
 368
 369 define i1 @known_non_equal_phis_fail(i8 %p, ptr %pq, i8 %n, i8 %r) {
 370 ; CHECK-LABEL: @known_non_equal_phis_fail(
 371 ; CHECK-NEXT:  entry:
 372 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 373 ; CHECK:       loop:
 374 ; CHECK-NEXT:    [[A:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
 375 ; CHECK-NEXT:    [[B:%.*]] = phi i8 [ 2, [[ENTRY]] ], [ [[A]], [[LOOP]] ]
 376 ; CHECK-NEXT:    [[NEXT]] = mul nsw i8 [[A]], 2
 377 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
 378 ; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
 379 ; CHECK:       exit:
 380 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[A]], [[B]]
 381 ; CHECK-NEXT:    ret i1 [[CMP]]
 382 ;
 383 entry:
 384   br label %loop
 385 loop:
 386   %A = phi i8 [ 2, %entry ], [ %next, %loop ]
 387   %B = phi i8 [ 2, %entry ], [ %A, %loop ]
 388   %next = mul nsw i8 %A, 2
 389   %cmp1 = icmp eq i8 %A, %n
 390   br i1 %cmp1, label %exit, label %loop
 391 exit:
 392   %cmp = icmp ne i8 %A, %B
 393   ret i1 %cmp
 394 }
 395
 396 define i1 @shl_nuw(i16 %x) {
 397 ; CHECK-LABEL: @shl_nuw(
 398 ; CHECK-NEXT:    ret i1 false
 399 ;
 400   %nz = or i16 %x, 2
 401   %mul = shl nuw i16 %nz, 1
 402   %cmp = icmp eq i16 %nz, %mul
 403   ret i1 %cmp
 404 }
 405
 406 define i1 @shl_nsw(i16 %x) {
 407 ; CHECK-LABEL: @shl_nsw(
 408 ; CHECK-NEXT:    ret i1 false
 409 ;
 410   %nz = or i16 %x, 2
 411   %mul = shl nsw i16 %nz, 1
 412   %cmp = icmp eq i16 %nz, %mul
 413   ret i1 %cmp
 414 }
 415
 416 define i1 @shl_may_wrap(i16 %x) {
 417 ; CHECK-LABEL: @shl_may_wrap(
 418 ; CHECK-NEXT:    [[NZ:%.*]] = or i16 [[X:%.*]], 2
 419 ; CHECK-NEXT:    [[MUL:%.*]] = shl i16 [[NZ]], 1
 420 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]
 421 ; CHECK-NEXT:    ret i1 [[CMP]]
 422 ;
 423   %nz = or i16 %x, 2
 424   %mul = shl i16 %nz, 1
 425   %cmp = icmp eq i16 %nz, %mul
 426   ret i1 %cmp
 427 }
 428
 429 define i1 @shl_shift_may_be_zero(i16 %x, i16 %shift) {
 430 ; CHECK-LABEL: @shl_shift_may_be_zero(
 431 ; CHECK-NEXT:    [[NZ:%.*]] = or i16 [[X:%.*]], 2
 432 ; CHECK-NEXT:    [[MUL:%.*]] = shl nuw i16 [[NZ]], [[SHIFT:%.*]]
 433 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]
 434 ; CHECK-NEXT:    ret i1 [[CMP]]
 435 ;
 436   %nz = or i16 %x, 2
 437   %mul = shl nuw i16 %nz, %shift
 438   %cmp = icmp eq i16 %nz, %mul
 439   ret i1 %cmp
 440 }
 441
 442 define i1 @shl_op_may_be_zero(i16 %x) {
 443 ; CHECK-LABEL: @shl_op_may_be_zero(
 444 ; CHECK-NEXT:    [[MUL:%.*]] = shl nuw i16 [[X:%.*]], 1
 445 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[X]], [[MUL]]
 446 ; CHECK-NEXT:    ret i1 [[CMP]]
 447 ;
 448   %mul = shl nuw i16 %x, 1
 449   %cmp = icmp eq i16 %x, %mul
 450   ret i1 %cmp
 451 }
 452
 453 ; The additional muls in these tests are necessary to actually
 454 ; test the isKnownNonEqual() code, rather than InstSimplify's own
 455 ; comparison folding.
 456
 457 define i1 @shl_shl_nuw(i8 %B, i8 %shift) {
 458 ; CHECK-LABEL: @shl_shl_nuw(
 459 ; CHECK-NEXT:    ret i1 false
 460 ;
 461   %A = add i8 %B, 1
 462   %A.op = shl nuw i8 %A, %shift
 463   %B.op = shl nuw i8 %B, %shift
 464   %A.op2 = mul nuw i8 %A.op, 3
 465   %B.op2 = mul nuw i8 %B.op, 3
 466   %cmp = icmp eq i8 %A.op2, %B.op2
 467   ret i1 %cmp
 468 }
 469
 470 define i1 @shl_shl_nsw(i8 %B, i8 %shift) {
 471 ; CHECK-LABEL: @shl_shl_nsw(
 472 ; CHECK-NEXT:    ret i1 false
 473 ;
 474   %A = add i8 %B, 1
 475   %A.op = shl nsw i8 %A, %shift
 476   %B.op = shl nsw i8 %B, %shift
 477   %A.op2 = mul nuw i8 %A.op, 3
 478   %B.op2 = mul nuw i8 %B.op, 3
 479   %cmp = icmp eq i8 %A.op2, %B.op2
 480   ret i1 %cmp
 481 }
 482
 483 define i1 @shl_shl_may_wrap(i8 %B, i8 %shift) {
 484 ; CHECK-LABEL: @shl_shl_may_wrap(
 485 ; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
 486 ; CHECK-NEXT:    [[A_OP:%.*]] = shl i8 [[A]], [[SHIFT:%.*]]
 487 ; CHECK-NEXT:    [[B_OP:%.*]] = shl nsw i8 [[B]], [[SHIFT]]
 488 ; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
 489 ; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
 490 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
 491 ; CHECK-NEXT:    ret i1 [[CMP]]
 492 ;
 493   %A = add i8 %B, 1
 494   %A.op = shl i8 %A, %shift
 495   %B.op = shl nsw i8 %B, %shift
 496   %A.op2 = mul nuw i8 %A.op, 3
 497   %B.op2 = mul nuw i8 %B.op, 3
 498   %cmp = icmp eq i8 %A.op2, %B.op2
 499   ret i1 %cmp
 500 }
 501
 502 define i1 @shl_shl_mixed_wrap(i8 %B, i8 %shift) {
 503 ; CHECK-LABEL: @shl_shl_mixed_wrap(
 504 ; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
 505 ; CHECK-NEXT:    [[A_OP:%.*]] = shl nuw i8 [[A]], [[SHIFT:%.*]]
 506 ; CHECK-NEXT:    [[B_OP:%.*]] = shl nsw i8 [[B]], [[SHIFT]]
 507 ; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
 508 ; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
 509 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
 510 ; CHECK-NEXT:    ret i1 [[CMP]]
 511 ;
 512   %A = add i8 %B, 1
 513   %A.op = shl nuw i8 %A, %shift
 514   %B.op = shl nsw i8 %B, %shift
 515   %A.op2 = mul nuw i8 %A.op, 3
 516   %B.op2 = mul nuw i8 %B.op, 3
 517   %cmp = icmp eq i8 %A.op2, %B.op2
 518   ret i1 %cmp
 519 }
 520
 521 define i1 @shl_shl_may_be_equal(i8 %A, i8 %B, i8 %shift) {
 522 ; CHECK-LABEL: @shl_shl_may_be_equal(
 523 ; CHECK-NEXT:    [[A_OP:%.*]] = shl nuw i8 [[A:%.*]], [[SHIFT:%.*]]
 524 ; CHECK-NEXT:    [[B_OP:%.*]] = shl nuw i8 [[B:%.*]], [[SHIFT]]
 525 ; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
 526 ; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
 527 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
 528 ; CHECK-NEXT:    ret i1 [[CMP]]
 529 ;
 530   %A.op = shl nuw i8 %A, %shift
 531   %B.op = shl nuw i8 %B, %shift
 532   %A.op2 = mul nuw i8 %A.op, 3
 533   %B.op2 = mul nuw i8 %B.op, 3
 534   %cmp = icmp eq i8 %A.op2, %B.op2
 535   ret i1 %cmp
 536 }
 537
 538 define i1 @ashr_ashr_exact(i8 %B, i8 %shift) {
 539 ; CHECK-LABEL: @ashr_ashr_exact(
 540 ; CHECK-NEXT:    ret i1 false
 541 ;
 542   %A = add i8 %B, 1
 543   %A.op = ashr exact i8 %A, %shift
 544   %B.op = ashr exact i8 %B, %shift
 545   %A.op2 = mul nuw i8 %A.op, 3
 546   %B.op2 = mul nuw i8 %B.op, 3
 547   %cmp = icmp eq i8 %A.op2, %B.op2
 548   ret i1 %cmp
 549 }
 550
 551 define i1 @ashr_ashr_discard_bits(i8 %B, i8 %shift) {
 552 ; CHECK-LABEL: @ashr_ashr_discard_bits(
 553 ; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
 554 ; CHECK-NEXT:    [[A_OP:%.*]] = ashr i8 [[A]], [[SHIFT:%.*]]
 555 ; CHECK-NEXT:    [[B_OP:%.*]] = ashr exact i8 [[B]], [[SHIFT]]
 556 ; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
 557 ; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
 558 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
 559 ; CHECK-NEXT:    ret i1 [[CMP]]
 560 ;
 561   %A = add i8 %B, 1
 562   %A.op = ashr i8 %A, %shift
 563   %B.op = ashr exact i8 %B, %shift
 564   %A.op2 = mul nuw i8 %A.op, 3
 565   %B.op2 = mul nuw i8 %B.op, 3
 566   %cmp = icmp eq i8 %A.op2, %B.op2
 567   ret i1 %cmp
 568 }
 569
 570 define i1 @ashr_ashr_may_be_equal(i8 %A, i8 %B, i8 %shift) {
 571 ; CHECK-LABEL: @ashr_ashr_may_be_equal(
 572 ; CHECK-NEXT:    [[A_OP:%.*]] = ashr exact i8 [[A:%.*]], [[SHIFT:%.*]]
 573 ; CHECK-NEXT:    [[B_OP:%.*]] = ashr exact i8 [[B:%.*]], [[SHIFT]]
 574 ; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
 575 ; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
 576 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
 577 ; CHECK-NEXT:    ret i1 [[CMP]]
 578 ;
 579   %A.op = ashr exact i8 %A, %shift
 580   %B.op = ashr exact i8 %B, %shift
 581   %A.op2 = mul nuw i8 %A.op, 3
 582   %B.op2 = mul nuw i8 %B.op, 3
 583   %cmp = icmp eq i8 %A.op2, %B.op2
 584   ret i1 %cmp
 585 }
 586
 587 define i1 @lshr_lshr_exact(i8 %B, i8 %shift) {
 588 ; CHECK-LABEL: @lshr_lshr_exact(
 589 ; CHECK-NEXT:    ret i1 false
 590 ;
 591   %A = add i8 %B, 1
 592   %A.op = lshr exact i8 %A, %shift
 593   %B.op = lshr exact i8 %B, %shift
 594   %A.op2 = mul nuw i8 %A.op, 3
 595   %B.op2 = mul nuw i8 %B.op, 3
 596   %cmp = icmp eq i8 %A.op2, %B.op2
 597   ret i1 %cmp
 598 }
 599
 600 define i1 @lshr_lshr_discard_bits(i8 %B, i8 %shift) {
 601 ; CHECK-LABEL: @lshr_lshr_discard_bits(
 602 ; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
 603 ; CHECK-NEXT:    [[A_OP:%.*]] = lshr i8 [[A]], [[SHIFT:%.*]]
 604 ; CHECK-NEXT:    [[B_OP:%.*]] = lshr exact i8 [[B]], [[SHIFT]]
 605 ; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
 606 ; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
 607 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
 608 ; CHECK-NEXT:    ret i1 [[CMP]]
 609 ;
 610   %A = add i8 %B, 1
 611   %A.op = lshr i8 %A, %shift
 612   %B.op = lshr exact i8 %B, %shift
 613   %A.op2 = mul nuw i8 %A.op, 3
 614   %B.op2 = mul nuw i8 %B.op, 3
 615   %cmp = icmp eq i8 %A.op2, %B.op2
 616   ret i1 %cmp
 617 }
 618
 619 define i1 @lshr_lshr_may_be_equal(i8 %A, i8 %B, i8 %shift) {
 620 ; CHECK-LABEL: @lshr_lshr_may_be_equal(
 621 ; CHECK-NEXT:    [[A_OP:%.*]] = lshr exact i8 [[A:%.*]], [[SHIFT:%.*]]
 622 ; CHECK-NEXT:    [[B_OP:%.*]] = lshr exact i8 [[B:%.*]], [[SHIFT]]
 623 ; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
 624 ; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
 625 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
 626 ; CHECK-NEXT:    ret i1 [[CMP]]
 627 ;
 628   %A.op = lshr exact i8 %A, %shift
 629   %B.op = lshr exact i8 %B, %shift
 630   %A.op2 = mul nuw i8 %A.op, 3
 631   %B.op2 = mul nuw i8 %B.op, 3
 632   %cmp = icmp eq i8 %A.op2, %B.op2
 633   ret i1 %cmp
 634 }
 635
 636 define i1 @recurrence_add_neq(i8 %A) {
 637 ; CHECK-LABEL: @recurrence_add_neq(
 638 ; CHECK-NEXT:  entry:
 639 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
 640 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 641 ; CHECK:       loop:
 642 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 643 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 644 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 645 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 646 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
 647 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
 648 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 649 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 650 ; CHECK:       exit:
 651 ; CHECK-NEXT:    ret i1 false
 652 ;
 653 entry:
 654   %B = add i8 %A, 1
 655   br label %loop
 656 loop:
 657   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 658   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
 659   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
 660   %iv.next = add i64 %iv, 1
 661   %A.iv.next = add i8 %A.iv, 1
 662   %B.iv.next = add i8 %B.iv, 1
 663   %cmp = icmp ne i64 %iv.next, 10
 664   br i1 %cmp, label %loop, label %exit
 665 exit:
 666   %res = icmp eq i8 %A.iv, %B.iv
 667   ret i1 %res
 668 }
 669
 670 define i1 @recurrence_add_eq(i8 %A) {
 671 ; CHECK-LABEL: @recurrence_add_eq(
 672 ; CHECK-NEXT:  entry:
 673 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 674 ; CHECK:       loop:
 675 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 676 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 677 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 678 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 679 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
 680 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
 681 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 682 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 683 ; CHECK:       exit:
 684 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
 685 ; CHECK-NEXT:    ret i1 [[RES]]
 686 ;
 687 entry:
 688   %B = add i8 %A, 0
 689   br label %loop
 690 loop:
 691   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 692   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
 693   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
 694   %iv.next = add i64 %iv, 1
 695   %A.iv.next = add i8 %A.iv, 1
 696   %B.iv.next = add i8 %B.iv, 1
 697   %cmp = icmp ne i64 %iv.next, 10
 698   br i1 %cmp, label %loop, label %exit
 699 exit:
 700   %res = icmp eq i8 %A.iv, %B.iv
 701   ret i1 %res
 702 }
 703
 704 define i1 @recurrence_add_unknown(i8 %A, i8 %B) {
 705 ; CHECK-LABEL: @recurrence_add_unknown(
 706 ; CHECK-NEXT:  entry:
 707 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 708 ; CHECK:       loop:
 709 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 710 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 711 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 712 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 713 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
 714 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
 715 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 716 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 717 ; CHECK:       exit:
 718 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
 719 ; CHECK-NEXT:    ret i1 [[RES]]
 720 ;
 721 entry:
 722   br label %loop
 723 loop:
 724   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 725   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
 726   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
 727   %iv.next = add i64 %iv, 1
 728   %A.iv.next = add i8 %A.iv, 1
 729   %B.iv.next = add i8 %B.iv, 1
 730   %cmp = icmp ne i64 %iv.next, 10
 731   br i1 %cmp, label %loop, label %exit
 732 exit:
 733   %res = icmp eq i8 %A.iv, %B.iv
 734   ret i1 %res
 735 }
 736
 737 ; If the steps are different, the invertibility is not enough
 738 ; (Though, in this case, we could prove neq with different logic)
 739 define i1 @recurrence_add_diff_step(i8 %A) {
 740 ; CHECK-LABEL: @recurrence_add_diff_step(
 741 ; CHECK-NEXT:  entry:
 742 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
 743 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 744 ; CHECK:       loop:
 745 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 746 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 747 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 748 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 749 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
 750 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 2
 751 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 752 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 753 ; CHECK:       exit:
 754 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
 755 ; CHECK-NEXT:    ret i1 [[RES]]
 756 ;
 757 entry:
 758   %B = add i8 %A, 1
 759   br label %loop
 760 loop:
 761   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 762   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
 763   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
 764   %iv.next = add i64 %iv, 1
 765   %A.iv.next = add i8 %A.iv, 1
 766   %B.iv.next = add i8 %B.iv, 2
 767   %cmp = icmp ne i64 %iv.next, 10
 768   br i1 %cmp, label %loop, label %exit
 769 exit:
 770   %res = icmp eq i8 %A.iv, %B.iv
 771   ret i1 %res
 772 }
 773
 774 define i1 @recurrence_add_op_order(i8 %A) {
 775 ; CHECK-LABEL: @recurrence_add_op_order(
 776 ; CHECK-NEXT:  entry:
 777 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
 778 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 779 ; CHECK:       loop:
 780 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 781 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 782 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 783 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 784 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 1, [[A_IV]]
 785 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 1, [[B_IV]]
 786 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 787 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 788 ; CHECK:       exit:
 789 ; CHECK-NEXT:    ret i1 false
 790 ;
 791 entry:
 792   %B = add i8 %A, 1
 793   br label %loop
 794 loop:
 795   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 796   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
 797   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
 798   %iv.next = add i64 %iv, 1
 799   %A.iv.next = add i8 1, %A.iv
 800   %B.iv.next = add i8 1, %B.iv
 801   %cmp = icmp ne i64 %iv.next, 10
 802   br i1 %cmp, label %loop, label %exit
 803 exit:
 804   %res = icmp eq i8 %A.iv, %B.iv
 805   ret i1 %res
 806 }
 807
 808 ; Just to show that phi operand order doesn't matter
 809 define i1 @recurrence_add_neq_phi_order(i8 %A) {
 810 ; CHECK-LABEL: @recurrence_add_neq_phi_order(
 811 ; CHECK-NEXT:  entry:
 812 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
 813 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 814 ; CHECK:       loop:
 815 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
 816 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A_IV_NEXT:%.*]], [[LOOP]] ], [ [[A]], [[ENTRY]] ]
 817 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B_IV_NEXT:%.*]], [[LOOP]] ], [ [[B]], [[ENTRY]] ]
 818 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 819 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
 820 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
 821 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 822 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 823 ; CHECK:       exit:
 824 ; CHECK-NEXT:    ret i1 false
 825 ;
 826 entry:
 827   %B = add i8 %A, 1
 828   br label %loop
 829 loop:
 830   %iv = phi i64 [%iv.next, %loop], [0, %entry]
 831   %A.iv = phi i8 [%A.iv.next, %loop], [%A, %entry]
 832   %B.iv = phi i8 [%B.iv.next, %loop], [%B, %entry]
 833   %iv.next = add i64 %iv, 1
 834   %A.iv.next = add i8 %A.iv, 1
 835   %B.iv.next = add i8 %B.iv, 1
 836   %cmp = icmp ne i64 %iv.next, 10
 837   br i1 %cmp, label %loop, label %exit
 838 exit:
 839   %res = icmp eq i8 %A.iv, %B.iv
 840   ret i1 %res
 841 }
 842
 843 ; Demonstrate case where phi operand orders differ and thus
 844 ; there's no single operand index to recurse through
 845 define i1 @recurrence_add_phi_different_order1(i8 %A) {
 846 ; CHECK-LABEL: @recurrence_add_phi_different_order1(
 847 ; CHECK-NEXT:  entry:
 848 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
 849 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 850 ; CHECK:       loop:
 851 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
 852 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 853 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B_IV_NEXT:%.*]], [[LOOP]] ], [ [[B]], [[ENTRY]] ]
 854 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 855 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
 856 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
 857 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 858 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 859 ; CHECK:       exit:
 860 ; CHECK-NEXT:    ret i1 false
 861 ;
 862 entry:
 863   %B = add i8 %A, 1
 864   br label %loop
 865 loop:
 866   %iv = phi i64 [%iv.next, %loop], [0, %entry]
 867   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
 868   %B.iv = phi i8 [%B.iv.next, %loop], [%B, %entry]
 869   %iv.next = add i64 %iv, 1
 870   %A.iv.next = add i8 %A.iv, 1
 871   %B.iv.next = add i8 %B.iv, 1
 872   %cmp = icmp ne i64 %iv.next, 10
 873   br i1 %cmp, label %loop, label %exit
 874 exit:
 875   %res = icmp eq i8 %A.iv, %B.iv
 876   ret i1 %res
 877 }
 878
 879 define i1 @recurrence_add_phi_different_order2(i8 %A) {
 880 ; CHECK-LABEL: @recurrence_add_phi_different_order2(
 881 ; CHECK-NEXT:  entry:
 882 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
 883 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 884 ; CHECK:       loop:
 885 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
 886 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A_IV_NEXT:%.*]], [[LOOP]] ], [ [[A]], [[ENTRY]] ]
 887 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 888 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 889 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
 890 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
 891 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 892 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 893 ; CHECK:       exit:
 894 ; CHECK-NEXT:    ret i1 false
 895 ;
 896 entry:
 897   %B = add i8 %A, 1
 898   br label %loop
 899 loop:
 900   %iv = phi i64 [%iv.next, %loop], [0, %entry]
 901   %A.iv = phi i8 [%A.iv.next, %loop], [%A, %entry]
 902   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
 903   %iv.next = add i64 %iv, 1
 904   %A.iv.next = add i8 %A.iv, 1
 905   %B.iv.next = add i8 %B.iv, 1
 906   %cmp = icmp ne i64 %iv.next, 10
 907   br i1 %cmp, label %loop, label %exit
 908 exit:
 909   %res = icmp eq i8 %A.iv, %B.iv
 910   ret i1 %res
 911 }
 912
 913 define i1 @recurrence_sub_neq(i8 %A) {
 914 ; CHECK-LABEL: @recurrence_sub_neq(
 915 ; CHECK-NEXT:  entry:
 916 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
 917 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 918 ; CHECK:       loop:
 919 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 920 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 921 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 922 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 923 ; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], 1
 924 ; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 [[B_IV]], 1
 925 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 926 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 927 ; CHECK:       exit:
 928 ; CHECK-NEXT:    ret i1 false
 929 ;
 930 entry:
 931   %B = add i8 %A, 1
 932   br label %loop
 933 loop:
 934   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 935   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
 936   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
 937   %iv.next = add i64 %iv, 1
 938   %A.iv.next = sub i8 %A.iv, 1
 939   %B.iv.next = sub i8 %B.iv, 1
 940   %cmp = icmp ne i64 %iv.next, 10
 941   br i1 %cmp, label %loop, label %exit
 942 exit:
 943   %res = icmp eq i8 %A.iv, %B.iv
 944   ret i1 %res
 945 }
 946
 947 define i1 @recurrence_sub_eq(i8 %A) {
 948 ; CHECK-LABEL: @recurrence_sub_eq(
 949 ; CHECK-NEXT:  entry:
 950 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 951 ; CHECK:       loop:
 952 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 953 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 954 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 955 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 956 ; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], 1
 957 ; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 [[B_IV]], 1
 958 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 959 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 960 ; CHECK:       exit:
 961 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
 962 ; CHECK-NEXT:    ret i1 [[RES]]
 963 ;
 964 entry:
 965   %B = add i8 %A, 0
 966   br label %loop
 967 loop:
 968   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 969   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
 970   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
 971   %iv.next = add i64 %iv, 1
 972   %A.iv.next = sub i8 %A.iv, 1
 973   %B.iv.next = sub i8 %B.iv, 1
 974   %cmp = icmp ne i64 %iv.next, 10
 975   br i1 %cmp, label %loop, label %exit
 976 exit:
 977   %res = icmp eq i8 %A.iv, %B.iv
 978   ret i1 %res
 979 }
 980
 981 define i1 @recurrence_sub_unknown(i8 %A, i8 %B) {
 982 ; CHECK-LABEL: @recurrence_sub_unknown(
 983 ; CHECK-NEXT:  entry:
 984 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 985 ; CHECK:       loop:
 986 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 987 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 988 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 989 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 990 ; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], 1
 991 ; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 [[B_IV]], 1
 992 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 993 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 994 ; CHECK:       exit:
 995 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
 996 ; CHECK-NEXT:    ret i1 [[RES]]
 997 ;
 998 entry:
 999   br label %loop
1000 loop:
1001   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1002   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1003   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1004   %iv.next = add i64 %iv, 1
1005   %A.iv.next = sub i8 %A.iv, 1
1006   %B.iv.next = sub i8 %B.iv, 1
1007   %cmp = icmp ne i64 %iv.next, 10
1008   br i1 %cmp, label %loop, label %exit
1009 exit:
1010   %res = icmp eq i8 %A.iv, %B.iv
1011   ret i1 %res
1012 }
1013
1014 define i1 @recurrence_sub_op_order(i8 %A) {
1015 ; CHECK-LABEL: @recurrence_sub_op_order(
1016 ; CHECK-NEXT:  entry:
1017 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1018 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1019 ; CHECK:       loop:
1020 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1021 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1022 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1023 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1024 ; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 1, [[A_IV]]
1025 ; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 1, [[B_IV]]
1026 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1027 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1028 ; CHECK:       exit:
1029 ; CHECK-NEXT:    ret i1 false
1030 ;
1031 entry:
1032   %B = add i8 %A, 1
1033   br label %loop
1034 loop:
1035   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1036   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1037   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1038   %iv.next = add i64 %iv, 1
1039   %A.iv.next = sub i8 1, %A.iv
1040   %B.iv.next = sub i8 1, %B.iv
1041   %cmp = icmp ne i64 %iv.next, 10
1042   br i1 %cmp, label %loop, label %exit
1043 exit:
1044   %res = icmp eq i8 %A.iv, %B.iv
1045   ret i1 %res
1046 }
1047
1048 define i1 @recurrence_sub_op_order2(i8 %A) {
1049 ; CHECK-LABEL: @recurrence_sub_op_order2(
1050 ; CHECK-NEXT:  entry:
1051 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1052 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1053 ; CHECK:       loop:
1054 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1055 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1056 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1057 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1058 ; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 1, [[A_IV]]
1059 ; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 [[B_IV]], 1
1060 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1061 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1062 ; CHECK:       exit:
1063 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1064 ; CHECK-NEXT:    ret i1 [[RES]]
1065 ;
1066 entry:
1067   %B = add i8 %A, 1
1068   br label %loop
1069 loop:
1070   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1071   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1072   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1073   %iv.next = add i64 %iv, 1
1074   %A.iv.next = sub i8 1, %A.iv
1075   %B.iv.next = sub i8 %B.iv, 1
1076   %cmp = icmp ne i64 %iv.next, 10
1077   br i1 %cmp, label %loop, label %exit
1078 exit:
1079   %res = icmp eq i8 %A.iv, %B.iv
1080   ret i1 %res
1081 }
1082
1083
1084 define i1 @recurrence_mul_neq(i8 %A) {
1085 ; CHECK-LABEL: @recurrence_mul_neq(
1086 ; CHECK-NEXT:  entry:
1087 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1088 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1089 ; CHECK:       loop:
1090 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1091 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1092 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1093 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1094 ; CHECK-NEXT:    [[A_IV_NEXT]] = mul nuw i8 [[A_IV]], 2
1095 ; CHECK-NEXT:    [[B_IV_NEXT]] = mul nuw i8 [[B_IV]], 2
1096 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1097 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1098 ; CHECK:       exit:
1099 ; CHECK-NEXT:    ret i1 false
1100 ;
1101 entry:
1102   %B = add i8 %A, 1
1103   br label %loop
1104 loop:
1105   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1106   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1107   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1108   %iv.next = add i64 %iv, 1
1109   %A.iv.next = mul nuw i8 %A.iv, 2
1110   %B.iv.next = mul nuw i8 %B.iv, 2
1111   %cmp = icmp ne i64 %iv.next, 10
1112   br i1 %cmp, label %loop, label %exit
1113 exit:
1114   %res = icmp eq i8 %A.iv, %B.iv
1115   ret i1 %res
1116 }
1117
1118 define i1 @recurrence_mul_eq(i8 %A) {
1119 ; CHECK-LABEL: @recurrence_mul_eq(
1120 ; CHECK-NEXT:  entry:
1121 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1122 ; CHECK:       loop:
1123 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1124 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1125 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1126 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1127 ; CHECK-NEXT:    [[A_IV_NEXT]] = mul nuw i8 [[A_IV]], 2
1128 ; CHECK-NEXT:    [[B_IV_NEXT]] = mul nuw i8 [[B_IV]], 2
1129 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1130 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1131 ; CHECK:       exit:
1132 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1133 ; CHECK-NEXT:    ret i1 [[RES]]
1134 ;
1135 entry:
1136   %B = add i8 %A, 0
1137   br label %loop
1138 loop:
1139   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1140   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1141   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1142   %iv.next = add i64 %iv, 1
1143   %A.iv.next = mul nuw i8 %A.iv, 2
1144   %B.iv.next = mul nuw i8 %B.iv, 2
1145   %cmp = icmp ne i64 %iv.next, 10
1146   br i1 %cmp, label %loop, label %exit
1147 exit:
1148   %res = icmp eq i8 %A.iv, %B.iv
1149   ret i1 %res
1150 }
1151
1152 define i1 @recurrence_mul_unknown(i8 %A, i8 %B) {
1153 ; CHECK-LABEL: @recurrence_mul_unknown(
1154 ; CHECK-NEXT:  entry:
1155 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1156 ; CHECK:       loop:
1157 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1158 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1159 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1160 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1161 ; CHECK-NEXT:    [[A_IV_NEXT]] = mul nuw i8 [[A_IV]], 2
1162 ; CHECK-NEXT:    [[B_IV_NEXT]] = mul nuw i8 [[B_IV]], 2
1163 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1164 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1165 ; CHECK:       exit:
1166 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1167 ; CHECK-NEXT:    ret i1 [[RES]]
1168 ;
1169 entry:
1170   br label %loop
1171 loop:
1172   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1173   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1174   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1175   %iv.next = add i64 %iv, 1
1176   %A.iv.next = mul nuw i8 %A.iv, 2
1177   %B.iv.next = mul nuw i8 %B.iv, 2
1178   %cmp = icmp ne i64 %iv.next, 10
1179   br i1 %cmp, label %loop, label %exit
1180 exit:
1181   %res = icmp eq i8 %A.iv, %B.iv
1182   ret i1 %res
1183 }
1184
1185 define i1 @recurrence_mul_noflags(i8 %A) {
1186 ; CHECK-LABEL: @recurrence_mul_noflags(
1187 ; CHECK-NEXT:  entry:
1188 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1189 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1190 ; CHECK:       loop:
1191 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1192 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1193 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1194 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1195 ; CHECK-NEXT:    [[A_IV_NEXT]] = mul i8 [[A_IV]], 2
1196 ; CHECK-NEXT:    [[B_IV_NEXT]] = mul i8 [[B_IV]], 2
1197 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1198 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1199 ; CHECK:       exit:
1200 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1201 ; CHECK-NEXT:    ret i1 [[RES]]
1202 ;
1203 entry:
1204   %B = add i8 %A, 1
1205   br label %loop
1206 loop:
1207   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1208   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1209   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1210   %iv.next = add i64 %iv, 1
1211   %A.iv.next = mul i8 %A.iv, 2
1212   %B.iv.next = mul i8 %B.iv, 2
1213   %cmp = icmp ne i64 %iv.next, 10
1214   br i1 %cmp, label %loop, label %exit
1215 exit:
1216   %res = icmp eq i8 %A.iv, %B.iv
1217   ret i1 %res
1218 }
1219
1220 define i1 @recurrence_shl_neq(i8 %A) {
1221 ; CHECK-LABEL: @recurrence_shl_neq(
1222 ; CHECK-NEXT:  entry:
1223 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1224 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1225 ; CHECK:       loop:
1226 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1227 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1228 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1229 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1230 ; CHECK-NEXT:    [[A_IV_NEXT]] = shl nuw i8 [[A_IV]], 1
1231 ; CHECK-NEXT:    [[B_IV_NEXT]] = shl nuw i8 [[B_IV]], 1
1232 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1233 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1234 ; CHECK:       exit:
1235 ; CHECK-NEXT:    ret i1 false
1236 ;
1237 entry:
1238   %B = add i8 %A, 1
1239   br label %loop
1240 loop:
1241   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1242   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1243   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1244   %iv.next = add i64 %iv, 1
1245   %A.iv.next = shl nuw i8 %A.iv, 1
1246   %B.iv.next = shl nuw i8 %B.iv, 1
1247   %cmp = icmp ne i64 %iv.next, 10
1248   br i1 %cmp, label %loop, label %exit
1249 exit:
1250   %res = icmp eq i8 %A.iv, %B.iv
1251   ret i1 %res
1252 }
1253
1254 define i1 @recurrence_shl_eq(i8 %A) {
1255 ; CHECK-LABEL: @recurrence_shl_eq(
1256 ; CHECK-NEXT:  entry:
1257 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1258 ; CHECK:       loop:
1259 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1260 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1261 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1262 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1263 ; CHECK-NEXT:    [[A_IV_NEXT]] = shl nuw i8 [[A_IV]], 1
1264 ; CHECK-NEXT:    [[B_IV_NEXT]] = shl nuw i8 [[B_IV]], 1
1265 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1266 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1267 ; CHECK:       exit:
1268 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1269 ; CHECK-NEXT:    ret i1 [[RES]]
1270 ;
1271 entry:
1272   %B = add i8 %A, 0
1273   br label %loop
1274 loop:
1275   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1276   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1277   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1278   %iv.next = add i64 %iv, 1
1279   %A.iv.next = shl nuw i8 %A.iv, 1
1280   %B.iv.next = shl nuw i8 %B.iv, 1
1281   %cmp = icmp ne i64 %iv.next, 10
1282   br i1 %cmp, label %loop, label %exit
1283 exit:
1284   %res = icmp eq i8 %A.iv, %B.iv
1285   ret i1 %res
1286 }
1287
1288 define i1 @recurrence_shl_unknown(i8 %A, i8 %B) {
1289 ; CHECK-LABEL: @recurrence_shl_unknown(
1290 ; CHECK-NEXT:  entry:
1291 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1292 ; CHECK:       loop:
1293 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1294 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1295 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1296 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1297 ; CHECK-NEXT:    [[A_IV_NEXT]] = shl nuw i8 [[A_IV]], 1
1298 ; CHECK-NEXT:    [[B_IV_NEXT]] = shl nuw i8 [[B_IV]], 1
1299 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1300 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1301 ; CHECK:       exit:
1302 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1303 ; CHECK-NEXT:    ret i1 [[RES]]
1304 ;
1305 entry:
1306   br label %loop
1307 loop:
1308   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1309   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1310   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1311   %iv.next = add i64 %iv, 1
1312   %A.iv.next = shl nuw i8 %A.iv, 1
1313   %B.iv.next = shl nuw i8 %B.iv, 1
1314   %cmp = icmp ne i64 %iv.next, 10
1315   br i1 %cmp, label %loop, label %exit
1316 exit:
1317   %res = icmp eq i8 %A.iv, %B.iv
1318   ret i1 %res
1319 }
1320
1321 define i1 @recurrence_shl_noflags(i8 %A) {
1322 ; CHECK-LABEL: @recurrence_shl_noflags(
1323 ; CHECK-NEXT:  entry:
1324 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1325 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1326 ; CHECK:       loop:
1327 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1328 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1329 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1330 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1331 ; CHECK-NEXT:    [[A_IV_NEXT]] = shl i8 [[A_IV]], 1
1332 ; CHECK-NEXT:    [[B_IV_NEXT]] = shl i8 [[B_IV]], 1
1333 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1334 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1335 ; CHECK:       exit:
1336 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1337 ; CHECK-NEXT:    ret i1 [[RES]]
1338 ;
1339 entry:
1340   %B = add i8 %A, 1
1341   br label %loop
1342 loop:
1343   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1344   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1345   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1346   %iv.next = add i64 %iv, 1
1347   %A.iv.next = shl i8 %A.iv, 1
1348   %B.iv.next = shl i8 %B.iv, 1
1349   %cmp = icmp ne i64 %iv.next, 10
1350   br i1 %cmp, label %loop, label %exit
1351 exit:
1352   %res = icmp eq i8 %A.iv, %B.iv
1353   ret i1 %res
1354 }
1355
1356 ; Represents a power function, but still invertable!
1357 define i1 @recurrence_shl_op_order(i8 %A) {
1358 ; CHECK-LABEL: @recurrence_shl_op_order(
1359 ; CHECK-NEXT:  entry:
1360 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1361 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1362 ; CHECK:       loop:
1363 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1364 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1365 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1366 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1367 ; CHECK-NEXT:    [[A_IV_NEXT]] = shl nuw i8 1, [[A_IV]]
1368 ; CHECK-NEXT:    [[B_IV_NEXT]] = shl nuw i8 1, [[B_IV]]
1369 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1370 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1371 ; CHECK:       exit:
1372 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1373 ; CHECK-NEXT:    ret i1 [[RES]]
1374 ;
1375 entry:
1376   %B = add i8 %A, 1
1377   br label %loop
1378 loop:
1379   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1380   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1381   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1382   %iv.next = add i64 %iv, 1
1383   %A.iv.next = shl nuw i8 1, %A.iv
1384   %B.iv.next = shl nuw i8 1, %B.iv
1385   %cmp = icmp ne i64 %iv.next, 10
1386   br i1 %cmp, label %loop, label %exit
1387 exit:
1388   %res = icmp eq i8 %A.iv, %B.iv
1389   ret i1 %res
1390 }
1391
1392 define i1 @recurrence_lshr_neq(i8 %A) {
1393 ; CHECK-LABEL: @recurrence_lshr_neq(
1394 ; CHECK-NEXT:  entry:
1395 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1396 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1397 ; CHECK:       loop:
1398 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1399 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1400 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1401 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1402 ; CHECK-NEXT:    [[A_IV_NEXT]] = lshr exact i8 [[A_IV]], 1
1403 ; CHECK-NEXT:    [[B_IV_NEXT]] = lshr exact i8 [[B_IV]], 1
1404 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1405 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1406 ; CHECK:       exit:
1407 ; CHECK-NEXT:    ret i1 false
1408 ;
1409 entry:
1410   %B = add i8 %A, 1
1411   br label %loop
1412 loop:
1413   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1414   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1415   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1416   %iv.next = add i64 %iv, 1
1417   %A.iv.next = lshr exact i8 %A.iv, 1
1418   %B.iv.next = lshr exact i8 %B.iv, 1
1419   %cmp = icmp ne i64 %iv.next, 10
1420   br i1 %cmp, label %loop, label %exit
1421 exit:
1422   %res = icmp eq i8 %A.iv, %B.iv
1423   ret i1 %res
1424 }
1425
1426 define i1 @recurrence_lshr_eq(i8 %A) {
1427 ; CHECK-LABEL: @recurrence_lshr_eq(
1428 ; CHECK-NEXT:  entry:
1429 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1430 ; CHECK:       loop:
1431 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1432 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1433 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1434 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1435 ; CHECK-NEXT:    [[A_IV_NEXT]] = lshr exact i8 [[A_IV]], 1
1436 ; CHECK-NEXT:    [[B_IV_NEXT]] = lshr exact i8 [[B_IV]], 1
1437 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1438 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1439 ; CHECK:       exit:
1440 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1441 ; CHECK-NEXT:    ret i1 [[RES]]
1442 ;
1443 entry:
1444   %B = add i8 %A, 0
1445   br label %loop
1446 loop:
1447   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1448   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1449   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1450   %iv.next = add i64 %iv, 1
1451   %A.iv.next = lshr exact i8 %A.iv, 1
1452   %B.iv.next = lshr exact i8 %B.iv, 1
1453   %cmp = icmp ne i64 %iv.next, 10
1454   br i1 %cmp, label %loop, label %exit
1455 exit:
1456   %res = icmp eq i8 %A.iv, %B.iv
1457   ret i1 %res
1458 }
1459
1460 define i1 @recurrence_lshr_unknown(i8 %A, i8 %B) {
1461 ; CHECK-LABEL: @recurrence_lshr_unknown(
1462 ; CHECK-NEXT:  entry:
1463 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1464 ; CHECK:       loop:
1465 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1466 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1467 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1468 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1469 ; CHECK-NEXT:    [[A_IV_NEXT]] = lshr exact i8 [[A_IV]], 1
1470 ; CHECK-NEXT:    [[B_IV_NEXT]] = lshr exact i8 [[B_IV]], 1
1471 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1472 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1473 ; CHECK:       exit:
1474 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1475 ; CHECK-NEXT:    ret i1 [[RES]]
1476 ;
1477 entry:
1478   br label %loop
1479 loop:
1480   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1481   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1482   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1483   %iv.next = add i64 %iv, 1
1484   %A.iv.next = lshr exact i8 %A.iv, 1
1485   %B.iv.next = lshr exact i8 %B.iv, 1
1486   %cmp = icmp ne i64 %iv.next, 10
1487   br i1 %cmp, label %loop, label %exit
1488 exit:
1489   %res = icmp eq i8 %A.iv, %B.iv
1490   ret i1 %res
1491 }
1492
1493 define i1 @recurrence_lshr_noflags(i8 %A) {
1494 ; CHECK-LABEL: @recurrence_lshr_noflags(
1495 ; CHECK-NEXT:  entry:
1496 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1497 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1498 ; CHECK:       loop:
1499 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1500 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1501 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1502 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1503 ; CHECK-NEXT:    [[A_IV_NEXT]] = lshr i8 [[A_IV]], 1
1504 ; CHECK-NEXT:    [[B_IV_NEXT]] = lshr i8 [[B_IV]], 1
1505 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1506 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1507 ; CHECK:       exit:
1508 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1509 ; CHECK-NEXT:    ret i1 [[RES]]
1510 ;
1511 entry:
1512   %B = add i8 %A, 1
1513   br label %loop
1514 loop:
1515   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1516   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1517   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1518   %iv.next = add i64 %iv, 1
1519   %A.iv.next = lshr i8 %A.iv, 1
1520   %B.iv.next = lshr i8 %B.iv, 1
1521   %cmp = icmp ne i64 %iv.next, 10
1522   br i1 %cmp, label %loop, label %exit
1523 exit:
1524   %res = icmp eq i8 %A.iv, %B.iv
1525   ret i1 %res
1526 }
1527
1528 define i1 @recurrence_lshr_op_order(i8 %A) {
1529 ; CHECK-LABEL: @recurrence_lshr_op_order(
1530 ; CHECK-NEXT:  entry:
1531 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1532 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1533 ; CHECK:       loop:
1534 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1535 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ 1, [[LOOP]] ]
1536 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ 1, [[LOOP]] ]
1537 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1538 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1539 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1540 ; CHECK:       exit:
1541 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1542 ; CHECK-NEXT:    ret i1 [[RES]]
1543 ;
1544 entry:
1545   %B = add i8 %A, 1
1546   br label %loop
1547 loop:
1548   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1549   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1550   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1551   %iv.next = add i64 %iv, 1
1552   %A.iv.next = lshr exact i8 1, %A.iv
1553   %B.iv.next = lshr exact i8 1, %B.iv
1554   %cmp = icmp ne i64 %iv.next, 10
1555   br i1 %cmp, label %loop, label %exit
1556 exit:
1557   %res = icmp eq i8 %A.iv, %B.iv
1558   ret i1 %res
1559 }
1560
1561
1562 define i1 @recurrence_ashr_neq(i8 %A) {
1563 ; CHECK-LABEL: @recurrence_ashr_neq(
1564 ; CHECK-NEXT:  entry:
1565 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1566 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1567 ; CHECK:       loop:
1568 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1569 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1570 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1571 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1572 ; CHECK-NEXT:    [[A_IV_NEXT]] = ashr exact i8 [[A_IV]], 1
1573 ; CHECK-NEXT:    [[B_IV_NEXT]] = ashr exact i8 [[B_IV]], 1
1574 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1575 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1576 ; CHECK:       exit:
1577 ; CHECK-NEXT:    ret i1 false
1578 ;
1579 entry:
1580   %B = add i8 %A, 1
1581   br label %loop
1582 loop:
1583   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1584   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1585   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1586   %iv.next = add i64 %iv, 1
1587   %A.iv.next = ashr exact i8 %A.iv, 1
1588   %B.iv.next = ashr exact i8 %B.iv, 1
1589   %cmp = icmp ne i64 %iv.next, 10
1590   br i1 %cmp, label %loop, label %exit
1591 exit:
1592   %res = icmp eq i8 %A.iv, %B.iv
1593   ret i1 %res
1594 }
1595
1596 define i1 @recurrence_ashr_eq(i8 %A) {
1597 ; CHECK-LABEL: @recurrence_ashr_eq(
1598 ; CHECK-NEXT:  entry:
1599 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1600 ; CHECK:       loop:
1601 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1602 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1603 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1604 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1605 ; CHECK-NEXT:    [[A_IV_NEXT]] = ashr exact i8 [[A_IV]], 1
1606 ; CHECK-NEXT:    [[B_IV_NEXT]] = ashr exact i8 [[B_IV]], 1
1607 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1608 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1609 ; CHECK:       exit:
1610 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1611 ; CHECK-NEXT:    ret i1 [[RES]]
1612 ;
1613 entry:
1614   %B = add i8 %A, 0
1615   br label %loop
1616 loop:
1617   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1618   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1619   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1620   %iv.next = add i64 %iv, 1
1621   %A.iv.next = ashr exact i8 %A.iv, 1
1622   %B.iv.next = ashr exact i8 %B.iv, 1
1623   %cmp = icmp ne i64 %iv.next, 10
1624   br i1 %cmp, label %loop, label %exit
1625 exit:
1626   %res = icmp eq i8 %A.iv, %B.iv
1627   ret i1 %res
1628 }
1629
1630 define i1 @recurrence_ashr_unknown(i8 %A, i8 %B) {
1631 ; CHECK-LABEL: @recurrence_ashr_unknown(
1632 ; CHECK-NEXT:  entry:
1633 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1634 ; CHECK:       loop:
1635 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1636 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1637 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1638 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1639 ; CHECK-NEXT:    [[A_IV_NEXT]] = ashr exact i8 [[A_IV]], 1
1640 ; CHECK-NEXT:    [[B_IV_NEXT]] = ashr exact i8 [[B_IV]], 1
1641 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1642 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1643 ; CHECK:       exit:
1644 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1645 ; CHECK-NEXT:    ret i1 [[RES]]
1646 ;
1647 entry:
1648   br label %loop
1649 loop:
1650   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1651   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1652   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1653   %iv.next = add i64 %iv, 1
1654   %A.iv.next = ashr exact i8 %A.iv, 1
1655   %B.iv.next = ashr exact i8 %B.iv, 1
1656   %cmp = icmp ne i64 %iv.next, 10
1657   br i1 %cmp, label %loop, label %exit
1658 exit:
1659   %res = icmp eq i8 %A.iv, %B.iv
1660   ret i1 %res
1661 }
1662
1663 define i1 @recurrence_ashr_noflags(i8 %A) {
1664 ; CHECK-LABEL: @recurrence_ashr_noflags(
1665 ; CHECK-NEXT:  entry:
1666 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1667 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1668 ; CHECK:       loop:
1669 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1670 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1671 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1672 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1673 ; CHECK-NEXT:    [[A_IV_NEXT]] = ashr i8 [[A_IV]], 1
1674 ; CHECK-NEXT:    [[B_IV_NEXT]] = ashr i8 [[B_IV]], 1
1675 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1676 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1677 ; CHECK:       exit:
1678 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1679 ; CHECK-NEXT:    ret i1 [[RES]]
1680 ;
1681 entry:
1682   %B = add i8 %A, 1
1683   br label %loop
1684 loop:
1685   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1686   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1687   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1688   %iv.next = add i64 %iv, 1
1689   %A.iv.next = ashr i8 %A.iv, 1
1690   %B.iv.next = ashr i8 %B.iv, 1
1691   %cmp = icmp ne i64 %iv.next, 10
1692   br i1 %cmp, label %loop, label %exit
1693 exit:
1694   %res = icmp eq i8 %A.iv, %B.iv
1695   ret i1 %res
1696 }
1697
1698 define i1 @PR50191_A(i32 %x) {
1699 ; CHECK-LABEL: @PR50191_A(
1700 ; CHECK-NEXT:  entry:
1701 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1702 ; CHECK:       loop:
1703 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1704 ; CHECK-NEXT:    [[P1:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY]] ], [ [[SUB1:%.*]], [[LOOP]] ]
1705 ; CHECK-NEXT:    [[P2:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[SUB2:%.*]], [[LOOP]] ]
1706 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1707 ; CHECK-NEXT:    [[SUB1]] = sub i32 [[P1]], [[P2]]
1708 ; CHECK-NEXT:    [[SUB2]] = sub i32 42, [[P2]]
1709 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1710 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1711 ; CHECK:       exit:
1712 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i32 [[P1]], [[P2]]
1713 ; CHECK-NEXT:    ret i1 [[RES]]
1714 ;
1715 entry:
1716   br label %loop
1717 loop:
1718   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1719   %p1 = phi i32 [%x, %entry ], [ %sub1, %loop ]
1720   %p2 = phi i32 [%x, %entry ], [ %sub2, %loop ]
1721   %iv.next = add i64 %iv, 1
1722   %sub1 = sub i32 %p1, %p2
1723   %sub2 = sub i32 42, %p2
1724   %cmp = icmp ne i64 %iv.next, 10
1725   br i1 %cmp, label %loop, label %exit
1726 exit:
1727   %res = icmp eq i32 %p1, %p2
1728   ret i1 %res
1729 }
1730
1731 define i1 @PR50191_B(i32 %x) {
1732 ; CHECK-LABEL: @PR50191_B(
1733 ; CHECK-NEXT:  entry:
1734 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1735 ; CHECK:       loop:
1736 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1737 ; CHECK-NEXT:    [[P1:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY]] ], [ [[SUB1:%.*]], [[LOOP]] ]
1738 ; CHECK-NEXT:    [[P2:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[SUB2:%.*]], [[LOOP]] ]
1739 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1740 ; CHECK-NEXT:    [[SUB1]] = sub i32 [[P2]], [[P1]]
1741 ; CHECK-NEXT:    [[SUB2]] = sub i32 [[P2]], 42
1742 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1743 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1744 ; CHECK:       exit:
1745 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i32 [[P1]], [[P2]]
1746 ; CHECK-NEXT:    ret i1 [[RES]]
1747 ;
1748 entry:
1749   br label %loop
1750 loop:
1751   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1752   %p1 = phi i32 [%x, %entry ], [ %sub1, %loop ]
1753   %p2 = phi i32 [%x, %entry ], [ %sub2, %loop ]
1754   %iv.next = add i64 %iv, 1
1755   %sub1 = sub i32 %p2, %p1
1756   %sub2 = sub i32 %p2, 42
1757   %cmp = icmp ne i64 %iv.next, 10
1758   br i1 %cmp, label %loop, label %exit
1759 exit:
1760   %res = icmp eq i32 %p1, %p2
1761   ret i1 %res
1762 }
1763
1764
1765 define i1 @mutual_recurrence_neq(i8 %A) {
1766 ; CHECK-LABEL: @mutual_recurrence_neq(
1767 ; CHECK-NEXT:  entry:
1768 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1769 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1770 ; CHECK:       loop:
1771 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1772 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1773 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[A_IV_NEXT]], [[LOOP]] ]
1774 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1775 ; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]
1776 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1777 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1778 ; CHECK:       exit:
1779 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1780 ; CHECK-NEXT:    ret i1 [[RES]]
1781 ;
1782 entry:
1783   %B = add i8 %A, 1
1784   br label %loop
1785 loop:
1786   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1787   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1788   %B.iv = phi i8 [%B, %entry], [%A.iv.next, %loop]
1789   %iv.next = add i64 %iv, 1
1790   %A.iv.next = sub i8 %A.iv, %B.iv
1791   %cmp = icmp ne i64 %iv.next, 10
1792   br i1 %cmp, label %loop, label %exit
1793 exit:
1794   %res = icmp eq i8 %A.iv, %B.iv
1795   ret i1 %res
1796 }
1797
1798 define i1 @mutual_recurrence_eq(i8 %A) {
1799 ; CHECK-LABEL: @mutual_recurrence_eq(
1800 ; CHECK-NEXT:  entry:
1801 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1802 ; CHECK:       loop:
1803 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1804 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1805 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT]], [[LOOP]] ]
1806 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1807 ; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]
1808 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1809 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1810 ; CHECK:       exit:
1811 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1812 ; CHECK-NEXT:    ret i1 [[RES]]
1813 ;
1814 entry:
1815   br label %loop
1816 loop:
1817   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1818   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1819   %B.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1820   %iv.next = add i64 %iv, 1
1821   %A.iv.next = sub i8 %A.iv, %B.iv
1822   %cmp = icmp ne i64 %iv.next, 10
1823   br i1 %cmp, label %loop, label %exit
1824 exit:
1825   %res = icmp eq i8 %A.iv, %B.iv
1826   ret i1 %res
1827 }
1828
1829 ; Illustrate a case where A_IV_i == B_IV_i for all i > 0, but A_IV_0 != B_IV_0.
1830 ; (E.g. This pair of mutually defined recurrences are not invertible.)
1831 define i1 @recurrence_collapse(i8 %A) {
1832 ; CHECK-LABEL: @recurrence_collapse(
1833 ; CHECK-NEXT:  entry:
1834 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
1835 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1836 ; CHECK:       loop:
1837 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1838 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
1839 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
1840 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1841 ; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]
1842 ; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]
1843 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
1844 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
1845 ; CHECK:       exit:
1846 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
1847 ; CHECK-NEXT:    ret i1 [[RES]]
1848 ;
1849 entry:
1850   %B = add i8 %A, 1
1851   br label %loop
1852 loop:
1853   %iv = phi i64 [0, %entry], [%iv.next, %loop]
1854   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
1855   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
1856   %iv.next = add i64 %iv, 1
1857   %A.iv.next = sub i8 %A.iv, %B.iv
1858   %B.iv.next = sub i8 %A.iv, %B.iv
1859   %cmp = icmp ne i64 %iv.next, 10
1860   br i1 %cmp, label %loop, label %exit
1861 exit:
1862   %res = icmp eq i8 %A.iv, %B.iv
1863   ret i1 %res
1864 }
1865
1866 ; Illustrate if 2 pointers are non-equal when one of them is a recursive GEP.
1867 define i1 @icmp_recursiveGEP_withPtr(ptr %val1) {
1868 ; CHECK-LABEL: @icmp_recursiveGEP_withPtr(
1869 ; CHECK-NEXT:  entry:
1870 ; CHECK-NEXT:    [[CMP_I:%.*]] = icmp eq ptr [[VAL1:%.*]], null
1871 ; CHECK-NEXT:    br i1 [[CMP_I]], label [[_Z9STRINGLENPKS_EXIT:%.*]], label [[WHILE_COND_I:%.*]]
1872 ; CHECK:       while.cond.i:
1873 ; CHECK-NEXT:    [[A_PN_I:%.*]] = phi ptr [ [[TEST_0_I:%.*]], [[WHILE_COND_I]] ], [ [[VAL1]], [[ENTRY:%.*]] ]
1874 ; CHECK-NEXT:    [[TEST_0_I]] = getelementptr inbounds i8, ptr [[A_PN_I]], i64 1
1875 ; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[TEST_0_I]], align 2
1876 ; CHECK-NEXT:    [[CMP3_NOT_I:%.*]] = icmp eq i8 [[TMP0]], 0
1877 ; CHECK-NEXT:    br i1 [[CMP3_NOT_I]], label [[WHILE_END_I:%.*]], label [[WHILE_COND_I]]
1878 ; CHECK:       while.end.i:
1879 ; CHECK-NEXT:    br label [[_Z9STRINGLENPKS_EXIT]]
1880 ; CHECK:       _Z9stringlenPKs.exit:
1881 ; CHECK-NEXT:    [[RETVAL_0_I:%.*]] = phi i1 [ false, [[WHILE_END_I]] ], [ true, [[ENTRY]] ]
1882 ; CHECK-NEXT:    ret i1 [[RETVAL_0_I]]
1883 ;
1884 entry:
1885   %cmp.i = icmp eq ptr %val1, null
1886   br i1 %cmp.i, label %_Z9stringlenPKs.exit, label %while.cond.i
1887
1888 while.cond.i:
1889   %a.pn.i = phi ptr [ %test.0.i, %while.cond.i ], [ %val1, %entry ]
1890   %test.0.i = getelementptr inbounds i8, ptr %a.pn.i, i64 1
1891   %0 = load i8, ptr %test.0.i, align 2
1892   %cmp3.not.i = icmp eq i8 %0, 0
1893   br i1 %cmp3.not.i, label %while.end.i, label %while.cond.i
1894
1895 while.end.i:
1896   %bool = icmp eq ptr %test.0.i, %val1
1897   br label %_Z9stringlenPKs.exit
1898
1899 _Z9stringlenPKs.exit:
1900   %retval.0.i = phi i1 [ %bool, %while.end.i ], [ true, %entry ]
1901   ret i1 %retval.0.i
1902 }
1903
1904 !0 = !{ i8 1, i8 5 }