Debian Codegraph @

llvm-project/llvm/unittests/IR/BasicBlockTest.cpp

raw
1 //===- llvm/unittest/IR/BasicBlockTest.cpp - BasicBlock 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/IR/BasicBlock.h"
10 #include "llvm/ADT/STLExtras.h"
11 #include "llvm/AsmParser/Parser.h"
12 #include "llvm/IR/Function.h"
13 #include "llvm/IR/IRBuilder.h"
14 #include "llvm/IR/Instructions.h"
15 #include "llvm/IR/LLVMContext.h"
16 #include "llvm/IR/Module.h"
17 #include "llvm/IR/NoFolder.h"
18 #include "llvm/IR/Verifier.h"
19 #include "llvm/Support/SourceMgr.h"
20 #include "gmock/gmock-matchers.h"
21 #include "gtest/gtest.h"
22 #include <memory>
23
24 namespace llvm {
25 namespace {
26
27 TEST(BasicBlockTest, PhiRange) {
28 LLVMContext Context;
29
30 // Create the main block.
31 std::unique_ptr<BasicBlock> BB(BasicBlock::Create(Context));
32
33 // Create some predecessors of it.
34 std::unique_ptr<BasicBlock> BB1(BasicBlock::Create(Context));
35 BranchInst::Create(BB.get(), BB1.get());
36 std::unique_ptr<BasicBlock> BB2(BasicBlock::Create(Context));
37 BranchInst::Create(BB.get(), BB2.get());
38
39 // Make sure this doesn't crash if there are no phis.
40 int PhiCount = 0;
41 for (auto &PN : BB->phis()) {
42 (void)PN;
43 PhiCount++;
44 }
45 ASSERT_EQ(PhiCount, 0) << "empty block should have no phis";
46
47 // Make it a cycle.
48 auto *BI = BranchInst::Create(BB.get(), BB.get());
49
50 // Now insert some PHI nodes.
51 auto *Int32Ty = Type::getInt32Ty(Context);
52 auto *P1 = PHINode::Create(Int32Ty, /*NumReservedValues*/ 3, "phi.1", BI);
53 auto *P2 = PHINode::Create(Int32Ty, /*NumReservedValues*/ 3, "phi.2", BI);
54 auto *P3 = PHINode::Create(Int32Ty, /*NumReservedValues*/ 3, "phi.3", BI);
55
56 // Some non-PHI nodes.
57 auto *Sum = BinaryOperator::CreateAdd(P1, P2, "sum", BI);
58
59 // Now wire up the incoming values that are interesting.
60 P1->addIncoming(P2, BB.get());
61 P2->addIncoming(P1, BB.get());
62 P3->addIncoming(Sum, BB.get());
63
64 // Finally, let's iterate them, which is the thing we're trying to test.
65 // We'll use this to wire up the rest of the incoming values.
66 for (auto &PN : BB->phis()) {
67 PN.addIncoming(UndefValue::get(Int32Ty), BB1.get());
68 PN.addIncoming(UndefValue::get(Int32Ty), BB2.get());
69 }
70
71 // Test that we can use const iterators and generally that the iterators
72 // behave like iterators.
73 BasicBlock::const_phi_iterator CI;
74 CI = BB->phis().begin();
75 EXPECT_NE(CI, BB->phis().end());
76
77 // Test that filtering iterators work with basic blocks.
78 auto isPhi = [](Instruction &I) { return isa<PHINode>(&I); };
79 auto Phis = make_filter_range(*BB, isPhi);
80 auto ReversedPhis = reverse(make_filter_range(*BB, isPhi));
81 EXPECT_EQ(std::distance(Phis.begin(), Phis.end()), 3);
82 EXPECT_EQ(&*Phis.begin(), P1);
83 EXPECT_EQ(std::distance(ReversedPhis.begin(), ReversedPhis.end()), 3);
84 EXPECT_EQ(&*ReversedPhis.begin(), P3);
85
86 // And iterate a const range.
87 for (const auto &PN : const_cast<const BasicBlock *>(BB.get())->phis()) {
88 EXPECT_EQ(BB.get(), PN.getIncomingBlock(0));
89 EXPECT_EQ(BB1.get(), PN.getIncomingBlock(1));
90 EXPECT_EQ(BB2.get(), PN.getIncomingBlock(2));
91 }
92 }
93
94 #define CHECK_ITERATORS(Range1, Range2) \
95 EXPECT_EQ(std::distance(Range1.begin(), Range1.end()), \
96 std::distance(Range2.begin(), Range2.end())); \
97 for (auto Pair : zip(Range1, Range2)) \
98 EXPECT_EQ(&std::get<0>(Pair), std::get<1>(Pair));
99
100 TEST(BasicBlockTest, TestInstructionsWithoutDebug) {
101 LLVMContext Ctx;
102
103 Module *M = new Module("MyModule", Ctx);
104 Type *ArgTy1[] = {Type::getInt32PtrTy(Ctx)};
105 FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), ArgTy1, false);
106 Argument *V = new Argument(Type::getInt32Ty(Ctx));
107 Function *F = Function::Create(FT, Function::ExternalLinkage, "", M);
108
109 Function *DbgAddr = Intrinsic::getDeclaration(M, Intrinsic::dbg_addr);
110 Function *DbgDeclare = Intrinsic::getDeclaration(M, Intrinsic::dbg_declare);
111 Function *DbgValue = Intrinsic::getDeclaration(M, Intrinsic::dbg_value);
112 Value *DIV = MetadataAsValue::get(Ctx, (Metadata *)nullptr);
113 SmallVector<Value *, 3> Args = {DIV, DIV, DIV};
114
115 BasicBlock *BB1 = BasicBlock::Create(Ctx, "", F);
116 const BasicBlock *BBConst = BB1;
117 IRBuilder<> Builder1(BB1);
118
119 AllocaInst *Var = Builder1.CreateAlloca(Builder1.getInt8Ty());
120 Builder1.CreateCall(DbgValue, Args);
121 Instruction *AddInst = cast<Instruction>(Builder1.CreateAdd(V, V));
122 Instruction *MulInst = cast<Instruction>(Builder1.CreateMul(AddInst, V));
123 Builder1.CreateCall(DbgDeclare, Args);
124 Instruction *SubInst = cast<Instruction>(Builder1.CreateSub(MulInst, V));
125 Builder1.CreateCall(DbgAddr, Args);
126
127 SmallVector<Instruction *, 4> Exp = {Var, AddInst, MulInst, SubInst};
128 CHECK_ITERATORS(BB1->instructionsWithoutDebug(), Exp);
129 CHECK_ITERATORS(BBConst->instructionsWithoutDebug(), Exp);
130
131 EXPECT_EQ(static_cast<size_t>(BB1->sizeWithoutDebug()), Exp.size());
132 EXPECT_EQ(static_cast<size_t>(BBConst->sizeWithoutDebug()), Exp.size());
133
134 delete M;
135 delete V;
136 }
137
138 TEST(BasicBlockTest, ComesBefore) {
139 const char *ModuleString = R"(define i32 @f(i32 %x) {
140 %add = add i32 %x, 42
141 ret i32 %add
142 })";
143 LLVMContext Ctx;
144 SMDiagnostic Err;
145 auto M = parseAssemblyString(ModuleString, Err, Ctx);
146 ASSERT_TRUE(M.get());
147
148 Function *F = M->getFunction("f");
149 BasicBlock &BB = F->front();
150 BasicBlock::iterator I = BB.begin();
151 Instruction *Add = &*I++;
152 Instruction *Ret = &*I++;
153
154 // Intentionally duplicated to verify cached and uncached are the same.
155 EXPECT_FALSE(BB.isInstrOrderValid());
156 EXPECT_FALSE(Add->comesBefore(Add));
157 EXPECT_TRUE(BB.isInstrOrderValid());
158 EXPECT_FALSE(Add->comesBefore(Add));
159 BB.invalidateOrders();
160 EXPECT_FALSE(BB.isInstrOrderValid());
161 EXPECT_TRUE(Add->comesBefore(Ret));
162 EXPECT_TRUE(BB.isInstrOrderValid());
163 EXPECT_TRUE(Add->comesBefore(Ret));
164 BB.invalidateOrders();
165 EXPECT_FALSE(Ret->comesBefore(Add));
166 EXPECT_FALSE(Ret->comesBefore(Add));
167 BB.invalidateOrders();
168 EXPECT_FALSE(Ret->comesBefore(Ret));
169 EXPECT_FALSE(Ret->comesBefore(Ret));
170 }
171
172 class InstrOrderInvalidationTest : public ::testing::Test {
173 protected:
174 void SetUp() override {
175 M.reset(new Module("MyModule", Ctx));
176 Nop = Intrinsic::getDeclaration(M.get(), Intrinsic::donothing);
177 FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), {}, false);
178 Function *F = Function::Create(FT, Function::ExternalLinkage, "foo", *M);
179 BB = BasicBlock::Create(Ctx, "entry", F);
180
181 IRBuilder<> Builder(BB);
182 I1 = Builder.CreateCall(Nop);
183 I2 = Builder.CreateCall(Nop);
184 I3 = Builder.CreateCall(Nop);
185 Ret = Builder.CreateRetVoid();
186 }
187
188 LLVMContext Ctx;
189 std::unique_ptr<Module> M;
190 Function *Nop = nullptr;
191 BasicBlock *BB = nullptr;
192 Instruction *I1 = nullptr;
193 Instruction *I2 = nullptr;
194 Instruction *I3 = nullptr;
195 Instruction *Ret = nullptr;
196 };
197
198 TEST_F(InstrOrderInvalidationTest, InsertInvalidation) {
199 EXPECT_FALSE(BB->isInstrOrderValid());
200 EXPECT_TRUE(I1->comesBefore(I2));
201 EXPECT_TRUE(BB->isInstrOrderValid());
202 EXPECT_TRUE(I2->comesBefore(I3));
203 EXPECT_TRUE(I3->comesBefore(Ret));
204 EXPECT_TRUE(BB->isInstrOrderValid());
205
206 // Invalidate orders.
207 IRBuilder<> Builder(BB, I2->getIterator());
208 Instruction *I1a = Builder.CreateCall(Nop);
209 EXPECT_FALSE(BB->isInstrOrderValid());
210 EXPECT_TRUE(I1->comesBefore(I1a));
211 EXPECT_TRUE(BB->isInstrOrderValid());
212 EXPECT_TRUE(I1a->comesBefore(I2));
213 EXPECT_TRUE(I2->comesBefore(I3));
214 EXPECT_TRUE(I3->comesBefore(Ret));
215 EXPECT_TRUE(BB->isInstrOrderValid());
216 }
217
218 TEST_F(InstrOrderInvalidationTest, SpliceInvalidation) {
219 EXPECT_TRUE(I1->comesBefore(I2));
220 EXPECT_TRUE(I2->comesBefore(I3));
221 EXPECT_TRUE(I3->comesBefore(Ret));
222 EXPECT_TRUE(BB->isInstrOrderValid());
223
224 // Use Instruction::moveBefore, which uses splice.
225 I2->moveBefore(I1);
226 EXPECT_FALSE(BB->isInstrOrderValid());
227
228 EXPECT_TRUE(I2->comesBefore(I1));
229 EXPECT_TRUE(I1->comesBefore(I3));
230 EXPECT_TRUE(I3->comesBefore(Ret));
231 EXPECT_TRUE(BB->isInstrOrderValid());
232 }
233
234 TEST_F(InstrOrderInvalidationTest, RemoveNoInvalidation) {
235 // Cache the instruction order.
236 EXPECT_FALSE(BB->isInstrOrderValid());
237 EXPECT_TRUE(I1->comesBefore(I2));
238 EXPECT_TRUE(BB->isInstrOrderValid());
239
240 // Removing does not invalidate instruction order.
241 I2->removeFromParent();
242 I2->deleteValue();
243 I2 = nullptr;
244 EXPECT_TRUE(BB->isInstrOrderValid());
245 EXPECT_TRUE(I1->comesBefore(I3));
246 EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator());
247 }
248
249 TEST_F(InstrOrderInvalidationTest, EraseNoInvalidation) {
250 // Cache the instruction order.
251 EXPECT_FALSE(BB->isInstrOrderValid());
252 EXPECT_TRUE(I1->comesBefore(I2));
253 EXPECT_TRUE(BB->isInstrOrderValid());
254
255 // Removing does not invalidate instruction order.
256 I2->eraseFromParent();
257 I2 = nullptr;
258 EXPECT_TRUE(BB->isInstrOrderValid());
259 EXPECT_TRUE(I1->comesBefore(I3));
260 EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator());
261 }
262
263 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
264 SMDiagnostic Err;
265 std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
266 if (!Mod)
267 Err.print(__FILE__, errs());
268 return Mod;
269 }
270
271 TEST(BasicBlockTest, SpliceFromBB) {
272 LLVMContext Ctx;
273 std::unique_ptr<Module> M = parseIR(Ctx, R"(
274 define void @f(i32 %a) {
275 from:
276 %fromInstr1 = add i32 %a, %a
277 %fromInstr2 = sub i32 %a, %a
278 br label %to
279
280 to:
281 %toInstr1 = mul i32 %a, %a
282 %toInstr2 = sdiv i32 %a, %a
283 ret void
284 }
285 )");
286 Function *F = &*M->begin();
287 auto BBIt = F->begin();
288 BasicBlock *FromBB = &*BBIt++;
289 BasicBlock *ToBB = &*BBIt++;
290
291 auto FromBBIt = FromBB->begin();
292 Instruction *FromI1 = &*FromBBIt++;
293 Instruction *FromI2 = &*FromBBIt++;
294 Instruction *FromBr = &*FromBBIt++;
295
296 auto ToBBIt = ToBB->begin();
297 Instruction *ToI1 = &*ToBBIt++;
298 Instruction *ToI2 = &*ToBBIt++;
299 Instruction *ToRet = &*ToBBIt++;
300 ToBB->splice(ToI1->getIterator(), FromBB);
301
302 EXPECT_TRUE(FromBB->empty());
303
304 auto It = ToBB->begin();
305 EXPECT_EQ(&*It++, FromI1);
306 EXPECT_EQ(&*It++, FromI2);
307 EXPECT_EQ(&*It++, FromBr);
308 EXPECT_EQ(&*It++, ToI1);
309 EXPECT_EQ(&*It++, ToI2);
310 EXPECT_EQ(&*It++, ToRet);
311 }
312
313 TEST(BasicBlockTest, SpliceOneInstr) {
314 LLVMContext Ctx;
315 std::unique_ptr<Module> M = parseIR(Ctx, R"(
316 define void @f(i32 %a) {
317 from:
318 %fromInstr1 = add i32 %a, %a
319 %fromInstr2 = sub i32 %a, %a
320 br label %to
321
322 to:
323 %toInstr1 = mul i32 %a, %a
324 %toInstr2 = sdiv i32 %a, %a
325 ret void
326 }
327 )");
328 Function *F = &*M->begin();
329 auto BBIt = F->begin();
330 BasicBlock *FromBB = &*BBIt++;
331 BasicBlock *ToBB = &*BBIt++;
332
333 auto FromBBIt = FromBB->begin();
334 Instruction *FromI1 = &*FromBBIt++;
335 Instruction *FromI2 = &*FromBBIt++;
336 Instruction *FromBr = &*FromBBIt++;
337
338 auto ToBBIt = ToBB->begin();
339 Instruction *ToI1 = &*ToBBIt++;
340 Instruction *ToI2 = &*ToBBIt++;
341 Instruction *ToRet = &*ToBBIt++;
342 ToBB->splice(ToI1->getIterator(), FromBB, FromI2->getIterator());
343
344 EXPECT_EQ(FromBB->size(), 2u);
345 EXPECT_EQ(ToBB->size(), 4u);
346
347 auto It = FromBB->begin();
348 EXPECT_EQ(&*It++, FromI1);
349 EXPECT_EQ(&*It++, FromBr);
350
351 It = ToBB->begin();
352 EXPECT_EQ(&*It++, FromI2);
353 EXPECT_EQ(&*It++, ToI1);
354 EXPECT_EQ(&*It++, ToI2);
355 EXPECT_EQ(&*It++, ToRet);
356 }
357
358 TEST(BasicBlockTest, SpliceOneInstrWhenFromIsSameAsTo) {
359 LLVMContext Ctx;
360 std::unique_ptr<Module> M = parseIR(Ctx, R"(
361 define void @f(i32 %a) {
362 bb:
363 %instr1 = add i32 %a, %a
364 %instr2 = sub i32 %a, %a
365 ret void
366 }
367 )");
368 Function *F = &*M->begin();
369 auto BBIt = F->begin();
370 BasicBlock *BB = &*BBIt++;
371
372 auto It = BB->begin();
373 Instruction *Instr1 = &*It++;
374 Instruction *Instr2 = &*It++;
375 Instruction *Ret = &*It++;
376
377 // According to ilist's splice() a single-element splice where dst == src
378 // should be a noop.
379 BB->splice(Instr1->getIterator(), BB, Instr1->getIterator());
380
381 It = BB->begin();
382 EXPECT_EQ(&*It++, Instr1);
383 EXPECT_EQ(&*It++, Instr2);
384 EXPECT_EQ(&*It++, Ret);
385 EXPECT_EQ(BB->size(), 3u);
386 }
387
388 TEST(BasicBlockTest, SpliceLastInstr) {
389 LLVMContext Ctx;
390 std::unique_ptr<Module> M = parseIR(Ctx, R"(
391 define void @f(i32 %a) {
392 from:
393 %fromInstr1 = add i32 %a, %a
394 %fromInstr2 = sub i32 %a, %a
395 br label %to
396
397 to:
398 %toInstr1 = mul i32 %a, %a
399 %toInstr2 = sdiv i32 %a, %a
400 ret void
401 }
402 )");
403 Function *F = &*M->begin();
404 auto BBIt = F->begin();
405 BasicBlock *FromBB = &*BBIt++;
406 BasicBlock *ToBB = &*BBIt++;
407
408 auto FromBBIt = FromBB->begin();
409 Instruction *FromI1 = &*FromBBIt++;
410 Instruction *FromI2 = &*FromBBIt++;
411 Instruction *FromBr = &*FromBBIt++;
412
413 auto ToBBIt = ToBB->begin();
414 Instruction *ToI1 = &*ToBBIt++;
415 Instruction *ToI2 = &*ToBBIt++;
416 Instruction *ToRet = &*ToBBIt++;
417 ToBB->splice(ToI1->getIterator(), FromBB, FromI2->getIterator(),
418 FromBr->getIterator());
419
420 EXPECT_EQ(FromBB->size(), 2u);
421 auto It = FromBB->begin();
422 EXPECT_EQ(&*It++, FromI1);
423 EXPECT_EQ(&*It++, FromBr);
424
425 EXPECT_EQ(ToBB->size(), 4u);
426 It = ToBB->begin();
427 EXPECT_EQ(&*It++, FromI2);
428 EXPECT_EQ(&*It++, ToI1);
429 EXPECT_EQ(&*It++, ToI2);
430 EXPECT_EQ(&*It++, ToRet);
431 }
432
433 TEST(BasicBlockTest, SpliceInstrRange) {
434 LLVMContext Ctx;
435 std::unique_ptr<Module> M = parseIR(Ctx, R"(
436 define void @f(i32 %a) {
437 from:
438 %fromInstr1 = add i32 %a, %a
439 %fromInstr2 = sub i32 %a, %a
440 br label %to
441
442 to:
443 %toInstr1 = mul i32 %a, %a
444 %toInstr2 = sdiv i32 %a, %a
445 ret void
446 }
447 )");
448 Function *F = &*M->begin();
449 auto BBIt = F->begin();
450 BasicBlock *FromBB = &*BBIt++;
451 BasicBlock *ToBB = &*BBIt++;
452
453 auto FromBBIt = FromBB->begin();
454 Instruction *FromI1 = &*FromBBIt++;
455 Instruction *FromI2 = &*FromBBIt++;
456 Instruction *FromBr = &*FromBBIt++;
457
458 auto ToBBIt = ToBB->begin();
459 Instruction *ToI1 = &*ToBBIt++;
460 Instruction *ToI2 = &*ToBBIt++;
461 Instruction *ToRet = &*ToBBIt++;
462 ToBB->splice(ToI2->getIterator(), FromBB, FromBB->begin(), FromBB->end());
463
464 EXPECT_EQ(FromBB->size(), 0u);
465
466 EXPECT_EQ(ToBB->size(), 6u);
467 auto It = ToBB->begin();
468 EXPECT_EQ(&*It++, ToI1);
469 EXPECT_EQ(&*It++, FromI1);
470 EXPECT_EQ(&*It++, FromI2);
471 EXPECT_EQ(&*It++, FromBr);
472 EXPECT_EQ(&*It++, ToI2);
473 EXPECT_EQ(&*It++, ToRet);
474 }
475
476 #ifdef EXPENSIVE_CHECKS
477 TEST(BasicBlockTest, SpliceEndBeforeBegin) {
478 LLVMContext Ctx;
479 std::unique_ptr<Module> M = parseIR(Ctx, R"(
480 define void @f(i32 %a) {
481 from:
482 %fromInstr1 = add i32 %a, %a
483 %fromInstr2 = sub i32 %a, %a
484 br label %to
485
486 to:
487 %toInstr1 = mul i32 %a, %a
488 %toInstr2 = sdiv i32 %a, %a
489 ret void
490 }
491 )");
492 Function *F = &*M->begin();
493 auto BBIt = F->begin();
494 BasicBlock *FromBB = &*BBIt++;
495 BasicBlock *ToBB = &*BBIt++;
496
497 auto FromBBIt = FromBB->begin();
498 Instruction *FromI1 = &*FromBBIt++;
499 Instruction *FromI2 = &*FromBBIt++;
500
501 auto ToBBIt = ToBB->begin();
502 Instruction *ToI2 = &*ToBBIt++;
503
504 EXPECT_DEATH(ToBB->splice(ToI2->getIterator(), FromBB, FromI2->getIterator(),
505 FromI1->getIterator()),
506 "FromBeginIt not before FromEndIt!");
507 }
508 #endif //EXPENSIVE_CHECKS
509
510 TEST(BasicBlockTest, EraseRange) {
511 LLVMContext Ctx;
512 std::unique_ptr<Module> M = parseIR(Ctx, R"(
513 define void @f(i32 %a) {
514 bb0:
515 %instr1 = add i32 %a, %a
516 %instr2 = sub i32 %a, %a
517 ret void
518 }
519 )");
520 Function *F = &*M->begin();
521
522 auto BB0It = F->begin();
523 BasicBlock *BB0 = &*BB0It;
524
525 auto It = BB0->begin();
526 Instruction *Instr1 = &*It++;
527 Instruction *Instr2 = &*It++;
528
529 EXPECT_EQ(BB0->size(), 3u);
530
531 // Erase no instruction
532 BB0->erase(Instr1->getIterator(), Instr1->getIterator());
533 EXPECT_EQ(BB0->size(), 3u);
534
535 // Erase %instr1
536 BB0->erase(Instr1->getIterator(), Instr2->getIterator());
537 EXPECT_EQ(BB0->size(), 2u);
538 EXPECT_EQ(&*BB0->begin(), Instr2);
539
540 // Erase all instructions
541 BB0->erase(BB0->begin(), BB0->end());
542 EXPECT_TRUE(BB0->empty());
543 }
544 } // End anonymous namespace.
545 } // End llvm namespace.