[Bug c++/102684] New: [missed optimization] std::min_element / ranges::min_element does not get optimized away with std::gcd

[Bug c++/102684] New: [missed optimization] std::min_element / ranges::min_element does not get optimized away with std::gcd

[xkeviota at gmail dot com]

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

            Bug ID: 102684
           Summary: [missed optimization] std::min_element /
                    ranges::min_element does not get optimized away with
                    std::gcd
           Product: gcc
           Version: 11.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: xkeviota at gmail dot com
  Target Milestone: ---

This code which calculates the gcd of the minimum and maximum element of a
range of elements gets optimized away entirely with clang to just a `return`
statement with `-O3` while gcc (trunk) produces up to 232 lines of assembly
depending on the optimization level
(https://compiler-explorer.com/z/TYrx5exP3).

#include <algorithm>
#include <numeric>
#include <span>
#include <vector>

namespace r = std::ranges;

template <typename T>
constexpr auto find_gcd(std::span<T> container) {
    return std::gcd(*r::min_element(container),
                    *r::max_element(container));
}

int main() {
    std::vector<int> ints = {2, 4, 6, 10};
    return find_gcd<int>(ints);
}

The same happens when `std::min_element` is used for example. I found one other
post regarding `std::min_element` from 2018 about custom predicates but I
wasn't sure if it might have the same underlying problem.

[Bug c++/102684] [missed optimization] std::min_element / ranges::min_element does not get optimized away with std::gcd

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
ISTR that clang evaluates constexpr declared things opportunistically as
constexpr even when that is not required (your find_gcd<>(ints) call is not in
such a context).

[Bug tree-optimization/102684] [missed optimization] std::min_element / ranges::min_element does not get optimized away with std::gcd

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c++                         |tree-optimization

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> ISTR that clang evaluates constexpr declared things opportunistically as
> constexpr even when that is not required (your find_gcd<>(ints) call is not
> in such a context).

I don't think that is the case here.

First issue is the standard GCC knows main is only called once so inlining is
less.  This is expected and can be ignored.  Just rename main to f and things
will improve right away.

The second issue I am trying to figure out but there seems like some missed
optimization dealing how many interations the loop is and if the loop is small
enough.

[Bug tree-optimization/102684] [missed optimization] std::min_element / ranges::min_element does not get optimized away with std::gcd

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

[Bug tree-optimization/102684] [missed optimization] std::min_element / ranges::min_element does not get optimized away with std::gcd

[xkeviota at gmail dot com]

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

--- Comment #3 from Kevin K <xkeviota at gmail dot com> ---
(In reply to Andrew Pinski from comment #2)
> (In reply to Richard Biener from comment #1)
> > ISTR that clang evaluates constexpr declared things opportunistically as
> > constexpr even when that is not required (your find_gcd<>(ints) call is not
> > in such a context).
> 
> I don't think that is the case here.
> 
> First issue is the standard GCC knows main is only called once so inlining
> is less.  This is expected and can be ignored.  Just rename main to f and
> things will improve right away.
> 
> The second issue I am trying to figure out but there seems like some missed
> optimization dealing how many interations the loop is and if the loop is
> small enough.

The generated assembly is the same with or without the constexpr modifier, so
yeah it does not seem to be that.

[Bug tree-optimization/102684] [missed optimization] std::min_element / ranges::min_element does not get optimized away with std::gcd

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Here is what optimized looks like on the trunk (after the main->f change):
  <bb 2> [local count: 1073741824]:
  _54 = operator new (16);
  MEM <uint128_t> [(char * {ref-all})_54] = 0xa000000060000000400000002;

  <bb 3> [local count: 3043903040]:
  # __m_103 = PHI <1(2), __m_85(6)>
  # __n_104 = PHI <5(2), __n_111(6)>
  if (__m_103 > __n_104)
    goto <bb 7>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 4> [local count: 1521951520]:
  __n_107 = __n_104 - __m_103;
  if (__n_107 == 0)
    goto <bb 5>; [22.00%]
  else
    goto <bb 6>; [78.00%]

  <bb 5> [local count: 1014634349]:
  _109 = __m_103 << 1;
  _41 = (int) _109;
  operator delete (_54, 16);
  return _41;

  <bb 6> [local count: 2709073704]:
  # __m_85 = PHI <__m_103(4), __n_104(7)>
  # __n_30 = PHI <__n_107(4), __n_87(7)>
  _110 = __builtin_ctz (__n_30);
  __n_111 = __n_30 >> _110;
  goto <bb 3>; [100.00%]

  <bb 7> [local count: 1521951520]:
  __n_87 = __m_103 - __n_104;
  goto <bb 6>; [100.00%]

There seems to be some VRP missing inside the loop.

[Bug tree-optimization/102684] [missed optimization] std::min_element / ranges::min_element does not get optimized away with std::gcd

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-10-12
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1