415 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=instcombine -S | FileCheck %s3 4declare void @use(i32)5 6define i64 @match_unsigned(i64 %x) {7; CHECK-LABEL: @match_unsigned(8; CHECK-NEXT: [[UREM:%.*]] = urem i64 [[X:%.*]], 191369; CHECK-NEXT: ret i64 [[UREM]]10;11 %t = urem i64 %x, 29912 %t1 = udiv i64 %x, 29913 %t2 = urem i64 %t1, 6414 %t3 = mul i64 %t2, 29915 %t4 = add i64 %t, %t316 ret i64 %t417}18 19define <2 x i64> @match_unsigned_vector(<2 x i64> %x) {20; CHECK-LABEL: @match_unsigned_vector(21; CHECK-NEXT: bb:22; CHECK-NEXT: [[UREM:%.*]] = urem <2 x i64> [[X:%.*]], splat (i64 19136)23; CHECK-NEXT: ret <2 x i64> [[UREM]]24;25bb:26 %tmp = urem <2 x i64> %x, <i64 299, i64 299>27 %tmp1 = udiv <2 x i64> %x, <i64 299, i64 299>28 %tmp2 = urem <2 x i64> %tmp1, <i64 64, i64 64>29 %tmp3 = mul <2 x i64> %tmp2, <i64 299, i64 299>30 %tmp4 = add <2 x i64> %tmp, %tmp331 ret <2 x i64> %tmp432}33define i64 @match_andAsRem_lshrAsDiv_shlAsMul(i64 %x) {34; CHECK-LABEL: @match_andAsRem_lshrAsDiv_shlAsMul(35; CHECK-NEXT: [[UREM:%.*]] = urem i64 [[X:%.*]], 57636; CHECK-NEXT: ret i64 [[UREM]]37;38 %t = and i64 %x, 6339 %t1 = lshr i64 %x, 640 %t2 = urem i64 %t1, 941 %t3 = shl i64 %t2, 642 %t4 = add i64 %t, %t343 ret i64 %t444}45 46define i64 @match_signed(i64 %x) {47; CHECK-LABEL: @match_signed(48; CHECK-NEXT: [[SREM1:%.*]] = srem i64 [[X:%.*]], 17222449; CHECK-NEXT: ret i64 [[SREM1]]50;51 %t = srem i64 %x, 29952 %t1 = sdiv i64 %x, 29953 %t2 = srem i64 %t1, 6454 %t3 = sdiv i64 %x, 1913655 %t4 = srem i64 %t3, 956 %t5 = mul i64 %t2, 29957 %t6 = add i64 %t, %t558 %t7 = mul i64 %t4, 1913659 %t8 = add i64 %t6, %t760 ret i64 %t861}62 63define <2 x i64> @match_signed_vector(<2 x i64> %x) {64; CHECK-LABEL: @match_signed_vector(65; CHECK-NEXT: bb:66; CHECK-NEXT: [[SREM1:%.*]] = srem <2 x i64> [[X:%.*]], splat (i64 172224)67; CHECK-NEXT: ret <2 x i64> [[SREM1]]68;69bb:70 %tmp = srem <2 x i64> %x, <i64 299, i64 299>71 %tmp1 = sdiv <2 x i64> %x, <i64 299, i64 299>72 %tmp2 = srem <2 x i64> %tmp1, <i64 64, i64 64>73 %tmp3 = sdiv <2 x i64> %x, <i64 19136, i64 19136>74 %tmp4 = srem <2 x i64> %tmp3, <i64 9, i64 9>75 %tmp5 = mul <2 x i64> %tmp2, <i64 299, i64 299>76 %tmp6 = add <2 x i64> %tmp, %tmp577 %tmp7 = mul <2 x i64> %tmp4, <i64 19136, i64 19136>78 %tmp8 = add <2 x i64> %tmp6, %tmp779 ret <2 x i64> %tmp880}81 82define i64 @not_match_inconsistent_signs(i64 %x) {83; CHECK-LABEL: @not_match_inconsistent_signs(84; CHECK-NEXT: [[T:%.*]] = urem i64 [[X:%.*]], 29985; CHECK-NEXT: [[T1:%.*]] = sdiv i64 [[X]], 29986; CHECK-NEXT: [[T2:%.*]] = and i64 [[T1]], 6387; CHECK-NEXT: [[T3:%.*]] = mul nuw nsw i64 [[T2]], 29988; CHECK-NEXT: [[T4:%.*]] = add nuw nsw i64 [[T]], [[T3]]89; CHECK-NEXT: ret i64 [[T4]]90;91 %t = urem i64 %x, 29992 %t1 = sdiv i64 %x, 29993 %t2 = urem i64 %t1, 6494 %t3 = mul i64 %t2, 29995 %t4 = add i64 %t, %t396 ret i64 %t497}98 99define i64 @not_match_inconsistent_values(i64 %x) {100; CHECK-LABEL: @not_match_inconsistent_values(101; CHECK-NEXT: [[T:%.*]] = urem i64 [[X:%.*]], 299102; CHECK-NEXT: [[T1:%.*]] = udiv i64 [[X]], 29103; CHECK-NEXT: [[T2:%.*]] = and i64 [[T1]], 63104; CHECK-NEXT: [[T3:%.*]] = mul nuw nsw i64 [[T2]], 299105; CHECK-NEXT: [[T4:%.*]] = add nuw nsw i64 [[T]], [[T3]]106; CHECK-NEXT: ret i64 [[T4]]107;108 %t = urem i64 %x, 299109 %t1 = udiv i64 %x, 29110 %t2 = urem i64 %t1, 64111 %t3 = mul i64 %t2, 299112 %t4 = add i64 %t, %t3113 ret i64 %t4114}115 116define i32 @not_match_overflow(i32 %x) {117; CHECK-LABEL: @not_match_overflow(118; CHECK-NEXT: [[X_FR:%.*]] = freeze i32 [[X:%.*]]119; CHECK-NEXT: [[T:%.*]] = urem i32 [[X_FR]], 299120; CHECK-NEXT: [[TMP1:%.*]] = urem i32 [[X_FR]], 299121; CHECK-NEXT: [[T3:%.*]] = sub nuw i32 [[X_FR]], [[TMP1]]122; CHECK-NEXT: [[T4:%.*]] = add i32 [[T]], [[T3]]123; CHECK-NEXT: ret i32 [[T4]]124;125 %t = urem i32 %x, 299126 %t1 = udiv i32 %x, 299127 %t2 = urem i32 %t1, 147483647128 %t3 = mul i32 %t2, 299129 %t4 = add i32 %t, %t3130 ret i32 %t4131}132 133; Tests from PR76128.134define i32 @fold_add_udiv_urem(i32 noundef %val) {135; CHECK-LABEL: @fold_add_udiv_urem(136; CHECK-NEXT: entry:137; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10138; CHECK-NEXT: [[TMP0:%.*]] = mul nuw i32 [[DIV]], 6139; CHECK-NEXT: [[ADD:%.*]] = add i32 [[TMP0]], [[VAL]]140; CHECK-NEXT: ret i32 [[ADD]]141;142entry:143 %div = udiv i32 %val, 10144 %shl = shl i32 %div, 4145 %rem = urem i32 %val, 10146 %add = add i32 %shl, %rem147 ret i32 %add148}149define i32 @fold_add_sdiv_srem(i32 noundef %val) {150; CHECK-LABEL: @fold_add_sdiv_srem(151; CHECK-NEXT: entry:152; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[VAL:%.*]], 10153; CHECK-NEXT: [[TMP0:%.*]] = mul nsw i32 [[DIV]], 6154; CHECK-NEXT: [[ADD:%.*]] = add i32 [[TMP0]], [[VAL]]155; CHECK-NEXT: ret i32 [[ADD]]156;157entry:158 %div = sdiv i32 %val, 10159 %shl = shl i32 %div, 4160 %rem = srem i32 %val, 10161 %add = add i32 %shl, %rem162 ret i32 %add163}164define i32 @fold_add_udiv_urem_to_mul(i32 noundef %val) {165; CHECK-LABEL: @fold_add_udiv_urem_to_mul(166; CHECK-NEXT: entry:167; CHECK-NEXT: [[ADD:%.*]] = mul i32 [[VAL:%.*]], 3168; CHECK-NEXT: ret i32 [[ADD]]169;170entry:171 %div = udiv i32 %val, 7172 %mul1 = mul i32 %div, 21173 %rem = urem i32 %val, 7174 %mul2 = mul i32 %rem, 3175 %add = add i32 %mul1, %mul2176 ret i32 %add177}178define i32 @fold_add_udiv_urem_to_mul_multiuse(i32 noundef %val) {179; CHECK-LABEL: @fold_add_udiv_urem_to_mul_multiuse(180; CHECK-NEXT: entry:181; CHECK-NEXT: [[REM:%.*]] = urem i32 [[VAL:%.*]], 7182; CHECK-NEXT: call void @use(i32 [[REM]])183; CHECK-NEXT: [[ADD:%.*]] = mul i32 [[VAL]], 3184; CHECK-NEXT: ret i32 [[ADD]]185;186entry:187 %div = udiv i32 %val, 7188 %mul1 = mul i32 %div, 21189 %rem = urem i32 %val, 7190 call void @use(i32 %rem)191 %mul2 = mul i32 %rem, 3192 %add = add i32 %mul1, %mul2193 ret i32 %add194}195define i32 @fold_add_udiv_urem_commuted(i32 noundef %val) {196; CHECK-LABEL: @fold_add_udiv_urem_commuted(197; CHECK-NEXT: entry:198; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10199; CHECK-NEXT: [[TMP0:%.*]] = mul nuw i32 [[DIV]], 6200; CHECK-NEXT: [[ADD:%.*]] = add i32 [[TMP0]], [[VAL]]201; CHECK-NEXT: ret i32 [[ADD]]202;203entry:204 %div = udiv i32 %val, 10205 %shl = shl i32 %div, 4206 %rem = urem i32 %val, 10207 %add = add i32 %rem, %shl208 ret i32 %add209}210define i32 @fold_add_udiv_urem_or_disjoint(i32 noundef %val) {211; CHECK-LABEL: @fold_add_udiv_urem_or_disjoint(212; CHECK-NEXT: entry:213; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10214; CHECK-NEXT: [[TMP0:%.*]] = mul nuw i32 [[DIV]], 6215; CHECK-NEXT: [[ADD:%.*]] = add i32 [[TMP0]], [[VAL]]216; CHECK-NEXT: ret i32 [[ADD]]217;218entry:219 %div = udiv i32 %val, 10220 %shl = shl i32 %div, 4221 %rem = urem i32 %val, 10222 %add = or disjoint i32 %shl, %rem223 ret i32 %add224}225; Negative tests226define i32 @fold_add_udiv_urem_without_noundef(i32 %val) {227; CHECK-LABEL: @fold_add_udiv_urem_without_noundef(228; CHECK-NEXT: entry:229; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10230; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[DIV]], 4231; CHECK-NEXT: [[REM:%.*]] = urem i32 [[VAL]], 10232; CHECK-NEXT: [[ADD:%.*]] = or disjoint i32 [[SHL]], [[REM]]233; CHECK-NEXT: ret i32 [[ADD]]234;235entry:236 %div = udiv i32 %val, 10237 %shl = shl i32 %div, 4238 %rem = urem i32 %val, 10239 %add = add i32 %shl, %rem240 ret i32 %add241}242define i32 @fold_add_udiv_urem_multiuse_mul(i32 noundef %val) {243; CHECK-LABEL: @fold_add_udiv_urem_multiuse_mul(244; CHECK-NEXT: entry:245; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10246; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[DIV]], 4247; CHECK-NEXT: call void @use(i32 [[SHL]])248; CHECK-NEXT: [[REM:%.*]] = urem i32 [[VAL]], 10249; CHECK-NEXT: [[ADD:%.*]] = or disjoint i32 [[SHL]], [[REM]]250; CHECK-NEXT: ret i32 [[ADD]]251;252entry:253 %div = udiv i32 %val, 10254 %shl = shl i32 %div, 4255 call void @use(i32 %shl)256 %rem = urem i32 %val, 10257 %add = add i32 %shl, %rem258 ret i32 %add259}260define i32 @fold_add_udiv_srem(i32 noundef %val) {261; CHECK-LABEL: @fold_add_udiv_srem(262; CHECK-NEXT: entry:263; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10264; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[DIV]], 4265; CHECK-NEXT: [[REM:%.*]] = srem i32 [[VAL]], 10266; CHECK-NEXT: [[ADD:%.*]] = add i32 [[SHL]], [[REM]]267; CHECK-NEXT: ret i32 [[ADD]]268;269entry:270 %div = udiv i32 %val, 10271 %shl = shl i32 %div, 4272 %rem = srem i32 %val, 10273 %add = add i32 %shl, %rem274 ret i32 %add275}276define i32 @fold_add_udiv_urem_non_constant(i32 noundef %val, i32 noundef %c) {277; CHECK-LABEL: @fold_add_udiv_urem_non_constant(278; CHECK-NEXT: entry:279; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[VAL:%.*]], [[C:%.*]]280; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[DIV]], 4281; CHECK-NEXT: [[REM:%.*]] = urem i32 [[VAL]], [[C]]282; CHECK-NEXT: [[ADD:%.*]] = add i32 [[SHL]], [[REM]]283; CHECK-NEXT: ret i32 [[ADD]]284;285entry:286 %div = udiv i32 %val, %c287 %shl = shl i32 %div, 4288 %rem = urem i32 %val, %c289 %add = add i32 %shl, %rem290 ret i32 %add291}292 293define i32 @fold_add_udiv_urem_no_mul(i32 noundef %val) {294; CHECK-LABEL: @fold_add_udiv_urem_no_mul(295; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10296; CHECK-NEXT: [[TMP1:%.*]] = mul i32 [[DIV]], -9297; CHECK-NEXT: [[ADD:%.*]] = add i32 [[TMP1]], [[VAL]]298; CHECK-NEXT: ret i32 [[ADD]]299;300 %div = udiv i32 %val, 10301 %rem = urem i32 %val, 10302 %add = add i32 %div, %rem303 ret i32 %add304}305 306define i32 @fold_add_udiv_urem_rem_mul(i32 noundef %val) {307; CHECK-LABEL: @fold_add_udiv_urem_rem_mul(308; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10309; CHECK-NEXT: [[TMP1:%.*]] = mul i32 [[VAL]], 3310; CHECK-NEXT: [[TMP2:%.*]] = mul i32 [[DIV]], -29311; CHECK-NEXT: [[ADD:%.*]] = add i32 [[TMP2]], [[TMP1]]312; CHECK-NEXT: ret i32 [[ADD]]313;314 %div = udiv i32 %val, 10315 %rem = urem i32 %val, 10316 %mul = mul i32 %rem, 3317 %add = add i32 %div, %mul318 ret i32 %add319}320 321define i32 @fold_add_udiv_urem_pow2_no_mul(i32 noundef %arg) {322; CHECK-LABEL: @fold_add_udiv_urem_pow2_no_mul(323; CHECK-NEXT: [[LSHR:%.*]] = lshr i32 [[ARG:%.*]], 4324; CHECK-NEXT: [[AND:%.*]] = and i32 [[ARG]], 15325; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i32 [[LSHR]], [[AND]]326; CHECK-NEXT: ret i32 [[ADD]]327;328 %lshr = lshr i32 %arg, 4329 %and = and i32 %arg, 15330 %add = add i32 %lshr, %and331 ret i32 %add332}333 334define i32 @fold_add_udiv_urem_pow2_div_mul(i32 noundef %arg) {335; CHECK-LABEL: @fold_add_udiv_urem_pow2_div_mul(336; CHECK-NEXT: [[LSHR:%.*]] = lshr i32 [[ARG:%.*]], 4337; CHECK-NEXT: [[TMP1:%.*]] = mul i32 [[LSHR]], -13338; CHECK-NEXT: [[ADD:%.*]] = add i32 [[TMP1]], [[ARG]]339; CHECK-NEXT: ret i32 [[ADD]]340;341 %lshr = lshr i32 %arg, 4342 %mul = mul i32 %lshr, 3343 %and = and i32 %arg, 15344 %add = add i32 %mul, %and345 ret i32 %add346}347 348define i32 @fold_add_sdiv_srem_no_mul(i32 noundef %val) {349; CHECK-LABEL: @fold_add_sdiv_srem_no_mul(350; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[VAL:%.*]], 10351; CHECK-NEXT: [[TMP1:%.*]] = mul i32 [[DIV]], -9352; CHECK-NEXT: [[ADD:%.*]] = add i32 [[TMP1]], [[VAL]]353; CHECK-NEXT: ret i32 [[ADD]]354;355 %div = sdiv i32 %val, 10356 %rem = srem i32 %val, 10357 %add = add i32 %div, %rem358 ret i32 %add359}360 361define i32 @fold_add_udiv_urem_pow2_rem_mul(i32 noundef %arg) {362; CHECK-LABEL: @fold_add_udiv_urem_pow2_rem_mul(363; CHECK-NEXT: [[LSHR:%.*]] = lshr i32 [[ARG:%.*]], 4364; CHECK-NEXT: [[AND:%.*]] = and i32 [[ARG]], 15365; CHECK-NEXT: [[MUL:%.*]] = mul nuw nsw i32 [[AND]], 3366; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i32 [[LSHR]], [[MUL]]367; CHECK-NEXT: ret i32 [[ADD]]368;369 %lshr = lshr i32 %arg, 4370 %and = and i32 %arg, 15371 %mul = mul i32 %and, 3372 %add = add i32 %lshr, %mul373 ret i32 %add374}375 376define i32 @fold_add_udiv_urem_pow2_both_mul(i32 noundef %arg) {377; CHECK-LABEL: @fold_add_udiv_urem_pow2_both_mul(378; CHECK-NEXT: [[LSHR:%.*]] = lshr i32 [[ARG:%.*]], 4379; CHECK-NEXT: [[TMP1:%.*]] = mul i32 [[ARG]], 3380; CHECK-NEXT: [[TMP2:%.*]] = mul i32 [[LSHR]], -41381; CHECK-NEXT: [[ADD:%.*]] = add i32 [[TMP2]], [[TMP1]]382; CHECK-NEXT: ret i32 [[ADD]]383;384 %lshr = lshr i32 %arg, 4385 %mul1 = mul i32 %lshr, 7386 %and = and i32 %arg, 15387 %mul2 = mul i32 %and, 3388 %add = add i32 %mul1, %mul2389 ret i32 %add390}391 392define i32 @fold_add_udiv_urem_by_two_no_mul(i32 noundef %arg) {393; CHECK-LABEL: @fold_add_udiv_urem_by_two_no_mul(394; CHECK-NEXT: [[LSHR:%.*]] = lshr i32 [[ARG:%.*]], 1395; CHECK-NEXT: [[ADD:%.*]] = sub i32 [[ARG]], [[LSHR]]396; CHECK-NEXT: ret i32 [[ADD]]397;398 %lshr = lshr i32 %arg, 1399 %and = and i32 %arg, 1400 %add = add i32 %lshr, %and401 ret i32 %add402}403 404define i32 @fold_add_sdiv_srem_by_two_no_mul(i32 noundef %arg) {405; CHECK-LABEL: @fold_add_sdiv_srem_by_two_no_mul(406; CHECK-NEXT: [[DIV_NEG:%.*]] = sdiv i32 [[ARG:%.*]], -2407; CHECK-NEXT: [[ADD:%.*]] = add i32 [[DIV_NEG]], [[ARG]]408; CHECK-NEXT: ret i32 [[ADD]]409;410 %div = sdiv i32 %arg, 2411 %rem = srem i32 %arg, 2412 %add = add i32 %div, %rem413 ret i32 %add414}415