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(new AssumptionCache(F)); 46 DT.reset(new DominatorTree(F)); 47 LI.reset(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(FuncName); 55 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 56 ScalarEvolution SE = buildSE(*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(Type::getVoidTy(Context), 81 std::vector<Type *>(), false); 82 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M); 83 BasicBlock *BB = BasicBlock::Create(Context, "entry", F); 84 ReturnInst::Create(Context, nullptr, BB); 85 86 Type *Ty = Type::getInt1Ty(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); 93 94 const SCEV *S0 = SE.getSCEV(V0); 95 const SCEV *S1 = SE.getSCEV(V1); 96 const SCEV *S2 = SE.getSCEV(V2); 97 98 const SCEV *P0 = SE.getAddExpr(S0, SE.getConstant(S0->getType(), 2)); 99 const SCEV *P1 = SE.getAddExpr(S1, SE.getConstant(S0->getType(), 2)); 100 const SCEV *P2 = SE.getAddExpr(S2, SE.getConstant(S0->getType(), 2)); 101 102 auto *M0 = cast<SCEVAddExpr>(P0); 103 auto *M1 = cast<SCEVAddExpr>(P1); 104 auto *M2 = cast<SCEVAddExpr>(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(V1); 120 V1->replaceAllUsesWith(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(Type::getVoidTy(Context), 130 std::vector<Type *>(), false); 131 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M); 132 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 133 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F); 134 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F); 135 BranchInst::Create(LoopBB, EntryBB); 136 BranchInst::Create(LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), 137 LoopBB); 138 ReturnInst::Create(Context, nullptr, ExitBB); 139 auto *Ty = Type::getInt32Ty(Context); 140 auto *PN = PHINode::Create(Ty, 2, "", &*LoopBB->begin()); 141 PN->addIncoming(Constant::getNullValue(Ty), EntryBB); 142 PN->addIncoming(UndefValue::get(Ty), LoopBB); 143 ScalarEvolution SE = buildSE(*F); 144 auto *S1 = SE.getSCEV(PN); 145 auto *S2 = SE.getSCEV(PN); 146 auto *ZeroConst = SE.getConstant(Ty, 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 "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, C); 233 234 assert(M && "Could not parse module?"); 235 assert(!verifyModule(*M) && "Must have been well formed!"); 236 237 runWithSE(*M, "f_1", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 238 auto *IV0 = getInstructionByName(F, "iv0"); 239 auto *IV0Inc = getInstructionByName(F, "iv0.inc"); 240 241 auto *FirstExprForIV0 = SE.getSCEV(IV0); 242 auto *FirstExprForIV0Inc = SE.getSCEV(IV0Inc); 243 auto *SecondExprForIV0 = SE.getSCEV(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(Ops0); 264 auto *Mul1 = SE.getMulExpr(Ops1); 265 auto *Mul2 = SE.getMulExpr(Ops2); 266 auto *Mul3 = SE.getMulExpr(Ops3); 267 auto *Mul4 = SE.getMulExpr(Ops4); 268 auto *Mul5 = SE.getMulExpr(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, FuncName, [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 280 CheckCommutativeMulExprs(SE, SE.getSCEV(getInstructionByName(F, "x")), 281 SE.getSCEV(getInstructionByName(F, "y")), 282 SE.getSCEV(getInstructionByName(F, "z"))); 283 }); 284 } 285 286 TEST_F(ScalarEvolutionsTest, CompareSCEVComplexity) { 287 FunctionType *FTy = 288 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false); 289 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M); 290 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 291 BasicBlock *LoopBB = BasicBlock::Create(Context, "bb1", F); 292 BranchInst::Create(LoopBB, EntryBB); 293 294 auto *Ty = Type::getInt32Ty(Context); 295 SmallVector<Instruction*, 8> Muls(8), Acc(8), NextAcc(8); 296 297 Acc[0] = PHINode::Create(Ty, 2, "", LoopBB); 298 Acc[1] = PHINode::Create(Ty, 2, "", LoopBB); 299 Acc[2] = PHINode::Create(Ty, 2, "", LoopBB); 300 Acc[3] = PHINode::Create(Ty, 2, "", LoopBB); 301 Acc[4] = PHINode::Create(Ty, 2, "", LoopBB); 302 Acc[5] = PHINode::Create(Ty, 2, "", LoopBB); 303 Acc[6] = PHINode::Create(Ty, 2, "", LoopBB); 304 Acc[7] = PHINode::Create(Ty, 2, "", LoopBB); 305 306 for (int i = 0; i < 20; i++) { 307 Muls[0] = BinaryOperator::CreateMul(Acc[0], Acc[0], "", LoopBB); 308 NextAcc[0] = BinaryOperator::CreateAdd(Muls[0], Acc[4], "", LoopBB); 309 Muls[1] = BinaryOperator::CreateMul(Acc[1], Acc[1], "", LoopBB); 310 NextAcc[1] = BinaryOperator::CreateAdd(Muls[1], Acc[5], "", LoopBB); 311 Muls[2] = BinaryOperator::CreateMul(Acc[2], Acc[2], "", LoopBB); 312 NextAcc[2] = BinaryOperator::CreateAdd(Muls[2], Acc[6], "", LoopBB); 313 Muls[3] = BinaryOperator::CreateMul(Acc[3], Acc[3], "", LoopBB); 314 NextAcc[3] = BinaryOperator::CreateAdd(Muls[3], Acc[7], "", LoopBB); 315 316 Muls[4] = BinaryOperator::CreateMul(Acc[4], Acc[4], "", LoopBB); 317 NextAcc[4] = BinaryOperator::CreateAdd(Muls[4], Acc[0], "", LoopBB); 318 Muls[5] = BinaryOperator::CreateMul(Acc[5], Acc[5], "", LoopBB); 319 NextAcc[5] = BinaryOperator::CreateAdd(Muls[5], Acc[1], "", LoopBB); 320 Muls[6] = BinaryOperator::CreateMul(Acc[6], Acc[6], "", LoopBB); 321 NextAcc[6] = BinaryOperator::CreateAdd(Muls[6], Acc[2], "", LoopBB); 322 Muls[7] = BinaryOperator::CreateMul(Acc[7], Acc[7], "", LoopBB); 323 NextAcc[7] = BinaryOperator::CreateAdd(Muls[7], Acc[3], "", LoopBB); 324 Acc = NextAcc; 325 } 326 327 auto II = LoopBB->begin(); 328 for (int i = 0; i < 8; i++) { 329 PHINode *Phi = cast<PHINode>(&*II++); 330 Phi->addIncoming(Acc[i], LoopBB); 331 Phi->addIncoming(UndefValue::get(Ty), EntryBB); 332 } 333 334 BasicBlock *ExitBB = BasicBlock::Create(Context, "bb2", F); 335 BranchInst::Create(LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), 336 LoopBB); 337 338 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB); 339 Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB); 340 Acc[2] = BinaryOperator::CreateAdd(Acc[4], Acc[5], "", ExitBB); 341 Acc[3] = BinaryOperator::CreateAdd(Acc[6], Acc[7], "", ExitBB); 342 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB); 343 Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB); 344 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB); 345 346 ReturnInst::Create(Context, nullptr, ExitBB); 347 348 ScalarEvolution SE = buildSE(*F); 349 350 EXPECT_NE(nullptr, SE.getSCEV(Acc[0])); 351 } 352 353 TEST_F(ScalarEvolutionsTest, CompareValueComplexity) { 354 IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(Context); 355 PointerType *IntPtrPtrTy = PointerType::getUnqual(Context); 356 357 FunctionType *FTy = 358 FunctionType::get(Type::getVoidTy(Context), {IntPtrTy, IntPtrTy}, false); 359 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M); 360 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 361 362 Value *X = &*F->arg_begin(); 363 Value *Y = &*std::next(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(X, Y, "", EntryBB); 376 auto *MulB = BinaryOperator::CreateMul(Y, X, "", EntryBB); 377 ReturnInst::Create(Context, nullptr, 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); 386 auto *A = SE.getSCEV(MulA); 387 auto *B = SE.getSCEV(MulB); 388 EXPECT_NE(A, B); 389 } 390 391 TEST_F(ScalarEvolutionsTest, SCEVAddExpr) { 392 Type *Ty32 = Type::getInt32Ty(Context); 393 Type *ArgTys[] = {Type::getInt64Ty(Context), Ty32, Ty32, Ty32, Ty32, Ty32}; 394 395 FunctionType *FTy = 396 FunctionType::get(Type::getVoidTy(Context), ArgTys, false); 397 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M); 398 399 Argument *A1 = &*F->arg_begin(); 400 Argument *A2 = &*(std::next(F->arg_begin())); 401 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 402 403 Instruction *Trunc = CastInst::CreateTruncOrBitCast(A1, Ty32, "", EntryBB); 404 Instruction *Mul1 = BinaryOperator::CreateMul(Trunc, A2, "", EntryBB); 405 Instruction *Add1 = BinaryOperator::CreateAdd(Mul1, Trunc, "", EntryBB); 406 Mul1 = BinaryOperator::CreateMul(Add1, Trunc, "", EntryBB); 407 Instruction *Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", 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(Add2, Add1, "", EntryBB); 414 Add1 = Add2; 415 Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB); 416 } 417 418 ReturnInst::Create(Context, nullptr, EntryBB); 419 ScalarEvolution SE = buildSE(*F); 420 EXPECT_NE(nullptr, SE.getSCEV(Mul1)); 421 422 Argument *A3 = &*(std::next(F->arg_begin(), 2)); 423 Argument *A4 = &*(std::next(F->arg_begin(), 3)); 424 Argument *A5 = &*(std::next(F->arg_begin(), 4)); 425 Argument *A6 = &*(std::next(F->arg_begin(), 5)); 426 427 auto *AddWithNUW = cast<SCEVAddExpr>(SE.getAddExpr( 428 SE.getAddExpr(SE.getSCEV(A2), SE.getSCEV(A3), SCEV::FlagNUW), 429 SE.getConstant(APInt(/*numBits=*/32, 5)), SCEV::FlagNUW)); 430 EXPECT_EQ(AddWithNUW->getNumOperands(), 3u); 431 EXPECT_EQ(AddWithNUW->getNoWrapFlags(), SCEV::FlagNUW); 432 433 auto *AddWithAnyWrap = 434 SE.getAddExpr(SE.getSCEV(A3), SE.getSCEV(A4), SCEV::FlagAnyWrap); 435 auto *AddWithAnyWrapNUW = cast<SCEVAddExpr>( 436 SE.getAddExpr(AddWithAnyWrap, SE.getSCEV(A5), SCEV::FlagNUW)); 437 EXPECT_EQ(AddWithAnyWrapNUW->getNumOperands(), 3u); 438 EXPECT_EQ(AddWithAnyWrapNUW->getNoWrapFlags(), SCEV::FlagAnyWrap); 439 440 auto *AddWithNSW = SE.getAddExpr( 441 SE.getSCEV(A2), SE.getConstant(APInt(32, 99)), SCEV::FlagNSW); 442 auto *AddWithNSW_NUW = cast<SCEVAddExpr>( 443 SE.getAddExpr(AddWithNSW, SE.getSCEV(A5), SCEV::FlagNUW)); 444 EXPECT_EQ(AddWithNSW_NUW->getNumOperands(), 3u); 445 EXPECT_EQ(AddWithNSW_NUW->getNoWrapFlags(), SCEV::FlagAnyWrap); 446 447 auto *AddWithNSWNUW = 448 SE.getAddExpr(SE.getSCEV(A2), SE.getSCEV(A4), 449 ScalarEvolution::setFlags(SCEV::FlagNUW, SCEV::FlagNSW)); 450 auto *AddWithNSWNUW_NUW = cast<SCEVAddExpr>( 451 SE.getAddExpr(AddWithNSWNUW, SE.getSCEV(A5), 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 SE.getAddExpr(AddWithNSW, SE.getSCEV(A6), 457 ScalarEvolution::setFlags(SCEV::FlagNUW, 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 "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, C); 520 521 assert(M && "Could not parse module?"); 522 assert(!verifyModule(*M) && "Must have been well formed!"); 523 524 runWithSE(*M, "f_1", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 525 auto &I0 = GetInstByName(F, "iv0"); 526 auto &I1 = *I0.getNextNode(); 527 528 auto *S0 = cast<SCEVAddRecExpr>(SE.getSCEV(&I0)); 529 PostIncLoopSet Loops; 530 Loops.insert(S0->getLoop()); 531 auto *N0 = normalizeForPostIncUse(S0, Loops, SE); 532 auto *D0 = denormalizeForPostIncUse(N0, Loops, SE); 533 EXPECT_EQ(S0, D0) << *S0 << " " << *D0; 534 535 auto *S1 = cast<SCEVAddRecExpr>(SE.getSCEV(&I1)); 536 Loops.clear(); 537 Loops.insert(S1->getLoop()); 538 auto *N1 = normalizeForPostIncUse(S1, Loops, SE); 539 auto *D1 = denormalizeForPostIncUse(N1, Loops, SE); 540 EXPECT_EQ(S1, D1) << *S1 << " " << *D1; 541 }); 542 543 runWithSE(*M, "f_2", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 544 auto *L2 = *LI.begin(); 545 auto *L1 = *std::next(LI.begin()); 546 auto *L0 = *std::next(LI.begin(), 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(OpsCopy, L, 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(OpsCopy, 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(&*F.arg_begin()); 565 const SCEV *V1 = SE.getSCEV(&*std::next(F.arg_begin(), 1)); 566 const SCEV *V2 = SE.getSCEV(&*std::next(F.arg_begin(), 2)); 567 const SCEV *V3 = SE.getSCEV(&*std::next(F.arg_begin(), 3)); 568 569 Exprs.push_back(GetAddRec(L0, {V0})); // 0 570 Exprs.push_back(GetAddRec(L0, {V0, V1})); // 1 571 Exprs.push_back(GetAddRec(L0, {V0, V1, V2})); // 2 572 Exprs.push_back(GetAddRec(L0, {V0, V1, V2, V3})); // 3 573 574 Exprs.push_back( 575 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[3], Exprs[0]})); // 4 576 Exprs.push_back( 577 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[0], Exprs[3]})); // 5 578 Exprs.push_back( 579 GetAddRec(L1, {Exprs[1], Exprs[3], Exprs[3], Exprs[1]})); // 6 580 581 Exprs.push_back(GetAdd({Exprs[6], Exprs[3], V2})); // 7 582 583 Exprs.push_back( 584 GetAddRec(L2, {Exprs[4], Exprs[3], Exprs[3], Exprs[5]})); // 8 585 586 Exprs.push_back( 587 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(L0); 595 if (i & 2) 596 LoopSets.back().insert(L1); 597 if (i & 4) 598 LoopSets.back().insert(L2); 599 } 600 601 for (const auto &LoopSet : LoopSets) 602 for (auto *S : Exprs) { 603 { 604 auto *N = llvm::normalizeForPostIncUse(S, LoopSet, SE); 605 auto *D = llvm::denormalizeForPostIncUse(N, 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, LoopSet, SE); 613 auto *N = llvm::normalizeForPostIncUse(D, 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(Type::getVoidTy(Context), {}, false); 670 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", M); 671 672 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 673 BasicBlock *CondBB = BasicBlock::Create(Context, "for.cond", F); 674 BasicBlock *EndBB = BasicBlock::Create(Context, "for.end", F); 675 BranchInst::Create(CondBB, EntryBB); 676 BasicBlock *PrevBB = EntryBB; 677 678 Type *I64Ty = Type::getInt64Ty(Context); 679 Type *I8Ty = Type::getInt8Ty(Context); 680 Type *I8PtrTy = PointerType::getUnqual(Context); 681 Value *Accum = Constant::getNullValue(I8PtrTy); 682 int Iters = 20; 683 for (int i = 0; i < Iters; i++) { 684 BasicBlock *IncBB = BasicBlock::Create(Context, "for.inc", F, EndBB); 685 auto *PN = PHINode::Create(I64Ty, 2, "", CondBB); 686 PN->addIncoming(ConstantInt::get(Context, APInt(64, 100)), PrevBB); 687 auto *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_SGT, PN, 688 ConstantInt::get(Context, APInt(64, 90)), "cmp", 689 CondBB); 690 BasicBlock *NextBB; 691 if (i != Iters - 1) 692 NextBB = BasicBlock::Create(Context, "for.cond", F, EndBB); 693 else 694 NextBB = EndBB; 695 BranchInst::Create(IncBB, NextBB, Cmp, CondBB); 696 auto *Dec = BinaryOperator::CreateNSWAdd( 697 PN, ConstantInt::get(Context, APInt(64, -1)), "dec", IncBB); 698 PN->addIncoming(Dec, IncBB); 699 BranchInst::Create(CondBB, IncBB); 700 701 Accum = GetElementPtrInst::Create(I8Ty, Accum, PN, "gep", EndBB); 702 703 PrevBB = CondBB; 704 CondBB = NextBB; 705 } 706 ReturnInst::Create(Context, nullptr, EndBB); 707 ScalarEvolution SE = buildSE(*F); 708 const SCEV *S = SE.getSCEV(Accum); 709 S = SE.getLosslessPtrToIntExpr(S); 710 Type *I128Ty = Type::getInt128Ty(Context); 711 SE.getZeroExtendExpr(S, 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(Context); 743 Type *T_pint64 = PointerType::get(Context, 10); 744 745 FunctionType *FTy = 746 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); 747 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM); 748 749 BasicBlock *Top = BasicBlock::Create(Context, "top", F); 750 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); 751 BasicBlock *L = BasicBlock::Create(Context, "L", F); 752 BasicBlock *Post = BasicBlock::Create(Context, "post", F); 753 754 IRBuilder<> Builder(Top); 755 Builder.CreateBr(LPh); 756 757 Builder.SetInsertPoint(LPh); 758 Builder.CreateBr(L); 759 760 Builder.SetInsertPoint(L); 761 PHINode *Phi = Builder.CreatePHI(T_int64, 2); 762 auto *Add = cast<Instruction>( 763 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add")); 764 auto *Limit = ConstantInt::get(T_int64, 1000); 765 auto *Cond = cast<Instruction>( 766 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond")); 767 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post)); 768 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); 769 Phi->addIncoming(Add, L); 770 771 Builder.SetInsertPoint(Post); 772 Builder.CreateRetVoid(); 773 774 ScalarEvolution SE = buildSE(*F); 775 auto *Loop = LI->getLoopFor(L); 776 const SCEV *EC = SE.getBackedgeTakenCount(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(APInt(/*numBits=*/64, 5)); 784 auto *AR = 785 SE.getAddRecExpr(Five, SE.getOne(T_int64), Loop, SCEV::FlagAnyWrap); 786 const SCEV *ARAtLoopExit = SE.getSCEVAtScope(AR, 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(Loop); 793 Br->eraseFromParent(); 794 Cond->eraseFromParent(); 795 796 Builder.SetInsertPoint(L); 797 auto *NewCond = Builder.CreateICmp( 798 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond"); 799 Builder.CreateCondBr(NewCond, L, Post); 800 const SCEV *NewEC = SE.getBackedgeTakenCount(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(AR, 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(Context); 841 Type *T_pint64 = PointerType::get(Context, 10); 842 843 FunctionType *FTy = 844 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); 845 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM); 846 847 Argument *Arg = &*F->arg_begin(); 848 849 BasicBlock *Top = BasicBlock::Create(Context, "top", F); 850 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); 851 BasicBlock *L = BasicBlock::Create(Context, "L", F); 852 BasicBlock *Post = BasicBlock::Create(Context, "post", F); 853 854 IRBuilder<> Builder(Top); 855 Builder.CreateBr(LPh); 856 857 Builder.SetInsertPoint(LPh); 858 auto *Load = cast<Instruction>(Builder.CreateLoad(T_int64, Arg, "load")); 859 Builder.CreateBr(L); 860 861 Builder.SetInsertPoint(L); 862 PHINode *Phi = Builder.CreatePHI(T_int64, 2); 863 auto *Add = cast<Instruction>( 864 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add")); 865 auto *Cond = cast<Instruction>( 866 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Load, "cond")); 867 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post)); 868 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); 869 Phi->addIncoming(Add, L); 870 871 Builder.SetInsertPoint(Post); 872 Builder.CreateRetVoid(); 873 874 ScalarEvolution SE = buildSE(*F); 875 auto *Loop = LI->getLoopFor(L); 876 const SCEV *EC = SE.getBackedgeTakenCount(Loop); 877 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC)); 878 EXPECT_FALSE(isa<SCEVConstant>(EC)); 879 880 SE.forgetValue(Load); 881 Br->eraseFromParent(); 882 Cond->eraseFromParent(); 883 Load->eraseFromParent(); 884 885 Builder.SetInsertPoint(L); 886 auto *NewCond = Builder.CreateICmp( 887 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond"); 888 Builder.CreateCondBr(NewCond, L, Post); 889 const SCEV *NewEC = SE.getBackedgeTakenCount(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(Type::getVoidTy(Context), std::vector<Type *>(), false); 905 Function *F = 906 Function::Create(FTy, Function::ExternalLinkage, "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, "entry", F); 922 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F); 923 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F); 924 925 // entry: 926 BranchInst::Create(LoopBB, EntryBB); 927 // loop: 928 auto *MinInt64 = 929 ConstantInt::get(Context, APInt(64, 0x8000000000000000U, true)); 930 auto *Int64_32 = ConstantInt::get(Context, APInt(64, 32)); 931 auto *Br = BranchInst::Create( 932 LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB); 933 auto *Phi = PHINode::Create(Type::getInt64Ty(Context), 2, "", Br); 934 auto *Shl = BinaryOperator::CreateShl(Phi, Int64_32, "", Br); 935 auto *AShr = BinaryOperator::CreateExactAShr(Shl, Int64_32, "", Br); 936 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt64, "", Br); 937 Phi->addIncoming(MinInt64, EntryBB); 938 Phi->addIncoming(Add, LoopBB); 939 // exit: 940 ReturnInst::Create(Context, nullptr, ExitBB); 941 942 // Make sure that SCEV doesn't blow up 943 ScalarEvolution SE = buildSE(*F); 944 const SCEV *Expr = SE.getSCEV(Phi); 945 EXPECT_NE(nullptr, Expr); 946 EXPECT_TRUE(isa<SCEVUnknown>(Expr)); 947 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(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(Context); 958 SmallVector<Type *, 1> Types; 959 Types.push_back(Int32Ty); 960 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false); 961 Function *F = 962 Function::Create(FTy, Function::ExternalLinkage, "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, "entry", F); 979 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F); 980 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F); 981 982 // entry: 983 BranchInst::Create(LoopBB, EntryBB); 984 // loop: 985 auto *MinInt32 = ConstantInt::get(Context, APInt(32, 0x80000000U, true)); 986 auto *Int32_16 = ConstantInt::get(Context, APInt(32, 16)); 987 auto *Br = BranchInst::Create( 988 LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB); 989 auto *Phi = PHINode::Create(Int32Ty, 2, "", Br); 990 auto *Shl = BinaryOperator::CreateShl(Phi, Int32_16, "", Br); 991 auto *AShr = BinaryOperator::CreateExactAShr(Shl, Int32_16, "", Br); 992 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt32, "", Br); 993 auto *Arg = &*(F->arg_begin()); 994 Phi->addIncoming(Arg, EntryBB); 995 Phi->addIncoming(Add, LoopBB); 996 // exit: 997 ReturnInst::Create(Context, nullptr, ExitBB); 998 999 // Make sure that SCEV doesn't blow up 1000 ScalarEvolution SE = buildSE(*F); 1001 const SCEV *Expr = SE.getSCEV(Phi); 1002 EXPECT_NE(nullptr, Expr); 1003 EXPECT_TRUE(isa<SCEVUnknown>(Expr)); 1004 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(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(Context); 1011 Type *Int32Ty = Type::getInt32Ty(Context); 1012 SmallVector<Type *, 1> Types; 1013 Types.push_back(ArgTy); 1014 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false); 1015 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M); 1016 BasicBlock *BB = BasicBlock::Create(Context, "entry", F); 1017 ReturnInst::Create(Context, nullptr, BB); 1018 1019 ScalarEvolution SE = buildSE(*F); 1020 1021 auto *Arg = &*(F->arg_begin()); 1022 const auto *ArgSCEV = SE.getSCEV(Arg); 1023 1024 // Build the SCEV 1025 const auto *A0 = SE.getNegativeSCEV(ArgSCEV); 1026 const auto *A1 = SE.getTruncateExpr(A0, Int32Ty); 1027 const auto *A = SE.getNegativeSCEV(A1); 1028 1029 const auto *B0 = SE.getTruncateExpr(ArgSCEV, Int32Ty); 1030 const auto *B = SE.getNegativeSCEV(B0); 1031 1032 const auto *Expr = SE.getAddExpr(A, B); 1033 // Verify that the SCEV was folded to 0 1034 const auto *ZeroConst = SE.getConstant(Int32Ty, 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(Context); 1055 1056 FunctionType *FTy = 1057 FunctionType::get(Type::getVoidTy(Context), { T_int64, T_int64 }, false); 1058 Function *F = Function::Create(FTy, Function::ExternalLinkage, "func", M); 1059 Argument *A = &*F->arg_begin(); 1060 Argument *B = &*std::next(F->arg_begin()); 1061 ConstantInt *C = ConstantInt::get(Context, APInt(64, 1)); 1062 1063 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F); 1064 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F); 1065 1066 IRBuilder<> Builder(Entry); 1067 auto *S1 = cast<Instruction>(Builder.CreateAdd(A, C, "s1")); 1068 auto *S2 = cast<Instruction>(Builder.CreateUDiv(S1, B, "s2")); 1069 Builder.CreateBr(Exit); 1070 1071 Builder.SetInsertPoint(Exit); 1072 Builder.CreateRetVoid(); 1073 1074 ScalarEvolution SE = buildSE(*F); 1075 // Get S2 first to move it to cache. 1076 const SCEV *AS = SE.getSCEV(A); 1077 const SCEV *BS = SE.getSCEV(B); 1078 const SCEV *CS = SE.getSCEV(C); 1079 const SCEV *S1S = SE.getSCEV(S1); 1080 const SCEV *S2S = SE.getSCEV(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 "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, C); 1106 1107 ASSERT_TRUE(M && "Could not parse module?"); 1108 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1109 1110 runWithSE(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1111 auto *ScevInc = SE.getSCEV(getInstructionByName(F, "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 "define void @foo(i32 %sz, i32 %pp, i32 %x) { " 1121 "entry: " 1122 " %v0 = add i32 %pp, 0 " 1123 " %v3 = add i32 %pp, 3 " 1124 " %vx = add i32 %pp, %x " 1125 " %vx3 = add i32 %vx, 3 " 1126 " br label %loop.body " 1127 "loop.body: " 1128 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] " 1129 " %xa = add nsw i32 %iv, %v0 " 1130 " %yy = add nsw i32 %iv, %v3 " 1131 " %xb = sub nsw i32 %yy, 3 " 1132 " %iv.next = add nsw i32 %iv, 1 " 1133 " %cmp = icmp sle i32 %iv.next, %sz " 1134 " br i1 %cmp, label %loop.body, label %exit " 1135 "exit: " 1136 " ret void " 1137 "} ", 1138 Err, C); 1139 1140 ASSERT_TRUE(M && "Could not parse module?"); 1141 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1142 1143 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1144 auto *ScevV0 = SE.getSCEV(getInstructionByName(F, "v0")); // %pp 1145 auto *ScevV3 = SE.getSCEV(getInstructionByName(F, "v3")); // (3 + %pp) 1146 auto *ScevVX = SE.getSCEV(getInstructionByName(F, "vx")); // (%pp + %x) 1147 // (%pp + %x + 3) 1148 auto *ScevVX3 = SE.getSCEV(getInstructionByName(F, "vx3")); 1149 auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1150 auto *ScevXA = SE.getSCEV(getInstructionByName(F, "xa")); // {%pp,+,1} 1151 auto *ScevYY = SE.getSCEV(getInstructionByName(F, "yy")); // {(3 + %pp),+,1} 1152 auto *ScevXB = SE.getSCEV(getInstructionByName(F, "xb")); // {%pp,+,1} 1153 auto *ScevIVNext = SE.getSCEV(getInstructionByName(F, "iv.next")); // {1,+,1} 1154 1155 auto diff = [&SE](const SCEV *LHS, const SCEV *RHS) -> std::optional<int> { 1156 auto ConstantDiffOrNone = computeConstantDifference(SE, LHS, RHS); 1157 if (!ConstantDiffOrNone) 1158 return std::nullopt; 1159 1160 auto ExtDiff = ConstantDiffOrNone->getSExtValue(); 1161 int Diff = ExtDiff; 1162 assert(Diff == ExtDiff && "Integer overflow"); 1163 return Diff; 1164 }; 1165 1166 EXPECT_EQ(diff(ScevV3, ScevV0), 3); 1167 EXPECT_EQ(diff(ScevV0, ScevV3), -3); 1168 EXPECT_EQ(diff(ScevV0, ScevV0), 0); 1169 EXPECT_EQ(diff(ScevV3, ScevV3), 0); 1170 EXPECT_EQ(diff(ScevVX3, ScevVX), 3); 1171 EXPECT_EQ(diff(ScevIV, ScevIV), 0); 1172 EXPECT_EQ(diff(ScevXA, ScevXB), 0); 1173 EXPECT_EQ(diff(ScevXA, ScevYY), -3); 1174 EXPECT_EQ(diff(ScevYY, ScevXB), 3); 1175 EXPECT_EQ(diff(ScevIV, ScevIVNext), -1); 1176 EXPECT_EQ(diff(ScevIVNext, ScevIV), 1); 1177 EXPECT_EQ(diff(ScevIVNext, ScevIVNext), 0); 1178 EXPECT_EQ(diff(ScevV0, ScevIV), std::nullopt); 1179 EXPECT_EQ(diff(ScevIVNext, ScevV3), std::nullopt); 1180 EXPECT_EQ(diff(ScevYY, ScevV3), std::nullopt); 1181 }); 1182 } 1183 1184 TEST_F(ScalarEvolutionsTest, SCEVrewriteUnknowns) { 1185 LLVMContext C; 1186 SMDiagnostic Err; 1187 std::unique_ptr<Module> M = parseAssemblyString( 1188 "define void @foo(i32 %i) { " 1189 "entry: " 1190 " %cmp3 = icmp ult i32 %i, 16 " 1191 " br i1 %cmp3, label %loop.body, label %exit " 1192 "loop.body: " 1193 " %iv = phi i32 [ %iv.next, %loop.body ], [ %i, %entry ] " 1194 " %iv.next = add nsw i32 %iv, 1 " 1195 " %cmp = icmp eq i32 %iv.next, 16 " 1196 " br i1 %cmp, label %exit, label %loop.body " 1197 "exit: " 1198 " ret void " 1199 "} ", 1200 Err, C); 1201 1202 ASSERT_TRUE(M && "Could not parse module?"); 1203 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1204 1205 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1206 auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1207 auto *ScevI = SE.getSCEV(getArgByName(F, "i")); // {0,+,1} 1208 1209 ValueToSCEVMapTy RewriteMap; 1210 RewriteMap[cast<SCEVUnknown>(ScevI)->getValue()] = 1211 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17)); 1212 auto *WithUMin = SCEVParameterRewriter::rewrite(ScevIV, SE, RewriteMap); 1213 1214 EXPECT_NE(WithUMin, ScevIV); 1215 auto *AR = dyn_cast<SCEVAddRecExpr>(WithUMin); 1216 EXPECT_TRUE(AR); 1217 EXPECT_EQ(AR->getStart(), 1218 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17))); 1219 EXPECT_EQ(AR->getStepRecurrence(SE), 1220 cast<SCEVAddRecExpr>(ScevIV)->getStepRecurrence(SE)); 1221 }); 1222 } 1223 1224 TEST_F(ScalarEvolutionsTest, SCEVAddNUW) { 1225 LLVMContext C; 1226 SMDiagnostic Err; 1227 std::unique_ptr<Module> M = parseAssemblyString("define void @foo(i32 %x) { " 1228 " ret void " 1229 "} ", 1230 Err, C); 1231 1232 ASSERT_TRUE(M && "Could not parse module?"); 1233 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1234 1235 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1236 auto *X = SE.getSCEV(getArgByName(F, "x")); 1237 auto *One = SE.getOne(X->getType()); 1238 auto *Sum = SE.getAddExpr(X, One, SCEV::FlagNUW); 1239 EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGE, Sum, X)); 1240 EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGT, Sum, X)); 1241 }); 1242 } 1243 1244 TEST_F(ScalarEvolutionsTest, SCEVgetRanges) { 1245 LLVMContext C; 1246 SMDiagnostic Err; 1247 std::unique_ptr<Module> M = parseAssemblyString( 1248 "define void @foo(i32 %i) { " 1249 "entry: " 1250 " br label %loop.body " 1251 "loop.body: " 1252 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] " 1253 " %iv.next = add nsw i32 %iv, 1 " 1254 " %cmp = icmp eq i32 %iv.next, 16 " 1255 " br i1 %cmp, label %exit, label %loop.body " 1256 "exit: " 1257 " ret void " 1258 "} ", 1259 Err, C); 1260 1261 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1262 auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1263 auto *ScevI = SE.getSCEV(getArgByName(F, "i")); 1264 EXPECT_EQ(SE.getUnsignedRange(ScevIV).getLower(), 0); 1265 EXPECT_EQ(SE.getUnsignedRange(ScevIV).getUpper(), 16); 1266 1267 auto *Add = SE.getAddExpr(ScevI, ScevIV); 1268 ValueToSCEVMapTy RewriteMap; 1269 RewriteMap[cast<SCEVUnknown>(ScevI)->getValue()] = 1270 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17)); 1271 auto *AddWithUMin = SCEVParameterRewriter::rewrite(Add, SE, RewriteMap); 1272 EXPECT_EQ(SE.getUnsignedRange(AddWithUMin).getLower(), 0); 1273 EXPECT_EQ(SE.getUnsignedRange(AddWithUMin).getUpper(), 33); 1274 }); 1275 } 1276 1277 TEST_F(ScalarEvolutionsTest, SCEVgetExitLimitForGuardedLoop) { 1278 LLVMContext C; 1279 SMDiagnostic Err; 1280 std::unique_ptr<Module> M = parseAssemblyString( 1281 "define void @foo(i32 %i) { " 1282 "entry: " 1283 " %cmp3 = icmp ult i32 %i, 16 " 1284 " br i1 %cmp3, label %loop.body, label %exit " 1285 "loop.body: " 1286 " %iv = phi i32 [ %iv.next, %loop.body ], [ %i, %entry ] " 1287 " %iv.next = add nsw i32 %iv, 1 " 1288 " %cmp = icmp eq i32 %iv.next, 16 " 1289 " br i1 %cmp, label %exit, label %loop.body " 1290 "exit: " 1291 " ret void " 1292 "} ", 1293 Err, C); 1294 1295 ASSERT_TRUE(M && "Could not parse module?"); 1296 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1297 1298 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1299 auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1300 const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop(); 1301 1302 const SCEV *BTC = SE.getBackedgeTakenCount(L); 1303 EXPECT_FALSE(isa<SCEVConstant>(BTC)); 1304 const SCEV *MaxBTC = SE.getConstantMaxBackedgeTakenCount(L); 1305 EXPECT_EQ(cast<SCEVConstant>(MaxBTC)->getAPInt(), 15); 1306 }); 1307 } 1308 1309 TEST_F(ScalarEvolutionsTest, ImpliedViaAddRecStart) { 1310 LLVMContext C; 1311 SMDiagnostic Err; 1312 std::unique_ptr<Module> M = parseAssemblyString( 1313 "define void @foo(i32* %p) { " 1314 "entry: " 1315 " %x = load i32, i32* %p, !range !0 " 1316 " br label %loop " 1317 "loop: " 1318 " %iv = phi i32 [ %x, %entry], [%iv.next, %backedge] " 1319 " %ne.check = icmp ne i32 %iv, 0 " 1320 " br i1 %ne.check, label %backedge, label %exit " 1321 "backedge: " 1322 " %iv.next = add i32 %iv, -1 " 1323 " br label %loop " 1324 "exit:" 1325 " ret void " 1326 "} " 1327 "!0 = !{i32 0, i32 2147483647}", 1328 Err, C); 1329 1330 ASSERT_TRUE(M && "Could not parse module?"); 1331 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1332 1333 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1334 auto *X = SE.getSCEV(getInstructionByName(F, "x")); 1335 auto *Context = getInstructionByName(F, "iv.next"); 1336 EXPECT_TRUE(SE.isKnownPredicateAt(ICmpInst::ICMP_NE, X, 1337 SE.getZero(X->getType()), Context)); 1338 }); 1339 } 1340 1341 TEST_F(ScalarEvolutionsTest, UnsignedIsImpliedViaOperations) { 1342 LLVMContext C; 1343 SMDiagnostic Err; 1344 std::unique_ptr<Module> M = 1345 parseAssemblyString("define void @foo(i32* %p1, i32* %p2) { " 1346 "entry: " 1347 " %x = load i32, i32* %p1, !range !0 " 1348 " %cond = icmp ne i32 %x, 0 " 1349 " br i1 %cond, label %guarded, label %exit " 1350 "guarded: " 1351 " %y = add i32 %x, -1 " 1352 " ret void " 1353 "exit: " 1354 " ret void " 1355 "} " 1356 "!0 = !{i32 0, i32 2147483647}", 1357 Err, C); 1358 1359 ASSERT_TRUE(M && "Could not parse module?"); 1360 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1361 1362 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1363 auto *X = SE.getSCEV(getInstructionByName(F, "x")); 1364 auto *Y = SE.getSCEV(getInstructionByName(F, "y")); 1365 auto *Guarded = getInstructionByName(F, "y")->getParent(); 1366 ASSERT_TRUE(Guarded); 1367 EXPECT_TRUE( 1368 SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_ULT, Y, X)); 1369 EXPECT_TRUE( 1370 SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_UGT, X, Y)); 1371 }); 1372 } 1373 1374 TEST_F(ScalarEvolutionsTest, ProveImplicationViaNarrowing) { 1375 LLVMContext C; 1376 SMDiagnostic Err; 1377 std::unique_ptr<Module> M = parseAssemblyString( 1378 "define i32 @foo(i32 %start, i32* %q) { " 1379 "entry: " 1380 " %wide.start = zext i32 %start to i64 " 1381 " br label %loop " 1382 "loop: " 1383 " %wide.iv = phi i64 [%wide.start, %entry], [%wide.iv.next, %backedge] " 1384 " %iv = phi i32 [%start, %entry], [%iv.next, %backedge] " 1385 " %cond = icmp eq i64 %wide.iv, 0 " 1386 " br i1 %cond, label %exit, label %backedge " 1387 "backedge: " 1388 " %iv.next = add i32 %iv, -1 " 1389 " %index = zext i32 %iv.next to i64 " 1390 " %load.addr = getelementptr i32, i32* %q, i64 %index " 1391 " %stop = load i32, i32* %load.addr " 1392 " %loop.cond = icmp eq i32 %stop, 0 " 1393 " %wide.iv.next = add nsw i64 %wide.iv, -1 " 1394 " br i1 %loop.cond, label %loop, label %failure " 1395 "exit: " 1396 " ret i32 0 " 1397 "failure: " 1398 " unreachable " 1399 "} ", 1400 Err, C); 1401 1402 ASSERT_TRUE(M && "Could not parse module?"); 1403 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1404 1405 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1406 auto *IV = SE.getSCEV(getInstructionByName(F, "iv")); 1407 auto *Zero = SE.getZero(IV->getType()); 1408 auto *Backedge = getInstructionByName(F, "iv.next")->getParent(); 1409 ASSERT_TRUE(Backedge); 1410 (void)IV; 1411 (void)Zero; 1412 // FIXME: This can only be proved with turned on option 1413 // scalar-evolution-use-expensive-range-sharpening which is currently off. 1414 // Enable the check once it's switched true by default. 1415 // EXPECT_TRUE(SE.isBasicBlockEntryGuardedByCond(Backedge, 1416 // ICmpInst::ICMP_UGT, 1417 // IV, Zero)); 1418 }); 1419 } 1420 1421 TEST_F(ScalarEvolutionsTest, ImpliedCond) { 1422 LLVMContext C; 1423 SMDiagnostic Err; 1424 std::unique_ptr<Module> M = parseAssemblyString( 1425 "define void @foo(i32 %len) { " 1426 "entry: " 1427 " br label %loop " 1428 "loop: " 1429 " %iv = phi i32 [ 0, %entry], [%iv.next, %loop] " 1430 " %iv.next = add nsw i32 %iv, 1 " 1431 " %cmp = icmp slt i32 %iv, %len " 1432 " br i1 %cmp, label %loop, label %exit " 1433 "exit:" 1434 " ret void " 1435 "}", 1436 Err, C); 1437 1438 ASSERT_TRUE(M && "Could not parse module?"); 1439 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1440 1441 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1442 Instruction *IV = getInstructionByName(F, "iv"); 1443 Type *Ty = IV->getType(); 1444 const SCEV *Zero = SE.getZero(Ty); 1445 const SCEV *MinusOne = SE.getMinusOne(Ty); 1446 // {0,+,1}<nuw><nsw> 1447 const SCEV *AddRec_0_1 = SE.getSCEV(IV); 1448 // {0,+,-1}<nw> 1449 const SCEV *AddRec_0_N1 = SE.getNegativeSCEV(AddRec_0_1); 1450 1451 // {0,+,1}<nuw><nsw> > 0 -> {0,+,-1}<nw> < 0 1452 EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SLT, AddRec_0_N1, Zero, 1453 ICmpInst::ICMP_SGT, AddRec_0_1, Zero)); 1454 // {0,+,-1}<nw> < -1 -> {0,+,1}<nuw><nsw> > 0 1455 EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SGT, AddRec_0_1, Zero, 1456 ICmpInst::ICMP_SLT, AddRec_0_N1, MinusOne)); 1457 }); 1458 } 1459 1460 TEST_F(ScalarEvolutionsTest, MatchURem) { 1461 LLVMContext C; 1462 SMDiagnostic Err; 1463 std::unique_ptr<Module> M = parseAssemblyString( 1464 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" " 1465 " " 1466 "define void @test(i32 %a, i32 %b, i16 %c, i64 %d) {" 1467 "entry: " 1468 " %rem1 = urem i32 %a, 2" 1469 " %rem2 = urem i32 %a, 5" 1470 " %rem3 = urem i32 %a, %b" 1471 " %c.ext = zext i16 %c to i32" 1472 " %rem4 = urem i32 %c.ext, 2" 1473 " %ext = zext i32 %rem4 to i64" 1474 " %rem5 = urem i64 %d, 17179869184" 1475 " ret void " 1476 "} ", 1477 Err, C); 1478 1479 assert(M && "Could not parse module?"); 1480 assert(!verifyModule(*M) && "Must have been well formed!"); 1481 1482 runWithSE(*M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1483 for (auto *N : {"rem1", "rem2", "rem3", "rem5"}) { 1484 auto *URemI = getInstructionByName(F, N); 1485 auto *S = SE.getSCEV(URemI); 1486 const SCEV *LHS, *RHS; 1487 EXPECT_TRUE(matchURem(SE, S, LHS, RHS)); 1488 EXPECT_EQ(LHS, SE.getSCEV(URemI->getOperand(0))); 1489 EXPECT_EQ(RHS, SE.getSCEV(URemI->getOperand(1))); 1490 EXPECT_EQ(LHS->getType(), S->getType()); 1491 EXPECT_EQ(RHS->getType(), S->getType()); 1492 } 1493 1494 // Check the case where the urem operand is zero-extended. Make sure the 1495 // match results are extended to the size of the input expression. 1496 auto *Ext = getInstructionByName(F, "ext"); 1497 auto *URem1 = getInstructionByName(F, "rem4"); 1498 auto *S = SE.getSCEV(Ext); 1499 const SCEV *LHS, *RHS; 1500 EXPECT_TRUE(matchURem(SE, S, LHS, RHS)); 1501 EXPECT_NE(LHS, SE.getSCEV(URem1->getOperand(0))); 1502 // RHS and URem1->getOperand(1) have different widths, so compare the 1503 // integer values. 1504 EXPECT_EQ(cast<SCEVConstant>(RHS)->getValue()->getZExtValue(), 1505 cast<SCEVConstant>(SE.getSCEV(URem1->getOperand(1))) 1506 ->getValue() 1507 ->getZExtValue()); 1508 EXPECT_EQ(LHS->getType(), S->getType()); 1509 EXPECT_EQ(RHS->getType(), S->getType()); 1510 }); 1511 } 1512 1513 TEST_F(ScalarEvolutionsTest, SCEVUDivFloorCeiling) { 1514 LLVMContext C; 1515 SMDiagnostic Err; 1516 std::unique_ptr<Module> M = parseAssemblyString("define void @foo() { " 1517 " ret void " 1518 "} ", 1519 Err, C); 1520 1521 ASSERT_TRUE(M && "Could not parse module?"); 1522 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1523 1524 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1525 // Check that SCEV's udiv and uceil handling produce the correct results 1526 // for all 8 bit options. Div-by-zero is deliberately excluded. 1527 for (unsigned N = 0; N < 256; N++) 1528 for (unsigned D = 1; D < 256; D++) { 1529 APInt NInt(8, N); 1530 APInt DInt(8, D); 1531 using namespace llvm::APIntOps; 1532 APInt FloorInt = RoundingUDiv(NInt, DInt, APInt::Rounding::DOWN); 1533 APInt CeilingInt = RoundingUDiv(NInt, DInt, APInt::Rounding::UP); 1534 auto *NS = SE.getConstant(NInt); 1535 auto *DS = SE.getConstant(DInt); 1536 auto *FloorS = cast<SCEVConstant>(SE.getUDivExpr(NS, DS)); 1537 auto *CeilingS = cast<SCEVConstant>(SE.getUDivCeilSCEV(NS, DS)); 1538 ASSERT_TRUE(FloorS->getAPInt() == FloorInt); 1539 ASSERT_TRUE(CeilingS->getAPInt() == CeilingInt); 1540 } 1541 }); 1542 } 1543 1544 TEST_F(ScalarEvolutionsTest, CheckGetPowerOfTwo) { 1545 Module M("CheckGetPowerOfTwo", Context); 1546 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false); 1547 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", M); 1548 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F); 1549 IRBuilder<> Builder(Entry); 1550 Builder.CreateRetVoid(); 1551 ScalarEvolution SE = buildSE(*F); 1552 1553 for (unsigned short i = 0; i < 64; ++i) 1554 EXPECT_TRUE( 1555 dyn_cast<SCEVConstant>(SE.getPowerOfTwo(Type::getInt64Ty(Context), i)) 1556 ->getValue() 1557 ->equalsInt(1ULL << i)); 1558 } 1559 1560 TEST_F(ScalarEvolutionsTest, ApplyLoopGuards) { 1561 LLVMContext C; 1562 SMDiagnostic Err; 1563 std::unique_ptr<Module> M = parseAssemblyString( 1564 "declare void @llvm.assume(i1)\n" 1565 "define void @test(i32 %num) {\n" 1566 "entry:\n" 1567 " %u = urem i32 %num, 4\n" 1568 " %cmp = icmp eq i32 %u, 0\n" 1569 " tail call void @llvm.assume(i1 %cmp)\n" 1570 " %cmp.1 = icmp ugt i32 %num, 0\n" 1571 " tail call void @llvm.assume(i1 %cmp.1)\n" 1572 " br label %for.body\n" 1573 "for.body:\n" 1574 " %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n" 1575 " %inc = add nuw nsw i32 %i.010, 1\n" 1576 " %cmp2 = icmp ult i32 %inc, %num\n" 1577 " br i1 %cmp2, label %for.body, label %exit\n" 1578 "exit:\n" 1579 " ret void\n" 1580 "}\n", 1581 Err, C); 1582 1583 ASSERT_TRUE(M && "Could not parse module?"); 1584 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1585 1586 runWithSE(*M, "test", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1587 auto *TCScev = SE.getSCEV(getArgByName(F, "num")); 1588 auto *ApplyLoopGuardsTC = SE.applyLoopGuards(TCScev, *LI.begin()); 1589 // Assert that the new TC is (4 * ((4 umax %num) /u 4)) 1590 APInt Four(32, 4); 1591 auto *Constant4 = SE.getConstant(Four); 1592 auto *Max = SE.getUMaxExpr(TCScev, Constant4); 1593 auto *Mul = SE.getMulExpr(SE.getUDivExpr(Max, Constant4), Constant4); 1594 ASSERT_TRUE(Mul == ApplyLoopGuardsTC); 1595 }); 1596 } 1597 1598 TEST_F(ScalarEvolutionsTest, ForgetValueWithOverflowInst) { 1599 LLVMContext C; 1600 SMDiagnostic Err; 1601 std::unique_ptr<Module> M = parseAssemblyString( 1602 "declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) " 1603 "define void @foo(i32 %i) { " 1604 "entry: " 1605 " br label %loop.body " 1606 "loop.body: " 1607 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] " 1608 " %iv.next = add nsw i32 %iv, 1 " 1609 " %call = call {i32, i1} @llvm.smul.with.overflow.i32(i32 %iv, i32 -2) " 1610 " %extractvalue = extractvalue {i32, i1} %call, 0 " 1611 " %cmp = icmp eq i32 %iv.next, 16 " 1612 " br i1 %cmp, label %exit, label %loop.body " 1613 "exit: " 1614 " ret void " 1615 "} ", 1616 Err, C); 1617 1618 ASSERT_TRUE(M && "Could not parse module?"); 1619 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1620 1621 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1622 auto *ExtractValue = getInstructionByName(F, "extractvalue"); 1623 auto *IV = getInstructionByName(F, "iv"); 1624 1625 auto *ExtractValueScev = SE.getSCEV(ExtractValue); 1626 EXPECT_NE(ExtractValueScev, nullptr); 1627 1628 SE.forgetValue(IV); 1629 auto *ExtractValueScevForgotten = SE.getExistingSCEV(ExtractValue); 1630 EXPECT_EQ(ExtractValueScevForgotten, nullptr); 1631 }); 1632 } 1633 1634 TEST_F(ScalarEvolutionsTest, ComplexityComparatorIsStrictWeakOrdering) { 1635 // Regression test for a case where caching of equivalent values caused the 1636 // comparator to get inconsistent. 1637 LLVMContext C; 1638 SMDiagnostic Err; 1639 std::unique_ptr<Module> M = parseAssemblyString(R"( 1640 define i32 @foo(i32 %arg0) { 1641 %1 = add i32 %arg0, 1 1642 %2 = add i32 %arg0, 1 1643 %3 = xor i32 %2, %1 1644 %4 = add i32 %3, %2 1645 %5 = add i32 %arg0, 1 1646 %6 = xor i32 %5, %arg0 1647 %7 = add i32 %arg0, %6 1648 %8 = add i32 %5, %7 1649 %9 = xor i32 %8, %7 1650 %10 = add i32 %9, %8 1651 %11 = xor i32 %10, %9 1652 %12 = add i32 %11, %10 1653 %13 = xor i32 %12, %11 1654 %14 = add i32 %12, %13 1655 %15 = add i32 %14, %4 1656 ret i32 %15 1657 })", 1658 Err, C); 1659 1660 ASSERT_TRUE(M && "Could not parse module?"); 1661 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1662 1663 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1664 // When _LIBCPP_HARDENING_MODE == _LIBCPP_HARDENING_MODE_DEBUG, this will 1665 // crash if the comparator has the specific caching bug. 1666 SE.getSCEV(F.getEntryBlock().getTerminator()->getOperand(0)); 1667 }); 1668 } 1669 1670 } // end namespace llvm 1671