1 | //===- IVDescriptorsTest.cpp - IVDescriptors 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/IVDescriptors.h" |
10 | #include "llvm/Analysis/AssumptionCache.h" |
11 | #include "llvm/Analysis/LoopInfo.h" |
12 | #include "llvm/Analysis/ScalarEvolution.h" |
13 | #include "llvm/Analysis/TargetLibraryInfo.h" |
14 | #include "llvm/AsmParser/Parser.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 and scalar evolution for the function and run the Test. |
22 | static void runWithLoopInfoAndSE( |
23 | Module &M, StringRef FuncName, |
24 | function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) { |
25 | auto *F = M.getFunction(Name: FuncName); |
26 | ASSERT_NE(F, nullptr) << "Could not find " << FuncName; |
27 | |
28 | TargetLibraryInfoImpl TLII; |
29 | TargetLibraryInfo TLI(TLII); |
30 | AssumptionCache AC(*F); |
31 | DominatorTree DT(*F); |
32 | LoopInfo LI(DT); |
33 | ScalarEvolution SE(*F, TLI, AC, DT, LI); |
34 | |
35 | Test(*F, LI, SE); |
36 | } |
37 | |
38 | static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) { |
39 | SMDiagnostic Err; |
40 | std::unique_ptr<Module> Mod = parseAssemblyString(AsmString: IR, Err, Context&: C); |
41 | if (!Mod) |
42 | Err.print(ProgName: "IVDescriptorsTests" , S&: errs()); |
43 | return Mod; |
44 | } |
45 | |
46 | // This tests that IVDescriptors can obtain the induction binary operator for |
47 | // integer induction variables. And getExactFPMathInst() correctly return the |
48 | // expected behavior, i.e. no FMF algebra. |
49 | TEST(IVDescriptorsTest, LoopWithSingleLatch) { |
50 | // Parse the module. |
51 | LLVMContext Context; |
52 | |
53 | std::unique_ptr<Module> M = parseIR( |
54 | C&: Context, |
55 | IR: R"(define void @foo(ptr %A, i32 %ub) { |
56 | entry: |
57 | br label %for.body |
58 | for.body: |
59 | %i = phi i32 [ 0, %entry ], [ %inc, %for.body ] |
60 | %idxprom = sext i32 %i to i64 |
61 | %arrayidx = getelementptr inbounds i32, ptr %A, i64 %idxprom |
62 | store i32 %i, ptr %arrayidx, align 4 |
63 | %inc = add nsw i32 %i, 1 |
64 | %cmp = icmp slt i32 %inc, %ub |
65 | br i1 %cmp, label %for.body, label %for.exit |
66 | for.exit: |
67 | br label %for.end |
68 | for.end: |
69 | ret void |
70 | })" |
71 | ); |
72 | |
73 | runWithLoopInfoAndSE( |
74 | M&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
75 | Function::iterator FI = F.begin(); |
76 | // First basic block is entry - skip it. |
77 | BasicBlock * = &*(++FI); |
78 | assert(Header->getName() == "for.body" ); |
79 | Loop *L = LI.getLoopFor(BB: Header); |
80 | EXPECT_NE(L, nullptr); |
81 | PHINode *Inst_i = dyn_cast<PHINode>(Val: &Header->front()); |
82 | assert(Inst_i->getName() == "i" ); |
83 | InductionDescriptor IndDesc; |
84 | bool IsInductionPHI = |
85 | InductionDescriptor::isInductionPHI(Phi: Inst_i, L, SE: &SE, D&: IndDesc); |
86 | EXPECT_TRUE(IsInductionPHI); |
87 | Instruction *Inst_inc = nullptr; |
88 | BasicBlock::iterator BBI = Header->begin(); |
89 | do { |
90 | if ((&*BBI)->getName() == "inc" ) |
91 | Inst_inc = &*BBI; |
92 | ++BBI; |
93 | } while (!Inst_inc); |
94 | assert(Inst_inc->getName() == "inc" ); |
95 | EXPECT_EQ(IndDesc.getInductionBinOp(), Inst_inc); |
96 | EXPECT_EQ(IndDesc.getExactFPMathInst(), nullptr); |
97 | }); |
98 | } |
99 | |
100 | // Depending on how SCEV deals with ptrtoint cast, the step of a phi could be |
101 | // a pointer, and InductionDescriptor used to fail with an assertion. |
102 | // So just check that it doesn't assert. |
103 | TEST(IVDescriptorsTest, LoopWithPtrToInt) { |
104 | // Parse the module. |
105 | LLVMContext Context; |
106 | |
107 | std::unique_ptr<Module> M = parseIR(C&: Context, IR: R"( |
108 | target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64" |
109 | target triple = "thumbv6m-arm-none-eabi" |
110 | |
111 | declare void @widget() |
112 | declare void @wobble(i32) |
113 | |
114 | define void @barney(ptr %arg, ptr %arg18, i32 %arg19) { |
115 | bb: |
116 | %tmp = ptrtoint ptr %arg to i32 |
117 | %tmp20 = ptrtoint ptr %arg18 to i32 |
118 | %tmp21 = or i32 %tmp20, %tmp |
119 | %tmp22 = and i32 %tmp21, 3 |
120 | %tmp23 = icmp eq i32 %tmp22, 0 |
121 | br i1 %tmp23, label %bb24, label %bb25 |
122 | |
123 | bb24: |
124 | tail call void @widget() |
125 | br label %bb34 |
126 | |
127 | bb25: |
128 | %tmp26 = sub i32 %tmp, %tmp20 |
129 | %tmp27 = icmp ult i32 %tmp26, %arg19 |
130 | br i1 %tmp27, label %bb28, label %bb34 |
131 | |
132 | bb28: |
133 | br label %bb29 |
134 | |
135 | bb29: |
136 | %tmp30 = phi i32 [ %tmp31, %bb29 ], [ %arg19, %bb28 ] |
137 | tail call void @wobble(i32 %tmp26) |
138 | %tmp31 = sub i32 %tmp30, %tmp26 |
139 | %tmp32 = icmp ugt i32 %tmp31, %tmp26 |
140 | br i1 %tmp32, label %bb29, label %bb33 |
141 | |
142 | bb33: |
143 | br label %bb34 |
144 | |
145 | bb34: |
146 | ret void |
147 | })" ); |
148 | |
149 | runWithLoopInfoAndSE( |
150 | M&: *M, FuncName: "barney" , Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
151 | Function::iterator FI = F.begin(); |
152 | // First basic block is entry - skip it. |
153 | BasicBlock * = &*(++(++(++(++FI)))); |
154 | assert(Header->getName() == "bb29" ); |
155 | Loop *L = LI.getLoopFor(BB: Header); |
156 | EXPECT_NE(L, nullptr); |
157 | PHINode *Inst_i = dyn_cast<PHINode>(Val: &Header->front()); |
158 | assert(Inst_i->getName() == "tmp30" ); |
159 | InductionDescriptor IndDesc; |
160 | bool IsInductionPHI = |
161 | InductionDescriptor::isInductionPHI(Phi: Inst_i, L, SE: &SE, D&: IndDesc); |
162 | EXPECT_TRUE(IsInductionPHI); |
163 | }); |
164 | } |
165 | |
166 | // This tests that correct identity value is returned for a RecurrenceDescriptor |
167 | // that describes FMin reduction idiom. |
168 | TEST(IVDescriptorsTest, FMinRednIdentity) { |
169 | // Parse the module. |
170 | LLVMContext Context; |
171 | |
172 | std::unique_ptr<Module> M = parseIR(C&: Context, |
173 | IR: R"(define float @foo(ptr %A, i64 %ub) { |
174 | entry: |
175 | br label %for.body |
176 | |
177 | for.body: |
178 | %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ] |
179 | %fmin = phi float [ 1.000000e+00, %entry ], [ %fmin.next, %for.body ] |
180 | %arrayidx = getelementptr inbounds float, ptr %A, i64 %i |
181 | %ld = load float, ptr %arrayidx |
182 | %fmin.cmp = fcmp nnan nsz olt float %fmin, %ld |
183 | %fmin.next = select nnan nsz i1 %fmin.cmp, float %fmin, float %ld |
184 | %i.next = add nsw i64 %i, 1 |
185 | %cmp = icmp slt i64 %i.next, %ub |
186 | br i1 %cmp, label %for.body, label %for.end |
187 | |
188 | for.end: |
189 | %fmin.lcssa = phi float [ %fmin.next, %for.body ] |
190 | ret float %fmin.lcssa |
191 | })" ); |
192 | |
193 | runWithLoopInfoAndSE( |
194 | M&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
195 | Function::iterator FI = F.begin(); |
196 | // First basic block is entry - skip it. |
197 | BasicBlock * = &*(++FI); |
198 | assert(Header->getName() == "for.body" ); |
199 | Loop *L = LI.getLoopFor(BB: Header); |
200 | EXPECT_NE(L, nullptr); |
201 | BasicBlock::iterator BBI = Header->begin(); |
202 | assert((&*BBI)->getName() == "i" ); |
203 | ++BBI; |
204 | PHINode *Phi = dyn_cast<PHINode>(Val: &*BBI); |
205 | assert(Phi->getName() == "fmin" ); |
206 | RecurrenceDescriptor Rdx; |
207 | bool IsRdxPhi = RecurrenceDescriptor::isReductionPHI(Phi, TheLoop: L, RedDes&: Rdx); |
208 | EXPECT_TRUE(IsRdxPhi); |
209 | RecurKind Kind = Rdx.getRecurrenceKind(); |
210 | EXPECT_EQ(Kind, RecurKind::FMin); |
211 | Type *Ty = Phi->getType(); |
212 | Value *Id = Rdx.getRecurrenceIdentity(K: Kind, Tp: Ty, FMF: Rdx.getFastMathFlags()); |
213 | // Identity value for FP min reduction is +Inf. |
214 | EXPECT_EQ(Id, ConstantFP::getInfinity(Ty, false /*Negative*/)); |
215 | }); |
216 | } |
217 | |
218 | // This tests that correct identity value is returned for a RecurrenceDescriptor |
219 | // that describes FMax reduction idiom. |
220 | TEST(IVDescriptorsTest, FMaxRednIdentity) { |
221 | // Parse the module. |
222 | LLVMContext Context; |
223 | |
224 | std::unique_ptr<Module> M = parseIR(C&: Context, |
225 | IR: R"(define float @foo(ptr %A, i64 %ub) { |
226 | entry: |
227 | br label %for.body |
228 | |
229 | for.body: |
230 | %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ] |
231 | %fmax = phi float [ 1.000000e+00, %entry ], [ %fmax.next, %for.body ] |
232 | %arrayidx = getelementptr inbounds float, ptr %A, i64 %i |
233 | %ld = load float, ptr %arrayidx |
234 | %fmax.cmp = fcmp nnan nsz ogt float %fmax, %ld |
235 | %fmax.next = select nnan nsz i1 %fmax.cmp, float %fmax, float %ld |
236 | %i.next = add nsw i64 %i, 1 |
237 | %cmp = icmp slt i64 %i.next, %ub |
238 | br i1 %cmp, label %for.body, label %for.end |
239 | |
240 | for.end: |
241 | %fmax.lcssa = phi float [ %fmax.next, %for.body ] |
242 | ret float %fmax.lcssa |
243 | })" ); |
244 | |
245 | runWithLoopInfoAndSE( |
246 | M&: *M, FuncName: "foo" , Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { |
247 | Function::iterator FI = F.begin(); |
248 | // First basic block is entry - skip it. |
249 | BasicBlock * = &*(++FI); |
250 | assert(Header->getName() == "for.body" ); |
251 | Loop *L = LI.getLoopFor(BB: Header); |
252 | EXPECT_NE(L, nullptr); |
253 | BasicBlock::iterator BBI = Header->begin(); |
254 | assert((&*BBI)->getName() == "i" ); |
255 | ++BBI; |
256 | PHINode *Phi = dyn_cast<PHINode>(Val: &*BBI); |
257 | assert(Phi->getName() == "fmax" ); |
258 | RecurrenceDescriptor Rdx; |
259 | bool IsRdxPhi = RecurrenceDescriptor::isReductionPHI(Phi, TheLoop: L, RedDes&: Rdx); |
260 | EXPECT_TRUE(IsRdxPhi); |
261 | RecurKind Kind = Rdx.getRecurrenceKind(); |
262 | EXPECT_EQ(Kind, RecurKind::FMax); |
263 | Type *Ty = Phi->getType(); |
264 | Value *Id = Rdx.getRecurrenceIdentity(K: Kind, Tp: Ty, FMF: Rdx.getFastMathFlags()); |
265 | // Identity value for FP max reduction is -Inf. |
266 | EXPECT_EQ(Id, ConstantFP::getInfinity(Ty, true /*Negative*/)); |
267 | }); |
268 | } |
269 | |