www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 12440] New: Implement whole-program analysis

reply d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12440

           Summary: Implement whole-program analysis
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: bugzilla digitalmars.com


--- Comment #0 from Walter Bright <bugzilla digitalmars.com> 2014-03-22
13:01:28 PDT ---
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.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 22 2014
next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12440


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs eml.cc


--- Comment #1 from bearophile_hugs eml.cc 2014-03-22 13:20:36 PDT ---
(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? -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Mar 22 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12440


Vladimir Panteleev <thecybershadow gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |thecybershadow gmail.com


--- Comment #2 from Vladimir Panteleev <thecybershadow gmail.com> 2014-03-23
10:28:55 EET ---
Can we have rdmd specify this flag by default, since it is passing all included
files to the compiler?

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 23 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12440



--- Comment #3 from bearophile_hugs eml.cc 2014-03-23 02:22:51 PDT ---
(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. -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Mar 23 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12440


Marco Leise <Marco.Leise gmx.de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |Marco.Leise gmx.de


--- Comment #4 from Marco Leise <Marco.Leise gmx.de> 2014-03-23 02:25:35 PDT ---
(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. -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Mar 23 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12440



--- Comment #5 from Vladimir Panteleev <thecybershadow gmail.com> 2014-03-23
11:28:43 EET ---
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).

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 23 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12440



--- Comment #6 from Marco Leise <Marco.Leise gmx.de> 2014-03-23 02:48:39 PDT ---
(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. -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Mar 23 2014
prev sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12440



--- Comment #7 from Vladimir Panteleev <thecybershadow gmail.com> 2014-03-25
11:13:57 EET ---
A related or duplicate isssue: issue 921

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 25 2014