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