[Bug c++/105903] New: Missed optimization for __synth3way

[Bug c++/105903] New: Missed optimization for __synth3way

[barry.revzin at gmail dot com]

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

            Bug ID: 105903
           Summary: Missed optimization for __synth3way
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: barry.revzin at gmail dot com
  Target Milestone: ---

Consider this example:

#include <compare>
#include <vector>

inline constexpr auto synth3way = std::__detail::__synth3way;

struct Iterator {
    std::vector<int>::iterator it;

    constexpr bool operator<(Iterator const& rhs) const {
        return it < rhs.it;
    }
    constexpr bool operator>(Iterator const& rhs) const {
        return it > rhs.it;
    }    
};

bool less(Iterator const& a, Iterator const& b) {
    return a < b;
}

bool less3way(Iterator const& a, Iterator const& b) {
    return synth3way(a, b) < 0;
}

Here, synth3way(a, b) < 0 produces identical code to a < b (compiling with gcc
12.1 --std=c++20 -O3), which is great. The compiler recognizes that it doesn't
have to do the second synthesized comparison. 

However, if we instead compared (sorry):

bool greater(Iterator const& a, Iterator const& b) {
    return a > b;
}

bool greater3way(Iterator const& a, Iterator const& b) {
    return synth3way(a, b) > 0;
}

This is now much worse:

greater(Iterator const&, Iterator const&):
        mov     rax, QWORD PTR [rdi]
        cmp     QWORD PTR [rsi], rax
        setb    al
        ret
greater3way(Iterator const&, Iterator const&):
        mov     rdx, QWORD PTR [rdi]
        mov     rcx, QWORD PTR [rsi]
        xor     eax, eax
        cmp     rdx, rcx
        jb      .L3
        cmp     rcx, rdx
        setb    al
.L3:
        ret

Interestingly, if we write this out:

bool greater3way(Iterator const& a, Iterator const& b) {
    auto const cmp = [&]{
        if (a < b) return std::weak_ordering::less;
        if (b < a) return std::weak_ordering::greater;
        return std::weak_ordering::equivalent;
    }();
    return cmp > 0;
}

bool greater3way_fold(Iterator const& a, Iterator const& b) {
    return [&]{
        if (a < b) return false;
        if (b < a) return true;
        return false;
    }();
}

The greater3way_fold implementation generates the same code as >, which
definitely suggests to me that the greater3way version is simply a missed
optimization. 

On compiler explorer: https://godbolt.org/z/1xvfsMrnf

Because synth3way is only used in contexts that require a weak ordering anyway,
it would be a valid optimization to replace synth3way(a, b) > 0 with b < a,
synth3way(a, b) <= 0 with !(b < a) and synth3way(a, b) >= 0 with !(a < b).
These replacements aren't generally true (because partial orders), but the
precondition on this type is that we have a weak order, so we should be able to
do better.

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c++                         |tree-optimization
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
           Severity|normal                      |enhancement
   Last reconfirmed|                            |2022-06-08
           Keywords|                            |missed-optimization

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.
Currently we have inside phiopt4
  if (_5 < _6)
    goto <bb 4>; [50.00%]
  else
    goto <bb 3>; [50.00%]

  <bb 3> [local count: 536870913]:
  _9 = _5 > _6;

  <bb 4> [local count: 1073741824]:
  # prephitmp_10 = PHI <0(2), _9(3)>

That is:
(_5 < _6) ? 0 : (_5 > _6)

Which I think can be optimized to just:
(_5 > _6)

[Bug tree-optimization/105903] Missed optimization for __synth3way

[luoxhu at gcc dot gnu.org]

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

--- Comment #2 from luoxhu at gcc dot gnu.org ---
diff --git a/gcc/match.pd b/gcc/match.pd
index 4a570894b2e..f6b5415a351 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -5718,6 +5718,22 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
      (bit_xor (convert (rshift @0 {shifter;})) @1)
      (bit_not (bit_xor (convert (rshift @0 {shifter;})) @1)))))))

+/* X >= Y ? X > Y : 0 into X > Y. */
+(simplify
+  (cond (ge @0 @1) (gt @0 @1) integer_zerop)
+   (if (INTEGRAL_TYPE_P (type)
+       && POINTER_TYPE_P (TREE_TYPE (@0))
+       && POINTER_TYPE_P (TREE_TYPE (@1)))
+    (gt @0 @1)))
+
+/* X < Y ? 0 : X > Y into X > Y.  */
+(simplify
+  (cond (lt @0 @1) integer_zerop (gt @0 @1))
+   (if (INTEGRAL_TYPE_P (type)
+       && POINTER_TYPE_P (TREE_TYPE (@0))
+       && POINTER_TYPE_P (TREE_TYPE (@1)))
+    (gt @0 @1)))
+

The two patterns could fold PHI in phiopt4 for the two greater3way and generate
expected results.

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
             Status|NEW                         |ASSIGNED
         Depends on|                            |96923

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to luoxhu from comment #2)
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 4a570894b2e..f6b5415a351 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -5718,6 +5718,22 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>       (bit_xor (convert (rshift @0 {shifter;})) @1)
>       (bit_not (bit_xor (convert (rshift @0 {shifter;})) @1)))))))
> 
> +/* X >= Y ? X > Y : 0 into X > Y. */
> +(simplify
> +  (cond (ge @0 @1) (gt @0 @1) integer_zerop)
> +   (if (INTEGRAL_TYPE_P (type)
> +       && POINTER_TYPE_P (TREE_TYPE (@0))
> +       && POINTER_TYPE_P (TREE_TYPE (@1)))
> +    (gt @0 @1)))
> +
> +/* X < Y ? 0 : X > Y into X > Y.  */
> +(simplify
> +  (cond (lt @0 @1) integer_zerop (gt @0 @1))
> +   (if (INTEGRAL_TYPE_P (type)
> +       && POINTER_TYPE_P (TREE_TYPE (@0))
> +       && POINTER_TYPE_P (TREE_TYPE (@1)))
> +    (gt @0 @1)))
> +

Hmm, could be simplified to just:
+#if GIMPLE
+/* a ? b : c -> (a & b) | (!a & c) for truth (boolean) values
+   Only if either b or c are integer constants. */
+(simplify
+ (cond @0 truth_valued_p@1 truth_valued_p@2)
+ (if (TREE_CODE (@1) == INTEGER_CST
+      || TREE_CODE (@2) == INTEGER_CST)
+  (with {
+       tree booltrue = constant_boolean_node (true, type);
+     }
+   (bit_ior (bit_and (convert @0) @1) (bit_and (bit_xor (convert @0) {
booltrue; }) @2)))))
+#endif

Which is PR 96923 so mine.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96923
[Bug 96923] Failure to optimize a select-related bool pattern to or+not

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 53237
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53237&action=edit
testcase

Even though it was included in comment #0, I am attaching it as it easier to
figure out what the testcase was.

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
After my patches for PR 96923  (and PR 100864), we get:


  _22 = _16 > _17;
... (some dead statements that PHI-OPT adds due to match and simplify)
  _8 = _16 >= _17;
  _13 = _8 & _22;

But there is nothing which optimizes the above into just _22 (_16 > _17) which
I find interesting ...

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #5)
> After my patches for PR 96923  (and PR 100864), we get:
> 
> 
>   _22 = _16 > _17;
> ... (some dead statements that PHI-OPT adds due to match and simplify)
>   _8 = _16 >= _17;
>   _13 = _8 & _22;
> 
> But there is nothing which optimizes the above into just _22 (_16 > _17)
> which I find interesting ...

Now after the patch I have for  106164 we get:
  _13 = _16 > _17;

Which is what we expect.

Note phiopt still should do some cleanup because of match-and-simplify as we
get:
  _3 = _16 < _17;
  _7 = _16 < _17;
  _8 = _16 >= _17;
  _13 = _16 > _17;

Where _3, _7 and _8 are all unused, I have to figure out the best way of doing
that.

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

Bug 96923 Summary: Failure to optimize a select-related bool pattern to or+not
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96923

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

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The patch which fixes PR 89263 also fixes this one.

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

Bug 89263 Summary: Simplify bool expression to OR
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89263

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

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

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

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

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

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Actually this is not optimized all the way in the end.
For greater3way, we still get:
  _8 = _5 > _6;
  _7 = _5 >= _6;
  _2 = _7 & _8;

This should be optimized to just _5 >= _6 .

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #9)
> Actually this is not optimized all the way in the end.
> For greater3way, we still get:
>   _8 = _5 > _6;
>   _7 = _5 >= _6;
>   _2 = _7 & _8;
> 
> This should be optimized to just _5 >= _6 .

Sorry `_5 > _6` .

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #10)
> (In reply to Andrew Pinski from comment #9)
> > Actually this is not optimized all the way in the end.
> > For greater3way, we still get:
> >   _8 = _5 > _6;
> >   _7 = _5 >= _6;
> >   _2 = _7 & _8;
> > 
> > This should be optimized to just _5 >= _6 .
> 
> Sorry `_5 > _6` .

What is interesting is I tested with the patches I have for PR 106164 which
should fix this but does not. If I try it out manually forwprop does catch it
so I need to figure out what is going wrong in phiopt4.

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #11)
> What is interesting is I tested with the patches I have for PR 106164 which
> should fix this but does not. If I try it out manually forwprop does catch
> it so I need to figure out what is going wrong in phiopt4.

Oh I missed it was a pointer type. So I have a patch ...

[Bug tree-optimization/105903] Missed optimization for __synth3way

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed by r14-2886 .