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