[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

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

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 ↗

(On Diff #201676)

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/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)

llvm/include/llvm/Support/GenericDomTreeConstruction.h

while (!WorkList.empty()) {
       if (BBInfo.DFSNum != 0) continue;
       BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
       BBInfo.Label = BB;
       NumToNode.push_back(BB);
 
       constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
       for (const NodePtr Succ :
            ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
+
+        // The clang's CFG contains nullpointers for unreachable successors (eg.
+        // an if statement's condition is always false, the 'then' branch is
+        // unreachable), skip them.
+        if (!Succ)
+          continue;
+
         const auto SIT = NodeToInfo.find(Succ);
         // Don't visit nodes more than once but remember to collect
         // ReverseChildren.
         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
           continue;
         }