1//===- llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp ----------------===//
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 "CFGBuilder.h"
10#include "llvm/Analysis/PostDominators.h"
11#include "llvm/IR/Dominators.h"
12#include "llvm/Support/GenericDomTreeConstruction.h"
13#include "gtest/gtest.h"
14#include <random>
15
16#define DEBUG_TYPE "batch-update-tests"
17
18using namespace llvm;
19
20namespace {
21const auto CFGInsert = CFGBuilder::ActionKind::Insert;
22const auto CFGDelete = CFGBuilder::ActionKind::Delete;
23
24using DomUpdate = DominatorTree::UpdateType;
25static_assert(
26 std::is_same_v<DomUpdate, PostDominatorTree::UpdateType>,
27 "Trees differing only in IsPostDom should have the same update types");
28using DomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBDomTree>;
29using PostDomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBPostDomTree>;
30const auto Insert = DominatorTree::Insert;
31const auto Delete = DominatorTree::Delete;
32
33std::vector<DomUpdate> ToDomUpdates(CFGBuilder &B,
34 std::vector<CFGBuilder::Update> &In) {
35 std::vector<DomUpdate> Res;
36 Res.reserve(n: In.size());
37
38 for (const auto &CFGU : In)
39 Res.push_back(x: {CFGU.Action == CFGInsert ? Insert : Delete,
40 B.getOrAddBlock(BlockName: CFGU.Edge.From),
41 B.getOrAddBlock(BlockName: CFGU.Edge.To)});
42 return Res;
43}
44} // namespace
45
46TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) {
47 CFGHolder Holder;
48 CFGBuilder Builder(Holder.F, {{.From: "A", .To: "B"}}, {});
49
50 BasicBlock *A = Builder.getOrAddBlock(BlockName: "A");
51 BasicBlock *B = Builder.getOrAddBlock(BlockName: "B");
52 BasicBlock *C = Builder.getOrAddBlock(BlockName: "C");
53 BasicBlock *D = Builder.getOrAddBlock(BlockName: "D");
54
55 std::vector<DomUpdate> Updates = {
56 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
57 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
58 SmallVector<DomUpdate, 4> Legalized;
59 cfg::LegalizeUpdates<BasicBlock *>(AllUpdates: Updates, Result&: Legalized, InverseGraph: false);
60 LLVM_DEBUG(dbgs() << "Legalized updates:\t");
61 LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });
62 LLVM_DEBUG(dbgs() << "\n");
63 EXPECT_EQ(Legalized.size(), 3UL);
64 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, B, C}));
65 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, B, D}));
66 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Delete, A, B}));
67}
68
69TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) {
70 CFGHolder Holder;
71 CFGBuilder Builder(Holder.F, {{.From: "A", .To: "B"}}, {});
72
73 BasicBlock *A = Builder.getOrAddBlock(BlockName: "A");
74 BasicBlock *B = Builder.getOrAddBlock(BlockName: "B");
75 BasicBlock *C = Builder.getOrAddBlock(BlockName: "C");
76 BasicBlock *D = Builder.getOrAddBlock(BlockName: "D");
77
78 std::vector<DomUpdate> Updates = {
79 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
80 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
81 SmallVector<DomUpdate, 4> Legalized;
82 cfg::LegalizeUpdates<BasicBlock *>(AllUpdates: Updates, Result&: Legalized, InverseGraph: true);
83 LLVM_DEBUG(dbgs() << "Legalized postdom updates:\t");
84 LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });
85 LLVM_DEBUG(dbgs() << "\n");
86 EXPECT_EQ(Legalized.size(), 3UL);
87 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, C, B}));
88 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, D, B}));
89 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Delete, B, A}));
90}
91
92TEST(DominatorTreeBatchUpdates, SingleInsertion) {
93 CFGHolder Holder;
94 CFGBuilder Builder(Holder.F, {{.From: "A", .To: "B"}}, {{.Action: CFGInsert, .Edge: {.From: "B", .To: "C"}}});
95
96 DominatorTree DT(*Holder.F);
97 EXPECT_TRUE(DT.verify());
98 PostDominatorTree PDT(*Holder.F);
99 EXPECT_TRUE(PDT.verify());
100
101 BasicBlock *B = Builder.getOrAddBlock(BlockName: "B");
102 BasicBlock *C = Builder.getOrAddBlock(BlockName: "C");
103 std::vector<DomUpdate> Updates = {{Insert, B, C}};
104
105 ASSERT_TRUE(Builder.applyUpdate());
106
107 DT.applyUpdates(Updates);
108 EXPECT_TRUE(DT.verify());
109 PDT.applyUpdates(Updates);
110 EXPECT_TRUE(PDT.verify());
111}
112
113TEST(DominatorTreeBatchUpdates, SingleDeletion) {
114 CFGHolder Holder;
115 CFGBuilder Builder(Holder.F, {{.From: "A", .To: "B"}, {.From: "B", .To: "C"}},
116 {{.Action: CFGDelete, .Edge: {.From: "B", .To: "C"}}});
117
118 DominatorTree DT(*Holder.F);
119 EXPECT_TRUE(DT.verify());
120 PostDominatorTree PDT(*Holder.F);
121 EXPECT_TRUE(PDT.verify());
122
123 BasicBlock *B = Builder.getOrAddBlock(BlockName: "B");
124 BasicBlock *C = Builder.getOrAddBlock(BlockName: "C");
125 std::vector<DomUpdate> Updates = {{Delete, B, C}};
126
127 ASSERT_TRUE(Builder.applyUpdate());
128
129 DT.applyUpdates(Updates);
130 EXPECT_TRUE(DT.verify());
131 PDT.applyUpdates(Updates);
132 EXPECT_TRUE(PDT.verify());
133}
134
135TEST(DominatorTreeBatchUpdates, FewInsertion) {
136 std::vector<CFGBuilder::Update> CFGUpdates = {{.Action: CFGInsert, .Edge: {.From: "B", .To: "C"}},
137 {.Action: CFGInsert, .Edge: {.From: "C", .To: "B"}},
138 {.Action: CFGInsert, .Edge: {.From: "C", .To: "D"}},
139 {.Action: CFGInsert, .Edge: {.From: "D", .To: "E"}}};
140
141 CFGHolder Holder;
142 CFGBuilder Builder(Holder.F, {{.From: "A", .To: "B"}}, CFGUpdates);
143
144 DominatorTree DT(*Holder.F);
145 EXPECT_TRUE(DT.verify());
146 PostDominatorTree PDT(*Holder.F);
147 EXPECT_TRUE(PDT.verify());
148
149 BasicBlock *B = Builder.getOrAddBlock(BlockName: "B");
150 BasicBlock *C = Builder.getOrAddBlock(BlockName: "C");
151 BasicBlock *D = Builder.getOrAddBlock(BlockName: "D");
152 BasicBlock *E = Builder.getOrAddBlock(BlockName: "E");
153
154 std::vector<DomUpdate> Updates = {
155 {Insert, B, C}, {Insert, C, B}, {Insert, C, D}, {Insert, D, E}};
156
157 while (Builder.applyUpdate())
158 ;
159
160 DT.applyUpdates(Updates);
161 EXPECT_TRUE(DT.verify());
162 PDT.applyUpdates(Updates);
163 EXPECT_TRUE(PDT.verify());
164}
165
166TEST(DominatorTreeBatchUpdates, FewDeletions) {
167 std::vector<CFGBuilder::Update> CFGUpdates = {{.Action: CFGDelete, .Edge: {.From: "B", .To: "C"}},
168 {.Action: CFGDelete, .Edge: {.From: "C", .To: "B"}},
169 {.Action: CFGDelete, .Edge: {.From: "B", .To: "D"}},
170 {.Action: CFGDelete, .Edge: {.From: "D", .To: "E"}}};
171
172 CFGHolder Holder;
173 CFGBuilder Builder(
174 Holder.F, {{.From: "A", .To: "B"}, {.From: "B", .To: "C"}, {.From: "B", .To: "D"}, {.From: "D", .To: "E"}, {.From: "C", .To: "B"}},
175 CFGUpdates);
176
177 DominatorTree DT(*Holder.F);
178 EXPECT_TRUE(DT.verify());
179 PostDominatorTree PDT(*Holder.F);
180 EXPECT_TRUE(PDT.verify());
181
182 auto Updates = ToDomUpdates(B&: Builder, In&: CFGUpdates);
183
184 while (Builder.applyUpdate())
185 ;
186
187 DT.applyUpdates(Updates);
188 EXPECT_TRUE(DT.verify());
189 PDT.applyUpdates(Updates);
190 EXPECT_TRUE(PDT.verify());
191}
192
193TEST(DominatorTreeBatchUpdates, InsertDelete) {
194 std::vector<CFGBuilder::Arc> Arcs = {
195 {.From: "1", .To: "2"}, {.From: "2", .To: "3"}, {.From: "3", .To: "4"}, {.From: "4", .To: "5"}, {.From: "5", .To: "6"}, {.From: "5", .To: "7"},
196 {.From: "3", .To: "8"}, {.From: "8", .To: "9"}, {.From: "9", .To: "10"}, {.From: "8", .To: "11"}, {.From: "11", .To: "12"}};
197
198 std::vector<CFGBuilder::Update> Updates = {
199 {.Action: CFGInsert, .Edge: {.From: "2", .To: "4"}}, {.Action: CFGInsert, .Edge: {.From: "12", .To: "10"}},
200 {.Action: CFGInsert, .Edge: {.From: "10", .To: "9"}}, {.Action: CFGInsert, .Edge: {.From: "7", .To: "6"}},
201 {.Action: CFGInsert, .Edge: {.From: "7", .To: "5"}}, {.Action: CFGDelete, .Edge: {.From: "3", .To: "8"}},
202 {.Action: CFGInsert, .Edge: {.From: "10", .To: "7"}}, {.Action: CFGInsert, .Edge: {.From: "2", .To: "8"}},
203 {.Action: CFGDelete, .Edge: {.From: "3", .To: "4"}}, {.Action: CFGDelete, .Edge: {.From: "8", .To: "9"}},
204 {.Action: CFGDelete, .Edge: {.From: "11", .To: "12"}}};
205
206 CFGHolder Holder;
207 CFGBuilder B(Holder.F, Arcs, Updates);
208 DominatorTree DT(*Holder.F);
209 EXPECT_TRUE(DT.verify());
210 PostDominatorTree PDT(*Holder.F);
211 EXPECT_TRUE(PDT.verify());
212
213 while (B.applyUpdate())
214 ;
215
216 auto DomUpdates = ToDomUpdates(B, In&: Updates);
217 DT.applyUpdates(Updates: DomUpdates);
218 EXPECT_TRUE(DT.verify());
219 PDT.applyUpdates(Updates: DomUpdates);
220 EXPECT_TRUE(PDT.verify());
221}
222
223TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) {
224 std::vector<CFGBuilder::Arc> Arcs = {
225 {.From: "1", .To: "2"}, {.From: "2", .To: "3"}, {.From: "3", .To: "4"}, {.From: "4", .To: "5"}, {.From: "5", .To: "6"}, {.From: "5", .To: "7"},
226 {.From: "3", .To: "8"}, {.From: "8", .To: "9"}, {.From: "9", .To: "10"}, {.From: "8", .To: "11"}, {.From: "11", .To: "12"}};
227
228 std::vector<CFGBuilder::Update> Updates = {
229 {.Action: CFGInsert, .Edge: {.From: "2", .To: "4"}}, {.Action: CFGInsert, .Edge: {.From: "12", .To: "10"}},
230 {.Action: CFGInsert, .Edge: {.From: "10", .To: "9"}}, {.Action: CFGInsert, .Edge: {.From: "7", .To: "6"}},
231 {.Action: CFGInsert, .Edge: {.From: "7", .To: "5"}}, {.Action: CFGDelete, .Edge: {.From: "3", .To: "8"}},
232 {.Action: CFGInsert, .Edge: {.From: "10", .To: "7"}}, {.Action: CFGInsert, .Edge: {.From: "2", .To: "8"}},
233 {.Action: CFGDelete, .Edge: {.From: "3", .To: "4"}}, {.Action: CFGDelete, .Edge: {.From: "8", .To: "9"}},
234 {.Action: CFGDelete, .Edge: {.From: "11", .To: "12"}}};
235
236 std::mt19937 Generator(0);
237 for (unsigned i = 0; i < 16; ++i) {
238 std::shuffle(first: Updates.begin(), last: Updates.end(), g&: Generator);
239 CFGHolder Holder;
240 CFGBuilder B(Holder.F, Arcs, Updates);
241 DominatorTree DT(*Holder.F);
242 EXPECT_TRUE(DT.verify());
243 PostDominatorTree PDT(*Holder.F);
244 EXPECT_TRUE(PDT.verify());
245
246 while (B.applyUpdate())
247 ;
248
249 auto DomUpdates = ToDomUpdates(B, In&: Updates);
250 DT.applyUpdates(Updates: DomUpdates);
251 EXPECT_TRUE(DT.verify());
252 PDT.applyUpdates(Updates: DomUpdates);
253 EXPECT_TRUE(PDT.verify());
254 }
255}
256
257// These are some odd flowgraphs, usually generated from csmith cases,
258// which are difficult on post dom trees.
259TEST(DominatorTreeBatchUpdates, InfiniteLoop) {
260 std::vector<CFGBuilder::Arc> Arcs = {
261 {.From: "1", .To: "2"},
262 {.From: "2", .To: "3"},
263 {.From: "3", .To: "6"}, {.From: "3", .To: "5"},
264 {.From: "4", .To: "5"},
265 {.From: "5", .To: "2"},
266 {.From: "6", .To: "3"}, {.From: "6", .To: "4"}};
267
268 // SplitBlock on 3 -> 5
269 std::vector<CFGBuilder::Update> Updates = {
270 {.Action: CFGInsert, .Edge: {.From: "N", .To: "5"}}, {.Action: CFGInsert, .Edge: {.From: "3", .To: "N"}}, {.Action: CFGDelete, .Edge: {.From: "3", .To: "5"}}};
271
272 CFGHolder Holder;
273 CFGBuilder B(Holder.F, Arcs, Updates);
274 DominatorTree DT(*Holder.F);
275 EXPECT_TRUE(DT.verify());
276 PostDominatorTree PDT(*Holder.F);
277 EXPECT_TRUE(PDT.verify());
278
279 while (B.applyUpdate())
280 ;
281
282 auto DomUpdates = ToDomUpdates(B, In&: Updates);
283 DT.applyUpdates(Updates: DomUpdates);
284 EXPECT_TRUE(DT.verify());
285 PDT.applyUpdates(Updates: DomUpdates);
286 EXPECT_TRUE(PDT.verify());
287}
288
289TEST(DominatorTreeBatchUpdates, DeadBlocks) {
290 std::vector<CFGBuilder::Arc> Arcs = {
291 {.From: "1", .To: "2"},
292 {.From: "2", .To: "3"},
293 {.From: "3", .To: "4"}, {.From: "3", .To: "7"},
294 {.From: "4", .To: "4"},
295 {.From: "5", .To: "6"}, {.From: "5", .To: "7"},
296 {.From: "6", .To: "7"},
297 {.From: "7", .To: "2"}, {.From: "7", .To: "8"}};
298
299 // Remove dead 5 and 7,
300 // plus SplitBlock on 7 -> 8
301 std::vector<CFGBuilder::Update> Updates = {
302 {.Action: CFGDelete, .Edge: {.From: "6", .To: "7"}}, {.Action: CFGDelete, .Edge: {.From: "5", .To: "7"}}, {.Action: CFGDelete, .Edge: {.From: "5", .To: "6"}},
303 {.Action: CFGInsert, .Edge: {.From: "N", .To: "8"}}, {.Action: CFGInsert, .Edge: {.From: "7", .To: "N"}}, {.Action: CFGDelete, .Edge: {.From: "7", .To: "8"}}};
304
305 CFGHolder Holder;
306 CFGBuilder B(Holder.F, Arcs, Updates);
307 DominatorTree DT(*Holder.F);
308 EXPECT_TRUE(DT.verify());
309 PostDominatorTree PDT(*Holder.F);
310 EXPECT_TRUE(PDT.verify());
311
312 while (B.applyUpdate())
313 ;
314
315 auto DomUpdates = ToDomUpdates(B, In&: Updates);
316 DT.applyUpdates(Updates: DomUpdates);
317 EXPECT_TRUE(DT.verify());
318 PDT.applyUpdates(Updates: DomUpdates);
319 EXPECT_TRUE(PDT.verify());
320}
321
322TEST(DominatorTreeBatchUpdates, InfiniteLoop2) {
323 std::vector<CFGBuilder::Arc> Arcs = {
324 {.From: "1", .To: "2"},
325 {.From: "2", .To: "6"}, {.From: "2", .To: "3"},
326 {.From: "3", .To: "4"},
327 {.From: "4", .To: "5"}, {.From: "4", .To: "6"},
328 {.From: "5", .To: "4"},
329 {.From: "6", .To: "2"}};
330
331 // SplitBlock on 4 -> 6
332 std::vector<CFGBuilder::Update> Updates = {
333 {.Action: CFGInsert, .Edge: {.From: "N", .To: "6"}}, {.Action: CFGInsert, .Edge: {.From: "4", .To: "N"}}, {.Action: CFGDelete, .Edge: {.From: "4", .To: "6"}}};
334
335 CFGHolder Holder;
336 CFGBuilder B(Holder.F, Arcs, Updates);
337 DominatorTree DT(*Holder.F);
338 EXPECT_TRUE(DT.verify());
339 PostDominatorTree PDT(*Holder.F);
340 EXPECT_TRUE(PDT.verify());
341
342 while (B.applyUpdate())
343 ;
344
345 auto DomUpdates = ToDomUpdates(B, In&: Updates);
346 DT.applyUpdates(Updates: DomUpdates);
347 EXPECT_TRUE(DT.verify());
348 PDT.applyUpdates(Updates: DomUpdates);
349 EXPECT_TRUE(PDT.verify());
350}
351

source code of llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp