1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -passes=instsimplify < %s -S | FileCheck %s 3 4define 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 14define 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 24define 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 33define 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 44define 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 55define 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 70define 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 85define 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 97define 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 109define 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 121define 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. 134define 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 150define 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 162define 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 175define 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 188define 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 206define 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 217define 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 227define 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 237define 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 247define 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 257define 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 270define 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 281define 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 294define 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; 306entry: 307 br label %loop 308loop: 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 314exit: 315 %cmp = icmp ne i8 %A, %B 316 ret i1 %cmp 317} 318 319define 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; 342entry: 343 br label %bb0 344 345bb0: 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 350switch.block: 351 switch i32 %switch.cond, label %bb1 [ 352 i32 0, label %epilogue 353 i32 1, label %epilogue 354 ] 355 356bb1: 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 361epilogue: 362 br label %bb1 363 364exit: 365 %ret = icmp eq i32 %phiA.0, %phiB.0 366 ret i1 %ret 367} 368 369define 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; 383entry: 384 br label %loop 385loop: 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 391exit: 392 %cmp = icmp ne i8 %A, %B 393 ret i1 %cmp 394} 395 396define 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 406define 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 416define 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 429define 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 442define 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 457define 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 470define 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 483define 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 502define 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 521define 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 538define 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 551define 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 570define 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 587define 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 600define 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 619define 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 636define 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; 653entry: 654 %B = add i8 %A, 1 655 br label %loop 656loop: 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 665exit: 666 %res = icmp eq i8 %A.iv, %B.iv 667 ret i1 %res 668} 669 670define 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; 687entry: 688 %B = add i8 %A, 0 689 br label %loop 690loop: 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 699exit: 700 %res = icmp eq i8 %A.iv, %B.iv 701 ret i1 %res 702} 703 704define 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; 721entry: 722 br label %loop 723loop: 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 732exit: 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) 739define 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; 757entry: 758 %B = add i8 %A, 1 759 br label %loop 760loop: 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 769exit: 770 %res = icmp eq i8 %A.iv, %B.iv 771 ret i1 %res 772} 773 774define 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; 791entry: 792 %B = add i8 %A, 1 793 br label %loop 794loop: 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 803exit: 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 809define 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; 826entry: 827 %B = add i8 %A, 1 828 br label %loop 829loop: 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 838exit: 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 845define 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; 862entry: 863 %B = add i8 %A, 1 864 br label %loop 865loop: 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 874exit: 875 %res = icmp eq i8 %A.iv, %B.iv 876 ret i1 %res 877} 878 879define 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; 896entry: 897 %B = add i8 %A, 1 898 br label %loop 899loop: 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 908exit: 909 %res = icmp eq i8 %A.iv, %B.iv 910 ret i1 %res 911} 912 913define 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; 930entry: 931 %B = add i8 %A, 1 932 br label %loop 933loop: 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 942exit: 943 %res = icmp eq i8 %A.iv, %B.iv 944 ret i1 %res 945} 946 947define 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; 964entry: 965 %B = add i8 %A, 0 966 br label %loop 967loop: 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 976exit: 977 %res = icmp eq i8 %A.iv, %B.iv 978 ret i1 %res 979} 980 981define 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; 998entry: 999 br label %loop 1000loop: 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 1009exit: 1010 %res = icmp eq i8 %A.iv, %B.iv 1011 ret i1 %res 1012} 1013 1014define 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; 1031entry: 1032 %B = add i8 %A, 1 1033 br label %loop 1034loop: 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 1043exit: 1044 %res = icmp eq i8 %A.iv, %B.iv 1045 ret i1 %res 1046} 1047 1048define 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; 1066entry: 1067 %B = add i8 %A, 1 1068 br label %loop 1069loop: 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 1078exit: 1079 %res = icmp eq i8 %A.iv, %B.iv 1080 ret i1 %res 1081} 1082 1083 1084define 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; 1101entry: 1102 %B = add i8 %A, 1 1103 br label %loop 1104loop: 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 1113exit: 1114 %res = icmp eq i8 %A.iv, %B.iv 1115 ret i1 %res 1116} 1117 1118define 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; 1135entry: 1136 %B = add i8 %A, 0 1137 br label %loop 1138loop: 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 1147exit: 1148 %res = icmp eq i8 %A.iv, %B.iv 1149 ret i1 %res 1150} 1151 1152define 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; 1169entry: 1170 br label %loop 1171loop: 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 1180exit: 1181 %res = icmp eq i8 %A.iv, %B.iv 1182 ret i1 %res 1183} 1184 1185define 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; 1203entry: 1204 %B = add i8 %A, 1 1205 br label %loop 1206loop: 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 1215exit: 1216 %res = icmp eq i8 %A.iv, %B.iv 1217 ret i1 %res 1218} 1219 1220define 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; 1237entry: 1238 %B = add i8 %A, 1 1239 br label %loop 1240loop: 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 1249exit: 1250 %res = icmp eq i8 %A.iv, %B.iv 1251 ret i1 %res 1252} 1253 1254define 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; 1271entry: 1272 %B = add i8 %A, 0 1273 br label %loop 1274loop: 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 1283exit: 1284 %res = icmp eq i8 %A.iv, %B.iv 1285 ret i1 %res 1286} 1287 1288define 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; 1305entry: 1306 br label %loop 1307loop: 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 1316exit: 1317 %res = icmp eq i8 %A.iv, %B.iv 1318 ret i1 %res 1319} 1320 1321define 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; 1339entry: 1340 %B = add i8 %A, 1 1341 br label %loop 1342loop: 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 1351exit: 1352 %res = icmp eq i8 %A.iv, %B.iv 1353 ret i1 %res 1354} 1355 1356; Represents a power function, but still invertable! 1357define 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; 1375entry: 1376 %B = add i8 %A, 1 1377 br label %loop 1378loop: 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 1387exit: 1388 %res = icmp eq i8 %A.iv, %B.iv 1389 ret i1 %res 1390} 1391 1392define 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; 1409entry: 1410 %B = add i8 %A, 1 1411 br label %loop 1412loop: 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 1421exit: 1422 %res = icmp eq i8 %A.iv, %B.iv 1423 ret i1 %res 1424} 1425 1426define 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; 1443entry: 1444 %B = add i8 %A, 0 1445 br label %loop 1446loop: 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 1455exit: 1456 %res = icmp eq i8 %A.iv, %B.iv 1457 ret i1 %res 1458} 1459 1460define 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; 1477entry: 1478 br label %loop 1479loop: 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 1488exit: 1489 %res = icmp eq i8 %A.iv, %B.iv 1490 ret i1 %res 1491} 1492 1493define 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; 1511entry: 1512 %B = add i8 %A, 1 1513 br label %loop 1514loop: 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 1523exit: 1524 %res = icmp eq i8 %A.iv, %B.iv 1525 ret i1 %res 1526} 1527 1528define 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; 1544entry: 1545 %B = add i8 %A, 1 1546 br label %loop 1547loop: 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 1556exit: 1557 %res = icmp eq i8 %A.iv, %B.iv 1558 ret i1 %res 1559} 1560 1561 1562define 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; 1579entry: 1580 %B = add i8 %A, 1 1581 br label %loop 1582loop: 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 1591exit: 1592 %res = icmp eq i8 %A.iv, %B.iv 1593 ret i1 %res 1594} 1595 1596define 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; 1613entry: 1614 %B = add i8 %A, 0 1615 br label %loop 1616loop: 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 1625exit: 1626 %res = icmp eq i8 %A.iv, %B.iv 1627 ret i1 %res 1628} 1629 1630define 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; 1647entry: 1648 br label %loop 1649loop: 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 1658exit: 1659 %res = icmp eq i8 %A.iv, %B.iv 1660 ret i1 %res 1661} 1662 1663define 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; 1681entry: 1682 %B = add i8 %A, 1 1683 br label %loop 1684loop: 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 1693exit: 1694 %res = icmp eq i8 %A.iv, %B.iv 1695 ret i1 %res 1696} 1697 1698define 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; 1715entry: 1716 br label %loop 1717loop: 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 1726exit: 1727 %res = icmp eq i32 %p1, %p2 1728 ret i1 %res 1729} 1730 1731define 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; 1748entry: 1749 br label %loop 1750loop: 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 1759exit: 1760 %res = icmp eq i32 %p1, %p2 1761 ret i1 %res 1762} 1763 1764 1765define 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; 1782entry: 1783 %B = add i8 %A, 1 1784 br label %loop 1785loop: 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 1793exit: 1794 %res = icmp eq i8 %A.iv, %B.iv 1795 ret i1 %res 1796} 1797 1798define 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; 1814entry: 1815 br label %loop 1816loop: 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 1824exit: 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.) 1831define 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; 1849entry: 1850 %B = add i8 %A, 1 1851 br label %loop 1852loop: 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 1861exit: 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. 1867define 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; 1884entry: 1885 %cmp.i = icmp eq ptr %val1, null 1886 br i1 %cmp.i, label %_Z9stringlenPKs.exit, label %while.cond.i 1887 1888while.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 1895while.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 } 1905