724 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=instcombine -S | FileCheck %s3 4target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"5target triple = "x86_64-unknown-linux-gnu"6 7define { i64, i64 } @mul_full_64_variant0(i64 %x, i64 %y) {8; CHECK-LABEL: @mul_full_64_variant0(9; CHECK-NEXT: [[XL:%.*]] = and i64 [[X:%.*]], 429496729510; CHECK-NEXT: [[XH:%.*]] = lshr i64 [[X]], 3211; CHECK-NEXT: [[YL:%.*]] = and i64 [[Y:%.*]], 429496729512; CHECK-NEXT: [[YH:%.*]] = lshr i64 [[Y]], 3213; CHECK-NEXT: [[T0:%.*]] = mul nuw i64 [[YL]], [[XL]]14; CHECK-NEXT: [[T1:%.*]] = mul nuw i64 [[YL]], [[XH]]15; CHECK-NEXT: [[T2:%.*]] = mul nuw i64 [[YH]], [[XL]]16; CHECK-NEXT: [[T3:%.*]] = mul nuw i64 [[YH]], [[XH]]17; CHECK-NEXT: [[T0L:%.*]] = and i64 [[T0]], 429496729518; CHECK-NEXT: [[T0H:%.*]] = lshr i64 [[T0]], 3219; CHECK-NEXT: [[U0:%.*]] = add i64 [[T0H]], [[T1]]20; CHECK-NEXT: [[U0L:%.*]] = and i64 [[U0]], 429496729521; CHECK-NEXT: [[U0H:%.*]] = lshr i64 [[U0]], 3222; CHECK-NEXT: [[U1:%.*]] = add i64 [[U0L]], [[T2]]23; CHECK-NEXT: [[U1LS:%.*]] = shl i64 [[U1]], 3224; CHECK-NEXT: [[U1H:%.*]] = lshr i64 [[U1]], 3225; CHECK-NEXT: [[U2:%.*]] = add i64 [[U0H]], [[T3]]26; CHECK-NEXT: [[LO:%.*]] = or disjoint i64 [[U1LS]], [[T0L]]27; CHECK-NEXT: [[HI:%.*]] = add i64 [[U2]], [[U1H]]28; CHECK-NEXT: [[RES_LO:%.*]] = insertvalue { i64, i64 } undef, i64 [[LO]], 029; CHECK-NEXT: [[RES:%.*]] = insertvalue { i64, i64 } [[RES_LO]], i64 [[HI]], 130; CHECK-NEXT: ret { i64, i64 } [[RES]]31;32 %xl = and i64 %x, 429496729533 %xh = lshr i64 %x, 3234 %yl = and i64 %y, 429496729535 %yh = lshr i64 %y, 3236 37 %t0 = mul nuw i64 %yl, %xl38 %t1 = mul nuw i64 %yl, %xh39 %t2 = mul nuw i64 %yh, %xl40 %t3 = mul nuw i64 %yh, %xh41 42 %t0l = and i64 %t0, 429496729543 %t0h = lshr i64 %t0, 3244 45 %u0 = add i64 %t0h, %t146 %u0l = and i64 %u0, 429496729547 %u0h = lshr i64 %u0, 3248 49 %u1 = add i64 %u0l, %t250 %u1ls = shl i64 %u1, 3251 %u1h = lshr i64 %u1, 3252 53 %u2 = add i64 %u0h, %t354 55 %lo = or i64 %u1ls, %t0l56 %hi = add i64 %u2, %u1h57 58 %res_lo = insertvalue { i64, i64 } undef, i64 %lo, 059 %res = insertvalue { i64, i64 } %res_lo, i64 %hi, 160 ret { i64, i64 } %res61}62 63; The following variants 1 - 3 are generated with this C++ program:64;65; #include <stdint.h>66;67; uint64_t mulxu(uint64_t a, uint64_t b, uint64_t *rhi) {68; auto hi = [](uint64_t x) { return x >> 32; };69; auto lo = [](uint64_t x) { return uint32_t(x); };70; uint64_t xl = lo(a);71; uint64_t xh = hi(a);72; uint64_t yl = lo(b);73; uint64_t yh = hi(b);74;75; uint64_t rhh = xh * yh;76; uint64_t rhl = xh * yl;77; uint64_t rlh = xl * yh;78; uint64_t rll = xl * yl;79;80; *rhi = rhh + hi(rhl + hi(rll)) + hi((rlh + lo(rhl + hi(rll))));81; #if ONE82; return a*b;83; #elif TWO84; return (uint64_t(lo(rlh + lo(rhl + hi(rll)))) << 32) + lo(rll);85; #elif THREE86; return ((rlh + rhl) << 32) + rll;87; #endif88; }89 90define i64 @mul_full_64_variant1(i64 %a, i64 %b, ptr nocapture %rhi) {91; CHECK-LABEL: @mul_full_64_variant1(92; CHECK-NEXT: [[CONV:%.*]] = and i64 [[A:%.*]], 429496729593; CHECK-NEXT: [[SHR_I43:%.*]] = lshr i64 [[A]], 3294; CHECK-NEXT: [[CONV3:%.*]] = and i64 [[B:%.*]], 429496729595; CHECK-NEXT: [[SHR_I41:%.*]] = lshr i64 [[B]], 3296; CHECK-NEXT: [[MUL:%.*]] = mul nuw i64 [[SHR_I41]], [[SHR_I43]]97; CHECK-NEXT: [[MUL5:%.*]] = mul nuw i64 [[CONV3]], [[SHR_I43]]98; CHECK-NEXT: [[MUL6:%.*]] = mul nuw i64 [[SHR_I41]], [[CONV]]99; CHECK-NEXT: [[MUL7:%.*]] = mul nuw i64 [[CONV3]], [[CONV]]100; CHECK-NEXT: [[SHR_I40:%.*]] = lshr i64 [[MUL7]], 32101; CHECK-NEXT: [[ADD:%.*]] = add i64 [[SHR_I40]], [[MUL5]]102; CHECK-NEXT: [[SHR_I39:%.*]] = lshr i64 [[ADD]], 32103; CHECK-NEXT: [[ADD10:%.*]] = add i64 [[SHR_I39]], [[MUL]]104; CHECK-NEXT: [[CONV14:%.*]] = and i64 [[ADD]], 4294967295105; CHECK-NEXT: [[ADD15:%.*]] = add i64 [[CONV14]], [[MUL6]]106; CHECK-NEXT: [[SHR_I:%.*]] = lshr i64 [[ADD15]], 32107; CHECK-NEXT: [[ADD17:%.*]] = add i64 [[ADD10]], [[SHR_I]]108; CHECK-NEXT: store i64 [[ADD17]], ptr [[RHI:%.*]], align 8109; CHECK-NEXT: [[MULLO:%.*]] = mul i64 [[B]], [[A]]110; CHECK-NEXT: ret i64 [[MULLO]]111;112 %conv = and i64 %a, 4294967295113 %shr.i43 = lshr i64 %a, 32114 %conv3 = and i64 %b, 4294967295115 %shr.i41 = lshr i64 %b, 32116 %mul = mul nuw i64 %shr.i41, %shr.i43117 %mul5 = mul nuw i64 %conv3, %shr.i43118 %mul6 = mul nuw i64 %shr.i41, %conv119 %mul7 = mul nuw i64 %conv3, %conv120 %shr.i40 = lshr i64 %mul7, 32121 %add = add i64 %shr.i40, %mul5122 %shr.i39 = lshr i64 %add, 32123 %add10 = add i64 %shr.i39, %mul124 %conv14 = and i64 %add, 4294967295125 %add15 = add i64 %conv14, %mul6126 %shr.i = lshr i64 %add15, 32127 %add17 = add i64 %add10, %shr.i128 store i64 %add17, ptr %rhi, align 8129 %mullo = mul i64 %b, %a130 ret i64 %mullo131}132 133define i64 @mul_full_64_variant2(i64 %a, i64 %b, ptr nocapture %rhi) {134; CHECK-LABEL: @mul_full_64_variant2(135; CHECK-NEXT: [[CONV:%.*]] = and i64 [[A:%.*]], 4294967295136; CHECK-NEXT: [[SHR_I58:%.*]] = lshr i64 [[A]], 32137; CHECK-NEXT: [[CONV3:%.*]] = and i64 [[B:%.*]], 4294967295138; CHECK-NEXT: [[SHR_I56:%.*]] = lshr i64 [[B]], 32139; CHECK-NEXT: [[MUL:%.*]] = mul nuw i64 [[SHR_I56]], [[SHR_I58]]140; CHECK-NEXT: [[MUL5:%.*]] = mul nuw i64 [[CONV3]], [[SHR_I58]]141; CHECK-NEXT: [[MUL6:%.*]] = mul nuw i64 [[SHR_I56]], [[CONV]]142; CHECK-NEXT: [[MUL7:%.*]] = mul nuw i64 [[CONV3]], [[CONV]]143; CHECK-NEXT: [[SHR_I55:%.*]] = lshr i64 [[MUL7]], 32144; CHECK-NEXT: [[ADD:%.*]] = add i64 [[SHR_I55]], [[MUL5]]145; CHECK-NEXT: [[SHR_I54:%.*]] = lshr i64 [[ADD]], 32146; CHECK-NEXT: [[ADD10:%.*]] = add i64 [[SHR_I54]], [[MUL]]147; CHECK-NEXT: [[CONV14:%.*]] = and i64 [[ADD]], 4294967295148; CHECK-NEXT: [[ADD15:%.*]] = add i64 [[CONV14]], [[MUL6]]149; CHECK-NEXT: [[SHR_I51:%.*]] = lshr i64 [[ADD15]], 32150; CHECK-NEXT: [[ADD17:%.*]] = add i64 [[ADD10]], [[SHR_I51]]151; CHECK-NEXT: store i64 [[ADD17]], ptr [[RHI:%.*]], align 8152; CHECK-NEXT: [[CONV24:%.*]] = shl i64 [[ADD15]], 32153; CHECK-NEXT: [[CONV26:%.*]] = and i64 [[MUL7]], 4294967295154; CHECK-NEXT: [[ADD27:%.*]] = or disjoint i64 [[CONV24]], [[CONV26]]155; CHECK-NEXT: ret i64 [[ADD27]]156;157 %conv = and i64 %a, 4294967295158 %shr.i58 = lshr i64 %a, 32159 %conv3 = and i64 %b, 4294967295160 %shr.i56 = lshr i64 %b, 32161 %mul = mul nuw i64 %shr.i56, %shr.i58162 %mul5 = mul nuw i64 %conv3, %shr.i58163 %mul6 = mul nuw i64 %shr.i56, %conv164 %mul7 = mul nuw i64 %conv3, %conv165 %shr.i55 = lshr i64 %mul7, 32166 %add = add i64 %shr.i55, %mul5167 %shr.i54 = lshr i64 %add, 32168 %add10 = add i64 %shr.i54, %mul169 %conv14 = and i64 %add, 4294967295170 %add15 = add i64 %conv14, %mul6171 %shr.i51 = lshr i64 %add15, 32172 %add17 = add i64 %add10, %shr.i51173 store i64 %add17, ptr %rhi, align 8174 %conv24 = shl i64 %add15, 32175 %conv26 = and i64 %mul7, 4294967295176 %add27 = or i64 %conv24, %conv26177 ret i64 %add27178}179 180; Negative test case for mul_fold function: MUL7 is used in more than one place181define i64 @mul_full_64_variant3(i64 %a, i64 %b, ptr nocapture %rhi) {182; CHECK-LABEL: @mul_full_64_variant3(183; CHECK-NEXT: [[CONV:%.*]] = and i64 [[A:%.*]], 4294967295184; CHECK-NEXT: [[SHR_I45:%.*]] = lshr i64 [[A]], 32185; CHECK-NEXT: [[CONV3:%.*]] = and i64 [[B:%.*]], 4294967295186; CHECK-NEXT: [[SHR_I43:%.*]] = lshr i64 [[B]], 32187; CHECK-NEXT: [[MUL:%.*]] = mul nuw i64 [[SHR_I43]], [[SHR_I45]]188; CHECK-NEXT: [[MUL5:%.*]] = mul nuw i64 [[CONV3]], [[SHR_I45]]189; CHECK-NEXT: [[MUL6:%.*]] = mul nuw i64 [[SHR_I43]], [[CONV]]190; CHECK-NEXT: [[MUL7:%.*]] = mul nuw i64 [[CONV3]], [[CONV]]191; CHECK-NEXT: [[SHR_I42:%.*]] = lshr i64 [[MUL7]], 32192; CHECK-NEXT: [[ADD:%.*]] = add i64 [[SHR_I42]], [[MUL5]]193; CHECK-NEXT: [[SHR_I41:%.*]] = lshr i64 [[ADD]], 32194; CHECK-NEXT: [[ADD10:%.*]] = add i64 [[SHR_I41]], [[MUL]]195; CHECK-NEXT: [[CONV14:%.*]] = and i64 [[ADD]], 4294967295196; CHECK-NEXT: [[ADD15:%.*]] = add i64 [[CONV14]], [[MUL6]]197; CHECK-NEXT: [[SHR_I:%.*]] = lshr i64 [[ADD15]], 32198; CHECK-NEXT: [[ADD17:%.*]] = add i64 [[ADD10]], [[SHR_I]]199; CHECK-NEXT: store i64 [[ADD17]], ptr [[RHI:%.*]], align 8200; CHECK-NEXT: [[ADD18:%.*]] = add i64 [[MUL6]], [[MUL5]]201; CHECK-NEXT: [[SHL:%.*]] = shl i64 [[ADD18]], 32202; CHECK-NEXT: [[ADD19:%.*]] = add i64 [[SHL]], [[MUL7]]203; CHECK-NEXT: ret i64 [[ADD19]]204;205 %conv = and i64 %a, 4294967295206 %shr.i45 = lshr i64 %a, 32207 %conv3 = and i64 %b, 4294967295208 %shr.i43 = lshr i64 %b, 32209 %mul = mul nuw i64 %shr.i43, %shr.i45210 %mul5 = mul nuw i64 %conv3, %shr.i45211 %mul6 = mul nuw i64 %shr.i43, %conv212 %mul7 = mul nuw i64 %conv3, %conv213 %shr.i42 = lshr i64 %mul7, 32214 %add = add i64 %shr.i42, %mul5215 %shr.i41 = lshr i64 %add, 32216 %add10 = add i64 %shr.i41, %mul217 %conv14 = and i64 %add, 4294967295218 %add15 = add i64 %conv14, %mul6219 %shr.i = lshr i64 %add15, 32220 %add17 = add i64 %add10, %shr.i221 store i64 %add17, ptr %rhi, align 8222 %add18 = add i64 %mul6, %mul5223 %shl = shl i64 %add18, 32224 %add19 = add i64 %shl, %mul7225 ret i64 %add19226}227 228 229define { i32, i32 } @mul_full_32(i32 %x, i32 %y) {230; CHECK-LABEL: @mul_full_32(231; CHECK-NEXT: [[XL:%.*]] = and i32 [[X:%.*]], 65535232; CHECK-NEXT: [[XH:%.*]] = lshr i32 [[X]], 16233; CHECK-NEXT: [[YL:%.*]] = and i32 [[Y:%.*]], 65535234; CHECK-NEXT: [[YH:%.*]] = lshr i32 [[Y]], 16235; CHECK-NEXT: [[T0:%.*]] = mul nuw i32 [[YL]], [[XL]]236; CHECK-NEXT: [[T1:%.*]] = mul nuw i32 [[YL]], [[XH]]237; CHECK-NEXT: [[T2:%.*]] = mul nuw i32 [[YH]], [[XL]]238; CHECK-NEXT: [[T3:%.*]] = mul nuw i32 [[YH]], [[XH]]239; CHECK-NEXT: [[T0L:%.*]] = and i32 [[T0]], 65535240; CHECK-NEXT: [[T0H:%.*]] = lshr i32 [[T0]], 16241; CHECK-NEXT: [[U0:%.*]] = add i32 [[T0H]], [[T1]]242; CHECK-NEXT: [[U0L:%.*]] = and i32 [[U0]], 65535243; CHECK-NEXT: [[U0H:%.*]] = lshr i32 [[U0]], 16244; CHECK-NEXT: [[U1:%.*]] = add i32 [[U0L]], [[T2]]245; CHECK-NEXT: [[U1LS:%.*]] = shl i32 [[U1]], 16246; CHECK-NEXT: [[U1H:%.*]] = lshr i32 [[U1]], 16247; CHECK-NEXT: [[U2:%.*]] = add i32 [[U0H]], [[T3]]248; CHECK-NEXT: [[LO:%.*]] = or disjoint i32 [[U1LS]], [[T0L]]249; CHECK-NEXT: [[HI:%.*]] = add i32 [[U2]], [[U1H]]250; CHECK-NEXT: [[RES_LO:%.*]] = insertvalue { i32, i32 } undef, i32 [[LO]], 0251; CHECK-NEXT: [[RES:%.*]] = insertvalue { i32, i32 } [[RES_LO]], i32 [[HI]], 1252; CHECK-NEXT: ret { i32, i32 } [[RES]]253;254 %xl = and i32 %x, 65535255 %xh = lshr i32 %x, 16256 %yl = and i32 %y, 65535257 %yh = lshr i32 %y, 16258 259 %t0 = mul nuw i32 %yl, %xl260 %t1 = mul nuw i32 %yl, %xh261 %t2 = mul nuw i32 %yh, %xl262 %t3 = mul nuw i32 %yh, %xh263 264 %t0l = and i32 %t0, 65535265 %t0h = lshr i32 %t0, 16266 267 %u0 = add i32 %t0h, %t1268 %u0l = and i32 %u0, 65535269 %u0h = lshr i32 %u0, 16270 271 %u1 = add i32 %u0l, %t2272 %u1ls = shl i32 %u1, 16273 %u1h = lshr i32 %u1, 16274 275 %u2 = add i32 %u0h, %t3276 277 %lo = or i32 %u1ls, %t0l278 %hi = add i32 %u2, %u1h279 280 %res_lo = insertvalue { i32, i32 } undef, i32 %lo, 0281 %res = insertvalue { i32, i32 } %res_lo, i32 %hi, 1282 ret { i32, i32 } %res283}284 285 286declare i64 @get_number()287 288; In the following test cases %x and %y are instructions, not arguments.289; This tests the placement of mul i128 and zexts.290; Instructions are also shuffled.291 292define { i64, i64 } @mul_full_64_variant0_1() {293; CHECK-LABEL: @mul_full_64_variant0_1(294; CHECK-NEXT: [[TMP1:%.*]] = call i64 @get_number()295; CHECK-NEXT: [[YL:%.*]] = and i64 [[TMP1]], 4294967295296; CHECK-NEXT: [[YH:%.*]] = lshr i64 [[TMP1]], 32297; CHECK-NEXT: [[TMP2:%.*]] = call i64 @get_number()298; CHECK-NEXT: [[XH:%.*]] = lshr i64 [[TMP2]], 32299; CHECK-NEXT: [[XL:%.*]] = and i64 [[TMP2]], 4294967295300; CHECK-NEXT: [[T1:%.*]] = mul nuw i64 [[YL]], [[XH]]301; CHECK-NEXT: [[T3:%.*]] = mul nuw i64 [[YH]], [[XH]]302; CHECK-NEXT: [[T2:%.*]] = mul nuw i64 [[YH]], [[XL]]303; CHECK-NEXT: [[T0:%.*]] = mul nuw i64 [[YL]], [[XL]]304; CHECK-NEXT: [[T0H:%.*]] = lshr i64 [[T0]], 32305; CHECK-NEXT: [[U0:%.*]] = add i64 [[T0H]], [[T1]]306; CHECK-NEXT: [[U0L:%.*]] = and i64 [[U0]], 4294967295307; CHECK-NEXT: [[U1:%.*]] = add i64 [[U0L]], [[T2]]308; CHECK-NEXT: [[U0H:%.*]] = lshr i64 [[U0]], 32309; CHECK-NEXT: [[U2:%.*]] = add i64 [[U0H]], [[T3]]310; CHECK-NEXT: [[U1H:%.*]] = lshr i64 [[U1]], 32311; CHECK-NEXT: [[HI:%.*]] = add i64 [[U2]], [[U1H]]312; CHECK-NEXT: [[U1LS:%.*]] = shl i64 [[U1]], 32313; CHECK-NEXT: [[T0L:%.*]] = and i64 [[T0]], 4294967295314; CHECK-NEXT: [[LO:%.*]] = or disjoint i64 [[U1LS]], [[T0L]]315; CHECK-NEXT: [[RES_LO:%.*]] = insertvalue { i64, i64 } undef, i64 [[LO]], 0316; CHECK-NEXT: [[RES:%.*]] = insertvalue { i64, i64 } [[RES_LO]], i64 [[HI]], 1317; CHECK-NEXT: ret { i64, i64 } [[RES]]318;319 %1 = call i64 @get_number()320 %yl = and i64 %1, 4294967295321 %yh = lshr i64 %1, 32322 323 %2 = call i64 @get_number()324 %xh = lshr i64 %2, 32325 %xl = and i64 %2, 4294967295326 327 %t1 = mul nuw i64 %yl, %xh328 %t3 = mul nuw i64 %yh, %xh329 %t2 = mul nuw i64 %yh, %xl330 %t0 = mul nuw i64 %yl, %xl331 332 %t0h = lshr i64 %t0, 32333 %u0 = add i64 %t0h, %t1334 %u0l = and i64 %u0, 4294967295335 %u1 = add i64 %u0l, %t2336 %u0h = lshr i64 %u0, 32337 %u2 = add i64 %u0h, %t3338 %u1h = lshr i64 %u1, 32339 %hi = add i64 %u2, %u1h340 341 %u1ls = shl i64 %u1, 32342 %t0l = and i64 %t0, 4294967295343 %lo = or i64 %u1ls, %t0l344 345 %res_lo = insertvalue { i64, i64 } undef, i64 %lo, 0346 %res = insertvalue { i64, i64 } %res_lo, i64 %hi, 1347 ret { i64, i64 } %res348}349 350define { i64, i64 } @mul_full_64_variant0_2() {351; CHECK-LABEL: @mul_full_64_variant0_2(352; CHECK-NEXT: [[X:%.*]] = call i64 @get_number()353; CHECK-NEXT: [[Y:%.*]] = call i64 @get_number()354; CHECK-NEXT: [[YL:%.*]] = and i64 [[Y]], 4294967295355; CHECK-NEXT: [[YH:%.*]] = lshr i64 [[Y]], 32356; CHECK-NEXT: [[XH:%.*]] = lshr i64 [[X]], 32357; CHECK-NEXT: [[XL:%.*]] = and i64 [[X]], 4294967295358; CHECK-NEXT: [[T3:%.*]] = mul nuw i64 [[XH]], [[YH]]359; CHECK-NEXT: [[T2:%.*]] = mul nuw i64 [[XL]], [[YH]]360; CHECK-NEXT: [[T1:%.*]] = mul nuw i64 [[XH]], [[YL]]361; CHECK-NEXT: [[T0:%.*]] = mul nuw i64 [[XL]], [[YL]]362; CHECK-NEXT: [[T0H:%.*]] = lshr i64 [[T0]], 32363; CHECK-NEXT: [[U0:%.*]] = add i64 [[T1]], [[T0H]]364; CHECK-NEXT: [[U0L:%.*]] = and i64 [[U0]], 4294967295365; CHECK-NEXT: [[U1:%.*]] = add i64 [[T2]], [[U0L]]366; CHECK-NEXT: [[U0H:%.*]] = lshr i64 [[U0]], 32367; CHECK-NEXT: [[U2:%.*]] = add i64 [[U0H]], [[T3]]368; CHECK-NEXT: [[U1H:%.*]] = lshr i64 [[U1]], 32369; CHECK-NEXT: [[HI:%.*]] = add i64 [[U1H]], [[U2]]370; CHECK-NEXT: [[U1LS:%.*]] = shl i64 [[U1]], 32371; CHECK-NEXT: [[T0L:%.*]] = and i64 [[T0]], 4294967295372; CHECK-NEXT: [[LO:%.*]] = or disjoint i64 [[T0L]], [[U1LS]]373; CHECK-NEXT: [[RES_LO:%.*]] = insertvalue { i64, i64 } undef, i64 [[LO]], 0374; CHECK-NEXT: [[RES:%.*]] = insertvalue { i64, i64 } [[RES_LO]], i64 [[HI]], 1375; CHECK-NEXT: ret { i64, i64 } [[RES]]376;377 %x = call i64 @get_number()378 %y = call i64 @get_number()379 380 %yl = and i64 %y, 4294967295381 %yh = lshr i64 %y, 32382 %xh = lshr i64 %x, 32383 %xl = and i64 %x, 4294967295384 385 %t3 = mul nuw i64 %xh, %yh386 %t2 = mul nuw i64 %xl, %yh387 %t1 = mul nuw i64 %xh, %yl388 %t0 = mul nuw i64 %xl, %yl389 390 %t0h = lshr i64 %t0, 32391 %u0 = add i64 %t1, %t0h392 %u0l = and i64 %u0, 4294967295393 %u1 = add i64 %t2, %u0l394 %u0h = lshr i64 %u0, 32395 %u2 = add i64 %u0h, %t3396 %u1h = lshr i64 %u1, 32397 %hi = add i64 %u1h, %u2398 399 %u1ls = shl i64 %u1, 32400 %t0l = and i64 %t0, 4294967295401 %lo = or i64 %t0l, %u1ls402 403 %res_lo = insertvalue { i64, i64 } undef, i64 %lo, 0404 %res = insertvalue { i64, i64 } %res_lo, i64 %hi, 1405 ret { i64, i64 } %res406}407 408 409define i64 @umulh_64(i64 %x, i64 %y) {410; CHECK-LABEL: @umulh_64(411; CHECK-NEXT: [[XL:%.*]] = and i64 [[X:%.*]], 4294967295412; CHECK-NEXT: [[XH:%.*]] = lshr i64 [[X]], 32413; CHECK-NEXT: [[YL:%.*]] = and i64 [[Y:%.*]], 4294967295414; CHECK-NEXT: [[YH:%.*]] = lshr i64 [[Y]], 32415; CHECK-NEXT: [[T0:%.*]] = mul nuw i64 [[YL]], [[XL]]416; CHECK-NEXT: [[T1:%.*]] = mul nuw i64 [[YL]], [[XH]]417; CHECK-NEXT: [[T2:%.*]] = mul nuw i64 [[YH]], [[XL]]418; CHECK-NEXT: [[T3:%.*]] = mul nuw i64 [[YH]], [[XH]]419; CHECK-NEXT: [[T0H:%.*]] = lshr i64 [[T0]], 32420; CHECK-NEXT: [[U0:%.*]] = add i64 [[T0H]], [[T1]]421; CHECK-NEXT: [[U0L:%.*]] = and i64 [[U0]], 4294967295422; CHECK-NEXT: [[U0H:%.*]] = lshr i64 [[U0]], 32423; CHECK-NEXT: [[U1:%.*]] = add i64 [[U0L]], [[T2]]424; CHECK-NEXT: [[U1H:%.*]] = lshr i64 [[U1]], 32425; CHECK-NEXT: [[U2:%.*]] = add i64 [[U0H]], [[T3]]426; CHECK-NEXT: [[HI:%.*]] = add i64 [[U2]], [[U1H]]427; CHECK-NEXT: ret i64 [[HI]]428;429 %xl = and i64 %x, 4294967295430 %xh = lshr i64 %x, 32431 %yl = and i64 %y, 4294967295432 %yh = lshr i64 %y, 32433 434 %t0 = mul nuw i64 %yl, %xl435 %t1 = mul nuw i64 %yl, %xh436 %t2 = mul nuw i64 %yh, %xl437 %t3 = mul nuw i64 %yh, %xh438 439 %t0h = lshr i64 %t0, 32440 441 %u0 = add i64 %t0h, %t1442 %u0l = and i64 %u0, 4294967295443 %u0h = lshr i64 %u0, 32444 445 %u1 = add i64 %u0l, %t2446 %u1h = lshr i64 %u1, 32447 448 %u2 = add i64 %u0h, %t3449 450 %hi = add i64 %u2, %u1h451 ret i64 %hi452}453 454; TODO: https://alive2.llvm.org/ce/z/y26zaW455define i64 @mullo(i64 %x, i64 %y) {456; CHECK-LABEL: @mullo(457; CHECK-NEXT: [[XL:%.*]] = and i64 [[X:%.*]], 4294967295458; CHECK-NEXT: [[XH:%.*]] = lshr i64 [[X]], 32459; CHECK-NEXT: [[YL:%.*]] = and i64 [[Y:%.*]], 4294967295460; CHECK-NEXT: [[YH:%.*]] = lshr i64 [[Y]], 32461; CHECK-NEXT: [[T0:%.*]] = mul nuw i64 [[YL]], [[XL]]462; CHECK-NEXT: [[T1:%.*]] = mul i64 [[Y]], [[XH]]463; CHECK-NEXT: [[T2:%.*]] = mul i64 [[YH]], [[X]]464; CHECK-NEXT: [[T0L:%.*]] = and i64 [[T0]], 4294967295465; CHECK-NEXT: [[T0H:%.*]] = lshr i64 [[T0]], 32466; CHECK-NEXT: [[U0:%.*]] = add i64 [[T0H]], [[T1]]467; CHECK-NEXT: [[U1:%.*]] = add i64 [[U0]], [[T2]]468; CHECK-NEXT: [[U1LS:%.*]] = shl i64 [[U1]], 32469; CHECK-NEXT: [[LO:%.*]] = or disjoint i64 [[U1LS]], [[T0L]]470; CHECK-NEXT: ret i64 [[LO]]471;472 %xl = and i64 %x, 4294967295473 %xh = lshr i64 %x, 32474 %yl = and i64 %y, 4294967295475 %yh = lshr i64 %y, 32476 477 %t0 = mul nuw i64 %yl, %xl478 %t1 = mul nuw i64 %yl, %xh479 %t2 = mul nuw i64 %yh, %xl480 481 %t0l = and i64 %t0, 4294967295482 %t0h = lshr i64 %t0, 32483 484 %u0 = add i64 %t0h, %t1485 %u0l = and i64 %u0, 4294967295486 487 %u1 = add i64 %u0l, %t2488 %u1ls = shl i64 %u1, 32489 490 %lo = or i64 %u1ls, %t0l491 ret i64 %lo492}493 494 495define i64 @mullo_variant3(i64 %a, i64 %b) {496; CHECK-LABEL: @mullo_variant3(497; CHECK-NEXT: [[LO:%.*]] = mul i64 [[A:%.*]], [[B:%.*]]498; CHECK-NEXT: ret i64 [[LO]]499;500 %al = and i64 %a, 4294967295501 %ah = lshr i64 %a, 32502 %bl = and i64 %b, 4294967295503 %bh = lshr i64 %b, 32504 505 %t0 = mul nuw i64 %bl, %al506 %t1 = mul nuw i64 %bl, %ah507 %t2 = mul nuw i64 %bh, %al508 509 %u1 = add i64 %t2, %t1510 %u1ls = shl i64 %u1, 32511 512 %lo = add i64 %u1ls, %t0513 ret i64 %lo514}515 516 517declare void @eat_i64(i64)518declare void @eat_i128(i128)519 520define i64 @mullo_duplicate(i64 %x, i64 %y) {521; CHECK-LABEL: @mullo_duplicate(522; CHECK-NEXT: [[DUPLICATED_MUL:%.*]] = mul i64 [[X:%.*]], [[Y:%.*]]523; CHECK-NEXT: call void @eat_i64(i64 [[DUPLICATED_MUL]])524; CHECK-NEXT: [[XL:%.*]] = and i64 [[X]], 4294967295525; CHECK-NEXT: [[XH:%.*]] = lshr i64 [[X]], 32526; CHECK-NEXT: [[YL:%.*]] = and i64 [[Y]], 4294967295527; CHECK-NEXT: [[YH:%.*]] = lshr i64 [[Y]], 32528; CHECK-NEXT: [[T0:%.*]] = mul nuw i64 [[YL]], [[XL]]529; CHECK-NEXT: [[T1:%.*]] = mul i64 [[Y]], [[XH]]530; CHECK-NEXT: [[T2:%.*]] = mul i64 [[YH]], [[X]]531; CHECK-NEXT: [[T0L:%.*]] = and i64 [[T0]], 4294967295532; CHECK-NEXT: [[T0H:%.*]] = lshr i64 [[T0]], 32533; CHECK-NEXT: [[U0:%.*]] = add i64 [[T0H]], [[T1]]534; CHECK-NEXT: [[U1:%.*]] = add i64 [[U0]], [[T2]]535; CHECK-NEXT: [[U1LS:%.*]] = shl i64 [[U1]], 32536; CHECK-NEXT: [[LO:%.*]] = or disjoint i64 [[U1LS]], [[T0L]]537; CHECK-NEXT: ret i64 [[LO]]538;539 %duplicated_mul = mul i64 %x, %y540 call void @eat_i64(i64 %duplicated_mul)541 542 %xl = and i64 %x, 4294967295543 %xh = lshr i64 %x, 32544 %yl = and i64 %y, 4294967295545 %yh = lshr i64 %y, 32546 547 %t0 = mul nuw i64 %yl, %xl548 %t1 = mul nuw i64 %yl, %xh549 %t2 = mul nuw i64 %yh, %xl550 551 %t0l = and i64 %t0, 4294967295552 %t0h = lshr i64 %t0, 32553 554 %u0 = add i64 %t0h, %t1555 %u0l = and i64 %u0, 4294967295556 557 %u1 = add i64 %u0l, %t2558 %u1ls = shl i64 %u1, 32559 560 %lo = or i64 %u1ls, %t0l561 ret i64 %lo562}563 564define { i64, i64 } @mul_full_64_duplicate(i64 %x, i64 %y) {565; CHECK-LABEL: @mul_full_64_duplicate(566; CHECK-NEXT: [[XX:%.*]] = zext i64 [[X:%.*]] to i128567; CHECK-NEXT: [[YY:%.*]] = zext i64 [[Y:%.*]] to i128568; CHECK-NEXT: [[DUPLICATED_MUL:%.*]] = mul nuw i128 [[XX]], [[YY]]569; CHECK-NEXT: call void @eat_i128(i128 [[DUPLICATED_MUL]])570; CHECK-NEXT: [[XL:%.*]] = and i64 [[X]], 4294967295571; CHECK-NEXT: [[XH:%.*]] = lshr i64 [[X]], 32572; CHECK-NEXT: [[YL:%.*]] = and i64 [[Y]], 4294967295573; CHECK-NEXT: [[YH:%.*]] = lshr i64 [[Y]], 32574; CHECK-NEXT: [[T0:%.*]] = mul nuw i64 [[YL]], [[XL]]575; CHECK-NEXT: [[T1:%.*]] = mul nuw i64 [[YL]], [[XH]]576; CHECK-NEXT: [[T2:%.*]] = mul nuw i64 [[YH]], [[XL]]577; CHECK-NEXT: [[T3:%.*]] = mul nuw i64 [[YH]], [[XH]]578; CHECK-NEXT: [[T0L:%.*]] = and i64 [[T0]], 4294967295579; CHECK-NEXT: [[T0H:%.*]] = lshr i64 [[T0]], 32580; CHECK-NEXT: [[U0:%.*]] = add i64 [[T0H]], [[T1]]581; CHECK-NEXT: [[U0L:%.*]] = and i64 [[U0]], 4294967295582; CHECK-NEXT: [[U0H:%.*]] = lshr i64 [[U0]], 32583; CHECK-NEXT: [[U1:%.*]] = add i64 [[U0L]], [[T2]]584; CHECK-NEXT: [[U1LS:%.*]] = shl i64 [[U1]], 32585; CHECK-NEXT: [[U1H:%.*]] = lshr i64 [[U1]], 32586; CHECK-NEXT: [[U2:%.*]] = add i64 [[U0H]], [[T3]]587; CHECK-NEXT: [[LO:%.*]] = or disjoint i64 [[U1LS]], [[T0L]]588; CHECK-NEXT: [[HI:%.*]] = add i64 [[U2]], [[U1H]]589; CHECK-NEXT: [[RES_LO:%.*]] = insertvalue { i64, i64 } undef, i64 [[LO]], 0590; CHECK-NEXT: [[RES:%.*]] = insertvalue { i64, i64 } [[RES_LO]], i64 [[HI]], 1591; CHECK-NEXT: ret { i64, i64 } [[RES]]592;593 %xx = zext i64 %x to i128594 %yy = zext i64 %y to i128595 %duplicated_mul = mul i128 %xx, %yy596 call void @eat_i128(i128 %duplicated_mul)597 598 %xl = and i64 %x, 4294967295599 %xh = lshr i64 %x, 32600 %yl = and i64 %y, 4294967295601 %yh = lshr i64 %y, 32602 603 %t0 = mul nuw i64 %yl, %xl604 %t1 = mul nuw i64 %yl, %xh605 %t2 = mul nuw i64 %yh, %xl606 %t3 = mul nuw i64 %yh, %xh607 608 %t0l = and i64 %t0, 4294967295609 %t0h = lshr i64 %t0, 32610 611 %u0 = add i64 %t0h, %t1612 %u0l = and i64 %u0, 4294967295613 %u0h = lshr i64 %u0, 32614 615 %u1 = add i64 %u0l, %t2616 %u1ls = shl i64 %u1, 32617 %u1h = lshr i64 %u1, 32618 619 %u2 = add i64 %u0h, %t3620 621 %lo = or i64 %u1ls, %t0l622 %hi = add i64 %u2, %u1h623 624 %res_lo = insertvalue { i64, i64 } undef, i64 %lo, 0625 %res = insertvalue { i64, i64 } %res_lo, i64 %hi, 1626 ret { i64, i64 } %res627}628 629 630define i64 @umulhi_64_v2() {631; CHECK-LABEL: @umulhi_64_v2(632; CHECK-NEXT: [[X:%.*]] = call i64 @get_number()633; CHECK-NEXT: [[Y:%.*]] = call i64 @get_number()634; CHECK-NEXT: [[YL:%.*]] = and i64 [[Y]], 4294967295635; CHECK-NEXT: [[YH:%.*]] = lshr i64 [[Y]], 32636; CHECK-NEXT: [[XH:%.*]] = lshr i64 [[X]], 32637; CHECK-NEXT: [[XL:%.*]] = and i64 [[X]], 4294967295638; CHECK-NEXT: [[T3:%.*]] = mul nuw i64 [[XH]], [[YH]]639; CHECK-NEXT: [[T2:%.*]] = mul nuw i64 [[XL]], [[YH]]640; CHECK-NEXT: [[T1:%.*]] = mul nuw i64 [[XH]], [[YL]]641; CHECK-NEXT: [[T0:%.*]] = mul nuw i64 [[XL]], [[YL]]642; CHECK-NEXT: [[T0H:%.*]] = lshr i64 [[T0]], 32643; CHECK-NEXT: [[U0:%.*]] = add i64 [[T1]], [[T0H]]644; CHECK-NEXT: [[U0L:%.*]] = and i64 [[U0]], 4294967295645; CHECK-NEXT: [[U1:%.*]] = add i64 [[T2]], [[U0L]]646; CHECK-NEXT: [[U0H:%.*]] = lshr i64 [[U0]], 32647; CHECK-NEXT: [[U2:%.*]] = add i64 [[U0H]], [[T3]]648; CHECK-NEXT: [[U1H:%.*]] = lshr i64 [[U1]], 32649; CHECK-NEXT: [[HI:%.*]] = add i64 [[U1H]], [[U2]]650; CHECK-NEXT: ret i64 [[HI]]651;652 %x = call i64 @get_number()653 %y = call i64 @get_number()654 655 %yl = and i64 %y, 4294967295656 %yh = lshr i64 %y, 32657 %xh = lshr i64 %x, 32658 %xl = and i64 %x, 4294967295659 660 %t3 = mul nuw i64 %xh, %yh661 %t2 = mul nuw i64 %xl, %yh662 %t1 = mul nuw i64 %xh, %yl663 %t0 = mul nuw i64 %xl, %yl664 665 %t0h = lshr i64 %t0, 32666 %u0 = add i64 %t1, %t0h667 %u0l = and i64 %u0, 4294967295668 %u1 = add i64 %t2, %u0l669 %u0h = lshr i64 %u0, 32670 %u2 = add i64 %u0h, %t3671 %u1h = lshr i64 %u1, 32672 %hi = add i64 %u1h, %u2673 674 ret i64 %hi675}676 677 678define i64 @umulhi_64_v3() {679; CHECK-LABEL: @umulhi_64_v3(680; CHECK-NEXT: [[X:%.*]] = call i64 @get_number()681; CHECK-NEXT: [[XH:%.*]] = lshr i64 [[X]], 32682; CHECK-NEXT: [[XL:%.*]] = and i64 [[X]], 4294967295683; CHECK-NEXT: [[Y:%.*]] = call i64 @get_number()684; CHECK-NEXT: [[YL:%.*]] = and i64 [[Y]], 4294967295685; CHECK-NEXT: [[YH:%.*]] = lshr i64 [[Y]], 32686; CHECK-NEXT: [[T3:%.*]] = mul nuw i64 [[XH]], [[YH]]687; CHECK-NEXT: [[T2:%.*]] = mul nuw i64 [[XL]], [[YH]]688; CHECK-NEXT: [[T1:%.*]] = mul nuw i64 [[XH]], [[YL]]689; CHECK-NEXT: [[T0:%.*]] = mul nuw i64 [[XL]], [[YL]]690; CHECK-NEXT: [[T0H:%.*]] = lshr i64 [[T0]], 32691; CHECK-NEXT: [[U0:%.*]] = add i64 [[T1]], [[T0H]]692; CHECK-NEXT: [[U0L:%.*]] = and i64 [[U0]], 4294967295693; CHECK-NEXT: [[U1:%.*]] = add i64 [[T2]], [[U0L]]694; CHECK-NEXT: [[U0H:%.*]] = lshr i64 [[U0]], 32695; CHECK-NEXT: [[U2:%.*]] = add i64 [[U0H]], [[T3]]696; CHECK-NEXT: [[U1H:%.*]] = lshr i64 [[U1]], 32697; CHECK-NEXT: [[HI:%.*]] = add i64 [[U1H]], [[U2]]698; CHECK-NEXT: ret i64 [[HI]]699;700 %x = call i64 @get_number()701 %xh = lshr i64 %x, 32702 %xl = and i64 %x, 4294967295703 704 %y = call i64 @get_number()705 %yl = and i64 %y, 4294967295706 %yh = lshr i64 %y, 32707 708 %t3 = mul nuw i64 %xh, %yh709 %t2 = mul nuw i64 %xl, %yh710 %t1 = mul nuw i64 %xh, %yl711 %t0 = mul nuw i64 %xl, %yl712 713 %t0h = lshr i64 %t0, 32714 %u0 = add i64 %t1, %t0h715 %u0l = and i64 %u0, 4294967295716 %u1 = add i64 %t2, %u0l717 %u0h = lshr i64 %u0, 32718 %u2 = add i64 %u0h, %t3719 %u1h = lshr i64 %u1, 32720 %hi = add i64 %u1h, %u2721 722 ret i64 %hi723}724