I also wonder what about devirtualization of dyn traits in Rust. Sure, impl traits like foo<T: AsRef>(bar: T) or foo(bar: impl AsRef) is for sure devirtualized, but foo(bar: &dyn AsRef) or most likely foo(bar: Box<dyn AsRef>), far as I remember, isn't always devirtualized. Sometimes it does, sometimes it doesn't. I wonder if it is MIR that did it, or just completely handed off to LLVM for detection.
MSVC (Microsoft's C++ compiler) had an pretty advanced inter-procedural (LTO) way of doing devirtualization, but it was so buggy and slow that it eventually got disabled. It was trying to prove that a pointer can only target a certain class all the time (or maybe a couple), but things get really messy with typical C/C++ code and even worse once you have DLLs which may inject new derived classes.
For comparison, Java will devirtualize calls if the call site typically calls only a single type. To the extent that writing a byte to a ByteBuffer, which looks like five or six virtual calls if you follow the java source code, actually ends up being a single assembly store instruction.
Nice post, I had never thought about those tricky ways of proving leafness outside of the obvious "final".
Re "When we know the dynamic type", I made a similar assertion on HN years ago, and of course it turned out that there's a weird wrinkle:
If the code in your snippet is expanded to:
Derived d;
Base *p = &d;
any_external_func(); // Added
p->f();
where any_external_func() is defined in some other translation unit (and, I'm now fairly sure, Derived's ctor is also defined in another translation unit, or it transitively calls something that is), this would seem not to affect anything -- but in fact the compiler must not assume that p's dynamic type is still Derived by the final line. Why? Because the following insane sequence of events might have happened:
1. d's ctor registers its this pointer in some global table.
2. Using this table, any_external_func() calls d's dtor and then overwrites it in place with a fresh instance of Base using placement new, which replaces everything, including its vtable, meaning that p->f() should call Base's version, not Derived's.
(It might be UB to call placement new on static or automatic storage holding an in-lifetime object, I don't know. If so, the above construction is moot -- but the closely analogous situation where we instead dynamically allocate dp = new Derived() still goes through, and is nearly as surprising.)
I also wonder what about devirtualization of dyn traits in Rust. Sure, impl traits like foo<T: AsRef>(bar: T) or foo(bar: impl AsRef) is for sure devirtualized, but foo(bar: &dyn AsRef) or most likely foo(bar: Box<dyn AsRef>), far as I remember, isn't always devirtualized. Sometimes it does, sometimes it doesn't. I wonder if it is MIR that did it, or just completely handed off to LLVM for detection.
MSVC (Microsoft's C++ compiler) had an pretty advanced inter-procedural (LTO) way of doing devirtualization, but it was so buggy and slow that it eventually got disabled. It was trying to prove that a pointer can only target a certain class all the time (or maybe a couple), but things get really messy with typical C/C++ code and even worse once you have DLLs which may inject new derived classes.
> final method
A pedantic Pete would mention C++ has member functions.
For comparison, Java will devirtualize calls if the call site typically calls only a single type. To the extent that writing a byte to a ByteBuffer, which looks like five or six virtual calls if you follow the java source code, actually ends up being a single assembly store instruction.
Nice post, I had never thought about those tricky ways of proving leafness outside of the obvious "final".
Re "When we know the dynamic type", I made a similar assertion on HN years ago, and of course it turned out that there's a weird wrinkle:
If the code in your snippet is expanded to:
where any_external_func() is defined in some other translation unit (and, I'm now fairly sure, Derived's ctor is also defined in another translation unit, or it transitively calls something that is), this would seem not to affect anything -- but in fact the compiler must not assume that p's dynamic type is still Derived by the final line. Why? Because the following insane sequence of events might have happened:1. d's ctor registers its this pointer in some global table.
2. Using this table, any_external_func() calls d's dtor and then overwrites it in place with a fresh instance of Base using placement new, which replaces everything, including its vtable, meaning that p->f() should call Base's version, not Derived's.
(It might be UB to call placement new on static or automatic storage holding an in-lifetime object, I don't know. If so, the above construction is moot -- but the closely analogous situation where we instead dynamically allocate dp = new Derived() still goes through, and is nearly as surprising.)