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.
