在进行除法乘法时，额外的移动是否更快？
Is an extra move somehow faster when doing division-by-multiplication?
考虑这个函数：
unsigned long f(unsigned long x) {
return x / 7;
}
使用 -O3，Clang turns the division into a multiplication，如预期：
f: # @f
movabs rcx, 2635249153387078803
mov rax, rdi
mul rcx
sub rdi, rdx
shr rdi
lea rax, [rdi + rdx]
shr rax, 2
ret
GCC 基本上做同样的事情，除了使用 rdx 而 Clang 使用 rcx。但他们似乎都在做额外的动作。为什么不是这个呢？
f:
movabs rax, 2635249153387078803
mul rdi
sub rdi, rdx
shr rdi
lea rax, [rdi + rdx]
shr rax, 2
ret
特别是，他们都将分子放在 rax 中，但是通过将幻数放在那里，您根本不需要移动分子。如果这真的更好，我很惊讶 GCC 和 Clang 都没有这样做，因为它感觉很明显。他们的方式实际上比我的方式更快，是否存在一些微架构原因？
您的版本没有看起来更快。
编辑： ROB（重新排序缓冲区）可以进行寄存器重命名，所以额外的 mov 实际上 没有 移动任何数据。它只能为生成的 uop 调整 PRF [物理寄存器文件] 中的索引。所以，mov可能被融合掉了。
我已经编写了你的两个 asm 版本：
这里是orig.s:
.file "orig.c"
.text
.p2align 4,,15
.globl orig
.type orig, @function
orig:
.LFB0:
.cfi_startproc
movabsq 35249153387078803, %rdx
movq %rdi, %rax
mulq %rdx
subq %rdx, %rdi
shrq %rdi
leaq (%rdx,%rdi), %rax
shrq , %rax
ret
.cfi_endproc
.LFE0:
.size orig, .-orig
.ident "GCC: (GNU) 8.3.1 20190223 (Red Hat 8.3.1-2)"
.section .note.GNU-stack,"",@progbits
并且，fix1.s：
.file "fix1.c"
.text
.p2align 4,,15
.globl fix1
.type fix1, @function
fix1:
.LFB0:
.cfi_startproc
movabsq 35249153387078803, %rax
mulq %rdi
subq %rdx, %rdi
shrq %rdi
leaq (%rdx,%rdi), %rax
shrq , %rax
ret
.cfi_endproc
.LFE0:
.size fix1, .-fix1
.ident "GCC: (GNU) 8.3.1 20190223 (Red Hat 8.3.1-2)"
.section .note.GNU-stack,"",@progbits
这是一个测试程序，main.c。 （您可能需要在 test 中改变迭代常数）：
#include <stdio.h>
#include <time.h>
typedef unsigned long ulong;
ulong orig(ulong);
ulong fix1(ulong);
typedef ulong (*fnc_p)(ulong);
typedef long long tsc_t;
static inline tsc_t
tscget(void)
{
struct timespec ts;
tsc_t tsc;
clock_gettime(CLOCK_MONOTONIC,&ts);
tsc = ts.tv_sec;
tsc *= 1000000000;
tsc += ts.tv_nsec;
return tsc;
}
tsc_t
test(fnc_p fnc)
{
tsc_t beg;
tsc_t end;
ulong tot = 0;
beg = tscget();
for (ulong cnt = 10000000; cnt > 0; --cnt)
tot += fnc(cnt);
end = tscget();
end -= beg;
return end;
}
int
main(void)
{
tsc_t odif = test(orig);
tsc_t fdif = test(fix1);
printf("odif=%lld fdif=%lld (%lld)\n",odif,fdif,odif - fdif);
return 0;
}
构建：
gcc -O3 -o main main.c orig.s fix1.s
以下是 20 次运行的测试结果：
odif=43937784 fdif=34104334 (9833450)
odif=39791246 fdif=42641752 (-2850506)
odif=25818191 fdif=25586750 (231441)
odif=35056015 fdif=25276729 (9779286)
odif=43955175 fdif=31112246 (12842929)
odif=25731472 fdif=25493826 (237646)
odif=25627395 fdif=26202191 (-574796)
odif=28029957 fdif=25627366 (2402591)
odif=25828608 fdif=26291294 (-462686)
odif=25690703 fdif=25703610 (-12907)
odif=25908418 fdif=26411828 (-503410)
odif=25690776 fdif=25673766 (17010)
odif=25992890 fdif=25982718 (10172)
odif=25693459 fdif=25636974 (56485)
odif=26572724 fdif=25870050 (702674)
odif=25627334 fdif=25621802 (5532)
odif=27760054 fdif=27382748 (377306)
odif=26343245 fdif=26195134 (148111)
odif=27289865 fdif=25840818 (1449047)
odif=25985794 fdif=25721351 (264443)
更新：
Your data doesn't appear to support your conclusion, unless I'm misinterpreting something.
正如我所说，您可能需要改变迭代次数（向上或向下）。或者，进行多次运行并采用最小值。但是，否则，我希望每行的最终数字或多或少是正的或负的不变的，而不是摆动+/-。可能很难衡量，没有更好的测试
您应该注意到现代 x86 模型（例如 Sandy Bridge 或更高版本）会执行 大规模 超标量和指令重新排序，以及融合微指令，所以我不会指望直译。例如，参见：https://www.realworldtech.com/sandy-bridge/
这是一个更好的（？）版本，但它仍然显示 相同 的东西。即，有时 original 更快，有时 "improved" 更快
#include <stdio.h>
#include <time.h>
typedef unsigned long ulong;
ulong orig(ulong);
ulong fix1(ulong);
typedef ulong (*fnc_p)(ulong);
typedef long long tsc_t;
typedef struct {
tsc_t orig;
tsc_t fix1;
} bnc_t;
#define BNCMAX 100
bnc_t bnclist[BNCMAX];
static inline tsc_t
tscget(void)
{
struct timespec ts;
tsc_t tsc;
clock_gettime(CLOCK_MONOTONIC,&ts);
tsc = ts.tv_sec;
tsc *= 1000000000;
tsc += ts.tv_nsec;
return tsc;
}
tsc_t
test(fnc_p fnc)
{
tsc_t beg;
tsc_t end;
ulong tot = 0;
beg = tscget();
for (ulong cnt = 10000000; cnt > 0; --cnt)
tot += fnc(cnt);
end = tscget();
end -= beg;
return end;
}
void
run(bnc_t *bnc)
{
tsc_t odif = test(orig);
tsc_t fdif = test(fix1);
bnc->orig = odif;
bnc->fix1 = fdif;
}
int
main(void)
{
bnc_t *bnc;
for (int pass = 0; pass < BNCMAX; ++pass) {
bnc = &bnclist[pass];
run(bnc);
}
for (int pass = 0; pass < BNCMAX; ++pass) {
bnc = &bnclist[pass];
printf("orig=%lld fix1=%lld (%lld)\n",
bnc->orig,bnc->fix1,bnc->orig - bnc->fix1);
}
return 0;
}
并且，这是输出（没有实际变化）：
orig=31588215 fix1=26821473 (4766742)
orig=25748732 fix1=25917183 (-168451)
orig=25805426 fix1=25635759 (169667)
orig=25479642 fix1=26037620 (-557978)
orig=26668860 fix1=25959444 (709416)
orig=26047616 fix1=25540493 (507123)
orig=25772292 fix1=25460041 (312251)
orig=25709852 fix1=26172701 (-462849)
orig=26124151 fix1=25766472 (357679)
orig=25539018 fix1=26845018 (-1306000)
orig=26884105 fix1=26869566 (14539)
orig=26184938 fix1=27826408 (-1641470)
orig=25841934 fix1=25482603 (359331)
orig=25509107 fix1=25436511 (72596)
orig=25448812 fix1=25473302 (-24490)
orig=25433894 fix1=25812646 (-378752)
orig=25868190 fix1=26180032 (-311842)
orig=25451573 fix1=25503657 (-52084)
orig=25393540 fix1=25484952 (-91412)
orig=26032526 fix1=26825219 (-792693)
orig=25859126 fix1=25529430 (329696)
orig=25692214 fix1=25431668 (260546)
orig=25463849 fix1=25370236 (93613)
orig=25650185 fix1=25401441 (248744)
orig=25702951 fix1=26858126 (-1155175)
orig=26187072 fix1=25800102 (386970)
orig=26493916 fix1=25591639 (902277)
orig=26456983 fix1=25724181 (732802)
orig=25842746 fix1=26119019 (-276273)
orig=26654148 fix1=29452577 (-2798429)
orig=27936505 fix1=28494045 (-557540)
orig=30067162 fix1=27029523 (3037639)
orig=25785637 fix1=25856415 (-70778)
orig=25521760 fix1=25286859 (234901)
orig=25433035 fix1=25626380 (-193345)
orig=25373358 fix1=25541615 (-168257)
orig=25846496 fix1=25446494 (400002)
orig=25368198 fix1=25321934 (46264)
orig=25615453 fix1=28574223 (-2958770)
orig=26660896 fix1=25508745 (1152151)
orig=25891979 fix1=25546436 (345543)
orig=25296369 fix1=25382779 (-86410)
orig=25438794 fix1=25372736 (66058)
orig=25531652 fix1=25498422 (33230)
orig=25977272 fix1=25456931 (520341)
orig=25336327 fix1=25423638 (-87311)
orig=26037148 fix1=25313703 (723445)
orig=25314995 fix1=25538181 (-223186)
orig=26638367 fix1=26446762 (191605)
orig=25915537 fix1=25633327 (282210)
orig=25409105 fix1=25287069 (122036)
orig=25633931 fix1=26423463 (-789532)
orig=26074523 fix1=26524398 (-449875)
orig=25602157 fix1=25580893 (21264)
orig=25490481 fix1=25557287 (-66806)
orig=25666843 fix1=25496179 (170664)
orig=26573635 fix1=25796737 (776898)
orig=26133811 fix1=26226840 (-93029)
orig=28262664 fix1=26022265 (2240399)
orig=25336820 fix1=25683095 (-346275)
orig=25899602 fix1=25660778 (238824)
orig=25440453 fix1=25630320 (-189867)
orig=25356601 fix1=25422670 (-66069)
orig=25419887 fix1=25611533 (-191646)
orig=25766460 fix1=25596927 (169533)
orig=25619510 fix1=25449303 (170207)
orig=25359373 fix1=25380306 (-20933)
orig=25474687 fix1=27194210 (-1719523)
orig=26389253 fix1=26709738 (-320485)
orig=26132999 fix1=25671907 (461092)
orig=25416724 fix1=25540911 (-124187)
orig=25440277 fix1=25364387 (75890)
orig=25704885 fix1=25661456 (43429)
orig=25544376 fix1=25380520 (163856)
orig=25340926 fix1=25956342 (-615416)
orig=25383668 fix1=25397807 (-14139)
orig=25636178 fix1=25769479 (-133301)
orig=26237022 fix1=29897502 (-3660480)
orig=28235814 fix1=25475574 (2760240)
orig=25457466 fix1=25450557 (6909)
orig=25775658 fix1=25802380 (-26722)
orig=27577521 fix1=25444772 (2132749)
orig=25380927 fix1=25409250 (-28323)
orig=25417872 fix1=25336530 (81342)
orig=25995656 fix1=26338512 (-342856)
orig=25553088 fix1=25334495 (218593)
orig=25416197 fix1=25521031 (-104834)
orig=29150160 fix1=25717390 (3432770)
orig=26026892 fix1=26916678 (-889786)
orig=25694048 fix1=25496660 (197388)
orig=25576011 fix1=25676045 (-100034)
orig=25461907 fix1=25462593 (-686)
orig=25736879 fix1=27349093 (-1612214)
orig=25687558 fix1=25829963 (-142405)
orig=25492417 fix1=25752421 (-260004)
orig=25559702 fix1=25423874 (135828)
orig=25799145 fix1=28961932 (-3162787)
orig=25912111 fix1=26018163 (-106052)
orig=25725927 fix1=25794091 (-68164)
orig=25528795 fix1=25855893 (-327098)
更新#2：
这是我最新的测试版本：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef unsigned long ulong;
ulong orig(ulong);
ulong fix1(ulong);
typedef ulong (*fnc_p)(ulong);
typedef long long tsc_t;
typedef struct {
tsc_t dif;
ulong tot;
} test_t;
typedef struct {
test_t orig;
test_t fix1;
} bnc_t;
#define BNCMAX 100
bnc_t bnclist[BNCMAX];
ulong itermax;
static inline tsc_t
tscget(void)
{
struct timespec ts;
tsc_t tsc;
clock_gettime(CLOCK_MONOTONIC,&ts);
tsc = ts.tv_sec;
tsc *= 1000000000;
tsc += ts.tv_nsec;
return tsc;
}
tsc_t
test(test_t *tst,fnc_p fnc)
{
tsc_t beg;
tsc_t end;
ulong tot = 0;
beg = tscget();
for (ulong cnt = itermax; cnt > 0; --cnt)
tot += fnc(cnt);
end = tscget();
end -= beg;
tst->dif = end;
tst->tot = tot;
return end;
}
void
run(bnc_t *bnc)
{
tsc_t odif = test(&bnc->orig,orig);
tsc_t fdif = test(&bnc->fix1,fix1);
}
int
main(int argc,char **argv)
{
bnc_t *bnc;
test_t bestorig;
test_t bestfix1;
--argc;
++argv;
if (argc > 0)
itermax = atoll(*argv);
else
itermax = 10000000;
for (int pass = 0; pass < BNCMAX; ++pass) {
bnc = &bnclist[pass];
run(bnc);
}
bnc = &bnclist[0];
bestorig = bnc->orig;
bestfix1 = bnc->orig;
for (int pass = 0; pass < BNCMAX; ++pass) {
bnc = &bnclist[pass];
printf("orig=%lld fix1=%lld (%lld)\n",
bnc->orig.dif,bnc->fix1.dif,bnc->orig.dif - bnc->fix1.dif);
if (bnc->orig.tot != bnc->fix1.tot)
printf("FAIL: orig=%ld fix1=%ld\n",bnc->orig.tot,bnc->fix1.tot);
if (bnc->orig.dif < bestorig.dif)
bestorig = bnc->orig;
if (bnc->fix1.dif < bestfix1.dif)
bestfix1 = bnc->fix1;
}
printf("\n");
printf("itermax=%ld\n",itermax);
printf("orig=%lld\n",bestorig.dif);
printf("fix1=%lld\n",bestfix1.dif);
return 0;
}
Visual Studio 2015 生成你期望的代码，rcx = input dividend:
mov rax, 2635249153387078803
mul rcx
sub rcx, rdx
shr rcx, 1
lea rax, QWORD PTR [rdx+rcx]
shr rax, 2
7 的除数需要 65 位乘法器才能获得适当的精度。
floor((2^(64+ceil(log2(7))))/7)+1 = floor((2^67)/7)+1 = 21081993227096630419
删除最高有效位 2^64，结果为 21081993227096630419 - 2^64 = 2635249153387078803，这是代码中实际使用的乘数。
生成的代码补偿了缺失的 2^64 位，此 pdf 文件中的图 4.1 和等式 4.5 对此进行了解释：
https://gmplib.org/~tege/divcnst-pldi94.pdf
进一步的解释可以在之前的回答中看到：
Why does GCC use multiplication by a strange number in implementing integer division?
如果 65 位乘法器尾随 0 位，则可以将其右移 1 位得到 64 位乘法器，从而减少指令数。例如，如果除以 5：
floor((2^(64+ceil(log2(5))))/5)+1 = floor((2^67)/5)+1 = 29514790517935282586
29514790517935282586 >> 1 = 14757395258967641293
mov rax, -3689348814741910323 ; == 14757395258967641293 == 0cccccccccccccccdH
mul rcx
shr rdx, 2
mov rax, rdx
这看起来很像是 gcc 和 clang 都错过了优化；额外的移动没有任何好处。
如果尚未报告，GCC 和 LLVM 都接受错过优化错误报告：https://bugs.llvm.org/ and https://gcc.gnu.org/bugzilla/。对于 GCC，甚至还有一个错误标记 "missed-optimization".
不幸的是，浪费的 mov 指令并不少见，尤其是在查看输入/输出 reg 被确定为调用约定而不是寄存器分配器的微小函数时。有时 do 仍然会在循环中发生，比如每次迭代都做一堆额外的工作，所以对于在循环后运行一次的代码来说，一切都在正确的位置。 /facepalm.
零延迟mov（mov-elimination）有助于降低此类错过优化的成本（以及无法避免mov的情况），但它仍然需要前端uop所以它几乎更糟。 （除非偶然，它有助于稍后对齐某些东西，但如果这是原因，那么 nop 也一样好）。
并且它在 ROB 中占据 space，减少无序执行程序可以看到缓存未命中或其他停顿的时间。 mov 从来都不是真正免费的，只是消除了执行单元和延迟部分 -
我对编译器内部结构的总猜测：
可能 gcc/clang 的内部机制需要了解这种除法模式是可交换的，可以将输入值放在其他寄存器中并将常量放入 RAX。
在一个循环中，他们想要其他寄存器中的常量，以便他们可以重用它，但希望编译器仍然可以在有用的情况下找出它。
考虑这个函数：
unsigned long f(unsigned long x) {
return x / 7;
}
使用 -O3，Clang turns the division into a multiplication，如预期：
f: # @f
movabs rcx, 2635249153387078803
mov rax, rdi
mul rcx
sub rdi, rdx
shr rdi
lea rax, [rdi + rdx]
shr rax, 2
ret
GCC 基本上做同样的事情，除了使用 rdx 而 Clang 使用 rcx。但他们似乎都在做额外的动作。为什么不是这个呢？
f:
movabs rax, 2635249153387078803
mul rdi
sub rdi, rdx
shr rdi
lea rax, [rdi + rdx]
shr rax, 2
ret
特别是，他们都将分子放在 rax 中，但是通过将幻数放在那里，您根本不需要移动分子。如果这真的更好，我很惊讶 GCC 和 Clang 都没有这样做，因为它感觉很明显。他们的方式实际上比我的方式更快，是否存在一些微架构原因？
您的版本没有看起来更快。
编辑： ROB（重新排序缓冲区）可以进行寄存器重命名，所以额外的 mov 实际上 没有 移动任何数据。它只能为生成的 uop 调整 PRF [物理寄存器文件] 中的索引。所以，mov可能被融合掉了。
我已经编写了你的两个 asm 版本：
这里是orig.s:
.file "orig.c"
.text
.p2align 4,,15
.globl orig
.type orig, @function
orig:
.LFB0:
.cfi_startproc
movabsq 35249153387078803, %rdx
movq %rdi, %rax
mulq %rdx
subq %rdx, %rdi
shrq %rdi
leaq (%rdx,%rdi), %rax
shrq , %rax
ret
.cfi_endproc
.LFE0:
.size orig, .-orig
.ident "GCC: (GNU) 8.3.1 20190223 (Red Hat 8.3.1-2)"
.section .note.GNU-stack,"",@progbits
并且，fix1.s：
.file "fix1.c"
.text
.p2align 4,,15
.globl fix1
.type fix1, @function
fix1:
.LFB0:
.cfi_startproc
movabsq 35249153387078803, %rax
mulq %rdi
subq %rdx, %rdi
shrq %rdi
leaq (%rdx,%rdi), %rax
shrq , %rax
ret
.cfi_endproc
.LFE0:
.size fix1, .-fix1
.ident "GCC: (GNU) 8.3.1 20190223 (Red Hat 8.3.1-2)"
.section .note.GNU-stack,"",@progbits
这是一个测试程序，main.c。 （您可能需要在 test 中改变迭代常数）：
#include <stdio.h>
#include <time.h>
typedef unsigned long ulong;
ulong orig(ulong);
ulong fix1(ulong);
typedef ulong (*fnc_p)(ulong);
typedef long long tsc_t;
static inline tsc_t
tscget(void)
{
struct timespec ts;
tsc_t tsc;
clock_gettime(CLOCK_MONOTONIC,&ts);
tsc = ts.tv_sec;
tsc *= 1000000000;
tsc += ts.tv_nsec;
return tsc;
}
tsc_t
test(fnc_p fnc)
{
tsc_t beg;
tsc_t end;
ulong tot = 0;
beg = tscget();
for (ulong cnt = 10000000; cnt > 0; --cnt)
tot += fnc(cnt);
end = tscget();
end -= beg;
return end;
}
int
main(void)
{
tsc_t odif = test(orig);
tsc_t fdif = test(fix1);
printf("odif=%lld fdif=%lld (%lld)\n",odif,fdif,odif - fdif);
return 0;
}
构建：
gcc -O3 -o main main.c orig.s fix1.s
以下是 20 次运行的测试结果：
odif=43937784 fdif=34104334 (9833450)
odif=39791246 fdif=42641752 (-2850506)
odif=25818191 fdif=25586750 (231441)
odif=35056015 fdif=25276729 (9779286)
odif=43955175 fdif=31112246 (12842929)
odif=25731472 fdif=25493826 (237646)
odif=25627395 fdif=26202191 (-574796)
odif=28029957 fdif=25627366 (2402591)
odif=25828608 fdif=26291294 (-462686)
odif=25690703 fdif=25703610 (-12907)
odif=25908418 fdif=26411828 (-503410)
odif=25690776 fdif=25673766 (17010)
odif=25992890 fdif=25982718 (10172)
odif=25693459 fdif=25636974 (56485)
odif=26572724 fdif=25870050 (702674)
odif=25627334 fdif=25621802 (5532)
odif=27760054 fdif=27382748 (377306)
odif=26343245 fdif=26195134 (148111)
odif=27289865 fdif=25840818 (1449047)
odif=25985794 fdif=25721351 (264443)
更新：
Your data doesn't appear to support your conclusion, unless I'm misinterpreting something.
正如我所说，您可能需要改变迭代次数（向上或向下）。或者，进行多次运行并采用最小值。但是，否则，我希望每行的最终数字或多或少是正的或负的不变的，而不是摆动+/-。可能很难衡量，没有更好的测试
您应该注意到现代 x86 模型（例如 Sandy Bridge 或更高版本）会执行 大规模 超标量和指令重新排序，以及融合微指令，所以我不会指望直译。例如，参见：https://www.realworldtech.com/sandy-bridge/
这是一个更好的（？）版本，但它仍然显示 相同 的东西。即，有时 original 更快，有时 "improved" 更快
#include <stdio.h>
#include <time.h>
typedef unsigned long ulong;
ulong orig(ulong);
ulong fix1(ulong);
typedef ulong (*fnc_p)(ulong);
typedef long long tsc_t;
typedef struct {
tsc_t orig;
tsc_t fix1;
} bnc_t;
#define BNCMAX 100
bnc_t bnclist[BNCMAX];
static inline tsc_t
tscget(void)
{
struct timespec ts;
tsc_t tsc;
clock_gettime(CLOCK_MONOTONIC,&ts);
tsc = ts.tv_sec;
tsc *= 1000000000;
tsc += ts.tv_nsec;
return tsc;
}
tsc_t
test(fnc_p fnc)
{
tsc_t beg;
tsc_t end;
ulong tot = 0;
beg = tscget();
for (ulong cnt = 10000000; cnt > 0; --cnt)
tot += fnc(cnt);
end = tscget();
end -= beg;
return end;
}
void
run(bnc_t *bnc)
{
tsc_t odif = test(orig);
tsc_t fdif = test(fix1);
bnc->orig = odif;
bnc->fix1 = fdif;
}
int
main(void)
{
bnc_t *bnc;
for (int pass = 0; pass < BNCMAX; ++pass) {
bnc = &bnclist[pass];
run(bnc);
}
for (int pass = 0; pass < BNCMAX; ++pass) {
bnc = &bnclist[pass];
printf("orig=%lld fix1=%lld (%lld)\n",
bnc->orig,bnc->fix1,bnc->orig - bnc->fix1);
}
return 0;
}
并且，这是输出（没有实际变化）：
orig=31588215 fix1=26821473 (4766742)
orig=25748732 fix1=25917183 (-168451)
orig=25805426 fix1=25635759 (169667)
orig=25479642 fix1=26037620 (-557978)
orig=26668860 fix1=25959444 (709416)
orig=26047616 fix1=25540493 (507123)
orig=25772292 fix1=25460041 (312251)
orig=25709852 fix1=26172701 (-462849)
orig=26124151 fix1=25766472 (357679)
orig=25539018 fix1=26845018 (-1306000)
orig=26884105 fix1=26869566 (14539)
orig=26184938 fix1=27826408 (-1641470)
orig=25841934 fix1=25482603 (359331)
orig=25509107 fix1=25436511 (72596)
orig=25448812 fix1=25473302 (-24490)
orig=25433894 fix1=25812646 (-378752)
orig=25868190 fix1=26180032 (-311842)
orig=25451573 fix1=25503657 (-52084)
orig=25393540 fix1=25484952 (-91412)
orig=26032526 fix1=26825219 (-792693)
orig=25859126 fix1=25529430 (329696)
orig=25692214 fix1=25431668 (260546)
orig=25463849 fix1=25370236 (93613)
orig=25650185 fix1=25401441 (248744)
orig=25702951 fix1=26858126 (-1155175)
orig=26187072 fix1=25800102 (386970)
orig=26493916 fix1=25591639 (902277)
orig=26456983 fix1=25724181 (732802)
orig=25842746 fix1=26119019 (-276273)
orig=26654148 fix1=29452577 (-2798429)
orig=27936505 fix1=28494045 (-557540)
orig=30067162 fix1=27029523 (3037639)
orig=25785637 fix1=25856415 (-70778)
orig=25521760 fix1=25286859 (234901)
orig=25433035 fix1=25626380 (-193345)
orig=25373358 fix1=25541615 (-168257)
orig=25846496 fix1=25446494 (400002)
orig=25368198 fix1=25321934 (46264)
orig=25615453 fix1=28574223 (-2958770)
orig=26660896 fix1=25508745 (1152151)
orig=25891979 fix1=25546436 (345543)
orig=25296369 fix1=25382779 (-86410)
orig=25438794 fix1=25372736 (66058)
orig=25531652 fix1=25498422 (33230)
orig=25977272 fix1=25456931 (520341)
orig=25336327 fix1=25423638 (-87311)
orig=26037148 fix1=25313703 (723445)
orig=25314995 fix1=25538181 (-223186)
orig=26638367 fix1=26446762 (191605)
orig=25915537 fix1=25633327 (282210)
orig=25409105 fix1=25287069 (122036)
orig=25633931 fix1=26423463 (-789532)
orig=26074523 fix1=26524398 (-449875)
orig=25602157 fix1=25580893 (21264)
orig=25490481 fix1=25557287 (-66806)
orig=25666843 fix1=25496179 (170664)
orig=26573635 fix1=25796737 (776898)
orig=26133811 fix1=26226840 (-93029)
orig=28262664 fix1=26022265 (2240399)
orig=25336820 fix1=25683095 (-346275)
orig=25899602 fix1=25660778 (238824)
orig=25440453 fix1=25630320 (-189867)
orig=25356601 fix1=25422670 (-66069)
orig=25419887 fix1=25611533 (-191646)
orig=25766460 fix1=25596927 (169533)
orig=25619510 fix1=25449303 (170207)
orig=25359373 fix1=25380306 (-20933)
orig=25474687 fix1=27194210 (-1719523)
orig=26389253 fix1=26709738 (-320485)
orig=26132999 fix1=25671907 (461092)
orig=25416724 fix1=25540911 (-124187)
orig=25440277 fix1=25364387 (75890)
orig=25704885 fix1=25661456 (43429)
orig=25544376 fix1=25380520 (163856)
orig=25340926 fix1=25956342 (-615416)
orig=25383668 fix1=25397807 (-14139)
orig=25636178 fix1=25769479 (-133301)
orig=26237022 fix1=29897502 (-3660480)
orig=28235814 fix1=25475574 (2760240)
orig=25457466 fix1=25450557 (6909)
orig=25775658 fix1=25802380 (-26722)
orig=27577521 fix1=25444772 (2132749)
orig=25380927 fix1=25409250 (-28323)
orig=25417872 fix1=25336530 (81342)
orig=25995656 fix1=26338512 (-342856)
orig=25553088 fix1=25334495 (218593)
orig=25416197 fix1=25521031 (-104834)
orig=29150160 fix1=25717390 (3432770)
orig=26026892 fix1=26916678 (-889786)
orig=25694048 fix1=25496660 (197388)
orig=25576011 fix1=25676045 (-100034)
orig=25461907 fix1=25462593 (-686)
orig=25736879 fix1=27349093 (-1612214)
orig=25687558 fix1=25829963 (-142405)
orig=25492417 fix1=25752421 (-260004)
orig=25559702 fix1=25423874 (135828)
orig=25799145 fix1=28961932 (-3162787)
orig=25912111 fix1=26018163 (-106052)
orig=25725927 fix1=25794091 (-68164)
orig=25528795 fix1=25855893 (-327098)
更新#2：
这是我最新的测试版本：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef unsigned long ulong;
ulong orig(ulong);
ulong fix1(ulong);
typedef ulong (*fnc_p)(ulong);
typedef long long tsc_t;
typedef struct {
tsc_t dif;
ulong tot;
} test_t;
typedef struct {
test_t orig;
test_t fix1;
} bnc_t;
#define BNCMAX 100
bnc_t bnclist[BNCMAX];
ulong itermax;
static inline tsc_t
tscget(void)
{
struct timespec ts;
tsc_t tsc;
clock_gettime(CLOCK_MONOTONIC,&ts);
tsc = ts.tv_sec;
tsc *= 1000000000;
tsc += ts.tv_nsec;
return tsc;
}
tsc_t
test(test_t *tst,fnc_p fnc)
{
tsc_t beg;
tsc_t end;
ulong tot = 0;
beg = tscget();
for (ulong cnt = itermax; cnt > 0; --cnt)
tot += fnc(cnt);
end = tscget();
end -= beg;
tst->dif = end;
tst->tot = tot;
return end;
}
void
run(bnc_t *bnc)
{
tsc_t odif = test(&bnc->orig,orig);
tsc_t fdif = test(&bnc->fix1,fix1);
}
int
main(int argc,char **argv)
{
bnc_t *bnc;
test_t bestorig;
test_t bestfix1;
--argc;
++argv;
if (argc > 0)
itermax = atoll(*argv);
else
itermax = 10000000;
for (int pass = 0; pass < BNCMAX; ++pass) {
bnc = &bnclist[pass];
run(bnc);
}
bnc = &bnclist[0];
bestorig = bnc->orig;
bestfix1 = bnc->orig;
for (int pass = 0; pass < BNCMAX; ++pass) {
bnc = &bnclist[pass];
printf("orig=%lld fix1=%lld (%lld)\n",
bnc->orig.dif,bnc->fix1.dif,bnc->orig.dif - bnc->fix1.dif);
if (bnc->orig.tot != bnc->fix1.tot)
printf("FAIL: orig=%ld fix1=%ld\n",bnc->orig.tot,bnc->fix1.tot);
if (bnc->orig.dif < bestorig.dif)
bestorig = bnc->orig;
if (bnc->fix1.dif < bestfix1.dif)
bestfix1 = bnc->fix1;
}
printf("\n");
printf("itermax=%ld\n",itermax);
printf("orig=%lld\n",bestorig.dif);
printf("fix1=%lld\n",bestfix1.dif);
return 0;
}
Visual Studio 2015 生成你期望的代码，rcx = input dividend:
mov rax, 2635249153387078803
mul rcx
sub rcx, rdx
shr rcx, 1
lea rax, QWORD PTR [rdx+rcx]
shr rax, 2
7 的除数需要 65 位乘法器才能获得适当的精度。
floor((2^(64+ceil(log2(7))))/7)+1 = floor((2^67)/7)+1 = 21081993227096630419
删除最高有效位 2^64，结果为 21081993227096630419 - 2^64 = 2635249153387078803，这是代码中实际使用的乘数。
生成的代码补偿了缺失的 2^64 位，此 pdf 文件中的图 4.1 和等式 4.5 对此进行了解释：
https://gmplib.org/~tege/divcnst-pldi94.pdf
进一步的解释可以在之前的回答中看到：
Why does GCC use multiplication by a strange number in implementing integer division?
如果 65 位乘法器尾随 0 位，则可以将其右移 1 位得到 64 位乘法器，从而减少指令数。例如，如果除以 5：
floor((2^(64+ceil(log2(5))))/5)+1 = floor((2^67)/5)+1 = 29514790517935282586
29514790517935282586 >> 1 = 14757395258967641293
mov rax, -3689348814741910323 ; == 14757395258967641293 == 0cccccccccccccccdH
mul rcx
shr rdx, 2
mov rax, rdx
这看起来很像是 gcc 和 clang 都错过了优化；额外的移动没有任何好处。
如果尚未报告，GCC 和 LLVM 都接受错过优化错误报告：https://bugs.llvm.org/ and https://gcc.gnu.org/bugzilla/。对于 GCC，甚至还有一个错误标记 "missed-optimization".
不幸的是，
浪费的 mov 指令并不少见，尤其是在查看输入/输出 reg 被确定为调用约定而不是寄存器分配器的微小函数时。有时 do 仍然会在循环中发生，比如每次迭代都做一堆额外的工作，所以对于在循环后运行一次的代码来说，一切都在正确的位置。 /facepalm.
零延迟mov（mov-elimination）有助于降低此类错过优化的成本（以及无法避免mov的情况），但它仍然需要前端uop所以它几乎更糟。 （除非偶然，它有助于稍后对齐某些东西，但如果这是原因，那么 nop 也一样好）。
并且它在 ROB 中占据 space，减少无序执行程序可以看到缓存未命中或其他停顿的时间。 mov 从来都不是真正免费的，只是消除了执行单元和延迟部分 -
我对编译器内部结构的总猜测：
可能 gcc/clang 的内部机制需要了解这种除法模式是可交换的，可以将输入值放在其他寄存器中并将常量放入 RAX。
在一个循环中，他们想要其他寄存器中的常量，以便他们可以重用它，但希望编译器仍然可以在有用的情况下找出它。