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