如何优化除以一个常数被除数的计算？

Question

众所周知，将除以常数的操作进行优化是gcc所擅长的。

现在我想知道如何对除以常数的操作进行优化。然而，无论是gcc还是clang都没有给我提供帮助。

也许我不太擅长搜索这样的信息，但我找不到有关优化除以常数的材料。（相比之下，除以常数则有很好的介绍）。

#include <stdio.h>

int f(int x)
{
    // can I optimize off the idiv opcode here?
    return 33659/x;
}

int main()
{
    int x;
    scanf("%d", &x);
    printf("%d", f(x));
    return 0;
}

编辑1：

#include <stdio.h>

#define DIVIDEND 33

void f ( unsigned int* arr, int n )
{
    for ( int i = 0; i < n ; i++ )
    {
        arr[i] = DIVIDEND / arr[i];
    }
}

int main()
{
    const int n = 1024;
    unsigned int buf[n];
    for ( int i = 0; i < n; i++ )
    {
        scanf ( "%u", buf + i );
    }
    f ( buf, n );
    for ( int i = 0; i < n; i++ )
    {
        printf ( "%d", buf[i] );
    }
    return 0;
}

使用 clang -O3 -march=native div.c -o div 进行优化仅展开了循环，而：

#include <stdio.h>

#define DIVIDEND 33
#define DIVISOR DIVIDEND

void f ( unsigned int* arr, int n )
{
    for ( int i = 0; i < n ; i++ )
    {
        //arr[i] = DIVIDEND / arr[i];
        arr[i] = arr[i] / DIVISOR;
    }
}

int main()
{
    const int n = 1024;
    unsigned int buf[n];
    for ( int i = 0; i < n; i++ )
    {
        scanf ( "%u", buf + i );
    }
    f ( buf, n );
    for ( int i = 0; i < n; i++ )
    {
        printf ( "%d", buf[i] );
    }
    return 0;
}

使用相同的命令行将产生一堆可怕的AVX2代码。（请记住，常数除法将被重写为shift+mul+add，这可以进行矢量化！）

编辑2：感谢@user2722968！应用RCPPS将使程序更快。

这是我的实验性实现，使用RCPPS进行快速常数被除数除法：

https://github.com/ThinerDAS/didactic-spoon/blob/master/div.c

然而，我不确定如何在不增加大量开销的情况下使其更加准确。

- Thiner

---

既然gcc和clang都没有显示任何优化，这就很明显地表明无法对其进行很好的优化（或者说完全不能被优化）。 - Ben Steffan

很有趣了解 OP 认为在这种情况下可能存在哪些优化。 - High Performance Mark

我认为不可能进行任何优化。 - linuxfan says Reinstate Monica

@PSkocik 1/x 的优化也可能是值得的。但无论如何，如果 x 受到足够限制，比如只有 [1, ... 10]，我可以想象出可能的优化方法。 - Ped7g

唯一的优化是将函数声明/定义为“static”，从而允许其进行内联。 - wildplasser

Answer 1

如果你能够触发一个非常好的“除以”优化，那么你可以通过使用RCPPS指令（它确实使用SSE/AVX）计算x/33659的倒数来获得好处。

- user2722968

---

RCPPS是一个不错的提示！这条指令只是一个非常粗略的近似，不是很可靠，但是速度非常快。很难触发这个指令 :( 我会尝试一下的。 - Thiner