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