[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

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

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

50

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

154

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

219

I thinks it should be A is control dependent on B

[Szelethus]

Fixes according to reviewer comments.

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

50

That is correct, but DomTreeBase does not. :/

154

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

224

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

229

Can it be const?

246

Can it be const?

251

Can dump be const?

251

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

251

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

224

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!

229

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.

246

Same.

251

Cant be const for the same reasons.

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

 /// 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() 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>;
 
+class CFGControlDependencyTree : public ManagedAnalysis {
+  CFGDomTree DomTree;
+  CFGPostDomTree PostDomTree;
+
+public:
+  void buildDominatorTree(CFG *cfg) {
+    DomTree.buildDominatorTree(cfg);
+    PostDomTree.buildDominatorTree(cfg);
+  }
+
+  CFGDomTree &getCFGDomTree() { return DomTree; }
+  const CFGDomTree &getCFGDomTree() const { return DomTree; }
+  CFGPostDomTree &getCFGPostDomTree() { return PostDomTree; }
+  const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; }
+
+  virtual void releaseMemory() {
+    DomTree.releaseMemory();
+    PostDomTree.releaseMemory();
+  }
+
+  bool isControlDependency(CFGBlock *A, CFGBlock *B) const {
+    return DomTree.dominates(A, B) && !PostDomTree.dominates(B, A);
+  }
+
+  /// Dumps immediate control dependencies for each block.
+  void dump() {
+    CFG *cfg = DomTree.getCFG();
+    llvm::errs() << "Immediate control dependency tree (Node#,IDom#):\n";
+    for (CFG::const_iterator I = cfg->begin(),
+        E = cfg->end(); I != E; ++I) {
+
+      assert(*I &&
+             "LLVM's Dominator tree builder uses nullpointers to signify the "
+             "virtual root!");
+
+      DomTreeNode *IDom = DomTree.getBase().getNode(*I)->getIDom();
+      if (IDom) {
+        if (!PostDomTree.dominates(*I, IDom->getBlock()))
+          llvm::errs() << "(" << (*I)->getBlockID()
+                       << ","
+                       << IDom->getBlock()->getBlockID()
+                       << ")\n";
+      }
+
+      bool IsEntryBlock = *I == &(*I)->getParent()->getEntry();
+      assert((IDom || IsEntryBlock) &&
+             "If the immediate dominator node is nullptr, the CFG block "
+             "should be the entry point (since it's the root of the dominator "
+             "tree)");
+      (void)IsEntryBlock;
+    }
+  }
+};
+
 } // 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<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
                                                              /*Inverse=*/false>;
 
 template <>
 template <>
 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;

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)) {
+      CFGControlDependencyTree dom;
+      dom.buildDominatorTree(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:      Immediate control dependency tree (Node#,IDom#):
+// CHECK-NEXT: (4,6)
+// CHECK-NEXT: (5,6)
+// CHECK-NEXT: (6,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:      Immediate control dependency tree (Node#,IDom#):
+// CHECK-NEXT: (3,4)
+// CHECK-NEXT: (4,6)
+// 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)

 //                           |        ---> [B2]
 //                           |       /
 // [B8 (ENTRY)] -> [B7] -> [B6] -> [B5] -> [B4] -> [B3]
 //                   \       |       \              /
 //                    \      |        <-------------
 //                     \      \
 //                      --------> [B1] -> [B0 (EXIT)]
 
-// CHECK:      Immediate dominance tree (Node#,IDom#):
+// CHECK:      Immediate control dependency tree (Node#,IDom#):
+// CHECK-NEXT: (4,5)
+// CHECK-NEXT: (5,6)
+// CHECK-NEXT: (6,7)
+// 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:      Immediate control dependency tree (Node#,IDom#):
+// CHECK-NEXT: (4,5)
+// CHECK-NEXT: (5,9)
+// CHECK-NEXT: (7,8)
+// CHECK-NEXT: (8,9)
+// CHECK-NEXT: (9,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:      Immediate control dependency tree (Node#,IDom#):
+// CHECK-NEXT: (2,10)
+// CHECK-NEXT: (4,9)
+// CHECK-NEXT: (6,8)
+// CHECK-NEXT: (7,8)
+// CHECK-NEXT: (8,9)
+// 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:      Immediate control dependency tree (Node#,IDom#):
+// 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:      Immediate control dependency tree (Node#,IDom#):
+// CHECK-NEXT: (2,3)
+// 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());
+
+  CFGControlDependencyTree Control;
+  Control.buildDominatorTree(cfg);
+
+  EXPECT_TRUE(Control.isControlDependency(SecondIfBlock, SecondThenBlock));
+  EXPECT_TRUE(Control.isControlDependency(FirstIfBlock, SecondIfBlock));
+  EXPECT_FALSE(Control.isControlDependency(SecondIfBlock, NullDerefBlock));
+}
+
+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();
+
+  CFGControlDependencyTree Control;
+  Control.buildDominatorTree(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.isControlDependency(GetBlock(5), GetBlock(2)));
+  EXPECT_TRUE(Control.getCFGDomTree().dominates(GetBlock(5), GetBlock(2)));
+  EXPECT_TRUE(Control.getCFGPostDomTree().dominates(GetBlock(2), GetBlock(5)));
+}
+
+
 } // namespace
 } // namespace analysis
 } // namespace clang