众所周知,将除以常数的操作进行优化是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
然而,我不确定如何在不增加大量开销的情况下使其更加准确。
x
受到足够限制,比如只有 [1, ... 10],我可以想象出可能的优化方法。 - Ped7g