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