1 | //===- LoopNestTest.cpp - LoopNestAnalysis unit tests ---------------------===// |
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 "llvm/Analysis/AssumptionCache.h" |
10 | #include "llvm/Analysis/LoopNestAnalysis.h" |
11 | #include "llvm/Analysis/ScalarEvolution.h" |
12 | #include "llvm/Analysis/TargetLibraryInfo.h" |
13 | #include "llvm/AsmParser/Parser.h" |
14 | #include "llvm/IR/Dominators.h" |
15 | #include "llvm/Support/SourceMgr.h" |
16 | #include "gtest/gtest.h" |
17 | |
18 | using namespace llvm; |
19 | |
20 | /// Build the loop nest analysis for a loop nest and run the given test \p Test. |
21 | static void runTest( |
22 | Module &M, StringRef FuncName, |
23 | function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) { |
24 | auto *F = M.getFunction(Name: FuncName); |
25 | ASSERT_NE(F, nullptr) << "Could not find " << FuncName; |
26 | |
27 | TargetLibraryInfoImpl TLII; |
28 | TargetLibraryInfo TLI(TLII); |
29 | AssumptionCache AC(*F); |
30 | DominatorTree DT(*F); |
31 | LoopInfo LI(DT); |
32 | ScalarEvolution SE(*F, TLI, AC, DT, LI); |
33 | |
34 | Test(*F, LI, SE); |
35 | } |
36 | |
37 | static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, |
38 | const char *ModuleStr) { |
39 | SMDiagnostic Err; |
40 | return parseAssemblyString(AsmString: ModuleStr, Err, Context); |
41 | } |
42 | |
43 | static Instruction *getInstructionByName(Function &F, StringRef Name) { |
44 | for (BasicBlock &BB : F) |
45 | for (Instruction &I : BB) |
46 | if (I.getName() == Name) |
47 | return &I; |
48 | llvm_unreachable("Expected to find instruction!" ); |
49 | } |
50 | |
51 | TEST(LoopNestTest, PerfectLoopNest) { |
52 | const char *ModuleStr = |
53 | "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" |
54 | "define void @foo(i64 signext %nx, i64 signext %ny) {\n" |
55 | "entry:\n" |
56 | " br label %for.outer\n" |
57 | "for.outer:\n" |
58 | " %i = phi i64 [ 0, %entry ], [ %inc13, %for.outer.latch ]\n" |
59 | " %cmp21 = icmp slt i64 0, %ny\n" |
60 | " br i1 %cmp21, label %for.inner.preheader, label %for.outer.latch\n" |
61 | "for.inner.preheader:\n" |
62 | " br label %for.inner\n" |
63 | "for.inner:\n" |
64 | " %j = phi i64 [ 0, %for.inner.preheader ], [ %inc, %for.inner.latch ]\n" |
65 | " br label %for.inner.latch\n" |
66 | "for.inner.latch:\n" |
67 | " %inc = add nsw i64 %j, 1\n" |
68 | " %cmp2 = icmp slt i64 %inc, %ny\n" |
69 | " br i1 %cmp2, label %for.inner, label %for.inner.exit\n" |
70 | "for.inner.exit:\n" |
71 | " br label %for.outer.latch\n" |
72 | "for.outer.latch:\n" |
73 | " %inc13 = add nsw i64 %i, 1\n" |
74 | " %cmp = icmp slt i64 %inc13, %nx\n" |
75 | " br i1 %cmp, label %for.outer, label %for.outer.exit\n" |
76 | "for.outer.exit:\n" |
77 | " br label %for.end\n" |
78 | "for.end:\n" |
79 | " ret void\n" |
80 | "}\n" ; |
81 | |
82 | LLVMContext Context; |
83 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); |
84 | |
85 | runTest(M&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
86 | Function::iterator FI = F.begin(); |
87 | // Skip the first basic block (entry), get to the outer loop header. |
88 | BasicBlock * = &*(++FI); |
89 | assert(Header->getName() == "for.outer" ); |
90 | Loop *L = LI.getLoopFor(BB: Header); |
91 | EXPECT_NE(L, nullptr); |
92 | |
93 | LoopNest LN(*L, SE); |
94 | EXPECT_TRUE(LN.areAllLoopsSimplifyForm()); |
95 | |
96 | // Ensure that we can identify the outermost loop in the nest. |
97 | const Loop &OL = LN.getOutermostLoop(); |
98 | EXPECT_EQ(OL.getName(), "for.outer" ); |
99 | |
100 | // Ensure that we can identify the innermost loop in the nest. |
101 | const Loop *IL = LN.getInnermostLoop(); |
102 | EXPECT_NE(IL, nullptr); |
103 | EXPECT_EQ(IL->getName(), "for.inner" ); |
104 | |
105 | // Ensure the loop nest is recognized as having 2 loops. |
106 | const ArrayRef<Loop*> Loops = LN.getLoops(); |
107 | EXPECT_EQ(Loops.size(), 2ull); |
108 | |
109 | // Ensure that we can obtain loops by depth. |
110 | LoopVectorTy LoopsAtDepth1 = LN.getLoopsAtDepth(Depth: 1); |
111 | EXPECT_EQ(LoopsAtDepth1.size(), 1u); |
112 | EXPECT_EQ(LoopsAtDepth1[0], &OL); |
113 | LoopVectorTy LoopsAtDepth2 = LN.getLoopsAtDepth(Depth: 2); |
114 | EXPECT_EQ(LoopsAtDepth2.size(), 1u); |
115 | EXPECT_EQ(LoopsAtDepth2[0], IL); |
116 | |
117 | // Ensure that we can obtain the loop index of a given loop, and get back |
118 | // the loop with that index. |
119 | EXPECT_EQ(LN.getLoop(LN.getLoopIndex(OL)), &OL); |
120 | EXPECT_EQ(LN.getLoop(LN.getLoopIndex(*IL)), IL); |
121 | |
122 | // Ensure the loop nest is recognized as perfect in its entirety. |
123 | const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE); |
124 | EXPECT_EQ(PLV.size(), 1ull); |
125 | EXPECT_EQ(PLV.front().size(), 2ull); |
126 | |
127 | // Ensure the nest depth and perfect nest depth are computed correctly. |
128 | EXPECT_EQ(LN.getNestDepth(), 2u); |
129 | EXPECT_EQ(LN.getMaxPerfectDepth(), 2u); |
130 | |
131 | EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty()); |
132 | }); |
133 | } |
134 | |
135 | TEST(LoopNestTest, ImperfectLoopNest) { |
136 | const char *ModuleStr = |
137 | "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" |
138 | "define void @foo(i32 signext %nx, i32 signext %ny, i32 signext %nk) {\n" |
139 | "entry:\n" |
140 | " br label %loop.i\n" |
141 | "loop.i:\n" |
142 | " %i = phi i32 [ 0, %entry ], [ %inci, %for.inci ]\n" |
143 | " %cmp21 = icmp slt i32 0, %ny\n" |
144 | " br i1 %cmp21, label %loop.j.preheader, label %for.inci\n" |
145 | "loop.j.preheader:\n" |
146 | " br label %loop.j\n" |
147 | "loop.j:\n" |
148 | " %j = phi i32 [ %incj, %for.incj ], [ 0, %loop.j.preheader ]\n" |
149 | " %cmp22 = icmp slt i32 0, %nk\n" |
150 | " br i1 %cmp22, label %loop.k.preheader, label %for.incj\n" |
151 | "loop.k.preheader:\n" |
152 | " call void @bar()\n" |
153 | " br label %loop.k\n" |
154 | "loop.k:\n" |
155 | " %k = phi i32 [ %inck, %for.inck ], [ 0, %loop.k.preheader ]\n" |
156 | " br label %for.inck\n" |
157 | "for.inck:\n" |
158 | " %inck = add nsw i32 %k, 1\n" |
159 | " %cmp5 = icmp slt i32 %inck, %nk\n" |
160 | " br i1 %cmp5, label %loop.k, label %for.incj.loopexit\n" |
161 | "for.incj.loopexit:\n" |
162 | " br label %for.incj\n" |
163 | "for.incj:\n" |
164 | " %incj = add nsw i32 %j, 1\n" |
165 | " %cmp2 = icmp slt i32 %incj, %ny\n" |
166 | " br i1 %cmp2, label %loop.j, label %for.inci.loopexit\n" |
167 | "for.inci.loopexit:\n" |
168 | " br label %for.inci\n" |
169 | "for.inci:\n" |
170 | " %inci = add nsw i32 %i, 1\n" |
171 | " %cmp = icmp slt i32 %inci, %nx\n" |
172 | " br i1 %cmp, label %loop.i, label %loop.i.end\n" |
173 | "loop.i.end:\n" |
174 | " ret void\n" |
175 | "}\n" |
176 | "declare void @bar()\n" ; |
177 | |
178 | LLVMContext Context; |
179 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); |
180 | |
181 | runTest(M&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
182 | Function::iterator FI = F.begin(); |
183 | // Skip the first basic block (entry), get to the outermost loop header. |
184 | BasicBlock * = &*(++FI); |
185 | assert(Header->getName() == "loop.i" ); |
186 | Loop *L = LI.getLoopFor(BB: Header); |
187 | EXPECT_NE(L, nullptr); |
188 | |
189 | LoopNest LN(*L, SE); |
190 | EXPECT_TRUE(LN.areAllLoopsSimplifyForm()); |
191 | |
192 | dbgs() << "LN: " << LN << "\n" ; |
193 | |
194 | // Ensure that we can identify the outermost loop in the nest. |
195 | const Loop &OL = LN.getOutermostLoop(); |
196 | EXPECT_EQ(OL.getName(), "loop.i" ); |
197 | |
198 | // Ensure that we can identify the innermost loop in the nest. |
199 | const Loop *IL = LN.getInnermostLoop(); |
200 | EXPECT_NE(IL, nullptr); |
201 | EXPECT_EQ(IL->getName(), "loop.k" ); |
202 | |
203 | // Ensure the loop nest is recognized as having 3 loops. |
204 | const ArrayRef<Loop*> Loops = LN.getLoops(); |
205 | EXPECT_EQ(Loops.size(), 3ull); |
206 | |
207 | // Ensure the loop nest is recognized as having 2 separate perfect loops groups. |
208 | const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE); |
209 | EXPECT_EQ(PLV.size(), 2ull); |
210 | EXPECT_EQ(PLV.front().size(), 2ull); |
211 | EXPECT_EQ(PLV.back().size(), 1ull); |
212 | |
213 | // Ensure the nest depth and perfect nest depth are computed correctly. |
214 | EXPECT_EQ(LN.getNestDepth(), 3u); |
215 | EXPECT_EQ(LN.getMaxPerfectDepth(), 2u); |
216 | |
217 | EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty()); |
218 | }); |
219 | } |
220 | |
221 | TEST(LoopNestTest, InterveningInstrLoopNest) { |
222 | const char *ModuleStr = |
223 | "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" |
224 | "define void @foo(i64 signext %nx, i64 signext %ny, i32* noalias %A, i32 " |
225 | "%op0, i32 %op1){\n" |
226 | "entry:\n" |
227 | " br label %for.outer\n" |
228 | "for.outer:\n" |
229 | " %i = phi i64 [ 0, %entry ], [ %inc13, %for.outer.latch ]\n" |
230 | " %cmp21 = icmp slt i64 0, %ny\n" |
231 | " call void @outerheader()\n" |
232 | " br i1 %cmp21, label %for.inner.preheader, label %for.outer.latch\n" |
233 | "for.inner.preheader:\n" |
234 | " %varr = getelementptr inbounds i32, i32* %A, i64 5\n" |
235 | " store i32 5, i32* %varr, align 4\n" |
236 | " call void @innerpreheader()\n" |
237 | " br label %for.inner\n" |
238 | "for.inner:\n" |
239 | " %j = phi i64 [ 0, %for.inner.preheader ], [ %inc, %for.inner.latch ]\n" |
240 | " br label %for.inner.latch\n" |
241 | "for.inner.latch:\n" |
242 | " %inc = add nsw i64 %j, 1\n" |
243 | " %cmp2 = icmp slt i64 %inc, %ny\n" |
244 | " br i1 %cmp2, label %for.inner, label %for.inner.exit\n" |
245 | "for.inner.exit:\n" |
246 | " %varr1 = getelementptr inbounds i32, i32* %A, i64 5\n" |
247 | " call void @innerexit()\n" |
248 | " br label %for.outer.latch\n" |
249 | "for.outer.latch:\n" |
250 | " %inc13 = add nsw i64 %i, 1\n" |
251 | " call void @outerlatch()\n" |
252 | " %cmp = icmp slt i64 %inc13, %nx\n" |
253 | " br i1 %cmp, label %for.outer, label %for.outer.exit\n" |
254 | "for.outer.exit:\n" |
255 | " br label %for.end\n" |
256 | "for.end:\n" |
257 | " ret void\n" |
258 | "}\n" |
259 | "declare void @innerpreheader()\n" |
260 | "declare void @outerheader()\n" |
261 | "declare void @outerlatch()\n" |
262 | "declare void @innerexit()\n" ; |
263 | |
264 | LLVMContext Context; |
265 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); |
266 | |
267 | runTest(M&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
268 | Function::iterator FI = F.begin(); |
269 | // Skip the first basic block (entry), get to the outer loop header. |
270 | BasicBlock * = &*(++FI); |
271 | assert(Header->getName() == "for.outer" ); |
272 | Loop *L = LI.getLoopFor(BB: Header); |
273 | EXPECT_NE(L, nullptr); |
274 | |
275 | LoopNest LN(*L, SE); |
276 | EXPECT_TRUE(LN.areAllLoopsSimplifyForm()); |
277 | |
278 | // Ensure that we can identify the outermost loop in the nest. |
279 | const Loop &OL = LN.getOutermostLoop(); |
280 | EXPECT_EQ(OL.getName(), "for.outer" ); |
281 | |
282 | // Ensure that we can identify the innermost loop in the nest. |
283 | const Loop *IL = LN.getInnermostLoop(); |
284 | EXPECT_NE(IL, nullptr); |
285 | EXPECT_EQ(IL->getName(), "for.inner" ); |
286 | |
287 | // Ensure the loop nest is recognized as having 2 loops. |
288 | const ArrayRef<Loop *> Loops = LN.getLoops(); |
289 | EXPECT_EQ(Loops.size(), 2ull); |
290 | |
291 | // Ensure the loop nest is not recognized as perfect in its entirety. |
292 | const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE); |
293 | EXPECT_EQ(PLV.size(), 2ull); |
294 | EXPECT_EQ(PLV.front().size(), 1ull); |
295 | EXPECT_EQ(PLV.back().size(), 1ull); |
296 | |
297 | // Ensure the nest depth and perfect nest depth are computed correctly. |
298 | EXPECT_EQ(LN.getNestDepth(), 2u); |
299 | EXPECT_EQ(LN.getMaxPerfectDepth(), 1u); |
300 | |
301 | // Ensure enclosed instructions are recognized |
302 | const LoopNest::InstrVectorTy InstrV = |
303 | LN.getInterveningInstructions(OuterLoop: OL, InnerLoop: *IL, SE); |
304 | EXPECT_EQ(InstrV.size(), 5u); |
305 | |
306 | Instruction *SI = getInstructionByName(F, Name: "varr" )->getNextNode(); |
307 | Instruction *CI = SI->getNextNode(); |
308 | Instruction *OLH = |
309 | getInstructionByName(F, Name: "i" )->getNextNode()->getNextNode(); |
310 | Instruction *OLL = getInstructionByName(F, Name: "inc13" )->getNextNode(); |
311 | Instruction *IE = getInstructionByName(F, Name: "varr1" )->getNextNode(); |
312 | |
313 | EXPECT_EQ(InstrV.front(), OLH); |
314 | EXPECT_EQ(InstrV[1], OLL); |
315 | EXPECT_EQ(InstrV[2], IE); |
316 | EXPECT_EQ(InstrV[3], SI); |
317 | EXPECT_EQ(InstrV.back(), CI); |
318 | }); |
319 | } |
320 | |