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   VPlan Plan(VPPH, &*TC, VPBB0);
  45   VPDominatorTree VPDT;
  46   VPDT.recalculate(Plan);
  47
  48   EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB4));
  49   EXPECT_FALSE(VPDT.dominates(VPBB4, VPBB1));
  50
  51   EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB2));
  52   EXPECT_FALSE(VPDT.dominates(VPBB2, VPBB1));
  53
  54   EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB3));
  55   EXPECT_FALSE(VPDT.dominates(VPBB3, VPBB1));
  56
  57   EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB2, VPBB3), VPBB1);
  58   EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB2, VPBB4), VPBB1);
  59   EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB4, VPBB4), VPBB4);
  60 }
  61
  62 static void
  63 checkDomChildren(VPDominatorTree &VPDT, VPBlockBase *Src,
  64                  std::initializer_list<VPBlockBase *> ExpectedChildren) {
  65   SmallVector<VPDomTreeNode *> Children(VPDT.getNode(Src)->children());
  66   SmallVector<VPDomTreeNode *> ExpectedNodes;
  67   for (VPBlockBase *C : ExpectedChildren)
  68     ExpectedNodes.push_back(VPDT.getNode(C));
  69
  70   EXPECT_EQ(Children, ExpectedNodes);
  71 }
  72
  73 TEST(VPDominatorTreeTest, DominanceRegionsTest) {
  74   {
  75     // 2 consecutive regions.
  76     // VPBB0
  77     //  |
  78     // R1 {
  79     //     \
  80     //     R1BB1     _
  81     //    /     \   / \
  82     //  R1BB2   R1BB3  |
  83     //    \      /  \_/
  84     //     R1BB4
  85     //  }
  86     //   |
  87     // R2 {
  88     //   \
  89     //    R2BB1
  90     //      |
  91     //    R2BB2
  92     // }
  93     //
  94     VPBasicBlock *VPPH = new VPBasicBlock("ph");
  95     VPBasicBlock *VPBB0 = new VPBasicBlock("VPBB0");
  96     VPBasicBlock *R1BB1 = new VPBasicBlock();
  97     VPBasicBlock *R1BB2 = new VPBasicBlock();
  98     VPBasicBlock *R1BB3 = new VPBasicBlock();
  99     VPBasicBlock *R1BB4 = new VPBasicBlock();
 100     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB4, "R1");
 101     R1BB2->setParent(R1);
 102     R1BB3->setParent(R1);
 103     VPBlockUtils::connectBlocks(VPBB0, R1);
 104     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
 105     VPBlockUtils::connectBlocks(R1BB1, R1BB3);
 106     VPBlockUtils::connectBlocks(R1BB2, R1BB4);
 107     VPBlockUtils::connectBlocks(R1BB3, R1BB4);
 108     // Cycle.
 109     VPBlockUtils::connectBlocks(R1BB3, R1BB3);
 110
 111     VPBasicBlock *R2BB1 = new VPBasicBlock();
 112     VPBasicBlock *R2BB2 = new VPBasicBlock();
 113     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
 114     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
 115     VPBlockUtils::connectBlocks(R1, R2);
 116
 117     auto TC = std::make_unique<VPValue>();
 118     VPlan Plan(VPPH, &*TC, VPBB0);
 119     VPDominatorTree VPDT;
 120     VPDT.recalculate(Plan);
 121
 122     checkDomChildren(VPDT, R1, {R1BB1});
 123     checkDomChildren(VPDT, R1BB1, {R1BB2, R1BB4, R1BB3});
 124     checkDomChildren(VPDT, R1BB2, {});
 125     checkDomChildren(VPDT, R1BB3, {});
 126     checkDomChildren(VPDT, R1BB4, {R2});
 127     checkDomChildren(VPDT, R2, {R2BB1});
 128     checkDomChildren(VPDT, R2BB1, {R2BB2});
 129
 130     EXPECT_TRUE(VPDT.dominates(R1, R2));
 131     EXPECT_FALSE(VPDT.dominates(R2, R1));
 132
 133     EXPECT_TRUE(VPDT.dominates(R1BB1, R1BB4));
 134     EXPECT_FALSE(VPDT.dominates(R1BB4, R1BB1));
 135
 136     EXPECT_TRUE(VPDT.dominates(R2BB1, R2BB2));
 137     EXPECT_FALSE(VPDT.dominates(R2BB2, R2BB1));
 138
 139     EXPECT_TRUE(VPDT.dominates(R1BB1, R2BB1));
 140     EXPECT_FALSE(VPDT.dominates(R2BB1, R1BB1));
 141
 142     EXPECT_TRUE(VPDT.dominates(R1BB4, R2BB1));
 143     EXPECT_FALSE(VPDT.dominates(R1BB3, R2BB1));
 144
 145     EXPECT_TRUE(VPDT.dominates(R1, R2BB1));
 146     EXPECT_FALSE(VPDT.dominates(R2BB1, R1));
 147   }
 148
 149   {
 150     // 2 nested regions.
 151     //  VPBB1
 152     //    |
 153     //  R1 {
 154     //         R1BB1
 155     //       /        \
 156     //   R2 {          |
 157     //     \           |
 158     //     R2BB1       |
 159     //       |   \    R1BB2
 160     //     R2BB2-/     |
 161     //        \        |
 162     //         R2BB3   |
 163     //   }            /
 164     //      \        /
 165     //        R1BB3
 166     //  }
 167     //   |
 168     //  VPBB2
 169     //
 170     VPBasicBlock *VPPH = new VPBasicBlock("ph");
 171     VPBasicBlock *R1BB1 = new VPBasicBlock("R1BB1");
 172     VPBasicBlock *R1BB2 = new VPBasicBlock("R1BB2");
 173     VPBasicBlock *R1BB3 = new VPBasicBlock("R1BB3");
 174     VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB3, "R1");
 175
 176     VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
 177     VPBasicBlock *R2BB2 = new VPBasicBlock("R2BB2");
 178     VPBasicBlock *R2BB3 = new VPBasicBlock("R2BB3");
 179     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB3, "R2");
 180     R2BB2->setParent(R2);
 181     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
 182     VPBlockUtils::connectBlocks(R2BB2, R2BB1);
 183     VPBlockUtils::connectBlocks(R2BB2, R2BB3);
 184
 185     R2->setParent(R1);
 186     VPBlockUtils::connectBlocks(R1BB1, R2);
 187     R1BB2->setParent(R1);
 188     VPBlockUtils::connectBlocks(R1BB1, R1BB2);
 189     VPBlockUtils::connectBlocks(R1BB2, R1BB3);
 190     VPBlockUtils::connectBlocks(R2, R1BB3);
 191
 192     VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
 193     VPBlockUtils::connectBlocks(VPBB1, R1);
 194     VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
 195     VPBlockUtils::connectBlocks(R1, VPBB2);
 196
 197     auto TC = std::make_unique<VPValue>();
 198     VPlan Plan(VPPH, &*TC, VPBB1);
 199     VPDominatorTree VPDT;
 200     VPDT.recalculate(Plan);
 201
 202     checkDomChildren(VPDT, VPBB1, {R1});
 203     checkDomChildren(VPDT, R1, {R1BB1});
 204     checkDomChildren(VPDT, R1BB1, {R2, R1BB3, R1BB2});
 205     checkDomChildren(VPDT, R1BB2, {});
 206     checkDomChildren(VPDT, R2, {R2BB1});
 207     checkDomChildren(VPDT, R2BB1, {R2BB2});
 208     checkDomChildren(VPDT, R2BB2, {R2BB3});
 209     checkDomChildren(VPDT, R2BB3, {});
 210     checkDomChildren(VPDT, R1BB3, {VPBB2});
 211     checkDomChildren(VPDT, VPBB2, {});
 212   }
 213 }
 214
 215 } // namespace
 216 } // namespace llvm