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