xref: /llvm-project/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp (revision fa789dffb1e12c2aece0187aeacc48dfb1768340) 
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 "../lib/Transforms/Vectorize/VPlanCFG.h"
12 #include "llvm/ADT/DepthFirstIterator.h"
13 #include "llvm/ADT/PostOrderIterator.h"
14 #include "llvm/Analysis/VectorUtils.h"
15 #include "llvm/IR/Instruction.h"
16 #include "llvm/IR/Instructions.h"
17 #include "gtest/gtest.h"
18 #include <string>
19 
20 namespace llvm {
21 namespace {
22 
23 #define CHECK_ITERATOR(Range1, ...)                                            \
24   do {                                                                         \
25     std::vector<VPInstruction *> Tmp = {__VA_ARGS__};                          \
26     EXPECT_EQ((size_t)std::distance(Range1.begin(), Range1.end()),             \
27               Tmp.size());                                                     \
28     for (auto Pair : zip(Range1, make_range(Tmp.begin(), Tmp.end())))          \
29       EXPECT_EQ(&std::get<0>(Pair), std::get<1>(Pair));                        \
30   } while (0)
31 
32 TEST(VPInstructionTest, insertBefore) {
33   VPInstruction *I1 = new VPInstruction(0, {});
34   VPInstruction *I2 = new VPInstruction(1, {});
35   VPInstruction *I3 = new VPInstruction(2, {});
36 
37   VPBasicBlock VPBB1;
38   VPBB1.appendRecipe(I1);
39 
40   I2->insertBefore(I1);
41   CHECK_ITERATOR(VPBB1, I2, I1);
42 
43   I3->insertBefore(I2);
44   CHECK_ITERATOR(VPBB1, I3, I2, I1);
45 }
46 
47 TEST(VPInstructionTest, eraseFromParent) {
48   VPInstruction *I1 = new VPInstruction(0, {});
49   VPInstruction *I2 = new VPInstruction(1, {});
50   VPInstruction *I3 = new VPInstruction(2, {});
51 
52   VPBasicBlock VPBB1;
53   VPBB1.appendRecipe(I1);
54   VPBB1.appendRecipe(I2);
55   VPBB1.appendRecipe(I3);
56 
57   I2->eraseFromParent();
58   CHECK_ITERATOR(VPBB1, I1, I3);
59 
60   I1->eraseFromParent();
61   CHECK_ITERATOR(VPBB1, I3);
62 
63   I3->eraseFromParent();
64   EXPECT_TRUE(VPBB1.empty());
65 }
66 
67 TEST(VPInstructionTest, moveAfter) {
68   VPInstruction *I1 = new VPInstruction(0, {});
69   VPInstruction *I2 = new VPInstruction(1, {});
70   VPInstruction *I3 = new VPInstruction(2, {});
71 
72   VPBasicBlock VPBB1;
73   VPBB1.appendRecipe(I1);
74   VPBB1.appendRecipe(I2);
75   VPBB1.appendRecipe(I3);
76 
77   I1->moveAfter(I2);
78 
79   CHECK_ITERATOR(VPBB1, I2, I1, I3);
80 
81   VPInstruction *I4 = new VPInstruction(4, {});
82   VPInstruction *I5 = new VPInstruction(5, {});
83   VPBasicBlock VPBB2;
84   VPBB2.appendRecipe(I4);
85   VPBB2.appendRecipe(I5);
86 
87   I3->moveAfter(I4);
88 
89   CHECK_ITERATOR(VPBB1, I2, I1);
90   CHECK_ITERATOR(VPBB2, I4, I3, I5);
91   EXPECT_EQ(I3->getParent(), I4->getParent());
92 }
93 
94 TEST(VPInstructionTest, moveBefore) {
95   VPInstruction *I1 = new VPInstruction(0, {});
96   VPInstruction *I2 = new VPInstruction(1, {});
97   VPInstruction *I3 = new VPInstruction(2, {});
98 
99   VPBasicBlock VPBB1;
100   VPBB1.appendRecipe(I1);
101   VPBB1.appendRecipe(I2);
102   VPBB1.appendRecipe(I3);
103 
104   I1->moveBefore(VPBB1, I3->getIterator());
105 
106   CHECK_ITERATOR(VPBB1, I2, I1, I3);
107 
108   VPInstruction *I4 = new VPInstruction(4, {});
109   VPInstruction *I5 = new VPInstruction(5, {});
110   VPBasicBlock VPBB2;
111   VPBB2.appendRecipe(I4);
112   VPBB2.appendRecipe(I5);
113 
114   I3->moveBefore(VPBB2, I4->getIterator());
115 
116   CHECK_ITERATOR(VPBB1, I2, I1);
117   CHECK_ITERATOR(VPBB2, I3, I4, I5);
118   EXPECT_EQ(I3->getParent(), I4->getParent());
119 
120   VPBasicBlock VPBB3;
121 
122   I4->moveBefore(VPBB3, VPBB3.end());
123 
124   CHECK_ITERATOR(VPBB1, I2, I1);
125   CHECK_ITERATOR(VPBB2, I3, I5);
126   CHECK_ITERATOR(VPBB3, I4);
127   EXPECT_EQ(&VPBB3, I4->getParent());
128 }
129 
130 TEST(VPInstructionTest, setOperand) {
131   VPValue *VPV1 = new VPValue();
132   VPValue *VPV2 = new VPValue();
133   VPInstruction *I1 = new VPInstruction(0, {VPV1, VPV2});
134   EXPECT_EQ(1u, VPV1->getNumUsers());
135   EXPECT_EQ(I1, *VPV1->user_begin());
136   EXPECT_EQ(1u, VPV2->getNumUsers());
137   EXPECT_EQ(I1, *VPV2->user_begin());
138 
139   // Replace operand 0 (VPV1) with VPV3.
140   VPValue *VPV3 = new VPValue();
141   I1->setOperand(0, VPV3);
142   EXPECT_EQ(0u, VPV1->getNumUsers());
143   EXPECT_EQ(1u, VPV2->getNumUsers());
144   EXPECT_EQ(I1, *VPV2->user_begin());
145   EXPECT_EQ(1u, VPV3->getNumUsers());
146   EXPECT_EQ(I1, *VPV3->user_begin());
147 
148   // Replace operand 1 (VPV2) with VPV3.
149   I1->setOperand(1, VPV3);
150   EXPECT_EQ(0u, VPV1->getNumUsers());
151   EXPECT_EQ(0u, VPV2->getNumUsers());
152   EXPECT_EQ(2u, VPV3->getNumUsers());
153   EXPECT_EQ(I1, *VPV3->user_begin());
154   EXPECT_EQ(I1, *std::next(VPV3->user_begin()));
155 
156   // Replace operand 0 (VPV3) with VPV4.
157   VPValue *VPV4 = new VPValue();
158   I1->setOperand(0, VPV4);
159   EXPECT_EQ(1u, VPV3->getNumUsers());
160   EXPECT_EQ(I1, *VPV3->user_begin());
161   EXPECT_EQ(I1, *VPV4->user_begin());
162 
163   // Replace operand 1 (VPV3) with VPV4.
164   I1->setOperand(1, VPV4);
165   EXPECT_EQ(0u, VPV3->getNumUsers());
166   EXPECT_EQ(I1, *VPV4->user_begin());
167   EXPECT_EQ(I1, *std::next(VPV4->user_begin()));
168 
169   delete I1;
170   delete VPV1;
171   delete VPV2;
172   delete VPV3;
173   delete VPV4;
174 }
175 
176 TEST(VPInstructionTest, replaceAllUsesWith) {
177   VPValue *VPV1 = new VPValue();
178   VPValue *VPV2 = new VPValue();
179   VPInstruction *I1 = new VPInstruction(0, {VPV1, VPV2});
180 
181   // Replace all uses of VPV1 with VPV3.
182   VPValue *VPV3 = new VPValue();
183   VPV1->replaceAllUsesWith(VPV3);
184   EXPECT_EQ(VPV3, I1->getOperand(0));
185   EXPECT_EQ(VPV2, I1->getOperand(1));
186   EXPECT_EQ(0u, VPV1->getNumUsers());
187   EXPECT_EQ(1u, VPV2->getNumUsers());
188   EXPECT_EQ(I1, *VPV2->user_begin());
189   EXPECT_EQ(1u, VPV3->getNumUsers());
190   EXPECT_EQ(I1, *VPV3->user_begin());
191 
192   // Replace all uses of VPV2 with VPV3.
193   VPV2->replaceAllUsesWith(VPV3);
194   EXPECT_EQ(VPV3, I1->getOperand(0));
195   EXPECT_EQ(VPV3, I1->getOperand(1));
196   EXPECT_EQ(0u, VPV1->getNumUsers());
197   EXPECT_EQ(0u, VPV2->getNumUsers());
198   EXPECT_EQ(2u, VPV3->getNumUsers());
199   EXPECT_EQ(I1, *VPV3->user_begin());
200 
201   // Replace all uses of VPV3 with VPV1.
202   VPV3->replaceAllUsesWith(VPV1);
203   EXPECT_EQ(VPV1, I1->getOperand(0));
204   EXPECT_EQ(VPV1, I1->getOperand(1));
205   EXPECT_EQ(2u, VPV1->getNumUsers());
206   EXPECT_EQ(I1, *VPV1->user_begin());
207   EXPECT_EQ(0u, VPV2->getNumUsers());
208   EXPECT_EQ(0u, VPV3->getNumUsers());
209 
210   VPInstruction *I2 = new VPInstruction(0, {VPV1, VPV2});
211   EXPECT_EQ(3u, VPV1->getNumUsers());
212   VPV1->replaceAllUsesWith(VPV3);
213   EXPECT_EQ(3u, VPV3->getNumUsers());
214 
215   delete I1;
216   delete I2;
217   delete VPV1;
218   delete VPV2;
219   delete VPV3;
220 }
221 
222 TEST(VPInstructionTest, releaseOperandsAtDeletion) {
223   VPValue *VPV1 = new VPValue();
224   VPValue *VPV2 = new VPValue();
225   VPInstruction *I1 = new VPInstruction(0, {VPV1, VPV2});
226 
227   EXPECT_EQ(1u, VPV1->getNumUsers());
228   EXPECT_EQ(I1, *VPV1->user_begin());
229   EXPECT_EQ(1u, VPV2->getNumUsers());
230   EXPECT_EQ(I1, *VPV2->user_begin());
231 
232   delete I1;
233 
234   EXPECT_EQ(0u, VPV1->getNumUsers());
235   EXPECT_EQ(0u, VPV2->getNumUsers());
236 
237   delete VPV1;
238   delete VPV2;
239 }
240 TEST(VPBasicBlockTest, getPlan) {
241   {
242     VPBasicBlock *VPPH = new VPBasicBlock("ph");
243     VPBasicBlock *VPBB1 = new VPBasicBlock();
244     VPBasicBlock *VPBB2 = new VPBasicBlock();
245     VPBasicBlock *VPBB3 = new VPBasicBlock();
246     VPBasicBlock *VPBB4 = new VPBasicBlock();
247 
248     //     VPBB1
249     //     /   \
250     // VPBB2  VPBB3
251     //    \    /
252     //    VPBB4
253     VPBlockUtils::connectBlocks(VPBB1, VPBB2);
254     VPBlockUtils::connectBlocks(VPBB1, VPBB3);
255     VPBlockUtils::connectBlocks(VPBB2, VPBB4);
256     VPBlockUtils::connectBlocks(VPBB3, VPBB4);
257 
258     auto TC = std::make_unique<VPValue>();
259     VPlan Plan(VPPH, &*TC, VPBB1);
260 
261     EXPECT_EQ(&Plan, VPBB1->getPlan());
262     EXPECT_EQ(&Plan, VPBB2->getPlan());
263     EXPECT_EQ(&Plan, VPBB3->getPlan());
264     EXPECT_EQ(&Plan, VPBB4->getPlan());
265   }
266 
267   {
268     VPBasicBlock *VPPH = new VPBasicBlock("ph");
269     // VPBasicBlock is the entry into the VPlan, followed by a region.
270     VPBasicBlock *R1BB1 = new VPBasicBlock();
271     VPBasicBlock *R1BB2 = new VPBasicBlock();
272     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB2, "R1");
273     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
274 
275     VPBasicBlock *VPBB1 = new VPBasicBlock();
276     VPBlockUtils::connectBlocks(VPBB1, R1);
277 
278     auto TC = std::make_unique<VPValue>();
279     VPlan Plan(VPPH, &*TC, VPBB1);
280 
281     EXPECT_EQ(&Plan, VPBB1->getPlan());
282     EXPECT_EQ(&Plan, R1->getPlan());
283     EXPECT_EQ(&Plan, R1BB1->getPlan());
284     EXPECT_EQ(&Plan, R1BB2->getPlan());
285   }
286 
287   {
288     VPBasicBlock *VPPH = new VPBasicBlock("ph");
289 
290     VPBasicBlock *R1BB1 = new VPBasicBlock();
291     VPBasicBlock *R1BB2 = new VPBasicBlock();
292     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB2, "R1");
293     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
294 
295     VPBasicBlock *R2BB1 = new VPBasicBlock();
296     VPBasicBlock *R2BB2 = new VPBasicBlock();
297     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
298     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
299 
300     VPBasicBlock *VPBB1 = new VPBasicBlock();
301     VPBlockUtils::connectBlocks(VPBB1, R1);
302     VPBlockUtils::connectBlocks(VPBB1, R2);
303 
304     VPBasicBlock *VPBB2 = new VPBasicBlock();
305     VPBlockUtils::connectBlocks(R1, VPBB2);
306     VPBlockUtils::connectBlocks(R2, VPBB2);
307 
308     auto TC = std::make_unique<VPValue>();
309     VPlan Plan(VPPH, &*TC, VPBB1);
310 
311     EXPECT_EQ(&Plan, VPBB1->getPlan());
312     EXPECT_EQ(&Plan, R1->getPlan());
313     EXPECT_EQ(&Plan, R1BB1->getPlan());
314     EXPECT_EQ(&Plan, R1BB2->getPlan());
315     EXPECT_EQ(&Plan, R2->getPlan());
316     EXPECT_EQ(&Plan, R2BB1->getPlan());
317     EXPECT_EQ(&Plan, R2BB2->getPlan());
318     EXPECT_EQ(&Plan, VPBB2->getPlan());
319   }
320 }
321 
322 TEST(VPBasicBlockTest, TraversingIteratorTest) {
323   {
324     // VPBasicBlocks only
325     //     VPBB1
326     //     /   \
327     // VPBB2  VPBB3
328     //    \    /
329     //    VPBB4
330     //
331     VPBasicBlock *VPPH = new VPBasicBlock("ph");
332     VPBasicBlock *VPBB1 = new VPBasicBlock();
333     VPBasicBlock *VPBB2 = new VPBasicBlock();
334     VPBasicBlock *VPBB3 = new VPBasicBlock();
335     VPBasicBlock *VPBB4 = new VPBasicBlock();
336 
337     VPBlockUtils::connectBlocks(VPBB1, VPBB2);
338     VPBlockUtils::connectBlocks(VPBB1, VPBB3);
339     VPBlockUtils::connectBlocks(VPBB2, VPBB4);
340     VPBlockUtils::connectBlocks(VPBB3, VPBB4);
341 
342     VPBlockDeepTraversalWrapper<const VPBlockBase *> Start(VPBB1);
343     SmallVector<const VPBlockBase *> FromIterator(depth_first(Start));
344     EXPECT_EQ(4u, FromIterator.size());
345     EXPECT_EQ(VPBB1, FromIterator[0]);
346     EXPECT_EQ(VPBB2, FromIterator[1]);
347 
348     // Use Plan to properly clean up created blocks.
349     auto TC = std::make_unique<VPValue>();
350     VPlan Plan(VPPH, &*TC, VPBB1);
351   }
352 
353   {
354     // 2 consecutive regions.
355     // VPBB0
356     //  |
357     // R1 {
358     //     \
359     //     R1BB1
360     //    /     \   |--|
361     //  R1BB2   R1BB3 -|
362     //    \      /
363     //     R1BB4
364     //  }
365     //   |
366     // R2 {
367     //   \
368     //    R2BB1
369     //      |
370     //    R2BB2
371     //
372     VPBasicBlock *VPPH = new VPBasicBlock("ph");
373     VPBasicBlock *VPBB0 = new VPBasicBlock("VPBB0");
374     VPBasicBlock *R1BB1 = new VPBasicBlock();
375     VPBasicBlock *R1BB2 = new VPBasicBlock();
376     VPBasicBlock *R1BB3 = new VPBasicBlock();
377     VPBasicBlock *R1BB4 = new VPBasicBlock();
378     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB4, "R1");
379     R1BB2->setParent(R1);
380     R1BB3->setParent(R1);
381     VPBlockUtils::connectBlocks(VPBB0, R1);
382     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
383     VPBlockUtils::connectBlocks(R1BB1, R1BB3);
384     VPBlockUtils::connectBlocks(R1BB2, R1BB4);
385     VPBlockUtils::connectBlocks(R1BB3, R1BB4);
386     // Cycle.
387     VPBlockUtils::connectBlocks(R1BB3, R1BB3);
388 
389     VPBasicBlock *R2BB1 = new VPBasicBlock();
390     VPBasicBlock *R2BB2 = new VPBasicBlock();
391     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
392     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
393     VPBlockUtils::connectBlocks(R1, R2);
394 
395     // Successors of R1.
396     SmallVector<const VPBlockBase *> FromIterator(
397         VPAllSuccessorsIterator<VPBlockBase *>(R1),
398         VPAllSuccessorsIterator<VPBlockBase *>::end(R1));
399     EXPECT_EQ(1u, FromIterator.size());
400     EXPECT_EQ(R1BB1, FromIterator[0]);
401 
402     // Depth-first.
403     VPBlockDeepTraversalWrapper<VPBlockBase *> Start(R1);
404     FromIterator.clear();
405     copy(df_begin(Start), df_end(Start), std::back_inserter(FromIterator));
406     EXPECT_EQ(8u, FromIterator.size());
407     EXPECT_EQ(R1, FromIterator[0]);
408     EXPECT_EQ(R1BB1, FromIterator[1]);
409     EXPECT_EQ(R1BB2, FromIterator[2]);
410     EXPECT_EQ(R1BB4, FromIterator[3]);
411     EXPECT_EQ(R2, FromIterator[4]);
412     EXPECT_EQ(R2BB1, FromIterator[5]);
413     EXPECT_EQ(R2BB2, FromIterator[6]);
414     EXPECT_EQ(R1BB3, FromIterator[7]);
415 
416     // const VPBasicBlocks only.
417     FromIterator.clear();
418     copy(VPBlockUtils::blocksOnly<const VPBasicBlock>(depth_first(Start)),
419          std::back_inserter(FromIterator));
420     EXPECT_EQ(6u, FromIterator.size());
421     EXPECT_EQ(R1BB1, FromIterator[0]);
422     EXPECT_EQ(R1BB2, FromIterator[1]);
423     EXPECT_EQ(R1BB4, FromIterator[2]);
424     EXPECT_EQ(R2BB1, FromIterator[3]);
425     EXPECT_EQ(R2BB2, FromIterator[4]);
426     EXPECT_EQ(R1BB3, FromIterator[5]);
427 
428     // VPRegionBlocks only.
429     SmallVector<VPRegionBlock *> FromIteratorVPRegion(
430         VPBlockUtils::blocksOnly<VPRegionBlock>(depth_first(Start)));
431     EXPECT_EQ(2u, FromIteratorVPRegion.size());
432     EXPECT_EQ(R1, FromIteratorVPRegion[0]);
433     EXPECT_EQ(R2, FromIteratorVPRegion[1]);
434 
435     // Post-order.
436     FromIterator.clear();
437     copy(post_order(Start), std::back_inserter(FromIterator));
438     EXPECT_EQ(8u, FromIterator.size());
439     EXPECT_EQ(R2BB2, FromIterator[0]);
440     EXPECT_EQ(R2BB1, FromIterator[1]);
441     EXPECT_EQ(R2, FromIterator[2]);
442     EXPECT_EQ(R1BB4, FromIterator[3]);
443     EXPECT_EQ(R1BB2, FromIterator[4]);
444     EXPECT_EQ(R1BB3, FromIterator[5]);
445     EXPECT_EQ(R1BB1, FromIterator[6]);
446     EXPECT_EQ(R1, FromIterator[7]);
447 
448     // Use Plan to properly clean up created blocks.
449     auto TC = std::make_unique<VPValue>();
450     VPlan Plan(VPPH, &*TC, VPBB0);
451   }
452 
453   {
454     // 2 nested regions.
455     //  VPBB1
456     //    |
457     //  R1 {
458     //         R1BB1
459     //       /        \
460     //   R2 {          |
461     //     \           |
462     //     R2BB1       |
463     //       |   \    R1BB2
464     //     R2BB2-|     |
465     //        \        |
466     //         R2BB3   |
467     //   }            /
468     //      \        /
469     //        R1BB3
470     //  }
471     //   |
472     //  VPBB2
473     //
474     VPBasicBlock *VPPH = new VPBasicBlock("ph");
475     VPBasicBlock *R1BB1 = new VPBasicBlock("R1BB1");
476     VPBasicBlock *R1BB2 = new VPBasicBlock("R1BB2");
477     VPBasicBlock *R1BB3 = new VPBasicBlock("R1BB3");
478     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB3, "R1");
479 
480     VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
481     VPBasicBlock *R2BB2 = new VPBasicBlock("R2BB2");
482     VPBasicBlock *R2BB3 = new VPBasicBlock("R2BB3");
483     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB3, "R2");
484     R2BB2->setParent(R2);
485     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
486     VPBlockUtils::connectBlocks(R2BB2, R2BB1);
487     VPBlockUtils::connectBlocks(R2BB2, R2BB3);
488 
489     R2->setParent(R1);
490     VPBlockUtils::connectBlocks(R1BB1, R2);
491     R1BB2->setParent(R1);
492     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
493     VPBlockUtils::connectBlocks(R1BB2, R1BB3);
494     VPBlockUtils::connectBlocks(R2, R1BB3);
495 
496     VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
497     VPBlockUtils::connectBlocks(VPBB1, R1);
498     VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
499     VPBlockUtils::connectBlocks(R1, VPBB2);
500 
501     // Depth-first.
502     VPBlockDeepTraversalWrapper<VPBlockBase *> Start(VPBB1);
503     SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
504     EXPECT_EQ(10u, FromIterator.size());
505     EXPECT_EQ(VPBB1, FromIterator[0]);
506     EXPECT_EQ(R1, FromIterator[1]);
507     EXPECT_EQ(R1BB1, FromIterator[2]);
508     EXPECT_EQ(R2, FromIterator[3]);
509     EXPECT_EQ(R2BB1, FromIterator[4]);
510     EXPECT_EQ(R2BB2, FromIterator[5]);
511     EXPECT_EQ(R2BB3, FromIterator[6]);
512     EXPECT_EQ(R1BB3, FromIterator[7]);
513     EXPECT_EQ(VPBB2, FromIterator[8]);
514     EXPECT_EQ(R1BB2, FromIterator[9]);
515 
516     // Post-order.
517     FromIterator.clear();
518     FromIterator.append(po_begin(Start), po_end(Start));
519     EXPECT_EQ(10u, FromIterator.size());
520     EXPECT_EQ(VPBB2, FromIterator[0]);
521     EXPECT_EQ(R1BB3, FromIterator[1]);
522     EXPECT_EQ(R2BB3, FromIterator[2]);
523     EXPECT_EQ(R2BB2, FromIterator[3]);
524     EXPECT_EQ(R2BB1, FromIterator[4]);
525     EXPECT_EQ(R2, FromIterator[5]);
526     EXPECT_EQ(R1BB2, FromIterator[6]);
527     EXPECT_EQ(R1BB1, FromIterator[7]);
528     EXPECT_EQ(R1, FromIterator[8]);
529     EXPECT_EQ(VPBB1, FromIterator[9]);
530 
531     // Use Plan to properly clean up created blocks.
532     auto TC = std::make_unique<VPValue>();
533     VPlan Plan(VPPH, &*TC, VPBB1);
534   }
535 
536   {
537     //  VPBB1
538     //    |
539     //  R1 {
540     //    \
541     //     R2 {
542     //      R2BB1
543     //        |
544     //      R2BB2
545     //   }
546     //
547     VPBasicBlock *VPPH = new VPBasicBlock("ph");
548     VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
549     VPBasicBlock *R2BB2 = new VPBasicBlock("R2BB2");
550     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
551     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
552 
553     VPRegionBlock *R1 = new VPRegionBlock(R2, R2, "R1");
554     R2->setParent(R1);
555 
556     VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
557     VPBlockUtils::connectBlocks(VPBB1, R1);
558 
559     // Depth-first.
560     VPBlockDeepTraversalWrapper<VPBlockBase *> Start(VPBB1);
561     SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
562     EXPECT_EQ(5u, FromIterator.size());
563     EXPECT_EQ(VPBB1, FromIterator[0]);
564     EXPECT_EQ(R1, FromIterator[1]);
565     EXPECT_EQ(R2, FromIterator[2]);
566     EXPECT_EQ(R2BB1, FromIterator[3]);
567     EXPECT_EQ(R2BB2, FromIterator[4]);
568 
569     // Post-order.
570     FromIterator.clear();
571     FromIterator.append(po_begin(Start), po_end(Start));
572     EXPECT_EQ(5u, FromIterator.size());
573     EXPECT_EQ(R2BB2, FromIterator[0]);
574     EXPECT_EQ(R2BB1, FromIterator[1]);
575     EXPECT_EQ(R2, FromIterator[2]);
576     EXPECT_EQ(R1, FromIterator[3]);
577     EXPECT_EQ(VPBB1, FromIterator[4]);
578 
579     // Use Plan to properly clean up created blocks.
580     auto TC = std::make_unique<VPValue>();
581     VPlan Plan(VPPH, &*TC, VPBB1);
582   }
583 
584   {
585     //  Nested regions with both R3 and R2 being exit nodes without successors.
586     //  The successors of R1 should be used.
587     //
588     //  VPBB1
589     //    |
590     //  R1 {
591     //    \
592     //     R2 {
593     //      \
594     //      R2BB1
595     //        |
596     //       R3 {
597     //          R3BB1
598     //      }
599     //   }
600     //   |
601     //  VPBB2
602     //
603     VPBasicBlock *VPPH = new VPBasicBlock("ph");
604     VPBasicBlock *R3BB1 = new VPBasicBlock("R3BB1");
605     VPRegionBlock *R3 = new VPRegionBlock(R3BB1, R3BB1, "R3");
606 
607     VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
608     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R3, "R2");
609     R3->setParent(R2);
610     VPBlockUtils::connectBlocks(R2BB1, R3);
611 
612     VPRegionBlock *R1 = new VPRegionBlock(R2, R2, "R1");
613     R2->setParent(R1);
614 
615     VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
616     VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
617     VPBlockUtils::connectBlocks(VPBB1, R1);
618     VPBlockUtils::connectBlocks(R1, VPBB2);
619 
620     // Depth-first.
621     VPBlockDeepTraversalWrapper<VPBlockBase *> Start(VPBB1);
622     SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
623     EXPECT_EQ(7u, FromIterator.size());
624     EXPECT_EQ(VPBB1, FromIterator[0]);
625     EXPECT_EQ(R1, FromIterator[1]);
626     EXPECT_EQ(R2, FromIterator[2]);
627     EXPECT_EQ(R2BB1, FromIterator[3]);
628     EXPECT_EQ(R3, FromIterator[4]);
629     EXPECT_EQ(R3BB1, FromIterator[5]);
630     EXPECT_EQ(VPBB2, FromIterator[6]);
631 
632     SmallVector<VPBlockBase *> FromIteratorVPBB;
633     copy(VPBlockUtils::blocksOnly<VPBasicBlock>(depth_first(Start)),
634          std::back_inserter(FromIteratorVPBB));
635     EXPECT_EQ(VPBB1, FromIteratorVPBB[0]);
636     EXPECT_EQ(R2BB1, FromIteratorVPBB[1]);
637     EXPECT_EQ(R3BB1, FromIteratorVPBB[2]);
638     EXPECT_EQ(VPBB2, FromIteratorVPBB[3]);
639 
640     // Post-order.
641     FromIterator.clear();
642     copy(post_order(Start), std::back_inserter(FromIterator));
643     EXPECT_EQ(7u, FromIterator.size());
644     EXPECT_EQ(VPBB2, FromIterator[0]);
645     EXPECT_EQ(R3BB1, FromIterator[1]);
646     EXPECT_EQ(R3, FromIterator[2]);
647     EXPECT_EQ(R2BB1, FromIterator[3]);
648     EXPECT_EQ(R2, FromIterator[4]);
649     EXPECT_EQ(R1, FromIterator[5]);
650     EXPECT_EQ(VPBB1, FromIterator[6]);
651 
652     // Post-order, const VPRegionBlocks only.
653     VPBlockDeepTraversalWrapper<const VPBlockBase *> StartConst(VPBB1);
654     SmallVector<const VPRegionBlock *> FromIteratorVPRegion(
655         VPBlockUtils::blocksOnly<const VPRegionBlock>(post_order(StartConst)));
656     EXPECT_EQ(3u, FromIteratorVPRegion.size());
657     EXPECT_EQ(R3, FromIteratorVPRegion[0]);
658     EXPECT_EQ(R2, FromIteratorVPRegion[1]);
659     EXPECT_EQ(R1, FromIteratorVPRegion[2]);
660 
661     // Post-order, VPBasicBlocks only.
662     FromIterator.clear();
663     copy(VPBlockUtils::blocksOnly<VPBasicBlock>(post_order(Start)),
664          std::back_inserter(FromIterator));
665     EXPECT_EQ(FromIterator.size(), 4u);
666     EXPECT_EQ(VPBB2, FromIterator[0]);
667     EXPECT_EQ(R3BB1, FromIterator[1]);
668     EXPECT_EQ(R2BB1, FromIterator[2]);
669     EXPECT_EQ(VPBB1, FromIterator[3]);
670 
671     // Use Plan to properly clean up created blocks.
672     auto TC = std::make_unique<VPValue>();
673     VPlan Plan(VPPH, &*TC, VPBB1);
674   }
675 }
676 
677 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
678 TEST(VPBasicBlockTest, print) {
679   VPInstruction *TC = new VPInstruction(Instruction::Add, {});
680   VPBasicBlock *VPBB0 = new VPBasicBlock("preheader");
681   VPBB0->appendRecipe(TC);
682 
683   VPInstruction *I1 = new VPInstruction(Instruction::Add, {});
684   VPInstruction *I2 = new VPInstruction(Instruction::Sub, {I1});
685   VPInstruction *I3 = new VPInstruction(Instruction::Br, {I1, I2});
686 
687   VPBasicBlock *VPBB1 = new VPBasicBlock();
688   VPBB1->appendRecipe(I1);
689   VPBB1->appendRecipe(I2);
690   VPBB1->appendRecipe(I3);
691   VPBB1->setName("bb1");
692 
693   VPInstruction *I4 = new VPInstruction(Instruction::Mul, {I2, I1});
694   VPInstruction *I5 = new VPInstruction(Instruction::Ret, {I4});
695   VPBasicBlock *VPBB2 = new VPBasicBlock();
696   VPBB2->appendRecipe(I4);
697   VPBB2->appendRecipe(I5);
698   VPBB2->setName("bb2");
699 
700   VPBlockUtils::connectBlocks(VPBB1, VPBB2);
701 
702   // Check printing an instruction without associated VPlan.
703   {
704     std::string I3Dump;
705     raw_string_ostream OS(I3Dump);
706     VPSlotTracker SlotTracker;
707     I3->print(OS, "", SlotTracker);
708     EXPECT_EQ("EMIT br <badref>, <badref>", I3Dump);
709   }
710 
711   VPlan Plan(VPBB0, TC, VPBB1);
712   std::string FullDump;
713   raw_string_ostream OS(FullDump);
714   Plan.printDOT(OS);
715 
716   const char *ExpectedStr = R"(digraph VPlan {
717 graph [labelloc=t, fontsize=30; label="Vectorization Plan\n for UF\>=1\nvp\<%1\> = original trip-count\n"]
718 node [shape=rect, fontname=Courier, fontsize=30]
719 edge [fontname=Courier, fontsize=30]
720 compound=true
721   N0 [label =
722     "preheader:\l" +
723     "  EMIT vp\<%1\> = add\l" +
724     "No successors\l"
725   ]
726   N1 [label =
727     "bb1:\l" +
728     "  EMIT vp\<%2\> = add\l" +
729     "  EMIT vp\<%3\> = sub vp\<%2\>\l" +
730     "  EMIT br vp\<%2\>, vp\<%3\>\l" +
731     "Successor(s): bb2\l"
732   ]
733   N1 -> N2 [ label=""]
734   N2 [label =
735     "bb2:\l" +
736     "  EMIT vp\<%5\> = mul vp\<%3\>, vp\<%2\>\l" +
737     "  EMIT ret vp\<%5\>\l" +
738     "No successors\l"
739   ]
740 }
741 )";
742   EXPECT_EQ(ExpectedStr, FullDump);
743 
744   const char *ExpectedBlock1Str = R"(bb1:
745   EMIT vp<%2> = add
746   EMIT vp<%3> = sub vp<%2>
747   EMIT br vp<%2>, vp<%3>
748 Successor(s): bb2
749 )";
750   std::string Block1Dump;
751   raw_string_ostream OS1(Block1Dump);
752   VPBB1->print(OS1);
753   EXPECT_EQ(ExpectedBlock1Str, Block1Dump);
754 
755   // Ensure that numbering is good when dumping the second block in isolation.
756   const char *ExpectedBlock2Str = R"(bb2:
757   EMIT vp<%5> = mul vp<%3>, vp<%2>
758   EMIT ret vp<%5>
759 No successors
760 )";
761   std::string Block2Dump;
762   raw_string_ostream OS2(Block2Dump);
763   VPBB2->print(OS2);
764   EXPECT_EQ(ExpectedBlock2Str, Block2Dump);
765 
766   {
767     std::string I3Dump;
768     raw_string_ostream OS(I3Dump);
769     VPSlotTracker SlotTracker(&Plan);
770     I3->print(OS, "", SlotTracker);
771     EXPECT_EQ("EMIT br vp<%2>, vp<%3>", I3Dump);
772   }
773 
774   {
775     std::string I4Dump;
776     raw_string_ostream OS(I4Dump);
777     OS << *I4;
778     EXPECT_EQ("EMIT vp<%5> = mul vp<%3>, vp<%2>", I4Dump);
779   }
780 }
781 
782 TEST(VPBasicBlockTest, printPlanWithVFsAndUFs) {
783 
784   VPInstruction *TC = new VPInstruction(Instruction::Sub, {});
785   VPBasicBlock *VPBB0 = new VPBasicBlock("preheader");
786   VPBB0->appendRecipe(TC);
787 
788   VPInstruction *I1 = new VPInstruction(Instruction::Add, {});
789   VPBasicBlock *VPBB1 = new VPBasicBlock();
790   VPBB1->appendRecipe(I1);
791   VPBB1->setName("bb1");
792 
793   VPlan Plan(VPBB0, TC, VPBB1);
794   Plan.setName("TestPlan");
795   Plan.addVF(ElementCount::getFixed(4));
796 
797   {
798     std::string FullDump;
799     raw_string_ostream OS(FullDump);
800     Plan.print(OS);
801 
802     const char *ExpectedStr = R"(VPlan 'TestPlan for VF={4},UF>=1' {
803 vp<%1> = original trip-count
804 
805 preheader:
806   EMIT vp<%1> = sub
807 No successors
808 
809 bb1:
810   EMIT vp<%2> = add
811 No successors
812 }
813 )";
814     EXPECT_EQ(ExpectedStr, FullDump);
815   }
816 
817   {
818     Plan.addVF(ElementCount::getScalable(8));
819     std::string FullDump;
820     raw_string_ostream OS(FullDump);
821     Plan.print(OS);
822 
823     const char *ExpectedStr = R"(VPlan 'TestPlan for VF={4,vscale x 8},UF>=1' {
824 vp<%1> = original trip-count
825 
826 preheader:
827   EMIT vp<%1> = sub
828 No successors
829 
830 bb1:
831   EMIT vp<%2> = add
832 No successors
833 }
834 )";
835     EXPECT_EQ(ExpectedStr, FullDump);
836   }
837 
838   {
839     Plan.setUF(4);
840     std::string FullDump;
841     raw_string_ostream OS(FullDump);
842     Plan.print(OS);
843 
844     const char *ExpectedStr = R"(VPlan 'TestPlan for VF={4,vscale x 8},UF={4}' {
845 vp<%1> = original trip-count
846 
847 preheader:
848   EMIT vp<%1> = sub
849 No successors
850 
851 bb1:
852   EMIT vp<%2> = add
853 No successors
854 }
855 )";
856     EXPECT_EQ(ExpectedStr, FullDump);
857   }
858 }
859 #endif
860 
861 TEST(VPRecipeTest, CastVPInstructionToVPUser) {
862   VPValue Op1;
863   VPValue Op2;
864   VPInstruction Recipe(Instruction::Add, {&Op1, &Op2});
865   EXPECT_TRUE(isa<VPUser>(&Recipe));
866   VPRecipeBase *BaseR = &Recipe;
867   EXPECT_TRUE(isa<VPUser>(BaseR));
868   EXPECT_EQ(&Recipe, BaseR);
869 }
870 
871 TEST(VPRecipeTest, CastVPWidenRecipeToVPUser) {
872   LLVMContext C;
873 
874   IntegerType *Int32 = IntegerType::get(C, 32);
875   auto *AI = BinaryOperator::CreateAdd(PoisonValue::get(Int32),
876                                        PoisonValue::get(Int32));
877   VPValue Op1;
878   VPValue Op2;
879   SmallVector<VPValue *, 2> Args;
880   Args.push_back(&Op1);
881   Args.push_back(&Op1);
882   VPWidenRecipe WidenR(*AI, make_range(Args.begin(), Args.end()));
883   EXPECT_TRUE(isa<VPUser>(&WidenR));
884   VPRecipeBase *WidenRBase = &WidenR;
885   EXPECT_TRUE(isa<VPUser>(WidenRBase));
886   EXPECT_EQ(&WidenR, WidenRBase);
887   delete AI;
888 }
889 
890 TEST(VPRecipeTest, CastVPWidenCallRecipeToVPUserAndVPDef) {
891   LLVMContext C;
892 
893   IntegerType *Int32 = IntegerType::get(C, 32);
894   FunctionType *FTy = FunctionType::get(Int32, false);
895   Function *Fn = Function::Create(FTy, GlobalValue::ExternalLinkage, 0);
896   auto *Call = CallInst::Create(FTy, Fn);
897   VPValue Op1;
898   VPValue Op2;
899   VPValue CalledFn(Call->getCalledFunction());
900   SmallVector<VPValue *, 2> Args;
901   Args.push_back(&Op1);
902   Args.push_back(&Op2);
903   Args.push_back(&CalledFn);
904   VPWidenCallRecipe Recipe(Call, Fn, Args);
905   EXPECT_TRUE(isa<VPUser>(&Recipe));
906   VPRecipeBase *BaseR = &Recipe;
907   EXPECT_TRUE(isa<VPUser>(BaseR));
908   EXPECT_EQ(&Recipe, BaseR);
909 
910   VPValue *VPV = &Recipe;
911   EXPECT_TRUE(VPV->getDefiningRecipe());
912   EXPECT_EQ(&Recipe, VPV->getDefiningRecipe());
913 
914   delete Call;
915   delete Fn;
916 }
917 
918 TEST(VPRecipeTest, CastVPWidenSelectRecipeToVPUserAndVPDef) {
919   LLVMContext C;
920 
921   IntegerType *Int1 = IntegerType::get(C, 1);
922   IntegerType *Int32 = IntegerType::get(C, 32);
923   auto *SelectI = SelectInst::Create(
924       PoisonValue::get(Int1), PoisonValue::get(Int32), PoisonValue::get(Int32));
925   VPValue Op1;
926   VPValue Op2;
927   VPValue Op3;
928   SmallVector<VPValue *, 4> Args;
929   Args.push_back(&Op1);
930   Args.push_back(&Op2);
931   Args.push_back(&Op3);
932   VPWidenSelectRecipe WidenSelectR(*SelectI,
933                                    make_range(Args.begin(), Args.end()));
934   EXPECT_TRUE(isa<VPUser>(&WidenSelectR));
935   VPRecipeBase *BaseR = &WidenSelectR;
936   EXPECT_TRUE(isa<VPUser>(BaseR));
937   EXPECT_EQ(&WidenSelectR, BaseR);
938 
939   VPValue *VPV = &WidenSelectR;
940   EXPECT_TRUE(isa<VPRecipeBase>(VPV->getDefiningRecipe()));
941   EXPECT_EQ(&WidenSelectR, VPV->getDefiningRecipe());
942 
943   delete SelectI;
944 }
945 
946 TEST(VPRecipeTest, CastVPWidenGEPRecipeToVPUserAndVPDef) {
947   LLVMContext C;
948 
949   IntegerType *Int32 = IntegerType::get(C, 32);
950   PointerType *Int32Ptr = PointerType::get(Int32, 0);
951   auto *GEP = GetElementPtrInst::Create(Int32, PoisonValue::get(Int32Ptr),
952                                         PoisonValue::get(Int32));
953   VPValue Op1;
954   VPValue Op2;
955   SmallVector<VPValue *, 4> Args;
956   Args.push_back(&Op1);
957   Args.push_back(&Op2);
958   VPWidenGEPRecipe Recipe(GEP, make_range(Args.begin(), Args.end()));
959   EXPECT_TRUE(isa<VPUser>(&Recipe));
960   VPRecipeBase *BaseR = &Recipe;
961   EXPECT_TRUE(isa<VPUser>(BaseR));
962   EXPECT_EQ(&Recipe, BaseR);
963 
964   VPValue *VPV = &Recipe;
965   EXPECT_TRUE(isa<VPRecipeBase>(VPV->getDefiningRecipe()));
966   EXPECT_EQ(&Recipe, VPV->getDefiningRecipe());
967 
968   delete GEP;
969 }
970 
971 TEST(VPRecipeTest, CastVPBlendRecipeToVPUser) {
972   LLVMContext C;
973 
974   IntegerType *Int32 = IntegerType::get(C, 32);
975   auto *Phi = PHINode::Create(Int32, 1);
976   VPValue I1;
977   VPValue I2;
978   VPValue M2;
979   SmallVector<VPValue *, 4> Args;
980   Args.push_back(&I1);
981   Args.push_back(&I2);
982   Args.push_back(&M2);
983   VPBlendRecipe Recipe(Phi, Args);
984   EXPECT_TRUE(isa<VPUser>(&Recipe));
985   VPRecipeBase *BaseR = &Recipe;
986   EXPECT_TRUE(isa<VPUser>(BaseR));
987   delete Phi;
988 }
989 
990 TEST(VPRecipeTest, CastVPInterleaveRecipeToVPUser) {
991   LLVMContext C;
992 
993   VPValue Addr;
994   VPValue Mask;
995   InterleaveGroup<Instruction> IG(4, false, Align(4));
996   VPInterleaveRecipe Recipe(&IG, &Addr, {}, &Mask, false);
997   EXPECT_TRUE(isa<VPUser>(&Recipe));
998   VPRecipeBase *BaseR = &Recipe;
999   EXPECT_TRUE(isa<VPUser>(BaseR));
1000   EXPECT_EQ(&Recipe, BaseR);
1001 }
1002 
1003 TEST(VPRecipeTest, CastVPReplicateRecipeToVPUser) {
1004   LLVMContext C;
1005 
1006   VPValue Op1;
1007   VPValue Op2;
1008   SmallVector<VPValue *, 4> Args;
1009   Args.push_back(&Op1);
1010   Args.push_back(&Op2);
1011 
1012   IntegerType *Int32 = IntegerType::get(C, 32);
1013   FunctionType *FTy = FunctionType::get(Int32, false);
1014   auto *Call = CallInst::Create(FTy, PoisonValue::get(FTy));
1015   VPReplicateRecipe Recipe(Call, make_range(Args.begin(), Args.end()), true);
1016   EXPECT_TRUE(isa<VPUser>(&Recipe));
1017   VPRecipeBase *BaseR = &Recipe;
1018   EXPECT_TRUE(isa<VPUser>(BaseR));
1019   delete Call;
1020 }
1021 
1022 TEST(VPRecipeTest, CastVPBranchOnMaskRecipeToVPUser) {
1023   LLVMContext C;
1024 
1025   VPValue Mask;
1026   VPBranchOnMaskRecipe Recipe(&Mask);
1027   EXPECT_TRUE(isa<VPUser>(&Recipe));
1028   VPRecipeBase *BaseR = &Recipe;
1029   EXPECT_TRUE(isa<VPUser>(BaseR));
1030   EXPECT_EQ(&Recipe, BaseR);
1031 }
1032 
1033 TEST(VPRecipeTest, CastVPWidenMemoryRecipeToVPUserAndVPDef) {
1034   LLVMContext C;
1035 
1036   IntegerType *Int32 = IntegerType::get(C, 32);
1037   PointerType *Int32Ptr = PointerType::get(Int32, 0);
1038   auto *Load =
1039       new LoadInst(Int32, PoisonValue::get(Int32Ptr), "", false, Align(1));
1040   VPValue Addr;
1041   VPValue Mask;
1042   VPWidenLoadRecipe Recipe(*Load, &Addr, &Mask, true, false, {});
1043   EXPECT_TRUE(isa<VPUser>(&Recipe));
1044   VPRecipeBase *BaseR = &Recipe;
1045   EXPECT_TRUE(isa<VPUser>(BaseR));
1046   EXPECT_EQ(&Recipe, BaseR);
1047 
1048   VPValue *VPV = Recipe.getVPSingleValue();
1049   EXPECT_TRUE(isa<VPRecipeBase>(VPV->getDefiningRecipe()));
1050   EXPECT_EQ(&Recipe, VPV->getDefiningRecipe());
1051 
1052   delete Load;
1053 }
1054 
1055 TEST(VPRecipeTest, MayHaveSideEffectsAndMayReadWriteMemory) {
1056   LLVMContext C;
1057   IntegerType *Int1 = IntegerType::get(C, 1);
1058   IntegerType *Int32 = IntegerType::get(C, 32);
1059   PointerType *Int32Ptr = PointerType::get(Int32, 0);
1060 
1061   {
1062     auto *AI = BinaryOperator::CreateAdd(PoisonValue::get(Int32),
1063                                          PoisonValue::get(Int32));
1064     VPValue Op1;
1065     VPValue Op2;
1066     SmallVector<VPValue *, 2> Args;
1067     Args.push_back(&Op1);
1068     Args.push_back(&Op1);
1069     VPWidenRecipe Recipe(*AI, make_range(Args.begin(), Args.end()));
1070     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1071     EXPECT_FALSE(Recipe.mayReadFromMemory());
1072     EXPECT_FALSE(Recipe.mayWriteToMemory());
1073     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1074     delete AI;
1075   }
1076 
1077   {
1078     auto *SelectI =
1079         SelectInst::Create(PoisonValue::get(Int1), PoisonValue::get(Int32),
1080                            PoisonValue::get(Int32));
1081     VPValue Op1;
1082     VPValue Op2;
1083     VPValue Op3;
1084     SmallVector<VPValue *, 4> Args;
1085     Args.push_back(&Op1);
1086     Args.push_back(&Op2);
1087     Args.push_back(&Op3);
1088     VPWidenSelectRecipe Recipe(*SelectI, make_range(Args.begin(), Args.end()));
1089     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1090     EXPECT_FALSE(Recipe.mayReadFromMemory());
1091     EXPECT_FALSE(Recipe.mayWriteToMemory());
1092     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1093     delete SelectI;
1094   }
1095 
1096   {
1097     auto *GEP = GetElementPtrInst::Create(Int32, PoisonValue::get(Int32Ptr),
1098                                           PoisonValue::get(Int32));
1099     VPValue Op1;
1100     VPValue Op2;
1101     SmallVector<VPValue *, 4> Args;
1102     Args.push_back(&Op1);
1103     Args.push_back(&Op2);
1104     VPWidenGEPRecipe Recipe(GEP, make_range(Args.begin(), Args.end()));
1105     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1106     EXPECT_FALSE(Recipe.mayReadFromMemory());
1107     EXPECT_FALSE(Recipe.mayWriteToMemory());
1108     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1109     delete GEP;
1110   }
1111 
1112   {
1113     VPValue Mask;
1114     VPBranchOnMaskRecipe Recipe(&Mask);
1115     EXPECT_TRUE(Recipe.mayHaveSideEffects());
1116     EXPECT_FALSE(Recipe.mayReadFromMemory());
1117     EXPECT_FALSE(Recipe.mayWriteToMemory());
1118     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1119   }
1120 
1121   {
1122     VPValue ChainOp;
1123     VPValue VecOp;
1124     VPValue CondOp;
1125     VPReductionRecipe Recipe(RecurrenceDescriptor(), nullptr, &ChainOp, &CondOp,
1126                              &VecOp, false);
1127     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1128     EXPECT_FALSE(Recipe.mayReadFromMemory());
1129     EXPECT_FALSE(Recipe.mayWriteToMemory());
1130     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1131   }
1132 
1133   {
1134     VPValue ChainOp;
1135     VPValue VecOp;
1136     VPValue CondOp;
1137     VPReductionRecipe Recipe(RecurrenceDescriptor(), nullptr, &ChainOp, &CondOp,
1138                              &VecOp, false);
1139     VPValue EVL;
1140     VPReductionEVLRecipe EVLRecipe(Recipe, EVL, &CondOp);
1141     EXPECT_FALSE(EVLRecipe.mayHaveSideEffects());
1142     EXPECT_FALSE(EVLRecipe.mayReadFromMemory());
1143     EXPECT_FALSE(EVLRecipe.mayWriteToMemory());
1144     EXPECT_FALSE(EVLRecipe.mayReadOrWriteMemory());
1145   }
1146 
1147   {
1148     auto *Load =
1149         new LoadInst(Int32, PoisonValue::get(Int32Ptr), "", false, Align(1));
1150     VPValue Addr;
1151     VPValue Mask;
1152     VPWidenLoadRecipe Recipe(*Load, &Addr, &Mask, true, false, {});
1153     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1154     EXPECT_TRUE(Recipe.mayReadFromMemory());
1155     EXPECT_FALSE(Recipe.mayWriteToMemory());
1156     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1157     delete Load;
1158   }
1159 
1160   {
1161     auto *Store = new StoreInst(PoisonValue::get(Int32),
1162                                 PoisonValue::get(Int32Ptr), false, Align(1));
1163     VPValue Addr;
1164     VPValue Mask;
1165     VPValue StoredV;
1166     VPWidenStoreRecipe Recipe(*Store, &Addr, &StoredV, &Mask, false, false, {});
1167     EXPECT_TRUE(Recipe.mayHaveSideEffects());
1168     EXPECT_FALSE(Recipe.mayReadFromMemory());
1169     EXPECT_TRUE(Recipe.mayWriteToMemory());
1170     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1171     delete Store;
1172   }
1173 
1174   {
1175     FunctionType *FTy = FunctionType::get(Int32, false);
1176     Function *Fn = Function::Create(FTy, GlobalValue::ExternalLinkage, 0);
1177     auto *Call = CallInst::Create(FTy, Fn);
1178     VPValue Op1;
1179     VPValue Op2;
1180     VPValue CalledFn(Call->getCalledFunction());
1181     SmallVector<VPValue *, 3> Args;
1182     Args.push_back(&Op1);
1183     Args.push_back(&Op2);
1184     Args.push_back(&CalledFn);
1185     VPWidenCallRecipe Recipe(Call, Fn, Args);
1186     EXPECT_TRUE(Recipe.mayHaveSideEffects());
1187     EXPECT_TRUE(Recipe.mayReadFromMemory());
1188     EXPECT_TRUE(Recipe.mayWriteToMemory());
1189     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1190     delete Call;
1191     delete Fn;
1192   }
1193 
1194   {
1195     // Test for a call to a function without side-effects.
1196     LLVMContext C;
1197     Module M("", C);
1198     Function *TheFn =
1199         Intrinsic::getOrInsertDeclaration(&M, Intrinsic::thread_pointer);
1200 
1201     auto *Call = CallInst::Create(TheFn->getFunctionType(), TheFn);
1202     VPValue Op1;
1203     VPValue Op2;
1204     VPValue CalledFn(TheFn);
1205     SmallVector<VPValue *, 3> Args;
1206     Args.push_back(&Op1);
1207     Args.push_back(&Op2);
1208     Args.push_back(&CalledFn);
1209     VPWidenCallRecipe Recipe(Call, TheFn, Args);
1210     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1211     EXPECT_FALSE(Recipe.mayReadFromMemory());
1212     EXPECT_FALSE(Recipe.mayWriteToMemory());
1213     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1214     delete Call;
1215   }
1216 
1217   {
1218     VPValue Op1;
1219     VPValue Op2;
1220     InductionDescriptor IndDesc;
1221     VPScalarIVStepsRecipe Recipe(IndDesc, &Op1, &Op2);
1222     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1223     EXPECT_FALSE(Recipe.mayReadFromMemory());
1224     EXPECT_FALSE(Recipe.mayWriteToMemory());
1225     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1226   }
1227 
1228   // The initial implementation is conservative with respect to VPInstructions.
1229   {
1230     VPValue Op1;
1231     VPValue Op2;
1232     VPInstruction VPInst(Instruction::Add, {&Op1, &Op2});
1233     VPRecipeBase &Recipe = VPInst;
1234     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1235     EXPECT_TRUE(Recipe.mayReadFromMemory());
1236     EXPECT_FALSE(Recipe.mayWriteToMemory());
1237     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1238   }
1239   {
1240     VPValue Op1;
1241     VPPredInstPHIRecipe Recipe(&Op1);
1242     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1243     EXPECT_FALSE(Recipe.mayReadFromMemory());
1244     EXPECT_FALSE(Recipe.mayWriteToMemory());
1245     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1246   }
1247 }
1248 
1249 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1250 TEST(VPRecipeTest, dumpRecipeInPlan) {
1251   VPBasicBlock *VPBB0 = new VPBasicBlock("preheader");
1252   VPBasicBlock *VPBB1 = new VPBasicBlock();
1253   VPlan Plan(VPBB0, VPBB1);
1254 
1255   LLVMContext C;
1256 
1257   IntegerType *Int32 = IntegerType::get(C, 32);
1258   auto *AI = BinaryOperator::CreateAdd(PoisonValue::get(Int32),
1259                                        PoisonValue::get(Int32));
1260   AI->setName("a");
1261   SmallVector<VPValue *, 2> Args;
1262   VPValue *ExtVPV1 = Plan.getOrAddLiveIn(ConstantInt::get(Int32, 1));
1263   VPValue *ExtVPV2 = Plan.getOrAddLiveIn(ConstantInt::get(Int32, 2));
1264   Args.push_back(ExtVPV1);
1265   Args.push_back(ExtVPV2);
1266   VPWidenRecipe *WidenR =
1267       new VPWidenRecipe(*AI, make_range(Args.begin(), Args.end()));
1268   VPBB1->appendRecipe(WidenR);
1269 
1270   {
1271     // Use EXPECT_EXIT to capture stderr and compare against expected output.
1272     //
1273     // Test VPValue::dump().
1274     VPValue *VPV = WidenR;
1275     EXPECT_EXIT(
1276         {
1277           VPV->dump();
1278           exit(0);
1279         },
1280         testing::ExitedWithCode(0), "WIDEN ir<%a> = add ir<1>, ir<2>");
1281 
1282     // Test VPRecipeBase::dump().
1283     VPRecipeBase *R = WidenR;
1284     EXPECT_EXIT(
1285         {
1286           R->dump();
1287           exit(0);
1288         },
1289         testing::ExitedWithCode(0), "WIDEN ir<%a> = add ir<1>, ir<2>");
1290 
1291     // Test VPDef::dump().
1292     VPDef *D = WidenR;
1293     EXPECT_EXIT(
1294         {
1295           D->dump();
1296           exit(0);
1297         },
1298         testing::ExitedWithCode(0), "WIDEN ir<%a> = add ir<1>, ir<2>");
1299   }
1300 
1301   delete AI;
1302 }
1303 
1304 TEST(VPRecipeTest, dumpRecipeUnnamedVPValuesInPlan) {
1305   VPBasicBlock *VPBB0 = new VPBasicBlock("preheader");
1306   VPBasicBlock *VPBB1 = new VPBasicBlock();
1307   VPlan Plan(VPBB0, VPBB1);
1308 
1309   LLVMContext C;
1310 
1311   IntegerType *Int32 = IntegerType::get(C, 32);
1312   auto *AI = BinaryOperator::CreateAdd(PoisonValue::get(Int32),
1313                                        PoisonValue::get(Int32));
1314   AI->setName("a");
1315   SmallVector<VPValue *, 2> Args;
1316   VPValue *ExtVPV1 = Plan.getOrAddLiveIn(ConstantInt::get(Int32, 1));
1317   VPValue *ExtVPV2 = Plan.getOrAddLiveIn(AI);
1318   Args.push_back(ExtVPV1);
1319   Args.push_back(ExtVPV2);
1320   VPInstruction *I1 = new VPInstruction(Instruction::Add, {ExtVPV1, ExtVPV2});
1321   VPInstruction *I2 = new VPInstruction(Instruction::Mul, {I1, I1});
1322   VPBB1->appendRecipe(I1);
1323   VPBB1->appendRecipe(I2);
1324 
1325   // Check printing I1.
1326   {
1327     // Use EXPECT_EXIT to capture stderr and compare against expected output.
1328     //
1329     // Test VPValue::dump().
1330     VPValue *VPV = I1;
1331     EXPECT_EXIT(
1332         {
1333           VPV->dump();
1334           exit(0);
1335         },
1336         testing::ExitedWithCode(0), "EMIT vp<%1> = add ir<1>, ir<%a>");
1337 
1338     // Test VPRecipeBase::dump().
1339     VPRecipeBase *R = I1;
1340     EXPECT_EXIT(
1341         {
1342           R->dump();
1343           exit(0);
1344         },
1345         testing::ExitedWithCode(0), "EMIT vp<%1> = add ir<1>, ir<%a>");
1346 
1347     // Test VPDef::dump().
1348     VPDef *D = I1;
1349     EXPECT_EXIT(
1350         {
1351           D->dump();
1352           exit(0);
1353         },
1354         testing::ExitedWithCode(0), "EMIT vp<%1> = add ir<1>, ir<%a>");
1355   }
1356   // Check printing I2.
1357   {
1358     // Use EXPECT_EXIT to capture stderr and compare against expected output.
1359     //
1360     // Test VPValue::dump().
1361     VPValue *VPV = I2;
1362     EXPECT_EXIT(
1363         {
1364           VPV->dump();
1365           exit(0);
1366         },
1367         testing::ExitedWithCode(0), "EMIT vp<%2> = mul vp<%1>, vp<%1>");
1368 
1369     // Test VPRecipeBase::dump().
1370     VPRecipeBase *R = I2;
1371     EXPECT_EXIT(
1372         {
1373           R->dump();
1374           exit(0);
1375         },
1376         testing::ExitedWithCode(0), "EMIT vp<%2> = mul vp<%1>, vp<%1>");
1377 
1378     // Test VPDef::dump().
1379     VPDef *D = I2;
1380     EXPECT_EXIT(
1381         {
1382           D->dump();
1383           exit(0);
1384         },
1385         testing::ExitedWithCode(0), "EMIT vp<%2> = mul vp<%1>, vp<%1>");
1386   }
1387   delete AI;
1388 }
1389 
1390 TEST(VPRecipeTest, dumpRecipeUnnamedVPValuesNotInPlanOrBlock) {
1391   LLVMContext C;
1392   IntegerType *Int32 = IntegerType::get(C, 32);
1393   auto *AI = BinaryOperator::CreateAdd(PoisonValue::get(Int32),
1394                                        PoisonValue::get(Int32));
1395   AI->setName("a");
1396   VPValue *ExtVPV1 = new VPValue(ConstantInt::get(Int32, 1));
1397   VPValue *ExtVPV2 = new VPValue(AI);
1398 
1399   VPInstruction *I1 = new VPInstruction(Instruction::Add, {ExtVPV1, ExtVPV2});
1400   VPInstruction *I2 = new VPInstruction(Instruction::Mul, {I1, I1});
1401 
1402   // Check printing I1.
1403   {
1404     // Use EXPECT_EXIT to capture stderr and compare against expected output.
1405     //
1406     // Test VPValue::dump().
1407     VPValue *VPV = I1;
1408     EXPECT_EXIT(
1409         {
1410           VPV->dump();
1411           exit(0);
1412         },
1413         testing::ExitedWithCode(0), "EMIT <badref> = add ir<1>, ir<%a>");
1414 
1415     // Test VPRecipeBase::dump().
1416     VPRecipeBase *R = I1;
1417     EXPECT_EXIT(
1418         {
1419           R->dump();
1420           exit(0);
1421         },
1422         testing::ExitedWithCode(0), "EMIT <badref> = add ir<1>, ir<%a>");
1423 
1424     // Test VPDef::dump().
1425     VPDef *D = I1;
1426     EXPECT_EXIT(
1427         {
1428           D->dump();
1429           exit(0);
1430         },
1431         testing::ExitedWithCode(0), "EMIT <badref> = add ir<1>, ir<%a>");
1432   }
1433   // Check printing I2.
1434   {
1435     // Use EXPECT_EXIT to capture stderr and compare against expected output.
1436     //
1437     // Test VPValue::dump().
1438     VPValue *VPV = I2;
1439     EXPECT_EXIT(
1440         {
1441           VPV->dump();
1442           exit(0);
1443         },
1444         testing::ExitedWithCode(0), "EMIT <badref> = mul <badref>, <badref>");
1445 
1446     // Test VPRecipeBase::dump().
1447     VPRecipeBase *R = I2;
1448     EXPECT_EXIT(
1449         {
1450           R->dump();
1451           exit(0);
1452         },
1453         testing::ExitedWithCode(0), "EMIT <badref> = mul <badref>, <badref>");
1454 
1455     // Test VPDef::dump().
1456     VPDef *D = I2;
1457     EXPECT_EXIT(
1458         {
1459           D->dump();
1460           exit(0);
1461         },
1462         testing::ExitedWithCode(0), "EMIT <badref> = mul <badref>, <badref>");
1463   }
1464 
1465   delete I2;
1466   delete I1;
1467   delete ExtVPV2;
1468   delete ExtVPV1;
1469   delete AI;
1470 }
1471 
1472 #endif
1473 
1474 TEST(VPRecipeTest, CastVPReductionRecipeToVPUser) {
1475   LLVMContext C;
1476 
1477   VPValue ChainOp;
1478   VPValue VecOp;
1479   VPValue CondOp;
1480   VPReductionRecipe Recipe(RecurrenceDescriptor(), nullptr, &ChainOp, &CondOp,
1481                            &VecOp, false);
1482   EXPECT_TRUE(isa<VPUser>(&Recipe));
1483   VPRecipeBase *BaseR = &Recipe;
1484   EXPECT_TRUE(isa<VPUser>(BaseR));
1485 }
1486 
1487 TEST(VPRecipeTest, CastVPReductionEVLRecipeToVPUser) {
1488   LLVMContext C;
1489 
1490   VPValue ChainOp;
1491   VPValue VecOp;
1492   VPValue CondOp;
1493   VPReductionRecipe Recipe(RecurrenceDescriptor(), nullptr, &ChainOp, &CondOp,
1494                            &VecOp, false);
1495   VPValue EVL;
1496   VPReductionEVLRecipe EVLRecipe(Recipe, EVL, &CondOp);
1497   EXPECT_TRUE(isa<VPUser>(&EVLRecipe));
1498   VPRecipeBase *BaseR = &EVLRecipe;
1499   EXPECT_TRUE(isa<VPUser>(BaseR));
1500 }
1501 
1502 struct VPDoubleValueDef : public VPRecipeBase {
1503   VPDoubleValueDef(ArrayRef<VPValue *> Operands) : VPRecipeBase(99, Operands) {
1504     new VPValue(nullptr, this);
1505     new VPValue(nullptr, this);
1506   }
1507 
1508   VPRecipeBase *clone() override { return nullptr; }
1509 
1510   void execute(struct VPTransformState &State) override {}
1511 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1512   void print(raw_ostream &O, const Twine &Indent,
1513              VPSlotTracker &SlotTracker) const override {}
1514 #endif
1515 };
1516 
1517 TEST(VPDoubleValueDefTest, traverseUseLists) {
1518   // Check that the def-use chains of a multi-def can be traversed in both
1519   // directions.
1520 
1521   // Create a new VPDef which defines 2 values and has 2 operands.
1522   VPInstruction Op0(20, {});
1523   VPInstruction Op1(30, {});
1524   VPDoubleValueDef DoubleValueDef({&Op0, &Op1});
1525 
1526   // Create a new users of the defined values.
1527   VPInstruction I1(
1528       1, {DoubleValueDef.getVPValue(0), DoubleValueDef.getVPValue(1)});
1529   VPInstruction I2(2, {DoubleValueDef.getVPValue(0)});
1530   VPInstruction I3(3, {DoubleValueDef.getVPValue(1)});
1531 
1532   // Check operands of the VPDef (traversing upwards).
1533   SmallVector<VPValue *, 4> DoubleOperands(DoubleValueDef.op_begin(),
1534                                            DoubleValueDef.op_end());
1535   EXPECT_EQ(2u, DoubleOperands.size());
1536   EXPECT_EQ(&Op0, DoubleOperands[0]);
1537   EXPECT_EQ(&Op1, DoubleOperands[1]);
1538 
1539   // Check users of the defined values (traversing downwards).
1540   SmallVector<VPUser *, 4> DoubleValueDefV0Users(
1541       DoubleValueDef.getVPValue(0)->user_begin(),
1542       DoubleValueDef.getVPValue(0)->user_end());
1543   EXPECT_EQ(2u, DoubleValueDefV0Users.size());
1544   EXPECT_EQ(&I1, DoubleValueDefV0Users[0]);
1545   EXPECT_EQ(&I2, DoubleValueDefV0Users[1]);
1546 
1547   SmallVector<VPUser *, 4> DoubleValueDefV1Users(
1548       DoubleValueDef.getVPValue(1)->user_begin(),
1549       DoubleValueDef.getVPValue(1)->user_end());
1550   EXPECT_EQ(2u, DoubleValueDefV1Users.size());
1551   EXPECT_EQ(&I1, DoubleValueDefV1Users[0]);
1552   EXPECT_EQ(&I3, DoubleValueDefV1Users[1]);
1553 
1554   // Now check that we can get the right VPDef for each defined value.
1555   EXPECT_EQ(&DoubleValueDef, I1.getOperand(0)->getDefiningRecipe());
1556   EXPECT_EQ(&DoubleValueDef, I1.getOperand(1)->getDefiningRecipe());
1557   EXPECT_EQ(&DoubleValueDef, I2.getOperand(0)->getDefiningRecipe());
1558   EXPECT_EQ(&DoubleValueDef, I3.getOperand(0)->getDefiningRecipe());
1559 }
1560 
1561 TEST(VPRecipeTest, CastToVPSingleDefRecipe) {
1562   VPValue Start;
1563   VPEVLBasedIVPHIRecipe R(&Start, {});
1564   VPRecipeBase *B = &R;
1565   EXPECT_TRUE(isa<VPSingleDefRecipe>(B));
1566   // TODO: check other VPSingleDefRecipes.
1567 }
1568 
1569 } // namespace
1570 } // namespace llvm
1571