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
195