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   for (auto &PN : BB->phis()) {
41     (void)PN;
42     EXPECT_TRUE(false) << "empty block should have no phis";
43   }
44 
45   // Make it a cycle.
46   auto *BI = BranchInst::Create(BB.get(), BB.get());
47 
48   // Now insert some PHI nodes.
49   auto *Int32Ty = Type::getInt32Ty(Context);
50   auto *P1 = PHINode::Create(Int32Ty, /*NumReservedValues*/ 3, "phi.1", BI);
51   auto *P2 = PHINode::Create(Int32Ty, /*NumReservedValues*/ 3, "phi.2", BI);
52   auto *P3 = PHINode::Create(Int32Ty, /*NumReservedValues*/ 3, "phi.3", BI);
53 
54   // Some non-PHI nodes.
55   auto *Sum = BinaryOperator::CreateAdd(P1, P2, "sum", BI);
56 
57   // Now wire up the incoming values that are interesting.
58   P1->addIncoming(P2, BB.get());
59   P2->addIncoming(P1, BB.get());
60   P3->addIncoming(Sum, BB.get());
61 
62   // Finally, let's iterate them, which is the thing we're trying to test.
63   // We'll use this to wire up the rest of the incoming values.
64   for (auto &PN : BB->phis()) {
65     PN.addIncoming(UndefValue::get(Int32Ty), BB1.get());
66     PN.addIncoming(UndefValue::get(Int32Ty), BB2.get());
67   }
68 
69   // Test that we can use const iterators and generally that the iterators
70   // behave like iterators.
71   BasicBlock::const_phi_iterator CI;
72   CI = BB->phis().begin();
73   EXPECT_NE(CI, BB->phis().end());
74 
75   // Test that filtering iterators work with basic blocks.
76   auto isPhi = [](Instruction &I) { return isa<PHINode>(&I); };
77   auto Phis = make_filter_range(*BB, isPhi);
78   auto ReversedPhis = reverse(make_filter_range(*BB, isPhi));
79   EXPECT_EQ(std::distance(Phis.begin(), Phis.end()), 3);
80   EXPECT_EQ(&*Phis.begin(), P1);
81   EXPECT_EQ(std::distance(ReversedPhis.begin(), ReversedPhis.end()), 3);
82   EXPECT_EQ(&*ReversedPhis.begin(), P3);
83 
84   // And iterate a const range.
85   for (const auto &PN : const_cast<const BasicBlock *>(BB.get())->phis()) {
86     EXPECT_EQ(BB.get(), PN.getIncomingBlock(0));
87     EXPECT_EQ(BB1.get(), PN.getIncomingBlock(1));
88     EXPECT_EQ(BB2.get(), PN.getIncomingBlock(2));
89   }
90 }
91 
92 #define CHECK_ITERATORS(Range1, Range2)                                        \
93   EXPECT_EQ(std::distance(Range1.begin(), Range1.end()),                       \
94             std::distance(Range2.begin(), Range2.end()));                      \
95   for (auto Pair : zip(Range1, Range2))                                        \
96     EXPECT_EQ(&std::get<0>(Pair), std::get<1>(Pair));
97 
98 TEST(BasicBlockTest, TestInstructionsWithoutDebug) {
99   LLVMContext Ctx;
100 
101   Module *M = new Module("MyModule", Ctx);
102   Type *ArgTy1[] = {Type::getInt32PtrTy(Ctx)};
103   FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), ArgTy1, false);
104   Argument *V = new Argument(Type::getInt32Ty(Ctx));
105   Function *F = Function::Create(FT, Function::ExternalLinkage, "", M);
106 
107   Function *DbgAddr = Intrinsic::getDeclaration(M, Intrinsic::dbg_addr);
108   Function *DbgDeclare = Intrinsic::getDeclaration(M, Intrinsic::dbg_declare);
109   Function *DbgValue = Intrinsic::getDeclaration(M, Intrinsic::dbg_value);
110   Value *DIV = MetadataAsValue::get(Ctx, (Metadata *)nullptr);
111   SmallVector<Value *, 3> Args = {DIV, DIV, DIV};
112 
113   BasicBlock *BB1 = BasicBlock::Create(Ctx, "", F);
114   const BasicBlock *BBConst = BB1;
115   IRBuilder<> Builder1(BB1);
116 
117   AllocaInst *Var = Builder1.CreateAlloca(Builder1.getInt8Ty());
118   Builder1.CreateCall(DbgValue, Args);
119   Instruction *AddInst = cast<Instruction>(Builder1.CreateAdd(V, V));
120   Instruction *MulInst = cast<Instruction>(Builder1.CreateMul(AddInst, V));
121   Builder1.CreateCall(DbgDeclare, Args);
122   Instruction *SubInst = cast<Instruction>(Builder1.CreateSub(MulInst, V));
123   Builder1.CreateCall(DbgAddr, Args);
124 
125   SmallVector<Instruction *, 4> Exp = {Var, AddInst, MulInst, SubInst};
126   CHECK_ITERATORS(BB1->instructionsWithoutDebug(), Exp);
127   CHECK_ITERATORS(BBConst->instructionsWithoutDebug(), Exp);
128 
129   EXPECT_EQ(static_cast<size_t>(BB1->sizeWithoutDebug()), Exp.size());
130   EXPECT_EQ(static_cast<size_t>(BBConst->sizeWithoutDebug()), Exp.size());
131 
132   delete M;
133   delete V;
134 }
135 
136 TEST(BasicBlockTest, ComesBefore) {
137   const char *ModuleString = R"(define i32 @f(i32 %x) {
138                                   %add = add i32 %x, 42
139                                   ret i32 %add
140                                 })";
141   LLVMContext Ctx;
142   SMDiagnostic Err;
143   auto M = parseAssemblyString(ModuleString, Err, Ctx);
144   ASSERT_TRUE(M.get());
145 
146   Function *F = M->getFunction("f");
147   BasicBlock &BB = F->front();
148   BasicBlock::iterator I = BB.begin();
149   Instruction *Add = &*I++;
150   Instruction *Ret = &*I++;
151 
152   // Intentionally duplicated to verify cached and uncached are the same.
153   EXPECT_FALSE(BB.isInstrOrderValid());
154   EXPECT_FALSE(Add->comesBefore(Add));
155   EXPECT_TRUE(BB.isInstrOrderValid());
156   EXPECT_FALSE(Add->comesBefore(Add));
157   BB.invalidateOrders();
158   EXPECT_FALSE(BB.isInstrOrderValid());
159   EXPECT_TRUE(Add->comesBefore(Ret));
160   EXPECT_TRUE(BB.isInstrOrderValid());
161   EXPECT_TRUE(Add->comesBefore(Ret));
162   BB.invalidateOrders();
163   EXPECT_FALSE(Ret->comesBefore(Add));
164   EXPECT_FALSE(Ret->comesBefore(Add));
165   BB.invalidateOrders();
166   EXPECT_FALSE(Ret->comesBefore(Ret));
167   EXPECT_FALSE(Ret->comesBefore(Ret));
168 }
169 
170 TEST(BasicBlockTest, EmptyPhi) {
171   LLVMContext Ctx;
172 
173   Module *M = new Module("MyModule", Ctx);
174   FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), {}, false);
175   Function *F = Function::Create(FT, Function::ExternalLinkage, "", M);
176 
177   BasicBlock *BB1 = BasicBlock::Create(Ctx, "", F);
178   ReturnInst::Create(Ctx, BB1);
179 
180   Type *Ty = Type::getInt32PtrTy(Ctx);
181   BasicBlock *BB2 = BasicBlock::Create(Ctx, "", F);
182   PHINode::Create(Ty, 0, "", BB2);
183   ReturnInst::Create(Ctx, BB2);
184   EXPECT_FALSE(verifyModule(*M, &errs()));
185 }
186 
187 class InstrOrderInvalidationTest : public ::testing::Test {
188 protected:
189   void SetUp() override {
190     M.reset(new Module("MyModule", Ctx));
191     Nop = Intrinsic::getDeclaration(M.get(), Intrinsic::donothing);
192     FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), {}, false);
193     Function *F = Function::Create(FT, Function::ExternalLinkage, "foo", *M);
194     BB = BasicBlock::Create(Ctx, "entry", F);
195 
196     IRBuilder<> Builder(BB);
197     I1 = Builder.CreateCall(Nop);
198     I2 = Builder.CreateCall(Nop);
199     I3 = Builder.CreateCall(Nop);
200     Ret = Builder.CreateRetVoid();
201   }
202 
203   LLVMContext Ctx;
204   std::unique_ptr<Module> M;
205   Function *Nop = nullptr;
206   BasicBlock *BB = nullptr;
207   Instruction *I1 = nullptr;
208   Instruction *I2 = nullptr;
209   Instruction *I3 = nullptr;
210   Instruction *Ret = nullptr;
211 };
212 
213 TEST_F(InstrOrderInvalidationTest, InsertInvalidation) {
214   EXPECT_FALSE(BB->isInstrOrderValid());
215   EXPECT_TRUE(I1->comesBefore(I2));
216   EXPECT_TRUE(BB->isInstrOrderValid());
217   EXPECT_TRUE(I2->comesBefore(I3));
218   EXPECT_TRUE(I3->comesBefore(Ret));
219   EXPECT_TRUE(BB->isInstrOrderValid());
220 
221   // Invalidate orders.
222   IRBuilder<> Builder(BB, I2->getIterator());
223   Instruction *I1a = Builder.CreateCall(Nop);
224   EXPECT_FALSE(BB->isInstrOrderValid());
225   EXPECT_TRUE(I1->comesBefore(I1a));
226   EXPECT_TRUE(BB->isInstrOrderValid());
227   EXPECT_TRUE(I1a->comesBefore(I2));
228   EXPECT_TRUE(I2->comesBefore(I3));
229   EXPECT_TRUE(I3->comesBefore(Ret));
230   EXPECT_TRUE(BB->isInstrOrderValid());
231 }
232 
233 TEST_F(InstrOrderInvalidationTest, SpliceInvalidation) {
234   EXPECT_TRUE(I1->comesBefore(I2));
235   EXPECT_TRUE(I2->comesBefore(I3));
236   EXPECT_TRUE(I3->comesBefore(Ret));
237   EXPECT_TRUE(BB->isInstrOrderValid());
238 
239   // Use Instruction::moveBefore, which uses splice.
240   I2->moveBefore(I1);
241   EXPECT_FALSE(BB->isInstrOrderValid());
242 
243   EXPECT_TRUE(I2->comesBefore(I1));
244   EXPECT_TRUE(I1->comesBefore(I3));
245   EXPECT_TRUE(I3->comesBefore(Ret));
246   EXPECT_TRUE(BB->isInstrOrderValid());
247 }
248 
249 TEST_F(InstrOrderInvalidationTest, RemoveNoInvalidation) {
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->removeFromParent();
257   I2->deleteValue();
258   I2 = nullptr;
259   EXPECT_TRUE(BB->isInstrOrderValid());
260   EXPECT_TRUE(I1->comesBefore(I3));
261   EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator());
262 }
263 
264 TEST_F(InstrOrderInvalidationTest, EraseNoInvalidation) {
265   // Cache the instruction order.
266   EXPECT_FALSE(BB->isInstrOrderValid());
267   EXPECT_TRUE(I1->comesBefore(I2));
268   EXPECT_TRUE(BB->isInstrOrderValid());
269 
270   // Removing does not invalidate instruction order.
271   I2->eraseFromParent();
272   I2 = nullptr;
273   EXPECT_TRUE(BB->isInstrOrderValid());
274   EXPECT_TRUE(I1->comesBefore(I3));
275   EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator());
276 }
277 
278 } // End anonymous namespace.
279 } // End llvm namespace.
280