[Bug tree-optimization/94566] New: conversion between std::strong_ordering and int

[Bug tree-optimization/94566] New: conversion between std::strong_ordering and int

[glisse at gcc dot gnu.org]

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

            Bug ID: 94566
           Summary: conversion between std::strong_ordering and int
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org
  Target Milestone: ---

#include <compare>

int conv1(std::strong_ordering s){
  if(s==std::strong_ordering::less) return -1;
  if(s==std::strong_ordering::equal) return 0;
  if(s==std::strong_ordering::greater) return 1;
  __builtin_unreachable();
}
std::strong_ordering conv2(int i){
  switch(i){
    case -1: return std::strong_ordering::less;
    case 0: return std::strong_ordering::equal;
    case 1: return std::strong_ordering::greater;
    default: __builtin_unreachable();
  }
}

Compiling with -std=gnu++2a -O3. I would like the compiler to notice that those
are just NOP (at most a sign-extension). Clang manages it for conv2. Gcc
generates:

        movl    $-1, %eax
        cmpb    $-1, %dil
        je      .L1
        xorl    %eax, %eax
        testb   %dil, %dil
        setne   %al
.L1:
        ret

and

        xorl    %eax, %eax
        testl   %edi, %edi
        je      .L10
        cmpl    $1, %edi
        sete    %al
        leal    -1(%rax,%rax), %eax
.L10:
        ret


(apparently the C++ committee thinks it is a good idea to provide a type that
is essentially an int that can only be -1, 0 or 1, but not provide any direct
way to convert to/from int)

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2020-04-13
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=94006
     Ever confirmed|0                           |1

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[rguenth at gcc dot gnu.org]

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

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
So for conv2 the most immediate issue is that we're failing to sink and common
the assignment to D.8516._M_value (I had patches for this).

conv2 (int i)
{
  int i_2(D) = i;
  struct strong_ordering D.8516;

  <bb 2> [local count: 1073741824]:
  if (i_2(D) == 0)
    goto <bb 5>; [33.33%]
  else
    goto <bb 3>; [66.67%]

  <bb 3> [local count: 1073741824]:
  if (i_2(D) == 1)
    goto <bb 6>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 4> [local count: 357878150]:
  D.8516._M_value = -1;
  goto <bb 7>; [100.00%]

  <bb 5> [local count: 357878150]:
  D.8516._M_value = 0;
  goto <bb 7>; [100.00%]

  <bb 6> [local count: 357878150]:
  D.8516._M_value = 1;

  <bb 7> [local count: 1073634451]:
  return D.8516;

for conv1 this is a missed phi-opt, at phiopt2 time:

conv1 (struct strong_ordering s)
{
  int SR.4;
  int _1;

  <bb 2> [local count: 1073741824]:
  SR.4_4 = s._M_value;
  if (SR.4_4 == -1)
    goto <bb 6>; [50.00%]
  else
    goto <bb 3>; [50.00%]

  <bb 3> [local count: 536870913]:
  if (SR.4_4 == 0)
    goto <bb 6>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 4> [local count: 268435456]:
  if (SR.4_4 == 1)
    goto <bb 6>; [100.00%]
  else
    goto <bb 5>; [0.00%]

  <bb 5> [count: 0]:
  __builtin_unreachable ();

  <bb 6> [local count: 1073741824]:
  # RANGE [-1, 1]
  # _1 = PHI <-1(2), 0(3), 1(4)>
  return _1;

it's a bit of a convoluted case of course but the only chance to pattern
match this ...

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|11832, 33315                |
         Depends on|                            |33315

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
I've verified my old fix for PR33315 does

t.C:11:45: optimized: sinking common stores to D.8528._M_value
...
conv2 (int i)
{
  struct strong_ordering D.8528;
  int _7;

  <bb 2> [local count: 1073741817]:
  switch (i_2(D)) <default: <L3> [0.00%], case -1: <L5> [33.33%], case 0: <L1>
[33.33%], case 1: <L2> [33.33%]>

  <bb 3> [local count: 357913942]:
<L1>:
  goto <bb 6>; [100.00%]

  <bb 4> [local count: 357913942]:
<L2>:
  goto <bb 6>; [100.00%]

  <bb 5> [count: 0]:
<L3>:
  __builtin_unreachable ();

  <bb 6> [local count: 1073741824]:
  # _7 = PHI <-1(2), 0(3), 1(4)>
<L5>:
  D.8528._M_value = _7;
  return D.8528;

still not optimized further tho.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=11832
[Bug 11832] Optimization of common stores in switch statements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33315
[Bug 33315] stores not commoned by sinking

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[glisse at gcc dot gnu.org]

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

--- Comment #3 from Marc Glisse <glisse at gcc dot gnu.org> ---
I thought we had code to recognize a switch that represents a linear function,
I was hoping that it would kick in with your hoisting patch...

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94566
Bug 94566 depends on bug 33315, which changed state.

Bug 33315 Summary: stores not commoned by sinking
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33315

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

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2020-04-13 00:00:00         |2021-6-14

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I wonder if we should always convert if-cases to switches and then do
switchconv and then lower the smaller ones (3 if max) right after switchconv
and then lower the rest in late as we do right now.  This should get the conv1
case.

The conv2 case problem is don't sink until late and never redo switchconv.

So here is the proposed pipeline:
iftoswitch - change to do it even without an heurstics
sink
switchconv
switchlower - early

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

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

--- Comment #5 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #2)
> I've verified my old fix for PR33315 does

Can you please show me which patch from the PR does that?

> 
> still not optimized further tho.

When does the sinking happen in the optimization pipeline?

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[marxin at gcc dot gnu.org]

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

--- Comment #6 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #3)
> I thought we had code to recognize a switch that represents a linear
> function, I was hoping that it would kick in with your hoisting patch...

Yep, we have the code but as mentioned the sinking needs to happen first.
Otherwise, you'll see:

g++ pr94566.C -O2 -fdump-tree-switchconv=/dev/stdout -std=gnu++2a

;; Function conv2 (_Z5conv2i, funcdef_no=90, decl_uid=8463, cgraph_uid=59,
symbol_order=88)

beginning to process the following SWITCH statement (pr94566.C:4) : ------- 
switch (i_2(D)) <default: <L3> [INV], case -1: <L0> [INV], case 0: <L1> [INV],
case 1: <L2> [INV]>

Bailing out - bad case - a non-final BB not empty
--------------------------------
struct strong_ordering conv2 (int i)
{
  struct strong_ordering D.8476;

  <bb 2> :
  switch (i_2(D)) <default: <L3> [INV], case -1: <L0> [INV], case 0: <L1>
[INV], case 1: <L2> [INV]>

  <bb 3> :
<L0>:
  D.8476._M_value = -1;
  goto <bb 7>; [INV]

  <bb 4> :
<L1>:
  D.8476._M_value = 0;
  goto <bb 7>; [INV]

  <bb 5> :
<L2>:
  D.8476._M_value = 1;
  goto <bb 7>; [INV]

  <bb 6> :
<L3>:
  __builtin_unreachable ();

  <bb 7> :
  return D.8476;

}

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

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

--- Comment #7 from Martin Liška <marxin at gcc dot gnu.org> ---
> So here is the proposed pipeline:
> iftoswitch - change to do it even without an heurstics
> sink
> switchconv
> switchlower - early

This one is also not ideal as there might be an optimization that eliminates
some of the switch case branches.

Note that we have a similar issue PR92005.

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[oschonrock at gmail dot com]

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

--- Comment #8 from Oliver Schönrock <oschonrock at gmail dot com> ---
how about:

#include <bit>
#include <compare>
#include <cstdint>

int conv3(std::strong_ordering s){
    return std::bit_cast<std::int8_t>(s);
}
std::strong_ordering conv4(int i){
    return std::bit_cast<std::strong_ordering>(static_cast<std::int8_t>(i));
}


conv3(std::strong_ordering):
        movsbl  %dil, %eax
        ret
conv4(int):
        movl    %edi, %eax
        ret


https://godbolt.org/z/szP5MGq4T

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
That one isn't portable, relies on both the strong_ordering underlying
implementation using an 8-bit integer member rather than something else, and
also hardcodes the exact values where in C++ the -1 / 0 / 1 are exposition only
and unordered value is -127 rather than what gcc uses (2).
By writing a series of ifs or switch one achieves portability and we'd just
like to get efficient code if the values the user chose match those used by the
implementation.

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[oschonrock at gmail dot com]

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

--- Comment #10 from Oliver Schönrock <oschonrock at gmail dot com> ---
I agree the switch optimisation is better, but...

 shouldn't std::bit_cast prevent incorrect casting with different underlying
implementaion? (ie if the size doesn't match, and the size could be deduced
with TMP) 

and "unordered value" doesn't apply to std::strong_ordering?

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[jakub at gcc dot gnu.org]

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

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Oliver Schönrock from comment #10)
> I agree the switch optimisation is better, but...
> 
>  shouldn't std::bit_cast prevent incorrect casting with different underlying
> implementaion? (ie if the size doesn't match, and the size could be deduced
> with TMP) 

The size can be deduced, yes.  What the bits actually mean can't be.

> and "unordered value" doesn't apply to std::strong_ordering?

Sure, but this PR isn't just about strong_ordering, same problem applies for
partial_ordering.
And actually not just those, but any case of some set of enumerators or macros
where you don't know the values exactly and mapping them to or from a set of
integer constants, ideally with 1:1 mapping but not guaranteed that way.

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Aldy or Andrew, why in conv1 we don't get a range for 
  SR.4_4 = sD.8798._M_valueD.7665;

Even though the range we have is [-1,1] according to the
__builtin_unreachable()?
It seems like we should get that range. Once we do get that the code works.
E.g. If we add:
  signed char *t = (signed char*)&s;
  signed char tt = *t;
  if (tt < -1 || tt > 1) __builtin_unreachable();

In the front before the other ifs, we get the code we are expecting.

conv2 has a similar issue too, though it has also a different issue of ordering
for the comparisons.

[Bug tree-optimization/94566] conversion between std::strong_ordering and int

[amacleod at redhat dot com]

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

--- Comment #13 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Andrew Pinski from comment #12)
> Aldy or Andrew, why in conv1 we don't get a range for 
>   SR.4_4 = sD.8798._M_valueD.7665;
> 
> Even though the range we have is [-1,1] according to the
> __builtin_unreachable()?
> It seems like we should get that range. Once we do get that the code works.
> E.g. If we add:
>   signed char *t = (signed char*)&s;
>   signed char tt = *t;
>   if (tt < -1 || tt > 1) __builtin_unreachable();
> 
> In the front before the other ifs, we get the code we are expecting.
> 
> conv2 has a similar issue too, though it has also a different issue of
> ordering for the comparisons.

its because the unreachable is after the branches, and we have multiple uses of
SR.4_4 before the unreachable.

  <bb 2> [local count: 1073741824]:
  SR.4_4 = s._M_value;
  if (SR.4_4 == -1)
    goto <bb 6>; [50.00%]
  else
    goto <bb 3>; [50.00%]

  <bb 3> [local count: 536870913]:
  if (SR.4_4 == 0)
    goto <bb 6>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 4> [local count: 268435456]:
  if (SR.4_4 == 1)
    goto <bb 6>; [100.00%]
  else
    goto <bb 5>; [0.00%]

  <bb 5> [count: 0]:
  __builtin_unreachable ();

  <bb 6> [local count: 1073741824]:
  # _1 = PHI <-1(2), 0(3), 1(4)>

We know when we get to bb5 that SR.4_4 is [-1, 1] for sure.
But we dont know that before we reach that spot.
if there was a call to 
  foo(SR.4_4)
in bb 3 for instance,   we wouldn't be able to propagate [-1,1] to the call to
foo because it happens before we know for sure.    and foo may go and do
something if it has a value of 6 and exit the compilation, thus never
returning.

So we can only provide a range of [-1, 1] AFTER the unreachable, or if there is
only a single use of it.. the multiples uses are what tricks it.

This has come up before.  we need some sort of backwards propagation that can
propagate discovered values earlier into the IL to a point where it is known to
be safe (ie, it wouldnt be able to propagate it past a call to foo() for
instance)
In cases like this, we could discover it is safe to propagate that range back
to the def point, and then we could set the global.

Until we add some smarts, either to the builtin unreachable elimination code,
or elsewhere, which is aware of how to handle such side effects, we can't set
the global because we dont know if it is safe at each use before the
unreachable call.