为什么 ARM gcc 在除以常数时调用 __udivsi3？
Why is ARM gcc calling __udivsi3 when dividing by a constant?
我正在使用最新可用版本的 ARM 封装 GCC：
arm-none-eabi-gcc（GNU Arm 嵌入式工具链 10-2020-q4-major）10.2.1 20201103（发布）
版权所有 (C) 2020 Free Software Foundation, Inc.
当我使用“-mcpu=cortex-m0 -mthumb -Ofast”编译此代码时：
int main(void) {
uint16_t num = (uint16_t) ADC1->DR;
ADC1->DR = num / 7;
}
我希望除法可以通过乘法和移位来完成，但生成的是这段代码：
08000b5c <main>:
8000b5c: b510 push {r4, lr}
8000b5e: 4c05 ldr r4, [pc, #20] ; (8000b74 <main+0x18>)
8000b60: 2107 movs r1, #7
8000b62: 6c20 ldr r0, [r4, #64] ; 0x40
8000b64: b280 uxth r0, r0
8000b66: f7ff facf bl 8000108 <__udivsi3>
8000b6a: b280 uxth r0, r0
8000b6c: 6420 str r0, [r4, #64] ; 0x40
8000b6e: 2000 movs r0, #0
8000b70: bd10 pop {r4, pc}
8000b72: 46c0 nop ; (mov r8, r8)
8000b74: 40012400 .word 0x40012400
使用__udivsi3代替乘法和移位是非常低效的。我是否使用了错误的标志，或者遗漏了其他东西，或者这是一个 GCC 错误？
编译器只有在知道结果对于语言允许的任何输入都是正确的情况下才能重新排列整数表达式。
因为7和2互质，所以任何输入都不能用乘法和移位来除以7。
如果您知道您打算提供的输入是可能的，那么您必须自己使用乘法和移位运算符来完成。
根据输入的大小，您必须选择要移动多少，以便输出正确（或至少对您的应用程序足够好）并且中间不会溢出。编译器无法知道什么对您的应用程序足够准确，或者您的最大输入是多少。如果它允许任何输入达到该类型的最大值，那么每次乘法都会溢出。
一般来说，如果除数不是 2 的互质，即如果它是 2 的幂，GCC 只会使用移位进行除法。
Cortex-M0 缺少执行 32x32->64 位乘法的指令。因为 num 是一个无符号的 16 位数量，所以将它乘以 9363 并右移 16 将在所有情况下产生正确的结果，但是——可能是因为 uint16_t 将被提升为 int 在乘法之前，gcc 不包括此类优化。
根据我的观察，gcc 在针对 Cortex-M0 的优化方面通常做得很差，未能采用一些适合该平台的直接优化，但有时会采用不适合该平台的“优化” .给出类似
的东西
void test1(uint8_t *p)
{
for (int i=0; i<32; i++)
p[i] = (p[i]*9363) >> 16; // Divide by 7
}
gcc 恰好在 -O2 为 Cortex-M0 生成了好的代码，但如果乘法被加法代替，编译器将生成代码，在循环的每次迭代中重新加载常量 9363。使用加法时，即使代码改为：
void test2(uint16_t *p)
{
register unsigned u9363 = 9363;
for (int i=0; i<32; i++)
p[i] = (p[i]+u9363) >> 16;
}
gcc 仍会将常量加载到循环中。有时 gcc 的优化也可能产生意想不到的行为后果。例如，人们可能期望在像 Cortex-M0 这样的平台上，调用如下内容：
unsigned short test(register unsigned short *p)
{
register unsigned short temp = *p;
return temp - (temp >> 15);
}
当中断更改 *p 的内容时，可能会产生与旧值或新值一致的行为。标准不需要这样的处理，但是大多数旨在适合嵌入式编程任务的实现将提供比标准要求的更强大的保证。如果旧值或新值同样可以接受，则让编译器使用更方便的值可能会比使用 volatile 允许更高效的代码。然而，碰巧的是，来自 gcc 的“优化”代码将用 *p.
的单独加载替换 temp 的两次使用
如果您将 gcc 与 Cortex-M0 一起使用并且非常关心性能或“惊人”行为的可能性，请养成检查编译器输出的习惯。对于某些类型的循环，甚至可能值得考虑测试 -O0。如果代码适当地使用了 register 关键字，它的性能有时可以胜过使用 -O2.
处理的相同代码。
扩展超级猫的答案。
喂这个：
unsigned short fun ( unsigned short x )
{
return(x/7);
}
乘以更大的东西：
00000000 <fun>:
0: e59f1010 ldr r1, [pc, #16] ; 18 <fun+0x18>
4: e0832190 umull r2, r3, r0, r1
8: e0400003 sub r0, r0, r3
c: e08300a0 add r0, r3, r0, lsr #1
10: e1a00120 lsr r0, r0, #2
14: e12fff1e bx lr
18: 24924925 .word 0x24924925
1/7 二进制（长除法）：
0.001001001001001
111)1.000000
111
====
1000
111
===
1
0.001001001001001001001001001001
0.0010 0100 1001 0010 0100 1001 001001
0x2492492492...
0x24924925>>32 (rounded up)
为此你需要一个 64 位的结果，你取上半部分并做一些调整，例如：
7 * 0x24924925 = 0x100000003
然后你取前 32 位（不是完全这么简单，但对于这个值你可以看到它有效）。
all thumbs 变体乘法是 32 位 = 32 位 * 32 位，因此结果将是 0x00000003，这是行不通的。
所以 0x24924，我们可以像 supercat 那样制作 0x2493 或 0x2492。
现在我们可以使用 32x32 = 32 位乘法：
0x2492 * 7 = 0x0FFFE
0x2493 * 7 = 0x10005
让我们 运行 大一点的：
0x100000000/0x2493 = a number greater than 65536. so that is fine.
但是：
0x3335 * 0x2493 = 0x0750DB6F
0x3336 * 0x2493 = 0x07510002
0x3335 / 7 = 0x750
0x3336 / 7 = 0x750
所以你只能用这种方法走到这一步。
如果按照arm代码的型号：
for(ra=0;ra<0x10000;ra++)
{
rb=0x2493*ra;
rd=rb>>16;
rb=ra-rd;
rb=rd+(rb>>1);
rb>>=2;
rc=ra/7;
printf("0x%X 0x%X 0x%X \n",ra,rb,rc);
if(rb!=rc) break;
}
然后它从 0x0000 到 0xFFFF 工作，所以你可以编写 asm 来做到这一点（注意它需要是 0x2493 而不是 0x2492）。
如果你知道 ope运行d 不会超过某个值，那么你可以使用更多的 1/7 位来乘以。
在任何情况下，如果编译器不为您进行此优化，那么您自己仍然有机会。
现在回想起来，我运行以前就入过这个，现在才明白过来。但是我在一个全尺寸的手臂上，我调用了一个我在 arm 模式下编译的例程（另一个代码在 thumb 模式下），并且基本上有一个 switch 语句 if denominator = 1 then result = x/1;如果分母 = 2 那么结果 = x/2 等等。然后它避免了 gcclib 函数并生成 1/x 乘法。 （我想要除以 3 或 4 个不同的常量）：
unsigned short udiv7 ( unsigned short x )
{
unsigned int r0;
unsigned int r3;
r0=x;
r3=0x2493*r0;
r3>>=16;
r0=r0-r3;
r0=r3+(r0>>1);
r0>>=2;
return(r0);
}
假设我没有犯错：
00000000 <udiv7>:
0: 4b04 ldr r3, [pc, #16] ; (14 <udiv7+0x14>)
2: 4343 muls r3, r0
4: 0c1b lsrs r3, r3, #16
6: 1ac0 subs r0, r0, r3
8: 0840 lsrs r0, r0, #1
a: 18c0 adds r0, r0, r3
c: 0883 lsrs r3, r0, #2
e: b298 uxth r0, r3
10: 4770 bx lr
12: 46c0 nop ; (mov r8, r8)
14: 00002493 .word 0x00002493
这应该比通用除法库例程更快。
编辑
我想我看到了 supercat 用有效的解决方案做了什么：
((i*37449 + 16384u) >> 18)
我们将其作为 1/7 分数：
0.001001001001001001001001001001
但我们只能进行 32 = 32x32 位乘法运算。前导零为我们提供了一些我们可以利用的喘息空间。因此，我们可以尝试代替 0x2492/0x2493：
1001001001001001
0x9249
0x9249*0xFFFF = 0x92486db7
到目前为止它不会溢出：
rb=((ra*0x9249) >> 18);
它本身在 7 * 0x9249 = 0x3FFFF 处失败，0x3FFFF>>18 是零而不是 1。
所以也许
rb=((ra*0x924A) >> 18);
失败于：
0xAAAD 0x1862 0x1861
那么：
rb=((ra*0x9249 + 0x8000) >> 18);
这行得通。
超级猫呢？
rb=((ra*0x9249 + 0x4000) >> 18);
并且 运行 对于所有值 0x0000 到 0xFFFF 都是干净的：
rb=((ra*0x9249 + 0x2000) >> 18);
这里失败了：
0xE007 0x2000 0x2001
所以有几个可行的解决方案。
unsigned short udiv7 ( unsigned short x )
{
unsigned int ret;
ret=x;
ret=((ret*0x9249 + 0x4000) >> 18);
return(ret);
}
00000000 <udiv7>:
0: 4b03 ldr r3, [pc, #12] ; (10 <udiv7+0x10>)
2: 4358 muls r0, r3
4: 2380 movs r3, #128 ; 0x80
6: 01db lsls r3, r3, #7
8: 469c mov ip, r3
a: 4460 add r0, ip
c: 0c80 lsrs r0, r0, #18
e: 4770 bx lr
10: 00009249 .word 0x00009249
编辑
就“为什么”问题而言，这不是 Stack Overflow 问题；如果您想知道为什么 gcc 不这样做，请询问该代码的作者。我们所能做的就是在这里推测，推测是他们可能选择不这样做是因为指令的数量，或者他们可能选择不这样做是因为他们有一个算法说明因为这不是 64 = 32x32 位乘法然后做不打扰。
同样，为什么问题不是 Stack Overflow 问题，所以也许我们应该关闭这个问题并删除所有答案。
我发现这非常有教育意义（一旦你 know/understand 正在说什么）。
另一个为什么？问题是为什么 gcc 可以按照 supercat 或我的方式来做？
我正在使用最新可用版本的 ARM 封装 GCC：
arm-none-eabi-gcc（GNU Arm 嵌入式工具链 10-2020-q4-major）10.2.1 20201103（发布） 版权所有 (C) 2020 Free Software Foundation, Inc.
当我使用“-mcpu=cortex-m0 -mthumb -Ofast”编译此代码时：
int main(void) {
uint16_t num = (uint16_t) ADC1->DR;
ADC1->DR = num / 7;
}
我希望除法可以通过乘法和移位来完成，但生成的是这段代码：
08000b5c <main>:
8000b5c: b510 push {r4, lr}
8000b5e: 4c05 ldr r4, [pc, #20] ; (8000b74 <main+0x18>)
8000b60: 2107 movs r1, #7
8000b62: 6c20 ldr r0, [r4, #64] ; 0x40
8000b64: b280 uxth r0, r0
8000b66: f7ff facf bl 8000108 <__udivsi3>
8000b6a: b280 uxth r0, r0
8000b6c: 6420 str r0, [r4, #64] ; 0x40
8000b6e: 2000 movs r0, #0
8000b70: bd10 pop {r4, pc}
8000b72: 46c0 nop ; (mov r8, r8)
8000b74: 40012400 .word 0x40012400
使用__udivsi3代替乘法和移位是非常低效的。我是否使用了错误的标志，或者遗漏了其他东西，或者这是一个 GCC 错误？
编译器只有在知道结果对于语言允许的任何输入都是正确的情况下才能重新排列整数表达式。
因为7和2互质，所以任何输入都不能用乘法和移位来除以7。
如果您知道您打算提供的输入是可能的，那么您必须自己使用乘法和移位运算符来完成。
根据输入的大小，您必须选择要移动多少，以便输出正确（或至少对您的应用程序足够好）并且中间不会溢出。编译器无法知道什么对您的应用程序足够准确，或者您的最大输入是多少。如果它允许任何输入达到该类型的最大值，那么每次乘法都会溢出。
一般来说，如果除数不是 2 的互质，即如果它是 2 的幂，GCC 只会使用移位进行除法。
Cortex-M0 缺少执行 32x32->64 位乘法的指令。因为 num 是一个无符号的 16 位数量，所以将它乘以 9363 并右移 16 将在所有情况下产生正确的结果，但是——可能是因为 uint16_t 将被提升为 int 在乘法之前，gcc 不包括此类优化。
根据我的观察，gcc 在针对 Cortex-M0 的优化方面通常做得很差，未能采用一些适合该平台的直接优化，但有时会采用不适合该平台的“优化” .给出类似
的东西void test1(uint8_t *p)
{
for (int i=0; i<32; i++)
p[i] = (p[i]*9363) >> 16; // Divide by 7
}
gcc 恰好在 -O2 为 Cortex-M0 生成了好的代码，但如果乘法被加法代替，编译器将生成代码，在循环的每次迭代中重新加载常量 9363。使用加法时，即使代码改为：
void test2(uint16_t *p)
{
register unsigned u9363 = 9363;
for (int i=0; i<32; i++)
p[i] = (p[i]+u9363) >> 16;
}
gcc 仍会将常量加载到循环中。有时 gcc 的优化也可能产生意想不到的行为后果。例如，人们可能期望在像 Cortex-M0 这样的平台上，调用如下内容：
unsigned short test(register unsigned short *p)
{
register unsigned short temp = *p;
return temp - (temp >> 15);
}
当中断更改 *p 的内容时，可能会产生与旧值或新值一致的行为。标准不需要这样的处理，但是大多数旨在适合嵌入式编程任务的实现将提供比标准要求的更强大的保证。如果旧值或新值同样可以接受，则让编译器使用更方便的值可能会比使用 volatile 允许更高效的代码。然而，碰巧的是，来自 gcc 的“优化”代码将用 *p.
temp 的两次使用
如果您将 gcc 与 Cortex-M0 一起使用并且非常关心性能或“惊人”行为的可能性，请养成检查编译器输出的习惯。对于某些类型的循环，甚至可能值得考虑测试 -O0。如果代码适当地使用了 register 关键字，它的性能有时可以胜过使用 -O2.
扩展超级猫的答案。
喂这个：
unsigned short fun ( unsigned short x )
{
return(x/7);
}
乘以更大的东西：
00000000 <fun>:
0: e59f1010 ldr r1, [pc, #16] ; 18 <fun+0x18>
4: e0832190 umull r2, r3, r0, r1
8: e0400003 sub r0, r0, r3
c: e08300a0 add r0, r3, r0, lsr #1
10: e1a00120 lsr r0, r0, #2
14: e12fff1e bx lr
18: 24924925 .word 0x24924925
1/7 二进制（长除法）：
0.001001001001001
111)1.000000
111
====
1000
111
===
1
0.001001001001001001001001001001
0.0010 0100 1001 0010 0100 1001 001001
0x2492492492...
0x24924925>>32 (rounded up)
为此你需要一个 64 位的结果，你取上半部分并做一些调整，例如：
7 * 0x24924925 = 0x100000003
然后你取前 32 位（不是完全这么简单，但对于这个值你可以看到它有效）。
all thumbs 变体乘法是 32 位 = 32 位 * 32 位，因此结果将是 0x00000003，这是行不通的。
所以 0x24924，我们可以像 supercat 那样制作 0x2493 或 0x2492。
现在我们可以使用 32x32 = 32 位乘法：
0x2492 * 7 = 0x0FFFE
0x2493 * 7 = 0x10005
让我们 运行 大一点的：
0x100000000/0x2493 = a number greater than 65536. so that is fine.
但是：
0x3335 * 0x2493 = 0x0750DB6F
0x3336 * 0x2493 = 0x07510002
0x3335 / 7 = 0x750
0x3336 / 7 = 0x750
所以你只能用这种方法走到这一步。
如果按照arm代码的型号：
for(ra=0;ra<0x10000;ra++)
{
rb=0x2493*ra;
rd=rb>>16;
rb=ra-rd;
rb=rd+(rb>>1);
rb>>=2;
rc=ra/7;
printf("0x%X 0x%X 0x%X \n",ra,rb,rc);
if(rb!=rc) break;
}
然后它从 0x0000 到 0xFFFF 工作，所以你可以编写 asm 来做到这一点（注意它需要是 0x2493 而不是 0x2492）。
如果你知道 ope运行d 不会超过某个值，那么你可以使用更多的 1/7 位来乘以。
在任何情况下，如果编译器不为您进行此优化，那么您自己仍然有机会。
现在回想起来，我运行以前就入过这个，现在才明白过来。但是我在一个全尺寸的手臂上，我调用了一个我在 arm 模式下编译的例程（另一个代码在 thumb 模式下），并且基本上有一个 switch 语句 if denominator = 1 then result = x/1;如果分母 = 2 那么结果 = x/2 等等。然后它避免了 gcclib 函数并生成 1/x 乘法。 （我想要除以 3 或 4 个不同的常量）：
unsigned short udiv7 ( unsigned short x )
{
unsigned int r0;
unsigned int r3;
r0=x;
r3=0x2493*r0;
r3>>=16;
r0=r0-r3;
r0=r3+(r0>>1);
r0>>=2;
return(r0);
}
假设我没有犯错：
00000000 <udiv7>:
0: 4b04 ldr r3, [pc, #16] ; (14 <udiv7+0x14>)
2: 4343 muls r3, r0
4: 0c1b lsrs r3, r3, #16
6: 1ac0 subs r0, r0, r3
8: 0840 lsrs r0, r0, #1
a: 18c0 adds r0, r0, r3
c: 0883 lsrs r3, r0, #2
e: b298 uxth r0, r3
10: 4770 bx lr
12: 46c0 nop ; (mov r8, r8)
14: 00002493 .word 0x00002493
这应该比通用除法库例程更快。
编辑
我想我看到了 supercat 用有效的解决方案做了什么：
((i*37449 + 16384u) >> 18)
我们将其作为 1/7 分数：
0.001001001001001001001001001001
但我们只能进行 32 = 32x32 位乘法运算。前导零为我们提供了一些我们可以利用的喘息空间。因此，我们可以尝试代替 0x2492/0x2493：
1001001001001001
0x9249
0x9249*0xFFFF = 0x92486db7
到目前为止它不会溢出：
rb=((ra*0x9249) >> 18);
它本身在 7 * 0x9249 = 0x3FFFF 处失败，0x3FFFF>>18 是零而不是 1。
所以也许
rb=((ra*0x924A) >> 18);
失败于：
0xAAAD 0x1862 0x1861
那么：
rb=((ra*0x9249 + 0x8000) >> 18);
这行得通。
超级猫呢？
rb=((ra*0x9249 + 0x4000) >> 18);
并且 运行 对于所有值 0x0000 到 0xFFFF 都是干净的：
rb=((ra*0x9249 + 0x2000) >> 18);
这里失败了：
0xE007 0x2000 0x2001
所以有几个可行的解决方案。
unsigned short udiv7 ( unsigned short x )
{
unsigned int ret;
ret=x;
ret=((ret*0x9249 + 0x4000) >> 18);
return(ret);
}
00000000 <udiv7>:
0: 4b03 ldr r3, [pc, #12] ; (10 <udiv7+0x10>)
2: 4358 muls r0, r3
4: 2380 movs r3, #128 ; 0x80
6: 01db lsls r3, r3, #7
8: 469c mov ip, r3
a: 4460 add r0, ip
c: 0c80 lsrs r0, r0, #18
e: 4770 bx lr
10: 00009249 .word 0x00009249
编辑
就“为什么”问题而言，这不是 Stack Overflow 问题；如果您想知道为什么 gcc 不这样做，请询问该代码的作者。我们所能做的就是在这里推测，推测是他们可能选择不这样做是因为指令的数量，或者他们可能选择不这样做是因为他们有一个算法说明因为这不是 64 = 32x32 位乘法然后做不打扰。
同样，为什么问题不是 Stack Overflow 问题，所以也许我们应该关闭这个问题并删除所有答案。
我发现这非常有教育意义（一旦你 know/understand 正在说什么）。
另一个为什么？问题是为什么 gcc 可以按照 supercat 或我的方式来做？