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
19using namespace llvm;
20
21/// Build the loop info and scalar evolution for the function and run the Test.
22static 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
38static 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.
49TEST(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) {
56entry:
57 br label %for.body
58for.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
66for.exit:
67 br label %for.end
68for.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 *Header = &*(++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.
103TEST(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 *Header = &*(++(++(++(++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.
168TEST(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) {
174entry:
175 br label %for.body
176
177for.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
188for.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 *Header = &*(++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.
220TEST(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) {
226entry:
227 br label %for.body
228
229for.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
240for.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 *Header = &*(++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

source code of llvm/unittests/Analysis/IVDescriptorsTest.cpp