1400 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(i8)5declare void @use32(i32)6 7declare i8 @llvm.umin.i8(i8, i8)8declare i8 @llvm.umax.i8(i8, i8)9declare i8 @llvm.smin.i8(i8, i8)10declare i8 @llvm.smax.i8(i8, i8)11 12define i32 @t1(i16 zeroext %x, i32 %y) {13; CHECK-LABEL: @t1(14; CHECK-NEXT: [[CONV:%.*]] = zext i16 [[X:%.*]] to i3215; CHECK-NEXT: [[TMP1:%.*]] = add i32 [[Y:%.*]], 116; CHECK-NEXT: [[D1:%.*]] = lshr i32 [[CONV]], [[TMP1]]17; CHECK-NEXT: ret i32 [[D1]]18;19 %conv = zext i16 %x to i3220 %s = shl i32 2, %y21 %d = sdiv i32 %conv, %s22 ret i32 %d23}24 25define <2 x i32> @t1vec(<2 x i16> %x, <2 x i32> %y) {26; CHECK-LABEL: @t1vec(27; CHECK-NEXT: [[CONV:%.*]] = zext <2 x i16> [[X:%.*]] to <2 x i32>28; CHECK-NEXT: [[TMP1:%.*]] = add <2 x i32> [[Y:%.*]], splat (i32 1)29; CHECK-NEXT: [[D1:%.*]] = lshr <2 x i32> [[CONV]], [[TMP1]]30; CHECK-NEXT: ret <2 x i32> [[D1]]31;32 %conv = zext <2 x i16> %x to <2 x i32>33 %s = shl <2 x i32> <i32 2, i32 2>, %y34 %d = sdiv <2 x i32> %conv, %s35 ret <2 x i32> %d36}37 38; rdar://1172132939define i64 @t2(i64 %x, i32 %y) {40; CHECK-LABEL: @t2(41; CHECK-NEXT: [[TMP1:%.*]] = zext nneg i32 [[Y:%.*]] to i6442; CHECK-NEXT: [[TMP2:%.*]] = lshr i64 [[X:%.*]], [[TMP1]]43; CHECK-NEXT: ret i64 [[TMP2]]44;45 %1 = shl i32 1, %y46 %2 = zext i32 %1 to i6447 %3 = udiv i64 %x, %248 ret i64 %349}50 51; PR1325052define i64 @t3(i64 %x, i32 %y) {53; CHECK-LABEL: @t3(54; CHECK-NEXT: [[TMP1:%.*]] = add i32 [[Y:%.*]], 255; CHECK-NEXT: [[TMP2:%.*]] = zext nneg i32 [[TMP1]] to i6456; CHECK-NEXT: [[TMP3:%.*]] = lshr i64 [[X:%.*]], [[TMP2]]57; CHECK-NEXT: ret i64 [[TMP3]]58;59 %1 = shl i32 4, %y60 %2 = zext i32 %1 to i6461 %3 = udiv i64 %x, %262 ret i64 %363}64 65define i32 @t4(i32 %x, i32 %y) {66; CHECK-LABEL: @t4(67; CHECK-NEXT: [[TMP1:%.*]] = call i32 @llvm.umax.i32(i32 [[Y:%.*]], i32 5)68; CHECK-NEXT: [[TMP2:%.*]] = lshr i32 [[X:%.*]], [[TMP1]]69; CHECK-NEXT: ret i32 [[TMP2]]70;71 %1 = shl i32 1, %y72 %2 = icmp ult i32 %1, 3273 %3 = select i1 %2, i32 32, i32 %174 %4 = udiv i32 %x, %375 ret i32 %476}77 78define i32 @t5(i1 %x, i1 %y, i32 %V) {79; CHECK-LABEL: @t5(80; CHECK-NEXT: [[TMP1:%.*]] = select i1 [[X:%.*]], i32 5, i32 681; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[Y:%.*]], i32 [[TMP1]], i32 [[V:%.*]]82; CHECK-NEXT: [[TMP3:%.*]] = lshr i32 [[V]], [[TMP2]]83; CHECK-NEXT: ret i32 [[TMP3]]84;85 %1 = shl i32 1, %V86 %2 = select i1 %x, i32 32, i32 6487 %3 = select i1 %y, i32 %2, i32 %188 %4 = udiv i32 %V, %389 ret i32 %490}91 92define i32 @t6(i32 %x, i32 %z) {93; CHECK-LABEL: @t6(94; CHECK-NEXT: [[DIVISOR:%.*]] = call i32 @llvm.umax.i32(i32 [[X:%.*]], i32 1)95; CHECK-NEXT: [[Y:%.*]] = udiv i32 [[Z:%.*]], [[DIVISOR]]96; CHECK-NEXT: ret i32 [[Y]]97;98 %x_is_zero = icmp eq i32 %x, 099 %divisor = select i1 %x_is_zero, i32 1, i32 %x100 %y = udiv i32 %z, %divisor101 ret i32 %y102}103 104define i8 @udiv_umin(i8 %x, i8 %y, i8 %z) {105; CHECK-LABEL: @udiv_umin(106; CHECK-NEXT: [[TMP1:%.*]] = call i8 @llvm.umin.i8(i8 [[Y:%.*]], i8 [[Z:%.*]])107; CHECK-NEXT: [[D1:%.*]] = lshr i8 [[X:%.*]], [[TMP1]]108; CHECK-NEXT: ret i8 [[D1]]109;110 %y2 = shl i8 1, %y111 %z2 = shl i8 1, %z112 %m = call i8 @llvm.umin.i8(i8 %y2, i8 %z2)113 %d = udiv i8 %x, %m114 ret i8 %d115}116 117define i8 @udiv_umax(i8 %x, i8 %y, i8 %z) {118; CHECK-LABEL: @udiv_umax(119; CHECK-NEXT: [[TMP1:%.*]] = call i8 @llvm.umax.i8(i8 [[Y:%.*]], i8 [[Z:%.*]])120; CHECK-NEXT: [[D1:%.*]] = lshr i8 [[X:%.*]], [[TMP1]]121; CHECK-NEXT: ret i8 [[D1]]122;123 %y2 = shl i8 1, %y124 %z2 = shl i8 1, %z125 %m = call i8 @llvm.umax.i8(i8 %y2, i8 %z2)126 %d = udiv i8 %x, %m127 ret i8 %d128}129 130; Negative test, cannot take exact log2131define i8 @udiv_umin_(i8 %x, i8 %y, i8 %z) {132; CHECK-LABEL: @udiv_umin_(133; CHECK-NEXT: [[Y2:%.*]] = shl nuw i8 1, [[Y:%.*]]134; CHECK-NEXT: [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[Y2]], i8 [[Z:%.*]])135; CHECK-NEXT: [[D:%.*]] = udiv i8 [[X:%.*]], [[M]]136; CHECK-NEXT: ret i8 [[D]]137;138 %y2 = shl i8 1, %y139 %m = call i8 @llvm.umin.i8(i8 %y2, i8 %z)140 %d = udiv i8 %x, %m141 ret i8 %d142}143 144; Negative test, extra use145define i8 @udiv_umin_extra_use(i8 %x, i8 %y, i8 %z) {146; CHECK-LABEL: @udiv_umin_extra_use(147; CHECK-NEXT: [[TMP1:%.*]] = call i8 @llvm.umin.i8(i8 [[Y:%.*]], i8 [[Z:%.*]])148; CHECK-NEXT: [[M:%.*]] = shl nuw i8 1, [[TMP1]]149; CHECK-NEXT: call void @use(i8 [[M]])150; CHECK-NEXT: [[D:%.*]] = lshr i8 [[X:%.*]], [[TMP1]]151; CHECK-NEXT: ret i8 [[D]]152;153 %y2 = shl i8 1, %y154 %z2 = shl i8 1, %z155 %m = call i8 @llvm.umin.i8(i8 %y2, i8 %z2)156 call void @use(i8 %m)157 %d = udiv i8 %x, %m158 ret i8 %d159}160 161; Negative test, signed min/max162define i8 @udiv_smin(i8 %x, i8 %y, i8 %z) {163; CHECK-LABEL: @udiv_smin(164; CHECK-NEXT: [[Y2:%.*]] = shl nuw i8 1, [[Y:%.*]]165; CHECK-NEXT: [[Z2:%.*]] = shl nuw i8 1, [[Z:%.*]]166; CHECK-NEXT: [[M:%.*]] = call i8 @llvm.smin.i8(i8 [[Y2]], i8 [[Z2]])167; CHECK-NEXT: [[TMP1:%.*]] = call range(i8 0, 9) i8 @llvm.cttz.i8(i8 [[M]], i1 true)168; CHECK-NEXT: [[D:%.*]] = lshr i8 [[X:%.*]], [[TMP1]]169; CHECK-NEXT: ret i8 [[D]]170;171 %y2 = shl i8 1, %y172 %z2 = shl i8 1, %z173 %m = call i8 @llvm.smin.i8(i8 %y2, i8 %z2)174 %d = udiv i8 %x, %m175 ret i8 %d176}177 178; Negative test, signed min/max179define i8 @udiv_smax(i8 %x, i8 %y, i8 %z) {180; CHECK-LABEL: @udiv_smax(181; CHECK-NEXT: [[Y2:%.*]] = shl nuw i8 1, [[Y:%.*]]182; CHECK-NEXT: [[Z2:%.*]] = shl nuw i8 1, [[Z:%.*]]183; CHECK-NEXT: [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[Y2]], i8 [[Z2]])184; CHECK-NEXT: [[TMP1:%.*]] = call range(i8 0, 9) i8 @llvm.cttz.i8(i8 [[M]], i1 true)185; CHECK-NEXT: [[D:%.*]] = lshr i8 [[X:%.*]], [[TMP1]]186; CHECK-NEXT: ret i8 [[D]]187;188 %y2 = shl i8 1, %y189 %z2 = shl i8 1, %z190 %m = call i8 @llvm.smax.i8(i8 %y2, i8 %z2)191 %d = udiv i8 %x, %m192 ret i8 %d193}194 195; (X << C1) / X -> 1 << C1 optimizations196 197define i32 @t7(i32 %x) {198; CHECK-LABEL: @t7(199; CHECK-NEXT: ret i32 4200;201 %shl = shl nsw i32 %x, 2202 %r = sdiv i32 %shl, %x203 ret i32 %r204}205 206; make sure the previous opt doesn't take place for wrapped shifts207 208define i32 @t8(i32 %x) {209; CHECK-LABEL: @t8(210; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[X:%.*]], 2211; CHECK-NEXT: [[R:%.*]] = sdiv i32 [[SHL]], [[X]]212; CHECK-NEXT: ret i32 [[R]]213;214 %shl = shl i32 %x, 2215 %r = sdiv i32 %shl, %x216 ret i32 %r217}218 219define <2 x i32> @t9(<2 x i32> %x) {220; CHECK-LABEL: @t9(221; CHECK-NEXT: ret <2 x i32> <i32 4, i32 8>222;223 %shl = shl nsw <2 x i32> %x, <i32 2, i32 3>224 %r = sdiv <2 x i32> %shl, %x225 ret <2 x i32> %r226}227 228define i32 @t10(i32 %x, i32 %y) {229; CHECK-LABEL: @t10(230; CHECK-NEXT: [[R:%.*]] = shl nuw nsw i32 1, [[Y:%.*]]231; CHECK-NEXT: ret i32 [[R]]232;233 %shl = shl nsw i32 %x, %y234 %r = sdiv i32 %shl, %x235 ret i32 %r236}237 238define <2 x i32> @t11(<2 x i32> %x, <2 x i32> %y) {239; CHECK-LABEL: @t11(240; CHECK-NEXT: [[R:%.*]] = shl nuw nsw <2 x i32> splat (i32 1), [[Y:%.*]]241; CHECK-NEXT: ret <2 x i32> [[R]]242;243 %shl = shl nsw <2 x i32> %x, %y244 %r = sdiv <2 x i32> %shl, %x245 ret <2 x i32> %r246}247 248define i32 @t12(i32 %x) {249; CHECK-LABEL: @t12(250; CHECK-NEXT: ret i32 4251;252 %shl = shl nuw i32 %x, 2253 %r = udiv i32 %shl, %x254 ret i32 %r255}256 257; make sure the previous opt doesn't take place for wrapped shifts258 259define i32 @t13(i32 %x) {260; CHECK-LABEL: @t13(261; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[X:%.*]], 2262; CHECK-NEXT: [[R:%.*]] = udiv i32 [[SHL]], [[X]]263; CHECK-NEXT: ret i32 [[R]]264;265 %shl = shl i32 %x, 2266 %r = udiv i32 %shl, %x267 ret i32 %r268}269 270define <2 x i32> @t14(<2 x i32> %x) {271; CHECK-LABEL: @t14(272; CHECK-NEXT: ret <2 x i32> <i32 4, i32 8>273;274 %shl = shl nuw <2 x i32> %x, <i32 2, i32 3>275 %r = udiv <2 x i32> %shl, %x276 ret <2 x i32> %r277}278 279define i32 @t15(i32 %x, i32 %y) {280; CHECK-LABEL: @t15(281; CHECK-NEXT: [[R:%.*]] = shl nuw i32 1, [[Y:%.*]]282; CHECK-NEXT: ret i32 [[R]]283;284 %shl = shl nuw i32 %x, %y285 %r = udiv i32 %shl, %x286 ret i32 %r287}288 289define <2 x i32> @t16(<2 x i32> %x, <2 x i32> %y) {290; CHECK-LABEL: @t16(291; CHECK-NEXT: [[R:%.*]] = shl nuw <2 x i32> splat (i32 1), [[Y:%.*]]292; CHECK-NEXT: ret <2 x i32> [[R]]293;294 %shl = shl nuw <2 x i32> %x, %y295 %r = udiv <2 x i32> %shl, %x296 ret <2 x i32> %r297}298 299; (X * Y) s/ (X << Z) --> Y s/ (1 << Z)300 301define i5 @sdiv_mul_shl_nsw(i5 %x, i5 %y, i5 %z) {302; CHECK-LABEL: @sdiv_mul_shl_nsw(303; CHECK-NEXT: [[TMP1:%.*]] = shl nuw i5 1, [[Z:%.*]]304; CHECK-NEXT: [[D:%.*]] = sdiv i5 [[Y:%.*]], [[TMP1]]305; CHECK-NEXT: ret i5 [[D]]306;307 %m1 = mul nsw i5 %x, %y308 %m2 = shl nsw i5 %x, %z309 %d = sdiv i5 %m1, %m2310 ret i5 %d311}312 313; (Y * Z) s/ (X << Z) --> Y s/ (1 << Z)314 315define i5 @sdiv_mul_shl_nsw_exact_commute1(i5 %x, i5 %y, i5 %z) {316; CHECK-LABEL: @sdiv_mul_shl_nsw_exact_commute1(317; CHECK-NEXT: [[TMP1:%.*]] = shl nuw i5 1, [[Z:%.*]]318; CHECK-NEXT: [[D:%.*]] = sdiv exact i5 [[Y:%.*]], [[TMP1]]319; CHECK-NEXT: ret i5 [[D]]320;321 %m1 = mul nsw i5 %y, %x322 %m2 = shl nsw i5 %x, %z323 %d = sdiv exact i5 %m1, %m2324 ret i5 %d325}326 327; negative test - shl is not commutative328 329define i5 @sdiv_mul_shl_nsw_commute2(i5 %x, i5 %y, i5 %z) {330; CHECK-LABEL: @sdiv_mul_shl_nsw_commute2(331; CHECK-NEXT: [[M1:%.*]] = mul nsw i5 [[Y:%.*]], [[X:%.*]]332; CHECK-NEXT: [[M2:%.*]] = shl nsw i5 [[Z:%.*]], [[X]]333; CHECK-NEXT: [[D:%.*]] = sdiv i5 [[M1]], [[M2]]334; CHECK-NEXT: ret i5 [[D]]335;336 %m1 = mul nsw i5 %y, %x337 %m2 = shl nsw i5 %z, %x338 %d = sdiv i5 %m1, %m2339 ret i5 %d340}341 342; extra use is ok343 344define i8 @sdiv_mul_shl_nsw_use1(i8 %x, i8 %y, i8 %z) {345; CHECK-LABEL: @sdiv_mul_shl_nsw_use1(346; CHECK-NEXT: [[M1:%.*]] = mul nsw i8 [[X:%.*]], [[Y:%.*]]347; CHECK-NEXT: call void @use(i8 [[M1]])348; CHECK-NEXT: [[TMP1:%.*]] = shl nuw i8 1, [[Z:%.*]]349; CHECK-NEXT: [[D:%.*]] = sdiv i8 [[Y]], [[TMP1]]350; CHECK-NEXT: ret i8 [[D]]351;352 %m1 = mul nsw i8 %x, %y353 call void @use(i8 %m1)354 %m2 = shl nsw i8 %x, %z355 %d = sdiv i8 %m1, %m2356 ret i8 %d357}358 359; extra use is ok360 361define i8 @sdiv_mul_shl_nsw_use2(i8 %x, i8 %y, i8 %z) {362; CHECK-LABEL: @sdiv_mul_shl_nsw_use2(363; CHECK-NEXT: [[M2:%.*]] = shl nsw i8 [[X:%.*]], [[Z:%.*]]364; CHECK-NEXT: call void @use(i8 [[M2]])365; CHECK-NEXT: [[TMP1:%.*]] = shl nuw i8 1, [[Z]]366; CHECK-NEXT: [[D:%.*]] = sdiv i8 [[Y:%.*]], [[TMP1]]367; CHECK-NEXT: ret i8 [[D]]368;369 %m1 = mul nsw i8 %x, %y370 %m2 = shl nsw i8 %x, %z371 call void @use(i8 %m2)372 %d = sdiv i8 %m1, %m2373 ret i8 %d374}375 376; negative test - both operands can't have extra uses377 378define i8 @sdiv_mul_shl_nsw_use3(i8 %x, i8 %y, i8 %z) {379; CHECK-LABEL: @sdiv_mul_shl_nsw_use3(380; CHECK-NEXT: [[M1:%.*]] = mul nsw i8 [[X:%.*]], [[Y:%.*]]381; CHECK-NEXT: call void @use(i8 [[M1]])382; CHECK-NEXT: [[M2:%.*]] = shl nsw i8 [[X]], [[Z:%.*]]383; CHECK-NEXT: call void @use(i8 [[M2]])384; CHECK-NEXT: [[D:%.*]] = sdiv i8 [[M1]], [[M2]]385; CHECK-NEXT: ret i8 [[D]]386;387 %m1 = mul nsw i8 %x, %y388 call void @use(i8 %m1)389 %m2 = shl nsw i8 %x, %z390 call void @use(i8 %m2)391 %d = sdiv i8 %m1, %m2392 ret i8 %d393}394 395; negative test - shl must be divisor396 397define i5 @sdiv_shl_mul_nsw(i5 %x, i5 %y, i5 %z) {398; CHECK-LABEL: @sdiv_shl_mul_nsw(399; CHECK-NEXT: [[M1:%.*]] = shl nsw i5 [[Z:%.*]], [[X:%.*]]400; CHECK-NEXT: [[M2:%.*]] = mul nsw i5 [[X]], [[Y:%.*]]401; CHECK-NEXT: [[D:%.*]] = sdiv i5 [[M1]], [[M2]]402; CHECK-NEXT: ret i5 [[D]]403;404 %m1 = shl nsw i5 %z, %x405 %m2 = mul nsw i5 %x, %y406 %d = sdiv i5 %m1, %m2407 ret i5 %d408}409 410; negative test - wrong no-wrap411 412define i5 @sdiv_mul_shl_missing_nsw1(i5 %x, i5 %y, i5 %z) {413; CHECK-LABEL: @sdiv_mul_shl_missing_nsw1(414; CHECK-NEXT: [[M1:%.*]] = mul nsw i5 [[X:%.*]], [[Y:%.*]]415; CHECK-NEXT: [[M2:%.*]] = shl nuw i5 [[Y]], [[Z:%.*]]416; CHECK-NEXT: [[D:%.*]] = sdiv i5 [[M1]], [[M2]]417; CHECK-NEXT: ret i5 [[D]]418;419 %m1 = mul nsw i5 %x, %y420 %m2 = shl nuw i5 %y, %z421 %d = sdiv i5 %m1, %m2422 ret i5 %d423}424 425; negative test - wrong no-wrap426 427define i5 @sdiv_mul_shl_missing_nsw2(i5 %x, i5 %y, i5 %z) {428; CHECK-LABEL: @sdiv_mul_shl_missing_nsw2(429; CHECK-NEXT: [[M1:%.*]] = mul nuw i5 [[X:%.*]], [[Y:%.*]]430; CHECK-NEXT: [[M2:%.*]] = shl nsw i5 [[Y]], [[Z:%.*]]431; CHECK-NEXT: [[D:%.*]] = sdiv i5 [[M1]], [[M2]]432; CHECK-NEXT: ret i5 [[D]]433;434 %m1 = mul nuw i5 %x, %y435 %m2 = shl nsw i5 %y, %z436 %d = sdiv i5 %m1, %m2437 ret i5 %d438}439 440; (X * Y) u/ (X << Z) --> Y u>> Z441 442define i5 @udiv_mul_shl_nuw(i5 %x, i5 %y, i5 %z) {443; CHECK-LABEL: @udiv_mul_shl_nuw(444; CHECK-NEXT: [[D:%.*]] = lshr i5 [[Y:%.*]], [[Z:%.*]]445; CHECK-NEXT: ret i5 [[D]]446;447 %m1 = mul nuw i5 %x, %y448 %m2 = shl nuw i5 %x, %z449 %d = udiv i5 %m1, %m2450 ret i5 %d451}452 453; (Y * X) u/ (X << Z) --> Y u>> Z454 455define i5 @udiv_mul_shl_nuw_exact_commute1(i5 %x, i5 %y, i5 %z) {456; CHECK-LABEL: @udiv_mul_shl_nuw_exact_commute1(457; CHECK-NEXT: [[D:%.*]] = lshr exact i5 [[Y:%.*]], [[Z:%.*]]458; CHECK-NEXT: ret i5 [[D]]459;460 %m1 = mul nuw i5 %y, %x461 %m2 = shl nuw i5 %x, %z462 %d = udiv exact i5 %m1, %m2463 ret i5 %d464}465 466; negative test - shl is not commutative467 468define i5 @udiv_mul_shl_nuw_commute2(i5 %x, i5 %y, i5 %z) {469; CHECK-LABEL: @udiv_mul_shl_nuw_commute2(470; CHECK-NEXT: [[M1:%.*]] = mul nuw i5 [[X:%.*]], [[Y:%.*]]471; CHECK-NEXT: [[M2:%.*]] = shl nuw i5 [[Z:%.*]], [[X]]472; CHECK-NEXT: [[D:%.*]] = udiv i5 [[M1]], [[M2]]473; CHECK-NEXT: ret i5 [[D]]474;475 %m1 = mul nuw i5 %x, %y476 %m2 = shl nuw i5 %z, %x477 %d = udiv i5 %m1, %m2478 ret i5 %d479}480 481; extra uses are ok482 483define i8 @udiv_mul_shl_nsw_use1(i8 %x, i8 %y, i8 %z) {484; CHECK-LABEL: @udiv_mul_shl_nsw_use1(485; CHECK-NEXT: [[M1:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]486; CHECK-NEXT: call void @use(i8 [[M1]])487; CHECK-NEXT: [[D:%.*]] = lshr i8 [[Y]], [[Z:%.*]]488; CHECK-NEXT: ret i8 [[D]]489;490 %m1 = mul nuw i8 %x, %y491 call void @use(i8 %m1)492 %m2 = shl nuw i8 %x, %z493 %d = udiv i8 %m1, %m2494 ret i8 %d495}496 497; extra uses are ok498 499define i8 @udiv_mul_shl_nsw_use2(i8 %x, i8 %y, i8 %z) {500; CHECK-LABEL: @udiv_mul_shl_nsw_use2(501; CHECK-NEXT: [[M2:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]502; CHECK-NEXT: call void @use(i8 [[M2]])503; CHECK-NEXT: [[D:%.*]] = lshr i8 [[Y:%.*]], [[Z]]504; CHECK-NEXT: ret i8 [[D]]505;506 %m1 = mul nuw i8 %x, %y507 %m2 = shl nuw i8 %x, %z508 call void @use(i8 %m2)509 %d = udiv i8 %m1, %m2510 ret i8 %d511}512 513; extra uses are ok514 515define i8 @udiv_mul_shl_nsw_use3(i8 %x, i8 %y, i8 %z) {516; CHECK-LABEL: @udiv_mul_shl_nsw_use3(517; CHECK-NEXT: [[M1:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]518; CHECK-NEXT: call void @use(i8 [[M1]])519; CHECK-NEXT: [[M2:%.*]] = shl nuw i8 [[X]], [[Z:%.*]]520; CHECK-NEXT: call void @use(i8 [[M2]])521; CHECK-NEXT: [[D:%.*]] = lshr i8 [[Y]], [[Z]]522; CHECK-NEXT: ret i8 [[D]]523;524 %m1 = mul nuw i8 %x, %y525 call void @use(i8 %m1)526 %m2 = shl nuw i8 %x, %z527 call void @use(i8 %m2)528 %d = udiv i8 %m1, %m2529 ret i8 %d530}531 532; (X << Z) / (X * Y) -> (1 << Z) / Y533 534define i5 @udiv_shl_mul_nuw(i5 %x, i5 %y, i5 %z) {535; CHECK-LABEL: @udiv_shl_mul_nuw(536; CHECK-NEXT: [[TMP1:%.*]] = shl nuw i5 1, [[Z:%.*]]537; CHECK-NEXT: [[D:%.*]] = udiv i5 [[TMP1]], [[Y:%.*]]538; CHECK-NEXT: ret i5 [[D]]539;540 %m1 = shl nuw i5 %x, %z541 %m2 = mul nuw i5 %x, %y542 %d = udiv i5 %m1, %m2543 ret i5 %d544}545 546define i5 @udiv_shl_mul_nuw_swap(i5 %x, i5 %y, i5 %z) {547; CHECK-LABEL: @udiv_shl_mul_nuw_swap(548; CHECK-NEXT: [[TMP1:%.*]] = shl nuw i5 1, [[Z:%.*]]549; CHECK-NEXT: [[D:%.*]] = udiv i5 [[TMP1]], [[Y:%.*]]550; CHECK-NEXT: ret i5 [[D]]551;552 %m1 = shl nuw i5 %x, %z553 %m2 = mul nuw i5 %y, %x554 %d = udiv i5 %m1, %m2555 ret i5 %d556}557 558define i5 @udiv_shl_mul_nuw_exact(i5 %x, i5 %y, i5 %z) {559; CHECK-LABEL: @udiv_shl_mul_nuw_exact(560; CHECK-NEXT: [[TMP1:%.*]] = shl nuw i5 1, [[Z:%.*]]561; CHECK-NEXT: [[D:%.*]] = udiv exact i5 [[TMP1]], [[Y:%.*]]562; CHECK-NEXT: ret i5 [[D]]563;564 %m1 = shl nuw i5 %x, %z565 %m2 = mul nuw i5 %x, %y566 %d = udiv exact i5 %m1, %m2567 ret i5 %d568}569 570define <2 x i4> @udiv_shl_mul_nuw_vec(<2 x i4> %x, <2 x i4> %y, <2 x i4> %z) {571; CHECK-LABEL: @udiv_shl_mul_nuw_vec(572; CHECK-NEXT: [[TMP1:%.*]] = shl nuw <2 x i4> splat (i4 1), [[Z:%.*]]573; CHECK-NEXT: [[D:%.*]] = udiv <2 x i4> [[TMP1]], [[Y:%.*]]574; CHECK-NEXT: ret <2 x i4> [[D]]575;576 %m1 = shl nuw <2 x i4> %x, %z577 %m2 = mul nuw <2 x i4> %y, %x578 %d = udiv <2 x i4> %m1, %m2579 ret <2 x i4> %d580}581 582define i8 @udiv_shl_mul_nuw_extra_use_of_shl(i8 %x, i8 %y, i8 %z) {583; CHECK-LABEL: @udiv_shl_mul_nuw_extra_use_of_shl(584; CHECK-NEXT: [[M1:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]585; CHECK-NEXT: call void @use(i8 [[M1]])586; CHECK-NEXT: [[TMP1:%.*]] = shl nuw i8 1, [[Z]]587; CHECK-NEXT: [[D:%.*]] = udiv i8 [[TMP1]], [[Y:%.*]]588; CHECK-NEXT: ret i8 [[D]]589;590 %m1 = shl nuw i8 %x, %z591 call void @use(i8 %m1)592 %m2 = mul nuw i8 %y, %x593 %d = udiv i8 %m1, %m2594 ret i8 %d595}596 597; negative test - extra use598 599define i8 @udiv_shl_mul_nuw_extra_use_of_mul(i8 %x, i8 %y, i8 %z) {600; CHECK-LABEL: @udiv_shl_mul_nuw_extra_use_of_mul(601; CHECK-NEXT: [[M1:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]602; CHECK-NEXT: [[M2:%.*]] = mul nuw i8 [[Y:%.*]], [[X]]603; CHECK-NEXT: call void @use(i8 [[M2]])604; CHECK-NEXT: [[D:%.*]] = udiv i8 [[M1]], [[M2]]605; CHECK-NEXT: ret i8 [[D]]606;607 %m1 = shl nuw i8 %x, %z608 %m2 = mul nuw i8 %y, %x609 call void @use(i8 %m2)610 %d = udiv i8 %m1, %m2611 ret i8 %d612}613 614define i8 @udiv_shl_mul_nuw_extra_use(i8 %x, i8 %y, i8 %z) {615; CHECK-LABEL: @udiv_shl_mul_nuw_extra_use(616; CHECK-NEXT: [[M1:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]617; CHECK-NEXT: call void @use(i8 [[M1]])618; CHECK-NEXT: [[M2:%.*]] = mul nuw i8 [[Y:%.*]], [[X]]619; CHECK-NEXT: call void @use(i8 [[M2]])620; CHECK-NEXT: [[D:%.*]] = udiv i8 [[M1]], [[M2]]621; CHECK-NEXT: ret i8 [[D]]622;623 %m1 = shl nuw i8 %x, %z624 call void @use(i8 %m1)625 %m2 = mul nuw i8 %y, %x626 call void @use(i8 %m2)627 %d = udiv i8 %m1, %m2628 ret i8 %d629}630 631; negative test - sdiv632 633define i5 @sdiv_shl_mul_nuw(i5 %x, i5 %y, i5 %z) {634; CHECK-LABEL: @sdiv_shl_mul_nuw(635; CHECK-NEXT: [[M1:%.*]] = shl nuw i5 [[X:%.*]], [[Z:%.*]]636; CHECK-NEXT: [[M2:%.*]] = mul nuw i5 [[X]], [[Y:%.*]]637; CHECK-NEXT: [[D:%.*]] = sdiv i5 [[M1]], [[M2]]638; CHECK-NEXT: ret i5 [[D]]639;640 %m1 = shl nuw i5 %x, %z641 %m2 = mul nuw i5 %x, %y642 %d = sdiv i5 %m1, %m2643 ret i5 %d644}645 646; negative test - wrong no-wrap647 648define i5 @udiv_mul_shl_missing_nsw1(i5 %x, i5 %y, i5 %z) {649; CHECK-LABEL: @udiv_mul_shl_missing_nsw1(650; CHECK-NEXT: [[M1:%.*]] = mul nsw i5 [[X:%.*]], [[Y:%.*]]651; CHECK-NEXT: [[M2:%.*]] = shl nuw i5 [[Y]], [[Z:%.*]]652; CHECK-NEXT: [[D:%.*]] = udiv i5 [[M1]], [[M2]]653; CHECK-NEXT: ret i5 [[D]]654;655 %m1 = mul nsw i5 %x, %y656 %m2 = shl nuw i5 %y, %z657 %d = udiv i5 %m1, %m2658 ret i5 %d659}660 661; negative test - wrong no-wrap662 663define i5 @udiv_mul_shl_missing_nsw2(i5 %x, i5 %y, i5 %z) {664; CHECK-LABEL: @udiv_mul_shl_missing_nsw2(665; CHECK-NEXT: [[M1:%.*]] = mul nuw i5 [[X:%.*]], [[Y:%.*]]666; CHECK-NEXT: [[M2:%.*]] = shl nsw i5 [[Y]], [[Z:%.*]]667; CHECK-NEXT: [[D:%.*]] = udiv i5 [[M1]], [[M2]]668; CHECK-NEXT: ret i5 [[D]]669;670 %m1 = mul nuw i5 %x, %y671 %m2 = shl nsw i5 %y, %z672 %d = udiv i5 %m1, %m2673 ret i5 %d674}675 676define i8 @udiv_shl_nuw(i8 %x, i8 %y, i8 %z) {677; CHECK-LABEL: @udiv_shl_nuw(678; CHECK-NEXT: [[S:%.*]] = shl nuw i8 [[Y:%.*]], [[Z:%.*]]679; CHECK-NEXT: [[D:%.*]] = udiv i8 [[X:%.*]], [[S]]680; CHECK-NEXT: ret i8 [[D]]681;682 %s = shl nuw i8 %y, %z683 %d = udiv i8 %x, %s684 ret i8 %d685}686 687define <2 x i4> @udiv_shl_nuw_exact(<2 x i4> %x, <2 x i4> %y, <2 x i4> %z) {688; CHECK-LABEL: @udiv_shl_nuw_exact(689; CHECK-NEXT: [[S:%.*]] = shl nuw <2 x i4> [[Y:%.*]], [[Z:%.*]]690; CHECK-NEXT: [[D:%.*]] = udiv exact <2 x i4> [[X:%.*]], [[S]]691; CHECK-NEXT: ret <2 x i4> [[D]]692;693 %s = shl nuw <2 x i4> %y, %z694 %d = udiv exact <2 x i4> %x, %s695 ret <2 x i4> %d696}697 698define i8 @udiv_shl(i8 %x, i8 %y, i8 %z) {699; CHECK-LABEL: @udiv_shl(700; CHECK-NEXT: [[S:%.*]] = shl i8 [[Y:%.*]], [[Z:%.*]]701; CHECK-NEXT: [[D:%.*]] = udiv i8 [[X:%.*]], [[S]]702; CHECK-NEXT: ret i8 [[D]]703;704 %s = shl i8 %y, %z705 %d = udiv i8 %x, %s706 ret i8 %d707}708 709define i8 @udiv_shl_nuw_use(i8 %x, i8 %y, i8 %z) {710; CHECK-LABEL: @udiv_shl_nuw_use(711; CHECK-NEXT: [[S:%.*]] = shl nuw i8 [[Y:%.*]], [[Z:%.*]]712; CHECK-NEXT: call void @use(i8 [[S]])713; CHECK-NEXT: [[D:%.*]] = udiv i8 [[X:%.*]], [[S]]714; CHECK-NEXT: ret i8 [[D]]715;716 %s = shl nuw i8 %y, %z717 call void @use(i8 %s)718 %d = udiv i8 %x, %s719 ret i8 %d720}721 722; ((X * Y) >> Z) / X --> Y >> Z723 724define i8 @udiv_lshr_mul_nuw(i8 %x, i8 %y, i8 %z) {725; CHECK-LABEL: @udiv_lshr_mul_nuw(726; CHECK-NEXT: [[DIV:%.*]] = lshr i8 [[Y:%.*]], [[Z:%.*]]727; CHECK-NEXT: ret i8 [[DIV]]728;729 %m = mul nuw i8 %x, %y730 %s = lshr i8 %m, %z731 %div = udiv i8 %s, %x732 ret i8 %div733}734 735; ((Y * X) >> Z) / X --> Y >> Z736 737define <2 x i4> @udiv_lshr_mul_nuw_exact_commute1(<2 x i4> %x, <2 x i4> %y, <2 x i4> %z) {738; CHECK-LABEL: @udiv_lshr_mul_nuw_exact_commute1(739; CHECK-NEXT: [[DIV:%.*]] = lshr exact <2 x i4> [[Y:%.*]], [[Z:%.*]]740; CHECK-NEXT: ret <2 x i4> [[DIV]]741;742 %m = mul nuw <2 x i4> %y, %x743 %s = lshr exact <2 x i4> %m, %z744 %div = udiv exact <2 x i4> %s, %x745 ret <2 x i4> %div746}747 748; negative test - mul is shifted amount, not shifted value749 750define i8 @udiv_lshr_mul_nuw_commute2(i8 %x, i8 %y, i8 %z) {751; CHECK-LABEL: @udiv_lshr_mul_nuw_commute2(752; CHECK-NEXT: [[M:%.*]] = mul nuw i8 [[Y:%.*]], [[X:%.*]]753; CHECK-NEXT: [[S:%.*]] = lshr i8 [[Z:%.*]], [[M]]754; CHECK-NEXT: [[DIV:%.*]] = udiv i8 [[S]], [[X]]755; CHECK-NEXT: ret i8 [[DIV]]756;757 %m = mul nuw i8 %y, %x758 %s = lshr i8 %z, %m759 %div = udiv i8 %s, %x760 ret i8 %div761}762 763; extra uses are ok764 765define i8 @udiv_lshr_mul_nuw_use1(i8 %x, i8 %y, i8 %z) {766; CHECK-LABEL: @udiv_lshr_mul_nuw_use1(767; CHECK-NEXT: [[M:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]768; CHECK-NEXT: call void @use(i8 [[M]])769; CHECK-NEXT: [[DIV:%.*]] = lshr i8 [[Y]], [[Z:%.*]]770; CHECK-NEXT: ret i8 [[DIV]]771;772 %m = mul nuw i8 %x, %y773 call void @use(i8 %m)774 %s = lshr i8 %m, %z775 %div = udiv i8 %s, %x776 ret i8 %div777}778 779; extra uses are ok780 781define i8 @udiv_lshr_mul_nuw_use2(i8 %x, i8 %y, i8 %z) {782; CHECK-LABEL: @udiv_lshr_mul_nuw_use2(783; CHECK-NEXT: [[M:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]784; CHECK-NEXT: [[S:%.*]] = lshr i8 [[M]], [[Z:%.*]]785; CHECK-NEXT: call void @use(i8 [[S]])786; CHECK-NEXT: [[DIV:%.*]] = lshr i8 [[Y]], [[Z]]787; CHECK-NEXT: ret i8 [[DIV]]788;789 %m = mul nuw i8 %x, %y790 %s = lshr i8 %m, %z791 call void @use(i8 %s)792 %div = udiv i8 %s, %x793 ret i8 %div794}795 796; extra uses are ok797 798define i8 @udiv_lshr_mul_nuw_use3(i8 %x, i8 %y, i8 %z) {799; CHECK-LABEL: @udiv_lshr_mul_nuw_use3(800; CHECK-NEXT: [[M:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]801; CHECK-NEXT: call void @use(i8 [[M]])802; CHECK-NEXT: [[S:%.*]] = lshr i8 [[M]], [[Z:%.*]]803; CHECK-NEXT: call void @use(i8 [[S]])804; CHECK-NEXT: [[DIV:%.*]] = lshr i8 [[Y]], [[Z]]805; CHECK-NEXT: ret i8 [[DIV]]806;807 %m = mul nuw i8 %x, %y808 call void @use(i8 %m)809 %s = lshr i8 %m, %z810 call void @use(i8 %s)811 %div = udiv i8 %s, %x812 ret i8 %div813}814 815; negative test - must have nuw816 817define i8 @udiv_lshr_mul_nsw(i8 %x, i8 %y, i8 %z) {818; CHECK-LABEL: @udiv_lshr_mul_nsw(819; CHECK-NEXT: [[M:%.*]] = mul nsw i8 [[X:%.*]], [[Y:%.*]]820; CHECK-NEXT: [[S:%.*]] = lshr i8 [[M]], [[Z:%.*]]821; CHECK-NEXT: [[DIV:%.*]] = udiv i8 [[S]], [[X]]822; CHECK-NEXT: ret i8 [[DIV]]823;824 %m = mul nsw i8 %x, %y825 %s = lshr i8 %m, %z826 %div = udiv i8 %s, %x827 ret i8 %div828}829 830; negative test - doesn't fold with signed div831 832define i8 @sdiv_lshr_mul_nsw(i8 %x, i8 %y, i8 %z) {833; CHECK-LABEL: @sdiv_lshr_mul_nsw(834; CHECK-NEXT: [[M:%.*]] = mul nsw i8 [[X:%.*]], [[Y:%.*]]835; CHECK-NEXT: [[S:%.*]] = lshr i8 [[M]], [[Z:%.*]]836; CHECK-NEXT: [[DIV:%.*]] = sdiv i8 [[S]], [[X]]837; CHECK-NEXT: ret i8 [[DIV]]838;839 %m = mul nsw i8 %x, %y840 %s = lshr i8 %m, %z841 %div = sdiv i8 %s, %x842 ret i8 %div843}844 845; (X << Z) / (Y << Z) --> X / Y846 847define i8 @sdiv_shl_shl_nsw2_nuw(i8 %x, i8 %y, i8 %z) {848; CHECK-LABEL: @sdiv_shl_shl_nsw2_nuw(849; CHECK-NEXT: [[D:%.*]] = sdiv i8 [[X:%.*]], [[Y:%.*]]850; CHECK-NEXT: ret i8 [[D]]851;852 %xz = shl nsw i8 %x, %z853 %yz = shl nsw nuw i8 %y, %z854 %d = sdiv i8 %xz, %yz855 ret i8 %d856}857 858; extra uses are ok and 'exact' propagates859 860define i8 @sdiv_shl_shl_nsw2_nuw_exact_use(i8 %x, i8 %y, i8 %z) {861; CHECK-LABEL: @sdiv_shl_shl_nsw2_nuw_exact_use(862; CHECK-NEXT: [[XZ:%.*]] = shl nsw i8 [[X:%.*]], [[Z:%.*]]863; CHECK-NEXT: call void @use(i8 [[XZ]])864; CHECK-NEXT: [[D:%.*]] = sdiv exact i8 [[X]], [[Y:%.*]]865; CHECK-NEXT: ret i8 [[D]]866;867 %xz = shl nsw i8 %x, %z868 call void @use(i8 %xz)869 %yz = shl nsw nuw i8 %y, %z870 %d = sdiv exact i8 %xz, %yz871 ret i8 %d872}873 874; negative test - wrong wrap875 876define i8 @sdiv_shl_shl_nsw_nuw2(i8 %x, i8 %y, i8 %z) {877; CHECK-LABEL: @sdiv_shl_shl_nsw_nuw2(878; CHECK-NEXT: [[XZ:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]879; CHECK-NEXT: [[YZ:%.*]] = shl nuw nsw i8 [[Y:%.*]], [[Z]]880; CHECK-NEXT: [[D:%.*]] = sdiv i8 [[XZ]], [[YZ]]881; CHECK-NEXT: ret i8 [[D]]882;883 %xz = shl nuw i8 %x, %z884 %yz = shl nsw nuw i8 %y, %z885 %d = sdiv i8 %xz, %yz886 ret i8 %d887}888 889; negative test - wrong wrap890 891define i8 @sdiv_shl_shl_nsw_nuw(i8 %x, i8 %y, i8 %z) {892; CHECK-LABEL: @sdiv_shl_shl_nsw_nuw(893; CHECK-NEXT: [[XZ:%.*]] = shl nsw i8 [[X:%.*]], [[Z:%.*]]894; CHECK-NEXT: [[YZ:%.*]] = shl nuw i8 [[Y:%.*]], [[Z]]895; CHECK-NEXT: [[D:%.*]] = sdiv i8 [[XZ]], [[YZ]]896; CHECK-NEXT: ret i8 [[D]]897;898 %xz = shl nsw i8 %x, %z899 %yz = shl nuw i8 %y, %z900 %d = sdiv i8 %xz, %yz901 ret i8 %d902}903 904; negative test - wrong wrap905 906define i8 @sdiv_shl_shl_nuw_nsw2(i8 %x, i8 %y, i8 %z) {907; CHECK-LABEL: @sdiv_shl_shl_nuw_nsw2(908; CHECK-NEXT: [[XZ:%.*]] = shl nuw nsw i8 [[X:%.*]], [[Z:%.*]]909; CHECK-NEXT: [[YZ:%.*]] = shl nsw i8 [[Y:%.*]], [[Z]]910; CHECK-NEXT: [[D:%.*]] = sdiv i8 [[XZ]], [[YZ]]911; CHECK-NEXT: ret i8 [[D]]912;913 %xz = shl nuw nsw i8 %x, %z914 %yz = shl nsw i8 %y, %z915 %d = sdiv i8 %xz, %yz916 ret i8 %d917}918 919; (X << Z) / (Y << Z) --> X / Y920 921define <2 x i8> @udiv_shl_shl_nuw2(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {922; CHECK-LABEL: @udiv_shl_shl_nuw2(923; CHECK-NEXT: [[D:%.*]] = udiv <2 x i8> [[X:%.*]], [[Y:%.*]]924; CHECK-NEXT: ret <2 x i8> [[D]]925;926 %xz = shl nuw <2 x i8> %x, %z927 %yz = shl nuw <2 x i8> %y, %z928 %d = udiv <2 x i8> %xz, %yz929 ret <2 x i8> %d930}931 932; extra uses are ok and 'exact' propagates933 934define i8 @udiv_shl_shl_nuw2_exact_use2(i8 %x, i8 %y, i8 %z) {935; CHECK-LABEL: @udiv_shl_shl_nuw2_exact_use2(936; CHECK-NEXT: [[XZ:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]937; CHECK-NEXT: call void @use(i8 [[XZ]])938; CHECK-NEXT: [[YZ:%.*]] = shl nuw i8 [[Y:%.*]], [[Z]]939; CHECK-NEXT: call void @use(i8 [[YZ]])940; CHECK-NEXT: [[D:%.*]] = udiv exact i8 [[X]], [[Y]]941; CHECK-NEXT: ret i8 [[D]]942;943 %xz = shl nuw i8 %x, %z944 call void @use(i8 %xz)945 %yz = shl nuw i8 %y, %z946 call void @use(i8 %yz)947 %d = udiv exact i8 %xz, %yz948 ret i8 %d949}950 951; negative test - wrong wrap952 953define i8 @udiv_shl_shl_nuw_nsw(i8 %x, i8 %y, i8 %z) {954; CHECK-LABEL: @udiv_shl_shl_nuw_nsw(955; CHECK-NEXT: [[XZ:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]956; CHECK-NEXT: [[YZ:%.*]] = shl nsw i8 [[Y:%.*]], [[Z]]957; CHECK-NEXT: [[D:%.*]] = udiv i8 [[XZ]], [[YZ]]958; CHECK-NEXT: ret i8 [[D]]959;960 %xz = shl nuw i8 %x, %z961 %yz = shl nsw i8 %y, %z962 %d = udiv i8 %xz, %yz963 ret i8 %d964}965 966; negative test - wrong wrap967 968define i8 @udiv_shl_shl_nsw_nuw(i8 %x, i8 %y, i8 %z) {969; CHECK-LABEL: @udiv_shl_shl_nsw_nuw(970; CHECK-NEXT: [[XZ:%.*]] = shl nsw i8 [[X:%.*]], [[Z:%.*]]971; CHECK-NEXT: [[YZ:%.*]] = shl nuw i8 [[Y:%.*]], [[Z]]972; CHECK-NEXT: [[D:%.*]] = udiv i8 [[XZ]], [[YZ]]973; CHECK-NEXT: ret i8 [[D]]974;975 %xz = shl nsw i8 %x, %z976 %yz = shl nuw i8 %y, %z977 %d = udiv i8 %xz, %yz978 ret i8 %d979}980 981define i8 @udiv_shl_shl_nuw_nsw2(i8 %x, i8 %y, i8 %z) {982; CHECK-LABEL: @udiv_shl_shl_nuw_nsw2(983; CHECK-NEXT: [[D:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]984; CHECK-NEXT: ret i8 [[D]]985;986 %xz = shl nuw nsw i8 %x, %z987 %yz = shl nsw i8 %y, %z988 %d = udiv i8 %xz, %yz989 ret i8 %d990}991 992; TODO: X / (Y << Z) --> (X >> Z) / Y993; https://alive2.llvm.org/ce/z/FjoN_A994 995define i8 @udiv_shl_nuw_divisor(i8 %x, i8 %y, i8 %z) {996; CHECK-LABEL: @udiv_shl_nuw_divisor(997; CHECK-NEXT: [[S:%.*]] = shl nuw i8 [[Y:%.*]], [[Z:%.*]]998; CHECK-NEXT: [[D:%.*]] = udiv i8 [[X:%.*]], [[S]]999; CHECK-NEXT: ret i8 [[D]]1000;1001 %s = shl nuw i8 %y, %z1002 %d = udiv i8 %x, %s1003 ret i8 %d1004}1005 1006define i8 @udiv_fail_shl_overflow(i8 %x, i8 %y) {1007; CHECK-LABEL: @udiv_fail_shl_overflow(1008; CHECK-NEXT: [[SHL:%.*]] = shl i8 2, [[Y:%.*]]1009; CHECK-NEXT: [[MIN:%.*]] = call i8 @llvm.umax.i8(i8 [[SHL]], i8 1)1010; CHECK-NEXT: [[TMP1:%.*]] = call range(i8 0, 9) i8 @llvm.cttz.i8(i8 [[MIN]], i1 true)1011; CHECK-NEXT: [[MUL:%.*]] = lshr i8 [[X:%.*]], [[TMP1]]1012; CHECK-NEXT: ret i8 [[MUL]]1013;1014 %shl = shl i8 2, %y1015 %min = call i8 @llvm.umax.i8(i8 %shl, i8 1)1016 %mul = udiv i8 %x, %min1017 ret i8 %mul1018}1019 1020define i8 @udiv_shl_no_overflow(i8 %x, i8 %y) {1021; CHECK-LABEL: @udiv_shl_no_overflow(1022; CHECK-NEXT: [[TMP1:%.*]] = add i8 [[Y:%.*]], 11023; CHECK-NEXT: [[MUL1:%.*]] = lshr i8 [[X:%.*]], [[TMP1]]1024; CHECK-NEXT: ret i8 [[MUL1]]1025;1026 %shl = shl nuw i8 2, %y1027 %min = call i8 @llvm.umax.i8(i8 %shl, i8 1)1028 %mul = udiv i8 %x, %min1029 ret i8 %mul1030}1031 1032; (X<<Y) / (X<<Z) -> 1 << Y >> Z1033 1034define i32 @sdiv_shl_pair_const(i32 %a) {1035; CHECK-LABEL: @sdiv_shl_pair_const(1036; CHECK-NEXT: entry:1037; CHECK-NEXT: ret i32 21038;1039entry:1040 %lhs = shl nsw i32 %a, 21041 %rhs = shl nsw i32 %a, 11042 %div = sdiv i32 %lhs, %rhs1043 ret i32 %div1044}1045 1046define i32 @udiv_shl_pair_const(i32 %a) {1047; CHECK-LABEL: @udiv_shl_pair_const(1048; CHECK-NEXT: entry:1049; CHECK-NEXT: ret i32 21050;1051entry:1052 %lhs = shl nuw i32 %a, 21053 %rhs = shl nuw i32 %a, 11054 %div = udiv i32 %lhs, %rhs1055 ret i32 %div1056}1057 1058define i32 @sdiv_shl_pair1(i32 %a, i32 %x, i32 %y) {1059; CHECK-LABEL: @sdiv_shl_pair1(1060; CHECK-NEXT: entry:1061; CHECK-NEXT: [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X:%.*]]1062; CHECK-NEXT: [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]1063; CHECK-NEXT: ret i32 [[DIV]]1064;1065entry:1066 %lhs = shl nsw i32 %a, %x1067 %rhs = shl nuw nsw i32 %a, %y1068 %div = sdiv i32 %lhs, %rhs1069 ret i32 %div1070}1071 1072define i32 @sdiv_shl_pair2(i32 %a, i32 %x, i32 %y) {1073; CHECK-LABEL: @sdiv_shl_pair2(1074; CHECK-NEXT: entry:1075; CHECK-NEXT: [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X:%.*]]1076; CHECK-NEXT: [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]1077; CHECK-NEXT: ret i32 [[DIV]]1078;1079entry:1080 %lhs = shl nuw nsw i32 %a, %x1081 %rhs = shl nsw i32 %a, %y1082 %div = sdiv i32 %lhs, %rhs1083 ret i32 %div1084}1085 1086define i32 @sdiv_shl_pair3(i32 %a, i32 %x, i32 %y) {1087; CHECK-LABEL: @sdiv_shl_pair3(1088; CHECK-NEXT: entry:1089; CHECK-NEXT: [[SHL_DIVIDEND:%.*]] = shl nuw i32 1, [[X:%.*]]1090; CHECK-NEXT: [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]1091; CHECK-NEXT: ret i32 [[DIV]]1092;1093entry:1094 %lhs = shl nsw i32 %a, %x1095 %rhs = shl nsw i32 %a, %y1096 %div = sdiv i32 %lhs, %rhs1097 ret i32 %div1098}1099 1100define i32 @sdiv_shl_no_pair_fail(i32 %a, i32 %b, i32 %x, i32 %y) {1101; CHECK-LABEL: @sdiv_shl_no_pair_fail(1102; CHECK-NEXT: entry:1103; CHECK-NEXT: [[LHS:%.*]] = shl nuw nsw i32 [[A:%.*]], [[X:%.*]]1104; CHECK-NEXT: [[RHS:%.*]] = shl nuw i32 [[B:%.*]], [[Y:%.*]]1105; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[LHS]], [[RHS]]1106; CHECK-NEXT: ret i32 [[DIV]]1107;1108entry:1109 %lhs = shl nuw nsw i32 %a, %x1110 %rhs = shl nuw i32 %b, %y1111 %div = sdiv i32 %lhs, %rhs1112 ret i32 %div1113}1114 1115define i32 @udiv_shl_pair1(i32 %a, i32 %x, i32 %y) {1116; CHECK-LABEL: @udiv_shl_pair1(1117; CHECK-NEXT: entry:1118; CHECK-NEXT: [[SHL_DIVIDEND:%.*]] = shl nuw i32 1, [[X:%.*]]1119; CHECK-NEXT: [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]1120; CHECK-NEXT: ret i32 [[DIV]]1121;1122entry:1123 %lhs = shl nuw i32 %a, %x1124 %rhs = shl nuw i32 %a, %y1125 %div = udiv i32 %lhs, %rhs1126 ret i32 %div1127}1128 1129define i32 @udiv_shl_pair2(i32 %a, i32 %x, i32 %y) {1130; CHECK-LABEL: @udiv_shl_pair2(1131; CHECK-NEXT: entry:1132; CHECK-NEXT: [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X:%.*]]1133; CHECK-NEXT: [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]1134; CHECK-NEXT: ret i32 [[DIV]]1135;1136entry:1137 %lhs = shl nuw nsw i32 %a, %x1138 %rhs = shl nuw i32 %a, %y1139 %div = udiv i32 %lhs, %rhs1140 ret i32 %div1141}1142 1143define i32 @udiv_shl_pair3(i32 %a, i32 %x, i32 %y) {1144; CHECK-LABEL: @udiv_shl_pair3(1145; CHECK-NEXT: entry:1146; CHECK-NEXT: [[SHL_DIVIDEND:%.*]] = shl nuw i32 1, [[X:%.*]]1147; CHECK-NEXT: [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]1148; CHECK-NEXT: ret i32 [[DIV]]1149;1150entry:1151 %lhs = shl nuw i32 %a, %x1152 %rhs = shl nuw nsw i32 %a, %y1153 %div = udiv i32 %lhs, %rhs1154 ret i32 %div1155}1156 1157define i32 @sdiv_shl_pair_overflow_fail1(i32 %a, i32 %x, i32 %y) {1158; CHECK-LABEL: @sdiv_shl_pair_overflow_fail1(1159; CHECK-NEXT: entry:1160; CHECK-NEXT: [[LHS:%.*]] = shl i32 [[A:%.*]], [[X:%.*]]1161; CHECK-NEXT: [[RHS:%.*]] = shl nsw i32 [[A]], [[Y:%.*]]1162; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[LHS]], [[RHS]]1163; CHECK-NEXT: ret i32 [[DIV]]1164;1165entry:1166 %lhs = shl i32 %a, %x1167 %rhs = shl nsw i32 %a, %y1168 %div = sdiv i32 %lhs, %rhs1169 ret i32 %div1170}1171 1172define i32 @sdiv_shl_pair_overflow_fail2(i32 %a, i32 %x, i32 %y) {1173; CHECK-LABEL: @sdiv_shl_pair_overflow_fail2(1174; CHECK-NEXT: entry:1175; CHECK-NEXT: [[LHS:%.*]] = shl nsw i32 [[A:%.*]], [[X:%.*]]1176; CHECK-NEXT: [[RHS:%.*]] = shl nuw i32 [[A]], [[Y:%.*]]1177; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[LHS]], [[RHS]]1178; CHECK-NEXT: ret i32 [[DIV]]1179;1180entry:1181 %lhs = shl nsw i32 %a, %x1182 %rhs = shl nuw i32 %a, %y1183 %div = sdiv i32 %lhs, %rhs1184 ret i32 %div1185}1186 1187define i32 @udiv_shl_pair_overflow_fail1(i32 %a, i32 %x, i32 %y) {1188; CHECK-LABEL: @udiv_shl_pair_overflow_fail1(1189; CHECK-NEXT: entry:1190; CHECK-NEXT: [[LHS:%.*]] = shl nsw i32 [[A:%.*]], [[X:%.*]]1191; CHECK-NEXT: [[RHS:%.*]] = shl nuw i32 [[A]], [[Y:%.*]]1192; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[LHS]], [[RHS]]1193; CHECK-NEXT: ret i32 [[DIV]]1194;1195entry:1196 %lhs = shl nsw i32 %a, %x1197 %rhs = shl nuw i32 %a, %y1198 %div = udiv i32 %lhs, %rhs1199 ret i32 %div1200}1201 1202define i32 @udiv_shl_pair_overflow_fail2(i32 %a, i32 %x, i32 %y) {1203; CHECK-LABEL: @udiv_shl_pair_overflow_fail2(1204; CHECK-NEXT: entry:1205; CHECK-NEXT: [[LHS:%.*]] = shl nsw i32 [[A:%.*]], [[X:%.*]]1206; CHECK-NEXT: [[RHS:%.*]] = shl i32 [[A]], [[Y:%.*]]1207; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[LHS]], [[RHS]]1208; CHECK-NEXT: ret i32 [[DIV]]1209;1210entry:1211 %lhs = shl nsw i32 %a, %x1212 %rhs = shl i32 %a, %y1213 %div = udiv i32 %lhs, %rhs1214 ret i32 %div1215}1216 1217define i32 @udiv_shl_pair_overflow_fail3(i32 %a, i32 %x, i32 %y) {1218; CHECK-LABEL: @udiv_shl_pair_overflow_fail3(1219; CHECK-NEXT: entry:1220; CHECK-NEXT: [[LHS:%.*]] = shl nuw nsw i32 [[A:%.*]], [[X:%.*]]1221; CHECK-NEXT: [[RHS:%.*]] = shl i32 [[A]], [[Y:%.*]]1222; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[LHS]], [[RHS]]1223; CHECK-NEXT: ret i32 [[DIV]]1224;1225entry:1226 %lhs = shl nuw nsw i32 %a, %x1227 %rhs = shl i32 %a, %y1228 %div = udiv i32 %lhs, %rhs1229 ret i32 %div1230}1231 1232define i32 @sdiv_shl_pair_multiuse1(i32 %a, i32 %x, i32 %y) {1233; CHECK-LABEL: @sdiv_shl_pair_multiuse1(1234; CHECK-NEXT: entry:1235; CHECK-NEXT: [[LHS:%.*]] = shl nuw nsw i32 [[A:%.*]], [[X:%.*]]1236; CHECK-NEXT: call void @use32(i32 [[LHS]])1237; CHECK-NEXT: [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X]]1238; CHECK-NEXT: [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]1239; CHECK-NEXT: ret i32 [[DIV]]1240;1241entry:1242 %lhs = shl nuw nsw i32 %a, %x1243 call void @use32(i32 %lhs)1244 %rhs = shl nsw i32 %a, %y1245 %div = sdiv i32 %lhs, %rhs1246 ret i32 %div1247}1248 1249define i32 @sdiv_shl_pair_multiuse2(i32 %a, i32 %x, i32 %y) {1250; CHECK-LABEL: @sdiv_shl_pair_multiuse2(1251; CHECK-NEXT: entry:1252; CHECK-NEXT: [[RHS:%.*]] = shl nsw i32 [[A:%.*]], [[Y:%.*]]1253; CHECK-NEXT: call void @use32(i32 [[RHS]])1254; CHECK-NEXT: [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X:%.*]]1255; CHECK-NEXT: [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y]]1256; CHECK-NEXT: ret i32 [[DIV]]1257;1258entry:1259 %lhs = shl nuw nsw i32 %a, %x1260 %rhs = shl nsw i32 %a, %y1261 call void @use32(i32 %rhs)1262 %div = sdiv i32 %lhs, %rhs1263 ret i32 %div1264}1265 1266define i32 @sdiv_shl_pair_multiuse3(i32 %a, i32 %x, i32 %y) {1267; CHECK-LABEL: @sdiv_shl_pair_multiuse3(1268; CHECK-NEXT: entry:1269; CHECK-NEXT: [[LHS:%.*]] = shl nuw nsw i32 [[A:%.*]], [[X:%.*]]1270; CHECK-NEXT: [[RHS:%.*]] = shl nsw i32 [[A]], [[Y:%.*]]1271; CHECK-NEXT: call void @use32(i32 [[LHS]])1272; CHECK-NEXT: call void @use32(i32 [[RHS]])1273; CHECK-NEXT: [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X]]1274; CHECK-NEXT: [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y]]1275; CHECK-NEXT: ret i32 [[DIV]]1276;1277entry:1278 %lhs = shl nuw nsw i32 %a, %x1279 %rhs = shl nsw i32 %a, %y1280 call void @use32(i32 %lhs)1281 call void @use32(i32 %rhs)1282 %div = sdiv i32 %lhs, %rhs1283 ret i32 %div1284}1285 1286@a = external global i321287define i32 @pr69291() {1288; CHECK-LABEL: @pr69291(1289; CHECK-NEXT: entry:1290; CHECK-NEXT: ret i32 11291;1292entry:1293 %conv = load i32, ptr @a, align 11294 %add = shl nuw nsw i32 %conv, 11295 %add2 = shl nuw nsw i32 %conv, 11296 %div = sdiv i32 %add, %add21297 ret i32 %div1298}1299 1300define i8 @udiv_if_power_of_two(i8 %x, i8 %y) {1301; CHECK-LABEL: @udiv_if_power_of_two(1302; CHECK-NEXT: start:1303; CHECK-NEXT: [[TMP0:%.*]] = tail call range(i8 0, 9) i8 @llvm.ctpop.i8(i8 [[Y:%.*]])1304; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i8 [[TMP0]], 11305; CHECK-NEXT: br i1 [[TMP1]], label [[BB1:%.*]], label [[BB3:%.*]]1306; CHECK: bb1:1307; CHECK-NEXT: [[TMP2:%.*]] = call range(i8 0, 9) i8 @llvm.cttz.i8(i8 [[Y]], i1 true)1308; CHECK-NEXT: [[TMP3:%.*]] = lshr i8 [[X:%.*]], [[TMP2]]1309; CHECK-NEXT: br label [[BB3]]1310; CHECK: bb3:1311; CHECK-NEXT: [[_0_SROA_0_0:%.*]] = phi i8 [ [[TMP3]], [[BB1]] ], [ 0, [[START:%.*]] ]1312; CHECK-NEXT: ret i8 [[_0_SROA_0_0]]1313;1314start:1315 %ctpop = tail call i8 @llvm.ctpop.i8(i8 %y)1316 %cmp = icmp eq i8 %ctpop, 11317 br i1 %cmp, label %bb1, label %bb31318 1319bb1:1320 %div = udiv i8 %x, %y1321 br label %bb31322 1323bb3:1324 %result = phi i8 [ %div, %bb1 ], [ 0, %start ]1325 ret i8 %result1326}1327 1328define i8 @udiv_exact_assume_power_of_two(i8 %x, i8 %y) {1329; CHECK-LABEL: @udiv_exact_assume_power_of_two(1330; CHECK-NEXT: start:1331; CHECK-NEXT: [[TMP0:%.*]] = tail call range(i8 1, 9) i8 @llvm.ctpop.i8(i8 [[Y:%.*]])1332; CHECK-NEXT: [[COND:%.*]] = icmp eq i8 [[TMP0]], 11333; CHECK-NEXT: tail call void @llvm.assume(i1 [[COND]])1334; CHECK-NEXT: [[TMP1:%.*]] = call range(i8 0, 9) i8 @llvm.cttz.i8(i8 [[Y]], i1 true)1335; CHECK-NEXT: [[_0:%.*]] = lshr exact i8 [[X:%.*]], [[TMP1]]1336; CHECK-NEXT: ret i8 [[_0]]1337;1338start:1339 %ctpop = tail call i8 @llvm.ctpop.i8(i8 %y)1340 %cond = icmp eq i8 %ctpop, 11341 tail call void @llvm.assume(i1 %cond)1342 %div = udiv exact i8 %x, %y1343 ret i8 %div1344}1345 1346define i7 @udiv_assume_power_of_two_illegal_type(i7 %x, i7 %y) {1347; CHECK-LABEL: @udiv_assume_power_of_two_illegal_type(1348; CHECK-NEXT: start:1349; CHECK-NEXT: [[TMP0:%.*]] = tail call range(i7 1, 8) i7 @llvm.ctpop.i7(i7 [[Y:%.*]])1350; CHECK-NEXT: [[COND:%.*]] = icmp eq i7 [[TMP0]], 11351; CHECK-NEXT: tail call void @llvm.assume(i1 [[COND]])1352; CHECK-NEXT: [[TMP1:%.*]] = call range(i7 0, 8) i7 @llvm.cttz.i7(i7 [[Y]], i1 true)1353; CHECK-NEXT: [[_0:%.*]] = lshr i7 [[X:%.*]], [[TMP1]]1354; CHECK-NEXT: ret i7 [[_0]]1355;1356start:1357 %ctpop = tail call i7 @llvm.ctpop.i7(i7 %y)1358 %cond = icmp eq i7 %ctpop, 11359 tail call void @llvm.assume(i1 %cond)1360 %div = udiv i7 %x, %y1361 ret i7 %div1362}1363 1364define i8 @udiv_assume_power_of_two_multiuse(i8 %x, i8 %y) {1365; CHECK-LABEL: @udiv_assume_power_of_two_multiuse(1366; CHECK-NEXT: start:1367; CHECK-NEXT: [[TMP0:%.*]] = tail call range(i8 1, 9) i8 @llvm.ctpop.i8(i8 [[Y:%.*]])1368; CHECK-NEXT: [[COND:%.*]] = icmp eq i8 [[TMP0]], 11369; CHECK-NEXT: tail call void @llvm.assume(i1 [[COND]])1370; CHECK-NEXT: [[TMP1:%.*]] = call range(i8 0, 9) i8 @llvm.cttz.i8(i8 [[Y]], i1 true)1371; CHECK-NEXT: [[_0:%.*]] = lshr i8 [[X:%.*]], [[TMP1]]1372; CHECK-NEXT: call void @use(i8 [[_0]])1373; CHECK-NEXT: ret i8 [[_0]]1374;1375start:1376 %ctpop = tail call i8 @llvm.ctpop.i8(i8 %y)1377 %cond = icmp eq i8 %ctpop, 11378 tail call void @llvm.assume(i1 %cond)1379 %div = udiv i8 %x, %y1380 call void @use(i8 %div)1381 ret i8 %div1382}1383 1384define i8 @udiv_power_of_two_negative(i8 %x, i8 %y, i8 %z) {1385; CHECK-LABEL: @udiv_power_of_two_negative(1386; CHECK-NEXT: start:1387; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i8 0, 9) i8 @llvm.ctpop.i8(i8 [[Z:%.*]])1388; CHECK-NEXT: [[COND:%.*]] = icmp eq i8 [[CTPOP]], 11389; CHECK-NEXT: tail call void @llvm.assume(i1 [[COND]])1390; CHECK-NEXT: [[_0:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]1391; CHECK-NEXT: ret i8 [[_0]]1392;1393start:1394 %ctpop = tail call i8 @llvm.ctpop.i8(i8 %z)1395 %cond = icmp eq i8 %ctpop, 11396 tail call void @llvm.assume(i1 %cond)1397 %div = udiv i8 %x, %y1398 ret i8 %div1399}1400