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 | |
23 | static 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 | |
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, 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 | |
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, 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 | |
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, 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 | |
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, 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 | |
427 | TEST(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 | |
519 | TEST(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 | |
596 | TEST(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 | |
699 | TEST(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 | |
725 | TEST(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 | |