Differential D62507
[Dominators] PR42041: Skip nullpointer successors Authored by Szelethus on May 27 2019, 5:31 PM.
Details https://bugs.llvm.org/show_bug.cgi?id=42041 In Clang's CFG, we use nullpointers to represent unreachable nodes, for This patch fixes this issue by specializing
Diff Detail
Event TimelineComment Actions @Szelethus, could you double-check that there's no way to tweak some graph traits (or something like that) in order to filter out null-successors specifically for Clang CFG? I don't immediately see a way to do that, but i might have missed something. Given that ChildrenGetter<Direction>::Get returns a SmallVector, it shouldn't be that impossible. Otherwise i hope an extra defensive check wouldn't hurt.
Comment Actions Yup, diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h index c64d2030c6f..14349dbd5b5 100644 --- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -111,12 +111,16 @@ struct SemiNCAInfo { static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) { auto RChildren = reverse(children<NodePtr>(N)); - return ResultTy(RChildren.begin(), RChildren.end()); + ResultTy Ret(RChildren.begin(), RChildren.end()); + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + return Ret; } static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) { auto IChildren = inverse_children<NodePtr>(N); - return ResultTy(IChildren.begin(), IChildren.end()); + ResultTy Ret(IChildren.begin(), IChildren.end()); + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + return Ret; } using Tag = std::integral_constant<bool, Inverse>; works perfectly, I'll just need to hide it in a template somehow.
Comment Actions Like I mentioned in another thread, I really dislike this approach. The single source of truth about graph traversal in dominators is the ChildGetter structure that internally uses children and inverse_children, and expects them to only return pointers to actual successors/predecessors. It's very weird that children and inverse_children return nullptrs -- they are not valid graph nodes, and I don't see why this would be desired, despite how unreachable regions are represented in the CFG. Would it be possible to change some graph traits responsible for children and inverse_children instead? Or as an alternative, let clang CFG specialize ChildGetter? Right now I'm marking this revision with 'request changes', until we explore alternative approaches. Comment Actions
Revert all changes to the dominator tree builder in LLVM, specialize ChildrenGetter::Get for clang's CFG. I'll try to explore nicer solutions, but this is clearly superior to my previous diff. Thank you all so much for the reviews!
Comment Actions Correctly use reverse(children<NodePtr>(N)) and inverse_children<NodePtr>(N), based on the original code: template <bool Inverse> struct ChildrenGetter { using ResultTy = SmallVector<NodePtr, 8>; static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) { auto RChildren = reverse(children<NodePtr>(N)); return ResultTy(RChildren.begin(), RChildren.end()); } static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) { auto IChildren = inverse_children<NodePtr>(N); return ResultTy(IChildren.begin(), IChildren.end()); } using Tag = std::integral_constant<bool, Inverse>; // etc etc... Comment Actions Thanks, I think this is a much better solution than directly hacking on DomTreeBuilder. Note that every time you ask DomTree about a nullptr CFG node, it understands it as a request for a virtual root. While now this should crash on forward dominators, you will get an actual tree node for a nullptr in postdominators. In the future, it may happen that forward dominators will also have a virtual root (for more efficient updates) and the users of clang CFG and dominators should be aware that not every CFG node (i.e., an unreachable successor) has a corresponding DomTreeNode. | ||||||||||||||||||