1 //===- llvm/unittests/IR/DeferredDominanceTest.cpp - DDT unit tests -------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/AsmParser/Parser.h"
11 #include "llvm/IR/Constants.h"
12 #include "llvm/IR/Dominators.h"
13 #include "llvm/IR/Instructions.h"
14 #include "llvm/IR/LLVMContext.h"
15 #include "llvm/IR/Module.h"
16 #include "llvm/Support/SourceMgr.h"
17 #include "gtest/gtest.h"
21 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
22 StringRef ModuleStr) {
24 std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
25 assert(M && "Bad LLVM IR?");
29 TEST(DeferredDominance, BasicOperations) {
30 StringRef FuncName = "f";
31 StringRef ModuleString =
32 "define i32 @f(i32 %i, i32 *%p) {\n"
34 " store i32 %i, i32 *%p\n"
35 " switch i32 %i, label %bb1 [\n"
36 " i32 0, label %bb2\n"
37 " i32 1, label %bb2\n"
38 " i32 2, label %bb3\n"
49 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
50 Function *F = M->getFunction(FuncName);
51 ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";
55 DeferredDominance DDT(DT);
56 ASSERT_TRUE(DDT.flush().verify());
58 Function::iterator FI = F->begin();
59 BasicBlock *BB0 = &*FI++;
60 BasicBlock *BB1 = &*FI++;
61 BasicBlock *BB2 = &*FI++;
62 BasicBlock *BB3 = &*FI++;
64 // Test discards of invalid self-domination updates. These use the single
65 // short-hand interface but are still queued inside DDT.
66 DDT.deleteEdge(BB0, BB0);
67 DDT.insertEdge(BB1, BB1);
69 // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
70 // entries are discarded.
71 std::vector<DominatorTree::UpdateType> Updates;
73 Updates.push_back({DominatorTree::Delete, BB0, BB3});
74 Updates.push_back({DominatorTree::Delete, BB0, BB3});
76 // Unnecessary Insert: no edge bb1 -> bb2 after change to bb0.
77 Updates.push_back({DominatorTree::Insert, BB1, BB2});
78 // Unnecessary Delete: edge exists bb0 -> bb1 after change to bb0.
79 Updates.push_back({DominatorTree::Delete, BB0, BB1});
81 // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
82 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
83 BB0->getTerminator()->eraseFromParent();
84 BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
85 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
87 // Deletion of a BasicBlock is an immediate event. We remove all uses to the
88 // contained Instructions and change the Terminator to "unreachable" when
89 // queued for deletion. Its parent is still F until DDT.flush() is called. We
90 // don't defer this action because it can cause problems for other transforms
91 // or analysis as it's part of the actual CFG. We only defer updates to the
92 // DominatorTree. This code will crash if it is placed before the
93 // BranchInst::Create() call above.
94 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
95 EXPECT_FALSE(DDT.pendingDeletedBB(BB3));
97 EXPECT_TRUE(DDT.pendingDeletedBB(BB3));
98 ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
99 EXPECT_EQ(BB3->getParent(), F);
101 // Verify. Updates to DDT must be applied *after* all changes to the CFG
102 // (including block deletion).
103 DDT.applyUpdates(Updates);
104 ASSERT_TRUE(DDT.flush().verify());
107 TEST(DeferredDominance, PairedUpdate) {
108 StringRef FuncName = "f";
109 StringRef ModuleString =
110 "define i32 @f(i32 %i, i32 *%p) {\n"
112 " store i32 %i, i32 *%p\n"
113 " switch i32 %i, label %bb1 [\n"
114 " i32 0, label %bb2\n"
115 " i32 1, label %bb2\n"
124 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
125 Function *F = M->getFunction(FuncName);
126 ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";
129 DominatorTree DT(*F);
130 DeferredDominance DDT(DT);
131 ASSERT_TRUE(DDT.flush().verify());
133 Function::iterator FI = F->begin();
134 BasicBlock *BB0 = &*FI++;
135 BasicBlock *BB1 = &*FI++;
136 BasicBlock *BB2 = &*FI++;
138 // CFG Change: only edge from bb0 is bb0 -> bb1.
139 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
140 BB0->getTerminator()->eraseFromParent();
141 BranchInst::Create(BB1, BB0);
142 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
144 // Must be done after the CFG change. The applyUpdate() routine analyzes the
145 // current state of the CFG.
146 DDT.deleteEdge(BB0, BB2);
148 // CFG Change: bb0 now has bb0 -> bb1 and bb0 -> bb2.
149 // With this change no dominance has been altered from the original IR. DT
150 // doesn't care if the type of TerminatorInstruction changed, only if the
151 // unique edges have.
152 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
153 BB0->getTerminator()->eraseFromParent();
154 BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
155 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
157 // Must be done after the CFG change. The applyUpdate() routine analyzes the
158 // current state of the CFG. This DDT update pairs with the previous one and
159 // is cancelled out before ever applying updates to DT.
160 DDT.insertEdge(BB0, BB2);
162 // Test the empty DeletedBB list.
163 EXPECT_FALSE(DDT.pendingDeletedBB(BB0));
164 EXPECT_FALSE(DDT.pendingDeletedBB(BB1));
165 EXPECT_FALSE(DDT.pendingDeletedBB(BB2));
167 // The DT has no changes, this flush() simply returns a reference to the
168 // internal DT calculated at the beginning of this test.
169 ASSERT_TRUE(DDT.flush().verify());
172 TEST(DeferredDominance, ReplaceEntryBB) {
173 StringRef FuncName = "f";
174 StringRef ModuleString =
175 "define i32 @f() {\n"
183 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
184 Function *F = M->getFunction(FuncName);
185 ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";
188 DominatorTree DT(*F);
189 DeferredDominance DDT(DT);
190 ASSERT_TRUE(DDT.flush().verify());
192 Function::iterator FI = F->begin();
193 BasicBlock *BB0 = &*FI++;
194 BasicBlock *BB1 = &*FI++;
196 // Add a block as the new function entry BB. We also link it to BB0.
197 BasicBlock *NewEntry =
198 BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
199 BranchInst::Create(BB0, NewEntry);
200 EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
201 EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
203 // Insert the new edge between new_eentry -> bb0. Without this the
204 // recalculate() call below will not actually recalculate the DT as there
205 // are no changes pending and no blocks deleted.
206 DDT.insertEdge(NewEntry, BB0);
208 // Changing the Entry BB requires a full recalulation.
210 ASSERT_TRUE(DDT.flush().verify());
212 // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
213 EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
214 NewEntry->getTerminator()->eraseFromParent();
215 BranchInst::Create(BB1, NewEntry);
216 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
218 // Update the DDT. At this point bb0 now has no predecessors but is still a
220 DDT.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
221 {DominatorTree::Insert, NewEntry, BB1}});
222 ASSERT_TRUE(DDT.flush().verify());
224 // Now remove bb0 from F.
225 ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
226 EXPECT_FALSE(DDT.pendingDeletedBB(BB0));
228 EXPECT_TRUE(DDT.pendingDeletedBB(BB0));
229 ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator()));
230 EXPECT_EQ(BB0->getParent(), F);
232 // Perform a full recalculation of the DDT. It is not necessary here but we
233 // do this to test the case when there are no pending DT updates but there are
234 // pending deleted BBs.
236 ASSERT_TRUE(DDT.flush().verify());
239 TEST(DeferredDominance, InheritedPreds) {
240 StringRef FuncName = "f";
241 StringRef ModuleString =
242 "define i32 @f(i32 %i, i32 *%p) {\n"
244 " store i32 %i, i32 *%p\n"
245 " switch i32 %i, label %bb1 [\n"
246 " i32 2, label %bb2\n"
247 " i32 3, label %bb3\n"
258 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
259 Function *F = M->getFunction(FuncName);
260 ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";
263 DominatorTree DT(*F);
264 DeferredDominance DDT(DT);
265 ASSERT_TRUE(DDT.flush().verify());
267 Function::iterator FI = F->begin();
268 BasicBlock *BB0 = &*FI++;
269 BasicBlock *BB1 = &*FI++;
270 BasicBlock *BB2 = &*FI++;
271 BasicBlock *BB3 = &*FI++;
273 // There are several CFG locations where we have:
277 // +> curr <+ converted into: pred1..predN curr
282 // There is a specific shape of this we have to be careful of:
286 // |+> curr <+ converted into: pred1..predN curr
291 // While the final CFG form is functionally identical the updates to
292 // DDT are not. In the first case we must have DDT.insertEdge(Pred1, Succ)
293 // while in the latter case we must *NOT* have DDT.insertEdge(Pred1, Succ).
295 // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to
297 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
298 BB0->getTerminator()->eraseFromParent();
299 BranchInst::Create(BB1, BB3, ConstantInt::getTrue(F->getContext()), BB0);
300 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
302 // Remove bb2 from F. This has to happen before the call to applyUpdates() for
303 // DDT to detect there is no longer an edge between bb2 -> bb3. The deleteBB()
304 // method converts bb2's TI into "unreachable".
305 ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));
306 EXPECT_FALSE(DDT.pendingDeletedBB(BB2));
308 EXPECT_TRUE(DDT.pendingDeletedBB(BB2));
309 ASSERT_TRUE(isa<UnreachableInst>(BB2->getTerminator()));
310 EXPECT_EQ(BB2->getParent(), F);
312 // Queue up the DDT updates.
313 std::vector<DominatorTree::UpdateType> Updates;
315 Updates.push_back({DominatorTree::Delete, BB0, BB2});
316 Updates.push_back({DominatorTree::Delete, BB2, BB3});
318 // Handle the specific shape case next.
319 // CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1.
320 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
321 BB0->getTerminator()->eraseFromParent();
322 BranchInst::Create(BB3, BB0);
323 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
325 // Remove bb1 from F. This has to happen before the call to applyUpdates() for
326 // DDT to detect there is no longer an edge between bb1 -> bb3. The deleteBB()
327 // method converts bb1's TI into "unreachable".
328 ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
329 EXPECT_FALSE(DDT.pendingDeletedBB(BB1));
331 EXPECT_TRUE(DDT.pendingDeletedBB(BB1));
332 ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator()));
333 EXPECT_EQ(BB1->getParent(), F);
335 // Update the DDT. In this case we don't call DDT.insertEdge(BB0, BB3) because
336 // the edge previously existed at the start of this test when DT was first
338 Updates.push_back({DominatorTree::Delete, BB0, BB1});
339 Updates.push_back({DominatorTree::Delete, BB1, BB3});
341 // Verify everything.
342 DDT.applyUpdates(Updates);
343 ASSERT_TRUE(DDT.flush().verify());