1 //===- ScalarEvolutionsTest.cpp - ScalarEvolution unit tests --------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "llvm/ADT/SmallVector.h"
11 #include "llvm/Analysis/AssumptionCache.h"
12 #include "llvm/Analysis/LoopInfo.h"
13 #include "llvm/Analysis/ScalarEvolutionExpander.h"
14 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
15 #include "llvm/Analysis/TargetLibraryInfo.h"
16 #include "llvm/AsmParser/Parser.h"
17 #include "llvm/IR/Constants.h"
18 #include "llvm/IR/Dominators.h"
19 #include "llvm/IR/GlobalVariable.h"
20 #include "llvm/IR/IRBuilder.h"
21 #include "llvm/IR/InstIterator.h"
22 #include "llvm/IR/LLVMContext.h"
23 #include "llvm/IR/LegacyPassManager.h"
24 #include "llvm/IR/Module.h"
25 #include "llvm/IR/Verifier.h"
26 #include "llvm/Support/SourceMgr.h"
27 #include "gtest/gtest.h"
28
29 namespace llvm {
30 namespace {
31
32 // We use this fixture to ensure that we clean up ScalarEvolution before
33 // deleting the PassManager.
34 class ScalarEvolutionsTest : public testing::Test {
35 protected:
36 LLVMContext Context;
37 Module M;
38 TargetLibraryInfoImpl TLII;
39 TargetLibraryInfo TLI;
40
41 std::unique_ptr<AssumptionCache> AC;
42 std::unique_ptr<DominatorTree> DT;
43 std::unique_ptr<LoopInfo> LI;
44
ScalarEvolutionsTest()45 ScalarEvolutionsTest() : M("", Context), TLII(), TLI(TLII) {}
46
buildSE(Function & F)47 ScalarEvolution buildSE(Function &F) {
48 AC.reset(new AssumptionCache(F));
49 DT.reset(new DominatorTree(F));
50 LI.reset(new LoopInfo(*DT));
51 return ScalarEvolution(F, TLI, *AC, *DT, *LI);
52 }
53
runWithSE(Module & M,StringRef FuncName,function_ref<void (Function & F,LoopInfo & LI,ScalarEvolution & SE)> Test)54 void runWithSE(
55 Module &M, StringRef FuncName,
56 function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {
57 auto *F = M.getFunction(FuncName);
58 ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
59 ScalarEvolution SE = buildSE(*F);
60 Test(*F, *LI, SE);
61 }
62 };
63
TEST_F(ScalarEvolutionsTest,SCEVUnknownRAUW)64 TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) {
65 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),
66 std::vector<Type *>(), false);
67 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
68 BasicBlock *BB = BasicBlock::Create(Context, "entry", F);
69 ReturnInst::Create(Context, nullptr, BB);
70
71 Type *Ty = Type::getInt1Ty(Context);
72 Constant *Init = Constant::getNullValue(Ty);
73 Value *V0 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V0");
74 Value *V1 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V1");
75 Value *V2 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V2");
76
77 ScalarEvolution SE = buildSE(*F);
78
79 const SCEV *S0 = SE.getSCEV(V0);
80 const SCEV *S1 = SE.getSCEV(V1);
81 const SCEV *S2 = SE.getSCEV(V2);
82
83 const SCEV *P0 = SE.getAddExpr(S0, S0);
84 const SCEV *P1 = SE.getAddExpr(S1, S1);
85 const SCEV *P2 = SE.getAddExpr(S2, S2);
86
87 const SCEVMulExpr *M0 = cast<SCEVMulExpr>(P0);
88 const SCEVMulExpr *M1 = cast<SCEVMulExpr>(P1);
89 const SCEVMulExpr *M2 = cast<SCEVMulExpr>(P2);
90
91 EXPECT_EQ(cast<SCEVConstant>(M0->getOperand(0))->getValue()->getZExtValue(),
92 2u);
93 EXPECT_EQ(cast<SCEVConstant>(M1->getOperand(0))->getValue()->getZExtValue(),
94 2u);
95 EXPECT_EQ(cast<SCEVConstant>(M2->getOperand(0))->getValue()->getZExtValue(),
96 2u);
97
98 // Before the RAUWs, these are all pointing to separate values.
99 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);
100 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V1);
101 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V2);
102
103 // Do some RAUWs.
104 V2->replaceAllUsesWith(V1);
105 V1->replaceAllUsesWith(V0);
106
107 // After the RAUWs, these should all be pointing to V0.
108 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);
109 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V0);
110 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V0);
111 }
112
TEST_F(ScalarEvolutionsTest,SimplifiedPHI)113 TEST_F(ScalarEvolutionsTest, SimplifiedPHI) {
114 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),
115 std::vector<Type *>(), false);
116 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
117 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
118 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);
119 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);
120 BranchInst::Create(LoopBB, EntryBB);
121 BranchInst::Create(LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)),
122 LoopBB);
123 ReturnInst::Create(Context, nullptr, ExitBB);
124 auto *Ty = Type::getInt32Ty(Context);
125 auto *PN = PHINode::Create(Ty, 2, "", &*LoopBB->begin());
126 PN->addIncoming(Constant::getNullValue(Ty), EntryBB);
127 PN->addIncoming(UndefValue::get(Ty), LoopBB);
128 ScalarEvolution SE = buildSE(*F);
129 auto *S1 = SE.getSCEV(PN);
130 auto *S2 = SE.getSCEV(PN);
131 auto *ZeroConst = SE.getConstant(Ty, 0);
132
133 // At some point, only the first call to getSCEV returned the simplified
134 // SCEVConstant and later calls just returned a SCEVUnknown referencing the
135 // PHI node.
136 EXPECT_EQ(S1, ZeroConst);
137 EXPECT_EQ(S1, S2);
138 }
139
TEST_F(ScalarEvolutionsTest,ExpandPtrTypeSCEV)140 TEST_F(ScalarEvolutionsTest, ExpandPtrTypeSCEV) {
141 // It is to test the fix for PR30213. It exercises the branch in scev
142 // expansion when the value in ValueOffsetPair is a ptr and the offset
143 // is not divisible by the elem type size of value.
144 auto *I8Ty = Type::getInt8Ty(Context);
145 auto *I8PtrTy = Type::getInt8PtrTy(Context);
146 auto *I32Ty = Type::getInt32Ty(Context);
147 auto *I32PtrTy = Type::getInt32PtrTy(Context);
148 FunctionType *FTy =
149 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);
150 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
151 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
152 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);
153 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);
154 BranchInst::Create(LoopBB, EntryBB);
155 ReturnInst::Create(Context, nullptr, ExitBB);
156
157 // loop: ; preds = %loop, %entry
158 // %alloca = alloca i32
159 // %gep0 = getelementptr i32, i32* %alloca, i32 1
160 // %bitcast1 = bitcast i32* %gep0 to i8*
161 // %gep1 = getelementptr i8, i8* %bitcast1, i32 1
162 // %gep2 = getelementptr i8, i8* undef, i32 1
163 // %cmp = icmp ult i8* undef, %bitcast1
164 // %select = select i1 %cmp, i8* %gep1, i8* %gep2
165 // %bitcast2 = bitcast i8* %select to i32*
166 // br i1 undef, label %loop, label %exit
167
168 const DataLayout &DL = F->getParent()->getDataLayout();
169 BranchInst *Br = BranchInst::Create(
170 LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB);
171 AllocaInst *Alloca = new AllocaInst(I32Ty, DL.getAllocaAddrSpace(),
172 "alloca", Br);
173 ConstantInt *Ci32 = ConstantInt::get(Context, APInt(32, 1));
174 GetElementPtrInst *Gep0 =
175 GetElementPtrInst::Create(I32Ty, Alloca, Ci32, "gep0", Br);
176 CastInst *CastA =
177 CastInst::CreateBitOrPointerCast(Gep0, I8PtrTy, "bitcast1", Br);
178 GetElementPtrInst *Gep1 =
179 GetElementPtrInst::Create(I8Ty, CastA, Ci32, "gep1", Br);
180 GetElementPtrInst *Gep2 = GetElementPtrInst::Create(
181 I8Ty, UndefValue::get(I8PtrTy), Ci32, "gep2", Br);
182 CmpInst *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULT,
183 UndefValue::get(I8PtrTy), CastA, "cmp", Br);
184 SelectInst *Sel = SelectInst::Create(Cmp, Gep1, Gep2, "select", Br);
185 CastInst *CastB =
186 CastInst::CreateBitOrPointerCast(Sel, I32PtrTy, "bitcast2", Br);
187
188 ScalarEvolution SE = buildSE(*F);
189 auto *S = SE.getSCEV(CastB);
190 SCEVExpander Exp(SE, M.getDataLayout(), "expander");
191 Value *V =
192 Exp.expandCodeFor(cast<SCEVAddExpr>(S)->getOperand(1), nullptr, Br);
193
194 // Expect the expansion code contains:
195 // %0 = bitcast i32* %bitcast2 to i8*
196 // %uglygep = getelementptr i8, i8* %0, i64 -1
197 // %1 = bitcast i8* %uglygep to i32*
198 EXPECT_TRUE(isa<BitCastInst>(V));
199 Instruction *Gep = cast<Instruction>(V)->getPrevNode();
200 EXPECT_TRUE(isa<GetElementPtrInst>(Gep));
201 EXPECT_TRUE(isa<ConstantInt>(Gep->getOperand(1)));
202 EXPECT_EQ(cast<ConstantInt>(Gep->getOperand(1))->getSExtValue(), -1);
203 EXPECT_TRUE(isa<BitCastInst>(Gep->getPrevNode()));
204 }
205
getInstructionByName(Function & F,StringRef Name)206 static Instruction *getInstructionByName(Function &F, StringRef Name) {
207 for (auto &I : instructions(F))
208 if (I.getName() == Name)
209 return &I;
210 llvm_unreachable("Expected to find instruction!");
211 }
212
TEST_F(ScalarEvolutionsTest,CommutativeExprOperandOrder)213 TEST_F(ScalarEvolutionsTest, CommutativeExprOperandOrder) {
214 LLVMContext C;
215 SMDiagnostic Err;
216 std::unique_ptr<Module> M = parseAssemblyString(
217 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
218 " "
219 "@var_0 = external global i32, align 4"
220 "@var_1 = external global i32, align 4"
221 "@var_2 = external global i32, align 4"
222 " "
223 "declare i32 @unknown(i32, i32, i32)"
224 " "
225 "define void @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) "
226 " local_unnamed_addr { "
227 "entry: "
228 " %entrycond = icmp sgt i32 %n, 0 "
229 " br i1 %entrycond, label %loop.ph, label %for.end "
230 " "
231 "loop.ph: "
232 " %a = load i32, i32* %A, align 4 "
233 " %b = load i32, i32* %B, align 4 "
234 " %mul = mul nsw i32 %b, %a "
235 " %iv0.init = getelementptr inbounds i8, i8* %arr, i32 %mul "
236 " br label %loop "
237 " "
238 "loop: "
239 " %iv0 = phi i8* [ %iv0.inc, %loop ], [ %iv0.init, %loop.ph ] "
240 " %iv1 = phi i32 [ %iv1.inc, %loop ], [ 0, %loop.ph ] "
241 " %conv = trunc i32 %iv1 to i8 "
242 " store i8 %conv, i8* %iv0, align 1 "
243 " %iv0.inc = getelementptr inbounds i8, i8* %iv0, i32 %b "
244 " %iv1.inc = add nuw nsw i32 %iv1, 1 "
245 " %exitcond = icmp eq i32 %iv1.inc, %n "
246 " br i1 %exitcond, label %for.end.loopexit, label %loop "
247 " "
248 "for.end.loopexit: "
249 " br label %for.end "
250 " "
251 "for.end: "
252 " ret void "
253 "} "
254 " "
255 "define void @f_2(i32* %X, i32* %Y, i32* %Z) { "
256 " %x = load i32, i32* %X "
257 " %y = load i32, i32* %Y "
258 " %z = load i32, i32* %Z "
259 " ret void "
260 "} "
261 " "
262 "define void @f_3() { "
263 " %x = load i32, i32* @var_0"
264 " %y = load i32, i32* @var_1"
265 " %z = load i32, i32* @var_2"
266 " ret void"
267 "} "
268 " "
269 "define void @f_4(i32 %a, i32 %b, i32 %c) { "
270 " %x = call i32 @unknown(i32 %a, i32 %b, i32 %c)"
271 " %y = call i32 @unknown(i32 %b, i32 %c, i32 %a)"
272 " %z = call i32 @unknown(i32 %c, i32 %a, i32 %b)"
273 " ret void"
274 "} "
275 ,
276 Err, C);
277
278 assert(M && "Could not parse module?");
279 assert(!verifyModule(*M) && "Must have been well formed!");
280
281 runWithSE(*M, "f_1", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
282 auto *IV0 = getInstructionByName(F, "iv0");
283 auto *IV0Inc = getInstructionByName(F, "iv0.inc");
284
285 auto *FirstExprForIV0 = SE.getSCEV(IV0);
286 auto *FirstExprForIV0Inc = SE.getSCEV(IV0Inc);
287 auto *SecondExprForIV0 = SE.getSCEV(IV0);
288
289 EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0));
290 EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0Inc));
291 EXPECT_TRUE(isa<SCEVAddRecExpr>(SecondExprForIV0));
292 });
293
294 auto CheckCommutativeMulExprs = [&](ScalarEvolution &SE, const SCEV *A,
295 const SCEV *B, const SCEV *C) {
296 EXPECT_EQ(SE.getMulExpr(A, B), SE.getMulExpr(B, A));
297 EXPECT_EQ(SE.getMulExpr(B, C), SE.getMulExpr(C, B));
298 EXPECT_EQ(SE.getMulExpr(A, C), SE.getMulExpr(C, A));
299
300 SmallVector<const SCEV *, 3> Ops0 = {A, B, C};
301 SmallVector<const SCEV *, 3> Ops1 = {A, C, B};
302 SmallVector<const SCEV *, 3> Ops2 = {B, A, C};
303 SmallVector<const SCEV *, 3> Ops3 = {B, C, A};
304 SmallVector<const SCEV *, 3> Ops4 = {C, B, A};
305 SmallVector<const SCEV *, 3> Ops5 = {C, A, B};
306
307 auto *Mul0 = SE.getMulExpr(Ops0);
308 auto *Mul1 = SE.getMulExpr(Ops1);
309 auto *Mul2 = SE.getMulExpr(Ops2);
310 auto *Mul3 = SE.getMulExpr(Ops3);
311 auto *Mul4 = SE.getMulExpr(Ops4);
312 auto *Mul5 = SE.getMulExpr(Ops5);
313
314 EXPECT_EQ(Mul0, Mul1) << "Expected " << *Mul0 << " == " << *Mul1;
315 EXPECT_EQ(Mul1, Mul2) << "Expected " << *Mul1 << " == " << *Mul2;
316 EXPECT_EQ(Mul2, Mul3) << "Expected " << *Mul2 << " == " << *Mul3;
317 EXPECT_EQ(Mul3, Mul4) << "Expected " << *Mul3 << " == " << *Mul4;
318 EXPECT_EQ(Mul4, Mul5) << "Expected " << *Mul4 << " == " << *Mul5;
319 };
320
321 for (StringRef FuncName : {"f_2", "f_3", "f_4"})
322 runWithSE(
323 *M, FuncName, [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
324 CheckCommutativeMulExprs(SE, SE.getSCEV(getInstructionByName(F, "x")),
325 SE.getSCEV(getInstructionByName(F, "y")),
326 SE.getSCEV(getInstructionByName(F, "z")));
327 });
328 }
329
TEST_F(ScalarEvolutionsTest,CompareSCEVComplexity)330 TEST_F(ScalarEvolutionsTest, CompareSCEVComplexity) {
331 FunctionType *FTy =
332 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);
333 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
334 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
335 BasicBlock *LoopBB = BasicBlock::Create(Context, "bb1", F);
336 BranchInst::Create(LoopBB, EntryBB);
337
338 auto *Ty = Type::getInt32Ty(Context);
339 SmallVector<Instruction*, 8> Muls(8), Acc(8), NextAcc(8);
340
341 Acc[0] = PHINode::Create(Ty, 2, "", LoopBB);
342 Acc[1] = PHINode::Create(Ty, 2, "", LoopBB);
343 Acc[2] = PHINode::Create(Ty, 2, "", LoopBB);
344 Acc[3] = PHINode::Create(Ty, 2, "", LoopBB);
345 Acc[4] = PHINode::Create(Ty, 2, "", LoopBB);
346 Acc[5] = PHINode::Create(Ty, 2, "", LoopBB);
347 Acc[6] = PHINode::Create(Ty, 2, "", LoopBB);
348 Acc[7] = PHINode::Create(Ty, 2, "", LoopBB);
349
350 for (int i = 0; i < 20; i++) {
351 Muls[0] = BinaryOperator::CreateMul(Acc[0], Acc[0], "", LoopBB);
352 NextAcc[0] = BinaryOperator::CreateAdd(Muls[0], Acc[4], "", LoopBB);
353 Muls[1] = BinaryOperator::CreateMul(Acc[1], Acc[1], "", LoopBB);
354 NextAcc[1] = BinaryOperator::CreateAdd(Muls[1], Acc[5], "", LoopBB);
355 Muls[2] = BinaryOperator::CreateMul(Acc[2], Acc[2], "", LoopBB);
356 NextAcc[2] = BinaryOperator::CreateAdd(Muls[2], Acc[6], "", LoopBB);
357 Muls[3] = BinaryOperator::CreateMul(Acc[3], Acc[3], "", LoopBB);
358 NextAcc[3] = BinaryOperator::CreateAdd(Muls[3], Acc[7], "", LoopBB);
359
360 Muls[4] = BinaryOperator::CreateMul(Acc[4], Acc[4], "", LoopBB);
361 NextAcc[4] = BinaryOperator::CreateAdd(Muls[4], Acc[0], "", LoopBB);
362 Muls[5] = BinaryOperator::CreateMul(Acc[5], Acc[5], "", LoopBB);
363 NextAcc[5] = BinaryOperator::CreateAdd(Muls[5], Acc[1], "", LoopBB);
364 Muls[6] = BinaryOperator::CreateMul(Acc[6], Acc[6], "", LoopBB);
365 NextAcc[6] = BinaryOperator::CreateAdd(Muls[6], Acc[2], "", LoopBB);
366 Muls[7] = BinaryOperator::CreateMul(Acc[7], Acc[7], "", LoopBB);
367 NextAcc[7] = BinaryOperator::CreateAdd(Muls[7], Acc[3], "", LoopBB);
368 Acc = NextAcc;
369 }
370
371 auto II = LoopBB->begin();
372 for (int i = 0; i < 8; i++) {
373 PHINode *Phi = cast<PHINode>(&*II++);
374 Phi->addIncoming(Acc[i], LoopBB);
375 Phi->addIncoming(UndefValue::get(Ty), EntryBB);
376 }
377
378 BasicBlock *ExitBB = BasicBlock::Create(Context, "bb2", F);
379 BranchInst::Create(LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)),
380 LoopBB);
381
382 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
383 Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB);
384 Acc[2] = BinaryOperator::CreateAdd(Acc[4], Acc[5], "", ExitBB);
385 Acc[3] = BinaryOperator::CreateAdd(Acc[6], Acc[7], "", ExitBB);
386 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
387 Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB);
388 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
389
390 ReturnInst::Create(Context, nullptr, ExitBB);
391
392 ScalarEvolution SE = buildSE(*F);
393
394 EXPECT_NE(nullptr, SE.getSCEV(Acc[0]));
395 }
396
TEST_F(ScalarEvolutionsTest,CompareValueComplexity)397 TEST_F(ScalarEvolutionsTest, CompareValueComplexity) {
398 IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(Context);
399 PointerType *IntPtrPtrTy = IntPtrTy->getPointerTo();
400
401 FunctionType *FTy =
402 FunctionType::get(Type::getVoidTy(Context), {IntPtrTy, IntPtrTy}, false);
403 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
404 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
405
406 Value *X = &*F->arg_begin();
407 Value *Y = &*std::next(F->arg_begin());
408
409 const int ValueDepth = 10;
410 for (int i = 0; i < ValueDepth; i++) {
411 X = new LoadInst(new IntToPtrInst(X, IntPtrPtrTy, "", EntryBB), "",
412 /*isVolatile*/ false, EntryBB);
413 Y = new LoadInst(new IntToPtrInst(Y, IntPtrPtrTy, "", EntryBB), "",
414 /*isVolatile*/ false, EntryBB);
415 }
416
417 auto *MulA = BinaryOperator::CreateMul(X, Y, "", EntryBB);
418 auto *MulB = BinaryOperator::CreateMul(Y, X, "", EntryBB);
419 ReturnInst::Create(Context, nullptr, EntryBB);
420
421 // This test isn't checking for correctness. Today making A and B resolve to
422 // the same SCEV would require deeper searching in CompareValueComplexity,
423 // which will slow down compilation. However, this test can fail (with LLVM's
424 // behavior still being correct) if we ever have a smarter
425 // CompareValueComplexity that is both fast and more accurate.
426
427 ScalarEvolution SE = buildSE(*F);
428 auto *A = SE.getSCEV(MulA);
429 auto *B = SE.getSCEV(MulB);
430 EXPECT_NE(A, B);
431 }
432
TEST_F(ScalarEvolutionsTest,SCEVAddExpr)433 TEST_F(ScalarEvolutionsTest, SCEVAddExpr) {
434 Type *Ty32 = Type::getInt32Ty(Context);
435 Type *ArgTys[] = {Type::getInt64Ty(Context), Ty32};
436
437 FunctionType *FTy =
438 FunctionType::get(Type::getVoidTy(Context), ArgTys, false);
439 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
440
441 Argument *A1 = &*F->arg_begin();
442 Argument *A2 = &*(std::next(F->arg_begin()));
443 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
444
445 Instruction *Trunc = CastInst::CreateTruncOrBitCast(A1, Ty32, "", EntryBB);
446 Instruction *Mul1 = BinaryOperator::CreateMul(Trunc, A2, "", EntryBB);
447 Instruction *Add1 = BinaryOperator::CreateAdd(Mul1, Trunc, "", EntryBB);
448 Mul1 = BinaryOperator::CreateMul(Add1, Trunc, "", EntryBB);
449 Instruction *Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB);
450 // FIXME: The size of this is arbitrary and doesn't seem to change the
451 // result, but SCEV will do quadratic work for these so a large number here
452 // will be extremely slow. We should revisit what and how this is testing
453 // SCEV.
454 for (int i = 0; i < 10; i++) {
455 Mul1 = BinaryOperator::CreateMul(Add2, Add1, "", EntryBB);
456 Add1 = Add2;
457 Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB);
458 }
459
460 ReturnInst::Create(Context, nullptr, EntryBB);
461 ScalarEvolution SE = buildSE(*F);
462 EXPECT_NE(nullptr, SE.getSCEV(Mul1));
463 }
464
GetInstByName(Function & F,StringRef Name)465 static Instruction &GetInstByName(Function &F, StringRef Name) {
466 for (auto &I : instructions(F))
467 if (I.getName() == Name)
468 return I;
469 llvm_unreachable("Could not find instructions!");
470 }
471
TEST_F(ScalarEvolutionsTest,SCEVNormalization)472 TEST_F(ScalarEvolutionsTest, SCEVNormalization) {
473 LLVMContext C;
474 SMDiagnostic Err;
475 std::unique_ptr<Module> M = parseAssemblyString(
476 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
477 " "
478 "@var_0 = external global i32, align 4"
479 "@var_1 = external global i32, align 4"
480 "@var_2 = external global i32, align 4"
481 " "
482 "declare i32 @unknown(i32, i32, i32)"
483 " "
484 "define void @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) "
485 " local_unnamed_addr { "
486 "entry: "
487 " br label %loop.ph "
488 " "
489 "loop.ph: "
490 " br label %loop "
491 " "
492 "loop: "
493 " %iv0 = phi i32 [ %iv0.inc, %loop ], [ 0, %loop.ph ] "
494 " %iv1 = phi i32 [ %iv1.inc, %loop ], [ -2147483648, %loop.ph ] "
495 " %iv0.inc = add i32 %iv0, 1 "
496 " %iv1.inc = add i32 %iv1, 3 "
497 " br i1 undef, label %for.end.loopexit, label %loop "
498 " "
499 "for.end.loopexit: "
500 " ret void "
501 "} "
502 " "
503 "define void @f_2(i32 %a, i32 %b, i32 %c, i32 %d) "
504 " local_unnamed_addr { "
505 "entry: "
506 " br label %loop_0 "
507 " "
508 "loop_0: "
509 " br i1 undef, label %loop_0, label %loop_1 "
510 " "
511 "loop_1: "
512 " br i1 undef, label %loop_2, label %loop_1 "
513 " "
514 " "
515 "loop_2: "
516 " br i1 undef, label %end, label %loop_2 "
517 " "
518 "end: "
519 " ret void "
520 "} "
521 ,
522 Err, C);
523
524 assert(M && "Could not parse module?");
525 assert(!verifyModule(*M) && "Must have been well formed!");
526
527 runWithSE(*M, "f_1", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
528 auto &I0 = GetInstByName(F, "iv0");
529 auto &I1 = *I0.getNextNode();
530
531 auto *S0 = cast<SCEVAddRecExpr>(SE.getSCEV(&I0));
532 PostIncLoopSet Loops;
533 Loops.insert(S0->getLoop());
534 auto *N0 = normalizeForPostIncUse(S0, Loops, SE);
535 auto *D0 = denormalizeForPostIncUse(N0, Loops, SE);
536 EXPECT_EQ(S0, D0) << *S0 << " " << *D0;
537
538 auto *S1 = cast<SCEVAddRecExpr>(SE.getSCEV(&I1));
539 Loops.clear();
540 Loops.insert(S1->getLoop());
541 auto *N1 = normalizeForPostIncUse(S1, Loops, SE);
542 auto *D1 = denormalizeForPostIncUse(N1, Loops, SE);
543 EXPECT_EQ(S1, D1) << *S1 << " " << *D1;
544 });
545
546 runWithSE(*M, "f_2", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
547 auto *L2 = *LI.begin();
548 auto *L1 = *std::next(LI.begin());
549 auto *L0 = *std::next(LI.begin(), 2);
550
551 auto GetAddRec = [&SE](const Loop *L, std::initializer_list<const SCEV *> Ops) {
552 SmallVector<const SCEV *, 4> OpsCopy(Ops);
553 return SE.getAddRecExpr(OpsCopy, L, SCEV::FlagAnyWrap);
554 };
555
556 auto GetAdd = [&SE](std::initializer_list<const SCEV *> Ops) {
557 SmallVector<const SCEV *, 4> OpsCopy(Ops);
558 return SE.getAddExpr(OpsCopy, SCEV::FlagAnyWrap);
559 };
560
561 // We first populate the AddRecs vector with a few "interesting" SCEV
562 // expressions, and then we go through the list and assert that each
563 // expression in it has an invertible normalization.
564
565 std::vector<const SCEV *> Exprs;
566 {
567 const SCEV *V0 = SE.getSCEV(&*F.arg_begin());
568 const SCEV *V1 = SE.getSCEV(&*std::next(F.arg_begin(), 1));
569 const SCEV *V2 = SE.getSCEV(&*std::next(F.arg_begin(), 2));
570 const SCEV *V3 = SE.getSCEV(&*std::next(F.arg_begin(), 3));
571
572 Exprs.push_back(GetAddRec(L0, {V0})); // 0
573 Exprs.push_back(GetAddRec(L0, {V0, V1})); // 1
574 Exprs.push_back(GetAddRec(L0, {V0, V1, V2})); // 2
575 Exprs.push_back(GetAddRec(L0, {V0, V1, V2, V3})); // 3
576
577 Exprs.push_back(
578 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[3], Exprs[0]})); // 4
579 Exprs.push_back(
580 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[0], Exprs[3]})); // 5
581 Exprs.push_back(
582 GetAddRec(L1, {Exprs[1], Exprs[3], Exprs[3], Exprs[1]})); // 6
583
584 Exprs.push_back(GetAdd({Exprs[6], Exprs[3], V2})); // 7
585
586 Exprs.push_back(
587 GetAddRec(L2, {Exprs[4], Exprs[3], Exprs[3], Exprs[5]})); // 8
588
589 Exprs.push_back(
590 GetAddRec(L2, {Exprs[4], Exprs[6], Exprs[7], Exprs[3], V0})); // 9
591 }
592
593 std::vector<PostIncLoopSet> LoopSets;
594 for (int i = 0; i < 8; i++) {
595 LoopSets.emplace_back();
596 if (i & 1)
597 LoopSets.back().insert(L0);
598 if (i & 2)
599 LoopSets.back().insert(L1);
600 if (i & 4)
601 LoopSets.back().insert(L2);
602 }
603
604 for (const auto &LoopSet : LoopSets)
605 for (auto *S : Exprs) {
606 {
607 auto *N = llvm::normalizeForPostIncUse(S, LoopSet, SE);
608 auto *D = llvm::denormalizeForPostIncUse(N, LoopSet, SE);
609
610 // Normalization and then denormalizing better give us back the same
611 // value.
612 EXPECT_EQ(S, D) << "S = " << *S << " D = " << *D << " N = " << *N;
613 }
614 {
615 auto *D = llvm::denormalizeForPostIncUse(S, LoopSet, SE);
616 auto *N = llvm::normalizeForPostIncUse(D, LoopSet, SE);
617
618 // Denormalization and then normalizing better give us back the same
619 // value.
620 EXPECT_EQ(S, N) << "S = " << *S << " N = " << *N;
621 }
622 }
623 });
624 }
625
626 // Expect the call of getZeroExtendExpr will not cost exponential time.
TEST_F(ScalarEvolutionsTest,SCEVZeroExtendExpr)627 TEST_F(ScalarEvolutionsTest, SCEVZeroExtendExpr) {
628 LLVMContext C;
629 SMDiagnostic Err;
630
631 // Generate a function like below:
632 // define void @foo() {
633 // entry:
634 // br label %for.cond
635 //
636 // for.cond:
637 // %0 = phi i64 [ 100, %entry ], [ %dec, %for.inc ]
638 // %cmp = icmp sgt i64 %0, 90
639 // br i1 %cmp, label %for.inc, label %for.cond1
640 //
641 // for.inc:
642 // %dec = add nsw i64 %0, -1
643 // br label %for.cond
644 //
645 // for.cond1:
646 // %1 = phi i64 [ 100, %for.cond ], [ %dec5, %for.inc2 ]
647 // %cmp3 = icmp sgt i64 %1, 90
648 // br i1 %cmp3, label %for.inc2, label %for.cond4
649 //
650 // for.inc2:
651 // %dec5 = add nsw i64 %1, -1
652 // br label %for.cond1
653 //
654 // ......
655 //
656 // for.cond89:
657 // %19 = phi i64 [ 100, %for.cond84 ], [ %dec94, %for.inc92 ]
658 // %cmp93 = icmp sgt i64 %19, 90
659 // br i1 %cmp93, label %for.inc92, label %for.end
660 //
661 // for.inc92:
662 // %dec94 = add nsw i64 %19, -1
663 // br label %for.cond89
664 //
665 // for.end:
666 // %gep = getelementptr i8, i8* null, i64 %dec
667 // %gep6 = getelementptr i8, i8* %gep, i64 %dec5
668 // ......
669 // %gep95 = getelementptr i8, i8* %gep91, i64 %dec94
670 // ret void
671 // }
672 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false);
673 Function *F = cast<Function>(M.getOrInsertFunction("foo", FTy));
674
675 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
676 BasicBlock *CondBB = BasicBlock::Create(Context, "for.cond", F);
677 BasicBlock *EndBB = BasicBlock::Create(Context, "for.end", F);
678 BranchInst::Create(CondBB, EntryBB);
679 BasicBlock *PrevBB = EntryBB;
680
681 Type *I64Ty = Type::getInt64Ty(Context);
682 Type *I8Ty = Type::getInt8Ty(Context);
683 Type *I8PtrTy = Type::getInt8PtrTy(Context);
684 Value *Accum = Constant::getNullValue(I8PtrTy);
685 int Iters = 20;
686 for (int i = 0; i < Iters; i++) {
687 BasicBlock *IncBB = BasicBlock::Create(Context, "for.inc", F, EndBB);
688 auto *PN = PHINode::Create(I64Ty, 2, "", CondBB);
689 PN->addIncoming(ConstantInt::get(Context, APInt(64, 100)), PrevBB);
690 auto *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_SGT, PN,
691 ConstantInt::get(Context, APInt(64, 90)), "cmp",
692 CondBB);
693 BasicBlock *NextBB;
694 if (i != Iters - 1)
695 NextBB = BasicBlock::Create(Context, "for.cond", F, EndBB);
696 else
697 NextBB = EndBB;
698 BranchInst::Create(IncBB, NextBB, Cmp, CondBB);
699 auto *Dec = BinaryOperator::CreateNSWAdd(
700 PN, ConstantInt::get(Context, APInt(64, -1)), "dec", IncBB);
701 PN->addIncoming(Dec, IncBB);
702 BranchInst::Create(CondBB, IncBB);
703
704 Accum = GetElementPtrInst::Create(I8Ty, Accum, Dec, "gep", EndBB);
705
706 PrevBB = CondBB;
707 CondBB = NextBB;
708 }
709 ReturnInst::Create(Context, nullptr, EndBB);
710 ScalarEvolution SE = buildSE(*F);
711 const SCEV *S = SE.getSCEV(Accum);
712 Type *I128Ty = Type::getInt128Ty(Context);
713 SE.getZeroExtendExpr(S, I128Ty);
714 }
715
716 // Make sure that SCEV doesn't introduce illegal ptrtoint/inttoptr instructions
TEST_F(ScalarEvolutionsTest,SCEVZeroExtendExprNonIntegral)717 TEST_F(ScalarEvolutionsTest, SCEVZeroExtendExprNonIntegral) {
718 /*
719 * Create the following code:
720 * func(i64 addrspace(10)* %arg)
721 * top:
722 * br label %L.ph
723 * L.ph:
724 * br label %L
725 * L:
726 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
727 * %add = add i64 %phi2, 1
728 * br i1 undef, label %post, label %L2
729 * post:
730 * %gepbase = getelementptr i64 addrspace(10)* %arg, i64 1
731 * #= %gep = getelementptr i64 addrspace(10)* %gepbase, i64 %add =#
732 * ret void
733 *
734 * We will create the appropriate SCEV expression for %gep and expand it,
735 * then check that no inttoptr/ptrtoint instructions got inserted.
736 */
737
738 // Create a module with non-integral pointers in it's datalayout
739 Module NIM("nonintegral", Context);
740 std::string DataLayout = M.getDataLayoutStr();
741 if (!DataLayout.empty())
742 DataLayout += "-";
743 DataLayout += "ni:10";
744 NIM.setDataLayout(DataLayout);
745
746 Type *T_int1 = Type::getInt1Ty(Context);
747 Type *T_int64 = Type::getInt64Ty(Context);
748 Type *T_pint64 = T_int64->getPointerTo(10);
749
750 FunctionType *FTy =
751 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
752 Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy));
753
754 Argument *Arg = &*F->arg_begin();
755
756 BasicBlock *Top = BasicBlock::Create(Context, "top", F);
757 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
758 BasicBlock *L = BasicBlock::Create(Context, "L", F);
759 BasicBlock *Post = BasicBlock::Create(Context, "post", F);
760
761 IRBuilder<> Builder(Top);
762 Builder.CreateBr(LPh);
763
764 Builder.SetInsertPoint(LPh);
765 Builder.CreateBr(L);
766
767 Builder.SetInsertPoint(L);
768 PHINode *Phi = Builder.CreatePHI(T_int64, 2);
769 Value *Add = Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add");
770 Builder.CreateCondBr(UndefValue::get(T_int1), L, Post);
771 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
772 Phi->addIncoming(Add, L);
773
774 Builder.SetInsertPoint(Post);
775 Value *GepBase = Builder.CreateGEP(Arg, ConstantInt::get(T_int64, 1));
776 Instruction *Ret = Builder.CreateRetVoid();
777
778 ScalarEvolution SE = buildSE(*F);
779 auto *AddRec =
780 SE.getAddRecExpr(SE.getUnknown(GepBase), SE.getConstant(T_int64, 1),
781 LI->getLoopFor(L), SCEV::FlagNUW);
782
783 SCEVExpander Exp(SE, NIM.getDataLayout(), "expander");
784 Exp.disableCanonicalMode();
785 Exp.expandCodeFor(AddRec, T_pint64, Ret);
786
787 // Make sure none of the instructions inserted were inttoptr/ptrtoint.
788 // The verifier will check this.
789 EXPECT_FALSE(verifyFunction(*F, &errs()));
790 }
791
792 // Make sure that SCEV invalidates exit limits after invalidating the values it
793 // depends on when we forget a loop.
TEST_F(ScalarEvolutionsTest,SCEVExitLimitForgetLoop)794 TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetLoop) {
795 /*
796 * Create the following code:
797 * func(i64 addrspace(10)* %arg)
798 * top:
799 * br label %L.ph
800 * L.ph:
801 * br label %L
802 * L:
803 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
804 * %add = add i64 %phi2, 1
805 * %cond = icmp slt i64 %add, 1000; then becomes 2000.
806 * br i1 %cond, label %post, label %L2
807 * post:
808 * ret void
809 *
810 */
811
812 // Create a module with non-integral pointers in it's datalayout
813 Module NIM("nonintegral", Context);
814 std::string DataLayout = M.getDataLayoutStr();
815 if (!DataLayout.empty())
816 DataLayout += "-";
817 DataLayout += "ni:10";
818 NIM.setDataLayout(DataLayout);
819
820 Type *T_int64 = Type::getInt64Ty(Context);
821 Type *T_pint64 = T_int64->getPointerTo(10);
822
823 FunctionType *FTy =
824 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
825 Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy));
826
827 BasicBlock *Top = BasicBlock::Create(Context, "top", F);
828 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
829 BasicBlock *L = BasicBlock::Create(Context, "L", F);
830 BasicBlock *Post = BasicBlock::Create(Context, "post", F);
831
832 IRBuilder<> Builder(Top);
833 Builder.CreateBr(LPh);
834
835 Builder.SetInsertPoint(LPh);
836 Builder.CreateBr(L);
837
838 Builder.SetInsertPoint(L);
839 PHINode *Phi = Builder.CreatePHI(T_int64, 2);
840 auto *Add = cast<Instruction>(
841 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));
842 auto *Limit = ConstantInt::get(T_int64, 1000);
843 auto *Cond = cast<Instruction>(
844 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond"));
845 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post));
846 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
847 Phi->addIncoming(Add, L);
848
849 Builder.SetInsertPoint(Post);
850 Builder.CreateRetVoid();
851
852 ScalarEvolution SE = buildSE(*F);
853 auto *Loop = LI->getLoopFor(L);
854 const SCEV *EC = SE.getBackedgeTakenCount(Loop);
855 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC));
856 EXPECT_TRUE(isa<SCEVConstant>(EC));
857 EXPECT_EQ(cast<SCEVConstant>(EC)->getAPInt().getLimitedValue(), 999u);
858
859 // The add recurrence {5,+,1} does not correspond to any PHI in the IR, and
860 // that is relevant to this test.
861 auto *Five = SE.getConstant(APInt(/*numBits=*/64, 5));
862 auto *AR =
863 SE.getAddRecExpr(Five, SE.getOne(T_int64), Loop, SCEV::FlagAnyWrap);
864 const SCEV *ARAtLoopExit = SE.getSCEVAtScope(AR, nullptr);
865 EXPECT_FALSE(isa<SCEVCouldNotCompute>(ARAtLoopExit));
866 EXPECT_TRUE(isa<SCEVConstant>(ARAtLoopExit));
867 EXPECT_EQ(cast<SCEVConstant>(ARAtLoopExit)->getAPInt().getLimitedValue(),
868 1004u);
869
870 SE.forgetLoop(Loop);
871 Br->eraseFromParent();
872 Cond->eraseFromParent();
873
874 Builder.SetInsertPoint(L);
875 auto *NewCond = Builder.CreateICmp(
876 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond");
877 Builder.CreateCondBr(NewCond, L, Post);
878 const SCEV *NewEC = SE.getBackedgeTakenCount(Loop);
879 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC));
880 EXPECT_TRUE(isa<SCEVConstant>(NewEC));
881 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u);
882 const SCEV *NewARAtLoopExit = SE.getSCEVAtScope(AR, nullptr);
883 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewARAtLoopExit));
884 EXPECT_TRUE(isa<SCEVConstant>(NewARAtLoopExit));
885 EXPECT_EQ(cast<SCEVConstant>(NewARAtLoopExit)->getAPInt().getLimitedValue(),
886 2004u);
887 }
888
889 // Make sure that SCEV invalidates exit limits after invalidating the values it
890 // depends on when we forget a value.
TEST_F(ScalarEvolutionsTest,SCEVExitLimitForgetValue)891 TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetValue) {
892 /*
893 * Create the following code:
894 * func(i64 addrspace(10)* %arg)
895 * top:
896 * br label %L.ph
897 * L.ph:
898 * %load = load i64 addrspace(10)* %arg
899 * br label %L
900 * L:
901 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
902 * %add = add i64 %phi2, 1
903 * %cond = icmp slt i64 %add, %load ; then becomes 2000.
904 * br i1 %cond, label %post, label %L2
905 * post:
906 * ret void
907 *
908 */
909
910 // Create a module with non-integral pointers in it's datalayout
911 Module NIM("nonintegral", Context);
912 std::string DataLayout = M.getDataLayoutStr();
913 if (!DataLayout.empty())
914 DataLayout += "-";
915 DataLayout += "ni:10";
916 NIM.setDataLayout(DataLayout);
917
918 Type *T_int64 = Type::getInt64Ty(Context);
919 Type *T_pint64 = T_int64->getPointerTo(10);
920
921 FunctionType *FTy =
922 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
923 Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy));
924
925 Argument *Arg = &*F->arg_begin();
926
927 BasicBlock *Top = BasicBlock::Create(Context, "top", F);
928 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
929 BasicBlock *L = BasicBlock::Create(Context, "L", F);
930 BasicBlock *Post = BasicBlock::Create(Context, "post", F);
931
932 IRBuilder<> Builder(Top);
933 Builder.CreateBr(LPh);
934
935 Builder.SetInsertPoint(LPh);
936 auto *Load = cast<Instruction>(Builder.CreateLoad(T_int64, Arg, "load"));
937 Builder.CreateBr(L);
938
939 Builder.SetInsertPoint(L);
940 PHINode *Phi = Builder.CreatePHI(T_int64, 2);
941 auto *Add = cast<Instruction>(
942 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));
943 auto *Cond = cast<Instruction>(
944 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Load, "cond"));
945 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post));
946 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
947 Phi->addIncoming(Add, L);
948
949 Builder.SetInsertPoint(Post);
950 Builder.CreateRetVoid();
951
952 ScalarEvolution SE = buildSE(*F);
953 auto *Loop = LI->getLoopFor(L);
954 const SCEV *EC = SE.getBackedgeTakenCount(Loop);
955 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC));
956 EXPECT_FALSE(isa<SCEVConstant>(EC));
957
958 SE.forgetValue(Load);
959 Br->eraseFromParent();
960 Cond->eraseFromParent();
961 Load->eraseFromParent();
962
963 Builder.SetInsertPoint(L);
964 auto *NewCond = Builder.CreateICmp(
965 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond");
966 Builder.CreateCondBr(NewCond, L, Post);
967 const SCEV *NewEC = SE.getBackedgeTakenCount(Loop);
968 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC));
969 EXPECT_TRUE(isa<SCEVConstant>(NewEC));
970 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u);
971 }
972
TEST_F(ScalarEvolutionsTest,SCEVAddRecFromPHIwithLargeConstants)973 TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstants) {
974 // Reference: https://reviews.llvm.org/D37265
975 // Make sure that SCEV does not blow up when constructing an AddRec
976 // with predicates for a phi with the update pattern:
977 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum
978 // when either the initial value of the Phi or the InvariantAccum are
979 // constants that are too large to fit in an ix but are zero when truncated to
980 // ix.
981 FunctionType *FTy =
982 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);
983 Function *F = cast<Function>(M.getOrInsertFunction("addrecphitest", FTy));
984
985 /*
986 Create IR:
987 entry:
988 br label %loop
989 loop:
990 %0 = phi i64 [-9223372036854775808, %entry], [%3, %loop]
991 %1 = shl i64 %0, 32
992 %2 = ashr exact i64 %1, 32
993 %3 = add i64 %2, -9223372036854775808
994 br i1 undef, label %exit, label %loop
995 exit:
996 ret void
997 */
998 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
999 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);
1000 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);
1001
1002 // entry:
1003 BranchInst::Create(LoopBB, EntryBB);
1004 // loop:
1005 auto *MinInt64 =
1006 ConstantInt::get(Context, APInt(64, 0x8000000000000000U, true));
1007 auto *Int64_32 = ConstantInt::get(Context, APInt(64, 32));
1008 auto *Br = BranchInst::Create(
1009 LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB);
1010 auto *Phi = PHINode::Create(Type::getInt64Ty(Context), 2, "", Br);
1011 auto *Shl = BinaryOperator::CreateShl(Phi, Int64_32, "", Br);
1012 auto *AShr = BinaryOperator::CreateExactAShr(Shl, Int64_32, "", Br);
1013 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt64, "", Br);
1014 Phi->addIncoming(MinInt64, EntryBB);
1015 Phi->addIncoming(Add, LoopBB);
1016 // exit:
1017 ReturnInst::Create(Context, nullptr, ExitBB);
1018
1019 // Make sure that SCEV doesn't blow up
1020 ScalarEvolution SE = buildSE(*F);
1021 SCEVUnionPredicate Preds;
1022 const SCEV *Expr = SE.getSCEV(Phi);
1023 EXPECT_NE(nullptr, Expr);
1024 EXPECT_TRUE(isa<SCEVUnknown>(Expr));
1025 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(Expr));
1026 }
1027
TEST_F(ScalarEvolutionsTest,SCEVAddRecFromPHIwithLargeConstantAccum)1028 TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstantAccum) {
1029 // Make sure that SCEV does not blow up when constructing an AddRec
1030 // with predicates for a phi with the update pattern:
1031 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum
1032 // when the InvariantAccum is a constant that is too large to fit in an
1033 // ix but are zero when truncated to ix, and the initial value of the
1034 // phi is not a constant.
1035 Type *Int32Ty = Type::getInt32Ty(Context);
1036 SmallVector<Type *, 1> Types;
1037 Types.push_back(Int32Ty);
1038 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false);
1039 Function *F = cast<Function>(M.getOrInsertFunction("addrecphitest", FTy));
1040
1041 /*
1042 Create IR:
1043 define @addrecphitest(i32)
1044 entry:
1045 br label %loop
1046 loop:
1047 %1 = phi i32 [%0, %entry], [%4, %loop]
1048 %2 = shl i32 %1, 16
1049 %3 = ashr exact i32 %2, 16
1050 %4 = add i32 %3, -2147483648
1051 br i1 undef, label %exit, label %loop
1052 exit:
1053 ret void
1054 */
1055 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
1056 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);
1057 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);
1058
1059 // entry:
1060 BranchInst::Create(LoopBB, EntryBB);
1061 // loop:
1062 auto *MinInt32 = ConstantInt::get(Context, APInt(32, 0x80000000U, true));
1063 auto *Int32_16 = ConstantInt::get(Context, APInt(32, 16));
1064 auto *Br = BranchInst::Create(
1065 LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB);
1066 auto *Phi = PHINode::Create(Int32Ty, 2, "", Br);
1067 auto *Shl = BinaryOperator::CreateShl(Phi, Int32_16, "", Br);
1068 auto *AShr = BinaryOperator::CreateExactAShr(Shl, Int32_16, "", Br);
1069 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt32, "", Br);
1070 auto *Arg = &*(F->arg_begin());
1071 Phi->addIncoming(Arg, EntryBB);
1072 Phi->addIncoming(Add, LoopBB);
1073 // exit:
1074 ReturnInst::Create(Context, nullptr, ExitBB);
1075
1076 // Make sure that SCEV doesn't blow up
1077 ScalarEvolution SE = buildSE(*F);
1078 SCEVUnionPredicate Preds;
1079 const SCEV *Expr = SE.getSCEV(Phi);
1080 EXPECT_NE(nullptr, Expr);
1081 EXPECT_TRUE(isa<SCEVUnknown>(Expr));
1082 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(Expr));
1083 }
1084
TEST_F(ScalarEvolutionsTest,SCEVFoldSumOfTruncs)1085 TEST_F(ScalarEvolutionsTest, SCEVFoldSumOfTruncs) {
1086 // Verify that the following SCEV gets folded to a zero:
1087 // (-1 * (trunc i64 (-1 * %0) to i32)) + (-1 * (trunc i64 %0 to i32)
1088 Type *ArgTy = Type::getInt64Ty(Context);
1089 Type *Int32Ty = Type::getInt32Ty(Context);
1090 SmallVector<Type *, 1> Types;
1091 Types.push_back(ArgTy);
1092 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false);
1093 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
1094 BasicBlock *BB = BasicBlock::Create(Context, "entry", F);
1095 ReturnInst::Create(Context, nullptr, BB);
1096
1097 ScalarEvolution SE = buildSE(*F);
1098
1099 auto *Arg = &*(F->arg_begin());
1100 const auto *ArgSCEV = SE.getSCEV(Arg);
1101
1102 // Build the SCEV
1103 const auto *A0 = SE.getNegativeSCEV(ArgSCEV);
1104 const auto *A1 = SE.getTruncateExpr(A0, Int32Ty);
1105 const auto *A = SE.getNegativeSCEV(A1);
1106
1107 const auto *B0 = SE.getTruncateExpr(ArgSCEV, Int32Ty);
1108 const auto *B = SE.getNegativeSCEV(B0);
1109
1110 const auto *Expr = SE.getAddExpr(A, B);
1111 // Verify that the SCEV was folded to 0
1112 const auto *ZeroConst = SE.getConstant(Int32Ty, 0);
1113 EXPECT_EQ(Expr, ZeroConst);
1114 }
1115
1116 // Check that we can correctly identify the points at which the SCEV of the
1117 // AddRec can be expanded.
TEST_F(ScalarEvolutionsTest,SCEVExpanderIsSafeToExpandAt)1118 TEST_F(ScalarEvolutionsTest, SCEVExpanderIsSafeToExpandAt) {
1119 /*
1120 * Create the following code:
1121 * func(i64 addrspace(10)* %arg)
1122 * top:
1123 * br label %L.ph
1124 * L.ph:
1125 * br label %L
1126 * L:
1127 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
1128 * %add = add i64 %phi2, 1
1129 * %cond = icmp slt i64 %add, 1000; then becomes 2000.
1130 * br i1 %cond, label %post, label %L2
1131 * post:
1132 * ret void
1133 *
1134 */
1135
1136 // Create a module with non-integral pointers in it's datalayout
1137 Module NIM("nonintegral", Context);
1138 std::string DataLayout = M.getDataLayoutStr();
1139 if (!DataLayout.empty())
1140 DataLayout += "-";
1141 DataLayout += "ni:10";
1142 NIM.setDataLayout(DataLayout);
1143
1144 Type *T_int64 = Type::getInt64Ty(Context);
1145 Type *T_pint64 = T_int64->getPointerTo(10);
1146
1147 FunctionType *FTy =
1148 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
1149 Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy));
1150
1151 BasicBlock *Top = BasicBlock::Create(Context, "top", F);
1152 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
1153 BasicBlock *L = BasicBlock::Create(Context, "L", F);
1154 BasicBlock *Post = BasicBlock::Create(Context, "post", F);
1155
1156 IRBuilder<> Builder(Top);
1157 Builder.CreateBr(LPh);
1158
1159 Builder.SetInsertPoint(LPh);
1160 Builder.CreateBr(L);
1161
1162 Builder.SetInsertPoint(L);
1163 PHINode *Phi = Builder.CreatePHI(T_int64, 2);
1164 auto *Add = cast<Instruction>(
1165 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));
1166 auto *Limit = ConstantInt::get(T_int64, 1000);
1167 auto *Cond = cast<Instruction>(
1168 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond"));
1169 Builder.CreateCondBr(Cond, L, Post);
1170 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
1171 Phi->addIncoming(Add, L);
1172
1173 Builder.SetInsertPoint(Post);
1174 Builder.CreateRetVoid();
1175
1176 ScalarEvolution SE = buildSE(*F);
1177 const SCEV *S = SE.getSCEV(Phi);
1178 EXPECT_TRUE(isa<SCEVAddRecExpr>(S));
1179 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
1180 EXPECT_TRUE(AR->isAffine());
1181 EXPECT_FALSE(isSafeToExpandAt(AR, Top->getTerminator(), SE));
1182 EXPECT_FALSE(isSafeToExpandAt(AR, LPh->getTerminator(), SE));
1183 EXPECT_TRUE(isSafeToExpandAt(AR, L->getTerminator(), SE));
1184 EXPECT_TRUE(isSafeToExpandAt(AR, Post->getTerminator(), SE));
1185 }
1186
1187 // Check that SCEV expander does not use the nuw instruction
1188 // for expansion.
TEST_F(ScalarEvolutionsTest,SCEVExpanderNUW)1189 TEST_F(ScalarEvolutionsTest, SCEVExpanderNUW) {
1190 /*
1191 * Create the following code:
1192 * func(i64 %a)
1193 * entry:
1194 * br false, label %exit, label %body
1195 * body:
1196 * %s1 = add i64 %a, -1
1197 * br label %exit
1198 * exit:
1199 * %s = add nuw i64 %a, -1
1200 * ret %s
1201 */
1202
1203 // Create a module.
1204 Module M("SCEVExpanderNUW", Context);
1205
1206 Type *T_int64 = Type::getInt64Ty(Context);
1207
1208 FunctionType *FTy =
1209 FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false);
1210 Function *F = cast<Function>(M.getOrInsertFunction("func", FTy));
1211 Argument *Arg = &*F->arg_begin();
1212 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));
1213
1214 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
1215 BasicBlock *Body = BasicBlock::Create(Context, "body", F);
1216 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
1217
1218 IRBuilder<> Builder(Entry);
1219 ConstantInt *Cond = ConstantInt::get(Context, APInt(1, 0));
1220 Builder.CreateCondBr(Cond, Exit, Body);
1221
1222 Builder.SetInsertPoint(Body);
1223 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
1224 Builder.CreateBr(Exit);
1225
1226 Builder.SetInsertPoint(Exit);
1227 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
1228 S2->setHasNoUnsignedWrap(true);
1229 auto *R = cast<Instruction>(Builder.CreateRetVoid());
1230
1231 ScalarEvolution SE = buildSE(*F);
1232 const SCEV *S = SE.getSCEV(S1);
1233 EXPECT_TRUE(isa<SCEVAddExpr>(S));
1234 SCEVExpander Exp(SE, M.getDataLayout(), "expander");
1235 auto *I = cast<Instruction>(Exp.expandCodeFor(S, nullptr, R));
1236 EXPECT_FALSE(I->hasNoUnsignedWrap());
1237 }
1238
1239 // Check that SCEV expander does not use the nsw instruction
1240 // for expansion.
TEST_F(ScalarEvolutionsTest,SCEVExpanderNSW)1241 TEST_F(ScalarEvolutionsTest, SCEVExpanderNSW) {
1242 /*
1243 * Create the following code:
1244 * func(i64 %a)
1245 * entry:
1246 * br false, label %exit, label %body
1247 * body:
1248 * %s1 = add i64 %a, -1
1249 * br label %exit
1250 * exit:
1251 * %s = add nsw i64 %a, -1
1252 * ret %s
1253 */
1254
1255 // Create a module.
1256 Module M("SCEVExpanderNSW", Context);
1257
1258 Type *T_int64 = Type::getInt64Ty(Context);
1259
1260 FunctionType *FTy =
1261 FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false);
1262 Function *F = cast<Function>(M.getOrInsertFunction("func", FTy));
1263 Argument *Arg = &*F->arg_begin();
1264 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));
1265
1266 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
1267 BasicBlock *Body = BasicBlock::Create(Context, "body", F);
1268 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
1269
1270 IRBuilder<> Builder(Entry);
1271 ConstantInt *Cond = ConstantInt::get(Context, APInt(1, 0));
1272 Builder.CreateCondBr(Cond, Exit, Body);
1273
1274 Builder.SetInsertPoint(Body);
1275 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
1276 Builder.CreateBr(Exit);
1277
1278 Builder.SetInsertPoint(Exit);
1279 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
1280 S2->setHasNoSignedWrap(true);
1281 auto *R = cast<Instruction>(Builder.CreateRetVoid());
1282
1283 ScalarEvolution SE = buildSE(*F);
1284 const SCEV *S = SE.getSCEV(S1);
1285 EXPECT_TRUE(isa<SCEVAddExpr>(S));
1286 SCEVExpander Exp(SE, M.getDataLayout(), "expander");
1287 auto *I = cast<Instruction>(Exp.expandCodeFor(S, nullptr, R));
1288 EXPECT_FALSE(I->hasNoSignedWrap());
1289 }
1290
1291 // Check that SCEV does not save the SCEV -> V
1292 // mapping of SCEV differ from V in NUW flag.
TEST_F(ScalarEvolutionsTest,SCEVCacheNUW)1293 TEST_F(ScalarEvolutionsTest, SCEVCacheNUW) {
1294 /*
1295 * Create the following code:
1296 * func(i64 %a)
1297 * entry:
1298 * %s1 = add i64 %a, -1
1299 * %s2 = add nuw i64 %a, -1
1300 * br label %exit
1301 * exit:
1302 * ret %s
1303 */
1304
1305 // Create a module.
1306 Module M("SCEVCacheNUW", Context);
1307
1308 Type *T_int64 = Type::getInt64Ty(Context);
1309
1310 FunctionType *FTy =
1311 FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false);
1312 Function *F = cast<Function>(M.getOrInsertFunction("func", FTy));
1313 Argument *Arg = &*F->arg_begin();
1314 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));
1315
1316 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
1317 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
1318
1319 IRBuilder<> Builder(Entry);
1320 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
1321 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
1322 S2->setHasNoUnsignedWrap(true);
1323 Builder.CreateBr(Exit);
1324
1325 Builder.SetInsertPoint(Exit);
1326 auto *R = cast<Instruction>(Builder.CreateRetVoid());
1327
1328 ScalarEvolution SE = buildSE(*F);
1329 // Get S2 first to move it to cache.
1330 const SCEV *SC2 = SE.getSCEV(S2);
1331 EXPECT_TRUE(isa<SCEVAddExpr>(SC2));
1332 // Now get S1.
1333 const SCEV *SC1 = SE.getSCEV(S1);
1334 EXPECT_TRUE(isa<SCEVAddExpr>(SC1));
1335 // Expand for S1, it should use S1 not S2 in spite S2
1336 // first in the cache.
1337 SCEVExpander Exp(SE, M.getDataLayout(), "expander");
1338 auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R));
1339 EXPECT_FALSE(I->hasNoUnsignedWrap());
1340 }
1341
1342 // Check that SCEV does not save the SCEV -> V
1343 // mapping of SCEV differ from V in NSW flag.
TEST_F(ScalarEvolutionsTest,SCEVCacheNSW)1344 TEST_F(ScalarEvolutionsTest, SCEVCacheNSW) {
1345 /*
1346 * Create the following code:
1347 * func(i64 %a)
1348 * entry:
1349 * %s1 = add i64 %a, -1
1350 * %s2 = add nsw i64 %a, -1
1351 * br label %exit
1352 * exit:
1353 * ret %s
1354 */
1355
1356 // Create a module.
1357 Module M("SCEVCacheNUW", Context);
1358
1359 Type *T_int64 = Type::getInt64Ty(Context);
1360
1361 FunctionType *FTy =
1362 FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false);
1363 Function *F = cast<Function>(M.getOrInsertFunction("func", FTy));
1364 Argument *Arg = &*F->arg_begin();
1365 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));
1366
1367 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
1368 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
1369
1370 IRBuilder<> Builder(Entry);
1371 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
1372 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
1373 S2->setHasNoSignedWrap(true);
1374 Builder.CreateBr(Exit);
1375
1376 Builder.SetInsertPoint(Exit);
1377 auto *R = cast<Instruction>(Builder.CreateRetVoid());
1378
1379 ScalarEvolution SE = buildSE(*F);
1380 // Get S2 first to move it to cache.
1381 const SCEV *SC2 = SE.getSCEV(S2);
1382 EXPECT_TRUE(isa<SCEVAddExpr>(SC2));
1383 // Now get S1.
1384 const SCEV *SC1 = SE.getSCEV(S1);
1385 EXPECT_TRUE(isa<SCEVAddExpr>(SC1));
1386 // Expand for S1, it should use S1 not S2 in spite S2
1387 // first in the cache.
1388 SCEVExpander Exp(SE, M.getDataLayout(), "expander");
1389 auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R));
1390 EXPECT_FALSE(I->hasNoSignedWrap());
1391 }
1392
1393 } // end anonymous namespace
1394 } // end namespace llvm
1395