Page MenuHomePhabricator

[Dominators] PR42041: Skip nullpointer successors
ClosedPublic

Authored by Szelethus on May 27 2019, 5:31 PM.

Details

Summary

https://bugs.llvm.org/show_bug.cgi?id=42041

In Clang's CFG, we use nullpointers to represent unreachable nodes, for
example, in the included testfile, block B0 is unreachable from block
B1, resulting in a nullpointer dereference somewhere in
llvm::DominatorTreeBase<clang::CFGBlock, false>::recalculate.

This patch fixes this issue by specializing
llvm::DomTreeBuilder::SemiNCAInfo::ChildrenGetter::Get for
clang::CFG to not contain nullpointer successors.

Diff Detail

Event Timeline

Szelethus created this revision.May 27 2019, 5:31 PM
NoQ accepted this revision.May 27 2019, 8:39 PM

@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.

This revision is now accepted and ready to land.May 27 2019, 8:39 PM
MaskRay added inline comments.May 27 2019, 10:16 PM
llvm/include/llvm/Support/GenericDomTreeConstruction.h
242

I hope we can find an approach that doesn't need the defensive check here. In post dominator tree nullptr represents the virtual root, this check will cause some confusion. I also don't know if a simple check here is sufficient, I guess somewhere else might need similar checks.

In D62507#1518692, @NoQ wrote:

@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.

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.

Szelethus planned changes to this revision.May 28 2019, 6:14 AM
Szelethus marked an inline comment as done.
Szelethus added inline comments.
llvm/include/llvm/Support/GenericDomTreeConstruction.h
242

Yup, this isn't a good approach then. Thanks!

kuhar requested changes to this revision.May 28 2019, 8:09 AM

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.

Szelethus updated this revision to Diff 201676.EditedMay 28 2019, 8:20 AM

"What's the difference between a template programmer and a monkey? A monkey uses tools."
/Zoltán Porkoláb/

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!

Szelethus edited the summary of this revision. (Show Details)May 28 2019, 8:23 AM
Szelethus set the repository for this revision to rC Clang.
kuhar added inline comments.May 28 2019, 8:24 AM
clang/include/clang/Analysis/Analyses/Dominators.h
190 ↗(On Diff #201676)

Shouldn't one of the cases use inverse_children?

Szelethus updated this revision to Diff 201679.May 28 2019, 8:32 AM

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...
Szelethus marked an inline comment as done.May 28 2019, 8:33 AM
kuhar accepted this revision.May 28 2019, 8:39 AM

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.

This revision is now accepted and ready to land.May 28 2019, 8:39 AM
MaskRay accepted this revision.May 28 2019, 8:48 AM

Drastically improve the readability of the test files.

This revision was automatically updated to reflect the committed changes.