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