1//===- DomTreeUpdaterTest.cpp - DomTreeUpdater unit 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 "llvm/Analysis/DomTreeUpdater.h"
10#include "llvm/Analysis/PostDominators.h"
11#include "llvm/AsmParser/Parser.h"
12#include "llvm/IR/Constants.h"
13#include "llvm/IR/Dominators.h"
14#include "llvm/IR/Instructions.h"
15#include "llvm/IR/LLVMContext.h"
16#include "llvm/IR/Module.h"
17#include "llvm/Support/SourceMgr.h"
18#include "gtest/gtest.h"
19#include <algorithm>
20
21using namespace llvm;
22
23static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
24 StringRef ModuleStr) {
25 SMDiagnostic Err;
26 std::unique_ptr<Module> M = parseAssemblyString(AsmString: ModuleStr, Err, Context);
27 assert(M && "Bad LLVM IR?");
28 return M;
29}
30
31TEST(DomTreeUpdater, EagerUpdateBasicOperations) {
32 StringRef FuncName = "f";
33 StringRef ModuleString = R"(
34 define i32 @f(i32 %i, i32 *%p) {
35 bb0:
36 store i32 %i, i32 *%p
37 switch i32 %i, label %bb1 [
38 i32 1, label %bb2
39 i32 2, label %bb3
40 ]
41 bb1:
42 ret i32 1
43 bb2:
44 ret i32 2
45 bb3:
46 ret i32 3
47 })";
48 // Make the module.
49 LLVMContext Context;
50 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString);
51 Function *F = M->getFunction(Name: FuncName);
52
53 // Make the DomTreeUpdater.
54 DominatorTree DT(*F);
55 PostDominatorTree PDT(*F);
56 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
57
58 ASSERT_TRUE(DTU.hasDomTree());
59 ASSERT_TRUE(DTU.hasPostDomTree());
60 ASSERT_TRUE(DTU.isEager());
61 ASSERT_FALSE(DTU.isLazy());
62 ASSERT_TRUE(DTU.getDomTree().verify());
63 ASSERT_TRUE(DTU.getPostDomTree().verify());
64 ASSERT_FALSE(DTU.hasPendingUpdates());
65
66 Function::iterator FI = F->begin();
67 BasicBlock *BB0 = &*FI++;
68 BasicBlock *BB1 = &*FI++;
69 BasicBlock *BB2 = &*FI++;
70 BasicBlock *BB3 = &*FI++;
71 SwitchInst *SI = dyn_cast<SwitchInst>(Val: BB0->getTerminator());
72 ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
73
74 DTU.applyUpdatesPermissive(
75 Updates: {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}});
76 ASSERT_FALSE(DTU.hasPendingUpdates());
77
78 // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
79 // entries are discarded.
80 std::vector<DominatorTree::UpdateType> Updates;
81 Updates.reserve(n: 4);
82 Updates.push_back(x: {DominatorTree::Delete, BB0, BB3});
83 Updates.push_back(x: {DominatorTree::Delete, BB0, BB3});
84
85 // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
86 Updates.push_back(x: {DominatorTree::Insert, BB1, BB2});
87 // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
88 Updates.push_back(x: {DominatorTree::Delete, BB0, BB1});
89
90 // CFG Change: remove edge bb0 -> bb3.
91 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
92 BB3->removePredecessor(Pred: BB0);
93 for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
94 if (i->getCaseSuccessor() == BB3) {
95 SI->removeCase(I: i);
96 break;
97 }
98 }
99 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
100 // Deletion of a BasicBlock is an immediate event. We remove all uses to the
101 // contained Instructions and change the Terminator to "unreachable" when
102 // queued for deletion.
103 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
104 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
105 DTU.applyUpdatesPermissive(Updates);
106 ASSERT_FALSE(DTU.hasPendingUpdates());
107
108 // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
109 // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
110 DTU.applyUpdatesPermissive(
111 Updates: {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, BB0, BB1}});
112
113 // DTU working with Eager UpdateStrategy does not need to flush.
114 ASSERT_TRUE(DT.verify());
115 ASSERT_TRUE(PDT.verify());
116
117 // Test callback utils.
118 ASSERT_EQ(BB3->getParent(), F);
119 DTU.callbackDeleteBB(DelBB: BB3,
120 Callback: [&F](BasicBlock *BB) { ASSERT_NE(BB->getParent(), F); });
121
122 ASSERT_TRUE(DT.verify());
123 ASSERT_TRUE(PDT.verify());
124 ASSERT_FALSE(DTU.hasPendingUpdates());
125
126 // Unnecessary flush() test
127 DTU.flush();
128 EXPECT_TRUE(DT.verify());
129 EXPECT_TRUE(PDT.verify());
130
131 // Remove all case branch to BB2 to test Eager recalculation.
132 // Code section from llvm::ConstantFoldTerminator
133 for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
134 if (i->getCaseSuccessor() == BB2) {
135 // Remove this entry.
136 BB2->removePredecessor(Pred: BB0);
137 i = SI->removeCase(I: i);
138 e = SI->case_end();
139 } else
140 ++i;
141 }
142 ASSERT_FALSE(DT.verify());
143 ASSERT_FALSE(PDT.verify());
144 DTU.recalculate(F&: *F);
145 ASSERT_TRUE(DT.verify());
146 ASSERT_TRUE(PDT.verify());
147}
148
149TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) {
150 StringRef FuncName = "f";
151 StringRef ModuleString = R"(
152 define i32 @f() {
153 bb0:
154 br label %bb1
155 bb1:
156 ret i32 1
157 }
158 )";
159 // Make the module.
160 LLVMContext Context;
161 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString);
162 Function *F = M->getFunction(Name: FuncName);
163
164 // Make the DTU.
165 DominatorTree DT(*F);
166 PostDominatorTree PDT(*F);
167 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
168 ASSERT_TRUE(DTU.hasDomTree());
169 ASSERT_TRUE(DTU.hasPostDomTree());
170 ASSERT_TRUE(DTU.isEager());
171 ASSERT_FALSE(DTU.isLazy());
172 ASSERT_TRUE(DT.verify());
173 ASSERT_TRUE(PDT.verify());
174
175 Function::iterator FI = F->begin();
176 BasicBlock *BB0 = &*FI++;
177 BasicBlock *BB1 = &*FI++;
178
179 // Add a block as the new function entry BB. We also link it to BB0.
180 BasicBlock *NewEntry =
181 BasicBlock::Create(Context&: F->getContext(), Name: "new_entry", Parent: F, InsertBefore: BB0);
182 BranchInst::Create(IfTrue: BB0, InsertAtEnd: NewEntry);
183 EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
184 EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
185
186 DTU.applyUpdates(Updates: {{DominatorTree::Insert, NewEntry, BB0}});
187
188 // Changing the Entry BB requires a full recalculation of DomTree.
189 DTU.recalculate(F&: *F);
190 ASSERT_TRUE(DT.verify());
191 ASSERT_TRUE(PDT.verify());
192
193 // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
194 EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
195 NewEntry->getTerminator()->eraseFromParent();
196 BranchInst::Create(IfTrue: BB1, InsertAtEnd: NewEntry);
197 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
198
199 // Update the DTU. At this point bb0 now has no predecessors but is still a
200 // Child of F.
201 DTU.applyUpdates(Updates: {{DominatorTree::Delete, NewEntry, BB0},
202 {DominatorTree::Insert, NewEntry, BB1}});
203 ASSERT_TRUE(DT.verify());
204 ASSERT_TRUE(PDT.verify());
205
206 // Now remove bb0 from F.
207 ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
208 EXPECT_FALSE(DTU.isBBPendingDeletion(BB0));
209 DTU.deleteBB(DelBB: BB0);
210 ASSERT_TRUE(DT.verify());
211 ASSERT_TRUE(PDT.verify());
212}
213
214TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) {
215 StringRef FuncName = "f";
216 StringRef ModuleString = R"(
217 define i32 @f(i32 %i, i32 *%p) {
218 bb0:
219 store i32 %i, i32 *%p
220 switch i32 %i, label %bb1 [
221 i32 0, label %bb2
222 i32 1, label %bb2
223 i32 2, label %bb3
224 ]
225 bb1:
226 ret i32 1
227 bb2:
228 ret i32 2
229 bb3:
230 ret i32 3
231 }
232 )";
233 // Make the module.
234 LLVMContext Context;
235 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString);
236 Function *F = M->getFunction(Name: FuncName);
237
238 // Make the DTU.
239 DominatorTree DT(*F);
240 PostDominatorTree *PDT = nullptr;
241 DomTreeUpdater DTU(&DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
242 ASSERT_TRUE(DTU.hasDomTree());
243 ASSERT_FALSE(DTU.hasPostDomTree());
244 ASSERT_FALSE(DTU.isEager());
245 ASSERT_TRUE(DTU.isLazy());
246 ASSERT_TRUE(DTU.getDomTree().verify());
247
248 Function::iterator FI = F->begin();
249 BasicBlock *BB0 = &*FI++;
250 BasicBlock *BB1 = &*FI++;
251 BasicBlock *BB2 = &*FI++;
252 BasicBlock *BB3 = &*FI++;
253
254 // Test discards of self-domination update.
255 DTU.applyUpdatesPermissive(Updates: {{DominatorTree::Insert, BB0, BB0}});
256 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
257
258 // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
259 // entries are discarded.
260 std::vector<DominatorTree::UpdateType> Updates;
261 Updates.reserve(n: 4);
262 Updates.push_back(x: {DominatorTree::Delete, BB0, BB3});
263 Updates.push_back(x: {DominatorTree::Delete, BB0, BB3});
264
265 // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
266 Updates.push_back(x: {DominatorTree::Insert, BB1, BB2});
267 // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
268 Updates.push_back(x: {DominatorTree::Delete, BB0, BB1});
269
270 // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
271 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
272 BB0->getTerminator()->eraseFromParent();
273 BranchInst::Create(IfTrue: BB1, IfFalse: BB2, Cond: ConstantInt::getTrue(Context&: F->getContext()), InsertAtEnd: BB0);
274 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
275
276 // Verify. Updates to DTU must be applied *after* all changes to the CFG
277 // (including block deletion).
278 DTU.applyUpdatesPermissive(Updates);
279 ASSERT_TRUE(DTU.getDomTree().verify());
280
281 // Deletion of a BasicBlock is an immediate event. We remove all uses to the
282 // contained Instructions and change the Terminator to "unreachable" when
283 // queued for deletion. Its parent is still F until all the pending updates
284 // are applied to all trees held by the DomTreeUpdater (DomTree/PostDomTree).
285 // We don't defer this action because it can cause problems for other
286 // transforms or analysis as it's part of the actual CFG. We only defer
287 // updates to the DominatorTrees. This code will crash if it is placed before
288 // the BranchInst::Create() call above. After a deletion of a BasicBlock. Only
289 // an explicit flush event can trigger the flushing of deleteBBs. Because some
290 // passes using Lazy UpdateStrategy rely on this behavior.
291
292 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
293 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
294 EXPECT_FALSE(DTU.hasPendingDeletedBB());
295 DTU.deleteBB(DelBB: BB3);
296 EXPECT_TRUE(DTU.isBBPendingDeletion(BB3));
297 EXPECT_TRUE(DTU.hasPendingDeletedBB());
298 ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
299 EXPECT_EQ(BB3->getParent(), F);
300 DTU.recalculate(F&: *F);
301 EXPECT_FALSE(DTU.hasPendingDeletedBB());
302}
303
304TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) {
305 StringRef FuncName = "f";
306 StringRef ModuleString = R"(
307 define i32 @f(i32 %i, i32 *%p) {
308 bb0:
309 store i32 %i, i32 *%p
310 switch i32 %i, label %bb1 [
311 i32 2, label %bb2
312 i32 3, label %bb3
313 ]
314 bb1:
315 br label %bb3
316 bb2:
317 br label %bb3
318 bb3:
319 ret i32 3
320 }
321 )";
322 // Make the module.
323 LLVMContext Context;
324 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString);
325 Function *F = M->getFunction(Name: FuncName);
326
327 // Make the DTU.
328 DominatorTree DT(*F);
329 PostDominatorTree *PDT = nullptr;
330 DomTreeUpdater DTU(&DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
331 ASSERT_TRUE(DTU.hasDomTree());
332 ASSERT_FALSE(DTU.hasPostDomTree());
333 ASSERT_FALSE(DTU.isEager());
334 ASSERT_TRUE(DTU.isLazy());
335 ASSERT_TRUE(DTU.getDomTree().verify());
336
337 Function::iterator FI = F->begin();
338 BasicBlock *BB0 = &*FI++;
339 BasicBlock *BB1 = &*FI++;
340 BasicBlock *BB2 = &*FI++;
341 BasicBlock *BB3 = &*FI++;
342
343 // There are several CFG locations where we have:
344 //
345 // pred1..predN
346 // | |
347 // +> curr <+ converted into: pred1..predN curr
348 // | | |
349 // v +> succ <+
350 // succ
351 //
352 // There is a specific shape of this we have to be careful of:
353 //
354 // pred1..predN
355 // || |
356 // |+> curr <+ converted into: pred1..predN curr
357 // | | | |
358 // | v +> succ <+
359 // +-> succ
360 //
361 // While the final CFG form is functionally identical the updates to
362 // DTU are not. In the first case we must have
363 // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in
364 // the latter case we must *NOT* have
365 // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}).
366
367 // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to
368 // remove bb2.
369 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
370 BB0->getTerminator()->eraseFromParent();
371 BranchInst::Create(IfTrue: BB1, IfFalse: BB3, Cond: ConstantInt::getTrue(Context&: F->getContext()), InsertAtEnd: BB0);
372 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
373
374 // Test callback utils.
375 std::vector<BasicBlock *> BasicBlocks;
376 BasicBlocks.push_back(x: BB1);
377 BasicBlocks.push_back(x: BB2);
378 auto Eraser = [&](BasicBlock *BB) { llvm::erase(C&: BasicBlocks, V: BB); };
379 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
380 // Remove bb2 from F. This has to happen before the call to
381 // applyUpdates() for DTU to detect there is no longer an edge between
382 // bb2 -> bb3. The deleteBB() method converts bb2's TI into "unreachable".
383 ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));
384 EXPECT_FALSE(DTU.isBBPendingDeletion(BB2));
385 DTU.callbackDeleteBB(DelBB: BB2, Callback: Eraser);
386 EXPECT_TRUE(DTU.isBBPendingDeletion(BB2));
387 ASSERT_TRUE(isa<UnreachableInst>(BB2->getTerminator()));
388 EXPECT_EQ(BB2->getParent(), F);
389
390 // Queue up the DTU updates.
391 std::vector<DominatorTree::UpdateType> Updates;
392 Updates.reserve(n: 4);
393 Updates.push_back(x: {DominatorTree::Delete, BB0, BB2});
394 Updates.push_back(x: {DominatorTree::Delete, BB2, BB3});
395
396 // Handle the specific shape case next.
397 // CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1.
398 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
399 BB0->getTerminator()->eraseFromParent();
400 BranchInst::Create(IfTrue: BB3, InsertAtEnd: BB0);
401 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
402
403 // Remove bb1 from F. This has to happen before the call to
404 // applyUpdates() for DTU to detect there is no longer an edge between
405 // bb1 -> bb3. The deleteBB() method converts bb1's TI into "unreachable".
406 ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
407 EXPECT_FALSE(DTU.isBBPendingDeletion(BB1));
408 DTU.callbackDeleteBB(DelBB: BB1, Callback: Eraser);
409 EXPECT_TRUE(DTU.isBBPendingDeletion(BB1));
410 ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator()));
411 EXPECT_EQ(BB1->getParent(), F);
412
413 // Update the DTU. In this case we don't submit {DominatorTree::Insert, BB0,
414 // BB3} because the edge previously existed at the start of this test when DT
415 // was first created.
416 Updates.push_back(x: {DominatorTree::Delete, BB0, BB1});
417 Updates.push_back(x: {DominatorTree::Delete, BB1, BB3});
418
419 // Verify everything.
420 DTU.applyUpdatesPermissive(Updates);
421 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
422 DTU.flush();
423 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(0));
424 ASSERT_TRUE(DT.verify());
425}
426
427TEST(DomTreeUpdater, LazyUpdateBasicOperations) {
428 StringRef FuncName = "f";
429 StringRef ModuleString = R"(
430 define i32 @f(i32 %i, i32 *%p) {
431 bb0:
432 store i32 %i, i32 *%p
433 switch i32 %i, label %bb1 [
434 i32 0, label %bb2
435 i32 1, label %bb2
436 i32 2, label %bb3
437 ]
438 bb1:
439 ret i32 1
440 bb2:
441 ret i32 2
442 bb3:
443 ret i32 3
444 }
445 )";
446 // Make the module.
447 LLVMContext Context;
448 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString);
449 Function *F = M->getFunction(Name: FuncName);
450
451 // Make the DTU.
452 DominatorTree DT(*F);
453 PostDominatorTree PDT(*F);
454 DomTreeUpdater DTU(&DT, &PDT, DomTreeUpdater::UpdateStrategy::Lazy);
455 ASSERT_TRUE(DTU.hasDomTree());
456 ASSERT_TRUE(DTU.hasPostDomTree());
457 ASSERT_FALSE(DTU.isEager());
458 ASSERT_TRUE(DTU.isLazy());
459 ASSERT_TRUE(DTU.getDomTree().verify());
460 ASSERT_TRUE(DTU.getPostDomTree().verify());
461
462 Function::iterator FI = F->begin();
463 BasicBlock *BB0 = &*FI++;
464 BasicBlock *BB1 = &*FI++;
465 BasicBlock *BB2 = &*FI++;
466 BasicBlock *BB3 = &*FI++;
467 // Test discards of self-domination update.
468 DTU.applyUpdates(Updates: {{DominatorTree::Delete, BB0, BB0}});
469
470 // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
471 // entries are discarded.
472 std::vector<DominatorTree::UpdateType> Updates;
473 Updates.reserve(n: 4);
474 Updates.push_back(x: {DominatorTree::Delete, BB0, BB3});
475 Updates.push_back(x: {DominatorTree::Delete, BB0, BB3});
476
477 // Unnecessary Insert: no edge bb1 -> bb2 after change to bb0.
478 Updates.push_back(x: {DominatorTree::Insert, BB1, BB2});
479 // Unnecessary Delete: edge exists bb0 -> bb1 after change to bb0.
480 Updates.push_back(x: {DominatorTree::Delete, BB0, BB1});
481
482 // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
483 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
484 BB0->getTerminator()->eraseFromParent();
485 BranchInst::Create(IfTrue: BB1, IfFalse: BB2, Cond: ConstantInt::getTrue(Context&: F->getContext()), InsertAtEnd: BB0);
486 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
487
488 // Deletion of a BasicBlock is an immediate event. We remove all uses to the
489 // contained Instructions and change the Terminator to "unreachable" when
490 // queued for deletion. Its parent is still F until DTU.flushDomTree is
491 // called. We don't defer this action because it can cause problems for other
492 // transforms or analysis as it's part of the actual CFG. We only defer
493 // updates to the DominatorTree. This code will crash if it is placed before
494 // the BranchInst::Create() call above.
495 bool CallbackFlag = false;
496 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
497 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
498 DTU.callbackDeleteBB(DelBB: BB3, Callback: [&](BasicBlock *) { CallbackFlag = true; });
499 EXPECT_TRUE(DTU.isBBPendingDeletion(BB3));
500 ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
501 EXPECT_EQ(BB3->getParent(), F);
502
503 // Verify. Updates to DTU must be applied *after* all changes to the CFG
504 // (including block deletion).
505 DTU.applyUpdatesPermissive(Updates);
506 ASSERT_TRUE(DTU.getDomTree().verify());
507 ASSERT_TRUE(DTU.hasPendingUpdates());
508 ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
509 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
510 ASSERT_TRUE(DTU.hasPendingDeletedBB());
511 ASSERT_TRUE(DTU.getPostDomTree().verify());
512 ASSERT_FALSE(DTU.hasPendingUpdates());
513 ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
514 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
515 ASSERT_FALSE(DTU.hasPendingDeletedBB());
516 ASSERT_EQ(CallbackFlag, true);
517}
518
519TEST(DomTreeUpdater, LazyUpdateReplaceEntryBB) {
520 StringRef FuncName = "f";
521 StringRef ModuleString = R"(
522 define i32 @f() {
523 bb0:
524 br label %bb1
525 bb1:
526 ret i32 1
527 }
528 )";
529 // Make the module.
530 LLVMContext Context;
531 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString);
532 Function *F = M->getFunction(Name: FuncName);
533
534 // Make the DTU.
535 DominatorTree DT(*F);
536 PostDominatorTree PDT(*F);
537 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
538 ASSERT_TRUE(DTU.hasDomTree());
539 ASSERT_TRUE(DTU.hasPostDomTree());
540 ASSERT_FALSE(DTU.isEager());
541 ASSERT_TRUE(DTU.isLazy());
542 ASSERT_TRUE(DTU.getDomTree().verify());
543 ASSERT_TRUE(DTU.getPostDomTree().verify());
544
545 Function::iterator FI = F->begin();
546 BasicBlock *BB0 = &*FI++;
547 BasicBlock *BB1 = &*FI++;
548
549 // Add a block as the new function entry BB. We also link it to BB0.
550 BasicBlock *NewEntry =
551 BasicBlock::Create(Context&: F->getContext(), Name: "new_entry", Parent: F, InsertBefore: BB0);
552 BranchInst::Create(IfTrue: BB0, InsertAtEnd: NewEntry);
553 EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
554 EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
555
556 // Insert the new edge between new_entry -> bb0. Without this the
557 // recalculate() call below will not actually recalculate the DT as there
558 // are no changes pending and no blocks deleted.
559 DTU.applyUpdates(Updates: {{DominatorTree::Insert, NewEntry, BB0}});
560
561 // Changing the Entry BB requires a full recalculation.
562 DTU.recalculate(F&: *F);
563 ASSERT_TRUE(DTU.getDomTree().verify());
564 ASSERT_TRUE(DTU.getPostDomTree().verify());
565
566 // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
567 EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
568 NewEntry->getTerminator()->eraseFromParent();
569 BranchInst::Create(IfTrue: BB1, InsertAtEnd: NewEntry);
570 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
571
572 // Update the DTU. At this point bb0 now has no predecessors but is still a
573 // Child of F.
574 DTU.applyUpdates(Updates: {{DominatorTree::Delete, NewEntry, BB0},
575 {DominatorTree::Insert, NewEntry, BB1}});
576 DTU.flush();
577 ASSERT_TRUE(DT.verify());
578 ASSERT_TRUE(PDT.verify());
579
580 // Now remove bb0 from F.
581 ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
582 EXPECT_FALSE(DTU.isBBPendingDeletion(BB0));
583 DTU.deleteBB(DelBB: BB0);
584 EXPECT_TRUE(DTU.isBBPendingDeletion(BB0));
585 ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator()));
586 EXPECT_EQ(BB0->getParent(), F);
587
588 // Perform a full recalculation of the DTU. It is not necessary here but we
589 // do this to test the case when there are no pending DT updates but there are
590 // pending deleted BBs.
591 ASSERT_TRUE(DTU.hasPendingDeletedBB());
592 DTU.recalculate(F&: *F);
593 ASSERT_FALSE(DTU.hasPendingDeletedBB());
594}
595
596TEST(DomTreeUpdater, LazyUpdateStepTest) {
597 // This test focus on testing a DTU holding both trees applying multiple
598 // updates and DT/PDT not flushed together.
599 StringRef FuncName = "f";
600 StringRef ModuleString = R"(
601 define i32 @f(i32 %i, i32 *%p) {
602 bb0:
603 store i32 %i, i32 *%p
604 switch i32 %i, label %bb1 [
605 i32 0, label %bb1
606 i32 1, label %bb2
607 i32 2, label %bb3
608 i32 3, label %bb1
609 ]
610 bb1:
611 ret i32 1
612 bb2:
613 ret i32 2
614 bb3:
615 ret i32 3
616 }
617 )";
618 // Make the module.
619 LLVMContext Context;
620 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString);
621 Function *F = M->getFunction(Name: FuncName);
622
623 // Make the DomTreeUpdater.
624 DominatorTree DT(*F);
625 PostDominatorTree PDT(*F);
626 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
627
628 ASSERT_TRUE(DTU.hasDomTree());
629 ASSERT_TRUE(DTU.hasPostDomTree());
630 ASSERT_FALSE(DTU.isEager());
631 ASSERT_TRUE(DTU.isLazy());
632 ASSERT_TRUE(DTU.getDomTree().verify());
633 ASSERT_TRUE(DTU.getPostDomTree().verify());
634 ASSERT_FALSE(DTU.hasPendingUpdates());
635
636 Function::iterator FI = F->begin();
637 BasicBlock *BB0 = &*FI++;
638 FI++;
639 BasicBlock *BB2 = &*FI++;
640 BasicBlock *BB3 = &*FI++;
641 SwitchInst *SI = dyn_cast<SwitchInst>(Val: BB0->getTerminator());
642 ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
643
644 // Delete edge bb0 -> bb3.
645 std::vector<DominatorTree::UpdateType> Updates;
646 Updates.reserve(n: 1);
647 Updates.push_back(x: {DominatorTree::Delete, BB0, BB3});
648
649 // CFG Change: remove edge bb0 -> bb3.
650 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 5u);
651 BB3->removePredecessor(Pred: BB0);
652 for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
653 if (i->getCaseIndex() == 2) {
654 SI->removeCase(I: i);
655 break;
656 }
657 }
658 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
659 // Deletion of a BasicBlock is an immediate event. We remove all uses to the
660 // contained Instructions and change the Terminator to "unreachable" when
661 // queued for deletion.
662 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
663 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
664 DTU.applyUpdates(Updates);
665
666 // Only flush DomTree.
667 ASSERT_TRUE(DTU.getDomTree().verify());
668 ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
669 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
670
671 ASSERT_EQ(BB3->getParent(), F);
672 DTU.deleteBB(DelBB: BB3);
673
674 Updates.clear();
675
676 // Remove all case branch to BB2 to test Eager recalculation.
677 // Code section from llvm::ConstantFoldTerminator
678 for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
679 if (i->getCaseSuccessor() == BB2) {
680 // Remove this entry.
681 BB2->removePredecessor(Pred: BB0);
682 i = SI->removeCase(I: i);
683 e = SI->case_end();
684 Updates.push_back(x: {DominatorTree::Delete, BB0, BB2});
685 } else
686 ++i;
687 }
688
689 DTU.applyUpdatesPermissive(Updates);
690 // flush PostDomTree
691 ASSERT_TRUE(DTU.getPostDomTree().verify());
692 ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
693 ASSERT_TRUE(DTU.hasPendingDomTreeUpdates());
694 // flush both trees
695 DTU.flush();
696 ASSERT_TRUE(DT.verify());
697}
698
699TEST(DomTreeUpdater, NoTreeTest) {
700 StringRef FuncName = "f";
701 StringRef ModuleString = R"(
702 define i32 @f() {
703 bb0:
704 ret i32 0
705 }
706 )";
707 // Make the module.
708 LLVMContext Context;
709 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString);
710 Function *F = M->getFunction(Name: FuncName);
711
712 // Make the DTU.
713 DomTreeUpdater DTU(nullptr, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);
714 ASSERT_FALSE(DTU.hasDomTree());
715 ASSERT_FALSE(DTU.hasPostDomTree());
716 Function::iterator FI = F->begin();
717 BasicBlock *BB0 = &*FI++;
718 // Test whether PendingDeletedBB is flushed after the recalculation.
719 DTU.deleteBB(DelBB: BB0);
720 ASSERT_TRUE(DTU.hasPendingDeletedBB());
721 DTU.recalculate(F&: *F);
722 ASSERT_FALSE(DTU.hasPendingDeletedBB());
723}
724
725TEST(DomTreeUpdater, LazyUpdateDeduplicationTest) {
726 StringRef FuncName = "f";
727 StringRef ModuleString = R"(
728 define i32 @f() {
729 bb0:
730 br label %bb1
731 bb1:
732 ret i32 1
733 bb2:
734 ret i32 1
735 }
736 )";
737 // Make the module.
738 LLVMContext Context;
739 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString);
740 Function *F = M->getFunction(Name: FuncName);
741
742 // Make the DTU.
743 DominatorTree DT(*F);
744 DomTreeUpdater DTU(&DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);
745 ASSERT_TRUE(DTU.getDomTree().verify());
746
747 Function::iterator FI = F->begin();
748 BasicBlock *BB0 = &*FI++;
749 BasicBlock *BB1 = &*FI++;
750 BasicBlock *BB2 = &*FI++;
751
752 // CFG Change: remove bb0 -> bb1 and add back bb0 -> bb1.
753 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
754 BB0->getTerminator()->eraseFromParent();
755 BranchInst::Create(IfTrue: BB1, InsertAtEnd: BB0);
756 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
757
758 // Update the DTU and simulate duplicates.
759 DTU.applyUpdatesPermissive(Updates: {{DominatorTree::Delete, BB0, BB1},
760 {DominatorTree::Delete, BB0, BB1},
761 {DominatorTree::Insert, BB0, BB1},
762 {DominatorTree::Insert, BB0, BB1},
763 {DominatorTree::Insert, BB0, BB1}});
764
765 // The above operations result in a no-op.
766 ASSERT_FALSE(DTU.hasPendingUpdates());
767
768 // Update the DTU. Simulate an invalid update.
769 DTU.applyUpdatesPermissive(Updates: {{DominatorTree::Delete, BB0, BB1}});
770 ASSERT_FALSE(DTU.hasPendingUpdates());
771
772 // CFG Change: remove bb0 -> bb1.
773 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
774 BB0->getTerminator()->eraseFromParent();
775
776 // Update the DTU and simulate invalid updates.
777 DTU.applyUpdatesPermissive(Updates: {{DominatorTree::Delete, BB0, BB1},
778 {DominatorTree::Insert, BB0, BB1},
779 {DominatorTree::Delete, BB0, BB1},
780 {DominatorTree::Insert, BB0, BB1},
781 {DominatorTree::Insert, BB0, BB1}});
782 ASSERT_TRUE(DTU.hasPendingUpdates());
783
784 // CFG Change: add bb0 -> bb2.
785 BranchInst::Create(IfTrue: BB2, InsertAtEnd: BB0);
786 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
787 DTU.applyUpdates(Updates: {{DominatorTree::Insert, BB0, BB2}});
788 ASSERT_TRUE(DTU.getDomTree().verify());
789}
790

source code of llvm/unittests/Analysis/DomTreeUpdaterTest.cpp