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
TEST(CFGDominatorTree,DomTree)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 // Sanity 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
TEST(CFGDominatorTree,ControlDependency)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 // Sanity 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
TEST(CFGDominatorTree,ControlDependencyWithLoops)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