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