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
21 using namespace llvm;
22
makeLLVMModule(LLVMContext & Context,StringRef ModuleStr)23 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
24 StringRef ModuleStr) {
25 SMDiagnostic Err;
26 std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
27 assert(M && "Bad LLVM IR?");
28 return M;
29 }
30
TEST(DomTreeUpdater,EagerUpdateBasicOperations)31 TEST(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, ModuleString);
51 Function *F = M->getFunction(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>(BB0->getTerminator());
72 ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
73
74 DTU.applyUpdatesPermissive(
75 {{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(4);
82 Updates.push_back({DominatorTree::Delete, BB0, BB3});
83 Updates.push_back({DominatorTree::Delete, BB0, BB3});
84
85 // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
86 Updates.push_back({DominatorTree::Insert, BB1, BB2});
87 // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
88 Updates.push_back({DominatorTree::Delete, BB0, BB1});
89
90 // CFG Change: remove edge bb0 -> bb3.
91 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
92 BB3->removePredecessor(BB0);
93 for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
94 if (i->getCaseSuccessor() == BB3) {
95 SI->removeCase(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 {{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(BB3,
120 [&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(BB0);
137 i = SI->removeCase(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);
145 ASSERT_TRUE(DT.verify());
146 ASSERT_TRUE(PDT.verify());
147 }
148
TEST(DomTreeUpdater,EagerUpdateReplaceEntryBB)149 TEST(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, ModuleString);
162 Function *F = M->getFunction(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(F->getContext(), "new_entry", F, BB0);
182 BranchInst::Create(BB0, NewEntry);
183 EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
184 EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
185
186 DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}});
187
188 // Changing the Entry BB requires a full recalculation of DomTree.
189 DTU.recalculate(*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(BB1, 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({{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(BB0);
210 ASSERT_TRUE(DT.verify());
211 ASSERT_TRUE(PDT.verify());
212 }
213
TEST(DomTreeUpdater,LazyUpdateDTBasicOperations)214 TEST(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, ModuleString);
236 Function *F = M->getFunction(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({{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(4);
262 Updates.push_back({DominatorTree::Delete, BB0, BB3});
263 Updates.push_back({DominatorTree::Delete, BB0, BB3});
264
265 // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
266 Updates.push_back({DominatorTree::Insert, BB1, BB2});
267 // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
268 Updates.push_back({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(BB1, BB2, ConstantInt::getTrue(F->getContext()), 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(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);
301 EXPECT_FALSE(DTU.hasPendingDeletedBB());
302 }
303
TEST(DomTreeUpdater,LazyUpdateDTInheritedPreds)304 TEST(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, ModuleString);
325 Function *F = M->getFunction(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(BB1, BB3, ConstantInt::getTrue(F->getContext()), BB0);
372 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
373
374 // Test callback utils.
375 std::vector<BasicBlock *> BasicBlocks;
376 BasicBlocks.push_back(BB1);
377 BasicBlocks.push_back(BB2);
378 auto Eraser = [&](BasicBlock *BB) {
379 BasicBlocks.erase(
380 std::remove_if(BasicBlocks.begin(), BasicBlocks.end(),
381 [&](const BasicBlock *i) { return i == BB; }),
382 BasicBlocks.end());
383 };
384 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
385 // Remove bb2 from F. This has to happen before the call to
386 // applyUpdates() for DTU to detect there is no longer an edge between
387 // bb2 -> bb3. The deleteBB() method converts bb2's TI into "unreachable".
388 ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));
389 EXPECT_FALSE(DTU.isBBPendingDeletion(BB2));
390 DTU.callbackDeleteBB(BB2, Eraser);
391 EXPECT_TRUE(DTU.isBBPendingDeletion(BB2));
392 ASSERT_TRUE(isa<UnreachableInst>(BB2->getTerminator()));
393 EXPECT_EQ(BB2->getParent(), F);
394
395 // Queue up the DTU updates.
396 std::vector<DominatorTree::UpdateType> Updates;
397 Updates.reserve(4);
398 Updates.push_back({DominatorTree::Delete, BB0, BB2});
399 Updates.push_back({DominatorTree::Delete, BB2, BB3});
400
401 // Handle the specific shape case next.
402 // CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1.
403 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
404 BB0->getTerminator()->eraseFromParent();
405 BranchInst::Create(BB3, BB0);
406 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
407
408 // Remove bb1 from F. This has to happen before the call to
409 // applyUpdates() for DTU to detect there is no longer an edge between
410 // bb1 -> bb3. The deleteBB() method converts bb1's TI into "unreachable".
411 ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
412 EXPECT_FALSE(DTU.isBBPendingDeletion(BB1));
413 DTU.callbackDeleteBB(BB1, Eraser);
414 EXPECT_TRUE(DTU.isBBPendingDeletion(BB1));
415 ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator()));
416 EXPECT_EQ(BB1->getParent(), F);
417
418 // Update the DTU. In this case we don't submit {DominatorTree::Insert, BB0,
419 // BB3} because the edge previously existed at the start of this test when DT
420 // was first created.
421 Updates.push_back({DominatorTree::Delete, BB0, BB1});
422 Updates.push_back({DominatorTree::Delete, BB1, BB3});
423
424 // Verify everything.
425 DTU.applyUpdatesPermissive(Updates);
426 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
427 DTU.flush();
428 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(0));
429 ASSERT_TRUE(DT.verify());
430 }
431
TEST(DomTreeUpdater,LazyUpdateBasicOperations)432 TEST(DomTreeUpdater, LazyUpdateBasicOperations) {
433 StringRef FuncName = "f";
434 StringRef ModuleString = R"(
435 define i32 @f(i32 %i, i32 *%p) {
436 bb0:
437 store i32 %i, i32 *%p
438 switch i32 %i, label %bb1 [
439 i32 0, label %bb2
440 i32 1, label %bb2
441 i32 2, label %bb3
442 ]
443 bb1:
444 ret i32 1
445 bb2:
446 ret i32 2
447 bb3:
448 ret i32 3
449 }
450 )";
451 // Make the module.
452 LLVMContext Context;
453 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
454 Function *F = M->getFunction(FuncName);
455
456 // Make the DTU.
457 DominatorTree DT(*F);
458 PostDominatorTree PDT(*F);
459 DomTreeUpdater DTU(&DT, &PDT, DomTreeUpdater::UpdateStrategy::Lazy);
460 ASSERT_TRUE(DTU.hasDomTree());
461 ASSERT_TRUE(DTU.hasPostDomTree());
462 ASSERT_FALSE(DTU.isEager());
463 ASSERT_TRUE(DTU.isLazy());
464 ASSERT_TRUE(DTU.getDomTree().verify());
465 ASSERT_TRUE(DTU.getPostDomTree().verify());
466
467 Function::iterator FI = F->begin();
468 BasicBlock *BB0 = &*FI++;
469 BasicBlock *BB1 = &*FI++;
470 BasicBlock *BB2 = &*FI++;
471 BasicBlock *BB3 = &*FI++;
472 // Test discards of self-domination update.
473 DTU.applyUpdates({{DominatorTree::Delete, BB0, BB0}});
474
475 // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
476 // entries are discarded.
477 std::vector<DominatorTree::UpdateType> Updates;
478 Updates.reserve(4);
479 Updates.push_back({DominatorTree::Delete, BB0, BB3});
480 Updates.push_back({DominatorTree::Delete, BB0, BB3});
481
482 // Unnecessary Insert: no edge bb1 -> bb2 after change to bb0.
483 Updates.push_back({DominatorTree::Insert, BB1, BB2});
484 // Unnecessary Delete: edge exists bb0 -> bb1 after change to bb0.
485 Updates.push_back({DominatorTree::Delete, BB0, BB1});
486
487 // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
488 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
489 BB0->getTerminator()->eraseFromParent();
490 BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
491 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
492
493 // Deletion of a BasicBlock is an immediate event. We remove all uses to the
494 // contained Instructions and change the Terminator to "unreachable" when
495 // queued for deletion. Its parent is still F until DTU.flushDomTree is
496 // called. We don't defer this action because it can cause problems for other
497 // transforms or analysis as it's part of the actual CFG. We only defer
498 // updates to the DominatorTree. This code will crash if it is placed before
499 // the BranchInst::Create() call above.
500 bool CallbackFlag = false;
501 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
502 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
503 DTU.callbackDeleteBB(BB3, [&](BasicBlock *) { CallbackFlag = true; });
504 EXPECT_TRUE(DTU.isBBPendingDeletion(BB3));
505 ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
506 EXPECT_EQ(BB3->getParent(), F);
507
508 // Verify. Updates to DTU must be applied *after* all changes to the CFG
509 // (including block deletion).
510 DTU.applyUpdatesPermissive(Updates);
511 ASSERT_TRUE(DTU.getDomTree().verify());
512 ASSERT_TRUE(DTU.hasPendingUpdates());
513 ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
514 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
515 ASSERT_TRUE(DTU.hasPendingDeletedBB());
516 ASSERT_TRUE(DTU.getPostDomTree().verify());
517 ASSERT_FALSE(DTU.hasPendingUpdates());
518 ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
519 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
520 ASSERT_FALSE(DTU.hasPendingDeletedBB());
521 ASSERT_EQ(CallbackFlag, true);
522 }
523
TEST(DomTreeUpdater,LazyUpdateReplaceEntryBB)524 TEST(DomTreeUpdater, LazyUpdateReplaceEntryBB) {
525 StringRef FuncName = "f";
526 StringRef ModuleString = R"(
527 define i32 @f() {
528 bb0:
529 br label %bb1
530 bb1:
531 ret i32 1
532 }
533 )";
534 // Make the module.
535 LLVMContext Context;
536 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
537 Function *F = M->getFunction(FuncName);
538
539 // Make the DTU.
540 DominatorTree DT(*F);
541 PostDominatorTree PDT(*F);
542 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
543 ASSERT_TRUE(DTU.hasDomTree());
544 ASSERT_TRUE(DTU.hasPostDomTree());
545 ASSERT_FALSE(DTU.isEager());
546 ASSERT_TRUE(DTU.isLazy());
547 ASSERT_TRUE(DTU.getDomTree().verify());
548 ASSERT_TRUE(DTU.getPostDomTree().verify());
549
550 Function::iterator FI = F->begin();
551 BasicBlock *BB0 = &*FI++;
552 BasicBlock *BB1 = &*FI++;
553
554 // Add a block as the new function entry BB. We also link it to BB0.
555 BasicBlock *NewEntry =
556 BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
557 BranchInst::Create(BB0, NewEntry);
558 EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
559 EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
560
561 // Insert the new edge between new_entry -> bb0. Without this the
562 // recalculate() call below will not actually recalculate the DT as there
563 // are no changes pending and no blocks deleted.
564 DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}});
565
566 // Changing the Entry BB requires a full recalculation.
567 DTU.recalculate(*F);
568 ASSERT_TRUE(DTU.getDomTree().verify());
569 ASSERT_TRUE(DTU.getPostDomTree().verify());
570
571 // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
572 EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
573 NewEntry->getTerminator()->eraseFromParent();
574 BranchInst::Create(BB1, NewEntry);
575 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
576
577 // Update the DTU. At this point bb0 now has no predecessors but is still a
578 // Child of F.
579 DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
580 {DominatorTree::Insert, NewEntry, BB1}});
581 DTU.flush();
582 ASSERT_TRUE(DT.verify());
583 ASSERT_TRUE(PDT.verify());
584
585 // Now remove bb0 from F.
586 ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
587 EXPECT_FALSE(DTU.isBBPendingDeletion(BB0));
588 DTU.deleteBB(BB0);
589 EXPECT_TRUE(DTU.isBBPendingDeletion(BB0));
590 ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator()));
591 EXPECT_EQ(BB0->getParent(), F);
592
593 // Perform a full recalculation of the DTU. It is not necessary here but we
594 // do this to test the case when there are no pending DT updates but there are
595 // pending deleted BBs.
596 ASSERT_TRUE(DTU.hasPendingDeletedBB());
597 DTU.recalculate(*F);
598 ASSERT_FALSE(DTU.hasPendingDeletedBB());
599 }
600
TEST(DomTreeUpdater,LazyUpdateStepTest)601 TEST(DomTreeUpdater, LazyUpdateStepTest) {
602 // This test focus on testing a DTU holding both trees applying multiple
603 // updates and DT/PDT not flushed together.
604 StringRef FuncName = "f";
605 StringRef ModuleString = R"(
606 define i32 @f(i32 %i, i32 *%p) {
607 bb0:
608 store i32 %i, i32 *%p
609 switch i32 %i, label %bb1 [
610 i32 0, label %bb1
611 i32 1, label %bb2
612 i32 2, label %bb3
613 i32 3, label %bb1
614 ]
615 bb1:
616 ret i32 1
617 bb2:
618 ret i32 2
619 bb3:
620 ret i32 3
621 }
622 )";
623 // Make the module.
624 LLVMContext Context;
625 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
626 Function *F = M->getFunction(FuncName);
627
628 // Make the DomTreeUpdater.
629 DominatorTree DT(*F);
630 PostDominatorTree PDT(*F);
631 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
632
633 ASSERT_TRUE(DTU.hasDomTree());
634 ASSERT_TRUE(DTU.hasPostDomTree());
635 ASSERT_FALSE(DTU.isEager());
636 ASSERT_TRUE(DTU.isLazy());
637 ASSERT_TRUE(DTU.getDomTree().verify());
638 ASSERT_TRUE(DTU.getPostDomTree().verify());
639 ASSERT_FALSE(DTU.hasPendingUpdates());
640
641 Function::iterator FI = F->begin();
642 BasicBlock *BB0 = &*FI++;
643 FI++;
644 BasicBlock *BB2 = &*FI++;
645 BasicBlock *BB3 = &*FI++;
646 SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
647 ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
648
649 // Delete edge bb0 -> bb3.
650 std::vector<DominatorTree::UpdateType> Updates;
651 Updates.reserve(1);
652 Updates.push_back({DominatorTree::Delete, BB0, BB3});
653
654 // CFG Change: remove edge bb0 -> bb3.
655 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 5u);
656 BB3->removePredecessor(BB0);
657 for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
658 if (i->getCaseIndex() == 2) {
659 SI->removeCase(i);
660 break;
661 }
662 }
663 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
664 // Deletion of a BasicBlock is an immediate event. We remove all uses to the
665 // contained Instructions and change the Terminator to "unreachable" when
666 // queued for deletion.
667 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
668 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
669 DTU.applyUpdates(Updates);
670
671 // Only flush DomTree.
672 ASSERT_TRUE(DTU.getDomTree().verify());
673 ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
674 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
675
676 ASSERT_EQ(BB3->getParent(), F);
677 DTU.deleteBB(BB3);
678
679 Updates.clear();
680
681 // Remove all case branch to BB2 to test Eager recalculation.
682 // Code section from llvm::ConstantFoldTerminator
683 for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
684 if (i->getCaseSuccessor() == BB2) {
685 // Remove this entry.
686 BB2->removePredecessor(BB0);
687 i = SI->removeCase(i);
688 e = SI->case_end();
689 Updates.push_back({DominatorTree::Delete, BB0, BB2});
690 } else
691 ++i;
692 }
693
694 DTU.applyUpdatesPermissive(Updates);
695 // flush PostDomTree
696 ASSERT_TRUE(DTU.getPostDomTree().verify());
697 ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
698 ASSERT_TRUE(DTU.hasPendingDomTreeUpdates());
699 // flush both trees
700 DTU.flush();
701 ASSERT_TRUE(DT.verify());
702 }
703
TEST(DomTreeUpdater,NoTreeTest)704 TEST(DomTreeUpdater, NoTreeTest) {
705 StringRef FuncName = "f";
706 StringRef ModuleString = R"(
707 define i32 @f() {
708 bb0:
709 ret i32 0
710 }
711 )";
712 // Make the module.
713 LLVMContext Context;
714 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
715 Function *F = M->getFunction(FuncName);
716
717 // Make the DTU.
718 DomTreeUpdater DTU(nullptr, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);
719 ASSERT_FALSE(DTU.hasDomTree());
720 ASSERT_FALSE(DTU.hasPostDomTree());
721 Function::iterator FI = F->begin();
722 BasicBlock *BB0 = &*FI++;
723 // Test whether PendingDeletedBB is flushed after the recalculation.
724 DTU.deleteBB(BB0);
725 ASSERT_TRUE(DTU.hasPendingDeletedBB());
726 DTU.recalculate(*F);
727 ASSERT_FALSE(DTU.hasPendingDeletedBB());
728 }
729
TEST(DomTreeUpdater,LazyUpdateDeduplicationTest)730 TEST(DomTreeUpdater, LazyUpdateDeduplicationTest) {
731 StringRef FuncName = "f";
732 StringRef ModuleString = R"(
733 define i32 @f() {
734 bb0:
735 br label %bb1
736 bb1:
737 ret i32 1
738 bb2:
739 ret i32 1
740 }
741 )";
742 // Make the module.
743 LLVMContext Context;
744 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
745 Function *F = M->getFunction(FuncName);
746
747 // Make the DTU.
748 DominatorTree DT(*F);
749 DomTreeUpdater DTU(&DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);
750 ASSERT_TRUE(DTU.getDomTree().verify());
751
752 Function::iterator FI = F->begin();
753 BasicBlock *BB0 = &*FI++;
754 BasicBlock *BB1 = &*FI++;
755 BasicBlock *BB2 = &*FI++;
756
757 // CFG Change: remove bb0 -> bb1 and add back bb0 -> bb1.
758 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
759 BB0->getTerminator()->eraseFromParent();
760 BranchInst::Create(BB1, BB0);
761 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
762
763 // Update the DTU and simulate duplicates.
764 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1},
765 {DominatorTree::Delete, BB0, BB1},
766 {DominatorTree::Insert, BB0, BB1},
767 {DominatorTree::Insert, BB0, BB1},
768 {DominatorTree::Insert, BB0, BB1}});
769
770 // The above operations result in a no-op.
771 ASSERT_FALSE(DTU.hasPendingUpdates());
772
773 // Update the DTU. Simulate an invalid update.
774 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1}});
775 ASSERT_FALSE(DTU.hasPendingUpdates());
776
777 // CFG Change: remove bb0 -> bb1.
778 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
779 BB0->getTerminator()->eraseFromParent();
780
781 // Update the DTU and simulate invalid updates.
782 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1},
783 {DominatorTree::Insert, BB0, BB1},
784 {DominatorTree::Delete, BB0, BB1},
785 {DominatorTree::Insert, BB0, BB1},
786 {DominatorTree::Insert, BB0, BB1}});
787 ASSERT_TRUE(DTU.hasPendingUpdates());
788
789 // CFG Change: add bb0 -> bb2.
790 BranchInst::Create(BB2, BB0);
791 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
792 DTU.applyUpdates({{DominatorTree::Insert, BB0, BB2}});
793 ASSERT_TRUE(DTU.getDomTree().verify());
794 }
795