Have Linker sort and validate static ctors/dtors

[schveiguy]

Description

Currently, when building code with static ctors/dtors, the compiler sticks all module infos into a common section, which the linker then concatenates together. The runtime then fetches those pieces out, and builds a graph of modules. During runtime, the modules are sorted in order of dependency, and any cycles are detected. Then if no cycles are detected, the ctors are run in the sorted order.

This information cannot be determined at compile-time, because D uses a separate compilation model. The compiler might not know which module dependencies are relevant when compiling any other modules. The end result is that every time you run the program, this sorting and cycle detection must happen, even though the result is always knowable based on the built executable.

At link time, the linker is building the entire section, and has access to all the information. Certain compilers, such as LDC, have "Link Time Optimization", which calls back into the compiler to perform optimizations after knowing all the possible code that is about to be generated.

A possible idea occurred to me that if we can hook into this mechanism, we may be able to run the sorting and cycle detection at link time, and let the runtime just execute the sorted modules in the order they appear.

I am very unsure of what capabilities are available for LTO, and whether they can be used for this purpose, so I'm not sure if this is a viable project.

What are rough milestones of this project?

1. Determine feasibility of using LTO to process/reorder the modules.
2. Implement the module using the LTO interface
3. Remove sorting of ctors/dtors from druntime

How does this project help the D community?

Currently, any application that is built must run the static constructor sorting every time the program is started. If there are cycles detected, it's not possible to even run the program correctly. Providing a nicer error during compile time would be ideal.

Recommended skills

Linkers, LTO, understanding ABI/binary data.

Point of Contact

@schveiguy (for ctor sorting and initialization algorithm support). Need a good contact for LTO.

References

Code that sorts the constructors and detects cycles: https://github.com/dlang/dmd/blob/master/druntime/src/rt/minfo.d