| commit | 38a8000f30aa87a51ac0598dae3cb9166084f6a0 | [log] [tgz] |
|---|---|---|
| author | yonghong-song <yhs@fb.com> | Tue Oct 01 14:20:54 2024 -0700 |
| committer | GitHub <noreply@github.com> | Tue Oct 01 14:20:54 2024 -0700 |
| tree | d1d7778bab3a7c0f33157ca73dd5ba886805ae52 | |
| parent | aa02b76b1a4c2df1a701fbd8a8378d1cd946e70a [diff] |
[BPF] Use mul for certain div/mod operations (#110712)
The motivation example likes below
```
$ cat t1.c
struct S {
int var[3];
};
int foo1 (struct S *a, struct S *b)
{
return a - b;
}
```
For cpu v1/v2/v3, the compilation will fail with the following error:
```
$ clang --target=bpf -O2 -c t1.c -mcpu=v3
t1.c:4:5: error: unsupported signed division, please convert to unsigned div/mod.
4 | int foo1 (struct S *a, struct S *b)
| ^
1 error generated.
```
The reason is that sdiv/smod is only supported at -mcpu=v4. At cpu
v1/v2/v3, only udiv/umod is supported.
But the above example (for func foo1()) is reasonable common and user
has to workaround the compilation failure by using udiv with
conditionals.
For x86, for the above t1.c, compile and dump the asm code like below:
```
$ clang -O2 -c t1.c && llvm-objdump -d t1.o
0000000000000000 <foo1>:
0: 48 29 f7 subq %rsi, %rdi
3: 48 c1 ef 02 shrq $0x2, %rdi
7: 69 c7 ab aa aa aa imull $0xaaaaaaab, %edi, %eax # imm = 0xAAAAAAAB
d: c3 retq
```
Basically sdiv can be replaced with sub, shr and imul. Latest gcc-bpf is
also able to generate code similar to x86 with -mcpu=v1. See
https://godbolt.org/z/feP9ETbjj
Generally multiplication is cheaper than divide. LLVM SelectionDAG
already supports to generate alternative codes (mul etc.) for div/mod
operations if the divisor is constant and if the cost of division is not
cheap. For BPF backend, let us use multiplication instead of divide
whenever possible. The following is the list of div/mod operations which
can be converted to mul.
- 32bit signed/unsigned div/mod with constant divisor
- 64bit signed/unsigned div with constant divisor and with 'exact' flag
in IR where 'exact' means if replacing div with mod, it is guaranteed
that modulo result will be 0. The above foo1() case belongs here.
Welcome to the LLVM project!
This repository contains the source code for LLVM, a toolkit for the construction of highly optimized compilers, optimizers, and run-time environments.
The LLVM project has multiple components. The core of the project is itself called “LLVM”. This contains all of the tools, libraries, and header files needed to process intermediate representations and convert them into object files. Tools include an assembler, disassembler, bitcode analyzer, and bitcode optimizer.
C-like languages use the Clang frontend. This component compiles C, C++, Objective-C, and Objective-C++ code into LLVM bitcode -- and from there into object files, using LLVM.
Other components include: the libc++ C++ standard library, the LLD linker, and more.
Consult the Getting Started with LLVM page for information on building and running LLVM.
For information on how to contribute to the LLVM project, please take a look at the Contributing to LLVM guide.
Join the LLVM Discourse forums, Discord chat, LLVM Office Hours or Regular sync-ups.
The LLVM project has adopted a code of conduct for participants to all modes of communication within the project.