[Bug tree-optimization/101179] New: y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[Bug tree-optimization/101179] New: y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[redi at gcc dot gnu.org]

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

            Bug ID: 101179
           Summary: y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce
                    different code
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org
  Target Milestone: ---

These produces different assembly:

int f1(int y)
{
    const bool x = y % 100 == 0;
    return y % (x ? 16 : 4) == 0;
}

int f2(int y)
{
    const bool x = y % 100 == 0;
    return y % (4 << (x * 2)) == 0;
}

Since they do the same calculation, I would expect them to produce the same
code.

Currently f1 produces slightly smaller code for aarch64 and x86_64.

With Clang they produce the same code (but using cmov which might not be
optimal).

[Bug tree-optimization/101179] y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[redi at gcc dot gnu.org]

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

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
On IRC Richi said: "VRP has code to do that but maybe for some reason shifts
are not handled"

[Bug tree-optimization/101179] y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
   Last reconfirmed|                            |2021-06-23
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(x ? 16 : 4)

to:
(4 << (x * 2))

Should be easy to add to match.pd's
/* A few simplifications of "a ? CST1 : CST2". */

And PHI-OPT will use it without you doing anything extra.

[Bug tree-optimization/101179] y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
the ?: one seems to produce better code currently though, so I'm not sure
transforming it to the shift is what we want.

[Bug tree-optimization/101179] y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
But here are two other functions which all should have the same code gen as the
original two:
int f3(int y)
{
    const bool x = y % 100 == 0;
    return (x ? y%16 : y%4) == 0;
}

int f4(int y)
{
    const bool x = y % 100 == 0;
    return (x ? (y%16) == 0 : (y%4) == 0);
}

Only the last one produces the best code.

[Bug tree-optimization/101179] y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4) 
> Only the last one produces the best code.

So for clang, f1-f3 produces the same code but f4 is bad.
It was only fixed in clang 10.

[Bug tree-optimization/101179] y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |85316

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #1)
> On IRC Richi said: "VRP has code to do that but maybe for some reason shifts
> are not handled"

Specifically simplify_using_ranges::simplify has

      /* Convert:
         LHS = CST BINOP VAR
         Where VAR is two-valued and LHS is used in GIMPLE_COND only
         To:
         LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)

         Also handles:
         LHS = VAR BINOP CST
         Where VAR is two-valued and LHS is used in GIMPLE_COND only
         To:
         LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */

restrictions that stand in the way:

      if (TREE_CODE_CLASS (rhs_code) == tcc_binary
...
          && single_imm_use (lhs, &use_p, &use_stmt)
          && gimple_code (use_stmt) == GIMPLE_COND)

VRP1 sees

  <bb 2> [local count: 1073741824]:
  _1 = y_7(D) % 100;
  x_8 = _1 == 0;
  _2 = (int) x_8;
  _3 = _2 * 2;
  _4 = 4 << _3;
  _5 = y_7(D) % _4;
  _6 = _5 == 0; 
  _9 = (int) _6;
  return _9; 

so it would consider _2 * 2 but its single use is in a shift, the
condition is after another op, the modulo, and there the condition
is in an assignment, not in a GIMPLE_COND.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85316
[Bug 85316] [meta-bug] VRP range propagation missed cases

[Bug tree-optimization/101179] y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |antoshkka at gmail dot com

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 101252 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/101179] y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[pinskia at gcc dot gnu.org]

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

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 101251 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/101179] y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[pinskia at gcc dot gnu.org]

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

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Here is one more function which should be the same:
int f0(int y)
{
    const bool x = y % 100 == 0;
    return (y & ((4 << (x * 2)) - 1)) != 0;
}

[Bug tree-optimization/101179] y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ktkachov at gcc dot gnu.org

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 108446 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/101179] y % (x ? 16 : 4) and y % (4 << (2 * (bool)x)) produce different code

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=71336

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Similar to PR 71336, difference is the difference is a power of 2 there while
here they are power of 2s