llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

   1 //===- llvm/unittests/Transforms/Vectorize/VPDomTreeTests.cpp - -----------===//
   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/VPlanDominatorTree.h"
  12 #include "gtest/gtest.h"
  13
  14 namespace llvm {
  15 namespace {
  16
  17 TEST(VPDominatorTreeTest, DominanceNoRegionsTest) {
  18   //   VPBB0
  19   //    |
  20   //   R1 {
  21   //     VPBB1
  22   //     /   \
  23     // VPBB2  VPBB3
  24   //    \    /
  25   //    VPBB4
  26   //  }
  27   VPBasicBlock *VPPH = new VPBasicBlock("ph");
  28   VPBasicBlock *VPBB0 = new VPBasicBlock("VPBB0");
  29   VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
  30   VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
  31   VPBasicBlock *VPBB3 = new VPBasicBlock("VPBB3");
  32   VPBasicBlock *VPBB4 = new VPBasicBlock("VPBB4");
  33   VPRegionBlock *R1 = new VPRegionBlock(VPBB1, VPBB4);
  34   VPBB2->setParent(R1);
  35   VPBB3->setParent(R1);
  36
  37   VPBlockUtils::connectBlocks(VPBB0, R1);
  38   VPBlockUtils::connectBlocks(VPBB1, VPBB2);
  39   VPBlockUtils::connectBlocks(VPBB1, VPBB3);
  40   VPBlockUtils::connectBlocks(VPBB2, VPBB4);
  41   VPBlockUtils::connectBlocks(VPBB3, VPBB4);
  42
  43   auto TC = std::make_unique<VPValue>();
  44   LLVMContext C;
  45   auto *ScalarHeader = BasicBlock::Create(C, "");
  46   VPIRBasicBlock *ScalarHeaderVPBB = new VPIRBasicBlock(ScalarHeader);
  47   VPBlockUtils::connectBlocks(R1, ScalarHeaderVPBB);
  48   VPlan Plan(VPPH, &*TC, VPBB0, ScalarHeaderVPBB);
  49
  50   VPDominatorTree VPDT;
  51   VPDT.recalculate(Plan);
  52
  53   EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB4));
  54   EXPECT_FALSE(VPDT.dominates(VPBB4, VPBB1));
  55
  56   EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB2));
  57   EXPECT_FALSE(VPDT.dominates(VPBB2, VPBB1));
  58
  59   EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB3));
  60   EXPECT_FALSE(VPDT.dominates(VPBB3, VPBB1));
  61
  62   EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB2, VPBB3), VPBB1);
  63   EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB2, VPBB4), VPBB1);
  64   EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB4, VPBB4), VPBB4);
  65   delete ScalarHeader;
  66 }
  67
  68 static void
  69 checkDomChildren(VPDominatorTree &VPDT, VPBlockBase *Src,
  70                  std::initializer_list<VPBlockBase *> ExpectedChildren) {
  71   SmallVector<VPDomTreeNode *> Children(VPDT.getNode(Src)->children());
  72   SmallVector<VPDomTreeNode *> ExpectedNodes;
  73   for (VPBlockBase *C : ExpectedChildren)
  74     ExpectedNodes.push_back(VPDT.getNode(C));
  75
  76   EXPECT_EQ(Children, ExpectedNodes);
  77 }
  78
  79 TEST(VPDominatorTreeTest, DominanceRegionsTest) {
  80   LLVMContext C;
  81   auto *ScalarHeader = BasicBlock::Create(C, "");
  82   {
  83     // 2 consecutive regions.
  84     // VPBB0
  85     //  |
  86     // R1 {
  87     //     \
  88     //     R1BB1     _
  89     //    /     \   / \
  90     //  R1BB2   R1BB3  |
  91     //    \      /  \_/
  92     //     R1BB4
  93     //  }
  94     //   |
  95     // R2 {
  96     //   \
  97     //    R2BB1
  98     //      |
  99     //    R2BB2
 100     // }
 101     //
 102     VPBasicBlock *VPPH = new VPBasicBlock("ph");
 103     VPBasicBlock *VPBB0 = new VPBasicBlock("VPBB0");
 104     VPBasicBlock *R1BB1 = new VPBasicBlock();
 105     VPBasicBlock *R1BB2 = new VPBasicBlock();
 106     VPBasicBlock *R1BB3 = new VPBasicBlock();
 107     VPBasicBlock *R1BB4 = new VPBasicBlock();
 108     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB4, "R1");
 109     R1BB2->setParent(R1);
 110     R1BB3->setParent(R1);
 111     VPBlockUtils::connectBlocks(VPBB0, R1);
 112     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
 113     VPBlockUtils::connectBlocks(R1BB1, R1BB3);
 114     VPBlockUtils::connectBlocks(R1BB2, R1BB4);
 115     VPBlockUtils::connectBlocks(R1BB3, R1BB4);
 116     // Cycle.
 117     VPBlockUtils::connectBlocks(R1BB3, R1BB3);
 118
 119     VPBasicBlock *R2BB1 = new VPBasicBlock();
 120     VPBasicBlock *R2BB2 = new VPBasicBlock();
 121     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
 122     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
 123     VPBlockUtils::connectBlocks(R1, R2);
 124
 125     auto TC = std::make_unique<VPValue>();
 126     VPIRBasicBlock *ScalarHeaderVPBB = new VPIRBasicBlock(ScalarHeader);
 127     VPBlockUtils::connectBlocks(R2, ScalarHeaderVPBB);
 128     VPlan Plan(VPPH, &*TC, VPBB0, ScalarHeaderVPBB);
 129     VPDominatorTree VPDT;
 130     VPDT.recalculate(Plan);
 131
 132     checkDomChildren(VPDT, R1, {R1BB1});
 133     checkDomChildren(VPDT, R1BB1, {R1BB2, R1BB4, R1BB3});
 134     checkDomChildren(VPDT, R1BB2, {});
 135     checkDomChildren(VPDT, R1BB3, {});
 136     checkDomChildren(VPDT, R1BB4, {R2});
 137     checkDomChildren(VPDT, R2, {R2BB1});
 138     checkDomChildren(VPDT, R2BB1, {R2BB2});
 139
 140     EXPECT_TRUE(VPDT.dominates(R1, R2));
 141     EXPECT_FALSE(VPDT.dominates(R2, R1));
 142
 143     EXPECT_TRUE(VPDT.dominates(R1BB1, R1BB4));
 144     EXPECT_FALSE(VPDT.dominates(R1BB4, R1BB1));
 145
 146     EXPECT_TRUE(VPDT.dominates(R2BB1, R2BB2));
 147     EXPECT_FALSE(VPDT.dominates(R2BB2, R2BB1));
 148
 149     EXPECT_TRUE(VPDT.dominates(R1BB1, R2BB1));
 150     EXPECT_FALSE(VPDT.dominates(R2BB1, R1BB1));
 151
 152     EXPECT_TRUE(VPDT.dominates(R1BB4, R2BB1));
 153     EXPECT_FALSE(VPDT.dominates(R1BB3, R2BB1));
 154
 155     EXPECT_TRUE(VPDT.dominates(R1, R2BB1));
 156     EXPECT_FALSE(VPDT.dominates(R2BB1, R1));
 157   }
 158
 159   {
 160     // 2 nested regions.
 161     //  VPBB1
 162     //    |
 163     //  R1 {
 164     //         R1BB1
 165     //       /        \
 166     //   R2 {          |
 167     //     \           |
 168     //     R2BB1       |
 169     //       |   \    R1BB2
 170     //     R2BB2-/     |
 171     //        \        |
 172     //         R2BB3   |
 173     //   }            /
 174     //      \        /
 175     //        R1BB3
 176     //  }
 177     //   |
 178     //  VPBB2
 179     //
 180     VPBasicBlock *VPPH = new VPBasicBlock("ph");
 181     VPBasicBlock *R1BB1 = new VPBasicBlock("R1BB1");
 182     VPBasicBlock *R1BB2 = new VPBasicBlock("R1BB2");
 183     VPBasicBlock *R1BB3 = new VPBasicBlock("R1BB3");
 184     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB3, "R1");
 185
 186     VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
 187     VPBasicBlock *R2BB2 = new VPBasicBlock("R2BB2");
 188     VPBasicBlock *R2BB3 = new VPBasicBlock("R2BB3");
 189     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB3, "R2");
 190     R2BB2->setParent(R2);
 191     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
 192     VPBlockUtils::connectBlocks(R2BB2, R2BB1);
 193     VPBlockUtils::connectBlocks(R2BB2, R2BB3);
 194
 195     R2->setParent(R1);
 196     VPBlockUtils::connectBlocks(R1BB1, R2);
 197     R1BB2->setParent(R1);
 198     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
 199     VPBlockUtils::connectBlocks(R1BB2, R1BB3);
 200     VPBlockUtils::connectBlocks(R2, R1BB3);
 201
 202     VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
 203     VPBlockUtils::connectBlocks(VPBB1, R1);
 204     VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
 205     VPBlockUtils::connectBlocks(R1, VPBB2);
 206
 207     auto TC = std::make_unique<VPValue>();
 208     VPIRBasicBlock *ScalarHeaderVPBB = new VPIRBasicBlock(ScalarHeader);
 209     VPBlockUtils::connectBlocks(VPBB2, ScalarHeaderVPBB);
 210     VPlan Plan(VPPH, &*TC, VPBB1, ScalarHeaderVPBB);
 211     VPDominatorTree VPDT;
 212     VPDT.recalculate(Plan);
 213
 214     checkDomChildren(VPDT, VPBB1, {R1});
 215     checkDomChildren(VPDT, R1, {R1BB1});
 216     checkDomChildren(VPDT, R1BB1, {R2, R1BB3, R1BB2});
 217     checkDomChildren(VPDT, R1BB2, {});
 218     checkDomChildren(VPDT, R2, {R2BB1});
 219     checkDomChildren(VPDT, R2BB1, {R2BB2});
 220     checkDomChildren(VPDT, R2BB2, {R2BB3});
 221     checkDomChildren(VPDT, R2BB3, {});
 222     checkDomChildren(VPDT, R1BB3, {VPBB2});
 223     checkDomChildren(VPDT, VPBB2, {ScalarHeaderVPBB});
 224   }
 225   delete ScalarHeader;
 226 }
 227
 228 } // namespace
 229 } // namespace llvm