513 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=instcombine -S | FileCheck %s3 4define i64 @test1(i64 %A, i32 %B) {5; CHECK-LABEL: @test1(6; CHECK-NEXT: [[TMP6:%.*]] = and i64 [[A:%.*]], 1237; CHECK-NEXT: ret i64 [[TMP6]]8;9 %tmp12 = zext i32 %B to i6410 %tmp3 = shl i64 %tmp12, 3211 %tmp5 = add i64 %tmp3, %A12 %tmp6 = and i64 %tmp5, 12313 ret i64 %tmp614}15 16define i32 @test2(i32 %A) {17; CHECK-LABEL: @test2(18; CHECK-NEXT: [[F:%.*]] = and i32 [[A:%.*]], 3919; CHECK-NEXT: ret i32 [[F]]20;21 %B = and i32 %A, 722 %C = and i32 %A, 3223 %F = add i32 %B, %C24 ret i32 %F25}26 27define i32 @test3(i32 %A) {28; CHECK-LABEL: @test3(29; CHECK-NEXT: [[B:%.*]] = and i32 [[A:%.*]], 12830; CHECK-NEXT: [[C:%.*]] = lshr i32 [[A]], 3031; CHECK-NEXT: [[F:%.*]] = or disjoint i32 [[B]], [[C]]32; CHECK-NEXT: ret i32 [[F]]33;34 %B = and i32 %A, 12835 %C = lshr i32 %A, 3036 %F = add i32 %B, %C37 ret i32 %F38}39 40define i32 @test4(i32 %A) {41; CHECK-LABEL: @test4(42; CHECK-NEXT: [[B:%.*]] = shl nuw i32 [[A:%.*]], 143; CHECK-NEXT: ret i32 [[B]]44;45 %B = add nuw i32 %A, %A46 ret i32 %B47}48 49define <2 x i1> @test5(<2 x i1> %A, <2 x i1> %B) {50; CHECK-LABEL: @test5(51; CHECK-NEXT: [[ADD:%.*]] = xor <2 x i1> [[A:%.*]], [[B:%.*]]52; CHECK-NEXT: ret <2 x i1> [[ADD]]53;54 %add = add <2 x i1> %A, %B55 ret <2 x i1> %add56}57 58define <2 x i64> @test6(<2 x i64> %A) {59; CHECK-LABEL: @test6(60; CHECK-NEXT: [[ADD:%.*]] = mul <2 x i64> [[A:%.*]], <i64 5, i64 9>61; CHECK-NEXT: ret <2 x i64> [[ADD]]62;63 %shl = shl <2 x i64> %A, <i64 2, i64 3>64 %add = add <2 x i64> %shl, %A65 ret <2 x i64> %add66}67 68define <2 x i64> @test7(<2 x i64> %A) {69; CHECK-LABEL: @test7(70; CHECK-NEXT: [[ADD:%.*]] = mul <2 x i64> [[A:%.*]], <i64 7, i64 12>71; CHECK-NEXT: ret <2 x i64> [[ADD]]72;73 %shl = shl <2 x i64> %A, <i64 2, i64 3>74 %mul = mul <2 x i64> %A, <i64 3, i64 4>75 %add = add <2 x i64> %shl, %mul76 ret <2 x i64> %add77}78 79define i16 @test9(i16 %a) {80; CHECK-LABEL: @test9(81; CHECK-NEXT: [[D:%.*]] = mul i16 [[A:%.*]], -3276782; CHECK-NEXT: ret i16 [[D]]83;84 %b = mul i16 %a, 285 %c = mul i16 %a, 3276786 %d = add i16 %b, %c87 ret i16 %d88}89 90; y + (~((x >> 3) & 0x55555555) + 1) -> y - ((x >> 3) & 0x55555555)91define i32 @test10(i32 %x, i32 %y) {92; CHECK-LABEL: @test10(93; CHECK-NEXT: [[SHR:%.*]] = ashr i32 [[X:%.*]], 394; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[SHR]], 143165576595; CHECK-NEXT: [[ADD1:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]96; CHECK-NEXT: ret i32 [[ADD1]]97;98 %shr = ashr i32 %x, 399 %shr.not = or i32 %shr, -1431655766100 %neg = xor i32 %shr.not, 1431655765101 %add = add i32 %y, 1102 %add1 = add i32 %add, %neg103 ret i32 %add1104}105 106; y + (~(x & 0x55555555) + 1) -> y - (x & 0x55555555)107define i32 @test11(i32 %x, i32 %y) {108; CHECK-LABEL: @test11(109; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655765110; CHECK-NEXT: [[ADD1:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]111; CHECK-NEXT: ret i32 [[ADD1]]112;113 %x.not = or i32 %x, -1431655766114 %neg = xor i32 %x.not, 1431655765115 %add = add i32 %y, 1116 %add1 = add i32 %add, %neg117 ret i32 %add1118}119 120; (y + 1) + ~(x & 0x55555555) -> y - (x & 0x55555555)121define i32 @test12(i32 %x, i32 %y) {122; CHECK-LABEL: @test12(123; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655765124; CHECK-NEXT: [[ADD1:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]125; CHECK-NEXT: ret i32 [[ADD1]]126;127 %add = add nsw i32 %y, 1128 %x.not = or i32 %x, -1431655766129 %neg = xor i32 %x.not, 1431655765130 %add1 = add nsw i32 %add, %neg131 ret i32 %add1132}133 134; y + (~(x & 0x55555556) + 1) -> y - (x & 0x55555556)135define i32 @test13(i32 %x, i32 %y) {136; CHECK-LABEL: @test13(137; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655766138; CHECK-NEXT: [[ADD1:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]139; CHECK-NEXT: ret i32 [[ADD1]]140;141 %x.not = or i32 %x, -1431655767142 %neg = xor i32 %x.not, 1431655766143 %add = add i32 %y, 1144 %add1 = add i32 %add, %neg145 ret i32 %add1146}147 148; (y + 1) + ~(x & 0x55555556) -> y - (x & 0x55555556)149define i32 @test14(i32 %x, i32 %y) {150; CHECK-LABEL: @test14(151; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655766152; CHECK-NEXT: [[ADD1:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]153; CHECK-NEXT: ret i32 [[ADD1]]154;155 %add = add nsw i32 %y, 1156 %x.not = or i32 %x, -1431655767157 %neg = xor i32 %x.not, 1431655766158 %add1 = add nsw i32 %add, %neg159 ret i32 %add1160}161 162; y + (~(x | 0x55555556) + 1) -> y - (x | 0x55555556)163define i32 @test15(i32 %x, i32 %y) {164; CHECK-LABEL: @test15(165; CHECK-NEXT: [[TMP1:%.*]] = or i32 [[X:%.*]], 1431655766166; CHECK-NEXT: [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]167; CHECK-NEXT: ret i32 [[SUB]]168;169 %x.not = and i32 %x, -1431655767170 %neg = xor i32 %x.not, -1431655767171 %add = add i32 %y, 1172 %add1 = add i32 %add, %neg173 ret i32 %add1174}175 176; (y + 1) + ~(x | 0x55555556) -> y - (x | 0x555555556)177define i32 @test16(i32 %x, i32 %y) {178; CHECK-LABEL: @test16(179; CHECK-NEXT: [[TMP1:%.*]] = or i32 [[X:%.*]], 1431655766180; CHECK-NEXT: [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]181; CHECK-NEXT: ret i32 [[SUB]]182;183 %add = add nsw i32 %y, 1184 %x.not = and i32 %x, -1431655767185 %neg = xor i32 %x.not, -1431655767186 %add1 = add nsw i32 %add, %neg187 ret i32 %add1188}189 190; y + (~(x | 0x55555555) + 1) -> y - (x | 0x55555555)191define i32 @test17(i32 %x, i32 %y) {192; CHECK-LABEL: @test17(193; CHECK-NEXT: [[TMP1:%.*]] = or i32 [[X:%.*]], 1431655765194; CHECK-NEXT: [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]195; CHECK-NEXT: ret i32 [[SUB]]196;197 %x.not = and i32 %x, -1431655766198 %add2 = xor i32 %x.not, -1431655765199 %add1 = add nsw i32 %add2, %y200 ret i32 %add1201}202 203; (y + 1) + ~(x | 0x55555555) -> y - (x | 0x55555555)204define i32 @test18(i32 %x, i32 %y) {205; CHECK-LABEL: @test18(206; CHECK-NEXT: [[TMP1:%.*]] = or i32 [[X:%.*]], 1431655765207; CHECK-NEXT: [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]208; CHECK-NEXT: ret i32 [[SUB]]209;210 %add = add nsw i32 %y, 1211 %x.not = and i32 %x, -1431655766212 %neg = xor i32 %x.not, -1431655766213 %add1 = add nsw i32 %add, %neg214 ret i32 %add1215}216 217define i16 @add_nsw_mul_nsw(i16 %x) {218; CHECK-LABEL: @add_nsw_mul_nsw(219; CHECK-NEXT: [[ADD2:%.*]] = mul nsw i16 [[X:%.*]], 3220; CHECK-NEXT: ret i16 [[ADD2]]221;222 %add1 = add nsw i16 %x, %x223 %add2 = add nsw i16 %add1, %x224 ret i16 %add2225}226 227define i16 @mul_add_to_mul_1(i16 %x) {228; CHECK-LABEL: @mul_add_to_mul_1(229; CHECK-NEXT: [[ADD2:%.*]] = mul nsw i16 [[X:%.*]], 9230; CHECK-NEXT: ret i16 [[ADD2]]231;232 %mul1 = mul nsw i16 %x, 8233 %add2 = add nsw i16 %x, %mul1234 ret i16 %add2235}236 237define i16 @mul_add_to_mul_2(i16 %x) {238; CHECK-LABEL: @mul_add_to_mul_2(239; CHECK-NEXT: [[ADD2:%.*]] = mul nsw i16 [[X:%.*]], 9240; CHECK-NEXT: ret i16 [[ADD2]]241;242 %mul1 = mul nsw i16 %x, 8243 %add2 = add nsw i16 %mul1, %x244 ret i16 %add2245}246 247define i16 @mul_add_to_mul_3(i16 %a) {248; CHECK-LABEL: @mul_add_to_mul_3(249; CHECK-NEXT: [[ADD:%.*]] = mul i16 [[A:%.*]], 5250; CHECK-NEXT: ret i16 [[ADD]]251;252 %mul1 = mul i16 %a, 2253 %mul2 = mul i16 %a, 3254 %add = add nsw i16 %mul1, %mul2255 ret i16 %add256}257 258define i16 @mul_add_to_mul_4(i16 %a) {259; CHECK-LABEL: @mul_add_to_mul_4(260; CHECK-NEXT: [[ADD:%.*]] = mul nsw i16 [[A:%.*]], 9261; CHECK-NEXT: ret i16 [[ADD]]262;263 %mul1 = mul nsw i16 %a, 2264 %mul2 = mul nsw i16 %a, 7265 %add = add nsw i16 %mul1, %mul2266 ret i16 %add267}268 269define i16 @mul_add_to_mul_5(i16 %a) {270; CHECK-LABEL: @mul_add_to_mul_5(271; CHECK-NEXT: [[ADD:%.*]] = mul nsw i16 [[A:%.*]], 10272; CHECK-NEXT: ret i16 [[ADD]]273;274 %mul1 = mul nsw i16 %a, 3275 %mul2 = mul nsw i16 %a, 7276 %add = add nsw i16 %mul1, %mul2277 ret i16 %add278}279 280define i32 @mul_add_to_mul_6(i32 %x, i32 %y) {281; CHECK-LABEL: @mul_add_to_mul_6(282; CHECK-NEXT: [[MUL1:%.*]] = mul nsw i32 [[X:%.*]], [[Y:%.*]]283; CHECK-NEXT: [[ADD:%.*]] = mul nsw i32 [[MUL1]], 6284; CHECK-NEXT: ret i32 [[ADD]]285;286 %mul1 = mul nsw i32 %x, %y287 %mul2 = mul nsw i32 %mul1, 5288 %add = add nsw i32 %mul1, %mul2289 ret i32 %add290}291 292define i16 @mul_add_to_mul_7(i16 %x) {293; CHECK-LABEL: @mul_add_to_mul_7(294; CHECK-NEXT: [[ADD2:%.*]] = shl i16 [[X:%.*]], 15295; CHECK-NEXT: ret i16 [[ADD2]]296;297 %mul1 = mul nsw i16 %x, 32767298 %add2 = add nsw i16 %x, %mul1299 ret i16 %add2300}301 302define i16 @mul_add_to_mul_8(i16 %a) {303; CHECK-LABEL: @mul_add_to_mul_8(304; CHECK-NEXT: [[ADD:%.*]] = mul nsw i16 [[A:%.*]], 32767305; CHECK-NEXT: ret i16 [[ADD]]306;307 %mul1 = mul nsw i16 %a, 16383308 %mul2 = mul nsw i16 %a, 16384309 %add = add nsw i16 %mul1, %mul2310 ret i16 %add311}312 313define i16 @mul_add_to_mul_9(i16 %a) {314; CHECK-LABEL: @mul_add_to_mul_9(315; CHECK-NEXT: [[ADD:%.*]] = shl i16 [[A:%.*]], 15316; CHECK-NEXT: ret i16 [[ADD]]317;318 %mul1 = mul nsw i16 %a, 16384319 %mul2 = mul nsw i16 %a, 16384320 %add = add nsw i16 %mul1, %mul2321 ret i16 %add322}323 324@g = external global i8325 326define i32 @shl_add_to_shl_constexpr() {327; CHECK-LABEL: @shl_add_to_shl_constexpr(328; CHECK-NEXT: [[ADD:%.*]] = shl i32 ptrtoint (ptr @g to i32), 2329; CHECK-NEXT: ret i32 [[ADD]]330;331 %shl = shl i32 ptrtoint (ptr @g to i32), 1332 %add = add i32 %shl, %shl333 ret i32 %add334}335 336; This test and the next test verify that when a range metadata is attached to337; llvm.cttz, ValueTracking correctly intersects the range specified by the338; metadata and the range implied by the intrinsic.339;340; In this test, the range specified by the metadata is more strict. Therefore,341; ValueTracking uses that range.342define i16 @add_cttz(i16 %a) {343; CHECK-LABEL: @add_cttz(344; CHECK-NEXT: [[CTTZ:%.*]] = call i16 @llvm.cttz.i16(i16 [[A:%.*]], i1 true), !range [[RNG0:![0-9]+]]345; CHECK-NEXT: [[B:%.*]] = or disjoint i16 [[CTTZ]], -8346; CHECK-NEXT: ret i16 [[B]]347;348 ; llvm.cttz.i16(..., /*is_zero_undefined=*/true) implies the value returned349 ; is in [0, 16). The range metadata indicates the value returned is in [0, 8).350 ; Intersecting these ranges, we know the value returned is in [0, 8).351 ; Therefore, InstCombine will transform352 ; add %cttz, 1111 1111 1111 1000 ; decimal -8353 ; to354 ; or %cttz, 1111 1111 1111 1000355 %cttz = call i16 @llvm.cttz.i16(i16 %a, i1 true), !range !0356 %b = add i16 %cttz, -8357 ret i16 %b358}359declare i16 @llvm.cttz.i16(i16, i1)360!0 = !{i16 0, i16 8}361 362; Similar to @add_cttz, but in this test, the range implied by the363; intrinsic is more strict. Therefore, ValueTracking uses that range.364define i16 @add_cttz_2(i16 %a) {365; CHECK-LABEL: @add_cttz_2(366; CHECK-NEXT: [[CTTZ:%.*]] = call i16 @llvm.cttz.i16(i16 [[A:%.*]], i1 true), !range [[RNG1:![0-9]+]]367; CHECK-NEXT: [[B:%.*]] = or disjoint i16 [[CTTZ]], -16368; CHECK-NEXT: ret i16 [[B]]369;370 ; llvm.cttz.i16(..., /*is_zero_undefined=*/true) implies the value returned371 ; is in [0, 16). The range metadata indicates the value returned is in372 ; [0, 32). Intersecting these ranges, we know the value returned is in373 ; [0, 16). Therefore, InstCombine will transform374 ; add %cttz, 1111 1111 1111 0000 ; decimal -16375 ; to376 ; or %cttz, 1111 1111 1111 0000377 %cttz = call i16 @llvm.cttz.i16(i16 %a, i1 true), !range !1378 %b = add i16 %cttz, -16379 ret i16 %b380}381!1 = !{i16 0, i16 32}382 383define i32 @add_or_and(i32 %x, i32 %y) {384; CHECK-LABEL: @add_or_and(385; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]386; CHECK-NEXT: ret i32 [[ADD]]387;388 %or = or i32 %x, %y389 %and = and i32 %x, %y390 %add = add i32 %or, %and391 ret i32 %add392}393 394define i32 @add_or_and_commutative(i32 %x, i32 %y) {395; CHECK-LABEL: @add_or_and_commutative(396; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]397; CHECK-NEXT: ret i32 [[ADD]]398;399 %or = or i32 %x, %y400 %and = and i32 %y, %x ; swapped401 %add = add i32 %or, %and402 ret i32 %add403}404 405define i32 @add_and_or(i32 %x, i32 %y) {406; CHECK-LABEL: @add_and_or(407; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]408; CHECK-NEXT: ret i32 [[ADD]]409;410 %or = or i32 %x, %y411 %and = and i32 %x, %y412 %add = add i32 %and, %or413 ret i32 %add414}415 416define i32 @add_and_or_commutative(i32 %x, i32 %y) {417; CHECK-LABEL: @add_and_or_commutative(418; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]419; CHECK-NEXT: ret i32 [[ADD]]420;421 %or = or i32 %x, %y422 %and = and i32 %y, %x ; swapped423 %add = add i32 %and, %or424 ret i32 %add425}426 427define i32 @add_nsw_or_and(i32 %x, i32 %y) {428; CHECK-LABEL: @add_nsw_or_and(429; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[X:%.*]], [[Y:%.*]]430; CHECK-NEXT: ret i32 [[ADD]]431;432 %or = or i32 %x, %y433 %and = and i32 %x, %y434 %add = add nsw i32 %or, %and435 ret i32 %add436}437 438define i32 @add_nuw_or_and(i32 %x, i32 %y) {439; CHECK-LABEL: @add_nuw_or_and(440; CHECK-NEXT: [[ADD:%.*]] = add nuw i32 [[X:%.*]], [[Y:%.*]]441; CHECK-NEXT: ret i32 [[ADD]]442;443 %or = or i32 %x, %y444 %and = and i32 %x, %y445 %add = add nuw i32 %or, %and446 ret i32 %add447}448 449define i32 @add_nuw_nsw_or_and(i32 %x, i32 %y) {450; CHECK-LABEL: @add_nuw_nsw_or_and(451; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i32 [[X:%.*]], [[Y:%.*]]452; CHECK-NEXT: ret i32 [[ADD]]453;454 %or = or i32 %x, %y455 %and = and i32 %x, %y456 %add = add nsw nuw i32 %or, %and457 ret i32 %add458}459 460; A *nsw B + A *nsw C != A *nsw (B + C)461; e.g. A = -1, B = 1, C = INT_SMAX462 463define i8 @add_of_mul(i8 %x, i8 %y, i8 %z) {464; CHECK-LABEL: @add_of_mul(465; CHECK-NEXT: entry:466; CHECK-NEXT: [[MB1:%.*]] = add i8 [[Y:%.*]], [[Z:%.*]]467; CHECK-NEXT: [[SUM:%.*]] = mul i8 [[X:%.*]], [[MB1]]468; CHECK-NEXT: ret i8 [[SUM]]469;470 entry:471 %mA = mul nsw i8 %x, %y472 %mB = mul nsw i8 %x, %z473 %sum = add nsw i8 %mA, %mB474 ret i8 %sum475}476 477define i32 @add_of_selects(i1 %A, i32 %B) {478; CHECK-LABEL: @add_of_selects(479; CHECK-NEXT: [[ADD:%.*]] = select i1 [[A:%.*]], i32 [[B:%.*]], i32 0480; CHECK-NEXT: ret i32 [[ADD]]481;482 %sel0 = select i1 %A, i32 0, i32 -2483 %sel1 = select i1 %A, i32 %B, i32 2484 %add = add i32 %sel0, %sel1485 ret i32 %add486}487 488; The ADD can't cause overflow out of the low 4 bits so the OR can be removed.489 490define i32 @add_undemanded_low_bits(i32 %x) {491; CHECK-LABEL: @add_undemanded_low_bits(492; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], 1616493; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[ADD]], 4494; CHECK-NEXT: ret i32 [[SHR]]495;496 %or = or i32 %x, 15497 %add = add i32 %or, 1616498 %shr = lshr i32 %add, 4499 ret i32 %shr500}501 502define i32 @sub_undemanded_low_bits(i32 %x) {503; CHECK-LABEL: @sub_undemanded_low_bits(504; CHECK-NEXT: [[SUB:%.*]] = add i32 [[X:%.*]], -1616505; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[SUB]], 4506; CHECK-NEXT: ret i32 [[SHR]]507;508 %or = or i32 %x, 15509 %sub = sub i32 %or, 1616510 %shr = lshr i32 %sub, 4511 ret i32 %shr512}513