[Dominators] PR42041: Skip nullpointer successors

[Szelethus]

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.

[NoQ]

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

[MaskRay]

llvm/include/llvm/Support/GenericDomTreeConstruction.h

242 ↗

(On Diff #201600)

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.

[Szelethus]

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]

llvm/include/llvm/Support/GenericDomTreeConstruction.h

242 ↗

(On Diff #201600)

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

[kuhar]

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]

"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!

[kuhar]

clang/include/clang/Analysis/Analyses/Dominators.h

190

Shouldn't one of the cases use inverse_children?

[Szelethus]

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

[kuhar]

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.

[Szelethus]

Drastically improve the readability of the test files.

clang/include/clang/Analysis/Analyses/Dominators.h

public:
   }
 
 private:
   CFG *cfg;
 };
 
 } // namespace clang
 
+namespace llvm {
+
+/// Clang's CFG contains nullpointers for unreachable succesors, e.g. when an
+/// if statement's condition is always false, it's 'then' branch is represented
+/// with a nullptr. This however will result in a nullpointer derefernece for
+/// dominator tree calculation.
+///
+/// To circumvent this, let's just crudely specialize the children getters
+/// used in LLVM's dominator tree builder.
+namespace DomTreeBuilder {
+
+using ClangCFGDomChildrenGetter =
+SemiNCAInfo<DomTreeBase<clang::CFGBlock>>::ChildrenGetter</*Reverse=*/false>;
+
+using ClangCFGDomReverseChildrenGetter =
+SemiNCAInfo<DomTreeBase<clang::CFGBlock>>::ChildrenGetter</*Reverse=*/true>;
+
+template <>
+template <>
+ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get(
+    clang::CFGBlock *N, std::integral_constant<bool, false>) {
+  auto RChildren = reverse(children<NodePtr>(N));
+  ResultTy Ret(RChildren.begin(), RChildren.end());
+  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
+  return Ret;
+}
+
+template <>
+template <>
+ClangCFGDomReverseChildrenGetter::ResultTy
+ClangCFGDomReverseChildrenGetter::Get(
+    clang::CFGBlock *N, std::integral_constant<bool, false>) {
+  auto RChildren = reverse(children<NodePtr>(N));
+  ResultTy Ret(RChildren.begin(), RChildren.end());
+  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
+  return Ret;
+}
+
+} // end of namespace DomTreeBuilder
+
 //===-------------------------------------
 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 /// iterable by generic graph iterators.
 ///
-namespace llvm {
-
-template <> struct GraphTraits< ::clang::DomTreeNode* > {
+template <> struct GraphTraits<clang::DomTreeNode *> {
   using NodeRef = ::clang::DomTreeNode *;
   using ChildIteratorType = ::clang::DomTreeNode::iterator;
 
   static NodeRef getEntryNode(NodeRef N) { return N; }
   static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->end(); }
 
   using nodes_iterator =

clang/test/Analysis/domtest.cpp

+// RUN: %clang_analyze_cc1 %s \
+// RUN:   -analyzer-checker=debug.DumpCFG \
+// RUN:   -analyzer-checker=debug.DumpDominators \
+// RUN:   2>&1 | FileCheck %s
+
+namespace pr42041_unreachable_cfg_successor {
+enum Kind {
+  A
+};
+
+void f() {
+  switch(Kind{}) {
+  case A:
+    break;
+  }
+}
+} // end of namespace pr42041_unreachable_cfg_successor
+
+// CHECK:      void f()
+// CHECK-NEXT:  [B3 (ENTRY)]
+// CHECK-NEXT:    Succs (1): B1
+//
+// CHECK:       [B1]
+// CHECK-NEXT:    1: {}
+// CHECK-NEXT:    2: pr42041_unreachable_cfg_successor::Kind[B1.1]
+// CHECK-SAME:                    (CXXFunctionalCastExpr, NoOp,
+// CHECK-SAME:                     enum pr42041_unreachable_cfg_successor::Kind)
+// CHECK-NEXT:    3: [B1.2] (ImplicitCastExpr, IntegralCast, int)
+// CHECK-NEXT:    T: switch [B1.3]
+// CHECK-NEXT:    Preds (1): B3
+// CHECK-NEXT:    Succs (2): B2 B0(Unreachable)
+//
+// CHECK:       [B2]
+// CHECK-NEXT:   case A:
+// CHECK-NEXT:    T: break;
+// CHECK-NEXT:    Preds (1): B1
+// CHECK-NEXT:    Succs (1): B0
+//
+// CHECK:       [B0 (EXIT)]
+// CHECK-NEXT:    Preds (2): B2 B1(Unreachable)
+//
+// CHECK:      Immediate dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,2)
+// CHECK-NEXT: (1,3)
+// CHECK-NEXT: (2,1)
+// CHECK-NEXT: (3,3)