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/LegacyPassManager.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/IR/Verifier.h"
25 #include "llvm/Support/SourceMgr.h"
26 #include "gtest/gtest.h"
27
28 namespace llvm {
29
30 // We use this fixture to ensure that we clean up ScalarEvolution before
31 // deleting the PassManager.
32 class ScalarEvolutionsTest : public testing::Test {
33 protected:
34 LLVMContext Context;
35 Module M;
36 TargetLibraryInfoImpl TLII;
37 TargetLibraryInfo TLI;
38
39 std::unique_ptr<AssumptionCache> AC;
40 std::unique_ptr<DominatorTree> DT;
41 std::unique_ptr<LoopInfo> LI;
42
ScalarEvolutionsTest()43 ScalarEvolutionsTest() : M("", Context), TLII(), TLI(TLII) {}
44
buildSE(Function & F)45 ScalarEvolution buildSE(Function &F) {
46 AC.reset(new AssumptionCache(F));
47 DT.reset(new DominatorTree(F));
48 LI.reset(new LoopInfo(*DT));
49 return ScalarEvolution(F, TLI, *AC, *DT, *LI);
50 }
51
runWithSE(Module & M,StringRef FuncName,function_ref<void (Function & F,LoopInfo & LI,ScalarEvolution & SE)> Test)52 void runWithSE(
53 Module &M, StringRef FuncName,
54 function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {
55 auto *F = M.getFunction(FuncName);
56 ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
57 ScalarEvolution SE = buildSE(*F);
58 Test(*F, *LI, SE);
59 }
60
computeConstantDifference(ScalarEvolution & SE,const SCEV * LHS,const SCEV * RHS)61 static Optional<APInt> computeConstantDifference(ScalarEvolution &SE,
62 const SCEV *LHS,
63 const SCEV *RHS) {
64 return SE.computeConstantDifference(LHS, RHS);
65 }
66 };
67
TEST_F(ScalarEvolutionsTest,SCEVUnknownRAUW)68 TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) {
69 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),
70 std::vector<Type *>(), false);
71 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);
72 BasicBlock *BB = BasicBlock::Create(Context, "entry", F);
73 ReturnInst::Create(Context, nullptr, BB);
74
75 Type *Ty = Type::getInt1Ty(Context);
76 Constant *Init = Constant::getNullValue(Ty);
77 Value *V0 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V0");
78 Value *V1 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V1");
79 Value *V2 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V2");
80
81 ScalarEvolution SE = buildSE(*F);
82
83 const SCEV *S0 = SE.getSCEV(V0);
84 const SCEV *S1 = SE.getSCEV(V1);
85 const SCEV *S2 = SE.getSCEV(V2);
86
87 const SCEV *P0 = SE.getAddExpr(S0, S0);
88 const SCEV *P1 = SE.getAddExpr(S1, S1);
89 const SCEV *P2 = SE.getAddExpr(S2, S2);
90
91 const SCEVMulExpr *M0 = cast<SCEVMulExpr>(P0);
92 const SCEVMulExpr *M1 = cast<SCEVMulExpr>(P1);
93 const SCEVMulExpr *M2 = cast<SCEVMulExpr>(P2);
94
95 EXPECT_EQ(cast<SCEVConstant>(M0->getOperand(0))->getValue()->getZExtValue(),
96 2u);
97 EXPECT_EQ(cast<SCEVConstant>(M1->getOperand(0))->getValue()->getZExtValue(),
98 2u);
99 EXPECT_EQ(cast<SCEVConstant>(M2->getOperand(0))->getValue()->getZExtValue(),
100 2u);
101
102 // Before the RAUWs, these are all pointing to separate values.
103 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);
104 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V1);
105 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V2);
106
107 // Do some RAUWs.
108 V2->replaceAllUsesWith(V1);
109 V1->replaceAllUsesWith(V0);
110
111 // After the RAUWs, these should all be pointing to V0.
112 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);
113 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V0);
114 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V0);
115 }
116
TEST_F(ScalarEvolutionsTest,SimplifiedPHI)117 TEST_F(ScalarEvolutionsTest, SimplifiedPHI) {
118 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),
119 std::vector<Type *>(), false);
120 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);
121 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
122 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);
123 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);
124 BranchInst::Create(LoopBB, EntryBB);
125 BranchInst::Create(LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)),
126 LoopBB);
127 ReturnInst::Create(Context, nullptr, ExitBB);
128 auto *Ty = Type::getInt32Ty(Context);
129 auto *PN = PHINode::Create(Ty, 2, "", &*LoopBB->begin());
130 PN->addIncoming(Constant::getNullValue(Ty), EntryBB);
131 PN->addIncoming(UndefValue::get(Ty), LoopBB);
132 ScalarEvolution SE = buildSE(*F);
133 auto *S1 = SE.getSCEV(PN);
134 auto *S2 = SE.getSCEV(PN);
135 auto *ZeroConst = SE.getConstant(Ty, 0);
136
137 // At some point, only the first call to getSCEV returned the simplified
138 // SCEVConstant and later calls just returned a SCEVUnknown referencing the
139 // PHI node.
140 EXPECT_EQ(S1, ZeroConst);
141 EXPECT_EQ(S1, S2);
142 }
143
144
getInstructionByName(Function & F,StringRef Name)145 static Instruction *getInstructionByName(Function &F, StringRef Name) {
146 for (auto &I : instructions(F))
147 if (I.getName() == Name)
148 return &I;
149 llvm_unreachable("Expected to find instruction!");
150 }
151
TEST_F(ScalarEvolutionsTest,CommutativeExprOperandOrder)152 TEST_F(ScalarEvolutionsTest, CommutativeExprOperandOrder) {
153 LLVMContext C;
154 SMDiagnostic Err;
155 std::unique_ptr<Module> M = parseAssemblyString(
156 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
157 " "
158 "@var_0 = external global i32, align 4"
159 "@var_1 = external global i32, align 4"
160 "@var_2 = external global i32, align 4"
161 " "
162 "declare i32 @unknown(i32, i32, i32)"
163 " "
164 "define void @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) "
165 " local_unnamed_addr { "
166 "entry: "
167 " %entrycond = icmp sgt i32 %n, 0 "
168 " br i1 %entrycond, label %loop.ph, label %for.end "
169 " "
170 "loop.ph: "
171 " %a = load i32, i32* %A, align 4 "
172 " %b = load i32, i32* %B, align 4 "
173 " %mul = mul nsw i32 %b, %a "
174 " %iv0.init = getelementptr inbounds i8, i8* %arr, i32 %mul "
175 " br label %loop "
176 " "
177 "loop: "
178 " %iv0 = phi i8* [ %iv0.inc, %loop ], [ %iv0.init, %loop.ph ] "
179 " %iv1 = phi i32 [ %iv1.inc, %loop ], [ 0, %loop.ph ] "
180 " %conv = trunc i32 %iv1 to i8 "
181 " store i8 %conv, i8* %iv0, align 1 "
182 " %iv0.inc = getelementptr inbounds i8, i8* %iv0, i32 %b "
183 " %iv1.inc = add nuw nsw i32 %iv1, 1 "
184 " %exitcond = icmp eq i32 %iv1.inc, %n "
185 " br i1 %exitcond, label %for.end.loopexit, label %loop "
186 " "
187 "for.end.loopexit: "
188 " br label %for.end "
189 " "
190 "for.end: "
191 " ret void "
192 "} "
193 " "
194 "define void @f_2(i32* %X, i32* %Y, i32* %Z) { "
195 " %x = load i32, i32* %X "
196 " %y = load i32, i32* %Y "
197 " %z = load i32, i32* %Z "
198 " ret void "
199 "} "
200 " "
201 "define void @f_3() { "
202 " %x = load i32, i32* @var_0"
203 " %y = load i32, i32* @var_1"
204 " %z = load i32, i32* @var_2"
205 " ret void"
206 "} "
207 " "
208 "define void @f_4(i32 %a, i32 %b, i32 %c) { "
209 " %x = call i32 @unknown(i32 %a, i32 %b, i32 %c)"
210 " %y = call i32 @unknown(i32 %b, i32 %c, i32 %a)"
211 " %z = call i32 @unknown(i32 %c, i32 %a, i32 %b)"
212 " ret void"
213 "} "
214 ,
215 Err, C);
216
217 assert(M && "Could not parse module?");
218 assert(!verifyModule(*M) && "Must have been well formed!");
219
220 runWithSE(*M, "f_1", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
221 auto *IV0 = getInstructionByName(F, "iv0");
222 auto *IV0Inc = getInstructionByName(F, "iv0.inc");
223
224 auto *FirstExprForIV0 = SE.getSCEV(IV0);
225 auto *FirstExprForIV0Inc = SE.getSCEV(IV0Inc);
226 auto *SecondExprForIV0 = SE.getSCEV(IV0);
227
228 EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0));
229 EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0Inc));
230 EXPECT_TRUE(isa<SCEVAddRecExpr>(SecondExprForIV0));
231 });
232
233 auto CheckCommutativeMulExprs = [&](ScalarEvolution &SE, const SCEV *A,
234 const SCEV *B, const SCEV *C) {
235 EXPECT_EQ(SE.getMulExpr(A, B), SE.getMulExpr(B, A));
236 EXPECT_EQ(SE.getMulExpr(B, C), SE.getMulExpr(C, B));
237 EXPECT_EQ(SE.getMulExpr(A, C), SE.getMulExpr(C, A));
238
239 SmallVector<const SCEV *, 3> Ops0 = {A, B, C};
240 SmallVector<const SCEV *, 3> Ops1 = {A, C, B};
241 SmallVector<const SCEV *, 3> Ops2 = {B, A, C};
242 SmallVector<const SCEV *, 3> Ops3 = {B, C, A};
243 SmallVector<const SCEV *, 3> Ops4 = {C, B, A};
244 SmallVector<const SCEV *, 3> Ops5 = {C, A, B};
245
246 auto *Mul0 = SE.getMulExpr(Ops0);
247 auto *Mul1 = SE.getMulExpr(Ops1);
248 auto *Mul2 = SE.getMulExpr(Ops2);
249 auto *Mul3 = SE.getMulExpr(Ops3);
250 auto *Mul4 = SE.getMulExpr(Ops4);
251 auto *Mul5 = SE.getMulExpr(Ops5);
252
253 EXPECT_EQ(Mul0, Mul1) << "Expected " << *Mul0 << " == " << *Mul1;
254 EXPECT_EQ(Mul1, Mul2) << "Expected " << *Mul1 << " == " << *Mul2;
255 EXPECT_EQ(Mul2, Mul3) << "Expected " << *Mul2 << " == " << *Mul3;
256 EXPECT_EQ(Mul3, Mul4) << "Expected " << *Mul3 << " == " << *Mul4;
257 EXPECT_EQ(Mul4, Mul5) << "Expected " << *Mul4 << " == " << *Mul5;
258 };
259
260 for (StringRef FuncName : {"f_2", "f_3", "f_4"})
261 runWithSE(
262 *M, FuncName, [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
263 CheckCommutativeMulExprs(SE, SE.getSCEV(getInstructionByName(F, "x")),
264 SE.getSCEV(getInstructionByName(F, "y")),
265 SE.getSCEV(getInstructionByName(F, "z")));
266 });
267 }
268
TEST_F(ScalarEvolutionsTest,CompareSCEVComplexity)269 TEST_F(ScalarEvolutionsTest, CompareSCEVComplexity) {
270 FunctionType *FTy =
271 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);
272 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);
273 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
274 BasicBlock *LoopBB = BasicBlock::Create(Context, "bb1", F);
275 BranchInst::Create(LoopBB, EntryBB);
276
277 auto *Ty = Type::getInt32Ty(Context);
278 SmallVector<Instruction*, 8> Muls(8), Acc(8), NextAcc(8);
279
280 Acc[0] = PHINode::Create(Ty, 2, "", LoopBB);
281 Acc[1] = PHINode::Create(Ty, 2, "", LoopBB);
282 Acc[2] = PHINode::Create(Ty, 2, "", LoopBB);
283 Acc[3] = PHINode::Create(Ty, 2, "", LoopBB);
284 Acc[4] = PHINode::Create(Ty, 2, "", LoopBB);
285 Acc[5] = PHINode::Create(Ty, 2, "", LoopBB);
286 Acc[6] = PHINode::Create(Ty, 2, "", LoopBB);
287 Acc[7] = PHINode::Create(Ty, 2, "", LoopBB);
288
289 for (int i = 0; i < 20; i++) {
290 Muls[0] = BinaryOperator::CreateMul(Acc[0], Acc[0], "", LoopBB);
291 NextAcc[0] = BinaryOperator::CreateAdd(Muls[0], Acc[4], "", LoopBB);
292 Muls[1] = BinaryOperator::CreateMul(Acc[1], Acc[1], "", LoopBB);
293 NextAcc[1] = BinaryOperator::CreateAdd(Muls[1], Acc[5], "", LoopBB);
294 Muls[2] = BinaryOperator::CreateMul(Acc[2], Acc[2], "", LoopBB);
295 NextAcc[2] = BinaryOperator::CreateAdd(Muls[2], Acc[6], "", LoopBB);
296 Muls[3] = BinaryOperator::CreateMul(Acc[3], Acc[3], "", LoopBB);
297 NextAcc[3] = BinaryOperator::CreateAdd(Muls[3], Acc[7], "", LoopBB);
298
299 Muls[4] = BinaryOperator::CreateMul(Acc[4], Acc[4], "", LoopBB);
300 NextAcc[4] = BinaryOperator::CreateAdd(Muls[4], Acc[0], "", LoopBB);
301 Muls[5] = BinaryOperator::CreateMul(Acc[5], Acc[5], "", LoopBB);
302 NextAcc[5] = BinaryOperator::CreateAdd(Muls[5], Acc[1], "", LoopBB);
303 Muls[6] = BinaryOperator::CreateMul(Acc[6], Acc[6], "", LoopBB);
304 NextAcc[6] = BinaryOperator::CreateAdd(Muls[6], Acc[2], "", LoopBB);
305 Muls[7] = BinaryOperator::CreateMul(Acc[7], Acc[7], "", LoopBB);
306 NextAcc[7] = BinaryOperator::CreateAdd(Muls[7], Acc[3], "", LoopBB);
307 Acc = NextAcc;
308 }
309
310 auto II = LoopBB->begin();
311 for (int i = 0; i < 8; i++) {
312 PHINode *Phi = cast<PHINode>(&*II++);
313 Phi->addIncoming(Acc[i], LoopBB);
314 Phi->addIncoming(UndefValue::get(Ty), EntryBB);
315 }
316
317 BasicBlock *ExitBB = BasicBlock::Create(Context, "bb2", F);
318 BranchInst::Create(LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)),
319 LoopBB);
320
321 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
322 Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB);
323 Acc[2] = BinaryOperator::CreateAdd(Acc[4], Acc[5], "", ExitBB);
324 Acc[3] = BinaryOperator::CreateAdd(Acc[6], Acc[7], "", ExitBB);
325 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
326 Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB);
327 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
328
329 ReturnInst::Create(Context, nullptr, ExitBB);
330
331 ScalarEvolution SE = buildSE(*F);
332
333 EXPECT_NE(nullptr, SE.getSCEV(Acc[0]));
334 }
335
TEST_F(ScalarEvolutionsTest,CompareValueComplexity)336 TEST_F(ScalarEvolutionsTest, CompareValueComplexity) {
337 IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(Context);
338 PointerType *IntPtrPtrTy = IntPtrTy->getPointerTo();
339
340 FunctionType *FTy =
341 FunctionType::get(Type::getVoidTy(Context), {IntPtrTy, IntPtrTy}, false);
342 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);
343 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
344
345 Value *X = &*F->arg_begin();
346 Value *Y = &*std::next(F->arg_begin());
347
348 const int ValueDepth = 10;
349 for (int i = 0; i < ValueDepth; i++) {
350 X = new LoadInst(IntPtrTy, new IntToPtrInst(X, IntPtrPtrTy, "", EntryBB),
351 "",
352 /*isVolatile*/ false, EntryBB);
353 Y = new LoadInst(IntPtrTy, new IntToPtrInst(Y, IntPtrPtrTy, "", EntryBB),
354 "",
355 /*isVolatile*/ false, EntryBB);
356 }
357
358 auto *MulA = BinaryOperator::CreateMul(X, Y, "", EntryBB);
359 auto *MulB = BinaryOperator::CreateMul(Y, X, "", EntryBB);
360 ReturnInst::Create(Context, nullptr, EntryBB);
361
362 // This test isn't checking for correctness. Today making A and B resolve to
363 // the same SCEV would require deeper searching in CompareValueComplexity,
364 // which will slow down compilation. However, this test can fail (with LLVM's
365 // behavior still being correct) if we ever have a smarter
366 // CompareValueComplexity that is both fast and more accurate.
367
368 ScalarEvolution SE = buildSE(*F);
369 auto *A = SE.getSCEV(MulA);
370 auto *B = SE.getSCEV(MulB);
371 EXPECT_NE(A, B);
372 }
373
TEST_F(ScalarEvolutionsTest,SCEVAddExpr)374 TEST_F(ScalarEvolutionsTest, SCEVAddExpr) {
375 Type *Ty32 = Type::getInt32Ty(Context);
376 Type *ArgTys[] = {Type::getInt64Ty(Context), Ty32};
377
378 FunctionType *FTy =
379 FunctionType::get(Type::getVoidTy(Context), ArgTys, false);
380 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);
381
382 Argument *A1 = &*F->arg_begin();
383 Argument *A2 = &*(std::next(F->arg_begin()));
384 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
385
386 Instruction *Trunc = CastInst::CreateTruncOrBitCast(A1, Ty32, "", EntryBB);
387 Instruction *Mul1 = BinaryOperator::CreateMul(Trunc, A2, "", EntryBB);
388 Instruction *Add1 = BinaryOperator::CreateAdd(Mul1, Trunc, "", EntryBB);
389 Mul1 = BinaryOperator::CreateMul(Add1, Trunc, "", EntryBB);
390 Instruction *Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB);
391 // FIXME: The size of this is arbitrary and doesn't seem to change the
392 // result, but SCEV will do quadratic work for these so a large number here
393 // will be extremely slow. We should revisit what and how this is testing
394 // SCEV.
395 for (int i = 0; i < 10; i++) {
396 Mul1 = BinaryOperator::CreateMul(Add2, Add1, "", EntryBB);
397 Add1 = Add2;
398 Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB);
399 }
400
401 ReturnInst::Create(Context, nullptr, EntryBB);
402 ScalarEvolution SE = buildSE(*F);
403 EXPECT_NE(nullptr, SE.getSCEV(Mul1));
404 }
405
GetInstByName(Function & F,StringRef Name)406 static Instruction &GetInstByName(Function &F, StringRef Name) {
407 for (auto &I : instructions(F))
408 if (I.getName() == Name)
409 return I;
410 llvm_unreachable("Could not find instructions!");
411 }
412
TEST_F(ScalarEvolutionsTest,SCEVNormalization)413 TEST_F(ScalarEvolutionsTest, SCEVNormalization) {
414 LLVMContext C;
415 SMDiagnostic Err;
416 std::unique_ptr<Module> M = parseAssemblyString(
417 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
418 " "
419 "@var_0 = external global i32, align 4"
420 "@var_1 = external global i32, align 4"
421 "@var_2 = external global i32, align 4"
422 " "
423 "declare i32 @unknown(i32, i32, i32)"
424 " "
425 "define void @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) "
426 " local_unnamed_addr { "
427 "entry: "
428 " br label %loop.ph "
429 " "
430 "loop.ph: "
431 " br label %loop "
432 " "
433 "loop: "
434 " %iv0 = phi i32 [ %iv0.inc, %loop ], [ 0, %loop.ph ] "
435 " %iv1 = phi i32 [ %iv1.inc, %loop ], [ -2147483648, %loop.ph ] "
436 " %iv0.inc = add i32 %iv0, 1 "
437 " %iv1.inc = add i32 %iv1, 3 "
438 " br i1 undef, label %for.end.loopexit, label %loop "
439 " "
440 "for.end.loopexit: "
441 " ret void "
442 "} "
443 " "
444 "define void @f_2(i32 %a, i32 %b, i32 %c, i32 %d) "
445 " local_unnamed_addr { "
446 "entry: "
447 " br label %loop_0 "
448 " "
449 "loop_0: "
450 " br i1 undef, label %loop_0, label %loop_1 "
451 " "
452 "loop_1: "
453 " br i1 undef, label %loop_2, label %loop_1 "
454 " "
455 " "
456 "loop_2: "
457 " br i1 undef, label %end, label %loop_2 "
458 " "
459 "end: "
460 " ret void "
461 "} "
462 ,
463 Err, C);
464
465 assert(M && "Could not parse module?");
466 assert(!verifyModule(*M) && "Must have been well formed!");
467
468 runWithSE(*M, "f_1", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
469 auto &I0 = GetInstByName(F, "iv0");
470 auto &I1 = *I0.getNextNode();
471
472 auto *S0 = cast<SCEVAddRecExpr>(SE.getSCEV(&I0));
473 PostIncLoopSet Loops;
474 Loops.insert(S0->getLoop());
475 auto *N0 = normalizeForPostIncUse(S0, Loops, SE);
476 auto *D0 = denormalizeForPostIncUse(N0, Loops, SE);
477 EXPECT_EQ(S0, D0) << *S0 << " " << *D0;
478
479 auto *S1 = cast<SCEVAddRecExpr>(SE.getSCEV(&I1));
480 Loops.clear();
481 Loops.insert(S1->getLoop());
482 auto *N1 = normalizeForPostIncUse(S1, Loops, SE);
483 auto *D1 = denormalizeForPostIncUse(N1, Loops, SE);
484 EXPECT_EQ(S1, D1) << *S1 << " " << *D1;
485 });
486
487 runWithSE(*M, "f_2", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
488 auto *L2 = *LI.begin();
489 auto *L1 = *std::next(LI.begin());
490 auto *L0 = *std::next(LI.begin(), 2);
491
492 auto GetAddRec = [&SE](const Loop *L, std::initializer_list<const SCEV *> Ops) {
493 SmallVector<const SCEV *, 4> OpsCopy(Ops);
494 return SE.getAddRecExpr(OpsCopy, L, SCEV::FlagAnyWrap);
495 };
496
497 auto GetAdd = [&SE](std::initializer_list<const SCEV *> Ops) {
498 SmallVector<const SCEV *, 4> OpsCopy(Ops);
499 return SE.getAddExpr(OpsCopy, SCEV::FlagAnyWrap);
500 };
501
502 // We first populate the AddRecs vector with a few "interesting" SCEV
503 // expressions, and then we go through the list and assert that each
504 // expression in it has an invertible normalization.
505
506 std::vector<const SCEV *> Exprs;
507 {
508 const SCEV *V0 = SE.getSCEV(&*F.arg_begin());
509 const SCEV *V1 = SE.getSCEV(&*std::next(F.arg_begin(), 1));
510 const SCEV *V2 = SE.getSCEV(&*std::next(F.arg_begin(), 2));
511 const SCEV *V3 = SE.getSCEV(&*std::next(F.arg_begin(), 3));
512
513 Exprs.push_back(GetAddRec(L0, {V0})); // 0
514 Exprs.push_back(GetAddRec(L0, {V0, V1})); // 1
515 Exprs.push_back(GetAddRec(L0, {V0, V1, V2})); // 2
516 Exprs.push_back(GetAddRec(L0, {V0, V1, V2, V3})); // 3
517
518 Exprs.push_back(
519 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[3], Exprs[0]})); // 4
520 Exprs.push_back(
521 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[0], Exprs[3]})); // 5
522 Exprs.push_back(
523 GetAddRec(L1, {Exprs[1], Exprs[3], Exprs[3], Exprs[1]})); // 6
524
525 Exprs.push_back(GetAdd({Exprs[6], Exprs[3], V2})); // 7
526
527 Exprs.push_back(
528 GetAddRec(L2, {Exprs[4], Exprs[3], Exprs[3], Exprs[5]})); // 8
529
530 Exprs.push_back(
531 GetAddRec(L2, {Exprs[4], Exprs[6], Exprs[7], Exprs[3], V0})); // 9
532 }
533
534 std::vector<PostIncLoopSet> LoopSets;
535 for (int i = 0; i < 8; i++) {
536 LoopSets.emplace_back();
537 if (i & 1)
538 LoopSets.back().insert(L0);
539 if (i & 2)
540 LoopSets.back().insert(L1);
541 if (i & 4)
542 LoopSets.back().insert(L2);
543 }
544
545 for (const auto &LoopSet : LoopSets)
546 for (auto *S : Exprs) {
547 {
548 auto *N = llvm::normalizeForPostIncUse(S, LoopSet, SE);
549 auto *D = llvm::denormalizeForPostIncUse(N, LoopSet, SE);
550
551 // Normalization and then denormalizing better give us back the same
552 // value.
553 EXPECT_EQ(S, D) << "S = " << *S << " D = " << *D << " N = " << *N;
554 }
555 {
556 auto *D = llvm::denormalizeForPostIncUse(S, LoopSet, SE);
557 auto *N = llvm::normalizeForPostIncUse(D, LoopSet, SE);
558
559 // Denormalization and then normalizing better give us back the same
560 // value.
561 EXPECT_EQ(S, N) << "S = " << *S << " N = " << *N;
562 }
563 }
564 });
565 }
566
567 // Expect the call of getZeroExtendExpr will not cost exponential time.
TEST_F(ScalarEvolutionsTest,SCEVZeroExtendExpr)568 TEST_F(ScalarEvolutionsTest, SCEVZeroExtendExpr) {
569 LLVMContext C;
570 SMDiagnostic Err;
571
572 // Generate a function like below:
573 // define void @foo() {
574 // entry:
575 // br label %for.cond
576 //
577 // for.cond:
578 // %0 = phi i64 [ 100, %entry ], [ %dec, %for.inc ]
579 // %cmp = icmp sgt i64 %0, 90
580 // br i1 %cmp, label %for.inc, label %for.cond1
581 //
582 // for.inc:
583 // %dec = add nsw i64 %0, -1
584 // br label %for.cond
585 //
586 // for.cond1:
587 // %1 = phi i64 [ 100, %for.cond ], [ %dec5, %for.inc2 ]
588 // %cmp3 = icmp sgt i64 %1, 90
589 // br i1 %cmp3, label %for.inc2, label %for.cond4
590 //
591 // for.inc2:
592 // %dec5 = add nsw i64 %1, -1
593 // br label %for.cond1
594 //
595 // ......
596 //
597 // for.cond89:
598 // %19 = phi i64 [ 100, %for.cond84 ], [ %dec94, %for.inc92 ]
599 // %cmp93 = icmp sgt i64 %19, 90
600 // br i1 %cmp93, label %for.inc92, label %for.end
601 //
602 // for.inc92:
603 // %dec94 = add nsw i64 %19, -1
604 // br label %for.cond89
605 //
606 // for.end:
607 // %gep = getelementptr i8, i8* null, i64 %dec
608 // %gep6 = getelementptr i8, i8* %gep, i64 %dec5
609 // ......
610 // %gep95 = getelementptr i8, i8* %gep91, i64 %dec94
611 // ret void
612 // }
613 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false);
614 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", M);
615
616 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
617 BasicBlock *CondBB = BasicBlock::Create(Context, "for.cond", F);
618 BasicBlock *EndBB = BasicBlock::Create(Context, "for.end", F);
619 BranchInst::Create(CondBB, EntryBB);
620 BasicBlock *PrevBB = EntryBB;
621
622 Type *I64Ty = Type::getInt64Ty(Context);
623 Type *I8Ty = Type::getInt8Ty(Context);
624 Type *I8PtrTy = Type::getInt8PtrTy(Context);
625 Value *Accum = Constant::getNullValue(I8PtrTy);
626 int Iters = 20;
627 for (int i = 0; i < Iters; i++) {
628 BasicBlock *IncBB = BasicBlock::Create(Context, "for.inc", F, EndBB);
629 auto *PN = PHINode::Create(I64Ty, 2, "", CondBB);
630 PN->addIncoming(ConstantInt::get(Context, APInt(64, 100)), PrevBB);
631 auto *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_SGT, PN,
632 ConstantInt::get(Context, APInt(64, 90)), "cmp",
633 CondBB);
634 BasicBlock *NextBB;
635 if (i != Iters - 1)
636 NextBB = BasicBlock::Create(Context, "for.cond", F, EndBB);
637 else
638 NextBB = EndBB;
639 BranchInst::Create(IncBB, NextBB, Cmp, CondBB);
640 auto *Dec = BinaryOperator::CreateNSWAdd(
641 PN, ConstantInt::get(Context, APInt(64, -1)), "dec", IncBB);
642 PN->addIncoming(Dec, IncBB);
643 BranchInst::Create(CondBB, IncBB);
644
645 Accum = GetElementPtrInst::Create(I8Ty, Accum, PN, "gep", EndBB);
646
647 PrevBB = CondBB;
648 CondBB = NextBB;
649 }
650 ReturnInst::Create(Context, nullptr, EndBB);
651 ScalarEvolution SE = buildSE(*F);
652 const SCEV *S = SE.getSCEV(Accum);
653 Type *I128Ty = Type::getInt128Ty(Context);
654 SE.getZeroExtendExpr(S, I128Ty);
655 }
656
657 // Make sure that SCEV invalidates exit limits after invalidating the values it
658 // depends on when we forget a loop.
TEST_F(ScalarEvolutionsTest,SCEVExitLimitForgetLoop)659 TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetLoop) {
660 /*
661 * Create the following code:
662 * func(i64 addrspace(10)* %arg)
663 * top:
664 * br label %L.ph
665 * L.ph:
666 * br label %L
667 * L:
668 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
669 * %add = add i64 %phi2, 1
670 * %cond = icmp slt i64 %add, 1000; then becomes 2000.
671 * br i1 %cond, label %post, label %L2
672 * post:
673 * ret void
674 *
675 */
676
677 // Create a module with non-integral pointers in it's datalayout
678 Module NIM("nonintegral", Context);
679 std::string DataLayout = M.getDataLayoutStr();
680 if (!DataLayout.empty())
681 DataLayout += "-";
682 DataLayout += "ni:10";
683 NIM.setDataLayout(DataLayout);
684
685 Type *T_int64 = Type::getInt64Ty(Context);
686 Type *T_pint64 = T_int64->getPointerTo(10);
687
688 FunctionType *FTy =
689 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
690 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM);
691
692 BasicBlock *Top = BasicBlock::Create(Context, "top", F);
693 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
694 BasicBlock *L = BasicBlock::Create(Context, "L", F);
695 BasicBlock *Post = BasicBlock::Create(Context, "post", F);
696
697 IRBuilder<> Builder(Top);
698 Builder.CreateBr(LPh);
699
700 Builder.SetInsertPoint(LPh);
701 Builder.CreateBr(L);
702
703 Builder.SetInsertPoint(L);
704 PHINode *Phi = Builder.CreatePHI(T_int64, 2);
705 auto *Add = cast<Instruction>(
706 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));
707 auto *Limit = ConstantInt::get(T_int64, 1000);
708 auto *Cond = cast<Instruction>(
709 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond"));
710 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post));
711 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
712 Phi->addIncoming(Add, L);
713
714 Builder.SetInsertPoint(Post);
715 Builder.CreateRetVoid();
716
717 ScalarEvolution SE = buildSE(*F);
718 auto *Loop = LI->getLoopFor(L);
719 const SCEV *EC = SE.getBackedgeTakenCount(Loop);
720 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC));
721 EXPECT_TRUE(isa<SCEVConstant>(EC));
722 EXPECT_EQ(cast<SCEVConstant>(EC)->getAPInt().getLimitedValue(), 999u);
723
724 // The add recurrence {5,+,1} does not correspond to any PHI in the IR, and
725 // that is relevant to this test.
726 auto *Five = SE.getConstant(APInt(/*numBits=*/64, 5));
727 auto *AR =
728 SE.getAddRecExpr(Five, SE.getOne(T_int64), Loop, SCEV::FlagAnyWrap);
729 const SCEV *ARAtLoopExit = SE.getSCEVAtScope(AR, nullptr);
730 EXPECT_FALSE(isa<SCEVCouldNotCompute>(ARAtLoopExit));
731 EXPECT_TRUE(isa<SCEVConstant>(ARAtLoopExit));
732 EXPECT_EQ(cast<SCEVConstant>(ARAtLoopExit)->getAPInt().getLimitedValue(),
733 1004u);
734
735 SE.forgetLoop(Loop);
736 Br->eraseFromParent();
737 Cond->eraseFromParent();
738
739 Builder.SetInsertPoint(L);
740 auto *NewCond = Builder.CreateICmp(
741 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond");
742 Builder.CreateCondBr(NewCond, L, Post);
743 const SCEV *NewEC = SE.getBackedgeTakenCount(Loop);
744 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC));
745 EXPECT_TRUE(isa<SCEVConstant>(NewEC));
746 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u);
747 const SCEV *NewARAtLoopExit = SE.getSCEVAtScope(AR, nullptr);
748 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewARAtLoopExit));
749 EXPECT_TRUE(isa<SCEVConstant>(NewARAtLoopExit));
750 EXPECT_EQ(cast<SCEVConstant>(NewARAtLoopExit)->getAPInt().getLimitedValue(),
751 2004u);
752 }
753
754 // Make sure that SCEV invalidates exit limits after invalidating the values it
755 // depends on when we forget a value.
TEST_F(ScalarEvolutionsTest,SCEVExitLimitForgetValue)756 TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetValue) {
757 /*
758 * Create the following code:
759 * func(i64 addrspace(10)* %arg)
760 * top:
761 * br label %L.ph
762 * L.ph:
763 * %load = load i64 addrspace(10)* %arg
764 * br label %L
765 * L:
766 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
767 * %add = add i64 %phi2, 1
768 * %cond = icmp slt i64 %add, %load ; then becomes 2000.
769 * br i1 %cond, label %post, label %L2
770 * post:
771 * ret void
772 *
773 */
774
775 // Create a module with non-integral pointers in it's datalayout
776 Module NIM("nonintegral", Context);
777 std::string DataLayout = M.getDataLayoutStr();
778 if (!DataLayout.empty())
779 DataLayout += "-";
780 DataLayout += "ni:10";
781 NIM.setDataLayout(DataLayout);
782
783 Type *T_int64 = Type::getInt64Ty(Context);
784 Type *T_pint64 = T_int64->getPointerTo(10);
785
786 FunctionType *FTy =
787 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
788 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM);
789
790 Argument *Arg = &*F->arg_begin();
791
792 BasicBlock *Top = BasicBlock::Create(Context, "top", F);
793 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
794 BasicBlock *L = BasicBlock::Create(Context, "L", F);
795 BasicBlock *Post = BasicBlock::Create(Context, "post", F);
796
797 IRBuilder<> Builder(Top);
798 Builder.CreateBr(LPh);
799
800 Builder.SetInsertPoint(LPh);
801 auto *Load = cast<Instruction>(Builder.CreateLoad(T_int64, Arg, "load"));
802 Builder.CreateBr(L);
803
804 Builder.SetInsertPoint(L);
805 PHINode *Phi = Builder.CreatePHI(T_int64, 2);
806 auto *Add = cast<Instruction>(
807 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));
808 auto *Cond = cast<Instruction>(
809 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Load, "cond"));
810 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post));
811 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
812 Phi->addIncoming(Add, L);
813
814 Builder.SetInsertPoint(Post);
815 Builder.CreateRetVoid();
816
817 ScalarEvolution SE = buildSE(*F);
818 auto *Loop = LI->getLoopFor(L);
819 const SCEV *EC = SE.getBackedgeTakenCount(Loop);
820 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC));
821 EXPECT_FALSE(isa<SCEVConstant>(EC));
822
823 SE.forgetValue(Load);
824 Br->eraseFromParent();
825 Cond->eraseFromParent();
826 Load->eraseFromParent();
827
828 Builder.SetInsertPoint(L);
829 auto *NewCond = Builder.CreateICmp(
830 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond");
831 Builder.CreateCondBr(NewCond, L, Post);
832 const SCEV *NewEC = SE.getBackedgeTakenCount(Loop);
833 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC));
834 EXPECT_TRUE(isa<SCEVConstant>(NewEC));
835 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u);
836 }
837
TEST_F(ScalarEvolutionsTest,SCEVAddRecFromPHIwithLargeConstants)838 TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstants) {
839 // Reference: https://reviews.llvm.org/D37265
840 // Make sure that SCEV does not blow up when constructing an AddRec
841 // with predicates for a phi with the update pattern:
842 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum
843 // when either the initial value of the Phi or the InvariantAccum are
844 // constants that are too large to fit in an ix but are zero when truncated to
845 // ix.
846 FunctionType *FTy =
847 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);
848 Function *F =
849 Function::Create(FTy, Function::ExternalLinkage, "addrecphitest", M);
850
851 /*
852 Create IR:
853 entry:
854 br label %loop
855 loop:
856 %0 = phi i64 [-9223372036854775808, %entry], [%3, %loop]
857 %1 = shl i64 %0, 32
858 %2 = ashr exact i64 %1, 32
859 %3 = add i64 %2, -9223372036854775808
860 br i1 undef, label %exit, label %loop
861 exit:
862 ret void
863 */
864 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
865 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);
866 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);
867
868 // entry:
869 BranchInst::Create(LoopBB, EntryBB);
870 // loop:
871 auto *MinInt64 =
872 ConstantInt::get(Context, APInt(64, 0x8000000000000000U, true));
873 auto *Int64_32 = ConstantInt::get(Context, APInt(64, 32));
874 auto *Br = BranchInst::Create(
875 LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB);
876 auto *Phi = PHINode::Create(Type::getInt64Ty(Context), 2, "", Br);
877 auto *Shl = BinaryOperator::CreateShl(Phi, Int64_32, "", Br);
878 auto *AShr = BinaryOperator::CreateExactAShr(Shl, Int64_32, "", Br);
879 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt64, "", Br);
880 Phi->addIncoming(MinInt64, EntryBB);
881 Phi->addIncoming(Add, LoopBB);
882 // exit:
883 ReturnInst::Create(Context, nullptr, ExitBB);
884
885 // Make sure that SCEV doesn't blow up
886 ScalarEvolution SE = buildSE(*F);
887 SCEVUnionPredicate Preds;
888 const SCEV *Expr = SE.getSCEV(Phi);
889 EXPECT_NE(nullptr, Expr);
890 EXPECT_TRUE(isa<SCEVUnknown>(Expr));
891 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(Expr));
892 }
893
TEST_F(ScalarEvolutionsTest,SCEVAddRecFromPHIwithLargeConstantAccum)894 TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstantAccum) {
895 // Make sure that SCEV does not blow up when constructing an AddRec
896 // with predicates for a phi with the update pattern:
897 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum
898 // when the InvariantAccum is a constant that is too large to fit in an
899 // ix but are zero when truncated to ix, and the initial value of the
900 // phi is not a constant.
901 Type *Int32Ty = Type::getInt32Ty(Context);
902 SmallVector<Type *, 1> Types;
903 Types.push_back(Int32Ty);
904 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false);
905 Function *F =
906 Function::Create(FTy, Function::ExternalLinkage, "addrecphitest", M);
907
908 /*
909 Create IR:
910 define @addrecphitest(i32)
911 entry:
912 br label %loop
913 loop:
914 %1 = phi i32 [%0, %entry], [%4, %loop]
915 %2 = shl i32 %1, 16
916 %3 = ashr exact i32 %2, 16
917 %4 = add i32 %3, -2147483648
918 br i1 undef, label %exit, label %loop
919 exit:
920 ret void
921 */
922 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
923 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);
924 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);
925
926 // entry:
927 BranchInst::Create(LoopBB, EntryBB);
928 // loop:
929 auto *MinInt32 = ConstantInt::get(Context, APInt(32, 0x80000000U, true));
930 auto *Int32_16 = ConstantInt::get(Context, APInt(32, 16));
931 auto *Br = BranchInst::Create(
932 LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB);
933 auto *Phi = PHINode::Create(Int32Ty, 2, "", Br);
934 auto *Shl = BinaryOperator::CreateShl(Phi, Int32_16, "", Br);
935 auto *AShr = BinaryOperator::CreateExactAShr(Shl, Int32_16, "", Br);
936 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt32, "", Br);
937 auto *Arg = &*(F->arg_begin());
938 Phi->addIncoming(Arg, EntryBB);
939 Phi->addIncoming(Add, LoopBB);
940 // exit:
941 ReturnInst::Create(Context, nullptr, ExitBB);
942
943 // Make sure that SCEV doesn't blow up
944 ScalarEvolution SE = buildSE(*F);
945 SCEVUnionPredicate Preds;
946 const SCEV *Expr = SE.getSCEV(Phi);
947 EXPECT_NE(nullptr, Expr);
948 EXPECT_TRUE(isa<SCEVUnknown>(Expr));
949 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(Expr));
950 }
951
TEST_F(ScalarEvolutionsTest,SCEVFoldSumOfTruncs)952 TEST_F(ScalarEvolutionsTest, SCEVFoldSumOfTruncs) {
953 // Verify that the following SCEV gets folded to a zero:
954 // (-1 * (trunc i64 (-1 * %0) to i32)) + (-1 * (trunc i64 %0 to i32)
955 Type *ArgTy = Type::getInt64Ty(Context);
956 Type *Int32Ty = Type::getInt32Ty(Context);
957 SmallVector<Type *, 1> Types;
958 Types.push_back(ArgTy);
959 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false);
960 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);
961 BasicBlock *BB = BasicBlock::Create(Context, "entry", F);
962 ReturnInst::Create(Context, nullptr, BB);
963
964 ScalarEvolution SE = buildSE(*F);
965
966 auto *Arg = &*(F->arg_begin());
967 const auto *ArgSCEV = SE.getSCEV(Arg);
968
969 // Build the SCEV
970 const auto *A0 = SE.getNegativeSCEV(ArgSCEV);
971 const auto *A1 = SE.getTruncateExpr(A0, Int32Ty);
972 const auto *A = SE.getNegativeSCEV(A1);
973
974 const auto *B0 = SE.getTruncateExpr(ArgSCEV, Int32Ty);
975 const auto *B = SE.getNegativeSCEV(B0);
976
977 const auto *Expr = SE.getAddExpr(A, B);
978 // Verify that the SCEV was folded to 0
979 const auto *ZeroConst = SE.getConstant(Int32Ty, 0);
980 EXPECT_EQ(Expr, ZeroConst);
981 }
982
983 // Check logic of SCEV expression size computation.
TEST_F(ScalarEvolutionsTest,SCEVComputeExpressionSize)984 TEST_F(ScalarEvolutionsTest, SCEVComputeExpressionSize) {
985 /*
986 * Create the following code:
987 * void func(i64 %a, i64 %b)
988 * entry:
989 * %s1 = add i64 %a, 1
990 * %s2 = udiv i64 %s1, %b
991 * br label %exit
992 * exit:
993 * ret
994 */
995
996 // Create a module.
997 Module M("SCEVComputeExpressionSize", Context);
998
999 Type *T_int64 = Type::getInt64Ty(Context);
1000
1001 FunctionType *FTy =
1002 FunctionType::get(Type::getVoidTy(Context), { T_int64, T_int64 }, false);
1003 Function *F = Function::Create(FTy, Function::ExternalLinkage, "func", M);
1004 Argument *A = &*F->arg_begin();
1005 Argument *B = &*std::next(F->arg_begin());
1006 ConstantInt *C = ConstantInt::get(Context, APInt(64, 1));
1007
1008 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
1009 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
1010
1011 IRBuilder<> Builder(Entry);
1012 auto *S1 = cast<Instruction>(Builder.CreateAdd(A, C, "s1"));
1013 auto *S2 = cast<Instruction>(Builder.CreateUDiv(S1, B, "s2"));
1014 Builder.CreateBr(Exit);
1015
1016 Builder.SetInsertPoint(Exit);
1017 Builder.CreateRetVoid();
1018
1019 ScalarEvolution SE = buildSE(*F);
1020 // Get S2 first to move it to cache.
1021 const SCEV *AS = SE.getSCEV(A);
1022 const SCEV *BS = SE.getSCEV(B);
1023 const SCEV *CS = SE.getSCEV(C);
1024 const SCEV *S1S = SE.getSCEV(S1);
1025 const SCEV *S2S = SE.getSCEV(S2);
1026 EXPECT_EQ(AS->getExpressionSize(), 1u);
1027 EXPECT_EQ(BS->getExpressionSize(), 1u);
1028 EXPECT_EQ(CS->getExpressionSize(), 1u);
1029 EXPECT_EQ(S1S->getExpressionSize(), 3u);
1030 EXPECT_EQ(S2S->getExpressionSize(), 5u);
1031 }
1032
TEST_F(ScalarEvolutionsTest,SCEVLoopDecIntrinsic)1033 TEST_F(ScalarEvolutionsTest, SCEVLoopDecIntrinsic) {
1034 LLVMContext C;
1035 SMDiagnostic Err;
1036 std::unique_ptr<Module> M = parseAssemblyString(
1037 "define void @foo(i32 %N) { "
1038 "entry: "
1039 " %cmp3 = icmp sgt i32 %N, 0 "
1040 " br i1 %cmp3, label %for.body, label %for.cond.cleanup "
1041 "for.cond.cleanup: "
1042 " ret void "
1043 "for.body: "
1044 " %i.04 = phi i32 [ %inc, %for.body ], [ 100, %entry ] "
1045 " %inc = call i32 @llvm.loop.decrement.reg.i32.i32.i32(i32 %i.04, i32 1) "
1046 " %exitcond = icmp ne i32 %inc, 0 "
1047 " br i1 %exitcond, label %for.cond.cleanup, label %for.body "
1048 "} "
1049 "declare i32 @llvm.loop.decrement.reg.i32.i32.i32(i32, i32) ",
1050 Err, C);
1051
1052 ASSERT_TRUE(M && "Could not parse module?");
1053 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1054
1055 runWithSE(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1056 auto *ScevInc = SE.getSCEV(getInstructionByName(F, "inc"));
1057 EXPECT_TRUE(isa<SCEVAddRecExpr>(ScevInc));
1058 });
1059 }
1060
TEST_F(ScalarEvolutionsTest,SCEVComputeConstantDifference)1061 TEST_F(ScalarEvolutionsTest, SCEVComputeConstantDifference) {
1062 LLVMContext C;
1063 SMDiagnostic Err;
1064 std::unique_ptr<Module> M = parseAssemblyString(
1065 "define void @foo(i32 %sz, i32 %pp) { "
1066 "entry: "
1067 " %v0 = add i32 %pp, 0 "
1068 " %v3 = add i32 %pp, 3 "
1069 " br label %loop.body "
1070 "loop.body: "
1071 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] "
1072 " %xa = add nsw i32 %iv, %v0 "
1073 " %yy = add nsw i32 %iv, %v3 "
1074 " %xb = sub nsw i32 %yy, 3 "
1075 " %iv.next = add nsw i32 %iv, 1 "
1076 " %cmp = icmp sle i32 %iv.next, %sz "
1077 " br i1 %cmp, label %loop.body, label %exit "
1078 "exit: "
1079 " ret void "
1080 "} ",
1081 Err, C);
1082
1083 ASSERT_TRUE(M && "Could not parse module?");
1084 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1085
1086 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1087 auto *ScevV0 = SE.getSCEV(getInstructionByName(F, "v0")); // %pp
1088 auto *ScevV3 = SE.getSCEV(getInstructionByName(F, "v3")); // (3 + %pp)
1089 auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1}
1090 auto *ScevXA = SE.getSCEV(getInstructionByName(F, "xa")); // {%pp,+,1}
1091 auto *ScevYY = SE.getSCEV(getInstructionByName(F, "yy")); // {(3 + %pp),+,1}
1092 auto *ScevXB = SE.getSCEV(getInstructionByName(F, "xb")); // {%pp,+,1}
1093 auto *ScevIVNext = SE.getSCEV(getInstructionByName(F, "iv.next")); // {1,+,1}
1094
1095 auto diff = [&SE](const SCEV *LHS, const SCEV *RHS) -> Optional<int> {
1096 auto ConstantDiffOrNone = computeConstantDifference(SE, LHS, RHS);
1097 if (!ConstantDiffOrNone)
1098 return None;
1099
1100 auto ExtDiff = ConstantDiffOrNone->getSExtValue();
1101 int Diff = ExtDiff;
1102 assert(Diff == ExtDiff && "Integer overflow");
1103 return Diff;
1104 };
1105
1106 EXPECT_EQ(diff(ScevV3, ScevV0), 3);
1107 EXPECT_EQ(diff(ScevV0, ScevV3), -3);
1108 EXPECT_EQ(diff(ScevV0, ScevV0), 0);
1109 EXPECT_EQ(diff(ScevV3, ScevV3), 0);
1110 EXPECT_EQ(diff(ScevIV, ScevIV), 0);
1111 EXPECT_EQ(diff(ScevXA, ScevXB), 0);
1112 EXPECT_EQ(diff(ScevXA, ScevYY), -3);
1113 EXPECT_EQ(diff(ScevYY, ScevXB), 3);
1114 EXPECT_EQ(diff(ScevIV, ScevIVNext), -1);
1115 EXPECT_EQ(diff(ScevIVNext, ScevIV), 1);
1116 EXPECT_EQ(diff(ScevIVNext, ScevIVNext), 0);
1117 EXPECT_EQ(diff(ScevV0, ScevIV), None);
1118 EXPECT_EQ(diff(ScevIVNext, ScevV3), None);
1119 EXPECT_EQ(diff(ScevYY, ScevV3), None);
1120 });
1121 }
1122
1123 } // end namespace llvm
1124