1 //===- LoopInfoTest.cpp - LoopInfo 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/LoopInfo.h"
10 #include "llvm/Analysis/AssumptionCache.h"
11 #include "llvm/Analysis/ScalarEvolution.h"
12 #include "llvm/Analysis/TargetLibraryInfo.h"
13 #include "llvm/AsmParser/Parser.h"
14 #include "llvm/IR/Constants.h"
15 #include "llvm/IR/Dominators.h"
16 #include "llvm/IR/Module.h"
17 #include "llvm/Support/SourceMgr.h"
18 #include "gtest/gtest.h"
19
20 using namespace llvm;
21
22 /// Build the loop info for the function and run the Test.
23 static void
runWithLoopInfo(Module & M,StringRef FuncName,function_ref<void (Function & F,LoopInfo & LI)> Test)24 runWithLoopInfo(Module &M, StringRef FuncName,
25 function_ref<void(Function &F, LoopInfo &LI)> Test) {
26 auto *F = M.getFunction(FuncName);
27 ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
28 // Compute the dominator tree and the loop info for the function.
29 DominatorTree DT(*F);
30 LoopInfo LI(DT);
31 Test(*F, LI);
32 }
33
34 /// Build the loop info and scalar evolution for the function and run the Test.
runWithLoopInfoPlus(Module & M,StringRef FuncName,function_ref<void (Function & F,LoopInfo & LI,ScalarEvolution & SE)> Test)35 static void runWithLoopInfoPlus(
36 Module &M, StringRef FuncName,
37 function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {
38 auto *F = M.getFunction(FuncName);
39 ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
40
41 TargetLibraryInfoImpl TLII;
42 TargetLibraryInfo TLI(TLII);
43 AssumptionCache AC(*F);
44 DominatorTree DT(*F);
45 LoopInfo LI(DT);
46 ScalarEvolution SE(*F, TLI, AC, DT, LI);
47 Test(*F, LI, SE);
48 }
49
makeLLVMModule(LLVMContext & Context,const char * ModuleStr)50 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
51 const char *ModuleStr) {
52 SMDiagnostic Err;
53 return parseAssemblyString(ModuleStr, Err, Context);
54 }
55
56 // This tests that for a loop with a single latch, we get the loop id from
57 // its only latch, even in case the loop may not be in a simplified form.
TEST(LoopInfoTest,LoopWithSingleLatch)58 TEST(LoopInfoTest, LoopWithSingleLatch) {
59 const char *ModuleStr =
60 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
61 "define void @foo(i32 %n) {\n"
62 "entry:\n"
63 " br i1 undef, label %for.cond, label %for.end\n"
64 "for.cond:\n"
65 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
66 " %cmp = icmp slt i32 %i.0, %n\n"
67 " br i1 %cmp, label %for.inc, label %for.end\n"
68 "for.inc:\n"
69 " %inc = add nsw i32 %i.0, 1\n"
70 " br label %for.cond, !llvm.loop !0\n"
71 "for.end:\n"
72 " ret void\n"
73 "}\n"
74 "!0 = distinct !{!0, !1}\n"
75 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
76
77 // Parse the module.
78 LLVMContext Context;
79 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
80
81 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
82 Function::iterator FI = F.begin();
83 // First basic block is entry - skip it.
84 BasicBlock *Header = &*(++FI);
85 assert(Header->getName() == "for.cond");
86 Loop *L = LI.getLoopFor(Header);
87
88 // This loop is not in simplified form.
89 EXPECT_FALSE(L->isLoopSimplifyForm());
90
91 // Analyze the loop metadata id.
92 bool loopIDFoundAndSet = false;
93 // Try to get and set the metadata id for the loop.
94 if (MDNode *D = L->getLoopID()) {
95 L->setLoopID(D);
96 loopIDFoundAndSet = true;
97 }
98
99 // We must have successfully found and set the loop id in the
100 // only latch the loop has.
101 EXPECT_TRUE(loopIDFoundAndSet);
102 });
103 }
104
105 // Test loop id handling for a loop with multiple latches.
TEST(LoopInfoTest,LoopWithMultipleLatches)106 TEST(LoopInfoTest, LoopWithMultipleLatches) {
107 const char *ModuleStr =
108 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
109 "define void @foo(i32 %n) {\n"
110 "entry:\n"
111 " br i1 undef, label %for.cond, label %for.end\n"
112 "for.cond:\n"
113 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %latch.1 ], [ %inc, %latch.2 ]\n"
114 " %inc = add nsw i32 %i.0, 1\n"
115 " %cmp = icmp slt i32 %i.0, %n\n"
116 " br i1 %cmp, label %latch.1, label %for.end\n"
117 "latch.1:\n"
118 " br i1 undef, label %for.cond, label %latch.2, !llvm.loop !0\n"
119 "latch.2:\n"
120 " br label %for.cond, !llvm.loop !0\n"
121 "for.end:\n"
122 " ret void\n"
123 "}\n"
124 "!0 = distinct !{!0, !1}\n"
125 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
126
127 // Parse the module.
128 LLVMContext Context;
129 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
130
131 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
132 Function::iterator FI = F.begin();
133 // First basic block is entry - skip it.
134 BasicBlock *Header = &*(++FI);
135 assert(Header->getName() == "for.cond");
136 Loop *L = LI.getLoopFor(Header);
137 EXPECT_NE(L, nullptr);
138
139 // This loop is not in simplified form.
140 EXPECT_FALSE(L->isLoopSimplifyForm());
141
142 // Try to get and set the metadata id for the loop.
143 MDNode *OldLoopID = L->getLoopID();
144 EXPECT_NE(OldLoopID, nullptr);
145
146 MDNode *NewLoopID = MDNode::get(Context, {nullptr});
147 // Set operand 0 to refer to the loop id itself.
148 NewLoopID->replaceOperandWith(0, NewLoopID);
149
150 L->setLoopID(NewLoopID);
151 EXPECT_EQ(L->getLoopID(), NewLoopID);
152 EXPECT_NE(L->getLoopID(), OldLoopID);
153
154 L->setLoopID(OldLoopID);
155 EXPECT_EQ(L->getLoopID(), OldLoopID);
156 EXPECT_NE(L->getLoopID(), NewLoopID);
157 });
158 }
159
TEST(LoopInfoTest,PreorderTraversals)160 TEST(LoopInfoTest, PreorderTraversals) {
161 const char *ModuleStr = "define void @f() {\n"
162 "entry:\n"
163 " br label %loop.0\n"
164 "loop.0:\n"
165 " br i1 undef, label %loop.0.0, label %loop.1\n"
166 "loop.0.0:\n"
167 " br i1 undef, label %loop.0.0, label %loop.0.1\n"
168 "loop.0.1:\n"
169 " br i1 undef, label %loop.0.1, label %loop.0.2\n"
170 "loop.0.2:\n"
171 " br i1 undef, label %loop.0.2, label %loop.0\n"
172 "loop.1:\n"
173 " br i1 undef, label %loop.1.0, label %end\n"
174 "loop.1.0:\n"
175 " br i1 undef, label %loop.1.0, label %loop.1.1\n"
176 "loop.1.1:\n"
177 " br i1 undef, label %loop.1.1, label %loop.1.2\n"
178 "loop.1.2:\n"
179 " br i1 undef, label %loop.1.2, label %loop.1\n"
180 "end:\n"
181 " ret void\n"
182 "}\n";
183 // Parse the module.
184 LLVMContext Context;
185 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
186 Function &F = *M->begin();
187
188 DominatorTree DT(F);
189 LoopInfo LI;
190 LI.analyze(DT);
191
192 Function::iterator I = F.begin();
193 ASSERT_EQ("entry", I->getName());
194 ++I;
195 Loop &L_0 = *LI.getLoopFor(&*I++);
196 ASSERT_EQ("loop.0", L_0.getHeader()->getName());
197 Loop &L_0_0 = *LI.getLoopFor(&*I++);
198 ASSERT_EQ("loop.0.0", L_0_0.getHeader()->getName());
199 Loop &L_0_1 = *LI.getLoopFor(&*I++);
200 ASSERT_EQ("loop.0.1", L_0_1.getHeader()->getName());
201 Loop &L_0_2 = *LI.getLoopFor(&*I++);
202 ASSERT_EQ("loop.0.2", L_0_2.getHeader()->getName());
203 Loop &L_1 = *LI.getLoopFor(&*I++);
204 ASSERT_EQ("loop.1", L_1.getHeader()->getName());
205 Loop &L_1_0 = *LI.getLoopFor(&*I++);
206 ASSERT_EQ("loop.1.0", L_1_0.getHeader()->getName());
207 Loop &L_1_1 = *LI.getLoopFor(&*I++);
208 ASSERT_EQ("loop.1.1", L_1_1.getHeader()->getName());
209 Loop &L_1_2 = *LI.getLoopFor(&*I++);
210 ASSERT_EQ("loop.1.2", L_1_2.getHeader()->getName());
211
212 auto Preorder = LI.getLoopsInPreorder();
213 ASSERT_EQ(8u, Preorder.size());
214 EXPECT_EQ(&L_0, Preorder[0]);
215 EXPECT_EQ(&L_0_0, Preorder[1]);
216 EXPECT_EQ(&L_0_1, Preorder[2]);
217 EXPECT_EQ(&L_0_2, Preorder[3]);
218 EXPECT_EQ(&L_1, Preorder[4]);
219 EXPECT_EQ(&L_1_0, Preorder[5]);
220 EXPECT_EQ(&L_1_1, Preorder[6]);
221 EXPECT_EQ(&L_1_2, Preorder[7]);
222
223 auto ReverseSiblingPreorder = LI.getLoopsInReverseSiblingPreorder();
224 ASSERT_EQ(8u, ReverseSiblingPreorder.size());
225 EXPECT_EQ(&L_1, ReverseSiblingPreorder[0]);
226 EXPECT_EQ(&L_1_2, ReverseSiblingPreorder[1]);
227 EXPECT_EQ(&L_1_1, ReverseSiblingPreorder[2]);
228 EXPECT_EQ(&L_1_0, ReverseSiblingPreorder[3]);
229 EXPECT_EQ(&L_0, ReverseSiblingPreorder[4]);
230 EXPECT_EQ(&L_0_2, ReverseSiblingPreorder[5]);
231 EXPECT_EQ(&L_0_1, ReverseSiblingPreorder[6]);
232 EXPECT_EQ(&L_0_0, ReverseSiblingPreorder[7]);
233 }
234
TEST(LoopInfoTest,CanonicalLoop)235 TEST(LoopInfoTest, CanonicalLoop) {
236 const char *ModuleStr =
237 "define void @foo(i32* %A, i32 %ub) {\n"
238 "entry:\n"
239 " %guardcmp = icmp slt i32 0, %ub\n"
240 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
241 "for.preheader:\n"
242 " br label %for.body\n"
243 "for.body:\n"
244 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
245 " %idxprom = sext i32 %i to i64\n"
246 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
247 " store i32 %i, i32* %arrayidx, align 4\n"
248 " %inc = add nsw i32 %i, 1\n"
249 " %cmp = icmp slt i32 %inc, %ub\n"
250 " br i1 %cmp, label %for.body, label %for.exit\n"
251 "for.exit:\n"
252 " br label %for.end\n"
253 "for.end:\n"
254 " ret void\n"
255 "}\n";
256
257 // Parse the module.
258 LLVMContext Context;
259 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
260
261 runWithLoopInfoPlus(
262 *M, "foo",
263 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
264 Function::iterator FI = F.begin();
265 BasicBlock *Entry = &*(FI);
266 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
267 // First two basic block are entry and for.preheader - skip them.
268 ++FI;
269 BasicBlock *Header = &*(++FI);
270 assert(Header->getName() == "for.body");
271 Loop *L = LI.getLoopFor(Header);
272 EXPECT_NE(L, nullptr);
273
274 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
275 EXPECT_NE(Bounds, std::nullopt);
276 ConstantInt *InitialIVValue =
277 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
278 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
279 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
280 ConstantInt *StepValue =
281 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
282 EXPECT_TRUE(StepValue && StepValue->isOne());
283 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
284 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
285 EXPECT_EQ(Bounds->getDirection(),
286 Loop::LoopBounds::Direction::Increasing);
287 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
288 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
289 EXPECT_TRUE(L->isGuarded());
290 EXPECT_TRUE(L->isRotatedForm());
291 });
292 }
293
TEST(LoopInfoTest,LoopWithInverseGuardSuccs)294 TEST(LoopInfoTest, LoopWithInverseGuardSuccs) {
295 const char *ModuleStr =
296 "define void @foo(i32* %A, i32 %ub) {\n"
297 "entry:\n"
298 " %guardcmp = icmp sge i32 0, %ub\n"
299 " br i1 %guardcmp, label %for.end, label %for.preheader\n"
300 "for.preheader:\n"
301 " br label %for.body\n"
302 "for.body:\n"
303 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
304 " %idxprom = sext i32 %i to i64\n"
305 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
306 " store i32 %i, i32* %arrayidx, align 4\n"
307 " %inc = add nsw i32 %i, 1\n"
308 " %cmp = icmp slt i32 %inc, %ub\n"
309 " br i1 %cmp, label %for.body, label %for.exit\n"
310 "for.exit:\n"
311 " br label %for.end\n"
312 "for.end:\n"
313 " ret void\n"
314 "}\n";
315
316 // Parse the module.
317 LLVMContext Context;
318 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
319
320 runWithLoopInfoPlus(
321 *M, "foo",
322 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
323 Function::iterator FI = F.begin();
324 BasicBlock *Entry = &*(FI);
325 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
326 // First two basic block are entry and for.preheader - skip them.
327 ++FI;
328 BasicBlock *Header = &*(++FI);
329 assert(Header->getName() == "for.body");
330 Loop *L = LI.getLoopFor(Header);
331 EXPECT_NE(L, nullptr);
332
333 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
334 EXPECT_NE(Bounds, std::nullopt);
335 ConstantInt *InitialIVValue =
336 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
337 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
338 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
339 ConstantInt *StepValue =
340 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
341 EXPECT_TRUE(StepValue && StepValue->isOne());
342 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
343 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
344 EXPECT_EQ(Bounds->getDirection(),
345 Loop::LoopBounds::Direction::Increasing);
346 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
347 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
348 EXPECT_TRUE(L->isGuarded());
349 EXPECT_TRUE(L->isRotatedForm());
350 });
351 }
352
TEST(LoopInfoTest,LoopWithSwappedGuardCmp)353 TEST(LoopInfoTest, LoopWithSwappedGuardCmp) {
354 const char *ModuleStr =
355 "define void @foo(i32* %A, i32 %ub) {\n"
356 "entry:\n"
357 " %guardcmp = icmp sgt i32 %ub, 0\n"
358 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
359 "for.preheader:\n"
360 " br label %for.body\n"
361 "for.body:\n"
362 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
363 " %idxprom = sext i32 %i to i64\n"
364 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
365 " store i32 %i, i32* %arrayidx, align 4\n"
366 " %inc = add nsw i32 %i, 1\n"
367 " %cmp = icmp sge i32 %inc, %ub\n"
368 " br i1 %cmp, label %for.exit, label %for.body\n"
369 "for.exit:\n"
370 " br label %for.end\n"
371 "for.end:\n"
372 " ret void\n"
373 "}\n";
374
375 // Parse the module.
376 LLVMContext Context;
377 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
378
379 runWithLoopInfoPlus(
380 *M, "foo",
381 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
382 Function::iterator FI = F.begin();
383 BasicBlock *Entry = &*(FI);
384 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
385 // First two basic block are entry and for.preheader - skip them.
386 ++FI;
387 BasicBlock *Header = &*(++FI);
388 assert(Header->getName() == "for.body");
389 Loop *L = LI.getLoopFor(Header);
390 EXPECT_NE(L, nullptr);
391
392 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
393 EXPECT_NE(Bounds, std::nullopt);
394 ConstantInt *InitialIVValue =
395 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
396 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
397 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
398 ConstantInt *StepValue =
399 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
400 EXPECT_TRUE(StepValue && StepValue->isOne());
401 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
402 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
403 EXPECT_EQ(Bounds->getDirection(),
404 Loop::LoopBounds::Direction::Increasing);
405 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
406 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
407 EXPECT_TRUE(L->isGuarded());
408 EXPECT_TRUE(L->isRotatedForm());
409 });
410 }
411
TEST(LoopInfoTest,LoopWithInverseLatchSuccs)412 TEST(LoopInfoTest, LoopWithInverseLatchSuccs) {
413 const char *ModuleStr =
414 "define void @foo(i32* %A, i32 %ub) {\n"
415 "entry:\n"
416 " %guardcmp = icmp slt i32 0, %ub\n"
417 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
418 "for.preheader:\n"
419 " br label %for.body\n"
420 "for.body:\n"
421 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
422 " %idxprom = sext i32 %i to i64\n"
423 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
424 " store i32 %i, i32* %arrayidx, align 4\n"
425 " %inc = add nsw i32 %i, 1\n"
426 " %cmp = icmp sge i32 %inc, %ub\n"
427 " br i1 %cmp, label %for.exit, label %for.body\n"
428 "for.exit:\n"
429 " br label %for.end\n"
430 "for.end:\n"
431 " ret void\n"
432 "}\n";
433
434 // Parse the module.
435 LLVMContext Context;
436 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
437
438 runWithLoopInfoPlus(
439 *M, "foo",
440 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
441 Function::iterator FI = F.begin();
442 BasicBlock *Entry = &*(FI);
443 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
444 // First two basic block are entry and for.preheader - skip them.
445 ++FI;
446 BasicBlock *Header = &*(++FI);
447 assert(Header->getName() == "for.body");
448 Loop *L = LI.getLoopFor(Header);
449 EXPECT_NE(L, nullptr);
450
451 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
452 EXPECT_NE(Bounds, std::nullopt);
453 ConstantInt *InitialIVValue =
454 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
455 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
456 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
457 ConstantInt *StepValue =
458 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
459 EXPECT_TRUE(StepValue && StepValue->isOne());
460 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
461 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
462 EXPECT_EQ(Bounds->getDirection(),
463 Loop::LoopBounds::Direction::Increasing);
464 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
465 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
466 EXPECT_TRUE(L->isGuarded());
467 EXPECT_TRUE(L->isRotatedForm());
468 });
469 }
470
TEST(LoopInfoTest,LoopWithLatchCmpNE)471 TEST(LoopInfoTest, LoopWithLatchCmpNE) {
472 const char *ModuleStr =
473 "define void @foo(i32* %A, i32 %ub) {\n"
474 "entry:\n"
475 " %guardcmp = icmp slt i32 0, %ub\n"
476 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
477 "for.preheader:\n"
478 " br label %for.body\n"
479 "for.body:\n"
480 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
481 " %idxprom = sext i32 %i to i64\n"
482 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
483 " store i32 %i, i32* %arrayidx, align 4\n"
484 " %inc = add nsw i32 %i, 1\n"
485 " %cmp = icmp ne i32 %i, %ub\n"
486 " br i1 %cmp, label %for.body, label %for.exit\n"
487 "for.exit:\n"
488 " br label %for.end\n"
489 "for.end:\n"
490 " ret void\n"
491 "}\n";
492
493 // Parse the module.
494 LLVMContext Context;
495 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
496
497 runWithLoopInfoPlus(
498 *M, "foo",
499 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
500 Function::iterator FI = F.begin();
501 BasicBlock *Entry = &*(FI);
502 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
503 // First two basic block are entry and for.preheader - skip them.
504 ++FI;
505 BasicBlock *Header = &*(++FI);
506 assert(Header->getName() == "for.body");
507 Loop *L = LI.getLoopFor(Header);
508 EXPECT_NE(L, nullptr);
509
510 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
511 EXPECT_NE(Bounds, std::nullopt);
512 ConstantInt *InitialIVValue =
513 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
514 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
515 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
516 ConstantInt *StepValue =
517 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
518 EXPECT_TRUE(StepValue && StepValue->isOne());
519 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
520 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
521 EXPECT_EQ(Bounds->getDirection(),
522 Loop::LoopBounds::Direction::Increasing);
523 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
524 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
525 EXPECT_TRUE(L->isGuarded());
526 EXPECT_TRUE(L->isRotatedForm());
527 });
528 }
529
TEST(LoopInfoTest,LoopWithGuardCmpSLE)530 TEST(LoopInfoTest, LoopWithGuardCmpSLE) {
531 const char *ModuleStr =
532 "define void @foo(i32* %A, i32 %ub) {\n"
533 "entry:\n"
534 " %ubPlusOne = add i32 %ub, 1\n"
535 " %guardcmp = icmp sle i32 0, %ub\n"
536 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
537 "for.preheader:\n"
538 " br label %for.body\n"
539 "for.body:\n"
540 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
541 " %idxprom = sext i32 %i to i64\n"
542 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
543 " store i32 %i, i32* %arrayidx, align 4\n"
544 " %inc = add nsw i32 %i, 1\n"
545 " %cmp = icmp ne i32 %i, %ubPlusOne\n"
546 " br i1 %cmp, label %for.body, label %for.exit\n"
547 "for.exit:\n"
548 " br label %for.end\n"
549 "for.end:\n"
550 " ret void\n"
551 "}\n";
552
553 // Parse the module.
554 LLVMContext Context;
555 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
556
557 runWithLoopInfoPlus(
558 *M, "foo",
559 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
560 Function::iterator FI = F.begin();
561 BasicBlock *Entry = &*(FI);
562 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
563 // First two basic block are entry and for.preheader - skip them.
564 ++FI;
565 BasicBlock *Header = &*(++FI);
566 assert(Header->getName() == "for.body");
567 Loop *L = LI.getLoopFor(Header);
568 EXPECT_NE(L, nullptr);
569
570 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
571 EXPECT_NE(Bounds, std::nullopt);
572 ConstantInt *InitialIVValue =
573 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
574 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
575 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
576 ConstantInt *StepValue =
577 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
578 EXPECT_TRUE(StepValue && StepValue->isOne());
579 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ubPlusOne");
580 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
581 EXPECT_EQ(Bounds->getDirection(),
582 Loop::LoopBounds::Direction::Increasing);
583 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
584 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
585 EXPECT_TRUE(L->isGuarded());
586 EXPECT_TRUE(L->isRotatedForm());
587 });
588 }
589
TEST(LoopInfoTest,LoopNonConstantStep)590 TEST(LoopInfoTest, LoopNonConstantStep) {
591 const char *ModuleStr =
592 "define void @foo(i32* %A, i32 %ub, i32 %step) {\n"
593 "entry:\n"
594 " %guardcmp = icmp slt i32 0, %ub\n"
595 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
596 "for.preheader:\n"
597 " br label %for.body\n"
598 "for.body:\n"
599 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
600 " %idxprom = zext i32 %i to i64\n"
601 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
602 " store i32 %i, i32* %arrayidx, align 4\n"
603 " %inc = add nsw i32 %i, %step\n"
604 " %cmp = icmp slt i32 %inc, %ub\n"
605 " br i1 %cmp, label %for.body, label %for.exit\n"
606 "for.exit:\n"
607 " br label %for.end\n"
608 "for.end:\n"
609 " ret void\n"
610 "}\n";
611
612 // Parse the module.
613 LLVMContext Context;
614 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
615
616 runWithLoopInfoPlus(
617 *M, "foo",
618 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
619 Function::iterator FI = F.begin();
620 BasicBlock *Entry = &*(FI);
621 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
622 // First two basic block are entry and for.preheader - skip them.
623 ++FI;
624 BasicBlock *Header = &*(++FI);
625 assert(Header->getName() == "for.body");
626 Loop *L = LI.getLoopFor(Header);
627 EXPECT_NE(L, nullptr);
628
629 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
630 EXPECT_NE(Bounds, std::nullopt);
631 ConstantInt *InitialIVValue =
632 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
633 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
634 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
635 EXPECT_EQ(Bounds->getStepValue()->getName(), "step");
636 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
637 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
638 EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown);
639 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
640 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
641 EXPECT_TRUE(L->isGuarded());
642 EXPECT_TRUE(L->isRotatedForm());
643 });
644 }
645
TEST(LoopInfoTest,LoopUnsignedBounds)646 TEST(LoopInfoTest, LoopUnsignedBounds) {
647 const char *ModuleStr =
648 "define void @foo(i32* %A, i32 %ub) {\n"
649 "entry:\n"
650 " %guardcmp = icmp ult i32 0, %ub\n"
651 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
652 "for.preheader:\n"
653 " br label %for.body\n"
654 "for.body:\n"
655 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
656 " %idxprom = zext i32 %i to i64\n"
657 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
658 " store i32 %i, i32* %arrayidx, align 4\n"
659 " %inc = add i32 %i, 1\n"
660 " %cmp = icmp ult i32 %inc, %ub\n"
661 " br i1 %cmp, label %for.body, label %for.exit\n"
662 "for.exit:\n"
663 " br label %for.end\n"
664 "for.end:\n"
665 " ret void\n"
666 "}\n";
667
668 // Parse the module.
669 LLVMContext Context;
670 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
671
672 runWithLoopInfoPlus(
673 *M, "foo",
674 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
675 Function::iterator FI = F.begin();
676 BasicBlock *Entry = &*(FI);
677 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
678 // First two basic block are entry and for.preheader - skip them.
679 ++FI;
680 BasicBlock *Header = &*(++FI);
681 assert(Header->getName() == "for.body");
682 Loop *L = LI.getLoopFor(Header);
683 EXPECT_NE(L, nullptr);
684
685 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
686 EXPECT_NE(Bounds, std::nullopt);
687 ConstantInt *InitialIVValue =
688 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
689 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
690 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
691 ConstantInt *StepValue =
692 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
693 EXPECT_TRUE(StepValue && StepValue->isOne());
694 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
695 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_ULT);
696 EXPECT_EQ(Bounds->getDirection(),
697 Loop::LoopBounds::Direction::Increasing);
698 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
699 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
700 EXPECT_TRUE(L->isGuarded());
701 EXPECT_TRUE(L->isRotatedForm());
702 });
703 }
704
TEST(LoopInfoTest,DecreasingLoop)705 TEST(LoopInfoTest, DecreasingLoop) {
706 const char *ModuleStr =
707 "define void @foo(i32* %A, i32 %ub) {\n"
708 "entry:\n"
709 " %guardcmp = icmp slt i32 0, %ub\n"
710 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
711 "for.preheader:\n"
712 " br label %for.body\n"
713 "for.body:\n"
714 " %i = phi i32 [ %ub, %for.preheader ], [ %inc, %for.body ]\n"
715 " %idxprom = sext i32 %i to i64\n"
716 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
717 " store i32 %i, i32* %arrayidx, align 4\n"
718 " %inc = sub nsw i32 %i, 1\n"
719 " %cmp = icmp sgt i32 %inc, 0\n"
720 " br i1 %cmp, label %for.body, label %for.exit\n"
721 "for.exit:\n"
722 " br label %for.end\n"
723 "for.end:\n"
724 " ret void\n"
725 "}\n";
726
727 // Parse the module.
728 LLVMContext Context;
729 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
730
731 runWithLoopInfoPlus(
732 *M, "foo",
733 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
734 Function::iterator FI = F.begin();
735 BasicBlock *Entry = &*(FI);
736 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
737 // First two basic block are entry and for.preheader - skip them.
738 ++FI;
739 BasicBlock *Header = &*(++FI);
740 assert(Header->getName() == "for.body");
741 Loop *L = LI.getLoopFor(Header);
742 EXPECT_NE(L, nullptr);
743
744 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
745 EXPECT_NE(Bounds, std::nullopt);
746 EXPECT_EQ(Bounds->getInitialIVValue().getName(), "ub");
747 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
748 ConstantInt *StepValue =
749 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
750 EXPECT_EQ(StepValue, nullptr);
751 ConstantInt *FinalIVValue =
752 dyn_cast<ConstantInt>(&Bounds->getFinalIVValue());
753 EXPECT_TRUE(FinalIVValue && FinalIVValue->isZero());
754 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SGT);
755 EXPECT_EQ(Bounds->getDirection(),
756 Loop::LoopBounds::Direction::Decreasing);
757 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
758 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
759 EXPECT_TRUE(L->isGuarded());
760 EXPECT_TRUE(L->isRotatedForm());
761 });
762 }
763
TEST(LoopInfoTest,CannotFindDirection)764 TEST(LoopInfoTest, CannotFindDirection) {
765 const char *ModuleStr =
766 "define void @foo(i32* %A, i32 %ub, i32 %step) {\n"
767 "entry:\n"
768 " %guardcmp = icmp slt i32 0, %ub\n"
769 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
770 "for.preheader:\n"
771 " br label %for.body\n"
772 "for.body:\n"
773 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
774 " %idxprom = sext i32 %i to i64\n"
775 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
776 " store i32 %i, i32* %arrayidx, align 4\n"
777 " %inc = add nsw i32 %i, %step\n"
778 " %cmp = icmp ne i32 %i, %ub\n"
779 " br i1 %cmp, label %for.body, label %for.exit\n"
780 "for.exit:\n"
781 " br label %for.end\n"
782 "for.end:\n"
783 " ret void\n"
784 "}\n";
785
786 // Parse the module.
787 LLVMContext Context;
788 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
789
790 runWithLoopInfoPlus(
791 *M, "foo",
792 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
793 Function::iterator FI = F.begin();
794 BasicBlock *Entry = &*(FI);
795 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
796 // First two basic block are entry and for.preheader
797 // - skip them.
798 ++FI;
799 BasicBlock *Header = &*(++FI);
800 assert(Header->getName() == "for.body");
801 Loop *L = LI.getLoopFor(Header);
802 EXPECT_NE(L, nullptr);
803
804 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
805 EXPECT_NE(Bounds, std::nullopt);
806 ConstantInt *InitialIVValue =
807 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
808 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
809 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
810 EXPECT_EQ(Bounds->getStepValue()->getName(), "step");
811 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
812 EXPECT_EQ(Bounds->getCanonicalPredicate(),
813 ICmpInst::BAD_ICMP_PREDICATE);
814 EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown);
815 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
816 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
817 EXPECT_TRUE(L->isGuarded());
818 EXPECT_TRUE(L->isRotatedForm());
819 });
820 }
821
TEST(LoopInfoTest,ZextIndVar)822 TEST(LoopInfoTest, ZextIndVar) {
823 const char *ModuleStr =
824 "define void @foo(i32* %A, i32 %ub) {\n"
825 "entry:\n"
826 " %guardcmp = icmp slt i32 0, %ub\n"
827 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
828 "for.preheader:\n"
829 " br label %for.body\n"
830 "for.body:\n"
831 " %indvars.iv = phi i64 [ 0, %for.preheader ], [ %indvars.iv.next, %for.body ]\n"
832 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
833 " %idxprom = sext i32 %i to i64\n"
834 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
835 " store i32 %i, i32* %arrayidx, align 4\n"
836 " %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n"
837 " %inc = add nsw i32 %i, 1\n"
838 " %wide.trip.count = zext i32 %ub to i64\n"
839 " %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count\n"
840 " br i1 %exitcond, label %for.body, label %for.exit\n"
841 "for.exit:\n"
842 " br label %for.end\n"
843 "for.end:\n"
844 " ret void\n"
845 "}\n";
846
847 // Parse the module.
848 LLVMContext Context;
849 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
850
851 runWithLoopInfoPlus(
852 *M, "foo",
853 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
854 Function::iterator FI = F.begin();
855 BasicBlock *Entry = &*(FI);
856 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
857 // First two basic block are entry and for.preheader - skip them.
858 ++FI;
859 BasicBlock *Header = &*(++FI);
860 assert(Header->getName() == "for.body");
861 Loop *L = LI.getLoopFor(Header);
862 EXPECT_NE(L, nullptr);
863
864 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
865 EXPECT_NE(Bounds, std::nullopt);
866 ConstantInt *InitialIVValue =
867 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
868 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
869 EXPECT_EQ(Bounds->getStepInst().getName(), "indvars.iv.next");
870 ConstantInt *StepValue =
871 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
872 EXPECT_TRUE(StepValue && StepValue->isOne());
873 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "wide.trip.count");
874 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_NE);
875 EXPECT_EQ(Bounds->getDirection(),
876 Loop::LoopBounds::Direction::Increasing);
877 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv");
878 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
879 EXPECT_TRUE(L->isGuarded());
880 EXPECT_TRUE(L->isRotatedForm());
881 });
882 }
883
TEST(LoopInfoTest,MultiExitingLoop)884 TEST(LoopInfoTest, MultiExitingLoop) {
885 const char *ModuleStr =
886 "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
887 "entry:\n"
888 " %guardcmp = icmp slt i32 0, %ub\n"
889 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
890 "for.preheader:\n"
891 " br label %for.body\n"
892 "for.body:\n"
893 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body.1 ]\n"
894 " br i1 %cond, label %for.body.1, label %for.exit\n"
895 "for.body.1:\n"
896 " %idxprom = sext i32 %i to i64\n"
897 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
898 " store i32 %i, i32* %arrayidx, align 4\n"
899 " %inc = add nsw i32 %i, 1\n"
900 " %cmp = icmp slt i32 %inc, %ub\n"
901 " br i1 %cmp, label %for.body, label %for.exit\n"
902 "for.exit:\n"
903 " br label %for.end\n"
904 "for.end:\n"
905 " ret void\n"
906 "}\n";
907
908 // Parse the module.
909 LLVMContext Context;
910 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
911
912 runWithLoopInfoPlus(
913 *M, "foo",
914 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
915 Function::iterator FI = F.begin();
916 BasicBlock *Entry = &*(FI);
917 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
918 // First two basic block are entry and for.preheader - skip them.
919 ++FI;
920 BasicBlock *Header = &*(++FI);
921 assert(Header->getName() == "for.body");
922 Loop *L = LI.getLoopFor(Header);
923 EXPECT_NE(L, nullptr);
924
925 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
926 EXPECT_NE(Bounds, std::nullopt);
927 ConstantInt *InitialIVValue =
928 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
929 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
930 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
931 ConstantInt *StepValue =
932 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
933 EXPECT_TRUE(StepValue && StepValue->isOne());
934 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
935 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
936 EXPECT_EQ(Bounds->getDirection(),
937 Loop::LoopBounds::Direction::Increasing);
938 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
939 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
940 EXPECT_TRUE(L->isGuarded());
941 });
942 }
943
TEST(LoopInfoTest,MultiExitLoop)944 TEST(LoopInfoTest, MultiExitLoop) {
945 const char *ModuleStr =
946 "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
947 "entry:\n"
948 " %guardcmp = icmp slt i32 0, %ub\n"
949 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
950 "for.preheader:\n"
951 " br label %for.body\n"
952 "for.body:\n"
953 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body.1 ]\n"
954 " br i1 %cond, label %for.body.1, label %for.exit\n"
955 "for.body.1:\n"
956 " %idxprom = sext i32 %i to i64\n"
957 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
958 " store i32 %i, i32* %arrayidx, align 4\n"
959 " %inc = add nsw i32 %i, 1\n"
960 " %cmp = icmp slt i32 %inc, %ub\n"
961 " br i1 %cmp, label %for.body, label %for.exit.1\n"
962 "for.exit:\n"
963 " br label %for.end\n"
964 "for.exit.1:\n"
965 " br label %for.end\n"
966 "for.end:\n"
967 " ret void\n"
968 "}\n";
969
970 // Parse the module.
971 LLVMContext Context;
972 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
973
974 runWithLoopInfoPlus(
975 *M, "foo",
976 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
977 Function::iterator FI = F.begin();
978 // First two basic block are entry and for.preheader - skip them.
979 ++FI;
980 BasicBlock *Header = &*(++FI);
981 assert(Header->getName() == "for.body");
982 Loop *L = LI.getLoopFor(Header);
983 EXPECT_NE(L, nullptr);
984
985 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
986 EXPECT_NE(Bounds, std::nullopt);
987 ConstantInt *InitialIVValue =
988 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
989 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
990 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
991 ConstantInt *StepValue =
992 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
993 EXPECT_TRUE(StepValue && StepValue->isOne());
994 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
995 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
996 EXPECT_EQ(Bounds->getDirection(),
997 Loop::LoopBounds::Direction::Increasing);
998 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
999 EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
1000 EXPECT_FALSE(L->isGuarded());
1001 });
1002 }
1003
TEST(LoopInfoTest,UnguardedLoop)1004 TEST(LoopInfoTest, UnguardedLoop) {
1005 const char *ModuleStr =
1006 "define void @foo(i32* %A, i32 %ub) {\n"
1007 "entry:\n"
1008 " br label %for.body\n"
1009 "for.body:\n"
1010 " %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n"
1011 " %idxprom = sext i32 %i to i64\n"
1012 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1013 " store i32 %i, i32* %arrayidx, align 4\n"
1014 " %inc = add nsw i32 %i, 1\n"
1015 " %cmp = icmp slt i32 %inc, %ub\n"
1016 " br i1 %cmp, label %for.body, label %for.exit\n"
1017 "for.exit:\n"
1018 " br label %for.end\n"
1019 "for.end:\n"
1020 " ret void\n"
1021 "}\n";
1022
1023 // Parse the module.
1024 LLVMContext Context;
1025 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1026
1027 runWithLoopInfoPlus(
1028 *M, "foo",
1029 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1030 Function::iterator FI = F.begin();
1031 // First basic block is entry - skip it.
1032 BasicBlock *Header = &*(++FI);
1033 assert(Header->getName() == "for.body");
1034 Loop *L = LI.getLoopFor(Header);
1035 EXPECT_NE(L, nullptr);
1036
1037 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1038 EXPECT_NE(Bounds, std::nullopt);
1039 ConstantInt *InitialIVValue =
1040 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1041 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1042 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
1043 ConstantInt *StepValue =
1044 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1045 EXPECT_TRUE(StepValue && StepValue->isOne());
1046 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1047 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1048 EXPECT_EQ(Bounds->getDirection(),
1049 Loop::LoopBounds::Direction::Increasing);
1050 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1051 EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
1052 EXPECT_FALSE(L->isGuarded());
1053 EXPECT_TRUE(L->isRotatedForm());
1054 });
1055 }
1056
TEST(LoopInfoTest,UnguardedLoopWithControlFlow)1057 TEST(LoopInfoTest, UnguardedLoopWithControlFlow) {
1058 const char *ModuleStr =
1059 "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
1060 "entry:\n"
1061 " br i1 %cond, label %for.preheader, label %for.end\n"
1062 "for.preheader:\n"
1063 " br label %for.body\n"
1064 "for.body:\n"
1065 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
1066 " %idxprom = sext i32 %i to i64\n"
1067 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1068 " store i32 %i, i32* %arrayidx, align 4\n"
1069 " %inc = add nsw i32 %i, 1\n"
1070 " %cmp = icmp slt i32 %inc, %ub\n"
1071 " br i1 %cmp, label %for.body, label %for.exit\n"
1072 "for.exit:\n"
1073 " br label %for.end\n"
1074 "for.end:\n"
1075 " ret void\n"
1076 "}\n";
1077
1078 // Parse the module.
1079 LLVMContext Context;
1080 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1081
1082 runWithLoopInfoPlus(
1083 *M, "foo",
1084 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1085 Function::iterator FI = F.begin();
1086 BasicBlock *Entry = &*(FI);
1087 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
1088 // First two basic block are entry and for.preheader - skip them.
1089 ++FI;
1090 BasicBlock *Header = &*(++FI);
1091 assert(Header->getName() == "for.body");
1092 Loop *L = LI.getLoopFor(Header);
1093 EXPECT_NE(L, nullptr);
1094
1095 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1096 EXPECT_NE(Bounds, std::nullopt);
1097 ConstantInt *InitialIVValue =
1098 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1099 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1100 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
1101 ConstantInt *StepValue =
1102 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1103 EXPECT_TRUE(StepValue && StepValue->isOne());
1104 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1105 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1106 EXPECT_EQ(Bounds->getDirection(),
1107 Loop::LoopBounds::Direction::Increasing);
1108 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1109 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
1110 EXPECT_TRUE(L->isGuarded());
1111 EXPECT_TRUE(L->isRotatedForm());
1112 });
1113 }
1114
TEST(LoopInfoTest,LoopNest)1115 TEST(LoopInfoTest, LoopNest) {
1116 const char *ModuleStr =
1117 "define void @foo(i32* %A, i32 %ub) {\n"
1118 "entry:\n"
1119 " %guardcmp = icmp slt i32 0, %ub\n"
1120 " br i1 %guardcmp, label %for.outer.preheader, label %for.end\n"
1121 "for.outer.preheader:\n"
1122 " br label %for.outer\n"
1123 "for.outer:\n"
1124 " %j = phi i32 [ 0, %for.outer.preheader ], [ %inc.outer, %for.outer.latch ]\n"
1125 " br i1 %guardcmp, label %for.inner.preheader, label %for.outer.latch\n"
1126 "for.inner.preheader:\n"
1127 " br label %for.inner\n"
1128 "for.inner:\n"
1129 " %i = phi i32 [ 0, %for.inner.preheader ], [ %inc, %for.inner ]\n"
1130 " %idxprom = sext i32 %i to i64\n"
1131 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1132 " store i32 %i, i32* %arrayidx, align 4\n"
1133 " %inc = add nsw i32 %i, 1\n"
1134 " %cmp = icmp slt i32 %inc, %ub\n"
1135 " br i1 %cmp, label %for.inner, label %for.inner.exit\n"
1136 "for.inner.exit:\n"
1137 " br label %for.outer.latch\n"
1138 "for.outer.latch:\n"
1139 " %inc.outer = add nsw i32 %j, 1\n"
1140 " %cmp.outer = icmp slt i32 %inc.outer, %ub\n"
1141 " br i1 %cmp.outer, label %for.outer, label %for.outer.exit\n"
1142 "for.outer.exit:\n"
1143 " br label %for.end\n"
1144 "for.end:\n"
1145 " ret void\n"
1146 "}\n";
1147
1148 // Parse the module.
1149 LLVMContext Context;
1150 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1151
1152 runWithLoopInfoPlus(
1153 *M, "foo",
1154 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1155 Function::iterator FI = F.begin();
1156 BasicBlock *Entry = &*(FI);
1157 BranchInst *OuterGuard = dyn_cast<BranchInst>(Entry->getTerminator());
1158 // First two basic block are entry and for.outer.preheader - skip them.
1159 ++FI;
1160 BasicBlock *Header = &*(++FI);
1161 assert(Header->getName() == "for.outer");
1162 BranchInst *InnerGuard = dyn_cast<BranchInst>(Header->getTerminator());
1163 Loop *L = LI.getLoopFor(Header);
1164 EXPECT_NE(L, nullptr);
1165
1166 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1167 EXPECT_NE(Bounds, std::nullopt);
1168 ConstantInt *InitialIVValue =
1169 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1170 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1171 EXPECT_EQ(Bounds->getStepInst().getName(), "inc.outer");
1172 ConstantInt *StepValue =
1173 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1174 EXPECT_TRUE(StepValue && StepValue->isOne());
1175 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1176 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1177 EXPECT_EQ(Bounds->getDirection(),
1178 Loop::LoopBounds::Direction::Increasing);
1179 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "j");
1180 EXPECT_EQ(L->getLoopGuardBranch(), OuterGuard);
1181 EXPECT_TRUE(L->isGuarded());
1182 EXPECT_TRUE(L->isRotatedForm());
1183
1184 // Next two basic blocks are for.outer and for.inner.preheader - skip
1185 // them.
1186 ++FI;
1187 Header = &*(++FI);
1188 assert(Header->getName() == "for.inner");
1189 L = LI.getLoopFor(Header);
1190 EXPECT_NE(L, nullptr);
1191
1192 std::optional<Loop::LoopBounds> InnerBounds = L->getBounds(SE);
1193 EXPECT_NE(InnerBounds, std::nullopt);
1194 InitialIVValue =
1195 dyn_cast<ConstantInt>(&InnerBounds->getInitialIVValue());
1196 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1197 EXPECT_EQ(InnerBounds->getStepInst().getName(), "inc");
1198 StepValue = dyn_cast_or_null<ConstantInt>(InnerBounds->getStepValue());
1199 EXPECT_TRUE(StepValue && StepValue->isOne());
1200 EXPECT_EQ(InnerBounds->getFinalIVValue().getName(), "ub");
1201 EXPECT_EQ(InnerBounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1202 EXPECT_EQ(InnerBounds->getDirection(),
1203 Loop::LoopBounds::Direction::Increasing);
1204 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1205 EXPECT_EQ(L->getLoopGuardBranch(), InnerGuard);
1206 EXPECT_TRUE(L->isGuarded());
1207 EXPECT_TRUE(L->isRotatedForm());
1208 });
1209 }
1210
TEST(LoopInfoTest,AuxiliaryIV)1211 TEST(LoopInfoTest, AuxiliaryIV) {
1212 const char *ModuleStr =
1213 "define void @foo(i32* %A, i32 %ub) {\n"
1214 "entry:\n"
1215 " %guardcmp = icmp slt i32 0, %ub\n"
1216 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
1217 "for.preheader:\n"
1218 " br label %for.body\n"
1219 "for.body:\n"
1220 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
1221 " %aux = phi i32 [ 0, %for.preheader ], [ %auxinc, %for.body ]\n"
1222 " %loopvariant = phi i32 [ 0, %for.preheader ], [ %loopvariantinc, %for.body ]\n"
1223 " %usedoutside = phi i32 [ 0, %for.preheader ], [ %usedoutsideinc, %for.body ]\n"
1224 " %mulopcode = phi i32 [ 0, %for.preheader ], [ %mulopcodeinc, %for.body ]\n"
1225 " %idxprom = sext i32 %i to i64\n"
1226 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1227 " store i32 %i, i32* %arrayidx, align 4\n"
1228 " %mulopcodeinc = mul nsw i32 %mulopcode, 5\n"
1229 " %usedoutsideinc = add nsw i32 %usedoutside, 5\n"
1230 " %loopvariantinc = add nsw i32 %loopvariant, %i\n"
1231 " %auxinc = add nsw i32 %aux, 5\n"
1232 " %inc = add nsw i32 %i, 1\n"
1233 " %cmp = icmp slt i32 %inc, %ub\n"
1234 " br i1 %cmp, label %for.body, label %for.exit\n"
1235 "for.exit:\n"
1236 " %lcssa = phi i32 [ %usedoutside, %for.body ]\n"
1237 " br label %for.end\n"
1238 "for.end:\n"
1239 " ret void\n"
1240 "}\n";
1241
1242 // Parse the module.
1243 LLVMContext Context;
1244 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1245
1246 runWithLoopInfoPlus(
1247 *M, "foo",
1248 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1249 Function::iterator FI = F.begin();
1250 BasicBlock *Entry = &*(FI);
1251 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
1252 // First two basic block are entry and for.preheader - skip them.
1253 ++FI;
1254 BasicBlock *Header = &*(++FI);
1255 assert(Header->getName() == "for.body");
1256 Loop *L = LI.getLoopFor(Header);
1257 EXPECT_NE(L, nullptr);
1258
1259 std::optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1260 EXPECT_NE(Bounds, std::nullopt);
1261 ConstantInt *InitialIVValue =
1262 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1263 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1264 EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
1265 ConstantInt *StepValue =
1266 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1267 EXPECT_TRUE(StepValue && StepValue->isOne());
1268 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1269 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1270 EXPECT_EQ(Bounds->getDirection(),
1271 Loop::LoopBounds::Direction::Increasing);
1272 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1273 BasicBlock::iterator II = Header->begin();
1274 PHINode &Instruction_i = cast<PHINode>(*(II));
1275 EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_i, SE));
1276 PHINode &Instruction_aux = cast<PHINode>(*(++II));
1277 EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_aux, SE));
1278 PHINode &Instruction_loopvariant = cast<PHINode>(*(++II));
1279 EXPECT_FALSE(
1280 L->isAuxiliaryInductionVariable(Instruction_loopvariant, SE));
1281 PHINode &Instruction_usedoutside = cast<PHINode>(*(++II));
1282 EXPECT_FALSE(
1283 L->isAuxiliaryInductionVariable(Instruction_usedoutside, SE));
1284 PHINode &Instruction_mulopcode = cast<PHINode>(*(++II));
1285 EXPECT_FALSE(
1286 L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE));
1287 EXPECT_EQ(L->getLoopGuardBranch(), Guard);
1288 EXPECT_TRUE(L->isGuarded());
1289 EXPECT_TRUE(L->isRotatedForm());
1290 });
1291 }
1292
TEST(LoopInfoTest,LoopNotInSimplifyForm)1293 TEST(LoopInfoTest, LoopNotInSimplifyForm) {
1294 const char *ModuleStr =
1295 "define void @foo(i32 %n) {\n"
1296 "entry:\n"
1297 " %guard.cmp = icmp sgt i32 %n, 0\n"
1298 " br i1 %guard.cmp, label %for.cond, label %for.end\n"
1299 "for.cond:\n"
1300 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %latch.1 ], [ %inc, %latch.2 ]\n"
1301 " %inc = add nsw i32 %i.0, 1\n"
1302 " %cmp = icmp slt i32 %i.0, %n\n"
1303 " br i1 %cmp, label %latch.1, label %for.end\n"
1304 "latch.1:\n"
1305 " br i1 undef, label %for.cond, label %latch.2\n"
1306 "latch.2:\n"
1307 " br label %for.cond\n"
1308 "for.end:\n"
1309 " ret void\n"
1310 "}\n";
1311
1312 // Parse the module.
1313 LLVMContext Context;
1314 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1315
1316 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1317 Function::iterator FI = F.begin();
1318 // First basic block is entry - skip it.
1319 BasicBlock *Header = &*(++FI);
1320 assert(Header && "No header");
1321 Loop *L = LI.getLoopFor(Header);
1322 EXPECT_NE(L, nullptr);
1323 EXPECT_FALSE(L->isLoopSimplifyForm());
1324 // No loop guard because loop in not in simplify form.
1325 EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
1326 EXPECT_FALSE(L->isGuarded());
1327 });
1328 }
1329
TEST(LoopInfoTest,LoopLatchNotExiting)1330 TEST(LoopInfoTest, LoopLatchNotExiting) {
1331 const char *ModuleStr =
1332 "define void @foo(i32* %A, i32 %ub) {\n"
1333 "entry:\n"
1334 " %guardcmp = icmp slt i32 0, %ub\n"
1335 " br i1 %guardcmp, label %for.preheader, label %for.end\n"
1336 "for.preheader:\n"
1337 " br label %for.body\n"
1338 "for.body:\n"
1339 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
1340 " %idxprom = sext i32 %i to i64\n"
1341 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1342 " store i32 %i, i32* %arrayidx, align 4\n"
1343 " %inc = add nsw i32 %i, 1\n"
1344 " %cmp = icmp slt i32 %inc, %ub\n"
1345 " br i1 %cmp, label %for.latch, label %for.exit\n"
1346 "for.latch:\n"
1347 " br label %for.body\n"
1348 "for.exit:\n"
1349 " br label %for.end\n"
1350 "for.end:\n"
1351 " ret void\n"
1352 "}\n";
1353
1354 // Parse the module.
1355 LLVMContext Context;
1356 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1357
1358 runWithLoopInfoPlus(
1359 *M, "foo",
1360 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1361 Function::iterator FI = F.begin();
1362 // First two basic block are entry and for.preheader - skip them.
1363 ++FI;
1364 BasicBlock *Header = &*(++FI);
1365 BasicBlock *Latch = &*(++FI);
1366 assert(Header && "No header");
1367 Loop *L = LI.getLoopFor(Header);
1368 EXPECT_NE(L, nullptr);
1369 EXPECT_TRUE(L->isLoopSimplifyForm());
1370 EXPECT_EQ(L->getLoopLatch(), Latch);
1371 EXPECT_FALSE(L->isLoopExiting(Latch));
1372 // No loop guard becuase loop is not exiting on latch.
1373 EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
1374 EXPECT_FALSE(L->isGuarded());
1375 });
1376 }
1377
1378 // Examine getUniqueExitBlocks/getUniqueNonLatchExitBlocks functions.
TEST(LoopInfoTest,LoopUniqueExitBlocks)1379 TEST(LoopInfoTest, LoopUniqueExitBlocks) {
1380 const char *ModuleStr =
1381 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
1382 "define void @foo(i32 %n, i1 %cond) {\n"
1383 "entry:\n"
1384 " br label %for.cond\n"
1385 "for.cond:\n"
1386 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
1387 " %cmp = icmp slt i32 %i.0, %n\n"
1388 " br i1 %cond, label %for.inc, label %for.end1\n"
1389 "for.inc:\n"
1390 " %inc = add nsw i32 %i.0, 1\n"
1391 " br i1 %cmp, label %for.cond, label %for.end2, !llvm.loop !0\n"
1392 "for.end1:\n"
1393 " br label %for.end\n"
1394 "for.end2:\n"
1395 " br label %for.end\n"
1396 "for.end:\n"
1397 " ret void\n"
1398 "}\n"
1399 "!0 = distinct !{!0, !1}\n"
1400 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
1401
1402 // Parse the module.
1403 LLVMContext Context;
1404 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1405
1406 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1407 Function::iterator FI = F.begin();
1408 // First basic block is entry - skip it.
1409 BasicBlock *Header = &*(++FI);
1410 assert(Header->getName() == "for.cond");
1411 Loop *L = LI.getLoopFor(Header);
1412
1413 SmallVector<BasicBlock *, 2> Exits;
1414 // This loop has 2 unique exits.
1415 L->getUniqueExitBlocks(Exits);
1416 EXPECT_TRUE(Exits.size() == 2);
1417 // And one unique non latch exit.
1418 Exits.clear();
1419 L->getUniqueNonLatchExitBlocks(Exits);
1420 EXPECT_TRUE(Exits.size() == 1);
1421 });
1422 }
1423
1424 // Regression test for getUniqueNonLatchExitBlocks functions.
1425 // It should detect the exit if it comes from both latch and non-latch blocks.
TEST(LoopInfoTest,LoopNonLatchUniqueExitBlocks)1426 TEST(LoopInfoTest, LoopNonLatchUniqueExitBlocks) {
1427 const char *ModuleStr =
1428 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
1429 "define void @foo(i32 %n, i1 %cond) {\n"
1430 "entry:\n"
1431 " br label %for.cond\n"
1432 "for.cond:\n"
1433 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
1434 " %cmp = icmp slt i32 %i.0, %n\n"
1435 " br i1 %cond, label %for.inc, label %for.end\n"
1436 "for.inc:\n"
1437 " %inc = add nsw i32 %i.0, 1\n"
1438 " br i1 %cmp, label %for.cond, label %for.end, !llvm.loop !0\n"
1439 "for.end:\n"
1440 " ret void\n"
1441 "}\n"
1442 "!0 = distinct !{!0, !1}\n"
1443 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
1444
1445 // Parse the module.
1446 LLVMContext Context;
1447 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1448
1449 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1450 Function::iterator FI = F.begin();
1451 // First basic block is entry - skip it.
1452 BasicBlock *Header = &*(++FI);
1453 assert(Header->getName() == "for.cond");
1454 Loop *L = LI.getLoopFor(Header);
1455
1456 SmallVector<BasicBlock *, 2> Exits;
1457 // This loop has 1 unique exit.
1458 L->getUniqueExitBlocks(Exits);
1459 EXPECT_TRUE(Exits.size() == 1);
1460 // And one unique non latch exit.
1461 Exits.clear();
1462 L->getUniqueNonLatchExitBlocks(Exits);
1463 EXPECT_TRUE(Exits.size() == 1);
1464 });
1465 }
1466
1467 // Test that a pointer-chasing loop is not rotated.
TEST(LoopInfoTest,LoopNotRotated)1468 TEST(LoopInfoTest, LoopNotRotated) {
1469 const char *ModuleStr =
1470 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
1471 "define void @foo(i32* %elem) {\n"
1472 "entry:\n"
1473 " br label %while.cond\n"
1474 "while.cond:\n"
1475 " %elem.addr.0 = phi i32* [ %elem, %entry ], [ %incdec.ptr, %while.body "
1476 "]\n"
1477 " %tobool = icmp eq i32* %elem.addr.0, null\n"
1478 " br i1 %tobool, label %while.end, label %while.body\n"
1479 "while.body:\n"
1480 " %incdec.ptr = getelementptr inbounds i32, i32* %elem.addr.0, i64 1\n"
1481 " br label %while.cond\n"
1482 "while.end:\n"
1483 " ret void\n"
1484 "}\n";
1485
1486 // Parse the module.
1487 LLVMContext Context;
1488 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1489
1490 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1491 Function::iterator FI = F.begin();
1492 // First basic block is entry - skip it.
1493 BasicBlock *Header = &*(++FI);
1494 assert(Header->getName() == "while.cond");
1495 Loop *L = LI.getLoopFor(Header);
1496 EXPECT_NE(L, nullptr);
1497
1498 // This loop is in simplified form.
1499 EXPECT_TRUE(L->isLoopSimplifyForm());
1500
1501 // This loop is not rotated.
1502 EXPECT_FALSE(L->isRotatedForm());
1503 });
1504 }
1505
TEST(LoopInfoTest,LoopUserBranch)1506 TEST(LoopInfoTest, LoopUserBranch) {
1507 const char *ModuleStr =
1508 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
1509 "define void @foo(i32* %B, i64 signext %nx, i1 %cond) {\n"
1510 "entry:\n"
1511 " br i1 %cond, label %bb, label %guard\n"
1512 "guard:\n"
1513 " %cmp.guard = icmp slt i64 0, %nx\n"
1514 " br i1 %cmp.guard, label %for.i.preheader, label %for.end\n"
1515 "for.i.preheader:\n"
1516 " br label %for.i\n"
1517 "for.i:\n"
1518 " %i = phi i64 [ 0, %for.i.preheader ], [ %inc13, %for.i ]\n"
1519 " %Bi = getelementptr inbounds i32, i32* %B, i64 %i\n"
1520 " store i32 0, i32* %Bi, align 4\n"
1521 " %inc13 = add nsw i64 %i, 1\n"
1522 " %cmp = icmp slt i64 %inc13, %nx\n"
1523 " br i1 %cmp, label %for.i, label %for.i.exit\n"
1524 "for.i.exit:\n"
1525 " br label %bb\n"
1526 "bb:\n"
1527 " br label %for.end\n"
1528 "for.end:\n"
1529 " ret void\n"
1530 "}\n";
1531
1532 // Parse the module.
1533 LLVMContext Context;
1534 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1535
1536 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1537 Function::iterator FI = F.begin();
1538 FI = ++FI;
1539 assert(FI->getName() == "guard");
1540
1541 FI = ++FI;
1542 BasicBlock *Header = &*(++FI);
1543 assert(Header->getName() == "for.i");
1544
1545 Loop *L = LI.getLoopFor(Header);
1546 EXPECT_NE(L, nullptr);
1547
1548 // L should not have a guard branch
1549 EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
1550 });
1551 }
1552
TEST(LoopInfoTest,LoopInductionVariable)1553 TEST(LoopInfoTest, LoopInductionVariable) {
1554 const char *ModuleStr =
1555 "define i32 @foo(i32* %addr) {\n"
1556 "entry:\n"
1557 " br label %for.body\n"
1558 "for.body:\n"
1559 " %sum.08 = phi i32 [ 0, %entry ], [ %add, %for.body ]\n"
1560 " %addr.addr.06 = phi i32* [ %addr, %entry ], [ %incdec.ptr, %for.body "
1561 "]\n"
1562 " %count.07 = phi i32 [ 6000, %entry ], [ %dec, %for.body ]\n"
1563 " %0 = load i32, i32* %addr.addr.06, align 4\n"
1564 " %add = add nsw i32 %0, %sum.08\n"
1565 " %dec = add nsw i32 %count.07, -1\n"
1566 " %incdec.ptr = getelementptr inbounds i32, i32* %addr.addr.06, i64 1\n"
1567 " %cmp = icmp ugt i32 %count.07, 1\n"
1568 " br i1 %cmp, label %for.body, label %for.end\n"
1569 "for.end:\n"
1570 " %cmp1 = icmp eq i32 %add, -1\n"
1571 " %conv = zext i1 %cmp1 to i32\n"
1572 " ret i32 %conv\n"
1573 "}\n";
1574
1575 // Parse the module.
1576 LLVMContext Context;
1577 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1578
1579 runWithLoopInfoPlus(
1580 *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1581 Function::iterator FI = F.begin();
1582 BasicBlock *Header = &*(++FI);
1583 Loop *L = LI.getLoopFor(Header);
1584 EXPECT_NE(L, nullptr);
1585 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "count.07");
1586 });
1587 }
1588
1589 // Test that we correctly identify tokens breaching LCSSA form.
TEST(LoopInfoTest,TokenLCSSA)1590 TEST(LoopInfoTest, TokenLCSSA) {
1591 const char *ModuleStr =
1592 "define void @test() gc \"statepoint-example\" {\n"
1593 "entry:\n"
1594 " br label %outer_loop\n"
1595 "outer_loop:\n"
1596 " br label %inner_loop\n"
1597 "inner_loop:\n"
1598 " %token = call token (i64, i32, i8 addrspace(1)* (i64, i32, i32, "
1599 "i32)*, i32, i32, ...) "
1600 "@llvm.experimental.gc.statepoint.p0f_p1i8i64i32i32i32f(i64 2882400000, "
1601 "i32 0, i8 addrspace(1)* (i64, i32, i32, i32)* nonnull elementtype(i8 "
1602 "addrspace(1)* (i64, i32, i32, i32)) @foo, i32 4, i32 0, i64 undef, i32 "
1603 "5, i32 5, i32 undef, i32 0, i32 0) [ \"deopt\"(), \"gc-live\"(i8 "
1604 "addrspace(1)* undef) ]\n"
1605 " br i1 undef, label %inner_loop, label %outer_backedge\n"
1606 "outer_backedge:\n"
1607 " br i1 undef, label %outer_loop, label %exit\n"
1608 "exit:\n"
1609 " %tmp35 = call coldcc i8 addrspace(1)* "
1610 "@llvm.experimental.gc.relocate.p1i8(token %token, i32 0, i32 0) ; "
1611 "(undef, undef)\n"
1612 " ret void\n"
1613 "}\n"
1614 "declare i8 addrspace(1)* @foo(i64, i32, i32, i32)\n"
1615 "declare i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token, i32 "
1616 "immarg, i32 immarg) #0\n"
1617 "declare token "
1618 "@llvm.experimental.gc.statepoint.p0f_p1i8i64i32i32i32f(i64 immarg, i32 "
1619 "immarg, i8 addrspace(1)* (i64, i32, i32, i32)*, i32 immarg, i32 immarg, "
1620 "...)\n"
1621 "attributes #0 = { nounwind readnone }\n";
1622
1623 // Parse the module.
1624 LLVMContext Context;
1625 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1626
1627 runWithLoopInfoPlus(*M, "test",
1628 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1629 Function::iterator FI = F.begin();
1630 BasicBlock *OuterHeader = &*(++FI);
1631 Loop *OuterLoop = LI.getLoopFor(OuterHeader);
1632 BasicBlock *InnerHeader = &*(++FI);
1633 Loop *InnerLoop = LI.getLoopFor(InnerHeader);
1634 EXPECT_NE(OuterLoop, nullptr);
1635 EXPECT_NE(InnerLoop, nullptr);
1636 DominatorTree DT(F);
1637 EXPECT_TRUE(OuterLoop->isLCSSAForm(DT, /*IgnoreTokens*/ true));
1638 EXPECT_FALSE(OuterLoop->isLCSSAForm(DT, /*IgnoreTokens*/ false));
1639 EXPECT_TRUE(InnerLoop->isLCSSAForm(DT, /*IgnoreTokens*/ true));
1640 EXPECT_FALSE(InnerLoop->isLCSSAForm(DT, /*IgnoreTokens*/ false));
1641 EXPECT_TRUE(
1642 OuterLoop->isRecursivelyLCSSAForm(DT, LI, /*IgnoreTokens*/ true));
1643 EXPECT_FALSE(
1644 OuterLoop->isRecursivelyLCSSAForm(DT, LI, /*IgnoreTokens*/ false));
1645 EXPECT_TRUE(
1646 InnerLoop->isRecursivelyLCSSAForm(DT, LI, /*IgnoreTokens*/ true));
1647 EXPECT_FALSE(
1648 InnerLoop->isRecursivelyLCSSAForm(DT, LI, /*IgnoreTokens*/ false));
1649 });
1650 }
1651