xref: /llvm-project/llvm/unittests/Analysis/LoopInfoTest.cpp (revision 8ee361ebe5ebada5c303b9aa93fecde9e4bec02a)
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
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.
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 
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.
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.
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 
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 
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       });
289 }
290 
291 TEST(LoopInfoTest, LoopWithInverseGuardSuccs) {
292   const char *ModuleStr =
293       "define void @foo(i32* %A, i32 %ub) {\n"
294       "entry:\n"
295       "  %guardcmp = icmp sge i32 0, %ub\n"
296       "  br i1 %guardcmp, label %for.end, label %for.preheader\n"
297       "for.preheader:\n"
298       "  br label %for.body\n"
299       "for.body:\n"
300       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
301       "  %idxprom = sext i32 %i to i64\n"
302       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
303       "  store i32 %i, i32* %arrayidx, align 4\n"
304       "  %inc = add nsw i32 %i, 1\n"
305       "  %cmp = icmp slt i32 %inc, %ub\n"
306       "  br i1 %cmp, label %for.body, label %for.exit\n"
307       "for.exit:\n"
308       "  br label %for.end\n"
309       "for.end:\n"
310       "  ret void\n"
311       "}\n";
312 
313   // Parse the module.
314   LLVMContext Context;
315   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
316 
317   runWithLoopInfoPlus(
318       *M, "foo",
319       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
320         Function::iterator FI = F.begin();
321         BasicBlock *Entry = &*(FI);
322         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
323         // First two basic block are entry and for.preheader - skip them.
324         ++FI;
325         BasicBlock *Header = &*(++FI);
326         assert(Header->getName() == "for.body");
327         Loop *L = LI.getLoopFor(Header);
328         EXPECT_NE(L, nullptr);
329 
330         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
331         EXPECT_NE(Bounds, None);
332         ConstantInt *InitialIVValue =
333             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
334         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
335         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
336         ConstantInt *StepValue =
337             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
338         EXPECT_TRUE(StepValue && StepValue->isOne());
339         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
340         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
341         EXPECT_EQ(Bounds->getDirection(),
342                   Loop::LoopBounds::Direction::Increasing);
343         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
344         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
345         EXPECT_TRUE(L->isGuarded());
346       });
347 }
348 
349 TEST(LoopInfoTest, LoopWithSwappedGuardCmp) {
350   const char *ModuleStr =
351       "define void @foo(i32* %A, i32 %ub) {\n"
352       "entry:\n"
353       "  %guardcmp = icmp sgt i32 %ub, 0\n"
354       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
355       "for.preheader:\n"
356       "  br label %for.body\n"
357       "for.body:\n"
358       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
359       "  %idxprom = sext i32 %i to i64\n"
360       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
361       "  store i32 %i, i32* %arrayidx, align 4\n"
362       "  %inc = add nsw i32 %i, 1\n"
363       "  %cmp = icmp sge i32 %inc, %ub\n"
364       "  br i1 %cmp, label %for.exit, label %for.body\n"
365       "for.exit:\n"
366       "  br label %for.end\n"
367       "for.end:\n"
368       "  ret void\n"
369       "}\n";
370 
371   // Parse the module.
372   LLVMContext Context;
373   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
374 
375   runWithLoopInfoPlus(
376       *M, "foo",
377       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
378         Function::iterator FI = F.begin();
379         BasicBlock *Entry = &*(FI);
380         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
381         // First two basic block are entry and for.preheader - skip them.
382         ++FI;
383         BasicBlock *Header = &*(++FI);
384         assert(Header->getName() == "for.body");
385         Loop *L = LI.getLoopFor(Header);
386         EXPECT_NE(L, nullptr);
387 
388         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
389         EXPECT_NE(Bounds, None);
390         ConstantInt *InitialIVValue =
391             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
392         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
393         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
394         ConstantInt *StepValue =
395             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
396         EXPECT_TRUE(StepValue && StepValue->isOne());
397         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
398         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
399         EXPECT_EQ(Bounds->getDirection(),
400                   Loop::LoopBounds::Direction::Increasing);
401         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
402         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
403         EXPECT_TRUE(L->isGuarded());
404       });
405 }
406 
407 TEST(LoopInfoTest, LoopWithInverseLatchSuccs) {
408   const char *ModuleStr =
409       "define void @foo(i32* %A, i32 %ub) {\n"
410       "entry:\n"
411       "  %guardcmp = icmp slt i32 0, %ub\n"
412       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
413       "for.preheader:\n"
414       "  br label %for.body\n"
415       "for.body:\n"
416       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
417       "  %idxprom = sext i32 %i to i64\n"
418       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
419       "  store i32 %i, i32* %arrayidx, align 4\n"
420       "  %inc = add nsw i32 %i, 1\n"
421       "  %cmp = icmp sge i32 %inc, %ub\n"
422       "  br i1 %cmp, label %for.exit, label %for.body\n"
423       "for.exit:\n"
424       "  br label %for.end\n"
425       "for.end:\n"
426       "  ret void\n"
427       "}\n";
428 
429   // Parse the module.
430   LLVMContext Context;
431   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
432 
433   runWithLoopInfoPlus(
434       *M, "foo",
435       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
436         Function::iterator FI = F.begin();
437         BasicBlock *Entry = &*(FI);
438         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
439         // First two basic block are entry and for.preheader - skip them.
440         ++FI;
441         BasicBlock *Header = &*(++FI);
442         assert(Header->getName() == "for.body");
443         Loop *L = LI.getLoopFor(Header);
444         EXPECT_NE(L, nullptr);
445 
446         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
447         EXPECT_NE(Bounds, None);
448         ConstantInt *InitialIVValue =
449             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
450         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
451         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
452         ConstantInt *StepValue =
453             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
454         EXPECT_TRUE(StepValue && StepValue->isOne());
455         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
456         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
457         EXPECT_EQ(Bounds->getDirection(),
458                   Loop::LoopBounds::Direction::Increasing);
459         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
460         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
461         EXPECT_TRUE(L->isGuarded());
462       });
463 }
464 
465 TEST(LoopInfoTest, LoopWithLatchCmpNE) {
466   const char *ModuleStr =
467       "define void @foo(i32* %A, i32 %ub) {\n"
468       "entry:\n"
469       "  %guardcmp = icmp slt i32 0, %ub\n"
470       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
471       "for.preheader:\n"
472       "  br label %for.body\n"
473       "for.body:\n"
474       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
475       "  %idxprom = sext i32 %i to i64\n"
476       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
477       "  store i32 %i, i32* %arrayidx, align 4\n"
478       "  %inc = add nsw i32 %i, 1\n"
479       "  %cmp = icmp ne i32 %i, %ub\n"
480       "  br i1 %cmp, label %for.body, label %for.exit\n"
481       "for.exit:\n"
482       "  br label %for.end\n"
483       "for.end:\n"
484       "  ret void\n"
485       "}\n";
486 
487   // Parse the module.
488   LLVMContext Context;
489   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
490 
491   runWithLoopInfoPlus(
492       *M, "foo",
493       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
494         Function::iterator FI = F.begin();
495         BasicBlock *Entry = &*(FI);
496         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
497         // First two basic block are entry and for.preheader - skip them.
498         ++FI;
499         BasicBlock *Header = &*(++FI);
500         assert(Header->getName() == "for.body");
501         Loop *L = LI.getLoopFor(Header);
502         EXPECT_NE(L, nullptr);
503 
504         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
505         EXPECT_NE(Bounds, None);
506         ConstantInt *InitialIVValue =
507             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
508         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
509         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
510         ConstantInt *StepValue =
511             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
512         EXPECT_TRUE(StepValue && StepValue->isOne());
513         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
514         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
515         EXPECT_EQ(Bounds->getDirection(),
516                   Loop::LoopBounds::Direction::Increasing);
517         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
518         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
519         EXPECT_TRUE(L->isGuarded());
520       });
521 }
522 
523 TEST(LoopInfoTest, LoopWithGuardCmpSLE) {
524   const char *ModuleStr =
525       "define void @foo(i32* %A, i32 %ub) {\n"
526       "entry:\n"
527       "  %ubPlusOne = add i32 %ub, 1\n"
528       "  %guardcmp = icmp sle i32 0, %ub\n"
529       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
530       "for.preheader:\n"
531       "  br label %for.body\n"
532       "for.body:\n"
533       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
534       "  %idxprom = sext i32 %i to i64\n"
535       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
536       "  store i32 %i, i32* %arrayidx, align 4\n"
537       "  %inc = add nsw i32 %i, 1\n"
538       "  %cmp = icmp ne i32 %i, %ubPlusOne\n"
539       "  br i1 %cmp, label %for.body, label %for.exit\n"
540       "for.exit:\n"
541       "  br label %for.end\n"
542       "for.end:\n"
543       "  ret void\n"
544       "}\n";
545 
546   // Parse the module.
547   LLVMContext Context;
548   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
549 
550   runWithLoopInfoPlus(
551       *M, "foo",
552       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
553         Function::iterator FI = F.begin();
554         BasicBlock *Entry = &*(FI);
555         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
556         // First two basic block are entry and for.preheader - skip them.
557         ++FI;
558         BasicBlock *Header = &*(++FI);
559         assert(Header->getName() == "for.body");
560         Loop *L = LI.getLoopFor(Header);
561         EXPECT_NE(L, nullptr);
562 
563         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
564         EXPECT_NE(Bounds, None);
565         ConstantInt *InitialIVValue =
566             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
567         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
568         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
569         ConstantInt *StepValue =
570             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
571         EXPECT_TRUE(StepValue && StepValue->isOne());
572         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ubPlusOne");
573         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
574         EXPECT_EQ(Bounds->getDirection(),
575                   Loop::LoopBounds::Direction::Increasing);
576         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
577         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
578         EXPECT_TRUE(L->isGuarded());
579       });
580 }
581 
582 TEST(LoopInfoTest, LoopNonConstantStep) {
583   const char *ModuleStr =
584       "define void @foo(i32* %A, i32 %ub, i32 %step) {\n"
585       "entry:\n"
586       "  %guardcmp = icmp slt i32 0, %ub\n"
587       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
588       "for.preheader:\n"
589       "  br label %for.body\n"
590       "for.body:\n"
591       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
592       "  %idxprom = zext i32 %i to i64\n"
593       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
594       "  store i32 %i, i32* %arrayidx, align 4\n"
595       "  %inc = add nsw i32 %i, %step\n"
596       "  %cmp = icmp slt i32 %inc, %ub\n"
597       "  br i1 %cmp, label %for.body, label %for.exit\n"
598       "for.exit:\n"
599       "  br label %for.end\n"
600       "for.end:\n"
601       "  ret void\n"
602       "}\n";
603 
604   // Parse the module.
605   LLVMContext Context;
606   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
607 
608   runWithLoopInfoPlus(
609       *M, "foo",
610       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
611         Function::iterator FI = F.begin();
612         BasicBlock *Entry = &*(FI);
613         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
614         // First two basic block are entry and for.preheader - skip them.
615         ++FI;
616         BasicBlock *Header = &*(++FI);
617         assert(Header->getName() == "for.body");
618         Loop *L = LI.getLoopFor(Header);
619         EXPECT_NE(L, nullptr);
620 
621         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
622         EXPECT_NE(Bounds, None);
623         ConstantInt *InitialIVValue =
624             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
625         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
626         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
627         EXPECT_EQ(Bounds->getStepValue()->getName(), "step");
628         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
629         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
630         EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown);
631         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
632         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
633         EXPECT_TRUE(L->isGuarded());
634       });
635 }
636 
637 TEST(LoopInfoTest, LoopUnsignedBounds) {
638   const char *ModuleStr =
639       "define void @foo(i32* %A, i32 %ub) {\n"
640       "entry:\n"
641       "  %guardcmp = icmp ult i32 0, %ub\n"
642       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
643       "for.preheader:\n"
644       "  br label %for.body\n"
645       "for.body:\n"
646       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
647       "  %idxprom = zext i32 %i to i64\n"
648       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
649       "  store i32 %i, i32* %arrayidx, align 4\n"
650       "  %inc = add i32 %i, 1\n"
651       "  %cmp = icmp ult i32 %inc, %ub\n"
652       "  br i1 %cmp, label %for.body, label %for.exit\n"
653       "for.exit:\n"
654       "  br label %for.end\n"
655       "for.end:\n"
656       "  ret void\n"
657       "}\n";
658 
659   // Parse the module.
660   LLVMContext Context;
661   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
662 
663   runWithLoopInfoPlus(
664       *M, "foo",
665       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
666         Function::iterator FI = F.begin();
667         BasicBlock *Entry = &*(FI);
668         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
669         // First two basic block are entry and for.preheader - skip them.
670         ++FI;
671         BasicBlock *Header = &*(++FI);
672         assert(Header->getName() == "for.body");
673         Loop *L = LI.getLoopFor(Header);
674         EXPECT_NE(L, nullptr);
675 
676         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
677         EXPECT_NE(Bounds, None);
678         ConstantInt *InitialIVValue =
679             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
680         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
681         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
682         ConstantInt *StepValue =
683             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
684         EXPECT_TRUE(StepValue && StepValue->isOne());
685         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
686         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_ULT);
687         EXPECT_EQ(Bounds->getDirection(),
688                   Loop::LoopBounds::Direction::Increasing);
689         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
690         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
691         EXPECT_TRUE(L->isGuarded());
692       });
693 }
694 
695 TEST(LoopInfoTest, DecreasingLoop) {
696   const char *ModuleStr =
697       "define void @foo(i32* %A, i32 %ub) {\n"
698       "entry:\n"
699       "  %guardcmp = icmp slt i32 0, %ub\n"
700       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
701       "for.preheader:\n"
702       "  br label %for.body\n"
703       "for.body:\n"
704       "  %i = phi i32 [ %ub, %for.preheader ], [ %inc, %for.body ]\n"
705       "  %idxprom = sext i32 %i to i64\n"
706       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
707       "  store i32 %i, i32* %arrayidx, align 4\n"
708       "  %inc = sub nsw i32 %i, 1\n"
709       "  %cmp = icmp sgt i32 %inc, 0\n"
710       "  br i1 %cmp, label %for.body, label %for.exit\n"
711       "for.exit:\n"
712       "  br label %for.end\n"
713       "for.end:\n"
714       "  ret void\n"
715       "}\n";
716 
717   // Parse the module.
718   LLVMContext Context;
719   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
720 
721   runWithLoopInfoPlus(
722       *M, "foo",
723       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
724         Function::iterator FI = F.begin();
725         BasicBlock *Entry = &*(FI);
726         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
727         // First two basic block are entry and for.preheader - skip them.
728         ++FI;
729         BasicBlock *Header = &*(++FI);
730         assert(Header->getName() == "for.body");
731         Loop *L = LI.getLoopFor(Header);
732         EXPECT_NE(L, nullptr);
733 
734         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
735         EXPECT_NE(Bounds, None);
736         EXPECT_EQ(Bounds->getInitialIVValue().getName(), "ub");
737         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
738         ConstantInt *StepValue =
739             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
740         EXPECT_EQ(StepValue, nullptr);
741         ConstantInt *FinalIVValue =
742             dyn_cast<ConstantInt>(&Bounds->getFinalIVValue());
743         EXPECT_TRUE(FinalIVValue && FinalIVValue->isZero());
744         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SGT);
745         EXPECT_EQ(Bounds->getDirection(),
746                   Loop::LoopBounds::Direction::Decreasing);
747         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
748         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
749         EXPECT_TRUE(L->isGuarded());
750       });
751 }
752 
753 TEST(LoopInfoTest, CannotFindDirection) {
754   const char *ModuleStr =
755       "define void @foo(i32* %A, i32 %ub, i32 %step) {\n"
756       "entry:\n"
757       "  %guardcmp = icmp slt i32 0, %ub\n"
758       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
759       "for.preheader:\n"
760       "  br label %for.body\n"
761       "for.body:\n"
762       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
763       "  %idxprom = sext i32 %i to i64\n"
764       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
765       "  store i32 %i, i32* %arrayidx, align 4\n"
766       "  %inc = add nsw i32 %i, %step\n"
767       "  %cmp = icmp ne i32 %i, %ub\n"
768       "  br i1 %cmp, label %for.body, label %for.exit\n"
769       "for.exit:\n"
770       "  br label %for.end\n"
771       "for.end:\n"
772       "  ret void\n"
773       "}\n";
774 
775   // Parse the module.
776   LLVMContext Context;
777   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
778 
779   runWithLoopInfoPlus(
780       *M, "foo",
781       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
782         Function::iterator FI = F.begin();
783         BasicBlock *Entry = &*(FI);
784         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
785         // First two basic block are entry and for.preheader
786         // - skip them.
787         ++FI;
788         BasicBlock *Header = &*(++FI);
789         assert(Header->getName() == "for.body");
790         Loop *L = LI.getLoopFor(Header);
791         EXPECT_NE(L, nullptr);
792 
793         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
794         EXPECT_NE(Bounds, None);
795         ConstantInt *InitialIVValue =
796             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
797         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
798         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
799         EXPECT_EQ(Bounds->getStepValue()->getName(), "step");
800         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
801         EXPECT_EQ(Bounds->getCanonicalPredicate(),
802                   ICmpInst::BAD_ICMP_PREDICATE);
803         EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown);
804         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
805         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
806         EXPECT_TRUE(L->isGuarded());
807       });
808 }
809 
810 TEST(LoopInfoTest, ZextIndVar) {
811   const char *ModuleStr =
812       "define void @foo(i32* %A, i32 %ub) {\n"
813       "entry:\n"
814       "  %guardcmp = icmp slt i32 0, %ub\n"
815       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
816       "for.preheader:\n"
817       "  br label %for.body\n"
818       "for.body:\n"
819       "  %indvars.iv = phi i64 [ 0, %for.preheader ], [ %indvars.iv.next, %for.body ]\n"
820       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
821       "  %idxprom = sext i32 %i to i64\n"
822       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
823       "  store i32 %i, i32* %arrayidx, align 4\n"
824       "  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n"
825       "  %inc = add nsw i32 %i, 1\n"
826       "  %wide.trip.count = zext i32 %ub to i64\n"
827       "  %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count\n"
828       "  br i1 %exitcond, label %for.body, label %for.exit\n"
829       "for.exit:\n"
830       "  br label %for.end\n"
831       "for.end:\n"
832       "  ret void\n"
833       "}\n";
834 
835   // Parse the module.
836   LLVMContext Context;
837   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
838 
839   runWithLoopInfoPlus(
840       *M, "foo",
841       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
842         Function::iterator FI = F.begin();
843         BasicBlock *Entry = &*(FI);
844         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
845         // First two basic block are entry and for.preheader - skip them.
846         ++FI;
847         BasicBlock *Header = &*(++FI);
848         assert(Header->getName() == "for.body");
849         Loop *L = LI.getLoopFor(Header);
850         EXPECT_NE(L, nullptr);
851 
852         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
853         EXPECT_NE(Bounds, None);
854         ConstantInt *InitialIVValue =
855             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
856         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
857         EXPECT_EQ(Bounds->getStepInst().getName(), "indvars.iv.next");
858         ConstantInt *StepValue =
859             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
860         EXPECT_TRUE(StepValue && StepValue->isOne());
861         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "wide.trip.count");
862         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_NE);
863         EXPECT_EQ(Bounds->getDirection(),
864                   Loop::LoopBounds::Direction::Increasing);
865         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv");
866         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
867         EXPECT_TRUE(L->isGuarded());
868       });
869 }
870 
871 TEST(LoopInfoTest, UnguardedLoop) {
872   const char *ModuleStr =
873       "define void @foo(i32* %A, i32 %ub) {\n"
874       "entry:\n"
875       "  br label %for.body\n"
876       "for.body:\n"
877       "  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n"
878       "  %idxprom = sext i32 %i to i64\n"
879       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
880       "  store i32 %i, i32* %arrayidx, align 4\n"
881       "  %inc = add nsw i32 %i, 1\n"
882       "  %cmp = icmp slt i32 %inc, %ub\n"
883       "  br i1 %cmp, label %for.body, label %for.exit\n"
884       "for.exit:\n"
885       "  br label %for.end\n"
886       "for.end:\n"
887       "  ret void\n"
888       "}\n";
889 
890   // Parse the module.
891   LLVMContext Context;
892   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
893 
894   runWithLoopInfoPlus(
895       *M, "foo",
896       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
897         Function::iterator FI = F.begin();
898         // First basic block is entry - skip it.
899         BasicBlock *Header = &*(++FI);
900         assert(Header->getName() == "for.body");
901         Loop *L = LI.getLoopFor(Header);
902         EXPECT_NE(L, nullptr);
903 
904         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
905         EXPECT_NE(Bounds, None);
906         ConstantInt *InitialIVValue =
907             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
908         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
909         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
910         ConstantInt *StepValue =
911             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
912         EXPECT_TRUE(StepValue && StepValue->isOne());
913         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
914         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
915         EXPECT_EQ(Bounds->getDirection(),
916                   Loop::LoopBounds::Direction::Increasing);
917         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
918         EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
919         EXPECT_FALSE(L->isGuarded());
920       });
921 }
922 
923 TEST(LoopInfoTest, UnguardedLoopWithControlFlow) {
924   const char *ModuleStr =
925       "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
926       "entry:\n"
927       "  br i1 %cond, label %for.preheader, label %for.end\n"
928       "for.preheader:\n"
929       "  br label %for.body\n"
930       "for.body:\n"
931       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
932       "  %idxprom = sext i32 %i to i64\n"
933       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
934       "  store i32 %i, i32* %arrayidx, align 4\n"
935       "  %inc = add nsw i32 %i, 1\n"
936       "  %cmp = icmp slt i32 %inc, %ub\n"
937       "  br i1 %cmp, label %for.body, label %for.exit\n"
938       "for.exit:\n"
939       "  br label %for.end\n"
940       "for.end:\n"
941       "  ret void\n"
942       "}\n";
943 
944   // Parse the module.
945   LLVMContext Context;
946   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
947 
948   runWithLoopInfoPlus(
949       *M, "foo",
950       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
951         Function::iterator FI = F.begin();
952         BasicBlock *Entry = &*(FI);
953         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
954         // First two basic block are entry and for.preheader - skip them.
955         ++FI;
956         BasicBlock *Header = &*(++FI);
957         assert(Header->getName() == "for.body");
958         Loop *L = LI.getLoopFor(Header);
959         EXPECT_NE(L, nullptr);
960 
961         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
962         EXPECT_NE(Bounds, None);
963         ConstantInt *InitialIVValue =
964             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
965         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
966         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
967         ConstantInt *StepValue =
968             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
969         EXPECT_TRUE(StepValue && StepValue->isOne());
970         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
971         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
972         EXPECT_EQ(Bounds->getDirection(),
973                   Loop::LoopBounds::Direction::Increasing);
974         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
975         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
976         EXPECT_TRUE(L->isGuarded());
977       });
978 }
979 
980 TEST(LoopInfoTest, LoopNest) {
981   const char *ModuleStr =
982       "define void @foo(i32* %A, i32 %ub) {\n"
983       "entry:\n"
984       "  %guardcmp = icmp slt i32 0, %ub\n"
985       "  br i1 %guardcmp, label %for.outer.preheader, label %for.end\n"
986       "for.outer.preheader:\n"
987       "  br label %for.outer\n"
988       "for.outer:\n"
989       "  %j = phi i32 [ 0, %for.outer.preheader ], [ %inc.outer, %for.outer.latch ]\n"
990       "  br i1 %guardcmp, label %for.inner.preheader, label %for.outer.latch\n"
991       "for.inner.preheader:\n"
992       "  br label %for.inner\n"
993       "for.inner:\n"
994       "  %i = phi i32 [ 0, %for.inner.preheader ], [ %inc, %for.inner ]\n"
995       "  %idxprom = sext i32 %i to i64\n"
996       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
997       "  store i32 %i, i32* %arrayidx, align 4\n"
998       "  %inc = add nsw i32 %i, 1\n"
999       "  %cmp = icmp slt i32 %inc, %ub\n"
1000       "  br i1 %cmp, label %for.inner, label %for.inner.exit\n"
1001       "for.inner.exit:\n"
1002       "  br label %for.outer.latch\n"
1003       "for.outer.latch:\n"
1004       "  %inc.outer = add nsw i32 %j, 1\n"
1005       "  %cmp.outer = icmp slt i32 %inc.outer, %ub\n"
1006       "  br i1 %cmp.outer, label %for.outer, label %for.outer.exit\n"
1007       "for.outer.exit:\n"
1008       "  br label %for.end\n"
1009       "for.end:\n"
1010       "  ret void\n"
1011       "}\n";
1012 
1013   // Parse the module.
1014   LLVMContext Context;
1015   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1016 
1017   runWithLoopInfoPlus(
1018       *M, "foo",
1019       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1020         Function::iterator FI = F.begin();
1021         BasicBlock *Entry = &*(FI);
1022         BranchInst *OuterGuard = dyn_cast<BranchInst>(Entry->getTerminator());
1023         // First two basic block are entry and for.outer.preheader - skip them.
1024         ++FI;
1025         BasicBlock *Header = &*(++FI);
1026         assert(Header->getName() == "for.outer");
1027         BranchInst *InnerGuard = dyn_cast<BranchInst>(Header->getTerminator());
1028         Loop *L = LI.getLoopFor(Header);
1029         EXPECT_NE(L, nullptr);
1030 
1031         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1032         EXPECT_NE(Bounds, None);
1033         ConstantInt *InitialIVValue =
1034             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1035         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1036         EXPECT_EQ(Bounds->getStepInst().getName(), "inc.outer");
1037         ConstantInt *StepValue =
1038             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1039         EXPECT_TRUE(StepValue && StepValue->isOne());
1040         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1041         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1042         EXPECT_EQ(Bounds->getDirection(),
1043                   Loop::LoopBounds::Direction::Increasing);
1044         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "j");
1045         EXPECT_EQ(L->getLoopGuardBranch(), OuterGuard);
1046         EXPECT_TRUE(L->isGuarded());
1047 
1048         // Next two basic blocks are for.outer and for.inner.preheader - skip
1049         // them.
1050         ++FI;
1051         Header = &*(++FI);
1052         assert(Header->getName() == "for.inner");
1053         L = LI.getLoopFor(Header);
1054         EXPECT_NE(L, nullptr);
1055 
1056         Optional<Loop::LoopBounds> InnerBounds = L->getBounds(SE);
1057         EXPECT_NE(InnerBounds, None);
1058         InitialIVValue =
1059             dyn_cast<ConstantInt>(&InnerBounds->getInitialIVValue());
1060         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1061         EXPECT_EQ(InnerBounds->getStepInst().getName(), "inc");
1062         StepValue = dyn_cast_or_null<ConstantInt>(InnerBounds->getStepValue());
1063         EXPECT_TRUE(StepValue && StepValue->isOne());
1064         EXPECT_EQ(InnerBounds->getFinalIVValue().getName(), "ub");
1065         EXPECT_EQ(InnerBounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1066         EXPECT_EQ(InnerBounds->getDirection(),
1067                   Loop::LoopBounds::Direction::Increasing);
1068         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1069         EXPECT_EQ(L->getLoopGuardBranch(), InnerGuard);
1070         EXPECT_TRUE(L->isGuarded());
1071       });
1072 }
1073 
1074 TEST(LoopInfoTest, AuxiliaryIV) {
1075   const char *ModuleStr =
1076       "define void @foo(i32* %A, i32 %ub) {\n"
1077       "entry:\n"
1078       "  %guardcmp = icmp slt i32 0, %ub\n"
1079       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
1080       "for.preheader:\n"
1081       "  br label %for.body\n"
1082       "for.body:\n"
1083       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
1084       "  %aux = phi i32 [ 0, %for.preheader ], [ %auxinc, %for.body ]\n"
1085       "  %loopvariant = phi i32 [ 0, %for.preheader ], [ %loopvariantinc, %for.body ]\n"
1086       "  %usedoutside = phi i32 [ 0, %for.preheader ], [ %usedoutsideinc, %for.body ]\n"
1087       "  %mulopcode = phi i32 [ 0, %for.preheader ], [ %mulopcodeinc, %for.body ]\n"
1088       "  %idxprom = sext i32 %i to i64\n"
1089       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1090       "  store i32 %i, i32* %arrayidx, align 4\n"
1091       "  %mulopcodeinc = mul nsw i32 %mulopcode, 5\n"
1092       "  %usedoutsideinc = add nsw i32 %usedoutside, 5\n"
1093       "  %loopvariantinc = add nsw i32 %loopvariant, %i\n"
1094       "  %auxinc = add nsw i32 %aux, 5\n"
1095       "  %inc = add nsw i32 %i, 1\n"
1096       "  %cmp = icmp slt i32 %inc, %ub\n"
1097       "  br i1 %cmp, label %for.body, label %for.exit\n"
1098       "for.exit:\n"
1099       "  %lcssa = phi i32 [ %usedoutside, %for.body ]\n"
1100       "  br label %for.end\n"
1101       "for.end:\n"
1102       "  ret void\n"
1103       "}\n";
1104 
1105   // Parse the module.
1106   LLVMContext Context;
1107   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1108 
1109   runWithLoopInfoPlus(
1110       *M, "foo",
1111       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1112         Function::iterator FI = F.begin();
1113         BasicBlock *Entry = &*(FI);
1114         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
1115         // First two basic block are entry and for.preheader - skip them.
1116         ++FI;
1117         BasicBlock *Header = &*(++FI);
1118         assert(Header->getName() == "for.body");
1119         Loop *L = LI.getLoopFor(Header);
1120         EXPECT_NE(L, nullptr);
1121 
1122         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1123         EXPECT_NE(Bounds, None);
1124         ConstantInt *InitialIVValue =
1125             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1126         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1127         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
1128         ConstantInt *StepValue =
1129             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1130         EXPECT_TRUE(StepValue && StepValue->isOne());
1131         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1132         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1133         EXPECT_EQ(Bounds->getDirection(),
1134                   Loop::LoopBounds::Direction::Increasing);
1135         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1136         BasicBlock::iterator II = Header->begin();
1137         PHINode &Instruction_i = cast<PHINode>(*(II));
1138         EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_i, SE));
1139         PHINode &Instruction_aux = cast<PHINode>(*(++II));
1140         EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_aux, SE));
1141         PHINode &Instruction_loopvariant = cast<PHINode>(*(++II));
1142         EXPECT_FALSE(
1143             L->isAuxiliaryInductionVariable(Instruction_loopvariant, SE));
1144         PHINode &Instruction_usedoutside = cast<PHINode>(*(++II));
1145         EXPECT_FALSE(
1146             L->isAuxiliaryInductionVariable(Instruction_usedoutside, SE));
1147         PHINode &Instruction_mulopcode = cast<PHINode>(*(++II));
1148         EXPECT_FALSE(
1149             L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE));
1150         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
1151         EXPECT_TRUE(L->isGuarded());
1152       });
1153 }
1154 
1155 // Examine getUniqueExitBlocks/getUniqueNonLatchExitBlocks functions.
1156 TEST(LoopInfoTest, LoopUniqueExitBlocks) {
1157   const char *ModuleStr =
1158       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
1159       "define void @foo(i32 %n, i1 %cond) {\n"
1160       "entry:\n"
1161       "  br label %for.cond\n"
1162       "for.cond:\n"
1163       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
1164       "  %cmp = icmp slt i32 %i.0, %n\n"
1165       "  br i1 %cond, label %for.inc, label %for.end1\n"
1166       "for.inc:\n"
1167       "  %inc = add nsw i32 %i.0, 1\n"
1168       "  br i1 %cmp, label %for.cond, label %for.end2, !llvm.loop !0\n"
1169       "for.end1:\n"
1170       "  br label %for.end\n"
1171       "for.end2:\n"
1172       "  br label %for.end\n"
1173       "for.end:\n"
1174       "  ret void\n"
1175       "}\n"
1176       "!0 = distinct !{!0, !1}\n"
1177       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
1178 
1179   // Parse the module.
1180   LLVMContext Context;
1181   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1182 
1183   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1184     Function::iterator FI = F.begin();
1185     // First basic block is entry - skip it.
1186     BasicBlock *Header = &*(++FI);
1187     assert(Header->getName() == "for.cond");
1188     Loop *L = LI.getLoopFor(Header);
1189 
1190     SmallVector<BasicBlock *, 2> Exits;
1191     // This loop has 2 unique exits.
1192     L->getUniqueExitBlocks(Exits);
1193     EXPECT_TRUE(Exits.size() == 2);
1194     // And one unique non latch exit.
1195     Exits.clear();
1196     L->getUniqueNonLatchExitBlocks(Exits);
1197     EXPECT_TRUE(Exits.size() == 1);
1198   });
1199 }
1200 
1201 // Regression test for  getUniqueNonLatchExitBlocks functions.
1202 // It should detect the exit if it comes from both latch and non-latch blocks.
1203 TEST(LoopInfoTest, LoopNonLatchUniqueExitBlocks) {
1204   const char *ModuleStr =
1205       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
1206       "define void @foo(i32 %n, i1 %cond) {\n"
1207       "entry:\n"
1208       "  br label %for.cond\n"
1209       "for.cond:\n"
1210       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
1211       "  %cmp = icmp slt i32 %i.0, %n\n"
1212       "  br i1 %cond, label %for.inc, label %for.end\n"
1213       "for.inc:\n"
1214       "  %inc = add nsw i32 %i.0, 1\n"
1215       "  br i1 %cmp, label %for.cond, label %for.end, !llvm.loop !0\n"
1216       "for.end:\n"
1217       "  ret void\n"
1218       "}\n"
1219       "!0 = distinct !{!0, !1}\n"
1220       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
1221 
1222   // Parse the module.
1223   LLVMContext Context;
1224   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1225 
1226   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1227     Function::iterator FI = F.begin();
1228     // First basic block is entry - skip it.
1229     BasicBlock *Header = &*(++FI);
1230     assert(Header->getName() == "for.cond");
1231     Loop *L = LI.getLoopFor(Header);
1232 
1233     SmallVector<BasicBlock *, 2> Exits;
1234     // This loop has 1 unique exit.
1235     L->getUniqueExitBlocks(Exits);
1236     EXPECT_TRUE(Exits.size() == 1);
1237     // And one unique non latch exit.
1238     Exits.clear();
1239     L->getUniqueNonLatchExitBlocks(Exits);
1240     EXPECT_TRUE(Exits.size() == 1);
1241   });
1242 }
1243