6 ms·
Escape analysis hates copy elision (2021)
- MaxBarraclough 3y agoRelated reading: this year the author submitted a GCC bug-report on this topic, linking back to the 2021 blog post. The bug appears to be still unresolved. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109945 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109945
- sapiogram 3y agoDoes anyone know what guarantees Rust functions have regarding escape analysis? In particular, is the `x` reference in `fn foo(x: &T)` guaranteed to not outlive the function, or would it be legal for `foo` to `transmute()` it into a `&'static T` and have to escape into a global?
- mattashii 3y agoRust borrows must not exceed the lifetime associated with the borrow. By default that indeed means the borrow/reference cannot be moved into a context that outlives the function's execution, so it indeed can't be moved into a static global (unless `unsafe` is used explicitly)
- gpderetta 3y agoBut unsafe could be used inside the (rust equivalent) body of make and take_ownership without the compiler knowing. So would the rust compiler need to take this possibility into account when optimizing or not?
- johncolanduoni 3y agoNo, that would be undefined behavior, as would other transmutations you could do with unsafe like converting it to a mutable reference.
- gpderetta 3y agoWhat is UB in unsafe rust? You would be taking the addresses and then using the address of a variable that is still in scope. This assuming that rust has the same guaranteed elision as C++, extending the lifetime of an automatic object into the caller.
- kibwen 3y agoI believe the parent is saying "that would be undefined behavior" in answer to your question "would the rust compiler need to take this possibility into account". The compiler would not take this possibility into account, because the fact that references cannot outlive their referents is an invariant of the language that can only be broken by incorrect unsafe code. (To put it another way, in any context where the compiler would take this into account, it would do so regardless of the existence of the unsafe code, because unsafe code still ultimately has to uphold all the same invariants as safe code.)
- gpderetta 3y agoSure, but the reference doesn't outlive the referent in c++: the language guarantees that the local object in make is exactly the same object in the caller's caller. 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.
- LegionMammal978 3y agoTransmuting lifetimes is one of the operations explicitly allowed for the std::mem::transmute() function [0]; lifetimes are only there to help safe code, and they have no effect on language-level UB. In fact, the 'static reference will be valid until the caller otherwise invalidates it. [0] https://doc.rust-lang.org/1.73.0/std/mem/fn.transmute.html#examples https://doc.rust-lang.org/1.73.0/std/mem/fn.transmute.html#e...
- kibwen 3y ago
- kaba0 3y agoBut there could be an object with the same lifetime as the function passed to both f and h, in the article’s example — could they not collaborate still in safe Rust? Or does the compiler know about that?
- alexchamberlain 3y agoNo, the following would be valid (if a little pointless): fn foo(x: &'a T) -> &'a T { x }
- sapiogram 3y agoYour example changed the type of the function, though. I'm assuming there is no `&T` in the function's output type.
- deleted 3y ago[deleted]
- alexchamberlain 3y agoOh sorry; I had misunderstood the question.
- MaxBarraclough 3y agoI'm afraid I don't know about Rust, but D has the scope parameter storage class for this. It enables the following compiler-enforced guarantee: > 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 https://dlang.org/spec/function.html#scope-parameters See also: https://dlang.org/blog/2023/10/02/crafting-self-evident-code-with-d/#self-documentingfunctiondeclarations https://dlang.org/blog/2023/10/02/crafting-self-evident-code... , https://news.ycombinator.com/item?id=37748543 https://news.ycombinator.com/item?id=37748543
- funnymony 3y agoLink to exact section: https://dlang.org/spec/function.html#scope-parameters https://dlang.org/spec/function.html#scope-parameters
- MaxBarraclough 3y agoGood call, have updated my links.
- pjmlp 3y agoNowadays also available in C#. https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/statements/declarations#scoped-ref https://learn.microsoft.com/en-us/dotnet/csharp/language-ref...
- WirelessGigabit 3y agoYou can't do that. Storing the reference as a &'static T will be ok for the lifetime of your function, there is no guarantee that the thing the &'static T points to will be alive after that. https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1DEArgoKkl9ZATwDKjdAGFUtEywYgATKUcAZPAZMADl3ACNMYgkAdlIAB1QFQjsGFzcPb3jE5IEAoNCWCKiuWKtMGxShAiZiAjT3Tx8yioEqmoI8kPDImMtq2vqMpv6OwK7CnpKASktUE2Jkdg4zTABqc3QQEDYWLYJiQwUWEwJMAFIAZgAhM40AQVu78yZbZFXjglWAWQBNAH0hAAVABKcicgL%2BwOwADEQKszl4AGxfACeVVMNnhFwAIvCkaj0SYbBAEV5gLRUGExKSppcbvdHuYMZ8CfsiQQSUiwBxnq91vtaddHo88Cw4rR%2BZsQFQWAQttjMGETMBVvxiN80WzMWdovS7qsDaqGKrZZzEVYqKRVXCEYiPpKtjK5SBoSQWC9TsRLk5uX9LtgpqsALT%2Bh3S2VbYGYBQmWifHV6w1J1UAOiwSuAfwIJnFmE5XlZzJpKZomFo6DNFpTGimJcCeAUCAgtPuSZ12OF0Q7DPuovFq2xxFQcVVJA1hO1useSaoxvQQ7iZvtFsDCenyYNcWIgQItAYYEgpIA4qgMGEUex4bqQJdoe3SVaV3T1wb7wyu8L7nETGEje8mIEzZXomhpbjue4HvmCY3hcd4fl4PirCYDAKEwVBrAm3z/ECoLgpCMJXtigp6i%2BwGkUm9CfCwKJ/Ey7JYrihbsvmFKiLQNLPj2%2BobvyJCYLR1SvEuNF0TYxGftxG4APRSas87DhA1ECcy4mtoab4PGpm7boIEGHgh0G3veCFWshqHocBWEAiCYIQlC0KEapDwflxs68cQ/G8ngyDUKefweVQNr4pqKlkVpSEoWhGG6lZOG2fhDmXLi%2ByHB8eb8Kg/mYFQq4fkK77dppdwcDMtCcAArLwngcFopCoJwwJmJ8ChzAsGFeBcPCkHKNUlTMADWIAXJIKYXAAnAAHFwiLRFwGgXIii0LfonCSFVmi8PVHC8AoIAaN1G0zHAsAwIgKCoGKdCROQlBoJd9BRMQJQXPtWAAG7eZgABqeCYAA7gA8nEjCcF1NBxpEu0QGEG2kGEgQ1CioO8PDzDECiANhNo5Q9V1d1sIIAMMLQSO9aQ6bKk4Yi0Lt3C8Fg7pGOIZP4B5FRvdGsOYKo5QnEstU7mWyP6HgYQHOjLhYLD%2ByiodfAGMACg/f9QMg3TMiCCIYjsFIGvyEoaiw7oXD6IYxhNSLYS7ZAMzDrYAi00GTirHbQb0Bz7E4rVqAc8Q25YNbUDMGwICYPg9sMKQb1iCYSxeBoXg8FMMzNBHDgMM4rgNCAsT%2BGMBRFBIJsJEkEeDJ4sQlzkDCdAXkwm6nlQjOXOeWGWONN%2B0tfdMUDfN1nGSlCM3cTL3KetYsEilRV61k1tqymOYbxcCm0QXNWqwQLghBjginVTLwPVaMnpCDZ1KZjYnGgTdEY2SBNY3RBo0TRIiK0cGtpC7OV%2B3Vd7nA7T2gdXqR1ToQCQHMAg34LAUAgHdOIV1iDBFYEsReBBl6r3XrVMOO9/Z6H4JrNiOtpAEP1iodQZNjakD%2BgcOIyNp4cEqqQP%2Bm1OAAxONAl2VAF5NQwWvDeEAXD3UiHifeh9DozAQJgJgWAojNnfp/b%2Bv9YZbUAftI%2BfVT5DS8CmLw0RJBSEvmNH%2BiIpAmzKhwC4s9/7bWAcfUgx0oBgKQPAxBN04EXQQQ9EAT016vUwB9RYytAbA2qmDOgnooYwzJqjRGwtYno0xtjGwwt8aMAIETEmsMKbACprQGmwsGZm2ZrVVmHcOa02wTzZAfNYaCwsV1WgotxYoklvzQ%2B25dggPlkwRWwTVZhN4KQrW4hdakMUOQo2mQDBGB8RbJpVt4C2ziBHR2ztXbuzLElLwm1fb%2B05rAYO7AcERyjjHOOCck4p3bi0TwEBHAtxNnnfIPc9BVzLgPTwxdsgRxHoXBuNyI5tAGJ8vQjdWjD3zq8vu7RHl9C7lC0eU9ZjzEnlwBhTCWF1U4DwpeqwV78I0JvbeRB1R73ReIkBA0hrrwuHoxEE0FoaC4HohC0gLGKJAD/ZhKiAGWCARo0B8BwEgEgdA9xriHrIJDhwNBfCsG8BOSQPAmwTbDKIRIEhsgJmG0oZkGhTA6F0wxdY1hHB2FQJOFw3F6D8WYIEUIrxIi95eAPnYzRUiZE9HkRy3gSieVzz5btdREitEXFpfSxliJmWsq8OyzgViA02MpcfBhOyk1mpTZo32SR7CSCAA%3D https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaP...
- LegionMammal978 3y agoNo, there is no guarantee that the reference will not be valid after the function returns. The only guarantee is that the reference will not be valid after the caller of the function modifies the referent (outside of an UnsafeCell), deallocates it, or creates a mutable reference to it. So there still is some escape analysis possible, in that any escape is scoped to the next modification. 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.
- nathanrf 3y agoIt is unsound to transmute `&'a T` into `&'static T`, but it is not UB - as long as all of the subsequent uses of the transmuted reference obey the "real" lifetime of the original reference: 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}"); } (because it's unsound, it's considered wrong to do this - you should not intentionally write functions whose types are lies, and this one definitely lies, so it should be marked `unsafe` - but this is not automatic UB) https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=978e04a0df4d8c191533674fbe358a39 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.
- pornel 3y agoRegardless of escape analysis, this problem doesn't exist in Rust, because the language features that lead to this problem don't exist either. 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 https://rust.godbolt.org/z/PnWv5d6n9 and https://rust.godbolt.org/z/Efosx3Wea 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/ https://khei4.github.io/gsoc2023/
- IAmLiterallyAB 3y agoOne of the escape analysis examples in the article got me thinking. Turns out this is one of those cases where marking a local variable const _does_ result in different code. See this godbolt example https://godbolt.org/z/nbzd59E33 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.
- levzettelin 3y agoInteresting point! That's my understanding as well.
- celrod 3y agoIt's unfortunately easy to defeat this, e.g. int y = 42; const int x = y; is enough, even though `x` is still a `const` local variable. https://godbolt.org/z/7vre49xb1 https://godbolt.org/z/7vre49xb1
- jenadine 3y agoI don't understand what is defeated in your example.
- celrod 3y agoI edited to add a godbolt link, but repeating here: https://godbolt.org/z/7vre49xb1 https://godbolt.org/z/7vre49xb1 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`.
- gameman144 3y agoIsn't that expected since 'y' is still non-const though? In your example, I'd expect 'x' to not escape, since a const-cast of it is undefined.
- celrod 3y ago[Deleted - responded to the wrong comment. I meant to respond to IAmLiteralyAB.]
- MauranKilom 3y agoSorry, can you elaborate what or who you are replying to?
- DannyBee 3y agoMost escape analysis these days is interprocedural, and as long as it can see all the things that happen to the variable, it is fine. 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.
- eru 3y agoInteresting. Thin lto wouldn't be enough?
- DannyBee 3y agoIt should be, actually, as long as you give it all the source code or give it object files with the summary data in them. 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.
- Thorrez 3y ago> Suppose S::make and take_ownership were secretly colluding, like this: 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>(); } >The compiler cannot rule out this possibility 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.
- bobbyi 3y agoThe usual justification for having a concept of "undefined behavior" at all is specifically to allow compilers to "rule out this possibility" so they can make this sort of optimization.
- eru 3y agoAt least that's the modern day retro-active justification. The historical origins of undefined behaviour in eg the C standard are murkier.