Bug 15318 – Templates not emitted for two "partial cycles"

Consider the following program: --- module A; import C; --- module B; import E; alias value = bar!5; void foo() { import core.stdc.stdio; printf("%p\n", &value); } --- module C; import E; alias value = bar!5; void foo() { import core.stdc.stdio; printf("%p\n", &value); } --- module D; import B; --- module E; immutable bar(int v) = v; --- If you compile it like this using DMD 2.068.2 or 2.069.1 --- dmd -c -offirst.o A.d B.d dmd -c -ofsecond.o C.d D.d dmd -main E.d first.o second.o --- you'll get an undefined symbol for the bar!5 instance. The same occurs when using -lib instead of "-c -of…", and E.d is of course unnecessary to compile in this case, but just added for completeness. The issue is that when compiling the first "package" (this test case is derived from problems using by-package compilation in a big code base), i.e. A and B, the symbol is determined to be instantiated by a non-root module (A -> C), so even though it is instantiated in B, it doesn't get emitted into the object file. But when compiling the second package, the D -> B import causes that instance in C not to be emitted either. One fix/workaround is to remove the following piece of logic from TemplateInstance.needsCodegen(): --- dtemplate.d if (tnext && !tnext.needsCodegen() && tnext.minst) { minst = tnext.minst; // cache result assert(!minst.isRoot()); return false; } --- Now, of course, this fix is not ideal in the sense that it also causes more work to be done in cases that are currently handled correctly. But fundamentally I can't see how eliding instances that are being done directly in root modules (B and C in this case) would ever be possible. There can always be parts of the global module dependency graph for a whole executable that are not visible from the local point of view when compiling a subset of the modules. For instance, in the above example there is no way the compiler can know about the existence of D when compiling A and B. Marked as a regression, as the issue didn't occur using 2.067.1 in said large real-world code base, but my suspicion is that the template instantiation logic was broken before too.

This seems to be a case where the second rule of this issue 14431 fix doesn't work. http://forum.dlang.org/post/[email protected] > If a template is instantiated in non-root module, compiler usually does not have to put it in object file. But if a template is instantiated in both of root and non-root modules which mutually import each other, it needs to placed in objfile. === In both of the compilations there is a root and a non-root module instantiating bar!5. Now unfortunately the compiler decides both times that the non-root module should do it. This problem would be solved by my proposal to define a global order for who is responsible to instantiate a template, by choosing the module with the lexicographically smaller module name. https://github.com/D-Programming-Language/dmd/pull/4384#discussion_r29910422 https://issues.dlang.org/show_bug.cgi?id=14431#c12 This would establish a stable order between B and C, and no matter how you compile them, B gets to instantiate the template. === An intermediate workaround for your problem is to use the -allinst switch, even though it slows down compilation a lot. You can also compile each module separately in which case both B and C get the instance (in general this is even slower than -allinst).

(In reply to Martin Nowak from comment #1) > In both of the compilations there is a root and a non-root module > instantiating bar!5. Now unfortunately the compiler decides both times that > the non-root module should do it. That is correct. > This problem would be solved by my proposal to define a global order for who > is responsible to instantiate a template, by choosing the module with the > lexicographically smaller module name. > https://github.com/D-Programming-Language/dmd/pull/4384#discussion_r29910422 > https://issues.dlang.org/show_bug.cgi?id=14431#c12 > > This would establish a stable order between B and C, and no matter how you > compile them, B gets to instantiate the template. At first glance, it seems as if this should work. However, I would need to think about it in more detail to be sure that the approach doesn't implicitly introduce any new edges in the module dependency graph that would break incremental compilation. > An intermediate workaround for your problem is to use the -allinst switch […] I'd say a much better workaround would be to just remove the clearly faulty "optimization" from DMD until we have a solid strategy to replace it with. In fact, Weka is currently using a lightweight fork of upstream LDC with the code mentioned in the original report patched out, and it has resolved all the related issues.

It can also be resolved by noting that C is not imported (directly or indirectly) by B, and so C's instantiation will not count as an imported instantiation when instantianting templates in B.

I don't think that the issue case is a bug in the current instantiation strategy. The codegen omission for non-root instances is designed for the compiling applications which is using big template style libraries. On the other hand, in the issue case, the non-root instance bar!5 is a part of the build target, so no libraries can supply the missing symbol. I think it could be resolved at compiler tool side. If a module is imported, all of template instances in it could be handled either: A. as non-root instances, because the module is a part of library. B. as speculative instances, because the module is a part of build target. But currently, all of import directories are in a ordered flat list. So, compiler cannot distinguish the two cases - today all of cases are treated as case A. My proposal is, adding a boundary between "build target" and "library". By that, we can have a new behavior for the modules for the build target. How to define the boundary? There's some ways I can think. - Use the 'package' difference. For example: If none of root modules belong to 'std' package, then all of modules belongs 'std' can be handled as library modules. - Use the found import directory. For example: The default import directly '.' can be handled as for the build-target always. - Use a new switch for the importing build-target modules. For example: dmd -buildTarget_I=... If compiler finds a module from that directory, the module will be handled as build target module. The approach would also fit to modern package system.

I very much prefer (In reply to Walter Bright from comment #3) > It can also be resolved by noting that C is not imported (directly or > indirectly) by B, and so C's instantiation will not count as an imported > instantiation when instantianting templates in B. Yep, this is indeed an option here. We'd still end up emitting the template twice in this example, though, which is what I alluded to regarding not being able to elide the instance. (In reply to Kenji Hara from comment #4) > I don't think that the issue case is a bug in the current instantiation > strategy. I can't really see how you can come to this conclusion. If it's not a regression, then where is the documentation that states that DMD is not to be invoked in this fashion? Like Martin and Andrei, I'd suggest taking a step back and thinking about what the template instantiation strategy is really meant to achieve first. I don't think piling up more and more special cases is going to be helpful, especially because it just pushes this complexity to the user.

> (In reply to Kenji Hara from comment #4) > > I don't think that the issue case is a bug in the current instantiation > > strategy. > > I can't really see how you can come to this conclusion. If it's not a > regression, then where is the documentation that states that DMD is not to > be invoked in this fashion? OK, I recognized true issue you reported. I had misunderstood.

It appears this was fixed for the OP testcase in DMD 2.072. Measurement points: 2.069.2 BROKEN 2.070.2 BROKEN 2.071.2 BROKEN 2.072.2 WORKS! 2.073.2 WORKS!

(In reply to Johan Engelen from comment #7) > It appears this was fixed for the OP testcase in DMD 2.072. Fixed in https://github.com/dlang/dmd/pull/5690 *** This issue has been marked as a duplicate of issue 13242 ***

(In reply to Johan Engelen from comment #7) > It appears this was fixed for the OP testcase in DMD 2.072. Let's hope it is actually fixed, rather than just not occurring anymore in the test case. ;)