Implement whole-program analysis

[dlangBugzillaToGithub]

Walter Bright (@WalterBright) reported this on 2014-03-22T13:01:28Z

Transferred from https://issues.dlang.org/show_bug.cgi?id=12440

CC List

• Vladimir Panteleev (@CyberShadow)
• Marco Leise

Description

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.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-03-22T13:20:36Z

(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?

[dlangBugzillaToGithub]

dlang-bugzilla (@CyberShadow) commented on 2014-03-23T01:28:55Z

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

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-03-23T02:22:51Z

(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.

[dlangBugzillaToGithub]

Marco.Leise commented on 2014-03-23T02:25:35Z

(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.

[dlangBugzillaToGithub]

dlang-bugzilla (@CyberShadow) commented on 2014-03-23T02:28:43Z

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).

[dlangBugzillaToGithub]

Marco.Leise commented on 2014-03-23T02:48:39Z

(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.

[dlangBugzillaToGithub]

dlang-bugzilla (@CyberShadow) commented on 2014-03-25T02:13:57Z

A related or duplicate isssue: issue 921