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(Name: 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(Name: 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(AsmString: 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&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI) { |
81 | Function::iterator FI = F.begin(); |
82 | // First basic block is entry - skip it. |
83 | BasicBlock * = &*(++FI); |
84 | assert(Header->getName() == "for.cond" ); |
85 | Loop *L = LI.getLoopFor(BB: 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&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI) { |
131 | Function::iterator FI = F.begin(); |
132 | // First basic block is entry - skip it. |
133 | BasicBlock * = &*(++FI); |
134 | assert(Header->getName() == "for.cond" ); |
135 | Loop *L = LI.getLoopFor(BB: 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, MDs: {nullptr}); |
146 | // Set operand 0 to refer to the loop id itself. |
147 | NewLoopID->replaceOperandWith(I: 0, New: 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(DomTree: DT); |
190 | |
191 | Function::iterator I = F.begin(); |
192 | ASSERT_EQ("entry" , I->getName()); |
193 | ++I; |
194 | Loop &L_0 = *LI.getLoopFor(BB: &*I++); |
195 | ASSERT_EQ("loop.0" , L_0.getHeader()->getName()); |
196 | Loop &L_0_0 = *LI.getLoopFor(BB: &*I++); |
197 | ASSERT_EQ("loop.0.0" , L_0_0.getHeader()->getName()); |
198 | Loop &L_0_1 = *LI.getLoopFor(BB: &*I++); |
199 | ASSERT_EQ("loop.0.1" , L_0_1.getHeader()->getName()); |
200 | Loop &L_0_2 = *LI.getLoopFor(BB: &*I++); |
201 | ASSERT_EQ("loop.0.2" , L_0_2.getHeader()->getName()); |
202 | Loop &L_1 = *LI.getLoopFor(BB: &*I++); |
203 | ASSERT_EQ("loop.1" , L_1.getHeader()->getName()); |
204 | Loop &L_1_0 = *LI.getLoopFor(BB: &*I++); |
205 | ASSERT_EQ("loop.1.0" , L_1_0.getHeader()->getName()); |
206 | Loop &L_1_1 = *LI.getLoopFor(BB: &*I++); |
207 | ASSERT_EQ("loop.1.1" , L_1_1.getHeader()->getName()); |
208 | Loop &L_1_2 = *LI.getLoopFor(BB: &*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&: *M, FuncName: "foo" , |
262 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
263 | Function::iterator FI = F.begin(); |
264 | BasicBlock *Entry = &*(FI); |
265 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
266 | // First two basic block are entry and for.preheader - skip them. |
267 | ++FI; |
268 | BasicBlock * = &*(++FI); |
269 | assert(Header->getName() == "for.body" ); |
270 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
277 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
278 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
279 | ConstantInt *StepValue = |
280 | dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
321 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
322 | Function::iterator FI = F.begin(); |
323 | BasicBlock *Entry = &*(FI); |
324 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
325 | // First two basic block are entry and for.preheader - skip them. |
326 | ++FI; |
327 | BasicBlock * = &*(++FI); |
328 | assert(Header->getName() == "for.body" ); |
329 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
336 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
337 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
338 | ConstantInt *StepValue = |
339 | dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
380 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
381 | Function::iterator FI = F.begin(); |
382 | BasicBlock *Entry = &*(FI); |
383 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
384 | // First two basic block are entry and for.preheader - skip them. |
385 | ++FI; |
386 | BasicBlock * = &*(++FI); |
387 | assert(Header->getName() == "for.body" ); |
388 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
395 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
396 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
397 | ConstantInt *StepValue = |
398 | dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
439 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
440 | Function::iterator FI = F.begin(); |
441 | BasicBlock *Entry = &*(FI); |
442 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
443 | // First two basic block are entry and for.preheader - skip them. |
444 | ++FI; |
445 | BasicBlock * = &*(++FI); |
446 | assert(Header->getName() == "for.body" ); |
447 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
454 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
455 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
456 | ConstantInt *StepValue = |
457 | dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
498 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
499 | Function::iterator FI = F.begin(); |
500 | BasicBlock *Entry = &*(FI); |
501 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
502 | // First two basic block are entry and for.preheader - skip them. |
503 | ++FI; |
504 | BasicBlock * = &*(++FI); |
505 | assert(Header->getName() == "for.body" ); |
506 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
513 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
514 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
515 | ConstantInt *StepValue = |
516 | dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
558 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
559 | Function::iterator FI = F.begin(); |
560 | BasicBlock *Entry = &*(FI); |
561 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
562 | // First two basic block are entry and for.preheader - skip them. |
563 | ++FI; |
564 | BasicBlock * = &*(++FI); |
565 | assert(Header->getName() == "for.body" ); |
566 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
573 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
574 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
575 | ConstantInt *StepValue = |
576 | dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
617 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
618 | Function::iterator FI = F.begin(); |
619 | BasicBlock *Entry = &*(FI); |
620 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
621 | // First two basic block are entry and for.preheader - skip them. |
622 | ++FI; |
623 | BasicBlock * = &*(++FI); |
624 | assert(Header->getName() == "for.body" ); |
625 | Loop *L = LI.getLoopFor(BB: 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>(Val: &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&: *M, FuncName: "foo" , |
673 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
674 | Function::iterator FI = F.begin(); |
675 | BasicBlock *Entry = &*(FI); |
676 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
677 | // First two basic block are entry and for.preheader - skip them. |
678 | ++FI; |
679 | BasicBlock * = &*(++FI); |
680 | assert(Header->getName() == "for.body" ); |
681 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
688 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
689 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
690 | ConstantInt *StepValue = |
691 | dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
732 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
733 | Function::iterator FI = F.begin(); |
734 | BasicBlock *Entry = &*(FI); |
735 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
736 | // First two basic block are entry and for.preheader - skip them. |
737 | ++FI; |
738 | BasicBlock * = &*(++FI); |
739 | assert(Header->getName() == "for.body" ); |
740 | Loop *L = LI.getLoopFor(BB: 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>(Val: Bounds->getStepValue()); |
749 | EXPECT_EQ(StepValue, nullptr); |
750 | ConstantInt *FinalIVValue = |
751 | dyn_cast<ConstantInt>(Val: &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&: *M, FuncName: "foo" , |
791 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
792 | Function::iterator FI = F.begin(); |
793 | BasicBlock *Entry = &*(FI); |
794 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
795 | // First two basic block are entry and for.preheader |
796 | // - skip them. |
797 | ++FI; |
798 | BasicBlock * = &*(++FI); |
799 | assert(Header->getName() == "for.body" ); |
800 | Loop *L = LI.getLoopFor(BB: 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>(Val: &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&: *M, FuncName: "foo" , |
852 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
853 | Function::iterator FI = F.begin(); |
854 | BasicBlock *Entry = &*(FI); |
855 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
856 | // First two basic block are entry and for.preheader - skip them. |
857 | ++FI; |
858 | BasicBlock * = &*(++FI); |
859 | assert(Header->getName() == "for.body" ); |
860 | Loop *L = LI.getLoopFor(BB: 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>(Val: &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>(Val: 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&: *M, FuncName: "foo" , |
913 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
914 | Function::iterator FI = F.begin(); |
915 | BasicBlock *Entry = &*(FI); |
916 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
917 | // First two basic block are entry and for.preheader - skip them. |
918 | ++FI; |
919 | BasicBlock * = &*(++FI); |
920 | assert(Header->getName() == "for.body" ); |
921 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
928 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
929 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
930 | ConstantInt *StepValue = |
931 | dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
975 | Test: [&](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 * = &*(++FI); |
980 | assert(Header->getName() == "for.body" ); |
981 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
988 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
989 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
990 | ConstantInt *StepValue = |
991 | dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
1028 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
1029 | Function::iterator FI = F.begin(); |
1030 | // First basic block is entry - skip it. |
1031 | BasicBlock * = &*(++FI); |
1032 | assert(Header->getName() == "for.body" ); |
1033 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
1040 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
1041 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
1042 | ConstantInt *StepValue = |
1043 | dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
1083 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
1084 | Function::iterator FI = F.begin(); |
1085 | BasicBlock *Entry = &*(FI); |
1086 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
1087 | // First two basic block are entry and for.preheader - skip them. |
1088 | ++FI; |
1089 | BasicBlock * = &*(++FI); |
1090 | assert(Header->getName() == "for.body" ); |
1091 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
1098 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
1099 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
1100 | ConstantInt *StepValue = |
1101 | dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
1153 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
1154 | Function::iterator FI = F.begin(); |
1155 | BasicBlock *Entry = &*(FI); |
1156 | BranchInst *OuterGuard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
1157 | // First two basic block are entry and for.outer.preheader - skip them. |
1158 | ++FI; |
1159 | BasicBlock * = &*(++FI); |
1160 | assert(Header->getName() == "for.outer" ); |
1161 | BranchInst *InnerGuard = dyn_cast<BranchInst>(Val: Header->getTerminator()); |
1162 | Loop *L = LI.getLoopFor(BB: 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>(Val: &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>(Val: 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(BB: 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>(Val: &InnerBounds->getInitialIVValue()); |
1195 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
1196 | EXPECT_EQ(InnerBounds->getStepInst().getName(), "inc" ); |
1197 | StepValue = dyn_cast_or_null<ConstantInt>(Val: 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&: *M, FuncName: "foo" , |
1247 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
1248 | Function::iterator FI = F.begin(); |
1249 | BasicBlock *Entry = &*(FI); |
1250 | BranchInst *Guard = dyn_cast<BranchInst>(Val: Entry->getTerminator()); |
1251 | // First two basic block are entry and for.preheader - skip them. |
1252 | ++FI; |
1253 | BasicBlock * = &*(++FI); |
1254 | assert(Header->getName() == "for.body" ); |
1255 | Loop *L = LI.getLoopFor(BB: 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>(Val: &Bounds->getInitialIVValue()); |
1262 | EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); |
1263 | EXPECT_EQ(Bounds->getStepInst().getName(), "inc" ); |
1264 | ConstantInt *StepValue = |
1265 | dyn_cast_or_null<ConstantInt>(Val: 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>(Val&: *(II)); |
1274 | EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_i, SE)); |
1275 | PHINode &Instruction_aux = cast<PHINode>(Val&: *(++II)); |
1276 | EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_aux, SE)); |
1277 | PHINode &Instruction_loopvariant = cast<PHINode>(Val&: *(++II)); |
1278 | EXPECT_FALSE( |
1279 | L->isAuxiliaryInductionVariable(Instruction_loopvariant, SE)); |
1280 | PHINode &Instruction_usedoutside = cast<PHINode>(Val&: *(++II)); |
1281 | EXPECT_FALSE( |
1282 | L->isAuxiliaryInductionVariable(Instruction_usedoutside, SE)); |
1283 | PHINode &Instruction_mulopcode = cast<PHINode>(Val&: *(++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&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI) { |
1316 | Function::iterator FI = F.begin(); |
1317 | // First basic block is entry - skip it. |
1318 | BasicBlock * = &*(++FI); |
1319 | assert(Header && "No header" ); |
1320 | Loop *L = LI.getLoopFor(BB: 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&: *M, FuncName: "foo" , |
1359 | Test: [&](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 * = &*(++FI); |
1364 | BasicBlock *Latch = &*(++FI); |
1365 | assert(Header && "No header" ); |
1366 | Loop *L = LI.getLoopFor(BB: 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&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI) { |
1406 | Function::iterator FI = F.begin(); |
1407 | // First basic block is entry - skip it. |
1408 | BasicBlock * = &*(++FI); |
1409 | assert(Header->getName() == "for.cond" ); |
1410 | Loop *L = LI.getLoopFor(BB: Header); |
1411 | |
1412 | SmallVector<BasicBlock *, 2> Exits; |
1413 | // This loop has 2 unique exits. |
1414 | L->getUniqueExitBlocks(ExitBlocks&: Exits); |
1415 | EXPECT_TRUE(Exits.size() == 2); |
1416 | // And one unique non latch exit. |
1417 | Exits.clear(); |
1418 | L->getUniqueNonLatchExitBlocks(ExitBlocks&: 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&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI) { |
1449 | Function::iterator FI = F.begin(); |
1450 | // First basic block is entry - skip it. |
1451 | BasicBlock * = &*(++FI); |
1452 | assert(Header->getName() == "for.cond" ); |
1453 | Loop *L = LI.getLoopFor(BB: Header); |
1454 | |
1455 | SmallVector<BasicBlock *, 2> Exits; |
1456 | // This loop has 1 unique exit. |
1457 | L->getUniqueExitBlocks(ExitBlocks&: Exits); |
1458 | EXPECT_TRUE(Exits.size() == 1); |
1459 | // And one unique non latch exit. |
1460 | Exits.clear(); |
1461 | L->getUniqueNonLatchExitBlocks(ExitBlocks&: 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&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI) { |
1490 | Function::iterator FI = F.begin(); |
1491 | // First basic block is entry - skip it. |
1492 | BasicBlock * = &*(++FI); |
1493 | assert(Header->getName() == "while.cond" ); |
1494 | Loop *L = LI.getLoopFor(BB: 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&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI) { |
1536 | Function::iterator FI = F.begin(); |
1537 | FI = ++FI; |
1538 | assert(FI->getName() == "guard" ); |
1539 | |
1540 | FI = ++FI; |
1541 | BasicBlock * = &*(++FI); |
1542 | assert(Header->getName() == "for.i" ); |
1543 | |
1544 | Loop *L = LI.getLoopFor(BB: 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&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
1580 | Function::iterator FI = F.begin(); |
1581 | BasicBlock * = &*(++FI); |
1582 | Loop *L = LI.getLoopFor(BB: 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&: *M, FuncName: "test" , |
1627 | Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
1628 | Function::iterator FI = F.begin(); |
1629 | BasicBlock * = &*(++FI); |
1630 | Loop *OuterLoop = LI.getLoopFor(BB: OuterHeader); |
1631 | BasicBlock * = &*(++FI); |
1632 | Loop *InnerLoop = LI.getLoopFor(BB: 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 | } |
1650 | |