From: Kyrylo Tkachov <[email protected]> [Apologies, resending due to problems with my email]
This series is aimed at improving zstd from SPEC2026, described as PR126035. This series has two parts. Patches 1 to 9 are mostly about the value at zero of .CLZ and .CTZ. I've tried not step over other work ongoing in this area, but I wanted to get this series out well before end of stage 1. The optional second argument V of .CLZ (x, V) and .CTZ (x, V) is the result for a zero x. Ranger, match.pd and fold_const_call use V. The expansion ignores V, so V must be the value that the target defines. During this work I found these bugs: - Patch 2: wrong ranges for counts of signed arguments. - Patch 3: the MIN of counts fold gives an ICE for vector counts and wrong code for a negative V. - Patch 4: wrong code in the CTZ compare fold for a negative V. - Patch 5: wrong code for table based counts whose entry for zero does not fit int. - Patch 7: the vectorizer can replace the value at zero of a count with the value of the target. - Patch 8: niter takes the start value of a bit count loop from a PHI that the exit test does not use. GCC 11 already miscompiles the popcount form. There is no PR for this bug. Patch 6 makes the expansion of a scalar call give V for a zero argument. If V is not the value of the target, the expansion tests the argument against zero. Jakub Jelinek proposed this in PR111280 comment 4, and Richard Biener agreed in comment 6. This fixes wrong code with offloading, x86 target_clones and narrow _BitInt types. It also gives correct code for the test case of PR127853 (table based counts on x86_64 without LZCNT). The forwprop fix for PR127853 is not in this series. Vineet Gupta handles it in that PR. Patch 9 then fixes PR111280. For a loop that shifts an IV with start value T until it is zero, niter uses T != 0 ? .CLZ (T) : PREC if the target does not define .CLZ at zero. Final value replacement evaluates .CLZ (T) also for a zero T. niter now passes PREC as the value at zero of the count. sqrtllu in gcc.c-torture/execute/920501-6.c then has 17 instead of 19 instructions on aarch64 and 23 instead of 25 on x86_64 with -march=x86-64-v3. Without LZCNT it has 29 instead of 22, because the expansion tests the argument of the count. Jakub Jelinek's comment 7 in PR111280 suggests a count whose value at zero is unspecified, which needs no test. This series does not do that. Patch 1 adds the clz_ifn and ctz_ifn effective targets for the tests. Patches 10 to 14 are for PR126035, the split form of a double-word count: lo != 0 ? ctz (lo) : 32 + ctz (hi) hi != 0 ? clz (hi) : 32 + clz (lo) GCC keeps the branch and the two narrow counts. For a nonzero value, one count of the double-word value gives the same result. The zstd sources in SPEC2026 use this form, with 32-bit table based counts for the halves. forwprop turns the table lookups into .CTZ and .CLZ counts that are defined at zero. The first version of this work matched the idiom in a dedicated phiopt function: https://gcc.gnu.org/pipermail/gcc-patches/2026-July/722878.html https://gcc.gnu.org/pipermail/gcc-patches/2026-July/722879.html As Andrea Pinski suggested in PR126035 after that posting, this version uses match.pd patterns instead. For that, match_simplify_replacement must accept conditional blocks with several statements. Patches 11 and 12 are based on Andrea's patch: https://gcc.gnu.org/pipermail/gcc-patches/2026-July/723433.html Patch 11 adds --param=phiopt-max-moved-stmts, which is 2 by default and does not count nop conversions. It also limits the moved statements to cheap integer operations. Richard Biener asked for both in: https://gcc.gnu.org/pipermail/gcc-patches/2026-July/723865.html These limits apply only to blocks with more than one statement. A block with one statement is handled as before. Patch 11 needs patch 10, which fixes a trunk bug: phiopt removes middle blocks with their debug binds, so a debugger shows an old value. Patch 12 adds bitreverse to the match.pd fold of x != 0 ? FUN (x) : 0 and removes cond_removal_in_builtin_zero_pattern, which match.pd and patch 11 then cover. A branch with a widening conversion to a _BitInt wider than any integer mode stays. Patch 13 adds the match.pd patterns for counts that are undefined at zero. Patch 14 extends them to counts that are defined at zero. Patches 13 and 14 also let early phiopt make counts, because after inlining, jump threading can hide the idiom from late phiopt. Early phiopt runs before offload streaming, so its two-argument counts need patch 6. On aarch64 the split 64-bit ctz of zstd used nine instructions with two counts. It now uses rbit, clz, cmp, mov and csel. This gives a ~3% speedup on the zstd benchmark in SPEC2026 on my aarch64 system. Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux. Each patch builds and passes the tests that it and the earlier patches add. Ok for trunk? Thanks, Kyrill Kyrylo Tkachov (14): testsuite: Add clz_ifn and ctz_ifn effective targets ranger: Fix the CLZ and CTZ ranges for signed arguments match.pd: Fix the condition of the MIN of counts fold match.pd: Fix the CTZ compare fold for a value at zero below the constant forwprop: Punt on table based counts with a zero entry outside int internal-fn: Implement the C[LT]Z value at zero for scalar calls [PR111280] vect: Check the C[LT]Z value at zero for all precisions niter: Check that bit count loops test the recurrence PHI niter: Give the complement counts a value at zero [PR111280] phiopt: Reset the debug binds of removed middle blocks phiopt: Allow match-and-simplify to move several statements of the arms [PR126035] phiopt: Remove cond_removal_in_builtin_zero_pattern match.pd: Combine split double-word clz and ctz [PR126035] match.pd: Combine split clz and ctz that are defined at zero [PR126035] gcc/doc/ifn.texi | 20 +- gcc/doc/params.texi | 7 + gcc/doc/sourcebuild.texi | 8 + gcc/gimple-match-head.cc | 31 + gcc/gimple-range-op.cc | 7 +- gcc/gimple.cc | 15 + gcc/gimple.h | 1 + gcc/internal-fn.cc | 55 +- gcc/match.pd | 111 ++- gcc/params.opt | 4 + gcc/testsuite/gcc.dg/torture/bitint-111.c | 62 ++ .../gcc.dg/torture/clz-ctz-table-2.c | 64 ++ .../gcc.dg/torture/clz-ctz-value-at-zero-1.c | 157 ++++ .../gcc.dg/torture/niter-bitcount-1.c | 66 ++ gcc/testsuite/gcc.dg/torture/pr126035-1.c | 142 ++++ gcc/testsuite/gcc.dg/torture/pr126035-2.c | 12 + gcc/testsuite/gcc.dg/torture/pr126035-3.c | 131 ++++ .../tree-ssa/clz-ctz-min-value-at-zero-1.c | 70 ++ .../gcc.dg/tree-ssa/clz-ctz-signed-1.c | 51 ++ .../gcc.dg/tree-ssa/ctz-cmp-value-at-zero-1.c | 69 ++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-53.c | 49 ++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-54.c | 52 ++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-55.c | 72 ++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-56.c | 17 + gcc/testsuite/gcc.dg/tree-ssa/phi-opt-57.c | 35 + gcc/testsuite/gcc.dg/tree-ssa/phi-opt-58.c | 29 + gcc/testsuite/gcc.dg/tree-ssa/phi-opt-59.c | 35 + gcc/testsuite/gcc.dg/tree-ssa/phi-opt-60.c | 25 + gcc/testsuite/gcc.dg/tree-ssa/phi-opt-61.c | 40 ++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-62.c | 21 + gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c | 25 + gcc/testsuite/gcc.dg/tree-ssa/pr111280.c | 63 ++ gcc/testsuite/gcc.dg/tree-ssa/pr126035-1.c | 89 +++ gcc/testsuite/gcc.dg/tree-ssa/pr126035-2.c | 69 ++ gcc/testsuite/gcc.dg/tree-ssa/pr126035-3.c | 63 ++ gcc/testsuite/gcc.dg/tree-ssa/pr126035-4.c | 31 + gcc/testsuite/gcc.dg/tree-ssa/pr126035-5.c | 51 ++ gcc/testsuite/gcc.dg/tree-ssa/pr126035-6.c | 55 ++ .../vect/bb-slp-clz-ctz-value-at-zero-1.c | 182 +++++ .../gcc.dg/vect/vect-clz-ctz-min-1.c | 27 + .../gcc.target/aarch64/clz-ctz-signed-1.c | 71 ++ .../aarch64/clz-ctz-value-at-zero-1.c | 61 ++ gcc/testsuite/gcc.target/aarch64/pr126035-1.c | 48 ++ gcc/testsuite/gcc.target/aarch64/pr126035-2.c | 65 ++ gcc/testsuite/gcc.target/aarch64/pr126035-3.c | 69 ++ .../gcc.target/i386/clzg-target-clones-1.c | 20 + gcc/testsuite/lib/target-supports.exp | 38 + gcc/tree-ssa-forwprop.cc | 11 + gcc/tree-ssa-loop-niter.cc | 85 ++- gcc/tree-ssa-phiopt.cc | 672 ++++++++---------- gcc/tree-ssa-reassoc.cc | 15 - gcc/tree-vect-patterns.cc | 43 +- 52 files changed, 2834 insertions(+), 477 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/torture/bitint-111.c create mode 100644 gcc/testsuite/gcc.dg/torture/clz-ctz-table-2.c create mode 100644 gcc/testsuite/gcc.dg/torture/clz-ctz-value-at-zero-1.c create mode 100644 gcc/testsuite/gcc.dg/torture/niter-bitcount-1.c create mode 100644 gcc/testsuite/gcc.dg/torture/pr126035-1.c create mode 100644 gcc/testsuite/gcc.dg/torture/pr126035-2.c create mode 100644 gcc/testsuite/gcc.dg/torture/pr126035-3.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/clz-ctz-min-value-at-zero-1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/clz-ctz-signed-1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ctz-cmp-value-at-zero-1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-53.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-54.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-55.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-56.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-57.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-58.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-59.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-60.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-61.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-62.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-63.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr111280.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126035-1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126035-2.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126035-3.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126035-4.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126035-5.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126035-6.c create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-clz-ctz-value-at-zero-1.c create mode 100644 gcc/testsuite/gcc.dg/vect/vect-clz-ctz-min-1.c create mode 100644 gcc/testsuite/gcc.target/aarch64/clz-ctz-signed-1.c create mode 100644 gcc/testsuite/gcc.target/aarch64/clz-ctz-value-at-zero-1.c create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-1.c create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-2.c create mode 100644 gcc/testsuite/gcc.target/aarch64/pr126035-3.c create mode 100644 gcc/testsuite/gcc.target/i386/clzg-target-clones-1.c base-commit: 8bb7a53a0df5c5c6eb41ae689cba5e1a7b814875 -- 2.34.1
