1//===- ScalarEvolutionsTest.cpp - ScalarEvolution 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/ADT/SmallVector.h"
10#include "llvm/Analysis/AssumptionCache.h"
11#include "llvm/Analysis/LoopInfo.h"
12#include "llvm/Analysis/ScalarEvolutionExpressions.h"
13#include "llvm/Analysis/ScalarEvolutionNormalization.h"
14#include "llvm/Analysis/TargetLibraryInfo.h"
15#include "llvm/AsmParser/Parser.h"
16#include "llvm/IR/Constants.h"
17#include "llvm/IR/Dominators.h"
18#include "llvm/IR/GlobalVariable.h"
19#include "llvm/IR/IRBuilder.h"
20#include "llvm/IR/InstIterator.h"
21#include "llvm/IR/LLVMContext.h"
22#include "llvm/IR/Module.h"
23#include "llvm/IR/Verifier.h"
24#include "llvm/Support/SourceMgr.h"
25#include "gtest/gtest.h"
26
27namespace llvm {
28
29// We use this fixture to ensure that we clean up ScalarEvolution before
30// deleting the PassManager.
31class ScalarEvolutionsTest : public testing::Test {
32protected:
33 LLVMContext Context;
34 Module M;
35 TargetLibraryInfoImpl TLII;
36 TargetLibraryInfo TLI;
37
38 std::unique_ptr<AssumptionCache> AC;
39 std::unique_ptr<DominatorTree> DT;
40 std::unique_ptr<LoopInfo> LI;
41
42 ScalarEvolutionsTest() : M("", Context), TLII(), TLI(TLII) {}
43
44 ScalarEvolution buildSE(Function &F) {
45 AC.reset(p: new AssumptionCache(F));
46 DT.reset(p: new DominatorTree(F));
47 LI.reset(p: new LoopInfo(*DT));
48 return ScalarEvolution(F, TLI, *AC, *DT, *LI);
49 }
50
51 void runWithSE(
52 Module &M, StringRef FuncName,
53 function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {
54 auto *F = M.getFunction(Name: FuncName);
55 ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
56 ScalarEvolution SE = buildSE(F&: *F);
57 Test(*F, *LI, SE);
58 }
59
60static std::optional<APInt> computeConstantDifference(ScalarEvolution &SE,
61 const SCEV *LHS,
62 const SCEV *RHS) {
63 return SE.computeConstantDifference(LHS, RHS);
64}
65
66 static bool matchURem(ScalarEvolution &SE, const SCEV *Expr, const SCEV *&LHS,
67 const SCEV *&RHS) {
68 return SE.matchURem(Expr, LHS, RHS);
69 }
70
71 static bool isImpliedCond(
72 ScalarEvolution &SE, ICmpInst::Predicate Pred, const SCEV *LHS,
73 const SCEV *RHS, ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
74 const SCEV *FoundRHS) {
75 return SE.isImpliedCond(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS);
76 }
77};
78
79TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) {
80 FunctionType *FTy = FunctionType::get(Result: Type::getVoidTy(C&: Context),
81 Params: std::vector<Type *>(), isVarArg: false);
82 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "f", M);
83 BasicBlock *BB = BasicBlock::Create(Context, Name: "entry", Parent: F);
84 ReturnInst::Create(C&: Context, retVal: nullptr, InsertAtEnd: BB);
85
86 Type *Ty = Type::getInt1Ty(C&: Context);
87 Constant *Init = Constant::getNullValue(Ty);
88 Value *V0 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V0");
89 Value *V1 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V1");
90 Value *V2 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V2");
91
92 ScalarEvolution SE = buildSE(F&: *F);
93
94 const SCEV *S0 = SE.getSCEV(V: V0);
95 const SCEV *S1 = SE.getSCEV(V: V1);
96 const SCEV *S2 = SE.getSCEV(V: V2);
97
98 const SCEV *P0 = SE.getAddExpr(LHS: S0, RHS: SE.getConstant(Ty: S0->getType(), V: 2));
99 const SCEV *P1 = SE.getAddExpr(LHS: S1, RHS: SE.getConstant(Ty: S0->getType(), V: 2));
100 const SCEV *P2 = SE.getAddExpr(LHS: S2, RHS: SE.getConstant(Ty: S0->getType(), V: 2));
101
102 auto *M0 = cast<SCEVAddExpr>(Val: P0);
103 auto *M1 = cast<SCEVAddExpr>(Val: P1);
104 auto *M2 = cast<SCEVAddExpr>(Val: P2);
105
106 EXPECT_EQ(cast<SCEVConstant>(M0->getOperand(0))->getValue()->getZExtValue(),
107 2u);
108 EXPECT_EQ(cast<SCEVConstant>(M1->getOperand(0))->getValue()->getZExtValue(),
109 2u);
110 EXPECT_EQ(cast<SCEVConstant>(M2->getOperand(0))->getValue()->getZExtValue(),
111 2u);
112
113 // Before the RAUWs, these are all pointing to separate values.
114 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);
115 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V1);
116 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V2);
117
118 // Do some RAUWs.
119 V2->replaceAllUsesWith(V: V1);
120 V1->replaceAllUsesWith(V: V0);
121
122 // After the RAUWs, these should all be pointing to V0.
123 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);
124 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V0);
125 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V0);
126}
127
128TEST_F(ScalarEvolutionsTest, SimplifiedPHI) {
129 FunctionType *FTy = FunctionType::get(Result: Type::getVoidTy(C&: Context),
130 Params: std::vector<Type *>(), isVarArg: false);
131 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "f", M);
132 BasicBlock *EntryBB = BasicBlock::Create(Context, Name: "entry", Parent: F);
133 BasicBlock *LoopBB = BasicBlock::Create(Context, Name: "loop", Parent: F);
134 BasicBlock *ExitBB = BasicBlock::Create(Context, Name: "exit", Parent: F);
135 BranchInst::Create(IfTrue: LoopBB, InsertAtEnd: EntryBB);
136 BranchInst::Create(IfTrue: LoopBB, IfFalse: ExitBB, Cond: UndefValue::get(T: Type::getInt1Ty(C&: Context)),
137 InsertAtEnd: LoopBB);
138 ReturnInst::Create(C&: Context, retVal: nullptr, InsertAtEnd: ExitBB);
139 auto *Ty = Type::getInt32Ty(C&: Context);
140 auto *PN = PHINode::Create(Ty, NumReservedValues: 2, NameStr: "", InsertBefore: &*LoopBB->begin());
141 PN->addIncoming(V: Constant::getNullValue(Ty), BB: EntryBB);
142 PN->addIncoming(V: UndefValue::get(T: Ty), BB: LoopBB);
143 ScalarEvolution SE = buildSE(F&: *F);
144 auto *S1 = SE.getSCEV(V: PN);
145 auto *S2 = SE.getSCEV(V: PN);
146 auto *ZeroConst = SE.getConstant(Ty, V: 0);
147
148 // At some point, only the first call to getSCEV returned the simplified
149 // SCEVConstant and later calls just returned a SCEVUnknown referencing the
150 // PHI node.
151 EXPECT_EQ(S1, ZeroConst);
152 EXPECT_EQ(S1, S2);
153}
154
155
156static Instruction *getInstructionByName(Function &F, StringRef Name) {
157 for (auto &I : instructions(F))
158 if (I.getName() == Name)
159 return &I;
160 llvm_unreachable("Expected to find instruction!");
161}
162
163static Value *getArgByName(Function &F, StringRef Name) {
164 for (auto &Arg : F.args())
165 if (Arg.getName() == Name)
166 return &Arg;
167 llvm_unreachable("Expected to find instruction!");
168}
169TEST_F(ScalarEvolutionsTest, CommutativeExprOperandOrder) {
170 LLVMContext C;
171 SMDiagnostic Err;
172 std::unique_ptr<Module> M = parseAssemblyString(
173 AsmString: "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
174 " "
175 "@var_0 = external global i32, align 4"
176 "@var_1 = external global i32, align 4"
177 "@var_2 = external global i32, align 4"
178 " "
179 "declare i32 @unknown(i32, i32, i32)"
180 " "
181 "define void @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) "
182 " local_unnamed_addr { "
183 "entry: "
184 " %entrycond = icmp sgt i32 %n, 0 "
185 " br i1 %entrycond, label %loop.ph, label %for.end "
186 " "
187 "loop.ph: "
188 " %a = load i32, i32* %A, align 4 "
189 " %b = load i32, i32* %B, align 4 "
190 " %mul = mul nsw i32 %b, %a "
191 " %iv0.init = getelementptr inbounds i8, i8* %arr, i32 %mul "
192 " br label %loop "
193 " "
194 "loop: "
195 " %iv0 = phi i8* [ %iv0.inc, %loop ], [ %iv0.init, %loop.ph ] "
196 " %iv1 = phi i32 [ %iv1.inc, %loop ], [ 0, %loop.ph ] "
197 " %conv = trunc i32 %iv1 to i8 "
198 " store i8 %conv, i8* %iv0, align 1 "
199 " %iv0.inc = getelementptr inbounds i8, i8* %iv0, i32 %b "
200 " %iv1.inc = add nuw nsw i32 %iv1, 1 "
201 " %exitcond = icmp eq i32 %iv1.inc, %n "
202 " br i1 %exitcond, label %for.end.loopexit, label %loop "
203 " "
204 "for.end.loopexit: "
205 " br label %for.end "
206 " "
207 "for.end: "
208 " ret void "
209 "} "
210 " "
211 "define void @f_2(i32* %X, i32* %Y, i32* %Z) { "
212 " %x = load i32, i32* %X "
213 " %y = load i32, i32* %Y "
214 " %z = load i32, i32* %Z "
215 " ret void "
216 "} "
217 " "
218 "define void @f_3() { "
219 " %x = load i32, i32* @var_0"
220 " %y = load i32, i32* @var_1"
221 " %z = load i32, i32* @var_2"
222 " ret void"
223 "} "
224 " "
225 "define void @f_4(i32 %a, i32 %b, i32 %c) { "
226 " %x = call i32 @unknown(i32 %a, i32 %b, i32 %c)"
227 " %y = call i32 @unknown(i32 %b, i32 %c, i32 %a)"
228 " %z = call i32 @unknown(i32 %c, i32 %a, i32 %b)"
229 " ret void"
230 "} "
231 ,
232 Err, Context&: C);
233
234 assert(M && "Could not parse module?");
235 assert(!verifyModule(*M) && "Must have been well formed!");
236
237 runWithSE(M&: *M, FuncName: "f_1", Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
238 auto *IV0 = getInstructionByName(F, Name: "iv0");
239 auto *IV0Inc = getInstructionByName(F, Name: "iv0.inc");
240
241 auto *FirstExprForIV0 = SE.getSCEV(V: IV0);
242 auto *FirstExprForIV0Inc = SE.getSCEV(V: IV0Inc);
243 auto *SecondExprForIV0 = SE.getSCEV(V: IV0);
244
245 EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0));
246 EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0Inc));
247 EXPECT_TRUE(isa<SCEVAddRecExpr>(SecondExprForIV0));
248 });
249
250 auto CheckCommutativeMulExprs = [&](ScalarEvolution &SE, const SCEV *A,
251 const SCEV *B, const SCEV *C) {
252 EXPECT_EQ(SE.getMulExpr(A, B), SE.getMulExpr(B, A));
253 EXPECT_EQ(SE.getMulExpr(B, C), SE.getMulExpr(C, B));
254 EXPECT_EQ(SE.getMulExpr(A, C), SE.getMulExpr(C, A));
255
256 SmallVector<const SCEV *, 3> Ops0 = {A, B, C};
257 SmallVector<const SCEV *, 3> Ops1 = {A, C, B};
258 SmallVector<const SCEV *, 3> Ops2 = {B, A, C};
259 SmallVector<const SCEV *, 3> Ops3 = {B, C, A};
260 SmallVector<const SCEV *, 3> Ops4 = {C, B, A};
261 SmallVector<const SCEV *, 3> Ops5 = {C, A, B};
262
263 auto *Mul0 = SE.getMulExpr(Ops&: Ops0);
264 auto *Mul1 = SE.getMulExpr(Ops&: Ops1);
265 auto *Mul2 = SE.getMulExpr(Ops&: Ops2);
266 auto *Mul3 = SE.getMulExpr(Ops&: Ops3);
267 auto *Mul4 = SE.getMulExpr(Ops&: Ops4);
268 auto *Mul5 = SE.getMulExpr(Ops&: Ops5);
269
270 EXPECT_EQ(Mul0, Mul1) << "Expected " << *Mul0 << " == " << *Mul1;
271 EXPECT_EQ(Mul1, Mul2) << "Expected " << *Mul1 << " == " << *Mul2;
272 EXPECT_EQ(Mul2, Mul3) << "Expected " << *Mul2 << " == " << *Mul3;
273 EXPECT_EQ(Mul3, Mul4) << "Expected " << *Mul3 << " == " << *Mul4;
274 EXPECT_EQ(Mul4, Mul5) << "Expected " << *Mul4 << " == " << *Mul5;
275 };
276
277 for (StringRef FuncName : {"f_2", "f_3", "f_4"})
278 runWithSE(
279 M&: *M, FuncName, Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
280 CheckCommutativeMulExprs(SE, SE.getSCEV(V: getInstructionByName(F, Name: "x")),
281 SE.getSCEV(V: getInstructionByName(F, Name: "y")),
282 SE.getSCEV(V: getInstructionByName(F, Name: "z")));
283 });
284}
285
286TEST_F(ScalarEvolutionsTest, CompareSCEVComplexity) {
287 FunctionType *FTy =
288 FunctionType::get(Result: Type::getVoidTy(C&: Context), Params: std::vector<Type *>(), isVarArg: false);
289 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "f", M);
290 BasicBlock *EntryBB = BasicBlock::Create(Context, Name: "entry", Parent: F);
291 BasicBlock *LoopBB = BasicBlock::Create(Context, Name: "bb1", Parent: F);
292 BranchInst::Create(IfTrue: LoopBB, InsertAtEnd: EntryBB);
293
294 auto *Ty = Type::getInt32Ty(C&: Context);
295 SmallVector<Instruction*, 8> Muls(8), Acc(8), NextAcc(8);
296
297 Acc[0] = PHINode::Create(Ty, NumReservedValues: 2, NameStr: "", InsertAtEnd: LoopBB);
298 Acc[1] = PHINode::Create(Ty, NumReservedValues: 2, NameStr: "", InsertAtEnd: LoopBB);
299 Acc[2] = PHINode::Create(Ty, NumReservedValues: 2, NameStr: "", InsertAtEnd: LoopBB);
300 Acc[3] = PHINode::Create(Ty, NumReservedValues: 2, NameStr: "", InsertAtEnd: LoopBB);
301 Acc[4] = PHINode::Create(Ty, NumReservedValues: 2, NameStr: "", InsertAtEnd: LoopBB);
302 Acc[5] = PHINode::Create(Ty, NumReservedValues: 2, NameStr: "", InsertAtEnd: LoopBB);
303 Acc[6] = PHINode::Create(Ty, NumReservedValues: 2, NameStr: "", InsertAtEnd: LoopBB);
304 Acc[7] = PHINode::Create(Ty, NumReservedValues: 2, NameStr: "", InsertAtEnd: LoopBB);
305
306 for (int i = 0; i < 20; i++) {
307 Muls[0] = BinaryOperator::CreateMul(V1: Acc[0], V2: Acc[0], Name: "", BB: LoopBB);
308 NextAcc[0] = BinaryOperator::CreateAdd(V1: Muls[0], V2: Acc[4], Name: "", BB: LoopBB);
309 Muls[1] = BinaryOperator::CreateMul(V1: Acc[1], V2: Acc[1], Name: "", BB: LoopBB);
310 NextAcc[1] = BinaryOperator::CreateAdd(V1: Muls[1], V2: Acc[5], Name: "", BB: LoopBB);
311 Muls[2] = BinaryOperator::CreateMul(V1: Acc[2], V2: Acc[2], Name: "", BB: LoopBB);
312 NextAcc[2] = BinaryOperator::CreateAdd(V1: Muls[2], V2: Acc[6], Name: "", BB: LoopBB);
313 Muls[3] = BinaryOperator::CreateMul(V1: Acc[3], V2: Acc[3], Name: "", BB: LoopBB);
314 NextAcc[3] = BinaryOperator::CreateAdd(V1: Muls[3], V2: Acc[7], Name: "", BB: LoopBB);
315
316 Muls[4] = BinaryOperator::CreateMul(V1: Acc[4], V2: Acc[4], Name: "", BB: LoopBB);
317 NextAcc[4] = BinaryOperator::CreateAdd(V1: Muls[4], V2: Acc[0], Name: "", BB: LoopBB);
318 Muls[5] = BinaryOperator::CreateMul(V1: Acc[5], V2: Acc[5], Name: "", BB: LoopBB);
319 NextAcc[5] = BinaryOperator::CreateAdd(V1: Muls[5], V2: Acc[1], Name: "", BB: LoopBB);
320 Muls[6] = BinaryOperator::CreateMul(V1: Acc[6], V2: Acc[6], Name: "", BB: LoopBB);
321 NextAcc[6] = BinaryOperator::CreateAdd(V1: Muls[6], V2: Acc[2], Name: "", BB: LoopBB);
322 Muls[7] = BinaryOperator::CreateMul(V1: Acc[7], V2: Acc[7], Name: "", BB: LoopBB);
323 NextAcc[7] = BinaryOperator::CreateAdd(V1: Muls[7], V2: Acc[3], Name: "", BB: LoopBB);
324 Acc = NextAcc;
325 }
326
327 auto II = LoopBB->begin();
328 for (int i = 0; i < 8; i++) {
329 PHINode *Phi = cast<PHINode>(Val: &*II++);
330 Phi->addIncoming(V: Acc[i], BB: LoopBB);
331 Phi->addIncoming(V: UndefValue::get(T: Ty), BB: EntryBB);
332 }
333
334 BasicBlock *ExitBB = BasicBlock::Create(Context, Name: "bb2", Parent: F);
335 BranchInst::Create(IfTrue: LoopBB, IfFalse: ExitBB, Cond: UndefValue::get(T: Type::getInt1Ty(C&: Context)),
336 InsertAtEnd: LoopBB);
337
338 Acc[0] = BinaryOperator::CreateAdd(V1: Acc[0], V2: Acc[1], Name: "", BB: ExitBB);
339 Acc[1] = BinaryOperator::CreateAdd(V1: Acc[2], V2: Acc[3], Name: "", BB: ExitBB);
340 Acc[2] = BinaryOperator::CreateAdd(V1: Acc[4], V2: Acc[5], Name: "", BB: ExitBB);
341 Acc[3] = BinaryOperator::CreateAdd(V1: Acc[6], V2: Acc[7], Name: "", BB: ExitBB);
342 Acc[0] = BinaryOperator::CreateAdd(V1: Acc[0], V2: Acc[1], Name: "", BB: ExitBB);
343 Acc[1] = BinaryOperator::CreateAdd(V1: Acc[2], V2: Acc[3], Name: "", BB: ExitBB);
344 Acc[0] = BinaryOperator::CreateAdd(V1: Acc[0], V2: Acc[1], Name: "", BB: ExitBB);
345
346 ReturnInst::Create(C&: Context, retVal: nullptr, InsertAtEnd: ExitBB);
347
348 ScalarEvolution SE = buildSE(F&: *F);
349
350 EXPECT_NE(nullptr, SE.getSCEV(Acc[0]));
351}
352
353TEST_F(ScalarEvolutionsTest, CompareValueComplexity) {
354 IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(C&: Context);
355 PointerType *IntPtrPtrTy = PointerType::getUnqual(C&: Context);
356
357 FunctionType *FTy =
358 FunctionType::get(Result: Type::getVoidTy(C&: Context), Params: {IntPtrTy, IntPtrTy}, isVarArg: false);
359 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "f", M);
360 BasicBlock *EntryBB = BasicBlock::Create(Context, Name: "entry", Parent: F);
361
362 Value *X = &*F->arg_begin();
363 Value *Y = &*std::next(x: F->arg_begin());
364
365 const int ValueDepth = 10;
366 for (int i = 0; i < ValueDepth; i++) {
367 X = new LoadInst(IntPtrTy, new IntToPtrInst(X, IntPtrPtrTy, "", EntryBB),
368 "",
369 /*isVolatile*/ false, EntryBB);
370 Y = new LoadInst(IntPtrTy, new IntToPtrInst(Y, IntPtrPtrTy, "", EntryBB),
371 "",
372 /*isVolatile*/ false, EntryBB);
373 }
374
375 auto *MulA = BinaryOperator::CreateMul(V1: X, V2: Y, Name: "", BB: EntryBB);
376 auto *MulB = BinaryOperator::CreateMul(V1: Y, V2: X, Name: "", BB: EntryBB);
377 ReturnInst::Create(C&: Context, retVal: nullptr, InsertAtEnd: EntryBB);
378
379 // This test isn't checking for correctness. Today making A and B resolve to
380 // the same SCEV would require deeper searching in CompareValueComplexity,
381 // which will slow down compilation. However, this test can fail (with LLVM's
382 // behavior still being correct) if we ever have a smarter
383 // CompareValueComplexity that is both fast and more accurate.
384
385 ScalarEvolution SE = buildSE(F&: *F);
386 auto *A = SE.getSCEV(V: MulA);
387 auto *B = SE.getSCEV(V: MulB);
388 EXPECT_NE(A, B);
389}
390
391TEST_F(ScalarEvolutionsTest, SCEVAddExpr) {
392 Type *Ty32 = Type::getInt32Ty(C&: Context);
393 Type *ArgTys[] = {Type::getInt64Ty(C&: Context), Ty32, Ty32, Ty32, Ty32, Ty32};
394
395 FunctionType *FTy =
396 FunctionType::get(Result: Type::getVoidTy(C&: Context), Params: ArgTys, isVarArg: false);
397 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "f", M);
398
399 Argument *A1 = &*F->arg_begin();
400 Argument *A2 = &*(std::next(x: F->arg_begin()));
401 BasicBlock *EntryBB = BasicBlock::Create(Context, Name: "entry", Parent: F);
402
403 Instruction *Trunc = CastInst::CreateTruncOrBitCast(S: A1, Ty: Ty32, Name: "", InsertAtEnd: EntryBB);
404 Instruction *Mul1 = BinaryOperator::CreateMul(V1: Trunc, V2: A2, Name: "", BB: EntryBB);
405 Instruction *Add1 = BinaryOperator::CreateAdd(V1: Mul1, V2: Trunc, Name: "", BB: EntryBB);
406 Mul1 = BinaryOperator::CreateMul(V1: Add1, V2: Trunc, Name: "", BB: EntryBB);
407 Instruction *Add2 = BinaryOperator::CreateAdd(V1: Mul1, V2: Add1, Name: "", BB: EntryBB);
408 // FIXME: The size of this is arbitrary and doesn't seem to change the
409 // result, but SCEV will do quadratic work for these so a large number here
410 // will be extremely slow. We should revisit what and how this is testing
411 // SCEV.
412 for (int i = 0; i < 10; i++) {
413 Mul1 = BinaryOperator::CreateMul(V1: Add2, V2: Add1, Name: "", BB: EntryBB);
414 Add1 = Add2;
415 Add2 = BinaryOperator::CreateAdd(V1: Mul1, V2: Add1, Name: "", BB: EntryBB);
416 }
417
418 ReturnInst::Create(C&: Context, retVal: nullptr, InsertAtEnd: EntryBB);
419 ScalarEvolution SE = buildSE(F&: *F);
420 EXPECT_NE(nullptr, SE.getSCEV(Mul1));
421
422 Argument *A3 = &*(std::next(x: F->arg_begin(), n: 2));
423 Argument *A4 = &*(std::next(x: F->arg_begin(), n: 3));
424 Argument *A5 = &*(std::next(x: F->arg_begin(), n: 4));
425 Argument *A6 = &*(std::next(x: F->arg_begin(), n: 5));
426
427 auto *AddWithNUW = cast<SCEVAddExpr>(Val: SE.getAddExpr(
428 LHS: SE.getAddExpr(LHS: SE.getSCEV(V: A2), RHS: SE.getSCEV(V: A3), Flags: SCEV::FlagNUW),
429 RHS: SE.getConstant(Val: APInt(/*numBits=*/32, 5)), Flags: SCEV::FlagNUW));
430 EXPECT_EQ(AddWithNUW->getNumOperands(), 3u);
431 EXPECT_EQ(AddWithNUW->getNoWrapFlags(), SCEV::FlagNUW);
432
433 auto *AddWithAnyWrap =
434 SE.getAddExpr(LHS: SE.getSCEV(V: A3), RHS: SE.getSCEV(V: A4), Flags: SCEV::FlagAnyWrap);
435 auto *AddWithAnyWrapNUW = cast<SCEVAddExpr>(
436 Val: SE.getAddExpr(LHS: AddWithAnyWrap, RHS: SE.getSCEV(V: A5), Flags: SCEV::FlagNUW));
437 EXPECT_EQ(AddWithAnyWrapNUW->getNumOperands(), 3u);
438 EXPECT_EQ(AddWithAnyWrapNUW->getNoWrapFlags(), SCEV::FlagAnyWrap);
439
440 auto *AddWithNSW = SE.getAddExpr(
441 LHS: SE.getSCEV(V: A2), RHS: SE.getConstant(Val: APInt(32, 99)), Flags: SCEV::FlagNSW);
442 auto *AddWithNSW_NUW = cast<SCEVAddExpr>(
443 Val: SE.getAddExpr(LHS: AddWithNSW, RHS: SE.getSCEV(V: A5), Flags: SCEV::FlagNUW));
444 EXPECT_EQ(AddWithNSW_NUW->getNumOperands(), 3u);
445 EXPECT_EQ(AddWithNSW_NUW->getNoWrapFlags(), SCEV::FlagAnyWrap);
446
447 auto *AddWithNSWNUW =
448 SE.getAddExpr(LHS: SE.getSCEV(V: A2), RHS: SE.getSCEV(V: A4),
449 Flags: ScalarEvolution::setFlags(Flags: SCEV::FlagNUW, OnFlags: SCEV::FlagNSW));
450 auto *AddWithNSWNUW_NUW = cast<SCEVAddExpr>(
451 Val: SE.getAddExpr(LHS: AddWithNSWNUW, RHS: SE.getSCEV(V: A5), Flags: SCEV::FlagNUW));
452 EXPECT_EQ(AddWithNSWNUW_NUW->getNumOperands(), 3u);
453 EXPECT_EQ(AddWithNSWNUW_NUW->getNoWrapFlags(), SCEV::FlagNUW);
454
455 auto *AddWithNSW_NSWNUW = cast<SCEVAddExpr>(
456 Val: SE.getAddExpr(LHS: AddWithNSW, RHS: SE.getSCEV(V: A6),
457 Flags: ScalarEvolution::setFlags(Flags: SCEV::FlagNUW, OnFlags: SCEV::FlagNSW)));
458 EXPECT_EQ(AddWithNSW_NSWNUW->getNumOperands(), 3u);
459 EXPECT_EQ(AddWithNSW_NSWNUW->getNoWrapFlags(), SCEV::FlagAnyWrap);
460}
461
462static Instruction &GetInstByName(Function &F, StringRef Name) {
463 for (auto &I : instructions(F))
464 if (I.getName() == Name)
465 return I;
466 llvm_unreachable("Could not find instructions!");
467}
468
469TEST_F(ScalarEvolutionsTest, SCEVNormalization) {
470 LLVMContext C;
471 SMDiagnostic Err;
472 std::unique_ptr<Module> M = parseAssemblyString(
473 AsmString: "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
474 " "
475 "@var_0 = external global i32, align 4"
476 "@var_1 = external global i32, align 4"
477 "@var_2 = external global i32, align 4"
478 " "
479 "declare i32 @unknown(i32, i32, i32)"
480 " "
481 "define void @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) "
482 " local_unnamed_addr { "
483 "entry: "
484 " br label %loop.ph "
485 " "
486 "loop.ph: "
487 " br label %loop "
488 " "
489 "loop: "
490 " %iv0 = phi i32 [ %iv0.inc, %loop ], [ 0, %loop.ph ] "
491 " %iv1 = phi i32 [ %iv1.inc, %loop ], [ -2147483648, %loop.ph ] "
492 " %iv0.inc = add i32 %iv0, 1 "
493 " %iv1.inc = add i32 %iv1, 3 "
494 " br i1 undef, label %for.end.loopexit, label %loop "
495 " "
496 "for.end.loopexit: "
497 " ret void "
498 "} "
499 " "
500 "define void @f_2(i32 %a, i32 %b, i32 %c, i32 %d) "
501 " local_unnamed_addr { "
502 "entry: "
503 " br label %loop_0 "
504 " "
505 "loop_0: "
506 " br i1 undef, label %loop_0, label %loop_1 "
507 " "
508 "loop_1: "
509 " br i1 undef, label %loop_2, label %loop_1 "
510 " "
511 " "
512 "loop_2: "
513 " br i1 undef, label %end, label %loop_2 "
514 " "
515 "end: "
516 " ret void "
517 "} "
518 ,
519 Err, Context&: C);
520
521 assert(M && "Could not parse module?");
522 assert(!verifyModule(*M) && "Must have been well formed!");
523
524 runWithSE(M&: *M, FuncName: "f_1", Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
525 auto &I0 = GetInstByName(F, Name: "iv0");
526 auto &I1 = *I0.getNextNode();
527
528 auto *S0 = cast<SCEVAddRecExpr>(Val: SE.getSCEV(V: &I0));
529 PostIncLoopSet Loops;
530 Loops.insert(Ptr: S0->getLoop());
531 auto *N0 = normalizeForPostIncUse(S: S0, Loops, SE);
532 auto *D0 = denormalizeForPostIncUse(S: N0, Loops, SE);
533 EXPECT_EQ(S0, D0) << *S0 << " " << *D0;
534
535 auto *S1 = cast<SCEVAddRecExpr>(Val: SE.getSCEV(V: &I1));
536 Loops.clear();
537 Loops.insert(Ptr: S1->getLoop());
538 auto *N1 = normalizeForPostIncUse(S: S1, Loops, SE);
539 auto *D1 = denormalizeForPostIncUse(S: N1, Loops, SE);
540 EXPECT_EQ(S1, D1) << *S1 << " " << *D1;
541 });
542
543 runWithSE(M&: *M, FuncName: "f_2", Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
544 auto *L2 = *LI.begin();
545 auto *L1 = *std::next(x: LI.begin());
546 auto *L0 = *std::next(x: LI.begin(), n: 2);
547
548 auto GetAddRec = [&SE](const Loop *L, std::initializer_list<const SCEV *> Ops) {
549 SmallVector<const SCEV *, 4> OpsCopy(Ops);
550 return SE.getAddRecExpr(Operands&: OpsCopy, L, Flags: SCEV::FlagAnyWrap);
551 };
552
553 auto GetAdd = [&SE](std::initializer_list<const SCEV *> Ops) {
554 SmallVector<const SCEV *, 4> OpsCopy(Ops);
555 return SE.getAddExpr(Ops&: OpsCopy, Flags: SCEV::FlagAnyWrap);
556 };
557
558 // We first populate the AddRecs vector with a few "interesting" SCEV
559 // expressions, and then we go through the list and assert that each
560 // expression in it has an invertible normalization.
561
562 std::vector<const SCEV *> Exprs;
563 {
564 const SCEV *V0 = SE.getSCEV(V: &*F.arg_begin());
565 const SCEV *V1 = SE.getSCEV(V: &*std::next(x: F.arg_begin(), n: 1));
566 const SCEV *V2 = SE.getSCEV(V: &*std::next(x: F.arg_begin(), n: 2));
567 const SCEV *V3 = SE.getSCEV(V: &*std::next(x: F.arg_begin(), n: 3));
568
569 Exprs.push_back(x: GetAddRec(L0, {V0})); // 0
570 Exprs.push_back(x: GetAddRec(L0, {V0, V1})); // 1
571 Exprs.push_back(x: GetAddRec(L0, {V0, V1, V2})); // 2
572 Exprs.push_back(x: GetAddRec(L0, {V0, V1, V2, V3})); // 3
573
574 Exprs.push_back(
575 x: GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[3], Exprs[0]})); // 4
576 Exprs.push_back(
577 x: GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[0], Exprs[3]})); // 5
578 Exprs.push_back(
579 x: GetAddRec(L1, {Exprs[1], Exprs[3], Exprs[3], Exprs[1]})); // 6
580
581 Exprs.push_back(x: GetAdd({Exprs[6], Exprs[3], V2})); // 7
582
583 Exprs.push_back(
584 x: GetAddRec(L2, {Exprs[4], Exprs[3], Exprs[3], Exprs[5]})); // 8
585
586 Exprs.push_back(
587 x: GetAddRec(L2, {Exprs[4], Exprs[6], Exprs[7], Exprs[3], V0})); // 9
588 }
589
590 std::vector<PostIncLoopSet> LoopSets;
591 for (int i = 0; i < 8; i++) {
592 LoopSets.emplace_back();
593 if (i & 1)
594 LoopSets.back().insert(Ptr: L0);
595 if (i & 2)
596 LoopSets.back().insert(Ptr: L1);
597 if (i & 4)
598 LoopSets.back().insert(Ptr: L2);
599 }
600
601 for (const auto &LoopSet : LoopSets)
602 for (auto *S : Exprs) {
603 {
604 auto *N = llvm::normalizeForPostIncUse(S, Loops: LoopSet, SE);
605 auto *D = llvm::denormalizeForPostIncUse(S: N, Loops: LoopSet, SE);
606
607 // Normalization and then denormalizing better give us back the same
608 // value.
609 EXPECT_EQ(S, D) << "S = " << *S << " D = " << *D << " N = " << *N;
610 }
611 {
612 auto *D = llvm::denormalizeForPostIncUse(S, Loops: LoopSet, SE);
613 auto *N = llvm::normalizeForPostIncUse(S: D, Loops: LoopSet, SE);
614
615 // Denormalization and then normalizing better give us back the same
616 // value.
617 EXPECT_EQ(S, N) << "S = " << *S << " N = " << *N;
618 }
619 }
620 });
621}
622
623// Expect the call of getZeroExtendExpr will not cost exponential time.
624TEST_F(ScalarEvolutionsTest, SCEVZeroExtendExpr) {
625 LLVMContext C;
626 SMDiagnostic Err;
627
628 // Generate a function like below:
629 // define void @foo() {
630 // entry:
631 // br label %for.cond
632 //
633 // for.cond:
634 // %0 = phi i64 [ 100, %entry ], [ %dec, %for.inc ]
635 // %cmp = icmp sgt i64 %0, 90
636 // br i1 %cmp, label %for.inc, label %for.cond1
637 //
638 // for.inc:
639 // %dec = add nsw i64 %0, -1
640 // br label %for.cond
641 //
642 // for.cond1:
643 // %1 = phi i64 [ 100, %for.cond ], [ %dec5, %for.inc2 ]
644 // %cmp3 = icmp sgt i64 %1, 90
645 // br i1 %cmp3, label %for.inc2, label %for.cond4
646 //
647 // for.inc2:
648 // %dec5 = add nsw i64 %1, -1
649 // br label %for.cond1
650 //
651 // ......
652 //
653 // for.cond89:
654 // %19 = phi i64 [ 100, %for.cond84 ], [ %dec94, %for.inc92 ]
655 // %cmp93 = icmp sgt i64 %19, 90
656 // br i1 %cmp93, label %for.inc92, label %for.end
657 //
658 // for.inc92:
659 // %dec94 = add nsw i64 %19, -1
660 // br label %for.cond89
661 //
662 // for.end:
663 // %gep = getelementptr i8, i8* null, i64 %dec
664 // %gep6 = getelementptr i8, i8* %gep, i64 %dec5
665 // ......
666 // %gep95 = getelementptr i8, i8* %gep91, i64 %dec94
667 // ret void
668 // }
669 FunctionType *FTy = FunctionType::get(Result: Type::getVoidTy(C&: Context), Params: {}, isVarArg: false);
670 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "foo", M);
671
672 BasicBlock *EntryBB = BasicBlock::Create(Context, Name: "entry", Parent: F);
673 BasicBlock *CondBB = BasicBlock::Create(Context, Name: "for.cond", Parent: F);
674 BasicBlock *EndBB = BasicBlock::Create(Context, Name: "for.end", Parent: F);
675 BranchInst::Create(IfTrue: CondBB, InsertAtEnd: EntryBB);
676 BasicBlock *PrevBB = EntryBB;
677
678 Type *I64Ty = Type::getInt64Ty(C&: Context);
679 Type *I8Ty = Type::getInt8Ty(C&: Context);
680 Type *I8PtrTy = PointerType::getUnqual(C&: Context);
681 Value *Accum = Constant::getNullValue(Ty: I8PtrTy);
682 int Iters = 20;
683 for (int i = 0; i < Iters; i++) {
684 BasicBlock *IncBB = BasicBlock::Create(Context, Name: "for.inc", Parent: F, InsertBefore: EndBB);
685 auto *PN = PHINode::Create(Ty: I64Ty, NumReservedValues: 2, NameStr: "", InsertAtEnd: CondBB);
686 PN->addIncoming(V: ConstantInt::get(Context, V: APInt(64, 100)), BB: PrevBB);
687 auto *Cmp = CmpInst::Create(Op: Instruction::ICmp, Pred: CmpInst::ICMP_SGT, S1: PN,
688 S2: ConstantInt::get(Context, V: APInt(64, 90)), Name: "cmp",
689 InsertAtEnd: CondBB);
690 BasicBlock *NextBB;
691 if (i != Iters - 1)
692 NextBB = BasicBlock::Create(Context, Name: "for.cond", Parent: F, InsertBefore: EndBB);
693 else
694 NextBB = EndBB;
695 BranchInst::Create(IfTrue: IncBB, IfFalse: NextBB, Cond: Cmp, InsertAtEnd: CondBB);
696 auto *Dec = BinaryOperator::CreateNSWAdd(
697 V1: PN, V2: ConstantInt::get(Context, V: APInt(64, -1)), Name: "dec", BB: IncBB);
698 PN->addIncoming(V: Dec, BB: IncBB);
699 BranchInst::Create(IfTrue: CondBB, InsertAtEnd: IncBB);
700
701 Accum = GetElementPtrInst::Create(PointeeType: I8Ty, Ptr: Accum, IdxList: PN, NameStr: "gep", InsertAtEnd: EndBB);
702
703 PrevBB = CondBB;
704 CondBB = NextBB;
705 }
706 ReturnInst::Create(C&: Context, retVal: nullptr, InsertAtEnd: EndBB);
707 ScalarEvolution SE = buildSE(F&: *F);
708 const SCEV *S = SE.getSCEV(V: Accum);
709 S = SE.getLosslessPtrToIntExpr(Op: S);
710 Type *I128Ty = Type::getInt128Ty(C&: Context);
711 SE.getZeroExtendExpr(Op: S, Ty: I128Ty);
712}
713
714// Make sure that SCEV invalidates exit limits after invalidating the values it
715// depends on when we forget a loop.
716TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetLoop) {
717 /*
718 * Create the following code:
719 * func(i64 addrspace(10)* %arg)
720 * top:
721 * br label %L.ph
722 * L.ph:
723 * br label %L
724 * L:
725 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
726 * %add = add i64 %phi2, 1
727 * %cond = icmp slt i64 %add, 1000; then becomes 2000.
728 * br i1 %cond, label %post, label %L2
729 * post:
730 * ret void
731 *
732 */
733
734 // Create a module with non-integral pointers in it's datalayout
735 Module NIM("nonintegral", Context);
736 std::string DataLayout = M.getDataLayoutStr();
737 if (!DataLayout.empty())
738 DataLayout += "-";
739 DataLayout += "ni:10";
740 NIM.setDataLayout(DataLayout);
741
742 Type *T_int64 = Type::getInt64Ty(C&: Context);
743 Type *T_pint64 = PointerType::get(C&: Context, AddressSpace: 10);
744
745 FunctionType *FTy =
746 FunctionType::get(Result: Type::getVoidTy(C&: Context), Params: {T_pint64}, isVarArg: false);
747 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "foo", M&: NIM);
748
749 BasicBlock *Top = BasicBlock::Create(Context, Name: "top", Parent: F);
750 BasicBlock *LPh = BasicBlock::Create(Context, Name: "L.ph", Parent: F);
751 BasicBlock *L = BasicBlock::Create(Context, Name: "L", Parent: F);
752 BasicBlock *Post = BasicBlock::Create(Context, Name: "post", Parent: F);
753
754 IRBuilder<> Builder(Top);
755 Builder.CreateBr(Dest: LPh);
756
757 Builder.SetInsertPoint(LPh);
758 Builder.CreateBr(Dest: L);
759
760 Builder.SetInsertPoint(L);
761 PHINode *Phi = Builder.CreatePHI(Ty: T_int64, NumReservedValues: 2);
762 auto *Add = cast<Instruction>(
763 Val: Builder.CreateAdd(LHS: Phi, RHS: ConstantInt::get(Ty: T_int64, V: 1), Name: "add"));
764 auto *Limit = ConstantInt::get(Ty: T_int64, V: 1000);
765 auto *Cond = cast<Instruction>(
766 Val: Builder.CreateICmp(P: ICmpInst::ICMP_SLT, LHS: Add, RHS: Limit, Name: "cond"));
767 auto *Br = cast<Instruction>(Val: Builder.CreateCondBr(Cond, True: L, False: Post));
768 Phi->addIncoming(V: ConstantInt::get(Ty: T_int64, V: 0), BB: LPh);
769 Phi->addIncoming(V: Add, BB: L);
770
771 Builder.SetInsertPoint(Post);
772 Builder.CreateRetVoid();
773
774 ScalarEvolution SE = buildSE(F&: *F);
775 auto *Loop = LI->getLoopFor(BB: L);
776 const SCEV *EC = SE.getBackedgeTakenCount(L: Loop);
777 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC));
778 EXPECT_TRUE(isa<SCEVConstant>(EC));
779 EXPECT_EQ(cast<SCEVConstant>(EC)->getAPInt().getLimitedValue(), 999u);
780
781 // The add recurrence {5,+,1} does not correspond to any PHI in the IR, and
782 // that is relevant to this test.
783 auto *Five = SE.getConstant(Val: APInt(/*numBits=*/64, 5));
784 auto *AR =
785 SE.getAddRecExpr(Start: Five, Step: SE.getOne(Ty: T_int64), L: Loop, Flags: SCEV::FlagAnyWrap);
786 const SCEV *ARAtLoopExit = SE.getSCEVAtScope(S: AR, L: nullptr);
787 EXPECT_FALSE(isa<SCEVCouldNotCompute>(ARAtLoopExit));
788 EXPECT_TRUE(isa<SCEVConstant>(ARAtLoopExit));
789 EXPECT_EQ(cast<SCEVConstant>(ARAtLoopExit)->getAPInt().getLimitedValue(),
790 1004u);
791
792 SE.forgetLoop(L: Loop);
793 Br->eraseFromParent();
794 Cond->eraseFromParent();
795
796 Builder.SetInsertPoint(L);
797 auto *NewCond = Builder.CreateICmp(
798 P: ICmpInst::ICMP_SLT, LHS: Add, RHS: ConstantInt::get(Ty: T_int64, V: 2000), Name: "new.cond");
799 Builder.CreateCondBr(Cond: NewCond, True: L, False: Post);
800 const SCEV *NewEC = SE.getBackedgeTakenCount(L: Loop);
801 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC));
802 EXPECT_TRUE(isa<SCEVConstant>(NewEC));
803 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u);
804 const SCEV *NewARAtLoopExit = SE.getSCEVAtScope(S: AR, L: nullptr);
805 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewARAtLoopExit));
806 EXPECT_TRUE(isa<SCEVConstant>(NewARAtLoopExit));
807 EXPECT_EQ(cast<SCEVConstant>(NewARAtLoopExit)->getAPInt().getLimitedValue(),
808 2004u);
809}
810
811// Make sure that SCEV invalidates exit limits after invalidating the values it
812// depends on when we forget a value.
813TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetValue) {
814 /*
815 * Create the following code:
816 * func(i64 addrspace(10)* %arg)
817 * top:
818 * br label %L.ph
819 * L.ph:
820 * %load = load i64 addrspace(10)* %arg
821 * br label %L
822 * L:
823 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
824 * %add = add i64 %phi2, 1
825 * %cond = icmp slt i64 %add, %load ; then becomes 2000.
826 * br i1 %cond, label %post, label %L2
827 * post:
828 * ret void
829 *
830 */
831
832 // Create a module with non-integral pointers in it's datalayout
833 Module NIM("nonintegral", Context);
834 std::string DataLayout = M.getDataLayoutStr();
835 if (!DataLayout.empty())
836 DataLayout += "-";
837 DataLayout += "ni:10";
838 NIM.setDataLayout(DataLayout);
839
840 Type *T_int64 = Type::getInt64Ty(C&: Context);
841 Type *T_pint64 = PointerType::get(C&: Context, AddressSpace: 10);
842
843 FunctionType *FTy =
844 FunctionType::get(Result: Type::getVoidTy(C&: Context), Params: {T_pint64}, isVarArg: false);
845 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "foo", M&: NIM);
846
847 Argument *Arg = &*F->arg_begin();
848
849 BasicBlock *Top = BasicBlock::Create(Context, Name: "top", Parent: F);
850 BasicBlock *LPh = BasicBlock::Create(Context, Name: "L.ph", Parent: F);
851 BasicBlock *L = BasicBlock::Create(Context, Name: "L", Parent: F);
852 BasicBlock *Post = BasicBlock::Create(Context, Name: "post", Parent: F);
853
854 IRBuilder<> Builder(Top);
855 Builder.CreateBr(Dest: LPh);
856
857 Builder.SetInsertPoint(LPh);
858 auto *Load = cast<Instruction>(Val: Builder.CreateLoad(Ty: T_int64, Ptr: Arg, Name: "load"));
859 Builder.CreateBr(Dest: L);
860
861 Builder.SetInsertPoint(L);
862 PHINode *Phi = Builder.CreatePHI(Ty: T_int64, NumReservedValues: 2);
863 auto *Add = cast<Instruction>(
864 Val: Builder.CreateAdd(LHS: Phi, RHS: ConstantInt::get(Ty: T_int64, V: 1), Name: "add"));
865 auto *Cond = cast<Instruction>(
866 Val: Builder.CreateICmp(P: ICmpInst::ICMP_SLT, LHS: Add, RHS: Load, Name: "cond"));
867 auto *Br = cast<Instruction>(Val: Builder.CreateCondBr(Cond, True: L, False: Post));
868 Phi->addIncoming(V: ConstantInt::get(Ty: T_int64, V: 0), BB: LPh);
869 Phi->addIncoming(V: Add, BB: L);
870
871 Builder.SetInsertPoint(Post);
872 Builder.CreateRetVoid();
873
874 ScalarEvolution SE = buildSE(F&: *F);
875 auto *Loop = LI->getLoopFor(BB: L);
876 const SCEV *EC = SE.getBackedgeTakenCount(L: Loop);
877 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC));
878 EXPECT_FALSE(isa<SCEVConstant>(EC));
879
880 SE.forgetValue(V: Load);
881 Br->eraseFromParent();
882 Cond->eraseFromParent();
883 Load->eraseFromParent();
884
885 Builder.SetInsertPoint(L);
886 auto *NewCond = Builder.CreateICmp(
887 P: ICmpInst::ICMP_SLT, LHS: Add, RHS: ConstantInt::get(Ty: T_int64, V: 2000), Name: "new.cond");
888 Builder.CreateCondBr(Cond: NewCond, True: L, False: Post);
889 const SCEV *NewEC = SE.getBackedgeTakenCount(L: Loop);
890 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC));
891 EXPECT_TRUE(isa<SCEVConstant>(NewEC));
892 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u);
893}
894
895TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstants) {
896 // Reference: https://reviews.llvm.org/D37265
897 // Make sure that SCEV does not blow up when constructing an AddRec
898 // with predicates for a phi with the update pattern:
899 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum
900 // when either the initial value of the Phi or the InvariantAccum are
901 // constants that are too large to fit in an ix but are zero when truncated to
902 // ix.
903 FunctionType *FTy =
904 FunctionType::get(Result: Type::getVoidTy(C&: Context), Params: std::vector<Type *>(), isVarArg: false);
905 Function *F =
906 Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "addrecphitest", M);
907
908 /*
909 Create IR:
910 entry:
911 br label %loop
912 loop:
913 %0 = phi i64 [-9223372036854775808, %entry], [%3, %loop]
914 %1 = shl i64 %0, 32
915 %2 = ashr exact i64 %1, 32
916 %3 = add i64 %2, -9223372036854775808
917 br i1 undef, label %exit, label %loop
918 exit:
919 ret void
920 */
921 BasicBlock *EntryBB = BasicBlock::Create(Context, Name: "entry", Parent: F);
922 BasicBlock *LoopBB = BasicBlock::Create(Context, Name: "loop", Parent: F);
923 BasicBlock *ExitBB = BasicBlock::Create(Context, Name: "exit", Parent: F);
924
925 // entry:
926 BranchInst::Create(IfTrue: LoopBB, InsertAtEnd: EntryBB);
927 // loop:
928 auto *MinInt64 =
929 ConstantInt::get(Context, V: APInt(64, 0x8000000000000000U, true));
930 auto *Int64_32 = ConstantInt::get(Context, V: APInt(64, 32));
931 auto *Br = BranchInst::Create(
932 IfTrue: LoopBB, IfFalse: ExitBB, Cond: UndefValue::get(T: Type::getInt1Ty(C&: Context)), InsertAtEnd: LoopBB);
933 auto *Phi = PHINode::Create(Ty: Type::getInt64Ty(C&: Context), NumReservedValues: 2, NameStr: "", InsertBefore: Br);
934 auto *Shl = BinaryOperator::CreateShl(V1: Phi, V2: Int64_32, Name: "", I: Br);
935 auto *AShr = BinaryOperator::CreateExactAShr(V1: Shl, V2: Int64_32, Name: "", I: Br);
936 auto *Add = BinaryOperator::CreateAdd(V1: AShr, V2: MinInt64, Name: "", I: Br);
937 Phi->addIncoming(V: MinInt64, BB: EntryBB);
938 Phi->addIncoming(V: Add, BB: LoopBB);
939 // exit:
940 ReturnInst::Create(C&: Context, retVal: nullptr, InsertAtEnd: ExitBB);
941
942 // Make sure that SCEV doesn't blow up
943 ScalarEvolution SE = buildSE(F&: *F);
944 const SCEV *Expr = SE.getSCEV(V: Phi);
945 EXPECT_NE(nullptr, Expr);
946 EXPECT_TRUE(isa<SCEVUnknown>(Expr));
947 auto Result = SE.createAddRecFromPHIWithCasts(SymbolicPHI: cast<SCEVUnknown>(Val: Expr));
948}
949
950TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstantAccum) {
951 // Make sure that SCEV does not blow up when constructing an AddRec
952 // with predicates for a phi with the update pattern:
953 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum
954 // when the InvariantAccum is a constant that is too large to fit in an
955 // ix but are zero when truncated to ix, and the initial value of the
956 // phi is not a constant.
957 Type *Int32Ty = Type::getInt32Ty(C&: Context);
958 SmallVector<Type *, 1> Types;
959 Types.push_back(Elt: Int32Ty);
960 FunctionType *FTy = FunctionType::get(Result: Type::getVoidTy(C&: Context), Params: Types, isVarArg: false);
961 Function *F =
962 Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "addrecphitest", M);
963
964 /*
965 Create IR:
966 define @addrecphitest(i32)
967 entry:
968 br label %loop
969 loop:
970 %1 = phi i32 [%0, %entry], [%4, %loop]
971 %2 = shl i32 %1, 16
972 %3 = ashr exact i32 %2, 16
973 %4 = add i32 %3, -2147483648
974 br i1 undef, label %exit, label %loop
975 exit:
976 ret void
977 */
978 BasicBlock *EntryBB = BasicBlock::Create(Context, Name: "entry", Parent: F);
979 BasicBlock *LoopBB = BasicBlock::Create(Context, Name: "loop", Parent: F);
980 BasicBlock *ExitBB = BasicBlock::Create(Context, Name: "exit", Parent: F);
981
982 // entry:
983 BranchInst::Create(IfTrue: LoopBB, InsertAtEnd: EntryBB);
984 // loop:
985 auto *MinInt32 = ConstantInt::get(Context, V: APInt(32, 0x80000000U, true));
986 auto *Int32_16 = ConstantInt::get(Context, V: APInt(32, 16));
987 auto *Br = BranchInst::Create(
988 IfTrue: LoopBB, IfFalse: ExitBB, Cond: UndefValue::get(T: Type::getInt1Ty(C&: Context)), InsertAtEnd: LoopBB);
989 auto *Phi = PHINode::Create(Ty: Int32Ty, NumReservedValues: 2, NameStr: "", InsertBefore: Br);
990 auto *Shl = BinaryOperator::CreateShl(V1: Phi, V2: Int32_16, Name: "", I: Br);
991 auto *AShr = BinaryOperator::CreateExactAShr(V1: Shl, V2: Int32_16, Name: "", I: Br);
992 auto *Add = BinaryOperator::CreateAdd(V1: AShr, V2: MinInt32, Name: "", I: Br);
993 auto *Arg = &*(F->arg_begin());
994 Phi->addIncoming(V: Arg, BB: EntryBB);
995 Phi->addIncoming(V: Add, BB: LoopBB);
996 // exit:
997 ReturnInst::Create(C&: Context, retVal: nullptr, InsertAtEnd: ExitBB);
998
999 // Make sure that SCEV doesn't blow up
1000 ScalarEvolution SE = buildSE(F&: *F);
1001 const SCEV *Expr = SE.getSCEV(V: Phi);
1002 EXPECT_NE(nullptr, Expr);
1003 EXPECT_TRUE(isa<SCEVUnknown>(Expr));
1004 auto Result = SE.createAddRecFromPHIWithCasts(SymbolicPHI: cast<SCEVUnknown>(Val: Expr));
1005}
1006
1007TEST_F(ScalarEvolutionsTest, SCEVFoldSumOfTruncs) {
1008 // Verify that the following SCEV gets folded to a zero:
1009 // (-1 * (trunc i64 (-1 * %0) to i32)) + (-1 * (trunc i64 %0 to i32)
1010 Type *ArgTy = Type::getInt64Ty(C&: Context);
1011 Type *Int32Ty = Type::getInt32Ty(C&: Context);
1012 SmallVector<Type *, 1> Types;
1013 Types.push_back(Elt: ArgTy);
1014 FunctionType *FTy = FunctionType::get(Result: Type::getVoidTy(C&: Context), Params: Types, isVarArg: false);
1015 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "f", M);
1016 BasicBlock *BB = BasicBlock::Create(Context, Name: "entry", Parent: F);
1017 ReturnInst::Create(C&: Context, retVal: nullptr, InsertAtEnd: BB);
1018
1019 ScalarEvolution SE = buildSE(F&: *F);
1020
1021 auto *Arg = &*(F->arg_begin());
1022 const auto *ArgSCEV = SE.getSCEV(V: Arg);
1023
1024 // Build the SCEV
1025 const auto *A0 = SE.getNegativeSCEV(V: ArgSCEV);
1026 const auto *A1 = SE.getTruncateExpr(Op: A0, Ty: Int32Ty);
1027 const auto *A = SE.getNegativeSCEV(V: A1);
1028
1029 const auto *B0 = SE.getTruncateExpr(Op: ArgSCEV, Ty: Int32Ty);
1030 const auto *B = SE.getNegativeSCEV(V: B0);
1031
1032 const auto *Expr = SE.getAddExpr(LHS: A, RHS: B);
1033 // Verify that the SCEV was folded to 0
1034 const auto *ZeroConst = SE.getConstant(Ty: Int32Ty, V: 0);
1035 EXPECT_EQ(Expr, ZeroConst);
1036}
1037
1038// Check logic of SCEV expression size computation.
1039TEST_F(ScalarEvolutionsTest, SCEVComputeExpressionSize) {
1040 /*
1041 * Create the following code:
1042 * void func(i64 %a, i64 %b)
1043 * entry:
1044 * %s1 = add i64 %a, 1
1045 * %s2 = udiv i64 %s1, %b
1046 * br label %exit
1047 * exit:
1048 * ret
1049 */
1050
1051 // Create a module.
1052 Module M("SCEVComputeExpressionSize", Context);
1053
1054 Type *T_int64 = Type::getInt64Ty(C&: Context);
1055
1056 FunctionType *FTy =
1057 FunctionType::get(Result: Type::getVoidTy(C&: Context), Params: { T_int64, T_int64 }, isVarArg: false);
1058 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "func", M);
1059 Argument *A = &*F->arg_begin();
1060 Argument *B = &*std::next(x: F->arg_begin());
1061 ConstantInt *C = ConstantInt::get(Context, V: APInt(64, 1));
1062
1063 BasicBlock *Entry = BasicBlock::Create(Context, Name: "entry", Parent: F);
1064 BasicBlock *Exit = BasicBlock::Create(Context, Name: "exit", Parent: F);
1065
1066 IRBuilder<> Builder(Entry);
1067 auto *S1 = cast<Instruction>(Val: Builder.CreateAdd(LHS: A, RHS: C, Name: "s1"));
1068 auto *S2 = cast<Instruction>(Val: Builder.CreateUDiv(LHS: S1, RHS: B, Name: "s2"));
1069 Builder.CreateBr(Dest: Exit);
1070
1071 Builder.SetInsertPoint(Exit);
1072 Builder.CreateRetVoid();
1073
1074 ScalarEvolution SE = buildSE(F&: *F);
1075 // Get S2 first to move it to cache.
1076 const SCEV *AS = SE.getSCEV(V: A);
1077 const SCEV *BS = SE.getSCEV(V: B);
1078 const SCEV *CS = SE.getSCEV(V: C);
1079 const SCEV *S1S = SE.getSCEV(V: S1);
1080 const SCEV *S2S = SE.getSCEV(V: S2);
1081 EXPECT_EQ(AS->getExpressionSize(), 1u);
1082 EXPECT_EQ(BS->getExpressionSize(), 1u);
1083 EXPECT_EQ(CS->getExpressionSize(), 1u);
1084 EXPECT_EQ(S1S->getExpressionSize(), 3u);
1085 EXPECT_EQ(S2S->getExpressionSize(), 5u);
1086}
1087
1088TEST_F(ScalarEvolutionsTest, SCEVLoopDecIntrinsic) {
1089 LLVMContext C;
1090 SMDiagnostic Err;
1091 std::unique_ptr<Module> M = parseAssemblyString(
1092 AsmString: "define void @foo(i32 %N) { "
1093 "entry: "
1094 " %cmp3 = icmp sgt i32 %N, 0 "
1095 " br i1 %cmp3, label %for.body, label %for.cond.cleanup "
1096 "for.cond.cleanup: "
1097 " ret void "
1098 "for.body: "
1099 " %i.04 = phi i32 [ %inc, %for.body ], [ 100, %entry ] "
1100 " %inc = call i32 @llvm.loop.decrement.reg.i32.i32.i32(i32 %i.04, i32 1) "
1101 " %exitcond = icmp ne i32 %inc, 0 "
1102 " br i1 %exitcond, label %for.cond.cleanup, label %for.body "
1103 "} "
1104 "declare i32 @llvm.loop.decrement.reg.i32.i32.i32(i32, i32) ",
1105 Err, Context&: C);
1106
1107 ASSERT_TRUE(M && "Could not parse module?");
1108 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1109
1110 runWithSE(M&: *M, FuncName: "foo", Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1111 auto *ScevInc = SE.getSCEV(V: getInstructionByName(F, Name: "inc"));
1112 EXPECT_TRUE(isa<SCEVAddRecExpr>(ScevInc));
1113 });
1114}
1115
1116TEST_F(ScalarEvolutionsTest, SCEVComputeConstantDifference) {
1117 LLVMContext C;
1118 SMDiagnostic Err;
1119 std::unique_ptr<Module> M = parseAssemblyString(
1120 AsmString: "define void @foo(i32 %sz, i32 %pp) { "
1121 "entry: "
1122 " %v0 = add i32 %pp, 0 "
1123 " %v3 = add i32 %pp, 3 "
1124 " br label %loop.body "
1125 "loop.body: "
1126 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] "
1127 " %xa = add nsw i32 %iv, %v0 "
1128 " %yy = add nsw i32 %iv, %v3 "
1129 " %xb = sub nsw i32 %yy, 3 "
1130 " %iv.next = add nsw i32 %iv, 1 "
1131 " %cmp = icmp sle i32 %iv.next, %sz "
1132 " br i1 %cmp, label %loop.body, label %exit "
1133 "exit: "
1134 " ret void "
1135 "} ",
1136 Err, Context&: C);
1137
1138 ASSERT_TRUE(M && "Could not parse module?");
1139 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1140
1141 runWithSE(M&: *M, FuncName: "foo", Test: [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1142 auto *ScevV0 = SE.getSCEV(V: getInstructionByName(F, Name: "v0")); // %pp
1143 auto *ScevV3 = SE.getSCEV(V: getInstructionByName(F, Name: "v3")); // (3 + %pp)
1144 auto *ScevIV = SE.getSCEV(V: getInstructionByName(F, Name: "iv")); // {0,+,1}
1145 auto *ScevXA = SE.getSCEV(V: getInstructionByName(F, Name: "xa")); // {%pp,+,1}
1146 auto *ScevYY = SE.getSCEV(V: getInstructionByName(F, Name: "yy")); // {(3 + %pp),+,1}
1147 auto *ScevXB = SE.getSCEV(V: getInstructionByName(F, Name: "xb")); // {%pp,+,1}
1148 auto *ScevIVNext = SE.getSCEV(V: getInstructionByName(F, Name: "iv.next")); // {1,+,1}
1149
1150 auto diff = [&SE](const SCEV *LHS, const SCEV *RHS) -> std::optional<int> {
1151 auto ConstantDiffOrNone = computeConstantDifference(SE, LHS, RHS);
1152 if (!ConstantDiffOrNone)
1153 return std::nullopt;
1154
1155 auto ExtDiff = ConstantDiffOrNone->getSExtValue();
1156 int Diff = ExtDiff;
1157 assert(Diff == ExtDiff && "Integer overflow");
1158 return Diff;
1159 };
1160
1161 EXPECT_EQ(diff(ScevV3, ScevV0), 3);
1162 EXPECT_EQ(diff(ScevV0, ScevV3), -3);
1163 EXPECT_EQ(diff(ScevV0, ScevV0), 0);
1164 EXPECT_EQ(diff(ScevV3, ScevV3), 0);
1165 EXPECT_EQ(diff(ScevIV, ScevIV), 0);
1166 EXPECT_EQ(diff(ScevXA, ScevXB), 0);
1167 EXPECT_EQ(diff(ScevXA, ScevYY), -3);
1168 EXPECT_EQ(diff(ScevYY, ScevXB), 3);
1169 EXPECT_EQ(diff(ScevIV, ScevIVNext), -1);
1170 EXPECT_EQ(diff(ScevIVNext, ScevIV), 1);
1171 EXPECT_EQ(diff(ScevIVNext, ScevIVNext), 0);
1172 EXPECT_EQ(diff(ScevV0, ScevIV), std::nullopt);
1173 EXPECT_EQ(diff(ScevIVNext, ScevV3), std::nullopt);
1174 EXPECT_EQ(diff(ScevYY, ScevV3), std::nullopt);
1175 });
1176}
1177
1178TEST_F(ScalarEvolutionsTest, SCEVrewriteUnknowns) {
1179 LLVMContext C;
1180 SMDiagnostic Err;
1181 std::unique_ptr<Module> M = parseAssemblyString(
1182 AsmString: "define void @foo(i32 %i) { "
1183 "entry: "
1184 " %cmp3 = icmp ult i32 %i, 16 "
1185 " br i1 %cmp3, label %loop.body, label %exit "
1186 "loop.body: "
1187 " %iv = phi i32 [ %iv.next, %loop.body ], [ %i, %entry ] "
1188 " %iv.next = add nsw i32 %iv, 1 "
1189 " %cmp = icmp eq i32 %iv.next, 16 "
1190 " br i1 %cmp, label %exit, label %loop.body "
1191 "exit: "
1192 " ret void "
1193 "} ",
1194 Err, Context&: C);
1195
1196 ASSERT_TRUE(M && "Could not parse module?");
1197 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1198
1199 runWithSE(M&: *M, FuncName: "foo", Test: [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1200 auto *ScevIV = SE.getSCEV(V: getInstructionByName(F, Name: "iv")); // {0,+,1}
1201 auto *ScevI = SE.getSCEV(V: getArgByName(F, Name: "i")); // {0,+,1}
1202
1203 ValueToSCEVMapTy RewriteMap;
1204 RewriteMap[cast<SCEVUnknown>(Val: ScevI)->getValue()] =
1205 SE.getUMinExpr(LHS: ScevI, RHS: SE.getConstant(Ty: ScevI->getType(), V: 17));
1206 auto *WithUMin = SCEVParameterRewriter::rewrite(Scev: ScevIV, SE, Map&: RewriteMap);
1207
1208 EXPECT_NE(WithUMin, ScevIV);
1209 auto *AR = dyn_cast<SCEVAddRecExpr>(Val: WithUMin);
1210 EXPECT_TRUE(AR);
1211 EXPECT_EQ(AR->getStart(),
1212 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17)));
1213 EXPECT_EQ(AR->getStepRecurrence(SE),
1214 cast<SCEVAddRecExpr>(ScevIV)->getStepRecurrence(SE));
1215 });
1216}
1217
1218TEST_F(ScalarEvolutionsTest, SCEVAddNUW) {
1219 LLVMContext C;
1220 SMDiagnostic Err;
1221 std::unique_ptr<Module> M = parseAssemblyString(AsmString: "define void @foo(i32 %x) { "
1222 " ret void "
1223 "} ",
1224 Err, Context&: C);
1225
1226 ASSERT_TRUE(M && "Could not parse module?");
1227 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1228
1229 runWithSE(M&: *M, FuncName: "foo", Test: [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1230 auto *X = SE.getSCEV(V: getArgByName(F, Name: "x"));
1231 auto *One = SE.getOne(Ty: X->getType());
1232 auto *Sum = SE.getAddExpr(LHS: X, RHS: One, Flags: SCEV::FlagNUW);
1233 EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGE, Sum, X));
1234 EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGT, Sum, X));
1235 });
1236}
1237
1238TEST_F(ScalarEvolutionsTest, SCEVgetRanges) {
1239 LLVMContext C;
1240 SMDiagnostic Err;
1241 std::unique_ptr<Module> M = parseAssemblyString(
1242 AsmString: "define void @foo(i32 %i) { "
1243 "entry: "
1244 " br label %loop.body "
1245 "loop.body: "
1246 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] "
1247 " %iv.next = add nsw i32 %iv, 1 "
1248 " %cmp = icmp eq i32 %iv.next, 16 "
1249 " br i1 %cmp, label %exit, label %loop.body "
1250 "exit: "
1251 " ret void "
1252 "} ",
1253 Err, Context&: C);
1254
1255 runWithSE(M&: *M, FuncName: "foo", Test: [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1256 auto *ScevIV = SE.getSCEV(V: getInstructionByName(F, Name: "iv")); // {0,+,1}
1257 auto *ScevI = SE.getSCEV(V: getArgByName(F, Name: "i"));
1258 EXPECT_EQ(SE.getUnsignedRange(ScevIV).getLower(), 0);
1259 EXPECT_EQ(SE.getUnsignedRange(ScevIV).getUpper(), 16);
1260
1261 auto *Add = SE.getAddExpr(LHS: ScevI, RHS: ScevIV);
1262 ValueToSCEVMapTy RewriteMap;
1263 RewriteMap[cast<SCEVUnknown>(Val: ScevI)->getValue()] =
1264 SE.getUMinExpr(LHS: ScevI, RHS: SE.getConstant(Ty: ScevI->getType(), V: 17));
1265 auto *AddWithUMin = SCEVParameterRewriter::rewrite(Scev: Add, SE, Map&: RewriteMap);
1266 EXPECT_EQ(SE.getUnsignedRange(AddWithUMin).getLower(), 0);
1267 EXPECT_EQ(SE.getUnsignedRange(AddWithUMin).getUpper(), 33);
1268 });
1269}
1270
1271TEST_F(ScalarEvolutionsTest, SCEVgetExitLimitForGuardedLoop) {
1272 LLVMContext C;
1273 SMDiagnostic Err;
1274 std::unique_ptr<Module> M = parseAssemblyString(
1275 AsmString: "define void @foo(i32 %i) { "
1276 "entry: "
1277 " %cmp3 = icmp ult i32 %i, 16 "
1278 " br i1 %cmp3, label %loop.body, label %exit "
1279 "loop.body: "
1280 " %iv = phi i32 [ %iv.next, %loop.body ], [ %i, %entry ] "
1281 " %iv.next = add nsw i32 %iv, 1 "
1282 " %cmp = icmp eq i32 %iv.next, 16 "
1283 " br i1 %cmp, label %exit, label %loop.body "
1284 "exit: "
1285 " ret void "
1286 "} ",
1287 Err, Context&: C);
1288
1289 ASSERT_TRUE(M && "Could not parse module?");
1290 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1291
1292 runWithSE(M&: *M, FuncName: "foo", Test: [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1293 auto *ScevIV = SE.getSCEV(V: getInstructionByName(F, Name: "iv")); // {0,+,1}
1294 const Loop *L = cast<SCEVAddRecExpr>(Val: ScevIV)->getLoop();
1295
1296 const SCEV *BTC = SE.getBackedgeTakenCount(L);
1297 EXPECT_FALSE(isa<SCEVConstant>(BTC));
1298 const SCEV *MaxBTC = SE.getConstantMaxBackedgeTakenCount(L);
1299 EXPECT_EQ(cast<SCEVConstant>(MaxBTC)->getAPInt(), 15);
1300 });
1301}
1302
1303TEST_F(ScalarEvolutionsTest, ImpliedViaAddRecStart) {
1304 LLVMContext C;
1305 SMDiagnostic Err;
1306 std::unique_ptr<Module> M = parseAssemblyString(
1307 AsmString: "define void @foo(i32* %p) { "
1308 "entry: "
1309 " %x = load i32, i32* %p, !range !0 "
1310 " br label %loop "
1311 "loop: "
1312 " %iv = phi i32 [ %x, %entry], [%iv.next, %backedge] "
1313 " %ne.check = icmp ne i32 %iv, 0 "
1314 " br i1 %ne.check, label %backedge, label %exit "
1315 "backedge: "
1316 " %iv.next = add i32 %iv, -1 "
1317 " br label %loop "
1318 "exit:"
1319 " ret void "
1320 "} "
1321 "!0 = !{i32 0, i32 2147483647}",
1322 Err, Context&: C);
1323
1324 ASSERT_TRUE(M && "Could not parse module?");
1325 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1326
1327 runWithSE(M&: *M, FuncName: "foo", Test: [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1328 auto *X = SE.getSCEV(V: getInstructionByName(F, Name: "x"));
1329 auto *Context = getInstructionByName(F, Name: "iv.next");
1330 EXPECT_TRUE(SE.isKnownPredicateAt(ICmpInst::ICMP_NE, X,
1331 SE.getZero(X->getType()), Context));
1332 });
1333}
1334
1335TEST_F(ScalarEvolutionsTest, UnsignedIsImpliedViaOperations) {
1336 LLVMContext C;
1337 SMDiagnostic Err;
1338 std::unique_ptr<Module> M =
1339 parseAssemblyString(AsmString: "define void @foo(i32* %p1, i32* %p2) { "
1340 "entry: "
1341 " %x = load i32, i32* %p1, !range !0 "
1342 " %cond = icmp ne i32 %x, 0 "
1343 " br i1 %cond, label %guarded, label %exit "
1344 "guarded: "
1345 " %y = add i32 %x, -1 "
1346 " ret void "
1347 "exit: "
1348 " ret void "
1349 "} "
1350 "!0 = !{i32 0, i32 2147483647}",
1351 Err, Context&: C);
1352
1353 ASSERT_TRUE(M && "Could not parse module?");
1354 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1355
1356 runWithSE(M&: *M, FuncName: "foo", Test: [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1357 auto *X = SE.getSCEV(V: getInstructionByName(F, Name: "x"));
1358 auto *Y = SE.getSCEV(V: getInstructionByName(F, Name: "y"));
1359 auto *Guarded = getInstructionByName(F, Name: "y")->getParent();
1360 ASSERT_TRUE(Guarded);
1361 EXPECT_TRUE(
1362 SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_ULT, Y, X));
1363 EXPECT_TRUE(
1364 SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_UGT, X, Y));
1365 });
1366}
1367
1368TEST_F(ScalarEvolutionsTest, ProveImplicationViaNarrowing) {
1369 LLVMContext C;
1370 SMDiagnostic Err;
1371 std::unique_ptr<Module> M = parseAssemblyString(
1372 AsmString: "define i32 @foo(i32 %start, i32* %q) { "
1373 "entry: "
1374 " %wide.start = zext i32 %start to i64 "
1375 " br label %loop "
1376 "loop: "
1377 " %wide.iv = phi i64 [%wide.start, %entry], [%wide.iv.next, %backedge] "
1378 " %iv = phi i32 [%start, %entry], [%iv.next, %backedge] "
1379 " %cond = icmp eq i64 %wide.iv, 0 "
1380 " br i1 %cond, label %exit, label %backedge "
1381 "backedge: "
1382 " %iv.next = add i32 %iv, -1 "
1383 " %index = zext i32 %iv.next to i64 "
1384 " %load.addr = getelementptr i32, i32* %q, i64 %index "
1385 " %stop = load i32, i32* %load.addr "
1386 " %loop.cond = icmp eq i32 %stop, 0 "
1387 " %wide.iv.next = add nsw i64 %wide.iv, -1 "
1388 " br i1 %loop.cond, label %loop, label %failure "
1389 "exit: "
1390 " ret i32 0 "
1391 "failure: "
1392 " unreachable "
1393 "} ",
1394 Err, Context&: C);
1395
1396 ASSERT_TRUE(M && "Could not parse module?");
1397 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1398
1399 runWithSE(M&: *M, FuncName: "foo", Test: [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1400 auto *IV = SE.getSCEV(V: getInstructionByName(F, Name: "iv"));
1401 auto *Zero = SE.getZero(Ty: IV->getType());
1402 auto *Backedge = getInstructionByName(F, Name: "iv.next")->getParent();
1403 ASSERT_TRUE(Backedge);
1404 (void)IV;
1405 (void)Zero;
1406 // FIXME: This can only be proved with turned on option
1407 // scalar-evolution-use-expensive-range-sharpening which is currently off.
1408 // Enable the check once it's switched true by default.
1409 // EXPECT_TRUE(SE.isBasicBlockEntryGuardedByCond(Backedge,
1410 // ICmpInst::ICMP_UGT,
1411 // IV, Zero));
1412 });
1413}
1414
1415TEST_F(ScalarEvolutionsTest, ImpliedCond) {
1416 LLVMContext C;
1417 SMDiagnostic Err;
1418 std::unique_ptr<Module> M = parseAssemblyString(
1419 AsmString: "define void @foo(i32 %len) { "
1420 "entry: "
1421 " br label %loop "
1422 "loop: "
1423 " %iv = phi i32 [ 0, %entry], [%iv.next, %loop] "
1424 " %iv.next = add nsw i32 %iv, 1 "
1425 " %cmp = icmp slt i32 %iv, %len "
1426 " br i1 %cmp, label %loop, label %exit "
1427 "exit:"
1428 " ret void "
1429 "}",
1430 Err, Context&: C);
1431
1432 ASSERT_TRUE(M && "Could not parse module?");
1433 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1434
1435 runWithSE(M&: *M, FuncName: "foo", Test: [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1436 Instruction *IV = getInstructionByName(F, Name: "iv");
1437 Type *Ty = IV->getType();
1438 const SCEV *Zero = SE.getZero(Ty);
1439 const SCEV *MinusOne = SE.getMinusOne(Ty);
1440 // {0,+,1}<nuw><nsw>
1441 const SCEV *AddRec_0_1 = SE.getSCEV(V: IV);
1442 // {0,+,-1}<nw>
1443 const SCEV *AddRec_0_N1 = SE.getNegativeSCEV(V: AddRec_0_1);
1444
1445 // {0,+,1}<nuw><nsw> > 0 -> {0,+,-1}<nw> < 0
1446 EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SLT, AddRec_0_N1, Zero,
1447 ICmpInst::ICMP_SGT, AddRec_0_1, Zero));
1448 // {0,+,-1}<nw> < -1 -> {0,+,1}<nuw><nsw> > 0
1449 EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SGT, AddRec_0_1, Zero,
1450 ICmpInst::ICMP_SLT, AddRec_0_N1, MinusOne));
1451 });
1452}
1453
1454TEST_F(ScalarEvolutionsTest, MatchURem) {
1455 LLVMContext C;
1456 SMDiagnostic Err;
1457 std::unique_ptr<Module> M = parseAssemblyString(
1458 AsmString: "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
1459 " "
1460 "define void @test(i32 %a, i32 %b, i16 %c, i64 %d) {"
1461 "entry: "
1462 " %rem1 = urem i32 %a, 2"
1463 " %rem2 = urem i32 %a, 5"
1464 " %rem3 = urem i32 %a, %b"
1465 " %c.ext = zext i16 %c to i32"
1466 " %rem4 = urem i32 %c.ext, 2"
1467 " %ext = zext i32 %rem4 to i64"
1468 " %rem5 = urem i64 %d, 17179869184"
1469 " ret void "
1470 "} ",
1471 Err, Context&: C);
1472
1473 assert(M && "Could not parse module?");
1474 assert(!verifyModule(*M) && "Must have been well formed!");
1475
1476 runWithSE(M&: *M, FuncName: "test", Test: [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1477 for (auto *N : {"rem1", "rem2", "rem3", "rem5"}) {
1478 auto *URemI = getInstructionByName(F, Name: N);
1479 auto *S = SE.getSCEV(V: URemI);
1480 const SCEV *LHS, *RHS;
1481 EXPECT_TRUE(matchURem(SE, S, LHS, RHS));
1482 EXPECT_EQ(LHS, SE.getSCEV(URemI->getOperand(0)));
1483 EXPECT_EQ(RHS, SE.getSCEV(URemI->getOperand(1)));
1484 EXPECT_EQ(LHS->getType(), S->getType());
1485 EXPECT_EQ(RHS->getType(), S->getType());
1486 }
1487
1488 // Check the case where the urem operand is zero-extended. Make sure the
1489 // match results are extended to the size of the input expression.
1490 auto *Ext = getInstructionByName(F, Name: "ext");
1491 auto *URem1 = getInstructionByName(F, Name: "rem4");
1492 auto *S = SE.getSCEV(V: Ext);
1493 const SCEV *LHS, *RHS;
1494 EXPECT_TRUE(matchURem(SE, S, LHS, RHS));
1495 EXPECT_NE(LHS, SE.getSCEV(URem1->getOperand(0)));
1496 // RHS and URem1->getOperand(1) have different widths, so compare the
1497 // integer values.
1498 EXPECT_EQ(cast<SCEVConstant>(RHS)->getValue()->getZExtValue(),
1499 cast<SCEVConstant>(SE.getSCEV(URem1->getOperand(1)))
1500 ->getValue()
1501 ->getZExtValue());
1502 EXPECT_EQ(LHS->getType(), S->getType());
1503 EXPECT_EQ(RHS->getType(), S->getType());
1504 });
1505}
1506
1507TEST_F(ScalarEvolutionsTest, SCEVUDivFloorCeiling) {
1508 LLVMContext C;
1509 SMDiagnostic Err;
1510 std::unique_ptr<Module> M = parseAssemblyString(AsmString: "define void @foo() { "
1511 " ret void "
1512 "} ",
1513 Err, Context&: C);
1514
1515 ASSERT_TRUE(M && "Could not parse module?");
1516 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1517
1518 runWithSE(M&: *M, FuncName: "foo", Test: [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1519 // Check that SCEV's udiv and uceil handling produce the correct results
1520 // for all 8 bit options. Div-by-zero is deliberately excluded.
1521 for (unsigned N = 0; N < 256; N++)
1522 for (unsigned D = 1; D < 256; D++) {
1523 APInt NInt(8, N);
1524 APInt DInt(8, D);
1525 using namespace llvm::APIntOps;
1526 APInt FloorInt = RoundingUDiv(A: NInt, B: DInt, RM: APInt::Rounding::DOWN);
1527 APInt CeilingInt = RoundingUDiv(A: NInt, B: DInt, RM: APInt::Rounding::UP);
1528 auto *NS = SE.getConstant(Val: NInt);
1529 auto *DS = SE.getConstant(Val: DInt);
1530 auto *FloorS = cast<SCEVConstant>(Val: SE.getUDivExpr(LHS: NS, RHS: DS));
1531 auto *CeilingS = cast<SCEVConstant>(Val: SE.getUDivCeilSCEV(N: NS, D: DS));
1532 ASSERT_TRUE(FloorS->getAPInt() == FloorInt);
1533 ASSERT_TRUE(CeilingS->getAPInt() == CeilingInt);
1534 }
1535 });
1536}
1537
1538TEST_F(ScalarEvolutionsTest, CheckGetPowerOfTwo) {
1539 Module M("CheckGetPowerOfTwo", Context);
1540 FunctionType *FTy = FunctionType::get(Result: Type::getVoidTy(C&: Context), Params: {}, isVarArg: false);
1541 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "foo", M);
1542 BasicBlock *Entry = BasicBlock::Create(Context, Name: "entry", Parent: F);
1543 IRBuilder<> Builder(Entry);
1544 Builder.CreateRetVoid();
1545 ScalarEvolution SE = buildSE(F&: *F);
1546
1547 for (unsigned short i = 0; i < 64; ++i)
1548 EXPECT_TRUE(
1549 dyn_cast<SCEVConstant>(SE.getPowerOfTwo(Type::getInt64Ty(Context), i))
1550 ->getValue()
1551 ->equalsInt(1ULL << i));
1552}
1553
1554TEST_F(ScalarEvolutionsTest, ApplyLoopGuards) {
1555 LLVMContext C;
1556 SMDiagnostic Err;
1557 std::unique_ptr<Module> M = parseAssemblyString(
1558 AsmString: "declare void @llvm.assume(i1)\n"
1559 "define void @test(i32 %num) {\n"
1560 "entry:\n"
1561 " %u = urem i32 %num, 4\n"
1562 " %cmp = icmp eq i32 %u, 0\n"
1563 " tail call void @llvm.assume(i1 %cmp)\n"
1564 " %cmp.1 = icmp ugt i32 %num, 0\n"
1565 " tail call void @llvm.assume(i1 %cmp.1)\n"
1566 " br label %for.body\n"
1567 "for.body:\n"
1568 " %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n"
1569 " %inc = add nuw nsw i32 %i.010, 1\n"
1570 " %cmp2 = icmp ult i32 %inc, %num\n"
1571 " br i1 %cmp2, label %for.body, label %exit\n"
1572 "exit:\n"
1573 " ret void\n"
1574 "}\n",
1575 Err, Context&: C);
1576
1577 ASSERT_TRUE(M && "Could not parse module?");
1578 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1579
1580 runWithSE(M&: *M, FuncName: "test", Test: [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1581 auto *TCScev = SE.getSCEV(V: getArgByName(F, Name: "num"));
1582 auto *ApplyLoopGuardsTC = SE.applyLoopGuards(Expr: TCScev, L: *LI.begin());
1583 // Assert that the new TC is (4 * ((4 umax %num) /u 4))
1584 APInt Four(32, 4);
1585 auto *Constant4 = SE.getConstant(Val: Four);
1586 auto *Max = SE.getUMaxExpr(LHS: TCScev, RHS: Constant4);
1587 auto *Mul = SE.getMulExpr(LHS: SE.getUDivExpr(LHS: Max, RHS: Constant4), RHS: Constant4);
1588 ASSERT_TRUE(Mul == ApplyLoopGuardsTC);
1589 });
1590}
1591
1592} // end namespace llvm
1593

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