Index: clang/include/clang/Analysis/Analyses/Dominators.h =================================================================== --- clang/include/clang/Analysis/Analyses/Dominators.h +++ clang/include/clang/Analysis/Analyses/Dominators.h @@ -155,13 +155,51 @@ } // 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>::ChildrenGetter; + +template <> +template <> +ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get( + clang::CFGBlock *N, std::integral_constant) { + auto RChildren = reverse(children(N)); + ResultTy Ret(RChildren.begin(), RChildren.end()); + Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + return Ret; +} + +using ClangCFGDomReverseChildrenGetter = +SemiNCAInfo>::ChildrenGetter; + +template <> +template <> +ClangCFGDomReverseChildrenGetter::ResultTy +ClangCFGDomReverseChildrenGetter::Get( + clang::CFGBlock *N, std::integral_constant) { + auto IChildren = inverse_children(N); + ResultTy Ret(IChildren.begin(), IChildren.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 { using NodeRef = ::clang::DomTreeNode *; using ChildIteratorType = ::clang::DomTreeNode::iterator; Index: clang/test/Analysis/domtest.c =================================================================== --- clang/test/Analysis/domtest.c +++ clang/test/Analysis/domtest.c @@ -1,6 +1,6 @@ -// RUN: rm -f %t -// RUN: %clang_analyze_cc1 -analyzer-checker=debug.DumpDominators %s > %t 2>&1 -// RUN: FileCheck --input-file=%t %s +// RUN: %clang_analyze_cc1 %s \ +// RUN: -analyzer-checker=debug.DumpDominators \ +// RUN: 2>&1 | FileCheck %s // Test the DominatorsTree implementation with various control flows int test1() @@ -24,17 +24,24 @@ return 0; } -// CHECK: Immediate dominance tree (Node#,IDom#): -// CHECK: (0,1) -// CHECK: (1,7) -// CHECK: (2,3) -// CHECK: (3,6) -// CHECK: (4,6) -// CHECK: (5,6) -// CHECK: (6,7) -// CHECK: (7,8) -// CHECK: (8,9) -// CHECK: (9,9) +// [B9 (ENTRY)] -> [B8] -> [B7] -> [B6] -> [B5] -> [B3] -> [B2] +// |\ \ / / +// | \ ---> [B4] ---> / +// | <--------------------------- +// V +// [B1] -> [B0 (EXIT)] + +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,1) +// CHECK-NEXT: (1,7) +// CHECK-NEXT: (2,3) +// CHECK-NEXT: (3,6) +// CHECK-NEXT: (4,6) +// CHECK-NEXT: (5,6) +// CHECK-NEXT: (6,7) +// CHECK-NEXT: (7,8) +// CHECK-NEXT: (8,9) +// CHECK-NEXT: (9,9) int test2() { @@ -54,15 +61,22 @@ return 0; } -// CHECK: Immediate dominance tree (Node#,IDom#): -// CHECK: (0,1) -// CHECK: (1,6) -// CHECK: (2,3) -// CHECK: (3,4) -// CHECK: (4,6) -// CHECK: (5,6) -// CHECK: (6,7) -// CHECK: (7,7) +// <------------- +// / \ +// -----------> [B4] -> [B3] -> [B2] +// / | +// / V +// [B7 (ENTRY)] -> [B6] -> [B5] -> [B1] -> [B0 (EXIT)] + +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,1) +// CHECK-NEXT: (1,6) +// CHECK-NEXT: (2,3) +// CHECK-NEXT: (3,4) +// CHECK-NEXT: (4,6) +// CHECK-NEXT: (5,6) +// CHECK-NEXT: (6,7) +// CHECK-NEXT: (7,7) int test3() { @@ -82,16 +96,26 @@ return 0; } -// CHECK: Immediate dominance tree (Node#,IDom#): -// CHECK: (0,1) -// CHECK: (1,7) -// CHECK: (2,5) -// CHECK: (3,4) -// CHECK: (4,5) -// CHECK: (5,6) -// CHECK: (6,7) -// CHECK: (7,8) -// CHECK: (8,8) +// <------------- +// / \ +// | ---> [B2] +// | / +// [B8 (ENTRY)] -> [B7] -> [B6] -> [B5] -> [B4] -> [B3] +// \ | \ / +// \ | <------------- +// \ \ +// --------> [B1] -> [B0 (EXIT)] + +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,1) +// CHECK-NEXT: (1,7) +// CHECK-NEXT: (2,5) +// CHECK-NEXT: (3,4) +// CHECK-NEXT: (4,5) +// CHECK-NEXT: (5,6) +// CHECK-NEXT: (6,7) +// CHECK-NEXT: (7,8) +// CHECK-NEXT: (8,8) int test4() { @@ -108,20 +132,33 @@ return 0; } -// CHECK: Immediate dominance tree (Node#,IDom#): -// CHECK: (0,1) -// CHECK: (1,10) -// CHECK: (2,9) -// CHECK: (3,4) -// CHECK: (4,5) -// CHECK: (5,9) -// CHECK: (6,7) -// CHECK: (7,8) -// CHECK: (8,9) -// CHECK: (9,10) -// CHECK: (10,11) -// CHECK: (11,12) -// CHECK: (12,12) +// <---------------------------------- +// / <----------------- \ +// / / \ \ +// [B12 (ENTRY)] -> [B11] -> [B10]-> [B9] -> [B8] ---> [B7] -> [B6] | +// | \ \ / +// | \ -----> [B2] --------/ +// | \ / +// | -> [B5] -> [B4] -> [B3] +// | \ / +// | <------------ +// \ +// -> [B1] -> [B0 (EXIT)] + +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,1) +// CHECK-NEXT: (1,10) +// CHECK-NEXT: (2,9) +// CHECK-NEXT: (3,4) +// CHECK-NEXT: (4,5) +// CHECK-NEXT: (5,9) +// CHECK-NEXT: (6,7) +// CHECK-NEXT: (7,8) +// CHECK-NEXT: (8,9) +// CHECK-NEXT: (9,10) +// CHECK-NEXT: (10,11) +// CHECK-NEXT: (11,12) +// CHECK-NEXT: (12,12) int test5() { @@ -151,18 +188,25 @@ return 0; } -// CHECK: Immediate dominance tree (Node#,IDom#): -// CHECK: (0,1) -// CHECK: (1,10) -// CHECK: (2,10) -// CHECK: (3,9) -// CHECK: (4,9) -// CHECK: (5,8) -// CHECK: (6,8) -// CHECK: (7,8) -// CHECK: (8,9) -// CHECK: (9,10) -// CHECK: (10,11) -// CHECK: (11,11) - - +// [B0 (EXIT)] <-- +// \ +// [B11 (ENTY)] -> [B10] -> [B9] -> [B8] -> [B7] -> [B5] -> [B3] -> [B1] +// | | | / / / +// | | V / / / +// | V [B6] --> / / +// V [B4] -----------------> / +// [B2]---------------------------------> + +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,1) +// CHECK-NEXT: (1,10) +// CHECK-NEXT: (2,10) +// CHECK-NEXT: (3,9) +// CHECK-NEXT: (4,9) +// CHECK-NEXT: (5,8) +// CHECK-NEXT: (6,8) +// CHECK-NEXT: (7,8) +// CHECK-NEXT: (8,9) +// CHECK-NEXT: (9,10) +// CHECK-NEXT: (10,11) +// CHECK-NEXT: (11,11) Index: clang/test/Analysis/domtest.cpp =================================================================== --- /dev/null +++ clang/test/Analysis/domtest.cpp @@ -0,0 +1,51 @@ +// RUN: %clang_analyze_cc1 %s \ +// RUN: -analyzer-checker=debug.DumpDominators \ +// RUN: 2>&1 | FileCheck %s + +bool coin(); + +namespace pr42041_unreachable_cfg_successor { +enum Kind { + A +}; + +void f() { + switch(Kind{}) { + case A: + break; + } +} +} // end of namespace pr42041_unreachable_cfg_successor + +// [B3 (ENTRY)] -> [B1] -> [B2] -> [B0 (EXIT)] + +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,2) +// CHECK-NEXT: (1,3) +// CHECK-NEXT: (2,1) +// CHECK-NEXT: (3,3) + +void funcWithBranch() { + int x = 0; + if (coin()) { + if (coin()) { + x = 5; + } + int j = 10 / x; + (void)j; + } +} + +// ----> [B2] ----> +// / \ +// [B5 (ENTRY)] -> [B4] -> [B3] -----------> [B1] +// \ / +// ----> [B0 (EXIT)] <---- + +// CHECK: Immediate dominance tree (Node#,IDom#): +// CHECK-NEXT: (0,4) +// CHECK-NEXT: (1,3) +// CHECK-NEXT: (2,3) +// CHECK-NEXT: (3,4) +// CHECK-NEXT: (4,5) +// CHECK-NEXT: (5,5)