[Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined

[Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined

[llvm at rifkin dot dev]

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

            Bug ID: 115201
           Summary: Recursive binary search is incorrectly inlined
           Product: gcc
           Version: 14.1.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: llvm at rifkin dot dev
  Target Milestone: ---

I was sent the following code 

template<typename T, typename I, typename C>
constexpr I binarySearch(const T& item, const I start, const I end, C&& cmp) {
    if (std::next(start) == end) {
        return start;
    }

    const auto mid = std::next(start, std::distance(start, end) / 2);
    if (cmp(item, *mid)) {
        return binarySearch(item, start, mid, std::forward<C>(cmp));
    }
    return binarySearch(item, mid, end, std::forward<C>(cmp));
}

auto foo(const std::vector<int>& items) {
    return *binarySearch(5, items.begin(), items.end(), std::less{});
}

This causes gcc to aggressively inline the recursive function into itself
eventually emitting 1600 instructions whereas clang emits about 30. Textual
assembly length of course means little as far as performance goes however in
this case it is indicative of something going wrong, even if a TCO'd loop were
somehow unrolled.

It seems that the tail recursion is not transformed during the tailr1 pass and
instead binarySearch is inlined into itself during inline, and additional
inlining happens with foo. https://godbolt.org/z/45r7dvbxr

Imho this sort of inlining makes little sense and either it should be properly
TCO'd or not inlined at all.

This happen going back to at least gcc 7.

[Bug ipa/115201] Recursive binary search is incorrectly inlined

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|tree-optimization           |ipa

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I suspect this is way GCC recursive inlining works and it is working correctly.
While LLVM does not do any recursive inlining (anywhere).

[Bug ipa/115201] Recursive binary search is incorrectly inlined

[llvm at rifkin dot dev]

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

--- Comment #2 from Jeremy R. <llvm at rifkin dot dev> ---
Does recursive inlining here interfere with TCO, or is GCC just not able to TCO
in this case?

I can understand why some bounded recursive inlining may be desirable, however
in this case it seems very not ideal.

[Bug ipa/115201] Recursive binary search is incorrectly inlined

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Oh the issue is the iterator is a struct which confuses things ...

[Bug ipa/115201] Recursive binary search is incorrectly inlined

[pinskia at gcc dot gnu.org]

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

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

The tail call happens in the foo2 case while not in foo1. This is due to struct
returns are not always handled for tail call ..

[Bug tree-optimization/115201] Recursive binary search with struct iterator is not handled by tail Recursion

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.

[Bug tree-optimization/115201] Recursive binary search with struct iterator is not handled by tail Recursion

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 58274
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58274&action=edit
Slightly more reduced

Slightly more reduced, foo3 should produce the same as foo4.

Basically Tailr does not handle recusive calls with struct arguments really.

[Bug tree-optimization/115201] Recursion not optimized for structs arguments

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
              /* The parameter should be a real operand, so that phi node
                 created for it at the start of the function has the meaning
                 of copying the value.  This test implies is_gimple_reg_type
                 from the previous condition, however this one could be
                 relaxed by being more careful with copying the new value
                 of the parameter (emitting appropriate GIMPLE_ASSIGN and
                 updating the virtual operands).  */

So this has been a known issue for a long time now.

[Bug tree-optimization/115201] Recursion not optimized for structs arguments

[pinskia at gcc dot gnu.org]

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

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #7)
> 	      /* The parameter should be a real operand, so that phi node
> 		 created for it at the start of the function has the meaning
> 		 of copying the value.  This test implies is_gimple_reg_type
> 		 from the previous condition, however this one could be
> 		 relaxed by being more careful with copying the new value
> 		 of the parameter (emitting appropriate GIMPLE_ASSIGN and
> 		 updating the virtual operands).  */
> 
> So this has been a known issue for a long time now.

Actually this is the correct one:
              /* Make sure there are no problems with copying.  The parameter
                 have a copyable type and the two arguments must have
reasonably
                 equivalent types.  The latter requirement could be relaxed if
                 we emitted a suitable type conversion statement.  */

That has been there since tree-ssa was merged in.