756 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 52; RUN: opt < %s -passes=aggressive-instcombine,instcombine -S | FileCheck %s3 4; Carry variant of mul-high. https://alive2.llvm.org/ce/z/G2bD6o5define i32 @mul_carry(i32 %x, i32 %y) {6; CHECK-LABEL: define i32 @mul_carry(7; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {8; CHECK-NEXT: [[ENTRY:.*:]]9; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[X]] to i6410; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[Y]] to i6411; CHECK-NEXT: [[TMP2:%.*]] = mul nuw i64 [[TMP0]], [[TMP1]]12; CHECK-NEXT: [[TMP3:%.*]] = lshr i64 [[TMP2]], 3213; CHECK-NEXT: [[ADD11:%.*]] = trunc nuw i64 [[TMP3]] to i3214; CHECK-NEXT: ret i32 [[ADD11]]15;16entry:17 %shr = lshr i32 %x, 1618 %and = and i32 %x, 6553519 %shr1 = lshr i32 %y, 1620 %and2 = and i32 %y, 6553521 %mul = mul nuw i32 %shr, %and222 %mul3 = mul nuw i32 %and, %shr123 %add = add i32 %mul, %mul324 %mul4 = mul nuw i32 %and, %and225 %shr5 = lshr i32 %mul4, 1626 %add6 = add i32 %add, %shr527 %cmp = icmp ult i32 %add6, %mul28 %cond = select i1 %cmp, i32 65536, i32 029 %mul8 = mul nuw i32 %shr, %shr130 %add9 = add nuw i32 %mul8, %cond31 %shr10 = lshr i32 %add6, 1632 %add11 = add i32 %add9, %shr1033 ret i32 %add1134}35 36; Carry variant of mul-high. https://alive2.llvm.org/ce/z/G2bD6o37define i128 @mul_carry_i128(i128 %x, i128 %y) {38; CHECK-LABEL: define i128 @mul_carry_i128(39; CHECK-SAME: i128 [[X:%.*]], i128 [[Y:%.*]]) {40; CHECK-NEXT: [[ENTRY:.*:]]41; CHECK-NEXT: [[TMP0:%.*]] = zext i128 [[X]] to i25642; CHECK-NEXT: [[TMP1:%.*]] = zext i128 [[Y]] to i25643; CHECK-NEXT: [[TMP2:%.*]] = mul nuw i256 [[TMP0]], [[TMP1]]44; CHECK-NEXT: [[TMP3:%.*]] = lshr i256 [[TMP2]], 12845; CHECK-NEXT: [[ADD11:%.*]] = trunc nuw i256 [[TMP3]] to i12846; CHECK-NEXT: ret i128 [[ADD11]]47;48entry:49 %shr = lshr i128 %x, 6450 %and = and i128 %x, u0xffffffffffffffff51 %shr1 = lshr i128 %y, 6452 %and2 = and i128 %y, u0xffffffffffffffff53 %mul = mul nuw i128 %shr, %and254 %mul3 = mul nuw i128 %and, %shr155 %add = add i128 %mul, %mul356 %mul4 = mul nuw i128 %and, %and257 %shr5 = lshr i128 %mul4, 6458 %add6 = add i128 %add, %shr559 %cmp = icmp ult i128 %add6, %mul60 %cond = select i1 %cmp, i128 u0x10000000000000000, i128 061 %mul8 = mul nuw i128 %shr, %shr162 %add9 = add nuw i128 %mul8, %cond63 %shr10 = lshr i128 %add6, 6464 %add11 = add i128 %add9, %shr1065 ret i128 %add1166}67 68; Carry variant of mul-high. https://alive2.llvm.org/ce/z/G2bD6o69define <4 x i32> @mul_carry_v4i32(<4 x i32> %x, <4 x i32> %y) {70; CHECK-LABEL: define <4 x i32> @mul_carry_v4i32(71; CHECK-SAME: <4 x i32> [[X:%.*]], <4 x i32> [[Y:%.*]]) {72; CHECK-NEXT: [[ENTRY:.*:]]73; CHECK-NEXT: [[TMP0:%.*]] = zext <4 x i32> [[X]] to <4 x i64>74; CHECK-NEXT: [[TMP1:%.*]] = zext <4 x i32> [[Y]] to <4 x i64>75; CHECK-NEXT: [[TMP2:%.*]] = mul nuw <4 x i64> [[TMP0]], [[TMP1]]76; CHECK-NEXT: [[TMP3:%.*]] = lshr <4 x i64> [[TMP2]], splat (i64 32)77; CHECK-NEXT: [[ADD11:%.*]] = trunc nuw <4 x i64> [[TMP3]] to <4 x i32>78; CHECK-NEXT: ret <4 x i32> [[ADD11]]79;80entry:81 %shr = lshr <4 x i32> %x, <i32 16, i32 16, i32 16, i32 16>82 %and = and <4 x i32> %x, <i32 65535, i32 65535, i32 65535, i32 65535>83 %shr1 = lshr <4 x i32> %y, <i32 16, i32 16, i32 16, i32 16>84 %and2 = and <4 x i32> %y, <i32 65535, i32 65535, i32 65535, i32 65535>85 %mul = mul nuw <4 x i32> %shr, %and286 %mul3 = mul nuw <4 x i32> %and, %shr187 %add = add <4 x i32> %mul, %mul388 %mul4 = mul nuw <4 x i32> %and, %and289 %shr5 = lshr <4 x i32> %mul4, <i32 16, i32 16, i32 16, i32 16>90 %add6 = add <4 x i32> %add, %shr591 %cmp = icmp ult <4 x i32> %add6, %mul92 %cond = select <4 x i1> %cmp, <4 x i32> <i32 65536, i32 65536, i32 65536, i32 65536>, <4 x i32> zeroinitializer93 %mul8 = mul nuw <4 x i32> %shr, %shr194 %add9 = add nuw <4 x i32> %mul8, %cond95 %shr10 = lshr <4 x i32> %add6, <i32 16, i32 16, i32 16, i32 16>96 %add11 = add <4 x i32> %add9, %shr1097 ret <4 x i32> %add1198}99 100; Check carry against xlyh, not xhyl101define i32 @mul_carry_xlyh(i32 %x, i32 %y) {102; CHECK-LABEL: define i32 @mul_carry_xlyh(103; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {104; CHECK-NEXT: [[ENTRY:.*:]]105; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[Y]] to i64106; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[X]] to i64107; CHECK-NEXT: [[TMP2:%.*]] = mul nuw i64 [[TMP0]], [[TMP1]]108; CHECK-NEXT: [[TMP3:%.*]] = lshr i64 [[TMP2]], 32109; CHECK-NEXT: [[ADD11:%.*]] = trunc nuw i64 [[TMP3]] to i32110; CHECK-NEXT: ret i32 [[ADD11]]111;112entry:113 %shr = lshr i32 %x, 16114 %and = and i32 %x, 65535115 %shr1 = lshr i32 %y, 16116 %and2 = and i32 %y, 65535117 %mul = mul nuw i32 %shr, %and2118 %mul3 = mul nuw i32 %and, %shr1119 %add = add i32 %mul, %mul3120 %mul4 = mul nuw i32 %and, %and2121 %shr5 = lshr i32 %mul4, 16122 %add6 = add i32 %add, %shr5123 %cmp = icmp ult i32 %add6, %mul3124 %cond = select i1 %cmp, i32 65536, i32 0125 %mul8 = mul nuw i32 %shr, %shr1126 %add9 = add nuw i32 %mul8, %cond127 %shr10 = lshr i32 %add6, 16128 %add11 = add i32 %add9, %shr10129 ret i32 %add11130}131 132define i32 @mul_carry_comm(i32 %x, i32 %y) {133; CHECK-LABEL: define i32 @mul_carry_comm(134; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {135; CHECK-NEXT: [[ENTRY:.*:]]136; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[X]] to i64137; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[Y]] to i64138; CHECK-NEXT: [[TMP2:%.*]] = mul nuw i64 [[TMP0]], [[TMP1]]139; CHECK-NEXT: [[TMP3:%.*]] = lshr i64 [[TMP2]], 32140; CHECK-NEXT: [[ADD11:%.*]] = trunc nuw i64 [[TMP3]] to i32141; CHECK-NEXT: ret i32 [[ADD11]]142;143entry:144 %shr = lshr i32 %x, 16145 %and = and i32 %x, 65535146 %shr1 = lshr i32 %y, 16147 %and2 = and i32 %y, 65535148 %mul = mul nuw i32 %and2, %shr149 %mul3 = mul nuw i32 %shr1, %and150 %add = add i32 %mul3, %mul151 %mul4 = mul nuw i32 %and, %and2152 %shr5 = lshr i32 %mul4, 16153 %add6 = add i32 %shr5, %add154 %cmp = icmp ult i32 %add6, %mul155 %cond = select i1 %cmp, i32 65536, i32 0156 %mul8 = mul nuw i32 %shr, %shr1157 %shr10 = lshr i32 %add6, 16158 %add9 = add nuw i32 %cond, %shr10159 %add11 = add i32 %add9, %mul8160 ret i32 %add11161}162 163 164; Negative tests165 166 167define i32 @mul_carry_notxlo(i32 %x, i32 %y) {168; CHECK-LABEL: define i32 @mul_carry_notxlo(169; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {170; CHECK-NEXT: [[ENTRY:.*:]]171; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16172; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 32767173; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 16174; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535175; CHECK-NEXT: [[MUL:%.*]] = mul nuw i32 [[SHR]], [[AND2]]176; CHECK-NEXT: [[MUL3:%.*]] = mul nuw nsw i32 [[AND]], [[SHR1]]177; CHECK-NEXT: [[ADD:%.*]] = add i32 [[MUL]], [[MUL3]]178; CHECK-NEXT: [[MUL4:%.*]] = mul nuw nsw i32 [[AND]], [[AND2]]179; CHECK-NEXT: [[SHR5:%.*]] = lshr i32 [[MUL4]], 16180; CHECK-NEXT: [[ADD6:%.*]] = add i32 [[ADD]], [[SHR5]]181; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD6]], [[MUL]]182; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 65536, i32 0183; CHECK-NEXT: [[MUL8:%.*]] = mul nuw i32 [[SHR]], [[SHR1]]184; CHECK-NEXT: [[ADD9:%.*]] = add nuw i32 [[MUL8]], [[COND]]185; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16186; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR10]]187; CHECK-NEXT: ret i32 [[ADD11]]188;189entry:190 %shr = lshr i32 %x, 16191 %and = and i32 %x, 32767 ; wrong mask192 %shr1 = lshr i32 %y, 16193 %and2 = and i32 %y, 65535194 %mul = mul nuw i32 %shr, %and2195 %mul3 = mul nuw i32 %and, %shr1196 %add = add i32 %mul, %mul3197 %mul4 = mul nuw i32 %and, %and2198 %shr5 = lshr i32 %mul4, 16199 %add6 = add i32 %add, %shr5200 %cmp = icmp ult i32 %add6, %mul201 %cond = select i1 %cmp, i32 65536, i32 0202 %mul8 = mul nuw i32 %shr, %shr1203 %add9 = add nuw i32 %mul8, %cond204 %shr10 = lshr i32 %add6, 16205 %add11 = add i32 %add9, %shr10206 ret i32 %add11207}208 209define i32 @mul_carry_notyhi(i32 %x, i32 %y) {210; CHECK-LABEL: define i32 @mul_carry_notyhi(211; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {212; CHECK-NEXT: [[ENTRY:.*:]]213; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16214; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535215; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 14216; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535217; CHECK-NEXT: [[MUL:%.*]] = mul nuw i32 [[SHR]], [[AND2]]218; CHECK-NEXT: [[MUL3:%.*]] = mul nuw i32 [[AND]], [[SHR1]]219; CHECK-NEXT: [[ADD:%.*]] = add i32 [[MUL]], [[MUL3]]220; CHECK-NEXT: [[MUL4:%.*]] = mul nuw i32 [[AND]], [[AND2]]221; CHECK-NEXT: [[SHR5:%.*]] = lshr i32 [[MUL4]], 16222; CHECK-NEXT: [[ADD6:%.*]] = add i32 [[ADD]], [[SHR5]]223; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD6]], [[MUL]]224; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 65536, i32 0225; CHECK-NEXT: [[MUL8:%.*]] = mul nuw i32 [[SHR]], [[SHR1]]226; CHECK-NEXT: [[ADD9:%.*]] = add nuw i32 [[MUL8]], [[COND]]227; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16228; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR10]]229; CHECK-NEXT: ret i32 [[ADD11]]230;231entry:232 %shr = lshr i32 %x, 16233 %and = and i32 %x, 65535234 %shr1 = lshr i32 %y, 14 ; wring shift235 %and2 = and i32 %y, 65535236 %mul = mul nuw i32 %shr, %and2237 %mul3 = mul nuw i32 %and, %shr1238 %add = add i32 %mul, %mul3239 %mul4 = mul nuw i32 %and, %and2240 %shr5 = lshr i32 %mul4, 16241 %add6 = add i32 %add, %shr5242 %cmp = icmp ult i32 %add6, %mul243 %cond = select i1 %cmp, i32 65536, i32 0244 %mul8 = mul nuw i32 %shr, %shr1245 %add9 = add nuw i32 %mul8, %cond246 %shr10 = lshr i32 %add6, 16247 %add11 = add i32 %add9, %shr10248 ret i32 %add11249}250 251define i32 @mul_carry_notcarry(i32 %x, i32 %y) {252; CHECK-LABEL: define i32 @mul_carry_notcarry(253; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {254; CHECK-NEXT: [[ENTRY:.*:]]255; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16256; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535257; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 16258; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535259; CHECK-NEXT: [[MUL:%.*]] = mul nuw i32 [[SHR]], [[AND2]]260; CHECK-NEXT: [[MUL3:%.*]] = mul nuw i32 [[AND]], [[SHR1]]261; CHECK-NEXT: [[ADD:%.*]] = add i32 [[MUL]], [[MUL3]]262; CHECK-NEXT: [[MUL4:%.*]] = mul nuw i32 [[AND]], [[AND2]]263; CHECK-NEXT: [[SHR5:%.*]] = lshr i32 [[MUL4]], 16264; CHECK-NEXT: [[ADD6:%.*]] = add i32 [[ADD]], [[SHR5]]265; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD6]], [[MUL]]266; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 0, i32 65536267; CHECK-NEXT: [[MUL8:%.*]] = mul nuw i32 [[SHR]], [[SHR1]]268; CHECK-NEXT: [[ADD9:%.*]] = add nuw i32 [[MUL8]], [[COND]]269; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16270; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR10]]271; CHECK-NEXT: ret i32 [[ADD11]]272;273entry:274 %shr = lshr i32 %x, 16275 %and = and i32 %x, 65535276 %shr1 = lshr i32 %y, 16277 %and2 = and i32 %y, 65535278 %mul = mul nuw i32 %shr, %and2279 %mul3 = mul nuw i32 %and, %shr1280 %add = add i32 %mul, %mul3281 %mul4 = mul nuw i32 %and, %and2282 %shr5 = lshr i32 %mul4, 16283 %add6 = add i32 %add, %shr5284 %cmp = icmp ult i32 %add6, %mul285 %cond = select i1 %cmp, i32 0, i32 65536 ; backwards286 %mul8 = mul nuw i32 %shr, %shr1287 %add9 = add nuw i32 %mul8, %cond288 %shr10 = lshr i32 %add6, 16289 %add11 = add i32 %add9, %shr10290 ret i32 %add11291}292 293define i32 @mul_carry_notlolo(i32 %x, i32 %y) {294; CHECK-LABEL: define i32 @mul_carry_notlolo(295; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {296; CHECK-NEXT: [[ENTRY:.*:]]297; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16298; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535299; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 16300; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535301; CHECK-NEXT: [[MUL:%.*]] = mul nuw i32 [[SHR]], [[AND2]]302; CHECK-NEXT: [[MUL3:%.*]] = mul nuw i32 [[AND]], [[SHR1]]303; CHECK-NEXT: [[ADD:%.*]] = add i32 [[MUL]], [[MUL3]]304; CHECK-NEXT: [[SHR5:%.*]] = lshr i32 [[MUL]], 16305; CHECK-NEXT: [[ADD6:%.*]] = add i32 [[ADD]], [[SHR5]]306; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD6]], [[MUL]]307; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 65536, i32 0308; CHECK-NEXT: [[MUL8:%.*]] = mul nuw i32 [[SHR]], [[SHR1]]309; CHECK-NEXT: [[ADD9:%.*]] = add nuw i32 [[MUL8]], [[COND]]310; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16311; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR10]]312; CHECK-NEXT: ret i32 [[ADD11]]313;314entry:315 %shr = lshr i32 %x, 16316 %and = and i32 %x, 65535317 %shr1 = lshr i32 %y, 16318 %and2 = and i32 %y, 65535319 %mul = mul nuw i32 %shr, %and2320 %mul3 = mul nuw i32 %and, %shr1321 %add = add i32 %mul, %mul3322 %mul4 = mul nuw i32 %and, %and2323 %shr5 = lshr i32 %mul, 16324 %add6 = add i32 %add, %shr5325 %cmp = icmp ult i32 %add6, %mul326 %cond = select i1 %cmp, i32 65536, i32 0327 %mul8 = mul nuw i32 %shr, %shr1328 %add9 = add nuw i32 %mul8, %cond329 %shr10 = lshr i32 %add6, 16330 %add11 = add i32 %add9, %shr10331 ret i32 %add11332}333 334define i32 @mul_carry_nothihi(i32 %x, i32 %y) {335; CHECK-LABEL: define i32 @mul_carry_nothihi(336; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {337; CHECK-NEXT: [[ENTRY:.*:]]338; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16339; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535340; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 16341; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535342; CHECK-NEXT: [[MUL:%.*]] = mul nuw i32 [[SHR]], [[AND2]]343; CHECK-NEXT: [[MUL3:%.*]] = mul nuw i32 [[AND]], [[SHR1]]344; CHECK-NEXT: [[ADD:%.*]] = add i32 [[MUL]], [[MUL3]]345; CHECK-NEXT: [[MUL4:%.*]] = mul nuw i32 [[AND]], [[AND2]]346; CHECK-NEXT: [[SHR5:%.*]] = lshr i32 [[MUL4]], 16347; CHECK-NEXT: [[ADD6:%.*]] = add i32 [[ADD]], [[SHR5]]348; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD6]], [[MUL]]349; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 65536, i32 0350; CHECK-NEXT: [[ADD9:%.*]] = add nuw i32 [[MUL4]], [[COND]]351; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16352; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR10]]353; CHECK-NEXT: ret i32 [[ADD11]]354;355entry:356 %shr = lshr i32 %x, 16357 %and = and i32 %x, 65535358 %shr1 = lshr i32 %y, 16359 %and2 = and i32 %y, 65535360 %mul = mul nuw i32 %shr, %and2361 %mul3 = mul nuw i32 %and, %shr1362 %add = add i32 %mul, %mul3363 %mul4 = mul nuw i32 %and, %and2364 %shr5 = lshr i32 %mul4, 16365 %add6 = add i32 %add, %shr5366 %cmp = icmp ult i32 %add6, %mul367 %cond = select i1 %cmp, i32 65536, i32 0368 %mul8 = mul nuw i32 %shr, %shr1369 %add9 = add nuw i32 %mul4, %cond370 %shr10 = lshr i32 %add6, 16371 %add11 = add i32 %add9, %shr10372 ret i32 %add11373}374 375; Extra uses376define i32 @mul_carry_use_carry(i32 %x, i32 %y) {377; CHECK-LABEL: define i32 @mul_carry_use_carry(378; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {379; CHECK-NEXT: [[ENTRY:.*:]]380; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16381; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535382; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 16383; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535384; CHECK-NEXT: [[MUL:%.*]] = mul nuw i32 [[SHR]], [[AND2]]385; CHECK-NEXT: [[MUL3:%.*]] = mul nuw i32 [[AND]], [[SHR1]]386; CHECK-NEXT: [[ADD:%.*]] = add i32 [[MUL]], [[MUL3]]387; CHECK-NEXT: [[MUL4:%.*]] = mul nuw i32 [[AND]], [[AND2]]388; CHECK-NEXT: [[SHR5:%.*]] = lshr i32 [[MUL4]], 16389; CHECK-NEXT: [[ADD6:%.*]] = add i32 [[ADD]], [[SHR5]]390; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD6]], [[MUL]]391; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 65536, i32 0392; CHECK-NEXT: [[MUL8:%.*]] = mul nuw i32 [[SHR]], [[SHR1]]393; CHECK-NEXT: [[ADD9:%.*]] = add nuw i32 [[MUL8]], [[COND]]394; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16395; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR10]]396; CHECK-NEXT: call void (...) @llvm.fake.use(i32 [[COND]])397; CHECK-NEXT: ret i32 [[ADD11]]398;399entry:400 %shr = lshr i32 %x, 16401 %and = and i32 %x, 65535402 %shr1 = lshr i32 %y, 16403 %and2 = and i32 %y, 65535404 %mul = mul nuw i32 %shr, %and2405 %mul3 = mul nuw i32 %and, %shr1406 %add = add i32 %mul, %mul3407 %mul4 = mul nuw i32 %and, %and2408 %shr5 = lshr i32 %mul4, 16409 %add6 = add i32 %add, %shr5410 %cmp = icmp ult i32 %add6, %mul411 %cond = select i1 %cmp, i32 65536, i32 0412 %mul8 = mul nuw i32 %shr, %shr1413 %add9 = add nuw i32 %mul8, %cond414 %shr10 = lshr i32 %add6, 16415 %add11 = add i32 %add9, %shr10416 call void (...) @llvm.fake.use(i32 %cond)417 ret i32 %add11418}419 420define i32 @mul_carry_use_mulhi(i32 %x, i32 %y) {421; CHECK-LABEL: define i32 @mul_carry_use_mulhi(422; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {423; CHECK-NEXT: [[ENTRY:.*:]]424; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16425; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535426; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 16427; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535428; CHECK-NEXT: [[MUL:%.*]] = mul nuw i32 [[SHR]], [[AND2]]429; CHECK-NEXT: [[MUL3:%.*]] = mul nuw i32 [[AND]], [[SHR1]]430; CHECK-NEXT: [[ADD:%.*]] = add i32 [[MUL]], [[MUL3]]431; CHECK-NEXT: [[MUL4:%.*]] = mul nuw i32 [[AND]], [[AND2]]432; CHECK-NEXT: [[SHR5:%.*]] = lshr i32 [[MUL4]], 16433; CHECK-NEXT: [[ADD6:%.*]] = add i32 [[ADD]], [[SHR5]]434; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD6]], [[MUL]]435; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 65536, i32 0436; CHECK-NEXT: [[MUL8:%.*]] = mul nuw i32 [[SHR]], [[SHR1]]437; CHECK-NEXT: [[ADD9:%.*]] = add nuw i32 [[MUL8]], [[COND]]438; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16439; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR10]]440; CHECK-NEXT: call void (...) @llvm.fake.use(i32 [[MUL8]])441; CHECK-NEXT: ret i32 [[ADD11]]442;443entry:444 %shr = lshr i32 %x, 16445 %and = and i32 %x, 65535446 %shr1 = lshr i32 %y, 16447 %and2 = and i32 %y, 65535448 %mul = mul nuw i32 %shr, %and2449 %mul3 = mul nuw i32 %and, %shr1450 %add = add i32 %mul, %mul3451 %mul4 = mul nuw i32 %and, %and2452 %shr5 = lshr i32 %mul4, 16453 %add6 = add i32 %add, %shr5454 %cmp = icmp ult i32 %add6, %mul455 %cond = select i1 %cmp, i32 65536, i32 0456 %mul8 = mul nuw i32 %shr, %shr1457 %add9 = add nuw i32 %mul8, %cond458 %shr10 = lshr i32 %add6, 16459 %add11 = add i32 %add9, %shr10460 call void (...) @llvm.fake.use(i32 %mul8)461 ret i32 %add11462}463 464define i32 @mul_carry_use_llh(i32 %x, i32 %y) {465; CHECK-LABEL: define i32 @mul_carry_use_llh(466; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {467; CHECK-NEXT: [[ENTRY:.*:]]468; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535469; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535470; CHECK-NEXT: [[ADD6:%.*]] = mul nuw i32 [[AND]], [[AND2]]471; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16472; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[X]] to i64473; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[Y]] to i64474; CHECK-NEXT: [[TMP2:%.*]] = mul nuw i64 [[TMP0]], [[TMP1]]475; CHECK-NEXT: [[TMP3:%.*]] = lshr i64 [[TMP2]], 32476; CHECK-NEXT: [[ADD11:%.*]] = trunc nuw i64 [[TMP3]] to i32477; CHECK-NEXT: call void (...) @llvm.fake.use(i32 [[SHR10]])478; CHECK-NEXT: ret i32 [[ADD11]]479;480entry:481 %shr = lshr i32 %x, 16482 %and = and i32 %x, 65535483 %shr1 = lshr i32 %y, 16484 %and2 = and i32 %y, 65535485 %mul = mul nuw i32 %shr, %and2486 %mul3 = mul nuw i32 %and, %shr1487 %add = add i32 %mul, %mul3488 %mul4 = mul nuw i32 %and, %and2489 %shr5 = lshr i32 %mul4, 16490 %add6 = add i32 %add, %shr5491 %cmp = icmp ult i32 %add6, %mul492 %cond = select i1 %cmp, i32 65536, i32 0493 %mul8 = mul nuw i32 %shr, %shr1494 %add9 = add nuw i32 %mul8, %cond495 %shr10 = lshr i32 %add6, 16496 %add11 = add i32 %add9, %shr10497 call void (...) @llvm.fake.use(i32 %shr5)498 ret i32 %add11499}500 501define i32 @mul_carry_use_mulll(i32 %x, i32 %y) {502; CHECK-LABEL: define i32 @mul_carry_use_mulll(503; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {504; CHECK-NEXT: [[ENTRY:.*:]]505; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535506; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535507; CHECK-NEXT: [[MUL4:%.*]] = mul nuw i32 [[AND]], [[AND2]]508; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[X]] to i64509; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[Y]] to i64510; CHECK-NEXT: [[TMP2:%.*]] = mul nuw i64 [[TMP0]], [[TMP1]]511; CHECK-NEXT: [[TMP3:%.*]] = lshr i64 [[TMP2]], 32512; CHECK-NEXT: [[ADD11:%.*]] = trunc nuw i64 [[TMP3]] to i32513; CHECK-NEXT: call void (...) @llvm.fake.use(i32 [[MUL4]])514; CHECK-NEXT: ret i32 [[ADD11]]515;516entry:517 %shr = lshr i32 %x, 16518 %and = and i32 %x, 65535519 %shr1 = lshr i32 %y, 16520 %and2 = and i32 %y, 65535521 %mul = mul nuw i32 %shr, %and2522 %mul3 = mul nuw i32 %and, %shr1523 %add = add i32 %mul, %mul3524 %mul4 = mul nuw i32 %and, %and2525 %shr5 = lshr i32 %mul4, 16526 %add6 = add i32 %add, %shr5527 %cmp = icmp ult i32 %add6, %mul528 %cond = select i1 %cmp, i32 65536, i32 0529 %mul8 = mul nuw i32 %shr, %shr1530 %add9 = add nuw i32 %mul8, %cond531 %shr10 = lshr i32 %add6, 16532 %add11 = add i32 %add9, %shr10533 call void (...) @llvm.fake.use(i32 %mul4)534 ret i32 %add11535}536 537define i32 @mul_carry_use_mullh(i32 %x, i32 %y) {538; CHECK-LABEL: define i32 @mul_carry_use_mullh(539; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {540; CHECK-NEXT: [[ENTRY:.*:]]541; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16542; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535543; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 16544; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535545; CHECK-NEXT: [[MUL:%.*]] = mul nuw i32 [[SHR]], [[AND2]]546; CHECK-NEXT: [[MUL3:%.*]] = mul nuw i32 [[AND]], [[SHR1]]547; CHECK-NEXT: [[ADD:%.*]] = add i32 [[MUL]], [[MUL3]]548; CHECK-NEXT: [[MUL4:%.*]] = mul nuw i32 [[AND]], [[AND2]]549; CHECK-NEXT: [[SHR5:%.*]] = lshr i32 [[MUL4]], 16550; CHECK-NEXT: [[ADD6:%.*]] = add i32 [[ADD]], [[SHR5]]551; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD6]], [[MUL]]552; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 65536, i32 0553; CHECK-NEXT: [[MUL8:%.*]] = mul nuw i32 [[SHR]], [[SHR1]]554; CHECK-NEXT: [[ADD9:%.*]] = add nuw i32 [[MUL8]], [[COND]]555; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16556; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR10]]557; CHECK-NEXT: call void (...) @llvm.fake.use(i32 [[MUL3]])558; CHECK-NEXT: ret i32 [[ADD11]]559;560entry:561 %shr = lshr i32 %x, 16562 %and = and i32 %x, 65535563 %shr1 = lshr i32 %y, 16564 %and2 = and i32 %y, 65535565 %mul = mul nuw i32 %shr, %and2566 %mul3 = mul nuw i32 %and, %shr1567 %add = add i32 %mul, %mul3568 %mul4 = mul nuw i32 %and, %and2569 %shr5 = lshr i32 %mul4, 16570 %add6 = add i32 %add, %shr5571 %cmp = icmp ult i32 %add6, %mul572 %cond = select i1 %cmp, i32 65536, i32 0573 %mul8 = mul nuw i32 %shr, %shr1574 %add9 = add nuw i32 %mul8, %cond575 %shr10 = lshr i32 %add6, 16576 %add11 = add i32 %add9, %shr10577 call void (...) @llvm.fake.use(i32 %mul3)578 ret i32 %add11579}580 581define i32 @mul_carry_use_mulhl(i32 %x, i32 %y) {582; CHECK-LABEL: define i32 @mul_carry_use_mulhl(583; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {584; CHECK-NEXT: [[ENTRY:.*:]]585; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16586; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535587; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 16588; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535589; CHECK-NEXT: [[MUL:%.*]] = mul nuw i32 [[SHR]], [[AND2]]590; CHECK-NEXT: [[MUL3:%.*]] = mul nuw i32 [[AND]], [[SHR1]]591; CHECK-NEXT: [[ADD:%.*]] = add i32 [[MUL]], [[MUL3]]592; CHECK-NEXT: [[MUL4:%.*]] = mul nuw i32 [[AND]], [[AND2]]593; CHECK-NEXT: [[SHR5:%.*]] = lshr i32 [[MUL4]], 16594; CHECK-NEXT: [[ADD6:%.*]] = add i32 [[ADD]], [[SHR5]]595; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD6]], [[MUL]]596; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 65536, i32 0597; CHECK-NEXT: [[MUL8:%.*]] = mul nuw i32 [[SHR]], [[SHR1]]598; CHECK-NEXT: [[ADD9:%.*]] = add nuw i32 [[MUL8]], [[COND]]599; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16600; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR10]]601; CHECK-NEXT: call void (...) @llvm.fake.use(i32 [[MUL]])602; CHECK-NEXT: ret i32 [[ADD11]]603;604entry:605 %shr = lshr i32 %x, 16606 %and = and i32 %x, 65535607 %shr1 = lshr i32 %y, 16608 %and2 = and i32 %y, 65535609 %mul = mul nuw i32 %shr, %and2610 %mul3 = mul nuw i32 %and, %shr1611 %add = add i32 %mul, %mul3612 %mul4 = mul nuw i32 %and, %and2613 %shr5 = lshr i32 %mul4, 16614 %add6 = add i32 %add, %shr5615 %cmp = icmp ult i32 %add6, %mul616 %cond = select i1 %cmp, i32 65536, i32 0617 %mul8 = mul nuw i32 %shr, %shr1618 %add9 = add nuw i32 %mul8, %cond619 %shr10 = lshr i32 %add6, 16620 %add11 = add i32 %add9, %shr10621 call void (...) @llvm.fake.use(i32 %mul)622 ret i32 %add11623}624 625define i32 @mul_carry_use_crosssum(i32 %x, i32 %y) {626; CHECK-LABEL: define i32 @mul_carry_use_crosssum(627; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {628; CHECK-NEXT: [[ENTRY:.*:]]629; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16630; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535631; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 16632; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535633; CHECK-NEXT: [[ADD9:%.*]] = mul nuw i32 [[SHR]], [[AND2]]634; CHECK-NEXT: [[SHR10:%.*]] = mul nuw i32 [[AND]], [[SHR1]]635; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR10]]636; CHECK-NEXT: [[MUL4:%.*]] = mul nuw i32 [[AND]], [[AND2]]637; CHECK-NEXT: [[SHR5:%.*]] = lshr i32 [[MUL4]], 16638; CHECK-NEXT: [[ADD6:%.*]] = add i32 [[ADD11]], [[SHR5]]639; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD6]], [[ADD9]]640; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 65536, i32 0641; CHECK-NEXT: [[MUL8:%.*]] = mul nuw i32 [[SHR]], [[SHR1]]642; CHECK-NEXT: [[ADD10:%.*]] = add nuw i32 [[MUL8]], [[COND]]643; CHECK-NEXT: [[SHR11:%.*]] = lshr i32 [[ADD6]], 16644; CHECK-NEXT: [[TMP4:%.*]] = add i32 [[ADD10]], [[SHR11]]645; CHECK-NEXT: call void (...) @llvm.fake.use(i32 [[ADD11]])646; CHECK-NEXT: ret i32 [[TMP4]]647;648entry:649 %shr = lshr i32 %x, 16650 %and = and i32 %x, 65535651 %shr1 = lshr i32 %y, 16652 %and2 = and i32 %y, 65535653 %mul = mul nuw i32 %shr, %and2654 %mul3 = mul nuw i32 %and, %shr1655 %add = add i32 %mul, %mul3656 %mul4 = mul nuw i32 %and, %and2657 %shr5 = lshr i32 %mul4, 16658 %add6 = add i32 %add, %shr5659 %cmp = icmp ult i32 %add6, %mul660 %cond = select i1 %cmp, i32 65536, i32 0661 %mul8 = mul nuw i32 %shr, %shr1662 %add9 = add nuw i32 %mul8, %cond663 %shr10 = lshr i32 %add6, 16664 %add11 = add i32 %add9, %shr10665 call void (...) @llvm.fake.use(i32 %add)666 ret i32 %add11667}668 669define i32 @mul_carry_use_lowaccumhi(i32 %x, i32 %y) {670; CHECK-LABEL: define i32 @mul_carry_use_lowaccumhi(671; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {672; CHECK-NEXT: [[ENTRY:.*:]]673; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16674; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535675; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 16676; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535677; CHECK-NEXT: [[MUL:%.*]] = mul nuw i32 [[SHR]], [[AND2]]678; CHECK-NEXT: [[MUL3:%.*]] = mul nuw i32 [[AND]], [[SHR1]]679; CHECK-NEXT: [[ADD:%.*]] = add i32 [[MUL]], [[MUL3]]680; CHECK-NEXT: [[ADD6:%.*]] = mul nuw i32 [[AND]], [[AND2]]681; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16682; CHECK-NEXT: [[ADD7:%.*]] = add i32 [[ADD]], [[SHR10]]683; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD7]], [[MUL]]684; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 65536, i32 0685; CHECK-NEXT: [[MUL8:%.*]] = mul nuw i32 [[SHR]], [[SHR1]]686; CHECK-NEXT: [[ADD9:%.*]] = add nuw i32 [[MUL8]], [[COND]]687; CHECK-NEXT: [[SHR11:%.*]] = lshr i32 [[ADD7]], 16688; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR11]]689; CHECK-NEXT: call void (...) @llvm.fake.use(i32 [[SHR11]])690; CHECK-NEXT: ret i32 [[ADD11]]691;692entry:693 %shr = lshr i32 %x, 16694 %and = and i32 %x, 65535695 %shr1 = lshr i32 %y, 16696 %and2 = and i32 %y, 65535697 %mul = mul nuw i32 %shr, %and2698 %mul3 = mul nuw i32 %and, %shr1699 %add = add i32 %mul, %mul3700 %mul4 = mul nuw i32 %and, %and2701 %shr5 = lshr i32 %mul4, 16702 %add6 = add i32 %add, %shr5703 %cmp = icmp ult i32 %add6, %mul704 %cond = select i1 %cmp, i32 65536, i32 0705 %mul8 = mul nuw i32 %shr, %shr1706 %add9 = add nuw i32 %mul8, %cond707 %shr10 = lshr i32 %add6, 16708 %add11 = add i32 %add9, %shr10709 call void (...) @llvm.fake.use(i32 %shr10)710 ret i32 %add11711}712 713define i32 @mul_carry_use_lowaccum(i32 %x, i32 %y) {714; CHECK-LABEL: define i32 @mul_carry_use_lowaccum(715; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {716; CHECK-NEXT: [[ENTRY:.*:]]717; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[X]], 16718; CHECK-NEXT: [[AND:%.*]] = and i32 [[X]], 65535719; CHECK-NEXT: [[SHR1:%.*]] = lshr i32 [[Y]], 16720; CHECK-NEXT: [[AND2:%.*]] = and i32 [[Y]], 65535721; CHECK-NEXT: [[MUL:%.*]] = mul nuw i32 [[SHR]], [[AND2]]722; CHECK-NEXT: [[MUL3:%.*]] = mul nuw i32 [[AND]], [[SHR1]]723; CHECK-NEXT: [[ADD:%.*]] = add i32 [[MUL]], [[MUL3]]724; CHECK-NEXT: [[MUL4:%.*]] = mul nuw i32 [[AND]], [[AND2]]725; CHECK-NEXT: [[SHR5:%.*]] = lshr i32 [[MUL4]], 16726; CHECK-NEXT: [[ADD6:%.*]] = add i32 [[ADD]], [[SHR5]]727; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[ADD6]], [[MUL]]728; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 65536, i32 0729; CHECK-NEXT: [[MUL8:%.*]] = mul nuw i32 [[SHR]], [[SHR1]]730; CHECK-NEXT: [[ADD9:%.*]] = add nuw i32 [[MUL8]], [[COND]]731; CHECK-NEXT: [[SHR10:%.*]] = lshr i32 [[ADD6]], 16732; CHECK-NEXT: [[ADD11:%.*]] = add i32 [[ADD9]], [[SHR10]]733; CHECK-NEXT: call void (...) @llvm.fake.use(i32 [[ADD6]])734; CHECK-NEXT: ret i32 [[ADD11]]735;736entry:737 %shr = lshr i32 %x, 16738 %and = and i32 %x, 65535739 %shr1 = lshr i32 %y, 16740 %and2 = and i32 %y, 65535741 %mul = mul nuw i32 %shr, %and2742 %mul3 = mul nuw i32 %and, %shr1743 %add = add i32 %mul, %mul3744 %mul4 = mul nuw i32 %and, %and2745 %shr5 = lshr i32 %mul4, 16746 %add6 = add i32 %add, %shr5747 %cmp = icmp ult i32 %add6, %mul748 %cond = select i1 %cmp, i32 65536, i32 0749 %mul8 = mul nuw i32 %shr, %shr1750 %add9 = add nuw i32 %mul8, %cond751 %shr10 = lshr i32 %add6, 16752 %add11 = add i32 %add9, %shr10753 call void (...) @llvm.fake.use(i32 %add6)754 ret i32 %add11755}756