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