588 lines · cpp
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-exception6//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 24namespace llvm {25namespace {26 27TEST(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",53 BI->getIterator());54 auto *P2 = PHINode::Create(Int32Ty, /*NumReservedValues*/ 3, "phi.2",55 BI->getIterator());56 auto *P3 = PHINode::Create(Int32Ty, /*NumReservedValues*/ 3, "phi.3",57 BI->getIterator());58 59 // Some non-PHI nodes.60 auto *Sum = BinaryOperator::CreateAdd(P1, P2, "sum", BI->getIterator());61 62 // Now wire up the incoming values that are interesting.63 P1->addIncoming(P2, BB.get());64 P2->addIncoming(P1, BB.get());65 P3->addIncoming(Sum, BB.get());66 67 // Finally, let's iterate them, which is the thing we're trying to test.68 // We'll use this to wire up the rest of the incoming values.69 for (auto &PN : BB->phis()) {70 PN.addIncoming(PoisonValue::get(Int32Ty), BB1.get());71 PN.addIncoming(PoisonValue::get(Int32Ty), BB2.get());72 }73 74 // Test that we can use const iterators and generally that the iterators75 // behave like iterators.76 BasicBlock::const_phi_iterator CI;77 CI = BB->phis().begin();78 EXPECT_NE(CI, BB->phis().end());79 80 // Test that filtering iterators work with basic blocks.81 auto isPhi = [](Instruction &I) { return isa<PHINode>(&I); };82 auto Phis = make_filter_range(*BB, isPhi);83 auto ReversedPhis = reverse(make_filter_range(*BB, isPhi));84 EXPECT_EQ(std::distance(Phis.begin(), Phis.end()), 3);85 EXPECT_EQ(&*Phis.begin(), P1);86 EXPECT_EQ(std::distance(ReversedPhis.begin(), ReversedPhis.end()), 3);87 EXPECT_EQ(&*ReversedPhis.begin(), P3);88 89 // And iterate a const range.90 for (const auto &PN : const_cast<const BasicBlock *>(BB.get())->phis()) {91 EXPECT_EQ(BB.get(), PN.getIncomingBlock(0));92 EXPECT_EQ(BB1.get(), PN.getIncomingBlock(1));93 EXPECT_EQ(BB2.get(), PN.getIncomingBlock(2));94 }95}96 97#define CHECK_ITERATORS(Range1, Range2) \98 EXPECT_EQ(std::distance(Range1.begin(), Range1.end()), \99 std::distance(Range2.begin(), Range2.end())); \100 for (auto Pair : zip(Range1, Range2)) \101 EXPECT_EQ(&std::get<0>(Pair), std::get<1>(Pair));102 103TEST(BasicBlockTest, TestInstructionsWithoutDebug) {104 LLVMContext Ctx;105 106 Module *M = new Module("MyModule", Ctx);107 Type *ArgTy1[] = {PointerType::getUnqual(Ctx)};108 FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), ArgTy1, false);109 Argument *V = new Argument(Type::getInt32Ty(Ctx));110 Function *F = Function::Create(FT, Function::ExternalLinkage, "", M);111 112 Function *DbgDeclare =113 Intrinsic::getOrInsertDeclaration(M, Intrinsic::dbg_declare);114 Function *DbgValue =115 Intrinsic::getOrInsertDeclaration(M, Intrinsic::dbg_value);116 Value *DIV = MetadataAsValue::get(Ctx, (Metadata *)nullptr);117 SmallVector<Value *, 3> Args = {DIV, DIV, DIV};118 119 BasicBlock *BB1 = BasicBlock::Create(Ctx, "", F);120 const BasicBlock *BBConst = BB1;121 IRBuilder<> Builder1(BB1);122 123 AllocaInst *Var = Builder1.CreateAlloca(Builder1.getInt8Ty());124 Builder1.CreateCall(DbgValue, Args);125 Instruction *AddInst = cast<Instruction>(Builder1.CreateAdd(V, V));126 Instruction *MulInst = cast<Instruction>(Builder1.CreateMul(AddInst, V));127 Builder1.CreateCall(DbgDeclare, Args);128 Instruction *SubInst = cast<Instruction>(Builder1.CreateSub(MulInst, V));129 130 SmallVector<Instruction *, 4> Exp = {Var, AddInst, MulInst, SubInst};131 CHECK_ITERATORS(BB1->instructionsWithoutDebug(), Exp);132 CHECK_ITERATORS(BBConst->instructionsWithoutDebug(), Exp);133 134 EXPECT_EQ(static_cast<size_t>(BB1->sizeWithoutDebug()), Exp.size());135 EXPECT_EQ(static_cast<size_t>(BBConst->sizeWithoutDebug()), Exp.size());136 137 delete M;138 delete V;139}140 141TEST(BasicBlockTest, ComesBefore) {142 const char *ModuleString = R"(define i32 @f(i32 %x) {143 %add = add i32 %x, 42144 ret i32 %add145 })";146 LLVMContext Ctx;147 SMDiagnostic Err;148 auto M = parseAssemblyString(ModuleString, Err, Ctx);149 ASSERT_TRUE(M.get());150 151 Function *F = M->getFunction("f");152 BasicBlock &BB = F->front();153 BasicBlock::iterator I = BB.begin();154 Instruction *Add = &*I++;155 Instruction *Ret = &*I++;156 157 // Intentionally duplicated to verify cached and uncached are the same.158 EXPECT_FALSE(BB.isInstrOrderValid());159 EXPECT_FALSE(Add->comesBefore(Add));160 EXPECT_TRUE(BB.isInstrOrderValid());161 EXPECT_FALSE(Add->comesBefore(Add));162 BB.invalidateOrders();163 EXPECT_FALSE(BB.isInstrOrderValid());164 EXPECT_TRUE(Add->comesBefore(Ret));165 EXPECT_TRUE(BB.isInstrOrderValid());166 EXPECT_TRUE(Add->comesBefore(Ret));167 BB.invalidateOrders();168 EXPECT_FALSE(Ret->comesBefore(Add));169 EXPECT_FALSE(Ret->comesBefore(Add));170 BB.invalidateOrders();171 EXPECT_FALSE(Ret->comesBefore(Ret));172 EXPECT_FALSE(Ret->comesBefore(Ret));173}174 175class InstrOrderInvalidationTest : public ::testing::Test {176protected:177 void SetUp() override {178 M.reset(new Module("MyModule", Ctx));179 Nop = Intrinsic::getOrInsertDeclaration(M.get(), Intrinsic::donothing);180 FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), {}, false);181 Function *F = Function::Create(FT, Function::ExternalLinkage, "foo", *M);182 BB = BasicBlock::Create(Ctx, "entry", F);183 184 IRBuilder<> Builder(BB);185 I1 = Builder.CreateCall(Nop);186 I2 = Builder.CreateCall(Nop);187 I3 = Builder.CreateCall(Nop);188 Ret = Builder.CreateRetVoid();189 }190 191 LLVMContext Ctx;192 std::unique_ptr<Module> M;193 Function *Nop = nullptr;194 BasicBlock *BB = nullptr;195 Instruction *I1 = nullptr;196 Instruction *I2 = nullptr;197 Instruction *I3 = nullptr;198 Instruction *Ret = nullptr;199};200 201TEST_F(InstrOrderInvalidationTest, InsertInvalidation) {202 EXPECT_FALSE(BB->isInstrOrderValid());203 EXPECT_TRUE(I1->comesBefore(I2));204 EXPECT_TRUE(BB->isInstrOrderValid());205 EXPECT_TRUE(I2->comesBefore(I3));206 EXPECT_TRUE(I3->comesBefore(Ret));207 EXPECT_TRUE(BB->isInstrOrderValid());208 209 // Invalidate orders.210 IRBuilder<> Builder(BB, I2->getIterator());211 Instruction *I1a = Builder.CreateCall(Nop);212 EXPECT_FALSE(BB->isInstrOrderValid());213 EXPECT_TRUE(I1->comesBefore(I1a));214 EXPECT_TRUE(BB->isInstrOrderValid());215 EXPECT_TRUE(I1a->comesBefore(I2));216 EXPECT_TRUE(I2->comesBefore(I3));217 EXPECT_TRUE(I3->comesBefore(Ret));218 EXPECT_TRUE(BB->isInstrOrderValid());219}220 221TEST_F(InstrOrderInvalidationTest, SpliceInvalidation) {222 EXPECT_TRUE(I1->comesBefore(I2));223 EXPECT_TRUE(I2->comesBefore(I3));224 EXPECT_TRUE(I3->comesBefore(Ret));225 EXPECT_TRUE(BB->isInstrOrderValid());226 227 // Use Instruction::moveBefore, which uses splice.228 I2->moveBefore(I1->getIterator());229 EXPECT_FALSE(BB->isInstrOrderValid());230 231 EXPECT_TRUE(I2->comesBefore(I1));232 EXPECT_TRUE(I1->comesBefore(I3));233 EXPECT_TRUE(I3->comesBefore(Ret));234 EXPECT_TRUE(BB->isInstrOrderValid());235}236 237TEST_F(InstrOrderInvalidationTest, RemoveNoInvalidation) {238 // Cache the instruction order.239 EXPECT_FALSE(BB->isInstrOrderValid());240 EXPECT_TRUE(I1->comesBefore(I2));241 EXPECT_TRUE(BB->isInstrOrderValid());242 243 // Removing does not invalidate instruction order.244 I2->removeFromParent();245 I2->deleteValue();246 I2 = nullptr;247 EXPECT_TRUE(BB->isInstrOrderValid());248 EXPECT_TRUE(I1->comesBefore(I3));249 EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator());250}251 252TEST_F(InstrOrderInvalidationTest, EraseNoInvalidation) {253 // Cache the instruction order.254 EXPECT_FALSE(BB->isInstrOrderValid());255 EXPECT_TRUE(I1->comesBefore(I2));256 EXPECT_TRUE(BB->isInstrOrderValid());257 258 // Removing does not invalidate instruction order.259 I2->eraseFromParent();260 I2 = nullptr;261 EXPECT_TRUE(BB->isInstrOrderValid());262 EXPECT_TRUE(I1->comesBefore(I3));263 EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator());264}265 266static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {267 SMDiagnostic Err;268 std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);269 if (!Mod)270 Err.print(__FILE__, errs());271 return Mod;272}273 274TEST(BasicBlockTest, SpliceFromBB) {275 LLVMContext Ctx;276 std::unique_ptr<Module> M = parseIR(Ctx, R"(277 define void @f(i32 %a) {278 from:279 %fromInstr1 = add i32 %a, %a280 %fromInstr2 = sub i32 %a, %a281 br label %to282 283 to:284 %toInstr1 = mul i32 %a, %a285 %toInstr2 = sdiv i32 %a, %a286 ret void287 }288)");289 Function *F = &*M->begin();290 auto BBIt = F->begin();291 BasicBlock *FromBB = &*BBIt++;292 BasicBlock *ToBB = &*BBIt++;293 294 auto FromBBIt = FromBB->begin();295 Instruction *FromI1 = &*FromBBIt++;296 Instruction *FromI2 = &*FromBBIt++;297 Instruction *FromBr = &*FromBBIt++;298 299 auto ToBBIt = ToBB->begin();300 Instruction *ToI1 = &*ToBBIt++;301 Instruction *ToI2 = &*ToBBIt++;302 Instruction *ToRet = &*ToBBIt++;303 ToBB->splice(ToI1->getIterator(), FromBB);304 305 EXPECT_TRUE(FromBB->empty());306 307 auto It = ToBB->begin();308 EXPECT_EQ(&*It++, FromI1);309 EXPECT_EQ(&*It++, FromI2);310 EXPECT_EQ(&*It++, FromBr);311 EXPECT_EQ(&*It++, ToI1);312 EXPECT_EQ(&*It++, ToI2);313 EXPECT_EQ(&*It++, ToRet);314}315 316TEST(BasicBlockTest, SpliceOneInstr) {317 LLVMContext Ctx;318 std::unique_ptr<Module> M = parseIR(Ctx, R"(319 define void @f(i32 %a) {320 from:321 %fromInstr1 = add i32 %a, %a322 %fromInstr2 = sub i32 %a, %a323 br label %to324 325 to:326 %toInstr1 = mul i32 %a, %a327 %toInstr2 = sdiv i32 %a, %a328 ret void329 }330)");331 Function *F = &*M->begin();332 auto BBIt = F->begin();333 BasicBlock *FromBB = &*BBIt++;334 BasicBlock *ToBB = &*BBIt++;335 336 auto FromBBIt = FromBB->begin();337 Instruction *FromI1 = &*FromBBIt++;338 Instruction *FromI2 = &*FromBBIt++;339 Instruction *FromBr = &*FromBBIt++;340 341 auto ToBBIt = ToBB->begin();342 Instruction *ToI1 = &*ToBBIt++;343 Instruction *ToI2 = &*ToBBIt++;344 Instruction *ToRet = &*ToBBIt++;345 ToBB->splice(ToI1->getIterator(), FromBB, FromI2->getIterator());346 347 EXPECT_EQ(FromBB->size(), 2u);348 EXPECT_EQ(ToBB->size(), 4u);349 350 auto It = FromBB->begin();351 EXPECT_EQ(&*It++, FromI1);352 EXPECT_EQ(&*It++, FromBr);353 354 It = ToBB->begin();355 EXPECT_EQ(&*It++, FromI2);356 EXPECT_EQ(&*It++, ToI1);357 EXPECT_EQ(&*It++, ToI2);358 EXPECT_EQ(&*It++, ToRet);359}360 361TEST(BasicBlockTest, SpliceOneInstrWhenFromIsSameAsTo) {362 LLVMContext Ctx;363 std::unique_ptr<Module> M = parseIR(Ctx, R"(364 define void @f(i32 %a) {365 bb:366 %instr1 = add i32 %a, %a367 %instr2 = sub i32 %a, %a368 ret void369 }370)");371 Function *F = &*M->begin();372 auto BBIt = F->begin();373 BasicBlock *BB = &*BBIt++;374 375 auto It = BB->begin();376 Instruction *Instr1 = &*It++;377 Instruction *Instr2 = &*It++;378 Instruction *Ret = &*It++;379 380 // According to ilist's splice() a single-element splice where dst == src381 // should be a noop.382 BB->splice(Instr1->getIterator(), BB, Instr1->getIterator());383 384 It = BB->begin();385 EXPECT_EQ(&*It++, Instr1);386 EXPECT_EQ(&*It++, Instr2);387 EXPECT_EQ(&*It++, Ret);388 EXPECT_EQ(BB->size(), 3u);389}390 391TEST(BasicBlockTest, SpliceLastInstr) {392 LLVMContext Ctx;393 std::unique_ptr<Module> M = parseIR(Ctx, R"(394 define void @f(i32 %a) {395 from:396 %fromInstr1 = add i32 %a, %a397 %fromInstr2 = sub i32 %a, %a398 br label %to399 400 to:401 %toInstr1 = mul i32 %a, %a402 %toInstr2 = sdiv i32 %a, %a403 ret void404 }405)");406 Function *F = &*M->begin();407 auto BBIt = F->begin();408 BasicBlock *FromBB = &*BBIt++;409 BasicBlock *ToBB = &*BBIt++;410 411 auto FromBBIt = FromBB->begin();412 Instruction *FromI1 = &*FromBBIt++;413 Instruction *FromI2 = &*FromBBIt++;414 Instruction *FromBr = &*FromBBIt++;415 416 auto ToBBIt = ToBB->begin();417 Instruction *ToI1 = &*ToBBIt++;418 Instruction *ToI2 = &*ToBBIt++;419 Instruction *ToRet = &*ToBBIt++;420 ToBB->splice(ToI1->getIterator(), FromBB, FromI2->getIterator(),421 FromBr->getIterator());422 423 EXPECT_EQ(FromBB->size(), 2u);424 auto It = FromBB->begin();425 EXPECT_EQ(&*It++, FromI1);426 EXPECT_EQ(&*It++, FromBr);427 428 EXPECT_EQ(ToBB->size(), 4u);429 It = ToBB->begin();430 EXPECT_EQ(&*It++, FromI2);431 EXPECT_EQ(&*It++, ToI1);432 EXPECT_EQ(&*It++, ToI2);433 EXPECT_EQ(&*It++, ToRet);434}435 436TEST(BasicBlockTest, SpliceInstrRange) {437 LLVMContext Ctx;438 std::unique_ptr<Module> M = parseIR(Ctx, R"(439 define void @f(i32 %a) {440 from:441 %fromInstr1 = add i32 %a, %a442 %fromInstr2 = sub i32 %a, %a443 br label %to444 445 to:446 %toInstr1 = mul i32 %a, %a447 %toInstr2 = sdiv i32 %a, %a448 ret void449 }450)");451 Function *F = &*M->begin();452 auto BBIt = F->begin();453 BasicBlock *FromBB = &*BBIt++;454 BasicBlock *ToBB = &*BBIt++;455 456 auto FromBBIt = FromBB->begin();457 Instruction *FromI1 = &*FromBBIt++;458 Instruction *FromI2 = &*FromBBIt++;459 Instruction *FromBr = &*FromBBIt++;460 461 auto ToBBIt = ToBB->begin();462 Instruction *ToI1 = &*ToBBIt++;463 Instruction *ToI2 = &*ToBBIt++;464 Instruction *ToRet = &*ToBBIt++;465 ToBB->splice(ToI2->getIterator(), FromBB, FromBB->begin(), FromBB->end());466 467 EXPECT_EQ(FromBB->size(), 0u);468 469 EXPECT_EQ(ToBB->size(), 6u);470 auto It = ToBB->begin();471 EXPECT_EQ(&*It++, ToI1);472 EXPECT_EQ(&*It++, FromI1);473 EXPECT_EQ(&*It++, FromI2);474 EXPECT_EQ(&*It++, FromBr);475 EXPECT_EQ(&*It++, ToI2);476 EXPECT_EQ(&*It++, ToRet);477}478 479#ifdef EXPENSIVE_CHECKS480TEST(BasicBlockTest, SpliceEndBeforeBegin) {481 LLVMContext Ctx;482 std::unique_ptr<Module> M = parseIR(Ctx, R"(483 define void @f(i32 %a) {484 from:485 %fromInstr1 = add i32 %a, %a486 %fromInstr2 = sub i32 %a, %a487 br label %to488 489 to:490 %toInstr1 = mul i32 %a, %a491 %toInstr2 = sdiv i32 %a, %a492 ret void493 }494)");495 Function *F = &*M->begin();496 auto BBIt = F->begin();497 BasicBlock *FromBB = &*BBIt++;498 BasicBlock *ToBB = &*BBIt++;499 500 auto FromBBIt = FromBB->begin();501 Instruction *FromI1 = &*FromBBIt++;502 Instruction *FromI2 = &*FromBBIt++;503 504 auto ToBBIt = ToBB->begin();505 Instruction *ToI2 = &*ToBBIt++;506 507 EXPECT_DEATH(ToBB->splice(ToI2->getIterator(), FromBB, FromI2->getIterator(),508 FromI1->getIterator()),509 "FromBeginIt not before FromEndIt!");510}511#endif //EXPENSIVE_CHECKS512 513TEST(BasicBlockTest, EraseRange) {514 LLVMContext Ctx;515 std::unique_ptr<Module> M = parseIR(Ctx, R"(516 define void @f(i32 %a) {517 bb0:518 %instr1 = add i32 %a, %a519 %instr2 = sub i32 %a, %a520 ret void521 }522)");523 Function *F = &*M->begin();524 525 auto BB0It = F->begin();526 BasicBlock *BB0 = &*BB0It;527 528 auto It = BB0->begin();529 Instruction *Instr1 = &*It++;530 Instruction *Instr2 = &*It++;531 532 EXPECT_EQ(BB0->size(), 3u);533 534 // Erase no instruction535 BB0->erase(Instr1->getIterator(), Instr1->getIterator());536 EXPECT_EQ(BB0->size(), 3u);537 538 // Erase %instr1539 BB0->erase(Instr1->getIterator(), Instr2->getIterator());540 EXPECT_EQ(BB0->size(), 2u);541 EXPECT_EQ(&*BB0->begin(), Instr2);542 543 // Erase all instructions544 BB0->erase(BB0->begin(), BB0->end());545 EXPECT_TRUE(BB0->empty());546}547 548TEST(BasicBlockTest, DiscardValueNames) {549 const char *ModuleString = "declare void @f(i32 %dangling)";550 SMDiagnostic Err;551 LLVMContext Ctx;552 { // Scope of M.553 auto M = parseAssemblyString(ModuleString, Err, Ctx);554 ASSERT_TRUE(M.get());555 EXPECT_FALSE(Ctx.shouldDiscardValueNames());556 }557 { // Scope of M.558 auto M = parseAssemblyString(ModuleString, Err, Ctx);559 ASSERT_TRUE(M.get());560 Ctx.setDiscardValueNames(true);561 }562}563 564TEST(BasicBlockTest, DiscardValueNames2) {565 SMDiagnostic Err;566 LLVMContext Ctx;567 Module M("Mod", Ctx);568 auto FTy = FunctionType::get(Type::getVoidTy(M.getContext()),569 {Type::getInt32Ty(Ctx)}, /*isVarArg=*/false);570 { // Scope of F.571 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", &M);572 F->getArg(0)->setName("dangling");573 F->removeFromParent();574 EXPECT_FALSE(Ctx.shouldDiscardValueNames());575 delete F;576 }577 { // Scope of F.578 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", &M);579 F->getArg(0)->setName("dangling");580 F->removeFromParent();581 Ctx.setDiscardValueNames(true);582 delete F;583 }584}585 586} // End anonymous namespace.587} // End llvm namespace.588