[Bug tree-optimization/99079] New: Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[Bug tree-optimization/99079] New: Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[marxin at gcc dot gnu.org]

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

            Bug ID: 99079
           Summary: Maybe a wrong code since r6-1462-g4ab1e111ef0669bb
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: marxin at gcc dot gnu.org
                CC: rguenth at gcc dot gnu.org
  Target Milestone: ---

Since the revision, we optimize the following in a different way:

$ cat x.cpp
unsigned long var = 31;
unsigned long arr;

static void test()
{
  unsigned long s = 1 << var;
  arr = 4897637220ULL % s;
}

int main()
{
  test();
  __builtin_printf ("arr: %ld\n", arr);
  if (arr != 4897637220ULL)
    __builtin_abort();
  return 0;
}

$ g++ x.cpp && ./a.out 
arr: 4897637220
$ g++ x.cpp && ./a.out 
arr: 4897637220

Clang is fine with the test-case:
$ clang++ x.cpp -O3 && ./a.out 
arr: 4897637220

and ICC as well.

[Bug tree-optimization/99079] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[marxin at gcc dot gnu.org]

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

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
I forgot to mention:
$ g++ x.cpp -O && ./a.out 
arr: 602669924
Aborted (core dumped)

[Bug tree-optimization/99079] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org
             Status|UNCONFIRMED                 |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
   Last reconfirmed|                            |2021-02-12
   Target Milestone|---                         |8.5
     Ever confirmed|0                           |1
           Priority|P3                          |P2

[Bug tree-optimization/99079] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 50175
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50175&action=edit
gcc11-pr99079.patch

Untested fix.
The problem is that the tree_nop_conversion_p (type, TREE_TYPE (@3))
test actually didn't test what it was meant to test, in
(mod @0 (convert?@3 (...)))
TREE_TYPE (@3) is the type of the second argument of the modulo, so
necessarily compatible with type (compatible also with TREE_TYPE (@0)).
But, I think we actually don't need to require only nop conversions, which are
certainly fine.
If the conversion is narrowing, i.e. TREE_TYPE (@1) is wider than type, then
we know that @1 is some power of two and after the cast, it will be either 0
(but then UB, so we can rule that out), or that power of two.
For widening conversion where TREE_TYPE (@1) is unsigned it is also fine,
@1 will be some power of two (0 being UB) and @1 - 1 is a mask we can use after
widening it to the type of the mod.
The only problematic case is widening conversion where TREE_TYPE (@1) is
signed,
as the testcase shows, if the power of two is negative, i.e. msb set and all
other bits clear, then the widening cast turns that into 0xffffffff80000000
(if type is unsigned) and as that is not a power of two, we can't transform it
into a mask by 0x7fffffff.

[Bug tree-optimization/99079] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #50175|0                           |1
        is obsolete|                            |

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 50176
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50176&action=edit
gcc11-pr99079.patch

Updated patch.  Actually, I think widening conversion from signed TREE_TYPE
(@1)
to signed type is fine too.
In the problematic case where @1 is negative (i.e. powerof2 << var which shifts
it into the sign bit, certainly valid at least in C++20), if we say have int to
long long conversion and we know the dividend is non-negative, it would be
@0 % (long long) INT_MIN, i.e. @0 % -0x80000000LL and that can still be
expanded
as @0 & 0x7fffffffLL.

[Bug tree-optimization/99079] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Ah, except we introduce UB into the program because (1 << var) - 1 when var is
31 will be INT_MIN - 1.  I think we should do the subtraction of 1 in utype
then.

[Bug tree-optimization/99079] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #50176|0                           |1
        is obsolete|                            |

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 50177
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50177&action=edit
gcc11-pr99079.patch

Yet another patch update to avoid introducing the UB when there was none.

[Bug tree-optimization/99079] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:70099a6acf5169eca55ef74549fb64de14e668f0

commit r11-7242-g70099a6acf5169eca55ef74549fb64de14e668f0
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Feb 15 09:16:06 2021 +0100

    match.pd: Fix up A % (cast) (pow2cst << B) simplification [PR99079]

    The (mod @0 (convert?@3 (power_of_two_cand@1 @2))) simplification
    uses tree_nop_conversion_p (type, TREE_TYPE (@3)) condition, but I believe
    it doesn't check what it was meant to check.  On convert?@3
    TREE_TYPE (@3) is not the type of what it has been converted from, but
    what it has been converted to, which needs to be (because it is operand
    of normal binary operation) equal or compatible to type of the modulo
    result and first operand - type.
    I could fix that by using && tree_nop_conversion_p (type, TREE_TYPE (@1))
    and be done with it, but actually most of the non-nop conversions are IMHO
    ok and so we would regress those optimizations.
    In particular, if we have say narrowing conversions (foo5 and foo6 in
    the new testcase), I think we are fine, either the shift of the power of
two
    constant after narrowing conversion is still that power of two (or negation
    of that) and then it will still work, or the result of narrowing conversion
    is 0 and then we would have UB which we can ignore.
    Similarly, widening conversions where the shift result is unsigned are
fine,
    or even widening conversions where the shift result is signed, but we sign
    extend to a signed wider divisor, the problematic case of INT_MIN will
    become x % (long long) INT_MIN and we can still optimize that to
    x & (long long) INT_MAX.
    What doesn't work is the case in the pr99079.c testcase, widening
conversion
    of a signed shift result to wider unsigned divisor, where if the shift
    is negative, we end up with x % (unsigned long long) INT_MIN which is
    x % 0xffffffff80000000ULL where the divisor is not a power of two and
    we can't optimize that to x & 0x7fffffffULL.

    So, the patch rejects only the single problematic case.

    Furthermore, when the shift result is signed, we were introducing UB into
    a program which previously didn't have one (well, left shift into the sign
    bit is UB in some language/version pairs, but it is definitely valid in
    C++20 - wonder if I shouldn't move the gcc.c-torture/execute/pr99079.c
    testcase to g++.dg/torture/pr99079.C and use -std=c++20), by adding that
    subtraction of 1, x % (1 << 31) in C++20 is well defined, but
    x & ((1 << 31) - 1) triggers UB on the subtraction.
    So, the patch performs the subtraction in the unsigned type if it isn't
    wrapping.

    2021-02-15  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/99079
            * match.pd (A % (pow2pcst << N) -> A & ((pow2pcst << N) - 1)):
Remove
            useless tree_nop_conversion_p (type, TREE_TYPE (@3)) check. 
Instead
            require both type and TREE_TYPE (@1) to be integral types and
either
            type having smaller or equal precision, or TREE_TYPE (@1) being
            unsigned type, or type being signed type.  If TREE_TYPE (@1)
            doesn't have wrapping overflow, perform the subtraction of one in
            unsigned type.

            * gcc.dg/fold-modpow2-2.c: New test.
            * gcc.c-torture/execute/pr99079.c: New test.

[Bug tree-optimization/99079] [8/9/10 Regression] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Maybe a wrong code since    |[8/9/10 Regression] Maybe a
                   |r6-1462-g4ab1e111ef0669bb   |wrong code since
                   |                            |r6-1462-g4ab1e111ef0669bb

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed on the trunk so far.

[Bug tree-optimization/99079] [8/9/10 Regression] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:45de8afb2d534e3b38b4d1898686b20c29cc6a94

commit r10-9470-g45de8afb2d534e3b38b4d1898686b20c29cc6a94
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Feb 15 09:16:06 2021 +0100

    match.pd: Fix up A % (cast) (pow2cst << B) simplification [PR99079]

    The (mod @0 (convert?@3 (power_of_two_cand@1 @2))) simplification
    uses tree_nop_conversion_p (type, TREE_TYPE (@3)) condition, but I believe
    it doesn't check what it was meant to check.  On convert?@3
    TREE_TYPE (@3) is not the type of what it has been converted from, but
    what it has been converted to, which needs to be (because it is operand
    of normal binary operation) equal or compatible to type of the modulo
    result and first operand - type.
    I could fix that by using && tree_nop_conversion_p (type, TREE_TYPE (@1))
    and be done with it, but actually most of the non-nop conversions are IMHO
    ok and so we would regress those optimizations.
    In particular, if we have say narrowing conversions (foo5 and foo6 in
    the new testcase), I think we are fine, either the shift of the power of
two
    constant after narrowing conversion is still that power of two (or negation
    of that) and then it will still work, or the result of narrowing conversion
    is 0 and then we would have UB which we can ignore.
    Similarly, widening conversions where the shift result is unsigned are
fine,
    or even widening conversions where the shift result is signed, but we sign
    extend to a signed wider divisor, the problematic case of INT_MIN will
    become x % (long long) INT_MIN and we can still optimize that to
    x & (long long) INT_MAX.
    What doesn't work is the case in the pr99079.c testcase, widening
conversion
    of a signed shift result to wider unsigned divisor, where if the shift
    is negative, we end up with x % (unsigned long long) INT_MIN which is
    x % 0xffffffff80000000ULL where the divisor is not a power of two and
    we can't optimize that to x & 0x7fffffffULL.

    So, the patch rejects only the single problematic case.

    Furthermore, when the shift result is signed, we were introducing UB into
    a program which previously didn't have one (well, left shift into the sign
    bit is UB in some language/version pairs, but it is definitely valid in
    C++20 - wonder if I shouldn't move the gcc.c-torture/execute/pr99079.c
    testcase to g++.dg/torture/pr99079.C and use -std=c++20), by adding that
    subtraction of 1, x % (1 << 31) in C++20 is well defined, but
    x & ((1 << 31) - 1) triggers UB on the subtraction.
    So, the patch performs the subtraction in the unsigned type if it isn't
    wrapping.

    2021-02-15  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/99079
            * match.pd (A % (pow2pcst << N) -> A & ((pow2pcst << N) - 1)):
Remove
            useless tree_nop_conversion_p (type, TREE_TYPE (@3)) check. 
Instead
            require both type and TREE_TYPE (@1) to be integral types and
either
            type having smaller or equal precision, or TREE_TYPE (@1) being
            unsigned type, or type being signed type.  If TREE_TYPE (@1)
            doesn't have wrapping overflow, perform the subtraction of one in
            unsigned type.

            * gcc.dg/fold-modpow2-2.c: New test.
            * gcc.c-torture/execute/pr99079.c: New test.

    (cherry picked from commit 70099a6acf5169eca55ef74549fb64de14e668f0)

[Bug tree-optimization/99079] [8/9 Regression] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[8/9/10 Regression] Maybe a |[8/9 Regression] Maybe a
                   |wrong code since            |wrong code since
                   |r6-1462-g4ab1e111ef0669bb   |r6-1462-g4ab1e111ef0669bb

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed for 10.3 too.

[Bug tree-optimization/99079] [8/9 Regression] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-9 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

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

commit r9-9420-gdfcddd8ed5c584f6eca6d918f8d88da2567d7350
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Feb 15 09:16:06 2021 +0100

    match.pd: Fix up A % (cast) (pow2cst << B) simplification [PR99079]

    The (mod @0 (convert?@3 (power_of_two_cand@1 @2))) simplification
    uses tree_nop_conversion_p (type, TREE_TYPE (@3)) condition, but I believe
    it doesn't check what it was meant to check.  On convert?@3
    TREE_TYPE (@3) is not the type of what it has been converted from, but
    what it has been converted to, which needs to be (because it is operand
    of normal binary operation) equal or compatible to type of the modulo
    result and first operand - type.
    I could fix that by using && tree_nop_conversion_p (type, TREE_TYPE (@1))
    and be done with it, but actually most of the non-nop conversions are IMHO
    ok and so we would regress those optimizations.
    In particular, if we have say narrowing conversions (foo5 and foo6 in
    the new testcase), I think we are fine, either the shift of the power of
two
    constant after narrowing conversion is still that power of two (or negation
    of that) and then it will still work, or the result of narrowing conversion
    is 0 and then we would have UB which we can ignore.
    Similarly, widening conversions where the shift result is unsigned are
fine,
    or even widening conversions where the shift result is signed, but we sign
    extend to a signed wider divisor, the problematic case of INT_MIN will
    become x % (long long) INT_MIN and we can still optimize that to
    x & (long long) INT_MAX.
    What doesn't work is the case in the pr99079.c testcase, widening
conversion
    of a signed shift result to wider unsigned divisor, where if the shift
    is negative, we end up with x % (unsigned long long) INT_MIN which is
    x % 0xffffffff80000000ULL where the divisor is not a power of two and
    we can't optimize that to x & 0x7fffffffULL.

    So, the patch rejects only the single problematic case.

    Furthermore, when the shift result is signed, we were introducing UB into
    a program which previously didn't have one (well, left shift into the sign
    bit is UB in some language/version pairs, but it is definitely valid in
    C++20 - wonder if I shouldn't move the gcc.c-torture/execute/pr99079.c
    testcase to g++.dg/torture/pr99079.C and use -std=c++20), by adding that
    subtraction of 1, x % (1 << 31) in C++20 is well defined, but
    x & ((1 << 31) - 1) triggers UB on the subtraction.
    So, the patch performs the subtraction in the unsigned type if it isn't
    wrapping.

    2021-02-15  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/99079
            * match.pd (A % (pow2pcst << N) -> A & ((pow2pcst << N) - 1)):
Remove
            useless tree_nop_conversion_p (type, TREE_TYPE (@3)) check. 
Instead
            require both type and TREE_TYPE (@1) to be integral types and
either
            type having smaller or equal precision, or TREE_TYPE (@1) being
            unsigned type, or type being signed type.  If TREE_TYPE (@1)
            doesn't have wrapping overflow, perform the subtraction of one in
            unsigned type.

            * gcc.dg/fold-modpow2-2.c: New test.
            * gcc.c-torture/execute/pr99079.c: New test.

    (cherry picked from commit 45de8afb2d534e3b38b4d1898686b20c29cc6a94)

[Bug tree-optimization/99079] [8/9 Regression] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-8 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:83b2007abb2ad05209483e8b9f75aec9b385bbb9

commit r8-10885-g83b2007abb2ad05209483e8b9f75aec9b385bbb9
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Feb 15 09:16:06 2021 +0100

    match.pd: Fix up A % (cast) (pow2cst << B) simplification [PR99079]

    The (mod @0 (convert?@3 (power_of_two_cand@1 @2))) simplification
    uses tree_nop_conversion_p (type, TREE_TYPE (@3)) condition, but I believe
    it doesn't check what it was meant to check.  On convert?@3
    TREE_TYPE (@3) is not the type of what it has been converted from, but
    what it has been converted to, which needs to be (because it is operand
    of normal binary operation) equal or compatible to type of the modulo
    result and first operand - type.
    I could fix that by using && tree_nop_conversion_p (type, TREE_TYPE (@1))
    and be done with it, but actually most of the non-nop conversions are IMHO
    ok and so we would regress those optimizations.
    In particular, if we have say narrowing conversions (foo5 and foo6 in
    the new testcase), I think we are fine, either the shift of the power of
two
    constant after narrowing conversion is still that power of two (or negation
    of that) and then it will still work, or the result of narrowing conversion
    is 0 and then we would have UB which we can ignore.
    Similarly, widening conversions where the shift result is unsigned are
fine,
    or even widening conversions where the shift result is signed, but we sign
    extend to a signed wider divisor, the problematic case of INT_MIN will
    become x % (long long) INT_MIN and we can still optimize that to
    x & (long long) INT_MAX.
    What doesn't work is the case in the pr99079.c testcase, widening
conversion
    of a signed shift result to wider unsigned divisor, where if the shift
    is negative, we end up with x % (unsigned long long) INT_MIN which is
    x % 0xffffffff80000000ULL where the divisor is not a power of two and
    we can't optimize that to x & 0x7fffffffULL.

    So, the patch rejects only the single problematic case.

    Furthermore, when the shift result is signed, we were introducing UB into
    a program which previously didn't have one (well, left shift into the sign
    bit is UB in some language/version pairs, but it is definitely valid in
    C++20 - wonder if I shouldn't move the gcc.c-torture/execute/pr99079.c
    testcase to g++.dg/torture/pr99079.C and use -std=c++20), by adding that
    subtraction of 1, x % (1 << 31) in C++20 is well defined, but
    x & ((1 << 31) - 1) triggers UB on the subtraction.
    So, the patch performs the subtraction in the unsigned type if it isn't
    wrapping.

    2021-02-15  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/99079
            * match.pd (A % (pow2pcst << N) -> A & ((pow2pcst << N) - 1)):
Remove
            useless tree_nop_conversion_p (type, TREE_TYPE (@3)) check. 
Instead
            require both type and TREE_TYPE (@1) to be integral types and
either
            type having smaller or equal precision, or TREE_TYPE (@1) being
            unsigned type, or type being signed type.  If TREE_TYPE (@1)
            doesn't have wrapping overflow, perform the subtraction of one in
            unsigned type.

            * gcc.dg/fold-modpow2-2.c: New test.
            * gcc.c-torture/execute/pr99079.c: New test.

    (cherry picked from commit 45de8afb2d534e3b38b4d1898686b20c29cc6a94)

[Bug tree-optimization/99079] [8/9 Regression] Maybe a wrong code since r6-1462-g4ab1e111ef0669bb

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.