11 ms·

What is that makes NVRO so much more difficult to implement? Why couldn't they mandate that just like RVO? Do compilers literally just special case a simple ret

What is that makes NVRO so much more difficult to implement? Why couldn't they mandate that just like RVO? Do compilers literally just special case a simple return statement of a direct construction or something?

bluGill 15d ago
The simple cases are simple. However the complex cases get hard. mytype foo() { mytype one; ... if(something) { mytype two; ... return two; } return one; } Is going to be much harder because you don't know are compile time which is returned and so cannot construct the one you return in the correct place. That is just off the top of my head, I'm not a compiler writer, I'm sure they have figured out the simple versions of the above, but you can start to see the complex versions that they can't.
- leni536 15d ago
  That one is not too hard either. `one` simply can't be NRVO'd as there is a runtime path in scope of it that doesn't return it. `two` can be (unless you hide some other return within ...).
  - bluGill 15d ago
    You can structre the code differently to get around that. There is a real desire to use NRVO "one" in cases when it is returned as well, if possible.
fluoridation 15d ago
N/RVO works by (at the machine language level, of course) rewriting the function signature to return void and take an extra pointer parameter, which is written to before returning. If you're returning a newly-constructed object, the compiler can rewrite that into calling the constructor on the pointer, but if you're returning a named object, the class may have a non-trivial destructor that needs to run after the move, such that it's not possible to rewrite uses of the local object into uses of the pointer. I'm not too confident on that last part, because such an implementation would mess with semantics in case of an exception, so anyone feel free to correct me on that.
- dataflow 15d ago
  > N/RVO works by (at the machine language level, of course) rewriting the function signature to return void and take an extra pointer parameter This sounds wrong, are you sure? Would you mind demonstrating with an example on godbolt? Whether NRVO applies or not, the ABI should be the same, AFAIK.
  - fluoridation 15d ago
    Yes, of that I'm sure. This optimization is only possible if the compiler has control of both sides of a call. If the function may be callable from other translation units or modules I imagine it generates a thin wrapper that's externally callable.
    - dgrunwald 15d ago
      The optimization is often possible even if the computer does not see the call, because most (all?) ABIs have always required hidden pointer parameters for class types with non-trivial destructors. https://godbolt.org/z/9WvnEvEYh https://godbolt.org/z/9WvnEvEYh Note how `std::unique_ptr<int>` effectively passed as a `int**`; and that the by-value unique_ptr is not destroyed at the end of the function -- destroying parameters is instead the caller's job (and commonly only happens at the end of the full expression containing the call -- though this choice is implementation-defined). But that can only work if the caller can see the updated value of the parameter (to avoid double-free for `clear`) -> thus the need to pass the parameter by hidden pointer.
    - dgrunwald 13d ago
      I don't know why I wrote the comment about parameters earlier -- (N)RVO is about return values. Those have a different reason for being passed behind a hidden pointer: the class type might have self-referencing pointers, so there must be an explicit move/copy constructor call whenever it changes address, to give the class an opportunity to update those pointers. This cannot work when returning in a register: the callee doesn't know the target address, and the caller doesn't the source address, so neither can call the move constructor. Thus, all ABIs must pass a pointer (or let caller+callee agree on a memory location in some other way) for types that aren't trivially copyable.
dataflow 15d ago
The point of (N)RVO is to directly construct the return value in-place at the calling frame. Which requires knowing what object will land there. In RVO there is no problem because you know what object is the one you need to put there. In NRVO there is a problem because you might have one of multiple objects being returned and you need to know which one to construct at the call site; it can't be all of them on top of each other. But you don't necessarily know at the time of construction whether that object will be the one that is actually returned. Doing so requires imperfect code analysis so the standard would need to define the complicated analyses to perform.
whizzter 15d ago
RVO is easy to detect since it happens only in expressions in return-statements. NRVO requires the compiler to analyze the flow, like if 2 different variables/constructions can lead to the return (what one do we take, or can we do either later?). Also, with RVO it's easy to detect and elide destruction calling for things going out of scope whilst NRVO would require more careful management of destruction order,etc. Basically, NRVO touches a lot of things in "inconventient" places that can easily require reworking internal compiler structures to track destinations whilst RVO was probably far easier to just "hack in".
- sprocketz 15d ago
  I figured any half decent compiler already do plenty of flow and liveness analysis on everything for register allocation, dead code elimination and what not. Maybe it's the guaranteed elision that makes it a problem, like you can't fail the analysis, but then maybe you go the rust route - fail to compile and urge the programmer to rewrite their code so it accepts it. Make it opt in with [[must_elide]] so old code still works I guess.
  - jcranmer 15d ago
    Despite its name, NRVO isn't an optimization performed by the optimizer, it's something done by the frontend of the compiler before it generates the code for the optimizer to run on. The frontend is extremely reluctant to do anything like flow analysis, in large part because the frontend doesn't even really have any code to do the analysis on, just the AST. More people (including far too many on the committee itself) need to understand the separation between the different parts of the compiler, and what each part can and cannot do effectively.
    - whizzter 15d ago
      They probably _were_, since lower level code representations often has little notion of complex types and their semantics they could be kept clean and focused on machine code, however type inference in a language like C++ complicates such matters immensly since an assignment can be both a register move and a function call. Template resolution solved that in the past, but C++ today allows auto in so many places that I'm uncertain that it can be done without some flow based support (if constexpr comes to mind). I mentioned ClangIR(MLIR) in the sibling comment here, feels like it was built for stuff like this.
locknitpicker 15d ago
> What is that makes NVRO so much more difficult to implement? I recall reading that at a high level RVO is implemented by treating the return value as an external object. In simple terms (simplistic terms) RVO then works by - first instantiating the return variable, - passing the var by reference to the function, - and then use return value to actually initialize the variable passed by reference. The moment there's some funny logic on what to write to that output value, the problem gets far more complex.
quuxplusone 15d ago
The problem is that "predictable reliable NRVO" is still a research problem. Real-world compilers do NRVO a lot but not in a way that is perfectly predictable — that is to say, not in a way that could be standardized across all compilers (or even between different releases of the same compiler). A "perfectly predictable" algorithm was proposed in Anton Zhilin's P2025, back in the year 2021: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2025r2.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p20... but unfortunately it had some subtle corner-case problems (which I do not remember), so it was sent back for revision, and never returned with a fix. (Maybe because a fix wasn't possible; again I don't remember what the deal was exactly.) The Right Path Forward would be for MSVC, GCC, and Clang all to try implementing P2025's algorithm in their front ends. Either something concrete breaks (reminding me what the problem was), or else all three mainstream compilers gain predictable NRVO and then we can "standardize existing practice." But the Right Path Forward requires tedious work by at least three people, which is hard.

bluGill 15d ago

The simple cases are simple. However the complex cases get hard. mytype foo() { mytype one; ... if(something) { mytype two; ... return two; } return one; } Is going to be much harder because you don't know are compile time which is returned and so cannot construct the one you return in the correct place. That is just off the top of my head, I'm not a compiler writer, I'm sure they have figured out the simple versions of the above, but you can start to see the complex versions that they can't.

leni536 15d ago
That one is not too hard either. `one` simply can't be NRVO'd as there is a runtime path in scope of it that doesn't return it. `two` can be (unless you hide some other return within ...).
- bluGill 15d ago
  You can structre the code differently to get around that. There is a real desire to use NRVO "one" in cases when it is returned as well, if possible.

fluoridation 15d ago

N/RVO works by (at the machine language level, of course) rewriting the function signature to return void and take an extra pointer parameter, which is written to before returning. If you're returning a newly-constructed object, the compiler can rewrite that into calling the constructor on the pointer, but if you're returning a named object, the class may have a non-trivial destructor that needs to run after the move, such that it's not possible to rewrite uses of the local object into uses of the pointer. I'm not too confident on that last part, because such an implementation would mess with semantics in case of an exception, so anyone feel free to correct me on that.

dataflow 15d ago
> N/RVO works by (at the machine language level, of course) rewriting the function signature to return void and take an extra pointer parameter This sounds wrong, are you sure? Would you mind demonstrating with an example on godbolt? Whether NRVO applies or not, the ABI should be the same, AFAIK.
- fluoridation 15d ago
  Yes, of that I'm sure. This optimization is only possible if the compiler has control of both sides of a call. If the function may be callable from other translation units or modules I imagine it generates a thin wrapper that's externally callable.
  - dgrunwald 15d ago
    The optimization is often possible even if the computer does not see the call, because most (all?) ABIs have always required hidden pointer parameters for class types with non-trivial destructors. https://godbolt.org/z/9WvnEvEYh https://godbolt.org/z/9WvnEvEYh Note how `std::unique_ptr<int>` effectively passed as a `int**`; and that the by-value unique_ptr is not destroyed at the end of the function -- destroying parameters is instead the caller's job (and commonly only happens at the end of the full expression containing the call -- though this choice is implementation-defined). But that can only work if the caller can see the updated value of the parameter (to avoid double-free for `clear`) -> thus the need to pass the parameter by hidden pointer.
  - dgrunwald 13d ago
    I don't know why I wrote the comment about parameters earlier -- (N)RVO is about return values. Those have a different reason for being passed behind a hidden pointer: the class type might have self-referencing pointers, so there must be an explicit move/copy constructor call whenever it changes address, to give the class an opportunity to update those pointers. This cannot work when returning in a register: the callee doesn't know the target address, and the caller doesn't the source address, so neither can call the move constructor. Thus, all ABIs must pass a pointer (or let caller+callee agree on a memory location in some other way) for types that aren't trivially copyable.

dataflow 15d ago

The point of (N)RVO is to directly construct the return value in-place at the calling frame. Which requires knowing what object will land there. In RVO there is no problem because you know what object is the one you need to put there. In NRVO there is a problem because you might have one of multiple objects being returned and you need to know which one to construct at the call site; it can't be all of them on top of each other. But you don't necessarily know at the time of construction whether that object will be the one that is actually returned. Doing so requires imperfect code analysis so the standard would need to define the complicated analyses to perform.

whizzter 15d ago

RVO is easy to detect since it happens only in expressions in return-statements. NRVO requires the compiler to analyze the flow, like if 2 different variables/constructions can lead to the return (what one do we take, or can we do either later?). Also, with RVO it's easy to detect and elide destruction calling for things going out of scope whilst NRVO would require more careful management of destruction order,etc. Basically, NRVO touches a lot of things in "inconventient" places that can easily require reworking internal compiler structures to track destinations whilst RVO was probably far easier to just "hack in".

sprocketz 15d ago
I figured any half decent compiler already do plenty of flow and liveness analysis on everything for register allocation, dead code elimination and what not. Maybe it's the guaranteed elision that makes it a problem, like you can't fail the analysis, but then maybe you go the rust route - fail to compile and urge the programmer to rewrite their code so it accepts it. Make it opt in with [[must_elide]] so old code still works I guess.
- jcranmer 15d ago
  Despite its name, NRVO isn't an optimization performed by the optimizer, it's something done by the frontend of the compiler before it generates the code for the optimizer to run on. The frontend is extremely reluctant to do anything like flow analysis, in large part because the frontend doesn't even really have any code to do the analysis on, just the AST. More people (including far too many on the committee itself) need to understand the separation between the different parts of the compiler, and what each part can and cannot do effectively.
  - whizzter 15d ago
    They probably _were_, since lower level code representations often has little notion of complex types and their semantics they could be kept clean and focused on machine code, however type inference in a language like C++ complicates such matters immensly since an assignment can be both a register move and a function call. Template resolution solved that in the past, but C++ today allows auto in so many places that I'm uncertain that it can be done without some flow based support (if constexpr comes to mind). I mentioned ClangIR(MLIR) in the sibling comment here, feels like it was built for stuff like this.

locknitpicker 15d ago

> What is that makes NVRO so much more difficult to implement? I recall reading that at a high level RVO is implemented by treating the return value as an external object. In simple terms (simplistic terms) RVO then works by - first instantiating the return variable, - passing the var by reference to the function, - and then use return value to actually initialize the variable passed by reference. The moment there's some funny logic on what to write to that output value, the problem gets far more complex.

quuxplusone 15d ago

The problem is that "predictable reliable NRVO" is still a research problem. Real-world compilers do NRVO a lot but not in a way that is perfectly predictable — that is to say, not in a way that could be standardized across all compilers (or even between different releases of the same compiler). A "perfectly predictable" algorithm was proposed in Anton Zhilin's P2025, back in the year 2021: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2025r2.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p20... but unfortunately it had some subtle corner-case problems (which I do not remember), so it was sent back for revision, and never returned with a fix. (Maybe because a fix wasn't possible; again I don't remember what the deal was exactly.) The Right Path Forward would be for MSVC, GCC, and Clang all to try implementing P2025's algorithm in their front ends. Either something concrete breaks (reminding me what the problem was), or else all three mainstream compilers gain predictable NRVO and then we can "standardize existing practice." But the Right Path Forward requires tedious work by at least three people, which is hard.