[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

191 ↗

(On Diff #202017)

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.

193 ↗

(On Diff #202017)

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 ↗

(On Diff #204972)

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

160 ↗

(On Diff #204972)

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

225 ↗

(On Diff #204972)

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 ↗

(On Diff #204972)

That is correct, but DomTreeBase does not. :/

160 ↗

(On Diff #204972)

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 ↗

(On Diff #205917)

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

235 ↗

(On Diff #205917)

Can it be const?

252 ↗

(On Diff #205917)

Can it be const?

257 ↗

(On Diff #205917)

Can dump be const?

257 ↗

(On Diff #205917)

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 ↗

(On Diff #205917)

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 ↗

(On Diff #205917)

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 ↗

(On Diff #205917)

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 ↗

(On Diff #205917)

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 ↗

(On Diff #205917)

Same.

257 ↗

(On Diff #205917)

Cant be const for the same reasons.

cfe/trunk/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:
 
   /// 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; }
+
+  // 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.
+  LLVM_DUMP_METHOD 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.

cfe/trunk/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();}

cfe/trunk/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>;
 

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)) {
-      CFGDomTree dom;
-      dom.buildDominatorTree(AC->getCFG());
-      dom.dump();
+      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();
+      CFGPostDomTree Dom;
+      Dom.buildDominatorTree(AC->getCFG());
+      Dom.dump();
     }
   }
 };
 }
 
 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 {

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

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

cfe/trunk/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);
+
+  CFGBlock *FirstIfBlock = *(cfg->begin() + 4);
+
+  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