[analyzer][IDF] Add a control dependency calculator + a new debug checker

[Szelethus]

Summary

I intend to improve the analyzer's bug reports by tracking condition expressions.

01 bool b = messyComputation();
02 int i = 0;
03 if (b) // control dependency of the bug site, let's explain why we assume val to be true
04   10 / i; // warn: division by zero

I'll detail this heuristic in the followup patch, strictly related to this one however:

• Create the new ControlDependencyCalculator class that uses llvm::IDFCalculator to (lazily) calculate control dependencies for Clang's CFG.
• A new debug checker debug.DumpControlDependencies is added for lit tests
• Add unittests

[kuhar]

You can easily get CD by calculating the PostDominanceFrontier. LLVM implements a templated IDF (Iterated Dominance Frontier) construction.
A native implementation for llvm ir for reference, if you need:

• https://github.com/seahorn/seahorn/blob/deep-dev-5.0/include/seahorn/Analysis/ControlDependenceAnalysis.hh
• https://github.com/seahorn/seahorn/blob/deep-dev-5.0/lib/Analysis/ControlDependenceAnalysis.cc

Paper: R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently
computing static single assignment form and the control dependence graph. ACM
Trans. Program. Lang. Syst., 13(4):451–490, Oct. 1991.

[Szelethus]

In D62619#1521824, @kuhar wrote:

You can easily get CD by calculating the PostDominanceFrontier. LLVM implements a templated IDF (Iterated Dominance Frontier) construction.
A native implementation for llvm ir for reference, if you need:

• https://github.com/seahorn/seahorn/blob/deep-dev-5.0/include/seahorn/Analysis/ControlDependenceAnalysis.hh
• https://github.com/seahorn/seahorn/blob/deep-dev-5.0/lib/Analysis/ControlDependenceAnalysis.cc

Paper: R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently
computing static single assignment form and the control dependence graph. ACM
Trans. Program. Lang. Syst., 13(4):451–490, Oct. 1991.

Wow, thank you so much! This looks like a far superior but not a much more complicated solution then my own :) And I came to realize it may not even be correct.

[Szelethus]

I seem to have made good progress on this, although it did require a lot of code changes on LLVM side (basically turning BasicBlock * to template arguments). Here's a sample:

//                               <----------------------------------
//                              /              <-----------------   \
//                             /              /                  \   \
// [B12 (ENTRY)] -> [B11] -> [B10]-> [B9] -> [B8] ---> [B7] -> [B6]  |
//                             |      \        \                     /
//                             |       \        -----> [B2] --------/
//                             |        \      /
//                             |          -> [B5] -> [B4] -> [B3]
//                             |               \              /
//                             |                <------------
//                              \
//                               -> [B1] -> [B0 (EXIT)]

Control dependencies  (Node, Dependency):
(2,10)
(3,5)
(3,9)
(3,10)
(4,5)
(4,9)
(4,10)
(5,9)
(5,5)
(5,10)
(6,8)
(6,9)
(6,10)
(7,8)
(7,9)
(7,10)
(8,9)
(8,8)
(8,10)
(9,10)
(10,10)

My solution is inspired by

In D62619#1521824, @kuhar wrote:

• https://github.com/seahorn/seahorn/blob/deep-dev-5.0/include/seahorn/Analysis/ControlDependenceAnalysis.hh
• https://github.com/seahorn/seahorn/blob/deep-dev-5.0/lib/Analysis/ControlDependenceAnalysis.cc

, and I really like where this is going. I am yet to figure out how to deal with Clang's CFG containing null pointers in a not-too-invasive way (will probably end up doing something similar to ChildrenGetter), as it currently crashes.

[Szelethus]

Also, I read some of the article you showed as well as the one I found on the dominance frontier file documentation[1], and I feel a lot more enlightened about the subject, thanks! I'll spend more time on them before wrapping this up.

[1]
Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
POPL '95. ACM, New York, NY, 62-73.

[xazax.hun]

I did not check the algorithm as you planned changes to that. I only did a quick review of the interface which might also be rendered obsolete once you update this patch.

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

197

Is it sensible to have a non-const reference to the DomTree? Why would the user want to modify this? I think do not really do transformations on the CFG once it is built.

199

Same as above.

[Szelethus]

While I managed to create a version of llvm::IDFCalculator that both compiles and works well with clang::CFGBlock *, I'm a little unsure about the specifics. I sent out a mail to reach a wider audience about the next steps: http://lists.llvm.org/pipermail/llvm-dev/2019-June/132786.html

[Szelethus]

Now using llvm::IDFCalculator.

[kuhar]

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

51

DomTree has a constructor that runs the builder -- why not use it directly?

160

Do you need it at all? I understand it's a wrapper around dominators, but this API is virtually impossible to use safely.

225

I thinks it should be A is control dependent on B

[Szelethus]

Fixes according to reviewer comments.

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

51

That is correct, but DomTreeBase does not. :/

160

I agree 100%, I'll get rid of this in another patch.

[Szelethus]

Rebase on previous patches.

[Szelethus]

Gentle ping :^)

[kuhar]

The non-static-analyzer bits look good to me, I added a few nits.

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

230

If the virtual function is introduced by ManagesAnalysis, isn't it better to use override here?

235

Can it be const?

252

Can it be const?

257

Can dump be const?

257

In LLVM, dumps are usually annotated with the LLVM_DUMP_METHOD attribute and not compiled in release builds. Is the convention different in the static analyzer?

[NoQ]

Static Analyzer bits look great to me as well!

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

257

LLVM_DUMP_METHOD is great. Hiding dump methods under #ifndef NDEBUG is something i've seen very rarely. It's fairly annoying to me that exploded graph dumps are unavailable in release builds, but apart from that i don't have any immediate opinion, so this sounds like a global LLVM policy that we're historically not paying much attention to, but i don't mind complying.

clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp

90

CaPiTaLiZe VaRiAbLeS.

(*doesn't really care*)

[Szelethus]

Can you formally accept then? :) (I'll address inlines before commiting of course!)

In D62619#1566693, @kuhar wrote:

The non-static-analyzer bits look good to me, I added a few nits.

Thank you! This part of the project was fear of mine, and I'm super grateful for all the guidance you have given!

[NoQ]

Sure!

[Szelethus]

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

230

I admit to have copy-pasted this from the class above, and, well, it isn't introduced by ManagedAnalysis. Which begs the question why it was made virtual at all.

Nice catch!

235

IDFCalculator takes it's arguments by a non-const pointer. I guess I could fix that too on LLVM's side eventually. The method itself retrieves control dependencies lazily, and might modify the state of this class.

252

Same.

257

Cant be const for the same reasons.

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

 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
 #define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
 
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/iterator.h"
+#include "llvm/Support/GenericIteratedDominanceFrontier.h"
 #include "llvm/Support/GenericDomTree.h"
 #include "llvm/Support/GenericDomTreeConstruction.h"
 #include "llvm/Support/raw_ostream.h"
 
 // FIXME: There is no good reason for the domtree to require a print method
 // which accepts an LLVM Module, so remove this (and the method's argument that
 // needs it) when that is fixed.
 

 /// Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase.
 template <bool IsPostDom>
 class CFGDominatorTreeImpl : public ManagedAnalysis {
   virtual void anchor();
 
 public:
   using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>;
 
-  DominatorTreeBase DT;
-
   CFGDominatorTreeImpl() = default;
+
+  CFGDominatorTreeImpl(CFG *cfg) {
+    buildDominatorTree(cfg);
+  }
+
   ~CFGDominatorTreeImpl() override = default;
 
-  DominatorTreeBase& getBase() { return *DT; }
+  DominatorTreeBase &getBase() { return DT; }
+
+  CFG *getCFG() { return cfg; }
 
   /// \returns the root CFGBlock of the dominators tree.
   CFGBlock *getRoot() const {
     return DT.getRoot();
   }
 
   /// \returns the root DomTreeNode, which is the wrapper for CFGBlock.
   DomTreeNode *getRootNode() {
public:
 
   const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
                                              const CFGBlock *B) {
     return DT.findNearestCommonDominator(A, B);
   }
 
   /// Update the dominator tree information when a node's immediate dominator
   /// changes.
   void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
     DT.changeImmediateDominator(N, NewIDom);
   }
 
   /// Tests whether \p A is reachable from the entry block.
   bool isReachableFromEntry(const CFGBlock *A) {
     return DT.isReachableFromEntry(A);
   }
 
   /// Releases the memory held by the dominator tree.
   virtual void releaseMemory() {
     DT.releaseMemory();
   }
 
   /// Converts the dominator tree to human readable form.
   virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
     DT.print(OS);
   }
 
 private:
   CFG *cfg;
+  DominatorTreeBase DT;
 };
 
 using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>;
 using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;
 
+} // end of namespace clang
+
+namespace llvm {
+namespace IDFCalculatorDetail {
+
+/// Specialize ChildrenGetterTy to skip nullpointer successors.
+template <bool IsPostDom>
+struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> {
+  using NodeRef = typename GraphTraits<clang::CFGBlock>::NodeRef;
+  using ChildrenTy = SmallVector<NodeRef, 8>;
+
+  ChildrenTy get(const NodeRef &N) {
+    using OrderedNodeTy =
+        typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;
+
+    auto Children = children<OrderedNodeTy>(N);
+    ChildrenTy Ret{Children.begin(), Children.end()};
+    Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
+    return Ret;
+  }
+};
+
+} // end of namespace IDFCalculatorDetail
+} // end of namespace llvm
+
+namespace clang {
+
+class ControlDependencyCalculator : public ManagedAnalysis {
+  using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;
+  using CFGBlockVector = llvm::SmallVector<CFGBlock *, 4>;
+  using CFGBlockSet = llvm::SmallPtrSet<CFGBlock *, 4>;
+
+  CFGPostDomTree PostDomTree;
+  IDFCalculator IDFCalc;
+
+  llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;
+
+public:
+  ControlDependencyCalculator(CFG *cfg)
+    : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}
+
+  const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; }
+
+  virtual void releaseMemory() {
+    PostDomTree.releaseMemory();
+  }
+
+  // Lazily retrieves the set of control dependencies to \p A.
+  const CFGBlockVector &getControlDependencies(CFGBlock *A) {
+    auto It = ControlDepenencyMap.find(A);
+    if (It == ControlDepenencyMap.end()) {
+      CFGBlockSet DefiningBlock = {A};
+      IDFCalc.setDefiningBlocks(DefiningBlock);
+
+      CFGBlockVector ControlDependencies;
+      IDFCalc.calculate(ControlDependencies);
+
+      It = ControlDepenencyMap.insert({A, ControlDependencies}).first;
+    }
+
+    assert(It != ControlDepenencyMap.end());
+    return It->second;
+  }
+
+  /// Whether \p A is control dependent on \p B.
+  bool isControlDependent(CFGBlock *A, CFGBlock *B) {
+    return llvm::is_contained(getControlDependencies(A), B);
+  }
+
+  // Dumps immediate control dependencies for each block.
+  void dump() {
+    CFG *cfg = PostDomTree.getCFG();
+    llvm::errs() << "Control dependencies (Node#,Dependency#):\n";
+    for (CFGBlock *BB : *cfg) {
+
+      assert(BB &&
+             "LLVM's Dominator tree builder uses nullpointers to signify the "
+             "virtual root!");
+
+      for (CFGBlock *isControlDependency : getControlDependencies(BB))
+        llvm::errs() << "(" << BB->getBlockID()
+                     << ","
+                     << isControlDependency->getBlockID()
+                     << ")\n";
+    }
+  }
+};
+
 } // 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.
ClangCFGPostDomReverseChildrenGetter::Get(
   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
 
+/// Aaaand the same goes for IDFCalculator.
+
 //===-------------------------------------
 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 /// iterable by generic graph iterators.
 ///
 template <> struct GraphTraits<clang::DomTreeNode *> {
   using NodeRef = ::clang::DomTreeNode *;
   using ChildIteratorType = ::clang::DomTreeNode::iterator;
 

clang/include/clang/Analysis/CFG.h

template <> struct GraphTraits< ::clang::CFGBlock *> {
   using NodeRef = ::clang::CFGBlock *;
   using ChildIteratorType = ::clang::CFGBlock::succ_iterator;
 
   static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; }
   static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
 };
 
+template <> struct GraphTraits<clang::CFGBlock>
+    : GraphTraits<clang::CFGBlock *> {};
+
 template <> struct GraphTraits< const ::clang::CFGBlock *> {
   using NodeRef = const ::clang::CFGBlock *;
   using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator;
 
   static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; }
   static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
 };
 
+template <> struct GraphTraits<const clang::CFGBlock>
+    : GraphTraits<clang::CFGBlock *> {};
+
 template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> {
   using NodeRef = ::clang::CFGBlock *;
   using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
 
   static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) {
     return G.Graph;
   }
 
   static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
 };
 
+template <> struct GraphTraits<Inverse<clang::CFGBlock>>
+    : GraphTraits<clang::CFGBlock *> {};
+
 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> {
   using NodeRef = const ::clang::CFGBlock *;
   using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
 
   static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) {
     return G.Graph;
   }
 
   static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
 };
 
+template <> struct GraphTraits<const Inverse<clang::CFGBlock>>
+    : GraphTraits<clang::CFGBlock *> {};
+
 // Traits for: CFG
 
 template <> struct GraphTraits< ::clang::CFG* >
     : public GraphTraits< ::clang::CFGBlock *>  {
   using nodes_iterator = ::clang::CFG::iterator;
 
   static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); }
   static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

 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 ControlDependencyTreeDumper : Checker<"DumpControlDependencies">,
+  HelpText<"Print the post control dependency 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>;
 

clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp

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

clang/test/Analysis/domtest.c

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

 
 // [B9 (ENTRY)] -> [B8] -> [B7] -> [B6] -> [B5] -> [B3] -> [B2]
 //                          |\       \              /       /
 //                          | \       ---> [B4] --->       /
 //                          |  <---------------------------
 //                          V
 //                         [B1] -> [B0 (EXIT)]
 
-// CHECK:      Immediate dominance tree (Node#,IDom#):
+// CHECK:      Control dependencies (Node#,Dependency#):
+// CHECK-NEXT: (2,7)
+// CHECK-NEXT: (3,7)
+// CHECK-NEXT: (4,6)
+// CHECK-NEXT: (4,7)
+// CHECK-NEXT: (5,6)
+// CHECK-NEXT: (5,7)
+// CHECK-NEXT: (6,7)
+// CHECK-NEXT: (7,7)
+// CHECK-NEXT: 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)

 
 //                                    <-------------
 //                                   /              \
 //                    -----------> [B4] -> [B3] -> [B2]
 //                   /              |
 //                  /               V
 // [B7 (ENTRY)] -> [B6] -> [B5] -> [B1] -> [B0 (EXIT)]
 
-// CHECK:      Immediate dominance tree (Node#,IDom#):
+// CHECK:      Control dependencies (Node#,Dependency#):
+// CHECK-NEXT: (2,4)
+// CHECK-NEXT: (2,6)
+// CHECK-NEXT: (3,4)
+// CHECK-NEXT: (3,6)
+// CHECK-NEXT: (4,6)
+// CHECK-NEXT: (4,4)
+// CHECK-NEXT: (5,6)
+// CHECK-NEXT: 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)
while(x>=0){
       }
     }
   }
   z = y;
 
   return 0;
 }
 
-//                            <-------------
-//                           /              \
-//                           |        ---> [B2]
-//                           |       /
-// [B8 (ENTRY)] -> [B7] -> [B6] -> [B5] -> [B4] -> [B3]
-//                   \       |       \              /
-//                    \      |        <-------------
+//                           <- [B2] <-
+//                          /          \
+// [B8 (ENTRY)] -> [B7] -> [B6] ---> [B5] -> [B4] -> [B3]
+//                   \       |         \              /
+//                    \      |          <-------------
 //                     \      \
 //                      --------> [B1] -> [B0 (EXIT)]
 
-// CHECK:      Immediate dominance tree (Node#,IDom#):
+// CHECK:      Control dependencies (Node#,Dependency#):
+// CHECK-NEXT: (2,6)
+// CHECK-NEXT: (2,7)
+// CHECK-NEXT: (3,5)
+// CHECK-NEXT: (3,6)
+// CHECK-NEXT: (3,7)
+// CHECK-NEXT: (4,5)
+// CHECK-NEXT: (4,6)
+// CHECK-NEXT: (4,7)
+// CHECK-NEXT: (5,6)
+// CHECK-NEXT: (5,5)
+// CHECK-NEXT: (5,7)
+// CHECK-NEXT: (6,7)
+// CHECK-NEXT: (6,6)
+// CHECK-NEXT: 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)

 //                             |       \        -----> [B2] --------/
 //                             |        \      /
 //                             |          -> [B5] -> [B4] -> [B3]
 //                             |               \              /
 //                             |                <------------
 //                              \
 //                               -> [B1] -> [B0 (EXIT)]
 
-// CHECK:      Immediate dominance tree (Node#,IDom#):
+// CHECK:      Control dependencies (Node#,Dependency#):
+// CHECK-NEXT: (2,10)
+// CHECK-NEXT: (3,5)
+// CHECK-NEXT: (3,9)
+// CHECK-NEXT: (3,10)
+// CHECK-NEXT: (4,5)
+// CHECK-NEXT: (4,9)
+// CHECK-NEXT: (4,10)
+// CHECK-NEXT: (5,9)
+// CHECK-NEXT: (5,5)
+// CHECK-NEXT: (5,10)
+// CHECK-NEXT: (6,8)
+// CHECK-NEXT: (6,9)
+// CHECK-NEXT: (6,10)
+// CHECK-NEXT: (7,8)
+// CHECK-NEXT: (7,9)
+// CHECK-NEXT: (7,10)
+// CHECK-NEXT: (8,9)
+// CHECK-NEXT: (8,8)
+// CHECK-NEXT: (8,10)
+// CHECK-NEXT: (9,10)
+// CHECK-NEXT: (10,10)
+// CHECK-NEXT: 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)

 //                                                                   \
 // [B11 (ENTY)] -> [B10] -> [B9] -> [B8] -> [B7] -> [B5] -> [B3] -> [B1]
 //                            |       |       |      /       /       /
 //                            |       |       V     /       /       /
 //                            |       V     [B6] -->       /       /
 //                            V     [B4] ----------------->       /
 //                          [B2]--------------------------------->
 
-// CHECK:      Immediate dominance tree (Node#,IDom#):
+// CHECK:      Control dependencies (Node#,Dependency#):
+// CHECK-NEXT: (2,10)
+// CHECK-NEXT: (3,10)
+// CHECK-NEXT: (4,9)
+// CHECK-NEXT: (4,10)
+// CHECK-NEXT: (5,9)
+// CHECK-NEXT: (5,10)
+// CHECK-NEXT: (6,8)
+// CHECK-NEXT: (6,9)
+// CHECK-NEXT: (6,10)
+// CHECK-NEXT: (7,8)
+// CHECK-NEXT: (7,9)
+// CHECK-NEXT: (7,10)
+// CHECK-NEXT: (8,9)
+// CHECK-NEXT: (8,10)
+// CHECK-NEXT: (9,10)
+// CHECK-NEXT: 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)

clang/test/Analysis/domtest.cpp

 // RUN: %clang_analyze_cc1 %s \
 // RUN:   -analyzer-checker=debug.DumpDominators \
 // RUN:   -analyzer-checker=debug.DumpPostDominators \
+// RUN:   -analyzer-checker=debug.DumpControlDependencies \
 // 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:      Control dependencies (Node#,Dependency#):
+// CHECK-NEXT: 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;
     (void)j;
   }
 }
 
-//                            ----> [B2] ---->
-//                           /                \
-// [B5 (ENTRY)] -> [B4] -> [B3] -----------> [B1]
-//                   \                       /
-//                    ----> [B0 (EXIT)] <----
+//                  1st if  2nd if
+//  [B5 (ENTRY)]  -> [B4] -> [B3] -> [B2] -> [B1] -> [B0 (EXIT)]
+//                    \        \              /         /
+//                     \        ------------->         /
+//                      ------------------------------>
 
-// CHECK:      Immediate dominance tree (Node#,IDom#):
+// CHECK:      Control dependencies (Node#,Dependency#):
+// CHECK-NEXT: (1,4)
+// CHECK-NEXT: (2,3)
+// CHECK-NEXT: (2,4)
+// CHECK-NEXT: (3,4)
+// CHECK-NEXT: 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)

clang/unittests/Analysis/CFGDominatorTree.cpp

TEST(CFGDominatorTree, DomTree) {
 
   // Tests for the post dominator tree's virtual root.
   EXPECT_TRUE(PostDom.dominates(nullptr, EntryBlock));
   EXPECT_TRUE(PostDom.dominates(nullptr, SwitchBlock));
   EXPECT_TRUE(PostDom.dominates(nullptr, CaseABlock));
   EXPECT_TRUE(PostDom.dominates(nullptr, ExitBlock));
 }
 
+TEST(CFGDominatorTree, ControlDependency) {
+  const char *Code = R"(bool coin();
+
+                        void funcWithBranch() {
+                          int x = 0;
+                          if (coin()) {
+                            if (coin()) {
+                              x = 5;
+                            }
+                            int j = 10 / x;
+                            (void)j;
+                          }
+                        };)";
+  BuildResult Result = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+
+  //                  1st if  2nd if
+  //  [B5 (ENTRY)]  -> [B4] -> [B3] -> [B2] -> [B1] -> [B0 (EXIT)]
+  //                    \        \              /         /
+  //                     \        ------------->         /
+  //                      ------------------------------>
+
+  CFG *cfg = Result.getCFG();
+
+  // Sanity checks.
+  EXPECT_EQ(cfg->size(), 6u);
+
+  CFGBlock *ExitBlock = *cfg->begin();
+  EXPECT_EQ(ExitBlock, &cfg->getExit());
+
+  CFGBlock *NullDerefBlock = *(cfg->begin() + 1);
+
+  CFGBlock *SecondThenBlock = *(cfg->begin() + 2);
+
+  CFGBlock *SecondIfBlock = *(cfg->begin() + 3);
+  EXPECT_TRUE(hasStmtType<IfStmt>(SecondIfBlock));
+
+  CFGBlock *FirstIfBlock = *(cfg->begin() + 4);
+  EXPECT_TRUE(hasStmtType<IfStmt>(FirstIfBlock));
+
+  CFGBlock *EntryBlock = *(cfg->begin() + 5);
+  EXPECT_EQ(EntryBlock, &cfg->getEntry());
+
+  ControlDependencyCalculator Control(cfg);
+
+  EXPECT_TRUE(Control.isControlDependent(SecondThenBlock, SecondIfBlock));
+  EXPECT_TRUE(Control.isControlDependent(SecondIfBlock, FirstIfBlock));
+  EXPECT_FALSE(Control.isControlDependent(NullDerefBlock, SecondIfBlock));
+}
+
+TEST(CFGDominatorTree, ControlDependencyWithLoops) {
+  const char *Code = R"(int test3() {
+                          int x,y,z;
+
+                          x = y = z = 1;
+                          if (x > 0) {
+                            while (x >= 0){
+                              while (y >= x) {
+                                x = x-1;
+                                y = y/2;
+                              }
+                            }
+                          }
+                          z = y;
+
+                          return 0;
+                        })";
+  BuildResult Result = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+
+  //                           <- [B2] <-
+  //                          /          \
+  // [B8 (ENTRY)] -> [B7] -> [B6] ---> [B5] -> [B4] -> [B3]
+  //                   \       |         \              /
+  //                    \      |          <-------------
+  //                     \      \
+  //                      --------> [B1] -> [B0 (EXIT)]
+
+  CFG *cfg = Result.getCFG();
+
+  ControlDependencyCalculator Control(cfg);
+
+  auto GetBlock = [cfg] (unsigned Index) -> CFGBlock * {
+    assert(Index < cfg->size());
+    return *(cfg->begin() + Index);
+  };
+
+  // While not immediately obvious, the second block in fact post dominates the
+  // fifth, hence B5 is not a control dependency of 2.
+  EXPECT_FALSE(Control.isControlDependent(GetBlock(5), GetBlock(2)));
+}
+
+
 } // namespace
 } // namespace analysis
 } // namespace clang