[Bug c++/67962] New: Optimization opportunity with conditional swap

[Bug c++/67962] New: Optimization opportunity with conditional swap

[morwenn29 at hotmail dot fr]

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

            Bug ID: 67962
           Summary: Optimization opportunity with conditional swap
           Product: gcc
           Version: 5.2.0
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: morwenn29 at hotmail dot fr
  Target Milestone: ---

If have some algorithms that use an extensive number of conditional swaps like
this (a few hundreds I guess):

    if (y < x)
    {
        std::swap(x, y);
    }

I thought that such a construct could be optimized by the compiler, but it
appears that the following function is more performant with integers most of
the time:

    void swap_if(int& x, int& y)
    {
        int dx = x;
        int dy = y;
        int tmp = x = std::min(dx, dy);
        y ^= dx ^ tmp;
    }

Would it be possible for g++ to recognize this kind of construct and optimize
it, at least for integer types? Reordering two values seems like something
common enough so that optimizing it could also benefit existing code.

As a side note, I hope that Bugzilla is he right place for this kind of
request. Sorry if it isn't.

[Bug tree-optimization/67962] Optimization opportunity with conditional swap to two MIN/MAX in phiopt

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-10-14
          Component|c++                         |tree-optimization
            Summary|Optimization opportunity    |Optimization opportunity
                   |with conditional swap       |with conditional swap to
                   |                            |two MIN/MAX in phiopt
     Ever confirmed|0                           |1
           Severity|minor                       |enhancement

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
We miss the opportunity to turn

  <bb 2>:
  if (y_5(D) < x_6(D))
    goto <bb 4>;
  else
    goto <bb 3>;

  <bb 3>:

  <bb 4>:
  # y_4 = PHI <y_5(D)(3), x_6(D)(2)>
  # x_2 = PHI <x_6(D)(3), y_5(D)(2)>

into

   y_4 = MAX (x_6, y_5);
   x_2 = MIN (x_6, y_5);

and further optimize MINMAX (ISTR that was suggested elsewhere).  phiopt only
considers a single min/max operation.

Now the question is whether the transform would be profitable in isolation.

[Bug tree-optimization/67962] Optimization opportunity with conditional swap to two MIN/MAX in phiopt

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Mine, but for gcc 13.  The main problem I see if two cmov might be slower than
a branch on x86_64 processors.

[Bug tree-optimization/67962] Optimization opportunity with conditional swap to two MIN/MAX in phiopt

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #3)
> Mine, but for gcc 13.  The main problem I see if two cmov might be slower
> than a branch on x86_64 processors.

Two cmov definitely, a min/max pair not.

Now, phiopt will turn

  <bb 2> :
  if (y_16(D) < x_17(D))
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :

  <bb 4> :
  # x_14 = PHI <x_17(D)(2), y_16(D)(3)>
  if (y_16(D) < x_17(D))
    goto <bb 5>; [INV]
  else
    goto <bb 6>; [INV]

  <bb 5> :

  <bb 6> :
  # y_15 = PHI <y_16(D)(2), x_17(D)(3)>

into the desired pair but fails for the equivalent

  <bb 2> :
  if (y_16(D) < x_17(D))
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :

  <bb 4> :
  # x_14 = PHI <x_17(D)(2), y_16(D)(3)>
  # y_15 = PHI <y_16(D)(2), x_17(D)(3)>

We do value-replacement for more than one PHI but not others, not exactly
sure why.  We could dry-run convert all PHIs and only if that succeeds
and the condition goes away perform the transforms.  Of course some
transforms might still not be profitable then.