1 //===- llvm/unittests/Transforms/Vectorize/VPlanTest.cpp - VPlan tests ----===//
2 //
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "../lib/Transforms/Vectorize/VPlan.h"
11 #include "llvm/ADT/DepthFirstIterator.h"
12 #include "llvm/ADT/PostOrderIterator.h"
13 #include "llvm/Analysis/VectorUtils.h"
14 #include "llvm/IR/Instruction.h"
15 #include "llvm/IR/Instructions.h"
16 #include "gtest/gtest.h"
17 #include <string>
18 
19 namespace llvm {
20 namespace {
21 
22 #define CHECK_ITERATOR(Range1, ...)                                            \
23   do {                                                                         \
24     std::vector<VPInstruction *> Tmp = {__VA_ARGS__};                          \
25     EXPECT_EQ((size_t)std::distance(Range1.begin(), Range1.end()),             \
26               Tmp.size());                                                     \
27     for (auto Pair : zip(Range1, make_range(Tmp.begin(), Tmp.end())))          \
28       EXPECT_EQ(&std::get<0>(Pair), std::get<1>(Pair));                        \
29   } while (0)
30 
31 TEST(VPInstructionTest, insertBefore) {
32   VPInstruction *I1 = new VPInstruction(0, {});
33   VPInstruction *I2 = new VPInstruction(1, {});
34   VPInstruction *I3 = new VPInstruction(2, {});
35 
36   VPBasicBlock VPBB1;
37   VPBB1.appendRecipe(I1);
38 
39   I2->insertBefore(I1);
40   CHECK_ITERATOR(VPBB1, I2, I1);
41 
42   I3->insertBefore(I2);
43   CHECK_ITERATOR(VPBB1, I3, I2, I1);
44 }
45 
46 TEST(VPInstructionTest, eraseFromParent) {
47   VPInstruction *I1 = new VPInstruction(0, {});
48   VPInstruction *I2 = new VPInstruction(1, {});
49   VPInstruction *I3 = new VPInstruction(2, {});
50 
51   VPBasicBlock VPBB1;
52   VPBB1.appendRecipe(I1);
53   VPBB1.appendRecipe(I2);
54   VPBB1.appendRecipe(I3);
55 
56   I2->eraseFromParent();
57   CHECK_ITERATOR(VPBB1, I1, I3);
58 
59   I1->eraseFromParent();
60   CHECK_ITERATOR(VPBB1, I3);
61 
62   I3->eraseFromParent();
63   EXPECT_TRUE(VPBB1.empty());
64 }
65 
66 TEST(VPInstructionTest, moveAfter) {
67   VPInstruction *I1 = new VPInstruction(0, {});
68   VPInstruction *I2 = new VPInstruction(1, {});
69   VPInstruction *I3 = new VPInstruction(2, {});
70 
71   VPBasicBlock VPBB1;
72   VPBB1.appendRecipe(I1);
73   VPBB1.appendRecipe(I2);
74   VPBB1.appendRecipe(I3);
75 
76   I1->moveAfter(I2);
77 
78   CHECK_ITERATOR(VPBB1, I2, I1, I3);
79 
80   VPInstruction *I4 = new VPInstruction(4, {});
81   VPInstruction *I5 = new VPInstruction(5, {});
82   VPBasicBlock VPBB2;
83   VPBB2.appendRecipe(I4);
84   VPBB2.appendRecipe(I5);
85 
86   I3->moveAfter(I4);
87 
88   CHECK_ITERATOR(VPBB1, I2, I1);
89   CHECK_ITERATOR(VPBB2, I4, I3, I5);
90   EXPECT_EQ(I3->getParent(), I4->getParent());
91 }
92 
93 TEST(VPInstructionTest, moveBefore) {
94   VPInstruction *I1 = new VPInstruction(0, {});
95   VPInstruction *I2 = new VPInstruction(1, {});
96   VPInstruction *I3 = new VPInstruction(2, {});
97 
98   VPBasicBlock VPBB1;
99   VPBB1.appendRecipe(I1);
100   VPBB1.appendRecipe(I2);
101   VPBB1.appendRecipe(I3);
102 
103   I1->moveBefore(VPBB1, I3->getIterator());
104 
105   CHECK_ITERATOR(VPBB1, I2, I1, I3);
106 
107   VPInstruction *I4 = new VPInstruction(4, {});
108   VPInstruction *I5 = new VPInstruction(5, {});
109   VPBasicBlock VPBB2;
110   VPBB2.appendRecipe(I4);
111   VPBB2.appendRecipe(I5);
112 
113   I3->moveBefore(VPBB2, I4->getIterator());
114 
115   CHECK_ITERATOR(VPBB1, I2, I1);
116   CHECK_ITERATOR(VPBB2, I3, I4, I5);
117   EXPECT_EQ(I3->getParent(), I4->getParent());
118 
119   VPBasicBlock VPBB3;
120 
121   I4->moveBefore(VPBB3, VPBB3.end());
122 
123   CHECK_ITERATOR(VPBB1, I2, I1);
124   CHECK_ITERATOR(VPBB2, I3, I5);
125   CHECK_ITERATOR(VPBB3, I4);
126   EXPECT_EQ(&VPBB3, I4->getParent());
127 }
128 
129 TEST(VPInstructionTest, setOperand) {
130   VPValue *VPV1 = new VPValue();
131   VPValue *VPV2 = new VPValue();
132   VPInstruction *I1 = new VPInstruction(0, {VPV1, VPV2});
133   EXPECT_EQ(1u, VPV1->getNumUsers());
134   EXPECT_EQ(I1, *VPV1->user_begin());
135   EXPECT_EQ(1u, VPV2->getNumUsers());
136   EXPECT_EQ(I1, *VPV2->user_begin());
137 
138   // Replace operand 0 (VPV1) with VPV3.
139   VPValue *VPV3 = new VPValue();
140   I1->setOperand(0, VPV3);
141   EXPECT_EQ(0u, VPV1->getNumUsers());
142   EXPECT_EQ(1u, VPV2->getNumUsers());
143   EXPECT_EQ(I1, *VPV2->user_begin());
144   EXPECT_EQ(1u, VPV3->getNumUsers());
145   EXPECT_EQ(I1, *VPV3->user_begin());
146 
147   // Replace operand 1 (VPV2) with VPV3.
148   I1->setOperand(1, VPV3);
149   EXPECT_EQ(0u, VPV1->getNumUsers());
150   EXPECT_EQ(0u, VPV2->getNumUsers());
151   EXPECT_EQ(2u, VPV3->getNumUsers());
152   EXPECT_EQ(I1, *VPV3->user_begin());
153   EXPECT_EQ(I1, *std::next(VPV3->user_begin()));
154 
155   // Replace operand 0 (VPV3) with VPV4.
156   VPValue *VPV4 = new VPValue();
157   I1->setOperand(0, VPV4);
158   EXPECT_EQ(1u, VPV3->getNumUsers());
159   EXPECT_EQ(I1, *VPV3->user_begin());
160   EXPECT_EQ(I1, *VPV4->user_begin());
161 
162   // Replace operand 1 (VPV3) with VPV4.
163   I1->setOperand(1, VPV4);
164   EXPECT_EQ(0u, VPV3->getNumUsers());
165   EXPECT_EQ(I1, *VPV4->user_begin());
166   EXPECT_EQ(I1, *std::next(VPV4->user_begin()));
167 
168   delete I1;
169   delete VPV1;
170   delete VPV2;
171   delete VPV3;
172   delete VPV4;
173 }
174 
175 TEST(VPInstructionTest, replaceAllUsesWith) {
176   VPValue *VPV1 = new VPValue();
177   VPValue *VPV2 = new VPValue();
178   VPInstruction *I1 = new VPInstruction(0, {VPV1, VPV2});
179 
180   // Replace all uses of VPV1 with VPV3.
181   VPValue *VPV3 = new VPValue();
182   VPV1->replaceAllUsesWith(VPV3);
183   EXPECT_EQ(VPV3, I1->getOperand(0));
184   EXPECT_EQ(VPV2, I1->getOperand(1));
185   EXPECT_EQ(0u, VPV1->getNumUsers());
186   EXPECT_EQ(1u, VPV2->getNumUsers());
187   EXPECT_EQ(I1, *VPV2->user_begin());
188   EXPECT_EQ(1u, VPV3->getNumUsers());
189   EXPECT_EQ(I1, *VPV3->user_begin());
190 
191   // Replace all uses of VPV2 with VPV3.
192   VPV2->replaceAllUsesWith(VPV3);
193   EXPECT_EQ(VPV3, I1->getOperand(0));
194   EXPECT_EQ(VPV3, I1->getOperand(1));
195   EXPECT_EQ(0u, VPV1->getNumUsers());
196   EXPECT_EQ(0u, VPV2->getNumUsers());
197   EXPECT_EQ(2u, VPV3->getNumUsers());
198   EXPECT_EQ(I1, *VPV3->user_begin());
199 
200   // Replace all uses of VPV3 with VPV1.
201   VPV3->replaceAllUsesWith(VPV1);
202   EXPECT_EQ(VPV1, I1->getOperand(0));
203   EXPECT_EQ(VPV1, I1->getOperand(1));
204   EXPECT_EQ(2u, VPV1->getNumUsers());
205   EXPECT_EQ(I1, *VPV1->user_begin());
206   EXPECT_EQ(0u, VPV2->getNumUsers());
207   EXPECT_EQ(0u, VPV3->getNumUsers());
208 
209   VPInstruction *I2 = new VPInstruction(0, {VPV1, VPV2});
210   EXPECT_EQ(3u, VPV1->getNumUsers());
211   VPV1->replaceAllUsesWith(VPV3);
212   EXPECT_EQ(3u, VPV3->getNumUsers());
213 
214   delete I1;
215   delete I2;
216   delete VPV1;
217   delete VPV2;
218   delete VPV3;
219 }
220 
221 TEST(VPInstructionTest, releaseOperandsAtDeletion) {
222   VPValue *VPV1 = new VPValue();
223   VPValue *VPV2 = new VPValue();
224   VPInstruction *I1 = new VPInstruction(0, {VPV1, VPV2});
225 
226   EXPECT_EQ(1u, VPV1->getNumUsers());
227   EXPECT_EQ(I1, *VPV1->user_begin());
228   EXPECT_EQ(1u, VPV2->getNumUsers());
229   EXPECT_EQ(I1, *VPV2->user_begin());
230 
231   delete I1;
232 
233   EXPECT_EQ(0u, VPV1->getNumUsers());
234   EXPECT_EQ(0u, VPV2->getNumUsers());
235 
236   delete VPV1;
237   delete VPV2;
238 }
239 TEST(VPBasicBlockTest, getPlan) {
240   {
241     VPBasicBlock *VPBB1 = new VPBasicBlock();
242     VPBasicBlock *VPBB2 = new VPBasicBlock();
243     VPBasicBlock *VPBB3 = new VPBasicBlock();
244     VPBasicBlock *VPBB4 = new VPBasicBlock();
245 
246     //     VPBB1
247     //     /   \
248     // VPBB2  VPBB3
249     //    \    /
250     //    VPBB4
251     VPBlockUtils::connectBlocks(VPBB1, VPBB2);
252     VPBlockUtils::connectBlocks(VPBB1, VPBB3);
253     VPBlockUtils::connectBlocks(VPBB2, VPBB4);
254     VPBlockUtils::connectBlocks(VPBB3, VPBB4);
255 
256     VPlan Plan;
257     Plan.setEntry(VPBB1);
258 
259     EXPECT_EQ(&Plan, VPBB1->getPlan());
260     EXPECT_EQ(&Plan, VPBB2->getPlan());
261     EXPECT_EQ(&Plan, VPBB3->getPlan());
262     EXPECT_EQ(&Plan, VPBB4->getPlan());
263   }
264 
265   {
266     // Region block is entry into VPlan.
267     VPBasicBlock *R1BB1 = new VPBasicBlock();
268     VPBasicBlock *R1BB2 = new VPBasicBlock();
269     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB2, "R1");
270     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
271 
272     VPlan Plan;
273     Plan.setEntry(R1);
274     EXPECT_EQ(&Plan, R1->getPlan());
275     EXPECT_EQ(&Plan, R1BB1->getPlan());
276     EXPECT_EQ(&Plan, R1BB2->getPlan());
277   }
278 
279   {
280     // VPBasicBlock is the entry into the VPlan, followed by a region.
281     VPBasicBlock *R1BB1 = new VPBasicBlock();
282     VPBasicBlock *R1BB2 = new VPBasicBlock();
283     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB2, "R1");
284     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
285 
286     VPBasicBlock *VPBB1 = new VPBasicBlock();
287     VPBlockUtils::connectBlocks(VPBB1, R1);
288 
289     VPlan Plan;
290     Plan.setEntry(VPBB1);
291     EXPECT_EQ(&Plan, VPBB1->getPlan());
292     EXPECT_EQ(&Plan, R1->getPlan());
293     EXPECT_EQ(&Plan, R1BB1->getPlan());
294     EXPECT_EQ(&Plan, R1BB2->getPlan());
295   }
296 
297   {
298     VPBasicBlock *R1BB1 = new VPBasicBlock();
299     VPBasicBlock *R1BB2 = new VPBasicBlock();
300     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB2, "R1");
301     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
302 
303     VPBasicBlock *R2BB1 = new VPBasicBlock();
304     VPBasicBlock *R2BB2 = new VPBasicBlock();
305     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
306     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
307 
308     VPBasicBlock *VPBB1 = new VPBasicBlock();
309     VPBlockUtils::connectBlocks(VPBB1, R1);
310     VPBlockUtils::connectBlocks(VPBB1, R2);
311 
312     VPBasicBlock *VPBB2 = new VPBasicBlock();
313     VPBlockUtils::connectBlocks(R1, VPBB2);
314     VPBlockUtils::connectBlocks(R2, VPBB2);
315 
316     VPlan Plan;
317     Plan.setEntry(VPBB1);
318     EXPECT_EQ(&Plan, VPBB1->getPlan());
319     EXPECT_EQ(&Plan, R1->getPlan());
320     EXPECT_EQ(&Plan, R1BB1->getPlan());
321     EXPECT_EQ(&Plan, R1BB2->getPlan());
322     EXPECT_EQ(&Plan, R2->getPlan());
323     EXPECT_EQ(&Plan, R2BB1->getPlan());
324     EXPECT_EQ(&Plan, R2BB2->getPlan());
325     EXPECT_EQ(&Plan, VPBB2->getPlan());
326   }
327 }
328 
329 TEST(VPBasicBlockTest, TraversingIteratorTest) {
330   {
331     // VPBasicBlocks only
332     //     VPBB1
333     //     /   \
334     // VPBB2  VPBB3
335     //    \    /
336     //    VPBB4
337     //
338     VPBasicBlock *VPBB1 = new VPBasicBlock();
339     VPBasicBlock *VPBB2 = new VPBasicBlock();
340     VPBasicBlock *VPBB3 = new VPBasicBlock();
341     VPBasicBlock *VPBB4 = new VPBasicBlock();
342 
343     VPBlockUtils::connectBlocks(VPBB1, VPBB2);
344     VPBlockUtils::connectBlocks(VPBB1, VPBB3);
345     VPBlockUtils::connectBlocks(VPBB2, VPBB4);
346     VPBlockUtils::connectBlocks(VPBB3, VPBB4);
347 
348     VPBlockRecursiveTraversalWrapper<const VPBlockBase *> Start(VPBB1);
349     SmallVector<const VPBlockBase *> FromIterator(depth_first(Start));
350     EXPECT_EQ(4u, FromIterator.size());
351     EXPECT_EQ(VPBB1, FromIterator[0]);
352     EXPECT_EQ(VPBB2, FromIterator[1]);
353 
354     // Use Plan to properly clean up created blocks.
355     VPlan Plan;
356     Plan.setEntry(VPBB1);
357   }
358 
359   {
360     // 2 consecutive regions.
361     // R1 {
362     //     \
363     //     R1BB1
364     //    /     \   |--|
365     //  R1BB2   R1BB3 -|
366     //    \      /
367     //     R1BB4
368     //  }
369     //   |
370     // R2 {
371     //   \
372     //    R2BB1
373     //      |
374     //    R2BB2
375     //
376     VPBasicBlock *R1BB1 = new VPBasicBlock();
377     VPBasicBlock *R1BB2 = new VPBasicBlock();
378     VPBasicBlock *R1BB3 = new VPBasicBlock();
379     VPBasicBlock *R1BB4 = new VPBasicBlock();
380     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB4, "R1");
381     R1BB2->setParent(R1);
382     R1BB3->setParent(R1);
383     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
384     VPBlockUtils::connectBlocks(R1BB1, R1BB3);
385     VPBlockUtils::connectBlocks(R1BB2, R1BB4);
386     VPBlockUtils::connectBlocks(R1BB3, R1BB4);
387     // Cycle.
388     VPBlockUtils::connectBlocks(R1BB3, R1BB3);
389 
390     VPBasicBlock *R2BB1 = new VPBasicBlock();
391     VPBasicBlock *R2BB2 = new VPBasicBlock();
392     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
393     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
394     VPBlockUtils::connectBlocks(R1, R2);
395 
396     // Depth-first.
397     VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(R1);
398     SmallVector<const VPBlockBase *> FromIterator(df_begin(Start),
399                                                   df_end(Start));
400     EXPECT_EQ(8u, FromIterator.size());
401     EXPECT_EQ(R1, FromIterator[0]);
402     EXPECT_EQ(R1BB1, FromIterator[1]);
403     EXPECT_EQ(R1BB2, FromIterator[2]);
404     EXPECT_EQ(R1BB4, FromIterator[3]);
405     EXPECT_EQ(R2, FromIterator[4]);
406     EXPECT_EQ(R2BB1, FromIterator[5]);
407     EXPECT_EQ(R2BB2, FromIterator[6]);
408     EXPECT_EQ(R1BB3, FromIterator[7]);
409 
410     // const VPBasicBlocks only.
411     FromIterator.clear();
412     copy(VPBlockUtils::blocksOnly<const VPBasicBlock>(depth_first(Start)),
413          std::back_inserter(FromIterator));
414     EXPECT_EQ(6u, FromIterator.size());
415     EXPECT_EQ(R1BB1, FromIterator[0]);
416     EXPECT_EQ(R1BB2, FromIterator[1]);
417     EXPECT_EQ(R1BB4, FromIterator[2]);
418     EXPECT_EQ(R2BB1, FromIterator[3]);
419     EXPECT_EQ(R2BB2, FromIterator[4]);
420     EXPECT_EQ(R1BB3, FromIterator[5]);
421 
422     // VPRegionBlocks only.
423     SmallVector<VPRegionBlock *> FromIteratorVPRegion(
424         VPBlockUtils::blocksOnly<VPRegionBlock>(depth_first(Start)));
425     EXPECT_EQ(2u, FromIteratorVPRegion.size());
426     EXPECT_EQ(R1, FromIteratorVPRegion[0]);
427     EXPECT_EQ(R2, FromIteratorVPRegion[1]);
428 
429     // Post-order.
430     FromIterator.clear();
431     copy(post_order(Start), std::back_inserter(FromIterator));
432     EXPECT_EQ(8u, FromIterator.size());
433     EXPECT_EQ(R2BB2, FromIterator[0]);
434     EXPECT_EQ(R2BB1, FromIterator[1]);
435     EXPECT_EQ(R2, FromIterator[2]);
436     EXPECT_EQ(R1BB4, FromIterator[3]);
437     EXPECT_EQ(R1BB2, FromIterator[4]);
438     EXPECT_EQ(R1BB3, FromIterator[5]);
439     EXPECT_EQ(R1BB1, FromIterator[6]);
440     EXPECT_EQ(R1, FromIterator[7]);
441 
442     // Use Plan to properly clean up created blocks.
443     VPlan Plan;
444     Plan.setEntry(R1);
445   }
446 
447   {
448     // 2 nested regions.
449     //  VPBB1
450     //    |
451     //  R1 {
452     //         R1BB1
453     //       /        \
454     //   R2 {          |
455     //     \           |
456     //     R2BB1       |
457     //       |   \    R1BB2
458     //     R2BB2-|     |
459     //        \        |
460     //         R2BB3   |
461     //   }            /
462     //      \        /
463     //        R1BB3
464     //  }
465     //   |
466     //  VPBB2
467     //
468     VPBasicBlock *R1BB1 = new VPBasicBlock("R1BB1");
469     VPBasicBlock *R1BB2 = new VPBasicBlock("R1BB2");
470     VPBasicBlock *R1BB3 = new VPBasicBlock("R1BB3");
471     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB3, "R1");
472 
473     VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
474     VPBasicBlock *R2BB2 = new VPBasicBlock("R2BB2");
475     VPBasicBlock *R2BB3 = new VPBasicBlock("R2BB3");
476     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB3, "R2");
477     R2BB2->setParent(R2);
478     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
479     VPBlockUtils::connectBlocks(R2BB2, R2BB1);
480     VPBlockUtils::connectBlocks(R2BB2, R2BB3);
481 
482     R2->setParent(R1);
483     VPBlockUtils::connectBlocks(R1BB1, R2);
484     R1BB2->setParent(R1);
485     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
486     VPBlockUtils::connectBlocks(R1BB2, R1BB3);
487     VPBlockUtils::connectBlocks(R2, R1BB3);
488 
489     VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
490     VPBlockUtils::connectBlocks(VPBB1, R1);
491     VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
492     VPBlockUtils::connectBlocks(R1, VPBB2);
493 
494     // Depth-first.
495     VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(VPBB1);
496     SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
497     EXPECT_EQ(10u, FromIterator.size());
498     EXPECT_EQ(VPBB1, FromIterator[0]);
499     EXPECT_EQ(R1, FromIterator[1]);
500     EXPECT_EQ(R1BB1, FromIterator[2]);
501     EXPECT_EQ(R2, FromIterator[3]);
502     EXPECT_EQ(R2BB1, FromIterator[4]);
503     EXPECT_EQ(R2BB2, FromIterator[5]);
504     EXPECT_EQ(R2BB3, FromIterator[6]);
505     EXPECT_EQ(R1BB3, FromIterator[7]);
506     EXPECT_EQ(VPBB2, FromIterator[8]);
507     EXPECT_EQ(R1BB2, FromIterator[9]);
508 
509     // Post-order.
510     FromIterator.clear();
511     FromIterator.append(po_begin(Start), po_end(Start));
512     EXPECT_EQ(10u, FromIterator.size());
513     EXPECT_EQ(VPBB2, FromIterator[0]);
514     EXPECT_EQ(R1BB3, FromIterator[1]);
515     EXPECT_EQ(R2BB3, FromIterator[2]);
516     EXPECT_EQ(R2BB2, FromIterator[3]);
517     EXPECT_EQ(R2BB1, FromIterator[4]);
518     EXPECT_EQ(R2, FromIterator[5]);
519     EXPECT_EQ(R1BB2, FromIterator[6]);
520     EXPECT_EQ(R1BB1, FromIterator[7]);
521     EXPECT_EQ(R1, FromIterator[8]);
522     EXPECT_EQ(VPBB1, FromIterator[9]);
523 
524     // Use Plan to properly clean up created blocks.
525     VPlan Plan;
526     Plan.setEntry(VPBB1);
527   }
528 
529   {
530     //  VPBB1
531     //    |
532     //  R1 {
533     //    \
534     //     R2 {
535     //      R2BB1
536     //        |
537     //      R2BB2
538     //   }
539     //
540     VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
541     VPBasicBlock *R2BB2 = new VPBasicBlock("R2BB2");
542     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
543     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
544 
545     VPRegionBlock *R1 = new VPRegionBlock(R2, R2, "R1");
546     R2->setParent(R1);
547 
548     VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
549     VPBlockUtils::connectBlocks(VPBB1, R1);
550 
551     // Depth-first.
552     VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(VPBB1);
553     SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
554     EXPECT_EQ(5u, FromIterator.size());
555     EXPECT_EQ(VPBB1, FromIterator[0]);
556     EXPECT_EQ(R1, FromIterator[1]);
557     EXPECT_EQ(R2, FromIterator[2]);
558     EXPECT_EQ(R2BB1, FromIterator[3]);
559     EXPECT_EQ(R2BB2, FromIterator[4]);
560 
561     // Post-order.
562     FromIterator.clear();
563     FromIterator.append(po_begin(Start), po_end(Start));
564     EXPECT_EQ(5u, FromIterator.size());
565     EXPECT_EQ(R2BB2, FromIterator[0]);
566     EXPECT_EQ(R2BB1, FromIterator[1]);
567     EXPECT_EQ(R2, FromIterator[2]);
568     EXPECT_EQ(R1, FromIterator[3]);
569     EXPECT_EQ(VPBB1, FromIterator[4]);
570 
571     // Use Plan to properly clean up created blocks.
572     VPlan Plan;
573     Plan.setEntry(VPBB1);
574   }
575 
576   {
577     //  Nested regions with both R3 and R2 being exit nodes without successors.
578     //  The successors of R1 should be used.
579     //
580     //  VPBB1
581     //    |
582     //  R1 {
583     //    \
584     //     R2 {
585     //      \
586     //      R2BB1
587     //        |
588     //       R3 {
589     //          R3BB1
590     //      }
591     //   }
592     //   |
593     //  VPBB2
594     //
595     VPBasicBlock *R3BB1 = new VPBasicBlock("R3BB1");
596     VPRegionBlock *R3 = new VPRegionBlock(R3BB1, R3BB1, "R3");
597 
598     VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
599     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R3, "R2");
600     R3->setParent(R2);
601     VPBlockUtils::connectBlocks(R2BB1, R3);
602 
603     VPRegionBlock *R1 = new VPRegionBlock(R2, R2, "R1");
604     R2->setParent(R1);
605 
606     VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
607     VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
608     VPBlockUtils::connectBlocks(VPBB1, R1);
609     VPBlockUtils::connectBlocks(R1, VPBB2);
610 
611     // Depth-first.
612     VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(VPBB1);
613     SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
614     EXPECT_EQ(7u, FromIterator.size());
615     EXPECT_EQ(VPBB1, FromIterator[0]);
616     EXPECT_EQ(R1, FromIterator[1]);
617     EXPECT_EQ(R2, FromIterator[2]);
618     EXPECT_EQ(R2BB1, FromIterator[3]);
619     EXPECT_EQ(R3, FromIterator[4]);
620     EXPECT_EQ(R3BB1, FromIterator[5]);
621     EXPECT_EQ(VPBB2, FromIterator[6]);
622 
623     SmallVector<VPBlockBase *> FromIteratorVPBB;
624     copy(VPBlockUtils::blocksOnly<VPBasicBlock>(depth_first(Start)),
625          std::back_inserter(FromIteratorVPBB));
626     EXPECT_EQ(VPBB1, FromIteratorVPBB[0]);
627     EXPECT_EQ(R2BB1, FromIteratorVPBB[1]);
628     EXPECT_EQ(R3BB1, FromIteratorVPBB[2]);
629     EXPECT_EQ(VPBB2, FromIteratorVPBB[3]);
630 
631     // Post-order.
632     FromIterator.clear();
633     copy(post_order(Start), std::back_inserter(FromIterator));
634     EXPECT_EQ(7u, FromIterator.size());
635     EXPECT_EQ(VPBB2, FromIterator[0]);
636     EXPECT_EQ(R3BB1, FromIterator[1]);
637     EXPECT_EQ(R3, FromIterator[2]);
638     EXPECT_EQ(R2BB1, FromIterator[3]);
639     EXPECT_EQ(R2, FromIterator[4]);
640     EXPECT_EQ(R1, FromIterator[5]);
641     EXPECT_EQ(VPBB1, FromIterator[6]);
642 
643     // Post-order, const VPRegionBlocks only.
644     VPBlockRecursiveTraversalWrapper<const VPBlockBase *> StartConst(VPBB1);
645     SmallVector<const VPRegionBlock *> FromIteratorVPRegion(
646         VPBlockUtils::blocksOnly<const VPRegionBlock>(post_order(StartConst)));
647     EXPECT_EQ(3u, FromIteratorVPRegion.size());
648     EXPECT_EQ(R3, FromIteratorVPRegion[0]);
649     EXPECT_EQ(R2, FromIteratorVPRegion[1]);
650     EXPECT_EQ(R1, FromIteratorVPRegion[2]);
651 
652     // Post-order, VPBasicBlocks only.
653     FromIterator.clear();
654     copy(VPBlockUtils::blocksOnly<VPBasicBlock>(post_order(Start)),
655          std::back_inserter(FromIterator));
656     EXPECT_EQ(FromIterator.size(), 4u);
657     EXPECT_EQ(VPBB2, FromIterator[0]);
658     EXPECT_EQ(R3BB1, FromIterator[1]);
659     EXPECT_EQ(R2BB1, FromIterator[2]);
660     EXPECT_EQ(VPBB1, FromIterator[3]);
661 
662     // Use Plan to properly clean up created blocks.
663     VPlan Plan;
664     Plan.setEntry(VPBB1);
665   }
666 }
667 
668 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
669 TEST(VPBasicBlockTest, print) {
670   VPInstruction *I1 = new VPInstruction(Instruction::Add, {});
671   VPInstruction *I2 = new VPInstruction(Instruction::Sub, {I1});
672   VPInstruction *I3 = new VPInstruction(Instruction::Br, {I1, I2});
673 
674   VPBasicBlock *VPBB1 = new VPBasicBlock();
675   VPBB1->appendRecipe(I1);
676   VPBB1->appendRecipe(I2);
677   VPBB1->appendRecipe(I3);
678   VPBB1->setName("bb1");
679 
680   VPInstruction *I4 = new VPInstruction(Instruction::Mul, {I2, I1});
681   VPInstruction *I5 = new VPInstruction(Instruction::Ret, {I4});
682   VPBasicBlock *VPBB2 = new VPBasicBlock();
683   VPBB2->appendRecipe(I4);
684   VPBB2->appendRecipe(I5);
685   VPBB2->setName("bb2");
686 
687   VPBlockUtils::connectBlocks(VPBB1, VPBB2);
688 
689   // Check printing an instruction without associated VPlan.
690   {
691     std::string I3Dump;
692     raw_string_ostream OS(I3Dump);
693     VPSlotTracker SlotTracker;
694     I3->print(OS, "", SlotTracker);
695     OS.flush();
696     EXPECT_EQ("EMIT br <badref> <badref>", I3Dump);
697   }
698 
699   VPlan Plan;
700   Plan.setEntry(VPBB1);
701   std::string FullDump;
702   raw_string_ostream OS(FullDump);
703   Plan.printDOT(OS);
704 
705   const char *ExpectedStr = R"(digraph VPlan {
706 graph [labelloc=t, fontsize=30; label="Vectorization Plan"]
707 node [shape=rect, fontname=Courier, fontsize=30]
708 edge [fontname=Courier, fontsize=30]
709 compound=true
710   N0 [label =
711     "bb1:\l" +
712     "  EMIT vp\<%1\> = add\l" +
713     "  EMIT vp\<%2\> = sub vp\<%1\>\l" +
714     "  EMIT br vp\<%1\> vp\<%2\>\l" +
715     "Successor(s): bb2\l"
716   ]
717   N0 -> N1 [ label=""]
718   N1 [label =
719     "bb2:\l" +
720     "  EMIT vp\<%4\> = mul vp\<%2\> vp\<%1\>\l" +
721     "  EMIT ret vp\<%4\>\l" +
722     "No successors\l"
723   ]
724 }
725 )";
726   EXPECT_EQ(ExpectedStr, FullDump);
727 
728   const char *ExpectedBlock1Str = R"(bb1:
729   EMIT vp<%1> = add
730   EMIT vp<%2> = sub vp<%1>
731   EMIT br vp<%1> vp<%2>
732 Successor(s): bb2
733 )";
734   std::string Block1Dump;
735   raw_string_ostream OS1(Block1Dump);
736   VPBB1->print(OS1);
737   EXPECT_EQ(ExpectedBlock1Str, Block1Dump);
738 
739   // Ensure that numbering is good when dumping the second block in isolation.
740   const char *ExpectedBlock2Str = R"(bb2:
741   EMIT vp<%4> = mul vp<%2> vp<%1>
742   EMIT ret vp<%4>
743 No successors
744 )";
745   std::string Block2Dump;
746   raw_string_ostream OS2(Block2Dump);
747   VPBB2->print(OS2);
748   EXPECT_EQ(ExpectedBlock2Str, Block2Dump);
749 
750   {
751     std::string I3Dump;
752     raw_string_ostream OS(I3Dump);
753     VPSlotTracker SlotTracker(&Plan);
754     I3->print(OS, "", SlotTracker);
755     OS.flush();
756     EXPECT_EQ("EMIT br vp<%1> vp<%2>", I3Dump);
757   }
758 
759   {
760     std::string I4Dump;
761     raw_string_ostream OS(I4Dump);
762     OS << *I4;
763     OS.flush();
764     EXPECT_EQ("EMIT vp<%4> = mul vp<%2> vp<%1>", I4Dump);
765   }
766 }
767 #endif
768 
769 TEST(VPRecipeTest, CastVPInstructionToVPUser) {
770   VPValue Op1;
771   VPValue Op2;
772   VPInstruction Recipe(Instruction::Add, {&Op1, &Op2});
773   EXPECT_TRUE(isa<VPUser>(&Recipe));
774   VPRecipeBase *BaseR = &Recipe;
775   EXPECT_TRUE(isa<VPUser>(BaseR));
776   EXPECT_EQ(&Recipe, BaseR);
777 }
778 
779 TEST(VPRecipeTest, CastVPWidenRecipeToVPUser) {
780   LLVMContext C;
781 
782   IntegerType *Int32 = IntegerType::get(C, 32);
783   auto *AI =
784       BinaryOperator::CreateAdd(UndefValue::get(Int32), UndefValue::get(Int32));
785   VPValue Op1;
786   VPValue Op2;
787   SmallVector<VPValue *, 2> Args;
788   Args.push_back(&Op1);
789   Args.push_back(&Op1);
790   VPWidenRecipe WidenR(*AI, make_range(Args.begin(), Args.end()));
791   EXPECT_TRUE(isa<VPUser>(&WidenR));
792   VPRecipeBase *WidenRBase = &WidenR;
793   EXPECT_TRUE(isa<VPUser>(WidenRBase));
794   EXPECT_EQ(&WidenR, WidenRBase);
795   delete AI;
796 }
797 
798 TEST(VPRecipeTest, CastVPWidenCallRecipeToVPUserAndVPDef) {
799   LLVMContext C;
800 
801   IntegerType *Int32 = IntegerType::get(C, 32);
802   FunctionType *FTy = FunctionType::get(Int32, false);
803   auto *Call = CallInst::Create(FTy, UndefValue::get(FTy));
804   VPValue Op1;
805   VPValue Op2;
806   SmallVector<VPValue *, 2> Args;
807   Args.push_back(&Op1);
808   Args.push_back(&Op2);
809   VPWidenCallRecipe Recipe(*Call, make_range(Args.begin(), Args.end()));
810   EXPECT_TRUE(isa<VPUser>(&Recipe));
811   VPRecipeBase *BaseR = &Recipe;
812   EXPECT_TRUE(isa<VPUser>(BaseR));
813   EXPECT_EQ(&Recipe, BaseR);
814 
815   VPValue *VPV = &Recipe;
816   EXPECT_TRUE(isa<VPRecipeBase>(VPV->getDef()));
817   EXPECT_EQ(&Recipe, dyn_cast<VPRecipeBase>(VPV->getDef()));
818 
819   delete Call;
820 }
821 
822 TEST(VPRecipeTest, CastVPWidenSelectRecipeToVPUserAndVPDef) {
823   LLVMContext C;
824 
825   IntegerType *Int1 = IntegerType::get(C, 1);
826   IntegerType *Int32 = IntegerType::get(C, 32);
827   auto *SelectI = SelectInst::Create(
828       UndefValue::get(Int1), UndefValue::get(Int32), UndefValue::get(Int32));
829   VPValue Op1;
830   VPValue Op2;
831   VPValue Op3;
832   SmallVector<VPValue *, 4> Args;
833   Args.push_back(&Op1);
834   Args.push_back(&Op2);
835   Args.push_back(&Op3);
836   VPWidenSelectRecipe WidenSelectR(*SelectI,
837                                    make_range(Args.begin(), Args.end()), false);
838   EXPECT_TRUE(isa<VPUser>(&WidenSelectR));
839   VPRecipeBase *BaseR = &WidenSelectR;
840   EXPECT_TRUE(isa<VPUser>(BaseR));
841   EXPECT_EQ(&WidenSelectR, BaseR);
842 
843   VPValue *VPV = &WidenSelectR;
844   EXPECT_TRUE(isa<VPRecipeBase>(VPV->getDef()));
845   EXPECT_EQ(&WidenSelectR, dyn_cast<VPRecipeBase>(VPV->getDef()));
846 
847   delete SelectI;
848 }
849 
850 TEST(VPRecipeTest, CastVPWidenGEPRecipeToVPUserAndVPDef) {
851   LLVMContext C;
852 
853   IntegerType *Int32 = IntegerType::get(C, 32);
854   PointerType *Int32Ptr = PointerType::get(Int32, 0);
855   auto *GEP = GetElementPtrInst::Create(Int32, UndefValue::get(Int32Ptr),
856                                         UndefValue::get(Int32));
857   VPValue Op1;
858   VPValue Op2;
859   SmallVector<VPValue *, 4> Args;
860   Args.push_back(&Op1);
861   Args.push_back(&Op2);
862   VPWidenGEPRecipe Recipe(GEP, make_range(Args.begin(), Args.end()));
863   EXPECT_TRUE(isa<VPUser>(&Recipe));
864   VPRecipeBase *BaseR = &Recipe;
865   EXPECT_TRUE(isa<VPUser>(BaseR));
866   EXPECT_EQ(&Recipe, BaseR);
867 
868   VPValue *VPV = &Recipe;
869   EXPECT_TRUE(isa<VPRecipeBase>(VPV->getDef()));
870   EXPECT_EQ(&Recipe, dyn_cast<VPRecipeBase>(VPV->getDef()));
871 
872   delete GEP;
873 }
874 
875 TEST(VPRecipeTest, CastVPBlendRecipeToVPUser) {
876   LLVMContext C;
877 
878   IntegerType *Int32 = IntegerType::get(C, 32);
879   auto *Phi = PHINode::Create(Int32, 1);
880   VPValue Op1;
881   VPValue Op2;
882   SmallVector<VPValue *, 4> Args;
883   Args.push_back(&Op1);
884   Args.push_back(&Op2);
885   VPBlendRecipe Recipe(Phi, Args);
886   EXPECT_TRUE(isa<VPUser>(&Recipe));
887   VPRecipeBase *BaseR = &Recipe;
888   EXPECT_TRUE(isa<VPUser>(BaseR));
889   delete Phi;
890 }
891 
892 TEST(VPRecipeTest, CastVPInterleaveRecipeToVPUser) {
893   LLVMContext C;
894 
895   VPValue Addr;
896   VPValue Mask;
897   InterleaveGroup<Instruction> IG(4, false, Align(4));
898   VPInterleaveRecipe Recipe(&IG, &Addr, {}, &Mask);
899   EXPECT_TRUE(isa<VPUser>(&Recipe));
900   VPRecipeBase *BaseR = &Recipe;
901   EXPECT_TRUE(isa<VPUser>(BaseR));
902   EXPECT_EQ(&Recipe, BaseR);
903 }
904 
905 TEST(VPRecipeTest, CastVPReplicateRecipeToVPUser) {
906   LLVMContext C;
907 
908   VPValue Op1;
909   VPValue Op2;
910   SmallVector<VPValue *, 4> Args;
911   Args.push_back(&Op1);
912   Args.push_back(&Op2);
913 
914   VPReplicateRecipe Recipe(nullptr, make_range(Args.begin(), Args.end()), true,
915                            false);
916   EXPECT_TRUE(isa<VPUser>(&Recipe));
917   VPRecipeBase *BaseR = &Recipe;
918   EXPECT_TRUE(isa<VPUser>(BaseR));
919 }
920 
921 TEST(VPRecipeTest, CastVPBranchOnMaskRecipeToVPUser) {
922   LLVMContext C;
923 
924   VPValue Mask;
925   VPBranchOnMaskRecipe Recipe(&Mask);
926   EXPECT_TRUE(isa<VPUser>(&Recipe));
927   VPRecipeBase *BaseR = &Recipe;
928   EXPECT_TRUE(isa<VPUser>(BaseR));
929   EXPECT_EQ(&Recipe, BaseR);
930 }
931 
932 TEST(VPRecipeTest, CastVPWidenMemoryInstructionRecipeToVPUserAndVPDef) {
933   LLVMContext C;
934 
935   IntegerType *Int32 = IntegerType::get(C, 32);
936   PointerType *Int32Ptr = PointerType::get(Int32, 0);
937   auto *Load =
938       new LoadInst(Int32, UndefValue::get(Int32Ptr), "", false, Align(1));
939   VPValue Addr;
940   VPValue Mask;
941   VPWidenMemoryInstructionRecipe Recipe(*Load, &Addr, &Mask, true, false);
942   EXPECT_TRUE(isa<VPUser>(&Recipe));
943   VPRecipeBase *BaseR = &Recipe;
944   EXPECT_TRUE(isa<VPUser>(BaseR));
945   EXPECT_EQ(&Recipe, BaseR);
946 
947   VPValue *VPV = Recipe.getVPSingleValue();
948   EXPECT_TRUE(isa<VPRecipeBase>(VPV->getDef()));
949   EXPECT_EQ(&Recipe, dyn_cast<VPRecipeBase>(VPV->getDef()));
950 
951   delete Load;
952 }
953 
954 TEST(VPRecipeTest, MayHaveSideEffectsAndMayReadWriteMemory) {
955   LLVMContext C;
956   IntegerType *Int1 = IntegerType::get(C, 1);
957   IntegerType *Int32 = IntegerType::get(C, 32);
958   PointerType *Int32Ptr = PointerType::get(Int32, 0);
959 
960   {
961     auto *AI = BinaryOperator::CreateAdd(UndefValue::get(Int32),
962                                          UndefValue::get(Int32));
963     VPValue Op1;
964     VPValue Op2;
965     SmallVector<VPValue *, 2> Args;
966     Args.push_back(&Op1);
967     Args.push_back(&Op1);
968     VPWidenRecipe Recipe(*AI, make_range(Args.begin(), Args.end()));
969     EXPECT_FALSE(Recipe.mayHaveSideEffects());
970     EXPECT_FALSE(Recipe.mayReadFromMemory());
971     EXPECT_FALSE(Recipe.mayWriteToMemory());
972     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
973     delete AI;
974   }
975 
976   {
977     auto *SelectI = SelectInst::Create(
978         UndefValue::get(Int1), UndefValue::get(Int32), UndefValue::get(Int32));
979     VPValue Op1;
980     VPValue Op2;
981     VPValue Op3;
982     SmallVector<VPValue *, 4> Args;
983     Args.push_back(&Op1);
984     Args.push_back(&Op2);
985     Args.push_back(&Op3);
986     VPWidenSelectRecipe Recipe(*SelectI, make_range(Args.begin(), Args.end()),
987                                false);
988     EXPECT_FALSE(Recipe.mayHaveSideEffects());
989     EXPECT_FALSE(Recipe.mayReadFromMemory());
990     EXPECT_FALSE(Recipe.mayWriteToMemory());
991     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
992     delete SelectI;
993   }
994 
995   {
996     auto *GEP = GetElementPtrInst::Create(Int32, UndefValue::get(Int32Ptr),
997                                           UndefValue::get(Int32));
998     VPValue Op1;
999     VPValue Op2;
1000     SmallVector<VPValue *, 4> Args;
1001     Args.push_back(&Op1);
1002     Args.push_back(&Op2);
1003     VPWidenGEPRecipe Recipe(GEP, make_range(Args.begin(), Args.end()));
1004     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1005     EXPECT_FALSE(Recipe.mayReadFromMemory());
1006     EXPECT_FALSE(Recipe.mayWriteToMemory());
1007     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1008     delete GEP;
1009   }
1010 
1011   {
1012     VPValue Mask;
1013     VPBranchOnMaskRecipe Recipe(&Mask);
1014     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1015     EXPECT_FALSE(Recipe.mayReadFromMemory());
1016     EXPECT_FALSE(Recipe.mayWriteToMemory());
1017     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1018   }
1019 
1020   {
1021     VPValue ChainOp;
1022     VPValue VecOp;
1023     VPValue CondOp;
1024     VPReductionRecipe Recipe(nullptr, nullptr, &ChainOp, &CondOp, &VecOp,
1025                              nullptr);
1026     EXPECT_FALSE(Recipe.mayHaveSideEffects());
1027     EXPECT_FALSE(Recipe.mayReadFromMemory());
1028     EXPECT_FALSE(Recipe.mayWriteToMemory());
1029     EXPECT_FALSE(Recipe.mayReadOrWriteMemory());
1030   }
1031 
1032   {
1033     auto *Load =
1034         new LoadInst(Int32, UndefValue::get(Int32Ptr), "", false, Align(1));
1035     VPValue Addr;
1036     VPValue Mask;
1037     VPWidenMemoryInstructionRecipe Recipe(*Load, &Addr, &Mask, true, false);
1038     EXPECT_TRUE(Recipe.mayHaveSideEffects());
1039     EXPECT_TRUE(Recipe.mayReadFromMemory());
1040     EXPECT_FALSE(Recipe.mayWriteToMemory());
1041     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1042     delete Load;
1043   }
1044 
1045   {
1046     auto *Store = new StoreInst(UndefValue::get(Int32),
1047                                 UndefValue::get(Int32Ptr), false, Align(1));
1048     VPValue Addr;
1049     VPValue Mask;
1050     VPValue StoredV;
1051     VPWidenMemoryInstructionRecipe Recipe(*Store, &Addr, &StoredV, &Mask, false,
1052                                           false);
1053     EXPECT_TRUE(Recipe.mayHaveSideEffects());
1054     EXPECT_FALSE(Recipe.mayReadFromMemory());
1055     EXPECT_TRUE(Recipe.mayWriteToMemory());
1056     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1057     delete Store;
1058   }
1059 
1060   {
1061     FunctionType *FTy = FunctionType::get(Int32, false);
1062     auto *Call = CallInst::Create(FTy, UndefValue::get(FTy));
1063     VPValue Op1;
1064     VPValue Op2;
1065     SmallVector<VPValue *, 2> Args;
1066     Args.push_back(&Op1);
1067     Args.push_back(&Op2);
1068     VPWidenCallRecipe Recipe(*Call, make_range(Args.begin(), Args.end()));
1069     EXPECT_TRUE(Recipe.mayHaveSideEffects());
1070     EXPECT_TRUE(Recipe.mayReadFromMemory());
1071     EXPECT_TRUE(Recipe.mayWriteToMemory());
1072     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1073     delete Call;
1074   }
1075 
1076   // The initial implementation is conservative with respect to VPInstructions.
1077   {
1078     VPValue Op1;
1079     VPValue Op2;
1080     VPInstruction VPInst(Instruction::Add, {&Op1, &Op2});
1081     VPRecipeBase &Recipe = VPInst;
1082     EXPECT_TRUE(Recipe.mayHaveSideEffects());
1083     EXPECT_TRUE(Recipe.mayReadFromMemory());
1084     EXPECT_TRUE(Recipe.mayWriteToMemory());
1085     EXPECT_TRUE(Recipe.mayReadOrWriteMemory());
1086   }
1087 }
1088 
1089 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1090 TEST(VPRecipeTest, dump) {
1091   VPlan Plan;
1092   VPBasicBlock *VPBB1 = new VPBasicBlock();
1093   Plan.setEntry(VPBB1);
1094 
1095   LLVMContext C;
1096 
1097   IntegerType *Int32 = IntegerType::get(C, 32);
1098   auto *AI =
1099       BinaryOperator::CreateAdd(UndefValue::get(Int32), UndefValue::get(Int32));
1100   AI->setName("a");
1101   SmallVector<VPValue *, 2> Args;
1102   VPValue *ExtVPV1 = Plan.getOrAddExternalDef(ConstantInt::get(Int32, 1));
1103   VPValue *ExtVPV2 = Plan.getOrAddExternalDef(ConstantInt::get(Int32, 2));
1104   Args.push_back(ExtVPV1);
1105   Args.push_back(ExtVPV2);
1106   VPWidenRecipe *WidenR =
1107       new VPWidenRecipe(*AI, make_range(Args.begin(), Args.end()));
1108   VPBB1->appendRecipe(WidenR);
1109 
1110   {
1111     // Use EXPECT_EXIT to capture stderr and compare against expected output.
1112     //
1113     // Test VPValue::dump().
1114     VPValue *VPV = WidenR;
1115     EXPECT_EXIT(
1116         {
1117           VPV->dump();
1118           exit(0);
1119         },
1120         testing::ExitedWithCode(0), "WIDEN ir<%a> = add ir<1>, ir<2>");
1121 
1122     // Test VPRecipeBase::dump().
1123     VPRecipeBase *R = WidenR;
1124     EXPECT_EXIT(
1125         {
1126           R->dump();
1127           exit(0);
1128         },
1129         testing::ExitedWithCode(0), "WIDEN ir<%a> = add ir<1>, ir<2>");
1130 
1131     // Test VPDef::dump().
1132     VPDef *D = WidenR;
1133     EXPECT_EXIT(
1134         {
1135           D->dump();
1136           exit(0);
1137         },
1138         testing::ExitedWithCode(0), "WIDEN ir<%a> = add ir<1>, ir<2>");
1139   }
1140 
1141   delete AI;
1142 }
1143 #endif
1144 
1145 TEST(VPRecipeTest, CastVPReductionRecipeToVPUser) {
1146   LLVMContext C;
1147 
1148   VPValue ChainOp;
1149   VPValue VecOp;
1150   VPValue CondOp;
1151   VPReductionRecipe Recipe(nullptr, nullptr, &ChainOp, &CondOp, &VecOp,
1152                            nullptr);
1153   EXPECT_TRUE(isa<VPUser>(&Recipe));
1154   VPRecipeBase *BaseR = &Recipe;
1155   EXPECT_TRUE(isa<VPUser>(BaseR));
1156 }
1157 
1158 struct VPDoubleValueDef : public VPRecipeBase {
1159   VPDoubleValueDef(ArrayRef<VPValue *> Operands) : VPRecipeBase(99, Operands) {
1160     new VPValue(nullptr, this);
1161     new VPValue(nullptr, this);
1162   }
1163 
1164   void execute(struct VPTransformState &State) override{};
1165 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1166   void print(raw_ostream &O, const Twine &Indent,
1167              VPSlotTracker &SlotTracker) const override {}
1168 #endif
1169 };
1170 
1171 TEST(VPDoubleValueDefTest, traverseUseLists) {
1172   // Check that the def-use chains of a multi-def can be traversed in both
1173   // directions.
1174 
1175   // Create a new VPDef which defines 2 values and has 2 operands.
1176   VPInstruction Op0(20, {});
1177   VPInstruction Op1(30, {});
1178   VPDoubleValueDef DoubleValueDef({&Op0, &Op1});
1179 
1180   // Create a new users of the defined values.
1181   VPInstruction I1(
1182       1, {DoubleValueDef.getVPValue(0), DoubleValueDef.getVPValue(1)});
1183   VPInstruction I2(2, {DoubleValueDef.getVPValue(0)});
1184   VPInstruction I3(3, {DoubleValueDef.getVPValue(1)});
1185 
1186   // Check operands of the VPDef (traversing upwards).
1187   SmallVector<VPValue *, 4> DoubleOperands(DoubleValueDef.op_begin(),
1188                                            DoubleValueDef.op_end());
1189   EXPECT_EQ(2u, DoubleOperands.size());
1190   EXPECT_EQ(&Op0, DoubleOperands[0]);
1191   EXPECT_EQ(&Op1, DoubleOperands[1]);
1192 
1193   // Check users of the defined values (traversing downwards).
1194   SmallVector<VPUser *, 4> DoubleValueDefV0Users(
1195       DoubleValueDef.getVPValue(0)->user_begin(),
1196       DoubleValueDef.getVPValue(0)->user_end());
1197   EXPECT_EQ(2u, DoubleValueDefV0Users.size());
1198   EXPECT_EQ(&I1, DoubleValueDefV0Users[0]);
1199   EXPECT_EQ(&I2, DoubleValueDefV0Users[1]);
1200 
1201   SmallVector<VPUser *, 4> DoubleValueDefV1Users(
1202       DoubleValueDef.getVPValue(1)->user_begin(),
1203       DoubleValueDef.getVPValue(1)->user_end());
1204   EXPECT_EQ(2u, DoubleValueDefV1Users.size());
1205   EXPECT_EQ(&I1, DoubleValueDefV1Users[0]);
1206   EXPECT_EQ(&I3, DoubleValueDefV1Users[1]);
1207 
1208   // Now check that we can get the right VPDef for each defined value.
1209   EXPECT_EQ(&DoubleValueDef, I1.getOperand(0)->getDef());
1210   EXPECT_EQ(&DoubleValueDef, I1.getOperand(1)->getDef());
1211   EXPECT_EQ(&DoubleValueDef, I2.getOperand(0)->getDef());
1212   EXPECT_EQ(&DoubleValueDef, I3.getOperand(0)->getDef());
1213 }
1214 
1215 } // namespace
1216 } // namespace llvm
1217