<feed xmlns='http://www.w3.org/2005/Atom'>
<title>llvm-project.git/llvm/lib/Target/BPF/BPFMIPeephole.cpp, branch users/nico/python-2</title>
<subtitle>Unnamed repository; edit this file 'description' to name the repository.
</subtitle>
<link rel='alternate' type='text/html' href='https://git.belthelziquor.com/llvm-project.git/'/>
<entry>
<title>[BPF] Handle traps with kfunc call __bpf_trap (#131731)</title>
<updated>2025-05-27T20:34:15+00:00</updated>
<author>
<name>yonghong-song</name>
<email>yhs@fb.com</email>
</author>
<published>2025-05-27T20:34:15+00:00</published>
<link rel='alternate' type='text/html' href='https://git.belthelziquor.com/llvm-project.git/commit/?id=ab391beb11f733b526b86f9df23734a34657d876'/>
<id>ab391beb11f733b526b86f9df23734a34657d876</id>
<content type='text'>
Currently, middle-end generates 'unreachable' insn if the compiler
feels the code is indeed unreachable or the code becomes invalid
due to some optimizaiton (e.g. code optimization with uninitialized
variables).

Right now BPF backend ignores 'unreachable' insn during selectiondag
lowering. For cases where 'unreachable' is due to invalid code
transformation, such a signal will be missed. Later on, users needs
some effort to debug it which impacts developer productivity.

This patch enabled selectiondag lowering for 'unreachable' insn.

Previous attempt ([1]) tries to have a backend IR pass to filter
out 'unreachable' insns in a number of cases. But such pattern
matching may misalign with future middle-end optimization with
'unreachable' insns.

This patch takes a different approach. The 'unreachable' insn is
lowered with special encoding in bpf object file and verifier
will do proper verification for the bpf prog. More specifically,
the 'unreachable' insn is replaced by a __bpf_trap() function.
This function will be a kfunc (in ".ksyms" section) with a weak
attribute, but does not have definition. The actual kfunc definition
is expected to be in kernel. The __bpf_trap() extern function
is also encoded in BTF. The name __bpf_trap() is chosen to satisfy
reserved identifier requirement.

Besides the uninitialized variable case, the builtin function
'__builtin_trap' can also generate kfunc __bpf_trap(). For example
in [3], we have
```
  # define __bpf_unreachable()  __builtin_trap()
```
If the compiler didn't remove __builtin_trap() during middle-end
optimization, compilation will fail.

With this patch, compilation will not fail and __builtin_trap()
is converted to __bpf_trap() kfunc. The eventual failure will be
in verifier instead of llvm compilation. To keep compilation
time failure, user can add an option like `-ftrap-function=&lt;something&gt;`.

I tested this patch on bpf selftests and all tests are passed.
I also tried original example in [2] and the code looks like below:
```
          ; {
               0:       bf 16 00 00 00 00 00 00 r6 = r1
          ;       bpf_printk("Start");
               1:       18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x0 ll
                        0000000000000008:  R_BPF_64_64  .rodata
               3:       b4 02 00 00 06 00 00 00 w2 = 0x6
               4:       85 00 00 00 06 00 00 00 call 0x6
          ; DEFINE_FUNC_CTX_POINTER(data)
               5:       61 61 4c 00 00 00 00 00 w1 = *(u32 *)(r6 + 0x4c)
          ;       bpf_printk("pre ipv6_hdrlen_offset");
               6:       18 01 00 00 06 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x6 ll
                        0000000000000030:  R_BPF_64_64  .rodata
               8:       b4 02 00 00 17 00 00 00 w2 = 0x17
               9:       85 00 00 00 06 00 00 00 call 0x6
              10:       85 10 00 00 ff ff ff ff call -0x1
                        0000000000000050:  R_BPF_64_32  __bpf_trap
              11:       95 00 00 00 00 00 00 00 exit
          &lt;END&gt;
```
Eventually kernel verifier will emit the following logs:
```
      10: (85) call __bpf_trap#74479
      unexpected __bpf_trap() due to uninitialized variable?
```
In another internal sched-ext bpf prog, with the patch we have bpf code:
```
  Disassembly of section .text:
  0000000000000000 &lt;scx_storage_init_single&gt;:
  ; {
       0:       bc 13 00 00 00 00 00 00 w3 = w1
       1:       b4 01 00 00 00 00 00 00 w1 = 0x0
  ;       const u32 zero = 0;
  ...
  0000000000003a80 &lt;create_dom&gt;:
  ; {
    1872:       bc 16 00 00 00 00 00 00 w6 = w1
  ;       bpf_printk("dom_id %d", dom_id);
    1873:       18 01 00 00 3f 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x3f ll
                0000000000003a88:  R_BPF_64_64  .rodata
    1875:       b4 02 00 00 0a 00 00 00 w2 = 0xa
    1876:       bc 63 00 00 00 00 00 00 w3 = w6
    1877:       85 00 00 00 06 00 00 00 call 0x6
  ;       ret = scx_bpf_create_dsq(dom_id, 0);
    1878:       bc 61 00 00 00 00 00 00 w1 = w6
    1879:       b4 02 00 00 00 00 00 00 w2 = 0x0
    1880:       85 10 00 00 ff ff ff ff call -0x1
                0000000000003ac0:  R_BPF_64_32  scx_bpf_create_dsq
  ;       domc-&gt;node_cpumask = node_data[node_id];
    1881:       85 10 00 00 ff ff ff ff call -0x1
                0000000000003ac8:  R_BPF_64_32  __bpf_trap
    1882:       95 00 00 00 00 00 00 00 exit
    &lt;END&gt;
```
The verifier can easily report the error too.

A bpf flag `-bpf-disable-trap-unreachable` is introduced to disable
trapping for 'unreachable' or __builtin_trap.

  [1] https://github.com/llvm/llvm-project/pull/126858
  [2] https://github.com/msune/clang_bpf/blob/main/Makefile#L3
  [3] https://github.com/libbpf/libbpf/blob/master/src/bpf_helpers.h</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Currently, middle-end generates 'unreachable' insn if the compiler
feels the code is indeed unreachable or the code becomes invalid
due to some optimizaiton (e.g. code optimization with uninitialized
variables).

Right now BPF backend ignores 'unreachable' insn during selectiondag
lowering. For cases where 'unreachable' is due to invalid code
transformation, such a signal will be missed. Later on, users needs
some effort to debug it which impacts developer productivity.

This patch enabled selectiondag lowering for 'unreachable' insn.

Previous attempt ([1]) tries to have a backend IR pass to filter
out 'unreachable' insns in a number of cases. But such pattern
matching may misalign with future middle-end optimization with
'unreachable' insns.

This patch takes a different approach. The 'unreachable' insn is
lowered with special encoding in bpf object file and verifier
will do proper verification for the bpf prog. More specifically,
the 'unreachable' insn is replaced by a __bpf_trap() function.
This function will be a kfunc (in ".ksyms" section) with a weak
attribute, but does not have definition. The actual kfunc definition
is expected to be in kernel. The __bpf_trap() extern function
is also encoded in BTF. The name __bpf_trap() is chosen to satisfy
reserved identifier requirement.

Besides the uninitialized variable case, the builtin function
'__builtin_trap' can also generate kfunc __bpf_trap(). For example
in [3], we have
```
  # define __bpf_unreachable()  __builtin_trap()
```
If the compiler didn't remove __builtin_trap() during middle-end
optimization, compilation will fail.

With this patch, compilation will not fail and __builtin_trap()
is converted to __bpf_trap() kfunc. The eventual failure will be
in verifier instead of llvm compilation. To keep compilation
time failure, user can add an option like `-ftrap-function=&lt;something&gt;`.

I tested this patch on bpf selftests and all tests are passed.
I also tried original example in [2] and the code looks like below:
```
          ; {
               0:       bf 16 00 00 00 00 00 00 r6 = r1
          ;       bpf_printk("Start");
               1:       18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x0 ll
                        0000000000000008:  R_BPF_64_64  .rodata
               3:       b4 02 00 00 06 00 00 00 w2 = 0x6
               4:       85 00 00 00 06 00 00 00 call 0x6
          ; DEFINE_FUNC_CTX_POINTER(data)
               5:       61 61 4c 00 00 00 00 00 w1 = *(u32 *)(r6 + 0x4c)
          ;       bpf_printk("pre ipv6_hdrlen_offset");
               6:       18 01 00 00 06 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x6 ll
                        0000000000000030:  R_BPF_64_64  .rodata
               8:       b4 02 00 00 17 00 00 00 w2 = 0x17
               9:       85 00 00 00 06 00 00 00 call 0x6
              10:       85 10 00 00 ff ff ff ff call -0x1
                        0000000000000050:  R_BPF_64_32  __bpf_trap
              11:       95 00 00 00 00 00 00 00 exit
          &lt;END&gt;
```
Eventually kernel verifier will emit the following logs:
```
      10: (85) call __bpf_trap#74479
      unexpected __bpf_trap() due to uninitialized variable?
```
In another internal sched-ext bpf prog, with the patch we have bpf code:
```
  Disassembly of section .text:
  0000000000000000 &lt;scx_storage_init_single&gt;:
  ; {
       0:       bc 13 00 00 00 00 00 00 w3 = w1
       1:       b4 01 00 00 00 00 00 00 w1 = 0x0
  ;       const u32 zero = 0;
  ...
  0000000000003a80 &lt;create_dom&gt;:
  ; {
    1872:       bc 16 00 00 00 00 00 00 w6 = w1
  ;       bpf_printk("dom_id %d", dom_id);
    1873:       18 01 00 00 3f 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x3f ll
                0000000000003a88:  R_BPF_64_64  .rodata
    1875:       b4 02 00 00 0a 00 00 00 w2 = 0xa
    1876:       bc 63 00 00 00 00 00 00 w3 = w6
    1877:       85 00 00 00 06 00 00 00 call 0x6
  ;       ret = scx_bpf_create_dsq(dom_id, 0);
    1878:       bc 61 00 00 00 00 00 00 w1 = w6
    1879:       b4 02 00 00 00 00 00 00 w2 = 0x0
    1880:       85 10 00 00 ff ff ff ff call -0x1
                0000000000003ac0:  R_BPF_64_32  scx_bpf_create_dsq
  ;       domc-&gt;node_cpumask = node_data[node_id];
    1881:       85 10 00 00 ff ff ff ff call -0x1
                0000000000003ac8:  R_BPF_64_32  __bpf_trap
    1882:       95 00 00 00 00 00 00 00 exit
    &lt;END&gt;
```
The verifier can easily report the error too.

A bpf flag `-bpf-disable-trap-unreachable` is introduced to disable
trapping for 'unreachable' or __builtin_trap.

  [1] https://github.com/llvm/llvm-project/pull/126858
  [2] https://github.com/msune/clang_bpf/blob/main/Makefile#L3
  [3] https://github.com/libbpf/libbpf/blob/master/src/bpf_helpers.h</pre>
</div>
</content>
</entry>
<entry>
<title>[NFC][LLVM][BPF] Cleanup pass initialization for BPF (#134414)</title>
<updated>2025-04-08T00:27:26+00:00</updated>
<author>
<name>Rahul Joshi</name>
<email>rjoshi@nvidia.com</email>
</author>
<published>2025-04-08T00:27:26+00:00</published>
<link rel='alternate' type='text/html' href='https://git.belthelziquor.com/llvm-project.git/commit/?id=1356e202b2b2747220e12c2a8cbd28846bb61548'/>
<id>1356e202b2b2747220e12c2a8cbd28846bb61548</id>
<content type='text'>
- Remove calls to pass initialization from pass constructors and move
them to target initialization.
- https://github.com/llvm/llvm-project/issues/111767</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
- Remove calls to pass initialization from pass constructors and move
them to target initialization.
- https://github.com/llvm/llvm-project/issues/111767</pre>
</div>
</content>
</entry>
<entry>
<title>[BPF] Remove 'may_goto 0' instructions (#123482)</title>
<updated>2025-01-28T23:19:05+00:00</updated>
<author>
<name>yonghong-song</name>
<email>yhs@fb.com</email>
</author>
<published>2025-01-28T23:19:05+00:00</published>
<link rel='alternate' type='text/html' href='https://git.belthelziquor.com/llvm-project.git/commit/?id=8aae191cb6ad1f2dfc468975e4f5e564fea3cbfd'/>
<id>8aae191cb6ad1f2dfc468975e4f5e564fea3cbfd</id>
<content type='text'>
Emil Tsalapatis from Meta reported such a case where 'may_goto 0' insn
is generated by clang compiler. But 'may_goto 0' insn is actually a
no-op so it makes sense to remove that in llvm. The patch is also able
to handle the following code pattern
```
   ...
   may_goto 2
   may_goto 1
   may_goto 0
   ...
```
where three may_goto insns can all be removed.

---------

Co-authored-by: Yonghong Song &lt;yonghong.song@linux.dev&gt;</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Emil Tsalapatis from Meta reported such a case where 'may_goto 0' insn
is generated by clang compiler. But 'may_goto 0' insn is actually a
no-op so it makes sense to remove that in llvm. The patch is also able
to handle the following code pattern
```
   ...
   may_goto 2
   may_goto 1
   may_goto 0
   ...
```
where three may_goto insns can all be removed.

---------

Co-authored-by: Yonghong Song &lt;yonghong.song@linux.dev&gt;</pre>
</div>
</content>
</entry>
<entry>
<title>[BPF] fix sub-register handling for bpf_fastcall (#110618)</title>
<updated>2024-10-01T18:20:22+00:00</updated>
<author>
<name>eddyz87</name>
<email>eddyz87@gmail.com</email>
</author>
<published>2024-10-01T18:20:22+00:00</published>
<link rel='alternate' type='text/html' href='https://git.belthelziquor.com/llvm-project.git/commit/?id=2fca0effb4e1cbb620b7f21e9b867198ba20028a'/>
<id>2fca0effb4e1cbb620b7f21e9b867198ba20028a</id>
<content type='text'>
bpf_fastcall induced spill/fill pairs should be generated for
sub-register as well as for sub-registers. At the moment this is not the
case, e.g.:

    $ cat t.c
    extern int foo(void) __attribute__((bpf_fastcall));

    int bar(int a) {
      foo();
      return a;
    }

    $ clang --target=bpf -mcpu=v3 -O2 -S t.c -o -
    ...
    call foo
    w0 = w1
    exit

Modify BPFMIPeephole.cpp:collectBPFFastCalls() to check sub-registers
liveness and thus produce correct code for example above:

    *(u64 *)(r10 - 8) = r1
    call foo
    r1 = *(u64 *)(r10 - 8)
    w0 = w1
    exit</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
bpf_fastcall induced spill/fill pairs should be generated for
sub-register as well as for sub-registers. At the moment this is not the
case, e.g.:

    $ cat t.c
    extern int foo(void) __attribute__((bpf_fastcall));

    int bar(int a) {
      foo();
      return a;
    }

    $ clang --target=bpf -mcpu=v3 -O2 -S t.c -o -
    ...
    call foo
    w0 = w1
    exit

Modify BPFMIPeephole.cpp:collectBPFFastCalls() to check sub-registers
liveness and thus produce correct code for example above:

    *(u64 *)(r10 - 8) = r1
    call foo
    r1 = *(u64 *)(r10 - 8)
    w0 = w1
    exit</pre>
</div>
</content>
</entry>
<entry>
<title>[BPF] introduce __attribute__((bpf_fastcall)) (#105417)</title>
<updated>2024-08-22T00:40:56+00:00</updated>
<author>
<name>eddyz87</name>
<email>eddyz87@gmail.com</email>
</author>
<published>2024-08-22T00:40:56+00:00</published>
<link rel='alternate' type='text/html' href='https://git.belthelziquor.com/llvm-project.git/commit/?id=64e464349bfca0d90e07f6db2f710d4d53cdacd4'/>
<id>64e464349bfca0d90e07f6db2f710d4d53cdacd4</id>
<content type='text'>
This commit introduces attribute bpf_fastcall to declare BPF functions
that do not clobber some of the caller saved registers (R0-R5).

The idea is to generate the code complying with generic BPF ABI,
but allow compatible Linux Kernel to remove unnecessary spills and
fills of non-scratched registers (given some compiler assistance).

For such functions do register allocation as-if caller saved registers
are not clobbered, but later wrap the calls with spill and fill
patterns that are simple to recognize in kernel.

For example for the following C code:

    #define __bpf_fastcall __attribute__((bpf_fastcall))

    void bar(void) __bpf_fastcall;
    void buz(long i, long j, long k);

    void foo(long i, long j, long k) {
      bar();
      buz(i, j, k);
    }

First allocate registers as if:

    foo:
      call bar    # note: no spills for i,j,k (r1,r2,r3)
      call buz
      exit

And later insert spills fills on the peephole phase:

    foo:
      *(u64 *)(r10 - 8) = r1;  # Such call pattern is
      *(u64 *)(r10 - 16) = r2; # correct when used with
      *(u64 *)(r10 - 24) = r3; # old kernels.
      call bar
      r3 = *(u64 *)(r10 - 24); # But also allows new
      r2 = *(u64 *)(r10 - 16); # kernels to recognize the
      r1 = *(u64 *)(r10 - 8);  # pattern and remove spills/fills.
      call buz
      exit

The offsets for generated spills/fills are picked as minimal stack
offsets for the function. Allocated stack slots are not used for any
other purposes, in order to simplify in-kernel analysis.</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
This commit introduces attribute bpf_fastcall to declare BPF functions
that do not clobber some of the caller saved registers (R0-R5).

The idea is to generate the code complying with generic BPF ABI,
but allow compatible Linux Kernel to remove unnecessary spills and
fills of non-scratched registers (given some compiler assistance).

For such functions do register allocation as-if caller saved registers
are not clobbered, but later wrap the calls with spill and fill
patterns that are simple to recognize in kernel.

For example for the following C code:

    #define __bpf_fastcall __attribute__((bpf_fastcall))

    void bar(void) __bpf_fastcall;
    void buz(long i, long j, long k);

    void foo(long i, long j, long k) {
      bar();
      buz(i, j, k);
    }

First allocate registers as if:

    foo:
      call bar    # note: no spills for i,j,k (r1,r2,r3)
      call buz
      exit

And later insert spills fills on the peephole phase:

    foo:
      *(u64 *)(r10 - 8) = r1;  # Such call pattern is
      *(u64 *)(r10 - 16) = r2; # correct when used with
      *(u64 *)(r10 - 24) = r3; # old kernels.
      call bar
      r3 = *(u64 *)(r10 - 24); # But also allows new
      r2 = *(u64 *)(r10 - 16); # kernels to recognize the
      r1 = *(u64 *)(r10 - 8);  # pattern and remove spills/fills.
      call buz
      exit

The offsets for generated spills/fills are picked as minimal stack
offsets for the function. Allocated stack slots are not used for any
other purposes, in order to simplify in-kernel analysis.</pre>
</div>
</content>
</entry>
<entry>
<title>Revert "[BPF] introduce `__attribute__((bpf_fastcall))` (#101228)"</title>
<updated>2024-08-19T18:30:27+00:00</updated>
<author>
<name>Eduard Zingerman</name>
<email>eddyz87@gmail.com</email>
</author>
<published>2024-08-19T18:30:27+00:00</published>
<link rel='alternate' type='text/html' href='https://git.belthelziquor.com/llvm-project.git/commit/?id=5e8f4618ce9502190fac96eb8a856146acce2a3a'/>
<id>5e8f4618ce9502190fac96eb8a856146acce2a3a</id>
<content type='text'>
This reverts commit e9b2e16dc98345bb1b91b1a6dacb3cec85f49e31.
Reverting because of the test failure:
https://lab.llvm.org/buildbot/#/builders/187/builds/509
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
This reverts commit e9b2e16dc98345bb1b91b1a6dacb3cec85f49e31.
Reverting because of the test failure:
https://lab.llvm.org/buildbot/#/builders/187/builds/509
</pre>
</div>
</content>
</entry>
<entry>
<title>[BPF] introduce `__attribute__((bpf_fastcall))` (#101228)</title>
<updated>2024-08-19T16:49:11+00:00</updated>
<author>
<name>eddyz87</name>
<email>eddyz87@gmail.com</email>
</author>
<published>2024-08-19T16:49:11+00:00</published>
<link rel='alternate' type='text/html' href='https://git.belthelziquor.com/llvm-project.git/commit/?id=e9b2e16dc98345bb1b91b1a6dacb3cec85f49e31'/>
<id>e9b2e16dc98345bb1b91b1a6dacb3cec85f49e31</id>
<content type='text'>
This commit introduces attribute bpf_fastcall to declare BPF functions
that do not clobber some of the caller saved registers (R0-R5).

The idea is to generate the code complying with generic BPF ABI, but
allow compatible Linux Kernel to remove unnecessary spills and fills of
non-scratched registers (given some compiler assistance).

For such functions do register allocation as-if caller saved registers
are not clobbered, but later wrap the calls with spill and fill patterns
that are simple to recognize in kernel.

For example for the following C code:

     #define __bpf_fastcall __attribute__((bpf_fastcall))

     void bar(void) __bpf_fastcall;
     void buz(long i, long j, long k);

     void foo(long i, long j, long k) {
       bar();
       buz(i, j, k);
     }

First allocate registers as if:

    foo:
      call bar    # note: no spills for i,j,k (r1,r2,r3)
      call buz
      exit

And later insert spills fills on the peephole phase:

    foo:
      *(u64 *)(r10 - 8) = r1;  # Such call pattern is
      *(u64 *)(r10 - 16) = r2; # correct when used with
      *(u64 *)(r10 - 24) = r3; # old kernels.
      call bar
      r3 = *(u64 *)(r10 - 24); # But also allows new
      r2 = *(u64 *)(r10 - 16); # kernels to recognize the
      r1 = *(u64 *)(r10 - 8);  # pattern and remove spills/fills.
      call buz
      exit

The offsets for generated spills/fills are picked as minimal stack
offsets for the function. Allocated stack slots are not used for any
other purposes, in order to simplify in-kernel analysis.

Corresponding functionality had been merged in Linux Kernel as
[this](https://lore.kernel.org/bpf/172179364482.1919.9590705031832457529.git-patchwork-notify@kernel.org/)
patch set (the patch assumed that `no_caller_saved_regsiters` attribute
would be used by LLVM, naming does not matter for the Kernel).</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
This commit introduces attribute bpf_fastcall to declare BPF functions
that do not clobber some of the caller saved registers (R0-R5).

The idea is to generate the code complying with generic BPF ABI, but
allow compatible Linux Kernel to remove unnecessary spills and fills of
non-scratched registers (given some compiler assistance).

For such functions do register allocation as-if caller saved registers
are not clobbered, but later wrap the calls with spill and fill patterns
that are simple to recognize in kernel.

For example for the following C code:

     #define __bpf_fastcall __attribute__((bpf_fastcall))

     void bar(void) __bpf_fastcall;
     void buz(long i, long j, long k);

     void foo(long i, long j, long k) {
       bar();
       buz(i, j, k);
     }

First allocate registers as if:

    foo:
      call bar    # note: no spills for i,j,k (r1,r2,r3)
      call buz
      exit

And later insert spills fills on the peephole phase:

    foo:
      *(u64 *)(r10 - 8) = r1;  # Such call pattern is
      *(u64 *)(r10 - 16) = r2; # correct when used with
      *(u64 *)(r10 - 24) = r3; # old kernels.
      call bar
      r3 = *(u64 *)(r10 - 24); # But also allows new
      r2 = *(u64 *)(r10 - 16); # kernels to recognize the
      r1 = *(u64 *)(r10 - 8);  # pattern and remove spills/fills.
      call buz
      exit

The offsets for generated spills/fills are picked as minimal stack
offsets for the function. Allocated stack slots are not used for any
other purposes, in order to simplify in-kernel analysis.

Corresponding functionality had been merged in Linux Kernel as
[this](https://lore.kernel.org/bpf/172179364482.1919.9590705031832457529.git-patchwork-notify@kernel.org/)
patch set (the patch assumed that `no_caller_saved_regsiters` attribute
would be used by LLVM, naming does not matter for the Kernel).</pre>
</div>
</content>
</entry>
<entry>
<title>[BPF] Replace BPFMIPeepholeTruncElim by custom logic in isZExtFree()</title>
<updated>2023-08-21T21:04:51+00:00</updated>
<author>
<name>Eduard Zingerman</name>
<email>eddyz87@gmail.com</email>
</author>
<published>2023-08-14T13:57:29+00:00</published>
<link rel='alternate' type='text/html' href='https://git.belthelziquor.com/llvm-project.git/commit/?id=651e644595b72c22fd22f51358cf083146790ed4'/>
<id>651e644595b72c22fd22f51358cf083146790ed4</id>
<content type='text'>
Replace `BPFMIPeepholeTruncElim` by adding an overload for
`TargetLowering::isZExtFree()` aware that zero extension is
free for `ISD::LOAD`.

Short description
=================

The `BPFMIPeepholeTruncElim` handles two patterns:

Pattern #1:

    %1 = LDB %0, ...              %1 = LDB %0, ...
    %2 = AND_ri %1, 0xff      -&gt;  %2 = MOV_ri %1    &lt;-- (!)

Pattern #2:

    bb.1:                         bb.1:
      %a = LDB %0, ...              %a = LDB %0, ...
      br %bb3                       br %bb3
    bb.2:                         bb.2:
      %b = LDB %0, ...        -&gt;    %b = LDB %0, ...
      br %bb3                       br %bb3
    bb.3:                         bb.3:
      %1 = PHI %a, %b               %1 = PHI %a, %b
      %2 = AND_ri %1, 0xff          %2 = MOV_ri %1  &lt;-- (!)

Plus variations:
- AND_ri_32 instead of AND_ri
- SLL/SLR instead of AND_ri
- LDH, LDW, LDB32, LDH32, LDW32

Both patterns could be handled by built-in transformations at
instruction selection phase if suitable `isZExtFree()` implementation
is provided. The idea is borrowed from `ARMTargetLowering::isZExtFree`.

When evaluating on BPF kernel selftests and remove_truncate_*.ll LLVM
test cases this revisions performs slightly better than
BPFMIPeepholeTruncElim, see "Impact" section below for details.

Commit also adds a few test cases to make sure that patterns in
question are handled.

Long description
================

Why this works: Pattern #1
--------------------------

Consider the following example:

    define i1 @foo(ptr %p) {
    entry:
      %a = load i8, ptr %p, align 1
      %cond = icmp eq i8 %a, 0
      ret i1 %cond
    }

Log for `llc -mcpu=v2 -mtriple=bpfel -debug-only=isel` command:

    ...
    Type-legalized selection DAG: %bb.0 'foo:entry'
    SelectionDAG has 13 nodes:
      t0: ch,glue = EntryToken
              t2: i64,ch = CopyFromReg t0, Register:i64 %0
            t16: i64,ch = load&lt;(load (s8) from %ir.p), anyext from i8&gt; t0, t2, undef:i64
          t19: i64 = and t16, Constant:i64&lt;255&gt;
        t17: i64 = setcc t19, Constant:i64&lt;0&gt;, seteq:ch
      t11: ch,glue = CopyToReg t0, Register:i64 $r0, t17
      t12: ch = BPFISD::RET_GLUE t11, Register:i64 $r0, t11:1
    ...
    Replacing.1 t19: i64 = and t16, Constant:i64&lt;255&gt;
    With: t16: i64,ch = load&lt;(load (s8) from %ir.p), anyext from i8&gt; t0, t2, undef:i64
     and 0 other values
    ...
    Optimized type-legalized selection DAG: %bb.0 'foo:entry'
    SelectionDAG has 11 nodes:
      t0: ch,glue = EntryToken
            t2: i64,ch = CopyFromReg t0, Register:i64 %0
          t20: i64,ch = load&lt;(load (s8) from %ir.p), zext from i8&gt; t0, t2, undef:i64
        t17: i64 = setcc t20, Constant:i64&lt;0&gt;, seteq:ch
      t11: ch,glue = CopyToReg t0, Register:i64 $r0, t17
      t12: ch = BPFISD::RET_GLUE t11, Register:i64 $r0, t11:1
    ...

Note:
- Optimized type-legalized selection DAG:
  - `t19 = and t16, 255` had been replaced by `t16` (load).
  - Patterns like `(and (load ... i8), 255)` are replaced by `load`
    in `DAGCombiner::BackwardsPropagateMask` called from
    `DAGCombiner::visitAND`.
  - Similarly patterns like `(shl (srl ..., 56), 56)` are replaced by
    `(and ..., 255)` in `DAGCombiner::visitSRL` (this function is huge,
    look for `TLI.shouldFoldConstantShiftPairToMask()` call).

Why this works: Pattern #2
--------------------------

Consider the following example:

    define i1 @foo(ptr %p) {
    entry:
      %a = load i8, ptr %p, align 1
      br label %next

    next:
      %cond = icmp eq i8 %a, 0
      ret i1 %cond
    }

Consider log for `llc -mcpu=v2 -mtriple=bpfel -debug-only=isel` command.
Log for first basic block:

    Initial selection DAG: %bb.0 'foo:entry'
    SelectionDAG has 9 nodes:
      t0: ch,glue = EntryToken
      t3: i64 = Constant&lt;0&gt;
            t2: i64,ch = CopyFromReg t0, Register:i64 %1
          t5: i8,ch = load&lt;(load (s8) from %ir.p)&gt; t0, t2, undef:i64
        t6: i64 = zero_extend t5
      t8: ch = CopyToReg t0, Register:i64 %0, t6
    ...
    Replacing.1 t6: i64 = zero_extend t5
    With: t9: i64,ch = load&lt;(load (s8) from %ir.p), zext from i8&gt; t0, t2, undef:i64
     and 0 other values
    ...
    Optimized lowered selection DAG: %bb.0 'foo:entry'
    SelectionDAG has 7 nodes:
      t0: ch,glue = EntryToken
          t2: i64,ch = CopyFromReg t0, Register:i64 %1
        t9: i64,ch = load&lt;(load (s8) from %ir.p), zext from i8&gt; t0, t2, undef:i64
      t8: ch = CopyToReg t0, Register:i64 %0, t9

Note:
- Initial selection DAG:
  - `%a = load ...` is lowered as `t6 = (zero_extend (load ...))`
    w/o special `isZExtFree()` overload added by this commit
    it is instead lowered as `t6 = (any_extend (load ...))`.
  - The decision to generate `zero_extend` or `any_extend` is
    done in `RegsForValue::getCopyToRegs` called from
    `SelectionDAGBuilder::CopyValueToVirtualRegister`:
    - if `isZExtFree()` for load returns true `zero_extend` is used;
    - `any_extend` is used otherwise.
- Optimized lowered selection DAG:
  - `t6 = (any_extend (load ...))` is replaced by
    `t9 = load ..., zext from i8`
    This is done by `DagCombiner.cpp:tryToFoldExtOfLoad()` called from
    `DAGCombiner::visitZERO_EXTEND`.

Log for second basic block:

    Initial selection DAG: %bb.1 'foo:next'
    SelectionDAG has 13 nodes:
      t0: ch,glue = EntryToken
                t2: i64,ch = CopyFromReg t0, Register:i64 %0
              t4: i64 = AssertZext t2, ValueType:ch:i8
            t5: i8 = truncate t4
          t8: i1 = setcc t5, Constant:i8&lt;0&gt;, seteq:ch
        t9: i64 = any_extend t8
      t11: ch,glue = CopyToReg t0, Register:i64 $r0, t9
      t12: ch = BPFISD::RET_GLUE t11, Register:i64 $r0, t11:1
    ...
    Replacing.2 t18: i64 = and t4, Constant:i64&lt;255&gt;
    With: t4: i64 = AssertZext t2, ValueType:ch:i8
    ...
    Type-legalized selection DAG: %bb.1 'foo:next'
    SelectionDAG has 13 nodes:
      t0: ch,glue = EntryToken
              t2: i64,ch = CopyFromReg t0, Register:i64 %0
            t4: i64 = AssertZext t2, ValueType:ch:i8
          t18: i64 = and t4, Constant:i64&lt;255&gt;
        t16: i64 = setcc t18, Constant:i64&lt;0&gt;, seteq:ch
      t11: ch,glue = CopyToReg t0, Register:i64 $r0, t16
      t12: ch = BPFISD::RET_GLUE t11, Register:i64 $r0, t11:1
    ...
    Optimized type-legalized selection DAG: %bb.1 'foo:next'
    SelectionDAG has 11 nodes:
      t0: ch,glue = EntryToken
            t2: i64,ch = CopyFromReg t0, Register:i64 %0
          t4: i64 = AssertZext t2, ValueType:ch:i8
        t16: i64 = setcc t4, Constant:i64&lt;0&gt;, seteq:ch
      t11: ch,glue = CopyToReg t0, Register:i64 $r0, t16
      t12: ch = BPFISD::RET_GLUE t11, Register:i64 $r0, t11:1
    ...

Note:
- Initial selection DAG:
  - `t0` is an input value for this basic block, it corresponds load
    instruction (`t9`) from the first basic block.
  - It is accessed within basic block via
    `t4` (AssertZext (CopyFromReg t0, ...)).
  - The `AssertZext` is generated by RegsForValue::getCopyFromRegs
    called from SelectionDAGBuilder::getCopyFromRegs, it is generated
    only when `LiveOutInfo` with known number of leading zeros is
    present for `t0`.
  - Known register bits in `LiveOutInfo` are computed by
    `SelectionDAG::computeKnownBits` called from
    `SelectionDAGISel::ComputeLiveOutVRegInfo`.
  - `computeKnownBits()` generates leading zeros information for
    `(load ..., zext from ...)` but *does not* generate leading zeros
    information for `(load ..., anyext from ...)`.
    This is why `isZExtFree()` added in this commit is important.
- Type-legalized selection DAG:
  - `t5 = truncate t4` is replaced by `t18 = and t4, 255`
- Optimized type-legalized selection DAG:
  - `t18 = and t4, 255` is replaced by `t4`, this is done by
    `DAGCombiner::SimplifyDemandedBits` called from
    `DAGCombiner::visitAND`, which simplifies patterns like
    `(and (assertzext ...))`

Impact
------

This change covers all remove_truncate_*.ll test cases:
- for -mcpu=v4 there are no changes in the generated code;
- for -mcpu=v2 code generated for remove_truncate_7 and
  remove_truncate_8 improved slightly, for other tests it is
  unchanged.

For remove_truncate_7:

    Before this revision                 After this revision
    --------------------                 -------------------
        r1 &lt;&lt;= 0x20                          r1 &lt;&lt;= 0x20
        r1 &gt;&gt;= 0x20                          r1 &gt;&gt;= 0x20
        if r1 == 0x0 goto +0x2 &lt;LBB0_2&gt;      if r1 == 0x0 goto +0x2 &lt;LBB0_2&gt;
        r1 = *(u32 *)(r2 + 0x0)              r0 = *(u32 *)(r2 + 0x0)
        goto +0x1 &lt;LBB0_3&gt;                   goto +0x1 &lt;LBB0_3&gt;
    &lt;LBB0_2&gt;:                            &lt;LBB0_2&gt;:
        r1 = *(u32 *)(r2 + 0x4)              r0 = *(u32 *)(r2 + 0x4)
    &lt;LBB0_3&gt;:                            &lt;LBB0_3&gt;:
        r0 = r1                              exit
        exit

For remove_truncate_8:

    Before this revision                 After this revision
    --------------------                 -------------------
        r2 = *(u32 *)(r1 + 0x0)              r2 = *(u32 *)(r1 + 0x0)
        r3 = r2                              r3 = r2
        r3 &lt;&lt;= 0x20                          r3 &lt;&lt;= 0x20
        r4 = r3                              r3 s&gt;&gt;= 0x20
        r4 s&gt;&gt;= 0x20
        if r4 s&gt; 0x2 goto +0x5 &lt;LBB0_3&gt;      if r3 s&gt; 0x2 goto +0x4 &lt;LBB0_3&gt;
        r4 = *(u32 *)(r1 + 0x4)              r3 = *(u32 *)(r1 + 0x4)
        r3 &gt;&gt;= 0x20
        if r3 &gt;= r4 goto +0x2 &lt;LBB0_3&gt;       if r2 &gt;= r3 goto +0x2 &lt;LBB0_3&gt;
        r2 += 0x2                            r2 += 0x2
        *(u32 *)(r1 + 0x0) = r2              *(u32 *)(r1 + 0x0) = r2
    &lt;LBB0_3&gt;:                            &lt;LBB0_3&gt;:
        r0 = 0x3                             r0 = 0x3
        exit                                 exit

For kernel BPF selftests statistics is as follows: (-mcpu=v4):
- For -mcpu=v4: 9 out of 655 object files have differences,
  in all cases total number of instructions marginally decreased
  (-27 instructions).
- For -mcpu=v2: 9 out of 655 object files have differences:
  - For 19 object files number of instruction decreased
    (-129 instruction in total): some redundant `rX &amp;= 0xffff`
    and register to register assignments removed;
  - For 2 object files number of instructions increased +2
    instructions in each file.

Both -mcpu=v2 instruction increases could be reduced to the same
example:

    define void @foo(ptr %p) {
    entry:
      %a = load i32, ptr %p, align 4
      %b = sext i32 %a to i64
      %c = icmp ult i64 1, %b
      br i1 %c, label %next, label %end

    next:
      call void inttoptr (i64 62 to ptr)(i32 %a)
      br label %end

    end:
      ret void
    }

Note that this example uses value loaded to `%a` both as a sign
extended (`%b`) and as zero extended (`%a` passed as parameter).
Here is the difference in final assembly code:

    Before this revision          After this revision
    --------------------          -------------------
        r1 = *(u32 *)(r1 + 0)         r1 = *(u32 *)(r1 + 0)
        r1 &lt;&lt;= 32                     r1 &lt;&lt;= 32
        r1 s&gt;&gt;= 32                    r1 s&gt;&gt;= 32
        if r1 &lt; 2 goto &lt;LBB0_2&gt;       if r1 &lt; 2 goto &lt;LBB0_2&gt;
                                      r1 &lt;&lt;= 32
                                      r1 &gt;&gt;= 32
        call 62                       call 62
    &lt;LBB0_2&gt;:                     &lt;LBB0_2&gt;:
        exit                          exit

Before this commit `%a` is passed to call as a sign extended value,
after this commit `%a` is passed to call as a zero extended value,
both are correct as 32-bit sub-register is the same.

The difference comes from `DAGCombiner` operation on the initial DAG:

Initial selection DAG before this commit:

    t5: i32,ch = load&lt;(load (s32) from %ir.p)&gt; t0, t2, undef:i64
          t6: i64 = any_extend t5         &lt;--------------------- (1)
        t8: ch = CopyToReg t0, Register:i64 %0, t6
            t9: i64 = sign_extend t5
          t12: i1 = setcc Constant:i64&lt;1&gt;, t9, setult:ch

Initial selection DAG after this commit:

    t5: i32,ch = load&lt;(load (s32) from %ir.p)&gt; t0, t2, undef:i64
          t6: i64 = zero_extend t5        &lt;--------------------- (2)
        t8: ch = CopyToReg t0, Register:i64 %0, t6
            t9: i64 = sign_extend t5
          t12: i1 = setcc Constant:i64&lt;1&gt;, t9, setult:ch

The node `t9` is processed before node `t6` and `load` instruction is
combined to load with sign extension:

    Replacing.1 t9: i64 = sign_extend t5
    With: t30: i64,ch = load&lt;(load (s32) from %ir.p), sext from i32&gt; t0, t2, undef:i64
     and 0 other values
    Replacing.1 t5: i32,ch = load&lt;(load (s32) from %ir.p)&gt; t0, t2, undef:i64
    With: t31: i32 = truncate t30
     and 1 other values

This is done by `DAGCombiner.cpp:tryToFoldExtOfLoad` called from
`DAGCombiner::visitSIGN_EXTEND`. Note that `t5` is used by `t6` which
is `any_extend` in (1) and `zero_extend` in (2).
`tryToFoldExtOfLoad()` rewrites such uses of `t5` differently:
- `any_extend` is simply removed
- `zero_extend` is replaced by `and t30, 0xffffffff`, which is later
  converted to a pair of shifts. This pair of shifts survives till the
  end of translation.

Differential Revision: https://reviews.llvm.org/D157870
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Replace `BPFMIPeepholeTruncElim` by adding an overload for
`TargetLowering::isZExtFree()` aware that zero extension is
free for `ISD::LOAD`.

Short description
=================

The `BPFMIPeepholeTruncElim` handles two patterns:

Pattern #1:

    %1 = LDB %0, ...              %1 = LDB %0, ...
    %2 = AND_ri %1, 0xff      -&gt;  %2 = MOV_ri %1    &lt;-- (!)

Pattern #2:

    bb.1:                         bb.1:
      %a = LDB %0, ...              %a = LDB %0, ...
      br %bb3                       br %bb3
    bb.2:                         bb.2:
      %b = LDB %0, ...        -&gt;    %b = LDB %0, ...
      br %bb3                       br %bb3
    bb.3:                         bb.3:
      %1 = PHI %a, %b               %1 = PHI %a, %b
      %2 = AND_ri %1, 0xff          %2 = MOV_ri %1  &lt;-- (!)

Plus variations:
- AND_ri_32 instead of AND_ri
- SLL/SLR instead of AND_ri
- LDH, LDW, LDB32, LDH32, LDW32

Both patterns could be handled by built-in transformations at
instruction selection phase if suitable `isZExtFree()` implementation
is provided. The idea is borrowed from `ARMTargetLowering::isZExtFree`.

When evaluating on BPF kernel selftests and remove_truncate_*.ll LLVM
test cases this revisions performs slightly better than
BPFMIPeepholeTruncElim, see "Impact" section below for details.

Commit also adds a few test cases to make sure that patterns in
question are handled.

Long description
================

Why this works: Pattern #1
--------------------------

Consider the following example:

    define i1 @foo(ptr %p) {
    entry:
      %a = load i8, ptr %p, align 1
      %cond = icmp eq i8 %a, 0
      ret i1 %cond
    }

Log for `llc -mcpu=v2 -mtriple=bpfel -debug-only=isel` command:

    ...
    Type-legalized selection DAG: %bb.0 'foo:entry'
    SelectionDAG has 13 nodes:
      t0: ch,glue = EntryToken
              t2: i64,ch = CopyFromReg t0, Register:i64 %0
            t16: i64,ch = load&lt;(load (s8) from %ir.p), anyext from i8&gt; t0, t2, undef:i64
          t19: i64 = and t16, Constant:i64&lt;255&gt;
        t17: i64 = setcc t19, Constant:i64&lt;0&gt;, seteq:ch
      t11: ch,glue = CopyToReg t0, Register:i64 $r0, t17
      t12: ch = BPFISD::RET_GLUE t11, Register:i64 $r0, t11:1
    ...
    Replacing.1 t19: i64 = and t16, Constant:i64&lt;255&gt;
    With: t16: i64,ch = load&lt;(load (s8) from %ir.p), anyext from i8&gt; t0, t2, undef:i64
     and 0 other values
    ...
    Optimized type-legalized selection DAG: %bb.0 'foo:entry'
    SelectionDAG has 11 nodes:
      t0: ch,glue = EntryToken
            t2: i64,ch = CopyFromReg t0, Register:i64 %0
          t20: i64,ch = load&lt;(load (s8) from %ir.p), zext from i8&gt; t0, t2, undef:i64
        t17: i64 = setcc t20, Constant:i64&lt;0&gt;, seteq:ch
      t11: ch,glue = CopyToReg t0, Register:i64 $r0, t17
      t12: ch = BPFISD::RET_GLUE t11, Register:i64 $r0, t11:1
    ...

Note:
- Optimized type-legalized selection DAG:
  - `t19 = and t16, 255` had been replaced by `t16` (load).
  - Patterns like `(and (load ... i8), 255)` are replaced by `load`
    in `DAGCombiner::BackwardsPropagateMask` called from
    `DAGCombiner::visitAND`.
  - Similarly patterns like `(shl (srl ..., 56), 56)` are replaced by
    `(and ..., 255)` in `DAGCombiner::visitSRL` (this function is huge,
    look for `TLI.shouldFoldConstantShiftPairToMask()` call).

Why this works: Pattern #2
--------------------------

Consider the following example:

    define i1 @foo(ptr %p) {
    entry:
      %a = load i8, ptr %p, align 1
      br label %next

    next:
      %cond = icmp eq i8 %a, 0
      ret i1 %cond
    }

Consider log for `llc -mcpu=v2 -mtriple=bpfel -debug-only=isel` command.
Log for first basic block:

    Initial selection DAG: %bb.0 'foo:entry'
    SelectionDAG has 9 nodes:
      t0: ch,glue = EntryToken
      t3: i64 = Constant&lt;0&gt;
            t2: i64,ch = CopyFromReg t0, Register:i64 %1
          t5: i8,ch = load&lt;(load (s8) from %ir.p)&gt; t0, t2, undef:i64
        t6: i64 = zero_extend t5
      t8: ch = CopyToReg t0, Register:i64 %0, t6
    ...
    Replacing.1 t6: i64 = zero_extend t5
    With: t9: i64,ch = load&lt;(load (s8) from %ir.p), zext from i8&gt; t0, t2, undef:i64
     and 0 other values
    ...
    Optimized lowered selection DAG: %bb.0 'foo:entry'
    SelectionDAG has 7 nodes:
      t0: ch,glue = EntryToken
          t2: i64,ch = CopyFromReg t0, Register:i64 %1
        t9: i64,ch = load&lt;(load (s8) from %ir.p), zext from i8&gt; t0, t2, undef:i64
      t8: ch = CopyToReg t0, Register:i64 %0, t9

Note:
- Initial selection DAG:
  - `%a = load ...` is lowered as `t6 = (zero_extend (load ...))`
    w/o special `isZExtFree()` overload added by this commit
    it is instead lowered as `t6 = (any_extend (load ...))`.
  - The decision to generate `zero_extend` or `any_extend` is
    done in `RegsForValue::getCopyToRegs` called from
    `SelectionDAGBuilder::CopyValueToVirtualRegister`:
    - if `isZExtFree()` for load returns true `zero_extend` is used;
    - `any_extend` is used otherwise.
- Optimized lowered selection DAG:
  - `t6 = (any_extend (load ...))` is replaced by
    `t9 = load ..., zext from i8`
    This is done by `DagCombiner.cpp:tryToFoldExtOfLoad()` called from
    `DAGCombiner::visitZERO_EXTEND`.

Log for second basic block:

    Initial selection DAG: %bb.1 'foo:next'
    SelectionDAG has 13 nodes:
      t0: ch,glue = EntryToken
                t2: i64,ch = CopyFromReg t0, Register:i64 %0
              t4: i64 = AssertZext t2, ValueType:ch:i8
            t5: i8 = truncate t4
          t8: i1 = setcc t5, Constant:i8&lt;0&gt;, seteq:ch
        t9: i64 = any_extend t8
      t11: ch,glue = CopyToReg t0, Register:i64 $r0, t9
      t12: ch = BPFISD::RET_GLUE t11, Register:i64 $r0, t11:1
    ...
    Replacing.2 t18: i64 = and t4, Constant:i64&lt;255&gt;
    With: t4: i64 = AssertZext t2, ValueType:ch:i8
    ...
    Type-legalized selection DAG: %bb.1 'foo:next'
    SelectionDAG has 13 nodes:
      t0: ch,glue = EntryToken
              t2: i64,ch = CopyFromReg t0, Register:i64 %0
            t4: i64 = AssertZext t2, ValueType:ch:i8
          t18: i64 = and t4, Constant:i64&lt;255&gt;
        t16: i64 = setcc t18, Constant:i64&lt;0&gt;, seteq:ch
      t11: ch,glue = CopyToReg t0, Register:i64 $r0, t16
      t12: ch = BPFISD::RET_GLUE t11, Register:i64 $r0, t11:1
    ...
    Optimized type-legalized selection DAG: %bb.1 'foo:next'
    SelectionDAG has 11 nodes:
      t0: ch,glue = EntryToken
            t2: i64,ch = CopyFromReg t0, Register:i64 %0
          t4: i64 = AssertZext t2, ValueType:ch:i8
        t16: i64 = setcc t4, Constant:i64&lt;0&gt;, seteq:ch
      t11: ch,glue = CopyToReg t0, Register:i64 $r0, t16
      t12: ch = BPFISD::RET_GLUE t11, Register:i64 $r0, t11:1
    ...

Note:
- Initial selection DAG:
  - `t0` is an input value for this basic block, it corresponds load
    instruction (`t9`) from the first basic block.
  - It is accessed within basic block via
    `t4` (AssertZext (CopyFromReg t0, ...)).
  - The `AssertZext` is generated by RegsForValue::getCopyFromRegs
    called from SelectionDAGBuilder::getCopyFromRegs, it is generated
    only when `LiveOutInfo` with known number of leading zeros is
    present for `t0`.
  - Known register bits in `LiveOutInfo` are computed by
    `SelectionDAG::computeKnownBits` called from
    `SelectionDAGISel::ComputeLiveOutVRegInfo`.
  - `computeKnownBits()` generates leading zeros information for
    `(load ..., zext from ...)` but *does not* generate leading zeros
    information for `(load ..., anyext from ...)`.
    This is why `isZExtFree()` added in this commit is important.
- Type-legalized selection DAG:
  - `t5 = truncate t4` is replaced by `t18 = and t4, 255`
- Optimized type-legalized selection DAG:
  - `t18 = and t4, 255` is replaced by `t4`, this is done by
    `DAGCombiner::SimplifyDemandedBits` called from
    `DAGCombiner::visitAND`, which simplifies patterns like
    `(and (assertzext ...))`

Impact
------

This change covers all remove_truncate_*.ll test cases:
- for -mcpu=v4 there are no changes in the generated code;
- for -mcpu=v2 code generated for remove_truncate_7 and
  remove_truncate_8 improved slightly, for other tests it is
  unchanged.

For remove_truncate_7:

    Before this revision                 After this revision
    --------------------                 -------------------
        r1 &lt;&lt;= 0x20                          r1 &lt;&lt;= 0x20
        r1 &gt;&gt;= 0x20                          r1 &gt;&gt;= 0x20
        if r1 == 0x0 goto +0x2 &lt;LBB0_2&gt;      if r1 == 0x0 goto +0x2 &lt;LBB0_2&gt;
        r1 = *(u32 *)(r2 + 0x0)              r0 = *(u32 *)(r2 + 0x0)
        goto +0x1 &lt;LBB0_3&gt;                   goto +0x1 &lt;LBB0_3&gt;
    &lt;LBB0_2&gt;:                            &lt;LBB0_2&gt;:
        r1 = *(u32 *)(r2 + 0x4)              r0 = *(u32 *)(r2 + 0x4)
    &lt;LBB0_3&gt;:                            &lt;LBB0_3&gt;:
        r0 = r1                              exit
        exit

For remove_truncate_8:

    Before this revision                 After this revision
    --------------------                 -------------------
        r2 = *(u32 *)(r1 + 0x0)              r2 = *(u32 *)(r1 + 0x0)
        r3 = r2                              r3 = r2
        r3 &lt;&lt;= 0x20                          r3 &lt;&lt;= 0x20
        r4 = r3                              r3 s&gt;&gt;= 0x20
        r4 s&gt;&gt;= 0x20
        if r4 s&gt; 0x2 goto +0x5 &lt;LBB0_3&gt;      if r3 s&gt; 0x2 goto +0x4 &lt;LBB0_3&gt;
        r4 = *(u32 *)(r1 + 0x4)              r3 = *(u32 *)(r1 + 0x4)
        r3 &gt;&gt;= 0x20
        if r3 &gt;= r4 goto +0x2 &lt;LBB0_3&gt;       if r2 &gt;= r3 goto +0x2 &lt;LBB0_3&gt;
        r2 += 0x2                            r2 += 0x2
        *(u32 *)(r1 + 0x0) = r2              *(u32 *)(r1 + 0x0) = r2
    &lt;LBB0_3&gt;:                            &lt;LBB0_3&gt;:
        r0 = 0x3                             r0 = 0x3
        exit                                 exit

For kernel BPF selftests statistics is as follows: (-mcpu=v4):
- For -mcpu=v4: 9 out of 655 object files have differences,
  in all cases total number of instructions marginally decreased
  (-27 instructions).
- For -mcpu=v2: 9 out of 655 object files have differences:
  - For 19 object files number of instruction decreased
    (-129 instruction in total): some redundant `rX &amp;= 0xffff`
    and register to register assignments removed;
  - For 2 object files number of instructions increased +2
    instructions in each file.

Both -mcpu=v2 instruction increases could be reduced to the same
example:

    define void @foo(ptr %p) {
    entry:
      %a = load i32, ptr %p, align 4
      %b = sext i32 %a to i64
      %c = icmp ult i64 1, %b
      br i1 %c, label %next, label %end

    next:
      call void inttoptr (i64 62 to ptr)(i32 %a)
      br label %end

    end:
      ret void
    }

Note that this example uses value loaded to `%a` both as a sign
extended (`%b`) and as zero extended (`%a` passed as parameter).
Here is the difference in final assembly code:

    Before this revision          After this revision
    --------------------          -------------------
        r1 = *(u32 *)(r1 + 0)         r1 = *(u32 *)(r1 + 0)
        r1 &lt;&lt;= 32                     r1 &lt;&lt;= 32
        r1 s&gt;&gt;= 32                    r1 s&gt;&gt;= 32
        if r1 &lt; 2 goto &lt;LBB0_2&gt;       if r1 &lt; 2 goto &lt;LBB0_2&gt;
                                      r1 &lt;&lt;= 32
                                      r1 &gt;&gt;= 32
        call 62                       call 62
    &lt;LBB0_2&gt;:                     &lt;LBB0_2&gt;:
        exit                          exit

Before this commit `%a` is passed to call as a sign extended value,
after this commit `%a` is passed to call as a zero extended value,
both are correct as 32-bit sub-register is the same.

The difference comes from `DAGCombiner` operation on the initial DAG:

Initial selection DAG before this commit:

    t5: i32,ch = load&lt;(load (s32) from %ir.p)&gt; t0, t2, undef:i64
          t6: i64 = any_extend t5         &lt;--------------------- (1)
        t8: ch = CopyToReg t0, Register:i64 %0, t6
            t9: i64 = sign_extend t5
          t12: i1 = setcc Constant:i64&lt;1&gt;, t9, setult:ch

Initial selection DAG after this commit:

    t5: i32,ch = load&lt;(load (s32) from %ir.p)&gt; t0, t2, undef:i64
          t6: i64 = zero_extend t5        &lt;--------------------- (2)
        t8: ch = CopyToReg t0, Register:i64 %0, t6
            t9: i64 = sign_extend t5
          t12: i1 = setcc Constant:i64&lt;1&gt;, t9, setult:ch

The node `t9` is processed before node `t6` and `load` instruction is
combined to load with sign extension:

    Replacing.1 t9: i64 = sign_extend t5
    With: t30: i64,ch = load&lt;(load (s32) from %ir.p), sext from i32&gt; t0, t2, undef:i64
     and 0 other values
    Replacing.1 t5: i32,ch = load&lt;(load (s32) from %ir.p)&gt; t0, t2, undef:i64
    With: t31: i32 = truncate t30
     and 1 other values

This is done by `DAGCombiner.cpp:tryToFoldExtOfLoad` called from
`DAGCombiner::visitSIGN_EXTEND`. Note that `t5` is used by `t6` which
is `any_extend` in (1) and `zero_extend` in (2).
`tryToFoldExtOfLoad()` rewrites such uses of `t5` differently:
- `any_extend` is simply removed
- `zero_extend` is replaced by `and t30, 0xffffffff`, which is later
  converted to a pair of shifts. This pair of shifts survives till the
  end of translation.

Differential Revision: https://reviews.llvm.org/D157870
</pre>
</div>
</content>
</entry>
<entry>
<title>[BPF] Add a few new insns under cpu=v4</title>
<updated>2023-07-26T15:37:30+00:00</updated>
<author>
<name>Yonghong Song</name>
<email>yhs@fb.com</email>
</author>
<published>2022-08-29T01:12:28+00:00</published>
<link rel='alternate' type='text/html' href='https://git.belthelziquor.com/llvm-project.git/commit/?id=6c412b6c6faa2dabd8602d35d3f5e796fb1daf80'/>
<id>6c412b6c6faa2dabd8602d35d3f5e796fb1daf80</id>
<content type='text'>
In [1], a few new insns are proposed to expand BPF ISA to
  . fixing the limitation of existing insn (e.g., 16bit jmp offset)
  . adding new insns which may improve code quality
    (sign_ext_ld, sign_ext_mov, st)
  . feature complete (sdiv, smod)
  . better user experience (bswap)

This patch implemented insn encoding for
  . sign-extended load
  . sign-extended mov
  . sdiv/smod
  . bswap insns
  . unconditional jump with 32bit offset

The new bswap insns are generated under cpu=v4 for __builtin_bswap.
For cpu=v3 or earlier, for __builtin_bswap, be or le insns are generated
which is not intuitive for the user.

To support 32-bit branch offset, a 32-bit ja (JMPL) insn is implemented.
For conditional branch which is beyond 16-bit offset, llvm will do
some transformation 'cond_jmp' -&gt; 'cond_jmp + jmpl' to simulate 32bit
conditional jmp. See BPFMIPeephole.cpp for details. The algorithm is
hueristic based. I have tested bpf selftest pyperf600 with unroll account
600 which can indeed generate 32-bit jump insn, e.g.,
        13:       06 00 00 00 9b cd 00 00 gotol +0xcd9b &lt;LBB0_6619&gt;

Eduard is working on to add 'st' insn to cpu=v4.

A list of llc flags:
  disable-ldsx, disable-movsx, disable-bswap,
  disable-sdiv-smod, disable-gotol
can be used to disable a particular insn for cpu v4.
For example, user can do:
  llc -march=bpf -mcpu=v4 -disable-movsx t.ll
to enable cpu v4 without movsx insns.

References:
  [1] https://lore.kernel.org/bpf/4bfe98be-5333-1c7e-2f6d-42486c8ec039@meta.com/

Differential Revision: https://reviews.llvm.org/D144829
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
In [1], a few new insns are proposed to expand BPF ISA to
  . fixing the limitation of existing insn (e.g., 16bit jmp offset)
  . adding new insns which may improve code quality
    (sign_ext_ld, sign_ext_mov, st)
  . feature complete (sdiv, smod)
  . better user experience (bswap)

This patch implemented insn encoding for
  . sign-extended load
  . sign-extended mov
  . sdiv/smod
  . bswap insns
  . unconditional jump with 32bit offset

The new bswap insns are generated under cpu=v4 for __builtin_bswap.
For cpu=v3 or earlier, for __builtin_bswap, be or le insns are generated
which is not intuitive for the user.

To support 32-bit branch offset, a 32-bit ja (JMPL) insn is implemented.
For conditional branch which is beyond 16-bit offset, llvm will do
some transformation 'cond_jmp' -&gt; 'cond_jmp + jmpl' to simulate 32bit
conditional jmp. See BPFMIPeephole.cpp for details. The algorithm is
hueristic based. I have tested bpf selftest pyperf600 with unroll account
600 which can indeed generate 32-bit jump insn, e.g.,
        13:       06 00 00 00 9b cd 00 00 gotol +0xcd9b &lt;LBB0_6619&gt;

Eduard is working on to add 'st' insn to cpu=v4.

A list of llc flags:
  disable-ldsx, disable-movsx, disable-bswap,
  disable-sdiv-smod, disable-gotol
can be used to disable a particular insn for cpu v4.
For example, user can do:
  llc -march=bpf -mcpu=v4 -disable-movsx t.ll
to enable cpu v4 without movsx insns.

References:
  [1] https://lore.kernel.org/bpf/4bfe98be-5333-1c7e-2f6d-42486c8ec039@meta.com/

Differential Revision: https://reviews.llvm.org/D144829
</pre>
</div>
</content>
</entry>
<entry>
<title>[CodeGen][Target] Remove uses of Register::isPhysicalRegister/isVirtualRegister. NFC</title>
<updated>2023-01-14T07:12:48+00:00</updated>
<author>
<name>Craig Topper</name>
<email>craig.topper@sifive.com</email>
</author>
<published>2023-01-14T06:57:36+00:00</published>
<link rel='alternate' type='text/html' href='https://git.belthelziquor.com/llvm-project.git/commit/?id=79858d1908b53560941b7d8f4d98e5ac781c674b'/>
<id>79858d1908b53560941b7d8f4d98e5ac781c674b</id>
<content type='text'>
Use isPhysical/isVirtual methods.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Use isPhysical/isVirtual methods.
</pre>
</div>
</content>
</entry>
</feed>
