Hi! This patch resolves PR 123311, which simplifies min(clz(x), clz(y)) to clz(x | y), and similarly simplifies min(ctz(x), ctz(y)) to ctz(x | y). LLVM already implements similar optimizations.
Build and tested on x86_64-linux, ok for trunk? Thanks, Yuao
From 563e1fbec4821ff253aee76c4a78458092b32d8d Mon Sep 17 00:00:00 2001 From: Yuao Ma <[email protected]> Date: Mon, 13 Jul 2026 22:35:24 +0800 Subject: [PATCH] match.pd: Optimize min of CLZ or CTZ calls [PR tree-optimization/123311] Simplify min (clz (x), clz (y)) to clz (x | y), and similarly simplify min (ctz (x), ctz (y)) to ctz (x | y). PR tree-optimization/123311 gcc/ChangeLog: * match.pd: Add simplifications for the minimum of two CLZ or CTZ calls. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/ctz-clz-min.c: New test. --- gcc/match.pd | 30 +++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/ctz-clz-min.c | 21 +++++++++++++++ 2 files changed, 51 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ctz-clz-min.c diff --git a/gcc/match.pd b/gcc/match.pd index 9d4ab622fe5..acdeb9e8983 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -10431,6 +10431,21 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (if (ok && wi::to_wide (@1) == (TYPE_PRECISION (type0) - 1)) (op @0 { build_one_cst (type0); })))))) +/* min (clz (x), clz (y)) => clz (x | y) */ +(simplify + (min (CLZ @0) (CLZ @1)) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) + (with + { tree type = TREE_TYPE (@0); + scalar_int_mode mode = SCALAR_INT_TYPE_MODE (type); + int prec = TYPE_PRECISION (type); + int cval; + int ret = CLZ_DEFINED_VALUE_AT_ZERO (mode, cval); + bool ok = ret == 0 || cval == prec; + } + (if (ok) + (CLZ (bit_ior @0 @1)))))) + /* CTZ simplifications. */ (for ctz (CTZ) /* ctz (-X) => ctz (X). ctz (abs (X)) => ctz (X). */ @@ -10557,6 +10572,21 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) wi::shifted_mask (tree_to_uhwi (@1), 1, false, prec)); }))))))) +/* min (ctz (x), ctz (y)) => ctz (x | y) */ +(simplify + (min (CTZ @0) (CTZ @1)) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) + (with + { tree type = TREE_TYPE (@0); + scalar_int_mode mode = SCALAR_INT_TYPE_MODE (type); + int prec = TYPE_PRECISION (type); + int cval; + int ret = CTZ_DEFINED_VALUE_AT_ZERO (mode, cval); + bool ok = ret == 0 || cval == prec; + } + (if (ok) + (CTZ (bit_ior @0 @1)))))) + #if GIMPLE /* ctz(ext(X)) == ctz(X). Valid just for the UB at zero cases though. */ (simplify diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ctz-clz-min.c b/gcc/testsuite/gcc.dg/tree-ssa/ctz-clz-min.c new file mode 100644 index 00000000000..0e5f4f08a0b --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ctz-clz-min.c @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target ctz } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +unsigned int +src1 (unsigned int x, unsigned int y) +{ + return __builtin_ctzg (x) < __builtin_ctzg (y) ? __builtin_ctzg (x) + : __builtin_ctzg (y); +} + +unsigned int +src2 (unsigned int x, unsigned int y) +{ + return __builtin_clzg (x) < __builtin_clzg (y) ? __builtin_clzg (x) + : __builtin_clzg (y); +} + +/* { dg-final { scan-tree-dump-not "MIN_EXPR" "optimized" } } */ +/* { dg-final { scan-tree-dump-times "__builtin_ctz|\\.CTZ" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "__builtin_clz|\\.CLZ" 1 "optimized" } } */ -- 2.54.0
