[Bug tree-optimization/101590] New: (len & - N) <= len is not optimized to 1

[Bug tree-optimization/101590] New: (len & - N) <= len is not optimized to 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

            Bug ID: 101590
           Summary: (len & - N) <= len is not optimized to 1
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: pinskia at gcc dot gnu.org
  Target Milestone: ---

#include <stddef.h>

const size_t N = 4;

bool foo(size_t len) {
        size_t newlen = len & -N;
        return newlen <= len;
}

[Bug tree-optimization/101590] (len & - N) <= len is not optimized to 1

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
it doesn't even have to be -N, any unsigned & N <= unsigned

[Bug tree-optimization/101590] (len & - N) <= len is not optimized to 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-07-27
             Status|UNCONFIRMED                 |ASSIGNED
     Ever confirmed|0                           |1
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> it doesn't even have to be -N, any unsigned & N <= unsigned

Here are the ones which are valid:

U | N < U -> false
U & N <= U -> true
U & N > U -> false
U | N >= U -> true

(for cmp (LT GE)
 (simplify
  (cmp (bit_ior @0 INTEGER_CST@1) @0)
  ({ constant_boolean_node (cmp == GE, type); })))
(for cmp (LE GT)
 (simplify
  (cmp (bit_and @0 INTEGER_CST@1) @0)
  ({ constant_boolean_node (cmp == LE, type); })))

I don't see an easy way to combine these two patterns though.

[Bug tree-optimization/101590] (len & - N) <= len is not optimized to 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #2)
> (In reply to Richard Biener from comment #1)
> > it doesn't even have to be -N, any unsigned & N <= unsigned
> 
> Here are the ones which are valid:
> 
> U | N < U -> false
> U & N <= U -> true
> U & N > U -> false
> U | N >= U -> true
> 
> (for cmp (LT GE)
>  (simplify
>   (cmp (bit_ior @0 INTEGER_CST@1) @0)
>   ({ constant_boolean_node (cmp == GE, type); })))
> (for cmp (LE GT)
>  (simplify
>   (cmp (bit_and @0 INTEGER_CST@1) @0)
>   ({ constant_boolean_node (cmp == LE, type); })))
> 
> I don't see an easy way to combine these two patterns though.

I forgot the check for unsigned :).

[Bug tree-optimization/101590] (len & - N) <= len is not optimized to 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---

U | N < U -> false
U & N <= U -> true
U & N > U -> false
U | N >= U -> true

>I don't see an easy way to combine these two patterns though.
I totally missed that the for loop is a pair for.

(for cmp   (lt      ge      le      gt     )
     bitop (bit_ior bit_ior bit_and bit_and)
 (simplify
  (cmp (bitop @0 INTEGER_CST@1) @0)
  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && TREE_UNSIGNED (TREE_TYPE (@0)))
   ({ constant_boolean_node (cmp == GE_EXPR || cmp == LE_EXPR, type); })))

[Bug tree-optimization/101590] (len & - N) <= len is not optimized to 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> U | N < U -> false
> U & N <= U -> true
> U & N > U -> false
> U | N >= U -> true
> 
> >I don't see an easy way to combine these two patterns though.
> I totally missed that the for loop is a pair for.
> 
> (for cmp   (lt      ge      le      gt     )
>      bitop (bit_ior bit_ior bit_and bit_and)
>  (simplify
>   (cmp (bitop @0 INTEGER_CST@1) @0)
>   (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && TREE_UNSIGNED (TREE_TYPE (@0)))
>    ({ constant_boolean_node (cmp == GE_EXPR || cmp == LE_EXPR, type); })))

@1 here does not even need to be a constant even ...

And that might solve PR 94884 even.

[Bug tree-optimization/101590] (len & - N) <= len is not optimized to 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
We should also handle:
int foo(int len, int N) {
        len &= 0xffff;
        N &= 0xff;
        int newlen = len & ~N;
        return newlen <= len;
}

That is 
(TREE_UNSIGNED (TREE_TYPE (@0))
 || (signbit(@0) == 0 && signbit(@1) == 0))

[Bug tree-optimization/101590] (len & - N) <= len is not optimized to 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
We could use tree_expr_nonnegative_p here .

Though I noticed that tree_single_nonnegative_warnv_p could be improved to use
nonzerobits if it is there to speed up things ...

I will handle that part seperately.

[Bug tree-optimization/101590] (len & - N) <= len is not optimized to 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So the test in the end should be:

INTEGRAL_TYPE_P (TREE_TYPE (@0)) && tree_expr_nonnegative_p (@0)

as it does not matter if @1 has the sign bit set or not. since nonzero & XYZ is
still nonzero and in this case we just need to know that `a < b` is not
dependent on a sign change happening.

[Bug tree-optimization/101590] (len & - N) <= len is not optimized to 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Just an FYI the corrected and full version (which I will be submitting later
today or tomorrow morning) is:
/*
   U & N <= U  -> true
   U & N >  U  -> false
   U needs to be non-negative.

   U | N <  U  -> false
   U | N >= U  -> true
   U and N needs to be non-negative

   U | N <  U  -> true
   U | N >= U  -> false
   U needs to be non-negative and N needs to be a negative constant.
   */
(for cmp   (lt      ge      le      gt     )
     bitop (bit_ior bit_ior bit_and bit_and)
 (simplify
  (cmp:c (bitop:c tree_expr_nonnegative_p@0 @1) @0)
  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   (if (bitop == BIT_AND_EXPR || tree_expr_nonnegative_p (@1))
    { constant_boolean_node (cmp == GE_EXPR || cmp == LE_EXPR, type); }
    /* The sign is opposite now so the comparison is swapped around. */
    (if (TREE_CODE (@1) == INTEGER_CST && wi::neg_p (wi::to_wide (@1)))
     { constant_boolean_node (cmp == LT_EXPR, type); })))))

[Bug tree-optimization/101590] (len & - N) <= len is not optimized to 1

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:a5e69e94591ae282857d59e868ff6cea7306c802

commit r14-4965-ga5e69e94591ae282857d59e868ff6cea7306c802
Author: Andrew Pinski <apinski@marvell.com>
Date:   Tue Sep 12 18:24:22 2023 -0700

    MATCH: Simplify `(X &| B) CMP X` if possible [PR 101590]

    I noticed we were missing these simplifications so let's add them.

    This adds the following simplifications:
    U & N <= U  -> true
    U & N >  U  -> false
    When U is known to be as non-negative.

    When N is also known to be non-negative, this is also true:
    U | N <  U  -> false
    U | N >= U  -> true

    When N is a negative integer, the result flips and we get:
    U | N <  U  -> true
    U | N >= U  -> false

    We could extend this later on to be the case where we know N
    is nonconstant but is known to be negative.

    Bootstrapped and tested on x86_64-linux-gnu with no regressions.

            PR tree-optimization/101590
            PR tree-optimization/94884

    gcc/ChangeLog:

            * match.pd (`(X BIT_OP Y) CMP X`): New pattern.

    gcc/testsuite/ChangeLog:

            * gcc.dg/tree-ssa/bitcmp-1.c: New test.
            * gcc.dg/tree-ssa/bitcmp-2.c: New test.
            * gcc.dg/tree-ssa/bitcmp-3.c: New test.
            * gcc.dg/tree-ssa/bitcmp-4.c: New test.
            * gcc.dg/tree-ssa/bitcmp-5.c: New test.
            * gcc.dg/tree-ssa/bitcmp-6.c: New test.

[Bug tree-optimization/101590] (len & - N) <= len is not optimized to 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101590

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
   Target Milestone|---                         |14.0
             Status|ASSIGNED                    |RESOLVED

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed.