Bug 12440 – Implement whole-program analysis

The idea is to examine the whole program's class hierarchies to determine which classes can be made final. Final classes can then benefit from non-virtual dispatch of its virtual functions, and even inline them. Normally, such is not possible because a linked-in object file that the compiler doesn't know about could derive from a class. Hence, to work, this would have to add a flag to the compiler, such as -wholeprogram, that causes the compiler to make the assumption that all classes defined in files supplied to the compiler on the command line (not imports) are never derived from from other object files or DLLs. This could be implemented as a pass inserted before the inliner runs. Note that if the user throws this flag, and the assumption is not true, the resulting program will behave badly in unpredictable ways.

(In reply to comment #0) > The idea is to examine the whole program's class hierarchies to determine which > classes can be made final. Final classes can then benefit from non-virtual > dispatch of its virtual functions, and even inline them. Good. (But this can't solve the other problem listed by Manu and C# designers of virtual calls. It's not just a matter of performance). Beside finding what class/method can be final, whole program's class analysis can find what call points of _virtual functions_ always call the same method, so it can turn those virtual calls into non-virtual calls. Whole program's call analysis can also find what points call two different virtual methods. In such points the compiler can use a faster tiny (2-slots wide) inline cache and avoid the virtual call. Monomorphic and 2-polimorphic virtual call points cover a large percentage of all virtual call points (3-polimorphic and megamorphic call points are comparatively). So doing this you remove a significant percentage of all virtual calls. > Hence, to work, this would have to add a flag to the compiler, such as > -wholeprogram, that causes the compiler to make the assumption that all classes > defined in files supplied to the compiler on the command line (not imports) are > never derived from from other object files or DLLs. I suggest to avoid the "one trick pony" syndrome: "whole program" analysis is useful for some other purposes too (like executable libraries: http://rosettacode.org/wiki/Executable_library a pattern currently not supported in D. Or to support Link-time-optimization, etc), so perhaps it's a good idea to give a little stronger meaning to "-wholeprogram", so it's useful for more than just OO de-virtualization. > This could be implemented as a pass inserted before the inliner runs. > > Note that if the user throws this flag, and the assumption is not true, the > resulting program will behave badly in unpredictable ways. Is it possible to enforce/verify the condition and avoid such undefined situations?

Can we have rdmd specify this flag by default, since it is passing all included files to the compiler?

(In reply to comment #2) > Can we have rdmd specify this flag by default, since it is passing all included > files to the compiler? A whole-program class hierarchy analysis is probably fast, but a complete virtual methods analysis could take a bit of time, so if you want a fast compilation you should be able to tall rdmd to not perform it.

(In reply to comment #2) > Can we have rdmd specify this flag by default, since it is passing all included > files to the compiler? No, because it breaks all applications that use plugins to extend the class hierarchy. It must be a well-informed decision.

With the current state of D shared libraries, how many of those do we have anyway? If a change improves performance for 99% of code and breaks 1%, I think that's a worthwhile change. We have a precedent (the -allinst switch and related changes).

(In reply to comment #5) > With the current state of D shared libraries, how many of those do we have > anyway? Close to none I guess. > If a change improves performance for 99% of code and breaks 1%, I think that's > a worthwhile change. The argument being? The state of shared libraries will continue to improve steadily as it did in the past. -wholeprogram (as described above) will cause issues once D gets there and the 1% deliberate silent breakage increases. At the minimum there would have to be a runtime error on loading plugins into a program compiled with -wholeprogram. And to pick up a suggestion on the forum by Ola, there could be a mechanism in place to tell the compiler which classes you need excluded from devirtualization, so you can use -wholeprogram together with plugins. > We have a precedent (the -allinst switch and related > changes). I didn't follow the discussion around -allinst so I cannot comment on that.

A related or duplicate isssue: issue 921

THIS ISSUE HAS BEEN MOVED TO GITHUB https://github.com/dlang/dmd/issues/18799 DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB