Incremental compilation with DMD

[Tom S]

Short story: DMD probably needs an option to output template instances 
to all object files that need them.

Long story:

I've been trying to make incremental compilation in xfBuild reliable, 
but it turns out that it's really tricky with DMD. Consider the 
following example:

* module A instantiates template T from module C
* module B instantiates the same template T from module C (with the same 
arguments)
* compile all modules at the same time in the order: A, B, C
* now A.obj contains the instantiation of T
* remove the instantiation from the A module
* perform an incremental compilation - 'A' was changed, so only it has 
to be recompiled
* linking of A.obj, B.obj and C.obj fails because no module has the 
instantiation of T for B.obj

What happens is that the optimization in DMD to only emit templates to 
the first module that needs it creates implicit inter-module 
dependencies. I've tried tracking them by modifying DMD, but still 
wouldn't find them all - it seems that one would have to dig deep in the 
codegen, my attempts at hacking the frontend (mostly template.c) weren't 
enough.

Yet, I still managed to get some of these implicit dependencies figured 
and attempted using this extra info in xfBuild when deciding what to 
compile incrementally. I've tossed it on a project of mine with > 350 
modules and no circular imports. The result was that even a trivial 
change caused most of the project to be pulled into compilation.

When doing regular incremental compilation, all modules that import the 
modified ones must be recompiled as well. And all modules that import 
these, and so on, up to the root of the project. This is because the 
incremental build tool must assume that the modules that import module 
'A' could have code of the form 'static if (A.something) { ... } else { 
... }' or another form of it. As far as I know, it's not trivial to 
detect whether this is really the case or whether the change is isolated 
to 'A'.

When trying to cope with the implicit dependencies caused by template 
instantiations and references, one also has to recompile all modules 
that contain template references to a module/object file which gets the 
instance. In the first example, it would mean recompiling module 'B' 
whenever 'A' changes. The graph of dependencies here doesn't depend very 
much on the structure of imports in a project, but rather in the order 
that DMD decides to run semantic() on template instances.

Add up these two conservative mechanisms and it turns out that tweaking 
a simple function causes half of your project to be rebuilt. This is not 
acceptable. Even if it was feasible - getting these implicit 
dependencies is probably a matter of either hacking the backend or 
dumping object files and matching unresolved symbols with comdats. 
Neither would be very fast or portable.

Compiling modules one-at-a-time is not a solution because it's too slow.

Thus my suggestion of adding an option to DMD so it may emit template 
instances to all object files that use them. If anyone has alternative 
ideas, I'd be glad to hear them, because I'm running out of options. The 
approach I'm currently using in an experimental version of xfBuild is:

* get a fixed order of modules to be compiled determined by the order 
DMD calls semantic() on them with the root modules at the end
* when a module is modified, additionally recompile all modules that 
occur after it in the list

This quite obviously ends up compiling way too many modules, but seems 
to work reliably (except when OPTLINK decides to crash) without 
requiring full rebuilds all the time. Still, I fear there might be 
corner cases where it will fail as well. DMD sometimes places 
initializers in weird places, e.g.:

.objs\xf-nucleus-model-ILinkedKernel.obj(xf-nucleus-model-ILinkedKernel)
  Error 42: Symbol Undefined 
_D61TypeInfo_S2xf7nucleus9particles13BasicParticle13BasicParticle6__initZ

The two modules (xf.nucleus.model.ILinkedKernel and 
xf.nucleus.particles.BasicParticle) are unrelated. This error occured 
once, somewhere deep into an automated attempt to break the experimental 
xfBuild by touching random modules and performing incremental builds.


-- 
Tomasz Stachowiak
http://h3.team0xf.com/
h3/h3r3tic on #D freenode