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