1 //===- llvm/unittests/Transforms/Vectorize/VPlanTest.cpp - VPlan tests ----===//
2 //
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "../lib/Transforms/Vectorize/VPlan.h"
11 #include "llvm/IR/Instruction.h"
12 #include "llvm/IR/Instructions.h"
13 #include "gtest/gtest.h"
14 #include <string>
15 
16 namespace llvm {
17 namespace {
18 
19 #define CHECK_ITERATOR(Range1, ...)                                            \
20   do {                                                                         \
21     std::vector<VPInstruction *> Tmp = {__VA_ARGS__};                          \
22     EXPECT_EQ((size_t)std::distance(Range1.begin(), Range1.end()),             \
23               Tmp.size());                                                     \
24     for (auto Pair : zip(Range1, make_range(Tmp.begin(), Tmp.end())))          \
25       EXPECT_EQ(&std::get<0>(Pair), std::get<1>(Pair));                        \
26   } while (0)
27 
28 TEST(VPInstructionTest, insertBefore) {
29   VPInstruction *I1 = new VPInstruction(0, {});
30   VPInstruction *I2 = new VPInstruction(1, {});
31   VPInstruction *I3 = new VPInstruction(2, {});
32 
33   VPBasicBlock VPBB1;
34   VPBB1.appendRecipe(I1);
35 
36   I2->insertBefore(I1);
37   CHECK_ITERATOR(VPBB1, I2, I1);
38 
39   I3->insertBefore(I2);
40   CHECK_ITERATOR(VPBB1, I3, I2, I1);
41 }
42 
43 TEST(VPInstructionTest, eraseFromParent) {
44   VPInstruction *I1 = new VPInstruction(0, {});
45   VPInstruction *I2 = new VPInstruction(1, {});
46   VPInstruction *I3 = new VPInstruction(2, {});
47 
48   VPBasicBlock VPBB1;
49   VPBB1.appendRecipe(I1);
50   VPBB1.appendRecipe(I2);
51   VPBB1.appendRecipe(I3);
52 
53   I2->eraseFromParent();
54   CHECK_ITERATOR(VPBB1, I1, I3);
55 
56   I1->eraseFromParent();
57   CHECK_ITERATOR(VPBB1, I3);
58 
59   I3->eraseFromParent();
60   EXPECT_TRUE(VPBB1.empty());
61 }
62 
63 TEST(VPInstructionTest, moveAfter) {
64   VPInstruction *I1 = new VPInstruction(0, {});
65   VPInstruction *I2 = new VPInstruction(1, {});
66   VPInstruction *I3 = new VPInstruction(2, {});
67 
68   VPBasicBlock VPBB1;
69   VPBB1.appendRecipe(I1);
70   VPBB1.appendRecipe(I2);
71   VPBB1.appendRecipe(I3);
72 
73   I1->moveAfter(I2);
74 
75   CHECK_ITERATOR(VPBB1, I2, I1, I3);
76 
77   VPInstruction *I4 = new VPInstruction(4, {});
78   VPInstruction *I5 = new VPInstruction(5, {});
79   VPBasicBlock VPBB2;
80   VPBB2.appendRecipe(I4);
81   VPBB2.appendRecipe(I5);
82 
83   I3->moveAfter(I4);
84 
85   CHECK_ITERATOR(VPBB1, I2, I1);
86   CHECK_ITERATOR(VPBB2, I4, I3, I5);
87   EXPECT_EQ(I3->getParent(), I4->getParent());
88 }
89 
90 TEST(VPInstructionTest, setOperand) {
91   VPValue *VPV1 = new VPValue();
92   VPValue *VPV2 = new VPValue();
93   VPInstruction *I1 = new VPInstruction(0, {VPV1, VPV2});
94   EXPECT_EQ(1u, VPV1->getNumUsers());
95   EXPECT_EQ(I1, *VPV1->user_begin());
96   EXPECT_EQ(1u, VPV2->getNumUsers());
97   EXPECT_EQ(I1, *VPV2->user_begin());
98 
99   // Replace operand 0 (VPV1) with VPV3.
100   VPValue *VPV3 = new VPValue();
101   I1->setOperand(0, VPV3);
102   EXPECT_EQ(0u, VPV1->getNumUsers());
103   EXPECT_EQ(1u, VPV2->getNumUsers());
104   EXPECT_EQ(I1, *VPV2->user_begin());
105   EXPECT_EQ(1u, VPV3->getNumUsers());
106   EXPECT_EQ(I1, *VPV3->user_begin());
107 
108   // Replace operand 1 (VPV2) with VPV3.
109   I1->setOperand(1, VPV3);
110   EXPECT_EQ(0u, VPV1->getNumUsers());
111   EXPECT_EQ(0u, VPV2->getNumUsers());
112   EXPECT_EQ(2u, VPV3->getNumUsers());
113   EXPECT_EQ(I1, *VPV3->user_begin());
114   EXPECT_EQ(I1, *std::next(VPV3->user_begin()));
115 
116   // Replace operand 0 (VPV3) with VPV4.
117   VPValue *VPV4 = new VPValue();
118   I1->setOperand(0, VPV4);
119   EXPECT_EQ(1u, VPV3->getNumUsers());
120   EXPECT_EQ(I1, *VPV3->user_begin());
121   EXPECT_EQ(I1, *VPV4->user_begin());
122 
123   // Replace operand 1 (VPV3) with VPV4.
124   I1->setOperand(1, VPV4);
125   EXPECT_EQ(0u, VPV3->getNumUsers());
126   EXPECT_EQ(I1, *VPV4->user_begin());
127   EXPECT_EQ(I1, *std::next(VPV4->user_begin()));
128 
129   delete I1;
130   delete VPV1;
131   delete VPV2;
132   delete VPV3;
133   delete VPV4;
134 }
135 
136 TEST(VPInstructionTest, replaceAllUsesWith) {
137   VPValue *VPV1 = new VPValue();
138   VPValue *VPV2 = new VPValue();
139   VPInstruction *I1 = new VPInstruction(0, {VPV1, VPV2});
140 
141   // Replace all uses of VPV1 with VPV3.
142   VPValue *VPV3 = new VPValue();
143   VPV1->replaceAllUsesWith(VPV3);
144   EXPECT_EQ(VPV3, I1->getOperand(0));
145   EXPECT_EQ(VPV2, I1->getOperand(1));
146   EXPECT_EQ(0u, VPV1->getNumUsers());
147   EXPECT_EQ(1u, VPV2->getNumUsers());
148   EXPECT_EQ(I1, *VPV2->user_begin());
149   EXPECT_EQ(1u, VPV3->getNumUsers());
150   EXPECT_EQ(I1, *VPV3->user_begin());
151 
152   // Replace all uses of VPV2 with VPV3.
153   VPV2->replaceAllUsesWith(VPV3);
154   EXPECT_EQ(VPV3, I1->getOperand(0));
155   EXPECT_EQ(VPV3, I1->getOperand(1));
156   EXPECT_EQ(0u, VPV1->getNumUsers());
157   EXPECT_EQ(0u, VPV2->getNumUsers());
158   EXPECT_EQ(2u, VPV3->getNumUsers());
159   EXPECT_EQ(I1, *VPV3->user_begin());
160 
161   // Replace all uses of VPV3 with VPV1.
162   VPV3->replaceAllUsesWith(VPV1);
163   EXPECT_EQ(VPV1, I1->getOperand(0));
164   EXPECT_EQ(VPV1, I1->getOperand(1));
165   EXPECT_EQ(2u, VPV1->getNumUsers());
166   EXPECT_EQ(I1, *VPV1->user_begin());
167   EXPECT_EQ(0u, VPV2->getNumUsers());
168   EXPECT_EQ(0u, VPV3->getNumUsers());
169 
170   delete I1;
171   delete VPV1;
172   delete VPV2;
173   delete VPV3;
174 }
175 
176 TEST(VPBasicBlockTest, getPlan) {
177   {
178     VPBasicBlock *VPBB1 = new VPBasicBlock();
179     VPBasicBlock *VPBB2 = new VPBasicBlock();
180     VPBasicBlock *VPBB3 = new VPBasicBlock();
181     VPBasicBlock *VPBB4 = new VPBasicBlock();
182 
183     //     VPBB1
184     //     /   \
185     // VPBB2  VPBB3
186     //    \    /
187     //    VPBB4
188     VPBlockUtils::connectBlocks(VPBB1, VPBB2);
189     VPBlockUtils::connectBlocks(VPBB1, VPBB3);
190     VPBlockUtils::connectBlocks(VPBB2, VPBB4);
191     VPBlockUtils::connectBlocks(VPBB3, VPBB4);
192 
193     VPlan Plan;
194     Plan.setEntry(VPBB1);
195 
196     EXPECT_EQ(&Plan, VPBB1->getPlan());
197     EXPECT_EQ(&Plan, VPBB2->getPlan());
198     EXPECT_EQ(&Plan, VPBB3->getPlan());
199     EXPECT_EQ(&Plan, VPBB4->getPlan());
200   }
201 
202   {
203     // Region block is entry into VPlan.
204     VPBasicBlock *R1BB1 = new VPBasicBlock();
205     VPBasicBlock *R1BB2 = new VPBasicBlock();
206     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB2, "R1");
207     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
208 
209     VPlan Plan;
210     Plan.setEntry(R1);
211     EXPECT_EQ(&Plan, R1->getPlan());
212     EXPECT_EQ(&Plan, R1BB1->getPlan());
213     EXPECT_EQ(&Plan, R1BB2->getPlan());
214   }
215 
216   {
217     // VPBasicBlock is the entry into the VPlan, followed by a region.
218     VPBasicBlock *R1BB1 = new VPBasicBlock();
219     VPBasicBlock *R1BB2 = new VPBasicBlock();
220     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB2, "R1");
221     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
222 
223     VPBasicBlock *VPBB1 = new VPBasicBlock();
224     VPBlockUtils::connectBlocks(VPBB1, R1);
225 
226     VPlan Plan;
227     Plan.setEntry(VPBB1);
228     EXPECT_EQ(&Plan, VPBB1->getPlan());
229     EXPECT_EQ(&Plan, R1->getPlan());
230     EXPECT_EQ(&Plan, R1BB1->getPlan());
231     EXPECT_EQ(&Plan, R1BB2->getPlan());
232   }
233 
234   {
235     VPBasicBlock *R1BB1 = new VPBasicBlock();
236     VPBasicBlock *R1BB2 = new VPBasicBlock();
237     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB2, "R1");
238     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
239 
240     VPBasicBlock *R2BB1 = new VPBasicBlock();
241     VPBasicBlock *R2BB2 = new VPBasicBlock();
242     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
243     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
244 
245     VPBasicBlock *VPBB1 = new VPBasicBlock();
246     VPBlockUtils::connectBlocks(VPBB1, R1);
247     VPBlockUtils::connectBlocks(VPBB1, R2);
248 
249     VPBasicBlock *VPBB2 = new VPBasicBlock();
250     VPBlockUtils::connectBlocks(R1, VPBB2);
251     VPBlockUtils::connectBlocks(R2, VPBB2);
252 
253     VPlan Plan;
254     Plan.setEntry(VPBB1);
255     EXPECT_EQ(&Plan, VPBB1->getPlan());
256     EXPECT_EQ(&Plan, R1->getPlan());
257     EXPECT_EQ(&Plan, R1BB1->getPlan());
258     EXPECT_EQ(&Plan, R1BB2->getPlan());
259     EXPECT_EQ(&Plan, R2->getPlan());
260     EXPECT_EQ(&Plan, R2BB1->getPlan());
261     EXPECT_EQ(&Plan, R2BB2->getPlan());
262     EXPECT_EQ(&Plan, VPBB2->getPlan());
263   }
264 }
265 
266 TEST(VPBasicBlockTest, print) {
267   VPInstruction *I1 = new VPInstruction(Instruction::Add, {});
268   VPInstruction *I2 = new VPInstruction(Instruction::Sub, {I1});
269   VPInstruction *I3 = new VPInstruction(Instruction::Br, {I1, I2});
270 
271   VPBasicBlock *VPBB1 = new VPBasicBlock();
272   VPBB1->appendRecipe(I1);
273   VPBB1->appendRecipe(I2);
274   VPBB1->appendRecipe(I3);
275 
276   VPInstruction *I4 = new VPInstruction(Instruction::Mul, {I2, I1});
277   VPInstruction *I5 = new VPInstruction(Instruction::Ret, {I4});
278   VPBasicBlock *VPBB2 = new VPBasicBlock();
279   VPBB2->appendRecipe(I4);
280   VPBB2->appendRecipe(I5);
281 
282   VPBlockUtils::connectBlocks(VPBB1, VPBB2);
283 
284   // Check printing an instruction without associated VPlan.
285   {
286     std::string I3Dump;
287     raw_string_ostream OS(I3Dump);
288     I3->print(OS);
289     OS.flush();
290     EXPECT_EQ("br <badref> <badref>", I3Dump);
291   }
292 
293   VPlan Plan;
294   Plan.setEntry(VPBB1);
295   std::string FullDump;
296   raw_string_ostream(FullDump) << Plan;
297 
298   const char *ExpectedStr = R"(digraph VPlan {
299 graph [labelloc=t, fontsize=30; label="Vectorization Plan"]
300 node [shape=rect, fontname=Courier, fontsize=30]
301 edge [fontname=Courier, fontsize=30]
302 compound=true
303   N0 [label =
304     ":\n" +
305       "EMIT vp<%0> = add\l" +
306       "EMIT vp<%1> = sub vp<%0>\l" +
307       "EMIT br vp<%0> vp<%1>\l"
308   ]
309   N0 -> N1 [ label=""]
310   N1 [label =
311     ":\n" +
312       "EMIT vp<%2> = mul vp<%1> vp<%0>\l" +
313       "EMIT ret vp<%2>\l"
314   ]
315 }
316 )";
317   EXPECT_EQ(ExpectedStr, FullDump);
318 
319   {
320     std::string I3Dump;
321     raw_string_ostream OS(I3Dump);
322     I3->print(OS);
323     OS.flush();
324     EXPECT_EQ("br vp<%0> vp<%1>", I3Dump);
325   }
326 
327   {
328     std::string I4Dump;
329     raw_string_ostream OS(I4Dump);
330     OS << *I4;
331     OS.flush();
332     EXPECT_EQ("vp<%2> = mul vp<%1> vp<%0>", I4Dump);
333   }
334 }
335 
336 TEST(VPRecipeTest, CastVPWidenRecipeToVPUser) {
337   LLVMContext C;
338 
339   IntegerType *Int32 = IntegerType::get(C, 32);
340   auto *AI =
341       BinaryOperator::CreateAdd(UndefValue::get(Int32), UndefValue::get(Int32));
342   VPValue Op1;
343   VPValue Op2;
344   SmallVector<VPValue *, 2> Args;
345   Args.push_back(&Op1);
346   Args.push_back(&Op1);
347   VPWidenRecipe WidenR(*AI, make_range(Args.begin(), Args.end()));
348   EXPECT_TRUE(isa<VPUser>(&WidenR));
349   VPRecipeBase *WidenRBase = &WidenR;
350   EXPECT_TRUE(isa<VPUser>(WidenRBase));
351   delete AI;
352 }
353 
354 TEST(VPRecipeTest, CastVPWidenCallRecipeToVPUser) {
355   LLVMContext C;
356 
357   IntegerType *Int32 = IntegerType::get(C, 32);
358   FunctionType *FTy = FunctionType::get(Int32, false);
359   auto *Call = CallInst::Create(FTy, UndefValue::get(FTy));
360   VPValue Op1;
361   VPValue Op2;
362   SmallVector<VPValue *, 2> Args;
363   Args.push_back(&Op1);
364   Args.push_back(&Op2);
365   VPWidenCallRecipe Recipe(*Call, make_range(Args.begin(), Args.end()));
366   EXPECT_TRUE(isa<VPUser>(&Recipe));
367   VPRecipeBase *BaseR = &Recipe;
368   EXPECT_TRUE(isa<VPUser>(BaseR));
369   delete Call;
370 }
371 
372 TEST(VPRecipeTest, CastVPWidenSelectRecipeToVPUser) {
373   LLVMContext C;
374 
375   IntegerType *Int1 = IntegerType::get(C, 1);
376   IntegerType *Int32 = IntegerType::get(C, 32);
377   auto *SelectI = SelectInst::Create(
378       UndefValue::get(Int1), UndefValue::get(Int32), UndefValue::get(Int32));
379   VPValue Op1;
380   VPValue Op2;
381   VPValue Op3;
382   SmallVector<VPValue *, 4> Args;
383   Args.push_back(&Op1);
384   Args.push_back(&Op2);
385   Args.push_back(&Op3);
386   VPWidenSelectRecipe WidenSelectR(*SelectI,
387                                    make_range(Args.begin(), Args.end()), false);
388   EXPECT_TRUE(isa<VPUser>(&WidenSelectR));
389   VPRecipeBase *BaseR = &WidenSelectR;
390   EXPECT_TRUE(isa<VPUser>(BaseR));
391   delete SelectI;
392 }
393 
394 TEST(VPRecipeTest, CastVPWidenGEPRecipeToVPUser) {
395   LLVMContext C;
396 
397   IntegerType *Int32 = IntegerType::get(C, 32);
398   PointerType *Int32Ptr = PointerType::get(Int32, 0);
399   auto *GEP = GetElementPtrInst::Create(Int32, UndefValue::get(Int32Ptr),
400                                         UndefValue::get(Int32));
401   VPValue Op1;
402   VPValue Op2;
403   SmallVector<VPValue *, 4> Args;
404   Args.push_back(&Op1);
405   Args.push_back(&Op2);
406   VPWidenGEPRecipe Recipe(GEP, make_range(Args.begin(), Args.end()));
407   EXPECT_TRUE(isa<VPUser>(&Recipe));
408   VPRecipeBase *BaseR = &Recipe;
409   EXPECT_TRUE(isa<VPUser>(BaseR));
410   delete GEP;
411 }
412 
413 TEST(VPRecipeTest, CastVPBlendRecipeToVPUser) {
414   LLVMContext C;
415 
416   IntegerType *Int32 = IntegerType::get(C, 32);
417   auto *Phi = PHINode::Create(Int32, 1);
418   VPValue Op1;
419   VPValue Op2;
420   SmallVector<VPValue *, 4> Args;
421   Args.push_back(&Op1);
422   Args.push_back(&Op2);
423   VPBlendRecipe Recipe(Phi, Args);
424   EXPECT_TRUE(isa<VPUser>(&Recipe));
425   VPRecipeBase *BaseR = &Recipe;
426   EXPECT_TRUE(isa<VPUser>(BaseR));
427   delete Phi;
428 }
429 
430 TEST(VPRecipeTest, CastVPInterleaveRecipeToVPUser) {
431   LLVMContext C;
432 
433   VPValue Addr;
434   VPValue Mask;
435   VPInterleaveRecipe Recipe(nullptr, &Addr, &Mask);
436   EXPECT_TRUE(isa<VPUser>(&Recipe));
437   VPRecipeBase *BaseR = &Recipe;
438   EXPECT_TRUE(isa<VPUser>(BaseR));
439 }
440 
441 TEST(VPRecipeTest, CastVPReplicateRecipeToVPUser) {
442   LLVMContext C;
443 
444   VPValue Op1;
445   VPValue Op2;
446   SmallVector<VPValue *, 4> Args;
447   Args.push_back(&Op1);
448   Args.push_back(&Op2);
449 
450   VPReplicateRecipe Recipe(nullptr, make_range(Args.begin(), Args.end()), true,
451                            false);
452   EXPECT_TRUE(isa<VPUser>(&Recipe));
453   VPRecipeBase *BaseR = &Recipe;
454   EXPECT_TRUE(isa<VPUser>(BaseR));
455 }
456 
457 TEST(VPRecipeTest, CastVPBranchOnMaskRecipeToVPUser) {
458   LLVMContext C;
459 
460   VPValue Mask;
461   VPBranchOnMaskRecipe Recipe(&Mask);
462   EXPECT_TRUE(isa<VPUser>(&Recipe));
463   VPRecipeBase *BaseR = &Recipe;
464   EXPECT_TRUE(isa<VPUser>(BaseR));
465 }
466 
467 TEST(VPRecipeTest, CastVPWidenMemoryInstructionRecipeToVPUser) {
468   LLVMContext C;
469 
470   IntegerType *Int32 = IntegerType::get(C, 32);
471   PointerType *Int32Ptr = PointerType::get(Int32, 0);
472   auto *Load =
473       new LoadInst(Int32, UndefValue::get(Int32Ptr), "", false, Align(1));
474   VPValue Addr;
475   VPValue Mask;
476   VPWidenMemoryInstructionRecipe Recipe(*Load, &Addr, &Mask);
477   EXPECT_TRUE(isa<VPUser>(&Recipe));
478   VPRecipeBase *BaseR = &Recipe;
479   EXPECT_TRUE(isa<VPUser>(BaseR));
480   delete Load;
481 }
482 
483 } // namespace
484 } // namespace llvm
485