llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

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