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