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