This is an archive of the discontinued LLVM Phabricator instance.

[Dominators] Make IsPostDominator a template parameter
ClosedPublic

Authored by kuhar on Jul 12 2017, 10:59 AM.

Details

Summary

DominatorTreeBase used to have IsPostDominators (bool) member to indicate if the tree is a dominator or a postdominator tree. This made it possible to switch between the two 'modes' at runtime, but it isn't used in practice anywhere.

This patch makes IsPostDominator a template argument. This way, it is easier to switch between different algorithms at compile-time based on this argument and design external utilities around it. It also makes it impossible to incidentally assign a postdominator tree to a dominator tree (and vice versa), and to further simplify template code in GenericDominatorTreeConstruction.

Diff Detail

Repository
rL LLVM

Event Timeline

kuhar created this revision.Jul 12 2017, 10:59 AM

(I formatted the patch with ToT clang-format-diff)

dberlin edited edge metadata.Jul 13 2017, 10:29 AM

For the cases that are always true, can you just use PostDominatorTree instead?

IE why is it:

PDT.reset(new DominatorTreeBase<BasicBlock, true>());

Instead of PDT.reset(new PostDominatorTree());

For the cases that are always true, can you just use PostDominatorTree instead?

From what I understand, PostDominatorTree lives in lib/Analysis and I'm not sure if I can include it everywhere.

How about we add something like:

template <typename T> using ForwardDomTreeBase = DominatorTreeBase<T, false>;
template <typename T> using PostDomTreeBase = DominatorTreeBase<T, true>;

at the bottom of GenericDominatorTree.h and use it instead of DominatorTreeBase<T, true/false>?

grosser edited edge metadata.Jul 13 2017, 11:35 PM

For the cases that are always true, can you just use PostDominatorTree instead?

From what I understand, PostDominatorTree lives in lib/Analysis and I'm not sure if I can include it everywhere.

How about we add something like:

template <typename T> using ForwardDomTreeBase = DominatorTreeBase<T, false>;
template <typename T> using PostDomTreeBase = DominatorTreeBase<T, true>;

at the bottom of GenericDominatorTree.h and use it instead of DominatorTreeBase<T, true/false>?

I like this suggestion!

For the cases that are always true, can you just use PostDominatorTree instead?

From what I understand, PostDominatorTree lives in lib/Analysis and I'm not sure if I can include it everywhere.

How about we add something like:

template <typename T> using ForwardDomTreeBase = DominatorTreeBase<T, false>;
template <typename T> using PostDomTreeBase = DominatorTreeBase<T, true>;

at the bottom of GenericDominatorTree.h and use it instead of DominatorTreeBase<T, true/false>?

This sounds like a much better idea than a random true/false parameter that has to be documented everywhere :)

I'd probably just call it DomTreeBase and PostDomTreeBase
while correct, I don't think anywhere in our code base refers to forward dominators as anything but dominators :)

dberlin accepted this revision.Jul 14 2017, 12:16 AM

(and feel free to commit once you've update it for all that)

This revision is now accepted and ready to land.Jul 14 2017, 12:16 AM
kuhar updated this revision to Diff 106674.Jul 14 2017, 11:14 AM

Add DomTreeBase and PostDomTreeBase aliases.

This revision was automatically updated to reflect the committed changes.

Ping! There is branching soon..

kuhar added a comment.Jul 16 2017, 6:16 AM

Investigating

kuhar added a comment.Jul 16 2017, 8:18 AM

I cannot reproduce this failure on my machine. Could someone be able to point me to a build script that makes x86_64 hit the problem?

I would guess that the problem has something to do with explicit template instantiation in MachineDominators.cpp and DominanaceFrontier.cpp. The only difference between these two files and Dominators.cpp, which was edited the same way, is that explicit instantiations are put inside the llvm namespace.
Here's a patch that puts them in global scope: https://reviews.llvm.org/D35461

Please do let me know if applying the patch fixes the failure.

This should be fixed by r308140.

Don Hinton discovered that the problem was the defaulted constructor of DominatorTreeBase -- some compilers (like gcc 5.4.1 and the gcc used in the NetBSD buildbot) don't handle this case when a class template gets explicitly instantiated.
It also managed to crash clang-3.8 here: http://lab.llvm.org:8011/builders/clang-x86_64-linux-selfhost-modules/builds/7503 .

I will try to look into that in more detail on Monday.

@kuhar, you just triggered the build failure with -fmodules. See also; https://bugs.llvm.org/show_bug.cgi?id=33810