clang/unittests/Analysis/CFGDominatorTree.cpp

   1 //===- unittests/Analysis/CFGDominatorTree.cpp - CFG tests ----------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "CFGBuildResult.h"
  10 #include "clang/Analysis/Analyses/Dominators.h"
  11 #include "gtest/gtest.h"
  12
  13 namespace clang {
  14 namespace analysis {
  15 namespace {
  16
  17 TEST(CFGDominatorTree, DomTree) {
  18   const char *Code = R"(enum Kind {
  19                           A
  20                         };
  21
  22                         void f() {
  23                           switch(Kind{}) {
  24                           case A:
  25                             break;
  26                           }
  27                         })";
  28   BuildResult Result = BuildCFG(Code);
  29   EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
  30
  31   //  [B3 (ENTRY)]  -> [B1] -> [B2] -> [B0 (EXIT)]
  32   //                  switch  case A
  33
  34   CFG *cfg = Result.getCFG();
  35
  36   // Basic correctness checks.
  37   EXPECT_EQ(cfg->size(), 4u);
  38
  39   CFGBlock *ExitBlock = *cfg->begin();
  40   EXPECT_EQ(ExitBlock, &cfg->getExit());
  41
  42   CFGBlock *SwitchBlock = *(cfg->begin() + 1);
  43
  44   CFGBlock *CaseABlock = *(cfg->begin() + 2);
  45
  46   CFGBlock *EntryBlock = *(cfg->begin() + 3);
  47   EXPECT_EQ(EntryBlock, &cfg->getEntry());
  48
  49   // Test the dominator tree.
  50   CFGDomTree Dom;
  51   Dom.buildDominatorTree(cfg);
  52
  53   EXPECT_TRUE(Dom.dominates(ExitBlock, ExitBlock));
  54   EXPECT_FALSE(Dom.properlyDominates(ExitBlock, ExitBlock));
  55   EXPECT_TRUE(Dom.dominates(CaseABlock, ExitBlock));
  56   EXPECT_TRUE(Dom.dominates(SwitchBlock, ExitBlock));
  57   EXPECT_TRUE(Dom.dominates(EntryBlock, ExitBlock));
  58
  59   EXPECT_TRUE(Dom.dominates(CaseABlock, CaseABlock));
  60   EXPECT_FALSE(Dom.properlyDominates(CaseABlock, CaseABlock));
  61   EXPECT_TRUE(Dom.dominates(SwitchBlock, CaseABlock));
  62   EXPECT_TRUE(Dom.dominates(EntryBlock, CaseABlock));
  63
  64   EXPECT_TRUE(Dom.dominates(SwitchBlock, SwitchBlock));
  65   EXPECT_FALSE(Dom.properlyDominates(SwitchBlock, SwitchBlock));
  66   EXPECT_TRUE(Dom.dominates(EntryBlock, SwitchBlock));
  67
  68   EXPECT_TRUE(Dom.dominates(EntryBlock, EntryBlock));
  69   EXPECT_FALSE(Dom.properlyDominates(EntryBlock, EntryBlock));
  70
  71   // Test the post dominator tree.
  72
  73   CFGPostDomTree PostDom;
  74   PostDom.buildDominatorTree(cfg);
  75
  76   EXPECT_TRUE(PostDom.dominates(ExitBlock, EntryBlock));
  77   EXPECT_TRUE(PostDom.dominates(CaseABlock, EntryBlock));
  78   EXPECT_TRUE(PostDom.dominates(SwitchBlock, EntryBlock));
  79   EXPECT_TRUE(PostDom.dominates(EntryBlock, EntryBlock));
  80   EXPECT_FALSE(Dom.properlyDominates(EntryBlock, EntryBlock));
  81
  82   EXPECT_TRUE(PostDom.dominates(ExitBlock, SwitchBlock));
  83   EXPECT_TRUE(PostDom.dominates(CaseABlock, SwitchBlock));
  84   EXPECT_TRUE(PostDom.dominates(SwitchBlock, SwitchBlock));
  85   EXPECT_FALSE(Dom.properlyDominates(SwitchBlock, SwitchBlock));
  86
  87   EXPECT_TRUE(PostDom.dominates(ExitBlock, CaseABlock));
  88   EXPECT_TRUE(PostDom.dominates(CaseABlock, CaseABlock));
  89   EXPECT_FALSE(Dom.properlyDominates(CaseABlock, CaseABlock));
  90
  91   EXPECT_TRUE(PostDom.dominates(ExitBlock, ExitBlock));
  92   EXPECT_FALSE(Dom.properlyDominates(ExitBlock, ExitBlock));
  93
  94   // Tests for the post dominator tree's virtual root.
  95   EXPECT_TRUE(PostDom.dominates(nullptr, EntryBlock));
  96   EXPECT_TRUE(PostDom.dominates(nullptr, SwitchBlock));
  97   EXPECT_TRUE(PostDom.dominates(nullptr, CaseABlock));
  98   EXPECT_TRUE(PostDom.dominates(nullptr, ExitBlock));
  99 }
 100
 101 TEST(CFGDominatorTree, ControlDependency) {
 102   const char *Code = R"(bool coin();
 103
 104                         void funcWithBranch() {
 105                           int x = 0;
 106                           if (coin()) {
 107                             if (coin()) {
 108                               x = 5;
 109                             }
 110                             int j = 10 / x;
 111                             (void)j;
 112                           }
 113                         };)";
 114   BuildResult Result = BuildCFG(Code);
 115   EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
 116
 117   //                  1st if  2nd if
 118   //  [B5 (ENTRY)]  -> [B4] -> [B3] -> [B2] -> [B1] -> [B0 (EXIT)]
 119   //                    \        \              /         /
 120   //                     \        ------------->         /
 121   //                      ------------------------------>
 122
 123   CFG *cfg = Result.getCFG();
 124
 125   // Basic correctness checks.
 126   EXPECT_EQ(cfg->size(), 6u);
 127
 128   CFGBlock *ExitBlock = *cfg->begin();
 129   EXPECT_EQ(ExitBlock, &cfg->getExit());
 130
 131   CFGBlock *NullDerefBlock = *(cfg->begin() + 1);
 132
 133   CFGBlock *SecondThenBlock = *(cfg->begin() + 2);
 134
 135   CFGBlock *SecondIfBlock = *(cfg->begin() + 3);
 136
 137   CFGBlock *FirstIfBlock = *(cfg->begin() + 4);
 138
 139   CFGBlock *EntryBlock = *(cfg->begin() + 5);
 140   EXPECT_EQ(EntryBlock, &cfg->getEntry());
 141
 142   ControlDependencyCalculator Control(cfg);
 143
 144   EXPECT_TRUE(Control.isControlDependent(SecondThenBlock, SecondIfBlock));
 145   EXPECT_TRUE(Control.isControlDependent(SecondIfBlock, FirstIfBlock));
 146   EXPECT_FALSE(Control.isControlDependent(NullDerefBlock, SecondIfBlock));
 147 }
 148
 149 TEST(CFGDominatorTree, ControlDependencyWithLoops) {
 150   const char *Code = R"(int test3() {
 151                           int x,y,z;
 152
 153                           x = y = z = 1;
 154                           if (x > 0) {
 155                             while (x >= 0){
 156                               while (y >= x) {
 157                                 x = x-1;
 158                                 y = y/2;
 159                               }
 160                             }
 161                           }
 162                           z = y;
 163
 164                           return 0;
 165                         })";
 166   BuildResult Result = BuildCFG(Code);
 167   EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
 168
 169   //                           <- [B2] <-
 170   //                          /          \
 171   // [B8 (ENTRY)] -> [B7] -> [B6] ---> [B5] -> [B4] -> [B3]
 172   //                   \       |         \              /
 173   //                    \      |          <-------------
 174   //                     \      \
 175   //                      --------> [B1] -> [B0 (EXIT)]
 176
 177   CFG *cfg = Result.getCFG();
 178
 179   ControlDependencyCalculator Control(cfg);
 180
 181   auto GetBlock = [cfg] (unsigned Index) -> CFGBlock * {
 182     assert(Index < cfg->size());
 183     return *(cfg->begin() + Index);
 184   };
 185
 186   // While not immediately obvious, the second block in fact post dominates the
 187   // fifth, hence B5 is not a control dependency of 2.
 188   EXPECT_FALSE(Control.isControlDependent(GetBlock(5), GetBlock(2)));
 189 }
 190
 191
 192 } // namespace
 193 } // namespace analysis
 194 } // namespace clang