bpf selftest pyperf180.c compilation failure with latest last llvm18 (in development)

bpf selftest pyperf180.c compilation failure with latest last llvm18 (in development)

[Yonghong Song]

With latest llvm18 (main branch of llvm-project repo), when building bpf selftests,
    [~/work/bpf-next (master)]$ make -C tools/testing/selftests/bpf LLVM=1 -j

The following compilation error happens:
    fatal error: error in backend: Branch target out of insn range
    PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
    Stack dump:
    0.      Program arguments: clang -g -Wall -Werror -D__TARGET_ARCH_x86 -mlittle-endian -I/home/yhs/work/bpf-next/tools/testing/selftests/bpf/tools/include -I/home/yhs
    /work/bpf-next/tools/testing/selftests/bpf -I/home/yhs/work/bpf-next/tools/include/uapi -I/home/yhs/work/bpf-next/tools/testing/selftests/usr/include -idirafter /hom
    e/yhs/work/llvm-project/llvm/build.18/install/lib/clang/18/include -idirafter /usr/local/include -idirafter /usr/include -Wno-compare-distinct-pointer-types -DENABLE
    _ATOMICS_TESTS -O2 --target=bpf -c progs/pyperf180.c -mcpu=v3 -o /home/yhs/work/bpf-next/tools/testing/selftests/bpf/pyperf180.bpf.o
    1.      <eof> parser at end of file
    2.      Code generation
    .....

The compilation failure only happens to cpu=v2 and cpu=v3. cpu=v4 is okay
since cpu=v4 supports 32-bit branch target offset.

The above failure is due to upstream llvm patch
    https://reviews.llvm.org/D143624
where some inlining ordering are changed in the compiler.
The following change can temporarily work around the issue:

diff --git a/tools/testing/selftests/bpf/progs/pyperf180.c b/tools/testing/selftests/bpf/progs/pyperf180.c
index c39f559d3100..db0bfaaf480c 100644
--- a/tools/testing/selftests/bpf/progs/pyperf180.c
+++ b/tools/testing/selftests/bpf/progs/pyperf180.c
@@ -1,4 +1,9 @@
  // SPDX-License-Identifier: GPL-2.0
  // Copyright (c) 2019 Facebook
+#if __clang_major__ >= 18
+#define STACK_MAX_LEN 150
+#else
  #define STACK_MAX_LEN 180
+#endif
+
  #include "pyperf.h"

We will do some more investigation to see whether we could do
anything in llvm side to mitigate the issue, or if not, will
provide a proper patch to fix the issue.

Re: bpf selftest pyperf180.c compilation failure with latest last llvm18 (in development)

[Eduard Zingerman]

On Mon, 2023-10-30 at 20:58 -0700, Yonghong Song wrote:
> With latest llvm18 (main branch of llvm-project repo), when building bpf selftests,
>     [~/work/bpf-next (master)]$ make -C tools/testing/selftests/bpf LLVM=1 -j
> 
> The following compilation error happens:
>     fatal error: error in backend: Branch target out of insn range
>     PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
>     Stack dump:
>     0.      Program arguments: clang -g -Wall -Werror -D__TARGET_ARCH_x86 -mlittle-endian -I/home/yhs/work/bpf-next/tools/testing/selftests/bpf/tools/include -I/home/yhs
>     /work/bpf-next/tools/testing/selftests/bpf -I/home/yhs/work/bpf-next/tools/include/uapi -I/home/yhs/work/bpf-next/tools/testing/selftests/usr/include -idirafter /hom
>     e/yhs/work/llvm-project/llvm/build.18/install/lib/clang/18/include -idirafter /usr/local/include -idirafter /usr/include -Wno-compare-distinct-pointer-types -DENABLE
>     _ATOMICS_TESTS -O2 --target=bpf -c progs/pyperf180.c -mcpu=v3 -o /home/yhs/work/bpf-next/tools/testing/selftests/bpf/pyperf180.bpf.o
>     1.      <eof> parser at end of file
>     2.      Code generation
>     .....
> 
> The compilation failure only happens to cpu=v2 and cpu=v3. cpu=v4 is okay
> since cpu=v4 supports 32-bit branch target offset.
> 
> The above failure is due to upstream llvm patch
>     https://reviews.llvm.org/D143624
> where some inlining ordering are changed in the compiler.

Hi Yonghong, Alexei,

This is a followup for the off-list discussion. I think I have a
relatively simple two pass algorithm that allows to replace jumps
longer than 2**16 by series of shorter jumps using "trampoline"
goto instructions.

The basic idea of the algorithm is to:
- Visit basic blocks sequentially from first to last (after LLVM is
  done with figuring BB ordering), effectively splitting basic blocks
  in two parts: "processed" and "unexplored".
- Insert "trampoline" jumps only at "unexplored" side, thus
  guaranteeing that distances between basic blocks on "processed" side
  never change.
- Maintain the list of "pending jumps":
  - Whenever a basic block is picked from "unexplored" side
    information about edges coming to and from this basic block is
    added as pending jumps:
    - backward edges are added before basic block is processed;
    - forward edges are added after basic block is processed.
  - Pending jump is a tuple (off,src,dst,backedge):
    - 'src', 'dst' - basic blocks (swapped for backedges);
    - 'off' - current distance from 'src'.
- When a basic block is picked from "unexplored" side:
  - discard all pending jumps that have this basic block as 'dst';
  - peek a pending jump for which jmp.off + bb.size > MAX_JUMP_DISTANCE;
  - if such jump is present:
    - split basic block;
    - insert trampoline instruction;
    - discard pending jump and schedule new pending jump with
      trampoline src, original dst, and off=0;
  - if such jump is not present move basic block from "unexplored" to
    "processed";
  - when basic block is moved from "unexplored" side to "processed",
    bump 'off' field of each pending jump by the size of the basic
    block.

So, the main part is to keep 'off' fields of pending jumps smaller
than MAX_JUMP_DISTANCE by inserting trampoline jumps.

I have a Python model for this algorithm at [0]. It passes a few
hand-coded tests but I still need to do some property-based testing.
I think I need another day to finish with testing, after that it
should be possible to translate this code to LLVM/C++ in a couple of days.

Please let me know if this is interesting.

Thanks,
Eduard

[0] https://gist.github.com/eddyz87/7e8d162b2bb2071769a9b3d960898405

[...]

Re: bpf selftest pyperf180.c compilation failure with latest last llvm18 (in development)

[Alexei Starovoitov]

On Tue, Nov 7, 2023 at 6:13 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2023-10-30 at 20:58 -0700, Yonghong Song wrote:
> > With latest llvm18 (main branch of llvm-project repo), when building bpf selftests,
> >     [~/work/bpf-next (master)]$ make -C tools/testing/selftests/bpf LLVM=1 -j
> >
> > The following compilation error happens:
> >     fatal error: error in backend: Branch target out of insn range
> >     PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
> >     Stack dump:
> >     0.      Program arguments: clang -g -Wall -Werror -D__TARGET_ARCH_x86 -mlittle-endian -I/home/yhs/work/bpf-next/tools/testing/selftests/bpf/tools/include -I/home/yhs
> >     /work/bpf-next/tools/testing/selftests/bpf -I/home/yhs/work/bpf-next/tools/include/uapi -I/home/yhs/work/bpf-next/tools/testing/selftests/usr/include -idirafter /hom
> >     e/yhs/work/llvm-project/llvm/build.18/install/lib/clang/18/include -idirafter /usr/local/include -idirafter /usr/include -Wno-compare-distinct-pointer-types -DENABLE
> >     _ATOMICS_TESTS -O2 --target=bpf -c progs/pyperf180.c -mcpu=v3 -o /home/yhs/work/bpf-next/tools/testing/selftests/bpf/pyperf180.bpf.o
> >     1.      <eof> parser at end of file
> >     2.      Code generation
> >     .....
> >
> > The compilation failure only happens to cpu=v2 and cpu=v3. cpu=v4 is okay
> > since cpu=v4 supports 32-bit branch target offset.
> >
> > The above failure is due to upstream llvm patch
> >     https://reviews.llvm.org/D143624
> > where some inlining ordering are changed in the compiler.
>
> Hi Yonghong, Alexei,
>
> This is a followup for the off-list discussion. I think I have a
> relatively simple two pass algorithm that allows to replace jumps
> longer than 2**16 by series of shorter jumps using "trampoline"
> goto instructions.
>
> The basic idea of the algorithm is to:
> - Visit basic blocks sequentially from first to last (after LLVM is
>   done with figuring BB ordering), effectively splitting basic blocks
>   in two parts: "processed" and "unexplored".
> - Insert "trampoline" jumps only at "unexplored" side, thus
>   guaranteeing that distances between basic blocks on "processed" side
>   never change.
> - Maintain the list of "pending jumps":
>   - Whenever a basic block is picked from "unexplored" side
>     information about edges coming to and from this basic block is
>     added as pending jumps:
>     - backward edges are added before basic block is processed;
>     - forward edges are added after basic block is processed.
>   - Pending jump is a tuple (off,src,dst,backedge):
>     - 'src', 'dst' - basic blocks (swapped for backedges);
>     - 'off' - current distance from 'src'.
> - When a basic block is picked from "unexplored" side:
>   - discard all pending jumps that have this basic block as 'dst';
>   - peek a pending jump for which jmp.off + bb.size > MAX_JUMP_DISTANCE;
>   - if such jump is present:
>     - split basic block;
>     - insert trampoline instruction;
>     - discard pending jump and schedule new pending jump with
>       trampoline src, original dst, and off=0;
>   - if such jump is not present move basic block from "unexplored" to
>     "processed";
>   - when basic block is moved from "unexplored" side to "processed",
>     bump 'off' field of each pending jump by the size of the basic
>     block.
>
> So, the main part is to keep 'off' fields of pending jumps smaller
> than MAX_JUMP_DISTANCE by inserting trampoline jumps.
>
> I have a Python model for this algorithm at [0]. It passes a few
> hand-coded tests but I still need to do some property-based testing.
> I think I need another day to finish with testing, after that it
> should be possible to translate this code to LLVM/C++ in a couple of days.

The algorithm doesn't look simple.
Even if we change llvm to do this, it's not clear whether
the verifier will be able to consume such code.
imo it's too much effort to address a non-issue.
I'd just adjust the pyperf180.c test.

Re: bpf selftest pyperf180.c compilation failure with latest last llvm18 (in development)

[Eduard Zingerman]

On Wed, 2023-11-08 at 12:05 -0800, Alexei Starovoitov wrote:
[...]
> The algorithm doesn't look simple.
> Even if we change llvm to do this, it's not clear whether
> the verifier will be able to consume such code.

Actually, I don't think that trampoline jumps could cause any trouble.

> imo it's too much effort to address a non-issue.
> I'd just adjust the pyperf180.c test.

Ok, I'll drop this. Thank you for taking a look.

Re: bpf selftest pyperf180.c compilation failure with latest last llvm18 (in development)

[Yonghong Song]

On 11/8/23 5:20 PM, Eduard Zingerman wrote:
> On Wed, 2023-11-08 at 12:05 -0800, Alexei Starovoitov wrote:
> [...]
>> The algorithm doesn't look simple.
>> Even if we change llvm to do this, it's not clear whether
>> the verifier will be able to consume such code.
> Actually, I don't think that trampoline jumps could cause any trouble.
>
>> imo it's too much effort to address a non-issue.
>> I'd just adjust the pyperf180.c test.
> Ok, I'll drop this. Thank you for taking a look.

Thanks Eduard for doing analysis for this! I will send
a patch soon to fix selftest failure issue.