Debian Codegraph @

llvm-project/llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

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