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.
runTest(Module & M,StringRef FuncName,function_ref<void (Function & F,LoopInfo & LI,ScalarEvolution & SE)> 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(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
makeLLVMModule(LLVMContext & Context,const char * ModuleStr)37 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
38 const char *ModuleStr) {
39 SMDiagnostic Err;
40 return parseAssemblyString(ModuleStr, Err, Context);
41 }
42
getInstructionByName(Function & F,StringRef Name)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
TEST(LoopNestTest,PerfectLoopNest)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, "foo", [&](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(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 the loop nest is recognized as perfect in its entirety.
110 const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE);
111 EXPECT_EQ(PLV.size(), 1ull);
112 EXPECT_EQ(PLV.front().size(), 2ull);
113
114 // Ensure the nest depth and perfect nest depth are computed correctly.
115 EXPECT_EQ(LN.getNestDepth(), 2u);
116 EXPECT_EQ(LN.getMaxPerfectDepth(), 2u);
117
118 EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty());
119 });
120 }
121
TEST(LoopNestTest,ImperfectLoopNest)122 TEST(LoopNestTest, ImperfectLoopNest) {
123 const char *ModuleStr =
124 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
125 "define void @foo(i32 signext %nx, i32 signext %ny, i32 signext %nk) {\n"
126 "entry:\n"
127 " br label %loop.i\n"
128 "loop.i:\n"
129 " %i = phi i32 [ 0, %entry ], [ %inci, %for.inci ]\n"
130 " %cmp21 = icmp slt i32 0, %ny\n"
131 " br i1 %cmp21, label %loop.j.preheader, label %for.inci\n"
132 "loop.j.preheader:\n"
133 " br label %loop.j\n"
134 "loop.j:\n"
135 " %j = phi i32 [ %incj, %for.incj ], [ 0, %loop.j.preheader ]\n"
136 " %cmp22 = icmp slt i32 0, %nk\n"
137 " br i1 %cmp22, label %loop.k.preheader, label %for.incj\n"
138 "loop.k.preheader:\n"
139 " call void @bar()\n"
140 " br label %loop.k\n"
141 "loop.k:\n"
142 " %k = phi i32 [ %inck, %for.inck ], [ 0, %loop.k.preheader ]\n"
143 " br label %for.inck\n"
144 "for.inck:\n"
145 " %inck = add nsw i32 %k, 1\n"
146 " %cmp5 = icmp slt i32 %inck, %nk\n"
147 " br i1 %cmp5, label %loop.k, label %for.incj.loopexit\n"
148 "for.incj.loopexit:\n"
149 " br label %for.incj\n"
150 "for.incj:\n"
151 " %incj = add nsw i32 %j, 1\n"
152 " %cmp2 = icmp slt i32 %incj, %ny\n"
153 " br i1 %cmp2, label %loop.j, label %for.inci.loopexit\n"
154 "for.inci.loopexit:\n"
155 " br label %for.inci\n"
156 "for.inci:\n"
157 " %inci = add nsw i32 %i, 1\n"
158 " %cmp = icmp slt i32 %inci, %nx\n"
159 " br i1 %cmp, label %loop.i, label %loop.i.end\n"
160 "loop.i.end:\n"
161 " ret void\n"
162 "}\n"
163 "declare void @bar()\n";
164
165 LLVMContext Context;
166 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
167
168 runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
169 Function::iterator FI = F.begin();
170 // Skip the first basic block (entry), get to the outermost loop header.
171 BasicBlock *Header = &*(++FI);
172 assert(Header->getName() == "loop.i");
173 Loop *L = LI.getLoopFor(Header);
174 EXPECT_NE(L, nullptr);
175
176 LoopNest LN(*L, SE);
177 EXPECT_TRUE(LN.areAllLoopsSimplifyForm());
178
179 dbgs() << "LN: " << LN << "\n";
180
181 // Ensure that we can identify the outermost loop in the nest.
182 const Loop &OL = LN.getOutermostLoop();
183 EXPECT_EQ(OL.getName(), "loop.i");
184
185 // Ensure that we can identify the innermost loop in the nest.
186 const Loop *IL = LN.getInnermostLoop();
187 EXPECT_NE(IL, nullptr);
188 EXPECT_EQ(IL->getName(), "loop.k");
189
190 // Ensure the loop nest is recognized as having 3 loops.
191 const ArrayRef<Loop*> Loops = LN.getLoops();
192 EXPECT_EQ(Loops.size(), 3ull);
193
194 // Ensure the loop nest is recognized as having 2 separate perfect loops groups.
195 const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE);
196 EXPECT_EQ(PLV.size(), 2ull);
197 EXPECT_EQ(PLV.front().size(), 2ull);
198 EXPECT_EQ(PLV.back().size(), 1ull);
199
200 // Ensure the nest depth and perfect nest depth are computed correctly.
201 EXPECT_EQ(LN.getNestDepth(), 3u);
202 EXPECT_EQ(LN.getMaxPerfectDepth(), 2u);
203
204 EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty());
205 });
206 }
207
TEST(LoopNestTest,InterveningInstrLoopNest)208 TEST(LoopNestTest, InterveningInstrLoopNest) {
209 const char *ModuleStr =
210 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
211 "define void @foo(i64 signext %nx, i64 signext %ny, i32* noalias %A, i32 "
212 "%op0, i32 %op1){\n"
213 "entry:\n"
214 " br label %for.outer\n"
215 "for.outer:\n"
216 " %i = phi i64 [ 0, %entry ], [ %inc13, %for.outer.latch ]\n"
217 " %cmp21 = icmp slt i64 0, %ny\n"
218 " call void @outerheader()\n"
219 " br i1 %cmp21, label %for.inner.preheader, label %for.outer.latch\n"
220 "for.inner.preheader:\n"
221 " %varr = getelementptr inbounds i32, i32* %A, i64 5\n"
222 " store i32 5, i32* %varr, align 4\n"
223 " call void @innerpreheader()\n"
224 " br label %for.inner\n"
225 "for.inner:\n"
226 " %j = phi i64 [ 0, %for.inner.preheader ], [ %inc, %for.inner.latch ]\n"
227 " br label %for.inner.latch\n"
228 "for.inner.latch:\n"
229 " %inc = add nsw i64 %j, 1\n"
230 " %cmp2 = icmp slt i64 %inc, %ny\n"
231 " br i1 %cmp2, label %for.inner, label %for.inner.exit\n"
232 "for.inner.exit:\n"
233 " %varr1 = getelementptr inbounds i32, i32* %A, i64 5\n"
234 " call void @innerexit()\n"
235 " br label %for.outer.latch\n"
236 "for.outer.latch:\n"
237 " %inc13 = add nsw i64 %i, 1\n"
238 " call void @outerlatch()\n"
239 " %cmp = icmp slt i64 %inc13, %nx\n"
240 " br i1 %cmp, label %for.outer, label %for.outer.exit\n"
241 "for.outer.exit:\n"
242 " br label %for.end\n"
243 "for.end:\n"
244 " ret void\n"
245 "}\n"
246 "declare void @innerpreheader()\n"
247 "declare void @outerheader()\n"
248 "declare void @outerlatch()\n"
249 "declare void @innerexit()\n";
250
251 LLVMContext Context;
252 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
253
254 runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
255 Function::iterator FI = F.begin();
256 // Skip the first basic block (entry), get to the outer loop header.
257 BasicBlock *Header = &*(++FI);
258 assert(Header->getName() == "for.outer");
259 Loop *L = LI.getLoopFor(Header);
260 EXPECT_NE(L, nullptr);
261
262 LoopNest LN(*L, SE);
263 EXPECT_TRUE(LN.areAllLoopsSimplifyForm());
264
265 // Ensure that we can identify the outermost loop in the nest.
266 const Loop &OL = LN.getOutermostLoop();
267 EXPECT_EQ(OL.getName(), "for.outer");
268
269 // Ensure that we can identify the innermost loop in the nest.
270 const Loop *IL = LN.getInnermostLoop();
271 EXPECT_NE(IL, nullptr);
272 EXPECT_EQ(IL->getName(), "for.inner");
273
274 // Ensure the loop nest is recognized as having 2 loops.
275 const ArrayRef<Loop *> Loops = LN.getLoops();
276 EXPECT_EQ(Loops.size(), 2ull);
277
278 // Ensure the loop nest is not recognized as perfect in its entirety.
279 const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE);
280 EXPECT_EQ(PLV.size(), 2ull);
281 EXPECT_EQ(PLV.front().size(), 1ull);
282 EXPECT_EQ(PLV.back().size(), 1ull);
283
284 // Ensure the nest depth and perfect nest depth are computed correctly.
285 EXPECT_EQ(LN.getNestDepth(), 2u);
286 EXPECT_EQ(LN.getMaxPerfectDepth(), 1u);
287
288 // Ensure enclosed instructions are recognized
289 const LoopNest::InstrVectorTy InstrV =
290 LN.getInterveningInstructions(OL, *IL, SE);
291 EXPECT_EQ(InstrV.size(), 5u);
292
293 Instruction *SI = getInstructionByName(F, "varr")->getNextNode();
294 Instruction *CI = SI->getNextNode();
295 Instruction *OLH =
296 getInstructionByName(F, "i")->getNextNode()->getNextNode();
297 Instruction *OLL = getInstructionByName(F, "inc13")->getNextNode();
298 Instruction *IE = getInstructionByName(F, "varr1")->getNextNode();
299
300 EXPECT_EQ(InstrV.front(), OLH);
301 EXPECT_EQ(InstrV[1], OLL);
302 EXPECT_EQ(InstrV[2], IE);
303 EXPECT_EQ(InstrV[3], SI);
304 EXPECT_EQ(InstrV.back(), CI);
305 });
306 }
307