1 //===- llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp -----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "../lib/Transforms/Vectorize/VPlanHCFGBuilder.h"
10 #include "VPlanTestBase.h"
11 #include "gtest/gtest.h"
12
13 namespace llvm {
14 namespace {
15
16 class VPlanDominatorTreeTest : public VPlanTestBase {};
17
TEST_F(VPlanDominatorTreeTest,BasicVPBBDomination)18 TEST_F(VPlanDominatorTreeTest, BasicVPBBDomination) {
19 const char *ModuleString =
20 "define void @f(i32* %a, i32* %b, i32* %c, i32 %N, i32 %M, i32 %K) {\n"
21 "entry:\n"
22 " br label %for.body\n"
23 "for.body:\n"
24 " %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.inc ]\n"
25 " br i1 true, label %if.then, label %if.else\n"
26 "if.then:\n"
27 " br label %for.inc\n"
28 "if.else:\n"
29 " br label %for.inc\n"
30 "for.inc:\n"
31 " %iv.next = add nuw nsw i64 %iv, 1\n"
32 " %exitcond = icmp eq i64 %iv.next, 300\n"
33 " br i1 %exitcond, label %for.end, label %for.body\n"
34 "for.end:\n"
35 " ret void\n"
36 "}\n";
37
38 Module &M = parseModule(ModuleString);
39
40 Function *F = M.getFunction("f");
41 BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
42 auto Plan = buildPlainCFG(LoopHeader);
43
44 // Build VPlan domination tree analysis.
45 VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
46 VPDominatorTree VPDT;
47 VPDT.recalculate(*TopRegion);
48
49 VPBlockBase *PH = TopRegion->getEntry();
50 VPBlockBase *H = PH->getSingleSuccessor();
51 VPBlockBase *IfThen = H->getSuccessors()[0];
52 VPBlockBase *IfElse = H->getSuccessors()[1];
53 VPBlockBase *Latch = IfThen->getSingleSuccessor();
54 VPBlockBase *Exit = Latch->getSuccessors()[0] != H
55 ? Latch->getSuccessors()[0]
56 : Latch->getSuccessors()[1];
57 // Reachability.
58 EXPECT_TRUE(VPDT.isReachableFromEntry(PH));
59 EXPECT_TRUE(VPDT.isReachableFromEntry(H));
60 EXPECT_TRUE(VPDT.isReachableFromEntry(IfThen));
61 EXPECT_TRUE(VPDT.isReachableFromEntry(IfElse));
62 EXPECT_TRUE(VPDT.isReachableFromEntry(Latch));
63 EXPECT_TRUE(VPDT.isReachableFromEntry(Exit));
64
65 // VPBB dominance.
66 EXPECT_TRUE(VPDT.dominates(PH, PH));
67 EXPECT_TRUE(VPDT.dominates(PH, H));
68 EXPECT_TRUE(VPDT.dominates(PH, IfThen));
69 EXPECT_TRUE(VPDT.dominates(PH, IfElse));
70 EXPECT_TRUE(VPDT.dominates(PH, Latch));
71 EXPECT_TRUE(VPDT.dominates(PH, Exit));
72
73 EXPECT_FALSE(VPDT.dominates(H, PH));
74 EXPECT_TRUE(VPDT.dominates(H, H));
75 EXPECT_TRUE(VPDT.dominates(H, IfThen));
76 EXPECT_TRUE(VPDT.dominates(H, IfElse));
77 EXPECT_TRUE(VPDT.dominates(H, Latch));
78 EXPECT_TRUE(VPDT.dominates(H, Exit));
79
80 EXPECT_FALSE(VPDT.dominates(IfThen, PH));
81 EXPECT_FALSE(VPDT.dominates(IfThen, H));
82 EXPECT_TRUE(VPDT.dominates(IfThen, IfThen));
83 EXPECT_FALSE(VPDT.dominates(IfThen, IfElse));
84 EXPECT_FALSE(VPDT.dominates(IfThen, Latch));
85 EXPECT_FALSE(VPDT.dominates(IfThen, Exit));
86
87 EXPECT_FALSE(VPDT.dominates(IfElse, PH));
88 EXPECT_FALSE(VPDT.dominates(IfElse, H));
89 EXPECT_FALSE(VPDT.dominates(IfElse, IfThen));
90 EXPECT_TRUE(VPDT.dominates(IfElse, IfElse));
91 EXPECT_FALSE(VPDT.dominates(IfElse, Latch));
92 EXPECT_FALSE(VPDT.dominates(IfElse, Exit));
93
94 EXPECT_FALSE(VPDT.dominates(Latch, PH));
95 EXPECT_FALSE(VPDT.dominates(Latch, H));
96 EXPECT_FALSE(VPDT.dominates(Latch, IfThen));
97 EXPECT_FALSE(VPDT.dominates(Latch, IfElse));
98 EXPECT_TRUE(VPDT.dominates(Latch, Latch));
99 EXPECT_TRUE(VPDT.dominates(Latch, Exit));
100
101 EXPECT_FALSE(VPDT.dominates(Exit, PH));
102 EXPECT_FALSE(VPDT.dominates(Exit, H));
103 EXPECT_FALSE(VPDT.dominates(Exit, IfThen));
104 EXPECT_FALSE(VPDT.dominates(Exit, IfElse));
105 EXPECT_FALSE(VPDT.dominates(Exit, Latch));
106 EXPECT_TRUE(VPDT.dominates(Exit, Exit));
107
108 // VPBB proper dominance.
109 EXPECT_FALSE(VPDT.properlyDominates(PH, PH));
110 EXPECT_TRUE(VPDT.properlyDominates(PH, H));
111 EXPECT_TRUE(VPDT.properlyDominates(PH, IfThen));
112 EXPECT_TRUE(VPDT.properlyDominates(PH, IfElse));
113 EXPECT_TRUE(VPDT.properlyDominates(PH, Latch));
114 EXPECT_TRUE(VPDT.properlyDominates(PH, Exit));
115
116 EXPECT_FALSE(VPDT.properlyDominates(H, PH));
117 EXPECT_FALSE(VPDT.properlyDominates(H, H));
118 EXPECT_TRUE(VPDT.properlyDominates(H, IfThen));
119 EXPECT_TRUE(VPDT.properlyDominates(H, IfElse));
120 EXPECT_TRUE(VPDT.properlyDominates(H, Latch));
121 EXPECT_TRUE(VPDT.properlyDominates(H, Exit));
122
123 EXPECT_FALSE(VPDT.properlyDominates(IfThen, PH));
124 EXPECT_FALSE(VPDT.properlyDominates(IfThen, H));
125 EXPECT_FALSE(VPDT.properlyDominates(IfThen, IfThen));
126 EXPECT_FALSE(VPDT.properlyDominates(IfThen, IfElse));
127 EXPECT_FALSE(VPDT.properlyDominates(IfThen, Latch));
128 EXPECT_FALSE(VPDT.properlyDominates(IfThen, Exit));
129
130 EXPECT_FALSE(VPDT.properlyDominates(IfElse, PH));
131 EXPECT_FALSE(VPDT.properlyDominates(IfElse, H));
132 EXPECT_FALSE(VPDT.properlyDominates(IfElse, IfThen));
133 EXPECT_FALSE(VPDT.properlyDominates(IfElse, IfElse));
134 EXPECT_FALSE(VPDT.properlyDominates(IfElse, Latch));
135 EXPECT_FALSE(VPDT.properlyDominates(IfElse, Exit));
136
137 EXPECT_FALSE(VPDT.properlyDominates(Latch, PH));
138 EXPECT_FALSE(VPDT.properlyDominates(Latch, H));
139 EXPECT_FALSE(VPDT.properlyDominates(Latch, IfThen));
140 EXPECT_FALSE(VPDT.properlyDominates(Latch, IfElse));
141 EXPECT_FALSE(VPDT.properlyDominates(Latch, Latch));
142 EXPECT_TRUE(VPDT.properlyDominates(Latch, Exit));
143
144 EXPECT_FALSE(VPDT.properlyDominates(Exit, PH));
145 EXPECT_FALSE(VPDT.properlyDominates(Exit, H));
146 EXPECT_FALSE(VPDT.properlyDominates(Exit, IfThen));
147 EXPECT_FALSE(VPDT.properlyDominates(Exit, IfElse));
148 EXPECT_FALSE(VPDT.properlyDominates(Exit, Latch));
149 EXPECT_FALSE(VPDT.properlyDominates(Exit, Exit));
150
151 // VPBB nearest common dominator.
152 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, PH));
153 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, H));
154 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, IfThen));
155 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, IfElse));
156 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, Latch));
157 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, Exit));
158
159 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(H, PH));
160 EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, H));
161 EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, IfThen));
162 EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, IfElse));
163 EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, Latch));
164 EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, Exit));
165
166 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(IfThen, PH));
167 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, H));
168 EXPECT_EQ(IfThen, VPDT.findNearestCommonDominator(IfThen, IfThen));
169 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, IfElse));
170 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, Latch));
171 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, Exit));
172
173 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(IfElse, PH));
174 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, H));
175 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, IfThen));
176 EXPECT_EQ(IfElse, VPDT.findNearestCommonDominator(IfElse, IfElse));
177 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, Latch));
178 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, Exit));
179
180 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(Latch, PH));
181 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, H));
182 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, IfThen));
183 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, IfElse));
184 EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Latch, Latch));
185 EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Latch, Exit));
186
187 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(Exit, PH));
188 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, H));
189 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, IfThen));
190 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, IfElse));
191 EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Exit, Latch));
192 EXPECT_EQ(Exit, VPDT.findNearestCommonDominator(Exit, Exit));
193 }
194 } // namespace
195 } // namespace llvm
196