I’d like to propose allowing more optimizations on linkonce_odr functions, and specifically using heuristics and hints from the frontend (because otherwise I think we can’t really do much, see details below).
Background:
Today, all C++ inline functions (keyword in source code, or implicitly inline, like members functions in class body) and template instantiations as emitted as linkonce_odr (except when in an anonymous namespace, marked static, or in a few more specific situations):
This is required by C++ semantics (ODR, needs only one visible address), and to avoid multiple copies in the final binary
Every TU emits its own copy of the function. At link time, the linker coalesces them (arbitrarily picks one)
For that case, IPO and inlining are (intentionally) restricted:
No IPO that would lose generality is allowed on the function signature or body directly: function-attrs inference, IPSCCP argument/return propagation, function specialization, DeadArgElim, ArgPromotion.
The inliner assumes the out-of-line copy is shared across TUs, so it’s conservative: It never treats a call as the last call to a local function, so no last-call bonus is applied, even when this TU has the only call.
It’s not legal to simply change the linkage to internal (would break C++ semantics), but it’s legal to inline, clone (and internalize the clone), and then do IPO on the clone leaving the original function’s body as is.
Anonymous namespaces emit internal linkage, and thus none of the limitations apply. A lot of real-world C++ doesn’t use them consistently, and in all places they would apply.
Motivation and experiments:
My direct motivation is from noticing a large lambda in a templated method in a .cpp file in a benchmark, that was not getting inlined. Making the inlining happen via any method (anonymous namespace, or avoiding the template) gives a large perf boost to the benchmark.
I believe this and similar situations aren’t rare, and similar perf opportunities are elsewhere.
As an experiment, I added a clone+internalize pass of all linkonce_odr functions and rebuilt a set of industry standard C++ benchmarks (SPEC2026) with -O3. This yielded a 3% perf win in one benchmark (different one than mentioned above), and a mixed bag of small perf gains, but also some regressions, and it grew codesize in some cases significantly.
As another experiment, I restricted the clone+internalize pass only to linkonce_odr function that come from a .cpp file. This yielded the same 3% perf win, some smaller gains, and no measurable perf regressions and no codesize regressions (!). In fact, the codesize overall on average slightly improved.
The proposal:
The main idea is “don’t pessimize all linkonce_odr functions”. Since LLVM can’t really know which linkonce_odr functions should be heavily optimized and which one’s shouldn’t, we need the frontend (Clang) to tell us.
There’s situations where Clang can imply from the higher-level structure that the function is very likely to be TU-local:
it’s defined in a .cpp file (and not in a .h file)
it’s a template instantiation where a template argument is a type defined in a .cpp file (or anything transitively derived from such an entity)
Concretely, we should use that as a heuristic:
Clang should mark implementation-file definitions (optionally transitively, via template arguments) with a function attribute.
An implementation-file linkonce_odr callee with a single call in the TU gets the last-call bonus, just like an internal function.
We can consider which parts of this should be specific to -O2/-O3 vs. -Os/-Oz optimization levels.
The “probably TU-local” hint is only ever about optimization cost and thresholds, not about treating a linkonce_odr definition as exact.
Questions:
What sort of optimization limits should there be for implementation-file linkonce_odr code? The clone-and-internalize link
Unity builds and #included .cpp files break the heuristic. The failure mode is a likely code-size hit, but not a correctness problem. Is this acceptable, and should we take precautions here via threshold and/or by limiting to -O2/-O3 builds?
To what extent does this also apply to weak_odr? I think the answer is “not at all”, because the requirement to separately emit the function means inlining really is inflating code size; and anyway, it doesn’t really matter because there aren’t any naive code patterns that lead to weak_odr definitions in the first place. But I’d like there to be a record that we thought about it in this thread.
My first instinct was that “defined in” is not quite right, and that it should be “exclusively declared in”, i.e. non-header implementations of vague-linkage functions that are declared in headers should not get the heuristic. Certainly a header declaration suggests that there might be uses from multiple TUs, which is a hint that we might be in the redundant-definitions situation.
On the other hand, any function that we emit as linkonce_odr (rather than weak_odr or something stronger) is a function that C++ requires to be defined in every TU that uses it, and the most likely explanation is still that — despite the header declaration — the function is only actually used from this TU. And there are legitimate reasons you might need a function or type to be declared in a header and still prefer to implement it in a non-header file, like needing it to be a friend of some public type.[1]
On balance, I think I’d recommend keeping the rule “defined in”, just as you’ve written it.
In fact, needing to be a friend class is one reason why even experts sometimes can’t use anonymous namespaces everywhere they might want. ↩︎
Most functions will be either address-taken or called, not both. If a function is only address-taken, nothing can use the cloned function. If a function is only called, the original linkonce_odr definition will end up dead after you clone, so you can just mutate the function definition.
For cases where we actually end up with two copies of the function, we probably want a relatively low threshold.
Preprocessed source usually has line directives (“#”); we can use them to figure out whether something is in the “main” file. Maybe we can detect preprocessed source where the line directives have been stripped.
I think it’s fine if this doesn’t trigger for #include’ed .cpp files.
I wonder if this may be a bit of a benchmark-specific optimization: a benchmark program might be tiny, or even a single file, and sees little risk of conflict arising from defining external symbols which should’ve been internal.
But in other software, having symbols defined in a TU which are accidentally external may carry a significant risk of symbol-name collision, so the issue should (ideally) be resolved on that basis…
Which, I suppose, is roughly what the -Wmissing-prototypes diagnostic is for…and last time I looked at that (a long time ago), it was too noisy to enable.
It would be good to have numbers with this optimization enabled/disabled with ThinLTO turned on as well. ThinLTO should subsume any optimization opportunity here as it will perform internalization on functions that never get called from outside of their translation unit.
I guess performance of non-ThinLTO binaries can be important in some cases, but I would probably want to hear more about the use case and why ThinLTO cannot be enabled. Anyone who cares about performance should be enabling ThinLTO.
I think that without some sort of cross-TU information, there’s nothing we can do there. But I agree that this is way too common. Probably even more in C than C++.
I can confirm that both LTO and ThinLTO subsume the perf win from the two benchmarks where I got noticeable large gains, and applying the experimental patch (lift the sole-call limit) does not produce any perf changes there.
As much as “make the code as-written perform better” is a reasonable/frequent goal - I’d personally be in favor of fixing the code, perhaps as @jyknight said via -Wmissing-prototype or similar - if it needs improvements to reduce false positives/make it viable, perhaps we can do that.
The motivation is the same as with any other optimizer improvement, to provide a generally useful improvement to any user of the compiler who ends up knowingly or unknowingly using a pattern that compiles in a sub-optimal way. Whether the individual cases I’m using as data points here can be fixed at the source code (or their build system) level seems irrelevant.
As long as the consequence of a false positive from this heuristic is just that we might make more aggressive inlining decisions than we would if we had full information, I don’t know that we need to wring our hands too much about someone falling afoul of it. That’s especially true if the problematic code patterns would all be either really weird or likely to be accepting of more aggressive optimization, which seems to be the case here; more below.
Right, I’ve been assuming that the heuristic is not literally based on the filename but instead based on whether the code comes from (expansion loc for macros, I guess) the main implementation file. That would leave I think six patterns that would cause a false positive here:
The programmer really has written redundant, ODR-compliant definitions of the same function in different source files. This is legal but very weird.
The programmer has definitions in different source files that happen to be the same entity for ODR purposes. This is a programmer error (ODR violation) that is already likely to cause miscompiles today. This heuristic is at least not making anything worse; in fact, it is slightly more likely to save the programmer from their mistake if they only ever build in optimized mode.
The programmer has a macro defined in a header which defines an inline function, and they expand it in multiple source files. This is also legal but very weird; I don’t know why someone would do this instead of just defining the function in the header normally. Maybe if the macro expansion is configuration-dependent (macro arguments?), but then they’ve got the above ODR violation to the extent that the configuration ever does vary.
The programmer is doing some kind of unity build where this implementation file is also #included by another implementation file. This is also very weird — not the unity build itself, but the fact that the #included implementation is still being compiled and linked into the program. Unity builds typically suppress the separate build of implementation files, for the obvious reason that implementation files usually contain strong definitions and so the merged build will immediately fail with a duplicate definition.
Someone doing a standard unity build will see zero impact from this heuristic, since all of the code will actually be defined in a “header” file.
The programmer is doing a non-standard unity build where they combine implementation files with e.g. cat rather than using #include. As above, the heuristic is only actually wrong if they also separately compile and link in the implementation files, which is not how unity builds work.
I’ve never seen anyone do a unity build this way — why would you not use #include? you’re literally just adding extra I/O to your build and losing source information — but if they did, they’d probably be happy about the heuristic because unity builds are typically done specifically to get more aggressive cross-TU optimization. If anything, I think we might get requests from standard unity build users to make the heuristic more aggressive so that all the #included implementation files still count.
The programmer is building a preprocessed file. As Eli says, a normal preprocessed file actually doesn’t interfere with this heuristic because of line directives, so the programmer must actually be building a stripped preprocessed file. This is, again, a very weird thing to do, but if we’re worried about it, I think it would be very easy to adjust the heuristic to not do anything if there are no #includes in the file at all.
So as I see it, the false positives all involve pretty questionable choices. I don’t think we should feel bad about a heuristic optimization that might lead to some extra code size if the programmer is doing something bizarre.
I don’t think we should feel bad about a heuristic optimization that might lead to some extra code size if the programmer is doing something bizarre.
Right, and agree that the false positive situations are bizarre, yet the potential for this optimization is definitely not bizarre or rare, in fact after skimming multiple large established C++ codebases recently, I think it’s safe to say that it’s actually quite common to fail to manually internalize templated code + inline class methods in .cpp files at the source code level via anonymous namespaces. LLVM itself has a lot of instances of that.
Yeah, even in Clang where we’re somewhat fanatical about these things, I imagine there’s still quite a bit of code that’s “really” internal but has external linkage. It’s just really easy to write. Diagnostics and education and better build systems are all great, but I agree that it’s still something we can do a better job at out of the box.
