xref: /llvm-project/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp (revision 9952e00af6c93e9807c3dfe076e99e7f5a77f675) 
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     OS.flush();
709     EXPECT_EQ("EMIT br <badref>, <badref>", I3Dump);
710   }
711 
712   VPlan Plan(VPBB0, TC, VPBB1);
713   std::string FullDump;
714   raw_string_ostream OS(FullDump);
715   Plan.printDOT(OS);
716 
717   const char *ExpectedStr = R"(digraph VPlan {
718 graph [labelloc=t, fontsize=30; label="Vectorization Plan\n for UF\>=1\nvp\<%1\> = original trip-count\n"]
719 node [shape=rect, fontname=Courier, fontsize=30]
720 edge [fontname=Courier, fontsize=30]
721 compound=true
722   N0 [label =
723     "preheader:\l" +
724     "  EMIT vp\<%1\> = add\l" +
725     "No successors\l"
726   ]
727   N1 [label =
728     "bb1:\l" +
729     "  EMIT vp\<%2\> = add\l" +
730     "  EMIT vp\<%3\> = sub vp\<%2\>\l" +
731     "  EMIT br vp\<%2\>, vp\<%3\>\l" +
732     "Successor(s): bb2\l"
733   ]
734   N1 -> N2 [ label=""]
735   N2 [label =
736     "bb2:\l" +
737     "  EMIT vp\<%5\> = mul vp\<%3\>, vp\<%2\>\l" +
738     "  EMIT ret vp\<%5\>\l" +
739     "No successors\l"
740   ]
741 }
742 )";
743   EXPECT_EQ(ExpectedStr, FullDump);
744 
745   const char *ExpectedBlock1Str = R"(bb1:
746   EMIT vp<%2> = add
747   EMIT vp<%3> = sub vp<%2>
748   EMIT br vp<%2>, vp<%3>
749 Successor(s): bb2
750 )";
751   std::string Block1Dump;
752   raw_string_ostream OS1(Block1Dump);
753   VPBB1->print(OS1);
754   EXPECT_EQ(ExpectedBlock1Str, Block1Dump);
755 
756   // Ensure that numbering is good when dumping the second block in isolation.
757   const char *ExpectedBlock2Str = R"(bb2:
758   EMIT vp<%5> = mul vp<%3>, vp<%2>
759   EMIT ret vp<%5>
760 No successors
761 )";
762   std::string Block2Dump;
763   raw_string_ostream OS2(Block2Dump);
764   VPBB2->print(OS2);
765   EXPECT_EQ(ExpectedBlock2Str, Block2Dump);
766 
767   {
768     std::string I3Dump;
769     raw_string_ostream OS(I3Dump);
770     VPSlotTracker SlotTracker(&Plan);
771     I3->print(OS, "", SlotTracker);
772     OS.flush();
773     EXPECT_EQ("EMIT br vp<%2>, vp<%3>", I3Dump);
774   }
775 
776   {
777     std::string I4Dump;
778     raw_string_ostream OS(I4Dump);
779     OS << *I4;
780     OS.flush();
781     EXPECT_EQ("EMIT vp<%5> = mul vp<%3>, vp<%2>", I4Dump);
782   }
783 }
784 
785 TEST(VPBasicBlockTest, printPlanWithVFsAndUFs) {
786 
787   VPInstruction *TC = new VPInstruction(Instruction::Sub, {});
788   VPBasicBlock *VPBB0 = new VPBasicBlock("preheader");
789   VPBB0->appendRecipe(TC);
790 
791   VPInstruction *I1 = new VPInstruction(Instruction::Add, {});
792   VPBasicBlock *VPBB1 = new VPBasicBlock();
793   VPBB1->appendRecipe(I1);
794   VPBB1->setName("bb1");
795 
796   VPlan Plan(VPBB0, TC, VPBB1);
797   Plan.setName("TestPlan");
798   Plan.addVF(ElementCount::getFixed(4));
799 
800   {
801     std::string FullDump;
802     raw_string_ostream OS(FullDump);
803     Plan.print(OS);
804 
805     const char *ExpectedStr = R"(VPlan 'TestPlan for VF={4},UF>=1' {
806 vp<%1> = original trip-count
807 
808 preheader:
809   EMIT vp<%1> = sub
810 No successors
811 
812 bb1:
813   EMIT vp<%2> = add
814 No successors
815 }
816 )";
817     EXPECT_EQ(ExpectedStr, FullDump);
818   }
819 
820   {
821     Plan.addVF(ElementCount::getScalable(8));
822     std::string FullDump;
823     raw_string_ostream OS(FullDump);
824     Plan.print(OS);
825 
826     const char *ExpectedStr = R"(VPlan 'TestPlan for VF={4,vscale x 8},UF>=1' {
827 vp<%1> = original trip-count
828 
829 preheader:
830   EMIT vp<%1> = sub
831 No successors
832 
833 bb1:
834   EMIT vp<%2> = add
835 No successors
836 }
837 )";
838     EXPECT_EQ(ExpectedStr, FullDump);
839   }
840 
841   {
842     Plan.setUF(4);
843     std::string FullDump;
844     raw_string_ostream OS(FullDump);
845     Plan.print(OS);
846 
847     const char *ExpectedStr = R"(VPlan 'TestPlan for VF={4,vscale x 8},UF={4}' {
848 vp<%1> = original trip-count
849 
850 preheader:
851   EMIT vp<%1> = sub
852 No successors
853 
854 bb1:
855   EMIT vp<%2> = add
856 No successors
857 }
858 )";
859     EXPECT_EQ(ExpectedStr, FullDump);
860   }
861 }
862 #endif
863 
864 TEST(VPRecipeTest, CastVPInstructionToVPUser) {
865   VPValue Op1;
866   VPValue Op2;
867   VPInstruction Recipe(Instruction::Add, {&Op1, &Op2});
868   EXPECT_TRUE(isa<VPUser>(&Recipe));
869   VPRecipeBase *BaseR = &Recipe;
870   EXPECT_TRUE(isa<VPUser>(BaseR));
871   EXPECT_EQ(&Recipe, BaseR);
872 }
873 
874 TEST(VPRecipeTest, CastVPWidenRecipeToVPUser) {
875   LLVMContext C;
876 
877   IntegerType *Int32 = IntegerType::get(C, 32);
878   auto *AI = BinaryOperator::CreateAdd(PoisonValue::get(Int32),
879                                        PoisonValue::get(Int32));
880   VPValue Op1;
881   VPValue Op2;
882   SmallVector<VPValue *, 2> Args;
883   Args.push_back(&Op1);
884   Args.push_back(&Op1);
885   VPWidenRecipe WidenR(*AI, make_range(Args.begin(), Args.end()));
886   EXPECT_TRUE(isa<VPUser>(&WidenR));
887   VPRecipeBase *WidenRBase = &WidenR;
888   EXPECT_TRUE(isa<VPUser>(WidenRBase));
889   EXPECT_EQ(&WidenR, WidenRBase);
890   delete AI;
891 }
892 
893 TEST(VPRecipeTest, CastVPWidenCallRecipeToVPUserAndVPDef) {
894   LLVMContext C;
895 
896   IntegerType *Int32 = IntegerType::get(C, 32);
897   FunctionType *FTy = FunctionType::get(Int32, false);
898   Function *Fn = Function::Create(FTy, GlobalValue::ExternalLinkage, 0);
899   auto *Call = CallInst::Create(FTy, Fn);
900   VPValue Op1;
901   VPValue Op2;
902   VPValue CalledFn(Call->getCalledFunction());
903   SmallVector<VPValue *, 2> Args;
904   Args.push_back(&Op1);
905   Args.push_back(&Op2);
906   Args.push_back(&CalledFn);
907   VPWidenCallRecipe Recipe(Call, make_range(Args.begin(), Args.end()), false);
908   EXPECT_TRUE(isa<VPUser>(&Recipe));
909   VPRecipeBase *BaseR = &Recipe;
910   EXPECT_TRUE(isa<VPUser>(BaseR));
911   EXPECT_EQ(&Recipe, BaseR);
912 
913   VPValue *VPV = &Recipe;
914   EXPECT_TRUE(VPV->getDefiningRecipe());
915   EXPECT_EQ(&Recipe, VPV->getDefiningRecipe());
916 
917   delete Call;
918   delete Fn;
919 }
920 
921 TEST(VPRecipeTest, CastVPWidenSelectRecipeToVPUserAndVPDef) {
922   LLVMContext C;
923 
924   IntegerType *Int1 = IntegerType::get(C, 1);
925   IntegerType *Int32 = IntegerType::get(C, 32);
926   auto *SelectI = SelectInst::Create(
927       PoisonValue::get(Int1), PoisonValue::get(Int32), PoisonValue::get(Int32));
928   VPValue Op1;
929   VPValue Op2;
930   VPValue Op3;
931   SmallVector<VPValue *, 4> Args;
932   Args.push_back(&Op1);
933   Args.push_back(&Op2);
934   Args.push_back(&Op3);
935   VPWidenSelectRecipe WidenSelectR(*SelectI,
936                                    make_range(Args.begin(), Args.end()));
937   EXPECT_TRUE(isa<VPUser>(&WidenSelectR));
938   VPRecipeBase *BaseR = &WidenSelectR;
939   EXPECT_TRUE(isa<VPUser>(BaseR));
940   EXPECT_EQ(&WidenSelectR, BaseR);
941 
942   VPValue *VPV = &WidenSelectR;
943   EXPECT_TRUE(isa<VPRecipeBase>(VPV->getDefiningRecipe()));
944   EXPECT_EQ(&WidenSelectR, VPV->getDefiningRecipe());
945 
946   delete SelectI;
947 }
948 
949 TEST(VPRecipeTest, CastVPWidenGEPRecipeToVPUserAndVPDef) {
950   LLVMContext C;
951 
952   IntegerType *Int32 = IntegerType::get(C, 32);
953   PointerType *Int32Ptr = PointerType::get(Int32, 0);
954   auto *GEP = GetElementPtrInst::Create(Int32, PoisonValue::get(Int32Ptr),
955                                         PoisonValue::get(Int32));
956   VPValue Op1;
957   VPValue Op2;
958   SmallVector<VPValue *, 4> Args;
959   Args.push_back(&Op1);
960   Args.push_back(&Op2);
961   VPWidenGEPRecipe Recipe(GEP, make_range(Args.begin(), Args.end()));
962   EXPECT_TRUE(isa<VPUser>(&Recipe));
963   VPRecipeBase *BaseR = &Recipe;
964   EXPECT_TRUE(isa<VPUser>(BaseR));
965   EXPECT_EQ(&Recipe, BaseR);
966 
967   VPValue *VPV = &Recipe;
968   EXPECT_TRUE(isa<VPRecipeBase>(VPV->getDefiningRecipe()));
969   EXPECT_EQ(&Recipe, VPV->getDefiningRecipe());
970 
971   delete GEP;
972 }
973 
974 TEST(VPRecipeTest, CastVPBlendRecipeToVPUser) {
975   LLVMContext C;
976 
977   IntegerType *Int32 = IntegerType::get(C, 32);
978   auto *Phi = PHINode::Create(Int32, 1);
979   VPValue I1;
980   VPValue I2;
981   VPValue M2;
982   SmallVector<VPValue *, 4> Args;
983   Args.push_back(&I1);
984   Args.push_back(&I2);
985   Args.push_back(&M2);
986   VPBlendRecipe Recipe(Phi, Args);
987   EXPECT_TRUE(isa<VPUser>(&Recipe));
988   VPRecipeBase *BaseR = &Recipe;
989   EXPECT_TRUE(isa<VPUser>(BaseR));
990   delete Phi;
991 }
992 
993 TEST(VPRecipeTest, CastVPInterleaveRecipeToVPUser) {
994   LLVMContext C;
995 
996   VPValue Addr;
997   VPValue Mask;
998   InterleaveGroup<Instruction> IG(4, false, Align(4));
999   VPInterleaveRecipe Recipe(&IG, &Addr, {}, &Mask, false);
1000   EXPECT_TRUE(isa<VPUser>(&Recipe));
1001   VPRecipeBase *BaseR = &Recipe;
1002   EXPECT_TRUE(isa<VPUser>(BaseR));
1003   EXPECT_EQ(&Recipe, BaseR);
1004 }
1005 
1006 TEST(VPRecipeTest, CastVPReplicateRecipeToVPUser) {
1007   LLVMContext C;
1008 
1009   VPValue Op1;
1010   VPValue Op2;
1011   SmallVector<VPValue *, 4> Args;
1012   Args.push_back(&Op1);
1013   Args.push_back(&Op2);
1014 
1015   IntegerType *Int32 = IntegerType::get(C, 32);
1016   FunctionType *FTy = FunctionType::get(Int32, false);
1017   auto *Call = CallInst::Create(FTy, PoisonValue::get(FTy));
1018   VPReplicateRecipe Recipe(Call, make_range(Args.begin(), Args.end()), true);
1019   EXPECT_TRUE(isa<VPUser>(&Recipe));
1020   VPRecipeBase *BaseR = &Recipe;
1021   EXPECT_TRUE(isa<VPUser>(BaseR));
1022   delete Call;
1023 }
1024 
1025 TEST(VPRecipeTest, CastVPBranchOnMaskRecipeToVPUser) {
1026   LLVMContext C;
1027 
1028   VPValue Mask;
1029   VPBranchOnMaskRecipe Recipe(&Mask);
1030   EXPECT_TRUE(isa<VPUser>(&Recipe));
1031   VPRecipeBase *BaseR = &Recipe;
1032   EXPECT_TRUE(isa<VPUser>(BaseR));
1033   EXPECT_EQ(&Recipe, BaseR);
1034 }
1035 
1036 TEST(VPRecipeTest, CastVPWidenMemoryRecipeToVPUserAndVPDef) {
1037   LLVMContext C;
1038 
1039   IntegerType *Int32 = IntegerType::get(C, 32);
1040   PointerType *Int32Ptr = PointerType::get(Int32, 0);
1041   auto *Load =
1042       new LoadInst(Int32, PoisonValue::get(Int32Ptr), "", false, Align(1));
1043   VPValue Addr;
1044   VPValue Mask;
1045   VPWidenLoadRecipe Recipe(*Load, &Addr, &Mask, true, false, {});
1046   EXPECT_TRUE(isa<VPUser>(&Recipe));
1047   VPRecipeBase *BaseR = &Recipe;
1048   EXPECT_TRUE(isa<VPUser>(BaseR));
1049   EXPECT_EQ(&Recipe, BaseR);
1050 
1051   VPValue *VPV = Recipe.getVPSingleValue();
1052   EXPECT_TRUE(isa<VPRecipeBase>(VPV->getDefiningRecipe()));
1053   EXPECT_EQ(&Recipe, VPV->getDefiningRecipe());
1054 
1055   delete Load;
1056 }
1057 
1058 TEST(VPRecipeTest, MayHaveSideEffectsAndMayReadWriteMemory) {
1059   LLVMContext C;
1060   IntegerType *Int1 = IntegerType::get(C, 1);
1061   IntegerType *Int32 = IntegerType::get(C, 32);
1062   PointerType *Int32Ptr = PointerType::get(Int32, 0);
1063 
1064   {
1065     auto *AI = BinaryOperator::CreateAdd(PoisonValue::get(Int32),
1066                                          PoisonValue::get(Int32));
1067     VPValue Op1;
1068     VPValue Op2;
1069     SmallVector<VPValue *, 2> Args;
1070     Args.push_back(&Op1);
1071     Args.push_back(&Op1);
1072     VPWidenRecipe Recipe(*AI, make_range(Args.begin(), Args.end()));
1073     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1074     EXPECT_FALSE(Recipe.mayReadFromMemory());
1075     EXPECT_FALSE(Recipe.mayWriteToMemory());
1076     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1077     delete AI;
1078   }
1079 
1080   {
1081     auto *SelectI =
1082         SelectInst::Create(PoisonValue::get(Int1), PoisonValue::get(Int32),
1083                            PoisonValue::get(Int32));
1084     VPValue Op1;
1085     VPValue Op2;
1086     VPValue Op3;
1087     SmallVector<VPValue *, 4> Args;
1088     Args.push_back(&Op1);
1089     Args.push_back(&Op2);
1090     Args.push_back(&Op3);
1091     VPWidenSelectRecipe Recipe(*SelectI, make_range(Args.begin(), Args.end()));
1092     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1093     EXPECT_FALSE(Recipe.mayReadFromMemory());
1094     EXPECT_FALSE(Recipe.mayWriteToMemory());
1095     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1096     delete SelectI;
1097   }
1098 
1099   {
1100     auto *GEP = GetElementPtrInst::Create(Int32, PoisonValue::get(Int32Ptr),
1101                                           PoisonValue::get(Int32));
1102     VPValue Op1;
1103     VPValue Op2;
1104     SmallVector<VPValue *, 4> Args;
1105     Args.push_back(&Op1);
1106     Args.push_back(&Op2);
1107     VPWidenGEPRecipe Recipe(GEP, make_range(Args.begin(), Args.end()));
1108     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1109     EXPECT_FALSE(Recipe.mayReadFromMemory());
1110     EXPECT_FALSE(Recipe.mayWriteToMemory());
1111     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1112     delete GEP;
1113   }
1114 
1115   {
1116     VPValue Mask;
1117     VPBranchOnMaskRecipe Recipe(&Mask);
1118     EXPECT_TRUE(Recipe.mayHaveSideEffects());
1119     EXPECT_FALSE(Recipe.mayReadFromMemory());
1120     EXPECT_FALSE(Recipe.mayWriteToMemory());
1121     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1122   }
1123 
1124   {
1125     VPValue ChainOp;
1126     VPValue VecOp;
1127     VPValue CondOp;
1128     VPReductionRecipe Recipe(RecurrenceDescriptor(), nullptr, &ChainOp, &CondOp,
1129                              &VecOp, false);
1130     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1131     EXPECT_FALSE(Recipe.mayReadFromMemory());
1132     EXPECT_FALSE(Recipe.mayWriteToMemory());
1133     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1134   }
1135 
1136   {
1137     auto *Load =
1138         new LoadInst(Int32, PoisonValue::get(Int32Ptr), "", false, Align(1));
1139     VPValue Addr;
1140     VPValue Mask;
1141     VPWidenLoadRecipe Recipe(*Load, &Addr, &Mask, true, false, {});
1142     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1143     EXPECT_TRUE(Recipe.mayReadFromMemory());
1144     EXPECT_FALSE(Recipe.mayWriteToMemory());
1145     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1146     delete Load;
1147   }
1148 
1149   {
1150     auto *Store = new StoreInst(PoisonValue::get(Int32),
1151                                 PoisonValue::get(Int32Ptr), false, Align(1));
1152     VPValue Addr;
1153     VPValue Mask;
1154     VPValue StoredV;
1155     VPWidenStoreRecipe Recipe(*Store, &Addr, &StoredV, &Mask, false, false, {});
1156     EXPECT_TRUE(Recipe.mayHaveSideEffects());
1157     EXPECT_FALSE(Recipe.mayReadFromMemory());
1158     EXPECT_TRUE(Recipe.mayWriteToMemory());
1159     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1160     delete Store;
1161   }
1162 
1163   {
1164     FunctionType *FTy = FunctionType::get(Int32, false);
1165     Function *Fn = Function::Create(FTy, GlobalValue::ExternalLinkage, 0);
1166     auto *Call = CallInst::Create(FTy, Fn);
1167     VPValue Op1;
1168     VPValue Op2;
1169     VPValue CalledFn(Call->getCalledFunction());
1170     SmallVector<VPValue *, 3> Args;
1171     Args.push_back(&Op1);
1172     Args.push_back(&Op2);
1173     Args.push_back(&CalledFn);
1174     VPWidenCallRecipe Recipe(Call, make_range(Args.begin(), Args.end()), false);
1175     EXPECT_TRUE(Recipe.mayHaveSideEffects());
1176     EXPECT_TRUE(Recipe.mayReadFromMemory());
1177     EXPECT_TRUE(Recipe.mayWriteToMemory());
1178     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1179     delete Call;
1180     delete Fn;
1181   }
1182 
1183   {
1184     // Test for a call to a function without side-effects.
1185     LLVMContext C;
1186     Module M("", C);
1187     Function *TheFn = Intrinsic::getDeclaration(&M, Intrinsic::thread_pointer);
1188 
1189     auto *Call = CallInst::Create(TheFn->getFunctionType(), TheFn);
1190     VPValue Op1;
1191     VPValue Op2;
1192     VPValue CalledFn(TheFn);
1193     SmallVector<VPValue *, 3> Args;
1194     Args.push_back(&Op1);
1195     Args.push_back(&Op2);
1196     Args.push_back(&CalledFn);
1197     VPWidenCallRecipe Recipe(Call, make_range(Args.begin(), Args.end()), false);
1198     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1199     EXPECT_FALSE(Recipe.mayReadFromMemory());
1200     EXPECT_FALSE(Recipe.mayWriteToMemory());
1201     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1202     delete Call;
1203   }
1204 
1205   {
1206     VPValue Op1;
1207     VPValue Op2;
1208     InductionDescriptor IndDesc;
1209     VPScalarIVStepsRecipe Recipe(IndDesc, &Op1, &Op2);
1210     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1211     EXPECT_FALSE(Recipe.mayReadFromMemory());
1212     EXPECT_FALSE(Recipe.mayWriteToMemory());
1213     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1214   }
1215 
1216   // The initial implementation is conservative with respect to VPInstructions.
1217   {
1218     VPValue Op1;
1219     VPValue Op2;
1220     VPInstruction VPInst(Instruction::Add, {&Op1, &Op2});
1221     VPRecipeBase &Recipe = VPInst;
1222     EXPECT_TRUE(Recipe.mayHaveSideEffects());
1223     EXPECT_TRUE(Recipe.mayReadFromMemory());
1224     EXPECT_TRUE(Recipe.mayWriteToMemory());
1225     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1226   }
1227   {
1228     VPValue Op1;
1229     VPPredInstPHIRecipe Recipe(&Op1);
1230     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1231     EXPECT_FALSE(Recipe.mayReadFromMemory());
1232     EXPECT_FALSE(Recipe.mayWriteToMemory());
1233     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1234   }
1235 }
1236 
1237 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1238 TEST(VPRecipeTest, dumpRecipeInPlan) {
1239   VPBasicBlock *VPBB0 = new VPBasicBlock("preheader");
1240   VPBasicBlock *VPBB1 = new VPBasicBlock();
1241   VPlan Plan(VPBB0, VPBB1);
1242 
1243   LLVMContext C;
1244 
1245   IntegerType *Int32 = IntegerType::get(C, 32);
1246   auto *AI = BinaryOperator::CreateAdd(PoisonValue::get(Int32),
1247                                        PoisonValue::get(Int32));
1248   AI->setName("a");
1249   SmallVector<VPValue *, 2> Args;
1250   VPValue *ExtVPV1 = Plan.getOrAddLiveIn(ConstantInt::get(Int32, 1));
1251   VPValue *ExtVPV2 = Plan.getOrAddLiveIn(ConstantInt::get(Int32, 2));
1252   Args.push_back(ExtVPV1);
1253   Args.push_back(ExtVPV2);
1254   VPWidenRecipe *WidenR =
1255       new VPWidenRecipe(*AI, make_range(Args.begin(), Args.end()));
1256   VPBB1->appendRecipe(WidenR);
1257 
1258   {
1259     // Use EXPECT_EXIT to capture stderr and compare against expected output.
1260     //
1261     // Test VPValue::dump().
1262     VPValue *VPV = WidenR;
1263     EXPECT_EXIT(
1264         {
1265           VPV->dump();
1266           exit(0);
1267         },
1268         testing::ExitedWithCode(0), "WIDEN ir<%a> = add ir<1>, ir<2>");
1269 
1270     // Test VPRecipeBase::dump().
1271     VPRecipeBase *R = WidenR;
1272     EXPECT_EXIT(
1273         {
1274           R->dump();
1275           exit(0);
1276         },
1277         testing::ExitedWithCode(0), "WIDEN ir<%a> = add ir<1>, ir<2>");
1278 
1279     // Test VPDef::dump().
1280     VPDef *D = WidenR;
1281     EXPECT_EXIT(
1282         {
1283           D->dump();
1284           exit(0);
1285         },
1286         testing::ExitedWithCode(0), "WIDEN ir<%a> = add ir<1>, ir<2>");
1287   }
1288 
1289   delete AI;
1290 }
1291 
1292 TEST(VPRecipeTest, dumpRecipeUnnamedVPValuesInPlan) {
1293   VPBasicBlock *VPBB0 = new VPBasicBlock("preheader");
1294   VPBasicBlock *VPBB1 = new VPBasicBlock();
1295   VPlan Plan(VPBB0, VPBB1);
1296 
1297   LLVMContext C;
1298 
1299   IntegerType *Int32 = IntegerType::get(C, 32);
1300   auto *AI = BinaryOperator::CreateAdd(PoisonValue::get(Int32),
1301                                        PoisonValue::get(Int32));
1302   AI->setName("a");
1303   SmallVector<VPValue *, 2> Args;
1304   VPValue *ExtVPV1 = Plan.getOrAddLiveIn(ConstantInt::get(Int32, 1));
1305   VPValue *ExtVPV2 = Plan.getOrAddLiveIn(AI);
1306   Args.push_back(ExtVPV1);
1307   Args.push_back(ExtVPV2);
1308   VPInstruction *I1 = new VPInstruction(Instruction::Add, {ExtVPV1, ExtVPV2});
1309   VPInstruction *I2 = new VPInstruction(Instruction::Mul, {I1, I1});
1310   VPBB1->appendRecipe(I1);
1311   VPBB1->appendRecipe(I2);
1312 
1313   // Check printing I1.
1314   {
1315     // Use EXPECT_EXIT to capture stderr and compare against expected output.
1316     //
1317     // Test VPValue::dump().
1318     VPValue *VPV = I1;
1319     EXPECT_EXIT(
1320         {
1321           VPV->dump();
1322           exit(0);
1323         },
1324         testing::ExitedWithCode(0), "EMIT vp<%1> = add ir<1>, ir<%a>");
1325 
1326     // Test VPRecipeBase::dump().
1327     VPRecipeBase *R = I1;
1328     EXPECT_EXIT(
1329         {
1330           R->dump();
1331           exit(0);
1332         },
1333         testing::ExitedWithCode(0), "EMIT vp<%1> = add ir<1>, ir<%a>");
1334 
1335     // Test VPDef::dump().
1336     VPDef *D = I1;
1337     EXPECT_EXIT(
1338         {
1339           D->dump();
1340           exit(0);
1341         },
1342         testing::ExitedWithCode(0), "EMIT vp<%1> = add ir<1>, ir<%a>");
1343   }
1344   // Check printing I2.
1345   {
1346     // Use EXPECT_EXIT to capture stderr and compare against expected output.
1347     //
1348     // Test VPValue::dump().
1349     VPValue *VPV = I2;
1350     EXPECT_EXIT(
1351         {
1352           VPV->dump();
1353           exit(0);
1354         },
1355         testing::ExitedWithCode(0), "EMIT vp<%2> = mul vp<%1>, vp<%1>");
1356 
1357     // Test VPRecipeBase::dump().
1358     VPRecipeBase *R = I2;
1359     EXPECT_EXIT(
1360         {
1361           R->dump();
1362           exit(0);
1363         },
1364         testing::ExitedWithCode(0), "EMIT vp<%2> = mul vp<%1>, vp<%1>");
1365 
1366     // Test VPDef::dump().
1367     VPDef *D = I2;
1368     EXPECT_EXIT(
1369         {
1370           D->dump();
1371           exit(0);
1372         },
1373         testing::ExitedWithCode(0), "EMIT vp<%2> = mul vp<%1>, vp<%1>");
1374   }
1375   delete AI;
1376 }
1377 
1378 TEST(VPRecipeTest, dumpRecipeUnnamedVPValuesNotInPlanOrBlock) {
1379   LLVMContext C;
1380   IntegerType *Int32 = IntegerType::get(C, 32);
1381   auto *AI = BinaryOperator::CreateAdd(PoisonValue::get(Int32),
1382                                        PoisonValue::get(Int32));
1383   AI->setName("a");
1384   VPValue *ExtVPV1 = new VPValue(ConstantInt::get(Int32, 1));
1385   VPValue *ExtVPV2 = new VPValue(AI);
1386 
1387   VPInstruction *I1 = new VPInstruction(Instruction::Add, {ExtVPV1, ExtVPV2});
1388   VPInstruction *I2 = new VPInstruction(Instruction::Mul, {I1, I1});
1389 
1390   // Check printing I1.
1391   {
1392     // Use EXPECT_EXIT to capture stderr and compare against expected output.
1393     //
1394     // Test VPValue::dump().
1395     VPValue *VPV = I1;
1396     EXPECT_EXIT(
1397         {
1398           VPV->dump();
1399           exit(0);
1400         },
1401         testing::ExitedWithCode(0), "EMIT <badref> = add ir<1>, ir<%a>");
1402 
1403     // Test VPRecipeBase::dump().
1404     VPRecipeBase *R = I1;
1405     EXPECT_EXIT(
1406         {
1407           R->dump();
1408           exit(0);
1409         },
1410         testing::ExitedWithCode(0), "EMIT <badref> = add ir<1>, ir<%a>");
1411 
1412     // Test VPDef::dump().
1413     VPDef *D = I1;
1414     EXPECT_EXIT(
1415         {
1416           D->dump();
1417           exit(0);
1418         },
1419         testing::ExitedWithCode(0), "EMIT <badref> = add ir<1>, ir<%a>");
1420   }
1421   // Check printing I2.
1422   {
1423     // Use EXPECT_EXIT to capture stderr and compare against expected output.
1424     //
1425     // Test VPValue::dump().
1426     VPValue *VPV = I2;
1427     EXPECT_EXIT(
1428         {
1429           VPV->dump();
1430           exit(0);
1431         },
1432         testing::ExitedWithCode(0), "EMIT <badref> = mul <badref>, <badref>");
1433 
1434     // Test VPRecipeBase::dump().
1435     VPRecipeBase *R = I2;
1436     EXPECT_EXIT(
1437         {
1438           R->dump();
1439           exit(0);
1440         },
1441         testing::ExitedWithCode(0), "EMIT <badref> = mul <badref>, <badref>");
1442 
1443     // Test VPDef::dump().
1444     VPDef *D = I2;
1445     EXPECT_EXIT(
1446         {
1447           D->dump();
1448           exit(0);
1449         },
1450         testing::ExitedWithCode(0), "EMIT <badref> = mul <badref>, <badref>");
1451   }
1452 
1453   delete I2;
1454   delete I1;
1455   delete ExtVPV2;
1456   delete ExtVPV1;
1457   delete AI;
1458 }
1459 
1460 #endif
1461 
1462 TEST(VPRecipeTest, CastVPReductionRecipeToVPUser) {
1463   LLVMContext C;
1464 
1465   VPValue ChainOp;
1466   VPValue VecOp;
1467   VPValue CondOp;
1468   VPReductionRecipe Recipe(RecurrenceDescriptor(), nullptr, &ChainOp, &CondOp,
1469                            &VecOp, false);
1470   EXPECT_TRUE(isa<VPUser>(&Recipe));
1471   VPRecipeBase *BaseR = &Recipe;
1472   EXPECT_TRUE(isa<VPUser>(BaseR));
1473 }
1474 
1475 struct VPDoubleValueDef : public VPRecipeBase {
1476   VPDoubleValueDef(ArrayRef<VPValue *> Operands) : VPRecipeBase(99, Operands) {
1477     new VPValue(nullptr, this);
1478     new VPValue(nullptr, this);
1479   }
1480 
1481   VPRecipeBase *clone() override { return nullptr; }
1482 
1483   void execute(struct VPTransformState &State) override {}
1484 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1485   void print(raw_ostream &O, const Twine &Indent,
1486              VPSlotTracker &SlotTracker) const override {}
1487 #endif
1488 };
1489 
1490 TEST(VPDoubleValueDefTest, traverseUseLists) {
1491   // Check that the def-use chains of a multi-def can be traversed in both
1492   // directions.
1493 
1494   // Create a new VPDef which defines 2 values and has 2 operands.
1495   VPInstruction Op0(20, {});
1496   VPInstruction Op1(30, {});
1497   VPDoubleValueDef DoubleValueDef({&Op0, &Op1});
1498 
1499   // Create a new users of the defined values.
1500   VPInstruction I1(
1501       1, {DoubleValueDef.getVPValue(0), DoubleValueDef.getVPValue(1)});
1502   VPInstruction I2(2, {DoubleValueDef.getVPValue(0)});
1503   VPInstruction I3(3, {DoubleValueDef.getVPValue(1)});
1504 
1505   // Check operands of the VPDef (traversing upwards).
1506   SmallVector<VPValue *, 4> DoubleOperands(DoubleValueDef.op_begin(),
1507                                            DoubleValueDef.op_end());
1508   EXPECT_EQ(2u, DoubleOperands.size());
1509   EXPECT_EQ(&Op0, DoubleOperands[0]);
1510   EXPECT_EQ(&Op1, DoubleOperands[1]);
1511 
1512   // Check users of the defined values (traversing downwards).
1513   SmallVector<VPUser *, 4> DoubleValueDefV0Users(
1514       DoubleValueDef.getVPValue(0)->user_begin(),
1515       DoubleValueDef.getVPValue(0)->user_end());
1516   EXPECT_EQ(2u, DoubleValueDefV0Users.size());
1517   EXPECT_EQ(&I1, DoubleValueDefV0Users[0]);
1518   EXPECT_EQ(&I2, DoubleValueDefV0Users[1]);
1519 
1520   SmallVector<VPUser *, 4> DoubleValueDefV1Users(
1521       DoubleValueDef.getVPValue(1)->user_begin(),
1522       DoubleValueDef.getVPValue(1)->user_end());
1523   EXPECT_EQ(2u, DoubleValueDefV1Users.size());
1524   EXPECT_EQ(&I1, DoubleValueDefV1Users[0]);
1525   EXPECT_EQ(&I3, DoubleValueDefV1Users[1]);
1526 
1527   // Now check that we can get the right VPDef for each defined value.
1528   EXPECT_EQ(&DoubleValueDef, I1.getOperand(0)->getDefiningRecipe());
1529   EXPECT_EQ(&DoubleValueDef, I1.getOperand(1)->getDefiningRecipe());
1530   EXPECT_EQ(&DoubleValueDef, I2.getOperand(0)->getDefiningRecipe());
1531   EXPECT_EQ(&DoubleValueDef, I3.getOperand(0)->getDefiningRecipe());
1532 }
1533 
1534 TEST(VPRecipeTest, CastToVPSingleDefRecipe) {
1535   VPValue Start;
1536   VPEVLBasedIVPHIRecipe R(&Start, {});
1537   VPRecipeBase *B = &R;
1538   EXPECT_TRUE(isa<VPSingleDefRecipe>(B));
1539   // TODO: check other VPSingleDefRecipes.
1540 }
1541 
1542 } // namespace
1543 } // namespace llvm
1544