public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined
@ 2024-05-23 1:41 llvm at rifkin dot dev
2024-05-23 1:54 ` [Bug ipa/115201] " pinskia at gcc dot gnu.org
` (7 more replies)
0 siblings, 8 replies; 9+ messages in thread
From: llvm at rifkin dot dev @ 2024-05-23 1:41 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug ipa/115201] Recursive binary search is incorrectly inlined
2024-05-23 1:41 [Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined llvm at rifkin dot dev
@ 2024-05-23 1:54 ` pinskia at gcc dot gnu.org
2024-05-23 2:04 ` llvm at rifkin dot dev
` (6 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: pinskia at gcc dot gnu.org @ 2024-05-23 1:54 UTC (permalink / raw)
To: gcc-bugs
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).
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug ipa/115201] Recursive binary search is incorrectly inlined
2024-05-23 1:41 [Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined llvm at rifkin dot dev
2024-05-23 1:54 ` [Bug ipa/115201] " pinskia at gcc dot gnu.org
@ 2024-05-23 2:04 ` llvm at rifkin dot dev
2024-05-23 2:10 ` pinskia at gcc dot gnu.org
` (5 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: llvm at rifkin dot dev @ 2024-05-23 2:04 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug ipa/115201] Recursive binary search is incorrectly inlined
2024-05-23 1:41 [Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined llvm at rifkin dot dev
2024-05-23 1:54 ` [Bug ipa/115201] " pinskia at gcc dot gnu.org
2024-05-23 2:04 ` llvm at rifkin dot dev
@ 2024-05-23 2:10 ` pinskia at gcc dot gnu.org
2024-05-23 2:11 ` pinskia at gcc dot gnu.org
` (4 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: pinskia at gcc dot gnu.org @ 2024-05-23 2:10 UTC (permalink / raw)
To: gcc-bugs
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 ...
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug ipa/115201] Recursive binary search is incorrectly inlined
2024-05-23 1:41 [Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined llvm at rifkin dot dev
` (2 preceding siblings ...)
2024-05-23 2:10 ` pinskia at gcc dot gnu.org
@ 2024-05-23 2:11 ` pinskia at gcc dot gnu.org
2024-05-23 2:13 ` [Bug tree-optimization/115201] Recursive binary search with struct iterator is not handled by tail Recursion pinskia at gcc dot gnu.org
` (3 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: pinskia at gcc dot gnu.org @ 2024-05-23 2:11 UTC (permalink / raw)
To: gcc-bugs
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 ..
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug tree-optimization/115201] Recursive binary search with struct iterator is not handled by tail Recursion
2024-05-23 1:41 [Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined llvm at rifkin dot dev
` (3 preceding siblings ...)
2024-05-23 2:11 ` pinskia at gcc dot gnu.org
@ 2024-05-23 2:13 ` pinskia at gcc dot gnu.org
2024-05-23 3:01 ` pinskia at gcc dot gnu.org
` (2 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: pinskia at gcc dot gnu.org @ 2024-05-23 2:13 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug tree-optimization/115201] Recursive binary search with struct iterator is not handled by tail Recursion
2024-05-23 1:41 [Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined llvm at rifkin dot dev
` (4 preceding siblings ...)
2024-05-23 2:13 ` [Bug tree-optimization/115201] Recursive binary search with struct iterator is not handled by tail Recursion pinskia at gcc dot gnu.org
@ 2024-05-23 3:01 ` pinskia at gcc dot gnu.org
2024-05-23 3:26 ` [Bug tree-optimization/115201] Recursion not optimized for structs arguments pinskia at gcc dot gnu.org
2024-05-23 3:29 ` pinskia at gcc dot gnu.org
7 siblings, 0 replies; 9+ messages in thread
From: pinskia at gcc dot gnu.org @ 2024-05-23 3:01 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug tree-optimization/115201] Recursion not optimized for structs arguments
2024-05-23 1:41 [Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined llvm at rifkin dot dev
` (5 preceding siblings ...)
2024-05-23 3:01 ` pinskia at gcc dot gnu.org
@ 2024-05-23 3:26 ` pinskia at gcc dot gnu.org
2024-05-23 3:29 ` pinskia at gcc dot gnu.org
7 siblings, 0 replies; 9+ messages in thread
From: pinskia at gcc dot gnu.org @ 2024-05-23 3:26 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug tree-optimization/115201] Recursion not optimized for structs arguments
2024-05-23 1:41 [Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined llvm at rifkin dot dev
` (6 preceding siblings ...)
2024-05-23 3:26 ` [Bug tree-optimization/115201] Recursion not optimized for structs arguments pinskia at gcc dot gnu.org
@ 2024-05-23 3:29 ` pinskia at gcc dot gnu.org
7 siblings, 0 replies; 9+ messages in thread
From: pinskia at gcc dot gnu.org @ 2024-05-23 3:29 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2024-05-23 3:29 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-05-23 1:41 [Bug tree-optimization/115201] New: Recursive binary search is incorrectly inlined llvm at rifkin dot dev
2024-05-23 1:54 ` [Bug ipa/115201] " pinskia at gcc dot gnu.org
2024-05-23 2:04 ` llvm at rifkin dot dev
2024-05-23 2:10 ` pinskia at gcc dot gnu.org
2024-05-23 2:11 ` pinskia at gcc dot gnu.org
2024-05-23 2:13 ` [Bug tree-optimization/115201] Recursive binary search with struct iterator is not handled by tail Recursion pinskia at gcc dot gnu.org
2024-05-23 3:01 ` pinskia at gcc dot gnu.org
2024-05-23 3:26 ` [Bug tree-optimization/115201] Recursion not optimized for structs arguments pinskia at gcc dot gnu.org
2024-05-23 3:29 ` pinskia at gcc dot gnu.org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).