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
18using namespace llvm;
19
20/// Build the loop nest analysis for a loop nest and run the given test \p Test.
21static 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
37static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
38 const char *ModuleStr) {
39 SMDiagnostic Err;
40 return parseAssemblyString(AsmString: ModuleStr, Err, Context);
41}
42
43static 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
51TEST(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 *Header = &*(++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
135TEST(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 *Header = &*(++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
221TEST(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 *Header = &*(++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

source code of llvm/unittests/Analysis/LoopNestTest.cpp