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

Question

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

arm none eabi gcc（GNU arm Embedded Toolchain 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错误？

Answer 1

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

因为7是2的共同素数，所以不可能用乘法和移位将任何输入除以7。

如果你知道你打算提供的输入是可能的，那么你必须自己使用乘法和移位运算符。

根据输入的大小，您必须选择移动多少，以便输出正确（或者至少对您的应用程序足够好），并且中间不会溢出。编译器无法知道什么对您的应用程序足够准确，或者您的最大输入是多少。如果它允许任何类型的最大输入，那么每一个乘法都会溢出。

一般来说，GCC只会在除数不是2的副素数的情况下使用移位进行除法，也就是说，如果除数是2的幂。

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

all thumbs变量乘法是32位=32位*32位，因此结果将是0x00000003，这不起作用。

所以0x24924，我们可以像超级猫一样制作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）。

如果您知道操作数没有超过某个值，那么可以使用更多的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

这应该比一般的部门库例程更快。

我想我看到了超级猫用有效的解决方案做了什么：

((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时失败

所以也许

    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

至于“为什么”问题，这不是一个堆栈溢出问题；如果你想知道为什么gcc不这么做，可以询问代码的作者。我们所能做的就是在这里推测，推测是他们可能选择不这样做，因为指令的数量，或者他们可能选择不这样做，因为他们有一个算法，因为这不是一个64=32x32位的乘法，那么就不用麻烦了。

同样，为什么问题不是堆栈溢出问题，所以也许我们应该关闭这个问题并删除所有答案。

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

另一个原因是什么？问题是为什么gcc会这样做，而他们本可以像supercat或我那样做？

Answer 3

Cortex-M0缺少执行32x32的指令-

从我观察到的情况来看，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的“优化”代码将取代temp的两种用法，分别加载*p。

如果您在Cortex M0中使用gcc，并且非常担心性能或“惊人”行为的可能性，请养成检查编译器输出的习惯。对于某些循环，甚至值得考虑测试-O0。如果代码适当地使用了寄存器关键字，它的性能有时会优于用-O2处理的相同代码。