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