[analyzer][Dominator] Add post dominator tree builder for the CFG + a debug checker

[Szelethus]

Summary

Transform clang::DominatorTree to be able to also calculate post dominators.

• Tidy up the documentation
• Make it clang::DominatorTree template class (similarly to how llvm::DominatorTreeBase works), rename it to clang::CFGDominatorTreeImpl
  • Clang's dominator tree is now called clang::CFGDomTree
  • Clang's brand new post dominator tree is called clang::CFGPostDomTree
• Add a lot of asserts to the dump() function
• Create a new checker to test the functionality

[kuhar]

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

39 ↗

(On Diff #201758)

Seems outdated?

47 ↗

(On Diff #201758)

nit: I think this can name can be somewhat confusing as it's not a base class of CFGDomTree.

49 ↗

(On Diff #201758)

Why not have it as a value member? Or a unique_ptr, if pointer semantics are really desired.

111 ↗

(On Diff #201758)

Assertions with multiple conditions conjoined are difficult to debug -- perhaps it'd be better to split them and assign to separate booleans for each condition, with descriptive names? This code can be hidden behind an ifdef for debug.

174 ↗

(On Diff #201758)

nit: How about having the parent class template called CFGDominatorTreeImpl and these two as CFGDomTree and CFGPostdomTree?

[Szelethus]

Fixes according to @kuhar's comments, thanks!

[Szelethus]

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

111 ↗

(On Diff #201758)

Do you like this better? I prefer running static analysis on large codebases with a Release+Asserts build, and I fear that this check will be lost if I use #ifdef DEBUG.

[kuhar]

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

111 ↗

(On Diff #201758)

I think it's much more readable now, thanks! Release+Asserts defines NDEBUG and the assertion will work if you put it into an ifdef.

[kuhar]

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

111 ↗

(On Diff #201758)

*does not define NDEBUG

[NoQ]

Dunno, looks great :)

Also thx @kuhar!

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

194–195 ↗

(On Diff #201769)

Is this the intended formatting?

[Szelethus]

Cascade the test file readability improvement from the previous patch.

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

 class Module;
 
 } // namespace llvm
 
 namespace clang {
 
 using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>;
 
-/// Concrete subclass of DominatorTreeBase for Clang
-/// This class implements the dominators tree functionality given a Clang CFG.
-///
-class DominatorTree : public ManagedAnalysis {
+/// Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase.
+template <bool IsPostDom>
+class CFGDominatorTreeImpl : public ManagedAnalysis {
   virtual void anchor();
 
 public:
-  llvm::DomTreeBase<CFGBlock> *DT;
+  using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>;
 
-  DominatorTree() {
-    DT = new llvm::DomTreeBase<CFGBlock>();
-  }
+  DominatorTreeBase DT;
 
-  ~DominatorTree() override { delete DT; }
+  CFGDominatorTreeImpl() = default;
+  ~CFGDominatorTreeImpl() override = default;
 
-  llvm::DomTreeBase<CFGBlock>& getBase() { return *DT; }
+  DominatorTreeBase& getBase() { return *DT; }
 
-  /// This method returns the root CFGBlock of the dominators tree.
+  /// \returns the root CFGBlock of the dominators tree.
   CFGBlock *getRoot() const {
-    return DT->getRoot();
+    return DT.getRoot();
   }
 
-  /// This method returns the root DomTreeNode, which is the wrapper
-  /// for CFGBlock.
-  DomTreeNode *getRootNode() const {
-    return DT->getRootNode();
+  /// \returns the root DomTreeNode, which is the wrapper for CFGBlock.
+  DomTreeNode *getRootNode() {
+    return DT.getRootNode();
   }
 
-  /// This method compares two dominator trees.
-  /// The method returns false if the other dominator tree matches this
-  /// dominator tree, otherwise returns true.
-  bool compare(DominatorTree &Other) const {
+  /// Compares two dominator trees.
+  /// \returns false if the other dominator tree matches this dominator tree,
+  /// false otherwise.
+  bool compare(CFGDominatorTreeImpl &Other) const {
     DomTreeNode *R = getRootNode();
     DomTreeNode *OtherR = Other.getRootNode();
 
     if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
       return true;
 
-    if (DT->compare(Other.getBase()))
+    if (DT.compare(Other.getBase()))
       return true;
 
     return false;
   }
 
-  /// This method builds the dominator tree for a given CFG
-  /// The CFG information is passed via AnalysisDeclContext
-  void buildDominatorTree(AnalysisDeclContext &AC) {
-    cfg = AC.getCFG();
-    DT->recalculate(*cfg);
+  /// Builds the dominator tree for a given CFG.
+  void buildDominatorTree(CFG *cfg) {
+    assert(cfg);
+    this->cfg = cfg;
+    DT.recalculate(*cfg);
   }
 
-  /// This method dumps immediate dominators for each block,
-  /// mainly used for debug purposes.
+  /// Dumps immediate dominators for each block.
   void dump() {
-    llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
+    llvm::errs() << "Immediate " << (IsPostDom ? "post " : "")
+                 << "dominance tree (Node#,IDom#):\n";
     for (CFG::const_iterator I = cfg->begin(),
         E = cfg->end(); I != E; ++I) {
-      if(DT->getNode(*I)->getIDom())
+
+      assert(*I &&
+             "LLVM's Dominator tree builder uses nullpointers to signify the "
+             "virtual root!");
+
+      DomTreeNode *IDom = DT.getNode(*I)->getIDom();
+      if (IDom && IDom->getBlock())
         llvm::errs() << "(" << (*I)->getBlockID()
                      << ","
-                     << DT->getNode(*I)->getIDom()->getBlock()->getBlockID()
+                     << IDom->getBlock()->getBlockID()
                      << ")\n";
-      else llvm::errs() << "(" << (*I)->getBlockID()
-                        << "," << (*I)->getBlockID() << ")\n";
+      else {
+        bool IsEntryBlock = *I == &(*I)->getParent()->getEntry();
+        bool IsExitBlock = *I == &(*I)->getParent()->getExit();
+
+        bool IsDomTreeRoot = !IDom && !IsPostDom && IsEntryBlock;
+        bool IsPostDomTreeRoot =
+            IDom && !IDom->getBlock() && IsPostDom && IsExitBlock;
+
+        assert((IsDomTreeRoot || IsPostDomTreeRoot) &&
+               "If the immediate dominator node is nullptr, the CFG block "
+               "should be the exit point (since it's the root of the dominator "
+               "tree), or if the CFG block it refers to is a nullpointer, it "
+               "must be the entry block (since it's the root of the post "
+               "dominator tree)");
+
+        (void)IsDomTreeRoot;
+        (void)IsPostDomTreeRoot;
+
+        llvm::errs() << "(" << (*I)->getBlockID()
       }
     }
+  }
 
-  /// This method tests if one CFGBlock dominates the other.
-  /// The method return true if A dominates B, false otherwise.
+  /// Tests whether \p A dominates \p B.
   /// Note a block always dominates itself.
   bool dominates(const CFGBlock *A, const CFGBlock *B) const {
-    return DT->dominates(A, B);
+    return DT.dominates(A, B);
   }
 
-  /// This method tests if one CFGBlock properly dominates the other.
-  /// The method return true if A properly dominates B, false otherwise.
+  /// Tests whether \p A properly dominates \p B.
+  /// \returns false if \p A is the same block as \p B, otherwise whether A
+  /// dominates B.
   bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
-    return DT->properlyDominates(A, B);
+    return DT.properlyDominates(A, B);
   }
 
-  /// This method finds the nearest common dominator CFG block
-  /// for CFG block A and B. If there is no such block then return NULL.
+  /// \returns the nearest common dominator CFG block for CFG block \p A and \p
+  /// B. If there is no such block then return NULL.
   CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
-    return DT->findNearestCommonDominator(A, B);
+    return DT.findNearestCommonDominator(A, B);
   }
 
   const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
                                              const CFGBlock *B) {
-    return DT->findNearestCommonDominator(A, B);
+    return DT.findNearestCommonDominator(A, B);
   }
 
-  /// This method is used to update the dominator
-  /// tree information when a node's immediate dominator changes.
+  /// Update the dominator tree information when a node's immediate dominator
+  /// changes.
   void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
-    DT->changeImmediateDominator(N, NewIDom);
+    DT.changeImmediateDominator(N, NewIDom);
   }
 
-  /// This method tests if the given CFGBlock can be reachable from root.
-  /// Returns true if reachable, false otherwise.
+  /// Tests whether \p A is reachable from the entry block.
   bool isReachableFromEntry(const CFGBlock *A) {
-    return DT->isReachableFromEntry(A);
+    return DT.isReachableFromEntry(A);
   }
 
-  /// This method releases the memory held by the dominator tree.
+  /// Releases the memory held by the dominator tree.
   virtual void releaseMemory() {
-    DT->releaseMemory();
+    DT.releaseMemory();
   }
 
-  /// This method converts the dominator tree to human readable form.
+  /// Converts the dominator tree to human readable form.
   virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
-    DT->print(OS);
+    DT.print(OS);
   }
 
 private:
   CFG *cfg;
 };
 
+using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>;
+using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;
+
 } // 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</*Inverse=*/false>;
+SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
+                                                             /*Inverse=*/false>;
 
 template <>
 template <>
 inline ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get(
     clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/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;
 }
 
 using ClangCFGDomReverseChildrenGetter =
-SemiNCAInfo<DomTreeBase<clang::CFGBlock>>::ChildrenGetter</*Inverse=*/true>;
+SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
+                                                              /*Inverse=*/true>;
 
 template <>
 template <>
 inline ClangCFGDomReverseChildrenGetter::ResultTy
 ClangCFGDomReverseChildrenGetter::Get(
     clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
   auto IChildren = inverse_children<NodePtr>(N);
   ResultTy Ret(IChildren.begin(), IChildren.end());
   Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
   return Ret;
 }
 
+using ClangCFGPostDomChildrenGetter =
+SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
+                                                             /*Inverse=*/false>;
+
+template <>
+template <>
+inline ClangCFGPostDomChildrenGetter::ResultTy
+ClangCFGPostDomChildrenGetter::Get(
+    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/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;
+}
+
+using ClangCFGPostDomReverseChildrenGetter =
+SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
+                                                              /*Inverse=*/true>;
+
+template <>
+template <>
+inline ClangCFGPostDomReverseChildrenGetter::ResultTy
+ClangCFGPostDomReverseChildrenGetter::Get(
+    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
+  auto IChildren = inverse_children<NodePtr>(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.
 ///
 template <> struct GraphTraits<clang::DomTreeNode *> {
   using NodeRef = ::clang::DomTreeNode *;
static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
     return nodes_iterator(df_begin(getEntryNode(N)));
   }
 
   static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
     return nodes_iterator(df_end(getEntryNode(N)));
   }
 };
 
-template <> struct GraphTraits< ::clang::DominatorTree* >
-    : public GraphTraits< ::clang::DomTreeNode* > {
-  static NodeRef getEntryNode(::clang::DominatorTree *DT) {
+template <> struct GraphTraits<clang::CFGDomTree *>
+    : public GraphTraits<clang::DomTreeNode *> {
+  static NodeRef getEntryNode(clang::CFGDomTree *DT) {
     return DT->getRootNode();
   }
 
-  static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
+  static nodes_iterator nodes_begin(clang::CFGDomTree *N) {
     return nodes_iterator(df_begin(getEntryNode(N)));
   }
 
-  static nodes_iterator nodes_end(::clang::DominatorTree *N) {
+  static nodes_iterator nodes_end(clang::CFGDomTree *N) {
     return nodes_iterator(df_end(getEntryNode(N)));
   }
 };
 
 } // namespace llvm
 
 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H

cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td

CmdLineOption<Boolean,
                   Hide>
   ]>,
   Documentation<NotDocumented>;
 
 def DominatorsTreeDumper : Checker<"DumpDominators">,
   HelpText<"Print the dominance tree for a given CFG">,
   Documentation<NotDocumented>;
 
+def PostDominatorsTreeDumper : Checker<"DumpPostDominators">,
+  HelpText<"Print the post dominance tree for a given CFG">,
+  Documentation<NotDocumented>;
+
 def LiveVariablesDumper : Checker<"DumpLiveVars">,
   HelpText<"Print results of live variable analysis">,
   Documentation<NotDocumented>;
 
 def LiveStatementsDumper : Checker<"DumpLiveStmts">,
   HelpText<"Print results of live statement analysis">,
   Documentation<NotDocumented>;
 

cfe/trunk/lib/Analysis/Dominators.cpp

 //===- Dominators.cpp - Implementation of dominators tree for Clang CFG ---===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/Analyses/Dominators.h"
 
 using namespace clang;
 
-void DominatorTree::anchor() {}
+template <>
+void CFGDominatorTreeImpl</*IsPostDom=*/true>::anchor() {}
+
+template <>
+void CFGDominatorTreeImpl</*IsPostDom=*/false>::anchor() {}

cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp

 //===----------------------------------------------------------------------===//
 
 namespace {
 class DominatorsTreeDumper : public Checker<check::ASTCodeBody> {
 public:
   void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
                         BugReporter &BR) const {
     if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) {
-      DominatorTree dom;
-      dom.buildDominatorTree(*AC);
+      CFGDomTree dom;
+      dom.buildDominatorTree(AC->getCFG());
       dom.dump();
     }
   }
 };
 }
 
 void ento::registerDominatorsTreeDumper(CheckerManager &mgr) {
   mgr.registerChecker<DominatorsTreeDumper>();
 }
 
 bool ento::shouldRegisterDominatorsTreeDumper(const LangOptions &LO) {
   return true;
 }
 
 //===----------------------------------------------------------------------===//
+// PostDominatorsTreeDumper
+//===----------------------------------------------------------------------===//
+
+namespace {
+class PostDominatorsTreeDumper : public Checker<check::ASTCodeBody> {
+public:
+  void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
+                        BugReporter &BR) const {
+    if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) {
+      CFGPostDomTree dom;
+      dom.buildDominatorTree(AC->getCFG());
+      dom.dump();
+    }
+  }
+};
+}
+
+void ento::registerPostDominatorsTreeDumper(CheckerManager &mgr) {
+  mgr.registerChecker<PostDominatorsTreeDumper>();
+}
+
+bool ento::shouldRegisterPostDominatorsTreeDumper(const LangOptions &LO) {
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
 // LiveVariablesDumper
 //===----------------------------------------------------------------------===//
 
 namespace {
 class LiveVariablesDumper : public Checker<check::ASTCodeBody> {
 public:
   void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
                         BugReporter &BR) const {

cfe/trunk/test/Analysis/domtest.c

 // RUN: %clang_analyze_cc1 %s \
 // RUN:   -analyzer-checker=debug.DumpDominators \
+// RUN:   -analyzer-checker=debug.DumpPostDominators \
 // RUN:   2>&1 | FileCheck %s
 
 // Test the DominatorsTree implementation with various control flows
 int test1()
 {
   int x = 6;
   int y = x/2;
   int z;

 // 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)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,0)
+// CHECK-NEXT: (2,7)
+// CHECK-NEXT: (3,2)
+// CHECK-NEXT: (4,3)
+// CHECK-NEXT: (5,3)
+// CHECK-NEXT: (6,3)
+// CHECK-NEXT: (7,1)
+// CHECK-NEXT: (8,7)
+// CHECK-NEXT: (9,8)
 
 int test2()
 {
   int x,y,z;
 
   x = 10; y = 100;
   if(x > 0){
     y = 1;

 // 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)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,0)
+// CHECK-NEXT: (2,4)
+// CHECK-NEXT: (3,2)
+// CHECK-NEXT: (4,1)
+// CHECK-NEXT: (5,1)
+// CHECK-NEXT: (6,1)
+// CHECK-NEXT: (7,6)
 
 int test3()
 {
   int x,y,z;
 
   x = y = z = 1;
   if(x>0) {
     while(x>=0){

 // 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)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,0)
+// CHECK-NEXT: (2,6)
+// CHECK-NEXT: (3,5)
+// CHECK-NEXT: (4,3)
+// CHECK-NEXT: (5,2)
+// CHECK-NEXT: (6,1)
+// CHECK-NEXT: (7,1)
+// CHECK-NEXT: (8,7)
 
 int test4()
 {
   int y = 3;
   while(y > 0) {
     if(y < 3) {
       while(y>0)
         y ++;

 // 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)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,0)
+// CHECK-NEXT: (2,10)
+// CHECK-NEXT: (3,5)
+// CHECK-NEXT: (4,3)
+// CHECK-NEXT: (5,2)
+// CHECK-NEXT: (6,8)
+// CHECK-NEXT: (7,6)
+// CHECK-NEXT: (8,2)
+// CHECK-NEXT: (9,2)
+// CHECK-NEXT: (10,1)
+// CHECK-NEXT: (11,10)
+// CHECK-NEXT: (12,11)
 
 int test5()
 {
   int x,y,z,a,b,c;
   x = 1;
   y = 2;
   z = 3;
   a = 4;

 // 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)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,0)
+// CHECK-NEXT: (2,1)
+// CHECK-NEXT: (3,1)
+// CHECK-NEXT: (4,3)
+// CHECK-NEXT: (5,3)
+// CHECK-NEXT: (6,5)
+// CHECK-NEXT: (7,5)
+// CHECK-NEXT: (8,5)
+// CHECK-NEXT: (9,3)
+// CHECK-NEXT: (10,1)
+// CHECK-NEXT: (11,10)

cfe/trunk/test/Analysis/domtest.cpp

 // RUN: %clang_analyze_cc1 %s \
 // RUN:   -analyzer-checker=debug.DumpDominators \
+// RUN:   -analyzer-checker=debug.DumpPostDominators \
 // 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)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,2)
+// CHECK-NEXT: (2,0)
+// CHECK-NEXT: (3,1)
 
 void funcWithBranch() {
   int x = 0;
   if (coin()) {
     if (coin()) {
       x = 5;
     }
     int j = 10 / x;

 
 // 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)
+// CHECK-NEXT: Immediate post dominance tree (Node#,IDom#):
+// CHECK-NEXT: (0,0)
+// CHECK-NEXT: (1,0)
+// CHECK-NEXT: (2,1)
+// CHECK-NEXT: (3,1)
+// CHECK-NEXT: (4,0)
+// CHECK-NEXT: (5,4)