Thank you Andrea and Jeff for providing the feedback, I learned a lot while working on this issue, I'm sharing the updated patch with the following changes:
- Replaced scan counts and regexes in the testcases with exact counts matching the simplified comparison constants. - Dropped precision > 1 requirement to, this was definitely not needed as Jeff pointed out. - Used `dg-require-effective-target int32` on both testcases. - Added `INTEGRAL_TYPE_P` guards to prevent matching pointer conversions of equal precision with `nop_convert`. - Introduced `negate_maybe_without_ud` to handle both direct signed negation and unsigned negation casts `(convert (negate (nop_convert @0)))`. - Guarded with `!TYPE_OVERFLOW_TRAPS` to avoid dropping traps under -ftrapv. - Fixed `(short)` cast in `pr126627-2.c` and changed `-fdump-tree-all` to `-fdump-tree-optimized`. Test results generated via DejaGnu show the following ( briefly ) : Running /home/utam1/gcc/gcc/testsuite/gcc.dg/tree-ssa/tree-ssa.exp ... PASS: gcc.dg/tree-ssa/pr126627-2.c (test for excess errors) PASS: gcc.dg/tree-ssa/pr126627-2.c scan-tree-dump-not optimized " & " PASS: gcc.dg/tree-ssa/pr126627-2.c scan-tree-dump-times optimized " == -32768" 1 PASS: gcc.dg/tree-ssa/pr126627-2.c scan-tree-dump-times optimized " != -32768" 1 PASS: gcc.dg/tree-ssa/pr126627-2.c scan-tree-dump-times optimized " == 32768" 1 PASS: gcc.dg/tree-ssa/pr126627-2.c scan-tree-dump-times optimized " != 32768" 1 PASS: gcc.dg/tree-ssa/pr126627.c (test for excess errors) PASS: gcc.dg/tree-ssa/pr126627.c scan-tree-dump-not optimized " & " PASS: gcc.dg/tree-ssa/pr126627.c scan-tree-dump-times optimized " == -2147483648" 1 PASS: gcc.dg/tree-ssa/pr126627.c scan-tree-dump-times optimized " != -2147483648" 2 PASS: gcc.dg/tree-ssa/pr126627.c scan-tree-dump-times optimized " == 2147483648" 1 PASS: gcc.dg/tree-ssa/pr126627.c scan-tree-dump-times optimized " != 2147483648" 1 === gcc Summary === # of expected passes 12 Regression Tests on tree-ssa testsuite : make -C build/gcc check-gcc RUNTESTFLAGS="tree-ssa.exp": Result: # of expected passes: 9,194 # of expected failures: 76 Please review the updated patch below, and let me know if further improvements are needed. Kind regards Uttam Bhadauriya ------------- Patch V2 ------------- >From e75cd42ceff72c5cd247e2eb81a6f7901c728644 Mon Sep 17 00:00:00 2001 From: Uttam Singh Bhadauriya <[email protected]> Date: Sun, 11 Oct 2026 10:00:10 +0530 Subject: [PATCH] tree-optimization: Simplify (a & -a) < 0 to a == INT_MIN [PR126627] The expression (a & -a) < 0 on a signed integer (or an unsigned integer cast to a signed integer) is equivalent to checking if a is the minimum signed value for its type. The only value where the lowest set bit is the sign bit is INT_MIN. This patch introduces a simplification in match.pd to optimize this pattern into a direct equality check. It also handles the negate-in-unsigned form which avoids UB on negation, matching it using the new negate_maybe_without_ud predicate. It guards the transformation with !TYPE_OVERFLOW_TRAPS since -a could otherwise trap for INT_MIN, which would incorrectly be removed. gcc/ChangeLog: PR tree-optimization/126627 * match.pd: Simplify (a & -a) < 0 to a == INT_MIN and (a & -a) >= 0 to a != INT_MIN, using the negate_maybe_without_ud predicate to support both signed and unsigned negation. gcc/testsuite/ChangeLog: PR tree-optimization/126627 * gcc.dg/tree-ssa/pr126627.c: New test. * gcc.dg/tree-ssa/pr126627-2.c: New test. Signed-off-by: Uttam Singh Bhadauriya <[email protected]> --- gcc/match.pd | 20 ++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr126627-2.c | 15 ++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr126627.c | 24 ++++++++++++++++++++++ 3 files changed, 59 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126627-2.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126627.c diff --git a/gcc/match.pd b/gcc/match.pd index 0a4f7b718b4..4bbda205fbf 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -9269,6 +9269,26 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) && TYPE_PRECISION (TREE_TYPE (@0)) == TYPE_PRECISION (TREE_TYPE (@1))) (cmp @0 (convert @1))))) +/* (a & -a) < 0 -> a == INT_MIN + (a & -a) >= 0 -> a != INT_MIN. */ +(match (negate_maybe_without_ud @0) + (negate @0)) +(match (negate_maybe_without_ud @0) + (convert (negate (nop_convert @0))) + (if (types_match (type, @0)))) + +(for cmp (lt ge) + eqcmp (eq ne) + (simplify + (cmp (nop_convert?@0 (bit_and:c (negate_maybe_without_ud @1) @1)) + integer_zerop) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) + && INTEGRAL_TYPE_P (TREE_TYPE (@1)) + && !TYPE_UNSIGNED (TREE_TYPE (@0)) + && !TYPE_OVERFLOW_TRAPS (TREE_TYPE (@1))) + (eqcmp @1 { wide_int_to_tree (TREE_TYPE (@1), + wi::min_value (TYPE_PRECISION (TREE_TYPE (@1)), SIGNED)); })))) + /* Non-equality compare simplifications from fold_binary */ (for cmp (lt gt le ge) /* Comparisons with the highest or lowest possible integer of diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr126627-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr126627-2.c new file mode 100644 index 00000000000..ea68b8897be --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr126627-2.c @@ -0,0 +1,15 @@ +/* PR tree-optimization/126627 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-require-effective-target int32 } */ + +int test_ss (short a) { return (short)(a & -a) < 0; } +int test_ss2 (short a) { return (short)(a & -a) >= 0; } +int test_us (unsigned short a) { return (short)(a & -a) < 0; } +int test_us2 (unsigned short a) { return (short)(a & -a) >= 0; } + +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */ +/* { dg-final { scan-tree-dump-times " == -32768" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " != -32768" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " == 32768" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " != 32768" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr126627.c b/gcc/testsuite/gcc.dg/tree-ssa/pr126627.c new file mode 100644 index 00000000000..d11f5312baf --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr126627.c @@ -0,0 +1,24 @@ +/* PR tree-optimization/126627 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-require-effective-target int32 } */ + +int test1 (int a) { return (a & -a) < 0; } +int test2 (int a) { return (a & -a) >= 0; } +int test3 (unsigned a) { return (int)(a & -a) < 0; } +int test4 (unsigned a) { return (int)(a & -a) >= 0; } + +/* Negation done in unsigned to avoid UB. */ +int test_si (signed a) +{ + unsigned b = a; + b = -b; + signed t = b; + return (a & t) >= 0; +} + +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */ +/* { dg-final { scan-tree-dump-times " == -2147483648" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " != -2147483648" 2 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " == 2147483648" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " != 2147483648" 1 "optimized" } } */ -- 2.34.1 On Sun, Oct 11, 2026 at 4:11 AM Andrea Pinski <[email protected]> wrote: > > On Sat, Oct 10, 2026 at 7:00 AM Uttam Bhadauriya > <[email protected]> wrote: > > > > Hello ! > > > > I am suggesting a patch for PR126627 / tree - optimization via this email. > > > > The expression '(a & -a) < 0' on a signed integer (or an unsigned > > integer cast to a signed integer) is equivalent to checking if `a` is > > the minimum signed value for its type. The only value where the lowest > > set bit is the sign bit is 'INT_MIN'. > > > > This patch introduces a simplification in `match.pd` to optimize this > > pattern into a direct equality check ('a == INT_MIN' and 'a != > > INT_MIN'). > > > > It also explicitly guards the transformation with > > '!TYPE_OVERFLOW_TRAPS' since '-a' could otherwise trap for 'INT_MIN', > > which would incorrectly be removed if folded. > > > > This patch has been locally built and regression tested on > > 'x86_64-pc-linux-gnu' ( As per the target shown in make file ). > > > > OS : Windows 11, Version : 23H2, with WSL Ubuntu 22.04.05 LTS > > > > Hopefully this is as per the expectations of the maintainers, this > > would be my first contribution in the GCC toolchain so apologies for > > any mistakes. > > > > Kind regards > > Uttam Bhadauriya > > P.S.: Please check the patch details below. > > > > From 31ff0cbfe3481c58956c6609bb09c10444978737 Mon Sep 17 00:00:00 2001 > > From: Uttam Singh Bhadauriya <[email protected]> > > Date: Sat, 10 Oct 2026 18:57:38 +0530 > > Subject: [PATCH] tree-optimization: Simplify (a & -a) < 0 to a == INT_MIN > > [PR126627] > > > > The expression (a & -a) < 0 on a signed integer (or an unsigned integer cast > > to a signed integer) is equivalent to checking if a is the minimum signed > > value for its type. The only value where the lowest set bit is the sign bit > > is INT_MIN. This patch introduces a simplification in match.pd to optimize > > this pattern into a direct equality check. > > > > It also guards the transformation with !TYPE_OVERFLOW_TRAPS since -a could > > otherwise trap for INT_MIN, which would incorrectly be removed. > > > > gcc/ChangeLog: > > > > PR tree-optimization/126627 > > * match.pd: Simplify (a & -a) < 0 to a == INT_MIN and > > (a & -a) >= 0 to a != INT_MIN. > > > > gcc/testsuite/ChangeLog: > > > > PR tree-optimization/126627 > > * gcc.dg/tree-ssa/pr126627.c: New test. > > > > Signed-off-by: Uttam Singh Bhadauriya <[email protected]> > > --- > > gcc/match.pd | 18 +++++++++++++++++ > > gcc/testsuite/gcc.dg/tree-ssa/pr126627.c | 25 ++++++++++++++++++++++++ > > 2 files changed, 43 insertions(+) > > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126627.c > > > > diff --git a/gcc/match.pd b/gcc/match.pd > > index 0a4f7b718b4..5cc08f36e9b 100644 > > --- a/gcc/match.pd > > +++ b/gcc/match.pd > > @@ -9269,6 +9269,24 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > > && TYPE_PRECISION (TREE_TYPE (@0)) == TYPE_PRECISION (TREE_TYPE > > (@1))) > > (cmp @0 (convert @1))))) > > > > +/* (a & -a) < 0 -> a == INT_MIN > > + (a & -a) >= 0 -> a != INT_MIN */ > > +(for cmp (lt ge) > > + eqcmp (eq ne) > > + (simplify > > + (cmp (convert?@0 (bit_and:c (negate @1) @1)) integer_zerop) > > + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) > > + && INTEGRAL_TYPE_P (TREE_TYPE (@1)) > > + && TYPE_PRECISION (TREE_TYPE (@1)) > 1 > > + && TYPE_PRECISION (TREE_TYPE (@0)) == TYPE_PRECISION (TREE_TYPE > > (@1)) > > Instead of convert, use nop_convert and then you can remove the > TYPE_PRECISION==TYPE_PRECISION check since that will be true there. > > > + && !TYPE_UNSIGNED (TREE_TYPE (@0)) > > + && !TYPE_OVERFLOW_TRAPS (TREE_TYPE (@1))) > > + (with { > > + unsigned int prec = TYPE_PRECISION (TREE_TYPE (@1)); > > + wide_int min = wi::set_bit_in_zero (prec - 1, prec); > > Instead of set_bit_in_zero use `wi::min_value (prec, SIGNED)`. > > > + } > > + (eqcmp @1 { wide_int_to_tree (TREE_TYPE (@1), min); }))))) > > > > + > > /* Non-equality compare simplifications from fold_binary */ > > (for cmp (lt gt le ge) > > /* Comparisons with the highest or lowest possible integer of > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr126627.c > > b/gcc/testsuite/gcc.dg/tree-ssa/pr126627.c > > new file mode 100644 > > index 00000000000..07c91bd7862 > > --- /dev/null > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr126627.c > > @@ -0,0 +1,25 @@ > > +/* PR tree-optimization/126627 */ > > +/* { dg-do compile } */ > > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > > + > > +int test1(int a) { > > + return (a & -a) < 0; > > +} > > + > > +int test2(int a) { > > + return (a & -a) >= 0; > > +} > > + > > +int test3(unsigned int a) { > > + return (int)(a & -a) < 0; > > +} > > + > > +int test4(unsigned int a) { > > + return (int)(a & -a) >= 0; > > +} > > + > > +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */ > > +/* { dg-final { scan-tree-dump-not " < 0" "optimized" } } */ > > +/* { dg-final { scan-tree-dump-not " >= 0" "optimized" } } */ > > +/* { dg-final { scan-tree-dump-times " == -2147483648" 2 "optimized" > > { target { ilp32 || lp64 } } } } */ > > +/* { dg-final { scan-tree-dump-times " == 2147483648" 2 "optimized" { > > target { ilp32 || lp64 } } } } */ > > Just use int32 as suggested by Jeff since that will also support LLP64 > targets (aka windows). > But you should also add a testcase for short and char. > e.g.: > ``` > int test_us(unsigned short a) { > return ((short)(a & -a)) >= 0; > } > int test_ss(signed short a) { > return ((short)(a & -a)) >= 0; > } > ``` > I am less worried about long though. > You will notice with short, your match pattern does not match as there > are few extra converts so that `-a` would not introduce undefined > behavior (for short, it will promote to int) so you need to support > that case too. > Likewise this for int too: > ``` > int test_si(signed a) { > unsigned b = a; > b = -b; > signed t = b; > return (a & t) >= 0; > } > ``` > > The simplified way of doing this is something like: > (match (negate_maybe_without_ud @0) > (negate @0)) > (match (negate_maybe_without_ud @0) > (convert (negate (nop_convert @0))) > (if (types_match (TREE_TYPE (@0, type))) > > And then use negate_maybe_without_ud instead of negate. > This should simplify the pattern without adding too many optional converts. > > Thanks, > Andrea > > > > -- > > 2.34.1
