Escape analysis hates copy elision (2021)
quuxplusone.github.io
quuxplusone.github.io
See this godbolt example https://godbolt.org/z/nbzd59E33
As I understand it, performing a const_cast itself isn't undefined behavior, which is why the compiler cannot assume function f doesn't modify the local. However, if we mark the local variable as const, the compiler is able to assume no modification will occur (because that would be undefined) and optimize the return.
int y = 42;
const int x = y;
In my example, even though `x` is a `const` local, the assembly still shows that it reloads `x` and adds `1` if we assign to it from a non-const local `y`.
Does the way x is initialized make it not "const-y" enough?
const int y = 42;
const int x = y;
So, it seems that all these compilers agree that modifying `x` is undefined behavior if `y` is const, but is defined if `y` is mutable.
I am not sure why this is.
I may have misunderstood, but I didn't get the impression this should be the case from reading: https://en.cppreference.com/w/cpp/language/cv
My best guess is that for some reason, `x` is a constant object only if initialized itself via a constant object. But I couldn't find anything saying that is the case. I asked on the #learn channel of cppslack.
std::unique_ptr<S> *global;
std::unique_ptr<S> S::make() {
std::unique_ptr<S> origp = std::make_unique<S>();
global = &origp;
return origp;
}
void take_ownership(S *rawp) {
delete rawp;
*global = std::make_unique<S>();
}
Why can't the compiler rule out that possibility? That looks like undefined behavior code to me, so thus the compiler could rule it out. S::make() is storing a pointer to a local variable (origp), and then that pointer is being accessed after S::make() has returned. I'm pretty sure that's undefined behavior.
At the very least, most compilers support doing interprocedural escape analysis, whether it's on by default at basic optimization levels or not.
In that sense, this is not a very hard problem - it was solvable in the 70's.
If you give the compiler all the source, or have libraries compiled as fat lto objects, etc, it should work fine.
The summary mod/ref info should be enough to get it right, because it should say the function does not modify the argument, and that should get propagated through.
The tricky case is where it sometimes modifies the argument - the summary data is not flow sensitive, IIRC
Flow sensitive algorithms are still really expensive worst case (N^3 minimum, sometimes exponential), but could be made practical here using BDD's. Most compilers still do not use BDD's to represent this sort of large binary decision data, even though they are very good at it. It's an area where research always felt more advanced than production (IE even if you don't go whole-hog on datalog, the data structures are still very useful for this sort of otherwise-memory/time intensive data)
In any, fat LTO should defintely be enough.
The question is whether rust gives this object identity guarantee as well and, if it does, whether there are other rules (like uniqueness of mutable refences) that still allows the optimisation.
[0] https://doc.rust-lang.org/1.73.0/std/mem/fn.transmute.html#e...
1. A reference cannot outlive its referent
2. A mutable reference cannot be aliased
https://doc.rust-lang.org/nomicon/references.html
Therefore, any use of transmute that extends a lifetime is UB if it causes the reference to outlive the referent. And because it's UB, the backend is going to assume the invariant holds universally and will optimize accordingly.
The Nomicon also has a section on generating lifetimes via transmute, which it calls "unbounded lifetimes": https://doc.rust-lang.org/nomicon/unbounded-lifetimes.html
By itself, a transmute of a currently-live reference cannot make it outlive its referent, in the sense used by the Rustonomicon. As it says later [0], a reference is alive until the point when it is last used, and no further.
Thus, with unsafe code, the lifetime of a reference can extend past the point when it stops being alive. As a consequence, extending the lifetime can never cause UB by itself: only using the reference after it has been invalidated can cause language-level UB.
Since language-level UB is based on liveness rather than lifetime, the compiler must assume that a reference passed to a function is valid even after it returns, up until the caller invalidates the reference by performing an operation incompatible with it remaining alive.
[0] https://doc.rust-lang.org/nomicon/lifetimes.html#the-area-co...
When a reference is 'used' is much broader than you might expect; https://github.com/rust-lang/rust/issues/52898 is a SIGILL from merely creating a null reference, never 'using' it.
fn foo(x: &'a T) -> &'a T { x }
> The parameter must not escape the function call (e.g. by being assigned to a global variable). Ignored for any parameter that is not a reference type.
https://dlang.org/spec/function.html#scope-parameters
See also: https://dlang.org/blog/2023/10/02/crafting-self-evident-code... , https://news.ycombinator.com/item?id=37748543
https://learn.microsoft.com/en-us/dotnet/csharp/language-ref...
https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaP...
Lifetimes do not affect whether or not something is UB on the language level; they only dictate which operations are safe and which are unsafe, and thus they act as a "social contract" for library-level UB.
fn example<'a>(r: &'a mut i32) -> &'static mut i32 {
unsafe { std::mem::transmute(r) }
}
fn main() {
let mut x: i32 = 5;
let ptr: &'static mut i32 = example(&mut x);
*ptr = 6;
println!("{x}");
}
https://play.rust-lang.org/?version=stable&mode=debug&editio...
You can run through Miri and confirm there's no UB even though we're modifying `ptr`, whose lifetime has been extended beyond the length of the function.
However, Rust does have extra guarantees here which make this irrelevant to the pessimization problem in the linked article - you cannot ever legally convert a `&T` into a `&mut T` - this is always UB. This means that Rust guarantees that `example` does not modify `x` (unless e.g. it contains an `UnsafeCell`, like a `Mutex`'s contents), and so it does not need to defensively reload its value.
That is to say: Rust, just like C++, makes it legal (but frowned upon) to "leak" a reference beyond the stated lifetime it's provided as. But unlike C++, it is (always!) illegal to "upgrade" a `&T` into a `&mut T`, and thus the fact that it escapes does not hinder other optimizations.
Obviously, good code should treat it as more than just a comment - using `const` correctly clarifies intent and makes it possible to stay sane as a C++ developer, but the abstract machine doesn't care.
In C++, you can basically always `const_cast` a `const T&` into a `T&` and then modify it without causing UB. A function that accepts a `const T&` is just pinky promising that it will be polite and probably not do that.
It is only UB if the underlying object is "actually const", and even then, it doesn't cause UB until you actually perform the mutation; creating the mutable reference itself is perfectly fine.
For example, the following is perfectly legal:
int& upgrade_to_mut(const int& x) {
return *const_cast<int*>(&x);
}
int x = 5;
const int& x_ref = x;
int& x_ref_mut = upgrade_to_mut(x_ref);
x_ref_mut = 6;
int& upgrade_to_mut(const int& x) {
return *const_cast<int*>(&x);
}
const int y = 5;
const int& y_ref = y;
int& y_ref_mut = upgrade_to_mut(y_ref); // it is actually legal to produce y_ref_mut, but we cannot modify it
y_ref_mut = 6; // this is UB: cannot modify a const object 'y'
> Modifying a const object through a non-const access path and referring to a volatile object through a non-volatile glvalue results in undefined behavior.
and both compiler have tried to take advantage of this in the past.
int x; // not a const object, so can be freely modified
const int y; // is a const object, so cannot be modified
The reason for mentioning a "non-const access path" is that the type system forbids you from modifying through a const access path in the first place, so the program would already be rejected if you tried that.
I'm not saying it's a good idea to go around dropping const qualifications; `const_cast` is mostly evil and should be avoided. But at the level of the abstract machine, it's a no-op, even when going from const -> non-const, other than changing the type of the provided pointer.
The benefit of `const` is that if you don't use C-style casts that discard constness, and you don't use `const_cast`, and you don't use `mutable` or other type-unsafe or const-unsafe features, it's not possible to accidentally obtain a non-const pointer to a const object. Thus C++ actually helps you avoid this UB pretty well. But the fact that general conversion from const to non-const is permitted reduces the kinds of optimizations that can be performed.
In other words, "const" (in a global context) can tell the compiler "you don't have to copy this to RAM, just read it directly from non-volatile storage." Obviously, that would be undesirable on a desktop computer, but if you're dealing with a wee little microcontroller, it's very helpful.
Another good example is string literals (except when initializing a non-const `char[]` variable), which are often allocated in read-only data in the same way, since they are const objects too.
In Rust, moves are built in into the language. Types with destructors can't have implicit copying, and there are no copy constructors. There is no moved-from state of objects, and destructors never run redundantly. Box (Rust's unique_ptr) is statically guaranteed to be always non-null and have a single owner at all times. So the language has no equivalent of omitting std::move, and has no semantically-observable copy to elide.
See https://rust.godbolt.org/z/PnWv5d6n9 and https://rust.godbolt.org/z/Efosx3Wea
Rust does emit memcpy for its moves, and for that it has got some specific LLVM improvements: https://khei4.github.io/gsoc2023/