为什么ARM gcc在除以常数时会调用__udivsi3?

Question

我正在使用最新版本的ARM打包的GCC：

arm-none-eabi-gcc（GNU Arm嵌入式工具链10-2020-q4-major）10.2.1 20201103（发布版） 版权所有（C）2020年自由软件基金会。

当我使用“-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 的 bug？

- Dan Sandberg

Answer 1

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的两个使用替换为分别加载。

如果您正在使用Cortex-M0的gcc，并且对性能或“惊人”的行为有任何担忧，请养成检查编译器输出的习惯。对于某些类型的循环，甚至考虑测试-O0是否值得。如果代码适当使用了register关键字，则其性能有时可以超过使用-O2处理的相同代码。

- supercat

---

很棒的答案，谢谢。您是否建议一款编译器，适用于Cortex-M0并能正确处理细节？ - Dan Sandberg

@DanSandberg：我在工作中使用ARM-Keil MDK。它相当昂贵，但你可以下载一个免费的功能受限评估版本。 - supercat

如果这个问题影响到您，请在此处将错误标记为影响您：https://bugs.launchpad.net/gcc-arm-embedded/+bug/1920818 - Dan Sandberg

@DanSandberg：就Cortex-M0代码生成效率而言，这个除法问题只是冰山一角。你有没有看过上面最后一个“test”函数的gcc生成的代码？除非gcc的维护人员对于尝试去最大化能够可靠且高效地处理具有相同语义 的非可移植但有用结构的范围感兴趣，而不会像“test”中那样创建无谓的怪异情况，否则我只会将gcc视为可靠的编译器，当且仅当我们在代码中使用"-O0"来部分代替我们每次构建后不进行手动检查的代码部分。 - supercat

顺便提一下，当计算 x*9363 时，gcc使用常量的加载后跟乘法，但是当使用 x*37449 时，它选择生成一个由移动、加法和移位组成的八条指令序列。在具有缓慢乘法的ARM上可能是一个不错的权衡，但在具有快速乘法的ARM上则不是。 - supercat

Answer 2

对supercat的回答进行扩展。

输入以下内容：

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位（虽然不完全是这么简单，但对于这个值，你可以看到它的工作原理）。

所有拇指变体乘法都是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

所以你只能用那种方法走到这一步。

如果我们遵循手臂代码的模式：

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工作，因此您可以编写汇编代码来执行此操作（请注意，需要的是0x2493而不是0x2492）。

如果您知道操作数不会超过某个值，则可以使用更多的1/7位来进行乘法运算。

无论如何，当编译器没有为您执行此优化时，您仍然有机会自己实现。

现在我想起来以前遇到过这种情况，现在有点明白了。但是我当时使用的是全尺寸的ARM，并调用了一个我在ARM模式下编译的例程（其他代码是Thumb模式），并且基本上有一个switch语句，如果分母= 1，则结果= 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 是零而不是一。

所以也许

    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上的问题，所以也许我们应该关闭这个问题并删除所有答案。

我发现这非常有教育意义（一旦你知道/理解了说的是什么）。

另一个“为什么”问题是，为什么gcc要以他们的方式来做，而不是像supercat或我一样来做呢？

- old_timer

---

倒数乘法，教程 https://homepage.divms.uiowa.edu/~jones/bcd/divide.html - old_timer

gcc 明显知道如何做到这一点（也可以尝试其他目标），因此我不认为这是一个错误或错过的优化。我假设他们在一定量的代码之后或者如果所有的拇指变体都不尝试优化，只是进行了一次尝试/不尝试的判断。 - old_timer

这篇文章与问题毫无关系。问题是“为什么gcc不自动执行此操作？”，而不是“我该如何自己执行此操作？”显然，提问者已经知道如何执行此操作，否则他们就不会问这个问题了。 - Tom V

Answer 3

编译器只有在知道结果对语言允许的任何输入都正确时，才能重新排列整数表达式。

因为7与2互质，所以不可能通过乘法和移位来除以任何输入。

如果您知道要提供的输入是可能的，则必须使用乘法和移位运算符自己完成。

根据输入的大小，您将不得不选择多少移位才能使输出正确（或者至少对您的应用程序足够好），并且中间值不会溢出。编译器无法知道什么对于您的应用程序足够准确，或者您的最大输入是什么。如果它允许任何类型的最大输入，则每个乘法都会溢出。

通常情况下，GCC只有在除数不与2互质，即为2的幂时，才会使用移位进行除法运算。

- Tom V

---

如果输入在0-65535范围内（num是uint16_t），如果编译器对这样的优化感兴趣，乘法和移位将会轻松地产生精确的结果。 - supercat

是的，对于uint16_t除以7，但不适用于任意常数除数，并且在这个32位平台上，除数通常也不会是16位。我想表达的是这是一个不太普遍适用的特殊情况。这就是为什么没有人考虑把它添加到编译器中，因为在这些特殊情况下，人们可以手动完成它。 - Tom V

@old_timer：对于从uint8_t、uint16_t或常量值产生的股息，只需简单的乘法指令即可保证其产生的值在0-65535范围内。我预计，在许多平台上，对于更大的输入，32x32乘法例程可能比除法例程更有效率，尽管一些Cortex-M0设备具有“除法辅助”电路，这可能会抵消该优势。 - supercat

使用32=32x32的乘法不足够（对于0到0xFFFF之间的许多情况，(x*9363)>>16会失败），如您所示。也许几年前您应该看过有关为什么gcc在指定isa具有除法（针对arm）时产生乘法的问题。如果他们愿意，芯片供应商肯定也可以添加分频器。尽管如此，这是一个好/有趣的问题。 - old_timer

我得看一下，但对于M0芯片或者其他芯片，芯片供应商可以编译快速乘法或慢速乘法，可以说可能存在命令行选项以生成非库代码（如果可能的话）。这不是我感兴趣的项目，我只是会像上面那样做（或者通过其他方式合成除法以避免除法）。一个例子就是只需将ADC值与7倍时间保留在那里，然后进行其余的数学运算，或者稍后分解它或不需要分解。 - old_timer