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