]> gcc.gnu.org Git - gcc.git/commit
Add cltz_complement idiom recognition
authorAndrew Carlotti <andrew.carlotti@arm.com>
Thu, 10 Nov 2022 15:56:51 +0000 (15:56 +0000)
committerAndrew Carlotti <andrew.carlotti@arm.com>
Mon, 16 Jan 2023 10:40:51 +0000 (10:40 +0000)
commitd347fbf774dc50bf7511f4dc6bc74547ed364995
tree03691316894f8649107eb81f2f362db4cc156fc9
parent3e087d9ab8247fa866945f156cfe3aa6dc7039ff
Add cltz_complement idiom recognition

This recognises patterns of the form:
while (n) { n >>= 1 }

This patch results in improved (but still suboptimal) codegen:

foo (unsigned int b) {
    int c = 0;

    while (b) {
        b >>= 1;
        c++;
    }

    return c;
}

foo:
.LFB11:
        .cfi_startproc
        cbz     w0, .L3
        clz     w1, w0
        tst     x0, 1
        mov     w0, 32
        sub     w0, w0, w1
        csel    w0, w0, wzr, ne
        ret

The conditional is unnecessary. phiopt could recognise a redundant csel
(using cond_removal_in_builtin_zero_pattern) when one of the inputs is a
clz call, but it cannot recognise the redunancy when the input is (e.g.)
(32 - clz).

I could perhaps extend this function to recognise this pattern in a later
patch, if this is a good place to recognise more patterns.

gcc/ChangeLog:

PR tree-optimization/94793
* tree-scalar-evolution.cc (expression_expensive_p): Add checks
for c[lt]z optabs.
* tree-ssa-loop-niter.cc (build_cltz_expr): New.
(number_of_iterations_cltz_complement): New.
(number_of_iterations_bitcount): Add call to the above.

gcc/testsuite/ChangeLog:

* lib/target-supports.exp (check_effective_target_clz)
(check_effective_target_clzl, check_effective_target_clzll)
(check_effective_target_ctz, check_effective_target_clzl)
(check_effective_target_ctzll): New.
* gcc.dg/tree-ssa/cltz-complement-max.c: New test.
* gcc.dg/tree-ssa/clz-complement-char.c: New test.
* gcc.dg/tree-ssa/clz-complement-int.c: New test.
* gcc.dg/tree-ssa/clz-complement-long-long.c: New test.
* gcc.dg/tree-ssa/clz-complement-long.c: New test.
* gcc.dg/tree-ssa/ctz-complement-char.c: New test.
* gcc.dg/tree-ssa/ctz-complement-int.c: New test.
* gcc.dg/tree-ssa/ctz-complement-long-long.c: New test.
* gcc.dg/tree-ssa/ctz-complement-long.c: New test.
12 files changed:
gcc/testsuite/gcc.dg/tree-ssa/cltz-complement-max.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/tree-ssa/clz-complement-char.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/tree-ssa/clz-complement-int.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long-long.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/tree-ssa/clz-complement-long.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-char.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-int.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long-long.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/tree-ssa/ctz-complement-long.c [new file with mode: 0644]
gcc/testsuite/lib/target-supports.exp
gcc/tree-scalar-evolution.cc
gcc/tree-ssa-loop-niter.cc
This page took 0.070154 seconds and 5 git commands to generate.