1907 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt -passes=instsimplify < %s -S | FileCheck %s3 4define i1 @test(ptr %pq, i8 %B) {5; CHECK-LABEL: @test(6; CHECK-NEXT: ret i1 false7;8 %q = load i8, ptr %pq, !range !0 ; %q is known nonzero; no known bits9 %A = add nsw i8 %B, %q10 %cmp = icmp eq i8 %A, %B11 ret i1 %cmp12}13 14define i1 @test2(i8 %a, i8 %b) {15; CHECK-LABEL: @test2(16; CHECK-NEXT: ret i1 false17;18 %A = or i8 %a, 2 ; %A[1] = 119 %B = and i8 %b, -3 ; %B[1] = 020 %cmp = icmp eq i8 %A, %B ; %A[1] and %B[1] are contradictory.21 ret i1 %cmp22}23 24define i1 @test3(i8 %B) {25; CHECK-LABEL: @test3(26; CHECK-NEXT: ret i1 false27;28 %A = add nsw i8 %B, 129 %cmp = icmp eq i8 %A, %B30 ret i1 %cmp31}32 33define i1 @sext(i8 %B) {34; CHECK-LABEL: @sext(35; CHECK-NEXT: ret i1 false36;37 %A = add nsw i8 %B, 138 %A.cast = sext i8 %A to i3239 %B.cast = sext i8 %B to i3240 %cmp = icmp eq i32 %A.cast, %B.cast41 ret i1 %cmp42}43 44define i1 @zext(i8 %B) {45; CHECK-LABEL: @zext(46; CHECK-NEXT: ret i1 false47;48 %A = add nsw i8 %B, 149 %A.cast = zext i8 %A to i3250 %B.cast = zext i8 %B to i3251 %cmp = icmp eq i32 %A.cast, %B.cast52 ret i1 %cmp53}54 55define i1 @inttoptr(i32 %B) {56; CHECK-LABEL: @inttoptr(57; CHECK-NEXT: [[A:%.*]] = add nsw i32 [[B:%.*]], 158; CHECK-NEXT: [[A_CAST:%.*]] = inttoptr i32 [[A]] to ptr59; CHECK-NEXT: [[B_CAST:%.*]] = inttoptr i32 [[B]] to ptr60; CHECK-NEXT: [[CMP:%.*]] = icmp eq ptr [[A_CAST]], [[B_CAST]]61; CHECK-NEXT: ret i1 [[CMP]]62;63 %A = add nsw i32 %B, 164 %A.cast = inttoptr i32 %A to ptr65 %B.cast = inttoptr i32 %B to ptr66 %cmp = icmp eq ptr %A.cast, %B.cast67 ret i1 %cmp68}69 70define i1 @ptrtoint(ptr %B) {71; CHECK-LABEL: @ptrtoint(72; CHECK-NEXT: [[A:%.*]] = getelementptr inbounds i32, ptr [[B:%.*]], i32 173; CHECK-NEXT: [[A_CAST:%.*]] = ptrtoint ptr [[A]] to i3274; CHECK-NEXT: [[B_CAST:%.*]] = ptrtoint ptr [[B]] to i3275; 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 179 %A.cast = ptrtoint ptr %A to i3280 %B.cast = ptrtoint ptr %B to i3281 %cmp = icmp eq i32 %A.cast, %B.cast82 ret i1 %cmp83}84 85define i1 @add1(i8 %B, i8 %C) {86; CHECK-LABEL: @add1(87; CHECK-NEXT: ret i1 false88;89 %A = add i8 %B, 190 %A.op = add i8 %A, %C91 %B.op = add i8 %B, %C92 93 %cmp = icmp eq i8 %A.op, %B.op94 ret i1 %cmp95}96 97define i1 @add2(i8 %B, i8 %C) {98; CHECK-LABEL: @add2(99; CHECK-NEXT: ret i1 false100;101 %A = add i8 %B, 1102 %A.op = add i8 %C, %A103 %B.op = add i8 %C, %B104 105 %cmp = icmp eq i8 %A.op, %B.op106 ret i1 %cmp107}108 109define i1 @sub1(i8 %B, i8 %C) {110; CHECK-LABEL: @sub1(111; CHECK-NEXT: ret i1 false112;113 %A = add i8 %B, 1114 %A.op = sub i8 %A, %C115 %B.op = sub i8 %B, %C116 117 %cmp = icmp eq i8 %A.op, %B.op118 ret i1 %cmp119}120 121define i1 @sub2(i8 %B, i8 %C) {122; CHECK-LABEL: @sub2(123; CHECK-NEXT: ret i1 false124;125 %A = add i8 %B, 1126 %A.op = sub i8 %C, %A127 %B.op = sub i8 %C, %B128 129 %cmp = icmp eq i8 %A.op, %B.op130 ret i1 %cmp131}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:%.*]], 1137; CHECK-NEXT: [[A_OP:%.*]] = mul i8 [[A]], 27138; CHECK-NEXT: [[B_OP:%.*]] = mul i8 [[B]], 27139; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[A_OP]], [[B_OP]]140; CHECK-NEXT: ret i1 [[CMP]]141;142 %A = add i8 %B, 1143 %A.op = mul i8 %A, 27144 %B.op = mul i8 %B, 27145 146 %cmp = icmp eq i8 %A.op, %B.op147 ret i1 %cmp148}149 150define i1 @mul2(i8 %B) {151; CHECK-LABEL: @mul2(152; CHECK-NEXT: ret i1 false153;154 %A = add i8 %B, 1155 %A.op = mul nuw i8 %A, 27156 %B.op = mul nuw i8 %B, 27157 158 %cmp = icmp eq i8 %A.op, %B.op159 ret i1 %cmp160}161 162define i1 @mul3(i8 %B) {163; CHECK-LABEL: @mul3(164; CHECK-NEXT: ret i1 false165;166 %A = add i8 %B, 1167 %A.op = mul nsw i8 %A, 27168 %B.op = mul nsw i8 %B, 27169 170 %cmp = icmp eq i8 %A.op, %B.op171 ret i1 %cmp172}173 174; Multiply by zero collapses all values to one175define i1 @mul4(i8 %B) {176; CHECK-LABEL: @mul4(177; CHECK-NEXT: ret i1 true178;179 %A = add i8 %B, 1180 %A.op = mul nuw i8 %A, 0181 %B.op = mul nuw i8 %B, 0182 183 %cmp = icmp eq i8 %A.op, %B.op184 ret i1 %cmp185}186 187; C might be zero, we can't tell188define i1 @mul5(i8 %B, i8 %C) {189; CHECK-LABEL: @mul5(190; CHECK-NEXT: [[A:%.*]] = add i8 [[B:%.*]], 1191; 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, 1197 %A.op = mul nsw nuw i8 %A, %C198 %B.op = mul nsw nuw i8 %B, %C199 200 %cmp = icmp eq i8 %A.op, %B.op201 ret i1 %cmp202}203 204@g = external global i16, align 1205 206define i1 @mul_constantexpr(i16 %a) {207; CHECK-LABEL: @mul_constantexpr(208; CHECK-NEXT: [[MUL:%.*]] = mul nsw i16 [[A:%.*]], 3209; CHECK-NEXT: [[MUL2:%.*]] = mul nsw i16 ptrtoint (ptr @g to i16), -1210; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[MUL2]], [[MUL]]211; CHECK-NEXT: ret i1 [[CMP]]212;213 %mul = mul nsw i16 %a, 3214 %mul2 = mul nsw i16 ptrtoint (ptr @g to i16), -1215 %cmp = icmp eq i16 %mul2, %mul216 ret i1 %cmp217}218 219define i1 @mul_nuw(i16 %x) {220; CHECK-LABEL: @mul_nuw(221; CHECK-NEXT: ret i1 false222;223 %nz = or i16 %x, 2224 %mul = mul nuw i16 %nz, 2225 %cmp = icmp eq i16 %nz, %mul226 ret i1 %cmp227}228 229define i1 @mul_nuw_comm(i16 %x) {230; CHECK-LABEL: @mul_nuw_comm(231; CHECK-NEXT: ret i1 false232;233 %nz = or i16 %x, 2234 %mul = mul nuw i16 %nz, 2235 %cmp = icmp eq i16 %mul, %nz236 ret i1 %cmp237}238 239define i1 @mul_nsw(i16 %x) {240; CHECK-LABEL: @mul_nsw(241; CHECK-NEXT: ret i1 false242;243 %nz = or i16 %x, 2244 %mul = mul nsw i16 %nz, 2245 %cmp = icmp eq i16 %nz, %mul246 ret i1 %cmp247}248 249define i1 @mul_nsw_comm(i16 %x) {250; CHECK-LABEL: @mul_nsw_comm(251; CHECK-NEXT: ret i1 false252;253 %nz = or i16 %x, 2254 %mul = mul nsw i16 %nz, 2255 %cmp = icmp eq i16 %mul, %nz256 ret i1 %cmp257}258 259define i1 @mul_may_wrap(i16 %x) {260; CHECK-LABEL: @mul_may_wrap(261; CHECK-NEXT: [[NZ:%.*]] = or i16 [[X:%.*]], 2262; CHECK-NEXT: [[MUL:%.*]] = mul i16 [[NZ]], 2263; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]264; CHECK-NEXT: ret i1 [[CMP]]265;266 %nz = or i16 %x, 2267 %mul = mul i16 %nz, 2268 %cmp = icmp eq i16 %nz, %mul269 ret i1 %cmp270}271 272define i1 @mul_may_be_zero(i16 %x) {273; CHECK-LABEL: @mul_may_be_zero(274; CHECK-NEXT: [[MUL:%.*]] = mul nuw i16 [[X:%.*]], 2275; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[X]], [[MUL]]276; CHECK-NEXT: ret i1 [[CMP]]277;278 %mul = mul nuw i16 %x, 2279 %cmp = icmp eq i16 %x, %mul280 ret i1 %cmp281}282 283define i1 @mul_other_may_be_zero_or_one(i16 %x, i16 %y) {284; CHECK-LABEL: @mul_other_may_be_zero_or_one(285; CHECK-NEXT: [[NZ:%.*]] = or i16 [[X:%.*]], 2286; CHECK-NEXT: [[MUL:%.*]] = mul nuw i16 [[NZ]], [[Y:%.*]]287; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]288; CHECK-NEXT: ret i1 [[CMP]]289;290 %nz = or i16 %x, 2291 %mul = mul nuw i16 %nz, %y292 %cmp = icmp eq i16 %nz, %mul293 ret i1 %cmp294}295 296define i1 @known_non_equal_phis(i8 %p, ptr %pq, i8 %n, i8 %r) {297; CHECK-LABEL: @known_non_equal_phis(298; CHECK-NEXT: entry:299; CHECK-NEXT: br label [[LOOP:%.*]]300; CHECK: loop:301; CHECK-NEXT: [[A:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]302; CHECK-NEXT: [[NEXT]] = mul nsw i8 [[A]], 2303; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]304; CHECK-NEXT: br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]305; CHECK: exit:306; CHECK-NEXT: ret i1 true307;308entry:309 br label %loop310loop:311 %A = phi i8 [ 2, %entry ], [ %next, %loop ]312 %B = phi i8 [ 3, %entry ], [ %A, %loop ]313 %next = mul nsw i8 %A, 2314 %cmp1 = icmp eq i8 %A, %n315 br i1 %cmp1, label %exit, label %loop316exit:317 %cmp = icmp ne i8 %A, %B318 ret i1 %cmp319}320 321define i1 @known_non_equal_phis_max_recursion_limit(i1 %cond, i32 %switch.cond) {322; CHECK-LABEL: @known_non_equal_phis_max_recursion_limit(323; CHECK-NEXT: entry:324; CHECK-NEXT: br label [[BB0:%.*]]325; CHECK: bb0:326; CHECK-NEXT: [[PHIA_0:%.*]] = phi i32 [ [[PHIA_1:%.*]], [[BB1:%.*]] ], [ 0, [[ENTRY:%.*]] ]327; CHECK-NEXT: [[PHIB_0:%.*]] = phi i32 [ [[PHIB_1:%.*]], [[BB1]] ], [ 0, [[ENTRY]] ]328; CHECK-NEXT: br i1 [[COND:%.*]], label [[SWITCH_BLOCK:%.*]], label [[EXIT:%.*]]329; CHECK: switch.block:330; CHECK-NEXT: switch i32 [[SWITCH_COND:%.*]], label [[BB1]] [331; CHECK-NEXT: i32 0, label [[EPILOGUE:%.*]]332; CHECK-NEXT: i32 1, label [[EPILOGUE]]333; CHECK-NEXT: ]334; CHECK: bb1:335; CHECK-NEXT: [[PHIA_1]] = phi i32 [ [[PHIA_0]], [[SWITCH_BLOCK]] ], [ 0, [[EPILOGUE]] ]336; CHECK-NEXT: [[PHIB_1]] = phi i32 [ [[PHIB_0]], [[SWITCH_BLOCK]] ], [ 0, [[EPILOGUE]] ]337; CHECK-NEXT: br label [[BB0]]338; CHECK: epilogue:339; CHECK-NEXT: br label [[BB1]]340; CHECK: exit:341; CHECK-NEXT: [[RET:%.*]] = icmp eq i32 [[PHIA_0]], [[PHIB_0]]342; CHECK-NEXT: ret i1 [[RET]]343;344entry:345 br label %bb0346 347bb0:348 %phiA.0 = phi i32 [ %phiA.1, %bb1 ], [ 0, %entry ]349 %phiB.0 = phi i32 [ %phiB.1, %bb1 ], [ 0, %entry ]350 br i1 %cond, label %switch.block, label %exit351 352switch.block:353 switch i32 %switch.cond, label %bb1 [354 i32 0, label %epilogue355 i32 1, label %epilogue356 ]357 358bb1:359 %phiA.1 = phi i32 [ %phiA.0, %switch.block ], [ 0, %epilogue ]360 %phiB.1 = phi i32 [ %phiB.0, %switch.block ], [ 0, %epilogue ]361 br label %bb0362 363epilogue:364 br label %bb1365 366exit:367 %ret = icmp eq i32 %phiA.0, %phiB.0368 ret i1 %ret369}370 371define i1 @known_non_equal_phis_fail(i8 %p, ptr %pq, i8 %n, i8 %r) {372; CHECK-LABEL: @known_non_equal_phis_fail(373; CHECK-NEXT: entry:374; CHECK-NEXT: br label [[LOOP:%.*]]375; CHECK: loop:376; CHECK-NEXT: [[A:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]377; CHECK-NEXT: [[B:%.*]] = phi i8 [ 2, [[ENTRY]] ], [ [[A]], [[LOOP]] ]378; CHECK-NEXT: [[NEXT]] = mul nsw i8 [[A]], 2379; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]380; CHECK-NEXT: br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]381; CHECK: exit:382; CHECK-NEXT: [[CMP:%.*]] = icmp ne i8 [[A]], [[B]]383; CHECK-NEXT: ret i1 [[CMP]]384;385entry:386 br label %loop387loop:388 %A = phi i8 [ 2, %entry ], [ %next, %loop ]389 %B = phi i8 [ 2, %entry ], [ %A, %loop ]390 %next = mul nsw i8 %A, 2391 %cmp1 = icmp eq i8 %A, %n392 br i1 %cmp1, label %exit, label %loop393exit:394 %cmp = icmp ne i8 %A, %B395 ret i1 %cmp396}397 398define i1 @shl_nuw(i16 %x) {399; CHECK-LABEL: @shl_nuw(400; CHECK-NEXT: ret i1 false401;402 %nz = or i16 %x, 2403 %mul = shl nuw i16 %nz, 1404 %cmp = icmp eq i16 %nz, %mul405 ret i1 %cmp406}407 408define i1 @shl_nsw(i16 %x) {409; CHECK-LABEL: @shl_nsw(410; CHECK-NEXT: ret i1 false411;412 %nz = or i16 %x, 2413 %mul = shl nsw i16 %nz, 1414 %cmp = icmp eq i16 %nz, %mul415 ret i1 %cmp416}417 418define i1 @shl_may_wrap(i16 %x) {419; CHECK-LABEL: @shl_may_wrap(420; CHECK-NEXT: [[NZ:%.*]] = or i16 [[X:%.*]], 2421; CHECK-NEXT: [[MUL:%.*]] = shl i16 [[NZ]], 1422; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]423; CHECK-NEXT: ret i1 [[CMP]]424;425 %nz = or i16 %x, 2426 %mul = shl i16 %nz, 1427 %cmp = icmp eq i16 %nz, %mul428 ret i1 %cmp429}430 431define i1 @shl_shift_may_be_zero(i16 %x, i16 %shift) {432; CHECK-LABEL: @shl_shift_may_be_zero(433; CHECK-NEXT: [[NZ:%.*]] = or i16 [[X:%.*]], 2434; CHECK-NEXT: [[MUL:%.*]] = shl nuw i16 [[NZ]], [[SHIFT:%.*]]435; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]436; CHECK-NEXT: ret i1 [[CMP]]437;438 %nz = or i16 %x, 2439 %mul = shl nuw i16 %nz, %shift440 %cmp = icmp eq i16 %nz, %mul441 ret i1 %cmp442}443 444define i1 @shl_op_may_be_zero(i16 %x) {445; CHECK-LABEL: @shl_op_may_be_zero(446; CHECK-NEXT: [[MUL:%.*]] = shl nuw i16 [[X:%.*]], 1447; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[X]], [[MUL]]448; CHECK-NEXT: ret i1 [[CMP]]449;450 %mul = shl nuw i16 %x, 1451 %cmp = icmp eq i16 %x, %mul452 ret i1 %cmp453}454 455; The additional muls in these tests are necessary to actually456; test the isKnownNonEqual() code, rather than InstSimplify's own457; comparison folding.458 459define i1 @shl_shl_nuw(i8 %B, i8 %shift) {460; CHECK-LABEL: @shl_shl_nuw(461; CHECK-NEXT: ret i1 false462;463 %A = add i8 %B, 1464 %A.op = shl nuw i8 %A, %shift465 %B.op = shl nuw i8 %B, %shift466 %A.op2 = mul nuw i8 %A.op, 3467 %B.op2 = mul nuw i8 %B.op, 3468 %cmp = icmp eq i8 %A.op2, %B.op2469 ret i1 %cmp470}471 472define i1 @shl_shl_nsw(i8 %B, i8 %shift) {473; CHECK-LABEL: @shl_shl_nsw(474; CHECK-NEXT: ret i1 false475;476 %A = add i8 %B, 1477 %A.op = shl nsw i8 %A, %shift478 %B.op = shl nsw i8 %B, %shift479 %A.op2 = mul nuw i8 %A.op, 3480 %B.op2 = mul nuw i8 %B.op, 3481 %cmp = icmp eq i8 %A.op2, %B.op2482 ret i1 %cmp483}484 485define i1 @shl_shl_may_wrap(i8 %B, i8 %shift) {486; CHECK-LABEL: @shl_shl_may_wrap(487; CHECK-NEXT: [[A:%.*]] = add i8 [[B:%.*]], 1488; CHECK-NEXT: [[A_OP:%.*]] = shl i8 [[A]], [[SHIFT:%.*]]489; CHECK-NEXT: [[B_OP:%.*]] = shl nsw i8 [[B]], [[SHIFT]]490; CHECK-NEXT: [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3491; CHECK-NEXT: [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3492; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]493; CHECK-NEXT: ret i1 [[CMP]]494;495 %A = add i8 %B, 1496 %A.op = shl i8 %A, %shift497 %B.op = shl nsw i8 %B, %shift498 %A.op2 = mul nuw i8 %A.op, 3499 %B.op2 = mul nuw i8 %B.op, 3500 %cmp = icmp eq i8 %A.op2, %B.op2501 ret i1 %cmp502}503 504define i1 @shl_shl_mixed_wrap(i8 %B, i8 %shift) {505; CHECK-LABEL: @shl_shl_mixed_wrap(506; CHECK-NEXT: [[A:%.*]] = add i8 [[B:%.*]], 1507; CHECK-NEXT: [[A_OP:%.*]] = shl nuw i8 [[A]], [[SHIFT:%.*]]508; CHECK-NEXT: [[B_OP:%.*]] = shl nsw i8 [[B]], [[SHIFT]]509; CHECK-NEXT: [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3510; CHECK-NEXT: [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3511; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]512; CHECK-NEXT: ret i1 [[CMP]]513;514 %A = add i8 %B, 1515 %A.op = shl nuw i8 %A, %shift516 %B.op = shl nsw i8 %B, %shift517 %A.op2 = mul nuw i8 %A.op, 3518 %B.op2 = mul nuw i8 %B.op, 3519 %cmp = icmp eq i8 %A.op2, %B.op2520 ret i1 %cmp521}522 523define i1 @shl_shl_may_be_equal(i8 %A, i8 %B, i8 %shift) {524; CHECK-LABEL: @shl_shl_may_be_equal(525; CHECK-NEXT: [[A_OP:%.*]] = shl nuw i8 [[A:%.*]], [[SHIFT:%.*]]526; CHECK-NEXT: [[B_OP:%.*]] = shl nuw i8 [[B:%.*]], [[SHIFT]]527; CHECK-NEXT: [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3528; CHECK-NEXT: [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3529; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]530; CHECK-NEXT: ret i1 [[CMP]]531;532 %A.op = shl nuw i8 %A, %shift533 %B.op = shl nuw i8 %B, %shift534 %A.op2 = mul nuw i8 %A.op, 3535 %B.op2 = mul nuw i8 %B.op, 3536 %cmp = icmp eq i8 %A.op2, %B.op2537 ret i1 %cmp538}539 540define i1 @ashr_ashr_exact(i8 %B, i8 %shift) {541; CHECK-LABEL: @ashr_ashr_exact(542; CHECK-NEXT: ret i1 false543;544 %A = add i8 %B, 1545 %A.op = ashr exact i8 %A, %shift546 %B.op = ashr exact i8 %B, %shift547 %A.op2 = mul nuw i8 %A.op, 3548 %B.op2 = mul nuw i8 %B.op, 3549 %cmp = icmp eq i8 %A.op2, %B.op2550 ret i1 %cmp551}552 553define i1 @ashr_ashr_discard_bits(i8 %B, i8 %shift) {554; CHECK-LABEL: @ashr_ashr_discard_bits(555; CHECK-NEXT: [[A:%.*]] = add i8 [[B:%.*]], 1556; CHECK-NEXT: [[A_OP:%.*]] = ashr i8 [[A]], [[SHIFT:%.*]]557; CHECK-NEXT: [[B_OP:%.*]] = ashr exact i8 [[B]], [[SHIFT]]558; CHECK-NEXT: [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3559; CHECK-NEXT: [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3560; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]561; CHECK-NEXT: ret i1 [[CMP]]562;563 %A = add i8 %B, 1564 %A.op = ashr i8 %A, %shift565 %B.op = ashr exact i8 %B, %shift566 %A.op2 = mul nuw i8 %A.op, 3567 %B.op2 = mul nuw i8 %B.op, 3568 %cmp = icmp eq i8 %A.op2, %B.op2569 ret i1 %cmp570}571 572define i1 @ashr_ashr_may_be_equal(i8 %A, i8 %B, i8 %shift) {573; CHECK-LABEL: @ashr_ashr_may_be_equal(574; CHECK-NEXT: [[A_OP:%.*]] = ashr exact i8 [[A:%.*]], [[SHIFT:%.*]]575; CHECK-NEXT: [[B_OP:%.*]] = ashr exact i8 [[B:%.*]], [[SHIFT]]576; CHECK-NEXT: [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3577; CHECK-NEXT: [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3578; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]579; CHECK-NEXT: ret i1 [[CMP]]580;581 %A.op = ashr exact i8 %A, %shift582 %B.op = ashr exact i8 %B, %shift583 %A.op2 = mul nuw i8 %A.op, 3584 %B.op2 = mul nuw i8 %B.op, 3585 %cmp = icmp eq i8 %A.op2, %B.op2586 ret i1 %cmp587}588 589define i1 @lshr_lshr_exact(i8 %B, i8 %shift) {590; CHECK-LABEL: @lshr_lshr_exact(591; CHECK-NEXT: ret i1 false592;593 %A = add i8 %B, 1594 %A.op = lshr exact i8 %A, %shift595 %B.op = lshr exact i8 %B, %shift596 %A.op2 = mul nuw i8 %A.op, 3597 %B.op2 = mul nuw i8 %B.op, 3598 %cmp = icmp eq i8 %A.op2, %B.op2599 ret i1 %cmp600}601 602define i1 @lshr_lshr_discard_bits(i8 %B, i8 %shift) {603; CHECK-LABEL: @lshr_lshr_discard_bits(604; CHECK-NEXT: [[A:%.*]] = add i8 [[B:%.*]], 1605; CHECK-NEXT: [[A_OP:%.*]] = lshr i8 [[A]], [[SHIFT:%.*]]606; CHECK-NEXT: [[B_OP:%.*]] = lshr exact i8 [[B]], [[SHIFT]]607; CHECK-NEXT: [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3608; CHECK-NEXT: [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3609; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]610; CHECK-NEXT: ret i1 [[CMP]]611;612 %A = add i8 %B, 1613 %A.op = lshr i8 %A, %shift614 %B.op = lshr exact i8 %B, %shift615 %A.op2 = mul nuw i8 %A.op, 3616 %B.op2 = mul nuw i8 %B.op, 3617 %cmp = icmp eq i8 %A.op2, %B.op2618 ret i1 %cmp619}620 621define i1 @lshr_lshr_may_be_equal(i8 %A, i8 %B, i8 %shift) {622; CHECK-LABEL: @lshr_lshr_may_be_equal(623; CHECK-NEXT: [[A_OP:%.*]] = lshr exact i8 [[A:%.*]], [[SHIFT:%.*]]624; CHECK-NEXT: [[B_OP:%.*]] = lshr exact i8 [[B:%.*]], [[SHIFT]]625; CHECK-NEXT: [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3626; CHECK-NEXT: [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3627; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]628; CHECK-NEXT: ret i1 [[CMP]]629;630 %A.op = lshr exact i8 %A, %shift631 %B.op = lshr exact i8 %B, %shift632 %A.op2 = mul nuw i8 %A.op, 3633 %B.op2 = mul nuw i8 %B.op, 3634 %cmp = icmp eq i8 %A.op2, %B.op2635 ret i1 %cmp636}637 638define i1 @recurrence_add_neq(i8 %A) {639; CHECK-LABEL: @recurrence_add_neq(640; CHECK-NEXT: entry:641; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 1642; CHECK-NEXT: br label [[LOOP:%.*]]643; CHECK: loop:644; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]645; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]646; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]647; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1648; CHECK-NEXT: [[A_IV_NEXT]] = add i8 [[A_IV]], 1649; CHECK-NEXT: [[B_IV_NEXT]] = add i8 [[B_IV]], 1650; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10651; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]652; CHECK: exit:653; CHECK-NEXT: ret i1 false654;655entry:656 %B = add i8 %A, 1657 br label %loop658loop:659 %iv = phi i64 [0, %entry], [%iv.next, %loop]660 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]661 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]662 %iv.next = add i64 %iv, 1663 %A.iv.next = add i8 %A.iv, 1664 %B.iv.next = add i8 %B.iv, 1665 %cmp = icmp ne i64 %iv.next, 10666 br i1 %cmp, label %loop, label %exit667exit:668 %res = icmp eq i8 %A.iv, %B.iv669 ret i1 %res670}671 672define i1 @recurrence_add_eq(i8 %A) {673; CHECK-LABEL: @recurrence_add_eq(674; CHECK-NEXT: entry:675; CHECK-NEXT: br label [[LOOP:%.*]]676; CHECK: loop:677; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]678; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]679; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]680; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1681; CHECK-NEXT: [[A_IV_NEXT]] = add i8 [[A_IV]], 1682; CHECK-NEXT: [[B_IV_NEXT]] = add i8 [[B_IV]], 1683; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10684; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]685; CHECK: exit:686; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]687; CHECK-NEXT: ret i1 [[RES]]688;689entry:690 %B = add i8 %A, 0691 br label %loop692loop:693 %iv = phi i64 [0, %entry], [%iv.next, %loop]694 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]695 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]696 %iv.next = add i64 %iv, 1697 %A.iv.next = add i8 %A.iv, 1698 %B.iv.next = add i8 %B.iv, 1699 %cmp = icmp ne i64 %iv.next, 10700 br i1 %cmp, label %loop, label %exit701exit:702 %res = icmp eq i8 %A.iv, %B.iv703 ret i1 %res704}705 706define i1 @recurrence_add_unknown(i8 %A, i8 %B) {707; CHECK-LABEL: @recurrence_add_unknown(708; CHECK-NEXT: entry:709; CHECK-NEXT: br label [[LOOP:%.*]]710; CHECK: loop:711; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]712; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]713; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]714; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1715; CHECK-NEXT: [[A_IV_NEXT]] = add i8 [[A_IV]], 1716; CHECK-NEXT: [[B_IV_NEXT]] = add i8 [[B_IV]], 1717; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10718; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]719; CHECK: exit:720; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]721; CHECK-NEXT: ret i1 [[RES]]722;723entry:724 br label %loop725loop:726 %iv = phi i64 [0, %entry], [%iv.next, %loop]727 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]728 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]729 %iv.next = add i64 %iv, 1730 %A.iv.next = add i8 %A.iv, 1731 %B.iv.next = add i8 %B.iv, 1732 %cmp = icmp ne i64 %iv.next, 10733 br i1 %cmp, label %loop, label %exit734exit:735 %res = icmp eq i8 %A.iv, %B.iv736 ret i1 %res737}738 739; If the steps are different, the invertibility is not enough740; (Though, in this case, we could prove neq with different logic)741define i1 @recurrence_add_diff_step(i8 %A) {742; CHECK-LABEL: @recurrence_add_diff_step(743; CHECK-NEXT: entry:744; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 1745; CHECK-NEXT: br label [[LOOP:%.*]]746; CHECK: loop:747; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]748; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]749; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]750; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1751; CHECK-NEXT: [[A_IV_NEXT]] = add i8 [[A_IV]], 1752; CHECK-NEXT: [[B_IV_NEXT]] = add i8 [[B_IV]], 2753; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10754; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]755; CHECK: exit:756; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]757; CHECK-NEXT: ret i1 [[RES]]758;759entry:760 %B = add i8 %A, 1761 br label %loop762loop:763 %iv = phi i64 [0, %entry], [%iv.next, %loop]764 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]765 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]766 %iv.next = add i64 %iv, 1767 %A.iv.next = add i8 %A.iv, 1768 %B.iv.next = add i8 %B.iv, 2769 %cmp = icmp ne i64 %iv.next, 10770 br i1 %cmp, label %loop, label %exit771exit:772 %res = icmp eq i8 %A.iv, %B.iv773 ret i1 %res774}775 776define i1 @recurrence_add_op_order(i8 %A) {777; CHECK-LABEL: @recurrence_add_op_order(778; CHECK-NEXT: entry:779; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 1780; CHECK-NEXT: br label [[LOOP:%.*]]781; CHECK: loop:782; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]783; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]784; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]785; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1786; CHECK-NEXT: [[A_IV_NEXT]] = add i8 1, [[A_IV]]787; CHECK-NEXT: [[B_IV_NEXT]] = add i8 1, [[B_IV]]788; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10789; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]790; CHECK: exit:791; CHECK-NEXT: ret i1 false792;793entry:794 %B = add i8 %A, 1795 br label %loop796loop:797 %iv = phi i64 [0, %entry], [%iv.next, %loop]798 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]799 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]800 %iv.next = add i64 %iv, 1801 %A.iv.next = add i8 1, %A.iv802 %B.iv.next = add i8 1, %B.iv803 %cmp = icmp ne i64 %iv.next, 10804 br i1 %cmp, label %loop, label %exit805exit:806 %res = icmp eq i8 %A.iv, %B.iv807 ret i1 %res808}809 810; Just to show that phi operand order doesn't matter811define i1 @recurrence_add_neq_phi_order(i8 %A) {812; CHECK-LABEL: @recurrence_add_neq_phi_order(813; CHECK-NEXT: entry:814; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 1815; CHECK-NEXT: br label [[LOOP:%.*]]816; CHECK: loop:817; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]818; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A_IV_NEXT:%.*]], [[LOOP]] ], [ [[A]], [[ENTRY]] ]819; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B_IV_NEXT:%.*]], [[LOOP]] ], [ [[B]], [[ENTRY]] ]820; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1821; CHECK-NEXT: [[A_IV_NEXT]] = add i8 [[A_IV]], 1822; CHECK-NEXT: [[B_IV_NEXT]] = add i8 [[B_IV]], 1823; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10824; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]825; CHECK: exit:826; CHECK-NEXT: ret i1 false827;828entry:829 %B = add i8 %A, 1830 br label %loop831loop:832 %iv = phi i64 [%iv.next, %loop], [0, %entry]833 %A.iv = phi i8 [%A.iv.next, %loop], [%A, %entry]834 %B.iv = phi i8 [%B.iv.next, %loop], [%B, %entry]835 %iv.next = add i64 %iv, 1836 %A.iv.next = add i8 %A.iv, 1837 %B.iv.next = add i8 %B.iv, 1838 %cmp = icmp ne i64 %iv.next, 10839 br i1 %cmp, label %loop, label %exit840exit:841 %res = icmp eq i8 %A.iv, %B.iv842 ret i1 %res843}844 845; Demonstrate case where phi operand orders differ and thus846; there's no single operand index to recurse through847define i1 @recurrence_add_phi_different_order1(i8 %A) {848; CHECK-LABEL: @recurrence_add_phi_different_order1(849; CHECK-NEXT: entry:850; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 1851; CHECK-NEXT: br label [[LOOP:%.*]]852; CHECK: loop:853; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]854; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]855; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B_IV_NEXT:%.*]], [[LOOP]] ], [ [[B]], [[ENTRY]] ]856; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1857; CHECK-NEXT: [[A_IV_NEXT]] = add i8 [[A_IV]], 1858; CHECK-NEXT: [[B_IV_NEXT]] = add i8 [[B_IV]], 1859; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10860; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]861; CHECK: exit:862; CHECK-NEXT: ret i1 false863;864entry:865 %B = add i8 %A, 1866 br label %loop867loop:868 %iv = phi i64 [%iv.next, %loop], [0, %entry]869 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]870 %B.iv = phi i8 [%B.iv.next, %loop], [%B, %entry]871 %iv.next = add i64 %iv, 1872 %A.iv.next = add i8 %A.iv, 1873 %B.iv.next = add i8 %B.iv, 1874 %cmp = icmp ne i64 %iv.next, 10875 br i1 %cmp, label %loop, label %exit876exit:877 %res = icmp eq i8 %A.iv, %B.iv878 ret i1 %res879}880 881define i1 @recurrence_add_phi_different_order2(i8 %A) {882; CHECK-LABEL: @recurrence_add_phi_different_order2(883; CHECK-NEXT: entry:884; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 1885; CHECK-NEXT: br label [[LOOP:%.*]]886; CHECK: loop:887; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]888; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A_IV_NEXT:%.*]], [[LOOP]] ], [ [[A]], [[ENTRY]] ]889; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]890; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1891; CHECK-NEXT: [[A_IV_NEXT]] = add i8 [[A_IV]], 1892; CHECK-NEXT: [[B_IV_NEXT]] = add i8 [[B_IV]], 1893; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10894; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]895; CHECK: exit:896; CHECK-NEXT: ret i1 false897;898entry:899 %B = add i8 %A, 1900 br label %loop901loop:902 %iv = phi i64 [%iv.next, %loop], [0, %entry]903 %A.iv = phi i8 [%A.iv.next, %loop], [%A, %entry]904 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]905 %iv.next = add i64 %iv, 1906 %A.iv.next = add i8 %A.iv, 1907 %B.iv.next = add i8 %B.iv, 1908 %cmp = icmp ne i64 %iv.next, 10909 br i1 %cmp, label %loop, label %exit910exit:911 %res = icmp eq i8 %A.iv, %B.iv912 ret i1 %res913}914 915define i1 @recurrence_sub_neq(i8 %A) {916; CHECK-LABEL: @recurrence_sub_neq(917; CHECK-NEXT: entry:918; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 1919; CHECK-NEXT: br label [[LOOP:%.*]]920; CHECK: loop:921; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]922; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]923; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]924; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1925; CHECK-NEXT: [[A_IV_NEXT]] = sub i8 [[A_IV]], 1926; CHECK-NEXT: [[B_IV_NEXT]] = sub i8 [[B_IV]], 1927; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10928; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]929; CHECK: exit:930; CHECK-NEXT: ret i1 false931;932entry:933 %B = add i8 %A, 1934 br label %loop935loop:936 %iv = phi i64 [0, %entry], [%iv.next, %loop]937 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]938 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]939 %iv.next = add i64 %iv, 1940 %A.iv.next = sub i8 %A.iv, 1941 %B.iv.next = sub i8 %B.iv, 1942 %cmp = icmp ne i64 %iv.next, 10943 br i1 %cmp, label %loop, label %exit944exit:945 %res = icmp eq i8 %A.iv, %B.iv946 ret i1 %res947}948 949define i1 @recurrence_sub_eq(i8 %A) {950; CHECK-LABEL: @recurrence_sub_eq(951; CHECK-NEXT: entry:952; CHECK-NEXT: br label [[LOOP:%.*]]953; CHECK: loop:954; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]955; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]956; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]957; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1958; CHECK-NEXT: [[A_IV_NEXT]] = sub i8 [[A_IV]], 1959; CHECK-NEXT: [[B_IV_NEXT]] = sub i8 [[B_IV]], 1960; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10961; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]962; CHECK: exit:963; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]964; CHECK-NEXT: ret i1 [[RES]]965;966entry:967 %B = add i8 %A, 0968 br label %loop969loop:970 %iv = phi i64 [0, %entry], [%iv.next, %loop]971 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]972 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]973 %iv.next = add i64 %iv, 1974 %A.iv.next = sub i8 %A.iv, 1975 %B.iv.next = sub i8 %B.iv, 1976 %cmp = icmp ne i64 %iv.next, 10977 br i1 %cmp, label %loop, label %exit978exit:979 %res = icmp eq i8 %A.iv, %B.iv980 ret i1 %res981}982 983define i1 @recurrence_sub_unknown(i8 %A, i8 %B) {984; CHECK-LABEL: @recurrence_sub_unknown(985; CHECK-NEXT: entry:986; CHECK-NEXT: br label [[LOOP:%.*]]987; CHECK: loop:988; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]989; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]990; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]991; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1992; CHECK-NEXT: [[A_IV_NEXT]] = sub i8 [[A_IV]], 1993; CHECK-NEXT: [[B_IV_NEXT]] = sub i8 [[B_IV]], 1994; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10995; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]996; CHECK: exit:997; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]998; CHECK-NEXT: ret i1 [[RES]]999;1000entry:1001 br label %loop1002loop:1003 %iv = phi i64 [0, %entry], [%iv.next, %loop]1004 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1005 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1006 %iv.next = add i64 %iv, 11007 %A.iv.next = sub i8 %A.iv, 11008 %B.iv.next = sub i8 %B.iv, 11009 %cmp = icmp ne i64 %iv.next, 101010 br i1 %cmp, label %loop, label %exit1011exit:1012 %res = icmp eq i8 %A.iv, %B.iv1013 ret i1 %res1014}1015 1016define i1 @recurrence_sub_op_order(i8 %A) {1017; CHECK-LABEL: @recurrence_sub_op_order(1018; CHECK-NEXT: entry:1019; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11020; CHECK-NEXT: br label [[LOOP:%.*]]1021; CHECK: loop:1022; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1023; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1024; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1025; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11026; CHECK-NEXT: [[A_IV_NEXT]] = sub i8 1, [[A_IV]]1027; CHECK-NEXT: [[B_IV_NEXT]] = sub i8 1, [[B_IV]]1028; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101029; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1030; CHECK: exit:1031; CHECK-NEXT: ret i1 false1032;1033entry:1034 %B = add i8 %A, 11035 br label %loop1036loop:1037 %iv = phi i64 [0, %entry], [%iv.next, %loop]1038 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1039 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1040 %iv.next = add i64 %iv, 11041 %A.iv.next = sub i8 1, %A.iv1042 %B.iv.next = sub i8 1, %B.iv1043 %cmp = icmp ne i64 %iv.next, 101044 br i1 %cmp, label %loop, label %exit1045exit:1046 %res = icmp eq i8 %A.iv, %B.iv1047 ret i1 %res1048}1049 1050define i1 @recurrence_sub_op_order2(i8 %A) {1051; CHECK-LABEL: @recurrence_sub_op_order2(1052; CHECK-NEXT: entry:1053; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11054; CHECK-NEXT: br label [[LOOP:%.*]]1055; CHECK: loop:1056; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1057; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1058; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1059; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11060; CHECK-NEXT: [[A_IV_NEXT]] = sub i8 1, [[A_IV]]1061; CHECK-NEXT: [[B_IV_NEXT]] = sub i8 [[B_IV]], 11062; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101063; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1064; CHECK: exit:1065; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1066; CHECK-NEXT: ret i1 [[RES]]1067;1068entry:1069 %B = add i8 %A, 11070 br label %loop1071loop:1072 %iv = phi i64 [0, %entry], [%iv.next, %loop]1073 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1074 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1075 %iv.next = add i64 %iv, 11076 %A.iv.next = sub i8 1, %A.iv1077 %B.iv.next = sub i8 %B.iv, 11078 %cmp = icmp ne i64 %iv.next, 101079 br i1 %cmp, label %loop, label %exit1080exit:1081 %res = icmp eq i8 %A.iv, %B.iv1082 ret i1 %res1083}1084 1085 1086define i1 @recurrence_mul_neq(i8 %A) {1087; CHECK-LABEL: @recurrence_mul_neq(1088; CHECK-NEXT: entry:1089; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11090; CHECK-NEXT: br label [[LOOP:%.*]]1091; CHECK: loop:1092; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1093; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1094; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1095; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11096; CHECK-NEXT: [[A_IV_NEXT]] = mul nuw i8 [[A_IV]], 21097; CHECK-NEXT: [[B_IV_NEXT]] = mul nuw i8 [[B_IV]], 21098; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101099; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1100; CHECK: exit:1101; CHECK-NEXT: ret i1 false1102;1103entry:1104 %B = add i8 %A, 11105 br label %loop1106loop:1107 %iv = phi i64 [0, %entry], [%iv.next, %loop]1108 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1109 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1110 %iv.next = add i64 %iv, 11111 %A.iv.next = mul nuw i8 %A.iv, 21112 %B.iv.next = mul nuw i8 %B.iv, 21113 %cmp = icmp ne i64 %iv.next, 101114 br i1 %cmp, label %loop, label %exit1115exit:1116 %res = icmp eq i8 %A.iv, %B.iv1117 ret i1 %res1118}1119 1120define i1 @recurrence_mul_eq(i8 %A) {1121; CHECK-LABEL: @recurrence_mul_eq(1122; CHECK-NEXT: entry:1123; CHECK-NEXT: br label [[LOOP:%.*]]1124; CHECK: loop:1125; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1126; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1127; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1128; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11129; CHECK-NEXT: [[A_IV_NEXT]] = mul nuw i8 [[A_IV]], 21130; CHECK-NEXT: [[B_IV_NEXT]] = mul nuw i8 [[B_IV]], 21131; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101132; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1133; CHECK: exit:1134; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1135; CHECK-NEXT: ret i1 [[RES]]1136;1137entry:1138 %B = add i8 %A, 01139 br label %loop1140loop:1141 %iv = phi i64 [0, %entry], [%iv.next, %loop]1142 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1143 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1144 %iv.next = add i64 %iv, 11145 %A.iv.next = mul nuw i8 %A.iv, 21146 %B.iv.next = mul nuw i8 %B.iv, 21147 %cmp = icmp ne i64 %iv.next, 101148 br i1 %cmp, label %loop, label %exit1149exit:1150 %res = icmp eq i8 %A.iv, %B.iv1151 ret i1 %res1152}1153 1154define i1 @recurrence_mul_unknown(i8 %A, i8 %B) {1155; CHECK-LABEL: @recurrence_mul_unknown(1156; CHECK-NEXT: entry:1157; CHECK-NEXT: br label [[LOOP:%.*]]1158; CHECK: loop:1159; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1160; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1161; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1162; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11163; CHECK-NEXT: [[A_IV_NEXT]] = mul nuw i8 [[A_IV]], 21164; CHECK-NEXT: [[B_IV_NEXT]] = mul nuw i8 [[B_IV]], 21165; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101166; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1167; CHECK: exit:1168; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1169; CHECK-NEXT: ret i1 [[RES]]1170;1171entry:1172 br label %loop1173loop:1174 %iv = phi i64 [0, %entry], [%iv.next, %loop]1175 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1176 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1177 %iv.next = add i64 %iv, 11178 %A.iv.next = mul nuw i8 %A.iv, 21179 %B.iv.next = mul nuw i8 %B.iv, 21180 %cmp = icmp ne i64 %iv.next, 101181 br i1 %cmp, label %loop, label %exit1182exit:1183 %res = icmp eq i8 %A.iv, %B.iv1184 ret i1 %res1185}1186 1187define i1 @recurrence_mul_noflags(i8 %A) {1188; CHECK-LABEL: @recurrence_mul_noflags(1189; CHECK-NEXT: entry:1190; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11191; CHECK-NEXT: br label [[LOOP:%.*]]1192; CHECK: loop:1193; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1194; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1195; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1196; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11197; CHECK-NEXT: [[A_IV_NEXT]] = mul i8 [[A_IV]], 21198; CHECK-NEXT: [[B_IV_NEXT]] = mul i8 [[B_IV]], 21199; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101200; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1201; CHECK: exit:1202; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1203; CHECK-NEXT: ret i1 [[RES]]1204;1205entry:1206 %B = add i8 %A, 11207 br label %loop1208loop:1209 %iv = phi i64 [0, %entry], [%iv.next, %loop]1210 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1211 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1212 %iv.next = add i64 %iv, 11213 %A.iv.next = mul i8 %A.iv, 21214 %B.iv.next = mul i8 %B.iv, 21215 %cmp = icmp ne i64 %iv.next, 101216 br i1 %cmp, label %loop, label %exit1217exit:1218 %res = icmp eq i8 %A.iv, %B.iv1219 ret i1 %res1220}1221 1222define i1 @recurrence_shl_neq(i8 %A) {1223; CHECK-LABEL: @recurrence_shl_neq(1224; CHECK-NEXT: entry:1225; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11226; CHECK-NEXT: br label [[LOOP:%.*]]1227; CHECK: loop:1228; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1229; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1230; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1231; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11232; CHECK-NEXT: [[A_IV_NEXT]] = shl nuw i8 [[A_IV]], 11233; CHECK-NEXT: [[B_IV_NEXT]] = shl nuw i8 [[B_IV]], 11234; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101235; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1236; CHECK: exit:1237; CHECK-NEXT: ret i1 false1238;1239entry:1240 %B = add i8 %A, 11241 br label %loop1242loop:1243 %iv = phi i64 [0, %entry], [%iv.next, %loop]1244 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1245 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1246 %iv.next = add i64 %iv, 11247 %A.iv.next = shl nuw i8 %A.iv, 11248 %B.iv.next = shl nuw i8 %B.iv, 11249 %cmp = icmp ne i64 %iv.next, 101250 br i1 %cmp, label %loop, label %exit1251exit:1252 %res = icmp eq i8 %A.iv, %B.iv1253 ret i1 %res1254}1255 1256define i1 @recurrence_shl_eq(i8 %A) {1257; CHECK-LABEL: @recurrence_shl_eq(1258; CHECK-NEXT: entry:1259; CHECK-NEXT: br label [[LOOP:%.*]]1260; CHECK: loop:1261; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1262; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1263; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1264; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11265; CHECK-NEXT: [[A_IV_NEXT]] = shl nuw i8 [[A_IV]], 11266; CHECK-NEXT: [[B_IV_NEXT]] = shl nuw i8 [[B_IV]], 11267; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101268; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1269; CHECK: exit:1270; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1271; CHECK-NEXT: ret i1 [[RES]]1272;1273entry:1274 %B = add i8 %A, 01275 br label %loop1276loop:1277 %iv = phi i64 [0, %entry], [%iv.next, %loop]1278 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1279 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1280 %iv.next = add i64 %iv, 11281 %A.iv.next = shl nuw i8 %A.iv, 11282 %B.iv.next = shl nuw i8 %B.iv, 11283 %cmp = icmp ne i64 %iv.next, 101284 br i1 %cmp, label %loop, label %exit1285exit:1286 %res = icmp eq i8 %A.iv, %B.iv1287 ret i1 %res1288}1289 1290define i1 @recurrence_shl_unknown(i8 %A, i8 %B) {1291; CHECK-LABEL: @recurrence_shl_unknown(1292; CHECK-NEXT: entry:1293; CHECK-NEXT: br label [[LOOP:%.*]]1294; CHECK: loop:1295; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1296; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1297; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1298; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11299; CHECK-NEXT: [[A_IV_NEXT]] = shl nuw i8 [[A_IV]], 11300; CHECK-NEXT: [[B_IV_NEXT]] = shl nuw i8 [[B_IV]], 11301; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101302; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1303; CHECK: exit:1304; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1305; CHECK-NEXT: ret i1 [[RES]]1306;1307entry:1308 br label %loop1309loop:1310 %iv = phi i64 [0, %entry], [%iv.next, %loop]1311 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1312 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1313 %iv.next = add i64 %iv, 11314 %A.iv.next = shl nuw i8 %A.iv, 11315 %B.iv.next = shl nuw i8 %B.iv, 11316 %cmp = icmp ne i64 %iv.next, 101317 br i1 %cmp, label %loop, label %exit1318exit:1319 %res = icmp eq i8 %A.iv, %B.iv1320 ret i1 %res1321}1322 1323define i1 @recurrence_shl_noflags(i8 %A) {1324; CHECK-LABEL: @recurrence_shl_noflags(1325; CHECK-NEXT: entry:1326; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11327; CHECK-NEXT: br label [[LOOP:%.*]]1328; CHECK: loop:1329; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1330; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1331; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1332; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11333; CHECK-NEXT: [[A_IV_NEXT]] = shl i8 [[A_IV]], 11334; CHECK-NEXT: [[B_IV_NEXT]] = shl i8 [[B_IV]], 11335; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101336; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1337; CHECK: exit:1338; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1339; CHECK-NEXT: ret i1 [[RES]]1340;1341entry:1342 %B = add i8 %A, 11343 br label %loop1344loop:1345 %iv = phi i64 [0, %entry], [%iv.next, %loop]1346 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1347 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1348 %iv.next = add i64 %iv, 11349 %A.iv.next = shl i8 %A.iv, 11350 %B.iv.next = shl i8 %B.iv, 11351 %cmp = icmp ne i64 %iv.next, 101352 br i1 %cmp, label %loop, label %exit1353exit:1354 %res = icmp eq i8 %A.iv, %B.iv1355 ret i1 %res1356}1357 1358; Represents a power function, but still invertable!1359define i1 @recurrence_shl_op_order(i8 %A) {1360; CHECK-LABEL: @recurrence_shl_op_order(1361; CHECK-NEXT: entry:1362; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11363; CHECK-NEXT: br label [[LOOP:%.*]]1364; CHECK: loop:1365; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1366; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1367; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1368; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11369; CHECK-NEXT: [[A_IV_NEXT]] = shl nuw i8 1, [[A_IV]]1370; CHECK-NEXT: [[B_IV_NEXT]] = shl nuw i8 1, [[B_IV]]1371; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101372; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1373; CHECK: exit:1374; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1375; CHECK-NEXT: ret i1 [[RES]]1376;1377entry:1378 %B = add i8 %A, 11379 br label %loop1380loop:1381 %iv = phi i64 [0, %entry], [%iv.next, %loop]1382 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1383 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1384 %iv.next = add i64 %iv, 11385 %A.iv.next = shl nuw i8 1, %A.iv1386 %B.iv.next = shl nuw i8 1, %B.iv1387 %cmp = icmp ne i64 %iv.next, 101388 br i1 %cmp, label %loop, label %exit1389exit:1390 %res = icmp eq i8 %A.iv, %B.iv1391 ret i1 %res1392}1393 1394define i1 @recurrence_lshr_neq(i8 %A) {1395; CHECK-LABEL: @recurrence_lshr_neq(1396; CHECK-NEXT: entry:1397; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11398; CHECK-NEXT: br label [[LOOP:%.*]]1399; CHECK: loop:1400; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1401; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1402; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1403; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11404; CHECK-NEXT: [[A_IV_NEXT]] = lshr exact i8 [[A_IV]], 11405; CHECK-NEXT: [[B_IV_NEXT]] = lshr exact i8 [[B_IV]], 11406; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101407; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1408; CHECK: exit:1409; CHECK-NEXT: ret i1 false1410;1411entry:1412 %B = add i8 %A, 11413 br label %loop1414loop:1415 %iv = phi i64 [0, %entry], [%iv.next, %loop]1416 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1417 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1418 %iv.next = add i64 %iv, 11419 %A.iv.next = lshr exact i8 %A.iv, 11420 %B.iv.next = lshr exact i8 %B.iv, 11421 %cmp = icmp ne i64 %iv.next, 101422 br i1 %cmp, label %loop, label %exit1423exit:1424 %res = icmp eq i8 %A.iv, %B.iv1425 ret i1 %res1426}1427 1428define i1 @recurrence_lshr_eq(i8 %A) {1429; CHECK-LABEL: @recurrence_lshr_eq(1430; CHECK-NEXT: entry:1431; CHECK-NEXT: br label [[LOOP:%.*]]1432; CHECK: loop:1433; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1434; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1435; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1436; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11437; CHECK-NEXT: [[A_IV_NEXT]] = lshr exact i8 [[A_IV]], 11438; CHECK-NEXT: [[B_IV_NEXT]] = lshr exact i8 [[B_IV]], 11439; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101440; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1441; CHECK: exit:1442; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1443; CHECK-NEXT: ret i1 [[RES]]1444;1445entry:1446 %B = add i8 %A, 01447 br label %loop1448loop:1449 %iv = phi i64 [0, %entry], [%iv.next, %loop]1450 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1451 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1452 %iv.next = add i64 %iv, 11453 %A.iv.next = lshr exact i8 %A.iv, 11454 %B.iv.next = lshr exact i8 %B.iv, 11455 %cmp = icmp ne i64 %iv.next, 101456 br i1 %cmp, label %loop, label %exit1457exit:1458 %res = icmp eq i8 %A.iv, %B.iv1459 ret i1 %res1460}1461 1462define i1 @recurrence_lshr_unknown(i8 %A, i8 %B) {1463; CHECK-LABEL: @recurrence_lshr_unknown(1464; CHECK-NEXT: entry:1465; CHECK-NEXT: br label [[LOOP:%.*]]1466; CHECK: loop:1467; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1468; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1469; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1470; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11471; CHECK-NEXT: [[A_IV_NEXT]] = lshr exact i8 [[A_IV]], 11472; CHECK-NEXT: [[B_IV_NEXT]] = lshr exact i8 [[B_IV]], 11473; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101474; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1475; CHECK: exit:1476; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1477; CHECK-NEXT: ret i1 [[RES]]1478;1479entry:1480 br label %loop1481loop:1482 %iv = phi i64 [0, %entry], [%iv.next, %loop]1483 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1484 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1485 %iv.next = add i64 %iv, 11486 %A.iv.next = lshr exact i8 %A.iv, 11487 %B.iv.next = lshr exact i8 %B.iv, 11488 %cmp = icmp ne i64 %iv.next, 101489 br i1 %cmp, label %loop, label %exit1490exit:1491 %res = icmp eq i8 %A.iv, %B.iv1492 ret i1 %res1493}1494 1495define i1 @recurrence_lshr_noflags(i8 %A) {1496; CHECK-LABEL: @recurrence_lshr_noflags(1497; CHECK-NEXT: entry:1498; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11499; CHECK-NEXT: br label [[LOOP:%.*]]1500; CHECK: loop:1501; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1502; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1503; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1504; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11505; CHECK-NEXT: [[A_IV_NEXT]] = lshr i8 [[A_IV]], 11506; CHECK-NEXT: [[B_IV_NEXT]] = lshr i8 [[B_IV]], 11507; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101508; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1509; CHECK: exit:1510; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1511; CHECK-NEXT: ret i1 [[RES]]1512;1513entry:1514 %B = add i8 %A, 11515 br label %loop1516loop:1517 %iv = phi i64 [0, %entry], [%iv.next, %loop]1518 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1519 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1520 %iv.next = add i64 %iv, 11521 %A.iv.next = lshr i8 %A.iv, 11522 %B.iv.next = lshr i8 %B.iv, 11523 %cmp = icmp ne i64 %iv.next, 101524 br i1 %cmp, label %loop, label %exit1525exit:1526 %res = icmp eq i8 %A.iv, %B.iv1527 ret i1 %res1528}1529 1530define i1 @recurrence_lshr_op_order(i8 %A) {1531; CHECK-LABEL: @recurrence_lshr_op_order(1532; CHECK-NEXT: entry:1533; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11534; CHECK-NEXT: br label [[LOOP:%.*]]1535; CHECK: loop:1536; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1537; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ 1, [[LOOP]] ]1538; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ 1, [[LOOP]] ]1539; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11540; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101541; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1542; CHECK: exit:1543; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1544; CHECK-NEXT: ret i1 [[RES]]1545;1546entry:1547 %B = add i8 %A, 11548 br label %loop1549loop:1550 %iv = phi i64 [0, %entry], [%iv.next, %loop]1551 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1552 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1553 %iv.next = add i64 %iv, 11554 %A.iv.next = lshr exact i8 1, %A.iv1555 %B.iv.next = lshr exact i8 1, %B.iv1556 %cmp = icmp ne i64 %iv.next, 101557 br i1 %cmp, label %loop, label %exit1558exit:1559 %res = icmp eq i8 %A.iv, %B.iv1560 ret i1 %res1561}1562 1563 1564define i1 @recurrence_ashr_neq(i8 %A) {1565; CHECK-LABEL: @recurrence_ashr_neq(1566; CHECK-NEXT: entry:1567; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11568; CHECK-NEXT: br label [[LOOP:%.*]]1569; CHECK: loop:1570; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1571; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1572; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1573; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11574; CHECK-NEXT: [[A_IV_NEXT]] = ashr exact i8 [[A_IV]], 11575; CHECK-NEXT: [[B_IV_NEXT]] = ashr exact i8 [[B_IV]], 11576; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101577; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1578; CHECK: exit:1579; CHECK-NEXT: ret i1 false1580;1581entry:1582 %B = add i8 %A, 11583 br label %loop1584loop:1585 %iv = phi i64 [0, %entry], [%iv.next, %loop]1586 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1587 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1588 %iv.next = add i64 %iv, 11589 %A.iv.next = ashr exact i8 %A.iv, 11590 %B.iv.next = ashr exact i8 %B.iv, 11591 %cmp = icmp ne i64 %iv.next, 101592 br i1 %cmp, label %loop, label %exit1593exit:1594 %res = icmp eq i8 %A.iv, %B.iv1595 ret i1 %res1596}1597 1598define i1 @recurrence_ashr_eq(i8 %A) {1599; CHECK-LABEL: @recurrence_ashr_eq(1600; CHECK-NEXT: entry:1601; CHECK-NEXT: br label [[LOOP:%.*]]1602; CHECK: loop:1603; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1604; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1605; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1606; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11607; CHECK-NEXT: [[A_IV_NEXT]] = ashr exact i8 [[A_IV]], 11608; CHECK-NEXT: [[B_IV_NEXT]] = ashr exact i8 [[B_IV]], 11609; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101610; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1611; CHECK: exit:1612; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1613; CHECK-NEXT: ret i1 [[RES]]1614;1615entry:1616 %B = add i8 %A, 01617 br label %loop1618loop:1619 %iv = phi i64 [0, %entry], [%iv.next, %loop]1620 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1621 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1622 %iv.next = add i64 %iv, 11623 %A.iv.next = ashr exact i8 %A.iv, 11624 %B.iv.next = ashr exact i8 %B.iv, 11625 %cmp = icmp ne i64 %iv.next, 101626 br i1 %cmp, label %loop, label %exit1627exit:1628 %res = icmp eq i8 %A.iv, %B.iv1629 ret i1 %res1630}1631 1632define i1 @recurrence_ashr_unknown(i8 %A, i8 %B) {1633; CHECK-LABEL: @recurrence_ashr_unknown(1634; CHECK-NEXT: entry:1635; CHECK-NEXT: br label [[LOOP:%.*]]1636; CHECK: loop:1637; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1638; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1639; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1640; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11641; CHECK-NEXT: [[A_IV_NEXT]] = ashr exact i8 [[A_IV]], 11642; CHECK-NEXT: [[B_IV_NEXT]] = ashr exact i8 [[B_IV]], 11643; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101644; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1645; CHECK: exit:1646; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1647; CHECK-NEXT: ret i1 [[RES]]1648;1649entry:1650 br label %loop1651loop:1652 %iv = phi i64 [0, %entry], [%iv.next, %loop]1653 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1654 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1655 %iv.next = add i64 %iv, 11656 %A.iv.next = ashr exact i8 %A.iv, 11657 %B.iv.next = ashr exact i8 %B.iv, 11658 %cmp = icmp ne i64 %iv.next, 101659 br i1 %cmp, label %loop, label %exit1660exit:1661 %res = icmp eq i8 %A.iv, %B.iv1662 ret i1 %res1663}1664 1665define i1 @recurrence_ashr_noflags(i8 %A) {1666; CHECK-LABEL: @recurrence_ashr_noflags(1667; CHECK-NEXT: entry:1668; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11669; CHECK-NEXT: br label [[LOOP:%.*]]1670; CHECK: loop:1671; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1672; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1673; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1674; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11675; CHECK-NEXT: [[A_IV_NEXT]] = ashr i8 [[A_IV]], 11676; CHECK-NEXT: [[B_IV_NEXT]] = ashr i8 [[B_IV]], 11677; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101678; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1679; CHECK: exit:1680; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1681; CHECK-NEXT: ret i1 [[RES]]1682;1683entry:1684 %B = add i8 %A, 11685 br label %loop1686loop:1687 %iv = phi i64 [0, %entry], [%iv.next, %loop]1688 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1689 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1690 %iv.next = add i64 %iv, 11691 %A.iv.next = ashr i8 %A.iv, 11692 %B.iv.next = ashr i8 %B.iv, 11693 %cmp = icmp ne i64 %iv.next, 101694 br i1 %cmp, label %loop, label %exit1695exit:1696 %res = icmp eq i8 %A.iv, %B.iv1697 ret i1 %res1698}1699 1700define i1 @PR50191_A(i32 %x) {1701; CHECK-LABEL: @PR50191_A(1702; CHECK-NEXT: entry:1703; CHECK-NEXT: br label [[LOOP:%.*]]1704; CHECK: loop:1705; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1706; CHECK-NEXT: [[P1:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY]] ], [ [[SUB1:%.*]], [[LOOP]] ]1707; CHECK-NEXT: [[P2:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[SUB2:%.*]], [[LOOP]] ]1708; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11709; CHECK-NEXT: [[SUB1]] = sub i32 [[P1]], [[P2]]1710; CHECK-NEXT: [[SUB2]] = sub i32 42, [[P2]]1711; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101712; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1713; CHECK: exit:1714; CHECK-NEXT: [[RES:%.*]] = icmp eq i32 [[P1]], [[P2]]1715; CHECK-NEXT: ret i1 [[RES]]1716;1717entry:1718 br label %loop1719loop:1720 %iv = phi i64 [0, %entry], [%iv.next, %loop]1721 %p1 = phi i32 [%x, %entry ], [ %sub1, %loop ]1722 %p2 = phi i32 [%x, %entry ], [ %sub2, %loop ]1723 %iv.next = add i64 %iv, 11724 %sub1 = sub i32 %p1, %p21725 %sub2 = sub i32 42, %p21726 %cmp = icmp ne i64 %iv.next, 101727 br i1 %cmp, label %loop, label %exit1728exit:1729 %res = icmp eq i32 %p1, %p21730 ret i1 %res1731}1732 1733define i1 @PR50191_B(i32 %x) {1734; CHECK-LABEL: @PR50191_B(1735; CHECK-NEXT: entry:1736; CHECK-NEXT: br label [[LOOP:%.*]]1737; CHECK: loop:1738; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1739; CHECK-NEXT: [[P1:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY]] ], [ [[SUB1:%.*]], [[LOOP]] ]1740; CHECK-NEXT: [[P2:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[SUB2:%.*]], [[LOOP]] ]1741; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11742; CHECK-NEXT: [[SUB1]] = sub i32 [[P2]], [[P1]]1743; CHECK-NEXT: [[SUB2]] = sub i32 [[P2]], 421744; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101745; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1746; CHECK: exit:1747; CHECK-NEXT: [[RES:%.*]] = icmp eq i32 [[P1]], [[P2]]1748; CHECK-NEXT: ret i1 [[RES]]1749;1750entry:1751 br label %loop1752loop:1753 %iv = phi i64 [0, %entry], [%iv.next, %loop]1754 %p1 = phi i32 [%x, %entry ], [ %sub1, %loop ]1755 %p2 = phi i32 [%x, %entry ], [ %sub2, %loop ]1756 %iv.next = add i64 %iv, 11757 %sub1 = sub i32 %p2, %p11758 %sub2 = sub i32 %p2, 421759 %cmp = icmp ne i64 %iv.next, 101760 br i1 %cmp, label %loop, label %exit1761exit:1762 %res = icmp eq i32 %p1, %p21763 ret i1 %res1764}1765 1766 1767define i1 @mutual_recurrence_neq(i8 %A) {1768; CHECK-LABEL: @mutual_recurrence_neq(1769; CHECK-NEXT: entry:1770; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11771; CHECK-NEXT: br label [[LOOP:%.*]]1772; CHECK: loop:1773; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1774; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1775; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[A_IV_NEXT]], [[LOOP]] ]1776; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11777; CHECK-NEXT: [[A_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]1778; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101779; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1780; CHECK: exit:1781; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1782; CHECK-NEXT: ret i1 [[RES]]1783;1784entry:1785 %B = add i8 %A, 11786 br label %loop1787loop:1788 %iv = phi i64 [0, %entry], [%iv.next, %loop]1789 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1790 %B.iv = phi i8 [%B, %entry], [%A.iv.next, %loop]1791 %iv.next = add i64 %iv, 11792 %A.iv.next = sub i8 %A.iv, %B.iv1793 %cmp = icmp ne i64 %iv.next, 101794 br i1 %cmp, label %loop, label %exit1795exit:1796 %res = icmp eq i8 %A.iv, %B.iv1797 ret i1 %res1798}1799 1800define i1 @mutual_recurrence_eq(i8 %A) {1801; CHECK-LABEL: @mutual_recurrence_eq(1802; CHECK-NEXT: entry:1803; CHECK-NEXT: br label [[LOOP:%.*]]1804; CHECK: loop:1805; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1806; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1807; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT]], [[LOOP]] ]1808; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11809; CHECK-NEXT: [[A_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]1810; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101811; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1812; CHECK: exit:1813; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1814; CHECK-NEXT: ret i1 [[RES]]1815;1816entry:1817 br label %loop1818loop:1819 %iv = phi i64 [0, %entry], [%iv.next, %loop]1820 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1821 %B.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1822 %iv.next = add i64 %iv, 11823 %A.iv.next = sub i8 %A.iv, %B.iv1824 %cmp = icmp ne i64 %iv.next, 101825 br i1 %cmp, label %loop, label %exit1826exit:1827 %res = icmp eq i8 %A.iv, %B.iv1828 ret i1 %res1829}1830 1831; Illustrate a case where A_IV_i == B_IV_i for all i > 0, but A_IV_0 != B_IV_0.1832; (E.g. This pair of mutually defined recurrences are not invertible.)1833define i1 @recurrence_collapse(i8 %A) {1834; CHECK-LABEL: @recurrence_collapse(1835; CHECK-NEXT: entry:1836; CHECK-NEXT: [[B:%.*]] = add i8 [[A:%.*]], 11837; CHECK-NEXT: br label [[LOOP:%.*]]1838; CHECK: loop:1839; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]1840; CHECK-NEXT: [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]1841; CHECK-NEXT: [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]1842; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 11843; CHECK-NEXT: [[A_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]1844; CHECK-NEXT: [[B_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]1845; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 101846; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]1847; CHECK: exit:1848; CHECK-NEXT: [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]1849; CHECK-NEXT: ret i1 [[RES]]1850;1851entry:1852 %B = add i8 %A, 11853 br label %loop1854loop:1855 %iv = phi i64 [0, %entry], [%iv.next, %loop]1856 %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]1857 %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]1858 %iv.next = add i64 %iv, 11859 %A.iv.next = sub i8 %A.iv, %B.iv1860 %B.iv.next = sub i8 %A.iv, %B.iv1861 %cmp = icmp ne i64 %iv.next, 101862 br i1 %cmp, label %loop, label %exit1863exit:1864 %res = icmp eq i8 %A.iv, %B.iv1865 ret i1 %res1866}1867 1868; Illustrate if 2 pointers are non-equal when one of them is a recursive GEP.1869define i1 @icmp_recursiveGEP_withPtr(ptr %val1) {1870; CHECK-LABEL: @icmp_recursiveGEP_withPtr(1871; CHECK-NEXT: entry:1872; CHECK-NEXT: [[CMP_I:%.*]] = icmp eq ptr [[VAL1:%.*]], null1873; CHECK-NEXT: br i1 [[CMP_I]], label [[_Z9STRINGLENPKS_EXIT:%.*]], label [[WHILE_COND_I:%.*]]1874; CHECK: while.cond.i:1875; CHECK-NEXT: [[A_PN_I:%.*]] = phi ptr [ [[TEST_0_I:%.*]], [[WHILE_COND_I]] ], [ [[VAL1]], [[ENTRY:%.*]] ]1876; CHECK-NEXT: [[TEST_0_I]] = getelementptr inbounds i8, ptr [[A_PN_I]], i64 11877; CHECK-NEXT: [[TMP0:%.*]] = load i8, ptr [[TEST_0_I]], align 21878; CHECK-NEXT: [[CMP3_NOT_I:%.*]] = icmp eq i8 [[TMP0]], 01879; CHECK-NEXT: br i1 [[CMP3_NOT_I]], label [[WHILE_END_I:%.*]], label [[WHILE_COND_I]]1880; CHECK: while.end.i:1881; CHECK-NEXT: br label [[_Z9STRINGLENPKS_EXIT]]1882; CHECK: _Z9stringlenPKs.exit:1883; CHECK-NEXT: [[RETVAL_0_I:%.*]] = phi i1 [ false, [[WHILE_END_I]] ], [ true, [[ENTRY]] ]1884; CHECK-NEXT: ret i1 [[RETVAL_0_I]]1885;1886entry:1887 %cmp.i = icmp eq ptr %val1, null1888 br i1 %cmp.i, label %_Z9stringlenPKs.exit, label %while.cond.i1889 1890while.cond.i:1891 %a.pn.i = phi ptr [ %test.0.i, %while.cond.i ], [ %val1, %entry ]1892 %test.0.i = getelementptr inbounds i8, ptr %a.pn.i, i64 11893 %0 = load i8, ptr %test.0.i, align 21894 %cmp3.not.i = icmp eq i8 %0, 01895 br i1 %cmp3.not.i, label %while.end.i, label %while.cond.i1896 1897while.end.i:1898 %bool = icmp eq ptr %test.0.i, %val11899 br label %_Z9stringlenPKs.exit1900 1901_Z9stringlenPKs.exit:1902 %retval.0.i = phi i1 [ %bool, %while.end.i ], [ true, %entry ]1903 ret i1 %retval.0.i1904}1905 1906!0 = !{ i8 1, i8 5 }1907